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 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, 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. */ 30typedef 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#define VAR_ANN_PARTITION(ann) (ann->partition) 53#define VAR_ANN_ROOT_INDEX(ann) (ann->root_index) 54 55#define NO_PARTITION -1 56 57/* Flags to pass to compact_var_map */ 58 59#define VARMAP_NORMAL 0 60#define VARMAP_NO_SINGLE_DEFS 1 61 62extern var_map init_var_map (int); 63extern void delete_var_map (var_map); 64extern void dump_var_map (FILE *, var_map); 65extern int var_union (var_map, tree, tree); 66extern void change_partition_var (var_map, tree, int); 67extern void compact_var_map (var_map, int); 68#ifdef ENABLE_CHECKING 69extern void register_ssa_partition_check (tree ssa_var); 70#endif 71 72static inline unsigned num_var_partitions (var_map); 73static inline tree var_to_partition_to_var (var_map, tree); 74static inline tree partition_to_var (var_map, int); 75static inline int var_to_partition (var_map, tree); 76static inline tree version_to_var (var_map, int); 77static inline int version_ref_count (var_map, tree); 78static inline void register_ssa_partition (var_map, tree, bool); 79 80#define SSA_VAR_MAP_REF_COUNT 0x01 81extern var_map create_ssa_var_map (int); 82 83/* Number of partitions in MAP. */ 84 85static inline unsigned 86num_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 94static inline int 95version_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 106static inline tree 107partition_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 119static 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 135static inline int 136var_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 162static inline tree 163var_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 178static inline void 179register_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 226typedef 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 245extern tree_live_info_p calculate_live_on_entry (var_map); 246extern void calculate_live_on_exit (tree_live_info_p); 247extern 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) 252extern void dump_live_info (FILE *, tree_live_info_p, int); 253 254static inline int partition_is_global (tree_live_info_p, int); 255static inline bitmap live_entry_blocks (tree_live_info_p, int); 256static inline bitmap live_on_exit (tree_live_info_p, basic_block); 257static inline var_map live_var_map (tree_live_info_p); 258static inline void live_merge_and_clear (tree_live_info_p, int, int); 259static 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 264static inline int 265partition_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 275static inline bitmap 276live_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 286static inline bitmap 287live_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 299static inline var_map 300live_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 309static inline void 310live_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 319static inline void 320make_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 339typedef struct tree_partition_associator_d 340{ 341 VEC(tree,heap) *trees; 342 VEC(int,heap) *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 353static inline tree tpa_tree (tpa_p, int); 354static inline int tpa_first_partition (tpa_p, int); 355static inline int tpa_next_partition (tpa_p, int); 356static inline int tpa_num_trees (tpa_p); 357static inline int tpa_find_tree (tpa_p, int); 358static inline void tpa_decompact (tpa_p); 359extern void tpa_delete (tpa_p); 360extern void tpa_dump (FILE *, tpa_p); 361extern void tpa_remove_partition (tpa_p, int, int); 362extern int tpa_compact (tpa_p); 363 364 365/* Return the number of distinct tree nodes in TPA. */ 366 367static inline int 368tpa_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 376static inline tree 377tpa_tree (tpa_p tpa, int i) 378{ 379 return VEC_index (tree, tpa->trees, i); 380} 381 382 383/* Return the first partition associated with tree list I in TPA. */ 384 385static inline int 386tpa_first_partition (tpa_p tpa, int i) 387{ 388 return VEC_index (int, tpa->first_partition, i); 389} 390 391 392/* Return the next partition after partition I in TPA's list. */ 393 394static inline int 395tpa_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 404static inline int 405tpa_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 424static inline void 425tpa_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 complementary 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 442typedef tpa_p root_var_p; 443 444static inline tree root_var (root_var_p, int); 445static inline int root_var_first_partition (root_var_p, int); 446static inline int root_var_next_partition (root_var_p, int); 447static inline int root_var_num (root_var_p); 448static inline void root_var_dump (FILE *, root_var_p); 449static inline void root_var_remove_partition (root_var_p, int, int); 450static inline void root_var_delete (root_var_p); 451static inline int root_var_find (root_var_p, int); 452static inline int root_var_compact (root_var_p); 453static inline void root_var_decompact (tpa_p); 454 455extern 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 464static inline int 465root_var_num (root_var_p rv) 466{ 467 return tpa_num_trees (rv); 468} 469 470 471/* Return root variable I from RV. */ 472 473static inline tree 474root_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 482static inline int 483root_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 491static inline int 492root_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 500static inline void 501root_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 511static inline void 512root_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 520static inline void 521root_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 529static inline int 530root_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 538static inline int 539root_var_compact (root_var_p rv) 540{ 541 return tpa_compact (rv); 542} 543 544 545/* Expose the single element lists in RV. */ 546 547static inline void 548root_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 558typedef tpa_p type_var_p; 559 560static inline tree type_var (type_var_p, int); 561static inline int type_var_first_partition (type_var_p, int); 562static inline int type_var_next_partition (type_var_p, int); 563static inline int type_var_num (type_var_p); 564static inline void type_var_dump (FILE *, type_var_p); 565static inline void type_var_remove_partition (type_var_p, int, int); 566static inline void type_var_delete (type_var_p); 567static inline int type_var_find (type_var_p, int); 568static inline int type_var_compact (type_var_p); 569static inline void type_var_decompact (type_var_p); 570 571extern 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 579static inline int 580type_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 588static inline tree 589type_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 597static inline int 598type_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 606static inline int 607type_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 615static inline void 616type_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 626static inline void 627type_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 635static inline void 636type_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 644static inline int 645type_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 653static inline int 654type_var_compact (type_var_p tv) 655{ 656 return tpa_compact (tv); 657} 658 659 660/* Expose single element lists in TV. */ 661 662static inline void 663type_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 676typedef 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 695typedef struct coalesce_list_d 696{ 697 var_map map; 698 partition_pair_p *list; 699 bool add_mode; 700} *coalesce_list_p; 701 702extern coalesce_list_p create_coalesce_list (var_map); 703extern void add_coalesce (coalesce_list_p, int, int, int); 704extern int coalesce_cost (int, bool, bool); 705extern void sort_coalesce_list (coalesce_list_p); 706extern void dump_coalesce_list (FILE *, coalesce_list_p); 707extern void delete_coalesce_list (coalesce_list_p); 708 709#define NO_BEST_COALESCE -1 710 711extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p, 712 coalesce_list_p); 713extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, 714 coalesce_list_p cl, FILE *); 715 716 717#endif /* _TREE_SSA_LIVE_H */ 718