gcc/tree-ssa-live.h

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