1169689Skan/* Liveness for 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#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "tree.h" 27169689Skan#include "flags.h" 28169689Skan#include "basic-block.h" 29169689Skan#include "function.h" 30169689Skan#include "diagnostic.h" 31169689Skan#include "bitmap.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-gimple.h" 34169689Skan#include "tree-inline.h" 35169689Skan#include "varray.h" 36169689Skan#include "timevar.h" 37169689Skan#include "hashtab.h" 38169689Skan#include "tree-dump.h" 39169689Skan#include "tree-ssa-live.h" 40169689Skan#include "toplev.h" 41169689Skan#include "vecprim.h" 42169689Skan 43169689Skanstatic void live_worklist (tree_live_info_p, int *, int); 44169689Skanstatic tree_live_info_p new_tree_live_info (var_map); 45169689Skanstatic inline void set_if_valid (var_map, bitmap, tree); 46169689Skanstatic inline void add_livein_if_notdef (tree_live_info_p, bitmap, 47169689Skan tree, basic_block); 48169689Skanstatic inline void register_ssa_partition (var_map, tree, bool); 49169689Skanstatic inline void add_conflicts_if_valid (tpa_p, conflict_graph, 50169689Skan var_map, bitmap, tree); 51169689Skanstatic partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool); 52169689Skan 53169689Skan/* This is where the mapping from SSA version number to real storage variable 54169689Skan is tracked. 55169689Skan 56169689Skan All SSA versions of the same variable may not ultimately be mapped back to 57169689Skan the same real variable. In that instance, we need to detect the live 58169689Skan range overlap, and give one of the variable new storage. The vector 59169689Skan 'partition_to_var' tracks which partition maps to which variable. 60169689Skan 61169689Skan Given a VAR, it is sometimes desirable to know which partition that VAR 62169689Skan represents. There is an additional field in the variable annotation to 63169689Skan track that information. */ 64169689Skan 65169689Skan/* Create a variable partition map of SIZE, initialize and return it. */ 66169689Skan 67169689Skanvar_map 68169689Skaninit_var_map (int size) 69169689Skan{ 70169689Skan var_map map; 71169689Skan 72169689Skan map = (var_map) xmalloc (sizeof (struct _var_map)); 73169689Skan map->var_partition = partition_new (size); 74169689Skan map->partition_to_var 75169689Skan = (tree *)xmalloc (size * sizeof (tree)); 76169689Skan memset (map->partition_to_var, 0, size * sizeof (tree)); 77169689Skan 78169689Skan map->partition_to_compact = NULL; 79169689Skan map->compact_to_partition = NULL; 80169689Skan map->num_partitions = size; 81169689Skan map->partition_size = size; 82169689Skan map->ref_count = NULL; 83169689Skan return map; 84169689Skan} 85169689Skan 86169689Skan 87169689Skan/* Free memory associated with MAP. */ 88169689Skan 89169689Skanvoid 90169689Skandelete_var_map (var_map map) 91169689Skan{ 92169689Skan free (map->partition_to_var); 93169689Skan partition_delete (map->var_partition); 94169689Skan if (map->partition_to_compact) 95169689Skan free (map->partition_to_compact); 96169689Skan if (map->compact_to_partition) 97169689Skan free (map->compact_to_partition); 98169689Skan if (map->ref_count) 99169689Skan free (map->ref_count); 100169689Skan free (map); 101169689Skan} 102169689Skan 103169689Skan 104169689Skan/* This function will combine the partitions in MAP for VAR1 and VAR2. It 105169689Skan Returns the partition which represents the new partition. If the two 106169689Skan partitions cannot be combined, NO_PARTITION is returned. */ 107169689Skan 108169689Skanint 109169689Skanvar_union (var_map map, tree var1, tree var2) 110169689Skan{ 111169689Skan int p1, p2, p3; 112169689Skan tree root_var = NULL_TREE; 113169689Skan tree other_var = NULL_TREE; 114169689Skan 115169689Skan /* This is independent of partition_to_compact. If partition_to_compact is 116169689Skan on, then whichever one of these partitions is absorbed will never have a 117169689Skan dereference into the partition_to_compact array any more. */ 118169689Skan 119169689Skan if (TREE_CODE (var1) == SSA_NAME) 120169689Skan p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); 121169689Skan else 122169689Skan { 123169689Skan p1 = var_to_partition (map, var1); 124169689Skan if (map->compact_to_partition) 125169689Skan p1 = map->compact_to_partition[p1]; 126169689Skan root_var = var1; 127169689Skan } 128169689Skan 129169689Skan if (TREE_CODE (var2) == SSA_NAME) 130169689Skan p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); 131169689Skan else 132169689Skan { 133169689Skan p2 = var_to_partition (map, var2); 134169689Skan if (map->compact_to_partition) 135169689Skan p2 = map->compact_to_partition[p2]; 136169689Skan 137169689Skan /* If there is no root_var set, or it's not a user variable, set the 138169689Skan root_var to this one. */ 139169689Skan if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var))) 140169689Skan { 141169689Skan other_var = root_var; 142169689Skan root_var = var2; 143169689Skan } 144169689Skan else 145169689Skan other_var = var2; 146169689Skan } 147169689Skan 148169689Skan gcc_assert (p1 != NO_PARTITION); 149169689Skan gcc_assert (p2 != NO_PARTITION); 150169689Skan 151169689Skan if (p1 == p2) 152169689Skan p3 = p1; 153169689Skan else 154169689Skan p3 = partition_union (map->var_partition, p1, p2); 155169689Skan 156169689Skan if (map->partition_to_compact) 157169689Skan p3 = map->partition_to_compact[p3]; 158169689Skan 159169689Skan if (root_var) 160169689Skan change_partition_var (map, root_var, p3); 161169689Skan if (other_var) 162169689Skan change_partition_var (map, other_var, p3); 163169689Skan 164169689Skan return p3; 165169689Skan} 166169689Skan 167169689Skan 168169689Skan/* Compress the partition numbers in MAP such that they fall in the range 169169689Skan 0..(num_partitions-1) instead of wherever they turned out during 170169689Skan the partitioning exercise. This removes any references to unused 171169689Skan partitions, thereby allowing bitmaps and other vectors to be much 172169689Skan denser. Compression type is controlled by FLAGS. 173169689Skan 174169689Skan This is implemented such that compaction doesn't affect partitioning. 175169689Skan Ie., once partitions are created and possibly merged, running one 176169689Skan or more different kind of compaction will not affect the partitions 177169689Skan themselves. Their index might change, but all the same variables will 178169689Skan still be members of the same partition group. This allows work on reduced 179169689Skan sets, and no loss of information when a larger set is later desired. 180169689Skan 181169689Skan In particular, coalescing can work on partitions which have 2 or more 182169689Skan definitions, and then 'recompact' later to include all the single 183169689Skan definitions for assignment to program variables. */ 184169689Skan 185169689Skanvoid 186169689Skancompact_var_map (var_map map, int flags) 187169689Skan{ 188169689Skan sbitmap used; 189169689Skan int tmp, root, root_i; 190169689Skan unsigned int x, limit, count; 191169689Skan tree var; 192169689Skan root_var_p rv = NULL; 193169689Skan 194169689Skan limit = map->partition_size; 195169689Skan used = sbitmap_alloc (limit); 196169689Skan sbitmap_zero (used); 197169689Skan 198169689Skan /* Already compressed? Abandon the old one. */ 199169689Skan if (map->partition_to_compact) 200169689Skan { 201169689Skan free (map->partition_to_compact); 202169689Skan map->partition_to_compact = NULL; 203169689Skan } 204169689Skan if (map->compact_to_partition) 205169689Skan { 206169689Skan free (map->compact_to_partition); 207169689Skan map->compact_to_partition = NULL; 208169689Skan } 209169689Skan 210169689Skan map->num_partitions = map->partition_size; 211169689Skan 212169689Skan if (flags & VARMAP_NO_SINGLE_DEFS) 213169689Skan rv = root_var_init (map); 214169689Skan 215169689Skan map->partition_to_compact = (int *)xmalloc (limit * sizeof (int)); 216169689Skan memset (map->partition_to_compact, 0xff, (limit * sizeof (int))); 217169689Skan 218169689Skan /* Find out which partitions are actually referenced. */ 219169689Skan count = 0; 220169689Skan for (x = 0; x < limit; x++) 221169689Skan { 222169689Skan tmp = partition_find (map->var_partition, x); 223169689Skan if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE) 224169689Skan { 225169689Skan /* It is referenced, check to see if there is more than one version 226169689Skan in the root_var table, if one is available. */ 227169689Skan if (rv) 228169689Skan { 229169689Skan root = root_var_find (rv, tmp); 230169689Skan root_i = root_var_first_partition (rv, root); 231169689Skan /* If there is only one, don't include this in the compaction. */ 232169689Skan if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE) 233169689Skan continue; 234169689Skan } 235169689Skan SET_BIT (used, tmp); 236169689Skan count++; 237169689Skan } 238169689Skan } 239169689Skan 240169689Skan /* Build a compacted partitioning. */ 241169689Skan if (count != limit) 242169689Skan { 243169689Skan sbitmap_iterator sbi; 244169689Skan 245169689Skan map->compact_to_partition = (int *)xmalloc (count * sizeof (int)); 246169689Skan count = 0; 247169689Skan /* SSA renaming begins at 1, so skip 0 when compacting. */ 248169689Skan EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi) 249169689Skan { 250169689Skan map->partition_to_compact[x] = count; 251169689Skan map->compact_to_partition[count] = x; 252169689Skan var = map->partition_to_var[x]; 253169689Skan if (TREE_CODE (var) != SSA_NAME) 254169689Skan change_partition_var (map, var, count); 255169689Skan count++; 256169689Skan } 257169689Skan } 258169689Skan else 259169689Skan { 260169689Skan free (map->partition_to_compact); 261169689Skan map->partition_to_compact = NULL; 262169689Skan } 263169689Skan 264169689Skan map->num_partitions = count; 265169689Skan 266169689Skan if (rv) 267169689Skan root_var_delete (rv); 268169689Skan sbitmap_free (used); 269169689Skan} 270169689Skan 271169689Skan 272169689Skan/* This function is used to change the representative variable in MAP for VAR's 273169689Skan partition from an SSA_NAME variable to a regular variable. This allows 274169689Skan partitions to be mapped back to real variables. */ 275169689Skan 276169689Skanvoid 277169689Skanchange_partition_var (var_map map, tree var, int part) 278169689Skan{ 279169689Skan var_ann_t ann; 280169689Skan 281169689Skan gcc_assert (TREE_CODE (var) != SSA_NAME); 282169689Skan 283169689Skan ann = var_ann (var); 284169689Skan ann->out_of_ssa_tag = 1; 285169689Skan VAR_ANN_PARTITION (ann) = part; 286169689Skan if (map->compact_to_partition) 287169689Skan map->partition_to_var[map->compact_to_partition[part]] = var; 288169689Skan} 289169689Skan 290169689Skanstatic inline void mark_all_vars_used (tree *); 291169689Skan 292169689Skan/* Helper function for mark_all_vars_used, called via walk_tree. */ 293169689Skan 294169689Skanstatic tree 295169689Skanmark_all_vars_used_1 (tree *tp, int *walk_subtrees, 296169689Skan void *data ATTRIBUTE_UNUSED) 297169689Skan{ 298169689Skan tree t = *tp; 299169689Skan 300169689Skan if (TREE_CODE (t) == SSA_NAME) 301169689Skan t = SSA_NAME_VAR (t); 302169689Skan 303169689Skan /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other 304169689Skan fields that do not contain vars. */ 305169689Skan if (TREE_CODE (t) == TARGET_MEM_REF) 306169689Skan { 307169689Skan mark_all_vars_used (&TMR_SYMBOL (t)); 308169689Skan mark_all_vars_used (&TMR_BASE (t)); 309169689Skan mark_all_vars_used (&TMR_INDEX (t)); 310169689Skan *walk_subtrees = 0; 311169689Skan return NULL; 312169689Skan } 313169689Skan 314169689Skan /* Only need to mark VAR_DECLS; parameters and return results are not 315169689Skan eliminated as unused. */ 316169689Skan if (TREE_CODE (t) == VAR_DECL) 317169689Skan set_is_used (t); 318169689Skan 319169689Skan if (IS_TYPE_OR_DECL_P (t)) 320169689Skan *walk_subtrees = 0; 321169689Skan 322169689Skan return NULL; 323169689Skan} 324169689Skan 325169689Skan/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be 326169689Skan eliminated during the tree->rtl conversion process. */ 327169689Skan 328169689Skanstatic inline void 329169689Skanmark_all_vars_used (tree *expr_p) 330169689Skan{ 331169689Skan walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL); 332169689Skan} 333169689Skan 334169689Skan 335169689Skan/* Remove local variables that are not referenced in the IL. */ 336169689Skan 337169689Skanvoid 338169689Skanremove_unused_locals (void) 339169689Skan{ 340169689Skan basic_block bb; 341169689Skan tree t, *cell; 342169689Skan 343169689Skan /* Assume all locals are unused. */ 344169689Skan for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t)) 345169689Skan { 346169689Skan tree var = TREE_VALUE (t); 347169689Skan if (TREE_CODE (var) != FUNCTION_DECL 348169689Skan && var_ann (var)) 349169689Skan var_ann (var)->used = false; 350169689Skan } 351169689Skan 352169689Skan /* Walk the CFG marking all referenced symbols. */ 353169689Skan FOR_EACH_BB (bb) 354169689Skan { 355169689Skan block_stmt_iterator bsi; 356169689Skan tree phi, def; 357169689Skan 358169689Skan /* Walk the statements. */ 359169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 360169689Skan mark_all_vars_used (bsi_stmt_ptr (bsi)); 361169689Skan 362169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 363169689Skan { 364169689Skan use_operand_p arg_p; 365169689Skan ssa_op_iter i; 366169689Skan 367169689Skan /* No point processing globals. */ 368169689Skan if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi)))) 369169689Skan continue; 370169689Skan 371169689Skan def = PHI_RESULT (phi); 372169689Skan mark_all_vars_used (&def); 373169689Skan 374169689Skan FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES) 375169689Skan { 376169689Skan tree arg = USE_FROM_PTR (arg_p); 377169689Skan mark_all_vars_used (&arg); 378169689Skan } 379169689Skan } 380169689Skan } 381169689Skan 382169689Skan /* Remove unmarked vars and clear used flag. */ 383169689Skan for (cell = &cfun->unexpanded_var_list; *cell; ) 384169689Skan { 385169689Skan tree var = TREE_VALUE (*cell); 386169689Skan var_ann_t ann; 387169689Skan 388169689Skan if (TREE_CODE (var) != FUNCTION_DECL 389169689Skan && (!(ann = var_ann (var)) 390169689Skan || !ann->used)) 391169689Skan { 392169689Skan *cell = TREE_CHAIN (*cell); 393169689Skan continue; 394169689Skan } 395169689Skan 396169689Skan cell = &TREE_CHAIN (*cell); 397169689Skan } 398169689Skan} 399169689Skan 400169689Skan/* This function looks through the program and uses FLAGS to determine what 401169689Skan SSA versioned variables are given entries in a new partition table. This 402169689Skan new partition map is returned. */ 403169689Skan 404169689Skanvar_map 405169689Skancreate_ssa_var_map (int flags) 406169689Skan{ 407169689Skan block_stmt_iterator bsi; 408169689Skan basic_block bb; 409169689Skan tree dest, use; 410169689Skan tree stmt; 411169689Skan var_map map; 412169689Skan ssa_op_iter iter; 413169689Skan#ifdef ENABLE_CHECKING 414169689Skan bitmap used_in_real_ops; 415169689Skan bitmap used_in_virtual_ops; 416169689Skan#endif 417169689Skan 418169689Skan map = init_var_map (num_ssa_names + 1); 419169689Skan 420169689Skan#ifdef ENABLE_CHECKING 421169689Skan used_in_real_ops = BITMAP_ALLOC (NULL); 422169689Skan used_in_virtual_ops = BITMAP_ALLOC (NULL); 423169689Skan#endif 424169689Skan 425169689Skan if (flags & SSA_VAR_MAP_REF_COUNT) 426169689Skan { 427169689Skan map->ref_count 428169689Skan = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int))); 429169689Skan memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int)); 430169689Skan } 431169689Skan 432169689Skan FOR_EACH_BB (bb) 433169689Skan { 434169689Skan tree phi, arg; 435169689Skan 436169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 437169689Skan { 438169689Skan int i; 439169689Skan register_ssa_partition (map, PHI_RESULT (phi), false); 440169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 441169689Skan { 442169689Skan arg = PHI_ARG_DEF (phi, i); 443169689Skan if (TREE_CODE (arg) == SSA_NAME) 444169689Skan register_ssa_partition (map, arg, true); 445169689Skan 446169689Skan mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i)); 447169689Skan } 448169689Skan } 449169689Skan 450169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 451169689Skan { 452169689Skan stmt = bsi_stmt (bsi); 453169689Skan 454169689Skan /* Register USE and DEF operands in each statement. */ 455169689Skan FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE) 456169689Skan { 457169689Skan register_ssa_partition (map, use, true); 458169689Skan 459169689Skan#ifdef ENABLE_CHECKING 460169689Skan bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use))); 461169689Skan#endif 462169689Skan } 463169689Skan 464169689Skan FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF) 465169689Skan { 466169689Skan register_ssa_partition (map, dest, false); 467169689Skan 468169689Skan#ifdef ENABLE_CHECKING 469169689Skan bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest))); 470169689Skan#endif 471169689Skan } 472169689Skan 473169689Skan#ifdef ENABLE_CHECKING 474169689Skan /* Validate that virtual ops don't get used in funny ways. */ 475169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, 476169689Skan SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF) 477169689Skan { 478169689Skan bitmap_set_bit (used_in_virtual_ops, 479169689Skan DECL_UID (SSA_NAME_VAR (use))); 480169689Skan } 481169689Skan 482169689Skan#endif /* ENABLE_CHECKING */ 483169689Skan 484169689Skan mark_all_vars_used (bsi_stmt_ptr (bsi)); 485169689Skan } 486169689Skan } 487169689Skan 488169689Skan#if defined ENABLE_CHECKING 489169689Skan { 490169689Skan unsigned i; 491169689Skan bitmap both = BITMAP_ALLOC (NULL); 492169689Skan bitmap_and (both, used_in_real_ops, used_in_virtual_ops); 493169689Skan if (!bitmap_empty_p (both)) 494169689Skan { 495169689Skan bitmap_iterator bi; 496169689Skan 497169689Skan EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) 498169689Skan fprintf (stderr, "Variable %s used in real and virtual operands\n", 499169689Skan get_name (referenced_var (i))); 500169689Skan internal_error ("SSA corruption"); 501169689Skan } 502169689Skan 503169689Skan BITMAP_FREE (used_in_real_ops); 504169689Skan BITMAP_FREE (used_in_virtual_ops); 505169689Skan BITMAP_FREE (both); 506169689Skan } 507169689Skan#endif 508169689Skan 509169689Skan return map; 510169689Skan} 511169689Skan 512169689Skan 513169689Skan/* Allocate and return a new live range information object base on MAP. */ 514169689Skan 515169689Skanstatic tree_live_info_p 516169689Skannew_tree_live_info (var_map map) 517169689Skan{ 518169689Skan tree_live_info_p live; 519169689Skan unsigned x; 520169689Skan 521169689Skan live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); 522169689Skan live->map = map; 523169689Skan live->num_blocks = last_basic_block; 524169689Skan 525169689Skan live->global = BITMAP_ALLOC (NULL); 526169689Skan 527169689Skan live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap)); 528169689Skan for (x = 0; x < num_var_partitions (map); x++) 529169689Skan live->livein[x] = BITMAP_ALLOC (NULL); 530169689Skan 531169689Skan /* liveout is deferred until it is actually requested. */ 532169689Skan live->liveout = NULL; 533169689Skan return live; 534169689Skan} 535169689Skan 536169689Skan 537169689Skan/* Free storage for live range info object LIVE. */ 538169689Skan 539169689Skanvoid 540169689Skandelete_tree_live_info (tree_live_info_p live) 541169689Skan{ 542169689Skan int x; 543169689Skan if (live->liveout) 544169689Skan { 545169689Skan for (x = live->num_blocks - 1; x >= 0; x--) 546169689Skan BITMAP_FREE (live->liveout[x]); 547169689Skan free (live->liveout); 548169689Skan } 549169689Skan if (live->livein) 550169689Skan { 551169689Skan for (x = num_var_partitions (live->map) - 1; x >= 0; x--) 552169689Skan BITMAP_FREE (live->livein[x]); 553169689Skan free (live->livein); 554169689Skan } 555169689Skan if (live->global) 556169689Skan BITMAP_FREE (live->global); 557169689Skan 558169689Skan free (live); 559169689Skan} 560169689Skan 561169689Skan 562169689Skan/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses 563169689Skan for partition I. STACK is a varray used for temporary memory which is 564169689Skan passed in rather than being allocated on every call. */ 565169689Skan 566169689Skanstatic void 567169689Skanlive_worklist (tree_live_info_p live, int *stack, int i) 568169689Skan{ 569169689Skan unsigned b; 570169689Skan tree var; 571169689Skan basic_block def_bb = NULL; 572169689Skan edge e; 573169689Skan var_map map = live->map; 574169689Skan edge_iterator ei; 575169689Skan bitmap_iterator bi; 576169689Skan int *tos = stack; 577169689Skan 578169689Skan var = partition_to_var (map, i); 579169689Skan if (SSA_NAME_DEF_STMT (var)) 580169689Skan def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 581169689Skan 582169689Skan EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi) 583169689Skan { 584169689Skan *tos++ = b; 585169689Skan } 586169689Skan 587169689Skan while (tos != stack) 588169689Skan { 589169689Skan b = *--tos; 590169689Skan 591169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) 592169689Skan if (e->src != ENTRY_BLOCK_PTR) 593169689Skan { 594169689Skan /* Its not live on entry to the block its defined in. */ 595169689Skan if (e->src == def_bb) 596169689Skan continue; 597169689Skan if (!bitmap_bit_p (live->livein[i], e->src->index)) 598169689Skan { 599169689Skan bitmap_set_bit (live->livein[i], e->src->index); 600169689Skan *tos++ = e->src->index; 601169689Skan } 602169689Skan } 603169689Skan } 604169689Skan} 605169689Skan 606169689Skan 607169689Skan/* If VAR is in a partition of MAP, set the bit for that partition in VEC. */ 608169689Skan 609169689Skanstatic inline void 610169689Skanset_if_valid (var_map map, bitmap vec, tree var) 611169689Skan{ 612169689Skan int p = var_to_partition (map, var); 613169689Skan if (p != NO_PARTITION) 614169689Skan bitmap_set_bit (vec, p); 615169689Skan} 616169689Skan 617169689Skan 618169689Skan/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and 619169689Skan global bit for it in the LIVE object. BB is the block being processed. */ 620169689Skan 621169689Skanstatic inline void 622169689Skanadd_livein_if_notdef (tree_live_info_p live, bitmap def_vec, 623169689Skan tree var, basic_block bb) 624169689Skan{ 625169689Skan int p = var_to_partition (live->map, var); 626169689Skan if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR) 627169689Skan return; 628169689Skan if (!bitmap_bit_p (def_vec, p)) 629169689Skan { 630169689Skan bitmap_set_bit (live->livein[p], bb->index); 631169689Skan bitmap_set_bit (live->global, p); 632169689Skan } 633169689Skan} 634169689Skan 635169689Skan 636169689Skan/* Given partition map MAP, calculate all the live on entry bitmaps for 637169689Skan each basic block. Return a live info object. */ 638169689Skan 639169689Skantree_live_info_p 640169689Skancalculate_live_on_entry (var_map map) 641169689Skan{ 642169689Skan tree_live_info_p live; 643169689Skan unsigned i; 644169689Skan basic_block bb; 645169689Skan bitmap saw_def; 646169689Skan tree phi, var, stmt; 647169689Skan tree op; 648169689Skan edge e; 649169689Skan int *stack; 650169689Skan block_stmt_iterator bsi; 651169689Skan ssa_op_iter iter; 652169689Skan bitmap_iterator bi; 653169689Skan#ifdef ENABLE_CHECKING 654169689Skan int num; 655169689Skan edge_iterator ei; 656169689Skan#endif 657169689Skan 658169689Skan saw_def = BITMAP_ALLOC (NULL); 659169689Skan 660169689Skan live = new_tree_live_info (map); 661169689Skan 662169689Skan FOR_EACH_BB (bb) 663169689Skan { 664169689Skan bitmap_clear (saw_def); 665169689Skan 666169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 667169689Skan { 668169689Skan for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) 669169689Skan { 670169689Skan var = PHI_ARG_DEF (phi, i); 671169689Skan if (!phi_ssa_name_p (var)) 672169689Skan continue; 673169689Skan stmt = SSA_NAME_DEF_STMT (var); 674169689Skan e = EDGE_PRED (bb, i); 675169689Skan 676169689Skan /* Any uses in PHIs which either don't have def's or are not 677169689Skan defined in the block from which the def comes, will be live 678169689Skan on entry to that block. */ 679169689Skan if (!stmt || e->src != bb_for_stmt (stmt)) 680169689Skan add_livein_if_notdef (live, saw_def, var, e->src); 681169689Skan } 682169689Skan } 683169689Skan 684169689Skan /* Don't mark PHI results as defined until all the PHI nodes have 685169689Skan been processed. If the PHI sequence is: 686169689Skan a_3 = PHI <a_1, a_2> 687169689Skan b_3 = PHI <b_1, a_3> 688169689Skan The a_3 referred to in b_3's PHI node is the one incoming on the 689169689Skan edge, *not* the PHI node just seen. */ 690169689Skan 691169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 692169689Skan { 693169689Skan var = PHI_RESULT (phi); 694169689Skan set_if_valid (map, saw_def, var); 695169689Skan } 696169689Skan 697169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 698169689Skan { 699169689Skan stmt = bsi_stmt (bsi); 700169689Skan 701169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) 702169689Skan { 703169689Skan add_livein_if_notdef (live, saw_def, op, bb); 704169689Skan } 705169689Skan 706169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 707169689Skan { 708169689Skan set_if_valid (map, saw_def, op); 709169689Skan } 710169689Skan } 711169689Skan } 712169689Skan 713169689Skan stack = XNEWVEC (int, last_basic_block); 714169689Skan EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi) 715169689Skan { 716169689Skan live_worklist (live, stack, i); 717169689Skan } 718169689Skan free (stack); 719169689Skan 720169689Skan#ifdef ENABLE_CHECKING 721169689Skan /* Check for live on entry partitions and report those with a DEF in 722169689Skan the program. This will typically mean an optimization has done 723169689Skan something wrong. */ 724169689Skan 725169689Skan bb = ENTRY_BLOCK_PTR; 726169689Skan num = 0; 727169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 728169689Skan { 729169689Skan int entry_block = e->dest->index; 730169689Skan if (e->dest == EXIT_BLOCK_PTR) 731169689Skan continue; 732169689Skan for (i = 0; i < (unsigned)num_var_partitions (map); i++) 733169689Skan { 734169689Skan basic_block tmp; 735169689Skan tree d; 736169689Skan var = partition_to_var (map, i); 737169689Skan stmt = SSA_NAME_DEF_STMT (var); 738169689Skan tmp = bb_for_stmt (stmt); 739169689Skan d = default_def (SSA_NAME_VAR (var)); 740169689Skan 741169689Skan if (bitmap_bit_p (live_entry_blocks (live, i), entry_block)) 742169689Skan { 743169689Skan if (!IS_EMPTY_STMT (stmt)) 744169689Skan { 745169689Skan num++; 746169689Skan print_generic_expr (stderr, var, TDF_SLIM); 747169689Skan fprintf (stderr, " is defined "); 748169689Skan if (tmp) 749169689Skan fprintf (stderr, " in BB%d, ", tmp->index); 750169689Skan fprintf (stderr, "by:\n"); 751169689Skan print_generic_expr (stderr, stmt, TDF_SLIM); 752169689Skan fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", 753169689Skan entry_block); 754169689Skan fprintf (stderr, " So it appears to have multiple defs.\n"); 755169689Skan } 756169689Skan else 757169689Skan { 758169689Skan if (d != var) 759169689Skan { 760169689Skan num++; 761169689Skan print_generic_expr (stderr, var, TDF_SLIM); 762169689Skan fprintf (stderr, " is live-on-entry to BB%d ",entry_block); 763169689Skan if (d) 764169689Skan { 765169689Skan fprintf (stderr, " but is not the default def of "); 766169689Skan print_generic_expr (stderr, d, TDF_SLIM); 767169689Skan fprintf (stderr, "\n"); 768169689Skan } 769169689Skan else 770169689Skan fprintf (stderr, " and there is no default def.\n"); 771169689Skan } 772169689Skan } 773169689Skan } 774169689Skan else 775169689Skan if (d == var) 776169689Skan { 777169689Skan /* The only way this var shouldn't be marked live on entry is 778169689Skan if it occurs in a PHI argument of the block. */ 779169689Skan int z, ok = 0; 780169689Skan for (phi = phi_nodes (e->dest); 781169689Skan phi && !ok; 782169689Skan phi = PHI_CHAIN (phi)) 783169689Skan { 784169689Skan for (z = 0; z < PHI_NUM_ARGS (phi); z++) 785169689Skan if (var == PHI_ARG_DEF (phi, z)) 786169689Skan { 787169689Skan ok = 1; 788169689Skan break; 789169689Skan } 790169689Skan } 791169689Skan if (ok) 792169689Skan continue; 793169689Skan num++; 794169689Skan print_generic_expr (stderr, var, TDF_SLIM); 795169689Skan fprintf (stderr, " is not marked live-on-entry to entry BB%d ", 796169689Skan entry_block); 797169689Skan fprintf (stderr, "but it is a default def so it should be.\n"); 798169689Skan } 799169689Skan } 800169689Skan } 801169689Skan gcc_assert (num <= 0); 802169689Skan#endif 803169689Skan 804169689Skan BITMAP_FREE (saw_def); 805169689Skan 806169689Skan return live; 807169689Skan} 808169689Skan 809169689Skan 810169689Skan/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ 811169689Skan 812169689Skanvoid 813169689Skancalculate_live_on_exit (tree_live_info_p liveinfo) 814169689Skan{ 815169689Skan unsigned b; 816169689Skan unsigned i, x; 817169689Skan bitmap *on_exit; 818169689Skan basic_block bb; 819169689Skan edge e; 820169689Skan tree t, phi; 821169689Skan bitmap on_entry; 822169689Skan var_map map = liveinfo->map; 823169689Skan 824169689Skan on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); 825169689Skan for (x = 0; x < (unsigned)last_basic_block; x++) 826169689Skan on_exit[x] = BITMAP_ALLOC (NULL); 827169689Skan 828169689Skan /* Set all the live-on-exit bits for uses in PHIs. */ 829169689Skan FOR_EACH_BB (bb) 830169689Skan { 831169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 832169689Skan for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) 833169689Skan { 834169689Skan t = PHI_ARG_DEF (phi, i); 835169689Skan e = PHI_ARG_EDGE (phi, i); 836169689Skan if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR) 837169689Skan continue; 838169689Skan set_if_valid (map, on_exit[e->src->index], t); 839169689Skan } 840169689Skan } 841169689Skan 842169689Skan /* Set live on exit for all predecessors of live on entry's. */ 843169689Skan for (i = 0; i < num_var_partitions (map); i++) 844169689Skan { 845169689Skan bitmap_iterator bi; 846169689Skan 847169689Skan on_entry = live_entry_blocks (liveinfo, i); 848169689Skan EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi) 849169689Skan { 850169689Skan edge_iterator ei; 851169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) 852169689Skan if (e->src != ENTRY_BLOCK_PTR) 853169689Skan bitmap_set_bit (on_exit[e->src->index], i); 854169689Skan } 855169689Skan } 856169689Skan 857169689Skan liveinfo->liveout = on_exit; 858169689Skan} 859169689Skan 860169689Skan 861169689Skan/* Initialize a tree_partition_associator object using MAP. */ 862169689Skan 863169689Skanstatic tpa_p 864169689Skantpa_init (var_map map) 865169689Skan{ 866169689Skan tpa_p tpa; 867169689Skan int num_partitions = num_var_partitions (map); 868169689Skan int x; 869169689Skan 870169689Skan if (num_partitions == 0) 871169689Skan return NULL; 872169689Skan 873169689Skan tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d)); 874169689Skan tpa->num_trees = 0; 875169689Skan tpa->uncompressed_num = -1; 876169689Skan tpa->map = map; 877169689Skan tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int)); 878169689Skan memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int)); 879169689Skan 880169689Skan tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int)); 881169689Skan memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int)); 882169689Skan 883169689Skan x = MAX (40, (num_partitions / 20)); 884169689Skan tpa->trees = VEC_alloc (tree, heap, x); 885169689Skan tpa->first_partition = VEC_alloc (int, heap, x); 886169689Skan 887169689Skan return tpa; 888169689Skan 889169689Skan} 890169689Skan 891169689Skan 892169689Skan/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */ 893169689Skan 894169689Skanvoid 895169689Skantpa_remove_partition (tpa_p tpa, int tree_index, int partition_index) 896169689Skan{ 897169689Skan int i; 898169689Skan 899169689Skan i = tpa_first_partition (tpa, tree_index); 900169689Skan if (i == partition_index) 901169689Skan { 902169689Skan VEC_replace (int, tpa->first_partition, tree_index, 903169689Skan tpa->next_partition[i]); 904169689Skan } 905169689Skan else 906169689Skan { 907169689Skan for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i)) 908169689Skan { 909169689Skan if (tpa->next_partition[i] == partition_index) 910169689Skan { 911169689Skan tpa->next_partition[i] = tpa->next_partition[partition_index]; 912169689Skan break; 913169689Skan } 914169689Skan } 915169689Skan } 916169689Skan} 917169689Skan 918169689Skan 919169689Skan/* Free the memory used by tree_partition_associator object TPA. */ 920169689Skan 921169689Skanvoid 922169689Skantpa_delete (tpa_p tpa) 923169689Skan{ 924169689Skan if (!tpa) 925169689Skan return; 926169689Skan 927169689Skan VEC_free (tree, heap, tpa->trees); 928169689Skan VEC_free (int, heap, tpa->first_partition); 929169689Skan free (tpa->partition_to_tree_map); 930169689Skan free (tpa->next_partition); 931169689Skan free (tpa); 932169689Skan} 933169689Skan 934169689Skan 935169689Skan/* This function will remove any tree entries from TPA which have only a single 936169689Skan element. This will help keep the size of the conflict graph down. The 937169689Skan function returns the number of remaining tree lists. */ 938169689Skan 939169689Skanint 940169689Skantpa_compact (tpa_p tpa) 941169689Skan{ 942169689Skan int last, x, y, first, swap_i; 943169689Skan tree swap_t; 944169689Skan 945169689Skan /* Find the last list which has more than 1 partition. */ 946169689Skan for (last = tpa->num_trees - 1; last > 0; last--) 947169689Skan { 948169689Skan first = tpa_first_partition (tpa, last); 949169689Skan if (tpa_next_partition (tpa, first) != NO_PARTITION) 950169689Skan break; 951169689Skan } 952169689Skan 953169689Skan x = 0; 954169689Skan while (x < last) 955169689Skan { 956169689Skan first = tpa_first_partition (tpa, x); 957169689Skan 958169689Skan /* If there is not more than one partition, swap with the current end 959169689Skan of the tree list. */ 960169689Skan if (tpa_next_partition (tpa, first) == NO_PARTITION) 961169689Skan { 962169689Skan swap_t = VEC_index (tree, tpa->trees, last); 963169689Skan swap_i = VEC_index (int, tpa->first_partition, last); 964169689Skan 965169689Skan /* Update the last entry. Since it is known to only have one 966169689Skan partition, there is nothing else to update. */ 967169689Skan VEC_replace (tree, tpa->trees, last, 968169689Skan VEC_index (tree, tpa->trees, x)); 969169689Skan VEC_replace (int, tpa->first_partition, last, 970169689Skan VEC_index (int, tpa->first_partition, x)); 971169689Skan tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last; 972169689Skan 973169689Skan /* Since this list is known to have more than one partition, update 974169689Skan the list owner entries. */ 975169689Skan VEC_replace (tree, tpa->trees, x, swap_t); 976169689Skan VEC_replace (int, tpa->first_partition, x, swap_i); 977169689Skan for (y = tpa_first_partition (tpa, x); 978169689Skan y != NO_PARTITION; 979169689Skan y = tpa_next_partition (tpa, y)) 980169689Skan tpa->partition_to_tree_map[y] = x; 981169689Skan 982169689Skan /* Ensure last is a list with more than one partition. */ 983169689Skan last--; 984169689Skan for (; last > x; last--) 985169689Skan { 986169689Skan first = tpa_first_partition (tpa, last); 987169689Skan if (tpa_next_partition (tpa, first) != NO_PARTITION) 988169689Skan break; 989169689Skan } 990169689Skan } 991169689Skan x++; 992169689Skan } 993169689Skan 994169689Skan first = tpa_first_partition (tpa, x); 995169689Skan if (tpa_next_partition (tpa, first) != NO_PARTITION) 996169689Skan x++; 997169689Skan tpa->uncompressed_num = tpa->num_trees; 998169689Skan tpa->num_trees = x; 999169689Skan return last; 1000169689Skan} 1001169689Skan 1002169689Skan 1003169689Skan/* Initialize a root_var object with SSA partitions from MAP which are based 1004169689Skan on each root variable. */ 1005169689Skan 1006169689Skanroot_var_p 1007169689Skanroot_var_init (var_map map) 1008169689Skan{ 1009169689Skan root_var_p rv; 1010169689Skan int num_partitions = num_var_partitions (map); 1011169689Skan int x, p; 1012169689Skan tree t; 1013169689Skan var_ann_t ann; 1014169689Skan sbitmap seen; 1015169689Skan 1016169689Skan rv = tpa_init (map); 1017169689Skan if (!rv) 1018169689Skan return NULL; 1019169689Skan 1020169689Skan seen = sbitmap_alloc (num_partitions); 1021169689Skan sbitmap_zero (seen); 1022169689Skan 1023169689Skan /* Start at the end and work towards the front. This will provide a list 1024169689Skan that is ordered from smallest to largest. */ 1025169689Skan for (x = num_partitions - 1; x >= 0; x--) 1026169689Skan { 1027169689Skan t = partition_to_var (map, x); 1028169689Skan 1029169689Skan /* The var map may not be compacted yet, so check for NULL. */ 1030169689Skan if (!t) 1031169689Skan continue; 1032169689Skan 1033169689Skan p = var_to_partition (map, t); 1034169689Skan 1035169689Skan gcc_assert (p != NO_PARTITION); 1036169689Skan 1037169689Skan /* Make sure we only put coalesced partitions into the list once. */ 1038169689Skan if (TEST_BIT (seen, p)) 1039169689Skan continue; 1040169689Skan SET_BIT (seen, p); 1041169689Skan if (TREE_CODE (t) == SSA_NAME) 1042169689Skan t = SSA_NAME_VAR (t); 1043169689Skan ann = var_ann (t); 1044169689Skan if (ann->root_var_processed) 1045169689Skan { 1046169689Skan rv->next_partition[p] = VEC_index (int, rv->first_partition, 1047169689Skan VAR_ANN_ROOT_INDEX (ann)); 1048169689Skan VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p); 1049169689Skan } 1050169689Skan else 1051169689Skan { 1052169689Skan ann->root_var_processed = 1; 1053169689Skan VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; 1054169689Skan VEC_safe_push (tree, heap, rv->trees, t); 1055169689Skan VEC_safe_push (int, heap, rv->first_partition, p); 1056169689Skan } 1057169689Skan rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann); 1058169689Skan } 1059169689Skan 1060169689Skan /* Reset the out_of_ssa_tag flag on each variable for later use. */ 1061169689Skan for (x = 0; x < rv->num_trees; x++) 1062169689Skan { 1063169689Skan t = VEC_index (tree, rv->trees, x); 1064169689Skan var_ann (t)->root_var_processed = 0; 1065169689Skan } 1066169689Skan 1067169689Skan sbitmap_free (seen); 1068169689Skan return rv; 1069169689Skan} 1070169689Skan 1071169689Skan 1072169689Skan/* Initialize a type_var structure which associates all the partitions in MAP 1073169689Skan of the same type to the type node's index. Volatiles are ignored. */ 1074169689Skan 1075169689Skantype_var_p 1076169689Skantype_var_init (var_map map) 1077169689Skan{ 1078169689Skan type_var_p tv; 1079169689Skan int x, y, p; 1080169689Skan int num_partitions = num_var_partitions (map); 1081169689Skan tree t; 1082169689Skan sbitmap seen; 1083169689Skan 1084169689Skan tv = tpa_init (map); 1085169689Skan if (!tv) 1086169689Skan return NULL; 1087169689Skan 1088169689Skan seen = sbitmap_alloc (num_partitions); 1089169689Skan sbitmap_zero (seen); 1090169689Skan 1091169689Skan for (x = num_partitions - 1; x >= 0; x--) 1092169689Skan { 1093169689Skan t = partition_to_var (map, x); 1094169689Skan 1095169689Skan /* Disallow coalescing of these types of variables. */ 1096169689Skan if (!t 1097169689Skan || TREE_THIS_VOLATILE (t) 1098169689Skan || TREE_CODE (t) == RESULT_DECL 1099169689Skan || TREE_CODE (t) == PARM_DECL 1100169689Skan || (DECL_P (t) 1101169689Skan && (DECL_REGISTER (t) 1102169689Skan || !DECL_IGNORED_P (t) 1103169689Skan || DECL_RTL_SET_P (t)))) 1104169689Skan continue; 1105169689Skan 1106169689Skan p = var_to_partition (map, t); 1107169689Skan 1108169689Skan gcc_assert (p != NO_PARTITION); 1109169689Skan 1110169689Skan /* If partitions have been coalesced, only add the representative 1111169689Skan for the partition to the list once. */ 1112169689Skan if (TEST_BIT (seen, p)) 1113169689Skan continue; 1114169689Skan SET_BIT (seen, p); 1115169689Skan t = TREE_TYPE (t); 1116169689Skan 1117169689Skan /* Find the list for this type. */ 1118169689Skan for (y = 0; y < tv->num_trees; y++) 1119169689Skan if (t == VEC_index (tree, tv->trees, y)) 1120169689Skan break; 1121169689Skan if (y == tv->num_trees) 1122169689Skan { 1123169689Skan tv->num_trees++; 1124169689Skan VEC_safe_push (tree, heap, tv->trees, t); 1125169689Skan VEC_safe_push (int, heap, tv->first_partition, p); 1126169689Skan } 1127169689Skan else 1128169689Skan { 1129169689Skan tv->next_partition[p] = VEC_index (int, tv->first_partition, y); 1130169689Skan VEC_replace (int, tv->first_partition, y, p); 1131169689Skan } 1132169689Skan tv->partition_to_tree_map[p] = y; 1133169689Skan } 1134169689Skan sbitmap_free (seen); 1135169689Skan return tv; 1136169689Skan} 1137169689Skan 1138169689Skan 1139169689Skan/* Create a new coalesce list object from MAP and return it. */ 1140169689Skan 1141169689Skancoalesce_list_p 1142169689Skancreate_coalesce_list (var_map map) 1143169689Skan{ 1144169689Skan coalesce_list_p list; 1145169689Skan 1146169689Skan list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); 1147169689Skan 1148169689Skan list->map = map; 1149169689Skan list->add_mode = true; 1150169689Skan list->list = (partition_pair_p *) xcalloc (num_var_partitions (map), 1151169689Skan sizeof (struct partition_pair_d)); 1152169689Skan return list; 1153169689Skan} 1154169689Skan 1155169689Skan 1156169689Skan/* Delete coalesce list CL. */ 1157169689Skan 1158169689Skanvoid 1159169689Skandelete_coalesce_list (coalesce_list_p cl) 1160169689Skan{ 1161169689Skan free (cl->list); 1162169689Skan free (cl); 1163169689Skan} 1164169689Skan 1165169689Skan 1166169689Skan/* Find a matching coalesce pair object in CL for partitions P1 and P2. If 1167169689Skan one isn't found, return NULL if CREATE is false, otherwise create a new 1168169689Skan coalesce pair object and return it. */ 1169169689Skan 1170169689Skanstatic partition_pair_p 1171169689Skanfind_partition_pair (coalesce_list_p cl, int p1, int p2, bool create) 1172169689Skan{ 1173169689Skan partition_pair_p node, tmp; 1174169689Skan int s; 1175169689Skan 1176169689Skan /* Normalize so that p1 is the smaller value. */ 1177169689Skan if (p2 < p1) 1178169689Skan { 1179169689Skan s = p1; 1180169689Skan p1 = p2; 1181169689Skan p2 = s; 1182169689Skan } 1183169689Skan 1184169689Skan tmp = NULL; 1185169689Skan 1186169689Skan /* The list is sorted such that if we find a value greater than p2, 1187169689Skan p2 is not in the list. */ 1188169689Skan for (node = cl->list[p1]; node; node = node->next) 1189169689Skan { 1190169689Skan if (node->second_partition == p2) 1191169689Skan return node; 1192169689Skan else 1193169689Skan if (node->second_partition > p2) 1194169689Skan break; 1195169689Skan tmp = node; 1196169689Skan } 1197169689Skan 1198169689Skan if (!create) 1199169689Skan return NULL; 1200169689Skan 1201169689Skan node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d)); 1202169689Skan node->first_partition = p1; 1203169689Skan node->second_partition = p2; 1204169689Skan node->cost = 0; 1205169689Skan 1206169689Skan if (tmp != NULL) 1207169689Skan { 1208169689Skan node->next = tmp->next; 1209169689Skan tmp->next = node; 1210169689Skan } 1211169689Skan else 1212169689Skan { 1213169689Skan /* This is now the first node in the list. */ 1214169689Skan node->next = cl->list[p1]; 1215169689Skan cl->list[p1] = node; 1216169689Skan } 1217169689Skan 1218169689Skan return node; 1219169689Skan} 1220169689Skan 1221169689Skan/* Return cost of execution of copy instruction with FREQUENCY 1222169689Skan possibly on CRITICAL edge and in HOT basic block. */ 1223169689Skanint 1224169689Skancoalesce_cost (int frequency, bool hot, bool critical) 1225169689Skan{ 1226169689Skan /* Base costs on BB frequencies bounded by 1. */ 1227169689Skan int cost = frequency; 1228169689Skan 1229169689Skan if (!cost) 1230169689Skan cost = 1; 1231169689Skan if (optimize_size || hot) 1232169689Skan cost = 1; 1233169689Skan /* Inserting copy on critical edge costs more 1234169689Skan than inserting it elsewhere. */ 1235169689Skan if (critical) 1236169689Skan cost *= 2; 1237169689Skan return cost; 1238169689Skan} 1239169689Skan 1240169689Skan/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */ 1241169689Skan 1242169689Skanvoid 1243169689Skanadd_coalesce (coalesce_list_p cl, int p1, int p2, 1244169689Skan int value) 1245169689Skan{ 1246169689Skan partition_pair_p node; 1247169689Skan 1248169689Skan gcc_assert (cl->add_mode); 1249169689Skan 1250169689Skan if (p1 == p2) 1251169689Skan return; 1252169689Skan 1253169689Skan node = find_partition_pair (cl, p1, p2, true); 1254169689Skan 1255169689Skan node->cost += value; 1256169689Skan} 1257169689Skan 1258169689Skan 1259169689Skan/* Comparison function to allow qsort to sort P1 and P2 in descending order. */ 1260169689Skan 1261169689Skanstatic 1262169689Skanint compare_pairs (const void *p1, const void *p2) 1263169689Skan{ 1264169689Skan return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost; 1265169689Skan} 1266169689Skan 1267169689Skan 1268169689Skan/* Prepare CL for removal of preferred pairs. When finished, list element 1269169689Skan 0 has all the coalesce pairs, sorted in order from most important coalesce 1270169689Skan to least important. */ 1271169689Skan 1272169689Skanvoid 1273169689Skansort_coalesce_list (coalesce_list_p cl) 1274169689Skan{ 1275169689Skan unsigned x, num, count; 1276169689Skan partition_pair_p chain, p; 1277169689Skan partition_pair_p *list; 1278169689Skan 1279169689Skan gcc_assert (cl->add_mode); 1280169689Skan 1281169689Skan cl->add_mode = false; 1282169689Skan 1283169689Skan /* Compact the array of lists to a single list, and count the elements. */ 1284169689Skan num = 0; 1285169689Skan chain = NULL; 1286169689Skan for (x = 0; x < num_var_partitions (cl->map); x++) 1287169689Skan if (cl->list[x] != NULL) 1288169689Skan { 1289169689Skan for (p = cl->list[x]; p->next != NULL; p = p->next) 1290169689Skan num++; 1291169689Skan num++; 1292169689Skan p->next = chain; 1293169689Skan chain = cl->list[x]; 1294169689Skan cl->list[x] = NULL; 1295169689Skan } 1296169689Skan 1297169689Skan /* Only call qsort if there are more than 2 items. */ 1298169689Skan if (num > 2) 1299169689Skan { 1300169689Skan list = XNEWVEC (partition_pair_p, num); 1301169689Skan count = 0; 1302169689Skan for (p = chain; p != NULL; p = p->next) 1303169689Skan list[count++] = p; 1304169689Skan 1305169689Skan gcc_assert (count == num); 1306169689Skan 1307169689Skan qsort (list, count, sizeof (partition_pair_p), compare_pairs); 1308169689Skan 1309169689Skan p = list[0]; 1310169689Skan for (x = 1; x < num; x++) 1311169689Skan { 1312169689Skan p->next = list[x]; 1313169689Skan p = list[x]; 1314169689Skan } 1315169689Skan p->next = NULL; 1316169689Skan cl->list[0] = list[0]; 1317169689Skan free (list); 1318169689Skan } 1319169689Skan else 1320169689Skan { 1321169689Skan cl->list[0] = chain; 1322169689Skan if (num == 2) 1323169689Skan { 1324169689Skan /* Simply swap the two elements if they are in the wrong order. */ 1325169689Skan if (chain->cost < chain->next->cost) 1326169689Skan { 1327169689Skan cl->list[0] = chain->next; 1328169689Skan cl->list[0]->next = chain; 1329169689Skan chain->next = NULL; 1330169689Skan } 1331169689Skan } 1332169689Skan } 1333169689Skan} 1334169689Skan 1335169689Skan 1336169689Skan/* Retrieve the best remaining pair to coalesce from CL. Returns the 2 1337169689Skan partitions via P1 and P2. Their calculated cost is returned by the function. 1338169689Skan NO_BEST_COALESCE is returned if the coalesce list is empty. */ 1339169689Skan 1340169689Skanstatic int 1341169689Skanpop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) 1342169689Skan{ 1343169689Skan partition_pair_p node; 1344169689Skan int ret; 1345169689Skan 1346169689Skan gcc_assert (!cl->add_mode); 1347169689Skan 1348169689Skan node = cl->list[0]; 1349169689Skan if (!node) 1350169689Skan return NO_BEST_COALESCE; 1351169689Skan 1352169689Skan cl->list[0] = node->next; 1353169689Skan 1354169689Skan *p1 = node->first_partition; 1355169689Skan *p2 = node->second_partition; 1356169689Skan ret = node->cost; 1357169689Skan free (node); 1358169689Skan 1359169689Skan return ret; 1360169689Skan} 1361169689Skan 1362169689Skan 1363169689Skan/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between 1364169689Skan VAR and any other live partitions in VEC which are associated via TPA. 1365169689Skan Reset the live bit in VEC. */ 1366169689Skan 1367169689Skanstatic inline void 1368169689Skanadd_conflicts_if_valid (tpa_p tpa, conflict_graph graph, 1369169689Skan var_map map, bitmap vec, tree var) 1370169689Skan{ 1371169689Skan int p, y, first; 1372169689Skan p = var_to_partition (map, var); 1373169689Skan if (p != NO_PARTITION) 1374169689Skan { 1375169689Skan bitmap_clear_bit (vec, p); 1376169689Skan first = tpa_find_tree (tpa, p); 1377169689Skan /* If find returns nothing, this object isn't interesting. */ 1378169689Skan if (first == TPA_NONE) 1379169689Skan return; 1380169689Skan /* Only add interferences between objects in the same list. */ 1381169689Skan for (y = tpa_first_partition (tpa, first); 1382169689Skan y != TPA_NONE; 1383169689Skan y = tpa_next_partition (tpa, y)) 1384169689Skan { 1385169689Skan if (bitmap_bit_p (vec, y)) 1386169689Skan conflict_graph_add (graph, p, y); 1387169689Skan } 1388169689Skan } 1389169689Skan} 1390169689Skan 1391169689Skan/* Return a conflict graph for the information contained in LIVE_INFO. Only 1392169689Skan conflicts between items in the same TPA list are added. If optional 1393169689Skan coalesce list CL is passed in, any copies encountered are added. */ 1394169689Skan 1395169689Skanconflict_graph 1396169689Skanbuild_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, 1397169689Skan coalesce_list_p cl) 1398169689Skan{ 1399169689Skan conflict_graph graph; 1400169689Skan var_map map; 1401169689Skan bitmap live; 1402169689Skan unsigned x, y, i; 1403169689Skan basic_block bb; 1404169689Skan int *partition_link, *tpa_nodes; 1405169689Skan VEC(int,heap) *tpa_to_clear; 1406169689Skan unsigned l; 1407169689Skan ssa_op_iter iter; 1408169689Skan bitmap_iterator bi; 1409169689Skan 1410169689Skan map = live_var_map (liveinfo); 1411169689Skan graph = conflict_graph_new (num_var_partitions (map)); 1412169689Skan 1413169689Skan if (tpa_num_trees (tpa) == 0) 1414169689Skan return graph; 1415169689Skan 1416169689Skan live = BITMAP_ALLOC (NULL); 1417169689Skan 1418169689Skan partition_link = XCNEWVEC (int, num_var_partitions (map) + 1); 1419169689Skan tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa)); 1420169689Skan tpa_to_clear = VEC_alloc (int, heap, 50); 1421169689Skan 1422169689Skan FOR_EACH_BB (bb) 1423169689Skan { 1424169689Skan block_stmt_iterator bsi; 1425169689Skan tree phi; 1426169689Skan int idx; 1427169689Skan 1428169689Skan /* Start with live on exit temporaries. */ 1429169689Skan bitmap_copy (live, live_on_exit (liveinfo, bb)); 1430169689Skan 1431169689Skan for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 1432169689Skan { 1433169689Skan bool is_a_copy = false; 1434169689Skan tree stmt = bsi_stmt (bsi); 1435169689Skan 1436169689Skan /* A copy between 2 partitions does not introduce an interference 1437169689Skan by itself. If they did, you would never be able to coalesce 1438169689Skan two things which are copied. If the two variables really do 1439169689Skan conflict, they will conflict elsewhere in the program. 1440169689Skan 1441169689Skan This is handled specially here since we may also be interested 1442169689Skan in copies between real variables and SSA_NAME variables. We may 1443169689Skan be interested in trying to coalesce SSA_NAME variables with 1444169689Skan root variables in some cases. */ 1445169689Skan 1446169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1447169689Skan { 1448169689Skan tree lhs = TREE_OPERAND (stmt, 0); 1449169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1450169689Skan int p1, p2; 1451169689Skan int bit; 1452169689Skan 1453169689Skan if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME) 1454169689Skan p1 = var_to_partition (map, lhs); 1455169689Skan else 1456169689Skan p1 = NO_PARTITION; 1457169689Skan 1458169689Skan if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME) 1459169689Skan p2 = var_to_partition (map, rhs); 1460169689Skan else 1461169689Skan p2 = NO_PARTITION; 1462169689Skan 1463169689Skan if (p1 != NO_PARTITION && p2 != NO_PARTITION) 1464169689Skan { 1465169689Skan is_a_copy = true; 1466169689Skan bit = bitmap_bit_p (live, p2); 1467169689Skan /* If the RHS is live, make it not live while we add 1468169689Skan the conflicts, then make it live again. */ 1469169689Skan if (bit) 1470169689Skan bitmap_clear_bit (live, p2); 1471169689Skan add_conflicts_if_valid (tpa, graph, map, live, lhs); 1472169689Skan if (bit) 1473169689Skan bitmap_set_bit (live, p2); 1474169689Skan if (cl) 1475169689Skan add_coalesce (cl, p1, p2, 1476169689Skan coalesce_cost (bb->frequency, 1477169689Skan maybe_hot_bb_p (bb), false)); 1478169689Skan set_if_valid (map, live, rhs); 1479169689Skan } 1480169689Skan } 1481169689Skan 1482169689Skan if (!is_a_copy) 1483169689Skan { 1484169689Skan tree var; 1485169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) 1486169689Skan { 1487169689Skan add_conflicts_if_valid (tpa, graph, map, live, var); 1488169689Skan } 1489169689Skan 1490169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 1491169689Skan { 1492169689Skan set_if_valid (map, live, var); 1493169689Skan } 1494169689Skan } 1495169689Skan } 1496169689Skan 1497169689Skan /* If result of a PHI is unused, then the loops over the statements 1498169689Skan will not record any conflicts. However, since the PHI node is 1499169689Skan going to be translated out of SSA form we must record a conflict 1500169689Skan between the result of the PHI and any variables with are live. 1501169689Skan Otherwise the out-of-ssa translation may create incorrect code. */ 1502169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1503169689Skan { 1504169689Skan tree result = PHI_RESULT (phi); 1505169689Skan int p = var_to_partition (map, result); 1506169689Skan 1507169689Skan if (p != NO_PARTITION && ! bitmap_bit_p (live, p)) 1508169689Skan add_conflicts_if_valid (tpa, graph, map, live, result); 1509169689Skan } 1510169689Skan 1511169689Skan /* Anything which is still live at this point interferes. 1512169689Skan In order to implement this efficiently, only conflicts between 1513169689Skan partitions which have the same TPA root need be added. 1514169689Skan TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero 1515169689Skan entry points to an index into 'partition_link', which then indexes 1516169689Skan into itself forming a linked list of partitions sharing a tpa root 1517169689Skan which have been seen as live up to this point. Since partitions start 1518169689Skan at index zero, all entries in partition_link are (partition + 1). 1519169689Skan 1520169689Skan Conflicts are added between the current partition and any already seen. 1521169689Skan tpa_clear contains all the tpa_roots processed, and these are the only 1522169689Skan entries which need to be zero'd out for a clean restart. */ 1523169689Skan 1524169689Skan EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi) 1525169689Skan { 1526169689Skan i = tpa_find_tree (tpa, x); 1527169689Skan if (i != (unsigned)TPA_NONE) 1528169689Skan { 1529169689Skan int start = tpa_nodes[i]; 1530169689Skan /* If start is 0, a new root reference list is being started. 1531169689Skan Register it to be cleared. */ 1532169689Skan if (!start) 1533169689Skan VEC_safe_push (int, heap, tpa_to_clear, i); 1534169689Skan 1535169689Skan /* Add interferences to other tpa members seen. */ 1536169689Skan for (y = start; y != 0; y = partition_link[y]) 1537169689Skan conflict_graph_add (graph, x, y - 1); 1538169689Skan tpa_nodes[i] = x + 1; 1539169689Skan partition_link[x + 1] = start; 1540169689Skan } 1541169689Skan } 1542169689Skan 1543169689Skan /* Now clear the used tpa root references. */ 1544169689Skan for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++) 1545169689Skan tpa_nodes[idx] = 0; 1546169689Skan VEC_truncate (int, tpa_to_clear, 0); 1547169689Skan } 1548169689Skan 1549169689Skan free (tpa_nodes); 1550169689Skan free (partition_link); 1551169689Skan VEC_free (int, heap, tpa_to_clear); 1552169689Skan BITMAP_FREE (live); 1553169689Skan return graph; 1554169689Skan} 1555169689Skan 1556169689Skan 1557169689Skan/* This routine will attempt to coalesce the elements in TPA subject to the 1558169689Skan conflicts found in GRAPH. If optional coalesce_list CL is provided, 1559169689Skan only coalesces specified within the coalesce list are attempted. Otherwise 1560169689Skan an attempt is made to coalesce as many partitions within each TPA grouping 1561169689Skan as possible. If DEBUG is provided, debug output will be sent there. */ 1562169689Skan 1563169689Skanvoid 1564169689Skancoalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, 1565169689Skan coalesce_list_p cl, FILE *debug) 1566169689Skan{ 1567169689Skan int x, y, z, w; 1568169689Skan tree var, tmp; 1569169689Skan 1570169689Skan /* Attempt to coalesce any items in a coalesce list. */ 1571169689Skan if (cl) 1572169689Skan { 1573169689Skan while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE) 1574169689Skan { 1575169689Skan if (debug) 1576169689Skan { 1577169689Skan fprintf (debug, "Coalesce list: (%d)", x); 1578169689Skan print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM); 1579169689Skan fprintf (debug, " & (%d)", y); 1580169689Skan print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM); 1581169689Skan } 1582169689Skan 1583169689Skan w = tpa_find_tree (tpa, x); 1584169689Skan z = tpa_find_tree (tpa, y); 1585169689Skan if (w != z || w == TPA_NONE || z == TPA_NONE) 1586169689Skan { 1587169689Skan if (debug) 1588169689Skan { 1589169689Skan if (w != z) 1590169689Skan fprintf (debug, ": Fail, Non-matching TPA's\n"); 1591169689Skan if (w == TPA_NONE) 1592169689Skan fprintf (debug, ": Fail %d non TPA.\n", x); 1593169689Skan else 1594169689Skan fprintf (debug, ": Fail %d non TPA.\n", y); 1595169689Skan } 1596169689Skan continue; 1597169689Skan } 1598169689Skan var = partition_to_var (map, x); 1599169689Skan tmp = partition_to_var (map, y); 1600169689Skan x = var_to_partition (map, var); 1601169689Skan y = var_to_partition (map, tmp); 1602169689Skan if (debug) 1603169689Skan fprintf (debug, " [map: %d, %d] ", x, y); 1604169689Skan if (x == y) 1605169689Skan { 1606169689Skan if (debug) 1607169689Skan fprintf (debug, ": Already Coalesced.\n"); 1608169689Skan continue; 1609169689Skan } 1610169689Skan if (!conflict_graph_conflict_p (graph, x, y)) 1611169689Skan { 1612169689Skan z = var_union (map, var, tmp); 1613169689Skan if (z == NO_PARTITION) 1614169689Skan { 1615169689Skan if (debug) 1616169689Skan fprintf (debug, ": Unable to perform partition union.\n"); 1617169689Skan continue; 1618169689Skan } 1619169689Skan 1620169689Skan /* z is the new combined partition. We need to remove the other 1621169689Skan partition from the list. Set x to be that other partition. */ 1622169689Skan if (z == x) 1623169689Skan { 1624169689Skan conflict_graph_merge_regs (graph, x, y); 1625169689Skan w = tpa_find_tree (tpa, y); 1626169689Skan tpa_remove_partition (tpa, w, y); 1627169689Skan } 1628169689Skan else 1629169689Skan { 1630169689Skan conflict_graph_merge_regs (graph, y, x); 1631169689Skan w = tpa_find_tree (tpa, x); 1632169689Skan tpa_remove_partition (tpa, w, x); 1633169689Skan } 1634169689Skan 1635169689Skan if (debug) 1636169689Skan fprintf (debug, ": Success -> %d\n", z); 1637169689Skan } 1638169689Skan else 1639169689Skan if (debug) 1640169689Skan fprintf (debug, ": Fail due to conflict\n"); 1641169689Skan } 1642169689Skan /* If using a coalesce list, don't try to coalesce anything else. */ 1643169689Skan return; 1644169689Skan } 1645169689Skan 1646169689Skan for (x = 0; x < tpa_num_trees (tpa); x++) 1647169689Skan { 1648169689Skan while (tpa_first_partition (tpa, x) != TPA_NONE) 1649169689Skan { 1650169689Skan int p1, p2; 1651169689Skan /* Coalesce first partition with anything that doesn't conflict. */ 1652169689Skan y = tpa_first_partition (tpa, x); 1653169689Skan tpa_remove_partition (tpa, x, y); 1654169689Skan 1655169689Skan var = partition_to_var (map, y); 1656169689Skan /* p1 is the partition representative to which y belongs. */ 1657169689Skan p1 = var_to_partition (map, var); 1658169689Skan 1659169689Skan for (z = tpa_next_partition (tpa, y); 1660169689Skan z != TPA_NONE; 1661169689Skan z = tpa_next_partition (tpa, z)) 1662169689Skan { 1663169689Skan tmp = partition_to_var (map, z); 1664169689Skan /* p2 is the partition representative to which z belongs. */ 1665169689Skan p2 = var_to_partition (map, tmp); 1666169689Skan if (debug) 1667169689Skan { 1668169689Skan fprintf (debug, "Coalesce : "); 1669169689Skan print_generic_expr (debug, var, TDF_SLIM); 1670169689Skan fprintf (debug, " &"); 1671169689Skan print_generic_expr (debug, tmp, TDF_SLIM); 1672169689Skan fprintf (debug, " (%d ,%d)", p1, p2); 1673169689Skan } 1674169689Skan 1675169689Skan /* If partitions are already merged, don't check for conflict. */ 1676169689Skan if (tmp == var) 1677169689Skan { 1678169689Skan tpa_remove_partition (tpa, x, z); 1679169689Skan if (debug) 1680169689Skan fprintf (debug, ": Already coalesced\n"); 1681169689Skan } 1682169689Skan else 1683169689Skan if (!conflict_graph_conflict_p (graph, p1, p2)) 1684169689Skan { 1685169689Skan int v; 1686169689Skan if (tpa_find_tree (tpa, y) == TPA_NONE 1687169689Skan || tpa_find_tree (tpa, z) == TPA_NONE) 1688169689Skan { 1689169689Skan if (debug) 1690169689Skan fprintf (debug, ": Fail non-TPA member\n"); 1691169689Skan continue; 1692169689Skan } 1693169689Skan if ((v = var_union (map, var, tmp)) == NO_PARTITION) 1694169689Skan { 1695169689Skan if (debug) 1696169689Skan fprintf (debug, ": Fail cannot combine partitions\n"); 1697169689Skan continue; 1698169689Skan } 1699169689Skan 1700169689Skan tpa_remove_partition (tpa, x, z); 1701169689Skan if (v == p1) 1702169689Skan conflict_graph_merge_regs (graph, v, z); 1703169689Skan else 1704169689Skan { 1705169689Skan /* Update the first partition's representative. */ 1706169689Skan conflict_graph_merge_regs (graph, v, y); 1707169689Skan p1 = v; 1708169689Skan } 1709169689Skan 1710169689Skan /* The root variable of the partition may be changed 1711169689Skan now. */ 1712169689Skan var = partition_to_var (map, p1); 1713169689Skan 1714169689Skan if (debug) 1715169689Skan fprintf (debug, ": Success -> %d\n", v); 1716169689Skan } 1717169689Skan else 1718169689Skan if (debug) 1719169689Skan fprintf (debug, ": Fail, Conflict\n"); 1720169689Skan } 1721169689Skan } 1722169689Skan } 1723169689Skan} 1724169689Skan 1725169689Skan 1726169689Skan/* Send debug info for coalesce list CL to file F. */ 1727169689Skan 1728169689Skanvoid 1729169689Skandump_coalesce_list (FILE *f, coalesce_list_p cl) 1730169689Skan{ 1731169689Skan partition_pair_p node; 1732169689Skan int x, num; 1733169689Skan tree var; 1734169689Skan 1735169689Skan if (cl->add_mode) 1736169689Skan { 1737169689Skan fprintf (f, "Coalesce List:\n"); 1738169689Skan num = num_var_partitions (cl->map); 1739169689Skan for (x = 0; x < num; x++) 1740169689Skan { 1741169689Skan node = cl->list[x]; 1742169689Skan if (node) 1743169689Skan { 1744169689Skan fprintf (f, "["); 1745169689Skan print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM); 1746169689Skan fprintf (f, "] - "); 1747169689Skan for ( ; node; node = node->next) 1748169689Skan { 1749169689Skan var = partition_to_var (cl->map, node->second_partition); 1750169689Skan print_generic_expr (f, var, TDF_SLIM); 1751169689Skan fprintf (f, "(%1d), ", node->cost); 1752169689Skan } 1753169689Skan fprintf (f, "\n"); 1754169689Skan } 1755169689Skan } 1756169689Skan } 1757169689Skan else 1758169689Skan { 1759169689Skan fprintf (f, "Sorted Coalesce list:\n"); 1760169689Skan for (node = cl->list[0]; node; node = node->next) 1761169689Skan { 1762169689Skan fprintf (f, "(%d) ", node->cost); 1763169689Skan var = partition_to_var (cl->map, node->first_partition); 1764169689Skan print_generic_expr (f, var, TDF_SLIM); 1765169689Skan fprintf (f, " : "); 1766169689Skan var = partition_to_var (cl->map, node->second_partition); 1767169689Skan print_generic_expr (f, var, TDF_SLIM); 1768169689Skan fprintf (f, "\n"); 1769169689Skan } 1770169689Skan } 1771169689Skan} 1772169689Skan 1773169689Skan 1774169689Skan/* Output tree_partition_associator object TPA to file F.. */ 1775169689Skan 1776169689Skanvoid 1777169689Skantpa_dump (FILE *f, tpa_p tpa) 1778169689Skan{ 1779169689Skan int x, i; 1780169689Skan 1781169689Skan if (!tpa) 1782169689Skan return; 1783169689Skan 1784169689Skan for (x = 0; x < tpa_num_trees (tpa); x++) 1785169689Skan { 1786169689Skan print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM); 1787169689Skan fprintf (f, " : ("); 1788169689Skan for (i = tpa_first_partition (tpa, x); 1789169689Skan i != TPA_NONE; 1790169689Skan i = tpa_next_partition (tpa, i)) 1791169689Skan { 1792169689Skan fprintf (f, "(%d)",i); 1793169689Skan print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM); 1794169689Skan fprintf (f, " "); 1795169689Skan 1796169689Skan#ifdef ENABLE_CHECKING 1797169689Skan if (tpa_find_tree (tpa, i) != x) 1798169689Skan fprintf (f, "**find tree incorrectly set** "); 1799169689Skan#endif 1800169689Skan 1801169689Skan } 1802169689Skan fprintf (f, ")\n"); 1803169689Skan } 1804169689Skan fflush (f); 1805169689Skan} 1806169689Skan 1807169689Skan 1808169689Skan/* Output partition map MAP to file F. */ 1809169689Skan 1810169689Skanvoid 1811169689Skandump_var_map (FILE *f, var_map map) 1812169689Skan{ 1813169689Skan int t; 1814169689Skan unsigned x, y; 1815169689Skan int p; 1816169689Skan 1817169689Skan fprintf (f, "\nPartition map \n\n"); 1818169689Skan 1819169689Skan for (x = 0; x < map->num_partitions; x++) 1820169689Skan { 1821169689Skan if (map->compact_to_partition != NULL) 1822169689Skan p = map->compact_to_partition[x]; 1823169689Skan else 1824169689Skan p = x; 1825169689Skan 1826169689Skan if (map->partition_to_var[p] == NULL_TREE) 1827169689Skan continue; 1828169689Skan 1829169689Skan t = 0; 1830169689Skan for (y = 1; y < num_ssa_names; y++) 1831169689Skan { 1832169689Skan p = partition_find (map->var_partition, y); 1833169689Skan if (map->partition_to_compact) 1834169689Skan p = map->partition_to_compact[p]; 1835169689Skan if (p == (int)x) 1836169689Skan { 1837169689Skan if (t++ == 0) 1838169689Skan { 1839169689Skan fprintf(f, "Partition %d (", x); 1840169689Skan print_generic_expr (f, partition_to_var (map, p), TDF_SLIM); 1841169689Skan fprintf (f, " - "); 1842169689Skan } 1843169689Skan fprintf (f, "%d ", y); 1844169689Skan } 1845169689Skan } 1846169689Skan if (t != 0) 1847169689Skan fprintf (f, ")\n"); 1848169689Skan } 1849169689Skan fprintf (f, "\n"); 1850169689Skan} 1851169689Skan 1852169689Skan 1853169689Skan/* Output live range info LIVE to file F, controlled by FLAG. */ 1854169689Skan 1855169689Skanvoid 1856169689Skandump_live_info (FILE *f, tree_live_info_p live, int flag) 1857169689Skan{ 1858169689Skan basic_block bb; 1859169689Skan unsigned i; 1860169689Skan var_map map = live->map; 1861169689Skan bitmap_iterator bi; 1862169689Skan 1863169689Skan if ((flag & LIVEDUMP_ENTRY) && live->livein) 1864169689Skan { 1865169689Skan FOR_EACH_BB (bb) 1866169689Skan { 1867169689Skan fprintf (f, "\nLive on entry to BB%d : ", bb->index); 1868169689Skan for (i = 0; i < num_var_partitions (map); i++) 1869169689Skan { 1870169689Skan if (bitmap_bit_p (live_entry_blocks (live, i), bb->index)) 1871169689Skan { 1872169689Skan print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); 1873169689Skan fprintf (f, " "); 1874169689Skan } 1875169689Skan } 1876169689Skan fprintf (f, "\n"); 1877169689Skan } 1878169689Skan } 1879169689Skan 1880169689Skan if ((flag & LIVEDUMP_EXIT) && live->liveout) 1881169689Skan { 1882169689Skan FOR_EACH_BB (bb) 1883169689Skan { 1884169689Skan fprintf (f, "\nLive on exit from BB%d : ", bb->index); 1885169689Skan EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi) 1886169689Skan { 1887169689Skan print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); 1888169689Skan fprintf (f, " "); 1889169689Skan } 1890169689Skan fprintf (f, "\n"); 1891169689Skan } 1892169689Skan } 1893169689Skan} 1894169689Skan 1895169689Skan#ifdef ENABLE_CHECKING 1896169689Skanvoid 1897169689Skanregister_ssa_partition_check (tree ssa_var) 1898169689Skan{ 1899169689Skan gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); 1900169689Skan if (!is_gimple_reg (SSA_NAME_VAR (ssa_var))) 1901169689Skan { 1902169689Skan fprintf (stderr, "Illegally registering a virtual SSA name :"); 1903169689Skan print_generic_expr (stderr, ssa_var, TDF_SLIM); 1904169689Skan fprintf (stderr, " in the SSA->Normal phase.\n"); 1905169689Skan internal_error ("SSA corruption"); 1906169689Skan } 1907169689Skan} 1908169689Skan#endif 1909