On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote: > Would someone who understands the ABCD pass be willing to check my patch?
looks like a good catch, Naveen! this is really great that you are keeping an eye on this! > Egor if you still follow the list, could you please take a look? sure! I'll take a look .. I guess tomorrow > 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
