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 Mon, 25 Sep 2006 16:19:16 GMT
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


Mime
View raw message