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