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

Data Structures

struct  count_ptr_d


void redirect_edge_var_map_add ()
void redirect_edge_var_map_clear ()
void redirect_edge_var_map_dup ()
edge_var_map_vectorredirect_edge_var_map_vector ()
static bool free_var_map_entry (const void *key, void **value, void *data)
void redirect_edge_var_map_destroy ()
edge ssa_redirect_edge ()
void flush_pending_stmts ()
static tree count_ptr_derefs ()
void count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p, unsigned *num_loads_p, unsigned *num_stores_p)
void gimple_replace_ssa_lhs ()
tree target_for_debug_bind ()
static tree find_released_ssa_name ()
void insert_debug_temp_for_var_def ()
void insert_debug_temps_for_defs ()
void reset_debug_uses ()
void release_defs_bitset ()
static bool verify_ssa_name ()
static bool verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, gimple stmt, bool is_virtual)
static bool verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p, gimple stmt, bool check_abnormal, bitmap names_defined_in_bb)
static bool verify_phi_args ()
DEBUG_FUNCTION void verify_ssa ()
static int uid_ssaname_map_eq ()
static unsigned int uid_ssaname_map_hash ()
void init_tree_ssa ()
static unsigned int execute_init_datastructures ()
static bool gate_init_datastructures ()
gimple_opt_passmake_pass_init_datastructures ()
void delete_tree_ssa ()
bool tree_ssa_useless_type_conversion ()
tree tree_ssa_strip_useless_type_conversions ()
bool ssa_undefined_value_p ()
static void maybe_rewrite_mem_ref_base ()
static tree non_rewritable_mem_ref_base ()
static bool non_rewritable_lvalue_p ()
static void maybe_optimize_var (tree var, bitmap addresses_taken, bitmap not_reg_needs, bitmap suitable_for_renaming)
void execute_update_addresses_taken ()
gimple_opt_passmake_pass_update_address_taken ()


static struct pointer_map_tedge_var_maps

Function Documentation

static tree count_ptr_derefs ( )
   Helper for count_uses_and_derefs.  Called by walk_tree to look for
   (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  
     Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
     pointer 'ptr' is *not* dereferenced, it is simply used to compute
     the address of 'fld' as 'ptr + offsetof(fld)'.  

References walk_stmt_info::is_lhs, count_ptr_d::num_loads, and count_ptr_d::num_stores.

Referenced by count_uses_and_derefs().

void count_uses_and_derefs ( tree  ptr,
gimple  stmt,
unsigned *  num_uses_p,
unsigned *  num_loads_p,
unsigned *  num_stores_p 
   Count the number of direct and indirect uses for pointer PTR in
   statement STMT.  The number of direct uses is stored in
   *NUM_USES_P.  Indirect references are counted separately depending
   on whether they are store or load operations.  The counts are
   stored in *NUM_STORES_P and *NUM_LOADS_P.  
     Find out the total number of uses of PTR in STMT.  
     Now count the number of indirect references to PTR.  This is
     truly awful, but we don't have much choice.  There are no parent
     pointers inside INDIRECT_REFs, so an expression like
     '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
     find all the indirect and direct uses of x_1 inside.  The only
     shortcut we can take is the fact that GIMPLE only allows
     INDIRECT_REFs inside the expressions below.  

References count, count_ptr_derefs(), walk_stmt_info::info, memset(), count_ptr_d::num_loads, count_ptr_d::num_stores, count_ptr_d::ptr, and walk_gimple_op().

void delete_tree_ssa ( void  )
   Deallocate memory associated with SSA data structures for FNDECL.  
     We no longer maintain the SSA operand cache at this point.  
     We no longer need the edge variable maps.  
static unsigned int execute_init_datastructures ( )
   Do the actions required to initialize internal data structures used
   in tree-ssa optimization passes.  
     Allocate hash tables, arrays and other structures.  

References cfun, gimple_df::default_defs, fini_ssa_operands(), fini_ssanames(), function::gimple_df, and ssa_operands_active().

void execute_update_addresses_taken ( void  )
   Compute TREE_ADDRESSABLE and DECL_GIMPLE_REG_P for local variables.  
     Collect into ADDRESSES_TAKEN all variables whose address is taken within
     the function body.  
             Note all addresses taken by the stmt.  
             If we have a call or an assignment, see if the lhs contains
             a local decl that requires not to be a gimple register.  
                                 We cannot move required conversions from
                                 the lhs to the rhs in asm statements, so
                                 require we do not need any.  
     We cannot iterate over all referenced vars because that can contain
     unused vars from BLOCK trees, which causes code generation differences
     for -g vs. -g0.  
     Operand caches need to be recomputed for operands referencing the updated
     variables and operands need to be rewritten to expose bare symbols.  
               Re-write TARGET_MEM_REFs of symbols we want to
               rewrite into SSA form.  
                   We shouldn't have any fancy wrapping of
                   component-refs on the LHS, but look through
                   VIEW_CONVERT_EXPRs as that is easy.  
                   Rewrite the RHS and make sure the resulting assignment
                   is validly typed.  
                   For var ={v} {CLOBBER}; where var lost
                   TREE_ADDRESSABLE just remove the stmt.  
         Update SSA form here, we are called as non-pass as well.  
static tree find_released_ssa_name ( )
   Called via walk_tree, look for SSA_NAMEs that have already been

References name_registered_for_update_p().

void flush_pending_stmts ( )
   Add PHI arguments queued in PENDING_STMT list on edge E to edge

References add_phi_arg(), gsi_stmt(), redirect_edge_var_map_def(), and redirect_edge_var_map_location().

static bool free_var_map_entry ( const void *  key,
void **  value,
void *  data 
   Used by redirect_edge_var_map_destroy to free all memory.  

References pointer_map_destroy(), and pointer_map_traverse().

static bool gate_init_datastructures ( )
   Gate for IPCP optimization.  
     Do nothing for funcions that was produced already in SSA form.  

Referenced by init_tree_ssa().

void gimple_replace_ssa_lhs ( )
   Replace the LHS of STMT, an assignment, either a GIMPLE_ASSIGN or a
   GIMPLE_CALL, with NLHS, in preparation for modifying the RHS to an
   expression with a different value.

   This will update any annotations (say debug bind stmts) referring
   to the original LHS, so that they use the RHS instead.  This is
   done even if NLHS and LHS are the same, for it is understood that
   the RHS will be modified afterwards, and NLHS will not be assigned
   an equivalent value.

   Adjusting any non-annotation uses of the LHS, if needed, is a
   responsibility of the caller.

   The effect of this call should be pretty much the same as that of
   inserting a copy of STMT before STMT, and then removing the
   original stmt, at which time gsi_remove() would have update
   annotations, but using this function saves all the inserting,
   copying and removing.  

References target_for_debug_bind().

void init_tree_ssa ( )
   Initialize global DFA and SSA structures.  

References gate_init_datastructures().

void insert_debug_temp_for_var_def ( )
   Insert a DEBUG BIND stmt before the DEF of VAR if VAR is referenced
   by other DEBUG stmts, and replace uses of the DEF with the
   newly-created debug temp.  
     If this name has already been registered for replacement, do nothing
     as anything that uses this name isn't in SSA form.  
     Check whether there are debug stmts that reference this variable and,
     if there are, decide whether we should use a debug temp.  
             Count this as an additional use, so as to make sure we
             use a temp unless VAR's definition has a SINGLE_RHS that
             can be shared.  
     If we didn't get an insertion point, and the stmt has already
     been removed, we won't be able to insert the debug bind stmt, so
     we'll have to drop debug information.  
         error_mark_node is what fixup_noreturn_call changes PHI arguments
             When removing blocks without following reverse dominance
             order, we may sometimes encounter SSA_NAMEs that have
             already been released, referenced in other SSA_DEFs that
             we're about to release.  Consider:

             <bb X>:
             v_1 = foo;

             <bb Y>:
             w_2 = v_1 + bar;
             # DEBUG w => w_2

             If we deleted BB X first, propagating the value of w_2
             won't do us any good.  It's too late to recover their
             original definition of v_1: when it was deleted, it was
             only referenced in other DEFs, it couldn't possibly know
             it should have been retained, and propagating every
             single DEF just in case it might have to be propagated
             into a DEBUG STMT would probably be too wasteful.

             When dominator information is not readily available, we
             check for and accept some loss of debug information.  But
             if it is available, there's no excuse for us to remove
             blocks in the wrong order, so we don't even check for
             dead SSA NAMEs.  SSA verification shall catch any
         If there's a single use of VAR, and VAR is the entire debug
         expression (usecount would have been incremented again
         otherwise), and the definition involves only constants and
         SSA names, then we can propagate VALUE into this single use,
         avoiding the temp.

         We can also avoid using a temp if VALUE can be shared and
         propagated into all uses, without generating expressions that
         wouldn't be valid gimple RHSs.

         Other cases that would require unsharing or non-gimple RHSs
         are deferred to a debug temp, although we could avoid temps
         at the expense of duplication of expressions.  
               unshare_expr is not needed here.  vexpr is either a
               SINGLE_RHS, that can be safely shared, some other RHS
               that was unshared when we found it had a single debug
               use, or a DEBUG_EXPR_DECL, that can be safely
             If we didn't replace uses with a debug decl fold the
             resulting expression.  Otherwise we end up with invalid IL.  

Referenced by release_ssa_name().

void insert_debug_temps_for_defs ( )
   Insert a DEBUG BIND stmt before STMT for each DEF referenced by
   other DEBUG stmts, and replace uses of the DEF with the
   newly-created debug temp.  

References gimple_debug_bind_p(), gimple_debug_bind_reset_value(), and update_stmt().

gimple_opt_pass* make_pass_init_datastructures ( )
gimple_opt_pass* make_pass_update_address_taken ( )
static void maybe_optimize_var ( tree  var,
bitmap  addresses_taken,
bitmap  not_reg_needs,
bitmap  suitable_for_renaming 
   When possible, clear TREE_ADDRESSABLE bit or set DECL_GIMPLE_REG_P bit and
   mark the variable VAR for conversion into SSA.  Return true when updating
   stmts is required.  
     Global Variables, result decls cannot be changed.  
         Do not change TREE_ADDRESSABLE if we need to preserve var as
         a non-register.  Otherwise we are confused and forget to
         add virtual operands for it.  

References bitmap_set_bit(), get_base_address(), gimple_get_lhs(), and non_rewritable_lvalue_p().

static void maybe_rewrite_mem_ref_base ( )
   If necessary, rewrite the base of the reference tree *TP from
   a MEM_REF to a plain or converted symbol.  
static bool non_rewritable_lvalue_p ( )
   For an lvalue tree LHS return true if it cannot be rewritten into SSA form.
   Otherwise return true.  
     A plain decl is always rewritable.  
     A decl that is wrapped inside a MEM-REF that covers
     it full is also rewritable.
     ???  The following could be relaxed allowing component
     references that do not change the access size.  

Referenced by maybe_optimize_var().

static tree non_rewritable_mem_ref_base ( )
   For a tree REF return its base if it is the base of a MEM_REF
   that cannot be rewritten into SSA form.  Otherwise return NULL_TREE.  
     A plain decl does not need it set.  
     But watch out for MEM_REFs we cannot lower to a

References bitmap_bit_p(), bitmap_set_bit(), dump_file, is_gimple_reg(), is_gimple_reg_type(), is_global_var(), and print_generic_expr().

void redirect_edge_var_map_add ( )
   Add a mapping with PHI RESULT and PHI DEF associated with edge E.  
void redirect_edge_var_map_clear ( )
   Clear the var mappings in edge E.  

Referenced by redirect_edge_var_map_destroy(), and remove_branch().

void redirect_edge_var_map_destroy ( void  )
   Clear the edge variable mappings.  

References edge_def::dest, gsi_end_p(), gsi_next(), gsi_start_phis(), and redirect_edge_var_map_clear().

void redirect_edge_var_map_dup ( )
   Duplicate the redirected var mappings in OLDE in NEWE.

   Since we can't remove a mapping, let's just duplicate it.  This assumes a
   pointer_map can have multiple edges mapping to the same var_map (many to
   one mapping), since we don't remove the previous mappings.  
edge_var_map_vector* redirect_edge_var_map_vector ( )
   Return the variable mappings for a given edge.  If there is none, return
     Hey, what kind of idiot would... you'd be surprised.  

Referenced by remove_forwarder_block_with_phi().

void release_defs_bitset ( )
   Delete SSA DEFs for SSA versions in the TOREMOVE bitmap, removing
   dominated stmts before their dominators, so that release_ssa_defs
   stands a chance of propagating DEFs into debug bind stmts.  
     Performing a topological sort is probably overkill, this will
     most likely run in slightly superlinear time, rather than the
     pathological quadratic worst case.  
               We can't propagate PHI nodes into debug stmts.  
               If we find another definition to remove that uses
               the one we're looking at, defer the removal of this
               one, so that it can be propagated into debug stmts
               after the other is.  
void reset_debug_uses ( )
   Reset all debug stmts that use SSA_NAME(s) defined in STMT.  

References bitmap_bit_p(), bitmap_empty_p(), and is_gimple_debug().

edge ssa_redirect_edge ( )
   Remove the corresponding arguments from the PHI nodes in E's
   destination block and redirect it to DEST.  Return redirected edge.
   The list of removed arguments is stored in a vector accessed
   through edge_var_maps.  
     Remove the appropriate PHI arguments in E's destination block.  
bool ssa_undefined_value_p ( )
   Return true if T, an SSA_NAME, has an undefined value.  
     Parameters get their initial value from the function entry.  
     When returning by reference the return address is actually a hidden
     Hard register variables get their initial value from the ether.  
     The value is undefined iff its definition statement is empty.  

Referenced by do_partial_partial_insertion().

tree target_for_debug_bind ( )
   Given a tree for an expression for which we might want to emit
   locations or values in debug information (generally a variable, but
   we might deal with other kinds of trees in the future), return the
   tree that should be used as the variable of a DEBUG_BIND STMT or
   VAR_LOCATION INSN or NOTE.  Return NULL if VAR is not to be tracked.  
     var-tracking only tracks registers.  

Referenced by debug_tree_ssa_stats(), find_def_blocks_for(), and gimple_replace_ssa_lhs().

tree tree_ssa_strip_useless_type_conversions ( )
   Strip conversions from EXP according to
   tree_ssa_useless_type_conversion and return the resulting

References integer_zerop().

bool tree_ssa_useless_type_conversion ( )
   Return true if EXPR is a useless type conversion, otherwise return
     If we have an assignment that merely uses a NOP_EXPR to change
     the top of the RHS to the type of the LHS and the type conversion
     is "safe", then strip away the type conversion so that we can
     enter LHS = RHS into the const_and_copies table.  
static int uid_ssaname_map_eq ( )
   Return true if the DECL_UID in both trees are equal.  

References GIMPLE_PASS, and TV_NONE.

static unsigned int uid_ssaname_map_hash ( )
   Hash a tree in a uid_decl_map.  
static bool verify_def ( basic_block  bb,
basic_block definition_block,
tree  ssa_name,
gimple  stmt,
bool  is_virtual 
   Return true if the definition of SSA_NAME at block BB is malformed.

   STMT is the statement where SSA_NAME is created.

   DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
      version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
      it means that the block in that array slot contains the
      definition of SSA_NAME.

   IS_VIRTUAL is true if SSA_NAME is created by a VDEF.  
static bool verify_phi_args ( )
   Return true if any of the arguments for PHI node PHI at block BB is

   DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
      version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
      it means that the block in that array slot contains the
      definition of SSA_NAME.  

References error(), and handled_component_p().

DEBUG_FUNCTION void verify_ssa ( )
   Verify common invariants in the SSA web.
   TODO: verify the variable annotations.  
     Keep track of SSA names present in the IL.  
     Now verify all the uses and make sure they agree with the definitions
     found in the previous pass.  
         Make sure that all edges have a clear 'aux' field.  
         Verify the arguments for every PHI node in the block.  
         Now verify all the uses and vuses in every statement of the block.  
     Restore the dominance information to its prior known state, so
     that we do not perturb the compiler's subsequent behavior.  

References edge_def::aux, edge_def::dest, error(), basic_block_def::index, and edge_def::src.

static bool verify_ssa_name ( )
   Return true if SSA_NAME is malformed and mark it visited.

   IS_VIRTUAL is true if this SSA_NAME was found inside a virtual

References error().

static bool verify_use ( basic_block  bb,
basic_block  def_bb,
use_operand_p  use_p,
gimple  stmt,
bool  check_abnormal,
bitmap  names_defined_in_bb 
   Return true if the use of SSA_NAME at statement STMT in block BB is

   DEF_BB is the block where SSA_NAME was found to be created.

   IDOM contains immediate dominator information for the flowgraph.

   CHECK_ABNORMAL is true if the caller wants to check whether this use
      is flowing through an abnormal edge (only used when checking PHI

   If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
     that are defined before STMT in basic block BB.  
     Make sure the use is in an appropriate list by checking the previous
     element to make sure it's the same.  

References error().

Variable Documentation

struct pointer_map_t* edge_var_maps

Miscellaneous SSA utility functions. Copyright (C) 2001-2013 Free Software Foundation, Inc.

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/.

   Pointer map of variable mappings, keyed by edge.