GCC Middle and Back End API Reference
tree-ssa-live.h File Reference
#include "partition.h"
Include dependency graph for tree-ssa-live.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  _var_map
 
struct  tree_live_info_d
 
class  virtual_operand_live
 

Macros

#define NO_PARTITION   -1
 
#define LIVEDUMP_ENTRY   0x01
 
#define LIVEDUMP_EXIT   0x02
 
#define LIVEDUMP_ALL   (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 

Typedefs

typedef struct _var_mapvar_map
 
typedef struct tree_live_info_dtree_live_info_p
 
typedef hash_map< int_hash< unsigned int, -1U >, unsigned int > live_vars_map
 

Functions

var_map init_var_map (int, class loop *=NULL, bitmap=NULL)
 
void delete_var_map (var_map)
 
int var_union (var_map, tree, tree)
 
void partition_view_normal (var_map)
 
void partition_view_bitmap (var_map, bitmap)
 
void dump_scope_blocks (FILE *, dump_flags_t)
 
void debug_scope_block (tree, dump_flags_t)
 
void debug_scope_blocks (dump_flags_t)
 
void remove_unused_locals (void)
 
void dump_var_map (FILE *, var_map)
 
void debug (_var_map &ref)
 
void debug (_var_map *ptr)
 
bool region_contains_p (var_map map, basic_block bb)
 
unsigned num_var_partitions (var_map map)
 
tree partition_to_var (var_map map, int i)
 
tree version_to_var (var_map map, int version)
 
int var_to_partition (var_map map, tree var)
 
tree var_to_partition_to_var (var_map map, tree var)
 
int basevar_index (var_map map, int partition)
 
int num_basevars (var_map map)
 
void delete_tree_live_info (tree_live_info_p)
 
tree_live_info_p calculate_live_ranges (var_map, bool)
 
void debug (tree_live_info_d &ref)
 
void debug (tree_live_info_d *ptr)
 
void dump_live_info (FILE *, tree_live_info_p, int)
 
vec< bitmap_headcompute_live_vars (struct function *, live_vars_map *)
 
bitmap live_vars_at_stmt (vec< bitmap_head > &, live_vars_map *, gimple *)
 
void destroy_live_vars (vec< bitmap_head > &)
 
bitmap live_on_entry (tree_live_info_p live, basic_block bb)
 
bitmap live_on_exit (tree_live_info_p live, basic_block bb)
 
var_map live_var_map (tree_live_info_p live)
 
void make_live_on_entry (tree_live_info_p live, basic_block bb, int p)
 

Macro Definition Documentation

◆ LIVEDUMP_ALL

#define LIVEDUMP_ALL   (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)

◆ LIVEDUMP_ENTRY

#define LIVEDUMP_ENTRY   0x01

◆ LIVEDUMP_EXIT

#define LIVEDUMP_EXIT   0x02

Referenced by dump_live_info().

◆ NO_PARTITION

Typedef Documentation

◆ live_vars_map

typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map

◆ tree_live_info_p

---------------- live on entry/exit info ------------------------------

This structure is used to represent live range information on SSA based
trees. A partition map must be provided, and based on the active partitions,
live-on-entry information and live-on-exit information can be calculated.
As well, partitions are marked as to whether they are global (live
outside the basic block they are defined in).

The live-on-entry information is per block.  It provide a bitmap for
each block which has a bit set for each partition that is live on entry to
that block.

The live-on-exit information is per block.  It provides a bitmap for each
block indicating which partitions are live on exit from the block.

For the purposes of this implementation, we treat the elements of a PHI
as follows:

   Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
   originate. They are *NOT* considered live on entry to the block
   containing the PHI node.

   The Def of a PHI node is *not* considered live on entry to the block.
   It is considered to be "define early" in the block. Picture it as each
   block having a stmt (or block-preheader) before the first real stmt in
   the block which defines all the variables that are defined by PHIs.

-----------------------------------------------------------------------   

◆ var_map

typedef struct _var_map * var_map
Routines for liveness in 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/>.   
Used to create the variable mapping when we go out of SSA form.

Mapping from an ssa_name to a partition number is maintained, as well as
partition number back to ssa_name.

This data structure also supports "views", which work on a subset of all
partitions.  This allows the coalescer to decide what partitions are
interesting to it, and only work with those partitions.  Whenever the view
is changed, the partition numbers change, but none of the partition groupings
change. (ie, it is truly a view since it doesn't change anything)

The final component of the data structure is the basevar map.  This provides
a list of all the different base variables which occur in a partition view,
and a unique index for each one. Routines are provided to quickly produce
the base variable of a partition.

Note that members of a partition MUST all have the same base variable.   

Function Documentation

◆ basevar_index()

int basevar_index ( var_map map,
int partition )
inline
Return the index into the basevar table for PARTITION's base in MAP.   

References gcc_checking_assert, map, and num_var_partitions().

Referenced by live_track_add_partition(), live_track_live_p(), live_track_process_def(), and live_track_remove_partition().

◆ calculate_live_ranges()

tree_live_info_p calculate_live_ranges ( var_map map,
bool want_livein )
extern
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().

◆ compute_live_vars()

vec< bitmap_head > compute_live_vars ( struct function * fn,
live_vars_map * vars )
extern
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().

◆ debug() [1/4]

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

References dump_var_map().

◆ debug() [2/4]

void debug ( _var_map * ptr)
extern

References debug.

◆ debug() [3/4]

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

References dump_live_info().

◆ debug() [4/4]

void debug ( tree_live_info_d * ptr)
extern

References debug.

◆ debug_scope_block()

void debug_scope_block ( tree scope,
dump_flags_t flags )
extern
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()

void debug_scope_blocks ( dump_flags_t flags)
extern
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)
extern
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)
extern
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 )
extern

◆ dump_scope_blocks()

void dump_scope_blocks ( FILE * file,
dump_flags_t flags )
extern
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 )
extern

◆ init_var_map()

var_map init_var_map ( int size,
class loop * loop,
bitmap bitint )
extern
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().

◆ live_on_entry()

bitmap live_on_entry ( tree_live_info_p live,
basic_block bb )
inline
Return the bitmap from LIVE representing the live on entry blocks for
partition P.   

References cfun, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, gcc_checking_assert, basic_block_def::index, and tree_live_info_d::livein.

Referenced by calculate_live_on_exit(), loe_visit_block(), and verify_live_on_entry().

◆ live_on_exit()

bitmap live_on_exit ( tree_live_info_p live,
basic_block bb )
inline
Return the bitmap from LIVE representing the live on exit partitions from
block BB.   

References cfun, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, gcc_checking_assert, basic_block_def::index, and tree_live_info_d::liveout.

Referenced by build_ssa_conflict_graph().

◆ live_var_map()

var_map live_var_map ( tree_live_info_p live)
inline
Return the partition map which the information in LIVE utilizes.   

References tree_live_info_d::map.

Referenced by build_ssa_conflict_graph().

◆ live_vars_at_stmt()

bitmap live_vars_at_stmt ( vec< bitmap_head > & active,
live_vars_map * vars,
gimple * stop_after )
extern
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().

◆ make_live_on_entry()

void make_live_on_entry ( tree_live_info_p live,
basic_block bb,
int p )
inline
Mark partition P as live on entry to basic block BB in LIVE.   

References bitmap_set_bit, basic_block_def::index, and tree_live_info_d::livein.

◆ num_basevars()

int num_basevars ( var_map map)
inline
Return the number of different base variables in MAP.   

References map.

Referenced by new_live_track().

◆ num_var_partitions()

◆ partition_to_var()

◆ partition_view_bitmap()

void partition_view_bitmap ( var_map map,
bitmap only )
extern
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_normal()

void partition_view_normal ( var_map map)
extern
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().

◆ region_contains_p()

bool region_contains_p ( var_map map,
basic_block bb )
inline
Return TRUE if region of the MAP contains basic block BB.   

References bitmap_bit_p, ENTRY_BLOCK, EXIT_BLOCK, basic_block_def::index, and map.

Referenced by calculate_live_on_exit(), loe_visit_block(), set_var_live_on_entry(), and verify_live_on_entry().

◆ remove_unused_locals()

◆ var_to_partition()

◆ var_to_partition_to_var()

tree var_to_partition_to_var ( var_map map,
tree var )
inline
Given VAR, return the variable which represents the entire partition
it is a member of in MAP.  NULL is returned if it is not in a partition.   

References map, NO_PARTITION, NULL_TREE, partition_to_var(), and var_to_partition().

Referenced by rewrite_trees().

◆ var_union()

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

◆ version_to_var()

tree version_to_var ( var_map map,
int version )
inline
Given ssa_name VERSION, if it has a partition in MAP,  return the var it
is associated with.  Otherwise return NULL.   

References map, NO_PARTITION, NULL_TREE, and partition_to_var().

Referenced by dump_part_var_map().