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 (zeroedges, 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
>>>> eSSA graphs, or
>>>>
>>>>
>>> currently they are solved using separate InequalityGraphs (okay, a
>>> single object that works in 2 states: upper and lower). Our eSSA
>>> 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 eSSA 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 eSSA graph. The
original paper describes how to do this for the upper bound problem and
implies that a separate eSSA graph would be necessary for the lower
bound problem.
Our implementation of ABCD builds a single eSSA graph with pinodes
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 eSSA graphs (i.e.
two separate HIRs).
>>>> b) The solver is modified to adopt the notion of piequivalence when
>>>> checking for termination conditions (and _only_ when checking for
>>>> termination conditions).
>>>>
>>>> As a thought experiment, consider the implications of allowing zero
>>>> edges between pirenamed variables. It would essentially convey
>>>> constraints granted onto pirenamed 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 pirenamed 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. Pirenamed
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
>>> reenable 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...
