harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Naveen Neelakantam (JIRA)" <j...@apache.org>
Subject [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Date Tue, 04 Nov 2008 15:08:46 GMT
[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.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message