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 /* Used to create the variable mapping when we go out of SSA form.  */
  30 typedef struct _var_map
  31 {
  32   /* The partition of all variables.  */
  33   partition var_partition;
  34
  35   /* Vector for compacting partitions.  */
  36   int *partition_to_compact;
  37   int *compact_to_partition;
  38
  39   /* Mapping of partition numbers to vars.  */
  40   tree *partition_to_var;
  41
  42   /* Current number of partitions.  */
  43   unsigned int num_partitions;
  44
  45   /* Original partition size.  */
  46   unsigned int partition_size;
  47 } *var_map;
  48
  49 #define VAR_ANN_PARTITION(ann) (ann->partition)
  50 #define VAR_ANN_ROOT_INDEX(ann) (ann->root_index)
  51
  52 #define NO_PARTITION            -1
  53
  54 /* Flags to pass to compact_var_map  */
  55
  56 #define VARMAP_NORMAL           0
  57 #define VARMAP_NO_SINGLE_DEFS   1
  58
  59 extern var_map init_var_map (int);
  60 extern void delete_var_map (var_map);
  61 extern void dump_var_map (FILE *, var_map);
  62 extern int var_union (var_map, tree, tree);
  63 extern void change_partition_var (var_map, tree, int);
  64 extern void compact_var_map (var_map, int);
  65 #ifdef ENABLE_CHECKING
  66 extern void register_ssa_partition_check (tree ssa_var);
  67 #endif
  68
  69 static inline unsigned num_var_partitions (var_map);
  70 static inline tree var_to_partition_to_var (var_map, tree);
  71 static inline tree partition_to_var (var_map, int);
  72 static inline int var_to_partition (var_map, tree);
  73 static inline tree version_to_var (var_map, int);
  74 static inline void register_ssa_partition (var_map, tree);
  75
  76 extern var_map create_ssa_var_map (void);
  77
  78 /* Number of partitions in MAP.  */
  79
  80 static inline unsigned
  81 num_var_partitions (var_map map)
  82 {
  83   return map->num_partitions;
  84 }
  85
  86
  87 /* Given partition index I from MAP, return the variable which represents that
  88    partition.  */
  89
  90 static inline tree
  91 partition_to_var (var_map map, int i)
  92 {
  93   if (map->compact_to_partition)
  94     i = map->compact_to_partition[i];
  95   i = partition_find (map->var_partition, i);
  96   return map->partition_to_var[i];
  97 }
  98
  99
 100 /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
 101    is associated with.  Otherwise return NULL.  */
 102
 103 static inline tree version_to_var (var_map map, int version)
 104 {
 105   int part;
 106   part = partition_find (map->var_partition, version);
 107   if (map->partition_to_compact)
 108     part = map->partition_to_compact[part];
 109   if (part == NO_PARTITION)
 110     return NULL_TREE;
 111
 112   return partition_to_var (map, part);
 113 }
 114
 115
 116 /* Given VAR, return the partition number in MAP which contains it.
 117    NO_PARTITION is returned if it's not in any partition.  */
 118
 119 static inline int
 120 var_to_partition (var_map map, tree var)
 121 {
 122   var_ann_t ann;
 123   int part;
 124
 125   if (TREE_CODE (var) == SSA_NAME)
 126     {
 127       part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
 128       if (map->partition_to_compact)
 129         part = map->partition_to_compact[part];
 130     }
 131   else
 132     {
 133       ann = var_ann (var);
 134       if (ann && ann->out_of_ssa_tag)
 135         part = VAR_ANN_PARTITION (ann);
 136       else
 137         part = NO_PARTITION;
 138     }
 139   return part;
 140 }
 141
 142
 143 /* Given VAR, return the variable which represents the entire partition
 144    it is a member of in MAP.  NULL is returned if it is not in a partition.  */
 145
 146 static inline tree
 147 var_to_partition_to_var (var_map map, tree var)
 148 {
 149   int part;
 150
 151   part = var_to_partition (map, var);
 152   if (part == NO_PARTITION)
 153     return NULL_TREE;
 154   return partition_to_var (map, part);
 155 }
 156
 157
 158 /* This routine registers a partition for SSA_VAR with MAP.  IS_USE is used
 159    to count references.  Any unregistered partitions may be compacted out
 160    later.  */
 161
 162 static inline void
 163 register_ssa_partition (var_map map, tree ssa_var)
 164 {
 165   int version;
 166
 167 #if defined ENABLE_CHECKING
 168   register_ssa_partition_check (ssa_var);
 169 #endif
 170
 171   version = SSA_NAME_VERSION (ssa_var);
 172   if (map->partition_to_var[version] == NULL_TREE)
 173     map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
 174 }
 175
 176
 177 /*  ---------------- live on entry/exit info ------------------------------
 178
 179     This structure is used to represent live range information on SSA based
 180     trees. A partition map must be provided, and based on the active partitions,
 181     live-on-entry information and live-on-exit information can be calculated.
 182     As well, partitions are marked as to whether they are global (live
 183     outside the basic block they are defined in).
 184
 185     The live-on-entry information is per variable. It provide a bitmap for
 186     each variable which has a bit set for each basic block that the variable
 187     is live on entry to that block.
 188
 189     The live-on-exit information is per block. It provides a bitmap for each
 190     block indicating which partitions are live on exit from the block.
 191
 192     For the purposes of this implementation, we treat the elements of a PHI
 193     as follows:
 194
 195        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
 196        originate. They are *NOT* considered live on entry to the block
 197        containing the PHI node.
 198
 199        The Def of a PHI node is *not* considered live on entry to the block.
 200        It is considered to be "define early" in the block. Picture it as each
 201        block having a stmt (or block-preheader) before the first real stmt in
 202        the block which defines all the variables that are defined by PHIs.
 203
 204     -----------------------------------------------------------------------  */
 205
 206
 207 typedef struct tree_live_info_d
 208 {
 209   /* Var map this relates to.  */
 210   var_map map;
 211
 212   /* Bitmap indicating which partitions are global.  */
 213   bitmap global;
 214
 215   /* Bitmap of live on entry blocks for partition elements.  */
 216   bitmap *livein;
 217
 218   /* Number of basic blocks when live on exit calculated.  */
 219   int num_blocks;
 220
 221   /* Bitmap of what variables are live on exit for a basic blocks.  */
 222   bitmap *liveout;
 223 } *tree_live_info_p;
 224
 225
 226 extern tree_live_info_p calculate_live_on_entry (var_map);
 227 extern void calculate_live_on_exit (tree_live_info_p);
 228 extern void delete_tree_live_info (tree_live_info_p);
 229
 230 #define LIVEDUMP_ENTRY  0x01
 231 #define LIVEDUMP_EXIT   0x02
 232 #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 233 extern void dump_live_info (FILE *, tree_live_info_p, int);
 234
 235 static inline int partition_is_global (tree_live_info_p, int);
 236 static inline bitmap live_entry_blocks (tree_live_info_p, int);
 237 static inline bitmap live_on_exit (tree_live_info_p, basic_block);
 238 static inline var_map live_var_map (tree_live_info_p);
 239 static inline void live_merge_and_clear (tree_live_info_p, int, int);
 240 static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
 241
 242
 243 /*  Return TRUE if P is marked as a global in LIVE.  */
 244
 245 static inline int
 246 partition_is_global (tree_live_info_p live, int p)
 247 {
 248   gcc_assert (live->global);
 249   return bitmap_bit_p (live->global, p);
 250 }
 251
 252
 253 /* Return the bitmap from LIVE representing the live on entry blocks for
 254    partition P.  */
 255
 256 static inline bitmap
 257 live_entry_blocks (tree_live_info_p live, int p)
 258 {
 259   gcc_assert (live->livein);
 260   return live->livein[p];
 261 }
 262
 263
 264 /* Return the bitmap from LIVE representing the live on exit partitions from
 265    block BB.  */
 266
 267 static inline bitmap
 268 live_on_exit (tree_live_info_p live, basic_block bb)
 269 {
 270   gcc_assert (live->liveout);
 271   gcc_assert (bb != ENTRY_BLOCK_PTR);
 272   gcc_assert (bb != EXIT_BLOCK_PTR);
 273
 274   return live->liveout[bb->index];
 275 }
 276
 277
 278 /* Return the partition map which the information in LIVE utilizes.  */
 279
 280 static inline var_map
 281 live_var_map (tree_live_info_p live)
 282 {
 283   return live->map;
 284 }
 285
 286
 287 /* Merge the live on entry information in LIVE for partitions P1 and P2. Place
 288    the result into P1.  Clear P2.  */
 289
 290 static inline void
 291 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 292 {
 293   bitmap_ior_into (live->livein[p1], live->livein[p2]);
 294   bitmap_zero (live->livein[p2]);
 295 }
 296
 297
 298 /* Mark partition P as live on entry to basic block BB in LIVE.  */
 299
 300 static inline void
 301 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 302 {
 303   bitmap_set_bit (live->livein[p], bb->index);
 304   bitmap_set_bit (live->global, p);
 305 }
 306
 307
 308 /* A tree_partition_associator (TPA)object is a base structure which allows
 309    partitions to be associated with a tree object.
 310
 311    A varray of tree elements represent each distinct tree item.
 312    A parallel int array represents the first partition number associated with
 313    the tree.
 314    This partition number is then used as in index into the next_partition
 315    array, which returns the index of the next partition which is associated
 316    with the tree. TPA_NONE indicates the end of the list.
 317    A varray paralleling the partition list 'partition_to_tree_map' is used
 318    to indicate which tree index the partition is in.  */
 319
 320 typedef struct tree_partition_associator_d
 321 {
 322   VEC(tree,heap) *trees;
 323   VEC(int,heap) *first_partition;
 324   int *next_partition;
 325   int *partition_to_tree_map;
 326   int num_trees;
 327   int uncompressed_num;
 328   var_map map;
 329 } *tpa_p;
 330
 331 /* Value returned when there are no more partitions associated with a tree.  */
 332 #define TPA_NONE                -1
 333
 334 static inline tree tpa_tree (tpa_p, int);
 335 static inline int tpa_first_partition (tpa_p, int);
 336 static inline int tpa_next_partition (tpa_p, int);
 337 static inline int tpa_num_trees (tpa_p);
 338 static inline int tpa_find_tree (tpa_p, int);
 339 static inline void tpa_decompact (tpa_p);
 340 extern void tpa_delete (tpa_p);
 341 extern void tpa_dump (FILE *, tpa_p);
 342 extern void tpa_remove_partition (tpa_p, int, int);
 343 extern int tpa_compact (tpa_p);
 344
 345
 346 /* Return the number of distinct tree nodes in TPA.  */
 347
 348 static inline int
 349 tpa_num_trees (tpa_p tpa)
 350 {
 351   return tpa->num_trees;
 352 }
 353
 354
 355 /* Return the tree node for index I in TPA.  */
 356
 357 static inline tree
 358 tpa_tree (tpa_p tpa, int i)
 359 {
 360   return VEC_index (tree, tpa->trees, i);
 361 }
 362
 363
 364 /* Return the first partition associated with tree list I in TPA.  */
 365
 366 static inline int
 367 tpa_first_partition (tpa_p tpa, int i)
 368 {
 369   return VEC_index (int, tpa->first_partition, i);
 370 }
 371
 372
 373 /* Return the next partition after partition I in TPA's list.  */
 374
 375 static inline int
 376 tpa_next_partition (tpa_p tpa, int i)
 377 {
 378   return tpa->next_partition[i];
 379 }
 380
 381
 382 /* Return the tree index from TPA whose list contains partition I.
 383    TPA_NONE is returned if I is not associated with any list.  */
 384
 385 static inline int
 386 tpa_find_tree (tpa_p tpa, int i)
 387 {
 388   int index;
 389
 390   index = tpa->partition_to_tree_map[i];
 391   /* When compressed, any index higher than the number of tree elements is
 392      a compressed element, so return TPA_NONE.  */
 393   if (index != TPA_NONE && index >= tpa_num_trees (tpa))
 394     {
 395       gcc_assert (tpa->uncompressed_num != -1);
 396       index = TPA_NONE;
 397     }
 398
 399   return index;
 400 }
 401
 402
 403 /* This function removes any compaction which was performed on TPA.  */
 404
 405 static inline void
 406 tpa_decompact(tpa_p tpa)
 407 {
 408   gcc_assert (tpa->uncompressed_num != -1);
 409   tpa->num_trees = tpa->uncompressed_num;
 410 }
 411
 412
 413 /* Once a var_map has been created and compressed, a complementary root_var
 414    object can be built.  This creates a list of all the root variables from
 415    which ssa version names are derived.  Each root variable has a list of
 416    which partitions are versions of that root.
 417
 418    This is implemented using the tree_partition_associator.
 419
 420    The tree vector is used to represent the root variable.
 421    The list of partitions represent SSA versions of the root variable.  */
 422
 423 typedef tpa_p root_var_p;
 424
 425 static inline tree root_var (root_var_p, int);
 426 static inline int root_var_first_partition (root_var_p, int);
 427 static inline int root_var_next_partition (root_var_p, int);
 428 static inline int root_var_num (root_var_p);
 429 static inline void root_var_dump (FILE *, root_var_p);
 430 static inline void root_var_remove_partition (root_var_p, int, int);
 431 static inline void root_var_delete (root_var_p);
 432 static inline int root_var_find (root_var_p, int);
 433 static inline int root_var_compact (root_var_p);
 434 static inline void root_var_decompact (tpa_p);
 435
 436 extern root_var_p root_var_init (var_map);
 437
 438 /* Value returned when there are no more partitions associated with a root
 439    variable.  */
 440 #define ROOT_VAR_NONE           TPA_NONE
 441
 442
 443 /* Return the number of distinct root variables in RV.  */
 444
 445 static inline int
 446 root_var_num (root_var_p rv)
 447 {
 448   return tpa_num_trees (rv);
 449 }
 450
 451
 452 /* Return root variable I from RV.  */
 453
 454 static inline tree
 455 root_var (root_var_p rv, int i)
 456 {
 457   return tpa_tree (rv, i);
 458 }
 459
 460
 461 /* Return the first partition in RV belonging to root variable list I.  */
 462
 463 static inline int
 464 root_var_first_partition (root_var_p rv, int i)
 465 {
 466   return tpa_first_partition (rv, i);
 467 }
 468
 469
 470 /* Return the next partition after partition I in a root list from RV.  */
 471
 472 static inline int
 473 root_var_next_partition (root_var_p rv, int i)
 474 {
 475   return tpa_next_partition (rv, i);
 476 }
 477
 478
 479 /* Send debug info for root_var list RV to file F.  */
 480
 481 static inline void
 482 root_var_dump (FILE *f, root_var_p rv)
 483 {
 484   fprintf (f, "\nRoot Var dump\n");
 485   tpa_dump (f, rv);
 486   fprintf (f, "\n");
 487 }
 488
 489
 490 /* Destroy root_var object RV.  */
 491
 492 static inline void
 493 root_var_delete (root_var_p rv)
 494 {
 495   tpa_delete (rv);
 496 }
 497
 498
 499 /* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV.  */
 500
 501 static inline void
 502 root_var_remove_partition (root_var_p rv, int root_index, int partition_index)
 503 {
 504   tpa_remove_partition (rv, root_index, partition_index);
 505 }
 506
 507
 508 /* Return the root_var list index for partition I in RV.  */
 509
 510 static inline int
 511 root_var_find (root_var_p rv, int i)
 512 {
 513   return tpa_find_tree (rv, i);
 514 }
 515
 516
 517 /* Hide single element lists in RV.  */
 518
 519 static inline int
 520 root_var_compact (root_var_p rv)
 521 {
 522   return tpa_compact (rv);
 523 }
 524
 525
 526 /* Expose the single element lists in RV.  */
 527
 528 static inline void
 529 root_var_decompact (root_var_p rv)
 530 {
 531   tpa_decompact (rv);
 532 }
 533
 534
 535 /* This set of routines implements a coalesce_list. This is an object which
 536    is used to track pairs of partitions which are desirable to coalesce
 537    together at some point.  Costs are associated with each pair, and when
 538    all desired information has been collected, the object can be used to
 539    order the pairs for processing.  */
 540
 541 /* This structure defines a pair entry.  */
 542
 543 typedef struct partition_pair
 544 {
 545   int first_partition;
 546   int second_partition;
 547   int cost;
 548 } * partition_pair_p;
 549
 550 extern unsigned int partition_pair_map_hash (const void *);
 551 extern int partition_pair_map_eq (const void *, const void *);
 552
 553 /* This structure maintains the list of coalesce pairs.  */
 554
 555 typedef struct coalesce_list_d
 556 {
 557   var_map map;
 558   htab_t list;
 559   partition_pair_p *sorted;
 560   int num_sorted;
 561   bool add_mode;
 562 } *coalesce_list_p;
 563
 564 extern coalesce_list_p create_coalesce_list (var_map);
 565 extern void add_coalesce (coalesce_list_p, int, int, int);
 566 extern int coalesce_cost (int, bool, bool);
 567 extern void sort_coalesce_list (coalesce_list_p);
 568 extern void dump_coalesce_list (FILE *, coalesce_list_p);
 569 extern void delete_coalesce_list (coalesce_list_p);
 570
 571 #define NO_BEST_COALESCE        -1
 572
 573 extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
 574                                                  coalesce_list_p);
 575 extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
 576                                   coalesce_list_p cl, FILE *);
 577
 578
 579 #endif /* _TREE_SSA_LIVE_H  */