1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "langhooks.h"
29 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
32 #include "hash-table.h"
33 #include "tree-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "tree-into-ssa.h"
49 #include "tree-inline.h"
50 #include "tree-pass.h"
54 #include "diagnostic-core.h"
55 #include "tree-into-ssa.h"
57 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
59 /* This file builds the SSA form for a function as described in:
60 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
61 Computing Static Single Assignment Form and the Control Dependence
62 Graph. ACM Transactions on Programming Languages and Systems,
63 13(4):451-490, October 1991. */
65 /* Structure to map a variable VAR to the set of blocks that contain
66 definitions for VAR. */
69 /* Blocks that contain definitions of VAR. Bit I will be set if the
70 Ith block contains a definition of VAR. */
73 /* Blocks that contain a PHI node for VAR. */
76 /* Blocks where VAR is live-on-entry. Similar semantics as
81 typedef struct def_blocks_d
*def_blocks_p
;
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
> 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 static 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 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
119 the to basic block with index I. Allocated once per compilation, *not*
120 released between different functions. */
121 static vec
<gimple_vec
> phis_to_rewrite
;
123 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
124 static bitmap blocks_with_phis_to_rewrite
;
126 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
127 to grow as the callers to create_new_def_for will create new names on
129 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
130 need to find a reasonable growth strategy. */
131 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
134 /* The function the SSA updating data structures have been initialized for.
135 NULL if they need to be initialized by create_new_def_for. */
136 static struct function
*update_ssa_initialized_fn
= NULL
;
138 /* Global data to attach to the main dominator walk structure. */
139 struct mark_def_sites_global_data
141 /* This bitmap contains the variables which are set before they
142 are used in a basic block. */
146 /* It is advantageous to avoid things like life analysis for variables which
147 do not need PHI nodes. This enum describes whether or not a particular
148 variable may need a PHI node. */
150 enum need_phi_state
{
151 /* This is the default. If we are still in this state after finding
152 all the definition and use sites, then we will assume the variable
153 needs PHI nodes. This is probably an overly conservative assumption. */
154 NEED_PHI_STATE_UNKNOWN
,
156 /* This state indicates that we have seen one or more sets of the
157 variable in a single basic block and that the sets dominate all
158 uses seen so far. If after finding all definition and use sites
159 we are still in this state, then the variable does not need any
163 /* This state indicates that we have either seen multiple definitions of
164 the variable in multiple blocks, or that we encountered a use in a
165 block that was not dominated by the block containing the set(s) of
166 this variable. This variable is assumed to need PHI nodes. */
170 /* Information stored for both SSA names and decls. */
173 /* This field indicates whether or not the variable may need PHI nodes.
174 See the enum's definition for more detailed information about the
176 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
178 /* The current reaching definition replacing this var. */
181 /* Definitions for this var. */
182 struct def_blocks_d def_blocks
;
185 /* The information associated with decls and SSA names. */
186 typedef struct common_info_d
*common_info_p
;
188 /* Information stored for decls. */
194 /* Information stored for both SSA names and decls. */
195 struct common_info_d info
;
198 /* The information associated with decls. */
199 typedef struct var_info_d
*var_info_p
;
202 /* VAR_INFOS hashtable helpers. */
204 struct var_info_hasher
: typed_free_remove
<var_info_d
>
206 typedef var_info_d value_type
;
207 typedef var_info_d compare_type
;
208 static inline hashval_t
hash (const value_type
*);
209 static inline bool equal (const value_type
*, const compare_type
*);
213 var_info_hasher::hash (const value_type
*p
)
215 return DECL_UID (p
->var
);
219 var_info_hasher::equal (const value_type
*p1
, const compare_type
*p2
)
221 return p1
->var
== p2
->var
;
225 /* Each entry in VAR_INFOS contains an element of type STRUCT
227 static hash_table
<var_info_hasher
> var_infos
;
230 /* Information stored for SSA names. */
233 /* Age of this record (so that info_for_ssa_name table can be cleared
234 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
235 are assumed to be null. */
238 /* Replacement mappings, allocated from update_ssa_obstack. */
241 /* Information stored for both SSA names and decls. */
242 struct common_info_d info
;
245 /* The information associated with names. */
246 typedef struct ssa_name_info
*ssa_name_info_p
;
248 static vec
<ssa_name_info_p
> info_for_ssa_name
;
249 static unsigned current_info_for_ssa_name_age
;
251 static bitmap_obstack update_ssa_obstack
;
253 /* The set of blocks affected by update_ssa. */
254 static bitmap blocks_to_update
;
256 /* The main entry point to the SSA renamer (rewrite_blocks) may be
257 called several times to do different, but related, tasks.
258 Initially, we need it to rename the whole program into SSA form.
259 At other times, we may need it to only rename into SSA newly
260 exposed symbols. Finally, we can also call it to incrementally fix
261 an already built SSA web. */
263 /* Convert the whole function into SSA form. */
266 /* Incrementally update the SSA web by replacing existing SSA
267 names with new ones. See update_ssa for details. */
271 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
272 static bitmap symbols_to_rename_set
;
273 static vec
<tree
> symbols_to_rename
;
275 /* Mark SYM for renaming. */
278 mark_for_renaming (tree sym
)
280 if (!symbols_to_rename_set
)
281 symbols_to_rename_set
= BITMAP_ALLOC (NULL
);
282 if (bitmap_set_bit (symbols_to_rename_set
, DECL_UID (sym
)))
283 symbols_to_rename
.safe_push (sym
);
286 /* Return true if SYM is marked for renaming. */
289 marked_for_renaming (tree sym
)
291 if (!symbols_to_rename_set
|| sym
== NULL_TREE
)
293 return bitmap_bit_p (symbols_to_rename_set
, DECL_UID (sym
));
297 /* Return true if STMT needs to be rewritten. When renaming a subset
298 of the variables, not all statements will be processed. This is
299 decided in mark_def_sites. */
302 rewrite_uses_p (gimple stmt
)
304 return gimple_visited_p (stmt
);
308 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
311 set_rewrite_uses (gimple stmt
, bool rewrite_p
)
313 gimple_set_visited (stmt
, rewrite_p
);
317 /* Return true if the DEFs created by statement STMT should be
318 registered when marking new definition sites. This is slightly
319 different than rewrite_uses_p: it's used by update_ssa to
320 distinguish statements that need to have both uses and defs
321 processed from those that only need to have their defs processed.
322 Statements that define new SSA names only need to have their defs
323 registered, but they don't need to have their uses renamed. */
326 register_defs_p (gimple stmt
)
328 return gimple_plf (stmt
, GF_PLF_1
) != 0;
332 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
335 set_register_defs (gimple stmt
, bool register_defs_p
)
337 gimple_set_plf (stmt
, GF_PLF_1
, register_defs_p
);
341 /* Get the information associated with NAME. */
343 static inline ssa_name_info_p
344 get_ssa_name_ann (tree name
)
346 unsigned ver
= SSA_NAME_VERSION (name
);
347 unsigned len
= info_for_ssa_name
.length ();
348 struct ssa_name_info
*info
;
350 /* Re-allocate the vector at most once per update/into-SSA. */
352 info_for_ssa_name
.safe_grow_cleared (num_ssa_names
);
354 /* But allocate infos lazily. */
355 info
= info_for_ssa_name
[ver
];
358 info
= XCNEW (struct ssa_name_info
);
359 info
->age
= current_info_for_ssa_name_age
;
360 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
361 info_for_ssa_name
[ver
] = info
;
364 if (info
->age
< current_info_for_ssa_name_age
)
366 info
->age
= current_info_for_ssa_name_age
;
367 info
->repl_set
= NULL
;
368 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
369 info
->info
.current_def
= NULL_TREE
;
370 info
->info
.def_blocks
.def_blocks
= NULL
;
371 info
->info
.def_blocks
.phi_blocks
= NULL
;
372 info
->info
.def_blocks
.livein_blocks
= NULL
;
378 /* Return and allocate the auxiliar information for DECL. */
380 static inline var_info_p
381 get_var_info (tree decl
)
383 struct var_info_d vi
;
386 slot
= var_infos
.find_slot_with_hash (&vi
, DECL_UID (decl
), INSERT
);
389 var_info_p v
= XCNEW (struct var_info_d
);
398 /* Clears info for SSA names. */
401 clear_ssa_name_info (void)
403 current_info_for_ssa_name_age
++;
405 /* If current_info_for_ssa_name_age wraps we use stale information.
406 Asser that this does not happen. */
407 gcc_assert (current_info_for_ssa_name_age
!= 0);
411 /* Get access to the auxiliar information stored per SSA name or decl. */
413 static inline common_info_p
414 get_common_info (tree var
)
416 if (TREE_CODE (var
) == SSA_NAME
)
417 return &get_ssa_name_ann (var
)->info
;
419 return &get_var_info (var
)->info
;
423 /* Return the current definition for VAR. */
426 get_current_def (tree var
)
428 return get_common_info (var
)->current_def
;
432 /* Sets current definition of VAR to DEF. */
435 set_current_def (tree var
, tree def
)
437 get_common_info (var
)->current_def
= def
;
440 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
441 all statements in basic block BB. */
444 initialize_flags_in_bb (basic_block bb
)
447 gimple_stmt_iterator gsi
;
449 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
451 gimple phi
= gsi_stmt (gsi
);
452 set_rewrite_uses (phi
, false);
453 set_register_defs (phi
, false);
456 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
458 stmt
= gsi_stmt (gsi
);
460 /* We are going to use the operand cache API, such as
461 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
462 cache for each statement should be up-to-date. */
463 gcc_checking_assert (!gimple_modified_p (stmt
));
464 set_rewrite_uses (stmt
, false);
465 set_register_defs (stmt
, false);
469 /* Mark block BB as interesting for update_ssa. */
472 mark_block_for_update (basic_block bb
)
474 gcc_checking_assert (blocks_to_update
!= NULL
);
475 if (!bitmap_set_bit (blocks_to_update
, bb
->index
))
477 initialize_flags_in_bb (bb
);
480 /* Return the set of blocks where variable VAR is defined and the blocks
481 where VAR is live on entry (livein). If no entry is found in
482 DEF_BLOCKS, a new one is created and returned. */
484 static inline struct def_blocks_d
*
485 get_def_blocks_for (common_info_p info
)
487 struct def_blocks_d
*db_p
= &info
->def_blocks
;
488 if (!db_p
->def_blocks
)
490 db_p
->def_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
491 db_p
->phi_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
492 db_p
->livein_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
499 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
500 VAR is defined by a PHI node. */
503 set_def_block (tree var
, basic_block bb
, bool phi_p
)
505 struct def_blocks_d
*db_p
;
508 info
= get_common_info (var
);
509 db_p
= get_def_blocks_for (info
);
511 /* Set the bit corresponding to the block where VAR is defined. */
512 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
514 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
516 /* Keep track of whether or not we may need to insert PHI nodes.
518 If we are in the UNKNOWN state, then this is the first definition
519 of VAR. Additionally, we have not seen any uses of VAR yet, so
520 we do not need a PHI node for this variable at this time (i.e.,
521 transition to NEED_PHI_STATE_NO).
523 If we are in any other state, then we either have multiple definitions
524 of this variable occurring in different blocks or we saw a use of the
525 variable which was not dominated by the block containing the
526 definition(s). In this case we may need a PHI node, so enter
527 state NEED_PHI_STATE_MAYBE. */
528 if (info
->need_phi_state
== NEED_PHI_STATE_UNKNOWN
)
529 info
->need_phi_state
= NEED_PHI_STATE_NO
;
531 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
535 /* Mark block BB as having VAR live at the entry to BB. */
538 set_livein_block (tree var
, basic_block bb
)
541 struct def_blocks_d
*db_p
;
543 info
= get_common_info (var
);
544 db_p
= get_def_blocks_for (info
);
546 /* Set the bit corresponding to the block where VAR is live in. */
547 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
549 /* Keep track of whether or not we may need to insert PHI nodes.
551 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
552 by the single block containing the definition(s) of this variable. If
553 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
554 NEED_PHI_STATE_MAYBE. */
555 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
557 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
559 if (def_block_index
== -1
560 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
561 BASIC_BLOCK (def_block_index
)))
562 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
565 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
569 /* Return true if NAME is in OLD_SSA_NAMES. */
572 is_old_name (tree name
)
574 unsigned ver
= SSA_NAME_VERSION (name
);
577 return (ver
< SBITMAP_SIZE (new_ssa_names
)
578 && bitmap_bit_p (old_ssa_names
, ver
));
582 /* Return true if NAME is in NEW_SSA_NAMES. */
585 is_new_name (tree name
)
587 unsigned ver
= SSA_NAME_VERSION (name
);
590 return (ver
< SBITMAP_SIZE (new_ssa_names
)
591 && bitmap_bit_p (new_ssa_names
, ver
));
595 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
598 names_replaced_by (tree new_tree
)
600 return get_ssa_name_ann (new_tree
)->repl_set
;
604 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
607 add_to_repl_tbl (tree new_tree
, tree old
)
609 bitmap
*set
= &get_ssa_name_ann (new_tree
)->repl_set
;
611 *set
= BITMAP_ALLOC (&update_ssa_obstack
);
612 bitmap_set_bit (*set
, SSA_NAME_VERSION (old
));
616 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
617 represents the set of names O_1 ... O_j replaced by N_i. This is
618 used by update_ssa and its helpers to introduce new SSA names in an
619 already formed SSA web. */
622 add_new_name_mapping (tree new_tree
, tree old
)
624 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
625 gcc_checking_assert (new_tree
!= old
626 && SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
628 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
629 caller may have created new names since the set was created. */
630 if (SBITMAP_SIZE (new_ssa_names
) <= num_ssa_names
- 1)
632 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
633 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
634 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
637 /* Update the REPL_TBL table. */
638 add_to_repl_tbl (new_tree
, old
);
640 /* If OLD had already been registered as a new name, then all the
641 names that OLD replaces should also be replaced by NEW_TREE. */
642 if (is_new_name (old
))
643 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
645 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
647 bitmap_set_bit (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
648 bitmap_set_bit (old_ssa_names
, SSA_NAME_VERSION (old
));
652 /* Call back for walk_dominator_tree used to collect definition sites
653 for every variable in the function. For every statement S in block
656 1- Variables defined by S in the DEFS of S are marked in the bitmap
659 2- If S uses a variable VAR and there is no preceding kill of VAR,
660 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
662 This information is used to determine which variables are live
663 across block boundaries to reduce the number of PHI nodes
667 mark_def_sites (basic_block bb
, gimple stmt
, bitmap kills
)
673 /* Since this is the first time that we rewrite the program into SSA
674 form, force an operand scan on every statement. */
677 gcc_checking_assert (blocks_to_update
== NULL
);
678 set_register_defs (stmt
, false);
679 set_rewrite_uses (stmt
, false);
681 if (is_gimple_debug (stmt
))
683 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
685 tree sym
= USE_FROM_PTR (use_p
);
686 gcc_checking_assert (DECL_P (sym
));
687 set_rewrite_uses (stmt
, true);
689 if (rewrite_uses_p (stmt
))
690 bitmap_set_bit (interesting_blocks
, bb
->index
);
694 /* If a variable is used before being set, then the variable is live
695 across a block boundary, so mark it live-on-entry to BB. */
696 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
698 tree sym
= USE_FROM_PTR (use_p
);
699 gcc_checking_assert (DECL_P (sym
));
700 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
701 set_livein_block (sym
, bb
);
702 set_rewrite_uses (stmt
, true);
705 /* Now process the defs. Mark BB as the definition block and add
706 each def to the set of killed symbols. */
707 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
709 gcc_checking_assert (DECL_P (def
));
710 set_def_block (def
, bb
, false);
711 bitmap_set_bit (kills
, DECL_UID (def
));
712 set_register_defs (stmt
, true);
715 /* If we found the statement interesting then also mark the block BB
717 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
718 bitmap_set_bit (interesting_blocks
, bb
->index
);
721 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
722 in the dfs numbering of the dominance tree. */
726 /* Basic block whose index this entry corresponds to. */
729 /* The dfs number of this node. */
733 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
737 cmp_dfsnum (const void *a
, const void *b
)
739 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
740 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
742 return (int) da
->dfs_num
- (int) db
->dfs_num
;
745 /* Among the intervals starting at the N points specified in DEFS, find
746 the one that contains S, and return its bb_index. */
749 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
751 unsigned f
= 0, t
= n
, m
;
756 if (defs
[m
].dfs_num
<= s
)
762 return defs
[f
].bb_index
;
765 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
766 KILLS is a bitmap of blocks where the value is defined before any use. */
769 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
772 unsigned i
, b
, p
, u
, top
;
774 basic_block def_bb
, use_bb
;
778 struct dom_dfsnum
*defs
;
779 unsigned n_defs
, adef
;
781 if (bitmap_empty_p (uses
))
787 /* The phi must dominate a use, or an argument of a live phi. Also, we
788 do not create any phi nodes in def blocks, unless they are also livein. */
789 to_remove
= BITMAP_ALLOC (NULL
);
790 bitmap_and_compl (to_remove
, kills
, uses
);
791 bitmap_and_compl_into (phis
, to_remove
);
792 if (bitmap_empty_p (phis
))
794 BITMAP_FREE (to_remove
);
798 /* We want to remove the unnecessary phi nodes, but we do not want to compute
799 liveness information, as that may be linear in the size of CFG, and if
800 there are lot of different variables to rewrite, this may lead to quadratic
803 Instead, we basically emulate standard dce. We put all uses to worklist,
804 then for each of them find the nearest def that dominates them. If this
805 def is a phi node, we mark it live, and if it was not live before, we
806 add the predecessors of its basic block to the worklist.
808 To quickly locate the nearest def that dominates use, we use dfs numbering
809 of the dominance tree (that is already available in order to speed up
810 queries). For each def, we have the interval given by the dfs number on
811 entry to and on exit from the corresponding subtree in the dominance tree.
812 The nearest dominator for a given use is the smallest of these intervals
813 that contains entry and exit dfs numbers for the basic block with the use.
814 If we store the bounds for all the uses to an array and sort it, we can
815 locate the nearest dominating def in logarithmic time by binary search.*/
816 bitmap_ior (to_remove
, kills
, phis
);
817 n_defs
= bitmap_count_bits (to_remove
);
818 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
819 defs
[0].bb_index
= 1;
822 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
824 def_bb
= BASIC_BLOCK (i
);
825 defs
[adef
].bb_index
= i
;
826 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
827 defs
[adef
+ 1].bb_index
= i
;
828 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
831 BITMAP_FREE (to_remove
);
832 gcc_assert (adef
== 2 * n_defs
+ 1);
833 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
834 gcc_assert (defs
[0].bb_index
== 1);
836 /* Now each DEFS entry contains the number of the basic block to that the
837 dfs number corresponds. Change them to the number of basic block that
838 corresponds to the interval following the dfs number. Also, for the
839 dfs_out numbers, increase the dfs number by one (so that it corresponds
840 to the start of the following interval, not to the end of the current
841 one). We use WORKLIST as a stack. */
842 auto_vec
<int> worklist (n_defs
+ 1);
843 worklist
.quick_push (1);
846 for (i
= 1; i
< adef
; i
++)
848 b
= defs
[i
].bb_index
;
851 /* This is a closing element. Interval corresponding to the top
852 of the stack after removing it follows. */
854 top
= worklist
[worklist
.length () - 1];
855 defs
[n_defs
].bb_index
= top
;
856 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
860 /* Opening element. Nothing to do, just push it to the stack and move
861 it to the correct position. */
862 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
863 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
864 worklist
.quick_push (b
);
868 /* If this interval starts at the same point as the previous one, cancel
870 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
871 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
876 gcc_assert (worklist
.is_empty ());
878 /* Now process the uses. */
879 live_phis
= BITMAP_ALLOC (NULL
);
880 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
882 worklist
.safe_push (i
);
885 while (!worklist
.is_empty ())
888 if (b
== ENTRY_BLOCK
)
891 /* If there is a phi node in USE_BB, it is made live. Otherwise,
892 find the def that dominates the immediate dominator of USE_BB
893 (the kill in USE_BB does not dominate the use). */
894 if (bitmap_bit_p (phis
, b
))
898 use_bb
= get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (b
));
899 p
= find_dfsnum_interval (defs
, n_defs
,
900 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
901 if (!bitmap_bit_p (phis
, p
))
905 /* If the phi node is already live, there is nothing to do. */
906 if (!bitmap_set_bit (live_phis
, p
))
909 /* Add the new uses to the worklist. */
910 def_bb
= BASIC_BLOCK (p
);
911 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
914 if (bitmap_bit_p (uses
, u
))
917 /* In case there is a kill directly in the use block, do not record
918 the use (this is also necessary for correctness, as we assume that
919 uses dominated by a def directly in their block have been filtered
921 if (bitmap_bit_p (kills
, u
))
924 bitmap_set_bit (uses
, u
);
925 worklist
.safe_push (u
);
929 bitmap_copy (phis
, live_phis
);
930 BITMAP_FREE (live_phis
);
934 /* Return the set of blocks where variable VAR is defined and the blocks
935 where VAR is live on entry (livein). Return NULL, if no entry is
936 found in DEF_BLOCKS. */
938 static inline struct def_blocks_d
*
939 find_def_blocks_for (tree var
)
941 def_blocks_p p
= &get_common_info (var
)->def_blocks
;
948 /* Marks phi node PHI in basic block BB for rewrite. */
951 mark_phi_for_rewrite (basic_block bb
, gimple phi
)
954 unsigned n
, idx
= bb
->index
;
956 if (rewrite_uses_p (phi
))
959 set_rewrite_uses (phi
, true);
961 if (!blocks_with_phis_to_rewrite
)
964 bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
);
966 n
= (unsigned) last_basic_block
+ 1;
967 if (phis_to_rewrite
.length () < n
)
968 phis_to_rewrite
.safe_grow_cleared (n
);
970 phis
= phis_to_rewrite
[idx
];
973 phis
.safe_push (phi
);
974 phis_to_rewrite
[idx
] = phis
;
977 /* Insert PHI nodes for variable VAR using the iterated dominance
978 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
979 function assumes that the caller is incrementally updating the
980 existing SSA form, in which case VAR may be an SSA name instead of
983 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
984 PHI node for VAR. On exit, only the nodes that received a PHI node
985 for VAR will be present in PHI_INSERTION_POINTS. */
988 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
995 struct def_blocks_d
*def_map
= find_def_blocks_for (var
);
997 /* Remove the blocks where we already have PHI nodes for VAR. */
998 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
1000 /* Remove obviously useless phi nodes. */
1001 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
1002 def_map
->livein_blocks
);
1004 /* And insert the PHI nodes. */
1005 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
1007 bb
= BASIC_BLOCK (bb_index
);
1009 mark_block_for_update (bb
);
1011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 fprintf (dump_file
, "creating PHI node in block #%d for ", bb_index
);
1014 print_generic_expr (dump_file
, var
, TDF_SLIM
);
1015 fprintf (dump_file
, "\n");
1019 if (TREE_CODE (var
) == SSA_NAME
)
1021 /* If we are rewriting SSA names, create the LHS of the PHI
1022 node by duplicating VAR. This is useful in the case of
1023 pointers, to also duplicate pointer attributes (alias
1024 information, in particular). */
1028 gcc_checking_assert (update_p
);
1029 new_lhs
= duplicate_ssa_name (var
, NULL
);
1030 phi
= create_phi_node (new_lhs
, bb
);
1031 add_new_name_mapping (new_lhs
, var
);
1033 /* Add VAR to every argument slot of PHI. We need VAR in
1034 every argument so that rewrite_update_phi_arguments knows
1035 which name is this PHI node replacing. If VAR is a
1036 symbol marked for renaming, this is not necessary, the
1037 renamer will use the symbol on the LHS to get its
1038 reaching definition. */
1039 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1040 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1046 gcc_checking_assert (DECL_P (var
));
1047 phi
= create_phi_node (var
, bb
);
1049 tracked_var
= target_for_debug_bind (var
);
1052 gimple note
= gimple_build_debug_bind (tracked_var
,
1055 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1056 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1060 /* Mark this PHI node as interesting for update_ssa. */
1061 set_register_defs (phi
, true);
1062 mark_phi_for_rewrite (bb
, phi
);
1066 /* Sort var_infos after DECL_UID of their var. */
1069 insert_phi_nodes_compare_var_infos (const void *a
, const void *b
)
1071 const struct var_info_d
*defa
= *(struct var_info_d
* const *)a
;
1072 const struct var_info_d
*defb
= *(struct var_info_d
* const *)b
;
1073 if (DECL_UID (defa
->var
) < DECL_UID (defb
->var
))
1079 /* Insert PHI nodes at the dominance frontier of blocks with variable
1080 definitions. DFS contains the dominance frontier information for
1084 insert_phi_nodes (bitmap_head
*dfs
)
1086 hash_table
<var_info_hasher
>::iterator hi
;
1090 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1092 auto_vec
<var_info_p
> vars (var_infos
.elements ());
1093 FOR_EACH_HASH_TABLE_ELEMENT (var_infos
, info
, var_info_p
, hi
)
1094 if (info
->info
.need_phi_state
!= NEED_PHI_STATE_NO
)
1095 vars
.quick_push (info
);
1097 /* Do two stages to avoid code generation differences for UID
1098 differences but no UID ordering differences. */
1099 vars
.qsort (insert_phi_nodes_compare_var_infos
);
1101 FOR_EACH_VEC_ELT (vars
, i
, info
)
1103 bitmap idf
= compute_idf (info
->info
.def_blocks
.def_blocks
, dfs
);
1104 insert_phi_nodes_for (info
->var
, idf
, false);
1108 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1112 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1113 register DEF (an SSA_NAME) to be a new definition for SYM. */
1116 register_new_def (tree def
, tree sym
)
1118 common_info_p info
= get_common_info (sym
);
1121 /* If this variable is set in a single basic block and all uses are
1122 dominated by the set(s) in that single basic block, then there is
1123 no reason to record anything for this variable in the block local
1124 definition stacks. Doing so just wastes time and memory.
1126 This is the same test to prune the set of variables which may
1127 need PHI nodes. So we just use that information since it's already
1128 computed and available for us to use. */
1129 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1131 info
->current_def
= def
;
1135 currdef
= info
->current_def
;
1137 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1138 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1139 in the stack so that we know which symbol is being defined by
1140 this SSA name when we unwind the stack. */
1141 if (currdef
&& !is_gimple_reg (sym
))
1142 block_defs_stack
.safe_push (sym
);
1144 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1145 stack is later used by the dominator tree callbacks to restore
1146 the reaching definitions for all the variables defined in the
1147 block after a recursive visit to all its immediately dominated
1148 blocks. If there is no current reaching definition, then just
1149 record the underlying _DECL node. */
1150 block_defs_stack
.safe_push (currdef
? currdef
: sym
);
1152 /* Set the current reaching definition for SYM to be DEF. */
1153 info
->current_def
= def
;
1157 /* Perform a depth-first traversal of the dominator tree looking for
1158 variables to rename. BB is the block where to start searching.
1159 Renaming is a five step process:
1161 1- Every definition made by PHI nodes at the start of the blocks is
1162 registered as the current definition for the corresponding variable.
1164 2- Every statement in BB is rewritten. USE and VUSE operands are
1165 rewritten with their corresponding reaching definition. DEF and
1166 VDEF targets are registered as new definitions.
1168 3- All the PHI nodes in successor blocks of BB are visited. The
1169 argument corresponding to BB is replaced with its current reaching
1172 4- Recursively rewrite every dominator child block of BB.
1174 5- Restore (in reverse order) the current reaching definition for every
1175 new definition introduced in this block. This is done so that when
1176 we return from the recursive call, all the current reaching
1177 definitions are restored to the names that were valid in the
1178 dominator parent of BB. */
1180 /* Return the current definition for variable VAR. If none is found,
1181 create a new SSA name to act as the zeroth definition for VAR. */
1184 get_reaching_def (tree var
)
1186 common_info_p info
= get_common_info (var
);
1189 /* Lookup the current reaching definition for VAR. */
1190 currdef
= info
->current_def
;
1192 /* If there is no reaching definition for VAR, create and register a
1193 default definition for it (if needed). */
1194 if (currdef
== NULL_TREE
)
1196 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1197 currdef
= get_or_create_ssa_default_def (cfun
, sym
);
1200 /* Return the current reaching definition for VAR, or the default
1201 definition, if we had to create one. */
1206 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1209 rewrite_debug_stmt_uses (gimple stmt
)
1211 use_operand_p use_p
;
1213 bool update
= false;
1215 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1217 tree var
= USE_FROM_PTR (use_p
), def
;
1218 common_info_p info
= get_common_info (var
);
1219 gcc_checking_assert (DECL_P (var
));
1220 def
= info
->current_def
;
1223 if (TREE_CODE (var
) == PARM_DECL
1224 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun
)))
1226 gimple_stmt_iterator gsi
1228 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1230 /* Search a few source bind stmts at the start of first bb to
1231 see if a DEBUG_EXPR_DECL can't be reused. */
1233 !gsi_end_p (gsi
) && lim
> 0;
1234 gsi_next (&gsi
), lim
--)
1236 gimple gstmt
= gsi_stmt (gsi
);
1237 if (!gimple_debug_source_bind_p (gstmt
))
1239 if (gimple_debug_source_bind_get_value (gstmt
) == var
)
1241 def
= gimple_debug_source_bind_get_var (gstmt
);
1242 if (TREE_CODE (def
) == DEBUG_EXPR_DECL
)
1248 /* If not, add a new source bind stmt. */
1249 if (def
== NULL_TREE
)
1252 def
= make_node (DEBUG_EXPR_DECL
);
1253 def_temp
= gimple_build_debug_source_bind (def
, var
, NULL
);
1254 DECL_ARTIFICIAL (def
) = 1;
1255 TREE_TYPE (def
) = TREE_TYPE (var
);
1256 DECL_MODE (def
) = DECL_MODE (var
);
1258 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1259 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
1266 /* Check if info->current_def can be trusted. */
1267 basic_block bb
= gimple_bb (stmt
);
1269 = SSA_NAME_IS_DEFAULT_DEF (def
)
1270 ? NULL
: gimple_bb (SSA_NAME_DEF_STMT (def
));
1272 /* If definition is in current bb, it is fine. */
1275 /* If definition bb doesn't dominate the current bb,
1276 it can't be used. */
1277 else if (def_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
1279 /* If there is just one definition and dominates the current
1281 else if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1285 struct def_blocks_d
*db_p
= get_def_blocks_for (info
);
1287 /* If there are some non-debug uses in the current bb,
1289 if (bitmap_bit_p (db_p
->livein_blocks
, bb
->index
))
1291 /* Otherwise give up for now. */
1298 gimple_debug_bind_reset_value (stmt
);
1302 SET_USE (use_p
, def
);
1308 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1309 the block with its immediate reaching definitions. Update the current
1310 definition of a variable when a new real or virtual definition is found. */
1313 rewrite_stmt (gimple_stmt_iterator
*si
)
1315 use_operand_p use_p
;
1316 def_operand_p def_p
;
1318 gimple stmt
= gsi_stmt (*si
);
1320 /* If mark_def_sites decided that we don't need to rewrite this
1321 statement, ignore it. */
1322 gcc_assert (blocks_to_update
== NULL
);
1323 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1328 fprintf (dump_file
, "Renaming statement ");
1329 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1330 fprintf (dump_file
, "\n");
1333 /* Step 1. Rewrite USES in the statement. */
1334 if (rewrite_uses_p (stmt
))
1336 if (is_gimple_debug (stmt
))
1337 rewrite_debug_stmt_uses (stmt
);
1339 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1341 tree var
= USE_FROM_PTR (use_p
);
1342 gcc_checking_assert (DECL_P (var
));
1343 SET_USE (use_p
, get_reaching_def (var
));
1347 /* Step 2. Register the statement's DEF operands. */
1348 if (register_defs_p (stmt
))
1349 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1351 tree var
= DEF_FROM_PTR (def_p
);
1355 gcc_checking_assert (DECL_P (var
));
1357 if (gimple_clobber_p (stmt
)
1358 && is_gimple_reg (var
))
1360 /* If we rewrite a DECL into SSA form then drop its
1361 clobber stmts and replace uses with a new default def. */
1362 gcc_checking_assert (TREE_CODE (var
) == VAR_DECL
1363 && !gimple_vdef (stmt
));
1364 gsi_replace (si
, gimple_build_nop (), true);
1365 register_new_def (get_or_create_ssa_default_def (cfun
, var
), var
);
1369 name
= make_ssa_name (var
, stmt
);
1370 SET_DEF (def_p
, name
);
1371 register_new_def (DEF_FROM_PTR (def_p
), var
);
1373 tracked_var
= target_for_debug_bind (var
);
1376 gimple note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1377 gsi_insert_after (si
, note
, GSI_SAME_STMT
);
1383 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1384 PHI nodes. For every PHI node found, add a new argument containing the
1385 current reaching definition for the variable and the edge through which
1386 that definition is reaching the PHI node. */
1389 rewrite_add_phi_arguments (basic_block bb
)
1394 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1397 gimple_stmt_iterator gsi
;
1399 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1405 phi
= gsi_stmt (gsi
);
1406 res
= gimple_phi_result (phi
);
1407 currdef
= get_reaching_def (SSA_NAME_VAR (res
));
1408 /* Virtual operand PHI args do not need a location. */
1409 if (virtual_operand_p (res
))
1410 loc
= UNKNOWN_LOCATION
;
1412 loc
= gimple_location (SSA_NAME_DEF_STMT (currdef
));
1413 add_phi_arg (phi
, currdef
, e
, loc
);
1418 class rewrite_dom_walker
: public dom_walker
1421 rewrite_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1423 virtual void before_dom_children (basic_block
);
1424 virtual void after_dom_children (basic_block
);
1427 /* SSA Rewriting Step 1. Initialization, create a block local stack
1428 of reaching definitions for new SSA names produced in this block
1429 (BLOCK_DEFS). Register new definitions for every PHI node in the
1433 rewrite_dom_walker::before_dom_children (basic_block bb
)
1435 gimple_stmt_iterator gsi
;
1437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1438 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1440 /* Mark the unwind point for this block. */
1441 block_defs_stack
.safe_push (NULL_TREE
);
1443 /* Step 1. Register new definitions for every PHI node in the block.
1444 Conceptually, all the PHI nodes are executed in parallel and each PHI
1445 node introduces a new version for the associated variable. */
1446 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1448 tree result
= gimple_phi_result (gsi_stmt (gsi
));
1449 register_new_def (result
, SSA_NAME_VAR (result
));
1452 /* Step 2. Rewrite every variable used in each statement in the block
1453 with its immediate reaching definitions. Update the current definition
1454 of a variable when a new real or virtual definition is found. */
1455 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
1456 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1457 rewrite_stmt (&gsi
);
1459 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1460 For every PHI node found, add a new argument containing the current
1461 reaching definition for the variable and the edge through which that
1462 definition is reaching the PHI node. */
1463 rewrite_add_phi_arguments (bb
);
1468 /* Called after visiting all the statements in basic block BB and all
1469 of its dominator children. Restore CURRDEFS to its original value. */
1472 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
1474 /* Restore CURRDEFS to its original state. */
1475 while (block_defs_stack
.length () > 0)
1477 tree tmp
= block_defs_stack
.pop ();
1478 tree saved_def
, var
;
1480 if (tmp
== NULL_TREE
)
1483 if (TREE_CODE (tmp
) == SSA_NAME
)
1485 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1486 current definition of its underlying variable. Note that
1487 if the SSA_NAME is not for a GIMPLE register, the symbol
1488 being defined is stored in the next slot in the stack.
1489 This mechanism is needed because an SSA name for a
1490 non-register symbol may be the definition for more than
1491 one symbol (e.g., SFTs, aliased variables, etc). */
1493 var
= SSA_NAME_VAR (saved_def
);
1494 if (!is_gimple_reg (var
))
1495 var
= block_defs_stack
.pop ();
1499 /* If we recorded anything else, it must have been a _DECL
1500 node and its current reaching definition must have been
1506 get_common_info (var
)->current_def
= saved_def
;
1511 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1514 debug_decl_set (bitmap set
)
1516 dump_decl_set (stderr
, set
);
1517 fprintf (stderr
, "\n");
1521 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1522 stack up to a maximum of N levels. If N is -1, the whole stack is
1523 dumped. New levels are created when the dominator tree traversal
1524 used for renaming enters a new sub-tree. */
1527 dump_defs_stack (FILE *file
, int n
)
1531 fprintf (file
, "\n\nRenaming stack");
1533 fprintf (file
, " (up to %d levels)", n
);
1534 fprintf (file
, "\n\n");
1537 fprintf (file
, "Level %d (current level)\n", i
);
1538 for (j
= (int) block_defs_stack
.length () - 1; j
>= 0; j
--)
1542 name
= block_defs_stack
[j
];
1543 if (name
== NULL_TREE
)
1548 fprintf (file
, "\nLevel %d\n", i
);
1559 var
= SSA_NAME_VAR (name
);
1560 if (!is_gimple_reg (var
))
1563 var
= block_defs_stack
[j
];
1567 fprintf (file
, " Previous CURRDEF (");
1568 print_generic_expr (file
, var
, 0);
1569 fprintf (file
, ") = ");
1571 print_generic_expr (file
, name
, 0);
1573 fprintf (file
, "<NIL>");
1574 fprintf (file
, "\n");
1579 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1580 stack up to a maximum of N levels. If N is -1, the whole stack is
1581 dumped. New levels are created when the dominator tree traversal
1582 used for renaming enters a new sub-tree. */
1585 debug_defs_stack (int n
)
1587 dump_defs_stack (stderr
, n
);
1591 /* Dump the current reaching definition of every symbol to FILE. */
1594 dump_currdefs (FILE *file
)
1599 if (symbols_to_rename
.is_empty ())
1602 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1603 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, var
)
1605 common_info_p info
= get_common_info (var
);
1606 fprintf (file
, "CURRDEF (");
1607 print_generic_expr (file
, var
, 0);
1608 fprintf (file
, ") = ");
1609 if (info
->current_def
)
1610 print_generic_expr (file
, info
->current_def
, 0);
1612 fprintf (file
, "<NIL>");
1613 fprintf (file
, "\n");
1618 /* Dump the current reaching definition of every symbol to stderr. */
1621 debug_currdefs (void)
1623 dump_currdefs (stderr
);
1627 /* Dump SSA information to FILE. */
1630 dump_tree_ssa (FILE *file
)
1632 const char *funcname
1633 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1635 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1637 dump_var_infos (file
);
1638 dump_defs_stack (file
, -1);
1639 dump_currdefs (file
);
1640 dump_tree_ssa_stats (file
);
1644 /* Dump SSA information to stderr. */
1647 debug_tree_ssa (void)
1649 dump_tree_ssa (stderr
);
1653 /* Dump statistics for the hash table HTAB. */
1656 htab_statistics (FILE *file
, hash_table
<var_info_hasher
> htab
)
1658 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1659 (long) htab
.size (),
1660 (long) htab
.elements (),
1661 htab
.collisions ());
1665 /* Dump SSA statistics on FILE. */
1668 dump_tree_ssa_stats (FILE *file
)
1670 if (var_infos
.is_created ())
1672 fprintf (file
, "\nHash table statistics:\n");
1673 fprintf (file
, " var_infos: ");
1674 htab_statistics (file
, var_infos
);
1675 fprintf (file
, "\n");
1680 /* Dump SSA statistics on stderr. */
1683 debug_tree_ssa_stats (void)
1685 dump_tree_ssa_stats (stderr
);
1689 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1692 debug_var_infos_r (var_info_d
**slot
, FILE *file
)
1694 struct var_info_d
*info
= *slot
;
1696 fprintf (file
, "VAR: ");
1697 print_generic_expr (file
, info
->var
, dump_flags
);
1698 bitmap_print (file
, info
->info
.def_blocks
.def_blocks
,
1699 ", DEF_BLOCKS: { ", "}");
1700 bitmap_print (file
, info
->info
.def_blocks
.livein_blocks
,
1701 ", LIVEIN_BLOCKS: { ", "}");
1702 bitmap_print (file
, info
->info
.def_blocks
.phi_blocks
,
1703 ", PHI_BLOCKS: { ", "}\n");
1709 /* Dump the VAR_INFOS hash table on FILE. */
1712 dump_var_infos (FILE *file
)
1714 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1715 if (var_infos
.is_created ())
1716 var_infos
.traverse
<FILE *, debug_var_infos_r
> (file
);
1720 /* Dump the VAR_INFOS hash table on stderr. */
1723 debug_var_infos (void)
1725 dump_var_infos (stderr
);
1729 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1732 register_new_update_single (tree new_name
, tree old_name
)
1734 common_info_p info
= get_common_info (old_name
);
1735 tree currdef
= info
->current_def
;
1737 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1738 This stack is later used by the dominator tree callbacks to
1739 restore the reaching definitions for all the variables
1740 defined in the block after a recursive visit to all its
1741 immediately dominated blocks. */
1742 block_defs_stack
.reserve (2);
1743 block_defs_stack
.quick_push (currdef
);
1744 block_defs_stack
.quick_push (old_name
);
1746 /* Set the current reaching definition for OLD_NAME to be
1748 info
->current_def
= new_name
;
1752 /* Register NEW_NAME to be the new reaching definition for all the
1753 names in OLD_NAMES. Used by the incremental SSA update routines to
1754 replace old SSA names with new ones. */
1757 register_new_update_set (tree new_name
, bitmap old_names
)
1762 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1763 register_new_update_single (new_name
, ssa_name (i
));
1768 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1769 it is a symbol marked for renaming, replace it with USE_P's current
1770 reaching definition. */
1773 maybe_replace_use (use_operand_p use_p
)
1775 tree rdef
= NULL_TREE
;
1776 tree use
= USE_FROM_PTR (use_p
);
1777 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1779 if (marked_for_renaming (sym
))
1780 rdef
= get_reaching_def (sym
);
1781 else if (is_old_name (use
))
1782 rdef
= get_reaching_def (use
);
1784 if (rdef
&& rdef
!= use
)
1785 SET_USE (use_p
, rdef
);
1789 /* Same as maybe_replace_use, but without introducing default stmts,
1790 returning false to indicate a need to do so. */
1793 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1795 tree rdef
= NULL_TREE
;
1796 tree use
= USE_FROM_PTR (use_p
);
1797 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1799 if (marked_for_renaming (sym
))
1800 rdef
= get_var_info (sym
)->info
.current_def
;
1801 else if (is_old_name (use
))
1803 rdef
= get_ssa_name_ann (use
)->info
.current_def
;
1804 /* We can't assume that, if there's no current definition, the
1805 default one should be used. It could be the case that we've
1806 rearranged blocks so that the earlier definition no longer
1807 dominates the use. */
1808 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1814 if (rdef
&& rdef
!= use
)
1815 SET_USE (use_p
, rdef
);
1817 return rdef
!= NULL_TREE
;
1821 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1822 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1823 register it as the current definition for the names replaced by
1827 maybe_register_def (def_operand_p def_p
, gimple stmt
,
1828 gimple_stmt_iterator gsi
)
1830 tree def
= DEF_FROM_PTR (def_p
);
1831 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1833 /* If DEF is a naked symbol that needs renaming, create a new
1835 if (marked_for_renaming (sym
))
1841 def
= make_ssa_name (def
, stmt
);
1842 SET_DEF (def_p
, def
);
1844 tracked_var
= target_for_debug_bind (sym
);
1847 gimple note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1848 /* If stmt ends the bb, insert the debug stmt on the single
1849 non-EH edge from the stmt. */
1850 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1852 basic_block bb
= gsi_bb (gsi
);
1855 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1856 if (!(e
->flags
& EDGE_EH
))
1858 gcc_checking_assert (!ef
);
1861 /* If there are other predecessors to ef->dest, then
1862 there must be PHI nodes for the modified
1863 variable, and therefore there will be debug bind
1864 stmts after the PHI nodes. The debug bind notes
1865 we'd insert would force the creation of a new
1866 block (diverging codegen) and be redundant with
1867 the post-PHI bind stmts, so don't add them.
1869 As for the exit edge, there wouldn't be redundant
1870 bind stmts, but there wouldn't be a PC to bind
1871 them to either, so avoid diverging the CFG. */
1872 if (ef
&& single_pred_p (ef
->dest
)
1873 && ef
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1875 /* If there were PHI nodes in the node, we'd
1876 have to make sure the value we're binding
1877 doesn't need rewriting. But there shouldn't
1878 be PHI nodes in a single-predecessor block,
1879 so we just add the note. */
1880 gsi_insert_on_edge_immediate (ef
, note
);
1884 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1888 register_new_update_single (def
, sym
);
1892 /* If DEF is a new name, register it as a new definition
1893 for all the names replaced by DEF. */
1894 if (is_new_name (def
))
1895 register_new_update_set (def
, names_replaced_by (def
));
1897 /* If DEF is an old name, register DEF as a new
1898 definition for itself. */
1899 if (is_old_name (def
))
1900 register_new_update_single (def
, def
);
1905 /* Update every variable used in the statement pointed-to by SI. The
1906 statement is assumed to be in SSA form already. Names in
1907 OLD_SSA_NAMES used by SI will be updated to their current reaching
1908 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1909 will be registered as a new definition for their corresponding name
1910 in OLD_SSA_NAMES. */
1913 rewrite_update_stmt (gimple stmt
, gimple_stmt_iterator gsi
)
1915 use_operand_p use_p
;
1916 def_operand_p def_p
;
1919 /* Only update marked statements. */
1920 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1925 fprintf (dump_file
, "Updating SSA information for statement ");
1926 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1929 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1930 symbol is marked for renaming. */
1931 if (rewrite_uses_p (stmt
))
1933 if (is_gimple_debug (stmt
))
1935 bool failed
= false;
1937 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1938 if (!maybe_replace_use_in_debug_stmt (use_p
))
1946 /* DOM sometimes threads jumps in such a way that a
1947 debug stmt ends up referencing a SSA variable that no
1948 longer dominates the debug stmt, but such that all
1949 incoming definitions refer to the same definition in
1950 an earlier dominator. We could try to recover that
1951 definition somehow, but this will have to do for now.
1953 Introducing a default definition, which is what
1954 maybe_replace_use() would do in such cases, may
1955 modify code generation, for the otherwise-unused
1956 default definition would never go away, modifying SSA
1957 version numbers all over. */
1958 gimple_debug_bind_reset_value (stmt
);
1964 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1965 maybe_replace_use (use_p
);
1969 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1970 Also register definitions for names whose underlying symbol is
1971 marked for renaming. */
1972 if (register_defs_p (stmt
))
1973 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1974 maybe_register_def (def_p
, stmt
, gsi
);
1978 /* Visit all the successor blocks of BB looking for PHI nodes. For
1979 every PHI node found, check if any of its arguments is in
1980 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1981 definition, replace it. */
1984 rewrite_update_phi_arguments (basic_block bb
)
1990 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1995 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
1998 phis
= phis_to_rewrite
[e
->dest
->index
];
1999 FOR_EACH_VEC_ELT (phis
, i
, phi
)
2001 tree arg
, lhs_sym
, reaching_def
= NULL
;
2002 use_operand_p arg_p
;
2004 gcc_checking_assert (rewrite_uses_p (phi
));
2006 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
2007 arg
= USE_FROM_PTR (arg_p
);
2009 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
2012 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2014 if (arg
== NULL_TREE
)
2016 /* When updating a PHI node for a recently introduced
2017 symbol we may find NULL arguments. That's why we
2018 take the symbol from the LHS of the PHI node. */
2019 reaching_def
= get_reaching_def (lhs_sym
);
2024 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2026 if (marked_for_renaming (sym
))
2027 reaching_def
= get_reaching_def (sym
);
2028 else if (is_old_name (arg
))
2029 reaching_def
= get_reaching_def (arg
);
2032 /* Update the argument if there is a reaching def. */
2035 source_location locus
;
2036 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2038 SET_USE (arg_p
, reaching_def
);
2040 /* Virtual operands do not need a location. */
2041 if (virtual_operand_p (reaching_def
))
2042 locus
= UNKNOWN_LOCATION
;
2045 gimple stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2047 /* Single element PHI nodes behave like copies, so get the
2048 location from the phi argument. */
2049 if (gimple_code (stmt
) == GIMPLE_PHI
2050 && gimple_phi_num_args (stmt
) == 1)
2051 locus
= gimple_phi_arg_location (stmt
, 0);
2053 locus
= gimple_location (stmt
);
2056 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2060 if (e
->flags
& EDGE_ABNORMAL
)
2061 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2066 class rewrite_update_dom_walker
: public dom_walker
2069 rewrite_update_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2071 virtual void before_dom_children (basic_block
);
2072 virtual void after_dom_children (basic_block
);
2075 /* Initialization of block data structures for the incremental SSA
2076 update pass. Create a block local stack of reaching definitions
2077 for new SSA names produced in this block (BLOCK_DEFS). Register
2078 new definitions for every PHI node in the block. */
2081 rewrite_update_dom_walker::before_dom_children (basic_block bb
)
2083 bool is_abnormal_phi
;
2084 gimple_stmt_iterator gsi
;
2086 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2087 fprintf (dump_file
, "Registering new PHI nodes in block #%d\n",
2090 /* Mark the unwind point for this block. */
2091 block_defs_stack
.safe_push (NULL_TREE
);
2093 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2096 /* Mark the LHS if any of the arguments flows through an abnormal
2098 is_abnormal_phi
= bb_has_abnormal_pred (bb
);
2100 /* If any of the PHI nodes is a replacement for a name in
2101 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2102 register it as a new definition for its corresponding name. Also
2103 register definitions for names whose underlying symbols are
2104 marked for renaming. */
2105 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2108 gimple phi
= gsi_stmt (gsi
);
2110 if (!register_defs_p (phi
))
2113 lhs
= gimple_phi_result (phi
);
2114 lhs_sym
= SSA_NAME_VAR (lhs
);
2116 if (marked_for_renaming (lhs_sym
))
2117 register_new_update_single (lhs
, lhs_sym
);
2121 /* If LHS is a new name, register a new definition for all
2122 the names replaced by LHS. */
2123 if (is_new_name (lhs
))
2124 register_new_update_set (lhs
, names_replaced_by (lhs
));
2126 /* If LHS is an OLD name, register it as a new definition
2128 if (is_old_name (lhs
))
2129 register_new_update_single (lhs
, lhs
);
2132 if (is_abnormal_phi
)
2133 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2136 /* Step 2. Rewrite every variable used in each statement in the block. */
2137 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
2139 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2140 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2141 rewrite_update_stmt (gsi_stmt (gsi
), gsi
);
2144 /* Step 3. Update PHI nodes. */
2145 rewrite_update_phi_arguments (bb
);
2148 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2149 the current reaching definition of every name re-written in BB to
2150 the original reaching definition before visiting BB. This
2151 unwinding must be done in the opposite order to what is done in
2152 register_new_update_set. */
2155 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
2157 while (block_defs_stack
.length () > 0)
2159 tree var
= block_defs_stack
.pop ();
2162 /* NULL indicates the unwind stop point for this block (see
2163 rewrite_update_enter_block). */
2167 saved_def
= block_defs_stack
.pop ();
2168 get_common_info (var
)->current_def
= saved_def
;
2173 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2176 ENTRY indicates the block where to start. Every block dominated by
2177 ENTRY will be rewritten.
2179 WHAT indicates what actions will be taken by the renamer (see enum
2182 BLOCKS are the set of interesting blocks for the dominator walker
2183 to process. If this set is NULL, then all the nodes dominated
2184 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2185 are not present in BLOCKS are ignored. */
2188 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2190 /* Rewrite all the basic blocks in the program. */
2191 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2193 block_defs_stack
.create (10);
2195 /* Recursively walk the dominator tree rewriting each statement in
2196 each basic block. */
2197 if (what
== REWRITE_ALL
)
2198 rewrite_dom_walker (CDI_DOMINATORS
).walk (entry
);
2199 else if (what
== REWRITE_UPDATE
)
2200 rewrite_update_dom_walker (CDI_DOMINATORS
).walk (entry
);
2204 /* Debugging dumps. */
2205 if (dump_file
&& (dump_flags
& TDF_STATS
))
2207 dump_dfa_stats (dump_file
);
2208 if (var_infos
.is_created ())
2209 dump_tree_ssa_stats (dump_file
);
2212 block_defs_stack
.release ();
2214 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2217 class mark_def_dom_walker
: public dom_walker
2220 mark_def_dom_walker (cdi_direction direction
);
2221 ~mark_def_dom_walker ();
2223 virtual void before_dom_children (basic_block
);
2226 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2227 large enough to accommodate all the variables referenced in the
2228 function, not just the ones we are renaming. */
2232 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction
)
2233 : dom_walker (direction
), m_kills (BITMAP_ALLOC (NULL
))
2237 mark_def_dom_walker::~mark_def_dom_walker ()
2239 BITMAP_FREE (m_kills
);
2242 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2243 at the start of each block, and call mark_def_sites for each statement. */
2246 mark_def_dom_walker::before_dom_children (basic_block bb
)
2248 gimple_stmt_iterator gsi
;
2250 bitmap_clear (m_kills
);
2251 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2252 mark_def_sites (bb
, gsi_stmt (gsi
), m_kills
);
2255 /* Initialize internal data needed during renaming. */
2258 init_ssa_renamer (void)
2260 cfun
->gimple_df
->in_ssa_p
= false;
2262 /* Allocate memory for the DEF_BLOCKS hash table. */
2263 gcc_assert (!var_infos
.is_created ());
2264 var_infos
.create (vec_safe_length (cfun
->local_decls
));
2266 bitmap_obstack_initialize (&update_ssa_obstack
);
2270 /* Deallocate internal data structures used by the renamer. */
2273 fini_ssa_renamer (void)
2275 if (var_infos
.is_created ())
2276 var_infos
.dispose ();
2278 bitmap_obstack_release (&update_ssa_obstack
);
2280 cfun
->gimple_df
->ssa_renaming_needed
= 0;
2281 cfun
->gimple_df
->rename_vops
= 0;
2282 cfun
->gimple_df
->in_ssa_p
= true;
2285 /* Main entry point into the SSA builder. The renaming process
2286 proceeds in four main phases:
2288 1- Compute dominance frontier and immediate dominators, needed to
2289 insert PHI nodes and rename the function in dominator tree
2292 2- Find and mark all the blocks that define variables.
2294 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2296 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2298 Steps 3 and 4 are done using the dominator tree walker
2299 (walk_dominator_tree). */
2302 rewrite_into_ssa (void)
2308 /* Initialize operand data structures. */
2309 init_ssa_operands (cfun
);
2311 /* Initialize internal data needed by the renamer. */
2312 init_ssa_renamer ();
2314 /* Initialize the set of interesting blocks. The callback
2315 mark_def_sites will add to this set those blocks that the renamer
2317 interesting_blocks
= sbitmap_alloc (last_basic_block
);
2318 bitmap_clear (interesting_blocks
);
2320 /* Initialize dominance frontier. */
2321 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
2323 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
2325 /* 1- Compute dominance frontiers. */
2326 calculate_dominance_info (CDI_DOMINATORS
);
2327 compute_dominance_frontiers (dfs
);
2329 /* 2- Find and mark definition sites. */
2330 mark_def_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
2332 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2333 insert_phi_nodes (dfs
);
2335 /* 4- Rename all the blocks. */
2336 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (cfun
), REWRITE_ALL
);
2338 /* Free allocated memory. */
2340 bitmap_clear (&dfs
[bb
->index
]);
2343 sbitmap_free (interesting_blocks
);
2345 fini_ssa_renamer ();
2347 /* Try to get rid of all gimplifier generated temporaries by making
2348 its SSA names anonymous. This way we can garbage collect them
2349 all after removing unused locals which we do in our TODO. */
2350 for (i
= 1; i
< num_ssa_names
; ++i
)
2352 tree decl
, name
= ssa_name (i
);
2354 || SSA_NAME_IS_DEFAULT_DEF (name
))
2356 decl
= SSA_NAME_VAR (name
);
2358 && TREE_CODE (decl
) == VAR_DECL
2359 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl
)
2360 && DECL_IGNORED_P (decl
))
2361 SET_SSA_NAME_VAR_OR_IDENTIFIER (name
, DECL_NAME (decl
));
2367 /* Gate for IPCP optimization. */
2370 gate_into_ssa (void)
2372 /* Do nothing for funcions that was produced already in SSA form. */
2373 return !(cfun
->curr_properties
& PROP_ssa
);
2378 const pass_data pass_data_build_ssa
=
2380 GIMPLE_PASS
, /* type */
2382 OPTGROUP_NONE
, /* optinfo_flags */
2383 true, /* has_gate */
2384 true, /* has_execute */
2385 TV_TREE_SSA_OTHER
, /* tv_id */
2386 PROP_cfg
, /* properties_required */
2387 PROP_ssa
, /* properties_provided */
2388 0, /* properties_destroyed */
2389 0, /* todo_flags_start */
2390 ( TODO_verify_ssa
| TODO_remove_unused_locals
), /* todo_flags_finish */
2393 class pass_build_ssa
: public gimple_opt_pass
2396 pass_build_ssa (gcc::context
*ctxt
)
2397 : gimple_opt_pass (pass_data_build_ssa
, ctxt
)
2400 /* opt_pass methods: */
2401 bool gate () { return gate_into_ssa (); }
2402 unsigned int execute () { return rewrite_into_ssa (); }
2404 }; // class pass_build_ssa
2409 make_pass_build_ssa (gcc::context
*ctxt
)
2411 return new pass_build_ssa (ctxt
);
2415 /* Mark the definition of VAR at STMT and BB as interesting for the
2416 renamer. BLOCKS is the set of blocks that need updating. */
2419 mark_def_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2421 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2422 set_register_defs (stmt
, true);
2426 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2428 set_def_block (var
, bb
, is_phi_p
);
2430 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2431 site for both itself and all the old names replaced by it. */
2432 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2436 bitmap set
= names_replaced_by (var
);
2438 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2439 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2445 /* Mark the use of VAR at STMT and BB as interesting for the
2446 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2450 mark_use_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2452 basic_block def_bb
= gimple_bb (stmt
);
2454 mark_block_for_update (def_bb
);
2455 mark_block_for_update (bb
);
2457 if (gimple_code (stmt
) == GIMPLE_PHI
)
2458 mark_phi_for_rewrite (def_bb
, stmt
);
2461 set_rewrite_uses (stmt
, true);
2463 if (is_gimple_debug (stmt
))
2467 /* If VAR has not been defined in BB, then it is live-on-entry
2468 to BB. Note that we cannot just use the block holding VAR's
2469 definition because if VAR is one of the names in OLD_SSA_NAMES,
2470 it will have several definitions (itself and all the names that
2474 struct def_blocks_d
*db_p
= get_def_blocks_for (get_common_info (var
));
2475 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2476 set_livein_block (var
, bb
);
2481 /* Do a dominator walk starting at BB processing statements that
2482 reference symbols in SSA operands. This is very similar to
2483 mark_def_sites, but the scan handles statements whose operands may
2484 already be SSA names.
2486 If INSERT_PHI_P is true, mark those uses as live in the
2487 corresponding block. This is later used by the PHI placement
2488 algorithm to make PHI pruning decisions.
2490 FIXME. Most of this would be unnecessary if we could associate a
2491 symbol to all the SSA names that reference it. But that
2492 sounds like it would be expensive to maintain. Still, it
2493 would be interesting to see if it makes better sense to do
2497 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2500 gimple_stmt_iterator si
;
2504 mark_block_for_update (bb
);
2506 /* Process PHI nodes marking interesting those that define or use
2507 the symbols that we are interested in. */
2508 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
2510 gimple phi
= gsi_stmt (si
);
2511 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2513 if (TREE_CODE (lhs
) == SSA_NAME
2514 && (! virtual_operand_p (lhs
)
2515 || ! cfun
->gimple_df
->rename_vops
))
2518 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2519 mark_for_renaming (lhs_sym
);
2520 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2522 /* Mark the uses in phi nodes as interesting. It would be more correct
2523 to process the arguments of the phi nodes of the successor edges of
2524 BB at the end of prepare_block_for_update, however, that turns out
2525 to be significantly more expensive. Doing it here is conservatively
2526 correct -- it may only cause us to believe a value to be live in a
2527 block that also contains its definition, and thus insert a few more
2528 phi nodes for it. */
2529 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2530 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2533 /* Process the statements. */
2534 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2538 use_operand_p use_p
;
2539 def_operand_p def_p
;
2541 stmt
= gsi_stmt (si
);
2543 if (cfun
->gimple_df
->rename_vops
2544 && gimple_vuse (stmt
))
2546 tree use
= gimple_vuse (stmt
);
2547 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2548 mark_for_renaming (sym
);
2549 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2552 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_USE
)
2554 tree use
= USE_FROM_PTR (use_p
);
2557 mark_for_renaming (use
);
2558 mark_use_interesting (use
, stmt
, bb
, insert_phi_p
);
2561 if (cfun
->gimple_df
->rename_vops
2562 && gimple_vdef (stmt
))
2564 tree def
= gimple_vdef (stmt
);
2565 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2566 mark_for_renaming (sym
);
2567 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2570 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_DEF
)
2572 tree def
= DEF_FROM_PTR (def_p
);
2575 mark_for_renaming (def
);
2576 mark_def_interesting (def
, stmt
, bb
, insert_phi_p
);
2580 /* Now visit all the blocks dominated by BB. */
2581 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2583 son
= next_dom_son (CDI_DOMINATORS
, son
))
2584 prepare_block_for_update (son
, insert_phi_p
);
2588 /* Helper for prepare_names_to_update. Mark all the use sites for
2589 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2590 prepare_names_to_update. */
2593 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2595 use_operand_p use_p
;
2596 imm_use_iterator iter
;
2598 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2600 gimple stmt
= USE_STMT (use_p
);
2601 basic_block bb
= gimple_bb (stmt
);
2603 if (gimple_code (stmt
) == GIMPLE_PHI
)
2605 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2606 edge e
= gimple_phi_arg_edge (stmt
, ix
);
2607 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2611 /* For regular statements, mark this as an interesting use
2613 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2619 /* Helper for prepare_names_to_update. Mark the definition site for
2620 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2621 prepare_names_to_update. */
2624 prepare_def_site_for (tree name
, bool insert_phi_p
)
2629 gcc_checking_assert (names_to_release
== NULL
2630 || !bitmap_bit_p (names_to_release
,
2631 SSA_NAME_VERSION (name
)));
2633 stmt
= SSA_NAME_DEF_STMT (name
);
2634 bb
= gimple_bb (stmt
);
2637 gcc_checking_assert (bb
->index
< last_basic_block
);
2638 mark_block_for_update (bb
);
2639 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2644 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2645 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2646 PHI nodes for newly created names. */
2649 prepare_names_to_update (bool insert_phi_p
)
2653 sbitmap_iterator sbi
;
2655 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2656 remove it from NEW_SSA_NAMES so that we don't try to visit its
2657 defining basic block (which most likely doesn't exist). Notice
2658 that we cannot do the same with names in OLD_SSA_NAMES because we
2659 want to replace existing instances. */
2660 if (names_to_release
)
2661 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2662 bitmap_clear_bit (new_ssa_names
, i
);
2664 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2665 names may be considered to be live-in on blocks that contain
2666 definitions for their replacements. */
2667 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2668 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2670 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2671 OLD_SSA_NAMES, but we have to ignore its definition site. */
2672 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
2674 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2675 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2676 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2681 /* Dump all the names replaced by NAME to FILE. */
2684 dump_names_replaced_by (FILE *file
, tree name
)
2690 print_generic_expr (file
, name
, 0);
2691 fprintf (file
, " -> { ");
2693 old_set
= names_replaced_by (name
);
2694 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2696 print_generic_expr (file
, ssa_name (i
), 0);
2697 fprintf (file
, " ");
2700 fprintf (file
, "}\n");
2704 /* Dump all the names replaced by NAME to stderr. */
2707 debug_names_replaced_by (tree name
)
2709 dump_names_replaced_by (stderr
, name
);
2713 /* Dump SSA update information to FILE. */
2716 dump_update_ssa (FILE *file
)
2721 if (!need_ssa_update_p (cfun
))
2724 if (new_ssa_names
&& bitmap_first_set_bit (new_ssa_names
) >= 0)
2726 sbitmap_iterator sbi
;
2728 fprintf (file
, "\nSSA replacement table\n");
2729 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2730 "O_1, ..., O_j\n\n");
2732 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2733 dump_names_replaced_by (file
, ssa_name (i
));
2736 if (symbols_to_rename_set
&& !bitmap_empty_p (symbols_to_rename_set
))
2738 fprintf (file
, "\nSymbols to be put in SSA form\n");
2739 dump_decl_set (file
, symbols_to_rename_set
);
2740 fprintf (file
, "\n");
2743 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2745 fprintf (file
, "\nSSA names to release after updating the SSA web\n\n");
2746 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2748 print_generic_expr (file
, ssa_name (i
), 0);
2749 fprintf (file
, " ");
2751 fprintf (file
, "\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 bitmap_clear (old_ssa_names
);
2776 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2777 bitmap_clear (new_ssa_names
);
2779 bitmap_obstack_initialize (&update_ssa_obstack
);
2781 names_to_release
= NULL
;
2782 update_ssa_initialized_fn
= fn
;
2786 /* Deallocate data structures used for incremental SSA updates. */
2789 delete_update_ssa (void)
2794 sbitmap_free (old_ssa_names
);
2795 old_ssa_names
= NULL
;
2797 sbitmap_free (new_ssa_names
);
2798 new_ssa_names
= NULL
;
2800 BITMAP_FREE (symbols_to_rename_set
);
2801 symbols_to_rename_set
= NULL
;
2802 symbols_to_rename
.release ();
2804 if (names_to_release
)
2806 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2807 release_ssa_name (ssa_name (i
));
2808 BITMAP_FREE (names_to_release
);
2811 clear_ssa_name_info ();
2813 fini_ssa_renamer ();
2815 if (blocks_with_phis_to_rewrite
)
2816 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2818 gimple_vec phis
= phis_to_rewrite
[i
];
2820 phis_to_rewrite
[i
].create (0);
2823 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2824 BITMAP_FREE (blocks_to_update
);
2826 update_ssa_initialized_fn
= NULL
;
2830 /* Create a new name for OLD_NAME in statement STMT and replace the
2831 operand pointed to by DEF_P with the newly created name. If DEF_P
2832 is NULL then STMT should be a GIMPLE assignment.
2833 Return the new name and register the replacement mapping <NEW, OLD> in
2834 update_ssa's tables. */
2837 create_new_def_for (tree old_name
, gimple stmt
, def_operand_p def
)
2841 timevar_push (TV_TREE_SSA_INCREMENTAL
);
2843 if (!update_ssa_initialized_fn
)
2844 init_update_ssa (cfun
);
2846 gcc_assert (update_ssa_initialized_fn
== cfun
);
2848 new_name
= duplicate_ssa_name (old_name
, stmt
);
2850 SET_DEF (def
, new_name
);
2852 gimple_assign_set_lhs (stmt
, new_name
);
2854 if (gimple_code (stmt
) == GIMPLE_PHI
)
2856 basic_block bb
= gimple_bb (stmt
);
2858 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2859 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = bb_has_abnormal_pred (bb
);
2862 add_new_name_mapping (new_name
, old_name
);
2864 /* For the benefit of passes that will be updating the SSA form on
2865 their own, set the current reaching definition of OLD_NAME to be
2867 get_ssa_name_ann (old_name
)->info
.current_def
= new_name
;
2869 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
2875 /* Mark virtual operands of FN for renaming by update_ssa. */
2878 mark_virtual_operands_for_renaming (struct function
*fn
)
2880 fn
->gimple_df
->ssa_renaming_needed
= 1;
2881 fn
->gimple_df
->rename_vops
= 1;
2884 /* Replace all uses of NAME by underlying variable and mark it
2885 for renaming. This assumes the defining statement of NAME is
2886 going to be removed. */
2889 mark_virtual_operand_for_renaming (tree name
)
2891 tree name_var
= SSA_NAME_VAR (name
);
2893 imm_use_iterator iter
;
2894 use_operand_p use_p
;
2897 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var
));
2898 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
2900 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2901 SET_USE (use_p
, name_var
);
2905 mark_virtual_operands_for_renaming (cfun
);
2908 /* Replace all uses of the virtual PHI result by its underlying variable
2909 and mark it for renaming. This assumes the PHI node is going to be
2913 mark_virtual_phi_result_for_renaming (gimple phi
)
2915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2917 fprintf (dump_file
, "Marking result for renaming : ");
2918 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
2919 fprintf (dump_file
, "\n");
2922 mark_virtual_operand_for_renaming (gimple_phi_result (phi
));
2925 /* Return true if there is any work to be done by update_ssa
2929 need_ssa_update_p (struct function
*fn
)
2931 gcc_assert (fn
!= NULL
);
2932 return (update_ssa_initialized_fn
== fn
2933 || (fn
->gimple_df
&& fn
->gimple_df
->ssa_renaming_needed
));
2936 /* Return true if name N has been registered in the replacement table. */
2939 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
2941 if (!update_ssa_initialized_fn
)
2944 gcc_assert (update_ssa_initialized_fn
== cfun
);
2946 return is_new_name (n
) || is_old_name (n
);
2950 /* Mark NAME to be released after update_ssa has finished. */
2953 release_ssa_name_after_update_ssa (tree name
)
2955 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
2957 if (names_to_release
== NULL
)
2958 names_to_release
= BITMAP_ALLOC (NULL
);
2960 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
2964 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2965 frontier information. BLOCKS is the set of blocks to be updated.
2967 This is slightly different than the regular PHI insertion
2968 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2969 real names (i.e., GIMPLE registers) are inserted:
2971 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2972 nodes inside the region affected by the block that defines VAR
2973 and the blocks that define all its replacements. All these
2974 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2976 First, we compute the entry point to the region (ENTRY). This is
2977 given by the nearest common dominator to all the definition
2978 blocks. When computing the iterated dominance frontier (IDF), any
2979 block not strictly dominated by ENTRY is ignored.
2981 We then call the standard PHI insertion algorithm with the pruned
2984 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2985 names is not pruned. PHI nodes are inserted at every IDF block. */
2988 insert_updated_phi_nodes_for (tree var
, bitmap_head
*dfs
, bitmap blocks
,
2989 unsigned update_flags
)
2992 struct def_blocks_d
*db
;
2993 bitmap idf
, pruned_idf
;
2997 if (TREE_CODE (var
) == SSA_NAME
)
2998 gcc_checking_assert (is_old_name (var
));
3000 gcc_checking_assert (marked_for_renaming (var
));
3002 /* Get all the definition sites for VAR. */
3003 db
= find_def_blocks_for (var
);
3005 /* No need to do anything if there were no definitions to VAR. */
3006 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
3009 /* Compute the initial iterated dominance frontier. */
3010 idf
= compute_idf (db
->def_blocks
, dfs
);
3011 pruned_idf
= BITMAP_ALLOC (NULL
);
3013 if (TREE_CODE (var
) == SSA_NAME
)
3015 if (update_flags
== TODO_update_ssa
)
3017 /* If doing regular SSA updates for GIMPLE registers, we are
3018 only interested in IDF blocks dominated by the nearest
3019 common dominator of all the definition blocks. */
3020 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3022 if (entry
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3023 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
3024 if (BASIC_BLOCK (i
) != entry
3025 && dominated_by_p (CDI_DOMINATORS
, BASIC_BLOCK (i
), entry
))
3026 bitmap_set_bit (pruned_idf
, i
);
3030 /* Otherwise, do not prune the IDF for VAR. */
3031 gcc_checking_assert (update_flags
== TODO_update_ssa_full_phi
);
3032 bitmap_copy (pruned_idf
, idf
);
3037 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3038 for the first time, so we need to compute the full IDF for
3040 bitmap_copy (pruned_idf
, idf
);
3043 if (!bitmap_empty_p (pruned_idf
))
3045 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3046 are included in the region to be updated. The feeding blocks
3047 are important to guarantee that the PHI arguments are renamed
3050 /* FIXME, this is not needed if we are updating symbols. We are
3051 already starting at the ENTRY block anyway. */
3052 bitmap_ior_into (blocks
, pruned_idf
);
3053 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3057 basic_block bb
= BASIC_BLOCK (i
);
3059 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3060 if (e
->src
->index
>= 0)
3061 bitmap_set_bit (blocks
, e
->src
->index
);
3064 insert_phi_nodes_for (var
, pruned_idf
, true);
3067 BITMAP_FREE (pruned_idf
);
3071 /* Sort symbols_to_rename after their DECL_UID. */
3074 insert_updated_phi_nodes_compare_uids (const void *a
, const void *b
)
3076 const_tree syma
= *(const const_tree
*)a
;
3077 const_tree symb
= *(const const_tree
*)b
;
3078 if (DECL_UID (syma
) == DECL_UID (symb
))
3080 return DECL_UID (syma
) < DECL_UID (symb
) ? -1 : 1;
3083 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3084 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3086 1- The names in OLD_SSA_NAMES dominated by the definitions of
3087 NEW_SSA_NAMES are all re-written to be reached by the
3088 appropriate definition from NEW_SSA_NAMES.
3090 2- If needed, new PHI nodes are added to the iterated dominance
3091 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3093 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3094 calling create_new_def_for to create new defs for names that the
3095 caller wants to replace.
3097 The caller cretaes the new names to be inserted and the names that need
3098 to be replaced by calling create_new_def_for for each old definition
3099 to be replaced. Note that the function assumes that the
3100 new defining statement has already been inserted in the IL.
3102 For instance, given the following code:
3105 2 x_1 = PHI (0, x_5)
3116 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3119 2 x_1 = PHI (0, x_5)
3132 We want to replace all the uses of x_1 with the new definitions of
3133 x_10 and x_11. Note that the only uses that should be replaced are
3134 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3135 *not* be replaced (this is why we cannot just mark symbol 'x' for
3138 Additionally, we may need to insert a PHI node at line 11 because
3139 that is a merge point for x_10 and x_11. So the use of x_1 at line
3140 11 will be replaced with the new PHI node. The insertion of PHI
3141 nodes is optional. They are not strictly necessary to preserve the
3142 SSA form, and depending on what the caller inserted, they may not
3143 even be useful for the optimizers. UPDATE_FLAGS controls various
3144 aspects of how update_ssa operates, see the documentation for
3145 TODO_update_ssa*. */
3148 update_ssa (unsigned update_flags
)
3150 basic_block bb
, start_bb
;
3154 sbitmap_iterator sbi
;
3157 /* Only one update flag should be set. */
3158 gcc_assert (update_flags
== TODO_update_ssa
3159 || update_flags
== TODO_update_ssa_no_phi
3160 || update_flags
== TODO_update_ssa_full_phi
3161 || update_flags
== TODO_update_ssa_only_virtuals
);
3163 if (!need_ssa_update_p (cfun
))
3166 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3169 fprintf (dump_file
, "\nUpdating SSA:\n");
3171 if (!update_ssa_initialized_fn
)
3172 init_update_ssa (cfun
);
3173 else if (update_flags
== TODO_update_ssa_only_virtuals
)
3175 /* If we only need to update virtuals, remove all the mappings for
3176 real names before proceeding. The caller is responsible for
3177 having dealt with the name mappings before calling update_ssa. */
3178 bitmap_clear (old_ssa_names
);
3179 bitmap_clear (new_ssa_names
);
3182 gcc_assert (update_ssa_initialized_fn
== cfun
);
3184 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3185 if (!phis_to_rewrite
.exists ())
3186 phis_to_rewrite
.create (last_basic_block
+ 1);
3187 blocks_to_update
= BITMAP_ALLOC (NULL
);
3189 /* Ensure that the dominance information is up-to-date. */
3190 calculate_dominance_info (CDI_DOMINATORS
);
3192 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3194 /* If there are names defined in the replacement table, prepare
3195 definition and use sites for all the names in NEW_SSA_NAMES and
3197 if (bitmap_first_set_bit (new_ssa_names
) >= 0)
3199 prepare_names_to_update (insert_phi_p
);
3201 /* If all the names in NEW_SSA_NAMES had been marked for
3202 removal, and there are no symbols to rename, then there's
3203 nothing else to do. */
3204 if (bitmap_first_set_bit (new_ssa_names
) < 0
3205 && !cfun
->gimple_df
->ssa_renaming_needed
)
3209 /* Next, determine the block at which to start the renaming process. */
3210 if (cfun
->gimple_df
->ssa_renaming_needed
)
3212 /* If we rename bare symbols initialize the mapping to
3213 auxiliar info we need to keep track of. */
3214 var_infos
.create (47);
3216 /* If we have to rename some symbols from scratch, we need to
3217 start the process at the root of the CFG. FIXME, it should
3218 be possible to determine the nearest block that had a
3219 definition for each of the symbols that are marked for
3220 updating. For now this seems more work than it's worth. */
3221 start_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3223 /* Traverse the CFG looking for existing definitions and uses of
3224 symbols in SSA operands. Mark interesting blocks and
3225 statements and set local live-in information for the PHI
3226 placement heuristics. */
3227 prepare_block_for_update (start_bb
, insert_phi_p
);
3229 #ifdef ENABLE_CHECKING
3230 for (i
= 1; i
< num_ssa_names
; ++i
)
3232 tree name
= ssa_name (i
);
3234 || virtual_operand_p (name
))
3237 /* For all but virtual operands, which do not have SSA names
3238 with overlapping life ranges, ensure that symbols marked
3239 for renaming do not have existing SSA names associated with
3240 them as we do not re-write them out-of-SSA before going
3241 into SSA for the remaining symbol uses. */
3242 if (marked_for_renaming (SSA_NAME_VAR (name
)))
3244 fprintf (stderr
, "Existing SSA name for symbol marked for "
3246 print_generic_expr (stderr
, name
, TDF_SLIM
);
3247 fprintf (stderr
, "\n");
3248 internal_error ("SSA corruption");
3255 /* Otherwise, the entry block to the region is the nearest
3256 common dominator for the blocks in BLOCKS. */
3257 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3261 /* If requested, insert PHI nodes at the iterated dominance frontier
3262 of every block, creating new definitions for names in OLD_SSA_NAMES
3263 and for symbols found. */
3268 /* If the caller requested PHI nodes to be added, compute
3269 dominance frontiers. */
3270 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
3272 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
3273 compute_dominance_frontiers (dfs
);
3275 if (bitmap_first_set_bit (old_ssa_names
) >= 0)
3277 sbitmap_iterator sbi
;
3279 /* insert_update_phi_nodes_for will call add_new_name_mapping
3280 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3281 will grow while we are traversing it (but it will not
3282 gain any new members). Copy OLD_SSA_NAMES to a temporary
3284 sbitmap tmp
= sbitmap_alloc (SBITMAP_SIZE (old_ssa_names
));
3285 bitmap_copy (tmp
, old_ssa_names
);
3286 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, sbi
)
3287 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3292 symbols_to_rename
.qsort (insert_updated_phi_nodes_compare_uids
);
3293 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3294 insert_updated_phi_nodes_for (sym
, dfs
, blocks_to_update
,
3298 bitmap_clear (&dfs
[bb
->index
]);
3301 /* Insertion of PHI nodes may have added blocks to the region.
3302 We need to re-compute START_BB to include the newly added
3304 if (start_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3305 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3309 /* Reset the current definition for name and symbol before renaming
3311 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
3312 get_ssa_name_ann (ssa_name (i
))->info
.current_def
= NULL_TREE
;
3314 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3315 get_var_info (sym
)->info
.current_def
= NULL_TREE
;
3317 /* Now start the renaming process at START_BB. */
3318 interesting_blocks
= sbitmap_alloc (last_basic_block
);
3319 bitmap_clear (interesting_blocks
);
3320 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3321 bitmap_set_bit (interesting_blocks
, i
);
3323 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3325 sbitmap_free (interesting_blocks
);
3327 /* Debugging dumps. */
3333 dump_update_ssa (dump_file
);
3335 fprintf (dump_file
, "Incremental SSA update started at block: %d\n",
3339 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3341 fprintf (dump_file
, "Number of blocks in CFG: %d\n", last_basic_block
);
3342 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n",
3343 c
, PERCENT (c
, last_basic_block
));
3345 if (dump_flags
& TDF_DETAILS
)
3347 fprintf (dump_file
, "Affected blocks:");
3348 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3349 fprintf (dump_file
, " %u", i
);
3350 fprintf (dump_file
, "\n");
3353 fprintf (dump_file
, "\n\n");
3356 /* Free allocated memory. */
3358 delete_update_ssa ();
3360 timevar_pop (TV_TREE_SSA_INCREMENTAL
);