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 Fri, 20 Apr 2007 09:45:16 GMT
On the 0x2BE day of Apache Harmony Naveen Neelakantam wrote:
> On Apr 20, 2007, at 1:42 AM, Egor Pasko wrote:
> 
> > On the 0x2B6 day of Apache Harmony Naveen Neelakantam wrote:
> >> I've uploaded a patch against Egor's ABCD implementation in
> >> HARMONY-1788.   It passes the tests included with HARMONY-2141,
> >> HARMONY-2144 and HARMONY-2147, and removes all but one bounds check
> >> from BidirectionalBubbleSort in HARMONY-1564.  I've also ran the
> >> DaCapo benchmarks using it and it doesn't seem to break anything.
> >
> > Naveen, I am somewhere in the middle of looking at your great
> > work. Sorry for being so slow, but, you know, making sure that ABCD
> > works as expected is not an easy thing to do :)
> 
> Indeed.  :-)
> 
> > 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.

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.

> I'll try to work up an example why tomorrow.

that would be just great

> 
> But maybe you are suggesting that we could have a single data-
> structure that logically represents both the upper and lower bound
> problems.  If so, I think that might be possible (and would certainly
> be more efficient).
> 
> Naveen
> 
> >
> > Will ask/comment more soon.
> >
> >> I've also opened a JIRA issue for my profile-based abstract and
> >> virtual call devirtualization patch: HARMONY-3630.
> >>
> >> Naveen
> >>
> >> On Apr 9, 2007, at 12:23 AM, Pavel Ozhdikhin wrote:
> >>
> >>> Naveen,
> >>>
> >>> Congrartulations! I eager to read your paper - please announce a
> >>> link here
> >>> when it's available.
> >>>
> >>> I'm also looking forward to a new ABCD impementation from Egor and
> >>> your -
> >>> your both did a lot to make it working, now it's time to make use
> >>> of it in
> >>> Harmony.
> >>>
> >>> Thanks,
> >>> Pavel
> >>>
> >>> On 4/8/07, Naveen Neelakantam <neelakan@uiuc.edu> wrote:
> >>>>
> >>>> Hello all,
> >>>>
> >>>> You might like to hear that a paper which used Apache Harmony as
> >>>> part
> >>>> of a research infrastructure was accepted to ISCA 2007
> >>>> (International
> >>>> Symposium on Computer Architecture).  I will be presenting this
> >>>> work
> >>>> in San Diego in June and will be sure to include a slide plugging
> >>>> Harmony.
> >>>>
> >>>> I would like to thank all of the JVM and classlib developers who
> >>>> made
> >>>> such an endeavor even possible.  You are doing a wonderful job, and
> >>>> it is much appreciated!  Please pat yourself on the back.  :-)
> >>>>
> >>>> BTW, in the process of doing this work I helped get Egor Pasko's
> >>>> ABCD
> >>>> reimplementation finished, and I added profile-based abstract call
> >>>> and virtual devirtualization to the code from HARMONY-2012.  I'll
> >>>> post the patches after the weekend.
> >>>>
> >>>> Thanks again,
> >>>> Naveen
> >>>>
> >>
> >>
> >
> > -- 
> > Egor Pasko
> >
> 
> 

-- 
Egor Pasko


Mime
View raw message