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:05:03 GMT
On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
> Sorry for the delayed response.  Clearly this is not my "day" job.  :-)
>
> Responses are inline.
>
> Egor Pasko wrote:
>> On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote:
>>   
>>> Would someone who understands the ABCD pass be willing to check my patch?
>>>
>>> Egor if you still follow the list, could you please take a look?
>>>     
>>
>> Naveen, again thanks for the great work!
>>
>> though I have some concerns about your patch:
>>
>> 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.

> 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 :)

> 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. :)

> Clearly this is a complicated problem, and I welcome argument. :-)
>> 2. "hvn,simplify,dce,uce,memopt,dce,uce" -- hmm.. this is big change,
>>    may affect a lot. Does anybody run benchmarks these days to ensure
>>    we do not affect performance with this?
>>   
> Can someone please comment on this?  I too am very concerned about the
> effect this might have on compilation speed.
>> 3. "memopt" contains "hvn", is there really a reason to run it twice?
>>   
> Probably not.
>
> I will try removing hvn from the mix and see what happens.  Thanks for
> the heads up
>>   
>>> Thanks,
>>> Naveen
>>>
>>> Naveen Neelakantam (JIRA) wrote:
>>>     
>>>> [drlvm][jit][abcd] classic abcd pass fixes
>>>> ------------------------------------------
>>>>
>>>>                  Key: HARMONY-6007
>>>>                  URL: https://issues.apache.org/jira/browse/HARMONY-6007
>>>>              Project: Harmony
>>>>           Issue Type: Bug
>>>>          Environment: RHEL4, 32-bit x86, gcc 4.1.2
>>>>             Reporter: Naveen Neelakantam
>>>>
>>>>
>>>> The ABCD pass has effectively been crippled by changes that have been made
to DRLVM over the past year (I haven't been able to narrow down when the change happened).
>>>>
>>>> The good news is that with two simple fixes, ABCD works again.  The attached
patch adds the necessary fixes.
>>>>
>>>> To see the problem however you can try running the bi-directional bubble
sort from HARMONY-1564.  It is well-known that ABCD should be able to eliminate all the bounds
checks from the sort algorithm.  However, if you run drlvm without this patch, none of the
bounds checks are eliminated.  You can examine the logs by doing the following:
>>>>
>>>>       
>>>>> java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump
-Xem:server_static BidirectionalBubbleSort
>>>>>
>>>>>         
>>>> After applying the patch, all the bounds checks will once again be eliminated.
 There were two separate problems to blame, which this patch addresses:
>>>> 1) Harmony now inserts multiple "arraylen" operations when translating from
bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen"
operation for the same array).  This redundancy must be eliminated before running ABCD otherwise
the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity.
 Thankfully, solving the problem is as simple as running the following passes before ABCD:
"hvn,simplify,dce,uce,memopt,dce,uce".
>>>> 2) Our implementation of ABCD includes a novel design by Egor Pasko where
both the upper-bound and lower-bound problems can be solved using the same inequality graph.
 In addition the implementation adds more constraints to the graph than the original ABCD
authors specified.  Both improvements are correct, except that they can prevent the ABCD solver
from finding valid solutions because pi-renamed variables appear to be different.  The patch
modifies the solver so that it treats pi-renamed variables as equivalent when checking for
termination conditions.
>>>>
>>>> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass
with these changes.
>>>>
>>>>
>>>>       
>>>     
>>
>>   
>
>

-- 
Egor Pasko


Mime
View raw message