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