1169689Skan/* Rewrite a program in Normal form into SSA. 2169689Skan Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@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 "rtl.h" 29169689Skan#include "tm_p.h" 30169689Skan#include "langhooks.h" 31169689Skan#include "hard-reg-set.h" 32169689Skan#include "basic-block.h" 33169689Skan#include "output.h" 34169689Skan#include "expr.h" 35169689Skan#include "function.h" 36169689Skan#include "diagnostic.h" 37169689Skan#include "bitmap.h" 38169689Skan#include "tree-flow.h" 39169689Skan#include "tree-gimple.h" 40169689Skan#include "tree-inline.h" 41169689Skan#include "varray.h" 42169689Skan#include "timevar.h" 43169689Skan#include "hashtab.h" 44169689Skan#include "tree-dump.h" 45169689Skan#include "tree-pass.h" 46169689Skan#include "cfgloop.h" 47169689Skan#include "domwalk.h" 48169689Skan#include "ggc.h" 49169689Skan#include "params.h" 50169689Skan#include "vecprim.h" 51169689Skan 52169689Skan/* This file builds the SSA form for a function as described in: 53169689Skan R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently 54169689Skan Computing Static Single Assignment Form and the Control Dependence 55169689Skan Graph. ACM Transactions on Programming Languages and Systems, 56169689Skan 13(4):451-490, October 1991. */ 57169689Skan 58169689Skan/* True if the code is in ssa form. */ 59169689Skanbool in_ssa_p; 60169689Skan 61169689Skan/* Structure to map a variable VAR to the set of blocks that contain 62169689Skan definitions for VAR. */ 63169689Skanstruct def_blocks_d 64169689Skan{ 65169689Skan /* The variable. */ 66169689Skan tree var; 67169689Skan 68169689Skan /* Blocks that contain definitions of VAR. Bit I will be set if the 69169689Skan Ith block contains a definition of VAR. */ 70169689Skan bitmap def_blocks; 71169689Skan 72169689Skan /* Blocks that contain a PHI node for VAR. */ 73169689Skan bitmap phi_blocks; 74169689Skan 75169689Skan /* Blocks where VAR is live-on-entry. Similar semantics as 76169689Skan DEF_BLOCKS. */ 77169689Skan bitmap livein_blocks; 78169689Skan}; 79169689Skan 80169689Skan 81169689Skan/* Each entry in DEF_BLOCKS contains an element of type STRUCT 82169689Skan DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the 83169689Skan basic blocks where VAR is defined (assigned a new value). It also 84169689Skan contains a bitmap of all the blocks where VAR is live-on-entry 85169689Skan (i.e., there is a use of VAR in block B without a preceding 86169689Skan definition in B). The live-on-entry information is used when 87169689Skan computing PHI pruning heuristics. */ 88169689Skanstatic htab_t def_blocks; 89169689Skan 90169689Skan/* Stack of trees used to restore the global currdefs to its original 91169689Skan state after completing rewriting of a block and its dominator 92169689Skan children. Its elements have the following properties: 93169689Skan 94169689Skan - An SSA_NAME indicates that the current definition of the 95169689Skan underlying variable should be set to the given SSA_NAME. 96169689Skan 97169689Skan - A _DECL node indicates that the underlying variable has no 98169689Skan current definition. 99169689Skan 100169689Skan - A NULL node is used to mark the last node associated with the 101169689Skan current block. 102169689Skan 103169689Skan - A NULL node at the top entry is used to mark the last node 104169689Skan associated with the current block. */ 105169689Skanstatic VEC(tree,heap) *block_defs_stack; 106169689Skan 107169689Skan/* Set of existing SSA names being replaced by update_ssa. */ 108169689Skanstatic sbitmap old_ssa_names; 109169689Skan 110169689Skan/* Set of new SSA names being added by update_ssa. Note that both 111169689Skan NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of 112169689Skan the operations done on them are presence tests. */ 113169689Skanstatic sbitmap new_ssa_names; 114169689Skan 115169689Skan/* Symbols whose SSA form needs to be updated or created for the first 116169689Skan time. */ 117169689Skanstatic bitmap syms_to_rename; 118169689Skan 119169689Skan/* Set of SSA names that have been marked to be released after they 120169689Skan were registered in the replacement table. They will be finally 121169689Skan released after we finish updating the SSA web. */ 122169689Skanstatic bitmap names_to_release; 123169689Skan 124169689Skan/* For each block, the phi nodes that need to be rewritten are stored into 125169689Skan these vectors. */ 126169689Skan 127169689Skantypedef VEC(tree, heap) *tree_vec; 128169689SkanDEF_VEC_P (tree_vec); 129169689SkanDEF_VEC_ALLOC_P (tree_vec, heap); 130169689Skan 131169689Skanstatic VEC(tree_vec, heap) *phis_to_rewrite; 132169689Skan 133169689Skan/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */ 134169689Skan 135169689Skanstatic bitmap blocks_with_phis_to_rewrite; 136169689Skan 137169689Skan/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need 138169689Skan to grow as the callers to register_new_name_mapping will typically 139169689Skan create new names on the fly. FIXME. Currently set to 1/3 to avoid 140169689Skan frequent reallocations but still need to find a reasonable growth 141169689Skan strategy. */ 142169689Skan#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3)) 143169689Skan 144169689Skan/* Tuple used to represent replacement mappings. */ 145169689Skanstruct repl_map_d 146169689Skan{ 147169689Skan tree name; 148169689Skan bitmap set; 149169689Skan}; 150169689Skan 151169689Skan/* NEW -> OLD_SET replacement table. If we are replacing several 152169689Skan existing SSA names O_1, O_2, ..., O_j with a new name N_i, 153169689Skan then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */ 154169689Skanstatic htab_t repl_tbl; 155169689Skan 156169689Skan/* true if register_new_name_mapping needs to initialize the data 157169689Skan structures needed by update_ssa. */ 158169689Skanstatic bool need_to_initialize_update_ssa_p = true; 159169689Skan 160169689Skan/* true if update_ssa needs to update virtual operands. */ 161169689Skanstatic bool need_to_update_vops_p = false; 162169689Skan 163169689Skan/* Statistics kept by update_ssa to use in the virtual mapping 164169689Skan heuristic. If the number of virtual mappings is beyond certain 165169689Skan threshold, the updater will switch from using the mappings into 166169689Skan renaming the virtual symbols from scratch. In some cases, the 167169689Skan large number of name mappings for virtual names causes significant 168169689Skan slowdowns in the PHI insertion code. */ 169169689Skanstruct update_ssa_stats_d 170169689Skan{ 171169689Skan unsigned num_virtual_mappings; 172169689Skan unsigned num_total_mappings; 173169689Skan bitmap virtual_symbols; 174169689Skan unsigned num_virtual_symbols; 175169689Skan}; 176169689Skanstatic struct update_ssa_stats_d update_ssa_stats; 177169689Skan 178169689Skan/* Global data to attach to the main dominator walk structure. */ 179169689Skanstruct mark_def_sites_global_data 180169689Skan{ 181169689Skan /* This bitmap contains the variables which are set before they 182169689Skan are used in a basic block. */ 183169689Skan bitmap kills; 184169689Skan 185169689Skan /* Bitmap of names to rename. */ 186169689Skan sbitmap names_to_rename; 187169689Skan 188169689Skan /* Set of blocks that mark_def_sites deems interesting for the 189169689Skan renamer to process. */ 190169689Skan sbitmap interesting_blocks; 191169689Skan}; 192169689Skan 193169689Skan 194169689Skan/* Information stored for SSA names. */ 195169689Skanstruct ssa_name_info 196169689Skan{ 197169689Skan /* The actual definition of the ssa name. */ 198169689Skan tree current_def; 199169689Skan 200169689Skan /* This field indicates whether or not the variable may need PHI nodes. 201169689Skan See the enum's definition for more detailed information about the 202169689Skan states. */ 203169689Skan ENUM_BITFIELD (need_phi_state) need_phi_state : 2; 204169689Skan 205169689Skan /* Age of this record (so that info_for_ssa_name table can be cleared 206169689Skan quicky); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields 207169689Skan are assumed to be null. */ 208169689Skan unsigned age; 209169689Skan}; 210169689Skan 211169689Skan/* The information associated with names. */ 212169689Skantypedef struct ssa_name_info *ssa_name_info_p; 213169689SkanDEF_VEC_P (ssa_name_info_p); 214169689SkanDEF_VEC_ALLOC_P (ssa_name_info_p, heap); 215169689Skan 216169689Skanstatic VEC(ssa_name_info_p, heap) *info_for_ssa_name; 217169689Skanstatic unsigned current_info_for_ssa_name_age; 218169689Skan 219169689Skan/* The set of blocks affected by update_ssa. */ 220169689Skan 221169689Skanstatic bitmap blocks_to_update; 222169689Skan 223169689Skan/* The main entry point to the SSA renamer (rewrite_blocks) may be 224169689Skan called several times to do different, but related, tasks. 225169689Skan Initially, we need it to rename the whole program into SSA form. 226169689Skan At other times, we may need it to only rename into SSA newly 227169689Skan exposed symbols. Finally, we can also call it to incrementally fix 228169689Skan an already built SSA web. */ 229169689Skanenum rewrite_mode { 230169689Skan /* Convert the whole function into SSA form. */ 231169689Skan REWRITE_ALL, 232169689Skan 233169689Skan /* Incrementally update the SSA web by replacing existing SSA 234169689Skan names with new ones. See update_ssa for details. */ 235169689Skan REWRITE_UPDATE 236169689Skan}; 237169689Skan 238169689Skan 239169689Skan/* Use TREE_VISITED to keep track of which statements we want to 240169689Skan rename. When renaming a subset of the variables, not all 241169689Skan statements will be processed. This is decided in mark_def_sites. */ 242169689Skan#define REWRITE_THIS_STMT(T) TREE_VISITED (T) 243169689Skan 244169689Skan/* Use the unsigned flag to keep track of which statements we want to 245169689Skan visit when marking new definition sites. This is slightly 246169689Skan different than REWRITE_THIS_STMT: it's used by update_ssa to 247169689Skan distinguish statements that need to have both uses and defs 248169689Skan processed from those that only need to have their defs processed. 249169689Skan Statements that define new SSA names only need to have their defs 250169689Skan registered, but they don't need to have their uses renamed. */ 251169689Skan#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag 252169689Skan 253169689Skan 254169689Skan/* Prototypes for debugging functions. */ 255169689Skanextern void dump_tree_ssa (FILE *); 256169689Skanextern void debug_tree_ssa (void); 257169689Skanextern void debug_def_blocks (void); 258169689Skanextern void dump_tree_ssa_stats (FILE *); 259169689Skanextern void debug_tree_ssa_stats (void); 260169689Skanvoid dump_update_ssa (FILE *); 261169689Skanvoid debug_update_ssa (void); 262169689Skanvoid dump_names_replaced_by (FILE *, tree); 263169689Skanvoid debug_names_replaced_by (tree); 264169689Skan 265169689Skan/* Get the information associated with NAME. */ 266169689Skan 267169689Skanstatic inline struct ssa_name_info * 268169689Skanget_ssa_name_ann (tree name) 269169689Skan{ 270169689Skan unsigned ver = SSA_NAME_VERSION (name); 271169689Skan unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name); 272169689Skan struct ssa_name_info *info; 273169689Skan 274169689Skan if (ver >= len) 275169689Skan { 276169689Skan unsigned new_len = num_ssa_names; 277169689Skan 278169689Skan VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len); 279169689Skan while (len++ < new_len) 280169689Skan { 281169689Skan struct ssa_name_info *info = XCNEW (struct ssa_name_info); 282169689Skan info->age = current_info_for_ssa_name_age; 283169689Skan VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info); 284169689Skan } 285169689Skan } 286169689Skan 287169689Skan info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver); 288169689Skan if (info->age < current_info_for_ssa_name_age) 289169689Skan { 290169689Skan info->need_phi_state = 0; 291169689Skan info->current_def = NULL_TREE; 292169689Skan info->age = current_info_for_ssa_name_age; 293169689Skan } 294169689Skan 295169689Skan return info; 296169689Skan} 297169689Skan 298169689Skan/* Clears info for ssa names. */ 299169689Skan 300169689Skanstatic void 301169689Skanclear_ssa_name_info (void) 302169689Skan{ 303169689Skan current_info_for_ssa_name_age++; 304169689Skan} 305169689Skan 306169689Skan/* Gets phi_state field for VAR. */ 307169689Skan 308169689Skanstatic inline enum need_phi_state 309169689Skanget_phi_state (tree var) 310169689Skan{ 311169689Skan if (TREE_CODE (var) == SSA_NAME) 312169689Skan return get_ssa_name_ann (var)->need_phi_state; 313169689Skan else 314169689Skan return var_ann (var)->need_phi_state; 315169689Skan} 316169689Skan 317169689Skan 318169689Skan/* Sets phi_state field for VAR to STATE. */ 319169689Skan 320169689Skanstatic inline void 321169689Skanset_phi_state (tree var, enum need_phi_state state) 322169689Skan{ 323169689Skan if (TREE_CODE (var) == SSA_NAME) 324169689Skan get_ssa_name_ann (var)->need_phi_state = state; 325169689Skan else 326169689Skan var_ann (var)->need_phi_state = state; 327169689Skan} 328169689Skan 329169689Skan 330169689Skan/* Return the current definition for VAR. */ 331169689Skan 332169689Skantree 333169689Skanget_current_def (tree var) 334169689Skan{ 335169689Skan if (TREE_CODE (var) == SSA_NAME) 336169689Skan return get_ssa_name_ann (var)->current_def; 337169689Skan else 338169689Skan return var_ann (var)->current_def; 339169689Skan} 340169689Skan 341169689Skan 342169689Skan/* Sets current definition of VAR to DEF. */ 343169689Skan 344169689Skanvoid 345169689Skanset_current_def (tree var, tree def) 346169689Skan{ 347169689Skan if (TREE_CODE (var) == SSA_NAME) 348169689Skan get_ssa_name_ann (var)->current_def = def; 349169689Skan else 350169689Skan var_ann (var)->current_def = def; 351169689Skan} 352169689Skan 353169689Skan 354169689Skan/* Compute global livein information given the set of blockx where 355169689Skan an object is locally live at the start of the block (LIVEIN) 356169689Skan and the set of blocks where the object is defined (DEF_BLOCKS). 357169689Skan 358169689Skan Note: This routine augments the existing local livein information 359169689Skan to include global livein (i.e., it modifies the underlying bitmap 360169689Skan for LIVEIN). */ 361169689Skan 362169689Skanvoid 363169689Skancompute_global_livein (bitmap livein, bitmap def_blocks) 364169689Skan{ 365169689Skan basic_block bb, *worklist, *tos; 366169689Skan unsigned i; 367169689Skan bitmap_iterator bi; 368169689Skan 369169689Skan tos = worklist 370169689Skan = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1)); 371169689Skan 372169689Skan EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi) 373169689Skan { 374169689Skan *tos++ = BASIC_BLOCK (i); 375169689Skan } 376169689Skan 377169689Skan /* Iterate until the worklist is empty. */ 378169689Skan while (tos != worklist) 379169689Skan { 380169689Skan edge e; 381169689Skan edge_iterator ei; 382169689Skan 383169689Skan /* Pull a block off the worklist. */ 384169689Skan bb = *--tos; 385169689Skan 386169689Skan /* For each predecessor block. */ 387169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 388169689Skan { 389169689Skan basic_block pred = e->src; 390169689Skan int pred_index = pred->index; 391169689Skan 392169689Skan /* None of this is necessary for the entry block. */ 393169689Skan if (pred != ENTRY_BLOCK_PTR 394169689Skan && ! bitmap_bit_p (livein, pred_index) 395169689Skan && ! bitmap_bit_p (def_blocks, pred_index)) 396169689Skan { 397169689Skan *tos++ = pred; 398169689Skan bitmap_set_bit (livein, pred_index); 399169689Skan } 400169689Skan } 401169689Skan } 402169689Skan 403169689Skan free (worklist); 404169689Skan} 405169689Skan 406169689Skan 407169689Skan/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for 408169689Skan all statements in basic block BB. */ 409169689Skan 410169689Skanstatic void 411169689Skaninitialize_flags_in_bb (basic_block bb) 412169689Skan{ 413169689Skan tree phi, stmt; 414169689Skan block_stmt_iterator bsi; 415169689Skan 416169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 417169689Skan { 418169689Skan REWRITE_THIS_STMT (phi) = 0; 419169689Skan REGISTER_DEFS_IN_THIS_STMT (phi) = 0; 420169689Skan } 421169689Skan 422169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 423169689Skan { 424169689Skan stmt = bsi_stmt (bsi); 425169689Skan /* We are going to use the operand cache API, such as 426169689Skan SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand 427169689Skan cache for each statement should be up-to-date. */ 428169689Skan gcc_assert (!stmt_modified_p (stmt)); 429169689Skan REWRITE_THIS_STMT (stmt) = 0; 430169689Skan REGISTER_DEFS_IN_THIS_STMT (stmt) = 0; 431169689Skan } 432169689Skan} 433169689Skan 434169689Skan/* Mark block BB as interesting for update_ssa. */ 435169689Skan 436169689Skanstatic void 437169689Skanmark_block_for_update (basic_block bb) 438169689Skan{ 439169689Skan gcc_assert (blocks_to_update != NULL); 440169689Skan if (bitmap_bit_p (blocks_to_update, bb->index)) 441169689Skan return; 442169689Skan bitmap_set_bit (blocks_to_update, bb->index); 443169689Skan initialize_flags_in_bb (bb); 444169689Skan} 445169689Skan 446169689Skan/* Return the set of blocks where variable VAR is defined and the blocks 447169689Skan where VAR is live on entry (livein). If no entry is found in 448169689Skan DEF_BLOCKS, a new one is created and returned. */ 449169689Skan 450169689Skanstatic inline struct def_blocks_d * 451169689Skanget_def_blocks_for (tree var) 452169689Skan{ 453169689Skan struct def_blocks_d db, *db_p; 454169689Skan void **slot; 455169689Skan 456169689Skan db.var = var; 457169689Skan slot = htab_find_slot (def_blocks, (void *) &db, INSERT); 458169689Skan if (*slot == NULL) 459169689Skan { 460169689Skan db_p = XNEW (struct def_blocks_d); 461169689Skan db_p->var = var; 462169689Skan db_p->def_blocks = BITMAP_ALLOC (NULL); 463169689Skan db_p->phi_blocks = BITMAP_ALLOC (NULL); 464169689Skan db_p->livein_blocks = BITMAP_ALLOC (NULL); 465169689Skan *slot = (void *) db_p; 466169689Skan } 467169689Skan else 468169689Skan db_p = (struct def_blocks_d *) *slot; 469169689Skan 470169689Skan return db_p; 471169689Skan} 472169689Skan 473169689Skan 474169689Skan/* Mark block BB as the definition site for variable VAR. PHI_P is true if 475169689Skan VAR is defined by a PHI node. */ 476169689Skan 477169689Skanstatic void 478169689Skanset_def_block (tree var, basic_block bb, bool phi_p) 479169689Skan{ 480169689Skan struct def_blocks_d *db_p; 481169689Skan enum need_phi_state state; 482169689Skan 483169689Skan state = get_phi_state (var); 484169689Skan db_p = get_def_blocks_for (var); 485169689Skan 486169689Skan /* Set the bit corresponding to the block where VAR is defined. */ 487169689Skan bitmap_set_bit (db_p->def_blocks, bb->index); 488169689Skan if (phi_p) 489169689Skan bitmap_set_bit (db_p->phi_blocks, bb->index); 490169689Skan 491169689Skan /* Keep track of whether or not we may need to insert PHI nodes. 492169689Skan 493169689Skan If we are in the UNKNOWN state, then this is the first definition 494169689Skan of VAR. Additionally, we have not seen any uses of VAR yet, so 495169689Skan we do not need a PHI node for this variable at this time (i.e., 496169689Skan transition to NEED_PHI_STATE_NO). 497169689Skan 498169689Skan If we are in any other state, then we either have multiple definitions 499169689Skan of this variable occurring in different blocks or we saw a use of the 500169689Skan variable which was not dominated by the block containing the 501169689Skan definition(s). In this case we may need a PHI node, so enter 502169689Skan state NEED_PHI_STATE_MAYBE. */ 503169689Skan if (state == NEED_PHI_STATE_UNKNOWN) 504169689Skan set_phi_state (var, NEED_PHI_STATE_NO); 505169689Skan else 506169689Skan set_phi_state (var, NEED_PHI_STATE_MAYBE); 507169689Skan} 508169689Skan 509169689Skan 510169689Skan/* Mark block BB as having VAR live at the entry to BB. */ 511169689Skan 512169689Skanstatic void 513169689Skanset_livein_block (tree var, basic_block bb) 514169689Skan{ 515169689Skan struct def_blocks_d *db_p; 516169689Skan enum need_phi_state state = get_phi_state (var); 517169689Skan 518169689Skan db_p = get_def_blocks_for (var); 519169689Skan 520169689Skan /* Set the bit corresponding to the block where VAR is live in. */ 521169689Skan bitmap_set_bit (db_p->livein_blocks, bb->index); 522169689Skan 523169689Skan /* Keep track of whether or not we may need to insert PHI nodes. 524169689Skan 525169689Skan If we reach here in NEED_PHI_STATE_NO, see if this use is dominated 526169689Skan by the single block containing the definition(s) of this variable. If 527169689Skan it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to 528169689Skan NEED_PHI_STATE_MAYBE. */ 529169689Skan if (state == NEED_PHI_STATE_NO) 530169689Skan { 531169689Skan int def_block_index = bitmap_first_set_bit (db_p->def_blocks); 532169689Skan 533169689Skan if (def_block_index == -1 534169689Skan || ! dominated_by_p (CDI_DOMINATORS, bb, 535169689Skan BASIC_BLOCK (def_block_index))) 536169689Skan set_phi_state (var, NEED_PHI_STATE_MAYBE); 537169689Skan } 538169689Skan else 539169689Skan set_phi_state (var, NEED_PHI_STATE_MAYBE); 540169689Skan} 541169689Skan 542169689Skan 543169689Skan/* Return true if symbol SYM is marked for renaming. */ 544169689Skan 545169689Skanstatic inline bool 546169689Skansymbol_marked_for_renaming (tree sym) 547169689Skan{ 548169689Skan gcc_assert (DECL_P (sym)); 549169689Skan return bitmap_bit_p (syms_to_rename, DECL_UID (sym)); 550169689Skan} 551169689Skan 552169689Skan 553169689Skan/* Return true if NAME is in OLD_SSA_NAMES. */ 554169689Skan 555169689Skanstatic inline bool 556169689Skanis_old_name (tree name) 557169689Skan{ 558169689Skan unsigned ver = SSA_NAME_VERSION (name); 559169689Skan return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver); 560169689Skan} 561169689Skan 562169689Skan 563169689Skan/* Return true if NAME is in NEW_SSA_NAMES. */ 564169689Skan 565169689Skanstatic inline bool 566169689Skanis_new_name (tree name) 567169689Skan{ 568169689Skan unsigned ver = SSA_NAME_VERSION (name); 569169689Skan return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver); 570169689Skan} 571169689Skan 572169689Skan 573169689Skan/* Hashing and equality functions for REPL_TBL. */ 574169689Skan 575169689Skanstatic hashval_t 576169689Skanrepl_map_hash (const void *p) 577169689Skan{ 578169689Skan return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name); 579169689Skan} 580169689Skan 581169689Skanstatic int 582169689Skanrepl_map_eq (const void *p1, const void *p2) 583169689Skan{ 584169689Skan return ((const struct repl_map_d *)p1)->name 585169689Skan == ((const struct repl_map_d *)p2)->name; 586169689Skan} 587169689Skan 588169689Skanstatic void 589169689Skanrepl_map_free (void *p) 590169689Skan{ 591169689Skan BITMAP_FREE (((struct repl_map_d *)p)->set); 592169689Skan free (p); 593169689Skan} 594169689Skan 595169689Skan 596169689Skan/* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET). */ 597169689Skan 598169689Skanstatic inline bitmap 599169689Skannames_replaced_by (tree new) 600169689Skan{ 601169689Skan struct repl_map_d m; 602169689Skan void **slot; 603169689Skan 604169689Skan m.name = new; 605169689Skan slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT); 606169689Skan 607169689Skan /* If N was not registered in the replacement table, return NULL. */ 608169689Skan if (slot == NULL || *slot == NULL) 609169689Skan return NULL; 610169689Skan 611169689Skan return ((struct repl_map_d *) *slot)->set; 612169689Skan} 613169689Skan 614169689Skan 615169689Skan/* Add OLD to REPL_TBL[NEW].SET. */ 616169689Skan 617169689Skanstatic inline void 618169689Skanadd_to_repl_tbl (tree new, tree old) 619169689Skan{ 620169689Skan struct repl_map_d m, *mp; 621169689Skan void **slot; 622169689Skan 623169689Skan m.name = new; 624169689Skan slot = htab_find_slot (repl_tbl, (void *) &m, INSERT); 625169689Skan if (*slot == NULL) 626169689Skan { 627169689Skan mp = XNEW (struct repl_map_d); 628169689Skan mp->name = new; 629169689Skan mp->set = BITMAP_ALLOC (NULL); 630169689Skan *slot = (void *) mp; 631169689Skan } 632169689Skan else 633169689Skan mp = (struct repl_map_d *) *slot; 634169689Skan 635169689Skan bitmap_set_bit (mp->set, SSA_NAME_VERSION (old)); 636169689Skan} 637169689Skan 638169689Skan 639169689Skan/* Add a new mapping NEW -> OLD REPL_TBL. Every entry N_i in REPL_TBL 640169689Skan represents the set of names O_1 ... O_j replaced by N_i. This is 641169689Skan used by update_ssa and its helpers to introduce new SSA names in an 642169689Skan already formed SSA web. */ 643169689Skan 644169689Skanstatic void 645169689Skanadd_new_name_mapping (tree new, tree old) 646169689Skan{ 647169689Skan timevar_push (TV_TREE_SSA_INCREMENTAL); 648169689Skan 649169689Skan /* OLD and NEW must be different SSA names for the same symbol. */ 650169689Skan gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old)); 651169689Skan 652169689Skan /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our 653169689Skan caller may have created new names since the set was created. */ 654169689Skan if (new_ssa_names->n_bits <= num_ssa_names - 1) 655169689Skan { 656169689Skan unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR; 657169689Skan new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0); 658169689Skan old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0); 659169689Skan } 660169689Skan 661169689Skan /* If this mapping is for virtual names, we will need to update 662169689Skan virtual operands. */ 663169689Skan if (!is_gimple_reg (new)) 664169689Skan { 665169689Skan tree sym; 666169689Skan size_t uid; 667169689Skan 668169689Skan need_to_update_vops_p = true; 669169689Skan 670169689Skan /* Keep counts of virtual mappings and symbols to use in the 671169689Skan virtual mapping heuristic. If we have large numbers of 672169689Skan virtual mappings for a relatively low number of symbols, it 673169689Skan will make more sense to rename the symbols from scratch. 674169689Skan Otherwise, the insertion of PHI nodes for each of the old 675169689Skan names in these mappings will be very slow. */ 676169689Skan sym = SSA_NAME_VAR (new); 677169689Skan uid = DECL_UID (sym); 678169689Skan update_ssa_stats.num_virtual_mappings++; 679169689Skan if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid)) 680169689Skan { 681169689Skan bitmap_set_bit (update_ssa_stats.virtual_symbols, uid); 682169689Skan update_ssa_stats.num_virtual_symbols++; 683169689Skan } 684169689Skan } 685169689Skan 686169689Skan /* Update the REPL_TBL table. */ 687169689Skan add_to_repl_tbl (new, old); 688169689Skan 689169689Skan /* If OLD had already been registered as a new name, then all the 690169689Skan names that OLD replaces should also be replaced by NEW. */ 691169689Skan if (is_new_name (old)) 692169689Skan bitmap_ior_into (names_replaced_by (new), names_replaced_by (old)); 693169689Skan 694169689Skan /* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES, 695169689Skan respectively. */ 696169689Skan SET_BIT (new_ssa_names, SSA_NAME_VERSION (new)); 697169689Skan SET_BIT (old_ssa_names, SSA_NAME_VERSION (old)); 698169689Skan 699169689Skan /* Update mapping counter to use in the virtual mapping heuristic. */ 700169689Skan update_ssa_stats.num_total_mappings++; 701169689Skan 702169689Skan timevar_pop (TV_TREE_SSA_INCREMENTAL); 703169689Skan} 704169689Skan 705169689Skan 706169689Skan/* Call back for walk_dominator_tree used to collect definition sites 707169689Skan for every variable in the function. For every statement S in block 708169689Skan BB: 709169689Skan 710169689Skan 1- Variables defined by S in the DEFS of S are marked in the bitmap 711169689Skan WALK_DATA->GLOBAL_DATA->KILLS. 712169689Skan 713169689Skan 2- If S uses a variable VAR and there is no preceding kill of VAR, 714169689Skan then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR. 715169689Skan 716169689Skan This information is used to determine which variables are live 717169689Skan across block boundaries to reduce the number of PHI nodes 718169689Skan we create. */ 719169689Skan 720169689Skanstatic void 721169689Skanmark_def_sites (struct dom_walk_data *walk_data, 722169689Skan basic_block bb, 723169689Skan block_stmt_iterator bsi) 724169689Skan{ 725169689Skan struct mark_def_sites_global_data *gd = 726169689Skan (struct mark_def_sites_global_data *) walk_data->global_data; 727169689Skan bitmap kills = gd->kills; 728169689Skan tree stmt, def; 729169689Skan use_operand_p use_p; 730169689Skan def_operand_p def_p; 731169689Skan ssa_op_iter iter; 732169689Skan 733169689Skan stmt = bsi_stmt (bsi); 734169689Skan update_stmt_if_modified (stmt); 735169689Skan 736169689Skan gcc_assert (blocks_to_update == NULL); 737169689Skan REGISTER_DEFS_IN_THIS_STMT (stmt) = 0; 738169689Skan REWRITE_THIS_STMT (stmt) = 0; 739169689Skan 740169689Skan /* If a variable is used before being set, then the variable is live 741169689Skan across a block boundary, so mark it live-on-entry to BB. */ 742169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 743169689Skan SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL) 744169689Skan { 745169689Skan tree sym = USE_FROM_PTR (use_p); 746169689Skan gcc_assert (DECL_P (sym)); 747169689Skan if (!bitmap_bit_p (kills, DECL_UID (sym))) 748169689Skan set_livein_block (sym, bb); 749169689Skan REWRITE_THIS_STMT (stmt) = 1; 750169689Skan } 751169689Skan 752169689Skan /* Note that virtual definitions are irrelevant for computing KILLS 753169689Skan because a V_MAY_DEF does not constitute a killing definition of the 754169689Skan variable. However, the operand of a virtual definitions is a use 755169689Skan of the variable, so it may cause the variable to be considered 756169689Skan live-on-entry. */ 757169689Skan FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter) 758169689Skan { 759169689Skan tree sym = USE_FROM_PTR (use_p); 760169689Skan gcc_assert (DECL_P (sym)); 761169689Skan set_livein_block (sym, bb); 762169689Skan set_def_block (sym, bb, false); 763169689Skan REGISTER_DEFS_IN_THIS_STMT (stmt) = 1; 764169689Skan REWRITE_THIS_STMT (stmt) = 1; 765169689Skan } 766169689Skan 767169689Skan /* Now process the defs and must-defs made by this statement. */ 768169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF) 769169689Skan { 770169689Skan gcc_assert (DECL_P (def)); 771169689Skan set_def_block (def, bb, false); 772169689Skan bitmap_set_bit (kills, DECL_UID (def)); 773169689Skan REGISTER_DEFS_IN_THIS_STMT (stmt) = 1; 774169689Skan } 775169689Skan 776169689Skan /* If we found the statement interesting then also mark the block BB 777169689Skan as interesting. */ 778169689Skan if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt)) 779169689Skan SET_BIT (gd->interesting_blocks, bb->index); 780169689Skan} 781169689Skan 782169689Skan/* Structure used by prune_unused_phi_nodes to record bounds of the intervals 783169689Skan in the dfs numbering of the dominance tree. */ 784169689Skan 785169689Skanstruct dom_dfsnum 786169689Skan{ 787169689Skan /* Basic block whose index this entry corresponds to. */ 788169689Skan unsigned bb_index; 789169689Skan 790169689Skan /* The dfs number of this node. */ 791169689Skan unsigned dfs_num; 792169689Skan}; 793169689Skan 794169689Skan/* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback 795169689Skan for qsort. */ 796169689Skan 797169689Skanstatic int 798169689Skancmp_dfsnum (const void *a, const void *b) 799169689Skan{ 800169689Skan const struct dom_dfsnum *da = a; 801169689Skan const struct dom_dfsnum *db = b; 802169689Skan 803169689Skan return (int) da->dfs_num - (int) db->dfs_num; 804169689Skan} 805169689Skan 806169689Skan/* Among the intervals starting at the N points specified in DEFS, find 807169689Skan the one that contains S, and return its bb_index. */ 808169689Skan 809169689Skanstatic unsigned 810169689Skanfind_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s) 811169689Skan{ 812169689Skan unsigned f = 0, t = n, m; 813169689Skan 814169689Skan while (t > f + 1) 815169689Skan { 816169689Skan m = (f + t) / 2; 817169689Skan if (defs[m].dfs_num <= s) 818169689Skan f = m; 819169689Skan else 820169689Skan t = m; 821169689Skan } 822169689Skan 823169689Skan return defs[f].bb_index; 824169689Skan} 825169689Skan 826169689Skan/* Clean bits from PHIS for phi nodes whose value cannot be used in USES. 827169689Skan KILLS is a bitmap of blocks where the value is defined before any use. */ 828169689Skan 829169689Skanstatic void 830169689Skanprune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses) 831169689Skan{ 832169689Skan VEC(int, heap) *worklist; 833169689Skan bitmap_iterator bi; 834169689Skan unsigned i, b, p, u, top; 835169689Skan bitmap live_phis; 836169689Skan basic_block def_bb, use_bb; 837169689Skan edge e; 838169689Skan edge_iterator ei; 839169689Skan bitmap to_remove; 840169689Skan struct dom_dfsnum *defs; 841169689Skan unsigned n_defs, adef; 842169689Skan 843169689Skan if (bitmap_empty_p (uses)) 844169689Skan { 845169689Skan bitmap_clear (phis); 846169689Skan return; 847169689Skan } 848169689Skan 849169689Skan /* The phi must dominate a use, or an argument of a live phi. Also, we 850169689Skan do not create any phi nodes in def blocks, unless they are also livein. */ 851169689Skan to_remove = BITMAP_ALLOC (NULL); 852169689Skan bitmap_and_compl (to_remove, kills, uses); 853169689Skan bitmap_and_compl_into (phis, to_remove); 854169689Skan if (bitmap_empty_p (phis)) 855169689Skan { 856169689Skan BITMAP_FREE (to_remove); 857169689Skan return; 858169689Skan } 859169689Skan 860169689Skan /* We want to remove the unnecessary phi nodes, but we do not want to compute 861169689Skan liveness information, as that may be linear in the size of CFG, and if 862169689Skan there are lot of different variables to rewrite, this may lead to quadratic 863169689Skan behavior. 864169689Skan 865169689Skan Instead, we basically emulate standard dce. We put all uses to worklist, 866169689Skan then for each of them find the nearest def that dominates them. If this 867169689Skan def is a phi node, we mark it live, and if it was not live before, we 868169689Skan add the predecessors of its basic block to the worklist. 869169689Skan 870169689Skan To quickly locate the nearest def that dominates use, we use dfs numbering 871169689Skan of the dominance tree (that is already available in order to speed up 872169689Skan queries). For each def, we have the interval given by the dfs number on 873169689Skan entry to and on exit from the corresponding subtree in the dominance tree. 874169689Skan The nearest dominator for a given use is the smallest of these intervals 875169689Skan that contains entry and exit dfs numbers for the basic block with the use. 876169689Skan If we store the bounds for all the uses to an array and sort it, we can 877169689Skan locate the nearest dominating def in logarithmic time by binary search.*/ 878169689Skan bitmap_ior (to_remove, kills, phis); 879169689Skan n_defs = bitmap_count_bits (to_remove); 880169689Skan defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1); 881169689Skan defs[0].bb_index = 1; 882169689Skan defs[0].dfs_num = 0; 883169689Skan adef = 1; 884169689Skan EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi) 885169689Skan { 886169689Skan def_bb = BASIC_BLOCK (i); 887169689Skan defs[adef].bb_index = i; 888169689Skan defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb); 889169689Skan defs[adef + 1].bb_index = i; 890169689Skan defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb); 891169689Skan adef += 2; 892169689Skan } 893169689Skan BITMAP_FREE (to_remove); 894169689Skan gcc_assert (adef == 2 * n_defs + 1); 895169689Skan qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum); 896169689Skan gcc_assert (defs[0].bb_index == 1); 897169689Skan 898169689Skan /* Now each DEFS entry contains the number of the basic block to that the 899169689Skan dfs number corresponds. Change them to the number of basic block that 900169689Skan corresponds to the interval following the dfs number. Also, for the 901169689Skan dfs_out numbers, increase the dfs number by one (so that it corresponds 902169689Skan to the start of the following interval, not to the end of the current 903169689Skan one). We use WORKLIST as a stack. */ 904169689Skan worklist = VEC_alloc (int, heap, n_defs + 1); 905169689Skan VEC_quick_push (int, worklist, 1); 906169689Skan top = 1; 907169689Skan n_defs = 1; 908169689Skan for (i = 1; i < adef; i++) 909169689Skan { 910169689Skan b = defs[i].bb_index; 911169689Skan if (b == top) 912169689Skan { 913169689Skan /* This is a closing element. Interval corresponding to the top 914169689Skan of the stack after removing it follows. */ 915169689Skan VEC_pop (int, worklist); 916169689Skan top = VEC_index (int, worklist, VEC_length (int, worklist) - 1); 917169689Skan defs[n_defs].bb_index = top; 918169689Skan defs[n_defs].dfs_num = defs[i].dfs_num + 1; 919169689Skan } 920169689Skan else 921169689Skan { 922169689Skan /* Opening element. Nothing to do, just push it to the stack and move 923169689Skan it to the correct position. */ 924169689Skan defs[n_defs].bb_index = defs[i].bb_index; 925169689Skan defs[n_defs].dfs_num = defs[i].dfs_num; 926169689Skan VEC_quick_push (int, worklist, b); 927169689Skan top = b; 928169689Skan } 929169689Skan 930169689Skan /* If this interval starts at the same point as the previous one, cancel 931169689Skan the previous one. */ 932169689Skan if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num) 933169689Skan defs[n_defs - 1].bb_index = defs[n_defs].bb_index; 934169689Skan else 935169689Skan n_defs++; 936169689Skan } 937169689Skan VEC_pop (int, worklist); 938169689Skan gcc_assert (VEC_empty (int, worklist)); 939169689Skan 940169689Skan /* Now process the uses. */ 941169689Skan live_phis = BITMAP_ALLOC (NULL); 942169689Skan EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi) 943169689Skan { 944169689Skan VEC_safe_push (int, heap, worklist, i); 945169689Skan } 946169689Skan 947169689Skan while (!VEC_empty (int, worklist)) 948169689Skan { 949169689Skan b = VEC_pop (int, worklist); 950169689Skan if (b == ENTRY_BLOCK) 951169689Skan continue; 952169689Skan 953169689Skan /* If there is a phi node in USE_BB, it is made live. Otherwise, 954169689Skan find the def that dominates the immediate dominator of USE_BB 955169689Skan (the kill in USE_BB does not dominate the use). */ 956169689Skan if (bitmap_bit_p (phis, b)) 957169689Skan p = b; 958169689Skan else 959169689Skan { 960169689Skan use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b)); 961169689Skan p = find_dfsnum_interval (defs, n_defs, 962169689Skan bb_dom_dfs_in (CDI_DOMINATORS, use_bb)); 963169689Skan if (!bitmap_bit_p (phis, p)) 964169689Skan continue; 965169689Skan } 966169689Skan 967169689Skan /* If the phi node is already live, there is nothing to do. */ 968169689Skan if (bitmap_bit_p (live_phis, p)) 969169689Skan continue; 970169689Skan 971169689Skan /* Mark the phi as live, and add the new uses to the worklist. */ 972169689Skan bitmap_set_bit (live_phis, p); 973169689Skan def_bb = BASIC_BLOCK (p); 974169689Skan FOR_EACH_EDGE (e, ei, def_bb->preds) 975169689Skan { 976169689Skan u = e->src->index; 977169689Skan if (bitmap_bit_p (uses, u)) 978169689Skan continue; 979169689Skan 980169689Skan /* In case there is a kill directly in the use block, do not record 981169689Skan the use (this is also necessary for correctness, as we assume that 982169689Skan uses dominated by a def directly in their block have been filtered 983169689Skan out before). */ 984169689Skan if (bitmap_bit_p (kills, u)) 985169689Skan continue; 986169689Skan 987169689Skan bitmap_set_bit (uses, u); 988169689Skan VEC_safe_push (int, heap, worklist, u); 989169689Skan } 990169689Skan } 991169689Skan 992169689Skan VEC_free (int, heap, worklist); 993169689Skan bitmap_copy (phis, live_phis); 994169689Skan BITMAP_FREE (live_phis); 995169689Skan free (defs); 996169689Skan} 997169689Skan 998169689Skan/* Given a set of blocks with variable definitions (DEF_BLOCKS), 999169689Skan return a bitmap with all the blocks in the iterated dominance 1000169689Skan frontier of the blocks in DEF_BLOCKS. DFS contains dominance 1001169689Skan frontier information as returned by compute_dominance_frontiers. 1002169689Skan 1003169689Skan The resulting set of blocks are the potential sites where PHI nodes 1004169689Skan are needed. The caller is responsible from freeing the memory 1005169689Skan allocated for the return value. */ 1006169689Skan 1007169689Skanstatic bitmap 1008169689Skanfind_idf (bitmap def_blocks, bitmap *dfs) 1009169689Skan{ 1010169689Skan bitmap_iterator bi; 1011169689Skan unsigned bb_index; 1012169689Skan VEC(int,heap) *work_stack; 1013169689Skan bitmap phi_insertion_points; 1014169689Skan 1015169689Skan work_stack = VEC_alloc (int, heap, n_basic_blocks); 1016169689Skan phi_insertion_points = BITMAP_ALLOC (NULL); 1017169689Skan 1018169689Skan /* Seed the work list with all the blocks in DEF_BLOCKS. */ 1019169689Skan EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi) 1020169689Skan /* We use VEC_quick_push here for speed. This is safe because we 1021169689Skan know that the number of definition blocks is no greater than 1022169689Skan the number of basic blocks, which is the initial capacity of 1023169689Skan WORK_STACK. */ 1024169689Skan VEC_quick_push (int, work_stack, bb_index); 1025169689Skan 1026169689Skan /* Pop a block off the worklist, add every block that appears in 1027169689Skan the original block's DF that we have not already processed to 1028169689Skan the worklist. Iterate until the worklist is empty. Blocks 1029169689Skan which are added to the worklist are potential sites for 1030169689Skan PHI nodes. */ 1031169689Skan while (VEC_length (int, work_stack) > 0) 1032169689Skan { 1033169689Skan bb_index = VEC_pop (int, work_stack); 1034169689Skan 1035169689Skan /* Since the registration of NEW -> OLD name mappings is done 1036169689Skan separately from the call to update_ssa, when updating the SSA 1037169689Skan form, the basic blocks where new and/or old names are defined 1038169689Skan may have disappeared by CFG cleanup calls. In this case, 1039169689Skan we may pull a non-existing block from the work stack. */ 1040169689Skan gcc_assert (bb_index < (unsigned) last_basic_block); 1041169689Skan 1042169689Skan EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points, 1043169689Skan 0, bb_index, bi) 1044169689Skan { 1045169689Skan /* Use a safe push because if there is a definition of VAR 1046169689Skan in every basic block, then WORK_STACK may eventually have 1047169689Skan more than N_BASIC_BLOCK entries. */ 1048169689Skan VEC_safe_push (int, heap, work_stack, bb_index); 1049169689Skan bitmap_set_bit (phi_insertion_points, bb_index); 1050169689Skan } 1051169689Skan } 1052169689Skan 1053169689Skan VEC_free (int, heap, work_stack); 1054169689Skan 1055169689Skan return phi_insertion_points; 1056169689Skan} 1057169689Skan 1058169689Skan 1059169689Skan/* Return the set of blocks where variable VAR is defined and the blocks 1060169689Skan where VAR is live on entry (livein). Return NULL, if no entry is 1061169689Skan found in DEF_BLOCKS. */ 1062169689Skan 1063169689Skanstatic inline struct def_blocks_d * 1064169689Skanfind_def_blocks_for (tree var) 1065169689Skan{ 1066169689Skan struct def_blocks_d dm; 1067169689Skan dm.var = var; 1068169689Skan return (struct def_blocks_d *) htab_find (def_blocks, &dm); 1069169689Skan} 1070169689Skan 1071169689Skan 1072169689Skan/* Retrieve or create a default definition for symbol SYM. */ 1073169689Skan 1074169689Skanstatic inline tree 1075169689Skanget_default_def_for (tree sym) 1076169689Skan{ 1077169689Skan tree ddef = default_def (sym); 1078169689Skan 1079169689Skan if (ddef == NULL_TREE) 1080169689Skan { 1081169689Skan ddef = make_ssa_name (sym, build_empty_stmt ()); 1082169689Skan set_default_def (sym, ddef); 1083169689Skan } 1084169689Skan 1085169689Skan return ddef; 1086169689Skan} 1087169689Skan 1088169689Skan 1089169689Skan/* Marks phi node PHI in basic block BB for rewrite. */ 1090169689Skan 1091169689Skanstatic void 1092169689Skanmark_phi_for_rewrite (basic_block bb, tree phi) 1093169689Skan{ 1094169689Skan tree_vec phis; 1095169689Skan unsigned i, idx = bb->index; 1096169689Skan 1097169689Skan if (REWRITE_THIS_STMT (phi)) 1098169689Skan return; 1099169689Skan REWRITE_THIS_STMT (phi) = 1; 1100169689Skan 1101169689Skan if (!blocks_with_phis_to_rewrite) 1102169689Skan return; 1103169689Skan 1104169689Skan bitmap_set_bit (blocks_with_phis_to_rewrite, idx); 1105169689Skan VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1); 1106169689Skan for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++) 1107169689Skan VEC_quick_push (tree_vec, phis_to_rewrite, NULL); 1108169689Skan 1109169689Skan phis = VEC_index (tree_vec, phis_to_rewrite, idx); 1110169689Skan if (!phis) 1111169689Skan phis = VEC_alloc (tree, heap, 10); 1112169689Skan 1113169689Skan VEC_safe_push (tree, heap, phis, phi); 1114169689Skan VEC_replace (tree_vec, phis_to_rewrite, idx, phis); 1115169689Skan} 1116169689Skan 1117169689Skan/* Insert PHI nodes for variable VAR using the iterated dominance 1118169689Skan frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this 1119169689Skan function assumes that the caller is incrementally updating the SSA 1120169689Skan form, in which case (1) VAR is assumed to be an SSA name, (2) a new 1121169689Skan SSA name is created for VAR's symbol, and, (3) all the arguments 1122169689Skan for the newly created PHI node are set to VAR. 1123169689Skan 1124169689Skan PHI_INSERTION_POINTS is updated to reflect nodes that already had a 1125169689Skan PHI node for VAR. On exit, only the nodes that received a PHI node 1126169689Skan for VAR will be present in PHI_INSERTION_POINTS. */ 1127169689Skan 1128169689Skanstatic void 1129169689Skaninsert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p) 1130169689Skan{ 1131169689Skan unsigned bb_index; 1132169689Skan edge e; 1133169689Skan tree phi; 1134169689Skan basic_block bb; 1135169689Skan bitmap_iterator bi; 1136169689Skan struct def_blocks_d *def_map; 1137169689Skan 1138169689Skan def_map = find_def_blocks_for (var); 1139169689Skan gcc_assert (def_map); 1140169689Skan 1141169689Skan /* Remove the blocks where we already have PHI nodes for VAR. */ 1142169689Skan bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks); 1143169689Skan 1144169689Skan /* Remove obviously useless phi nodes. */ 1145169689Skan prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks, 1146169689Skan def_map->livein_blocks); 1147169689Skan 1148169689Skan /* And insert the PHI nodes. */ 1149169689Skan EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi) 1150169689Skan { 1151169689Skan bb = BASIC_BLOCK (bb_index); 1152169689Skan if (update_p) 1153169689Skan mark_block_for_update (bb); 1154169689Skan 1155169689Skan if (update_p && TREE_CODE (var) == SSA_NAME) 1156169689Skan { 1157169689Skan /* If we are rewriting SSA names, create the LHS of the PHI 1158169689Skan node by duplicating VAR. This is useful in the case of 1159169689Skan pointers, to also duplicate pointer attributes (alias 1160169689Skan information, in particular). */ 1161169689Skan edge_iterator ei; 1162169689Skan tree new_lhs; 1163169689Skan 1164169689Skan phi = create_phi_node (var, bb); 1165169689Skan new_lhs = duplicate_ssa_name (var, phi); 1166169689Skan SET_PHI_RESULT (phi, new_lhs); 1167169689Skan add_new_name_mapping (new_lhs, var); 1168169689Skan 1169169689Skan /* Add VAR to every argument slot of PHI. We need VAR in 1170169689Skan every argument so that rewrite_update_phi_arguments knows 1171169689Skan which name is this PHI node replacing. If VAR is a 1172169689Skan symbol marked for renaming, this is not necessary, the 1173169689Skan renamer will use the symbol on the LHS to get its 1174169689Skan reaching definition. */ 1175169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1176169689Skan add_phi_arg (phi, var, e); 1177169689Skan } 1178169689Skan else 1179169689Skan { 1180169689Skan tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var); 1181169689Skan phi = create_phi_node (sym, bb); 1182169689Skan } 1183169689Skan 1184169689Skan /* Mark this PHI node as interesting for update_ssa. */ 1185169689Skan REGISTER_DEFS_IN_THIS_STMT (phi) = 1; 1186169689Skan mark_phi_for_rewrite (bb, phi); 1187169689Skan } 1188169689Skan} 1189169689Skan 1190169689Skan 1191169689Skan/* Insert PHI nodes at the dominance frontier of blocks with variable 1192169689Skan definitions. DFS contains the dominance frontier information for 1193169689Skan the flowgraph. PHI nodes will only be inserted at the dominance 1194169689Skan frontier of definition blocks for variables whose NEED_PHI_STATE 1195169689Skan annotation is marked as ``maybe'' or ``unknown'' (computed by 1196169689Skan mark_def_sites). */ 1197169689Skan 1198169689Skanstatic void 1199169689Skaninsert_phi_nodes (bitmap *dfs) 1200169689Skan{ 1201169689Skan referenced_var_iterator rvi; 1202169689Skan tree var; 1203169689Skan 1204169689Skan timevar_push (TV_TREE_INSERT_PHI_NODES); 1205169689Skan 1206169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 1207169689Skan { 1208169689Skan struct def_blocks_d *def_map; 1209169689Skan bitmap idf; 1210169689Skan 1211169689Skan def_map = find_def_blocks_for (var); 1212169689Skan if (def_map == NULL) 1213169689Skan continue; 1214169689Skan 1215169689Skan if (get_phi_state (var) != NEED_PHI_STATE_NO) 1216169689Skan { 1217169689Skan idf = find_idf (def_map->def_blocks, dfs); 1218169689Skan insert_phi_nodes_for (var, idf, false); 1219169689Skan BITMAP_FREE (idf); 1220169689Skan } 1221169689Skan } 1222169689Skan 1223169689Skan timevar_pop (TV_TREE_INSERT_PHI_NODES); 1224169689Skan} 1225169689Skan 1226169689Skan 1227169689Skan/* Register DEF (an SSA_NAME) to be a new definition for its underlying 1228169689Skan variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition 1229169689Skan into the stack pointed to by BLOCK_DEFS_P. */ 1230169689Skan 1231169689Skanvoid 1232169689Skanregister_new_def (tree def, VEC(tree,heap) **block_defs_p) 1233169689Skan{ 1234169689Skan tree var = SSA_NAME_VAR (def); 1235169689Skan tree currdef; 1236169689Skan 1237169689Skan /* If this variable is set in a single basic block and all uses are 1238169689Skan dominated by the set(s) in that single basic block, then there is 1239169689Skan no reason to record anything for this variable in the block local 1240169689Skan definition stacks. Doing so just wastes time and memory. 1241169689Skan 1242169689Skan This is the same test to prune the set of variables which may 1243169689Skan need PHI nodes. So we just use that information since it's already 1244169689Skan computed and available for us to use. */ 1245169689Skan if (get_phi_state (var) == NEED_PHI_STATE_NO) 1246169689Skan { 1247169689Skan set_current_def (var, def); 1248169689Skan return; 1249169689Skan } 1250169689Skan 1251169689Skan currdef = get_current_def (var); 1252169689Skan 1253169689Skan /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is 1254169689Skan later used by the dominator tree callbacks to restore the reaching 1255169689Skan definitions for all the variables defined in the block after a recursive 1256169689Skan visit to all its immediately dominated blocks. If there is no current 1257169689Skan reaching definition, then just record the underlying _DECL node. */ 1258169689Skan VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var); 1259169689Skan 1260169689Skan /* Set the current reaching definition for VAR to be DEF. */ 1261169689Skan set_current_def (var, def); 1262169689Skan} 1263169689Skan 1264169689Skan 1265169689Skan/* Perform a depth-first traversal of the dominator tree looking for 1266169689Skan variables to rename. BB is the block where to start searching. 1267169689Skan Renaming is a five step process: 1268169689Skan 1269169689Skan 1- Every definition made by PHI nodes at the start of the blocks is 1270169689Skan registered as the current definition for the corresponding variable. 1271169689Skan 1272169689Skan 2- Every statement in BB is rewritten. USE and VUSE operands are 1273169689Skan rewritten with their corresponding reaching definition. DEF and 1274169689Skan VDEF targets are registered as new definitions. 1275169689Skan 1276169689Skan 3- All the PHI nodes in successor blocks of BB are visited. The 1277169689Skan argument corresponding to BB is replaced with its current reaching 1278169689Skan definition. 1279169689Skan 1280169689Skan 4- Recursively rewrite every dominator child block of BB. 1281169689Skan 1282169689Skan 5- Restore (in reverse order) the current reaching definition for every 1283169689Skan new definition introduced in this block. This is done so that when 1284169689Skan we return from the recursive call, all the current reaching 1285169689Skan definitions are restored to the names that were valid in the 1286169689Skan dominator parent of BB. */ 1287169689Skan 1288169689Skan/* SSA Rewriting Step 1. Initialization, create a block local stack 1289169689Skan of reaching definitions for new SSA names produced in this block 1290169689Skan (BLOCK_DEFS). Register new definitions for every PHI node in the 1291169689Skan block. */ 1292169689Skan 1293169689Skanstatic void 1294169689Skanrewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1295169689Skan basic_block bb) 1296169689Skan{ 1297169689Skan tree phi; 1298169689Skan 1299169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1300169689Skan fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index); 1301169689Skan 1302169689Skan /* Mark the unwind point for this block. */ 1303169689Skan VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE); 1304169689Skan 1305169689Skan /* Step 1. Register new definitions for every PHI node in the block. 1306169689Skan Conceptually, all the PHI nodes are executed in parallel and each PHI 1307169689Skan node introduces a new version for the associated variable. */ 1308169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1309169689Skan { 1310169689Skan tree result = PHI_RESULT (phi); 1311169689Skan register_new_def (result, &block_defs_stack); 1312169689Skan } 1313169689Skan} 1314169689Skan 1315169689Skan 1316169689Skan/* Return the current definition for variable VAR. If none is found, 1317169689Skan create a new SSA name to act as the zeroth definition for VAR. If VAR 1318169689Skan is call clobbered and there exists a more recent definition of 1319169689Skan GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR 1320169689Skan has been clobbered by a function call since its last assignment. */ 1321169689Skan 1322169689Skanstatic tree 1323169689Skanget_reaching_def (tree var) 1324169689Skan{ 1325169689Skan tree currdef_var, avar; 1326169689Skan 1327169689Skan /* Lookup the current reaching definition for VAR. */ 1328169689Skan currdef_var = get_current_def (var); 1329169689Skan 1330169689Skan /* If there is no reaching definition for VAR, create and register a 1331169689Skan default definition for it (if needed). */ 1332169689Skan if (currdef_var == NULL_TREE) 1333169689Skan { 1334169689Skan avar = DECL_P (var) ? var : SSA_NAME_VAR (var); 1335169689Skan currdef_var = get_default_def_for (avar); 1336169689Skan set_current_def (var, currdef_var); 1337169689Skan } 1338169689Skan 1339169689Skan /* Return the current reaching definition for VAR, or the default 1340169689Skan definition, if we had to create one. */ 1341169689Skan return currdef_var; 1342169689Skan} 1343169689Skan 1344169689Skan 1345169689Skan/* SSA Rewriting Step 2. Rewrite every variable used in each statement in 1346169689Skan the block with its immediate reaching definitions. Update the current 1347169689Skan definition of a variable when a new real or virtual definition is found. */ 1348169689Skan 1349169689Skanstatic void 1350169689Skanrewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1351169689Skan basic_block bb ATTRIBUTE_UNUSED, 1352169689Skan block_stmt_iterator si) 1353169689Skan{ 1354169689Skan tree stmt; 1355169689Skan use_operand_p use_p; 1356169689Skan def_operand_p def_p; 1357169689Skan ssa_op_iter iter; 1358169689Skan 1359169689Skan stmt = bsi_stmt (si); 1360169689Skan 1361169689Skan /* If mark_def_sites decided that we don't need to rewrite this 1362169689Skan statement, ignore it. */ 1363169689Skan gcc_assert (blocks_to_update == NULL); 1364169689Skan if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt)) 1365169689Skan return; 1366169689Skan 1367169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1368169689Skan { 1369169689Skan fprintf (dump_file, "Renaming statement "); 1370169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 1371169689Skan fprintf (dump_file, "\n"); 1372169689Skan } 1373169689Skan 1374169689Skan /* Step 1. Rewrite USES and VUSES in the statement. */ 1375169689Skan if (REWRITE_THIS_STMT (stmt)) 1376169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 1377169689Skan SSA_OP_ALL_USES|SSA_OP_ALL_KILLS) 1378169689Skan { 1379169689Skan tree var = USE_FROM_PTR (use_p); 1380169689Skan gcc_assert (DECL_P (var)); 1381169689Skan SET_USE (use_p, get_reaching_def (var)); 1382169689Skan } 1383169689Skan 1384169689Skan /* Step 2. Register the statement's DEF and VDEF operands. */ 1385169689Skan if (REGISTER_DEFS_IN_THIS_STMT (stmt)) 1386169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 1387169689Skan { 1388169689Skan tree var = DEF_FROM_PTR (def_p); 1389169689Skan gcc_assert (DECL_P (var)); 1390169689Skan SET_DEF (def_p, make_ssa_name (var, stmt)); 1391169689Skan register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack); 1392169689Skan } 1393169689Skan} 1394169689Skan 1395169689Skan 1396169689Skan/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for 1397169689Skan PHI nodes. For every PHI node found, add a new argument containing the 1398169689Skan current reaching definition for the variable and the edge through which 1399169689Skan that definition is reaching the PHI node. */ 1400169689Skan 1401169689Skanstatic void 1402169689Skanrewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1403169689Skan basic_block bb) 1404169689Skan{ 1405169689Skan edge e; 1406169689Skan edge_iterator ei; 1407169689Skan 1408169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1409169689Skan { 1410169689Skan tree phi; 1411169689Skan 1412169689Skan for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 1413169689Skan { 1414169689Skan tree currdef; 1415169689Skan currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi))); 1416169689Skan add_phi_arg (phi, currdef, e); 1417169689Skan } 1418169689Skan } 1419169689Skan} 1420169689Skan 1421169689Skan 1422169689Skan/* Called after visiting basic block BB. Restore CURRDEFS to its 1423169689Skan original value. */ 1424169689Skan 1425169689Skanstatic void 1426169689Skanrewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1427169689Skan basic_block bb ATTRIBUTE_UNUSED) 1428169689Skan{ 1429169689Skan /* Restore CURRDEFS to its original state. */ 1430169689Skan while (VEC_length (tree, block_defs_stack) > 0) 1431169689Skan { 1432169689Skan tree tmp = VEC_pop (tree, block_defs_stack); 1433169689Skan tree saved_def, var; 1434169689Skan 1435169689Skan if (tmp == NULL_TREE) 1436169689Skan break; 1437169689Skan 1438169689Skan /* If we recorded an SSA_NAME, then make the SSA_NAME the current 1439169689Skan definition of its underlying variable. If we recorded anything 1440169689Skan else, it must have been an _DECL node and its current reaching 1441169689Skan definition must have been NULL. */ 1442169689Skan if (TREE_CODE (tmp) == SSA_NAME) 1443169689Skan { 1444169689Skan saved_def = tmp; 1445169689Skan var = SSA_NAME_VAR (saved_def); 1446169689Skan } 1447169689Skan else 1448169689Skan { 1449169689Skan saved_def = NULL; 1450169689Skan var = tmp; 1451169689Skan } 1452169689Skan 1453169689Skan set_current_def (var, saved_def); 1454169689Skan } 1455169689Skan} 1456169689Skan 1457169689Skan 1458169689Skan/* Dump SSA information to FILE. */ 1459169689Skan 1460169689Skanvoid 1461169689Skandump_tree_ssa (FILE *file) 1462169689Skan{ 1463169689Skan basic_block bb; 1464169689Skan const char *funcname 1465169689Skan = lang_hooks.decl_printable_name (current_function_decl, 2); 1466169689Skan 1467169689Skan fprintf (file, "SSA information for %s\n\n", funcname); 1468169689Skan 1469169689Skan FOR_EACH_BB (bb) 1470169689Skan { 1471169689Skan dump_bb (bb, file, 0); 1472169689Skan fputs (" ", file); 1473169689Skan print_generic_stmt (file, phi_nodes (bb), dump_flags); 1474169689Skan fputs ("\n\n", file); 1475169689Skan } 1476169689Skan} 1477169689Skan 1478169689Skan 1479169689Skan/* Dump SSA information to stderr. */ 1480169689Skan 1481169689Skanvoid 1482169689Skandebug_tree_ssa (void) 1483169689Skan{ 1484169689Skan dump_tree_ssa (stderr); 1485169689Skan} 1486169689Skan 1487169689Skan 1488169689Skan/* Dump statistics for the hash table HTAB. */ 1489169689Skan 1490169689Skanstatic void 1491169689Skanhtab_statistics (FILE *file, htab_t htab) 1492169689Skan{ 1493169689Skan fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 1494169689Skan (long) htab_size (htab), 1495169689Skan (long) htab_elements (htab), 1496169689Skan htab_collisions (htab)); 1497169689Skan} 1498169689Skan 1499169689Skan 1500169689Skan/* Dump SSA statistics on FILE. */ 1501169689Skan 1502169689Skanvoid 1503169689Skandump_tree_ssa_stats (FILE *file) 1504169689Skan{ 1505169689Skan fprintf (file, "\nHash table statistics:\n"); 1506169689Skan 1507169689Skan fprintf (file, " def_blocks: "); 1508169689Skan htab_statistics (file, def_blocks); 1509169689Skan 1510169689Skan fprintf (file, "\n"); 1511169689Skan} 1512169689Skan 1513169689Skan 1514169689Skan/* Dump SSA statistics on stderr. */ 1515169689Skan 1516169689Skanvoid 1517169689Skandebug_tree_ssa_stats (void) 1518169689Skan{ 1519169689Skan dump_tree_ssa_stats (stderr); 1520169689Skan} 1521169689Skan 1522169689Skan 1523169689Skan/* Hashing and equality functions for DEF_BLOCKS. */ 1524169689Skan 1525169689Skanstatic hashval_t 1526169689Skandef_blocks_hash (const void *p) 1527169689Skan{ 1528169689Skan return htab_hash_pointer 1529169689Skan ((const void *)((const struct def_blocks_d *)p)->var); 1530169689Skan} 1531169689Skan 1532169689Skanstatic int 1533169689Skandef_blocks_eq (const void *p1, const void *p2) 1534169689Skan{ 1535169689Skan return ((const struct def_blocks_d *)p1)->var 1536169689Skan == ((const struct def_blocks_d *)p2)->var; 1537169689Skan} 1538169689Skan 1539169689Skan 1540169689Skan/* Free memory allocated by one entry in DEF_BLOCKS. */ 1541169689Skan 1542169689Skanstatic void 1543169689Skandef_blocks_free (void *p) 1544169689Skan{ 1545169689Skan struct def_blocks_d *entry = (struct def_blocks_d *) p; 1546169689Skan BITMAP_FREE (entry->def_blocks); 1547169689Skan BITMAP_FREE (entry->phi_blocks); 1548169689Skan BITMAP_FREE (entry->livein_blocks); 1549169689Skan free (entry); 1550169689Skan} 1551169689Skan 1552169689Skan 1553169689Skan/* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */ 1554169689Skan 1555169689Skanstatic int 1556169689Skandebug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED) 1557169689Skan{ 1558169689Skan struct def_blocks_d *db_p = (struct def_blocks_d *) *slot; 1559169689Skan 1560169689Skan fprintf (stderr, "VAR: "); 1561169689Skan print_generic_expr (stderr, db_p->var, dump_flags); 1562169689Skan bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}"); 1563169689Skan bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n"); 1564169689Skan 1565169689Skan return 1; 1566169689Skan} 1567169689Skan 1568169689Skan 1569169689Skan/* Dump the DEF_BLOCKS hash table on stderr. */ 1570169689Skan 1571169689Skanvoid 1572169689Skandebug_def_blocks (void) 1573169689Skan{ 1574169689Skan htab_traverse (def_blocks, debug_def_blocks_r, NULL); 1575169689Skan} 1576169689Skan 1577169689Skan 1578169689Skan/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */ 1579169689Skan 1580169689Skanstatic inline void 1581169689Skanregister_new_update_single (tree new_name, tree old_name) 1582169689Skan{ 1583169689Skan tree currdef = get_current_def (old_name); 1584169689Skan 1585169689Skan /* Push the current reaching definition into *BLOCK_DEFS_P. 1586169689Skan This stack is later used by the dominator tree callbacks to 1587169689Skan restore the reaching definitions for all the variables 1588169689Skan defined in the block after a recursive visit to all its 1589169689Skan immediately dominated blocks. */ 1590169689Skan VEC_reserve (tree, heap, block_defs_stack, 2); 1591169689Skan VEC_quick_push (tree, block_defs_stack, currdef); 1592169689Skan VEC_quick_push (tree, block_defs_stack, old_name); 1593169689Skan 1594169689Skan /* Set the current reaching definition for OLD_NAME to be 1595169689Skan NEW_NAME. */ 1596169689Skan set_current_def (old_name, new_name); 1597169689Skan} 1598169689Skan 1599169689Skan 1600169689Skan/* Register NEW_NAME to be the new reaching definition for all the 1601169689Skan names in OLD_NAMES. Used by the incremental SSA update routines to 1602169689Skan replace old SSA names with new ones. */ 1603169689Skan 1604169689Skanstatic inline void 1605169689Skanregister_new_update_set (tree new_name, bitmap old_names) 1606169689Skan{ 1607169689Skan bitmap_iterator bi; 1608169689Skan unsigned i; 1609169689Skan 1610169689Skan EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi) 1611169689Skan register_new_update_single (new_name, ssa_name (i)); 1612169689Skan} 1613169689Skan 1614169689Skan 1615169689Skan/* Initialization of block data structures for the incremental SSA 1616169689Skan update pass. Create a block local stack of reaching definitions 1617169689Skan for new SSA names produced in this block (BLOCK_DEFS). Register 1618169689Skan new definitions for every PHI node in the block. */ 1619169689Skan 1620169689Skanstatic void 1621169689Skanrewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1622169689Skan basic_block bb) 1623169689Skan{ 1624169689Skan edge e; 1625169689Skan edge_iterator ei; 1626169689Skan tree phi; 1627169689Skan bool is_abnormal_phi; 1628169689Skan 1629169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1630169689Skan fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n", 1631169689Skan bb->index); 1632169689Skan 1633169689Skan /* Mark the unwind point for this block. */ 1634169689Skan VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE); 1635169689Skan 1636169689Skan if (!bitmap_bit_p (blocks_to_update, bb->index)) 1637169689Skan return; 1638169689Skan 1639169689Skan /* Mark the LHS if any of the arguments flows through an abnormal 1640169689Skan edge. */ 1641169689Skan is_abnormal_phi = false; 1642169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1643169689Skan if (e->flags & EDGE_ABNORMAL) 1644169689Skan { 1645169689Skan is_abnormal_phi = true; 1646169689Skan break; 1647169689Skan } 1648169689Skan 1649169689Skan /* If any of the PHI nodes is a replacement for a name in 1650169689Skan OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then 1651169689Skan register it as a new definition for its corresponding name. Also 1652169689Skan register definitions for names whose underlying symbols are 1653169689Skan marked for renaming. */ 1654169689Skan 1655169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1656169689Skan { 1657169689Skan tree lhs, lhs_sym; 1658169689Skan 1659169689Skan if (!REGISTER_DEFS_IN_THIS_STMT (phi)) 1660169689Skan continue; 1661169689Skan 1662169689Skan lhs = PHI_RESULT (phi); 1663169689Skan lhs_sym = SSA_NAME_VAR (lhs); 1664169689Skan 1665169689Skan if (symbol_marked_for_renaming (lhs_sym)) 1666169689Skan register_new_update_single (lhs, lhs_sym); 1667169689Skan else 1668169689Skan { 1669169689Skan /* If LHS is a new name, register a new definition for all 1670169689Skan the names replaced by LHS. */ 1671169689Skan if (is_new_name (lhs)) 1672169689Skan register_new_update_set (lhs, names_replaced_by (lhs)); 1673169689Skan 1674169689Skan /* If LHS is an OLD name, register it as a new definition 1675169689Skan for itself. */ 1676169689Skan if (is_old_name (lhs)) 1677169689Skan register_new_update_single (lhs, lhs); 1678169689Skan } 1679169689Skan 1680169689Skan if (is_abnormal_phi) 1681169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1; 1682169689Skan } 1683169689Skan} 1684169689Skan 1685169689Skan 1686169689Skan/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore 1687169689Skan the current reaching definition of every name re-written in BB to 1688169689Skan the original reaching definition before visiting BB. This 1689169689Skan unwinding must be done in the opposite order to what is done in 1690169689Skan register_new_update_set. */ 1691169689Skan 1692169689Skanstatic void 1693169689Skanrewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1694169689Skan basic_block bb ATTRIBUTE_UNUSED) 1695169689Skan{ 1696169689Skan while (VEC_length (tree, block_defs_stack) > 0) 1697169689Skan { 1698169689Skan tree var = VEC_pop (tree, block_defs_stack); 1699169689Skan tree saved_def; 1700169689Skan 1701169689Skan /* NULL indicates the unwind stop point for this block (see 1702169689Skan rewrite_update_init_block). */ 1703169689Skan if (var == NULL) 1704169689Skan return; 1705169689Skan 1706169689Skan saved_def = VEC_pop (tree, block_defs_stack); 1707169689Skan set_current_def (var, saved_def); 1708169689Skan } 1709169689Skan} 1710169689Skan 1711169689Skan 1712169689Skan/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or 1713169689Skan it is a symbol marked for renaming, replace it with USE_P's current 1714169689Skan reaching definition. */ 1715169689Skan 1716169689Skanstatic inline void 1717169689Skanmaybe_replace_use (use_operand_p use_p) 1718169689Skan{ 1719169689Skan tree rdef = NULL_TREE; 1720169689Skan tree use = USE_FROM_PTR (use_p); 1721169689Skan tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 1722169689Skan 1723169689Skan if (symbol_marked_for_renaming (sym)) 1724169689Skan rdef = get_reaching_def (sym); 1725169689Skan else if (is_old_name (use)) 1726169689Skan rdef = get_reaching_def (use); 1727169689Skan 1728169689Skan if (rdef && rdef != use) 1729169689Skan SET_USE (use_p, rdef); 1730169689Skan} 1731169689Skan 1732169689Skan 1733169689Skan/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES 1734169689Skan or OLD_SSA_NAMES, or if it is a symbol marked for renaming, 1735169689Skan register it as the current definition for the names replaced by 1736169689Skan DEF_P. */ 1737169689Skan 1738169689Skanstatic inline void 1739169689Skanmaybe_register_def (def_operand_p def_p, tree stmt) 1740169689Skan{ 1741169689Skan tree def = DEF_FROM_PTR (def_p); 1742169689Skan tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 1743169689Skan 1744169689Skan /* If DEF is a naked symbol that needs renaming, create a 1745169689Skan new name for it. */ 1746169689Skan if (symbol_marked_for_renaming (sym)) 1747169689Skan { 1748169689Skan if (DECL_P (def)) 1749169689Skan { 1750169689Skan def = make_ssa_name (def, stmt); 1751169689Skan SET_DEF (def_p, def); 1752169689Skan } 1753169689Skan 1754169689Skan register_new_update_single (def, sym); 1755169689Skan } 1756169689Skan else 1757169689Skan { 1758169689Skan /* If DEF is a new name, register it as a new definition 1759169689Skan for all the names replaced by DEF. */ 1760169689Skan if (is_new_name (def)) 1761169689Skan register_new_update_set (def, names_replaced_by (def)); 1762169689Skan 1763169689Skan /* If DEF is an old name, register DEF as a new 1764169689Skan definition for itself. */ 1765169689Skan if (is_old_name (def)) 1766169689Skan register_new_update_single (def, def); 1767169689Skan } 1768169689Skan} 1769169689Skan 1770169689Skan 1771169689Skan/* Update every variable used in the statement pointed-to by SI. The 1772169689Skan statement is assumed to be in SSA form already. Names in 1773169689Skan OLD_SSA_NAMES used by SI will be updated to their current reaching 1774169689Skan definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI 1775169689Skan will be registered as a new definition for their corresponding name 1776169689Skan in OLD_SSA_NAMES. */ 1777169689Skan 1778169689Skanstatic void 1779169689Skanrewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1780169689Skan basic_block bb ATTRIBUTE_UNUSED, 1781169689Skan block_stmt_iterator si) 1782169689Skan{ 1783169689Skan stmt_ann_t ann; 1784169689Skan tree stmt; 1785169689Skan use_operand_p use_p; 1786169689Skan def_operand_p def_p; 1787169689Skan ssa_op_iter iter; 1788169689Skan 1789169689Skan stmt = bsi_stmt (si); 1790169689Skan ann = stmt_ann (stmt); 1791169689Skan 1792169689Skan gcc_assert (bitmap_bit_p (blocks_to_update, bb->index)); 1793169689Skan 1794169689Skan /* Only update marked statements. */ 1795169689Skan if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt)) 1796169689Skan return; 1797169689Skan 1798169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1799169689Skan { 1800169689Skan fprintf (dump_file, "Updating SSA information for statement "); 1801169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 1802169689Skan fprintf (dump_file, "\n"); 1803169689Skan } 1804169689Skan 1805169689Skan /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying 1806169689Skan symbol is marked for renaming. */ 1807169689Skan if (REWRITE_THIS_STMT (stmt)) 1808169689Skan { 1809169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) 1810169689Skan maybe_replace_use (use_p); 1811169689Skan 1812169689Skan if (need_to_update_vops_p) 1813169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 1814169689Skan SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 1815169689Skan maybe_replace_use (use_p); 1816169689Skan } 1817169689Skan 1818169689Skan /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES. 1819169689Skan Also register definitions for names whose underlying symbol is 1820169689Skan marked for renaming. */ 1821169689Skan if (REGISTER_DEFS_IN_THIS_STMT (stmt)) 1822169689Skan { 1823169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF) 1824169689Skan maybe_register_def (def_p, stmt); 1825169689Skan 1826169689Skan if (need_to_update_vops_p) 1827169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS) 1828169689Skan maybe_register_def (def_p, stmt); 1829169689Skan } 1830169689Skan} 1831169689Skan 1832169689Skan 1833169689Skan/* Replace the operand pointed to by USE_P with USE's current reaching 1834169689Skan definition. */ 1835169689Skan 1836169689Skanstatic inline void 1837169689Skanreplace_use (use_operand_p use_p, tree use) 1838169689Skan{ 1839169689Skan tree rdef = get_reaching_def (use); 1840169689Skan if (rdef != use) 1841169689Skan SET_USE (use_p, rdef); 1842169689Skan} 1843169689Skan 1844169689Skan 1845169689Skan/* Visit all the successor blocks of BB looking for PHI nodes. For 1846169689Skan every PHI node found, check if any of its arguments is in 1847169689Skan OLD_SSA_NAMES. If so, and if the argument has a current reaching 1848169689Skan definition, replace it. */ 1849169689Skan 1850169689Skanstatic void 1851169689Skanrewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1852169689Skan basic_block bb) 1853169689Skan{ 1854169689Skan edge e; 1855169689Skan edge_iterator ei; 1856169689Skan unsigned i; 1857169689Skan 1858169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1859169689Skan { 1860169689Skan tree phi; 1861169689Skan tree_vec phis; 1862169689Skan 1863169689Skan if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index)) 1864169689Skan continue; 1865169689Skan 1866169689Skan phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index); 1867169689Skan for (i = 0; VEC_iterate (tree, phis, i, phi); i++) 1868169689Skan { 1869169689Skan tree arg; 1870169689Skan use_operand_p arg_p; 1871169689Skan 1872169689Skan gcc_assert (REWRITE_THIS_STMT (phi)); 1873169689Skan 1874169689Skan arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); 1875169689Skan arg = USE_FROM_PTR (arg_p); 1876169689Skan 1877169689Skan if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME) 1878169689Skan continue; 1879169689Skan 1880169689Skan if (arg == NULL_TREE) 1881169689Skan { 1882169689Skan /* When updating a PHI node for a recently introduced 1883169689Skan symbol we may find NULL arguments. That's why we 1884169689Skan take the symbol from the LHS of the PHI node. */ 1885169689Skan replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi))); 1886169689Skan } 1887169689Skan else 1888169689Skan { 1889169689Skan tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg); 1890169689Skan 1891169689Skan if (symbol_marked_for_renaming (sym)) 1892169689Skan replace_use (arg_p, sym); 1893169689Skan else if (is_old_name (arg)) 1894169689Skan replace_use (arg_p, arg); 1895169689Skan } 1896169689Skan 1897169689Skan if (e->flags & EDGE_ABNORMAL) 1898169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1; 1899169689Skan } 1900169689Skan } 1901169689Skan} 1902169689Skan 1903169689Skan 1904169689Skan/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA 1905169689Skan form. 1906169689Skan 1907169689Skan ENTRY indicates the block where to start. Every block dominated by 1908169689Skan ENTRY will be rewritten. 1909169689Skan 1910169689Skan WHAT indicates what actions will be taken by the renamer (see enum 1911169689Skan rewrite_mode). 1912169689Skan 1913169689Skan BLOCKS are the set of interesting blocks for the dominator walker 1914169689Skan to process. If this set is NULL, then all the nodes dominated 1915169689Skan by ENTRY are walked. Otherwise, blocks dominated by ENTRY that 1916169689Skan are not present in BLOCKS are ignored. */ 1917169689Skan 1918169689Skanstatic void 1919169689Skanrewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks) 1920169689Skan{ 1921169689Skan struct dom_walk_data walk_data; 1922169689Skan 1923169689Skan /* Rewrite all the basic blocks in the program. */ 1924169689Skan timevar_push (TV_TREE_SSA_REWRITE_BLOCKS); 1925169689Skan 1926169689Skan /* Setup callbacks for the generic dominator tree walker. */ 1927169689Skan memset (&walk_data, 0, sizeof (walk_data)); 1928169689Skan 1929169689Skan walk_data.dom_direction = CDI_DOMINATORS; 1930169689Skan walk_data.interesting_blocks = blocks; 1931169689Skan 1932169689Skan if (what == REWRITE_UPDATE) 1933169689Skan walk_data.before_dom_children_before_stmts = rewrite_update_init_block; 1934169689Skan else 1935169689Skan walk_data.before_dom_children_before_stmts = rewrite_initialize_block; 1936169689Skan 1937169689Skan if (what == REWRITE_ALL) 1938169689Skan walk_data.before_dom_children_walk_stmts = rewrite_stmt; 1939169689Skan else if (what == REWRITE_UPDATE) 1940169689Skan walk_data.before_dom_children_walk_stmts = rewrite_update_stmt; 1941169689Skan else 1942169689Skan gcc_unreachable (); 1943169689Skan 1944169689Skan if (what == REWRITE_ALL) 1945169689Skan walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments; 1946169689Skan else if (what == REWRITE_UPDATE) 1947169689Skan walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments; 1948169689Skan else 1949169689Skan gcc_unreachable (); 1950169689Skan 1951169689Skan if (what == REWRITE_ALL) 1952169689Skan walk_data.after_dom_children_after_stmts = rewrite_finalize_block; 1953169689Skan else if (what == REWRITE_UPDATE) 1954169689Skan walk_data.after_dom_children_after_stmts = rewrite_update_fini_block; 1955169689Skan else 1956169689Skan gcc_unreachable (); 1957169689Skan 1958169689Skan block_defs_stack = VEC_alloc (tree, heap, 10); 1959169689Skan 1960169689Skan /* Initialize the dominator walker. */ 1961169689Skan init_walk_dominator_tree (&walk_data); 1962169689Skan 1963169689Skan /* Recursively walk the dominator tree rewriting each statement in 1964169689Skan each basic block. */ 1965169689Skan walk_dominator_tree (&walk_data, entry); 1966169689Skan 1967169689Skan /* Finalize the dominator walker. */ 1968169689Skan fini_walk_dominator_tree (&walk_data); 1969169689Skan 1970169689Skan /* Debugging dumps. */ 1971169689Skan if (dump_file && (dump_flags & TDF_STATS)) 1972169689Skan { 1973169689Skan dump_dfa_stats (dump_file); 1974169689Skan if (def_blocks) 1975169689Skan dump_tree_ssa_stats (dump_file); 1976169689Skan } 1977169689Skan 1978169689Skan if (def_blocks) 1979169689Skan { 1980169689Skan htab_delete (def_blocks); 1981169689Skan def_blocks = NULL; 1982169689Skan } 1983169689Skan 1984169689Skan VEC_free (tree, heap, block_defs_stack); 1985169689Skan 1986169689Skan timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS); 1987169689Skan} 1988169689Skan 1989169689Skan 1990169689Skan/* Block initialization routine for mark_def_sites. Clear the 1991169689Skan KILLS bitmap at the start of each block. */ 1992169689Skan 1993169689Skanstatic void 1994169689Skanmark_def_sites_initialize_block (struct dom_walk_data *walk_data, 1995169689Skan basic_block bb ATTRIBUTE_UNUSED) 1996169689Skan{ 1997169689Skan struct mark_def_sites_global_data *gd = 1998169689Skan (struct mark_def_sites_global_data *) walk_data->global_data; 1999169689Skan bitmap kills = gd->kills; 2000169689Skan bitmap_clear (kills); 2001169689Skan} 2002169689Skan 2003169689Skan 2004169689Skan/* Mark the definition site blocks for each variable, so that we know 2005169689Skan where the variable is actually live. 2006169689Skan 2007169689Skan INTERESTING_BLOCKS will be filled in with all the blocks that 2008169689Skan should be processed by the renamer. It is assumed to be 2009169689Skan initialized and zeroed by the caller. */ 2010169689Skan 2011169689Skanstatic void 2012169689Skanmark_def_site_blocks (sbitmap interesting_blocks) 2013169689Skan{ 2014169689Skan struct dom_walk_data walk_data; 2015169689Skan struct mark_def_sites_global_data mark_def_sites_global_data; 2016169689Skan referenced_var_iterator rvi; 2017169689Skan tree var; 2018169689Skan 2019169689Skan /* Allocate memory for the DEF_BLOCKS hash table. */ 2020169689Skan def_blocks = htab_create (num_referenced_vars, 2021169689Skan def_blocks_hash, def_blocks_eq, def_blocks_free); 2022169689Skan FOR_EACH_REFERENCED_VAR(var, rvi) 2023169689Skan set_current_def (var, NULL_TREE); 2024169689Skan 2025169689Skan /* Setup callbacks for the generic dominator tree walker to find and 2026169689Skan mark definition sites. */ 2027169689Skan walk_data.walk_stmts_backward = false; 2028169689Skan walk_data.dom_direction = CDI_DOMINATORS; 2029169689Skan walk_data.initialize_block_local_data = NULL; 2030169689Skan walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block; 2031169689Skan walk_data.before_dom_children_walk_stmts = mark_def_sites; 2032169689Skan walk_data.before_dom_children_after_stmts = NULL; 2033169689Skan walk_data.after_dom_children_before_stmts = NULL; 2034169689Skan walk_data.after_dom_children_walk_stmts = NULL; 2035169689Skan walk_data.after_dom_children_after_stmts = NULL; 2036169689Skan walk_data.interesting_blocks = NULL; 2037169689Skan 2038169689Skan /* Notice that this bitmap is indexed using variable UIDs, so it must be 2039169689Skan large enough to accommodate all the variables referenced in the 2040169689Skan function, not just the ones we are renaming. */ 2041169689Skan mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL); 2042169689Skan 2043169689Skan /* Create the set of interesting blocks that will be filled by 2044169689Skan mark_def_sites. */ 2045169689Skan mark_def_sites_global_data.interesting_blocks = interesting_blocks; 2046169689Skan walk_data.global_data = &mark_def_sites_global_data; 2047169689Skan 2048169689Skan /* We do not have any local data. */ 2049169689Skan walk_data.block_local_data_size = 0; 2050169689Skan 2051169689Skan /* Initialize the dominator walker. */ 2052169689Skan init_walk_dominator_tree (&walk_data); 2053169689Skan 2054169689Skan /* Recursively walk the dominator tree. */ 2055169689Skan walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 2056169689Skan 2057169689Skan /* Finalize the dominator walker. */ 2058169689Skan fini_walk_dominator_tree (&walk_data); 2059169689Skan 2060169689Skan /* We no longer need this bitmap, clear and free it. */ 2061169689Skan BITMAP_FREE (mark_def_sites_global_data.kills); 2062169689Skan} 2063169689Skan 2064169689Skan 2065169689Skan/* Main entry point into the SSA builder. The renaming process 2066169689Skan proceeds in four main phases: 2067169689Skan 2068169689Skan 1- Compute dominance frontier and immediate dominators, needed to 2069169689Skan insert PHI nodes and rename the function in dominator tree 2070169689Skan order. 2071169689Skan 2072169689Skan 2- Find and mark all the blocks that define variables 2073169689Skan (mark_def_site_blocks). 2074169689Skan 2075169689Skan 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes). 2076169689Skan 2077169689Skan 4- Rename all the blocks (rewrite_blocks) and statements in the program. 2078169689Skan 2079169689Skan Steps 3 and 4 are done using the dominator tree walker 2080169689Skan (walk_dominator_tree). */ 2081169689Skan 2082169689Skanstatic unsigned int 2083169689Skanrewrite_into_ssa (void) 2084169689Skan{ 2085169689Skan bitmap *dfs; 2086169689Skan basic_block bb; 2087169689Skan sbitmap interesting_blocks; 2088169689Skan 2089169689Skan timevar_push (TV_TREE_SSA_OTHER); 2090169689Skan 2091169689Skan /* Initialize operand data structures. */ 2092169689Skan init_ssa_operands (); 2093169689Skan 2094169689Skan /* Initialize the set of interesting blocks. The callback 2095169689Skan mark_def_sites will add to this set those blocks that the renamer 2096169689Skan should process. */ 2097169689Skan interesting_blocks = sbitmap_alloc (last_basic_block); 2098169689Skan sbitmap_zero (interesting_blocks); 2099169689Skan 2100169689Skan /* Initialize dominance frontier. */ 2101169689Skan dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap)); 2102169689Skan FOR_EACH_BB (bb) 2103169689Skan dfs[bb->index] = BITMAP_ALLOC (NULL); 2104169689Skan 2105169689Skan /* 1- Compute dominance frontiers. */ 2106169689Skan calculate_dominance_info (CDI_DOMINATORS); 2107169689Skan compute_dominance_frontiers (dfs); 2108169689Skan 2109169689Skan /* 2- Find and mark definition sites. */ 2110169689Skan mark_def_site_blocks (interesting_blocks); 2111169689Skan 2112169689Skan /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */ 2113169689Skan insert_phi_nodes (dfs); 2114169689Skan 2115169689Skan /* 4- Rename all the blocks. */ 2116169689Skan rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks); 2117169689Skan 2118169689Skan /* Free allocated memory. */ 2119169689Skan FOR_EACH_BB (bb) 2120169689Skan BITMAP_FREE (dfs[bb->index]); 2121169689Skan free (dfs); 2122169689Skan sbitmap_free (interesting_blocks); 2123169689Skan 2124169689Skan timevar_pop (TV_TREE_SSA_OTHER); 2125169689Skan in_ssa_p = true; 2126169689Skan return 0; 2127169689Skan} 2128169689Skan 2129169689Skan 2130169689Skanstruct tree_opt_pass pass_build_ssa = 2131169689Skan{ 2132169689Skan "ssa", /* name */ 2133169689Skan NULL, /* gate */ 2134169689Skan rewrite_into_ssa, /* execute */ 2135169689Skan NULL, /* sub */ 2136169689Skan NULL, /* next */ 2137169689Skan 0, /* static_pass_number */ 2138169689Skan 0, /* tv_id */ 2139169689Skan PROP_cfg | PROP_referenced_vars, /* properties_required */ 2140169689Skan PROP_ssa, /* properties_provided */ 2141169689Skan 0, /* properties_destroyed */ 2142169689Skan 0, /* todo_flags_start */ 2143169689Skan TODO_dump_func 2144169689Skan | TODO_verify_ssa 2145169689Skan | TODO_remove_unused_locals, /* todo_flags_finish */ 2146169689Skan 0 /* letter */ 2147169689Skan}; 2148169689Skan 2149169689Skan 2150169689Skan/* Mark the definition of VAR at STMT and BB as interesting for the 2151169689Skan renamer. BLOCKS is the set of blocks that need updating. */ 2152169689Skan 2153169689Skanstatic void 2154169689Skanmark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p) 2155169689Skan{ 2156169689Skan gcc_assert (bitmap_bit_p (blocks_to_update, bb->index)); 2157169689Skan REGISTER_DEFS_IN_THIS_STMT (stmt) = 1; 2158169689Skan 2159169689Skan if (insert_phi_p) 2160169689Skan { 2161169689Skan bool is_phi_p = TREE_CODE (stmt) == PHI_NODE; 2162169689Skan 2163169689Skan set_def_block (var, bb, is_phi_p); 2164169689Skan 2165169689Skan /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition 2166169689Skan site for both itself and all the old names replaced by it. */ 2167169689Skan if (TREE_CODE (var) == SSA_NAME && is_new_name (var)) 2168169689Skan { 2169169689Skan bitmap_iterator bi; 2170169689Skan unsigned i; 2171169689Skan bitmap set = names_replaced_by (var); 2172169689Skan if (set) 2173169689Skan EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 2174169689Skan set_def_block (ssa_name (i), bb, is_phi_p); 2175169689Skan } 2176169689Skan } 2177169689Skan} 2178169689Skan 2179169689Skan 2180169689Skan/* Mark the use of VAR at STMT and BB as interesting for the 2181169689Skan renamer. INSERT_PHI_P is true if we are going to insert new PHI 2182169689Skan nodes. */ 2183169689Skan 2184169689Skanstatic inline void 2185169689Skanmark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p) 2186169689Skan{ 2187169689Skan basic_block def_bb = bb_for_stmt (stmt); 2188169689Skan 2189169689Skan mark_block_for_update (def_bb); 2190169689Skan mark_block_for_update (bb); 2191169689Skan 2192169689Skan if (TREE_CODE (stmt) == PHI_NODE) 2193169689Skan mark_phi_for_rewrite (def_bb, stmt); 2194169689Skan else 2195169689Skan REWRITE_THIS_STMT (stmt) = 1; 2196169689Skan 2197169689Skan /* If VAR has not been defined in BB, then it is live-on-entry 2198169689Skan to BB. Note that we cannot just use the block holding VAR's 2199169689Skan definition because if VAR is one of the names in OLD_SSA_NAMES, 2200169689Skan it will have several definitions (itself and all the names that 2201169689Skan replace it). */ 2202169689Skan if (insert_phi_p) 2203169689Skan { 2204169689Skan struct def_blocks_d *db_p = get_def_blocks_for (var); 2205169689Skan if (!bitmap_bit_p (db_p->def_blocks, bb->index)) 2206169689Skan set_livein_block (var, bb); 2207169689Skan } 2208169689Skan} 2209169689Skan 2210169689Skan 2211169689Skan/* Do a dominator walk starting at BB processing statements that 2212169689Skan reference symbols in SYMS_TO_RENAME. This is very similar to 2213169689Skan mark_def_sites, but the scan handles statements whose operands may 2214169689Skan already be SSA names. 2215169689Skan 2216169689Skan If INSERT_PHI_P is true, mark those uses as live in the 2217169689Skan corresponding block. This is later used by the PHI placement 2218169689Skan algorithm to make PHI pruning decisions. */ 2219169689Skan 2220169689Skanstatic void 2221169689Skanprepare_block_for_update (basic_block bb, bool insert_phi_p) 2222169689Skan{ 2223169689Skan basic_block son; 2224169689Skan block_stmt_iterator si; 2225169689Skan tree phi; 2226169689Skan edge e; 2227169689Skan edge_iterator ei; 2228169689Skan 2229169689Skan mark_block_for_update (bb); 2230169689Skan 2231169689Skan /* Process PHI nodes marking interesting those that define or use 2232169689Skan the symbols that we are interested in. */ 2233169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2234169689Skan { 2235169689Skan tree lhs_sym, lhs = PHI_RESULT (phi); 2236169689Skan 2237169689Skan lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs); 2238169689Skan 2239169689Skan if (!symbol_marked_for_renaming (lhs_sym)) 2240169689Skan continue; 2241169689Skan mark_def_interesting (lhs_sym, phi, bb, insert_phi_p); 2242169689Skan 2243169689Skan /* Mark the uses in phi nodes as interesting. It would be more correct 2244169689Skan to process the arguments of the phi nodes of the successor edges of 2245169689Skan BB at the end of prepare_block_for_update, however, that turns out 2246169689Skan to be significantly more expensive. Doing it here is conservatively 2247169689Skan correct -- it may only cause us to believe a value to be live in a 2248169689Skan block that also contains its definition, and thus insert a few more 2249169689Skan phi nodes for it. */ 2250169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2251169689Skan { 2252169689Skan mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p); 2253169689Skan } 2254169689Skan } 2255169689Skan 2256169689Skan /* Process the statements. */ 2257169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 2258169689Skan { 2259169689Skan tree stmt; 2260169689Skan ssa_op_iter i; 2261169689Skan use_operand_p use_p; 2262169689Skan def_operand_p def_p; 2263169689Skan 2264169689Skan stmt = bsi_stmt (si); 2265169689Skan 2266169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE) 2267169689Skan { 2268169689Skan tree use = USE_FROM_PTR (use_p); 2269169689Skan tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 2270169689Skan if (symbol_marked_for_renaming (sym)) 2271169689Skan mark_use_interesting (use, stmt, bb, insert_phi_p); 2272169689Skan } 2273169689Skan 2274169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF) 2275169689Skan { 2276169689Skan tree def = DEF_FROM_PTR (def_p); 2277169689Skan tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 2278169689Skan 2279169689Skan if (symbol_marked_for_renaming (sym)) 2280169689Skan mark_def_interesting (def, stmt, bb, insert_phi_p); 2281169689Skan } 2282169689Skan 2283169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS) 2284169689Skan { 2285169689Skan tree def = DEF_FROM_PTR (def_p); 2286169689Skan tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 2287169689Skan 2288169689Skan if (symbol_marked_for_renaming (sym)) 2289169689Skan { 2290169689Skan mark_use_interesting (sym, stmt, bb, insert_phi_p); 2291169689Skan mark_def_interesting (sym, stmt, bb, insert_phi_p); 2292169689Skan } 2293169689Skan } 2294169689Skan 2295169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE) 2296169689Skan { 2297169689Skan tree use = USE_FROM_PTR (use_p); 2298169689Skan tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 2299169689Skan 2300169689Skan if (symbol_marked_for_renaming (sym)) 2301169689Skan mark_use_interesting (sym, stmt, bb, insert_phi_p); 2302169689Skan } 2303169689Skan } 2304169689Skan 2305169689Skan /* Now visit all the blocks dominated by BB. */ 2306169689Skan for (son = first_dom_son (CDI_DOMINATORS, bb); 2307169689Skan son; 2308169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 2309169689Skan prepare_block_for_update (son, insert_phi_p); 2310169689Skan} 2311169689Skan 2312169689Skan 2313169689Skan/* Helper for prepare_names_to_update. Mark all the use sites for 2314169689Skan NAME as interesting. BLOCKS and INSERT_PHI_P are as in 2315169689Skan prepare_names_to_update. */ 2316169689Skan 2317169689Skanstatic void 2318169689Skanprepare_use_sites_for (tree name, bool insert_phi_p) 2319169689Skan{ 2320169689Skan use_operand_p use_p; 2321169689Skan imm_use_iterator iter; 2322169689Skan 2323169689Skan FOR_EACH_IMM_USE_FAST (use_p, iter, name) 2324169689Skan { 2325169689Skan tree stmt = USE_STMT (use_p); 2326169689Skan basic_block bb = bb_for_stmt (stmt); 2327169689Skan 2328169689Skan if (TREE_CODE (stmt) == PHI_NODE) 2329169689Skan { 2330169689Skan int ix = PHI_ARG_INDEX_FROM_USE (use_p); 2331169689Skan edge e = PHI_ARG_EDGE (stmt, ix); 2332169689Skan mark_use_interesting (name, stmt, e->src, insert_phi_p); 2333169689Skan } 2334169689Skan else 2335169689Skan { 2336169689Skan /* For regular statements, mark this as an interesting use 2337169689Skan for NAME. */ 2338169689Skan mark_use_interesting (name, stmt, bb, insert_phi_p); 2339169689Skan } 2340169689Skan } 2341169689Skan} 2342169689Skan 2343169689Skan 2344169689Skan/* Helper for prepare_names_to_update. Mark the definition site for 2345169689Skan NAME as interesting. BLOCKS and INSERT_PHI_P are as in 2346169689Skan prepare_names_to_update. */ 2347169689Skan 2348169689Skanstatic void 2349169689Skanprepare_def_site_for (tree name, bool insert_phi_p) 2350169689Skan{ 2351169689Skan tree stmt; 2352169689Skan basic_block bb; 2353169689Skan 2354169689Skan gcc_assert (names_to_release == NULL 2355169689Skan || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name))); 2356169689Skan 2357169689Skan stmt = SSA_NAME_DEF_STMT (name); 2358169689Skan bb = bb_for_stmt (stmt); 2359169689Skan if (bb) 2360169689Skan { 2361169689Skan gcc_assert (bb->index < last_basic_block); 2362169689Skan mark_block_for_update (bb); 2363169689Skan mark_def_interesting (name, stmt, bb, insert_phi_p); 2364169689Skan } 2365169689Skan} 2366169689Skan 2367169689Skan 2368169689Skan/* Mark definition and use sites of names in NEW_SSA_NAMES and 2369169689Skan OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert 2370169689Skan PHI nodes for newly created names. */ 2371169689Skan 2372169689Skanstatic void 2373169689Skanprepare_names_to_update (bool insert_phi_p) 2374169689Skan{ 2375169689Skan unsigned i = 0; 2376169689Skan bitmap_iterator bi; 2377169689Skan sbitmap_iterator sbi; 2378169689Skan 2379169689Skan /* If a name N from NEW_SSA_NAMES is also marked to be released, 2380169689Skan remove it from NEW_SSA_NAMES so that we don't try to visit its 2381169689Skan defining basic block (which most likely doesn't exist). Notice 2382169689Skan that we cannot do the same with names in OLD_SSA_NAMES because we 2383169689Skan want to replace existing instances. */ 2384169689Skan if (names_to_release) 2385169689Skan EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2386169689Skan RESET_BIT (new_ssa_names, i); 2387169689Skan 2388169689Skan /* First process names in NEW_SSA_NAMES. Otherwise, uses of old 2389169689Skan names may be considered to be live-in on blocks that contain 2390169689Skan definitions for their replacements. */ 2391169689Skan EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi) 2392169689Skan prepare_def_site_for (ssa_name (i), insert_phi_p); 2393169689Skan 2394169689Skan /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from 2395169689Skan OLD_SSA_NAMES, but we have to ignore its definition site. */ 2396169689Skan EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2397169689Skan { 2398169689Skan if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i)) 2399169689Skan prepare_def_site_for (ssa_name (i), insert_phi_p); 2400169689Skan prepare_use_sites_for (ssa_name (i), insert_phi_p); 2401169689Skan } 2402169689Skan} 2403169689Skan 2404169689Skan 2405169689Skan/* Dump all the names replaced by NAME to FILE. */ 2406169689Skan 2407169689Skanvoid 2408169689Skandump_names_replaced_by (FILE *file, tree name) 2409169689Skan{ 2410169689Skan unsigned i; 2411169689Skan bitmap old_set; 2412169689Skan bitmap_iterator bi; 2413169689Skan 2414169689Skan print_generic_expr (file, name, 0); 2415169689Skan fprintf (file, " -> { "); 2416169689Skan 2417169689Skan old_set = names_replaced_by (name); 2418169689Skan EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi) 2419169689Skan { 2420169689Skan print_generic_expr (file, ssa_name (i), 0); 2421169689Skan fprintf (file, " "); 2422169689Skan } 2423169689Skan 2424169689Skan fprintf (file, "}\n"); 2425169689Skan} 2426169689Skan 2427169689Skan 2428169689Skan/* Dump all the names replaced by NAME to stderr. */ 2429169689Skan 2430169689Skanvoid 2431169689Skandebug_names_replaced_by (tree name) 2432169689Skan{ 2433169689Skan dump_names_replaced_by (stderr, name); 2434169689Skan} 2435169689Skan 2436169689Skan 2437169689Skan/* Dump SSA update information to FILE. */ 2438169689Skan 2439169689Skanvoid 2440169689Skandump_update_ssa (FILE *file) 2441169689Skan{ 2442169689Skan unsigned i = 0; 2443169689Skan bitmap_iterator bi; 2444169689Skan 2445169689Skan if (!need_ssa_update_p ()) 2446169689Skan return; 2447169689Skan 2448169689Skan if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0) 2449169689Skan { 2450169689Skan sbitmap_iterator sbi; 2451169689Skan 2452169689Skan fprintf (file, "\nSSA replacement table\n"); 2453169689Skan fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces " 2454169689Skan "O_1, ..., O_j\n\n"); 2455169689Skan 2456169689Skan EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi) 2457169689Skan dump_names_replaced_by (file, ssa_name (i)); 2458169689Skan 2459169689Skan fprintf (file, "\n"); 2460169689Skan fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n", 2461169689Skan update_ssa_stats.num_virtual_mappings); 2462169689Skan fprintf (file, "Number of real NEW -> OLD mappings: %7u\n", 2463169689Skan update_ssa_stats.num_total_mappings 2464169689Skan - update_ssa_stats.num_virtual_mappings); 2465169689Skan fprintf (file, "Number of total NEW -> OLD mappings: %7u\n", 2466169689Skan update_ssa_stats.num_total_mappings); 2467169689Skan 2468169689Skan fprintf (file, "\nNumber of virtual symbols: %u\n", 2469169689Skan update_ssa_stats.num_virtual_symbols); 2470169689Skan } 2471169689Skan 2472169689Skan if (syms_to_rename && !bitmap_empty_p (syms_to_rename)) 2473169689Skan { 2474169689Skan fprintf (file, "\n\nSymbols to be put in SSA form\n\n"); 2475169689Skan EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi) 2476169689Skan { 2477169689Skan print_generic_expr (file, referenced_var (i), 0); 2478169689Skan fprintf (file, " "); 2479169689Skan } 2480169689Skan } 2481169689Skan 2482169689Skan if (names_to_release && !bitmap_empty_p (names_to_release)) 2483169689Skan { 2484169689Skan fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n"); 2485169689Skan EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2486169689Skan { 2487169689Skan print_generic_expr (file, ssa_name (i), 0); 2488169689Skan fprintf (file, " "); 2489169689Skan } 2490169689Skan } 2491169689Skan 2492169689Skan fprintf (file, "\n\n"); 2493169689Skan} 2494169689Skan 2495169689Skan 2496169689Skan/* Dump SSA update information to stderr. */ 2497169689Skan 2498169689Skanvoid 2499169689Skandebug_update_ssa (void) 2500169689Skan{ 2501169689Skan dump_update_ssa (stderr); 2502169689Skan} 2503169689Skan 2504169689Skan 2505169689Skan/* Initialize data structures used for incremental SSA updates. */ 2506169689Skan 2507169689Skanstatic void 2508169689Skaninit_update_ssa (void) 2509169689Skan{ 2510169689Skan /* Reserve more space than the current number of names. The calls to 2511169689Skan add_new_name_mapping are typically done after creating new SSA 2512169689Skan names, so we'll need to reallocate these arrays. */ 2513169689Skan old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR); 2514169689Skan sbitmap_zero (old_ssa_names); 2515169689Skan 2516169689Skan new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR); 2517169689Skan sbitmap_zero (new_ssa_names); 2518169689Skan 2519169689Skan repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free); 2520169689Skan need_to_initialize_update_ssa_p = false; 2521169689Skan need_to_update_vops_p = false; 2522169689Skan syms_to_rename = BITMAP_ALLOC (NULL); 2523169689Skan names_to_release = NULL; 2524169689Skan memset (&update_ssa_stats, 0, sizeof (update_ssa_stats)); 2525169689Skan update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL); 2526169689Skan} 2527169689Skan 2528169689Skan 2529169689Skan/* Deallocate data structures used for incremental SSA updates. */ 2530169689Skan 2531169689Skanvoid 2532169689Skandelete_update_ssa (void) 2533169689Skan{ 2534169689Skan unsigned i; 2535169689Skan bitmap_iterator bi; 2536169689Skan 2537169689Skan sbitmap_free (old_ssa_names); 2538169689Skan old_ssa_names = NULL; 2539169689Skan 2540169689Skan sbitmap_free (new_ssa_names); 2541169689Skan new_ssa_names = NULL; 2542169689Skan 2543169689Skan htab_delete (repl_tbl); 2544169689Skan repl_tbl = NULL; 2545169689Skan 2546169689Skan need_to_initialize_update_ssa_p = true; 2547169689Skan need_to_update_vops_p = false; 2548169689Skan BITMAP_FREE (syms_to_rename); 2549169689Skan BITMAP_FREE (update_ssa_stats.virtual_symbols); 2550169689Skan 2551169689Skan if (names_to_release) 2552169689Skan { 2553169689Skan EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2554169689Skan release_ssa_name (ssa_name (i)); 2555169689Skan BITMAP_FREE (names_to_release); 2556169689Skan } 2557169689Skan 2558169689Skan clear_ssa_name_info (); 2559169689Skan} 2560169689Skan 2561169689Skan 2562169689Skan/* Create a new name for OLD_NAME in statement STMT and replace the 2563169689Skan operand pointed to by DEF_P with the newly created name. Return 2564169689Skan the new name and register the replacement mapping <NEW, OLD> in 2565169689Skan update_ssa's tables. */ 2566169689Skan 2567169689Skantree 2568169689Skancreate_new_def_for (tree old_name, tree stmt, def_operand_p def) 2569169689Skan{ 2570169689Skan tree new_name = duplicate_ssa_name (old_name, stmt); 2571169689Skan 2572169689Skan SET_DEF (def, new_name); 2573169689Skan 2574169689Skan if (TREE_CODE (stmt) == PHI_NODE) 2575169689Skan { 2576169689Skan edge e; 2577169689Skan edge_iterator ei; 2578169689Skan basic_block bb = bb_for_stmt (stmt); 2579169689Skan 2580169689Skan /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */ 2581169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2582169689Skan if (e->flags & EDGE_ABNORMAL) 2583169689Skan { 2584169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1; 2585169689Skan break; 2586169689Skan } 2587169689Skan } 2588169689Skan 2589169689Skan register_new_name_mapping (new_name, old_name); 2590169689Skan 2591169689Skan /* For the benefit of passes that will be updating the SSA form on 2592169689Skan their own, set the current reaching definition of OLD_NAME to be 2593169689Skan NEW_NAME. */ 2594169689Skan set_current_def (old_name, new_name); 2595169689Skan 2596169689Skan return new_name; 2597169689Skan} 2598169689Skan 2599169689Skan 2600169689Skan/* Register name NEW to be a replacement for name OLD. This function 2601169689Skan must be called for every replacement that should be performed by 2602169689Skan update_ssa. */ 2603169689Skan 2604169689Skanvoid 2605169689Skanregister_new_name_mapping (tree new, tree old) 2606169689Skan{ 2607169689Skan if (need_to_initialize_update_ssa_p) 2608169689Skan init_update_ssa (); 2609169689Skan 2610169689Skan add_new_name_mapping (new, old); 2611169689Skan} 2612169689Skan 2613169689Skan 2614169689Skan/* Register symbol SYM to be renamed by update_ssa. */ 2615169689Skan 2616169689Skanvoid 2617169689Skanmark_sym_for_renaming (tree sym) 2618169689Skan{ 2619169689Skan if (need_to_initialize_update_ssa_p) 2620169689Skan init_update_ssa (); 2621169689Skan 2622169689Skan bitmap_set_bit (syms_to_rename, DECL_UID (sym)); 2623169689Skan 2624169689Skan if (!is_gimple_reg (sym)) 2625169689Skan need_to_update_vops_p = true; 2626169689Skan} 2627169689Skan 2628169689Skan 2629169689Skan/* Register all the symbols in SET to be renamed by update_ssa. */ 2630169689Skan 2631169689Skanvoid 2632169689Skanmark_set_for_renaming (bitmap set) 2633169689Skan{ 2634169689Skan bitmap_iterator bi; 2635169689Skan unsigned i; 2636169689Skan 2637169689Skan if (bitmap_empty_p (set)) 2638169689Skan return; 2639169689Skan 2640169689Skan if (need_to_initialize_update_ssa_p) 2641169689Skan init_update_ssa (); 2642169689Skan 2643169689Skan bitmap_ior_into (syms_to_rename, set); 2644169689Skan 2645169689Skan EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 2646169689Skan if (!is_gimple_reg (referenced_var (i))) 2647169689Skan { 2648169689Skan need_to_update_vops_p = true; 2649169689Skan break; 2650169689Skan } 2651169689Skan} 2652169689Skan 2653169689Skan 2654169689Skan/* Return true if there is any work to be done by update_ssa. */ 2655169689Skan 2656169689Skanbool 2657169689Skanneed_ssa_update_p (void) 2658169689Skan{ 2659169689Skan return syms_to_rename || old_ssa_names || new_ssa_names; 2660169689Skan} 2661169689Skan 2662169689Skan 2663169689Skan/* Return true if name N has been registered in the replacement table. */ 2664169689Skan 2665169689Skanbool 2666169689Skanname_registered_for_update_p (tree n) 2667169689Skan{ 2668169689Skan if (!need_ssa_update_p ()) 2669169689Skan return false; 2670169689Skan 2671169689Skan return is_new_name (n) 2672169689Skan || is_old_name (n) 2673169689Skan || symbol_marked_for_renaming (SSA_NAME_VAR (n)); 2674169689Skan} 2675169689Skan 2676169689Skan 2677169689Skan/* Return the set of all the SSA names marked to be replaced. */ 2678169689Skan 2679169689Skanbitmap 2680169689Skanssa_names_to_replace (void) 2681169689Skan{ 2682169689Skan unsigned i = 0; 2683169689Skan bitmap ret; 2684169689Skan sbitmap_iterator sbi; 2685169689Skan 2686169689Skan ret = BITMAP_ALLOC (NULL); 2687169689Skan EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2688169689Skan bitmap_set_bit (ret, i); 2689169689Skan 2690169689Skan return ret; 2691169689Skan} 2692169689Skan 2693169689Skan 2694169689Skan/* Mark NAME to be released after update_ssa has finished. */ 2695169689Skan 2696169689Skanvoid 2697169689Skanrelease_ssa_name_after_update_ssa (tree name) 2698169689Skan{ 2699169689Skan gcc_assert (!need_to_initialize_update_ssa_p); 2700169689Skan 2701169689Skan if (names_to_release == NULL) 2702169689Skan names_to_release = BITMAP_ALLOC (NULL); 2703169689Skan 2704169689Skan bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name)); 2705169689Skan} 2706169689Skan 2707169689Skan 2708169689Skan/* Insert new PHI nodes to replace VAR. DFS contains dominance 2709169689Skan frontier information. BLOCKS is the set of blocks to be updated. 2710169689Skan 2711169689Skan This is slightly different than the regular PHI insertion 2712169689Skan algorithm. The value of UPDATE_FLAGS controls how PHI nodes for 2713169689Skan real names (i.e., GIMPLE registers) are inserted: 2714169689Skan 2715169689Skan - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI 2716169689Skan nodes inside the region affected by the block that defines VAR 2717169689Skan and the blocks that define all its replacements. All these 2718169689Skan definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS. 2719169689Skan 2720169689Skan First, we compute the entry point to the region (ENTRY). This is 2721169689Skan given by the nearest common dominator to all the definition 2722169689Skan blocks. When computing the iterated dominance frontier (IDF), any 2723169689Skan block not strictly dominated by ENTRY is ignored. 2724169689Skan 2725169689Skan We then call the standard PHI insertion algorithm with the pruned 2726169689Skan IDF. 2727169689Skan 2728169689Skan - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real 2729169689Skan names is not pruned. PHI nodes are inserted at every IDF block. */ 2730169689Skan 2731169689Skanstatic void 2732169689Skaninsert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks, 2733169689Skan unsigned update_flags) 2734169689Skan{ 2735169689Skan basic_block entry; 2736169689Skan struct def_blocks_d *db; 2737169689Skan bitmap idf, pruned_idf; 2738169689Skan bitmap_iterator bi; 2739169689Skan unsigned i; 2740169689Skan 2741169689Skan#if defined ENABLE_CHECKING 2742169689Skan if (TREE_CODE (var) == SSA_NAME) 2743169689Skan gcc_assert (is_old_name (var)); 2744169689Skan else 2745169689Skan gcc_assert (symbol_marked_for_renaming (var)); 2746169689Skan#endif 2747169689Skan 2748169689Skan /* Get all the definition sites for VAR. */ 2749169689Skan db = find_def_blocks_for (var); 2750169689Skan 2751169689Skan /* No need to do anything if there were no definitions to VAR. */ 2752169689Skan if (db == NULL || bitmap_empty_p (db->def_blocks)) 2753169689Skan return; 2754169689Skan 2755169689Skan /* Compute the initial iterated dominance frontier. */ 2756169689Skan idf = find_idf (db->def_blocks, dfs); 2757169689Skan pruned_idf = BITMAP_ALLOC (NULL); 2758169689Skan 2759169689Skan if (TREE_CODE (var) == SSA_NAME) 2760169689Skan { 2761169689Skan if (update_flags == TODO_update_ssa) 2762169689Skan { 2763169689Skan /* If doing regular SSA updates for GIMPLE registers, we are 2764169689Skan only interested in IDF blocks dominated by the nearest 2765169689Skan common dominator of all the definition blocks. */ 2766169689Skan entry = nearest_common_dominator_for_set (CDI_DOMINATORS, 2767169689Skan db->def_blocks); 2768169689Skan 2769169689Skan if (entry != ENTRY_BLOCK_PTR) 2770169689Skan EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi) 2771169689Skan if (BASIC_BLOCK (i) != entry 2772169689Skan && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry)) 2773169689Skan bitmap_set_bit (pruned_idf, i); 2774169689Skan } 2775169689Skan else 2776169689Skan { 2777169689Skan /* Otherwise, do not prune the IDF for VAR. */ 2778169689Skan gcc_assert (update_flags == TODO_update_ssa_full_phi); 2779169689Skan bitmap_copy (pruned_idf, idf); 2780169689Skan } 2781169689Skan } 2782169689Skan else 2783169689Skan { 2784169689Skan /* Otherwise, VAR is a symbol that needs to be put into SSA form 2785169689Skan for the first time, so we need to compute the full IDF for 2786169689Skan it. */ 2787169689Skan bitmap_copy (pruned_idf, idf); 2788169689Skan } 2789169689Skan 2790169689Skan if (!bitmap_empty_p (pruned_idf)) 2791169689Skan { 2792169689Skan /* Make sure that PRUNED_IDF blocks and all their feeding blocks 2793169689Skan are included in the region to be updated. The feeding blocks 2794169689Skan are important to guarantee that the PHI arguments are renamed 2795169689Skan properly. */ 2796169689Skan bitmap_ior_into (blocks, pruned_idf); 2797169689Skan EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi) 2798169689Skan { 2799169689Skan edge e; 2800169689Skan edge_iterator ei; 2801169689Skan basic_block bb = BASIC_BLOCK (i); 2802169689Skan 2803169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2804169689Skan if (e->src->index >= 0) 2805169689Skan bitmap_set_bit (blocks, e->src->index); 2806169689Skan } 2807169689Skan 2808169689Skan insert_phi_nodes_for (var, pruned_idf, true); 2809169689Skan } 2810169689Skan 2811169689Skan BITMAP_FREE (pruned_idf); 2812169689Skan BITMAP_FREE (idf); 2813169689Skan} 2814169689Skan 2815169689Skan 2816169689Skan/* Heuristic to determine whether SSA name mappings for virtual names 2817169689Skan should be discarded and their symbols rewritten from scratch. When 2818169689Skan there is a large number of mappings for virtual names, the 2819169689Skan insertion of PHI nodes for the old names in the mappings takes 2820169689Skan considerable more time than if we inserted PHI nodes for the 2821169689Skan symbols instead. 2822169689Skan 2823169689Skan Currently the heuristic takes these stats into account: 2824169689Skan 2825169689Skan - Number of mappings for virtual SSA names. 2826169689Skan - Number of distinct virtual symbols involved in those mappings. 2827169689Skan 2828169689Skan If the number of virtual mappings is much larger than the number of 2829169689Skan virtual symbols, then it will be faster to compute PHI insertion 2830169689Skan spots for the symbols. Even if this involves traversing the whole 2831169689Skan CFG, which is what happens when symbols are renamed from scratch. */ 2832169689Skan 2833169689Skanstatic bool 2834169689Skanswitch_virtuals_to_full_rewrite_p (void) 2835169689Skan{ 2836169689Skan if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS) 2837169689Skan return false; 2838169689Skan 2839169689Skan if (update_ssa_stats.num_virtual_mappings 2840169689Skan > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO 2841169689Skan * update_ssa_stats.num_virtual_symbols) 2842169689Skan return true; 2843169689Skan 2844169689Skan return false; 2845169689Skan} 2846169689Skan 2847169689Skan 2848169689Skan/* Remove every virtual mapping and mark all the affected virtual 2849169689Skan symbols for renaming. */ 2850169689Skan 2851169689Skanstatic void 2852169689Skanswitch_virtuals_to_full_rewrite (void) 2853169689Skan{ 2854169689Skan unsigned i = 0; 2855169689Skan sbitmap_iterator sbi; 2856169689Skan 2857169689Skan if (dump_file) 2858169689Skan { 2859169689Skan fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n"); 2860169689Skan fprintf (dump_file, "\tNumber of virtual mappings: %7u\n", 2861169689Skan update_ssa_stats.num_virtual_mappings); 2862169689Skan fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n", 2863169689Skan update_ssa_stats.num_virtual_symbols); 2864169689Skan fprintf (dump_file, "Updating FUD-chains from top of CFG will be " 2865169689Skan "faster than processing\nthe name mappings.\n\n"); 2866169689Skan } 2867169689Skan 2868169689Skan /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES. 2869169689Skan Note that it is not really necessary to remove the mappings from 2870169689Skan REPL_TBL, that would only waste time. */ 2871169689Skan EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi) 2872169689Skan if (!is_gimple_reg (ssa_name (i))) 2873169689Skan RESET_BIT (new_ssa_names, i); 2874169689Skan 2875169689Skan EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2876169689Skan if (!is_gimple_reg (ssa_name (i))) 2877169689Skan RESET_BIT (old_ssa_names, i); 2878169689Skan 2879169689Skan bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols); 2880169689Skan} 2881169689Skan 2882169689Skan 2883169689Skan/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of 2884169689Skan existing SSA names (OLD_SSA_NAMES), update the SSA form so that: 2885169689Skan 2886169689Skan 1- The names in OLD_SSA_NAMES dominated by the definitions of 2887169689Skan NEW_SSA_NAMES are all re-written to be reached by the 2888169689Skan appropriate definition from NEW_SSA_NAMES. 2889169689Skan 2890169689Skan 2- If needed, new PHI nodes are added to the iterated dominance 2891169689Skan frontier of the blocks where each of NEW_SSA_NAMES are defined. 2892169689Skan 2893169689Skan The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by 2894169689Skan calling register_new_name_mapping for every pair of names that the 2895169689Skan caller wants to replace. 2896169689Skan 2897169689Skan The caller identifies the new names that have been inserted and the 2898169689Skan names that need to be replaced by calling register_new_name_mapping 2899169689Skan for every pair <NEW, OLD>. Note that the function assumes that the 2900169689Skan new names have already been inserted in the IL. 2901169689Skan 2902169689Skan For instance, given the following code: 2903169689Skan 2904169689Skan 1 L0: 2905169689Skan 2 x_1 = PHI (0, x_5) 2906169689Skan 3 if (x_1 < 10) 2907169689Skan 4 if (x_1 > 7) 2908169689Skan 5 y_2 = 0 2909169689Skan 6 else 2910169689Skan 7 y_3 = x_1 + x_7 2911169689Skan 8 endif 2912169689Skan 9 x_5 = x_1 + 1 2913169689Skan 10 goto L0; 2914169689Skan 11 endif 2915169689Skan 2916169689Skan Suppose that we insert new names x_10 and x_11 (lines 4 and 8). 2917169689Skan 2918169689Skan 1 L0: 2919169689Skan 2 x_1 = PHI (0, x_5) 2920169689Skan 3 if (x_1 < 10) 2921169689Skan 4 x_10 = ... 2922169689Skan 5 if (x_1 > 7) 2923169689Skan 6 y_2 = 0 2924169689Skan 7 else 2925169689Skan 8 x_11 = ... 2926169689Skan 9 y_3 = x_1 + x_7 2927169689Skan 10 endif 2928169689Skan 11 x_5 = x_1 + 1 2929169689Skan 12 goto L0; 2930169689Skan 13 endif 2931169689Skan 2932169689Skan We want to replace all the uses of x_1 with the new definitions of 2933169689Skan x_10 and x_11. Note that the only uses that should be replaced are 2934169689Skan those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should 2935169689Skan *not* be replaced (this is why we cannot just mark symbol 'x' for 2936169689Skan renaming). 2937169689Skan 2938169689Skan Additionally, we may need to insert a PHI node at line 11 because 2939169689Skan that is a merge point for x_10 and x_11. So the use of x_1 at line 2940169689Skan 11 will be replaced with the new PHI node. The insertion of PHI 2941169689Skan nodes is optional. They are not strictly necessary to preserve the 2942169689Skan SSA form, and depending on what the caller inserted, they may not 2943169689Skan even be useful for the optimizers. UPDATE_FLAGS controls various 2944169689Skan aspects of how update_ssa operates, see the documentation for 2945169689Skan TODO_update_ssa*. */ 2946169689Skan 2947169689Skanvoid 2948169689Skanupdate_ssa (unsigned update_flags) 2949169689Skan{ 2950169689Skan basic_block bb, start_bb; 2951169689Skan bitmap_iterator bi; 2952169689Skan unsigned i = 0; 2953169689Skan sbitmap tmp; 2954169689Skan bool insert_phi_p; 2955169689Skan sbitmap_iterator sbi; 2956169689Skan 2957169689Skan if (!need_ssa_update_p ()) 2958169689Skan return; 2959169689Skan 2960169689Skan timevar_push (TV_TREE_SSA_INCREMENTAL); 2961169689Skan 2962169689Skan blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL); 2963169689Skan if (!phis_to_rewrite) 2964169689Skan phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block); 2965169689Skan blocks_to_update = BITMAP_ALLOC (NULL); 2966169689Skan 2967169689Skan /* Ensure that the dominance information is up-to-date. */ 2968169689Skan calculate_dominance_info (CDI_DOMINATORS); 2969169689Skan 2970169689Skan /* Only one update flag should be set. */ 2971169689Skan gcc_assert (update_flags == TODO_update_ssa 2972169689Skan || update_flags == TODO_update_ssa_no_phi 2973169689Skan || update_flags == TODO_update_ssa_full_phi 2974169689Skan || update_flags == TODO_update_ssa_only_virtuals); 2975169689Skan 2976169689Skan /* If we only need to update virtuals, remove all the mappings for 2977169689Skan real names before proceeding. The caller is responsible for 2978169689Skan having dealt with the name mappings before calling update_ssa. */ 2979169689Skan if (update_flags == TODO_update_ssa_only_virtuals) 2980169689Skan { 2981169689Skan sbitmap_zero (old_ssa_names); 2982169689Skan sbitmap_zero (new_ssa_names); 2983169689Skan htab_empty (repl_tbl); 2984169689Skan } 2985169689Skan 2986169689Skan insert_phi_p = (update_flags != TODO_update_ssa_no_phi); 2987169689Skan 2988169689Skan if (insert_phi_p) 2989169689Skan { 2990169689Skan /* If the caller requested PHI nodes to be added, initialize 2991169689Skan live-in information data structures (DEF_BLOCKS). */ 2992169689Skan 2993169689Skan /* For each SSA name N, the DEF_BLOCKS table describes where the 2994169689Skan name is defined, which blocks have PHI nodes for N, and which 2995169689Skan blocks have uses of N (i.e., N is live-on-entry in those 2996169689Skan blocks). */ 2997169689Skan def_blocks = htab_create (num_ssa_names, def_blocks_hash, 2998169689Skan def_blocks_eq, def_blocks_free); 2999169689Skan } 3000169689Skan else 3001169689Skan { 3002169689Skan def_blocks = NULL; 3003169689Skan } 3004169689Skan 3005169689Skan /* Heuristic to avoid massive slow downs when the replacement 3006169689Skan mappings include lots of virtual names. */ 3007169689Skan if (insert_phi_p && switch_virtuals_to_full_rewrite_p ()) 3008169689Skan switch_virtuals_to_full_rewrite (); 3009169689Skan 3010169689Skan /* If there are names defined in the replacement table, prepare 3011169689Skan definition and use sites for all the names in NEW_SSA_NAMES and 3012169689Skan OLD_SSA_NAMES. */ 3013169689Skan if (sbitmap_first_set_bit (new_ssa_names) >= 0) 3014169689Skan { 3015169689Skan prepare_names_to_update (insert_phi_p); 3016169689Skan 3017169689Skan /* If all the names in NEW_SSA_NAMES had been marked for 3018169689Skan removal, and there are no symbols to rename, then there's 3019169689Skan nothing else to do. */ 3020169689Skan if (sbitmap_first_set_bit (new_ssa_names) < 0 3021169689Skan && bitmap_empty_p (syms_to_rename)) 3022169689Skan goto done; 3023169689Skan } 3024169689Skan 3025169689Skan /* Next, determine the block at which to start the renaming process. */ 3026169689Skan if (!bitmap_empty_p (syms_to_rename)) 3027169689Skan { 3028169689Skan /* If we have to rename some symbols from scratch, we need to 3029169689Skan start the process at the root of the CFG. FIXME, it should 3030169689Skan be possible to determine the nearest block that had a 3031169689Skan definition for each of the symbols that are marked for 3032169689Skan updating. For now this seems more work than it's worth. */ 3033169689Skan start_bb = ENTRY_BLOCK_PTR; 3034169689Skan 3035169689Skan /* Traverse the CFG looking for definitions and uses of symbols 3036169689Skan in SYMS_TO_RENAME. Mark interesting blocks and statements 3037169689Skan and set local live-in information for the PHI placement 3038169689Skan heuristics. */ 3039169689Skan prepare_block_for_update (start_bb, insert_phi_p); 3040169689Skan } 3041169689Skan else 3042169689Skan { 3043169689Skan /* Otherwise, the entry block to the region is the nearest 3044169689Skan common dominator for the blocks in BLOCKS. */ 3045169689Skan start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, 3046169689Skan blocks_to_update); 3047169689Skan } 3048169689Skan 3049169689Skan /* If requested, insert PHI nodes at the iterated dominance frontier 3050169689Skan of every block, creating new definitions for names in OLD_SSA_NAMES 3051169689Skan and for symbols in SYMS_TO_RENAME. */ 3052169689Skan if (insert_phi_p) 3053169689Skan { 3054169689Skan bitmap *dfs; 3055169689Skan 3056169689Skan /* If the caller requested PHI nodes to be added, compute 3057169689Skan dominance frontiers. */ 3058169689Skan dfs = XNEWVEC (bitmap, last_basic_block); 3059169689Skan FOR_EACH_BB (bb) 3060169689Skan dfs[bb->index] = BITMAP_ALLOC (NULL); 3061169689Skan compute_dominance_frontiers (dfs); 3062169689Skan 3063169689Skan if (sbitmap_first_set_bit (old_ssa_names) >= 0) 3064169689Skan { 3065169689Skan sbitmap_iterator sbi; 3066169689Skan 3067169689Skan /* insert_update_phi_nodes_for will call add_new_name_mapping 3068169689Skan when inserting new PHI nodes, so the set OLD_SSA_NAMES 3069169689Skan will grow while we are traversing it (but it will not 3070169689Skan gain any new members). Copy OLD_SSA_NAMES to a temporary 3071169689Skan for traversal. */ 3072169689Skan sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits); 3073169689Skan sbitmap_copy (tmp, old_ssa_names); 3074169689Skan EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi) 3075169689Skan insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update, 3076169689Skan update_flags); 3077169689Skan sbitmap_free (tmp); 3078169689Skan } 3079169689Skan 3080169689Skan EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi) 3081169689Skan insert_updated_phi_nodes_for (referenced_var (i), dfs, 3082169689Skan blocks_to_update, update_flags); 3083169689Skan 3084169689Skan FOR_EACH_BB (bb) 3085169689Skan BITMAP_FREE (dfs[bb->index]); 3086169689Skan free (dfs); 3087169689Skan 3088169689Skan /* Insertion of PHI nodes may have added blocks to the region. 3089169689Skan We need to re-compute START_BB to include the newly added 3090169689Skan blocks. */ 3091169689Skan if (start_bb != ENTRY_BLOCK_PTR) 3092169689Skan start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, 3093169689Skan blocks_to_update); 3094169689Skan } 3095169689Skan 3096169689Skan /* Reset the current definition for name and symbol before renaming 3097169689Skan the sub-graph. */ 3098169689Skan EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 3099169689Skan set_current_def (ssa_name (i), NULL_TREE); 3100169689Skan 3101169689Skan EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi) 3102169689Skan set_current_def (referenced_var (i), NULL_TREE); 3103169689Skan 3104169689Skan /* Now start the renaming process at START_BB. */ 3105169689Skan tmp = sbitmap_alloc (last_basic_block); 3106169689Skan sbitmap_zero (tmp); 3107169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) 3108169689Skan SET_BIT (tmp, i); 3109169689Skan 3110169689Skan rewrite_blocks (start_bb, REWRITE_UPDATE, tmp); 3111169689Skan 3112169689Skan sbitmap_free (tmp); 3113169689Skan 3114169689Skan /* Debugging dumps. */ 3115169689Skan if (dump_file) 3116169689Skan { 3117169689Skan int c; 3118169689Skan unsigned i; 3119169689Skan 3120169689Skan dump_update_ssa (dump_file); 3121169689Skan 3122169689Skan fprintf (dump_file, "Incremental SSA update started at block: %d\n\n", 3123169689Skan start_bb->index); 3124169689Skan 3125169689Skan c = 0; 3126169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) 3127169689Skan c++; 3128169689Skan fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block); 3129169689Skan fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n", 3130169689Skan c, PERCENT (c, last_basic_block)); 3131169689Skan 3132169689Skan if (dump_flags & TDF_DETAILS) 3133169689Skan { 3134169689Skan fprintf (dump_file, "Affected blocks: "); 3135169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) 3136169689Skan fprintf (dump_file, "%u ", i); 3137169689Skan fprintf (dump_file, "\n"); 3138169689Skan } 3139169689Skan 3140169689Skan fprintf (dump_file, "\n\n"); 3141169689Skan } 3142169689Skan 3143169689Skan /* Free allocated memory. */ 3144169689Skandone: 3145169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi) 3146169689Skan { 3147169689Skan tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i); 3148169689Skan 3149169689Skan VEC_free (tree, heap, phis); 3150169689Skan VEC_replace (tree_vec, phis_to_rewrite, i, NULL); 3151169689Skan } 3152169689Skan BITMAP_FREE (blocks_with_phis_to_rewrite); 3153169689Skan BITMAP_FREE (blocks_to_update); 3154169689Skan delete_update_ssa (); 3155169689Skan 3156169689Skan timevar_pop (TV_TREE_SSA_INCREMENTAL); 3157169689Skan} 3158