gcc/tree-ssa-live.h

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