On Apr 25, 2007, at 9:06 AM, Pavel Ozhdikhin wrote:
> 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 pi
>> constraint. 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 lower
>> bound
>> > 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
I'll take a look, but I need to setup a Windows dev environment first.
Naveen
>
>
>> 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
>> >
>> >
>> >
>> >
>>
