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] abcd and devirtualizer patches was: [OT] Harmony used in accepted research paper
Date Wed, 25 Apr 2007 20:05:19 GMT
On the 0x2C3 day of Apache Harmony Pavel Ozhdikhin wrote:
> On 4/21/07, Naveen Neelakantam <neelakan@uiuc.edu> wrote:
> >
> >
> > On Apr 20, 2007, at 4:45 AM, Egor Pasko wrote:
> >
> > > On the 0x2BE day of Apache Harmony Naveen Neelakantam wrote:
> > >> On Apr 20, 2007, at 1:42 AM, Egor Pasko wrote:
> > >>
> >
> > <snip>
> >
> > >>> One major question for now: Why do we need two separate inequality
> > >>> graphs, for upper and lower bound problems? You name the lower bound
> > >>> graph as 'inverted', but I do not see any 'inverted' edges in
> > >>> tests I
> > >>> tried. It seems like we can merge two graphs into one in the way
> > >>> extra
> > >>> pi edges they won't disturb each other.
> > >>>
> > >>> Do you have any quick counter-example to this approach (so I do not
> > >>> stagger for a long time searching it)?
> > >>
> > >> I could be wrong, but I think you need two different inequality
> > >> graphs.  If I recall correctly, the reason has to do with the types
> > >> of constraints inserted for conditional branch operations are
> > >> different in the upper and lower bound problems.
> > >
> > > the only difference between the two graphs is controlled by this new
> > > version of code:
> > >
> > > void BuildInequalityGraphWalker::addPiEdgesForBounds
> > >      (IOpndProxy* dst, const PiBound& lb, const PiBound& ub)
> > > {
> > >     if ( _isLower && !lb.isUndefined() ) {
> > >         addPiEdgesWithOneBoundInf(dst, false, lb);
> > >     }
> > >     else if ( !_isLower && !ub.isUndefined() ) {
> > >         addPiEdgesWithOneBoundInf(dst, true, ub);
> > >     }
> > > }
> > >
> > > in case of the lower bound problem it adds the edge of the interest
> > > for the lower bound problem taking only one side of pi-constraint. In
> > > case of upper-bound problem, it takes the other side because this is
> > > what upper problem is interested in. That's right and works well.
> > >
> > > I am thinking of adding both sides of pi-constraint in both upper and
> > > lower cases. I think, it should work, but did not test it yet. In this
> > > case the graph should look exactly the same.
> >
> > I've looked at the inequality graphs produced for the upper and lower
> > bound problems for the sort method of BidirectionalBubbleSort, and
> > they are quite different (I used your dot output support to look at
> > them).   I guess I am not sure what you mean by "the graph should
> > look exactly the same".  I am fairly certain they must be different.
> >
> > Also, I am concerned about the implications on the e-SSA graph of
> > always inserting both sides of a pi-constraint.  In the upper bound
> > problem, pi-nodes should only rename variables if they are involved
> > in a valid upper bound constraint (and vice versa for the lower-bound
> > problem).
> >
> > These problems may only creep up if the pi-constraint has one side
> > undefined (upper or lower).  Perhaps we could just treat these
> > specially, but all other pi-constraints would be identical for the
> > upper and lower bound problems.
> >
> > Once upon a time I tried to use a single inequality graph to
> > represent both the upper and lower bound problems, but I could never
> > get it to work.  I eventually gave up and implemented the code you
> > see.  But that doesn't mean I'm necessarily right, just that I may
> > not be patient enough.  :-)
> >
> > > P.S.:
> > > I realize that I invented not an ideal name for
> > > addPiEdgesWithOneBoundInf() which does not properly describe what this
> > > function does. Since both bounds can be non-infinite and it still
> > > works fine. I am going to collect similar small improvements in 3-4
> > > tiny patches and attach them to JIRA for further consideration.
> >
> > Do you have a nice way of managing layers of patches?  If so, teach
> > me!  :-)
> >
> > Otherwise, maybe we should get someone to check the code into SVN and
> > then we can submit improvements against that?
> 
> 
> 
> I've started looking into this patch. I've run into compilation problems on
> VS .NET 2003. I can update the patch and test it before integration to SVN,
> if you don't mind. Is there anything preventing us from including the new
> ABCD into the server optimization path? I can also update the emconf files
> to put classic_abcd in place of the old abcd pass.

I think, almost nothing prevents us from committing it. I reviewed the
most part. Although, the code can be somewhat polished towards better
maintainability (logging, simplicity, performance), these issues are
rather minor with respect to what is done and just works. So, I would
be happy to see it committed and send small non-critical improvements
later on.

But we are now in the middle of "quick and short stabilizing", so,
let's wait a little with this big feature. OK?

> Thanks,
> Pavel
> 
> >
> > >> I'll try to work up an example why tomorrow.
> > >
> > > that would be just great
> >
> > I tried...  My head hurts and I haven't found a good example yet...
> > ABCD is hard.  sorry.
> >
> > Naveen
> >
> >
> >
> >

-- 
Egor Pasko


Mime
View raw message