1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2020 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 "tree-pass.h"
30 #include "gimple-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "langhooks.h"
34 #include "gimple-iterator.h"
36 #include "tree-into-ssa.h"
40 #include "statistics.h"
41 #include "stringpool.h"
44 #include "attr-fnspec.h"
46 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
48 /* This file builds the SSA form for a function as described in:
49 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
50 Computing Static Single Assignment Form and the Control Dependence
51 Graph. ACM Transactions on Programming Languages and Systems,
52 13(4):451-490, October 1991. */
54 /* Structure to map a variable VAR to the set of blocks that contain
55 definitions for VAR. */
58 /* Blocks that contain definitions of VAR. Bit I will be set if the
59 Ith block contains a definition of VAR. */
62 /* Blocks that contain a PHI node for VAR. */
65 /* Blocks where VAR is live-on-entry. Similar semantics as
70 /* Stack of trees used to restore the global currdefs to its original
71 state after completing rewriting of a block and its dominator
72 children. Its elements have the following properties:
74 - An SSA_NAME (N) indicates that the current definition of the
75 underlying variable should be set to the given SSA_NAME. If the
76 symbol associated with the SSA_NAME is not a GIMPLE register, the
77 next slot in the stack must be a _DECL node (SYM). In this case,
78 the name N in the previous slot is the current reaching
81 - A _DECL node indicates that the underlying variable has no
84 - A NULL node at the top entry is used to mark the last slot
85 associated with the current block. */
86 static vec
<tree
> block_defs_stack
;
89 /* Set of existing SSA names being replaced by update_ssa. */
90 static sbitmap old_ssa_names
;
92 /* Set of new SSA names being added by update_ssa. Note that both
93 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
94 the operations done on them are presence tests. */
95 static sbitmap new_ssa_names
;
97 static sbitmap interesting_blocks
;
99 /* Set of SSA names that have been marked to be released after they
100 were registered in the replacement table. They will be finally
101 released after we finish updating the SSA web. */
102 bitmap names_to_release
;
104 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
105 the to basic block with index I. Allocated once per compilation, *not*
106 released between different functions. */
107 static vec
< vec
<gphi
*> > phis_to_rewrite
;
109 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
110 static bitmap blocks_with_phis_to_rewrite
;
112 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
113 to grow as the callers to create_new_def_for will create new names on
115 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
116 need to find a reasonable growth strategy. */
117 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
120 /* The function the SSA updating data structures have been initialized for.
121 NULL if they need to be initialized by create_new_def_for. */
122 static struct function
*update_ssa_initialized_fn
= NULL
;
124 /* Global data to attach to the main dominator walk structure. */
125 struct mark_def_sites_global_data
127 /* This bitmap contains the variables which are set before they
128 are used in a basic block. */
132 /* It is advantageous to avoid things like life analysis for variables which
133 do not need PHI nodes. This enum describes whether or not a particular
134 variable may need a PHI node. */
136 enum need_phi_state
{
137 /* This is the default. If we are still in this state after finding
138 all the definition and use sites, then we will assume the variable
139 needs PHI nodes. This is probably an overly conservative assumption. */
140 NEED_PHI_STATE_UNKNOWN
,
142 /* This state indicates that we have seen one or more sets of the
143 variable in a single basic block and that the sets dominate all
144 uses seen so far. If after finding all definition and use sites
145 we are still in this state, then the variable does not need any
149 /* This state indicates that we have either seen multiple definitions of
150 the variable in multiple blocks, or that we encountered a use in a
151 block that was not dominated by the block containing the set(s) of
152 this variable. This variable is assumed to need PHI nodes. */
156 /* Information stored for both SSA names and decls. */
159 /* This field indicates whether or not the variable may need PHI nodes.
160 See the enum's definition for more detailed information about the
162 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
164 /* The current reaching definition replacing this var. */
167 /* Definitions for this var. */
168 struct def_blocks def_blocks
;
171 /* Information stored for decls. */
177 /* Information stored for both SSA names and decls. */
182 /* VAR_INFOS hashtable helpers. */
184 struct var_info_hasher
: free_ptr_hash
<var_info
>
186 static inline hashval_t
hash (const value_type
&);
187 static inline bool equal (const value_type
&, const compare_type
&);
191 var_info_hasher::hash (const value_type
&p
)
193 return DECL_UID (p
->var
);
197 var_info_hasher::equal (const value_type
&p1
, const compare_type
&p2
)
199 return p1
->var
== p2
->var
;
203 /* Each entry in VAR_INFOS contains an element of type STRUCT
205 static hash_table
<var_info_hasher
> *var_infos
;
208 /* Information stored for SSA names. */
211 /* Age of this record (so that info_for_ssa_name table can be cleared
212 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
213 are assumed to be null. */
216 /* Replacement mappings, allocated from update_ssa_obstack. */
219 /* Information stored for both SSA names and decls. */
223 static vec
<ssa_name_info
*> info_for_ssa_name
;
224 static unsigned current_info_for_ssa_name_age
;
226 static bitmap_obstack update_ssa_obstack
;
228 /* The set of blocks affected by update_ssa. */
229 static bitmap blocks_to_update
;
231 /* The main entry point to the SSA renamer (rewrite_blocks) may be
232 called several times to do different, but related, tasks.
233 Initially, we need it to rename the whole program into SSA form.
234 At other times, we may need it to only rename into SSA newly
235 exposed symbols. Finally, we can also call it to incrementally fix
236 an already built SSA web. */
238 /* Convert the whole function into SSA form. */
241 /* Incrementally update the SSA web by replacing existing SSA
242 names with new ones. See update_ssa for details. */
246 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
247 static bitmap symbols_to_rename_set
;
248 static vec
<tree
> symbols_to_rename
;
250 /* Mark SYM for renaming. */
253 mark_for_renaming (tree sym
)
255 if (!symbols_to_rename_set
)
256 symbols_to_rename_set
= BITMAP_ALLOC (NULL
);
257 if (bitmap_set_bit (symbols_to_rename_set
, DECL_UID (sym
)))
258 symbols_to_rename
.safe_push (sym
);
261 /* Return true if SYM is marked for renaming. */
264 marked_for_renaming (tree sym
)
266 if (!symbols_to_rename_set
|| sym
== NULL_TREE
)
268 return bitmap_bit_p (symbols_to_rename_set
, DECL_UID (sym
));
272 /* Return true if STMT needs to be rewritten. When renaming a subset
273 of the variables, not all statements will be processed. This is
274 decided in mark_def_sites. */
277 rewrite_uses_p (gimple
*stmt
)
279 return gimple_visited_p (stmt
);
283 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
286 set_rewrite_uses (gimple
*stmt
, bool rewrite_p
)
288 gimple_set_visited (stmt
, rewrite_p
);
292 /* Return true if the DEFs created by statement STMT should be
293 registered when marking new definition sites. This is slightly
294 different than rewrite_uses_p: it's used by update_ssa to
295 distinguish statements that need to have both uses and defs
296 processed from those that only need to have their defs processed.
297 Statements that define new SSA names only need to have their defs
298 registered, but they don't need to have their uses renamed. */
301 register_defs_p (gimple
*stmt
)
303 return gimple_plf (stmt
, GF_PLF_1
) != 0;
307 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
310 set_register_defs (gimple
*stmt
, bool register_defs_p
)
312 gimple_set_plf (stmt
, GF_PLF_1
, register_defs_p
);
316 /* Get the information associated with NAME. */
318 static inline ssa_name_info
*
319 get_ssa_name_ann (tree name
)
321 unsigned ver
= SSA_NAME_VERSION (name
);
322 unsigned len
= info_for_ssa_name
.length ();
323 struct ssa_name_info
*info
;
325 /* Re-allocate the vector at most once per update/into-SSA. */
327 info_for_ssa_name
.safe_grow_cleared (num_ssa_names
, true);
329 /* But allocate infos lazily. */
330 info
= info_for_ssa_name
[ver
];
333 info
= XCNEW (struct ssa_name_info
);
334 info
->age
= current_info_for_ssa_name_age
;
335 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
336 info_for_ssa_name
[ver
] = info
;
339 if (info
->age
< current_info_for_ssa_name_age
)
341 info
->age
= current_info_for_ssa_name_age
;
342 info
->repl_set
= NULL
;
343 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
344 info
->info
.current_def
= NULL_TREE
;
345 info
->info
.def_blocks
.def_blocks
= NULL
;
346 info
->info
.def_blocks
.phi_blocks
= NULL
;
347 info
->info
.def_blocks
.livein_blocks
= NULL
;
353 /* Return and allocate the auxiliar information for DECL. */
355 static inline var_info
*
356 get_var_info (tree decl
)
361 slot
= var_infos
->find_slot_with_hash (&vi
, DECL_UID (decl
), INSERT
);
364 var_info
*v
= XCNEW (var_info
);
373 /* Clears info for SSA names. */
376 clear_ssa_name_info (void)
378 current_info_for_ssa_name_age
++;
380 /* If current_info_for_ssa_name_age wraps we use stale information.
381 Asser that this does not happen. */
382 gcc_assert (current_info_for_ssa_name_age
!= 0);
386 /* Get access to the auxiliar information stored per SSA name or decl. */
388 static inline common_info
*
389 get_common_info (tree var
)
391 if (TREE_CODE (var
) == SSA_NAME
)
392 return &get_ssa_name_ann (var
)->info
;
394 return &get_var_info (var
)->info
;
398 /* Return the current definition for VAR. */
401 get_current_def (tree var
)
403 return get_common_info (var
)->current_def
;
407 /* Sets current definition of VAR to DEF. */
410 set_current_def (tree var
, tree def
)
412 get_common_info (var
)->current_def
= def
;
415 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
416 all statements in basic block BB. */
419 initialize_flags_in_bb (basic_block bb
)
422 gimple_stmt_iterator gsi
;
424 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
426 gimple
*phi
= gsi_stmt (gsi
);
427 set_rewrite_uses (phi
, false);
428 set_register_defs (phi
, false);
431 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
433 stmt
= gsi_stmt (gsi
);
435 /* We are going to use the operand cache API, such as
436 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
437 cache for each statement should be up-to-date. */
438 gcc_checking_assert (!gimple_modified_p (stmt
));
439 set_rewrite_uses (stmt
, false);
440 set_register_defs (stmt
, false);
444 /* Mark block BB as interesting for update_ssa. */
447 mark_block_for_update (basic_block bb
)
449 gcc_checking_assert (blocks_to_update
!= NULL
);
450 if (!bitmap_set_bit (blocks_to_update
, bb
->index
))
452 initialize_flags_in_bb (bb
);
455 /* Return the set of blocks where variable VAR is defined and the blocks
456 where VAR is live on entry (livein). If no entry is found in
457 DEF_BLOCKS, a new one is created and returned. */
459 static inline def_blocks
*
460 get_def_blocks_for (common_info
*info
)
462 def_blocks
*db_p
= &info
->def_blocks
;
463 if (!db_p
->def_blocks
)
465 db_p
->def_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
466 db_p
->phi_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
467 db_p
->livein_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
474 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
475 VAR is defined by a PHI node. */
478 set_def_block (tree var
, basic_block bb
, bool phi_p
)
483 info
= get_common_info (var
);
484 db_p
= get_def_blocks_for (info
);
486 /* Set the bit corresponding to the block where VAR is defined. */
487 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
489 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
491 /* Keep track of whether or not we may need to insert PHI nodes.
493 If we are in the UNKNOWN state, then this is the first definition
494 of VAR. Additionally, we have not seen any uses of VAR yet, so
495 we do not need a PHI node for this variable at this time (i.e.,
496 transition to NEED_PHI_STATE_NO).
498 If we are in any other state, then we either have multiple definitions
499 of this variable occurring in different blocks or we saw a use of the
500 variable which was not dominated by the block containing the
501 definition(s). In this case we may need a PHI node, so enter
502 state NEED_PHI_STATE_MAYBE. */
503 if (info
->need_phi_state
== NEED_PHI_STATE_UNKNOWN
)
504 info
->need_phi_state
= NEED_PHI_STATE_NO
;
506 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
510 /* Mark block BB as having VAR live at the entry to BB. */
513 set_livein_block (tree var
, basic_block bb
)
518 info
= get_common_info (var
);
519 db_p
= get_def_blocks_for (info
);
521 /* Set the bit corresponding to the block where VAR is live in. */
522 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
524 /* Keep track of whether or not we may need to insert PHI nodes.
526 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
527 by the single block containing the definition(s) of this variable. If
528 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
529 NEED_PHI_STATE_MAYBE. */
530 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
532 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
534 if (def_block_index
== -1
535 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
536 BASIC_BLOCK_FOR_FN (cfun
, def_block_index
)))
537 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
540 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
544 /* Return true if NAME is in OLD_SSA_NAMES. */
547 is_old_name (tree name
)
549 unsigned ver
= SSA_NAME_VERSION (name
);
552 return (ver
< SBITMAP_SIZE (old_ssa_names
)
553 && bitmap_bit_p (old_ssa_names
, ver
));
557 /* Return true if NAME is in NEW_SSA_NAMES. */
560 is_new_name (tree name
)
562 unsigned ver
= SSA_NAME_VERSION (name
);
565 return (ver
< SBITMAP_SIZE (new_ssa_names
)
566 && bitmap_bit_p (new_ssa_names
, ver
));
570 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
573 names_replaced_by (tree new_tree
)
575 return get_ssa_name_ann (new_tree
)->repl_set
;
579 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
582 add_to_repl_tbl (tree new_tree
, tree old
)
584 bitmap
*set
= &get_ssa_name_ann (new_tree
)->repl_set
;
586 *set
= BITMAP_ALLOC (&update_ssa_obstack
);
587 bitmap_set_bit (*set
, SSA_NAME_VERSION (old
));
591 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
592 represents the set of names O_1 ... O_j replaced by N_i. This is
593 used by update_ssa and its helpers to introduce new SSA names in an
594 already formed SSA web. */
597 add_new_name_mapping (tree new_tree
, tree old
)
599 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
600 gcc_checking_assert (new_tree
!= old
601 && SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
603 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
604 caller may have created new names since the set was created. */
605 if (SBITMAP_SIZE (new_ssa_names
) <= num_ssa_names
- 1)
607 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
608 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
609 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
612 /* Update the REPL_TBL table. */
613 add_to_repl_tbl (new_tree
, old
);
615 /* If OLD had already been registered as a new name, then all the
616 names that OLD replaces should also be replaced by NEW_TREE. */
617 if (is_new_name (old
))
618 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
620 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
622 bitmap_set_bit (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
623 bitmap_set_bit (old_ssa_names
, SSA_NAME_VERSION (old
));
627 /* Call back for walk_dominator_tree used to collect definition sites
628 for every variable in the function. For every statement S in block
631 1- Variables defined by S in the DEFS of S are marked in the bitmap
634 2- If S uses a variable VAR and there is no preceding kill of VAR,
635 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
637 This information is used to determine which variables are live
638 across block boundaries to reduce the number of PHI nodes
642 mark_def_sites (basic_block bb
, gimple
*stmt
, bitmap kills
)
648 /* Since this is the first time that we rewrite the program into SSA
649 form, force an operand scan on every statement. */
652 gcc_checking_assert (blocks_to_update
== NULL
);
653 set_register_defs (stmt
, false);
654 set_rewrite_uses (stmt
, false);
656 if (is_gimple_debug (stmt
))
658 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
660 tree sym
= USE_FROM_PTR (use_p
);
661 gcc_checking_assert (DECL_P (sym
));
662 set_rewrite_uses (stmt
, true);
664 if (rewrite_uses_p (stmt
))
665 bitmap_set_bit (interesting_blocks
, bb
->index
);
669 /* If a variable is used before being set, then the variable is live
670 across a block boundary, so mark it live-on-entry to BB. */
671 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
673 tree sym
= USE_FROM_PTR (use_p
);
674 if (TREE_CODE (sym
) == SSA_NAME
)
676 gcc_checking_assert (DECL_P (sym
));
677 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
678 set_livein_block (sym
, bb
);
679 set_rewrite_uses (stmt
, true);
682 /* Now process the defs. Mark BB as the definition block and add
683 each def to the set of killed symbols. */
684 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
686 if (TREE_CODE (def
) == SSA_NAME
)
688 gcc_checking_assert (DECL_P (def
));
689 set_def_block (def
, bb
, false);
690 bitmap_set_bit (kills
, DECL_UID (def
));
691 set_register_defs (stmt
, true);
694 /* If we found the statement interesting then also mark the block BB
696 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
697 bitmap_set_bit (interesting_blocks
, bb
->index
);
700 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
701 in the dfs numbering of the dominance tree. */
705 /* Basic block whose index this entry corresponds to. */
708 /* The dfs number of this node. */
712 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
716 cmp_dfsnum (const void *a
, const void *b
)
718 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
719 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
721 return (int) da
->dfs_num
- (int) db
->dfs_num
;
724 /* Among the intervals starting at the N points specified in DEFS, find
725 the one that contains S, and return its bb_index. */
728 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
730 unsigned f
= 0, t
= n
, m
;
735 if (defs
[m
].dfs_num
<= s
)
741 return defs
[f
].bb_index
;
744 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
745 KILLS is a bitmap of blocks where the value is defined before any use. */
748 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
751 unsigned i
, b
, p
, u
, top
;
753 basic_block def_bb
, use_bb
;
757 struct dom_dfsnum
*defs
;
758 unsigned n_defs
, adef
;
760 if (bitmap_empty_p (uses
))
766 /* The phi must dominate a use, or an argument of a live phi. Also, we
767 do not create any phi nodes in def blocks, unless they are also livein. */
768 to_remove
= BITMAP_ALLOC (NULL
);
769 bitmap_and_compl (to_remove
, kills
, uses
);
770 bitmap_and_compl_into (phis
, to_remove
);
771 if (bitmap_empty_p (phis
))
773 BITMAP_FREE (to_remove
);
777 /* We want to remove the unnecessary phi nodes, but we do not want to compute
778 liveness information, as that may be linear in the size of CFG, and if
779 there are lot of different variables to rewrite, this may lead to quadratic
782 Instead, we basically emulate standard dce. We put all uses to worklist,
783 then for each of them find the nearest def that dominates them. If this
784 def is a phi node, we mark it live, and if it was not live before, we
785 add the predecessors of its basic block to the worklist.
787 To quickly locate the nearest def that dominates use, we use dfs numbering
788 of the dominance tree (that is already available in order to speed up
789 queries). For each def, we have the interval given by the dfs number on
790 entry to and on exit from the corresponding subtree in the dominance tree.
791 The nearest dominator for a given use is the smallest of these intervals
792 that contains entry and exit dfs numbers for the basic block with the use.
793 If we store the bounds for all the uses to an array and sort it, we can
794 locate the nearest dominating def in logarithmic time by binary search.*/
795 bitmap_ior (to_remove
, kills
, phis
);
796 n_defs
= bitmap_count_bits (to_remove
);
797 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
798 defs
[0].bb_index
= 1;
801 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
803 def_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
804 defs
[adef
].bb_index
= i
;
805 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
806 defs
[adef
+ 1].bb_index
= i
;
807 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
810 BITMAP_FREE (to_remove
);
811 gcc_assert (adef
== 2 * n_defs
+ 1);
812 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
813 gcc_assert (defs
[0].bb_index
== 1);
815 /* Now each DEFS entry contains the number of the basic block to that the
816 dfs number corresponds. Change them to the number of basic block that
817 corresponds to the interval following the dfs number. Also, for the
818 dfs_out numbers, increase the dfs number by one (so that it corresponds
819 to the start of the following interval, not to the end of the current
820 one). We use WORKLIST as a stack. */
821 auto_vec
<int> worklist (n_defs
+ 1);
822 worklist
.quick_push (1);
825 for (i
= 1; i
< adef
; i
++)
827 b
= defs
[i
].bb_index
;
830 /* This is a closing element. Interval corresponding to the top
831 of the stack after removing it follows. */
833 top
= worklist
[worklist
.length () - 1];
834 defs
[n_defs
].bb_index
= top
;
835 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
839 /* Opening element. Nothing to do, just push it to the stack and move
840 it to the correct position. */
841 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
842 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
843 worklist
.quick_push (b
);
847 /* If this interval starts at the same point as the previous one, cancel
849 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
850 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
855 gcc_assert (worklist
.is_empty ());
857 /* Now process the uses. */
858 live_phis
= BITMAP_ALLOC (NULL
);
859 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
861 worklist
.safe_push (i
);
864 while (!worklist
.is_empty ())
867 if (b
== ENTRY_BLOCK
)
870 /* If there is a phi node in USE_BB, it is made live. Otherwise,
871 find the def that dominates the immediate dominator of USE_BB
872 (the kill in USE_BB does not dominate the use). */
873 if (bitmap_bit_p (phis
, b
))
877 use_bb
= get_immediate_dominator (CDI_DOMINATORS
,
878 BASIC_BLOCK_FOR_FN (cfun
, b
));
879 p
= find_dfsnum_interval (defs
, n_defs
,
880 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
881 if (!bitmap_bit_p (phis
, p
))
885 /* If the phi node is already live, there is nothing to do. */
886 if (!bitmap_set_bit (live_phis
, p
))
889 /* Add the new uses to the worklist. */
890 def_bb
= BASIC_BLOCK_FOR_FN (cfun
, p
);
891 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
894 if (bitmap_bit_p (uses
, u
))
897 /* In case there is a kill directly in the use block, do not record
898 the use (this is also necessary for correctness, as we assume that
899 uses dominated by a def directly in their block have been filtered
901 if (bitmap_bit_p (kills
, u
))
904 bitmap_set_bit (uses
, u
);
905 worklist
.safe_push (u
);
909 bitmap_copy (phis
, live_phis
);
910 BITMAP_FREE (live_phis
);
914 /* Return the set of blocks where variable VAR is defined and the blocks
915 where VAR is live on entry (livein). Return NULL, if no entry is
916 found in DEF_BLOCKS. */
918 static inline def_blocks
*
919 find_def_blocks_for (tree var
)
921 def_blocks
*p
= &get_common_info (var
)->def_blocks
;
928 /* Marks phi node PHI in basic block BB for rewrite. */
931 mark_phi_for_rewrite (basic_block bb
, gphi
*phi
)
934 unsigned n
, idx
= bb
->index
;
936 if (rewrite_uses_p (phi
))
939 set_rewrite_uses (phi
, true);
941 if (!blocks_with_phis_to_rewrite
)
944 if (bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
))
946 n
= (unsigned) last_basic_block_for_fn (cfun
) + 1;
947 if (phis_to_rewrite
.length () < n
)
948 phis_to_rewrite
.safe_grow_cleared (n
, true);
950 phis
= phis_to_rewrite
[idx
];
951 gcc_assert (!phis
.exists ());
955 phis
= phis_to_rewrite
[idx
];
957 phis
.safe_push (phi
);
958 phis_to_rewrite
[idx
] = phis
;
961 /* Insert PHI nodes for variable VAR using the iterated dominance
962 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
963 function assumes that the caller is incrementally updating the
964 existing SSA form, in which case VAR may be an SSA name instead of
967 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
968 PHI node for VAR. On exit, only the nodes that received a PHI node
969 for VAR will be present in PHI_INSERTION_POINTS. */
972 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
979 def_blocks
*def_map
= find_def_blocks_for (var
);
981 /* Remove the blocks where we already have PHI nodes for VAR. */
982 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
984 /* Remove obviously useless phi nodes. */
985 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
986 def_map
->livein_blocks
);
988 /* And insert the PHI nodes. */
989 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
991 bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
993 mark_block_for_update (bb
);
995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
997 fprintf (dump_file
, "creating PHI node in block #%d for ", bb_index
);
998 print_generic_expr (dump_file
, var
, TDF_SLIM
);
999 fprintf (dump_file
, "\n");
1003 if (TREE_CODE (var
) == SSA_NAME
)
1005 /* If we are rewriting SSA names, create the LHS of the PHI
1006 node by duplicating VAR. This is useful in the case of
1007 pointers, to also duplicate pointer attributes (alias
1008 information, in particular). */
1012 gcc_checking_assert (update_p
);
1013 new_lhs
= duplicate_ssa_name (var
, NULL
);
1014 phi
= create_phi_node (new_lhs
, bb
);
1015 add_new_name_mapping (new_lhs
, var
);
1017 /* Add VAR to every argument slot of PHI. We need VAR in
1018 every argument so that rewrite_update_phi_arguments knows
1019 which name is this PHI node replacing. If VAR is a
1020 symbol marked for renaming, this is not necessary, the
1021 renamer will use the symbol on the LHS to get its
1022 reaching definition. */
1023 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1024 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1030 gcc_checking_assert (DECL_P (var
));
1031 phi
= create_phi_node (var
, bb
);
1033 tracked_var
= target_for_debug_bind (var
);
1036 gimple
*note
= gimple_build_debug_bind (tracked_var
,
1039 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1040 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1044 /* Mark this PHI node as interesting for update_ssa. */
1045 set_register_defs (phi
, true);
1046 mark_phi_for_rewrite (bb
, phi
);
1050 /* Sort var_infos after DECL_UID of their var. */
1053 insert_phi_nodes_compare_var_infos (const void *a
, const void *b
)
1055 const var_info
*defa
= *(var_info
* const *)a
;
1056 const var_info
*defb
= *(var_info
* const *)b
;
1057 if (DECL_UID (defa
->var
) < DECL_UID (defb
->var
))
1063 /* Insert PHI nodes at the dominance frontier of blocks with variable
1064 definitions. DFS contains the dominance frontier information for
1068 insert_phi_nodes (bitmap_head
*dfs
)
1070 hash_table
<var_info_hasher
>::iterator hi
;
1074 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1076 /* When the gimplifier introduces SSA names it cannot easily avoid
1077 situations where abnormal edges added by CFG construction break
1078 the use-def dominance requirement. For this case rewrite SSA
1079 names with broken use-def dominance out-of-SSA and register them
1080 for PHI insertion. We only need to do this if abnormal edges
1081 can appear in the function. */
1083 if (cfun
->calls_setjmp
1084 || cfun
->has_nonlocal_label
)
1085 FOR_EACH_SSA_NAME (i
, name
, cfun
)
1087 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1088 if (SSA_NAME_IS_DEFAULT_DEF (name
))
1091 basic_block def_bb
= gimple_bb (def_stmt
);
1092 imm_use_iterator it
;
1094 bool need_phis
= false;
1095 FOR_EACH_IMM_USE_STMT (use_stmt
, it
, name
)
1097 basic_block use_bb
= gimple_bb (use_stmt
);
1098 if (use_bb
!= def_bb
1099 && ! dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1104 tree var
= create_tmp_reg (TREE_TYPE (name
));
1105 use_operand_p use_p
;
1106 FOR_EACH_IMM_USE_STMT (use_stmt
, it
, name
)
1108 basic_block use_bb
= gimple_bb (use_stmt
);
1109 FOR_EACH_IMM_USE_ON_STMT (use_p
, it
)
1110 SET_USE (use_p
, var
);
1111 update_stmt (use_stmt
);
1112 set_livein_block (var
, use_bb
);
1113 set_rewrite_uses (use_stmt
, true);
1114 bitmap_set_bit (interesting_blocks
, use_bb
->index
);
1116 def_operand_p def_p
;
1118 FOR_EACH_SSA_DEF_OPERAND (def_p
, def_stmt
, dit
, SSA_OP_DEF
)
1119 if (DEF_FROM_PTR (def_p
) == name
)
1120 SET_DEF (def_p
, var
);
1121 update_stmt (def_stmt
);
1122 set_def_block (var
, def_bb
, false);
1123 set_register_defs (def_stmt
, true);
1124 bitmap_set_bit (interesting_blocks
, def_bb
->index
);
1125 release_ssa_name (name
);
1129 auto_vec
<var_info
*> vars (var_infos
->elements ());
1130 FOR_EACH_HASH_TABLE_ELEMENT (*var_infos
, info
, var_info_p
, hi
)
1131 if (info
->info
.need_phi_state
!= NEED_PHI_STATE_NO
)
1132 vars
.quick_push (info
);
1134 /* Do two stages to avoid code generation differences for UID
1135 differences but no UID ordering differences. */
1136 vars
.qsort (insert_phi_nodes_compare_var_infos
);
1138 FOR_EACH_VEC_ELT (vars
, i
, info
)
1140 bitmap idf
= compute_idf (info
->info
.def_blocks
.def_blocks
, dfs
);
1141 insert_phi_nodes_for (info
->var
, idf
, false);
1145 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1149 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1150 register DEF (an SSA_NAME) to be a new definition for SYM. */
1153 register_new_def (tree def
, tree sym
)
1155 common_info
*info
= get_common_info (sym
);
1158 /* If this variable is set in a single basic block and all uses are
1159 dominated by the set(s) in that single basic block, then there is
1160 no reason to record anything for this variable in the block local
1161 definition stacks. Doing so just wastes time and memory.
1163 This is the same test to prune the set of variables which may
1164 need PHI nodes. So we just use that information since it's already
1165 computed and available for us to use. */
1166 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1168 info
->current_def
= def
;
1172 currdef
= info
->current_def
;
1174 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1175 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1176 in the stack so that we know which symbol is being defined by
1177 this SSA name when we unwind the stack. */
1178 if (currdef
&& !is_gimple_reg (sym
))
1179 block_defs_stack
.safe_push (sym
);
1181 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1182 stack is later used by the dominator tree callbacks to restore
1183 the reaching definitions for all the variables defined in the
1184 block after a recursive visit to all its immediately dominated
1185 blocks. If there is no current reaching definition, then just
1186 record the underlying _DECL node. */
1187 block_defs_stack
.safe_push (currdef
? currdef
: sym
);
1189 /* Set the current reaching definition for SYM to be DEF. */
1190 info
->current_def
= def
;
1194 /* Perform a depth-first traversal of the dominator tree looking for
1195 variables to rename. BB is the block where to start searching.
1196 Renaming is a five step process:
1198 1- Every definition made by PHI nodes at the start of the blocks is
1199 registered as the current definition for the corresponding variable.
1201 2- Every statement in BB is rewritten. USE and VUSE operands are
1202 rewritten with their corresponding reaching definition. DEF and
1203 VDEF targets are registered as new definitions.
1205 3- All the PHI nodes in successor blocks of BB are visited. The
1206 argument corresponding to BB is replaced with its current reaching
1209 4- Recursively rewrite every dominator child block of BB.
1211 5- Restore (in reverse order) the current reaching definition for every
1212 new definition introduced in this block. This is done so that when
1213 we return from the recursive call, all the current reaching
1214 definitions are restored to the names that were valid in the
1215 dominator parent of BB. */
1217 /* Return the current definition for variable VAR. If none is found,
1218 create a new SSA name to act as the zeroth definition for VAR. */
1221 get_reaching_def (tree var
)
1223 common_info
*info
= get_common_info (var
);
1226 /* Lookup the current reaching definition for VAR. */
1227 currdef
= info
->current_def
;
1229 /* If there is no reaching definition for VAR, create and register a
1230 default definition for it (if needed). */
1231 if (currdef
== NULL_TREE
)
1233 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1235 sym
= create_tmp_reg (TREE_TYPE (var
));
1236 currdef
= get_or_create_ssa_default_def (cfun
, sym
);
1239 /* Return the current reaching definition for VAR, or the default
1240 definition, if we had to create one. */
1245 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1248 rewrite_debug_stmt_uses (gimple
*stmt
)
1250 use_operand_p use_p
;
1252 bool update
= false;
1254 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1256 tree var
= USE_FROM_PTR (use_p
), def
;
1257 common_info
*info
= get_common_info (var
);
1258 gcc_checking_assert (DECL_P (var
));
1259 def
= info
->current_def
;
1262 if (TREE_CODE (var
) == PARM_DECL
1263 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun
)))
1265 gimple_stmt_iterator gsi
1267 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1269 /* Search a few source bind stmts at the start of first bb to
1270 see if a DEBUG_EXPR_DECL can't be reused. */
1272 !gsi_end_p (gsi
) && lim
> 0;
1273 gsi_next (&gsi
), lim
--)
1275 gimple
*gstmt
= gsi_stmt (gsi
);
1276 if (!gimple_debug_source_bind_p (gstmt
))
1278 if (gimple_debug_source_bind_get_value (gstmt
) == var
)
1280 def
= gimple_debug_source_bind_get_var (gstmt
);
1281 if (TREE_CODE (def
) == DEBUG_EXPR_DECL
)
1287 /* If not, add a new source bind stmt. */
1288 if (def
== NULL_TREE
)
1291 def
= make_node (DEBUG_EXPR_DECL
);
1292 def_temp
= gimple_build_debug_source_bind (def
, var
, NULL
);
1293 DECL_ARTIFICIAL (def
) = 1;
1294 TREE_TYPE (def
) = TREE_TYPE (var
);
1295 SET_DECL_MODE (def
, DECL_MODE (var
));
1297 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1298 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
1305 /* Check if info->current_def can be trusted. */
1306 basic_block bb
= gimple_bb (stmt
);
1308 = SSA_NAME_IS_DEFAULT_DEF (def
)
1309 ? NULL
: gimple_bb (SSA_NAME_DEF_STMT (def
));
1311 /* If definition is in current bb, it is fine. */
1314 /* If definition bb doesn't dominate the current bb,
1315 it can't be used. */
1316 else if (def_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
1318 /* If there is just one definition and dominates the current
1320 else if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1324 def_blocks
*db_p
= get_def_blocks_for (info
);
1326 /* If there are some non-debug uses in the current bb,
1328 if (bitmap_bit_p (db_p
->livein_blocks
, bb
->index
))
1330 /* Otherwise give up for now. */
1337 gimple_debug_bind_reset_value (stmt
);
1341 SET_USE (use_p
, def
);
1347 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1348 the block with its immediate reaching definitions. Update the current
1349 definition of a variable when a new real or virtual definition is found. */
1352 rewrite_stmt (gimple_stmt_iterator
*si
)
1354 use_operand_p use_p
;
1355 def_operand_p def_p
;
1357 gimple
*stmt
= gsi_stmt (*si
);
1359 /* If mark_def_sites decided that we don't need to rewrite this
1360 statement, ignore it. */
1361 gcc_assert (blocks_to_update
== NULL
);
1362 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1367 fprintf (dump_file
, "Renaming statement ");
1368 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1369 fprintf (dump_file
, "\n");
1372 /* Step 1. Rewrite USES in the statement. */
1373 if (rewrite_uses_p (stmt
))
1375 if (is_gimple_debug (stmt
))
1376 rewrite_debug_stmt_uses (stmt
);
1378 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1380 tree var
= USE_FROM_PTR (use_p
);
1381 if (TREE_CODE (var
) == SSA_NAME
)
1383 gcc_checking_assert (DECL_P (var
));
1384 SET_USE (use_p
, get_reaching_def (var
));
1388 /* Step 2. Register the statement's DEF operands. */
1389 if (register_defs_p (stmt
))
1390 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1392 tree var
= DEF_FROM_PTR (def_p
);
1396 if (TREE_CODE (var
) == SSA_NAME
)
1398 gcc_checking_assert (DECL_P (var
));
1400 if (gimple_clobber_p (stmt
)
1401 && is_gimple_reg (var
))
1403 /* If we rewrite a DECL into SSA form then drop its
1404 clobber stmts and replace uses with a new default def. */
1405 gcc_checking_assert (VAR_P (var
) && !gimple_vdef (stmt
));
1406 gsi_replace (si
, gimple_build_nop (), true);
1407 register_new_def (get_or_create_ssa_default_def (cfun
, var
), var
);
1411 name
= make_ssa_name (var
, stmt
);
1412 SET_DEF (def_p
, name
);
1413 register_new_def (DEF_FROM_PTR (def_p
), var
);
1415 /* Do not insert debug stmts if the stmt ends the BB. */
1416 if (stmt_ends_bb_p (stmt
))
1419 tracked_var
= target_for_debug_bind (var
);
1422 gimple
*note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1423 gsi_insert_after (si
, note
, GSI_SAME_STMT
);
1429 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1430 PHI nodes. For every PHI node found, add a new argument containing the
1431 current reaching definition for the variable and the edge through which
1432 that definition is reaching the PHI node. */
1435 rewrite_add_phi_arguments (basic_block bb
)
1440 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1445 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1452 res
= gimple_phi_result (phi
);
1453 currdef
= get_reaching_def (SSA_NAME_VAR (res
));
1454 /* Virtual operand PHI args do not need a location. */
1455 if (virtual_operand_p (res
))
1456 loc
= UNKNOWN_LOCATION
;
1458 loc
= gimple_location (SSA_NAME_DEF_STMT (currdef
));
1459 add_phi_arg (phi
, currdef
, e
, loc
);
1464 class rewrite_dom_walker
: public dom_walker
1467 rewrite_dom_walker (cdi_direction direction
)
1468 : dom_walker (direction
, ALL_BLOCKS
, NULL
) {}
1470 virtual edge
before_dom_children (basic_block
);
1471 virtual void after_dom_children (basic_block
);
1474 /* SSA Rewriting Step 1. Initialization, create a block local stack
1475 of reaching definitions for new SSA names produced in this block
1476 (BLOCK_DEFS). Register new definitions for every PHI node in the
1480 rewrite_dom_walker::before_dom_children (basic_block bb
)
1482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1483 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1485 /* Mark the unwind point for this block. */
1486 block_defs_stack
.safe_push (NULL_TREE
);
1488 /* Step 1. Register new definitions for every PHI node in the block.
1489 Conceptually, all the PHI nodes are executed in parallel and each PHI
1490 node introduces a new version for the associated variable. */
1491 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1494 tree result
= gimple_phi_result (gsi_stmt (gsi
));
1495 register_new_def (result
, SSA_NAME_VAR (result
));
1498 /* Step 2. Rewrite every variable used in each statement in the block
1499 with its immediate reaching definitions. Update the current definition
1500 of a variable when a new real or virtual definition is found. */
1501 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
1502 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1504 rewrite_stmt (&gsi
);
1506 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1507 For every PHI node found, add a new argument containing the current
1508 reaching definition for the variable and the edge through which that
1509 definition is reaching the PHI node. */
1510 rewrite_add_phi_arguments (bb
);
1517 /* Called after visiting all the statements in basic block BB and all
1518 of its dominator children. Restore CURRDEFS to its original value. */
1521 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
1523 /* Restore CURRDEFS to its original state. */
1524 while (block_defs_stack
.length () > 0)
1526 tree tmp
= block_defs_stack
.pop ();
1527 tree saved_def
, var
;
1529 if (tmp
== NULL_TREE
)
1532 if (TREE_CODE (tmp
) == SSA_NAME
)
1534 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1535 current definition of its underlying variable. Note that
1536 if the SSA_NAME is not for a GIMPLE register, the symbol
1537 being defined is stored in the next slot in the stack.
1538 This mechanism is needed because an SSA name for a
1539 non-register symbol may be the definition for more than
1540 one symbol (e.g., SFTs, aliased variables, etc). */
1542 var
= SSA_NAME_VAR (saved_def
);
1543 if (!is_gimple_reg (var
))
1544 var
= block_defs_stack
.pop ();
1548 /* If we recorded anything else, it must have been a _DECL
1549 node and its current reaching definition must have been
1555 get_common_info (var
)->current_def
= saved_def
;
1560 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1563 debug_decl_set (bitmap set
)
1565 dump_decl_set (stderr
, set
);
1566 fprintf (stderr
, "\n");
1570 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1571 stack up to a maximum of N levels. If N is -1, the whole stack is
1572 dumped. New levels are created when the dominator tree traversal
1573 used for renaming enters a new sub-tree. */
1576 dump_defs_stack (FILE *file
, int n
)
1580 fprintf (file
, "\n\nRenaming stack");
1582 fprintf (file
, " (up to %d levels)", n
);
1583 fprintf (file
, "\n\n");
1586 fprintf (file
, "Level %d (current level)\n", i
);
1587 for (j
= (int) block_defs_stack
.length () - 1; j
>= 0; j
--)
1591 name
= block_defs_stack
[j
];
1592 if (name
== NULL_TREE
)
1597 fprintf (file
, "\nLevel %d\n", i
);
1608 var
= SSA_NAME_VAR (name
);
1609 if (!is_gimple_reg (var
))
1612 var
= block_defs_stack
[j
];
1616 fprintf (file
, " Previous CURRDEF (");
1617 print_generic_expr (file
, var
);
1618 fprintf (file
, ") = ");
1620 print_generic_expr (file
, name
);
1622 fprintf (file
, "<NIL>");
1623 fprintf (file
, "\n");
1628 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1629 stack up to a maximum of N levels. If N is -1, the whole stack is
1630 dumped. New levels are created when the dominator tree traversal
1631 used for renaming enters a new sub-tree. */
1634 debug_defs_stack (int n
)
1636 dump_defs_stack (stderr
, n
);
1640 /* Dump the current reaching definition of every symbol to FILE. */
1643 dump_currdefs (FILE *file
)
1648 if (symbols_to_rename
.is_empty ())
1651 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1652 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, var
)
1654 common_info
*info
= get_common_info (var
);
1655 fprintf (file
, "CURRDEF (");
1656 print_generic_expr (file
, var
);
1657 fprintf (file
, ") = ");
1658 if (info
->current_def
)
1659 print_generic_expr (file
, info
->current_def
);
1661 fprintf (file
, "<NIL>");
1662 fprintf (file
, "\n");
1667 /* Dump the current reaching definition of every symbol to stderr. */
1670 debug_currdefs (void)
1672 dump_currdefs (stderr
);
1676 /* Dump SSA information to FILE. */
1679 dump_tree_ssa (FILE *file
)
1681 const char *funcname
1682 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1684 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1686 dump_var_infos (file
);
1687 dump_defs_stack (file
, -1);
1688 dump_currdefs (file
);
1689 dump_tree_ssa_stats (file
);
1693 /* Dump SSA information to stderr. */
1696 debug_tree_ssa (void)
1698 dump_tree_ssa (stderr
);
1702 /* Dump statistics for the hash table HTAB. */
1705 htab_statistics (FILE *file
, const hash_table
<var_info_hasher
> &htab
)
1707 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1708 (long) htab
.size (),
1709 (long) htab
.elements (),
1710 htab
.collisions ());
1714 /* Dump SSA statistics on FILE. */
1717 dump_tree_ssa_stats (FILE *file
)
1721 fprintf (file
, "\nHash table statistics:\n");
1722 fprintf (file
, " var_infos: ");
1723 htab_statistics (file
, *var_infos
);
1724 fprintf (file
, "\n");
1729 /* Dump SSA statistics on stderr. */
1732 debug_tree_ssa_stats (void)
1734 dump_tree_ssa_stats (stderr
);
1738 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1741 debug_var_infos_r (var_info
**slot
, FILE *file
)
1743 var_info
*info
= *slot
;
1745 fprintf (file
, "VAR: ");
1746 print_generic_expr (file
, info
->var
, dump_flags
);
1747 bitmap_print (file
, info
->info
.def_blocks
.def_blocks
,
1748 ", DEF_BLOCKS: { ", "}");
1749 bitmap_print (file
, info
->info
.def_blocks
.livein_blocks
,
1750 ", LIVEIN_BLOCKS: { ", "}");
1751 bitmap_print (file
, info
->info
.def_blocks
.phi_blocks
,
1752 ", PHI_BLOCKS: { ", "}\n");
1758 /* Dump the VAR_INFOS hash table on FILE. */
1761 dump_var_infos (FILE *file
)
1763 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1765 var_infos
->traverse
<FILE *, debug_var_infos_r
> (file
);
1769 /* Dump the VAR_INFOS hash table on stderr. */
1772 debug_var_infos (void)
1774 dump_var_infos (stderr
);
1778 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1781 register_new_update_single (tree new_name
, tree old_name
)
1783 common_info
*info
= get_common_info (old_name
);
1784 tree currdef
= info
->current_def
;
1786 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1787 This stack is later used by the dominator tree callbacks to
1788 restore the reaching definitions for all the variables
1789 defined in the block after a recursive visit to all its
1790 immediately dominated blocks. */
1791 block_defs_stack
.reserve (2);
1792 block_defs_stack
.quick_push (currdef
);
1793 block_defs_stack
.quick_push (old_name
);
1795 /* Set the current reaching definition for OLD_NAME to be
1797 info
->current_def
= new_name
;
1801 /* Register NEW_NAME to be the new reaching definition for all the
1802 names in OLD_NAMES. Used by the incremental SSA update routines to
1803 replace old SSA names with new ones. */
1806 register_new_update_set (tree new_name
, bitmap old_names
)
1811 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1812 register_new_update_single (new_name
, ssa_name (i
));
1817 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1818 it is a symbol marked for renaming, replace it with USE_P's current
1819 reaching definition. */
1822 maybe_replace_use (use_operand_p use_p
)
1824 tree rdef
= NULL_TREE
;
1825 tree use
= USE_FROM_PTR (use_p
);
1826 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1828 if (marked_for_renaming (sym
))
1829 rdef
= get_reaching_def (sym
);
1830 else if (is_old_name (use
))
1831 rdef
= get_reaching_def (use
);
1833 if (rdef
&& rdef
!= use
)
1834 SET_USE (use_p
, rdef
);
1838 /* Same as maybe_replace_use, but without introducing default stmts,
1839 returning false to indicate a need to do so. */
1842 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1844 tree rdef
= NULL_TREE
;
1845 tree use
= USE_FROM_PTR (use_p
);
1846 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1848 if (marked_for_renaming (sym
))
1849 rdef
= get_var_info (sym
)->info
.current_def
;
1850 else if (is_old_name (use
))
1852 rdef
= get_ssa_name_ann (use
)->info
.current_def
;
1853 /* We can't assume that, if there's no current definition, the
1854 default one should be used. It could be the case that we've
1855 rearranged blocks so that the earlier definition no longer
1856 dominates the use. */
1857 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1863 if (rdef
&& rdef
!= use
)
1864 SET_USE (use_p
, rdef
);
1866 return rdef
!= NULL_TREE
;
1870 /* If DEF has x_5 = ASAN_POISON () as its current def, add
1871 ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1872 a poisoned (out of scope) variable. */
1875 maybe_add_asan_poison_write (tree def
, gimple_stmt_iterator
*gsi
)
1877 tree cdef
= get_current_def (def
);
1879 && TREE_CODE (cdef
) == SSA_NAME
1880 && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef
), IFN_ASAN_POISON
))
1883 = gimple_build_call_internal (IFN_ASAN_POISON_USE
, 1, cdef
);
1884 gimple_set_location (call
, gimple_location (gsi_stmt (*gsi
)));
1885 gsi_insert_before (gsi
, call
, GSI_SAME_STMT
);
1890 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1891 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1892 register it as the current definition for the names replaced by
1893 DEF_P. Returns whether the statement should be removed. */
1896 maybe_register_def (def_operand_p def_p
, gimple
*stmt
,
1897 gimple_stmt_iterator gsi
)
1899 tree def
= DEF_FROM_PTR (def_p
);
1900 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1901 bool to_delete
= false;
1903 /* If DEF is a naked symbol that needs renaming, create a new
1905 if (marked_for_renaming (sym
))
1909 if (gimple_clobber_p (stmt
) && is_gimple_reg (sym
))
1911 gcc_checking_assert (VAR_P (sym
));
1912 /* Replace clobber stmts with a default def. This new use of a
1913 default definition may make it look like SSA_NAMEs have
1914 conflicting lifetimes, so we need special code to let them
1915 coalesce properly. */
1917 def
= get_or_create_ssa_default_def (cfun
, sym
);
1921 if (asan_sanitize_use_after_scope ())
1922 maybe_add_asan_poison_write (def
, &gsi
);
1923 def
= make_ssa_name (def
, stmt
);
1925 SET_DEF (def_p
, def
);
1927 tree tracked_var
= target_for_debug_bind (sym
);
1930 gimple
*note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1931 /* If stmt ends the bb, insert the debug stmt on the single
1932 non-EH edge from the stmt. */
1933 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1935 basic_block bb
= gsi_bb (gsi
);
1938 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1939 if (!(e
->flags
& EDGE_EH
))
1941 gcc_checking_assert (!ef
);
1944 /* If there are other predecessors to ef->dest, then
1945 there must be PHI nodes for the modified
1946 variable, and therefore there will be debug bind
1947 stmts after the PHI nodes. The debug bind notes
1948 we'd insert would force the creation of a new
1949 block (diverging codegen) and be redundant with
1950 the post-PHI bind stmts, so don't add them.
1952 As for the exit edge, there wouldn't be redundant
1953 bind stmts, but there wouldn't be a PC to bind
1954 them to either, so avoid diverging the CFG. */
1955 if (ef
&& single_pred_p (ef
->dest
)
1956 && ef
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1958 /* If there were PHI nodes in the node, we'd
1959 have to make sure the value we're binding
1960 doesn't need rewriting. But there shouldn't
1961 be PHI nodes in a single-predecessor block,
1962 so we just add the note. */
1963 gsi_insert_on_edge_immediate (ef
, note
);
1967 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1971 register_new_update_single (def
, sym
);
1975 /* If DEF is a new name, register it as a new definition
1976 for all the names replaced by DEF. */
1977 if (is_new_name (def
))
1978 register_new_update_set (def
, names_replaced_by (def
));
1980 /* If DEF is an old name, register DEF as a new
1981 definition for itself. */
1982 if (is_old_name (def
))
1983 register_new_update_single (def
, def
);
1990 /* Update every variable used in the statement pointed-to by SI. The
1991 statement is assumed to be in SSA form already. Names in
1992 OLD_SSA_NAMES used by SI will be updated to their current reaching
1993 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1994 will be registered as a new definition for their corresponding name
1995 in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1998 rewrite_update_stmt (gimple
*stmt
, gimple_stmt_iterator gsi
)
2000 use_operand_p use_p
;
2001 def_operand_p def_p
;
2004 /* Only update marked statements. */
2005 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
2008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2010 fprintf (dump_file
, "Updating SSA information for statement ");
2011 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2014 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2015 symbol is marked for renaming. */
2016 if (rewrite_uses_p (stmt
))
2018 if (is_gimple_debug (stmt
))
2020 bool failed
= false;
2022 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
2023 if (!maybe_replace_use_in_debug_stmt (use_p
))
2031 /* DOM sometimes threads jumps in such a way that a
2032 debug stmt ends up referencing a SSA variable that no
2033 longer dominates the debug stmt, but such that all
2034 incoming definitions refer to the same definition in
2035 an earlier dominator. We could try to recover that
2036 definition somehow, but this will have to do for now.
2038 Introducing a default definition, which is what
2039 maybe_replace_use() would do in such cases, may
2040 modify code generation, for the otherwise-unused
2041 default definition would never go away, modifying SSA
2042 version numbers all over. */
2043 gimple_debug_bind_reset_value (stmt
);
2049 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
2050 maybe_replace_use (use_p
);
2054 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2055 Also register definitions for names whose underlying symbol is
2056 marked for renaming. */
2057 bool to_delete
= false;
2058 if (register_defs_p (stmt
))
2059 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
2060 to_delete
|= maybe_register_def (def_p
, stmt
, gsi
);
2066 /* Visit all the successor blocks of BB looking for PHI nodes. For
2067 every PHI node found, check if any of its arguments is in
2068 OLD_SSA_NAMES. If so, and if the argument has a current reaching
2069 definition, replace it. */
2072 rewrite_update_phi_arguments (basic_block bb
)
2078 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2083 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
2086 phis
= phis_to_rewrite
[e
->dest
->index
];
2087 FOR_EACH_VEC_ELT (phis
, i
, phi
)
2089 tree arg
, lhs_sym
, reaching_def
= NULL
;
2090 use_operand_p arg_p
;
2092 gcc_checking_assert (rewrite_uses_p (phi
));
2094 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
2095 arg
= USE_FROM_PTR (arg_p
);
2097 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
2100 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2102 if (arg
== NULL_TREE
)
2104 /* When updating a PHI node for a recently introduced
2105 symbol we may find NULL arguments. That's why we
2106 take the symbol from the LHS of the PHI node. */
2107 reaching_def
= get_reaching_def (lhs_sym
);
2112 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2114 if (marked_for_renaming (sym
))
2115 reaching_def
= get_reaching_def (sym
);
2116 else if (is_old_name (arg
))
2117 reaching_def
= get_reaching_def (arg
);
2120 /* Update the argument if there is a reaching def. */
2124 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2126 SET_USE (arg_p
, reaching_def
);
2128 /* Virtual operands do not need a location. */
2129 if (virtual_operand_p (reaching_def
))
2130 locus
= UNKNOWN_LOCATION
;
2133 gimple
*stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2134 gphi
*other_phi
= dyn_cast
<gphi
*> (stmt
);
2136 /* Single element PHI nodes behave like copies, so get the
2137 location from the phi argument. */
2139 && gimple_phi_num_args (other_phi
) == 1)
2140 locus
= gimple_phi_arg_location (other_phi
, 0);
2142 locus
= gimple_location (stmt
);
2145 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2149 if (e
->flags
& EDGE_ABNORMAL
)
2150 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2155 class rewrite_update_dom_walker
: public dom_walker
2158 rewrite_update_dom_walker (cdi_direction direction
)
2159 : dom_walker (direction
, ALL_BLOCKS
, NULL
) {}
2161 virtual edge
before_dom_children (basic_block
);
2162 virtual void after_dom_children (basic_block
);
2165 /* Initialization of block data structures for the incremental SSA
2166 update pass. Create a block local stack of reaching definitions
2167 for new SSA names produced in this block (BLOCK_DEFS). Register
2168 new definitions for every PHI node in the block. */
2171 rewrite_update_dom_walker::before_dom_children (basic_block bb
)
2173 bool is_abnormal_phi
;
2175 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2176 fprintf (dump_file
, "Registering new PHI nodes in block #%d\n",
2179 /* Mark the unwind point for this block. */
2180 block_defs_stack
.safe_push (NULL_TREE
);
2182 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2185 /* Mark the LHS if any of the arguments flows through an abnormal
2187 is_abnormal_phi
= bb_has_abnormal_pred (bb
);
2189 /* If any of the PHI nodes is a replacement for a name in
2190 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2191 register it as a new definition for its corresponding name. Also
2192 register definitions for names whose underlying symbols are
2193 marked for renaming. */
2194 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2198 gphi
*phi
= gsi
.phi ();
2200 if (!register_defs_p (phi
))
2203 lhs
= gimple_phi_result (phi
);
2204 lhs_sym
= SSA_NAME_VAR (lhs
);
2206 if (marked_for_renaming (lhs_sym
))
2207 register_new_update_single (lhs
, lhs_sym
);
2211 /* If LHS is a new name, register a new definition for all
2212 the names replaced by LHS. */
2213 if (is_new_name (lhs
))
2214 register_new_update_set (lhs
, names_replaced_by (lhs
));
2216 /* If LHS is an OLD name, register it as a new definition
2218 if (is_old_name (lhs
))
2219 register_new_update_single (lhs
, lhs
);
2222 if (is_abnormal_phi
)
2223 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2226 /* Step 2. Rewrite every variable used in each statement in the block. */
2227 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
2229 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2230 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2231 if (rewrite_update_stmt (gsi_stmt (gsi
), gsi
))
2232 gsi_remove (&gsi
, true);
2237 /* Step 3. Update PHI nodes. */
2238 rewrite_update_phi_arguments (bb
);
2243 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2244 the current reaching definition of every name re-written in BB to
2245 the original reaching definition before visiting BB. This
2246 unwinding must be done in the opposite order to what is done in
2247 register_new_update_set. */
2250 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
2252 while (block_defs_stack
.length () > 0)
2254 tree var
= block_defs_stack
.pop ();
2257 /* NULL indicates the unwind stop point for this block (see
2258 rewrite_update_enter_block). */
2262 saved_def
= block_defs_stack
.pop ();
2263 get_common_info (var
)->current_def
= saved_def
;
2268 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2271 ENTRY indicates the block where to start. Every block dominated by
2272 ENTRY will be rewritten.
2274 WHAT indicates what actions will be taken by the renamer (see enum
2277 BLOCKS are the set of interesting blocks for the dominator walker
2278 to process. If this set is NULL, then all the nodes dominated
2279 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2280 are not present in BLOCKS are ignored. */
2283 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2285 /* Rewrite all the basic blocks in the program. */
2286 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2288 block_defs_stack
.create (10);
2290 /* Recursively walk the dominator tree rewriting each statement in
2291 each basic block. */
2292 if (what
== REWRITE_ALL
)
2293 rewrite_dom_walker (CDI_DOMINATORS
).walk (entry
);
2294 else if (what
== REWRITE_UPDATE
)
2295 rewrite_update_dom_walker (CDI_DOMINATORS
).walk (entry
);
2299 /* Debugging dumps. */
2300 if (dump_file
&& (dump_flags
& TDF_STATS
))
2302 dump_dfa_stats (dump_file
);
2304 dump_tree_ssa_stats (dump_file
);
2307 block_defs_stack
.release ();
2309 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2312 class mark_def_dom_walker
: public dom_walker
2315 mark_def_dom_walker (cdi_direction direction
);
2316 ~mark_def_dom_walker ();
2318 virtual edge
before_dom_children (basic_block
);
2321 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2322 large enough to accommodate all the variables referenced in the
2323 function, not just the ones we are renaming. */
2327 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction
)
2328 : dom_walker (direction
, ALL_BLOCKS
, NULL
), m_kills (BITMAP_ALLOC (NULL
))
2332 mark_def_dom_walker::~mark_def_dom_walker ()
2334 BITMAP_FREE (m_kills
);
2337 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2338 at the start of each block, and call mark_def_sites for each statement. */
2341 mark_def_dom_walker::before_dom_children (basic_block bb
)
2343 gimple_stmt_iterator gsi
;
2345 bitmap_clear (m_kills
);
2346 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2347 mark_def_sites (bb
, gsi_stmt (gsi
), m_kills
);
2351 /* Initialize internal data needed during renaming. */
2354 init_ssa_renamer (void)
2356 cfun
->gimple_df
->in_ssa_p
= false;
2358 /* Allocate memory for the DEF_BLOCKS hash table. */
2359 gcc_assert (!var_infos
);
2360 var_infos
= new hash_table
<var_info_hasher
>
2361 (vec_safe_length (cfun
->local_decls
));
2363 bitmap_obstack_initialize (&update_ssa_obstack
);
2367 /* Deallocate internal data structures used by the renamer. */
2370 fini_ssa_renamer (void)
2375 bitmap_obstack_release (&update_ssa_obstack
);
2377 cfun
->gimple_df
->ssa_renaming_needed
= 0;
2378 cfun
->gimple_df
->rename_vops
= 0;
2379 cfun
->gimple_df
->in_ssa_p
= true;
2382 /* Main entry point into the SSA builder. The renaming process
2383 proceeds in four main phases:
2385 1- Compute dominance frontier and immediate dominators, needed to
2386 insert PHI nodes and rename the function in dominator tree
2389 2- Find and mark all the blocks that define variables.
2391 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2393 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2395 Steps 3 and 4 are done using the dominator tree walker
2396 (walk_dominator_tree). */
2400 const pass_data pass_data_build_ssa
=
2402 GIMPLE_PASS
, /* type */
2404 OPTGROUP_NONE
, /* optinfo_flags */
2405 TV_TREE_SSA_OTHER
, /* tv_id */
2406 PROP_cfg
, /* properties_required */
2407 PROP_ssa
, /* properties_provided */
2408 0, /* properties_destroyed */
2409 0, /* todo_flags_start */
2410 TODO_remove_unused_locals
, /* todo_flags_finish */
2413 class pass_build_ssa
: public gimple_opt_pass
2416 pass_build_ssa (gcc::context
*ctxt
)
2417 : gimple_opt_pass (pass_data_build_ssa
, ctxt
)
2420 /* opt_pass methods: */
2421 virtual bool gate (function
*fun
)
2423 /* Do nothing for funcions that was produced already in SSA form. */
2424 return !(fun
->curr_properties
& PROP_ssa
);
2427 virtual unsigned int execute (function
*);
2429 }; // class pass_build_ssa
2432 pass_build_ssa::execute (function
*fun
)
2437 /* Increase the set of variables we can rewrite into SSA form
2438 by clearing TREE_ADDRESSABLE and transform the IL to support this. */
2440 execute_update_addresses_taken ();
2442 /* Initialize operand data structures. */
2443 init_ssa_operands (fun
);
2445 /* Initialize internal data needed by the renamer. */
2446 init_ssa_renamer ();
2448 /* Initialize the set of interesting blocks. The callback
2449 mark_def_sites will add to this set those blocks that the renamer
2451 interesting_blocks
= sbitmap_alloc (last_basic_block_for_fn (fun
));
2452 bitmap_clear (interesting_blocks
);
2454 /* Initialize dominance frontier. */
2455 dfs
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (fun
));
2456 FOR_EACH_BB_FN (bb
, fun
)
2457 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
2459 /* 1- Compute dominance frontiers. */
2460 calculate_dominance_info (CDI_DOMINATORS
);
2461 compute_dominance_frontiers (dfs
);
2463 /* 2- Find and mark definition sites. */
2464 mark_def_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2466 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2467 insert_phi_nodes (dfs
);
2469 /* 4- Rename all the blocks. */
2470 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun
), REWRITE_ALL
);
2472 /* Free allocated memory. */
2473 FOR_EACH_BB_FN (bb
, fun
)
2474 bitmap_clear (&dfs
[bb
->index
]);
2477 sbitmap_free (interesting_blocks
);
2479 fini_ssa_renamer ();
2481 /* Try to get rid of all gimplifier generated temporaries by making
2482 its SSA names anonymous. This way we can garbage collect them
2483 all after removing unused locals which we do in our TODO. */
2487 FOR_EACH_SSA_NAME (i
, name
, cfun
)
2489 if (SSA_NAME_IS_DEFAULT_DEF (name
))
2491 tree decl
= SSA_NAME_VAR (name
);
2494 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl
)
2495 && DECL_IGNORED_P (decl
))
2496 SET_SSA_NAME_VAR_OR_IDENTIFIER (name
, DECL_NAME (decl
));
2499 /* Initialize SSA_NAME_POINTS_TO_READONLY_MEMORY. */
2501 = lookup_attribute ("fn spec",
2502 TYPE_ATTRIBUTES (TREE_TYPE (fun
->decl
)));
2505 attr_fnspec
fnspec (TREE_VALUE (TREE_VALUE (fnspec_tree
)));
2507 for (tree arg
= DECL_ARGUMENTS (cfun
->decl
);
2508 arg
; arg
= DECL_CHAIN (arg
), ++i
)
2510 if (!fnspec
.arg_specified_p (i
))
2512 if (fnspec
.arg_readonly_p (i
))
2514 tree name
= ssa_default_def (fun
, arg
);
2516 SSA_NAME_POINTS_TO_READONLY_MEMORY (name
) = 1;
2527 make_pass_build_ssa (gcc::context
*ctxt
)
2529 return new pass_build_ssa (ctxt
);
2533 /* Mark the definition of VAR at STMT and BB as interesting for the
2534 renamer. BLOCKS is the set of blocks that need updating. */
2537 mark_def_interesting (tree var
, gimple
*stmt
, basic_block bb
,
2540 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2541 set_register_defs (stmt
, true);
2545 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2547 set_def_block (var
, bb
, is_phi_p
);
2549 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2550 site for both itself and all the old names replaced by it. */
2551 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2555 bitmap set
= names_replaced_by (var
);
2557 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2558 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2564 /* Mark the use of VAR at STMT and BB as interesting for the
2565 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2569 mark_use_interesting (tree var
, gimple
*stmt
, basic_block bb
,
2572 basic_block def_bb
= gimple_bb (stmt
);
2574 mark_block_for_update (def_bb
);
2575 mark_block_for_update (bb
);
2577 if (gimple_code (stmt
) == GIMPLE_PHI
)
2578 mark_phi_for_rewrite (def_bb
, as_a
<gphi
*> (stmt
));
2581 set_rewrite_uses (stmt
, true);
2583 if (is_gimple_debug (stmt
))
2587 /* If VAR has not been defined in BB, then it is live-on-entry
2588 to BB. Note that we cannot just use the block holding VAR's
2589 definition because if VAR is one of the names in OLD_SSA_NAMES,
2590 it will have several definitions (itself and all the names that
2594 def_blocks
*db_p
= get_def_blocks_for (get_common_info (var
));
2595 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2596 set_livein_block (var
, bb
);
2600 /* Processing statements in BB that reference symbols in SSA operands.
2601 This is very similar to mark_def_sites, but the scan handles
2602 statements whose operands may already be SSA names.
2604 If INSERT_PHI_P is true, mark those uses as live in the
2605 corresponding block. This is later used by the PHI placement
2606 algorithm to make PHI pruning decisions.
2608 FIXME. Most of this would be unnecessary if we could associate a
2609 symbol to all the SSA names that reference it. But that
2610 sounds like it would be expensive to maintain. Still, it
2611 would be interesting to see if it makes better sense to do
2615 prepare_block_for_update_1 (basic_block bb
, bool insert_phi_p
)
2620 mark_block_for_update (bb
);
2622 /* Process PHI nodes marking interesting those that define or use
2623 the symbols that we are interested in. */
2624 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
2627 gphi
*phi
= si
.phi ();
2628 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2630 if (TREE_CODE (lhs
) == SSA_NAME
2631 && (! virtual_operand_p (lhs
)
2632 || ! cfun
->gimple_df
->rename_vops
))
2635 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2636 mark_for_renaming (lhs_sym
);
2637 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2639 /* Mark the uses in phi nodes as interesting. It would be more correct
2640 to process the arguments of the phi nodes of the successor edges of
2641 BB at the end of prepare_block_for_update, however, that turns out
2642 to be significantly more expensive. Doing it here is conservatively
2643 correct -- it may only cause us to believe a value to be live in a
2644 block that also contains its definition, and thus insert a few more
2645 phi nodes for it. */
2646 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2647 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2650 /* Process the statements. */
2651 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
2656 use_operand_p use_p
;
2657 def_operand_p def_p
;
2659 stmt
= gsi_stmt (si
);
2661 if (cfun
->gimple_df
->rename_vops
2662 && gimple_vuse (stmt
))
2664 tree use
= gimple_vuse (stmt
);
2665 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2666 mark_for_renaming (sym
);
2667 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2670 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_USE
)
2672 tree use
= USE_FROM_PTR (use_p
);
2675 mark_for_renaming (use
);
2676 mark_use_interesting (use
, stmt
, bb
, insert_phi_p
);
2679 if (cfun
->gimple_df
->rename_vops
2680 && gimple_vdef (stmt
))
2682 tree def
= gimple_vdef (stmt
);
2683 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2684 mark_for_renaming (sym
);
2685 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2688 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_DEF
)
2690 tree def
= DEF_FROM_PTR (def_p
);
2693 mark_for_renaming (def
);
2694 mark_def_interesting (def
, stmt
, bb
, insert_phi_p
);
2700 /* Do a dominator walk starting at BB processing statements that
2701 reference symbols in SSA operands. This is very similar to
2702 mark_def_sites, but the scan handles statements whose operands may
2703 already be SSA names.
2705 If INSERT_PHI_P is true, mark those uses as live in the
2706 corresponding block. This is later used by the PHI placement
2707 algorithm to make PHI pruning decisions.
2709 FIXME. Most of this would be unnecessary if we could associate a
2710 symbol to all the SSA names that reference it. But that
2711 sounds like it would be expensive to maintain. Still, it
2712 would be interesting to see if it makes better sense to do
2715 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2718 basic_block
*worklist
;
2720 /* Allocate the worklist. */
2721 worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
2722 /* Add the BB to the worklist. */
2723 worklist
[sp
++] = bb
;
2730 /* Pick a block from the worklist. */
2731 bb
= worklist
[--sp
];
2733 prepare_block_for_update_1 (bb
, insert_phi_p
);
2735 /* Now add all the blocks dominated by BB to the worklist. */
2736 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2738 son
= next_dom_son (CDI_DOMINATORS
, son
))
2739 worklist
[sp
++] = son
;
2744 /* Helper for prepare_names_to_update. Mark all the use sites for
2745 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2746 prepare_names_to_update. */
2749 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2751 use_operand_p use_p
;
2752 imm_use_iterator iter
;
2754 /* If we rename virtual operands do not update them. */
2755 if (virtual_operand_p (name
)
2756 && cfun
->gimple_df
->rename_vops
)
2759 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2761 gimple
*stmt
= USE_STMT (use_p
);
2762 basic_block bb
= gimple_bb (stmt
);
2764 if (gimple_code (stmt
) == GIMPLE_PHI
)
2766 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2767 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (stmt
), ix
);
2768 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2772 /* For regular statements, mark this as an interesting use
2774 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2780 /* Helper for prepare_names_to_update. Mark the definition site for
2781 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2782 prepare_names_to_update. */
2785 prepare_def_site_for (tree name
, bool insert_phi_p
)
2790 gcc_checking_assert (names_to_release
== NULL
2791 || !bitmap_bit_p (names_to_release
,
2792 SSA_NAME_VERSION (name
)));
2794 /* If we rename virtual operands do not update them. */
2795 if (virtual_operand_p (name
)
2796 && cfun
->gimple_df
->rename_vops
)
2799 stmt
= SSA_NAME_DEF_STMT (name
);
2800 bb
= gimple_bb (stmt
);
2803 gcc_checking_assert (bb
->index
< last_basic_block_for_fn (cfun
));
2804 mark_block_for_update (bb
);
2805 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2810 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2811 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2812 PHI nodes for newly created names. */
2815 prepare_names_to_update (bool insert_phi_p
)
2819 sbitmap_iterator sbi
;
2821 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2822 remove it from NEW_SSA_NAMES so that we don't try to visit its
2823 defining basic block (which most likely doesn't exist). Notice
2824 that we cannot do the same with names in OLD_SSA_NAMES because we
2825 want to replace existing instances. */
2826 if (names_to_release
)
2827 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2828 bitmap_clear_bit (new_ssa_names
, i
);
2830 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2831 names may be considered to be live-in on blocks that contain
2832 definitions for their replacements. */
2833 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2834 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2836 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2837 OLD_SSA_NAMES, but we have to ignore its definition site. */
2838 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
2840 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2841 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2842 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2847 /* Dump all the names replaced by NAME to FILE. */
2850 dump_names_replaced_by (FILE *file
, tree name
)
2856 print_generic_expr (file
, name
);
2857 fprintf (file
, " -> { ");
2859 old_set
= names_replaced_by (name
);
2860 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2862 print_generic_expr (file
, ssa_name (i
));
2863 fprintf (file
, " ");
2866 fprintf (file
, "}\n");
2870 /* Dump all the names replaced by NAME to stderr. */
2873 debug_names_replaced_by (tree name
)
2875 dump_names_replaced_by (stderr
, name
);
2879 /* Dump SSA update information to FILE. */
2882 dump_update_ssa (FILE *file
)
2887 if (!need_ssa_update_p (cfun
))
2890 if (new_ssa_names
&& bitmap_first_set_bit (new_ssa_names
) >= 0)
2892 sbitmap_iterator sbi
;
2894 fprintf (file
, "\nSSA replacement table\n");
2895 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2896 "O_1, ..., O_j\n\n");
2898 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2899 dump_names_replaced_by (file
, ssa_name (i
));
2902 if (symbols_to_rename_set
&& !bitmap_empty_p (symbols_to_rename_set
))
2904 fprintf (file
, "\nSymbols to be put in SSA form\n");
2905 dump_decl_set (file
, symbols_to_rename_set
);
2906 fprintf (file
, "\n");
2909 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2911 fprintf (file
, "\nSSA names to release after updating the SSA web\n\n");
2912 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2914 print_generic_expr (file
, ssa_name (i
));
2915 fprintf (file
, " ");
2917 fprintf (file
, "\n");
2922 /* Dump SSA update information to stderr. */
2925 debug_update_ssa (void)
2927 dump_update_ssa (stderr
);
2931 /* Initialize data structures used for incremental SSA updates. */
2934 init_update_ssa (struct function
*fn
)
2936 /* Reserve more space than the current number of names. The calls to
2937 add_new_name_mapping are typically done after creating new SSA
2938 names, so we'll need to reallocate these arrays. */
2939 old_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2940 bitmap_clear (old_ssa_names
);
2942 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2943 bitmap_clear (new_ssa_names
);
2945 bitmap_obstack_initialize (&update_ssa_obstack
);
2947 names_to_release
= NULL
;
2948 update_ssa_initialized_fn
= fn
;
2952 /* Deallocate data structures used for incremental SSA updates. */
2955 delete_update_ssa (void)
2960 sbitmap_free (old_ssa_names
);
2961 old_ssa_names
= NULL
;
2963 sbitmap_free (new_ssa_names
);
2964 new_ssa_names
= NULL
;
2966 BITMAP_FREE (symbols_to_rename_set
);
2967 symbols_to_rename_set
= NULL
;
2968 symbols_to_rename
.release ();
2970 if (names_to_release
)
2972 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2973 release_ssa_name (ssa_name (i
));
2974 BITMAP_FREE (names_to_release
);
2977 clear_ssa_name_info ();
2979 fini_ssa_renamer ();
2981 if (blocks_with_phis_to_rewrite
)
2982 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2983 phis_to_rewrite
[i
].release ();
2985 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2986 BITMAP_FREE (blocks_to_update
);
2988 update_ssa_initialized_fn
= NULL
;
2992 /* Create a new name for OLD_NAME in statement STMT and replace the
2993 operand pointed to by DEF_P with the newly created name. If DEF_P
2994 is NULL then STMT should be a GIMPLE assignment.
2995 Return the new name and register the replacement mapping <NEW, OLD> in
2996 update_ssa's tables. */
2999 create_new_def_for (tree old_name
, gimple
*stmt
, def_operand_p def
)
3003 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3005 if (!update_ssa_initialized_fn
)
3006 init_update_ssa (cfun
);
3008 gcc_assert (update_ssa_initialized_fn
== cfun
);
3010 new_name
= duplicate_ssa_name (old_name
, stmt
);
3012 SET_DEF (def
, new_name
);
3014 gimple_assign_set_lhs (stmt
, new_name
);
3016 if (gimple_code (stmt
) == GIMPLE_PHI
)
3018 basic_block bb
= gimple_bb (stmt
);
3020 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
3021 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = bb_has_abnormal_pred (bb
);
3024 add_new_name_mapping (new_name
, old_name
);
3026 /* For the benefit of passes that will be updating the SSA form on
3027 their own, set the current reaching definition of OLD_NAME to be
3029 get_ssa_name_ann (old_name
)->info
.current_def
= new_name
;
3031 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
3037 /* Mark virtual operands of FN for renaming by update_ssa. */
3040 mark_virtual_operands_for_renaming (struct function
*fn
)
3042 fn
->gimple_df
->ssa_renaming_needed
= 1;
3043 fn
->gimple_df
->rename_vops
= 1;
3046 /* Replace all uses of NAME by underlying variable and mark it
3047 for renaming. This assumes the defining statement of NAME is
3048 going to be removed. */
3051 mark_virtual_operand_for_renaming (tree name
)
3053 tree name_var
= SSA_NAME_VAR (name
);
3055 imm_use_iterator iter
;
3056 use_operand_p use_p
;
3059 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var
));
3060 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
3062 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
3063 SET_USE (use_p
, name_var
);
3067 mark_virtual_operands_for_renaming (cfun
);
3070 /* Replace all uses of the virtual PHI result by its underlying variable
3071 and mark it for renaming. This assumes the PHI node is going to be
3075 mark_virtual_phi_result_for_renaming (gphi
*phi
)
3077 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3079 fprintf (dump_file
, "Marking result for renaming : ");
3080 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
3081 fprintf (dump_file
, "\n");
3084 mark_virtual_operand_for_renaming (gimple_phi_result (phi
));
3087 /* Return true if there is any work to be done by update_ssa
3091 need_ssa_update_p (struct function
*fn
)
3093 gcc_assert (fn
!= NULL
);
3094 return (update_ssa_initialized_fn
== fn
3095 || (fn
->gimple_df
&& fn
->gimple_df
->ssa_renaming_needed
));
3098 /* Return true if name N has been registered in the replacement table. */
3101 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
3103 if (!update_ssa_initialized_fn
)
3106 gcc_assert (update_ssa_initialized_fn
== cfun
);
3108 return is_new_name (n
) || is_old_name (n
);
3112 /* Mark NAME to be released after update_ssa has finished. */
3115 release_ssa_name_after_update_ssa (tree name
)
3117 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
3119 if (names_to_release
== NULL
)
3120 names_to_release
= BITMAP_ALLOC (NULL
);
3122 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
3126 /* Insert new PHI nodes to replace VAR. DFS contains dominance
3127 frontier information. BLOCKS is the set of blocks to be updated.
3129 This is slightly different than the regular PHI insertion
3130 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3131 real names (i.e., GIMPLE registers) are inserted:
3133 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3134 nodes inside the region affected by the block that defines VAR
3135 and the blocks that define all its replacements. All these
3136 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3138 First, we compute the entry point to the region (ENTRY). This is
3139 given by the nearest common dominator to all the definition
3140 blocks. When computing the iterated dominance frontier (IDF), any
3141 block not strictly dominated by ENTRY is ignored.
3143 We then call the standard PHI insertion algorithm with the pruned
3146 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3147 names is not pruned. PHI nodes are inserted at every IDF block. */
3150 insert_updated_phi_nodes_for (tree var
, bitmap_head
*dfs
, bitmap blocks
,
3151 unsigned update_flags
)
3155 bitmap idf
, pruned_idf
;
3159 if (TREE_CODE (var
) == SSA_NAME
)
3160 gcc_checking_assert (is_old_name (var
));
3162 gcc_checking_assert (marked_for_renaming (var
));
3164 /* Get all the definition sites for VAR. */
3165 db
= find_def_blocks_for (var
);
3167 /* No need to do anything if there were no definitions to VAR. */
3168 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
3171 /* Compute the initial iterated dominance frontier. */
3172 idf
= compute_idf (db
->def_blocks
, dfs
);
3173 pruned_idf
= BITMAP_ALLOC (NULL
);
3175 if (TREE_CODE (var
) == SSA_NAME
)
3177 if (update_flags
== TODO_update_ssa
)
3179 /* If doing regular SSA updates for GIMPLE registers, we are
3180 only interested in IDF blocks dominated by the nearest
3181 common dominator of all the definition blocks. */
3182 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3184 if (entry
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3185 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
3186 if (BASIC_BLOCK_FOR_FN (cfun
, i
) != entry
3187 && dominated_by_p (CDI_DOMINATORS
,
3188 BASIC_BLOCK_FOR_FN (cfun
, i
), entry
))
3189 bitmap_set_bit (pruned_idf
, i
);
3193 /* Otherwise, do not prune the IDF for VAR. */
3194 gcc_checking_assert (update_flags
== TODO_update_ssa_full_phi
);
3195 bitmap_copy (pruned_idf
, idf
);
3200 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3201 for the first time, so we need to compute the full IDF for
3203 bitmap_copy (pruned_idf
, idf
);
3206 if (!bitmap_empty_p (pruned_idf
))
3208 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3209 are included in the region to be updated. The feeding blocks
3210 are important to guarantee that the PHI arguments are renamed
3213 /* FIXME, this is not needed if we are updating symbols. We are
3214 already starting at the ENTRY block anyway. */
3215 bitmap_ior_into (blocks
, pruned_idf
);
3216 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3220 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3222 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3223 if (e
->src
->index
>= 0)
3224 bitmap_set_bit (blocks
, e
->src
->index
);
3227 insert_phi_nodes_for (var
, pruned_idf
, true);
3230 BITMAP_FREE (pruned_idf
);
3234 /* Sort symbols_to_rename after their DECL_UID. */
3237 insert_updated_phi_nodes_compare_uids (const void *a
, const void *b
)
3239 const_tree syma
= *(const const_tree
*)a
;
3240 const_tree symb
= *(const const_tree
*)b
;
3241 if (DECL_UID (syma
) == DECL_UID (symb
))
3243 return DECL_UID (syma
) < DECL_UID (symb
) ? -1 : 1;
3246 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3247 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3249 1- The names in OLD_SSA_NAMES dominated by the definitions of
3250 NEW_SSA_NAMES are all re-written to be reached by the
3251 appropriate definition from NEW_SSA_NAMES.
3253 2- If needed, new PHI nodes are added to the iterated dominance
3254 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3256 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3257 calling create_new_def_for to create new defs for names that the
3258 caller wants to replace.
3260 The caller cretaes the new names to be inserted and the names that need
3261 to be replaced by calling create_new_def_for for each old definition
3262 to be replaced. Note that the function assumes that the
3263 new defining statement has already been inserted in the IL.
3265 For instance, given the following code:
3268 2 x_1 = PHI (0, x_5)
3279 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3282 2 x_1 = PHI (0, x_5)
3295 We want to replace all the uses of x_1 with the new definitions of
3296 x_10 and x_11. Note that the only uses that should be replaced are
3297 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3298 *not* be replaced (this is why we cannot just mark symbol 'x' for
3301 Additionally, we may need to insert a PHI node at line 11 because
3302 that is a merge point for x_10 and x_11. So the use of x_1 at line
3303 11 will be replaced with the new PHI node. The insertion of PHI
3304 nodes is optional. They are not strictly necessary to preserve the
3305 SSA form, and depending on what the caller inserted, they may not
3306 even be useful for the optimizers. UPDATE_FLAGS controls various
3307 aspects of how update_ssa operates, see the documentation for
3308 TODO_update_ssa*. */
3311 update_ssa (unsigned update_flags
)
3313 basic_block bb
, start_bb
;
3317 sbitmap_iterator sbi
;
3320 /* Only one update flag should be set. */
3321 gcc_assert (update_flags
== TODO_update_ssa
3322 || update_flags
== TODO_update_ssa_no_phi
3323 || update_flags
== TODO_update_ssa_full_phi
3324 || update_flags
== TODO_update_ssa_only_virtuals
);
3326 if (!need_ssa_update_p (cfun
))
3331 timevar_push (TV_TREE_STMT_VERIFY
);
3335 FOR_EACH_BB_FN (bb
, cfun
)
3337 gimple_stmt_iterator gsi
;
3338 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3340 gimple
*stmt
= gsi_stmt (gsi
);
3343 use_operand_p use_p
;
3344 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_ALL_USES
)
3346 tree use
= USE_FROM_PTR (use_p
);
3347 if (TREE_CODE (use
) != SSA_NAME
)
3350 if (SSA_NAME_IN_FREE_LIST (use
))
3352 error ("statement uses released SSA name");
3353 debug_gimple_stmt (stmt
);
3354 fprintf (stderr
, "The use of ");
3355 print_generic_expr (stderr
, use
);
3356 fprintf (stderr
," should have been replaced\n");
3364 internal_error ("cannot update SSA form");
3366 timevar_pop (TV_TREE_STMT_VERIFY
);
3369 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3372 fprintf (dump_file
, "\nUpdating SSA:\n");
3374 if (!update_ssa_initialized_fn
)
3375 init_update_ssa (cfun
);
3376 else if (update_flags
== TODO_update_ssa_only_virtuals
)
3378 /* If we only need to update virtuals, remove all the mappings for
3379 real names before proceeding. The caller is responsible for
3380 having dealt with the name mappings before calling update_ssa. */
3381 bitmap_clear (old_ssa_names
);
3382 bitmap_clear (new_ssa_names
);
3385 gcc_assert (update_ssa_initialized_fn
== cfun
);
3387 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3388 if (!phis_to_rewrite
.exists ())
3389 phis_to_rewrite
.create (last_basic_block_for_fn (cfun
) + 1);
3390 blocks_to_update
= BITMAP_ALLOC (NULL
);
3392 /* Ensure that the dominance information is up-to-date. */
3393 calculate_dominance_info (CDI_DOMINATORS
);
3395 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3397 /* If there are names defined in the replacement table, prepare
3398 definition and use sites for all the names in NEW_SSA_NAMES and
3400 if (bitmap_first_set_bit (new_ssa_names
) >= 0)
3402 statistics_counter_event (cfun
, "Incremental SSA update", 1);
3404 prepare_names_to_update (insert_phi_p
);
3406 /* If all the names in NEW_SSA_NAMES had been marked for
3407 removal, and there are no symbols to rename, then there's
3408 nothing else to do. */
3409 if (bitmap_first_set_bit (new_ssa_names
) < 0
3410 && !cfun
->gimple_df
->ssa_renaming_needed
)
3414 /* Next, determine the block at which to start the renaming process. */
3415 if (cfun
->gimple_df
->ssa_renaming_needed
)
3417 statistics_counter_event (cfun
, "Symbol to SSA rewrite", 1);
3419 /* If we rename bare symbols initialize the mapping to
3420 auxiliar info we need to keep track of. */
3421 var_infos
= new hash_table
<var_info_hasher
> (47);
3423 /* If we have to rename some symbols from scratch, we need to
3424 start the process at the root of the CFG. FIXME, it should
3425 be possible to determine the nearest block that had a
3426 definition for each of the symbols that are marked for
3427 updating. For now this seems more work than it's worth. */
3428 start_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3430 /* Traverse the CFG looking for existing definitions and uses of
3431 symbols in SSA operands. Mark interesting blocks and
3432 statements and set local live-in information for the PHI
3433 placement heuristics. */
3434 prepare_block_for_update (start_bb
, insert_phi_p
);
3439 FOR_EACH_SSA_NAME (i
, name
, cfun
)
3441 if (virtual_operand_p (name
))
3444 /* For all but virtual operands, which do not have SSA names
3445 with overlapping life ranges, ensure that symbols marked
3446 for renaming do not have existing SSA names associated with
3447 them as we do not re-write them out-of-SSA before going
3448 into SSA for the remaining symbol uses. */
3449 if (marked_for_renaming (SSA_NAME_VAR (name
)))
3451 fprintf (stderr
, "Existing SSA name for symbol marked for "
3453 print_generic_expr (stderr
, name
, TDF_SLIM
);
3454 fprintf (stderr
, "\n");
3455 internal_error ("SSA corruption");
3461 /* Otherwise, the entry block to the region is the nearest
3462 common dominator for the blocks in BLOCKS. */
3463 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3467 /* If requested, insert PHI nodes at the iterated dominance frontier
3468 of every block, creating new definitions for names in OLD_SSA_NAMES
3469 and for symbols found. */
3474 /* If the caller requested PHI nodes to be added, compute
3475 dominance frontiers. */
3476 dfs
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
3477 FOR_EACH_BB_FN (bb
, cfun
)
3478 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
3479 compute_dominance_frontiers (dfs
);
3481 if (bitmap_first_set_bit (old_ssa_names
) >= 0)
3483 sbitmap_iterator sbi
;
3485 /* insert_update_phi_nodes_for will call add_new_name_mapping
3486 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3487 will grow while we are traversing it (but it will not
3488 gain any new members). Copy OLD_SSA_NAMES to a temporary
3490 auto_sbitmap
tmp (SBITMAP_SIZE (old_ssa_names
));
3491 bitmap_copy (tmp
, old_ssa_names
);
3492 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, sbi
)
3493 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3497 symbols_to_rename
.qsort (insert_updated_phi_nodes_compare_uids
);
3498 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3499 insert_updated_phi_nodes_for (sym
, dfs
, blocks_to_update
,
3502 FOR_EACH_BB_FN (bb
, cfun
)
3503 bitmap_clear (&dfs
[bb
->index
]);
3506 /* Insertion of PHI nodes may have added blocks to the region.
3507 We need to re-compute START_BB to include the newly added
3509 if (start_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3510 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3514 /* Reset the current definition for name and symbol before renaming
3516 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
3517 get_ssa_name_ann (ssa_name (i
))->info
.current_def
= NULL_TREE
;
3519 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3520 get_var_info (sym
)->info
.current_def
= NULL_TREE
;
3522 /* Now start the renaming process at START_BB. */
3523 interesting_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
3524 bitmap_clear (interesting_blocks
);
3525 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3526 bitmap_set_bit (interesting_blocks
, i
);
3528 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3530 sbitmap_free (interesting_blocks
);
3532 /* Debugging dumps. */
3538 dump_update_ssa (dump_file
);
3540 fprintf (dump_file
, "Incremental SSA update started at block: %d\n",
3544 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3546 fprintf (dump_file
, "Number of blocks in CFG: %d\n",
3547 last_basic_block_for_fn (cfun
));
3548 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n",
3549 c
, PERCENT (c
, last_basic_block_for_fn (cfun
)));
3551 if (dump_flags
& TDF_DETAILS
)
3553 fprintf (dump_file
, "Affected blocks:");
3554 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3555 fprintf (dump_file
, " %u", i
);
3556 fprintf (dump_file
, "\n");
3559 fprintf (dump_file
, "\n\n");
3562 /* Free allocated memory. */
3564 delete_update_ssa ();
3566 timevar_pop (TV_TREE_SSA_INCREMENTAL
);