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 "stringpool.h"
39 #include "tree-ssanames.h"
40 #include "tree-into-ssa.h"
44 #include "tree-inline.h"
45 #include "hash-table.h"
46 #include "tree-pass.h"
50 #include "diagnostic-core.h"
51 #include "tree-into-ssa.h"
53 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
55 /* This file builds the SSA form for a function as described in:
56 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
57 Computing Static Single Assignment Form and the Control Dependence
58 Graph. ACM Transactions on Programming Languages and Systems,
59 13(4):451-490, October 1991. */
61 /* Structure to map a variable VAR to the set of blocks that contain
62 definitions for VAR. */
65 /* Blocks that contain definitions of VAR. Bit I will be set if the
66 Ith block contains a definition of VAR. */
69 /* Blocks that contain a PHI node for VAR. */
72 /* Blocks where VAR is live-on-entry. Similar semantics as
77 typedef struct def_blocks_d
*def_blocks_p
;
80 /* Stack of trees used to restore the global currdefs to its original
81 state after completing rewriting of a block and its dominator
82 children. Its elements have the following properties:
84 - An SSA_NAME (N) indicates that the current definition of the
85 underlying variable should be set to the given SSA_NAME. If the
86 symbol associated with the SSA_NAME is not a GIMPLE register, the
87 next slot in the stack must be a _DECL node (SYM). In this case,
88 the name N in the previous slot is the current reaching
91 - A _DECL node indicates that the underlying variable has no
94 - A NULL node at the top entry is used to mark the last slot
95 associated with the current block. */
96 static vec
<tree
> block_defs_stack
;
99 /* Set of existing SSA names being replaced by update_ssa. */
100 static sbitmap old_ssa_names
;
102 /* Set of new SSA names being added by update_ssa. Note that both
103 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
104 the operations done on them are presence tests. */
105 static sbitmap new_ssa_names
;
107 static sbitmap interesting_blocks
;
109 /* Set of SSA names that have been marked to be released after they
110 were registered in the replacement table. They will be finally
111 released after we finish updating the SSA web. */
112 static bitmap names_to_release
;
114 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
115 the to basic block with index I. Allocated once per compilation, *not*
116 released between different functions. */
117 static vec
<gimple_vec
> phis_to_rewrite
;
119 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
120 static bitmap blocks_with_phis_to_rewrite
;
122 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
123 to grow as the callers to create_new_def_for will create new names on
125 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
126 need to find a reasonable growth strategy. */
127 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
130 /* The function the SSA updating data structures have been initialized for.
131 NULL if they need to be initialized by create_new_def_for. */
132 static struct function
*update_ssa_initialized_fn
= NULL
;
134 /* Global data to attach to the main dominator walk structure. */
135 struct mark_def_sites_global_data
137 /* This bitmap contains the variables which are set before they
138 are used in a basic block. */
142 /* It is advantageous to avoid things like life analysis for variables which
143 do not need PHI nodes. This enum describes whether or not a particular
144 variable may need a PHI node. */
146 enum need_phi_state
{
147 /* This is the default. If we are still in this state after finding
148 all the definition and use sites, then we will assume the variable
149 needs PHI nodes. This is probably an overly conservative assumption. */
150 NEED_PHI_STATE_UNKNOWN
,
152 /* This state indicates that we have seen one or more sets of the
153 variable in a single basic block and that the sets dominate all
154 uses seen so far. If after finding all definition and use sites
155 we are still in this state, then the variable does not need any
159 /* This state indicates that we have either seen multiple definitions of
160 the variable in multiple blocks, or that we encountered a use in a
161 block that was not dominated by the block containing the set(s) of
162 this variable. This variable is assumed to need PHI nodes. */
166 /* Information stored for both SSA names and decls. */
169 /* This field indicates whether or not the variable may need PHI nodes.
170 See the enum's definition for more detailed information about the
172 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
174 /* The current reaching definition replacing this var. */
177 /* Definitions for this var. */
178 struct def_blocks_d def_blocks
;
181 /* The information associated with decls and SSA names. */
182 typedef struct common_info_d
*common_info_p
;
184 /* Information stored for decls. */
190 /* Information stored for both SSA names and decls. */
191 struct common_info_d info
;
194 /* The information associated with decls. */
195 typedef struct var_info_d
*var_info_p
;
198 /* VAR_INFOS hashtable helpers. */
200 struct var_info_hasher
: typed_free_remove
<var_info_d
>
202 typedef var_info_d value_type
;
203 typedef var_info_d compare_type
;
204 static inline hashval_t
hash (const value_type
*);
205 static inline bool equal (const value_type
*, const compare_type
*);
209 var_info_hasher::hash (const value_type
*p
)
211 return DECL_UID (p
->var
);
215 var_info_hasher::equal (const value_type
*p1
, const compare_type
*p2
)
217 return p1
->var
== p2
->var
;
221 /* Each entry in VAR_INFOS contains an element of type STRUCT
223 static hash_table
<var_info_hasher
> var_infos
;
226 /* Information stored for SSA names. */
229 /* Age of this record (so that info_for_ssa_name table can be cleared
230 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
231 are assumed to be null. */
234 /* Replacement mappings, allocated from update_ssa_obstack. */
237 /* Information stored for both SSA names and decls. */
238 struct common_info_d info
;
241 /* The information associated with names. */
242 typedef struct ssa_name_info
*ssa_name_info_p
;
244 static vec
<ssa_name_info_p
> info_for_ssa_name
;
245 static unsigned current_info_for_ssa_name_age
;
247 static bitmap_obstack update_ssa_obstack
;
249 /* The set of blocks affected by update_ssa. */
250 static bitmap blocks_to_update
;
252 /* The main entry point to the SSA renamer (rewrite_blocks) may be
253 called several times to do different, but related, tasks.
254 Initially, we need it to rename the whole program into SSA form.
255 At other times, we may need it to only rename into SSA newly
256 exposed symbols. Finally, we can also call it to incrementally fix
257 an already built SSA web. */
259 /* Convert the whole function into SSA form. */
262 /* Incrementally update the SSA web by replacing existing SSA
263 names with new ones. See update_ssa for details. */
267 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
268 static bitmap symbols_to_rename_set
;
269 static vec
<tree
> symbols_to_rename
;
271 /* Mark SYM for renaming. */
274 mark_for_renaming (tree sym
)
276 if (!symbols_to_rename_set
)
277 symbols_to_rename_set
= BITMAP_ALLOC (NULL
);
278 if (bitmap_set_bit (symbols_to_rename_set
, DECL_UID (sym
)))
279 symbols_to_rename
.safe_push (sym
);
282 /* Return true if SYM is marked for renaming. */
285 marked_for_renaming (tree sym
)
287 if (!symbols_to_rename_set
|| sym
== NULL_TREE
)
289 return bitmap_bit_p (symbols_to_rename_set
, DECL_UID (sym
));
293 /* Return true if STMT needs to be rewritten. When renaming a subset
294 of the variables, not all statements will be processed. This is
295 decided in mark_def_sites. */
298 rewrite_uses_p (gimple stmt
)
300 return gimple_visited_p (stmt
);
304 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
307 set_rewrite_uses (gimple stmt
, bool rewrite_p
)
309 gimple_set_visited (stmt
, rewrite_p
);
313 /* Return true if the DEFs created by statement STMT should be
314 registered when marking new definition sites. This is slightly
315 different than rewrite_uses_p: it's used by update_ssa to
316 distinguish statements that need to have both uses and defs
317 processed from those that only need to have their defs processed.
318 Statements that define new SSA names only need to have their defs
319 registered, but they don't need to have their uses renamed. */
322 register_defs_p (gimple stmt
)
324 return gimple_plf (stmt
, GF_PLF_1
) != 0;
328 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
331 set_register_defs (gimple stmt
, bool register_defs_p
)
333 gimple_set_plf (stmt
, GF_PLF_1
, register_defs_p
);
337 /* Get the information associated with NAME. */
339 static inline ssa_name_info_p
340 get_ssa_name_ann (tree name
)
342 unsigned ver
= SSA_NAME_VERSION (name
);
343 unsigned len
= info_for_ssa_name
.length ();
344 struct ssa_name_info
*info
;
346 /* Re-allocate the vector at most once per update/into-SSA. */
348 info_for_ssa_name
.safe_grow_cleared (num_ssa_names
);
350 /* But allocate infos lazily. */
351 info
= info_for_ssa_name
[ver
];
354 info
= XCNEW (struct ssa_name_info
);
355 info
->age
= current_info_for_ssa_name_age
;
356 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
357 info_for_ssa_name
[ver
] = info
;
360 if (info
->age
< current_info_for_ssa_name_age
)
362 info
->age
= current_info_for_ssa_name_age
;
363 info
->repl_set
= NULL
;
364 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
365 info
->info
.current_def
= NULL_TREE
;
366 info
->info
.def_blocks
.def_blocks
= NULL
;
367 info
->info
.def_blocks
.phi_blocks
= NULL
;
368 info
->info
.def_blocks
.livein_blocks
= NULL
;
374 /* Return and allocate the auxiliar information for DECL. */
376 static inline var_info_p
377 get_var_info (tree decl
)
379 struct var_info_d vi
;
382 slot
= var_infos
.find_slot_with_hash (&vi
, DECL_UID (decl
), INSERT
);
385 var_info_p v
= XCNEW (struct var_info_d
);
394 /* Clears info for SSA names. */
397 clear_ssa_name_info (void)
399 current_info_for_ssa_name_age
++;
401 /* If current_info_for_ssa_name_age wraps we use stale information.
402 Asser that this does not happen. */
403 gcc_assert (current_info_for_ssa_name_age
!= 0);
407 /* Get access to the auxiliar information stored per SSA name or decl. */
409 static inline common_info_p
410 get_common_info (tree var
)
412 if (TREE_CODE (var
) == SSA_NAME
)
413 return &get_ssa_name_ann (var
)->info
;
415 return &get_var_info (var
)->info
;
419 /* Return the current definition for VAR. */
422 get_current_def (tree var
)
424 return get_common_info (var
)->current_def
;
428 /* Sets current definition of VAR to DEF. */
431 set_current_def (tree var
, tree def
)
433 get_common_info (var
)->current_def
= def
;
436 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
437 all statements in basic block BB. */
440 initialize_flags_in_bb (basic_block bb
)
443 gimple_stmt_iterator gsi
;
445 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
447 gimple phi
= gsi_stmt (gsi
);
448 set_rewrite_uses (phi
, false);
449 set_register_defs (phi
, false);
452 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
454 stmt
= gsi_stmt (gsi
);
456 /* We are going to use the operand cache API, such as
457 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
458 cache for each statement should be up-to-date. */
459 gcc_checking_assert (!gimple_modified_p (stmt
));
460 set_rewrite_uses (stmt
, false);
461 set_register_defs (stmt
, false);
465 /* Mark block BB as interesting for update_ssa. */
468 mark_block_for_update (basic_block bb
)
470 gcc_checking_assert (blocks_to_update
!= NULL
);
471 if (!bitmap_set_bit (blocks_to_update
, bb
->index
))
473 initialize_flags_in_bb (bb
);
476 /* Return the set of blocks where variable VAR is defined and the blocks
477 where VAR is live on entry (livein). If no entry is found in
478 DEF_BLOCKS, a new one is created and returned. */
480 static inline struct def_blocks_d
*
481 get_def_blocks_for (common_info_p info
)
483 struct def_blocks_d
*db_p
= &info
->def_blocks
;
484 if (!db_p
->def_blocks
)
486 db_p
->def_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
487 db_p
->phi_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
488 db_p
->livein_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
495 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
496 VAR is defined by a PHI node. */
499 set_def_block (tree var
, basic_block bb
, bool phi_p
)
501 struct def_blocks_d
*db_p
;
504 info
= get_common_info (var
);
505 db_p
= get_def_blocks_for (info
);
507 /* Set the bit corresponding to the block where VAR is defined. */
508 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
510 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
512 /* Keep track of whether or not we may need to insert PHI nodes.
514 If we are in the UNKNOWN state, then this is the first definition
515 of VAR. Additionally, we have not seen any uses of VAR yet, so
516 we do not need a PHI node for this variable at this time (i.e.,
517 transition to NEED_PHI_STATE_NO).
519 If we are in any other state, then we either have multiple definitions
520 of this variable occurring in different blocks or we saw a use of the
521 variable which was not dominated by the block containing the
522 definition(s). In this case we may need a PHI node, so enter
523 state NEED_PHI_STATE_MAYBE. */
524 if (info
->need_phi_state
== NEED_PHI_STATE_UNKNOWN
)
525 info
->need_phi_state
= NEED_PHI_STATE_NO
;
527 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
531 /* Mark block BB as having VAR live at the entry to BB. */
534 set_livein_block (tree var
, basic_block bb
)
537 struct def_blocks_d
*db_p
;
539 info
= get_common_info (var
);
540 db_p
= get_def_blocks_for (info
);
542 /* Set the bit corresponding to the block where VAR is live in. */
543 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
545 /* Keep track of whether or not we may need to insert PHI nodes.
547 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
548 by the single block containing the definition(s) of this variable. If
549 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
550 NEED_PHI_STATE_MAYBE. */
551 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
553 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
555 if (def_block_index
== -1
556 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
557 BASIC_BLOCK (def_block_index
)))
558 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
561 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
565 /* Return true if NAME is in OLD_SSA_NAMES. */
568 is_old_name (tree name
)
570 unsigned ver
= SSA_NAME_VERSION (name
);
573 return (ver
< SBITMAP_SIZE (new_ssa_names
)
574 && bitmap_bit_p (old_ssa_names
, ver
));
578 /* Return true if NAME is in NEW_SSA_NAMES. */
581 is_new_name (tree name
)
583 unsigned ver
= SSA_NAME_VERSION (name
);
586 return (ver
< SBITMAP_SIZE (new_ssa_names
)
587 && bitmap_bit_p (new_ssa_names
, ver
));
591 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
594 names_replaced_by (tree new_tree
)
596 return get_ssa_name_ann (new_tree
)->repl_set
;
600 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
603 add_to_repl_tbl (tree new_tree
, tree old
)
605 bitmap
*set
= &get_ssa_name_ann (new_tree
)->repl_set
;
607 *set
= BITMAP_ALLOC (&update_ssa_obstack
);
608 bitmap_set_bit (*set
, SSA_NAME_VERSION (old
));
612 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
613 represents the set of names O_1 ... O_j replaced by N_i. This is
614 used by update_ssa and its helpers to introduce new SSA names in an
615 already formed SSA web. */
618 add_new_name_mapping (tree new_tree
, tree old
)
620 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
621 gcc_checking_assert (new_tree
!= old
622 && SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
624 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
625 caller may have created new names since the set was created. */
626 if (SBITMAP_SIZE (new_ssa_names
) <= num_ssa_names
- 1)
628 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
629 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
630 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
633 /* Update the REPL_TBL table. */
634 add_to_repl_tbl (new_tree
, old
);
636 /* If OLD had already been registered as a new name, then all the
637 names that OLD replaces should also be replaced by NEW_TREE. */
638 if (is_new_name (old
))
639 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
641 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
643 bitmap_set_bit (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
644 bitmap_set_bit (old_ssa_names
, SSA_NAME_VERSION (old
));
648 /* Call back for walk_dominator_tree used to collect definition sites
649 for every variable in the function. For every statement S in block
652 1- Variables defined by S in the DEFS of S are marked in the bitmap
655 2- If S uses a variable VAR and there is no preceding kill of VAR,
656 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
658 This information is used to determine which variables are live
659 across block boundaries to reduce the number of PHI nodes
663 mark_def_sites (basic_block bb
, gimple stmt
, bitmap kills
)
669 /* Since this is the first time that we rewrite the program into SSA
670 form, force an operand scan on every statement. */
673 gcc_checking_assert (blocks_to_update
== NULL
);
674 set_register_defs (stmt
, false);
675 set_rewrite_uses (stmt
, false);
677 if (is_gimple_debug (stmt
))
679 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
681 tree sym
= USE_FROM_PTR (use_p
);
682 gcc_checking_assert (DECL_P (sym
));
683 set_rewrite_uses (stmt
, true);
685 if (rewrite_uses_p (stmt
))
686 bitmap_set_bit (interesting_blocks
, bb
->index
);
690 /* If a variable is used before being set, then the variable is live
691 across a block boundary, so mark it live-on-entry to BB. */
692 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
694 tree sym
= USE_FROM_PTR (use_p
);
695 gcc_checking_assert (DECL_P (sym
));
696 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
697 set_livein_block (sym
, bb
);
698 set_rewrite_uses (stmt
, true);
701 /* Now process the defs. Mark BB as the definition block and add
702 each def to the set of killed symbols. */
703 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
705 gcc_checking_assert (DECL_P (def
));
706 set_def_block (def
, bb
, false);
707 bitmap_set_bit (kills
, DECL_UID (def
));
708 set_register_defs (stmt
, true);
711 /* If we found the statement interesting then also mark the block BB
713 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
714 bitmap_set_bit (interesting_blocks
, bb
->index
);
717 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
718 in the dfs numbering of the dominance tree. */
722 /* Basic block whose index this entry corresponds to. */
725 /* The dfs number of this node. */
729 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
733 cmp_dfsnum (const void *a
, const void *b
)
735 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
736 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
738 return (int) da
->dfs_num
- (int) db
->dfs_num
;
741 /* Among the intervals starting at the N points specified in DEFS, find
742 the one that contains S, and return its bb_index. */
745 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
747 unsigned f
= 0, t
= n
, m
;
752 if (defs
[m
].dfs_num
<= s
)
758 return defs
[f
].bb_index
;
761 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
762 KILLS is a bitmap of blocks where the value is defined before any use. */
765 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
769 unsigned i
, b
, p
, u
, top
;
771 basic_block def_bb
, use_bb
;
775 struct dom_dfsnum
*defs
;
776 unsigned n_defs
, adef
;
778 if (bitmap_empty_p (uses
))
784 /* The phi must dominate a use, or an argument of a live phi. Also, we
785 do not create any phi nodes in def blocks, unless they are also livein. */
786 to_remove
= BITMAP_ALLOC (NULL
);
787 bitmap_and_compl (to_remove
, kills
, uses
);
788 bitmap_and_compl_into (phis
, to_remove
);
789 if (bitmap_empty_p (phis
))
791 BITMAP_FREE (to_remove
);
795 /* We want to remove the unnecessary phi nodes, but we do not want to compute
796 liveness information, as that may be linear in the size of CFG, and if
797 there are lot of different variables to rewrite, this may lead to quadratic
800 Instead, we basically emulate standard dce. We put all uses to worklist,
801 then for each of them find the nearest def that dominates them. If this
802 def is a phi node, we mark it live, and if it was not live before, we
803 add the predecessors of its basic block to the worklist.
805 To quickly locate the nearest def that dominates use, we use dfs numbering
806 of the dominance tree (that is already available in order to speed up
807 queries). For each def, we have the interval given by the dfs number on
808 entry to and on exit from the corresponding subtree in the dominance tree.
809 The nearest dominator for a given use is the smallest of these intervals
810 that contains entry and exit dfs numbers for the basic block with the use.
811 If we store the bounds for all the uses to an array and sort it, we can
812 locate the nearest dominating def in logarithmic time by binary search.*/
813 bitmap_ior (to_remove
, kills
, phis
);
814 n_defs
= bitmap_count_bits (to_remove
);
815 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
816 defs
[0].bb_index
= 1;
819 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
821 def_bb
= BASIC_BLOCK (i
);
822 defs
[adef
].bb_index
= i
;
823 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
824 defs
[adef
+ 1].bb_index
= i
;
825 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
828 BITMAP_FREE (to_remove
);
829 gcc_assert (adef
== 2 * n_defs
+ 1);
830 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
831 gcc_assert (defs
[0].bb_index
== 1);
833 /* Now each DEFS entry contains the number of the basic block to that the
834 dfs number corresponds. Change them to the number of basic block that
835 corresponds to the interval following the dfs number. Also, for the
836 dfs_out numbers, increase the dfs number by one (so that it corresponds
837 to the start of the following interval, not to the end of the current
838 one). We use WORKLIST as a stack. */
839 worklist
.create (n_defs
+ 1);
840 worklist
.quick_push (1);
843 for (i
= 1; i
< adef
; i
++)
845 b
= defs
[i
].bb_index
;
848 /* This is a closing element. Interval corresponding to the top
849 of the stack after removing it follows. */
851 top
= worklist
[worklist
.length () - 1];
852 defs
[n_defs
].bb_index
= top
;
853 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
857 /* Opening element. Nothing to do, just push it to the stack and move
858 it to the correct position. */
859 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
860 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
861 worklist
.quick_push (b
);
865 /* If this interval starts at the same point as the previous one, cancel
867 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
868 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
873 gcc_assert (worklist
.is_empty ());
875 /* Now process the uses. */
876 live_phis
= BITMAP_ALLOC (NULL
);
877 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
879 worklist
.safe_push (i
);
882 while (!worklist
.is_empty ())
885 if (b
== ENTRY_BLOCK
)
888 /* If there is a phi node in USE_BB, it is made live. Otherwise,
889 find the def that dominates the immediate dominator of USE_BB
890 (the kill in USE_BB does not dominate the use). */
891 if (bitmap_bit_p (phis
, b
))
895 use_bb
= get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (b
));
896 p
= find_dfsnum_interval (defs
, n_defs
,
897 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
898 if (!bitmap_bit_p (phis
, p
))
902 /* If the phi node is already live, there is nothing to do. */
903 if (!bitmap_set_bit (live_phis
, p
))
906 /* Add the new uses to the worklist. */
907 def_bb
= BASIC_BLOCK (p
);
908 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
911 if (bitmap_bit_p (uses
, u
))
914 /* In case there is a kill directly in the use block, do not record
915 the use (this is also necessary for correctness, as we assume that
916 uses dominated by a def directly in their block have been filtered
918 if (bitmap_bit_p (kills
, u
))
921 bitmap_set_bit (uses
, u
);
922 worklist
.safe_push (u
);
927 bitmap_copy (phis
, live_phis
);
928 BITMAP_FREE (live_phis
);
932 /* Return the set of blocks where variable VAR is defined and the blocks
933 where VAR is live on entry (livein). Return NULL, if no entry is
934 found in DEF_BLOCKS. */
936 static inline struct def_blocks_d
*
937 find_def_blocks_for (tree var
)
939 def_blocks_p p
= &get_common_info (var
)->def_blocks
;
946 /* Marks phi node PHI in basic block BB for rewrite. */
949 mark_phi_for_rewrite (basic_block bb
, gimple phi
)
952 unsigned n
, idx
= bb
->index
;
954 if (rewrite_uses_p (phi
))
957 set_rewrite_uses (phi
, true);
959 if (!blocks_with_phis_to_rewrite
)
962 bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
);
964 n
= (unsigned) last_basic_block
+ 1;
965 if (phis_to_rewrite
.length () < n
)
966 phis_to_rewrite
.safe_grow_cleared (n
);
968 phis
= phis_to_rewrite
[idx
];
971 phis
.safe_push (phi
);
972 phis_to_rewrite
[idx
] = phis
;
975 /* Insert PHI nodes for variable VAR using the iterated dominance
976 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
977 function assumes that the caller is incrementally updating the
978 existing SSA form, in which case VAR may be an SSA name instead of
981 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
982 PHI node for VAR. On exit, only the nodes that received a PHI node
983 for VAR will be present in PHI_INSERTION_POINTS. */
986 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
993 struct def_blocks_d
*def_map
= find_def_blocks_for (var
);
995 /* Remove the blocks where we already have PHI nodes for VAR. */
996 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
998 /* Remove obviously useless phi nodes. */
999 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
1000 def_map
->livein_blocks
);
1002 /* And insert the PHI nodes. */
1003 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
1005 bb
= BASIC_BLOCK (bb_index
);
1007 mark_block_for_update (bb
);
1009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1011 fprintf (dump_file
, "creating PHI node in block #%d for ", bb_index
);
1012 print_generic_expr (dump_file
, var
, TDF_SLIM
);
1013 fprintf (dump_file
, "\n");
1017 if (TREE_CODE (var
) == SSA_NAME
)
1019 /* If we are rewriting SSA names, create the LHS of the PHI
1020 node by duplicating VAR. This is useful in the case of
1021 pointers, to also duplicate pointer attributes (alias
1022 information, in particular). */
1026 gcc_checking_assert (update_p
);
1027 new_lhs
= duplicate_ssa_name (var
, NULL
);
1028 phi
= create_phi_node (new_lhs
, bb
);
1029 add_new_name_mapping (new_lhs
, var
);
1031 /* Add VAR to every argument slot of PHI. We need VAR in
1032 every argument so that rewrite_update_phi_arguments knows
1033 which name is this PHI node replacing. If VAR is a
1034 symbol marked for renaming, this is not necessary, the
1035 renamer will use the symbol on the LHS to get its
1036 reaching definition. */
1037 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1038 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1044 gcc_checking_assert (DECL_P (var
));
1045 phi
= create_phi_node (var
, bb
);
1047 tracked_var
= target_for_debug_bind (var
);
1050 gimple note
= gimple_build_debug_bind (tracked_var
,
1053 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1054 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1058 /* Mark this PHI node as interesting for update_ssa. */
1059 set_register_defs (phi
, true);
1060 mark_phi_for_rewrite (bb
, phi
);
1064 /* Sort var_infos after DECL_UID of their var. */
1067 insert_phi_nodes_compare_var_infos (const void *a
, const void *b
)
1069 const struct var_info_d
*defa
= *(struct var_info_d
* const *)a
;
1070 const struct var_info_d
*defb
= *(struct var_info_d
* const *)b
;
1071 if (DECL_UID (defa
->var
) < DECL_UID (defb
->var
))
1077 /* Insert PHI nodes at the dominance frontier of blocks with variable
1078 definitions. DFS contains the dominance frontier information for
1082 insert_phi_nodes (bitmap_head
*dfs
)
1084 hash_table
<var_info_hasher
>::iterator hi
;
1087 vec
<var_info_p
> vars
;
1089 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1091 vars
.create (var_infos
.elements ());
1092 FOR_EACH_HASH_TABLE_ELEMENT (var_infos
, info
, var_info_p
, hi
)
1093 if (info
->info
.need_phi_state
!= NEED_PHI_STATE_NO
)
1094 vars
.quick_push (info
);
1096 /* Do two stages to avoid code generation differences for UID
1097 differences but no UID ordering differences. */
1098 vars
.qsort (insert_phi_nodes_compare_var_infos
);
1100 FOR_EACH_VEC_ELT (vars
, i
, info
)
1102 bitmap idf
= compute_idf (info
->info
.def_blocks
.def_blocks
, dfs
);
1103 insert_phi_nodes_for (info
->var
, idf
, false);
1109 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1113 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1114 register DEF (an SSA_NAME) to be a new definition for SYM. */
1117 register_new_def (tree def
, tree sym
)
1119 common_info_p info
= get_common_info (sym
);
1122 /* If this variable is set in a single basic block and all uses are
1123 dominated by the set(s) in that single basic block, then there is
1124 no reason to record anything for this variable in the block local
1125 definition stacks. Doing so just wastes time and memory.
1127 This is the same test to prune the set of variables which may
1128 need PHI nodes. So we just use that information since it's already
1129 computed and available for us to use. */
1130 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1132 info
->current_def
= def
;
1136 currdef
= info
->current_def
;
1138 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1139 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1140 in the stack so that we know which symbol is being defined by
1141 this SSA name when we unwind the stack. */
1142 if (currdef
&& !is_gimple_reg (sym
))
1143 block_defs_stack
.safe_push (sym
);
1145 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1146 stack is later used by the dominator tree callbacks to restore
1147 the reaching definitions for all the variables defined in the
1148 block after a recursive visit to all its immediately dominated
1149 blocks. If there is no current reaching definition, then just
1150 record the underlying _DECL node. */
1151 block_defs_stack
.safe_push (currdef
? currdef
: sym
);
1153 /* Set the current reaching definition for SYM to be DEF. */
1154 info
->current_def
= def
;
1158 /* Perform a depth-first traversal of the dominator tree looking for
1159 variables to rename. BB is the block where to start searching.
1160 Renaming is a five step process:
1162 1- Every definition made by PHI nodes at the start of the blocks is
1163 registered as the current definition for the corresponding variable.
1165 2- Every statement in BB is rewritten. USE and VUSE operands are
1166 rewritten with their corresponding reaching definition. DEF and
1167 VDEF targets are registered as new definitions.
1169 3- All the PHI nodes in successor blocks of BB are visited. The
1170 argument corresponding to BB is replaced with its current reaching
1173 4- Recursively rewrite every dominator child block of BB.
1175 5- Restore (in reverse order) the current reaching definition for every
1176 new definition introduced in this block. This is done so that when
1177 we return from the recursive call, all the current reaching
1178 definitions are restored to the names that were valid in the
1179 dominator parent of BB. */
1181 /* Return the current definition for variable VAR. If none is found,
1182 create a new SSA name to act as the zeroth definition for VAR. */
1185 get_reaching_def (tree var
)
1187 common_info_p info
= get_common_info (var
);
1190 /* Lookup the current reaching definition for VAR. */
1191 currdef
= info
->current_def
;
1193 /* If there is no reaching definition for VAR, create and register a
1194 default definition for it (if needed). */
1195 if (currdef
== NULL_TREE
)
1197 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1198 currdef
= get_or_create_ssa_default_def (cfun
, sym
);
1201 /* Return the current reaching definition for VAR, or the default
1202 definition, if we had to create one. */
1207 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1210 rewrite_debug_stmt_uses (gimple stmt
)
1212 use_operand_p use_p
;
1214 bool update
= false;
1216 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1218 tree var
= USE_FROM_PTR (use_p
), def
;
1219 common_info_p info
= get_common_info (var
);
1220 gcc_checking_assert (DECL_P (var
));
1221 def
= info
->current_def
;
1224 if (TREE_CODE (var
) == PARM_DECL
&& single_succ_p (ENTRY_BLOCK_PTR
))
1226 gimple_stmt_iterator gsi
1227 = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR
));
1229 /* Search a few source bind stmts at the start of first bb to
1230 see if a DEBUG_EXPR_DECL can't be reused. */
1232 !gsi_end_p (gsi
) && lim
> 0;
1233 gsi_next (&gsi
), lim
--)
1235 gimple gstmt
= gsi_stmt (gsi
);
1236 if (!gimple_debug_source_bind_p (gstmt
))
1238 if (gimple_debug_source_bind_get_value (gstmt
) == var
)
1240 def
= gimple_debug_source_bind_get_var (gstmt
);
1241 if (TREE_CODE (def
) == DEBUG_EXPR_DECL
)
1247 /* If not, add a new source bind stmt. */
1248 if (def
== NULL_TREE
)
1251 def
= make_node (DEBUG_EXPR_DECL
);
1252 def_temp
= gimple_build_debug_source_bind (def
, var
, NULL
);
1253 DECL_ARTIFICIAL (def
) = 1;
1254 TREE_TYPE (def
) = TREE_TYPE (var
);
1255 DECL_MODE (def
) = DECL_MODE (var
);
1256 gsi
= gsi_after_labels (single_succ (ENTRY_BLOCK_PTR
));
1257 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
1264 /* Check if info->current_def can be trusted. */
1265 basic_block bb
= gimple_bb (stmt
);
1267 = SSA_NAME_IS_DEFAULT_DEF (def
)
1268 ? NULL
: gimple_bb (SSA_NAME_DEF_STMT (def
));
1270 /* If definition is in current bb, it is fine. */
1273 /* If definition bb doesn't dominate the current bb,
1274 it can't be used. */
1275 else if (def_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
1277 /* If there is just one definition and dominates the current
1279 else if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1283 struct def_blocks_d
*db_p
= get_def_blocks_for (info
);
1285 /* If there are some non-debug uses in the current bb,
1287 if (bitmap_bit_p (db_p
->livein_blocks
, bb
->index
))
1289 /* Otherwise give up for now. */
1296 gimple_debug_bind_reset_value (stmt
);
1300 SET_USE (use_p
, def
);
1306 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1307 the block with its immediate reaching definitions. Update the current
1308 definition of a variable when a new real or virtual definition is found. */
1311 rewrite_stmt (gimple_stmt_iterator
*si
)
1313 use_operand_p use_p
;
1314 def_operand_p def_p
;
1316 gimple stmt
= gsi_stmt (*si
);
1318 /* If mark_def_sites decided that we don't need to rewrite this
1319 statement, ignore it. */
1320 gcc_assert (blocks_to_update
== NULL
);
1321 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1326 fprintf (dump_file
, "Renaming statement ");
1327 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1328 fprintf (dump_file
, "\n");
1331 /* Step 1. Rewrite USES in the statement. */
1332 if (rewrite_uses_p (stmt
))
1334 if (is_gimple_debug (stmt
))
1335 rewrite_debug_stmt_uses (stmt
);
1337 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1339 tree var
= USE_FROM_PTR (use_p
);
1340 gcc_checking_assert (DECL_P (var
));
1341 SET_USE (use_p
, get_reaching_def (var
));
1345 /* Step 2. Register the statement's DEF operands. */
1346 if (register_defs_p (stmt
))
1347 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1349 tree var
= DEF_FROM_PTR (def_p
);
1353 gcc_checking_assert (DECL_P (var
));
1355 if (gimple_clobber_p (stmt
)
1356 && is_gimple_reg (var
))
1358 /* If we rewrite a DECL into SSA form then drop its
1359 clobber stmts and replace uses with a new default def. */
1360 gcc_checking_assert (TREE_CODE (var
) == VAR_DECL
1361 && !gimple_vdef (stmt
));
1362 gsi_replace (si
, gimple_build_nop (), true);
1363 register_new_def (get_or_create_ssa_default_def (cfun
, var
), var
);
1367 name
= make_ssa_name (var
, stmt
);
1368 SET_DEF (def_p
, name
);
1369 register_new_def (DEF_FROM_PTR (def_p
), var
);
1371 tracked_var
= target_for_debug_bind (var
);
1374 gimple note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1375 gsi_insert_after (si
, note
, GSI_SAME_STMT
);
1381 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1382 PHI nodes. For every PHI node found, add a new argument containing the
1383 current reaching definition for the variable and the edge through which
1384 that definition is reaching the PHI node. */
1387 rewrite_add_phi_arguments (basic_block bb
)
1392 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1395 gimple_stmt_iterator gsi
;
1397 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1403 phi
= gsi_stmt (gsi
);
1404 res
= gimple_phi_result (phi
);
1405 currdef
= get_reaching_def (SSA_NAME_VAR (res
));
1406 /* Virtual operand PHI args do not need a location. */
1407 if (virtual_operand_p (res
))
1408 loc
= UNKNOWN_LOCATION
;
1410 loc
= gimple_location (SSA_NAME_DEF_STMT (currdef
));
1411 add_phi_arg (phi
, currdef
, e
, loc
);
1416 class rewrite_dom_walker
: public dom_walker
1419 rewrite_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1421 virtual void before_dom_children (basic_block
);
1422 virtual void after_dom_children (basic_block
);
1425 /* SSA Rewriting Step 1. Initialization, create a block local stack
1426 of reaching definitions for new SSA names produced in this block
1427 (BLOCK_DEFS). Register new definitions for every PHI node in the
1431 rewrite_dom_walker::before_dom_children (basic_block bb
)
1433 gimple_stmt_iterator gsi
;
1435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1436 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1438 /* Mark the unwind point for this block. */
1439 block_defs_stack
.safe_push (NULL_TREE
);
1441 /* Step 1. Register new definitions for every PHI node in the block.
1442 Conceptually, all the PHI nodes are executed in parallel and each PHI
1443 node introduces a new version for the associated variable. */
1444 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1446 tree result
= gimple_phi_result (gsi_stmt (gsi
));
1447 register_new_def (result
, SSA_NAME_VAR (result
));
1450 /* Step 2. Rewrite every variable used in each statement in the block
1451 with its immediate reaching definitions. Update the current definition
1452 of a variable when a new real or virtual definition is found. */
1453 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
1454 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1455 rewrite_stmt (&gsi
);
1457 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1458 For every PHI node found, add a new argument containing the current
1459 reaching definition for the variable and the edge through which that
1460 definition is reaching the PHI node. */
1461 rewrite_add_phi_arguments (bb
);
1466 /* Called after visiting all the statements in basic block BB and all
1467 of its dominator children. Restore CURRDEFS to its original value. */
1470 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
1472 /* Restore CURRDEFS to its original state. */
1473 while (block_defs_stack
.length () > 0)
1475 tree tmp
= block_defs_stack
.pop ();
1476 tree saved_def
, var
;
1478 if (tmp
== NULL_TREE
)
1481 if (TREE_CODE (tmp
) == SSA_NAME
)
1483 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1484 current definition of its underlying variable. Note that
1485 if the SSA_NAME is not for a GIMPLE register, the symbol
1486 being defined is stored in the next slot in the stack.
1487 This mechanism is needed because an SSA name for a
1488 non-register symbol may be the definition for more than
1489 one symbol (e.g., SFTs, aliased variables, etc). */
1491 var
= SSA_NAME_VAR (saved_def
);
1492 if (!is_gimple_reg (var
))
1493 var
= block_defs_stack
.pop ();
1497 /* If we recorded anything else, it must have been a _DECL
1498 node and its current reaching definition must have been
1504 get_common_info (var
)->current_def
= saved_def
;
1509 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1512 debug_decl_set (bitmap set
)
1514 dump_decl_set (stderr
, set
);
1515 fprintf (stderr
, "\n");
1519 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1520 stack up to a maximum of N levels. If N is -1, the whole stack is
1521 dumped. New levels are created when the dominator tree traversal
1522 used for renaming enters a new sub-tree. */
1525 dump_defs_stack (FILE *file
, int n
)
1529 fprintf (file
, "\n\nRenaming stack");
1531 fprintf (file
, " (up to %d levels)", n
);
1532 fprintf (file
, "\n\n");
1535 fprintf (file
, "Level %d (current level)\n", i
);
1536 for (j
= (int) block_defs_stack
.length () - 1; j
>= 0; j
--)
1540 name
= block_defs_stack
[j
];
1541 if (name
== NULL_TREE
)
1546 fprintf (file
, "\nLevel %d\n", i
);
1557 var
= SSA_NAME_VAR (name
);
1558 if (!is_gimple_reg (var
))
1561 var
= block_defs_stack
[j
];
1565 fprintf (file
, " Previous CURRDEF (");
1566 print_generic_expr (file
, var
, 0);
1567 fprintf (file
, ") = ");
1569 print_generic_expr (file
, name
, 0);
1571 fprintf (file
, "<NIL>");
1572 fprintf (file
, "\n");
1577 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1578 stack up to a maximum of N levels. If N is -1, the whole stack is
1579 dumped. New levels are created when the dominator tree traversal
1580 used for renaming enters a new sub-tree. */
1583 debug_defs_stack (int n
)
1585 dump_defs_stack (stderr
, n
);
1589 /* Dump the current reaching definition of every symbol to FILE. */
1592 dump_currdefs (FILE *file
)
1597 if (symbols_to_rename
.is_empty ())
1600 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1601 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, var
)
1603 common_info_p info
= get_common_info (var
);
1604 fprintf (file
, "CURRDEF (");
1605 print_generic_expr (file
, var
, 0);
1606 fprintf (file
, ") = ");
1607 if (info
->current_def
)
1608 print_generic_expr (file
, info
->current_def
, 0);
1610 fprintf (file
, "<NIL>");
1611 fprintf (file
, "\n");
1616 /* Dump the current reaching definition of every symbol to stderr. */
1619 debug_currdefs (void)
1621 dump_currdefs (stderr
);
1625 /* Dump SSA information to FILE. */
1628 dump_tree_ssa (FILE *file
)
1630 const char *funcname
1631 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1633 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1635 dump_var_infos (file
);
1636 dump_defs_stack (file
, -1);
1637 dump_currdefs (file
);
1638 dump_tree_ssa_stats (file
);
1642 /* Dump SSA information to stderr. */
1645 debug_tree_ssa (void)
1647 dump_tree_ssa (stderr
);
1651 /* Dump statistics for the hash table HTAB. */
1654 htab_statistics (FILE *file
, hash_table
<var_info_hasher
> htab
)
1656 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1657 (long) htab
.size (),
1658 (long) htab
.elements (),
1659 htab
.collisions ());
1663 /* Dump SSA statistics on FILE. */
1666 dump_tree_ssa_stats (FILE *file
)
1668 if (var_infos
.is_created ())
1670 fprintf (file
, "\nHash table statistics:\n");
1671 fprintf (file
, " var_infos: ");
1672 htab_statistics (file
, var_infos
);
1673 fprintf (file
, "\n");
1678 /* Dump SSA statistics on stderr. */
1681 debug_tree_ssa_stats (void)
1683 dump_tree_ssa_stats (stderr
);
1687 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1690 debug_var_infos_r (var_info_d
**slot
, FILE *file
)
1692 struct var_info_d
*info
= *slot
;
1694 fprintf (file
, "VAR: ");
1695 print_generic_expr (file
, info
->var
, dump_flags
);
1696 bitmap_print (file
, info
->info
.def_blocks
.def_blocks
,
1697 ", DEF_BLOCKS: { ", "}");
1698 bitmap_print (file
, info
->info
.def_blocks
.livein_blocks
,
1699 ", LIVEIN_BLOCKS: { ", "}");
1700 bitmap_print (file
, info
->info
.def_blocks
.phi_blocks
,
1701 ", PHI_BLOCKS: { ", "}\n");
1707 /* Dump the VAR_INFOS hash table on FILE. */
1710 dump_var_infos (FILE *file
)
1712 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1713 if (var_infos
.is_created ())
1714 var_infos
.traverse
<FILE *, debug_var_infos_r
> (file
);
1718 /* Dump the VAR_INFOS hash table on stderr. */
1721 debug_var_infos (void)
1723 dump_var_infos (stderr
);
1727 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1730 register_new_update_single (tree new_name
, tree old_name
)
1732 common_info_p info
= get_common_info (old_name
);
1733 tree currdef
= info
->current_def
;
1735 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1736 This stack is later used by the dominator tree callbacks to
1737 restore the reaching definitions for all the variables
1738 defined in the block after a recursive visit to all its
1739 immediately dominated blocks. */
1740 block_defs_stack
.reserve (2);
1741 block_defs_stack
.quick_push (currdef
);
1742 block_defs_stack
.quick_push (old_name
);
1744 /* Set the current reaching definition for OLD_NAME to be
1746 info
->current_def
= new_name
;
1750 /* Register NEW_NAME to be the new reaching definition for all the
1751 names in OLD_NAMES. Used by the incremental SSA update routines to
1752 replace old SSA names with new ones. */
1755 register_new_update_set (tree new_name
, bitmap old_names
)
1760 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1761 register_new_update_single (new_name
, ssa_name (i
));
1766 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1767 it is a symbol marked for renaming, replace it with USE_P's current
1768 reaching definition. */
1771 maybe_replace_use (use_operand_p use_p
)
1773 tree rdef
= NULL_TREE
;
1774 tree use
= USE_FROM_PTR (use_p
);
1775 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1777 if (marked_for_renaming (sym
))
1778 rdef
= get_reaching_def (sym
);
1779 else if (is_old_name (use
))
1780 rdef
= get_reaching_def (use
);
1782 if (rdef
&& rdef
!= use
)
1783 SET_USE (use_p
, rdef
);
1787 /* Same as maybe_replace_use, but without introducing default stmts,
1788 returning false to indicate a need to do so. */
1791 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1793 tree rdef
= NULL_TREE
;
1794 tree use
= USE_FROM_PTR (use_p
);
1795 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1797 if (marked_for_renaming (sym
))
1798 rdef
= get_var_info (sym
)->info
.current_def
;
1799 else if (is_old_name (use
))
1801 rdef
= get_ssa_name_ann (use
)->info
.current_def
;
1802 /* We can't assume that, if there's no current definition, the
1803 default one should be used. It could be the case that we've
1804 rearranged blocks so that the earlier definition no longer
1805 dominates the use. */
1806 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1812 if (rdef
&& rdef
!= use
)
1813 SET_USE (use_p
, rdef
);
1815 return rdef
!= NULL_TREE
;
1819 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1820 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1821 register it as the current definition for the names replaced by
1825 maybe_register_def (def_operand_p def_p
, gimple stmt
,
1826 gimple_stmt_iterator gsi
)
1828 tree def
= DEF_FROM_PTR (def_p
);
1829 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1831 /* If DEF is a naked symbol that needs renaming, create a new
1833 if (marked_for_renaming (sym
))
1839 def
= make_ssa_name (def
, stmt
);
1840 SET_DEF (def_p
, def
);
1842 tracked_var
= target_for_debug_bind (sym
);
1845 gimple note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1846 /* If stmt ends the bb, insert the debug stmt on the single
1847 non-EH edge from the stmt. */
1848 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1850 basic_block bb
= gsi_bb (gsi
);
1853 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1854 if (!(e
->flags
& EDGE_EH
))
1856 gcc_checking_assert (!ef
);
1859 /* If there are other predecessors to ef->dest, then
1860 there must be PHI nodes for the modified
1861 variable, and therefore there will be debug bind
1862 stmts after the PHI nodes. The debug bind notes
1863 we'd insert would force the creation of a new
1864 block (diverging codegen) and be redundant with
1865 the post-PHI bind stmts, so don't add them.
1867 As for the exit edge, there wouldn't be redundant
1868 bind stmts, but there wouldn't be a PC to bind
1869 them to either, so avoid diverging the CFG. */
1870 if (ef
&& single_pred_p (ef
->dest
)
1871 && ef
->dest
!= EXIT_BLOCK_PTR
)
1873 /* If there were PHI nodes in the node, we'd
1874 have to make sure the value we're binding
1875 doesn't need rewriting. But there shouldn't
1876 be PHI nodes in a single-predecessor block,
1877 so we just add the note. */
1878 gsi_insert_on_edge_immediate (ef
, note
);
1882 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1886 register_new_update_single (def
, sym
);
1890 /* If DEF is a new name, register it as a new definition
1891 for all the names replaced by DEF. */
1892 if (is_new_name (def
))
1893 register_new_update_set (def
, names_replaced_by (def
));
1895 /* If DEF is an old name, register DEF as a new
1896 definition for itself. */
1897 if (is_old_name (def
))
1898 register_new_update_single (def
, def
);
1903 /* Update every variable used in the statement pointed-to by SI. The
1904 statement is assumed to be in SSA form already. Names in
1905 OLD_SSA_NAMES used by SI will be updated to their current reaching
1906 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1907 will be registered as a new definition for their corresponding name
1908 in OLD_SSA_NAMES. */
1911 rewrite_update_stmt (gimple stmt
, gimple_stmt_iterator gsi
)
1913 use_operand_p use_p
;
1914 def_operand_p def_p
;
1917 /* Only update marked statements. */
1918 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1921 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1923 fprintf (dump_file
, "Updating SSA information for statement ");
1924 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1927 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1928 symbol is marked for renaming. */
1929 if (rewrite_uses_p (stmt
))
1931 if (is_gimple_debug (stmt
))
1933 bool failed
= false;
1935 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1936 if (!maybe_replace_use_in_debug_stmt (use_p
))
1944 /* DOM sometimes threads jumps in such a way that a
1945 debug stmt ends up referencing a SSA variable that no
1946 longer dominates the debug stmt, but such that all
1947 incoming definitions refer to the same definition in
1948 an earlier dominator. We could try to recover that
1949 definition somehow, but this will have to do for now.
1951 Introducing a default definition, which is what
1952 maybe_replace_use() would do in such cases, may
1953 modify code generation, for the otherwise-unused
1954 default definition would never go away, modifying SSA
1955 version numbers all over. */
1956 gimple_debug_bind_reset_value (stmt
);
1962 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1963 maybe_replace_use (use_p
);
1967 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1968 Also register definitions for names whose underlying symbol is
1969 marked for renaming. */
1970 if (register_defs_p (stmt
))
1971 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1972 maybe_register_def (def_p
, stmt
, gsi
);
1976 /* Visit all the successor blocks of BB looking for PHI nodes. For
1977 every PHI node found, check if any of its arguments is in
1978 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1979 definition, replace it. */
1982 rewrite_update_phi_arguments (basic_block bb
)
1988 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1993 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
1996 phis
= phis_to_rewrite
[e
->dest
->index
];
1997 FOR_EACH_VEC_ELT (phis
, i
, phi
)
1999 tree arg
, lhs_sym
, reaching_def
= NULL
;
2000 use_operand_p arg_p
;
2002 gcc_checking_assert (rewrite_uses_p (phi
));
2004 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
2005 arg
= USE_FROM_PTR (arg_p
);
2007 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
2010 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2012 if (arg
== NULL_TREE
)
2014 /* When updating a PHI node for a recently introduced
2015 symbol we may find NULL arguments. That's why we
2016 take the symbol from the LHS of the PHI node. */
2017 reaching_def
= get_reaching_def (lhs_sym
);
2022 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2024 if (marked_for_renaming (sym
))
2025 reaching_def
= get_reaching_def (sym
);
2026 else if (is_old_name (arg
))
2027 reaching_def
= get_reaching_def (arg
);
2030 /* Update the argument if there is a reaching def. */
2033 source_location locus
;
2034 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2036 SET_USE (arg_p
, reaching_def
);
2038 /* Virtual operands do not need a location. */
2039 if (virtual_operand_p (reaching_def
))
2040 locus
= UNKNOWN_LOCATION
;
2043 gimple stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2045 /* Single element PHI nodes behave like copies, so get the
2046 location from the phi argument. */
2047 if (gimple_code (stmt
) == GIMPLE_PHI
2048 && gimple_phi_num_args (stmt
) == 1)
2049 locus
= gimple_phi_arg_location (stmt
, 0);
2051 locus
= gimple_location (stmt
);
2054 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2058 if (e
->flags
& EDGE_ABNORMAL
)
2059 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2064 class rewrite_update_dom_walker
: public dom_walker
2067 rewrite_update_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2069 virtual void before_dom_children (basic_block
);
2070 virtual void after_dom_children (basic_block
);
2073 /* Initialization of block data structures for the incremental SSA
2074 update pass. Create a block local stack of reaching definitions
2075 for new SSA names produced in this block (BLOCK_DEFS). Register
2076 new definitions for every PHI node in the block. */
2079 rewrite_update_dom_walker::before_dom_children (basic_block bb
)
2081 bool is_abnormal_phi
;
2082 gimple_stmt_iterator gsi
;
2084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2085 fprintf (dump_file
, "Registering new PHI nodes in block #%d\n",
2088 /* Mark the unwind point for this block. */
2089 block_defs_stack
.safe_push (NULL_TREE
);
2091 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2094 /* Mark the LHS if any of the arguments flows through an abnormal
2096 is_abnormal_phi
= bb_has_abnormal_pred (bb
);
2098 /* If any of the PHI nodes is a replacement for a name in
2099 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2100 register it as a new definition for its corresponding name. Also
2101 register definitions for names whose underlying symbols are
2102 marked for renaming. */
2103 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2106 gimple phi
= gsi_stmt (gsi
);
2108 if (!register_defs_p (phi
))
2111 lhs
= gimple_phi_result (phi
);
2112 lhs_sym
= SSA_NAME_VAR (lhs
);
2114 if (marked_for_renaming (lhs_sym
))
2115 register_new_update_single (lhs
, lhs_sym
);
2119 /* If LHS is a new name, register a new definition for all
2120 the names replaced by LHS. */
2121 if (is_new_name (lhs
))
2122 register_new_update_set (lhs
, names_replaced_by (lhs
));
2124 /* If LHS is an OLD name, register it as a new definition
2126 if (is_old_name (lhs
))
2127 register_new_update_single (lhs
, lhs
);
2130 if (is_abnormal_phi
)
2131 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2134 /* Step 2. Rewrite every variable used in each statement in the block. */
2135 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
2137 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2138 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2139 rewrite_update_stmt (gsi_stmt (gsi
), gsi
);
2142 /* Step 3. Update PHI nodes. */
2143 rewrite_update_phi_arguments (bb
);
2146 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2147 the current reaching definition of every name re-written in BB to
2148 the original reaching definition before visiting BB. This
2149 unwinding must be done in the opposite order to what is done in
2150 register_new_update_set. */
2153 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
2155 while (block_defs_stack
.length () > 0)
2157 tree var
= block_defs_stack
.pop ();
2160 /* NULL indicates the unwind stop point for this block (see
2161 rewrite_update_enter_block). */
2165 saved_def
= block_defs_stack
.pop ();
2166 get_common_info (var
)->current_def
= saved_def
;
2171 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2174 ENTRY indicates the block where to start. Every block dominated by
2175 ENTRY will be rewritten.
2177 WHAT indicates what actions will be taken by the renamer (see enum
2180 BLOCKS are the set of interesting blocks for the dominator walker
2181 to process. If this set is NULL, then all the nodes dominated
2182 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2183 are not present in BLOCKS are ignored. */
2186 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2188 /* Rewrite all the basic blocks in the program. */
2189 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2191 block_defs_stack
.create (10);
2193 /* Recursively walk the dominator tree rewriting each statement in
2194 each basic block. */
2195 if (what
== REWRITE_ALL
)
2196 rewrite_dom_walker (CDI_DOMINATORS
).walk (entry
);
2197 else if (what
== REWRITE_UPDATE
)
2198 rewrite_update_dom_walker (CDI_DOMINATORS
).walk (entry
);
2202 /* Debugging dumps. */
2203 if (dump_file
&& (dump_flags
& TDF_STATS
))
2205 dump_dfa_stats (dump_file
);
2206 if (var_infos
.is_created ())
2207 dump_tree_ssa_stats (dump_file
);
2210 block_defs_stack
.release ();
2212 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2215 class mark_def_dom_walker
: public dom_walker
2218 mark_def_dom_walker (cdi_direction direction
);
2219 ~mark_def_dom_walker ();
2221 virtual void before_dom_children (basic_block
);
2224 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2225 large enough to accommodate all the variables referenced in the
2226 function, not just the ones we are renaming. */
2230 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction
)
2231 : dom_walker (direction
), m_kills (BITMAP_ALLOC (NULL
))
2235 mark_def_dom_walker::~mark_def_dom_walker ()
2237 BITMAP_FREE (m_kills
);
2240 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2241 at the start of each block, and call mark_def_sites for each statement. */
2244 mark_def_dom_walker::before_dom_children (basic_block bb
)
2246 gimple_stmt_iterator gsi
;
2248 bitmap_clear (m_kills
);
2249 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2250 mark_def_sites (bb
, gsi_stmt (gsi
), m_kills
);
2253 /* Initialize internal data needed during renaming. */
2256 init_ssa_renamer (void)
2258 cfun
->gimple_df
->in_ssa_p
= false;
2260 /* Allocate memory for the DEF_BLOCKS hash table. */
2261 gcc_assert (!var_infos
.is_created ());
2262 var_infos
.create (vec_safe_length (cfun
->local_decls
));
2264 bitmap_obstack_initialize (&update_ssa_obstack
);
2268 /* Deallocate internal data structures used by the renamer. */
2271 fini_ssa_renamer (void)
2273 if (var_infos
.is_created ())
2274 var_infos
.dispose ();
2276 bitmap_obstack_release (&update_ssa_obstack
);
2278 cfun
->gimple_df
->ssa_renaming_needed
= 0;
2279 cfun
->gimple_df
->rename_vops
= 0;
2280 cfun
->gimple_df
->in_ssa_p
= true;
2283 /* Main entry point into the SSA builder. The renaming process
2284 proceeds in four main phases:
2286 1- Compute dominance frontier and immediate dominators, needed to
2287 insert PHI nodes and rename the function in dominator tree
2290 2- Find and mark all the blocks that define variables.
2292 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2294 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2296 Steps 3 and 4 are done using the dominator tree walker
2297 (walk_dominator_tree). */
2300 rewrite_into_ssa (void)
2306 /* Initialize operand data structures. */
2307 init_ssa_operands (cfun
);
2309 /* Initialize internal data needed by the renamer. */
2310 init_ssa_renamer ();
2312 /* Initialize the set of interesting blocks. The callback
2313 mark_def_sites will add to this set those blocks that the renamer
2315 interesting_blocks
= sbitmap_alloc (last_basic_block
);
2316 bitmap_clear (interesting_blocks
);
2318 /* Initialize dominance frontier. */
2319 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
2321 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
2323 /* 1- Compute dominance frontiers. */
2324 calculate_dominance_info (CDI_DOMINATORS
);
2325 compute_dominance_frontiers (dfs
);
2327 /* 2- Find and mark definition sites. */
2328 mark_def_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
2330 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2331 insert_phi_nodes (dfs
);
2333 /* 4- Rename all the blocks. */
2334 rewrite_blocks (ENTRY_BLOCK_PTR
, REWRITE_ALL
);
2336 /* Free allocated memory. */
2338 bitmap_clear (&dfs
[bb
->index
]);
2341 sbitmap_free (interesting_blocks
);
2343 fini_ssa_renamer ();
2345 /* Try to get rid of all gimplifier generated temporaries by making
2346 its SSA names anonymous. This way we can garbage collect them
2347 all after removing unused locals which we do in our TODO. */
2348 for (i
= 1; i
< num_ssa_names
; ++i
)
2350 tree decl
, name
= ssa_name (i
);
2352 || SSA_NAME_IS_DEFAULT_DEF (name
))
2354 decl
= SSA_NAME_VAR (name
);
2356 && TREE_CODE (decl
) == VAR_DECL
2357 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl
)
2358 && DECL_IGNORED_P (decl
))
2359 SET_SSA_NAME_VAR_OR_IDENTIFIER (name
, DECL_NAME (decl
));
2365 /* Gate for IPCP optimization. */
2368 gate_into_ssa (void)
2370 /* Do nothing for funcions that was produced already in SSA form. */
2371 return !(cfun
->curr_properties
& PROP_ssa
);
2376 const pass_data pass_data_build_ssa
=
2378 GIMPLE_PASS
, /* type */
2380 OPTGROUP_NONE
, /* optinfo_flags */
2381 true, /* has_gate */
2382 true, /* has_execute */
2383 TV_TREE_SSA_OTHER
, /* tv_id */
2384 PROP_cfg
, /* properties_required */
2385 PROP_ssa
, /* properties_provided */
2386 0, /* properties_destroyed */
2387 0, /* todo_flags_start */
2388 ( TODO_verify_ssa
| TODO_remove_unused_locals
), /* todo_flags_finish */
2391 class pass_build_ssa
: public gimple_opt_pass
2394 pass_build_ssa (gcc::context
*ctxt
)
2395 : gimple_opt_pass (pass_data_build_ssa
, ctxt
)
2398 /* opt_pass methods: */
2399 bool gate () { return gate_into_ssa (); }
2400 unsigned int execute () { return rewrite_into_ssa (); }
2402 }; // class pass_build_ssa
2407 make_pass_build_ssa (gcc::context
*ctxt
)
2409 return new pass_build_ssa (ctxt
);
2413 /* Mark the definition of VAR at STMT and BB as interesting for the
2414 renamer. BLOCKS is the set of blocks that need updating. */
2417 mark_def_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2419 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2420 set_register_defs (stmt
, true);
2424 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2426 set_def_block (var
, bb
, is_phi_p
);
2428 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2429 site for both itself and all the old names replaced by it. */
2430 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2434 bitmap set
= names_replaced_by (var
);
2436 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2437 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2443 /* Mark the use of VAR at STMT and BB as interesting for the
2444 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2448 mark_use_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2450 basic_block def_bb
= gimple_bb (stmt
);
2452 mark_block_for_update (def_bb
);
2453 mark_block_for_update (bb
);
2455 if (gimple_code (stmt
) == GIMPLE_PHI
)
2456 mark_phi_for_rewrite (def_bb
, stmt
);
2459 set_rewrite_uses (stmt
, true);
2461 if (is_gimple_debug (stmt
))
2465 /* If VAR has not been defined in BB, then it is live-on-entry
2466 to BB. Note that we cannot just use the block holding VAR's
2467 definition because if VAR is one of the names in OLD_SSA_NAMES,
2468 it will have several definitions (itself and all the names that
2472 struct def_blocks_d
*db_p
= get_def_blocks_for (get_common_info (var
));
2473 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2474 set_livein_block (var
, bb
);
2479 /* Do a dominator walk starting at BB processing statements that
2480 reference symbols in SSA operands. This is very similar to
2481 mark_def_sites, but the scan handles statements whose operands may
2482 already be SSA names.
2484 If INSERT_PHI_P is true, mark those uses as live in the
2485 corresponding block. This is later used by the PHI placement
2486 algorithm to make PHI pruning decisions.
2488 FIXME. Most of this would be unnecessary if we could associate a
2489 symbol to all the SSA names that reference it. But that
2490 sounds like it would be expensive to maintain. Still, it
2491 would be interesting to see if it makes better sense to do
2495 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2498 gimple_stmt_iterator si
;
2502 mark_block_for_update (bb
);
2504 /* Process PHI nodes marking interesting those that define or use
2505 the symbols that we are interested in. */
2506 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
2508 gimple phi
= gsi_stmt (si
);
2509 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2511 if (TREE_CODE (lhs
) == SSA_NAME
2512 && (! virtual_operand_p (lhs
)
2513 || ! cfun
->gimple_df
->rename_vops
))
2516 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2517 mark_for_renaming (lhs_sym
);
2518 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2520 /* Mark the uses in phi nodes as interesting. It would be more correct
2521 to process the arguments of the phi nodes of the successor edges of
2522 BB at the end of prepare_block_for_update, however, that turns out
2523 to be significantly more expensive. Doing it here is conservatively
2524 correct -- it may only cause us to believe a value to be live in a
2525 block that also contains its definition, and thus insert a few more
2526 phi nodes for it. */
2527 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2528 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2531 /* Process the statements. */
2532 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2536 use_operand_p use_p
;
2537 def_operand_p def_p
;
2539 stmt
= gsi_stmt (si
);
2541 if (cfun
->gimple_df
->rename_vops
2542 && gimple_vuse (stmt
))
2544 tree use
= gimple_vuse (stmt
);
2545 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2546 mark_for_renaming (sym
);
2547 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2550 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_USE
)
2552 tree use
= USE_FROM_PTR (use_p
);
2555 mark_for_renaming (use
);
2556 mark_use_interesting (use
, stmt
, bb
, insert_phi_p
);
2559 if (cfun
->gimple_df
->rename_vops
2560 && gimple_vdef (stmt
))
2562 tree def
= gimple_vdef (stmt
);
2563 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2564 mark_for_renaming (sym
);
2565 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2568 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_DEF
)
2570 tree def
= DEF_FROM_PTR (def_p
);
2573 mark_for_renaming (def
);
2574 mark_def_interesting (def
, stmt
, bb
, insert_phi_p
);
2578 /* Now visit all the blocks dominated by BB. */
2579 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2581 son
= next_dom_son (CDI_DOMINATORS
, son
))
2582 prepare_block_for_update (son
, insert_phi_p
);
2586 /* Helper for prepare_names_to_update. Mark all the use sites for
2587 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2588 prepare_names_to_update. */
2591 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2593 use_operand_p use_p
;
2594 imm_use_iterator iter
;
2596 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2598 gimple stmt
= USE_STMT (use_p
);
2599 basic_block bb
= gimple_bb (stmt
);
2601 if (gimple_code (stmt
) == GIMPLE_PHI
)
2603 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2604 edge e
= gimple_phi_arg_edge (stmt
, ix
);
2605 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2609 /* For regular statements, mark this as an interesting use
2611 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2617 /* Helper for prepare_names_to_update. Mark the definition site for
2618 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2619 prepare_names_to_update. */
2622 prepare_def_site_for (tree name
, bool insert_phi_p
)
2627 gcc_checking_assert (names_to_release
== NULL
2628 || !bitmap_bit_p (names_to_release
,
2629 SSA_NAME_VERSION (name
)));
2631 stmt
= SSA_NAME_DEF_STMT (name
);
2632 bb
= gimple_bb (stmt
);
2635 gcc_checking_assert (bb
->index
< last_basic_block
);
2636 mark_block_for_update (bb
);
2637 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2642 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2643 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2644 PHI nodes for newly created names. */
2647 prepare_names_to_update (bool insert_phi_p
)
2651 sbitmap_iterator sbi
;
2653 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2654 remove it from NEW_SSA_NAMES so that we don't try to visit its
2655 defining basic block (which most likely doesn't exist). Notice
2656 that we cannot do the same with names in OLD_SSA_NAMES because we
2657 want to replace existing instances. */
2658 if (names_to_release
)
2659 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2660 bitmap_clear_bit (new_ssa_names
, i
);
2662 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2663 names may be considered to be live-in on blocks that contain
2664 definitions for their replacements. */
2665 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2666 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2668 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2669 OLD_SSA_NAMES, but we have to ignore its definition site. */
2670 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
2672 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2673 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2674 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2679 /* Dump all the names replaced by NAME to FILE. */
2682 dump_names_replaced_by (FILE *file
, tree name
)
2688 print_generic_expr (file
, name
, 0);
2689 fprintf (file
, " -> { ");
2691 old_set
= names_replaced_by (name
);
2692 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2694 print_generic_expr (file
, ssa_name (i
), 0);
2695 fprintf (file
, " ");
2698 fprintf (file
, "}\n");
2702 /* Dump all the names replaced by NAME to stderr. */
2705 debug_names_replaced_by (tree name
)
2707 dump_names_replaced_by (stderr
, name
);
2711 /* Dump SSA update information to FILE. */
2714 dump_update_ssa (FILE *file
)
2719 if (!need_ssa_update_p (cfun
))
2722 if (new_ssa_names
&& bitmap_first_set_bit (new_ssa_names
) >= 0)
2724 sbitmap_iterator sbi
;
2726 fprintf (file
, "\nSSA replacement table\n");
2727 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2728 "O_1, ..., O_j\n\n");
2730 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2731 dump_names_replaced_by (file
, ssa_name (i
));
2734 if (symbols_to_rename_set
&& !bitmap_empty_p (symbols_to_rename_set
))
2736 fprintf (file
, "\nSymbols to be put in SSA form\n");
2737 dump_decl_set (file
, symbols_to_rename_set
);
2738 fprintf (file
, "\n");
2741 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2743 fprintf (file
, "\nSSA names to release after updating the SSA web\n\n");
2744 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2746 print_generic_expr (file
, ssa_name (i
), 0);
2747 fprintf (file
, " ");
2749 fprintf (file
, "\n");
2754 /* Dump SSA update information to stderr. */
2757 debug_update_ssa (void)
2759 dump_update_ssa (stderr
);
2763 /* Initialize data structures used for incremental SSA updates. */
2766 init_update_ssa (struct function
*fn
)
2768 /* Reserve more space than the current number of names. The calls to
2769 add_new_name_mapping are typically done after creating new SSA
2770 names, so we'll need to reallocate these arrays. */
2771 old_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2772 bitmap_clear (old_ssa_names
);
2774 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2775 bitmap_clear (new_ssa_names
);
2777 bitmap_obstack_initialize (&update_ssa_obstack
);
2779 names_to_release
= NULL
;
2780 update_ssa_initialized_fn
= fn
;
2784 /* Deallocate data structures used for incremental SSA updates. */
2787 delete_update_ssa (void)
2792 sbitmap_free (old_ssa_names
);
2793 old_ssa_names
= NULL
;
2795 sbitmap_free (new_ssa_names
);
2796 new_ssa_names
= NULL
;
2798 BITMAP_FREE (symbols_to_rename_set
);
2799 symbols_to_rename_set
= NULL
;
2800 symbols_to_rename
.release ();
2802 if (names_to_release
)
2804 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2805 release_ssa_name (ssa_name (i
));
2806 BITMAP_FREE (names_to_release
);
2809 clear_ssa_name_info ();
2811 fini_ssa_renamer ();
2813 if (blocks_with_phis_to_rewrite
)
2814 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2816 gimple_vec phis
= phis_to_rewrite
[i
];
2818 phis_to_rewrite
[i
].create (0);
2821 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2822 BITMAP_FREE (blocks_to_update
);
2824 update_ssa_initialized_fn
= NULL
;
2828 /* Create a new name for OLD_NAME in statement STMT and replace the
2829 operand pointed to by DEF_P with the newly created name. If DEF_P
2830 is NULL then STMT should be a GIMPLE assignment.
2831 Return the new name and register the replacement mapping <NEW, OLD> in
2832 update_ssa's tables. */
2835 create_new_def_for (tree old_name
, gimple stmt
, def_operand_p def
)
2839 timevar_push (TV_TREE_SSA_INCREMENTAL
);
2841 if (!update_ssa_initialized_fn
)
2842 init_update_ssa (cfun
);
2844 gcc_assert (update_ssa_initialized_fn
== cfun
);
2846 new_name
= duplicate_ssa_name (old_name
, stmt
);
2848 SET_DEF (def
, new_name
);
2850 gimple_assign_set_lhs (stmt
, new_name
);
2852 if (gimple_code (stmt
) == GIMPLE_PHI
)
2854 basic_block bb
= gimple_bb (stmt
);
2856 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2857 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = bb_has_abnormal_pred (bb
);
2860 add_new_name_mapping (new_name
, old_name
);
2862 /* For the benefit of passes that will be updating the SSA form on
2863 their own, set the current reaching definition of OLD_NAME to be
2865 get_ssa_name_ann (old_name
)->info
.current_def
= new_name
;
2867 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
2873 /* Mark virtual operands of FN for renaming by update_ssa. */
2876 mark_virtual_operands_for_renaming (struct function
*fn
)
2878 fn
->gimple_df
->ssa_renaming_needed
= 1;
2879 fn
->gimple_df
->rename_vops
= 1;
2882 /* Replace all uses of NAME by underlying variable and mark it
2883 for renaming. This assumes the defining statement of NAME is
2884 going to be removed. */
2887 mark_virtual_operand_for_renaming (tree name
)
2889 tree name_var
= SSA_NAME_VAR (name
);
2891 imm_use_iterator iter
;
2892 use_operand_p use_p
;
2895 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var
));
2896 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
2898 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2899 SET_USE (use_p
, name_var
);
2903 mark_virtual_operands_for_renaming (cfun
);
2906 /* Replace all uses of the virtual PHI result by its underlying variable
2907 and mark it for renaming. This assumes the PHI node is going to be
2911 mark_virtual_phi_result_for_renaming (gimple phi
)
2913 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2915 fprintf (dump_file
, "Marking result for renaming : ");
2916 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
2917 fprintf (dump_file
, "\n");
2920 mark_virtual_operand_for_renaming (gimple_phi_result (phi
));
2923 /* Return true if there is any work to be done by update_ssa
2927 need_ssa_update_p (struct function
*fn
)
2929 gcc_assert (fn
!= NULL
);
2930 return (update_ssa_initialized_fn
== fn
2931 || (fn
->gimple_df
&& fn
->gimple_df
->ssa_renaming_needed
));
2934 /* Return true if name N has been registered in the replacement table. */
2937 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
2939 if (!update_ssa_initialized_fn
)
2942 gcc_assert (update_ssa_initialized_fn
== cfun
);
2944 return is_new_name (n
) || is_old_name (n
);
2948 /* Mark NAME to be released after update_ssa has finished. */
2951 release_ssa_name_after_update_ssa (tree name
)
2953 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
2955 if (names_to_release
== NULL
)
2956 names_to_release
= BITMAP_ALLOC (NULL
);
2958 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
2962 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2963 frontier information. BLOCKS is the set of blocks to be updated.
2965 This is slightly different than the regular PHI insertion
2966 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2967 real names (i.e., GIMPLE registers) are inserted:
2969 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2970 nodes inside the region affected by the block that defines VAR
2971 and the blocks that define all its replacements. All these
2972 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2974 First, we compute the entry point to the region (ENTRY). This is
2975 given by the nearest common dominator to all the definition
2976 blocks. When computing the iterated dominance frontier (IDF), any
2977 block not strictly dominated by ENTRY is ignored.
2979 We then call the standard PHI insertion algorithm with the pruned
2982 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2983 names is not pruned. PHI nodes are inserted at every IDF block. */
2986 insert_updated_phi_nodes_for (tree var
, bitmap_head
*dfs
, bitmap blocks
,
2987 unsigned update_flags
)
2990 struct def_blocks_d
*db
;
2991 bitmap idf
, pruned_idf
;
2995 if (TREE_CODE (var
) == SSA_NAME
)
2996 gcc_checking_assert (is_old_name (var
));
2998 gcc_checking_assert (marked_for_renaming (var
));
3000 /* Get all the definition sites for VAR. */
3001 db
= find_def_blocks_for (var
);
3003 /* No need to do anything if there were no definitions to VAR. */
3004 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
3007 /* Compute the initial iterated dominance frontier. */
3008 idf
= compute_idf (db
->def_blocks
, dfs
);
3009 pruned_idf
= BITMAP_ALLOC (NULL
);
3011 if (TREE_CODE (var
) == SSA_NAME
)
3013 if (update_flags
== TODO_update_ssa
)
3015 /* If doing regular SSA updates for GIMPLE registers, we are
3016 only interested in IDF blocks dominated by the nearest
3017 common dominator of all the definition blocks. */
3018 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3020 if (entry
!= ENTRY_BLOCK_PTR
)
3021 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
3022 if (BASIC_BLOCK (i
) != entry
3023 && dominated_by_p (CDI_DOMINATORS
, BASIC_BLOCK (i
), entry
))
3024 bitmap_set_bit (pruned_idf
, i
);
3028 /* Otherwise, do not prune the IDF for VAR. */
3029 gcc_checking_assert (update_flags
== TODO_update_ssa_full_phi
);
3030 bitmap_copy (pruned_idf
, idf
);
3035 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3036 for the first time, so we need to compute the full IDF for
3038 bitmap_copy (pruned_idf
, idf
);
3041 if (!bitmap_empty_p (pruned_idf
))
3043 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3044 are included in the region to be updated. The feeding blocks
3045 are important to guarantee that the PHI arguments are renamed
3048 /* FIXME, this is not needed if we are updating symbols. We are
3049 already starting at the ENTRY block anyway. */
3050 bitmap_ior_into (blocks
, pruned_idf
);
3051 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3055 basic_block bb
= BASIC_BLOCK (i
);
3057 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3058 if (e
->src
->index
>= 0)
3059 bitmap_set_bit (blocks
, e
->src
->index
);
3062 insert_phi_nodes_for (var
, pruned_idf
, true);
3065 BITMAP_FREE (pruned_idf
);
3069 /* Sort symbols_to_rename after their DECL_UID. */
3072 insert_updated_phi_nodes_compare_uids (const void *a
, const void *b
)
3074 const_tree syma
= *(const const_tree
*)a
;
3075 const_tree symb
= *(const const_tree
*)b
;
3076 if (DECL_UID (syma
) == DECL_UID (symb
))
3078 return DECL_UID (syma
) < DECL_UID (symb
) ? -1 : 1;
3081 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3082 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3084 1- The names in OLD_SSA_NAMES dominated by the definitions of
3085 NEW_SSA_NAMES are all re-written to be reached by the
3086 appropriate definition from NEW_SSA_NAMES.
3088 2- If needed, new PHI nodes are added to the iterated dominance
3089 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3091 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3092 calling create_new_def_for to create new defs for names that the
3093 caller wants to replace.
3095 The caller cretaes the new names to be inserted and the names that need
3096 to be replaced by calling create_new_def_for for each old definition
3097 to be replaced. Note that the function assumes that the
3098 new defining statement has already been inserted in the IL.
3100 For instance, given the following code:
3103 2 x_1 = PHI (0, x_5)
3114 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3117 2 x_1 = PHI (0, x_5)
3130 We want to replace all the uses of x_1 with the new definitions of
3131 x_10 and x_11. Note that the only uses that should be replaced are
3132 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3133 *not* be replaced (this is why we cannot just mark symbol 'x' for
3136 Additionally, we may need to insert a PHI node at line 11 because
3137 that is a merge point for x_10 and x_11. So the use of x_1 at line
3138 11 will be replaced with the new PHI node. The insertion of PHI
3139 nodes is optional. They are not strictly necessary to preserve the
3140 SSA form, and depending on what the caller inserted, they may not
3141 even be useful for the optimizers. UPDATE_FLAGS controls various
3142 aspects of how update_ssa operates, see the documentation for
3143 TODO_update_ssa*. */
3146 update_ssa (unsigned update_flags
)
3148 basic_block bb
, start_bb
;
3152 sbitmap_iterator sbi
;
3155 /* Only one update flag should be set. */
3156 gcc_assert (update_flags
== TODO_update_ssa
3157 || update_flags
== TODO_update_ssa_no_phi
3158 || update_flags
== TODO_update_ssa_full_phi
3159 || update_flags
== TODO_update_ssa_only_virtuals
);
3161 if (!need_ssa_update_p (cfun
))
3164 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3166 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3167 fprintf (dump_file
, "\nUpdating SSA:\n");
3169 if (!update_ssa_initialized_fn
)
3170 init_update_ssa (cfun
);
3171 else if (update_flags
== TODO_update_ssa_only_virtuals
)
3173 /* If we only need to update virtuals, remove all the mappings for
3174 real names before proceeding. The caller is responsible for
3175 having dealt with the name mappings before calling update_ssa. */
3176 bitmap_clear (old_ssa_names
);
3177 bitmap_clear (new_ssa_names
);
3180 gcc_assert (update_ssa_initialized_fn
== cfun
);
3182 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3183 if (!phis_to_rewrite
.exists ())
3184 phis_to_rewrite
.create (last_basic_block
+ 1);
3185 blocks_to_update
= BITMAP_ALLOC (NULL
);
3187 /* Ensure that the dominance information is up-to-date. */
3188 calculate_dominance_info (CDI_DOMINATORS
);
3190 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3192 /* If there are names defined in the replacement table, prepare
3193 definition and use sites for all the names in NEW_SSA_NAMES and
3195 if (bitmap_first_set_bit (new_ssa_names
) >= 0)
3197 prepare_names_to_update (insert_phi_p
);
3199 /* If all the names in NEW_SSA_NAMES had been marked for
3200 removal, and there are no symbols to rename, then there's
3201 nothing else to do. */
3202 if (bitmap_first_set_bit (new_ssa_names
) < 0
3203 && !cfun
->gimple_df
->ssa_renaming_needed
)
3207 /* Next, determine the block at which to start the renaming process. */
3208 if (cfun
->gimple_df
->ssa_renaming_needed
)
3210 /* If we rename bare symbols initialize the mapping to
3211 auxiliar info we need to keep track of. */
3212 var_infos
.create (47);
3214 /* If we have to rename some symbols from scratch, we need to
3215 start the process at the root of the CFG. FIXME, it should
3216 be possible to determine the nearest block that had a
3217 definition for each of the symbols that are marked for
3218 updating. For now this seems more work than it's worth. */
3219 start_bb
= ENTRY_BLOCK_PTR
;
3221 /* Traverse the CFG looking for existing definitions and uses of
3222 symbols in SSA operands. Mark interesting blocks and
3223 statements and set local live-in information for the PHI
3224 placement heuristics. */
3225 prepare_block_for_update (start_bb
, insert_phi_p
);
3227 #ifdef ENABLE_CHECKING
3228 for (i
= 1; i
< num_ssa_names
; ++i
)
3230 tree name
= ssa_name (i
);
3232 || virtual_operand_p (name
))
3235 /* For all but virtual operands, which do not have SSA names
3236 with overlapping life ranges, ensure that symbols marked
3237 for renaming do not have existing SSA names associated with
3238 them as we do not re-write them out-of-SSA before going
3239 into SSA for the remaining symbol uses. */
3240 if (marked_for_renaming (SSA_NAME_VAR (name
)))
3242 fprintf (stderr
, "Existing SSA name for symbol marked for "
3244 print_generic_expr (stderr
, name
, TDF_SLIM
);
3245 fprintf (stderr
, "\n");
3246 internal_error ("SSA corruption");
3253 /* Otherwise, the entry block to the region is the nearest
3254 common dominator for the blocks in BLOCKS. */
3255 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3259 /* If requested, insert PHI nodes at the iterated dominance frontier
3260 of every block, creating new definitions for names in OLD_SSA_NAMES
3261 and for symbols found. */
3266 /* If the caller requested PHI nodes to be added, compute
3267 dominance frontiers. */
3268 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
3270 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
3271 compute_dominance_frontiers (dfs
);
3273 if (bitmap_first_set_bit (old_ssa_names
) >= 0)
3275 sbitmap_iterator sbi
;
3277 /* insert_update_phi_nodes_for will call add_new_name_mapping
3278 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3279 will grow while we are traversing it (but it will not
3280 gain any new members). Copy OLD_SSA_NAMES to a temporary
3282 sbitmap tmp
= sbitmap_alloc (SBITMAP_SIZE (old_ssa_names
));
3283 bitmap_copy (tmp
, old_ssa_names
);
3284 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, sbi
)
3285 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3290 symbols_to_rename
.qsort (insert_updated_phi_nodes_compare_uids
);
3291 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3292 insert_updated_phi_nodes_for (sym
, dfs
, blocks_to_update
,
3296 bitmap_clear (&dfs
[bb
->index
]);
3299 /* Insertion of PHI nodes may have added blocks to the region.
3300 We need to re-compute START_BB to include the newly added
3302 if (start_bb
!= ENTRY_BLOCK_PTR
)
3303 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3307 /* Reset the current definition for name and symbol before renaming
3309 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
3310 get_ssa_name_ann (ssa_name (i
))->info
.current_def
= NULL_TREE
;
3312 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3313 get_var_info (sym
)->info
.current_def
= NULL_TREE
;
3315 /* Now start the renaming process at START_BB. */
3316 interesting_blocks
= sbitmap_alloc (last_basic_block
);
3317 bitmap_clear (interesting_blocks
);
3318 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3319 bitmap_set_bit (interesting_blocks
, i
);
3321 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3323 sbitmap_free (interesting_blocks
);
3325 /* Debugging dumps. */
3331 dump_update_ssa (dump_file
);
3333 fprintf (dump_file
, "Incremental SSA update started at block: %d\n",
3337 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3339 fprintf (dump_file
, "Number of blocks in CFG: %d\n", last_basic_block
);
3340 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n",
3341 c
, PERCENT (c
, last_basic_block
));
3343 if (dump_flags
& TDF_DETAILS
)
3345 fprintf (dump_file
, "Affected blocks:");
3346 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3347 fprintf (dump_file
, " %u", i
);
3348 fprintf (dump_file
, "\n");
3351 fprintf (dump_file
, "\n\n");
3354 /* Free allocated memory. */
3356 delete_update_ssa ();
3358 timevar_pop (TV_TREE_SSA_INCREMENTAL
);