gcc/tree-ssa-live.h

   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
   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 #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
  54 typedef 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
  87 extern var_map init_var_map (int);
  88 extern void delete_var_map (var_map);
  89 extern void dump_var_map (FILE *, var_map);
  90 extern int var_union (var_map, tree, tree);
  91 extern void partition_view_normal (var_map, bool);
  92 extern void partition_view_bitmap (var_map, bitmap, bool);
  93 #ifdef ENABLE_CHECKING
  94 extern void register_ssa_partition_check (tree ssa_var);
  95 #endif
  96
  97
  98 /* Return number of partitions in MAP.  */
  99
 100 static inline unsigned
 101 num_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
 110 static inline tree
 111 partition_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
 125 static inline tree
 126 version_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
 142 static inline int
 143 var_to_partition (var_map map, tree var)
 144 {
 145   int part;
 146
 147   part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
 148   if (map->partition_to_view)
 149     part = map->partition_to_view[part];
 150   return part;
 151 }
 152
 153
 154 /* Given VAR, return the variable which represents the entire partition
 155    it is a member of in MAP.  NULL is returned if it is not in a partition.  */
 156
 157 static inline tree
 158 var_to_partition_to_var (var_map map, tree var)
 159 {
 160   int part;
 161
 162   part = var_to_partition (map, var);
 163   if (part == NO_PARTITION)
 164     return NULL_TREE;
 165   return partition_to_var (map, part);
 166 }
 167
 168
 169 /* Return the index into the basevar table for PARTITION's base in MAP.  */
 170
 171 static inline int
 172 basevar_index (var_map map, int partition)
 173 {
 174   gcc_checking_assert (partition >= 0
 175                        && partition <= (int) num_var_partitions (map));
 176   return map->partition_to_base_index[partition];
 177 }
 178
 179
 180 /* Return the number of different base variables in MAP.  */
 181
 182 static inline int
 183 num_basevars (var_map map)
 184 {
 185   return map->num_basevars;
 186 }
 187
 188
 189
 190 /* This routine registers a partition for SSA_VAR with MAP.  Any unregistered
 191    partitions may be filtered out by a view later.  */
 192
 193 static inline void
 194 register_ssa_partition (var_map map ATTRIBUTE_UNUSED,
 195                         tree ssa_var ATTRIBUTE_UNUSED)
 196 {
 197 #if defined ENABLE_CHECKING
 198   register_ssa_partition_check (ssa_var);
 199 #endif
 200 }
 201
 202
 203 /*  ---------------- live on entry/exit info ------------------------------
 204
 205     This structure is used to represent live range information on SSA based
 206     trees. A partition map must be provided, and based on the active partitions,
 207     live-on-entry information and live-on-exit information can be calculated.
 208     As well, partitions are marked as to whether they are global (live
 209     outside the basic block they are defined in).
 210
 211     The live-on-entry information is per block.  It provide a bitmap for
 212     each block which has a bit set for each partition that is live on entry to
 213     that block.
 214
 215     The live-on-exit information is per block.  It provides a bitmap for each
 216     block indicating which partitions are live on exit from the block.
 217
 218     For the purposes of this implementation, we treat the elements of a PHI
 219     as follows:
 220
 221        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
 222        originate. They are *NOT* considered live on entry to the block
 223        containing the PHI node.
 224
 225        The Def of a PHI node is *not* considered live on entry to the block.
 226        It is considered to be "define early" in the block. Picture it as each
 227        block having a stmt (or block-preheader) before the first real stmt in
 228        the block which defines all the variables that are defined by PHIs.
 229
 230     -----------------------------------------------------------------------  */
 231
 232
 233 typedef struct tree_live_info_d
 234 {
 235   /* Var map this relates to.  */
 236   var_map map;
 237
 238   /* Bitmap indicating which partitions are global.  */
 239   bitmap global;
 240
 241   /* Bitmap of live on entry blocks for partition elements.  */
 242   bitmap *livein;
 243
 244   /* Number of basic blocks when live on exit calculated.  */
 245   int num_blocks;
 246
 247   /* Vector used when creating live ranges as a visited stack.  */
 248   int *work_stack;
 249
 250   /* Top of workstack.  */
 251   int *stack_top;
 252
 253   /* Bitmap of what variables are live on exit for a basic blocks.  */
 254   bitmap *liveout;
 255 } *tree_live_info_p;
 256
 257
 258 extern tree_live_info_p calculate_live_ranges (var_map);
 259 extern void calculate_live_on_exit (tree_live_info_p);
 260 extern void delete_tree_live_info (tree_live_info_p);
 261
 262 #define LIVEDUMP_ENTRY  0x01
 263 #define LIVEDUMP_EXIT   0x02
 264 #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 265 extern void dump_live_info (FILE *, tree_live_info_p, int);
 266
 267
 268 /*  Return TRUE if P is marked as a global in LIVE.  */
 269
 270 static inline int
 271 partition_is_global (tree_live_info_p live, int p)
 272 {
 273   gcc_checking_assert (live->global);
 274   return bitmap_bit_p (live->global, p);
 275 }
 276
 277
 278 /* Return the bitmap from LIVE representing the live on entry blocks for
 279    partition P.  */
 280
 281 static inline bitmap
 282 live_on_entry (tree_live_info_p live, basic_block bb)
 283 {
 284   gcc_checking_assert (live->livein
 285                        && bb != ENTRY_BLOCK_PTR
 286                        && bb != EXIT_BLOCK_PTR);
 287
 288   return live->livein[bb->index];
 289 }
 290
 291
 292 /* Return the bitmap from LIVE representing the live on exit partitions from
 293    block BB.  */
 294
 295 static inline bitmap
 296 live_on_exit (tree_live_info_p live, basic_block bb)
 297 {
 298   gcc_checking_assert (live->liveout
 299                        && bb != ENTRY_BLOCK_PTR
 300                        && bb != EXIT_BLOCK_PTR);
 301
 302   return live->liveout[bb->index];
 303 }
 304
 305
 306 /* Return the partition map which the information in LIVE utilizes.  */
 307
 308 static inline var_map
 309 live_var_map (tree_live_info_p live)
 310 {
 311   return live->map;
 312 }
 313
 314
 315 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
 316    the result into P1.  Clear P2.  */
 317
 318 static inline void
 319 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 320 {
 321   gcc_checking_assert (live->livein[p1] && live->livein[p2]);
 322   bitmap_ior_into (live->livein[p1], live->livein[p2]);
 323   bitmap_zero (live->livein[p2]);
 324 }
 325
 326
 327 /* Mark partition P as live on entry to basic block BB in LIVE.  */
 328
 329 static inline void
 330 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 331 {
 332   bitmap_set_bit (live->livein[bb->index], p);
 333   bitmap_set_bit (live->global, p);
 334 }
 335
 336
 337 /* From tree-ssa-coalesce.c  */
 338 extern var_map coalesce_ssa_name (void);
 339
 340
 341 /* From tree-ssa-ter.c  */
 342 extern bitmap find_replaceable_exprs (var_map);
 343 extern void dump_replaceable_exprs (FILE *, bitmap);
 344
 345
 346 #endif /* _TREE_SSA_LIVE_H  */