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 IA32 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
IRtoInequalityGraph 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, email: harmonydevunsubscribe@incubator.apache.org
For additional commands, email: harmonydevhelp@incubator.apache.org
