[PATCH] fwprop: Prevent infinite looping (PR79405)

[Segher Boessenkool <segher at kernel dot crashing dot org>]

The algorithm fwprop uses never reconsiders a possible propagation,
although it could succeed if the def (in the def-use to propagate)
has changed.  This causes fwprop to do infinite propagations, like
in the scenario in the PR, where we end up with effectively
  B = A
  A = B
  D = A
where only propagations into the last statement are still tried, and
that loops (it becomes D = B, then back to D = A, etc.)

Fixing this properly isn't easy; this patch instead limits the number
of propagations performed to the number of uses we originally had,
which is the maximum number of propagations that can be done if there
are no such infinite loops.

Bootstrapped and regression checked on powerpc64-linux {-m64,-m32};
is this okay for trunk?


Segher


2017-03-23  Segher Boessenkool  <segher@kernel.crashing.org>

	PR rtl-optimization/79405
	* fwprop.c (propagations_left): New variable.
	(forward_propagate_into): Decrement it.
	(fwprop_init): Initialize it.
	(fw_prop): If the variable has reached zero, stop propagating.
	(fwprop_addr): Ditto.

gcc/testsuite/
	PR rtl-optimization/79405
	gcc.dg/pr79405.c: New testcase.

---
 gcc/fwprop.c                   | 17 ++++++++++++++++
 gcc/testsuite/gcc.dg/pr79405.c | 45 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 62 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr79405.c

diff --git a/gcc/fwprop.c b/gcc/fwprop.c
index 285fb1a..0ab25ef 100644
--- a/gcc/fwprop.c
+++ b/gcc/fwprop.c
@@ -120,6 +120,13 @@ static vec<df_ref> use_def_ref;
 static vec<df_ref> reg_defs;
 static vec<df_ref> reg_defs_stack;
 
+/* The maximum number of propagations that are still allowed.  If we do
+   more propagations than originally we had uses, we must have ended up
+   in a propagation loop, as in PR79405.  Until the algorithm fwprop
+   uses can obviously not get into such loops we need a workaround like
+   this.  */
+static int propagations_left;
+
 /* The MD bitmaps are trimmed to include only live registers to cut
    memory usage on testcases like insn-recog.c.  Track live registers
    in the basic block and do not perform forward propagation if the
@@ -1407,6 +1414,8 @@ forward_propagate_into (df_ref use)
   if (forward_propagate_and_simplify (use, def_insn, def_set)
       || forward_propagate_subreg (use, def_insn, def_set))
     {
+      propagations_left--;
+
       if (cfun->can_throw_non_call_exceptions
 	  && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
 	  && purge_dead_edges (DF_REF_BB (use)))
@@ -1434,6 +1443,8 @@ fwprop_init (void)
   active_defs = XNEWVEC (df_ref, max_reg_num ());
   if (flag_checking)
     active_defs_check = sparseset_alloc (max_reg_num ());
+
+  propagations_left = DF_USES_TABLE_SIZE ();
 }
 
 static void
@@ -1480,6 +1491,9 @@ fwprop (void)
 
   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
     {
+      if (!propagations_left)
+	break;
+
       df_ref use = DF_USES_GET (i);
       if (use)
 	if (DF_REF_TYPE (use) == DF_REF_REG_USE
@@ -1540,6 +1554,9 @@ fwprop_addr (void)
      end, and we'll go through them as well.  */
   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
     {
+      if (!propagations_left)
+	break;
+
       df_ref use = DF_USES_GET (i);
       if (use)
 	if (DF_REF_TYPE (use) != DF_REF_REG_USE
diff --git a/gcc/testsuite/gcc.dg/pr79405.c b/gcc/testsuite/gcc.dg/pr79405.c
new file mode 100644
index 0000000..c17baff
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr79405.c
@@ -0,0 +1,45 @@
+/* PR rtl-optimization/79405 */
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+char cz;
+long long int xx, u2;
+
+void
+qv (int js, int wl)
+{
+  if (js != 0)
+    {
+      short int sc;
+      int *at = (int *)&sc;
+      long long int gx = 0;
+
+      for (;;)
+	{
+	  *at = 0;
+	  js /= sc;
+
+	  for (wl = 0; wl < 2; ++wl)
+	    {
+	      xx = gx;
+	      u2 %= xx > 0;
+	      cz /= u2;
+
+ fa:
+	      if (cz != u2)
+		{
+		  gx |= js;
+		  cz = gx / js;
+		}
+	    }
+	}
+
+ yq:
+      wl /= 0x80000000;
+      u2 = wl;
+      u2 |= (wl != 0) | (wl != 0 && gx != 0);
+      js = u2;
+      goto fa;
+    }
+  goto yq;
+}
-- 
1.9.3