GCC Middle and Back End API Reference
tree-ssa-live.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "timevar.h"
#include "ssa.h"
#include "cgraph.h"
#include "gimple-pretty-print.h"
#include "diagnostic-core.h"
#include "gimple-iterator.h"
#include "tree-dfa.h"
#include "dumpfile.h"
#include "tree-ssa-live.h"
#include "debug.h"
#include "tree-ssa.h"
#include "ipa-utils.h"
#include "cfgloop.h"
#include "stringpool.h"
#include "attribs.h"
#include "optinfo.h"
#include "gimple-walk.h"
#include "cfganal.h"
#include "tree-cfg.h"
Include dependency graph for tree-ssa-live.cc:

Data Structures

struct  compute_live_vars_data
 

Functions

static void verify_live_on_entry (tree_live_info_p)
 
static void var_map_base_fini (var_map map)
 
var_map init_var_map (int size, class loop *loop, bitmap bitint)
 
void delete_var_map (var_map map)
 
int var_union (var_map map, tree var1, tree var2)
 
static bitmap partition_view_init (var_map map)
 
static void partition_view_fini (var_map map, bitmap selected)
 
void partition_view_normal (var_map map)
 
void partition_view_bitmap (var_map map, bitmap only)
 
static bool set_is_used (tree var)
 
static bool is_used_p (tree var)
 
static void mark_all_vars_used (tree *)
 
static tree mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)
 
static void mark_scope_block_unused (tree scope)
 
static bool remove_unused_scope_block_p (tree scope, bool in_ctor_dtor_block)
 
static tree clear_unused_block_pointer_1 (tree *tp, int *, void *)
 
static void clear_unused_block_pointer (void)
 
static void dump_scope_block (FILE *file, int indent, tree scope, dump_flags_t flags)
 
DEBUG_FUNCTION void debug_scope_block (tree scope, dump_flags_t flags)
 
void dump_scope_blocks (FILE *file, dump_flags_t flags)
 
DEBUG_FUNCTION void debug_scope_blocks (dump_flags_t flags)
 
void remove_unused_locals (void)
 
static tree_live_info_p new_tree_live_info (var_map map)
 
void delete_tree_live_info (tree_live_info_p live)
 
static void loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited)
 
static void live_worklist (tree_live_info_p live)
 
static void set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 
static void calculate_live_on_exit (tree_live_info_p liveinfo)
 
tree_live_info_p calculate_live_ranges (var_map map, bool want_livein)
 
static bool compute_live_vars_visit (gimple *, tree op, tree, void *pdata)
 
static void compute_live_vars_1 (basic_block bb, compute_live_vars_data *data, gimple *stop_after)
 
vec< bitmap_headcompute_live_vars (struct function *fn, live_vars_map *vars)
 
bitmap live_vars_at_stmt (vec< bitmap_head > &active, live_vars_map *vars, gimple *stop_after)
 
void destroy_live_vars (vec< bitmap_head > &active)
 
void dump_var_map (FILE *f, var_map map)
 
DEBUG_FUNCTION void debug (_var_map &ref)
 
DEBUG_FUNCTION void debug (_var_map *ptr)
 
void dump_live_info (FILE *f, tree_live_info_p live, int flag)
 
DEBUG_FUNCTION void debug (tree_live_info_d &ref)
 
DEBUG_FUNCTION void debug (tree_live_info_d *ptr)
 

Variables

static bitmap usedvars
 

Function Documentation

◆ calculate_live_on_exit()

◆ calculate_live_ranges()

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

References bitmap_obstack_release(), calculate_live_on_exit(), free(), i, live_worklist(), tree_live_info_d::livein, tree_live_info_d::livein_obstack, map, new_tree_live_info(), NULL, NULL_TREE, num_var_partitions(), partition_to_var(), set_var_live_on_entry(), and verify_live_on_entry().

Referenced by coalesce_ssa_name().

◆ clear_unused_block_pointer()

static void clear_unused_block_pointer ( void )
static

◆ clear_unused_block_pointer_1()

static tree clear_unused_block_pointer_1 ( tree * tp,
int * ,
void *  )
static
Helper function for clear_unused_block_pointer, called via walk_tree.   

References EXPR_P, NULL, NULL_TREE, TREE_BLOCK, TREE_SET_BLOCK, and TREE_USED.

Referenced by clear_unused_block_pointer().

◆ compute_live_vars()

vec< bitmap_head > compute_live_vars ( struct function * fn,
live_vars_map * vars )
For function FN and live_vars_map (hash map from DECL_UIDs to a dense set of
indexes of automatic variables VARS, compute which of those variables are
(might be) live at the end of each basic block.   

References BASIC_BLOCK_FOR_FN, BITMAP_ALLOC, bitmap_default_obstack, BITMAP_FREE, bitmap_initialize(), bitmap_ior_into(), changed, compute_live_vars_1(), free(), i, basic_block_def::index, last_basic_block_for_fn, NULL, and pre_and_rev_post_order_compute_fn().

Referenced by add_clobbers_to_eh_landing_pad(), and find_tail_calls().

◆ compute_live_vars_1()

static void compute_live_vars_1 ( basic_block bb,
compute_live_vars_data * data,
gimple * stop_after )
static
Helper routine for compute_live_vars, calculating the sets of live
variables at the end of BB, leaving the result in DATA->work.
If STOP_AFTER is non-NULL, stop processing after that stmt.   

References bitmap_clear(), bitmap_clear_bit(), bitmap_ior_into(), compute_live_vars_visit(), DECL_UID, FOR_EACH_EDGE, gimple_assign_lhs(), gimple_clobber_p(), gsi_after_labels(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), is_gimple_debug(), NULL, basic_block_def::preds, VAR_P, visit, and walk_stmt_load_store_addr_ops().

Referenced by compute_live_vars(), and live_vars_at_stmt().

◆ compute_live_vars_visit()

static bool compute_live_vars_visit ( gimple * ,
tree op,
tree ,
void * pdata )
static
Callback for walk_stmt_load_store_addr_ops.  If OP is a VAR_DECL with
uid set in DATA->vars, enter its corresponding index into bitmap
DATA->work.   

References bitmap_set_bit, DECL_UID, get_base_address(), and VAR_P.

Referenced by compute_live_vars_1().

◆ debug() [1/4]

DEBUG_FUNCTION void debug ( _var_map & ref)
Generic dump for the above.   

References dump_var_map().

◆ debug() [2/4]

DEBUG_FUNCTION void debug ( _var_map * ptr)

References debug.

◆ debug() [3/4]

DEBUG_FUNCTION void debug ( tree_live_info_d & ref)
Generic dump for the above.   

References dump_live_info().

◆ debug() [4/4]

DEBUG_FUNCTION void debug ( tree_live_info_d * ptr)

References debug.

◆ debug_scope_block()

DEBUG_FUNCTION void debug_scope_block ( tree scope,
dump_flags_t flags )
Dump the tree of lexical scopes starting at SCOPE to stderr.  FLAGS
is as in print_generic_expr.   

References dump_scope_block().

◆ debug_scope_blocks()

DEBUG_FUNCTION void debug_scope_blocks ( dump_flags_t flags)
Dump the tree of lexical scopes of current_function_decl to stderr.
FLAGS is as in print_generic_expr.   

References dump_scope_blocks().

◆ delete_tree_live_info()

◆ delete_var_map()

void delete_var_map ( var_map map)
Free memory associated with MAP.   

References BITMAP_FREE, free(), map, and var_map_base_fini().

Referenced by finish_out_of_ssa().

◆ destroy_live_vars()

void destroy_live_vars ( vec< bitmap_head > & active)
Destroy what compute_live_vars has returned when it is no longer needed.   

References bitmap_clear(), and i.

Referenced by add_clobbers_to_eh_landing_pad(), and tree_optimize_tail_calls_1().

◆ dump_live_info()

void dump_live_info ( FILE * f,
tree_live_info_p live,
int flag )

◆ dump_scope_block()

static void dump_scope_block ( FILE * file,
int indent,
tree scope,
dump_flags_t flags )
static

◆ dump_scope_blocks()

void dump_scope_blocks ( FILE * file,
dump_flags_t flags )
Dump the tree of lexical scopes of current_function_decl to FILE.
FLAGS is as in print_generic_expr.   

References current_function_decl, DECL_INITIAL, and dump_scope_block().

Referenced by debug_scope_blocks(), execute_build_cfg(), and remove_unused_locals().

◆ dump_var_map()

void dump_var_map ( FILE * f,
var_map map )

◆ init_var_map()

var_map init_var_map ( int size,
class loop * loop,
bitmap bitint )
Create a variable partition map of SIZE for region, initialize and return
it.  Region is a loop if LOOP is non-NULL, otherwise is the current
function.  If BITINT is non-NULL, only SSA_NAMEs from that bitmap
will be coalesced.   

References BITMAP_ALLOC, bitmap_set_bit, cfun, FOR_EACH_BB_FN, free(), get_loop_body_in_dom_order(), i, basic_block_def::index, map, n_basic_blocks_for_fn, NULL, NUM_FIXED_BLOCKS, loop::num_nodes, and vNULL.

Referenced by gimple_lower_bitint(), and remove_ssa_form().

◆ is_used_p()

static bool is_used_p ( tree var)
inlinestatic
Return true if VAR is marked as used.   

References bitmap_bit_p, DECL_UID, and usedvars.

Referenced by remove_unused_locals(), and remove_unused_scope_block_p().

◆ live_vars_at_stmt()

bitmap live_vars_at_stmt ( vec< bitmap_head > & active,
live_vars_map * vars,
gimple * stop_after )
For ACTIVE computed by compute_live_vars, compute a bitmap of variables
live after the STOP_AFTER statement and return that bitmap.   

References BITMAP_ALLOC, compute_live_vars_1(), gimple_bb(), and NULL.

Referenced by find_tail_calls().

◆ live_worklist()

static void live_worklist ( tree_live_info_p live)
static
Using LIVE, fill in all the live-on-entry blocks between the defs and uses
of all the variables.   

References b, BASIC_BLOCK_FOR_FN, bitmap_clear(), cfun, i, last_basic_block_for_fn, loe_visit_block(), tree_live_info_d::map, tree_live_info_d::stack_top, _var_map::vec_bbs, visited, and tree_live_info_d::work_stack.

Referenced by calculate_live_ranges().

◆ loe_visit_block()

static void loe_visit_block ( tree_live_info_p live,
basic_block bb,
sbitmap visited )
static
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.   

References bitmap_bit_p, bitmap_clear_bit(), bitmap_ior_and_compl_into(), bitmap_set_bit, FOR_EACH_EDGE, gcc_checking_assert, basic_block_def::index, live_on_entry(), tree_live_info_d::liveout, tree_live_info_d::map, basic_block_def::preds, region_contains_p(), tree_live_info_d::stack_top, and visited.

Referenced by live_worklist().

◆ mark_all_vars_used()

static void mark_all_vars_used ( tree * expr_p)
inlinestatic
Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
eliminated during the tree->rtl conversion process.   

References mark_all_vars_used_1(), NULL, and walk_tree.

Referenced by mark_all_vars_used_1(), and remove_unused_locals().

◆ mark_all_vars_used_1()

static tree mark_all_vars_used_1 ( tree * tp,
int * walk_subtrees,
void * data )
static

◆ mark_scope_block_unused()

static void mark_scope_block_unused ( tree scope)
static
Mark the scope block SCOPE and its subblocks unused when they can be
possibly eliminated if dead.   

References BLOCK_CHAIN, BLOCK_SUBBLOCKS, debug_hooks, gcc_debug_hooks::ignore_block, mark_scope_block_unused(), and TREE_USED.

Referenced by mark_scope_block_unused(), and remove_unused_locals().

◆ new_tree_live_info()

◆ partition_view_bitmap()

void partition_view_bitmap ( var_map map,
bitmap only )
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_ALLOC, bitmap_bit_p, bitmap_set_bit, EXECUTE_IF_SET_IN_BITMAP, gcc_assert, map, NULL, partition_view_fini(), partition_view_init(), and var_map_base_fini().

Referenced by coalesce_ssa_name().

◆ partition_view_fini()

static void partition_view_fini ( var_map map,
bitmap selected )
static
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.   

References bitmap_count_bits(), BITMAP_FREE, count, EXECUTE_IF_SET_IN_BITMAP, gcc_assert, i, and map.

Referenced by partition_view_bitmap(), and partition_view_normal().

◆ partition_view_init()

static bitmap partition_view_init ( var_map map)
static
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
denser.

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

References BITMAP_ALLOC, bitmap_set_bit, free(), has_zero_uses(), map, NULL, NULL_TREE, ssa_name, SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, VAR_P, and virtual_operand_p().

Referenced by partition_view_bitmap(), and partition_view_normal().

◆ partition_view_normal()

void partition_view_normal ( var_map map)
Create a partition view which includes all the used partitions in MAP.   

References map, partition_view_fini(), partition_view_init(), and var_map_base_fini().

Referenced by gimple_lower_bitint(), and remove_ssa_form().

◆ remove_unused_locals()

◆ remove_unused_scope_block_p()

static bool remove_unused_scope_block_p ( tree scope,
bool in_ctor_dtor_block )
static
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.   

References BLOCK_CHAIN, BLOCK_NUM_NONLOCALIZED_VARS, BLOCK_ORIGIN, BLOCK_SOURCE_LOCATION, BLOCK_SUBBLOCKS, BLOCK_SUPERCONTEXT, block_ultimate_origin(), BLOCK_VARS, DECL_CHAIN, DECL_HAS_VALUE_EXPR_P, DECL_IGNORED_P, DINFO_LEVEL_NONE, DINFO_LEVEL_NORMAL, DINFO_LEVEL_VERBOSE, gcc_assert, inlined_function_outer_scope_p(), inlined_polymorphic_ctor_dtor_block_p(), is_used_p(), LOCATION_LOCUS, optinfo_wants_inlining_info_p(), remove_unused_scope_block_p(), TREE_CODE, TREE_USED, UNKNOWN_LOCATION, and VAR_P.

Referenced by remove_unused_locals(), and remove_unused_scope_block_p().

◆ set_is_used()

static bool set_is_used ( tree var)
inlinestatic
Mark VAR as used, so that it'll be preserved during rtl expansion.
Returns true if VAR wasn't marked before.   

References bitmap_set_bit, DECL_UID, and usedvars.

Referenced by mark_all_vars_used_1().

◆ set_var_live_on_entry()

static void set_var_live_on_entry ( tree ssa_name,
tree_live_info_p live )
static
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.   

References as_a(), bitmap_set_bit, cfun, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_IMM_USE_FAST, gimple_bb(), gimple_phi_arg_edge(), basic_block_def::index, is_gimple_debug(), tree_live_info_d::livein, tree_live_info_d::liveout, tree_live_info_d::map, NO_PARTITION, NULL, PHI_ARG_INDEX_FROM_USE, region_contains_p(), ssa_name, SSA_NAME_DEF_STMT, ssa_undefined_value_p(), USE_STMT, and var_to_partition().

Referenced by calculate_live_ranges().

◆ var_map_base_fini()

static void var_map_base_fini ( var_map map)
static
VARMAP maintains a mapping from SSA version number to real variables.

All SSA_NAMES are divided into partitions.  Initially each ssa_name is the
only member of it's own partition.  Coalescing will attempt to group any
ssa_names which occur in a copy or in a PHI node into the same partition.

At the end of out-of-ssa, each partition becomes a "real" variable and is
rewritten as a compiler variable.

The var_map data structure is used to manage these partitions.  It allows
partitions to be combined, and determines which partition belongs to what
ssa_name or variable, and vice versa.   
Remove the base table in MAP.   

References free(), map, and NULL.

Referenced by delete_var_map(), partition_view_bitmap(), and partition_view_normal().

◆ var_union()

int var_union ( var_map map,
tree var1,
tree var2 )
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.   

References gcc_assert, map, NO_PARTITION, SSA_NAME_VERSION, and TREE_CODE.

Referenced by attempt_coalesce().

◆ verify_live_on_entry()

static void verify_live_on_entry ( tree_live_info_p live)
static
Liveness for SSA trees.
   Copyright (C) 2003-2024 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod <amacleod@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/>.   
Verify that the info in LIVE matches the current cfg.   

References bitmap_bit_p, cfun, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, gcc_assert, gimple_bb(), gimple_nop_p(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), has_zero_uses(), i, basic_block_def::index, live_on_entry(), map, tree_live_info_d::map, NULL_TREE, num_var_partitions(), partition_to_var(), gphi_iterator::phi(), print_generic_expr(), print_gimple_stmt(), region_contains_p(), ssa_default_def(), SSA_NAME_DEF_STMT, SSA_NAME_VAR, ssa_undefined_value_p(), basic_block_def::succs, TDF_SLIM, VAR_P, and virtual_operand_p().

Referenced by calculate_live_ranges().

Variable Documentation

◆ usedvars

bitmap usedvars
static