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