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.


Pushed to the trunk,


Jeff