--- Comment #17 from Segher Boessenkool <segher at gcc dot gnu.org> ---
(In reply to rguent...@suse.de from comment #16)
> I would guess so. I wonder if the combiner could restrict itself
> here? Maybe LUID "distances" are an approximation? Doesn't the
> combiner use DF uses so the number of combinations shouldn't increase
> with basic-block size but only with the number of uses? Of course
> since we don't have SSA the uses probably include those that cross
> other defs...
Combine doesn't try too many pairs: it tries every def only with its
first use, so that is linear in # insns. But the check if a combination
is valid uses reg_used_between_p, which is no good for insns a big
> That said, algorithmically first building up a kind-of-SSA to
> restrict things combine will try might help to avoid this kind
> of issues.
Yup. Not going to happen in stage4, of course :-/
There are a few other things which aren't linear, but this is the
worst one (the rest only happens occasionally, or only on successful
> Since combine does a df_analyze we should have a way to record
> the number of insns in a block without another IL walk, it could
> also fall back to 2->1 and 2->2 insn combinations after visiting
> a new PARAM max-combine-bb-insns-3-3 number of insns in an EBB.
The 3->1 (or 3->2) isn't really the problem; there just are many more
to try than 2->.
> Actually it already does two walks over the whole function in
> combine_instructions it seems, so recording # insns per EBB should
> be possible? (if that's really the key metric causing the issue)
The average distance between a set and its first use is the key metric.
The numbers make it feel like that is pretty constrained here still
(I haven't run numbers on it), but 100 is very much already if there are
1M insns in the block (or whatever). All numbers that aren't terrible,
but combines it takes up quite a chunk of time.
Combine also makes garbage for every try, and none of that is cleaned
up during combine. Maybe we should change that? (I can try next week).