On 4/25/07, Pavel Ozhdikhin <pavel.ozhdikhin@gmail.com> 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 counterexample 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 piconstraint. In
> > > case of upperbound 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 piconstraint 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 eSSA graph of
> > always inserting both sides of a piconstraint. In the upper bound
> > problem, pinodes should only rename variables if they are involved
> > in a valid upper bound constraint (and vice versa for the lowerbound
> > problem).
> >
> > These problems may only creep up if the piconstraint has one side
> > undefined (upper or lower). Perhaps we could just treat these
> > specially, but all other piconstraints 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 noninfinite and it still
> > > works fine. I am going to collect similar small improvements in 34
> > > 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.
>
Naveen,
I've updated the patch but ran into the smoke test failure in Xem:server
mode. Please see details in the JIRA.
Thanks,
Pavel
> 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
> >
> >
> >
> >
>
