[LLVMdev] SCEV ordering

[Dan Gohman]

The SCEV framework sorts operands of commutative SCEVs by their
getSCEVType() value, and then does an ad-hoc sort to group repeated
operands, but it does not do a full sort. In some test cases I'm
looking at right now, this causes it to miss opportunities to reuse
SCEV objects, as in cases like this:

 ( %i +  %r54 +  %r59)
 ( %r54 +  %r59 +  %i)

As a result, passes like LoopStrengthReduce which use addresses of
SCEVs as keys in std::map end up using different entries for these.

The obvious solution would be to sort the values. Many SCEV types
could be ordered in reasonable ways, though for SCEVUnknown it
would require an ordering for Value objects, and I don't really
want this to get complicated. I'm considering just using
getValueID() as a primary sort and then using the value name to
sort values of the same kind. Using names is straight-forward, but
it could lead to spruious reorderings, since the names are
arbitrary.

Is there anything I'm missing here? Or, would there be other uses
for a general ordering for Values?

Dan

-- 
Dan Gohman, Cray Inc.