On 4/21/07, Naveen Neelakantam 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:
> >>
>
>
>
> >>> 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.
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
>
>
>
>