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 Tue, 26 Sep 2006 08:50:41 GMT
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: harmony-dev-unsubscribe@incubator.apache.org
> > For additional commands, e-mail: harmony-dev-help@incubator.apache.org
> >
> 
> 
> ---------------------------------------------------------------------
> 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
> 
> 

-- 
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