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