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