Re: [drlvm][jit] possible ABCD bug

Naveen Neelakantam Tue, 26 Sep 2006 18:56:50 -0700

Thanks Egor!

.tar.gz is fine with me.  I prefer linux anyway.

I'll take a look at your code and get back to you. I'm excited toget an effective ABCD pass implemented.


Naveen

On Sep 26, 2006, at 1:50 AM, Egor Pasko wrote:

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

It is sad, because this decision is central to the algorithm  and

means that much of the existing ABCD code is not useful to workwith.


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 onIA-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, veryobvious

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 acheck

  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 upsetalmost

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 implementedthe

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

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 doyou

think?

Anyway, I'll publish my results, but, maybe, a bit later andworking.


--
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: harmony-dev-[EMAIL PROTECTED]



---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: [EMAIL PROTECTED]

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



---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]

Re: [drlvm][jit] possible ABCD bug

Reply via email to