GCC Middle and Back End API Reference
tree-ssa-propagate.cc File Reference
#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"
Include dependency graph for tree-ssa-propagate.cc:

Data Structures

struct  prop_stats_d
class  substitute_and_fold_dom_walker


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)


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_ssa_edge()

static void add_ssa_edge ( tree var)
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

References BB_VISITED, bitmap_set_bit, dump_file, dump_flags, EDGE_PRED, basic_block_def::flags, FOR_EACH_IMM_USE_FAST, 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()

◆ may_propagate_copy()

◆ may_propagate_copy_into_asm()

bool may_propagate_copy_into_asm ( tree dest)
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()

bool may_propagate_copy_into_stmt ( gimple * dest,
tree orig )
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, dyn_cast(), gcc_unreachable, 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()

void propagate_tree_value ( tree * op_p,
tree val )
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(), dyn_cast(), gcc_unreachable, 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 as_a(), gcc_assert, gimple_phi_arg_edge(), is_a(), 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()

static void ssa_prop_fini ( void )

◆ ssa_prop_init()

◆ stmt_makes_single_store()

bool stmt_makes_single_store ( gimple * stmt)
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, gimple_get_lhs(), gimple_vdef(), REFERENCE_CLASS_P, and TREE_THIS_VOLATILE.

Referenced by compute_invariantness().

Variable Documentation

◆ bb_to_cfg_order

◆ cfg_blocks

bitmap cfg_blocks
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
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
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

        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

     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

        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


  [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

int* cfg_order_to_bb

◆ curr_order

int curr_order
Current RPO index in the iteration.   

Referenced by ssa_propagation_engine::ssa_propagate().

◆ prop_stats

◆ ssa_edge_worklist

bitmap ssa_edge_worklist
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