PATCH RFC: Speed up compilation of 20001226-1.c

[Daniel Berlin]

On 15 Apr 2007 14:06:55 -0700, Ian Lance Taylor <iant@google.com> wrote:
> 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.

If you want to play with the ordering of VRP, there is an optimal
ordering of visitation for each type of propagation problem (RPO or
PO) that will give you the best results.  It is not actually related
to the number of successors or predecessors, but where they go.