[LLVMdev] SCEV ordering
sabre at nondot.org
Fri Apr 20 17:16:03 CDT 2007
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.
> 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
If it is possible, it would be useful to file a bugzilla with an example
that shows this happening.
More information about the LLVMdev