[LLVMdev] SCEV ordering

[Chris Lattner]

On Fri, 20 Apr 2007, 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.

Ouch.  :(

> 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?

I'm strongly in favor of more canonicalization.  The problem is that we 
can't sort on the natural key (the address of the SCEV or Value*) because 
that will make the compiler non-deterministic.

It might be worthwhile to take a look at the reassociate pass which has a 
good solution for this, but which isn't directly applicable.  It basically 
gives each instruction in the program a unique ID based on the BB it is in 
and the index of the instruction in the BB.  This *might* work for SCEV if 
we're careful to keep the mapping up-to-date as instructions are inserted 
and removed, but might be tricky to get right.

If there is something simpler that gets most of the gain, that might be a 
good intermediate step.  In any case, you're right that this is a major 
issue :)

If it is possible, it would be useful to file a bugzilla with an example 
that shows this happening.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/