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