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/09/24 12:45:17 UTC
[drlvm][jit] possible ABCD bug
I've been reading through the ABCD implementation in jitrino, and if
I understand it correctly, I found a bug. I've attached a patch to
fix it. Someone who actually understands the code should verify this.
Also, did anyone ever test this ABCD pass? I ask because I've tried
running it on a bidirectional bubble sort as mentioned in the
original paper. The paper mentions that the pass should be able to
prove all of the bounds checks in the sort method as redundant/
unnecessary. However, when I try running the abcd pass on a
bidirectional bubble sort (attached), none of the bounds checks are
eliminated.
Naveen
Re: [drlvm][jit] possible ABCD bug
Posted by "Geir Magnusson Jr." <ge...@pobox.com>.
thanks. That license seems fine.
geir
On Sep 24, 2006, at 4:08 PM, Naveen Neelakantam wrote:
> I've opened a JIRA issue that contains a patch that points out the
> possible bug:
>
> patch for possible ABCD bug
> ---------------------------
>
> Key: HARMONY-1564
> URL: http://issues.apache.org/jira/browse/
> HARMONY-1564
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Reporter: Naveen Neelakantam
> Attachments: abcd.patch, BidirectionalBubbleSort.java
>
> On Sep 24, 2006, at 12:34 PM, Geir Magnusson Jr. wrote:
>
>>
>> On Sep 24, 2006, at 2:05 PM, Naveen Neelakantam wrote:
>>
>>> Hmm. I have seen the code generator of a VM that isn't open
>>> source, but that was over a year ago. I don't really understand
>>> the implications of that, other than I am not able to become an
>>> "Authorized Harmony Contributor" without consent.
>>
>> yes, that can be a problem. We can discuss here or in private -
>> whatever you'd prefer.
>
> I'll email you to discuss it further.
>
>>>
>>> In this case, I have never seen another implementation of ABCD
>>> and my only prior exposure to the algorithm is Ras Bodik's PLDI
>>> paper. Can I still point out bugs and discuss the implementation?
>>
>> Yes.
>>
>>>
>>> Thanks,
>>> Naveen
>>>
>>> On Sep 24, 2006, at 6:16 AM, Geir Magnusson Jr. wrote:
>>>
>>>> Hi,
>>>>
>>>> Welcome to Harmony, and thanks for looking into this.
>>>>
>>>> Two things :
>>>>
>>>> 1) The patch didn't come through - we strip off certain types of
>>>> attachments. The best thing to do would be to enter a JIRA in
>>>> our bug-tracking system :
>>>>
>>>> https://issues.apache.org/jira/browse/HARMONY
>>>>
>>>> 2) We have a process through which we ensure that our
>>>> contributors haven't been exposed to other implementations that
>>>> aren't available in open source, in an attempt to lower any risk
>>>> of accidental copyright infringment or worse. The process is
>>>> detailed here :
>>>>
>>>> http://incubator.apache.org/harmony/contribution_policy.html
>>>>
>>>> The key part of it is that you complete an Authorized
>>>> Contributor Questionairre :
>>>>
>>>> http://incubator.apache.org/harmony/auth_cont_quest.html
>>>>
>>>> The ideal solution is to fill it out, turn it into a PDF, and
>>>> then send that to me (geir at pobox dot com) or, less ideally :)
>>>> is fax to +1 203 665 6400.
>>>>
>>>> Thanks again, welcome again,and sorry for the paperwork.
>>>>
>>>> geir
>>>>
>>>> On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
>>>>
>>>>> I've been reading through the ABCD implementation in jitrino,
>>>>> and if I understand it correctly, I found a bug. I've attached
>>>>> a patch to fix it. Someone who actually understands the code
>>>>> should verify this.
>>>>>
>>>>> Also, did anyone ever test this ABCD pass? I ask because I've
>>>>> tried running it on a bidirectional bubble sort as mentioned in
>>>>> the original paper. The paper mentions that the pass should be
>>>>> able to prove all of the bounds checks in the sort method as
>>>>> redundant/unnecessary. However, when I try running the abcd
>>>>> pass on a bidirectional bubble sort (attached), none of the
>>>>> bounds checks are eliminated.
>>>>>
>>>>> 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
>>>>
>>>>
>>>> -------------------------------------------------------------------
>>>> --
>>>> 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
>>>>
>>>
>>>
>>> --------------------------------------------------------------------
>>> -
>>> 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
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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>.
I've opened a JIRA issue that contains a patch that points out the
possible bug:
patch for possible ABCD bug
---------------------------
Key: HARMONY-1564
URL: http://issues.apache.org/jira/browse/HARMONY-1564
Project: Harmony
Issue Type: Bug
Components: DRLVM
Reporter: Naveen Neelakantam
Attachments: abcd.patch, BidirectionalBubbleSort.java
On Sep 24, 2006, at 12:34 PM, Geir Magnusson Jr. wrote:
>
> On Sep 24, 2006, at 2:05 PM, Naveen Neelakantam wrote:
>
>> Hmm. I have seen the code generator of a VM that isn't open
>> source, but that was over a year ago. I don't really understand
>> the implications of that, other than I am not able to become an
>> "Authorized Harmony Contributor" without consent.
>
> yes, that can be a problem. We can discuss here or in private -
> whatever you'd prefer.
I'll email you to discuss it further.
>>
>> In this case, I have never seen another implementation of ABCD and
>> my only prior exposure to the algorithm is Ras Bodik's PLDI
>> paper. Can I still point out bugs and discuss the implementation?
>
> Yes.
>
>>
>> Thanks,
>> Naveen
>>
>> On Sep 24, 2006, at 6:16 AM, Geir Magnusson Jr. wrote:
>>
>>> Hi,
>>>
>>> Welcome to Harmony, and thanks for looking into this.
>>>
>>> Two things :
>>>
>>> 1) The patch didn't come through - we strip off certain types of
>>> attachments. The best thing to do would be to enter a JIRA in
>>> our bug-tracking system :
>>>
>>> https://issues.apache.org/jira/browse/HARMONY
>>>
>>> 2) We have a process through which we ensure that our
>>> contributors haven't been exposed to other implementations that
>>> aren't available in open source, in an attempt to lower any risk
>>> of accidental copyright infringment or worse. The process is
>>> detailed here :
>>>
>>> http://incubator.apache.org/harmony/contribution_policy.html
>>>
>>> The key part of it is that you complete an Authorized Contributor
>>> Questionairre :
>>>
>>> http://incubator.apache.org/harmony/auth_cont_quest.html
>>>
>>> The ideal solution is to fill it out, turn it into a PDF, and
>>> then send that to me (geir at pobox dot com) or, less ideally :)
>>> is fax to +1 203 665 6400.
>>>
>>> Thanks again, welcome again,and sorry for the paperwork.
>>>
>>> geir
>>>
>>> On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
>>>
>>>> I've been reading through the ABCD implementation in jitrino,
>>>> and if I understand it correctly, I found a bug. I've attached
>>>> a patch to fix it. Someone who actually understands the code
>>>> should verify this.
>>>>
>>>> Also, did anyone ever test this ABCD pass? I ask because I've
>>>> tried running it on a bidirectional bubble sort as mentioned in
>>>> the original paper. The paper mentions that the pass should be
>>>> able to prove all of the bounds checks in the sort method as
>>>> redundant/unnecessary. However, when I try running the abcd
>>>> pass on a bidirectional bubble sort (attached), none of the
>>>> bounds checks are eliminated.
>>>>
>>>> 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
>>>
>>>
>>> --------------------------------------------------------------------
>>> -
>>> 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
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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 "Geir Magnusson Jr." <ge...@pobox.com>.
On Sep 24, 2006, at 2:05 PM, Naveen Neelakantam wrote:
> Hmm. I have seen the code generator of a VM that isn't open
> source, but that was over a year ago. I don't really understand
> the implications of that, other than I am not able to become an
> "Authorized Harmony Contributor" without consent.
yes, that can be a problem. We can discuss here or in private -
whatever you'd prefer.
>
> In this case, I have never seen another implementation of ABCD and
> my only prior exposure to the algorithm is Ras Bodik's PLDI paper.
> Can I still point out bugs and discuss the implementation?
Yes.
>
> Thanks,
> Naveen
>
> On Sep 24, 2006, at 6:16 AM, Geir Magnusson Jr. wrote:
>
>> Hi,
>>
>> Welcome to Harmony, and thanks for looking into this.
>>
>> Two things :
>>
>> 1) The patch didn't come through - we strip off certain types of
>> attachments. The best thing to do would be to enter a JIRA in our
>> bug-tracking system :
>>
>> https://issues.apache.org/jira/browse/HARMONY
>>
>> 2) We have a process through which we ensure that our contributors
>> haven't been exposed to other implementations that aren't
>> available in open source, in an attempt to lower any risk of
>> accidental copyright infringment or worse. The process is
>> detailed here :
>>
>> http://incubator.apache.org/harmony/contribution_policy.html
>>
>> The key part of it is that you complete an Authorized Contributor
>> Questionairre :
>>
>> http://incubator.apache.org/harmony/auth_cont_quest.html
>>
>> The ideal solution is to fill it out, turn it into a PDF, and then
>> send that to me (geir at pobox dot com) or, less ideally :) is fax
>> to +1 203 665 6400.
>>
>> Thanks again, welcome again,and sorry for the paperwork.
>>
>> geir
>>
>> On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
>>
>>> I've been reading through the ABCD implementation in jitrino, and
>>> if I understand it correctly, I found a bug. I've attached a
>>> patch to fix it. Someone who actually understands the code
>>> should verify this.
>>>
>>> Also, did anyone ever test this ABCD pass? I ask because I've
>>> tried running it on a bidirectional bubble sort as mentioned in
>>> the original paper. The paper mentions that the pass should be
>>> able to prove all of the bounds checks in the sort method as
>>> redundant/unnecessary. However, when I try running the abcd pass
>>> on a bidirectional bubble sort (attached), none of the bounds
>>> checks are eliminated.
>>>
>>> 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
>>
>>
>> ---------------------------------------------------------------------
>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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>.
Hmm. I have seen the code generator of a VM that isn't open source,
but that was over a year ago. I don't really understand the
implications of that, other than I am not able to become an
"Authorized Harmony Contributor" without consent.
In this case, I have never seen another implementation of ABCD and my
only prior exposure to the algorithm is Ras Bodik's PLDI paper. Can
I still point out bugs and discuss the implementation?
Thanks,
Naveen
On Sep 24, 2006, at 6:16 AM, Geir Magnusson Jr. wrote:
> Hi,
>
> Welcome to Harmony, and thanks for looking into this.
>
> Two things :
>
> 1) The patch didn't come through - we strip off certain types of
> attachments. The best thing to do would be to enter a JIRA in our
> bug-tracking system :
>
> https://issues.apache.org/jira/browse/HARMONY
>
> 2) We have a process through which we ensure that our contributors
> haven't been exposed to other implementations that aren't available
> in open source, in an attempt to lower any risk of accidental
> copyright infringment or worse. The process is detailed here :
>
> http://incubator.apache.org/harmony/contribution_policy.html
>
> The key part of it is that you complete an Authorized Contributor
> Questionairre :
>
> http://incubator.apache.org/harmony/auth_cont_quest.html
>
> The ideal solution is to fill it out, turn it into a PDF, and then
> send that to me (geir at pobox dot com) or, less ideally :) is fax
> to +1 203 665 6400.
>
> Thanks again, welcome again,and sorry for the paperwork.
>
> geir
>
> On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
>
>> I've been reading through the ABCD implementation in jitrino, and
>> if I understand it correctly, I found a bug. I've attached a
>> patch to fix it. Someone who actually understands the code should
>> verify this.
>>
>> Also, did anyone ever test this ABCD pass? I ask because I've
>> tried running it on a bidirectional bubble sort as mentioned in
>> the original paper. The paper mentions that the pass should be
>> able to prove all of the bounds checks in the sort method as
>> redundant/unnecessary. However, when I try running the abcd pass
>> on a bidirectional bubble sort (attached), none of the bounds
>> checks are eliminated.
>>
>> 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
>
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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 "Geir Magnusson Jr." <ge...@pobox.com>.
On Sep 24, 2006, at 2:11 PM, Naveen Neelakantam wrote:
> Oh, and the bidirectional bubble sort program I mentioned was
> pieced together from code I found on the web. It is tagged with a
> Sun license (code apparently written by James Gosling). Can I
> submit it with the original license attached, even though I
> modified it? The license does say I am free to modify and
> distribute the code.
You can submit it, but we'll probably not do anything with it - it
will depend on the license. Worst case, you can just provide a link
to that code, and a patch, so that people who wish to test can use that.
geir
>
> Naveen
>
> On Sep 24, 2006, at 6:16 AM, Geir Magnusson Jr. wrote:
>
>> Hi,
>>
>> Welcome to Harmony, and thanks for looking into this.
>>
>> Two things :
>>
>> 1) The patch didn't come through - we strip off certain types of
>> attachments. The best thing to do would be to enter a JIRA in our
>> bug-tracking system :
>>
>> https://issues.apache.org/jira/browse/HARMONY
>>
>> 2) We have a process through which we ensure that our contributors
>> haven't been exposed to other implementations that aren't
>> available in open source, in an attempt to lower any risk of
>> accidental copyright infringment or worse. The process is
>> detailed here :
>>
>> http://incubator.apache.org/harmony/contribution_policy.html
>>
>> The key part of it is that you complete an Authorized Contributor
>> Questionairre :
>>
>> http://incubator.apache.org/harmony/auth_cont_quest.html
>>
>> The ideal solution is to fill it out, turn it into a PDF, and then
>> send that to me (geir at pobox dot com) or, less ideally :) is fax
>> to +1 203 665 6400.
>>
>> Thanks again, welcome again,and sorry for the paperwork.
>>
>> geir
>>
>> On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
>>
>>> I've been reading through the ABCD implementation in jitrino, and
>>> if I understand it correctly, I found a bug. I've attached a
>>> patch to fix it. Someone who actually understands the code
>>> should verify this.
>>>
>>> Also, did anyone ever test this ABCD pass? I ask because I've
>>> tried running it on a bidirectional bubble sort as mentioned in
>>> the original paper. The paper mentions that the pass should be
>>> able to prove all of the bounds checks in the sort method as
>>> redundant/unnecessary. However, when I try running the abcd pass
>>> on a bidirectional bubble sort (attached), none of the bounds
>>> checks are eliminated.
>>>
>>> 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
>>
>>
>> ---------------------------------------------------------------------
>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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>.
Oh, and the bidirectional bubble sort program I mentioned was pieced
together from code I found on the web. It is tagged with a Sun
license (code apparently written by James Gosling). Can I submit it
with the original license attached, even though I modified it? The
license does say I am free to modify and distribute the code.
Naveen
On Sep 24, 2006, at 6:16 AM, Geir Magnusson Jr. wrote:
> Hi,
>
> Welcome to Harmony, and thanks for looking into this.
>
> Two things :
>
> 1) The patch didn't come through - we strip off certain types of
> attachments. The best thing to do would be to enter a JIRA in our
> bug-tracking system :
>
> https://issues.apache.org/jira/browse/HARMONY
>
> 2) We have a process through which we ensure that our contributors
> haven't been exposed to other implementations that aren't available
> in open source, in an attempt to lower any risk of accidental
> copyright infringment or worse. The process is detailed here :
>
> http://incubator.apache.org/harmony/contribution_policy.html
>
> The key part of it is that you complete an Authorized Contributor
> Questionairre :
>
> http://incubator.apache.org/harmony/auth_cont_quest.html
>
> The ideal solution is to fill it out, turn it into a PDF, and then
> send that to me (geir at pobox dot com) or, less ideally :) is fax
> to +1 203 665 6400.
>
> Thanks again, welcome again,and sorry for the paperwork.
>
> geir
>
> On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
>
>> I've been reading through the ABCD implementation in jitrino, and
>> if I understand it correctly, I found a bug. I've attached a
>> patch to fix it. Someone who actually understands the code should
>> verify this.
>>
>> Also, did anyone ever test this ABCD pass? I ask because I've
>> tried running it on a bidirectional bubble sort as mentioned in
>> the original paper. The paper mentions that the pass should be
>> able to prove all of the bounds checks in the sort method as
>> redundant/unnecessary. However, when I try running the abcd pass
>> on a bidirectional bubble sort (attached), none of the bounds
>> checks are eliminated.
>>
>> 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
>
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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 "Geir Magnusson Jr." <ge...@pobox.com>.
Hi,
Welcome to Harmony, and thanks for looking into this.
Two things :
1) The patch didn't come through - we strip off certain types of
attachments. The best thing to do would be to enter a JIRA in our
bug-tracking system :
https://issues.apache.org/jira/browse/HARMONY
2) We have a process through which we ensure that our contributors
haven't been exposed to other implementations that aren't available
in open source, in an attempt to lower any risk of accidental
copyright infringment or worse. The process is detailed here :
http://incubator.apache.org/harmony/contribution_policy.html
The key part of it is that you complete an Authorized Contributor
Questionairre :
http://incubator.apache.org/harmony/auth_cont_quest.html
The ideal solution is to fill it out, turn it into a PDF, and then
send that to me (geir at pobox dot com) or, less ideally :) is fax to
+1 203 665 6400.
Thanks again, welcome again,and sorry for the paperwork.
geir
On Sep 24, 2006, at 6:45 AM, Naveen Neelakantam wrote:
> I've been reading through the ABCD implementation in jitrino, and
> if I understand it correctly, I found a bug. I've attached a patch
> to fix it. Someone who actually understands the code should verify
> this.
>
> Also, did anyone ever test this ABCD pass? I ask because I've
> tried running it on a bidirectional bubble sort as mentioned in the
> original paper. The paper mentions that the pass should be able to
> prove all of the bounds checks in the sort method as redundant/
> unnecessary. However, when I try running the abcd pass on a
> bidirectional bubble sort (attached), none of the bounds checks are
> eliminated.
>
> 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
---------------------------------------------------------------------
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
Re: [drlvm][jit] possible ABCD bug
Posted by Naveen Neelakantam <ne...@uiuc.edu>.
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 Naveen Neelakantam <ne...@uiuc.edu>.
Thanks Egor!
.tar.gz is fine with me. I prefer linux anyway.
I'll take a look at your code and get back to you. I'm excited to
get an effective ABCD pass implemented.
Naveen
On Sep 26, 2006, at 1:50 AM, Egor Pasko wrote:
> On the 0x1EF day of Apache Harmony Naveen Neelakantam wrote:
>> Hello Egor,
>>
>> I'm glad to hear the bug is real. It is a sign that I have learned
>> how the ABCD code works. As you pointed out, this was no easy feat!
>> :-)
>>
>> I wanted to do exactly what you seem to have already started. The
>> fact that the existing ABCD pass does not build an inequality graph
>> was very surprising to me. The pass tries to use SSA use-def chains
>> as a substitute, which they certainly are not. The reason is subtle,
>> but it has very severe implications on the effectiveness of the
>> pass.
>> It is sad, because this decision is central to the algorithm and
>> means that much of the existing ABCD code is not useful to work
>> with.
>>
>> I would definitely like to improve jitrino's ABCD, and would be happy
>> to help you in your efforts.
>
> 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.
>
>> Thanks,
>> Naveen
>>
>> On Sep 25, 2006, at 2:11 AM, Egor Pasko wrote:
>>
>>> On the 0x1EE day of Apache Harmony Naveen Neelakantam wrote:
>>>> I've been reading through the ABCD implementation in jitrino,
>>>> and if
>>>> I understand it correctly, I found a bug. I've attached a patch to
>>>> fix it. Someone who actually understands the code should verify
>>>> this.
>>>
>>> Naveen, you found a secret :) Recently, I spent some time
>>> understanding Jitrino's ABCD code too. Now it seems pretty clear,
>>> you
>>> pinpointed a bug. I did not try the patch on a strong benchmark such
>>> as DaCapo, and cannot estimate how much it can give in terms of
>>> performance. (Although, it is both a performance and correctness
>>> related fix)
>>>
>>> As you pointed out recently, checking both bounds assumes one
>>> comparison in CG. So, we won't get any performance benefit on
>>> IA-32 if
>>> we remove only one (lower or upper) bound of a 'chkbounds'.
>>>
>>>> Also, did anyone ever test this ABCD pass?
>>>
>>> That's a long story.
>>>
>>> And here is the secret: Jitrino ABCD removes *only* lower bounds
>>> checks. Thus, it is useless currently. Well, this is not 100%
>>> true :)
>>> Sometimes, I saw it removing upper checks, but, probably, very
>>> obvious
>>> checks. I should have looked into the problem more thoroughly.
>>>
>>> This is a very sad story, so I decided to look what is happening.
>>> The
>>> algorithm is *not* easy to read, but what I can say for sure:
>>> * it is not the algorithm as in the original paper
>>> * it's algorithm applies some more advanced techniques
>>> (i.e. analysis of bounds of the kind A*x+B, where A and B are
>>> constants, x is a variable) and lacks them
>>> * "inequality graph" is not built, thus uncovering some extra
>>> limitations
>>> * the algorithm assumes all constants to be zero, when proving a
>>> check
>>> to eliminate. So, I cannot find any evidence for the algorithm to
>>> remove an upper check :(
>>>
>>> I tried the original ABCD example from the paper. And was upset
>>> almost
>>> like you :) I tried to trigger various switches, but they gave no
>>> clue, except a lot of assertions out of the blue.
>>>
>>>> I ask because I've tried running it on a bidirectional bubble sort
>>>> as mentioned in the original paper. The paper mentions that the
>>>> pass should be able to prove all of the bounds checks in the sort
>>>> method as redundant/ unnecessary. However, when I try running the
>>>> abcd pass on a bidirectional bubble sort (attached), none of the
>>>> bounds checks are eliminated.
>>>
>>> well, some actually are:
>>>
>>> bash$ grep "We can eliminate " naveen.sort.log
>>> We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -)
>>> g25:tau
>>> !!! We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -)
>>> g25:tau
>>> We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -) g36:tau
>>> !!! We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -)
>>> g36:tau
>>> We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -) g45:tau
>>> !!! We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -)
>>> g45:tau
>>> We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -)
>>> g55:tau
>>> !!! We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -)
>>> g55:tau
>>> We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -)
>>> g92:tau
>>> !!! We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -)
>>> g92:tau
>>> We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32 -)
>>> g103:tau
>>> !!! We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32
>>> -) g103:tau
>>> We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -)
>>> g199:tau
>>> !!! We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -)
>>> g199:tau
>>> We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -)
>>> g185:tau
>>> !!! We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -)
>>> g185:tau
>>>
>>> but, you see, only lower bounds!
>>>
>>> (BTW, I applied your fix, it had no influence on your specific test)
>>>
>>> ...The code was so buggy and not easy to read, so I decided to
>>> implement the original algorithm by myself :) Well, I implemented
>>> the
>>> algorithm on a given inequality graph. Tested it a bit, and became
>>> satisfied on how it works. Now I am working on the
>>> IR-to-InequalityGraph transformer. And almost implemented it. At
>>> this
>>> point there is not a lot to do there to make the code working and
>>> eliminating.
>>>
>>> But, hey, you are the first to talk about ABCD on this list! I am so
>>> glad, someone found it too. If you are interested in improving
>>> Jitrino's ABCD, I can publish my early code sketches in JIRA, so we
>>> could improve the code together ASAP. I would be glad to. What do
>>> you
>>> think?
>>>
>>> Anyway, I'll publish my results, but, maybe, a bit later and
>>> working.
>>>
>>> --
>>> 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
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>
---------------------------------------------------------------------
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 0x1EF day of Apache Harmony Naveen Neelakantam wrote:
> Hello Egor,
>
> I'm glad to hear the bug is real. It is a sign that I have learned
> how the ABCD code works. As you pointed out, this was no easy feat!
> :-)
>
> I wanted to do exactly what you seem to have already started. The
> fact that the existing ABCD pass does not build an inequality graph
> was very surprising to me. The pass tries to use SSA use-def chains
> as a substitute, which they certainly are not. The reason is subtle,
> but it has very severe implications on the effectiveness of the pass.
> It is sad, because this decision is central to the algorithm and
> means that much of the existing ABCD code is not useful to work with.
>
> I would definitely like to improve jitrino's ABCD, and would be happy
> to help you in your efforts.
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.
> Thanks,
> Naveen
>
> On Sep 25, 2006, at 2:11 AM, Egor Pasko wrote:
>
> > On the 0x1EE day of Apache Harmony Naveen Neelakantam wrote:
> >> I've been reading through the ABCD implementation in jitrino, and if
> >> I understand it correctly, I found a bug. I've attached a patch to
> >> fix it. Someone who actually understands the code should verify
> >> this.
> >
> > Naveen, you found a secret :) Recently, I spent some time
> > understanding Jitrino's ABCD code too. Now it seems pretty clear, you
> > pinpointed a bug. I did not try the patch on a strong benchmark such
> > as DaCapo, and cannot estimate how much it can give in terms of
> > performance. (Although, it is both a performance and correctness
> > related fix)
> >
> > As you pointed out recently, checking both bounds assumes one
> > comparison in CG. So, we won't get any performance benefit on IA-32 if
> > we remove only one (lower or upper) bound of a 'chkbounds'.
> >
> >> Also, did anyone ever test this ABCD pass?
> >
> > That's a long story.
> >
> > And here is the secret: Jitrino ABCD removes *only* lower bounds
> > checks. Thus, it is useless currently. Well, this is not 100% true :)
> > Sometimes, I saw it removing upper checks, but, probably, very obvious
> > checks. I should have looked into the problem more thoroughly.
> >
> > This is a very sad story, so I decided to look what is happening. The
> > algorithm is *not* easy to read, but what I can say for sure:
> > * it is not the algorithm as in the original paper
> > * it's algorithm applies some more advanced techniques
> > (i.e. analysis of bounds of the kind A*x+B, where A and B are
> > constants, x is a variable) and lacks them
> > * "inequality graph" is not built, thus uncovering some extra
> > limitations
> > * the algorithm assumes all constants to be zero, when proving a check
> > to eliminate. So, I cannot find any evidence for the algorithm to
> > remove an upper check :(
> >
> > I tried the original ABCD example from the paper. And was upset almost
> > like you :) I tried to trigger various switches, but they gave no
> > clue, except a lot of assertions out of the blue.
> >
> >> I ask because I've tried running it on a bidirectional bubble sort
> >> as mentioned in the original paper. The paper mentions that the
> >> pass should be able to prove all of the bounds checks in the sort
> >> method as redundant/ unnecessary. However, when I try running the
> >> abcd pass on a bidirectional bubble sort (attached), none of the
> >> bounds checks are eliminated.
> >
> > well, some actually are:
> >
> > bash$ grep "We can eliminate " naveen.sort.log
> > We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -)
> > g25:tau
> > !!! We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -)
> > g25:tau
> > We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -) g36:tau
> > !!! We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -)
> > g36:tau
> > We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -) g45:tau
> > !!! We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -)
> > g45:tau
> > We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -) g55:tau
> > !!! We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -)
> > g55:tau
> > We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -)
> > g92:tau
> > !!! We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -)
> > g92:tau
> > We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32 -)
> > g103:tau
> > !!! We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32
> > -) g103:tau
> > We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -) g199:tau
> > !!! We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -)
> > g199:tau
> > We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -)
> > g185:tau
> > !!! We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -)
> > g185:tau
> >
> > but, you see, only lower bounds!
> >
> > (BTW, I applied your fix, it had no influence on your specific test)
> >
> > ...The code was so buggy and not easy to read, so I decided to
> > implement the original algorithm by myself :) Well, I implemented the
> > algorithm on a given inequality graph. Tested it a bit, and became
> > satisfied on how it works. Now I am working on the
> > IR-to-InequalityGraph transformer. And almost implemented it. At this
> > point there is not a lot to do there to make the code working and
> > eliminating.
> >
> > But, hey, you are the first to talk about ABCD on this list! I am so
> > glad, someone found it too. If you are interested in improving
> > Jitrino's ABCD, I can publish my early code sketches in JIRA, so we
> > could improve the code together ASAP. I would be glad to. What do you
> > think?
> >
> > Anyway, I'll publish my results, but, maybe, a bit later and working.
> >
> > --
> > 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
> >
>
>
> ---------------------------------------------------------------------
> 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
Re: [drlvm][jit] possible ABCD bug
Posted by Naveen Neelakantam <ne...@uiuc.edu>.
Hello Egor,
I'm glad to hear the bug is real. It is a sign that I have learned
how the ABCD code works. As you pointed out, this was no easy
feat! :-)
I wanted to do exactly what you seem to have already started. The
fact that the existing ABCD pass does not build an inequality graph
was very surprising to me. The pass tries to use SSA use-def chains
as a substitute, which they certainly are not. The reason is subtle,
but it has very severe implications on the effectiveness of the
pass. It is sad, because this decision is central to the algorithm
and means that much of the existing ABCD code is not useful to work
with.
I would definitely like to improve jitrino's ABCD, and would be happy
to help you in your efforts.
Thanks,
Naveen
On Sep 25, 2006, at 2:11 AM, Egor Pasko wrote:
> On the 0x1EE day of Apache Harmony Naveen Neelakantam wrote:
>> I've been reading through the ABCD implementation in jitrino, and if
>> I understand it correctly, I found a bug. I've attached a patch to
>> fix it. Someone who actually understands the code should verify
>> this.
>
> Naveen, you found a secret :) Recently, I spent some time
> understanding Jitrino's ABCD code too. Now it seems pretty clear, you
> pinpointed a bug. I did not try the patch on a strong benchmark such
> as DaCapo, and cannot estimate how much it can give in terms of
> performance. (Although, it is both a performance and correctness
> related fix)
>
> As you pointed out recently, checking both bounds assumes one
> comparison in CG. So, we won't get any performance benefit on IA-32 if
> we remove only one (lower or upper) bound of a 'chkbounds'.
>
>> Also, did anyone ever test this ABCD pass?
>
> That's a long story.
>
> And here is the secret: Jitrino ABCD removes *only* lower bounds
> checks. Thus, it is useless currently. Well, this is not 100% true :)
> Sometimes, I saw it removing upper checks, but, probably, very obvious
> checks. I should have looked into the problem more thoroughly.
>
> This is a very sad story, so I decided to look what is happening. The
> algorithm is *not* easy to read, but what I can say for sure:
> * it is not the algorithm as in the original paper
> * it's algorithm applies some more advanced techniques
> (i.e. analysis of bounds of the kind A*x+B, where A and B are
> constants, x is a variable) and lacks them
> * "inequality graph" is not built, thus uncovering some extra
> limitations
> * the algorithm assumes all constants to be zero, when proving a check
> to eliminate. So, I cannot find any evidence for the algorithm to
> remove an upper check :(
>
> I tried the original ABCD example from the paper. And was upset almost
> like you :) I tried to trigger various switches, but they gave no
> clue, except a lot of assertions out of the blue.
>
>> I ask because I've tried running it on a bidirectional bubble sort
>> as mentioned in the original paper. The paper mentions that the
>> pass should be able to prove all of the bounds checks in the sort
>> method as redundant/ unnecessary. However, when I try running the
>> abcd pass on a bidirectional bubble sort (attached), none of the
>> bounds checks are eliminated.
>
> well, some actually are:
>
> bash$ grep "We can eliminate " naveen.sort.log
> We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -)
> g25:tau
> !!! We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -)
> g25:tau
> We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -) g36:tau
> !!! We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -)
> g36:tau
> We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -) g45:tau
> !!! We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -)
> g45:tau
> We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -) g55:tau
> !!! We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -)
> g55:tau
> We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -)
> g92:tau
> !!! We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -)
> g92:tau
> We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32 -)
> g103:tau
> !!! We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32
> -) g103:tau
> We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -) g199:tau
> !!! We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -)
> g199:tau
> We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -)
> g185:tau
> !!! We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -)
> g185:tau
>
> but, you see, only lower bounds!
>
> (BTW, I applied your fix, it had no influence on your specific test)
>
> ...The code was so buggy and not easy to read, so I decided to
> implement the original algorithm by myself :) Well, I implemented the
> algorithm on a given inequality graph. Tested it a bit, and became
> satisfied on how it works. Now I am working on the
> IR-to-InequalityGraph transformer. And almost implemented it. At this
> point there is not a lot to do there to make the code working and
> eliminating.
>
> But, hey, you are the first to talk about ABCD on this list! I am so
> glad, someone found it too. If you are interested in improving
> Jitrino's ABCD, I can publish my early code sketches in JIRA, so we
> could improve the code together ASAP. I would be glad to. What do you
> think?
>
> Anyway, I'll publish my results, but, maybe, a bit later and working.
>
> --
> 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
>
---------------------------------------------------------------------
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 0x1EE day of Apache Harmony Naveen Neelakantam wrote:
> I've been reading through the ABCD implementation in jitrino, and if
> I understand it correctly, I found a bug. I've attached a patch to
> fix it. Someone who actually understands the code should verify this.
Naveen, you found a secret :) Recently, I spent some time
understanding Jitrino's ABCD code too. Now it seems pretty clear, you
pinpointed a bug. I did not try the patch on a strong benchmark such
as DaCapo, and cannot estimate how much it can give in terms of
performance. (Although, it is both a performance and correctness
related fix)
As you pointed out recently, checking both bounds assumes one
comparison in CG. So, we won't get any performance benefit on IA-32 if
we remove only one (lower or upper) bound of a 'chkbounds'.
> Also, did anyone ever test this ABCD pass?
That's a long story.
And here is the secret: Jitrino ABCD removes *only* lower bounds
checks. Thus, it is useless currently. Well, this is not 100% true :)
Sometimes, I saw it removing upper checks, but, probably, very obvious
checks. I should have looked into the problem more thoroughly.
This is a very sad story, so I decided to look what is happening. The
algorithm is *not* easy to read, but what I can say for sure:
* it is not the algorithm as in the original paper
* it's algorithm applies some more advanced techniques
(i.e. analysis of bounds of the kind A*x+B, where A and B are
constants, x is a variable) and lacks them
* "inequality graph" is not built, thus uncovering some extra
limitations
* the algorithm assumes all constants to be zero, when proving a check
to eliminate. So, I cannot find any evidence for the algorithm to
remove an upper check :(
I tried the original ABCD example from the paper. And was upset almost
like you :) I tried to trigger various switches, but they gave no
clue, except a lot of assertions out of the blue.
> I ask because I've tried running it on a bidirectional bubble sort
> as mentioned in the original paper. The paper mentions that the
> pass should be able to prove all of the bounds checks in the sort
> method as redundant/ unnecessary. However, when I try running the
> abcd pass on a bidirectional bubble sort (attached), none of the
> bounds checks are eliminated.
well, some actually are:
bash$ grep "We can eliminate " naveen.sort.log
We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -) g25:tau
!!! We can eliminate LB check of I43:chkbounds g195.16 .lt. g8.8 -) g25:tau
We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -) g36:tau
!!! We can eliminate LB check of I54:chkbounds g32 .lt. g8.18 -) g36:tau
We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -) g45:tau
!!! We can eliminate LB check of I64:chkbounds g180 .lt. g8.8 -) g45:tau
We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -) g55:tau
!!! We can eliminate LB check of I74:chkbounds g194 .lt. g8.12 -) g55:tau
We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -) g92:tau
!!! We can eliminate LB check of I118:chkbounds g82.27 .lt. g8.1 -) g92:tau
We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32 -) g103:tau
!!! We can eliminate LB check of I129:chkbounds g80.31 .lt. g8.32 -) g103:tau
We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -) g199:tau
!!! We can eliminate LB check of I314:chkbounds g196 .lt. g8.5 -) g199:tau
We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -) g185:tau
!!! We can eliminate LB check of I294:chkbounds g218.3 .lt. g8.1 -) g185:tau
but, you see, only lower bounds!
(BTW, I applied your fix, it had no influence on your specific test)
...The code was so buggy and not easy to read, so I decided to
implement the original algorithm by myself :) Well, I implemented the
algorithm on a given inequality graph. Tested it a bit, and became
satisfied on how it works. Now I am working on the
IR-to-InequalityGraph transformer. And almost implemented it. At this
point there is not a lot to do there to make the code working and
eliminating.
But, hey, you are the first to talk about ABCD on this list! I am so
glad, someone found it too. If you are interested in improving
Jitrino's ABCD, I can publish my early code sketches in JIRA, so we
could improve the code together ASAP. I would be glad to. What do you
think?
Anyway, I'll publish my results, but, maybe, a bit later and working.
--
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