[LLVMdev] SCEV ordering

[Reid Spencer]

Hi Dan,

On Fri, 2007-04-20 at 10:37 -0500, Dan Gohman wrote:
> 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.

I don't see why the address-of-Value sorting isn't working here. If %i,
%r54 and %r59 are really the same value in both cases, they should have
the same address in both cases which means sorting by Value address
should be sufficient.  Is there some reason they can't be sorted by
Value address with some kind of default for things like SCEVUnknown?

Reid. 

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