Fix missed propagation opportunity in DOM

Fix missed propagation opportunity in DOM

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 2114 bytes --]


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.


[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 1723 bytes --]

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8493ee1..1f1f939 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2013-09-06  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-dom.c (cprop_into_successor_phis): Also propagate
+	edge implied equivalences into successor phis.
+
 2013-09-06 Claudiu Zissulescu <claziss@synopsys.com>
 
 	* resource.c (mark_target_live_regs): Compute resources taking
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 691e6f9..f999a64 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 ();
     }
 }
 

Re: Fix missed propagation opportunity in DOM

[Andreas Schwab]

Jeff Law <law@redhat.com> writes:

> +2013-09-06  Jeff Law  <law@redhat.com>
> +
> +	* tree-ssa-dom.c (cprop_into_successor_phis): Also propagate
> +	edge implied equivalences into successor phis.

This is causing bootstrap miscompare (in gcc/compare-elim.o) on ia64.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."