1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2015 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"
41 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
43 /* This file builds the SSA form for a function as described in:
44 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
45 Computing Static Single Assignment Form and the Control Dependence
46 Graph. ACM Transactions on Programming Languages and Systems,
47 13(4):451-490, October 1991. */
49 /* Structure to map a variable VAR to the set of blocks that contain
50 definitions for VAR. */
53 /* Blocks that contain definitions of VAR. Bit I will be set if the
54 Ith block contains a definition of VAR. */
57 /* Blocks that contain a PHI node for VAR. */
60 /* Blocks where VAR is live-on-entry. Similar semantics as
65 /* Stack of trees used to restore the global currdefs to its original
66 state after completing rewriting of a block and its dominator
67 children. Its elements have the following properties:
69 - An SSA_NAME (N) indicates that the current definition of the
70 underlying variable should be set to the given SSA_NAME. If the
71 symbol associated with the SSA_NAME is not a GIMPLE register, the
72 next slot in the stack must be a _DECL node (SYM). In this case,
73 the name N in the previous slot is the current reaching
76 - A _DECL node indicates that the underlying variable has no
79 - A NULL node at the top entry is used to mark the last slot
80 associated with the current block. */
81 static vec
<tree
> block_defs_stack
;
84 /* Set of existing SSA names being replaced by update_ssa. */
85 static sbitmap old_ssa_names
;
87 /* Set of new SSA names being added by update_ssa. Note that both
88 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
89 the operations done on them are presence tests. */
90 static sbitmap new_ssa_names
;
92 static sbitmap interesting_blocks
;
94 /* Set of SSA names that have been marked to be released after they
95 were registered in the replacement table. They will be finally
96 released after we finish updating the SSA web. */
97 static bitmap names_to_release
;
99 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
100 the to basic block with index I. Allocated once per compilation, *not*
101 released between different functions. */
102 static vec
< vec
<gphi
*> > phis_to_rewrite
;
104 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
105 static bitmap blocks_with_phis_to_rewrite
;
107 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
108 to grow as the callers to create_new_def_for will create new names on
110 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
111 need to find a reasonable growth strategy. */
112 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
115 /* The function the SSA updating data structures have been initialized for.
116 NULL if they need to be initialized by create_new_def_for. */
117 static struct function
*update_ssa_initialized_fn
= NULL
;
119 /* Global data to attach to the main dominator walk structure. */
120 struct mark_def_sites_global_data
122 /* This bitmap contains the variables which are set before they
123 are used in a basic block. */
127 /* It is advantageous to avoid things like life analysis for variables which
128 do not need PHI nodes. This enum describes whether or not a particular
129 variable may need a PHI node. */
131 enum need_phi_state
{
132 /* This is the default. If we are still in this state after finding
133 all the definition and use sites, then we will assume the variable
134 needs PHI nodes. This is probably an overly conservative assumption. */
135 NEED_PHI_STATE_UNKNOWN
,
137 /* This state indicates that we have seen one or more sets of the
138 variable in a single basic block and that the sets dominate all
139 uses seen so far. If after finding all definition and use sites
140 we are still in this state, then the variable does not need any
144 /* This state indicates that we have either seen multiple definitions of
145 the variable in multiple blocks, or that we encountered a use in a
146 block that was not dominated by the block containing the set(s) of
147 this variable. This variable is assumed to need PHI nodes. */
151 /* Information stored for both SSA names and decls. */
154 /* This field indicates whether or not the variable may need PHI nodes.
155 See the enum's definition for more detailed information about the
157 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
159 /* The current reaching definition replacing this var. */
162 /* Definitions for this var. */
163 struct def_blocks def_blocks
;
166 /* Information stored for decls. */
172 /* Information stored for both SSA names and decls. */
177 /* VAR_INFOS hashtable helpers. */
179 struct var_info_hasher
: free_ptr_hash
<var_info
>
181 static inline hashval_t
hash (const value_type
&);
182 static inline bool equal (const value_type
&, const compare_type
&);
186 var_info_hasher::hash (const value_type
&p
)
188 return DECL_UID (p
->var
);
192 var_info_hasher::equal (const value_type
&p1
, const compare_type
&p2
)
194 return p1
->var
== p2
->var
;
198 /* Each entry in VAR_INFOS contains an element of type STRUCT
200 static hash_table
<var_info_hasher
> *var_infos
;
203 /* Information stored for SSA names. */
206 /* Age of this record (so that info_for_ssa_name table can be cleared
207 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
208 are assumed to be null. */
211 /* Replacement mappings, allocated from update_ssa_obstack. */
214 /* Information stored for both SSA names and decls. */
218 static vec
<ssa_name_info
*> info_for_ssa_name
;
219 static unsigned current_info_for_ssa_name_age
;
221 static bitmap_obstack update_ssa_obstack
;
223 /* The set of blocks affected by update_ssa. */
224 static bitmap blocks_to_update
;
226 /* The main entry point to the SSA renamer (rewrite_blocks) may be
227 called several times to do different, but related, tasks.
228 Initially, we need it to rename the whole program into SSA form.
229 At other times, we may need it to only rename into SSA newly
230 exposed symbols. Finally, we can also call it to incrementally fix
231 an already built SSA web. */
233 /* Convert the whole function into SSA form. */
236 /* Incrementally update the SSA web by replacing existing SSA
237 names with new ones. See update_ssa for details. */
241 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
242 static bitmap symbols_to_rename_set
;
243 static vec
<tree
> symbols_to_rename
;
245 /* Mark SYM for renaming. */
248 mark_for_renaming (tree sym
)
250 if (!symbols_to_rename_set
)
251 symbols_to_rename_set
= BITMAP_ALLOC (NULL
);
252 if (bitmap_set_bit (symbols_to_rename_set
, DECL_UID (sym
)))
253 symbols_to_rename
.safe_push (sym
);
256 /* Return true if SYM is marked for renaming. */
259 marked_for_renaming (tree sym
)
261 if (!symbols_to_rename_set
|| sym
== NULL_TREE
)
263 return bitmap_bit_p (symbols_to_rename_set
, DECL_UID (sym
));
267 /* Return true if STMT needs to be rewritten. When renaming a subset
268 of the variables, not all statements will be processed. This is
269 decided in mark_def_sites. */
272 rewrite_uses_p (gimple
*stmt
)
274 return gimple_visited_p (stmt
);
278 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
281 set_rewrite_uses (gimple
*stmt
, bool rewrite_p
)
283 gimple_set_visited (stmt
, rewrite_p
);
287 /* Return true if the DEFs created by statement STMT should be
288 registered when marking new definition sites. This is slightly
289 different than rewrite_uses_p: it's used by update_ssa to
290 distinguish statements that need to have both uses and defs
291 processed from those that only need to have their defs processed.
292 Statements that define new SSA names only need to have their defs
293 registered, but they don't need to have their uses renamed. */
296 register_defs_p (gimple
*stmt
)
298 return gimple_plf (stmt
, GF_PLF_1
) != 0;
302 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
305 set_register_defs (gimple
*stmt
, bool register_defs_p
)
307 gimple_set_plf (stmt
, GF_PLF_1
, register_defs_p
);
311 /* Get the information associated with NAME. */
313 static inline ssa_name_info
*
314 get_ssa_name_ann (tree name
)
316 unsigned ver
= SSA_NAME_VERSION (name
);
317 unsigned len
= info_for_ssa_name
.length ();
318 struct ssa_name_info
*info
;
320 /* Re-allocate the vector at most once per update/into-SSA. */
322 info_for_ssa_name
.safe_grow_cleared (num_ssa_names
);
324 /* But allocate infos lazily. */
325 info
= info_for_ssa_name
[ver
];
328 info
= XCNEW (struct ssa_name_info
);
329 info
->age
= current_info_for_ssa_name_age
;
330 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
331 info_for_ssa_name
[ver
] = info
;
334 if (info
->age
< current_info_for_ssa_name_age
)
336 info
->age
= current_info_for_ssa_name_age
;
337 info
->repl_set
= NULL
;
338 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
339 info
->info
.current_def
= NULL_TREE
;
340 info
->info
.def_blocks
.def_blocks
= NULL
;
341 info
->info
.def_blocks
.phi_blocks
= NULL
;
342 info
->info
.def_blocks
.livein_blocks
= NULL
;
348 /* Return and allocate the auxiliar information for DECL. */
350 static inline var_info
*
351 get_var_info (tree decl
)
356 slot
= var_infos
->find_slot_with_hash (&vi
, DECL_UID (decl
), INSERT
);
359 var_info
*v
= XCNEW (var_info
);
368 /* Clears info for SSA names. */
371 clear_ssa_name_info (void)
373 current_info_for_ssa_name_age
++;
375 /* If current_info_for_ssa_name_age wraps we use stale information.
376 Asser that this does not happen. */
377 gcc_assert (current_info_for_ssa_name_age
!= 0);
381 /* Get access to the auxiliar information stored per SSA name or decl. */
383 static inline common_info
*
384 get_common_info (tree var
)
386 if (TREE_CODE (var
) == SSA_NAME
)
387 return &get_ssa_name_ann (var
)->info
;
389 return &get_var_info (var
)->info
;
393 /* Return the current definition for VAR. */
396 get_current_def (tree var
)
398 return get_common_info (var
)->current_def
;
402 /* Sets current definition of VAR to DEF. */
405 set_current_def (tree var
, tree def
)
407 get_common_info (var
)->current_def
= def
;
410 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
411 all statements in basic block BB. */
414 initialize_flags_in_bb (basic_block bb
)
417 gimple_stmt_iterator gsi
;
419 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
421 gimple
*phi
= gsi_stmt (gsi
);
422 set_rewrite_uses (phi
, false);
423 set_register_defs (phi
, false);
426 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
428 stmt
= gsi_stmt (gsi
);
430 /* We are going to use the operand cache API, such as
431 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
432 cache for each statement should be up-to-date. */
433 gcc_checking_assert (!gimple_modified_p (stmt
));
434 set_rewrite_uses (stmt
, false);
435 set_register_defs (stmt
, false);
439 /* Mark block BB as interesting for update_ssa. */
442 mark_block_for_update (basic_block bb
)
444 gcc_checking_assert (blocks_to_update
!= NULL
);
445 if (!bitmap_set_bit (blocks_to_update
, bb
->index
))
447 initialize_flags_in_bb (bb
);
450 /* Return the set of blocks where variable VAR is defined and the blocks
451 where VAR is live on entry (livein). If no entry is found in
452 DEF_BLOCKS, a new one is created and returned. */
454 static inline def_blocks
*
455 get_def_blocks_for (common_info
*info
)
457 def_blocks
*db_p
= &info
->def_blocks
;
458 if (!db_p
->def_blocks
)
460 db_p
->def_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
461 db_p
->phi_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
462 db_p
->livein_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
469 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
470 VAR is defined by a PHI node. */
473 set_def_block (tree var
, basic_block bb
, bool phi_p
)
478 info
= get_common_info (var
);
479 db_p
= get_def_blocks_for (info
);
481 /* Set the bit corresponding to the block where VAR is defined. */
482 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
484 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
486 /* Keep track of whether or not we may need to insert PHI nodes.
488 If we are in the UNKNOWN state, then this is the first definition
489 of VAR. Additionally, we have not seen any uses of VAR yet, so
490 we do not need a PHI node for this variable at this time (i.e.,
491 transition to NEED_PHI_STATE_NO).
493 If we are in any other state, then we either have multiple definitions
494 of this variable occurring in different blocks or we saw a use of the
495 variable which was not dominated by the block containing the
496 definition(s). In this case we may need a PHI node, so enter
497 state NEED_PHI_STATE_MAYBE. */
498 if (info
->need_phi_state
== NEED_PHI_STATE_UNKNOWN
)
499 info
->need_phi_state
= NEED_PHI_STATE_NO
;
501 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
505 /* Mark block BB as having VAR live at the entry to BB. */
508 set_livein_block (tree var
, basic_block bb
)
513 info
= get_common_info (var
);
514 db_p
= get_def_blocks_for (info
);
516 /* Set the bit corresponding to the block where VAR is live in. */
517 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
519 /* Keep track of whether or not we may need to insert PHI nodes.
521 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
522 by the single block containing the definition(s) of this variable. If
523 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
524 NEED_PHI_STATE_MAYBE. */
525 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
527 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
529 if (def_block_index
== -1
530 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
531 BASIC_BLOCK_FOR_FN (cfun
, def_block_index
)))
532 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
535 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
539 /* Return true if NAME is in OLD_SSA_NAMES. */
542 is_old_name (tree name
)
544 unsigned ver
= SSA_NAME_VERSION (name
);
547 return (ver
< SBITMAP_SIZE (old_ssa_names
)
548 && bitmap_bit_p (old_ssa_names
, ver
));
552 /* Return true if NAME is in NEW_SSA_NAMES. */
555 is_new_name (tree name
)
557 unsigned ver
= SSA_NAME_VERSION (name
);
560 return (ver
< SBITMAP_SIZE (new_ssa_names
)
561 && bitmap_bit_p (new_ssa_names
, ver
));
565 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
568 names_replaced_by (tree new_tree
)
570 return get_ssa_name_ann (new_tree
)->repl_set
;
574 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
577 add_to_repl_tbl (tree new_tree
, tree old
)
579 bitmap
*set
= &get_ssa_name_ann (new_tree
)->repl_set
;
581 *set
= BITMAP_ALLOC (&update_ssa_obstack
);
582 bitmap_set_bit (*set
, SSA_NAME_VERSION (old
));
586 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
587 represents the set of names O_1 ... O_j replaced by N_i. This is
588 used by update_ssa and its helpers to introduce new SSA names in an
589 already formed SSA web. */
592 add_new_name_mapping (tree new_tree
, tree old
)
594 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
595 gcc_checking_assert (new_tree
!= old
596 && SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
598 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
599 caller may have created new names since the set was created. */
600 if (SBITMAP_SIZE (new_ssa_names
) <= num_ssa_names
- 1)
602 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
603 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
604 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
607 /* Update the REPL_TBL table. */
608 add_to_repl_tbl (new_tree
, old
);
610 /* If OLD had already been registered as a new name, then all the
611 names that OLD replaces should also be replaced by NEW_TREE. */
612 if (is_new_name (old
))
613 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
615 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
617 bitmap_set_bit (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
618 bitmap_set_bit (old_ssa_names
, SSA_NAME_VERSION (old
));
622 /* Call back for walk_dominator_tree used to collect definition sites
623 for every variable in the function. For every statement S in block
626 1- Variables defined by S in the DEFS of S are marked in the bitmap
629 2- If S uses a variable VAR and there is no preceding kill of VAR,
630 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
632 This information is used to determine which variables are live
633 across block boundaries to reduce the number of PHI nodes
637 mark_def_sites (basic_block bb
, gimple
*stmt
, bitmap kills
)
643 /* Since this is the first time that we rewrite the program into SSA
644 form, force an operand scan on every statement. */
647 gcc_checking_assert (blocks_to_update
== NULL
);
648 set_register_defs (stmt
, false);
649 set_rewrite_uses (stmt
, false);
651 if (is_gimple_debug (stmt
))
653 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
655 tree sym
= USE_FROM_PTR (use_p
);
656 gcc_checking_assert (DECL_P (sym
));
657 set_rewrite_uses (stmt
, true);
659 if (rewrite_uses_p (stmt
))
660 bitmap_set_bit (interesting_blocks
, bb
->index
);
664 /* If a variable is used before being set, then the variable is live
665 across a block boundary, so mark it live-on-entry to BB. */
666 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
668 tree sym
= USE_FROM_PTR (use_p
);
669 gcc_checking_assert (DECL_P (sym
));
670 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
671 set_livein_block (sym
, bb
);
672 set_rewrite_uses (stmt
, true);
675 /* Now process the defs. Mark BB as the definition block and add
676 each def to the set of killed symbols. */
677 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
679 gcc_checking_assert (DECL_P (def
));
680 set_def_block (def
, bb
, false);
681 bitmap_set_bit (kills
, DECL_UID (def
));
682 set_register_defs (stmt
, true);
685 /* If we found the statement interesting then also mark the block BB
687 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
688 bitmap_set_bit (interesting_blocks
, bb
->index
);
691 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
692 in the dfs numbering of the dominance tree. */
696 /* Basic block whose index this entry corresponds to. */
699 /* The dfs number of this node. */
703 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
707 cmp_dfsnum (const void *a
, const void *b
)
709 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
710 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
712 return (int) da
->dfs_num
- (int) db
->dfs_num
;
715 /* Among the intervals starting at the N points specified in DEFS, find
716 the one that contains S, and return its bb_index. */
719 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
721 unsigned f
= 0, t
= n
, m
;
726 if (defs
[m
].dfs_num
<= s
)
732 return defs
[f
].bb_index
;
735 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
736 KILLS is a bitmap of blocks where the value is defined before any use. */
739 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
742 unsigned i
, b
, p
, u
, top
;
744 basic_block def_bb
, use_bb
;
748 struct dom_dfsnum
*defs
;
749 unsigned n_defs
, adef
;
751 if (bitmap_empty_p (uses
))
757 /* The phi must dominate a use, or an argument of a live phi. Also, we
758 do not create any phi nodes in def blocks, unless they are also livein. */
759 to_remove
= BITMAP_ALLOC (NULL
);
760 bitmap_and_compl (to_remove
, kills
, uses
);
761 bitmap_and_compl_into (phis
, to_remove
);
762 if (bitmap_empty_p (phis
))
764 BITMAP_FREE (to_remove
);
768 /* We want to remove the unnecessary phi nodes, but we do not want to compute
769 liveness information, as that may be linear in the size of CFG, and if
770 there are lot of different variables to rewrite, this may lead to quadratic
773 Instead, we basically emulate standard dce. We put all uses to worklist,
774 then for each of them find the nearest def that dominates them. If this
775 def is a phi node, we mark it live, and if it was not live before, we
776 add the predecessors of its basic block to the worklist.
778 To quickly locate the nearest def that dominates use, we use dfs numbering
779 of the dominance tree (that is already available in order to speed up
780 queries). For each def, we have the interval given by the dfs number on
781 entry to and on exit from the corresponding subtree in the dominance tree.
782 The nearest dominator for a given use is the smallest of these intervals
783 that contains entry and exit dfs numbers for the basic block with the use.
784 If we store the bounds for all the uses to an array and sort it, we can
785 locate the nearest dominating def in logarithmic time by binary search.*/
786 bitmap_ior (to_remove
, kills
, phis
);
787 n_defs
= bitmap_count_bits (to_remove
);
788 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
789 defs
[0].bb_index
= 1;
792 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
794 def_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
795 defs
[adef
].bb_index
= i
;
796 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
797 defs
[adef
+ 1].bb_index
= i
;
798 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
801 BITMAP_FREE (to_remove
);
802 gcc_assert (adef
== 2 * n_defs
+ 1);
803 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
804 gcc_assert (defs
[0].bb_index
== 1);
806 /* Now each DEFS entry contains the number of the basic block to that the
807 dfs number corresponds. Change them to the number of basic block that
808 corresponds to the interval following the dfs number. Also, for the
809 dfs_out numbers, increase the dfs number by one (so that it corresponds
810 to the start of the following interval, not to the end of the current
811 one). We use WORKLIST as a stack. */
812 auto_vec
<int> worklist (n_defs
+ 1);
813 worklist
.quick_push (1);
816 for (i
= 1; i
< adef
; i
++)
818 b
= defs
[i
].bb_index
;
821 /* This is a closing element. Interval corresponding to the top
822 of the stack after removing it follows. */
824 top
= worklist
[worklist
.length () - 1];
825 defs
[n_defs
].bb_index
= top
;
826 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
830 /* Opening element. Nothing to do, just push it to the stack and move
831 it to the correct position. */
832 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
833 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
834 worklist
.quick_push (b
);
838 /* If this interval starts at the same point as the previous one, cancel
840 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
841 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
846 gcc_assert (worklist
.is_empty ());
848 /* Now process the uses. */
849 live_phis
= BITMAP_ALLOC (NULL
);
850 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
852 worklist
.safe_push (i
);
855 while (!worklist
.is_empty ())
858 if (b
== ENTRY_BLOCK
)
861 /* If there is a phi node in USE_BB, it is made live. Otherwise,
862 find the def that dominates the immediate dominator of USE_BB
863 (the kill in USE_BB does not dominate the use). */
864 if (bitmap_bit_p (phis
, b
))
868 use_bb
= get_immediate_dominator (CDI_DOMINATORS
,
869 BASIC_BLOCK_FOR_FN (cfun
, b
));
870 p
= find_dfsnum_interval (defs
, n_defs
,
871 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
872 if (!bitmap_bit_p (phis
, p
))
876 /* If the phi node is already live, there is nothing to do. */
877 if (!bitmap_set_bit (live_phis
, p
))
880 /* Add the new uses to the worklist. */
881 def_bb
= BASIC_BLOCK_FOR_FN (cfun
, p
);
882 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
885 if (bitmap_bit_p (uses
, u
))
888 /* In case there is a kill directly in the use block, do not record
889 the use (this is also necessary for correctness, as we assume that
890 uses dominated by a def directly in their block have been filtered
892 if (bitmap_bit_p (kills
, u
))
895 bitmap_set_bit (uses
, u
);
896 worklist
.safe_push (u
);
900 bitmap_copy (phis
, live_phis
);
901 BITMAP_FREE (live_phis
);
905 /* Return the set of blocks where variable VAR is defined and the blocks
906 where VAR is live on entry (livein). Return NULL, if no entry is
907 found in DEF_BLOCKS. */
909 static inline def_blocks
*
910 find_def_blocks_for (tree var
)
912 def_blocks
*p
= &get_common_info (var
)->def_blocks
;
919 /* Marks phi node PHI in basic block BB for rewrite. */
922 mark_phi_for_rewrite (basic_block bb
, gphi
*phi
)
925 unsigned n
, idx
= bb
->index
;
927 if (rewrite_uses_p (phi
))
930 set_rewrite_uses (phi
, true);
932 if (!blocks_with_phis_to_rewrite
)
935 bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
);
937 n
= (unsigned) last_basic_block_for_fn (cfun
) + 1;
938 if (phis_to_rewrite
.length () < n
)
939 phis_to_rewrite
.safe_grow_cleared (n
);
941 phis
= phis_to_rewrite
[idx
];
944 phis
.safe_push (phi
);
945 phis_to_rewrite
[idx
] = phis
;
948 /* Insert PHI nodes for variable VAR using the iterated dominance
949 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
950 function assumes that the caller is incrementally updating the
951 existing SSA form, in which case VAR may be an SSA name instead of
954 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
955 PHI node for VAR. On exit, only the nodes that received a PHI node
956 for VAR will be present in PHI_INSERTION_POINTS. */
959 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
966 def_blocks
*def_map
= find_def_blocks_for (var
);
968 /* Remove the blocks where we already have PHI nodes for VAR. */
969 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
971 /* Remove obviously useless phi nodes. */
972 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
973 def_map
->livein_blocks
);
975 /* And insert the PHI nodes. */
976 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
978 bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
980 mark_block_for_update (bb
);
982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
984 fprintf (dump_file
, "creating PHI node in block #%d for ", bb_index
);
985 print_generic_expr (dump_file
, var
, TDF_SLIM
);
986 fprintf (dump_file
, "\n");
990 if (TREE_CODE (var
) == SSA_NAME
)
992 /* If we are rewriting SSA names, create the LHS of the PHI
993 node by duplicating VAR. This is useful in the case of
994 pointers, to also duplicate pointer attributes (alias
995 information, in particular). */
999 gcc_checking_assert (update_p
);
1000 new_lhs
= duplicate_ssa_name (var
, NULL
);
1001 phi
= create_phi_node (new_lhs
, bb
);
1002 add_new_name_mapping (new_lhs
, var
);
1004 /* Add VAR to every argument slot of PHI. We need VAR in
1005 every argument so that rewrite_update_phi_arguments knows
1006 which name is this PHI node replacing. If VAR is a
1007 symbol marked for renaming, this is not necessary, the
1008 renamer will use the symbol on the LHS to get its
1009 reaching definition. */
1010 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1011 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1017 gcc_checking_assert (DECL_P (var
));
1018 phi
= create_phi_node (var
, bb
);
1020 tracked_var
= target_for_debug_bind (var
);
1023 gimple
*note
= gimple_build_debug_bind (tracked_var
,
1026 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1027 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1031 /* Mark this PHI node as interesting for update_ssa. */
1032 set_register_defs (phi
, true);
1033 mark_phi_for_rewrite (bb
, phi
);
1037 /* Sort var_infos after DECL_UID of their var. */
1040 insert_phi_nodes_compare_var_infos (const void *a
, const void *b
)
1042 const var_info
*defa
= *(var_info
* const *)a
;
1043 const var_info
*defb
= *(var_info
* const *)b
;
1044 if (DECL_UID (defa
->var
) < DECL_UID (defb
->var
))
1050 /* Insert PHI nodes at the dominance frontier of blocks with variable
1051 definitions. DFS contains the dominance frontier information for
1055 insert_phi_nodes (bitmap_head
*dfs
)
1057 hash_table
<var_info_hasher
>::iterator hi
;
1061 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1063 auto_vec
<var_info
*> vars (var_infos
->elements ());
1064 FOR_EACH_HASH_TABLE_ELEMENT (*var_infos
, info
, var_info_p
, hi
)
1065 if (info
->info
.need_phi_state
!= NEED_PHI_STATE_NO
)
1066 vars
.quick_push (info
);
1068 /* Do two stages to avoid code generation differences for UID
1069 differences but no UID ordering differences. */
1070 vars
.qsort (insert_phi_nodes_compare_var_infos
);
1072 FOR_EACH_VEC_ELT (vars
, i
, info
)
1074 bitmap idf
= compute_idf (info
->info
.def_blocks
.def_blocks
, dfs
);
1075 insert_phi_nodes_for (info
->var
, idf
, false);
1079 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1083 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1084 register DEF (an SSA_NAME) to be a new definition for SYM. */
1087 register_new_def (tree def
, tree sym
)
1089 common_info
*info
= get_common_info (sym
);
1092 /* If this variable is set in a single basic block and all uses are
1093 dominated by the set(s) in that single basic block, then there is
1094 no reason to record anything for this variable in the block local
1095 definition stacks. Doing so just wastes time and memory.
1097 This is the same test to prune the set of variables which may
1098 need PHI nodes. So we just use that information since it's already
1099 computed and available for us to use. */
1100 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1102 info
->current_def
= def
;
1106 currdef
= info
->current_def
;
1108 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1109 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1110 in the stack so that we know which symbol is being defined by
1111 this SSA name when we unwind the stack. */
1112 if (currdef
&& !is_gimple_reg (sym
))
1113 block_defs_stack
.safe_push (sym
);
1115 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1116 stack is later used by the dominator tree callbacks to restore
1117 the reaching definitions for all the variables defined in the
1118 block after a recursive visit to all its immediately dominated
1119 blocks. If there is no current reaching definition, then just
1120 record the underlying _DECL node. */
1121 block_defs_stack
.safe_push (currdef
? currdef
: sym
);
1123 /* Set the current reaching definition for SYM to be DEF. */
1124 info
->current_def
= def
;
1128 /* Perform a depth-first traversal of the dominator tree looking for
1129 variables to rename. BB is the block where to start searching.
1130 Renaming is a five step process:
1132 1- Every definition made by PHI nodes at the start of the blocks is
1133 registered as the current definition for the corresponding variable.
1135 2- Every statement in BB is rewritten. USE and VUSE operands are
1136 rewritten with their corresponding reaching definition. DEF and
1137 VDEF targets are registered as new definitions.
1139 3- All the PHI nodes in successor blocks of BB are visited. The
1140 argument corresponding to BB is replaced with its current reaching
1143 4- Recursively rewrite every dominator child block of BB.
1145 5- Restore (in reverse order) the current reaching definition for every
1146 new definition introduced in this block. This is done so that when
1147 we return from the recursive call, all the current reaching
1148 definitions are restored to the names that were valid in the
1149 dominator parent of BB. */
1151 /* Return the current definition for variable VAR. If none is found,
1152 create a new SSA name to act as the zeroth definition for VAR. */
1155 get_reaching_def (tree var
)
1157 common_info
*info
= get_common_info (var
);
1160 /* Lookup the current reaching definition for VAR. */
1161 currdef
= info
->current_def
;
1163 /* If there is no reaching definition for VAR, create and register a
1164 default definition for it (if needed). */
1165 if (currdef
== NULL_TREE
)
1167 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1168 currdef
= get_or_create_ssa_default_def (cfun
, sym
);
1171 /* Return the current reaching definition for VAR, or the default
1172 definition, if we had to create one. */
1177 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1180 rewrite_debug_stmt_uses (gimple
*stmt
)
1182 use_operand_p use_p
;
1184 bool update
= false;
1186 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1188 tree var
= USE_FROM_PTR (use_p
), def
;
1189 common_info
*info
= get_common_info (var
);
1190 gcc_checking_assert (DECL_P (var
));
1191 def
= info
->current_def
;
1194 if (TREE_CODE (var
) == PARM_DECL
1195 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun
)))
1197 gimple_stmt_iterator gsi
1199 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1201 /* Search a few source bind stmts at the start of first bb to
1202 see if a DEBUG_EXPR_DECL can't be reused. */
1204 !gsi_end_p (gsi
) && lim
> 0;
1205 gsi_next (&gsi
), lim
--)
1207 gimple
*gstmt
= gsi_stmt (gsi
);
1208 if (!gimple_debug_source_bind_p (gstmt
))
1210 if (gimple_debug_source_bind_get_value (gstmt
) == var
)
1212 def
= gimple_debug_source_bind_get_var (gstmt
);
1213 if (TREE_CODE (def
) == DEBUG_EXPR_DECL
)
1219 /* If not, add a new source bind stmt. */
1220 if (def
== NULL_TREE
)
1223 def
= make_node (DEBUG_EXPR_DECL
);
1224 def_temp
= gimple_build_debug_source_bind (def
, var
, NULL
);
1225 DECL_ARTIFICIAL (def
) = 1;
1226 TREE_TYPE (def
) = TREE_TYPE (var
);
1227 DECL_MODE (def
) = DECL_MODE (var
);
1229 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1230 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
1237 /* Check if info->current_def can be trusted. */
1238 basic_block bb
= gimple_bb (stmt
);
1240 = SSA_NAME_IS_DEFAULT_DEF (def
)
1241 ? NULL
: gimple_bb (SSA_NAME_DEF_STMT (def
));
1243 /* If definition is in current bb, it is fine. */
1246 /* If definition bb doesn't dominate the current bb,
1247 it can't be used. */
1248 else if (def_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
1250 /* If there is just one definition and dominates the current
1252 else if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1256 def_blocks
*db_p
= get_def_blocks_for (info
);
1258 /* If there are some non-debug uses in the current bb,
1260 if (bitmap_bit_p (db_p
->livein_blocks
, bb
->index
))
1262 /* Otherwise give up for now. */
1269 gimple_debug_bind_reset_value (stmt
);
1273 SET_USE (use_p
, def
);
1279 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1280 the block with its immediate reaching definitions. Update the current
1281 definition of a variable when a new real or virtual definition is found. */
1284 rewrite_stmt (gimple_stmt_iterator
*si
)
1286 use_operand_p use_p
;
1287 def_operand_p def_p
;
1289 gimple
*stmt
= gsi_stmt (*si
);
1291 /* If mark_def_sites decided that we don't need to rewrite this
1292 statement, ignore it. */
1293 gcc_assert (blocks_to_update
== NULL
);
1294 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1299 fprintf (dump_file
, "Renaming statement ");
1300 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1301 fprintf (dump_file
, "\n");
1304 /* Step 1. Rewrite USES in the statement. */
1305 if (rewrite_uses_p (stmt
))
1307 if (is_gimple_debug (stmt
))
1308 rewrite_debug_stmt_uses (stmt
);
1310 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1312 tree var
= USE_FROM_PTR (use_p
);
1313 gcc_checking_assert (DECL_P (var
));
1314 SET_USE (use_p
, get_reaching_def (var
));
1318 /* Step 2. Register the statement's DEF operands. */
1319 if (register_defs_p (stmt
))
1320 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1322 tree var
= DEF_FROM_PTR (def_p
);
1326 gcc_checking_assert (DECL_P (var
));
1328 if (gimple_clobber_p (stmt
)
1329 && is_gimple_reg (var
))
1331 /* If we rewrite a DECL into SSA form then drop its
1332 clobber stmts and replace uses with a new default def. */
1333 gcc_checking_assert (TREE_CODE (var
) == VAR_DECL
1334 && !gimple_vdef (stmt
));
1335 gsi_replace (si
, gimple_build_nop (), true);
1336 register_new_def (get_or_create_ssa_default_def (cfun
, var
), var
);
1340 name
= make_ssa_name (var
, stmt
);
1341 SET_DEF (def_p
, name
);
1342 register_new_def (DEF_FROM_PTR (def_p
), var
);
1344 tracked_var
= target_for_debug_bind (var
);
1347 gimple
*note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1348 gsi_insert_after (si
, note
, GSI_SAME_STMT
);
1354 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1355 PHI nodes. For every PHI node found, add a new argument containing the
1356 current reaching definition for the variable and the edge through which
1357 that definition is reaching the PHI node. */
1360 rewrite_add_phi_arguments (basic_block bb
)
1365 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1370 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1377 res
= gimple_phi_result (phi
);
1378 currdef
= get_reaching_def (SSA_NAME_VAR (res
));
1379 /* Virtual operand PHI args do not need a location. */
1380 if (virtual_operand_p (res
))
1381 loc
= UNKNOWN_LOCATION
;
1383 loc
= gimple_location (SSA_NAME_DEF_STMT (currdef
));
1384 add_phi_arg (phi
, currdef
, e
, loc
);
1389 class rewrite_dom_walker
: public dom_walker
1392 rewrite_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1394 virtual void before_dom_children (basic_block
);
1395 virtual void after_dom_children (basic_block
);
1398 /* SSA Rewriting Step 1. Initialization, create a block local stack
1399 of reaching definitions for new SSA names produced in this block
1400 (BLOCK_DEFS). Register new definitions for every PHI node in the
1404 rewrite_dom_walker::before_dom_children (basic_block bb
)
1406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1407 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1409 /* Mark the unwind point for this block. */
1410 block_defs_stack
.safe_push (NULL_TREE
);
1412 /* Step 1. Register new definitions for every PHI node in the block.
1413 Conceptually, all the PHI nodes are executed in parallel and each PHI
1414 node introduces a new version for the associated variable. */
1415 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1418 tree result
= gimple_phi_result (gsi_stmt (gsi
));
1419 register_new_def (result
, SSA_NAME_VAR (result
));
1422 /* Step 2. Rewrite every variable used in each statement in the block
1423 with its immediate reaching definitions. Update the current definition
1424 of a variable when a new real or virtual definition is found. */
1425 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
1426 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1428 rewrite_stmt (&gsi
);
1430 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1431 For every PHI node found, add a new argument containing the current
1432 reaching definition for the variable and the edge through which that
1433 definition is reaching the PHI node. */
1434 rewrite_add_phi_arguments (bb
);
1439 /* Called after visiting all the statements in basic block BB and all
1440 of its dominator children. Restore CURRDEFS to its original value. */
1443 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
1445 /* Restore CURRDEFS to its original state. */
1446 while (block_defs_stack
.length () > 0)
1448 tree tmp
= block_defs_stack
.pop ();
1449 tree saved_def
, var
;
1451 if (tmp
== NULL_TREE
)
1454 if (TREE_CODE (tmp
) == SSA_NAME
)
1456 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1457 current definition of its underlying variable. Note that
1458 if the SSA_NAME is not for a GIMPLE register, the symbol
1459 being defined is stored in the next slot in the stack.
1460 This mechanism is needed because an SSA name for a
1461 non-register symbol may be the definition for more than
1462 one symbol (e.g., SFTs, aliased variables, etc). */
1464 var
= SSA_NAME_VAR (saved_def
);
1465 if (!is_gimple_reg (var
))
1466 var
= block_defs_stack
.pop ();
1470 /* If we recorded anything else, it must have been a _DECL
1471 node and its current reaching definition must have been
1477 get_common_info (var
)->current_def
= saved_def
;
1482 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1485 debug_decl_set (bitmap set
)
1487 dump_decl_set (stderr
, set
);
1488 fprintf (stderr
, "\n");
1492 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1493 stack up to a maximum of N levels. If N is -1, the whole stack is
1494 dumped. New levels are created when the dominator tree traversal
1495 used for renaming enters a new sub-tree. */
1498 dump_defs_stack (FILE *file
, int n
)
1502 fprintf (file
, "\n\nRenaming stack");
1504 fprintf (file
, " (up to %d levels)", n
);
1505 fprintf (file
, "\n\n");
1508 fprintf (file
, "Level %d (current level)\n", i
);
1509 for (j
= (int) block_defs_stack
.length () - 1; j
>= 0; j
--)
1513 name
= block_defs_stack
[j
];
1514 if (name
== NULL_TREE
)
1519 fprintf (file
, "\nLevel %d\n", i
);
1530 var
= SSA_NAME_VAR (name
);
1531 if (!is_gimple_reg (var
))
1534 var
= block_defs_stack
[j
];
1538 fprintf (file
, " Previous CURRDEF (");
1539 print_generic_expr (file
, var
, 0);
1540 fprintf (file
, ") = ");
1542 print_generic_expr (file
, name
, 0);
1544 fprintf (file
, "<NIL>");
1545 fprintf (file
, "\n");
1550 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1551 stack up to a maximum of N levels. If N is -1, the whole stack is
1552 dumped. New levels are created when the dominator tree traversal
1553 used for renaming enters a new sub-tree. */
1556 debug_defs_stack (int n
)
1558 dump_defs_stack (stderr
, n
);
1562 /* Dump the current reaching definition of every symbol to FILE. */
1565 dump_currdefs (FILE *file
)
1570 if (symbols_to_rename
.is_empty ())
1573 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1574 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, var
)
1576 common_info
*info
= get_common_info (var
);
1577 fprintf (file
, "CURRDEF (");
1578 print_generic_expr (file
, var
, 0);
1579 fprintf (file
, ") = ");
1580 if (info
->current_def
)
1581 print_generic_expr (file
, info
->current_def
, 0);
1583 fprintf (file
, "<NIL>");
1584 fprintf (file
, "\n");
1589 /* Dump the current reaching definition of every symbol to stderr. */
1592 debug_currdefs (void)
1594 dump_currdefs (stderr
);
1598 /* Dump SSA information to FILE. */
1601 dump_tree_ssa (FILE *file
)
1603 const char *funcname
1604 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1606 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1608 dump_var_infos (file
);
1609 dump_defs_stack (file
, -1);
1610 dump_currdefs (file
);
1611 dump_tree_ssa_stats (file
);
1615 /* Dump SSA information to stderr. */
1618 debug_tree_ssa (void)
1620 dump_tree_ssa (stderr
);
1624 /* Dump statistics for the hash table HTAB. */
1627 htab_statistics (FILE *file
, const hash_table
<var_info_hasher
> &htab
)
1629 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1630 (long) htab
.size (),
1631 (long) htab
.elements (),
1632 htab
.collisions ());
1636 /* Dump SSA statistics on FILE. */
1639 dump_tree_ssa_stats (FILE *file
)
1643 fprintf (file
, "\nHash table statistics:\n");
1644 fprintf (file
, " var_infos: ");
1645 htab_statistics (file
, *var_infos
);
1646 fprintf (file
, "\n");
1651 /* Dump SSA statistics on stderr. */
1654 debug_tree_ssa_stats (void)
1656 dump_tree_ssa_stats (stderr
);
1660 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1663 debug_var_infos_r (var_info
**slot
, FILE *file
)
1665 var_info
*info
= *slot
;
1667 fprintf (file
, "VAR: ");
1668 print_generic_expr (file
, info
->var
, dump_flags
);
1669 bitmap_print (file
, info
->info
.def_blocks
.def_blocks
,
1670 ", DEF_BLOCKS: { ", "}");
1671 bitmap_print (file
, info
->info
.def_blocks
.livein_blocks
,
1672 ", LIVEIN_BLOCKS: { ", "}");
1673 bitmap_print (file
, info
->info
.def_blocks
.phi_blocks
,
1674 ", PHI_BLOCKS: { ", "}\n");
1680 /* Dump the VAR_INFOS hash table on FILE. */
1683 dump_var_infos (FILE *file
)
1685 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1687 var_infos
->traverse
<FILE *, debug_var_infos_r
> (file
);
1691 /* Dump the VAR_INFOS hash table on stderr. */
1694 debug_var_infos (void)
1696 dump_var_infos (stderr
);
1700 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1703 register_new_update_single (tree new_name
, tree old_name
)
1705 common_info
*info
= get_common_info (old_name
);
1706 tree currdef
= info
->current_def
;
1708 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1709 This stack is later used by the dominator tree callbacks to
1710 restore the reaching definitions for all the variables
1711 defined in the block after a recursive visit to all its
1712 immediately dominated blocks. */
1713 block_defs_stack
.reserve (2);
1714 block_defs_stack
.quick_push (currdef
);
1715 block_defs_stack
.quick_push (old_name
);
1717 /* Set the current reaching definition for OLD_NAME to be
1719 info
->current_def
= new_name
;
1723 /* Register NEW_NAME to be the new reaching definition for all the
1724 names in OLD_NAMES. Used by the incremental SSA update routines to
1725 replace old SSA names with new ones. */
1728 register_new_update_set (tree new_name
, bitmap old_names
)
1733 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1734 register_new_update_single (new_name
, ssa_name (i
));
1739 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1740 it is a symbol marked for renaming, replace it with USE_P's current
1741 reaching definition. */
1744 maybe_replace_use (use_operand_p use_p
)
1746 tree rdef
= NULL_TREE
;
1747 tree use
= USE_FROM_PTR (use_p
);
1748 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1750 if (marked_for_renaming (sym
))
1751 rdef
= get_reaching_def (sym
);
1752 else if (is_old_name (use
))
1753 rdef
= get_reaching_def (use
);
1755 if (rdef
&& rdef
!= use
)
1756 SET_USE (use_p
, rdef
);
1760 /* Same as maybe_replace_use, but without introducing default stmts,
1761 returning false to indicate a need to do so. */
1764 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1766 tree rdef
= NULL_TREE
;
1767 tree use
= USE_FROM_PTR (use_p
);
1768 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1770 if (marked_for_renaming (sym
))
1771 rdef
= get_var_info (sym
)->info
.current_def
;
1772 else if (is_old_name (use
))
1774 rdef
= get_ssa_name_ann (use
)->info
.current_def
;
1775 /* We can't assume that, if there's no current definition, the
1776 default one should be used. It could be the case that we've
1777 rearranged blocks so that the earlier definition no longer
1778 dominates the use. */
1779 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1785 if (rdef
&& rdef
!= use
)
1786 SET_USE (use_p
, rdef
);
1788 return rdef
!= NULL_TREE
;
1792 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1793 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1794 register it as the current definition for the names replaced by
1795 DEF_P. Returns whether the statement should be removed. */
1798 maybe_register_def (def_operand_p def_p
, gimple
*stmt
,
1799 gimple_stmt_iterator gsi
)
1801 tree def
= DEF_FROM_PTR (def_p
);
1802 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1803 bool to_delete
= false;
1805 /* If DEF is a naked symbol that needs renaming, create a new
1807 if (marked_for_renaming (sym
))
1811 if (gimple_clobber_p (stmt
) && is_gimple_reg (sym
))
1813 gcc_checking_assert (TREE_CODE (sym
) == VAR_DECL
);
1814 /* Replace clobber stmts with a default def. This new use of a
1815 default definition may make it look like SSA_NAMEs have
1816 conflicting lifetimes, so we need special code to let them
1817 coalesce properly. */
1819 def
= get_or_create_ssa_default_def (cfun
, sym
);
1822 def
= make_ssa_name (def
, stmt
);
1823 SET_DEF (def_p
, def
);
1825 tree tracked_var
= target_for_debug_bind (sym
);
1828 gimple
*note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1829 /* If stmt ends the bb, insert the debug stmt on the single
1830 non-EH edge from the stmt. */
1831 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1833 basic_block bb
= gsi_bb (gsi
);
1836 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1837 if (!(e
->flags
& EDGE_EH
))
1839 gcc_checking_assert (!ef
);
1842 /* If there are other predecessors to ef->dest, then
1843 there must be PHI nodes for the modified
1844 variable, and therefore there will be debug bind
1845 stmts after the PHI nodes. The debug bind notes
1846 we'd insert would force the creation of a new
1847 block (diverging codegen) and be redundant with
1848 the post-PHI bind stmts, so don't add them.
1850 As for the exit edge, there wouldn't be redundant
1851 bind stmts, but there wouldn't be a PC to bind
1852 them to either, so avoid diverging the CFG. */
1853 if (ef
&& single_pred_p (ef
->dest
)
1854 && ef
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1856 /* If there were PHI nodes in the node, we'd
1857 have to make sure the value we're binding
1858 doesn't need rewriting. But there shouldn't
1859 be PHI nodes in a single-predecessor block,
1860 so we just add the note. */
1861 gsi_insert_on_edge_immediate (ef
, note
);
1865 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1869 register_new_update_single (def
, sym
);
1873 /* If DEF is a new name, register it as a new definition
1874 for all the names replaced by DEF. */
1875 if (is_new_name (def
))
1876 register_new_update_set (def
, names_replaced_by (def
));
1878 /* If DEF is an old name, register DEF as a new
1879 definition for itself. */
1880 if (is_old_name (def
))
1881 register_new_update_single (def
, def
);
1888 /* Update every variable used in the statement pointed-to by SI. The
1889 statement is assumed to be in SSA form already. Names in
1890 OLD_SSA_NAMES used by SI will be updated to their current reaching
1891 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1892 will be registered as a new definition for their corresponding name
1893 in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1896 rewrite_update_stmt (gimple
*stmt
, gimple_stmt_iterator gsi
)
1898 use_operand_p use_p
;
1899 def_operand_p def_p
;
1902 /* Only update marked statements. */
1903 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1908 fprintf (dump_file
, "Updating SSA information for statement ");
1909 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1912 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1913 symbol is marked for renaming. */
1914 if (rewrite_uses_p (stmt
))
1916 if (is_gimple_debug (stmt
))
1918 bool failed
= false;
1920 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1921 if (!maybe_replace_use_in_debug_stmt (use_p
))
1929 /* DOM sometimes threads jumps in such a way that a
1930 debug stmt ends up referencing a SSA variable that no
1931 longer dominates the debug stmt, but such that all
1932 incoming definitions refer to the same definition in
1933 an earlier dominator. We could try to recover that
1934 definition somehow, but this will have to do for now.
1936 Introducing a default definition, which is what
1937 maybe_replace_use() would do in such cases, may
1938 modify code generation, for the otherwise-unused
1939 default definition would never go away, modifying SSA
1940 version numbers all over. */
1941 gimple_debug_bind_reset_value (stmt
);
1947 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1948 maybe_replace_use (use_p
);
1952 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1953 Also register definitions for names whose underlying symbol is
1954 marked for renaming. */
1955 bool to_delete
= false;
1956 if (register_defs_p (stmt
))
1957 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1958 to_delete
|= maybe_register_def (def_p
, stmt
, gsi
);
1964 /* Visit all the successor blocks of BB looking for PHI nodes. For
1965 every PHI node found, check if any of its arguments is in
1966 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1967 definition, replace it. */
1970 rewrite_update_phi_arguments (basic_block bb
)
1976 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1981 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
1984 phis
= phis_to_rewrite
[e
->dest
->index
];
1985 FOR_EACH_VEC_ELT (phis
, i
, phi
)
1987 tree arg
, lhs_sym
, reaching_def
= NULL
;
1988 use_operand_p arg_p
;
1990 gcc_checking_assert (rewrite_uses_p (phi
));
1992 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
1993 arg
= USE_FROM_PTR (arg_p
);
1995 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
1998 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2000 if (arg
== NULL_TREE
)
2002 /* When updating a PHI node for a recently introduced
2003 symbol we may find NULL arguments. That's why we
2004 take the symbol from the LHS of the PHI node. */
2005 reaching_def
= get_reaching_def (lhs_sym
);
2010 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2012 if (marked_for_renaming (sym
))
2013 reaching_def
= get_reaching_def (sym
);
2014 else if (is_old_name (arg
))
2015 reaching_def
= get_reaching_def (arg
);
2018 /* Update the argument if there is a reaching def. */
2021 source_location locus
;
2022 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2024 SET_USE (arg_p
, reaching_def
);
2026 /* Virtual operands do not need a location. */
2027 if (virtual_operand_p (reaching_def
))
2028 locus
= UNKNOWN_LOCATION
;
2031 gimple
*stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2032 gphi
*other_phi
= dyn_cast
<gphi
*> (stmt
);
2034 /* Single element PHI nodes behave like copies, so get the
2035 location from the phi argument. */
2037 && gimple_phi_num_args (other_phi
) == 1)
2038 locus
= gimple_phi_arg_location (other_phi
, 0);
2040 locus
= gimple_location (stmt
);
2043 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2047 if (e
->flags
& EDGE_ABNORMAL
)
2048 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2053 class rewrite_update_dom_walker
: public dom_walker
2056 rewrite_update_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2058 virtual void before_dom_children (basic_block
);
2059 virtual void after_dom_children (basic_block
);
2062 /* Initialization of block data structures for the incremental SSA
2063 update pass. Create a block local stack of reaching definitions
2064 for new SSA names produced in this block (BLOCK_DEFS). Register
2065 new definitions for every PHI node in the block. */
2068 rewrite_update_dom_walker::before_dom_children (basic_block bb
)
2070 bool is_abnormal_phi
;
2072 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2073 fprintf (dump_file
, "Registering new PHI nodes in block #%d\n",
2076 /* Mark the unwind point for this block. */
2077 block_defs_stack
.safe_push (NULL_TREE
);
2079 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2082 /* Mark the LHS if any of the arguments flows through an abnormal
2084 is_abnormal_phi
= bb_has_abnormal_pred (bb
);
2086 /* If any of the PHI nodes is a replacement for a name in
2087 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2088 register it as a new definition for its corresponding name. Also
2089 register definitions for names whose underlying symbols are
2090 marked for renaming. */
2091 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2095 gphi
*phi
= gsi
.phi ();
2097 if (!register_defs_p (phi
))
2100 lhs
= gimple_phi_result (phi
);
2101 lhs_sym
= SSA_NAME_VAR (lhs
);
2103 if (marked_for_renaming (lhs_sym
))
2104 register_new_update_single (lhs
, lhs_sym
);
2108 /* If LHS is a new name, register a new definition for all
2109 the names replaced by LHS. */
2110 if (is_new_name (lhs
))
2111 register_new_update_set (lhs
, names_replaced_by (lhs
));
2113 /* If LHS is an OLD name, register it as a new definition
2115 if (is_old_name (lhs
))
2116 register_new_update_single (lhs
, lhs
);
2119 if (is_abnormal_phi
)
2120 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2123 /* Step 2. Rewrite every variable used in each statement in the block. */
2124 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
2126 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2127 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2128 if (rewrite_update_stmt (gsi_stmt (gsi
), gsi
))
2129 gsi_remove (&gsi
, true);
2134 /* Step 3. Update PHI nodes. */
2135 rewrite_update_phi_arguments (bb
);
2138 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2139 the current reaching definition of every name re-written in BB to
2140 the original reaching definition before visiting BB. This
2141 unwinding must be done in the opposite order to what is done in
2142 register_new_update_set. */
2145 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
2147 while (block_defs_stack
.length () > 0)
2149 tree var
= block_defs_stack
.pop ();
2152 /* NULL indicates the unwind stop point for this block (see
2153 rewrite_update_enter_block). */
2157 saved_def
= block_defs_stack
.pop ();
2158 get_common_info (var
)->current_def
= saved_def
;
2163 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2166 ENTRY indicates the block where to start. Every block dominated by
2167 ENTRY will be rewritten.
2169 WHAT indicates what actions will be taken by the renamer (see enum
2172 BLOCKS are the set of interesting blocks for the dominator walker
2173 to process. If this set is NULL, then all the nodes dominated
2174 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2175 are not present in BLOCKS are ignored. */
2178 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2180 /* Rewrite all the basic blocks in the program. */
2181 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2183 block_defs_stack
.create (10);
2185 /* Recursively walk the dominator tree rewriting each statement in
2186 each basic block. */
2187 if (what
== REWRITE_ALL
)
2188 rewrite_dom_walker (CDI_DOMINATORS
).walk (entry
);
2189 else if (what
== REWRITE_UPDATE
)
2190 rewrite_update_dom_walker (CDI_DOMINATORS
).walk (entry
);
2194 /* Debugging dumps. */
2195 if (dump_file
&& (dump_flags
& TDF_STATS
))
2197 dump_dfa_stats (dump_file
);
2199 dump_tree_ssa_stats (dump_file
);
2202 block_defs_stack
.release ();
2204 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2207 class mark_def_dom_walker
: public dom_walker
2210 mark_def_dom_walker (cdi_direction direction
);
2211 ~mark_def_dom_walker ();
2213 virtual void before_dom_children (basic_block
);
2216 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2217 large enough to accommodate all the variables referenced in the
2218 function, not just the ones we are renaming. */
2222 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction
)
2223 : dom_walker (direction
), m_kills (BITMAP_ALLOC (NULL
))
2227 mark_def_dom_walker::~mark_def_dom_walker ()
2229 BITMAP_FREE (m_kills
);
2232 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2233 at the start of each block, and call mark_def_sites for each statement. */
2236 mark_def_dom_walker::before_dom_children (basic_block bb
)
2238 gimple_stmt_iterator gsi
;
2240 bitmap_clear (m_kills
);
2241 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2242 mark_def_sites (bb
, gsi_stmt (gsi
), m_kills
);
2245 /* Initialize internal data needed during renaming. */
2248 init_ssa_renamer (void)
2250 cfun
->gimple_df
->in_ssa_p
= false;
2252 /* Allocate memory for the DEF_BLOCKS hash table. */
2253 gcc_assert (!var_infos
);
2254 var_infos
= new hash_table
<var_info_hasher
>
2255 (vec_safe_length (cfun
->local_decls
));
2257 bitmap_obstack_initialize (&update_ssa_obstack
);
2261 /* Deallocate internal data structures used by the renamer. */
2264 fini_ssa_renamer (void)
2269 bitmap_obstack_release (&update_ssa_obstack
);
2271 cfun
->gimple_df
->ssa_renaming_needed
= 0;
2272 cfun
->gimple_df
->rename_vops
= 0;
2273 cfun
->gimple_df
->in_ssa_p
= true;
2276 /* Main entry point into the SSA builder. The renaming process
2277 proceeds in four main phases:
2279 1- Compute dominance frontier and immediate dominators, needed to
2280 insert PHI nodes and rename the function in dominator tree
2283 2- Find and mark all the blocks that define variables.
2285 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2287 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2289 Steps 3 and 4 are done using the dominator tree walker
2290 (walk_dominator_tree). */
2294 const pass_data pass_data_build_ssa
=
2296 GIMPLE_PASS
, /* type */
2298 OPTGROUP_NONE
, /* optinfo_flags */
2299 TV_TREE_SSA_OTHER
, /* tv_id */
2300 PROP_cfg
, /* properties_required */
2301 PROP_ssa
, /* properties_provided */
2302 0, /* properties_destroyed */
2303 0, /* todo_flags_start */
2304 TODO_remove_unused_locals
, /* todo_flags_finish */
2307 class pass_build_ssa
: public gimple_opt_pass
2310 pass_build_ssa (gcc::context
*ctxt
)
2311 : gimple_opt_pass (pass_data_build_ssa
, ctxt
)
2314 /* opt_pass methods: */
2315 virtual bool gate (function
*fun
)
2317 /* Do nothing for funcions that was produced already in SSA form. */
2318 return !(fun
->curr_properties
& PROP_ssa
);
2321 virtual unsigned int execute (function
*);
2323 }; // class pass_build_ssa
2326 pass_build_ssa::execute (function
*fun
)
2332 /* Initialize operand data structures. */
2333 init_ssa_operands (fun
);
2335 /* Initialize internal data needed by the renamer. */
2336 init_ssa_renamer ();
2338 /* Initialize the set of interesting blocks. The callback
2339 mark_def_sites will add to this set those blocks that the renamer
2341 interesting_blocks
= sbitmap_alloc (last_basic_block_for_fn (fun
));
2342 bitmap_clear (interesting_blocks
);
2344 /* Initialize dominance frontier. */
2345 dfs
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (fun
));
2346 FOR_EACH_BB_FN (bb
, fun
)
2347 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
2349 /* 1- Compute dominance frontiers. */
2350 calculate_dominance_info (CDI_DOMINATORS
);
2351 compute_dominance_frontiers (dfs
);
2353 /* 2- Find and mark definition sites. */
2354 mark_def_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2356 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2357 insert_phi_nodes (dfs
);
2359 /* 4- Rename all the blocks. */
2360 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun
), REWRITE_ALL
);
2362 /* Free allocated memory. */
2363 FOR_EACH_BB_FN (bb
, fun
)
2364 bitmap_clear (&dfs
[bb
->index
]);
2367 sbitmap_free (interesting_blocks
);
2369 fini_ssa_renamer ();
2371 /* Try to get rid of all gimplifier generated temporaries by making
2372 its SSA names anonymous. This way we can garbage collect them
2373 all after removing unused locals which we do in our TODO. */
2374 for (i
= 1; i
< num_ssa_names
; ++i
)
2376 tree decl
, name
= ssa_name (i
);
2378 || SSA_NAME_IS_DEFAULT_DEF (name
))
2380 decl
= SSA_NAME_VAR (name
);
2382 && TREE_CODE (decl
) == VAR_DECL
2383 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl
)
2384 && DECL_IGNORED_P (decl
))
2385 SET_SSA_NAME_VAR_OR_IDENTIFIER (name
, DECL_NAME (decl
));
2394 make_pass_build_ssa (gcc::context
*ctxt
)
2396 return new pass_build_ssa (ctxt
);
2400 /* Mark the definition of VAR at STMT and BB as interesting for the
2401 renamer. BLOCKS is the set of blocks that need updating. */
2404 mark_def_interesting (tree var
, gimple
*stmt
, basic_block bb
,
2407 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2408 set_register_defs (stmt
, true);
2412 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2414 set_def_block (var
, bb
, is_phi_p
);
2416 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2417 site for both itself and all the old names replaced by it. */
2418 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2422 bitmap set
= names_replaced_by (var
);
2424 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2425 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2431 /* Mark the use of VAR at STMT and BB as interesting for the
2432 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2436 mark_use_interesting (tree var
, gimple
*stmt
, basic_block bb
,
2439 basic_block def_bb
= gimple_bb (stmt
);
2441 mark_block_for_update (def_bb
);
2442 mark_block_for_update (bb
);
2444 if (gimple_code (stmt
) == GIMPLE_PHI
)
2445 mark_phi_for_rewrite (def_bb
, as_a
<gphi
*> (stmt
));
2448 set_rewrite_uses (stmt
, true);
2450 if (is_gimple_debug (stmt
))
2454 /* If VAR has not been defined in BB, then it is live-on-entry
2455 to BB. Note that we cannot just use the block holding VAR's
2456 definition because if VAR is one of the names in OLD_SSA_NAMES,
2457 it will have several definitions (itself and all the names that
2461 def_blocks
*db_p
= get_def_blocks_for (get_common_info (var
));
2462 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2463 set_livein_block (var
, bb
);
2468 /* Do a dominator walk starting at BB processing statements that
2469 reference symbols in SSA operands. This is very similar to
2470 mark_def_sites, but the scan handles statements whose operands may
2471 already be SSA names.
2473 If INSERT_PHI_P is true, mark those uses as live in the
2474 corresponding block. This is later used by the PHI placement
2475 algorithm to make PHI pruning decisions.
2477 FIXME. Most of this would be unnecessary if we could associate a
2478 symbol to all the SSA names that reference it. But that
2479 sounds like it would be expensive to maintain. Still, it
2480 would be interesting to see if it makes better sense to do
2484 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2490 mark_block_for_update (bb
);
2492 /* Process PHI nodes marking interesting those that define or use
2493 the symbols that we are interested in. */
2494 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
2497 gphi
*phi
= si
.phi ();
2498 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2500 if (TREE_CODE (lhs
) == SSA_NAME
2501 && (! virtual_operand_p (lhs
)
2502 || ! cfun
->gimple_df
->rename_vops
))
2505 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2506 mark_for_renaming (lhs_sym
);
2507 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2509 /* Mark the uses in phi nodes as interesting. It would be more correct
2510 to process the arguments of the phi nodes of the successor edges of
2511 BB at the end of prepare_block_for_update, however, that turns out
2512 to be significantly more expensive. Doing it here is conservatively
2513 correct -- it may only cause us to believe a value to be live in a
2514 block that also contains its definition, and thus insert a few more
2515 phi nodes for it. */
2516 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2517 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2520 /* Process the statements. */
2521 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
2526 use_operand_p use_p
;
2527 def_operand_p def_p
;
2529 stmt
= gsi_stmt (si
);
2531 if (cfun
->gimple_df
->rename_vops
2532 && gimple_vuse (stmt
))
2534 tree use
= gimple_vuse (stmt
);
2535 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2536 mark_for_renaming (sym
);
2537 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2540 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_USE
)
2542 tree use
= USE_FROM_PTR (use_p
);
2545 mark_for_renaming (use
);
2546 mark_use_interesting (use
, stmt
, bb
, insert_phi_p
);
2549 if (cfun
->gimple_df
->rename_vops
2550 && gimple_vdef (stmt
))
2552 tree def
= gimple_vdef (stmt
);
2553 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2554 mark_for_renaming (sym
);
2555 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2558 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_DEF
)
2560 tree def
= DEF_FROM_PTR (def_p
);
2563 mark_for_renaming (def
);
2564 mark_def_interesting (def
, stmt
, bb
, insert_phi_p
);
2568 /* Now visit all the blocks dominated by BB. */
2569 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2571 son
= next_dom_son (CDI_DOMINATORS
, son
))
2572 prepare_block_for_update (son
, insert_phi_p
);
2576 /* Helper for prepare_names_to_update. Mark all the use sites for
2577 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2578 prepare_names_to_update. */
2581 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2583 use_operand_p use_p
;
2584 imm_use_iterator iter
;
2586 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2588 gimple
*stmt
= USE_STMT (use_p
);
2589 basic_block bb
= gimple_bb (stmt
);
2591 if (gimple_code (stmt
) == GIMPLE_PHI
)
2593 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2594 edge e
= gimple_phi_arg_edge (as_a
<gphi
*> (stmt
), ix
);
2595 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2599 /* For regular statements, mark this as an interesting use
2601 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2607 /* Helper for prepare_names_to_update. Mark the definition site for
2608 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2609 prepare_names_to_update. */
2612 prepare_def_site_for (tree name
, bool insert_phi_p
)
2617 gcc_checking_assert (names_to_release
== NULL
2618 || !bitmap_bit_p (names_to_release
,
2619 SSA_NAME_VERSION (name
)));
2621 stmt
= SSA_NAME_DEF_STMT (name
);
2622 bb
= gimple_bb (stmt
);
2625 gcc_checking_assert (bb
->index
< last_basic_block_for_fn (cfun
));
2626 mark_block_for_update (bb
);
2627 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2632 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2633 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2634 PHI nodes for newly created names. */
2637 prepare_names_to_update (bool insert_phi_p
)
2641 sbitmap_iterator sbi
;
2643 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2644 remove it from NEW_SSA_NAMES so that we don't try to visit its
2645 defining basic block (which most likely doesn't exist). Notice
2646 that we cannot do the same with names in OLD_SSA_NAMES because we
2647 want to replace existing instances. */
2648 if (names_to_release
)
2649 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2650 bitmap_clear_bit (new_ssa_names
, i
);
2652 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2653 names may be considered to be live-in on blocks that contain
2654 definitions for their replacements. */
2655 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2656 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2658 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2659 OLD_SSA_NAMES, but we have to ignore its definition site. */
2660 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
2662 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2663 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2664 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2669 /* Dump all the names replaced by NAME to FILE. */
2672 dump_names_replaced_by (FILE *file
, tree name
)
2678 print_generic_expr (file
, name
, 0);
2679 fprintf (file
, " -> { ");
2681 old_set
= names_replaced_by (name
);
2682 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2684 print_generic_expr (file
, ssa_name (i
), 0);
2685 fprintf (file
, " ");
2688 fprintf (file
, "}\n");
2692 /* Dump all the names replaced by NAME to stderr. */
2695 debug_names_replaced_by (tree name
)
2697 dump_names_replaced_by (stderr
, name
);
2701 /* Dump SSA update information to FILE. */
2704 dump_update_ssa (FILE *file
)
2709 if (!need_ssa_update_p (cfun
))
2712 if (new_ssa_names
&& bitmap_first_set_bit (new_ssa_names
) >= 0)
2714 sbitmap_iterator sbi
;
2716 fprintf (file
, "\nSSA replacement table\n");
2717 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2718 "O_1, ..., O_j\n\n");
2720 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2721 dump_names_replaced_by (file
, ssa_name (i
));
2724 if (symbols_to_rename_set
&& !bitmap_empty_p (symbols_to_rename_set
))
2726 fprintf (file
, "\nSymbols to be put in SSA form\n");
2727 dump_decl_set (file
, symbols_to_rename_set
);
2728 fprintf (file
, "\n");
2731 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2733 fprintf (file
, "\nSSA names to release after updating the SSA web\n\n");
2734 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2736 print_generic_expr (file
, ssa_name (i
), 0);
2737 fprintf (file
, " ");
2739 fprintf (file
, "\n");
2744 /* Dump SSA update information to stderr. */
2747 debug_update_ssa (void)
2749 dump_update_ssa (stderr
);
2753 /* Initialize data structures used for incremental SSA updates. */
2756 init_update_ssa (struct function
*fn
)
2758 /* Reserve more space than the current number of names. The calls to
2759 add_new_name_mapping are typically done after creating new SSA
2760 names, so we'll need to reallocate these arrays. */
2761 old_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2762 bitmap_clear (old_ssa_names
);
2764 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2765 bitmap_clear (new_ssa_names
);
2767 bitmap_obstack_initialize (&update_ssa_obstack
);
2769 names_to_release
= NULL
;
2770 update_ssa_initialized_fn
= fn
;
2774 /* Deallocate data structures used for incremental SSA updates. */
2777 delete_update_ssa (void)
2782 sbitmap_free (old_ssa_names
);
2783 old_ssa_names
= NULL
;
2785 sbitmap_free (new_ssa_names
);
2786 new_ssa_names
= NULL
;
2788 BITMAP_FREE (symbols_to_rename_set
);
2789 symbols_to_rename_set
= NULL
;
2790 symbols_to_rename
.release ();
2792 if (names_to_release
)
2794 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2795 release_ssa_name (ssa_name (i
));
2796 BITMAP_FREE (names_to_release
);
2799 clear_ssa_name_info ();
2801 fini_ssa_renamer ();
2803 if (blocks_with_phis_to_rewrite
)
2804 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2806 vec
<gphi
*> phis
= phis_to_rewrite
[i
];
2808 phis_to_rewrite
[i
].create (0);
2811 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2812 BITMAP_FREE (blocks_to_update
);
2814 update_ssa_initialized_fn
= NULL
;
2818 /* Create a new name for OLD_NAME in statement STMT and replace the
2819 operand pointed to by DEF_P with the newly created name. If DEF_P
2820 is NULL then STMT should be a GIMPLE assignment.
2821 Return the new name and register the replacement mapping <NEW, OLD> in
2822 update_ssa's tables. */
2825 create_new_def_for (tree old_name
, gimple
*stmt
, def_operand_p def
)
2829 timevar_push (TV_TREE_SSA_INCREMENTAL
);
2831 if (!update_ssa_initialized_fn
)
2832 init_update_ssa (cfun
);
2834 gcc_assert (update_ssa_initialized_fn
== cfun
);
2836 new_name
= duplicate_ssa_name (old_name
, stmt
);
2838 SET_DEF (def
, new_name
);
2840 gimple_assign_set_lhs (stmt
, new_name
);
2842 if (gimple_code (stmt
) == GIMPLE_PHI
)
2844 basic_block bb
= gimple_bb (stmt
);
2846 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2847 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = bb_has_abnormal_pred (bb
);
2850 add_new_name_mapping (new_name
, old_name
);
2852 /* For the benefit of passes that will be updating the SSA form on
2853 their own, set the current reaching definition of OLD_NAME to be
2855 get_ssa_name_ann (old_name
)->info
.current_def
= new_name
;
2857 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
2863 /* Mark virtual operands of FN for renaming by update_ssa. */
2866 mark_virtual_operands_for_renaming (struct function
*fn
)
2868 fn
->gimple_df
->ssa_renaming_needed
= 1;
2869 fn
->gimple_df
->rename_vops
= 1;
2872 /* Replace all uses of NAME by underlying variable and mark it
2873 for renaming. This assumes the defining statement of NAME is
2874 going to be removed. */
2877 mark_virtual_operand_for_renaming (tree name
)
2879 tree name_var
= SSA_NAME_VAR (name
);
2881 imm_use_iterator iter
;
2882 use_operand_p use_p
;
2885 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var
));
2886 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
2888 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2889 SET_USE (use_p
, name_var
);
2893 mark_virtual_operands_for_renaming (cfun
);
2896 /* Replace all uses of the virtual PHI result by its underlying variable
2897 and mark it for renaming. This assumes the PHI node is going to be
2901 mark_virtual_phi_result_for_renaming (gphi
*phi
)
2903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2905 fprintf (dump_file
, "Marking result for renaming : ");
2906 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
2907 fprintf (dump_file
, "\n");
2910 mark_virtual_operand_for_renaming (gimple_phi_result (phi
));
2913 /* Return true if there is any work to be done by update_ssa
2917 need_ssa_update_p (struct function
*fn
)
2919 gcc_assert (fn
!= NULL
);
2920 return (update_ssa_initialized_fn
== fn
2921 || (fn
->gimple_df
&& fn
->gimple_df
->ssa_renaming_needed
));
2924 /* Return true if name N has been registered in the replacement table. */
2927 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
2929 if (!update_ssa_initialized_fn
)
2932 gcc_assert (update_ssa_initialized_fn
== cfun
);
2934 return is_new_name (n
) || is_old_name (n
);
2938 /* Mark NAME to be released after update_ssa has finished. */
2941 release_ssa_name_after_update_ssa (tree name
)
2943 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
2945 if (names_to_release
== NULL
)
2946 names_to_release
= BITMAP_ALLOC (NULL
);
2948 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
2952 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2953 frontier information. BLOCKS is the set of blocks to be updated.
2955 This is slightly different than the regular PHI insertion
2956 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2957 real names (i.e., GIMPLE registers) are inserted:
2959 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2960 nodes inside the region affected by the block that defines VAR
2961 and the blocks that define all its replacements. All these
2962 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2964 First, we compute the entry point to the region (ENTRY). This is
2965 given by the nearest common dominator to all the definition
2966 blocks. When computing the iterated dominance frontier (IDF), any
2967 block not strictly dominated by ENTRY is ignored.
2969 We then call the standard PHI insertion algorithm with the pruned
2972 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2973 names is not pruned. PHI nodes are inserted at every IDF block. */
2976 insert_updated_phi_nodes_for (tree var
, bitmap_head
*dfs
, bitmap blocks
,
2977 unsigned update_flags
)
2981 bitmap idf
, pruned_idf
;
2985 if (TREE_CODE (var
) == SSA_NAME
)
2986 gcc_checking_assert (is_old_name (var
));
2988 gcc_checking_assert (marked_for_renaming (var
));
2990 /* Get all the definition sites for VAR. */
2991 db
= find_def_blocks_for (var
);
2993 /* No need to do anything if there were no definitions to VAR. */
2994 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
2997 /* Compute the initial iterated dominance frontier. */
2998 idf
= compute_idf (db
->def_blocks
, dfs
);
2999 pruned_idf
= BITMAP_ALLOC (NULL
);
3001 if (TREE_CODE (var
) == SSA_NAME
)
3003 if (update_flags
== TODO_update_ssa
)
3005 /* If doing regular SSA updates for GIMPLE registers, we are
3006 only interested in IDF blocks dominated by the nearest
3007 common dominator of all the definition blocks. */
3008 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3010 if (entry
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3011 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
3012 if (BASIC_BLOCK_FOR_FN (cfun
, i
) != entry
3013 && dominated_by_p (CDI_DOMINATORS
,
3014 BASIC_BLOCK_FOR_FN (cfun
, i
), entry
))
3015 bitmap_set_bit (pruned_idf
, i
);
3019 /* Otherwise, do not prune the IDF for VAR. */
3020 gcc_checking_assert (update_flags
== TODO_update_ssa_full_phi
);
3021 bitmap_copy (pruned_idf
, idf
);
3026 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3027 for the first time, so we need to compute the full IDF for
3029 bitmap_copy (pruned_idf
, idf
);
3032 if (!bitmap_empty_p (pruned_idf
))
3034 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3035 are included in the region to be updated. The feeding blocks
3036 are important to guarantee that the PHI arguments are renamed
3039 /* FIXME, this is not needed if we are updating symbols. We are
3040 already starting at the ENTRY block anyway. */
3041 bitmap_ior_into (blocks
, pruned_idf
);
3042 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3046 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3048 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3049 if (e
->src
->index
>= 0)
3050 bitmap_set_bit (blocks
, e
->src
->index
);
3053 insert_phi_nodes_for (var
, pruned_idf
, true);
3056 BITMAP_FREE (pruned_idf
);
3060 /* Sort symbols_to_rename after their DECL_UID. */
3063 insert_updated_phi_nodes_compare_uids (const void *a
, const void *b
)
3065 const_tree syma
= *(const const_tree
*)a
;
3066 const_tree symb
= *(const const_tree
*)b
;
3067 if (DECL_UID (syma
) == DECL_UID (symb
))
3069 return DECL_UID (syma
) < DECL_UID (symb
) ? -1 : 1;
3072 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3073 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3075 1- The names in OLD_SSA_NAMES dominated by the definitions of
3076 NEW_SSA_NAMES are all re-written to be reached by the
3077 appropriate definition from NEW_SSA_NAMES.
3079 2- If needed, new PHI nodes are added to the iterated dominance
3080 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3082 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3083 calling create_new_def_for to create new defs for names that the
3084 caller wants to replace.
3086 The caller cretaes the new names to be inserted and the names that need
3087 to be replaced by calling create_new_def_for for each old definition
3088 to be replaced. Note that the function assumes that the
3089 new defining statement has already been inserted in the IL.
3091 For instance, given the following code:
3094 2 x_1 = PHI (0, x_5)
3105 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3108 2 x_1 = PHI (0, x_5)
3121 We want to replace all the uses of x_1 with the new definitions of
3122 x_10 and x_11. Note that the only uses that should be replaced are
3123 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3124 *not* be replaced (this is why we cannot just mark symbol 'x' for
3127 Additionally, we may need to insert a PHI node at line 11 because
3128 that is a merge point for x_10 and x_11. So the use of x_1 at line
3129 11 will be replaced with the new PHI node. The insertion of PHI
3130 nodes is optional. They are not strictly necessary to preserve the
3131 SSA form, and depending on what the caller inserted, they may not
3132 even be useful for the optimizers. UPDATE_FLAGS controls various
3133 aspects of how update_ssa operates, see the documentation for
3134 TODO_update_ssa*. */
3137 update_ssa (unsigned update_flags
)
3139 basic_block bb
, start_bb
;
3143 sbitmap_iterator sbi
;
3146 /* Only one update flag should be set. */
3147 gcc_assert (update_flags
== TODO_update_ssa
3148 || update_flags
== TODO_update_ssa_no_phi
3149 || update_flags
== TODO_update_ssa_full_phi
3150 || update_flags
== TODO_update_ssa_only_virtuals
);
3152 if (!need_ssa_update_p (cfun
))
3157 timevar_push (TV_TREE_STMT_VERIFY
);
3161 FOR_EACH_BB_FN (bb
, cfun
)
3163 gimple_stmt_iterator gsi
;
3164 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3166 gimple
*stmt
= gsi_stmt (gsi
);
3169 use_operand_p use_p
;
3170 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_ALL_USES
)
3172 tree use
= USE_FROM_PTR (use_p
);
3173 if (TREE_CODE (use
) != SSA_NAME
)
3176 if (SSA_NAME_IN_FREE_LIST (use
))
3178 error ("statement uses released SSA name:");
3179 debug_gimple_stmt (stmt
);
3180 fprintf (stderr
, "The use of ");
3181 print_generic_expr (stderr
, use
, 0);
3182 fprintf (stderr
," should have been replaced\n");
3190 internal_error ("cannot update SSA form");
3192 timevar_pop (TV_TREE_STMT_VERIFY
);
3195 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3198 fprintf (dump_file
, "\nUpdating SSA:\n");
3200 if (!update_ssa_initialized_fn
)
3201 init_update_ssa (cfun
);
3202 else if (update_flags
== TODO_update_ssa_only_virtuals
)
3204 /* If we only need to update virtuals, remove all the mappings for
3205 real names before proceeding. The caller is responsible for
3206 having dealt with the name mappings before calling update_ssa. */
3207 bitmap_clear (old_ssa_names
);
3208 bitmap_clear (new_ssa_names
);
3211 gcc_assert (update_ssa_initialized_fn
== cfun
);
3213 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3214 if (!phis_to_rewrite
.exists ())
3215 phis_to_rewrite
.create (last_basic_block_for_fn (cfun
) + 1);
3216 blocks_to_update
= BITMAP_ALLOC (NULL
);
3218 /* Ensure that the dominance information is up-to-date. */
3219 calculate_dominance_info (CDI_DOMINATORS
);
3221 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3223 /* If there are names defined in the replacement table, prepare
3224 definition and use sites for all the names in NEW_SSA_NAMES and
3226 if (bitmap_first_set_bit (new_ssa_names
) >= 0)
3228 prepare_names_to_update (insert_phi_p
);
3230 /* If all the names in NEW_SSA_NAMES had been marked for
3231 removal, and there are no symbols to rename, then there's
3232 nothing else to do. */
3233 if (bitmap_first_set_bit (new_ssa_names
) < 0
3234 && !cfun
->gimple_df
->ssa_renaming_needed
)
3238 /* Next, determine the block at which to start the renaming process. */
3239 if (cfun
->gimple_df
->ssa_renaming_needed
)
3241 /* If we rename bare symbols initialize the mapping to
3242 auxiliar info we need to keep track of. */
3243 var_infos
= new hash_table
<var_info_hasher
> (47);
3245 /* If we have to rename some symbols from scratch, we need to
3246 start the process at the root of the CFG. FIXME, it should
3247 be possible to determine the nearest block that had a
3248 definition for each of the symbols that are marked for
3249 updating. For now this seems more work than it's worth. */
3250 start_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3252 /* Traverse the CFG looking for existing definitions and uses of
3253 symbols in SSA operands. Mark interesting blocks and
3254 statements and set local live-in information for the PHI
3255 placement heuristics. */
3256 prepare_block_for_update (start_bb
, insert_phi_p
);
3259 for (i
= 1; i
< num_ssa_names
; ++i
)
3261 tree name
= ssa_name (i
);
3263 || virtual_operand_p (name
))
3266 /* For all but virtual operands, which do not have SSA names
3267 with overlapping life ranges, ensure that symbols marked
3268 for renaming do not have existing SSA names associated with
3269 them as we do not re-write them out-of-SSA before going
3270 into SSA for the remaining symbol uses. */
3271 if (marked_for_renaming (SSA_NAME_VAR (name
)))
3273 fprintf (stderr
, "Existing SSA name for symbol marked for "
3275 print_generic_expr (stderr
, name
, TDF_SLIM
);
3276 fprintf (stderr
, "\n");
3277 internal_error ("SSA corruption");
3283 /* Otherwise, the entry block to the region is the nearest
3284 common dominator for the blocks in BLOCKS. */
3285 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3289 /* If requested, insert PHI nodes at the iterated dominance frontier
3290 of every block, creating new definitions for names in OLD_SSA_NAMES
3291 and for symbols found. */
3296 /* If the caller requested PHI nodes to be added, compute
3297 dominance frontiers. */
3298 dfs
= XNEWVEC (bitmap_head
, last_basic_block_for_fn (cfun
));
3299 FOR_EACH_BB_FN (bb
, cfun
)
3300 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
3301 compute_dominance_frontiers (dfs
);
3303 if (bitmap_first_set_bit (old_ssa_names
) >= 0)
3305 sbitmap_iterator sbi
;
3307 /* insert_update_phi_nodes_for will call add_new_name_mapping
3308 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3309 will grow while we are traversing it (but it will not
3310 gain any new members). Copy OLD_SSA_NAMES to a temporary
3312 sbitmap tmp
= sbitmap_alloc (SBITMAP_SIZE (old_ssa_names
));
3313 bitmap_copy (tmp
, old_ssa_names
);
3314 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, sbi
)
3315 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3320 symbols_to_rename
.qsort (insert_updated_phi_nodes_compare_uids
);
3321 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3322 insert_updated_phi_nodes_for (sym
, dfs
, blocks_to_update
,
3325 FOR_EACH_BB_FN (bb
, cfun
)
3326 bitmap_clear (&dfs
[bb
->index
]);
3329 /* Insertion of PHI nodes may have added blocks to the region.
3330 We need to re-compute START_BB to include the newly added
3332 if (start_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3333 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3337 /* Reset the current definition for name and symbol before renaming
3339 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
3340 get_ssa_name_ann (ssa_name (i
))->info
.current_def
= NULL_TREE
;
3342 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3343 get_var_info (sym
)->info
.current_def
= NULL_TREE
;
3345 /* Now start the renaming process at START_BB. */
3346 interesting_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
3347 bitmap_clear (interesting_blocks
);
3348 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3349 bitmap_set_bit (interesting_blocks
, i
);
3351 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3353 sbitmap_free (interesting_blocks
);
3355 /* Debugging dumps. */
3361 dump_update_ssa (dump_file
);
3363 fprintf (dump_file
, "Incremental SSA update started at block: %d\n",
3367 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3369 fprintf (dump_file
, "Number of blocks in CFG: %d\n",
3370 last_basic_block_for_fn (cfun
));
3371 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n",
3372 c
, PERCENT (c
, last_basic_block_for_fn (cfun
)));
3374 if (dump_flags
& TDF_DETAILS
)
3376 fprintf (dump_file
, "Affected blocks:");
3377 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3378 fprintf (dump_file
, " %u", i
);
3379 fprintf (dump_file
, "\n");
3382 fprintf (dump_file
, "\n\n");
3385 /* Free allocated memory. */
3387 delete_update_ssa ();
3389 timevar_pop (TV_TREE_SSA_INCREMENTAL
);