gcc/tree-ssa-live.h

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