1/* Routines for liveness in SSA trees. 2 Copyright (C) 2003, 2004, 2005, 2007, 2008 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#include "vecprim.h" 27 28 29 30/* Used to create the variable mapping when we go out of SSA form. 31 32 Mapping from an ssa_name to a partition number is maintained, as well as 33 partition number to back to ssa_name. A partition can also be represented 34 by a non-ssa_name variable. This allows ssa_names and their partition to 35 be coalesced with live on entry compiler variables, as well as eventually 36 having real compiler variables assigned to each partition as part of the 37 final stage of going of of ssa. 38 39 Non-ssa_names maintain their partition index in the variable annotation. 40 41 This data structure also supports "views", which work on a subset of all 42 partitions. This allows the coalescer to decide what partitions are 43 interesting to it, and only work with those partitions. Whenever the view 44 is changed, the partition numbers change, but none of the partition groupings 45 change. (ie, it is truly a view since it doesn't change anything) 46 47 The final component of the data structure is the basevar map. This provides 48 a list of all the different base variables which occur in a partition view, 49 and a unique index for each one. Routines are provided to quickly produce 50 the base variable of a partition. 51 52 Note that members of a partition MUST all have the same base variable. */ 53 54typedef struct _var_map 55{ 56 /* The partition manager of all variables. */ 57 partition var_partition; 58 59 /* Vector for managing partitions views. */ 60 int *partition_to_view; 61 int *view_to_partition; 62 63 /* Current number of partitions in var_map based on the current view. */ 64 unsigned int num_partitions; 65 66 /* Original full partition size. */ 67 unsigned int partition_size; 68 69 /* Number of base variables in the base var list. */ 70 int num_basevars; 71 72 /* Map of partitions numbers to base variable table indexes. */ 73 int *partition_to_base_index; 74 75 /* Table of base variable's. */ 76 VEC (tree, heap) *basevars; 77} *var_map; 78 79 80/* Index to the basevar table of a non ssa-name variable. */ 81#define VAR_ANN_BASE_INDEX(ann) (ann->base_index) 82 83 84/* Value used to represent no partition number. */ 85#define NO_PARTITION -1 86 87extern var_map init_var_map (int); 88extern void delete_var_map (var_map); 89extern void dump_var_map (FILE *, var_map); 90extern int var_union (var_map, tree, tree); 91extern void partition_view_normal (var_map, bool); 92extern void partition_view_bitmap (var_map, bitmap, bool); 93#ifdef ENABLE_CHECKING 94extern void register_ssa_partition_check (tree ssa_var); 95#endif 96 97 98/* Return number of partitions in MAP. */ 99 100static inline unsigned 101num_var_partitions (var_map map) 102{ 103 return map->num_partitions; 104} 105 106 107/* Given partition index I from MAP, return the variable which represents that 108 partition. */ 109 110static inline tree 111partition_to_var (var_map map, int i) 112{ 113 tree name; 114 if (map->view_to_partition) 115 i = map->view_to_partition[i]; 116 i = partition_find (map->var_partition, i); 117 name = ssa_name (i); 118 return name; 119} 120 121 122/* Given ssa_name VERSION, if it has a partition in MAP, return the var it 123 is associated with. Otherwise return NULL. */ 124 125static inline tree 126version_to_var (var_map map, int version) 127{ 128 int part; 129 part = partition_find (map->var_partition, version); 130 if (map->partition_to_view) 131 part = map->partition_to_view[part]; 132 if (part == NO_PARTITION) 133 return NULL_TREE; 134 135 return partition_to_var (map, part); 136} 137 138 139/* Given VAR, return the partition number in MAP which contains it. 140 NO_PARTITION is returned if it's not in any partition. */ 141 142static inline int 143var_to_partition (var_map map, tree var) 144{ 145 int part; 146 147 gcc_assert (TREE_CODE (var) == SSA_NAME); 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 158static inline tree 159var_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 172static inline int 173basevar_index (var_map map, int partition) 174{ 175 gcc_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 183static inline int 184num_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 194static inline void 195register_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 234typedef 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 259extern tree_live_info_p calculate_live_ranges (var_map); 260extern void calculate_live_on_exit (tree_live_info_p); 261extern 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) 266extern 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 271static inline int 272partition_is_global (tree_live_info_p live, int p) 273{ 274 gcc_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 282static inline bitmap 283live_on_entry (tree_live_info_p live, basic_block bb) 284{ 285 gcc_assert (live->livein); 286 gcc_assert (bb != ENTRY_BLOCK_PTR); 287 gcc_assert (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 296static inline bitmap 297live_on_exit (tree_live_info_p live, basic_block bb) 298{ 299 gcc_assert (live->liveout); 300 gcc_assert (bb != ENTRY_BLOCK_PTR); 301 gcc_assert (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 309static inline var_map 310live_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 319static inline void 320live_merge_and_clear (tree_live_info_p live, int p1, int p2) 321{ 322 gcc_assert (live->livein[p1]); 323 gcc_assert (live->livein[p2]); 324 bitmap_ior_into (live->livein[p1], live->livein[p2]); 325 bitmap_zero (live->livein[p2]); 326} 327 328 329/* Mark partition P as live on entry to basic block BB in LIVE. */ 330 331static inline void 332make_live_on_entry (tree_live_info_p live, basic_block bb , int p) 333{ 334 bitmap_set_bit (live->livein[bb->index], p); 335 bitmap_set_bit (live->global, p); 336} 337 338 339/* From tree-ssa-coalesce.c */ 340extern var_map coalesce_ssa_name (void); 341 342 343/* From tree-ssa-ter.c */ 344extern bitmap find_replaceable_exprs (var_map); 345extern void dump_replaceable_exprs (FILE *, bitmap); 346 347 348#endif /* _TREE_SSA_LIVE_H */ 349