re PR tree-optimization/34043 (Missed optimization causing extra loads and stores when using x86_64 builtin function together with aggregate types.)

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

	PR tree-optimization/34043
	PR tree-optimization/33989
	* tree-ssa-pre.c (execute_pre): Allow SCCVN to do insertion
	when doing FRE.
	(bitmap_find_leader): Use extra argument to verify dominance
	relationship inside a basic-block.
	(can_PRE_operation): Add VIEW_CONVERT_EXPR.
	(find_leader_in_sets): Adjust.
	(create_component_ref_by_pieces): Take extra argument for
	dominance check, handle lookup failures.
	(find_or_generate_expression): Likewise.
	(create_expression_by_pieces): Likewise.
	(insert_into_preds_of_block): Adjust.
	(create_value_expr_from): If asked for, verify all operands
	are in the blocks AVAIL_OUT set.
	(make_values_for_stmt): Check for SSA_NAMEs that are life
	over an abnormal edge.
	(compute_avail): Remove such check.
	(do_SCCVN_insertion): New function.
	(eliminate): If we do not find a leader suitable for replacement
	insert a replacement expression from SCCVN if available.
	* tree-ssa-sccvn.h (run_scc_vn): Update prototype.
	(struct vn_ssa_aux): Add needs_insertion flag.
	* tree-ssa-sccvn.c (may_insert): New global flag.
	(copy_reference_ops_from_ref): Value-number union member access
	based on its size, not type and member if insertion is allowed.
	(visit_reference_op_load): For a weak match from union type
	punning lookup a view-converted value and insert a SSA_NAME
	for that value if that is not found.
	(visit_use): Make dumps shorter.  Do not disallow value numbering
	SSA_NAMEs that are life over an abnormal edge to constants.
	(free_scc_vn): Release inserted SSA_NAMEs.
	(run_scc_vn): New flag to specify whether insertion is allowed.
	Process SSA_NAMEs in forward order.
	* tree-ssa-loop-im.c (for_each_index): Handle invariant
	ADDR_EXPRs inside VIEW_CONVERT_EXPR.
	* fold-const.c (fold_unary): Fold VIEW_CONVERT_EXPRs from/to
	pointer type to/from integral types that do not change the
	precision to regular conversions.

	* gcc.dg/tree-ssa/ssa-fre-7.c: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-8.c: Likewise.
	* gcc.dg/tree-ssa/ssa-fre-9.c: Likewise.
	* gcc.dg/tree-ssa/ssa-fre-10.c: Likewise.
	* gcc.dg/tree-ssa/ssa-pre-17.c: Likewise.

From-SVN: r133218

1 files changed, 150 insertions, 46 deletions

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 4f2bc76..9a5fa44 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -376,15 +376,15 @@ static struct
 } pre_stats;
 
 static bool do_partial_partial;
-static tree bitmap_find_leader (bitmap_set_t, tree);
+static tree bitmap_find_leader (bitmap_set_t, tree, tree);
 static void bitmap_value_insert_into_set (bitmap_set_t, tree);
 static void bitmap_value_replace_in_set (bitmap_set_t, tree);
 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
 static bool bitmap_set_contains_value (bitmap_set_t, tree);
 static void bitmap_insert_into_set (bitmap_set_t, tree);
 static bitmap_set_t bitmap_set_new (void);
-static tree create_expression_by_pieces (basic_block, tree, tree);
-static tree find_or_generate_expression (basic_block, tree, tree);
+static tree create_expression_by_pieces (basic_block, tree, tree, tree);
+static tree find_or_generate_expression (basic_block, tree, tree, tree);
 
 /* We can add and remove elements and entries to and from sets
    and hash tables, so we use alloc pools for them.  */
@@ -954,9 +954,9 @@ find_leader_in_sets (tree expr, bitmap_set_t set1, bitmap_set_t set2)
 {
   tree result;
 
-  result = bitmap_find_leader (set1, expr);
+  result = bitmap_find_leader (set1, expr, NULL_TREE);
   if (!result && set2)
-    result = bitmap_find_leader (set2, expr);
+    result = bitmap_find_leader (set2, expr, NULL_TREE);
   return result;
 }
 
@@ -1394,11 +1394,12 @@ phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
 }
 
 /* Find the leader for a value (i.e., the name representing that
-   value) in a given set, and return it.  Return NULL if no leader is
-   found.  */
+   value) in a given set, and return it.  If STMT is non-NULL it
+   makes sure the defining statement for the leader dominates it.
+   Return NULL if no leader is found.  */
 
 static tree
-bitmap_find_leader (bitmap_set_t set, tree val)
+bitmap_find_leader (bitmap_set_t set, tree val, tree stmt)
 {
   if (val == NULL)
     return NULL;
@@ -1425,7 +1426,17 @@ bitmap_find_leader (bitmap_set_t set, tree val)
 
       EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
 				set->expressions, 0, i, bi)
-	return expression_for_id (i);
+	{
+	  tree val = expression_for_id (i);
+	  if (stmt)
+	    {
+	      tree def_stmt = SSA_NAME_DEF_STMT (val);
+	      if (bb_for_stmt (def_stmt) == bb_for_stmt (stmt)
+		  && stmt_ann (def_stmt)->uid >= stmt_ann (stmt)->uid)
+		continue;
+	    }
+	  return val;
+	}
     }
   return NULL;
 }
@@ -2107,6 +2118,7 @@ can_PRE_operation (tree op)
     || COMPARISON_CLASS_P (op)
     || TREE_CODE (op) == INDIRECT_REF
     || TREE_CODE (op) == COMPONENT_REF
+    || TREE_CODE (op) == VIEW_CONVERT_EXPR
     || TREE_CODE (op) == CALL_EXPR
     || TREE_CODE (op) == ARRAY_REF;
 }
@@ -2136,14 +2148,15 @@ static VEC(tree, heap) *need_creation;
    are doing.
 */
 static tree
-create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
+create_component_ref_by_pieces (basic_block block, tree expr, tree stmts,
+				tree domstmt)
 {
   tree genop = expr;
   tree folded;
 
   if (TREE_CODE (genop) == VALUE_HANDLE)
     {
-      tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
+      tree found = bitmap_find_leader (AVAIL_OUT (block), expr, domstmt);
       if (found)
 	return found;
     }
@@ -2163,16 +2176,18 @@ create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
 	tree op1, op2, op3;
 	op0 = create_component_ref_by_pieces (block,
 					      TREE_OPERAND (genop, 0),
-					      stmts);
+					      stmts, domstmt);
 	op1 = TREE_OPERAND (genop, 1);
 	if (TREE_CODE (op1) == VALUE_HANDLE)
-	  op1 = find_or_generate_expression (block, op1, stmts);
+	  op1 = find_or_generate_expression (block, op1, stmts, domstmt);
 	op2 = TREE_OPERAND (genop, 2);
 	if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
-	  op2 = find_or_generate_expression (block, op2, stmts);
+	  op2 = find_or_generate_expression (block, op2, stmts, domstmt);
 	op3 = TREE_OPERAND (genop, 3);
 	if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
-	  op3 = find_or_generate_expression (block, op3, stmts);
+	  op3 = find_or_generate_expression (block, op3, stmts, domstmt);
+	if (!op0 || !op1)
+	  return NULL_TREE;
 	folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
 			      op2, op3);
 	return folded;
@@ -2183,7 +2198,9 @@ create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
 	tree op1;
 	op0 = create_component_ref_by_pieces (block,
 					      TREE_OPERAND (genop, 0),
-					      stmts);
+					      stmts, domstmt);
+	if (!op0)
+	  return NULL_TREE;
 	/* op1 should be a FIELD_DECL, which are represented by
 	   themselves.  */
 	op1 = TREE_OPERAND (genop, 1);
@@ -2195,7 +2212,9 @@ create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
     case INDIRECT_REF:
       {
 	tree op1 = TREE_OPERAND (genop, 0);
-	tree genop1 = find_or_generate_expression (block, op1, stmts);
+	tree genop1 = find_or_generate_expression (block, op1, stmts, domstmt);
+	if (!genop1)
+	  return NULL_TREE;
 
 	folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
 			      genop1);
@@ -2222,12 +2241,17 @@ create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
    EXPR is the expression to find a leader or generate for.
    STMTS is the statement list to put the inserted expressions on.
    Returns the SSA_NAME of the LHS of the generated expression or the
-   leader.  */
+   leader.
+   DOMSTMT if non-NULL is a statement that should be dominated by
+   all uses in the generated expression.  If DOMSTMT is non-NULL this
+   routine can fail and return NULL_TREE.  Otherwise it will assert
+   on failure.  */
 
 static tree
-find_or_generate_expression (basic_block block, tree expr, tree stmts)
+find_or_generate_expression (basic_block block, tree expr, tree stmts,
+			     tree domstmt)
 {
-  tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
+  tree genop = bitmap_find_leader (AVAIL_OUT (block), expr, domstmt);
 
   /* If it's still NULL, it must be a complex expression, so generate
      it recursively.  */
@@ -2247,10 +2271,14 @@ find_or_generate_expression (basic_block block, tree expr, tree stmts)
 	  if (can_PRE_operation (genop))
 	    {
 	      handled = true;
-	      genop = create_expression_by_pieces (block, genop, stmts);
+	      genop = create_expression_by_pieces (block, genop, stmts,
+						   domstmt);
 	      break;
 	    }
 	}
+      if (!handled && domstmt)
+	return NULL_TREE;
+
       gcc_assert (handled);
     }
   return genop;
@@ -2269,10 +2297,15 @@ find_or_generate_expression (basic_block block, tree expr, tree stmts)
    partially or fully redundant.  Those that are will be either made
    fully redundant during the next iteration of insert (for partially
    redundant ones), or eliminated by eliminate (for fully redundant
-   ones).  */
+   ones).
+
+   If DOMSTMT is non-NULL then we make sure that all uses in the
+   expressions dominate that statement.  In this case the function
+   can return NULL_TREE to signal failure.  */
 
 static tree
-create_expression_by_pieces (basic_block block, tree expr, tree stmts)
+create_expression_by_pieces (basic_block block, tree expr, tree stmts,
+			     tree domstmt)
 {
   tree temp, name;
   tree folded, forced_stmts, newexpr;
@@ -2293,7 +2326,9 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
 	fn = CALL_EXPR_FN (expr);
 	sc = CALL_EXPR_STATIC_CHAIN (expr);
 
-	genfn = find_or_generate_expression (block, fn, stmts);
+	genfn = find_or_generate_expression (block, fn, stmts, domstmt);
+	if (!genfn)
+	  return NULL_TREE;
 
 	nargs = call_expr_nargs (expr);
 	buffer = (tree*) alloca (nargs * sizeof (tree));
@@ -2301,13 +2336,20 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
 	for (i = 0; i < nargs; i++)
 	  {
 	    tree arg = CALL_EXPR_ARG (expr, i);
-	    buffer[i] = find_or_generate_expression (block, arg, stmts);
+	    buffer[i] = find_or_generate_expression (block, arg, stmts,
+						     domstmt);
+	    if (!buffer[i])
+	      return NULL_TREE;
 	  }
 
 	folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
 	if (sc)
-	  CALL_EXPR_STATIC_CHAIN (folded) =
-	    find_or_generate_expression (block, sc, stmts);
+	  {
+	    CALL_EXPR_STATIC_CHAIN (folded) =
+	      find_or_generate_expression (block, sc, stmts, domstmt);
+	    if (!CALL_EXPR_STATIC_CHAIN (folded))
+	      return NULL_TREE;
+	  }
 	folded = fold (folded);
 	break;
       }
@@ -2317,12 +2359,18 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
 	if (TREE_CODE (expr) == COMPONENT_REF
 	    || TREE_CODE (expr) == ARRAY_REF)
 	  {
-	    folded = create_component_ref_by_pieces (block, expr, stmts);
+	    folded = create_component_ref_by_pieces (block, expr, stmts,
+						     domstmt);
+	    if (!folded)
+	      return NULL_TREE;
 	  }
 	else
 	  {
 	    tree op1 = TREE_OPERAND (expr, 0);
-	    tree genop1 = find_or_generate_expression (block, op1, stmts);
+	    tree genop1 = find_or_generate_expression (block, op1, stmts,
+						       domstmt);
+	    if (!genop1)
+	      return NULL_TREE;
 
 	    folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
 				  genop1);
@@ -2335,8 +2383,10 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
       {
 	tree op1 = TREE_OPERAND (expr, 0);
 	tree op2 = TREE_OPERAND (expr, 1);
-	tree genop1 = find_or_generate_expression (block, op1, stmts);
-	tree genop2 = find_or_generate_expression (block, op2, stmts);
+	tree genop1 = find_or_generate_expression (block, op1, stmts, domstmt);
+	tree genop2 = find_or_generate_expression (block, op2, stmts, domstmt);
+	if (!genop1 || !genop2)
+	  return NULL_TREE;
 	folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
 			      genop1, genop2);
 	break;
@@ -2345,7 +2395,9 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
     case tcc_unary:
       {
 	tree op1 = TREE_OPERAND (expr, 0);
-	tree genop1 = find_or_generate_expression (block, op1, stmts);
+	tree genop1 = find_or_generate_expression (block, op1, stmts, domstmt);
+	if (!genop1)
+	  return NULL_TREE;
 	folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
 			      genop1);
 	break;
@@ -2421,7 +2473,8 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
   vn_add (name, v);
   VN_INFO_GET (name)->valnum = name;
   get_or_alloc_expression_id (name);
-  bitmap_value_replace_in_set (NEW_SETS (block), name);
+  if (!in_fre)
+    bitmap_value_replace_in_set (NEW_SETS (block), name);
   bitmap_value_replace_in_set (AVAIL_OUT (block), name);
 
   pre_stats.insertions++;
@@ -2497,7 +2550,7 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
 	{
 	  builtexpr = create_expression_by_pieces (bprime,
 						   eprime,
-						   stmts);
+						   stmts, NULL_TREE);
 	  gcc_assert (!(pred->flags & EDGE_ABNORMAL));
 	  bsi_insert_on_edge (pred, stmts);
 	  avail[bprime->index] = builtexpr;
@@ -2659,7 +2712,7 @@ do_regular_insertion (basic_block block, basic_block dom)
 	      vprime = get_value_handle (eprime);
 	      gcc_assert (vprime);
 	      edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
-						 vprime);
+						 vprime, NULL_TREE);
 	      if (edoubleprime == NULL)
 		{
 		  avail[bprime->index] = eprime;
@@ -2788,7 +2841,7 @@ do_partial_partial_insertion (basic_block block, basic_block dom)
 	      vprime = get_value_handle (eprime);
 	      gcc_assert (vprime);
 	      edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
-						 vprime);
+						 vprime, NULL_TREE);
 	      if (edoubleprime == NULL)
 		{
 		  by_all = false;
@@ -2970,10 +3023,14 @@ find_existing_value_expr (tree t, VEC (tree, gc) *vuses)
    replaced with the value handles of each of the operands of EXPR.
 
    VUSES represent the virtual use operands associated with EXPR (if
-   any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
+   any).  Insert EXPR's operands into the EXP_GEN set for BLOCK.
+
+   If CHECK_AVAIL is true, checks availability of each operand in
+   BLOCKs AVAIL_OUT set.  */
 
 static inline tree
-create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses)
+create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses,
+			bool check_avail)
 {
   int i;
   enum tree_code code = TREE_CODE (expr);
@@ -3021,7 +3078,7 @@ create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses)
       /* Recursively value-numberize reference ops and tree lists.  */
       if (REFERENCE_CLASS_P (op))
 	{
-	  tree tempop = create_value_expr_from (op, block, vuses);
+	  tree tempop = create_value_expr_from (op, block, vuses, check_avail);
 	  op = tempop ? tempop : op;
 	  val = vn_lookup_or_add_with_vuses (op, vuses);
 	  set_expression_vuses (op, vuses);
@@ -3037,6 +3094,11 @@ create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses)
 	TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
 
       TREE_OPERAND (vexpr, i) = val;
+
+      if (check_avail
+	  && TREE_CODE (val) == VALUE_HANDLE
+	  && !bitmap_set_contains_value (AVAIL_OUT (block), val))
+	return NULL_TREE;
     }
   efi = find_existing_value_expr (vexpr, vuses);
   if (efi)
@@ -3271,12 +3333,13 @@ make_values_for_stmt (tree stmt, basic_block block)
   vuses = copy_vuses_from_stmt (stmt);
   STRIP_USELESS_TYPE_CONVERSION (rhs);
   if (can_value_number_operation (rhs)
-      && (!lhsval || !is_gimple_min_invariant (lhsval)))
+      && (!lhsval || !is_gimple_min_invariant (lhsval))
+      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
     {
       /* For value numberable operation, create a
 	 duplicate expression with the operands replaced
 	 with the value handles of the original RHS.  */
-      tree newt = create_value_expr_from (rhs, block, vuses);
+      tree newt = create_value_expr_from (rhs, block, vuses, false);
       if (newt)
 	{
 	  set_expression_vuses (newt, vuses);
@@ -3480,8 +3543,6 @@ compute_avail (void)
 	  else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 		   && !ann->has_volatile_ops
 		   && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
-		   && (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI
-		       (GIMPLE_STMT_OPERAND (stmt, 0)))
 		   && !tree_could_throw_p (stmt))
 	    {
 	      if (make_values_for_stmt (stmt, block))
@@ -3510,6 +3571,36 @@ compute_avail (void)
   free (worklist);
 }
 
+/* Insert the expression for SSA_VN that SCCVN thought would be simpler
+   than the available expressions for it.  The insertion point is
+   right before the first use in STMT.  Returns the SSA_NAME that should
+   be used for replacement.  */
+
+static tree
+do_SCCVN_insertion (tree stmt, tree ssa_vn)
+{
+  basic_block bb = bb_for_stmt (stmt);
+  block_stmt_iterator bsi;
+  tree expr, stmts;
+
+  /* First create a value expression from the expression we want
+     to insert and associate it with the value handle for SSA_VN.  */
+  expr = create_value_expr_from (VN_INFO (ssa_vn)->expr, bb, NULL, true);
+  if (expr == NULL_TREE)
+    return NULL_TREE;
+  set_value_handle (expr, get_value_handle (ssa_vn));
+
+  /* Then use create_expression_by_pieces to generate a valid
+     expression to insert at this point of the IL stream.  */
+  stmts = alloc_stmt_list ();
+  expr = create_expression_by_pieces (bb, expr, stmts, stmt);
+  if (expr == NULL_TREE)
+    return NULL_TREE;
+  bsi = bsi_for_stmt (stmt);
+  bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+
+  return expr;
+}
 
 /* Eliminate fully redundant computations.  */
 
@@ -3540,7 +3631,20 @@ eliminate (void)
 	      tree sprime;
 
 	      sprime = bitmap_find_leader (AVAIL_OUT (b),
-					   get_value_handle (lhs));
+					   get_value_handle (lhs), NULL_TREE);
+
+	      /* If there is no existing usable leader but SCCVN thinks
+		 it has an expression it wants to use as replacement,
+		 insert that.  */
+	      if (!sprime
+		  || sprime == lhs)
+		{
+		  tree val = VN_INFO (lhs)->valnum;
+		  if (val != VN_TOP
+		      && VN_INFO (val)->needs_insertion
+		      && can_PRE_operation (VN_INFO (val)->expr))
+		    sprime = do_SCCVN_insertion (stmt, val);
+		}
 
 	      if (sprime
 		  && sprime != lhs
@@ -3837,7 +3941,7 @@ execute_pre (bool do_fre)
     insert_fake_stores ();
 
   /* Collect and value number expressions computed in each basic block.  */
-  if (!run_scc_vn ())
+  if (!run_scc_vn (do_fre))
     {
       if (!do_fre)
 	remove_dead_inserted_code ();
@@ -3885,8 +3989,8 @@ execute_pre (bool do_fre)
     }
   bsi_commit_edge_inserts ();
 
-  free_scc_vn ();
   clear_expression_ids ();
+  free_scc_vn ();
   if (!do_fre)
     {
       remove_dead_inserted_code ();