I think it's been the case for a while that parallel builds of GCC tend
to serialise around the compilation of insn-recog.c, especially with
higher --enable-checking settings. This patch tries to speed that
up by replacing most of genrecog with a new algorithm.
I think the main problems with the current code are:
1. Vector architectures have added lots of new instructions that have
a similar shape and differ only in mode, code or unspec number.
The current algorithm doesn't have any way of factoring out those
similarities.
2. When matching a particular instruction, the current code examines
everything about a SET_DEST before moving on to the SET_SRC. This has
two subproblems:
2a. The destination of a SET isn't very distinctive. It's usually
just a register_operand, a memory_operand, a nonimmediate_operand
or a flags register. We therefore tend to backtrack to the
SET_DEST a lot, oscillating between groups of instructions with
the same kind of destination.
2b. Backtracking through predicate checks is relatively expensive.
It would be good to narrow down the "shape" of the instruction
first and only then check the predicates. (The backtracking is
expensive in terms of insn-recog.o compile time too, both because
we need to copy into argument registers and out of the result
register, and because it adds more sites where spills are needed.)
3. The code keeps one local variable per rtx depth, so it ends up
loading the same rtx many times over (mostly when backtracking).
This is very expensive in rtl-checking builds because each XEXP
includes a code check and a line-specific failure call.
In principle the idea of having one local variable per depth
is good. But it was originally written that way when all optimisations
were done at the rtl level and I imagine each local variable mapped
to one pseudo register. These days the statements that reload the
value needed on backtracking lead to many more SSA names and phi
statements than you'd get with just a single variable per position
(loaded once, so naturally SSA). There is still the potential benefit
of avoiding having sibling rtxes live at once, but fixing (2) above
reduces that problem.
Also, the code is all goto-based, which makes it rather hard to step through.
The patch deals with these as follows:
1. Detect subpatterns that differ only by mode, code and/or integer
(e.g. unspec number) and split them out into a common routine.
2. Match the "shape" of the instruction first, in terms of codes,
integers and vector lengths, and only then check the modes, predicates
and dups. When checking the shape, handle SET_SRCs before SET_DESTs.
In practice this seems to greatly reduce the amount of backtracking.
3. Have one local variable per rtx position. I tested the patch with
and without the change and it helped a lot with rtl-checking builds
without seeming to affect release builds much either way.
As far as debuggability goes, the new code avoids gotos and just
uses "natural" control flow.
The headline stat is that a stage 3 --enable-checking=yes,rtl,df
build of insn-recog.c on my box goes from 7m43s to 2m2s (using the
same stage 2 compiler). The corresponding --enable-checking=release
change is from 49s to 24s (less impressive, as expected).
The patch seems to speed up recog. E.g. the time taken to build
fold-const.ii goes from 6.74s before the patch to 6.69s after it;
not a big speed-up, but reproducible.
Tested on x86_64-linux-gnu, aarch64-linux-gnu and arm-none-eabi.
Also tested by building the testsuite for each of the targets above
and making sure there were no assembly differences. Made sure that no
objects in spec2k6 changed for aarch64-linux-gnu (except for perlbench
perl.o and cactusADM datestamp.o, where the differences are timestamps).
OK to install?