gcc/tree-ssa-live.h

   1 /* Routines for liveness in SSA trees.
   2    Copyright (C) 2003, 2004, 2005, 2007 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 #include "vecprim.h"
  27
  28
  29
  30 /* Used to create the variable mapping when we go out of SSA form.
  31
  32    Mapping from an ssa_name to a partition number is maintained, as well as
  33    partition number to back to ssa_name. A partition can also be represented
  34    by a non-ssa_name variable.  This allows ssa_names and their partition to
  35    be coalesced with live on entry compiler variables, as well as eventually
  36    having real compiler variables assigned to each partition as part of the
  37    final stage of going of of ssa.
  38
  39    Non-ssa_names maintain their partition index in the variable annotation.
  40
  41    This data structure also supports "views", which work on a subset of all
  42    partitions.  This allows the coalescer to decide what partitions are
  43    interesting to it, and only work with those partitions.  Whenever the view
  44    is changed, the partition numbers change, but none of the partition groupings
  45    change. (ie, it is truly a view since it doesn't change anything)
  46
  47    The final component of the data structure is the basevar map.  This provides
  48    a list of all the different base variables which occur in a partition view,
  49    and a unique index for each one. Routines are provided to quickly produce
  50    the base variable of a partition.
  51
  52    Note that members of a partition MUST all have the same base variable.  */
  53
  54 typedef struct _var_map
  55 {
  56   /* The partition manager of all variables.  */
  57   partition var_partition;
  58
  59   /* Vector for managing partitions views.  */
  60   int *partition_to_view;
  61   int *view_to_partition;
  62
  63   /* Mapping of partition numbers to variables.  */
  64   tree *partition_to_var;
  65
  66   /* Current number of partitions in var_map based on the current view.  */
  67   unsigned int num_partitions;
  68
  69   /* Original full partition size.  */
  70   unsigned int partition_size;
  71
  72   /* Number of base variables in the base var list.  */
  73   int num_basevars;
  74
  75   /* Map of partitions numbers to base variable table indexes.  */
  76   int *partition_to_base_index;
  77
  78   /* Table of base variable's.  */
  79   VEC (tree, heap) *basevars;
  80 } *var_map;
  81
  82
  83 /* Partition number of a  non ssa-name variable.  */
  84 #define VAR_ANN_PARTITION(ann) (ann->partition)
  85 /* Index iot the basevar table of a non ssa-name variable.  */
  86 #define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
  87
  88
  89 /* Value used to represent no partition number.  */
  90 #define NO_PARTITION            -1
  91
  92 extern var_map init_var_map (int);
  93 extern void delete_var_map (var_map);
  94 extern void dump_var_map (FILE *, var_map);
  95 extern int var_union (var_map, tree, tree);
  96 extern void change_partition_var (var_map, tree, int);
  97 extern void partition_view_normal (var_map, bool);
  98 extern void partition_view_bitmap (var_map, bitmap, bool);
  99 #ifdef ENABLE_CHECKING
 100 extern void register_ssa_partition_check (tree ssa_var);
 101 #endif
 102
 103
 104 /* Return number of partitions in MAP.  */
 105
 106 static inline unsigned
 107 num_var_partitions (var_map map)
 108 {
 109   return map->num_partitions;
 110 }
 111
 112
 113 /* Given partition index I from MAP, return the variable which represents that
 114    partition.  */
 115
 116 static inline tree
 117 partition_to_var (var_map map, int i)
 118 {
 119   if (map->view_to_partition)
 120     i = map->view_to_partition[i];
 121   i = partition_find (map->var_partition, i);
 122   return map->partition_to_var[i];
 123 }
 124
 125
 126 /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
 127    is associated with.  Otherwise return NULL.  */
 128
 129 static inline tree
 130 version_to_var (var_map map, int version)
 131 {
 132   int part;
 133   part = partition_find (map->var_partition, version);
 134   if (map->partition_to_view)
 135     part = map->partition_to_view[part];
 136   if (part == NO_PARTITION)
 137     return NULL_TREE;
 138
 139   return partition_to_var (map, part);
 140 }
 141
 142
 143 /* Given VAR, return the partition number in MAP which contains it.
 144    NO_PARTITION is returned if it's not in any partition.  */
 145
 146 static inline int
 147 var_to_partition (var_map map, tree var)
 148 {
 149   var_ann_t ann;
 150   int part;
 151
 152   if (TREE_CODE (var) == SSA_NAME)
 153     {
 154       part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
 155       if (map->partition_to_view)
 156         part = map->partition_to_view[part];
 157     }
 158   else
 159     {
 160       ann = var_ann (var);
 161       if (ann && ann->out_of_ssa_tag)
 162         part = VAR_ANN_PARTITION (ann);
 163       else
 164         part = NO_PARTITION;
 165     }
 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 static 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 static inline int
 188 basevar_index (var_map map, int partition)
 189 {
 190   gcc_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 static inline int
 199 num_basevars (var_map map)
 200 {
 201   return map->num_basevars;
 202 }
 203
 204
 205
 206 /* This routine registers a partition for SSA_VAR with MAP.  Any unregistered
 207    partitions may be filtered out by a view later.  */
 208
 209 static inline void
 210 register_ssa_partition (var_map map, tree ssa_var)
 211 {
 212   int version;
 213
 214 #if defined ENABLE_CHECKING
 215   register_ssa_partition_check (ssa_var);
 216 #endif
 217
 218   version = SSA_NAME_VERSION (ssa_var);
 219   if (map->partition_to_var[version] == NULL_TREE)
 220     map->partition_to_var[version] = ssa_var;
 221 }
 222
 223
 224 /*  ---------------- live on entry/exit info ------------------------------
 225
 226     This structure is used to represent live range information on SSA based
 227     trees. A partition map must be provided, and based on the active partitions,
 228     live-on-entry information and live-on-exit information can be calculated.
 229     As well, partitions are marked as to whether they are global (live
 230     outside the basic block they are defined in).
 231
 232     The live-on-entry information is per block.  It provide a bitmap for
 233     each block which has a bit set for each partition that is live on entry to
 234     that block.
 235
 236     The live-on-exit information is per block.  It provides a bitmap for each
 237     block indicating which partitions are live on exit from the block.
 238
 239     For the purposes of this implementation, we treat the elements of a PHI
 240     as follows:
 241
 242        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
 243        originate. They are *NOT* considered live on entry to the block
 244        containing the PHI node.
 245
 246        The Def of a PHI node is *not* considered live on entry to the block.
 247        It is considered to be "define early" in the block. Picture it as each
 248        block having a stmt (or block-preheader) before the first real stmt in
 249        the block which defines all the variables that are defined by PHIs.
 250
 251     -----------------------------------------------------------------------  */
 252
 253
 254 typedef struct tree_live_info_d
 255 {
 256   /* Var map this relates to.  */
 257   var_map map;
 258
 259   /* Bitmap indicating which partitions are global.  */
 260   bitmap global;
 261
 262   /* Bitmap of live on entry blocks for partition elements.  */
 263   bitmap *livein;
 264
 265   /* Number of basic blocks when live on exit calculated.  */
 266   int num_blocks;
 267
 268   /* Vector used when creating live ranges as a visited stack.  */
 269   int *work_stack;
 270
 271   /* Top of workstack.  */
 272   int *stack_top;
 273
 274   /* Bitmap of what variables are live on exit for a basic blocks.  */
 275   bitmap *liveout;
 276 } *tree_live_info_p;
 277
 278
 279 extern tree_live_info_p calculate_live_ranges (var_map);
 280 extern void calculate_live_on_exit (tree_live_info_p);
 281 extern void delete_tree_live_info (tree_live_info_p);
 282
 283 #define LIVEDUMP_ENTRY  0x01
 284 #define LIVEDUMP_EXIT   0x02
 285 #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 286 extern void dump_live_info (FILE *, tree_live_info_p, int);
 287
 288
 289 /*  Return TRUE if P is marked as a global in LIVE.  */
 290
 291 static inline int
 292 partition_is_global (tree_live_info_p live, int p)
 293 {
 294   gcc_assert (live->global);
 295   return bitmap_bit_p (live->global, p);
 296 }
 297
 298
 299 /* Return the bitmap from LIVE representing the live on entry blocks for
 300    partition P.  */
 301
 302 static inline bitmap
 303 live_on_entry (tree_live_info_p live, basic_block bb)
 304 {
 305   gcc_assert (live->livein);
 306   gcc_assert (bb != ENTRY_BLOCK_PTR);
 307   gcc_assert (bb != EXIT_BLOCK_PTR);
 308
 309   return live->livein[bb->index];
 310 }
 311
 312
 313 /* Return the bitmap from LIVE representing the live on exit partitions from
 314    block BB.  */
 315
 316 static inline bitmap
 317 live_on_exit (tree_live_info_p live, basic_block bb)
 318 {
 319   gcc_assert (live->liveout);
 320   gcc_assert (bb != ENTRY_BLOCK_PTR);
 321   gcc_assert (bb != EXIT_BLOCK_PTR);
 322
 323   return live->liveout[bb->index];
 324 }
 325
 326
 327 /* Return the partition map which the information in LIVE utilizes.  */
 328
 329 static inline var_map
 330 live_var_map (tree_live_info_p live)
 331 {
 332   return live->map;
 333 }
 334
 335
 336 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
 337    the result into P1.  Clear P2.  */
 338
 339 static inline void
 340 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 341 {
 342   gcc_assert (live->livein[p1]);
 343   gcc_assert (live->livein[p2]);
 344   bitmap_ior_into (live->livein[p1], live->livein[p2]);
 345   bitmap_zero (live->livein[p2]);
 346 }
 347
 348
 349 /* Mark partition P as live on entry to basic block BB in LIVE.  */
 350
 351 static inline void
 352 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 353 {
 354   bitmap_set_bit (live->livein[bb->index], p);
 355   bitmap_set_bit (live->global, p);
 356 }
 357
 358
 359 /* From tree-ssa-coalesce.c  */
 360 extern var_map coalesce_ssa_name (void);
 361
 362
 363 /* From tree-ssa-ter.c  */
 364 extern tree *find_replaceable_exprs (var_map);
 365 extern void dump_replaceable_exprs (FILE *, tree *);
 366
 367
 368 #endif /* _TREE_SSA_LIVE_H  */