[LLVMdev] SCEV ordering
djg at cray.com
Mon Apr 23 08:52:00 PDT 2007
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 Gohman, Cray Inc.
More information about the llvm-dev