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
