CbC/CbC_gcc: gcc/tree-ssa-pre.c comparison

comparison gcc/tree-ssa-pre.c @ 63:b7f97abdc517 gcc-4.6-20100522

update gcc from gcc-4.5.0 to gcc-4.6

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Mon, 24 May 2010 12:47:05 +0900
parents	77e2b8dfacca
children	f6334be47118

comparison

equal deleted inserted replaced

-:3c8a44c06a95
+:b7f97abdc517
 /* SSA-PRE for trees.
-Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
 Free Software Foundation, Inc.
 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
 <stevenb@suse.de>
 This file is part of GCC.
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
-#include "ggc.h"
 #include "tree.h"
 #include "basic-block.h"
 #include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
 #include "tree-inline.h"
 #include "tree-flow.h"
 #include "gimple.h"
 #include "tree-dump.h"
 #include "timevar.h"
 #include "fibheap.h"
 #include "hashtab.h"
 #include "tree-iterator.h"
-#include "real.h"
 #include "alloc-pool.h"
 #include "obstack.h"
 #include "tree-pass.h"
 #include "flags.h"
 #include "bitmap.h"
 return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
 case REFERENCE:
 return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
 			      PRE_EXPR_REFERENCE (e2));
 default:
-abort();
+gcc_unreachable ();
 }
 }
 static hashval_t
 pre_expr_hash (const void *p1)
 switch (e->kind)
 {
 case CONSTANT:
 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
 case NAME:
-return iterative_hash_hashval_t (SSA_NAME_VERSION (PRE_EXPR_NAME (e)), 0);
+return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
 case NARY:
 return PRE_EXPR_NARY (e)->hashcode;
 case REFERENCE:
 return PRE_EXPR_REFERENCE (e)->hashcode;
 default:
-abort ();
+gcc_unreachable ();
 }
 }
 /* Next global expression id number.  */
 /* Mapping from expression to id number we can use in bitmap sets.  */
 DEF_VEC_P (pre_expr);
 DEF_VEC_ALLOC_P (pre_expr, heap);
 static VEC(pre_expr, heap) *expressions;
 static htab_t expression_to_id;
+static VEC(unsigned, heap) *name_to_id;
 /* Allocate an expression id for EXPR.  */
 static inline unsigned int
 alloc_expression_id (pre_expr expr)
 void **slot;
 /* Make sure we won't overflow. */
 gcc_assert (next_expression_id + 1 > next_expression_id);
 expr->id = next_expression_id++;
 VEC_safe_push (pre_expr, heap, expressions, expr);
-slot = htab_find_slot (expression_to_id, expr, INSERT);
+if (expr->kind == NAME)
-gcc_assert (!*slot);
+{
-*slot = expr;
+unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
+/* VEC_safe_grow_cleared allocates no headroom.  Avoid frequent
+	 re-allocations by using VEC_reserve upfront.  There is no
+	 VEC_quick_grow_cleared unfortunately.  */
+VEC_reserve (unsigned, heap, name_to_id, num_ssa_names);
+VEC_safe_grow_cleared (unsigned, heap, name_to_id, num_ssa_names);
+gcc_assert (VEC_index (unsigned, name_to_id, version) == 0);
+VEC_replace (unsigned, name_to_id, version, expr->id);
+}
+else
+{
+slot = htab_find_slot (expression_to_id, expr, INSERT);
+gcc_assert (!*slot);
+*slot = expr;
+}
 return next_expression_id - 1;
 }
 /* Return the expression id for tree EXPR.  */
 static inline unsigned int
 lookup_expression_id (const pre_expr expr)
 {
 void **slot;
-slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
+if (expr->kind == NAME)
-if (!slot)
+{
-return 0;
+unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
-return ((pre_expr)*slot)->id;
+if (VEC_length (unsigned, name_to_id) <= version)
+	return 0;
+return VEC_index (unsigned, name_to_id, version);
+}
+else
+{
+slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
+if (!slot)
+	return 0;
+return ((pre_expr)*slot)->id;
+}
 }
 /* Return the existing expression id for EXPR, or create one if one
 does not exist yet.  */
 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
 static pre_expr
 get_or_alloc_expr_for_name (tree name)
 {
-pre_expr result = (pre_expr) pool_alloc (pre_expr_pool);
+struct pre_expr_d expr;
+pre_expr result;
 unsigned int result_id;
+expr.kind = NAME;
+expr.id = 0;
+PRE_EXPR_NAME (&expr) = name;
+result_id = lookup_expression_id (&expr);
+if (result_id != 0)
+return expression_for_id (result_id);
+result = (pre_expr) pool_alloc (pre_expr_pool);
 result->kind = NAME;
-result->id = 0;
 PRE_EXPR_NAME (result) = name;
-result_id = lookup_expression_id (result);
+alloc_expression_id (result);
-if (result_id != 0)
-{
-pool_free (pre_expr_pool, result);
-result = expression_for_id (result_id);
-return result;
-}
-get_or_alloc_expression_id (result);
 return result;
 }
 static bool in_fre = false;
 /* A cache for value_dies_in_block_x.  */
 bitmap expr_dies;
 /* True if we have visited this block during ANTIC calculation.  */
-unsigned int visited:1;
+unsigned int visited : 1;
 /* True we have deferred processing this block during ANTIC
 calculation until its successor is processed.  */
 unsigned int deferred : 1;
+/* True when the block contains a call that might not return.  */
+unsigned int contains_may_not_return_call : 1;
 } *bb_value_sets_t;
 #define EXP_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->exp_gen
 #define PHI_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->phi_gen
 #define TMP_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->tmp_gen
 #define PA_IN(BB)	((bb_value_sets_t) ((BB)->aux))->pa_in
 #define NEW_SETS(BB)	((bb_value_sets_t) ((BB)->aux))->new_sets
 #define EXPR_DIES(BB)	((bb_value_sets_t) ((BB)->aux))->expr_dies
 #define BB_VISITED(BB)	((bb_value_sets_t) ((BB)->aux))->visited
 #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
+#define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
 /* Basic block list in postorder.  */
 static int *postorder;
 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
-static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, bool);
+static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
+				      unsigned int, bool);
 static bitmap_set_t bitmap_set_new (void);
 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
 					 gimple, tree);
 static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
 					 gimple);
 {
 set = bitmap_set_new ();
 VEC_replace (bitmap_set_t, value_expressions, v, set);
 }
-bitmap_insert_into_set_1 (set, e, true);
+bitmap_insert_into_set_1 (set, e, v, true);
 }
 /* Create a new bitmap set and return it.  */
 static bitmap_set_t
 }
 }
 static void
 bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
-			  bool allow_constants)
+			  unsigned int val, bool allow_constants)
 {
-unsigned int val  = get_expr_value_id (expr);
 if (allow_constants || !value_id_constant_p (val))
 {
 /* We specifically expect this and only this function to be able to
 	 insert constants into a set.  */
 bitmap_set_bit (set->values, val);
 /* Insert an expression EXPR into a bitmapped set.  */
 static void
 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
 {
-bitmap_insert_into_set_1 (set, expr, false);
+bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);
 }
 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
 static void
 static VEC(pre_expr, heap) *
 sorted_array_from_bitmap_set (bitmap_set_t set)
 {
 unsigned int i, j;
 bitmap_iterator bi, bj;
-VEC(pre_expr, heap) *result = NULL;
+VEC(pre_expr, heap) *result;
+/* Pre-allocate roughly enough space for the array.  */
+result = VEC_alloc (pre_expr, heap, bitmap_count_bits (set->values));
 FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
 {
 /* The number of expressions having a given value is usually
 	 relatively small.  Thus, rather than making a vector of all
 static void
 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
 {
 unsigned int val = get_expr_value_id (expr);
+#ifdef ENABLE_CHECKING
+gcc_assert (expr->id == get_or_alloc_expression_id (expr));
+#endif
+/* Constant values are always considered to be part of the set.  */
 if (value_id_constant_p (val))
 return;
-if (!bitmap_set_contains_value (set, val))
+/* If the value membership changed, add the expression.  */
-bitmap_insert_into_set (set, expr);
+if (bitmap_set_bit (set->values, val))
+bitmap_set_bit (set->expressions, expr->id);
 }
 /* Print out EXPR to outfile.  */
 static void
 static pre_expr
 get_or_alloc_expr_for_constant (tree constant)
 {
 unsigned int result_id;
 unsigned int value_id;
-pre_expr newexpr = (pre_expr) pool_alloc (pre_expr_pool);
+struct pre_expr_d expr;
+pre_expr newexpr;
+expr.kind = CONSTANT;
+PRE_EXPR_CONSTANT (&expr) = constant;
+result_id = lookup_expression_id (&expr);
+if (result_id != 0)
+return expression_for_id (result_id);
+newexpr = (pre_expr) pool_alloc (pre_expr_pool);
 newexpr->kind = CONSTANT;
 PRE_EXPR_CONSTANT (newexpr) = constant;
-result_id = lookup_expression_id (newexpr);
+alloc_expression_id (newexpr);
-if (result_id != 0)
-{
-pool_free (pre_expr_pool, newexpr);
-newexpr = expression_for_id (result_id);
-return newexpr;
-}
 value_id = get_or_alloc_constant_value_id (constant);
-get_or_alloc_expression_id (newexpr);
 add_to_value (value_id, newexpr);
 return newexpr;
 }
 /* Given a value id V, find the actual tree representing the constant
 	  }
 }
 case REFERENCE:
 {
 	vn_reference_t ref = PRE_EXPR_REFERENCE (e);
-	VEC (vn_reference_op_s, heap) *operands = ref->operands;
+	tree folded;
-	vn_reference_op_t op;
+	if ((folded = fully_constant_vn_reference_p (ref)))
+	  return get_or_alloc_expr_for_constant (folded);
-	/* Try to simplify the translated expression if it is
+	return e;
-	   a call to a builtin function with at most two arguments.  */
+}
-	op = VEC_index (vn_reference_op_s, operands, 0);
-	if (op->opcode == CALL_EXPR
-	    && TREE_CODE (op->op0) == ADDR_EXPR
-	    && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
-	    && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
-	    && VEC_length (vn_reference_op_s, operands) >= 2
-	    && VEC_length (vn_reference_op_s, operands) <= 3)
-	  {
-	    vn_reference_op_t arg0, arg1 = NULL;
-	    bool anyconst = false;
-	    arg0 = VEC_index (vn_reference_op_s, operands, 1);
-	    if (VEC_length (vn_reference_op_s, operands) > 2)
-	      arg1 = VEC_index (vn_reference_op_s, operands, 2);
-	    if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
-		|| (arg0->opcode == ADDR_EXPR
-		    && is_gimple_min_invariant (arg0->op0)))
-	      anyconst = true;
-	    if (arg1
-		&& (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
-		    || (arg1->opcode == ADDR_EXPR
-			&& is_gimple_min_invariant (arg1->op0))))
-	      anyconst = true;
-	    if (anyconst)
-	      {
-		tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
-					       arg1 ? 2 : 1,
-					       arg0->op0,
-					       arg1 ? arg1->op0 : NULL);
-		if (folded
-		    && TREE_CODE (folded) == NOP_EXPR)
-		  folded = TREE_OPERAND (folded, 0);
-		if (folded
-		    && is_gimple_min_invariant (folded))
-		  return get_or_alloc_expr_for_constant (folded);
-	      }
-	  }
-	  return e;
-	}
 default:
 return e;
 }
 return e;
 }
 /* Build and insert the assignment of the end result to the temporary
 that we will return.  */
 if (!pretemp || exprtype != TREE_TYPE (pretemp))
 {
-pretemp = create_tmp_var (exprtype, "pretmp");
+pretemp = create_tmp_reg (exprtype, "pretmp");
 get_var_ann (pretemp);
 }
 name = make_ssa_name (pretemp, gimple_build_nop ());
 VN_INFO_GET (name)->value_id = value_id;
 return name;
 }
+static pre_expr
+phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+	       basic_block pred, basic_block phiblock);
 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
 the phis in PRED.  Return NULL if we can't find a leader for each part
 of the translated expression.  */
 static pre_expr
-phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
-	       basic_block pred, basic_block phiblock)
+		 basic_block pred, basic_block phiblock)
 {
-pre_expr oldexpr = expr;
-pre_expr phitrans;
-if (!expr)
-return NULL;
-if (value_id_constant_p (get_expr_value_id (expr)))
-return expr;
-phitrans = phi_trans_lookup (expr, pred);
-if (phitrans)
-return phitrans;
 switch (expr->kind)
 {
-/* Constants contain no values that need translation.  */
-case CONSTANT:
-return expr;
 case NARY:
 {
 	unsigned int i;
 	bool changed = false;
 	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
 	      }
 	  }
 	if (changed)
 	  {
 	    pre_expr constant;
+	    unsigned int new_val_id;
 	    tree result = vn_nary_op_lookup_pieces (newnary.length,
 						    newnary.opcode,
 						    newnary.type,
 						    newnary.op[0],
 						    newnary.op[1],
 						    newnary.op[2],
 						    newnary.op[3],
 						    &nary);
-	    unsigned int new_val_id;
+	    if (result && is_gimple_min_invariant (result))
+	      return get_or_alloc_expr_for_constant (result);
 	    expr = (pre_expr) pool_alloc (pre_expr_pool);
 	    expr->kind = NARY;
 	    expr->id = 0;
-	    if (result && is_gimple_min_invariant (result))
-	      return get_or_alloc_expr_for_constant (result);
 	    if (nary)
 	      {
 		PRE_EXPR_NARY (expr) = nary;
 		constant = fully_constant_expression (expr);
 		if (constant != expr)
 		  return constant;
 		get_or_alloc_expression_id (expr);
 	      }
 	    add_to_value (new_val_id, expr);
 	  }
-	phi_trans_add (oldexpr, expr, pred);
 	return expr;
 }
 break;
 case REFERENCE:
 	    tree result = vn_reference_lookup_pieces (newvuse, ref->set,
 						      ref->type,
 						      newoperands,
 						      &newref, true);
-	    if (newref)
+	    if (result)
 	      VEC_free (vn_reference_op_s, heap, newoperands);
 	    if (result && is_gimple_min_invariant (result))
 	      {
 	        gcc_assert (!newoperands);
 		get_or_alloc_expression_id (expr);
 	      }
 	    add_to_value (new_val_id, expr);
 	  }
 	VEC_free (vn_reference_op_s, heap, newoperands);
-	phi_trans_add (oldexpr, expr, pred);
 	return expr;
 }
 break;
 case NAME:
 default:
 gcc_unreachable ();
 }
 }
+/* Wrapper around phi_translate_1 providing caching functionality.  */
+static pre_expr
+phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+	       basic_block pred, basic_block phiblock)
+{
+pre_expr phitrans;
+if (!expr)
+return NULL;
+/* Constants contain no values that need translation.  */
+if (expr->kind == CONSTANT)
+return expr;
+if (value_id_constant_p (get_expr_value_id (expr)))
+return expr;
+if (expr->kind != NAME)
+{
+phitrans = phi_trans_lookup (expr, pred);
+if (phitrans)
+	return phitrans;
+}
+/* Translate.  */
+phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
+/* Don't add empty translations to the cache.  Neither add
+translations of NAMEs as those are cheap to translate.  */
+if (phitrans
+&& expr->kind != NAME)
+phi_trans_add (expr, phitrans, pred);
+return phitrans;
+}
 /* For each expression in SET, translate the values through phi nodes
 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
 expressions in DEST.  */
 static void
 {
 VEC (pre_expr, heap) *exprs;
 pre_expr expr;
 int i;
-if (!phi_nodes (phiblock))
+if (gimple_seq_empty_p (phi_nodes (phiblock)))
 {
 bitmap_set_copy (dest, set);
 return;
 }
 exprs = sorted_array_from_bitmap_set (set);
 for (i = 0; VEC_iterate (pre_expr, exprs, i, expr); i++)
 {
 pre_expr translated;
 translated = phi_translate (expr, set, NULL, pred, phiblock);
+if (!translated)
-/* Don't add empty translations to the cache  */
+	continue;
-if (translated)
-	phi_trans_add (expr, translated, pred);
+/* We might end up with multiple expressions from SET being
+	 translated to the same value.  In this case we do not want
-if (translated != NULL)
+	 to retain the NARY or REFERENCE expression but prefer a NAME
+	 which would be the leader.  */
+if (translated->kind == NAME)
+	bitmap_value_replace_in_set (dest, translated);
+else
 	bitmap_value_insert_into_set (dest, translated);
 }
 VEC_free (pre_expr, heap, exprs);
 }
 		if (!union_contains_value (set1, set2,
 					   get_expr_value_id (&temp)))
 		  return false;
 	      }
 	  }
+	/* If the NARY may trap make sure the block does not contain
+	   a possible exit point.
+	   ???  This is overly conservative if we translate AVAIL_OUT
+	   as the available expression might be after the exit point.  */
+	if (BB_MAY_NOTRETURN (block)
+	    && vn_nary_may_trap (nary))
+	  return false;
 	return true;
 }
 break;
 case REFERENCE:
 {
 	  changed = true;
 	  VEC_free (basic_block, heap, worklist);
 	  goto maybe_dump_sets;
 	}
-if (phi_nodes (first))
+if (!gimple_seq_empty_p (phi_nodes (first)))
 	phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
 else
 	bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
 for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
 	{
-	  if (phi_nodes (bprime))
+	  if (!gimple_seq_empty_p (phi_nodes (bprime)))
 	    {
 	      bitmap_set_t tmp = bitmap_set_new ();
 	      phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
 	      bitmap_set_and (ANTIC_OUT, tmp);
 	      bitmap_set_free (tmp);
 	      bitmap_iterator bi;
 	      FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
 		bitmap_value_insert_into_set (PA_OUT,
 					      expression_for_id (i));
-	      if (phi_nodes (bprime))
+	      if (!gimple_seq_empty_p (phi_nodes (bprime)))
 		{
 		  bitmap_set_t pa_in = bitmap_set_new ();
 		  phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
 		  FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
 		    bitmap_value_insert_into_set (PA_OUT,
 	    }
 	}
 BB_VISITED (block) = 0;
 BB_DEFERRED (block) = 0;
 /* While we are here, give empty ANTIC_IN sets to each block.  */
 ANTIC_IN (block) = bitmap_set_new ();
 PA_IN (block) = bitmap_set_new ();
 }
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "Starting iteration %d\n", num_iterations);
 num_iterations++;
 changed = false;
-for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
+for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
 	{
 	  if (TEST_BIT (changed_blocks, postorder[i]))
 	    {
 	      basic_block block = BASIC_BLOCK (postorder[i]);
 	      changed |= compute_antic_aux (block,
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file, "Starting iteration %d\n", num_iterations);
 	  num_iterations++;
 	  changed = false;
-	  for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
+	  for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--)
 	    {
 	      if (TEST_BIT (changed_blocks, postorder[i]))
 		{
 		  basic_block block = BASIC_BLOCK (postorder[i]);
 		  changed
 /* Inserted expressions are placed onto this worklist, which is used
 for performing quick dead code elimination of insertions we made
 that didn't turn out to be necessary.   */
-static VEC(gimple,heap) *inserted_exprs;
+static bitmap inserted_exprs;
-static bitmap inserted_phi_names;
 /* Pool allocated fake store expressions are placed onto this
 worklist, which, after performing dead code elimination, is walked
 to see which expressions need to be put into GC'able memory  */
 static VEC(gimple, heap) *need_creation;
 ++*operand;
 switch (currop->opcode)
 {
 case CALL_EXPR:
 {
-	tree folded, sc = currop->op1;
+	tree folded, sc = NULL_TREE;
 	unsigned int nargs = 0;
-	tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
+	tree fn, *args;
-						ref->operands) - 1);
+	if (TREE_CODE (currop->op0) == FUNCTION_DECL)
+	  fn = currop->op0;
+	else
+	  {
+	    pre_expr op0 = get_or_alloc_expr_for (currop->op0);
+	    fn = find_or_generate_expression (block, op0, stmts, domstmt);
+	    if (!fn)
+	      return NULL_TREE;
+	  }
+	if (currop->op1)
+	  {
+	    pre_expr scexpr = get_or_alloc_expr_for (currop->op1);
+	    sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
+	    if (!sc)
+	      return NULL_TREE;
+	  }
+	args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
+					  ref->operands) - 1);
 	while (*operand < VEC_length (vn_reference_op_s, ref->operands))
 	  {
 	    args[nargs] = create_component_ref_by_pieces_1 (block, ref,
 							    operand, stmts,
 							    domstmt);
+	    if (!args[nargs])
+	      {
+		free (args);
+		return NULL_TREE;
+	      }
 	    nargs++;
 	  }
 	folded = build_call_array (currop->type,
-				   TREE_CODE (currop->op0) == FUNCTION_DECL
+				   (TREE_CODE (fn) == FUNCTION_DECL
-				   ? build_fold_addr_expr (currop->op0)
+				    ? build_fold_addr_expr (fn) : fn),
-				   : currop->op0,
 				   nargs, args);
 	free (args);
 	if (sc)
-	  {
+	  CALL_EXPR_STATIC_CHAIN (folded) = sc;
-	    pre_expr scexpr = get_or_alloc_expr_for (sc);
-	    sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
-	    if (!sc)
-	      return NULL_TREE;
-	    CALL_EXPR_STATIC_CHAIN (folded) = sc;
-	  }
 	return folded;
 }
 break;
 case TARGET_MEM_REF:
 {
 	genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
 	if (!genop1)
 	  return NULL_TREE;
 	if (genop2)
 	  {
-	    op2expr = get_or_alloc_expr_for (genop2);
+	    /* Drop zero minimum index.  */
-	    genop2 = find_or_generate_expression (block, op2expr, stmts,
+	    if (tree_int_cst_equal (genop2, integer_zero_node))
-						  domstmt);
+	      genop2 = NULL_TREE;
-	    if (!genop2)
+	    else
-	      return NULL_TREE;
+	      {
+		op2expr = get_or_alloc_expr_for (genop2);
+		genop2 = find_or_generate_expression (block, op2expr, stmts,
+						      domstmt);
+		if (!genop2)
+		  return NULL_TREE;
+	      }
 	  }
 	if (genop3)
 	  {
 	    tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
-	    genop3 = size_binop (EXACT_DIV_EXPR, genop3,
+	    /* We can't always put a size in units of the element alignment
-				 size_int (TYPE_ALIGN_UNIT (elmt_type)));
+	       here as the element alignment may be not visible.  See
-	    op3expr = get_or_alloc_expr_for (genop3);
+	       PR43783.  Simply drop the element size for constant
-	    genop3 = find_or_generate_expression (block, op3expr, stmts,
+	       sizes.  */
-						  domstmt);
+	    if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
-	    if (!genop3)
+	      genop3 = NULL_TREE;
-	      return NULL_TREE;
+	    else
+	      {
+		genop3 = size_binop (EXACT_DIV_EXPR, genop3,
+				     size_int (TYPE_ALIGN_UNIT (elmt_type)));
+		op3expr = get_or_alloc_expr_for (genop3);
+		genop3 = find_or_generate_expression (block, op3expr, stmts,
+						      domstmt);
+		if (!genop3)
+		  return NULL_TREE;
+	      }
 	  }
 	return build4 (currop->opcode, currop->type, genop0, genop1,
 		       genop2, genop3);
 }
 case COMPONENT_REF:
 							 stmts, domstmt);
 	      tree genop2 = find_or_generate_expression (block, op2,
 							 stmts, domstmt);
 	      if (!genop1 || !genop2)
 		return NULL_TREE;
-	      genop1 = fold_convert (TREE_TYPE (nary->op[0]),
-				     genop1);
 	      /* Ensure op2 is a sizetype for POINTER_PLUS_EXPR.  It
 		 may be a constant with the wrong type.  */
 	      if (nary->opcode == POINTER_PLUS_EXPR)
-		genop2 = fold_convert (sizetype, genop2);
+		{
+		  genop1 = fold_convert (nary->type, genop1);
+		  genop2 = fold_convert (sizetype, genop2);
+		}
 	      else
-		genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
+		{
+		  genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
+		  genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
+		}
 	      folded = fold_build2 (nary->opcode, nary->type,
 				    genop1, genop2);
 	    }
 	    break;
 	{
 	  gimple stmt = gsi_stmt (gsi);
 	  tree forcedname = gimple_get_lhs (stmt);
 	  pre_expr nameexpr;
-	  VEC_safe_push (gimple, heap, inserted_exprs, stmt);
 	  if (TREE_CODE (forcedname) == SSA_NAME)
 	    {
+	      bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
 	      VN_INFO_GET (forcedname)->valnum = forcedname;
 	      VN_INFO (forcedname)->value_id = get_next_value_id ();
 	      nameexpr = get_or_alloc_expr_for_name (forcedname);
 	      add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
 	      if (!in_fre)
 /* Build and insert the assignment of the end result to the temporary
 that we will return.  */
 if (!pretemp || exprtype != TREE_TYPE (pretemp))
 {
-pretemp = create_tmp_var (exprtype, "pretmp");
+pretemp = create_tmp_reg (exprtype, "pretmp");
 get_var_ann (pretemp);
 }
 temp = pretemp;
 add_referenced_var (temp);
-if (TREE_CODE (exprtype) == COMPLEX_TYPE
-|| TREE_CODE (exprtype) == VECTOR_TYPE)
-DECL_GIMPLE_REG_P (temp) = 1;
 newstmt = gimple_build_assign (temp, folded);
 name = make_ssa_name (temp, newstmt);
 gimple_assign_set_lhs (newstmt, name);
 gimple_set_plf (newstmt, NECESSARY, false);
 gimple_seq_add_stmt (stmts, newstmt);
-VEC_safe_push (gimple, heap, inserted_exprs, newstmt);
+bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
 /* All the symbols in NEWEXPR should be put into SSA form.  */
 mark_symbols_for_renaming (newstmt);
 /* Add a value number to the temporary.
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
 	  nophi = true;
 	}
-}
-/* Make sure we are not inserting trapping expressions.  */
-FOR_EACH_EDGE (pred, ei, block->preds)
-{
-bprime = pred->src;
-eprime = avail[bprime->index];
-if (eprime->kind == NARY
-	  && vn_nary_may_trap (PRE_EXPR_NARY (eprime)))
-	return false;
 }
 /* Make the necessary insertions.  */
 FOR_EACH_EDGE (pred, ei, block->preds)
 {
 			  gimple_stmt_iterator gsi;
 			  gsi = gsi_start (stmts);
 			  for (; !gsi_end_p (gsi); gsi_next (&gsi))
 			    {
 			      gimple stmt = gsi_stmt (gsi);
-			      VEC_safe_push (gimple, heap, inserted_exprs, stmt);
+			      tree lhs = gimple_get_lhs (stmt);
+			      if (TREE_CODE (lhs) == SSA_NAME)
+				bitmap_set_bit (inserted_exprs,
+						SSA_NAME_VERSION (lhs));
 			      gimple_set_plf (stmt, NECESSARY, false);
 			    }
 			  gsi_insert_seq_on_edge (pred, stmts);
 			}
 		      avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
 		  gimple_stmt_iterator gsi;
 		  gsi = gsi_start (stmts);
 		  for (; !gsi_end_p (gsi); gsi_next (&gsi))
 		    {
 		      gimple stmt = gsi_stmt (gsi);
-		      VEC_safe_push (gimple, heap, inserted_exprs, stmt);
+		      tree lhs = gimple_get_lhs (stmt);
+		      if (TREE_CODE (lhs) == SSA_NAME)
+			bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
 		      gimple_set_plf (stmt, NECESSARY, false);
 		    }
 		  gsi_insert_seq_on_edge (pred, stmts);
 		}
 	      avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
 phi = create_phi_node (temp, block);
 gimple_set_plf (phi, NECESSARY, false);
 VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
 VN_INFO (gimple_phi_result (phi))->value_id = val;
-VEC_safe_push (gimple, heap, inserted_exprs, phi);
+bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi)));
-bitmap_set_bit (inserted_phi_names,
-		  SSA_NAME_VERSION (gimple_phi_result (phi)));
 FOR_EACH_EDGE (pred, ei, block->preds)
 {
 pre_expr ae = avail[pred->src->index];
 gcc_assert (get_expr_type (ae) == type
 		  || useless_type_conversion_p (type, get_expr_type (ae)));
 /* Generate values for PHI nodes.  */
 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
 	make_values_for_phi (gsi_stmt (gsi), block);
+BB_MAY_NOTRETURN (block) = 0;
 /* Now compute value numbers and populate value sets with all
 	 the expressions computed in BLOCK.  */
 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  ssa_op_iter iter;
 	  tree op;
 	  stmt = gsi_stmt (gsi);
 	  gimple_set_uid (stmt, stmt_uid++);
+	  /* Cache whether the basic-block has any non-visible side-effect
+	     or control flow.
+	     If this isn't a call or it is the last stmt in the
+	     basic-block then the CFG represents things correctly.  */
+	  if (is_gimple_call (stmt)
+	      && !stmt_ends_bb_p (stmt))
+	    {
+	      /* Non-looping const functions always return normally.
+		 Otherwise the call might not return or have side-effects
+		 that forbids hoisting possibly trapping expressions
+		 before it.  */
+	      int flags = gimple_call_flags (stmt);
+	      if (!(flags & ECF_CONST)
+		  || (flags & ECF_LOOPING_CONST_OR_PURE))
+		BB_MAY_NOTRETURN (block) = 1;
+	    }
 	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
 	    {
 	      pre_expr e = get_or_alloc_expr_for_name (op);
 	  /* We want to perform redundant PHI elimination.  Do so by
 	     replacing the PHI with a single copy if possible.
 	     Do not touch inserted, single-argument or virtual PHIs.  */
 	  if (gimple_phi_num_args (phi) == 1
-	      || !is_gimple_reg (res)
+	      || !is_gimple_reg (res))
-	      || bitmap_bit_p (inserted_phi_names, SSA_NAME_VERSION (res)))
 	    {
 	      gsi_next (&gsi);
 	      continue;
 	    }
 	      fprintf (dump_file, "\n");
 	    }
 	  remove_phi_node (&gsi, false);
+	  if (!bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))
+	      && TREE_CODE (sprime) == SSA_NAME)
+	    gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
 	  if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
 	    sprime = fold_convert (TREE_TYPE (res), sprime);
 	  stmt = gimple_build_assign (res, sprime);
 	  SSA_NAME_DEF_STMT (res) = stmt;
-	  if (TREE_CODE (sprime) == SSA_NAME)
+	  gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
-	    gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
-			    NECESSARY, true);
 	  gsi2 = gsi_after_labels (b);
 	  gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
 	  /* Queue the copy for eventual removal.  */
 	  VEC_safe_push (gimple, heap, to_remove, stmt);
-	  pre_stats.eliminations++;
+	  /* If we inserted this PHI node ourself, it's not an elimination.  */
+	  if (bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
+	    pre_stats.phis--;
+	  else
+	    pre_stats.eliminations++;
 	}
 }
 /* We cannot remove stmts during BB walk, especially not release SSA
 names there as this confuses the VN machinery.  The stmts ending
 up in to_remove are either stores or simple copies.  */
 for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i)
 {
 tree lhs = gimple_assign_lhs (stmt);
+tree rhs = gimple_assign_rhs1 (stmt);
 use_operand_p use_p;
 gimple use_stmt;
 /* If there is a single use only, propagate the equivalency
 	 instead of keeping the copy.  */
 if (TREE_CODE (lhs) == SSA_NAME
+	  && TREE_CODE (rhs) == SSA_NAME
 	  && single_imm_use (lhs, &use_p, &use_stmt)
-	  && may_propagate_copy (USE_FROM_PTR (use_p),
+	  && may_propagate_copy (USE_FROM_PTR (use_p), rhs))
-				 gimple_assign_rhs1 (stmt)))
 	{
-	  SET_USE (use_p, gimple_assign_rhs1 (stmt));
+	  SET_USE (use_p, rhs);
 	  update_stmt (use_stmt);
+	  if (bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (lhs))
+	      && TREE_CODE (rhs) == SSA_NAME)
+	    gimple_set_plf (SSA_NAME_DEF_STMT (rhs), NECESSARY, true);
 	}
 /* If this is a store or a now unused copy, remove it.  */
 if (TREE_CODE (lhs) != SSA_NAME
 	  || has_zero_uses (lhs))
 	{
 	  gsi = gsi_for_stmt (stmt);
 	  unlink_stmt_vdef (stmt);
 	  gsi_remove (&gsi, true);
+	  if (TREE_CODE (lhs) == SSA_NAME)
+	    bitmap_clear_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
 	  release_defs (stmt);
 	}
 }
 VEC_free (gimple, heap, to_remove);
 pass removes any insertions we made that weren't actually used.  */
 static void
 remove_dead_inserted_code (void)
 {
-VEC(gimple,heap) *worklist = NULL;
+bitmap worklist;
-int i;
+unsigned i;
+bitmap_iterator bi;
 gimple t;
-worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs));
+worklist = BITMAP_ALLOC (NULL);
-for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
+EXECUTE_IF_SET_IN_BITMAP (inserted_exprs, 0, i, bi)
 {
+t = SSA_NAME_DEF_STMT (ssa_name (i));
 if (gimple_plf (t, NECESSARY))
-	VEC_quick_push (gimple, worklist, t);
+	bitmap_set_bit (worklist, i);
 }
-while (VEC_length (gimple, worklist) > 0)
+while (!bitmap_empty_p (worklist))
 {
-t = VEC_pop (gimple, worklist);
+i = bitmap_first_set_bit (worklist);
+bitmap_clear_bit (worklist, i);
+t = SSA_NAME_DEF_STMT (ssa_name (i));
 /* PHI nodes are somewhat special in that each PHI alternative has
 	 data and control dependencies.  All the statements feeding the
 	 PHI node's arguments are always necessary. */
 if (gimple_code (t) == GIMPLE_PHI)
 	{
 	  unsigned k;
-	  VEC_reserve (gimple, heap, worklist, gimple_phi_num_args (t));
 	  for (k = 0; k < gimple_phi_num_args (t); k++)
 	    {
 	      tree arg = PHI_ARG_DEF (t, k);
 	      if (TREE_CODE (arg) == SSA_NAME)
 		{
 		  gimple n = mark_operand_necessary (arg);
 		  if (n)
-		    VEC_quick_push (gimple, worklist, n);
+		    bitmap_set_bit (worklist, SSA_NAME_VERSION (arg));
 		}
 	    }
 	}
 else
 	{
 	  FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
 	    {
 	      gimple n = mark_operand_necessary (use);
 	      if (n)
-		VEC_safe_push (gimple, heap, worklist, n);
+		bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
 	    }
 	}
 }
-for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
+EXECUTE_IF_SET_IN_BITMAP (inserted_exprs, 0, i, bi)
 {
+t = SSA_NAME_DEF_STMT (ssa_name (i));
 if (!gimple_plf (t, NECESSARY))
 	{
 	  gimple_stmt_iterator gsi;
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	      gsi_remove (&gsi, true);
 	      release_defs (t);
 	    }
 	}
 }
-VEC_free (gimple, heap, worklist);
+BITMAP_FREE (worklist);
 }
+/* Compute a reverse post-order in *POST_ORDER.  If INCLUDE_ENTRY_EXIT is
+true, then then ENTRY_BLOCK and EXIT_BLOCK are included.  Returns
+the number of visited blocks.  */
+static int
+my_rev_post_order_compute (int *post_order, bool include_entry_exit)
+{
+edge_iterator *stack;
+int sp;
+int post_order_num = 0;
+sbitmap visited;
+if (include_entry_exit)
+post_order[post_order_num++] = EXIT_BLOCK;
+/* Allocate stack for back-tracking up CFG.  */
+stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+sp = 0;
+/* Allocate bitmap to track nodes that have been visited.  */
+visited = sbitmap_alloc (last_basic_block);
+/* None of the nodes in the CFG have been visited yet.  */
+sbitmap_zero (visited);
+/* Push the last edge on to the stack.  */
+stack[sp++] = ei_start (EXIT_BLOCK_PTR->preds);
+while (sp)
+{
+edge_iterator ei;
+basic_block src;
+basic_block dest;
+/* Look at the edge on the top of the stack.  */
+ei = stack[sp - 1];
+src = ei_edge (ei)->src;
+dest = ei_edge (ei)->dest;
+/* Check if the edge destination has been visited yet.  */
+if (src != ENTRY_BLOCK_PTR && ! TEST_BIT (visited, src->index))
+{
+/* Mark that we have visited the destination.  */
+SET_BIT (visited, src->index);
+if (EDGE_COUNT (src->preds) > 0)
+/* Since the DEST node has been visited for the first
+time, check its successors.  */
+stack[sp++] = ei_start (src->preds);
+else
+post_order[post_order_num++] = src->index;
+}
+else
+{
+if (ei_one_before_end_p (ei) && dest != EXIT_BLOCK_PTR)
+post_order[post_order_num++] = dest->index;
+if (!ei_one_before_end_p (ei))
+ei_next (&stack[sp - 1]);
+else
+sp--;
+}
+}
+if (include_entry_exit)
+post_order[post_order_num++] = ENTRY_BLOCK;
+free (stack);
+sbitmap_free (visited);
+return post_order_num;
+}
 /* Initialize data structures used by PRE.  */
 static void
 init_pre (bool do_fre)
 expressions = NULL;
 VEC_safe_push (pre_expr, heap, expressions, NULL);
 value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
 VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
 			 get_max_value_id() + 1);
+name_to_id = NULL;
 in_fre = do_fre;
-inserted_exprs = NULL;
+inserted_exprs = BITMAP_ALLOC (NULL);
 need_creation = NULL;
 pretemp = NULL_TREE;
 storetemp = NULL_TREE;
 prephitemp = NULL_TREE;
 connect_infinite_loops_to_exit ();
 memset (&pre_stats, 0, sizeof (pre_stats));
 postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
-post_order_compute (postorder, false, false);
+my_rev_post_order_compute (postorder, false);
 FOR_ALL_BB (bb)
 bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
 calculate_dominance_info (CDI_POST_DOMINATORS);
 calculate_dominance_info (CDI_DOMINATORS);
 bitmap_obstack_initialize (&grand_bitmap_obstack);
-inserted_phi_names = BITMAP_ALLOC (&grand_bitmap_obstack);
 phi_translate_table = htab_create (5110, expr_pred_trans_hash,
 				     expr_pred_trans_eq, free);
 expression_to_id = htab_create (num_ssa_names * 3,
 				  pre_expr_hash,
 				  pre_expr_eq, NULL);
 {
 basic_block bb;
 free (postorder);
 VEC_free (bitmap_set_t, heap, value_expressions);
-VEC_free (gimple, heap, inserted_exprs);
+BITMAP_FREE (inserted_exprs);
 VEC_free (gimple, heap, need_creation);
 bitmap_obstack_release (&grand_bitmap_obstack);
 free_alloc_pool (bitmap_set_pool);
 free_alloc_pool (pre_expr_pool);
 htab_delete (phi_translate_table);
 htab_delete (expression_to_id);
+VEC_free (unsigned, heap, name_to_id);
 FOR_ALL_BB (bb)
 {
 free (bb->aux);
 bb->aux = NULL;
 loop_optimizer_init (LOOPS_NORMAL);
 if (!run_scc_vn (do_fre))
 {
 if (!do_fre)
-	{
+	loop_optimizer_finalize ();
-	  remove_dead_inserted_code ();
-	  loop_optimizer_finalize ();
-	}
 return 0;
 }
 init_pre (do_fre);
 scev_initialize ();
 /* Collect and value number expressions computed in each basic block.  */
 compute_avail ();
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 compute_antic ();
 insert ();
 }
+/* Make sure to remove fake edges before committing our inserts.
+This makes sure we don't end up with extra critical edges that
+we would need to split.  */
+remove_fake_exit_edges ();
+gsi_commit_edge_inserts ();
 /* Remove all the redundant expressions.  */
 todo |= eliminate ();
 statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
 statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
 statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
 statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
 statistics_counter_event (cfun, "Constified", pre_stats.constified);
-/* Make sure to remove fake edges before committing our inserts.
-This makes sure we don't end up with extra critical edges that
-we would need to split.  */
-remove_fake_exit_edges ();
-gsi_commit_edge_inserts ();
 clear_expression_ids ();
 free_scc_vn ();
 if (!do_fre)
 remove_dead_inserted_code ();

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-pre.c @ 63:b7f97abdc517 gcc-4.6-20100522