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