harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Naveen Neelakantam <neela...@uiuc.edu>
Subject Re: [drlvm][jit] abcd and devirtualizer patches was: [OT] Harmony used in accepted research paper
Date Fri, 20 Apr 2007 23:04:19 GMT

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




Mime
View raw message