The irritating test case gcc.c-torture/compile/20001226-1.c takes a
long time to compile. In particular, I noticed that there was a 0.5%
increase in compile time of that test case with my recently proposed
patch to VRP. I looked into it a bit, and found that with a small
heuristic in the propagator I could speed up compilation of that test
case by 40% (really) at -O2. It doesn't seem to make much difference
for other test cases, or for a bootstrap.
Basically, in that highly artificial test case there is a block with
over 8000 predecessors. Each predecessor is a conditional with two
successors. It so happens that for each conditional the propagator
puts the block with over 8000 predecessors first on the work list.
Each time that happens, VRP will spend time looking at each
predecessor edge. Each time one more edge will be executable (which
in this context means that the propagation engine has seen them
already). It's better for VRP to look at this block last, when all
the edges are executable.
My patch is to change the code which adds a block to the work list so
that, instead of always adding to the tail, it checks if the new block
has fewer predecessors than the tail block, and, if so, the new block
is added to the head instead.