Fix phi backedge detection in backprop (PR85989)

Message ID 87fu268ywj.fsf@linaro.org
State New
Headers show
Series
  • Fix phi backedge detection in backprop (PR85989)
Related show

Commit Message

Richard Sandiford June 1, 2018, 12:38 p.m.
This PR is a nasty wrong code bug due to my fluffing a test for a
backedge in gimple-ssa-backprop.c.  Backedges are supposed to be
from definitions in the statement we're visiting to uses in statements
that we haven't visited yet.  However, the check failed to account for
PHIs in the current block that had already been processed, so if two
PHIs in the same block referenced each other, we'd treat both
references as backedges.

In more detail:

The first phase of the pass goes through all statements in an arbitrary
order, making optimistic assumptions about any statements that haven't
been visited yet.  The second phase then calculates a correct
(supposedly maximal) fixed point.

Although the first phase order is arbitrary in principle, we still use
the CFG rpo to cut down on the backedges.  This means that the only
thing that's truly arbitrary is the order that we process the PHIs
in a block.  Any order should be OK and should eventually give the
same results.  But we have to follow whatever order we pick,
and the pass wasn't doing that.

Tested on aarch64-linux-gnu (with and without SVE), aarch64_be-elf
and x86_64-linux-gnu.  OK for trunk and all release branches?

Sorry for what in hindsight was a really stupid bug.

Richard



2018-06-01  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/85989
	* gimple-ssa-backprop.c (backprop::m_visited_phis): New member
	variable.
	(backprop::intersect_uses): Check it when deciding whether this
	is a backedge reference.
	(backprop::process_block): Add each phi to m_visited_phis
	after visiting it, then clear it at the end.

gcc/testsuite/
	PR tree-optimization/85989
	* gcc.dg/torture/pr85989.c: New test.

Comments

Richard Biener June 1, 2018, 12:42 p.m. | #1
On Fri, Jun 1, 2018 at 2:38 PM Richard Sandiford
<richard.sandiford@linaro.org> wrote:
>

> This PR is a nasty wrong code bug due to my fluffing a test for a

> backedge in gimple-ssa-backprop.c.  Backedges are supposed to be

> from definitions in the statement we're visiting to uses in statements

> that we haven't visited yet.  However, the check failed to account for

> PHIs in the current block that had already been processed, so if two

> PHIs in the same block referenced each other, we'd treat both

> references as backedges.

>

> In more detail:

>

> The first phase of the pass goes through all statements in an arbitrary

> order, making optimistic assumptions about any statements that haven't

> been visited yet.  The second phase then calculates a correct

> (supposedly maximal) fixed point.

>

> Although the first phase order is arbitrary in principle, we still use

> the CFG rpo to cut down on the backedges.  This means that the only

> thing that's truly arbitrary is the order that we process the PHIs

> in a block.  Any order should be OK and should eventually give the

> same results.  But we have to follow whatever order we pick,

> and the pass wasn't doing that.

>

> Tested on aarch64-linux-gnu (with and without SVE), aarch64_be-elf

> and x86_64-linux-gnu.  OK for trunk and all release branches?


OK.

Thanks,
Richard.

> Sorry for what in hindsight was a really stupid bug.

>

> Richard

>

>

>

> 2018-06-01  Richard Sandiford  <richard.sandiford@linaro.org>

>

> gcc/

>         PR tree-optimization/85989

>         * gimple-ssa-backprop.c (backprop::m_visited_phis): New member

>         variable.

>         (backprop::intersect_uses): Check it when deciding whether this

>         is a backedge reference.

>         (backprop::process_block): Add each phi to m_visited_phis

>         after visiting it, then clear it at the end.

>

> gcc/testsuite/

>         PR tree-optimization/85989

>         * gcc.dg/torture/pr85989.c: New test.

>

> Index: gcc/gimple-ssa-backprop.c

> ===================================================================

> --- gcc/gimple-ssa-backprop.c   2018-05-18 09:26:37.726714678 +0100

> +++ gcc/gimple-ssa-backprop.c   2018-06-01 13:36:04.223449400 +0100

> @@ -260,6 +260,11 @@ dump_usage_info (FILE *file, tree var, u

>       post-order walk.  */

>    auto_sbitmap m_visited_blocks;

>

> +  /* A bitmap of phis that we have finished processing in the initial

> +     post-order walk, excluding those from blocks mentioned in

> +     M_VISITED_BLOCKS.  */

> +  auto_bitmap m_visited_phis;

> +

>    /* A worklist of SSA names whose definitions need to be reconsidered.  */

>    auto_vec <tree, 64> m_worklist;

>

> @@ -496,8 +501,11 @@ backprop::intersect_uses (tree var, usag

>      {

>        if (is_gimple_debug (stmt))

>         continue;

> -      if (is_a <gphi *> (stmt)

> -         && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))

> +      gphi *phi = dyn_cast <gphi *> (stmt);

> +      if (phi

> +         && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index)

> +         && !bitmap_bit_p (m_visited_phis,

> +                           SSA_NAME_VERSION (gimple_phi_result (phi))))

>         {

>           /* Skip unprocessed phis.  */

>           if (dump_file && (dump_flags & TDF_DETAILS))

> @@ -505,7 +513,7 @@ backprop::intersect_uses (tree var, usag

>               fprintf (dump_file, "[BACKEDGE] ");

>               print_generic_expr (dump_file, var);

>               fprintf (dump_file, " in ");

> -             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);

> +             print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);

>             }

>         }

>        else

> @@ -629,7 +637,12 @@ backprop::process_block (basic_block bb)

>      }

>    for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);

>         gsi_next (&gpi))

> -    process_var (gimple_phi_result (gpi.phi ()));

> +    {

> +      tree result = gimple_phi_result (gpi.phi ());

> +      process_var (result);

> +      bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));

> +    }

> +  bitmap_clear (m_visited_phis);

>  }

>

>  /* Delete the definition of VAR, which has no uses.  */

> Index: gcc/testsuite/gcc.dg/torture/pr85989.c

> ===================================================================

> --- /dev/null   2018-04-20 16:19:46.369131350 +0100

> +++ gcc/testsuite/gcc.dg/torture/pr85989.c      2018-06-01 13:36:04.223449400 +0100

> @@ -0,0 +1,31 @@

> +/* { dg-do run } */

> +

> +#define N 9

> +

> +void __attribute__((noipa))

> +f (double x, double y, double *res)

> +{

> +  y = -y;

> +  for (int i = 0; i < N; ++i)

> +    {

> +      double tmp = y;

> +      y = x;

> +      x = tmp;

> +      res[i] = i;

> +    }

> +  res[N] = y * y;

> +  res[N + 1] = x;

> +}

> +

> +int

> +main (void)

> +{

> +  double res[N + 2];

> +  f (10, 20, res);

> +  for (int i = 0; i < N; ++i)

> +    if (res[i] != i)

> +      __builtin_abort ();

> +  if (res[N] != 100 || res[N + 1] != -20)

> +    __builtin_abort ();

> +  return 0;

> +}

Patch

Index: gcc/gimple-ssa-backprop.c
===================================================================
--- gcc/gimple-ssa-backprop.c	2018-05-18 09:26:37.726714678 +0100
+++ gcc/gimple-ssa-backprop.c	2018-06-01 13:36:04.223449400 +0100
@@ -260,6 +260,11 @@  dump_usage_info (FILE *file, tree var, u
      post-order walk.  */
   auto_sbitmap m_visited_blocks;
 
+  /* A bitmap of phis that we have finished processing in the initial
+     post-order walk, excluding those from blocks mentioned in
+     M_VISITED_BLOCKS.  */
+  auto_bitmap m_visited_phis;
+
   /* A worklist of SSA names whose definitions need to be reconsidered.  */
   auto_vec <tree, 64> m_worklist;
 
@@ -496,8 +501,11 @@  backprop::intersect_uses (tree var, usag
     {
       if (is_gimple_debug (stmt))
 	continue;
-      if (is_a <gphi *> (stmt)
-	  && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))
+      gphi *phi = dyn_cast <gphi *> (stmt);
+      if (phi
+	  && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index)
+	  && !bitmap_bit_p (m_visited_phis,
+			    SSA_NAME_VERSION (gimple_phi_result (phi))))
 	{
 	  /* Skip unprocessed phis.  */
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -505,7 +513,7 @@  backprop::intersect_uses (tree var, usag
 	      fprintf (dump_file, "[BACKEDGE] ");
 	      print_generic_expr (dump_file, var);
 	      fprintf (dump_file, " in ");
-	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 	    }
 	}
       else
@@ -629,7 +637,12 @@  backprop::process_block (basic_block bb)
     }
   for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
        gsi_next (&gpi))
-    process_var (gimple_phi_result (gpi.phi ()));
+    {
+      tree result = gimple_phi_result (gpi.phi ());
+      process_var (result);
+      bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));
+    }
+  bitmap_clear (m_visited_phis);
 }
 
 /* Delete the definition of VAR, which has no uses.  */
Index: gcc/testsuite/gcc.dg/torture/pr85989.c
===================================================================
--- /dev/null	2018-04-20 16:19:46.369131350 +0100
+++ gcc/testsuite/gcc.dg/torture/pr85989.c	2018-06-01 13:36:04.223449400 +0100
@@ -0,0 +1,31 @@ 
+/* { dg-do run } */
+
+#define N 9
+
+void __attribute__((noipa))
+f (double x, double y, double *res)
+{
+  y = -y;
+  for (int i = 0; i < N; ++i)
+    {
+      double tmp = y;
+      y = x;
+      x = tmp;
+      res[i] = i;
+    }
+  res[N] = y * y;
+  res[N + 1] = x;
+}
+
+int
+main (void)
+{
+  double res[N + 2];
+  f (10, 20, res);
+  for (int i = 0; i < N; ++i)
+    if (res[i] != i)
+      __builtin_abort ();
+  if (res[N] != 100 || res[N + 1] != -20)
+    __builtin_abort ();
+  return 0;
+}