/* SSA-PRE for trees.
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ 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>
#include "langhooks.h"
#include "cfgloop.h"
#include "tree-ssa-sccvn.h"
+#include "tree-scalar-evolution.h"
#include "params.h"
#include "dbgcnt.h"
/* Representation of expressions on value numbers:
- Expressions consisting of value numbers are represented the same
+ Expressions consisting of value numbers are represented the same
way as our VN internally represents them, with an additional
"pre_expr" wrapping around them in order to facilitate storing all
of the expressions in the same sets. */
return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
PRE_EXPR_REFERENCE (e2));
default:
- abort();
+ gcc_unreachable ();
}
}
case CONSTANT:
return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
case NAME:
- return iterative_hash_expr (PRE_EXPR_NAME (e), 0);
+ return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
case NARY:
- return vn_nary_op_compute_hash (PRE_EXPR_NARY (e));
+ return PRE_EXPR_NARY (e)->hashcode;
case REFERENCE:
- return vn_reference_compute_hash (PRE_EXPR_REFERENCE (e));
+ return PRE_EXPR_REFERENCE (e)->hashcode;
default:
- abort ();
+ gcc_unreachable ();
}
}
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. */
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);
- gcc_assert (!*slot);
- *slot = expr;
+ if (expr->kind == NAME)
+ {
+ 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;
}
{
void **slot;
- slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
- if (!slot)
- return 0;
- return ((pre_expr)*slot)->id;
+ if (expr->kind == NAME)
+ {
+ unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
+ 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
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);
- if (result_id != 0)
- {
- pool_free (pre_expr_pool, result);
- result = expression_for_id (result_id);
- return result;
- }
- get_or_alloc_expression_id (result);
+ alloc_expression_id (result);
return result;
}
#define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
+#define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
+ EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi))
+
/* Mapping from value id to expressions with that value_id. */
DEF_VEC_P (bitmap_set_t);
DEF_VEC_ALLOC_P (bitmap_set_t, heap);
the current iteration. */
bitmap_set_t new_sets;
+ /* 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 ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
#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 BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
+#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
-/* Maximal set of values, used to initialize the ANTIC problem, which
- is an intersection problem. */
-static bitmap_set_t maximal_set;
-
/* Basic block list in postorder. */
static int *postorder;
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);
+static unsigned int get_expr_value_id (pre_expr);
/* We can add and remove elements and entries to and from sets
and hash tables, so we use alloc pools for them. */
cleaned up. */
static bitmap need_eh_cleanup;
-/* Which expressions have been seen during a given phi translation. */
-static bitmap seen_during_translate;
-
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
{
bitmap_set_t set;
+ gcc_assert (get_expr_value_id (e) == v);
+
if (v >= VEC_length (bitmap_set_t, value_expressions))
{
VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
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 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
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. */
}
-/* A comparison function for use in qsort to top sort a bitmap set. Simply
- subtracts value ids, since they are created with leaves before
- their parent users (IE topological order). */
-
-static int
-value_id_compare (const void *pa, const void *pb)
-{
- const unsigned int vha = get_expr_value_id (*((const pre_expr *)pa));
- const unsigned int vhb = get_expr_value_id (*((const pre_expr *)pb));
-
- return vha - vhb;
-}
-
/* Generate an topological-ordered array of bitmap set SET. */
static VEC(pre_expr, heap) *
sorted_array_from_bitmap_set (bitmap_set_t set)
{
- unsigned int i;
- bitmap_iterator bi;
- VEC(pre_expr, heap) *result = NULL;
+ unsigned int i, j;
+ bitmap_iterator bi, bj;
+ VEC(pre_expr, heap) *result;
- FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
- VEC_safe_push (pre_expr, heap, result, expression_for_id (i));
+ /* Pre-allocate roughly enough space for the array. */
+ result = VEC_alloc (pre_expr, heap, bitmap_count_bits (set->values));
- qsort (VEC_address (pre_expr, result), VEC_length (pre_expr, result),
- sizeof (pre_expr), value_id_compare);
+ 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
+ the expressions and sorting it by value-id, we walk the values
+ and check in the reverse mapping that tells us what expressions
+ have a given value, to filter those in our set. As a result,
+ the expressions are inserted in value-id order, which means
+ topological order.
+
+ If this is somehow a significant lose for some cases, we can
+ choose which set to walk based on the set size. */
+ bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);
+ FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)
+ {
+ if (bitmap_bit_p (set->expressions, j))
+ VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
+ }
+ }
return result;
}
{
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))
- bitmap_insert_into_set (set, expr);
+ /* If the value membership changed, add the expression. */
+ if (bitmap_set_bit (set->values, val))
+ bitmap_set_bit (set->expressions, expr->id);
}
/* Print out EXPR to outfile. */
VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
i++)
{
+ bool closebrace = false;
if (vro->opcode != SSA_NAME
&& TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
- fprintf (outfile, "%s ", tree_code_name [vro->opcode]);
+ {
+ fprintf (outfile, "%s", tree_code_name [vro->opcode]);
+ if (vro->op0)
+ {
+ fprintf (outfile, "<");
+ closebrace = true;
+ }
+ }
if (vro->op0)
{
- if (vro->op1)
- fprintf (outfile, "<");
print_generic_expr (outfile, vro->op0, 0);
if (vro->op1)
{
fprintf (outfile, ",");
print_generic_expr (outfile, vro->op1, 0);
}
- if (vro->op1)
- fprintf (outfile, ">");
+ if (vro->op2)
+ {
+ fprintf (outfile, ",");
+ print_generic_expr (outfile, vro->op2, 0);
+ }
}
+ if (closebrace)
+ fprintf (outfile, ">");
if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
fprintf (outfile, ",");
}
fprintf (outfile, "}");
+ if (ref->vuse)
+ {
+ fprintf (outfile, "@");
+ print_generic_expr (outfile, ref->vuse, 0);
+ }
}
break;
}
{
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);
- if (result_id != 0)
- {
- pool_free (pre_expr_pool, newexpr);
- newexpr = expression_for_id (result_id);
- return newexpr;
- }
+ alloc_expression_id (newexpr);
value_id = get_or_alloc_constant_value_id (constant);
- get_or_alloc_expression_id (newexpr);
add_to_value (value_id, newexpr);
return newexpr;
}
vn_nary_op_t nary = PRE_EXPR_NARY (e);
switch (TREE_CODE_CLASS (nary->opcode))
{
+ case tcc_expression:
+ if (nary->opcode == TRUTH_NOT_EXPR)
+ goto do_unary;
+ if (nary->opcode != TRUTH_AND_EXPR
+ && nary->opcode != TRUTH_OR_EXPR
+ && nary->opcode != TRUTH_XOR_EXPR)
+ return e;
+ /* Fallthrough. */
case tcc_binary:
+ case tcc_comparison:
{
/* We have to go from trees to pre exprs to value ids to
constants. */
tree naryop0 = nary->op[0];
tree naryop1 = nary->op[1];
- tree const0, const1, result;
- if (is_gimple_min_invariant (naryop0))
- const0 = naryop0;
- else
+ tree result;
+ if (!is_gimple_min_invariant (naryop0))
{
pre_expr rep0 = get_or_alloc_expr_for (naryop0);
unsigned int vrep0 = get_expr_value_id (rep0);
- const0 = get_constant_for_value_id (vrep0);
+ tree const0 = get_constant_for_value_id (vrep0);
+ if (const0)
+ naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
}
- if (is_gimple_min_invariant (naryop1))
- const1 = naryop1;
- else
+ if (!is_gimple_min_invariant (naryop1))
{
pre_expr rep1 = get_or_alloc_expr_for (naryop1);
unsigned int vrep1 = get_expr_value_id (rep1);
- const1 = get_constant_for_value_id (vrep1);
- }
- result = NULL;
- if (const0 && const1)
- {
- tree type1 = TREE_TYPE (nary->op[0]);
- tree type2 = TREE_TYPE (nary->op[1]);
- const0 = fold_convert (type1, const0);
- const1 = fold_convert (type2, const1);
- result = fold_binary (nary->opcode, nary->type, const0,
- const1);
+ tree const1 = get_constant_for_value_id (vrep1);
+ if (const1)
+ naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
}
+ result = fold_binary (nary->opcode, nary->type,
+ naryop0, naryop1);
if (result && is_gimple_min_invariant (result))
return get_or_alloc_expr_for_constant (result);
+ /* We might have simplified the expression to a
+ SSA_NAME for example from x_1 * 1. But we cannot
+ insert a PHI for x_1 unconditionally as x_1 might
+ not be available readily. */
return e;
}
+ case tcc_reference:
+ if (nary->opcode != REALPART_EXPR
+ && nary->opcode != IMAGPART_EXPR
+ && nary->opcode != VIEW_CONVERT_EXPR)
+ return e;
+ /* Fallthrough. */
case tcc_unary:
+do_unary:
{
- /* We have to go from trees to pre exprs to value ids to
- constants. */
+ /* We have to go from trees to pre exprs to value ids to
+ constants. */
tree naryop0 = nary->op[0];
tree const0, result;
if (is_gimple_min_invariant (naryop0))
const0 = fold_convert (type1, const0);
result = fold_unary (nary->opcode, nary->type, const0);
}
-
if (result && is_gimple_min_invariant (result))
return get_or_alloc_expr_for_constant (result);
return e;
case REFERENCE:
{
vn_reference_t ref = PRE_EXPR_REFERENCE (e);
- VEC (vn_reference_op_s, heap) *operands = ref->operands;
- vn_reference_op_t op;
-
- /* Try to simplify the translated expression if it is
- 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;
- }
+ tree folded;
+ if ((folded = fully_constant_vn_reference_p (ref)))
+ return get_or_alloc_expr_for_constant (folded);
+ return e;
+ }
default:
return e;
}
return e;
}
-/* Translate the vuses in the VUSES vector backwards through phi nodes
- in PHIBLOCK, so that they have the value they would have in
- BLOCK. */
+/* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
+ it has the value it would have in BLOCK. Set *SAME_VALID to true
+ in case the new vuse doesn't change the value id of the OPERANDS. */
-static VEC(tree, gc) *
-translate_vuses_through_block (VEC (tree, gc) *vuses,
- basic_block phiblock,
- basic_block block)
+static tree
+translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands,
+ alias_set_type set, tree type, tree vuse,
+ basic_block phiblock,
+ basic_block block, bool *same_valid)
{
- tree oldvuse;
- VEC(tree, gc) *result = NULL;
- int i;
+ gimple phi = SSA_NAME_DEF_STMT (vuse);
+ ao_ref ref;
+ edge e = NULL;
+ bool use_oracle;
+
+ *same_valid = true;
+
+ if (gimple_bb (phi) != phiblock)
+ return vuse;
- for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
+ use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands);
+
+ /* Use the alias-oracle to find either the PHI node in this block,
+ the first VUSE used in this block that is equivalent to vuse or
+ the first VUSE which definition in this block kills the value. */
+ if (gimple_code (phi) == GIMPLE_PHI)
+ e = find_edge (block, phiblock);
+ else if (use_oracle)
+ while (!stmt_may_clobber_ref_p_1 (phi, &ref))
+ {
+ vuse = gimple_vuse (phi);
+ phi = SSA_NAME_DEF_STMT (vuse);
+ if (gimple_bb (phi) != phiblock)
+ return vuse;
+ if (gimple_code (phi) == GIMPLE_PHI)
+ {
+ e = find_edge (block, phiblock);
+ break;
+ }
+ }
+ else
+ return NULL_TREE;
+
+ if (e)
{
- gimple phi = SSA_NAME_DEF_STMT (oldvuse);
- if (gimple_code (phi) == GIMPLE_PHI
- && gimple_bb (phi) == phiblock)
+ if (use_oracle)
{
- edge e = find_edge (block, gimple_bb (phi));
- if (e)
- {
- tree def = PHI_ARG_DEF (phi, e->dest_idx);
- if (def != oldvuse)
- {
- if (!result)
- result = VEC_copy (tree, gc, vuses);
- VEC_replace (tree, result, i, def);
- }
- }
+ bitmap visited = NULL;
+ /* Try to find a vuse that dominates this phi node by skipping
+ non-clobbering statements. */
+ vuse = get_continuation_for_phi (phi, &ref, &visited);
+ if (visited)
+ BITMAP_FREE (visited);
}
+ else
+ vuse = NULL_TREE;
+ if (!vuse)
+ {
+ /* If we didn't find any, the value ID can't stay the same,
+ but return the translated vuse. */
+ *same_valid = false;
+ vuse = PHI_ARG_DEF (phi, e->dest_idx);
+ }
+ /* ??? We would like to return vuse here as this is the canonical
+ upmost vdef that this reference is associated with. But during
+ insertion of the references into the hash tables we only ever
+ directly insert with their direct gimple_vuse, hence returning
+ something else would make us not find the other expression. */
+ return PHI_ARG_DEF (phi, e->dest_idx);
}
- /* We avoid creating a new copy of the vuses unless something
- actually changed, so result can be NULL. */
- if (result)
- {
- sort_vuses (result);
- return result;
- }
- return vuses;
-
+ return NULL_TREE;
}
-/* Like find_leader, but checks for the value existing in SET1 *or*
+/* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
SET2. This is used to avoid making a set consisting of the union
of PA_IN and ANTIC_IN during insert. */
case CONSTANT:
return TREE_TYPE (PRE_EXPR_CONSTANT (e));
case REFERENCE:
- {
- vn_reference_op_t vro;
-
- gcc_assert (PRE_EXPR_REFERENCE (e)->operands);
- vro = VEC_index (vn_reference_op_s,
- PRE_EXPR_REFERENCE (e)->operands,
- 0);
- /* We don't store type along with COMPONENT_REF because it is
- always the same as FIELD_DECL's type. */
- if (!vro->type)
- {
- gcc_assert (vro->opcode == COMPONENT_REF);
- return TREE_TYPE (vro->op0);
- }
- return vro->type;
- }
-
+ return PRE_EXPR_REFERENCE (e)->type;
case NARY:
return PRE_EXPR_NARY (e)->type;
}
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);
}
+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. SEEN is a bitmap saying which expression we have
- translated since we started translation of the toplevel expression.
- Return NULL if we can't find a leader for each part of the
- translated expression. */
+ 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_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
- basic_block pred, basic_block phiblock, bitmap seen)
+ 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;
-
- /* Prevent cycles when we have recursively dependent leaders. This
- can only happen when phi translating the maximal set. */
- if (seen)
- {
- unsigned int expr_id = get_expression_id (expr);
- if (bitmap_bit_p (seen, expr_id))
- return NULL;
- bitmap_set_bit (seen, expr_id);
- }
-
switch (expr->kind)
{
- /* Constants contain no values that need translation. */
- case CONSTANT:
- return expr;
-
case NARY:
{
unsigned int i;
continue;
else
{
+ pre_expr leader, result;
unsigned int op_val_id = VN_INFO (newnary.op[i])->value_id;
- pre_expr leader = find_leader_in_sets (op_val_id, set1, set2);
- pre_expr result = phi_translate_1 (leader, set1, set2,
- pred, phiblock, seen);
+ leader = find_leader_in_sets (op_val_id, set1, set2);
+ result = phi_translate (leader, set1, set2, pred, phiblock);
if (result && result != leader)
{
tree name = get_representative_for (result);
if (changed)
{
pre_expr constant;
+ unsigned int new_val_id;
tree result = vn_nary_op_lookup_pieces (newnary.length,
newnary.opcode,
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;
}
add_to_value (new_val_id, expr);
}
- phi_trans_add (oldexpr, expr, pred);
return expr;
}
break;
{
vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
VEC (vn_reference_op_s, heap) *operands = ref->operands;
- VEC (tree, gc) *vuses = ref->vuses;
- VEC (tree, gc) *newvuses = vuses;
+ tree vuse = ref->vuse;
+ tree newvuse = vuse;
VEC (vn_reference_op_s, heap) *newoperands = NULL;
- bool changed = false;
- unsigned int i;
+ bool changed = false, same_valid = true;
+ unsigned int i, j;
vn_reference_op_t operand;
vn_reference_t newref;
- for (i = 0; VEC_iterate (vn_reference_op_s, operands, i, operand); i++)
+ for (i = 0, j = 0;
+ VEC_iterate (vn_reference_op_s, operands, i, operand); i++, j++)
{
pre_expr opresult;
pre_expr leader;
{
unsigned int op_val_id = VN_INFO (op0)->value_id;
leader = find_leader_in_sets (op_val_id, set1, set2);
- opresult = phi_translate_1 (leader, set1, set2,
- pred, phiblock, seen);
+ opresult = phi_translate (leader, set1, set2, pred, phiblock);
if (opresult && opresult != leader)
{
tree name = get_representative_for (opresult);
{
unsigned int op_val_id = VN_INFO (op1)->value_id;
leader = find_leader_in_sets (op_val_id, set1, set2);
- opresult = phi_translate_1 (leader, set1, set2,
- pred, phiblock, seen);
+ opresult = phi_translate (leader, set1, set2, pred, phiblock);
if (opresult && opresult != leader)
{
tree name = get_representative_for (opresult);
else if (!opresult)
break;
}
+ /* We can't possibly insert these. */
+ else if (op1 && !is_gimple_min_invariant (op1))
+ break;
changed |= op1 != oldop1;
if (op2 && TREE_CODE (op2) == SSA_NAME)
{
unsigned int op_val_id = VN_INFO (op2)->value_id;
leader = find_leader_in_sets (op_val_id, set1, set2);
- opresult = phi_translate_1 (leader, set1, set2,
- pred, phiblock, seen);
+ opresult = phi_translate (leader, set1, set2, pred, phiblock);
if (opresult && opresult != leader)
{
tree name = get_representative_for (opresult);
else if (!opresult)
break;
}
+ /* We can't possibly insert these. */
+ else if (op2 && !is_gimple_min_invariant (op2))
+ break;
changed |= op2 != oldop2;
if (!newoperands)
newop.op0 = op0;
newop.op1 = op1;
newop.op2 = op2;
- VEC_replace (vn_reference_op_s, newoperands, i, &newop);
+ VEC_replace (vn_reference_op_s, newoperands, j, &newop);
+ /* If it transforms from an SSA_NAME to an address, fold with
+ a preceding indirect reference. */
+ if (j > 0 && op0 && TREE_CODE (op0) == ADDR_EXPR
+ && VEC_index (vn_reference_op_s,
+ newoperands, j - 1)->opcode == INDIRECT_REF)
+ vn_reference_fold_indirect (&newoperands, &j);
}
if (i != VEC_length (vn_reference_op_s, operands))
{
return NULL;
}
- newvuses = translate_vuses_through_block (vuses, phiblock, pred);
- changed |= newvuses != vuses;
+ if (vuse)
+ {
+ newvuse = translate_vuse_through_block (newoperands,
+ ref->set, ref->type,
+ vuse, phiblock, pred,
+ &same_valid);
+ if (newvuse == NULL_TREE)
+ {
+ VEC_free (vn_reference_op_s, heap, newoperands);
+ return NULL;
+ }
+ }
- if (changed)
+ if (changed || newvuse != vuse)
{
unsigned int new_val_id;
pre_expr constant;
- tree result = vn_reference_lookup_pieces (newvuses,
+ 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))
}
else
{
- new_val_id = get_next_value_id ();
- VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
- get_max_value_id() + 1);
- newref = vn_reference_insert_pieces (newvuses,
+ if (changed || !same_valid)
+ {
+ new_val_id = get_next_value_id ();
+ VEC_safe_grow_cleared (bitmap_set_t, heap,
+ value_expressions,
+ get_max_value_id() + 1);
+ }
+ else
+ new_val_id = ref->value_id;
+ newref = vn_reference_insert_pieces (newvuse, ref->set,
+ ref->type,
newoperands,
result, new_val_id);
newoperands = NULL;
add_to_value (new_val_id, expr);
}
VEC_free (vn_reference_op_s, heap, newoperands);
- phi_trans_add (oldexpr, expr, pred);
return expr;
}
break;
tree def = PHI_ARG_DEF (phi, e->dest_idx);
pre_expr newexpr;
+ if (TREE_CODE (def) == SSA_NAME)
+ def = VN_INFO (def)->valnum;
+
/* Handle constant. */
if (is_gimple_min_invariant (def))
return get_or_alloc_expr_for_constant (def);
}
}
-/* 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. */
+/* 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)
{
- bitmap_clear (seen_during_translate);
- return phi_translate_1 (expr, set1, set2, pred, phiblock,
- seen_during_translate);
+ 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. */
pre_expr expr;
int i;
- if (!phi_nodes (phiblock))
+ if (gimple_seq_empty_p (phi_nodes (phiblock)))
{
bitmap_set_copy (dest, set);
return;
{
pre_expr translated;
translated = phi_translate (expr, set, NULL, pred, phiblock);
+ if (!translated)
+ continue;
- /* Don't add constants or empty translations to the cache, since
- we won't look them up that way, or use the result, anyway. */
- if (translated && !value_id_constant_p (get_expr_value_id (translated)))
- phi_trans_add (expr, translated, pred);
-
- if (translated != NULL)
+ /* We might end up with multiple expressions from SET being
+ translated to the same value. In this case we do not want
+ 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);
static bool
value_dies_in_block_x (pre_expr expr, basic_block block)
{
- int i;
- tree vuse;
- VEC (tree, gc) *vuses = PRE_EXPR_REFERENCE (expr)->vuses;
+ tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
+ vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
+ gimple def;
+ gimple_stmt_iterator gsi;
+ unsigned id = get_expression_id (expr);
+ bool res = false;
+ ao_ref ref;
+
+ if (!vuse)
+ return false;
- /* Conservatively, a value dies if it's vuses are defined in this
- block, unless they come from phi nodes (which are merge operations,
- rather than stores. */
- for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+ /* Lookup a previously calculated result. */
+ if (EXPR_DIES (block)
+ && bitmap_bit_p (EXPR_DIES (block), id * 2))
+ return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
+
+ /* A memory expression {e, VUSE} dies in the block if there is a
+ statement that may clobber e. If, starting statement walk from the
+ top of the basic block, a statement uses VUSE there can be no kill
+ inbetween that use and the original statement that loaded {e, VUSE},
+ so we can stop walking. */
+ ref.base = NULL_TREE;
+ for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple def = SSA_NAME_DEF_STMT (vuse);
+ tree def_vuse, def_vdef;
+ def = gsi_stmt (gsi);
+ def_vuse = gimple_vuse (def);
+ def_vdef = gimple_vdef (def);
- if (gimple_bb (def) != block)
- continue;
- if (gimple_code (def) == GIMPLE_PHI)
+ /* Not a memory statement. */
+ if (!def_vuse)
continue;
- return true;
+
+ /* Not a may-def. */
+ if (!def_vdef)
+ {
+ /* A load with the same VUSE, we're done. */
+ if (def_vuse == vuse)
+ break;
+
+ continue;
+ }
+
+ /* Init ref only if we really need it. */
+ if (ref.base == NULL_TREE
+ && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
+ refx->operands))
+ {
+ res = true;
+ break;
+ }
+ /* If the statement may clobber expr, it dies. */
+ if (stmt_may_clobber_ref_p_1 (def, &ref))
+ {
+ res = true;
+ break;
+ }
}
- return false;
+
+ /* Remember the result. */
+ if (!EXPR_DIES (block))
+ EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
+ bitmap_set_bit (EXPR_DIES (block), id * 2);
+ if (res)
+ bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
+
+ return res;
}
ONLY SET2 CAN BE NULL.
This means that we have a leader for each part of the expression
(if it consists of values), or the expression is an SSA_NAME.
- For loads/calls, we also see if the vuses are killed in this block.
-*/
+ For loads/calls, we also see if the vuse is killed in this block. */
static bool
valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
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;
if (!vro_valid_in_sets (set1, set2, vro))
return false;
}
+ if (ref->vuse)
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
+ if (!gimple_nop_p (def_stmt)
+ && gimple_bb (def_stmt) != block
+ && !dominated_by_p (CDI_DOMINATORS,
+ block, gimple_bb (def_stmt)))
+ return false;
+ }
return !value_dies_in_block_x (expr, block);
}
default:
{
VEC(basic_block, heap) * worklist;
size_t i;
- basic_block bprime, first;
+ basic_block bprime, first = NULL;
worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
FOR_EACH_EDGE (e, ei, block->succs)
- VEC_quick_push (basic_block, worklist, e->dest);
- first = VEC_index (basic_block, worklist, 0);
-
- if (phi_nodes (first))
{
- bitmap_set_t from = ANTIC_IN (first);
-
- if (!BB_VISITED (first))
- from = maximal_set;
- phi_translate_set (ANTIC_OUT, from, block, first);
+ if (!first
+ && BB_VISITED (e->dest))
+ first = e->dest;
+ else if (BB_VISITED (e->dest))
+ VEC_quick_push (basic_block, worklist, e->dest);
}
- else
+
+ /* Of multiple successors we have to have visited one already. */
+ if (!first)
{
- if (!BB_VISITED (first))
- bitmap_set_copy (ANTIC_OUT, maximal_set);
- else
- bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
+ SET_BIT (changed_blocks, block->index);
+ BB_VISITED (block) = 0;
+ BB_DEFERRED (block) = 1;
+ changed = true;
+ VEC_free (basic_block, heap, worklist);
+ goto maybe_dump_sets;
}
- for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
+ 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 ();
- bitmap_set_t from = ANTIC_IN (bprime);
-
- if (!BB_VISITED (bprime))
- from = maximal_set;
- phi_translate_set (tmp, from, block, bprime);
+ phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
bitmap_set_and (ANTIC_OUT, tmp);
bitmap_set_free (tmp);
}
else
- {
- if (!BB_VISITED (bprime))
- bitmap_set_and (ANTIC_OUT, maximal_set);
- else
- bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
- }
+ bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
}
VEC_free (basic_block, heap, worklist);
}
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);
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 ();
fprintf (dump_file, "Starting iteration %d\n", num_iterations);
num_iterations++;
changed = false;
- for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
+ for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
{
if (TEST_BIT (changed_blocks, postorder[i]))
{
fprintf (dump_file, "Starting iteration %d\n", num_iterations);
num_iterations++;
changed = false;
- for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
+ for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--)
{
if (TEST_BIT (changed_blocks, postorder[i]))
{
return false;
}
-/* Return true if OP is an exception handler related operation, such as
- FILTER_EXPR or EXC_PTR_EXPR. */
-
-static bool
-is_exception_related (gimple stmt)
-{
- return (is_gimple_assign (stmt)
- && (gimple_assign_rhs_code (stmt) == FILTER_EXPR
- || gimple_assign_rhs_code (stmt) == EXC_PTR_EXPR));
-}
-
-/* Return true if OP is a tree which we can perform PRE on
- on. This may not match the operations we can value number, but in
+/* Return true if OP is a tree which we can perform PRE on.
+ This may not match the operations we can value number, but in
a perfect world would. */
static bool
/* 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;
/* Pool allocated fake store expressions are placed onto this
worklist, which, after performing dead code elimination, is walked
{
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,
- ref->operands) - 1);
+ tree fn, *args;
+ 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
- ? build_fold_addr_expr (currop->op0)
- : currop->op0,
+ (TREE_CODE (fn) == FUNCTION_DECL
+ ? build_fold_addr_expr (fn) : fn),
nargs, args);
free (args);
if (sc)
+ CALL_EXPR_STATIC_CHAIN (folded) = sc;
+ return folded;
+ }
+ break;
+ case TARGET_MEM_REF:
+ {
+ vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
+ *operand);
+ pre_expr op0expr;
+ tree genop0 = NULL_TREE;
+ tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
+ stmts, domstmt);
+ if (!baseop)
+ return NULL_TREE;
+ if (currop->op0)
{
- pre_expr scexpr = get_or_alloc_expr_for (sc);
- sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
- if (!sc)
+ op0expr = get_or_alloc_expr_for (currop->op0);
+ genop0 = find_or_generate_expression (block, op0expr,
+ stmts, domstmt);
+ if (!genop0)
return NULL_TREE;
- CALL_EXPR_STATIC_CHAIN (folded) = sc;
}
- return folded;
+ if (DECL_P (baseop))
+ return build6 (TARGET_MEM_REF, currop->type,
+ baseop, NULL_TREE,
+ genop0, currop->op1, currop->op2,
+ unshare_expr (nextop->op1));
+ else
+ return build6 (TARGET_MEM_REF, currop->type,
+ NULL_TREE, baseop,
+ genop0, currop->op1, currop->op2,
+ unshare_expr (nextop->op1));
}
break;
case ADDR_EXPR:
pre_expr op1expr;
tree genop2 = currop->op1;
pre_expr op2expr;
- tree genop3;
+ tree genop3 = currop->op2;
+ pre_expr op3expr;
genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
stmts, domstmt);
if (!genop0)
return NULL_TREE;
if (genop2)
{
- op2expr = get_or_alloc_expr_for (genop2);
- genop2 = find_or_generate_expression (block, op2expr, stmts,
- domstmt);
- if (!genop2)
- return NULL_TREE;
+ /* Drop zero minimum index. */
+ if (tree_int_cst_equal (genop2, integer_zero_node))
+ genop2 = NULL_TREE;
+ else
+ {
+ 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));
+ /* We can't always put a size in units of the element alignment
+ here as the element alignment may be not visible. See
+ PR43783. Simply drop the element size for constant
+ sizes. */
+ if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
+ genop3 = 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;
+ }
}
-
- genop3 = currop->op2;
return build4 (currop->opcode, currop->type, genop0, genop1,
genop2, genop3);
}
gimple_seq *stmts, gimple domstmt, tree type)
{
tree temp, name;
- tree folded, newexpr;
- gimple_seq forced_stmts;
+ tree folded;
+ gimple_seq forced_stmts = NULL;
unsigned int value_id;
gimple_stmt_iterator gsi;
tree exprtype = type ? type : get_expr_type (expr);
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);
}
default:
return NULL_TREE;
}
- folded = fold_convert (exprtype, folded);
+
+ if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
+ folded = fold_convert (exprtype, folded);
+
/* Force the generated expression to be a sequence of GIMPLE
statements.
We have to call unshare_expr because force_gimple_operand may
modify the tree we pass to it. */
- newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
- false, NULL);
+ folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
+ false, NULL);
/* If we have any intermediate expressions to the value sets, add them
to the value sets and chain them in the instruction stream. */
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);
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, newexpr);
+ 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);
}
+/* Returns true if we want to inhibit the insertions of PHI nodes
+ for the given EXPR for basic block BB (a member of a loop).
+ We want to do this, when we fear that the induction variable we
+ create might inhibit vectorization. */
+
+static bool
+inhibit_phi_insertion (basic_block bb, pre_expr expr)
+{
+ vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
+ VEC (vn_reference_op_s, heap) *ops = vr->operands;
+ vn_reference_op_t op;
+ unsigned i;
+
+ /* If we aren't going to vectorize we don't inhibit anything. */
+ if (!flag_tree_vectorize)
+ return false;
+
+ /* Otherwise we inhibit the insertion when the address of the
+ memory reference is a simple induction variable. In other
+ cases the vectorizer won't do anything anyway (either it's
+ loop invariant or a complicated expression). */
+ for (i = 0; VEC_iterate (vn_reference_op_s, ops, i, op); ++i)
+ {
+ switch (op->opcode)
+ {
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ if (TREE_CODE (op->op0) != SSA_NAME)
+ break;
+ /* Fallthru. */
+ case SSA_NAME:
+ {
+ basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
+ affine_iv iv;
+ /* Default defs are loop invariant. */
+ if (!defbb)
+ break;
+ /* Defined outside this loop, also loop invariant. */
+ if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
+ break;
+ /* If it's a simple induction variable inhibit insertion,
+ the vectorizer might be interested in this one. */
+ if (simple_iv (bb->loop_father, bb->loop_father,
+ op->op0, &iv, true))
+ return true;
+ /* No simple IV, vectorizer can't do anything, hence no
+ reason to inhibit the transformation for this operand. */
+ break;
+ }
+ default:
+ break;
+ }
+ }
+ return false;
+}
+
/* Insert the to-be-made-available values of expression EXPRNUM for each
predecessor, stored in AVAIL, into the predecessors of BLOCK, and
merge the result with a phi node, given the same value number as
pre_expr eprime;
edge_iterator ei;
tree type = get_expr_type (expr);
- tree temp, res;
+ tree temp;
gimple phi;
if (dump_file && (dump_flags & TDF_DETAILS))
}
/* Make sure we aren't creating an induction variable. */
- if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
- && expr->kind != REFERENCE)
+ if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
{
bool firstinsideloop = false;
bool secondinsideloop = false;
secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
EDGE_PRED (block, 1)->src);
/* Induction variables only have one edge inside the loop. */
- if (firstinsideloop ^ secondinsideloop)
+ if ((firstinsideloop ^ secondinsideloop)
+ && (expr->kind != REFERENCE
+ || inhibit_phi_insertion (block, expr)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
}
}
-
/* Make the necessary insertions. */
FOR_EACH_EDGE (pred, ei, block->preds)
{
should give us back a constant with the right type.
*/
tree constant = PRE_EXPR_CONSTANT (eprime);
- if (TREE_TYPE (constant) != type)
+ if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
{
tree builtexpr = fold_convert (type, constant);
- if (is_gimple_min_invariant (builtexpr))
- {
- PRE_EXPR_CONSTANT (eprime) = builtexpr;
- }
- else
+ if (!is_gimple_min_invariant (builtexpr))
{
tree forcedexpr = force_gimple_operand (builtexpr,
&stmts, true,
NULL);
- if (is_gimple_min_invariant (forcedexpr))
- {
- PRE_EXPR_CONSTANT (eprime) = forcedexpr;
- }
- else
+ if (!is_gimple_min_invariant (forcedexpr))
{
if (forcedexpr != builtexpr)
{
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);
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);
if (TREE_CODE (type) == COMPLEX_TYPE
|| TREE_CODE (type) == VECTOR_TYPE)
DECL_GIMPLE_REG_P (temp) = 1;
-
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;
+ bitmap_set_bit (inserted_exprs, 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)));
if (ae->kind == CONSTANT)
- add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred);
+ add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
else
- add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred);
- }
- /* If the PHI node is already available, use it. */
- if ((res = vn_phi_lookup (phi)) != NULL_TREE)
- {
- gimple_stmt_iterator gsi = gsi_for_stmt (phi);
- remove_phi_node (&gsi, true);
- release_defs (phi);
- add_to_value (val, get_or_alloc_expr_for_name (res));
- return false;
+ add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
+ UNKNOWN_LOCATION);
}
- 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);
-
newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
add_to_value (val, newphi);
basic_block bprime;
pre_expr eprime = NULL;
edge_iterator ei;
- pre_expr edoubleprime;
+ pre_expr edoubleprime = NULL;
+ bool do_insertion = false;
val = get_expr_value_id (expr);
if (bitmap_set_contains_value (PHI_GEN (block), val))
{
avail[bprime->index] = edoubleprime;
by_some = true;
+ /* We want to perform insertions to remove a redundancy on
+ a path in the CFG we want to optimize for speed. */
+ if (optimize_edge_for_speed_p (pred))
+ do_insertion = true;
if (first_s == NULL)
first_s = edoubleprime;
else if (!pre_expr_eq (first_s, edoubleprime))
already existing along every predecessor, and
it's defined by some predecessor, it is
partially redundant. */
- if (!cant_insert && !all_same && by_some && dbg_cnt (treepre_insert))
+ if (!cant_insert && !all_same && by_some && do_insertion
+ && dbg_cnt (treepre_insert))
{
if (insert_into_preds_of_block (block, get_expression_id (expr),
avail))
pre_stats.constified++;
}
else
- info->valnum = PRE_EXPR_NAME (edoubleprime);
+ info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum;
info->value_id = new_val;
}
}
}
-/* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
- not defined by a phi node.
- PHI nodes can't go in the maximal sets because they are not in
- TMP_GEN, so it is possible to get into non-monotonic situations
- during ANTIC calculation, because it will *add* bits. */
+/* Add OP to EXP_GEN (block), and possibly to the maximal set. */
static void
add_to_exp_gen (basic_block block, tree op)
return;
result = get_or_alloc_expr_for_name (op);
bitmap_value_insert_into_set (EXP_GEN (block), result);
- if (TREE_CODE (op) != SSA_NAME
- || gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_PHI)
- bitmap_value_insert_into_set (maximal_set, result);
}
}
add_to_value (get_expr_value_id (e), e);
bitmap_insert_into_set (PHI_GEN (block), e);
bitmap_value_insert_into_set (AVAIL_OUT (block), e);
+ if (!in_fre)
+ {
+ unsigned i;
+ for (i = 0; i < gimple_phi_num_args (phi); ++i)
+ {
+ tree arg = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ e = get_or_alloc_expr_for_name (arg);
+ add_to_value (get_expr_value_id (e), e);
+ }
+ }
+ }
}
}
basic_block block, son;
basic_block *worklist;
size_t sp = 0;
- tree param;
+ unsigned i;
- /* For arguments with default definitions, we pretend they are
- defined in the entry block. */
- for (param = DECL_ARGUMENTS (current_function_decl);
- param;
- param = TREE_CHAIN (param))
+ /* We pretend that default definitions are defined in the entry block.
+ This includes function arguments and the static chain decl. */
+ for (i = 1; i < num_ssa_names; ++i)
{
- if (gimple_default_def (cfun, param) != NULL)
- {
- tree def = gimple_default_def (cfun, param);
- pre_expr e = get_or_alloc_expr_for_name (def);
-
- add_to_value (get_expr_value_id (e), e);
- if (!in_fre)
- {
- bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
- bitmap_value_insert_into_set (maximal_set, e);
- }
- bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
- }
- }
-
- /* Likewise for the static chain decl. */
- if (cfun->static_chain_decl)
- {
- param = cfun->static_chain_decl;
- if (gimple_default_def (cfun, param) != NULL)
- {
- tree def = gimple_default_def (cfun, param);
- pre_expr e = get_or_alloc_expr_for_name (def);
+ tree name = ssa_name (i);
+ pre_expr e;
+ if (!name
+ || !SSA_NAME_IS_DEFAULT_DEF (name)
+ || has_zero_uses (name)
+ || !is_gimple_reg (name))
+ continue;
- add_to_value (get_expr_value_id (e), e);
- if (!in_fre)
- {
- bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
- bitmap_value_insert_into_set (maximal_set, e);
- }
- bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
- }
+ e = get_or_alloc_expr_for_name (name);
+ add_to_value (get_expr_value_id (e), e);
+ if (!in_fre)
+ bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
+ bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
}
/* Allocate the worklist. */
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))
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);
add_to_value (get_expr_value_id (e), e);
if (!in_fre)
- {
- bitmap_insert_into_set (TMP_GEN (block), e);
- bitmap_value_insert_into_set (maximal_set, e);
- }
+ bitmap_insert_into_set (TMP_GEN (block), e);
bitmap_value_insert_into_set (AVAIL_OUT (block), e);
}
continue;
copy_reference_ops_from_call (stmt, &ops);
- vn_reference_lookup_pieces (shared_vuses_from_stmt (stmt),
+ vn_reference_lookup_pieces (gimple_vuse (stmt), 0,
+ gimple_expr_type (stmt),
ops, &ref, false);
VEC_free (vn_reference_op_s, heap, ops);
if (!ref)
get_or_alloc_expression_id (result);
add_to_value (get_expr_value_id (result), result);
if (!in_fre)
- {
- bitmap_value_insert_into_set (EXP_GEN (block),
- result);
- bitmap_value_insert_into_set (maximal_set, result);
- }
+ bitmap_value_insert_into_set (EXP_GEN (block), result);
continue;
}
switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
{
case tcc_unary:
- if (is_exception_related (stmt))
- continue;
case tcc_binary:
+ case tcc_comparison:
{
vn_nary_op_t nary;
unsigned int i;
vn_reference_op_t vro;
vn_reference_lookup (gimple_assign_rhs1 (stmt),
- shared_vuses_from_stmt (stmt),
- false, &ref);
+ gimple_vuse (stmt),
+ true, &ref);
if (!ref)
continue;
get_or_alloc_expression_id (result);
add_to_value (get_expr_value_id (result), result);
if (!in_fre)
- {
- bitmap_value_insert_into_set (EXP_GEN (block), result);
- bitmap_value_insert_into_set (maximal_set, result);
- }
+ bitmap_value_insert_into_set (EXP_GEN (block), result);
continue;
}
static unsigned int
eliminate (void)
{
+ VEC (gimple, heap) *to_remove = NULL;
basic_block b;
unsigned int todo = 0;
+ gimple_stmt_iterator gsi;
+ gimple stmt;
+ unsigned i;
FOR_EACH_BB (b)
{
- gimple_stmt_iterator i;
-
- for (i = gsi_start_bb (b); !gsi_end_p (i); gsi_next (&i))
+ for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (i);
+ stmt = gsi_stmt (gsi);
/* Lookup the RHS of the expression, see if we have an
available computation for it. If so, replace the RHS with
value is constant, use that constant. */
if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
{
- sprime = fold_convert (TREE_TYPE (lhs),
- VN_INFO (lhs)->valnum);
+ sprime = VN_INFO (lhs)->valnum;
+ if (!useless_type_conversion_p (TREE_TYPE (lhs),
+ TREE_TYPE (sprime)))
+ sprime = fold_convert (TREE_TYPE (lhs), sprime);
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, stmt, 0, 0);
}
pre_stats.eliminations++;
- propagate_tree_value_into_stmt (&i, sprime);
- stmt = gsi_stmt (i);
+ propagate_tree_value_into_stmt (&gsi, sprime);
+ stmt = gsi_stmt (gsi);
update_stmt (stmt);
continue;
}
sprime = fold_convert (gimple_expr_type (stmt), sprime);
pre_stats.eliminations++;
- propagate_tree_value_into_stmt (&i, sprime);
- stmt = gsi_stmt (i);
+ propagate_tree_value_into_stmt (&gsi, sprime);
+ stmt = gsi_stmt (gsi);
update_stmt (stmt);
/* If we removed EH side effects from the statement, clean
}
}
}
+ /* If the statement is a scalar store, see if the expression
+ has the same value number as its rhs. If so, the store is
+ dead. */
+ else if (gimple_assign_single_p (stmt)
+ && !is_gimple_reg (gimple_assign_lhs (stmt))
+ && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
+ {
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree val;
+ val = vn_reference_lookup (gimple_assign_lhs (stmt),
+ gimple_vuse (stmt), true, NULL);
+ if (TREE_CODE (rhs) == SSA_NAME)
+ rhs = VN_INFO (rhs)->valnum;
+ if (val
+ && operand_equal_p (val, rhs, 0))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Deleted redundant store ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
+
+ /* Queue stmt for removal. */
+ VEC_safe_push (gimple, heap, to_remove, stmt);
+ }
+ }
/* Visit COND_EXPRs and fold the comparison with the
available value-numbers. */
else if (gimple_code (stmt) == GIMPLE_COND)
todo = TODO_cleanup_cfg;
}
}
+ /* Visit indirect calls and turn them into direct calls if
+ possible. */
+ if (gimple_code (stmt) == GIMPLE_CALL
+ && TREE_CODE (gimple_call_fn (stmt)) == SSA_NAME)
+ {
+ tree fn = VN_INFO (gimple_call_fn (stmt))->valnum;
+ if (TREE_CODE (fn) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Replacing call target with ");
+ print_generic_expr (dump_file, fn, 0);
+ fprintf (dump_file, " in ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
+
+ gimple_call_set_fn (stmt, fn);
+ update_stmt (stmt);
+ if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
+ {
+ bitmap_set_bit (need_eh_cleanup,
+ gimple_bb (stmt)->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Removed EH side effects.\n");
+ }
+
+ /* Changing an indirect call to a direct call may
+ have exposed different semantics. This may
+ require an SSA update. */
+ todo |= TODO_update_ssa_only_virtuals;
+ }
+ }
+ }
+
+ for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
+ {
+ gimple stmt, phi = gsi_stmt (gsi);
+ tree sprime = NULL_TREE, res = PHI_RESULT (phi);
+ pre_expr sprimeexpr, resexpr;
+ gimple_stmt_iterator gsi2;
+
+ /* 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))
+ {
+ gsi_next (&gsi);
+ continue;
+ }
+
+ resexpr = get_or_alloc_expr_for_name (res);
+ sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
+ get_expr_value_id (resexpr), NULL);
+ if (sprimeexpr)
+ {
+ if (sprimeexpr->kind == CONSTANT)
+ sprime = PRE_EXPR_CONSTANT (sprimeexpr);
+ else if (sprimeexpr->kind == NAME)
+ sprime = PRE_EXPR_NAME (sprimeexpr);
+ else
+ gcc_unreachable ();
+ }
+ if (!sprimeexpr
+ || sprime == res)
+ {
+ gsi_next (&gsi);
+ continue;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Replaced redundant PHI node defining ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, sprime, 0);
+ 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;
+ gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
+
+ 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);
+ /* 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), rhs))
+ {
+ 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);
return todo;
}
static void
remove_dead_inserted_code (void)
{
- VEC(gimple,heap) *worklist = NULL;
- int i;
+ bitmap worklist;
+ unsigned i;
+ bitmap_iterator bi;
gimple t;
- worklist = VEC_alloc (gimple, heap, VEC_length (gimple, inserted_exprs));
- for (i = 0; VEC_iterate (gimple, inserted_exprs, i, t); i++)
+ worklist = BITMAP_ALLOC (NULL);
+ 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
{
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);
{
gimple n = mark_operand_necessary (arg);
if (n)
- VEC_quick_push (gimple, worklist, n);
+ bitmap_set_bit (worklist, SSA_NAME_VERSION (arg));
}
}
}
{
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 (gimple_code (t) == GIMPLE_PHI)
remove_phi_node (&gsi, true);
else
- gsi_remove (&gsi, true);
- release_defs (t);
+ {
+ 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
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;
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);
expression_to_id = htab_create (num_ssa_names * 3,
pre_expr_hash,
pre_expr_eq, NULL);
- seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_pool = create_alloc_pool ("Bitmap sets",
sizeof (struct bitmap_set), 30);
pre_expr_pool = create_alloc_pool ("pre_expr nodes",
TMP_GEN (bb) = bitmap_set_new ();
AVAIL_OUT (bb) = bitmap_set_new ();
}
- maximal_set = in_fre ? NULL : bitmap_set_new ();
need_eh_cleanup = BITMAP_ALLOC (NULL);
}
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)
{
only wants to do full redundancy elimination. */
static unsigned int
-execute_pre (bool do_fre ATTRIBUTE_UNUSED)
+execute_pre (bool do_fre)
{
unsigned int todo = 0;
- do_partial_partial = optimize > 2;
+ do_partial_partial = optimize > 2 && optimize_function_for_speed_p (cfun);
/* This has to happen before SCCVN runs because
loop_optimizer_init may create new phis, etc. */
if (!run_scc_vn (do_fre))
{
if (!do_fre)
- {
- remove_dead_inserted_code ();
- loop_optimizer_finalize ();
- }
-
+ loop_optimizer_finalize ();
+
return 0;
}
- init_pre (do_fre);
+ init_pre (do_fre);
+ scev_initialize ();
/* Collect and value number expressions computed in each basic block. */
compute_avail ();
FOR_ALL_BB (bb)
{
print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
- print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
- bb->index);
- print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
- bb->index);
+ print_bitmap_set (dump_file, PHI_GEN (bb), "phi_gen", bb->index);
+ print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
+ print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
}
}
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, "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 ();
+ scev_finalize ();
fini_pre (do_fre);
return todo;
static unsigned int
do_pre (void)
{
- return TODO_rebuild_alias | execute_pre (false);
+ return execute_pre (false);
}
static bool
gate_pre (void)
{
- /* PRE tends to generate bigger code. */
- return flag_tree_pre != 0 && optimize_function_for_speed_p (cfun);
+ return flag_tree_pre != 0;
}
struct gimple_opt_pass pass_pre =
0, /* static_pass_number */
TV_TREE_PRE, /* tv_id */
PROP_no_crit_edges | PROP_cfg
- | PROP_ssa | PROP_alias, /* properties_required */
+ | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
- 0, /* todo_flags_start */
+ TODO_rebuild_alias, /* todo_flags_start */
TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
| TODO_verify_ssa /* todo_flags_finish */
}
NULL, /* next */
0, /* static_pass_number */
TV_TREE_FRE, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
OSDN Git Service
