1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "langhooks.h"
29 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
33 #include "gimple-iterator.h"
34 #include "gimple-ssa.h"
36 #include "tree-phinodes.h"
37 #include "ssa-iterators.h"
38 #include "tree-ssanames.h"
39 #include "tree-into-ssa.h"
42 #include "tree-inline.h"
43 #include "hash-table.h"
44 #include "tree-pass.h"
48 #include "diagnostic-core.h"
49 #include "tree-into-ssa.h"
51 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
53 /* This file builds the SSA form for a function as described in:
54 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
55 Computing Static Single Assignment Form and the Control Dependence
56 Graph. ACM Transactions on Programming Languages and Systems,
57 13(4):451-490, October 1991. */
59 /* Structure to map a variable VAR to the set of blocks that contain
60 definitions for VAR. */
63 /* Blocks that contain definitions of VAR. Bit I will be set if the
64 Ith block contains a definition of VAR. */
67 /* Blocks that contain a PHI node for VAR. */
70 /* Blocks where VAR is live-on-entry. Similar semantics as
75 typedef struct def_blocks_d
*def_blocks_p
;
78 /* Stack of trees used to restore the global currdefs to its original
79 state after completing rewriting of a block and its dominator
80 children. Its elements have the following properties:
82 - An SSA_NAME (N) indicates that the current definition of the
83 underlying variable should be set to the given SSA_NAME. If the
84 symbol associated with the SSA_NAME is not a GIMPLE register, the
85 next slot in the stack must be a _DECL node (SYM). In this case,
86 the name N in the previous slot is the current reaching
89 - A _DECL node indicates that the underlying variable has no
92 - A NULL node at the top entry is used to mark the last slot
93 associated with the current block. */
94 static vec
<tree
> block_defs_stack
;
97 /* Set of existing SSA names being replaced by update_ssa. */
98 static sbitmap old_ssa_names
;
100 /* Set of new SSA names being added by update_ssa. Note that both
101 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
102 the operations done on them are presence tests. */
103 static sbitmap new_ssa_names
;
105 static sbitmap interesting_blocks
;
107 /* Set of SSA names that have been marked to be released after they
108 were registered in the replacement table. They will be finally
109 released after we finish updating the SSA web. */
110 static bitmap names_to_release
;
112 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
113 the to basic block with index I. Allocated once per compilation, *not*
114 released between different functions. */
115 static vec
<gimple_vec
> phis_to_rewrite
;
117 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
118 static bitmap blocks_with_phis_to_rewrite
;
120 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
121 to grow as the callers to create_new_def_for will create new names on
123 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
124 need to find a reasonable growth strategy. */
125 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
128 /* The function the SSA updating data structures have been initialized for.
129 NULL if they need to be initialized by create_new_def_for. */
130 static struct function
*update_ssa_initialized_fn
= NULL
;
132 /* Global data to attach to the main dominator walk structure. */
133 struct mark_def_sites_global_data
135 /* This bitmap contains the variables which are set before they
136 are used in a basic block. */
140 /* It is advantageous to avoid things like life analysis for variables which
141 do not need PHI nodes. This enum describes whether or not a particular
142 variable may need a PHI node. */
144 enum need_phi_state
{
145 /* This is the default. If we are still in this state after finding
146 all the definition and use sites, then we will assume the variable
147 needs PHI nodes. This is probably an overly conservative assumption. */
148 NEED_PHI_STATE_UNKNOWN
,
150 /* This state indicates that we have seen one or more sets of the
151 variable in a single basic block and that the sets dominate all
152 uses seen so far. If after finding all definition and use sites
153 we are still in this state, then the variable does not need any
157 /* This state indicates that we have either seen multiple definitions of
158 the variable in multiple blocks, or that we encountered a use in a
159 block that was not dominated by the block containing the set(s) of
160 this variable. This variable is assumed to need PHI nodes. */
164 /* Information stored for both SSA names and decls. */
167 /* This field indicates whether or not the variable may need PHI nodes.
168 See the enum's definition for more detailed information about the
170 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
172 /* The current reaching definition replacing this var. */
175 /* Definitions for this var. */
176 struct def_blocks_d def_blocks
;
179 /* The information associated with decls and SSA names. */
180 typedef struct common_info_d
*common_info_p
;
182 /* Information stored for decls. */
188 /* Information stored for both SSA names and decls. */
189 struct common_info_d info
;
192 /* The information associated with decls. */
193 typedef struct var_info_d
*var_info_p
;
196 /* VAR_INFOS hashtable helpers. */
198 struct var_info_hasher
: typed_free_remove
<var_info_d
>
200 typedef var_info_d value_type
;
201 typedef var_info_d compare_type
;
202 static inline hashval_t
hash (const value_type
*);
203 static inline bool equal (const value_type
*, const compare_type
*);
207 var_info_hasher::hash (const value_type
*p
)
209 return DECL_UID (p
->var
);
213 var_info_hasher::equal (const value_type
*p1
, const compare_type
*p2
)
215 return p1
->var
== p2
->var
;
219 /* Each entry in VAR_INFOS contains an element of type STRUCT
221 static hash_table
<var_info_hasher
> var_infos
;
224 /* Information stored for SSA names. */
227 /* Age of this record (so that info_for_ssa_name table can be cleared
228 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
229 are assumed to be null. */
232 /* Replacement mappings, allocated from update_ssa_obstack. */
235 /* Information stored for both SSA names and decls. */
236 struct common_info_d info
;
239 /* The information associated with names. */
240 typedef struct ssa_name_info
*ssa_name_info_p
;
242 static vec
<ssa_name_info_p
> info_for_ssa_name
;
243 static unsigned current_info_for_ssa_name_age
;
245 static bitmap_obstack update_ssa_obstack
;
247 /* The set of blocks affected by update_ssa. */
248 static bitmap blocks_to_update
;
250 /* The main entry point to the SSA renamer (rewrite_blocks) may be
251 called several times to do different, but related, tasks.
252 Initially, we need it to rename the whole program into SSA form.
253 At other times, we may need it to only rename into SSA newly
254 exposed symbols. Finally, we can also call it to incrementally fix
255 an already built SSA web. */
257 /* Convert the whole function into SSA form. */
260 /* Incrementally update the SSA web by replacing existing SSA
261 names with new ones. See update_ssa for details. */
265 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
266 static bitmap symbols_to_rename_set
;
267 static vec
<tree
> symbols_to_rename
;
269 /* Mark SYM for renaming. */
272 mark_for_renaming (tree sym
)
274 if (!symbols_to_rename_set
)
275 symbols_to_rename_set
= BITMAP_ALLOC (NULL
);
276 if (bitmap_set_bit (symbols_to_rename_set
, DECL_UID (sym
)))
277 symbols_to_rename
.safe_push (sym
);
280 /* Return true if SYM is marked for renaming. */
283 marked_for_renaming (tree sym
)
285 if (!symbols_to_rename_set
|| sym
== NULL_TREE
)
287 return bitmap_bit_p (symbols_to_rename_set
, DECL_UID (sym
));
291 /* Return true if STMT needs to be rewritten. When renaming a subset
292 of the variables, not all statements will be processed. This is
293 decided in mark_def_sites. */
296 rewrite_uses_p (gimple stmt
)
298 return gimple_visited_p (stmt
);
302 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
305 set_rewrite_uses (gimple stmt
, bool rewrite_p
)
307 gimple_set_visited (stmt
, rewrite_p
);
311 /* Return true if the DEFs created by statement STMT should be
312 registered when marking new definition sites. This is slightly
313 different than rewrite_uses_p: it's used by update_ssa to
314 distinguish statements that need to have both uses and defs
315 processed from those that only need to have their defs processed.
316 Statements that define new SSA names only need to have their defs
317 registered, but they don't need to have their uses renamed. */
320 register_defs_p (gimple stmt
)
322 return gimple_plf (stmt
, GF_PLF_1
) != 0;
326 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
329 set_register_defs (gimple stmt
, bool register_defs_p
)
331 gimple_set_plf (stmt
, GF_PLF_1
, register_defs_p
);
335 /* Get the information associated with NAME. */
337 static inline ssa_name_info_p
338 get_ssa_name_ann (tree name
)
340 unsigned ver
= SSA_NAME_VERSION (name
);
341 unsigned len
= info_for_ssa_name
.length ();
342 struct ssa_name_info
*info
;
344 /* Re-allocate the vector at most once per update/into-SSA. */
346 info_for_ssa_name
.safe_grow_cleared (num_ssa_names
);
348 /* But allocate infos lazily. */
349 info
= info_for_ssa_name
[ver
];
352 info
= XCNEW (struct ssa_name_info
);
353 info
->age
= current_info_for_ssa_name_age
;
354 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
355 info_for_ssa_name
[ver
] = info
;
358 if (info
->age
< current_info_for_ssa_name_age
)
360 info
->age
= current_info_for_ssa_name_age
;
361 info
->repl_set
= NULL
;
362 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
363 info
->info
.current_def
= NULL_TREE
;
364 info
->info
.def_blocks
.def_blocks
= NULL
;
365 info
->info
.def_blocks
.phi_blocks
= NULL
;
366 info
->info
.def_blocks
.livein_blocks
= NULL
;
372 /* Return and allocate the auxiliar information for DECL. */
374 static inline var_info_p
375 get_var_info (tree decl
)
377 struct var_info_d vi
;
380 slot
= var_infos
.find_slot_with_hash (&vi
, DECL_UID (decl
), INSERT
);
383 var_info_p v
= XCNEW (struct var_info_d
);
392 /* Clears info for SSA names. */
395 clear_ssa_name_info (void)
397 current_info_for_ssa_name_age
++;
399 /* If current_info_for_ssa_name_age wraps we use stale information.
400 Asser that this does not happen. */
401 gcc_assert (current_info_for_ssa_name_age
!= 0);
405 /* Get access to the auxiliar information stored per SSA name or decl. */
407 static inline common_info_p
408 get_common_info (tree var
)
410 if (TREE_CODE (var
) == SSA_NAME
)
411 return &get_ssa_name_ann (var
)->info
;
413 return &get_var_info (var
)->info
;
417 /* Return the current definition for VAR. */
420 get_current_def (tree var
)
422 return get_common_info (var
)->current_def
;
426 /* Sets current definition of VAR to DEF. */
429 set_current_def (tree var
, tree def
)
431 get_common_info (var
)->current_def
= def
;
434 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
435 all statements in basic block BB. */
438 initialize_flags_in_bb (basic_block bb
)
441 gimple_stmt_iterator gsi
;
443 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
445 gimple phi
= gsi_stmt (gsi
);
446 set_rewrite_uses (phi
, false);
447 set_register_defs (phi
, false);
450 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
452 stmt
= gsi_stmt (gsi
);
454 /* We are going to use the operand cache API, such as
455 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
456 cache for each statement should be up-to-date. */
457 gcc_checking_assert (!gimple_modified_p (stmt
));
458 set_rewrite_uses (stmt
, false);
459 set_register_defs (stmt
, false);
463 /* Mark block BB as interesting for update_ssa. */
466 mark_block_for_update (basic_block bb
)
468 gcc_checking_assert (blocks_to_update
!= NULL
);
469 if (!bitmap_set_bit (blocks_to_update
, bb
->index
))
471 initialize_flags_in_bb (bb
);
474 /* Return the set of blocks where variable VAR is defined and the blocks
475 where VAR is live on entry (livein). If no entry is found in
476 DEF_BLOCKS, a new one is created and returned. */
478 static inline struct def_blocks_d
*
479 get_def_blocks_for (common_info_p info
)
481 struct def_blocks_d
*db_p
= &info
->def_blocks
;
482 if (!db_p
->def_blocks
)
484 db_p
->def_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
485 db_p
->phi_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
486 db_p
->livein_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
493 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
494 VAR is defined by a PHI node. */
497 set_def_block (tree var
, basic_block bb
, bool phi_p
)
499 struct def_blocks_d
*db_p
;
502 info
= get_common_info (var
);
503 db_p
= get_def_blocks_for (info
);
505 /* Set the bit corresponding to the block where VAR is defined. */
506 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
508 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
510 /* Keep track of whether or not we may need to insert PHI nodes.
512 If we are in the UNKNOWN state, then this is the first definition
513 of VAR. Additionally, we have not seen any uses of VAR yet, so
514 we do not need a PHI node for this variable at this time (i.e.,
515 transition to NEED_PHI_STATE_NO).
517 If we are in any other state, then we either have multiple definitions
518 of this variable occurring in different blocks or we saw a use of the
519 variable which was not dominated by the block containing the
520 definition(s). In this case we may need a PHI node, so enter
521 state NEED_PHI_STATE_MAYBE. */
522 if (info
->need_phi_state
== NEED_PHI_STATE_UNKNOWN
)
523 info
->need_phi_state
= NEED_PHI_STATE_NO
;
525 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
529 /* Mark block BB as having VAR live at the entry to BB. */
532 set_livein_block (tree var
, basic_block bb
)
535 struct def_blocks_d
*db_p
;
537 info
= get_common_info (var
);
538 db_p
= get_def_blocks_for (info
);
540 /* Set the bit corresponding to the block where VAR is live in. */
541 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
543 /* Keep track of whether or not we may need to insert PHI nodes.
545 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
546 by the single block containing the definition(s) of this variable. If
547 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
548 NEED_PHI_STATE_MAYBE. */
549 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
551 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
553 if (def_block_index
== -1
554 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
555 BASIC_BLOCK (def_block_index
)))
556 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
559 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
563 /* Return true if NAME is in OLD_SSA_NAMES. */
566 is_old_name (tree name
)
568 unsigned ver
= SSA_NAME_VERSION (name
);
571 return (ver
< SBITMAP_SIZE (new_ssa_names
)
572 && bitmap_bit_p (old_ssa_names
, ver
));
576 /* Return true if NAME is in NEW_SSA_NAMES. */
579 is_new_name (tree name
)
581 unsigned ver
= SSA_NAME_VERSION (name
);
584 return (ver
< SBITMAP_SIZE (new_ssa_names
)
585 && bitmap_bit_p (new_ssa_names
, ver
));
589 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
592 names_replaced_by (tree new_tree
)
594 return get_ssa_name_ann (new_tree
)->repl_set
;
598 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
601 add_to_repl_tbl (tree new_tree
, tree old
)
603 bitmap
*set
= &get_ssa_name_ann (new_tree
)->repl_set
;
605 *set
= BITMAP_ALLOC (&update_ssa_obstack
);
606 bitmap_set_bit (*set
, SSA_NAME_VERSION (old
));
610 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
611 represents the set of names O_1 ... O_j replaced by N_i. This is
612 used by update_ssa and its helpers to introduce new SSA names in an
613 already formed SSA web. */
616 add_new_name_mapping (tree new_tree
, tree old
)
618 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
619 gcc_checking_assert (new_tree
!= old
620 && SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
622 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
623 caller may have created new names since the set was created. */
624 if (SBITMAP_SIZE (new_ssa_names
) <= num_ssa_names
- 1)
626 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
627 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
628 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
631 /* Update the REPL_TBL table. */
632 add_to_repl_tbl (new_tree
, old
);
634 /* If OLD had already been registered as a new name, then all the
635 names that OLD replaces should also be replaced by NEW_TREE. */
636 if (is_new_name (old
))
637 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
639 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
641 bitmap_set_bit (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
642 bitmap_set_bit (old_ssa_names
, SSA_NAME_VERSION (old
));
646 /* Call back for walk_dominator_tree used to collect definition sites
647 for every variable in the function. For every statement S in block
650 1- Variables defined by S in the DEFS of S are marked in the bitmap
653 2- If S uses a variable VAR and there is no preceding kill of VAR,
654 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
656 This information is used to determine which variables are live
657 across block boundaries to reduce the number of PHI nodes
661 mark_def_sites (basic_block bb
, gimple stmt
, bitmap kills
)
667 /* Since this is the first time that we rewrite the program into SSA
668 form, force an operand scan on every statement. */
671 gcc_checking_assert (blocks_to_update
== NULL
);
672 set_register_defs (stmt
, false);
673 set_rewrite_uses (stmt
, false);
675 if (is_gimple_debug (stmt
))
677 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
679 tree sym
= USE_FROM_PTR (use_p
);
680 gcc_checking_assert (DECL_P (sym
));
681 set_rewrite_uses (stmt
, true);
683 if (rewrite_uses_p (stmt
))
684 bitmap_set_bit (interesting_blocks
, bb
->index
);
688 /* If a variable is used before being set, then the variable is live
689 across a block boundary, so mark it live-on-entry to BB. */
690 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
692 tree sym
= USE_FROM_PTR (use_p
);
693 gcc_checking_assert (DECL_P (sym
));
694 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
695 set_livein_block (sym
, bb
);
696 set_rewrite_uses (stmt
, true);
699 /* Now process the defs. Mark BB as the definition block and add
700 each def to the set of killed symbols. */
701 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
703 gcc_checking_assert (DECL_P (def
));
704 set_def_block (def
, bb
, false);
705 bitmap_set_bit (kills
, DECL_UID (def
));
706 set_register_defs (stmt
, true);
709 /* If we found the statement interesting then also mark the block BB
711 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
712 bitmap_set_bit (interesting_blocks
, bb
->index
);
715 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
716 in the dfs numbering of the dominance tree. */
720 /* Basic block whose index this entry corresponds to. */
723 /* The dfs number of this node. */
727 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
731 cmp_dfsnum (const void *a
, const void *b
)
733 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
734 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
736 return (int) da
->dfs_num
- (int) db
->dfs_num
;
739 /* Among the intervals starting at the N points specified in DEFS, find
740 the one that contains S, and return its bb_index. */
743 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
745 unsigned f
= 0, t
= n
, m
;
750 if (defs
[m
].dfs_num
<= s
)
756 return defs
[f
].bb_index
;
759 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
760 KILLS is a bitmap of blocks where the value is defined before any use. */
763 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
767 unsigned i
, b
, p
, u
, top
;
769 basic_block def_bb
, use_bb
;
773 struct dom_dfsnum
*defs
;
774 unsigned n_defs
, adef
;
776 if (bitmap_empty_p (uses
))
782 /* The phi must dominate a use, or an argument of a live phi. Also, we
783 do not create any phi nodes in def blocks, unless they are also livein. */
784 to_remove
= BITMAP_ALLOC (NULL
);
785 bitmap_and_compl (to_remove
, kills
, uses
);
786 bitmap_and_compl_into (phis
, to_remove
);
787 if (bitmap_empty_p (phis
))
789 BITMAP_FREE (to_remove
);
793 /* We want to remove the unnecessary phi nodes, but we do not want to compute
794 liveness information, as that may be linear in the size of CFG, and if
795 there are lot of different variables to rewrite, this may lead to quadratic
798 Instead, we basically emulate standard dce. We put all uses to worklist,
799 then for each of them find the nearest def that dominates them. If this
800 def is a phi node, we mark it live, and if it was not live before, we
801 add the predecessors of its basic block to the worklist.
803 To quickly locate the nearest def that dominates use, we use dfs numbering
804 of the dominance tree (that is already available in order to speed up
805 queries). For each def, we have the interval given by the dfs number on
806 entry to and on exit from the corresponding subtree in the dominance tree.
807 The nearest dominator for a given use is the smallest of these intervals
808 that contains entry and exit dfs numbers for the basic block with the use.
809 If we store the bounds for all the uses to an array and sort it, we can
810 locate the nearest dominating def in logarithmic time by binary search.*/
811 bitmap_ior (to_remove
, kills
, phis
);
812 n_defs
= bitmap_count_bits (to_remove
);
813 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
814 defs
[0].bb_index
= 1;
817 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
819 def_bb
= BASIC_BLOCK (i
);
820 defs
[adef
].bb_index
= i
;
821 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
822 defs
[adef
+ 1].bb_index
= i
;
823 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
826 BITMAP_FREE (to_remove
);
827 gcc_assert (adef
== 2 * n_defs
+ 1);
828 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
829 gcc_assert (defs
[0].bb_index
== 1);
831 /* Now each DEFS entry contains the number of the basic block to that the
832 dfs number corresponds. Change them to the number of basic block that
833 corresponds to the interval following the dfs number. Also, for the
834 dfs_out numbers, increase the dfs number by one (so that it corresponds
835 to the start of the following interval, not to the end of the current
836 one). We use WORKLIST as a stack. */
837 worklist
.create (n_defs
+ 1);
838 worklist
.quick_push (1);
841 for (i
= 1; i
< adef
; i
++)
843 b
= defs
[i
].bb_index
;
846 /* This is a closing element. Interval corresponding to the top
847 of the stack after removing it follows. */
849 top
= worklist
[worklist
.length () - 1];
850 defs
[n_defs
].bb_index
= top
;
851 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
855 /* Opening element. Nothing to do, just push it to the stack and move
856 it to the correct position. */
857 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
858 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
859 worklist
.quick_push (b
);
863 /* If this interval starts at the same point as the previous one, cancel
865 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
866 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
871 gcc_assert (worklist
.is_empty ());
873 /* Now process the uses. */
874 live_phis
= BITMAP_ALLOC (NULL
);
875 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
877 worklist
.safe_push (i
);
880 while (!worklist
.is_empty ())
883 if (b
== ENTRY_BLOCK
)
886 /* If there is a phi node in USE_BB, it is made live. Otherwise,
887 find the def that dominates the immediate dominator of USE_BB
888 (the kill in USE_BB does not dominate the use). */
889 if (bitmap_bit_p (phis
, b
))
893 use_bb
= get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (b
));
894 p
= find_dfsnum_interval (defs
, n_defs
,
895 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
896 if (!bitmap_bit_p (phis
, p
))
900 /* If the phi node is already live, there is nothing to do. */
901 if (!bitmap_set_bit (live_phis
, p
))
904 /* Add the new uses to the worklist. */
905 def_bb
= BASIC_BLOCK (p
);
906 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
909 if (bitmap_bit_p (uses
, u
))
912 /* In case there is a kill directly in the use block, do not record
913 the use (this is also necessary for correctness, as we assume that
914 uses dominated by a def directly in their block have been filtered
916 if (bitmap_bit_p (kills
, u
))
919 bitmap_set_bit (uses
, u
);
920 worklist
.safe_push (u
);
925 bitmap_copy (phis
, live_phis
);
926 BITMAP_FREE (live_phis
);
930 /* Return the set of blocks where variable VAR is defined and the blocks
931 where VAR is live on entry (livein). Return NULL, if no entry is
932 found in DEF_BLOCKS. */
934 static inline struct def_blocks_d
*
935 find_def_blocks_for (tree var
)
937 def_blocks_p p
= &get_common_info (var
)->def_blocks
;
944 /* Marks phi node PHI in basic block BB for rewrite. */
947 mark_phi_for_rewrite (basic_block bb
, gimple phi
)
950 unsigned n
, idx
= bb
->index
;
952 if (rewrite_uses_p (phi
))
955 set_rewrite_uses (phi
, true);
957 if (!blocks_with_phis_to_rewrite
)
960 bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
);
962 n
= (unsigned) last_basic_block
+ 1;
963 if (phis_to_rewrite
.length () < n
)
964 phis_to_rewrite
.safe_grow_cleared (n
);
966 phis
= phis_to_rewrite
[idx
];
969 phis
.safe_push (phi
);
970 phis_to_rewrite
[idx
] = phis
;
973 /* Insert PHI nodes for variable VAR using the iterated dominance
974 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
975 function assumes that the caller is incrementally updating the
976 existing SSA form, in which case VAR may be an SSA name instead of
979 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
980 PHI node for VAR. On exit, only the nodes that received a PHI node
981 for VAR will be present in PHI_INSERTION_POINTS. */
984 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
991 struct def_blocks_d
*def_map
= find_def_blocks_for (var
);
993 /* Remove the blocks where we already have PHI nodes for VAR. */
994 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
996 /* Remove obviously useless phi nodes. */
997 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
998 def_map
->livein_blocks
);
1000 /* And insert the PHI nodes. */
1001 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
1003 bb
= BASIC_BLOCK (bb_index
);
1005 mark_block_for_update (bb
);
1007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1009 fprintf (dump_file
, "creating PHI node in block #%d for ", bb_index
);
1010 print_generic_expr (dump_file
, var
, TDF_SLIM
);
1011 fprintf (dump_file
, "\n");
1015 if (TREE_CODE (var
) == SSA_NAME
)
1017 /* If we are rewriting SSA names, create the LHS of the PHI
1018 node by duplicating VAR. This is useful in the case of
1019 pointers, to also duplicate pointer attributes (alias
1020 information, in particular). */
1024 gcc_checking_assert (update_p
);
1025 new_lhs
= duplicate_ssa_name (var
, NULL
);
1026 phi
= create_phi_node (new_lhs
, bb
);
1027 add_new_name_mapping (new_lhs
, var
);
1029 /* Add VAR to every argument slot of PHI. We need VAR in
1030 every argument so that rewrite_update_phi_arguments knows
1031 which name is this PHI node replacing. If VAR is a
1032 symbol marked for renaming, this is not necessary, the
1033 renamer will use the symbol on the LHS to get its
1034 reaching definition. */
1035 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1036 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1042 gcc_checking_assert (DECL_P (var
));
1043 phi
= create_phi_node (var
, bb
);
1045 tracked_var
= target_for_debug_bind (var
);
1048 gimple note
= gimple_build_debug_bind (tracked_var
,
1051 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1052 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1056 /* Mark this PHI node as interesting for update_ssa. */
1057 set_register_defs (phi
, true);
1058 mark_phi_for_rewrite (bb
, phi
);
1062 /* Sort var_infos after DECL_UID of their var. */
1065 insert_phi_nodes_compare_var_infos (const void *a
, const void *b
)
1067 const struct var_info_d
*defa
= *(struct var_info_d
* const *)a
;
1068 const struct var_info_d
*defb
= *(struct var_info_d
* const *)b
;
1069 if (DECL_UID (defa
->var
) < DECL_UID (defb
->var
))
1075 /* Insert PHI nodes at the dominance frontier of blocks with variable
1076 definitions. DFS contains the dominance frontier information for
1080 insert_phi_nodes (bitmap_head
*dfs
)
1082 hash_table
<var_info_hasher
>::iterator hi
;
1085 vec
<var_info_p
> vars
;
1087 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1089 vars
.create (var_infos
.elements ());
1090 FOR_EACH_HASH_TABLE_ELEMENT (var_infos
, info
, var_info_p
, hi
)
1091 if (info
->info
.need_phi_state
!= NEED_PHI_STATE_NO
)
1092 vars
.quick_push (info
);
1094 /* Do two stages to avoid code generation differences for UID
1095 differences but no UID ordering differences. */
1096 vars
.qsort (insert_phi_nodes_compare_var_infos
);
1098 FOR_EACH_VEC_ELT (vars
, i
, info
)
1100 bitmap idf
= compute_idf (info
->info
.def_blocks
.def_blocks
, dfs
);
1101 insert_phi_nodes_for (info
->var
, idf
, false);
1107 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1111 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1112 register DEF (an SSA_NAME) to be a new definition for SYM. */
1115 register_new_def (tree def
, tree sym
)
1117 common_info_p info
= get_common_info (sym
);
1120 /* If this variable is set in a single basic block and all uses are
1121 dominated by the set(s) in that single basic block, then there is
1122 no reason to record anything for this variable in the block local
1123 definition stacks. Doing so just wastes time and memory.
1125 This is the same test to prune the set of variables which may
1126 need PHI nodes. So we just use that information since it's already
1127 computed and available for us to use. */
1128 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1130 info
->current_def
= def
;
1134 currdef
= info
->current_def
;
1136 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1137 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1138 in the stack so that we know which symbol is being defined by
1139 this SSA name when we unwind the stack. */
1140 if (currdef
&& !is_gimple_reg (sym
))
1141 block_defs_stack
.safe_push (sym
);
1143 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1144 stack is later used by the dominator tree callbacks to restore
1145 the reaching definitions for all the variables defined in the
1146 block after a recursive visit to all its immediately dominated
1147 blocks. If there is no current reaching definition, then just
1148 record the underlying _DECL node. */
1149 block_defs_stack
.safe_push (currdef
? currdef
: sym
);
1151 /* Set the current reaching definition for SYM to be DEF. */
1152 info
->current_def
= def
;
1156 /* Perform a depth-first traversal of the dominator tree looking for
1157 variables to rename. BB is the block where to start searching.
1158 Renaming is a five step process:
1160 1- Every definition made by PHI nodes at the start of the blocks is
1161 registered as the current definition for the corresponding variable.
1163 2- Every statement in BB is rewritten. USE and VUSE operands are
1164 rewritten with their corresponding reaching definition. DEF and
1165 VDEF targets are registered as new definitions.
1167 3- All the PHI nodes in successor blocks of BB are visited. The
1168 argument corresponding to BB is replaced with its current reaching
1171 4- Recursively rewrite every dominator child block of BB.
1173 5- Restore (in reverse order) the current reaching definition for every
1174 new definition introduced in this block. This is done so that when
1175 we return from the recursive call, all the current reaching
1176 definitions are restored to the names that were valid in the
1177 dominator parent of BB. */
1179 /* Return the current definition for variable VAR. If none is found,
1180 create a new SSA name to act as the zeroth definition for VAR. */
1183 get_reaching_def (tree var
)
1185 common_info_p info
= get_common_info (var
);
1188 /* Lookup the current reaching definition for VAR. */
1189 currdef
= info
->current_def
;
1191 /* If there is no reaching definition for VAR, create and register a
1192 default definition for it (if needed). */
1193 if (currdef
== NULL_TREE
)
1195 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1196 currdef
= get_or_create_ssa_default_def (cfun
, sym
);
1199 /* Return the current reaching definition for VAR, or the default
1200 definition, if we had to create one. */
1205 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1208 rewrite_debug_stmt_uses (gimple stmt
)
1210 use_operand_p use_p
;
1212 bool update
= false;
1214 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1216 tree var
= USE_FROM_PTR (use_p
), def
;
1217 common_info_p info
= get_common_info (var
);
1218 gcc_checking_assert (DECL_P (var
));
1219 def
= info
->current_def
;
1222 if (TREE_CODE (var
) == PARM_DECL
&& single_succ_p (ENTRY_BLOCK_PTR
))
1224 gimple_stmt_iterator gsi
1225 = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR
));
1227 /* Search a few source bind stmts at the start of first bb to
1228 see if a DEBUG_EXPR_DECL can't be reused. */
1230 !gsi_end_p (gsi
) && lim
> 0;
1231 gsi_next (&gsi
), lim
--)
1233 gimple gstmt
= gsi_stmt (gsi
);
1234 if (!gimple_debug_source_bind_p (gstmt
))
1236 if (gimple_debug_source_bind_get_value (gstmt
) == var
)
1238 def
= gimple_debug_source_bind_get_var (gstmt
);
1239 if (TREE_CODE (def
) == DEBUG_EXPR_DECL
)
1245 /* If not, add a new source bind stmt. */
1246 if (def
== NULL_TREE
)
1249 def
= make_node (DEBUG_EXPR_DECL
);
1250 def_temp
= gimple_build_debug_source_bind (def
, var
, NULL
);
1251 DECL_ARTIFICIAL (def
) = 1;
1252 TREE_TYPE (def
) = TREE_TYPE (var
);
1253 DECL_MODE (def
) = DECL_MODE (var
);
1254 gsi
= gsi_after_labels (single_succ (ENTRY_BLOCK_PTR
));
1255 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
1262 /* Check if info->current_def can be trusted. */
1263 basic_block bb
= gimple_bb (stmt
);
1265 = SSA_NAME_IS_DEFAULT_DEF (def
)
1266 ? NULL
: gimple_bb (SSA_NAME_DEF_STMT (def
));
1268 /* If definition is in current bb, it is fine. */
1271 /* If definition bb doesn't dominate the current bb,
1272 it can't be used. */
1273 else if (def_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
1275 /* If there is just one definition and dominates the current
1277 else if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1281 struct def_blocks_d
*db_p
= get_def_blocks_for (info
);
1283 /* If there are some non-debug uses in the current bb,
1285 if (bitmap_bit_p (db_p
->livein_blocks
, bb
->index
))
1287 /* Otherwise give up for now. */
1294 gimple_debug_bind_reset_value (stmt
);
1298 SET_USE (use_p
, def
);
1304 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1305 the block with its immediate reaching definitions. Update the current
1306 definition of a variable when a new real or virtual definition is found. */
1309 rewrite_stmt (gimple_stmt_iterator
*si
)
1311 use_operand_p use_p
;
1312 def_operand_p def_p
;
1314 gimple stmt
= gsi_stmt (*si
);
1316 /* If mark_def_sites decided that we don't need to rewrite this
1317 statement, ignore it. */
1318 gcc_assert (blocks_to_update
== NULL
);
1319 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1324 fprintf (dump_file
, "Renaming statement ");
1325 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1326 fprintf (dump_file
, "\n");
1329 /* Step 1. Rewrite USES in the statement. */
1330 if (rewrite_uses_p (stmt
))
1332 if (is_gimple_debug (stmt
))
1333 rewrite_debug_stmt_uses (stmt
);
1335 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1337 tree var
= USE_FROM_PTR (use_p
);
1338 gcc_checking_assert (DECL_P (var
));
1339 SET_USE (use_p
, get_reaching_def (var
));
1343 /* Step 2. Register the statement's DEF operands. */
1344 if (register_defs_p (stmt
))
1345 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1347 tree var
= DEF_FROM_PTR (def_p
);
1351 gcc_checking_assert (DECL_P (var
));
1353 if (gimple_clobber_p (stmt
)
1354 && is_gimple_reg (var
))
1356 /* If we rewrite a DECL into SSA form then drop its
1357 clobber stmts and replace uses with a new default def. */
1358 gcc_checking_assert (TREE_CODE (var
) == VAR_DECL
1359 && !gimple_vdef (stmt
));
1360 gsi_replace (si
, gimple_build_nop (), true);
1361 register_new_def (get_or_create_ssa_default_def (cfun
, var
), var
);
1365 name
= make_ssa_name (var
, stmt
);
1366 SET_DEF (def_p
, name
);
1367 register_new_def (DEF_FROM_PTR (def_p
), var
);
1369 tracked_var
= target_for_debug_bind (var
);
1372 gimple note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1373 gsi_insert_after (si
, note
, GSI_SAME_STMT
);
1379 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1380 PHI nodes. For every PHI node found, add a new argument containing the
1381 current reaching definition for the variable and the edge through which
1382 that definition is reaching the PHI node. */
1385 rewrite_add_phi_arguments (basic_block bb
)
1390 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1393 gimple_stmt_iterator gsi
;
1395 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1401 phi
= gsi_stmt (gsi
);
1402 res
= gimple_phi_result (phi
);
1403 currdef
= get_reaching_def (SSA_NAME_VAR (res
));
1404 /* Virtual operand PHI args do not need a location. */
1405 if (virtual_operand_p (res
))
1406 loc
= UNKNOWN_LOCATION
;
1408 loc
= gimple_location (SSA_NAME_DEF_STMT (currdef
));
1409 add_phi_arg (phi
, currdef
, e
, loc
);
1414 class rewrite_dom_walker
: public dom_walker
1417 rewrite_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1419 virtual void before_dom_children (basic_block
);
1420 virtual void after_dom_children (basic_block
);
1423 /* SSA Rewriting Step 1. Initialization, create a block local stack
1424 of reaching definitions for new SSA names produced in this block
1425 (BLOCK_DEFS). Register new definitions for every PHI node in the
1429 rewrite_dom_walker::before_dom_children (basic_block bb
)
1431 gimple_stmt_iterator gsi
;
1433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1434 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1436 /* Mark the unwind point for this block. */
1437 block_defs_stack
.safe_push (NULL_TREE
);
1439 /* Step 1. Register new definitions for every PHI node in the block.
1440 Conceptually, all the PHI nodes are executed in parallel and each PHI
1441 node introduces a new version for the associated variable. */
1442 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1444 tree result
= gimple_phi_result (gsi_stmt (gsi
));
1445 register_new_def (result
, SSA_NAME_VAR (result
));
1448 /* Step 2. Rewrite every variable used in each statement in the block
1449 with its immediate reaching definitions. Update the current definition
1450 of a variable when a new real or virtual definition is found. */
1451 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
1452 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1453 rewrite_stmt (&gsi
);
1455 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1456 For every PHI node found, add a new argument containing the current
1457 reaching definition for the variable and the edge through which that
1458 definition is reaching the PHI node. */
1459 rewrite_add_phi_arguments (bb
);
1464 /* Called after visiting all the statements in basic block BB and all
1465 of its dominator children. Restore CURRDEFS to its original value. */
1468 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
1470 /* Restore CURRDEFS to its original state. */
1471 while (block_defs_stack
.length () > 0)
1473 tree tmp
= block_defs_stack
.pop ();
1474 tree saved_def
, var
;
1476 if (tmp
== NULL_TREE
)
1479 if (TREE_CODE (tmp
) == SSA_NAME
)
1481 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1482 current definition of its underlying variable. Note that
1483 if the SSA_NAME is not for a GIMPLE register, the symbol
1484 being defined is stored in the next slot in the stack.
1485 This mechanism is needed because an SSA name for a
1486 non-register symbol may be the definition for more than
1487 one symbol (e.g., SFTs, aliased variables, etc). */
1489 var
= SSA_NAME_VAR (saved_def
);
1490 if (!is_gimple_reg (var
))
1491 var
= block_defs_stack
.pop ();
1495 /* If we recorded anything else, it must have been a _DECL
1496 node and its current reaching definition must have been
1502 get_common_info (var
)->current_def
= saved_def
;
1507 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1510 debug_decl_set (bitmap set
)
1512 dump_decl_set (stderr
, set
);
1513 fprintf (stderr
, "\n");
1517 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1518 stack up to a maximum of N levels. If N is -1, the whole stack is
1519 dumped. New levels are created when the dominator tree traversal
1520 used for renaming enters a new sub-tree. */
1523 dump_defs_stack (FILE *file
, int n
)
1527 fprintf (file
, "\n\nRenaming stack");
1529 fprintf (file
, " (up to %d levels)", n
);
1530 fprintf (file
, "\n\n");
1533 fprintf (file
, "Level %d (current level)\n", i
);
1534 for (j
= (int) block_defs_stack
.length () - 1; j
>= 0; j
--)
1538 name
= block_defs_stack
[j
];
1539 if (name
== NULL_TREE
)
1544 fprintf (file
, "\nLevel %d\n", i
);
1555 var
= SSA_NAME_VAR (name
);
1556 if (!is_gimple_reg (var
))
1559 var
= block_defs_stack
[j
];
1563 fprintf (file
, " Previous CURRDEF (");
1564 print_generic_expr (file
, var
, 0);
1565 fprintf (file
, ") = ");
1567 print_generic_expr (file
, name
, 0);
1569 fprintf (file
, "<NIL>");
1570 fprintf (file
, "\n");
1575 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1576 stack up to a maximum of N levels. If N is -1, the whole stack is
1577 dumped. New levels are created when the dominator tree traversal
1578 used for renaming enters a new sub-tree. */
1581 debug_defs_stack (int n
)
1583 dump_defs_stack (stderr
, n
);
1587 /* Dump the current reaching definition of every symbol to FILE. */
1590 dump_currdefs (FILE *file
)
1595 if (symbols_to_rename
.is_empty ())
1598 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1599 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, var
)
1601 common_info_p info
= get_common_info (var
);
1602 fprintf (file
, "CURRDEF (");
1603 print_generic_expr (file
, var
, 0);
1604 fprintf (file
, ") = ");
1605 if (info
->current_def
)
1606 print_generic_expr (file
, info
->current_def
, 0);
1608 fprintf (file
, "<NIL>");
1609 fprintf (file
, "\n");
1614 /* Dump the current reaching definition of every symbol to stderr. */
1617 debug_currdefs (void)
1619 dump_currdefs (stderr
);
1623 /* Dump SSA information to FILE. */
1626 dump_tree_ssa (FILE *file
)
1628 const char *funcname
1629 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1631 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1633 dump_var_infos (file
);
1634 dump_defs_stack (file
, -1);
1635 dump_currdefs (file
);
1636 dump_tree_ssa_stats (file
);
1640 /* Dump SSA information to stderr. */
1643 debug_tree_ssa (void)
1645 dump_tree_ssa (stderr
);
1649 /* Dump statistics for the hash table HTAB. */
1652 htab_statistics (FILE *file
, hash_table
<var_info_hasher
> htab
)
1654 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1655 (long) htab
.size (),
1656 (long) htab
.elements (),
1657 htab
.collisions ());
1661 /* Dump SSA statistics on FILE. */
1664 dump_tree_ssa_stats (FILE *file
)
1666 if (var_infos
.is_created ())
1668 fprintf (file
, "\nHash table statistics:\n");
1669 fprintf (file
, " var_infos: ");
1670 htab_statistics (file
, var_infos
);
1671 fprintf (file
, "\n");
1676 /* Dump SSA statistics on stderr. */
1679 debug_tree_ssa_stats (void)
1681 dump_tree_ssa_stats (stderr
);
1685 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1688 debug_var_infos_r (var_info_d
**slot
, FILE *file
)
1690 struct var_info_d
*info
= *slot
;
1692 fprintf (file
, "VAR: ");
1693 print_generic_expr (file
, info
->var
, dump_flags
);
1694 bitmap_print (file
, info
->info
.def_blocks
.def_blocks
,
1695 ", DEF_BLOCKS: { ", "}");
1696 bitmap_print (file
, info
->info
.def_blocks
.livein_blocks
,
1697 ", LIVEIN_BLOCKS: { ", "}");
1698 bitmap_print (file
, info
->info
.def_blocks
.phi_blocks
,
1699 ", PHI_BLOCKS: { ", "}\n");
1705 /* Dump the VAR_INFOS hash table on FILE. */
1708 dump_var_infos (FILE *file
)
1710 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1711 if (var_infos
.is_created ())
1712 var_infos
.traverse
<FILE *, debug_var_infos_r
> (file
);
1716 /* Dump the VAR_INFOS hash table on stderr. */
1719 debug_var_infos (void)
1721 dump_var_infos (stderr
);
1725 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1728 register_new_update_single (tree new_name
, tree old_name
)
1730 common_info_p info
= get_common_info (old_name
);
1731 tree currdef
= info
->current_def
;
1733 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1734 This stack is later used by the dominator tree callbacks to
1735 restore the reaching definitions for all the variables
1736 defined in the block after a recursive visit to all its
1737 immediately dominated blocks. */
1738 block_defs_stack
.reserve (2);
1739 block_defs_stack
.quick_push (currdef
);
1740 block_defs_stack
.quick_push (old_name
);
1742 /* Set the current reaching definition for OLD_NAME to be
1744 info
->current_def
= new_name
;
1748 /* Register NEW_NAME to be the new reaching definition for all the
1749 names in OLD_NAMES. Used by the incremental SSA update routines to
1750 replace old SSA names with new ones. */
1753 register_new_update_set (tree new_name
, bitmap old_names
)
1758 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1759 register_new_update_single (new_name
, ssa_name (i
));
1764 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1765 it is a symbol marked for renaming, replace it with USE_P's current
1766 reaching definition. */
1769 maybe_replace_use (use_operand_p use_p
)
1771 tree rdef
= NULL_TREE
;
1772 tree use
= USE_FROM_PTR (use_p
);
1773 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1775 if (marked_for_renaming (sym
))
1776 rdef
= get_reaching_def (sym
);
1777 else if (is_old_name (use
))
1778 rdef
= get_reaching_def (use
);
1780 if (rdef
&& rdef
!= use
)
1781 SET_USE (use_p
, rdef
);
1785 /* Same as maybe_replace_use, but without introducing default stmts,
1786 returning false to indicate a need to do so. */
1789 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1791 tree rdef
= NULL_TREE
;
1792 tree use
= USE_FROM_PTR (use_p
);
1793 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1795 if (marked_for_renaming (sym
))
1796 rdef
= get_var_info (sym
)->info
.current_def
;
1797 else if (is_old_name (use
))
1799 rdef
= get_ssa_name_ann (use
)->info
.current_def
;
1800 /* We can't assume that, if there's no current definition, the
1801 default one should be used. It could be the case that we've
1802 rearranged blocks so that the earlier definition no longer
1803 dominates the use. */
1804 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1810 if (rdef
&& rdef
!= use
)
1811 SET_USE (use_p
, rdef
);
1813 return rdef
!= NULL_TREE
;
1817 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1818 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1819 register it as the current definition for the names replaced by
1823 maybe_register_def (def_operand_p def_p
, gimple stmt
,
1824 gimple_stmt_iterator gsi
)
1826 tree def
= DEF_FROM_PTR (def_p
);
1827 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1829 /* If DEF is a naked symbol that needs renaming, create a new
1831 if (marked_for_renaming (sym
))
1837 def
= make_ssa_name (def
, stmt
);
1838 SET_DEF (def_p
, def
);
1840 tracked_var
= target_for_debug_bind (sym
);
1843 gimple note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1844 /* If stmt ends the bb, insert the debug stmt on the single
1845 non-EH edge from the stmt. */
1846 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1848 basic_block bb
= gsi_bb (gsi
);
1851 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1852 if (!(e
->flags
& EDGE_EH
))
1854 gcc_checking_assert (!ef
);
1857 /* If there are other predecessors to ef->dest, then
1858 there must be PHI nodes for the modified
1859 variable, and therefore there will be debug bind
1860 stmts after the PHI nodes. The debug bind notes
1861 we'd insert would force the creation of a new
1862 block (diverging codegen) and be redundant with
1863 the post-PHI bind stmts, so don't add them.
1865 As for the exit edge, there wouldn't be redundant
1866 bind stmts, but there wouldn't be a PC to bind
1867 them to either, so avoid diverging the CFG. */
1868 if (ef
&& single_pred_p (ef
->dest
)
1869 && ef
->dest
!= EXIT_BLOCK_PTR
)
1871 /* If there were PHI nodes in the node, we'd
1872 have to make sure the value we're binding
1873 doesn't need rewriting. But there shouldn't
1874 be PHI nodes in a single-predecessor block,
1875 so we just add the note. */
1876 gsi_insert_on_edge_immediate (ef
, note
);
1880 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1884 register_new_update_single (def
, sym
);
1888 /* If DEF is a new name, register it as a new definition
1889 for all the names replaced by DEF. */
1890 if (is_new_name (def
))
1891 register_new_update_set (def
, names_replaced_by (def
));
1893 /* If DEF is an old name, register DEF as a new
1894 definition for itself. */
1895 if (is_old_name (def
))
1896 register_new_update_single (def
, def
);
1901 /* Update every variable used in the statement pointed-to by SI. The
1902 statement is assumed to be in SSA form already. Names in
1903 OLD_SSA_NAMES used by SI will be updated to their current reaching
1904 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1905 will be registered as a new definition for their corresponding name
1906 in OLD_SSA_NAMES. */
1909 rewrite_update_stmt (gimple stmt
, gimple_stmt_iterator gsi
)
1911 use_operand_p use_p
;
1912 def_operand_p def_p
;
1915 /* Only update marked statements. */
1916 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1921 fprintf (dump_file
, "Updating SSA information for statement ");
1922 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1925 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1926 symbol is marked for renaming. */
1927 if (rewrite_uses_p (stmt
))
1929 if (is_gimple_debug (stmt
))
1931 bool failed
= false;
1933 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1934 if (!maybe_replace_use_in_debug_stmt (use_p
))
1942 /* DOM sometimes threads jumps in such a way that a
1943 debug stmt ends up referencing a SSA variable that no
1944 longer dominates the debug stmt, but such that all
1945 incoming definitions refer to the same definition in
1946 an earlier dominator. We could try to recover that
1947 definition somehow, but this will have to do for now.
1949 Introducing a default definition, which is what
1950 maybe_replace_use() would do in such cases, may
1951 modify code generation, for the otherwise-unused
1952 default definition would never go away, modifying SSA
1953 version numbers all over. */
1954 gimple_debug_bind_reset_value (stmt
);
1960 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1961 maybe_replace_use (use_p
);
1965 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1966 Also register definitions for names whose underlying symbol is
1967 marked for renaming. */
1968 if (register_defs_p (stmt
))
1969 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1970 maybe_register_def (def_p
, stmt
, gsi
);
1974 /* Visit all the successor blocks of BB looking for PHI nodes. For
1975 every PHI node found, check if any of its arguments is in
1976 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1977 definition, replace it. */
1980 rewrite_update_phi_arguments (basic_block bb
)
1986 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1991 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
1994 phis
= phis_to_rewrite
[e
->dest
->index
];
1995 FOR_EACH_VEC_ELT (phis
, i
, phi
)
1997 tree arg
, lhs_sym
, reaching_def
= NULL
;
1998 use_operand_p arg_p
;
2000 gcc_checking_assert (rewrite_uses_p (phi
));
2002 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
2003 arg
= USE_FROM_PTR (arg_p
);
2005 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
2008 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2010 if (arg
== NULL_TREE
)
2012 /* When updating a PHI node for a recently introduced
2013 symbol we may find NULL arguments. That's why we
2014 take the symbol from the LHS of the PHI node. */
2015 reaching_def
= get_reaching_def (lhs_sym
);
2020 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2022 if (marked_for_renaming (sym
))
2023 reaching_def
= get_reaching_def (sym
);
2024 else if (is_old_name (arg
))
2025 reaching_def
= get_reaching_def (arg
);
2028 /* Update the argument if there is a reaching def. */
2031 source_location locus
;
2032 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2034 SET_USE (arg_p
, reaching_def
);
2036 /* Virtual operands do not need a location. */
2037 if (virtual_operand_p (reaching_def
))
2038 locus
= UNKNOWN_LOCATION
;
2041 gimple stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2043 /* Single element PHI nodes behave like copies, so get the
2044 location from the phi argument. */
2045 if (gimple_code (stmt
) == GIMPLE_PHI
2046 && gimple_phi_num_args (stmt
) == 1)
2047 locus
= gimple_phi_arg_location (stmt
, 0);
2049 locus
= gimple_location (stmt
);
2052 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2056 if (e
->flags
& EDGE_ABNORMAL
)
2057 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2062 class rewrite_update_dom_walker
: public dom_walker
2065 rewrite_update_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2067 virtual void before_dom_children (basic_block
);
2068 virtual void after_dom_children (basic_block
);
2071 /* Initialization of block data structures for the incremental SSA
2072 update pass. Create a block local stack of reaching definitions
2073 for new SSA names produced in this block (BLOCK_DEFS). Register
2074 new definitions for every PHI node in the block. */
2077 rewrite_update_dom_walker::before_dom_children (basic_block bb
)
2079 bool is_abnormal_phi
;
2080 gimple_stmt_iterator gsi
;
2082 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2083 fprintf (dump_file
, "Registering new PHI nodes in block #%d\n",
2086 /* Mark the unwind point for this block. */
2087 block_defs_stack
.safe_push (NULL_TREE
);
2089 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2092 /* Mark the LHS if any of the arguments flows through an abnormal
2094 is_abnormal_phi
= bb_has_abnormal_pred (bb
);
2096 /* If any of the PHI nodes is a replacement for a name in
2097 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2098 register it as a new definition for its corresponding name. Also
2099 register definitions for names whose underlying symbols are
2100 marked for renaming. */
2101 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2104 gimple phi
= gsi_stmt (gsi
);
2106 if (!register_defs_p (phi
))
2109 lhs
= gimple_phi_result (phi
);
2110 lhs_sym
= SSA_NAME_VAR (lhs
);
2112 if (marked_for_renaming (lhs_sym
))
2113 register_new_update_single (lhs
, lhs_sym
);
2117 /* If LHS is a new name, register a new definition for all
2118 the names replaced by LHS. */
2119 if (is_new_name (lhs
))
2120 register_new_update_set (lhs
, names_replaced_by (lhs
));
2122 /* If LHS is an OLD name, register it as a new definition
2124 if (is_old_name (lhs
))
2125 register_new_update_single (lhs
, lhs
);
2128 if (is_abnormal_phi
)
2129 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2132 /* Step 2. Rewrite every variable used in each statement in the block. */
2133 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
2135 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2136 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2137 rewrite_update_stmt (gsi_stmt (gsi
), gsi
);
2140 /* Step 3. Update PHI nodes. */
2141 rewrite_update_phi_arguments (bb
);
2144 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2145 the current reaching definition of every name re-written in BB to
2146 the original reaching definition before visiting BB. This
2147 unwinding must be done in the opposite order to what is done in
2148 register_new_update_set. */
2151 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
2153 while (block_defs_stack
.length () > 0)
2155 tree var
= block_defs_stack
.pop ();
2158 /* NULL indicates the unwind stop point for this block (see
2159 rewrite_update_enter_block). */
2163 saved_def
= block_defs_stack
.pop ();
2164 get_common_info (var
)->current_def
= saved_def
;
2169 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2172 ENTRY indicates the block where to start. Every block dominated by
2173 ENTRY will be rewritten.
2175 WHAT indicates what actions will be taken by the renamer (see enum
2178 BLOCKS are the set of interesting blocks for the dominator walker
2179 to process. If this set is NULL, then all the nodes dominated
2180 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2181 are not present in BLOCKS are ignored. */
2184 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2186 /* Rewrite all the basic blocks in the program. */
2187 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2189 block_defs_stack
.create (10);
2191 /* Recursively walk the dominator tree rewriting each statement in
2192 each basic block. */
2193 if (what
== REWRITE_ALL
)
2194 rewrite_dom_walker (CDI_DOMINATORS
).walk (entry
);
2195 else if (what
== REWRITE_UPDATE
)
2196 rewrite_update_dom_walker (CDI_DOMINATORS
).walk (entry
);
2200 /* Debugging dumps. */
2201 if (dump_file
&& (dump_flags
& TDF_STATS
))
2203 dump_dfa_stats (dump_file
);
2204 if (var_infos
.is_created ())
2205 dump_tree_ssa_stats (dump_file
);
2208 block_defs_stack
.release ();
2210 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2213 class mark_def_dom_walker
: public dom_walker
2216 mark_def_dom_walker (cdi_direction direction
);
2217 ~mark_def_dom_walker ();
2219 virtual void before_dom_children (basic_block
);
2222 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2223 large enough to accommodate all the variables referenced in the
2224 function, not just the ones we are renaming. */
2228 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction
)
2229 : dom_walker (direction
), m_kills (BITMAP_ALLOC (NULL
))
2233 mark_def_dom_walker::~mark_def_dom_walker ()
2235 BITMAP_FREE (m_kills
);
2238 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2239 at the start of each block, and call mark_def_sites for each statement. */
2242 mark_def_dom_walker::before_dom_children (basic_block bb
)
2244 gimple_stmt_iterator gsi
;
2246 bitmap_clear (m_kills
);
2247 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2248 mark_def_sites (bb
, gsi_stmt (gsi
), m_kills
);
2251 /* Initialize internal data needed during renaming. */
2254 init_ssa_renamer (void)
2256 cfun
->gimple_df
->in_ssa_p
= false;
2258 /* Allocate memory for the DEF_BLOCKS hash table. */
2259 gcc_assert (!var_infos
.is_created ());
2260 var_infos
.create (vec_safe_length (cfun
->local_decls
));
2262 bitmap_obstack_initialize (&update_ssa_obstack
);
2266 /* Deallocate internal data structures used by the renamer. */
2269 fini_ssa_renamer (void)
2271 if (var_infos
.is_created ())
2272 var_infos
.dispose ();
2274 bitmap_obstack_release (&update_ssa_obstack
);
2276 cfun
->gimple_df
->ssa_renaming_needed
= 0;
2277 cfun
->gimple_df
->rename_vops
= 0;
2278 cfun
->gimple_df
->in_ssa_p
= true;
2281 /* Main entry point into the SSA builder. The renaming process
2282 proceeds in four main phases:
2284 1- Compute dominance frontier and immediate dominators, needed to
2285 insert PHI nodes and rename the function in dominator tree
2288 2- Find and mark all the blocks that define variables.
2290 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2292 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2294 Steps 3 and 4 are done using the dominator tree walker
2295 (walk_dominator_tree). */
2298 rewrite_into_ssa (void)
2304 /* Initialize operand data structures. */
2305 init_ssa_operands (cfun
);
2307 /* Initialize internal data needed by the renamer. */
2308 init_ssa_renamer ();
2310 /* Initialize the set of interesting blocks. The callback
2311 mark_def_sites will add to this set those blocks that the renamer
2313 interesting_blocks
= sbitmap_alloc (last_basic_block
);
2314 bitmap_clear (interesting_blocks
);
2316 /* Initialize dominance frontier. */
2317 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
2319 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
2321 /* 1- Compute dominance frontiers. */
2322 calculate_dominance_info (CDI_DOMINATORS
);
2323 compute_dominance_frontiers (dfs
);
2325 /* 2- Find and mark definition sites. */
2326 mark_def_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
2328 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2329 insert_phi_nodes (dfs
);
2331 /* 4- Rename all the blocks. */
2332 rewrite_blocks (ENTRY_BLOCK_PTR
, REWRITE_ALL
);
2334 /* Free allocated memory. */
2336 bitmap_clear (&dfs
[bb
->index
]);
2339 sbitmap_free (interesting_blocks
);
2341 fini_ssa_renamer ();
2343 /* Try to get rid of all gimplifier generated temporaries by making
2344 its SSA names anonymous. This way we can garbage collect them
2345 all after removing unused locals which we do in our TODO. */
2346 for (i
= 1; i
< num_ssa_names
; ++i
)
2348 tree decl
, name
= ssa_name (i
);
2350 || SSA_NAME_IS_DEFAULT_DEF (name
))
2352 decl
= SSA_NAME_VAR (name
);
2354 && TREE_CODE (decl
) == VAR_DECL
2355 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl
)
2356 && DECL_IGNORED_P (decl
))
2357 SET_SSA_NAME_VAR_OR_IDENTIFIER (name
, DECL_NAME (decl
));
2363 /* Gate for IPCP optimization. */
2366 gate_into_ssa (void)
2368 /* Do nothing for funcions that was produced already in SSA form. */
2369 return !(cfun
->curr_properties
& PROP_ssa
);
2374 const pass_data pass_data_build_ssa
=
2376 GIMPLE_PASS
, /* type */
2378 OPTGROUP_NONE
, /* optinfo_flags */
2379 true, /* has_gate */
2380 true, /* has_execute */
2381 TV_TREE_SSA_OTHER
, /* tv_id */
2382 PROP_cfg
, /* properties_required */
2383 PROP_ssa
, /* properties_provided */
2384 0, /* properties_destroyed */
2385 0, /* todo_flags_start */
2386 ( TODO_verify_ssa
| TODO_remove_unused_locals
), /* todo_flags_finish */
2389 class pass_build_ssa
: public gimple_opt_pass
2392 pass_build_ssa (gcc::context
*ctxt
)
2393 : gimple_opt_pass (pass_data_build_ssa
, ctxt
)
2396 /* opt_pass methods: */
2397 bool gate () { return gate_into_ssa (); }
2398 unsigned int execute () { return rewrite_into_ssa (); }
2400 }; // class pass_build_ssa
2405 make_pass_build_ssa (gcc::context
*ctxt
)
2407 return new pass_build_ssa (ctxt
);
2411 /* Mark the definition of VAR at STMT and BB as interesting for the
2412 renamer. BLOCKS is the set of blocks that need updating. */
2415 mark_def_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2417 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2418 set_register_defs (stmt
, true);
2422 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2424 set_def_block (var
, bb
, is_phi_p
);
2426 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2427 site for both itself and all the old names replaced by it. */
2428 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2432 bitmap set
= names_replaced_by (var
);
2434 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2435 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2441 /* Mark the use of VAR at STMT and BB as interesting for the
2442 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2446 mark_use_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2448 basic_block def_bb
= gimple_bb (stmt
);
2450 mark_block_for_update (def_bb
);
2451 mark_block_for_update (bb
);
2453 if (gimple_code (stmt
) == GIMPLE_PHI
)
2454 mark_phi_for_rewrite (def_bb
, stmt
);
2457 set_rewrite_uses (stmt
, true);
2459 if (is_gimple_debug (stmt
))
2463 /* If VAR has not been defined in BB, then it is live-on-entry
2464 to BB. Note that we cannot just use the block holding VAR's
2465 definition because if VAR is one of the names in OLD_SSA_NAMES,
2466 it will have several definitions (itself and all the names that
2470 struct def_blocks_d
*db_p
= get_def_blocks_for (get_common_info (var
));
2471 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2472 set_livein_block (var
, bb
);
2477 /* Do a dominator walk starting at BB processing statements that
2478 reference symbols in SSA operands. This is very similar to
2479 mark_def_sites, but the scan handles statements whose operands may
2480 already be SSA names.
2482 If INSERT_PHI_P is true, mark those uses as live in the
2483 corresponding block. This is later used by the PHI placement
2484 algorithm to make PHI pruning decisions.
2486 FIXME. Most of this would be unnecessary if we could associate a
2487 symbol to all the SSA names that reference it. But that
2488 sounds like it would be expensive to maintain. Still, it
2489 would be interesting to see if it makes better sense to do
2493 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2496 gimple_stmt_iterator si
;
2500 mark_block_for_update (bb
);
2502 /* Process PHI nodes marking interesting those that define or use
2503 the symbols that we are interested in. */
2504 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
2506 gimple phi
= gsi_stmt (si
);
2507 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2509 if (TREE_CODE (lhs
) == SSA_NAME
2510 && (! virtual_operand_p (lhs
)
2511 || ! cfun
->gimple_df
->rename_vops
))
2514 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2515 mark_for_renaming (lhs_sym
);
2516 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2518 /* Mark the uses in phi nodes as interesting. It would be more correct
2519 to process the arguments of the phi nodes of the successor edges of
2520 BB at the end of prepare_block_for_update, however, that turns out
2521 to be significantly more expensive. Doing it here is conservatively
2522 correct -- it may only cause us to believe a value to be live in a
2523 block that also contains its definition, and thus insert a few more
2524 phi nodes for it. */
2525 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2526 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2529 /* Process the statements. */
2530 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2534 use_operand_p use_p
;
2535 def_operand_p def_p
;
2537 stmt
= gsi_stmt (si
);
2539 if (cfun
->gimple_df
->rename_vops
2540 && gimple_vuse (stmt
))
2542 tree use
= gimple_vuse (stmt
);
2543 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2544 mark_for_renaming (sym
);
2545 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2548 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_USE
)
2550 tree use
= USE_FROM_PTR (use_p
);
2553 mark_for_renaming (use
);
2554 mark_use_interesting (use
, stmt
, bb
, insert_phi_p
);
2557 if (cfun
->gimple_df
->rename_vops
2558 && gimple_vdef (stmt
))
2560 tree def
= gimple_vdef (stmt
);
2561 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2562 mark_for_renaming (sym
);
2563 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2566 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_DEF
)
2568 tree def
= DEF_FROM_PTR (def_p
);
2571 mark_for_renaming (def
);
2572 mark_def_interesting (def
, stmt
, bb
, insert_phi_p
);
2576 /* Now visit all the blocks dominated by BB. */
2577 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2579 son
= next_dom_son (CDI_DOMINATORS
, son
))
2580 prepare_block_for_update (son
, insert_phi_p
);
2584 /* Helper for prepare_names_to_update. Mark all the use sites for
2585 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2586 prepare_names_to_update. */
2589 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2591 use_operand_p use_p
;
2592 imm_use_iterator iter
;
2594 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2596 gimple stmt
= USE_STMT (use_p
);
2597 basic_block bb
= gimple_bb (stmt
);
2599 if (gimple_code (stmt
) == GIMPLE_PHI
)
2601 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2602 edge e
= gimple_phi_arg_edge (stmt
, ix
);
2603 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2607 /* For regular statements, mark this as an interesting use
2609 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2615 /* Helper for prepare_names_to_update. Mark the definition site for
2616 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2617 prepare_names_to_update. */
2620 prepare_def_site_for (tree name
, bool insert_phi_p
)
2625 gcc_checking_assert (names_to_release
== NULL
2626 || !bitmap_bit_p (names_to_release
,
2627 SSA_NAME_VERSION (name
)));
2629 stmt
= SSA_NAME_DEF_STMT (name
);
2630 bb
= gimple_bb (stmt
);
2633 gcc_checking_assert (bb
->index
< last_basic_block
);
2634 mark_block_for_update (bb
);
2635 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2640 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2641 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2642 PHI nodes for newly created names. */
2645 prepare_names_to_update (bool insert_phi_p
)
2649 sbitmap_iterator sbi
;
2651 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2652 remove it from NEW_SSA_NAMES so that we don't try to visit its
2653 defining basic block (which most likely doesn't exist). Notice
2654 that we cannot do the same with names in OLD_SSA_NAMES because we
2655 want to replace existing instances. */
2656 if (names_to_release
)
2657 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2658 bitmap_clear_bit (new_ssa_names
, i
);
2660 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2661 names may be considered to be live-in on blocks that contain
2662 definitions for their replacements. */
2663 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2664 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2666 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2667 OLD_SSA_NAMES, but we have to ignore its definition site. */
2668 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
2670 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2671 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2672 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2677 /* Dump all the names replaced by NAME to FILE. */
2680 dump_names_replaced_by (FILE *file
, tree name
)
2686 print_generic_expr (file
, name
, 0);
2687 fprintf (file
, " -> { ");
2689 old_set
= names_replaced_by (name
);
2690 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2692 print_generic_expr (file
, ssa_name (i
), 0);
2693 fprintf (file
, " ");
2696 fprintf (file
, "}\n");
2700 /* Dump all the names replaced by NAME to stderr. */
2703 debug_names_replaced_by (tree name
)
2705 dump_names_replaced_by (stderr
, name
);
2709 /* Dump SSA update information to FILE. */
2712 dump_update_ssa (FILE *file
)
2717 if (!need_ssa_update_p (cfun
))
2720 if (new_ssa_names
&& bitmap_first_set_bit (new_ssa_names
) >= 0)
2722 sbitmap_iterator sbi
;
2724 fprintf (file
, "\nSSA replacement table\n");
2725 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2726 "O_1, ..., O_j\n\n");
2728 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2729 dump_names_replaced_by (file
, ssa_name (i
));
2732 if (symbols_to_rename_set
&& !bitmap_empty_p (symbols_to_rename_set
))
2734 fprintf (file
, "\nSymbols to be put in SSA form\n");
2735 dump_decl_set (file
, symbols_to_rename_set
);
2736 fprintf (file
, "\n");
2739 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2741 fprintf (file
, "\nSSA names to release after updating the SSA web\n\n");
2742 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2744 print_generic_expr (file
, ssa_name (i
), 0);
2745 fprintf (file
, " ");
2747 fprintf (file
, "\n");
2752 /* Dump SSA update information to stderr. */
2755 debug_update_ssa (void)
2757 dump_update_ssa (stderr
);
2761 /* Initialize data structures used for incremental SSA updates. */
2764 init_update_ssa (struct function
*fn
)
2766 /* Reserve more space than the current number of names. The calls to
2767 add_new_name_mapping are typically done after creating new SSA
2768 names, so we'll need to reallocate these arrays. */
2769 old_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2770 bitmap_clear (old_ssa_names
);
2772 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2773 bitmap_clear (new_ssa_names
);
2775 bitmap_obstack_initialize (&update_ssa_obstack
);
2777 names_to_release
= NULL
;
2778 update_ssa_initialized_fn
= fn
;
2782 /* Deallocate data structures used for incremental SSA updates. */
2785 delete_update_ssa (void)
2790 sbitmap_free (old_ssa_names
);
2791 old_ssa_names
= NULL
;
2793 sbitmap_free (new_ssa_names
);
2794 new_ssa_names
= NULL
;
2796 BITMAP_FREE (symbols_to_rename_set
);
2797 symbols_to_rename_set
= NULL
;
2798 symbols_to_rename
.release ();
2800 if (names_to_release
)
2802 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2803 release_ssa_name (ssa_name (i
));
2804 BITMAP_FREE (names_to_release
);
2807 clear_ssa_name_info ();
2809 fini_ssa_renamer ();
2811 if (blocks_with_phis_to_rewrite
)
2812 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2814 gimple_vec phis
= phis_to_rewrite
[i
];
2816 phis_to_rewrite
[i
].create (0);
2819 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2820 BITMAP_FREE (blocks_to_update
);
2822 update_ssa_initialized_fn
= NULL
;
2826 /* Create a new name for OLD_NAME in statement STMT and replace the
2827 operand pointed to by DEF_P with the newly created name. If DEF_P
2828 is NULL then STMT should be a GIMPLE assignment.
2829 Return the new name and register the replacement mapping <NEW, OLD> in
2830 update_ssa's tables. */
2833 create_new_def_for (tree old_name
, gimple stmt
, def_operand_p def
)
2837 timevar_push (TV_TREE_SSA_INCREMENTAL
);
2839 if (!update_ssa_initialized_fn
)
2840 init_update_ssa (cfun
);
2842 gcc_assert (update_ssa_initialized_fn
== cfun
);
2844 new_name
= duplicate_ssa_name (old_name
, stmt
);
2846 SET_DEF (def
, new_name
);
2848 gimple_assign_set_lhs (stmt
, new_name
);
2850 if (gimple_code (stmt
) == GIMPLE_PHI
)
2852 basic_block bb
= gimple_bb (stmt
);
2854 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2855 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = bb_has_abnormal_pred (bb
);
2858 add_new_name_mapping (new_name
, old_name
);
2860 /* For the benefit of passes that will be updating the SSA form on
2861 their own, set the current reaching definition of OLD_NAME to be
2863 get_ssa_name_ann (old_name
)->info
.current_def
= new_name
;
2865 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
2871 /* Mark virtual operands of FN for renaming by update_ssa. */
2874 mark_virtual_operands_for_renaming (struct function
*fn
)
2876 fn
->gimple_df
->ssa_renaming_needed
= 1;
2877 fn
->gimple_df
->rename_vops
= 1;
2880 /* Replace all uses of NAME by underlying variable and mark it
2881 for renaming. This assumes the defining statement of NAME is
2882 going to be removed. */
2885 mark_virtual_operand_for_renaming (tree name
)
2887 tree name_var
= SSA_NAME_VAR (name
);
2889 imm_use_iterator iter
;
2890 use_operand_p use_p
;
2893 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var
));
2894 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
2896 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2897 SET_USE (use_p
, name_var
);
2901 mark_virtual_operands_for_renaming (cfun
);
2904 /* Replace all uses of the virtual PHI result by its underlying variable
2905 and mark it for renaming. This assumes the PHI node is going to be
2909 mark_virtual_phi_result_for_renaming (gimple phi
)
2911 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2913 fprintf (dump_file
, "Marking result for renaming : ");
2914 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
2915 fprintf (dump_file
, "\n");
2918 mark_virtual_operand_for_renaming (gimple_phi_result (phi
));
2921 /* Return true if there is any work to be done by update_ssa
2925 need_ssa_update_p (struct function
*fn
)
2927 gcc_assert (fn
!= NULL
);
2928 return (update_ssa_initialized_fn
== fn
2929 || (fn
->gimple_df
&& fn
->gimple_df
->ssa_renaming_needed
));
2932 /* Return true if name N has been registered in the replacement table. */
2935 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
2937 if (!update_ssa_initialized_fn
)
2940 gcc_assert (update_ssa_initialized_fn
== cfun
);
2942 return is_new_name (n
) || is_old_name (n
);
2946 /* Mark NAME to be released after update_ssa has finished. */
2949 release_ssa_name_after_update_ssa (tree name
)
2951 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
2953 if (names_to_release
== NULL
)
2954 names_to_release
= BITMAP_ALLOC (NULL
);
2956 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
2960 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2961 frontier information. BLOCKS is the set of blocks to be updated.
2963 This is slightly different than the regular PHI insertion
2964 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2965 real names (i.e., GIMPLE registers) are inserted:
2967 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2968 nodes inside the region affected by the block that defines VAR
2969 and the blocks that define all its replacements. All these
2970 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2972 First, we compute the entry point to the region (ENTRY). This is
2973 given by the nearest common dominator to all the definition
2974 blocks. When computing the iterated dominance frontier (IDF), any
2975 block not strictly dominated by ENTRY is ignored.
2977 We then call the standard PHI insertion algorithm with the pruned
2980 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2981 names is not pruned. PHI nodes are inserted at every IDF block. */
2984 insert_updated_phi_nodes_for (tree var
, bitmap_head
*dfs
, bitmap blocks
,
2985 unsigned update_flags
)
2988 struct def_blocks_d
*db
;
2989 bitmap idf
, pruned_idf
;
2993 if (TREE_CODE (var
) == SSA_NAME
)
2994 gcc_checking_assert (is_old_name (var
));
2996 gcc_checking_assert (marked_for_renaming (var
));
2998 /* Get all the definition sites for VAR. */
2999 db
= find_def_blocks_for (var
);
3001 /* No need to do anything if there were no definitions to VAR. */
3002 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
3005 /* Compute the initial iterated dominance frontier. */
3006 idf
= compute_idf (db
->def_blocks
, dfs
);
3007 pruned_idf
= BITMAP_ALLOC (NULL
);
3009 if (TREE_CODE (var
) == SSA_NAME
)
3011 if (update_flags
== TODO_update_ssa
)
3013 /* If doing regular SSA updates for GIMPLE registers, we are
3014 only interested in IDF blocks dominated by the nearest
3015 common dominator of all the definition blocks. */
3016 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3018 if (entry
!= ENTRY_BLOCK_PTR
)
3019 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
3020 if (BASIC_BLOCK (i
) != entry
3021 && dominated_by_p (CDI_DOMINATORS
, BASIC_BLOCK (i
), entry
))
3022 bitmap_set_bit (pruned_idf
, i
);
3026 /* Otherwise, do not prune the IDF for VAR. */
3027 gcc_checking_assert (update_flags
== TODO_update_ssa_full_phi
);
3028 bitmap_copy (pruned_idf
, idf
);
3033 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3034 for the first time, so we need to compute the full IDF for
3036 bitmap_copy (pruned_idf
, idf
);
3039 if (!bitmap_empty_p (pruned_idf
))
3041 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3042 are included in the region to be updated. The feeding blocks
3043 are important to guarantee that the PHI arguments are renamed
3046 /* FIXME, this is not needed if we are updating symbols. We are
3047 already starting at the ENTRY block anyway. */
3048 bitmap_ior_into (blocks
, pruned_idf
);
3049 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3053 basic_block bb
= BASIC_BLOCK (i
);
3055 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3056 if (e
->src
->index
>= 0)
3057 bitmap_set_bit (blocks
, e
->src
->index
);
3060 insert_phi_nodes_for (var
, pruned_idf
, true);
3063 BITMAP_FREE (pruned_idf
);
3067 /* Sort symbols_to_rename after their DECL_UID. */
3070 insert_updated_phi_nodes_compare_uids (const void *a
, const void *b
)
3072 const_tree syma
= *(const const_tree
*)a
;
3073 const_tree symb
= *(const const_tree
*)b
;
3074 if (DECL_UID (syma
) == DECL_UID (symb
))
3076 return DECL_UID (syma
) < DECL_UID (symb
) ? -1 : 1;
3079 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3080 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3082 1- The names in OLD_SSA_NAMES dominated by the definitions of
3083 NEW_SSA_NAMES are all re-written to be reached by the
3084 appropriate definition from NEW_SSA_NAMES.
3086 2- If needed, new PHI nodes are added to the iterated dominance
3087 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3089 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3090 calling create_new_def_for to create new defs for names that the
3091 caller wants to replace.
3093 The caller cretaes the new names to be inserted and the names that need
3094 to be replaced by calling create_new_def_for for each old definition
3095 to be replaced. Note that the function assumes that the
3096 new defining statement has already been inserted in the IL.
3098 For instance, given the following code:
3101 2 x_1 = PHI (0, x_5)
3112 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3115 2 x_1 = PHI (0, x_5)
3128 We want to replace all the uses of x_1 with the new definitions of
3129 x_10 and x_11. Note that the only uses that should be replaced are
3130 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3131 *not* be replaced (this is why we cannot just mark symbol 'x' for
3134 Additionally, we may need to insert a PHI node at line 11 because
3135 that is a merge point for x_10 and x_11. So the use of x_1 at line
3136 11 will be replaced with the new PHI node. The insertion of PHI
3137 nodes is optional. They are not strictly necessary to preserve the
3138 SSA form, and depending on what the caller inserted, they may not
3139 even be useful for the optimizers. UPDATE_FLAGS controls various
3140 aspects of how update_ssa operates, see the documentation for
3141 TODO_update_ssa*. */
3144 update_ssa (unsigned update_flags
)
3146 basic_block bb
, start_bb
;
3150 sbitmap_iterator sbi
;
3153 /* Only one update flag should be set. */
3154 gcc_assert (update_flags
== TODO_update_ssa
3155 || update_flags
== TODO_update_ssa_no_phi
3156 || update_flags
== TODO_update_ssa_full_phi
3157 || update_flags
== TODO_update_ssa_only_virtuals
);
3159 if (!need_ssa_update_p (cfun
))
3162 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3165 fprintf (dump_file
, "\nUpdating SSA:\n");
3167 if (!update_ssa_initialized_fn
)
3168 init_update_ssa (cfun
);
3169 else if (update_flags
== TODO_update_ssa_only_virtuals
)
3171 /* If we only need to update virtuals, remove all the mappings for
3172 real names before proceeding. The caller is responsible for
3173 having dealt with the name mappings before calling update_ssa. */
3174 bitmap_clear (old_ssa_names
);
3175 bitmap_clear (new_ssa_names
);
3178 gcc_assert (update_ssa_initialized_fn
== cfun
);
3180 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3181 if (!phis_to_rewrite
.exists ())
3182 phis_to_rewrite
.create (last_basic_block
+ 1);
3183 blocks_to_update
= BITMAP_ALLOC (NULL
);
3185 /* Ensure that the dominance information is up-to-date. */
3186 calculate_dominance_info (CDI_DOMINATORS
);
3188 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3190 /* If there are names defined in the replacement table, prepare
3191 definition and use sites for all the names in NEW_SSA_NAMES and
3193 if (bitmap_first_set_bit (new_ssa_names
) >= 0)
3195 prepare_names_to_update (insert_phi_p
);
3197 /* If all the names in NEW_SSA_NAMES had been marked for
3198 removal, and there are no symbols to rename, then there's
3199 nothing else to do. */
3200 if (bitmap_first_set_bit (new_ssa_names
) < 0
3201 && !cfun
->gimple_df
->ssa_renaming_needed
)
3205 /* Next, determine the block at which to start the renaming process. */
3206 if (cfun
->gimple_df
->ssa_renaming_needed
)
3208 /* If we rename bare symbols initialize the mapping to
3209 auxiliar info we need to keep track of. */
3210 var_infos
.create (47);
3212 /* If we have to rename some symbols from scratch, we need to
3213 start the process at the root of the CFG. FIXME, it should
3214 be possible to determine the nearest block that had a
3215 definition for each of the symbols that are marked for
3216 updating. For now this seems more work than it's worth. */
3217 start_bb
= ENTRY_BLOCK_PTR
;
3219 /* Traverse the CFG looking for existing definitions and uses of
3220 symbols in SSA operands. Mark interesting blocks and
3221 statements and set local live-in information for the PHI
3222 placement heuristics. */
3223 prepare_block_for_update (start_bb
, insert_phi_p
);
3225 #ifdef ENABLE_CHECKING
3226 for (i
= 1; i
< num_ssa_names
; ++i
)
3228 tree name
= ssa_name (i
);
3230 || virtual_operand_p (name
))
3233 /* For all but virtual operands, which do not have SSA names
3234 with overlapping life ranges, ensure that symbols marked
3235 for renaming do not have existing SSA names associated with
3236 them as we do not re-write them out-of-SSA before going
3237 into SSA for the remaining symbol uses. */
3238 if (marked_for_renaming (SSA_NAME_VAR (name
)))
3240 fprintf (stderr
, "Existing SSA name for symbol marked for "
3242 print_generic_expr (stderr
, name
, TDF_SLIM
);
3243 fprintf (stderr
, "\n");
3244 internal_error ("SSA corruption");
3251 /* Otherwise, the entry block to the region is the nearest
3252 common dominator for the blocks in BLOCKS. */
3253 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3257 /* If requested, insert PHI nodes at the iterated dominance frontier
3258 of every block, creating new definitions for names in OLD_SSA_NAMES
3259 and for symbols found. */
3264 /* If the caller requested PHI nodes to be added, compute
3265 dominance frontiers. */
3266 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
3268 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
3269 compute_dominance_frontiers (dfs
);
3271 if (bitmap_first_set_bit (old_ssa_names
) >= 0)
3273 sbitmap_iterator sbi
;
3275 /* insert_update_phi_nodes_for will call add_new_name_mapping
3276 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3277 will grow while we are traversing it (but it will not
3278 gain any new members). Copy OLD_SSA_NAMES to a temporary
3280 sbitmap tmp
= sbitmap_alloc (SBITMAP_SIZE (old_ssa_names
));
3281 bitmap_copy (tmp
, old_ssa_names
);
3282 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, sbi
)
3283 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3288 symbols_to_rename
.qsort (insert_updated_phi_nodes_compare_uids
);
3289 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3290 insert_updated_phi_nodes_for (sym
, dfs
, blocks_to_update
,
3294 bitmap_clear (&dfs
[bb
->index
]);
3297 /* Insertion of PHI nodes may have added blocks to the region.
3298 We need to re-compute START_BB to include the newly added
3300 if (start_bb
!= ENTRY_BLOCK_PTR
)
3301 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3305 /* Reset the current definition for name and symbol before renaming
3307 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
3308 get_ssa_name_ann (ssa_name (i
))->info
.current_def
= NULL_TREE
;
3310 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3311 get_var_info (sym
)->info
.current_def
= NULL_TREE
;
3313 /* Now start the renaming process at START_BB. */
3314 interesting_blocks
= sbitmap_alloc (last_basic_block
);
3315 bitmap_clear (interesting_blocks
);
3316 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3317 bitmap_set_bit (interesting_blocks
, i
);
3319 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3321 sbitmap_free (interesting_blocks
);
3323 /* Debugging dumps. */
3329 dump_update_ssa (dump_file
);
3331 fprintf (dump_file
, "Incremental SSA update started at block: %d\n",
3335 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3337 fprintf (dump_file
, "Number of blocks in CFG: %d\n", last_basic_block
);
3338 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n",
3339 c
, PERCENT (c
, last_basic_block
));
3341 if (dump_flags
& TDF_DETAILS
)
3343 fprintf (dump_file
, "Affected blocks:");
3344 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3345 fprintf (dump_file
, " %u", i
);
3346 fprintf (dump_file
, "\n");
3349 fprintf (dump_file
, "\n\n");
3352 /* Free allocated memory. */
3354 delete_update_ssa ();
3356 timevar_pop (TV_TREE_SSA_INCREMENTAL
);