Thanks for the quick response!
(snip)
Egor Pasko wrote:
On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
Egor Pasko wrote:
On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote:
1. changes in the solver are very unwanted because we want to make the
solver as readable as possible (given that the concept is really
complicated). Once we want equivalent Pi operands to behave like a
single Pi operand, we should better link them together in the
inequality graph (zero-edges, both higher and lower graphs). The
solver goes through zero chains just fine.
I agree with the spirit of your comment, however in this case your
suggestion is infeasible. There are two alternatives as I see it,
which are dictated by the specifics of the algorithm. Either:
a) The upper bound and lower bound problems are solved using separate
e-SSA graphs, or
currently they are solved using separate InequalityGraphs (okay, a
single object that works in 2 states: upper and lower). Our e-SSA
contains enough information to build both inequality graphs. So, this
approach should work.
Actually, I think you misunderstood me. Separate inequality graphs are
insufficient. Option (1) is to solve the upper and lower bound problems
with separate e-SSA graphs.
b) The solver is modified to adopt the notion of pi-equivalence when
checking for termination conditions (and _only_ when checking for
termination conditions).
As a thought experiment, consider the implications of allowing zero
edges between pi-renamed variables. It would essentially convey
constraints granted onto pi-renamed variables upon their sources.
This would make it possible for sources to appear constrained by
inequalities that do _not_ dominate them. This is clearly incorrect.
Clearly, this is not my day job too :) I should refresh some memories.
AFAIR we do not constrain the original operand because the edge is
directed :)
Right, but to solve the issue I've identified, you would need to add a
zero edge from a pi-renamed source to it's destination, which is incorrect.
In my opinion something must be done here, or ABCD should simply be
disabled as it is otherwise crippled.
currently ABCD should be correct, but not that capable. We should
re-enable the capabilities. I am not seeing the reason to disable it
now.
Let's go this way. You try to make extra edges in InequalityGraph as I
described, if this does not work, I'll go hunting my memories and fix
it. That may imply taking your original approach. :)
I'm convinced simply adding extra edges won't work. I can try to use
the BidirectionalBubbleSort example to demonstrate why, but expect a
delay. :-)
(snip)
