https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80960
--- Comment #16 from rguenther at suse dot de <rguenther at suse dot de> --- On Tue, 2 Apr 2019, segher at gcc dot gnu.org wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80960 > > --- Comment #15 from Segher Boessenkool <segher at gcc dot gnu.org> --- > It seems to be that this happens for huge basic blocks, and the combiner > tries to combine pairs of instructions that are far apart. This is unlikely > to work often, and the cost is quadratic in # insns, the way checking where > a register is used works. > > The param to do only 2->1 (and 2->2) combinations should help a lot, make > combine not take longer than the rest of the compiler does. Does it? 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... That said, algorithmically first building up a kind-of-SSA to restrict things combine will try might help to avoid this kind of issues. 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. 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)
