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. >>> 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? >>> 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.. ;) -- Egor Pasko
