gcc/tree-ssa-live.h

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