Egor Pasko wrote:
On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
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.
I mean though HIR is the same, we can take different information bits
from HIR when constructing upper and lower inequality graphs. And I
believe there is enough in HIR to take for both upper and lower
problems.
That isn't correct, as far as I can tell. As part of ABCD the SSA graph
is augmented with pi nodes, which turns it into an e-SSA graph. The
original paper describes how to do this for the upper bound problem and
implies that a separate e-SSA graph would be necessary for the lower
bound problem.
Our implementation of ABCD builds a single e-SSA graph with pi-nodes
that represent constraints from _both_ the upper and lower bound
problems. This confuses the information available and is the root cause
of the problem. Option (1) is to build two separate e-SSA graphs (i.e.
two separate HIRs).
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.
Edges in InequalityGraph are always pointing from inscruction source
to instruction destination. In this case the instruction is pi. What's
the problem?
The problem has to do with the _termination_ step of the ABCD solver.
It is a simple comparison to determine if the source and destination
vertices are the same and meet the bounds criteria. Pi-renamed
variables should appear to be the same vertex as far as the
_termination_ step is concerned.
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. :-)
hm, it worked earlier. The HIR changed locally, so should work
now. Your demonstration would be a really hard work.. ;
I'm confused why you think it would be hard. ABCD currently does not
eliminate the bounds checks from BidirectionalBubbleSort...
