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