1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
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"
39 #include "tree-gimple.h"
40 #include "tree-inline.h"
44 #include "tree-dump.h"
45 #include "tree-pass.h"
52 /* This file builds the SSA form for a function as described in:
53 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
54 Computing Static Single Assignment Form and the Control Dependence
55 Graph. ACM Transactions on Programming Languages and Systems,
56 13(4):451-490, October 1991. */
58 /* True if the code is in ssa form. */
61 /* Structure to map a variable VAR to the set of blocks that contain
62 definitions for VAR. */
68 /* Blocks that contain definitions of VAR. Bit I will be set if the
69 Ith block contains a definition of VAR. */
72 /* Blocks that contain a PHI node for VAR. */
75 /* Blocks where VAR is live-on-entry. Similar semantics as
81 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
82 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
83 basic blocks where VAR is defined (assigned a new value). It also
84 contains a bitmap of all the blocks where VAR is live-on-entry
85 (i.e., there is a use of VAR in block B without a preceding
86 definition in B). The live-on-entry information is used when
87 computing PHI pruning heuristics. */
88 static htab_t def_blocks;
90 /* Stack of trees used to restore the global currdefs to its original
91 state after completing rewriting of a block and its dominator
92 children. Its elements have the following properties:
94 - An SSA_NAME indicates that the current definition of the
95 underlying variable should be set to the given SSA_NAME.
97 - A _DECL node indicates that the underlying variable has no
100 - A NULL node is used to mark the last node associated with the
103 - A NULL node at the top entry is used to mark the last node
104 associated with the current block. */
105 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;
115 /* Symbols whose SSA form needs to be updated or created for the first
117 static bitmap syms_to_rename;
119 /* Set of SSA names that have been marked to be released after they
120 were registered in the replacement table. They will be finally
121 released after we finish updating the SSA web. */
122 static bitmap names_to_release;
124 /* For each block, the phi nodes that need to be rewritten are stored into
127 typedef VEC(tree, heap) *tree_vec;
128 DEF_VEC_P (tree_vec);
129 DEF_VEC_ALLOC_P (tree_vec, heap);
131 static VEC(tree_vec, heap) *phis_to_rewrite;
133 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
135 static bitmap blocks_with_phis_to_rewrite;
137 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
138 to grow as the callers to register_new_name_mapping will typically
139 create new names on the fly. FIXME. Currently set to 1/3 to avoid
140 frequent reallocations but still need to find a reasonable growth
142 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
144 /* Tuple used to represent replacement mappings. */
151 /* NEW -> OLD_SET replacement table. If we are replacing several
152 existing SSA names O_1, O_2, ..., O_j with a new name N_i,
153 then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */
154 static htab_t repl_tbl;
156 /* true if register_new_name_mapping needs to initialize the data
157 structures needed by update_ssa. */
158 static bool need_to_initialize_update_ssa_p = true;
160 /* true if update_ssa needs to update virtual operands. */
161 static bool need_to_update_vops_p = false;
163 /* Statistics kept by update_ssa to use in the virtual mapping
164 heuristic. If the number of virtual mappings is beyond certain
165 threshold, the updater will switch from using the mappings into
166 renaming the virtual symbols from scratch. In some cases, the
167 large number of name mappings for virtual names causes significant
168 slowdowns in the PHI insertion code. */
169 struct update_ssa_stats_d
171 unsigned num_virtual_mappings;
172 unsigned num_total_mappings;
173 bitmap virtual_symbols;
174 unsigned num_virtual_symbols;
176 static struct update_ssa_stats_d update_ssa_stats;
178 /* Global data to attach to the main dominator walk structure. */
179 struct mark_def_sites_global_data
181 /* This bitmap contains the variables which are set before they
182 are used in a basic block. */
185 /* Bitmap of names to rename. */
186 sbitmap names_to_rename;
188 /* Set of blocks that mark_def_sites deems interesting for the
189 renamer to process. */
190 sbitmap interesting_blocks;
194 /* Information stored for SSA names. */
197 /* This field indicates whether or not the variable may need PHI nodes.
198 See the enum's definition for more detailed information about the
200 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
202 /* The actual definition of the ssa name. */
207 /* The main entry point to the SSA renamer (rewrite_blocks) may be
208 called several times to do different, but related, tasks.
209 Initially, we need it to rename the whole program into SSA form.
210 At other times, we may need it to only rename into SSA newly
211 exposed symbols. Finally, we can also call it to incrementally fix
212 an already built SSA web. */
214 /* Convert the whole function into SSA form. */
217 /* Incrementally update the SSA web by replacing existing SSA
218 names with new ones. See update_ssa for details. */
223 /* Use TREE_VISITED to keep track of which statements we want to
224 rename. When renaming a subset of the variables, not all
225 statements will be processed. This is decided in mark_def_sites. */
226 #define REWRITE_THIS_STMT(T) TREE_VISITED (T)
228 /* Use the unsigned flag to keep track of which statements we want to
229 visit when marking new definition sites. This is slightly
230 different than REWRITE_THIS_STMT: it's used by update_ssa to
231 distinguish statements that need to have both uses and defs
232 processed from those that only need to have their defs processed.
233 Statements that define new SSA names only need to have their defs
234 registered, but they don't need to have their uses renamed. */
235 #define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
238 /* Prototypes for debugging functions. */
239 extern void dump_tree_ssa (FILE *);
240 extern void debug_tree_ssa (void);
241 extern void debug_def_blocks (void);
242 extern void dump_tree_ssa_stats (FILE *);
243 extern void debug_tree_ssa_stats (void);
244 void dump_update_ssa (FILE *);
245 void debug_update_ssa (void);
246 void dump_names_replaced_by (FILE *, tree);
247 void debug_names_replaced_by (tree);
249 /* Get the information associated with NAME. */
251 static inline struct ssa_name_info *
252 get_ssa_name_ann (tree name)
254 if (!SSA_NAME_AUX (name))
255 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
257 return (struct ssa_name_info *) SSA_NAME_AUX (name);
261 /* Gets phi_state field for VAR. */
263 static inline enum need_phi_state
264 get_phi_state (tree var)
266 if (TREE_CODE (var) == SSA_NAME)
267 return get_ssa_name_ann (var)->need_phi_state;
269 return var_ann (var)->need_phi_state;
273 /* Sets phi_state field for VAR to STATE. */
276 set_phi_state (tree var, enum need_phi_state state)
278 if (TREE_CODE (var) == SSA_NAME)
279 get_ssa_name_ann (var)->need_phi_state = state;
281 var_ann (var)->need_phi_state = state;
285 /* Return the current definition for VAR. */
288 get_current_def (tree var)
290 if (TREE_CODE (var) == SSA_NAME)
291 return get_ssa_name_ann (var)->current_def;
293 return var_ann (var)->current_def;
297 /* Sets current definition of VAR to DEF. */
300 set_current_def (tree var, tree def)
302 if (TREE_CODE (var) == SSA_NAME)
303 get_ssa_name_ann (var)->current_def = def;
305 var_ann (var)->current_def = def;
309 /* Compute global livein information given the set of blockx where
310 an object is locally live at the start of the block (LIVEIN)
311 and the set of blocks where the object is defined (DEF_BLOCKS).
313 Note: This routine augments the existing local livein information
314 to include global livein (i.e., it modifies the underlying bitmap
318 compute_global_livein (bitmap livein, bitmap def_blocks)
320 basic_block bb, *worklist, *tos;
325 = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
327 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
329 *tos++ = BASIC_BLOCK (i);
332 /* Iterate until the worklist is empty. */
333 while (tos != worklist)
338 /* Pull a block off the worklist. */
341 /* For each predecessor block. */
342 FOR_EACH_EDGE (e, ei, bb->preds)
344 basic_block pred = e->src;
345 int pred_index = pred->index;
347 /* None of this is necessary for the entry block. */
348 if (pred != ENTRY_BLOCK_PTR
349 && ! bitmap_bit_p (livein, pred_index)
350 && ! bitmap_bit_p (def_blocks, pred_index))
353 bitmap_set_bit (livein, pred_index);
362 /* Return the set of blocks where variable VAR is defined and the blocks
363 where VAR is live on entry (livein). If no entry is found in
364 DEF_BLOCKS, a new one is created and returned. */
366 static inline struct def_blocks_d *
367 get_def_blocks_for (tree var)
369 struct def_blocks_d db, *db_p;
373 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
376 db_p = XNEW (struct def_blocks_d);
378 db_p->def_blocks = BITMAP_ALLOC (NULL);
379 db_p->phi_blocks = BITMAP_ALLOC (NULL);
380 db_p->livein_blocks = BITMAP_ALLOC (NULL);
381 *slot = (void *) db_p;
384 db_p = (struct def_blocks_d *) *slot;
390 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
391 VAR is defined by a PHI node. */
394 set_def_block (tree var, basic_block bb, bool phi_p)
396 struct def_blocks_d *db_p;
397 enum need_phi_state state;
399 state = get_phi_state (var);
400 db_p = get_def_blocks_for (var);
402 /* Set the bit corresponding to the block where VAR is defined. */
403 bitmap_set_bit (db_p->def_blocks, bb->index);
405 bitmap_set_bit (db_p->phi_blocks, bb->index);
407 /* Keep track of whether or not we may need to insert PHI nodes.
409 If we are in the UNKNOWN state, then this is the first definition
410 of VAR. Additionally, we have not seen any uses of VAR yet, so
411 we do not need a PHI node for this variable at this time (i.e.,
412 transition to NEED_PHI_STATE_NO).
414 If we are in any other state, then we either have multiple definitions
415 of this variable occurring in different blocks or we saw a use of the
416 variable which was not dominated by the block containing the
417 definition(s). In this case we may need a PHI node, so enter
418 state NEED_PHI_STATE_MAYBE. */
419 if (state == NEED_PHI_STATE_UNKNOWN)
420 set_phi_state (var, NEED_PHI_STATE_NO);
422 set_phi_state (var, NEED_PHI_STATE_MAYBE);
426 /* Mark block BB as having VAR live at the entry to BB. */
429 set_livein_block (tree var, basic_block bb)
431 struct def_blocks_d *db_p;
432 enum need_phi_state state = get_phi_state (var);
434 db_p = get_def_blocks_for (var);
436 /* Set the bit corresponding to the block where VAR is live in. */
437 bitmap_set_bit (db_p->livein_blocks, bb->index);
439 /* Keep track of whether or not we may need to insert PHI nodes.
441 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
442 by the single block containing the definition(s) of this variable. If
443 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
444 NEED_PHI_STATE_MAYBE. */
445 if (state == NEED_PHI_STATE_NO)
447 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
449 if (def_block_index == -1
450 || ! dominated_by_p (CDI_DOMINATORS, bb,
451 BASIC_BLOCK (def_block_index)))
452 set_phi_state (var, NEED_PHI_STATE_MAYBE);
455 set_phi_state (var, NEED_PHI_STATE_MAYBE);
459 /* Return true if symbol SYM is marked for renaming. */
462 symbol_marked_for_renaming (tree sym)
464 gcc_assert (DECL_P (sym));
465 return bitmap_bit_p (syms_to_rename, DECL_UID (sym));
469 /* Return true if NAME is in OLD_SSA_NAMES. */
472 is_old_name (tree name)
474 unsigned ver = SSA_NAME_VERSION (name);
475 return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
479 /* Return true if NAME is in NEW_SSA_NAMES. */
482 is_new_name (tree name)
484 unsigned ver = SSA_NAME_VERSION (name);
485 return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
489 /* Hashing and equality functions for REPL_TBL. */
492 repl_map_hash (const void *p)
494 return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
498 repl_map_eq (const void *p1, const void *p2)
500 return ((const struct repl_map_d *)p1)->name
501 == ((const struct repl_map_d *)p2)->name;
505 repl_map_free (void *p)
507 BITMAP_FREE (((struct repl_map_d *)p)->set);
512 /* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET). */
515 names_replaced_by (tree new)
521 slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
523 /* If N was not registered in the replacement table, return NULL. */
524 if (slot == NULL || *slot == NULL)
527 return ((struct repl_map_d *) *slot)->set;
531 /* Add OLD to REPL_TBL[NEW].SET. */
534 add_to_repl_tbl (tree new, tree old)
536 struct repl_map_d m, *mp;
540 slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
543 mp = XNEW (struct repl_map_d);
545 mp->set = BITMAP_ALLOC (NULL);
549 mp = (struct repl_map_d *) *slot;
551 bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
555 /* Add a new mapping NEW -> OLD REPL_TBL. Every entry N_i in REPL_TBL
556 represents the set of names O_1 ... O_j replaced by N_i. This is
557 used by update_ssa and its helpers to introduce new SSA names in an
558 already formed SSA web. */
561 add_new_name_mapping (tree new, tree old)
563 timevar_push (TV_TREE_SSA_INCREMENTAL);
565 /* OLD and NEW must be different SSA names for the same symbol. */
566 gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old));
568 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
569 caller may have created new names since the set was created. */
570 if (new_ssa_names->n_bits <= num_ssa_names - 1)
572 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
573 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
574 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
577 /* If this mapping is for virtual names, we will need to update
579 if (!is_gimple_reg (new))
584 need_to_update_vops_p = true;
586 /* Keep counts of virtual mappings and symbols to use in the
587 virtual mapping heuristic. If we have large numbers of
588 virtual mappings for a relatively low number of symbols, it
589 will make more sense to rename the symbols from scratch.
590 Otherwise, the insertion of PHI nodes for each of the old
591 names in these mappings will be very slow. */
592 sym = SSA_NAME_VAR (new);
593 uid = DECL_UID (sym);
594 update_ssa_stats.num_virtual_mappings++;
595 if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid))
597 bitmap_set_bit (update_ssa_stats.virtual_symbols, uid);
598 update_ssa_stats.num_virtual_symbols++;
602 /* Update the REPL_TBL table. */
603 add_to_repl_tbl (new, old);
605 /* If OLD had already been registered as a new name, then all the
606 names that OLD replaces should also be replaced by NEW. */
607 if (is_new_name (old))
608 bitmap_ior_into (names_replaced_by (new), names_replaced_by (old));
610 /* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
612 SET_BIT (new_ssa_names, SSA_NAME_VERSION (new));
613 SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
615 /* Update mapping counter to use in the virtual mapping heuristic. */
616 update_ssa_stats.num_total_mappings++;
618 timevar_pop (TV_TREE_SSA_INCREMENTAL);
622 /* Call back for walk_dominator_tree used to collect definition sites
623 for every variable in the function. For every statement S in block
626 1- Variables defined by S in the DEFS of S are marked in the bitmap
627 WALK_DATA->GLOBAL_DATA->KILLS.
629 2- If S uses a variable VAR and there is no preceding kill of VAR,
630 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
632 This information is used to determine which variables are live
633 across block boundaries to reduce the number of PHI nodes
637 mark_def_sites (struct dom_walk_data *walk_data,
639 block_stmt_iterator bsi)
641 struct mark_def_sites_global_data *gd =
642 (struct mark_def_sites_global_data *) walk_data->global_data;
643 bitmap kills = gd->kills;
649 stmt = bsi_stmt (bsi);
650 update_stmt_if_modified (stmt);
652 REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
653 REWRITE_THIS_STMT (stmt) = 0;
655 /* If a variable is used before being set, then the variable is live
656 across a block boundary, so mark it live-on-entry to BB. */
657 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
658 SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL)
660 tree sym = USE_FROM_PTR (use_p);
661 gcc_assert (DECL_P (sym));
662 if (!bitmap_bit_p (kills, DECL_UID (sym)))
663 set_livein_block (sym, bb);
664 REWRITE_THIS_STMT (stmt) = 1;
667 /* Note that virtual definitions are irrelevant for computing KILLS
668 because a V_MAY_DEF does not constitute a killing definition of the
669 variable. However, the operand of a virtual definitions is a use
670 of the variable, so it may cause the variable to be considered
672 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
674 tree sym = USE_FROM_PTR (use_p);
675 gcc_assert (DECL_P (sym));
676 set_livein_block (sym, bb);
677 set_def_block (sym, bb, false);
678 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
679 REWRITE_THIS_STMT (stmt) = 1;
682 /* Now process the defs and must-defs made by this statement. */
683 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
685 gcc_assert (DECL_P (def));
686 set_def_block (def, bb, false);
687 bitmap_set_bit (kills, DECL_UID (def));
688 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
691 /* If we found the statement interesting then also mark the block BB
693 if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
694 SET_BIT (gd->interesting_blocks, bb->index);
698 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
699 return a bitmap with all the blocks in the iterated dominance
700 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
701 frontier information as returned by compute_dominance_frontiers.
703 The resulting set of blocks are the potential sites where PHI nodes
704 are needed. The caller is responsible from freeing the memory
705 allocated for the return value. */
708 find_idf (bitmap def_blocks, bitmap *dfs)
712 VEC(int,heap) *work_stack;
713 bitmap phi_insertion_points;
715 work_stack = VEC_alloc (int, heap, n_basic_blocks);
716 phi_insertion_points = BITMAP_ALLOC (NULL);
718 /* Seed the work list with all the blocks in DEF_BLOCKS. */
719 EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
720 /* We use VEC_quick_push here for speed. This is safe because we
721 know that the number of definition blocks is no greater than
722 the number of basic blocks, which is the initial capacity of
724 VEC_quick_push (int, work_stack, bb_index);
726 /* Pop a block off the worklist, add every block that appears in
727 the original block's DF that we have not already processed to
728 the worklist. Iterate until the worklist is empty. Blocks
729 which are added to the worklist are potential sites for
731 while (VEC_length (int, work_stack) > 0)
733 bb_index = VEC_pop (int, work_stack);
735 /* Since the registration of NEW -> OLD name mappings is done
736 separately from the call to update_ssa, when updating the SSA
737 form, the basic blocks where new and/or old names are defined
738 may have disappeared by CFG cleanup calls. In this case,
739 we may pull a non-existing block from the work stack. */
740 gcc_assert (bb_index < (unsigned) last_basic_block);
742 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
745 /* Use a safe push because if there is a definition of VAR
746 in every basic block, then WORK_STACK may eventually have
747 more than N_BASIC_BLOCK entries. */
748 VEC_safe_push (int, heap, work_stack, bb_index);
749 bitmap_set_bit (phi_insertion_points, bb_index);
753 VEC_free (int, heap, work_stack);
755 return phi_insertion_points;
759 /* Return the set of blocks where variable VAR is defined and the blocks
760 where VAR is live on entry (livein). Return NULL, if no entry is
761 found in DEF_BLOCKS. */
763 static inline struct def_blocks_d *
764 find_def_blocks_for (tree var)
766 struct def_blocks_d dm;
768 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
772 /* Retrieve or create a default definition for symbol SYM. */
775 get_default_def_for (tree sym)
777 tree ddef = default_def (sym);
779 if (ddef == NULL_TREE)
781 ddef = make_ssa_name (sym, build_empty_stmt ());
782 set_default_def (sym, ddef);
789 /* Marks phi node PHI in basic block BB for rewrite. */
792 mark_phi_for_rewrite (basic_block bb, tree phi)
795 unsigned i, idx = bb->index;
797 if (REWRITE_THIS_STMT (phi))
799 REWRITE_THIS_STMT (phi) = 1;
801 if (!blocks_with_phis_to_rewrite)
804 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
805 VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
806 for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
807 VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
809 phis = VEC_index (tree_vec, phis_to_rewrite, idx);
811 phis = VEC_alloc (tree, heap, 10);
813 VEC_safe_push (tree, heap, phis, phi);
814 VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
817 /* Insert PHI nodes for variable VAR using the iterated dominance
818 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
819 function assumes that the caller is incrementally updating the SSA
820 form, in which case (1) VAR is assumed to be an SSA name, (2) a new
821 SSA name is created for VAR's symbol, and, (3) all the arguments
822 for the newly created PHI node are set to VAR.
824 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
825 PHI node for VAR. On exit, only the nodes that received a PHI node
826 for VAR will be present in PHI_INSERTION_POINTS. */
829 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
836 struct def_blocks_d *def_map;
838 def_map = find_def_blocks_for (var);
839 gcc_assert (def_map);
841 /* Remove the blocks where we already have PHI nodes for VAR. */
842 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
844 /* Now compute global livein for this variable. Note this modifies
845 def_map->livein_blocks. */
846 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
848 /* And insert the PHI nodes. */
849 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
852 bb = BASIC_BLOCK (bb_index);
854 if (update_p && TREE_CODE (var) == SSA_NAME)
856 /* If we are rewriting SSA names, create the LHS of the PHI
857 node by duplicating VAR. This is useful in the case of
858 pointers, to also duplicate pointer attributes (alias
859 information, in particular). */
863 phi = create_phi_node (var, bb);
864 new_lhs = duplicate_ssa_name (var, phi);
865 SET_PHI_RESULT (phi, new_lhs);
866 add_new_name_mapping (new_lhs, var);
868 /* Add VAR to every argument slot of PHI. We need VAR in
869 every argument so that rewrite_update_phi_arguments knows
870 which name is this PHI node replacing. If VAR is a
871 symbol marked for renaming, this is not necessary, the
872 renamer will use the symbol on the LHS to get its
873 reaching definition. */
874 FOR_EACH_EDGE (e, ei, bb->preds)
875 add_phi_arg (phi, var, e);
879 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
880 phi = create_phi_node (sym, bb);
883 /* Mark this PHI node as interesting for update_ssa. */
884 REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
885 mark_phi_for_rewrite (bb, phi);
890 /* Insert PHI nodes at the dominance frontier of blocks with variable
891 definitions. DFS contains the dominance frontier information for
892 the flowgraph. PHI nodes will only be inserted at the dominance
893 frontier of definition blocks for variables whose NEED_PHI_STATE
894 annotation is marked as ``maybe'' or ``unknown'' (computed by
898 insert_phi_nodes (bitmap *dfs)
900 referenced_var_iterator rvi;
903 timevar_push (TV_TREE_INSERT_PHI_NODES);
905 FOR_EACH_REFERENCED_VAR (var, rvi)
907 struct def_blocks_d *def_map;
910 def_map = find_def_blocks_for (var);
914 if (get_phi_state (var) != NEED_PHI_STATE_NO)
916 idf = find_idf (def_map->def_blocks, dfs);
917 insert_phi_nodes_for (var, idf, false);
922 timevar_pop (TV_TREE_INSERT_PHI_NODES);
926 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
927 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
928 into the stack pointed to by BLOCK_DEFS_P. */
931 register_new_def (tree def, VEC(tree,heap) **block_defs_p)
933 tree var = SSA_NAME_VAR (def);
936 /* If this variable is set in a single basic block and all uses are
937 dominated by the set(s) in that single basic block, then there is
938 no reason to record anything for this variable in the block local
939 definition stacks. Doing so just wastes time and memory.
941 This is the same test to prune the set of variables which may
942 need PHI nodes. So we just use that information since it's already
943 computed and available for us to use. */
944 if (get_phi_state (var) == NEED_PHI_STATE_NO)
946 set_current_def (var, def);
950 currdef = get_current_def (var);
952 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
953 later used by the dominator tree callbacks to restore the reaching
954 definitions for all the variables defined in the block after a recursive
955 visit to all its immediately dominated blocks. If there is no current
956 reaching definition, then just record the underlying _DECL node. */
957 VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var);
959 /* Set the current reaching definition for VAR to be DEF. */
960 set_current_def (var, def);
964 /* Perform a depth-first traversal of the dominator tree looking for
965 variables to rename. BB is the block where to start searching.
966 Renaming is a five step process:
968 1- Every definition made by PHI nodes at the start of the blocks is
969 registered as the current definition for the corresponding variable.
971 2- Every statement in BB is rewritten. USE and VUSE operands are
972 rewritten with their corresponding reaching definition. DEF and
973 VDEF targets are registered as new definitions.
975 3- All the PHI nodes in successor blocks of BB are visited. The
976 argument corresponding to BB is replaced with its current reaching
979 4- Recursively rewrite every dominator child block of BB.
981 5- Restore (in reverse order) the current reaching definition for every
982 new definition introduced in this block. This is done so that when
983 we return from the recursive call, all the current reaching
984 definitions are restored to the names that were valid in the
985 dominator parent of BB. */
987 /* SSA Rewriting Step 1. Initialization, create a block local stack
988 of reaching definitions for new SSA names produced in this block
989 (BLOCK_DEFS). Register new definitions for every PHI node in the
993 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
998 if (dump_file && (dump_flags & TDF_DETAILS))
999 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1001 /* Mark the unwind point for this block. */
1002 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1004 /* Step 1. Register new definitions for every PHI node in the block.
1005 Conceptually, all the PHI nodes are executed in parallel and each PHI
1006 node introduces a new version for the associated variable. */
1007 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1009 tree result = PHI_RESULT (phi);
1010 register_new_def (result, &block_defs_stack);
1015 /* Return the current definition for variable VAR. If none is found,
1016 create a new SSA name to act as the zeroth definition for VAR. If VAR
1017 is call clobbered and there exists a more recent definition of
1018 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
1019 has been clobbered by a function call since its last assignment. */
1022 get_reaching_def (tree var)
1024 tree currdef_var, avar;
1026 /* Lookup the current reaching definition for VAR. */
1027 currdef_var = get_current_def (var);
1029 /* If there is no reaching definition for VAR, create and register a
1030 default definition for it (if needed). */
1031 if (currdef_var == NULL_TREE)
1033 avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
1034 currdef_var = get_default_def_for (avar);
1035 set_current_def (var, currdef_var);
1038 /* Return the current reaching definition for VAR, or the default
1039 definition, if we had to create one. */
1044 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1045 the block with its immediate reaching definitions. Update the current
1046 definition of a variable when a new real or virtual definition is found. */
1049 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1050 basic_block bb ATTRIBUTE_UNUSED,
1051 block_stmt_iterator si)
1054 use_operand_p use_p;
1055 def_operand_p def_p;
1058 stmt = bsi_stmt (si);
1060 /* If mark_def_sites decided that we don't need to rewrite this
1061 statement, ignore it. */
1062 if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1065 if (dump_file && (dump_flags & TDF_DETAILS))
1067 fprintf (dump_file, "Renaming statement ");
1068 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1069 fprintf (dump_file, "\n");
1072 /* Step 1. Rewrite USES and VUSES in the statement. */
1073 if (REWRITE_THIS_STMT (stmt))
1074 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1075 SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
1077 tree var = USE_FROM_PTR (use_p);
1078 gcc_assert (DECL_P (var));
1079 SET_USE (use_p, get_reaching_def (var));
1082 /* Step 2. Register the statement's DEF and VDEF operands. */
1083 if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1084 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1086 tree var = DEF_FROM_PTR (def_p);
1087 gcc_assert (DECL_P (var));
1088 SET_DEF (def_p, make_ssa_name (var, stmt));
1089 register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1094 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1095 PHI nodes. For every PHI node found, add a new argument containing the
1096 current reaching definition for the variable and the edge through which
1097 that definition is reaching the PHI node. */
1100 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1106 FOR_EACH_EDGE (e, ei, bb->succs)
1110 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1113 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
1114 add_phi_arg (phi, currdef, e);
1120 /* Called after visiting basic block BB. Restore CURRDEFS to its
1124 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1125 basic_block bb ATTRIBUTE_UNUSED)
1127 /* Restore CURRDEFS to its original state. */
1128 while (VEC_length (tree, block_defs_stack) > 0)
1130 tree tmp = VEC_pop (tree, block_defs_stack);
1131 tree saved_def, var;
1133 if (tmp == NULL_TREE)
1136 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1137 definition of its underlying variable. If we recorded anything
1138 else, it must have been an _DECL node and its current reaching
1139 definition must have been NULL. */
1140 if (TREE_CODE (tmp) == SSA_NAME)
1143 var = SSA_NAME_VAR (saved_def);
1151 set_current_def (var, saved_def);
1156 /* Dump SSA information to FILE. */
1159 dump_tree_ssa (FILE *file)
1162 const char *funcname
1163 = lang_hooks.decl_printable_name (current_function_decl, 2);
1165 fprintf (file, "SSA information for %s\n\n", funcname);
1169 dump_bb (bb, file, 0);
1171 print_generic_stmt (file, phi_nodes (bb), dump_flags);
1172 fputs ("\n\n", file);
1177 /* Dump SSA information to stderr. */
1180 debug_tree_ssa (void)
1182 dump_tree_ssa (stderr);
1186 /* Dump statistics for the hash table HTAB. */
1189 htab_statistics (FILE *file, htab_t htab)
1191 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1192 (long) htab_size (htab),
1193 (long) htab_elements (htab),
1194 htab_collisions (htab));
1198 /* Dump SSA statistics on FILE. */
1201 dump_tree_ssa_stats (FILE *file)
1203 fprintf (file, "\nHash table statistics:\n");
1205 fprintf (file, " def_blocks: ");
1206 htab_statistics (file, def_blocks);
1208 fprintf (file, "\n");
1212 /* Dump SSA statistics on stderr. */
1215 debug_tree_ssa_stats (void)
1217 dump_tree_ssa_stats (stderr);
1221 /* Hashing and equality functions for DEF_BLOCKS. */
1224 def_blocks_hash (const void *p)
1226 return htab_hash_pointer
1227 ((const void *)((const struct def_blocks_d *)p)->var);
1231 def_blocks_eq (const void *p1, const void *p2)
1233 return ((const struct def_blocks_d *)p1)->var
1234 == ((const struct def_blocks_d *)p2)->var;
1238 /* Free memory allocated by one entry in DEF_BLOCKS. */
1241 def_blocks_free (void *p)
1243 struct def_blocks_d *entry = (struct def_blocks_d *) p;
1244 BITMAP_FREE (entry->def_blocks);
1245 BITMAP_FREE (entry->phi_blocks);
1246 BITMAP_FREE (entry->livein_blocks);
1251 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1254 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1256 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1258 fprintf (stderr, "VAR: ");
1259 print_generic_expr (stderr, db_p->var, dump_flags);
1260 bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1261 bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1267 /* Dump the DEF_BLOCKS hash table on stderr. */
1270 debug_def_blocks (void)
1272 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1276 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1279 register_new_update_single (tree new_name, tree old_name)
1281 tree currdef = get_current_def (old_name);
1283 /* Push the current reaching definition into *BLOCK_DEFS_P.
1284 This stack is later used by the dominator tree callbacks to
1285 restore the reaching definitions for all the variables
1286 defined in the block after a recursive visit to all its
1287 immediately dominated blocks. */
1288 VEC_reserve (tree, heap, block_defs_stack, 2);
1289 VEC_quick_push (tree, block_defs_stack, currdef);
1290 VEC_quick_push (tree, block_defs_stack, old_name);
1292 /* Set the current reaching definition for OLD_NAME to be
1294 set_current_def (old_name, new_name);
1298 /* Register NEW_NAME to be the new reaching definition for all the
1299 names in OLD_NAMES. Used by the incremental SSA update routines to
1300 replace old SSA names with new ones. */
1303 register_new_update_set (tree new_name, bitmap old_names)
1308 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1309 register_new_update_single (new_name, ssa_name (i));
1313 /* Initialization of block data structures for the incremental SSA
1314 update pass. Create a block local stack of reaching definitions
1315 for new SSA names produced in this block (BLOCK_DEFS). Register
1316 new definitions for every PHI node in the block. */
1319 rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1325 bool is_abnormal_phi;
1327 if (dump_file && (dump_flags & TDF_DETAILS))
1328 fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
1331 /* Mark the unwind point for this block. */
1332 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1334 /* Mark the LHS if any of the arguments flows through an abnormal
1336 is_abnormal_phi = false;
1337 FOR_EACH_EDGE (e, ei, bb->preds)
1338 if (e->flags & EDGE_ABNORMAL)
1340 is_abnormal_phi = true;
1344 /* If any of the PHI nodes is a replacement for a name in
1345 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
1346 register it as a new definition for its corresponding name. Also
1347 register definitions for names whose underlying symbols are
1348 marked for renaming. */
1349 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1353 if (!REGISTER_DEFS_IN_THIS_STMT (phi))
1356 lhs = PHI_RESULT (phi);
1357 lhs_sym = SSA_NAME_VAR (lhs);
1359 if (symbol_marked_for_renaming (lhs_sym))
1360 register_new_update_single (lhs, lhs_sym);
1363 /* If LHS is a new name, register a new definition for all
1364 the names replaced by LHS. */
1365 if (is_new_name (lhs))
1366 register_new_update_set (lhs, names_replaced_by (lhs));
1368 /* If LHS is an OLD name, register it as a new definition
1370 if (is_old_name (lhs))
1371 register_new_update_single (lhs, lhs);
1374 if (is_abnormal_phi)
1375 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
1380 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
1381 the current reaching definition of every name re-written in BB to
1382 the original reaching definition before visiting BB. This
1383 unwinding must be done in the opposite order to what is done in
1384 register_new_update_set. */
1387 rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1388 basic_block bb ATTRIBUTE_UNUSED)
1390 while (VEC_length (tree, block_defs_stack) > 0)
1392 tree var = VEC_pop (tree, block_defs_stack);
1395 /* NULL indicates the unwind stop point for this block (see
1396 rewrite_update_init_block). */
1400 saved_def = VEC_pop (tree, block_defs_stack);
1401 set_current_def (var, saved_def);
1406 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1407 it is a symbol marked for renaming, replace it with USE_P's current
1408 reaching definition. */
1411 maybe_replace_use (use_operand_p use_p)
1413 tree rdef = NULL_TREE;
1414 tree use = USE_FROM_PTR (use_p);
1415 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1417 if (symbol_marked_for_renaming (sym))
1418 rdef = get_reaching_def (sym);
1419 else if (is_old_name (use))
1420 rdef = get_reaching_def (use);
1422 if (rdef && rdef != use)
1423 SET_USE (use_p, rdef);
1427 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1428 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1429 register it as the current definition for the names replaced by
1433 maybe_register_def (def_operand_p def_p, tree stmt)
1435 tree def = DEF_FROM_PTR (def_p);
1436 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1438 /* If DEF is a naked symbol that needs renaming, create a
1440 if (symbol_marked_for_renaming (sym))
1444 def = make_ssa_name (def, stmt);
1445 SET_DEF (def_p, def);
1448 register_new_update_single (def, sym);
1452 /* If DEF is a new name, register it as a new definition
1453 for all the names replaced by DEF. */
1454 if (is_new_name (def))
1455 register_new_update_set (def, names_replaced_by (def));
1457 /* If DEF is an old name, register DEF as a new
1458 definition for itself. */
1459 if (is_old_name (def))
1460 register_new_update_single (def, def);
1465 /* Update every variable used in the statement pointed-to by SI. The
1466 statement is assumed to be in SSA form already. Names in
1467 OLD_SSA_NAMES used by SI will be updated to their current reaching
1468 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1469 will be registered as a new definition for their corresponding name
1470 in OLD_SSA_NAMES. */
1473 rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1474 basic_block bb ATTRIBUTE_UNUSED,
1475 block_stmt_iterator si)
1479 use_operand_p use_p;
1480 def_operand_p def_p;
1483 stmt = bsi_stmt (si);
1484 ann = stmt_ann (stmt);
1486 /* Only update marked statements. */
1487 if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1490 if (dump_file && (dump_flags & TDF_DETAILS))
1492 fprintf (dump_file, "Updating SSA information for statement ");
1493 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1494 fprintf (dump_file, "\n");
1497 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1498 symbol is marked for renaming. */
1499 if (REWRITE_THIS_STMT (stmt))
1501 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1502 maybe_replace_use (use_p);
1504 if (need_to_update_vops_p)
1505 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1506 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1507 maybe_replace_use (use_p);
1510 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1511 Also register definitions for names whose underlying symbol is
1512 marked for renaming. */
1513 if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1515 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1516 maybe_register_def (def_p, stmt);
1518 if (need_to_update_vops_p)
1519 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
1520 maybe_register_def (def_p, stmt);
1525 /* Replace the operand pointed to by USE_P with USE's current reaching
1529 replace_use (use_operand_p use_p, tree use)
1531 tree rdef = get_reaching_def (use);
1533 SET_USE (use_p, rdef);
1537 /* Visit all the successor blocks of BB looking for PHI nodes. For
1538 every PHI node found, check if any of its arguments is in
1539 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1540 definition, replace it. */
1543 rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1550 FOR_EACH_EDGE (e, ei, bb->succs)
1555 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1558 phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
1559 for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
1562 use_operand_p arg_p;
1564 gcc_assert (REWRITE_THIS_STMT (phi));
1566 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1567 arg = USE_FROM_PTR (arg_p);
1569 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
1572 if (arg == NULL_TREE)
1574 /* When updating a PHI node for a recently introduced
1575 symbol we may find NULL arguments. That's why we
1576 take the symbol from the LHS of the PHI node. */
1577 replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
1581 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
1583 if (symbol_marked_for_renaming (sym))
1584 replace_use (arg_p, sym);
1585 else if (is_old_name (arg))
1586 replace_use (arg_p, arg);
1589 if (e->flags & EDGE_ABNORMAL)
1590 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
1596 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
1599 ENTRY indicates the block where to start. Every block dominated by
1600 ENTRY will be rewritten.
1602 WHAT indicates what actions will be taken by the renamer (see enum
1605 BLOCKS are the set of interesting blocks for the dominator walker
1606 to process. If this set is NULL, then all the nodes dominated
1607 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
1608 are not present in BLOCKS are ignored. */
1611 rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
1613 struct dom_walk_data walk_data;
1615 /* Rewrite all the basic blocks in the program. */
1616 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1618 /* Setup callbacks for the generic dominator tree walker. */
1619 memset (&walk_data, 0, sizeof (walk_data));
1621 walk_data.dom_direction = CDI_DOMINATORS;
1622 walk_data.interesting_blocks = blocks;
1624 if (what == REWRITE_UPDATE)
1625 walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
1627 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1629 if (what == REWRITE_ALL)
1630 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1631 else if (what == REWRITE_UPDATE)
1632 walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
1636 if (what == REWRITE_ALL)
1637 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1638 else if (what == REWRITE_UPDATE)
1639 walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
1643 if (what == REWRITE_ALL)
1644 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1645 else if (what == REWRITE_UPDATE)
1646 walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
1650 block_defs_stack = VEC_alloc (tree, heap, 10);
1652 /* Initialize the dominator walker. */
1653 init_walk_dominator_tree (&walk_data);
1655 /* Recursively walk the dominator tree rewriting each statement in
1656 each basic block. */
1657 walk_dominator_tree (&walk_data, entry);
1659 /* Finalize the dominator walker. */
1660 fini_walk_dominator_tree (&walk_data);
1662 /* Debugging dumps. */
1663 if (dump_file && (dump_flags & TDF_STATS))
1665 dump_dfa_stats (dump_file);
1667 dump_tree_ssa_stats (dump_file);
1672 htab_delete (def_blocks);
1676 VEC_free (tree, heap, block_defs_stack);
1678 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1682 /* Block initialization routine for mark_def_sites. Clear the
1683 KILLS bitmap at the start of each block. */
1686 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
1687 basic_block bb ATTRIBUTE_UNUSED)
1689 struct mark_def_sites_global_data *gd =
1690 (struct mark_def_sites_global_data *) walk_data->global_data;
1691 bitmap kills = gd->kills;
1692 bitmap_clear (kills);
1696 /* Mark the definition site blocks for each variable, so that we know
1697 where the variable is actually live.
1699 INTERESTING_BLOCKS will be filled in with all the blocks that
1700 should be processed by the renamer. It is assumed to be
1701 initialized and zeroed by the caller. */
1704 mark_def_site_blocks (sbitmap interesting_blocks)
1706 struct dom_walk_data walk_data;
1707 struct mark_def_sites_global_data mark_def_sites_global_data;
1708 referenced_var_iterator rvi;
1711 /* Allocate memory for the DEF_BLOCKS hash table. */
1712 def_blocks = htab_create (num_referenced_vars,
1713 def_blocks_hash, def_blocks_eq, def_blocks_free);
1714 FOR_EACH_REFERENCED_VAR(var, rvi)
1715 set_current_def (var, NULL_TREE);
1717 /* Setup callbacks for the generic dominator tree walker to find and
1718 mark definition sites. */
1719 walk_data.walk_stmts_backward = false;
1720 walk_data.dom_direction = CDI_DOMINATORS;
1721 walk_data.initialize_block_local_data = NULL;
1722 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1723 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1724 walk_data.before_dom_children_after_stmts = NULL;
1725 walk_data.after_dom_children_before_stmts = NULL;
1726 walk_data.after_dom_children_walk_stmts = NULL;
1727 walk_data.after_dom_children_after_stmts = NULL;
1728 walk_data.interesting_blocks = NULL;
1730 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1731 large enough to accommodate all the variables referenced in the
1732 function, not just the ones we are renaming. */
1733 mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
1735 /* Create the set of interesting blocks that will be filled by
1737 mark_def_sites_global_data.interesting_blocks = interesting_blocks;
1738 walk_data.global_data = &mark_def_sites_global_data;
1740 /* We do not have any local data. */
1741 walk_data.block_local_data_size = 0;
1743 /* Initialize the dominator walker. */
1744 init_walk_dominator_tree (&walk_data);
1746 /* Recursively walk the dominator tree. */
1747 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1749 /* Finalize the dominator walker. */
1750 fini_walk_dominator_tree (&walk_data);
1752 /* We no longer need this bitmap, clear and free it. */
1753 BITMAP_FREE (mark_def_sites_global_data.kills);
1757 /* Main entry point into the SSA builder. The renaming process
1758 proceeds in four main phases:
1760 1- Compute dominance frontier and immediate dominators, needed to
1761 insert PHI nodes and rename the function in dominator tree
1764 2- Find and mark all the blocks that define variables
1765 (mark_def_site_blocks).
1767 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1769 4- Rename all the blocks (rewrite_blocks) and statements in the program.
1771 Steps 3 and 4 are done using the dominator tree walker
1772 (walk_dominator_tree). */
1775 rewrite_into_ssa (void)
1779 sbitmap interesting_blocks;
1781 timevar_push (TV_TREE_SSA_OTHER);
1783 /* Initialize operand data structures. */
1784 init_ssa_operands ();
1786 /* Initialize the set of interesting blocks. The callback
1787 mark_def_sites will add to this set those blocks that the renamer
1789 interesting_blocks = sbitmap_alloc (last_basic_block);
1790 sbitmap_zero (interesting_blocks);
1792 /* Initialize dominance frontier. */
1793 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap));
1795 dfs[bb->index] = BITMAP_ALLOC (NULL);
1797 /* 1- Compute dominance frontiers. */
1798 calculate_dominance_info (CDI_DOMINATORS);
1799 compute_dominance_frontiers (dfs);
1801 /* 2- Find and mark definition sites. */
1802 mark_def_site_blocks (interesting_blocks);
1804 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
1805 insert_phi_nodes (dfs);
1807 /* 4- Rename all the blocks. */
1808 rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
1810 /* Free allocated memory. */
1812 BITMAP_FREE (dfs[bb->index]);
1814 sbitmap_free (interesting_blocks);
1816 timevar_pop (TV_TREE_SSA_OTHER);
1822 struct tree_opt_pass pass_build_ssa =
1826 rewrite_into_ssa, /* execute */
1829 0, /* static_pass_number */
1831 PROP_cfg | PROP_referenced_vars, /* properties_required */
1832 PROP_ssa, /* properties_provided */
1833 0, /* properties_destroyed */
1834 0, /* todo_flags_start */
1837 | TODO_remove_unused_locals, /* todo_flags_finish */
1842 /* Mark the definition of VAR at STMT and BB as interesting for the
1843 renamer. BLOCKS is the set of blocks that need updating. */
1846 mark_def_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
1849 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
1850 bitmap_set_bit (blocks, bb->index);
1854 bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
1856 set_def_block (var, bb, is_phi_p);
1858 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
1859 site for both itself and all the old names replaced by it. */
1860 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
1864 bitmap set = names_replaced_by (var);
1866 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1867 set_def_block (ssa_name (i), bb, is_phi_p);
1873 /* Mark the use of VAR at STMT and BB as interesting for the
1874 renamer. INSERT_PHI_P is true if we are going to insert new PHI
1875 nodes. BLOCKS is the set of blocks that need updating. */
1878 mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
1881 basic_block def_bb = bb_for_stmt (stmt);
1883 if (TREE_CODE (stmt) == PHI_NODE)
1884 mark_phi_for_rewrite (def_bb, stmt);
1886 REWRITE_THIS_STMT (stmt) = 1;
1887 bitmap_set_bit (blocks, bb->index);
1889 /* If VAR has not been defined in BB, then it is live-on-entry
1890 to BB. Note that we cannot just use the block holding VAR's
1891 definition because if VAR is one of the names in OLD_SSA_NAMES,
1892 it will have several definitions (itself and all the names that
1896 struct def_blocks_d *db_p = get_def_blocks_for (var);
1897 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
1898 set_livein_block (var, bb);
1903 /* Do a dominator walk starting at BB processing statements that
1904 reference symbols in SYMS_TO_RENAME. This is very similar to
1905 mark_def_sites, but the scan handles statements whose operands may
1906 already be SSA names. Blocks that contain defs or uses of symbols
1907 in SYMS_TO_RENAME are added to BLOCKS.
1909 If INSERT_PHI_P is true, mark those uses as live in the
1910 corresponding block. This is later used by the PHI placement
1911 algorithm to make PHI pruning decisions. */
1914 prepare_block_for_update (basic_block bb, bitmap blocks, bool insert_phi_p)
1917 block_stmt_iterator si;
1920 /* Process PHI nodes marking interesting those that define or use
1921 the symbols that we are interested in. */
1922 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1924 tree lhs_sym, lhs = PHI_RESULT (phi);
1926 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
1928 if (symbol_marked_for_renaming (lhs_sym))
1930 mark_use_interesting (lhs_sym, phi, bb, blocks, insert_phi_p);
1931 mark_def_interesting (lhs_sym, phi, bb, blocks, insert_phi_p);
1935 /* Process the statements. */
1936 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1940 use_operand_p use_p;
1941 def_operand_p def_p;
1943 stmt = bsi_stmt (si);
1945 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
1947 tree use = USE_FROM_PTR (use_p);
1948 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1949 if (symbol_marked_for_renaming (sym))
1950 mark_use_interesting (use, stmt, bb, blocks, insert_phi_p);
1953 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
1955 tree def = DEF_FROM_PTR (def_p);
1956 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1958 if (symbol_marked_for_renaming (sym))
1959 mark_def_interesting (def, stmt, bb, blocks, insert_phi_p);
1962 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
1964 tree def = DEF_FROM_PTR (def_p);
1965 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1967 if (symbol_marked_for_renaming (sym))
1969 mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p);
1970 mark_def_interesting (sym, stmt, bb, blocks, insert_phi_p);
1974 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE)
1976 tree use = USE_FROM_PTR (use_p);
1977 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1979 if (symbol_marked_for_renaming (sym))
1980 mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p);
1984 /* Now visit all the blocks dominated by BB. */
1985 for (son = first_dom_son (CDI_DOMINATORS, bb);
1987 son = next_dom_son (CDI_DOMINATORS, son))
1988 prepare_block_for_update (son, blocks, insert_phi_p);
1992 /* Helper for prepare_names_to_update. Mark all the use sites for
1993 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
1994 prepare_names_to_update. */
1997 prepare_use_sites_for (tree name, bitmap blocks, bool insert_phi_p)
1999 use_operand_p use_p;
2000 imm_use_iterator iter;
2002 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2004 tree stmt = USE_STMT (use_p);
2005 basic_block bb = bb_for_stmt (stmt);
2007 if (TREE_CODE (stmt) == PHI_NODE)
2009 /* Mark this use of NAME interesting for the renamer.
2010 Notice that we explicitly call mark_use_interesting with
2011 INSERT_PHI_P == false.
2013 This is to avoid marking NAME as live-in in this block
2014 BB. If we were to mark NAME live-in to BB, then NAME
2015 would be considered live-in through ALL incoming edges to
2016 BB which is not what we want. Since we are updating the
2017 SSA form for NAME, we don't really know what other names
2018 of NAME are coming in through other edges into BB.
2020 If we considered NAME live-in at BB, then the PHI
2021 placement algorithm may try to insert PHI nodes in blocks
2022 that are not only unnecessary but also the renamer would
2023 not know how to fill in. */
2024 mark_use_interesting (name, stmt, bb, blocks, false);
2026 /* As discussed above, we only want to mark NAME live-in
2027 through the edge corresponding to its slot inside the PHI
2028 argument list. So, we look for the block BB1 where NAME
2029 is flowing through. If BB1 does not contain a definition
2030 of NAME, then consider NAME live-in at BB1. */
2033 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2034 edge e = PHI_ARG_EDGE (stmt, ix);
2035 basic_block bb1 = e->src;
2036 struct def_blocks_d *db = get_def_blocks_for (name);
2038 if (!bitmap_bit_p (db->def_blocks, bb1->index))
2039 set_livein_block (name, bb1);
2044 /* For regular statements, mark this as an interesting use
2046 mark_use_interesting (name, stmt, bb, blocks, insert_phi_p);
2052 /* Helper for prepare_names_to_update. Mark the definition site for
2053 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2054 prepare_names_to_update. */
2057 prepare_def_site_for (tree name, bitmap blocks, bool insert_phi_p)
2062 gcc_assert (names_to_release == NULL
2063 || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2065 stmt = SSA_NAME_DEF_STMT (name);
2066 bb = bb_for_stmt (stmt);
2069 gcc_assert (bb->index < last_basic_block);
2070 mark_def_interesting (name, stmt, bb, blocks, insert_phi_p);
2075 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2076 OLD_SSA_NAMES. Add each definition block to BLOCKS. INSERT_PHI_P
2077 is true if the caller wants to insert PHI nodes for newly created
2081 prepare_names_to_update (bitmap blocks, bool insert_phi_p)
2085 sbitmap_iterator sbi;
2087 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2088 remove it from NEW_SSA_NAMES so that we don't try to visit its
2089 defining basic block (which most likely doesn't exist). Notice
2090 that we cannot do the same with names in OLD_SSA_NAMES because we
2091 want to replace existing instances. */
2092 if (names_to_release)
2093 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2094 RESET_BIT (new_ssa_names, i);
2096 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2097 names may be considered to be live-in on blocks that contain
2098 definitions for their replacements. */
2099 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2100 prepare_def_site_for (ssa_name (i), blocks, insert_phi_p);
2102 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2103 OLD_SSA_NAMES, but we have to ignore its definition site. */
2104 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2106 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2107 prepare_def_site_for (ssa_name (i), blocks, insert_phi_p);
2108 prepare_use_sites_for (ssa_name (i), blocks, insert_phi_p);
2113 /* Dump all the names replaced by NAME to FILE. */
2116 dump_names_replaced_by (FILE *file, tree name)
2122 print_generic_expr (file, name, 0);
2123 fprintf (file, " -> { ");
2125 old_set = names_replaced_by (name);
2126 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2128 print_generic_expr (file, ssa_name (i), 0);
2129 fprintf (file, " ");
2132 fprintf (file, "}\n");
2136 /* Dump all the names replaced by NAME to stderr. */
2139 debug_names_replaced_by (tree name)
2141 dump_names_replaced_by (stderr, name);
2145 /* Dump SSA update information to FILE. */
2148 dump_update_ssa (FILE *file)
2153 if (!need_ssa_update_p ())
2156 if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2158 sbitmap_iterator sbi;
2160 fprintf (file, "\nSSA replacement table\n");
2161 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2162 "O_1, ..., O_j\n\n");
2164 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2165 dump_names_replaced_by (file, ssa_name (i));
2167 fprintf (file, "\n");
2168 fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
2169 update_ssa_stats.num_virtual_mappings);
2170 fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
2171 update_ssa_stats.num_total_mappings
2172 - update_ssa_stats.num_virtual_mappings);
2173 fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
2174 update_ssa_stats.num_total_mappings);
2176 fprintf (file, "\nNumber of virtual symbols: %u\n",
2177 update_ssa_stats.num_virtual_symbols);
2180 if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
2182 fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2183 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2185 print_generic_expr (file, referenced_var (i), 0);
2186 fprintf (file, " ");
2190 if (names_to_release && !bitmap_empty_p (names_to_release))
2192 fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2193 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2195 print_generic_expr (file, ssa_name (i), 0);
2196 fprintf (file, " ");
2200 fprintf (file, "\n\n");
2204 /* Dump SSA update information to stderr. */
2207 debug_update_ssa (void)
2209 dump_update_ssa (stderr);
2213 /* Initialize data structures used for incremental SSA updates. */
2216 init_update_ssa (void)
2218 /* Reserve more space than the current number of names. The calls to
2219 add_new_name_mapping are typically done after creating new SSA
2220 names, so we'll need to reallocate these arrays. */
2221 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2222 sbitmap_zero (old_ssa_names);
2224 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2225 sbitmap_zero (new_ssa_names);
2227 repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2228 need_to_initialize_update_ssa_p = false;
2229 need_to_update_vops_p = false;
2230 syms_to_rename = BITMAP_ALLOC (NULL);
2231 names_to_release = NULL;
2232 memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
2233 update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
2237 /* Deallocate data structures used for incremental SSA updates. */
2240 delete_update_ssa (void)
2245 sbitmap_free (old_ssa_names);
2246 old_ssa_names = NULL;
2248 sbitmap_free (new_ssa_names);
2249 new_ssa_names = NULL;
2251 htab_delete (repl_tbl);
2254 need_to_initialize_update_ssa_p = true;
2255 need_to_update_vops_p = false;
2256 BITMAP_FREE (syms_to_rename);
2257 BITMAP_FREE (update_ssa_stats.virtual_symbols);
2259 if (names_to_release)
2261 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2262 release_ssa_name (ssa_name (i));
2263 BITMAP_FREE (names_to_release);
2266 for (i = 1; i < num_ssa_names; i++)
2268 tree n = ssa_name (i);
2272 free (SSA_NAME_AUX (n));
2273 SSA_NAME_AUX (n) = NULL;
2279 /* Create a new name for OLD_NAME in statement STMT and replace the
2280 operand pointed to by DEF_P with the newly created name. Return
2281 the new name and register the replacement mapping <NEW, OLD> in
2282 update_ssa's tables. */
2285 create_new_def_for (tree old_name, tree stmt, def_operand_p def)
2287 tree new_name = duplicate_ssa_name (old_name, stmt);
2289 SET_DEF (def, new_name);
2291 if (TREE_CODE (stmt) == PHI_NODE)
2295 basic_block bb = bb_for_stmt (stmt);
2297 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2298 FOR_EACH_EDGE (e, ei, bb->preds)
2299 if (e->flags & EDGE_ABNORMAL)
2301 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
2306 register_new_name_mapping (new_name, old_name);
2308 /* For the benefit of passes that will be updating the SSA form on
2309 their own, set the current reaching definition of OLD_NAME to be
2311 set_current_def (old_name, new_name);
2317 /* Register name NEW to be a replacement for name OLD. This function
2318 must be called for every replacement that should be performed by
2322 register_new_name_mapping (tree new, tree old)
2324 if (need_to_initialize_update_ssa_p)
2327 add_new_name_mapping (new, old);
2331 /* Register symbol SYM to be renamed by update_ssa. */
2334 mark_sym_for_renaming (tree sym)
2336 if (need_to_initialize_update_ssa_p)
2339 bitmap_set_bit (syms_to_rename, DECL_UID (sym));
2341 if (!is_gimple_reg (sym))
2342 need_to_update_vops_p = true;
2346 /* Register all the symbols in SET to be renamed by update_ssa. */
2349 mark_set_for_renaming (bitmap set)
2354 if (bitmap_empty_p (set))
2357 if (need_to_initialize_update_ssa_p)
2360 bitmap_ior_into (syms_to_rename, set);
2362 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2363 if (!is_gimple_reg (referenced_var (i)))
2365 need_to_update_vops_p = true;
2371 /* Return true if there is any work to be done by update_ssa. */
2374 need_ssa_update_p (void)
2376 return syms_to_rename || old_ssa_names || new_ssa_names;
2380 /* Return true if name N has been registered in the replacement table. */
2383 name_registered_for_update_p (tree n)
2385 if (!need_ssa_update_p ())
2388 return is_new_name (n)
2390 || symbol_marked_for_renaming (SSA_NAME_VAR (n));
2394 /* Return the set of all the SSA names marked to be replaced. */
2397 ssa_names_to_replace (void)
2401 sbitmap_iterator sbi;
2403 ret = BITMAP_ALLOC (NULL);
2404 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2405 bitmap_set_bit (ret, i);
2411 /* Mark NAME to be released after update_ssa has finished. */
2414 release_ssa_name_after_update_ssa (tree name)
2416 gcc_assert (!need_to_initialize_update_ssa_p);
2418 if (names_to_release == NULL)
2419 names_to_release = BITMAP_ALLOC (NULL);
2421 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2425 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2426 frontier information. BLOCKS is the set of blocks to be updated.
2428 This is slightly different than the regular PHI insertion
2429 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2430 real names (i.e., GIMPLE registers) are inserted:
2432 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2433 nodes inside the region affected by the block that defines VAR
2434 and the blocks that define all its replacements. All these
2435 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2437 First, we compute the entry point to the region (ENTRY). This is
2438 given by the nearest common dominator to all the definition
2439 blocks. When computing the iterated dominance frontier (IDF), any
2440 block not strictly dominated by ENTRY is ignored.
2442 We then call the standard PHI insertion algorithm with the pruned
2445 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2446 names is not pruned. PHI nodes are inserted at every IDF block. */
2449 insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
2450 unsigned update_flags)
2453 struct def_blocks_d *db;
2454 bitmap idf, pruned_idf;
2458 #if defined ENABLE_CHECKING
2459 if (TREE_CODE (var) == SSA_NAME)
2460 gcc_assert (is_old_name (var));
2462 gcc_assert (symbol_marked_for_renaming (var));
2465 /* Get all the definition sites for VAR. */
2466 db = find_def_blocks_for (var);
2468 /* No need to do anything if there were no definitions to VAR. */
2469 if (db == NULL || bitmap_empty_p (db->def_blocks))
2472 /* Compute the initial iterated dominance frontier. */
2473 idf = find_idf (db->def_blocks, dfs);
2474 pruned_idf = BITMAP_ALLOC (NULL);
2476 if (TREE_CODE (var) == SSA_NAME)
2478 if (update_flags == TODO_update_ssa)
2480 /* If doing regular SSA updates for GIMPLE registers, we are
2481 only interested in IDF blocks dominated by the nearest
2482 common dominator of all the definition blocks. */
2483 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
2486 if (entry != ENTRY_BLOCK_PTR)
2487 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
2488 if (BASIC_BLOCK (i) != entry
2489 && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
2490 bitmap_set_bit (pruned_idf, i);
2494 /* Otherwise, do not prune the IDF for VAR. */
2495 gcc_assert (update_flags == TODO_update_ssa_full_phi);
2496 bitmap_copy (pruned_idf, idf);
2501 /* Otherwise, VAR is a symbol that needs to be put into SSA form
2502 for the first time, so we need to compute the full IDF for
2504 bitmap_copy (pruned_idf, idf);
2507 if (!bitmap_empty_p (pruned_idf))
2509 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
2510 are included in the region to be updated. The feeding blocks
2511 are important to guarantee that the PHI arguments are renamed
2513 bitmap_ior_into (blocks, pruned_idf);
2514 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
2518 basic_block bb = BASIC_BLOCK (i);
2520 FOR_EACH_EDGE (e, ei, bb->preds)
2521 if (e->src->index >= 0)
2522 bitmap_set_bit (blocks, e->src->index);
2525 insert_phi_nodes_for (var, pruned_idf, true);
2528 BITMAP_FREE (pruned_idf);
2533 /* Heuristic to determine whether SSA name mappings for virtual names
2534 should be discarded and their symbols rewritten from scratch. When
2535 there is a large number of mappings for virtual names, the
2536 insertion of PHI nodes for the old names in the mappings takes
2537 considerable more time than if we inserted PHI nodes for the
2540 Currently the heuristic takes these stats into account:
2542 - Number of mappings for virtual SSA names.
2543 - Number of distinct virtual symbols involved in those mappings.
2545 If the number of virtual mappings is much larger than the number of
2546 virtual symbols, then it will be faster to compute PHI insertion
2547 spots for the symbols. Even if this involves traversing the whole
2548 CFG, which is what happens when symbols are renamed from scratch. */
2551 switch_virtuals_to_full_rewrite_p (void)
2553 if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
2556 if (update_ssa_stats.num_virtual_mappings
2557 > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
2558 * update_ssa_stats.num_virtual_symbols)
2565 /* Remove every virtual mapping and mark all the affected virtual
2566 symbols for renaming. */
2569 switch_virtuals_to_full_rewrite (void)
2572 sbitmap_iterator sbi;
2576 fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
2577 fprintf (dump_file, "\tNumber of virtual mappings: %7u\n",
2578 update_ssa_stats.num_virtual_mappings);
2579 fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
2580 update_ssa_stats.num_virtual_symbols);
2581 fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
2582 "faster than processing\nthe name mappings.\n\n");
2585 /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
2586 Note that it is not really necessary to remove the mappings from
2587 REPL_TBL, that would only waste time. */
2588 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2589 if (!is_gimple_reg (ssa_name (i)))
2590 RESET_BIT (new_ssa_names, i);
2592 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2593 if (!is_gimple_reg (ssa_name (i)))
2594 RESET_BIT (old_ssa_names, i);
2596 bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols);
2600 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
2601 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
2603 1- The names in OLD_SSA_NAMES dominated by the definitions of
2604 NEW_SSA_NAMES are all re-written to be reached by the
2605 appropriate definition from NEW_SSA_NAMES.
2607 2- If needed, new PHI nodes are added to the iterated dominance
2608 frontier of the blocks where each of NEW_SSA_NAMES are defined.
2610 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
2611 calling register_new_name_mapping for every pair of names that the
2612 caller wants to replace.
2614 The caller identifies the new names that have been inserted and the
2615 names that need to be replaced by calling register_new_name_mapping
2616 for every pair <NEW, OLD>. Note that the function assumes that the
2617 new names have already been inserted in the IL.
2619 For instance, given the following code:
2622 2 x_1 = PHI (0, x_5)
2633 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
2636 2 x_1 = PHI (0, x_5)
2649 We want to replace all the uses of x_1 with the new definitions of
2650 x_10 and x_11. Note that the only uses that should be replaced are
2651 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
2652 *not* be replaced (this is why we cannot just mark symbol 'x' for
2655 Additionally, we may need to insert a PHI node at line 11 because
2656 that is a merge point for x_10 and x_11. So the use of x_1 at line
2657 11 will be replaced with the new PHI node. The insertion of PHI
2658 nodes is optional. They are not strictly necessary to preserve the
2659 SSA form, and depending on what the caller inserted, they may not
2660 even be useful for the optimizers. UPDATE_FLAGS controls various
2661 aspects of how update_ssa operates, see the documentation for
2662 TODO_update_ssa*. */
2665 update_ssa (unsigned update_flags)
2668 basic_block bb, start_bb;
2673 sbitmap_iterator sbi;
2675 if (!need_ssa_update_p ())
2678 timevar_push (TV_TREE_SSA_INCREMENTAL);
2680 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
2681 if (!phis_to_rewrite)
2682 phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
2684 /* Ensure that the dominance information is up-to-date. */
2685 calculate_dominance_info (CDI_DOMINATORS);
2687 /* Only one update flag should be set. */
2688 gcc_assert (update_flags == TODO_update_ssa
2689 || update_flags == TODO_update_ssa_no_phi
2690 || update_flags == TODO_update_ssa_full_phi
2691 || update_flags == TODO_update_ssa_only_virtuals);
2693 /* If we only need to update virtuals, remove all the mappings for
2694 real names before proceeding. The caller is responsible for
2695 having dealt with the name mappings before calling update_ssa. */
2696 if (update_flags == TODO_update_ssa_only_virtuals)
2698 sbitmap_zero (old_ssa_names);
2699 sbitmap_zero (new_ssa_names);
2700 htab_empty (repl_tbl);
2703 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
2707 /* If the caller requested PHI nodes to be added, initialize
2708 live-in information data structures (DEF_BLOCKS). */
2710 /* For each SSA name N, the DEF_BLOCKS table describes where the
2711 name is defined, which blocks have PHI nodes for N, and which
2712 blocks have uses of N (i.e., N is live-on-entry in those
2714 def_blocks = htab_create (num_ssa_names, def_blocks_hash,
2715 def_blocks_eq, def_blocks_free);
2722 blocks = BITMAP_ALLOC (NULL);
2724 /* Clear the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags
2725 for every statement and PHI node. */
2728 block_stmt_iterator si;
2731 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2733 REWRITE_THIS_STMT (phi) = 0;
2734 REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
2737 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2739 tree stmt = bsi_stmt (si);
2740 /* We are going to use the operand cache API, such as
2741 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
2742 cache for each statement should be up-to-date. */
2743 gcc_assert (!stmt_modified_p (stmt));
2744 REWRITE_THIS_STMT (stmt) = 0;
2745 REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
2749 /* Heuristic to avoid massive slow downs when the replacement
2750 mappings include lots of virtual names. */
2751 if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
2752 switch_virtuals_to_full_rewrite ();
2754 /* If there are names defined in the replacement table, prepare
2755 definition and use sites for all the names in NEW_SSA_NAMES and
2757 if (sbitmap_first_set_bit (new_ssa_names) >= 0)
2759 prepare_names_to_update (blocks, insert_phi_p);
2761 /* If all the names in NEW_SSA_NAMES had been marked for
2762 removal, and there are no symbols to rename, then there's
2763 nothing else to do. */
2764 if (sbitmap_first_set_bit (new_ssa_names) < 0
2765 && bitmap_empty_p (syms_to_rename))
2769 /* Next, determine the block at which to start the renaming process. */
2770 if (!bitmap_empty_p (syms_to_rename))
2772 /* If we have to rename some symbols from scratch, we need to
2773 start the process at the root of the CFG. FIXME, it should
2774 be possible to determine the nearest block that had a
2775 definition for each of the symbols that are marked for
2776 updating. For now this seems more work than it's worth. */
2777 start_bb = ENTRY_BLOCK_PTR;
2779 /* Traverse the CFG looking for definitions and uses of symbols
2780 in SYMS_TO_RENAME. Mark interesting blocks and statements
2781 and set local live-in information for the PHI placement
2783 prepare_block_for_update (start_bb, blocks, insert_phi_p);
2787 /* Otherwise, the entry block to the region is the nearest
2788 common dominator for the blocks in BLOCKS. */
2789 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks);
2792 /* If requested, insert PHI nodes at the iterated dominance frontier
2793 of every block, creating new definitions for names in OLD_SSA_NAMES
2794 and for symbols in SYMS_TO_RENAME. */
2799 /* If the caller requested PHI nodes to be added, compute
2800 dominance frontiers. */
2801 dfs = XNEWVEC (bitmap, last_basic_block);
2803 dfs[bb->index] = BITMAP_ALLOC (NULL);
2804 compute_dominance_frontiers (dfs);
2806 if (sbitmap_first_set_bit (old_ssa_names) >= 0)
2808 sbitmap_iterator sbi;
2810 /* insert_update_phi_nodes_for will call add_new_name_mapping
2811 when inserting new PHI nodes, so the set OLD_SSA_NAMES
2812 will grow while we are traversing it (but it will not
2813 gain any new members). Copy OLD_SSA_NAMES to a temporary
2815 sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
2816 sbitmap_copy (tmp, old_ssa_names);
2817 EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
2818 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks,
2823 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2824 insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks,
2828 BITMAP_FREE (dfs[bb->index]);
2831 /* Insertion of PHI nodes may have added blocks to the region.
2832 We need to re-compute START_BB to include the newly added
2834 if (start_bb != ENTRY_BLOCK_PTR)
2835 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks);
2838 /* Reset the current definition for name and symbol before renaming
2840 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2841 set_current_def (ssa_name (i), NULL_TREE);
2843 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2844 set_current_def (referenced_var (i), NULL_TREE);
2846 /* Now start the renaming process at START_BB. */
2847 tmp = sbitmap_alloc (last_basic_block);
2849 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
2852 rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
2856 /* Debugging dumps. */
2862 dump_update_ssa (dump_file);
2864 fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
2868 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
2870 fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
2871 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
2872 c, PERCENT (c, last_basic_block));
2874 if (dump_flags & TDF_DETAILS)
2876 fprintf (dump_file, "Affected blocks: ");
2877 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
2878 fprintf (dump_file, "%u ", i);
2879 fprintf (dump_file, "\n");
2882 fprintf (dump_file, "\n\n");
2885 /* Free allocated memory. */
2887 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2889 tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
2891 VEC_free (tree, heap, phis);
2892 VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
2894 BITMAP_FREE (blocks_with_phis_to_rewrite);
2895 BITMAP_FREE (blocks);
2896 delete_update_ssa ();
2898 timevar_pop (TV_TREE_SSA_INCREMENTAL);