1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "langhooks.h"
30 #include "basic-block.h"
33 #include "tree-pretty-print.h"
34 #include "gimple-pretty-print.h"
36 #include "tree-flow.h"
38 #include "tree-inline.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
49 /* This file builds the SSA form for a function as described in:
50 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
51 Computing Static Single Assignment Form and the Control Dependence
52 Graph. ACM Transactions on Programming Languages and Systems,
53 13(4):451-490, October 1991. */
55 /* Structure to map a variable VAR to the set of blocks that contain
56 definitions for VAR. */
62 /* Blocks that contain definitions of VAR. Bit I will be set if the
63 Ith block contains a definition of VAR. */
66 /* Blocks that contain a PHI node for VAR. */
69 /* Blocks where VAR is live-on-entry. Similar semantics as
75 /* Each entry in DEF_BLOCKS contains an element of type STRUCT
76 DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
77 basic blocks where VAR is defined (assigned a new value). It also
78 contains a bitmap of all the blocks where VAR is live-on-entry
79 (i.e., there is a use of VAR in block B without a preceding
80 definition in B). The live-on-entry information is used when
81 computing PHI pruning heuristics. */
82 static htab_t def_blocks;
84 /* Stack of trees used to restore the global currdefs to its original
85 state after completing rewriting of a block and its dominator
86 children. Its elements have the following properties:
88 - An SSA_NAME (N) indicates that the current definition of the
89 underlying variable should be set to the given SSA_NAME. If the
90 symbol associated with the SSA_NAME is not a GIMPLE register, the
91 next slot in the stack must be a _DECL node (SYM). In this case,
92 the name N in the previous slot is the current reaching
95 - A _DECL node indicates that the underlying variable has no
98 - A NULL node at the top entry is used to mark the last slot
99 associated with the current block. */
100 static VEC(tree,heap) *block_defs_stack;
103 /* Set of existing SSA names being replaced by update_ssa. */
104 static sbitmap old_ssa_names;
106 /* Set of new SSA names being added by update_ssa. Note that both
107 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
108 the operations done on them are presence tests. */
109 static sbitmap new_ssa_names;
111 sbitmap interesting_blocks;
113 /* Set of SSA names that have been marked to be released after they
114 were registered in the replacement table. They will be finally
115 released after we finish updating the SSA web. */
116 static bitmap names_to_release;
118 static VEC(gimple_vec, heap) *phis_to_rewrite;
120 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
121 static bitmap blocks_with_phis_to_rewrite;
123 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
124 to grow as the callers to register_new_name_mapping will typically
125 create new names on the fly. FIXME. Currently set to 1/3 to avoid
126 frequent reallocations but still need to find a reasonable growth
128 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
130 /* Tuple used to represent replacement mappings. */
138 /* NEW -> OLD_SET replacement table. If we are replacing several
139 existing SSA names O_1, O_2, ..., O_j with a new name N_i,
140 then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */
141 static htab_t repl_tbl;
143 /* The function the SSA updating data structures have been initialized for.
144 NULL if they need to be initialized by register_new_name_mapping. */
145 static struct function *update_ssa_initialized_fn = NULL;
147 /* Statistics kept by update_ssa to use in the virtual mapping
148 heuristic. If the number of virtual mappings is beyond certain
149 threshold, the updater will switch from using the mappings into
150 renaming the virtual symbols from scratch. In some cases, the
151 large number of name mappings for virtual names causes significant
152 slowdowns in the PHI insertion code. */
153 struct update_ssa_stats_d
155 unsigned num_virtual_mappings;
156 unsigned num_total_mappings;
157 bitmap virtual_symbols;
158 unsigned num_virtual_symbols;
160 static struct update_ssa_stats_d update_ssa_stats;
162 /* Global data to attach to the main dominator walk structure. */
163 struct mark_def_sites_global_data
165 /* This bitmap contains the variables which are set before they
166 are used in a basic block. */
171 /* Information stored for SSA names. */
174 /* The current reaching definition replacing this SSA name. */
177 /* This field indicates whether or not the variable may need PHI nodes.
178 See the enum's definition for more detailed information about the
180 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
182 /* Age of this record (so that info_for_ssa_name table can be cleared
183 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
184 are assumed to be null. */
188 /* The information associated with names. */
189 typedef struct ssa_name_info *ssa_name_info_p;
190 DEF_VEC_P (ssa_name_info_p);
191 DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
193 static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
194 static unsigned current_info_for_ssa_name_age;
196 /* The set of blocks affected by update_ssa. */
197 static bitmap blocks_to_update;
199 /* The main entry point to the SSA renamer (rewrite_blocks) may be
200 called several times to do different, but related, tasks.
201 Initially, we need it to rename the whole program into SSA form.
202 At other times, we may need it to only rename into SSA newly
203 exposed symbols. Finally, we can also call it to incrementally fix
204 an already built SSA web. */
206 /* Convert the whole function into SSA form. */
209 /* Incrementally update the SSA web by replacing existing SSA
210 names with new ones. See update_ssa for details. */
217 /* Prototypes for debugging functions. */
218 extern void dump_tree_ssa (FILE *);
219 extern void debug_tree_ssa (void);
220 extern void debug_def_blocks (void);
221 extern void dump_tree_ssa_stats (FILE *);
222 extern void debug_tree_ssa_stats (void);
223 extern void dump_update_ssa (FILE *);
224 extern void debug_update_ssa (void);
225 extern void dump_names_replaced_by (FILE *, tree);
226 extern void debug_names_replaced_by (tree);
227 extern void dump_def_blocks (FILE *);
228 extern void debug_def_blocks (void);
229 extern void dump_defs_stack (FILE *, int);
230 extern void debug_defs_stack (int);
231 extern void dump_currdefs (FILE *);
232 extern void debug_currdefs (void);
234 /* Return true if STMT needs to be rewritten. When renaming a subset
235 of the variables, not all statements will be processed. This is
236 decided in mark_def_sites. */
239 rewrite_uses_p (gimple stmt)
241 return gimple_visited_p (stmt);
245 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
248 set_rewrite_uses (gimple stmt, bool rewrite_p)
250 gimple_set_visited (stmt, rewrite_p);
254 /* Return true if the DEFs created by statement STMT should be
255 registered when marking new definition sites. This is slightly
256 different than rewrite_uses_p: it's used by update_ssa to
257 distinguish statements that need to have both uses and defs
258 processed from those that only need to have their defs processed.
259 Statements that define new SSA names only need to have their defs
260 registered, but they don't need to have their uses renamed. */
263 register_defs_p (gimple stmt)
265 return gimple_plf (stmt, GF_PLF_1) != 0;
269 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
272 set_register_defs (gimple stmt, bool register_defs_p)
274 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
278 /* Get the information associated with NAME. */
280 static inline ssa_name_info_p
281 get_ssa_name_ann (tree name)
283 unsigned ver = SSA_NAME_VERSION (name);
284 unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
285 struct ssa_name_info *info;
289 unsigned new_len = num_ssa_names;
291 VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
292 while (len++ < new_len)
294 struct ssa_name_info *info = XCNEW (struct ssa_name_info);
295 info->age = current_info_for_ssa_name_age;
296 VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
300 info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
301 if (info->age < current_info_for_ssa_name_age)
303 info->need_phi_state = NEED_PHI_STATE_UNKNOWN;
304 info->current_def = NULL_TREE;
305 info->age = current_info_for_ssa_name_age;
312 /* Clears info for SSA names. */
315 clear_ssa_name_info (void)
317 current_info_for_ssa_name_age++;
321 /* Get phi_state field for VAR. */
323 static inline enum need_phi_state
324 get_phi_state (tree var)
326 if (TREE_CODE (var) == SSA_NAME)
327 return get_ssa_name_ann (var)->need_phi_state;
329 return var_ann (var)->need_phi_state;
333 /* Sets phi_state field for VAR to STATE. */
336 set_phi_state (tree var, enum need_phi_state state)
338 if (TREE_CODE (var) == SSA_NAME)
339 get_ssa_name_ann (var)->need_phi_state = state;
341 var_ann (var)->need_phi_state = state;
345 /* Return the current definition for VAR. */
348 get_current_def (tree var)
350 if (TREE_CODE (var) == SSA_NAME)
351 return get_ssa_name_ann (var)->current_def;
353 return var_ann (var)->current_def;
357 /* Sets current definition of VAR to DEF. */
360 set_current_def (tree var, tree def)
362 if (TREE_CODE (var) == SSA_NAME)
363 get_ssa_name_ann (var)->current_def = def;
365 var_ann (var)->current_def = def;
369 /* Compute global livein information given the set of blocks where
370 an object is locally live at the start of the block (LIVEIN)
371 and the set of blocks where the object is defined (DEF_BLOCKS).
373 Note: This routine augments the existing local livein information
374 to include global livein (i.e., it modifies the underlying bitmap
378 compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED)
380 basic_block bb, *worklist, *tos;
385 = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
387 EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
388 *tos++ = BASIC_BLOCK (i);
390 /* Iterate until the worklist is empty. */
391 while (tos != worklist)
396 /* Pull a block off the worklist. */
399 /* For each predecessor block. */
400 FOR_EACH_EDGE (e, ei, bb->preds)
402 basic_block pred = e->src;
403 int pred_index = pred->index;
405 /* None of this is necessary for the entry block. */
406 if (pred != ENTRY_BLOCK_PTR
407 && ! bitmap_bit_p (livein, pred_index)
408 && ! bitmap_bit_p (def_blocks, pred_index))
411 bitmap_set_bit (livein, pred_index);
420 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
421 all statements in basic block BB. */
424 initialize_flags_in_bb (basic_block bb)
427 gimple_stmt_iterator gsi;
429 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
431 gimple phi = gsi_stmt (gsi);
432 set_rewrite_uses (phi, false);
433 set_register_defs (phi, false);
436 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
438 stmt = gsi_stmt (gsi);
440 /* We are going to use the operand cache API, such as
441 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
442 cache for each statement should be up-to-date. */
443 gcc_assert (!gimple_modified_p (stmt));
444 set_rewrite_uses (stmt, false);
445 set_register_defs (stmt, false);
449 /* Mark block BB as interesting for update_ssa. */
452 mark_block_for_update (basic_block bb)
454 gcc_assert (blocks_to_update != NULL);
455 if (!bitmap_set_bit (blocks_to_update, bb->index))
457 initialize_flags_in_bb (bb);
460 /* Return the set of blocks where variable VAR is defined and the blocks
461 where VAR is live on entry (livein). If no entry is found in
462 DEF_BLOCKS, a new one is created and returned. */
464 static inline struct def_blocks_d *
465 get_def_blocks_for (tree var)
467 struct def_blocks_d db, *db_p;
471 slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
474 db_p = XNEW (struct def_blocks_d);
476 db_p->def_blocks = BITMAP_ALLOC (NULL);
477 db_p->phi_blocks = BITMAP_ALLOC (NULL);
478 db_p->livein_blocks = BITMAP_ALLOC (NULL);
479 *slot = (void *) db_p;
482 db_p = (struct def_blocks_d *) *slot;
488 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
489 VAR is defined by a PHI node. */
492 set_def_block (tree var, basic_block bb, bool phi_p)
494 struct def_blocks_d *db_p;
495 enum need_phi_state state;
497 state = get_phi_state (var);
498 db_p = get_def_blocks_for (var);
500 /* Set the bit corresponding to the block where VAR is defined. */
501 bitmap_set_bit (db_p->def_blocks, bb->index);
503 bitmap_set_bit (db_p->phi_blocks, bb->index);
505 /* Keep track of whether or not we may need to insert PHI nodes.
507 If we are in the UNKNOWN state, then this is the first definition
508 of VAR. Additionally, we have not seen any uses of VAR yet, so
509 we do not need a PHI node for this variable at this time (i.e.,
510 transition to NEED_PHI_STATE_NO).
512 If we are in any other state, then we either have multiple definitions
513 of this variable occurring in different blocks or we saw a use of the
514 variable which was not dominated by the block containing the
515 definition(s). In this case we may need a PHI node, so enter
516 state NEED_PHI_STATE_MAYBE. */
517 if (state == NEED_PHI_STATE_UNKNOWN)
518 set_phi_state (var, NEED_PHI_STATE_NO);
520 set_phi_state (var, NEED_PHI_STATE_MAYBE);
524 /* Mark block BB as having VAR live at the entry to BB. */
527 set_livein_block (tree var, basic_block bb)
529 struct def_blocks_d *db_p;
530 enum need_phi_state state = get_phi_state (var);
532 db_p = get_def_blocks_for (var);
534 /* Set the bit corresponding to the block where VAR is live in. */
535 bitmap_set_bit (db_p->livein_blocks, bb->index);
537 /* Keep track of whether or not we may need to insert PHI nodes.
539 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
540 by the single block containing the definition(s) of this variable. If
541 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
542 NEED_PHI_STATE_MAYBE. */
543 if (state == NEED_PHI_STATE_NO)
545 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
547 if (def_block_index == -1
548 || ! dominated_by_p (CDI_DOMINATORS, bb,
549 BASIC_BLOCK (def_block_index)))
550 set_phi_state (var, NEED_PHI_STATE_MAYBE);
553 set_phi_state (var, NEED_PHI_STATE_MAYBE);
557 /* Return true if symbol SYM is marked for renaming. */
560 symbol_marked_for_renaming (tree sym)
562 return bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (sym));
566 /* Return true if NAME is in OLD_SSA_NAMES. */
569 is_old_name (tree name)
571 unsigned ver = SSA_NAME_VERSION (name);
574 return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
578 /* Return true if NAME is in NEW_SSA_NAMES. */
581 is_new_name (tree name)
583 unsigned ver = SSA_NAME_VERSION (name);
586 return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
590 /* Hashing and equality functions for REPL_TBL. */
593 repl_map_hash (const void *p)
595 return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
599 repl_map_eq (const void *p1, const void *p2)
601 return ((const struct repl_map_d *)p1)->name
602 == ((const struct repl_map_d *)p2)->name;
606 repl_map_free (void *p)
608 BITMAP_FREE (((struct repl_map_d *)p)->set);
613 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
616 names_replaced_by (tree new_tree)
622 slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
624 /* If N was not registered in the replacement table, return NULL. */
625 if (slot == NULL || *slot == NULL)
628 return ((struct repl_map_d *) *slot)->set;
632 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
635 add_to_repl_tbl (tree new_tree, tree old)
637 struct repl_map_d m, *mp;
641 slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
644 mp = XNEW (struct repl_map_d);
646 mp->set = BITMAP_ALLOC (NULL);
650 mp = (struct repl_map_d *) *slot;
652 bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
656 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
657 represents the set of names O_1 ... O_j replaced by N_i. This is
658 used by update_ssa and its helpers to introduce new SSA names in an
659 already formed SSA web. */
662 add_new_name_mapping (tree new_tree, tree old)
664 timevar_push (TV_TREE_SSA_INCREMENTAL);
666 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
667 gcc_assert (new_tree != old && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
669 /* If this mapping is for virtual names, we will need to update
670 virtual operands. If this is a mapping for .MEM, then we gather
671 the symbols associated with each name. */
672 if (!is_gimple_reg (new_tree))
676 update_ssa_stats.num_virtual_mappings++;
677 update_ssa_stats.num_virtual_symbols++;
679 /* Keep counts of virtual mappings and symbols to use in the
680 virtual mapping heuristic. If we have large numbers of
681 virtual mappings for a relatively low number of symbols, it
682 will make more sense to rename the symbols from scratch.
683 Otherwise, the insertion of PHI nodes for each of the old
684 names in these mappings will be very slow. */
685 sym = SSA_NAME_VAR (new_tree);
686 bitmap_set_bit (update_ssa_stats.virtual_symbols, DECL_UID (sym));
689 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
690 caller may have created new names since the set was created. */
691 if (new_ssa_names->n_bits <= num_ssa_names - 1)
693 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
694 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
695 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
698 /* Update the REPL_TBL table. */
699 add_to_repl_tbl (new_tree, old);
701 /* If OLD had already been registered as a new name, then all the
702 names that OLD replaces should also be replaced by NEW_TREE. */
703 if (is_new_name (old))
704 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
706 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
708 SET_BIT (new_ssa_names, SSA_NAME_VERSION (new_tree));
709 SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
711 /* Update mapping counter to use in the virtual mapping heuristic. */
712 update_ssa_stats.num_total_mappings++;
714 timevar_pop (TV_TREE_SSA_INCREMENTAL);
718 /* Call back for walk_dominator_tree used to collect definition sites
719 for every variable in the function. For every statement S in block
722 1- Variables defined by S in the DEFS of S are marked in the bitmap
725 2- If S uses a variable VAR and there is no preceding kill of VAR,
726 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
728 This information is used to determine which variables are live
729 across block boundaries to reduce the number of PHI nodes
733 mark_def_sites (basic_block bb, gimple stmt, bitmap kills)
739 /* Since this is the first time that we rewrite the program into SSA
740 form, force an operand scan on every statement. */
743 gcc_assert (blocks_to_update == NULL);
744 set_register_defs (stmt, false);
745 set_rewrite_uses (stmt, false);
747 if (is_gimple_debug (stmt))
749 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
751 tree sym = USE_FROM_PTR (use_p);
752 gcc_assert (DECL_P (sym));
753 set_rewrite_uses (stmt, true);
755 if (rewrite_uses_p (stmt))
756 SET_BIT (interesting_blocks, bb->index);
760 /* If a variable is used before being set, then the variable is live
761 across a block boundary, so mark it live-on-entry to BB. */
762 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
764 tree sym = USE_FROM_PTR (use_p);
765 gcc_assert (DECL_P (sym));
766 if (!bitmap_bit_p (kills, DECL_UID (sym)))
767 set_livein_block (sym, bb);
768 set_rewrite_uses (stmt, true);
771 /* Now process the defs. Mark BB as the definition block and add
772 each def to the set of killed symbols. */
773 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
775 gcc_assert (DECL_P (def));
776 set_def_block (def, bb, false);
777 bitmap_set_bit (kills, DECL_UID (def));
778 set_register_defs (stmt, true);
781 /* If we found the statement interesting then also mark the block BB
783 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
784 SET_BIT (interesting_blocks, bb->index);
787 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
788 in the dfs numbering of the dominance tree. */
792 /* Basic block whose index this entry corresponds to. */
795 /* The dfs number of this node. */
799 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
803 cmp_dfsnum (const void *a, const void *b)
805 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
806 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
808 return (int) da->dfs_num - (int) db->dfs_num;
811 /* Among the intervals starting at the N points specified in DEFS, find
812 the one that contains S, and return its bb_index. */
815 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
817 unsigned f = 0, t = n, m;
822 if (defs[m].dfs_num <= s)
828 return defs[f].bb_index;
831 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
832 KILLS is a bitmap of blocks where the value is defined before any use. */
835 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
837 VEC(int, heap) *worklist;
839 unsigned i, b, p, u, top;
841 basic_block def_bb, use_bb;
845 struct dom_dfsnum *defs;
846 unsigned n_defs, adef;
848 if (bitmap_empty_p (uses))
854 /* The phi must dominate a use, or an argument of a live phi. Also, we
855 do not create any phi nodes in def blocks, unless they are also livein. */
856 to_remove = BITMAP_ALLOC (NULL);
857 bitmap_and_compl (to_remove, kills, uses);
858 bitmap_and_compl_into (phis, to_remove);
859 if (bitmap_empty_p (phis))
861 BITMAP_FREE (to_remove);
865 /* We want to remove the unnecessary phi nodes, but we do not want to compute
866 liveness information, as that may be linear in the size of CFG, and if
867 there are lot of different variables to rewrite, this may lead to quadratic
870 Instead, we basically emulate standard dce. We put all uses to worklist,
871 then for each of them find the nearest def that dominates them. If this
872 def is a phi node, we mark it live, and if it was not live before, we
873 add the predecessors of its basic block to the worklist.
875 To quickly locate the nearest def that dominates use, we use dfs numbering
876 of the dominance tree (that is already available in order to speed up
877 queries). For each def, we have the interval given by the dfs number on
878 entry to and on exit from the corresponding subtree in the dominance tree.
879 The nearest dominator for a given use is the smallest of these intervals
880 that contains entry and exit dfs numbers for the basic block with the use.
881 If we store the bounds for all the uses to an array and sort it, we can
882 locate the nearest dominating def in logarithmic time by binary search.*/
883 bitmap_ior (to_remove, kills, phis);
884 n_defs = bitmap_count_bits (to_remove);
885 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
886 defs[0].bb_index = 1;
889 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
891 def_bb = BASIC_BLOCK (i);
892 defs[adef].bb_index = i;
893 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
894 defs[adef + 1].bb_index = i;
895 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
898 BITMAP_FREE (to_remove);
899 gcc_assert (adef == 2 * n_defs + 1);
900 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
901 gcc_assert (defs[0].bb_index == 1);
903 /* Now each DEFS entry contains the number of the basic block to that the
904 dfs number corresponds. Change them to the number of basic block that
905 corresponds to the interval following the dfs number. Also, for the
906 dfs_out numbers, increase the dfs number by one (so that it corresponds
907 to the start of the following interval, not to the end of the current
908 one). We use WORKLIST as a stack. */
909 worklist = VEC_alloc (int, heap, n_defs + 1);
910 VEC_quick_push (int, worklist, 1);
913 for (i = 1; i < adef; i++)
915 b = defs[i].bb_index;
918 /* This is a closing element. Interval corresponding to the top
919 of the stack after removing it follows. */
920 VEC_pop (int, worklist);
921 top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
922 defs[n_defs].bb_index = top;
923 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
927 /* Opening element. Nothing to do, just push it to the stack and move
928 it to the correct position. */
929 defs[n_defs].bb_index = defs[i].bb_index;
930 defs[n_defs].dfs_num = defs[i].dfs_num;
931 VEC_quick_push (int, worklist, b);
935 /* If this interval starts at the same point as the previous one, cancel
937 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
938 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
942 VEC_pop (int, worklist);
943 gcc_assert (VEC_empty (int, worklist));
945 /* Now process the uses. */
946 live_phis = BITMAP_ALLOC (NULL);
947 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
949 VEC_safe_push (int, heap, worklist, i);
952 while (!VEC_empty (int, worklist))
954 b = VEC_pop (int, worklist);
955 if (b == ENTRY_BLOCK)
958 /* If there is a phi node in USE_BB, it is made live. Otherwise,
959 find the def that dominates the immediate dominator of USE_BB
960 (the kill in USE_BB does not dominate the use). */
961 if (bitmap_bit_p (phis, b))
965 use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
966 p = find_dfsnum_interval (defs, n_defs,
967 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
968 if (!bitmap_bit_p (phis, p))
972 /* If the phi node is already live, there is nothing to do. */
973 if (!bitmap_set_bit (live_phis, p))
976 /* Add the new uses to the worklist. */
977 def_bb = BASIC_BLOCK (p);
978 FOR_EACH_EDGE (e, ei, def_bb->preds)
981 if (bitmap_bit_p (uses, u))
984 /* In case there is a kill directly in the use block, do not record
985 the use (this is also necessary for correctness, as we assume that
986 uses dominated by a def directly in their block have been filtered
988 if (bitmap_bit_p (kills, u))
991 bitmap_set_bit (uses, u);
992 VEC_safe_push (int, heap, worklist, u);
996 VEC_free (int, heap, worklist);
997 bitmap_copy (phis, live_phis);
998 BITMAP_FREE (live_phis);
1002 /* Return the set of blocks where variable VAR is defined and the blocks
1003 where VAR is live on entry (livein). Return NULL, if no entry is
1004 found in DEF_BLOCKS. */
1006 static inline struct def_blocks_d *
1007 find_def_blocks_for (tree var)
1009 struct def_blocks_d dm;
1011 return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1015 /* Retrieve or create a default definition for symbol SYM. */
1018 get_default_def_for (tree sym)
1020 tree ddef = gimple_default_def (cfun, sym);
1022 if (ddef == NULL_TREE)
1024 ddef = make_ssa_name (sym, gimple_build_nop ());
1025 set_default_def (sym, ddef);
1032 /* Marks phi node PHI in basic block BB for rewrite. */
1035 mark_phi_for_rewrite (basic_block bb, gimple phi)
1038 unsigned i, idx = bb->index;
1040 if (rewrite_uses_p (phi))
1043 set_rewrite_uses (phi, true);
1045 if (!blocks_with_phis_to_rewrite)
1048 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
1049 VEC_reserve (gimple_vec, heap, phis_to_rewrite, last_basic_block + 1);
1050 for (i = VEC_length (gimple_vec, phis_to_rewrite); i <= idx; i++)
1051 VEC_quick_push (gimple_vec, phis_to_rewrite, NULL);
1053 phis = VEC_index (gimple_vec, phis_to_rewrite, idx);
1055 phis = VEC_alloc (gimple, heap, 10);
1057 VEC_safe_push (gimple, heap, phis, phi);
1058 VEC_replace (gimple_vec, phis_to_rewrite, idx, phis);
1061 /* Insert PHI nodes for variable VAR using the iterated dominance
1062 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
1063 function assumes that the caller is incrementally updating the
1064 existing SSA form, in which case VAR may be an SSA name instead of
1067 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
1068 PHI node for VAR. On exit, only the nodes that received a PHI node
1069 for VAR will be present in PHI_INSERTION_POINTS. */
1072 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
1079 struct def_blocks_d *def_map;
1081 def_map = find_def_blocks_for (var);
1082 gcc_assert (def_map);
1084 /* Remove the blocks where we already have PHI nodes for VAR. */
1085 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1087 /* Remove obviously useless phi nodes. */
1088 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1089 def_map->livein_blocks);
1091 /* And insert the PHI nodes. */
1092 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1094 bb = BASIC_BLOCK (bb_index);
1096 mark_block_for_update (bb);
1100 if (TREE_CODE (var) == SSA_NAME)
1102 /* If we are rewriting SSA names, create the LHS of the PHI
1103 node by duplicating VAR. This is useful in the case of
1104 pointers, to also duplicate pointer attributes (alias
1105 information, in particular). */
1109 gcc_assert (update_p);
1110 phi = create_phi_node (var, bb);
1112 new_lhs = duplicate_ssa_name (var, phi);
1113 gimple_phi_set_result (phi, new_lhs);
1114 add_new_name_mapping (new_lhs, var);
1116 /* Add VAR to every argument slot of PHI. We need VAR in
1117 every argument so that rewrite_update_phi_arguments knows
1118 which name is this PHI node replacing. If VAR is a
1119 symbol marked for renaming, this is not necessary, the
1120 renamer will use the symbol on the LHS to get its
1121 reaching definition. */
1122 FOR_EACH_EDGE (e, ei, bb->preds)
1123 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1129 gcc_assert (DECL_P (var));
1130 phi = create_phi_node (var, bb);
1132 tracked_var = target_for_debug_bind (var);
1135 gimple note = gimple_build_debug_bind (tracked_var,
1138 gimple_stmt_iterator si = gsi_after_labels (bb);
1139 gsi_insert_before (&si, note, GSI_SAME_STMT);
1143 /* Mark this PHI node as interesting for update_ssa. */
1144 set_register_defs (phi, true);
1145 mark_phi_for_rewrite (bb, phi);
1150 /* Insert PHI nodes at the dominance frontier of blocks with variable
1151 definitions. DFS contains the dominance frontier information for
1155 insert_phi_nodes (bitmap_head *dfs)
1157 referenced_var_iterator rvi;
1163 timevar_push (TV_TREE_INSERT_PHI_NODES);
1165 /* Do two stages to avoid code generation differences for UID
1166 differences but no UID ordering differences. */
1168 vars = BITMAP_ALLOC (NULL);
1169 FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
1171 struct def_blocks_d *def_map;
1173 def_map = find_def_blocks_for (var);
1174 if (def_map == NULL)
1177 if (get_phi_state (var) != NEED_PHI_STATE_NO)
1178 bitmap_set_bit (vars, DECL_UID (var));
1181 EXECUTE_IF_SET_IN_BITMAP (vars, 0, uid, bi)
1183 tree var = referenced_var (uid);
1184 struct def_blocks_d *def_map;
1187 def_map = find_def_blocks_for (var);
1188 idf = compute_idf (def_map->def_blocks, dfs);
1189 insert_phi_nodes_for (var, idf, false);
1195 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1199 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1200 register DEF (an SSA_NAME) to be a new definition for SYM. */
1203 register_new_def (tree def, tree sym)
1207 /* If this variable is set in a single basic block and all uses are
1208 dominated by the set(s) in that single basic block, then there is
1209 no reason to record anything for this variable in the block local
1210 definition stacks. Doing so just wastes time and memory.
1212 This is the same test to prune the set of variables which may
1213 need PHI nodes. So we just use that information since it's already
1214 computed and available for us to use. */
1215 if (get_phi_state (sym) == NEED_PHI_STATE_NO)
1217 set_current_def (sym, def);
1221 currdef = get_current_def (sym);
1223 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1224 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1225 in the stack so that we know which symbol is being defined by
1226 this SSA name when we unwind the stack. */
1227 if (currdef && !is_gimple_reg (sym))
1228 VEC_safe_push (tree, heap, block_defs_stack, sym);
1230 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1231 stack is later used by the dominator tree callbacks to restore
1232 the reaching definitions for all the variables defined in the
1233 block after a recursive visit to all its immediately dominated
1234 blocks. If there is no current reaching definition, then just
1235 record the underlying _DECL node. */
1236 VEC_safe_push (tree, heap, block_defs_stack, currdef ? currdef : sym);
1238 /* Set the current reaching definition for SYM to be DEF. */
1239 set_current_def (sym, def);
1243 /* Perform a depth-first traversal of the dominator tree looking for
1244 variables to rename. BB is the block where to start searching.
1245 Renaming is a five step process:
1247 1- Every definition made by PHI nodes at the start of the blocks is
1248 registered as the current definition for the corresponding variable.
1250 2- Every statement in BB is rewritten. USE and VUSE operands are
1251 rewritten with their corresponding reaching definition. DEF and
1252 VDEF targets are registered as new definitions.
1254 3- All the PHI nodes in successor blocks of BB are visited. The
1255 argument corresponding to BB is replaced with its current reaching
1258 4- Recursively rewrite every dominator child block of BB.
1260 5- Restore (in reverse order) the current reaching definition for every
1261 new definition introduced in this block. This is done so that when
1262 we return from the recursive call, all the current reaching
1263 definitions are restored to the names that were valid in the
1264 dominator parent of BB. */
1266 /* Return the current definition for variable VAR. If none is found,
1267 create a new SSA name to act as the zeroth definition for VAR. */
1270 get_reaching_def (tree var)
1274 /* Lookup the current reaching definition for VAR. */
1275 currdef = get_current_def (var);
1277 /* If there is no reaching definition for VAR, create and register a
1278 default definition for it (if needed). */
1279 if (currdef == NULL_TREE)
1281 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1282 currdef = get_default_def_for (sym);
1283 set_current_def (var, currdef);
1286 /* Return the current reaching definition for VAR, or the default
1287 definition, if we had to create one. */
1292 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1295 rewrite_debug_stmt_uses (gimple stmt)
1297 use_operand_p use_p;
1299 bool update = false;
1301 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1303 tree var = USE_FROM_PTR (use_p), def = NULL_TREE;
1304 gcc_assert (DECL_P (var));
1305 if (var_ann (var) == NULL)
1307 if (TREE_CODE (var) == PARM_DECL && single_succ_p (ENTRY_BLOCK_PTR))
1309 gimple_stmt_iterator gsi
1310 = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
1312 /* Search a few source bind stmts at the start of first bb to
1313 see if a DEBUG_EXPR_DECL can't be reused. */
1315 !gsi_end_p (gsi) && lim > 0;
1316 gsi_next (&gsi), lim--)
1318 gimple gstmt = gsi_stmt (gsi);
1319 if (!gimple_debug_source_bind_p (gstmt))
1321 if (gimple_debug_source_bind_get_value (gstmt) == var)
1323 def = gimple_debug_source_bind_get_var (gstmt);
1324 if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1330 /* If not, add a new source bind stmt. */
1331 if (def == NULL_TREE)
1334 def = make_node (DEBUG_EXPR_DECL);
1335 def_temp = gimple_build_debug_source_bind (def, var, NULL);
1336 DECL_ARTIFICIAL (def) = 1;
1337 TREE_TYPE (def) = TREE_TYPE (var);
1338 DECL_MODE (def) = DECL_MODE (var);
1339 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
1340 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1346 def = get_current_def (var);
1349 gimple_debug_bind_reset_value (stmt);
1353 SET_USE (use_p, def);
1359 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1360 the block with its immediate reaching definitions. Update the current
1361 definition of a variable when a new real or virtual definition is found. */
1364 rewrite_stmt (gimple_stmt_iterator si)
1366 use_operand_p use_p;
1367 def_operand_p def_p;
1369 gimple stmt = gsi_stmt (si);
1371 /* If mark_def_sites decided that we don't need to rewrite this
1372 statement, ignore it. */
1373 gcc_assert (blocks_to_update == NULL);
1374 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1377 if (dump_file && (dump_flags & TDF_DETAILS))
1379 fprintf (dump_file, "Renaming statement ");
1380 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1381 fprintf (dump_file, "\n");
1384 /* Step 1. Rewrite USES in the statement. */
1385 if (rewrite_uses_p (stmt))
1387 if (is_gimple_debug (stmt))
1388 rewrite_debug_stmt_uses (stmt);
1390 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1392 tree var = USE_FROM_PTR (use_p);
1393 gcc_assert (DECL_P (var));
1394 SET_USE (use_p, get_reaching_def (var));
1398 /* Step 2. Register the statement's DEF operands. */
1399 if (register_defs_p (stmt))
1400 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1402 tree var = DEF_FROM_PTR (def_p);
1403 tree name = make_ssa_name (var, stmt);
1405 gcc_assert (DECL_P (var));
1406 SET_DEF (def_p, name);
1407 register_new_def (DEF_FROM_PTR (def_p), var);
1409 tracked_var = target_for_debug_bind (var);
1412 gimple note = gimple_build_debug_bind (tracked_var, name, stmt);
1413 gsi_insert_after (&si, note, GSI_SAME_STMT);
1419 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1420 PHI nodes. For every PHI node found, add a new argument containing the
1421 current reaching definition for the variable and the edge through which
1422 that definition is reaching the PHI node. */
1425 rewrite_add_phi_arguments (basic_block bb)
1430 FOR_EACH_EDGE (e, ei, bb->succs)
1433 gimple_stmt_iterator gsi;
1435 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1441 phi = gsi_stmt (gsi);
1442 currdef = get_reaching_def (SSA_NAME_VAR (gimple_phi_result (phi)));
1443 stmt = SSA_NAME_DEF_STMT (currdef);
1444 add_phi_arg (phi, currdef, e, gimple_location (stmt));
1449 /* SSA Rewriting Step 1. Initialization, create a block local stack
1450 of reaching definitions for new SSA names produced in this block
1451 (BLOCK_DEFS). Register new definitions for every PHI node in the
1455 rewrite_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1459 gimple_stmt_iterator gsi;
1461 if (dump_file && (dump_flags & TDF_DETAILS))
1462 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1464 /* Mark the unwind point for this block. */
1465 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1467 /* Step 1. Register new definitions for every PHI node in the block.
1468 Conceptually, all the PHI nodes are executed in parallel and each PHI
1469 node introduces a new version for the associated variable. */
1470 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1474 phi = gsi_stmt (gsi);
1475 result = gimple_phi_result (phi);
1476 gcc_assert (is_gimple_reg (result));
1477 register_new_def (result, SSA_NAME_VAR (result));
1480 /* Step 2. Rewrite every variable used in each statement in the block
1481 with its immediate reaching definitions. Update the current definition
1482 of a variable when a new real or virtual definition is found. */
1483 if (TEST_BIT (interesting_blocks, bb->index))
1484 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1487 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1488 For every PHI node found, add a new argument containing the current
1489 reaching definition for the variable and the edge through which that
1490 definition is reaching the PHI node. */
1491 rewrite_add_phi_arguments (bb);
1496 /* Called after visiting all the statements in basic block BB and all
1497 of its dominator children. Restore CURRDEFS to its original value. */
1500 rewrite_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1501 basic_block bb ATTRIBUTE_UNUSED)
1503 /* Restore CURRDEFS to its original state. */
1504 while (VEC_length (tree, block_defs_stack) > 0)
1506 tree tmp = VEC_pop (tree, block_defs_stack);
1507 tree saved_def, var;
1509 if (tmp == NULL_TREE)
1512 if (TREE_CODE (tmp) == SSA_NAME)
1514 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1515 current definition of its underlying variable. Note that
1516 if the SSA_NAME is not for a GIMPLE register, the symbol
1517 being defined is stored in the next slot in the stack.
1518 This mechanism is needed because an SSA name for a
1519 non-register symbol may be the definition for more than
1520 one symbol (e.g., SFTs, aliased variables, etc). */
1522 var = SSA_NAME_VAR (saved_def);
1523 if (!is_gimple_reg (var))
1524 var = VEC_pop (tree, block_defs_stack);
1528 /* If we recorded anything else, it must have been a _DECL
1529 node and its current reaching definition must have been
1535 set_current_def (var, saved_def);
1540 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1543 dump_decl_set (FILE *file, bitmap set)
1550 fprintf (file, "{ ");
1552 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
1554 tree var = referenced_var_lookup (cfun, i);
1556 print_generic_expr (file, var, 0);
1558 fprintf (file, "D.%u", i);
1559 fprintf (file, " ");
1562 fprintf (file, "}");
1565 fprintf (file, "NIL");
1569 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1572 debug_decl_set (bitmap set)
1574 dump_decl_set (stderr, set);
1575 fprintf (stderr, "\n");
1579 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1580 stack up to a maximum of N levels. If N is -1, the whole stack is
1581 dumped. New levels are created when the dominator tree traversal
1582 used for renaming enters a new sub-tree. */
1585 dump_defs_stack (FILE *file, int n)
1589 fprintf (file, "\n\nRenaming stack");
1591 fprintf (file, " (up to %d levels)", n);
1592 fprintf (file, "\n\n");
1595 fprintf (file, "Level %d (current level)\n", i);
1596 for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
1600 name = VEC_index (tree, block_defs_stack, j);
1601 if (name == NULL_TREE)
1606 fprintf (file, "\nLevel %d\n", i);
1617 var = SSA_NAME_VAR (name);
1618 if (!is_gimple_reg (var))
1621 var = VEC_index (tree, block_defs_stack, j);
1625 fprintf (file, " Previous CURRDEF (");
1626 print_generic_expr (file, var, 0);
1627 fprintf (file, ") = ");
1629 print_generic_expr (file, name, 0);
1631 fprintf (file, "<NIL>");
1632 fprintf (file, "\n");
1637 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1638 stack up to a maximum of N levels. If N is -1, the whole stack is
1639 dumped. New levels are created when the dominator tree traversal
1640 used for renaming enters a new sub-tree. */
1643 debug_defs_stack (int n)
1645 dump_defs_stack (stderr, n);
1649 /* Dump the current reaching definition of every symbol to FILE. */
1652 dump_currdefs (FILE *file)
1654 referenced_var_iterator i;
1657 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1658 FOR_EACH_REFERENCED_VAR (cfun, var, i)
1659 if (SYMS_TO_RENAME (cfun) == NULL
1660 || bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (var)))
1662 fprintf (file, "CURRDEF (");
1663 print_generic_expr (file, var, 0);
1664 fprintf (file, ") = ");
1665 if (get_current_def (var))
1666 print_generic_expr (file, get_current_def (var), 0);
1668 fprintf (file, "<NIL>");
1669 fprintf (file, "\n");
1674 /* Dump the current reaching definition of every symbol to stderr. */
1677 debug_currdefs (void)
1679 dump_currdefs (stderr);
1683 /* Dump SSA information to FILE. */
1686 dump_tree_ssa (FILE *file)
1688 const char *funcname
1689 = lang_hooks.decl_printable_name (current_function_decl, 2);
1691 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1693 dump_def_blocks (file);
1694 dump_defs_stack (file, -1);
1695 dump_currdefs (file);
1696 dump_tree_ssa_stats (file);
1700 /* Dump SSA information to stderr. */
1703 debug_tree_ssa (void)
1705 dump_tree_ssa (stderr);
1709 /* Dump statistics for the hash table HTAB. */
1712 htab_statistics (FILE *file, htab_t htab)
1714 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1715 (long) htab_size (htab),
1716 (long) htab_elements (htab),
1717 htab_collisions (htab));
1721 /* Dump SSA statistics on FILE. */
1724 dump_tree_ssa_stats (FILE *file)
1726 if (def_blocks || repl_tbl)
1727 fprintf (file, "\nHash table statistics:\n");
1731 fprintf (file, " def_blocks: ");
1732 htab_statistics (file, def_blocks);
1737 fprintf (file, " repl_tbl: ");
1738 htab_statistics (file, repl_tbl);
1741 if (def_blocks || repl_tbl)
1742 fprintf (file, "\n");
1746 /* Dump SSA statistics on stderr. */
1749 debug_tree_ssa_stats (void)
1751 dump_tree_ssa_stats (stderr);
1755 /* Hashing and equality functions for DEF_BLOCKS. */
1758 def_blocks_hash (const void *p)
1760 return htab_hash_pointer
1761 ((const void *)((const struct def_blocks_d *)p)->var);
1765 def_blocks_eq (const void *p1, const void *p2)
1767 return ((const struct def_blocks_d *)p1)->var
1768 == ((const struct def_blocks_d *)p2)->var;
1772 /* Free memory allocated by one entry in DEF_BLOCKS. */
1775 def_blocks_free (void *p)
1777 struct def_blocks_d *entry = (struct def_blocks_d *) p;
1778 BITMAP_FREE (entry->def_blocks);
1779 BITMAP_FREE (entry->phi_blocks);
1780 BITMAP_FREE (entry->livein_blocks);
1785 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1788 debug_def_blocks_r (void **slot, void *data)
1790 FILE *file = (FILE *) data;
1791 struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1793 fprintf (file, "VAR: ");
1794 print_generic_expr (file, db_p->var, dump_flags);
1795 bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1796 bitmap_print (file, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}");
1797 bitmap_print (file, db_p->phi_blocks, ", PHI_BLOCKS: { ", "}\n");
1803 /* Dump the DEF_BLOCKS hash table on FILE. */
1806 dump_def_blocks (FILE *file)
1808 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1810 htab_traverse (def_blocks, debug_def_blocks_r, file);
1814 /* Dump the DEF_BLOCKS hash table on stderr. */
1817 debug_def_blocks (void)
1819 dump_def_blocks (stderr);
1823 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1826 register_new_update_single (tree new_name, tree old_name)
1828 tree currdef = get_current_def (old_name);
1830 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1831 This stack is later used by the dominator tree callbacks to
1832 restore the reaching definitions for all the variables
1833 defined in the block after a recursive visit to all its
1834 immediately dominated blocks. */
1835 VEC_reserve (tree, heap, block_defs_stack, 2);
1836 VEC_quick_push (tree, block_defs_stack, currdef);
1837 VEC_quick_push (tree, block_defs_stack, old_name);
1839 /* Set the current reaching definition for OLD_NAME to be
1841 set_current_def (old_name, new_name);
1845 /* Register NEW_NAME to be the new reaching definition for all the
1846 names in OLD_NAMES. Used by the incremental SSA update routines to
1847 replace old SSA names with new ones. */
1850 register_new_update_set (tree new_name, bitmap old_names)
1855 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1856 register_new_update_single (new_name, ssa_name (i));
1861 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1862 it is a symbol marked for renaming, replace it with USE_P's current
1863 reaching definition. */
1866 maybe_replace_use (use_operand_p use_p)
1868 tree rdef = NULL_TREE;
1869 tree use = USE_FROM_PTR (use_p);
1870 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1872 if (symbol_marked_for_renaming (sym))
1873 rdef = get_reaching_def (sym);
1874 else if (is_old_name (use))
1875 rdef = get_reaching_def (use);
1877 if (rdef && rdef != use)
1878 SET_USE (use_p, rdef);
1882 /* Same as maybe_replace_use, but without introducing default stmts,
1883 returning false to indicate a need to do so. */
1886 maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1888 tree rdef = NULL_TREE;
1889 tree use = USE_FROM_PTR (use_p);
1890 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1892 if (symbol_marked_for_renaming (sym))
1893 rdef = get_current_def (sym);
1894 else if (is_old_name (use))
1896 rdef = get_current_def (use);
1897 /* We can't assume that, if there's no current definition, the
1898 default one should be used. It could be the case that we've
1899 rearranged blocks so that the earlier definition no longer
1900 dominates the use. */
1901 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1907 if (rdef && rdef != use)
1908 SET_USE (use_p, rdef);
1910 return rdef != NULL_TREE;
1914 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1915 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1916 register it as the current definition for the names replaced by
1920 maybe_register_def (def_operand_p def_p, gimple stmt,
1921 gimple_stmt_iterator gsi)
1923 tree def = DEF_FROM_PTR (def_p);
1924 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1926 /* If DEF is a naked symbol that needs renaming, create a new
1928 if (symbol_marked_for_renaming (sym))
1934 def = make_ssa_name (def, stmt);
1935 SET_DEF (def_p, def);
1937 tracked_var = target_for_debug_bind (sym);
1940 gimple note = gimple_build_debug_bind (tracked_var, def, stmt);
1941 /* If stmt ends the bb, insert the debug stmt on the single
1942 non-EH edge from the stmt. */
1943 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1945 basic_block bb = gsi_bb (gsi);
1948 FOR_EACH_EDGE (e, ei, bb->succs)
1949 if (!(e->flags & EDGE_EH))
1954 /* If there are other predecessors to ef->dest, then
1955 there must be PHI nodes for the modified
1956 variable, and therefore there will be debug bind
1957 stmts after the PHI nodes. The debug bind notes
1958 we'd insert would force the creation of a new
1959 block (diverging codegen) and be redundant with
1960 the post-PHI bind stmts, so don't add them.
1962 As for the exit edge, there wouldn't be redundant
1963 bind stmts, but there wouldn't be a PC to bind
1964 them to either, so avoid diverging the CFG. */
1965 if (ef && single_pred_p (ef->dest)
1966 && ef->dest != EXIT_BLOCK_PTR)
1968 /* If there were PHI nodes in the node, we'd
1969 have to make sure the value we're binding
1970 doesn't need rewriting. But there shouldn't
1971 be PHI nodes in a single-predecessor block,
1972 so we just add the note. */
1973 gsi_insert_on_edge_immediate (ef, note);
1977 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1981 register_new_update_single (def, sym);
1985 /* If DEF is a new name, register it as a new definition
1986 for all the names replaced by DEF. */
1987 if (is_new_name (def))
1988 register_new_update_set (def, names_replaced_by (def));
1990 /* If DEF is an old name, register DEF as a new
1991 definition for itself. */
1992 if (is_old_name (def))
1993 register_new_update_single (def, def);
1998 /* Update every variable used in the statement pointed-to by SI. The
1999 statement is assumed to be in SSA form already. Names in
2000 OLD_SSA_NAMES used by SI will be updated to their current reaching
2001 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
2002 will be registered as a new definition for their corresponding name
2003 in OLD_SSA_NAMES. */
2006 rewrite_update_stmt (gimple stmt, gimple_stmt_iterator gsi)
2008 use_operand_p use_p;
2009 def_operand_p def_p;
2012 /* Only update marked statements. */
2013 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
2016 if (dump_file && (dump_flags & TDF_DETAILS))
2018 fprintf (dump_file, "Updating SSA information for statement ");
2019 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2020 fprintf (dump_file, "\n");
2023 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2024 symbol is marked for renaming. */
2025 if (rewrite_uses_p (stmt))
2027 if (is_gimple_debug (stmt))
2029 bool failed = false;
2031 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2032 if (!maybe_replace_use_in_debug_stmt (use_p))
2040 /* DOM sometimes threads jumps in such a way that a
2041 debug stmt ends up referencing a SSA variable that no
2042 longer dominates the debug stmt, but such that all
2043 incoming definitions refer to the same definition in
2044 an earlier dominator. We could try to recover that
2045 definition somehow, but this will have to do for now.
2047 Introducing a default definition, which is what
2048 maybe_replace_use() would do in such cases, may
2049 modify code generation, for the otherwise-unused
2050 default definition would never go away, modifying SSA
2051 version numbers all over. */
2052 gimple_debug_bind_reset_value (stmt);
2058 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2059 maybe_replace_use (use_p);
2063 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2064 Also register definitions for names whose underlying symbol is
2065 marked for renaming. */
2066 if (register_defs_p (stmt))
2067 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2068 maybe_register_def (def_p, stmt, gsi);
2072 /* Visit all the successor blocks of BB looking for PHI nodes. For
2073 every PHI node found, check if any of its arguments is in
2074 OLD_SSA_NAMES. If so, and if the argument has a current reaching
2075 definition, replace it. */
2078 rewrite_update_phi_arguments (basic_block bb)
2084 FOR_EACH_EDGE (e, ei, bb->succs)
2089 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2092 phis = VEC_index (gimple_vec, phis_to_rewrite, e->dest->index);
2093 FOR_EACH_VEC_ELT (gimple, phis, i, phi)
2095 tree arg, lhs_sym, reaching_def = NULL;
2096 use_operand_p arg_p;
2098 gcc_assert (rewrite_uses_p (phi));
2100 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2101 arg = USE_FROM_PTR (arg_p);
2103 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2106 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2108 if (arg == NULL_TREE)
2110 /* When updating a PHI node for a recently introduced
2111 symbol we may find NULL arguments. That's why we
2112 take the symbol from the LHS of the PHI node. */
2113 reaching_def = get_reaching_def (lhs_sym);
2118 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2120 if (symbol_marked_for_renaming (sym))
2121 reaching_def = get_reaching_def (sym);
2122 else if (is_old_name (arg))
2123 reaching_def = get_reaching_def (arg);
2126 /* Update the argument if there is a reaching def. */
2130 source_location locus;
2131 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2133 SET_USE (arg_p, reaching_def);
2134 stmt = SSA_NAME_DEF_STMT (reaching_def);
2136 /* Single element PHI nodes behave like copies, so get the
2137 location from the phi argument. */
2138 if (gimple_code (stmt) == GIMPLE_PHI &&
2139 gimple_phi_num_args (stmt) == 1)
2140 locus = gimple_phi_arg_location (stmt, 0);
2142 locus = gimple_location (stmt);
2144 gimple_phi_arg_set_location (phi, arg_i, locus);
2148 if (e->flags & EDGE_ABNORMAL)
2149 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2155 /* Initialization of block data structures for the incremental SSA
2156 update pass. Create a block local stack of reaching definitions
2157 for new SSA names produced in this block (BLOCK_DEFS). Register
2158 new definitions for every PHI node in the block. */
2161 rewrite_update_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2164 bool is_abnormal_phi;
2165 gimple_stmt_iterator gsi;
2167 if (dump_file && (dump_flags & TDF_DETAILS))
2168 fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
2171 /* Mark the unwind point for this block. */
2172 VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
2174 if (!bitmap_bit_p (blocks_to_update, bb->index))
2177 /* Mark the LHS if any of the arguments flows through an abnormal
2179 is_abnormal_phi = bb_has_abnormal_pred (bb);
2181 /* If any of the PHI nodes is a replacement for a name in
2182 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2183 register it as a new definition for its corresponding name. Also
2184 register definitions for names whose underlying symbols are
2185 marked for renaming. */
2186 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2189 gimple phi = gsi_stmt (gsi);
2191 if (!register_defs_p (phi))
2194 lhs = gimple_phi_result (phi);
2195 lhs_sym = SSA_NAME_VAR (lhs);
2197 if (symbol_marked_for_renaming (lhs_sym))
2198 register_new_update_single (lhs, lhs_sym);
2202 /* If LHS is a new name, register a new definition for all
2203 the names replaced by LHS. */
2204 if (is_new_name (lhs))
2205 register_new_update_set (lhs, names_replaced_by (lhs));
2207 /* If LHS is an OLD name, register it as a new definition
2209 if (is_old_name (lhs))
2210 register_new_update_single (lhs, lhs);
2213 if (is_abnormal_phi)
2214 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2217 /* Step 2. Rewrite every variable used in each statement in the block. */
2218 if (TEST_BIT (interesting_blocks, bb->index))
2220 gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
2221 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2222 rewrite_update_stmt (gsi_stmt (gsi), gsi);
2225 /* Step 3. Update PHI nodes. */
2226 rewrite_update_phi_arguments (bb);
2229 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2230 the current reaching definition of every name re-written in BB to
2231 the original reaching definition before visiting BB. This
2232 unwinding must be done in the opposite order to what is done in
2233 register_new_update_set. */
2236 rewrite_update_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2237 basic_block bb ATTRIBUTE_UNUSED)
2239 while (VEC_length (tree, block_defs_stack) > 0)
2241 tree var = VEC_pop (tree, block_defs_stack);
2244 /* NULL indicates the unwind stop point for this block (see
2245 rewrite_update_enter_block). */
2249 saved_def = VEC_pop (tree, block_defs_stack);
2250 set_current_def (var, saved_def);
2255 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2258 ENTRY indicates the block where to start. Every block dominated by
2259 ENTRY will be rewritten.
2261 WHAT indicates what actions will be taken by the renamer (see enum
2264 BLOCKS are the set of interesting blocks for the dominator walker
2265 to process. If this set is NULL, then all the nodes dominated
2266 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2267 are not present in BLOCKS are ignored. */
2270 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2272 struct dom_walk_data walk_data;
2274 /* Rewrite all the basic blocks in the program. */
2275 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2277 /* Setup callbacks for the generic dominator tree walker. */
2278 memset (&walk_data, 0, sizeof (walk_data));
2280 walk_data.dom_direction = CDI_DOMINATORS;
2282 if (what == REWRITE_ALL)
2284 walk_data.before_dom_children = rewrite_enter_block;
2285 walk_data.after_dom_children = rewrite_leave_block;
2287 else if (what == REWRITE_UPDATE)
2289 walk_data.before_dom_children = rewrite_update_enter_block;
2290 walk_data.after_dom_children = rewrite_update_leave_block;
2295 block_defs_stack = VEC_alloc (tree, heap, 10);
2297 /* Initialize the dominator walker. */
2298 init_walk_dominator_tree (&walk_data);
2300 /* Recursively walk the dominator tree rewriting each statement in
2301 each basic block. */
2302 walk_dominator_tree (&walk_data, entry);
2304 /* Finalize the dominator walker. */
2305 fini_walk_dominator_tree (&walk_data);
2307 /* Debugging dumps. */
2308 if (dump_file && (dump_flags & TDF_STATS))
2310 dump_dfa_stats (dump_file);
2312 dump_tree_ssa_stats (dump_file);
2315 VEC_free (tree, heap, block_defs_stack);
2317 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2321 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2322 at the start of each block, and call mark_def_sites for each statement. */
2325 mark_def_sites_block (struct dom_walk_data *walk_data, basic_block bb)
2327 struct mark_def_sites_global_data *gd;
2329 gimple_stmt_iterator gsi;
2331 gd = (struct mark_def_sites_global_data *) walk_data->global_data;
2334 bitmap_clear (kills);
2335 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2336 mark_def_sites (bb, gsi_stmt (gsi), kills);
2340 /* Mark the definition site blocks for each variable, so that we know
2341 where the variable is actually live.
2343 The INTERESTING_BLOCKS global will be filled in with all the blocks
2344 that should be processed by the renamer. It is assumed that the
2345 caller has already initialized and zeroed it. */
2348 mark_def_site_blocks (void)
2350 struct dom_walk_data walk_data;
2351 struct mark_def_sites_global_data mark_def_sites_global_data;
2353 /* Setup callbacks for the generic dominator tree walker to find and
2354 mark definition sites. */
2355 walk_data.dom_direction = CDI_DOMINATORS;
2356 walk_data.initialize_block_local_data = NULL;
2357 walk_data.before_dom_children = mark_def_sites_block;
2358 walk_data.after_dom_children = NULL;
2360 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2361 large enough to accommodate all the variables referenced in the
2362 function, not just the ones we are renaming. */
2363 mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
2364 walk_data.global_data = &mark_def_sites_global_data;
2366 /* We do not have any local data. */
2367 walk_data.block_local_data_size = 0;
2369 /* Initialize the dominator walker. */
2370 init_walk_dominator_tree (&walk_data);
2372 /* Recursively walk the dominator tree. */
2373 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
2375 /* Finalize the dominator walker. */
2376 fini_walk_dominator_tree (&walk_data);
2378 /* We no longer need this bitmap, clear and free it. */
2379 BITMAP_FREE (mark_def_sites_global_data.kills);
2383 /* Initialize internal data needed during renaming. */
2386 init_ssa_renamer (void)
2389 referenced_var_iterator rvi;
2391 cfun->gimple_df->in_ssa_p = false;
2393 /* Allocate memory for the DEF_BLOCKS hash table. */
2394 gcc_assert (def_blocks == NULL);
2395 def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
2396 def_blocks_eq, def_blocks_free);
2398 FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
2399 set_current_def (var, NULL_TREE);
2403 /* Deallocate internal data structures used by the renamer. */
2406 fini_ssa_renamer (void)
2410 htab_delete (def_blocks);
2414 cfun->gimple_df->in_ssa_p = true;
2417 /* Main entry point into the SSA builder. The renaming process
2418 proceeds in four main phases:
2420 1- Compute dominance frontier and immediate dominators, needed to
2421 insert PHI nodes and rename the function in dominator tree
2424 2- Find and mark all the blocks that define variables
2425 (mark_def_site_blocks).
2427 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2429 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2431 Steps 3 and 4 are done using the dominator tree walker
2432 (walk_dominator_tree). */
2435 rewrite_into_ssa (void)
2440 /* Initialize operand data structures. */
2441 init_ssa_operands ();
2443 /* Initialize internal data needed by the renamer. */
2444 init_ssa_renamer ();
2446 /* Initialize the set of interesting blocks. The callback
2447 mark_def_sites will add to this set those blocks that the renamer
2449 interesting_blocks = sbitmap_alloc (last_basic_block);
2450 sbitmap_zero (interesting_blocks);
2452 /* Initialize dominance frontier. */
2453 dfs = XNEWVEC (bitmap_head, last_basic_block);
2455 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2457 /* 1- Compute dominance frontiers. */
2458 calculate_dominance_info (CDI_DOMINATORS);
2459 compute_dominance_frontiers (dfs);
2461 /* 2- Find and mark definition sites. */
2462 mark_def_site_blocks ();
2464 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2465 insert_phi_nodes (dfs);
2467 /* 4- Rename all the blocks. */
2468 rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL);
2470 /* Free allocated memory. */
2472 bitmap_clear (&dfs[bb->index]);
2475 sbitmap_free (interesting_blocks);
2477 fini_ssa_renamer ();
2483 struct gimple_opt_pass pass_build_ssa =
2489 rewrite_into_ssa, /* execute */
2492 0, /* static_pass_number */
2493 TV_TREE_SSA_OTHER, /* tv_id */
2494 PROP_cfg | PROP_referenced_vars, /* properties_required */
2495 PROP_ssa, /* properties_provided */
2496 0, /* properties_destroyed */
2497 0, /* todo_flags_start */
2498 TODO_update_ssa_only_virtuals
2500 | TODO_remove_unused_locals /* todo_flags_finish */
2505 /* Mark the definition of VAR at STMT and BB as interesting for the
2506 renamer. BLOCKS is the set of blocks that need updating. */
2509 mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2511 gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
2512 set_register_defs (stmt, true);
2516 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2518 set_def_block (var, bb, is_phi_p);
2520 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2521 site for both itself and all the old names replaced by it. */
2522 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2526 bitmap set = names_replaced_by (var);
2528 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2529 set_def_block (ssa_name (i), bb, is_phi_p);
2535 /* Mark the use of VAR at STMT and BB as interesting for the
2536 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2540 mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2542 basic_block def_bb = gimple_bb (stmt);
2544 mark_block_for_update (def_bb);
2545 mark_block_for_update (bb);
2547 if (gimple_code (stmt) == GIMPLE_PHI)
2548 mark_phi_for_rewrite (def_bb, stmt);
2551 set_rewrite_uses (stmt, true);
2553 if (is_gimple_debug (stmt))
2557 /* If VAR has not been defined in BB, then it is live-on-entry
2558 to BB. Note that we cannot just use the block holding VAR's
2559 definition because if VAR is one of the names in OLD_SSA_NAMES,
2560 it will have several definitions (itself and all the names that
2564 struct def_blocks_d *db_p = get_def_blocks_for (var);
2565 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2566 set_livein_block (var, bb);
2571 /* Do a dominator walk starting at BB processing statements that
2572 reference symbols in SYMS_TO_RENAME. This is very similar to
2573 mark_def_sites, but the scan handles statements whose operands may
2574 already be SSA names.
2576 If INSERT_PHI_P is true, mark those uses as live in the
2577 corresponding block. This is later used by the PHI placement
2578 algorithm to make PHI pruning decisions.
2580 FIXME. Most of this would be unnecessary if we could associate a
2581 symbol to all the SSA names that reference it. But that
2582 sounds like it would be expensive to maintain. Still, it
2583 would be interesting to see if it makes better sense to do
2587 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2590 gimple_stmt_iterator si;
2594 mark_block_for_update (bb);
2596 /* Process PHI nodes marking interesting those that define or use
2597 the symbols that we are interested in. */
2598 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
2600 gimple phi = gsi_stmt (si);
2601 tree lhs_sym, lhs = gimple_phi_result (phi);
2603 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2605 if (!symbol_marked_for_renaming (lhs_sym))
2608 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2610 /* Mark the uses in phi nodes as interesting. It would be more correct
2611 to process the arguments of the phi nodes of the successor edges of
2612 BB at the end of prepare_block_for_update, however, that turns out
2613 to be significantly more expensive. Doing it here is conservatively
2614 correct -- it may only cause us to believe a value to be live in a
2615 block that also contains its definition, and thus insert a few more
2616 phi nodes for it. */
2617 FOR_EACH_EDGE (e, ei, bb->preds)
2618 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2621 /* Process the statements. */
2622 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2626 use_operand_p use_p;
2627 def_operand_p def_p;
2629 stmt = gsi_stmt (si);
2631 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
2633 tree use = USE_FROM_PTR (use_p);
2634 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2635 if (symbol_marked_for_renaming (sym))
2636 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2639 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_ALL_DEFS)
2641 tree def = DEF_FROM_PTR (def_p);
2642 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2643 if (symbol_marked_for_renaming (sym))
2644 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2648 /* Now visit all the blocks dominated by BB. */
2649 for (son = first_dom_son (CDI_DOMINATORS, bb);
2651 son = next_dom_son (CDI_DOMINATORS, son))
2652 prepare_block_for_update (son, insert_phi_p);
2656 /* Helper for prepare_names_to_update. Mark all the use sites for
2657 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2658 prepare_names_to_update. */
2661 prepare_use_sites_for (tree name, bool insert_phi_p)
2663 use_operand_p use_p;
2664 imm_use_iterator iter;
2666 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2668 gimple stmt = USE_STMT (use_p);
2669 basic_block bb = gimple_bb (stmt);
2671 if (gimple_code (stmt) == GIMPLE_PHI)
2673 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2674 edge e = gimple_phi_arg_edge (stmt, ix);
2675 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2679 /* For regular statements, mark this as an interesting use
2681 mark_use_interesting (name, stmt, bb, insert_phi_p);
2687 /* Helper for prepare_names_to_update. Mark the definition site for
2688 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2689 prepare_names_to_update. */
2692 prepare_def_site_for (tree name, bool insert_phi_p)
2697 gcc_assert (names_to_release == NULL
2698 || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2700 stmt = SSA_NAME_DEF_STMT (name);
2701 bb = gimple_bb (stmt);
2704 gcc_assert (bb->index < last_basic_block);
2705 mark_block_for_update (bb);
2706 mark_def_interesting (name, stmt, bb, insert_phi_p);
2711 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2712 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2713 PHI nodes for newly created names. */
2716 prepare_names_to_update (bool insert_phi_p)
2720 sbitmap_iterator sbi;
2722 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2723 remove it from NEW_SSA_NAMES so that we don't try to visit its
2724 defining basic block (which most likely doesn't exist). Notice
2725 that we cannot do the same with names in OLD_SSA_NAMES because we
2726 want to replace existing instances. */
2727 if (names_to_release)
2728 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2729 RESET_BIT (new_ssa_names, i);
2731 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2732 names may be considered to be live-in on blocks that contain
2733 definitions for their replacements. */
2734 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2735 prepare_def_site_for (ssa_name (i), insert_phi_p);
2737 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2738 OLD_SSA_NAMES, but we have to ignore its definition site. */
2739 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2741 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2742 prepare_def_site_for (ssa_name (i), insert_phi_p);
2743 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2748 /* Dump all the names replaced by NAME to FILE. */
2751 dump_names_replaced_by (FILE *file, tree name)
2757 print_generic_expr (file, name, 0);
2758 fprintf (file, " -> { ");
2760 old_set = names_replaced_by (name);
2761 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2763 print_generic_expr (file, ssa_name (i), 0);
2764 fprintf (file, " ");
2767 fprintf (file, "}\n");
2771 /* Dump all the names replaced by NAME to stderr. */
2774 debug_names_replaced_by (tree name)
2776 dump_names_replaced_by (stderr, name);
2780 /* Dump SSA update information to FILE. */
2783 dump_update_ssa (FILE *file)
2788 if (!need_ssa_update_p (cfun))
2791 if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2793 sbitmap_iterator sbi;
2795 fprintf (file, "\nSSA replacement table\n");
2796 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2797 "O_1, ..., O_j\n\n");
2799 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2800 dump_names_replaced_by (file, ssa_name (i));
2802 fprintf (file, "\n");
2803 fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
2804 update_ssa_stats.num_virtual_mappings);
2805 fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
2806 update_ssa_stats.num_total_mappings
2807 - update_ssa_stats.num_virtual_mappings);
2808 fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
2809 update_ssa_stats.num_total_mappings);
2811 fprintf (file, "\nNumber of virtual symbols: %u\n",
2812 update_ssa_stats.num_virtual_symbols);
2815 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
2817 fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2818 dump_decl_set (file, SYMS_TO_RENAME (cfun));
2819 fprintf (file, "\n");
2822 if (names_to_release && !bitmap_empty_p (names_to_release))
2824 fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2825 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2827 print_generic_expr (file, ssa_name (i), 0);
2828 fprintf (file, " ");
2832 fprintf (file, "\n\n");
2836 /* Dump SSA update information to stderr. */
2839 debug_update_ssa (void)
2841 dump_update_ssa (stderr);
2845 /* Initialize data structures used for incremental SSA updates. */
2848 init_update_ssa (struct function *fn)
2850 /* Reserve more space than the current number of names. The calls to
2851 add_new_name_mapping are typically done after creating new SSA
2852 names, so we'll need to reallocate these arrays. */
2853 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2854 sbitmap_zero (old_ssa_names);
2856 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2857 sbitmap_zero (new_ssa_names);
2859 repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2860 names_to_release = NULL;
2861 memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
2862 update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
2863 update_ssa_initialized_fn = fn;
2867 /* Deallocate data structures used for incremental SSA updates. */
2870 delete_update_ssa (void)
2875 sbitmap_free (old_ssa_names);
2876 old_ssa_names = NULL;
2878 sbitmap_free (new_ssa_names);
2879 new_ssa_names = NULL;
2881 htab_delete (repl_tbl);
2884 bitmap_clear (SYMS_TO_RENAME (update_ssa_initialized_fn));
2885 BITMAP_FREE (update_ssa_stats.virtual_symbols);
2887 if (names_to_release)
2889 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2890 release_ssa_name (ssa_name (i));
2891 BITMAP_FREE (names_to_release);
2894 clear_ssa_name_info ();
2896 fini_ssa_renamer ();
2898 if (blocks_with_phis_to_rewrite)
2899 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2901 gimple_vec phis = VEC_index (gimple_vec, phis_to_rewrite, i);
2903 VEC_free (gimple, heap, phis);
2904 VEC_replace (gimple_vec, phis_to_rewrite, i, NULL);
2907 BITMAP_FREE (blocks_with_phis_to_rewrite);
2908 BITMAP_FREE (blocks_to_update);
2909 update_ssa_initialized_fn = NULL;
2913 /* Create a new name for OLD_NAME in statement STMT and replace the
2914 operand pointed to by DEF_P with the newly created name. Return
2915 the new name and register the replacement mapping <NEW, OLD> in
2916 update_ssa's tables. */
2919 create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
2921 tree new_name = duplicate_ssa_name (old_name, stmt);
2923 SET_DEF (def, new_name);
2925 if (gimple_code (stmt) == GIMPLE_PHI)
2927 basic_block bb = gimple_bb (stmt);
2929 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2930 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2933 register_new_name_mapping (new_name, old_name);
2935 /* For the benefit of passes that will be updating the SSA form on
2936 their own, set the current reaching definition of OLD_NAME to be
2938 set_current_def (old_name, new_name);
2944 /* Register name NEW to be a replacement for name OLD. This function
2945 must be called for every replacement that should be performed by
2949 register_new_name_mapping (tree new_tree, tree old)
2951 if (!update_ssa_initialized_fn)
2952 init_update_ssa (cfun);
2954 gcc_assert (update_ssa_initialized_fn == cfun);
2956 add_new_name_mapping (new_tree, old);
2960 /* Register symbol SYM to be renamed by update_ssa. */
2963 mark_sym_for_renaming (tree sym)
2965 bitmap_set_bit (SYMS_TO_RENAME (cfun), DECL_UID (sym));
2969 /* Register all the symbols in SET to be renamed by update_ssa. */
2972 mark_set_for_renaming (bitmap set)
2977 if (set == NULL || bitmap_empty_p (set))
2980 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2981 mark_sym_for_renaming (referenced_var (i));
2985 /* Return true if there is any work to be done by update_ssa
2989 need_ssa_update_p (struct function *fn)
2991 gcc_assert (fn != NULL);
2992 return (update_ssa_initialized_fn == fn
2994 && !bitmap_empty_p (SYMS_TO_RENAME (fn))));
2997 /* Return true if SSA name mappings have been registered for SSA updating. */
3000 name_mappings_registered_p (void)
3002 if (!update_ssa_initialized_fn)
3005 gcc_assert (update_ssa_initialized_fn == cfun);
3007 return repl_tbl && htab_elements (repl_tbl) > 0;
3010 /* Return true if name N has been registered in the replacement table. */
3013 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3015 if (!update_ssa_initialized_fn)
3018 gcc_assert (update_ssa_initialized_fn == cfun);
3020 return is_new_name (n) || is_old_name (n);
3024 /* Return the set of all the SSA names marked to be replaced. */
3027 ssa_names_to_replace (void)
3031 sbitmap_iterator sbi;
3033 gcc_assert (update_ssa_initialized_fn == NULL
3034 || update_ssa_initialized_fn == cfun);
3036 ret = BITMAP_ALLOC (NULL);
3037 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3038 bitmap_set_bit (ret, i);
3044 /* Mark NAME to be released after update_ssa has finished. */
3047 release_ssa_name_after_update_ssa (tree name)
3049 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3051 if (names_to_release == NULL)
3052 names_to_release = BITMAP_ALLOC (NULL);
3054 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3058 /* Insert new PHI nodes to replace VAR. DFS contains dominance
3059 frontier information. BLOCKS is the set of blocks to be updated.
3061 This is slightly different than the regular PHI insertion
3062 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3063 real names (i.e., GIMPLE registers) are inserted:
3065 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3066 nodes inside the region affected by the block that defines VAR
3067 and the blocks that define all its replacements. All these
3068 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3070 First, we compute the entry point to the region (ENTRY). This is
3071 given by the nearest common dominator to all the definition
3072 blocks. When computing the iterated dominance frontier (IDF), any
3073 block not strictly dominated by ENTRY is ignored.
3075 We then call the standard PHI insertion algorithm with the pruned
3078 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3079 names is not pruned. PHI nodes are inserted at every IDF block. */
3082 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
3083 unsigned update_flags)
3086 struct def_blocks_d *db;
3087 bitmap idf, pruned_idf;
3091 if (TREE_CODE (var) == SSA_NAME)
3092 gcc_checking_assert (is_old_name (var));
3094 gcc_checking_assert (symbol_marked_for_renaming (var));
3096 /* Get all the definition sites for VAR. */
3097 db = find_def_blocks_for (var);
3099 /* No need to do anything if there were no definitions to VAR. */
3100 if (db == NULL || bitmap_empty_p (db->def_blocks))
3103 /* Compute the initial iterated dominance frontier. */
3104 idf = compute_idf (db->def_blocks, dfs);
3105 pruned_idf = BITMAP_ALLOC (NULL);
3107 if (TREE_CODE (var) == SSA_NAME)
3109 if (update_flags == TODO_update_ssa)
3111 /* If doing regular SSA updates for GIMPLE registers, we are
3112 only interested in IDF blocks dominated by the nearest
3113 common dominator of all the definition blocks. */
3114 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3116 if (entry != ENTRY_BLOCK_PTR)
3117 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3118 if (BASIC_BLOCK (i) != entry
3119 && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
3120 bitmap_set_bit (pruned_idf, i);
3124 /* Otherwise, do not prune the IDF for VAR. */
3125 gcc_assert (update_flags == TODO_update_ssa_full_phi);
3126 bitmap_copy (pruned_idf, idf);
3131 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3132 for the first time, so we need to compute the full IDF for
3134 bitmap_copy (pruned_idf, idf);
3137 if (!bitmap_empty_p (pruned_idf))
3139 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3140 are included in the region to be updated. The feeding blocks
3141 are important to guarantee that the PHI arguments are renamed
3144 /* FIXME, this is not needed if we are updating symbols. We are
3145 already starting at the ENTRY block anyway. */
3146 bitmap_ior_into (blocks, pruned_idf);
3147 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3151 basic_block bb = BASIC_BLOCK (i);
3153 FOR_EACH_EDGE (e, ei, bb->preds)
3154 if (e->src->index >= 0)
3155 bitmap_set_bit (blocks, e->src->index);
3158 insert_phi_nodes_for (var, pruned_idf, true);
3161 BITMAP_FREE (pruned_idf);
3166 /* Heuristic to determine whether SSA name mappings for virtual names
3167 should be discarded and their symbols rewritten from scratch. When
3168 there is a large number of mappings for virtual names, the
3169 insertion of PHI nodes for the old names in the mappings takes
3170 considerable more time than if we inserted PHI nodes for the
3173 Currently the heuristic takes these stats into account:
3175 - Number of mappings for virtual SSA names.
3176 - Number of distinct virtual symbols involved in those mappings.
3178 If the number of virtual mappings is much larger than the number of
3179 virtual symbols, then it will be faster to compute PHI insertion
3180 spots for the symbols. Even if this involves traversing the whole
3181 CFG, which is what happens when symbols are renamed from scratch. */
3184 switch_virtuals_to_full_rewrite_p (void)
3186 if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
3189 if (update_ssa_stats.num_virtual_mappings
3190 > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
3191 * update_ssa_stats.num_virtual_symbols)
3198 /* Remove every virtual mapping and mark all the affected virtual
3199 symbols for renaming. */
3202 switch_virtuals_to_full_rewrite (void)
3205 sbitmap_iterator sbi;
3209 fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
3210 fprintf (dump_file, "\tNumber of virtual mappings: %7u\n",
3211 update_ssa_stats.num_virtual_mappings);
3212 fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
3213 update_ssa_stats.num_virtual_symbols);
3214 fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
3215 "faster than processing\nthe name mappings.\n\n");
3218 /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
3219 Note that it is not really necessary to remove the mappings from
3220 REPL_TBL, that would only waste time. */
3221 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
3222 if (!is_gimple_reg (ssa_name (i)))
3223 RESET_BIT (new_ssa_names, i);
3225 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3226 if (!is_gimple_reg (ssa_name (i)))
3227 RESET_BIT (old_ssa_names, i);
3229 mark_set_for_renaming (update_ssa_stats.virtual_symbols);
3233 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3234 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3236 1- The names in OLD_SSA_NAMES dominated by the definitions of
3237 NEW_SSA_NAMES are all re-written to be reached by the
3238 appropriate definition from NEW_SSA_NAMES.
3240 2- If needed, new PHI nodes are added to the iterated dominance
3241 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3243 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3244 calling register_new_name_mapping for every pair of names that the
3245 caller wants to replace.
3247 The caller identifies the new names that have been inserted and the
3248 names that need to be replaced by calling register_new_name_mapping
3249 for every pair <NEW, OLD>. Note that the function assumes that the
3250 new names have already been inserted in the IL.
3252 For instance, given the following code:
3255 2 x_1 = PHI (0, x_5)
3266 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3269 2 x_1 = PHI (0, x_5)
3282 We want to replace all the uses of x_1 with the new definitions of
3283 x_10 and x_11. Note that the only uses that should be replaced are
3284 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3285 *not* be replaced (this is why we cannot just mark symbol 'x' for
3288 Additionally, we may need to insert a PHI node at line 11 because
3289 that is a merge point for x_10 and x_11. So the use of x_1 at line
3290 11 will be replaced with the new PHI node. The insertion of PHI
3291 nodes is optional. They are not strictly necessary to preserve the
3292 SSA form, and depending on what the caller inserted, they may not
3293 even be useful for the optimizers. UPDATE_FLAGS controls various
3294 aspects of how update_ssa operates, see the documentation for
3295 TODO_update_ssa*. */
3298 update_ssa (unsigned update_flags)
3300 basic_block bb, start_bb;
3304 sbitmap_iterator sbi;
3306 if (!need_ssa_update_p (cfun))
3309 timevar_push (TV_TREE_SSA_INCREMENTAL);
3311 if (!update_ssa_initialized_fn)
3312 init_update_ssa (cfun);
3313 gcc_assert (update_ssa_initialized_fn == cfun);
3315 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3316 if (!phis_to_rewrite)
3317 phis_to_rewrite = VEC_alloc (gimple_vec, heap, last_basic_block);
3318 blocks_to_update = BITMAP_ALLOC (NULL);
3320 /* Ensure that the dominance information is up-to-date. */
3321 calculate_dominance_info (CDI_DOMINATORS);
3323 /* Only one update flag should be set. */
3324 gcc_assert (update_flags == TODO_update_ssa
3325 || update_flags == TODO_update_ssa_no_phi
3326 || update_flags == TODO_update_ssa_full_phi
3327 || update_flags == TODO_update_ssa_only_virtuals);
3329 /* If we only need to update virtuals, remove all the mappings for
3330 real names before proceeding. The caller is responsible for
3331 having dealt with the name mappings before calling update_ssa. */
3332 if (update_flags == TODO_update_ssa_only_virtuals)
3334 sbitmap_zero (old_ssa_names);
3335 sbitmap_zero (new_ssa_names);
3336 htab_empty (repl_tbl);
3339 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3343 /* If the caller requested PHI nodes to be added, initialize
3344 live-in information data structures (DEF_BLOCKS). */
3346 /* For each SSA name N, the DEF_BLOCKS table describes where the
3347 name is defined, which blocks have PHI nodes for N, and which
3348 blocks have uses of N (i.e., N is live-on-entry in those
3350 def_blocks = htab_create (num_ssa_names, def_blocks_hash,
3351 def_blocks_eq, def_blocks_free);
3358 /* Heuristic to avoid massive slow downs when the replacement
3359 mappings include lots of virtual names. */
3360 if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
3361 switch_virtuals_to_full_rewrite ();
3363 /* If there are names defined in the replacement table, prepare
3364 definition and use sites for all the names in NEW_SSA_NAMES and
3366 if (sbitmap_first_set_bit (new_ssa_names) >= 0)
3368 prepare_names_to_update (insert_phi_p);
3370 /* If all the names in NEW_SSA_NAMES had been marked for
3371 removal, and there are no symbols to rename, then there's
3372 nothing else to do. */
3373 if (sbitmap_first_set_bit (new_ssa_names) < 0
3374 && bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3378 /* Next, determine the block at which to start the renaming process. */
3379 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
3381 /* If we have to rename some symbols from scratch, we need to
3382 start the process at the root of the CFG. FIXME, it should
3383 be possible to determine the nearest block that had a
3384 definition for each of the symbols that are marked for
3385 updating. For now this seems more work than it's worth. */
3386 start_bb = ENTRY_BLOCK_PTR;
3388 /* Traverse the CFG looking for existing definitions and uses of
3389 symbols in SYMS_TO_RENAME. Mark interesting blocks and
3390 statements and set local live-in information for the PHI
3391 placement heuristics. */
3392 prepare_block_for_update (start_bb, insert_phi_p);
3396 /* Otherwise, the entry block to the region is the nearest
3397 common dominator for the blocks in BLOCKS. */
3398 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3402 /* If requested, insert PHI nodes at the iterated dominance frontier
3403 of every block, creating new definitions for names in OLD_SSA_NAMES
3404 and for symbols in SYMS_TO_RENAME. */
3409 /* If the caller requested PHI nodes to be added, compute
3410 dominance frontiers. */
3411 dfs = XNEWVEC (bitmap_head, last_basic_block);
3413 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3414 compute_dominance_frontiers (dfs);
3416 if (sbitmap_first_set_bit (old_ssa_names) >= 0)
3418 sbitmap_iterator sbi;
3420 /* insert_update_phi_nodes_for will call add_new_name_mapping
3421 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3422 will grow while we are traversing it (but it will not
3423 gain any new members). Copy OLD_SSA_NAMES to a temporary
3425 sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
3426 sbitmap_copy (tmp, old_ssa_names);
3427 EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
3428 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3433 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3434 insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks_to_update,
3438 bitmap_clear (&dfs[bb->index]);
3441 /* Insertion of PHI nodes may have added blocks to the region.
3442 We need to re-compute START_BB to include the newly added
3444 if (start_bb != ENTRY_BLOCK_PTR)
3445 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3449 /* Reset the current definition for name and symbol before renaming
3451 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3452 set_current_def (ssa_name (i), NULL_TREE);
3454 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun), 0, i, bi)
3455 set_current_def (referenced_var (i), NULL_TREE);
3457 /* Now start the renaming process at START_BB. */
3458 interesting_blocks = sbitmap_alloc (last_basic_block);
3459 sbitmap_zero (interesting_blocks);
3460 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3461 SET_BIT (interesting_blocks, i);
3463 rewrite_blocks (start_bb, REWRITE_UPDATE);
3465 sbitmap_free (interesting_blocks);
3467 /* Debugging dumps. */
3473 dump_update_ssa (dump_file);
3475 fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
3479 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3481 fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
3482 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
3483 c, PERCENT (c, last_basic_block));
3485 if (dump_flags & TDF_DETAILS)
3487 fprintf (dump_file, "Affected blocks: ");
3488 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3489 fprintf (dump_file, "%u ", i);
3490 fprintf (dump_file, "\n");
3493 fprintf (dump_file, "\n\n");
3496 /* Free allocated memory. */
3498 delete_update_ssa ();
3500 timevar_pop (TV_TREE_SSA_INCREMENTAL);