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 usedef 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 HARMONY1564 (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 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
> >
>
>
> 
> 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
>
>

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
