On 4/21/07, Naveen Neelakantam <[EMAIL PROTECTED]> 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 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
