gcc/tree-ssa-live.h

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