harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Naveen Neelakantam <neela...@illinois.edu>
Subject Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Date Tue, 02 Dec 2008 11:37:29 GMT
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...

Mime
View raw message