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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
