Re: Add a new combine pass

[Segher Boessenkool <segher@kernel.crashing.org>]

On Wed, Nov 27, 2019 at 09:29:27AM +0100, Richard Biener wrote:
> On Tue, Nov 26, 2019 at 2:42 AM Segher Boessenkool
> <segher@kernel.crashing.org> wrote:
> > combine actually *calculates* DU chains almost completely, it just throws
> > away most of that information (it wants to have LOG_LINKS, as it did ages
> > ago).  The only thing stopping us from doing that right now is that not
> > all uses are counted (some are skipped).
> >
> > Since combine works only within BBs, DU chains are linear to compute, and
> > UD chains are trivial (and just linear to compute).
> 
> quadraticness appears for RTL DU/UD chains because of partial definitions,
> that doesn't change for BBs so even there computing is them is quadratic
> (because recording them is).  The situation is simply having N partial
> defs all reaching M uses which gives you a chain of size N * M.

And both N and M are constants here (bounded by a constant).  The only
dimensions we care about are those the user can grow unlimited: number
of registers, number of instructions, number of functions, that kind of
thing.

The control flow graph in a basic block is a DAG, making most of this
linear to compute.  Only updating it after every separate change is not
easily linear in total.

> Updating is linear as well if you can disregard partial defs.  Updating cannot
> be quadratic if compute is linear ;)

Sure it can.  Updating has to be O(1) (amortized) per change for the whole
pass to be O(n).  If it is O(n) per change you are likely O(n^2) in total.

I don't see how to make combine itself O(1) per change, but yeah I can
see how that can work (or almost work) for something simpler (and less
weighed down by history :-) ).


Segher