harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Naveen Neelakantam <neela...@uiuc.edu>
Subject Re: [drlvm][jit] possible ABCD bug
Date Wed, 27 Sep 2006 01:56:15 GMT
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


Mime
View raw message