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