On Wed, Nov 27, 2019 at 09:29:27AM +0100, Richard Biener wrote: > On Tue, Nov 26, 2019 at 2:42 AM Segher Boessenkool > <seg...@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
