gcc/tree-ssa-live.h

   1 /* Routines for liveness in SSA trees.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Andrew MacLeod  <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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   /* Current number of partitions in var_map based on the current view.  */
  65   unsigned int num_partitions;
  66
  67   /* Original full partition size.  */
  68   unsigned int partition_size;
  69
  70   /* Number of base variables in the base var list.  */
  71   int num_basevars;
  72
  73   /* Map of partitions numbers to base variable table indexes.  */
  74   int *partition_to_base_index;
  75
  76   /* Table of base variable's.  */
  77   VEC (tree, heap) *basevars;
  78 } *var_map;
  79
  80
  81 /* Index to the basevar table of a non ssa-name variable.  */
  82 #define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
  83
  84
  85 /* Value used to represent no partition number.  */
  86 #define NO_PARTITION            -1
  87
  88 extern var_map init_var_map (int);
  89 extern void delete_var_map (var_map);
  90 extern void dump_var_map (FILE *, var_map);
  91 extern int var_union (var_map, tree, tree);
  92 extern void partition_view_normal (var_map, bool);
  93 extern void partition_view_bitmap (var_map, bitmap, bool);
  94 #ifdef ENABLE_CHECKING
  95 extern void register_ssa_partition_check (tree ssa_var);
  96 #endif
  97
  98
  99 /* Return number of partitions in MAP.  */
 100
 101 static inline unsigned
 102 num_var_partitions (var_map map)
 103 {
 104   return map->num_partitions;
 105 }
 106
 107
 108 /* Given partition index I from MAP, return the variable which represents that
 109    partition.  */
 110
 111 static inline tree
 112 partition_to_var (var_map map, int i)
 113 {
 114   tree name;
 115   if (map->view_to_partition)
 116     i = map->view_to_partition[i];
 117   i = partition_find (map->var_partition, i);
 118   name = ssa_name (i);
 119   return name;
 120 }
 121
 122
 123 /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
 124    is associated with.  Otherwise return NULL.  */
 125
 126 static inline tree
 127 version_to_var (var_map map, int version)
 128 {
 129   int part;
 130   part = partition_find (map->var_partition, version);
 131   if (map->partition_to_view)
 132     part = map->partition_to_view[part];
 133   if (part == NO_PARTITION)
 134     return NULL_TREE;
 135
 136   return partition_to_var (map, part);
 137 }
 138
 139
 140 /* Given VAR, return the partition number in MAP which contains it.
 141    NO_PARTITION is returned if it's not in any partition.  */
 142
 143 static inline int
 144 var_to_partition (var_map map, tree var)
 145 {
 146   int part;
 147
 148   part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
 149   if (map->partition_to_view)
 150     part = map->partition_to_view[part];
 151   return part;
 152 }
 153
 154
 155 /* Given VAR, return the variable which represents the entire partition
 156    it is a member of in MAP.  NULL is returned if it is not in a partition.  */
 157
 158 static inline tree
 159 var_to_partition_to_var (var_map map, tree var)
 160 {
 161   int part;
 162
 163   part = var_to_partition (map, var);
 164   if (part == NO_PARTITION)
 165     return NULL_TREE;
 166   return partition_to_var (map, part);
 167 }
 168
 169
 170 /* Return the index into the basevar table for PARTITION's base in MAP.  */
 171
 172 static inline int
 173 basevar_index (var_map map, int partition)
 174 {
 175   gcc_checking_assert (partition >= 0
 176                        && partition <= (int) num_var_partitions (map));
 177   return map->partition_to_base_index[partition];
 178 }
 179
 180
 181 /* Return the number of different base variables in MAP.  */
 182
 183 static inline int
 184 num_basevars (var_map map)
 185 {
 186   return map->num_basevars;
 187 }
 188
 189
 190
 191 /* This routine registers a partition for SSA_VAR with MAP.  Any unregistered
 192    partitions may be filtered out by a view later.  */
 193
 194 static inline void
 195 register_ssa_partition (var_map map ATTRIBUTE_UNUSED,
 196                         tree ssa_var ATTRIBUTE_UNUSED)
 197 {
 198 #if defined ENABLE_CHECKING
 199   register_ssa_partition_check (ssa_var);
 200 #endif
 201 }
 202
 203
 204 /*  ---------------- live on entry/exit info ------------------------------
 205
 206     This structure is used to represent live range information on SSA based
 207     trees. A partition map must be provided, and based on the active partitions,
 208     live-on-entry information and live-on-exit information can be calculated.
 209     As well, partitions are marked as to whether they are global (live
 210     outside the basic block they are defined in).
 211
 212     The live-on-entry information is per block.  It provide a bitmap for
 213     each block which has a bit set for each partition that is live on entry to
 214     that block.
 215
 216     The live-on-exit information is per block.  It provides a bitmap for each
 217     block indicating which partitions are live on exit from the block.
 218
 219     For the purposes of this implementation, we treat the elements of a PHI
 220     as follows:
 221
 222        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
 223        originate. They are *NOT* considered live on entry to the block
 224        containing the PHI node.
 225
 226        The Def of a PHI node is *not* considered live on entry to the block.
 227        It is considered to be "define early" in the block. Picture it as each
 228        block having a stmt (or block-preheader) before the first real stmt in
 229        the block which defines all the variables that are defined by PHIs.
 230
 231     -----------------------------------------------------------------------  */
 232
 233
 234 typedef struct tree_live_info_d
 235 {
 236   /* Var map this relates to.  */
 237   var_map map;
 238
 239   /* Bitmap indicating which partitions are global.  */
 240   bitmap global;
 241
 242   /* Bitmap of live on entry blocks for partition elements.  */
 243   bitmap *livein;
 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   /* Bitmap of what variables are live on exit for a basic blocks.  */
 255   bitmap *liveout;
 256 } *tree_live_info_p;
 257
 258
 259 extern tree_live_info_p calculate_live_ranges (var_map);
 260 extern void calculate_live_on_exit (tree_live_info_p);
 261 extern void delete_tree_live_info (tree_live_info_p);
 262
 263 #define LIVEDUMP_ENTRY  0x01
 264 #define LIVEDUMP_EXIT   0x02
 265 #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 266 extern void dump_live_info (FILE *, tree_live_info_p, int);
 267
 268
 269 /*  Return TRUE if P is marked as a global in LIVE.  */
 270
 271 static inline int
 272 partition_is_global (tree_live_info_p live, int p)
 273 {
 274   gcc_checking_assert (live->global);
 275   return bitmap_bit_p (live->global, p);
 276 }
 277
 278
 279 /* Return the bitmap from LIVE representing the live on entry blocks for
 280    partition P.  */
 281
 282 static inline bitmap
 283 live_on_entry (tree_live_info_p live, basic_block bb)
 284 {
 285   gcc_checking_assert (live->livein
 286                        && bb != ENTRY_BLOCK_PTR
 287                        && bb != EXIT_BLOCK_PTR);
 288
 289   return live->livein[bb->index];
 290 }
 291
 292
 293 /* Return the bitmap from LIVE representing the live on exit partitions from
 294    block BB.  */
 295
 296 static inline bitmap
 297 live_on_exit (tree_live_info_p live, basic_block bb)
 298 {
 299   gcc_checking_assert (live->liveout
 300                        && bb != ENTRY_BLOCK_PTR
 301                        && bb != EXIT_BLOCK_PTR);
 302
 303   return live->liveout[bb->index];
 304 }
 305
 306
 307 /* Return the partition map which the information in LIVE utilizes.  */
 308
 309 static inline var_map
 310 live_var_map (tree_live_info_p live)
 311 {
 312   return live->map;
 313 }
 314
 315
 316 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
 317    the result into P1.  Clear P2.  */
 318
 319 static inline void
 320 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 321 {
 322   gcc_checking_assert (live->livein[p1] && live->livein[p2]);
 323   bitmap_ior_into (live->livein[p1], live->livein[p2]);
 324   bitmap_zero (live->livein[p2]);
 325 }
 326
 327
 328 /* Mark partition P as live on entry to basic block BB in LIVE.  */
 329
 330 static inline void
 331 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 332 {
 333   bitmap_set_bit (live->livein[bb->index], p);
 334   bitmap_set_bit (live->global, p);
 335 }
 336
 337
 338 /* From tree-ssa-coalesce.c  */
 339 extern var_map coalesce_ssa_name (void);
 340
 341
 342 /* From tree-ssa-ter.c  */
 343 extern bitmap find_replaceable_exprs (var_map);
 344 extern void dump_replaceable_exprs (FILE *, bitmap);
 345
 346
 347 #endif /* _TREE_SSA_LIVE_H  */