[Bug tree-optimization/57488] [4.9 regression] loop terminates early at -O3

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57488

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
The fun thing is that this is a regular partial redundancy but requires
an earlier partial partial redundancy elimination to be performed.

So what happens is that

int v;
void foo (int n)
{
  int i, j;
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      v++;
}

gets transformed to

int v;
void foo (int n)
{
  int i, j;
  for (i = 0; i < n; ++i)
    tem = v;
    for (j = 0; j < n; ++j)
      # PHI <tem, v>
      v = tem + 1;
}

and in the 3rd insert iteration this becomes

int v;
void foo (int n)
{
  int i, j;
  tem2 = v;
  for (i = 0; i < n; ++i)
    # tem2 = PHI <tem2, ...>
    tem = tem2;
    for (j = 0; j < n; ++j)
      # tem = PHI <tem, v>
      v = tem + 1;
}

with ... replaced by the value and representative 'tem' because via the
NEW sets we propagate that down to the latch.

Of course PRE works fine with the above simplified testcase ...

The following speedup patch fixes the bug:

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c  (revision 200237)
+++ gcc/tree-ssa-pre.c  (working copy)
@@ -3665,6 +3666,12 @@ insert (void)
       if (dump_file && dump_flags & TDF_DETAILS)
        fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
+
+      /* Clear the NEW sets before the next iteration.  We have already
+         fully propagated its contents.  */
+      if (new_stuff)
+       FOR_ALL_BB (bb)
+         bitmap_set_free (NEW_SETS (bb));
     }
   statistics_histogram_event (cfun, "insert iterations", num_iterations);
 }

remains to be seen why ... (I can only think of NEW sets propagated
over backedges requiring a 2nd iteration to make their effect visible)

That said, this bug seems to be latent for a long time.