GCC Middle and Back End API Reference
tree-ssa-dce.c File Reference

Data Structures

struct  stmt_stats


static void mark_stmt_necessary ()
static void mark_operand_necessary ()
static void mark_stmt_if_obviously_necessary ()
static void mark_last_stmt_necessary ()
static void mark_control_dependent_edges_necessary ()
static void find_obviously_necessary_stmts ()
static bool ref_may_be_aliased ()
static bool mark_aliased_reaching_defs_necessary_1 ()
static void mark_aliased_reaching_defs_necessary ()
static bool mark_all_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
static void mark_all_reaching_defs_necessary ()
static bool degenerate_phi_p ()
static void propagate_necessity ()
static bool remove_dead_phis ()
static edge forward_edge_to_pdom ()
static void remove_dead_stmt ()
static bool eliminate_unnecessary_stmts ()
static void print_stats ()
static void tree_dce_init ()
static void tree_dce_done ()
static unsigned int perform_tree_ssa_dce ()
static unsigned int tree_ssa_dce ()
static unsigned int tree_ssa_dce_loop ()
static unsigned int tree_ssa_cd_dce ()
static bool gate_dce ()
gimple_opt_passmake_pass_dce ()
gimple_opt_passmake_pass_dce_loop ()
gimple_opt_passmake_pass_cd_dce ()


static struct stmt_stats stats
static vec< gimpleworklist
static sbitmap processed
static sbitmap last_stmt_necessary
static sbitmap bb_contains_live_stmts
static control_dependencescd
static sbitmap visited_control_parents
static bool cfg_altered
static bitmap visited = NULL
static unsigned int longest_chain = 0
static unsigned int total_chain = 0
static unsigned int nr_walks = 0
static bool chain_ovfl = false

Function Documentation

static bool degenerate_phi_p ( )
   Return true for PHI nodes with one or identical arguments
   can be removed.  
static bool eliminate_unnecessary_stmts ( )
   Eliminate unnecessary statements. Any instruction not marked as necessary
   contributes nothing to the program, and can be deleted.  
     Walking basic blocks and statements in reverse order avoids
     releasing SSA names before any other DEFs that refer to them are
     released.  This helps avoid loss of debug information, as we get
     a chance to propagate all RHSs of removed SSAs into debug uses,
     rather than only the latest ones.  E.g., consider:

     x_3 = y_1 + z_2;
     a_5 = x_3 - b_4;
     # DEBUG a => a_5

     If we were to release x_3 before a_5, when we reached a_5 and
     tried to substitute it into the debug stmt, we'd see x_3 there,
     but x_3's DEF, type, etc would have already been disconnected.
     By going backwards, the debug stmt first changes to:

     # DEBUG a => x_3 - b_4

     and then to:

     # DEBUG a => y_1 + z_2 - b_4

     as desired.  
         Remove dead statements.  
             We can mark a call to free as not necessary if the
             defining statement of its argument is an allocation
             function and that is not necessary itself.  
             If GSI is not necessary then remove it.  
                 When LHS of var = call (); is dead, simplify it into
                 call (); saving one operand.  
                     Avoid doing so for allocation calls which we
                     did not mark as necessary, it will confuse the
                     special logic we apply to malloc/free pair removal.  
     Since we don't track liveness of virtual PHI nodes, it is possible that we
     rendered some PHI nodes unreachable while they are still in use.
     Mark them for renaming.  
         Delete all unreachable basic blocks in reverse dominator order.  
                     Speed up the removal of blocks that don't
                     dominate others.  Walking backwards, this should
                     be the common case.  ??? Do we need to recompute
                     dominators because of cfg_altered?  
                             Rearrangements to the CFG may have failed
                             to update the dominators tree, so that
                             formerly-dominated blocks are now
                             otherwise reachable.  
         Remove dead PHI nodes.  
static void find_obviously_necessary_stmts ( )
   Find obviously necessary statements.  These are things like most function
   calls, and stores to file level variables.

   If EL is NULL, control statements are conservatively marked as
   necessary.  Otherwise it contains the list of edges used by control
   dependence analysis.  
         PHI nodes are never inherently necessary.  
         Check all statements in the block.  
     Pure and const functions are finite and thus have no infinite loops in
     Prevent the empty possibly infinite loops from being removed.  
static edge forward_edge_to_pdom ( )
   Forward edge E to respective POST_DOM_BB and update PHIs.  
     If edge was already around, no updating is necessary.  
         We are sure that for every live PHI we are seeing control dependent BB.
         This means that we can pick any edge to duplicate PHI args from.  
             PHIs for virtuals have no control dependency relation on them.
             We are lost here and must force renaming of the symbol.  
             Dead PHI do not imply control dependency.  
             The resulting PHI if not dead can only be degenerate.  

References dump_file, and print_gimple_stmt().

static bool gate_dce ( )

References execute(), and tree_ssa_cd_dce().

gimple_opt_pass* make_pass_cd_dce ( )
gimple_opt_pass* make_pass_dce ( )
gimple_opt_pass* make_pass_dce_loop ( )
static void mark_aliased_reaching_defs_necessary ( )
static bool mark_aliased_reaching_defs_necessary_1 ( )
   Worker for the walker that marks reaching definitions of REF,
   which is based on a non-aliased decl, necessary.  It returns
   true whenever the defining statement of the current VDEF is
   a kill for REF, as no dominating may-defs are necessary for REF
   anymore.  DATA points to the basic-block that contains the
   stmt that refers to REF.  
     All stmts we visit are necessary.  
     If the stmt lhs kills ref, then we can stop walking.  
         The assignment is not necessarily carried out if it can throw
         and we can catch it in the current function where we could inspect
         the previous value.
         ???  We only need to care about the RHS throwing.  For aggregate
         assignments or similar calls and non-call exceptions the LHS
         might throw as well.  
         We can get MEM[symbol: sZ, index: D.8862_1] here,
         so base == refd->base does not always hold.  
             For a must-alias check we need to be able to constrain
             the accesses properly.  
             Or they need to be exactly the same.  
                      Make sure there is no induction variable involved
                      in the references (gcc.c-torture/execute/pr42142.c).
                      The simplest way is to check if the kill dominates
                      the use.  
                      But when both are in the same block we cannot
                      easily tell whether we came from a backedge
                      unless we decide to compute stmt UIDs
                      (see PR58246).  
     Otherwise keep walking.  

References ao_ref_s::max_size, and ao_ref_s::offset.

static void mark_all_reaching_defs_necessary ( )

References dump_file, and print_gimple_stmt().

static bool mark_all_reaching_defs_necessary_1 ( ao_ref ref,
tree  vdef,
void *  data 
   Worker for the walker that marks reaching definitions of REF, which
   is not based on a non-aliased decl.  For simplicity we need to end
   up marking all may-defs necessary that are not based on a non-aliased
   decl.  The only job of this walker is to skip may-defs based on
   a non-aliased decl.  
     We have to skip already visited (and thus necessary) statements
     to make the chaining work after we dropped back to simple mode.  
     We want to skip stores to non-aliased variables.  
     We want to skip statments that do not constitute stores but have
     a virtual definition.  
static void mark_control_dependent_edges_necessary ( )
   Mark control dependent edges of BB as necessary.  We have to do this only
   once for each basic block so we set the appropriate bit after we're done.

   When IGNORE_SELF is true, ignore BB in the list of control dependences.  
static void mark_last_stmt_necessary ( )
   Mark the last statement of BB as necessary.  
     We actually mark the statement only if it is a control statement.  

References control_dependences::get_edge(), control_dependences::get_edges_dependent_on(), basic_block_def::index, and edge_def::src.

static void mark_operand_necessary ( )
   Mark the statement defining operand OP as necessary.  

Referenced by ref_may_be_aliased().

static void mark_stmt_if_obviously_necessary ( )
   Mark STMT as necessary if it obviously is.  Add it to the worklist if
   it can make other statements necessary.

   If AGGRESSIVE is false, control statements are conservatively marked as
     With non-call exceptions, we have to assume that all statements could
     throw.  If a statement could throw, it can be deemed necessary.  
     Statements that are implicitly live.  Most function calls, asm
     and return statements are required.  Labels and GIMPLE_BIND nodes
     are kept because they are control flow, and we have no way of
     knowing whether they can be removed.  DCE can eliminate all the
     other statements in a block, and CFG can then remove the block
     and labels.  
           Most, but not all function calls are required.  Function calls that
           produce no result and have no side effects (i.e. const pure
           functions) are unnecessary.  
         Debug temps without a value are not useful.  ??? If we could
         easily locate the debug temp bind stmt for a use thereof,
         would could refrain from marking all debug temps here, and
         mark them only if they're used.  
         Fall through.  
     If the statement has volatile operands, it needs to be preserved.
     Same for statements that can alter control flow in unpredictable

References BUILT_IN_NORMAL, gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_fndecl(), gimple_call_lhs(), gimple_debug_bind_get_var(), gimple_debug_bind_has_value_p(), gimple_debug_bind_p(), gimple_has_side_effects(), mark_stmt_necessary(), and simple_goto_p().

static void mark_stmt_necessary ( )
   If STMT is not already marked necessary, mark it, and add it to the
   worklist if ADD_TO_WORKLIST is true.  

Referenced by mark_stmt_if_obviously_necessary().

static unsigned int perform_tree_ssa_dce ( )
   Main routine to eliminate dead code.

   AGGRESSIVE controls the aggressiveness of the algorithm.
   In conservative mode, we ignore control dependence and simply declare
   all but the most trivially dead branches necessary.  This mode is fast.
   In aggressive mode, control dependences are taken into account, which
   results in more dead code elimination, but at the cost of some time.

   FIXME: Aggressive mode before PRE doesn't work currently because
          the dominance info is not invalidated after DCE1.  This is
          not an issue right now because we only run aggressive DCE
          as the last tree SSA pass, but keep this in mind when you
          start experimenting with pass ordering.  
     Preheaders are needed for SCEV to work.
     Simple lateches and recorded exits improve chances that loop will
     proved to be finite in testcases such as in loop-15.c and loop-24.c  
         Compute control dependence.  
     We do not update postdominators, so free them unconditionally.  
     If we removed paths in the CFG, then we need to update
     dominators as well.  I haven't investigated the possibility
     of incrementally updating dominators.  
     Debugging dumps.  
static void print_stats ( )
   Print out removed statement statistics.  
static void propagate_necessity ( )
   Propagate necessity using the operands of necessary statements.
   Process the uses on each statement in the worklist, and add all
   feeding statements which contribute to the calculation of this
   value to the worklist.

   In conservative mode, EL is NULL.  
         Take STMT from worklist.  
             Mark the last statement of the basic blocks on which the block
             containing STMT is control dependent, but only if we haven't
             already done so.  
             We do not process virtual PHI nodes nor do we track their
             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.  In aggressive mode,
             we also consider the control dependent edges leading to the
             predecessor block associated with each PHI alternative as
             For PHI operands it matters from where the control flow arrives
             to the BB.  Consider the following example:

             if (test)

             We need to mark control dependence of the empty basic blocks, since they
             contains computation of PHI operands.

             Doing so is too restrictive in the case the predecestor block is in
             the loop. Consider:

              if (b)
                  int i;
                  for (i = 0; i<1000; ++i)
                  j = 0;
              return j;

             There is PHI for J in the BB containing return statement.
             In this case the control dependence of predecestor block (that is
             within the empty loop) also contains the block determining number
             of iterations of the block that would prevent removing of empty
             loop in this case.

             This scenario can be avoided by splitting critical edges.
             To save the critical edge splitting pass we identify how the control
             dependence would look like if the edge was split.

             Consider the modified CFG created from current CFG by splitting
             edge B->C.  In the postdominance tree of modified CFG, C' is
             always child of C.  There are two cases how chlids of C' can look

                1) C' is leaf

                   In this case the only basic block C' is control dependent on is B.

                2) C' has single child that is B

                   In this case control dependence of C' is same as control
                   dependence of B in original CFG except for block B itself.
                   (since C' postdominate B in modified CFG)

             Now how to decide what case happens?  There are two basic options:

                a) C postdominate B.  Then C immediately postdominate B and
                   case 2 happens iff there is no other way from B to C except
                   the edge B->C.

                   There is other way from B to C iff there is succesor of B that
                   is not postdominated by B.  Testing this condition is somewhat
                   expensive, because we need to iterate all succesors of B.
                   We are safe to assume that this does not happen: we will mark B
                   as needed when processing the other path from B to C that is
                   conrol dependent on B and marking control dependencies of B
                   itself is harmless because they will be processed anyway after
                   processing control statement in B.

                b) C does not postdominate B.  Always case 1 happens since there is
                   path from C to exit that does not go through B and thus also C'.  
             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.  
             If this is a call to free which is directly fed by an
             allocation function do not mark that necessary through
             processing the argument.  
                 If the pointer we free is defined by an allocation
                 function do not add the call to the worklist.  
             If we dropped to simple mode make all immediately
             reachable definitions necessary.  
             For statements that may load from memory (have a VUSE) we
             have to mark all reaching (may-)definitions as necessary.
             We partition this task into two cases:
              1) explicit loads based on decls that are not aliased
              2) implicit loads (like calls) and explicit loads not
                 based on decls that are not aliased (like indirect
                 references or loads from globals)
             For 1) we mark all reaching may-defs as necessary, stopping
             at dominating kills.  For 2) we want to mark all dominating
             references necessary, but non-aliased ones which we handle
             in 1).  By keeping a global visited bitmap for references
             we walk for 2) we avoid quadratic behavior for those.  
                 Calls to functions that are merely acting as barriers
                 or that only store to memory do not make any previous
                 stores necessary.  
                 Calls implicitly load from memory, their arguments
                 in addition may explicitly perform memory loads.  
                 If this is a load mark things necessary.  
                 A return statement may perform a load.  
                 Inputs may perform loads.  
                 The beginning of a transaction is a memory barrier.  
                 ??? If we were really cool, we'd only be a barrier
                 for the memories touched within the transaction.  
             If we over-used our alias oracle budget drop to simple
             mode.  The cost metric allows quadratic behavior
             (number of uses times number of may-defs queries) up to
             a constant maximal number of queries and after that falls back to
             super-linear complexity.  
                 Linear in the number of may-defs.  
                 Linear in the number of uses.  
static bool ref_may_be_aliased ( )
   Return true if REF is based on an aliased base, otherwise false.  

References gimple_get_lhs(), gimple_has_lhs(), and mark_operand_necessary().

Referenced by mark_aliased_reaching_defs_necessary().

static bool remove_dead_phis ( )
   Remove dead PHI nodes from block BB.  
         We do not track necessity of virtual PHI nodes.  Instead do
         very simple dead PHI removal here.  
             Virtual PHI nodes with one or identical arguments
             can be removed.  
static void remove_dead_stmt ( )
   Remove dead statement pointed to by iterator I.  Receives the basic block BB
   containing I so that we don't have to look it up.  
     If we have determined that a conditional branch statement contributes
     nothing to the program, then we not only remove it, but we also change
     the flow graph so that the current block will simply fall-thru to its
     immediate post-dominator.  The blocks we are circumventing will be
     removed by cleanup_tree_cfg if this change in the flow graph makes them
         If edge is already there, try to use it.  This avoids need to update
         PHI nodes.  Also watch for cases where post dominator does not exists
         or is exit block.  These can happen for infinite loops as we create
         fake edges in the dominator tree.  
         The edge is no longer associated with a conditional, so it does
         not have TRUE/FALSE flags.  
         The lone outgoing edge from BB will be a fallthru edge.  
         Remove the remaining outgoing edges.  
     If this is a store into a variable that is being optimized away,
     add a debug bind stmt if possible.  

References gimple_assign_rhs1(), gsi_insert_after(), GSI_SAME_STMT, and unshare_expr().

static void tree_dce_done ( )
   Cleanup after this pass.  
static void tree_dce_init ( )
   Initialization for this pass.  Set up the used data structures.  
static unsigned int tree_ssa_cd_dce ( )

Referenced by gate_dce().

static unsigned int tree_ssa_dce ( )
   Pass entry points.  
static unsigned int tree_ssa_dce_loop ( )

Variable Documentation

sbitmap bb_contains_live_stmts
   Vector indicating that BB contains statements that are live.  
control_dependences* cd
   Before we can determine whether a control branch is dead, we need to
   compute which blocks are control dependent on which edges.

   We expect each block to be control dependent on very few edges so we
   use a bitmap for each block recording its edges.  An array holds the
   bitmap.  The Ith bit in the bitmap is set if that block is dependent
   on the Ith edge.  

Referenced by same_phi_alternatives_1().

bool cfg_altered
   TRUE if this pass alters the CFG (by removing control statements).
   FALSE otherwise.

   If this pass alters the CFG, then it will arrange for the dominators
   to be recomputed.  
bool chain_ovfl = false
sbitmap last_stmt_necessary
   Vector indicating that the last statement of a basic block has already
   been marked as necessary.  
unsigned int longest_chain = 0
unsigned int nr_walks = 0
sbitmap processed
   Vector indicating an SSA name has already been processed and marked
   as necessary.  

Referenced by restore_last_backtrack_point().

struct stmt_stats stats
unsigned int total_chain = 0
sbitmap visited_control_parents
   Vector indicating that a basic block has already had all the edges
   processed that it is control dependent on.  
vec<gimple> worklist