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
