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

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

[Richard Biener]

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.

Thanks,
Richard.

2014-05-08  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.

	* gcc.dg/tree-ssa/ssa-fre-39.c: New testcase.

Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c.orig	2014-05-08 12:22:58.926026518 +0200
--- gcc/tree-ssa-sccvn.c	2014-05-08 13:42:50.646696614 +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-08 13:17:29.916801314 +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" } } */

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

[Richard Biener]

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" } } */

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

[Jeff Law]

On 05/16/14 02:02, Richard Biener wrote:
>>
> Quiet as usual.
Which strongly suggests folks trust you to do the right thing here :-) 
  I think the FRE/PRE reference in $SUBJECT made me ignore the patch 
entirely -- my brain hurts when I look at our tree PRE implementation.

Jeff

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

[Richard Biener]

On May 16, 2014 7:07:11 PM CEST, Jeff Law <law@redhat.com> wrote:
>On 05/16/14 02:02, Richard Biener wrote:
>>>
>> Quiet as usual.
>Which strongly suggests folks trust you to do the right thing here :-) 
>  I think the FRE/PRE reference in $SUBJECT made me ignore the patch 
>entirely -- my brain hurts when I look at our tree PRE implementation.

Heh, it's much easier to understand than it once was!

:)

Richard.

>Jeff