1303231Sdim/* Liveness for SSA trees. 2303231Sdim Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3353358Sdim Contributed by Andrew MacLeod <amacleod@redhat.com> 4353358Sdim 5353358SdimThis file is part of GCC. 6303231Sdim 7303231SdimGCC is free software; you can redistribute it and/or modify 8303231Sdimit under the terms of the GNU General Public License as published by 9303231Sdimthe Free Software Foundation; either version 2, or (at your option) 10303231Sdimany later version. 11303231Sdim 12303231SdimGCC is distributed in the hope that it will be useful, 13303231Sdimbut WITHOUT ANY WARRANTY; without even the implied warranty of 14303231SdimMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15341825SdimGNU General Public License for more details. 16303231Sdim 17303231SdimYou should have received a copy of the GNU General Public License 18303231Sdimalong with GCC; see the file COPYING. If not, write to 19303231Sdimthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20303231SdimBoston, MA 02110-1301, USA. */ 21303231Sdim 22341825Sdim#include "config.h" 23303231Sdim#include "system.h" 24341825Sdim#include "coretypes.h" 25303231Sdim#include "tm.h" 26303231Sdim#include "tree.h" 27341825Sdim#include "flags.h" 28303231Sdim#include "basic-block.h" 29303231Sdim#include "function.h" 30303231Sdim#include "diagnostic.h" 31303231Sdim#include "bitmap.h" 32303231Sdim#include "tree-flow.h" 33303231Sdim#include "tree-gimple.h" 34341825Sdim#include "tree-inline.h" 35341825Sdim#include "varray.h" 36341825Sdim#include "timevar.h" 37341825Sdim#include "hashtab.h" 38341825Sdim#include "tree-dump.h" 39341825Sdim#include "tree-ssa-live.h" 40341825Sdim#include "toplev.h" 41341825Sdim#include "vecprim.h" 42341825Sdim 43341825Sdimstatic void live_worklist (tree_live_info_p, int *, int); 44341825Sdimstatic tree_live_info_p new_tree_live_info (var_map); 45341825Sdimstatic inline void set_if_valid (var_map, bitmap, tree); 46341825Sdimstatic inline void add_livein_if_notdef (tree_live_info_p, bitmap, 47360784Sdim tree, basic_block); 48341825Sdimstatic inline void register_ssa_partition (var_map, tree, bool); 49341825Sdimstatic inline void add_conflicts_if_valid (tpa_p, conflict_graph, 50341825Sdim var_map, bitmap, tree); 51341825Sdimstatic partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool); 52341825Sdim 53341825Sdim/* This is where the mapping from SSA version number to real storage variable 54341825Sdim is tracked. 55341825Sdim 56341825Sdim All SSA versions of the same variable may not ultimately be mapped back to 57341825Sdim the same real variable. In that instance, we need to detect the live 58341825Sdim range overlap, and give one of the variable new storage. The vector 59341825Sdim 'partition_to_var' tracks which partition maps to which variable. 60341825Sdim 61341825Sdim Given a VAR, it is sometimes desirable to know which partition that VAR 62341825Sdim represents. There is an additional field in the variable annotation to 63341825Sdim track that information. */ 64341825Sdim 65341825Sdim/* Create a variable partition map of SIZE, initialize and return it. */ 66360784Sdim 67341825Sdimvar_map 68341825Sdiminit_var_map (int size) 69341825Sdim{ 70341825Sdim var_map map; 71341825Sdim 72341825Sdim map = (var_map) xmalloc (sizeof (struct _var_map)); 73341825Sdim map->var_partition = partition_new (size); 74341825Sdim map->partition_to_var 75341825Sdim = (tree *)xmalloc (size * sizeof (tree)); 76341825Sdim memset (map->partition_to_var, 0, size * sizeof (tree)); 77341825Sdim 78341825Sdim map->partition_to_compact = NULL; 79341825Sdim map->compact_to_partition = NULL; 80341825Sdim map->num_partitions = size; 81341825Sdim map->partition_size = size; 82341825Sdim map->ref_count = NULL; 83341825Sdim return map; 84341825Sdim} 85341825Sdim 86341825Sdim 87341825Sdim/* Free memory associated with MAP. */ 88303231Sdim 89303231Sdimvoid 90341825Sdimdelete_var_map (var_map map) 91341825Sdim{ 92341825Sdim free (map->partition_to_var); 93341825Sdim partition_delete (map->var_partition); 94303231Sdim if (map->partition_to_compact) 95303231Sdim free (map->partition_to_compact); 96303231Sdim if (map->compact_to_partition) 97303231Sdim free (map->compact_to_partition); 98303231Sdim if (map->ref_count) 99303231Sdim free (map->ref_count); 100303231Sdim free (map); 101303231Sdim} 102303231Sdim 103341825Sdim 104341825Sdim/* This function will combine the partitions in MAP for VAR1 and VAR2. It 105341825Sdim Returns the partition which represents the new partition. If the two 106341825Sdim partitions cannot be combined, NO_PARTITION is returned. */ 107341825Sdim 108303231Sdimint 109341825Sdimvar_union (var_map map, tree var1, tree var2) 110303231Sdim{ 111303231Sdim int p1, p2, p3; 112303231Sdim tree root_var = NULL_TREE; 113303231Sdim tree other_var = NULL_TREE; 114303231Sdim 115303231Sdim /* This is independent of partition_to_compact. If partition_to_compact is 116341825Sdim on, then whichever one of these partitions is absorbed will never have a 117303231Sdim dereference into the partition_to_compact array any more. */ 118341825Sdim 119341825Sdim if (TREE_CODE (var1) == SSA_NAME) 120341825Sdim p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); 121341825Sdim else 122341825Sdim { 123341825Sdim p1 = var_to_partition (map, var1); 124341825Sdim if (map->compact_to_partition) 125341825Sdim p1 = map->compact_to_partition[p1]; 126303231Sdim root_var = var1; 127303231Sdim } 128341825Sdim 129341825Sdim if (TREE_CODE (var2) == SSA_NAME) 130341825Sdim p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); 131341825Sdim else 132303231Sdim { 133303231Sdim p2 = var_to_partition (map, var2); 134341825Sdim if (map->compact_to_partition) 135341825Sdim p2 = map->compact_to_partition[p2]; 136341825Sdim 137360784Sdim /* If there is no root_var set, or it's not a user variable, set the 138341825Sdim root_var to this one. */ 139341825Sdim if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var))) 140341825Sdim { 141341825Sdim other_var = root_var; 142341825Sdim root_var = var2; 143341825Sdim } 144353358Sdim else 145341825Sdim other_var = var2; 146341825Sdim } 147341825Sdim 148341825Sdim gcc_assert (p1 != NO_PARTITION); 149341825Sdim gcc_assert (p2 != NO_PARTITION); 150341825Sdim 151341825Sdim if (p1 == p2) 152341825Sdim p3 = p1; 153341825Sdim else 154341825Sdim p3 = partition_union (map->var_partition, p1, p2); 155303231Sdim 156303231Sdim if (map->partition_to_compact) 157344779Sdim p3 = map->partition_to_compact[p3]; 158344779Sdim 159344779Sdim if (root_var) 160344779Sdim change_partition_var (map, root_var, p3); 161344779Sdim if (other_var) 162344779Sdim change_partition_var (map, other_var, p3); 163344779Sdim 164344779Sdim return p3; 165344779Sdim} 166341825Sdim 167341825Sdim 168341825Sdim/* Compress the partition numbers in MAP such that they fall in the range 169341825Sdim 0..(num_partitions-1) instead of wherever they turned out during 170303231Sdim the partitioning exercise. This removes any references to unused 171303231Sdim partitions, thereby allowing bitmaps and other vectors to be much 172341825Sdim denser. Compression type is controlled by FLAGS. 173341825Sdim 174341825Sdim This is implemented such that compaction doesn't affect partitioning. 175341825Sdim Ie., once partitions are created and possibly merged, running one 176341825Sdim or more different kind of compaction will not affect the partitions 177341825Sdim themselves. Their index might change, but all the same variables will 178341825Sdim still be members of the same partition group. This allows work on reduced 179341825Sdim sets, and no loss of information when a larger set is later desired. 180341825Sdim 181341825Sdim In particular, coalescing can work on partitions which have 2 or more 182341825Sdim definitions, and then 'recompact' later to include all the single 183341825Sdim definitions for assignment to program variables. */ 184341825Sdim 185341825Sdimvoid 186341825Sdimcompact_var_map (var_map map, int flags) 187341825Sdim{ 188341825Sdim sbitmap used; 189303231Sdim int tmp, root, root_i; 190303231Sdim unsigned int x, limit, count; 191303231Sdim tree var; 192303231Sdim root_var_p rv = NULL; 193341825Sdim 194341825Sdim limit = map->partition_size; 195341825Sdim used = sbitmap_alloc (limit); 196341825Sdim sbitmap_zero (used); 197303231Sdim 198341825Sdim /* Already compressed? Abandon the old one. */ 199341825Sdim if (map->partition_to_compact) 200341825Sdim { 201303231Sdim free (map->partition_to_compact); 202341825Sdim map->partition_to_compact = NULL; 203341825Sdim } 204303231Sdim if (map->compact_to_partition) 205303231Sdim { 206341825Sdim free (map->compact_to_partition); 207341825Sdim map->compact_to_partition = NULL; 208341825Sdim } 209341825Sdim 210341825Sdim map->num_partitions = map->partition_size; 211341825Sdim 212341825Sdim if (flags & VARMAP_NO_SINGLE_DEFS) 213303231Sdim rv = root_var_init (map); 214341825Sdim 215341825Sdim map->partition_to_compact = (int *)xmalloc (limit * sizeof (int)); 216341825Sdim memset (map->partition_to_compact, 0xff, (limit * sizeof (int))); 217341825Sdim 218341825Sdim /* Find out which partitions are actually referenced. */ 219341825Sdim count = 0; 220341825Sdim for (x = 0; x < limit; x++) 221341825Sdim { 222341825Sdim tmp = partition_find (map->var_partition, x); 223341825Sdim if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE) 224341825Sdim { 225341825Sdim /* It is referenced, check to see if there is more than one version 226341825Sdim in the root_var table, if one is available. */ 227341825Sdim if (rv) 228341825Sdim { 229341825Sdim root = root_var_find (rv, tmp); 230341825Sdim root_i = root_var_first_partition (rv, root); 231341825Sdim /* If there is only one, don't include this in the compaction. */ 232341825Sdim if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE) 233341825Sdim continue; 234341825Sdim } 235341825Sdim SET_BIT (used, tmp); 236341825Sdim count++; 237341825Sdim } 238341825Sdim } 239341825Sdim 240341825Sdim /* Build a compacted partitioning. */ 241341825Sdim if (count != limit) 242341825Sdim { 243341825Sdim sbitmap_iterator sbi; 244341825Sdim 245341825Sdim map->compact_to_partition = (int *)xmalloc (count * sizeof (int)); 246341825Sdim count = 0; 247341825Sdim /* SSA renaming begins at 1, so skip 0 when compacting. */ 248341825Sdim EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi) 249341825Sdim { 250341825Sdim map->partition_to_compact[x] = count; 251341825Sdim map->compact_to_partition[count] = x; 252341825Sdim var = map->partition_to_var[x]; 253341825Sdim if (TREE_CODE (var) != SSA_NAME) 254341825Sdim change_partition_var (map, var, count); 255341825Sdim count++; 256341825Sdim } 257341825Sdim } 258341825Sdim else 259341825Sdim { 260341825Sdim free (map->partition_to_compact); 261341825Sdim map->partition_to_compact = NULL; 262341825Sdim } 263341825Sdim 264341825Sdim map->num_partitions = count; 265341825Sdim 266341825Sdim if (rv) 267341825Sdim root_var_delete (rv); 268341825Sdim sbitmap_free (used); 269341825Sdim} 270303231Sdim 271303231Sdim 272341825Sdim/* This function is used to change the representative variable in MAP for VAR's 273303231Sdim partition from an SSA_NAME variable to a regular variable. This allows 274303231Sdim partitions to be mapped back to real variables. */ 275341825Sdim 276341825Sdimvoid 277341825Sdimchange_partition_var (var_map map, tree var, int part) 278341825Sdim{ 279303231Sdim var_ann_t ann; 280341825Sdim 281341825Sdim gcc_assert (TREE_CODE (var) != SSA_NAME); 282341825Sdim 283341825Sdim ann = var_ann (var); 284341825Sdim ann->out_of_ssa_tag = 1; 285341825Sdim VAR_ANN_PARTITION (ann) = part; 286341825Sdim if (map->compact_to_partition) 287341825Sdim map->partition_to_var[map->compact_to_partition[part]] = var; 288341825Sdim} 289341825Sdim 290341825Sdimstatic inline void mark_all_vars_used (tree *); 291341825Sdim 292341825Sdim/* Helper function for mark_all_vars_used, called via walk_tree. */ 293341825Sdim 294341825Sdimstatic tree 295341825Sdimmark_all_vars_used_1 (tree *tp, int *walk_subtrees, 296341825Sdim void *data ATTRIBUTE_UNUSED) 297341825Sdim{ 298341825Sdim tree t = *tp; 299341825Sdim 300341825Sdim if (TREE_CODE (t) == SSA_NAME) 301341825Sdim t = SSA_NAME_VAR (t); 302341825Sdim 303341825Sdim /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other 304341825Sdim fields that do not contain vars. */ 305341825Sdim if (TREE_CODE (t) == TARGET_MEM_REF) 306341825Sdim { 307341825Sdim mark_all_vars_used (&TMR_SYMBOL (t)); 308341825Sdim mark_all_vars_used (&TMR_BASE (t)); 309341825Sdim mark_all_vars_used (&TMR_INDEX (t)); 310303231Sdim *walk_subtrees = 0; 311341825Sdim return NULL; 312341825Sdim } 313341825Sdim 314341825Sdim /* Only need to mark VAR_DECLS; parameters and return results are not 315341825Sdim eliminated as unused. */ 316341825Sdim if (TREE_CODE (t) == VAR_DECL) 317341825Sdim set_is_used (t); 318341825Sdim 319341825Sdim if (IS_TYPE_OR_DECL_P (t)) 320341825Sdim *walk_subtrees = 0; 321341825Sdim 322341825Sdim return NULL; 323341825Sdim} 324341825Sdim 325341825Sdim/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be 326341825Sdim eliminated during the tree->rtl conversion process. */ 327341825Sdim 328341825Sdimstatic inline void 329341825Sdimmark_all_vars_used (tree *expr_p) 330303231Sdim{ 331341825Sdim walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL); 332341825Sdim} 333341825Sdim 334341825Sdim 335341825Sdim/* Remove local variables that are not referenced in the IL. */ 336341825Sdim 337341825Sdimvoid 338341825Sdimremove_unused_locals (void) 339341825Sdim{ 340341825Sdim basic_block bb; 341341825Sdim tree t, *cell; 342341825Sdim 343341825Sdim /* Assume all locals are unused. */ 344341825Sdim for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t)) 345341825Sdim { 346341825Sdim tree var = TREE_VALUE (t); 347341825Sdim if (TREE_CODE (var) != FUNCTION_DECL 348341825Sdim && var_ann (var)) 349341825Sdim var_ann (var)->used = false; 350341825Sdim } 351341825Sdim 352341825Sdim /* Walk the CFG marking all referenced symbols. */ 353341825Sdim FOR_EACH_BB (bb) 354341825Sdim { 355341825Sdim block_stmt_iterator bsi; 356341825Sdim tree phi, def; 357303231Sdim 358303231Sdim /* Walk the statements. */ 359341825Sdim for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 360341825Sdim mark_all_vars_used (bsi_stmt_ptr (bsi)); 361341825Sdim 362341825Sdim for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 363341825Sdim { 364341825Sdim use_operand_p arg_p; 365341825Sdim ssa_op_iter i; 366341825Sdim 367341825Sdim /* No point processing globals. */ 368341825Sdim if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi)))) 369341825Sdim continue; 370303231Sdim 371303231Sdim def = PHI_RESULT (phi); 372341825Sdim mark_all_vars_used (&def); 373341825Sdim 374341825Sdim FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES) 375341825Sdim { 376341825Sdim tree arg = USE_FROM_PTR (arg_p); 377341825Sdim mark_all_vars_used (&arg); 378341825Sdim } 379341825Sdim } 380341825Sdim } 381341825Sdim 382341825Sdim /* Remove unmarked vars and clear used flag. */ 383341825Sdim for (cell = &cfun->unexpanded_var_list; *cell; ) 384303231Sdim { 385341825Sdim tree var = TREE_VALUE (*cell); 386341825Sdim var_ann_t ann; 387341825Sdim 388341825Sdim if (TREE_CODE (var) != FUNCTION_DECL 389341825Sdim && (!(ann = var_ann (var)) 390341825Sdim || !ann->used)) 391341825Sdim { 392341825Sdim *cell = TREE_CHAIN (*cell); 393341825Sdim continue; 394341825Sdim } 395303231Sdim 396341825Sdim cell = &TREE_CHAIN (*cell); 397341825Sdim } 398341825Sdim} 399341825Sdim 400303231Sdim/* This function looks through the program and uses FLAGS to determine what 401341825Sdim SSA versioned variables are given entries in a new partition table. This 402341825Sdim new partition map is returned. */ 403341825Sdim 404341825Sdimvar_map 405341825Sdimcreate_ssa_var_map (int flags) 406341825Sdim{ 407341825Sdim block_stmt_iterator bsi; 408303231Sdim basic_block bb; 409341825Sdim tree dest, use; 410341825Sdim tree stmt; 411341825Sdim var_map map; 412341825Sdim ssa_op_iter iter; 413341825Sdim#ifdef ENABLE_CHECKING 414341825Sdim bitmap used_in_real_ops; 415341825Sdim bitmap used_in_virtual_ops; 416341825Sdim#endif 417341825Sdim 418341825Sdim map = init_var_map (num_ssa_names + 1); 419303231Sdim 420341825Sdim#ifdef ENABLE_CHECKING 421341825Sdim used_in_real_ops = BITMAP_ALLOC (NULL); 422341825Sdim used_in_virtual_ops = BITMAP_ALLOC (NULL); 423341825Sdim#endif 424341825Sdim 425341825Sdim if (flags & SSA_VAR_MAP_REF_COUNT) 426341825Sdim { 427341825Sdim map->ref_count 428341825Sdim = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int))); 429341825Sdim memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int)); 430344779Sdim } 431344779Sdim 432344779Sdim FOR_EACH_BB (bb) 433344779Sdim { 434344779Sdim tree phi, arg; 435344779Sdim 436344779Sdim for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 437344779Sdim { 438344779Sdim int i; 439341825Sdim register_ssa_partition (map, PHI_RESULT (phi), false); 440341825Sdim for (i = 0; i < PHI_NUM_ARGS (phi); i++) 441341825Sdim { 442341825Sdim arg = PHI_ARG_DEF (phi, i); 443341825Sdim if (TREE_CODE (arg) == SSA_NAME) 444341825Sdim register_ssa_partition (map, arg, true); 445303231Sdim 446303231Sdim mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i)); 447341825Sdim } 448341825Sdim } 449303231Sdim 450341825Sdim for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 451341825Sdim { 452341825Sdim stmt = bsi_stmt (bsi); 453341825Sdim 454341825Sdim /* Register USE and DEF operands in each statement. */ 455341825Sdim FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE) 456341825Sdim { 457341825Sdim register_ssa_partition (map, use, true); 458341825Sdim 459341825Sdim#ifdef ENABLE_CHECKING 460341825Sdim bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use))); 461341825Sdim#endif 462303231Sdim } 463303231Sdim 464341825Sdim FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF) 465341825Sdim { 466303231Sdim register_ssa_partition (map, dest, false); 467341825Sdim 468341825Sdim#ifdef ENABLE_CHECKING 469341825Sdim bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest))); 470341825Sdim#endif 471341825Sdim } 472341825Sdim 473341825Sdim#ifdef ENABLE_CHECKING 474341825Sdim /* Validate that virtual ops don't get used in funny ways. */ 475341825Sdim FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, 476341825Sdim SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF) 477341825Sdim { 478303231Sdim bitmap_set_bit (used_in_virtual_ops, 479303231Sdim DECL_UID (SSA_NAME_VAR (use))); 480341825Sdim } 481341825Sdim 482341825Sdim#endif /* ENABLE_CHECKING */ 483303231Sdim 484341825Sdim mark_all_vars_used (bsi_stmt_ptr (bsi)); 485341825Sdim } 486341825Sdim } 487341825Sdim 488341825Sdim#if defined ENABLE_CHECKING 489341825Sdim { 490341825Sdim unsigned i; 491341825Sdim bitmap both = BITMAP_ALLOC (NULL); 492341825Sdim bitmap_and (both, used_in_real_ops, used_in_virtual_ops); 493303231Sdim if (!bitmap_empty_p (both)) 494341825Sdim { 495303231Sdim bitmap_iterator bi; 496341825Sdim 497303231Sdim EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) 498341825Sdim fprintf (stderr, "Variable %s used in real and virtual operands\n", 499360784Sdim get_name (referenced_var (i))); 500341825Sdim internal_error ("SSA corruption"); 501341825Sdim } 502341825Sdim 503303231Sdim BITMAP_FREE (used_in_real_ops); 504341825Sdim BITMAP_FREE (used_in_virtual_ops); 505341825Sdim BITMAP_FREE (both); 506341825Sdim } 507341825Sdim#endif 508341825Sdim 509341825Sdim return map; 510341825Sdim} 511341825Sdim 512341825Sdim 513341825Sdim/* Allocate and return a new live range information object base on MAP. */ 514303231Sdim 515341825Sdimstatic tree_live_info_p 516303231Sdimnew_tree_live_info (var_map map) 517341825Sdim{ 518341825Sdim tree_live_info_p live; 519341825Sdim unsigned x; 520341825Sdim 521341825Sdim live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); 522341825Sdim live->map = map; 523341825Sdim live->num_blocks = last_basic_block; 524341825Sdim 525341825Sdim live->global = BITMAP_ALLOC (NULL); 526341825Sdim 527341825Sdim live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap)); 528341825Sdim for (x = 0; x < num_var_partitions (map); x++) 529341825Sdim live->livein[x] = BITMAP_ALLOC (NULL); 530341825Sdim 531341825Sdim /* liveout is deferred until it is actually requested. */ 532341825Sdim live->liveout = NULL; 533341825Sdim return live; 534303231Sdim} 535303231Sdim 536303231Sdim 537341825Sdim/* Free storage for live range info object LIVE. */ 538341825Sdim 539303231Sdimvoid 540341825Sdimdelete_tree_live_info (tree_live_info_p live) 541341825Sdim{ 542341825Sdim int x; 543341825Sdim if (live->liveout) 544360784Sdim { 545341825Sdim for (x = live->num_blocks - 1; x >= 0; x--) 546341825Sdim BITMAP_FREE (live->liveout[x]); 547341825Sdim free (live->liveout); 548341825Sdim } 549341825Sdim if (live->livein) 550341825Sdim { 551341825Sdim for (x = num_var_partitions (live->map) - 1; x >= 0; x--) 552341825Sdim BITMAP_FREE (live->livein[x]); 553341825Sdim free (live->livein); 554341825Sdim } 555303231Sdim if (live->global) 556303231Sdim BITMAP_FREE (live->global); 557341825Sdim 558341825Sdim free (live); 559341825Sdim} 560341825Sdim 561341825Sdim 562303231Sdim/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses 563341825Sdim for partition I. STACK is a varray used for temporary memory which is 564341825Sdim passed in rather than being allocated on every call. */ 565303231Sdim 566341825Sdimstatic void 567341825Sdimlive_worklist (tree_live_info_p live, int *stack, int i) 568341825Sdim{ 569341825Sdim unsigned b; 570341825Sdim tree var; 571341825Sdim basic_block def_bb = NULL; 572341825Sdim edge e; 573341825Sdim var_map map = live->map; 574341825Sdim edge_iterator ei; 575303231Sdim bitmap_iterator bi; 576341825Sdim int *tos = stack; 577341825Sdim 578341825Sdim var = partition_to_var (map, i); 579303231Sdim if (SSA_NAME_DEF_STMT (var)) 580360784Sdim def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 581341825Sdim 582303231Sdim EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi) 583303231Sdim { 584341825Sdim *tos++ = b; 585341825Sdim } 586341825Sdim 587341825Sdim while (tos != stack) 588341825Sdim { 589341825Sdim b = *--tos; 590341825Sdim 591341825Sdim FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) 592341825Sdim if (e->src != ENTRY_BLOCK_PTR) 593341825Sdim { 594303231Sdim /* Its not live on entry to the block its defined in. */ 595303231Sdim if (e->src == def_bb) 596341825Sdim continue; 597341825Sdim if (!bitmap_bit_p (live->livein[i], e->src->index)) 598341825Sdim { 599341825Sdim bitmap_set_bit (live->livein[i], e->src->index); 600341825Sdim *tos++ = e->src->index; 601341825Sdim } 602353358Sdim } 603353358Sdim } 604353358Sdim} 605353358Sdim 606341825Sdim 607341825Sdim/* If VAR is in a partition of MAP, set the bit for that partition in VEC. */ 608341825Sdim 609341825Sdimstatic inline void 610341825Sdimset_if_valid (var_map map, bitmap vec, tree var) 611341825Sdim{ 612341825Sdim int p = var_to_partition (map, var); 613341825Sdim if (p != NO_PARTITION) 614353358Sdim bitmap_set_bit (vec, p); 615341825Sdim} 616341825Sdim 617341825Sdim 618341825Sdim/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and 619341825Sdim global bit for it in the LIVE object. BB is the block being processed. */ 620341825Sdim 621341825Sdimstatic inline void 622341825Sdimadd_livein_if_notdef (tree_live_info_p live, bitmap def_vec, 623341825Sdim tree var, basic_block bb) 624341825Sdim{ 625341825Sdim int p = var_to_partition (live->map, var); 626341825Sdim if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR) 627341825Sdim return; 628341825Sdim if (!bitmap_bit_p (def_vec, p)) 629341825Sdim { 630341825Sdim bitmap_set_bit (live->livein[p], bb->index); 631341825Sdim bitmap_set_bit (live->global, p); 632341825Sdim } 633341825Sdim} 634341825Sdim 635303231Sdim 636341825Sdim/* Given partition map MAP, calculate all the live on entry bitmaps for 637341825Sdim each basic block. Return a live info object. */ 638341825Sdim 639341825Sdimtree_live_info_p 640341825Sdimcalculate_live_on_entry (var_map map) 641341825Sdim{ 642341825Sdim tree_live_info_p live; 643341825Sdim unsigned i; 644341825Sdim basic_block bb; 645341825Sdim bitmap saw_def; 646341825Sdim tree phi, var, stmt; 647341825Sdim tree op; 648341825Sdim edge e; 649341825Sdim int *stack; 650360784Sdim block_stmt_iterator bsi; 651341825Sdim ssa_op_iter iter; 652341825Sdim bitmap_iterator bi; 653341825Sdim#ifdef ENABLE_CHECKING 654341825Sdim int num; 655341825Sdim edge_iterator ei; 656341825Sdim#endif 657353358Sdim 658353358Sdim saw_def = BITMAP_ALLOC (NULL); 659341825Sdim 660341825Sdim live = new_tree_live_info (map); 661341825Sdim 662341825Sdim FOR_EACH_BB (bb) 663341825Sdim { 664341825Sdim bitmap_clear (saw_def); 665341825Sdim 666341825Sdim for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 667360784Sdim { 668341825Sdim for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) 669341825Sdim { 670341825Sdim var = PHI_ARG_DEF (phi, i); 671341825Sdim if (!phi_ssa_name_p (var)) 672341825Sdim continue; 673341825Sdim stmt = SSA_NAME_DEF_STMT (var); 674341825Sdim e = EDGE_PRED (bb, i); 675341825Sdim 676341825Sdim /* Any uses in PHIs which either don't have def's or are not 677341825Sdim defined in the block from which the def comes, will be live 678353358Sdim on entry to that block. */ 679353358Sdim if (!stmt || e->src != bb_for_stmt (stmt)) 680353358Sdim add_livein_if_notdef (live, saw_def, var, e->src); 681353358Sdim } 682341825Sdim } 683341825Sdim 684341825Sdim /* Don't mark PHI results as defined until all the PHI nodes have 685341825Sdim been processed. If the PHI sequence is: 686341825Sdim a_3 = PHI <a_1, a_2> 687341825Sdim b_3 = PHI <b_1, a_3> 688341825Sdim The a_3 referred to in b_3's PHI node is the one incoming on the 689341825Sdim edge, *not* the PHI node just seen. */ 690341825Sdim 691341825Sdim for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 692341825Sdim { 693341825Sdim var = PHI_RESULT (phi); 694341825Sdim set_if_valid (map, saw_def, var); 695341825Sdim } 696341825Sdim 697341825Sdim for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 698341825Sdim { 699341825Sdim stmt = bsi_stmt (bsi); 700341825Sdim 701341825Sdim FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) 702341825Sdim { 703341825Sdim add_livein_if_notdef (live, saw_def, op, bb); 704341825Sdim } 705341825Sdim 706341825Sdim FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 707341825Sdim { 708341825Sdim set_if_valid (map, saw_def, op); 709353358Sdim } 710353358Sdim } 711353358Sdim } 712353358Sdim 713341825Sdim stack = XNEWVEC (int, last_basic_block); 714341825Sdim EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi) 715341825Sdim { 716341825Sdim live_worklist (live, stack, i); 717341825Sdim } 718341825Sdim free (stack); 719341825Sdim 720341825Sdim#ifdef ENABLE_CHECKING 721303231Sdim /* Check for live on entry partitions and report those with a DEF in 722303231Sdim the program. This will typically mean an optimization has done 723303231Sdim something wrong. */ 724303231Sdim 725303231Sdim bb = ENTRY_BLOCK_PTR; 726303231Sdim num = 0; 727341825Sdim FOR_EACH_EDGE (e, ei, bb->succs) 728341825Sdim { 729341825Sdim int entry_block = e->dest->index; 730341825Sdim if (e->dest == EXIT_BLOCK_PTR) 731341825Sdim continue; 732341825Sdim for (i = 0; i < (unsigned)num_var_partitions (map); i++) 733341825Sdim { 734341825Sdim basic_block tmp; 735341825Sdim tree d; 736360784Sdim var = partition_to_var (map, i); 737341825Sdim stmt = SSA_NAME_DEF_STMT (var); 738341825Sdim tmp = bb_for_stmt (stmt); 739341825Sdim d = default_def (SSA_NAME_VAR (var)); 740341825Sdim 741341825Sdim if (bitmap_bit_p (live_entry_blocks (live, i), entry_block)) 742341825Sdim { 743341825Sdim if (!IS_EMPTY_STMT (stmt)) 744341825Sdim { 745341825Sdim num++; 746360784Sdim print_generic_expr (stderr, var, TDF_SLIM); 747341825Sdim fprintf (stderr, " is defined "); 748341825Sdim if (tmp) 749341825Sdim fprintf (stderr, " in BB%d, ", tmp->index); 750341825Sdim fprintf (stderr, "by:\n"); 751341825Sdim print_generic_expr (stderr, stmt, TDF_SLIM); 752341825Sdim fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", 753341825Sdim entry_block); 754341825Sdim fprintf (stderr, " So it appears to have multiple defs.\n"); 755341825Sdim } 756341825Sdim else 757341825Sdim { 758341825Sdim if (d != var) 759341825Sdim { 760341825Sdim num++; 761341825Sdim print_generic_expr (stderr, var, TDF_SLIM); 762341825Sdim fprintf (stderr, " is live-on-entry to BB%d ",entry_block); 763341825Sdim if (d) 764341825Sdim { 765341825Sdim fprintf (stderr, " but is not the default def of "); 766341825Sdim print_generic_expr (stderr, d, TDF_SLIM); 767341825Sdim fprintf (stderr, "\n"); 768341825Sdim } 769341825Sdim else 770341825Sdim fprintf (stderr, " and there is no default def.\n"); 771341825Sdim } 772341825Sdim } 773341825Sdim } 774303231Sdim else 775341825Sdim if (d == var) 776341825Sdim { 777341825Sdim /* The only way this var shouldn't be marked live on entry is 778341825Sdim if it occurs in a PHI argument of the block. */ 779341825Sdim int z, ok = 0; 780341825Sdim for (phi = phi_nodes (e->dest); 781341825Sdim phi && !ok; 782341825Sdim phi = PHI_CHAIN (phi)) 783341825Sdim { 784341825Sdim for (z = 0; z < PHI_NUM_ARGS (phi); z++) 785341825Sdim if (var == PHI_ARG_DEF (phi, z)) 786341825Sdim { 787303231Sdim ok = 1; 788303231Sdim break; 789303231Sdim } 790303231Sdim } 791303231Sdim if (ok) 792303231Sdim continue; 793303231Sdim num++; 794303231Sdim print_generic_expr (stderr, var, TDF_SLIM); 795303231Sdim fprintf (stderr, " is not marked live-on-entry to entry BB%d ", 796 entry_block); 797 fprintf (stderr, "but it is a default def so it should be.\n"); 798 } 799 } 800 } 801 gcc_assert (num <= 0); 802#endif 803 804 BITMAP_FREE (saw_def); 805 806 return live; 807} 808 809 810/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ 811 812void 813calculate_live_on_exit (tree_live_info_p liveinfo) 814{ 815 unsigned b; 816 unsigned i, x; 817 bitmap *on_exit; 818 basic_block bb; 819 edge e; 820 tree t, phi; 821 bitmap on_entry; 822 var_map map = liveinfo->map; 823 824 on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); 825 for (x = 0; x < (unsigned)last_basic_block; x++) 826 on_exit[x] = BITMAP_ALLOC (NULL); 827 828 /* Set all the live-on-exit bits for uses in PHIs. */ 829 FOR_EACH_BB (bb) 830 { 831 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 832 for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) 833 { 834 t = PHI_ARG_DEF (phi, i); 835 e = PHI_ARG_EDGE (phi, i); 836 if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR) 837 continue; 838 set_if_valid (map, on_exit[e->src->index], t); 839 } 840 } 841 842 /* Set live on exit for all predecessors of live on entry's. */ 843 for (i = 0; i < num_var_partitions (map); i++) 844 { 845 bitmap_iterator bi; 846 847 on_entry = live_entry_blocks (liveinfo, i); 848 EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi) 849 { 850 edge_iterator ei; 851 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) 852 if (e->src != ENTRY_BLOCK_PTR) 853 bitmap_set_bit (on_exit[e->src->index], i); 854 } 855 } 856 857 liveinfo->liveout = on_exit; 858} 859 860 861/* Initialize a tree_partition_associator object using MAP. */ 862 863static tpa_p 864tpa_init (var_map map) 865{ 866 tpa_p tpa; 867 int num_partitions = num_var_partitions (map); 868 int x; 869 870 if (num_partitions == 0) 871 return NULL; 872 873 tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d)); 874 tpa->num_trees = 0; 875 tpa->uncompressed_num = -1; 876 tpa->map = map; 877 tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int)); 878 memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int)); 879 880 tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int)); 881 memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int)); 882 883 x = MAX (40, (num_partitions / 20)); 884 tpa->trees = VEC_alloc (tree, heap, x); 885 tpa->first_partition = VEC_alloc (int, heap, x); 886 887 return tpa; 888 889} 890 891 892/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */ 893 894void 895tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index) 896{ 897 int i; 898 899 i = tpa_first_partition (tpa, tree_index); 900 if (i == partition_index) 901 { 902 VEC_replace (int, tpa->first_partition, tree_index, 903 tpa->next_partition[i]); 904 } 905 else 906 { 907 for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i)) 908 { 909 if (tpa->next_partition[i] == partition_index) 910 { 911 tpa->next_partition[i] = tpa->next_partition[partition_index]; 912 break; 913 } 914 } 915 } 916} 917 918 919/* Free the memory used by tree_partition_associator object TPA. */ 920 921void 922tpa_delete (tpa_p tpa) 923{ 924 if (!tpa) 925 return; 926 927 VEC_free (tree, heap, tpa->trees); 928 VEC_free (int, heap, tpa->first_partition); 929 free (tpa->partition_to_tree_map); 930 free (tpa->next_partition); 931 free (tpa); 932} 933 934 935/* This function will remove any tree entries from TPA which have only a single 936 element. This will help keep the size of the conflict graph down. The 937 function returns the number of remaining tree lists. */ 938 939int 940tpa_compact (tpa_p tpa) 941{ 942 int last, x, y, first, swap_i; 943 tree swap_t; 944 945 /* Find the last list which has more than 1 partition. */ 946 for (last = tpa->num_trees - 1; last > 0; last--) 947 { 948 first = tpa_first_partition (tpa, last); 949 if (tpa_next_partition (tpa, first) != NO_PARTITION) 950 break; 951 } 952 953 x = 0; 954 while (x < last) 955 { 956 first = tpa_first_partition (tpa, x); 957 958 /* If there is not more than one partition, swap with the current end 959 of the tree list. */ 960 if (tpa_next_partition (tpa, first) == NO_PARTITION) 961 { 962 swap_t = VEC_index (tree, tpa->trees, last); 963 swap_i = VEC_index (int, tpa->first_partition, last); 964 965 /* Update the last entry. Since it is known to only have one 966 partition, there is nothing else to update. */ 967 VEC_replace (tree, tpa->trees, last, 968 VEC_index (tree, tpa->trees, x)); 969 VEC_replace (int, tpa->first_partition, last, 970 VEC_index (int, tpa->first_partition, x)); 971 tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last; 972 973 /* Since this list is known to have more than one partition, update 974 the list owner entries. */ 975 VEC_replace (tree, tpa->trees, x, swap_t); 976 VEC_replace (int, tpa->first_partition, x, swap_i); 977 for (y = tpa_first_partition (tpa, x); 978 y != NO_PARTITION; 979 y = tpa_next_partition (tpa, y)) 980 tpa->partition_to_tree_map[y] = x; 981 982 /* Ensure last is a list with more than one partition. */ 983 last--; 984 for (; last > x; last--) 985 { 986 first = tpa_first_partition (tpa, last); 987 if (tpa_next_partition (tpa, first) != NO_PARTITION) 988 break; 989 } 990 } 991 x++; 992 } 993 994 first = tpa_first_partition (tpa, x); 995 if (tpa_next_partition (tpa, first) != NO_PARTITION) 996 x++; 997 tpa->uncompressed_num = tpa->num_trees; 998 tpa->num_trees = x; 999 return last; 1000} 1001 1002 1003/* Initialize a root_var object with SSA partitions from MAP which are based 1004 on each root variable. */ 1005 1006root_var_p 1007root_var_init (var_map map) 1008{ 1009 root_var_p rv; 1010 int num_partitions = num_var_partitions (map); 1011 int x, p; 1012 tree t; 1013 var_ann_t ann; 1014 sbitmap seen; 1015 1016 rv = tpa_init (map); 1017 if (!rv) 1018 return NULL; 1019 1020 seen = sbitmap_alloc (num_partitions); 1021 sbitmap_zero (seen); 1022 1023 /* Start at the end and work towards the front. This will provide a list 1024 that is ordered from smallest to largest. */ 1025 for (x = num_partitions - 1; x >= 0; x--) 1026 { 1027 t = partition_to_var (map, x); 1028 1029 /* The var map may not be compacted yet, so check for NULL. */ 1030 if (!t) 1031 continue; 1032 1033 p = var_to_partition (map, t); 1034 1035 gcc_assert (p != NO_PARTITION); 1036 1037 /* Make sure we only put coalesced partitions into the list once. */ 1038 if (TEST_BIT (seen, p)) 1039 continue; 1040 SET_BIT (seen, p); 1041 if (TREE_CODE (t) == SSA_NAME) 1042 t = SSA_NAME_VAR (t); 1043 ann = var_ann (t); 1044 if (ann->root_var_processed) 1045 { 1046 rv->next_partition[p] = VEC_index (int, rv->first_partition, 1047 VAR_ANN_ROOT_INDEX (ann)); 1048 VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p); 1049 } 1050 else 1051 { 1052 ann->root_var_processed = 1; 1053 VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; 1054 VEC_safe_push (tree, heap, rv->trees, t); 1055 VEC_safe_push (int, heap, rv->first_partition, p); 1056 } 1057 rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann); 1058 } 1059 1060 /* Reset the out_of_ssa_tag flag on each variable for later use. */ 1061 for (x = 0; x < rv->num_trees; x++) 1062 { 1063 t = VEC_index (tree, rv->trees, x); 1064 var_ann (t)->root_var_processed = 0; 1065 } 1066 1067 sbitmap_free (seen); 1068 return rv; 1069} 1070 1071 1072/* Initialize a type_var structure which associates all the partitions in MAP 1073 of the same type to the type node's index. Volatiles are ignored. */ 1074 1075type_var_p 1076type_var_init (var_map map) 1077{ 1078 type_var_p tv; 1079 int x, y, p; 1080 int num_partitions = num_var_partitions (map); 1081 tree t; 1082 sbitmap seen; 1083 1084 tv = tpa_init (map); 1085 if (!tv) 1086 return NULL; 1087 1088 seen = sbitmap_alloc (num_partitions); 1089 sbitmap_zero (seen); 1090 1091 for (x = num_partitions - 1; x >= 0; x--) 1092 { 1093 t = partition_to_var (map, x); 1094 1095 /* Disallow coalescing of these types of variables. */ 1096 if (!t 1097 || TREE_THIS_VOLATILE (t) 1098 || TREE_CODE (t) == RESULT_DECL 1099 || TREE_CODE (t) == PARM_DECL 1100 || (DECL_P (t) 1101 && (DECL_REGISTER (t) 1102 || !DECL_IGNORED_P (t) 1103 || DECL_RTL_SET_P (t)))) 1104 continue; 1105 1106 p = var_to_partition (map, t); 1107 1108 gcc_assert (p != NO_PARTITION); 1109 1110 /* If partitions have been coalesced, only add the representative 1111 for the partition to the list once. */ 1112 if (TEST_BIT (seen, p)) 1113 continue; 1114 SET_BIT (seen, p); 1115 t = TREE_TYPE (t); 1116 1117 /* Find the list for this type. */ 1118 for (y = 0; y < tv->num_trees; y++) 1119 if (t == VEC_index (tree, tv->trees, y)) 1120 break; 1121 if (y == tv->num_trees) 1122 { 1123 tv->num_trees++; 1124 VEC_safe_push (tree, heap, tv->trees, t); 1125 VEC_safe_push (int, heap, tv->first_partition, p); 1126 } 1127 else 1128 { 1129 tv->next_partition[p] = VEC_index (int, tv->first_partition, y); 1130 VEC_replace (int, tv->first_partition, y, p); 1131 } 1132 tv->partition_to_tree_map[p] = y; 1133 } 1134 sbitmap_free (seen); 1135 return tv; 1136} 1137 1138 1139/* Create a new coalesce list object from MAP and return it. */ 1140 1141coalesce_list_p 1142create_coalesce_list (var_map map) 1143{ 1144 coalesce_list_p list; 1145 1146 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); 1147 1148 list->map = map; 1149 list->add_mode = true; 1150 list->list = (partition_pair_p *) xcalloc (num_var_partitions (map), 1151 sizeof (struct partition_pair_d)); 1152 return list; 1153} 1154 1155 1156/* Delete coalesce list CL. */ 1157 1158void 1159delete_coalesce_list (coalesce_list_p cl) 1160{ 1161 free (cl->list); 1162 free (cl); 1163} 1164 1165 1166/* Find a matching coalesce pair object in CL for partitions P1 and P2. If 1167 one isn't found, return NULL if CREATE is false, otherwise create a new 1168 coalesce pair object and return it. */ 1169 1170static partition_pair_p 1171find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create) 1172{ 1173 partition_pair_p node, tmp; 1174 int s; 1175 1176 /* Normalize so that p1 is the smaller value. */ 1177 if (p2 < p1) 1178 { 1179 s = p1; 1180 p1 = p2; 1181 p2 = s; 1182 } 1183 1184 tmp = NULL; 1185 1186 /* The list is sorted such that if we find a value greater than p2, 1187 p2 is not in the list. */ 1188 for (node = cl->list[p1]; node; node = node->next) 1189 { 1190 if (node->second_partition == p2) 1191 return node; 1192 else 1193 if (node->second_partition > p2) 1194 break; 1195 tmp = node; 1196 } 1197 1198 if (!create) 1199 return NULL; 1200 1201 node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d)); 1202 node->first_partition = p1; 1203 node->second_partition = p2; 1204 node->cost = 0; 1205 1206 if (tmp != NULL) 1207 { 1208 node->next = tmp->next; 1209 tmp->next = node; 1210 } 1211 else 1212 { 1213 /* This is now the first node in the list. */ 1214 node->next = cl->list[p1]; 1215 cl->list[p1] = node; 1216 } 1217 1218 return node; 1219} 1220 1221/* Return cost of execution of copy instruction with FREQUENCY 1222 possibly on CRITICAL edge and in HOT basic block. */ 1223int 1224coalesce_cost (int frequency, bool hot, bool critical) 1225{ 1226 /* Base costs on BB frequencies bounded by 1. */ 1227 int cost = frequency; 1228 1229 if (!cost) 1230 cost = 1; 1231 if (optimize_size || hot) 1232 cost = 1; 1233 /* Inserting copy on critical edge costs more 1234 than inserting it elsewhere. */ 1235 if (critical) 1236 cost *= 2; 1237 return cost; 1238} 1239 1240/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */ 1241 1242void 1243add_coalesce (coalesce_list_p cl, int p1, int p2, 1244 int value) 1245{ 1246 partition_pair_p node; 1247 1248 gcc_assert (cl->add_mode); 1249 1250 if (p1 == p2) 1251 return; 1252 1253 node = find_partition_pair (cl, p1, p2, true); 1254 1255 node->cost += value; 1256} 1257 1258 1259/* Comparison function to allow qsort to sort P1 and P2 in descending order. */ 1260 1261static 1262int compare_pairs (const void *p1, const void *p2) 1263{ 1264 return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost; 1265} 1266 1267 1268/* Prepare CL for removal of preferred pairs. When finished, list element 1269 0 has all the coalesce pairs, sorted in order from most important coalesce 1270 to least important. */ 1271 1272void 1273sort_coalesce_list (coalesce_list_p cl) 1274{ 1275 unsigned x, num, count; 1276 partition_pair_p chain, p; 1277 partition_pair_p *list; 1278 1279 gcc_assert (cl->add_mode); 1280 1281 cl->add_mode = false; 1282 1283 /* Compact the array of lists to a single list, and count the elements. */ 1284 num = 0; 1285 chain = NULL; 1286 for (x = 0; x < num_var_partitions (cl->map); x++) 1287 if (cl->list[x] != NULL) 1288 { 1289 for (p = cl->list[x]; p->next != NULL; p = p->next) 1290 num++; 1291 num++; 1292 p->next = chain; 1293 chain = cl->list[x]; 1294 cl->list[x] = NULL; 1295 } 1296 1297 /* Only call qsort if there are more than 2 items. */ 1298 if (num > 2) 1299 { 1300 list = XNEWVEC (partition_pair_p, num); 1301 count = 0; 1302 for (p = chain; p != NULL; p = p->next) 1303 list[count++] = p; 1304 1305 gcc_assert (count == num); 1306 1307 qsort (list, count, sizeof (partition_pair_p), compare_pairs); 1308 1309 p = list[0]; 1310 for (x = 1; x < num; x++) 1311 { 1312 p->next = list[x]; 1313 p = list[x]; 1314 } 1315 p->next = NULL; 1316 cl->list[0] = list[0]; 1317 free (list); 1318 } 1319 else 1320 { 1321 cl->list[0] = chain; 1322 if (num == 2) 1323 { 1324 /* Simply swap the two elements if they are in the wrong order. */ 1325 if (chain->cost < chain->next->cost) 1326 { 1327 cl->list[0] = chain->next; 1328 cl->list[0]->next = chain; 1329 chain->next = NULL; 1330 } 1331 } 1332 } 1333} 1334 1335 1336/* Retrieve the best remaining pair to coalesce from CL. Returns the 2 1337 partitions via P1 and P2. Their calculated cost is returned by the function. 1338 NO_BEST_COALESCE is returned if the coalesce list is empty. */ 1339 1340static int 1341pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) 1342{ 1343 partition_pair_p node; 1344 int ret; 1345 1346 gcc_assert (!cl->add_mode); 1347 1348 node = cl->list[0]; 1349 if (!node) 1350 return NO_BEST_COALESCE; 1351 1352 cl->list[0] = node->next; 1353 1354 *p1 = node->first_partition; 1355 *p2 = node->second_partition; 1356 ret = node->cost; 1357 free (node); 1358 1359 return ret; 1360} 1361 1362 1363/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between 1364 VAR and any other live partitions in VEC which are associated via TPA. 1365 Reset the live bit in VEC. */ 1366 1367static inline void 1368add_conflicts_if_valid (tpa_p tpa, conflict_graph graph, 1369 var_map map, bitmap vec, tree var) 1370{ 1371 int p, y, first; 1372 p = var_to_partition (map, var); 1373 if (p != NO_PARTITION) 1374 { 1375 bitmap_clear_bit (vec, p); 1376 first = tpa_find_tree (tpa, p); 1377 /* If find returns nothing, this object isn't interesting. */ 1378 if (first == TPA_NONE) 1379 return; 1380 /* Only add interferences between objects in the same list. */ 1381 for (y = tpa_first_partition (tpa, first); 1382 y != TPA_NONE; 1383 y = tpa_next_partition (tpa, y)) 1384 { 1385 if (bitmap_bit_p (vec, y)) 1386 conflict_graph_add (graph, p, y); 1387 } 1388 } 1389} 1390 1391/* Return a conflict graph for the information contained in LIVE_INFO. Only 1392 conflicts between items in the same TPA list are added. If optional 1393 coalesce list CL is passed in, any copies encountered are added. */ 1394 1395conflict_graph 1396build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, 1397 coalesce_list_p cl) 1398{ 1399 conflict_graph graph; 1400 var_map map; 1401 bitmap live; 1402 unsigned x, y, i; 1403 basic_block bb; 1404 int *partition_link, *tpa_nodes; 1405 VEC(int,heap) *tpa_to_clear; 1406 unsigned l; 1407 ssa_op_iter iter; 1408 bitmap_iterator bi; 1409 1410 map = live_var_map (liveinfo); 1411 graph = conflict_graph_new (num_var_partitions (map)); 1412 1413 if (tpa_num_trees (tpa) == 0) 1414 return graph; 1415 1416 live = BITMAP_ALLOC (NULL); 1417 1418 partition_link = XCNEWVEC (int, num_var_partitions (map) + 1); 1419 tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa)); 1420 tpa_to_clear = VEC_alloc (int, heap, 50); 1421 1422 FOR_EACH_BB (bb) 1423 { 1424 block_stmt_iterator bsi; 1425 tree phi; 1426 int idx; 1427 1428 /* Start with live on exit temporaries. */ 1429 bitmap_copy (live, live_on_exit (liveinfo, bb)); 1430 1431 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 1432 { 1433 bool is_a_copy = false; 1434 tree stmt = bsi_stmt (bsi); 1435 1436 /* A copy between 2 partitions does not introduce an interference 1437 by itself. If they did, you would never be able to coalesce 1438 two things which are copied. If the two variables really do 1439 conflict, they will conflict elsewhere in the program. 1440 1441 This is handled specially here since we may also be interested 1442 in copies between real variables and SSA_NAME variables. We may 1443 be interested in trying to coalesce SSA_NAME variables with 1444 root variables in some cases. */ 1445 1446 if (TREE_CODE (stmt) == MODIFY_EXPR) 1447 { 1448 tree lhs = TREE_OPERAND (stmt, 0); 1449 tree rhs = TREE_OPERAND (stmt, 1); 1450 int p1, p2; 1451 int bit; 1452 1453 if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME) 1454 p1 = var_to_partition (map, lhs); 1455 else 1456 p1 = NO_PARTITION; 1457 1458 if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME) 1459 p2 = var_to_partition (map, rhs); 1460 else 1461 p2 = NO_PARTITION; 1462 1463 if (p1 != NO_PARTITION && p2 != NO_PARTITION) 1464 { 1465 is_a_copy = true; 1466 bit = bitmap_bit_p (live, p2); 1467 /* If the RHS is live, make it not live while we add 1468 the conflicts, then make it live again. */ 1469 if (bit) 1470 bitmap_clear_bit (live, p2); 1471 add_conflicts_if_valid (tpa, graph, map, live, lhs); 1472 if (bit) 1473 bitmap_set_bit (live, p2); 1474 if (cl) 1475 add_coalesce (cl, p1, p2, 1476 coalesce_cost (bb->frequency, 1477 maybe_hot_bb_p (bb), false)); 1478 set_if_valid (map, live, rhs); 1479 } 1480 } 1481 1482 if (!is_a_copy) 1483 { 1484 tree var; 1485 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) 1486 { 1487 add_conflicts_if_valid (tpa, graph, map, live, var); 1488 } 1489 1490 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 1491 { 1492 set_if_valid (map, live, var); 1493 } 1494 } 1495 } 1496 1497 /* If result of a PHI is unused, then the loops over the statements 1498 will not record any conflicts. However, since the PHI node is 1499 going to be translated out of SSA form we must record a conflict 1500 between the result of the PHI and any variables with are live. 1501 Otherwise the out-of-ssa translation may create incorrect code. */ 1502 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1503 { 1504 tree result = PHI_RESULT (phi); 1505 int p = var_to_partition (map, result); 1506 1507 if (p != NO_PARTITION && ! bitmap_bit_p (live, p)) 1508 add_conflicts_if_valid (tpa, graph, map, live, result); 1509 } 1510 1511 /* Anything which is still live at this point interferes. 1512 In order to implement this efficiently, only conflicts between 1513 partitions which have the same TPA root need be added. 1514 TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero 1515 entry points to an index into 'partition_link', which then indexes 1516 into itself forming a linked list of partitions sharing a tpa root 1517 which have been seen as live up to this point. Since partitions start 1518 at index zero, all entries in partition_link are (partition + 1). 1519 1520 Conflicts are added between the current partition and any already seen. 1521 tpa_clear contains all the tpa_roots processed, and these are the only 1522 entries which need to be zero'd out for a clean restart. */ 1523 1524 EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi) 1525 { 1526 i = tpa_find_tree (tpa, x); 1527 if (i != (unsigned)TPA_NONE) 1528 { 1529 int start = tpa_nodes[i]; 1530 /* If start is 0, a new root reference list is being started. 1531 Register it to be cleared. */ 1532 if (!start) 1533 VEC_safe_push (int, heap, tpa_to_clear, i); 1534 1535 /* Add interferences to other tpa members seen. */ 1536 for (y = start; y != 0; y = partition_link[y]) 1537 conflict_graph_add (graph, x, y - 1); 1538 tpa_nodes[i] = x + 1; 1539 partition_link[x + 1] = start; 1540 } 1541 } 1542 1543 /* Now clear the used tpa root references. */ 1544 for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++) 1545 tpa_nodes[idx] = 0; 1546 VEC_truncate (int, tpa_to_clear, 0); 1547 } 1548 1549 free (tpa_nodes); 1550 free (partition_link); 1551 VEC_free (int, heap, tpa_to_clear); 1552 BITMAP_FREE (live); 1553 return graph; 1554} 1555 1556 1557/* This routine will attempt to coalesce the elements in TPA subject to the 1558 conflicts found in GRAPH. If optional coalesce_list CL is provided, 1559 only coalesces specified within the coalesce list are attempted. Otherwise 1560 an attempt is made to coalesce as many partitions within each TPA grouping 1561 as possible. If DEBUG is provided, debug output will be sent there. */ 1562 1563void 1564coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, 1565 coalesce_list_p cl, FILE *debug) 1566{ 1567 int x, y, z, w; 1568 tree var, tmp; 1569 1570 /* Attempt to coalesce any items in a coalesce list. */ 1571 if (cl) 1572 { 1573 while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE) 1574 { 1575 if (debug) 1576 { 1577 fprintf (debug, "Coalesce list: (%d)", x); 1578 print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM); 1579 fprintf (debug, " & (%d)", y); 1580 print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM); 1581 } 1582 1583 w = tpa_find_tree (tpa, x); 1584 z = tpa_find_tree (tpa, y); 1585 if (w != z || w == TPA_NONE || z == TPA_NONE) 1586 { 1587 if (debug) 1588 { 1589 if (w != z) 1590 fprintf (debug, ": Fail, Non-matching TPA's\n"); 1591 if (w == TPA_NONE) 1592 fprintf (debug, ": Fail %d non TPA.\n", x); 1593 else 1594 fprintf (debug, ": Fail %d non TPA.\n", y); 1595 } 1596 continue; 1597 } 1598 var = partition_to_var (map, x); 1599 tmp = partition_to_var (map, y); 1600 x = var_to_partition (map, var); 1601 y = var_to_partition (map, tmp); 1602 if (debug) 1603 fprintf (debug, " [map: %d, %d] ", x, y); 1604 if (x == y) 1605 { 1606 if (debug) 1607 fprintf (debug, ": Already Coalesced.\n"); 1608 continue; 1609 } 1610 if (!conflict_graph_conflict_p (graph, x, y)) 1611 { 1612 z = var_union (map, var, tmp); 1613 if (z == NO_PARTITION) 1614 { 1615 if (debug) 1616 fprintf (debug, ": Unable to perform partition union.\n"); 1617 continue; 1618 } 1619 1620 /* z is the new combined partition. We need to remove the other 1621 partition from the list. Set x to be that other partition. */ 1622 if (z == x) 1623 { 1624 conflict_graph_merge_regs (graph, x, y); 1625 w = tpa_find_tree (tpa, y); 1626 tpa_remove_partition (tpa, w, y); 1627 } 1628 else 1629 { 1630 conflict_graph_merge_regs (graph, y, x); 1631 w = tpa_find_tree (tpa, x); 1632 tpa_remove_partition (tpa, w, x); 1633 } 1634 1635 if (debug) 1636 fprintf (debug, ": Success -> %d\n", z); 1637 } 1638 else 1639 if (debug) 1640 fprintf (debug, ": Fail due to conflict\n"); 1641 } 1642 /* If using a coalesce list, don't try to coalesce anything else. */ 1643 return; 1644 } 1645 1646 for (x = 0; x < tpa_num_trees (tpa); x++) 1647 { 1648 while (tpa_first_partition (tpa, x) != TPA_NONE) 1649 { 1650 int p1, p2; 1651 /* Coalesce first partition with anything that doesn't conflict. */ 1652 y = tpa_first_partition (tpa, x); 1653 tpa_remove_partition (tpa, x, y); 1654 1655 var = partition_to_var (map, y); 1656 /* p1 is the partition representative to which y belongs. */ 1657 p1 = var_to_partition (map, var); 1658 1659 for (z = tpa_next_partition (tpa, y); 1660 z != TPA_NONE; 1661 z = tpa_next_partition (tpa, z)) 1662 { 1663 tmp = partition_to_var (map, z); 1664 /* p2 is the partition representative to which z belongs. */ 1665 p2 = var_to_partition (map, tmp); 1666 if (debug) 1667 { 1668 fprintf (debug, "Coalesce : "); 1669 print_generic_expr (debug, var, TDF_SLIM); 1670 fprintf (debug, " &"); 1671 print_generic_expr (debug, tmp, TDF_SLIM); 1672 fprintf (debug, " (%d ,%d)", p1, p2); 1673 } 1674 1675 /* If partitions are already merged, don't check for conflict. */ 1676 if (tmp == var) 1677 { 1678 tpa_remove_partition (tpa, x, z); 1679 if (debug) 1680 fprintf (debug, ": Already coalesced\n"); 1681 } 1682 else 1683 if (!conflict_graph_conflict_p (graph, p1, p2)) 1684 { 1685 int v; 1686 if (tpa_find_tree (tpa, y) == TPA_NONE 1687 || tpa_find_tree (tpa, z) == TPA_NONE) 1688 { 1689 if (debug) 1690 fprintf (debug, ": Fail non-TPA member\n"); 1691 continue; 1692 } 1693 if ((v = var_union (map, var, tmp)) == NO_PARTITION) 1694 { 1695 if (debug) 1696 fprintf (debug, ": Fail cannot combine partitions\n"); 1697 continue; 1698 } 1699 1700 tpa_remove_partition (tpa, x, z); 1701 if (v == p1) 1702 conflict_graph_merge_regs (graph, v, z); 1703 else 1704 { 1705 /* Update the first partition's representative. */ 1706 conflict_graph_merge_regs (graph, v, y); 1707 p1 = v; 1708 } 1709 1710 /* The root variable of the partition may be changed 1711 now. */ 1712 var = partition_to_var (map, p1); 1713 1714 if (debug) 1715 fprintf (debug, ": Success -> %d\n", v); 1716 } 1717 else 1718 if (debug) 1719 fprintf (debug, ": Fail, Conflict\n"); 1720 } 1721 } 1722 } 1723} 1724 1725 1726/* Send debug info for coalesce list CL to file F. */ 1727 1728void 1729dump_coalesce_list (FILE *f, coalesce_list_p cl) 1730{ 1731 partition_pair_p node; 1732 int x, num; 1733 tree var; 1734 1735 if (cl->add_mode) 1736 { 1737 fprintf (f, "Coalesce List:\n"); 1738 num = num_var_partitions (cl->map); 1739 for (x = 0; x < num; x++) 1740 { 1741 node = cl->list[x]; 1742 if (node) 1743 { 1744 fprintf (f, "["); 1745 print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM); 1746 fprintf (f, "] - "); 1747 for ( ; node; node = node->next) 1748 { 1749 var = partition_to_var (cl->map, node->second_partition); 1750 print_generic_expr (f, var, TDF_SLIM); 1751 fprintf (f, "(%1d), ", node->cost); 1752 } 1753 fprintf (f, "\n"); 1754 } 1755 } 1756 } 1757 else 1758 { 1759 fprintf (f, "Sorted Coalesce list:\n"); 1760 for (node = cl->list[0]; node; node = node->next) 1761 { 1762 fprintf (f, "(%d) ", node->cost); 1763 var = partition_to_var (cl->map, node->first_partition); 1764 print_generic_expr (f, var, TDF_SLIM); 1765 fprintf (f, " : "); 1766 var = partition_to_var (cl->map, node->second_partition); 1767 print_generic_expr (f, var, TDF_SLIM); 1768 fprintf (f, "\n"); 1769 } 1770 } 1771} 1772 1773 1774/* Output tree_partition_associator object TPA to file F.. */ 1775 1776void 1777tpa_dump (FILE *f, tpa_p tpa) 1778{ 1779 int x, i; 1780 1781 if (!tpa) 1782 return; 1783 1784 for (x = 0; x < tpa_num_trees (tpa); x++) 1785 { 1786 print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM); 1787 fprintf (f, " : ("); 1788 for (i = tpa_first_partition (tpa, x); 1789 i != TPA_NONE; 1790 i = tpa_next_partition (tpa, i)) 1791 { 1792 fprintf (f, "(%d)",i); 1793 print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM); 1794 fprintf (f, " "); 1795 1796#ifdef ENABLE_CHECKING 1797 if (tpa_find_tree (tpa, i) != x) 1798 fprintf (f, "**find tree incorrectly set** "); 1799#endif 1800 1801 } 1802 fprintf (f, ")\n"); 1803 } 1804 fflush (f); 1805} 1806 1807 1808/* Output partition map MAP to file F. */ 1809 1810void 1811dump_var_map (FILE *f, var_map map) 1812{ 1813 int t; 1814 unsigned x, y; 1815 int p; 1816 1817 fprintf (f, "\nPartition map \n\n"); 1818 1819 for (x = 0; x < map->num_partitions; x++) 1820 { 1821 if (map->compact_to_partition != NULL) 1822 p = map->compact_to_partition[x]; 1823 else 1824 p = x; 1825 1826 if (map->partition_to_var[p] == NULL_TREE) 1827 continue; 1828 1829 t = 0; 1830 for (y = 1; y < num_ssa_names; y++) 1831 { 1832 p = partition_find (map->var_partition, y); 1833 if (map->partition_to_compact) 1834 p = map->partition_to_compact[p]; 1835 if (p == (int)x) 1836 { 1837 if (t++ == 0) 1838 { 1839 fprintf(f, "Partition %d (", x); 1840 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM); 1841 fprintf (f, " - "); 1842 } 1843 fprintf (f, "%d ", y); 1844 } 1845 } 1846 if (t != 0) 1847 fprintf (f, ")\n"); 1848 } 1849 fprintf (f, "\n"); 1850} 1851 1852 1853/* Output live range info LIVE to file F, controlled by FLAG. */ 1854 1855void 1856dump_live_info (FILE *f, tree_live_info_p live, int flag) 1857{ 1858 basic_block bb; 1859 unsigned i; 1860 var_map map = live->map; 1861 bitmap_iterator bi; 1862 1863 if ((flag & LIVEDUMP_ENTRY) && live->livein) 1864 { 1865 FOR_EACH_BB (bb) 1866 { 1867 fprintf (f, "\nLive on entry to BB%d : ", bb->index); 1868 for (i = 0; i < num_var_partitions (map); i++) 1869 { 1870 if (bitmap_bit_p (live_entry_blocks (live, i), bb->index)) 1871 { 1872 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); 1873 fprintf (f, " "); 1874 } 1875 } 1876 fprintf (f, "\n"); 1877 } 1878 } 1879 1880 if ((flag & LIVEDUMP_EXIT) && live->liveout) 1881 { 1882 FOR_EACH_BB (bb) 1883 { 1884 fprintf (f, "\nLive on exit from BB%d : ", bb->index); 1885 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi) 1886 { 1887 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); 1888 fprintf (f, " "); 1889 } 1890 fprintf (f, "\n"); 1891 } 1892 } 1893} 1894 1895#ifdef ENABLE_CHECKING 1896void 1897register_ssa_partition_check (tree ssa_var) 1898{ 1899 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); 1900 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var))) 1901 { 1902 fprintf (stderr, "Illegally registering a virtual SSA name :"); 1903 print_generic_expr (stderr, ssa_var, TDF_SLIM); 1904 fprintf (stderr, " in the SSA->Normal phase.\n"); 1905 internal_error ("SSA corruption"); 1906 } 1907} 1908#endif 1909