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...@uiuc.edu> on 2006/10/03 05:39:41 UTC
Re: [drlvm][jit] possible ABCD bug
Hello Egor,
I finally got a chance to read through your code. It is well
designed, and correct (as far as I can tell). I especially like the
way that the upper bounds solver works as the lower bounds solver
simply by flipping a flag (and both operate on the same inequality
graph). Very nice!
I made some changes that you might be interested in, which I've
uploaded in the form of a patch. They are (in the order they appear
in the patch file):
1) In updateMemDistanceWithPredecessors, it should not be possible
for the dest operand to have a usable memoized value. This is simply
because if it did, updateMemDistanceWithPredecessors would not have
been called. I therefore replaced some code with an assert.
2) Also in updateMemDistanceWithPredecessors, I added an
optimization. Essentially, we can take advantage of ProveResult
being a lattice (i.e. is monotonic) to prevent some recursive proofs.
3) I fixed a small error in testDoubleCycleGraph().
4) Fixed a gcc 4.1.1 syntax error in the header.
Once again, your code is very good. It is also nice that it matches
the algorithm outlined in the ABCD paper wherever possible.
Is there something else I can do to help?
Naveen
On Sep 26, 2006, at 3:50 AM, Egor Pasko wrote:
> On the 0x1EF day of Apache Harmony Naveen Neelakantam wrote:
>
> Naveen, I am glad to see someone interested in ABCD. Hope for
> collaboration and a lot of fun with the code :)
>
> I attached my solver to HARMONY-1564 (oops, sorry for .tar.gz, I am so
> used to it:) It is just the implementation of the solver with a number
> of tests to play with. Though, it depends on Log.h, Stl.h and types.h
> and is better placed in working_vm/vm/jitrino/src/optimizer/abcd as I
> expected to place it.
>
> To make it real need to create InequalityGraph from HIR, that's what I
> started to do already. Not finished, unfortunately. I will publish the
> sketches if you are eager to see them ASAP. I guess, it will take some
> time for you to play with the solver, though :)
>
> Plz, do not hesitate to ask any question on the code. I pretend that
> it should be a more easy read than the present implementation. So, I
> would appreciate any comments.
>
> It makes sense to make a separate JIRA for our ABCD
> improvements. That's a TODO.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm][jit] possible ABCD bug
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x1F9 day of Apache Harmony Naveen Neelakantam wrote:
> On Oct 4, 2006, at 12:53 AM, Egor Pasko wrote:
>
> >>> One more to say on the patch:
> >>> + // meetBest(Reduced, x) <= Reduced
> >>>
> >>> should be:
> >>> + // meetBest(Reduced, x) >= Reduced
> >>> (just a comment, but still...)
> >>>
> >>> so, could you, please, refresh the patch with my suggestions
> >>> implemented?
> >>
> >> Will do, once we come to agreement above.
> >
> > we have it now
>
> Ok, I updated the patch. However I also added a few more changes. :-)
Thank you, Naveen, I looked through the patch and completely agree to
it. I'll update you with my changes soon.
> Basically, I redefined the ProveResult enum so that the lattice True
> > Reduced > False is also true using integer arithmetic. What do you
> think?
I like it!
--
Egor Pasko, Intel Managed Runtime Division
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm][jit] possible ABCD bug
Posted by Naveen Neelakantam <ne...@uiuc.edu>.
On Oct 4, 2006, at 12:53 AM, Egor Pasko wrote:
>>> One more to say on the patch:
>>> + // meetBest(Reduced, x) <= Reduced
>>>
>>> should be:
>>> + // meetBest(Reduced, x) >= Reduced
>>> (just a comment, but still...)
>>>
>>> so, could you, please, refresh the patch with my suggestions
>>> implemented?
>>
>> Will do, once we come to agreement above.
>
> we have it now
Ok, I updated the patch. However I also added a few more changes. :-)
Basically, I redefined the ProveResult enum so that the lattice True
> Reduced > False is also true using integer arithmetic. What do
you think?
Naveen
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm][jit] possible ABCD bug
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x1F8 day of Apache Harmony Naveen Neelakantam wrote:
> >> 2) Also in updateMemDistanceWithPredecessors, I added an
> >> optimization. Essentially, we can take advantage of ProveResult
> >> being a lattice (i.e. is monotonic) to prevent some recursive proofs.
> >
> > oh, the optimization is fine, but seems that it would make a
> > suspicious 'Reduced' instead of 'True' sometimes, which still looks
> > like OK for our purposes. It won't give us a big performance gain due
> > to the sparse nature of the inequality graph.. Though, optimizing
> > prematurely makes a lot of fun, so I like it :) I would suggest to
> > move the 'if' statement outside the loop because it is a loop
> > invariant. Elinimanting this 'break' would be a better style.
>
> The if statement is not loop invariant because the value of "res"
> changes each loop iteration. Am I missing something? As for the
> "break", I can definitely rewrite the loop to get rid of it.
Wait a minute, I need to check if my hair became blond. Now "break"
looks fine. Sorry:)
> > One more to say on the patch:
> > + // meetBest(Reduced, x) <= Reduced
> >
> > should be:
> > + // meetBest(Reduced, x) >= Reduced
> > (just a comment, but still...)
> >
> > so, could you, please, refresh the patch with my suggestions
> > implemented?
>
> Will do, once we come to agreement above.
we have it now
> >> Once again, your code is very good. It is also nice that it matches
> >> the algorithm outlined in the ABCD paper wherever possible.
> >
> > heh:) did you notice that "line 9" of the algorithm? (Figure 5 in the
> > paper). I replaced '>' by '<', and only after that it worked
> > (classic_abcd_solver.cpp:645). I suppose, it's a bug in the
> > paper. Could you, please, double check this?
>
> I did not notice it before, but I agree that the bug is in the paper.
I love this game :)
> >> Is there something else I can do to help?
> >
> > Yeah, now it's my step. We would do our best if I publish my
> > HIR->Igraph conversion scratches (they don't work yet).
> >
> > Unfortunately, I am so busy with ClassLoaderTest which fails after
> > some seemingly correct optimizations in 'memopt'.. I'll open the
> > sources in a couple of days. Can you wait so long?
>
> No worries. I am also working on other things, but would like to try
> and move this forward whenever possible.
OK, I'll submit the code this week. Maybe, even tomorrow. (I have some
progress on ClassLoaderTest)
--
Egor Pasko, Intel Managed Runtime Division
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm][jit] possible ABCD bug
Posted by Naveen Neelakantam <ne...@uiuc.edu>.
On Oct 3, 2006, at 12:29 AM, Egor Pasko wrote:
> On the 0x1F7 day of Apache Harmony Naveen Neelakantam wrote:
>> Hello Egor,
>>
>> I finally got a chance to read through your code. It is well
>> designed, and correct (as far as I can tell). I especially like the
>> way that the upper bounds solver works as the lower bounds solver
>> simply by flipping a flag (and both operate on the same inequality
>> graph). Very nice!
>
> Too many good words for me, cannot handle it)) Thnx
:-)
>> 2) Also in updateMemDistanceWithPredecessors, I added an
>> optimization. Essentially, we can take advantage of ProveResult
>> being a lattice (i.e. is monotonic) to prevent some recursive proofs.
>
> oh, the optimization is fine, but seems that it would make a
> suspicious 'Reduced' instead of 'True' sometimes, which still looks
> like OK for our purposes. It won't give us a big performance gain due
> to the sparse nature of the inequality graph.. Though, optimizing
> prematurely makes a lot of fun, so I like it :) I would suggest to
> move the 'if' statement outside the loop because it is a loop
> invariant. Elinimanting this 'break' would be a better style.
The if statement is not loop invariant because the value of "res"
changes each loop iteration. Am I missing something? As for the
"break", I can definitely rewrite the loop to get rid of it.
> One more to say on the patch:
> + // meetBest(Reduced, x) <= Reduced
>
> should be:
> + // meetBest(Reduced, x) >= Reduced
> (just a comment, but still...)
>
> so, could you, please, refresh the patch with my suggestions
> implemented?
Will do, once we come to agreement above.
>> Once again, your code is very good. It is also nice that it matches
>> the algorithm outlined in the ABCD paper wherever possible.
>
> heh:) did you notice that "line 9" of the algorithm? (Figure 5 in the
> paper). I replaced '>' by '<', and only after that it worked
> (classic_abcd_solver.cpp:645). I suppose, it's a bug in the
> paper. Could you, please, double check this?
I did not notice it before, but I agree that the bug is in the paper.
>> Is there something else I can do to help?
>
> Yeah, now it's my step. We would do our best if I publish my
> HIR->Igraph conversion scratches (they don't work yet).
>
> Unfortunately, I am so busy with ClassLoaderTest which fails after
> some seemingly correct optimizations in 'memopt'.. I'll open the
> sources in a couple of days. Can you wait so long?
No worries. I am also working on other things, but would like to try
and move this forward whenever possible.
> What I did:
> * Created a new optimization pass "classic_abcd"
> * moved the Pi insertion logic to a separate Class (and file
> insertpi.cpp) to reuse it in "classic_abcd"
> * to use an Opnd in Inequality Graph like an IOpnd, I made an
> "IOpndProxy : public IOpnd" containing an original operand and
> tweaking here and there to make them have unique ids :)
> * Started creating Inequality graph (not all info reused, some bugs,
> crashes, etc.)
>
> I would be happy if you look at that code, and finish it up to an
> initial version while I am stuck with those critical bugz.
I can certainly take a look and try to finish it up.
> Do you have some other ideas how we can collaborate better at this
> point?
I'm happy, so not really. :-)
Naveen
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm][jit] possible ABCD bug
Posted by Egor Pasko <eg...@gmail.com>.
On the 0x1F7 day of Apache Harmony Naveen Neelakantam wrote:
> Hello Egor,
>
> I finally got a chance to read through your code. It is well
> designed, and correct (as far as I can tell). I especially like the
> way that the upper bounds solver works as the lower bounds solver
> simply by flipping a flag (and both operate on the same inequality
> graph). Very nice!
Too many good words for me, cannot handle it)) Thnx
> I made some changes that you might be interested in, which I've
> uploaded in the form of a patch.
Great! I've been reading it along the morning and waiting for your message :)
> They are (in the order they appear in the patch file):
>
> 1) In updateMemDistanceWithPredecessors, it should not be possible
> for the dest operand to have a usable memoized value. This is simply
> because if it did, updateMemDistanceWithPredecessors would not have
> been called. I therefore replaced some code with an assert.
hm, that's right! We are at the 'dest' for the first time (because
active[dest] was NULL). Original paper's authors have a good sense of
humor...
> 2) Also in updateMemDistanceWithPredecessors, I added an
> optimization. Essentially, we can take advantage of ProveResult
> being a lattice (i.e. is monotonic) to prevent some recursive proofs.
oh, the optimization is fine, but seems that it would make a
suspicious 'Reduced' instead of 'True' sometimes, which still looks
like OK for our purposes. It won't give us a big performance gain due
to the sparse nature of the inequality graph.. Though, optimizing
prematurely makes a lot of fun, so I like it :) I would suggest to
move the 'if' statement outside the loop because it is a loop
invariant. Elinimanting this 'break' would be a better style.
One more to say on the patch:
+ // meetBest(Reduced, x) <= Reduced
should be:
+ // meetBest(Reduced, x) >= Reduced
(just a comment, but still...)
so, could you, please, refresh the patch with my suggestions
implemented?
> 3) I fixed a small error in testDoubleCycleGraph().
Thanks for that!
> 4) Fixed a gcc 4.1.1 syntax error in the header.
Thanks for that too! Most of my time I work on gcc 3.3.3, sorry..
> Once again, your code is very good. It is also nice that it matches
> the algorithm outlined in the ABCD paper wherever possible.
heh:) did you notice that "line 9" of the algorithm? (Figure 5 in the
paper). I replaced '>' by '<', and only after that it worked
(classic_abcd_solver.cpp:645). I suppose, it's a bug in the
paper. Could you, please, double check this?
> Is there something else I can do to help?
Yeah, now it's my step. We would do our best if I publish my
HIR->Igraph conversion scratches (they don't work yet).
Unfortunately, I am so busy with ClassLoaderTest which fails after
some seemingly correct optimizations in 'memopt'.. I'll open the
sources in a couple of days. Can you wait so long?
What I did:
* Created a new optimization pass "classic_abcd"
* moved the Pi insertion logic to a separate Class (and file
insertpi.cpp) to reuse it in "classic_abcd"
* to use an Opnd in Inequality Graph like an IOpnd, I made an
"IOpndProxy : public IOpnd" containing an original operand and
tweaking here and there to make them have unique ids :)
* Started creating Inequality graph (not all info reused, some bugs,
crashes, etc.)
I would be happy if you look at that code, and finish it up to an
initial version while I am stuck with those critical bugz.
Do you have some other ideas how we can collaborate better at this
point?
> Naveen
>
> On Sep 26, 2006, at 3:50 AM, Egor Pasko wrote:
>
> > On the 0x1EF day of Apache Harmony Naveen Neelakantam wrote:
> >
> > Naveen, I am glad to see someone interested in ABCD. Hope for
> > collaboration and a lot of fun with the code :)
> >
> > I attached my solver to HARMONY-1564 (oops, sorry for .tar.gz, I am so
> > used to it:) It is just the implementation of the solver with a number
> > of tests to play with. Though, it depends on Log.h, Stl.h and types.h
> > and is better placed in working_vm/vm/jitrino/src/optimizer/abcd as I
> > expected to place it.
> >
> > To make it real need to create InequalityGraph from HIR, that's what I
> > started to do already. Not finished, unfortunately. I will publish the
> > sketches if you are eager to see them ASAP. I guess, it will take some
> > time for you to play with the solver, though :)
> >
> > Plz, do not hesitate to ask any question on the code. I pretend that
> > it should be a more easy read than the present implementation. So, I
> > would appreciate any comments.
> >
> > It makes sense to make a separate JIRA for our ABCD
> > improvements. That's a TODO.
>
>
> ---------------------------------------------------------------------
> Terms of use : http://incubator.apache.org/harmony/mailing.html
> To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
> For additional commands, e-mail: harmony-dev-help@incubator.apache.org
>
>
--
Egor Pasko, Intel Managed Runtime Division
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org