harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Egor Pasko <egor.pa...@gmail.com>
Subject Re: [drlvm][jit] possible ABCD bug
Date Mon, 25 Sep 2006 09:11:58 GMT
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


Mime
View raw message