On the 0x50E day of Apache Harmony Naveen Neelakantam wrote: > 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).
our pi nodes are richer than in the original paper, they contain all upper- and lower- related information. That is why I said that a single e-SSA would be enough. >>>>> 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. okay, I cannot say I understand this, sorry :) I'll manage to get some time for this task, I promise. >>>>> 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... on first implementation we checked BidirectionalBubbleSort with the current ABCD. It removed all checks. IMHO, this is a good argument to prove that the issue is fixable without introducing principially new concepts. -- Egor Pasko
