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