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