| /* SSA-PRE for trees. |
| Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
| Free Software Foundation, Inc. |
| Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher |
| <stevenb@suse.de> |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3, or (at your option) |
| any later version. |
| |
| GCC is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "tm.h" |
| #include "tree.h" |
| #include "basic-block.h" |
| #include "gimple-pretty-print.h" |
| #include "tree-inline.h" |
| #include "tree-flow.h" |
| #include "gimple.h" |
| #include "hash-table.h" |
| #include "tree-iterator.h" |
| #include "alloc-pool.h" |
| #include "obstack.h" |
| #include "tree-pass.h" |
| #include "flags.h" |
| #include "bitmap.h" |
| #include "langhooks.h" |
| #include "cfgloop.h" |
| #include "tree-ssa-sccvn.h" |
| #include "tree-scalar-evolution.h" |
| #include "params.h" |
| #include "dbgcnt.h" |
| #include "domwalk.h" |
| |
| /* TODO: |
| |
| 1. Avail sets can be shared by making an avail_find_leader that |
| walks up the dominator tree and looks in those avail sets. |
| This might affect code optimality, it's unclear right now. |
| 2. Strength reduction can be performed by anticipating expressions |
| we can repair later on. |
| 3. We can do back-substitution or smarter value numbering to catch |
| commutative expressions split up over multiple statements. |
| */ |
| |
| /* For ease of terminology, "expression node" in the below refers to |
| every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs |
| represent the actual statement containing the expressions we care about, |
| and we cache the value number by putting it in the expression. */ |
| |
| /* Basic algorithm |
| |
| First we walk the statements to generate the AVAIL sets, the |
| EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the |
| generation of values/expressions by a given block. We use them |
| when computing the ANTIC sets. The AVAIL sets consist of |
| SSA_NAME's that represent values, so we know what values are |
| available in what blocks. AVAIL is a forward dataflow problem. In |
| SSA, values are never killed, so we don't need a kill set, or a |
| fixpoint iteration, in order to calculate the AVAIL sets. In |
| traditional parlance, AVAIL sets tell us the downsafety of the |
| expressions/values. |
| |
| Next, we generate the ANTIC sets. These sets represent the |
| anticipatable expressions. ANTIC is a backwards dataflow |
| problem. An expression is anticipatable in a given block if it could |
| be generated in that block. This means that if we had to perform |
| an insertion in that block, of the value of that expression, we |
| could. Calculating the ANTIC sets requires phi translation of |
| expressions, because the flow goes backwards through phis. We must |
| iterate to a fixpoint of the ANTIC sets, because we have a kill |
| set. Even in SSA form, values are not live over the entire |
| function, only from their definition point onwards. So we have to |
| remove values from the ANTIC set once we go past the definition |
| point of the leaders that make them up. |
| compute_antic/compute_antic_aux performs this computation. |
| |
| Third, we perform insertions to make partially redundant |
| expressions fully redundant. |
| |
| An expression is partially redundant (excluding partial |
| anticipation) if: |
| |
| 1. It is AVAIL in some, but not all, of the predecessors of a |
| given block. |
| 2. It is ANTIC in all the predecessors. |
| |
| In order to make it fully redundant, we insert the expression into |
| the predecessors where it is not available, but is ANTIC. |
| |
| For the partial anticipation case, we only perform insertion if it |
| is partially anticipated in some block, and fully available in all |
| of the predecessors. |
| |
| insert/insert_aux/do_regular_insertion/do_partial_partial_insertion |
| performs these steps. |
| |
| Fourth, we eliminate fully redundant expressions. |
| This is a simple statement walk that replaces redundant |
| calculations with the now available values. */ |
| |
| /* Representations of value numbers: |
| |
| Value numbers are represented by a representative SSA_NAME. We |
| will create fake SSA_NAME's in situations where we need a |
| representative but do not have one (because it is a complex |
| expression). In order to facilitate storing the value numbers in |
| bitmaps, and keep the number of wasted SSA_NAME's down, we also |
| associate a value_id with each value number, and create full blown |
| ssa_name's only where we actually need them (IE in operands of |
| existing expressions). |
| |
| Theoretically you could replace all the value_id's with |
| SSA_NAME_VERSION, but this would allocate a large number of |
| SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number. |
| It would also require an additional indirection at each point we |
| use the value id. */ |
| |
| /* Representation of expressions on value numbers: |
| |
| 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. */ |
| |
| /* Representation of sets: |
| |
| The dataflow sets do not need to be sorted in any particular order |
| for the majority of their lifetime, are simply represented as two |
| bitmaps, one that keeps track of values present in the set, and one |
| that keeps track of expressions present in the set. |
| |
| When we need them in topological order, we produce it on demand by |
| transforming the bitmap into an array and sorting it into topo |
| order. */ |
| |
| /* Type of expression, used to know which member of the PRE_EXPR union |
| is valid. */ |
| |
| enum pre_expr_kind |
| { |
| NAME, |
| NARY, |
| REFERENCE, |
| CONSTANT |
| }; |
| |
| typedef union pre_expr_union_d |
| { |
| tree name; |
| tree constant; |
| vn_nary_op_t nary; |
| vn_reference_t reference; |
| } pre_expr_union; |
| |
| typedef struct pre_expr_d : typed_noop_remove <pre_expr_d> |
| { |
| enum pre_expr_kind kind; |
| unsigned int id; |
| pre_expr_union u; |
| |
| /* hash_table support. */ |
| typedef pre_expr_d T; |
| static inline hashval_t hash (const pre_expr_d *); |
| static inline int equal (const pre_expr_d *, const pre_expr_d *); |
| } *pre_expr; |
| |
| #define PRE_EXPR_NAME(e) (e)->u.name |
| #define PRE_EXPR_NARY(e) (e)->u.nary |
| #define PRE_EXPR_REFERENCE(e) (e)->u.reference |
| #define PRE_EXPR_CONSTANT(e) (e)->u.constant |
| |
| /* Compare E1 and E1 for equality. */ |
| |
| inline int |
| pre_expr_d::equal (const struct pre_expr_d *e1, const struct pre_expr_d *e2) |
| { |
| if (e1->kind != e2->kind) |
| return false; |
| |
| switch (e1->kind) |
| { |
| case CONSTANT: |
| return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1), |
| PRE_EXPR_CONSTANT (e2)); |
| case NAME: |
| return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2); |
| case NARY: |
| return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2)); |
| case REFERENCE: |
| return vn_reference_eq (PRE_EXPR_REFERENCE (e1), |
| PRE_EXPR_REFERENCE (e2)); |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| /* Hash E. */ |
| |
| inline hashval_t |
| pre_expr_d::hash (const struct pre_expr_d *e) |
| { |
| switch (e->kind) |
| { |
| case CONSTANT: |
| return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e)); |
| case NAME: |
| return SSA_NAME_VERSION (PRE_EXPR_NAME (e)); |
| case NARY: |
| return PRE_EXPR_NARY (e)->hashcode; |
| case REFERENCE: |
| return PRE_EXPR_REFERENCE (e)->hashcode; |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| /* Next global expression id number. */ |
| static unsigned int next_expression_id; |
| |
| /* Mapping from expression to id number we can use in bitmap sets. */ |
| DEF_VEC_P (pre_expr); |
| DEF_VEC_ALLOC_P (pre_expr, heap); |
| static VEC(pre_expr, heap) *expressions; |
| static hash_table <pre_expr_d> expression_to_id; |
| static VEC(unsigned, heap) *name_to_id; |
| |
| /* Allocate an expression id for EXPR. */ |
| |
| static inline unsigned int |
| alloc_expression_id (pre_expr expr) |
| { |
| struct pre_expr_d **slot; |
| /* Make sure we won't overflow. */ |
| gcc_assert (next_expression_id + 1 > next_expression_id); |
| expr->id = next_expression_id++; |
| VEC_safe_push (pre_expr, heap, expressions, expr); |
| 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. */ |
| unsigned old_len = VEC_length (unsigned, name_to_id); |
| VEC_reserve (unsigned, heap, name_to_id, num_ssa_names - old_len); |
| 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 = expression_to_id.find_slot (expr, INSERT); |
| gcc_assert (!*slot); |
| *slot = expr; |
| } |
| return next_expression_id - 1; |
| } |
| |
| /* Return the expression id for tree EXPR. */ |
| |
| static inline unsigned int |
| get_expression_id (const pre_expr expr) |
| { |
| return expr->id; |
| } |
| |
| static inline unsigned int |
| lookup_expression_id (const pre_expr expr) |
| { |
| struct pre_expr_d **slot; |
| |
| 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 = expression_to_id.find_slot (expr, NO_INSERT); |
| if (!slot) |
| return 0; |
| return ((pre_expr)*slot)->id; |
| } |
| } |
| |
| /* Return the existing expression id for EXPR, or create one if one |
| does not exist yet. */ |
| |
| static inline unsigned int |
| get_or_alloc_expression_id (pre_expr expr) |
| { |
| unsigned int id = lookup_expression_id (expr); |
| if (id == 0) |
| return alloc_expression_id (expr); |
| return expr->id = id; |
| } |
| |
| /* Return the expression that has expression id ID */ |
| |
| static inline pre_expr |
| expression_for_id (unsigned int id) |
| { |
| return VEC_index (pre_expr, expressions, id); |
| } |
| |
| /* Free the expression id field in all of our expressions, |
| and then destroy the expressions array. */ |
| |
| static void |
| clear_expression_ids (void) |
| { |
| VEC_free (pre_expr, heap, expressions); |
| } |
| |
| static alloc_pool pre_expr_pool; |
| |
| /* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */ |
| |
| static pre_expr |
| get_or_alloc_expr_for_name (tree name) |
| { |
| 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; |
| PRE_EXPR_NAME (result) = name; |
| alloc_expression_id (result); |
| return result; |
| } |
| |
| /* An unordered bitmap set. One bitmap tracks values, the other, |
| expressions. */ |
| typedef struct bitmap_set |
| { |
| bitmap_head expressions; |
| bitmap_head values; |
| } *bitmap_set_t; |
| |
| #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. */ |
| static VEC(bitmap, heap) *value_expressions; |
| |
| /* Sets that we need to keep track of. */ |
| typedef struct bb_bitmap_sets |
| { |
| /* The EXP_GEN set, which represents expressions/values generated in |
| a basic block. */ |
| bitmap_set_t exp_gen; |
| |
| /* The PHI_GEN set, which represents PHI results generated in a |
| basic block. */ |
| bitmap_set_t phi_gen; |
| |
| /* The TMP_GEN set, which represents results/temporaries generated |
| in a basic block. IE the LHS of an expression. */ |
| bitmap_set_t tmp_gen; |
| |
| /* The AVAIL_OUT set, which represents which values are available in |
| a given basic block. */ |
| bitmap_set_t avail_out; |
| |
| /* The ANTIC_IN set, which represents which values are anticipatable |
| in a given basic block. */ |
| bitmap_set_t antic_in; |
| |
| /* The PA_IN set, which represents which values are |
| partially anticipatable in a given basic block. */ |
| bitmap_set_t pa_in; |
| |
| /* The NEW_SETS set, which is used during insertion to augment the |
| AVAIL_OUT set of blocks with the new insertions performed during |
| 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; |
| |
| /* True we have deferred processing this block during ANTIC |
| calculation until its successor is processed. */ |
| unsigned int deferred : 1; |
| |
| /* True when the block contains a call that might not return. */ |
| unsigned int contains_may_not_return_call : 1; |
| } *bb_value_sets_t; |
| |
| #define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen |
| #define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen |
| #define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen |
| #define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out |
| #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 EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies |
| #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited |
| #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred |
| #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call |
| |
| |
| /* Basic block list in postorder. */ |
| static int *postorder; |
| |
| /* This structure is used to keep track of statistics on what |
| optimization PRE was able to perform. */ |
| static struct |
| { |
| /* The number of RHS computations eliminated by PRE. */ |
| int eliminations; |
| |
| /* The number of new expressions/temporaries generated by PRE. */ |
| int insertions; |
| |
| /* The number of inserts found due to partial anticipation */ |
| int pa_insert; |
| |
| /* The number of new PHI nodes added by PRE. */ |
| int phis; |
| |
| /* The number of values found constant. */ |
| int constified; |
| |
| } pre_stats; |
| |
| static bool do_partial_partial; |
| static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int); |
| static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr); |
| static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr); |
| static void bitmap_set_copy (bitmap_set_t, bitmap_set_t); |
| static bool bitmap_set_contains_value (bitmap_set_t, unsigned int); |
| static void bitmap_insert_into_set (bitmap_set_t, pre_expr); |
| static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr, |
| unsigned int, bool); |
| static bitmap_set_t bitmap_set_new (void); |
| static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *, |
| tree); |
| static tree find_or_generate_expression (basic_block, tree, gimple_seq *); |
| 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. */ |
| |
| static alloc_pool bitmap_set_pool; |
| static bitmap_obstack grand_bitmap_obstack; |
| |
| /* Set of blocks with statements that have had their EH properties changed. */ |
| static bitmap need_eh_cleanup; |
| |
| /* Set of blocks with statements that have had their AB properties changed. */ |
| static bitmap need_ab_cleanup; |
| |
| /* A three tuple {e, pred, v} used to cache phi translations in the |
| phi_translate_table. */ |
| |
| typedef struct expr_pred_trans_d : typed_free_remove<expr_pred_trans_d> |
| { |
| /* The expression. */ |
| pre_expr e; |
| |
| /* The predecessor block along which we translated the expression. */ |
| basic_block pred; |
| |
| /* The value that resulted from the translation. */ |
| pre_expr v; |
| |
| /* The hashcode for the expression, pred pair. This is cached for |
| speed reasons. */ |
| hashval_t hashcode; |
| |
| /* hash_table support. */ |
| typedef expr_pred_trans_d T; |
| static inline hashval_t hash (const expr_pred_trans_d *); |
| static inline int equal (const expr_pred_trans_d *, const expr_pred_trans_d *); |
| } *expr_pred_trans_t; |
| typedef const struct expr_pred_trans_d *const_expr_pred_trans_t; |
| |
| inline hashval_t |
| expr_pred_trans_d::hash (const expr_pred_trans_d *e) |
| { |
| return e->hashcode; |
| } |
| |
| inline int |
| expr_pred_trans_d::equal (const expr_pred_trans_d *ve1, |
| const expr_pred_trans_d *ve2) |
| { |
| basic_block b1 = ve1->pred; |
| basic_block b2 = ve2->pred; |
| |
| /* If they are not translations for the same basic block, they can't |
| be equal. */ |
| if (b1 != b2) |
| return false; |
| return pre_expr_d::equal (ve1->e, ve2->e); |
| } |
| |
| /* The phi_translate_table caches phi translations for a given |
| expression and predecessor. */ |
| static hash_table <expr_pred_trans_d> phi_translate_table; |
| |
| /* Search in the phi translation table for the translation of |
| expression E in basic block PRED. |
| Return the translated value, if found, NULL otherwise. */ |
| |
| static inline pre_expr |
| phi_trans_lookup (pre_expr e, basic_block pred) |
| { |
| expr_pred_trans_t *slot; |
| struct expr_pred_trans_d ept; |
| |
| ept.e = e; |
| ept.pred = pred; |
| ept.hashcode = iterative_hash_hashval_t (pre_expr_d::hash (e), pred->index); |
| slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode, |
| NO_INSERT); |
| if (!slot) |
| return NULL; |
| else |
| return (*slot)->v; |
| } |
| |
| |
| /* Add the tuple mapping from {expression E, basic block PRED} to |
| value V, to the phi translation table. */ |
| |
| static inline void |
| phi_trans_add (pre_expr e, pre_expr v, basic_block pred) |
| { |
| expr_pred_trans_t *slot; |
| expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d); |
| new_pair->e = e; |
| new_pair->pred = pred; |
| new_pair->v = v; |
| new_pair->hashcode = iterative_hash_hashval_t (pre_expr_d::hash (e), |
| pred->index); |
| |
| slot = phi_translate_table.find_slot_with_hash (new_pair, |
| new_pair->hashcode, INSERT); |
| free (*slot); |
| *slot = new_pair; |
| } |
| |
| |
| /* Add expression E to the expression set of value id V. */ |
| |
| static void |
| add_to_value (unsigned int v, pre_expr e) |
| { |
| bitmap set; |
| |
| gcc_checking_assert (get_expr_value_id (e) == v); |
| |
| if (v >= VEC_length (bitmap, value_expressions)) |
| { |
| VEC_safe_grow_cleared (bitmap, heap, value_expressions, v + 1); |
| } |
| |
| set = VEC_index (bitmap, value_expressions, v); |
| if (!set) |
| { |
| set = BITMAP_ALLOC (&grand_bitmap_obstack); |
| VEC_replace (bitmap, value_expressions, v, set); |
| } |
| |
| bitmap_set_bit (set, get_or_alloc_expression_id (e)); |
| } |
| |
| /* Create a new bitmap set and return it. */ |
| |
| static bitmap_set_t |
| bitmap_set_new (void) |
| { |
| bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool); |
| bitmap_initialize (&ret->expressions, &grand_bitmap_obstack); |
| bitmap_initialize (&ret->values, &grand_bitmap_obstack); |
| return ret; |
| } |
| |
| /* Return the value id for a PRE expression EXPR. */ |
| |
| static unsigned int |
| get_expr_value_id (pre_expr expr) |
| { |
| switch (expr->kind) |
| { |
| case CONSTANT: |
| { |
| unsigned int id; |
| id = get_constant_value_id (PRE_EXPR_CONSTANT (expr)); |
| if (id == 0) |
| { |
| id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr)); |
| add_to_value (id, expr); |
| } |
| return id; |
| } |
| case NAME: |
| return VN_INFO (PRE_EXPR_NAME (expr))->value_id; |
| case NARY: |
| return PRE_EXPR_NARY (expr)->value_id; |
| case REFERENCE: |
| return PRE_EXPR_REFERENCE (expr)->value_id; |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */ |
| |
| static tree |
| sccvn_valnum_from_value_id (unsigned int val) |
| { |
| bitmap_iterator bi; |
| unsigned int i; |
| bitmap exprset = VEC_index (bitmap, value_expressions, val); |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) |
| { |
| pre_expr vexpr = expression_for_id (i); |
| if (vexpr->kind == NAME) |
| return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum; |
| else if (vexpr->kind == CONSTANT) |
| return PRE_EXPR_CONSTANT (vexpr); |
| } |
| return NULL_TREE; |
| } |
| |
| /* Remove an expression EXPR from a bitmapped set. */ |
| |
| static void |
| bitmap_remove_from_set (bitmap_set_t set, pre_expr expr) |
| { |
| unsigned int val = get_expr_value_id (expr); |
| if (!value_id_constant_p (val)) |
| { |
| bitmap_clear_bit (&set->values, val); |
| bitmap_clear_bit (&set->expressions, get_expression_id (expr)); |
| } |
| } |
| |
| static void |
| bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr, |
| unsigned int val, bool allow_constants) |
| { |
| if (allow_constants || !value_id_constant_p (val)) |
| { |
| /* We specifically expect this and only this function to be able to |
| insert constants into a set. */ |
| bitmap_set_bit (&set->values, val); |
| bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr)); |
| } |
| } |
| |
| /* Insert an expression EXPR into a bitmapped set. */ |
| |
| static void |
| bitmap_insert_into_set (bitmap_set_t set, pre_expr expr) |
| { |
| bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false); |
| } |
| |
| /* Copy a bitmapped set ORIG, into bitmapped set DEST. */ |
| |
| static void |
| bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig) |
| { |
| bitmap_copy (&dest->expressions, &orig->expressions); |
| bitmap_copy (&dest->values, &orig->values); |
| } |
| |
| |
| /* Free memory used up by SET. */ |
| static void |
| bitmap_set_free (bitmap_set_t set) |
| { |
| bitmap_clear (&set->expressions); |
| bitmap_clear (&set->values); |
| } |
| |
| |
| /* 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, 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_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 exprset = VEC_index (bitmap, value_expressions, i); |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj) |
| { |
| if (bitmap_bit_p (&set->expressions, j)) |
| VEC_safe_push (pre_expr, heap, result, expression_for_id (j)); |
| } |
| } |
| |
| return result; |
| } |
| |
| /* Perform bitmapped set operation DEST &= ORIG. */ |
| |
| static void |
| bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig) |
| { |
| bitmap_iterator bi; |
| unsigned int i; |
| |
| if (dest != orig) |
| { |
| bitmap_head temp; |
| bitmap_initialize (&temp, &grand_bitmap_obstack); |
| |
| bitmap_and_into (&dest->values, &orig->values); |
| bitmap_copy (&temp, &dest->expressions); |
| EXECUTE_IF_SET_IN_BITMAP (&temp, 0, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| unsigned int value_id = get_expr_value_id (expr); |
| if (!bitmap_bit_p (&dest->values, value_id)) |
| bitmap_clear_bit (&dest->expressions, i); |
| } |
| bitmap_clear (&temp); |
| } |
| } |
| |
| /* Subtract all values and expressions contained in ORIG from DEST. */ |
| |
| static bitmap_set_t |
| bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig) |
| { |
| bitmap_set_t result = bitmap_set_new (); |
| bitmap_iterator bi; |
| unsigned int i; |
| |
| bitmap_and_compl (&result->expressions, &dest->expressions, |
| &orig->expressions); |
| |
| FOR_EACH_EXPR_ID_IN_SET (result, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| unsigned int value_id = get_expr_value_id (expr); |
| bitmap_set_bit (&result->values, value_id); |
| } |
| |
| return result; |
| } |
| |
| /* Subtract all the values in bitmap set B from bitmap set A. */ |
| |
| static void |
| bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b) |
| { |
| unsigned int i; |
| bitmap_iterator bi; |
| bitmap_head temp; |
| |
| bitmap_initialize (&temp, &grand_bitmap_obstack); |
| |
| bitmap_copy (&temp, &a->expressions); |
| EXECUTE_IF_SET_IN_BITMAP (&temp, 0, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| if (bitmap_set_contains_value (b, get_expr_value_id (expr))) |
| bitmap_remove_from_set (a, expr); |
| } |
| bitmap_clear (&temp); |
| } |
| |
| |
| /* Return true if bitmapped set SET contains the value VALUE_ID. */ |
| |
| static bool |
| bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id) |
| { |
| if (value_id_constant_p (value_id)) |
| return true; |
| |
| if (!set || bitmap_empty_p (&set->expressions)) |
| return false; |
| |
| return bitmap_bit_p (&set->values, value_id); |
| } |
| |
| static inline bool |
| bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr) |
| { |
| return bitmap_bit_p (&set->expressions, get_expression_id (expr)); |
| } |
| |
| /* Replace an instance of value LOOKFOR with expression EXPR in SET. */ |
| |
| static void |
| bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor, |
| const pre_expr expr) |
| { |
| bitmap exprset; |
| unsigned int i; |
| bitmap_iterator bi; |
| |
| if (value_id_constant_p (lookfor)) |
| return; |
| |
| if (!bitmap_set_contains_value (set, lookfor)) |
| return; |
| |
| /* The number of expressions having a given value is usually |
| significantly less than the total number of expressions in SET. |
| Thus, rather than check, for each expression in SET, whether it |
| has the value LOOKFOR, we walk the reverse mapping that tells us |
| what expressions have a given value, and see if any of those |
| expressions are in our set. For large testcases, this is about |
| 5-10x faster than walking the bitmap. If this is somehow a |
| significant lose for some cases, we can choose which set to walk |
| based on the set size. */ |
| exprset = VEC_index (bitmap, value_expressions, lookfor); |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) |
| { |
| if (bitmap_clear_bit (&set->expressions, i)) |
| { |
| bitmap_set_bit (&set->expressions, get_expression_id (expr)); |
| return; |
| } |
| } |
| } |
| |
| /* Return true if two bitmap sets are equal. */ |
| |
| static bool |
| bitmap_set_equal (bitmap_set_t a, bitmap_set_t b) |
| { |
| return bitmap_equal_p (&a->values, &b->values); |
| } |
| |
| /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists, |
| and add it otherwise. */ |
| |
| static void |
| bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr) |
| { |
| unsigned int val = get_expr_value_id (expr); |
| |
| if (bitmap_set_contains_value (set, val)) |
| bitmap_set_replace_value (set, val, expr); |
| else |
| bitmap_insert_into_set (set, expr); |
| } |
| |
| /* Insert EXPR into SET if EXPR's value is not already present in |
| SET. */ |
| |
| static void |
| bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr) |
| { |
| unsigned int val = get_expr_value_id (expr); |
| |
| gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr)); |
| |
| /* Constant values are always considered to be part of the set. */ |
| if (value_id_constant_p (val)) |
| return; |
| |
| /* 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. */ |
| |
| static void |
| print_pre_expr (FILE *outfile, const pre_expr expr) |
| { |
| switch (expr->kind) |
| { |
| case CONSTANT: |
| print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0); |
| break; |
| case NAME: |
| print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0); |
| break; |
| case NARY: |
| { |
| unsigned int i; |
| vn_nary_op_t nary = PRE_EXPR_NARY (expr); |
| fprintf (outfile, "{%s,", tree_code_name [nary->opcode]); |
| for (i = 0; i < nary->length; i++) |
| { |
| print_generic_expr (outfile, nary->op[i], 0); |
| if (i != (unsigned) nary->length - 1) |
| fprintf (outfile, ","); |
| } |
| fprintf (outfile, "}"); |
| } |
| break; |
| |
| case REFERENCE: |
| { |
| vn_reference_op_t vro; |
| unsigned int i; |
| vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
| fprintf (outfile, "{"); |
| for (i = 0; |
| 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]); |
| if (vro->op0) |
| { |
| fprintf (outfile, "<"); |
| closebrace = true; |
| } |
| } |
| if (vro->op0) |
| { |
| print_generic_expr (outfile, vro->op0, 0); |
| if (vro->op1) |
| { |
| fprintf (outfile, ","); |
| print_generic_expr (outfile, vro->op1, 0); |
| } |
| 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; |
| } |
| } |
| void debug_pre_expr (pre_expr); |
| |
| /* Like print_pre_expr but always prints to stderr. */ |
| DEBUG_FUNCTION void |
| debug_pre_expr (pre_expr e) |
| { |
| print_pre_expr (stderr, e); |
| fprintf (stderr, "\n"); |
| } |
| |
| /* Print out SET to OUTFILE. */ |
| |
| static void |
| print_bitmap_set (FILE *outfile, bitmap_set_t set, |
| const char *setname, int blockindex) |
| { |
| fprintf (outfile, "%s[%d] := { ", setname, blockindex); |
| if (set) |
| { |
| bool first = true; |
| unsigned i; |
| bitmap_iterator bi; |
| |
| FOR_EACH_EXPR_ID_IN_SET (set, i, bi) |
| { |
| const pre_expr expr = expression_for_id (i); |
| |
| if (!first) |
| fprintf (outfile, ", "); |
| first = false; |
| print_pre_expr (outfile, expr); |
| |
| fprintf (outfile, " (%04d)", get_expr_value_id (expr)); |
| } |
| } |
| fprintf (outfile, " }\n"); |
| } |
| |
| void debug_bitmap_set (bitmap_set_t); |
| |
| DEBUG_FUNCTION void |
| debug_bitmap_set (bitmap_set_t set) |
| { |
| print_bitmap_set (stderr, set, "debug", 0); |
| } |
| |
| void debug_bitmap_sets_for (basic_block); |
| |
| DEBUG_FUNCTION void |
| debug_bitmap_sets_for (basic_block bb) |
| { |
| print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index); |
| print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index); |
| print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index); |
| print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index); |
| print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index); |
| if (do_partial_partial) |
| print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index); |
| print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index); |
| } |
| |
| /* Print out the expressions that have VAL to OUTFILE. */ |
| |
| static void |
| print_value_expressions (FILE *outfile, unsigned int val) |
| { |
| bitmap set = VEC_index (bitmap, value_expressions, val); |
| if (set) |
| { |
| bitmap_set x; |
| char s[10]; |
| sprintf (s, "%04d", val); |
| x.expressions = *set; |
| print_bitmap_set (outfile, &x, s, 0); |
| } |
| } |
| |
| |
| DEBUG_FUNCTION void |
| debug_value_expressions (unsigned int val) |
| { |
| print_value_expressions (stderr, val); |
| } |
| |
| /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to |
| represent it. */ |
| |
| static pre_expr |
| get_or_alloc_expr_for_constant (tree constant) |
| { |
| unsigned int result_id; |
| unsigned int value_id; |
| 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; |
| alloc_expression_id (newexpr); |
| value_id = get_or_alloc_constant_value_id (constant); |
| add_to_value (value_id, newexpr); |
| return newexpr; |
| } |
| |
| /* Given a value id V, find the actual tree representing the constant |
| value if there is one, and return it. Return NULL if we can't find |
| a constant. */ |
| |
| static tree |
| get_constant_for_value_id (unsigned int v) |
| { |
| if (value_id_constant_p (v)) |
| { |
| unsigned int i; |
| bitmap_iterator bi; |
| bitmap exprset = VEC_index (bitmap, value_expressions, v); |
| |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| if (expr->kind == CONSTANT) |
| return PRE_EXPR_CONSTANT (expr); |
| } |
| } |
| return NULL; |
| } |
| |
| /* Get or allocate a pre_expr for a piece of GIMPLE, and return it. |
| Currently only supports constants and SSA_NAMES. */ |
| static pre_expr |
| get_or_alloc_expr_for (tree t) |
| { |
| if (TREE_CODE (t) == SSA_NAME) |
| return get_or_alloc_expr_for_name (t); |
| else if (is_gimple_min_invariant (t)) |
| return get_or_alloc_expr_for_constant (t); |
| else |
| { |
| /* More complex expressions can result from SCCVN expression |
| simplification that inserts values for them. As they all |
| do not have VOPs the get handled by the nary ops struct. */ |
| vn_nary_op_t result; |
| unsigned int result_id; |
| vn_nary_op_lookup (t, &result); |
| if (result != NULL) |
| { |
| pre_expr e = (pre_expr) pool_alloc (pre_expr_pool); |
| e->kind = NARY; |
| PRE_EXPR_NARY (e) = result; |
| result_id = lookup_expression_id (e); |
| if (result_id != 0) |
| { |
| pool_free (pre_expr_pool, e); |
| e = expression_for_id (result_id); |
| return e; |
| } |
| alloc_expression_id (e); |
| return e; |
| } |
| } |
| return NULL; |
| } |
| |
| /* Return the folded version of T if T, when folded, is a gimple |
| min_invariant. Otherwise, return T. */ |
| |
| static pre_expr |
| fully_constant_expression (pre_expr e) |
| { |
| switch (e->kind) |
| { |
| case CONSTANT: |
| return e; |
| case NARY: |
| { |
| vn_nary_op_t nary = PRE_EXPR_NARY (e); |
| switch (TREE_CODE_CLASS (nary->opcode)) |
| { |
| 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 result; |
| if (!is_gimple_min_invariant (naryop0)) |
| { |
| pre_expr rep0 = get_or_alloc_expr_for (naryop0); |
| unsigned int vrep0 = get_expr_value_id (rep0); |
| tree const0 = get_constant_for_value_id (vrep0); |
| if (const0) |
| naryop0 = fold_convert (TREE_TYPE (naryop0), const0); |
| } |
| if (!is_gimple_min_invariant (naryop1)) |
| { |
| pre_expr rep1 = get_or_alloc_expr_for (naryop1); |
| unsigned int vrep1 = get_expr_value_id (rep1); |
| 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: |
| { |
| /* 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 = naryop0; |
| else |
| { |
| pre_expr rep0 = get_or_alloc_expr_for (naryop0); |
| unsigned int vrep0 = get_expr_value_id (rep0); |
| const0 = get_constant_for_value_id (vrep0); |
| } |
| result = NULL; |
| if (const0) |
| { |
| tree type1 = TREE_TYPE (nary->op[0]); |
| 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; |
| } |
| default: |
| 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 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 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) |
| { |
| 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; |
| |
| if (e) |
| { |
| if (use_oracle) |
| { |
| bitmap visited = NULL; |
| unsigned int cnt; |
| /* Try to find a vuse that dominates this phi node by skipping |
| non-clobbering statements. */ |
| vuse = get_continuation_for_phi (phi, &ref, &cnt, &visited, false); |
| 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); |
| } |
| |
| return NULL_TREE; |
| } |
| |
| /* 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. */ |
| |
| static inline pre_expr |
| find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2) |
| { |
| pre_expr result; |
| |
| result = bitmap_find_leader (set1, val); |
| if (!result && set2) |
| result = bitmap_find_leader (set2, val); |
| return result; |
| } |
| |
| /* Get the tree type for our PRE expression e. */ |
| |
| static tree |
| get_expr_type (const pre_expr e) |
| { |
| switch (e->kind) |
| { |
| case NAME: |
| return TREE_TYPE (PRE_EXPR_NAME (e)); |
| case CONSTANT: |
| return TREE_TYPE (PRE_EXPR_CONSTANT (e)); |
| case REFERENCE: |
| return PRE_EXPR_REFERENCE (e)->type; |
| case NARY: |
| return PRE_EXPR_NARY (e)->type; |
| } |
| gcc_unreachable(); |
| } |
| |
| /* Get a representative SSA_NAME for a given expression. |
| Since all of our sub-expressions are treated as values, we require |
| them to be SSA_NAME's for simplicity. |
| Prior versions of GVNPRE used to use "value handles" here, so that |
| an expression would be VH.11 + VH.10 instead of d_3 + e_6. In |
| either case, the operands are really values (IE we do not expect |
| them to be usable without finding leaders). */ |
| |
| static tree |
| get_representative_for (const pre_expr e) |
| { |
| tree name; |
| unsigned int value_id = get_expr_value_id (e); |
| |
| switch (e->kind) |
| { |
| case NAME: |
| return PRE_EXPR_NAME (e); |
| case CONSTANT: |
| return PRE_EXPR_CONSTANT (e); |
| case NARY: |
| case REFERENCE: |
| { |
| /* Go through all of the expressions representing this value |
| and pick out an SSA_NAME. */ |
| unsigned int i; |
| bitmap_iterator bi; |
| bitmap exprs = VEC_index (bitmap, value_expressions, value_id); |
| EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi) |
| { |
| pre_expr rep = expression_for_id (i); |
| if (rep->kind == NAME) |
| return PRE_EXPR_NAME (rep); |
| } |
| } |
| break; |
| } |
| /* If we reached here we couldn't find an SSA_NAME. This can |
| happen when we've discovered a value that has never appeared in |
| the program as set to an SSA_NAME, most likely as the result of |
| phi translation. */ |
| if (dump_file) |
| { |
| fprintf (dump_file, |
| "Could not find SSA_NAME representative for expression:"); |
| print_pre_expr (dump_file, e); |
| fprintf (dump_file, "\n"); |
| } |
| |
| /* Build and insert the assignment of the end result to the temporary |
| that we will return. */ |
| name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp"); |
| VN_INFO_GET (name)->value_id = value_id; |
| VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id); |
| if (VN_INFO (name)->valnum == NULL_TREE) |
| VN_INFO (name)->valnum = name; |
| add_to_value (value_id, get_or_alloc_expr_for_name (name)); |
| if (dump_file) |
| { |
| fprintf (dump_file, "Created SSA_NAME representative "); |
| print_generic_expr (dump_file, name, 0); |
| fprintf (dump_file, " for expression:"); |
| print_pre_expr (dump_file, e); |
| fprintf (dump_file, "\n"); |
| } |
| |
| return name; |
| } |
| |
| |
| |
| static pre_expr |
| phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, |
| basic_block pred, basic_block phiblock); |
| |
| /* Translate EXPR using phis in PHIBLOCK, so that it has the values of |
| the phis in PRED. Return NULL if we can't find a leader for each part |
| of the translated expression. */ |
| |
| static pre_expr |
| phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, |
| basic_block pred, basic_block phiblock) |
| { |
| switch (expr->kind) |
| { |
| case NARY: |
| { |
| unsigned int i; |
| bool changed = false; |
| vn_nary_op_t nary = PRE_EXPR_NARY (expr); |
| vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s, |
| sizeof_vn_nary_op (nary->length)); |
| memcpy (newnary, nary, sizeof_vn_nary_op (nary->length)); |
| |
| for (i = 0; i < newnary->length; i++) |
| { |
| if (TREE_CODE (newnary->op[i]) != SSA_NAME) |
| continue; |
| else |
| { |
| pre_expr leader, result; |
| unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id; |
| 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 (!name) |
| return NULL; |
| newnary->op[i] = name; |
| } |
| else if (!result) |
| return NULL; |
| |
| changed |= newnary->op[i] != nary->op[i]; |
| } |
| } |
| if (changed) |
| { |
| pre_expr constant; |
| unsigned int new_val_id; |
| |
| tree result = vn_nary_op_lookup_pieces (newnary->length, |
| newnary->opcode, |
| newnary->type, |
| &newnary->op[0], |
| &nary); |
| 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 (nary) |
| { |
| PRE_EXPR_NARY (expr) = nary; |
| constant = fully_constant_expression (expr); |
| if (constant != expr) |
| return constant; |
| |
| new_val_id = nary->value_id; |
| get_or_alloc_expression_id (expr); |
| } |
| else |
| { |
| new_val_id = get_next_value_id (); |
| VEC_safe_grow_cleared (bitmap, heap, |
| value_expressions, |
| get_max_value_id() + 1); |
| nary = vn_nary_op_insert_pieces (newnary->length, |
| newnary->opcode, |
| newnary->type, |
| &newnary->op[0], |
| result, new_val_id); |
| PRE_EXPR_NARY (expr) = nary; |
| constant = fully_constant_expression (expr); |
| if (constant != expr) |
| return constant; |
| get_or_alloc_expression_id (expr); |
| } |
| add_to_value (new_val_id, expr); |
| } |
| return expr; |
| } |
| break; |
| |
| case REFERENCE: |
| { |
| vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
| VEC (vn_reference_op_s, heap) *operands = ref->operands; |
| tree vuse = ref->vuse; |
| tree newvuse = vuse; |
| VEC (vn_reference_op_s, heap) *newoperands = NULL; |
| bool changed = false, same_valid = true; |
| unsigned int i, j, n; |
| vn_reference_op_t operand; |
| vn_reference_t newref; |
| |
| for (i = 0, j = 0; |
| VEC_iterate (vn_reference_op_s, operands, i, operand); i++, j++) |
| { |
| pre_expr opresult; |
| pre_expr leader; |
| tree op[3]; |
| tree type = operand->type; |
| vn_reference_op_s newop = *operand; |
| op[0] = operand->op0; |
| op[1] = operand->op1; |
| op[2] = operand->op2; |
| for (n = 0; n < 3; ++n) |
| { |
| unsigned int op_val_id; |
| if (!op[n]) |
| continue; |
| if (TREE_CODE (op[n]) != SSA_NAME) |
| { |
| /* We can't possibly insert these. */ |
| if (n != 0 |
| && !is_gimple_min_invariant (op[n])) |
| break; |
| continue; |
| } |
| op_val_id = VN_INFO (op[n])->value_id; |
| leader = find_leader_in_sets (op_val_id, set1, set2); |
| if (!leader) |
| break; |
| /* Make sure we do not recursively translate ourselves |
| like for translating a[n_1] with the leader for |
| n_1 being a[n_1]. */ |
| if (get_expression_id (leader) != get_expression_id (expr)) |
| { |
| opresult = phi_translate (leader, set1, set2, |
| pred, phiblock); |
| if (!opresult) |
| break; |
| if (opresult != leader) |
| { |
| tree name = get_representative_for (opresult); |
| if (!name) |
| break; |
| changed |= name != op[n]; |
| op[n] = name; |
| } |
| } |
| } |
| if (n != 3) |
| { |
| if (newoperands) |
| VEC_free (vn_reference_op_s, heap, newoperands); |
| return NULL; |
| } |
| if (!newoperands) |
| newoperands = VEC_copy (vn_reference_op_s, heap, operands); |
| /* We may have changed from an SSA_NAME to a constant */ |
| if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME) |
| newop.opcode = TREE_CODE (op[0]); |
| newop.type = type; |
| newop.op0 = op[0]; |
| newop.op1 = op[1]; |
| newop.op2 = op[2]; |
| /* If it transforms a non-constant ARRAY_REF into a constant |
| one, adjust the constant offset. */ |
| if (newop.opcode == ARRAY_REF |
| && newop.off == -1 |
| && TREE_CODE (op[0]) == INTEGER_CST |
| && TREE_CODE (op[1]) == INTEGER_CST |
| && TREE_CODE (op[2]) == INTEGER_CST) |
| { |
| double_int off = tree_to_double_int (op[0]); |
| off += -tree_to_double_int (op[1]); |
| off *= tree_to_double_int (op[2]); |
| if (off.fits_shwi ()) |
| newop.off = off.low; |
| } |
| 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 && op[0] && TREE_CODE (op[0]) == ADDR_EXPR |
| && VEC_index (vn_reference_op_s, |
| newoperands, j - 1).opcode == MEM_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; |
| } |
| |
| 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 || newvuse != vuse) |
| { |
| unsigned int new_val_id; |
| pre_expr constant; |
| |
| tree result = vn_reference_lookup_pieces (newvuse, ref->set, |
| ref->type, |
| newoperands, |
| &newref, VN_WALK); |
| if (result) |
| VEC_free (vn_reference_op_s, heap, newoperands); |
| |
| /* We can always insert constants, so if we have a partial |
| redundant constant load of another type try to translate it |
| to a constant of appropriate type. */ |
| if (result && is_gimple_min_invariant (result)) |
| { |
| tree tem = result; |
| if (!useless_type_conversion_p (ref->type, TREE_TYPE (result))) |
| { |
| tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result); |
| if (tem && !is_gimple_min_invariant (tem)) |
| tem = NULL_TREE; |
| } |
| if (tem) |
| return get_or_alloc_expr_for_constant (tem); |
| } |
| |
| /* If we'd have to convert things we would need to validate |
| if we can insert the translated expression. So fail |
| here for now - we cannot insert an alias with a different |
| type in the VN tables either, as that would assert. */ |
| if (result |
| && !useless_type_conversion_p (ref->type, TREE_TYPE (result))) |
| return NULL; |
| else if (!result && newref |
| && !useless_type_conversion_p (ref->type, newref->type)) |
| { |
| VEC_free (vn_reference_op_s, heap, newoperands); |
| return NULL; |
| } |
| |
| expr = (pre_expr) pool_alloc (pre_expr_pool); |
| expr->kind = REFERENCE; |
| expr->id = 0; |
| |
| 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 |
| { |
| if (changed || !same_valid) |
| { |
| new_val_id = get_next_value_id (); |
| VEC_safe_grow_cleared (bitmap, 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); |
| } |
| VEC_free (vn_reference_op_s, heap, newoperands); |
| return expr; |
| } |
| break; |
| |
| case NAME: |
| { |
| tree name = PRE_EXPR_NAME (expr); |
| gimple def_stmt = SSA_NAME_DEF_STMT (name); |
| /* If the SSA name is defined by a PHI node in this block, |
| translate it. */ |
| if (gimple_code (def_stmt) == GIMPLE_PHI |
| && gimple_bb (def_stmt) == phiblock) |
| { |
| edge e = find_edge (pred, gimple_bb (def_stmt)); |
| tree def = PHI_ARG_DEF (def_stmt, e->dest_idx); |
| |
| /* Handle constant. */ |
| if (is_gimple_min_invariant (def)) |
| return get_or_alloc_expr_for_constant (def); |
| |
| return get_or_alloc_expr_for_name (def); |
| } |
| /* Otherwise return it unchanged - it will get cleaned if its |
| value is not available in PREDs AVAIL_OUT set of expressions. */ |
| return expr; |
| } |
| |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| /* Wrapper around phi_translate_1 providing caching functionality. */ |
| |
| static pre_expr |
| phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, |
| basic_block pred, basic_block phiblock) |
| { |
| pre_expr phitrans; |
| |
| if (!expr) |
| return NULL; |
| |
| /* Constants contain no values that need translation. */ |
| if (expr->kind == CONSTANT) |
| return expr; |
| |
| if (value_id_constant_p (get_expr_value_id (expr))) |
| return expr; |
| |
| if (expr->kind != NAME) |
| { |
| phitrans = phi_trans_lookup (expr, pred); |
| if (phitrans) |
| return phitrans; |
| } |
| |
| /* Translate. */ |
| phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock); |
| |
| /* Don't add empty translations to the cache. Neither add |
| translations of NAMEs as those are cheap to translate. */ |
| if (phitrans |
| && expr->kind != NAME) |
| phi_trans_add (expr, phitrans, pred); |
| |
| return phitrans; |
| } |
| |
| |
| /* For each expression in SET, translate the values through phi nodes |
| in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting |
| expressions in DEST. */ |
| |
| static void |
| phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred, |
| basic_block phiblock) |
| { |
| VEC (pre_expr, heap) *exprs; |
| pre_expr expr; |
| int i; |
| |
| if (gimple_seq_empty_p (phi_nodes (phiblock))) |
| { |
| bitmap_set_copy (dest, set); |
| return; |
| } |
| |
| exprs = sorted_array_from_bitmap_set (set); |
| FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) |
| { |
| pre_expr translated; |
| translated = phi_translate (expr, set, NULL, pred, phiblock); |
| if (!translated) |
| continue; |
| |
| /* 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); |
| } |
| |
| /* Find the leader for a value (i.e., the name representing that |
| value) in a given set, and return it. If STMT is non-NULL it |
| makes sure the defining statement for the leader dominates it. |
| Return NULL if no leader is found. */ |
| |
| static pre_expr |
| bitmap_find_leader (bitmap_set_t set, unsigned int val) |
| { |
| if (value_id_constant_p (val)) |
| { |
| unsigned int i; |
| bitmap_iterator bi; |
| bitmap exprset = VEC_index (bitmap, value_expressions, val); |
| |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| if (expr->kind == CONSTANT) |
| return expr; |
| } |
| } |
| if (bitmap_set_contains_value (set, val)) |
| { |
| /* Rather than walk the entire bitmap of expressions, and see |
| whether any of them has the value we are looking for, we look |
| at the reverse mapping, which tells us the set of expressions |
| that have a given value (IE value->expressions with that |
| value) and see if any of those expressions are in our set. |
| The number of expressions per value is usually significantly |
| less than the number of expressions in the set. In fact, for |
| large testcases, doing it this way is roughly 5-10x faster |
| than walking the bitmap. |
| If this is somehow a significant lose for some cases, we can |
| choose which set to walk based on which set is smaller. */ |
| unsigned int i; |
| bitmap_iterator bi; |
| bitmap exprset = VEC_index (bitmap, value_expressions, val); |
| |
| EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi) |
| return expression_for_id (i); |
| } |
| return NULL; |
| } |
| |
| /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of |
| BLOCK by seeing if it is not killed in the block. Note that we are |
| only determining whether there is a store that kills it. Because |
| of the order in which clean iterates over values, we are guaranteed |
| that altered operands will have caused us to be eliminated from the |
| ANTIC_IN set already. */ |
| |
| static bool |
| value_dies_in_block_x (pre_expr expr, basic_block block) |
| { |
| 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; |
| |
| /* 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)) |
| { |
| tree def_vuse, def_vdef; |
| def = gsi_stmt (gsi); |
| def_vuse = gimple_vuse (def); |
| def_vdef = gimple_vdef (def); |
| |
| /* Not a memory statement. */ |
| if (!def_vuse) |
| continue; |
| |
| /* 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; |
| } |
| } |
| |
| /* 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; |
| } |
| |
| |
| /* Determine if OP is valid in SET1 U SET2, which it is when the union |
| contains its value-id. */ |
| |
| static bool |
| op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op) |
| { |
| if (op && TREE_CODE (op) == SSA_NAME) |
| { |
| unsigned int value_id = VN_INFO (op)->value_id; |
| if (!(bitmap_set_contains_value (set1, value_id) |
| || (set2 && bitmap_set_contains_value (set2, value_id)))) |
| return false; |
| } |
| return true; |
| } |
| |
| /* Determine if the expression EXPR is valid in SET1 U 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 vuse is killed in this block. */ |
| |
| static bool |
| valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr, |
| basic_block block) |
| { |
| switch (expr->kind) |
| { |
| case NAME: |
| return bitmap_set_contains_expr (AVAIL_OUT (block), expr); |
| case NARY: |
| { |
| unsigned int i; |
| vn_nary_op_t nary = PRE_EXPR_NARY (expr); |
| for (i = 0; i < nary->length; i++) |
| if (!op_valid_in_sets (set1, set2, nary->op[i])) |
| return false; |
| return true; |
| } |
| break; |
| case REFERENCE: |
| { |
| vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
| vn_reference_op_t vro; |
| unsigned int i; |
| |
| FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, i, vro) |
| { |
| if (!op_valid_in_sets (set1, set2, vro->op0) |
| || !op_valid_in_sets (set1, set2, vro->op1) |
| || !op_valid_in_sets (set1, set2, vro->op2)) |
| return false; |
| } |
| return true; |
| } |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| /* Clean the set of expressions that are no longer valid in SET1 or |
| SET2. This means expressions that are made up of values we have no |
| leaders for in SET1 or SET2. This version is used for partial |
| anticipation, which means it is not valid in either ANTIC_IN or |
| PA_IN. */ |
| |
| static void |
| dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block) |
| { |
| VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1); |
| pre_expr expr; |
| int i; |
| |
| FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) |
| { |
| if (!valid_in_sets (set1, set2, expr, block)) |
| bitmap_remove_from_set (set1, expr); |
| } |
| VEC_free (pre_expr, heap, exprs); |
| } |
| |
| /* Clean the set of expressions that are no longer valid in SET. This |
| means expressions that are made up of values we have no leaders for |
| in SET. */ |
| |
| static void |
| clean (bitmap_set_t set, basic_block block) |
| { |
| VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set); |
| pre_expr expr; |
| int i; |
| |
| FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) |
| { |
| if (!valid_in_sets (set, NULL, expr, block)) |
| bitmap_remove_from_set (set, expr); |
| } |
| VEC_free (pre_expr, heap, exprs); |
| } |
| |
| /* Clean the set of expressions that are no longer valid in SET because |
| they are clobbered in BLOCK or because they trap and may not be executed. */ |
| |
| static void |
| prune_clobbered_mems (bitmap_set_t set, basic_block block) |
| { |
| bitmap_iterator bi; |
| unsigned i; |
| |
| FOR_EACH_EXPR_ID_IN_SET (set, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| if (expr->kind == REFERENCE) |
| { |
| vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
| 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))) |
| || (gimple_bb (def_stmt) == block |
| && value_dies_in_block_x (expr, block)))) |
| bitmap_remove_from_set (set, expr); |
| } |
| } |
| else if (expr->kind == NARY) |
| { |
| vn_nary_op_t nary = PRE_EXPR_NARY (expr); |
| /* 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)) |
| bitmap_remove_from_set (set, expr); |
| } |
| } |
| } |
| |
| static sbitmap has_abnormal_preds; |
| |
| /* List of blocks that may have changed during ANTIC computation and |
| thus need to be iterated over. */ |
| |
| static sbitmap changed_blocks; |
| |
| /* Decide whether to defer a block for a later iteration, or PHI |
| translate SOURCE to DEST using phis in PHIBLOCK. Return false if we |
| should defer the block, and true if we processed it. */ |
| |
| static bool |
| defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source, |
| basic_block block, basic_block phiblock) |
| { |
| if (!BB_VISITED (phiblock)) |
| { |
| SET_BIT (changed_blocks, block->index); |
| BB_VISITED (block) = 0; |
| BB_DEFERRED (block) = 1; |
| return false; |
| } |
| else |
| phi_translate_set (dest, source, block, phiblock); |
| return true; |
| } |
| |
| /* Compute the ANTIC set for BLOCK. |
| |
| If succs(BLOCK) > 1 then |
| ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK) |
| else if succs(BLOCK) == 1 then |
| ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) |
| |
| ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK]) |
| */ |
| |
| static bool |
| compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) |
| { |
| bool changed = false; |
| bitmap_set_t S, old, ANTIC_OUT; |
| bitmap_iterator bi; |
| unsigned int bii; |
| edge e; |
| edge_iterator ei; |
| |
| old = ANTIC_OUT = S = NULL; |
| BB_VISITED (block) = 1; |
| |
| /* If any edges from predecessors are abnormal, antic_in is empty, |
| so do nothing. */ |
| if (block_has_abnormal_pred_edge) |
| goto maybe_dump_sets; |
| |
| old = ANTIC_IN (block); |
| ANTIC_OUT = bitmap_set_new (); |
| |
| /* If the block has no successors, ANTIC_OUT is empty. */ |
| if (EDGE_COUNT (block->succs) == 0) |
| ; |
| /* If we have one successor, we could have some phi nodes to |
| translate through. */ |
| else if (single_succ_p (block)) |
| { |
| basic_block succ_bb = single_succ (block); |
| |
| /* We trade iterations of the dataflow equations for having to |
| phi translate the maximal set, which is incredibly slow |
| (since the maximal set often has 300+ members, even when you |
| have a small number of blocks). |
| Basically, we defer the computation of ANTIC for this block |
| until we have processed it's successor, which will inevitably |
| have a *much* smaller set of values to phi translate once |
| clean has been run on it. |
| The cost of doing this is that we technically perform more |
| iterations, however, they are lower cost iterations. |
| |
| Timings for PRE on tramp3d-v4: |
| without maximal set fix: 11 seconds |
| with maximal set fix/without deferring: 26 seconds |
| with maximal set fix/with deferring: 11 seconds |
| */ |
| |
| if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb), |
| block, succ_bb)) |
| { |
| changed = true; |
| goto maybe_dump_sets; |
| } |
| } |
| /* If we have multiple successors, we take the intersection of all of |
| them. Note that in the case of loop exit phi nodes, we may have |
| phis to translate through. */ |
| else |
| { |
| VEC(basic_block, heap) * worklist; |
| size_t i; |
| basic_block bprime, first = NULL; |
| |
| worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs)); |
| FOR_EACH_EDGE (e, ei, block->succs) |
| { |
| if (!first |
| && BB_VISITED (e->dest)) |
| first = e->dest; |
| else if (BB_VISITED (e->dest)) |
| VEC_quick_push (basic_block, worklist, e->dest); |
| } |
| |
| /* Of multiple successors we have to have visited one already. */ |
| if (!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; |
| } |
| |
| 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_EACH_VEC_ELT (basic_block, worklist, i, bprime) |
| { |
| if (!gimple_seq_empty_p (phi_nodes (bprime))) |
| { |
| bitmap_set_t tmp = bitmap_set_new (); |
| phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime); |
| bitmap_set_and (ANTIC_OUT, tmp); |
| bitmap_set_free (tmp); |
| } |
| else |
| bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime)); |
| } |
| VEC_free (basic_block, heap, worklist); |
| } |
| |
| /* Prune expressions that are clobbered in block and thus become |
| invalid if translated from ANTIC_OUT to ANTIC_IN. */ |
| prune_clobbered_mems (ANTIC_OUT, block); |
| |
| /* Generate ANTIC_OUT - TMP_GEN. */ |
| S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block)); |
| |
| /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */ |
| ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block), |
| TMP_GEN (block)); |
| |
| /* Then union in the ANTIC_OUT - TMP_GEN values, |
| to get ANTIC_OUT U EXP_GEN - TMP_GEN */ |
| FOR_EACH_EXPR_ID_IN_SET (S, bii, bi) |
| bitmap_value_insert_into_set (ANTIC_IN (block), |
| expression_for_id (bii)); |
| |
| clean (ANTIC_IN (block), block); |
| |
| if (!bitmap_set_equal (old, ANTIC_IN (block))) |
| { |
| changed = true; |
| SET_BIT (changed_blocks, block->index); |
| FOR_EACH_EDGE (e, ei, block->preds) |
| SET_BIT (changed_blocks, e->src->index); |
| } |
| else |
| RESET_BIT (changed_blocks, block->index); |
| |
| maybe_dump_sets: |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| if (!BB_DEFERRED (block) || BB_VISITED (block)) |
| { |
| if (ANTIC_OUT) |
| print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index); |
| |
| print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN", |
| block->index); |
| |
| if (S) |
| print_bitmap_set (dump_file, S, "S", block->index); |
| } |
| else |
| { |
| fprintf (dump_file, |
| "Block %d was deferred for a future iteration.\n", |
| block->index); |
| } |
| } |
| if (old) |
| bitmap_set_free (old); |
| if (S) |
| bitmap_set_free (S); |
| if (ANTIC_OUT) |
| bitmap_set_free (ANTIC_OUT); |
| return changed; |
| } |
| |
| /* Compute PARTIAL_ANTIC for BLOCK. |
| |
| If succs(BLOCK) > 1 then |
| PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not |
| in ANTIC_OUT for all succ(BLOCK) |
| else if succs(BLOCK) == 1 then |
| PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)]) |
| |
| PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] |
| - ANTIC_IN[BLOCK]) |
| |
| */ |
| static bool |
| compute_partial_antic_aux (basic_block block, |
| bool block_has_abnormal_pred_edge) |
| { |
| bool changed = false; |
| bitmap_set_t old_PA_IN; |
| bitmap_set_t PA_OUT; |
| edge e; |
| edge_iterator ei; |
| unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH); |
| |
| old_PA_IN = PA_OUT = NULL; |
| |
| /* If any edges from predecessors are abnormal, antic_in is empty, |
| so do nothing. */ |
| if (block_has_abnormal_pred_edge) |
| goto maybe_dump_sets; |
| |
| /* If there are too many partially anticipatable values in the |
| block, phi_translate_set can take an exponential time: stop |
| before the translation starts. */ |
| if (max_pa |
| && single_succ_p (block) |
| && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa) |
| goto maybe_dump_sets; |
| |
| old_PA_IN = PA_IN (block); |
| PA_OUT = bitmap_set_new (); |
| |
| /* If the block has no successors, ANTIC_OUT is empty. */ |
| if (EDGE_COUNT (block->succs) == 0) |
| ; |
| /* If we have one successor, we could have some phi nodes to |
| translate through. Note that we can't phi translate across DFS |
| back edges in partial antic, because it uses a union operation on |
| the successors. For recurrences like IV's, we will end up |
| generating a new value in the set on each go around (i + 3 (VH.1) |
| VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */ |
| else if (single_succ_p (block)) |
| { |
| basic_block succ = single_succ (block); |
| if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK)) |
| phi_translate_set (PA_OUT, PA_IN (succ), block, succ); |
| } |
| /* If we have multiple successors, we take the union of all of |
| them. */ |
| else |
| { |
| VEC(basic_block, heap) * worklist; |
| size_t i; |
| basic_block bprime; |
| |
| worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs)); |
| FOR_EACH_EDGE (e, ei, block->succs) |
| { |
| if (e->flags & EDGE_DFS_BACK) |
| continue; |
| VEC_quick_push (basic_block, worklist, e->dest); |
| } |
| if (VEC_length (basic_block, worklist) > 0) |
| { |
| FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime) |
| { |
| unsigned int i; |
| bitmap_iterator bi; |
| |
| FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi) |
| bitmap_value_insert_into_set (PA_OUT, |
| expression_for_id (i)); |
| if (!gimple_seq_empty_p (phi_nodes (bprime))) |
| { |
| bitmap_set_t pa_in = bitmap_set_new (); |
| phi_translate_set (pa_in, PA_IN (bprime), block, bprime); |
| FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi) |
| bitmap_value_insert_into_set (PA_OUT, |
| expression_for_id (i)); |
| bitmap_set_free (pa_in); |
| } |
| else |
| FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi) |
| bitmap_value_insert_into_set (PA_OUT, |
| expression_for_id (i)); |
| } |
| } |
| VEC_free (basic_block, heap, worklist); |
| } |
| |
| /* Prune expressions that are clobbered in block and thus become |
| invalid if translated from PA_OUT to PA_IN. */ |
| prune_clobbered_mems (PA_OUT, block); |
| |
| /* PA_IN starts with PA_OUT - TMP_GEN. |
| Then we subtract things from ANTIC_IN. */ |
| PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block)); |
| |
| /* For partial antic, we want to put back in the phi results, since |
| we will properly avoid making them partially antic over backedges. */ |
| bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values); |
| bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions); |
| |
| /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */ |
| bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block)); |
| |
| dependent_clean (PA_IN (block), ANTIC_IN (block), block); |
| |
| if (!bitmap_set_equal (old_PA_IN, PA_IN (block))) |
| { |
| changed = true; |
| SET_BIT (changed_blocks, block->index); |
| FOR_EACH_EDGE (e, ei, block->preds) |
| SET_BIT (changed_blocks, e->src->index); |
| } |
| else |
| RESET_BIT (changed_blocks, block->index); |
| |
| maybe_dump_sets: |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| if (PA_OUT) |
| print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index); |
| |
| print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index); |
| } |
| if (old_PA_IN) |
| bitmap_set_free (old_PA_IN); |
| if (PA_OUT) |
| bitmap_set_free (PA_OUT); |
| return changed; |
| } |
| |
| /* Compute ANTIC and partial ANTIC sets. */ |
| |
| static void |
| compute_antic (void) |
| { |
| bool changed = true; |
| int num_iterations = 0; |
| basic_block block; |
| int i; |
| |
| /* If any predecessor edges are abnormal, we punt, so antic_in is empty. |
| We pre-build the map of blocks with incoming abnormal edges here. */ |
| has_abnormal_preds = sbitmap_alloc (last_basic_block); |
| sbitmap_zero (has_abnormal_preds); |
| |
| FOR_EACH_BB (block) |
| { |
| edge_iterator ei; |
| edge e; |
| |
| FOR_EACH_EDGE (e, ei, block->preds) |
| { |
| e->flags &= ~EDGE_DFS_BACK; |
| if (e->flags & EDGE_ABNORMAL) |
| { |
| SET_BIT (has_abnormal_preds, block->index); |
| break; |
| } |
| } |
| |
| 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 (); |
| } |
| |
| /* At the exit block we anticipate nothing. */ |
| ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new (); |
| BB_VISITED (EXIT_BLOCK_PTR) = 1; |
| PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new (); |
| |
| changed_blocks = sbitmap_alloc (last_basic_block + 1); |
| sbitmap_ones (changed_blocks); |
| while (changed) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "Starting iteration %d\n", num_iterations); |
| /* ??? We need to clear our PHI translation cache here as the |
| ANTIC sets shrink and we restrict valid translations to |
| those having operands with leaders in ANTIC. Same below |
| for PA ANTIC computation. */ |
| num_iterations++; |
| changed = false; |
| for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--) |
| { |
| if (TEST_BIT (changed_blocks, postorder[i])) |
| { |
| basic_block block = BASIC_BLOCK (postorder[i]); |
| changed |= compute_antic_aux (block, |
| TEST_BIT (has_abnormal_preds, |
| block->index)); |
| } |
| } |
| /* Theoretically possible, but *highly* unlikely. */ |
| gcc_checking_assert (num_iterations < 500); |
| } |
| |
| statistics_histogram_event (cfun, "compute_antic iterations", |
| num_iterations); |
| |
| if (do_partial_partial) |
| { |
| sbitmap_ones (changed_blocks); |
| mark_dfs_back_edges (); |
| num_iterations = 0; |
| changed = true; |
| while (changed) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "Starting iteration %d\n", num_iterations); |
| num_iterations++; |
| changed = false; |
| for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--) |
| { |
| if (TEST_BIT (changed_blocks, postorder[i])) |
| { |
| basic_block block = BASIC_BLOCK (postorder[i]); |
| changed |
| |= compute_partial_antic_aux (block, |
| TEST_BIT (has_abnormal_preds, |
| block->index)); |
| } |
| } |
| /* Theoretically possible, but *highly* unlikely. */ |
| gcc_checking_assert (num_iterations < 500); |
| } |
| statistics_histogram_event (cfun, "compute_partial_antic iterations", |
| num_iterations); |
| } |
| sbitmap_free (has_abnormal_preds); |
| sbitmap_free (changed_blocks); |
| } |
| |
| |
| /* 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 bitmap inserted_exprs; |
| |
| /* The actual worker for create_component_ref_by_pieces. */ |
| |
| static tree |
| create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref, |
| unsigned int *operand, gimple_seq *stmts) |
| { |
| vn_reference_op_t currop = &VEC_index (vn_reference_op_s, ref->operands, |
| *operand); |
| tree genop; |
| ++*operand; |
| switch (currop->opcode) |
| { |
| case CALL_EXPR: |
| { |
| tree folded, sc = NULL_TREE; |
| unsigned int nargs = 0; |
| tree fn, *args; |
| if (TREE_CODE (currop->op0) == FUNCTION_DECL) |
| fn = currop->op0; |
| else |
| fn = find_or_generate_expression (block, currop->op0, stmts); |
| if (currop->op1) |
| sc = find_or_generate_expression (block, currop->op1, stmts); |
| 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); |
| nargs++; |
| } |
| folded = build_call_array (currop->type, |
| (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; |
| } |
| |
| case MEM_REF: |
| { |
| tree baseop = create_component_ref_by_pieces_1 (block, ref, operand, |
| stmts); |
| tree offset = currop->op0; |
| if (TREE_CODE (baseop) == ADDR_EXPR |
| && handled_component_p (TREE_OPERAND (baseop, 0))) |
| { |
| HOST_WIDE_INT off; |
| tree base; |
| base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0), |
| &off); |
| gcc_assert (base); |
| offset = int_const_binop (PLUS_EXPR, offset, |
| build_int_cst (TREE_TYPE (offset), |
| off)); |
| baseop = build_fold_addr_expr (base); |
| } |
| return fold_build2 (MEM_REF, currop->type, baseop, offset); |
| } |
| |
| case TARGET_MEM_REF: |
| { |
| tree genop0 = NULL_TREE, genop1 = NULL_TREE; |
| vn_reference_op_t nextop = &VEC_index (vn_reference_op_s, ref->operands, |
| ++*operand); |
| tree baseop = create_component_ref_by_pieces_1 (block, ref, operand, |
| stmts); |
| if (currop->op0) |
| genop0 = find_or_generate_expression (block, currop->op0, stmts); |
| if (nextop->op0) |
| genop1 = find_or_generate_expression (block, nextop->op0, stmts); |
| return build5 (TARGET_MEM_REF, currop->type, |
| baseop, currop->op2, genop0, currop->op1, genop1); |
| } |
| |
| case ADDR_EXPR: |
| if (currop->op0) |
| { |
| gcc_assert (is_gimple_min_invariant (currop->op0)); |
| return currop->op0; |
| } |
| /* Fallthrough. */ |
| case REALPART_EXPR: |
| case IMAGPART_EXPR: |
| case VIEW_CONVERT_EXPR: |
| { |
| tree genop0 = create_component_ref_by_pieces_1 (block, ref, |
| operand, stmts); |
| return fold_build1 (currop->opcode, currop->type, genop0); |
| } |
| |
| case WITH_SIZE_EXPR: |
| { |
| tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand, |
| stmts); |
| tree genop1 = find_or_generate_expression (block, currop->op0, stmts); |
| return fold_build2 (currop->opcode, currop->type, genop0, genop1); |
| } |
| |
| case BIT_FIELD_REF: |
| { |
| tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand, |
| stmts); |
| tree op1 = currop->op0; |
| tree op2 = currop->op1; |
| return fold_build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2); |
| } |
| |
| /* For array ref vn_reference_op's, operand 1 of the array ref |
| is op0 of the reference op and operand 3 of the array ref is |
| op1. */ |
| case ARRAY_RANGE_REF: |
| case ARRAY_REF: |
| { |
| tree genop0; |
| tree genop1 = currop->op0; |
| tree genop2 = currop->op1; |
| tree genop3 = currop->op2; |
| genop0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts); |
| genop1 = find_or_generate_expression (block, genop1, stmts); |
| if (genop2) |
| { |
| tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0)); |
| /* Drop zero minimum index if redundant. */ |
| if (integer_zerop (genop2) |
| && (!domain_type |
| || integer_zerop (TYPE_MIN_VALUE (domain_type)))) |
| genop2 = NULL_TREE; |
| else |
| genop2 = find_or_generate_expression (block, genop2, stmts); |
| } |
| 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))); |
| genop3 = find_or_generate_expression (block, genop3, stmts); |
| } |
| } |
| return build4 (currop->opcode, currop->type, genop0, genop1, |
| genop2, genop3); |
| } |
| case COMPONENT_REF: |
| { |
| tree op0; |
| tree op1; |
| tree genop2 = currop->op1; |
| op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts); |
| /* op1 should be a FIELD_DECL, which are represented by themselves. */ |
| op1 = currop->op0; |
| if (genop2) |
| genop2 = find_or_generate_expression (block, genop2, stmts); |
| return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2); |
| } |
| |
| case SSA_NAME: |
| { |
| genop = find_or_generate_expression (block, currop->op0, stmts); |
| return genop; |
| } |
| case STRING_CST: |
| case INTEGER_CST: |
| case COMPLEX_CST: |
| case VECTOR_CST: |
| case REAL_CST: |
| case CONSTRUCTOR: |
| case VAR_DECL: |
| case PARM_DECL: |
| case CONST_DECL: |
| case RESULT_DECL: |
| case FUNCTION_DECL: |
| return currop->op0; |
| |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the |
| COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with |
| trying to rename aggregates into ssa form directly, which is a no no. |
| |
| Thus, this routine doesn't create temporaries, it just builds a |
| single access expression for the array, calling |
| find_or_generate_expression to build the innermost pieces. |
| |
| This function is a subroutine of create_expression_by_pieces, and |
| should not be called on it's own unless you really know what you |
| are doing. */ |
| |
| static tree |
| create_component_ref_by_pieces (basic_block block, vn_reference_t ref, |
| gimple_seq *stmts) |
| { |
| unsigned int op = 0; |
| return create_component_ref_by_pieces_1 (block, ref, &op, stmts); |
| } |
| |
| /* Find a leader for an expression, or generate one using |
| create_expression_by_pieces if it's ANTIC but |
| complex. |
| BLOCK is the basic_block we are looking for leaders in. |
| OP is the tree expression to find a leader for or generate. |
| STMTS is the statement list to put the inserted expressions on. |
| Returns the SSA_NAME of the LHS of the generated expression or the |
| leader. |
| DOMSTMT if non-NULL is a statement that should be dominated by |
| all uses in the generated expression. If DOMSTMT is non-NULL this |
| routine can fail and return NULL_TREE. Otherwise it will assert |
| on failure. */ |
| |
| static tree |
| find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts) |
| { |
| pre_expr expr = get_or_alloc_expr_for (op); |
| unsigned int lookfor = get_expr_value_id (expr); |
| pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor); |
| if (leader) |
| { |
| if (leader->kind == NAME) |
| return PRE_EXPR_NAME (leader); |
| else if (leader->kind == CONSTANT) |
| return PRE_EXPR_CONSTANT (leader); |
| } |
| |
| /* It must be a complex expression, so generate it recursively. */ |
| bitmap exprset = VEC_index (bitmap, value_expressions, lookfor); |
| bitmap_iterator bi; |
| unsigned int i; |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) |
| { |
| pre_expr temp = expression_for_id (i); |
| if (temp->kind != NAME) |
| return create_expression_by_pieces (block, temp, stmts, |
| get_expr_type (expr)); |
| } |
| |
| gcc_unreachable (); |
| } |
| |
| #define NECESSARY GF_PLF_1 |
| |
| /* Create an expression in pieces, so that we can handle very complex |
| expressions that may be ANTIC, but not necessary GIMPLE. |
| BLOCK is the basic block the expression will be inserted into, |
| EXPR is the expression to insert (in value form) |
| STMTS is a statement list to append the necessary insertions into. |
| |
| This function will die if we hit some value that shouldn't be |
| ANTIC but is (IE there is no leader for it, or its components). |
| This function may also generate expressions that are themselves |
| partially or fully redundant. Those that are will be either made |
| fully redundant during the next iteration of insert (for partially |
| redundant ones), or eliminated by eliminate (for fully redundant |
| ones). |
| |
| If DOMSTMT is non-NULL then we make sure that all uses in the |
| expressions dominate that statement. In this case the function |
| can return NULL_TREE to signal failure. */ |
| |
| static tree |
| create_expression_by_pieces (basic_block block, pre_expr expr, |
| gimple_seq *stmts, tree type) |
| { |
| tree name; |
| tree folded; |
| gimple_seq forced_stmts = NULL; |
| unsigned int value_id; |
| gimple_stmt_iterator gsi; |
| tree exprtype = type ? type : get_expr_type (expr); |
| pre_expr nameexpr; |
| gimple newstmt; |
| |
| switch (expr->kind) |
| { |
| /* We may hit the NAME/CONSTANT case if we have to convert types |
| that value numbering saw through. */ |
| case NAME: |
| folded = PRE_EXPR_NAME (expr); |
| break; |
| case CONSTANT: |
| folded = PRE_EXPR_CONSTANT (expr); |
| break; |
| case REFERENCE: |
| { |
| vn_reference_t ref = PRE_EXPR_REFERENCE (expr); |
| folded = create_component_ref_by_pieces (block, ref, stmts); |
| } |
| break; |
| case NARY: |
| { |
| vn_nary_op_t nary = PRE_EXPR_NARY (expr); |
| tree genop[4]; |
| unsigned i; |
| for (i = 0; i < nary->length; ++i) |
| { |
| genop[i] = find_or_generate_expression (block, nary->op[i], stmts); |
| /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It |
| may have conversions stripped. */ |
| if (nary->opcode == POINTER_PLUS_EXPR) |
| { |
| if (i == 0) |
| genop[i] = fold_convert (nary->type, genop[i]); |
| else if (i == 1) |
| genop[i] = convert_to_ptrofftype (genop[i]); |
| } |
| else |
| genop[i] = fold_convert (TREE_TYPE (nary->op[i]), genop[i]); |
| } |
| if (nary->opcode == CONSTRUCTOR) |
| { |
| VEC(constructor_elt,gc) *elts = NULL; |
| for (i = 0; i < nary->length; ++i) |
| CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]); |
| folded = build_constructor (nary->type, elts); |
| } |
| else |
| { |
| switch (nary->length) |
| { |
| case 1: |
| folded = fold_build1 (nary->opcode, nary->type, |
| genop[0]); |
| break; |
| case 2: |
| folded = fold_build2 (nary->opcode, nary->type, |
| genop[0], genop[1]); |
| break; |
| case 3: |
| folded = fold_build3 (nary->opcode, nary->type, |
| genop[0], genop[1], genop[3]); |
| break; |
| default: |
| gcc_unreachable (); |
| } |
| } |
| } |
| break; |
| default: |
| gcc_unreachable (); |
| } |
| |
| 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. */ |
| 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. */ |
| if (forced_stmts) |
| { |
| gsi = gsi_start (forced_stmts); |
| for (; !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| gimple stmt = gsi_stmt (gsi); |
| tree forcedname = gimple_get_lhs (stmt); |
| pre_expr nameexpr; |
| |
| 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); |
| bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); |
| } |
| } |
| gimple_seq_add_seq (stmts, forced_stmts); |
| } |
| |
| name = make_temp_ssa_name (exprtype, NULL, "pretmp"); |
| newstmt = gimple_build_assign (name, folded); |
| gimple_set_plf (newstmt, NECESSARY, false); |
| |
| gimple_seq_add_stmt (stmts, newstmt); |
| bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name)); |
| |
| /* Fold the last statement. */ |
| gsi = gsi_last (*stmts); |
| if (fold_stmt_inplace (&gsi)) |
| update_stmt (gsi_stmt (gsi)); |
| |
| /* Add a value number to the temporary. |
| The value may already exist in either NEW_SETS, or AVAIL_OUT, because |
| we are creating the expression by pieces, and this particular piece of |
| the expression may have been represented. There is no harm in replacing |
| here. */ |
| value_id = get_expr_value_id (expr); |
| VN_INFO_GET (name)->value_id = value_id; |
| VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id); |
| if (VN_INFO (name)->valnum == NULL_TREE) |
| VN_INFO (name)->valnum = name; |
| gcc_assert (VN_INFO (name)->valnum != NULL_TREE); |
| nameexpr = get_or_alloc_expr_for_name (name); |
| add_to_value (value_id, nameexpr); |
| if (NEW_SETS (block)) |
| bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); |
| bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); |
| |
| pre_stats.insertions++; |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Inserted "); |
| print_gimple_stmt (dump_file, newstmt, 0, 0); |
| fprintf (dump_file, " in predecessor %d\n", block->index); |
| } |
| |
| return name; |
| } |
| |
| |
| /* 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_EACH_VEC_ELT (vn_reference_op_s, ops, i, op) |
| { |
| switch (op->opcode) |
| { |
| case CALL_EXPR: |
| /* Calls are not a problem. */ |
| return false; |
| |
| 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 |
| NODE. Return true if we have inserted new stuff. */ |
| |
| static bool |
| insert_into_preds_of_block (basic_block block, unsigned int exprnum, |
| VEC(pre_expr, heap) *avail) |
| { |
| pre_expr expr = expression_for_id (exprnum); |
| pre_expr newphi; |
| unsigned int val = get_expr_value_id (expr); |
| edge pred; |
| bool insertions = false; |
| bool nophi = false; |
| basic_block bprime; |
| pre_expr eprime; |
| edge_iterator ei; |
| tree type = get_expr_type (expr); |
| tree temp; |
| gimple phi; |
| |
| /* Make sure we aren't creating an induction variable. */ |
| if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2) |
| { |
| bool firstinsideloop = false; |
| bool secondinsideloop = false; |
| firstinsideloop = flow_bb_inside_loop_p (block->loop_father, |
| EDGE_PRED (block, 0)->src); |
| 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) |
| && (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"); |
| nophi = true; |
| } |
| } |
| |
| /* Make the necessary insertions. */ |
| FOR_EACH_EDGE (pred, ei, block->preds) |
| { |
| gimple_seq stmts = NULL; |
| tree builtexpr; |
| bprime = pred->src; |
| eprime = VEC_index (pre_expr, avail, pred->dest_idx); |
| |
| if (eprime->kind != NAME && eprime->kind != CONSTANT) |
| { |
| builtexpr = create_expression_by_pieces (bprime, eprime, |
| &stmts, type); |
| gcc_assert (!(pred->flags & EDGE_ABNORMAL)); |
| gsi_insert_seq_on_edge (pred, stmts); |
| VEC_replace (pre_expr, avail, pred->dest_idx, |
| get_or_alloc_expr_for_name (builtexpr)); |
| insertions = true; |
| } |
| else if (eprime->kind == CONSTANT) |
| { |
| /* Constants may not have the right type, fold_convert |
| should give us back a constant with the right type. */ |
| tree constant = PRE_EXPR_CONSTANT (eprime); |
| if (!useless_type_conversion_p (type, TREE_TYPE (constant))) |
| { |
| tree builtexpr = fold_convert (type, constant); |
| if (!is_gimple_min_invariant (builtexpr)) |
| { |
| tree forcedexpr = force_gimple_operand (builtexpr, |
| &stmts, true, |
| NULL); |
| if (!is_gimple_min_invariant (forcedexpr)) |
| { |
| if (forcedexpr != builtexpr) |
| { |
| VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime); |
| VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime); |
| } |
| if (stmts) |
| { |
| gimple_stmt_iterator gsi; |
| gsi = gsi_start (stmts); |
| for (; !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| gimple stmt = gsi_stmt (gsi); |
| 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); |
| } |
| VEC_replace (pre_expr, avail, pred->dest_idx, |
| get_or_alloc_expr_for_name (forcedexpr)); |
| } |
| } |
| else |
| VEC_replace (pre_expr, avail, pred->dest_idx, |
| get_or_alloc_expr_for_constant (builtexpr)); |
| } |
| } |
| else if (eprime->kind == NAME) |
| { |
| /* We may have to do a conversion because our value |
| numbering can look through types in certain cases, but |
| our IL requires all operands of a phi node have the same |
| type. */ |
| tree name = PRE_EXPR_NAME (eprime); |
| if (!useless_type_conversion_p (type, TREE_TYPE (name))) |
| { |
| tree builtexpr; |
| tree forcedexpr; |
| builtexpr = fold_convert (type, name); |
| forcedexpr = force_gimple_operand (builtexpr, |
| &stmts, true, |
| NULL); |
| |
| if (forcedexpr != name) |
| { |
| VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum; |
| VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id; |
| } |
| |
| if (stmts) |
| { |
| gimple_stmt_iterator gsi; |
| gsi = gsi_start (stmts); |
| for (; !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| gimple stmt = gsi_stmt (gsi); |
| 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); |
| } |
| VEC_replace (pre_expr, avail, pred->dest_idx, |
| get_or_alloc_expr_for_name (forcedexpr)); |
| } |
| } |
| } |
| /* If we didn't want a phi node, and we made insertions, we still have |
| inserted new stuff, and thus return true. If we didn't want a phi node, |
| and didn't make insertions, we haven't added anything new, so return |
| false. */ |
| if (nophi && insertions) |
| return true; |
| else if (nophi && !insertions) |
| return false; |
| |
| /* Now build a phi for the new variable. */ |
| temp = make_temp_ssa_name (type, NULL, "prephitmp"); |
| phi = create_phi_node (temp, block); |
| |
| gimple_set_plf (phi, NECESSARY, false); |
| VN_INFO_GET (temp)->value_id = val; |
| VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val); |
| if (VN_INFO (temp)->valnum == NULL_TREE) |
| VN_INFO (temp)->valnum = temp; |
| bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp)); |
| FOR_EACH_EDGE (pred, ei, block->preds) |
| { |
| pre_expr ae = VEC_index (pre_expr, avail, pred->dest_idx); |
| 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, UNKNOWN_LOCATION); |
| else |
| add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION); |
| } |
| |
| newphi = get_or_alloc_expr_for_name (temp); |
| add_to_value (val, newphi); |
| |
| /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing |
| this insertion, since we test for the existence of this value in PHI_GEN |
| before proceeding with the partial redundancy checks in insert_aux. |
| |
| The value may exist in AVAIL_OUT, in particular, it could be represented |
| by the expression we are trying to eliminate, in which case we want the |
| replacement to occur. If it's not existing in AVAIL_OUT, we want it |
| inserted there. |
| |
| Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of |
| this block, because if it did, it would have existed in our dominator's |
| AVAIL_OUT, and would have been skipped due to the full redundancy check. |
| */ |
| |
| bitmap_insert_into_set (PHI_GEN (block), newphi); |
| bitmap_value_replace_in_set (AVAIL_OUT (block), |
| newphi); |
| bitmap_insert_into_set (NEW_SETS (block), |
| newphi); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Created phi "); |
| print_gimple_stmt (dump_file, phi, 0, 0); |
| fprintf (dump_file, " in block %d\n", block->index); |
| } |
| pre_stats.phis++; |
| return true; |
| } |
| |
| |
| |
| /* Perform insertion of partially redundant values. |
| For BLOCK, do the following: |
| 1. Propagate the NEW_SETS of the dominator into the current block. |
| If the block has multiple predecessors, |
| 2a. Iterate over the ANTIC expressions for the block to see if |
| any of them are partially redundant. |
| 2b. If so, insert them into the necessary predecessors to make |
| the expression fully redundant. |
| 2c. Insert a new PHI merging the values of the predecessors. |
| 2d. Insert the new PHI, and the new expressions, into the |
| NEW_SETS set. |
| 3. Recursively call ourselves on the dominator children of BLOCK. |
| |
| Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by |
| do_regular_insertion and do_partial_insertion. |
| |
| */ |
| |
| static bool |
| do_regular_insertion (basic_block block, basic_block dom) |
| { |
| bool new_stuff = false; |
| VEC (pre_expr, heap) *exprs; |
| pre_expr expr; |
| VEC (pre_expr, heap) *avail = NULL; |
| int i; |
| |
| exprs = sorted_array_from_bitmap_set (ANTIC_IN (block)); |
| VEC_safe_grow (pre_expr, heap, avail, EDGE_COUNT (block->preds)); |
| |
| FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) |
| { |
| if (expr->kind != NAME) |
| { |
| unsigned int val; |
| bool by_some = false; |
| bool cant_insert = false; |
| bool all_same = true; |
| pre_expr first_s = NULL; |
| edge pred; |
| 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)) |
| continue; |
| if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "Found fully redundant value\n"); |
| continue; |
| } |
| |
| FOR_EACH_EDGE (pred, ei, block->preds) |
| { |
| unsigned int vprime; |
| |
| /* 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); |
| |
| /* eprime will generally only be NULL if the |
| value of the expression, translated |
| through the PHI for this predecessor, is |
| undefined. If that is the case, we can't |
| make the expression fully redundant, |
| because its value is undefined along a |
| predecessor path. We can thus break out |
| early because it doesn't matter what the |
| rest of the results are. */ |
| if (eprime == NULL) |
| { |
| VEC_replace (pre_expr, avail, pred->dest_idx, NULL); |
| cant_insert = true; |
| break; |
| } |
| |
| eprime = fully_constant_expression (eprime); |
| vprime = get_expr_value_id (eprime); |
| edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), |
| vprime); |
| if (edoubleprime == NULL) |
| { |
| VEC_replace (pre_expr, avail, pred->dest_idx, eprime); |
| all_same = false; |
| } |
| else |
| { |
| VEC_replace (pre_expr, avail, pred->dest_idx, 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_d::equal (first_s, edoubleprime)) |
| all_same = false; |
| } |
| } |
| /* If we can insert it, it's not the same value |
| already existing along every predecessor, and |
| it's defined by some predecessor, it is |
| partially redundant. */ |
| if (!cant_insert && !all_same && by_some) |
| { |
| if (!do_insertion) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Skipping partial redundancy for " |
| "expression "); |
| print_pre_expr (dump_file, expr); |
| fprintf (dump_file, " (%04d), no redundancy on to be " |
| "optimized for speed edge\n", val); |
| } |
| } |
| else if (dbg_cnt (treepre_insert)) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Found partial redundancy for " |
| "expression "); |
| print_pre_expr (dump_file, expr); |
| fprintf (dump_file, " (%04d)\n", |
| get_expr_value_id (expr)); |
| } |
| if (insert_into_preds_of_block (block, |
| get_expression_id (expr), |
| avail)) |
| new_stuff = true; |
| } |
| } |
| /* If all edges produce the same value and that value is |
| an invariant, then the PHI has the same value on all |
| edges. Note this. */ |
| else if (!cant_insert && all_same && eprime |
| && (edoubleprime->kind == CONSTANT |
| || edoubleprime->kind == NAME) |
| && !value_id_constant_p (val)) |
| { |
| unsigned int j; |
| bitmap_iterator bi; |
| bitmap exprset = VEC_index (bitmap, value_expressions, val); |
| |
| unsigned int new_val = get_expr_value_id (edoubleprime); |
| EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bi) |
| { |
| pre_expr expr = expression_for_id (j); |
| |
| if (expr->kind == NAME) |
| { |
| 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. */ |
| 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; |
| } |
| } |
| } |
| } |
| } |
| |
| VEC_free (pre_expr, heap, exprs); |
| VEC_free (pre_expr, heap, avail); |
| return new_stuff; |
| } |
| |
| |
| /* Perform insertion for partially anticipatable expressions. There |
| is only one case we will perform insertion for these. This case is |
| if the expression is partially anticipatable, and fully available. |
| In this case, we know that putting it earlier will enable us to |
| remove the later computation. */ |
| |
| |
| static bool |
| do_partial_partial_insertion (basic_block block, basic_block dom) |
| { |
| bool new_stuff = false; |
| VEC (pre_expr, heap) *exprs; |
| pre_expr expr; |
| VEC (pre_expr, heap) *avail = NULL; |
| int i; |
| |
| exprs = sorted_array_from_bitmap_set (PA_IN (block)); |
| VEC_safe_grow (pre_expr, heap, avail, EDGE_COUNT (block->preds)); |
| |
| FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) |
| { |
| if (expr->kind != NAME) |
| { |
| unsigned int val; |
| bool by_all = true; |
| bool cant_insert = false; |
| edge pred; |
| basic_block bprime; |
| pre_expr eprime = NULL; |
| edge_iterator ei; |
| |
| val = get_expr_value_id (expr); |
| if (bitmap_set_contains_value (PHI_GEN (block), val)) |
| continue; |
| if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) |
| continue; |
| |
| FOR_EACH_EDGE (pred, ei, block->preds) |
| { |
| unsigned int vprime; |
| pre_expr edoubleprime; |
| |
| /* 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), |
| bprime, block); |
| |
| /* eprime will generally only be NULL if the |
| value of the expression, translated |
| through the PHI for this predecessor, is |
| undefined. If that is the case, we can't |
| make the expression fully redundant, |
| because its value is undefined along a |
| predecessor path. We can thus break out |
| early because it doesn't matter what the |
| rest of the results are. */ |
| if (eprime == NULL) |
| { |
| VEC_replace (pre_expr, avail, pred->dest_idx, NULL); |
| cant_insert = true; |
| break; |
| } |
| |
| eprime = fully_constant_expression (eprime); |
| vprime = get_expr_value_id (eprime); |
| edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime); |
| VEC_replace (pre_expr, avail, pred->dest_idx, edoubleprime); |
| if (edoubleprime == NULL) |
| { |
| by_all = false; |
| break; |
| } |
| } |
| |
| /* If we can insert it, it's not the same value |
| already existing along every predecessor, and |
| it's defined by some predecessor, it is |
| partially redundant. */ |
| if (!cant_insert && by_all) |
| { |
| edge succ; |
| bool do_insertion = false; |
| |
| /* Insert only if we can remove a later expression on a path |
| that we want to optimize for speed. |
| The phi node that we will be inserting in BLOCK is not free, |
| and inserting it for the sake of !optimize_for_speed successor |
| may cause regressions on the speed path. */ |
| FOR_EACH_EDGE (succ, ei, block->succs) |
| { |
| if (bitmap_set_contains_value (PA_IN (succ->dest), val)) |
| { |
| if (optimize_edge_for_speed_p (succ)) |
| do_insertion = true; |
| } |
| } |
| |
| if (!do_insertion) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Skipping partial partial redundancy " |
| "for expression "); |
| print_pre_expr (dump_file, expr); |
| fprintf (dump_file, " (%04d), not partially anticipated " |
| "on any to be optimized for speed edges\n", val); |
| } |
| } |
| else if (dbg_cnt (treepre_insert)) |
| { |
| pre_stats.pa_insert++; |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Found partial partial redundancy " |
| "for expression "); |
| print_pre_expr (dump_file, expr); |
| fprintf (dump_file, " (%04d)\n", |
| get_expr_value_id (expr)); |
| } |
| if (insert_into_preds_of_block (block, |
| get_expression_id (expr), |
| avail)) |
| new_stuff = true; |
| } |
| } |
| } |
| } |
| |
| VEC_free (pre_expr, heap, exprs); |
| VEC_free (pre_expr, heap, avail); |
| return new_stuff; |
| } |
| |
| static bool |
| insert_aux (basic_block block) |
| { |
| basic_block son; |
| bool new_stuff = false; |
| |
| if (block) |
| { |
| basic_block dom; |
| dom = get_immediate_dominator (CDI_DOMINATORS, block); |
| if (dom) |
| { |
| unsigned i; |
| bitmap_iterator bi; |
| bitmap_set_t newset = NEW_SETS (dom); |
| if (newset) |
| { |
| /* Note that we need to value_replace both NEW_SETS, and |
| AVAIL_OUT. For both the case of NEW_SETS, the value may be |
| represented by some non-simple expression here that we want |
| to replace it with. */ |
| FOR_EACH_EXPR_ID_IN_SET (newset, i, bi) |
| { |
| pre_expr expr = expression_for_id (i); |
| bitmap_value_replace_in_set (NEW_SETS (block), expr); |
| bitmap_value_replace_in_set (AVAIL_OUT (block), expr); |
| } |
| } |
| if (!single_pred_p (block)) |
| { |
| new_stuff |= do_regular_insertion (block, dom); |
| if (do_partial_partial) |
| new_stuff |= do_partial_partial_insertion (block, dom); |
| } |
| } |
| } |
| for (son = first_dom_son (CDI_DOMINATORS, block); |
| son; |
| son = next_dom_son (CDI_DOMINATORS, son)) |
| { |
| new_stuff |= insert_aux (son); |
| } |
| |
| return new_stuff; |
| } |
| |
| /* Perform insertion of partially redundant values. */ |
| |
| static void |
| insert (void) |
| { |
| bool new_stuff = true; |
| basic_block bb; |
| int num_iterations = 0; |
| |
| FOR_ALL_BB (bb) |
| NEW_SETS (bb) = bitmap_set_new (); |
| |
| while (new_stuff) |
| { |
| num_iterations++; |
| if (dump_file && dump_flags & TDF_DETAILS) |
| fprintf (dump_file, "Starting insert iteration %d\n", num_iterations); |
| new_stuff = insert_aux (ENTRY_BLOCK_PTR); |
| } |
| statistics_histogram_event (cfun, "insert iterations", num_iterations); |
| } |
| |
| |
| /* Add OP to EXP_GEN (block), and possibly to the maximal set. */ |
| |
| static void |
| add_to_exp_gen (basic_block block, tree op) |
| { |
| pre_expr result; |
| |
| if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op)) |
| return; |
| |
| result = get_or_alloc_expr_for_name (op); |
| bitmap_value_insert_into_set (EXP_GEN (block), result); |
| } |
| |
| /* Create value ids for PHI in BLOCK. */ |
| |
| static void |
| make_values_for_phi (gimple phi, basic_block block) |
| { |
| tree result = gimple_phi_result (phi); |
| unsigned i; |
| |
| /* We have no need for virtual phis, as they don't represent |
| actual computations. */ |
| if (virtual_operand_p (result)) |
| return; |
| |
| pre_expr e = get_or_alloc_expr_for_name (result); |
| add_to_value (get_expr_value_id (e), e); |
| bitmap_value_insert_into_set (AVAIL_OUT (block), e); |
| bitmap_insert_into_set (PHI_GEN (block), e); |
| 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); |
| } |
| } |
| } |
| |
| /* Compute the AVAIL set for all basic blocks. |
| |
| This function performs value numbering of the statements in each basic |
| block. The AVAIL sets are built from information we glean while doing |
| this value numbering, since the AVAIL sets contain only one entry per |
| value. |
| |
| AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)]. |
| AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */ |
| |
| static void |
| compute_avail (void) |
| { |
| |
| basic_block block, son; |
| basic_block *worklist; |
| size_t sp = 0; |
| unsigned i; |
| |
| /* 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) |
| { |
| tree name = ssa_name (i); |
| pre_expr e; |
| if (!name |
| || !SSA_NAME_IS_DEFAULT_DEF (name) |
| || has_zero_uses (name) |
| || virtual_operand_p (name)) |
| continue; |
| |
| e = get_or_alloc_expr_for_name (name); |
| add_to_value (get_expr_value_id (e), e); |
| bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e); |
| bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e); |
| } |
| |
| /* Allocate the worklist. */ |
| worklist = XNEWVEC (basic_block, n_basic_blocks); |
| |
| /* Seed the algorithm by putting the dominator children of the entry |
| block on the worklist. */ |
| for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR); |
| son; |
| son = next_dom_son (CDI_DOMINATORS, son)) |
| worklist[sp++] = son; |
| |
| /* Loop until the worklist is empty. */ |
| while (sp) |
| { |
| gimple_stmt_iterator gsi; |
| gimple stmt; |
| basic_block dom; |
| |
| /* Pick a block from the worklist. */ |
| block = worklist[--sp]; |
| |
| /* Initially, the set of available values in BLOCK is that of |
| its immediate dominator. */ |
| dom = get_immediate_dominator (CDI_DOMINATORS, block); |
| if (dom) |
| bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom)); |
| |
| /* Generate values for PHI nodes. */ |
| for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi)) |
| make_values_for_phi (gsi_stmt (gsi), block); |
| |
| BB_MAY_NOTRETURN (block) = 0; |
| |
| /* Now compute value numbers and populate value sets with all |
| the expressions computed in BLOCK. */ |
| for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| ssa_op_iter iter; |
| tree op; |
| |
| stmt = gsi_stmt (gsi); |
| |
| /* 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); |
| bitmap_insert_into_set (TMP_GEN (block), e); |
| bitmap_value_insert_into_set (AVAIL_OUT (block), e); |
| } |
| |
| if (gimple_has_side_effects (stmt) |
| || stmt_could_throw_p (stmt) |
| || is_gimple_debug (stmt)) |
| continue; |
| |
| FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) |
| add_to_exp_gen (block, op); |
| |
| switch (gimple_code (stmt)) |
| { |
| case GIMPLE_RETURN: |
| continue; |
| |
| case GIMPLE_CALL: |
| { |
| vn_reference_t ref; |
| pre_expr result = NULL; |
| VEC(vn_reference_op_s, heap) *ops = NULL; |
| |
| /* We can value number only calls to real functions. */ |
| if (gimple_call_internal_p (stmt)) |
| continue; |
| |
| copy_reference_ops_from_call (stmt, &ops); |
| vn_reference_lookup_pieces (gimple_vuse (stmt), 0, |
| gimple_expr_type (stmt), |
| ops, &ref, VN_NOWALK); |
| VEC_free (vn_reference_op_s, heap, ops); |
| if (!ref) |
| continue; |
| |
| /* If the value of the call is not invalidated in |
| this block until it is computed, add the expression |
| to EXP_GEN. */ |
| if (!gimple_vuse (stmt) |
| || gimple_code |
| (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI |
| || gimple_bb (SSA_NAME_DEF_STMT |
| (gimple_vuse (stmt))) != block) |
| { |
| result = (pre_expr) pool_alloc (pre_expr_pool); |
| result->kind = REFERENCE; |
| result->id = 0; |
| PRE_EXPR_REFERENCE (result) = ref; |
| |
| get_or_alloc_expression_id (result); |
| add_to_value (get_expr_value_id (result), result); |
| bitmap_value_insert_into_set (EXP_GEN (block), result); |
| } |
| continue; |
| } |
| |
| case GIMPLE_ASSIGN: |
| { |
| pre_expr result = NULL; |
| switch (vn_get_stmt_kind (stmt)) |
| { |
| case VN_NARY: |
| { |
| enum tree_code code = gimple_assign_rhs_code (stmt); |
| vn_nary_op_t nary; |
| |
| /* COND_EXPR and VEC_COND_EXPR are awkward in |
| that they contain an embedded complex expression. |
| Don't even try to shove those through PRE. */ |
| if (code == COND_EXPR |
| || code == VEC_COND_EXPR) |
| continue; |
| |
| vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1, |
| code, |
| gimple_expr_type (stmt), |
| gimple_assign_rhs1_ptr (stmt), |
| &nary); |
| if (!nary) |
| continue; |
| |
| /* If the NARY traps and there was a preceding |
| point in the block that might not return avoid |
| adding the nary to EXP_GEN. */ |
| if (BB_MAY_NOTRETURN (block) |
| && vn_nary_may_trap (nary)) |
| continue; |
| |
| result = (pre_expr) pool_alloc (pre_expr_pool); |
| result->kind = NARY; |
| result->id = 0; |
| PRE_EXPR_NARY (result) = nary; |
| break; |
| } |
| |
| case VN_REFERENCE: |
| { |
| vn_reference_t ref; |
| vn_reference_lookup (gimple_assign_rhs1 (stmt), |
| gimple_vuse (stmt), |
| VN_WALK, &ref); |
| if (!ref) |
| continue; |
| |
| /* If the value of the reference is not invalidated in |
| this block until it is computed, add the expression |
| to EXP_GEN. */ |
| if (gimple_vuse (stmt)) |
| { |
| gimple def_stmt; |
| bool ok = true; |
| def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt)); |
| while (!gimple_nop_p (def_stmt) |
| && gimple_code (def_stmt) != GIMPLE_PHI |
| && gimple_bb (def_stmt) == block) |
| { |
| if (stmt_may_clobber_ref_p |
| (def_stmt, gimple_assign_rhs1 (stmt))) |
| { |
| ok = false; |
| break; |
| } |
| def_stmt |
| = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt)); |
| } |
| if (!ok) |
| continue; |
| } |
| |
| result = (pre_expr) pool_alloc (pre_expr_pool); |
| result->kind = REFERENCE; |
| result->id = 0; |
| PRE_EXPR_REFERENCE (result) = ref; |
| break; |
| } |
| |
| default: |
| continue; |
| } |
| |
| get_or_alloc_expression_id (result); |
| add_to_value (get_expr_value_id (result), result); |
| bitmap_value_insert_into_set (EXP_GEN (block), result); |
| continue; |
| } |
| default: |
| break; |
| } |
| } |
| |
| /* Put the dominator children of BLOCK on the worklist of blocks |
| to compute available sets for. */ |
| for (son = first_dom_son (CDI_DOMINATORS, block); |
| son; |
| son = next_dom_son (CDI_DOMINATORS, son)) |
| worklist[sp++] = son; |
| } |
| |
| free (worklist); |
| } |
| |
| |
| /* Local state for the eliminate domwalk. */ |
| static VEC (gimple, heap) *el_to_remove; |
| static VEC (gimple, heap) *el_to_update; |
| static unsigned int el_todo; |
| static VEC (tree, heap) *el_avail; |
| static VEC (tree, heap) *el_avail_stack; |
| |
| /* Return a leader for OP that is available at the current point of the |
| eliminate domwalk. */ |
| |
| static tree |
| eliminate_avail (tree op) |
| { |
| tree valnum = VN_INFO (op)->valnum; |
| if (TREE_CODE (valnum) == SSA_NAME) |
| { |
| if (SSA_NAME_IS_DEFAULT_DEF (valnum)) |
| return valnum; |
| if (VEC_length (tree, el_avail) > SSA_NAME_VERSION (valnum)) |
| return VEC_index (tree, el_avail, SSA_NAME_VERSION (valnum)); |
| } |
| else if (is_gimple_min_invariant (valnum)) |
| return valnum; |
| return NULL_TREE; |
| } |
| |
| /* At the current point of the eliminate domwalk make OP available. */ |
| |
| static void |
| eliminate_push_avail (tree op) |
| { |
| tree valnum = VN_INFO (op)->valnum; |
| if (TREE_CODE (valnum) == SSA_NAME) |
| { |
| if (VEC_length (tree, el_avail) <= SSA_NAME_VERSION (valnum)) |
| VEC_safe_grow_cleared (tree, heap, |
| el_avail, SSA_NAME_VERSION (valnum) + 1); |
| VEC_replace (tree, el_avail, SSA_NAME_VERSION (valnum), op); |
| VEC_safe_push (tree, heap, el_avail_stack, op); |
| } |
| } |
| |
| /* Insert the expression recorded by SCCVN for VAL at *GSI. Returns |
| the leader for the expression if insertion was successful. */ |
| |
| static tree |
| eliminate_insert (gimple_stmt_iterator *gsi, tree val) |
| { |
| tree expr = vn_get_expr_for (val); |
| if (!CONVERT_EXPR_P (expr) |
| && TREE_CODE (expr) != VIEW_CONVERT_EXPR) |
| return NULL_TREE; |
| |
| tree op = TREE_OPERAND (expr, 0); |
| tree leader = TREE_CODE (op) == SSA_NAME ? eliminate_avail (op) : op; |
| if (!leader) |
| return NULL_TREE; |
| |
| tree res = make_temp_ssa_name (TREE_TYPE (val), NULL, "pretmp"); |
| gimple tem = gimple_build_assign (res, |
| build1 (TREE_CODE (expr), |
| TREE_TYPE (expr), leader)); |
| gsi_insert_before (gsi, tem, GSI_SAME_STMT); |
| VN_INFO_GET (res)->valnum = val; |
| |
| if (TREE_CODE (leader) == SSA_NAME) |
| gimple_set_plf (SSA_NAME_DEF_STMT (leader), NECESSARY, true); |
| |
| pre_stats.insertions++; |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Inserted "); |
| print_gimple_stmt (dump_file, tem, 0, 0); |
| } |
| |
| return res; |
| } |
| |
| /* Perform elimination for the basic-block B during the domwalk. */ |
| |
| static void |
| eliminate_bb (dom_walk_data *, basic_block b) |
| { |
| gimple_stmt_iterator gsi; |
| gimple stmt; |
| |
| /* Mark new bb. */ |
| VEC_safe_push (tree, heap, el_avail_stack, NULL_TREE); |
| |
| for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);) |
| { |
| gimple stmt, phi = gsi_stmt (gsi); |
| tree sprime = NULL_TREE, res = PHI_RESULT (phi); |
| 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 |
| || virtual_operand_p (res)) |
| { |
| gsi_next (&gsi); |
| continue; |
| } |
| |
| sprime = eliminate_avail (res); |
| if (!sprime |
| || sprime == res) |
| { |
| eliminate_push_avail (res); |
| gsi_next (&gsi); |
| continue; |
| } |
| else if (is_gimple_min_invariant (sprime)) |
| { |
| if (!useless_type_conversion_p (TREE_TYPE (res), |
| TREE_TYPE (sprime))) |
| sprime = fold_convert (TREE_TYPE (res), sprime); |
| } |
| |
| 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 (inserted_exprs |
| && !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, el_to_remove, stmt); |
| /* If we inserted this PHI node ourself, it's not an elimination. */ |
| if (inserted_exprs |
| && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))) |
| pre_stats.phis--; |
| else |
| pre_stats.eliminations++; |
| } |
| |
| for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| tree lhs = NULL_TREE; |
| tree rhs = NULL_TREE; |
| |
| stmt = gsi_stmt (gsi); |
| |
| if (gimple_has_lhs (stmt)) |
| lhs = gimple_get_lhs (stmt); |
| |
| if (gimple_assign_single_p (stmt)) |
| rhs = gimple_assign_rhs1 (stmt); |
| |
| /* Lookup the RHS of the expression, see if we have an |
| available computation for it. If so, replace the RHS with |
| the available computation. |
| |
| See PR43491. |
| We don't replace global register variable when it is a the RHS of |
| a single assign. We do replace local register variable since gcc |
| does not guarantee local variable will be allocated in register. */ |
| if (gimple_has_lhs (stmt) |
| && TREE_CODE (lhs) == SSA_NAME |
| && !gimple_assign_ssa_name_copy_p (stmt) |
| && (!gimple_assign_single_p (stmt) |
| || (!is_gimple_min_invariant (rhs) |
| && (gimple_assign_rhs_code (stmt) != VAR_DECL |
| || !is_global_var (rhs) |
| || !DECL_HARD_REGISTER (rhs)))) |
| && !gimple_has_volatile_ops (stmt)) |
| { |
| tree sprime; |
| gimple orig_stmt = stmt; |
| |
| sprime = eliminate_avail (lhs); |
| if (!sprime) |
| { |
| /* If there is no existing usable leader but SCCVN thinks |
| it has an expression it wants to use as replacement, |
| insert that. */ |
| tree val = VN_INFO (lhs)->valnum; |
| if (val != VN_TOP |
| && TREE_CODE (val) == SSA_NAME |
| && VN_INFO (val)->needs_insertion |
| && (sprime = eliminate_insert (&gsi, val)) != NULL_TREE) |
| eliminate_push_avail (sprime); |
| } |
| else if (is_gimple_min_invariant (sprime)) |
| { |
| /* If there is no existing leader but SCCVN knows this |
| value is constant, use that constant. */ |
| 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)) |
| { |
| fprintf (dump_file, "Replaced "); |
| print_gimple_expr (dump_file, stmt, 0, 0); |
| fprintf (dump_file, " with "); |
| print_generic_expr (dump_file, sprime, 0); |
| fprintf (dump_file, " in "); |
| print_gimple_stmt (dump_file, stmt, 0, 0); |
| } |
| pre_stats.eliminations++; |
| propagate_tree_value_into_stmt (&gsi, sprime); |
| stmt = gsi_stmt (gsi); |
| update_stmt (stmt); |
| |
| /* If we removed EH side-effects from the statement, clean |
| its EH information. */ |
| if (maybe_clean_or_replace_eh_stmt (orig_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"); |
| } |
| continue; |
| } |
| |
| /* If there is no usable leader mark lhs as leader for its value. */ |
| if (!sprime) |
| eliminate_push_avail (lhs); |
| |
| if (sprime |
| && sprime != lhs |
| && (rhs == NULL_TREE |
| || TREE_CODE (rhs) != SSA_NAME |
| || may_propagate_copy (rhs, sprime))) |
| { |
| bool can_make_abnormal_goto |
| = is_gimple_call (stmt) |
| && stmt_can_make_abnormal_goto (stmt); |
| |
| gcc_assert (sprime != rhs); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Replaced "); |
| print_gimple_expr (dump_file, stmt, 0, 0); |
| fprintf (dump_file, " with "); |
| print_generic_expr (dump_file, sprime, 0); |
| fprintf (dump_file, " in "); |
| print_gimple_stmt (dump_file, stmt, 0, 0); |
| } |
| |
| if (TREE_CODE (sprime) == SSA_NAME) |
| gimple_set_plf (SSA_NAME_DEF_STMT (sprime), |
| NECESSARY, true); |
| /* We need to make sure the new and old types actually match, |
| which may require adding a simple cast, which fold_convert |
| will do for us. */ |
| if ((!rhs || TREE_CODE (rhs) != SSA_NAME) |
| && !useless_type_conversion_p (gimple_expr_type (stmt), |
| TREE_TYPE (sprime))) |
| sprime = fold_convert (gimple_expr_type (stmt), sprime); |
| |
| pre_stats.eliminations++; |
| propagate_tree_value_into_stmt (&gsi, sprime); |
| stmt = gsi_stmt (gsi); |
| update_stmt (stmt); |
| |
| /* If we removed EH side-effects from the statement, clean |
| its EH information. */ |
| if (maybe_clean_or_replace_eh_stmt (orig_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"); |
| } |
| |
| /* Likewise for AB side-effects. */ |
| if (can_make_abnormal_goto |
| && !stmt_can_make_abnormal_goto (stmt)) |
| { |
| bitmap_set_bit (need_ab_cleanup, |
| gimple_bb (stmt)->index); |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, " Removed AB side-effects.\n"); |
| } |
| } |
| } |
| /* 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) |
| && !gimple_has_volatile_ops (stmt) |
| && !is_gimple_reg (gimple_assign_lhs (stmt)) |
| && (TREE_CODE (rhs) == SSA_NAME |
| || is_gimple_min_invariant (rhs))) |
| { |
| tree val; |
| val = vn_reference_lookup (gimple_assign_lhs (stmt), |
| gimple_vuse (stmt), VN_WALK, 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, el_to_remove, stmt); |
| } |
| } |
| /* Visit COND_EXPRs and fold the comparison with the |
| available value-numbers. */ |
| else if (gimple_code (stmt) == GIMPLE_COND) |
| { |
| tree op0 = gimple_cond_lhs (stmt); |
| tree op1 = gimple_cond_rhs (stmt); |
| tree result; |
| |
| if (TREE_CODE (op0) == SSA_NAME) |
| op0 = VN_INFO (op0)->valnum; |
| if (TREE_CODE (op1) == SSA_NAME) |
| op1 = VN_INFO (op1)->valnum; |
| result = fold_binary (gimple_cond_code (stmt), boolean_type_node, |
| op0, op1); |
| if (result && TREE_CODE (result) == INTEGER_CST) |
| { |
| if (integer_zerop (result)) |
| gimple_cond_make_false (stmt); |
| else |
| gimple_cond_make_true (stmt); |
| update_stmt (stmt); |
| el_todo = TODO_cleanup_cfg; |
| } |
| } |
| /* Visit indirect calls and turn them into direct calls if |
| possible. */ |
| if (is_gimple_call (stmt)) |
| { |
| tree orig_fn = gimple_call_fn (stmt); |
| tree fn; |
| if (!orig_fn) |
| continue; |
| if (TREE_CODE (orig_fn) == SSA_NAME) |
| fn = VN_INFO (orig_fn)->valnum; |
| else if (TREE_CODE (orig_fn) == OBJ_TYPE_REF |
| && TREE_CODE (OBJ_TYPE_REF_EXPR (orig_fn)) == SSA_NAME) |
| fn = VN_INFO (OBJ_TYPE_REF_EXPR (orig_fn))->valnum; |
| else |
| continue; |
| if (gimple_call_addr_fndecl (fn) != NULL_TREE |
| && useless_type_conversion_p (TREE_TYPE (orig_fn), |
| TREE_TYPE (fn))) |
| { |
| bool can_make_abnormal_goto |
| = stmt_can_make_abnormal_goto (stmt); |
| bool was_noreturn = gimple_call_noreturn_p (stmt); |
| |
| 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); |
| VEC_safe_push (gimple, heap, el_to_update, stmt); |
| |
| /* When changing a call into a noreturn call, cfg cleanup |
| is needed to fix up the noreturn call. */ |
| if (!was_noreturn && gimple_call_noreturn_p (stmt)) |
| el_todo |= TODO_cleanup_cfg; |
| |
| /* If we removed EH side-effects from the statement, clean |
| its EH information. */ |
| 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"); |
| } |
| |
| /* Likewise for AB side-effects. */ |
| if (can_make_abnormal_goto |
| && !stmt_can_make_abnormal_goto (stmt)) |
| { |
| bitmap_set_bit (need_ab_cleanup, |
| gimple_bb (stmt)->index); |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, " Removed AB side-effects.\n"); |
| } |
| |
| /* Changing an indirect call to a direct call may |
| have exposed different semantics. This may |
| require an SSA update. */ |
| el_todo |= TODO_update_ssa_only_virtuals; |
| } |
| } |
| } |
| } |
| |
| /* Make no longer available leaders no longer available. */ |
| |
| static void |
| eliminate_leave_block (dom_walk_data *, basic_block) |
| { |
| tree entry; |
| while ((entry = VEC_pop (tree, el_avail_stack)) != NULL_TREE) |
| VEC_replace (tree, el_avail, |
| SSA_NAME_VERSION (VN_INFO (entry)->valnum), NULL_TREE); |
| } |
| |
| /* Eliminate fully redundant computations. */ |
| |
| static unsigned int |
| eliminate (void) |
| { |
| struct dom_walk_data walk_data; |
| gimple_stmt_iterator gsi; |
| gimple stmt; |
| unsigned i; |
| |
| need_eh_cleanup = BITMAP_ALLOC (NULL); |
| need_ab_cleanup = BITMAP_ALLOC (NULL); |
| |
| el_to_remove = NULL; |
| el_to_update = NULL; |
| el_todo = 0; |
| el_avail = NULL; |
| el_avail_stack = NULL; |
| |
| walk_data.dom_direction = CDI_DOMINATORS; |
| walk_data.initialize_block_local_data = NULL; |
| walk_data.before_dom_children = eliminate_bb; |
| walk_data.after_dom_children = eliminate_leave_block; |
| walk_data.global_data = NULL; |
| walk_data.block_local_data_size = 0; |
| init_walk_dominator_tree (&walk_data); |
| walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); |
| fini_walk_dominator_tree (&walk_data); |
| |
| VEC_free (tree, heap, el_avail); |
| VEC_free (tree, heap, el_avail_stack); |
| |
| /* We cannot remove stmts during BB walk, especially not release SSA |
| names there as this confuses the VN machinery. The stmts ending |
| up in el_to_remove are either stores or simple copies. */ |
| FOR_EACH_VEC_ELT (gimple, el_to_remove, i, stmt) |
| { |
| 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 (inserted_exprs |
| && 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)) |
| { |
| basic_block bb = gimple_bb (stmt); |
| gsi = gsi_for_stmt (stmt); |
| unlink_stmt_vdef (stmt); |
| if (gsi_remove (&gsi, true)) |
| bitmap_set_bit (need_eh_cleanup, bb->index); |
| if (inserted_exprs |
| && TREE_CODE (lhs) == SSA_NAME) |
| bitmap_clear_bit (inserted_exprs, SSA_NAME_VERSION (lhs)); |
| release_defs (stmt); |
| } |
| } |
| VEC_free (gimple, heap, el_to_remove); |
| |
| /* We cannot update call statements with virtual operands during |
| SSA walk. This might remove them which in turn makes our |
| VN lattice invalid. */ |
| FOR_EACH_VEC_ELT (gimple, el_to_update, i, stmt) |
| update_stmt (stmt); |
| VEC_free (gimple, heap, el_to_update); |
| |
| return el_todo; |
| } |
| |
| /* Perform CFG cleanups made necessary by elimination. */ |
| |
| static void |
| fini_eliminate (void) |
| { |
| bool do_eh_cleanup = !bitmap_empty_p (need_eh_cleanup); |
| bool do_ab_cleanup = !bitmap_empty_p (need_ab_cleanup); |
| |
| if (do_eh_cleanup) |
| gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
| |
| if (do_ab_cleanup) |
| gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup); |
| |
| BITMAP_FREE (need_eh_cleanup); |
| BITMAP_FREE (need_ab_cleanup); |
| |
| if (do_eh_cleanup || do_ab_cleanup) |
| cleanup_tree_cfg (); |
| } |
| |
| /* Borrow a bit of tree-ssa-dce.c for the moment. |
| XXX: In 4.1, we should be able to just run a DCE pass after PRE, though |
| this may be a bit faster, and we may want critical edges kept split. */ |
| |
| /* If OP's defining statement has not already been determined to be necessary, |
| mark that statement necessary. Return the stmt, if it is newly |
| necessary. */ |
| |
| static inline gimple |
| mark_operand_necessary (tree op) |
| { |
| gimple stmt; |
| |
| gcc_assert (op); |
| |
| if (TREE_CODE (op) != SSA_NAME) |
| return NULL; |
| |
| stmt = SSA_NAME_DEF_STMT (op); |
| gcc_assert (stmt); |
| |
| if (gimple_plf (stmt, NECESSARY) |
| || gimple_nop_p (stmt)) |
| return NULL; |
| |
| gimple_set_plf (stmt, NECESSARY, true); |
| return stmt; |
| } |
| |
| /* Because we don't follow exactly the standard PRE algorithm, and decide not |
| to insert PHI nodes sometimes, and because value numbering of casts isn't |
| perfect, we sometimes end up inserting dead code. This simple DCE-like |
| pass removes any insertions we made that weren't actually used. */ |
| |
| static void |
| remove_dead_inserted_code (void) |
| { |
| bitmap worklist; |
| unsigned i; |
| bitmap_iterator bi; |
| gimple t; |
| |
| 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)) |
| bitmap_set_bit (worklist, i); |
| } |
| while (!bitmap_empty_p (worklist)) |
| { |
| i = bitmap_first_set_bit (worklist); |
| bitmap_clear_bit (worklist, i); |
| t = SSA_NAME_DEF_STMT (ssa_name (i)); |
| |
| /* PHI nodes are somewhat special in that each PHI alternative has |
| data and control dependencies. All the statements feeding the |
| PHI node's arguments are always necessary. */ |
| if (gimple_code (t) == GIMPLE_PHI) |
| { |
| unsigned k; |
| |
| for (k = 0; k < gimple_phi_num_args (t); k++) |
| { |
| tree arg = PHI_ARG_DEF (t, k); |
| if (TREE_CODE (arg) == SSA_NAME) |
| { |
| gimple n = mark_operand_necessary (arg); |
| if (n) |
| bitmap_set_bit (worklist, SSA_NAME_VERSION (arg)); |
| } |
| } |
| } |
| else |
| { |
| /* Propagate through the operands. Examine all the USE, VUSE and |
| VDEF operands in this statement. Mark all the statements |
| which feed this statement's uses as necessary. */ |
| ssa_op_iter iter; |
| tree use; |
| |
| /* The operands of VDEF expressions are also needed as they |
| represent potential definitions that may reach this |
| statement (VDEF operands allow us to follow def-def |
| links). */ |
| |
| FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES) |
| { |
| gimple n = mark_operand_necessary (use); |
| if (n) |
| bitmap_set_bit (worklist, SSA_NAME_VERSION (use)); |
| } |
| } |
| } |
| |
| EXECUTE_IF_SET_IN_BITMAP (inserted_exprs, 0, i, bi) |
| { |
| t = SSA_NAME_DEF_STMT (ssa_name (i)); |
| if (!gimple_plf (t, NECESSARY)) |
| { |
| gimple_stmt_iterator gsi; |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Removing unnecessary insertion:"); |
| print_gimple_stmt (dump_file, t, 0, 0); |
| } |
| |
| gsi = gsi_for_stmt (t); |
| if (gimple_code (t) == GIMPLE_PHI) |
| remove_phi_node (&gsi, true); |
| else |
| { |
| gsi_remove (&gsi, true); |
| release_defs (t); |
| } |
| } |
| } |
| 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 source 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 SRC node has been visited for the first |
| time, check its predecessors. */ |
| stack[sp++] = ei_start (src->preds); |
| else |
| post_order[post_order_num++] = src->index; |
| } |
| else |
| { |
| if (ei_one_before_end_p (ei) && dest != EXIT_BLOCK_PTR) |
| post_order[post_order_num++] = dest->index; |
| |
| if (!ei_one_before_end_p (ei)) |
| ei_next (&stack[sp - 1]); |
| else |
| sp--; |
| } |
| } |
| |
| if (include_entry_exit) |
| post_order[post_order_num++] = ENTRY_BLOCK; |
| |
| free (stack); |
| sbitmap_free (visited); |
| return post_order_num; |
| } |
| |
| |
| /* Initialize data structures used by PRE. */ |
| |
| static void |
| init_pre (void) |
| { |
| basic_block bb; |
| |
| next_expression_id = 1; |
| expressions = NULL; |
| VEC_safe_push (pre_expr, heap, expressions, NULL); |
| value_expressions = VEC_alloc (bitmap, heap, get_max_value_id () + 1); |
| VEC_safe_grow_cleared (bitmap, heap, value_expressions, |
| get_max_value_id() + 1); |
| name_to_id = NULL; |
| |
| inserted_exprs = BITMAP_ALLOC (NULL); |
| |
| connect_infinite_loops_to_exit (); |
| memset (&pre_stats, 0, sizeof (pre_stats)); |
| |
| |
| postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS); |
| my_rev_post_order_compute (postorder, false); |
| |
| alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets)); |
| |
| calculate_dominance_info (CDI_POST_DOMINATORS); |
| calculate_dominance_info (CDI_DOMINATORS); |
| |
| bitmap_obstack_initialize (&grand_bitmap_obstack); |
| phi_translate_table.create (5110); |
| expression_to_id.create (num_ssa_names * 3); |
| bitmap_set_pool = create_alloc_pool ("Bitmap sets", |
| sizeof (struct bitmap_set), 30); |
| pre_expr_pool = create_alloc_pool ("pre_expr nodes", |
| sizeof (struct pre_expr_d), 30); |
| FOR_ALL_BB (bb) |
| { |
| EXP_GEN (bb) = bitmap_set_new (); |
| PHI_GEN (bb) = bitmap_set_new (); |
| TMP_GEN (bb) = bitmap_set_new (); |
| AVAIL_OUT (bb) = bitmap_set_new (); |
| } |
| } |
| |
| |
| /* Deallocate data structures used by PRE. */ |
| |
| static void |
| fini_pre () |
| { |
| free (postorder); |
| VEC_free (bitmap, heap, value_expressions); |
| BITMAP_FREE (inserted_exprs); |
| bitmap_obstack_release (&grand_bitmap_obstack); |
| free_alloc_pool (bitmap_set_pool); |
| free_alloc_pool (pre_expr_pool); |
| phi_translate_table.dispose (); |
| expression_to_id.dispose (); |
| VEC_free (unsigned, heap, name_to_id); |
| |
| free_aux_for_blocks (); |
| |
| free_dominance_info (CDI_POST_DOMINATORS); |
| } |
| |
| /* Gate and execute functions for PRE. */ |
| |
| static unsigned int |
| do_pre (void) |
| { |
| unsigned int todo = 0; |
| |
| do_partial_partial = |
| flag_tree_partial_pre && optimize_function_for_speed_p (cfun); |
| |
| /* This has to happen before SCCVN runs because |
| loop_optimizer_init may create new phis, etc. */ |
| loop_optimizer_init (LOOPS_NORMAL); |
| |
| if (!run_scc_vn (VN_WALK)) |
| { |
| loop_optimizer_finalize (); |
| return 0; |
| } |
| |
| init_pre (); |
| scev_initialize (); |
| |
| /* Collect and value number expressions computed in each basic block. */ |
| compute_avail (); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| basic_block bb; |
| FOR_ALL_BB (bb) |
| { |
| print_bitmap_set (dump_file, EXP_GEN (bb), |
| "exp_gen", 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 can get quite slow on an incredibly large number of basic |
| blocks due to some quadratic behavior. Until this behavior is |
| fixed, don't run it when he have an incredibly large number of |
| bb's. If we aren't going to run insert, there is no point in |
| computing ANTIC, either, even though it's plenty fast. */ |
| if (n_basic_blocks < 4000) |
| { |
| compute_antic (); |
| insert (); |
| } |
| |
| /* Make sure to remove fake edges before committing our inserts. |
| This makes sure we don't end up with extra critical edges that |
| we would need to split. */ |
| remove_fake_exit_edges (); |
| gsi_commit_edge_inserts (); |
| |
| /* Remove all the redundant expressions. */ |
| todo |= eliminate (); |
| |
| statistics_counter_event (cfun, "Insertions", pre_stats.insertions); |
| statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert); |
| statistics_counter_event (cfun, "New PHIs", pre_stats.phis); |
| statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations); |
| statistics_counter_event (cfun, "Constified", pre_stats.constified); |
| |
| clear_expression_ids (); |
| remove_dead_inserted_code (); |
| todo |= TODO_verify_flow; |
| |
| scev_finalize (); |
| fini_pre (); |
| fini_eliminate (); |
| loop_optimizer_finalize (); |
| |
| /* TODO: tail_merge_optimize may merge all predecessors of a block, in which |
| case we can merge the block with the remaining predecessor of the block. |
| It should either: |
| - call merge_blocks after each tail merge iteration |
| - call merge_blocks after all tail merge iterations |
| - mark TODO_cleanup_cfg when necessary |
| - share the cfg cleanup with fini_pre. */ |
| todo |= tail_merge_optimize (todo); |
| |
| free_scc_vn (); |
| |
| /* Tail merging invalidates the virtual SSA web, together with |
| cfg-cleanup opportunities exposed by PRE this will wreck the |
| SSA updating machinery. So make sure to run update-ssa |
| manually, before eventually scheduling cfg-cleanup as part of |
| the todo. */ |
| update_ssa (TODO_update_ssa_only_virtuals); |
| |
| return todo; |
| } |
| |
| static bool |
| gate_pre (void) |
| { |
| return flag_tree_pre != 0; |
| } |
| |
| struct gimple_opt_pass pass_pre = |
| { |
| { |
| GIMPLE_PASS, |
| "pre", /* name */ |
| gate_pre, /* gate */ |
| do_pre, /* execute */ |
| NULL, /* sub */ |
| NULL, /* next */ |
| 0, /* static_pass_number */ |
| TV_TREE_PRE, /* tv_id */ |
| PROP_no_crit_edges | PROP_cfg |
| | PROP_ssa, /* properties_required */ |
| 0, /* properties_provided */ |
| 0, /* properties_destroyed */ |
| TODO_rebuild_alias, /* todo_flags_start */ |
| TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ |
| } |
| }; |
| |
| |
| /* Gate and execute functions for FRE. */ |
| |
| static unsigned int |
| execute_fre (void) |
| { |
| unsigned int todo = 0; |
| |
| if (!run_scc_vn (VN_WALKREWRITE)) |
| return 0; |
| |
| memset (&pre_stats, 0, sizeof (pre_stats)); |
| |
| /* Remove all the redundant expressions. */ |
| todo |= eliminate (); |
| |
| fini_eliminate (); |
| |
| free_scc_vn (); |
| |
| statistics_counter_event (cfun, "Insertions", pre_stats.insertions); |
| statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations); |
| statistics_counter_event (cfun, "Constified", pre_stats.constified); |
| |
| return todo; |
| } |
| |
| static bool |
| gate_fre (void) |
| { |
| return flag_tree_fre != 0; |
| } |
| |
| struct gimple_opt_pass pass_fre = |
| { |
| { |
| GIMPLE_PASS, |
| "fre", /* name */ |
| gate_fre, /* gate */ |
| execute_fre, /* execute */ |
| NULL, /* sub */ |
| NULL, /* next */ |
| 0, /* static_pass_number */ |
| TV_TREE_FRE, /* tv_id */ |
| PROP_cfg | PROP_ssa, /* properties_required */ |
| 0, /* properties_provided */ |
| 0, /* properties_destroyed */ |
| 0, /* todo_flags_start */ |
| TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ |
| } |
| }; |