[LLVMdev] SCEV ordering

[Dan Gohman]

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.