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