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.
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 >
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/
On Fri, Apr 20, 2007 at 03:16:03PM -0700, Chris Lattner wrote:> > 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.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 -- Dan Gohman, Cray Inc.