1/* Routines for liveness in SSA trees. 2 Copyright (C) 2003-2015 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} *var_map; 66 67 68/* Value used to represent no partition number. */ 69#define NO_PARTITION -1 70 71extern var_map init_var_map (int); 72extern void delete_var_map (var_map); 73extern int var_union (var_map, tree, tree); 74extern void partition_view_normal (var_map, bool); 75extern void partition_view_bitmap (var_map, bitmap, bool); 76extern void dump_scope_blocks (FILE *, int); 77extern void debug_scope_block (tree, int); 78extern void debug_scope_blocks (int); 79extern void remove_unused_locals (void); 80extern void dump_var_map (FILE *, var_map); 81extern void debug (_var_map &ref); 82extern void debug (_var_map *ptr); 83#ifdef ENABLE_CHECKING 84extern void register_ssa_partition_check (tree ssa_var); 85#endif 86 87 88/* Return number of partitions in MAP. */ 89 90static inline unsigned 91num_var_partitions (var_map map) 92{ 93 return map->num_partitions; 94} 95 96 97/* Given partition index I from MAP, return the variable which represents that 98 partition. */ 99 100static inline tree 101partition_to_var (var_map map, int i) 102{ 103 tree name; 104 if (map->view_to_partition) 105 i = map->view_to_partition[i]; 106 i = partition_find (map->var_partition, i); 107 name = ssa_name (i); 108 return name; 109} 110 111 112/* Given ssa_name VERSION, if it has a partition in MAP, return the var it 113 is associated with. Otherwise return NULL. */ 114 115static inline tree 116version_to_var (var_map map, int version) 117{ 118 int part; 119 part = partition_find (map->var_partition, version); 120 if (map->partition_to_view) 121 part = map->partition_to_view[part]; 122 if (part == NO_PARTITION) 123 return NULL_TREE; 124 125 return partition_to_var (map, part); 126} 127 128 129/* Given VAR, return the partition number in MAP which contains it. 130 NO_PARTITION is returned if it's not in any partition. */ 131 132static inline int 133var_to_partition (var_map map, tree var) 134{ 135 int part; 136 137 part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); 138 if (map->partition_to_view) 139 part = map->partition_to_view[part]; 140 return part; 141} 142 143 144/* Given VAR, return the variable which represents the entire partition 145 it is a member of in MAP. NULL is returned if it is not in a partition. */ 146 147static inline tree 148var_to_partition_to_var (var_map map, tree var) 149{ 150 int part; 151 152 part = var_to_partition (map, var); 153 if (part == NO_PARTITION) 154 return NULL_TREE; 155 return partition_to_var (map, part); 156} 157 158 159/* Return the index into the basevar table for PARTITION's base in MAP. */ 160 161static inline int 162basevar_index (var_map map, int partition) 163{ 164 gcc_checking_assert (partition >= 0 165 && partition <= (int) num_var_partitions (map)); 166 return map->partition_to_base_index[partition]; 167} 168 169 170/* Return the number of different base variables in MAP. */ 171 172static inline int 173num_basevars (var_map map) 174{ 175 return map->num_basevars; 176} 177 178 179 180/* This routine registers a partition for SSA_VAR with MAP. Any unregistered 181 partitions may be filtered out by a view later. */ 182 183static inline void 184register_ssa_partition (var_map map ATTRIBUTE_UNUSED, 185 tree ssa_var ATTRIBUTE_UNUSED) 186{ 187#if defined ENABLE_CHECKING 188 register_ssa_partition_check (ssa_var); 189#endif 190} 191 192 193/* ---------------- live on entry/exit info ------------------------------ 194 195 This structure is used to represent live range information on SSA based 196 trees. A partition map must be provided, and based on the active partitions, 197 live-on-entry information and live-on-exit information can be calculated. 198 As well, partitions are marked as to whether they are global (live 199 outside the basic block they are defined in). 200 201 The live-on-entry information is per block. It provide a bitmap for 202 each block which has a bit set for each partition that is live on entry to 203 that block. 204 205 The live-on-exit information is per block. It provides a bitmap for each 206 block indicating which partitions are live on exit from the block. 207 208 For the purposes of this implementation, we treat the elements of a PHI 209 as follows: 210 211 Uses in a PHI are considered LIVE-ON-EXIT to the block from which they 212 originate. They are *NOT* considered live on entry to the block 213 containing the PHI node. 214 215 The Def of a PHI node is *not* considered live on entry to the block. 216 It is considered to be "define early" in the block. Picture it as each 217 block having a stmt (or block-preheader) before the first real stmt in 218 the block which defines all the variables that are defined by PHIs. 219 220 ----------------------------------------------------------------------- */ 221 222 223typedef struct tree_live_info_d 224{ 225 /* Var map this relates to. */ 226 var_map map; 227 228 /* Bitmap indicating which partitions are global. */ 229 bitmap global; 230 231 /* Bitmaps of live on entry blocks for partition elements. */ 232 bitmap_head *livein; 233 234 /* Bitmaps of what variables are live on exit for a basic blocks. */ 235 bitmap_head *liveout; 236 237 /* Number of basic blocks when live on exit calculated. */ 238 int num_blocks; 239 240 /* Vector used when creating live ranges as a visited stack. */ 241 int *work_stack; 242 243 /* Top of workstack. */ 244 int *stack_top; 245 246 /* Obstacks to allocate the bitmaps on. */ 247 bitmap_obstack livein_obstack; 248 bitmap_obstack liveout_obstack; 249} *tree_live_info_p; 250 251 252#define LIVEDUMP_ENTRY 0x01 253#define LIVEDUMP_EXIT 0x02 254#define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) 255extern void delete_tree_live_info (tree_live_info_p); 256extern tree_live_info_p calculate_live_ranges (var_map, bool); 257extern void debug (tree_live_info_d &ref); 258extern void debug (tree_live_info_d *ptr); 259extern void dump_live_info (FILE *, tree_live_info_p, int); 260 261 262/* Return TRUE if P is marked as a global in LIVE. */ 263 264static inline int 265partition_is_global (tree_live_info_p live, int p) 266{ 267 gcc_checking_assert (live->global); 268 return bitmap_bit_p (live->global, p); 269} 270 271 272/* Return the bitmap from LIVE representing the live on entry blocks for 273 partition P. */ 274 275static inline bitmap 276live_on_entry (tree_live_info_p live, basic_block bb) 277{ 278 gcc_checking_assert (live->livein 279 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) 280 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); 281 282 return &live->livein[bb->index]; 283} 284 285 286/* Return the bitmap from LIVE representing the live on exit partitions from 287 block BB. */ 288 289static inline bitmap 290live_on_exit (tree_live_info_p live, basic_block bb) 291{ 292 gcc_checking_assert (live->liveout 293 && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) 294 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); 295 296 return &live->liveout[bb->index]; 297} 298 299 300/* Return the partition map which the information in LIVE utilizes. */ 301 302static inline var_map 303live_var_map (tree_live_info_p live) 304{ 305 return live->map; 306} 307 308 309/* Merge the live on entry information in LIVE for partitions P1 and P2. Place 310 the result into P1. Clear P2. */ 311 312static inline void 313live_merge_and_clear (tree_live_info_p live, int p1, int p2) 314{ 315 gcc_checking_assert (&live->livein[p1] && &live->livein[p2]); 316 bitmap_ior_into (&live->livein[p1], &live->livein[p2]); 317 bitmap_clear (&live->livein[p2]); 318} 319 320 321/* Mark partition P as live on entry to basic block BB in LIVE. */ 322 323static inline void 324make_live_on_entry (tree_live_info_p live, basic_block bb , int p) 325{ 326 bitmap_set_bit (&live->livein[bb->index], p); 327 bitmap_set_bit (live->global, p); 328} 329 330#endif /* _TREE_SSA_LIVE_H */ 331