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?
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.
