harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Egor Pasko <egor.pa...@gmail.com>
Subject Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Date Tue, 02 Dec 2008 10:43:31 GMT
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


Mime
View raw message