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