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 (zeroedges, both higher and lower graphs). The
solver goes through zero chains just fine.
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?
3. "memopt" contains "hvn", is there really a reason to run it twice?
> Thanks,
> Naveen
>
> Naveen Neelakantam (JIRA) wrote:
> > [drlvm][jit][abcd] classic abcd pass fixes
> > 
> >
> > Key: HARMONY6007
> > URL: https://issues.apache.org/jira/browse/HARMONY6007
> > Project: Harmony
> > Issue Type: Bug
> > Environment: RHEL4, 32bit 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 bidirectional bubble sort from
HARMONY1564. It is wellknown 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 postdominates 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
upperbound and lowerbound 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 pirenamed variables appear to be different. The patch modifies the
solver so that it treats pirenamed variables as equivalent when checking for termination
conditions.
> >
> > I've verified that HARMONY2141, HARMONY2144, and HARMONY2147 still pass with
these changes.
> >
> >
>
>

Egor Pasko
