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

Data Structures

struct  tree_int_map_hasher


static void verify_live_on_entry (tree_live_info_p)
static void var_map_base_init ()
static void var_map_base_fini ()
var_map init_var_map ()
void delete_var_map ()
int var_union ()
static bitmap partition_view_init ()
static void partition_view_fini ()
void partition_view_normal ()
void partition_view_bitmap ()
static bool set_is_used ()
static bool is_used_p ()
static void mark_all_vars_used (tree *)
static tree mark_all_vars_used_1 ()
static void mark_scope_block_unused ()
static bool remove_unused_scope_block_p ()
static void mark_all_vars_used ()
static tree clear_unused_block_pointer_1 ()
static void clear_unused_block_pointer ()
static void dump_scope_block ()
DEBUG_FUNCTION void debug_scope_block ()
void dump_scope_blocks ()
DEBUG_FUNCTION void debug_scope_blocks ()
void remove_unused_locals ()
static tree_live_info_p new_tree_live_info ()
void delete_tree_live_info ()
static void loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, bitmap tmp)
static void live_worklist ()
static void set_var_live_on_entry ()
void calculate_live_on_exit ()
tree_live_info_p calculate_live_ranges ()
void dump_var_map ()
DEBUG_FUNCTION void debug ()
void dump_live_info ()
void register_ssa_partition_check ()
static void verify_live_on_entry ()


static bitmap usedvars
static bitmap_obstack liveness_bitmap_obstack

Function Documentation

void calculate_live_on_exit ( )
   Calculate the live on exit vectors based on the entry info in LIVEINFO.  
     live on entry calculations used liveout vectors for defs, clear them.  
     Set all the live-on-exit bits for uses in PHIs.  
         Mark the PHI arguments which are live on exit to the pred block.  
         Add each successors live on entry to this bock live on exit.  

References _var_map::num_partitions, partition_to_var(), _var_map::partition_to_view, print_generic_expr(), _var_map::var_partition, _var_map::view_to_partition, and virtual_operand_p().

tree_live_info_p calculate_live_ranges ( )
   Given partition map MAP, calculate all the live on entry bitmaps for
   each partition.  Return a new live info object.  

Referenced by coalesce_partitions().

static void clear_unused_block_pointer ( )
   Set all block pointer in debug or clobber stmt to NULL if the block
   is unused, so that they will not be streamed out.  
static tree clear_unused_block_pointer_1 ( )
   Helper function for clear_unused_block_pointer, called via walk_tree.  
DEBUG_FUNCTION void debug ( )
   Generic dump for the above.  
DEBUG_FUNCTION void debug_scope_block ( )
   Dump the tree of lexical scopes starting at SCOPE to stderr.  FLAGS
   is as in print_generic_expr.  
DEBUG_FUNCTION void debug_scope_blocks ( )
   Dump the tree of lexical scopes of current_function_decl to stderr.
   FLAGS is as in print_generic_expr.  
void delete_tree_live_info ( )
   Free storage for live range info object LIVE.  
void delete_var_map ( )
   Free memory associated with MAP.  

References _var_map::var_partition.

static void dump_scope_block ( )
   Dump scope blocks starting at SCOPE to FILE.  INDENT is the
   indentation level and FLAGS is as in print_generic_expr.  
void dump_scope_blocks ( )
   Dump the tree of lexical scopes of current_function_decl to FILE.
   FLAGS is as in print_generic_expr.  
void dump_var_map ( )
   Output partition map MAP to file F.  

References basic_block_def::index, tree_live_info_d::liveout, partition_to_var(), and print_generic_expr().

Referenced by coalesce_partitions().

var_map init_var_map ( )
   Create a variable partition map of SIZE, initialize and return it.  
static bool is_used_p ( )
   Return true if VAR is marked as used.  

References mark_all_vars_used().

static void live_worklist ( )
   Using LIVE, fill in all the live-on-entry blocks between the defs and uses
   of all the variables.  
     Visit all the blocks in reverse order and propagate live on entry values
     into the predecessors blocks.  
     Process any blocks which require further iteration.  

References edge_def::src.

static void loe_visit_block ( tree_live_info_p  live,
basic_block  bb,
sbitmap  visited,
bitmap  tmp 
   Visit basic block BB and propagate any required live on entry bits from
   LIVE into the predecessors.  VISITED is the bitmap of visited blocks.
   TMP is a temporary work bitmap which is passed in to avoid reallocating
   it each time.  
         TMP is variables live-on-entry from BB that aren't defined in the
         predecessor block.  This should be the live on entry vars to pred.
         Note that liveout is the DEFs in a block while live on entry is
         being calculated.  
         Add these bits to live-on-entry for the pred. if there are any
         changes, and pred_bb has been visited already, add it to the
         revisit stack.  

References add_block(), bitmap_set_bit(), gimple_bb(), gimple_phi_arg_edge(), basic_block_def::index, tree_live_info_d::liveout, tree_live_info_d::map, and var_to_partition().

static void mark_all_vars_used ( tree )

Referenced by is_used_p().

static void mark_all_vars_used ( )
   Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
   eliminated during the tree->rtl conversion process.  
static tree mark_all_vars_used_1 ( )
   Helper function for mark_all_vars_used, called via walk_tree.  
     Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
     fields do not contain vars.  
     Only need to mark VAR_DECLS; parameters and return results are not
     eliminated as unused.  
         When a global var becomes used for the first time also walk its
         initializer (non global ones don't have any).  
     remove_unused_scope_block_p requires information about labels
     which are not DECL_IGNORED_P to tell if they might be used in the IL.  
       Although the TREE_USED values that the frontend uses would be
       acceptable (albeit slightly over-conservative) for our purposes,
       init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
       must re-compute it here.  
static void mark_scope_block_unused ( )
   Mark the scope block SCOPE and its subblocks unused when they can be
   possibly eliminated if dead.  
static tree_live_info_p new_tree_live_info ( )
   Allocate and return a new live range information object base on MAP.  
void partition_view_bitmap ( )
   Create a partition view in MAP which includes just partitions which occur in
   the bitmap ONLY. If WANT_BASES is true, create the base variable map
   as well.  

References bitmap_set_bit().

Referenced by coalesce_partitions().

static void partition_view_fini ( )
   This routine will finalize the view data for MAP based on the partitions
   set in SELECTED.  This is either the same bitmap returned from
   partition_view_init, or a trimmed down version if some of those partitions
   were not desired in this view.  SELECTED is freed before returning.  
     If its a one-to-one ratio, we don't need any view compaction.  
         Give each selected partition an index.  

References _var_map::partition_to_view, and _var_map::view_to_partition.

static bitmap partition_view_init ( )
   Compress the partition numbers in MAP such that they fall in the range
   0..(num_partitions-1) instead of wherever they turned out during
   the partitioning exercise.  This removes any references to unused
   partitions, thereby allowing bitmaps and other vectors to be much

   This is implemented such that compaction doesn't affect partitioning.
   Ie., once partitions are created and possibly merged, running one
   or more different kind of compaction will not affect the partitions
   themselves.  Their index might change, but all the same variables will
   still be members of the same partition group.  This allows work on reduced
   sets, and no loss of information when a larger set is later desired.

   In particular, coalescing can work on partitions which have 2 or more
   definitions, and then 'recompact' later to include all the single
   definitions for assignment to program variables.  
   Set MAP back to the initial state of having no partition view.  Return a
   bitmap which has a bit set for each partition number which is in use in the
     Already in a view? Abandon the old one.  
     Find out which partitions are actually referenced.  
void partition_view_normal ( )
   Create a partition view which includes all the used partitions in MAP.  If
   WANT_BASES is true, create the base variable map as well.  
void register_ssa_partition_check ( )
   Verify that SSA_VAR is a non-virtual SSA_NAME.  

References gimple_phi_arg_def(), gimple_phi_num_args(), and gsi_stmt().

Referenced by basevar_index().

void remove_unused_locals ( void  )
   Remove local variables that are not referenced in the IL.  
     Removing declarations from lexical blocks when not optimizing is
     not only a waste of time, it actually causes differences in stack
     Walk the CFG marking all referenced symbols.  
         Walk the statements.  
     We do a two-pass approach about the out-of-scope clobbers.  We want
     to remove them if they are the only references to a local variable,
     but we want to retain them when there's any other.  So the first pass
     ignores them, and the second pass (if there were any) tries to remove
                   Remove clobbers referencing unused vars, or clobbers
                   with MEM_REF lhs referencing uninitialized pointers.  
     Remove unmarked local and global vars from local_decls.  
                 Release any default def associated with var.  
static bool remove_unused_scope_block_p ( )
   Look if the block is dead (by possibly eliminating its dead subblocks)
   and return true if so.
   Block is declared dead if:
     1) No statements are associated with it.
     2) Declares no live variables
     3) All subblocks are dead
        or there is precisely one subblocks and the block
        has same abstract origin as outer block and declares
        no variables, so it is pure wrapper.
   When we are not outputting full debug info, we also eliminate dead variables
   out of scope blocks to let them to be recycled by GGC and to save copying work
   done by the inliner.  
         Debug info of nested function refers to the block of the
         function.  We might stil call it even if all statements
         of function it was nested into was elliminated.

         TODO: We can actually look into cgraph to see if function
         will be output to file.  
         If a decl has a value expr, we need to instantiate it
         regardless of debug info generation, to avoid codegen
         differences in memory overlap tests.  update_equiv_regs() may
         indirectly call validate_equiv_mem() to test whether a
         SET_DEST overlaps with others, and if the value expr changes
         by virtual register instantiation, we may get end up with
         different results.  
         Remove everything we don't generate debug info for.  
         When we are outputting debug info, we usually want to output
         info about optimized-out variables in the scope blocks.
         Exception are the scope blocks not containing any instructions
         at all so user can't get into the scopes at first place.  
           For labels that are still used in the IL, the decision to
           preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
           risk having different ordering in debug vs.  non-debug builds
           during inlining or versioning.
           A label appearing here (we have already checked DECL_IGNORED_P)
           should not be used in the IL unless it has been explicitly used
           before, so we use TREE_USED as an approximation.  
           In principle, we should do the same here as for the debug case
           below, however, when debugging, there might be additional nested
           levels that keep an upper level with a label live, so we have to
           force this block to be considered used, too.  
         When we are not doing full debug info, we however can keep around
         only the used variables for cfgexpand's memory packing saving quite
         a lot of memory.

         For sake of -g3, we keep around those vars but we don't count this as
         use of block, so innermost block with no used vars and no instructions
         can be considered dead.  We only want to keep around blocks user can
         breakpoint into and ask about value of optimized out variables.

         Similarly we need to keep around types at least until all
         variables of all nested blocks are gone.  We track no
         information on whether given type is used or not, so we have
         to keep them even when not emitting debug information,
         otherwise we may end up remapping variables and their (local)
         types in different orders depending on whether debug
         information is being generated.  
      Outer scope is always used.  
      Innermost blocks with no live variables nor statements can be always
      For terse debug info we can eliminate info on unused variables.  
          Even for -g0/-g1 don't prune outer scopes from artificial
          functions, otherwise diagnostics using tree_nonartificial_location
          will not be emitted properly.  
      See if this block is important for representation of inlined function.
      Inlined functions are always represented by block with
      block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
      Verfify that only blocks with source location set
      are entry points to the inlined functions.  
static bool set_is_used ( )
   Mark VAR as used, so that it'll be preserved during rtl expansion.
   Returns true if VAR wasn't marked before.  
static void set_var_live_on_entry ( )
   Calculate the initial live on entry vector for SSA_NAME using immediate_use
   links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
   in the liveout vector.  
         Mark defs in liveout bitmap temporarily.  
     Visit each use of SSA_NAME and if it isn't in the same block as the def,
     add it to the list of live on entry blocks.  
             Uses in PHI's are considered to be live at exit of the SRC block
             as this is where a copy would be inserted.  Check to see if it is
             defined in that block, or whether its live on entry.  
             If its not defined in this block, its live on entry.  
         If there was a live on entry use, set the bit.  
     If SSA_NAME is live on entry to at least one block, fill in all the live
     on entry blocks between the def and all the uses.  

References bitmap_clear(), bitmap_ior_into(), bitmap_set_bit(), edge_def::dest, gimple_phi_arg_edge(), gimple_phi_num_args(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, live_on_entry(), tree_live_info_d::liveout, tree_live_info_d::map, edge_def::src, basic_block_def::succs, and var_to_partition().

static void var_map_base_fini ( )
   Remove the base table in MAP.  
     Free the basevar info if it is present.  

References map, _var_map::num_basevars, _var_map::num_partitions, _var_map::partition_size, _var_map::partition_to_view, _var_map::var_partition, and _var_map::view_to_partition.

static void var_map_base_init ( )
   This routine will initialize the basevar fields of MAP.  
     We can have at most num_part entries in the hash tables, so it's
     enough to allocate so many map elements once, saving some malloc
     If a base table already exists, clear it, otherwise create it.  
     Build the base variable list, and point partitions at their bases.  
           This restricts what anonymous SSA names we can coalesce
           as it restricts the sets we compute conflicts for.
           Using TREE_TYPE to generate sets is the easies as
           type equivalency also holds for SSA names with the same
           underlying decl. 

           Check gimple_can_coalesce_p when changing this code.  
         If base variable hasn't been seen, set it up.  
int var_union ( )
   This function will combine the partitions in MAP for VAR1 and VAR2.  It
   Returns the partition which represents the new partition.  If the two
   partitions cannot be combined, NO_PARTITION is returned.  
     This is independent of partition_to_view. If partition_to_view is
     on, then whichever one of these partitions is absorbed will never have a
     dereference into the partition_to_view array any more.  
static void verify_live_on_entry ( tree_live_info_p  )

Liveness for SSA trees. Copyright (C) 2003-2013 Free Software Foundation, Inc. Contributed by Andrew MacLeod amacl.nosp@m.eod@.nosp@m.redha.nosp@m.t.co.nosp@m.m

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

static void verify_live_on_entry ( )
   Verify that the info in LIVE matches the current cfg.  
      Check for live on entry partitions and report those with a DEF in
      the program. This will typically mean an optimization has done
      something wrong.  
                   The only way this var shouldn't be marked live on entry is
                   if it occurs in a PHI argument of the block.  

Variable Documentation

bitmap_obstack liveness_bitmap_obstack
   Obstack for globale liveness info bitmaps.  We don't want to put these
   on the default obstack because these bitmaps can grow quite large and
   we'll hold on to all that memory until the end of the compiler run.
   As a bonus, delete_tree_live_info can destroy all the bitmaps by just
   releasing the whole obstack.  
bitmap usedvars