1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
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_bit_p (blocks_to_update
, bb
->index
))
457 bitmap_set_bit (blocks_to_update
, bb
->index
);
458 initialize_flags_in_bb (bb
);
461 /* Return the set of blocks where variable VAR is defined and the blocks
462 where VAR is live on entry (livein). If no entry is found in
463 DEF_BLOCKS, a new one is created and returned. */
465 static inline struct def_blocks_d
*
466 get_def_blocks_for (tree var
)
468 struct def_blocks_d db
, *db_p
;
472 slot
= htab_find_slot (def_blocks
, (void *) &db
, INSERT
);
475 db_p
= XNEW (struct def_blocks_d
);
477 db_p
->def_blocks
= BITMAP_ALLOC (NULL
);
478 db_p
->phi_blocks
= BITMAP_ALLOC (NULL
);
479 db_p
->livein_blocks
= BITMAP_ALLOC (NULL
);
480 *slot
= (void *) db_p
;
483 db_p
= (struct def_blocks_d
*) *slot
;
489 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
490 VAR is defined by a PHI node. */
493 set_def_block (tree var
, basic_block bb
, bool phi_p
)
495 struct def_blocks_d
*db_p
;
496 enum need_phi_state state
;
498 state
= get_phi_state (var
);
499 db_p
= get_def_blocks_for (var
);
501 /* Set the bit corresponding to the block where VAR is defined. */
502 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
504 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
506 /* Keep track of whether or not we may need to insert PHI nodes.
508 If we are in the UNKNOWN state, then this is the first definition
509 of VAR. Additionally, we have not seen any uses of VAR yet, so
510 we do not need a PHI node for this variable at this time (i.e.,
511 transition to NEED_PHI_STATE_NO).
513 If we are in any other state, then we either have multiple definitions
514 of this variable occurring in different blocks or we saw a use of the
515 variable which was not dominated by the block containing the
516 definition(s). In this case we may need a PHI node, so enter
517 state NEED_PHI_STATE_MAYBE. */
518 if (state
== NEED_PHI_STATE_UNKNOWN
)
519 set_phi_state (var
, NEED_PHI_STATE_NO
);
521 set_phi_state (var
, NEED_PHI_STATE_MAYBE
);
525 /* Mark block BB as having VAR live at the entry to BB. */
528 set_livein_block (tree var
, basic_block bb
)
530 struct def_blocks_d
*db_p
;
531 enum need_phi_state state
= get_phi_state (var
);
533 db_p
= get_def_blocks_for (var
);
535 /* Set the bit corresponding to the block where VAR is live in. */
536 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
538 /* Keep track of whether or not we may need to insert PHI nodes.
540 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
541 by the single block containing the definition(s) of this variable. If
542 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
543 NEED_PHI_STATE_MAYBE. */
544 if (state
== NEED_PHI_STATE_NO
)
546 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
548 if (def_block_index
== -1
549 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
550 BASIC_BLOCK (def_block_index
)))
551 set_phi_state (var
, NEED_PHI_STATE_MAYBE
);
554 set_phi_state (var
, NEED_PHI_STATE_MAYBE
);
558 /* Return true if symbol SYM is marked for renaming. */
561 symbol_marked_for_renaming (tree sym
)
563 return bitmap_bit_p (SYMS_TO_RENAME (cfun
), DECL_UID (sym
));
567 /* Return true if NAME is in OLD_SSA_NAMES. */
570 is_old_name (tree name
)
572 unsigned ver
= SSA_NAME_VERSION (name
);
575 return ver
< new_ssa_names
->n_bits
&& TEST_BIT (old_ssa_names
, ver
);
579 /* Return true if NAME is in NEW_SSA_NAMES. */
582 is_new_name (tree name
)
584 unsigned ver
= SSA_NAME_VERSION (name
);
587 return ver
< new_ssa_names
->n_bits
&& TEST_BIT (new_ssa_names
, ver
);
591 /* Hashing and equality functions for REPL_TBL. */
594 repl_map_hash (const void *p
)
596 return htab_hash_pointer ((const void *)((const struct repl_map_d
*)p
)->name
);
600 repl_map_eq (const void *p1
, const void *p2
)
602 return ((const struct repl_map_d
*)p1
)->name
603 == ((const struct repl_map_d
*)p2
)->name
;
607 repl_map_free (void *p
)
609 BITMAP_FREE (((struct repl_map_d
*)p
)->set
);
614 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
617 names_replaced_by (tree new_tree
)
623 slot
= htab_find_slot (repl_tbl
, (void *) &m
, NO_INSERT
);
625 /* If N was not registered in the replacement table, return NULL. */
626 if (slot
== NULL
|| *slot
== NULL
)
629 return ((struct repl_map_d
*) *slot
)->set
;
633 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
636 add_to_repl_tbl (tree new_tree
, tree old
)
638 struct repl_map_d m
, *mp
;
642 slot
= htab_find_slot (repl_tbl
, (void *) &m
, INSERT
);
645 mp
= XNEW (struct repl_map_d
);
647 mp
->set
= BITMAP_ALLOC (NULL
);
651 mp
= (struct repl_map_d
*) *slot
;
653 bitmap_set_bit (mp
->set
, SSA_NAME_VERSION (old
));
657 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
658 represents the set of names O_1 ... O_j replaced by N_i. This is
659 used by update_ssa and its helpers to introduce new SSA names in an
660 already formed SSA web. */
663 add_new_name_mapping (tree new_tree
, tree old
)
665 timevar_push (TV_TREE_SSA_INCREMENTAL
);
667 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
668 gcc_assert (new_tree
!= old
&& SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
670 /* If this mapping is for virtual names, we will need to update
671 virtual operands. If this is a mapping for .MEM, then we gather
672 the symbols associated with each name. */
673 if (!is_gimple_reg (new_tree
))
677 update_ssa_stats
.num_virtual_mappings
++;
678 update_ssa_stats
.num_virtual_symbols
++;
680 /* Keep counts of virtual mappings and symbols to use in the
681 virtual mapping heuristic. If we have large numbers of
682 virtual mappings for a relatively low number of symbols, it
683 will make more sense to rename the symbols from scratch.
684 Otherwise, the insertion of PHI nodes for each of the old
685 names in these mappings will be very slow. */
686 sym
= SSA_NAME_VAR (new_tree
);
687 bitmap_set_bit (update_ssa_stats
.virtual_symbols
, DECL_UID (sym
));
690 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
691 caller may have created new names since the set was created. */
692 if (new_ssa_names
->n_bits
<= num_ssa_names
- 1)
694 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
695 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
696 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
699 /* Update the REPL_TBL table. */
700 add_to_repl_tbl (new_tree
, old
);
702 /* If OLD had already been registered as a new name, then all the
703 names that OLD replaces should also be replaced by NEW_TREE. */
704 if (is_new_name (old
))
705 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
707 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
709 SET_BIT (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
710 SET_BIT (old_ssa_names
, SSA_NAME_VERSION (old
));
712 /* Update mapping counter to use in the virtual mapping heuristic. */
713 update_ssa_stats
.num_total_mappings
++;
715 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
719 /* Call back for walk_dominator_tree used to collect definition sites
720 for every variable in the function. For every statement S in block
723 1- Variables defined by S in the DEFS of S are marked in the bitmap
726 2- If S uses a variable VAR and there is no preceding kill of VAR,
727 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
729 This information is used to determine which variables are live
730 across block boundaries to reduce the number of PHI nodes
734 mark_def_sites (basic_block bb
, gimple stmt
, bitmap kills
)
740 /* Since this is the first time that we rewrite the program into SSA
741 form, force an operand scan on every statement. */
744 gcc_assert (blocks_to_update
== NULL
);
745 set_register_defs (stmt
, false);
746 set_rewrite_uses (stmt
, false);
748 if (is_gimple_debug (stmt
))
751 /* If a variable is used before being set, then the variable is live
752 across a block boundary, so mark it live-on-entry to BB. */
753 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
755 tree sym
= USE_FROM_PTR (use_p
);
756 gcc_assert (DECL_P (sym
));
757 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
758 set_livein_block (sym
, bb
);
759 set_rewrite_uses (stmt
, true);
762 /* Now process the defs. Mark BB as the definition block and add
763 each def to the set of killed symbols. */
764 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
766 gcc_assert (DECL_P (def
));
767 set_def_block (def
, bb
, false);
768 bitmap_set_bit (kills
, DECL_UID (def
));
769 set_register_defs (stmt
, true);
772 /* If we found the statement interesting then also mark the block BB
774 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
775 SET_BIT (interesting_blocks
, bb
->index
);
778 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
779 in the dfs numbering of the dominance tree. */
783 /* Basic block whose index this entry corresponds to. */
786 /* The dfs number of this node. */
790 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
794 cmp_dfsnum (const void *a
, const void *b
)
796 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
797 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
799 return (int) da
->dfs_num
- (int) db
->dfs_num
;
802 /* Among the intervals starting at the N points specified in DEFS, find
803 the one that contains S, and return its bb_index. */
806 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
808 unsigned f
= 0, t
= n
, m
;
813 if (defs
[m
].dfs_num
<= s
)
819 return defs
[f
].bb_index
;
822 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
823 KILLS is a bitmap of blocks where the value is defined before any use. */
826 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
828 VEC(int, heap
) *worklist
;
830 unsigned i
, b
, p
, u
, top
;
832 basic_block def_bb
, use_bb
;
836 struct dom_dfsnum
*defs
;
837 unsigned n_defs
, adef
;
839 if (bitmap_empty_p (uses
))
845 /* The phi must dominate a use, or an argument of a live phi. Also, we
846 do not create any phi nodes in def blocks, unless they are also livein. */
847 to_remove
= BITMAP_ALLOC (NULL
);
848 bitmap_and_compl (to_remove
, kills
, uses
);
849 bitmap_and_compl_into (phis
, to_remove
);
850 if (bitmap_empty_p (phis
))
852 BITMAP_FREE (to_remove
);
856 /* We want to remove the unnecessary phi nodes, but we do not want to compute
857 liveness information, as that may be linear in the size of CFG, and if
858 there are lot of different variables to rewrite, this may lead to quadratic
861 Instead, we basically emulate standard dce. We put all uses to worklist,
862 then for each of them find the nearest def that dominates them. If this
863 def is a phi node, we mark it live, and if it was not live before, we
864 add the predecessors of its basic block to the worklist.
866 To quickly locate the nearest def that dominates use, we use dfs numbering
867 of the dominance tree (that is already available in order to speed up
868 queries). For each def, we have the interval given by the dfs number on
869 entry to and on exit from the corresponding subtree in the dominance tree.
870 The nearest dominator for a given use is the smallest of these intervals
871 that contains entry and exit dfs numbers for the basic block with the use.
872 If we store the bounds for all the uses to an array and sort it, we can
873 locate the nearest dominating def in logarithmic time by binary search.*/
874 bitmap_ior (to_remove
, kills
, phis
);
875 n_defs
= bitmap_count_bits (to_remove
);
876 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
877 defs
[0].bb_index
= 1;
880 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
882 def_bb
= BASIC_BLOCK (i
);
883 defs
[adef
].bb_index
= i
;
884 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
885 defs
[adef
+ 1].bb_index
= i
;
886 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
889 BITMAP_FREE (to_remove
);
890 gcc_assert (adef
== 2 * n_defs
+ 1);
891 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
892 gcc_assert (defs
[0].bb_index
== 1);
894 /* Now each DEFS entry contains the number of the basic block to that the
895 dfs number corresponds. Change them to the number of basic block that
896 corresponds to the interval following the dfs number. Also, for the
897 dfs_out numbers, increase the dfs number by one (so that it corresponds
898 to the start of the following interval, not to the end of the current
899 one). We use WORKLIST as a stack. */
900 worklist
= VEC_alloc (int, heap
, n_defs
+ 1);
901 VEC_quick_push (int, worklist
, 1);
904 for (i
= 1; i
< adef
; i
++)
906 b
= defs
[i
].bb_index
;
909 /* This is a closing element. Interval corresponding to the top
910 of the stack after removing it follows. */
911 VEC_pop (int, worklist
);
912 top
= VEC_index (int, worklist
, VEC_length (int, worklist
) - 1);
913 defs
[n_defs
].bb_index
= top
;
914 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
918 /* Opening element. Nothing to do, just push it to the stack and move
919 it to the correct position. */
920 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
921 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
922 VEC_quick_push (int, worklist
, b
);
926 /* If this interval starts at the same point as the previous one, cancel
928 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
929 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
933 VEC_pop (int, worklist
);
934 gcc_assert (VEC_empty (int, worklist
));
936 /* Now process the uses. */
937 live_phis
= BITMAP_ALLOC (NULL
);
938 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
940 VEC_safe_push (int, heap
, worklist
, i
);
943 while (!VEC_empty (int, worklist
))
945 b
= VEC_pop (int, worklist
);
946 if (b
== ENTRY_BLOCK
)
949 /* If there is a phi node in USE_BB, it is made live. Otherwise,
950 find the def that dominates the immediate dominator of USE_BB
951 (the kill in USE_BB does not dominate the use). */
952 if (bitmap_bit_p (phis
, b
))
956 use_bb
= get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (b
));
957 p
= find_dfsnum_interval (defs
, n_defs
,
958 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
959 if (!bitmap_bit_p (phis
, p
))
963 /* If the phi node is already live, there is nothing to do. */
964 if (bitmap_bit_p (live_phis
, p
))
967 /* Mark the phi as live, and add the new uses to the worklist. */
968 bitmap_set_bit (live_phis
, p
);
969 def_bb
= BASIC_BLOCK (p
);
970 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
973 if (bitmap_bit_p (uses
, u
))
976 /* In case there is a kill directly in the use block, do not record
977 the use (this is also necessary for correctness, as we assume that
978 uses dominated by a def directly in their block have been filtered
980 if (bitmap_bit_p (kills
, u
))
983 bitmap_set_bit (uses
, u
);
984 VEC_safe_push (int, heap
, worklist
, u
);
988 VEC_free (int, heap
, worklist
);
989 bitmap_copy (phis
, live_phis
);
990 BITMAP_FREE (live_phis
);
994 /* Return the set of blocks where variable VAR is defined and the blocks
995 where VAR is live on entry (livein). Return NULL, if no entry is
996 found in DEF_BLOCKS. */
998 static inline struct def_blocks_d
*
999 find_def_blocks_for (tree var
)
1001 struct def_blocks_d dm
;
1003 return (struct def_blocks_d
*) htab_find (def_blocks
, &dm
);
1007 /* Retrieve or create a default definition for symbol SYM. */
1010 get_default_def_for (tree sym
)
1012 tree ddef
= gimple_default_def (cfun
, sym
);
1014 if (ddef
== NULL_TREE
)
1016 ddef
= make_ssa_name (sym
, gimple_build_nop ());
1017 set_default_def (sym
, ddef
);
1024 /* Marks phi node PHI in basic block BB for rewrite. */
1027 mark_phi_for_rewrite (basic_block bb
, gimple phi
)
1030 unsigned i
, idx
= bb
->index
;
1032 if (rewrite_uses_p (phi
))
1035 set_rewrite_uses (phi
, true);
1037 if (!blocks_with_phis_to_rewrite
)
1040 bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
);
1041 VEC_reserve (gimple_vec
, heap
, phis_to_rewrite
, last_basic_block
+ 1);
1042 for (i
= VEC_length (gimple_vec
, phis_to_rewrite
); i
<= idx
; i
++)
1043 VEC_quick_push (gimple_vec
, phis_to_rewrite
, NULL
);
1045 phis
= VEC_index (gimple_vec
, phis_to_rewrite
, idx
);
1047 phis
= VEC_alloc (gimple
, heap
, 10);
1049 VEC_safe_push (gimple
, heap
, phis
, phi
);
1050 VEC_replace (gimple_vec
, phis_to_rewrite
, idx
, phis
);
1053 /* Insert PHI nodes for variable VAR using the iterated dominance
1054 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
1055 function assumes that the caller is incrementally updating the
1056 existing SSA form, in which case VAR may be an SSA name instead of
1059 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
1060 PHI node for VAR. On exit, only the nodes that received a PHI node
1061 for VAR will be present in PHI_INSERTION_POINTS. */
1064 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
1071 struct def_blocks_d
*def_map
;
1073 def_map
= find_def_blocks_for (var
);
1074 gcc_assert (def_map
);
1076 /* Remove the blocks where we already have PHI nodes for VAR. */
1077 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
1079 /* Remove obviously useless phi nodes. */
1080 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
1081 def_map
->livein_blocks
);
1083 /* And insert the PHI nodes. */
1084 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
1086 bb
= BASIC_BLOCK (bb_index
);
1088 mark_block_for_update (bb
);
1092 if (TREE_CODE (var
) == SSA_NAME
)
1094 /* If we are rewriting SSA names, create the LHS of the PHI
1095 node by duplicating VAR. This is useful in the case of
1096 pointers, to also duplicate pointer attributes (alias
1097 information, in particular). */
1101 gcc_assert (update_p
);
1102 phi
= create_phi_node (var
, bb
);
1104 new_lhs
= duplicate_ssa_name (var
, phi
);
1105 gimple_phi_set_result (phi
, new_lhs
);
1106 add_new_name_mapping (new_lhs
, var
);
1108 /* Add VAR to every argument slot of PHI. We need VAR in
1109 every argument so that rewrite_update_phi_arguments knows
1110 which name is this PHI node replacing. If VAR is a
1111 symbol marked for renaming, this is not necessary, the
1112 renamer will use the symbol on the LHS to get its
1113 reaching definition. */
1114 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1115 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1121 gcc_assert (DECL_P (var
));
1122 phi
= create_phi_node (var
, bb
);
1124 tracked_var
= target_for_debug_bind (var
);
1127 gimple note
= gimple_build_debug_bind (tracked_var
,
1130 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1131 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1135 /* Mark this PHI node as interesting for update_ssa. */
1136 set_register_defs (phi
, true);
1137 mark_phi_for_rewrite (bb
, phi
);
1142 /* Insert PHI nodes at the dominance frontier of blocks with variable
1143 definitions. DFS contains the dominance frontier information for
1147 insert_phi_nodes (bitmap
*dfs
)
1149 referenced_var_iterator rvi
;
1155 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1157 /* Do two stages to avoid code generation differences for UID
1158 differences but no UID ordering differences. */
1160 vars
= BITMAP_ALLOC (NULL
);
1161 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1163 struct def_blocks_d
*def_map
;
1165 def_map
= find_def_blocks_for (var
);
1166 if (def_map
== NULL
)
1169 if (get_phi_state (var
) != NEED_PHI_STATE_NO
)
1170 bitmap_set_bit (vars
, DECL_UID (var
));
1173 EXECUTE_IF_SET_IN_BITMAP (vars
, 0, uid
, bi
)
1175 tree var
= referenced_var (uid
);
1176 struct def_blocks_d
*def_map
;
1179 def_map
= find_def_blocks_for (var
);
1180 idf
= compute_idf (def_map
->def_blocks
, dfs
);
1181 insert_phi_nodes_for (var
, idf
, false);
1187 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1191 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1192 register DEF (an SSA_NAME) to be a new definition for SYM. */
1195 register_new_def (tree def
, tree sym
)
1199 /* If this variable is set in a single basic block and all uses are
1200 dominated by the set(s) in that single basic block, then there is
1201 no reason to record anything for this variable in the block local
1202 definition stacks. Doing so just wastes time and memory.
1204 This is the same test to prune the set of variables which may
1205 need PHI nodes. So we just use that information since it's already
1206 computed and available for us to use. */
1207 if (get_phi_state (sym
) == NEED_PHI_STATE_NO
)
1209 set_current_def (sym
, def
);
1213 currdef
= get_current_def (sym
);
1215 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1216 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1217 in the stack so that we know which symbol is being defined by
1218 this SSA name when we unwind the stack. */
1219 if (currdef
&& !is_gimple_reg (sym
))
1220 VEC_safe_push (tree
, heap
, block_defs_stack
, sym
);
1222 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1223 stack is later used by the dominator tree callbacks to restore
1224 the reaching definitions for all the variables defined in the
1225 block after a recursive visit to all its immediately dominated
1226 blocks. If there is no current reaching definition, then just
1227 record the underlying _DECL node. */
1228 VEC_safe_push (tree
, heap
, block_defs_stack
, currdef
? currdef
: sym
);
1230 /* Set the current reaching definition for SYM to be DEF. */
1231 set_current_def (sym
, def
);
1235 /* Perform a depth-first traversal of the dominator tree looking for
1236 variables to rename. BB is the block where to start searching.
1237 Renaming is a five step process:
1239 1- Every definition made by PHI nodes at the start of the blocks is
1240 registered as the current definition for the corresponding variable.
1242 2- Every statement in BB is rewritten. USE and VUSE operands are
1243 rewritten with their corresponding reaching definition. DEF and
1244 VDEF targets are registered as new definitions.
1246 3- All the PHI nodes in successor blocks of BB are visited. The
1247 argument corresponding to BB is replaced with its current reaching
1250 4- Recursively rewrite every dominator child block of BB.
1252 5- Restore (in reverse order) the current reaching definition for every
1253 new definition introduced in this block. This is done so that when
1254 we return from the recursive call, all the current reaching
1255 definitions are restored to the names that were valid in the
1256 dominator parent of BB. */
1258 /* Return the current definition for variable VAR. If none is found,
1259 create a new SSA name to act as the zeroth definition for VAR. */
1262 get_reaching_def (tree var
)
1266 /* Lookup the current reaching definition for VAR. */
1267 currdef
= get_current_def (var
);
1269 /* If there is no reaching definition for VAR, create and register a
1270 default definition for it (if needed). */
1271 if (currdef
== NULL_TREE
)
1273 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1274 currdef
= get_default_def_for (sym
);
1275 set_current_def (var
, currdef
);
1278 /* Return the current reaching definition for VAR, or the default
1279 definition, if we had to create one. */
1284 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1285 the block with its immediate reaching definitions. Update the current
1286 definition of a variable when a new real or virtual definition is found. */
1289 rewrite_stmt (gimple_stmt_iterator si
)
1291 use_operand_p use_p
;
1292 def_operand_p def_p
;
1294 gimple stmt
= gsi_stmt (si
);
1296 /* If mark_def_sites decided that we don't need to rewrite this
1297 statement, ignore it. */
1298 gcc_assert (blocks_to_update
== NULL
);
1299 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1304 fprintf (dump_file
, "Renaming statement ");
1305 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1306 fprintf (dump_file
, "\n");
1309 /* Step 1. Rewrite USES in the statement. */
1310 if (rewrite_uses_p (stmt
))
1311 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1313 tree var
= USE_FROM_PTR (use_p
);
1314 gcc_assert (DECL_P (var
));
1315 SET_USE (use_p
, get_reaching_def (var
));
1318 /* Step 2. Register the statement's DEF operands. */
1319 if (register_defs_p (stmt
))
1320 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_DEF
)
1322 tree var
= DEF_FROM_PTR (def_p
);
1323 tree name
= make_ssa_name (var
, stmt
);
1325 gcc_assert (DECL_P (var
));
1326 SET_DEF (def_p
, name
);
1327 register_new_def (DEF_FROM_PTR (def_p
), var
);
1329 tracked_var
= target_for_debug_bind (var
);
1332 gimple note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1333 gsi_insert_after (&si
, note
, GSI_SAME_STMT
);
1339 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1340 PHI nodes. For every PHI node found, add a new argument containing the
1341 current reaching definition for the variable and the edge through which
1342 that definition is reaching the PHI node. */
1345 rewrite_add_phi_arguments (basic_block bb
)
1350 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1353 gimple_stmt_iterator gsi
;
1355 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1361 phi
= gsi_stmt (gsi
);
1362 currdef
= get_reaching_def (SSA_NAME_VAR (gimple_phi_result (phi
)));
1363 stmt
= SSA_NAME_DEF_STMT (currdef
);
1364 add_phi_arg (phi
, currdef
, e
, gimple_location (stmt
));
1369 /* SSA Rewriting Step 1. Initialization, create a block local stack
1370 of reaching definitions for new SSA names produced in this block
1371 (BLOCK_DEFS). Register new definitions for every PHI node in the
1375 rewrite_enter_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1379 gimple_stmt_iterator gsi
;
1381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1382 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1384 /* Mark the unwind point for this block. */
1385 VEC_safe_push (tree
, heap
, block_defs_stack
, NULL_TREE
);
1387 /* Step 1. Register new definitions for every PHI node in the block.
1388 Conceptually, all the PHI nodes are executed in parallel and each PHI
1389 node introduces a new version for the associated variable. */
1390 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1394 phi
= gsi_stmt (gsi
);
1395 result
= gimple_phi_result (phi
);
1396 gcc_assert (is_gimple_reg (result
));
1397 register_new_def (result
, SSA_NAME_VAR (result
));
1400 /* Step 2. Rewrite every variable used in each statement in the block
1401 with its immediate reaching definitions. Update the current definition
1402 of a variable when a new real or virtual definition is found. */
1403 if (TEST_BIT (interesting_blocks
, bb
->index
))
1404 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1407 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1408 For every PHI node found, add a new argument containing the current
1409 reaching definition for the variable and the edge through which that
1410 definition is reaching the PHI node. */
1411 rewrite_add_phi_arguments (bb
);
1416 /* Called after visiting all the statements in basic block BB and all
1417 of its dominator children. Restore CURRDEFS to its original value. */
1420 rewrite_leave_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1421 basic_block bb ATTRIBUTE_UNUSED
)
1423 /* Restore CURRDEFS to its original state. */
1424 while (VEC_length (tree
, block_defs_stack
) > 0)
1426 tree tmp
= VEC_pop (tree
, block_defs_stack
);
1427 tree saved_def
, var
;
1429 if (tmp
== NULL_TREE
)
1432 if (TREE_CODE (tmp
) == SSA_NAME
)
1434 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1435 current definition of its underlying variable. Note that
1436 if the SSA_NAME is not for a GIMPLE register, the symbol
1437 being defined is stored in the next slot in the stack.
1438 This mechanism is needed because an SSA name for a
1439 non-register symbol may be the definition for more than
1440 one symbol (e.g., SFTs, aliased variables, etc). */
1442 var
= SSA_NAME_VAR (saved_def
);
1443 if (!is_gimple_reg (var
))
1444 var
= VEC_pop (tree
, block_defs_stack
);
1448 /* If we recorded anything else, it must have been a _DECL
1449 node and its current reaching definition must have been
1455 set_current_def (var
, saved_def
);
1460 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1463 dump_decl_set (FILE *file
, bitmap set
)
1470 fprintf (file
, "{ ");
1472 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
1474 struct tree_decl_minimal in
;
1477 var
= (tree
) htab_find_with_hash (gimple_referenced_vars (cfun
),
1480 print_generic_expr (file
, var
, 0);
1482 fprintf (file
, "D.%u", i
);
1483 fprintf (file
, " ");
1486 fprintf (file
, "}");
1489 fprintf (file
, "NIL");
1493 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1496 debug_decl_set (bitmap set
)
1498 dump_decl_set (stderr
, set
);
1499 fprintf (stderr
, "\n");
1503 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1504 stack up to a maximum of N levels. If N is -1, the whole stack is
1505 dumped. New levels are created when the dominator tree traversal
1506 used for renaming enters a new sub-tree. */
1509 dump_defs_stack (FILE *file
, int n
)
1513 fprintf (file
, "\n\nRenaming stack");
1515 fprintf (file
, " (up to %d levels)", n
);
1516 fprintf (file
, "\n\n");
1519 fprintf (file
, "Level %d (current level)\n", i
);
1520 for (j
= (int) VEC_length (tree
, block_defs_stack
) - 1; j
>= 0; j
--)
1524 name
= VEC_index (tree
, block_defs_stack
, j
);
1525 if (name
== NULL_TREE
)
1530 fprintf (file
, "\nLevel %d\n", i
);
1541 var
= SSA_NAME_VAR (name
);
1542 if (!is_gimple_reg (var
))
1545 var
= VEC_index (tree
, block_defs_stack
, j
);
1549 fprintf (file
, " Previous CURRDEF (");
1550 print_generic_expr (file
, var
, 0);
1551 fprintf (file
, ") = ");
1553 print_generic_expr (file
, name
, 0);
1555 fprintf (file
, "<NIL>");
1556 fprintf (file
, "\n");
1561 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1562 stack up to a maximum of N levels. If N is -1, the whole stack is
1563 dumped. New levels are created when the dominator tree traversal
1564 used for renaming enters a new sub-tree. */
1567 debug_defs_stack (int n
)
1569 dump_defs_stack (stderr
, n
);
1573 /* Dump the current reaching definition of every symbol to FILE. */
1576 dump_currdefs (FILE *file
)
1578 referenced_var_iterator i
;
1581 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1582 FOR_EACH_REFERENCED_VAR (var
, i
)
1583 if (SYMS_TO_RENAME (cfun
) == NULL
1584 || bitmap_bit_p (SYMS_TO_RENAME (cfun
), DECL_UID (var
)))
1586 fprintf (file
, "CURRDEF (");
1587 print_generic_expr (file
, var
, 0);
1588 fprintf (file
, ") = ");
1589 if (get_current_def (var
))
1590 print_generic_expr (file
, get_current_def (var
), 0);
1592 fprintf (file
, "<NIL>");
1593 fprintf (file
, "\n");
1598 /* Dump the current reaching definition of every symbol to stderr. */
1601 debug_currdefs (void)
1603 dump_currdefs (stderr
);
1607 /* Dump SSA information to FILE. */
1610 dump_tree_ssa (FILE *file
)
1612 const char *funcname
1613 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1615 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1617 dump_def_blocks (file
);
1618 dump_defs_stack (file
, -1);
1619 dump_currdefs (file
);
1620 dump_tree_ssa_stats (file
);
1624 /* Dump SSA information to stderr. */
1627 debug_tree_ssa (void)
1629 dump_tree_ssa (stderr
);
1633 /* Dump statistics for the hash table HTAB. */
1636 htab_statistics (FILE *file
, htab_t htab
)
1638 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1639 (long) htab_size (htab
),
1640 (long) htab_elements (htab
),
1641 htab_collisions (htab
));
1645 /* Dump SSA statistics on FILE. */
1648 dump_tree_ssa_stats (FILE *file
)
1650 if (def_blocks
|| repl_tbl
)
1651 fprintf (file
, "\nHash table statistics:\n");
1655 fprintf (file
, " def_blocks: ");
1656 htab_statistics (file
, def_blocks
);
1661 fprintf (file
, " repl_tbl: ");
1662 htab_statistics (file
, repl_tbl
);
1665 if (def_blocks
|| repl_tbl
)
1666 fprintf (file
, "\n");
1670 /* Dump SSA statistics on stderr. */
1673 debug_tree_ssa_stats (void)
1675 dump_tree_ssa_stats (stderr
);
1679 /* Hashing and equality functions for DEF_BLOCKS. */
1682 def_blocks_hash (const void *p
)
1684 return htab_hash_pointer
1685 ((const void *)((const struct def_blocks_d
*)p
)->var
);
1689 def_blocks_eq (const void *p1
, const void *p2
)
1691 return ((const struct def_blocks_d
*)p1
)->var
1692 == ((const struct def_blocks_d
*)p2
)->var
;
1696 /* Free memory allocated by one entry in DEF_BLOCKS. */
1699 def_blocks_free (void *p
)
1701 struct def_blocks_d
*entry
= (struct def_blocks_d
*) p
;
1702 BITMAP_FREE (entry
->def_blocks
);
1703 BITMAP_FREE (entry
->phi_blocks
);
1704 BITMAP_FREE (entry
->livein_blocks
);
1709 /* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
1712 debug_def_blocks_r (void **slot
, void *data
)
1714 FILE *file
= (FILE *) data
;
1715 struct def_blocks_d
*db_p
= (struct def_blocks_d
*) *slot
;
1717 fprintf (file
, "VAR: ");
1718 print_generic_expr (file
, db_p
->var
, dump_flags
);
1719 bitmap_print (file
, db_p
->def_blocks
, ", DEF_BLOCKS: { ", "}");
1720 bitmap_print (file
, db_p
->livein_blocks
, ", LIVEIN_BLOCKS: { ", "}");
1721 bitmap_print (file
, db_p
->phi_blocks
, ", PHI_BLOCKS: { ", "}\n");
1727 /* Dump the DEF_BLOCKS hash table on FILE. */
1730 dump_def_blocks (FILE *file
)
1732 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1734 htab_traverse (def_blocks
, debug_def_blocks_r
, file
);
1738 /* Dump the DEF_BLOCKS hash table on stderr. */
1741 debug_def_blocks (void)
1743 dump_def_blocks (stderr
);
1747 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1750 register_new_update_single (tree new_name
, tree old_name
)
1752 tree currdef
= get_current_def (old_name
);
1754 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1755 This stack is later used by the dominator tree callbacks to
1756 restore the reaching definitions for all the variables
1757 defined in the block after a recursive visit to all its
1758 immediately dominated blocks. */
1759 VEC_reserve (tree
, heap
, block_defs_stack
, 2);
1760 VEC_quick_push (tree
, block_defs_stack
, currdef
);
1761 VEC_quick_push (tree
, block_defs_stack
, old_name
);
1763 /* Set the current reaching definition for OLD_NAME to be
1765 set_current_def (old_name
, new_name
);
1769 /* Register NEW_NAME to be the new reaching definition for all the
1770 names in OLD_NAMES. Used by the incremental SSA update routines to
1771 replace old SSA names with new ones. */
1774 register_new_update_set (tree new_name
, bitmap old_names
)
1779 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1780 register_new_update_single (new_name
, ssa_name (i
));
1785 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1786 it is a symbol marked for renaming, replace it with USE_P's current
1787 reaching definition. */
1790 maybe_replace_use (use_operand_p use_p
)
1792 tree rdef
= NULL_TREE
;
1793 tree use
= USE_FROM_PTR (use_p
);
1794 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1796 if (symbol_marked_for_renaming (sym
))
1797 rdef
= get_reaching_def (sym
);
1798 else if (is_old_name (use
))
1799 rdef
= get_reaching_def (use
);
1801 if (rdef
&& rdef
!= use
)
1802 SET_USE (use_p
, rdef
);
1806 /* Same as maybe_replace_use, but without introducing default stmts,
1807 returning false to indicate a need to do so. */
1810 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1812 tree rdef
= NULL_TREE
;
1813 tree use
= USE_FROM_PTR (use_p
);
1814 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1816 if (symbol_marked_for_renaming (sym
))
1817 rdef
= get_current_def (sym
);
1818 else if (is_old_name (use
))
1820 rdef
= get_current_def (use
);
1821 /* We can't assume that, if there's no current definition, the
1822 default one should be used. It could be the case that we've
1823 rearranged blocks so that the earlier definition no longer
1824 dominates the use. */
1825 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1831 if (rdef
&& rdef
!= use
)
1832 SET_USE (use_p
, rdef
);
1834 return rdef
!= NULL_TREE
;
1838 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1839 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1840 register it as the current definition for the names replaced by
1844 maybe_register_def (def_operand_p def_p
, gimple stmt
,
1845 gimple_stmt_iterator gsi
)
1847 tree def
= DEF_FROM_PTR (def_p
);
1848 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1850 /* If DEF is a naked symbol that needs renaming, create a new
1852 if (symbol_marked_for_renaming (sym
))
1858 def
= make_ssa_name (def
, stmt
);
1859 SET_DEF (def_p
, def
);
1861 tracked_var
= target_for_debug_bind (sym
);
1864 gimple note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1865 /* If stmt ends the bb, insert the debug stmt on the single
1866 non-EH edge from the stmt. */
1867 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1869 basic_block bb
= gsi_bb (gsi
);
1872 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1873 if (!(e
->flags
& EDGE_EH
))
1879 && single_pred_p (ef
->dest
)
1880 && !phi_nodes (ef
->dest
)
1881 && ef
->dest
!= EXIT_BLOCK_PTR
);
1882 gsi_insert_on_edge_immediate (ef
, note
);
1885 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1889 register_new_update_single (def
, sym
);
1893 /* If DEF is a new name, register it as a new definition
1894 for all the names replaced by DEF. */
1895 if (is_new_name (def
))
1896 register_new_update_set (def
, names_replaced_by (def
));
1898 /* If DEF is an old name, register DEF as a new
1899 definition for itself. */
1900 if (is_old_name (def
))
1901 register_new_update_single (def
, def
);
1906 /* Update every variable used in the statement pointed-to by SI. The
1907 statement is assumed to be in SSA form already. Names in
1908 OLD_SSA_NAMES used by SI will be updated to their current reaching
1909 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1910 will be registered as a new definition for their corresponding name
1911 in OLD_SSA_NAMES. */
1914 rewrite_update_stmt (gimple stmt
, gimple_stmt_iterator gsi
)
1916 use_operand_p use_p
;
1917 def_operand_p def_p
;
1920 /* Only update marked statements. */
1921 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1926 fprintf (dump_file
, "Updating SSA information for statement ");
1927 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1928 fprintf (dump_file
, "\n");
1931 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1932 symbol is marked for renaming. */
1933 if (rewrite_uses_p (stmt
))
1935 if (is_gimple_debug (stmt
))
1937 bool failed
= false;
1939 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1940 if (!maybe_replace_use_in_debug_stmt (use_p
))
1948 /* DOM sometimes threads jumps in such a way that a
1949 debug stmt ends up referencing a SSA variable that no
1950 longer dominates the debug stmt, but such that all
1951 incoming definitions refer to the same definition in
1952 an earlier dominator. We could try to recover that
1953 definition somehow, but this will have to do for now.
1955 Introducing a default definition, which is what
1956 maybe_replace_use() would do in such cases, may
1957 modify code generation, for the otherwise-unused
1958 default definition would never go away, modifying SSA
1959 version numbers all over. */
1960 gimple_debug_bind_reset_value (stmt
);
1966 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1967 maybe_replace_use (use_p
);
1971 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1972 Also register definitions for names whose underlying symbol is
1973 marked for renaming. */
1974 if (register_defs_p (stmt
))
1975 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1976 maybe_register_def (def_p
, stmt
, gsi
);
1980 /* Visit all the successor blocks of BB looking for PHI nodes. For
1981 every PHI node found, check if any of its arguments is in
1982 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1983 definition, replace it. */
1986 rewrite_update_phi_arguments (basic_block bb
)
1992 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1997 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
2000 phis
= VEC_index (gimple_vec
, phis_to_rewrite
, e
->dest
->index
);
2001 for (i
= 0; VEC_iterate (gimple
, phis
, i
, phi
); i
++)
2003 tree arg
, lhs_sym
, reaching_def
= NULL
;
2004 use_operand_p arg_p
;
2006 gcc_assert (rewrite_uses_p (phi
));
2008 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
2009 arg
= USE_FROM_PTR (arg_p
);
2011 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
2014 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2016 if (arg
== NULL_TREE
)
2018 /* When updating a PHI node for a recently introduced
2019 symbol we may find NULL arguments. That's why we
2020 take the symbol from the LHS of the PHI node. */
2021 reaching_def
= get_reaching_def (lhs_sym
);
2026 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2028 if (symbol_marked_for_renaming (sym
))
2029 reaching_def
= get_reaching_def (sym
);
2030 else if (is_old_name (arg
))
2031 reaching_def
= get_reaching_def (arg
);
2034 /* Update the argument if there is a reaching def. */
2038 source_location locus
;
2039 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2041 SET_USE (arg_p
, reaching_def
);
2042 stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2044 /* Single element PHI nodes behave like copies, so get the
2045 location from the phi argument. */
2046 if (gimple_code (stmt
) == GIMPLE_PHI
&&
2047 gimple_phi_num_args (stmt
) == 1)
2048 locus
= gimple_phi_arg_location (stmt
, 0);
2050 locus
= gimple_location (stmt
);
2052 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2056 if (e
->flags
& EDGE_ABNORMAL
)
2057 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2063 /* Initialization of block data structures for the incremental SSA
2064 update pass. Create a block local stack of reaching definitions
2065 for new SSA names produced in this block (BLOCK_DEFS). Register
2066 new definitions for every PHI node in the block. */
2069 rewrite_update_enter_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2074 bool is_abnormal_phi
;
2075 gimple_stmt_iterator gsi
;
2077 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2078 fprintf (dump_file
, "\n\nRegistering new PHI nodes in block #%d\n\n",
2081 /* Mark the unwind point for this block. */
2082 VEC_safe_push (tree
, heap
, block_defs_stack
, NULL_TREE
);
2084 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2087 /* Mark the LHS if any of the arguments flows through an abnormal
2089 is_abnormal_phi
= false;
2090 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2091 if (e
->flags
& EDGE_ABNORMAL
)
2093 is_abnormal_phi
= true;
2097 /* If any of the PHI nodes is a replacement for a name in
2098 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2099 register it as a new definition for its corresponding name. Also
2100 register definitions for names whose underlying symbols are
2101 marked for renaming. */
2102 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2105 gimple phi
= gsi_stmt (gsi
);
2107 if (!register_defs_p (phi
))
2110 lhs
= gimple_phi_result (phi
);
2111 lhs_sym
= SSA_NAME_VAR (lhs
);
2113 if (symbol_marked_for_renaming (lhs_sym
))
2114 register_new_update_single (lhs
, lhs_sym
);
2118 /* If LHS is a new name, register a new definition for all
2119 the names replaced by LHS. */
2120 if (is_new_name (lhs
))
2121 register_new_update_set (lhs
, names_replaced_by (lhs
));
2123 /* If LHS is an OLD name, register it as a new definition
2125 if (is_old_name (lhs
))
2126 register_new_update_single (lhs
, lhs
);
2129 if (is_abnormal_phi
)
2130 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2133 /* Step 2. Rewrite every variable used in each statement in the block. */
2134 if (TEST_BIT (interesting_blocks
, bb
->index
))
2136 gcc_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2137 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2138 rewrite_update_stmt (gsi_stmt (gsi
), gsi
);
2141 /* Step 3. Update PHI nodes. */
2142 rewrite_update_phi_arguments (bb
);
2145 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2146 the current reaching definition of every name re-written in BB to
2147 the original reaching definition before visiting BB. This
2148 unwinding must be done in the opposite order to what is done in
2149 register_new_update_set. */
2152 rewrite_update_leave_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2153 basic_block bb ATTRIBUTE_UNUSED
)
2155 while (VEC_length (tree
, block_defs_stack
) > 0)
2157 tree var
= VEC_pop (tree
, block_defs_stack
);
2160 /* NULL indicates the unwind stop point for this block (see
2161 rewrite_update_enter_block). */
2165 saved_def
= VEC_pop (tree
, block_defs_stack
);
2166 set_current_def (var
, saved_def
);
2171 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2174 ENTRY indicates the block where to start. Every block dominated by
2175 ENTRY will be rewritten.
2177 WHAT indicates what actions will be taken by the renamer (see enum
2180 BLOCKS are the set of interesting blocks for the dominator walker
2181 to process. If this set is NULL, then all the nodes dominated
2182 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2183 are not present in BLOCKS are ignored. */
2186 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2188 struct dom_walk_data walk_data
;
2190 /* Rewrite all the basic blocks in the program. */
2191 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2193 /* Setup callbacks for the generic dominator tree walker. */
2194 memset (&walk_data
, 0, sizeof (walk_data
));
2196 walk_data
.dom_direction
= CDI_DOMINATORS
;
2198 if (what
== REWRITE_ALL
)
2200 walk_data
.before_dom_children
= rewrite_enter_block
;
2201 walk_data
.after_dom_children
= rewrite_leave_block
;
2203 else if (what
== REWRITE_UPDATE
)
2205 walk_data
.before_dom_children
= rewrite_update_enter_block
;
2206 walk_data
.after_dom_children
= rewrite_update_leave_block
;
2211 block_defs_stack
= VEC_alloc (tree
, heap
, 10);
2213 /* Initialize the dominator walker. */
2214 init_walk_dominator_tree (&walk_data
);
2216 /* Recursively walk the dominator tree rewriting each statement in
2217 each basic block. */
2218 walk_dominator_tree (&walk_data
, entry
);
2220 /* Finalize the dominator walker. */
2221 fini_walk_dominator_tree (&walk_data
);
2223 /* Debugging dumps. */
2224 if (dump_file
&& (dump_flags
& TDF_STATS
))
2226 dump_dfa_stats (dump_file
);
2228 dump_tree_ssa_stats (dump_file
);
2231 VEC_free (tree
, heap
, block_defs_stack
);
2233 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2237 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2238 at the start of each block, and call mark_def_sites for each statement. */
2241 mark_def_sites_block (struct dom_walk_data
*walk_data
, basic_block bb
)
2243 struct mark_def_sites_global_data
*gd
;
2245 gimple_stmt_iterator gsi
;
2247 gd
= (struct mark_def_sites_global_data
*) walk_data
->global_data
;
2250 bitmap_clear (kills
);
2251 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2252 mark_def_sites (bb
, gsi_stmt (gsi
), kills
);
2256 /* Mark the definition site blocks for each variable, so that we know
2257 where the variable is actually live.
2259 The INTERESTING_BLOCKS global will be filled in with all the blocks
2260 that should be processed by the renamer. It is assumed that the
2261 caller has already initialized and zeroed it. */
2264 mark_def_site_blocks (void)
2266 struct dom_walk_data walk_data
;
2267 struct mark_def_sites_global_data mark_def_sites_global_data
;
2269 /* Setup callbacks for the generic dominator tree walker to find and
2270 mark definition sites. */
2271 walk_data
.dom_direction
= CDI_DOMINATORS
;
2272 walk_data
.initialize_block_local_data
= NULL
;
2273 walk_data
.before_dom_children
= mark_def_sites_block
;
2274 walk_data
.after_dom_children
= NULL
;
2276 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2277 large enough to accommodate all the variables referenced in the
2278 function, not just the ones we are renaming. */
2279 mark_def_sites_global_data
.kills
= BITMAP_ALLOC (NULL
);
2280 walk_data
.global_data
= &mark_def_sites_global_data
;
2282 /* We do not have any local data. */
2283 walk_data
.block_local_data_size
= 0;
2285 /* Initialize the dominator walker. */
2286 init_walk_dominator_tree (&walk_data
);
2288 /* Recursively walk the dominator tree. */
2289 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
2291 /* Finalize the dominator walker. */
2292 fini_walk_dominator_tree (&walk_data
);
2294 /* We no longer need this bitmap, clear and free it. */
2295 BITMAP_FREE (mark_def_sites_global_data
.kills
);
2299 /* Initialize internal data needed during renaming. */
2302 init_ssa_renamer (void)
2305 referenced_var_iterator rvi
;
2307 cfun
->gimple_df
->in_ssa_p
= false;
2309 /* Allocate memory for the DEF_BLOCKS hash table. */
2310 gcc_assert (def_blocks
== NULL
);
2311 def_blocks
= htab_create (num_referenced_vars
, def_blocks_hash
,
2312 def_blocks_eq
, def_blocks_free
);
2314 FOR_EACH_REFERENCED_VAR(var
, rvi
)
2315 set_current_def (var
, NULL_TREE
);
2319 /* Deallocate internal data structures used by the renamer. */
2322 fini_ssa_renamer (void)
2326 htab_delete (def_blocks
);
2330 cfun
->gimple_df
->in_ssa_p
= true;
2333 /* Main entry point into the SSA builder. The renaming process
2334 proceeds in four main phases:
2336 1- Compute dominance frontier and immediate dominators, needed to
2337 insert PHI nodes and rename the function in dominator tree
2340 2- Find and mark all the blocks that define variables
2341 (mark_def_site_blocks).
2343 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2345 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2347 Steps 3 and 4 are done using the dominator tree walker
2348 (walk_dominator_tree). */
2351 rewrite_into_ssa (void)
2356 timevar_push (TV_TREE_SSA_OTHER
);
2358 /* Initialize operand data structures. */
2359 init_ssa_operands ();
2361 /* Initialize internal data needed by the renamer. */
2362 init_ssa_renamer ();
2364 /* Initialize the set of interesting blocks. The callback
2365 mark_def_sites will add to this set those blocks that the renamer
2367 interesting_blocks
= sbitmap_alloc (last_basic_block
);
2368 sbitmap_zero (interesting_blocks
);
2370 /* Initialize dominance frontier. */
2371 dfs
= XNEWVEC (bitmap
, last_basic_block
);
2373 dfs
[bb
->index
] = BITMAP_ALLOC (NULL
);
2375 /* 1- Compute dominance frontiers. */
2376 calculate_dominance_info (CDI_DOMINATORS
);
2377 compute_dominance_frontiers (dfs
);
2379 /* 2- Find and mark definition sites. */
2380 mark_def_site_blocks ();
2382 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2383 insert_phi_nodes (dfs
);
2385 /* 4- Rename all the blocks. */
2386 rewrite_blocks (ENTRY_BLOCK_PTR
, REWRITE_ALL
);
2388 /* Free allocated memory. */
2390 BITMAP_FREE (dfs
[bb
->index
]);
2393 sbitmap_free (interesting_blocks
);
2395 fini_ssa_renamer ();
2397 timevar_pop (TV_TREE_SSA_OTHER
);
2402 struct gimple_opt_pass pass_build_ssa
=
2408 rewrite_into_ssa
, /* execute */
2411 0, /* static_pass_number */
2412 TV_NONE
, /* tv_id */
2413 PROP_cfg
| PROP_referenced_vars
, /* properties_required */
2414 PROP_ssa
, /* properties_provided */
2415 0, /* properties_destroyed */
2416 0, /* todo_flags_start */
2418 | TODO_update_ssa_only_virtuals
2420 | TODO_remove_unused_locals
/* todo_flags_finish */
2425 /* Mark the definition of VAR at STMT and BB as interesting for the
2426 renamer. BLOCKS is the set of blocks that need updating. */
2429 mark_def_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2431 gcc_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2432 set_register_defs (stmt
, true);
2436 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2438 set_def_block (var
, bb
, is_phi_p
);
2440 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2441 site for both itself and all the old names replaced by it. */
2442 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2446 bitmap set
= names_replaced_by (var
);
2448 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2449 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2455 /* Mark the use of VAR at STMT and BB as interesting for the
2456 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2460 mark_use_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2462 basic_block def_bb
= gimple_bb (stmt
);
2464 mark_block_for_update (def_bb
);
2465 mark_block_for_update (bb
);
2467 if (gimple_code (stmt
) == GIMPLE_PHI
)
2468 mark_phi_for_rewrite (def_bb
, stmt
);
2471 set_rewrite_uses (stmt
, true);
2473 if (is_gimple_debug (stmt
))
2477 /* If VAR has not been defined in BB, then it is live-on-entry
2478 to BB. Note that we cannot just use the block holding VAR's
2479 definition because if VAR is one of the names in OLD_SSA_NAMES,
2480 it will have several definitions (itself and all the names that
2484 struct def_blocks_d
*db_p
= get_def_blocks_for (var
);
2485 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2486 set_livein_block (var
, bb
);
2491 /* Do a dominator walk starting at BB processing statements that
2492 reference symbols in SYMS_TO_RENAME. This is very similar to
2493 mark_def_sites, but the scan handles statements whose operands may
2494 already be SSA names.
2496 If INSERT_PHI_P is true, mark those uses as live in the
2497 corresponding block. This is later used by the PHI placement
2498 algorithm to make PHI pruning decisions.
2500 FIXME. Most of this would be unnecessary if we could associate a
2501 symbol to all the SSA names that reference it. But that
2502 sounds like it would be expensive to maintain. Still, it
2503 would be interesting to see if it makes better sense to do
2507 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2510 gimple_stmt_iterator si
;
2514 mark_block_for_update (bb
);
2516 /* Process PHI nodes marking interesting those that define or use
2517 the symbols that we are interested in. */
2518 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
2520 gimple phi
= gsi_stmt (si
);
2521 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2523 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2525 if (!symbol_marked_for_renaming (lhs_sym
))
2528 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2530 /* Mark the uses in phi nodes as interesting. It would be more correct
2531 to process the arguments of the phi nodes of the successor edges of
2532 BB at the end of prepare_block_for_update, however, that turns out
2533 to be significantly more expensive. Doing it here is conservatively
2534 correct -- it may only cause us to believe a value to be live in a
2535 block that also contains its definition, and thus insert a few more
2536 phi nodes for it. */
2537 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2538 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2541 /* Process the statements. */
2542 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2546 use_operand_p use_p
;
2547 def_operand_p def_p
;
2549 stmt
= gsi_stmt (si
);
2551 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_ALL_USES
)
2553 tree use
= USE_FROM_PTR (use_p
);
2554 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2555 if (symbol_marked_for_renaming (sym
))
2556 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2559 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_ALL_DEFS
)
2561 tree def
= DEF_FROM_PTR (def_p
);
2562 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2563 if (symbol_marked_for_renaming (sym
))
2564 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2568 /* Now visit all the blocks dominated by BB. */
2569 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2571 son
= next_dom_son (CDI_DOMINATORS
, son
))
2572 prepare_block_for_update (son
, insert_phi_p
);
2576 /* Helper for prepare_names_to_update. Mark all the use sites for
2577 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2578 prepare_names_to_update. */
2581 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2583 use_operand_p use_p
;
2584 imm_use_iterator iter
;
2586 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2588 gimple stmt
= USE_STMT (use_p
);
2589 basic_block bb
= gimple_bb (stmt
);
2591 if (gimple_code (stmt
) == GIMPLE_PHI
)
2593 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2594 edge e
= gimple_phi_arg_edge (stmt
, ix
);
2595 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2599 /* For regular statements, mark this as an interesting use
2601 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2607 /* Helper for prepare_names_to_update. Mark the definition site for
2608 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2609 prepare_names_to_update. */
2612 prepare_def_site_for (tree name
, bool insert_phi_p
)
2617 gcc_assert (names_to_release
== NULL
2618 || !bitmap_bit_p (names_to_release
, SSA_NAME_VERSION (name
)));
2620 stmt
= SSA_NAME_DEF_STMT (name
);
2621 bb
= gimple_bb (stmt
);
2624 gcc_assert (bb
->index
< last_basic_block
);
2625 mark_block_for_update (bb
);
2626 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2631 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2632 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2633 PHI nodes for newly created names. */
2636 prepare_names_to_update (bool insert_phi_p
)
2640 sbitmap_iterator sbi
;
2642 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2643 remove it from NEW_SSA_NAMES so that we don't try to visit its
2644 defining basic block (which most likely doesn't exist). Notice
2645 that we cannot do the same with names in OLD_SSA_NAMES because we
2646 want to replace existing instances. */
2647 if (names_to_release
)
2648 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2649 RESET_BIT (new_ssa_names
, i
);
2651 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2652 names may be considered to be live-in on blocks that contain
2653 definitions for their replacements. */
2654 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names
, 0, i
, sbi
)
2655 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2657 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2658 OLD_SSA_NAMES, but we have to ignore its definition site. */
2659 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names
, 0, i
, sbi
)
2661 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2662 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2663 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2668 /* Dump all the names replaced by NAME to FILE. */
2671 dump_names_replaced_by (FILE *file
, tree name
)
2677 print_generic_expr (file
, name
, 0);
2678 fprintf (file
, " -> { ");
2680 old_set
= names_replaced_by (name
);
2681 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2683 print_generic_expr (file
, ssa_name (i
), 0);
2684 fprintf (file
, " ");
2687 fprintf (file
, "}\n");
2691 /* Dump all the names replaced by NAME to stderr. */
2694 debug_names_replaced_by (tree name
)
2696 dump_names_replaced_by (stderr
, name
);
2700 /* Dump SSA update information to FILE. */
2703 dump_update_ssa (FILE *file
)
2708 if (!need_ssa_update_p (cfun
))
2711 if (new_ssa_names
&& sbitmap_first_set_bit (new_ssa_names
) >= 0)
2713 sbitmap_iterator sbi
;
2715 fprintf (file
, "\nSSA replacement table\n");
2716 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2717 "O_1, ..., O_j\n\n");
2719 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names
, 0, i
, sbi
)
2720 dump_names_replaced_by (file
, ssa_name (i
));
2722 fprintf (file
, "\n");
2723 fprintf (file
, "Number of virtual NEW -> OLD mappings: %7u\n",
2724 update_ssa_stats
.num_virtual_mappings
);
2725 fprintf (file
, "Number of real NEW -> OLD mappings: %7u\n",
2726 update_ssa_stats
.num_total_mappings
2727 - update_ssa_stats
.num_virtual_mappings
);
2728 fprintf (file
, "Number of total NEW -> OLD mappings: %7u\n",
2729 update_ssa_stats
.num_total_mappings
);
2731 fprintf (file
, "\nNumber of virtual symbols: %u\n",
2732 update_ssa_stats
.num_virtual_symbols
);
2735 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun
)))
2737 fprintf (file
, "\n\nSymbols to be put in SSA form\n\n");
2738 dump_decl_set (file
, SYMS_TO_RENAME (cfun
));
2739 fprintf (file
, "\n");
2742 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2744 fprintf (file
, "\n\nSSA names to release after updating the SSA web\n\n");
2745 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2747 print_generic_expr (file
, ssa_name (i
), 0);
2748 fprintf (file
, " ");
2752 fprintf (file
, "\n\n");
2756 /* Dump SSA update information to stderr. */
2759 debug_update_ssa (void)
2761 dump_update_ssa (stderr
);
2765 /* Initialize data structures used for incremental SSA updates. */
2768 init_update_ssa (struct function
*fn
)
2770 /* Reserve more space than the current number of names. The calls to
2771 add_new_name_mapping are typically done after creating new SSA
2772 names, so we'll need to reallocate these arrays. */
2773 old_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2774 sbitmap_zero (old_ssa_names
);
2776 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2777 sbitmap_zero (new_ssa_names
);
2779 repl_tbl
= htab_create (20, repl_map_hash
, repl_map_eq
, repl_map_free
);
2780 names_to_release
= NULL
;
2781 memset (&update_ssa_stats
, 0, sizeof (update_ssa_stats
));
2782 update_ssa_stats
.virtual_symbols
= BITMAP_ALLOC (NULL
);
2783 update_ssa_initialized_fn
= fn
;
2787 /* Deallocate data structures used for incremental SSA updates. */
2790 delete_update_ssa (void)
2795 sbitmap_free (old_ssa_names
);
2796 old_ssa_names
= NULL
;
2798 sbitmap_free (new_ssa_names
);
2799 new_ssa_names
= NULL
;
2801 htab_delete (repl_tbl
);
2804 bitmap_clear (SYMS_TO_RENAME (update_ssa_initialized_fn
));
2805 BITMAP_FREE (update_ssa_stats
.virtual_symbols
);
2807 if (names_to_release
)
2809 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2810 release_ssa_name (ssa_name (i
));
2811 BITMAP_FREE (names_to_release
);
2814 clear_ssa_name_info ();
2816 fini_ssa_renamer ();
2818 if (blocks_with_phis_to_rewrite
)
2819 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2821 gimple_vec phis
= VEC_index (gimple_vec
, phis_to_rewrite
, i
);
2823 VEC_free (gimple
, heap
, phis
);
2824 VEC_replace (gimple_vec
, phis_to_rewrite
, i
, NULL
);
2827 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2828 BITMAP_FREE (blocks_to_update
);
2829 update_ssa_initialized_fn
= NULL
;
2833 /* Create a new name for OLD_NAME in statement STMT and replace the
2834 operand pointed to by DEF_P with the newly created name. Return
2835 the new name and register the replacement mapping <NEW, OLD> in
2836 update_ssa's tables. */
2839 create_new_def_for (tree old_name
, gimple stmt
, def_operand_p def
)
2841 tree new_name
= duplicate_ssa_name (old_name
, stmt
);
2843 SET_DEF (def
, new_name
);
2845 if (gimple_code (stmt
) == GIMPLE_PHI
)
2849 basic_block bb
= gimple_bb (stmt
);
2851 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2852 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2853 if (e
->flags
& EDGE_ABNORMAL
)
2855 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = 1;
2860 register_new_name_mapping (new_name
, old_name
);
2862 /* For the benefit of passes that will be updating the SSA form on
2863 their own, set the current reaching definition of OLD_NAME to be
2865 set_current_def (old_name
, new_name
);
2871 /* Register name NEW to be a replacement for name OLD. This function
2872 must be called for every replacement that should be performed by
2876 register_new_name_mapping (tree new_tree
, tree old
)
2878 if (!update_ssa_initialized_fn
)
2879 init_update_ssa (cfun
);
2881 gcc_assert (update_ssa_initialized_fn
== cfun
);
2883 add_new_name_mapping (new_tree
, old
);
2887 /* Register symbol SYM to be renamed by update_ssa. */
2890 mark_sym_for_renaming (tree sym
)
2892 bitmap_set_bit (SYMS_TO_RENAME (cfun
), DECL_UID (sym
));
2896 /* Register all the symbols in SET to be renamed by update_ssa. */
2899 mark_set_for_renaming (bitmap set
)
2904 if (set
== NULL
|| bitmap_empty_p (set
))
2907 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2908 mark_sym_for_renaming (referenced_var (i
));
2912 /* Return true if there is any work to be done by update_ssa
2916 need_ssa_update_p (struct function
*fn
)
2918 gcc_assert (fn
!= NULL
);
2919 return (update_ssa_initialized_fn
== fn
2921 && !bitmap_empty_p (SYMS_TO_RENAME (fn
))));
2924 /* Return true if SSA name mappings have been registered for SSA updating. */
2927 name_mappings_registered_p (void)
2929 if (!update_ssa_initialized_fn
)
2932 gcc_assert (update_ssa_initialized_fn
== cfun
);
2934 return repl_tbl
&& htab_elements (repl_tbl
) > 0;
2937 /* Return true if name N has been registered in the replacement table. */
2940 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
2942 if (!update_ssa_initialized_fn
)
2945 gcc_assert (update_ssa_initialized_fn
== cfun
);
2947 return is_new_name (n
) || is_old_name (n
);
2951 /* Return the set of all the SSA names marked to be replaced. */
2954 ssa_names_to_replace (void)
2958 sbitmap_iterator sbi
;
2960 gcc_assert (update_ssa_initialized_fn
== NULL
2961 || update_ssa_initialized_fn
== cfun
);
2963 ret
= BITMAP_ALLOC (NULL
);
2964 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names
, 0, i
, sbi
)
2965 bitmap_set_bit (ret
, i
);
2971 /* Mark NAME to be released after update_ssa has finished. */
2974 release_ssa_name_after_update_ssa (tree name
)
2976 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
2978 if (names_to_release
== NULL
)
2979 names_to_release
= BITMAP_ALLOC (NULL
);
2981 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
2985 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2986 frontier information. BLOCKS is the set of blocks to be updated.
2988 This is slightly different than the regular PHI insertion
2989 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2990 real names (i.e., GIMPLE registers) are inserted:
2992 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2993 nodes inside the region affected by the block that defines VAR
2994 and the blocks that define all its replacements. All these
2995 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2997 First, we compute the entry point to the region (ENTRY). This is
2998 given by the nearest common dominator to all the definition
2999 blocks. When computing the iterated dominance frontier (IDF), any
3000 block not strictly dominated by ENTRY is ignored.
3002 We then call the standard PHI insertion algorithm with the pruned
3005 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3006 names is not pruned. PHI nodes are inserted at every IDF block. */
3009 insert_updated_phi_nodes_for (tree var
, bitmap
*dfs
, bitmap blocks
,
3010 unsigned update_flags
)
3013 struct def_blocks_d
*db
;
3014 bitmap idf
, pruned_idf
;
3018 #if defined ENABLE_CHECKING
3019 if (TREE_CODE (var
) == SSA_NAME
)
3020 gcc_assert (is_old_name (var
));
3022 gcc_assert (symbol_marked_for_renaming (var
));
3025 /* Get all the definition sites for VAR. */
3026 db
= find_def_blocks_for (var
);
3028 /* No need to do anything if there were no definitions to VAR. */
3029 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
3032 /* Compute the initial iterated dominance frontier. */
3033 idf
= compute_idf (db
->def_blocks
, dfs
);
3034 pruned_idf
= BITMAP_ALLOC (NULL
);
3036 if (TREE_CODE (var
) == SSA_NAME
)
3038 if (update_flags
== TODO_update_ssa
)
3040 /* If doing regular SSA updates for GIMPLE registers, we are
3041 only interested in IDF blocks dominated by the nearest
3042 common dominator of all the definition blocks. */
3043 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3045 if (entry
!= ENTRY_BLOCK_PTR
)
3046 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
3047 if (BASIC_BLOCK (i
) != entry
3048 && dominated_by_p (CDI_DOMINATORS
, BASIC_BLOCK (i
), entry
))
3049 bitmap_set_bit (pruned_idf
, i
);
3053 /* Otherwise, do not prune the IDF for VAR. */
3054 gcc_assert (update_flags
== TODO_update_ssa_full_phi
);
3055 bitmap_copy (pruned_idf
, idf
);
3060 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3061 for the first time, so we need to compute the full IDF for
3063 bitmap_copy (pruned_idf
, idf
);
3066 if (!bitmap_empty_p (pruned_idf
))
3068 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3069 are included in the region to be updated. The feeding blocks
3070 are important to guarantee that the PHI arguments are renamed
3073 /* FIXME, this is not needed if we are updating symbols. We are
3074 already starting at the ENTRY block anyway. */
3075 bitmap_ior_into (blocks
, pruned_idf
);
3076 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3080 basic_block bb
= BASIC_BLOCK (i
);
3082 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3083 if (e
->src
->index
>= 0)
3084 bitmap_set_bit (blocks
, e
->src
->index
);
3087 insert_phi_nodes_for (var
, pruned_idf
, true);
3090 BITMAP_FREE (pruned_idf
);
3095 /* Heuristic to determine whether SSA name mappings for virtual names
3096 should be discarded and their symbols rewritten from scratch. When
3097 there is a large number of mappings for virtual names, the
3098 insertion of PHI nodes for the old names in the mappings takes
3099 considerable more time than if we inserted PHI nodes for the
3102 Currently the heuristic takes these stats into account:
3104 - Number of mappings for virtual SSA names.
3105 - Number of distinct virtual symbols involved in those mappings.
3107 If the number of virtual mappings is much larger than the number of
3108 virtual symbols, then it will be faster to compute PHI insertion
3109 spots for the symbols. Even if this involves traversing the whole
3110 CFG, which is what happens when symbols are renamed from scratch. */
3113 switch_virtuals_to_full_rewrite_p (void)
3115 if (update_ssa_stats
.num_virtual_mappings
< (unsigned) MIN_VIRTUAL_MAPPINGS
)
3118 if (update_ssa_stats
.num_virtual_mappings
3119 > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
3120 * update_ssa_stats
.num_virtual_symbols
)
3127 /* Remove every virtual mapping and mark all the affected virtual
3128 symbols for renaming. */
3131 switch_virtuals_to_full_rewrite (void)
3134 sbitmap_iterator sbi
;
3138 fprintf (dump_file
, "\nEnabled virtual name mapping heuristic.\n");
3139 fprintf (dump_file
, "\tNumber of virtual mappings: %7u\n",
3140 update_ssa_stats
.num_virtual_mappings
);
3141 fprintf (dump_file
, "\tNumber of unique virtual symbols: %7u\n",
3142 update_ssa_stats
.num_virtual_symbols
);
3143 fprintf (dump_file
, "Updating FUD-chains from top of CFG will be "
3144 "faster than processing\nthe name mappings.\n\n");
3147 /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
3148 Note that it is not really necessary to remove the mappings from
3149 REPL_TBL, that would only waste time. */
3150 EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names
, 0, i
, sbi
)
3151 if (!is_gimple_reg (ssa_name (i
)))
3152 RESET_BIT (new_ssa_names
, i
);
3154 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names
, 0, i
, sbi
)
3155 if (!is_gimple_reg (ssa_name (i
)))
3156 RESET_BIT (old_ssa_names
, i
);
3158 mark_set_for_renaming (update_ssa_stats
.virtual_symbols
);
3162 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3163 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3165 1- The names in OLD_SSA_NAMES dominated by the definitions of
3166 NEW_SSA_NAMES are all re-written to be reached by the
3167 appropriate definition from NEW_SSA_NAMES.
3169 2- If needed, new PHI nodes are added to the iterated dominance
3170 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3172 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3173 calling register_new_name_mapping for every pair of names that the
3174 caller wants to replace.
3176 The caller identifies the new names that have been inserted and the
3177 names that need to be replaced by calling register_new_name_mapping
3178 for every pair <NEW, OLD>. Note that the function assumes that the
3179 new names have already been inserted in the IL.
3181 For instance, given the following code:
3184 2 x_1 = PHI (0, x_5)
3195 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3198 2 x_1 = PHI (0, x_5)
3211 We want to replace all the uses of x_1 with the new definitions of
3212 x_10 and x_11. Note that the only uses that should be replaced are
3213 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3214 *not* be replaced (this is why we cannot just mark symbol 'x' for
3217 Additionally, we may need to insert a PHI node at line 11 because
3218 that is a merge point for x_10 and x_11. So the use of x_1 at line
3219 11 will be replaced with the new PHI node. The insertion of PHI
3220 nodes is optional. They are not strictly necessary to preserve the
3221 SSA form, and depending on what the caller inserted, they may not
3222 even be useful for the optimizers. UPDATE_FLAGS controls various
3223 aspects of how update_ssa operates, see the documentation for
3224 TODO_update_ssa*. */
3227 update_ssa (unsigned update_flags
)
3229 basic_block bb
, start_bb
;
3233 sbitmap_iterator sbi
;
3235 if (!need_ssa_update_p (cfun
))
3238 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3240 if (!update_ssa_initialized_fn
)
3241 init_update_ssa (cfun
);
3242 gcc_assert (update_ssa_initialized_fn
== cfun
);
3244 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3245 if (!phis_to_rewrite
)
3246 phis_to_rewrite
= VEC_alloc (gimple_vec
, heap
, last_basic_block
);
3247 blocks_to_update
= BITMAP_ALLOC (NULL
);
3249 /* Ensure that the dominance information is up-to-date. */
3250 calculate_dominance_info (CDI_DOMINATORS
);
3252 /* Only one update flag should be set. */
3253 gcc_assert (update_flags
== TODO_update_ssa
3254 || update_flags
== TODO_update_ssa_no_phi
3255 || update_flags
== TODO_update_ssa_full_phi
3256 || update_flags
== TODO_update_ssa_only_virtuals
);
3258 /* If we only need to update virtuals, remove all the mappings for
3259 real names before proceeding. The caller is responsible for
3260 having dealt with the name mappings before calling update_ssa. */
3261 if (update_flags
== TODO_update_ssa_only_virtuals
)
3263 sbitmap_zero (old_ssa_names
);
3264 sbitmap_zero (new_ssa_names
);
3265 htab_empty (repl_tbl
);
3268 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3272 /* If the caller requested PHI nodes to be added, initialize
3273 live-in information data structures (DEF_BLOCKS). */
3275 /* For each SSA name N, the DEF_BLOCKS table describes where the
3276 name is defined, which blocks have PHI nodes for N, and which
3277 blocks have uses of N (i.e., N is live-on-entry in those
3279 def_blocks
= htab_create (num_ssa_names
, def_blocks_hash
,
3280 def_blocks_eq
, def_blocks_free
);
3287 /* Heuristic to avoid massive slow downs when the replacement
3288 mappings include lots of virtual names. */
3289 if (insert_phi_p
&& switch_virtuals_to_full_rewrite_p ())
3290 switch_virtuals_to_full_rewrite ();
3292 /* If there are names defined in the replacement table, prepare
3293 definition and use sites for all the names in NEW_SSA_NAMES and
3295 if (sbitmap_first_set_bit (new_ssa_names
) >= 0)
3297 prepare_names_to_update (insert_phi_p
);
3299 /* If all the names in NEW_SSA_NAMES had been marked for
3300 removal, and there are no symbols to rename, then there's
3301 nothing else to do. */
3302 if (sbitmap_first_set_bit (new_ssa_names
) < 0
3303 && bitmap_empty_p (SYMS_TO_RENAME (cfun
)))
3307 /* Next, determine the block at which to start the renaming process. */
3308 if (!bitmap_empty_p (SYMS_TO_RENAME (cfun
)))
3310 /* If we have to rename some symbols from scratch, we need to
3311 start the process at the root of the CFG. FIXME, it should
3312 be possible to determine the nearest block that had a
3313 definition for each of the symbols that are marked for
3314 updating. For now this seems more work than it's worth. */
3315 start_bb
= ENTRY_BLOCK_PTR
;
3317 /* Traverse the CFG looking for existing definitions and uses of
3318 symbols in SYMS_TO_RENAME. Mark interesting blocks and
3319 statements and set local live-in information for the PHI
3320 placement heuristics. */
3321 prepare_block_for_update (start_bb
, insert_phi_p
);
3325 /* Otherwise, the entry block to the region is the nearest
3326 common dominator for the blocks in BLOCKS. */
3327 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3331 /* If requested, insert PHI nodes at the iterated dominance frontier
3332 of every block, creating new definitions for names in OLD_SSA_NAMES
3333 and for symbols in SYMS_TO_RENAME. */
3338 /* If the caller requested PHI nodes to be added, compute
3339 dominance frontiers. */
3340 dfs
= XNEWVEC (bitmap
, last_basic_block
);
3342 dfs
[bb
->index
] = BITMAP_ALLOC (NULL
);
3343 compute_dominance_frontiers (dfs
);
3345 if (sbitmap_first_set_bit (old_ssa_names
) >= 0)
3347 sbitmap_iterator sbi
;
3349 /* insert_update_phi_nodes_for will call add_new_name_mapping
3350 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3351 will grow while we are traversing it (but it will not
3352 gain any new members). Copy OLD_SSA_NAMES to a temporary
3354 sbitmap tmp
= sbitmap_alloc (old_ssa_names
->n_bits
);
3355 sbitmap_copy (tmp
, old_ssa_names
);
3356 EXECUTE_IF_SET_IN_SBITMAP (tmp
, 0, i
, sbi
)
3357 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3362 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun
), 0, i
, bi
)
3363 insert_updated_phi_nodes_for (referenced_var (i
), dfs
, blocks_to_update
,
3367 BITMAP_FREE (dfs
[bb
->index
]);
3370 /* Insertion of PHI nodes may have added blocks to the region.
3371 We need to re-compute START_BB to include the newly added
3373 if (start_bb
!= ENTRY_BLOCK_PTR
)
3374 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3378 /* Reset the current definition for name and symbol before renaming
3380 EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names
, 0, i
, sbi
)
3381 set_current_def (ssa_name (i
), NULL_TREE
);
3383 EXECUTE_IF_SET_IN_BITMAP (SYMS_TO_RENAME (cfun
), 0, i
, bi
)
3384 set_current_def (referenced_var (i
), NULL_TREE
);
3386 /* Now start the renaming process at START_BB. */
3387 interesting_blocks
= sbitmap_alloc (last_basic_block
);
3388 sbitmap_zero (interesting_blocks
);
3389 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3390 SET_BIT (interesting_blocks
, i
);
3392 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3394 sbitmap_free (interesting_blocks
);
3396 /* Debugging dumps. */
3402 dump_update_ssa (dump_file
);
3404 fprintf (dump_file
, "Incremental SSA update started at block: %d\n\n",
3408 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3410 fprintf (dump_file
, "Number of blocks in CFG: %d\n", last_basic_block
);
3411 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n\n",
3412 c
, PERCENT (c
, last_basic_block
));
3414 if (dump_flags
& TDF_DETAILS
)
3416 fprintf (dump_file
, "Affected blocks: ");
3417 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3418 fprintf (dump_file
, "%u ", i
);
3419 fprintf (dump_file
, "\n");
3422 fprintf (dump_file
, "\n\n");
3425 /* Free allocated memory. */
3427 delete_update_ssa ();
3429 timevar_pop (TV_TREE_SSA_INCREMENTAL
);