1 /* Rewrite a program in Normal form into SSA. 2 Copyright (C) 2001-2020 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 if (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 gcc_assert (!phis.exists ()); 951 phis.create (10); 952 } 953 else 954 phis = phis_to_rewrite[idx]; 955 956 phis.safe_push (phi); 957 phis_to_rewrite[idx] = phis; 958 } 959 960 /* Insert PHI nodes for variable VAR using the iterated dominance 961 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this 962 function assumes that the caller is incrementally updating the 963 existing SSA form, in which case VAR may be an SSA name instead of 964 a symbol. 965 966 PHI_INSERTION_POINTS is updated to reflect nodes that already had a 967 PHI node for VAR. On exit, only the nodes that received a PHI node 968 for VAR will be present in PHI_INSERTION_POINTS. */ 969 970 static void 971 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p) 972 { 973 unsigned bb_index; 974 edge e; 975 gphi *phi; 976 basic_block bb; 977 bitmap_iterator bi; 978 def_blocks *def_map = find_def_blocks_for (var); 979 980 /* Remove the blocks where we already have PHI nodes for VAR. */ 981 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks); 982 983 /* Remove obviously useless phi nodes. */ 984 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks, 985 def_map->livein_blocks); 986 987 /* And insert the PHI nodes. */ 988 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi) 989 { 990 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 991 if (update_p) 992 mark_block_for_update (bb); 993 994 if (dump_file && (dump_flags & TDF_DETAILS)) 995 { 996 fprintf (dump_file, "creating PHI node in block #%d for ", bb_index); 997 print_generic_expr (dump_file, var, TDF_SLIM); 998 fprintf (dump_file, "\n"); 999 } 1000 phi = NULL; 1001 1002 if (TREE_CODE (var) == SSA_NAME) 1003 { 1004 /* If we are rewriting SSA names, create the LHS of the PHI 1005 node by duplicating VAR. This is useful in the case of 1006 pointers, to also duplicate pointer attributes (alias 1007 information, in particular). */ 1008 edge_iterator ei; 1009 tree new_lhs; 1010 1011 gcc_checking_assert (update_p); 1012 new_lhs = duplicate_ssa_name (var, NULL); 1013 phi = create_phi_node (new_lhs, bb); 1014 add_new_name_mapping (new_lhs, var); 1015 1016 /* Add VAR to every argument slot of PHI. We need VAR in 1017 every argument so that rewrite_update_phi_arguments knows 1018 which name is this PHI node replacing. If VAR is a 1019 symbol marked for renaming, this is not necessary, the 1020 renamer will use the symbol on the LHS to get its 1021 reaching definition. */ 1022 FOR_EACH_EDGE (e, ei, bb->preds) 1023 add_phi_arg (phi, var, e, UNKNOWN_LOCATION); 1024 } 1025 else 1026 { 1027 tree tracked_var; 1028 1029 gcc_checking_assert (DECL_P (var)); 1030 phi = create_phi_node (var, bb); 1031 1032 tracked_var = target_for_debug_bind (var); 1033 if (tracked_var) 1034 { 1035 gimple *note = gimple_build_debug_bind (tracked_var, 1036 PHI_RESULT (phi), 1037 phi); 1038 gimple_stmt_iterator si = gsi_after_labels (bb); 1039 gsi_insert_before (&si, note, GSI_SAME_STMT); 1040 } 1041 } 1042 1043 /* Mark this PHI node as interesting for update_ssa. */ 1044 set_register_defs (phi, true); 1045 mark_phi_for_rewrite (bb, phi); 1046 } 1047 } 1048 1049 /* Sort var_infos after DECL_UID of their var. */ 1050 1051 static int 1052 insert_phi_nodes_compare_var_infos (const void *a, const void *b) 1053 { 1054 const var_info *defa = *(var_info * const *)a; 1055 const var_info *defb = *(var_info * const *)b; 1056 if (DECL_UID (defa->var) < DECL_UID (defb->var)) 1057 return -1; 1058 else 1059 return 1; 1060 } 1061 1062 /* Insert PHI nodes at the dominance frontier of blocks with variable 1063 definitions. DFS contains the dominance frontier information for 1064 the flowgraph. */ 1065 1066 static void 1067 insert_phi_nodes (bitmap_head *dfs) 1068 { 1069 hash_table<var_info_hasher>::iterator hi; 1070 unsigned i; 1071 var_info *info; 1072 1073 timevar_push (TV_TREE_INSERT_PHI_NODES); 1074 1075 /* When the gimplifier introduces SSA names it cannot easily avoid 1076 situations where abnormal edges added by CFG construction break 1077 the use-def dominance requirement. For this case rewrite SSA 1078 names with broken use-def dominance out-of-SSA and register them 1079 for PHI insertion. We only need to do this if abnormal edges 1080 can appear in the function. */ 1081 tree name; 1082 if (cfun->calls_setjmp 1083 || cfun->has_nonlocal_label) 1084 FOR_EACH_SSA_NAME (i, name, cfun) 1085 { 1086 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 1087 if (SSA_NAME_IS_DEFAULT_DEF (name)) 1088 continue; 1089 1090 basic_block def_bb = gimple_bb (def_stmt); 1091 imm_use_iterator it; 1092 gimple *use_stmt; 1093 bool need_phis = false; 1094 FOR_EACH_IMM_USE_STMT (use_stmt, it, name) 1095 { 1096 basic_block use_bb = gimple_bb (use_stmt); 1097 if (use_bb != def_bb 1098 && ! dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)) 1099 need_phis = true; 1100 } 1101 if (need_phis) 1102 { 1103 tree var = create_tmp_reg (TREE_TYPE (name)); 1104 use_operand_p use_p; 1105 FOR_EACH_IMM_USE_STMT (use_stmt, it, name) 1106 { 1107 basic_block use_bb = gimple_bb (use_stmt); 1108 FOR_EACH_IMM_USE_ON_STMT (use_p, it) 1109 SET_USE (use_p, var); 1110 update_stmt (use_stmt); 1111 set_livein_block (var, use_bb); 1112 set_rewrite_uses (use_stmt, true); 1113 bitmap_set_bit (interesting_blocks, use_bb->index); 1114 } 1115 def_operand_p def_p; 1116 ssa_op_iter dit; 1117 FOR_EACH_SSA_DEF_OPERAND (def_p, def_stmt, dit, SSA_OP_DEF) 1118 if (DEF_FROM_PTR (def_p) == name) 1119 SET_DEF (def_p, var); 1120 update_stmt (def_stmt); 1121 set_def_block (var, def_bb, false); 1122 set_register_defs (def_stmt, true); 1123 bitmap_set_bit (interesting_blocks, def_bb->index); 1124 release_ssa_name (name); 1125 } 1126 } 1127 1128 auto_vec<var_info *> vars (var_infos->elements ()); 1129 FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi) 1130 if (info->info.need_phi_state != NEED_PHI_STATE_NO) 1131 vars.quick_push (info); 1132 1133 /* Do two stages to avoid code generation differences for UID 1134 differences but no UID ordering differences. */ 1135 vars.qsort (insert_phi_nodes_compare_var_infos); 1136 1137 FOR_EACH_VEC_ELT (vars, i, info) 1138 { 1139 bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs); 1140 insert_phi_nodes_for (info->var, idf, false); 1141 BITMAP_FREE (idf); 1142 } 1143 1144 timevar_pop (TV_TREE_INSERT_PHI_NODES); 1145 } 1146 1147 1148 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and 1149 register DEF (an SSA_NAME) to be a new definition for SYM. */ 1150 1151 static void 1152 register_new_def (tree def, tree sym) 1153 { 1154 common_info *info = get_common_info (sym); 1155 tree currdef; 1156 1157 /* If this variable is set in a single basic block and all uses are 1158 dominated by the set(s) in that single basic block, then there is 1159 no reason to record anything for this variable in the block local 1160 definition stacks. Doing so just wastes time and memory. 1161 1162 This is the same test to prune the set of variables which may 1163 need PHI nodes. So we just use that information since it's already 1164 computed and available for us to use. */ 1165 if (info->need_phi_state == NEED_PHI_STATE_NO) 1166 { 1167 info->current_def = def; 1168 return; 1169 } 1170 1171 currdef = info->current_def; 1172 1173 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose 1174 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM 1175 in the stack so that we know which symbol is being defined by 1176 this SSA name when we unwind the stack. */ 1177 if (currdef && !is_gimple_reg (sym)) 1178 block_defs_stack.safe_push (sym); 1179 1180 /* Push the current reaching definition into BLOCK_DEFS_STACK. This 1181 stack is later used by the dominator tree callbacks to restore 1182 the reaching definitions for all the variables defined in the 1183 block after a recursive visit to all its immediately dominated 1184 blocks. If there is no current reaching definition, then just 1185 record the underlying _DECL node. */ 1186 block_defs_stack.safe_push (currdef ? currdef : sym); 1187 1188 /* Set the current reaching definition for SYM to be DEF. */ 1189 info->current_def = def; 1190 } 1191 1192 1193 /* Perform a depth-first traversal of the dominator tree looking for 1194 variables to rename. BB is the block where to start searching. 1195 Renaming is a five step process: 1196 1197 1- Every definition made by PHI nodes at the start of the blocks is 1198 registered as the current definition for the corresponding variable. 1199 1200 2- Every statement in BB is rewritten. USE and VUSE operands are 1201 rewritten with their corresponding reaching definition. DEF and 1202 VDEF targets are registered as new definitions. 1203 1204 3- All the PHI nodes in successor blocks of BB are visited. The 1205 argument corresponding to BB is replaced with its current reaching 1206 definition. 1207 1208 4- Recursively rewrite every dominator child block of BB. 1209 1210 5- Restore (in reverse order) the current reaching definition for every 1211 new definition introduced in this block. This is done so that when 1212 we return from the recursive call, all the current reaching 1213 definitions are restored to the names that were valid in the 1214 dominator parent of BB. */ 1215 1216 /* Return the current definition for variable VAR. If none is found, 1217 create a new SSA name to act as the zeroth definition for VAR. */ 1218 1219 static tree 1220 get_reaching_def (tree var) 1221 { 1222 common_info *info = get_common_info (var); 1223 tree currdef; 1224 1225 /* Lookup the current reaching definition for VAR. */ 1226 currdef = info->current_def; 1227 1228 /* If there is no reaching definition for VAR, create and register a 1229 default definition for it (if needed). */ 1230 if (currdef == NULL_TREE) 1231 { 1232 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var); 1233 if (! sym) 1234 sym = create_tmp_reg (TREE_TYPE (var)); 1235 currdef = get_or_create_ssa_default_def (cfun, sym); 1236 } 1237 1238 /* Return the current reaching definition for VAR, or the default 1239 definition, if we had to create one. */ 1240 return currdef; 1241 } 1242 1243 1244 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */ 1245 1246 static void 1247 rewrite_debug_stmt_uses (gimple *stmt) 1248 { 1249 use_operand_p use_p; 1250 ssa_op_iter iter; 1251 bool update = false; 1252 1253 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) 1254 { 1255 tree var = USE_FROM_PTR (use_p), def; 1256 common_info *info = get_common_info (var); 1257 gcc_checking_assert (DECL_P (var)); 1258 def = info->current_def; 1259 if (!def) 1260 { 1261 if (TREE_CODE (var) == PARM_DECL 1262 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun))) 1263 { 1264 gimple_stmt_iterator gsi 1265 = 1266 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))); 1267 int lim; 1268 /* Search a few source bind stmts at the start of first bb to 1269 see if a DEBUG_EXPR_DECL can't be reused. */ 1270 for (lim = 32; 1271 !gsi_end_p (gsi) && lim > 0; 1272 gsi_next (&gsi), lim--) 1273 { 1274 gimple *gstmt = gsi_stmt (gsi); 1275 if (!gimple_debug_source_bind_p (gstmt)) 1276 break; 1277 if (gimple_debug_source_bind_get_value (gstmt) == var) 1278 { 1279 def = gimple_debug_source_bind_get_var (gstmt); 1280 if (TREE_CODE (def) == DEBUG_EXPR_DECL) 1281 break; 1282 else 1283 def = NULL_TREE; 1284 } 1285 } 1286 /* If not, add a new source bind stmt. */ 1287 if (def == NULL_TREE) 1288 { 1289 gimple *def_temp; 1290 def = make_node (DEBUG_EXPR_DECL); 1291 def_temp = gimple_build_debug_source_bind (def, var, NULL); 1292 DECL_ARTIFICIAL (def) = 1; 1293 TREE_TYPE (def) = TREE_TYPE (var); 1294 SET_DECL_MODE (def, DECL_MODE (var)); 1295 gsi = 1296 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))); 1297 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT); 1298 } 1299 update = true; 1300 } 1301 } 1302 else 1303 { 1304 /* Check if info->current_def can be trusted. */ 1305 basic_block bb = gimple_bb (stmt); 1306 basic_block def_bb 1307 = SSA_NAME_IS_DEFAULT_DEF (def) 1308 ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def)); 1309 1310 /* If definition is in current bb, it is fine. */ 1311 if (bb == def_bb) 1312 ; 1313 /* If definition bb doesn't dominate the current bb, 1314 it can't be used. */ 1315 else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 1316 def = NULL; 1317 /* If there is just one definition and dominates the current 1318 bb, it is fine. */ 1319 else if (info->need_phi_state == NEED_PHI_STATE_NO) 1320 ; 1321 else 1322 { 1323 def_blocks *db_p = get_def_blocks_for (info); 1324 1325 /* If there are some non-debug uses in the current bb, 1326 it is fine. */ 1327 if (bitmap_bit_p (db_p->livein_blocks, bb->index)) 1328 ; 1329 /* Otherwise give up for now. */ 1330 else 1331 def = NULL; 1332 } 1333 } 1334 if (def == NULL) 1335 { 1336 gimple_debug_bind_reset_value (stmt); 1337 update_stmt (stmt); 1338 return; 1339 } 1340 SET_USE (use_p, def); 1341 } 1342 if (update) 1343 update_stmt (stmt); 1344 } 1345 1346 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in 1347 the block with its immediate reaching definitions. Update the current 1348 definition of a variable when a new real or virtual definition is found. */ 1349 1350 static void 1351 rewrite_stmt (gimple_stmt_iterator *si) 1352 { 1353 use_operand_p use_p; 1354 def_operand_p def_p; 1355 ssa_op_iter iter; 1356 gimple *stmt = gsi_stmt (*si); 1357 1358 /* If mark_def_sites decided that we don't need to rewrite this 1359 statement, ignore it. */ 1360 gcc_assert (blocks_to_update == NULL); 1361 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt)) 1362 return; 1363 1364 if (dump_file && (dump_flags & TDF_DETAILS)) 1365 { 1366 fprintf (dump_file, "Renaming statement "); 1367 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1368 fprintf (dump_file, "\n"); 1369 } 1370 1371 /* Step 1. Rewrite USES in the statement. */ 1372 if (rewrite_uses_p (stmt)) 1373 { 1374 if (is_gimple_debug (stmt)) 1375 rewrite_debug_stmt_uses (stmt); 1376 else 1377 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 1378 { 1379 tree var = USE_FROM_PTR (use_p); 1380 if (TREE_CODE (var) == SSA_NAME) 1381 continue; 1382 gcc_checking_assert (DECL_P (var)); 1383 SET_USE (use_p, get_reaching_def (var)); 1384 } 1385 } 1386 1387 /* Step 2. Register the statement's DEF operands. */ 1388 if (register_defs_p (stmt)) 1389 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 1390 { 1391 tree var = DEF_FROM_PTR (def_p); 1392 tree name; 1393 tree tracked_var; 1394 1395 if (TREE_CODE (var) == SSA_NAME) 1396 continue; 1397 gcc_checking_assert (DECL_P (var)); 1398 1399 if (gimple_clobber_p (stmt) 1400 && is_gimple_reg (var)) 1401 { 1402 /* If we rewrite a DECL into SSA form then drop its 1403 clobber stmts and replace uses with a new default def. */ 1404 gcc_checking_assert (VAR_P (var) && !gimple_vdef (stmt)); 1405 gsi_replace (si, gimple_build_nop (), true); 1406 register_new_def (get_or_create_ssa_default_def (cfun, var), var); 1407 break; 1408 } 1409 1410 name = make_ssa_name (var, stmt); 1411 SET_DEF (def_p, name); 1412 register_new_def (DEF_FROM_PTR (def_p), var); 1413 1414 tracked_var = target_for_debug_bind (var); 1415 if (tracked_var) 1416 { 1417 gimple *note = gimple_build_debug_bind (tracked_var, name, stmt); 1418 gsi_insert_after (si, note, GSI_SAME_STMT); 1419 } 1420 } 1421 } 1422 1423 1424 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for 1425 PHI nodes. For every PHI node found, add a new argument containing the 1426 current reaching definition for the variable and the edge through which 1427 that definition is reaching the PHI node. */ 1428 1429 static void 1430 rewrite_add_phi_arguments (basic_block bb) 1431 { 1432 edge e; 1433 edge_iterator ei; 1434 1435 FOR_EACH_EDGE (e, ei, bb->succs) 1436 { 1437 gphi *phi; 1438 gphi_iterator gsi; 1439 1440 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); 1441 gsi_next (&gsi)) 1442 { 1443 tree currdef, res; 1444 location_t loc; 1445 1446 phi = gsi.phi (); 1447 res = gimple_phi_result (phi); 1448 currdef = get_reaching_def (SSA_NAME_VAR (res)); 1449 /* Virtual operand PHI args do not need a location. */ 1450 if (virtual_operand_p (res)) 1451 loc = UNKNOWN_LOCATION; 1452 else 1453 loc = gimple_location (SSA_NAME_DEF_STMT (currdef)); 1454 add_phi_arg (phi, currdef, e, loc); 1455 } 1456 } 1457 } 1458 1459 class rewrite_dom_walker : public dom_walker 1460 { 1461 public: 1462 rewrite_dom_walker (cdi_direction direction) 1463 : dom_walker (direction, ALL_BLOCKS, NULL) {} 1464 1465 virtual edge before_dom_children (basic_block); 1466 virtual void after_dom_children (basic_block); 1467 }; 1468 1469 /* SSA Rewriting Step 1. Initialization, create a block local stack 1470 of reaching definitions for new SSA names produced in this block 1471 (BLOCK_DEFS). Register new definitions for every PHI node in the 1472 block. */ 1473 1474 edge 1475 rewrite_dom_walker::before_dom_children (basic_block bb) 1476 { 1477 if (dump_file && (dump_flags & TDF_DETAILS)) 1478 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index); 1479 1480 /* Mark the unwind point for this block. */ 1481 block_defs_stack.safe_push (NULL_TREE); 1482 1483 /* Step 1. Register new definitions for every PHI node in the block. 1484 Conceptually, all the PHI nodes are executed in parallel and each PHI 1485 node introduces a new version for the associated variable. */ 1486 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 1487 gsi_next (&gsi)) 1488 { 1489 tree result = gimple_phi_result (gsi_stmt (gsi)); 1490 register_new_def (result, SSA_NAME_VAR (result)); 1491 } 1492 1493 /* Step 2. Rewrite every variable used in each statement in the block 1494 with its immediate reaching definitions. Update the current definition 1495 of a variable when a new real or virtual definition is found. */ 1496 if (bitmap_bit_p (interesting_blocks, bb->index)) 1497 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 1498 gsi_next (&gsi)) 1499 rewrite_stmt (&gsi); 1500 1501 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes. 1502 For every PHI node found, add a new argument containing the current 1503 reaching definition for the variable and the edge through which that 1504 definition is reaching the PHI node. */ 1505 rewrite_add_phi_arguments (bb); 1506 1507 return NULL; 1508 } 1509 1510 1511 1512 /* Called after visiting all the statements in basic block BB and all 1513 of its dominator children. Restore CURRDEFS to its original value. */ 1514 1515 void 1516 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) 1517 { 1518 /* Restore CURRDEFS to its original state. */ 1519 while (block_defs_stack.length () > 0) 1520 { 1521 tree tmp = block_defs_stack.pop (); 1522 tree saved_def, var; 1523 1524 if (tmp == NULL_TREE) 1525 break; 1526 1527 if (TREE_CODE (tmp) == SSA_NAME) 1528 { 1529 /* If we recorded an SSA_NAME, then make the SSA_NAME the 1530 current definition of its underlying variable. Note that 1531 if the SSA_NAME is not for a GIMPLE register, the symbol 1532 being defined is stored in the next slot in the stack. 1533 This mechanism is needed because an SSA name for a 1534 non-register symbol may be the definition for more than 1535 one symbol (e.g., SFTs, aliased variables, etc). */ 1536 saved_def = tmp; 1537 var = SSA_NAME_VAR (saved_def); 1538 if (!is_gimple_reg (var)) 1539 var = block_defs_stack.pop (); 1540 } 1541 else 1542 { 1543 /* If we recorded anything else, it must have been a _DECL 1544 node and its current reaching definition must have been 1545 NULL. */ 1546 saved_def = NULL; 1547 var = tmp; 1548 } 1549 1550 get_common_info (var)->current_def = saved_def; 1551 } 1552 } 1553 1554 1555 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */ 1556 1557 DEBUG_FUNCTION void 1558 debug_decl_set (bitmap set) 1559 { 1560 dump_decl_set (stderr, set); 1561 fprintf (stderr, "\n"); 1562 } 1563 1564 1565 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the 1566 stack up to a maximum of N levels. If N is -1, the whole stack is 1567 dumped. New levels are created when the dominator tree traversal 1568 used for renaming enters a new sub-tree. */ 1569 1570 void 1571 dump_defs_stack (FILE *file, int n) 1572 { 1573 int i, j; 1574 1575 fprintf (file, "\n\nRenaming stack"); 1576 if (n > 0) 1577 fprintf (file, " (up to %d levels)", n); 1578 fprintf (file, "\n\n"); 1579 1580 i = 1; 1581 fprintf (file, "Level %d (current level)\n", i); 1582 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--) 1583 { 1584 tree name, var; 1585 1586 name = block_defs_stack[j]; 1587 if (name == NULL_TREE) 1588 { 1589 i++; 1590 if (n > 0 && i > n) 1591 break; 1592 fprintf (file, "\nLevel %d\n", i); 1593 continue; 1594 } 1595 1596 if (DECL_P (name)) 1597 { 1598 var = name; 1599 name = NULL_TREE; 1600 } 1601 else 1602 { 1603 var = SSA_NAME_VAR (name); 1604 if (!is_gimple_reg (var)) 1605 { 1606 j--; 1607 var = block_defs_stack[j]; 1608 } 1609 } 1610 1611 fprintf (file, " Previous CURRDEF ("); 1612 print_generic_expr (file, var); 1613 fprintf (file, ") = "); 1614 if (name) 1615 print_generic_expr (file, name); 1616 else 1617 fprintf (file, "<NIL>"); 1618 fprintf (file, "\n"); 1619 } 1620 } 1621 1622 1623 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the 1624 stack up to a maximum of N levels. If N is -1, the whole stack is 1625 dumped. New levels are created when the dominator tree traversal 1626 used for renaming enters a new sub-tree. */ 1627 1628 DEBUG_FUNCTION void 1629 debug_defs_stack (int n) 1630 { 1631 dump_defs_stack (stderr, n); 1632 } 1633 1634 1635 /* Dump the current reaching definition of every symbol to FILE. */ 1636 1637 void 1638 dump_currdefs (FILE *file) 1639 { 1640 unsigned i; 1641 tree var; 1642 1643 if (symbols_to_rename.is_empty ()) 1644 return; 1645 1646 fprintf (file, "\n\nCurrent reaching definitions\n\n"); 1647 FOR_EACH_VEC_ELT (symbols_to_rename, i, var) 1648 { 1649 common_info *info = get_common_info (var); 1650 fprintf (file, "CURRDEF ("); 1651 print_generic_expr (file, var); 1652 fprintf (file, ") = "); 1653 if (info->current_def) 1654 print_generic_expr (file, info->current_def); 1655 else 1656 fprintf (file, "<NIL>"); 1657 fprintf (file, "\n"); 1658 } 1659 } 1660 1661 1662 /* Dump the current reaching definition of every symbol to stderr. */ 1663 1664 DEBUG_FUNCTION void 1665 debug_currdefs (void) 1666 { 1667 dump_currdefs (stderr); 1668 } 1669 1670 1671 /* Dump SSA information to FILE. */ 1672 1673 void 1674 dump_tree_ssa (FILE *file) 1675 { 1676 const char *funcname 1677 = lang_hooks.decl_printable_name (current_function_decl, 2); 1678 1679 fprintf (file, "SSA renaming information for %s\n\n", funcname); 1680 1681 dump_var_infos (file); 1682 dump_defs_stack (file, -1); 1683 dump_currdefs (file); 1684 dump_tree_ssa_stats (file); 1685 } 1686 1687 1688 /* Dump SSA information to stderr. */ 1689 1690 DEBUG_FUNCTION void 1691 debug_tree_ssa (void) 1692 { 1693 dump_tree_ssa (stderr); 1694 } 1695 1696 1697 /* Dump statistics for the hash table HTAB. */ 1698 1699 static void 1700 htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab) 1701 { 1702 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 1703 (long) htab.size (), 1704 (long) htab.elements (), 1705 htab.collisions ()); 1706 } 1707 1708 1709 /* Dump SSA statistics on FILE. */ 1710 1711 void 1712 dump_tree_ssa_stats (FILE *file) 1713 { 1714 if (var_infos) 1715 { 1716 fprintf (file, "\nHash table statistics:\n"); 1717 fprintf (file, " var_infos: "); 1718 htab_statistics (file, *var_infos); 1719 fprintf (file, "\n"); 1720 } 1721 } 1722 1723 1724 /* Dump SSA statistics on stderr. */ 1725 1726 DEBUG_FUNCTION void 1727 debug_tree_ssa_stats (void) 1728 { 1729 dump_tree_ssa_stats (stderr); 1730 } 1731 1732 1733 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */ 1734 1735 int 1736 debug_var_infos_r (var_info **slot, FILE *file) 1737 { 1738 var_info *info = *slot; 1739 1740 fprintf (file, "VAR: "); 1741 print_generic_expr (file, info->var, dump_flags); 1742 bitmap_print (file, info->info.def_blocks.def_blocks, 1743 ", DEF_BLOCKS: { ", "}"); 1744 bitmap_print (file, info->info.def_blocks.livein_blocks, 1745 ", LIVEIN_BLOCKS: { ", "}"); 1746 bitmap_print (file, info->info.def_blocks.phi_blocks, 1747 ", PHI_BLOCKS: { ", "}\n"); 1748 1749 return 1; 1750 } 1751 1752 1753 /* Dump the VAR_INFOS hash table on FILE. */ 1754 1755 void 1756 dump_var_infos (FILE *file) 1757 { 1758 fprintf (file, "\n\nDefinition and live-in blocks:\n\n"); 1759 if (var_infos) 1760 var_infos->traverse <FILE *, debug_var_infos_r> (file); 1761 } 1762 1763 1764 /* Dump the VAR_INFOS hash table on stderr. */ 1765 1766 DEBUG_FUNCTION void 1767 debug_var_infos (void) 1768 { 1769 dump_var_infos (stderr); 1770 } 1771 1772 1773 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */ 1774 1775 static inline void 1776 register_new_update_single (tree new_name, tree old_name) 1777 { 1778 common_info *info = get_common_info (old_name); 1779 tree currdef = info->current_def; 1780 1781 /* Push the current reaching definition into BLOCK_DEFS_STACK. 1782 This stack is later used by the dominator tree callbacks to 1783 restore the reaching definitions for all the variables 1784 defined in the block after a recursive visit to all its 1785 immediately dominated blocks. */ 1786 block_defs_stack.reserve (2); 1787 block_defs_stack.quick_push (currdef); 1788 block_defs_stack.quick_push (old_name); 1789 1790 /* Set the current reaching definition for OLD_NAME to be 1791 NEW_NAME. */ 1792 info->current_def = new_name; 1793 } 1794 1795 1796 /* Register NEW_NAME to be the new reaching definition for all the 1797 names in OLD_NAMES. Used by the incremental SSA update routines to 1798 replace old SSA names with new ones. */ 1799 1800 static inline void 1801 register_new_update_set (tree new_name, bitmap old_names) 1802 { 1803 bitmap_iterator bi; 1804 unsigned i; 1805 1806 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi) 1807 register_new_update_single (new_name, ssa_name (i)); 1808 } 1809 1810 1811 1812 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or 1813 it is a symbol marked for renaming, replace it with USE_P's current 1814 reaching definition. */ 1815 1816 static inline void 1817 maybe_replace_use (use_operand_p use_p) 1818 { 1819 tree rdef = NULL_TREE; 1820 tree use = USE_FROM_PTR (use_p); 1821 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 1822 1823 if (marked_for_renaming (sym)) 1824 rdef = get_reaching_def (sym); 1825 else if (is_old_name (use)) 1826 rdef = get_reaching_def (use); 1827 1828 if (rdef && rdef != use) 1829 SET_USE (use_p, rdef); 1830 } 1831 1832 1833 /* Same as maybe_replace_use, but without introducing default stmts, 1834 returning false to indicate a need to do so. */ 1835 1836 static inline bool 1837 maybe_replace_use_in_debug_stmt (use_operand_p use_p) 1838 { 1839 tree rdef = NULL_TREE; 1840 tree use = USE_FROM_PTR (use_p); 1841 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 1842 1843 if (marked_for_renaming (sym)) 1844 rdef = get_var_info (sym)->info.current_def; 1845 else if (is_old_name (use)) 1846 { 1847 rdef = get_ssa_name_ann (use)->info.current_def; 1848 /* We can't assume that, if there's no current definition, the 1849 default one should be used. It could be the case that we've 1850 rearranged blocks so that the earlier definition no longer 1851 dominates the use. */ 1852 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use)) 1853 rdef = use; 1854 } 1855 else 1856 rdef = use; 1857 1858 if (rdef && rdef != use) 1859 SET_USE (use_p, rdef); 1860 1861 return rdef != NULL_TREE; 1862 } 1863 1864 1865 /* If DEF has x_5 = ASAN_POISON () as its current def, add 1866 ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into 1867 a poisoned (out of scope) variable. */ 1868 1869 static void 1870 maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi) 1871 { 1872 tree cdef = get_current_def (def); 1873 if (cdef != NULL 1874 && TREE_CODE (cdef) == SSA_NAME 1875 && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), IFN_ASAN_POISON)) 1876 { 1877 gcall *call 1878 = gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef); 1879 gimple_set_location (call, gimple_location (gsi_stmt (*gsi))); 1880 gsi_insert_before (gsi, call, GSI_SAME_STMT); 1881 } 1882 } 1883 1884 1885 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES 1886 or OLD_SSA_NAMES, or if it is a symbol marked for renaming, 1887 register it as the current definition for the names replaced by 1888 DEF_P. Returns whether the statement should be removed. */ 1889 1890 static inline bool 1891 maybe_register_def (def_operand_p def_p, gimple *stmt, 1892 gimple_stmt_iterator gsi) 1893 { 1894 tree def = DEF_FROM_PTR (def_p); 1895 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 1896 bool to_delete = false; 1897 1898 /* If DEF is a naked symbol that needs renaming, create a new 1899 name for it. */ 1900 if (marked_for_renaming (sym)) 1901 { 1902 if (DECL_P (def)) 1903 { 1904 if (gimple_clobber_p (stmt) && is_gimple_reg (sym)) 1905 { 1906 gcc_checking_assert (VAR_P (sym)); 1907 /* Replace clobber stmts with a default def. This new use of a 1908 default definition may make it look like SSA_NAMEs have 1909 conflicting lifetimes, so we need special code to let them 1910 coalesce properly. */ 1911 to_delete = true; 1912 def = get_or_create_ssa_default_def (cfun, sym); 1913 } 1914 else 1915 { 1916 if (asan_sanitize_use_after_scope ()) 1917 maybe_add_asan_poison_write (def, &gsi); 1918 def = make_ssa_name (def, stmt); 1919 } 1920 SET_DEF (def_p, def); 1921 1922 tree tracked_var = target_for_debug_bind (sym); 1923 if (tracked_var) 1924 { 1925 gimple *note = gimple_build_debug_bind (tracked_var, def, stmt); 1926 /* If stmt ends the bb, insert the debug stmt on the single 1927 non-EH edge from the stmt. */ 1928 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt)) 1929 { 1930 basic_block bb = gsi_bb (gsi); 1931 edge_iterator ei; 1932 edge e, ef = NULL; 1933 FOR_EACH_EDGE (e, ei, bb->succs) 1934 if (!(e->flags & EDGE_EH)) 1935 { 1936 gcc_checking_assert (!ef); 1937 ef = e; 1938 } 1939 /* If there are other predecessors to ef->dest, then 1940 there must be PHI nodes for the modified 1941 variable, and therefore there will be debug bind 1942 stmts after the PHI nodes. The debug bind notes 1943 we'd insert would force the creation of a new 1944 block (diverging codegen) and be redundant with 1945 the post-PHI bind stmts, so don't add them. 1946 1947 As for the exit edge, there wouldn't be redundant 1948 bind stmts, but there wouldn't be a PC to bind 1949 them to either, so avoid diverging the CFG. */ 1950 if (ef && single_pred_p (ef->dest) 1951 && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1952 { 1953 /* If there were PHI nodes in the node, we'd 1954 have to make sure the value we're binding 1955 doesn't need rewriting. But there shouldn't 1956 be PHI nodes in a single-predecessor block, 1957 so we just add the note. */ 1958 gsi_insert_on_edge_immediate (ef, note); 1959 } 1960 } 1961 else 1962 gsi_insert_after (&gsi, note, GSI_SAME_STMT); 1963 } 1964 } 1965 1966 register_new_update_single (def, sym); 1967 } 1968 else 1969 { 1970 /* If DEF is a new name, register it as a new definition 1971 for all the names replaced by DEF. */ 1972 if (is_new_name (def)) 1973 register_new_update_set (def, names_replaced_by (def)); 1974 1975 /* If DEF is an old name, register DEF as a new 1976 definition for itself. */ 1977 if (is_old_name (def)) 1978 register_new_update_single (def, def); 1979 } 1980 1981 return to_delete; 1982 } 1983 1984 1985 /* Update every variable used in the statement pointed-to by SI. The 1986 statement is assumed to be in SSA form already. Names in 1987 OLD_SSA_NAMES used by SI will be updated to their current reaching 1988 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI 1989 will be registered as a new definition for their corresponding name 1990 in OLD_SSA_NAMES. Returns whether STMT should be removed. */ 1991 1992 static bool 1993 rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi) 1994 { 1995 use_operand_p use_p; 1996 def_operand_p def_p; 1997 ssa_op_iter iter; 1998 1999 /* Only update marked statements. */ 2000 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt)) 2001 return false; 2002 2003 if (dump_file && (dump_flags & TDF_DETAILS)) 2004 { 2005 fprintf (dump_file, "Updating SSA information for statement "); 2006 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2007 } 2008 2009 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying 2010 symbol is marked for renaming. */ 2011 if (rewrite_uses_p (stmt)) 2012 { 2013 if (is_gimple_debug (stmt)) 2014 { 2015 bool failed = false; 2016 2017 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) 2018 if (!maybe_replace_use_in_debug_stmt (use_p)) 2019 { 2020 failed = true; 2021 break; 2022 } 2023 2024 if (failed) 2025 { 2026 /* DOM sometimes threads jumps in such a way that a 2027 debug stmt ends up referencing a SSA variable that no 2028 longer dominates the debug stmt, but such that all 2029 incoming definitions refer to the same definition in 2030 an earlier dominator. We could try to recover that 2031 definition somehow, but this will have to do for now. 2032 2033 Introducing a default definition, which is what 2034 maybe_replace_use() would do in such cases, may 2035 modify code generation, for the otherwise-unused 2036 default definition would never go away, modifying SSA 2037 version numbers all over. */ 2038 gimple_debug_bind_reset_value (stmt); 2039 update_stmt (stmt); 2040 } 2041 } 2042 else 2043 { 2044 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 2045 maybe_replace_use (use_p); 2046 } 2047 } 2048 2049 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES. 2050 Also register definitions for names whose underlying symbol is 2051 marked for renaming. */ 2052 bool to_delete = false; 2053 if (register_defs_p (stmt)) 2054 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 2055 to_delete |= maybe_register_def (def_p, stmt, gsi); 2056 2057 return to_delete; 2058 } 2059 2060 2061 /* Visit all the successor blocks of BB looking for PHI nodes. For 2062 every PHI node found, check if any of its arguments is in 2063 OLD_SSA_NAMES. If so, and if the argument has a current reaching 2064 definition, replace it. */ 2065 2066 static void 2067 rewrite_update_phi_arguments (basic_block bb) 2068 { 2069 edge e; 2070 edge_iterator ei; 2071 unsigned i; 2072 2073 FOR_EACH_EDGE (e, ei, bb->succs) 2074 { 2075 gphi *phi; 2076 vec<gphi *> phis; 2077 2078 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index)) 2079 continue; 2080 2081 phis = phis_to_rewrite[e->dest->index]; 2082 FOR_EACH_VEC_ELT (phis, i, phi) 2083 { 2084 tree arg, lhs_sym, reaching_def = NULL; 2085 use_operand_p arg_p; 2086 2087 gcc_checking_assert (rewrite_uses_p (phi)); 2088 2089 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); 2090 arg = USE_FROM_PTR (arg_p); 2091 2092 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME) 2093 continue; 2094 2095 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi)); 2096 2097 if (arg == NULL_TREE) 2098 { 2099 /* When updating a PHI node for a recently introduced 2100 symbol we may find NULL arguments. That's why we 2101 take the symbol from the LHS of the PHI node. */ 2102 reaching_def = get_reaching_def (lhs_sym); 2103 2104 } 2105 else 2106 { 2107 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg); 2108 2109 if (marked_for_renaming (sym)) 2110 reaching_def = get_reaching_def (sym); 2111 else if (is_old_name (arg)) 2112 reaching_def = get_reaching_def (arg); 2113 } 2114 2115 /* Update the argument if there is a reaching def. */ 2116 if (reaching_def) 2117 { 2118 location_t locus; 2119 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p); 2120 2121 SET_USE (arg_p, reaching_def); 2122 2123 /* Virtual operands do not need a location. */ 2124 if (virtual_operand_p (reaching_def)) 2125 locus = UNKNOWN_LOCATION; 2126 else 2127 { 2128 gimple *stmt = SSA_NAME_DEF_STMT (reaching_def); 2129 gphi *other_phi = dyn_cast <gphi *> (stmt); 2130 2131 /* Single element PHI nodes behave like copies, so get the 2132 location from the phi argument. */ 2133 if (other_phi 2134 && gimple_phi_num_args (other_phi) == 1) 2135 locus = gimple_phi_arg_location (other_phi, 0); 2136 else 2137 locus = gimple_location (stmt); 2138 } 2139 2140 gimple_phi_arg_set_location (phi, arg_i, locus); 2141 } 2142 2143 2144 if (e->flags & EDGE_ABNORMAL) 2145 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1; 2146 } 2147 } 2148 } 2149 2150 class rewrite_update_dom_walker : public dom_walker 2151 { 2152 public: 2153 rewrite_update_dom_walker (cdi_direction direction) 2154 : dom_walker (direction, ALL_BLOCKS, NULL) {} 2155 2156 virtual edge before_dom_children (basic_block); 2157 virtual void after_dom_children (basic_block); 2158 }; 2159 2160 /* Initialization of block data structures for the incremental SSA 2161 update pass. Create a block local stack of reaching definitions 2162 for new SSA names produced in this block (BLOCK_DEFS). Register 2163 new definitions for every PHI node in the block. */ 2164 2165 edge 2166 rewrite_update_dom_walker::before_dom_children (basic_block bb) 2167 { 2168 bool is_abnormal_phi; 2169 2170 if (dump_file && (dump_flags & TDF_DETAILS)) 2171 fprintf (dump_file, "Registering new PHI nodes in block #%d\n", 2172 bb->index); 2173 2174 /* Mark the unwind point for this block. */ 2175 block_defs_stack.safe_push (NULL_TREE); 2176 2177 if (!bitmap_bit_p (blocks_to_update, bb->index)) 2178 return NULL; 2179 2180 /* Mark the LHS if any of the arguments flows through an abnormal 2181 edge. */ 2182 is_abnormal_phi = bb_has_abnormal_pred (bb); 2183 2184 /* If any of the PHI nodes is a replacement for a name in 2185 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then 2186 register it as a new definition for its corresponding name. Also 2187 register definitions for names whose underlying symbols are 2188 marked for renaming. */ 2189 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 2190 gsi_next (&gsi)) 2191 { 2192 tree lhs, lhs_sym; 2193 gphi *phi = gsi.phi (); 2194 2195 if (!register_defs_p (phi)) 2196 continue; 2197 2198 lhs = gimple_phi_result (phi); 2199 lhs_sym = SSA_NAME_VAR (lhs); 2200 2201 if (marked_for_renaming (lhs_sym)) 2202 register_new_update_single (lhs, lhs_sym); 2203 else 2204 { 2205 2206 /* If LHS is a new name, register a new definition for all 2207 the names replaced by LHS. */ 2208 if (is_new_name (lhs)) 2209 register_new_update_set (lhs, names_replaced_by (lhs)); 2210 2211 /* If LHS is an OLD name, register it as a new definition 2212 for itself. */ 2213 if (is_old_name (lhs)) 2214 register_new_update_single (lhs, lhs); 2215 } 2216 2217 if (is_abnormal_phi) 2218 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1; 2219 } 2220 2221 /* Step 2. Rewrite every variable used in each statement in the block. */ 2222 if (bitmap_bit_p (interesting_blocks, bb->index)) 2223 { 2224 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index)); 2225 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 2226 if (rewrite_update_stmt (gsi_stmt (gsi), gsi)) 2227 gsi_remove (&gsi, true); 2228 else 2229 gsi_next (&gsi); 2230 } 2231 2232 /* Step 3. Update PHI nodes. */ 2233 rewrite_update_phi_arguments (bb); 2234 2235 return NULL; 2236 } 2237 2238 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore 2239 the current reaching definition of every name re-written in BB to 2240 the original reaching definition before visiting BB. This 2241 unwinding must be done in the opposite order to what is done in 2242 register_new_update_set. */ 2243 2244 void 2245 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) 2246 { 2247 while (block_defs_stack.length () > 0) 2248 { 2249 tree var = block_defs_stack.pop (); 2250 tree saved_def; 2251 2252 /* NULL indicates the unwind stop point for this block (see 2253 rewrite_update_enter_block). */ 2254 if (var == NULL) 2255 return; 2256 2257 saved_def = block_defs_stack.pop (); 2258 get_common_info (var)->current_def = saved_def; 2259 } 2260 } 2261 2262 2263 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA 2264 form. 2265 2266 ENTRY indicates the block where to start. Every block dominated by 2267 ENTRY will be rewritten. 2268 2269 WHAT indicates what actions will be taken by the renamer (see enum 2270 rewrite_mode). 2271 2272 BLOCKS are the set of interesting blocks for the dominator walker 2273 to process. If this set is NULL, then all the nodes dominated 2274 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that 2275 are not present in BLOCKS are ignored. */ 2276 2277 static void 2278 rewrite_blocks (basic_block entry, enum rewrite_mode what) 2279 { 2280 /* Rewrite all the basic blocks in the program. */ 2281 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS); 2282 2283 block_defs_stack.create (10); 2284 2285 /* Recursively walk the dominator tree rewriting each statement in 2286 each basic block. */ 2287 if (what == REWRITE_ALL) 2288 rewrite_dom_walker (CDI_DOMINATORS).walk (entry); 2289 else if (what == REWRITE_UPDATE) 2290 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry); 2291 else 2292 gcc_unreachable (); 2293 2294 /* Debugging dumps. */ 2295 if (dump_file && (dump_flags & TDF_STATS)) 2296 { 2297 dump_dfa_stats (dump_file); 2298 if (var_infos) 2299 dump_tree_ssa_stats (dump_file); 2300 } 2301 2302 block_defs_stack.release (); 2303 2304 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS); 2305 } 2306 2307 class mark_def_dom_walker : public dom_walker 2308 { 2309 public: 2310 mark_def_dom_walker (cdi_direction direction); 2311 ~mark_def_dom_walker (); 2312 2313 virtual edge before_dom_children (basic_block); 2314 2315 private: 2316 /* Notice that this bitmap is indexed using variable UIDs, so it must be 2317 large enough to accommodate all the variables referenced in the 2318 function, not just the ones we are renaming. */ 2319 bitmap m_kills; 2320 }; 2321 2322 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction) 2323 : dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL)) 2324 { 2325 } 2326 2327 mark_def_dom_walker::~mark_def_dom_walker () 2328 { 2329 BITMAP_FREE (m_kills); 2330 } 2331 2332 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap 2333 at the start of each block, and call mark_def_sites for each statement. */ 2334 2335 edge 2336 mark_def_dom_walker::before_dom_children (basic_block bb) 2337 { 2338 gimple_stmt_iterator gsi; 2339 2340 bitmap_clear (m_kills); 2341 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2342 mark_def_sites (bb, gsi_stmt (gsi), m_kills); 2343 return NULL; 2344 } 2345 2346 /* Initialize internal data needed during renaming. */ 2347 2348 static void 2349 init_ssa_renamer (void) 2350 { 2351 cfun->gimple_df->in_ssa_p = false; 2352 2353 /* Allocate memory for the DEF_BLOCKS hash table. */ 2354 gcc_assert (!var_infos); 2355 var_infos = new hash_table<var_info_hasher> 2356 (vec_safe_length (cfun->local_decls)); 2357 2358 bitmap_obstack_initialize (&update_ssa_obstack); 2359 } 2360 2361 2362 /* Deallocate internal data structures used by the renamer. */ 2363 2364 static void 2365 fini_ssa_renamer (void) 2366 { 2367 delete var_infos; 2368 var_infos = NULL; 2369 2370 bitmap_obstack_release (&update_ssa_obstack); 2371 2372 cfun->gimple_df->ssa_renaming_needed = 0; 2373 cfun->gimple_df->rename_vops = 0; 2374 cfun->gimple_df->in_ssa_p = true; 2375 } 2376 2377 /* Main entry point into the SSA builder. The renaming process 2378 proceeds in four main phases: 2379 2380 1- Compute dominance frontier and immediate dominators, needed to 2381 insert PHI nodes and rename the function in dominator tree 2382 order. 2383 2384 2- Find and mark all the blocks that define variables. 2385 2386 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes). 2387 2388 4- Rename all the blocks (rewrite_blocks) and statements in the program. 2389 2390 Steps 3 and 4 are done using the dominator tree walker 2391 (walk_dominator_tree). */ 2392 2393 namespace { 2394 2395 const pass_data pass_data_build_ssa = 2396 { 2397 GIMPLE_PASS, /* type */ 2398 "ssa", /* name */ 2399 OPTGROUP_NONE, /* optinfo_flags */ 2400 TV_TREE_SSA_OTHER, /* tv_id */ 2401 PROP_cfg, /* properties_required */ 2402 PROP_ssa, /* properties_provided */ 2403 0, /* properties_destroyed */ 2404 0, /* todo_flags_start */ 2405 TODO_remove_unused_locals, /* todo_flags_finish */ 2406 }; 2407 2408 class pass_build_ssa : public gimple_opt_pass 2409 { 2410 public: 2411 pass_build_ssa (gcc::context *ctxt) 2412 : gimple_opt_pass (pass_data_build_ssa, ctxt) 2413 {} 2414 2415 /* opt_pass methods: */ 2416 virtual bool gate (function *fun) 2417 { 2418 /* Do nothing for funcions that was produced already in SSA form. */ 2419 return !(fun->curr_properties & PROP_ssa); 2420 } 2421 2422 virtual unsigned int execute (function *); 2423 2424 }; // class pass_build_ssa 2425 2426 unsigned int 2427 pass_build_ssa::execute (function *fun) 2428 { 2429 bitmap_head *dfs; 2430 basic_block bb; 2431 2432 /* Increase the set of variables we can rewrite into SSA form 2433 by clearing TREE_ADDRESSABLE and setting DECL_GIMPLE_REG_P 2434 and transform the IL to support this. */ 2435 if (optimize) 2436 execute_update_addresses_taken (); 2437 2438 /* Initialize operand data structures. */ 2439 init_ssa_operands (fun); 2440 2441 /* Initialize internal data needed by the renamer. */ 2442 init_ssa_renamer (); 2443 2444 /* Initialize the set of interesting blocks. The callback 2445 mark_def_sites will add to this set those blocks that the renamer 2446 should process. */ 2447 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun)); 2448 bitmap_clear (interesting_blocks); 2449 2450 /* Initialize dominance frontier. */ 2451 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun)); 2452 FOR_EACH_BB_FN (bb, fun) 2453 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack); 2454 2455 /* 1- Compute dominance frontiers. */ 2456 calculate_dominance_info (CDI_DOMINATORS); 2457 compute_dominance_frontiers (dfs); 2458 2459 /* 2- Find and mark definition sites. */ 2460 mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); 2461 2462 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */ 2463 insert_phi_nodes (dfs); 2464 2465 /* 4- Rename all the blocks. */ 2466 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL); 2467 2468 /* Free allocated memory. */ 2469 FOR_EACH_BB_FN (bb, fun) 2470 bitmap_clear (&dfs[bb->index]); 2471 free (dfs); 2472 2473 sbitmap_free (interesting_blocks); 2474 2475 fini_ssa_renamer (); 2476 2477 /* Try to get rid of all gimplifier generated temporaries by making 2478 its SSA names anonymous. This way we can garbage collect them 2479 all after removing unused locals which we do in our TODO. */ 2480 unsigned i; 2481 tree name; 2482 2483 FOR_EACH_SSA_NAME (i, name, cfun) 2484 { 2485 if (SSA_NAME_IS_DEFAULT_DEF (name)) 2486 continue; 2487 tree decl = SSA_NAME_VAR (name); 2488 if (decl 2489 && VAR_P (decl) 2490 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl) 2491 && DECL_IGNORED_P (decl)) 2492 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl)); 2493 } 2494 2495 /* Initialize SSA_NAME_POINTS_TO_READONLY_MEMORY. */ 2496 tree fnspec = lookup_attribute ("fn spec", 2497 TYPE_ATTRIBUTES (TREE_TYPE (fun->decl))); 2498 if (fnspec) 2499 { 2500 fnspec = TREE_VALUE (TREE_VALUE (fnspec)); 2501 unsigned i = 1; 2502 for (tree arg = DECL_ARGUMENTS (cfun->decl); 2503 arg; arg = DECL_CHAIN (arg), ++i) 2504 { 2505 if (i >= (unsigned) TREE_STRING_LENGTH (fnspec)) 2506 break; 2507 if (TREE_STRING_POINTER (fnspec)[i] == 'R' 2508 || TREE_STRING_POINTER (fnspec)[i] == 'r') 2509 { 2510 tree name = ssa_default_def (fun, arg); 2511 if (name) 2512 SSA_NAME_POINTS_TO_READONLY_MEMORY (name) = 1; 2513 } 2514 } 2515 } 2516 2517 return 0; 2518 } 2519 2520 } // anon namespace 2521 2522 gimple_opt_pass * 2523 make_pass_build_ssa (gcc::context *ctxt) 2524 { 2525 return new pass_build_ssa (ctxt); 2526 } 2527 2528 2529 /* Mark the definition of VAR at STMT and BB as interesting for the 2530 renamer. BLOCKS is the set of blocks that need updating. */ 2531 2532 static void 2533 mark_def_interesting (tree var, gimple *stmt, basic_block bb, 2534 bool insert_phi_p) 2535 { 2536 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index)); 2537 set_register_defs (stmt, true); 2538 2539 if (insert_phi_p) 2540 { 2541 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI; 2542 2543 set_def_block (var, bb, is_phi_p); 2544 2545 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition 2546 site for both itself and all the old names replaced by it. */ 2547 if (TREE_CODE (var) == SSA_NAME && is_new_name (var)) 2548 { 2549 bitmap_iterator bi; 2550 unsigned i; 2551 bitmap set = names_replaced_by (var); 2552 if (set) 2553 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 2554 set_def_block (ssa_name (i), bb, is_phi_p); 2555 } 2556 } 2557 } 2558 2559 2560 /* Mark the use of VAR at STMT and BB as interesting for the 2561 renamer. INSERT_PHI_P is true if we are going to insert new PHI 2562 nodes. */ 2563 2564 static inline void 2565 mark_use_interesting (tree var, gimple *stmt, basic_block bb, 2566 bool insert_phi_p) 2567 { 2568 basic_block def_bb = gimple_bb (stmt); 2569 2570 mark_block_for_update (def_bb); 2571 mark_block_for_update (bb); 2572 2573 if (gimple_code (stmt) == GIMPLE_PHI) 2574 mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt)); 2575 else 2576 { 2577 set_rewrite_uses (stmt, true); 2578 2579 if (is_gimple_debug (stmt)) 2580 return; 2581 } 2582 2583 /* If VAR has not been defined in BB, then it is live-on-entry 2584 to BB. Note that we cannot just use the block holding VAR's 2585 definition because if VAR is one of the names in OLD_SSA_NAMES, 2586 it will have several definitions (itself and all the names that 2587 replace it). */ 2588 if (insert_phi_p) 2589 { 2590 def_blocks *db_p = get_def_blocks_for (get_common_info (var)); 2591 if (!bitmap_bit_p (db_p->def_blocks, bb->index)) 2592 set_livein_block (var, bb); 2593 } 2594 } 2595 2596 /* Processing statements in BB that reference symbols in SSA operands. 2597 This is very similar to mark_def_sites, but the scan handles 2598 statements whose operands may already be SSA names. 2599 2600 If INSERT_PHI_P is true, mark those uses as live in the 2601 corresponding block. This is later used by the PHI placement 2602 algorithm to make PHI pruning decisions. 2603 2604 FIXME. Most of this would be unnecessary if we could associate a 2605 symbol to all the SSA names that reference it. But that 2606 sounds like it would be expensive to maintain. Still, it 2607 would be interesting to see if it makes better sense to do 2608 that. */ 2609 2610 static void 2611 prepare_block_for_update_1 (basic_block bb, bool insert_phi_p) 2612 { 2613 edge e; 2614 edge_iterator ei; 2615 2616 mark_block_for_update (bb); 2617 2618 /* Process PHI nodes marking interesting those that define or use 2619 the symbols that we are interested in. */ 2620 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); 2621 gsi_next (&si)) 2622 { 2623 gphi *phi = si.phi (); 2624 tree lhs_sym, lhs = gimple_phi_result (phi); 2625 2626 if (TREE_CODE (lhs) == SSA_NAME 2627 && (! virtual_operand_p (lhs) 2628 || ! cfun->gimple_df->rename_vops)) 2629 continue; 2630 2631 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs); 2632 mark_for_renaming (lhs_sym); 2633 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p); 2634 2635 /* Mark the uses in phi nodes as interesting. It would be more correct 2636 to process the arguments of the phi nodes of the successor edges of 2637 BB at the end of prepare_block_for_update, however, that turns out 2638 to be significantly more expensive. Doing it here is conservatively 2639 correct -- it may only cause us to believe a value to be live in a 2640 block that also contains its definition, and thus insert a few more 2641 phi nodes for it. */ 2642 FOR_EACH_EDGE (e, ei, bb->preds) 2643 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p); 2644 } 2645 2646 /* Process the statements. */ 2647 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); 2648 gsi_next (&si)) 2649 { 2650 gimple *stmt; 2651 ssa_op_iter i; 2652 use_operand_p use_p; 2653 def_operand_p def_p; 2654 2655 stmt = gsi_stmt (si); 2656 2657 if (cfun->gimple_df->rename_vops 2658 && gimple_vuse (stmt)) 2659 { 2660 tree use = gimple_vuse (stmt); 2661 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use); 2662 mark_for_renaming (sym); 2663 mark_use_interesting (sym, stmt, bb, insert_phi_p); 2664 } 2665 2666 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE) 2667 { 2668 tree use = USE_FROM_PTR (use_p); 2669 if (!DECL_P (use)) 2670 continue; 2671 mark_for_renaming (use); 2672 mark_use_interesting (use, stmt, bb, insert_phi_p); 2673 } 2674 2675 if (cfun->gimple_df->rename_vops 2676 && gimple_vdef (stmt)) 2677 { 2678 tree def = gimple_vdef (stmt); 2679 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def); 2680 mark_for_renaming (sym); 2681 mark_def_interesting (sym, stmt, bb, insert_phi_p); 2682 } 2683 2684 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF) 2685 { 2686 tree def = DEF_FROM_PTR (def_p); 2687 if (!DECL_P (def)) 2688 continue; 2689 mark_for_renaming (def); 2690 mark_def_interesting (def, stmt, bb, insert_phi_p); 2691 } 2692 } 2693 2694 } 2695 2696 /* Do a dominator walk starting at BB processing statements that 2697 reference symbols in SSA operands. This is very similar to 2698 mark_def_sites, but the scan handles statements whose operands may 2699 already be SSA names. 2700 2701 If INSERT_PHI_P is true, mark those uses as live in the 2702 corresponding block. This is later used by the PHI placement 2703 algorithm to make PHI pruning decisions. 2704 2705 FIXME. Most of this would be unnecessary if we could associate a 2706 symbol to all the SSA names that reference it. But that 2707 sounds like it would be expensive to maintain. Still, it 2708 would be interesting to see if it makes better sense to do 2709 that. */ 2710 static void 2711 prepare_block_for_update (basic_block bb, bool insert_phi_p) 2712 { 2713 size_t sp = 0; 2714 basic_block *worklist; 2715 2716 /* Allocate the worklist. */ 2717 worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); 2718 /* Add the BB to the worklist. */ 2719 worklist[sp++] = bb; 2720 2721 while (sp) 2722 { 2723 basic_block bb; 2724 basic_block son; 2725 2726 /* Pick a block from the worklist. */ 2727 bb = worklist[--sp]; 2728 2729 prepare_block_for_update_1 (bb, insert_phi_p); 2730 2731 /* Now add all the blocks dominated by BB to the worklist. */ 2732 for (son = first_dom_son (CDI_DOMINATORS, bb); 2733 son; 2734 son = next_dom_son (CDI_DOMINATORS, son)) 2735 worklist[sp++] = son; 2736 } 2737 free (worklist); 2738 } 2739 2740 /* Helper for prepare_names_to_update. Mark all the use sites for 2741 NAME as interesting. BLOCKS and INSERT_PHI_P are as in 2742 prepare_names_to_update. */ 2743 2744 static void 2745 prepare_use_sites_for (tree name, bool insert_phi_p) 2746 { 2747 use_operand_p use_p; 2748 imm_use_iterator iter; 2749 2750 /* If we rename virtual operands do not update them. */ 2751 if (virtual_operand_p (name) 2752 && cfun->gimple_df->rename_vops) 2753 return; 2754 2755 FOR_EACH_IMM_USE_FAST (use_p, iter, name) 2756 { 2757 gimple *stmt = USE_STMT (use_p); 2758 basic_block bb = gimple_bb (stmt); 2759 2760 if (gimple_code (stmt) == GIMPLE_PHI) 2761 { 2762 int ix = PHI_ARG_INDEX_FROM_USE (use_p); 2763 edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix); 2764 mark_use_interesting (name, stmt, e->src, insert_phi_p); 2765 } 2766 else 2767 { 2768 /* For regular statements, mark this as an interesting use 2769 for NAME. */ 2770 mark_use_interesting (name, stmt, bb, insert_phi_p); 2771 } 2772 } 2773 } 2774 2775 2776 /* Helper for prepare_names_to_update. Mark the definition site for 2777 NAME as interesting. BLOCKS and INSERT_PHI_P are as in 2778 prepare_names_to_update. */ 2779 2780 static void 2781 prepare_def_site_for (tree name, bool insert_phi_p) 2782 { 2783 gimple *stmt; 2784 basic_block bb; 2785 2786 gcc_checking_assert (names_to_release == NULL 2787 || !bitmap_bit_p (names_to_release, 2788 SSA_NAME_VERSION (name))); 2789 2790 /* If we rename virtual operands do not update them. */ 2791 if (virtual_operand_p (name) 2792 && cfun->gimple_df->rename_vops) 2793 return; 2794 2795 stmt = SSA_NAME_DEF_STMT (name); 2796 bb = gimple_bb (stmt); 2797 if (bb) 2798 { 2799 gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun)); 2800 mark_block_for_update (bb); 2801 mark_def_interesting (name, stmt, bb, insert_phi_p); 2802 } 2803 } 2804 2805 2806 /* Mark definition and use sites of names in NEW_SSA_NAMES and 2807 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert 2808 PHI nodes for newly created names. */ 2809 2810 static void 2811 prepare_names_to_update (bool insert_phi_p) 2812 { 2813 unsigned i = 0; 2814 bitmap_iterator bi; 2815 sbitmap_iterator sbi; 2816 2817 /* If a name N from NEW_SSA_NAMES is also marked to be released, 2818 remove it from NEW_SSA_NAMES so that we don't try to visit its 2819 defining basic block (which most likely doesn't exist). Notice 2820 that we cannot do the same with names in OLD_SSA_NAMES because we 2821 want to replace existing instances. */ 2822 if (names_to_release) 2823 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2824 bitmap_clear_bit (new_ssa_names, i); 2825 2826 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old 2827 names may be considered to be live-in on blocks that contain 2828 definitions for their replacements. */ 2829 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi) 2830 prepare_def_site_for (ssa_name (i), insert_phi_p); 2831 2832 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from 2833 OLD_SSA_NAMES, but we have to ignore its definition site. */ 2834 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi) 2835 { 2836 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i)) 2837 prepare_def_site_for (ssa_name (i), insert_phi_p); 2838 prepare_use_sites_for (ssa_name (i), insert_phi_p); 2839 } 2840 } 2841 2842 2843 /* Dump all the names replaced by NAME to FILE. */ 2844 2845 void 2846 dump_names_replaced_by (FILE *file, tree name) 2847 { 2848 unsigned i; 2849 bitmap old_set; 2850 bitmap_iterator bi; 2851 2852 print_generic_expr (file, name); 2853 fprintf (file, " -> { "); 2854 2855 old_set = names_replaced_by (name); 2856 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi) 2857 { 2858 print_generic_expr (file, ssa_name (i)); 2859 fprintf (file, " "); 2860 } 2861 2862 fprintf (file, "}\n"); 2863 } 2864 2865 2866 /* Dump all the names replaced by NAME to stderr. */ 2867 2868 DEBUG_FUNCTION void 2869 debug_names_replaced_by (tree name) 2870 { 2871 dump_names_replaced_by (stderr, name); 2872 } 2873 2874 2875 /* Dump SSA update information to FILE. */ 2876 2877 void 2878 dump_update_ssa (FILE *file) 2879 { 2880 unsigned i = 0; 2881 bitmap_iterator bi; 2882 2883 if (!need_ssa_update_p (cfun)) 2884 return; 2885 2886 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0) 2887 { 2888 sbitmap_iterator sbi; 2889 2890 fprintf (file, "\nSSA replacement table\n"); 2891 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces " 2892 "O_1, ..., O_j\n\n"); 2893 2894 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi) 2895 dump_names_replaced_by (file, ssa_name (i)); 2896 } 2897 2898 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set)) 2899 { 2900 fprintf (file, "\nSymbols to be put in SSA form\n"); 2901 dump_decl_set (file, symbols_to_rename_set); 2902 fprintf (file, "\n"); 2903 } 2904 2905 if (names_to_release && !bitmap_empty_p (names_to_release)) 2906 { 2907 fprintf (file, "\nSSA names to release after updating the SSA web\n\n"); 2908 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2909 { 2910 print_generic_expr (file, ssa_name (i)); 2911 fprintf (file, " "); 2912 } 2913 fprintf (file, "\n"); 2914 } 2915 } 2916 2917 2918 /* Dump SSA update information to stderr. */ 2919 2920 DEBUG_FUNCTION void 2921 debug_update_ssa (void) 2922 { 2923 dump_update_ssa (stderr); 2924 } 2925 2926 2927 /* Initialize data structures used for incremental SSA updates. */ 2928 2929 static void 2930 init_update_ssa (struct function *fn) 2931 { 2932 /* Reserve more space than the current number of names. The calls to 2933 add_new_name_mapping are typically done after creating new SSA 2934 names, so we'll need to reallocate these arrays. */ 2935 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR); 2936 bitmap_clear (old_ssa_names); 2937 2938 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR); 2939 bitmap_clear (new_ssa_names); 2940 2941 bitmap_obstack_initialize (&update_ssa_obstack); 2942 2943 names_to_release = NULL; 2944 update_ssa_initialized_fn = fn; 2945 } 2946 2947 2948 /* Deallocate data structures used for incremental SSA updates. */ 2949 2950 void 2951 delete_update_ssa (void) 2952 { 2953 unsigned i; 2954 bitmap_iterator bi; 2955 2956 sbitmap_free (old_ssa_names); 2957 old_ssa_names = NULL; 2958 2959 sbitmap_free (new_ssa_names); 2960 new_ssa_names = NULL; 2961 2962 BITMAP_FREE (symbols_to_rename_set); 2963 symbols_to_rename_set = NULL; 2964 symbols_to_rename.release (); 2965 2966 if (names_to_release) 2967 { 2968 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi) 2969 release_ssa_name (ssa_name (i)); 2970 BITMAP_FREE (names_to_release); 2971 } 2972 2973 clear_ssa_name_info (); 2974 2975 fini_ssa_renamer (); 2976 2977 if (blocks_with_phis_to_rewrite) 2978 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi) 2979 phis_to_rewrite[i].release (); 2980 2981 BITMAP_FREE (blocks_with_phis_to_rewrite); 2982 BITMAP_FREE (blocks_to_update); 2983 2984 update_ssa_initialized_fn = NULL; 2985 } 2986 2987 2988 /* Create a new name for OLD_NAME in statement STMT and replace the 2989 operand pointed to by DEF_P with the newly created name. If DEF_P 2990 is NULL then STMT should be a GIMPLE assignment. 2991 Return the new name and register the replacement mapping <NEW, OLD> in 2992 update_ssa's tables. */ 2993 2994 tree 2995 create_new_def_for (tree old_name, gimple *stmt, def_operand_p def) 2996 { 2997 tree new_name; 2998 2999 timevar_push (TV_TREE_SSA_INCREMENTAL); 3000 3001 if (!update_ssa_initialized_fn) 3002 init_update_ssa (cfun); 3003 3004 gcc_assert (update_ssa_initialized_fn == cfun); 3005 3006 new_name = duplicate_ssa_name (old_name, stmt); 3007 if (def) 3008 SET_DEF (def, new_name); 3009 else 3010 gimple_assign_set_lhs (stmt, new_name); 3011 3012 if (gimple_code (stmt) == GIMPLE_PHI) 3013 { 3014 basic_block bb = gimple_bb (stmt); 3015 3016 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */ 3017 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb); 3018 } 3019 3020 add_new_name_mapping (new_name, old_name); 3021 3022 /* For the benefit of passes that will be updating the SSA form on 3023 their own, set the current reaching definition of OLD_NAME to be 3024 NEW_NAME. */ 3025 get_ssa_name_ann (old_name)->info.current_def = new_name; 3026 3027 timevar_pop (TV_TREE_SSA_INCREMENTAL); 3028 3029 return new_name; 3030 } 3031 3032 3033 /* Mark virtual operands of FN for renaming by update_ssa. */ 3034 3035 void 3036 mark_virtual_operands_for_renaming (struct function *fn) 3037 { 3038 fn->gimple_df->ssa_renaming_needed = 1; 3039 fn->gimple_df->rename_vops = 1; 3040 } 3041 3042 /* Replace all uses of NAME by underlying variable and mark it 3043 for renaming. This assumes the defining statement of NAME is 3044 going to be removed. */ 3045 3046 void 3047 mark_virtual_operand_for_renaming (tree name) 3048 { 3049 tree name_var = SSA_NAME_VAR (name); 3050 bool used = false; 3051 imm_use_iterator iter; 3052 use_operand_p use_p; 3053 gimple *stmt; 3054 3055 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var)); 3056 FOR_EACH_IMM_USE_STMT (stmt, iter, name) 3057 { 3058 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 3059 SET_USE (use_p, name_var); 3060 used = true; 3061 } 3062 if (used) 3063 mark_virtual_operands_for_renaming (cfun); 3064 } 3065 3066 /* Replace all uses of the virtual PHI result by its underlying variable 3067 and mark it for renaming. This assumes the PHI node is going to be 3068 removed. */ 3069 3070 void 3071 mark_virtual_phi_result_for_renaming (gphi *phi) 3072 { 3073 if (dump_file && (dump_flags & TDF_DETAILS)) 3074 { 3075 fprintf (dump_file, "Marking result for renaming : "); 3076 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 3077 fprintf (dump_file, "\n"); 3078 } 3079 3080 mark_virtual_operand_for_renaming (gimple_phi_result (phi)); 3081 } 3082 3083 /* Return true if there is any work to be done by update_ssa 3084 for function FN. */ 3085 3086 bool 3087 need_ssa_update_p (struct function *fn) 3088 { 3089 gcc_assert (fn != NULL); 3090 return (update_ssa_initialized_fn == fn 3091 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed)); 3092 } 3093 3094 /* Return true if name N has been registered in the replacement table. */ 3095 3096 bool 3097 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED) 3098 { 3099 if (!update_ssa_initialized_fn) 3100 return false; 3101 3102 gcc_assert (update_ssa_initialized_fn == cfun); 3103 3104 return is_new_name (n) || is_old_name (n); 3105 } 3106 3107 3108 /* Mark NAME to be released after update_ssa has finished. */ 3109 3110 void 3111 release_ssa_name_after_update_ssa (tree name) 3112 { 3113 gcc_assert (cfun && update_ssa_initialized_fn == cfun); 3114 3115 if (names_to_release == NULL) 3116 names_to_release = BITMAP_ALLOC (NULL); 3117 3118 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name)); 3119 } 3120 3121 3122 /* Insert new PHI nodes to replace VAR. DFS contains dominance 3123 frontier information. BLOCKS is the set of blocks to be updated. 3124 3125 This is slightly different than the regular PHI insertion 3126 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for 3127 real names (i.e., GIMPLE registers) are inserted: 3128 3129 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI 3130 nodes inside the region affected by the block that defines VAR 3131 and the blocks that define all its replacements. All these 3132 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS. 3133 3134 First, we compute the entry point to the region (ENTRY). This is 3135 given by the nearest common dominator to all the definition 3136 blocks. When computing the iterated dominance frontier (IDF), any 3137 block not strictly dominated by ENTRY is ignored. 3138 3139 We then call the standard PHI insertion algorithm with the pruned 3140 IDF. 3141 3142 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real 3143 names is not pruned. PHI nodes are inserted at every IDF block. */ 3144 3145 static void 3146 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks, 3147 unsigned update_flags) 3148 { 3149 basic_block entry; 3150 def_blocks *db; 3151 bitmap idf, pruned_idf; 3152 bitmap_iterator bi; 3153 unsigned i; 3154 3155 if (TREE_CODE (var) == SSA_NAME) 3156 gcc_checking_assert (is_old_name (var)); 3157 else 3158 gcc_checking_assert (marked_for_renaming (var)); 3159 3160 /* Get all the definition sites for VAR. */ 3161 db = find_def_blocks_for (var); 3162 3163 /* No need to do anything if there were no definitions to VAR. */ 3164 if (db == NULL || bitmap_empty_p (db->def_blocks)) 3165 return; 3166 3167 /* Compute the initial iterated dominance frontier. */ 3168 idf = compute_idf (db->def_blocks, dfs); 3169 pruned_idf = BITMAP_ALLOC (NULL); 3170 3171 if (TREE_CODE (var) == SSA_NAME) 3172 { 3173 if (update_flags == TODO_update_ssa) 3174 { 3175 /* If doing regular SSA updates for GIMPLE registers, we are 3176 only interested in IDF blocks dominated by the nearest 3177 common dominator of all the definition blocks. */ 3178 entry = nearest_common_dominator_for_set (CDI_DOMINATORS, 3179 db->def_blocks); 3180 if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun)) 3181 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi) 3182 if (BASIC_BLOCK_FOR_FN (cfun, i) != entry 3183 && dominated_by_p (CDI_DOMINATORS, 3184 BASIC_BLOCK_FOR_FN (cfun, i), entry)) 3185 bitmap_set_bit (pruned_idf, i); 3186 } 3187 else 3188 { 3189 /* Otherwise, do not prune the IDF for VAR. */ 3190 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi); 3191 bitmap_copy (pruned_idf, idf); 3192 } 3193 } 3194 else 3195 { 3196 /* Otherwise, VAR is a symbol that needs to be put into SSA form 3197 for the first time, so we need to compute the full IDF for 3198 it. */ 3199 bitmap_copy (pruned_idf, idf); 3200 } 3201 3202 if (!bitmap_empty_p (pruned_idf)) 3203 { 3204 /* Make sure that PRUNED_IDF blocks and all their feeding blocks 3205 are included in the region to be updated. The feeding blocks 3206 are important to guarantee that the PHI arguments are renamed 3207 properly. */ 3208 3209 /* FIXME, this is not needed if we are updating symbols. We are 3210 already starting at the ENTRY block anyway. */ 3211 bitmap_ior_into (blocks, pruned_idf); 3212 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi) 3213 { 3214 edge e; 3215 edge_iterator ei; 3216 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); 3217 3218 FOR_EACH_EDGE (e, ei, bb->preds) 3219 if (e->src->index >= 0) 3220 bitmap_set_bit (blocks, e->src->index); 3221 } 3222 3223 insert_phi_nodes_for (var, pruned_idf, true); 3224 } 3225 3226 BITMAP_FREE (pruned_idf); 3227 BITMAP_FREE (idf); 3228 } 3229 3230 /* Sort symbols_to_rename after their DECL_UID. */ 3231 3232 static int 3233 insert_updated_phi_nodes_compare_uids (const void *a, const void *b) 3234 { 3235 const_tree syma = *(const const_tree *)a; 3236 const_tree symb = *(const const_tree *)b; 3237 if (DECL_UID (syma) == DECL_UID (symb)) 3238 return 0; 3239 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1; 3240 } 3241 3242 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of 3243 existing SSA names (OLD_SSA_NAMES), update the SSA form so that: 3244 3245 1- The names in OLD_SSA_NAMES dominated by the definitions of 3246 NEW_SSA_NAMES are all re-written to be reached by the 3247 appropriate definition from NEW_SSA_NAMES. 3248 3249 2- If needed, new PHI nodes are added to the iterated dominance 3250 frontier of the blocks where each of NEW_SSA_NAMES are defined. 3251 3252 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by 3253 calling create_new_def_for to create new defs for names that the 3254 caller wants to replace. 3255 3256 The caller cretaes the new names to be inserted and the names that need 3257 to be replaced by calling create_new_def_for for each old definition 3258 to be replaced. Note that the function assumes that the 3259 new defining statement has already been inserted in the IL. 3260 3261 For instance, given the following code: 3262 3263 1 L0: 3264 2 x_1 = PHI (0, x_5) 3265 3 if (x_1 < 10) 3266 4 if (x_1 > 7) 3267 5 y_2 = 0 3268 6 else 3269 7 y_3 = x_1 + x_7 3270 8 endif 3271 9 x_5 = x_1 + 1 3272 10 goto L0; 3273 11 endif 3274 3275 Suppose that we insert new names x_10 and x_11 (lines 4 and 8). 3276 3277 1 L0: 3278 2 x_1 = PHI (0, x_5) 3279 3 if (x_1 < 10) 3280 4 x_10 = ... 3281 5 if (x_1 > 7) 3282 6 y_2 = 0 3283 7 else 3284 8 x_11 = ... 3285 9 y_3 = x_1 + x_7 3286 10 endif 3287 11 x_5 = x_1 + 1 3288 12 goto L0; 3289 13 endif 3290 3291 We want to replace all the uses of x_1 with the new definitions of 3292 x_10 and x_11. Note that the only uses that should be replaced are 3293 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should 3294 *not* be replaced (this is why we cannot just mark symbol 'x' for 3295 renaming). 3296 3297 Additionally, we may need to insert a PHI node at line 11 because 3298 that is a merge point for x_10 and x_11. So the use of x_1 at line 3299 11 will be replaced with the new PHI node. The insertion of PHI 3300 nodes is optional. They are not strictly necessary to preserve the 3301 SSA form, and depending on what the caller inserted, they may not 3302 even be useful for the optimizers. UPDATE_FLAGS controls various 3303 aspects of how update_ssa operates, see the documentation for 3304 TODO_update_ssa*. */ 3305 3306 void 3307 update_ssa (unsigned update_flags) 3308 { 3309 basic_block bb, start_bb; 3310 bitmap_iterator bi; 3311 unsigned i = 0; 3312 bool insert_phi_p; 3313 sbitmap_iterator sbi; 3314 tree sym; 3315 3316 /* Only one update flag should be set. */ 3317 gcc_assert (update_flags == TODO_update_ssa 3318 || update_flags == TODO_update_ssa_no_phi 3319 || update_flags == TODO_update_ssa_full_phi 3320 || update_flags == TODO_update_ssa_only_virtuals); 3321 3322 if (!need_ssa_update_p (cfun)) 3323 return; 3324 3325 if (flag_checking) 3326 { 3327 timevar_push (TV_TREE_STMT_VERIFY); 3328 3329 bool err = false; 3330 3331 FOR_EACH_BB_FN (bb, cfun) 3332 { 3333 gimple_stmt_iterator gsi; 3334 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 3335 { 3336 gimple *stmt = gsi_stmt (gsi); 3337 3338 ssa_op_iter i; 3339 use_operand_p use_p; 3340 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES) 3341 { 3342 tree use = USE_FROM_PTR (use_p); 3343 if (TREE_CODE (use) != SSA_NAME) 3344 continue; 3345 3346 if (SSA_NAME_IN_FREE_LIST (use)) 3347 { 3348 error ("statement uses released SSA name"); 3349 debug_gimple_stmt (stmt); 3350 fprintf (stderr, "The use of "); 3351 print_generic_expr (stderr, use); 3352 fprintf (stderr," should have been replaced\n"); 3353 err = true; 3354 } 3355 } 3356 } 3357 } 3358 3359 if (err) 3360 internal_error ("cannot update SSA form"); 3361 3362 timevar_pop (TV_TREE_STMT_VERIFY); 3363 } 3364 3365 timevar_push (TV_TREE_SSA_INCREMENTAL); 3366 3367 if (dump_file && (dump_flags & TDF_DETAILS)) 3368 fprintf (dump_file, "\nUpdating SSA:\n"); 3369 3370 if (!update_ssa_initialized_fn) 3371 init_update_ssa (cfun); 3372 else if (update_flags == TODO_update_ssa_only_virtuals) 3373 { 3374 /* If we only need to update virtuals, remove all the mappings for 3375 real names before proceeding. The caller is responsible for 3376 having dealt with the name mappings before calling update_ssa. */ 3377 bitmap_clear (old_ssa_names); 3378 bitmap_clear (new_ssa_names); 3379 } 3380 3381 gcc_assert (update_ssa_initialized_fn == cfun); 3382 3383 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL); 3384 if (!phis_to_rewrite.exists ()) 3385 phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1); 3386 blocks_to_update = BITMAP_ALLOC (NULL); 3387 3388 /* Ensure that the dominance information is up-to-date. */ 3389 calculate_dominance_info (CDI_DOMINATORS); 3390 3391 insert_phi_p = (update_flags != TODO_update_ssa_no_phi); 3392 3393 /* If there are names defined in the replacement table, prepare 3394 definition and use sites for all the names in NEW_SSA_NAMES and 3395 OLD_SSA_NAMES. */ 3396 if (bitmap_first_set_bit (new_ssa_names) >= 0) 3397 { 3398 statistics_counter_event (cfun, "Incremental SSA update", 1); 3399 3400 prepare_names_to_update (insert_phi_p); 3401 3402 /* If all the names in NEW_SSA_NAMES had been marked for 3403 removal, and there are no symbols to rename, then there's 3404 nothing else to do. */ 3405 if (bitmap_first_set_bit (new_ssa_names) < 0 3406 && !cfun->gimple_df->ssa_renaming_needed) 3407 goto done; 3408 } 3409 3410 /* Next, determine the block at which to start the renaming process. */ 3411 if (cfun->gimple_df->ssa_renaming_needed) 3412 { 3413 statistics_counter_event (cfun, "Symbol to SSA rewrite", 1); 3414 3415 /* If we rename bare symbols initialize the mapping to 3416 auxiliar info we need to keep track of. */ 3417 var_infos = new hash_table<var_info_hasher> (47); 3418 3419 /* If we have to rename some symbols from scratch, we need to 3420 start the process at the root of the CFG. FIXME, it should 3421 be possible to determine the nearest block that had a 3422 definition for each of the symbols that are marked for 3423 updating. For now this seems more work than it's worth. */ 3424 start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); 3425 3426 /* Traverse the CFG looking for existing definitions and uses of 3427 symbols in SSA operands. Mark interesting blocks and 3428 statements and set local live-in information for the PHI 3429 placement heuristics. */ 3430 prepare_block_for_update (start_bb, insert_phi_p); 3431 3432 tree name; 3433 3434 if (flag_checking) 3435 FOR_EACH_SSA_NAME (i, name, cfun) 3436 { 3437 if (virtual_operand_p (name)) 3438 continue; 3439 3440 /* For all but virtual operands, which do not have SSA names 3441 with overlapping life ranges, ensure that symbols marked 3442 for renaming do not have existing SSA names associated with 3443 them as we do not re-write them out-of-SSA before going 3444 into SSA for the remaining symbol uses. */ 3445 if (marked_for_renaming (SSA_NAME_VAR (name))) 3446 { 3447 fprintf (stderr, "Existing SSA name for symbol marked for " 3448 "renaming: "); 3449 print_generic_expr (stderr, name, TDF_SLIM); 3450 fprintf (stderr, "\n"); 3451 internal_error ("SSA corruption"); 3452 } 3453 } 3454 } 3455 else 3456 { 3457 /* Otherwise, the entry block to the region is the nearest 3458 common dominator for the blocks in BLOCKS. */ 3459 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, 3460 blocks_to_update); 3461 } 3462 3463 /* If requested, insert PHI nodes at the iterated dominance frontier 3464 of every block, creating new definitions for names in OLD_SSA_NAMES 3465 and for symbols found. */ 3466 if (insert_phi_p) 3467 { 3468 bitmap_head *dfs; 3469 3470 /* If the caller requested PHI nodes to be added, compute 3471 dominance frontiers. */ 3472 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 3473 FOR_EACH_BB_FN (bb, cfun) 3474 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack); 3475 compute_dominance_frontiers (dfs); 3476 3477 if (bitmap_first_set_bit (old_ssa_names) >= 0) 3478 { 3479 sbitmap_iterator sbi; 3480 3481 /* insert_update_phi_nodes_for will call add_new_name_mapping 3482 when inserting new PHI nodes, so the set OLD_SSA_NAMES 3483 will grow while we are traversing it (but it will not 3484 gain any new members). Copy OLD_SSA_NAMES to a temporary 3485 for traversal. */ 3486 auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names)); 3487 bitmap_copy (tmp, old_ssa_names); 3488 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi) 3489 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update, 3490 update_flags); 3491 } 3492 3493 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids); 3494 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym) 3495 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update, 3496 update_flags); 3497 3498 FOR_EACH_BB_FN (bb, cfun) 3499 bitmap_clear (&dfs[bb->index]); 3500 free (dfs); 3501 3502 /* Insertion of PHI nodes may have added blocks to the region. 3503 We need to re-compute START_BB to include the newly added 3504 blocks. */ 3505 if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)) 3506 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, 3507 blocks_to_update); 3508 } 3509 3510 /* Reset the current definition for name and symbol before renaming 3511 the sub-graph. */ 3512 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi) 3513 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE; 3514 3515 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym) 3516 get_var_info (sym)->info.current_def = NULL_TREE; 3517 3518 /* Now start the renaming process at START_BB. */ 3519 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun)); 3520 bitmap_clear (interesting_blocks); 3521 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) 3522 bitmap_set_bit (interesting_blocks, i); 3523 3524 rewrite_blocks (start_bb, REWRITE_UPDATE); 3525 3526 sbitmap_free (interesting_blocks); 3527 3528 /* Debugging dumps. */ 3529 if (dump_file) 3530 { 3531 int c; 3532 unsigned i; 3533 3534 dump_update_ssa (dump_file); 3535 3536 fprintf (dump_file, "Incremental SSA update started at block: %d\n", 3537 start_bb->index); 3538 3539 c = 0; 3540 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) 3541 c++; 3542 fprintf (dump_file, "Number of blocks in CFG: %d\n", 3543 last_basic_block_for_fn (cfun)); 3544 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n", 3545 c, PERCENT (c, last_basic_block_for_fn (cfun))); 3546 3547 if (dump_flags & TDF_DETAILS) 3548 { 3549 fprintf (dump_file, "Affected blocks:"); 3550 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) 3551 fprintf (dump_file, " %u", i); 3552 fprintf (dump_file, "\n"); 3553 } 3554 3555 fprintf (dump_file, "\n\n"); 3556 } 3557 3558 /* Free allocated memory. */ 3559 done: 3560 delete_update_ssa (); 3561 3562 timevar_pop (TV_TREE_SSA_INCREMENTAL); 3563 } 3564