#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "tree.h"#include "gimple.h"#include "ssa.h"#include "gimple-pretty-print.h"#include "dumpfile.h"#include "gimple-iterator.h"#include "gimple-fold.h"#include "tree-eh.h"#include "gimplify.h"#include "tree-cfg.h"#include "tree-ssa.h"#include "tree-ssa-propagate.h"#include "domwalk.h"#include "cfgloop.h"#include "tree-cfgcleanup.h"#include "cfganal.h"#include "tree-ssa-dce.h"
Data Structures | |
| struct | prop_stats_d |
| class | substitute_and_fold_dom_walker |
Functions | |
| static void | add_ssa_edge (tree var) |
| static void | add_control_edge (edge e) |
| static void | ssa_prop_init (void) |
| static void | ssa_prop_fini (void) |
| bool | stmt_makes_single_store (gimple *stmt) |
| bool | may_propagate_copy (tree dest, tree orig, bool dest_not_abnormal_phi_edge_p) |
| bool | may_propagate_copy_into_stmt (gimple *dest, tree orig) |
| bool | may_propagate_copy_into_asm (tree dest) |
| void | replace_exp (use_operand_p op_p, tree val) |
| void | propagate_value (use_operand_p op_p, tree val) |
| void | propagate_tree_value (tree *op_p, tree val) |
| void | propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val) |
| unsigned | clean_up_loop_closed_phi (function *fun) |
Variables | |
| static bitmap | cfg_blocks |
| static int * | bb_to_cfg_order |
| static int * | cfg_order_to_bb |
| static bitmap | ssa_edge_worklist |
| static vec< gimple * > | uid_to_stmt |
| static int | curr_order |
| static struct prop_stats_d | prop_stats |
Function Documentation
◆ add_control_edge()
Add edge E to the control flow worklist.
References bb_to_cfg_order, bitmap_set_bit, cfg_blocks, cfun, dump_file, dump_flags, EXIT_BLOCK_PTR_FOR_FN, basic_block_def::flags, ggc_alloc(), basic_block_def::index, and TDF_DETAILS.
Referenced by ssa_propagation_engine::simulate_block(), ssa_propagation_engine::simulate_stmt(), and ssa_propagation_engine::ssa_propagate().
◆ add_ssa_edge()
We have just defined a new value for VAR. If IS_VARYING is true, add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add them to INTERESTING_SSA_EDGES.
References BB_VISITED, bitmap_set_bit, dump_file, dump_flags, EDGE_PRED, FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_bb(), gimple_uid(), PHI_ARG_INDEX_FROM_USE, print_gimple_stmt(), prop_simulate_again_p(), ssa_edge_worklist, TDF_DETAILS, TDF_SLIM, uid_to_stmt, and USE_STMT.
Referenced by ssa_propagation_engine::simulate_stmt().
◆ clean_up_loop_closed_phi()
Check exits of each loop in FUN, walk over loop closed PHIs in each exit basic block and propagate degenerate PHIs.
References calculate_dominance_info(), CDI_DOMINATORS, dump_file, dump_flags, FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, get_loop_exit_edges(), ggc_alloc(), gimple_phi_arg_def(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), LOOPS_HAVE_RECORDED_EXITS, loops_state_satisfies_p(), may_propagate_copy(), gphi_iterator::phi(), print_generic_expr(), remove_phi_node(), replace_uses_by(), SET_USE, single_pred_p(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, TDF_DETAILS, and virtual_operand_p().
Referenced by loop_optimizer_finalize().
◆ may_propagate_copy()
Return true if we may propagate ORIG into DEST, false otherwise. If DEST_NOT_ABNORMAL_PHI_EDGE_P is true then assume the propagation does not happen into a PHI argument which flows in from an abnormal edge which relaxes some constraints.
References ggc_alloc(), NULL_TREE, SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, SSA_NAME_VAR, TREE_CODE, TREE_TYPE, useless_type_conversion_p(), VAR_P, and virtual_operand_p().
Referenced by substitute_and_fold_dom_walker::before_dom_children(), eliminate_dom_walker::before_dom_children(), clean_up_loop_closed_phi(), copy_prop_visit_assignment(), cprop_into_successor_phis(), cprop_operand(), eliminate_dom_walker::eliminate_stmt(), fold_stmt_1(), gimple_merge_blocks(), may_propagate_copy_into_stmt(), process_bb(), substitute_and_fold_engine::propagate_into_phi_args(), propagate_value(), record_equivalences_from_phis(), substitute_and_fold_engine::replace_phi_args_in(), substitute_and_fold_engine::replace_uses_in(), and copy_prop::visit_phi().
◆ may_propagate_copy_into_asm()
Similarly, but we know that we're propagating into an ASM_EXPR.
Referenced by cprop_operand(), and substitute_and_fold_engine::replace_uses_in().
◆ may_propagate_copy_into_stmt()
Like may_propagate_copy, but use as the destination expression the principal expression (typically, the RHS) contained in statement DEST. This is more efficient when working with the gimple tuples representation.
References boolean_type_node, gcc_unreachable, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_call_lhs(), gimple_switch_index(), is_gimple_assign(), is_gimple_call(), may_propagate_copy(), NULL_TREE, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, TREE_CODE, TREE_TYPE, and useless_type_conversion_p().
Referenced by eliminate_redundant_computations().
◆ propagate_tree_value()
Propagate the value VAL (assumed to be a constant or another SSA_NAME) into the tree pointed to by OP_P. Use this version for const/copy propagation when SSA operands are not available. It will perform the additional checks to ensure validity of the const/copy propagation, but will not update any operand information. Be sure to mark the stmt as modified.
References TREE_CODE, and unshare_expr().
Referenced by propagate_tree_value_into_stmt().
◆ propagate_tree_value_into_stmt()
| void propagate_tree_value_into_stmt | ( | gimple_stmt_iterator * | gsi, |
| tree | val ) |
Like propagate_tree_value, but use as the operand to replace the principal expression (typically, the RHS) contained in the statement referenced by iterator GSI. Note that it is not always possible to update the statement in-place, so a new statement may be created to replace the original.
References build_zero_cst(), gcc_unreachable, ggc_alloc(), gimple_assign_rhs1(), gimple_assign_set_rhs_from_tree(), gimple_assign_single_p(), gimple_call_lhs(), gimple_cond_set_code(), gimple_cond_set_lhs(), gimple_cond_set_rhs(), gimple_switch_index_ptr(), gsi_stmt(), is_gimple_assign(), is_gimple_call(), NULL_TREE, propagate_tree_value(), replace_call_with_value(), and TREE_TYPE.
Referenced by eliminate_redundant_computations(), eliminate_dom_walker::eliminate_stmt(), and dom_opt_dom_walker::optimize_stmt().
◆ propagate_value()
| void propagate_value | ( | use_operand_p | op_p, |
| tree | val ) |
Propagate the value VAL (assumed to be a constant or another SSA_NAME) into the operand pointed to by OP_P. Use this version for const/copy propagation as it will perform additional checks to ensure validity of the const/copy propagation.
References gcc_assert, ggc_alloc(), gimple_phi_arg_edge(), may_propagate_copy(), PHI_ARG_INDEX_FROM_USE, replace_exp(), USE_FROM_PTR, and USE_STMT.
Referenced by eliminate_dom_walker::before_dom_children(), cprop_into_successor_phis(), cprop_operand(), eliminate_dom_walker::eliminate_stmt(), process_bb(), substitute_and_fold_engine::propagate_into_phi_args(), substitute_and_fold_engine::replace_phi_args_in(), and substitute_and_fold_engine::replace_uses_in().
◆ replace_exp()
| void replace_exp | ( | use_operand_p | op_p, |
| tree | val ) |
Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). Use this version when not const/copy propagating values. For example, PRE uses this version when building expressions as they would appear in specific blocks taking into account actions of PHI nodes. The statement in which an expression has been replaced should be folded using fold_stmt_inplace.
References CONSTANT_CLASS_P, SET_USE, TREE_CODE, and unshare_expr().
Referenced by propagate_value(), replace_uses_by(), and value_replacement().
◆ ssa_prop_fini()
Free allocated storage.
References bb_to_cfg_order, BITMAP_FREE, cfg_blocks, cfg_order_to_bb, free(), ssa_edge_worklist, and uid_to_stmt.
Referenced by ssa_propagation_engine::ssa_propagate().
◆ ssa_prop_init()
Initialize local data structures and work lists.
References BASIC_BLOCK_FOR_FN, bb_to_cfg_order, BITMAP_ALLOC, bitmap_tree_view(), cfg_blocks, cfg_order_to_bb, cfun, basic_block_def::flags, FOR_EACH_EDGE, ggc_alloc(), gimple_set_uid(), gimple_stmt_max_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, inc_gimple_stmt_max_uid(), last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, pre_and_rev_post_order_compute_fn(), set_gimple_stmt_max_uid(), si, ssa_edge_worklist, basic_block_def::succs, and uid_to_stmt.
Referenced by ssa_propagation_engine::ssa_propagate().
◆ stmt_makes_single_store()
Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref' is a non-volatile pointer dereference, a structure reference or a reference to a single _DECL. Ignore volatile memory references because they are not interesting for the optimizers.
References DECL_P, ggc_alloc(), gimple_get_lhs(), gimple_vdef(), REFERENCE_CLASS_P, and TREE_THIS_VOLATILE.
Referenced by compute_invariantness().
Variable Documentation
◆ bb_to_cfg_order
|
static |
Referenced by add_control_edge(), ssa_prop_fini(), ssa_prop_init(), and ssa_propagation_engine::ssa_propagate().
◆ cfg_blocks
|
static |
Generic SSA value propagation engine. Copyright (C) 2004-2024 Free Software Foundation, Inc. Contributed by Diego Novillo <dnovillo@redhat.com> 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/>.
This file implements a generic value propagation engine based on
the same propagation used by the SSA-CCP algorithm [1].
Propagation is performed by simulating the execution of every
statement that produces the value being propagated. Simulation
proceeds as follows:
1- Initially, all edges of the CFG are marked not executable and
the CFG worklist is seeded with all the statements in the entry
basic block (block 0).
2- Every statement S is simulated with a call to the call-back
function SSA_PROP_VISIT_STMT. This evaluation may produce 3
results:
SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
interest and does not affect any of the work lists.
The statement may be simulated again if any of its input
operands change in future iterations of the simulator.
SSA_PROP_VARYING: The value produced by S cannot be determined
at compile time. Further simulation of S is not required.
If S is a conditional jump, all the outgoing edges for the
block are considered executable and added to the work
list.
SSA_PROP_INTERESTING: S produces a value that can be computed
at compile time. Its result can be propagated into the
statements that feed from S. Furthermore, if S is a
conditional jump, only the edge known to be taken is added
to the work list. Edges that are known not to execute are
never simulated.
3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
return value from SSA_PROP_VISIT_PHI has the same semantics as
described in #2.
4- Three work lists are kept. Statements are only added to these
lists if they produce one of SSA_PROP_INTERESTING or
SSA_PROP_VARYING.
CFG_BLOCKS contains the list of blocks to be simulated.
Blocks are added to this list if their incoming edges are
found executable.
SSA_EDGE_WORKLIST contains the list of statements that we
need to revisit.
5- Simulation terminates when all three work lists are drained.
Before calling ssa_propagate, it is important to clear
prop_simulate_again_p for all the statements in the program that
should be simulated. This initialization allows an implementation
to specify which statements should never be simulated.
It is also important to compute def-use information before calling
ssa_propagate.
References:
[1] Constant propagation with conditional branches,
Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
[2] Building an Optimizing Compiler,
Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
[3] Advanced Compiler Design and Implementation,
Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 Worklists of control flow edge destinations. This contains the CFG order number of the blocks so we can iterate in CFG order by visiting in bit-order. We use two worklists to first make forward progress before iterating.
Referenced by add_control_edge(), ssa_prop_fini(), ssa_prop_init(), and ssa_propagation_engine::ssa_propagate().
◆ cfg_order_to_bb
|
static |
Referenced by ssa_prop_fini(), ssa_prop_init(), and ssa_propagation_engine::ssa_propagate().
◆ curr_order
|
static |
Current RPO index in the iteration.
Referenced by ssa_propagation_engine::ssa_propagate().
◆ prop_stats
|
static |
◆ ssa_edge_worklist
|
static |
Worklists of SSA edges which will need reexamination as their definition has changed. SSA edges are def-use edges in the SSA web. For each D-U edge, we store the target statement or PHI node UID in a bitmap. UIDs order stmts in execution order. We use two worklists to first make forward progress before iterating.
Referenced by add_ssa_edge(), ssa_propagation_engine::simulate_stmt(), ssa_prop_fini(), ssa_prop_init(), and ssa_propagation_engine::ssa_propagate().
◆ uid_to_stmt
Referenced by add_ssa_edge(), ssa_prop_fini(), ssa_prop_init(), and ssa_propagation_engine::ssa_propagate().
