gcc/tree-ssa-live.h

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