gcc/tree-ssa-live.h

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