X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-ssa-pre.c;h=ac676cd415058467c4a8a35259531f766063176c;hp=336c54ec7004cd68006ed70f85bbefdd1b5f9ef0;hb=03beaa3e3b7b228ee9da2a82310c4c45c411ff1b;hpb=f00b5e356b0d32c82a91371060636a9a3278caac diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 336c54ec700..ac676cd4150 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -1,5 +1,5 @@ /* 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 and Steven Bosscher @@ -45,6 +45,7 @@ along with GCC; see the file COPYING3. If not see #include "langhooks.h" #include "cfgloop.h" #include "tree-ssa-sccvn.h" +#include "tree-scalar-evolution.h" #include "params.h" #include "dbgcnt.h" @@ -134,7 +135,7 @@ along with GCC; see the file COPYING3. If not see /* 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. */ @@ -203,7 +204,7 @@ pre_expr_eq (const void *p1, const void *p2) return vn_reference_eq (PRE_EXPR_REFERENCE (e1), PRE_EXPR_REFERENCE (e2)); default: - abort(); + gcc_unreachable (); } } @@ -216,13 +217,13 @@ pre_expr_hash (const void *p1) 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 (); } } @@ -235,6 +236,7 @@ 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. */ @@ -246,9 +248,23 @@ alloc_expression_id (pre_expr 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; } @@ -265,10 +281,20 @@ lookup_expression_id (const pre_expr expr) { 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 @@ -307,20 +333,21 @@ static alloc_pool pre_expr_pool; 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; } @@ -337,6 +364,9 @@ typedef struct bitmap_set #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); @@ -374,12 +404,18 @@ typedef struct bb_bitmap_sets 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 @@ -389,14 +425,12 @@ typedef struct bb_bitmap_sets #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; @@ -428,12 +462,14 @@ 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); +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. */ @@ -453,9 +489,6 @@ static tree prephitemp; 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. */ @@ -559,6 +592,8 @@ add_to_value (unsigned int v, pre_expr e) { 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, @@ -572,7 +607,7 @@ add_to_value (unsigned int v, pre_expr e) 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. */ @@ -630,9 +665,8 @@ bitmap_remove_from_set (bitmap_set_t set, pre_expr expr) 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 @@ -647,7 +681,7 @@ bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr, 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. */ @@ -669,33 +703,37 @@ bitmap_set_free (bitmap_set_t set) } -/* 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; + + /* Pre-allocate roughly enough space for the array. */ + result = VEC_alloc (pre_expr, heap, bitmap_count_bits (set->values)); - FOR_EACH_EXPR_ID_IN_SET (set, i, bi) - VEC_safe_push (pre_expr, heap, result, expression_for_id (i)); + 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. - qsort (VEC_address (pre_expr, result), VEC_length (pre_expr, result), - sizeof (pre_expr), value_id_compare); + 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; } @@ -854,11 +892,17 @@ 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)) - 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. */ @@ -899,26 +943,42 @@ print_pre_expr (FILE *outfile, const pre_expr expr) 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; } @@ -998,18 +1058,20 @@ 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); - 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; } @@ -1088,47 +1150,59 @@ fully_constant_expression (pre_expr e) 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)) @@ -1146,7 +1220,6 @@ fully_constant_expression (pre_expr e) 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; @@ -1155,57 +1228,95 @@ fully_constant_expression (pre_expr e) return e; } } + case REFERENCE: + { + vn_reference_t ref = PRE_EXPR_REFERENCE (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; + + 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; - for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++) + 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. */ @@ -1232,23 +1343,7 @@ get_expr_type (const pre_expr e) 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; } @@ -1312,7 +1407,7 @@ get_representative_for (const pre_expr e) 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); } @@ -1338,46 +1433,20 @@ get_representative_for (const pre_expr e) +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; @@ -1395,10 +1464,10 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, 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); @@ -1415,6 +1484,7 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, if (changed) { pre_expr constant; + unsigned int new_val_id; tree result = vn_nary_op_lookup_pieces (newnary.length, newnary.opcode, @@ -1424,15 +1494,12 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, 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; @@ -1465,23 +1532,24 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, } add_to_value (new_val_id, expr); } - phi_trans_add (oldexpr, expr, pred); return expr; } break; + case REFERENCE: { 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; @@ -1498,17 +1566,16 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, { 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); if (!name) - return NULL; + break; op0 = name; } else if (!opresult) - return NULL; + break; } changed |= op0 != oldop0; @@ -1516,35 +1583,39 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, { 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); if (!name) - return NULL; + break; op1 = name; } else if (!opresult) - return NULL; + 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); if (!name) - return NULL; + break; op2 = name; } else if (!opresult) - return NULL; + break; } + /* We can't possibly insert these. */ + else if (op2 && !is_gimple_min_invariant (op2)) + break; changed |= op2 != oldop2; if (!newoperands) @@ -1556,24 +1627,51 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, 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)) + { + if (newoperands) + VEC_free (vn_reference_op_s, heap, newoperands); + 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) { - tree result = vn_reference_lookup_pieces (newvuses, - newoperands, - &newref); unsigned int new_val_id; + pre_expr constant; - if (newref) + tree result = vn_reference_lookup_pieces (newvuse, ref->set, + ref->type, + newoperands, + &newref, true); + if (result) VEC_free (vn_reference_op_s, heap, newoperands); if (result && is_gimple_min_invariant (result)) - return get_or_alloc_expr_for_constant (result); + { + gcc_assert (!newoperands); + return get_or_alloc_expr_for_constant (result); + } expr = (pre_expr) pool_alloc (pre_expr_pool); expr->kind = REFERENCE; @@ -1582,26 +1680,42 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, if (newref) { PRE_EXPR_REFERENCE (expr) = newref; + constant = fully_constant_expression (expr); + if (constant != expr) + return constant; + new_val_id = newref->value_id; get_or_alloc_expression_id (expr); } 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; PRE_EXPR_REFERENCE (expr) = newref; + 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); + VEC_free (vn_reference_op_s, heap, newoperands); return expr; } break; + case NAME: { gimple phi = NULL; @@ -1622,6 +1736,9 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, 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); @@ -1640,20 +1757,44 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, } } -/* 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. */ @@ -1666,7 +1807,7 @@ phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred, pre_expr expr; int i; - if (!phi_nodes (phiblock)) + if (gimple_seq_empty_p (phi_nodes (phiblock))) { bitmap_set_copy (dest, set); return; @@ -1677,13 +1818,16 @@ phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred, { 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); @@ -1757,24 +1901,73 @@ bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt) 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) + /* Not a memory statement. */ + if (!def_vuse) continue; - if (gimple_code (def) == GIMPLE_PHI) - 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; } @@ -1836,8 +2029,7 @@ vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, 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, @@ -1867,6 +2059,13 @@ 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; @@ -1881,6 +2080,15 @@ valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr, 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: @@ -2026,49 +2234,45 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) { 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); } @@ -2210,7 +2414,7 @@ compute_partial_antic_aux (basic_block block, 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); @@ -2299,6 +2503,7 @@ compute_antic (void) 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 (); @@ -2317,7 +2522,7 @@ compute_antic (void) 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])) { @@ -2348,7 +2553,7 @@ compute_antic (void) 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])) { @@ -2382,19 +2587,8 @@ can_value_number_call (gimple stmt) 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 @@ -2414,7 +2608,7 @@ can_PRE_operation (tree op) /* 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 @@ -2436,26 +2630,79 @@ create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, { case CALL_EXPR: { - tree folded; + 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) + { + op0expr = get_or_alloc_expr_for (currop->op0); + genop0 = find_or_generate_expression (block, op0expr, + stmts, domstmt); + if (!genop0) + return NULL_TREE; + } + 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: if (currop->op0) { @@ -2491,8 +2738,12 @@ create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, genop1 = fold_convert (build_pointer_type (currop->type), genop1); - folded = fold_build1 (currop->opcode, currop->type, - genop1); + if (currop->opcode == MISALIGNED_INDIRECT_REF) + folded = fold_build2 (currop->opcode, currop->type, + genop1, currop->op1); + else + folded = fold_build1 (currop->opcode, currop->type, + genop1); return folded; } break; @@ -2530,7 +2781,8 @@ create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, 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) @@ -2541,14 +2793,38 @@ create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, 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); } @@ -2651,8 +2927,9 @@ find_or_generate_expression (basic_block block, pre_expr expr, } /* If it's still NULL, it must be a complex expression, so generate - it recursively. */ - if (genop == NULL) + it recursively. Not so for FRE though. */ + if (genop == NULL + && !in_fre) { bitmap_set_t exprset; unsigned int lookfor = get_expr_value_id (expr); @@ -2706,8 +2983,8 @@ create_expression_by_pieces (basic_block block, pre_expr expr, 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); @@ -2745,15 +3022,19 @@ create_expression_by_pieces (basic_block block, pre_expr 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); } @@ -2779,13 +3060,16 @@ create_expression_by_pieces (basic_block block, pre_expr expr, 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. */ @@ -2798,14 +3082,15 @@ create_expression_by_pieces (basic_block block, pre_expr expr, 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); - bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); + if (!in_fre) + bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); } mark_symbols_for_renaming (stmt); @@ -2817,24 +3102,20 @@ create_expression_by_pieces (basic_block block, pre_expr expr, 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); @@ -2865,6 +3146,62 @@ create_expression_by_pieces (basic_block block, pre_expr expr, } +/* 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 @@ -2895,8 +3232,7 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, } /* 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; @@ -2905,7 +3241,9 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, 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"); @@ -2913,7 +3251,6 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, } } - /* Make the necessary insertions. */ FOR_EACH_EDGE (pred, ei, block->preds) { @@ -2939,23 +3276,15 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, 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) { @@ -2969,7 +3298,10 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, 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); @@ -3008,7 +3340,9 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, 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); @@ -3044,16 +3378,17 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, 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))); 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); + add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred, + UNKNOWN_LOCATION); } newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi)); @@ -3131,6 +3466,8 @@ do_regular_insertion (basic_block block, basic_block dom) basic_block bprime; pre_expr eprime = NULL; edge_iterator ei; + pre_expr edoubleprime = NULL; + bool do_insertion = false; val = get_expr_value_id (expr); if (bitmap_set_contains_value (PHI_GEN (block), val)) @@ -3146,16 +3483,10 @@ do_regular_insertion (basic_block block, basic_block dom) FOR_EACH_EDGE (pred, ei, block->preds) { unsigned int vprime; - pre_expr edoubleprime; - /* This can happen in the very weird case - that our fake infinite loop edges have caused a - critical edge to appear. */ - if (EDGE_CRITICAL_P (pred)) - { - cant_insert = true; - break; - } + /* We should never run insertion for the exit block + and so not come across fake pred edges. */ + gcc_assert (!(pred->flags & EDGE_FAKE)); bprime = pred->src; eprime = phi_translate (expr, ANTIC_IN (block), NULL, bprime, block); @@ -3188,6 +3519,10 @@ do_regular_insertion (basic_block block, basic_block dom) { 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)) @@ -3198,7 +3533,8 @@ do_regular_insertion (basic_block block, basic_block dom) 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)) @@ -3208,7 +3544,8 @@ do_regular_insertion (basic_block block, basic_block dom) an invariant, then the PHI has the same value on all edges. Note this. */ else if (!cant_insert && all_same && eprime - && eprime->kind == CONSTANT + && (edoubleprime->kind == CONSTANT + || edoubleprime->kind == NAME) && !value_id_constant_p (val)) { unsigned int j; @@ -3216,7 +3553,7 @@ do_regular_insertion (basic_block block, basic_block dom) bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val); - unsigned int new_val = get_expr_value_id (eprime); + unsigned int new_val = get_expr_value_id (edoubleprime); FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi) { pre_expr expr = expression_for_id (j); @@ -3226,9 +3563,14 @@ do_regular_insertion (basic_block block, basic_block dom) vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr)); /* Just reset the value id and valnum so it is the same as the constant we have discovered. */ - info->valnum = PRE_EXPR_CONSTANT (eprime); + if (edoubleprime->kind == CONSTANT) + { + info->valnum = PRE_EXPR_CONSTANT (edoubleprime); + pre_stats.constified++; + } + else + info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum; info->value_id = new_val; - pre_stats.constified++; } } } @@ -3281,14 +3623,9 @@ do_partial_partial_insertion (basic_block block, basic_block dom) unsigned int vprime; pre_expr edoubleprime; - /* This can happen in the very weird case - that our fake infinite loop edges have caused a - critical edge to appear. */ - if (EDGE_CRITICAL_P (pred)) - { - cant_insert = true; - break; - } + /* We should never run insertion for the exit block + and so not come across fake pred edges. */ + gcc_assert (!(pred->flags & EDGE_FAKE)); bprime = pred->src; eprime = phi_translate (expr, ANTIC_IN (block), PA_IN (block), @@ -3409,11 +3746,7 @@ insert (void) } -/* 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) @@ -3425,9 +3758,6 @@ 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); } } @@ -3446,6 +3776,19 @@ make_values_for_phi (gimple phi, basic_block block) 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); + } + } + } } } @@ -3466,46 +3809,25 @@ compute_avail (void) basic_block block, son; basic_block *worklist; size_t sp = 0; - tree param; - - /* 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)) - { - 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); - } - } + unsigned i; - /* Likewise for the static chain decl. */ - if (cfun->static_chain_decl) + /* 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) { - 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. */ @@ -3539,6 +3861,8 @@ compute_avail (void) 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)) @@ -3549,16 +3873,30 @@ compute_avail (void) 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); } @@ -3585,8 +3923,9 @@ compute_avail (void) continue; copy_reference_ops_from_call (stmt, &ops); - vn_reference_lookup_pieces (shared_vuses_from_stmt (stmt), - ops, &ref); + 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) continue; @@ -3610,11 +3949,7 @@ compute_avail (void) 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; } @@ -3624,9 +3959,8 @@ compute_avail (void) 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; @@ -3660,8 +3994,8 @@ compute_avail (void) 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; @@ -3695,10 +4029,7 @@ compute_avail (void) 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; } @@ -3754,16 +4085,18 @@ do_SCCVN_insertion (gimple stmt, tree ssa_vn) 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 @@ -3803,8 +4136,10 @@ eliminate (void) 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)) { @@ -3816,8 +4151,8 @@ eliminate (void) 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; } @@ -3864,8 +4199,8 @@ eliminate (void) 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 @@ -3879,6 +4214,33 @@ eliminate (void) } } } + /* 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) @@ -3903,9 +4265,144 @@ eliminate (void) 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 (!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; } @@ -3946,19 +4443,23 @@ mark_operand_necessary (tree op) 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 @@ -3967,7 +4468,6 @@ remove_dead_inserted_code (void) { 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); @@ -3975,7 +4475,7 @@ remove_dead_inserted_code (void) { gimple n = mark_operand_necessary (arg); if (n) - VEC_quick_push (gimple, worklist, n); + bitmap_set_bit (worklist, SSA_NAME_VERSION (arg)); } } } @@ -3996,13 +4496,14 @@ remove_dead_inserted_code (void) { 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; @@ -4017,13 +4518,88 @@ remove_dead_inserted_code (void) 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 @@ -4037,10 +4613,11 @@ init_pre (bool do_fre) 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; @@ -4051,7 +4628,7 @@ init_pre (bool do_fre) 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); @@ -4065,7 +4642,6 @@ init_pre (bool do_fre) 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", @@ -4077,7 +4653,6 @@ init_pre (bool do_fre) 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); } @@ -4092,14 +4667,14 @@ fini_pre (bool do_fre) 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); - remove_fake_exit_edges (); + VEC_free (unsigned, heap, name_to_id); FOR_ALL_BB (bb) { @@ -4125,11 +4700,11 @@ fini_pre (bool do_fre) 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. */ @@ -4139,15 +4714,13 @@ execute_pre (bool do_fre ATTRIBUTE_UNUSED) 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 (); @@ -4159,10 +4732,9 @@ execute_pre (bool do_fre ATTRIBUTE_UNUSED) 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); } } @@ -4177,6 +4749,12 @@ execute_pre (bool do_fre ATTRIBUTE_UNUSED) 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 (); @@ -4185,13 +4763,13 @@ execute_pre (bool do_fre ATTRIBUTE_UNUSED) 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); - 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; @@ -4202,7 +4780,7 @@ execute_pre (bool do_fre ATTRIBUTE_UNUSED) static unsigned int do_pre (void) { - return TODO_rebuild_alias | execute_pre (false); + return execute_pre (false); } static bool @@ -4223,10 +4801,10 @@ 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 */ } @@ -4258,7 +4836,7 @@ struct gimple_opt_pass pass_fre = 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 */