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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
30 #include "langhooks.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-inline.h"
45 #include "tree-dump.h"
46 #include "tree-pass.h"
51 /* This file builds the SSA form for a function as described in:
52 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
53 Computing Static Single Assignment Form and the Control Dependence
54 Graph. ACM Transactions on Programming Languages and Systems,
55 13(4):451-490, October 1991. */
57 /* True if the code is in ssa form. */
60 /* Structure to map a variable VAR to the set of blocks that contain
61 definitions for VAR. */
67 /* Blocks that contain definitions of VAR. Bit I will be set if the
68 Ith block contains a definition of VAR. */
71 /* Blocks that contain a PHI node for VAR. */
74 /* Blocks where VAR is live-on-entry. Similar semantics as
80 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
81 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
82 basic blocks where VAR is defined (assigned a new value). It also
83 contains a bitmap of all the blocks where VAR is live-on-entry
84 (i.e., there is a use of VAR in block B without a preceding
85 definition in B). The live-on-entry information is used when
86 computing PHI pruning heuristics. */
87 static htab_t def_blocks;
89 /* Stack of trees used to restore the global currdefs to its original
90 state after completing rewriting of a block and its dominator
91 children. Its elements have the following properties:
93 - An SSA_NAME indicates that the current definition of the
94 underlying variable should be set to the given SSA_NAME.
96 - A _DECL node indicates that the underlying variable has no
99 - A NULL node is used to mark the last node associated with the
102 - A NULL node at the top entry is used to mark the last node
103 associated with the current block. */
104 static VEC(tree,heap) *block_defs_stack;
106 /* Basic block vectors used in this file ought to be allocated in the
107 heap. We use pointer vector, because ints can be easily passed by
110 DEF_VEC_ALLOC_P(int,heap);
112 /* Set of existing SSA names being replaced by update_ssa. */
113 static sbitmap old_ssa_names;
115 /* Set of new SSA names being added by update_ssa. Note that both
116 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
117 the operations done on them are presence tests. */
118 static sbitmap new_ssa_names;
120 /* Set of virtual SSA names to be updated. Since virtuals are always
121 in FUD chain form, these names are not used as a mapping mechanism
122 like OLD_SSA_NAMES and NEW_SSA_NAMES. Instead, the names in this
123 set are used by ssa_names_to_replace to inform its caller which
124 names are going to be updated. */
125 static bitmap old_virtual_ssa_names;
127 /* Symbols whose SSA form needs to be updated or created for the first
129 static bitmap syms_to_rename;
131 /* Set of SSA names that have been marked to be released after they
132 were registered in the replacement table. They will be finally
133 released after we finish updating the SSA web. */
134 static bitmap names_to_release;
136 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
137 to grow as the callers to register_new_name_mapping will typically
138 create new names on the fly. FIXME. Currently set to 1/3 to avoid
139 frequent reallocations but still need to find a reasonable growth
141 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
143 /* Tuple used to represent replacement mappings. */
150 /* NEW -> OLD_SET replacement table. If we are replacing several
151 existing SSA names O_1, O_2, ..., O_j with a new name N_i,
152 then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */
153 static htab_t repl_tbl;
155 /* true if register_new_name_mapping needs to initialize the data
156 structures needed by update_ssa. */
157 static bool need_to_initialize_update_ssa_p = true;
159 /* true if update_ssa needs to update virtual operands. */
160 static bool need_to_update_vops_p = false;
162 /* true if update_ssa is replacing existing SSA names. */
163 static bool need_to_replace_names_p = false;
165 /* Global data to attach to the main dominator walk structure. */
166 struct mark_def_sites_global_data
168 /* This bitmap contains the variables which are set before they
169 are used in a basic block. */
172 /* Bitmap of names to rename. */
173 sbitmap names_to_rename;
175 /* Set of blocks that mark_def_sites deems interesting for the
176 renamer to process. */
177 sbitmap interesting_blocks;
181 /* Information stored for SSA names. */
184 /* This field indicates whether or not the variable may need PHI nodes.
185 See the enum's definition for more detailed information about the
187 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
189 /* The actual definition of the ssa name. */
194 /* The main entry point to the SSA renamer (rewrite_blocks) may be
195 called several times to do different, but related, tasks.
196 Initially, we need it to rename the whole program into SSA form.
197 At other times, we may need it to only rename into SSA newly
198 exposed symbols. Finally, we can also call it to incrementally fix
199 an already built SSA web. */
201 /* Convert the whole function into SSA form. */
204 /* Incrementally update the SSA web by replacing existing SSA
205 names with new ones. See update_ssa for details. */
210 /* Use TREE_VISITED to keep track of which statements we want to
211 rename. When renaming a subset of the variables, not all
212 statements will be processed. This is decided in mark_def_sites. */
213 #define REWRITE_THIS_STMT(T) TREE_VISITED (T)
215 /* Use the unsigned flag to keep track of which statements we want to
216 visit when marking new definition sites. This is slightly
217 different than REWRITE_THIS_STMT: it's used by update_ssa to
218 distinguish statements that need to have both uses and defs
219 processed from those that only need to have their defs processed.
220 Statements that define new SSA names only need to have their defs
221 registered, but they don't need to have their uses renamed. */
222 #define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
225 /* Get the information associated with NAME. */
227 static inline struct ssa_name_info *
228 get_ssa_name_ann (tree name)
230 if (!SSA_NAME_AUX (name))
231 SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
233 return SSA_NAME_AUX (name);
237 /* Gets phi_state field for VAR. */
239 static inline enum need_phi_state
240 get_phi_state (tree var)
242 if (TREE_CODE (var) == SSA_NAME)
243 return get_ssa_name_ann (var)->need_phi_state;
245 return var_ann (var)->need_phi_state;
249 /* Sets phi_state field for VAR to STATE. */
252 set_phi_state (tree var, enum need_phi_state state)
254 if (TREE_CODE (var) == SSA_NAME)
255 get_ssa_name_ann (var)->need_phi_state = state;
257 var_ann (var)->need_phi_state = state;
261 /* Return the current definition for VAR. */
264 get_current_def (tree var)
266 if (TREE_CODE (var) == SSA_NAME)
267 return get_ssa_name_ann (var)->current_def;
269 return var_ann (var)->current_def;
273 /* Sets current definition of VAR to DEF. */
276 set_current_def (tree var, tree def)
278 if (TREE_CODE (var) == SSA_NAME)
279 get_ssa_name_ann (var)->current_def = def;
281 var_ann (var)->current_def = def;
285 /* Compute global livein information given the set of blockx where
286 an object is locally live at the start of the block (LIVEIN)
287 and the set of blocks where the object is defined (DEF_BLOCKS).
289 Note: This routine augments the existing local livein information
290 to include global livein (i.e., it modifies the underlying bitmap
294 compute_global_livein (bitmap livein, bitmap def_blocks)
296 basic_block bb, *worklist, *tos;
301 = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
303 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
305 *tos++ = BASIC_BLOCK (i);
308 /* Iterate until the worklist is empty. */
309 while (tos != worklist)
314 /* Pull a block off the worklist. */
317 /* For each predecessor block. */
318 FOR_EACH_EDGE (e, ei, bb->preds)
320 basic_block pred = e->src;
321 int pred_index = pred->index;
323 /* None of this is necessary for the entry block. */
324 if (pred != ENTRY_BLOCK_PTR
325 && ! bitmap_bit_p (livein, pred_index)
326 && ! bitmap_bit_p (def_blocks, pred_index))
329 bitmap_set_bit (livein, pred_index);
338 /* Return the set of blocks where variable VAR is defined and the blocks
339 where VAR is live on entry (livein). If no entry is found in
340 DEF_BLOCKS, a new one is created and returned. */
342 static inline struct def_blocks_d *
343 get_def_blocks_for (tree var)
345 struct def_blocks_d db, *db_p;
349 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
352 db_p = xmalloc (sizeof (*db_p));
354 db_p->def_blocks = BITMAP_ALLOC (NULL);
355 db_p->phi_blocks = BITMAP_ALLOC (NULL);
356 db_p->livein_blocks = BITMAP_ALLOC (NULL);
357 *slot = (void *) db_p;
360 db_p = (struct def_blocks_d *) *slot;
366 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
367 VAR is defined by a PHI node. */
370 set_def_block (tree var, basic_block bb, bool phi_p)
372 struct def_blocks_d *db_p;
373 enum need_phi_state state;
375 state = get_phi_state (var);
376 db_p = get_def_blocks_for (var);
378 /* Set the bit corresponding to the block where VAR is defined. */
379 bitmap_set_bit (db_p->def_blocks, bb->index);
381 bitmap_set_bit (db_p->phi_blocks, bb->index);
383 /* Keep track of whether or not we may need to insert PHI nodes.
385 If we are in the UNKNOWN state, then this is the first definition
386 of VAR. Additionally, we have not seen any uses of VAR yet, so
387 we do not need a PHI node for this variable at this time (i.e.,
388 transition to NEED_PHI_STATE_NO).
390 If we are in any other state, then we either have multiple definitions
391 of this variable occurring in different blocks or we saw a use of the
392 variable which was not dominated by the block containing the
393 definition(s). In this case we may need a PHI node, so enter
394 state NEED_PHI_STATE_MAYBE. */
395 if (state == NEED_PHI_STATE_UNKNOWN)
396 set_phi_state (var, NEED_PHI_STATE_NO);
398 set_phi_state (var, NEED_PHI_STATE_MAYBE);
402 /* Mark block BB as having VAR live at the entry to BB. */
405 set_livein_block (tree var, basic_block bb)
407 struct def_blocks_d *db_p;
408 enum need_phi_state state = get_phi_state (var);
410 db_p = get_def_blocks_for (var);
412 /* Set the bit corresponding to the block where VAR is live in. */
413 bitmap_set_bit (db_p->livein_blocks, bb->index);
415 /* Keep track of whether or not we may need to insert PHI nodes.
417 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
418 by the single block containing the definition(s) of this variable. If
419 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
420 NEED_PHI_STATE_MAYBE. */
421 if (state == NEED_PHI_STATE_NO)
423 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
425 if (def_block_index == -1
426 || ! dominated_by_p (CDI_DOMINATORS, bb,
427 BASIC_BLOCK (def_block_index)))
428 set_phi_state (var, NEED_PHI_STATE_MAYBE);
431 set_phi_state (var, NEED_PHI_STATE_MAYBE);
435 /* Return true if symbol SYM is marked for renaming. */
438 symbol_marked_for_renaming (tree sym)
440 gcc_assert (DECL_P (sym));
441 return bitmap_bit_p (syms_to_rename, var_ann (sym)->uid);
445 /* Return true if NAME is in OLD_SSA_NAMES. */
448 is_old_name (tree name)
450 if (!need_to_replace_names_p)
453 return TEST_BIT (old_ssa_names, SSA_NAME_VERSION (name));
457 /* Return true if NAME is in NEW_SSA_NAMES. */
460 is_new_name (tree name)
462 if (!need_to_replace_names_p)
465 return TEST_BIT (new_ssa_names, SSA_NAME_VERSION (name));
469 /* Hashing and equality functions for REPL_TBL. */
472 repl_map_hash (const void *p)
474 return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
478 repl_map_eq (const void *p1, const void *p2)
480 return ((const struct repl_map_d *)p1)->name
481 == ((const struct repl_map_d *)p2)->name;
485 repl_map_free (void *p)
487 BITMAP_FREE (((struct repl_map_d *)p)->set);
492 /* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET). */
495 names_replaced_by (tree new)
501 slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
503 /* If N was not registered in the replacement table, return NULL. */
504 if (slot == NULL || *slot == NULL)
507 return ((struct repl_map_d *) *slot)->set;
511 /* Add OLD to REPL_TBL[NEW].SET. */
514 add_to_repl_tbl (tree new, tree old)
516 struct repl_map_d m, *mp;
520 slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
523 mp = xmalloc (sizeof (*mp));
525 mp->set = BITMAP_ALLOC (NULL);
529 mp = (struct repl_map_d *) *slot;
531 bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
535 /* Add a new mapping NEW -> OLD REPL_TBL. Every entry N_i in REPL_TBL
536 represents the set of names O_1 ... O_j replaced by N_i. This is
537 used by update_ssa and its helpers to introduce new SSA names in an
538 already formed SSA web. */
541 add_new_name_mapping (tree new, tree old)
543 timevar_push (TV_TREE_SSA_INCREMENTAL);
545 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
546 caller may have created new names since the set was created. */
547 if (new_ssa_names->n_bits <= num_ssa_names - 1)
549 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
550 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
551 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
554 /* We don't need to keep replacement mappings for virtual names.
555 Since these names are kept in FUD-chain form, we need to traverse
556 the CFG from ENTRY to repair FUD chains. */
557 if (!is_gimple_reg (new))
561 gcc_assert (!is_gimple_reg (old));
567 sym = SSA_NAME_VAR (old);
568 bitmap_set_bit (old_virtual_ssa_names, SSA_NAME_VERSION (old));
571 mark_sym_for_renaming (sym);
572 need_to_update_vops_p = true;
574 timevar_pop (TV_TREE_SSA_INCREMENTAL);
579 /* Assume that OLD and NEW are different GIMPLE register names. */
580 gcc_assert (new != old && is_gimple_reg (old));
582 /* Update the REPL_TBL table. */
583 add_to_repl_tbl (new, old);
585 /* If OLD had already been registered as a new name, then all the
586 names that OLD replaces should also be replaced by NEW. */
587 if (is_new_name (old))
588 bitmap_ior_into (names_replaced_by (new), names_replaced_by (old));
590 /* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
592 SET_BIT (new_ssa_names, SSA_NAME_VERSION (new));
593 SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
595 /* Indicate that we are going to be replacing existing names. */
596 need_to_replace_names_p = true;
598 timevar_pop (TV_TREE_SSA_INCREMENTAL);
602 /* Call back for walk_dominator_tree used to collect definition sites
603 for every variable in the function. For every statement S in block
606 1- Variables defined by S in DEF_OPS(S) are marked in the bitmap
607 WALK_DATA->GLOBAL_DATA->KILLS.
609 2- If S uses a variable VAR and there is no preceding kill of VAR,
610 then it is marked in marked in the LIVEIN_BLOCKS bitmap
613 This information is used to determine which variables are live
614 across block boundaries to reduce the number of PHI nodes
618 mark_def_sites (struct dom_walk_data *walk_data,
620 block_stmt_iterator bsi)
622 struct mark_def_sites_global_data *gd = walk_data->global_data;
623 bitmap kills = gd->kills;
629 stmt = bsi_stmt (bsi);
630 update_stmt_if_modified (stmt);
632 REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
633 REWRITE_THIS_STMT (stmt) = 0;
635 /* If a variable is used before being set, then the variable is live
636 across a block boundary, so mark it live-on-entry to BB. */
637 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
638 SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL)
640 tree sym = USE_FROM_PTR (use_p);
641 gcc_assert (DECL_P (sym));
642 if (!bitmap_bit_p (kills, var_ann (sym)->uid))
643 set_livein_block (sym, bb);
644 REWRITE_THIS_STMT (stmt) = 1;
647 /* Note that virtual definitions are irrelevant for computing KILLS
648 because a V_MAY_DEF does not constitute a killing definition of the
649 variable. However, the operand of a virtual definitions is a use
650 of the variable, so it may cause the variable to be considered
652 FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
654 tree sym = USE_FROM_PTR (use_p);
655 gcc_assert (DECL_P (sym));
656 set_livein_block (sym, bb);
657 set_def_block (sym, bb, false);
658 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
659 REWRITE_THIS_STMT (stmt) = 1;
662 /* Now process the defs and must-defs made by this statement. */
663 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
665 gcc_assert (DECL_P (def));
666 set_def_block (def, bb, false);
667 bitmap_set_bit (kills, var_ann (def)->uid);
668 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
671 /* If we found the statement interesting then also mark the block BB
673 if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
674 SET_BIT (gd->interesting_blocks, bb->index);
678 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
679 return a bitmap with all the blocks in the iterated dominance
680 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
681 frontier information as returned by compute_dominance_frontiers.
683 The resulting set of blocks are the potential sites where PHI nodes
684 are needed. The caller is responsible from freeing the memory
685 allocated for the return value. */
688 find_idf (bitmap def_blocks, bitmap *dfs)
692 VEC(int,heap) *work_stack;
693 bitmap phi_insertion_points;
695 work_stack = VEC_alloc (int, heap, n_basic_blocks);
696 phi_insertion_points = BITMAP_ALLOC (NULL);
698 /* Seed the work list with all the blocks in DEF_BLOCKS. */
699 EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
700 /* We use VEC_quick_push here for speed. This is safe because we
701 know that the number of definition blocks is no greater than
702 the number of basic blocks, which is the initial capacity of
704 VEC_quick_push (int, work_stack, bb_index);
706 /* Pop a block off the worklist, add every block that appears in
707 the original block's DF that we have not already processed to
708 the worklist. Iterate until the worklist is empty. Blocks
709 which are added to the worklist are potential sites for
711 while (VEC_length (int, work_stack) > 0)
713 bb_index = VEC_pop (int, work_stack);
715 /* Since the registration of NEW -> OLD name mappings is done
716 separately from the call to update_ssa, when updating the SSA
717 form, the basic blocks where new and/or old names are defined
718 may have disappeared by CFG cleanup calls. In this case,
719 we may pull a non-existing block from the work stack. */
720 gcc_assert (bb_index < (unsigned) last_basic_block);
722 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
725 /* Use a safe push because if there is a definition of VAR
726 in every basic block, then WORK_STACK may eventually have
727 more than N_BASIC_BLOCK entries. */
728 VEC_safe_push (int, heap, work_stack, bb_index);
729 bitmap_set_bit (phi_insertion_points, bb_index);
733 VEC_free (int, heap, work_stack);
735 return phi_insertion_points;
739 /* Return the set of blocks where variable VAR is defined and the blocks
740 where VAR is live on entry (livein). Return NULL, if no entry is
741 found in DEF_BLOCKS. */
743 static inline struct def_blocks_d *
744 find_def_blocks_for (tree var)
746 struct def_blocks_d dm;
748 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
752 /* Retrieve or create a default definition for symbol SYM. */
755 get_default_def_for (tree sym)
757 tree ddef = default_def (sym);
759 if (ddef == NULL_TREE)
761 ddef = make_ssa_name (sym, build_empty_stmt ());
762 set_default_def (sym, ddef);
769 /* Insert PHI nodes for variable VAR using the iterated dominance
770 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
771 function assumes that the caller is incrementally updating the SSA
772 form, in which case (1) VAR is assumed to be an SSA name, (2) a new
773 SSA name is created for VAR's symbol, and, (3) all the arguments
774 for the newly created PHI node are set to VAR.
776 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
777 PHI node for VAR. On exit, only the nodes that received a PHI node
778 for VAR will be present in PHI_INSERTION_POINTS. */
781 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
788 struct def_blocks_d *def_map;
790 def_map = find_def_blocks_for (var);
791 gcc_assert (def_map);
793 /* Remove the blocks where we already have PHI nodes for VAR. */
794 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
796 /* Now compute global livein for this variable. Note this modifies
797 def_map->livein_blocks. */
798 compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
800 /* And insert the PHI nodes. */
801 EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
804 bb = BASIC_BLOCK (bb_index);
805 phi = create_phi_node (var, bb);
807 if (TREE_CODE (var) == SSA_NAME)
811 /* FIXME. After removing rewrite_ssa_into_ssa, change this
812 if() to gcc_assert(). */
815 /* If we are rewriting SSA names, create the LHS of the
816 PHI node by duplicating VAR. This is useful in the
817 case of pointers, to also duplicate pointer
818 attributes (alias information, in particular). */
819 tree new_lhs = duplicate_ssa_name (var, phi);
820 SET_PHI_RESULT (phi, new_lhs);
821 add_new_name_mapping (new_lhs, var);
824 /* Add VAR to every argument slot of PHI. We need VAR in
825 every argument so that rewrite_update_phi_arguments knows
826 which name is this PHI node replacing. If VAR is a
827 symbol marked for renaming, this is not necessary, the
828 renamer will use the symbol on the LHS to get its
829 reaching definition. */
830 FOR_EACH_EDGE (e, ei, bb->preds)
831 add_phi_arg (phi, var, e);
834 /* Mark this PHI node as interesting for update_ssa. */
835 REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
836 REWRITE_THIS_STMT (phi) = 1;
841 /* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
842 at the dominance frontier (DFS) of blocks defining VAR. */
845 insert_phi_nodes_1 (tree var, bitmap *dfs)
847 struct def_blocks_d *def_map;
850 def_map = find_def_blocks_for (var);
854 if (get_phi_state (var) != NEED_PHI_STATE_NO)
856 idf = find_idf (def_map->def_blocks, dfs);
857 insert_phi_nodes_for (var, idf, false);
863 /* Insert PHI nodes at the dominance frontier of blocks with variable
864 definitions. DFS contains the dominance frontier information for
865 the flowgraph. PHI nodes will only be inserted at the dominance
866 frontier of definition blocks for variables whose NEED_PHI_STATE
867 annotation is marked as ``maybe'' or ``unknown'' (computed by
868 mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
869 for ssa name rewriting. */
872 insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
876 timevar_push (TV_TREE_INSERT_PHI_NODES);
882 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
884 insert_phi_nodes_1 (ssa_name (i), dfs);
888 for (i = 0; i < num_referenced_vars; i++)
889 insert_phi_nodes_1 (referenced_var (i), dfs);
892 timevar_pop (TV_TREE_INSERT_PHI_NODES);
896 /* Register DEF (an SSA_NAME) to be a new definition for its underlying
897 variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
898 into the stack pointed by BLOCK_DEFS_P. */
901 register_new_def (tree def, VEC(tree,heap) **block_defs_p)
903 tree var = SSA_NAME_VAR (def);
906 /* If this variable is set in a single basic block and all uses are
907 dominated by the set(s) in that single basic block, then there is
908 no reason to record anything for this variable in the block local
909 definition stacks. Doing so just wastes time and memory.
911 This is the same test to prune the set of variables which may
912 need PHI nodes. So we just use that information since it's already
913 computed and available for us to use. */
914 if (get_phi_state (var) == NEED_PHI_STATE_NO)
916 set_current_def (var, def);
920 currdef = get_current_def (var);
922 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
923 later used by the dominator tree callbacks to restore the reaching
924 definitions for all the variables defined in the block after a recursive
925 visit to all its immediately dominated blocks. If there is no current
926 reaching definition, then just record the underlying _DECL node. */
927 VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var);
929 /* Set the current reaching definition for VAR to be DEF. */
930 set_current_def (var, def);
934 /* Perform a depth-first traversal of the dominator tree looking for
935 variables to rename. BB is the block where to start searching.
936 Renaming is a five step process:
938 1- Every definition made by PHI nodes at the start of the blocks is
939 registered as the current definition for the corresponding variable.
941 2- Every statement in BB is rewritten. USE and VUSE operands are
942 rewritten with their corresponding reaching definition. DEF and
943 VDEF targets are registered as new definitions.
945 3- All the PHI nodes in successor blocks of BB are visited. The
946 argument corresponding to BB is replaced with its current reaching
949 4- Recursively rewrite every dominator child block of BB.
951 5- Restore (in reverse order) the current reaching definition for every
952 new definition introduced in this block. This is done so that when
953 we return from the recursive call, all the current reaching
954 definitions are restored to the names that were valid in the
955 dominator parent of BB. */
957 /* SSA Rewriting Step 1. Initialization, create a block local stack
958 of reaching definitions for new SSA names produced in this block
959 (BLOCK_DEFS). Register new definitions for every PHI node in the
963 rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
968 if (dump_file && (dump_flags & TDF_DETAILS))
969 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
971 /* Mark the unwind point for this block. */
972 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
974 /* Step 1. Register new definitions for every PHI node in the block.
975 Conceptually, all the PHI nodes are executed in parallel and each PHI
976 node introduces a new version for the associated variable. */
977 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
979 tree result = PHI_RESULT (phi);
980 register_new_def (result, &block_defs_stack);
985 /* Return the current definition for variable VAR. If none is found,
986 create a new SSA name to act as the zeroth definition for VAR. If VAR
987 is call clobbered and there exists a more recent definition of
988 GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
989 has been clobbered by a function call since its last assignment. */
992 get_reaching_def (tree var)
994 tree currdef_var, avar;
996 /* Lookup the current reaching definition for VAR. */
997 currdef_var = get_current_def (var);
999 /* If there is no reaching definition for VAR, create and register a
1000 default definition for it (if needed). */
1001 if (currdef_var == NULL_TREE)
1003 avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
1004 currdef_var = get_default_def_for (avar);
1005 set_current_def (var, currdef_var);
1008 /* Return the current reaching definition for VAR, or the default
1009 definition, if we had to create one. */
1014 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1015 the block with its immediate reaching definitions. Update the current
1016 definition of a variable when a new real or virtual definition is found. */
1019 rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1020 basic_block bb ATTRIBUTE_UNUSED,
1021 block_stmt_iterator si)
1024 use_operand_p use_p;
1025 def_operand_p def_p;
1028 stmt = bsi_stmt (si);
1030 /* If mark_def_sites decided that we don't need to rewrite this
1031 statement, ignore it. */
1032 if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1035 if (dump_file && (dump_flags & TDF_DETAILS))
1037 fprintf (dump_file, "Renaming statement ");
1038 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1039 fprintf (dump_file, "\n");
1042 /* Step 1. Rewrite USES and VUSES in the statement. */
1043 if (REWRITE_THIS_STMT (stmt))
1044 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1045 SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
1047 tree var = USE_FROM_PTR (use_p);
1048 gcc_assert (DECL_P (var));
1049 SET_USE (use_p, get_reaching_def (var));
1052 /* Step 2. Register the statement's DEF and VDEF operands. */
1053 if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1054 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1056 tree var = DEF_FROM_PTR (def_p);
1057 gcc_assert (DECL_P (var));
1058 SET_DEF (def_p, make_ssa_name (var, stmt));
1059 register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1064 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1065 PHI nodes. For every PHI node found, add a new argument containing the
1066 current reaching definition for the variable and the edge through which
1067 that definition is reaching the PHI node. */
1070 rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1076 FOR_EACH_EDGE (e, ei, bb->succs)
1080 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1083 currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
1084 add_phi_arg (phi, currdef, e);
1090 /* Called after visiting basic block BB. Restore CURRDEFS to its
1094 rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1095 basic_block bb ATTRIBUTE_UNUSED)
1097 /* Restore CURRDEFS to its original state. */
1098 while (VEC_length (tree, block_defs_stack) > 0)
1100 tree tmp = VEC_pop (tree, block_defs_stack);
1101 tree saved_def, var;
1103 if (tmp == NULL_TREE)
1106 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1107 definition of its underlying variable. If we recorded anything
1108 else, it must have been an _DECL node and its current reaching
1109 definition must have been NULL. */
1110 if (TREE_CODE (tmp) == SSA_NAME)
1113 var = SSA_NAME_VAR (saved_def);
1121 set_current_def (var, saved_def);
1126 /* Dump SSA information to FILE. */
1129 dump_tree_ssa (FILE *file)
1132 const char *funcname
1133 = lang_hooks.decl_printable_name (current_function_decl, 2);
1135 fprintf (file, "SSA information for %s\n\n", funcname);
1139 dump_bb (bb, file, 0);
1141 print_generic_stmt (file, phi_nodes (bb), dump_flags);
1142 fputs ("\n\n", file);
1147 /* Dump SSA information to stderr. */
1150 debug_tree_ssa (void)
1152 dump_tree_ssa (stderr);
1156 /* Dump statistics for the hash table HTAB. */
1159 htab_statistics (FILE *file, htab_t htab)
1161 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1162 (long) htab_size (htab),
1163 (long) htab_elements (htab),
1164 htab_collisions (htab));
1168 /* Dump SSA statistics on FILE. */
1171 dump_tree_ssa_stats (FILE *file)
1173 fprintf (file, "\nHash table statistics:\n");
1175 fprintf (file, " def_blocks: ");
1176 htab_statistics (file, def_blocks);
1178 fprintf (file, "\n");
1182 /* Dump SSA statistics on stderr. */
1185 debug_tree_ssa_stats (void)
1187 dump_tree_ssa_stats (stderr);
1191 /* Hashing and equality functions for DEF_BLOCKS. */
1194 def_blocks_hash (const void *p)
1196 return htab_hash_pointer
1197 ((const void *)((const struct def_blocks_d *)p)->var);
1201 def_blocks_eq (const void *p1, const void *p2)
1203 return ((const struct def_blocks_d *)p1)->var
1204 == ((const struct def_blocks_d *)p2)->var;
1208 /* Free memory allocated by one entry in DEF_BLOCKS. */
1211 def_blocks_free (void *p)
1213 struct def_blocks_d *entry = p;
1214 BITMAP_FREE (entry->def_blocks);
1215 BITMAP_FREE (entry->phi_blocks);
1216 BITMAP_FREE (entry->livein_blocks);
1221 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1224 debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1226 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1228 fprintf (stderr, "VAR: ");
1229 print_generic_expr (stderr, db_p->var, dump_flags);
1230 bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1231 bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1237 /* Dump the DEF_BLOCKS hash table on stderr. */
1240 debug_def_blocks (void)
1242 htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1246 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1249 register_new_update_single (tree new_name, tree old_name)
1251 tree currdef = get_current_def (old_name);
1253 /* Push the current reaching definition into *BLOCK_DEFS_P.
1254 This stack is later used by the dominator tree callbacks to
1255 restore the reaching definitions for all the variables
1256 defined in the block after a recursive visit to all its
1257 immediately dominated blocks. */
1258 VEC_reserve (tree, heap, block_defs_stack, 2);
1259 VEC_quick_push (tree, block_defs_stack, currdef);
1260 VEC_quick_push (tree, block_defs_stack, old_name);
1262 /* Set the current reaching definition for OLD_NAME to be
1264 set_current_def (old_name, new_name);
1268 /* Register NEW_NAME to be the new reaching definition for all the
1269 names in OLD_NAMES. Used by the incremental SSA update routines to
1270 replace old SSA names with new ones. */
1273 register_new_update_set (tree new_name, bitmap old_names)
1278 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1279 register_new_update_single (new_name, ssa_name (i));
1283 /* Initialization of block data structures for the incremental SSA
1284 update pass. Create a block local stack of reaching definitions
1285 for new SSA names produced in this block (BLOCK_DEFS). Register
1286 new definitions for every PHI node in the block. */
1289 rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1295 bool is_abnormal_phi;
1297 if (dump_file && (dump_flags & TDF_DETAILS))
1298 fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
1301 /* Mark the unwind point for this block. */
1302 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1304 /* Mark the LHS if any of the arguments flows through an abnormal
1306 is_abnormal_phi = false;
1307 FOR_EACH_EDGE (e, ei, bb->preds)
1308 if (e->flags & EDGE_ABNORMAL)
1310 is_abnormal_phi = true;
1314 /* If any of the PHI nodes is a replacement for a name in
1315 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
1316 register it as a new definition for its corresponding name. Also
1317 register definitions for names whose underlying symbols are
1318 marked for renaming. */
1319 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1323 if (!REGISTER_DEFS_IN_THIS_STMT (phi))
1326 lhs = PHI_RESULT (phi);
1327 lhs_sym = SSA_NAME_VAR (lhs);
1329 if (symbol_marked_for_renaming (lhs_sym))
1330 register_new_update_single (lhs, lhs_sym);
1333 /* If LHS is a new name, register a new definition for all
1334 the names replaced by LHS. */
1335 if (is_new_name (lhs))
1336 register_new_update_set (lhs, names_replaced_by (lhs));
1338 /* If LHS is an OLD name, register it as a new definition
1340 if (is_old_name (lhs))
1341 register_new_update_single (lhs, lhs);
1344 if (is_abnormal_phi)
1345 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
1350 /* Replace the operand pointed by USE_P with USE's current reaching
1354 replace_use (use_operand_p use_p, tree use)
1356 tree rdef = get_reaching_def (use);
1358 SET_USE (use_p, rdef);
1362 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
1363 the current reaching definition of every name re-written in BB to
1364 the original reaching definition before visiting BB. This
1365 unwinding must be done in the opposite order to what is done in
1366 register_new_update_set. */
1369 rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1370 basic_block bb ATTRIBUTE_UNUSED)
1372 while (VEC_length (tree, block_defs_stack) > 0)
1374 tree var = VEC_pop (tree, block_defs_stack);
1377 /* NULL indicates the unwind stop point for this block (see
1378 rewrite_update_init_block). */
1382 saved_def = VEC_pop (tree, block_defs_stack);
1383 set_current_def (var, saved_def);
1388 /* Update every variable used in the statement pointed-to by SI. The
1389 statement is assumed to be in SSA form already. Names in
1390 OLD_SSA_NAMES used by SI will be updated to their current reaching
1391 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1392 will be registered as a new definition for their corresponding name
1393 in OLD_SSA_NAMES. */
1396 rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1397 basic_block bb ATTRIBUTE_UNUSED,
1398 block_stmt_iterator si)
1402 use_operand_p use_p;
1403 def_operand_p def_p;
1406 stmt = bsi_stmt (si);
1407 ann = stmt_ann (stmt);
1409 /* Only update marked statements. */
1410 if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1413 if (dump_file && (dump_flags & TDF_DETAILS))
1415 fprintf (dump_file, "Updating SSA information for statement ");
1416 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1417 fprintf (dump_file, "\n");
1420 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1421 symbol is marked for renaming. */
1422 if (REWRITE_THIS_STMT (stmt))
1424 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1426 tree use = USE_FROM_PTR (use_p);
1427 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1429 if (symbol_marked_for_renaming (sym))
1430 replace_use (use_p, sym);
1431 else if (is_old_name (use))
1432 replace_use (use_p, use);
1435 if (need_to_update_vops_p)
1436 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1437 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1439 tree use = USE_FROM_PTR (use_p);
1440 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1442 if (symbol_marked_for_renaming (sym))
1443 replace_use (use_p, sym);
1447 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1448 Also register definitions for names whose underlying symbol is
1449 marked for renaming. */
1450 if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1452 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1454 tree def = DEF_FROM_PTR (def_p);
1455 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1457 /* If DEF is a naked symbol that needs renaming, create a
1459 if (symbol_marked_for_renaming (sym))
1463 def = make_ssa_name (def, stmt);
1464 SET_DEF (def_p, def);
1467 register_new_update_single (def, sym);
1471 /* If DEF is a new name, register it as a new definition
1472 for all the names replaced by DEF. */
1473 if (is_new_name (def))
1474 register_new_update_set (def, names_replaced_by (def));
1476 /* If DEF is an old name, register DEF as a new
1477 definition for itself. */
1478 if (is_old_name (def))
1479 register_new_update_single (def, def);
1483 if (need_to_update_vops_p)
1484 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
1486 tree def = DEF_FROM_PTR (def_p);
1487 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1489 if (symbol_marked_for_renaming (sym))
1493 def = make_ssa_name (def, stmt);
1494 SET_DEF (def_p, def);
1497 register_new_update_single (def, sym);
1504 /* Visit all the successor blocks of BB looking for PHI nodes. For
1505 every PHI node found, check if any of its arguments is in
1506 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1507 definition, replace it. */
1510 rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1516 FOR_EACH_EDGE (e, ei, bb->succs)
1520 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1523 use_operand_p arg_p;
1525 /* Skip PHI nodes that are not marked for rewrite. */
1526 if (!REWRITE_THIS_STMT (phi))
1529 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1530 arg = USE_FROM_PTR (arg_p);
1532 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
1535 if (arg == NULL_TREE)
1537 /* When updating a PHI node for a recently introduced
1538 symbol we may find NULL arguments. That's why we
1539 take the symbol from the LHS of the PHI node. */
1540 replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
1544 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
1546 if (symbol_marked_for_renaming (sym))
1547 replace_use (arg_p, sym);
1548 else if (is_old_name (arg))
1549 replace_use (arg_p, arg);
1552 if (e->flags & EDGE_ABNORMAL)
1553 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
1559 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
1562 ENTRY indicates the block where to start. Every block dominated by
1563 ENTRY will be rewritten.
1565 WHAT indicates what actions will be taken by the renamer (see enum
1568 BLOCKS are the set of interesting blocks for the dominator walker
1569 to process. If this set is NULL, then all the nodes dominated
1570 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
1571 are not present in BLOCKS are ignored. */
1574 rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
1576 struct dom_walk_data walk_data;
1578 /* Rewrite all the basic blocks in the program. */
1579 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1581 /* Setup callbacks for the generic dominator tree walker. */
1582 memset (&walk_data, 0, sizeof (walk_data));
1584 walk_data.dom_direction = CDI_DOMINATORS;
1585 walk_data.interesting_blocks = blocks;
1587 if (what == REWRITE_UPDATE)
1588 walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
1590 walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1592 if (what == REWRITE_ALL)
1593 walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1594 else if (what == REWRITE_UPDATE)
1595 walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
1599 if (what == REWRITE_ALL)
1600 walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1601 else if (what == REWRITE_UPDATE)
1602 walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
1606 if (what == REWRITE_ALL)
1607 walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
1608 else if (what == REWRITE_UPDATE)
1609 walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
1613 block_defs_stack = VEC_alloc (tree, heap, 10);
1615 /* Initialize the dominator walker. */
1616 init_walk_dominator_tree (&walk_data);
1618 /* Recursively walk the dominator tree rewriting each statement in
1619 each basic block. */
1620 walk_dominator_tree (&walk_data, entry);
1622 /* Finalize the dominator walker. */
1623 fini_walk_dominator_tree (&walk_data);
1625 /* Debugging dumps. */
1626 if (dump_file && (dump_flags & TDF_STATS))
1628 dump_dfa_stats (dump_file);
1630 dump_tree_ssa_stats (dump_file);
1635 htab_delete (def_blocks);
1639 VEC_free (tree, heap, block_defs_stack);
1641 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1645 /* Block initialization routine for mark_def_sites. Clear the
1646 KILLS bitmap at the start of each block. */
1649 mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
1650 basic_block bb ATTRIBUTE_UNUSED)
1652 struct mark_def_sites_global_data *gd = walk_data->global_data;
1653 bitmap kills = gd->kills;
1654 bitmap_clear (kills);
1658 /* Mark the definition site blocks for each variable, so that we know
1659 where the variable is actually live.
1661 INTERESTING_BLOCKS will be filled in with all the blocks that
1662 should be processed by the renamer. It is assumed to be
1663 initialized and zeroed by the caller. */
1666 mark_def_site_blocks (sbitmap interesting_blocks)
1669 struct dom_walk_data walk_data;
1670 struct mark_def_sites_global_data mark_def_sites_global_data;
1672 /* Allocate memory for the DEF_BLOCKS hash table. */
1673 def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
1674 def_blocks_hash, def_blocks_eq, def_blocks_free);
1676 for (i = 0; i < num_referenced_vars; i++)
1677 set_current_def (referenced_var (i), NULL_TREE);
1679 /* Setup callbacks for the generic dominator tree walker to find and
1680 mark definition sites. */
1681 walk_data.walk_stmts_backward = false;
1682 walk_data.dom_direction = CDI_DOMINATORS;
1683 walk_data.initialize_block_local_data = NULL;
1684 walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
1685 walk_data.before_dom_children_walk_stmts = mark_def_sites;
1686 walk_data.before_dom_children_after_stmts = NULL;
1687 walk_data.after_dom_children_before_stmts = NULL;
1688 walk_data.after_dom_children_walk_stmts = NULL;
1689 walk_data.after_dom_children_after_stmts = NULL;
1690 walk_data.interesting_blocks = NULL;
1692 /* Notice that this bitmap is indexed using variable UIDs, so it must be
1693 large enough to accommodate all the variables referenced in the
1694 function, not just the ones we are renaming. */
1695 mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
1697 /* Create the set of interesting blocks that will be filled by
1699 mark_def_sites_global_data.interesting_blocks = interesting_blocks;
1700 walk_data.global_data = &mark_def_sites_global_data;
1702 /* We do not have any local data. */
1703 walk_data.block_local_data_size = 0;
1705 /* Initialize the dominator walker. */
1706 init_walk_dominator_tree (&walk_data);
1708 /* Recursively walk the dominator tree. */
1709 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1711 /* Finalize the dominator walker. */
1712 fini_walk_dominator_tree (&walk_data);
1714 /* We no longer need this bitmap, clear and free it. */
1715 BITMAP_FREE (mark_def_sites_global_data.kills);
1719 /* Main entry point into the SSA builder. The renaming process
1720 proceeds in four main phases:
1722 1- Compute dominance frontier and immediate dominators, needed to
1723 insert PHI nodes and rename the function in dominator tree
1726 2- Find and mark all the blocks that define variables
1727 (mark_def_site_blocks).
1729 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
1731 4- Rename all the blocks (rewrite_blocks) and statements in the program.
1733 Steps 3 and 5 are done using the dominator tree walker
1734 (walk_dominator_tree). */
1737 rewrite_into_ssa (void)
1741 sbitmap interesting_blocks;
1743 timevar_push (TV_TREE_SSA_OTHER);
1745 /* Initialize operand data structures. */
1746 init_ssa_operands ();
1748 /* Initialize the set of interesting blocks. The callback
1749 mark_def_sites will add to this set those blocks that the renamer
1751 interesting_blocks = sbitmap_alloc (last_basic_block);
1752 sbitmap_zero (interesting_blocks);
1754 /* Initialize dominance frontier. */
1755 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
1757 dfs[bb->index] = BITMAP_ALLOC (NULL);
1759 /* 1- Compute dominance frontiers. */
1760 calculate_dominance_info (CDI_DOMINATORS);
1761 compute_dominance_frontiers (dfs);
1763 /* 2- Find and mark definition sites. */
1764 mark_def_site_blocks (interesting_blocks);
1766 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
1767 insert_phi_nodes (dfs, NULL);
1769 /* 4- Rename all the blocks. */
1770 rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
1772 /* Free allocated memory. */
1774 BITMAP_FREE (dfs[bb->index]);
1776 sbitmap_free (interesting_blocks);
1778 timevar_pop (TV_TREE_SSA_OTHER);
1783 struct tree_opt_pass pass_build_ssa =
1787 rewrite_into_ssa, /* execute */
1790 0, /* static_pass_number */
1792 PROP_cfg | PROP_referenced_vars, /* properties_required */
1793 PROP_ssa, /* properties_provided */
1794 0, /* properties_destroyed */
1795 0, /* todo_flags_start */
1796 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
1801 /* Mark the definition of VAR at STMT and BB as interesting for the
1802 renamer. BLOCKS is the set of blocks that need updating. */
1805 mark_def_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
1808 REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
1809 bitmap_set_bit (blocks, bb->index);
1813 bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
1815 #if defined ENABLE_CHECKING
1816 /* If VAR is a virtual, then it had better be a symbol.
1817 Virtuals are in FUD-chain form, so we are interested in the
1818 definition and use sites of the symbol, not the individual
1820 if (!is_gimple_reg (var))
1821 gcc_assert (DECL_P (var));
1824 set_def_block (var, bb, is_phi_p);
1826 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
1827 site for both itself and all the old names replaced by it. */
1828 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
1832 bitmap set = names_replaced_by (var);
1834 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1835 set_def_block (ssa_name (i), bb, is_phi_p);
1841 /* Mark the use of VAR at STMT and BB as interesting for the
1842 renamer. INSERT_PHI_P is true if we are going to insert new PHI
1843 nodes. BLOCKS is the set of blocks that need updating. */
1846 mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
1849 REWRITE_THIS_STMT (stmt) = 1;
1850 bitmap_set_bit (blocks, bb->index);
1852 /* If VAR has not been defined in BB, then it is live-on-entry
1853 to BB. Note that we cannot just use the block holding VAR's
1854 definition because if VAR is one of the names in OLD_SSA_NAMES,
1855 it will have several definitions (itself and all the names that
1859 struct def_blocks_d *db_p;
1861 #if defined ENABLE_CHECKING
1862 /* If VAR is a virtual, then it had better be a symbol.
1863 Virtuals are in FUD-chain form, so we are interested in the
1864 definition and use sites of the symbol, not the individual
1866 if (!is_gimple_reg (var))
1867 gcc_assert (DECL_P (var));
1870 db_p = get_def_blocks_for (var);
1871 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
1872 set_livein_block (var, bb);
1877 /* If any of the arguments of PHI is in OLD_SSA_NAMES, mark PHI to
1878 be rewritten. BB is the block where PHI resides, BLOCKS is the
1879 region to be renamed and INSERT_PHI_P is true if the updating
1880 process should insert new PHI nodes. */
1883 prepare_phi_args_for_update (tree phi, basic_block bb, bitmap blocks,
1888 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1890 tree arg = PHI_ARG_DEF (phi, i);
1892 if (TREE_CODE (arg) == SSA_NAME && is_old_name (arg))
1894 /* Mark this use of ARG interesting for the renamer. Notice
1895 that we explicitly call mark_use_interesting with
1896 INSERT_PHI_P == false.
1898 This is to avoid marking ARG as live-in in this block BB.
1899 If we were to mark ARG live-in to BB, then ARG would be
1900 considered live-in through ALL incoming edges to BB which
1901 is not what we want. Since we are updating the SSA form
1902 for ARG, we don't really know what other names of ARG are
1903 coming in through other edges into BB.
1905 If we considered ARG live-in at BB, then the PHI
1906 placement algorithm may try to insert PHI nodes in blocks
1907 that are not only unnecessary but also the renamer would
1908 not know how to fill in. */
1909 mark_use_interesting (arg, phi, bb, blocks, false);
1911 /* As discussed above, we only want to mark ARG live-in
1912 through the edge corresponding to its slot inside the PHI
1913 argument list. So, we look for the block BB1 where ARG is
1914 flowing through. If BB1 does not contain a definition of
1915 ARG, then consider ARG live-in at BB1. */
1918 edge e = PHI_ARG_EDGE (phi, i);
1919 basic_block bb1 = e->src;
1920 struct def_blocks_d *db = get_def_blocks_for (arg);
1922 if (!bitmap_bit_p (db->def_blocks, bb1->index))
1923 set_livein_block (arg, bb1);
1930 /* Do a dominator walk starting at BB processing statements that
1931 reference variables in OLD_SSA_NAMES and NEW_SSA_NAMES.
1933 1- Mark in BLOCKS the defining block of every name N in
1936 2- Mark in BLOCKS the defining block of every name O in
1939 3- For every statement or PHI node that uses a name O in
1940 OLD_SSA_NAMES. If INSERT_PHI_P is true, mark those uses as live
1941 in the corresponding block. This is later used by the PHI
1942 placement algorithm to make PHI pruning decisions.
1944 If VISIT_DOM_P is true, all the dominator children of BB are also
1947 FIXME. This process is slower than necessary. Once we have
1948 immediate uses merged in, we should be able to just visit the
1949 immediate uses of all the names that we are about to replace,
1950 instead of visiting the whole block. */
1953 prepare_block_for_update (basic_block bb, bool insert_phi_p,
1954 bitmap blocks, bool visit_dom_p)
1957 block_stmt_iterator si;
1960 /* Process PHI nodes marking interesting those that define or use
1961 the names that we are interested in. */
1962 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1964 tree lhs_sym, lhs = PHI_RESULT (phi);
1966 REWRITE_THIS_STMT (phi) = 0;
1967 REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
1969 /* Ignore virtual PHIs if we are not updating virtual operands.
1970 Note that even if NEED_TO_REPLACE_NAMES_P is false, we need
1971 to process real PHIs because we may be rewriting GIMPLE regs
1972 into SSA for the first time. Therefore, we cannot do a
1973 similar shortcut for real PHIs. */
1974 if (!need_to_update_vops_p && !is_gimple_reg (lhs))
1977 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
1979 if (symbol_marked_for_renaming (lhs_sym))
1981 /* If the LHS is a virtual symbol marked for renaming, then
1982 we don't need to scan the argument list. Since virtual
1983 operands are in FUD-chain form, all the arguments of this
1984 PHI must be the same symbol as the LHS. So, we just need
1985 to mark this site as both an interesting use and an
1986 interesting def for the symbol. */
1987 mark_use_interesting (lhs_sym, phi, bb, blocks, insert_phi_p);
1988 mark_def_interesting (lhs_sym, phi, bb, blocks, insert_phi_p);
1990 else if (need_to_replace_names_p)
1992 /* If the LHS is in OLD_SSA_NAMES or NEW_SSA_NAMES, this is
1993 a definition site for it. */
1994 if (is_old_name (lhs) || is_new_name (lhs))
1995 mark_def_interesting (lhs, phi, bb, blocks, insert_phi_p);
1997 prepare_phi_args_for_update (phi, bb, blocks, insert_phi_p);
2001 /* Process the statements. */
2002 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2006 use_operand_p use_p;
2007 def_operand_p def_p;
2009 stmt = bsi_stmt (si);
2011 REWRITE_THIS_STMT (stmt) = 0;
2012 REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
2014 /* Note, even if NEED_TO_REPLACE_NAMES_P is false, we need to
2015 scan real uses and defs, as we may be renaming a GIMPLE
2016 register for the first time. */
2017 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2019 tree use = USE_FROM_PTR (use_p);
2020 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2021 if (symbol_marked_for_renaming (sym) || is_old_name (use))
2022 mark_use_interesting (use, stmt, bb, blocks, insert_phi_p);
2025 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2027 tree def = DEF_FROM_PTR (def_p);
2028 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2030 if (symbol_marked_for_renaming (sym)
2031 || is_new_name (def)
2032 || is_old_name (def))
2033 mark_def_interesting (def, stmt, bb, blocks, insert_phi_p);
2036 /* If we don't need to update virtual operands, continue to the
2038 if (!need_to_update_vops_p)
2041 /* For every interesting N_i = V_MAY_DEF <N_j> and
2042 N_i = V_MUST_DEF <N_j>, mark the statement as interesting.
2043 Notice that N_j may in fact be a naked symbol (if this
2044 statement is the result of basic block duplication). The
2045 rename process will later fill in the appropriate reaching
2046 definition for the symbol. */
2047 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
2049 tree def = DEF_FROM_PTR (def_p);
2050 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2052 if (symbol_marked_for_renaming (sym))
2054 mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p);
2055 mark_def_interesting (sym, stmt, bb, blocks, insert_phi_p);
2059 /* Similarly, for V_USE <N_i>. */
2060 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE)
2062 tree use = USE_FROM_PTR (use_p);
2063 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2065 if (symbol_marked_for_renaming (sym))
2066 mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p);
2070 /* Now visit all the blocks dominated by BB. */
2072 for (son = first_dom_son (CDI_DOMINATORS, bb);
2074 son = next_dom_son (CDI_DOMINATORS, son))
2075 prepare_block_for_update (son, insert_phi_p, blocks, true);
2079 /* Helper for prepare_def_sites. Mark the definition site for NAME as
2080 interesting. BLOCKS and INSERT_PHI_P are as in prepare_def_sites. */
2083 prepare_def_site_for (tree name, bitmap blocks, bool insert_phi_p)
2088 gcc_assert (name && is_gimple_reg (name));
2089 gcc_assert (names_to_release == NULL
2090 || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2092 stmt = SSA_NAME_DEF_STMT (name);
2093 bb = bb_for_stmt (stmt);
2096 gcc_assert (bb->index < last_basic_block);
2097 mark_def_interesting (name, stmt, bb, blocks, insert_phi_p);
2102 /* Mark definition sites of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2103 Add each definition block to BLOCKS. INSERT_PHI_P is true if the
2104 caller wants to insert PHI nodes for newly created names. */
2107 prepare_def_sites (bitmap blocks, bool insert_phi_p)
2112 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2113 remove it from NEW_SSA_NAMES so that we don't try to visit its
2114 defining basic block (which most likely doesn't exist). Notice
2115 that we cannot do the same with names in OLD_SSA_NAMES because we
2116 want to replace existing instances. */
2117 if (names_to_release)
2118 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2119 RESET_BIT (new_ssa_names, i);
2121 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2122 OLD_SSA_NAMES, but we have to ignore its definition site. */
2123 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i,
2124 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2125 prepare_def_site_for (ssa_name (i), blocks, insert_phi_p));
2127 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i,
2128 prepare_def_site_for (ssa_name (i), blocks, insert_phi_p));
2132 /* Dump all the names replaced by NAME to FILE. */
2135 dump_names_replaced_by (FILE *file, tree name)
2141 print_generic_expr (file, name, 0);
2142 fprintf (file, " -> { ");
2144 old_set = names_replaced_by (name);
2145 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2147 print_generic_expr (file, ssa_name (i), 0);
2148 fprintf (file, " ");
2151 fprintf (file, "}\n");
2155 /* Dump all the names replaced by NAME to stderr. */
2158 debug_names_replaced_by (tree name)
2160 dump_names_replaced_by (stderr, name);
2164 /* Dump the SSA name replacement table to FILE. */
2167 dump_repl_tbl (FILE *file)
2172 if (!need_ssa_update_p ())
2175 if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2177 fprintf (file, "\nSSA replacement table\n");
2178 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2179 "O_1, ..., O_j\n\n");
2181 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i,
2182 dump_names_replaced_by (file, ssa_name (i)));
2185 if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
2187 fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2188 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2190 print_generic_expr (file, referenced_var (i), 0);
2191 fprintf (file, " ");
2195 if (old_virtual_ssa_names && !bitmap_empty_p (old_virtual_ssa_names))
2197 fprintf (file, "\n\nVirtual SSA names to be updated\n\n");
2198 EXECUTE_IF_SET_IN_BITMAP (old_virtual_ssa_names, 0, i, bi)
2200 print_generic_expr (file, ssa_name (i), 0);
2201 fprintf (file, " ");
2205 if (names_to_release && !bitmap_empty_p (names_to_release))
2207 fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2208 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2210 print_generic_expr (file, ssa_name (i), 0);
2211 fprintf (file, " ");
2215 fprintf (file, "\n\n");
2219 /* Dump the SSA name replacement table to stderr. */
2222 debug_repl_tbl (void)
2224 dump_repl_tbl (stderr);
2228 /* Initialize data structures used for incremental SSA updates. */
2231 init_update_ssa (void)
2233 /* Reserve 1/3 more than the current number of names. The calls to
2234 add_new_name_mapping are typically done after creating new SSA
2235 names, so we'll need to reallocate these arrays. */
2236 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2237 sbitmap_zero (old_ssa_names);
2239 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2240 sbitmap_zero (new_ssa_names);
2242 repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2243 need_to_initialize_update_ssa_p = false;
2244 need_to_update_vops_p = false;
2245 need_to_replace_names_p = false;
2246 syms_to_rename = BITMAP_ALLOC (NULL);
2247 old_virtual_ssa_names = BITMAP_ALLOC (NULL);
2248 names_to_release = NULL;
2252 /* Deallocate data structures used for incremental SSA updates. */
2255 delete_update_ssa (void)
2260 sbitmap_free (old_ssa_names);
2261 old_ssa_names = NULL;
2263 sbitmap_free (new_ssa_names);
2264 new_ssa_names = NULL;
2266 htab_delete (repl_tbl);
2269 need_to_initialize_update_ssa_p = true;
2270 need_to_update_vops_p = false;
2271 need_to_replace_names_p = false;
2272 BITMAP_FREE (syms_to_rename);
2273 BITMAP_FREE (old_virtual_ssa_names);
2275 if (names_to_release)
2277 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2278 release_ssa_name (ssa_name (i));
2279 BITMAP_FREE (names_to_release);
2282 for (i = 1; i < num_ssa_names; i++)
2284 tree n = ssa_name (i);
2288 free (SSA_NAME_AUX (n));
2289 SSA_NAME_AUX (n) = NULL;
2293 /* Unmark all the names we may have protected from being released in
2294 insert_updated_phi_nodes_for. */
2295 unmark_all_for_rewrite ();
2299 /* Create a new name for OLD_NAME in statement STMT and replace the
2300 operand pointed to by DEF_P with the newly created name. Return
2301 the new name and register the replacement mapping <NEW, OLD> in
2302 update_ssa's tables. */
2305 create_new_def_for (tree old_name, tree stmt, def_operand_p def)
2307 tree new_name = duplicate_ssa_name (old_name, stmt);
2309 SET_DEF (def, new_name);
2311 if (TREE_CODE (stmt) == PHI_NODE)
2315 basic_block bb = bb_for_stmt (stmt);
2317 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2318 FOR_EACH_EDGE (e, ei, bb->preds)
2319 if (e->flags & EDGE_ABNORMAL)
2321 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
2326 register_new_name_mapping (new_name, old_name);
2328 /* For the benefit of passes that will be updating the SSA form on
2329 their own, set the current reaching definition of OLD_NAME to be
2331 set_current_def (old_name, new_name);
2337 /* Register name NEW to be a replacement for name OLD. This function
2338 must be called for every replacement that should be performed by
2342 register_new_name_mapping (tree new, tree old)
2344 if (need_to_initialize_update_ssa_p)
2347 add_new_name_mapping (new, old);
2351 /* Register symbol SYM to be renamed by update_ssa. */
2354 mark_sym_for_renaming (tree sym)
2356 if (need_to_initialize_update_ssa_p)
2359 bitmap_set_bit (syms_to_rename, var_ann (sym)->uid);
2361 if (!is_gimple_reg (sym))
2362 need_to_update_vops_p = true;
2366 /* Register all the symbols in SET to be renamed by update_ssa. */
2369 mark_set_for_renaming (bitmap set)
2374 if (need_to_initialize_update_ssa_p)
2377 bitmap_ior_into (syms_to_rename, set);
2379 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2380 if (!is_gimple_reg (referenced_var (i)))
2382 need_to_update_vops_p = true;
2388 /* Return true if there is any work to be done by update_ssa. */
2391 need_ssa_update_p (void)
2393 return syms_to_rename || old_ssa_names || new_ssa_names;
2397 /* Return true if name N has been registered in the replacement table. */
2400 name_registered_for_update_p (tree n)
2402 if (!need_ssa_update_p ())
2405 return is_new_name (n)
2407 || symbol_marked_for_renaming (SSA_NAME_VAR (n));
2411 /* Return the set of all the SSA names marked to be replaced. */
2414 ssa_names_to_replace (void)
2419 ret = BITMAP_ALLOC (NULL);
2420 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i,
2421 bitmap_set_bit (ret, i));
2423 bitmap_ior_into (ret, old_virtual_ssa_names);
2429 /* Mark NAME to be released after update_ssa has finished. */
2432 release_ssa_name_after_update_ssa (tree name)
2434 gcc_assert (!need_to_initialize_update_ssa_p);
2436 if (names_to_release == NULL)
2437 names_to_release = BITMAP_ALLOC (NULL);
2439 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2443 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2444 frontier information. BLOCKS is the set of blocks to be updated.
2446 This is slightly different than the regular PHI insertion
2447 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2448 real names (i.e., GIMPLE registers) are inserted:
2450 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2451 nodes inside the region affected by the block that defines VAR
2452 and the blocks that define all its replacements. All these
2453 definition blocks have been gathered by prepare_block_for_update
2454 and they are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2456 First, we compute the entry point to the region (ENTRY). This is
2457 given by the nearest common dominator to all the definition
2458 blocks. When computing the iterated dominance frontier (IDF), any
2459 block not strictly dominated by ENTRY is ignored.
2461 We then call the standard PHI insertion algorithm with the pruned
2464 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2465 names is not pruned. PHI nodes are inserted at every IDF block. */
2468 insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
2469 unsigned update_flags)
2472 struct def_blocks_d *db;
2473 bitmap idf, pruned_idf;
2477 #if defined ENABLE_CHECKING
2478 if (TREE_CODE (var) == SSA_NAME)
2479 gcc_assert (is_old_name (var));
2481 gcc_assert (symbol_marked_for_renaming (var));
2484 /* Get all the definition sites for VAR. */
2485 db = find_def_blocks_for (var);
2487 /* No need to do anything if there were no definitions to VAR. */
2488 if (db == NULL || bitmap_empty_p (db->def_blocks))
2491 /* Compute the initial iterated dominance frontier. */
2492 idf = find_idf (db->def_blocks, dfs);
2493 pruned_idf = BITMAP_ALLOC (NULL);
2495 if (TREE_CODE (var) == SSA_NAME)
2497 if (update_flags == TODO_update_ssa)
2499 /* If doing regular SSA updates for GIMPLE registers, we are
2500 only interested in IDF blocks dominated by the nearest
2501 common dominator of all the definition blocks. */
2502 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
2505 if (entry != ENTRY_BLOCK_PTR)
2506 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
2507 if (BASIC_BLOCK (i) != entry
2508 && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
2509 bitmap_set_bit (pruned_idf, i);
2513 /* Otherwise, do not prune the IDF for VAR. */
2514 gcc_assert (update_flags == TODO_update_ssa_full_phi);
2515 bitmap_copy (pruned_idf, idf);
2520 /* Otherwise, VAR is a symbol that needs to be put into SSA form
2521 for the first time, so we need to compute the full IDF for
2523 bitmap_copy (pruned_idf, idf);
2525 /* There may already be PHI nodes for VAR in the flowgraph.
2526 Some of them are no longer necessary. PRUNED_IDF is
2527 the set of blocks that need PHI nodes for VAR and
2528 DB.PHI_BLOCKS is the set of blocks that already contain a PHI
2529 node for VAR. Therefore, the set DB.PHI_BLOCKS - PRUNED_IDF
2530 gives us the set of blocks that contain PHI nodes which are
2531 no longer needed. */
2532 if (!bitmap_empty_p (db->phi_blocks) && !bitmap_empty_p (pruned_idf))
2533 EXECUTE_IF_AND_COMPL_IN_BITMAP (db->phi_blocks, pruned_idf, 0, i, bi)
2538 phi = find_phi_node_for (BASIC_BLOCK (i), var, &prev);
2540 /* Protect the name on PHI's LHS from being released into
2541 the SSA name free list. Since we have still not
2542 updated the SSA form of the program, there may be
2543 instances of PHI's LHS in the IL. */
2544 ver = SSA_NAME_VERSION (PHI_RESULT (phi));
2545 mark_for_rewrite (PHI_RESULT (phi));
2546 release_ssa_name_after_update_ssa (PHI_RESULT (phi));
2547 remove_phi_node (phi, prev);
2551 if (!bitmap_empty_p (pruned_idf))
2553 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
2554 are included in the region to be updated. The feeding blocks
2555 are important to guarantee that the PHI arguments are renamed
2557 bitmap_ior_into (blocks, pruned_idf);
2558 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
2562 basic_block bb = BASIC_BLOCK (i);
2564 FOR_EACH_EDGE (e, ei, bb->preds)
2565 if (e->src->index >= 0)
2566 bitmap_set_bit (blocks, e->src->index);
2569 insert_phi_nodes_for (var, pruned_idf, true);
2572 BITMAP_FREE (pruned_idf);
2577 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
2578 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
2580 1- The names in OLD_SSA_NAMES dominated by the definitions of
2581 NEW_SSA_NAMES are all re-written to be reached by the
2582 appropriate definition from NEW_SSA_NAMES.
2584 2- If needed, new PHI nodes are added to the iterated dominance
2585 frontier of the blocks where each of NEW_SSA_NAMES are defined.
2587 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
2588 calling register_new_name_mapping for every pair of names that the
2589 caller wants to replace.
2591 The caller identifies the new names that have been inserted and the
2592 names that need to be replaced by calling register_new_name_mapping
2593 for every pair <NEW, OLD>. Note that the function assumes that the
2594 new names have already been inserted in the IL.
2596 For instance, given the following code:
2599 2 x_1 = PHI (0, x_5)
2610 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
2613 2 x_1 = PHI (0, x_5)
2626 We want to replace all the uses of x_1 with the new definitions of
2627 x_10 and x_11. Note that the only uses that should be replaced are
2628 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
2629 *not* be replaced (this is why we cannot just mark symbol 'x' for
2632 Additionally, we may need to insert a PHI node at line 11 because
2633 that is a merge point for x_10 and x_11. So the use of x_1 at line
2634 11 will be replaced with the new PHI node. The insertion of PHI
2635 nodes is optional. They are not strictly necessary to preserve the
2636 SSA form, and depending on what the caller inserted, they may not
2637 even be useful for the optimizers. UPDATE_FLAGS controls various
2638 aspects of how update_ssa operates, see the documentation for
2639 TODO_update_ssa*. */
2642 update_ssa (unsigned update_flags)
2644 bitmap *dfs, blocks;
2645 basic_block bb, start_bb;
2651 if (!need_ssa_update_p ())
2654 timevar_push (TV_TREE_SSA_INCREMENTAL);
2656 /* Ensure that the dominance information is up-to-date. */
2657 calculate_dominance_info (CDI_DOMINATORS);
2659 /* Only one update flag should be set. */
2660 gcc_assert (update_flags == TODO_update_ssa
2661 || update_flags == TODO_update_ssa_no_phi
2662 || update_flags == TODO_update_ssa_full_phi
2663 || update_flags == TODO_update_ssa_only_virtuals);
2665 /* If we only need to update virtuals, remove all the mappings for
2666 real names before proceeding. */
2667 if (update_flags == TODO_update_ssa_only_virtuals)
2669 sbitmap_zero (old_ssa_names);
2670 sbitmap_zero (new_ssa_names);
2671 htab_empty (repl_tbl);
2672 need_to_replace_names_p = false;
2675 if (update_flags == TODO_update_ssa
2676 || update_flags == TODO_update_ssa_full_phi
2677 || update_flags == TODO_update_ssa_only_virtuals)
2678 insert_phi_p = true;
2680 insert_phi_p = false;
2684 /* If the caller requested PHI nodes to be added, compute
2685 dominance frontiers and initialize live-in information data
2686 structures (DEF_BLOCKS). */
2687 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
2689 dfs[bb->index] = BITMAP_ALLOC (NULL);
2690 compute_dominance_frontiers (dfs);
2692 /* For each SSA name N, the DEF_BLOCKS table describes where the
2693 name is defined, which blocks have PHI nodes for N, and which
2694 blocks have uses of N (i.e., N is live-on-entry in those
2696 def_blocks = htab_create (num_ssa_names, def_blocks_hash,
2697 def_blocks_eq, def_blocks_free);
2705 blocks = BITMAP_ALLOC (NULL);
2707 /* Determine the CFG region that we are going to update. First add
2708 all the blocks that define each of the names in NEW_SSA_NAMES
2709 and OLD_SSA_NAMES. */
2710 prepare_def_sites (blocks, insert_phi_p);
2712 /* Next, determine the nearest common dominator START_BB for all the
2713 blocks in the region. */
2714 if (!bitmap_empty_p (syms_to_rename) || bitmap_empty_p (blocks))
2716 /* If the region to update is seemingly empty, or if we have to
2717 rename some symbols from scratch, we need to start the
2718 process at the root of the CFG.
2720 FIXME, it should be possible to determine the nearest block
2721 that had a definition for each of the symbols that are marked
2722 for updating. For now this seems more work than it's worth. */
2723 start_bb = ENTRY_BLOCK_PTR;
2726 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks);
2728 /* Traverse all the blocks dominated by START_BB. Mark interesting
2729 blocks and statements and set local live-in information for the
2730 PHI placement heuristics. */
2731 prepare_block_for_update (start_bb, insert_phi_p, blocks, true);
2733 /* If are going to insert PHI nodes, blocks in the dominance
2734 frontier of START_BB may be affected. Note that we don't need to
2735 visit the dominator children of blocks in the dominance frontier
2736 of START_BB. None of the changes inside this region can affect
2737 blocks on the outside. */
2738 if (insert_phi_p && start_bb->index >= 0)
2739 EXECUTE_IF_SET_IN_BITMAP (dfs[start_bb->index], 0, i, bi)
2740 prepare_block_for_update (BASIC_BLOCK (i), insert_phi_p,
2743 /* If requested, insert PHI nodes at the iterated dominance frontier
2744 of every block making new definitions for names in OLD_SSA_NAMES
2745 and for symbols in SYMS_TO_RENAME. */
2748 if (sbitmap_first_set_bit (old_ssa_names) >= 0)
2750 /* insert_updated_phi_nodes_for will call
2751 add_new_name_mapping when inserting new PHI nodes, so the
2752 set OLD_SSA_NAMES will grow while we are traversing it
2753 (but it will not gain any new members). Copy
2754 OLD_SSA_NAMES to a temporary for traversal. */
2755 sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
2756 sbitmap_copy (tmp, old_ssa_names);
2757 EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i,
2758 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks,
2763 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2764 insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks,
2767 /* Insertion of PHI nodes may have added blocks to the region.
2768 We need to re-compute START_BB to include the newly added
2770 if (start_bb != ENTRY_BLOCK_PTR)
2771 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks);
2774 /* Reset the current definition for name and symbol before renaming
2776 if (update_flags == TODO_update_ssa_full_phi)
2778 /* If we are not prunning the IDF for new PHI nodes, set the
2779 current name of every GIMPLE register to NULL. This way, PHI
2780 arguments coming from edges with uninitialized values will be
2781 renamed to use the symbol's default definition. */
2782 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i,
2783 set_current_def (ssa_name (i), NULL_TREE));
2787 /* Otherwise, set each old name to be its current reaching
2789 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i,
2790 set_current_def (ssa_name (i), NULL_TREE));
2793 EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2794 set_current_def (referenced_var (i), NULL_TREE);
2796 /* Now start the renaming process at START_BB. */
2797 tmp = sbitmap_alloc (last_basic_block);
2799 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
2802 rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
2806 /* Debugging dumps. */
2812 dump_repl_tbl (dump_file);
2814 fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
2818 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
2820 fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
2821 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
2822 c, PERCENT (c, last_basic_block));
2824 if (dump_flags & TDF_DETAILS)
2826 fprintf (dump_file, "Affected blocks: ");
2827 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
2828 fprintf (dump_file, "%u ", i);
2829 fprintf (dump_file, "\n");
2832 fprintf (dump_file, "\n\n");
2835 /* Free allocated memory. */
2839 BITMAP_FREE (dfs[bb->index]);
2843 BITMAP_FREE (blocks);
2844 delete_update_ssa ();
2846 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2850 /*---------------------------------------------------------------------------
2851 Functions to fix a program in invalid SSA form into valid SSA
2852 form. The main entry point here is rewrite_ssa_into_ssa.
2853 ---------------------------------------------------------------------------*/
2855 /* Called after visiting basic block BB. Restore CURRDEFS to its
2859 ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2860 basic_block bb ATTRIBUTE_UNUSED)
2863 /* Step 5. Restore the current reaching definition for each variable
2864 referenced in the block (in reverse order). */
2865 while (VEC_length (tree, block_defs_stack) > 0)
2867 tree var = VEC_pop (tree, block_defs_stack);
2873 saved_def = VEC_pop (tree, block_defs_stack);
2874 set_current_def (var, saved_def);
2879 /* Register DEF (an SSA_NAME) to be a new definition for the original
2880 ssa name VAR and push VAR's current reaching definition
2881 into the stack pointed by BLOCK_DEFS_P. */
2884 ssa_register_new_def (tree var, tree def)
2888 /* If this variable is set in a single basic block and all uses are
2889 dominated by the set(s) in that single basic block, then there is
2890 nothing to do. TODO we should not be called at all, and just
2891 keep the original name. */
2892 if (get_phi_state (var) == NEED_PHI_STATE_NO)
2894 set_current_def (var, def);
2898 currdef = get_current_def (var);
2900 /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
2901 later used by the dominator tree callbacks to restore the reaching
2902 definitions for all the variables defined in the block after a recursive
2903 visit to all its immediately dominated blocks. */
2904 VEC_reserve (tree, heap, block_defs_stack, 2);
2905 VEC_quick_push (tree, block_defs_stack, currdef);
2906 VEC_quick_push (tree, block_defs_stack, var);
2908 /* Set the current reaching definition for VAR to be DEF. */
2909 set_current_def (var, def);
2913 /* Same as rewrite_stmt, for rewriting ssa names. */
2916 ssa_rewrite_stmt (struct dom_walk_data *walk_data,
2917 basic_block bb ATTRIBUTE_UNUSED,
2918 block_stmt_iterator si)
2923 use_operand_p use_p;
2924 def_operand_p def_p;
2925 sbitmap names_to_rename = walk_data->global_data;
2927 stmt = bsi_stmt (si);
2928 ann = stmt_ann (stmt);
2930 if (dump_file && (dump_flags & TDF_DETAILS))
2932 fprintf (dump_file, "Renaming statement ");
2933 print_generic_stmt (dump_file, stmt, TDF_SLIM);
2934 fprintf (dump_file, "\n");
2937 /* We have just scanned the code for operands. No statement should
2939 gcc_assert (!ann->modified);
2941 /* Step 1. Rewrite USES and VUSES in the statement. */
2942 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
2944 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
2945 SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
2948 /* Step 2. Register the statement's DEF and VDEF operands. */
2949 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2951 var = DEF_FROM_PTR (def_p);
2953 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
2956 SET_DEF (def_p, duplicate_ssa_name (var, stmt));
2957 ssa_register_new_def (var, DEF_FROM_PTR (def_p));
2962 /* Ditto, for ssa name rewriting. */
2965 ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
2968 sbitmap names_to_rename = walk_data->global_data;
2972 FOR_EACH_EDGE (e, ei, bb->succs)
2976 if (e->dest == EXIT_BLOCK_PTR)
2979 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
2981 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2982 if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
2985 if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
2988 SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
2989 if (e->flags & EDGE_ABNORMAL)
2990 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
2995 /* Ditto, for rewriting ssa names. */
2998 ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
3001 sbitmap names_to_rename = walk_data->global_data;
3006 if (dump_file && (dump_flags & TDF_DETAILS))
3007 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
3009 /* Mark the unwind point for this block. */
3010 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
3012 FOR_EACH_EDGE (e, ei, bb->preds)
3013 if (e->flags & EDGE_ABNORMAL)
3015 abnormal_phi = (e != NULL);
3017 /* Step 1. Register new definitions for every PHI node in the block.
3018 Conceptually, all the PHI nodes are executed in parallel and each PHI
3019 node introduces a new version for the associated variable. */
3020 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3022 tree result = PHI_RESULT (phi);
3024 if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
3026 new_name = duplicate_ssa_name (result, phi);
3027 SET_PHI_RESULT (phi, new_name);
3030 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
3031 ssa_register_new_def (result, new_name);
3037 /* Same as mark_def_sites, but works over SSA names. */
3040 ssa_mark_def_sites (struct dom_walk_data *walk_data,
3042 block_stmt_iterator bsi)
3044 struct mark_def_sites_global_data *gd = walk_data->global_data;
3045 bitmap kills = gd->kills;
3046 size_t uid, def_uid;
3047 tree stmt, use, def;
3050 /* Mark all the blocks that have definitions for each variable in the
3051 names_to_rename bitmap. */
3052 stmt = bsi_stmt (bsi);
3053 update_stmt_if_modified (stmt);
3055 /* If a variable is used before being set, then the variable is live
3056 across a block boundary, so mark it live-on-entry to BB. */
3057 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
3059 uid = SSA_NAME_VERSION (use);
3061 if (TEST_BIT (gd->names_to_rename, uid)
3062 && !bitmap_bit_p (kills, uid))
3063 set_livein_block (use, bb);
3066 /* Now process the definition made by this statement. Mark the
3067 variables in KILLS. */
3068 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
3070 def_uid = SSA_NAME_VERSION (def);
3072 if (TEST_BIT (gd->names_to_rename, def_uid))
3074 set_def_block (def, bb, false);
3075 bitmap_set_bit (kills, def_uid);
3081 /* Block initialization routine for mark_def_sites. Clear the
3082 KILLS bitmap at the start of each block. */
3085 ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
3088 struct mark_def_sites_global_data *gd = walk_data->global_data;
3089 bitmap kills = gd->kills;
3093 bitmap_clear (kills);
3095 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3097 def = PHI_RESULT (phi);
3098 def_uid = SSA_NAME_VERSION (def);
3100 if (!TEST_BIT (gd->names_to_rename, def_uid))
3103 set_def_block (def, bb, true);
3104 bitmap_set_bit (kills, def_uid);
3108 /* Marks ssa names used as arguments of phis at the end of BB. */
3111 ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
3113 struct mark_def_sites_global_data *gd = walk_data->global_data;
3114 bitmap kills = gd->kills;
3120 FOR_EACH_EDGE (e, ei, bb->succs)
3122 if (e->dest == EXIT_BLOCK_PTR)
3125 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
3127 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
3128 if (TREE_CODE (use) != SSA_NAME)
3131 uid = SSA_NAME_VERSION (use);
3133 if (TEST_BIT (gd->names_to_rename, uid)
3134 && !bitmap_bit_p (kills, uid))
3135 set_livein_block (use, bb);
3141 /* The marked ssa names may have more than one definition;
3142 add PHI nodes and rewrite them to fix this. */
3145 rewrite_ssa_into_ssa (void)
3149 struct dom_walk_data walk_data;
3150 struct mark_def_sites_global_data mark_def_sites_global_data;
3152 sbitmap snames_to_rename;
3156 if (!any_marked_for_rewrite_p ())
3158 to_rename = marked_ssa_names ();
3160 timevar_push (TV_TREE_SSA_OTHER);
3162 /* Allocate memory for the DEF_BLOCKS hash table. */
3163 def_blocks = htab_create (num_ssa_names,
3164 def_blocks_hash, def_blocks_eq, def_blocks_free);
3166 /* Initialize dominance frontier and immediate dominator bitmaps.
3167 Also count the number of predecessors for each block. Doing so
3168 can save significant time during PHI insertion for large graphs. */
3169 dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
3171 dfs[bb->index] = BITMAP_ALLOC (NULL);
3173 /* Ensure that the dominance information is OK. */
3174 calculate_dominance_info (CDI_DOMINATORS);
3176 /* Compute dominance frontiers. */
3177 compute_dominance_frontiers (dfs);
3179 /* Setup callbacks for the generic dominator tree walker to find and
3180 mark definition sites. */
3181 walk_data.walk_stmts_backward = false;
3182 walk_data.dom_direction = CDI_DOMINATORS;
3183 walk_data.interesting_blocks = NULL;
3184 walk_data.initialize_block_local_data = NULL;
3185 walk_data.before_dom_children_before_stmts
3186 = ssa_mark_def_sites_initialize_block;
3187 walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
3188 walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses;
3189 walk_data.after_dom_children_before_stmts = NULL;
3190 walk_data.after_dom_children_walk_stmts = NULL;
3191 walk_data.after_dom_children_after_stmts = NULL;
3193 snames_to_rename = sbitmap_alloc (num_ssa_names);
3194 sbitmap_zero (snames_to_rename);
3195 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
3197 SET_BIT (snames_to_rename, i);
3198 set_current_def (ssa_name (i), NULL_TREE);
3201 mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
3202 mark_def_sites_global_data.names_to_rename = snames_to_rename;
3203 walk_data.global_data = &mark_def_sites_global_data;
3205 block_defs_stack = VEC_alloc (tree, heap, 10);
3207 /* We do not have any local data. */
3208 walk_data.block_local_data_size = 0;
3210 /* Initialize the dominator walker. */
3211 init_walk_dominator_tree (&walk_data);
3213 /* Recursively walk the dominator tree. */
3214 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
3216 /* Finalize the dominator walker. */
3217 fini_walk_dominator_tree (&walk_data);
3219 /* We no longer need this bitmap, clear and free it. */
3220 BITMAP_FREE (mark_def_sites_global_data.kills);
3222 /* Insert PHI nodes at dominance frontiers of definition blocks. */
3223 insert_phi_nodes (dfs, to_rename);
3225 /* Rewrite all the basic blocks in the program. */
3226 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
3228 /* Setup callbacks for the generic dominator tree walker. */
3229 walk_data.walk_stmts_backward = false;
3230 walk_data.dom_direction = CDI_DOMINATORS;
3231 walk_data.interesting_blocks = NULL;
3232 walk_data.initialize_block_local_data = NULL;
3233 walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
3234 walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
3235 walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
3236 walk_data.after_dom_children_before_stmts = NULL;
3237 walk_data.after_dom_children_walk_stmts = NULL;
3238 walk_data.after_dom_children_after_stmts = ssa_rewrite_finalize_block;
3239 walk_data.global_data = snames_to_rename;
3240 walk_data.block_local_data_size = 0;
3242 /* Initialize the dominator walker. */
3243 init_walk_dominator_tree (&walk_data);
3245 /* Recursively walk the dominator tree rewriting each statement in
3246 each basic block. */
3247 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
3249 /* Finalize the dominator walker. */
3250 fini_walk_dominator_tree (&walk_data);
3252 unmark_all_for_rewrite ();
3254 EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
3256 /* Free SSA_NAME_AUX. We don't have to zero it because
3257 release_ssa_name will. */
3258 if (SSA_NAME_AUX (ssa_name (i)))
3259 free (SSA_NAME_AUX (ssa_name (i)));
3261 release_ssa_name (ssa_name (i));
3264 sbitmap_free (snames_to_rename);
3266 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
3268 /* Debugging dumps. */
3269 if (dump_file && (dump_flags & TDF_STATS))
3271 dump_dfa_stats (dump_file);
3272 dump_tree_ssa_stats (dump_file);
3275 /* Free allocated memory. */
3277 BITMAP_FREE (dfs[bb->index]);
3280 htab_delete (def_blocks);
3282 #ifdef ENABLE_CHECKING
3283 for (i = 1; i < num_ssa_names; i++)
3285 tree name = ssa_name (i);
3289 gcc_assert (SSA_NAME_AUX (name) == NULL);
3293 BITMAP_FREE (to_rename);
3295 VEC_free (tree, heap, block_defs_stack);
3296 timevar_pop (TV_TREE_SSA_OTHER);