More gimple const/copy propagation opportunities

More gimple const/copy propagation opportunities

While investigating a benchmark for optimization opportunities I came across single block loop which either iterates precisely once or forever.    This is an interesting scenario as we can ignore the infinite looping path and treat any PHI nodes as degenerates.  So more concretely let's consider this trivial testcase:

volatile void abort (void);

void
foo(int a)
{
 int b = 0;

 while (1)
   {
     if (!a)
       break;
     b = 1;
   }

 if (b != 0)
   abort ();
}

Quick analysis shows that b's initial value is 0 and its value only changes if we enter an infinite loop.  So if we get to the test b != 0, the only possible value b could have would be 0 and the test and its true arm can be eliminated.

The DOM3 dump looks something like this:

;;   basic block 2, loop depth 0, count 118111600 (estimated locally), maybe hot
;;    prev block 0, next block 3, flags: (NEW, VISITED)
;;    pred:       ENTRY [always]  count:118111600 (estimated locally) (FALLTHRU,EXECUTABLE)
;;    succ:       3 [always]  count:118111600 (estimated locally) (FALLTHRU,EXECUTABLE)

;;   basic block 3, loop depth 1, count 1073741824 (estimated locally), maybe hot
;;    prev block 2, next block 4, flags: (NEW, VISITED)
;;    pred:       2 [always]  count:118111600 (estimated locally) (FALLTHRU,EXECUTABLE)
;;                3 [89.0% (guessed)]  count:955630224 (estimated locally) (FALSE_VALUE,EXECUTABLE)
  # b_1 = PHI <0(2), 1(3)>
  if (a_3(D) == 0)
    goto <bb 4>; [11.00%]
  else
    goto <bb 3>; [89.00%]
;;    succ:       4 [11.0% (guessed)]  count:118111600 (estimated locally) (TRUE_VALUE,EXECUTABLE)
;;                3 [89.0% (guessed)]  count:955630224 (estimated locally) (FALSE_VALUE,EXECUTABLE)

;;   basic block 4, loop depth 0, count 118111600 (estimated locally), maybe hot
;;    prev block 3, next block 5, flags: (NEW, VISITED)
;;    pred:       3 [11.0% (guessed)]  count:118111600 (estimated locally) (TRUE_VALUE,EXECUTABLE)
  if (b_1 != 0)
    goto <bb 5>; [0.00%]
  else
    goto <bb 6>; [100.00%]
;;    succ:       5 [never]  count:0 (precise) (TRUE_VALUE,EXECUTABLE)
;;                6 [always]  count:118111600 (estimated locally) (FALSE_VALUE,EXECUTABLE)

This is a good representative of what the benchmark code looks like.

The primary effect we want to capture is to realize that the test if (b_1 != 0) is always false and optimize it accordingly.

In the benchmark, this opportunity is well hidden until after the loop optimizers have completed, so the first chance to capture this case is in DOM3.  Furthermore, DOM wants loops normalized with latch blocks/edges.  So instead of bb3 looping back to itself, there's an intermediate empty block during DOM.

I originally thought this was likely to only affect the benchmark.  But when I instrumented the optimization and bootstrapped GCC, much to my surprise there were several hundred similar cases identified in GCC itself.  So it's not as benchmark specific as I'd initially feared.

Anyway, detecting this in DOM is pretty simple.   We detect the infinite loop, including the latch block.  Once we've done that, we walk the PHI nodes and attach equivalences to the appropriate outgoing edge.   That's all we need to do as the rest of DOM is already prepared to handle equivalences on edges.

gcc/
	* tree-ssa-dom.cc (single_block_loop_p): New function.
	(record_edge_info): Also record equivalences for the outgoing
	edge of a single block loop where the condition is an invariant.

gcc/testsuite/
	* gcc.dg/infinite-loop.c: New test.