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 14:34:58 GMT
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
>>>>>>    solver as readable as possible (given that the concept is really
>>>>>>    complicated). Once we want equivalent Pi operands to behave like
>>>>>>    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

Egor Pasko

View raw message