2008-03-14 Richard Guenther <rguenther@suse.de>

	PR tree-optimization/34172
	* tree-flow.h (refs_may_alias_p): Declare.
	(get_single_def_stmt): Likewise.
	(get_single_def_stmt_from_phi): Likewise.
	(get_single_def_stmt_with_phi): Likewise.
	* tree-dfa.c (refs_may_alias_p): New function.
	(get_single_def_stmt): Likewise.
	(get_single_def_stmt_from_phi): Likewise.
	(get_single_def_stmt_with_phi): Likewise.
	* tree-ssa-sccvn.c (get_def_ref_stmt_vuses): New function.
	(vn_reference_lookup_1): New helper function.
	(vn_reference_lookup): Walk the virtual use-def chain to
	continue searching for a match if the def does not alias the
	reference we are looking for.

	* gcc.dg/tree-ssa/ssa-fre-11.c: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-12.c: Likewise.
	* gcc.dg/tree-ssa/ssa-fre-13.c: Likewise.
	* gcc.dg/tree-ssa/ssa-fre-14.c: Likewise.
	* gcc.dg/tree-ssa/ssa-fre-15.c: Likewise.
	* gcc.dg/tree-ssa/20031106-4.c: Remove XFAIL.


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

1 files changed, 162 insertions, 0 deletions

diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c
index 346f6f3803c..349581671a5 100644
--- a/gcc/tree-dfa.c
+++ b/gcc/tree-dfa.c
@@ -1046,3 +1046,165 @@ stmt_references_abnormal_ssa_name (tree stmt)
   return false;
 }
 
+/* Return true, if the two memory references REF1 and REF2 may alias.  */
+
+bool
+refs_may_alias_p (tree ref1, tree ref2)
+{
+  tree base1, base2;
+  HOST_WIDE_INT offset1 = 0, offset2 = 0;
+  HOST_WIDE_INT size1 = -1, size2 = -1;
+  HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
+
+  gcc_assert ((SSA_VAR_P (ref1)
+	       || handled_component_p (ref1)
+	       || TREE_CODE (ref1) == INDIRECT_REF)
+	      && (SSA_VAR_P (ref2)
+		  || handled_component_p (ref2)
+		  || TREE_CODE (ref2) == INDIRECT_REF));
+
+  /* Defer to TBAA if possible.  */
+  if (flag_strict_aliasing
+      && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
+    return false;
+
+  /* Decompose the references into their base objects and the access.  */
+  base1 = ref1;
+  if (handled_component_p (ref1))
+    base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
+  base2 = ref2;
+  if (handled_component_p (ref2))
+    base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
+
+  /* If both references are based on different variables, they cannot alias.
+     If both references are based on the same variable, they cannot alias if
+     if the accesses do not overlap.  */
+  if (SSA_VAR_P (base1)
+      && SSA_VAR_P (base2)
+      && (!operand_equal_p (base1, base2, 0)
+	  || !ranges_overlap_p (offset1, max_size1, offset2, max_size2)))
+    return false;
+
+  /* If both references are through pointers and both pointers are equal
+     then they do not alias if the accesses do not overlap.  */
+  if (TREE_CODE (base1) == INDIRECT_REF
+      && TREE_CODE (base2) == INDIRECT_REF
+      && operand_equal_p (TREE_OPERAND (base1, 0),
+			  TREE_OPERAND (base2, 0), 0)
+      && !ranges_overlap_p (offset1, max_size1, offset2, max_size2))
+    return false;
+
+  return true;
+}
+
+/* Given a stmt STMT that references memory, return the single stmt
+   that is reached by following the VUSE -> VDEF link.  Returns
+   NULL_TREE, if there is no single stmt that defines all VUSEs of
+   STMT.
+   Note that for a stmt with a single virtual operand this may return
+   a PHI node as well.  Note that if all VUSEs are default definitions
+   this function will return an empty statement.  */
+
+tree
+get_single_def_stmt (tree stmt)
+{
+  tree def_stmt = NULL_TREE;
+  tree use;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
+    {
+      tree tmp = SSA_NAME_DEF_STMT (use);
+
+      /* ???  This is too simplistic for multiple virtual operands
+	 reaching different PHI nodes of the same basic blocks or for
+	 reaching all default definitions.  */
+      if (def_stmt
+	  && def_stmt != tmp
+	  && !(IS_EMPTY_STMT (def_stmt)
+	       && IS_EMPTY_STMT (tmp)))
+	return NULL_TREE;
+
+      def_stmt = tmp;
+    }
+
+  return def_stmt;
+}
+
+/* Given a PHI node of virtual operands, tries to eliminate cyclic
+   reached definitions if they do not alias REF and returns the
+   defining statement of the single virtual operand that flows in
+   from a non-backedge.  Returns NULL_TREE if such statement within
+   the above conditions cannot be found.  */
+
+tree
+get_single_def_stmt_from_phi (tree ref, tree phi)
+{
+  tree def_arg = NULL_TREE;
+  int i;
+
+  /* Find the single PHI argument that is not flowing in from a
+     back edge and verify that the loop-carried definitions do
+     not alias the reference we look for.  */
+  for (i = 0; i < PHI_NUM_ARGS (phi); ++i)
+    {
+      tree arg = PHI_ARG_DEF (phi, i);
+      tree def_stmt;
+
+      if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK))
+	{
+	  /* Multiple non-back edges?  Do not try to handle this.  */
+	  if (def_arg)
+	    return NULL_TREE;
+	  def_arg = arg;
+	  continue;
+	}
+
+      /* Follow the definitions back to the original PHI node.  Bail
+	 out once a definition is found that may alias REF.  */
+      def_stmt = SSA_NAME_DEF_STMT (arg);
+      do
+	{
+	  if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
+	      || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
+	    return NULL_TREE;
+	  /* ???  This will only work, reaching the PHI node again if
+	     there is a single virtual operand on def_stmt.  */
+	  def_stmt = get_single_def_stmt (def_stmt);
+	  if (!def_stmt)
+	    return NULL_TREE;
+	}
+      while (def_stmt != phi);
+    }
+
+  return SSA_NAME_DEF_STMT (def_arg);
+}
+
+/* Return the single reference statement defining all virtual uses
+   on STMT or NULL_TREE, if there are multiple defining statements.
+   Take into account only definitions that alias REF if following
+   back-edges when looking through a loop PHI node.  */
+
+tree
+get_single_def_stmt_with_phi (tree ref, tree stmt)
+{
+  switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
+    {
+    case 0:
+      gcc_unreachable ();
+
+    case 1:
+      {
+	tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
+					     (stmt, SSA_OP_VIRTUAL_USES));
+	/* We can handle lookups over PHI nodes only for a single
+	   virtual operand.  */
+	if (TREE_CODE (def_stmt) == PHI_NODE)
+	  return get_single_def_stmt_from_phi (ref, def_stmt);
+	return def_stmt;
+      }
+
+    default:
+      return get_single_def_stmt (stmt);
+    }
+}