1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "tree-flow.h"
40 #include "tree-inline.h"
44 #include "tree-dump.h"
45 #include "tree-pass.h"
53 /* This file builds the SSA form for a function as described in:
54 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
55 Computing Static Single Assignment Form and the Control Dependence
56 Graph. ACM Transactions on Programming Languages and Systems,
57 13(4):451-490, October 1991. */
59 /* Structure to map a variable VAR to the set of blocks that contain
60 definitions for VAR. */
66 /* Blocks that contain definitions of VAR. Bit I will be set if the
67 Ith block contains a definition of VAR. */
70 /* Blocks that contain a PHI node for VAR. */
73 /* Blocks where VAR is live-on-entry. Similar semantics as
79 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
80 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
81 basic blocks where VAR is defined (assigned a new value). It also
82 contains a bitmap of all the blocks where VAR is live-on-entry
83 (i.e., there is a use of VAR in block B without a preceding
84 definition in B). The live-on-entry information is used when
85 computing PHI pruning heuristics. */
86 static htab_t def_blocks;
88 /* Stack of trees used to restore the global currdefs to its original
89 state after completing rewriting of a block and its dominator
90 children. Its elements have the following properties:
92 - An SSA_NAME (N) indicates that the current definition of the
93 underlying variable should be set to the given SSA_NAME. If the
94 symbol associated with the SSA_NAME is not a GIMPLE register, the
95 next slot in the stack must be a _DECL node (SYM). In this case,
96 the name N in the previous slot is the current reaching
99 - A _DECL node indicates that the underlying variable has no
102 - A NULL node at the top entry is used to mark the last slot
103 associated with the current block. */
104 static VEC(tree,heap) *block_defs_stack;
107 /* Set of existing SSA names being replaced by update_ssa. */
108 static sbitmap old_ssa_names;
110 /* Set of new SSA names being added by update_ssa. Note that both
111 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
112 the operations done on them are presence tests. */
113 static sbitmap new_ssa_names;
116 /* Subset of SYMS_TO_RENAME. Contains all the GIMPLE register symbols
117 that have been marked for renaming. */
118 static bitmap regs_to_rename;
120 /* Subset of SYMS_TO_RENAME. Contains all the memory symbols
121 that have been marked for renaming. */
122 static bitmap mem_syms_to_rename;
124 /* Set of SSA names that have been marked to be released after they
125 were registered in the replacement table. They will be finally
126 released after we finish updating the SSA web. */
127 static bitmap names_to_release;
129 static VEC(gimple_vec, heap) *phis_to_rewrite;
131 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
132 static bitmap blocks_with_phis_to_rewrite;
134 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
135 to grow as the callers to register_new_name_mapping will typically
136 create new names on the fly. FIXME. Currently set to 1/3 to avoid
137 frequent reallocations but still need to find a reasonable growth
139 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
141 /* Tuple used to represent replacement mappings. */
149 /* NEW -> OLD_SET replacement table. If we are replacing several
150 existing SSA names O_1, O_2, ..., O_j with a new name N_i,
151 then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */
152 static htab_t repl_tbl;
154 /* The function the SSA updating data structures have been initialized for.
155 NULL if they need to be initialized by register_new_name_mapping. */
156 static struct function *update_ssa_initialized_fn = NULL;
158 /* Statistics kept by update_ssa to use in the virtual mapping
159 heuristic. If the number of virtual mappings is beyond certain
160 threshold, the updater will switch from using the mappings into
161 renaming the virtual symbols from scratch. In some cases, the
162 large number of name mappings for virtual names causes significant
163 slowdowns in the PHI insertion code. */
164 struct update_ssa_stats_d
166 unsigned num_virtual_mappings;
167 unsigned num_total_mappings;
168 bitmap virtual_symbols;
169 unsigned num_virtual_symbols;
171 static struct update_ssa_stats_d update_ssa_stats;
173 /* Global data to attach to the main dominator walk structure. */
174 struct mark_def_sites_global_data
176 /* This bitmap contains the variables which are set before they
177 are used in a basic block. */
180 /* Bitmap of names to rename. */
181 sbitmap names_to_rename;
183 /* Set of blocks that mark_def_sites deems interesting for the
184 renamer to process. */
185 sbitmap interesting_blocks;
189 /* Information stored for SSA names. */
192 /* The current reaching definition replacing this SSA name. */
195 /* This field indicates whether or not the variable may need PHI nodes.
196 See the enum's definition for more detailed information about the
198 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
200 /* Age of this record (so that info_for_ssa_name table can be cleared
201 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
202 are assumed to be null. */
206 /* The information associated with names. */
207 typedef struct ssa_name_info *ssa_name_info_p;
208 DEF_VEC_P (ssa_name_info_p);
209 DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
211 static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
212 static unsigned current_info_for_ssa_name_age;
214 /* The set of blocks affected by update_ssa. */
215 static bitmap blocks_to_update;
217 /* The main entry point to the SSA renamer (rewrite_blocks) may be
218 called several times to do different, but related, tasks.
219 Initially, we need it to rename the whole program into SSA form.
220 At other times, we may need it to only rename into SSA newly
221 exposed symbols. Finally, we can also call it to incrementally fix
222 an already built SSA web. */
224 /* Convert the whole function into SSA form. */
227 /* Incrementally update the SSA web by replacing existing SSA
228 names with new ones. See update_ssa for details. */
235 /* Prototypes for debugging functions. */
236 extern void dump_tree_ssa (FILE *);
237 extern void debug_tree_ssa (void);
238 extern void debug_def_blocks (void);
239 extern void dump_tree_ssa_stats (FILE *);
240 extern void debug_tree_ssa_stats (void);
241 extern void dump_update_ssa (FILE *);
242 extern void debug_update_ssa (void);
243 extern void dump_names_replaced_by (FILE *, tree);
244 extern void debug_names_replaced_by (tree);
245 extern void dump_def_blocks (FILE *);
246 extern void debug_def_blocks (void);
247 extern void dump_defs_stack (FILE *, int);
248 extern void debug_defs_stack (int);
249 extern void dump_currdefs (FILE *);
250 extern void debug_currdefs (void);
252 /* Return true if STMT needs to be rewritten. When renaming a subset
253 of the variables, not all statements will be processed. This is
254 decided in mark_def_sites. */
257 rewrite_uses_p (gimple stmt)
259 return gimple_visited_p (stmt);
263 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
266 set_rewrite_uses (gimple stmt, bool rewrite_p)
268 gimple_set_visited (stmt, rewrite_p);
272 /* Return true if the DEFs created by statement STMT should be
273 registered when marking new definition sites. This is slightly
274 different than rewrite_uses_p: it's used by update_ssa to
275 distinguish statements that need to have both uses and defs
276 processed from those that only need to have their defs processed.
277 Statements that define new SSA names only need to have their defs
278 registered, but they don't need to have their uses renamed. */
281 register_defs_p (gimple stmt)
283 return gimple_plf (stmt, GF_PLF_1) != 0;
287 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
290 set_register_defs (gimple stmt, bool register_defs_p)
292 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
296 /* Get the information associated with NAME. */
298 static inline ssa_name_info_p
299 get_ssa_name_ann (tree name)
301 unsigned ver = SSA_NAME_VERSION (name);
302 unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
303 struct ssa_name_info *info;
307 unsigned new_len = num_ssa_names;
309 VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
310 while (len++ < new_len)
312 struct ssa_name_info *info = XCNEW (struct ssa_name_info);
313 info->age = current_info_for_ssa_name_age;
314 VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
318 info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
319 if (info->age < current_info_for_ssa_name_age)
321 info->need_phi_state = 0;
322 info->current_def = NULL_TREE;
323 info->age = current_info_for_ssa_name_age;
330 /* Clears info for SSA names. */
333 clear_ssa_name_info (void)
335 current_info_for_ssa_name_age++;
339 /* Get phi_state field for VAR. */
341 static inline enum need_phi_state
342 get_phi_state (tree var)
344 if (TREE_CODE (var) == SSA_NAME)
345 return get_ssa_name_ann (var)->need_phi_state;
347 return var_ann (var)->need_phi_state;
351 /* Sets phi_state field for VAR to STATE. */
354 set_phi_state (tree var, enum need_phi_state state)
356 if (TREE_CODE (var) == SSA_NAME)
357 get_ssa_name_ann (var)->need_phi_state = state;
359 var_ann (var)->need_phi_state = state;
363 /* Return the current definition for VAR. */
366 get_current_def (tree var)
368 if (TREE_CODE (var) == SSA_NAME)
369 return get_ssa_name_ann (var)->current_def;
371 return var_ann (var)->current_def;
375 /* Sets current definition of VAR to DEF. */
378 set_current_def (tree var, tree def)
380 if (TREE_CODE (var) == SSA_NAME)
381 get_ssa_name_ann (var)->current_def = def;
383 var_ann (var)->current_def = def;
387 /* Compute global livein information given the set of blocks where
388 an object is locally live at the start of the block (LIVEIN)
389 and the set of blocks where the object is defined (DEF_BLOCKS).
391 Note: This routine augments the existing local livein information
392 to include global livein (i.e., it modifies the underlying bitmap
396 compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED)
398 basic_block bb, *worklist, *tos;
403 = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
405 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
406 *tos++ = BASIC_BLOCK (i);
408 /* Iterate until the worklist is empty. */
409 while (tos != worklist)
414 /* Pull a block off the worklist. */
417 /* For each predecessor block. */
418 FOR_EACH_EDGE (e, ei, bb->preds)
420 basic_block pred = e->src;
421 int pred_index = pred->index;
423 /* None of this is necessary for the entry block. */
424 if (pred != ENTRY_BLOCK_PTR
425 && ! bitmap_bit_p (livein, pred_index)
426 && ! bitmap_bit_p (def_blocks, pred_index))
429 bitmap_set_bit (livein, pred_index);
438 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
439 all statements in basic block BB. */
442 initialize_flags_in_bb (basic_block bb)
445 gimple_stmt_iterator gsi;
447 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
449 gimple phi = gsi_stmt (gsi);
450 set_rewrite_uses (phi, false);
451 set_register_defs (phi, false);
454 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
456 stmt = gsi_stmt (gsi);
458 /* We are going to use the operand cache API, such as
459 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
460 cache for each statement should be up-to-date. */
461 gcc_assert (!gimple_modified_p (stmt));
462 set_rewrite_uses (stmt, false);
463 set_register_defs (stmt, false);
467 /* Mark block BB as interesting for update_ssa. */
470 mark_block_for_update (basic_block bb)
472 gcc_assert (blocks_to_update != NULL);
473 if (bitmap_bit_p (blocks_to_update, bb->index))
475 bitmap_set_bit (blocks_to_update, bb->index);
476 initialize_flags_in_bb (bb);
479 /* Return the set of blocks where variable VAR is defined and the blocks
480 where VAR is live on entry (livein). If no entry is found in
481 DEF_BLOCKS, a new one is created and returned. */
483 static inline struct def_blocks_d *
484 get_def_blocks_for (tree var)
486 struct def_blocks_d db, *db_p;
490 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
493 db_p = XNEW (struct def_blocks_d);
495 db_p->def_blocks = BITMAP_ALLOC (NULL);
496 db_p->phi_blocks = BITMAP_ALLOC (NULL);
497 db_p->livein_blocks = BITMAP_ALLOC (NULL);
498 *slot = (void *) db_p;
501 db_p = (struct def_blocks_d *) *slot;
507 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
508 VAR is defined by a PHI node. */
511 set_def_block (tree var, basic_block bb, bool phi_p)
513 struct def_blocks_d *db_p;
514 enum need_phi_state state;
516 state = get_phi_state (var);
517 db_p = get_def_blocks_for (var);
519 /* Set the bit corresponding to the block where VAR is defined. */
520 bitmap_set_bit (db_p->def_blocks, bb->index);
522 bitmap_set_bit (db_p->phi_blocks, bb->index);
524 /* Keep track of whether or not we may need to insert PHI nodes.
526 If we are in the UNKNOWN state, then this is the first definition
527 of VAR. Additionally, we have not seen any uses of VAR yet, so
528 we do not need a PHI node for this variable at this time (i.e.,
529 transition to NEED_PHI_STATE_NO).
531 If we are in any other state, then we either have multiple definitions
532 of this variable occurring in different blocks or we saw a use of the
533 variable which was not dominated by the block containing the
534 definition(s). In this case we may need a PHI node, so enter
535 state NEED_PHI_STATE_MAYBE. */
536 if (state == NEED_PHI_STATE_UNKNOWN)
537 set_phi_state (var, NEED_PHI_STATE_NO);
539 set_phi_state (var, NEED_PHI_STATE_MAYBE);
543 /* Mark block BB as having VAR live at the entry to BB. */
546 set_livein_block (tree var, basic_block bb)
548 struct def_blocks_d *db_p;
549 enum need_phi_state state = get_phi_state (var);
551 db_p = get_def_blocks_for (var);
553 /* Set the bit corresponding to the block where VAR is live in. */
554 bitmap_set_bit (db_p->livein_blocks, bb->index);
556 /* Keep track of whether or not we may need to insert PHI nodes.
558 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
559 by the single block containing the definition(s) of this variable. If
560 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
561 NEED_PHI_STATE_MAYBE. */
562 if (state == NEED_PHI_STATE_NO)
564 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
566 if (def_block_index == -1
567 || ! dominated_by_p (CDI_DOMINATORS, bb,
568 BASIC_BLOCK (def_block_index)))
569 set_phi_state (var, NEED_PHI_STATE_MAYBE);
572 set_phi_state (var, NEED_PHI_STATE_MAYBE);
576 /* Return true if symbol SYM is marked for renaming. */
579 symbol_marked_for_renaming (tree sym)
581 return bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (sym));
585 /* Return true if NAME is in OLD_SSA_NAMES. */
588 is_old_name (tree name)
590 unsigned ver = SSA_NAME_VERSION (name);
593 return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
597 /* Return true if NAME is in NEW_SSA_NAMES. */
600 is_new_name (tree name)
602 unsigned ver = SSA_NAME_VERSION (name);
605 return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
609 /* Hashing and equality functions for REPL_TBL. */
612 repl_map_hash (const void *p)
614 return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
618 repl_map_eq (const void *p1, const void *p2)
620 return ((const struct repl_map_d *)p1)->name
621 == ((const struct repl_map_d *)p2)->name;
625 repl_map_free (void *p)
627 BITMAP_FREE (((struct repl_map_d *)p)->set);
632 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
635 names_replaced_by (tree new_tree)
641 slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
643 /* If N was not registered in the replacement table, return NULL. */
644 if (slot == NULL || *slot == NULL)
647 return ((struct repl_map_d *) *slot)->set;
651 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
654 add_to_repl_tbl (tree new_tree, tree old)
656 struct repl_map_d m, *mp;
660 slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
663 mp = XNEW (struct repl_map_d);
665 mp->set = BITMAP_ALLOC (NULL);
669 mp = (struct repl_map_d *) *slot;
671 bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
675 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
676 represents the set of names O_1 ... O_j replaced by N_i. This is
677 used by update_ssa and its helpers to introduce new SSA names in an
678 already formed SSA web. */
681 add_new_name_mapping (tree new_tree, tree old)
683 timevar_push (TV_TREE_SSA_INCREMENTAL);
685 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
686 gcc_assert (new_tree != old && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
688 /* If this mapping is for virtual names, we will need to update
689 virtual operands. If this is a mapping for .MEM, then we gather
690 the symbols associated with each name. */
691 if (!is_gimple_reg (new_tree))
695 update_ssa_stats.num_virtual_mappings++;
696 update_ssa_stats.num_virtual_symbols++;
698 /* Keep counts of virtual mappings and symbols to use in the
699 virtual mapping heuristic. If we have large numbers of
700 virtual mappings for a relatively low number of symbols, it
701 will make more sense to rename the symbols from scratch.
702 Otherwise, the insertion of PHI nodes for each of the old
703 names in these mappings will be very slow. */
704 sym = SSA_NAME_VAR (new_tree);
705 bitmap_set_bit (update_ssa_stats.virtual_symbols, DECL_UID (sym));
708 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
709 caller may have created new names since the set was created. */
710 if (new_ssa_names->n_bits <= num_ssa_names - 1)
712 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
713 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
714 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
717 /* Update the REPL_TBL table. */
718 add_to_repl_tbl (new_tree, old);
720 /* If OLD had already been registered as a new name, then all the
721 names that OLD replaces should also be replaced by NEW_TREE. */
722 if (is_new_name (old))
723 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
725 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
727 SET_BIT (new_ssa_names, SSA_NAME_VERSION (new_tree));
728 SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
730 /* Update mapping counter to use in the virtual mapping heuristic. */
731 update_ssa_stats.num_total_mappings++;
733 timevar_pop (TV_TREE_SSA_INCREMENTAL);
737 /* Call back for walk_dominator_tree used to collect definition sites
738 for every variable in the function. For every statement S in block
741 1- Variables defined by S in the DEFS of S are marked in the bitmap
742 WALK_DATA->GLOBAL_DATA->KILLS.
744 2- If S uses a variable VAR and there is no preceding kill of VAR,
745 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
747 This information is used to determine which variables are live
748 across block boundaries to reduce the number of PHI nodes
752 mark_def_sites (struct dom_walk_data *walk_data, basic_block bb,
753 gimple_stmt_iterator gsi)
755 struct mark_def_sites_global_data *gd;
762 /* Since this is the first time that we rewrite the program into SSA
763 form, force an operand scan on every statement. */
764 stmt = gsi_stmt (gsi);
767 gd = (struct mark_def_sites_global_data *) walk_data->global_data;
770 gcc_assert (blocks_to_update == NULL);
771 set_register_defs (stmt, false);
772 set_rewrite_uses (stmt, false);
774 /* If a variable is used before being set, then the variable is live
775 across a block boundary, so mark it live-on-entry to BB. */
776 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
778 tree sym = USE_FROM_PTR (use_p);
779 gcc_assert (DECL_P (sym));
780 if (!bitmap_bit_p (kills, DECL_UID (sym)))
781 set_livein_block (sym, bb);
782 set_rewrite_uses (stmt, true);
785 /* Now process the defs. Mark BB as the definition block and add
786 each def to the set of killed symbols. */
787 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
789 gcc_assert (DECL_P (def));
790 set_def_block (def, bb, false);
791 bitmap_set_bit (kills, DECL_UID (def));
792 set_register_defs (stmt, true);
795 /* If we found the statement interesting then also mark the block BB
797 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
798 SET_BIT (gd->interesting_blocks, bb->index);
801 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
802 in the dfs numbering of the dominance tree. */
806 /* Basic block whose index this entry corresponds to. */
809 /* The dfs number of this node. */
813 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
817 cmp_dfsnum (const void *a, const void *b)
819 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
820 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
822 return (int) da->dfs_num - (int) db->dfs_num;
825 /* Among the intervals starting at the N points specified in DEFS, find
826 the one that contains S, and return its bb_index. */
829 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
831 unsigned f = 0, t = n, m;
836 if (defs[m].dfs_num <= s)
842 return defs[f].bb_index;
845 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
846 KILLS is a bitmap of blocks where the value is defined before any use. */
849 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
851 VEC(int, heap) *worklist;
853 unsigned i, b, p, u, top;
855 basic_block def_bb, use_bb;
859 struct dom_dfsnum *defs;
860 unsigned n_defs, adef;
862 if (bitmap_empty_p (uses))
868 /* The phi must dominate a use, or an argument of a live phi. Also, we
869 do not create any phi nodes in def blocks, unless they are also livein. */
870 to_remove = BITMAP_ALLOC (NULL);
871 bitmap_and_compl (to_remove, kills, uses);
872 bitmap_and_compl_into (phis, to_remove);
873 if (bitmap_empty_p (phis))
875 BITMAP_FREE (to_remove);
879 /* We want to remove the unnecessary phi nodes, but we do not want to compute
880 liveness information, as that may be linear in the size of CFG, and if
881 there are lot of different variables to rewrite, this may lead to quadratic
884 Instead, we basically emulate standard dce. We put all uses to worklist,
885 then for each of them find the nearest def that dominates them. If this
886 def is a phi node, we mark it live, and if it was not live before, we
887 add the predecessors of its basic block to the worklist.
889 To quickly locate the nearest def that dominates use, we use dfs numbering
890 of the dominance tree (that is already available in order to speed up
891 queries). For each def, we have the interval given by the dfs number on
892 entry to and on exit from the corresponding subtree in the dominance tree.
893 The nearest dominator for a given use is the smallest of these intervals
894 that contains entry and exit dfs numbers for the basic block with the use.
895 If we store the bounds for all the uses to an array and sort it, we can
896 locate the nearest dominating def in logarithmic time by binary search.*/
897 bitmap_ior (to_remove, kills, phis);
898 n_defs = bitmap_count_bits (to_remove);
899 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
900 defs[0].bb_index = 1;
903 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
905 def_bb = BASIC_BLOCK (i);
906 defs[adef].bb_index = i;
907 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
908 defs[adef + 1].bb_index = i;
909 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
912 BITMAP_FREE (to_remove);
913 gcc_assert (adef == 2 * n_defs + 1);
914 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
915 gcc_assert (defs[0].bb_index == 1);
917 /* Now each DEFS entry contains the number of the basic block to that the
918 dfs number corresponds. Change them to the number of basic block that
919 corresponds to the interval following the dfs number. Also, for the
920 dfs_out numbers, increase the dfs number by one (so that it corresponds
921 to the start of the following interval, not to the end of the current
922 one). We use WORKLIST as a stack. */
923 worklist = VEC_alloc (int, heap, n_defs + 1);
924 VEC_quick_push (int, worklist, 1);
927 for (i = 1; i < adef; i++)
929 b = defs[i].bb_index;
932 /* This is a closing element. Interval corresponding to the top
933 of the stack after removing it follows. */
934 VEC_pop (int, worklist);
935 top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
936 defs[n_defs].bb_index = top;
937 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
941 /* Opening element. Nothing to do, just push it to the stack and move
942 it to the correct position. */
943 defs[n_defs].bb_index = defs[i].bb_index;
944 defs[n_defs].dfs_num = defs[i].dfs_num;
945 VEC_quick_push (int, worklist, b);
949 /* If this interval starts at the same point as the previous one, cancel
951 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
952 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
956 VEC_pop (int, worklist);
957 gcc_assert (VEC_empty (int, worklist));
959 /* Now process the uses. */
960 live_phis = BITMAP_ALLOC (NULL);
961 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
963 VEC_safe_push (int, heap, worklist, i);
966 while (!VEC_empty (int, worklist))
968 b = VEC_pop (int, worklist);
969 if (b == ENTRY_BLOCK)
972 /* If there is a phi node in USE_BB, it is made live. Otherwise,
973 find the def that dominates the immediate dominator of USE_BB
974 (the kill in USE_BB does not dominate the use). */
975 if (bitmap_bit_p (phis, b))
979 use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
980 p = find_dfsnum_interval (defs, n_defs,
981 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
982 if (!bitmap_bit_p (phis, p))
986 /* If the phi node is already live, there is nothing to do. */
987 if (bitmap_bit_p (live_phis, p))
990 /* Mark the phi as live, and add the new uses to the worklist. */
991 bitmap_set_bit (live_phis, p);
992 def_bb = BASIC_BLOCK (p);
993 FOR_EACH_EDGE (e, ei, def_bb->preds)
996 if (bitmap_bit_p (uses, u))
999 /* In case there is a kill directly in the use block, do not record
1000 the use (this is also necessary for correctness, as we assume that
1001 uses dominated by a def directly in their block have been filtered
1003 if (bitmap_bit_p (kills, u))
1006 bitmap_set_bit (uses, u);
1007 VEC_safe_push (int, heap, worklist, u);
1011 VEC_free (int, heap, worklist);
1012 bitmap_copy (phis, live_phis);
1013 BITMAP_FREE (live_phis);
1017 /* Return the set of blocks where variable VAR is defined and the blocks
1018 where VAR is live on entry (livein). Return NULL, if no entry is
1019 found in DEF_BLOCKS. */
1021 static inline struct def_blocks_d *
1022 find_def_blocks_for (tree var)
1024 struct def_blocks_d dm;
1026 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1030 /* Retrieve or create a default definition for symbol SYM. */
1033 get_default_def_for (tree sym)
1035 tree ddef = gimple_default_def (cfun, sym);
1037 if (ddef == NULL_TREE)
1039 ddef = make_ssa_name (sym, gimple_build_nop ());
1040 set_default_def (sym, ddef);
1047 /* Marks phi node PHI in basic block BB for rewrite. */
1050 mark_phi_for_rewrite (basic_block bb, gimple phi)
1053 unsigned i, idx = bb->index;
1055 if (rewrite_uses_p (phi))
1058 set_rewrite_uses (phi, true);
1060 if (!blocks_with_phis_to_rewrite)
1063 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
1064 VEC_reserve (gimple_vec, heap, phis_to_rewrite, last_basic_block + 1);
1065 for (i = VEC_length (gimple_vec, phis_to_rewrite); i <= idx; i++)
1066 VEC_quick_push (gimple_vec, phis_to_rewrite, NULL);
1068 phis = VEC_index (gimple_vec, phis_to_rewrite, idx);
1070 phis = VEC_alloc (gimple, heap, 10);
1072 VEC_safe_push (gimple, heap, phis, phi);
1073 VEC_replace (gimple_vec, phis_to_rewrite, idx, phis);
1077 /* Insert PHI nodes for variable VAR using the iterated dominance
1078 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
1079 function assumes that the caller is incrementally updating the
1080 existing SSA form, in which case VAR may be an SSA name instead of
1083 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
1084 PHI node for VAR. On exit, only the nodes that received a PHI node
1085 for VAR will be present in PHI_INSERTION_POINTS. */
1088 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
1095 struct def_blocks_d *def_map;
1097 def_map = find_def_blocks_for (var);
1098 gcc_assert (def_map);
1100 /* Remove the blocks where we already have PHI nodes for VAR. */
1101 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1103 /* Remove obviously useless phi nodes. */
1104 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1105 def_map->livein_blocks);
1107 /* And insert the PHI nodes. */
1108 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1110 bb = BASIC_BLOCK (bb_index);
1112 mark_block_for_update (bb);
1116 if (TREE_CODE (var) == SSA_NAME)
1118 /* If we are rewriting SSA names, create the LHS of the PHI
1119 node by duplicating VAR. This is useful in the case of
1120 pointers, to also duplicate pointer attributes (alias
1121 information, in particular). */
1125 gcc_assert (update_p);
1126 phi = create_phi_node (var, bb);
1128 new_lhs = duplicate_ssa_name (var, phi);
1129 gimple_phi_set_result (phi, new_lhs);
1130 add_new_name_mapping (new_lhs, var);
1132 /* Add VAR to every argument slot of PHI. We need VAR in
1133 every argument so that rewrite_update_phi_arguments knows
1134 which name is this PHI node replacing. If VAR is a
1135 symbol marked for renaming, this is not necessary, the
1136 renamer will use the symbol on the LHS to get its
1137 reaching definition. */
1138 FOR_EACH_EDGE (e, ei, bb->preds)
1139 add_phi_arg (phi, var, e);
1143 gcc_assert (DECL_P (var));
1144 phi = create_phi_node (var, bb);
1147 /* Mark this PHI node as interesting for update_ssa. */
1148 set_register_defs (phi, true);
1149 mark_phi_for_rewrite (bb, phi);
1154 /* Insert PHI nodes at the dominance frontier of blocks with variable
1155 definitions. DFS contains the dominance frontier information for
1159 insert_phi_nodes (bitmap *dfs)
1161 referenced_var_iterator rvi;
1164 timevar_push (TV_TREE_INSERT_PHI_NODES);
1166 FOR_EACH_REFERENCED_VAR (var, rvi)
1168 struct def_blocks_d *def_map;
1171 def_map = find_def_blocks_for (var);
1172 if (def_map == NULL)
1175 if (get_phi_state (var) != NEED_PHI_STATE_NO)
1177 idf = compute_idf (def_map->def_blocks, dfs);
1178 insert_phi_nodes_for (var, idf, false);
1183 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1187 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1188 register DEF (an SSA_NAME) to be a new definition for SYM. */
1191 register_new_def (tree def, tree sym)
1195 /* If this variable is set in a single basic block and all uses are
1196 dominated by the set(s) in that single basic block, then there is
1197 no reason to record anything for this variable in the block local
1198 definition stacks. Doing so just wastes time and memory.
1200 This is the same test to prune the set of variables which may
1201 need PHI nodes. So we just use that information since it's already
1202 computed and available for us to use. */
1203 if (get_phi_state (sym) == NEED_PHI_STATE_NO)
1205 set_current_def (sym, def);
1209 currdef = get_current_def (sym);
1211 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1212 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1213 in the stack so that we know which symbol is being defined by
1214 this SSA name when we unwind the stack. */
1215 if (currdef && !is_gimple_reg (sym))
1216 VEC_safe_push (tree, heap, block_defs_stack, sym);
1218 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1219 stack is later used by the dominator tree callbacks to restore
1220 the reaching definitions for all the variables defined in the
1221 block after a recursive visit to all its immediately dominated
1222 blocks. If there is no current reaching definition, then just
1223 record the underlying _DECL node. */
1224 VEC_safe_push (tree, heap, block_defs_stack, currdef ? currdef : sym);
1226 /* Set the current reaching definition for SYM to be DEF. */
1227 set_current_def (sym, def);
1231 /* Perform a depth-first traversal of the dominator tree looking for
1232 variables to rename. BB is the block where to start searching.
1233 Renaming is a five step process:
1235 1- Every definition made by PHI nodes at the start of the blocks is
1236 registered as the current definition for the corresponding variable.
1238 2- Every statement in BB is rewritten. USE and VUSE operands are
1239 rewritten with their corresponding reaching definition. DEF and
1240 VDEF targets are registered as new definitions.
1242 3- All the PHI nodes in successor blocks of BB are visited. The
1243 argument corresponding to BB is replaced with its current reaching
1246 4- Recursively rewrite every dominator child block of BB.
1248 5- Restore (in reverse order) the current reaching definition for every
1249 new definition introduced in this block. This is done so that when
1250 we return from the recursive call, all the current reaching
1251 definitions are restored to the names that were valid in the
1252 dominator parent of BB. */
1254 /* SSA Rewriting Step 1. Initialization, create a block local stack
1255 of reaching definitions for new SSA names produced in this block
1256 (BLOCK_DEFS). Register new definitions for every PHI node in the
1260 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1264 gimple_stmt_iterator gsi;
1266 if (dump_file && (dump_flags & TDF_DETAILS))
1267 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1269 /* Mark the unwind point for this block. */
1270 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1272 /* Step 1. Register new definitions for every PHI node in the block.
1273 Conceptually, all the PHI nodes are executed in parallel and each PHI
1274 node introduces a new version for the associated variable. */
1275 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1279 phi = gsi_stmt (gsi);
1280 result = gimple_phi_result (phi);
1281 gcc_assert (is_gimple_reg (result));
1282 register_new_def (result, SSA_NAME_VAR (result));
1287 /* Return the current definition for variable VAR. If none is found,
1288 create a new SSA name to act as the zeroth definition for VAR. */
1291 get_reaching_def (tree var)
1295 /* Lookup the current reaching definition for VAR. */
1296 currdef = get_current_def (var);
1298 /* If there is no reaching definition for VAR, create and register a
1299 default definition for it (if needed). */
1300 if (currdef == NULL_TREE)
1302 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1303 currdef = get_default_def_for (sym);
1304 set_current_def (var, currdef);
1307 /* Return the current reaching definition for VAR, or the default
1308 definition, if we had to create one. */
1313 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1314 the block with its immediate reaching definitions. Update the current
1315 definition of a variable when a new real or virtual definition is found. */
1318 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1319 basic_block bb ATTRIBUTE_UNUSED, gimple_stmt_iterator si)
1322 use_operand_p use_p;
1323 def_operand_p def_p;
1326 stmt = gsi_stmt (si);
1328 /* If mark_def_sites decided that we don't need to rewrite this
1329 statement, ignore it. */
1330 gcc_assert (blocks_to_update == NULL);
1331 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1334 if (dump_file && (dump_flags & TDF_DETAILS))
1336 fprintf (dump_file, "Renaming statement ");
1337 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1338 fprintf (dump_file, "\n");
1341 /* Step 1. Rewrite USES in the statement. */
1342 if (rewrite_uses_p (stmt))
1343 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1345 tree var = USE_FROM_PTR (use_p);
1346 gcc_assert (DECL_P (var));
1347 SET_USE (use_p, get_reaching_def (var));
1350 /* Step 2. Register the statement's DEF operands. */
1351 if (register_defs_p (stmt))
1352 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1354 tree var = DEF_FROM_PTR (def_p);
1355 gcc_assert (DECL_P (var));
1356 SET_DEF (def_p, make_ssa_name (var, stmt));
1357 register_new_def (DEF_FROM_PTR (def_p), var);
1362 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1363 PHI nodes. For every PHI node found, add a new argument containing the
1364 current reaching definition for the variable and the edge through which
1365 that definition is reaching the PHI node. */
1368 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1374 FOR_EACH_EDGE (e, ei, bb->succs)
1377 gimple_stmt_iterator gsi;
1379 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1383 phi = gsi_stmt (gsi);
1384 currdef = get_reaching_def (SSA_NAME_VAR (gimple_phi_result (phi)));
1385 add_phi_arg (phi, currdef, e);
1391 /* Called after visiting all the statements in basic block BB and all
1392 of its dominator children. Restore CURRDEFS to its original value. */
1395 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1396 basic_block bb ATTRIBUTE_UNUSED)
1398 /* Restore CURRDEFS to its original state. */
1399 while (VEC_length (tree, block_defs_stack) > 0)
1401 tree tmp = VEC_pop (tree, block_defs_stack);
1402 tree saved_def, var;
1404 if (tmp == NULL_TREE)
1407 if (TREE_CODE (tmp) == SSA_NAME)
1409 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1410 current definition of its underlying variable. Note that
1411 if the SSA_NAME is not for a GIMPLE register, the symbol
1412 being defined is stored in the next slot in the stack.
1413 This mechanism is needed because an SSA name for a
1414 non-register symbol may be the definition for more than
1415 one symbol (e.g., SFTs, aliased variables, etc). */
1417 var = SSA_NAME_VAR (saved_def);
1418 if (!is_gimple_reg (var))
1419 var = VEC_pop (tree, block_defs_stack);
1423 /* If we recorded anything else, it must have been a _DECL
1424 node and its current reaching definition must have been
1430 set_current_def (var, saved_def);
1435 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1438 dump_decl_set (FILE *file, bitmap set)
1445 fprintf (file, "{ ");
1447 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1449 print_generic_expr (file, referenced_var (i), 0);
1450 fprintf (file, " ");
1453 fprintf (file, "}");
1456 fprintf (file, "NIL");
1460 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1463 debug_decl_set (bitmap set)
1465 dump_decl_set (stderr, set);
1466 fprintf (stderr, "\n");
1470 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1471 stack up to a maximum of N levels. If N is -1, the whole stack is
1472 dumped. New levels are created when the dominator tree traversal
1473 used for renaming enters a new sub-tree. */
1476 dump_defs_stack (FILE *file, int n)
1480 fprintf (file, "\n\nRenaming stack");
1482 fprintf (file, " (up to %d levels)", n);
1483 fprintf (file, "\n\n");
1486 fprintf (file, "Level %d (current level)\n", i);
1487 for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
1491 name = VEC_index (tree, block_defs_stack, j);
1492 if (name == NULL_TREE)
1497 fprintf (file, "\nLevel %d\n", i);
1508 var = SSA_NAME_VAR (name);
1509 if (!is_gimple_reg (var))
1512 var = VEC_index (tree, block_defs_stack, j);
1516 fprintf (file, " Previous CURRDEF (");
1517 print_generic_expr (file, var, 0);
1518 fprintf (file, ") = ");
1520 print_generic_expr (file, name, 0);
1522 fprintf (file, "<NIL>");
1523 fprintf (file, "\n");
1528 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1529 stack up to a maximum of N levels. If N is -1, the whole stack is
1530 dumped. New levels are created when the dominator tree traversal
1531 used for renaming enters a new sub-tree. */
1534 debug_defs_stack (int n)
1536 dump_defs_stack (stderr, n);
1540 /* Dump the current reaching definition of every symbol to FILE. */
1543 dump_currdefs (FILE *file)
1545 referenced_var_iterator i;
1548 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1549 FOR_EACH_REFERENCED_VAR (var, i)
1550 if (SYMS_TO_RENAME (cfun) == NULL
1551 || bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (var)))
1553 fprintf (file, "CURRDEF (");
1554 print_generic_expr (file, var, 0);
1555 fprintf (file, ") = ");
1556 if (get_current_def (var))
1557 print_generic_expr (file, get_current_def (var), 0);
1559 fprintf (file, "<NIL>");
1560 fprintf (file, "\n");
1565 /* Dump the current reaching definition of every symbol to stderr. */
1568 debug_currdefs (void)
1570 dump_currdefs (stderr);
1574 /* Dump SSA information to FILE. */
1577 dump_tree_ssa (FILE *file)
1579 const char *funcname
1580 = lang_hooks.decl_printable_name (current_function_decl, 2);
1582 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1584 dump_def_blocks (file);
1585 dump_defs_stack (file, -1);
1586 dump_currdefs (file);
1587 dump_tree_ssa_stats (file);
1591 /* Dump SSA information to stderr. */
1594 debug_tree_ssa (void)
1596 dump_tree_ssa (stderr);
1600 /* Dump statistics for the hash table HTAB. */
1603 htab_statistics (FILE *file, htab_t htab)
1605 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1606 (long) htab_size (htab),
1607 (long) htab_elements (htab),
1608 htab_collisions (htab));
1612 /* Dump SSA statistics on FILE. */
1615 dump_tree_ssa_stats (FILE *file)
1617 if (def_blocks || repl_tbl)
1618 fprintf (file, "\nHash table statistics:\n");
1622 fprintf (file, " def_blocks: ");
1623 htab_statistics (file, def_blocks);
1628 fprintf (file, " repl_tbl: ");
1629 htab_statistics (file, repl_tbl);
1632 if (def_blocks || repl_tbl)
1633 fprintf (file, "\n");
1637 /* Dump SSA statistics on stderr. */
1640 debug_tree_ssa_stats (void)
1642 dump_tree_ssa_stats (stderr);
1646 /* Hashing and equality functions for DEF_BLOCKS. */
1649 def_blocks_hash (const void *p)
1651 return htab_hash_pointer
1652 ((const void *)((const struct def_blocks_d *)p)->var);
1656 def_blocks_eq (const void *p1, const void *p2)
1658 return ((const struct def_blocks_d *)p1)->var
1659 == ((const struct def_blocks_d *)p2)->var;
1663 /* Free memory allocated by one entry in DEF_BLOCKS. */
1666 def_blocks_free (void *p)
1668 struct def_blocks_d *entry = (struct def_blocks_d *) p;
1669 BITMAP_FREE (entry->def_blocks);
1670 BITMAP_FREE (entry->phi_blocks);
1671 BITMAP_FREE (entry->livein_blocks);
1676 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1679 debug_def_blocks_r (void **slot, void *data)
1681 FILE *file = (FILE *) data;
1682 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1684 fprintf (file, "VAR: ");
1685 print_generic_expr (file, db_p->var, dump_flags);
1686 bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1687 bitmap_print (file, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}");
1688 bitmap_print (file, db_p->phi_blocks, ", PHI_BLOCKS: { ", "}\n");
1694 /* Dump the DEF_BLOCKS hash table on FILE. */
1697 dump_def_blocks (FILE *file)
1699 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1701 htab_traverse (def_blocks, debug_def_blocks_r, file);
1705 /* Dump the DEF_BLOCKS hash table on stderr. */
1708 debug_def_blocks (void)
1710 dump_def_blocks (stderr);
1714 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1717 register_new_update_single (tree new_name, tree old_name)
1719 tree currdef = get_current_def (old_name);
1721 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1722 This stack is later used by the dominator tree callbacks to
1723 restore the reaching definitions for all the variables
1724 defined in the block after a recursive visit to all its
1725 immediately dominated blocks. */
1726 VEC_reserve (tree, heap, block_defs_stack, 2);
1727 VEC_quick_push (tree, block_defs_stack, currdef);
1728 VEC_quick_push (tree, block_defs_stack, old_name);
1730 /* Set the current reaching definition for OLD_NAME to be
1732 set_current_def (old_name, new_name);
1736 /* Register NEW_NAME to be the new reaching definition for all the
1737 names in OLD_NAMES. Used by the incremental SSA update routines to
1738 replace old SSA names with new ones. */
1741 register_new_update_set (tree new_name, bitmap old_names)
1746 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1747 register_new_update_single (new_name, ssa_name (i));
1751 /* Initialization of block data structures for the incremental SSA
1752 update pass. Create a block local stack of reaching definitions
1753 for new SSA names produced in this block (BLOCK_DEFS). Register
1754 new definitions for every PHI node in the block. */
1757 rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1762 bool is_abnormal_phi;
1763 gimple_stmt_iterator gsi;
1765 if (dump_file && (dump_flags & TDF_DETAILS))
1766 fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
1769 /* Mark the unwind point for this block. */
1770 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1772 if (!bitmap_bit_p (blocks_to_update, bb->index))
1775 /* Mark the LHS if any of the arguments flows through an abnormal
1777 is_abnormal_phi = false;
1778 FOR_EACH_EDGE (e, ei, bb->preds)
1779 if (e->flags & EDGE_ABNORMAL)
1781 is_abnormal_phi = true;
1785 /* If any of the PHI nodes is a replacement for a name in
1786 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
1787 register it as a new definition for its corresponding name. Also
1788 register definitions for names whose underlying symbols are
1789 marked for renaming. */
1790 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1793 gimple phi = gsi_stmt (gsi);
1795 if (!register_defs_p (phi))
1798 lhs = gimple_phi_result (phi);
1799 lhs_sym = SSA_NAME_VAR (lhs);
1801 if (symbol_marked_for_renaming (lhs_sym))
1802 register_new_update_single (lhs, lhs_sym);
1806 /* If LHS is a new name, register a new definition for all
1807 the names replaced by LHS. */
1808 if (is_new_name (lhs))
1809 register_new_update_set (lhs, names_replaced_by (lhs));
1811 /* If LHS is an OLD name, register it as a new definition
1813 if (is_old_name (lhs))
1814 register_new_update_single (lhs, lhs);
1817 if (is_abnormal_phi)
1818 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
1823 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
1824 the current reaching definition of every name re-written in BB to
1825 the original reaching definition before visiting BB. This
1826 unwinding must be done in the opposite order to what is done in
1827 register_new_update_set. */
1830 rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1831 basic_block bb ATTRIBUTE_UNUSED)
1833 while (VEC_length (tree, block_defs_stack) > 0)
1835 tree var = VEC_pop (tree, block_defs_stack);
1838 /* NULL indicates the unwind stop point for this block (see
1839 rewrite_update_init_block). */
1843 saved_def = VEC_pop (tree, block_defs_stack);
1844 set_current_def (var, saved_def);
1849 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1850 it is a symbol marked for renaming, replace it with USE_P's current
1851 reaching definition. */
1854 maybe_replace_use (use_operand_p use_p)
1856 tree rdef = NULL_TREE;
1857 tree use = USE_FROM_PTR (use_p);
1858 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1860 if (symbol_marked_for_renaming (sym))
1861 rdef = get_reaching_def (sym);
1862 else if (is_old_name (use))
1863 rdef = get_reaching_def (use);
1865 if (rdef && rdef != use)
1866 SET_USE (use_p, rdef);
1870 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1871 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1872 register it as the current definition for the names replaced by
1876 maybe_register_def (def_operand_p def_p, gimple stmt)
1878 tree def = DEF_FROM_PTR (def_p);
1879 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1881 /* If DEF is a naked symbol that needs renaming, create a new
1883 if (symbol_marked_for_renaming (sym))
1887 def = make_ssa_name (def, stmt);
1888 SET_DEF (def_p, def);
1891 register_new_update_single (def, sym);
1895 /* If DEF is a new name, register it as a new definition
1896 for all the names replaced by DEF. */
1897 if (is_new_name (def))
1898 register_new_update_set (def, names_replaced_by (def));
1900 /* If DEF is an old name, register DEF as a new
1901 definition for itself. */
1902 if (is_old_name (def))
1903 register_new_update_single (def, def);
1908 /* Update every variable used in the statement pointed-to by SI. The
1909 statement is assumed to be in SSA form already. Names in
1910 OLD_SSA_NAMES used by SI will be updated to their current reaching
1911 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1912 will be registered as a new definition for their corresponding name
1913 in OLD_SSA_NAMES. */
1916 rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1917 basic_block bb ATTRIBUTE_UNUSED,
1918 gimple_stmt_iterator si)
1921 use_operand_p use_p;
1922 def_operand_p def_p;
1925 stmt = gsi_stmt (si);
1927 gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
1929 /* Only update marked statements. */
1930 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1933 if (dump_file && (dump_flags & TDF_DETAILS))
1935 fprintf (dump_file, "Updating SSA information for statement ");
1936 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1937 fprintf (dump_file, "\n");
1940 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1941 symbol is marked for renaming. */
1942 if (rewrite_uses_p (stmt))
1943 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1944 maybe_replace_use (use_p);
1946 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1947 Also register definitions for names whose underlying symbol is
1948 marked for renaming. */
1949 if (register_defs_p (stmt))
1950 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1951 maybe_register_def (def_p, stmt);
1955 /* Visit all the successor blocks of BB looking for PHI nodes. For
1956 every PHI node found, check if any of its arguments is in
1957 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1958 definition, replace it. */
1961 rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1968 FOR_EACH_EDGE (e, ei, bb->succs)
1973 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1976 phis = VEC_index (gimple_vec, phis_to_rewrite, e->dest->index);
1977 for (i = 0; VEC_iterate (gimple, phis, i, phi); i++)
1980 use_operand_p arg_p;
1982 gcc_assert (rewrite_uses_p (phi));
1984 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1985 arg = USE_FROM_PTR (arg_p);
1987 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
1990 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
1992 if (arg == NULL_TREE)
1994 /* When updating a PHI node for a recently introduced
1995 symbol we may find NULL arguments. That's why we
1996 take the symbol from the LHS of the PHI node. */
1997 SET_USE (arg_p, get_reaching_def (lhs_sym));
2001 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2003 if (symbol_marked_for_renaming (sym))
2004 SET_USE (arg_p, get_reaching_def (sym));
2005 else if (is_old_name (arg))
2006 SET_USE (arg_p, get_reaching_def (arg));
2009 if (e->flags & EDGE_ABNORMAL)
2010 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2016 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2019 ENTRY indicates the block where to start. Every block dominated by
2020 ENTRY will be rewritten.
2022 WHAT indicates what actions will be taken by the renamer (see enum
2025 BLOCKS are the set of interesting blocks for the dominator walker
2026 to process. If this set is NULL, then all the nodes dominated
2027 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2028 are not present in BLOCKS are ignored. */
2031 rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
2033 struct dom_walk_data walk_data;
2035 /* Rewrite all the basic blocks in the program. */
2036 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2038 /* Setup callbacks for the generic dominator tree walker. */
2039 memset (&walk_data, 0, sizeof (walk_data));
2041 walk_data.dom_direction = CDI_DOMINATORS;
2042 walk_data.interesting_blocks = blocks;
2044 if (what == REWRITE_ALL)
2045 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
2047 walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
2049 if (what == REWRITE_ALL)
2050 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
2051 else if (what == REWRITE_UPDATE)
2052 walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
2056 if (what == REWRITE_ALL)
2057 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
2058 else if (what == REWRITE_UPDATE)
2059 walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
2063 if (what == REWRITE_ALL)
2064 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
2065 else if (what == REWRITE_UPDATE)
2066 walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
2070 block_defs_stack = VEC_alloc (tree, heap, 10);
2072 /* Initialize the dominator walker. */
2073 init_walk_dominator_tree (&walk_data);
2075 /* Recursively walk the dominator tree rewriting each statement in
2076 each basic block. */
2077 walk_dominator_tree (&walk_data, entry);
2079 /* Finalize the dominator walker. */
2080 fini_walk_dominator_tree (&walk_data);
2082 /* Debugging dumps. */
2083 if (dump_file && (dump_flags & TDF_STATS))
2085 dump_dfa_stats (dump_file);
2087 dump_tree_ssa_stats (dump_file);
2090 VEC_free (tree, heap, block_defs_stack);
2092 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2096 /* Block initialization routine for mark_def_sites. Clear the
2097 KILLS bitmap at the start of each block. */
2100 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
2101 basic_block bb ATTRIBUTE_UNUSED)
2103 struct mark_def_sites_global_data *gd;
2104 gd = (struct mark_def_sites_global_data *) walk_data->global_data;
2105 bitmap_clear (gd->kills);
2109 /* Mark the definition site blocks for each variable, so that we know
2110 where the variable is actually live.
2112 INTERESTING_BLOCKS will be filled in with all the blocks that
2113 should be processed by the renamer. It is assumed to be
2114 initialized and zeroed by the caller. */
2117 mark_def_site_blocks (sbitmap interesting_blocks)
2119 struct dom_walk_data walk_data;
2120 struct mark_def_sites_global_data mark_def_sites_global_data;
2122 /* Setup callbacks for the generic dominator tree walker to find and
2123 mark definition sites. */
2124 walk_data.walk_stmts_backward = false;
2125 walk_data.dom_direction = CDI_DOMINATORS;
2126 walk_data.initialize_block_local_data = NULL;
2127 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
2128 walk_data.before_dom_children_walk_stmts = mark_def_sites;
2129 walk_data.before_dom_children_after_stmts = NULL;
2130 walk_data.after_dom_children_before_stmts = NULL;
2131 walk_data.after_dom_children_walk_stmts = NULL;
2132 walk_data.after_dom_children_after_stmts = NULL;
2133 walk_data.interesting_blocks = NULL;
2135 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2136 large enough to accommodate all the variables referenced in the
2137 function, not just the ones we are renaming. */
2138 mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
2140 /* Create the set of interesting blocks that will be filled by
2142 mark_def_sites_global_data.interesting_blocks = interesting_blocks;
2143 walk_data.global_data = &mark_def_sites_global_data;
2145 /* We do not have any local data. */
2146 walk_data.block_local_data_size = 0;
2148 /* Initialize the dominator walker. */
2149 init_walk_dominator_tree (&walk_data);
2151 /* Recursively walk the dominator tree. */
2152 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
2154 /* Finalize the dominator walker. */
2155 fini_walk_dominator_tree (&walk_data);
2157 /* We no longer need this bitmap, clear and free it. */
2158 BITMAP_FREE (mark_def_sites_global_data.kills);
2162 /* Initialize internal data needed during renaming. */
2165 init_ssa_renamer (void)
2168 referenced_var_iterator rvi;
2170 cfun->gimple_df->in_ssa_p = false;
2172 /* Allocate memory for the DEF_BLOCKS hash table. */
2173 gcc_assert (def_blocks == NULL);
2174 def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
2175 def_blocks_eq, def_blocks_free);
2177 FOR_EACH_REFERENCED_VAR(var, rvi)
2178 set_current_def (var, NULL_TREE);
2182 /* Deallocate internal data structures used by the renamer. */
2185 fini_ssa_renamer (void)
2189 htab_delete (def_blocks);
2193 cfun->gimple_df->in_ssa_p = true;
2196 /* Main entry point into the SSA builder. The renaming process
2197 proceeds in four main phases:
2199 1- Compute dominance frontier and immediate dominators, needed to
2200 insert PHI nodes and rename the function in dominator tree
2203 2- Find and mark all the blocks that define variables
2204 (mark_def_site_blocks).
2206 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2208 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2210 Steps 3 and 4 are done using the dominator tree walker
2211 (walk_dominator_tree). */
2214 rewrite_into_ssa (void)
2218 sbitmap interesting_blocks;
2220 timevar_push (TV_TREE_SSA_OTHER);
2222 /* Initialize operand data structures. */
2223 init_ssa_operands ();
2225 /* Initialize internal data needed by the renamer. */
2226 init_ssa_renamer ();
2228 /* Initialize the set of interesting blocks. The callback
2229 mark_def_sites will add to this set those blocks that the renamer
2231 interesting_blocks = sbitmap_alloc (last_basic_block);
2232 sbitmap_zero (interesting_blocks);
2234 /* Initialize dominance frontier. */
2235 dfs = XNEWVEC (bitmap, last_basic_block);
2237 dfs[bb->index] = BITMAP_ALLOC (NULL);
2239 /* 1- Compute dominance frontiers. */
2240 calculate_dominance_info (CDI_DOMINATORS);
2241 compute_dominance_frontiers (dfs);
2243 /* 2- Find and mark definition sites. */
2244 mark_def_site_blocks (interesting_blocks);
2246 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2247 insert_phi_nodes (dfs);
2249 /* 4- Rename all the blocks. */
2250 rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
2252 /* Free allocated memory. */
2254 BITMAP_FREE (dfs[bb->index]);
2256 sbitmap_free (interesting_blocks);
2258 fini_ssa_renamer ();
2260 timevar_pop (TV_TREE_SSA_OTHER);
2265 struct gimple_opt_pass pass_build_ssa =
2271 rewrite_into_ssa, /* execute */
2274 0, /* static_pass_number */
2275 TV_NONE, /* tv_id */
2276 PROP_cfg | PROP_referenced_vars, /* properties_required */
2277 PROP_ssa, /* properties_provided */
2278 0, /* properties_destroyed */
2279 0, /* todo_flags_start */
2281 | TODO_update_ssa_only_virtuals
2283 | TODO_remove_unused_locals /* todo_flags_finish */
2288 /* Mark the definition of VAR at STMT and BB as interesting for the
2289 renamer. BLOCKS is the set of blocks that need updating. */
2292 mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2294 gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
2295 set_register_defs (stmt, true);
2299 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2301 set_def_block (var, bb, is_phi_p);
2303 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2304 site for both itself and all the old names replaced by it. */
2305 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2309 bitmap set = names_replaced_by (var);
2311 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2312 set_def_block (ssa_name (i), bb, is_phi_p);
2318 /* Mark the use of VAR at STMT and BB as interesting for the
2319 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2323 mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2325 basic_block def_bb = gimple_bb (stmt);
2327 mark_block_for_update (def_bb);
2328 mark_block_for_update (bb);
2330 if (gimple_code (stmt) == GIMPLE_PHI)
2331 mark_phi_for_rewrite (def_bb, stmt);
2333 set_rewrite_uses (stmt, true);
2335 /* If VAR has not been defined in BB, then it is live-on-entry
2336 to BB. Note that we cannot just use the block holding VAR's
2337 definition because if VAR is one of the names in OLD_SSA_NAMES,
2338 it will have several definitions (itself and all the names that
2342 struct def_blocks_d *db_p = get_def_blocks_for (var);
2343 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2344 set_livein_block (var, bb);
2349 /* Do a dominator walk starting at BB processing statements that
2350 reference symbols in SYMS_TO_RENAME. This is very similar to
2351 mark_def_sites, but the scan handles statements whose operands may
2352 already be SSA names.
2354 If INSERT_PHI_P is true, mark those uses as live in the
2355 corresponding block. This is later used by the PHI placement
2356 algorithm to make PHI pruning decisions.
2358 FIXME. Most of this would be unnecessary if we could associate a
2359 symbol to all the SSA names that reference it. But that
2360 sounds like it would be expensive to maintain. Still, it
2361 would be interesting to see if it makes better sense to do
2365 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2368 gimple_stmt_iterator si;
2372 mark_block_for_update (bb);
2374 /* Process PHI nodes marking interesting those that define or use
2375 the symbols that we are interested in. */
2376 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
2378 gimple phi = gsi_stmt (si);
2379 tree lhs_sym, lhs = gimple_phi_result (phi);
2381 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2383 if (!symbol_marked_for_renaming (lhs_sym))
2386 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2388 /* Mark the uses in phi nodes as interesting. It would be more correct
2389 to process the arguments of the phi nodes of the successor edges of
2390 BB at the end of prepare_block_for_update, however, that turns out
2391 to be significantly more expensive. Doing it here is conservatively
2392 correct -- it may only cause us to believe a value to be live in a
2393 block that also contains its definition, and thus insert a few more
2394 phi nodes for it. */
2395 FOR_EACH_EDGE (e, ei, bb->preds)
2396 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2399 /* Process the statements. */
2400 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2404 use_operand_p use_p;
2405 def_operand_p def_p;
2407 stmt = gsi_stmt (si);
2409 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
2411 tree use = USE_FROM_PTR (use_p);
2412 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2413 if (symbol_marked_for_renaming (sym))
2414 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2417 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_ALL_DEFS)
2419 tree def = DEF_FROM_PTR (def_p);
2420 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2421 if (symbol_marked_for_renaming (sym))
2422 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2426 /* Now visit all the blocks dominated by BB. */
2427 for (son = first_dom_son (CDI_DOMINATORS, bb);
2429 son = next_dom_son (CDI_DOMINATORS, son))
2430 prepare_block_for_update (son, insert_phi_p);
2434 /* Helper for prepare_names_to_update. Mark all the use sites for
2435 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2436 prepare_names_to_update. */
2439 prepare_use_sites_for (tree name, bool insert_phi_p)
2441 use_operand_p use_p;
2442 imm_use_iterator iter;
2444 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2446 gimple stmt = USE_STMT (use_p);
2447 basic_block bb = gimple_bb (stmt);
2449 if (gimple_code (stmt) == GIMPLE_PHI)
2451 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2452 edge e = gimple_phi_arg_edge (stmt, ix);
2453 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2457 /* For regular statements, mark this as an interesting use
2459 mark_use_interesting (name, stmt, bb, insert_phi_p);
2465 /* Helper for prepare_names_to_update. Mark the definition site for
2466 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2467 prepare_names_to_update. */
2470 prepare_def_site_for (tree name, bool insert_phi_p)
2475 gcc_assert (names_to_release == NULL
2476 || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2478 stmt = SSA_NAME_DEF_STMT (name);
2479 bb = gimple_bb (stmt);
2482 gcc_assert (bb->index < last_basic_block);
2483 mark_block_for_update (bb);
2484 mark_def_interesting (name, stmt, bb, insert_phi_p);
2489 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2490 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2491 PHI nodes for newly created names. */
2494 prepare_names_to_update (bool insert_phi_p)
2498 sbitmap_iterator sbi;
2500 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2501 remove it from NEW_SSA_NAMES so that we don't try to visit its
2502 defining basic block (which most likely doesn't exist). Notice
2503 that we cannot do the same with names in OLD_SSA_NAMES because we
2504 want to replace existing instances. */
2505 if (names_to_release)
2506 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2507 RESET_BIT (new_ssa_names, i);
2509 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2510 names may be considered to be live-in on blocks that contain
2511 definitions for their replacements. */
2512 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2513 prepare_def_site_for (ssa_name (i), insert_phi_p);
2515 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2516 OLD_SSA_NAMES, but we have to ignore its definition site. */
2517 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2519 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2520 prepare_def_site_for (ssa_name (i), insert_phi_p);
2521 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2526 /* Dump all the names replaced by NAME to FILE. */
2529 dump_names_replaced_by (FILE *file, tree name)
2535 print_generic_expr (file, name, 0);
2536 fprintf (file, " -> { ");
2538 old_set = names_replaced_by (name);
2539 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2541 print_generic_expr (file, ssa_name (i), 0);
2542 fprintf (file, " ");
2545 fprintf (file, "}\n");
2549 /* Dump all the names replaced by NAME to stderr. */
2552 debug_names_replaced_by (tree name)
2554 dump_names_replaced_by (stderr, name);
2558 /* Dump SSA update information to FILE. */
2561 dump_update_ssa (FILE *file)
2566 if (!need_ssa_update_p (cfun))
2569 if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2571 sbitmap_iterator sbi;
2573 fprintf (file, "\nSSA replacement table\n");
2574 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2575 "O_1, ..., O_j\n\n");
2577 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2578 dump_names_replaced_by (file, ssa_name (i));
2580 fprintf (file, "\n");
2581 fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
2582 update_ssa_stats.num_virtual_mappings);
2583 fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
2584 update_ssa_stats.num_total_mappings
2585 - update_ssa_stats.num_virtual_mappings);
2586 fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
2587 update_ssa_stats.num_total_mappings);
2589 fprintf (file, "\nNumber of virtual symbols: %u\n",
2590 update_ssa_stats.num_virtual_symbols);
2593 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
2595 fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2596 dump_decl_set (file, SYMS_TO_RENAME (cfun));
2597 fprintf (file, "\n");
2600 if (names_to_release && !bitmap_empty_p (names_to_release))
2602 fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2603 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2605 print_generic_expr (file, ssa_name (i), 0);
2606 fprintf (file, " ");
2610 fprintf (file, "\n\n");
2614 /* Dump SSA update information to stderr. */
2617 debug_update_ssa (void)
2619 dump_update_ssa (stderr);
2623 /* Initialize data structures used for incremental SSA updates. */
2626 init_update_ssa (struct function *fn)
2628 /* Reserve more space than the current number of names. The calls to
2629 add_new_name_mapping are typically done after creating new SSA
2630 names, so we'll need to reallocate these arrays. */
2631 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2632 sbitmap_zero (old_ssa_names);
2634 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2635 sbitmap_zero (new_ssa_names);
2637 repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2638 regs_to_rename = BITMAP_ALLOC (NULL);
2639 mem_syms_to_rename = BITMAP_ALLOC (NULL);
2640 names_to_release = NULL;
2641 memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
2642 update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
2643 update_ssa_initialized_fn = fn;
2647 /* Deallocate data structures used for incremental SSA updates. */
2650 delete_update_ssa (void)
2655 sbitmap_free (old_ssa_names);
2656 old_ssa_names = NULL;
2658 sbitmap_free (new_ssa_names);
2659 new_ssa_names = NULL;
2661 htab_delete (repl_tbl);
2664 bitmap_clear (SYMS_TO_RENAME (update_ssa_initialized_fn));
2665 BITMAP_FREE (regs_to_rename);
2666 BITMAP_FREE (mem_syms_to_rename);
2667 BITMAP_FREE (update_ssa_stats.virtual_symbols);
2669 if (names_to_release)
2671 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2672 release_ssa_name (ssa_name (i));
2673 BITMAP_FREE (names_to_release);
2676 clear_ssa_name_info ();
2678 fini_ssa_renamer ();
2680 if (blocks_with_phis_to_rewrite)
2681 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2683 gimple_vec phis = VEC_index (gimple_vec, phis_to_rewrite, i);
2685 VEC_free (gimple, heap, phis);
2686 VEC_replace (gimple_vec, phis_to_rewrite, i, NULL);
2689 BITMAP_FREE (blocks_with_phis_to_rewrite);
2690 BITMAP_FREE (blocks_to_update);
2691 update_ssa_initialized_fn = NULL;
2695 /* Create a new name for OLD_NAME in statement STMT and replace the
2696 operand pointed to by DEF_P with the newly created name. Return
2697 the new name and register the replacement mapping <NEW, OLD> in
2698 update_ssa's tables. */
2701 create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
2703 tree new_name = duplicate_ssa_name (old_name, stmt);
2705 SET_DEF (def, new_name);
2707 if (gimple_code (stmt) == GIMPLE_PHI)
2711 basic_block bb = gimple_bb (stmt);
2713 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2714 FOR_EACH_EDGE (e, ei, bb->preds)
2715 if (e->flags & EDGE_ABNORMAL)
2717 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
2722 register_new_name_mapping (new_name, old_name);
2724 /* For the benefit of passes that will be updating the SSA form on
2725 their own, set the current reaching definition of OLD_NAME to be
2727 set_current_def (old_name, new_name);
2733 /* Register name NEW to be a replacement for name OLD. This function
2734 must be called for every replacement that should be performed by
2738 register_new_name_mapping (tree new_tree, tree old)
2740 if (!update_ssa_initialized_fn)
2741 init_update_ssa (cfun);
2743 gcc_assert (update_ssa_initialized_fn == cfun);
2745 add_new_name_mapping (new_tree, old);
2749 /* Register symbol SYM to be renamed by update_ssa. */
2752 mark_sym_for_renaming (tree sym)
2754 bitmap_set_bit (SYMS_TO_RENAME (cfun), DECL_UID (sym));
2758 /* Register all the symbols in SET to be renamed by update_ssa. */
2761 mark_set_for_renaming (bitmap set)
2766 if (set == NULL || bitmap_empty_p (set))
2769 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2770 mark_sym_for_renaming (referenced_var (i));
2774 /* Return true if there is any work to be done by update_ssa
2778 need_ssa_update_p (struct function *fn)
2780 gcc_assert (fn != NULL);
2781 return (update_ssa_initialized_fn == fn
2783 && !bitmap_empty_p (SYMS_TO_RENAME (fn))));
2786 /* Return true if SSA name mappings have been registered for SSA updating. */
2789 name_mappings_registered_p (void)
2791 if (!update_ssa_initialized_fn)
2794 gcc_assert (update_ssa_initialized_fn == cfun);
2796 return repl_tbl && htab_elements (repl_tbl) > 0;
2799 /* Return true if name N has been registered in the replacement table. */
2802 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
2804 if (!update_ssa_initialized_fn)
2807 gcc_assert (update_ssa_initialized_fn == cfun);
2809 return is_new_name (n) || is_old_name (n);
2813 /* Return the set of all the SSA names marked to be replaced. */
2816 ssa_names_to_replace (void)
2820 sbitmap_iterator sbi;
2822 gcc_assert (update_ssa_initialized_fn == NULL
2823 || update_ssa_initialized_fn == cfun);
2825 ret = BITMAP_ALLOC (NULL);
2826 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2827 bitmap_set_bit (ret, i);
2833 /* Mark NAME to be released after update_ssa has finished. */
2836 release_ssa_name_after_update_ssa (tree name)
2838 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
2840 if (names_to_release == NULL)
2841 names_to_release = BITMAP_ALLOC (NULL);
2843 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2847 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2848 frontier information. BLOCKS is the set of blocks to be updated.
2850 This is slightly different than the regular PHI insertion
2851 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2852 real names (i.e., GIMPLE registers) are inserted:
2854 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2855 nodes inside the region affected by the block that defines VAR
2856 and the blocks that define all its replacements. All these
2857 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2859 First, we compute the entry point to the region (ENTRY). This is
2860 given by the nearest common dominator to all the definition
2861 blocks. When computing the iterated dominance frontier (IDF), any
2862 block not strictly dominated by ENTRY is ignored.
2864 We then call the standard PHI insertion algorithm with the pruned
2867 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2868 names is not pruned. PHI nodes are inserted at every IDF block. */
2871 insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
2872 unsigned update_flags)
2875 struct def_blocks_d *db;
2876 bitmap idf, pruned_idf;
2880 #if defined ENABLE_CHECKING
2881 if (TREE_CODE (var) == SSA_NAME)
2882 gcc_assert (is_old_name (var));
2884 gcc_assert (symbol_marked_for_renaming (var));
2887 /* Get all the definition sites for VAR. */
2888 db = find_def_blocks_for (var);
2890 /* No need to do anything if there were no definitions to VAR. */
2891 if (db == NULL || bitmap_empty_p (db->def_blocks))
2894 /* Compute the initial iterated dominance frontier. */
2895 idf = compute_idf (db->def_blocks, dfs);
2896 pruned_idf = BITMAP_ALLOC (NULL);
2898 if (TREE_CODE (var) == SSA_NAME)
2900 if (update_flags == TODO_update_ssa)
2902 /* If doing regular SSA updates for GIMPLE registers, we are
2903 only interested in IDF blocks dominated by the nearest
2904 common dominator of all the definition blocks. */
2905 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
2907 if (entry != ENTRY_BLOCK_PTR)
2908 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
2909 if (BASIC_BLOCK (i) != entry
2910 && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
2911 bitmap_set_bit (pruned_idf, i);
2915 /* Otherwise, do not prune the IDF for VAR. */
2916 gcc_assert (update_flags == TODO_update_ssa_full_phi);
2917 bitmap_copy (pruned_idf, idf);
2922 /* Otherwise, VAR is a symbol that needs to be put into SSA form
2923 for the first time, so we need to compute the full IDF for
2925 bitmap_copy (pruned_idf, idf);
2928 if (!bitmap_empty_p (pruned_idf))
2930 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
2931 are included in the region to be updated. The feeding blocks
2932 are important to guarantee that the PHI arguments are renamed
2935 /* FIXME, this is not needed if we are updating symbols. We are
2936 already starting at the ENTRY block anyway. */
2937 bitmap_ior_into (blocks, pruned_idf);
2938 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
2942 basic_block bb = BASIC_BLOCK (i);
2944 FOR_EACH_EDGE (e, ei, bb->preds)
2945 if (e->src->index >= 0)
2946 bitmap_set_bit (blocks, e->src->index);
2949 insert_phi_nodes_for (var, pruned_idf, true);
2952 BITMAP_FREE (pruned_idf);
2957 /* Heuristic to determine whether SSA name mappings for virtual names
2958 should be discarded and their symbols rewritten from scratch. When
2959 there is a large number of mappings for virtual names, the
2960 insertion of PHI nodes for the old names in the mappings takes
2961 considerable more time than if we inserted PHI nodes for the
2964 Currently the heuristic takes these stats into account:
2966 - Number of mappings for virtual SSA names.
2967 - Number of distinct virtual symbols involved in those mappings.
2969 If the number of virtual mappings is much larger than the number of
2970 virtual symbols, then it will be faster to compute PHI insertion
2971 spots for the symbols. Even if this involves traversing the whole
2972 CFG, which is what happens when symbols are renamed from scratch. */
2975 switch_virtuals_to_full_rewrite_p (void)
2977 if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
2980 if (update_ssa_stats.num_virtual_mappings
2981 > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
2982 * update_ssa_stats.num_virtual_symbols)
2989 /* Remove every virtual mapping and mark all the affected virtual
2990 symbols for renaming. */
2993 switch_virtuals_to_full_rewrite (void)
2996 sbitmap_iterator sbi;
3000 fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
3001 fprintf (dump_file, "\tNumber of virtual mappings: %7u\n",
3002 update_ssa_stats.num_virtual_mappings);
3003 fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
3004 update_ssa_stats.num_virtual_symbols);
3005 fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
3006 "faster than processing\nthe name mappings.\n\n");
3009 /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
3010 Note that it is not really necessary to remove the mappings from
3011 REPL_TBL, that would only waste time. */
3012 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
3013 if (!is_gimple_reg (ssa_name (i)))
3014 RESET_BIT (new_ssa_names, i);
3016 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3017 if (!is_gimple_reg (ssa_name (i)))
3018 RESET_BIT (old_ssa_names, i);
3020 mark_set_for_renaming (update_ssa_stats.virtual_symbols);
3024 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3025 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3027 1- The names in OLD_SSA_NAMES dominated by the definitions of
3028 NEW_SSA_NAMES are all re-written to be reached by the
3029 appropriate definition from NEW_SSA_NAMES.
3031 2- If needed, new PHI nodes are added to the iterated dominance
3032 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3034 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3035 calling register_new_name_mapping for every pair of names that the
3036 caller wants to replace.
3038 The caller identifies the new names that have been inserted and the
3039 names that need to be replaced by calling register_new_name_mapping
3040 for every pair <NEW, OLD>. Note that the function assumes that the
3041 new names have already been inserted in the IL.
3043 For instance, given the following code:
3046 2 x_1 = PHI (0, x_5)
3057 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3060 2 x_1 = PHI (0, x_5)
3073 We want to replace all the uses of x_1 with the new definitions of
3074 x_10 and x_11. Note that the only uses that should be replaced are
3075 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3076 *not* be replaced (this is why we cannot just mark symbol 'x' for
3079 Additionally, we may need to insert a PHI node at line 11 because
3080 that is a merge point for x_10 and x_11. So the use of x_1 at line
3081 11 will be replaced with the new PHI node. The insertion of PHI
3082 nodes is optional. They are not strictly necessary to preserve the
3083 SSA form, and depending on what the caller inserted, they may not
3084 even be useful for the optimizers. UPDATE_FLAGS controls various
3085 aspects of how update_ssa operates, see the documentation for
3086 TODO_update_ssa*. */
3089 update_ssa (unsigned update_flags)
3091 basic_block bb, start_bb;
3096 sbitmap_iterator sbi;
3098 if (!need_ssa_update_p (cfun))
3101 timevar_push (TV_TREE_SSA_INCREMENTAL);
3103 if (!update_ssa_initialized_fn)
3104 init_update_ssa (cfun);
3105 gcc_assert (update_ssa_initialized_fn == cfun);
3107 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3108 if (!phis_to_rewrite)
3109 phis_to_rewrite = VEC_alloc (gimple_vec, heap, last_basic_block);
3110 blocks_to_update = BITMAP_ALLOC (NULL);
3112 /* Ensure that the dominance information is up-to-date. */
3113 calculate_dominance_info (CDI_DOMINATORS);
3115 /* Only one update flag should be set. */
3116 gcc_assert (update_flags == TODO_update_ssa
3117 || update_flags == TODO_update_ssa_no_phi
3118 || update_flags == TODO_update_ssa_full_phi
3119 || update_flags == TODO_update_ssa_only_virtuals);
3121 /* If we only need to update virtuals, remove all the mappings for
3122 real names before proceeding. The caller is responsible for
3123 having dealt with the name mappings before calling update_ssa. */
3124 if (update_flags == TODO_update_ssa_only_virtuals)
3126 sbitmap_zero (old_ssa_names);
3127 sbitmap_zero (new_ssa_names);
3128 htab_empty (repl_tbl);
3131 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3135 /* If the caller requested PHI nodes to be added, initialize
3136 live-in information data structures (DEF_BLOCKS). */
3138 /* For each SSA name N, the DEF_BLOCKS table describes where the
3139 name is defined, which blocks have PHI nodes for N, and which
3140 blocks have uses of N (i.e., N is live-on-entry in those
3142 def_blocks = htab_create (num_ssa_names, def_blocks_hash,
3143 def_blocks_eq, def_blocks_free);
3150 /* Heuristic to avoid massive slow downs when the replacement
3151 mappings include lots of virtual names. */
3152 if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
3153 switch_virtuals_to_full_rewrite ();
3155 /* If there are symbols to rename, identify those symbols that are
3156 GIMPLE registers into the set REGS_TO_RENAME and those that are
3157 memory symbols into the set MEM_SYMS_TO_RENAME. */
3158 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3163 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3165 tree sym = referenced_var (i);
3166 if (is_gimple_reg (sym))
3167 bitmap_set_bit (regs_to_rename, i);
3170 /* Memory symbols are those not in REGS_TO_RENAME. */
3171 bitmap_and_compl (mem_syms_to_rename,
3172 SYMS_TO_RENAME (cfun), regs_to_rename);
3175 /* If there are names defined in the replacement table, prepare
3176 definition and use sites for all the names in NEW_SSA_NAMES and
3178 if (sbitmap_first_set_bit (new_ssa_names) >= 0)
3180 prepare_names_to_update (insert_phi_p);
3182 /* If all the names in NEW_SSA_NAMES had been marked for
3183 removal, and there are no symbols to rename, then there's
3184 nothing else to do. */
3185 if (sbitmap_first_set_bit (new_ssa_names) < 0
3186 && bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3190 /* Next, determine the block at which to start the renaming process. */
3191 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3193 /* If we have to rename some symbols from scratch, we need to
3194 start the process at the root of the CFG. FIXME, it should
3195 be possible to determine the nearest block that had a
3196 definition for each of the symbols that are marked for
3197 updating. For now this seems more work than it's worth. */
3198 start_bb = ENTRY_BLOCK_PTR;
3200 /* Traverse the CFG looking for existing definitions and uses of
3201 symbols in SYMS_TO_RENAME. Mark interesting blocks and
3202 statements and set local live-in information for the PHI
3203 placement heuristics. */
3204 prepare_block_for_update (start_bb, insert_phi_p);
3208 /* Otherwise, the entry block to the region is the nearest
3209 common dominator for the blocks in BLOCKS. */
3210 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3214 /* If requested, insert PHI nodes at the iterated dominance frontier
3215 of every block, creating new definitions for names in OLD_SSA_NAMES
3216 and for symbols in SYMS_TO_RENAME. */
3221 /* If the caller requested PHI nodes to be added, compute
3222 dominance frontiers. */
3223 dfs = XNEWVEC (bitmap, last_basic_block);
3225 dfs[bb->index] = BITMAP_ALLOC (NULL);
3226 compute_dominance_frontiers (dfs);
3228 if (sbitmap_first_set_bit (old_ssa_names) >= 0)
3230 sbitmap_iterator sbi;
3232 /* insert_update_phi_nodes_for will call add_new_name_mapping
3233 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3234 will grow while we are traversing it (but it will not
3235 gain any new members). Copy OLD_SSA_NAMES to a temporary
3237 sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
3238 sbitmap_copy (tmp, old_ssa_names);
3239 EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
3240 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3245 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3246 insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks_to_update,
3250 BITMAP_FREE (dfs[bb->index]);
3253 /* Insertion of PHI nodes may have added blocks to the region.
3254 We need to re-compute START_BB to include the newly added
3256 if (start_bb != ENTRY_BLOCK_PTR)
3257 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3261 /* Reset the current definition for name and symbol before renaming
3263 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3264 set_current_def (ssa_name (i), NULL_TREE);
3266 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3267 set_current_def (referenced_var (i), NULL_TREE);
3269 /* Now start the renaming process at START_BB. */
3270 tmp = sbitmap_alloc (last_basic_block);
3272 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3275 rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
3279 /* Debugging dumps. */
3285 dump_update_ssa (dump_file);
3287 fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
3291 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3293 fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
3294 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
3295 c, PERCENT (c, last_basic_block));
3297 if (dump_flags & TDF_DETAILS)
3299 fprintf (dump_file, "Affected blocks: ");
3300 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3301 fprintf (dump_file, "%u ", i);
3302 fprintf (dump_file, "\n");
3305 fprintf (dump_file, "\n\n");
3308 /* Free allocated memory. */
3310 delete_update_ssa ();
3312 timevar_pop (TV_TREE_SSA_INCREMENTAL);