gcc/tree-ssa-live.h

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