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: [EMAIL PROTECTED] > > For additional commands, e-mail: [EMAIL PROTECTED] > > > > > --------------------------------------------------------------------- > Terms of use : http://incubator.apache.org/harmony/mailing.html > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > -- 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]
