Re: [PATCH][1/n][RFC] Make FRE/PRE somewhat predicate aware

[Richard Biener <rguenther at suse dot de>]

On Thu, 8 May 2014, Richard Biener wrote:

> 
> Ok, not really predicate aware, but this makes value-numbering
> pessimistically handle non-executable edges.  In the following
> patch groundwork is laid and PHI value-numbering is adjusted
> to take advantage of edges known to be not executable.
> 
> SCCVN is not well-suited to be control aware, but we still
> can see if value-numbering allows us to mark edges as
> not executable by looking at control statements.  Value-numbering
> of PHI nodes is one obvious consumer of such information
> and it also gives a natural order to do that (pessimistic)
> edge executability computation - dominator order.
> 
> Thus the following adds a pass over all control statements,
> trying to simplify them after value-numbering their operands
> (and all uses recursively, as SCCVN does).
> 
> With followup patches I will try to use this information to
> reduce the amount of work done (also improving optimization,
> of course).  One other obvious candidate is the alias walker
> which doesn't have to consider unreachable paths when
> walking into virtual PHIs.
> 
> The patch will likely get some more cleanups (due to the hack
> in set_ssa_val_to).
> 
> Comments still welcome.

Quiet as usual.  Well, the following is what I have committed
after bootstrapping and regtesting on x86_64-unknown-linux-gnu.
It fixes the inliner which is confused by random pass-local
flags on the edges to the exit block, adds one more testcase
and adjusts two.

I figured that followups for more optimizations are not
necessary as virtual operand value-numbering already gets
us most of the benefit.  Followups trying to do less work
may still be possible but they are low on priority.

Richard.

2014-05-16  Richard Biener  <rguenther@suse.de>

	* tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h.
	(set_ssa_val_to): Handle unexpected sets to VN_TOP.
	(visit_phi): Ignore edges marked as not executable.
	(class cond_dom_walker): New.
	(cond_dom_walker::before_dom_children): Value-number
	control statements and mark successor edges as not
	executable if possible.
	(run_scc_vn): First walk all control statements in
	dominator order, marking edges as not executable.
	* tree-inline.c (copy_edges_for_bb): Be not confused
	about random edge flags.

	* gcc.dg/tree-ssa/ssa-fre-39.c: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-40.c: Likewise.
	* gcc.dg/tree-ssa/ssa-pre-8.c: One more elimination.
	* gcc.dg/tree-ssa/struct-aliasing-2.c: Scan cddce1 dump.

Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c.orig	2014-05-15 12:47:20.762286122 +0200
--- gcc/tree-ssa-sccvn.c	2014-05-15 13:04:57.872213342 +0200
*************** along with GCC; see the file COPYING3.
*** 51,56 ****
--- 51,58 ----
  #include "params.h"
  #include "tree-ssa-propagate.h"
  #include "tree-ssa-sccvn.h"
+ #include "tree-cfg.h"
+ #include "domwalk.h"
  
  /* This algorithm is based on the SCC algorithm presented by Keith
     Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
*************** set_ssa_val_to (tree from, tree to)
*** 2661,2666 ****
--- 2663,2687 ----
    tree currval = SSA_VAL (from);
    HOST_WIDE_INT toff, coff;
  
+   /* The only thing we allow as value numbers are ssa_names
+      and invariants.  So assert that here.  We don't allow VN_TOP
+      as visiting a stmt should produce a value-number other than
+      that.
+      ???  Still VN_TOP can happen for unreachable code, so force
+      it to varying in that case.  Not all code is prepared to
+      get VN_TOP on valueization.  */
+   if (to == VN_TOP)
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, "Forcing value number to varying on "
+ 		 "receiving VN_TOP\n");
+       to = from;
+     }
+ 
+   gcc_assert (to != NULL_TREE
+ 	      && (TREE_CODE (to) == SSA_NAME
+ 		  || is_gimple_min_invariant (to)));
+ 
    if (from != to)
      {
        if (currval == from)
*************** set_ssa_val_to (tree from, tree to)
*** 2680,2692 ****
  	to = from;
      }
  
-   /* The only thing we allow as value numbers are VN_TOP, ssa_names
-      and invariants.  So assert that here.  */
-   gcc_assert (to != NULL_TREE
- 	      && (to == VN_TOP
- 		  || TREE_CODE (to) == SSA_NAME
- 		  || is_gimple_min_invariant (to)));
- 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "Setting value number of ");
--- 2701,2706 ----
*************** visit_phi (gimple phi)
*** 3071,3077 ****
    tree result;
    tree sameval = VN_TOP;
    bool allsame = true;
-   unsigned i;
  
    /* TODO: We could check for this in init_sccvn, and replace this
       with a gcc_assert.  */
--- 3085,3090 ----
*************** visit_phi (gimple phi)
*** 3080,3106 ****
  
    /* See if all non-TOP arguments have the same value.  TOP is
       equivalent to everything, so we can ignore it.  */
!   for (i = 0; i < gimple_phi_num_args (phi); i++)
!     {
!       tree def = PHI_ARG_DEF (phi, i);
  
!       if (TREE_CODE (def) == SSA_NAME)
! 	def = SSA_VAL (def);
!       if (def == VN_TOP)
! 	continue;
!       if (sameval == VN_TOP)
! 	{
! 	  sameval = def;
! 	}
!       else
! 	{
! 	  if (!expressions_equal_p (def, sameval))
! 	    {
! 	      allsame = false;
! 	      break;
! 	    }
! 	}
!     }
  
    /* If all value numbered to the same value, the phi node has that
       value.  */
--- 3093,3122 ----
  
    /* See if all non-TOP arguments have the same value.  TOP is
       equivalent to everything, so we can ignore it.  */
!   edge_iterator ei;
!   edge e;
!   FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
!     if (e->flags & EDGE_EXECUTABLE)
!       {
! 	tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
  
! 	if (TREE_CODE (def) == SSA_NAME)
! 	  def = SSA_VAL (def);
! 	if (def == VN_TOP)
! 	  continue;
! 	if (sameval == VN_TOP)
! 	  {
! 	    sameval = def;
! 	  }
! 	else
! 	  {
! 	    if (!expressions_equal_p (def, sameval))
! 	      {
! 		allsame = false;
! 		break;
! 	      }
! 	  }
!       }
  
    /* If all value numbered to the same value, the phi node has that
       value.  */
*************** set_hashtable_value_ids (void)
*** 4098,4103 ****
--- 4114,4218 ----
      set_value_id_for_result (vr->result, &vr->value_id);
  }
  
+ class cond_dom_walker : public dom_walker
+ {
+ public:
+   cond_dom_walker () : dom_walker (CDI_DOMINATORS), fail (false) {}
+ 
+   virtual void before_dom_children (basic_block);
+ 
+   bool fail;
+ };
+ 
+ void
+ cond_dom_walker::before_dom_children (basic_block bb)
+ {
+   edge e;
+   edge_iterator ei;
+ 
+   if (fail)
+     return;
+ 
+   /* If any of the predecessor edges are still marked as possibly
+      executable consider this block reachable.  */
+   bool reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun);
+   FOR_EACH_EDGE (e, ei, bb->preds)
+     reachable |= (e->flags & EDGE_EXECUTABLE);
+ 
+   /* If the block is not reachable all outgoing edges are not
+      executable.  */
+   if (!reachable)
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, "Marking all outgoing edges of unreachable "
+ 		 "BB %d as not executable\n", bb->index);
+ 
+       FOR_EACH_EDGE (e, ei, bb->succs)
+ 	e->flags &= ~EDGE_EXECUTABLE;
+       return;
+     }
+ 
+   gimple stmt = last_stmt (bb);
+   if (!stmt)
+     return;
+ 
+   /* Value-number the last stmts SSA uses.  */
+   ssa_op_iter i;
+   tree op;
+   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
+     if (VN_INFO (op)->visited == false
+ 	&& !DFS (op))
+       {
+ 	fail = true;
+ 	return;
+       }
+ 
+   /* ???  We can even handle stmts with outgoing EH or ABNORMAL edges
+      if value-numbering can prove they are not reachable.  Handling
+      computed gotos is also possible.  */
+   tree val;
+   switch (gimple_code (stmt))
+     {
+     case GIMPLE_COND:
+       {
+ 	tree lhs = gimple_cond_lhs (stmt);
+ 	tree rhs = gimple_cond_rhs (stmt);
+ 	/* Work hard in computing the condition and take into account
+ 	   the valueization of the defining stmt.  */
+ 	if (TREE_CODE (lhs) == SSA_NAME)
+ 	  lhs = vn_get_expr_for (lhs);
+ 	if (TREE_CODE (rhs) == SSA_NAME)
+ 	  rhs = vn_get_expr_for (rhs);
+ 	val = fold_binary (gimple_cond_code (stmt),
+ 			   boolean_type_node, lhs, rhs);
+ 	break;
+       }
+     case GIMPLE_SWITCH:
+       val = gimple_switch_index (stmt);
+       break;
+     case GIMPLE_GOTO:
+       val = gimple_goto_dest (stmt);
+       break;
+     default:
+       val = NULL_TREE;
+       break;
+     }
+   if (!val)
+     return;
+ 
+   edge taken = find_taken_edge (bb, vn_valueize (val));
+   if (!taken)
+     return;
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as "
+ 	     "not executable\n", bb->index, bb->index, taken->dest->index);
+ 
+   FOR_EACH_EDGE (e, ei, bb->succs)
+     if (e != taken)
+       e->flags &= ~EDGE_EXECUTABLE;
+ }
+ 
  /* Do SCCVN.  Returns true if it finished, false if we bailed out
     due to resource constraints.  DEFAULT_VN_WALK_KIND_ specifies
     how we use the alias oracle walking during the VN process.  */
*************** set_hashtable_value_ids (void)
*** 4105,4110 ****
--- 4220,4226 ----
  bool
  run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
  {
+   basic_block bb;
    size_t i;
    tree param;
  
*************** run_scc_vn (vn_lookup_kind default_vn_wa
*** 4122,4127 ****
--- 4238,4263 ----
  	VN_INFO (def)->valnum = def;
      }
  
+   /* Mark all edges as possibly executable.  */
+   FOR_ALL_BB_FN (bb, cfun)
+     {
+       edge_iterator ei;
+       edge e;
+       FOR_EACH_EDGE (e, ei, bb->succs)
+ 	e->flags |= EDGE_EXECUTABLE;
+     }
+ 
+   /* Walk all blocks in dominator order, value-numbering the last stmts
+      SSA uses and decide whether outgoing edges are not executable.  */
+   cond_dom_walker walker;
+   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+   if (walker.fail)
+     {
+       free_scc_vn ();
+       return false;
+     }
+ 
+   /* Value-number remaining SSA names.  */
    for (i = 1; i < num_ssa_names; ++i)
      {
        tree name = ssa_name (i);
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c	2014-05-15 13:04:57.872213342 +0200
***************
*** 0 ****
--- 1,19 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre1" } */
+ 
+ int foo (int i)
+ {
+   int k = i + 1;
+   int j = i + 1;
+   if (k != j)
+     k = k + 1;
+   if (k != j)
+     k = k + 1;
+   k = k - i;
+   return k;
+ }
+ 
+ /* We should be able to value-number the final assignment to k to 1.  */
+ 
+ /* { dg-final { scan-tree-dump "k_. = 1;" "fre1" } } */
+ /* { dg-final { cleanup-tree-dump "fre1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c.orig	2014-05-15 12:47:20.762286122 +0200
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c	2014-05-15 13:04:57.873213341 +0200
*************** foo (__SIZE_TYPE__ i, struct s *array)
*** 17,23 ****
    return 0;
  }
  /* We should eliminate two address calculations, and one load.  */
  /* We used to eliminate a cast but that was before POINTER_PLUS_EXPR
     was added.  */
! /* { dg-final { scan-tree-dump-times "Eliminated: 3" 1 "fre1"} } */
  /* { dg-final { cleanup-tree-dump "fre1" } } */
--- 17,25 ----
    return 0;
  }
  /* We should eliminate two address calculations, and one load.  */
+ /* We also elimiate the PHI node feeding the return because the case
+    returning 1 is unreachable.  */
  /* We used to eliminate a cast but that was before POINTER_PLUS_EXPR
     was added.  */
! /* { dg-final { scan-tree-dump-times "Eliminated: 4" 1 "fre1"} } */
  /* { dg-final { cleanup-tree-dump "fre1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c.orig	2014-05-15 12:47:20.762286122 +0200
--- gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c	2014-05-15 13:04:57.873213341 +0200
***************
*** 1,5 ****
  /* { dg-do compile } */
! /* { dg-options "-O2 -fdump-tree-fre1" } */
  
  struct S { unsigned f; };
  
--- 1,5 ----
  /* { dg-do compile } */
! /* { dg-options "-O2 -fdump-tree-cddce1" } */
  
  struct S { unsigned f; };
  
*************** foo ( struct S *p)
*** 12,19 ****
  }
  
  
! /* There should only be one load of p->f because fwprop can change
!    *(int *)&p->f into just (int)p->f.  */
! /* { dg-final { scan-tree-dump-times "= \[^\n\]*p_.\\\(D\\\)" 1 "fre1" } } */
! /* { dg-final { cleanup-tree-dump "fre1" } } */
  
--- 12,19 ----
  }
  
  
! /* There should only be one load of p->f because FRE removes the redundancy
!    by realizing it can cast the result of either to the other.  */
! /* { dg-final { scan-tree-dump-times "= \[^\n\]*p_.\\\(D\\\)" 1 "cddce1" } } */
! /* { dg-final { cleanup-tree-dump "cddce1" } } */
  
Index: gcc/tree-inline.c
===================================================================
*** gcc/tree-inline.c.orig	2014-05-15 12:47:20.762286122 +0200
--- gcc/tree-inline.c	2014-05-15 13:04:57.888213340 +0200
*************** copy_edges_for_bb (basic_block bb, gcov_
*** 1988,1994 ****
  	flags = old_edge->flags;
  
  	/* Return edges do get a FALLTHRU flag when the get inlined.  */
! 	if (old_edge->dest->index == EXIT_BLOCK && !old_edge->flags
  	    && old_edge->dest->aux != EXIT_BLOCK_PTR_FOR_FN (cfun))
  	  flags |= EDGE_FALLTHRU;
  	new_edge = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags);
--- 1988,1995 ----
  	flags = old_edge->flags;
  
  	/* Return edges do get a FALLTHRU flag when the get inlined.  */
! 	if (old_edge->dest->index == EXIT_BLOCK
! 	    && !(old_edge->flags & (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE|EDGE_FAKE))
  	    && old_edge->dest->aux != EXIT_BLOCK_PTR_FOR_FN (cfun))
  	  flags |= EDGE_FALLTHRU;
  	new_edge = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags);
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c	2014-05-15 13:38:20.317075476 +0200
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre1" } */
+ 
+ int x;
+ int foo (int *p)
+ {
+   x = 0;
+   if (x)
+     *p = 1;
+   return x;
+ }
+ 
+ /* The final load of x should be replaced as well as the
+    aliasing store via *p is not reachable.  */
+ 
+ /* { dg-final { scan-tree-dump-not "= x;" "fre1" } } */