1/* Routines for liveness in SSA trees. 2 Copyright (C) 2003-2020 Free Software Foundation, Inc. 3 Contributed by Andrew MacLeod <amacleod@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21 22#ifndef _TREE_SSA_LIVE_H 23#define _TREE_SSA_LIVE_H 1 24 25#include "partition.h" 26 27/* Used to create the variable mapping when we go out of SSA form. 28 29 Mapping from an ssa_name to a partition number is maintained, as well as 30 partition number back to ssa_name. 31 32 This data structure also supports "views", which work on a subset of all 33 partitions. This allows the coalescer to decide what partitions are 34 interesting to it, and only work with those partitions. Whenever the view 35 is changed, the partition numbers change, but none of the partition groupings 36 change. (ie, it is truly a view since it doesn't change anything) 37 38 The final component of the data structure is the basevar map. This provides 39 a list of all the different base variables which occur in a partition view, 40 and a unique index for each one. Routines are provided to quickly produce 41 the base variable of a partition. 42 43 Note that members of a partition MUST all have the same base variable. */ 44 45typedef struct _var_map 46{ 47 /* The partition manager of all variables. */ 48 partition var_partition; 49 50 /* Vector for managing partitions views. */ 51 int *partition_to_view; 52 int *view_to_partition; 53 54 /* Current number of partitions in var_map based on the current view. */ 55 unsigned int num_partitions; 56 57 /* Original full partition size. */ 58 unsigned int partition_size; 59 60 /* Number of base variables in the base var list. */ 61 int num_basevars; 62 63 /* Map of partitions numbers to base variable table indexes. */ 64 int *partition_to_base_index; 65 66 /* Bitmap of basic block. It describes the region within which the analysis 67 is done. Using pointer avoids allocating memory in out-of-ssa case. */ 68 bitmap bmp_bbs; 69 70 /* Vector of basic block in the region. */ 71 vec<basic_block> vec_bbs; 72 73 /* True if this map is for out-of-ssa, otherwise for live range 74 computation. When for out-of-ssa, it also means the var map is computed 75 for whole current function. */ 76 bool outofssa_p; 77} *var_map; 78 79 80/* Value used to represent no partition number. */ 81#define NO_PARTITION -1 82 83extern var_map init_var_map (int, class loop* = NULL); 84extern void delete_var_map (var_map); 85extern int var_union (var_map, tree, tree); 86extern void partition_view_normal (var_map); 87extern void partition_view_bitmap (var_map, bitmap); 88extern void dump_scope_blocks (FILE *, dump_flags_t); 89extern void debug_scope_block (tree, dump_flags_t); 90extern void debug_scope_blocks (dump_flags_t); 91extern void remove_unused_locals (void); 92extern void dump_var_map (FILE *, var_map); 93extern void debug (_var_map &ref); 94extern void debug (_var_map *ptr); 95 96 97/* Return TRUE if region of the MAP contains basic block BB. */ 98 99inline bool 100region_contains_p (var_map map, basic_block bb) 101{ 102 /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK. */ 103 if (map->outofssa_p) 104 return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK); 105 106 return bitmap_bit_p (map->bmp_bbs, bb->index); 107} 108 109 110/* Return number of partitions in MAP. */ 111 112static inline unsigned 113num_var_partitions (var_map map) 114{ 115 return map->num_partitions; 116} 117 118 119/* Given partition index I from MAP, return the variable which represents that 120 partition. */ 121 122static inline tree 123partition_to_var (var_map map, int i) 124{ 125 tree name; 126 if (map->view_to_partition) 127 i = map->view_to_partition[i]; 128 i = partition_find (map->var_partition, i); 129 name = ssa_name (i); 130 return name; 131} 132 133 134/* Given ssa_name VERSION, if it has a partition in MAP, return the var it 135 is associated with. Otherwise return NULL. */ 136 137static inline tree 138version_to_var (var_map map, int version) 139{ 140 int part; 141 part = partition_find (map->var_partition, version); 142 if (map->partition_to_view) 143 part = map->partition_to_view[part]; 144 if (part == NO_PARTITION) 145 return NULL_TREE; 146 147 return partition_to_var (map, part); 148} 149 150 151/* Given VAR, return the partition number in MAP which contains it. 152 NO_PARTITION is returned if it's not in any partition. */ 153 154static inline int 155var_to_partition (var_map map, tree var) 156{ 157 int part; 158 159 part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); 160 if (map->partition_to_view) 161 part = map->partition_to_view[part]; 162 return part; 163} 164 165 166/* Given VAR, return the variable which represents the entire partition 167 it is a member of in MAP. NULL is returned if it is not in a partition. */ 168 169static inline tree 170var_to_partition_to_var (var_map map, tree var) 171{ 172 int part; 173 174 part = var_to_partition (map, var); 175 if (part == NO_PARTITION) 176 return NULL_TREE; 177 return partition_to_var (map, part); 178} 179 180 181/* Return the index into the basevar table for PARTITION's base in MAP. */ 182 183static inline int 184basevar_index (var_map map, int partition) 185{ 186 gcc_checking_assert (partition >= 0 187 && partition <= (int) num_var_partitions (map)); 188 return map->partition_to_base_index[partition]; 189} 190 191 192/* Return the number of different base variables in MAP. */ 193 194static inline int 195num_basevars (var_map map) 196{ 197 return map->num_basevars; 198} 199 200 201/* ---------------- live on entry/exit info ------------------------------ 202 203 This structure is used to represent live range information on SSA based 204 trees. A partition map must be provided, and based on the active partitions, 205 live-on-entry information and live-on-exit information can be calculated. 206 As well, partitions are marked as to whether they are global (live 207 outside the basic block they are defined in). 208 209 The live-on-entry information is per block. It provide a bitmap for 210 each block which has a bit set for each partition that is live on entry to 211 that block. 212 213 The live-on-exit information is per block. It provides a bitmap for each 214 block indicating which partitions are live on exit from the block. 215 216 For the purposes of this implementation, we treat the elements of a PHI 217 as follows: 218 219 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they 220 originate. They are *NOT* considered live on entry to the block 221 containing the PHI node. 222 223 The Def of a PHI node is *not* considered live on entry to the block. 224 It is considered to be "define early" in the block. Picture it as each 225 block having a stmt (or block-preheader) before the first real stmt in 226 the block which defines all the variables that are defined by PHIs. 227 228 ----------------------------------------------------------------------- */ 229 230 231typedef struct tree_live_info_d 232{ 233 /* Var map this relates to. */ 234 var_map map; 235 236 /* Bitmap indicating which partitions are global. */ 237 bitmap global; 238 239 /* Bitmaps of live on entry blocks for partition elements. */ 240 bitmap_head *livein; 241 242 /* Bitmaps of what variables are live on exit for a basic blocks. */ 243 bitmap_head *liveout; 244 245 /* Number of basic blocks when live on exit calculated. */ 246 int num_blocks; 247 248 /* Vector used when creating live ranges as a visited stack. */ 249 int *work_stack; 250 251 /* Top of workstack. */ 252 int *stack_top; 253 254 /* Obstacks to allocate the bitmaps on. */ 255 bitmap_obstack livein_obstack; 256 bitmap_obstack liveout_obstack; 257} *tree_live_info_p; 258 259 260#define LIVEDUMP_ENTRY 0x01 261#define LIVEDUMP_EXIT 0x02 262#define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) 263extern void delete_tree_live_info (tree_live_info_p); 264extern tree_live_info_p calculate_live_ranges (var_map, bool); 265extern void debug (tree_live_info_d &ref); 266extern void debug (tree_live_info_d *ptr); 267extern void dump_live_info (FILE *, tree_live_info_p, int); 268 269typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map; 270extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *); 271extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *, 272 gimple *); 273extern void destroy_live_vars (vec<bitmap_head> &); 274 275/* Return TRUE if P is marked as a global in LIVE. */ 276 277static inline int 278partition_is_global (tree_live_info_p live, int p) 279{ 280 gcc_checking_assert (live->global); 281 return bitmap_bit_p (live->global, p); 282} 283 284 285/* Return the bitmap from LIVE representing the live on entry blocks for 286 partition P. */ 287 288static inline bitmap 289live_on_entry (tree_live_info_p live, basic_block bb) 290{ 291 gcc_checking_assert (live->livein 292 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) 293 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); 294 295 return &live->livein[bb->index]; 296} 297 298 299/* Return the bitmap from LIVE representing the live on exit partitions from 300 block BB. */ 301 302static inline bitmap 303live_on_exit (tree_live_info_p live, basic_block bb) 304{ 305 gcc_checking_assert (live->liveout 306 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) 307 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); 308 309 return &live->liveout[bb->index]; 310} 311 312 313/* Return the partition map which the information in LIVE utilizes. */ 314 315static inline var_map 316live_var_map (tree_live_info_p live) 317{ 318 return live->map; 319} 320 321 322/* Mark partition P as live on entry to basic block BB in LIVE. */ 323 324static inline void 325make_live_on_entry (tree_live_info_p live, basic_block bb , int p) 326{ 327 bitmap_set_bit (&live->livein[bb->index], p); 328 bitmap_set_bit (live->global, p); 329} 330 331#endif /* _TREE_SSA_LIVE_H */ 332