gcc/tree-ssa-live.h

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