1/* Rewrite a program in Normal form into SSA. 2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "tree.h" 27#include "flags.h" 28#include "rtl.h" 29#include "tm_p.h" 30#include "langhooks.h" 31#include "hard-reg-set.h" 32#include "basic-block.h" 33#include "output.h" 34#include "expr.h" 35#include "function.h" 36#include "diagnostic.h" 37#include "bitmap.h" 38#include "tree-flow.h" 39#include "tree-gimple.h" 40#include "tree-inline.h" 41#include "varray.h" 42#include "timevar.h" 43#include "hashtab.h" 44#include "tree-dump.h" 45#include "tree-pass.h" 46#include "cfgloop.h" 47#include "domwalk.h" 48#include "ggc.h" 49#include "params.h" 50 51/* This file builds the SSA form for a function as described in: 52 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently 53 Computing Static Single Assignment Form and the Control Dependence 54 Graph. ACM Transactions on Programming Languages and Systems, 55 13(4):451-490, October 1991. */ 56 57/* True if the code is in ssa form. */ 58bool in_ssa_p; 59 60/* Structure to map a variable VAR to the set of blocks that contain 61 definitions for VAR. */ 62struct def_blocks_d 63{ 64 /* The variable. */ 65 tree var; 66 67 /* Blocks that contain definitions of VAR. Bit I will be set if the 68 Ith block contains a definition of VAR. */ 69 bitmap def_blocks; 70 71 /* Blocks that contain a PHI node for VAR. */ 72 bitmap phi_blocks; 73 74 /* Blocks where VAR is live-on-entry. Similar semantics as 75 DEF_BLOCKS. */ 76 bitmap livein_blocks; 77}; 78 79 80/* Each entry in DEF_BLOCKS contains an element of type STRUCT 81 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the 82 basic blocks where VAR is defined (assigned a new value). It also 83 contains a bitmap of all the blocks where VAR is live-on-entry 84 (i.e., there is a use of VAR in block B without a preceding 85 definition in B). The live-on-entry information is used when 86 computing PHI pruning heuristics. */ 87static htab_t def_blocks; 88 89/* Stack of trees used to restore the global currdefs to its original 90 state after completing rewriting of a block and its dominator 91 children. Its elements have the following properties: 92 93 - An SSA_NAME indicates that the current definition of the 94 underlying variable should be set to the given SSA_NAME. 95 96 - A _DECL node indicates that the underlying variable has no 97 current definition. 98 99 - A NULL node is used to mark the last node associated with the 100 current block. 101 102 - A NULL node at the top entry is used to mark the last node 103 associated with the current block. */ 104static VEC(tree,heap) *block_defs_stack; 105 106/* Basic block vectors used in this file ought to be allocated in the 107 heap. We use pointer vector, because ints can be easily passed by 108 value. */ 109DEF_VEC_I(int); 110DEF_VEC_ALLOC_I(int,heap); 111 112/* Set of existing SSA names being replaced by update_ssa. */ 113static sbitmap old_ssa_names; 114 115/* Set of new SSA names being added by update_ssa. Note that both 116 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of 117 the operations done on them are presence tests. */ 118static sbitmap new_ssa_names; 119 120/* Symbols whose SSA form needs to be updated or created for the first 121 time. */ 122static bitmap syms_to_rename; 123 124/* Set of SSA names that have been marked to be released after they 125 were registered in the replacement table. They will be finally 126 released after we finish updating the SSA web. */ 127static bitmap names_to_release; 128 129/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need 130 to grow as the callers to register_new_name_mapping will typically 131 create new names on the fly. FIXME. Currently set to 1/3 to avoid 132 frequent reallocations but still need to find a reasonable growth 133 strategy. */ 134#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3)) 135 136/* Tuple used to represent replacement mappings. */ 137struct repl_map_d 138{ 139 tree name; 140 bitmap set; 141}; 142 143/* NEW -> OLD_SET replacement table. If we are replacing several 144 existing SSA names O_1, O_2, ..., O_j with a new name N_i, 145 then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */ 146static htab_t repl_tbl; 147 148/* true if register_new_name_mapping needs to initialize the data 149 structures needed by update_ssa. */ 150static bool need_to_initialize_update_ssa_p = true; 151 152/* true if update_ssa needs to update virtual operands. */ 153static bool need_to_update_vops_p = false; 154 155/* Statistics kept by update_ssa to use in the virtual mapping 156 heuristic. If the number of virtual mappings is beyond certain 157 threshold, the updater will switch from using the mappings into 158 renaming the virtual symbols from scratch. In some cases, the 159 large number of name mappings for virtual names causes significant 160 slowdowns in the PHI insertion code. */ 161struct update_ssa_stats_d 162{ 163 unsigned num_virtual_mappings; 164 unsigned num_total_mappings; 165 bitmap virtual_symbols; 166 unsigned num_virtual_symbols; 167}; 168static struct update_ssa_stats_d update_ssa_stats; 169 170/* Global data to attach to the main dominator walk structure. */ 171struct mark_def_sites_global_data 172{ 173 /* This bitmap contains the variables which are set before they 174 are used in a basic block. */ 175 bitmap kills; 176 177 /* Bitmap of names to rename. */ 178 sbitmap names_to_rename; 179 180 /* Set of blocks that mark_def_sites deems interesting for the 181 renamer to process. */ 182 sbitmap interesting_blocks; 183}; 184 185 186/* Information stored for SSA names. */ 187struct ssa_name_info 188{ 189 /* This field indicates whether or not the variable may need PHI nodes. 190 See the enum's definition for more detailed information about the 191 states. */ 192 ENUM_BITFIELD (need_phi_state) need_phi_state : 2; 193 194 /* The actual definition of the ssa name. */ 195 tree current_def; 196}; 197 198 199/* The main entry point to the SSA renamer (rewrite_blocks) may be 200 called several times to do different, but related, tasks. 201 Initially, we need it to rename the whole program into SSA form. 202 At other times, we may need it to only rename into SSA newly 203 exposed symbols. Finally, we can also call it to incrementally fix 204 an already built SSA web. */ 205enum rewrite_mode { 206 /* Convert the whole function into SSA form. */ 207 REWRITE_ALL, 208 209 /* Incrementally update the SSA web by replacing existing SSA 210 names with new ones. See update_ssa for details. */ 211 REWRITE_UPDATE 212}; 213 214 215/* Use TREE_VISITED to keep track of which statements we want to 216 rename. When renaming a subset of the variables, not all 217 statements will be processed. This is decided in mark_def_sites. */ 218#define REWRITE_THIS_STMT(T) TREE_VISITED (T) 219 220/* Use the unsigned flag to keep track of which statements we want to 221 visit when marking new definition sites. This is slightly 222 different than REWRITE_THIS_STMT: it's used by update_ssa to 223 distinguish statements that need to have both uses and defs 224 processed from those that only need to have their defs processed. 225 Statements that define new SSA names only need to have their defs 226 registered, but they don't need to have their uses renamed. */ 227#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag 228 229 230/* Prototypes for debugging functions. */ 231extern void dump_tree_ssa (FILE *); 232extern void debug_tree_ssa (void); 233extern void debug_def_blocks (void); 234extern void dump_tree_ssa_stats (FILE *); 235extern void debug_tree_ssa_stats (void); 236void dump_update_ssa (FILE *); 237void debug_update_ssa (void); 238void dump_names_replaced_by (FILE *, tree); 239void debug_names_replaced_by (tree); 240 241/* Get the information associated with NAME. */ 242 243static inline struct ssa_name_info * 244get_ssa_name_ann (tree name) 245{ 246 if (!SSA_NAME_AUX (name)) 247 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info)); 248 249 return SSA_NAME_AUX (name); 250} 251 252 253/* Gets phi_state field for VAR. */ 254 255static inline enum need_phi_state 256get_phi_state (tree var) 257{ 258 if (TREE_CODE (var) == SSA_NAME) 259 return get_ssa_name_ann (var)->need_phi_state; 260 else 261 return var_ann (var)->need_phi_state; 262} 263 264 265/* Sets phi_state field for VAR to STATE. */ 266 267static inline void 268set_phi_state (tree var, enum need_phi_state state) 269{ 270 if (TREE_CODE (var) == SSA_NAME) 271 get_ssa_name_ann (var)->need_phi_state = state; 272 else 273 var_ann (var)->need_phi_state = state; 274} 275 276 277/* Return the current definition for VAR. */ 278 279tree 280get_current_def (tree var) 281{ 282 if (TREE_CODE (var) == SSA_NAME) 283 return get_ssa_name_ann (var)->current_def; 284 else 285 return var_ann (var)->current_def; 286} 287 288 289/* Sets current definition of VAR to DEF. */ 290 291void 292set_current_def (tree var, tree def) 293{ 294 if (TREE_CODE (var) == SSA_NAME) 295 get_ssa_name_ann (var)->current_def = def; 296 else 297 var_ann (var)->current_def = def; 298} 299 300 301/* Compute global livein information given the set of blockx where 302 an object is locally live at the start of the block (LIVEIN) 303 and the set of blocks where the object is defined (DEF_BLOCKS). 304 305 Note: This routine augments the existing local livein information 306 to include global livein (i.e., it modifies the underlying bitmap 307 for LIVEIN). */ 308 309void 310compute_global_livein (bitmap livein, bitmap def_blocks) 311{ 312 basic_block bb, *worklist, *tos; 313 unsigned i; 314 bitmap_iterator bi; 315 316 tos = worklist 317 = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1)); 318 319 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi) 320 { 321 *tos++ = BASIC_BLOCK (i); 322 } 323 324 /* Iterate until the worklist is empty. */ 325 while (tos != worklist) 326 { 327 edge e; 328 edge_iterator ei; 329 330 /* Pull a block off the worklist. */ 331 bb = *--tos; 332 333 /* For each predecessor block. */ 334 FOR_EACH_EDGE (e, ei, bb->preds) 335 { 336 basic_block pred = e->src; 337 int pred_index = pred->index; 338 339 /* None of this is necessary for the entry block. */ 340 if (pred != ENTRY_BLOCK_PTR 341 && ! bitmap_bit_p (livein, pred_index) 342 && ! bitmap_bit_p (def_blocks, pred_index)) 343 { 344 *tos++ = pred; 345 bitmap_set_bit (livein, pred_index); 346 } 347 } 348 } 349 350 free (worklist); 351} 352 353 354/* Return the set of blocks where variable VAR is defined and the blocks 355 where VAR is live on entry (livein). If no entry is found in 356 DEF_BLOCKS, a new one is created and returned. */ 357 358static inline struct def_blocks_d * 359get_def_blocks_for (tree var) 360{ 361 struct def_blocks_d db, *db_p; 362 void **slot; 363 364 db.var = var; 365 slot = htab_find_slot (def_blocks, (void *) &db, INSERT); 366 if (*slot == NULL) 367 { 368 db_p = xmalloc (sizeof (*db_p)); 369 db_p->var = var; 370 db_p->def_blocks = BITMAP_ALLOC (NULL); 371 db_p->phi_blocks = BITMAP_ALLOC (NULL); 372 db_p->livein_blocks = BITMAP_ALLOC (NULL); 373 *slot = (void *) db_p; 374 } 375 else 376 db_p = (struct def_blocks_d *) *slot; 377 378 return db_p; 379} 380 381 382/* Mark block BB as the definition site for variable VAR. PHI_P is true if 383 VAR is defined by a PHI node. */ 384 385static void 386set_def_block (tree var, basic_block bb, bool phi_p) 387{ 388 struct def_blocks_d *db_p; 389 enum need_phi_state state; 390 391 state = get_phi_state (var); 392 db_p = get_def_blocks_for (var); 393 394 /* Set the bit corresponding to the block where VAR is defined. */ 395 bitmap_set_bit (db_p->def_blocks, bb->index); 396 if (phi_p) 397 bitmap_set_bit (db_p->phi_blocks, bb->index); 398 399 /* Keep track of whether or not we may need to insert PHI nodes. 400 401 If we are in the UNKNOWN state, then this is the first definition 402 of VAR. Additionally, we have not seen any uses of VAR yet, so 403 we do not need a PHI node for this variable at this time (i.e., 404 transition to NEED_PHI_STATE_NO). 405 406 If we are in any other state, then we either have multiple definitions 407 of this variable occurring in different blocks or we saw a use of the 408 variable which was not dominated by the block containing the 409 definition(s). In this case we may need a PHI node, so enter 410 state NEED_PHI_STATE_MAYBE. */ 411 if (state == NEED_PHI_STATE_UNKNOWN) 412 set_phi_state (var, NEED_PHI_STATE_NO); 413 else 414 set_phi_state (var, NEED_PHI_STATE_MAYBE); 415} 416 417 418/* Mark block BB as having VAR live at the entry to BB. */ 419 420static void 421set_livein_block (tree var, basic_block bb) 422{ 423 struct def_blocks_d *db_p; 424 enum need_phi_state state = get_phi_state (var); 425 426 db_p = get_def_blocks_for (var); 427 428 /* Set the bit corresponding to the block where VAR is live in. */ 429 bitmap_set_bit (db_p->livein_blocks, bb->index); 430 431 /* Keep track of whether or not we may need to insert PHI nodes. 432 433 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated 434 by the single block containing the definition(s) of this variable. If 435 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to 436 NEED_PHI_STATE_MAYBE. */ 437 if (state == NEED_PHI_STATE_NO) 438 { 439 int def_block_index = bitmap_first_set_bit (db_p->def_blocks); 440 441 if (def_block_index == -1 442 || ! dominated_by_p (CDI_DOMINATORS, bb, 443 BASIC_BLOCK (def_block_index))) 444 set_phi_state (var, NEED_PHI_STATE_MAYBE); 445 } 446 else 447 set_phi_state (var, NEED_PHI_STATE_MAYBE); 448} 449 450 451/* Return true if symbol SYM is marked for renaming. */ 452 453static inline bool 454symbol_marked_for_renaming (tree sym) 455{ 456 gcc_assert (DECL_P (sym)); 457 return bitmap_bit_p (syms_to_rename, DECL_UID (sym)); 458} 459 460 461/* Return true if NAME is in OLD_SSA_NAMES. */ 462 463static inline bool 464is_old_name (tree name) 465{ 466 unsigned ver = SSA_NAME_VERSION (name); 467 return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver); 468} 469 470 471/* Return true if NAME is in NEW_SSA_NAMES. */ 472 473static inline bool 474is_new_name (tree name) 475{ 476 unsigned ver = SSA_NAME_VERSION (name); 477 return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver); 478} 479 480 481/* Hashing and equality functions for REPL_TBL. */ 482 483static hashval_t 484repl_map_hash (const void *p) 485{ 486 return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name); 487} 488 489static int 490repl_map_eq (const void *p1, const void *p2) 491{ 492 return ((const struct repl_map_d *)p1)->name 493 == ((const struct repl_map_d *)p2)->name; 494} 495 496static void 497repl_map_free (void *p) 498{ 499 BITMAP_FREE (((struct repl_map_d *)p)->set); 500 free (p); 501} 502 503 504/* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET). */ 505 506static inline bitmap 507names_replaced_by (tree new) 508{ 509 struct repl_map_d m; 510 void **slot; 511 512 m.name = new; 513 slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT); 514 515 /* If N was not registered in the replacement table, return NULL. */ 516 if (slot == NULL || *slot == NULL) 517 return NULL; 518 519 return ((struct repl_map_d *) *slot)->set; 520} 521 522 523/* Add OLD to REPL_TBL[NEW].SET. */ 524 525static inline void 526add_to_repl_tbl (tree new, tree old) 527{ 528 struct repl_map_d m, *mp; 529 void **slot; 530 531 m.name = new; 532 slot = htab_find_slot (repl_tbl, (void *) &m, INSERT); 533 if (*slot == NULL) 534 { 535 mp = xmalloc (sizeof (*mp)); 536 mp->name = new; 537 mp->set = BITMAP_ALLOC (NULL); 538 *slot = (void *) mp; 539 } 540 else 541 mp = (struct repl_map_d *) *slot; 542 543 bitmap_set_bit (mp->set, SSA_NAME_VERSION (old)); 544} 545 546 547/* Add a new mapping NEW -> OLD REPL_TBL. Every entry N_i in REPL_TBL 548 represents the set of names O_1 ... O_j replaced by N_i. This is 549 used by update_ssa and its helpers to introduce new SSA names in an 550 already formed SSA web. */ 551 552static void 553add_new_name_mapping (tree new, tree old) 554{ 555 timevar_push (TV_TREE_SSA_INCREMENTAL); 556 557 /* OLD and NEW must be different SSA names for the same symbol. */ 558 gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old)); 559 560 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our 561 caller may have created new names since the set was created. */ 562 if (new_ssa_names->n_bits <= num_ssa_names - 1) 563 { 564 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR; 565 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0); 566 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0); 567 } 568 569 /* If this mapping is for virtual names, we will need to update 570 virtual operands. */ 571 if (!is_gimple_reg (new)) 572 { 573 tree sym; 574 size_t uid; 575 576 need_to_update_vops_p = true; 577 578 /* Keep counts of virtual mappings and symbols to use in the 579 virtual mapping heuristic. If we have large numbers of 580 virtual mappings for a relatively low number of symbols, it 581 will make more sense to rename the symbols from scratch. 582 Otherwise, the insertion of PHI nodes for each of the old 583 names in these mappings will be very slow. */ 584 sym = SSA_NAME_VAR (new); 585 uid = DECL_UID (sym); 586 update_ssa_stats.num_virtual_mappings++; 587 if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid)) 588 { 589 bitmap_set_bit (update_ssa_stats.virtual_symbols, uid); 590 update_ssa_stats.num_virtual_symbols++; 591 } 592 } 593 594 /* Update the REPL_TBL table. */ 595 add_to_repl_tbl (new, old); 596 597 /* If OLD had already been registered as a new name, then all the 598 names that OLD replaces should also be replaced by NEW. */ 599 if (is_new_name (old)) 600 bitmap_ior_into (names_replaced_by (new), names_replaced_by (old)); 601 602 /* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES, 603 respectively. */ 604 SET_BIT (new_ssa_names, SSA_NAME_VERSION (new)); 605 SET_BIT (old_ssa_names, SSA_NAME_VERSION (old)); 606 607 /* Update mapping counter to use in the virtual mapping heuristic. */ 608 update_ssa_stats.num_total_mappings++; 609 610 timevar_pop (TV_TREE_SSA_INCREMENTAL); 611} 612 613 614/* Call back for walk_dominator_tree used to collect definition sites 615 for every variable in the function. For every statement S in block 616 BB: 617 618 1- Variables defined by S in the DEFS of S are marked in the bitmap 619 WALK_DATA->GLOBAL_DATA->KILLS. 620 621 2- If S uses a variable VAR and there is no preceding kill of VAR, 622 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR. 623 624 This information is used to determine which variables are live 625 across block boundaries to reduce the number of PHI nodes 626 we create. */ 627 628static void 629mark_def_sites (struct dom_walk_data *walk_data, 630 basic_block bb, 631 block_stmt_iterator bsi) 632{ 633 struct mark_def_sites_global_data *gd = walk_data->global_data; 634 bitmap kills = gd->kills; 635 tree stmt, def; 636 use_operand_p use_p; 637 def_operand_p def_p; 638 ssa_op_iter iter; 639 640 stmt = bsi_stmt (bsi); 641 update_stmt_if_modified (stmt); 642 643 REGISTER_DEFS_IN_THIS_STMT (stmt) = 0; 644 REWRITE_THIS_STMT (stmt) = 0; 645 646 /* If a variable is used before being set, then the variable is live 647 across a block boundary, so mark it live-on-entry to BB. */ 648 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 649 SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL) 650 { 651 tree sym = USE_FROM_PTR (use_p); 652 gcc_assert (DECL_P (sym)); 653 if (!bitmap_bit_p (kills, DECL_UID (sym))) 654 set_livein_block (sym, bb); 655 REWRITE_THIS_STMT (stmt) = 1; 656 } 657 658 /* Note that virtual definitions are irrelevant for computing KILLS 659 because a V_MAY_DEF does not constitute a killing definition of the 660 variable. However, the operand of a virtual definitions is a use 661 of the variable, so it may cause the variable to be considered 662 live-on-entry. */ 663 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter) 664 { 665 tree sym = USE_FROM_PTR (use_p); 666 gcc_assert (DECL_P (sym)); 667 set_livein_block (sym, bb); 668 set_def_block (sym, bb, false); 669 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1; 670 REWRITE_THIS_STMT (stmt) = 1; 671 } 672 673 /* Now process the defs and must-defs made by this statement. */ 674 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF) 675 { 676 gcc_assert (DECL_P (def)); 677 set_def_block (def, bb, false); 678 bitmap_set_bit (kills, DECL_UID (def)); 679 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1; 680 } 681 682 /* If we found the statement interesting then also mark the block BB 683 as interesting. */ 684 if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt)) 685 SET_BIT (gd->interesting_blocks, bb->index); 686} 687 688 689/* Given a set of blocks with variable definitions (DEF_BLOCKS), 690 return a bitmap with all the blocks in the iterated dominance 691 frontier of the blocks in DEF_BLOCKS. DFS contains dominance 692 frontier information as returned by compute_dominance_frontiers. 693 694 The resulting set of blocks are the potential sites where PHI nodes 695 are needed. The caller is responsible from freeing the memory 696 allocated for the return value. */ 697 698static bitmap 699find_idf (bitmap def_blocks, bitmap *dfs) 700{ 701 bitmap_iterator bi; 702 unsigned bb_index; 703 VEC(int,heap) *work_stack; 704 bitmap phi_insertion_points; 705 706 work_stack = VEC_alloc (int, heap, n_basic_blocks); 707 phi_insertion_points = BITMAP_ALLOC (NULL); 708 709 /* Seed the work list with all the blocks in DEF_BLOCKS. */ 710 EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi) 711 /* We use VEC_quick_push here for speed. This is safe because we 712 know that the number of definition blocks is no greater than 713 the number of basic blocks, which is the initial capacity of 714 WORK_STACK. */ 715 VEC_quick_push (int, work_stack, bb_index); 716 717 /* Pop a block off the worklist, add every block that appears in 718 the original block's DF that we have not already processed to 719 the worklist. Iterate until the worklist is empty. Blocks 720 which are added to the worklist are potential sites for 721 PHI nodes. */ 722 while (VEC_length (int, work_stack) > 0) 723 { 724 bb_index = VEC_pop (int, work_stack); 725 726 /* Since the registration of NEW -> OLD name mappings is done 727 separately from the call to update_ssa, when updating the SSA 728 form, the basic blocks where new and/or old names are defined 729 may have disappeared by CFG cleanup calls. In this case, 730 we may pull a non-existing block from the work stack. */ 731 gcc_assert (bb_index < (unsigned) last_basic_block); 732 733 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points, 734 0, bb_index, bi) 735 { 736 /* Use a safe push because if there is a definition of VAR 737 in every basic block, then WORK_STACK may eventually have 738 more than N_BASIC_BLOCK entries. */ 739 VEC_safe_push (int, heap, work_stack, bb_index); 740 bitmap_set_bit (phi_insertion_points, bb_index); 741 } 742 } 743 744 VEC_free (int, heap, work_stack); 745 746 return phi_insertion_points; 747} 748 749 750/* Return the set of blocks where variable VAR is defined and the blocks 751 where VAR is live on entry (livein). Return NULL, if no entry is 752 found in DEF_BLOCKS. */ 753 754static inline struct def_blocks_d * 755find_def_blocks_for (tree var) 756{ 757 struct def_blocks_d dm; 758 dm.var = var; 759 return (struct def_blocks_d *) htab_find (def_blocks, &dm); 760} 761 762 763/* Retrieve or create a default definition for symbol SYM. */ 764 765static inline tree 766get_default_def_for (tree sym) 767{ 768 tree ddef = default_def (sym); 769 770 if (ddef == NULL_TREE) 771 { 772 ddef = make_ssa_name (sym, build_empty_stmt ()); 773 set_default_def (sym, ddef); 774 } 775 776 return ddef; 777} 778 779 780/* Insert PHI nodes for variable VAR using the iterated dominance 781 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this 782 function assumes that the caller is incrementally updating the SSA 783 form, in which case (1) VAR is assumed to be an SSA name, (2) a new 784 SSA name is created for VAR's symbol, and, (3) all the arguments 785 for the newly created PHI node are set to VAR. 786 787 PHI_INSERTION_POINTS is updated to reflect nodes that already had a 788 PHI node for VAR. On exit, only the nodes that received a PHI node 789 for VAR will be present in PHI_INSERTION_POINTS. */ 790 791static void 792insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p) 793{ 794 unsigned bb_index; 795 edge e; 796 tree phi; 797 basic_block bb; 798 bitmap_iterator bi; 799 struct def_blocks_d *def_map; 800 801 def_map = find_def_blocks_for (var); 802 gcc_assert (def_map); 803 804 /* Remove the blocks where we already have PHI nodes for VAR. */ 805 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks); 806 807 /* Now compute global livein for this variable. Note this modifies 808 def_map->livein_blocks. */ 809 compute_global_livein (def_map->livein_blocks, def_map->def_blocks); 810 811 /* And insert the PHI nodes. */ 812 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks, 813 0, bb_index, bi) 814 { 815 bb = BASIC_BLOCK (bb_index); 816 817 if (update_p && TREE_CODE (var) == SSA_NAME) 818 { 819 /* If we are rewriting SSA names, create the LHS of the PHI 820 node by duplicating VAR. This is useful in the case of 821 pointers, to also duplicate pointer attributes (alias 822 information, in particular). */ 823 edge_iterator ei; 824 tree new_lhs; 825 826 phi = create_phi_node (var, bb); 827 new_lhs = duplicate_ssa_name (var, phi); 828 SET_PHI_RESULT (phi, new_lhs); 829 add_new_name_mapping (new_lhs, var); 830 831 /* Add VAR to every argument slot of PHI. We need VAR in 832 every argument so that rewrite_update_phi_arguments knows 833 which name is this PHI node replacing. If VAR is a 834 symbol marked for renaming, this is not necessary, the 835 renamer will use the symbol on the LHS to get its 836 reaching definition. */ 837 FOR_EACH_EDGE (e, ei, bb->preds) 838 add_phi_arg (phi, var, e); 839 } 840 else 841 { 842 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var); 843 phi = create_phi_node (sym, bb); 844 } 845 846 /* Mark this PHI node as interesting for update_ssa. */ 847 REGISTER_DEFS_IN_THIS_STMT (phi) = 1; 848 REWRITE_THIS_STMT (phi) = 1; 849 } 850} 851 852 853/* Insert PHI nodes at the dominance frontier of blocks with variable 854 definitions. DFS contains the dominance frontier information for 855 the flowgraph. PHI nodes will only be inserted at the dominance 856 frontier of definition blocks for variables whose NEED_PHI_STATE 857 annotation is marked as ``maybe'' or ``unknown'' (computed by 858 mark_def_sites). */ 859 860static void 861insert_phi_nodes (bitmap *dfs) 862{ 863 referenced_var_iterator rvi; 864 tree var; 865 866 timevar_push (TV_TREE_INSERT_PHI_NODES); 867 868 FOR_EACH_REFERENCED_VAR (var, rvi) 869 { 870 struct def_blocks_d *def_map; 871 bitmap idf; 872 873 def_map = find_def_blocks_for (var); 874 if (def_map == NULL) 875 continue; 876 877 if (get_phi_state (var) != NEED_PHI_STATE_NO) 878 { 879 idf = find_idf (def_map->def_blocks, dfs); 880 insert_phi_nodes_for (var, idf, false); 881 BITMAP_FREE (idf); 882 } 883 } 884 885 timevar_pop (TV_TREE_INSERT_PHI_NODES); 886} 887 888 889/* Register DEF (an SSA_NAME) to be a new definition for its underlying 890 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition 891 into the stack pointed to by BLOCK_DEFS_P. */ 892 893void 894register_new_def (tree def, VEC(tree,heap) **block_defs_p) 895{ 896 tree var = SSA_NAME_VAR (def); 897 tree currdef; 898 899 /* If this variable is set in a single basic block and all uses are 900 dominated by the set(s) in that single basic block, then there is 901 no reason to record anything for this variable in the block local 902 definition stacks. Doing so just wastes time and memory. 903 904 This is the same test to prune the set of variables which may 905 need PHI nodes. So we just use that information since it's already 906 computed and available for us to use. */ 907 if (get_phi_state (var) == NEED_PHI_STATE_NO) 908 { 909 set_current_def (var, def); 910 return; 911 } 912 913 currdef = get_current_def (var); 914 915 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is 916 later used by the dominator tree callbacks to restore the reaching 917 definitions for all the variables defined in the block after a recursive 918 visit to all its immediately dominated blocks. If there is no current 919 reaching definition, then just record the underlying _DECL node. */ 920 VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var); 921 922 /* Set the current reaching definition for VAR to be DEF. */ 923 set_current_def (var, def); 924} 925 926 927/* Perform a depth-first traversal of the dominator tree looking for 928 variables to rename. BB is the block where to start searching. 929 Renaming is a five step process: 930 931 1- Every definition made by PHI nodes at the start of the blocks is 932 registered as the current definition for the corresponding variable. 933 934 2- Every statement in BB is rewritten. USE and VUSE operands are 935 rewritten with their corresponding reaching definition. DEF and 936 VDEF targets are registered as new definitions. 937 938 3- All the PHI nodes in successor blocks of BB are visited. The 939 argument corresponding to BB is replaced with its current reaching 940 definition. 941 942 4- Recursively rewrite every dominator child block of BB. 943 944 5- Restore (in reverse order) the current reaching definition for every 945 new definition introduced in this block. This is done so that when 946 we return from the recursive call, all the current reaching 947 definitions are restored to the names that were valid in the 948 dominator parent of BB. */ 949 950/* SSA Rewriting Step 1. Initialization, create a block local stack 951 of reaching definitions for new SSA names produced in this block 952 (BLOCK_DEFS). Register new definitions for every PHI node in the 953 block. */ 954 955static void 956rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 957 basic_block bb) 958{ 959 tree phi; 960 961 if (dump_file && (dump_flags & TDF_DETAILS)) 962 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index); 963 964 /* Mark the unwind point for this block. */ 965 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE); 966 967 /* Step 1. Register new definitions for every PHI node in the block. 968 Conceptually, all the PHI nodes are executed in parallel and each PHI 969 node introduces a new version for the associated variable. */ 970 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 971 { 972 tree result = PHI_RESULT (phi); 973 register_new_def (result, &block_defs_stack); 974 } 975} 976 977 978/* Return the current definition for variable VAR. If none is found, 979 create a new SSA name to act as the zeroth definition for VAR. If VAR 980 is call clobbered and there exists a more recent definition of 981 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR 982 has been clobbered by a function call since its last assignment. */ 983 984static tree 985get_reaching_def (tree var) 986{ 987 tree currdef_var, avar; 988 989 /* Lookup the current reaching definition for VAR. */ 990 currdef_var = get_current_def (var); 991 992 /* If there is no reaching definition for VAR, create and register a 993 default definition for it (if needed). */ 994 if (currdef_var == NULL_TREE) 995 { 996 avar = DECL_P (var) ? var : SSA_NAME_VAR (var); 997 currdef_var = get_default_def_for (avar); 998 set_current_def (var, currdef_var); 999 } 1000 1001 /* Return the current reaching definition for VAR, or the default 1002 definition, if we had to create one. */ 1003 return currdef_var; 1004} 1005 1006 1007/* SSA Rewriting Step 2. Rewrite every variable used in each statement in 1008 the block with its immediate reaching definitions. Update the current 1009 definition of a variable when a new real or virtual definition is found. */ 1010 1011static void 1012rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1013 basic_block bb ATTRIBUTE_UNUSED, 1014 block_stmt_iterator si) 1015{ 1016 tree stmt; 1017 use_operand_p use_p; 1018 def_operand_p def_p; 1019 ssa_op_iter iter; 1020 1021 stmt = bsi_stmt (si); 1022 1023 /* If mark_def_sites decided that we don't need to rewrite this 1024 statement, ignore it. */ 1025 if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt)) 1026 return; 1027 1028 if (dump_file && (dump_flags & TDF_DETAILS)) 1029 { 1030 fprintf (dump_file, "Renaming statement "); 1031 print_generic_stmt (dump_file, stmt, TDF_SLIM); 1032 fprintf (dump_file, "\n"); 1033 } 1034 1035 /* Step 1. Rewrite USES and VUSES in the statement. */ 1036 if (REWRITE_THIS_STMT (stmt)) 1037 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 1038 SSA_OP_ALL_USES|SSA_OP_ALL_KILLS) 1039 { 1040 tree var = USE_FROM_PTR (use_p); 1041 gcc_assert (DECL_P (var)); 1042 SET_USE (use_p, get_reaching_def (var)); 1043 } 1044 1045 /* Step 2. Register the statement's DEF and VDEF operands. */ 1046 if (REGISTER_DEFS_IN_THIS_STMT (stmt)) 1047 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 1048 { 1049 tree var = DEF_FROM_PTR (def_p); 1050 gcc_assert (DECL_P (var)); 1051 SET_DEF (def_p, make_ssa_name (var, stmt)); 1052 register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack); 1053 } 1054} 1055 1056 1057/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for 1058 PHI nodes. For every PHI node found, add a new argument containing the 1059 current reaching definition for the variable and the edge through which 1060 that definition is reaching the PHI node. */ 1061 1062static void 1063rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1064 basic_block bb) 1065{ 1066 edge e; 1067 edge_iterator ei; 1068 1069 FOR_EACH_EDGE (e, ei, bb->succs) 1070 { 1071 tree phi; 1072 1073 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 1074 { 1075 tree currdef; 1076 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi))); 1077 add_phi_arg (phi, currdef, e); 1078 } 1079 } 1080} 1081 1082 1083/* Called after visiting basic block BB. Restore CURRDEFS to its 1084 original value. */ 1085 1086static void 1087rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1088 basic_block bb ATTRIBUTE_UNUSED) 1089{ 1090 /* Restore CURRDEFS to its original state. */ 1091 while (VEC_length (tree, block_defs_stack) > 0) 1092 { 1093 tree tmp = VEC_pop (tree, block_defs_stack); 1094 tree saved_def, var; 1095 1096 if (tmp == NULL_TREE) 1097 break; 1098 1099 /* If we recorded an SSA_NAME, then make the SSA_NAME the current 1100 definition of its underlying variable. If we recorded anything 1101 else, it must have been an _DECL node and its current reaching 1102 definition must have been NULL. */ 1103 if (TREE_CODE (tmp) == SSA_NAME) 1104 { 1105 saved_def = tmp; 1106 var = SSA_NAME_VAR (saved_def); 1107 } 1108 else 1109 { 1110 saved_def = NULL; 1111 var = tmp; 1112 } 1113 1114 set_current_def (var, saved_def); 1115 } 1116} 1117 1118 1119/* Dump SSA information to FILE. */ 1120 1121void 1122dump_tree_ssa (FILE *file) 1123{ 1124 basic_block bb; 1125 const char *funcname 1126 = lang_hooks.decl_printable_name (current_function_decl, 2); 1127 1128 fprintf (file, "SSA information for %s\n\n", funcname); 1129 1130 FOR_EACH_BB (bb) 1131 { 1132 dump_bb (bb, file, 0); 1133 fputs (" ", file); 1134 print_generic_stmt (file, phi_nodes (bb), dump_flags); 1135 fputs ("\n\n", file); 1136 } 1137} 1138 1139 1140/* Dump SSA information to stderr. */ 1141 1142void 1143debug_tree_ssa (void) 1144{ 1145 dump_tree_ssa (stderr); 1146} 1147 1148 1149/* Dump statistics for the hash table HTAB. */ 1150 1151static void 1152htab_statistics (FILE *file, htab_t htab) 1153{ 1154 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 1155 (long) htab_size (htab), 1156 (long) htab_elements (htab), 1157 htab_collisions (htab)); 1158} 1159 1160 1161/* Dump SSA statistics on FILE. */ 1162 1163void 1164dump_tree_ssa_stats (FILE *file) 1165{ 1166 fprintf (file, "\nHash table statistics:\n"); 1167 1168 fprintf (file, " def_blocks: "); 1169 htab_statistics (file, def_blocks); 1170 1171 fprintf (file, "\n"); 1172} 1173 1174 1175/* Dump SSA statistics on stderr. */ 1176 1177void 1178debug_tree_ssa_stats (void) 1179{ 1180 dump_tree_ssa_stats (stderr); 1181} 1182 1183 1184/* Hashing and equality functions for DEF_BLOCKS. */ 1185 1186static hashval_t 1187def_blocks_hash (const void *p) 1188{ 1189 return htab_hash_pointer 1190 ((const void *)((const struct def_blocks_d *)p)->var); 1191} 1192 1193static int 1194def_blocks_eq (const void *p1, const void *p2) 1195{ 1196 return ((const struct def_blocks_d *)p1)->var 1197 == ((const struct def_blocks_d *)p2)->var; 1198} 1199 1200 1201/* Free memory allocated by one entry in DEF_BLOCKS. */ 1202 1203static void 1204def_blocks_free (void *p) 1205{ 1206 struct def_blocks_d *entry = p; 1207 BITMAP_FREE (entry->def_blocks); 1208 BITMAP_FREE (entry->phi_blocks); 1209 BITMAP_FREE (entry->livein_blocks); 1210 free (entry); 1211} 1212 1213 1214/* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */ 1215 1216static int 1217debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED) 1218{ 1219 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot; 1220 1221 fprintf (stderr, "VAR: "); 1222 print_generic_expr (stderr, db_p->var, dump_flags); 1223 bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}"); 1224 bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n"); 1225 1226 return 1; 1227} 1228 1229 1230/* Dump the DEF_BLOCKS hash table on stderr. */ 1231 1232void 1233debug_def_blocks (void) 1234{ 1235 htab_traverse (def_blocks, debug_def_blocks_r, NULL); 1236} 1237 1238 1239/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */ 1240 1241static inline void 1242register_new_update_single (tree new_name, tree old_name) 1243{ 1244 tree currdef = get_current_def (old_name); 1245 1246 /* Push the current reaching definition into *BLOCK_DEFS_P. 1247 This stack is later used by the dominator tree callbacks to 1248 restore the reaching definitions for all the variables 1249 defined in the block after a recursive visit to all its 1250 immediately dominated blocks. */ 1251 VEC_reserve (tree, heap, block_defs_stack, 2); 1252 VEC_quick_push (tree, block_defs_stack, currdef); 1253 VEC_quick_push (tree, block_defs_stack, old_name); 1254 1255 /* Set the current reaching definition for OLD_NAME to be 1256 NEW_NAME. */ 1257 set_current_def (old_name, new_name); 1258} 1259 1260 1261/* Register NEW_NAME to be the new reaching definition for all the 1262 names in OLD_NAMES. Used by the incremental SSA update routines to 1263 replace old SSA names with new ones. */ 1264 1265static inline void 1266register_new_update_set (tree new_name, bitmap old_names) 1267{ 1268 bitmap_iterator bi; 1269 unsigned i; 1270 1271 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi) 1272 register_new_update_single (new_name, ssa_name (i)); 1273} 1274 1275 1276/* Initialization of block data structures for the incremental SSA 1277 update pass. Create a block local stack of reaching definitions 1278 for new SSA names produced in this block (BLOCK_DEFS). Register 1279 new definitions for every PHI node in the block. */ 1280 1281static void 1282rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1283 basic_block bb) 1284{ 1285 edge e; 1286 edge_iterator ei; 1287 tree phi; 1288 bool is_abnormal_phi; 1289 1290 if (dump_file && (dump_flags & TDF_DETAILS)) 1291 fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n", 1292 bb->index); 1293 1294 /* Mark the unwind point for this block. */ 1295 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE); 1296 1297 /* Mark the LHS if any of the arguments flows through an abnormal 1298 edge. */ 1299 is_abnormal_phi = false; 1300 FOR_EACH_EDGE (e, ei, bb->preds) 1301 if (e->flags & EDGE_ABNORMAL) 1302 { 1303 is_abnormal_phi = true; 1304 break; 1305 } 1306 1307 /* If any of the PHI nodes is a replacement for a name in 1308 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then 1309 register it as a new definition for its corresponding name. Also 1310 register definitions for names whose underlying symbols are 1311 marked for renaming. */ 1312 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1313 { 1314 tree lhs, lhs_sym; 1315 1316 if (!REGISTER_DEFS_IN_THIS_STMT (phi)) 1317 continue; 1318 1319 lhs = PHI_RESULT (phi); 1320 lhs_sym = SSA_NAME_VAR (lhs); 1321 1322 if (symbol_marked_for_renaming (lhs_sym)) 1323 register_new_update_single (lhs, lhs_sym); 1324 else 1325 { 1326 /* If LHS is a new name, register a new definition for all 1327 the names replaced by LHS. */ 1328 if (is_new_name (lhs)) 1329 register_new_update_set (lhs, names_replaced_by (lhs)); 1330 1331 /* If LHS is an OLD name, register it as a new definition 1332 for itself. */ 1333 if (is_old_name (lhs)) 1334 register_new_update_single (lhs, lhs); 1335 } 1336 1337 if (is_abnormal_phi) 1338 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1; 1339 } 1340} 1341 1342 1343/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore 1344 the current reaching definition of every name re-written in BB to 1345 the original reaching definition before visiting BB. This 1346 unwinding must be done in the opposite order to what is done in 1347 register_new_update_set. */ 1348 1349static void 1350rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1351 basic_block bb ATTRIBUTE_UNUSED) 1352{ 1353 while (VEC_length (tree, block_defs_stack) > 0) 1354 { 1355 tree var = VEC_pop (tree, block_defs_stack); 1356 tree saved_def; 1357 1358 /* NULL indicates the unwind stop point for this block (see 1359 rewrite_update_init_block). */ 1360 if (var == NULL) 1361 return; 1362 1363 saved_def = VEC_pop (tree, block_defs_stack); 1364 set_current_def (var, saved_def); 1365 } 1366} 1367 1368 1369/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or 1370 it is a symbol marked for renaming, replace it with USE_P's current 1371 reaching definition. */ 1372 1373static inline void 1374maybe_replace_use (use_operand_p use_p) 1375{ 1376 tree rdef = NULL_TREE; 1377 tree use = USE_FROM_PTR (use_p); 1378 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 1379 1380 if (symbol_marked_for_renaming (sym)) 1381 rdef = get_reaching_def (sym); 1382 else if (is_old_name (use)) 1383 rdef = get_reaching_def (use); 1384 1385 if (rdef && rdef != use) 1386 SET_USE (use_p, rdef); 1387} 1388 1389 1390/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES 1391 or OLD_SSA_NAMES, or if it is a symbol marked for renaming, 1392 register it as the current definition for the names replaced by 1393 DEF_P. */ 1394 1395static inline void 1396maybe_register_def (def_operand_p def_p, tree stmt) 1397{ 1398 tree def = DEF_FROM_PTR (def_p); 1399 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 1400 1401 /* If DEF is a naked symbol that needs renaming, create a 1402 new name for it. */ 1403 if (symbol_marked_for_renaming (sym)) 1404 { 1405 if (DECL_P (def)) 1406 { 1407 def = make_ssa_name (def, stmt); 1408 SET_DEF (def_p, def); 1409 } 1410 1411 register_new_update_single (def, sym); 1412 } 1413 else 1414 { 1415 /* If DEF is a new name, register it as a new definition 1416 for all the names replaced by DEF. */ 1417 if (is_new_name (def)) 1418 register_new_update_set (def, names_replaced_by (def)); 1419 1420 /* If DEF is an old name, register DEF as a new 1421 definition for itself. */ 1422 if (is_old_name (def)) 1423 register_new_update_single (def, def); 1424 } 1425} 1426 1427 1428/* Update every variable used in the statement pointed-to by SI. The 1429 statement is assumed to be in SSA form already. Names in 1430 OLD_SSA_NAMES used by SI will be updated to their current reaching 1431 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI 1432 will be registered as a new definition for their corresponding name 1433 in OLD_SSA_NAMES. */ 1434 1435static void 1436rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1437 basic_block bb ATTRIBUTE_UNUSED, 1438 block_stmt_iterator si) 1439{ 1440 stmt_ann_t ann; 1441 tree stmt; 1442 use_operand_p use_p; 1443 def_operand_p def_p; 1444 ssa_op_iter iter; 1445 1446 stmt = bsi_stmt (si); 1447 ann = stmt_ann (stmt); 1448 1449 /* Only update marked statements. */ 1450 if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt)) 1451 return; 1452 1453 if (dump_file && (dump_flags & TDF_DETAILS)) 1454 { 1455 fprintf (dump_file, "Updating SSA information for statement "); 1456 print_generic_stmt (dump_file, stmt, TDF_SLIM); 1457 fprintf (dump_file, "\n"); 1458 } 1459 1460 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying 1461 symbol is marked for renaming. */ 1462 if (REWRITE_THIS_STMT (stmt)) 1463 { 1464 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) 1465 maybe_replace_use (use_p); 1466 1467 if (need_to_update_vops_p) 1468 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 1469 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 1470 maybe_replace_use (use_p); 1471 } 1472 1473 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES. 1474 Also register definitions for names whose underlying symbol is 1475 marked for renaming. */ 1476 if (REGISTER_DEFS_IN_THIS_STMT (stmt)) 1477 { 1478 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF) 1479 maybe_register_def (def_p, stmt); 1480 1481 if (need_to_update_vops_p) 1482 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS) 1483 maybe_register_def (def_p, stmt); 1484 } 1485} 1486 1487 1488/* Replace the operand pointed to by USE_P with USE's current reaching 1489 definition. */ 1490 1491static inline void 1492replace_use (use_operand_p use_p, tree use) 1493{ 1494 tree rdef = get_reaching_def (use); 1495 if (rdef != use) 1496 SET_USE (use_p, rdef); 1497} 1498 1499 1500/* Visit all the successor blocks of BB looking for PHI nodes. For 1501 every PHI node found, check if any of its arguments is in 1502 OLD_SSA_NAMES. If so, and if the argument has a current reaching 1503 definition, replace it. */ 1504 1505static void 1506rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1507 basic_block bb) 1508{ 1509 edge e; 1510 edge_iterator ei; 1511 1512 FOR_EACH_EDGE (e, ei, bb->succs) 1513 { 1514 tree phi; 1515 1516 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 1517 { 1518 tree arg; 1519 use_operand_p arg_p; 1520 1521 /* Skip PHI nodes that are not marked for rewrite. */ 1522 if (!REWRITE_THIS_STMT (phi)) 1523 continue; 1524 1525 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); 1526 arg = USE_FROM_PTR (arg_p); 1527 1528 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME) 1529 continue; 1530 1531 if (arg == NULL_TREE) 1532 { 1533 /* When updating a PHI node for a recently introduced 1534 symbol we may find NULL arguments. That's why we 1535 take the symbol from the LHS of the PHI node. */ 1536 replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi))); 1537 } 1538 else 1539 { 1540 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg); 1541 1542 if (symbol_marked_for_renaming (sym)) 1543 replace_use (arg_p, sym); 1544 else if (is_old_name (arg)) 1545 replace_use (arg_p, arg); 1546 } 1547 1548 if (e->flags & EDGE_ABNORMAL) 1549 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1; 1550 } 1551 } 1552} 1553 1554 1555/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA 1556 form. 1557 1558 ENTRY indicates the block where to start. Every block dominated by 1559 ENTRY will be rewritten. 1560 1561 WHAT indicates what actions will be taken by the renamer (see enum 1562 rewrite_mode). 1563 1564 BLOCKS are the set of interesting blocks for the dominator walker 1565 to process. If this set is NULL, then all the nodes dominated 1566 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that 1567 are not present in BLOCKS are ignored. */ 1568 1569static void 1570rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks) 1571{ 1572 struct dom_walk_data walk_data; 1573 1574 /* Rewrite all the basic blocks in the program. */ 1575 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS); 1576 1577 /* Setup callbacks for the generic dominator tree walker. */ 1578 memset (&walk_data, 0, sizeof (walk_data)); 1579 1580 walk_data.dom_direction = CDI_DOMINATORS; 1581 walk_data.interesting_blocks = blocks; 1582 1583 if (what == REWRITE_UPDATE) 1584 walk_data.before_dom_children_before_stmts = rewrite_update_init_block; 1585 else 1586 walk_data.before_dom_children_before_stmts = rewrite_initialize_block; 1587 1588 if (what == REWRITE_ALL) 1589 walk_data.before_dom_children_walk_stmts = rewrite_stmt; 1590 else if (what == REWRITE_UPDATE) 1591 walk_data.before_dom_children_walk_stmts = rewrite_update_stmt; 1592 else 1593 gcc_unreachable (); 1594 1595 if (what == REWRITE_ALL) 1596 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments; 1597 else if (what == REWRITE_UPDATE) 1598 walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments; 1599 else 1600 gcc_unreachable (); 1601 1602 if (what == REWRITE_ALL) 1603 walk_data.after_dom_children_after_stmts = rewrite_finalize_block; 1604 else if (what == REWRITE_UPDATE) 1605 walk_data.after_dom_children_after_stmts = rewrite_update_fini_block; 1606 else 1607 gcc_unreachable (); 1608 1609 block_defs_stack = VEC_alloc (tree, heap, 10); 1610 1611 /* Initialize the dominator walker. */ 1612 init_walk_dominator_tree (&walk_data); 1613 1614 /* Recursively walk the dominator tree rewriting each statement in 1615 each basic block. */ 1616 walk_dominator_tree (&walk_data, entry); 1617 1618 /* Finalize the dominator walker. */ 1619 fini_walk_dominator_tree (&walk_data); 1620 1621 /* Debugging dumps. */ 1622 if (dump_file && (dump_flags & TDF_STATS)) 1623 { 1624 dump_dfa_stats (dump_file); 1625 if (def_blocks) 1626 dump_tree_ssa_stats (dump_file); 1627 } 1628 1629 if (def_blocks) 1630 { 1631 htab_delete (def_blocks); 1632 def_blocks = NULL; 1633 } 1634 1635 VEC_free (tree, heap, block_defs_stack); 1636 1637 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS); 1638} 1639 1640 1641/* Block initialization routine for mark_def_sites. Clear the 1642 KILLS bitmap at the start of each block. */ 1643 1644static void 1645mark_def_sites_initialize_block (struct dom_walk_data *walk_data, 1646 basic_block bb ATTRIBUTE_UNUSED) 1647{ 1648 struct mark_def_sites_global_data *gd = walk_data->global_data; 1649 bitmap kills = gd->kills; 1650 bitmap_clear (kills); 1651} 1652 1653 1654/* Mark the definition site blocks for each variable, so that we know 1655 where the variable is actually live. 1656 1657 INTERESTING_BLOCKS will be filled in with all the blocks that 1658 should be processed by the renamer. It is assumed to be 1659 initialized and zeroed by the caller. */ 1660 1661static void 1662mark_def_site_blocks (sbitmap interesting_blocks) 1663{ 1664 struct dom_walk_data walk_data; 1665 struct mark_def_sites_global_data mark_def_sites_global_data; 1666 referenced_var_iterator rvi; 1667 tree var; 1668 1669 /* Allocate memory for the DEF_BLOCKS hash table. */ 1670 def_blocks = htab_create (num_referenced_vars, 1671 def_blocks_hash, def_blocks_eq, def_blocks_free); 1672 FOR_EACH_REFERENCED_VAR(var, rvi) 1673 set_current_def (var, NULL_TREE); 1674 1675 /* Setup callbacks for the generic dominator tree walker to find and 1676 mark definition sites. */ 1677 walk_data.walk_stmts_backward = false; 1678 walk_data.dom_direction = CDI_DOMINATORS; 1679 walk_data.initialize_block_local_data = NULL; 1680 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block; 1681 walk_data.before_dom_children_walk_stmts = mark_def_sites; 1682 walk_data.before_dom_children_after_stmts = NULL; 1683 walk_data.after_dom_children_before_stmts = NULL; 1684 walk_data.after_dom_children_walk_stmts = NULL; 1685 walk_data.after_dom_children_after_stmts = NULL; 1686 walk_data.interesting_blocks = NULL; 1687 1688 /* Notice that this bitmap is indexed using variable UIDs, so it must be 1689 large enough to accommodate all the variables referenced in the 1690 function, not just the ones we are renaming. */ 1691 mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL); 1692 1693 /* Create the set of interesting blocks that will be filled by 1694 mark_def_sites. */ 1695 mark_def_sites_global_data.interesting_blocks = interesting_blocks; 1696 walk_data.global_data = &mark_def_sites_global_data; 1697 1698 /* We do not have any local data. */ 1699 walk_data.block_local_data_size = 0; 1700 1701 /* Initialize the dominator walker. */ 1702 init_walk_dominator_tree (&walk_data); 1703 1704 /* Recursively walk the dominator tree. */ 1705 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 1706 1707 /* Finalize the dominator walker. */ 1708 fini_walk_dominator_tree (&walk_data); 1709 1710 /* We no longer need this bitmap, clear and free it. */ 1711 BITMAP_FREE (mark_def_sites_global_data.kills); 1712} 1713 1714 1715/* Main entry point into the SSA builder. The renaming process 1716 proceeds in four main phases: 1717 1718 1- Compute dominance frontier and immediate dominators, needed to 1719 insert PHI nodes and rename the function in dominator tree 1720 order. 1721 1722 2- Find and mark all the blocks that define variables 1723 (mark_def_site_blocks). 1724 1725 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes). 1726 1727 4- Rename all the blocks (rewrite_blocks) and statements in the program. 1728 1729 Steps 3 and 5 are done using the dominator tree walker 1730 (walk_dominator_tree). */ 1731 1732static void 1733rewrite_into_ssa (void) 1734{ 1735 bitmap *dfs; 1736 basic_block bb; 1737 sbitmap interesting_blocks; 1738 1739 timevar_push (TV_TREE_SSA_OTHER); 1740 1741 /* Initialize operand data structures. */ 1742 init_ssa_operands (); 1743 1744 /* Initialize the set of interesting blocks. The callback 1745 mark_def_sites will add to this set those blocks that the renamer 1746 should process. */ 1747 interesting_blocks = sbitmap_alloc (last_basic_block); 1748 sbitmap_zero (interesting_blocks); 1749 1750 /* Initialize dominance frontier. */ 1751 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap)); 1752 FOR_EACH_BB (bb) 1753 dfs[bb->index] = BITMAP_ALLOC (NULL); 1754 1755 /* 1- Compute dominance frontiers. */ 1756 calculate_dominance_info (CDI_DOMINATORS); 1757 compute_dominance_frontiers (dfs); 1758 1759 /* 2- Find and mark definition sites. */ 1760 mark_def_site_blocks (interesting_blocks); 1761 1762 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */ 1763 insert_phi_nodes (dfs); 1764 1765 /* 4- Rename all the blocks. */ 1766 rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks); 1767 1768 /* Free allocated memory. */ 1769 FOR_EACH_BB (bb) 1770 BITMAP_FREE (dfs[bb->index]); 1771 free (dfs); 1772 sbitmap_free (interesting_blocks); 1773 1774 timevar_pop (TV_TREE_SSA_OTHER); 1775 in_ssa_p = true; 1776} 1777 1778 1779struct tree_opt_pass pass_build_ssa = 1780{ 1781 "ssa", /* name */ 1782 NULL, /* gate */ 1783 rewrite_into_ssa, /* execute */ 1784 NULL, /* sub */ 1785 NULL, /* next */ 1786 0, /* static_pass_number */ 1787 0, /* tv_id */ 1788 PROP_cfg | PROP_referenced_vars, /* properties_required */ 1789 PROP_ssa, /* properties_provided */ 1790 0, /* properties_destroyed */ 1791 0, /* todo_flags_start */ 1792 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ 1793 0 /* letter */ 1794}; 1795 1796 1797/* Mark the definition of VAR at STMT and BB as interesting for the 1798 renamer. BLOCKS is the set of blocks that need updating. */ 1799 1800static void 1801mark_def_interesting (tree var, tree stmt, basic_block bb, bitmap blocks, 1802 bool insert_phi_p) 1803{ 1804 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1; 1805 bitmap_set_bit (blocks, bb->index); 1806 1807 if (insert_phi_p) 1808 { 1809 bool is_phi_p = TREE_CODE (stmt) == PHI_NODE; 1810 1811 set_def_block (var, bb, is_phi_p); 1812 1813 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition 1814 site for both itself and all the old names replaced by it. */ 1815 if (TREE_CODE (var) == SSA_NAME && is_new_name (var)) 1816 { 1817 bitmap_iterator bi; 1818 unsigned i; 1819 bitmap set = names_replaced_by (var); 1820 if (set) 1821 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 1822 set_def_block (ssa_name (i), bb, is_phi_p); 1823 } 1824 } 1825} 1826 1827 1828/* Mark the use of VAR at STMT and BB as interesting for the 1829 renamer. INSERT_PHI_P is true if we are going to insert new PHI 1830 nodes. BLOCKS is the set of blocks that need updating. */ 1831 1832static inline void 1833mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks, 1834 bool insert_phi_p) 1835{ 1836 REWRITE_THIS_STMT (stmt) = 1; 1837 bitmap_set_bit (blocks, bb->index); 1838 1839 /* If VAR has not been defined in BB, then it is live-on-entry 1840 to BB. Note that we cannot just use the block holding VAR's 1841 definition because if VAR is one of the names in OLD_SSA_NAMES, 1842 it will have several definitions (itself and all the names that 1843 replace it). */ 1844 if (insert_phi_p) 1845 { 1846 struct def_blocks_d *db_p = get_def_blocks_for (var); 1847 if (!bitmap_bit_p (db_p->def_blocks, bb->index)) 1848 set_livein_block (var, bb); 1849 } 1850} 1851 1852 1853/* Do a dominator walk starting at BB processing statements that 1854 reference symbols in SYMS_TO_RENAME. This is very similar to 1855 mark_def_sites, but the scan handles statements whose operands may 1856 already be SSA names. Blocks that contain defs or uses of symbols 1857 in SYMS_TO_RENAME are added to BLOCKS. 1858 1859 If INSERT_PHI_P is true, mark those uses as live in the 1860 corresponding block. This is later used by the PHI placement 1861 algorithm to make PHI pruning decisions. */ 1862 1863static void 1864prepare_block_for_update (basic_block bb, bitmap blocks, bool insert_phi_p) 1865{ 1866 basic_block son; 1867 block_stmt_iterator si; 1868 tree phi; 1869 1870 /* Process PHI nodes marking interesting those that define or use 1871 the symbols that we are interested in. */ 1872 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1873 { 1874 tree lhs_sym, lhs = PHI_RESULT (phi); 1875 1876 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs); 1877 1878 if (symbol_marked_for_renaming (lhs_sym)) 1879 { 1880 mark_use_interesting (lhs_sym, phi, bb, blocks, insert_phi_p); 1881 mark_def_interesting (lhs_sym, phi, bb, blocks, insert_phi_p); 1882 } 1883 } 1884 1885 /* Process the statements. */ 1886 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 1887 { 1888 tree stmt; 1889 ssa_op_iter i; 1890 use_operand_p use_p; 1891 def_operand_p def_p; 1892 1893 stmt = bsi_stmt (si); 1894 1895 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE) 1896 { 1897 tree use = USE_FROM_PTR (use_p); 1898 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 1899 if (symbol_marked_for_renaming (sym)) 1900 mark_use_interesting (use, stmt, bb, blocks, insert_phi_p); 1901 } 1902 1903 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF) 1904 { 1905 tree def = DEF_FROM_PTR (def_p); 1906 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 1907 1908 if (symbol_marked_for_renaming (sym)) 1909 mark_def_interesting (def, stmt, bb, blocks, insert_phi_p); 1910 } 1911 1912 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS) 1913 { 1914 tree def = DEF_FROM_PTR (def_p); 1915 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 1916 1917 if (symbol_marked_for_renaming (sym)) 1918 { 1919 mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p); 1920 mark_def_interesting (sym, stmt, bb, blocks, insert_phi_p); 1921 } 1922 } 1923 1924 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE) 1925 { 1926 tree use = USE_FROM_PTR (use_p); 1927 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 1928 1929 if (symbol_marked_for_renaming (sym)) 1930 mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p); 1931 } 1932 } 1933 1934 /* Now visit all the blocks dominated by BB. */ 1935 for (son = first_dom_son (CDI_DOMINATORS, bb); 1936 son; 1937 son = next_dom_son (CDI_DOMINATORS, son)) 1938 prepare_block_for_update (son, blocks, insert_phi_p); 1939} 1940 1941 1942/* Helper for prepare_names_to_update. Mark all the use sites for 1943 NAME as interesting. BLOCKS and INSERT_PHI_P are as in 1944 prepare_names_to_update. */ 1945 1946static void 1947prepare_use_sites_for (tree name, bitmap blocks, bool insert_phi_p) 1948{ 1949 use_operand_p use_p; 1950 imm_use_iterator iter; 1951 1952 FOR_EACH_IMM_USE_FAST (use_p, iter, name) 1953 { 1954 tree stmt = USE_STMT (use_p); 1955 basic_block bb = bb_for_stmt (stmt); 1956 1957 if (TREE_CODE (stmt) == PHI_NODE) 1958 { 1959 /* Mark this use of NAME interesting for the renamer. 1960 Notice that we explicitly call mark_use_interesting with 1961 INSERT_PHI_P == false. 1962 1963 This is to avoid marking NAME as live-in in this block 1964 BB. If we were to mark NAME live-in to BB, then NAME 1965 would be considered live-in through ALL incoming edges to 1966 BB which is not what we want. Since we are updating the 1967 SSA form for NAME, we don't really know what other names 1968 of NAME are coming in through other edges into BB. 1969 1970 If we considered NAME live-in at BB, then the PHI 1971 placement algorithm may try to insert PHI nodes in blocks 1972 that are not only unnecessary but also the renamer would 1973 not know how to fill in. */ 1974 mark_use_interesting (name, stmt, bb, blocks, false); 1975 1976 /* As discussed above, we only want to mark NAME live-in 1977 through the edge corresponding to its slot inside the PHI 1978 argument list. So, we look for the block BB1 where NAME 1979 is flowing through. If BB1 does not contain a definition 1980 of NAME, then consider NAME live-in at BB1. */ 1981 if (insert_phi_p) 1982 { 1983 int ix = PHI_ARG_INDEX_FROM_USE (use_p); 1984 edge e = PHI_ARG_EDGE (stmt, ix); 1985 basic_block bb1 = e->src; 1986 struct def_blocks_d *db = get_def_blocks_for (name); 1987 1988 if (!bitmap_bit_p (db->def_blocks, bb1->index)) 1989 set_livein_block (name, bb1); 1990 } 1991 } 1992 else 1993 { 1994 /* For regular statements, mark this as an interesting use 1995 for NAME. */ 1996 mark_use_interesting (name, stmt, bb, blocks, insert_phi_p); 1997 } 1998 } 1999} 2000 2001 2002/* Helper for prepare_names_to_update. Mark the definition site for 2003 NAME as interesting. BLOCKS and INSERT_PHI_P are as in 2004 prepare_names_to_update. */ 2005 2006static void 2007prepare_def_site_for (tree name, bitmap blocks, bool insert_phi_p) 2008{ 2009 tree stmt; 2010 basic_block bb; 2011 2012 gcc_assert (names_to_release == NULL 2013 || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name))); 2014 2015 stmt = SSA_NAME_DEF_STMT (name); 2016 bb = bb_for_stmt (stmt); 2017 if (bb) 2018 { 2019 gcc_assert (bb->index < last_basic_block); 2020 mark_def_interesting (name, stmt, bb, blocks, insert_phi_p); 2021 } 2022} 2023 2024 2025/* Mark definition and use sites of names in NEW_SSA_NAMES and 2026 OLD_SSA_NAMES. Add each definition block to BLOCKS. INSERT_PHI_P 2027 is true if the caller wants to insert PHI nodes for newly created 2028 names. */ 2029 2030static void 2031prepare_names_to_update (bitmap blocks, bool insert_phi_p) 2032{ 2033 unsigned i = 0; 2034 bitmap_iterator bi; 2035 sbitmap_iterator sbi; 2036 2037 /* If a name N from NEW_SSA_NAMES is also marked to be released, 2038 remove it from NEW_SSA_NAMES so that we don't try to visit its 2039 defining basic block (which most likely doesn't exist). Notice 2040 that we cannot do the same with names in OLD_SSA_NAMES because we 2041 want to replace existing instances. */ 2042 if (names_to_release) 2043 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2044 RESET_BIT (new_ssa_names, i); 2045 2046 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old 2047 names may be considered to be live-in on blocks that contain 2048 definitions for their replacements. */ 2049 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi) 2050 prepare_def_site_for (ssa_name (i), blocks, insert_phi_p); 2051 2052 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from 2053 OLD_SSA_NAMES, but we have to ignore its definition site. */ 2054 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2055 { 2056 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i)) 2057 prepare_def_site_for (ssa_name (i), blocks, insert_phi_p); 2058 prepare_use_sites_for (ssa_name (i), blocks, insert_phi_p); 2059 } 2060} 2061 2062 2063/* Dump all the names replaced by NAME to FILE. */ 2064 2065void 2066dump_names_replaced_by (FILE *file, tree name) 2067{ 2068 unsigned i; 2069 bitmap old_set; 2070 bitmap_iterator bi; 2071 2072 print_generic_expr (file, name, 0); 2073 fprintf (file, " -> { "); 2074 2075 old_set = names_replaced_by (name); 2076 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi) 2077 { 2078 print_generic_expr (file, ssa_name (i), 0); 2079 fprintf (file, " "); 2080 } 2081 2082 fprintf (file, "}\n"); 2083} 2084 2085 2086/* Dump all the names replaced by NAME to stderr. */ 2087 2088void 2089debug_names_replaced_by (tree name) 2090{ 2091 dump_names_replaced_by (stderr, name); 2092} 2093 2094 2095/* Dump SSA update information to FILE. */ 2096 2097void 2098dump_update_ssa (FILE *file) 2099{ 2100 unsigned i = 0; 2101 bitmap_iterator bi; 2102 2103 if (!need_ssa_update_p ()) 2104 return; 2105 2106 if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0) 2107 { 2108 sbitmap_iterator sbi; 2109 2110 fprintf (file, "\nSSA replacement table\n"); 2111 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces " 2112 "O_1, ..., O_j\n\n"); 2113 2114 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi) 2115 dump_names_replaced_by (file, ssa_name (i)); 2116 2117 fprintf (file, "\n"); 2118 fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n", 2119 update_ssa_stats.num_virtual_mappings); 2120 fprintf (file, "Number of real NEW -> OLD mappings: %7u\n", 2121 update_ssa_stats.num_total_mappings 2122 - update_ssa_stats.num_virtual_mappings); 2123 fprintf (file, "Number of total NEW -> OLD mappings: %7u\n", 2124 update_ssa_stats.num_total_mappings); 2125 2126 fprintf (file, "\nNumber of virtual symbols: %u\n", 2127 update_ssa_stats.num_virtual_symbols); 2128 } 2129 2130 if (syms_to_rename && !bitmap_empty_p (syms_to_rename)) 2131 { 2132 fprintf (file, "\n\nSymbols to be put in SSA form\n\n"); 2133 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi) 2134 { 2135 print_generic_expr (file, referenced_var (i), 0); 2136 fprintf (file, " "); 2137 } 2138 } 2139 2140 if (names_to_release && !bitmap_empty_p (names_to_release)) 2141 { 2142 fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n"); 2143 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2144 { 2145 print_generic_expr (file, ssa_name (i), 0); 2146 fprintf (file, " "); 2147 } 2148 } 2149 2150 fprintf (file, "\n\n"); 2151} 2152 2153 2154/* Dump SSA update information to stderr. */ 2155 2156void 2157debug_update_ssa (void) 2158{ 2159 dump_update_ssa (stderr); 2160} 2161 2162 2163/* Initialize data structures used for incremental SSA updates. */ 2164 2165static void 2166init_update_ssa (void) 2167{ 2168 /* Reserve more space than the current number of names. The calls to 2169 add_new_name_mapping are typically done after creating new SSA 2170 names, so we'll need to reallocate these arrays. */ 2171 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR); 2172 sbitmap_zero (old_ssa_names); 2173 2174 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR); 2175 sbitmap_zero (new_ssa_names); 2176 2177 repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free); 2178 need_to_initialize_update_ssa_p = false; 2179 need_to_update_vops_p = false; 2180 syms_to_rename = BITMAP_ALLOC (NULL); 2181 names_to_release = NULL; 2182 memset (&update_ssa_stats, 0, sizeof (update_ssa_stats)); 2183 update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL); 2184} 2185 2186 2187/* Deallocate data structures used for incremental SSA updates. */ 2188 2189void 2190delete_update_ssa (void) 2191{ 2192 unsigned i; 2193 bitmap_iterator bi; 2194 2195 sbitmap_free (old_ssa_names); 2196 old_ssa_names = NULL; 2197 2198 sbitmap_free (new_ssa_names); 2199 new_ssa_names = NULL; 2200 2201 htab_delete (repl_tbl); 2202 repl_tbl = NULL; 2203 2204 need_to_initialize_update_ssa_p = true; 2205 need_to_update_vops_p = false; 2206 BITMAP_FREE (syms_to_rename); 2207 BITMAP_FREE (update_ssa_stats.virtual_symbols); 2208 2209 if (names_to_release) 2210 { 2211 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2212 release_ssa_name (ssa_name (i)); 2213 BITMAP_FREE (names_to_release); 2214 } 2215 2216 for (i = 1; i < num_ssa_names; i++) 2217 { 2218 tree n = ssa_name (i); 2219 2220 if (n) 2221 { 2222 free (SSA_NAME_AUX (n)); 2223 SSA_NAME_AUX (n) = NULL; 2224 } 2225 } 2226} 2227 2228 2229/* Create a new name for OLD_NAME in statement STMT and replace the 2230 operand pointed to by DEF_P with the newly created name. Return 2231 the new name and register the replacement mapping <NEW, OLD> in 2232 update_ssa's tables. */ 2233 2234tree 2235create_new_def_for (tree old_name, tree stmt, def_operand_p def) 2236{ 2237 tree new_name = duplicate_ssa_name (old_name, stmt); 2238 2239 SET_DEF (def, new_name); 2240 2241 if (TREE_CODE (stmt) == PHI_NODE) 2242 { 2243 edge e; 2244 edge_iterator ei; 2245 basic_block bb = bb_for_stmt (stmt); 2246 2247 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */ 2248 FOR_EACH_EDGE (e, ei, bb->preds) 2249 if (e->flags & EDGE_ABNORMAL) 2250 { 2251 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1; 2252 break; 2253 } 2254 } 2255 2256 register_new_name_mapping (new_name, old_name); 2257 2258 /* For the benefit of passes that will be updating the SSA form on 2259 their own, set the current reaching definition of OLD_NAME to be 2260 NEW_NAME. */ 2261 set_current_def (old_name, new_name); 2262 2263 return new_name; 2264} 2265 2266 2267/* Register name NEW to be a replacement for name OLD. This function 2268 must be called for every replacement that should be performed by 2269 update_ssa. */ 2270 2271void 2272register_new_name_mapping (tree new, tree old) 2273{ 2274 if (need_to_initialize_update_ssa_p) 2275 init_update_ssa (); 2276 2277 add_new_name_mapping (new, old); 2278} 2279 2280 2281/* Register symbol SYM to be renamed by update_ssa. */ 2282 2283void 2284mark_sym_for_renaming (tree sym) 2285{ 2286 if (need_to_initialize_update_ssa_p) 2287 init_update_ssa (); 2288 2289 bitmap_set_bit (syms_to_rename, DECL_UID (sym)); 2290 2291 if (!is_gimple_reg (sym)) 2292 need_to_update_vops_p = true; 2293} 2294 2295 2296/* Register all the symbols in SET to be renamed by update_ssa. */ 2297 2298void 2299mark_set_for_renaming (bitmap set) 2300{ 2301 bitmap_iterator bi; 2302 unsigned i; 2303 2304 if (bitmap_empty_p (set)) 2305 return; 2306 2307 if (need_to_initialize_update_ssa_p) 2308 init_update_ssa (); 2309 2310 bitmap_ior_into (syms_to_rename, set); 2311 2312 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 2313 if (!is_gimple_reg (referenced_var (i))) 2314 { 2315 need_to_update_vops_p = true; 2316 break; 2317 } 2318} 2319 2320 2321/* Return true if there is any work to be done by update_ssa. */ 2322 2323bool 2324need_ssa_update_p (void) 2325{ 2326 return syms_to_rename || old_ssa_names || new_ssa_names; 2327} 2328 2329 2330/* Return true if name N has been registered in the replacement table. */ 2331 2332bool 2333name_registered_for_update_p (tree n) 2334{ 2335 if (!need_ssa_update_p ()) 2336 return false; 2337 2338 return is_new_name (n) 2339 || is_old_name (n) 2340 || symbol_marked_for_renaming (SSA_NAME_VAR (n)); 2341} 2342 2343 2344/* Return the set of all the SSA names marked to be replaced. */ 2345 2346bitmap 2347ssa_names_to_replace (void) 2348{ 2349 unsigned i = 0; 2350 bitmap ret; 2351 sbitmap_iterator sbi; 2352 2353 ret = BITMAP_ALLOC (NULL); 2354 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2355 bitmap_set_bit (ret, i); 2356 2357 return ret; 2358} 2359 2360 2361/* Mark NAME to be released after update_ssa has finished. */ 2362 2363void 2364release_ssa_name_after_update_ssa (tree name) 2365{ 2366 gcc_assert (!need_to_initialize_update_ssa_p); 2367 2368 if (names_to_release == NULL) 2369 names_to_release = BITMAP_ALLOC (NULL); 2370 2371 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name)); 2372} 2373 2374 2375/* Insert new PHI nodes to replace VAR. DFS contains dominance 2376 frontier information. BLOCKS is the set of blocks to be updated. 2377 2378 This is slightly different than the regular PHI insertion 2379 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for 2380 real names (i.e., GIMPLE registers) are inserted: 2381 2382 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI 2383 nodes inside the region affected by the block that defines VAR 2384 and the blocks that define all its replacements. All these 2385 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS. 2386 2387 First, we compute the entry point to the region (ENTRY). This is 2388 given by the nearest common dominator to all the definition 2389 blocks. When computing the iterated dominance frontier (IDF), any 2390 block not strictly dominated by ENTRY is ignored. 2391 2392 We then call the standard PHI insertion algorithm with the pruned 2393 IDF. 2394 2395 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real 2396 names is not pruned. PHI nodes are inserted at every IDF block. */ 2397 2398static void 2399insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks, 2400 unsigned update_flags) 2401{ 2402 basic_block entry; 2403 struct def_blocks_d *db; 2404 bitmap idf, pruned_idf; 2405 bitmap_iterator bi; 2406 unsigned i; 2407 2408#if defined ENABLE_CHECKING 2409 if (TREE_CODE (var) == SSA_NAME) 2410 gcc_assert (is_old_name (var)); 2411 else 2412 gcc_assert (symbol_marked_for_renaming (var)); 2413#endif 2414 2415 /* Get all the definition sites for VAR. */ 2416 db = find_def_blocks_for (var); 2417 2418 /* No need to do anything if there were no definitions to VAR. */ 2419 if (db == NULL || bitmap_empty_p (db->def_blocks)) 2420 return; 2421 2422 /* Compute the initial iterated dominance frontier. */ 2423 idf = find_idf (db->def_blocks, dfs); 2424 pruned_idf = BITMAP_ALLOC (NULL); 2425 2426 if (TREE_CODE (var) == SSA_NAME) 2427 { 2428 if (update_flags == TODO_update_ssa) 2429 { 2430 /* If doing regular SSA updates for GIMPLE registers, we are 2431 only interested in IDF blocks dominated by the nearest 2432 common dominator of all the definition blocks. */ 2433 entry = nearest_common_dominator_for_set (CDI_DOMINATORS, 2434 db->def_blocks); 2435 2436 if (entry != ENTRY_BLOCK_PTR) 2437 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi) 2438 if (BASIC_BLOCK (i) != entry 2439 && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry)) 2440 bitmap_set_bit (pruned_idf, i); 2441 } 2442 else 2443 { 2444 /* Otherwise, do not prune the IDF for VAR. */ 2445 gcc_assert (update_flags == TODO_update_ssa_full_phi); 2446 bitmap_copy (pruned_idf, idf); 2447 } 2448 } 2449 else 2450 { 2451 /* Otherwise, VAR is a symbol that needs to be put into SSA form 2452 for the first time, so we need to compute the full IDF for 2453 it. */ 2454 bitmap_copy (pruned_idf, idf); 2455 } 2456 2457 if (!bitmap_empty_p (pruned_idf)) 2458 { 2459 /* Make sure that PRUNED_IDF blocks and all their feeding blocks 2460 are included in the region to be updated. The feeding blocks 2461 are important to guarantee that the PHI arguments are renamed 2462 properly. */ 2463 bitmap_ior_into (blocks, pruned_idf); 2464 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi) 2465 { 2466 edge e; 2467 edge_iterator ei; 2468 basic_block bb = BASIC_BLOCK (i); 2469 2470 FOR_EACH_EDGE (e, ei, bb->preds) 2471 if (e->src->index >= 0) 2472 bitmap_set_bit (blocks, e->src->index); 2473 } 2474 2475 insert_phi_nodes_for (var, pruned_idf, true); 2476 } 2477 2478 BITMAP_FREE (pruned_idf); 2479 BITMAP_FREE (idf); 2480} 2481 2482 2483/* Heuristic to determine whether SSA name mappings for virtual names 2484 should be discarded and their symbols rewritten from scratch. When 2485 there is a large number of mappings for virtual names, the 2486 insertion of PHI nodes for the old names in the mappings takes 2487 considerable more time than if we inserted PHI nodes for the 2488 symbols instead. 2489 2490 Currently the heuristic takes these stats into account: 2491 2492 - Number of mappings for virtual SSA names. 2493 - Number of distinct virtual symbols involved in those mappings. 2494 2495 If the number of virtual mappings is much larger than the number of 2496 virtual symbols, then it will be faster to compute PHI insertion 2497 spots for the symbols. Even if this involves traversing the whole 2498 CFG, which is what happens when symbols are renamed from scratch. */ 2499 2500static bool 2501switch_virtuals_to_full_rewrite_p (void) 2502{ 2503 if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS) 2504 return false; 2505 2506 if (update_ssa_stats.num_virtual_mappings 2507 > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO 2508 * update_ssa_stats.num_virtual_symbols) 2509 return true; 2510 2511 return false; 2512} 2513 2514 2515/* Remove every virtual mapping and mark all the affected virtual 2516 symbols for renaming. */ 2517 2518static void 2519switch_virtuals_to_full_rewrite (void) 2520{ 2521 unsigned i = 0; 2522 sbitmap_iterator sbi; 2523 2524 if (dump_file) 2525 { 2526 fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n"); 2527 fprintf (dump_file, "\tNumber of virtual mappings: %7u\n", 2528 update_ssa_stats.num_virtual_mappings); 2529 fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n", 2530 update_ssa_stats.num_virtual_symbols); 2531 fprintf (dump_file, "Updating FUD-chains from top of CFG will be " 2532 "faster than processing\nthe name mappings.\n\n"); 2533 } 2534 2535 /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES. 2536 Note that it is not really necessary to remove the mappings from 2537 REPL_TBL, that would only waste time. */ 2538 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi) 2539 if (!is_gimple_reg (ssa_name (i))) 2540 RESET_BIT (new_ssa_names, i); 2541 2542 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2543 if (!is_gimple_reg (ssa_name (i))) 2544 RESET_BIT (old_ssa_names, i); 2545 2546 bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols); 2547} 2548 2549 2550/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of 2551 existing SSA names (OLD_SSA_NAMES), update the SSA form so that: 2552 2553 1- The names in OLD_SSA_NAMES dominated by the definitions of 2554 NEW_SSA_NAMES are all re-written to be reached by the 2555 appropriate definition from NEW_SSA_NAMES. 2556 2557 2- If needed, new PHI nodes are added to the iterated dominance 2558 frontier of the blocks where each of NEW_SSA_NAMES are defined. 2559 2560 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by 2561 calling register_new_name_mapping for every pair of names that the 2562 caller wants to replace. 2563 2564 The caller identifies the new names that have been inserted and the 2565 names that need to be replaced by calling register_new_name_mapping 2566 for every pair <NEW, OLD>. Note that the function assumes that the 2567 new names have already been inserted in the IL. 2568 2569 For instance, given the following code: 2570 2571 1 L0: 2572 2 x_1 = PHI (0, x_5) 2573 3 if (x_1 < 10) 2574 4 if (x_1 > 7) 2575 5 y_2 = 0 2576 6 else 2577 7 y_3 = x_1 + x_7 2578 8 endif 2579 9 x_5 = x_1 + 1 2580 10 goto L0; 2581 11 endif 2582 2583 Suppose that we insert new names x_10 and x_11 (lines 4 and 8). 2584 2585 1 L0: 2586 2 x_1 = PHI (0, x_5) 2587 3 if (x_1 < 10) 2588 4 x_10 = ... 2589 5 if (x_1 > 7) 2590 6 y_2 = 0 2591 7 else 2592 8 x_11 = ... 2593 9 y_3 = x_1 + x_7 2594 10 endif 2595 11 x_5 = x_1 + 1 2596 12 goto L0; 2597 13 endif 2598 2599 We want to replace all the uses of x_1 with the new definitions of 2600 x_10 and x_11. Note that the only uses that should be replaced are 2601 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should 2602 *not* be replaced (this is why we cannot just mark symbol 'x' for 2603 renaming). 2604 2605 Additionally, we may need to insert a PHI node at line 11 because 2606 that is a merge point for x_10 and x_11. So the use of x_1 at line 2607 11 will be replaced with the new PHI node. The insertion of PHI 2608 nodes is optional. They are not strictly necessary to preserve the 2609 SSA form, and depending on what the caller inserted, they may not 2610 even be useful for the optimizers. UPDATE_FLAGS controls various 2611 aspects of how update_ssa operates, see the documentation for 2612 TODO_update_ssa*. */ 2613 2614void 2615update_ssa (unsigned update_flags) 2616{ 2617 bitmap blocks; 2618 basic_block bb, start_bb; 2619 bitmap_iterator bi; 2620 unsigned i = 0; 2621 sbitmap tmp; 2622 bool insert_phi_p; 2623 sbitmap_iterator sbi; 2624 2625 if (!need_ssa_update_p ()) 2626 return; 2627 2628 timevar_push (TV_TREE_SSA_INCREMENTAL); 2629 2630 /* Ensure that the dominance information is up-to-date. */ 2631 calculate_dominance_info (CDI_DOMINATORS); 2632 2633 /* Only one update flag should be set. */ 2634 gcc_assert (update_flags == TODO_update_ssa 2635 || update_flags == TODO_update_ssa_no_phi 2636 || update_flags == TODO_update_ssa_full_phi 2637 || update_flags == TODO_update_ssa_only_virtuals); 2638 2639 /* If we only need to update virtuals, remove all the mappings for 2640 real names before proceeding. The caller is responsible for 2641 having dealt with the name mappings before calling update_ssa. */ 2642 if (update_flags == TODO_update_ssa_only_virtuals) 2643 { 2644 sbitmap_zero (old_ssa_names); 2645 sbitmap_zero (new_ssa_names); 2646 htab_empty (repl_tbl); 2647 } 2648 2649 insert_phi_p = (update_flags != TODO_update_ssa_no_phi); 2650 2651 if (insert_phi_p) 2652 { 2653 /* If the caller requested PHI nodes to be added, initialize 2654 live-in information data structures (DEF_BLOCKS). */ 2655 2656 /* For each SSA name N, the DEF_BLOCKS table describes where the 2657 name is defined, which blocks have PHI nodes for N, and which 2658 blocks have uses of N (i.e., N is live-on-entry in those 2659 blocks). */ 2660 def_blocks = htab_create (num_ssa_names, def_blocks_hash, 2661 def_blocks_eq, def_blocks_free); 2662 } 2663 else 2664 { 2665 def_blocks = NULL; 2666 } 2667 2668 blocks = BITMAP_ALLOC (NULL); 2669 2670 /* Clear the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags 2671 for every statement and PHI node. */ 2672 FOR_EACH_BB (bb) 2673 { 2674 block_stmt_iterator si; 2675 tree phi; 2676 2677 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2678 { 2679 REWRITE_THIS_STMT (phi) = 0; 2680 REGISTER_DEFS_IN_THIS_STMT (phi) = 0; 2681 } 2682 2683 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 2684 { 2685 tree stmt = bsi_stmt (si); 2686 /* We are going to use the operand cache API, such as 2687 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand 2688 cache for each statement should be up-to-date. */ 2689 gcc_assert (!stmt_modified_p (stmt)); 2690 REWRITE_THIS_STMT (stmt) = 0; 2691 REGISTER_DEFS_IN_THIS_STMT (stmt) = 0; 2692 } 2693 } 2694 2695 /* Heuristic to avoid massive slow downs when the replacement 2696 mappings include lots of virtual names. */ 2697 if (insert_phi_p && switch_virtuals_to_full_rewrite_p ()) 2698 switch_virtuals_to_full_rewrite (); 2699 2700 /* If there are names defined in the replacement table, prepare 2701 definition and use sites for all the names in NEW_SSA_NAMES and 2702 OLD_SSA_NAMES. */ 2703 if (sbitmap_first_set_bit (new_ssa_names) >= 0) 2704 { 2705 prepare_names_to_update (blocks, insert_phi_p); 2706 2707 /* If all the names in NEW_SSA_NAMES had been marked for 2708 removal, and there are no symbols to rename, then there's 2709 nothing else to do. */ 2710 if (sbitmap_first_set_bit (new_ssa_names) < 0 2711 && bitmap_empty_p (syms_to_rename)) 2712 goto done; 2713 } 2714 2715 /* Next, determine the block at which to start the renaming process. */ 2716 if (!bitmap_empty_p (syms_to_rename)) 2717 { 2718 /* If we have to rename some symbols from scratch, we need to 2719 start the process at the root of the CFG. FIXME, it should 2720 be possible to determine the nearest block that had a 2721 definition for each of the symbols that are marked for 2722 updating. For now this seems more work than it's worth. */ 2723 start_bb = ENTRY_BLOCK_PTR; 2724 2725 /* Traverse the CFG looking for definitions and uses of symbols 2726 in SYMS_TO_RENAME. Mark interesting blocks and statements 2727 and set local live-in information for the PHI placement 2728 heuristics. */ 2729 prepare_block_for_update (start_bb, blocks, insert_phi_p); 2730 } 2731 else 2732 { 2733 /* Otherwise, the entry block to the region is the nearest 2734 common dominator for the blocks in BLOCKS. */ 2735 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks); 2736 } 2737 2738 /* If requested, insert PHI nodes at the iterated dominance frontier 2739 of every block, creating new definitions for names in OLD_SSA_NAMES 2740 and for symbols in SYMS_TO_RENAME. */ 2741 if (insert_phi_p) 2742 { 2743 bitmap *dfs; 2744 2745 /* If the caller requested PHI nodes to be added, compute 2746 dominance frontiers. */ 2747 dfs = xmalloc (last_basic_block * sizeof (bitmap)); 2748 FOR_EACH_BB (bb) 2749 dfs[bb->index] = BITMAP_ALLOC (NULL); 2750 compute_dominance_frontiers (dfs); 2751 2752 if (sbitmap_first_set_bit (old_ssa_names) >= 0) 2753 { 2754 sbitmap_iterator sbi; 2755 2756 /* insert_update_phi_nodes_for will call add_new_name_mapping 2757 when inserting new PHI nodes, so the set OLD_SSA_NAMES 2758 will grow while we are traversing it (but it will not 2759 gain any new members). Copy OLD_SSA_NAMES to a temporary 2760 for traversal. */ 2761 sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits); 2762 sbitmap_copy (tmp, old_ssa_names); 2763 EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi) 2764 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks, 2765 update_flags); 2766 sbitmap_free (tmp); 2767 } 2768 2769 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi) 2770 insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks, 2771 update_flags); 2772 2773 FOR_EACH_BB (bb) 2774 BITMAP_FREE (dfs[bb->index]); 2775 free (dfs); 2776 2777 /* Insertion of PHI nodes may have added blocks to the region. 2778 We need to re-compute START_BB to include the newly added 2779 blocks. */ 2780 if (start_bb != ENTRY_BLOCK_PTR) 2781 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks); 2782 } 2783 2784 /* Reset the current definition for name and symbol before renaming 2785 the sub-graph. */ 2786 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi) 2787 set_current_def (ssa_name (i), NULL_TREE); 2788 2789 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi) 2790 set_current_def (referenced_var (i), NULL_TREE); 2791 2792 /* Now start the renaming process at START_BB. */ 2793 tmp = sbitmap_alloc (last_basic_block); 2794 sbitmap_zero (tmp); 2795 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 2796 SET_BIT (tmp, i); 2797 2798 rewrite_blocks (start_bb, REWRITE_UPDATE, tmp); 2799 2800 sbitmap_free (tmp); 2801 2802 /* Debugging dumps. */ 2803 if (dump_file) 2804 { 2805 int c; 2806 unsigned i; 2807 2808 dump_update_ssa (dump_file); 2809 2810 fprintf (dump_file, "Incremental SSA update started at block: %d\n\n", 2811 start_bb->index); 2812 2813 c = 0; 2814 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 2815 c++; 2816 fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block); 2817 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n", 2818 c, PERCENT (c, last_basic_block)); 2819 2820 if (dump_flags & TDF_DETAILS) 2821 { 2822 fprintf (dump_file, "Affected blocks: "); 2823 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 2824 fprintf (dump_file, "%u ", i); 2825 fprintf (dump_file, "\n"); 2826 } 2827 2828 fprintf (dump_file, "\n\n"); 2829 } 2830 2831 /* Free allocated memory. */ 2832done: 2833 BITMAP_FREE (blocks); 2834 delete_update_ssa (); 2835 2836 timevar_pop (TV_TREE_SSA_INCREMENTAL); 2837} 2838