Patchwork Fix missed propagation opportunity in DOM

login
register
mail settings
Submitter Jeff Law
Date Sept. 17, 2013, 5:27 p.m.
Message ID <52389119.3040403@redhat.com>
Download mbox | patch
Permalink /patch/275515/
State New
Headers show

Comments

Jeff Law - Sept. 17, 2013, 5:27 p.m.
This is a repost with fixes to avoid the phase-ordering problem exposed 
by 58387 and 58340.  I've included the testcase for 58387.

--


I recently noticed that we were failing to propagate edge equivalences 
into PHI arguments in non-dominated successors.

The case loos like this:

;;   basic block 11, loop depth 0, count 0, freq 160, maybe hot
;;    prev block 10, next block 12, flags: (NEW, REACHABLE)
;;    pred:       10 [50.0%]  (FALSE_VALUE,EXECUTABLE)
   _257 = di_13(D)->comps;
   _258 = (long unsigned int) _255;
   _259 = _258 * 24;
   p_260 = _257 + _259;
   _261 = _255 + 1;
   di_13(D)->next_comp = _261;
   if (p_260 != 0B)
     goto <bb 12>;
   else
     goto <bb 13>;
;;    succ:       12 [100.0%]  (TRUE_VALUE,EXECUTABLE)
;;                13 (FALSE_VALUE,EXECUTABLE)

;;   basic block 12, loop depth 0, count 0, freq 272, maybe hot
;;   Invalid sum of incoming frequencies 160, should be 272
;;    prev block 11, next block 13, flags: (NEW, REACHABLE)
;;    pred:       11 [100.0%]  (TRUE_VALUE,EXECUTABLE)
   p_260->type = 37;
   p_260->u.s_builtin.type = _139;
;;    succ:       13 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 13, loop depth 0, count 0, freq 319, maybe hot
;;   Invalid sum of incoming frequencies 432, should be 319
;;    prev block 12, next block 14, flags: (NEW, REACHABLE)
;;    pred:       110 [100.0%]  (FALLTHRU)
;;                12 [100.0%]  (FALLTHRU,EXECUTABLE)
;;                11 (FALSE_VALUE,EXECUTABLE)
   # _478 = PHI <0B(110), p_260(12), p_260(11)>
   ret = _478;
   _142 = di_13(D)->expansion;
   _143 = _478->u.s_builtin.type;

In particular note block 11 does *not* dominate block 13.  However, we 
know that when we traverse the edge 11->13 that p_260 will have the 
value zero, which should be propagated into the PHI node.

After fixing the propagation with the attached patch we have
_478 = PHI <0B(110), p_260(12), 0B(11)>

I have other code which then discovers the unconditional NULL pointer 
dereferences when we traverse 110->13 or 11->13 and isolates those paths.

That in turn allows blocks 12 and 13 to be combined, which in turn 
allows discovery of additional CSE opportunities.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu.  Applied 
to the trunk.
* gcc.c-torture/execute/pr58387.c: New test.


	* tree-ssa-dom.c (cprop_into_successor_phis): Also propagate
	edge implied equivalences into successor phis.
	* tree-ssa-threadupdate.c (phi_args_equal_on_edges): Moved into
	here from tree-ssa-threadedge.c.
	(mark_threaded_blocks): When threading through a joiner, if both
	successors of the joiner's clone reach the same block, verify the
	PHI arguments are equal.  If not, cancel the jump threading request.
	* tree-ssa-threadedge.c (phi_args_equal_on_edges): Moved into
	tree-ssa-threadupdate.c
	(thread_across_edge): Don't check PHI argument equality when
	threading through joiner block here.

Patch

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr58387.c b/gcc/testsuite/gcc.c-torture/execute/pr58387.c
new file mode 100644
index 0000000..74c32df
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr58387.c
@@ -0,0 +1,11 @@ 
+extern void abort(void);
+
+int a = -1; 
+
+int main ()
+{
+  int b = a == 0 ? 0 : -a;
+  if (b < 1)
+    abort ();
+  return 0;
+}
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index e02a566..bf75135 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -1642,6 +1642,28 @@  cprop_into_successor_phis (basic_block bb)
       if (gsi_end_p (gsi))
 	continue;
 
+      /* We may have an equivalence associated with this edge.  While
+	 we can not propagate it into non-dominated blocks, we can
+	 propagate them into PHIs in non-dominated blocks.  */
+
+      /* Push the unwind marker so we can reset the const and copies
+	 table back to its original state after processing this edge.  */
+      const_and_copies_stack.safe_push (NULL_TREE);
+
+      /* Extract and record any simple NAME = VALUE equivalences. 
+
+	 Don't bother with [01] = COND equivalences, they're not useful
+	 here.  */
+      struct edge_info *edge_info = (struct edge_info *) e->aux;
+      if (edge_info)
+	{
+	  tree lhs = edge_info->lhs;
+	  tree rhs = edge_info->rhs;
+
+	  if (lhs && TREE_CODE (lhs) == SSA_NAME)
+	    record_const_or_copy (lhs, rhs);
+	}
+
       indx = e->dest_idx;
       for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
 	{
@@ -1667,6 +1689,8 @@  cprop_into_successor_phis (basic_block bb)
 	      && may_propagate_copy (orig_val, new_val))
 	    propagate_value (orig_p, new_val);
 	}
+
+      restore_vars_to_original_value ();
     }
 }
 
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 42474f1..47db280 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -841,28 +841,6 @@  thread_around_empty_blocks (edge taken_edge,
   return false;
 }
       
-/* E1 and E2 are edges into the same basic block.  Return TRUE if the
-   PHI arguments associated with those edges are equal or there are no
-   PHI arguments, otherwise return FALSE.  */
-
-static bool
-phi_args_equal_on_edges (edge e1, edge e2)
-{
-  gimple_stmt_iterator gsi;
-  int indx1 = e1->dest_idx;
-  int indx2 = e2->dest_idx;
-
-  for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
-    {
-      gimple phi = gsi_stmt (gsi);
-
-      if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
-			    gimple_phi_arg_def (phi, indx2), 0))
-	return false;
-    }
-  return true;
-}
-
 /* We are exiting E->src, see if E->dest ends with a conditional
    jump which has a known value when reached via E.
 
@@ -1021,18 +999,9 @@  thread_across_edge (gimple dummy_cond,
 	   record the jump threading opportunity.  */
 	if (found)
 	  {
-	    edge tmp;
-	    /* If there is already an edge from the block to be duplicated
-	       (E2->src) to the final target (E3->dest), then make sure that
-	       the PHI args associated with the edges E2 and E3 are the
-	       same.  */
-	    tmp = find_edge (taken_edge->src, path[path.length () - 1]->dest);
-	    if (!tmp || phi_args_equal_on_edges (tmp, path[path.length () - 1]))
-	      {
-		propagate_threaded_block_debug_into (path[path.length () - 1]->dest,
-						     taken_edge->dest);
-		register_jump_thread (path, true);
-	      }
+	    propagate_threaded_block_debug_into (path[path.length () - 1]->dest,
+						 taken_edge->dest);
+	    register_jump_thread (path, true);
 	  }
 
         path.release();
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index d755266..4131128 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -1147,6 +1147,28 @@  fail:
   return false;
 }
 
+/* E1 and E2 are edges into the same basic block.  Return TRUE if the
+   PHI arguments associated with those edges are equal or there are no
+   PHI arguments, otherwise return FALSE.  */
+
+static bool
+phi_args_equal_on_edges (edge e1, edge e2)
+{
+  gimple_stmt_iterator gsi;
+  int indx1 = e1->dest_idx;
+  int indx2 = e2->dest_idx;
+
+  for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple phi = gsi_stmt (gsi);
+
+      if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
+			    gimple_phi_arg_def (phi, indx2), 0))
+	return false;
+    }
+  return true;
+}
+
 /* Walk through the registered jump threads and convert them into a
    form convenient for this pass.
 
@@ -1219,6 +1241,46 @@  mark_threaded_blocks (bitmap threaded_blocks)
 	}
     }
 
+  /* If we have a joiner block (J) which has two successors S1 and S2 and
+     we are threading though S1 and the final destination of the thread
+     is S2, then we must verify that any PHI nodes in S2 have the same
+     PHI arguments for the edge J->S2 and J->S1->...->S2.
+
+     We used to detect this prior to registering the jump thread, but
+     that prohibits propagation of edge equivalences into non-dominated
+     PHI nodes as the equivalency test might occur before propagation. 
+
+     This works for now, but will need improvement as part of the FSA
+     optimization. 
+
+     Note since we've moved the thread request data to the edges,
+     we have to iterate on those rather than the threaded_edges vector.  */
+  EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
+    {
+      bb = BASIC_BLOCK (i);
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  if (e->aux)
+	    {
+	      bool have_joiner = THREAD_TARGET2 (e) != NULL;
+
+	      if (have_joiner)
+		{
+		  basic_block joiner = e->dest;
+		  edge final_edge = THREAD_TARGET2 (e);
+		  basic_block final_dest = final_edge->dest;
+		  edge e2 = find_edge (joiner, final_dest);
+
+		  if (e2 && !phi_args_equal_on_edges (e2, final_edge))
+		    {
+		      free (e->aux);
+		      e->aux = NULL;
+		    }
+		}
+	    }
+	}
+    }
+
 
   /* If optimizing for size, only thread through block if we don't have
      to duplicate it or it's an otherwise empty redirection block.  */