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