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, 03 Oct 2006 05:29:21 GMT
On the 0x1F7 day of Apache Harmony Naveen Neelakantam wrote:
> Hello Egor,
> 
> I finally got a chance to read through your code.  It is well
> designed, and correct (as far as I can tell).  I especially like the
> way that the upper bounds solver works as the lower bounds solver
> simply by flipping a flag (and both operate on the same inequality
> graph).  Very nice!

Too many good words for me, cannot handle it)) Thnx

> I made some changes that you might be interested in, which I've
> uploaded in the form of a patch. 

Great! I've been reading it along the morning and waiting for your message :)

> They are (in the order they appear in the patch file):
> 
> 1) In updateMemDistanceWithPredecessors, it should not be possible
> for the dest operand to have a usable memoized value.  This is simply
> because if it did, updateMemDistanceWithPredecessors would not have
> been called.  I therefore replaced some code with an assert.

hm, that's right! We are at the 'dest' for the first time (because
active[dest] was NULL). Original paper's authors have a good sense of
humor...

> 2) Also in updateMemDistanceWithPredecessors, I added an
> optimization.  Essentially, we can take advantage of ProveResult
> being a lattice (i.e. is monotonic) to prevent some recursive proofs.

oh, the optimization is fine, but seems that it would make a
suspicious 'Reduced' instead of 'True' sometimes, which still looks
like OK for our purposes. It won't give us a big performance gain due
to the sparse nature of the inequality graph.. Though, optimizing
prematurely makes a lot of fun, so I like it :) I would suggest to
move the 'if' statement outside the loop because it is a loop
invariant. Elinimanting this 'break' would be a better style.

One more to say on the patch:
+            //            meetBest(Reduced, x) <= Reduced  

should be:
+            //            meetBest(Reduced, x) >= Reduced  
(just a comment, but still...)

so, could you, please, refresh the patch with my suggestions
implemented?

> 3) I fixed a small error in testDoubleCycleGraph().

Thanks for that!

> 4) Fixed a gcc 4.1.1 syntax error in the header.

Thanks for that too! Most of my time I work on gcc 3.3.3, sorry..

> Once again, your code is very good.  It is also nice that it matches
> the algorithm outlined in the ABCD paper wherever possible.

heh:) did you notice that "line 9" of the algorithm? (Figure 5 in the
paper). I replaced '>' by '<', and only after that it worked
(classic_abcd_solver.cpp:645). I suppose, it's a bug in the
paper. Could you, please, double check this?

> Is there something else I can do to help?

Yeah, now it's my step. We would do our best if I publish my
HIR->Igraph conversion scratches (they don't work yet).

Unfortunately, I am so busy with ClassLoaderTest which fails after
some seemingly correct optimizations in 'memopt'.. I'll open the
sources in a couple of days. Can you wait so long?

What I did:
* Created a new optimization pass "classic_abcd"
* moved the Pi insertion logic to a separate Class (and file
  insertpi.cpp) to reuse it in "classic_abcd"
* to use an Opnd in Inequality Graph like an IOpnd, I made an
  "IOpndProxy : public IOpnd" containing an original operand and
  tweaking here and there to make them have unique ids :)
* Started creating Inequality graph (not all info reused, some bugs,
  crashes, etc.)

I would be happy if you look at that code, and finish it up to an
initial version while I am stuck with those critical bugz.

Do you have some other ideas how we can collaborate better at this
point?

> Naveen
> 
> On Sep 26, 2006, at 3:50 AM, Egor Pasko wrote:
> 
> > On the 0x1EF day of Apache Harmony Naveen Neelakantam wrote:
> >
> > 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.
> 
> 
> ---------------------------------------------------------------------
> 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