SCEV ordering

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

Hi Dan,

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.

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. :frowning:

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 :slight_smile:

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

-Chris

I think what I was missing is that the reassociate pass itself usually
saves the day. With the -std-compile-opts passes, reassociate is run before
the SCEV-using passes, so most chains of adds are already in a canonical
order. There still are some cases where having ScalarEvolution do its own
sorting does reduce the total number of SCEVs allocated, but I now see that
it's pretty rare in practice.

Dan

Ok! If you find a specific example, please do find a bugzilla. This is the sort of thing that is very difficult to notice while studying .s files, yet can have a big impact. :slight_smile:

-Chris