- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| union | pre_expr_union_d |
| struct | pre_expr_d |
| struct | bitmap_set |
| struct | bb_bitmap_sets |
| struct | expr_pred_trans_d |
Typedefs | |
| typedef union pre_expr_union_d | pre_expr_union |
| typedef pre_expr_d * | pre_expr |
| typedef struct bitmap_set * | bitmap_set_t |
| typedef struct bb_bitmap_sets * | bb_value_sets_t |
| typedef expr_pred_trans_d * | expr_pred_trans_t |
| typedef struct expr_pred_trans_d * | const_expr_pred_trans_t |
Enumerations | |
| enum | pre_expr_kind { NAME, NARY, REFERENCE, CONSTANT } |
Variables | |
| static unsigned int | next_expression_id |
| static vec< pre_expr > | expressions |
| static hash_table< pre_expr_d > | expression_to_id |
| static vec< unsigned > | name_to_id |
| static alloc_pool | pre_expr_pool |
| static vec< bitmap > | value_expressions |
| static int * | postorder |
| static int | postorder_num |
| struct { | |
| int eliminations | |
| int insertions | |
| int pa_insert | |
| int phis | |
| } | pre_stats |
| static bool | do_partial_partial |
| static alloc_pool | bitmap_set_pool |
| static bitmap_obstack | grand_bitmap_obstack |
| static bitmap | need_eh_cleanup |
| static bitmap | need_ab_cleanup |
| static hash_table < expr_pred_trans_d > | phi_translate_table |
| static sbitmap | has_abnormal_preds |
| static sbitmap | changed_blocks |
| static bitmap | inserted_exprs |
| static vec< gimple > | el_to_remove |
| static vec< gimple > | el_to_update |
| static unsigned int | el_todo |
| static vec< tree > | el_avail |
| static vec< tree > | el_avail_stack |
| typedef struct bb_bitmap_sets * bb_value_sets_t |
Sets that we need to keep track of.
| typedef struct bitmap_set * bitmap_set_t |
An unordered bitmap set. One bitmap tracks values, the other, expressions.
| typedef struct expr_pred_trans_d* const_expr_pred_trans_t |
| typedef expr_pred_trans_d * expr_pred_trans_t |
A three tuple {e, pred, v} used to cache phi translations in the
phi_translate_table.
| typedef pre_expr_d * pre_expr |
| typedef union pre_expr_union_d pre_expr_union |
| enum pre_expr_kind |
@verbatim SSA-PRE for trees.
Copyright (C) 2001-2013 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/.
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.
|
static |
Add expression E to the expression set of value id V.
References bitmap_set_bit(), get_expr_value_id(), get_or_alloc_expression_id(), and expr_pred_trans_d::v.
Referenced by compute_avail(), create_expression_by_pieces(), do_regular_insertion(), get_or_alloc_expr_for_constant(), get_representative_for(), insert_into_preds_of_block(), and phi_translate_1().
|
inlinestatic |
Allocate an expression id for EXPR.
References hash_table< Descriptor, Allocator >::find_slot(), pre_expr_d::id, pre_expr_d::kind, NAME, and next_expression_id.
Referenced by get_or_alloc_expr_for(), get_or_alloc_expr_for_constant(), get_or_alloc_expr_for_name(), and get_or_alloc_expression_id().
|
static |
|
static |
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.
References bitmap_set_contains_value(), CONSTANT, expression_for_id(), pre_expr_d::kind, and value_id_constant_p().
|
static |
Referenced by bitmap_value_replace_in_set(), compute_avail(), do_regular_insertion(), and insert_into_preds_of_block().
|
static |
Insert an expression EXPR into a bitmapped set.
References bitmap_insert_into_set_1(), and get_expr_value_id().
|
static |
References bitmap_set_bit(), get_or_alloc_expression_id(), and value_id_constant_p().
Referenced by bitmap_insert_into_set().
|
static |
Remove an expression EXPR from a bitmapped set.
References bitmap_clear_bit(), get_expr_value_id(), get_expression_id(), and value_id_constant_p().
Referenced by bitmap_set_subtract_values(), clean(), dependent_clean(), and prune_clobbered_mems().
|
static |
Perform bitmapped set operation DEST &= ORIG.
References bitmap_and_into(), bitmap_bit_p(), bitmap_clear(), bitmap_clear_bit(), bitmap_copy(), expression_for_id(), bitmap_set::expressions, get_expr_value_id(), and bitmap_set::values.
Referenced by compute_antic_aux().
|
inlinestatic |
References bitmap_bit_p(), and get_expression_id().
|
static |
|
static |
Return true if bitmapped set SET contains the value VALUE_ID.
References bitmap_bit_p(), bitmap_empty_p(), and value_id_constant_p().
|
static |
Referenced by compute_antic_aux(), compute_avail(), and phi_translate_set().
|
static |
Copy a bitmapped set ORIG, into bitmapped set DEST.
References bitmap_copy(), bitmap_set::expressions, and bitmap_set::values.
|
static |
Return true if two bitmap sets are equal.
References bitmap_equal_p(), and bitmap_set::values.
Referenced by compute_antic_aux(), and compute_partial_antic_aux().
|
static |
Free memory used up by SET.
References bitmap_clear().
Referenced by compute_antic_aux(), compute_partial_antic_aux(), and insert().
|
static |
Create a new bitmap set and return it.
References bitmap_set::expressions, pool_alloc(), and bitmap_set::values.
Referenced by bitmap_set_subtract(), compute_antic(), compute_antic_aux(), compute_partial_antic_aux(), init_pre(), and insert().
|
static |
Replace an instance of value LOOKFOR with expression EXPR in SET.
References bitmap_clear_bit(), bitmap_set_bit(), bitmap_set_contains_value(), get_expression_id(), and value_id_constant_p().
Referenced by bitmap_value_replace_in_set().
|
static |
Subtract all values and expressions contained in ORIG from DEST.
References bitmap_and_compl(), bitmap_set_bit(), bitmap_set_new(), expression_for_id(), bitmap_set::expressions, get_expr_value_id(), and bitmap_set::values.
Referenced by compute_antic_aux(), and compute_partial_antic_aux().
|
static |
Subtract all the values in bitmap set B from bitmap set A.
References bitmap_clear(), bitmap_copy(), bitmap_remove_from_set(), bitmap_set_contains_value(), expression_for_id(), bitmap_set::expressions, and get_expr_value_id().
Referenced by compute_partial_antic_aux().
|
static |
Referenced by compute_antic_aux(), compute_avail(), compute_partial_antic_aux(), and phi_translate_set().
|
static |
Insert EXPR into SET if EXPR's value is not already present in SET.
References bitmap_set_bit(), get_expr_value_id(), get_or_alloc_expression_id(), pre_expr_d::id, and value_id_constant_p().
|
static |
|
static |
Replace an instance of EXPR's VALUE with EXPR in SET if it exists, and add it otherwise.
References bitmap_insert_into_set(), bitmap_set_contains_value(), bitmap_set_replace_value(), and get_expr_value_id().
|
static |
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.
References bitmap_remove_from_set(), exprs, sorted_array_from_bitmap_set(), and valid_in_sets().
Referenced by compute_antic_aux().
|
static |
Free the expression id field in all of our expressions, and then destroy the expressions array.
Referenced by do_pre().
|
static |
Compute ANTIC and partial ANTIC sets.
References bitmap_bit_p(), bitmap_clear(), bitmap_ones(), bitmap_set_bit(), bitmap_set_new(), cfun, changed, compute_antic_aux(), compute_partial_antic_aux(), do_partial_partial, dump_file, dump_flags, edge_def::flags, basic_block_def::index, mark_dfs_back_edges(), postorder, postorder_num, basic_block_def::preds, sbitmap_alloc(), sbitmap_free(), and statistics_histogram_event().
Referenced by do_pre().
|
static |
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])
References bitmap_clear_bit(), bitmap_set_and(), bitmap_set_bit(), bitmap_set_copy(), bitmap_set_equal(), bitmap_set_free(), bitmap_set_new(), bitmap_set_subtract(), bitmap_value_insert_into_set(), changed, clean(), defer_or_phi_translate_block(), edge_def::dest, dump_file, dump_flags, expression_for_id(), first, gimple_seq_empty_p(), basic_block_def::index, phi_nodes(), phi_translate_set(), basic_block_def::preds, print_bitmap_set(), prune_clobbered_mems(), single_succ(), single_succ_p(), edge_def::src, basic_block_def::succs, and worklist.
Referenced by compute_antic().
|
static |
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].
References add_to_value(), bitmap_insert_into_set(), bitmap_set_copy(), bitmap_value_insert_into_set(), CDI_DOMINATORS, copy_reference_ops_from_call(), dom, dump_file, dump_flags, first_dom_son(), free(), get_expr_value_id(), get_immediate_dominator(), get_or_alloc_expr_for_name(), get_or_alloc_expression_id(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_call_flags(), gimple_call_internal_p(), gimple_expr_type(), gimple_has_side_effects(), gimple_nop_p(), gimple_phi_result(), gimple_vuse(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), has_zero_uses(), pre_expr_d::id, basic_block_def::index, is_gimple_call(), is_gimple_debug(), pre_expr_d::kind, NARY, next_dom_son(), pool_alloc(), print_bitmap_set(), REFERENCE, ssa_undefined_value_p(), stmt_could_throw_p(), stmt_ends_bb_p(), stmt_may_clobber_ref_p(), virtual_operand_p(), vn_get_stmt_kind(), VN_NARY, vn_nary_may_trap(), vn_nary_op_lookup_stmt(), VN_NOWALK, VN_REFERENCE, vn_reference_lookup(), vn_reference_lookup_pieces(), VN_WALK, vNULL, and worklist.
Referenced by do_pre().
|
static |
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])
References bitmap_clear_bit(), bitmap_count_bits(), bitmap_ior_into(), bitmap_set_bit(), bitmap_set_equal(), bitmap_set_free(), bitmap_set_new(), bitmap_set_subtract(), bitmap_set_subtract_values(), bitmap_value_insert_into_set(), changed, dependent_clean(), edge_def::dest, dump_file, dump_flags, expression_for_id(), edge_def::flags, gimple_seq_empty_p(), basic_block_def::index, phi_nodes(), phi_translate_set(), basic_block_def::preds, print_bitmap_set(), prune_clobbered_mems(), single_succ(), single_succ_edge(), single_succ_p(), edge_def::src, basic_block_def::succs, and worklist.
Referenced by compute_antic().
|
static |
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.
References create_component_ref_by_pieces_1().
Referenced by create_expression_by_pieces().
|
static |
The actual worker for create_component_ref_by_pieces.
References build_int_cst(), find_or_generate_expression(), free(), get_addr_base_and_unit_offset(), handled_component_p(), HOST_WIDE_INT, int_const_binop(), integer_zerop(), is_gimple_min_invariant(), offset, vn_reference_op_struct::op0, vn_reference_op_struct::op1, vn_reference_op_struct::op2, vn_reference_op_struct::opcode, vn_reference_s::operands, sc, tree_int_cst_equal(), and vn_reference_op_struct::type.
Referenced by create_component_ref_by_pieces().
|
static |
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). The function returns NULL_TREE in case a different antic expression has to be inserted first. 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).
References add_to_value(), bitmap_set_bit(), bitmap_value_replace_in_set(), build_constructor(), CONSTANT, create_component_ref_by_pieces(), dump_file, dump_flags, find_or_generate_expression(), fold_stmt_inplace(), force_gimple_operand(), get_expr_type(), get_expr_value_id(), get_next_value_id(), get_or_alloc_expr_for_name(), gimple_get_lhs(), gimple_seq_add_seq(), gimple_seq_add_stmt(), gimple_set_plf(), gsi_end_p(), gsi_next(), gsi_stmt(), basic_block_def::index, pre_expr_d::kind, vn_nary_op_s::length, make_temp_ssa_name(), NAME, NARY, vn_nary_op_s::op, pre_stats, print_gimple_stmt(), REFERENCE, sccvn_valnum_from_value_id(), vn_nary_op_s::type, unshare_expr(), update_stmt(), useless_type_conversion_p(), vn_ssa_aux::valnum, vn_ssa_aux::value_id, VN_INFO(), and VN_INFO_GET().
Referenced by find_or_generate_expression(), and insert_into_preds_of_block().
| void debug_bitmap_set | ( | bitmap_set_t | ) |
| DEBUG_FUNCTION void debug_bitmap_set | ( | ) |
References print_bitmap_set().
| void debug_bitmap_sets_for | ( | basic_block | ) |
| DEBUG_FUNCTION void debug_bitmap_sets_for | ( | ) |
References do_partial_partial, basic_block_def::index, and print_bitmap_set().
| void debug_pre_expr | ( | pre_expr | ) |
| DEBUG_FUNCTION void debug_pre_expr | ( | ) |
Like print_pre_expr but always prints to stderr.
References print_pre_expr().
| DEBUG_FUNCTION void debug_value_expressions | ( | ) |
References print_value_expressions().
|
static |
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.
References bitmap_set_bit(), basic_block_def::index, and phi_translate_set().
Referenced by compute_antic_aux().
|
static |
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.
References bitmap_remove_from_set(), exprs, sorted_array_from_bitmap_set(), and valid_in_sets().
Referenced by compute_partial_antic_aux().
|
static |
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.
References bitmap_find_leader(), bitmap_set_contains_value(), dbg_cnt(), edge_def::dest, edge_def::dest_idx, dump_file, dump_flags, exprs, edge_def::flags, fully_constant_expression(), get_expr_value_id(), get_expression_id(), insert_into_preds_of_block(), pre_expr_d::kind, NARY, optimize_edge_for_speed_p(), phi_translate(), pre_stats, basic_block_def::preds, print_pre_expr(), REFERENCE, sorted_array_from_bitmap_set(), edge_def::src, basic_block_def::succs, and vNULL.
Referenced by insert_aux().
|
static |
Gate and execute functions for PRE.
References cfun, clear_expression_ids(), compute_antic(), compute_avail(), do_partial_partial, eliminate(), fini_eliminate(), fini_pre(), free_scc_vn(), gsi_commit_edge_inserts(), init_pre(), insert(), loop_optimizer_finalize(), loop_optimizer_init(), optimize_function_for_speed_p(), pre_stats, remove_dead_inserted_code(), remove_fake_exit_edges(), run_scc_vn(), scev_finalize(), scev_initialize(), statistics_counter_event(), tail_merge_optimize(), update_ssa(), and VN_WALK.
|
static |
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.
References add_to_value(), bitmap_find_leader(), bitmap_insert_into_set(), bitmap_set_bit(), bitmap_set_contains_value(), bitmap_value_replace_in_set(), CONSTANT, dbg_cnt(), edge_def::dest_idx, dump_file, dump_flags, pre_expr_d::equal(), exprs, edge_def::flags, fully_constant_expression(), get_expr_type(), get_expr_value_id(), get_expression_id(), get_or_alloc_expr_for_name(), gimple_set_plf(), gsi_after_labels(), gsi_insert_before(), GSI_NEW_STMT, insert_into_preds_of_block(), pre_expr_d::kind, make_temp_ssa_name(), NAME, NARY, optimize_edge_for_speed_p(), phi_translate(), basic_block_def::preds, print_pre_expr(), REFERENCE, sccvn_valnum_from_value_id(), sorted_array_from_bitmap_set(), edge_def::src, vn_ssa_aux::valnum, vn_ssa_aux::value_id, VN_INFO(), VN_INFO_GET(), and vNULL.
Referenced by insert_aux().
|
static |
Eliminate fully redundant computations.
References dom_walk_data::after_dom_children, dom_walk_data::before_dom_children, bitmap_bit_p(), bitmap_clear_bit(), bitmap_set_bit(), dom_walk_data::block_local_data_size, CDI_DOMINATORS, el_todo, eliminate_bb(), eliminate_leave_block(), fini_walk_dominator_tree(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_bb(), gimple_set_plf(), dom_walk_data::global_data, gsi_for_stmt(), gsi_remove(), has_zero_uses(), basic_block_def::index, init_walk_dominator_tree(), dom_walk_data::initialize_block_local_data, may_propagate_copy(), release_defs(), single_imm_use(), unlink_stmt_vdef(), update_stmt(), and walk_dominator_tree().
Referenced by do_pre(), and execute_fre().
|
static |
Return a leader for OP that is available at the current point of the eliminate domwalk.
References is_gimple_min_invariant(), vn_ssa_aux::valnum, and VN_INFO().
Referenced by eliminate_bb(), and eliminate_insert().
|
static |
Perform elimination for the basic-block B during the domwalk.
References bitmap_bit_p(), bitmap_set_bit(), dump_file, dump_flags, el_todo, eliminate_avail(), eliminate_insert(), eliminate_push_avail(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_call_addr_fndecl(), gimple_call_fn(), gimple_call_noreturn_p(), gimple_call_set_fn(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_make_false(), gimple_cond_make_true(), gimple_cond_rhs(), gimple_expr_type(), gimple_get_lhs(), gimple_has_lhs(), gimple_has_volatile_ops(), gimple_phi_num_args(), gimple_plf(), gimple_set_plf(), gimple_vuse(), gsi_after_labels(), gsi_end_p(), gsi_insert_before(), GSI_NEW_STMT, gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), integer_zerop(), ipa_intraprocedural_devirtualization(), is_gimple_call(), is_gimple_min_invariant(), is_gimple_reg(), is_global_var(), may_propagate_copy(), maybe_clean_or_replace_eh_stmt(), operand_equal_p(), pre_stats, print_generic_expr(), print_gimple_expr(), print_gimple_stmt(), propagate_tree_value_into_stmt(), remove_phi_node(), stmt_can_make_abnormal_goto(), update_stmt(), useless_type_conversion_p(), vn_ssa_aux::valnum, virtual_operand_p(), VN_INFO(), vn_reference_lookup(), VN_TOP, and VN_WALK.
Referenced by eliminate().
|
static |
Insert the expression recorded by SCCVN for VAL at *GSI. Returns the leader for the expression if insertion was successful.
References dump_file, dump_flags, eliminate_avail(), gimple_set_plf(), gsi_insert_before(), GSI_SAME_STMT, make_temp_ssa_name(), pre_stats, print_gimple_stmt(), vn_ssa_aux::valnum, vn_get_expr_for(), and VN_INFO_GET().
Referenced by eliminate_bb().
|
static |
Make no longer available leaders no longer available.
References VN_INFO().
Referenced by eliminate().
|
static |
At the current point of the eliminate domwalk make OP available.
References vn_ssa_aux::valnum, and VN_INFO().
Referenced by eliminate_bb().
|
static |
Gate and execute functions for FRE.
References cfun, eliminate(), fini_eliminate(), free_scc_vn(), memset(), pre_stats, run_scc_vn(), statistics_counter_event(), and VN_WALKREWRITE.
|
inlinestatic |
Return the expression that has expression id ID
References pre_expr_d::id.
Referenced by bitmap_find_leader(), bitmap_set_and(), bitmap_set_subtract(), bitmap_set_subtract_values(), compute_antic_aux(), compute_partial_antic_aux(), find_or_generate_expression(), get_constant_for_value_id(), get_or_alloc_expr_for(), get_or_alloc_expr_for_constant(), get_or_alloc_expr_for_name(), get_representative_for(), insert_aux(), insert_into_preds_of_block(), print_bitmap_set(), prune_clobbered_mems(), sccvn_valnum_from_value_id(), and sorted_array_from_bitmap_set().
|
inlinestatic |
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.
References bitmap_find_leader().
Referenced by phi_translate_1().
|
static |
Referenced by create_component_ref_by_pieces_1(), and create_expression_by_pieces().
|
static |
Find a simple leader for an expression, or generate one using create_expression_by_pieces from a NARY expression for the value. BLOCK is the basic_block we are looking for leaders in. OP is the tree expression to find a leader for or generate. Returns the leader or NULL_TREE on failure.
References bitmap_find_leader(), CONSTANT, create_expression_by_pieces(), expression_for_id(), get_expr_type(), get_expr_value_id(), get_or_alloc_expr_for(), pre_expr_d::kind, NAME, and NARY.
|
static |
Perform CFG cleanups made necessary by elimination.
References bitmap_empty_p(), gimple_purge_all_dead_abnormal_call_edges(), and gimple_purge_all_dead_eh_edges().
Referenced by do_pre(), and execute_fre().
|
static |
Deallocate data structures used by PRE.
References bitmap_obstack_release(), CDI_POST_DOMINATORS, hash_table< Descriptor, Allocator >::dispose(), free(), free_alloc_pool(), free_aux_for_blocks(), free_dominance_info(), and postorder.
Referenced by do_pre().
|
static |
Return the folded version of T if T, when folded, is a gimple min_invariant. Otherwise, return T.
References CONSTANT, fully_constant_vn_reference_p(), get_constant_for_value_id(), get_expr_value_id(), get_or_alloc_expr_for(), get_or_alloc_expr_for_constant(), is_gimple_min_invariant(), pre_expr_d::kind, NARY, vn_nary_op_s::op, REFERENCE, tcc_binary, tcc_comparison, tcc_reference, tcc_unary, and vn_nary_op_s::type.
Referenced by do_partial_partial_insertion(), do_regular_insertion(), and phi_translate_1().
|
static |
|
static |
|
static |
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.
References CONSTANT, expression_for_id(), pre_expr_d::kind, and value_id_constant_p().
Referenced by fully_constant_expression().
|
static |
Get the tree type for our PRE expression e.
References CONSTANT, pre_expr_d::kind, NAME, NARY, and REFERENCE.
Referenced by create_expression_by_pieces(), do_regular_insertion(), find_or_generate_expression(), get_representative_for(), and insert_into_preds_of_block().
|
static |
Referenced by add_to_value(), bitmap_insert_into_set(), bitmap_remove_from_set(), bitmap_set_and(), bitmap_set_subtract(), bitmap_set_subtract_values(), bitmap_value_insert_into_set(), bitmap_value_replace_in_set(), compute_avail(), create_expression_by_pieces(), do_partial_partial_insertion(), do_regular_insertion(), find_or_generate_expression(), fully_constant_expression(), get_representative_for(), insert_into_preds_of_block(), phi_translate(), print_bitmap_set(), and valid_in_sets().
|
static |
Return the value id for a PRE expression EXPR.
References CONSTANT, get_constant_value_id(), pre_expr_d::kind, NAME, NARY, REFERENCE, vn_ssa_aux::value_id, and VN_INFO().
|
inlinestatic |
Return the expression id for tree EXPR.
References pre_expr_d::id.
Referenced by bitmap_remove_from_set(), bitmap_set_contains_expr(), bitmap_set_replace_value(), do_partial_partial_insertion(), do_regular_insertion(), phi_translate_1(), and value_dies_in_block_x().
|
static |
Get or allocate a pre_expr for a piece of GIMPLE, and return it. Currently only supports constants and SSA_NAMES.
References alloc_expression_id(), expression_for_id(), get_or_alloc_expr_for_constant(), get_or_alloc_expr_for_name(), is_gimple_min_invariant(), pre_expr_d::kind, lookup_expression_id(), NARY, pool_alloc(), pool_free(), and vn_nary_op_lookup().
Referenced by find_or_generate_expression(), and fully_constant_expression().
|
static |
Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to represent it.
References add_to_value(), alloc_expression_id(), CONSTANT, expression_for_id(), get_or_alloc_constant_value_id(), pre_expr_d::kind, lookup_expression_id(), and pool_alloc().
Referenced by fully_constant_expression(), get_or_alloc_expr_for(), insert_into_preds_of_block(), and phi_translate_1().
|
static |
Given an SSA_NAME NAME, get or create a pre_expr to represent it.
References alloc_expression_id(), expression_for_id(), pre_expr_d::id, pre_expr_d::kind, lookup_expression_id(), NAME, and pool_alloc().
Referenced by compute_avail(), create_expression_by_pieces(), do_regular_insertion(), get_or_alloc_expr_for(), get_representative_for(), insert_into_preds_of_block(), and phi_translate_1().
|
inlinestatic |
Return the existing expression id for EXPR, or create one if one does not exist yet.
References alloc_expression_id(), pre_expr_d::id, and lookup_expression_id().
Referenced by add_to_value(), bitmap_insert_into_set_1(), bitmap_value_insert_into_set(), compute_avail(), and phi_translate_1().
|
static |
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).
References add_to_value(), CONSTANT, dump_file, dump_flags, expression_for_id(), exprs, get_expr_type(), get_expr_value_id(), get_or_alloc_expr_for_name(), gimple_build_nop(), pre_expr_d::kind, make_temp_ssa_name(), NAME, NARY, vn_ssa_aux::needs_insertion, print_generic_expr(), print_pre_expr(), REFERENCE, vn_ssa_aux::valnum, vn_ssa_aux::value_id, VN_INFO(), and VN_INFO_GET().
Referenced by phi_translate_1().
|
static |
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.
References flow_bb_inside_loop_p(), gimple_bb(), basic_block_def::loop_father, vn_reference_op_struct::op0, vn_reference_op_struct::opcode, vn_reference_s::operands, and simple_iv().
Referenced by insert_into_preds_of_block().
|
static |
Initialize data structures used by PRE.
References alloc_aux_for_blocks(), bitmap_obstack_initialize(), bitmap_set_new(), calculate_dominance_info(), CDI_DOMINATORS, CDI_POST_DOMINATORS, connect_infinite_loops_to_exit(), hash_table< Descriptor, Allocator >::create(), create_alloc_pool(), get_max_value_id(), inverted_post_order_compute(), memset(), next_expression_id, postorder, postorder_num, and pre_stats.
Referenced by do_pre().
|
static |
Perform insertion of partially redundant values.
References bitmap_set_free(), bitmap_set_new(), cfun, dump_file, dump_flags, insert_aux(), and statistics_histogram_event().
Referenced by do_pre().
|
static |
|
static |
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.
References add_phi_arg(), add_to_value(), bb_loop_depth(), bitmap_insert_into_set(), bitmap_set_bit(), bitmap_value_replace_in_set(), CONSTANT, create_expression_by_pieces(), create_phi_node(), edge_def::dest_idx, dump_file, dump_flags, expression_for_id(), edge_def::flags, flow_bb_inside_loop_p(), force_gimple_operand(), get_expr_type(), get_expr_value_id(), get_or_alloc_expr_for_constant(), get_or_alloc_expr_for_name(), gimple_get_lhs(), gimple_set_plf(), gsi_end_p(), gsi_insert_seq_on_edge(), gsi_next(), gsi_stmt(), basic_block_def::index, inhibit_phi_insertion(), insertions, is_gimple_min_invariant(), pre_expr_d::kind, basic_block_def::loop_father, make_temp_ssa_name(), NAME, pre_stats, basic_block_def::preds, print_gimple_stmt(), REFERENCE, sccvn_valnum_from_value_id(), edge_def::src, unshare_expr(), useless_type_conversion_p(), vn_ssa_aux::valnum, vn_ssa_aux::value_id, VN_INFO(), and VN_INFO_GET().
Referenced by do_partial_partial_insertion(), and do_regular_insertion().
|
inlinestatic |
| gimple_opt_pass* make_pass_fre | ( | ) |
| gimple_opt_pass* make_pass_pre | ( | ) |
|
inlinestatic |
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.
References gimple_nop_p(), gimple_plf(), and gimple_set_plf().
Referenced by remove_dead_inserted_code().
|
static |
Determine if OP is valid in SET1 U SET2, which it is when the union contains its value-id.
References bitmap_set_contains_value(), vn_ssa_aux::value_id, and VN_INFO().
Referenced by valid_in_sets().
|
inlinestatic |
Add the tuple mapping from {expression E, basic block PRED} to
value V, to the phi translation table.
References expr_pred_trans_d::e, hash_table< Descriptor, Allocator >::find_slot_with_hash(), free(), pre_expr_d::hash(), expr_pred_trans_d::hashcode, basic_block_def::index, iterative_hash_hashval_t(), expr_pred_trans_d::pred, and expr_pred_trans_d::v.
Referenced by phi_translate().
|
inlinestatic |
Search in the phi translation table for the translation of expression E in basic block PRED. Return the translated value, if found, NULL otherwise.
References expr_pred_trans_d::e, hash_table< Descriptor, Allocator >::find_slot_with_hash(), pre_expr_d::hash(), expr_pred_trans_d::hashcode, basic_block_def::index, iterative_hash_hashval_t(), expr_pred_trans_d::pred, and expr_pred_trans_d::v.
Referenced by phi_translate().
|
static |
Wrapper around phi_translate_1 providing caching functionality.
References CONSTANT, get_expr_value_id(), pre_expr_d::kind, NAME, phi_trans_add(), phi_trans_lookup(), phi_translate_1(), and value_id_constant_p().
Referenced by do_partial_partial_insertion(), do_regular_insertion(), phi_translate_1(), and phi_translate_set().
|
static |
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.
References add_to_value(), changed, edge_def::dest_idx, find_edge(), find_leader_in_sets(), double_int::fits_shwi(), fully_constant_expression(), get_expression_id(), get_max_value_id(), get_next_value_id(), get_or_alloc_expr_for_constant(), get_or_alloc_expr_for_name(), get_or_alloc_expression_id(), get_representative_for(), pre_expr_d::id, is_gimple_min_invariant(), pre_expr_d::kind, vn_nary_op_s::length, double_int::low, memcpy(), NAME, NARY, vn_reference_op_struct::off, vn_nary_op_s::op, vn_reference_op_struct::op0, vn_reference_op_struct::op1, vn_reference_op_struct::op2, vn_reference_op_struct::opcode, vn_reference_s::operands, phi_translate(), pool_alloc(), REFERENCE, vn_reference_s::set, sizeof_vn_nary_op(), translate_vuse_through_block(), tree_to_double_int(), vn_nary_op_s::type, vn_reference_op_struct::type, vn_reference_s::type, type(), useless_type_conversion_p(), vn_nary_op_s::value_id, vn_reference_s::value_id, vn_ssa_aux::value_id, VN_INFO(), vn_nary_op_insert_pieces(), vn_nary_op_lookup_pieces(), vn_reference_fold_indirect(), vn_reference_insert_pieces(), vn_reference_lookup_pieces(), VN_WALK, vNULL, and vn_reference_s::vuse.
Referenced by phi_translate().
|
static |
For each expression in SET, translate the values through phi nodes in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting expressions in DEST.
References bitmap_set_copy(), bitmap_value_insert_into_set(), bitmap_value_replace_in_set(), exprs, gimple_seq_empty_p(), pre_expr_d::kind, NAME, phi_nodes(), phi_translate(), and sorted_array_from_bitmap_set().
Referenced by compute_antic_aux(), compute_partial_antic_aux(), and defer_or_phi_translate_block().
|
static |
Print out SET to OUTFILE.
References expression_for_id(), first, get_expr_value_id(), and print_pre_expr().
Referenced by compute_antic_aux(), compute_avail(), compute_partial_antic_aux(), debug_bitmap_set(), debug_bitmap_sets_for(), and print_value_expressions().
|
static |
Print out EXPR to outfile.
References CONSTANT, pre_expr_d::kind, vn_nary_op_s::length, NAME, NARY, vn_nary_op_s::op, vn_reference_op_struct::op0, vn_reference_op_struct::op1, vn_reference_op_struct::op2, vn_reference_op_struct::opcode, vn_reference_s::operands, print_generic_expr(), REFERENCE, tcc_declaration, tree_code_name, and vn_reference_s::vuse.
Referenced by debug_pre_expr(), do_partial_partial_insertion(), do_regular_insertion(), get_representative_for(), and print_bitmap_set().
|
static |
Print out the expressions that have VAL to OUTFILE.
References bitmap_set::expressions, and print_bitmap_set().
Referenced by debug_value_expressions().
|
static |
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.
References bitmap_remove_from_set(), CDI_DOMINATORS, dominated_by_p(), expression_for_id(), gimple_nop_p(), pre_expr_d::kind, NARY, REFERENCE, value_dies_in_block_x(), vn_nary_may_trap(), and vn_reference_s::vuse.
Referenced by compute_antic_aux(), and compute_partial_antic_aux().
|
static |
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.
References bitmap_clear_bit(), bitmap_empty_p(), bitmap_first_set_bit(), bitmap_set_bit(), dump_file, dump_flags, gimple_phi_num_args(), gimple_plf(), gsi_for_stmt(), gsi_remove(), mark_operand_necessary(), print_gimple_stmt(), release_defs(), remove_phi_node(), and worklist.
Referenced by do_pre().
|
static |
Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL.
References CONSTANT, expression_for_id(), pre_expr_d::kind, NAME, vn_ssa_aux::valnum, and VN_INFO().
Referenced by create_expression_by_pieces(), do_regular_insertion(), and insert_into_preds_of_block().
Generate an topological-ordered array of bitmap set SET.
References bitmap_bit_p(), bitmap_count_bits(), and expression_for_id().
Referenced by clean(), dependent_clean(), do_partial_partial_insertion(), do_regular_insertion(), and phi_translate_set().
|
static |
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.
References ao_ref_init_from_vn_reference(), edge_def::dest_idx, find_edge(), get_continuation_for_phi(), gimple_vuse(), stmt_may_clobber_ref_p_1(), and visited.
Referenced by phi_translate_1().
|
static |
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.
References bitmap_find_leader(), get_expr_value_id(), pre_expr_d::kind, vn_nary_op_s::length, NAME, NARY, vn_nary_op_s::op, vn_reference_op_struct::op0, vn_reference_op_struct::op1, vn_reference_op_struct::op2, op_valid_in_sets(), vn_reference_s::operands, and REFERENCE.
Referenced by clean(), and dependent_clean().
|
static |
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.
References ao_ref_init_from_vn_reference(), ao_ref_s::base, bitmap_bit_p(), bitmap_set_bit(), get_expression_id(), gimple_vdef(), gimple_vuse(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), vn_reference_s::operands, vn_reference_s::set, stmt_may_clobber_ref_p_1(), and vn_reference_s::type.
Referenced by prune_clobbered_mems().
|
static |
We can add and remove elements and entries to and from sets and hash tables, so we use alloc pools for them.
|
static |
List of blocks that may have changed during ANTIC computation and thus need to be iterated over.
|
static |
Referenced by compute_antic(), debug_bitmap_sets_for(), do_pre(), and insert_aux().
|
static |
Referenced by eliminate(), and eliminate_bb().
| int eliminations |
|
static |
|
static |
|
static |
|
static |
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.
| int insertions |
Referenced by insert_into_preds_of_block(), and prune_insertions_deletions().
|
static |
|
static |
Set of blocks with statements that have had their AB properties changed.
|
static |
Set of blocks with statements that have had their EH properties changed.
|
static |
Next global expression id number.
Referenced by alloc_expression_id(), and init_pre().
| int pa_insert |
|
static |
The phi_translate_table caches phi translations for a given expression and predecessor.
| int phis |
Referenced by bb_has_non_vop_phi(), delete_update_ssa(), expand_omp_for_generic(), gimple_duplicate_bb(), mark_phi_for_rewrite(), reinstall_phi_args(), rewrite_update_phi_arguments(), tree_ssa_phiopt_worker(), uncprop_into_successor_phis(), vect_create_epilog_for_reduction(), and vectorizable_reduction().
|
static |
Basic block list in postorder.
Referenced by compute_antic(), fast_dce(), fini_pre(), graphds_domtree(), graphds_scc(), init_pre(), and walk_dominator_tree().
|
static |
Referenced by compute_antic(), init_pre(), and walk_dominator_tree().
|
static |
| struct { ... } pre_stats |
This structure is used to keep track of statistics on what optimization PRE was able to perform.
Referenced by create_expression_by_pieces(), do_partial_partial_insertion(), do_pre(), eliminate_bb(), eliminate_insert(), execute_fre(), init_pre(), and insert_into_preds_of_block().
1.8.1.1