2007-04-18 Richard Guenther <rguenther@suse.de>

	PR tree-optimization/19431
	PR tree-optimization/21463
	* tree-pass.h (pass_phiprop): Declare.
	* passes.c (init_optimization_passes): New phiprop pass.
	* tree-ssa-forwprop.c (struct phiprop_d): New structure.
	(phivn_valid_p): New helper function.
	(phiprop_insert_phi): Likewise.
	(propagate_with_phi): Likewise.
	(tree_ssa_phiprop): New propagator propagating loads
	through phi nodes if profitable.

	* gcc.c-torture/execute/20070212-1.c: New testcase.
	* gcc.c-torture/execute/20070212-2.c: Likewise.
	* gcc.c-torture/execute/20070212-3.c: Likewise.
	* gcc.dg/tree-ssa/pr19431.c: Likewise.
	* gcc.dg/tree-ssa/pr21463.c: Likewise.
	* g++.dg/tree-ssa/pr21463.C: Likewise.
	* g++.dg/tree-ssa/pr30738.C: Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@123946 138bc75d-0d04-0410-961f-82ee72b054a4

12 files changed, 487 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0c19d7ea14b..fdde4316d49 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2007-04-18  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/19431
+	PR tree-optimization/21463
+	* tree-pass.h (pass_phiprop): Declare.
+	* passes.c (init_optimization_passes): New phiprop pass.
+	* tree-ssa-forwprop.c (struct phiprop_d): New structure.
+	(phivn_valid_p): New helper function.
+	(phiprop_insert_phi): Likewise.
+	(propagate_with_phi): Likewise.
+	(tree_ssa_phiprop): New propagator propagating loads
+	through phi nodes if profitable.
+
 2007-04-18  Dorit Nuzman  <dorit@il.ibm.com>
 
 	* tree-vect-analyze.c (process_use): New function.
diff --git a/gcc/passes.c b/gcc/passes.c
index a0b4aa4b875..11b11981fdd 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -524,6 +524,7 @@ init_optimization_passes (void)
 
       /* Initial scalar cleanups.  */
       NEXT_PASS (pass_ccp);
+      NEXT_PASS (pass_phiprop);
       NEXT_PASS (pass_fre);
       NEXT_PASS (pass_dce);
       NEXT_PASS (pass_forwprop);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index fe20b61b743..bcea2252ec5 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,15 @@
+2007-04-18  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/19431
+	PR tree-optimization/21463
+	* gcc.c-torture/execute/20070212-1.c: New testcase.
+	* gcc.c-torture/execute/20070212-2.c: Likewise.
+	* gcc.c-torture/execute/20070212-3.c: Likewise.
+	* gcc.dg/tree-ssa/pr19431.c: Likewise.
+	* gcc.dg/tree-ssa/pr21463.c: Likewise.
+	* g++.dg/tree-ssa/pr21463.C: Likewise.
+	* g++.dg/tree-ssa/pr30738.C: Likewise.
+
 2007-04-17  Mark Mitchell  <mark@codesourcery.com>
 
 	PR c++/31513
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr21463.C b/gcc/testsuite/g++.dg/tree-ssa/pr21463.C
new file mode 100644
index 00000000000..6d6ee93ba44
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr21463.C
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-phiopt1" } */
+
+template<class T> static inline const T &ref_max(const T &a, const T &b)
+{ return a<b ? b : a; }
+template<class T> static inline const T &ref_min(const T &a, const T &b)
+{ return a<b ? a : b; }
+
+template<class T> struct foo_t {
+	T a0, a1;
+	T bar_ref(const T b, const T c) {
+		return ref_max(ref_min(a0, c), ref_min(ref_max(a1, c), b));
+	}
+};
+
+template struct foo_t<int>;
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "phiopt1" } } */
+/* { dg-final { cleanup-tree-dump "phiopt1" } } */
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr30738.C b/gcc/testsuite/g++.dg/tree-ssa/pr30738.C
new file mode 100644
index 00000000000..b9d735e814d
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr30738.C
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-phiopt1" } */
+
+template <class T>
+static inline const T&
+min_ref (const T &x, const T &y)
+{
+  return x < y ? x : y;
+}
+
+int test_min_ref (int x, int y)
+{
+  return min_ref (x, y);
+}
+
+/* { dg-final { scan-tree-dump "MIN_EXPR" "phiopt1" } } */
+/* { dg-final { cleanup-tree-dump "phiopt1" } } */
diff --git a/gcc/testsuite/gcc.c-torture/execute/20070212-1.c b/gcc/testsuite/gcc.c-torture/execute/20070212-1.c
new file mode 100644
index 00000000000..efda7f9cf66
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/20070212-1.c
@@ -0,0 +1,26 @@
+struct f
+{
+  int i;
+};
+
+int g(int i, int c, struct f *ff, int *p)
+{
+  int *t;
+  if (c)
+   t = &i;
+  else
+   t = &ff->i;
+  *p = 0;
+  return *t;
+}
+
+extern void abort(void);
+
+int main()
+{
+  struct f f;
+  f.i = 1;
+  if (g(5, 0, &f, &f.i) != 0)
+    abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.c-torture/execute/20070212-2.c b/gcc/testsuite/gcc.c-torture/execute/20070212-2.c
new file mode 100644
index 00000000000..a107d0efb93
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/20070212-2.c
@@ -0,0 +1,19 @@
+int f(int k, int i1, int j1)
+{
+  int *f1;
+  if(k)
+   f1 = &i1;
+  else
+   f1 = &j1;
+  i1 = 0;
+  return *f1;
+}
+
+extern void abort (void);
+
+int main()
+{
+  if (f(1, 1, 2) != 0)
+    abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.c-torture/execute/20070212-3.c b/gcc/testsuite/gcc.c-torture/execute/20070212-3.c
new file mode 100644
index 00000000000..174be2bd90a
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/20070212-3.c
@@ -0,0 +1,30 @@
+struct foo { int i; int j; };
+
+int bar (struct foo *k, int k2, int f, int f2)
+{
+  int *p, *q;
+  int res;
+  if (f)
+    p = &k->i;
+  else
+    p = &k->j;
+  res = *p;
+  k->i = 1;
+  if (f2)
+    q = p;
+  else
+    q = &k2;
+  return res + *q;
+}
+
+extern void abort (void);
+
+int main()
+{
+  struct foo k;
+  k.i = 0;
+  k.j = 1;
+  if (bar (&k, 1, 1, 1) != 1)
+    abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c b/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c
new file mode 100644
index 00000000000..4334648ce64
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* We want this optimized as
+<bb 2>:
+  if (k != 0) goto <L2>; else goto <L3>;
+
+<L3>:;
+  i1 = j1;
+
+<L2>:;
+  return i1;
+
+  This requires that i1 and j1 are changed into registers after they
+  no longer have their address taken.  */
+
+int f(int k, int i1, int j1)
+{
+  int *f1;
+  if(k)
+   f1 = &i1;
+  else
+   f1 = &j1;
+  return *f1;
+}
+
+/* { dg-final { scan-tree-dump "i1 = j1" "optimized" } } */
+/* { dg-final { scan-tree-dump "return i1;" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c
new file mode 100644
index 00000000000..f490bf61e5a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-phiprop" } */
+
+struct f
+{
+  int i;
+};
+
+int g(int i, int c, struct f *ff, int g)
+{
+  int *t;
+  if (c)
+    t = &i;
+  else
+    t = &ff->i;
+  return *t;
+}
+
+/* { dg-final { scan-tree-dump-not "\\*t" "phiprop" } } */
+/* { dg-final { cleanup-tree-dump "phiprop" } } */
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index ed4fb470dfe..1b92f8c9807 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -285,6 +285,7 @@ extern struct tree_opt_pass pass_warn_function_return;
 extern struct tree_opt_pass pass_warn_function_noreturn;
 extern struct tree_opt_pass pass_phiopt;
 extern struct tree_opt_pass pass_forwprop;
+extern struct tree_opt_pass pass_phiprop;
 extern struct tree_opt_pass pass_dse;
 extern struct tree_opt_pass pass_nrv;
 extern struct tree_opt_pass pass_mark_used_blocks;
diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c
index 95a0c91a1de..4e7f19f62c8 100644
--- a/gcc/tree-ssa-forwprop.c
+++ b/gcc/tree-ssa-forwprop.c
@@ -1059,3 +1059,302 @@ struct tree_opt_pass pass_forwprop = {
   | TODO_verify_ssa,		/* todo_flags_finish */
   0				/* letter */
 };
+
+
+/* Structure to keep track of the value of a dereferenced PHI result
+   and the set of virtual operands used for that dereference.  */
+
+struct phiprop_d
+{
+  tree value;
+  tree vop_stmt;
+};
+
+/* Verify if the value recorded for NAME in PHIVN is still valid at
+   the start of basic block BB.  */
+
+static bool
+phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb)
+{
+  tree vop_stmt = phivn[SSA_NAME_VERSION (name)].vop_stmt;
+  ssa_op_iter ui;
+  tree vuse;
+
+  /* The def stmts of all virtual uses need to be post-dominated
+     by bb.  */
+  FOR_EACH_SSA_TREE_OPERAND (vuse, vop_stmt, ui, SSA_OP_VUSE)
+    {
+      tree use_stmt;
+      imm_use_iterator ui2;
+      bool ok = true;
+
+      FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse)
+	{
+	  /* If BB does not dominate a VDEF, the value is invalid.  */
+	  if (((TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
+	        && !ZERO_SSA_OPERANDS (use_stmt, SSA_OP_VDEF))
+	       || TREE_CODE (use_stmt) == PHI_NODE)
+	      && !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (use_stmt), bb))
+	    {
+	      ok = false;
+	      BREAK_FROM_IMM_USE_STMT (ui2);
+	    }
+	}
+      if (!ok)
+	return false;
+    }
+
+  return true;
+}
+
+/* Insert a new phi node for the dereference of PHI at basic_block
+   BB with the virtual operands from USE_STMT.  */
+
+static tree
+phiprop_insert_phi (basic_block bb, tree phi, tree use_stmt,
+		    struct phiprop_d *phivn, size_t n)
+{
+  tree res, new_phi;
+  edge_iterator ei;
+  edge e;
+
+  /* Build a new PHI node to replace the definition of
+     the indirect reference lhs.  */
+  res = GIMPLE_STMT_OPERAND (use_stmt, 0);
+  SSA_NAME_DEF_STMT (res) = new_phi = create_phi_node (res, bb);
+
+  /* Add PHI arguments for each edge inserting loads of the
+     addressable operands.  */
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      tree old_arg, new_var, tmp;
+
+      old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+      while (TREE_CODE (old_arg) == SSA_NAME
+	     && (SSA_NAME_VERSION (old_arg) >= n
+	         || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE))
+	{
+	  tree def_stmt = SSA_NAME_DEF_STMT (old_arg);
+	  old_arg = GIMPLE_STMT_OPERAND (def_stmt, 1);
+	}
+
+      if (TREE_CODE (old_arg) == SSA_NAME)
+	/* Reuse a formely created dereference.  */
+	new_var = phivn[SSA_NAME_VERSION (old_arg)].value;
+      else
+	{
+	  old_arg = TREE_OPERAND (old_arg, 0);
+	  new_var = create_tmp_var (TREE_TYPE (old_arg), NULL);
+	  tmp = build2 (GIMPLE_MODIFY_STMT, void_type_node,
+			NULL_TREE, unshare_expr (old_arg));
+	  if (TREE_CODE (TREE_TYPE (old_arg)) == COMPLEX_TYPE
+	      || TREE_CODE (TREE_TYPE (old_arg)) == VECTOR_TYPE)
+	    DECL_GIMPLE_REG_P (new_var) = 1;
+	  add_referenced_var (new_var);
+	  new_var = make_ssa_name (new_var, tmp);
+	  GIMPLE_STMT_OPERAND (tmp, 0) = new_var;
+
+	  bsi_insert_on_edge (e, tmp);
+
+	  update_stmt (tmp);
+	  mark_symbols_for_renaming (tmp);
+	}
+
+      add_phi_arg (new_phi, new_var, e);
+    }
+
+  update_stmt (new_phi);
+
+  return res;
+}
+
+/* Propagate between the phi node arguments of PHI in BB and phi result
+   users.  For now this matches
+        # p_2 = PHI <&x, &y>
+      <Lx>:;
+	p_3 = p_2;
+	z_2 = *p_3;
+   and converts it to
+	# z_2 = PHI <x, y>
+      <Lx>:;
+   Returns true if a transformation was done and edge insertions
+   need to be committed.  Global data PHIVN and N is used to track
+   past transformation results.  We need to be especially careful here
+   with aliasing issues as we are moving memory reads.  */
+
+static bool
+propagate_with_phi (basic_block bb, tree phi, struct phiprop_d *phivn, size_t n)
+{
+  tree ptr = PHI_RESULT (phi);
+  tree use_stmt, res = NULL_TREE;
+  block_stmt_iterator bsi;
+  imm_use_iterator ui;
+  use_operand_p arg_p, use;
+  ssa_op_iter i;
+  bool phi_inserted;
+
+  if (MTAG_P (SSA_NAME_VAR (ptr))
+      || !POINTER_TYPE_P (TREE_TYPE (ptr))
+      || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr))))
+    return false;
+
+  /* Check if we can "cheaply" dereference all phi arguments.  */
+  FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
+    {
+      tree arg = USE_FROM_PTR (arg_p);
+      /* Walk the ssa chain until we reach a ssa name we already
+	 created a value for or we reach a definition of the form
+	 ssa_name_n = &var;  */
+      while (TREE_CODE (arg) == SSA_NAME
+	     && !SSA_NAME_IS_DEFAULT_DEF (arg)
+	     && (SSA_NAME_VERSION (arg) >= n
+	         || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))
+	{
+	  tree def_stmt = SSA_NAME_DEF_STMT (arg);
+	  if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
+	    return false;
+	  arg = GIMPLE_STMT_OPERAND (def_stmt, 1);
+	}
+      if ((TREE_CODE (arg) != ADDR_EXPR
+	   /* Avoid to have to decay *&a to a[0] later.  */
+	   || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg, 0))))
+	  && !(TREE_CODE (arg) == SSA_NAME
+	       && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE
+	       && phivn_valid_p (phivn, arg, bb)))
+	return false;
+    }
+
+  /* Find a dereferencing use.  First follow (single use) ssa
+     copy chains for ptr.  */
+  while (single_imm_use (ptr, &use, &use_stmt)
+	 && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
+	 && GIMPLE_STMT_OPERAND (use_stmt, 1) == ptr
+	 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME)
+    ptr = GIMPLE_STMT_OPERAND (use_stmt, 0);
+
+  /* Replace the first dereference of *ptr if there is one and if we
+     can move the loads to the place of the ptr phi node.  */
+  phi_inserted = false;
+  FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
+    {
+      ssa_op_iter ui2;
+      tree vuse;
+
+      /* Check whether this is a load of *ptr.  */
+      if (!(TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
+	    && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME 
+	    && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == INDIRECT_REF
+	    && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0) == ptr
+	    /* We cannot replace a load that may throw or is volatile.  */
+	    && !tree_can_throw_internal (use_stmt)))
+	continue;
+
+      /* Check if we can move the loads.  The def stmts of all virtual uses
+	 need to be post-dominated by bb.  */
+      FOR_EACH_SSA_TREE_OPERAND (vuse, use_stmt, ui2, SSA_OP_VUSE)
+	{
+	  tree def_stmt = SSA_NAME_DEF_STMT (vuse);
+	  if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
+	      && (bb_for_stmt (def_stmt) == bb
+		  || !dominated_by_p (CDI_DOMINATORS,
+				      bb, bb_for_stmt (def_stmt))))
+	    goto next;
+	}
+
+      /* Found a proper dereference.  Insert a phi node if this
+	 is the first load transformation.  */
+      if (!phi_inserted)
+	{
+	  res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
+
+	  /* Remember the value we created for *ptr.  */
+	  phivn[SSA_NAME_VERSION (ptr)].value = res;
+	  phivn[SSA_NAME_VERSION (ptr)].vop_stmt = use_stmt;
+
+	  /* Remove old stmt.  The phi is taken care of by DCE, if we
+	     want to delete it here we also have to delete all intermediate
+	     copies.  */
+	  bsi = bsi_for_stmt (use_stmt);
+	  bsi_remove (&bsi, 0);
+
+	  phi_inserted = true;
+	}
+      else
+	{
+	  /* Further replacements are easy, just make a copy out of the
+	     load.  */
+	  GIMPLE_STMT_OPERAND (use_stmt, 1) = res;
+	  update_stmt (use_stmt);
+	}
+
+next:;
+      /* Continue searching for a proper dereference.  */
+    }
+
+  return phi_inserted;
+}
+
+/* Helper walking the dominator tree starting from BB and processing
+   phi nodes with global data PHIVN and N.  */
+
+static bool
+tree_ssa_phiprop_1 (basic_block bb, struct phiprop_d *phivn, size_t n)
+{
+  bool did_something = false; 
+  basic_block son;
+  tree phi;
+
+  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+    did_something |= propagate_with_phi (bb, phi, phivn, n);
+
+  for (son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    did_something |= tree_ssa_phiprop_1 (son, phivn, n);
+
+  return did_something;
+}
+
+/* Main entry for phiprop pass.  */
+
+static unsigned int
+tree_ssa_phiprop (void)
+{
+  struct phiprop_d *phivn;
+
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  phivn = XCNEWVEC (struct phiprop_d, num_ssa_names);
+
+  if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR, phivn, num_ssa_names))
+    bsi_commit_edge_inserts ();
+
+  free (phivn);
+
+  return 0;
+}
+
+static bool
+gate_phiprop (void)
+{
+  return 1;
+}
+
+struct tree_opt_pass pass_phiprop = {
+  "phiprop",			/* name */
+  gate_phiprop,			/* gate */
+  tree_ssa_phiprop,		/* execute */
+  NULL,				/* sub */
+  NULL,				/* next */
+  0,				/* static_pass_number */
+  TV_TREE_FORWPROP,		/* tv_id */
+  PROP_cfg | PROP_ssa,		/* properties_required */
+  0,				/* properties_provided */
+  0,				/* properties_destroyed */
+  0,				/* todo_flags_start */
+  TODO_dump_func
+  | TODO_ggc_collect
+  | TODO_update_ssa
+  | TODO_verify_ssa,		/* todo_flags_finish */
+  0				/* letter */
+};