You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by Naveen Neelakantam <ne...@illinois.edu> on 2008/11/04 17:01:23 UTC
Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd
pass fixes
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.
>
>
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x572 day of Apache Harmony Naveen Neelakantam wrote:
> Hi Egor,
>
> I had started to worry that this topic would be forgotten. Obviously it
> hasn't been because you have been very busy!
>
> I will take a detailed look at your new patch this weekend and get back
> to you. That way I can be sure to have a drink handy, per your
> instructions.:-)
JFYI: Committed revision 764315. Could not wait :)
--
Egor Pasko
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x572 day of Apache Harmony Naveen Neelakantam wrote:
> Hi Egor,
>
> I had started to worry that this topic would be forgotten. Obviously it
> hasn't been because you have been very busy!
>
> I will take a detailed look at your new patch this weekend and get back
> to you. That way I can be sure to have a drink handy, per your
> instructions.:-)
Naveen, thanks! nice to 'hear' from you.
I just could not sleep well, so, to forget this I had to do something
constructive :)
--
Egor Pasko
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic
abcd pass fixes
Posted by Naveen Neelakantam <ne...@illinois.edu>.
Hi Egor,
I had started to worry that this topic would be forgotten. Obviously it
hasn't been because you have been very busy!
I will take a detailed look at your new patch this weekend and get back
to you. That way I can be sure to have a drink handy, per your
instructions.:-)
Naveen
On 3/10/2009 3:25 AM, Egor Pasko wrote:
> On the 0x511 day of Apache Harmony Naveen Neelakantam wrote:
>
>>> on first implementation we checked BidirectionalBubbleSort with the
>>> current ABCD. It removed all checks. IMHO, this is a good argument to
>>> prove that the issue is fixable without introducing principially new
>>> concepts.
>>>
>>>
>> I disagree with your assessment. I believe that although ABCD did
>> work once, it is actually quite fragile. My fix removes a major
>> source of this fragility.
>>
>> And as for introducing new concepts, I believe that has already
>> happened when you decided to introduce an e-SSA that has enhanced pi
>> nodes and that is used for both the upper bound and lower bound
>> problems simultaneously. I think those were good changes based on
>> sound understanding. I believe my change also falls into this
>> category. Please take the time to understand what I am proposing.
>>
>
> Naveen,
>
> sorry for the very late reply. It is not only me very busy, but also
> there had to be a lot of experimentation to find out what is
> happening.
>
> The short story is: "Your patch in HARMONY-6007 is great, awesome,
> it's operation is absolutely correct, it reveals a bunch of serious
> existing problems. I am very thankful for these. Fixing these
> problems covers all issues and adds extra benefits. So, I am going to
> stay with the new version."
>
> Now the full story, take a good seat, have a nice drink and leesen
> carefully :) I would be really glad to see comments, objections,
> advice, counterexamples, etc.
>
> Preface.
>
> I attached my patch to HARMONY-6007, please, take a look (the solver
> contains a lot of trailing space removal, sorry for that).
>
> Chapter 1. Passes.
>
> Optimization passed preceding to "classic_abcd" are:
> "memopt,dce,uce,simplify,dce,uce". I removed "hvn" since I did not
> find cases, where it becomes useful in presence of
> "memopt". "simplify" is required immediately before "classic_abcd"
> (modulo "dce,uce") because the latter relies on constants being
> folded, you can see it by running DaCapo pmd benchmark in debug mode
> using server_static pass.
>
> Chapter 2. Revealed problems.
>
> Naveen, your patch does a great job at termination stage at finding
> arraylength operands even if they are unconnected
> (i.e. unconstrained). Array length operand being unconstrained is a
> bug in "classic_abcd", so I jumped in at fixing this. The problem
> appeared in this pseudocoded situation: "call A() -> int x;
> newarray(size=x);". The fix contains two parts: (1) handling more load
> operations that can produce arraylength operands (Op_LdStatic,
> Op_TauLdInd, Op_DirectCall, Op_TauVirtualCall, etc.) and (2) not
> renaming array length operands in chkbounds instructions so that there
> is a single instance of this arraylen to find in the solver.
>
> Meanwhile I spotted another problem with our approach. Consider the code:
> int arr[] = new int[limit];
> if (i< limit) {
> if (0<= i) {
> arr[i] = 5;
> }
> }
>
> both original version and your patched version failed to eliminate the
> check here. Just because pi renaming logic was incorrect (in fact I
> never looked into it before and relied on many assumptions about what
> in fact it does not do). And there was a bug that relied on the fact
> that Pi instructions always start the block. This is no longer the
> case when we insert tauedge() (this was probably why it broke, not
> sure). Weird, we have a lot of such crap in JIT. So, I fixed, cleaned
> that up a little. I was lazy to verify that it works right with
> nontrivial code structures. Small examples like the above worked. If
> you spot something weird with a relatively small test, I would very
> much appreciate and will fix that faster than this time.
>
> Chapter 3. Results.
>
> I ran DaCapo with both patches in server_static mode with debug build
> (all I could, not everything works, dammit). Original patch in
> HARMONY-6007 ate 9.5% checks, while the new patch ate 9.9555%. Among
> the whole run I found only 2 methods, where original patch
> outperformed the new one, but again I was lazy to spot the problem
> since the methods were quite big.
>
> Almost forgot, regression tests passed with both patches. I should
> commit them into the codebase as real regression tests. TODO.
>
> Chapter 4. Problems remaining.
>
> My solution is still "more fragile" in terms of being resistant to
> adding new opcodes. Whoever adds new opcodes should be careful about
> setting the constrained/unconstrained status on them in the inequality
> graph. I'd like to stick with this solution though, as I said, to
> minimize the amount of levels of abstraction.
>
> Another problem: memopt sucks .. at finding aliases of arraylen loads
> if we are working with fields and not with arrays on stack.
>
> Example:
> public class field {
> public Object ss = new Object();
> public Object[] objs = null;
> private Object[] run(int l) {
> objs = new Object[l];
> for (int i = l-1; i>= 0; i--) {
> objs[i] = ss;
> }
> return objs;
> }
> public static void main(String[] args) {
> field t = new field();
> System.out.println(t.run(10)[0]);
> }
> }
>
> this is probably not killing performance in real cases because there
> is usually some external call in the loop that can potentially rewrite
> the field (using reflection, argh).
>
> If anyone finds more problems with bounds checks removal, please,
> report with tests. To find out how many bounds checks was
> detected/eliminated for each method, this DRLVM option is useful:
> -XX:jit.arg.dump_abcd_stats=true, this dumps the info in the
> ./bounds_checks.log (Though do not forget that other optimizations can
> also eliminate bounds checks as hvn,dabce,fastArrayFill).
>
> Chapter 5. Conclusions.
>
> Naveen, thank you thank you thank you for the great work! Without it I
> would have been clueless about important problem sources for a much
> longer while. Great job!
>
>
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x511 day of Apache Harmony Naveen Neelakantam wrote:
>> on first implementation we checked BidirectionalBubbleSort with the
>> current ABCD. It removed all checks. IMHO, this is a good argument to
>> prove that the issue is fixable without introducing principially new
>> concepts.
>>
>
> I disagree with your assessment. I believe that although ABCD did
> work once, it is actually quite fragile. My fix removes a major
> source of this fragility.
>
> And as for introducing new concepts, I believe that has already
> happened when you decided to introduce an e-SSA that has enhanced pi
> nodes and that is used for both the upper bound and lower bound
> problems simultaneously. I think those were good changes based on
> sound understanding. I believe my change also falls into this
> category. Please take the time to understand what I am proposing.
Naveen,
sorry for the very late reply. It is not only me very busy, but also
there had to be a lot of experimentation to find out what is
happening.
The short story is: "Your patch in HARMONY-6007 is great, awesome,
it's operation is absolutely correct, it reveals a bunch of serious
existing problems. I am very thankful for these. Fixing these
problems covers all issues and adds extra benefits. So, I am going to
stay with the new version."
Now the full story, take a good seat, have a nice drink and leesen
carefully :) I would be really glad to see comments, objections,
advice, counterexamples, etc.
Preface.
I attached my patch to HARMONY-6007, please, take a look (the solver
contains a lot of trailing space removal, sorry for that).
Chapter 1. Passes.
Optimization passed preceding to "classic_abcd" are:
"memopt,dce,uce,simplify,dce,uce". I removed "hvn" since I did not
find cases, where it becomes useful in presence of
"memopt". "simplify" is required immediately before "classic_abcd"
(modulo "dce,uce") because the latter relies on constants being
folded, you can see it by running DaCapo pmd benchmark in debug mode
using server_static pass.
Chapter 2. Revealed problems.
Naveen, your patch does a great job at termination stage at finding
arraylength operands even if they are unconnected
(i.e. unconstrained). Array length operand being unconstrained is a
bug in "classic_abcd", so I jumped in at fixing this. The problem
appeared in this pseudocoded situation: "call A() -> int x;
newarray(size=x);". The fix contains two parts: (1) handling more load
operations that can produce arraylength operands (Op_LdStatic,
Op_TauLdInd, Op_DirectCall, Op_TauVirtualCall, etc.) and (2) not
renaming array length operands in chkbounds instructions so that there
is a single instance of this arraylen to find in the solver.
Meanwhile I spotted another problem with our approach. Consider the code:
int arr[] = new int[limit];
if (i < limit) {
if (0 <= i) {
arr[i] = 5;
}
}
both original version and your patched version failed to eliminate the
check here. Just because pi renaming logic was incorrect (in fact I
never looked into it before and relied on many assumptions about what
in fact it does not do). And there was a bug that relied on the fact
that Pi instructions always start the block. This is no longer the
case when we insert tauedge() (this was probably why it broke, not
sure). Weird, we have a lot of such crap in JIT. So, I fixed, cleaned
that up a little. I was lazy to verify that it works right with
nontrivial code structures. Small examples like the above worked. If
you spot something weird with a relatively small test, I would very
much appreciate and will fix that faster than this time.
Chapter 3. Results.
I ran DaCapo with both patches in server_static mode with debug build
(all I could, not everything works, dammit). Original patch in
HARMONY-6007 ate 9.5% checks, while the new patch ate 9.9555%. Among
the whole run I found only 2 methods, where original patch
outperformed the new one, but again I was lazy to spot the problem
since the methods were quite big.
Almost forgot, regression tests passed with both patches. I should
commit them into the codebase as real regression tests. TODO.
Chapter 4. Problems remaining.
My solution is still "more fragile" in terms of being resistant to
adding new opcodes. Whoever adds new opcodes should be careful about
setting the constrained/unconstrained status on them in the inequality
graph. I'd like to stick with this solution though, as I said, to
minimize the amount of levels of abstraction.
Another problem: memopt sucks .. at finding aliases of arraylen loads
if we are working with fields and not with arrays on stack.
Example:
public class field {
public Object ss = new Object();
public Object[] objs = null;
private Object[] run(int l) {
objs = new Object[l];
for (int i = l-1; i >= 0; i--) {
objs[i] = ss;
}
return objs;
}
public static void main(String[] args) {
field t = new field();
System.out.println(t.run(10)[0]);
}
}
this is probably not killing performance in real cases because there
is usually some external call in the loop that can potentially rewrite
the field (using reflection, argh).
If anyone finds more problems with bounds checks removal, please,
report with tests. To find out how many bounds checks was
detected/eliminated for each method, this DRLVM option is useful:
-XX:jit.arg.dump_abcd_stats=true, this dumps the info in the
./bounds_checks.log (Though do not forget that other optimizations can
also eliminate bounds checks as hvn,dabce,fastArrayFill).
Chapter 5. Conclusions.
Naveen, thank you thank you thank you for the great work! Without it I
would have been clueless about important problem sources for a much
longer while. Great job!
--
Egor Pasko
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic
abcd pass fixes
Posted by Naveen Neelakantam <ne...@illinois.edu>.
(snip)
On 12/2/2008 6:34 AM, Egor Pasko wrote:
>>>>>> 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. :)
>>>>>
>>>>>
>>>> I'm convinced simply adding extra edges won't work. I can try to use
>>>> the BidirectionalBubbleSort example to demonstrate why, but expect a
>>>> delay. :-)
>>>>
>>>>
>>> hm, it worked earlier. The HIR changed locally, so should work
>>> now. Your demonstration would be a really hard work.. ;
>>>
>> I'm confused why you think it would be hard. ABCD currently does not
>> eliminate the bounds checks from BidirectionalBubbleSort...
>>
>
> on first implementation we checked BidirectionalBubbleSort with the
> current ABCD. It removed all checks. IMHO, this is a good argument to
> prove that the issue is fixable without introducing principially new
> concepts.
>
I disagree with your assessment. I believe that although ABCD did work
once, it is actually quite fragile. My fix removes a major source of
this fragility.
And as for introducing new concepts, I believe that has already happened
when you decided to introduce an e-SSA that has enhanced pi nodes and
that is used for both the upper bound and lower bound problems
simultaneously. I think those were good changes based on sound
understanding. I believe my change also falls into this category.
Please take the time to understand what I am proposing.
Naveen
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
> Egor Pasko wrote:
>> On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
>>
>>> Thanks for the quick response!
>>>
>>> (snip)
>>>
>>> Egor Pasko wrote:
>>>
>>>> On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
>>>>
>>>>> Egor Pasko wrote:
>>>>>
>>>>>> On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote:
>>>>>>
>>>>>>
>>>>>> 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.
>>>>
>>> Actually, I think you misunderstood me. Separate inequality graphs
>>> are insufficient. Option (1) is to solve the upper and lower bound
>>> problems with separate e-SSA graphs.
>>>
>>
>> I mean though HIR is the same, we can take different information bits
>> from HIR when constructing upper and lower inequality graphs. And I
>> believe there is enough in HIR to take for both upper and lower
>> problems.
>>
>
> That isn't correct, as far as I can tell. As part of ABCD the SSA
> graph is augmented with pi nodes, which turns it into an e-SSA graph.
> The original paper describes how to do this for the upper bound
> problem and implies that a separate e-SSA graph would be necessary for
> the lower bound problem.
>
> Our implementation of ABCD builds a single e-SSA graph with pi-nodes
> that represent constraints from _both_ the upper and lower bound
> problems. This confuses the information available and is the root
> cause of the problem. Option (1) is to build two separate e-SSA
> graphs (i.e. two separate HIRs).
our pi nodes are richer than in the original paper, they contain all
upper- and lower- related information. That is why I said that a
single e-SSA would be enough.
>>>>> 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 :)
>>>>
>>> Right, but to solve the issue I've identified, you would need to add a
>>> zero edge from a pi-renamed source to it's destination, which is
>>> incorrect.
>>>
>>
>> Edges in InequalityGraph are always pointing from inscruction source
>> to instruction destination. In this case the instruction is pi. What's
>> the problem?
>>
>
> The problem has to do with the _termination_ step of the ABCD solver.
> It is a simple comparison to determine if the source and destination
> vertices are the same and meet the bounds criteria. Pi-renamed
> variables should appear to be the same vertex as far as the
> _termination_ step is concerned.
okay, I cannot say I understand this, sorry :)
I'll manage to get some time for this task, I promise.
>>>>> 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. :)
>>>>
>>> I'm convinced simply adding extra edges won't work. I can try to use
>>> the BidirectionalBubbleSort example to demonstrate why, but expect a
>>> delay. :-)
>>>
>>
>> hm, it worked earlier. The HIR changed locally, so should work
>> now. Your demonstration would be a really hard work.. ;
> I'm confused why you think it would be hard. ABCD currently does not
> eliminate the bounds checks from BidirectionalBubbleSort...
on first implementation we checked BidirectionalBubbleSort with the
current ABCD. It removed all checks. IMHO, this is a good argument to
prove that the issue is fixable without introducing principially new
concepts.
--
Egor Pasko
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic
abcd pass fixes
Posted by Naveen Neelakantam <ne...@illinois.edu>.
Egor Pasko wrote:
> On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
>
>> Thanks for the quick response!
>>
>> (snip)
>>
>> Egor Pasko wrote:
>>
>>> On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
>>>
>>>
>>>> Egor Pasko wrote:
>>>>
>>>>
>>>>> On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote:
>>>>>
>>>>>
>>>>> 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.
>>>
>>>
>> Actually, I think you misunderstood me. Separate inequality graphs
>> are insufficient. Option (1) is to solve the upper and lower bound
>> problems with separate e-SSA graphs.
>>
>
> I mean though HIR is the same, we can take different information bits
> from HIR when constructing upper and lower inequality graphs. And I
> believe there is enough in HIR to take for both upper and lower
> problems.
>
That isn't correct, as far as I can tell. As part of ABCD the SSA graph
is augmented with pi nodes, which turns it into an e-SSA graph. The
original paper describes how to do this for the upper bound problem and
implies that a separate e-SSA graph would be necessary for the lower
bound problem.
Our implementation of ABCD builds a single e-SSA graph with pi-nodes
that represent constraints from _both_ the upper and lower bound
problems. This confuses the information available and is the root cause
of the problem. Option (1) is to build two separate e-SSA graphs (i.e.
two separate HIRs).
>>>> 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 :)
>>>
>>>
>> Right, but to solve the issue I've identified, you would need to add a
>> zero edge from a pi-renamed source to it's destination, which is
>> incorrect.
>>
>
> Edges in InequalityGraph are always pointing from inscruction source
> to instruction destination. In this case the instruction is pi. What's
> the problem?
>
The problem has to do with the _termination_ step of the ABCD solver.
It is a simple comparison to determine if the source and destination
vertices are the same and meet the bounds criteria. Pi-renamed
variables should appear to be the same vertex as far as the
_termination_ step is concerned.
>>>> 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. :)
>>>
>>>
>> I'm convinced simply adding extra edges won't work. I can try to use
>> the BidirectionalBubbleSort example to demonstrate why, but expect a
>> delay. :-)
>>
>
> hm, it worked earlier. The HIR changed locally, so should work
> now. Your demonstration would be a really hard work.. ;
I'm confused why you think it would be hard. ABCD currently does not
eliminate the bounds checks from BidirectionalBubbleSort...
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
> Thanks for the quick response!
>
> (snip)
>
> Egor Pasko wrote:
>> On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
>>
>>> Egor Pasko wrote:
>>>
>>>> On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote:
>>>>
>>>>
>>>> 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.
>>
> Actually, I think you misunderstood me. Separate inequality graphs
> are insufficient. Option (1) is to solve the upper and lower bound
> problems with separate e-SSA graphs.
I mean though HIR is the same, we can take different information bits
from HIR when constructing upper and lower inequality graphs. And I
believe there is enough in HIR to take for both upper and lower
problems.
>>> 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 :)
>>
> Right, but to solve the issue I've identified, you would need to add a
> zero edge from a pi-renamed source to it's destination, which is
> incorrect.
Edges in InequalityGraph are always pointing from inscruction source
to instruction destination. In this case the instruction is pi. What's
the problem?
>>> 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. :)
>>
> I'm convinced simply adding extra edges won't work. I can try to use
> the BidirectionalBubbleSort example to demonstrate why, but expect a
> delay. :-)
hm, it worked earlier. The HIR changed locally, so should work
now. Your demonstration would be a really hard work.. ;)
--
Egor Pasko
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic
abcd pass fixes
Posted by Naveen Neelakantam <ne...@illinois.edu>.
Thanks for the quick response!
(snip)
Egor Pasko wrote:
> On the 0x50E day of Apache Harmony Naveen Neelakantam wrote:
>
>> Egor Pasko wrote:
>>
>>> On the 0x4F2 day of Apache Harmony Naveen Neelakantam wrote:
>>>
>>>
>>>
>>> 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.
>
Actually, I think you misunderstood me. Separate inequality graphs are
insufficient. Option (1) is to solve the upper and lower bound problems
with separate e-SSA graphs.
>> 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 :)
>
Right, but to solve the issue I've identified, you would need to add a
zero edge from a pi-renamed source to it's destination, which is incorrect.
>> 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. :)
>
I'm convinced simply adding extra edges won't work. I can try to use
the BidirectionalBubbleSort example to demonstrate why, but expect a
delay. :-)
(snip)
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
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
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic
abcd pass fixes
Posted by Naveen Neelakantam <ne...@illinois.edu>.
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
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.
In my opinion something must be done here, or ABCD should simply be
disabled as it is otherwise crippled.
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.
>>>
>>>
>>>
>>
>
>
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
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.
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: 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
Re: Fwd: [jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass fixes
Posted by Egor Pasko <eg...@gmail.com>.
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