1169689Skan/* Routines for liveness in SSA trees. 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Andrew MacLeod <amacleod@redhat.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan 23169689Skan#ifndef _TREE_SSA_LIVE_H 24169689Skan#define _TREE_SSA_LIVE_H 1 25169689Skan 26169689Skan#include "partition.h" 27169689Skan#include "vecprim.h" 28169689Skan 29169689Skan/* Used to create the variable mapping when we go out of SSA form. */ 30169689Skantypedef struct _var_map 31169689Skan{ 32169689Skan /* The partition of all variables. */ 33169689Skan partition var_partition; 34169689Skan 35169689Skan /* Vector for compacting partitions. */ 36169689Skan int *partition_to_compact; 37169689Skan int *compact_to_partition; 38169689Skan 39169689Skan /* Mapping of partition numbers to vars. */ 40169689Skan tree *partition_to_var; 41169689Skan 42169689Skan /* Current number of partitions. */ 43169689Skan unsigned int num_partitions; 44169689Skan 45169689Skan /* Original partition size. */ 46169689Skan unsigned int partition_size; 47169689Skan 48169689Skan /* Reference count, if required. */ 49169689Skan int *ref_count; 50169689Skan} *var_map; 51169689Skan 52169689Skan#define VAR_ANN_PARTITION(ann) (ann->partition) 53169689Skan#define VAR_ANN_ROOT_INDEX(ann) (ann->root_index) 54169689Skan 55169689Skan#define NO_PARTITION -1 56169689Skan 57169689Skan/* Flags to pass to compact_var_map */ 58169689Skan 59169689Skan#define VARMAP_NORMAL 0 60169689Skan#define VARMAP_NO_SINGLE_DEFS 1 61169689Skan 62169689Skanextern var_map init_var_map (int); 63169689Skanextern void delete_var_map (var_map); 64169689Skanextern void dump_var_map (FILE *, var_map); 65169689Skanextern int var_union (var_map, tree, tree); 66169689Skanextern void change_partition_var (var_map, tree, int); 67169689Skanextern void compact_var_map (var_map, int); 68169689Skan#ifdef ENABLE_CHECKING 69169689Skanextern void register_ssa_partition_check (tree ssa_var); 70169689Skan#endif 71169689Skan 72169689Skanstatic inline unsigned num_var_partitions (var_map); 73169689Skanstatic inline tree var_to_partition_to_var (var_map, tree); 74169689Skanstatic inline tree partition_to_var (var_map, int); 75169689Skanstatic inline int var_to_partition (var_map, tree); 76169689Skanstatic inline tree version_to_var (var_map, int); 77169689Skanstatic inline int version_ref_count (var_map, tree); 78169689Skanstatic inline void register_ssa_partition (var_map, tree, bool); 79169689Skan 80169689Skan#define SSA_VAR_MAP_REF_COUNT 0x01 81169689Skanextern var_map create_ssa_var_map (int); 82169689Skan 83169689Skan/* Number of partitions in MAP. */ 84169689Skan 85169689Skanstatic inline unsigned 86169689Skannum_var_partitions (var_map map) 87169689Skan{ 88169689Skan return map->num_partitions; 89169689Skan} 90169689Skan 91169689Skan 92169689Skan/* Return the reference count for SSA_VAR's partition in MAP. */ 93169689Skan 94169689Skanstatic inline int 95169689Skanversion_ref_count (var_map map, tree ssa_var) 96169689Skan{ 97169689Skan int version = SSA_NAME_VERSION (ssa_var); 98169689Skan gcc_assert (map->ref_count); 99169689Skan return map->ref_count[version]; 100169689Skan} 101169689Skan 102169689Skan 103169689Skan/* Given partition index I from MAP, return the variable which represents that 104169689Skan partition. */ 105169689Skan 106169689Skanstatic inline tree 107169689Skanpartition_to_var (var_map map, int i) 108169689Skan{ 109169689Skan if (map->compact_to_partition) 110169689Skan i = map->compact_to_partition[i]; 111169689Skan i = partition_find (map->var_partition, i); 112169689Skan return map->partition_to_var[i]; 113169689Skan} 114169689Skan 115169689Skan 116169689Skan/* Given ssa_name VERSION, if it has a partition in MAP, return the var it 117169689Skan is associated with. Otherwise return NULL. */ 118169689Skan 119169689Skanstatic inline tree version_to_var (var_map map, int version) 120169689Skan{ 121169689Skan int part; 122169689Skan part = partition_find (map->var_partition, version); 123169689Skan if (map->partition_to_compact) 124169689Skan part = map->partition_to_compact[part]; 125169689Skan if (part == NO_PARTITION) 126169689Skan return NULL_TREE; 127169689Skan 128169689Skan return partition_to_var (map, part); 129169689Skan} 130169689Skan 131169689Skan 132169689Skan/* Given VAR, return the partition number in MAP which contains it. 133169689Skan NO_PARTITION is returned if it's not in any partition. */ 134169689Skan 135169689Skanstatic inline int 136169689Skanvar_to_partition (var_map map, tree var) 137169689Skan{ 138169689Skan var_ann_t ann; 139169689Skan int part; 140169689Skan 141169689Skan if (TREE_CODE (var) == SSA_NAME) 142169689Skan { 143169689Skan part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); 144169689Skan if (map->partition_to_compact) 145169689Skan part = map->partition_to_compact[part]; 146169689Skan } 147169689Skan else 148169689Skan { 149169689Skan ann = var_ann (var); 150169689Skan if (ann->out_of_ssa_tag) 151169689Skan part = VAR_ANN_PARTITION (ann); 152169689Skan else 153169689Skan part = NO_PARTITION; 154169689Skan } 155169689Skan return part; 156169689Skan} 157169689Skan 158169689Skan 159169689Skan/* Given VAR, return the variable which represents the entire partition 160169689Skan it is a member of in MAP. NULL is returned if it is not in a partition. */ 161169689Skan 162169689Skanstatic inline tree 163169689Skanvar_to_partition_to_var (var_map map, tree var) 164169689Skan{ 165169689Skan int part; 166169689Skan 167169689Skan part = var_to_partition (map, var); 168169689Skan if (part == NO_PARTITION) 169169689Skan return NULL_TREE; 170169689Skan return partition_to_var (map, part); 171169689Skan} 172169689Skan 173169689Skan 174169689Skan/* This routine registers a partition for SSA_VAR with MAP. IS_USE is used 175169689Skan to count references. Any unregistered partitions may be compacted out 176169689Skan later. */ 177169689Skan 178169689Skanstatic inline void 179169689Skanregister_ssa_partition (var_map map, tree ssa_var, bool is_use) 180169689Skan{ 181169689Skan int version; 182169689Skan 183169689Skan#if defined ENABLE_CHECKING 184169689Skan register_ssa_partition_check (ssa_var); 185169689Skan#endif 186169689Skan 187169689Skan version = SSA_NAME_VERSION (ssa_var); 188169689Skan if (is_use && map->ref_count) 189169689Skan map->ref_count[version]++; 190169689Skan 191169689Skan if (map->partition_to_var[version] == NULL_TREE) 192169689Skan map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var; 193169689Skan} 194169689Skan 195169689Skan 196169689Skan/* ---------------- live on entry/exit info ------------------------------ 197169689Skan 198169689Skan This structure is used to represent live range information on SSA based 199169689Skan trees. A partition map must be provided, and based on the active partitions, 200169689Skan live-on-entry information and live-on-exit information can be calculated. 201169689Skan As well, partitions are marked as to whether they are global (live 202169689Skan outside the basic block they are defined in). 203169689Skan 204169689Skan The live-on-entry information is per variable. It provide a bitmap for 205169689Skan each variable which has a bit set for each basic block that the variable 206169689Skan is live on entry to that block. 207169689Skan 208169689Skan The live-on-exit information is per block. It provides a bitmap for each 209169689Skan block indicating which partitions are live on exit from the block. 210169689Skan 211169689Skan For the purposes of this implementation, we treat the elements of a PHI 212169689Skan as follows: 213169689Skan 214169689Skan Uses in a PHI are considered LIVE-ON-EXIT to the block from which they 215169689Skan originate. They are *NOT* considered live on entry to the block 216169689Skan containing the PHI node. 217169689Skan 218169689Skan The Def of a PHI node is *not* considered live on entry to the block. 219169689Skan It is considered to be "define early" in the block. Picture it as each 220169689Skan block having a stmt (or block-preheader) before the first real stmt in 221169689Skan the block which defines all the variables that are defined by PHIs. 222169689Skan 223169689Skan ----------------------------------------------------------------------- */ 224169689Skan 225169689Skan 226169689Skantypedef struct tree_live_info_d 227169689Skan{ 228169689Skan /* Var map this relates to. */ 229169689Skan var_map map; 230169689Skan 231169689Skan /* Bitmap indicating which partitions are global. */ 232169689Skan bitmap global; 233169689Skan 234169689Skan /* Bitmap of live on entry blocks for partition elements. */ 235169689Skan bitmap *livein; 236169689Skan 237169689Skan /* Number of basic blocks when live on exit calculated. */ 238169689Skan int num_blocks; 239169689Skan 240169689Skan /* Bitmap of what variables are live on exit for a basic blocks. */ 241169689Skan bitmap *liveout; 242169689Skan} *tree_live_info_p; 243169689Skan 244169689Skan 245169689Skanextern tree_live_info_p calculate_live_on_entry (var_map); 246169689Skanextern void calculate_live_on_exit (tree_live_info_p); 247169689Skanextern void delete_tree_live_info (tree_live_info_p); 248169689Skan 249169689Skan#define LIVEDUMP_ENTRY 0x01 250169689Skan#define LIVEDUMP_EXIT 0x02 251169689Skan#define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) 252169689Skanextern void dump_live_info (FILE *, tree_live_info_p, int); 253169689Skan 254169689Skanstatic inline int partition_is_global (tree_live_info_p, int); 255169689Skanstatic inline bitmap live_entry_blocks (tree_live_info_p, int); 256169689Skanstatic inline bitmap live_on_exit (tree_live_info_p, basic_block); 257169689Skanstatic inline var_map live_var_map (tree_live_info_p); 258169689Skanstatic inline void live_merge_and_clear (tree_live_info_p, int, int); 259169689Skanstatic inline void make_live_on_entry (tree_live_info_p, basic_block, int); 260169689Skan 261169689Skan 262169689Skan/* Return TRUE if P is marked as a global in LIVE. */ 263169689Skan 264169689Skanstatic inline int 265169689Skanpartition_is_global (tree_live_info_p live, int p) 266169689Skan{ 267169689Skan gcc_assert (live->global); 268169689Skan return bitmap_bit_p (live->global, p); 269169689Skan} 270169689Skan 271169689Skan 272169689Skan/* Return the bitmap from LIVE representing the live on entry blocks for 273169689Skan partition P. */ 274169689Skan 275169689Skanstatic inline bitmap 276169689Skanlive_entry_blocks (tree_live_info_p live, int p) 277169689Skan{ 278169689Skan gcc_assert (live->livein); 279169689Skan return live->livein[p]; 280169689Skan} 281169689Skan 282169689Skan 283169689Skan/* Return the bitmap from LIVE representing the live on exit partitions from 284169689Skan block BB. */ 285169689Skan 286169689Skanstatic inline bitmap 287169689Skanlive_on_exit (tree_live_info_p live, basic_block bb) 288169689Skan{ 289169689Skan gcc_assert (live->liveout); 290169689Skan gcc_assert (bb != ENTRY_BLOCK_PTR); 291169689Skan gcc_assert (bb != EXIT_BLOCK_PTR); 292169689Skan 293169689Skan return live->liveout[bb->index]; 294169689Skan} 295169689Skan 296169689Skan 297169689Skan/* Return the partition map which the information in LIVE utilizes. */ 298169689Skan 299169689Skanstatic inline var_map 300169689Skanlive_var_map (tree_live_info_p live) 301169689Skan{ 302169689Skan return live->map; 303169689Skan} 304169689Skan 305169689Skan 306169689Skan/* Merge the live on entry information in LIVE for partitions P1 and P2. Place 307169689Skan the result into P1. Clear P2. */ 308169689Skan 309169689Skanstatic inline void 310169689Skanlive_merge_and_clear (tree_live_info_p live, int p1, int p2) 311169689Skan{ 312169689Skan bitmap_ior_into (live->livein[p1], live->livein[p2]); 313169689Skan bitmap_zero (live->livein[p2]); 314169689Skan} 315169689Skan 316169689Skan 317169689Skan/* Mark partition P as live on entry to basic block BB in LIVE. */ 318169689Skan 319169689Skanstatic inline void 320169689Skanmake_live_on_entry (tree_live_info_p live, basic_block bb , int p) 321169689Skan{ 322169689Skan bitmap_set_bit (live->livein[p], bb->index); 323169689Skan bitmap_set_bit (live->global, p); 324169689Skan} 325169689Skan 326169689Skan 327169689Skan/* A tree_partition_associator (TPA)object is a base structure which allows 328169689Skan partitions to be associated with a tree object. 329169689Skan 330169689Skan A varray of tree elements represent each distinct tree item. 331169689Skan A parallel int array represents the first partition number associated with 332169689Skan the tree. 333169689Skan This partition number is then used as in index into the next_partition 334169689Skan array, which returns the index of the next partition which is associated 335169689Skan with the tree. TPA_NONE indicates the end of the list. 336169689Skan A varray paralleling the partition list 'partition_to_tree_map' is used 337169689Skan to indicate which tree index the partition is in. */ 338169689Skan 339169689Skantypedef struct tree_partition_associator_d 340169689Skan{ 341169689Skan VEC(tree,heap) *trees; 342169689Skan VEC(int,heap) *first_partition; 343169689Skan int *next_partition; 344169689Skan int *partition_to_tree_map; 345169689Skan int num_trees; 346169689Skan int uncompressed_num; 347169689Skan var_map map; 348169689Skan} *tpa_p; 349169689Skan 350169689Skan/* Value returned when there are no more partitions associated with a tree. */ 351169689Skan#define TPA_NONE -1 352169689Skan 353169689Skanstatic inline tree tpa_tree (tpa_p, int); 354169689Skanstatic inline int tpa_first_partition (tpa_p, int); 355169689Skanstatic inline int tpa_next_partition (tpa_p, int); 356169689Skanstatic inline int tpa_num_trees (tpa_p); 357169689Skanstatic inline int tpa_find_tree (tpa_p, int); 358169689Skanstatic inline void tpa_decompact (tpa_p); 359169689Skanextern void tpa_delete (tpa_p); 360169689Skanextern void tpa_dump (FILE *, tpa_p); 361169689Skanextern void tpa_remove_partition (tpa_p, int, int); 362169689Skanextern int tpa_compact (tpa_p); 363169689Skan 364169689Skan 365169689Skan/* Return the number of distinct tree nodes in TPA. */ 366169689Skan 367169689Skanstatic inline int 368169689Skantpa_num_trees (tpa_p tpa) 369169689Skan{ 370169689Skan return tpa->num_trees; 371169689Skan} 372169689Skan 373169689Skan 374169689Skan/* Return the tree node for index I in TPA. */ 375169689Skan 376169689Skanstatic inline tree 377169689Skantpa_tree (tpa_p tpa, int i) 378169689Skan{ 379169689Skan return VEC_index (tree, tpa->trees, i); 380169689Skan} 381169689Skan 382169689Skan 383169689Skan/* Return the first partition associated with tree list I in TPA. */ 384169689Skan 385169689Skanstatic inline int 386169689Skantpa_first_partition (tpa_p tpa, int i) 387169689Skan{ 388169689Skan return VEC_index (int, tpa->first_partition, i); 389169689Skan} 390169689Skan 391169689Skan 392169689Skan/* Return the next partition after partition I in TPA's list. */ 393169689Skan 394169689Skanstatic inline int 395169689Skantpa_next_partition (tpa_p tpa, int i) 396169689Skan{ 397169689Skan return tpa->next_partition[i]; 398169689Skan} 399169689Skan 400169689Skan 401169689Skan/* Return the tree index from TPA whose list contains partition I. 402169689Skan TPA_NONE is returned if I is not associated with any list. */ 403169689Skan 404169689Skanstatic inline int 405169689Skantpa_find_tree (tpa_p tpa, int i) 406169689Skan{ 407169689Skan int index; 408169689Skan 409169689Skan index = tpa->partition_to_tree_map[i]; 410169689Skan /* When compressed, any index higher than the number of tree elements is 411169689Skan a compressed element, so return TPA_NONE. */ 412169689Skan if (index != TPA_NONE && index >= tpa_num_trees (tpa)) 413169689Skan { 414169689Skan gcc_assert (tpa->uncompressed_num != -1); 415169689Skan index = TPA_NONE; 416169689Skan } 417169689Skan 418169689Skan return index; 419169689Skan} 420169689Skan 421169689Skan 422169689Skan/* This function removes any compaction which was performed on TPA. */ 423169689Skan 424169689Skanstatic inline void 425169689Skantpa_decompact(tpa_p tpa) 426169689Skan{ 427169689Skan gcc_assert (tpa->uncompressed_num != -1); 428169689Skan tpa->num_trees = tpa->uncompressed_num; 429169689Skan} 430169689Skan 431169689Skan 432169689Skan/* Once a var_map has been created and compressed, a complementary root_var 433169689Skan object can be built. This creates a list of all the root variables from 434169689Skan which ssa version names are derived. Each root variable has a list of 435169689Skan which partitions are versions of that root. 436169689Skan 437169689Skan This is implemented using the tree_partition_associator. 438169689Skan 439169689Skan The tree vector is used to represent the root variable. 440169689Skan The list of partitions represent SSA versions of the root variable. */ 441169689Skan 442169689Skantypedef tpa_p root_var_p; 443169689Skan 444169689Skanstatic inline tree root_var (root_var_p, int); 445169689Skanstatic inline int root_var_first_partition (root_var_p, int); 446169689Skanstatic inline int root_var_next_partition (root_var_p, int); 447169689Skanstatic inline int root_var_num (root_var_p); 448169689Skanstatic inline void root_var_dump (FILE *, root_var_p); 449169689Skanstatic inline void root_var_remove_partition (root_var_p, int, int); 450169689Skanstatic inline void root_var_delete (root_var_p); 451169689Skanstatic inline int root_var_find (root_var_p, int); 452169689Skanstatic inline int root_var_compact (root_var_p); 453169689Skanstatic inline void root_var_decompact (tpa_p); 454169689Skan 455169689Skanextern root_var_p root_var_init (var_map); 456169689Skan 457169689Skan/* Value returned when there are no more partitions associated with a root 458169689Skan variable. */ 459169689Skan#define ROOT_VAR_NONE TPA_NONE 460169689Skan 461169689Skan 462169689Skan/* Return the number of distinct root variables in RV. */ 463169689Skan 464169689Skanstatic inline int 465169689Skanroot_var_num (root_var_p rv) 466169689Skan{ 467169689Skan return tpa_num_trees (rv); 468169689Skan} 469169689Skan 470169689Skan 471169689Skan/* Return root variable I from RV. */ 472169689Skan 473169689Skanstatic inline tree 474169689Skanroot_var (root_var_p rv, int i) 475169689Skan{ 476169689Skan return tpa_tree (rv, i); 477169689Skan} 478169689Skan 479169689Skan 480169689Skan/* Return the first partition in RV belonging to root variable list I. */ 481169689Skan 482169689Skanstatic inline int 483169689Skanroot_var_first_partition (root_var_p rv, int i) 484169689Skan{ 485169689Skan return tpa_first_partition (rv, i); 486169689Skan} 487169689Skan 488169689Skan 489169689Skan/* Return the next partition after partition I in a root list from RV. */ 490169689Skan 491169689Skanstatic inline int 492169689Skanroot_var_next_partition (root_var_p rv, int i) 493169689Skan{ 494169689Skan return tpa_next_partition (rv, i); 495169689Skan} 496169689Skan 497169689Skan 498169689Skan/* Send debug info for root_var list RV to file F. */ 499169689Skan 500169689Skanstatic inline void 501169689Skanroot_var_dump (FILE *f, root_var_p rv) 502169689Skan{ 503169689Skan fprintf (f, "\nRoot Var dump\n"); 504169689Skan tpa_dump (f, rv); 505169689Skan fprintf (f, "\n"); 506169689Skan} 507169689Skan 508169689Skan 509169689Skan/* Destroy root_var object RV. */ 510169689Skan 511169689Skanstatic inline void 512169689Skanroot_var_delete (root_var_p rv) 513169689Skan{ 514169689Skan tpa_delete (rv); 515169689Skan} 516169689Skan 517169689Skan 518169689Skan/* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */ 519169689Skan 520169689Skanstatic inline void 521169689Skanroot_var_remove_partition (root_var_p rv, int root_index, int partition_index) 522169689Skan{ 523169689Skan tpa_remove_partition (rv, root_index, partition_index); 524169689Skan} 525169689Skan 526169689Skan 527169689Skan/* Return the root_var list index for partition I in RV. */ 528169689Skan 529169689Skanstatic inline int 530169689Skanroot_var_find (root_var_p rv, int i) 531169689Skan{ 532169689Skan return tpa_find_tree (rv, i); 533169689Skan} 534169689Skan 535169689Skan 536169689Skan/* Hide single element lists in RV. */ 537169689Skan 538169689Skanstatic inline int 539169689Skanroot_var_compact (root_var_p rv) 540169689Skan{ 541169689Skan return tpa_compact (rv); 542169689Skan} 543169689Skan 544169689Skan 545169689Skan/* Expose the single element lists in RV. */ 546169689Skan 547169689Skanstatic inline void 548169689Skanroot_var_decompact (root_var_p rv) 549169689Skan{ 550169689Skan tpa_decompact (rv); 551169689Skan} 552169689Skan 553169689Skan 554169689Skan/* A TYPE_VAR object is similar to a root_var object, except this associates 555169689Skan partitions with their type rather than their root variable. This is used to 556169689Skan coalesce memory locations based on type. */ 557169689Skan 558169689Skantypedef tpa_p type_var_p; 559169689Skan 560169689Skanstatic inline tree type_var (type_var_p, int); 561169689Skanstatic inline int type_var_first_partition (type_var_p, int); 562169689Skanstatic inline int type_var_next_partition (type_var_p, int); 563169689Skanstatic inline int type_var_num (type_var_p); 564169689Skanstatic inline void type_var_dump (FILE *, type_var_p); 565169689Skanstatic inline void type_var_remove_partition (type_var_p, int, int); 566169689Skanstatic inline void type_var_delete (type_var_p); 567169689Skanstatic inline int type_var_find (type_var_p, int); 568169689Skanstatic inline int type_var_compact (type_var_p); 569169689Skanstatic inline void type_var_decompact (type_var_p); 570169689Skan 571169689Skanextern type_var_p type_var_init (var_map); 572169689Skan 573169689Skan/* Value returned when there is no partitions associated with a list. */ 574169689Skan#define TYPE_VAR_NONE TPA_NONE 575169689Skan 576169689Skan 577169689Skan/* Return the number of distinct type lists in TV. */ 578169689Skan 579169689Skanstatic inline int 580169689Skantype_var_num (type_var_p tv) 581169689Skan{ 582169689Skan return tpa_num_trees (tv); 583169689Skan} 584169689Skan 585169689Skan 586169689Skan/* Return the type of list I in TV. */ 587169689Skan 588169689Skanstatic inline tree 589169689Skantype_var (type_var_p tv, int i) 590169689Skan{ 591169689Skan return tpa_tree (tv, i); 592169689Skan} 593169689Skan 594169689Skan 595169689Skan/* Return the first partition belonging to type list I in TV. */ 596169689Skan 597169689Skanstatic inline int 598169689Skantype_var_first_partition (type_var_p tv, int i) 599169689Skan{ 600169689Skan return tpa_first_partition (tv, i); 601169689Skan} 602169689Skan 603169689Skan 604169689Skan/* Return the next partition after partition I in a type list within TV. */ 605169689Skan 606169689Skanstatic inline int 607169689Skantype_var_next_partition (type_var_p tv, int i) 608169689Skan{ 609169689Skan return tpa_next_partition (tv, i); 610169689Skan} 611169689Skan 612169689Skan 613169689Skan/* Send debug info for type_var object TV to file F. */ 614169689Skan 615169689Skanstatic inline void 616169689Skantype_var_dump (FILE *f, type_var_p tv) 617169689Skan{ 618169689Skan fprintf (f, "\nType Var dump\n"); 619169689Skan tpa_dump (f, tv); 620169689Skan fprintf (f, "\n"); 621169689Skan} 622169689Skan 623169689Skan 624169689Skan/* Delete type_var object TV. */ 625169689Skan 626169689Skanstatic inline void 627169689Skantype_var_delete (type_var_p tv) 628169689Skan{ 629169689Skan tpa_delete (tv); 630169689Skan} 631169689Skan 632169689Skan 633169689Skan/* Remove partition PARTITION_INDEX from type list TYPE_INDEX in TV. */ 634169689Skan 635169689Skanstatic inline void 636169689Skantype_var_remove_partition (type_var_p tv, int type_index, int partition_index) 637169689Skan{ 638169689Skan tpa_remove_partition (tv, type_index, partition_index); 639169689Skan} 640169689Skan 641169689Skan 642169689Skan/* Return the type index in TV for the list partition I is in. */ 643169689Skan 644169689Skanstatic inline int 645169689Skantype_var_find (type_var_p tv, int i) 646169689Skan{ 647169689Skan return tpa_find_tree (tv, i); 648169689Skan} 649169689Skan 650169689Skan 651169689Skan/* Hide single element lists in TV. */ 652169689Skan 653169689Skanstatic inline int 654169689Skantype_var_compact (type_var_p tv) 655169689Skan{ 656169689Skan return tpa_compact (tv); 657169689Skan} 658169689Skan 659169689Skan 660169689Skan/* Expose single element lists in TV. */ 661169689Skan 662169689Skanstatic inline void 663169689Skantype_var_decompact (type_var_p tv) 664169689Skan{ 665169689Skan tpa_decompact (tv); 666169689Skan} 667169689Skan 668169689Skan/* This set of routines implements a coalesce_list. This is an object which 669169689Skan is used to track pairs of partitions which are desirable to coalesce 670169689Skan together at some point. Costs are associated with each pair, and when 671169689Skan all desired information has been collected, the object can be used to 672169689Skan order the pairs for processing. */ 673169689Skan 674169689Skan/* This structure defines a pair for coalescing. */ 675169689Skan 676169689Skantypedef struct partition_pair_d 677169689Skan{ 678169689Skan int first_partition; 679169689Skan int second_partition; 680169689Skan int cost; 681169689Skan struct partition_pair_d *next; 682169689Skan} *partition_pair_p; 683169689Skan 684169689Skan/* This structure maintains the list of coalesce pairs. 685169689Skan When add_mode is true, list is a triangular shaped list of coalesce pairs. 686169689Skan The smaller partition number is used to index the list, and the larger is 687169689Skan index is located in a partition_pair_p object. These lists are sorted from 688169689Skan smallest to largest by 'second_partition'. New coalesce pairs are allowed 689169689Skan to be added in this mode. 690169689Skan When add_mode is false, the lists have all been merged into list[0]. The 691169689Skan rest of the lists are not used. list[0] is ordered from most desirable 692169689Skan coalesce to least desirable. pop_best_coalesce() retrieves the pairs 693169689Skan one at a time. */ 694169689Skan 695169689Skantypedef struct coalesce_list_d 696169689Skan{ 697169689Skan var_map map; 698169689Skan partition_pair_p *list; 699169689Skan bool add_mode; 700169689Skan} *coalesce_list_p; 701169689Skan 702169689Skanextern coalesce_list_p create_coalesce_list (var_map); 703169689Skanextern void add_coalesce (coalesce_list_p, int, int, int); 704169689Skanextern int coalesce_cost (int, bool, bool); 705169689Skanextern void sort_coalesce_list (coalesce_list_p); 706169689Skanextern void dump_coalesce_list (FILE *, coalesce_list_p); 707169689Skanextern void delete_coalesce_list (coalesce_list_p); 708169689Skan 709169689Skan#define NO_BEST_COALESCE -1 710169689Skan 711169689Skanextern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p, 712169689Skan coalesce_list_p); 713169689Skanextern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, 714169689Skan coalesce_list_p cl, FILE *); 715169689Skan 716169689Skan 717169689Skan#endif /* _TREE_SSA_LIVE_H */ 718