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"
35 #include "tree-inline.h"
36 #include "hash-table.h"
37 #include "tree-pass.h"
41 #include "diagnostic-core.h"
44 /* This file builds the SSA form for a function as described in:
45 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
46 Computing Static Single Assignment Form and the Control Dependence
47 Graph. ACM Transactions on Programming Languages and Systems,
48 13(4):451-490, October 1991. */
50 /* Structure to map a variable VAR to the set of blocks that contain
51 definitions for VAR. */
54 /* Blocks that contain definitions of VAR. Bit I will be set if the
55 Ith block contains a definition of VAR. */
58 /* Blocks that contain a PHI node for VAR. */
61 /* Blocks where VAR is live-on-entry. Similar semantics as
66 typedef struct def_blocks_d
*def_blocks_p
;
69 /* Stack of trees used to restore the global currdefs to its original
70 state after completing rewriting of a block and its dominator
71 children. Its elements have the following properties:
73 - An SSA_NAME (N) indicates that the current definition of the
74 underlying variable should be set to the given SSA_NAME. If the
75 symbol associated with the SSA_NAME is not a GIMPLE register, the
76 next slot in the stack must be a _DECL node (SYM). In this case,
77 the name N in the previous slot is the current reaching
80 - A _DECL node indicates that the underlying variable has no
83 - A NULL node at the top entry is used to mark the last slot
84 associated with the current block. */
85 static vec
<tree
> block_defs_stack
;
88 /* Set of existing SSA names being replaced by update_ssa. */
89 static sbitmap old_ssa_names
;
91 /* Set of new SSA names being added by update_ssa. Note that both
92 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
93 the operations done on them are presence tests. */
94 static sbitmap new_ssa_names
;
96 static sbitmap interesting_blocks
;
98 /* Set of SSA names that have been marked to be released after they
99 were registered in the replacement table. They will be finally
100 released after we finish updating the SSA web. */
101 static bitmap names_to_release
;
103 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
104 the to basic block with index I. Allocated once per compilation, *not*
105 released between different functions. */
106 static vec
<gimple_vec
> phis_to_rewrite
;
108 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
109 static bitmap blocks_with_phis_to_rewrite
;
111 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
112 to grow as the callers to create_new_def_for will create new names on
114 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
115 need to find a reasonable growth strategy. */
116 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
119 /* The function the SSA updating data structures have been initialized for.
120 NULL if they need to be initialized by create_new_def_for. */
121 static struct function
*update_ssa_initialized_fn
= NULL
;
123 /* Global data to attach to the main dominator walk structure. */
124 struct mark_def_sites_global_data
126 /* This bitmap contains the variables which are set before they
127 are used in a basic block. */
131 /* Information stored for both SSA names and decls. */
134 /* This field indicates whether or not the variable may need PHI nodes.
135 See the enum's definition for more detailed information about the
137 ENUM_BITFIELD (need_phi_state
) need_phi_state
: 2;
139 /* The current reaching definition replacing this var. */
142 /* Definitions for this var. */
143 struct def_blocks_d def_blocks
;
146 /* The information associated with decls and SSA names. */
147 typedef struct common_info_d
*common_info_p
;
149 /* Information stored for decls. */
155 /* Information stored for both SSA names and decls. */
156 struct common_info_d info
;
159 /* The information associated with decls. */
160 typedef struct var_info_d
*var_info_p
;
163 /* VAR_INFOS hashtable helpers. */
165 struct var_info_hasher
: typed_free_remove
<var_info_d
>
167 typedef var_info_d value_type
;
168 typedef var_info_d compare_type
;
169 static inline hashval_t
hash (const value_type
*);
170 static inline bool equal (const value_type
*, const compare_type
*);
174 var_info_hasher::hash (const value_type
*p
)
176 return DECL_UID (p
->var
);
180 var_info_hasher::equal (const value_type
*p1
, const compare_type
*p2
)
182 return p1
->var
== p2
->var
;
186 /* Each entry in VAR_INFOS contains an element of type STRUCT
188 static hash_table
<var_info_hasher
> var_infos
;
191 /* Information stored for SSA names. */
194 /* Age of this record (so that info_for_ssa_name table can be cleared
195 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
196 are assumed to be null. */
199 /* Replacement mappings, allocated from update_ssa_obstack. */
202 /* Information stored for both SSA names and decls. */
203 struct common_info_d info
;
206 /* The information associated with names. */
207 typedef struct ssa_name_info
*ssa_name_info_p
;
209 static vec
<ssa_name_info_p
> info_for_ssa_name
;
210 static unsigned current_info_for_ssa_name_age
;
212 static bitmap_obstack update_ssa_obstack
;
214 /* The set of blocks affected by update_ssa. */
215 static bitmap blocks_to_update
;
217 /* The main entry point to the SSA renamer (rewrite_blocks) may be
218 called several times to do different, but related, tasks.
219 Initially, we need it to rename the whole program into SSA form.
220 At other times, we may need it to only rename into SSA newly
221 exposed symbols. Finally, we can also call it to incrementally fix
222 an already built SSA web. */
224 /* Convert the whole function into SSA form. */
227 /* Incrementally update the SSA web by replacing existing SSA
228 names with new ones. See update_ssa for details. */
235 /* Prototypes for debugging functions. */
236 extern void dump_tree_ssa (FILE *);
237 extern void debug_tree_ssa (void);
238 extern void debug_def_blocks (void);
239 extern void dump_tree_ssa_stats (FILE *);
240 extern void debug_tree_ssa_stats (void);
241 extern void dump_update_ssa (FILE *);
242 extern void debug_update_ssa (void);
243 extern void dump_names_replaced_by (FILE *, tree
);
244 extern void debug_names_replaced_by (tree
);
245 extern void dump_var_infos (FILE *);
246 extern void debug_var_infos (void);
247 extern void dump_defs_stack (FILE *, int);
248 extern void debug_defs_stack (int);
249 extern void dump_currdefs (FILE *);
250 extern void debug_currdefs (void);
253 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
254 static bitmap symbols_to_rename_set
;
255 static vec
<tree
> symbols_to_rename
;
257 /* Mark SYM for renaming. */
260 mark_for_renaming (tree sym
)
262 if (!symbols_to_rename_set
)
263 symbols_to_rename_set
= BITMAP_ALLOC (NULL
);
264 if (bitmap_set_bit (symbols_to_rename_set
, DECL_UID (sym
)))
265 symbols_to_rename
.safe_push (sym
);
268 /* Return true if SYM is marked for renaming. */
271 marked_for_renaming (tree sym
)
273 if (!symbols_to_rename_set
|| sym
== NULL_TREE
)
275 return bitmap_bit_p (symbols_to_rename_set
, DECL_UID (sym
));
279 /* Return true if STMT needs to be rewritten. When renaming a subset
280 of the variables, not all statements will be processed. This is
281 decided in mark_def_sites. */
284 rewrite_uses_p (gimple stmt
)
286 return gimple_visited_p (stmt
);
290 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
293 set_rewrite_uses (gimple stmt
, bool rewrite_p
)
295 gimple_set_visited (stmt
, rewrite_p
);
299 /* Return true if the DEFs created by statement STMT should be
300 registered when marking new definition sites. This is slightly
301 different than rewrite_uses_p: it's used by update_ssa to
302 distinguish statements that need to have both uses and defs
303 processed from those that only need to have their defs processed.
304 Statements that define new SSA names only need to have their defs
305 registered, but they don't need to have their uses renamed. */
308 register_defs_p (gimple stmt
)
310 return gimple_plf (stmt
, GF_PLF_1
) != 0;
314 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
317 set_register_defs (gimple stmt
, bool register_defs_p
)
319 gimple_set_plf (stmt
, GF_PLF_1
, register_defs_p
);
323 /* Get the information associated with NAME. */
325 static inline ssa_name_info_p
326 get_ssa_name_ann (tree name
)
328 unsigned ver
= SSA_NAME_VERSION (name
);
329 unsigned len
= info_for_ssa_name
.length ();
330 struct ssa_name_info
*info
;
332 /* Re-allocate the vector at most once per update/into-SSA. */
334 info_for_ssa_name
.safe_grow_cleared (num_ssa_names
);
336 /* But allocate infos lazily. */
337 info
= info_for_ssa_name
[ver
];
340 info
= XCNEW (struct ssa_name_info
);
341 info
->age
= current_info_for_ssa_name_age
;
342 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
343 info_for_ssa_name
[ver
] = info
;
346 if (info
->age
< current_info_for_ssa_name_age
)
348 info
->age
= current_info_for_ssa_name_age
;
349 info
->repl_set
= NULL
;
350 info
->info
.need_phi_state
= NEED_PHI_STATE_UNKNOWN
;
351 info
->info
.current_def
= NULL_TREE
;
352 info
->info
.def_blocks
.def_blocks
= NULL
;
353 info
->info
.def_blocks
.phi_blocks
= NULL
;
354 info
->info
.def_blocks
.livein_blocks
= NULL
;
360 /* Return and allocate the auxiliar information for DECL. */
362 static inline var_info_p
363 get_var_info (tree decl
)
365 struct var_info_d vi
;
368 slot
= var_infos
.find_slot_with_hash (&vi
, DECL_UID (decl
), INSERT
);
371 var_info_p v
= XCNEW (struct var_info_d
);
380 /* Clears info for SSA names. */
383 clear_ssa_name_info (void)
385 current_info_for_ssa_name_age
++;
387 /* If current_info_for_ssa_name_age wraps we use stale information.
388 Asser that this does not happen. */
389 gcc_assert (current_info_for_ssa_name_age
!= 0);
393 /* Get access to the auxiliar information stored per SSA name or decl. */
395 static inline common_info_p
396 get_common_info (tree var
)
398 if (TREE_CODE (var
) == SSA_NAME
)
399 return &get_ssa_name_ann (var
)->info
;
401 return &get_var_info (var
)->info
;
405 /* Return the current definition for VAR. */
408 get_current_def (tree var
)
410 return get_common_info (var
)->current_def
;
414 /* Sets current definition of VAR to DEF. */
417 set_current_def (tree var
, tree def
)
419 get_common_info (var
)->current_def
= def
;
422 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
423 all statements in basic block BB. */
426 initialize_flags_in_bb (basic_block bb
)
429 gimple_stmt_iterator gsi
;
431 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
433 gimple phi
= gsi_stmt (gsi
);
434 set_rewrite_uses (phi
, false);
435 set_register_defs (phi
, false);
438 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
440 stmt
= gsi_stmt (gsi
);
442 /* We are going to use the operand cache API, such as
443 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
444 cache for each statement should be up-to-date. */
445 gcc_checking_assert (!gimple_modified_p (stmt
));
446 set_rewrite_uses (stmt
, false);
447 set_register_defs (stmt
, false);
451 /* Mark block BB as interesting for update_ssa. */
454 mark_block_for_update (basic_block bb
)
456 gcc_checking_assert (blocks_to_update
!= NULL
);
457 if (!bitmap_set_bit (blocks_to_update
, bb
->index
))
459 initialize_flags_in_bb (bb
);
462 /* Return the set of blocks where variable VAR is defined and the blocks
463 where VAR is live on entry (livein). If no entry is found in
464 DEF_BLOCKS, a new one is created and returned. */
466 static inline struct def_blocks_d
*
467 get_def_blocks_for (common_info_p info
)
469 struct def_blocks_d
*db_p
= &info
->def_blocks
;
470 if (!db_p
->def_blocks
)
472 db_p
->def_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
473 db_p
->phi_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
474 db_p
->livein_blocks
= BITMAP_ALLOC (&update_ssa_obstack
);
481 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
482 VAR is defined by a PHI node. */
485 set_def_block (tree var
, basic_block bb
, bool phi_p
)
487 struct def_blocks_d
*db_p
;
490 info
= get_common_info (var
);
491 db_p
= get_def_blocks_for (info
);
493 /* Set the bit corresponding to the block where VAR is defined. */
494 bitmap_set_bit (db_p
->def_blocks
, bb
->index
);
496 bitmap_set_bit (db_p
->phi_blocks
, bb
->index
);
498 /* Keep track of whether or not we may need to insert PHI nodes.
500 If we are in the UNKNOWN state, then this is the first definition
501 of VAR. Additionally, we have not seen any uses of VAR yet, so
502 we do not need a PHI node for this variable at this time (i.e.,
503 transition to NEED_PHI_STATE_NO).
505 If we are in any other state, then we either have multiple definitions
506 of this variable occurring in different blocks or we saw a use of the
507 variable which was not dominated by the block containing the
508 definition(s). In this case we may need a PHI node, so enter
509 state NEED_PHI_STATE_MAYBE. */
510 if (info
->need_phi_state
== NEED_PHI_STATE_UNKNOWN
)
511 info
->need_phi_state
= NEED_PHI_STATE_NO
;
513 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
517 /* Mark block BB as having VAR live at the entry to BB. */
520 set_livein_block (tree var
, basic_block bb
)
523 struct def_blocks_d
*db_p
;
525 info
= get_common_info (var
);
526 db_p
= get_def_blocks_for (info
);
528 /* Set the bit corresponding to the block where VAR is live in. */
529 bitmap_set_bit (db_p
->livein_blocks
, bb
->index
);
531 /* Keep track of whether or not we may need to insert PHI nodes.
533 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
534 by the single block containing the definition(s) of this variable. If
535 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
536 NEED_PHI_STATE_MAYBE. */
537 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
539 int def_block_index
= bitmap_first_set_bit (db_p
->def_blocks
);
541 if (def_block_index
== -1
542 || ! dominated_by_p (CDI_DOMINATORS
, bb
,
543 BASIC_BLOCK (def_block_index
)))
544 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
547 info
->need_phi_state
= NEED_PHI_STATE_MAYBE
;
551 /* Return true if NAME is in OLD_SSA_NAMES. */
554 is_old_name (tree name
)
556 unsigned ver
= SSA_NAME_VERSION (name
);
559 return (ver
< SBITMAP_SIZE (new_ssa_names
)
560 && bitmap_bit_p (old_ssa_names
, ver
));
564 /* Return true if NAME is in NEW_SSA_NAMES. */
567 is_new_name (tree name
)
569 unsigned ver
= SSA_NAME_VERSION (name
);
572 return (ver
< SBITMAP_SIZE (new_ssa_names
)
573 && bitmap_bit_p (new_ssa_names
, ver
));
577 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
580 names_replaced_by (tree new_tree
)
582 return get_ssa_name_ann (new_tree
)->repl_set
;
586 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
589 add_to_repl_tbl (tree new_tree
, tree old
)
591 bitmap
*set
= &get_ssa_name_ann (new_tree
)->repl_set
;
593 *set
= BITMAP_ALLOC (&update_ssa_obstack
);
594 bitmap_set_bit (*set
, SSA_NAME_VERSION (old
));
598 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
599 represents the set of names O_1 ... O_j replaced by N_i. This is
600 used by update_ssa and its helpers to introduce new SSA names in an
601 already formed SSA web. */
604 add_new_name_mapping (tree new_tree
, tree old
)
606 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
607 gcc_checking_assert (new_tree
!= old
608 && SSA_NAME_VAR (new_tree
) == SSA_NAME_VAR (old
));
610 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
611 caller may have created new names since the set was created. */
612 if (SBITMAP_SIZE (new_ssa_names
) <= num_ssa_names
- 1)
614 unsigned int new_sz
= num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
;
615 new_ssa_names
= sbitmap_resize (new_ssa_names
, new_sz
, 0);
616 old_ssa_names
= sbitmap_resize (old_ssa_names
, new_sz
, 0);
619 /* Update the REPL_TBL table. */
620 add_to_repl_tbl (new_tree
, old
);
622 /* If OLD had already been registered as a new name, then all the
623 names that OLD replaces should also be replaced by NEW_TREE. */
624 if (is_new_name (old
))
625 bitmap_ior_into (names_replaced_by (new_tree
), names_replaced_by (old
));
627 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
629 bitmap_set_bit (new_ssa_names
, SSA_NAME_VERSION (new_tree
));
630 bitmap_set_bit (old_ssa_names
, SSA_NAME_VERSION (old
));
634 /* Call back for walk_dominator_tree used to collect definition sites
635 for every variable in the function. For every statement S in block
638 1- Variables defined by S in the DEFS of S are marked in the bitmap
641 2- If S uses a variable VAR and there is no preceding kill of VAR,
642 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
644 This information is used to determine which variables are live
645 across block boundaries to reduce the number of PHI nodes
649 mark_def_sites (basic_block bb
, gimple stmt
, bitmap kills
)
655 /* Since this is the first time that we rewrite the program into SSA
656 form, force an operand scan on every statement. */
659 gcc_checking_assert (blocks_to_update
== NULL
);
660 set_register_defs (stmt
, false);
661 set_rewrite_uses (stmt
, false);
663 if (is_gimple_debug (stmt
))
665 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
667 tree sym
= USE_FROM_PTR (use_p
);
668 gcc_checking_assert (DECL_P (sym
));
669 set_rewrite_uses (stmt
, true);
671 if (rewrite_uses_p (stmt
))
672 bitmap_set_bit (interesting_blocks
, bb
->index
);
676 /* If a variable is used before being set, then the variable is live
677 across a block boundary, so mark it live-on-entry to BB. */
678 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
680 tree sym
= USE_FROM_PTR (use_p
);
681 gcc_checking_assert (DECL_P (sym
));
682 if (!bitmap_bit_p (kills
, DECL_UID (sym
)))
683 set_livein_block (sym
, bb
);
684 set_rewrite_uses (stmt
, true);
687 /* Now process the defs. Mark BB as the definition block and add
688 each def to the set of killed symbols. */
689 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
691 gcc_checking_assert (DECL_P (def
));
692 set_def_block (def
, bb
, false);
693 bitmap_set_bit (kills
, DECL_UID (def
));
694 set_register_defs (stmt
, true);
697 /* If we found the statement interesting then also mark the block BB
699 if (rewrite_uses_p (stmt
) || register_defs_p (stmt
))
700 bitmap_set_bit (interesting_blocks
, bb
->index
);
703 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
704 in the dfs numbering of the dominance tree. */
708 /* Basic block whose index this entry corresponds to. */
711 /* The dfs number of this node. */
715 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
719 cmp_dfsnum (const void *a
, const void *b
)
721 const struct dom_dfsnum
*const da
= (const struct dom_dfsnum
*) a
;
722 const struct dom_dfsnum
*const db
= (const struct dom_dfsnum
*) b
;
724 return (int) da
->dfs_num
- (int) db
->dfs_num
;
727 /* Among the intervals starting at the N points specified in DEFS, find
728 the one that contains S, and return its bb_index. */
731 find_dfsnum_interval (struct dom_dfsnum
*defs
, unsigned n
, unsigned s
)
733 unsigned f
= 0, t
= n
, m
;
738 if (defs
[m
].dfs_num
<= s
)
744 return defs
[f
].bb_index
;
747 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
748 KILLS is a bitmap of blocks where the value is defined before any use. */
751 prune_unused_phi_nodes (bitmap phis
, bitmap kills
, bitmap uses
)
755 unsigned i
, b
, p
, u
, top
;
757 basic_block def_bb
, use_bb
;
761 struct dom_dfsnum
*defs
;
762 unsigned n_defs
, adef
;
764 if (bitmap_empty_p (uses
))
770 /* The phi must dominate a use, or an argument of a live phi. Also, we
771 do not create any phi nodes in def blocks, unless they are also livein. */
772 to_remove
= BITMAP_ALLOC (NULL
);
773 bitmap_and_compl (to_remove
, kills
, uses
);
774 bitmap_and_compl_into (phis
, to_remove
);
775 if (bitmap_empty_p (phis
))
777 BITMAP_FREE (to_remove
);
781 /* We want to remove the unnecessary phi nodes, but we do not want to compute
782 liveness information, as that may be linear in the size of CFG, and if
783 there are lot of different variables to rewrite, this may lead to quadratic
786 Instead, we basically emulate standard dce. We put all uses to worklist,
787 then for each of them find the nearest def that dominates them. If this
788 def is a phi node, we mark it live, and if it was not live before, we
789 add the predecessors of its basic block to the worklist.
791 To quickly locate the nearest def that dominates use, we use dfs numbering
792 of the dominance tree (that is already available in order to speed up
793 queries). For each def, we have the interval given by the dfs number on
794 entry to and on exit from the corresponding subtree in the dominance tree.
795 The nearest dominator for a given use is the smallest of these intervals
796 that contains entry and exit dfs numbers for the basic block with the use.
797 If we store the bounds for all the uses to an array and sort it, we can
798 locate the nearest dominating def in logarithmic time by binary search.*/
799 bitmap_ior (to_remove
, kills
, phis
);
800 n_defs
= bitmap_count_bits (to_remove
);
801 defs
= XNEWVEC (struct dom_dfsnum
, 2 * n_defs
+ 1);
802 defs
[0].bb_index
= 1;
805 EXECUTE_IF_SET_IN_BITMAP (to_remove
, 0, i
, bi
)
807 def_bb
= BASIC_BLOCK (i
);
808 defs
[adef
].bb_index
= i
;
809 defs
[adef
].dfs_num
= bb_dom_dfs_in (CDI_DOMINATORS
, def_bb
);
810 defs
[adef
+ 1].bb_index
= i
;
811 defs
[adef
+ 1].dfs_num
= bb_dom_dfs_out (CDI_DOMINATORS
, def_bb
);
814 BITMAP_FREE (to_remove
);
815 gcc_assert (adef
== 2 * n_defs
+ 1);
816 qsort (defs
, adef
, sizeof (struct dom_dfsnum
), cmp_dfsnum
);
817 gcc_assert (defs
[0].bb_index
== 1);
819 /* Now each DEFS entry contains the number of the basic block to that the
820 dfs number corresponds. Change them to the number of basic block that
821 corresponds to the interval following the dfs number. Also, for the
822 dfs_out numbers, increase the dfs number by one (so that it corresponds
823 to the start of the following interval, not to the end of the current
824 one). We use WORKLIST as a stack. */
825 worklist
.create (n_defs
+ 1);
826 worklist
.quick_push (1);
829 for (i
= 1; i
< adef
; i
++)
831 b
= defs
[i
].bb_index
;
834 /* This is a closing element. Interval corresponding to the top
835 of the stack after removing it follows. */
837 top
= worklist
[worklist
.length () - 1];
838 defs
[n_defs
].bb_index
= top
;
839 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
+ 1;
843 /* Opening element. Nothing to do, just push it to the stack and move
844 it to the correct position. */
845 defs
[n_defs
].bb_index
= defs
[i
].bb_index
;
846 defs
[n_defs
].dfs_num
= defs
[i
].dfs_num
;
847 worklist
.quick_push (b
);
851 /* If this interval starts at the same point as the previous one, cancel
853 if (defs
[n_defs
].dfs_num
== defs
[n_defs
- 1].dfs_num
)
854 defs
[n_defs
- 1].bb_index
= defs
[n_defs
].bb_index
;
859 gcc_assert (worklist
.is_empty ());
861 /* Now process the uses. */
862 live_phis
= BITMAP_ALLOC (NULL
);
863 EXECUTE_IF_SET_IN_BITMAP (uses
, 0, i
, bi
)
865 worklist
.safe_push (i
);
868 while (!worklist
.is_empty ())
871 if (b
== ENTRY_BLOCK
)
874 /* If there is a phi node in USE_BB, it is made live. Otherwise,
875 find the def that dominates the immediate dominator of USE_BB
876 (the kill in USE_BB does not dominate the use). */
877 if (bitmap_bit_p (phis
, b
))
881 use_bb
= get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (b
));
882 p
= find_dfsnum_interval (defs
, n_defs
,
883 bb_dom_dfs_in (CDI_DOMINATORS
, use_bb
));
884 if (!bitmap_bit_p (phis
, p
))
888 /* If the phi node is already live, there is nothing to do. */
889 if (!bitmap_set_bit (live_phis
, p
))
892 /* Add the new uses to the worklist. */
893 def_bb
= BASIC_BLOCK (p
);
894 FOR_EACH_EDGE (e
, ei
, def_bb
->preds
)
897 if (bitmap_bit_p (uses
, u
))
900 /* In case there is a kill directly in the use block, do not record
901 the use (this is also necessary for correctness, as we assume that
902 uses dominated by a def directly in their block have been filtered
904 if (bitmap_bit_p (kills
, u
))
907 bitmap_set_bit (uses
, u
);
908 worklist
.safe_push (u
);
913 bitmap_copy (phis
, live_phis
);
914 BITMAP_FREE (live_phis
);
918 /* Return the set of blocks where variable VAR is defined and the blocks
919 where VAR is live on entry (livein). Return NULL, if no entry is
920 found in DEF_BLOCKS. */
922 static inline struct def_blocks_d
*
923 find_def_blocks_for (tree var
)
925 def_blocks_p p
= &get_common_info (var
)->def_blocks
;
932 /* Marks phi node PHI in basic block BB for rewrite. */
935 mark_phi_for_rewrite (basic_block bb
, gimple phi
)
938 unsigned n
, idx
= bb
->index
;
940 if (rewrite_uses_p (phi
))
943 set_rewrite_uses (phi
, true);
945 if (!blocks_with_phis_to_rewrite
)
948 bitmap_set_bit (blocks_with_phis_to_rewrite
, idx
);
950 n
= (unsigned) last_basic_block
+ 1;
951 if (phis_to_rewrite
.length () < n
)
952 phis_to_rewrite
.safe_grow_cleared (n
);
954 phis
= phis_to_rewrite
[idx
];
957 phis
.safe_push (phi
);
958 phis_to_rewrite
[idx
] = phis
;
961 /* Insert PHI nodes for variable VAR using the iterated dominance
962 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
963 function assumes that the caller is incrementally updating the
964 existing SSA form, in which case VAR may be an SSA name instead of
967 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
968 PHI node for VAR. On exit, only the nodes that received a PHI node
969 for VAR will be present in PHI_INSERTION_POINTS. */
972 insert_phi_nodes_for (tree var
, bitmap phi_insertion_points
, bool update_p
)
979 struct def_blocks_d
*def_map
= find_def_blocks_for (var
);
981 /* Remove the blocks where we already have PHI nodes for VAR. */
982 bitmap_and_compl_into (phi_insertion_points
, def_map
->phi_blocks
);
984 /* Remove obviously useless phi nodes. */
985 prune_unused_phi_nodes (phi_insertion_points
, def_map
->def_blocks
,
986 def_map
->livein_blocks
);
988 /* And insert the PHI nodes. */
989 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points
, 0, bb_index
, bi
)
991 bb
= BASIC_BLOCK (bb_index
);
993 mark_block_for_update (bb
);
995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
997 fprintf (dump_file
, "creating PHI node in block #%d for ", bb_index
);
998 print_generic_expr (dump_file
, var
, TDF_SLIM
);
999 fprintf (dump_file
, "\n");
1003 if (TREE_CODE (var
) == SSA_NAME
)
1005 /* If we are rewriting SSA names, create the LHS of the PHI
1006 node by duplicating VAR. This is useful in the case of
1007 pointers, to also duplicate pointer attributes (alias
1008 information, in particular). */
1012 gcc_checking_assert (update_p
);
1013 new_lhs
= duplicate_ssa_name (var
, NULL
);
1014 phi
= create_phi_node (new_lhs
, bb
);
1015 add_new_name_mapping (new_lhs
, var
);
1017 /* Add VAR to every argument slot of PHI. We need VAR in
1018 every argument so that rewrite_update_phi_arguments knows
1019 which name is this PHI node replacing. If VAR is a
1020 symbol marked for renaming, this is not necessary, the
1021 renamer will use the symbol on the LHS to get its
1022 reaching definition. */
1023 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1024 add_phi_arg (phi
, var
, e
, UNKNOWN_LOCATION
);
1030 gcc_checking_assert (DECL_P (var
));
1031 phi
= create_phi_node (var
, bb
);
1033 tracked_var
= target_for_debug_bind (var
);
1036 gimple note
= gimple_build_debug_bind (tracked_var
,
1039 gimple_stmt_iterator si
= gsi_after_labels (bb
);
1040 gsi_insert_before (&si
, note
, GSI_SAME_STMT
);
1044 /* Mark this PHI node as interesting for update_ssa. */
1045 set_register_defs (phi
, true);
1046 mark_phi_for_rewrite (bb
, phi
);
1050 /* Sort var_infos after DECL_UID of their var. */
1053 insert_phi_nodes_compare_var_infos (const void *a
, const void *b
)
1055 const struct var_info_d
*defa
= *(struct var_info_d
* const *)a
;
1056 const struct var_info_d
*defb
= *(struct var_info_d
* const *)b
;
1057 if (DECL_UID (defa
->var
) < DECL_UID (defb
->var
))
1063 /* Insert PHI nodes at the dominance frontier of blocks with variable
1064 definitions. DFS contains the dominance frontier information for
1068 insert_phi_nodes (bitmap_head
*dfs
)
1070 hash_table
<var_info_hasher
>::iterator hi
;
1073 vec
<var_info_p
> vars
;
1075 timevar_push (TV_TREE_INSERT_PHI_NODES
);
1077 vars
.create (var_infos
.elements ());
1078 FOR_EACH_HASH_TABLE_ELEMENT (var_infos
, info
, var_info_p
, hi
)
1079 if (info
->info
.need_phi_state
!= NEED_PHI_STATE_NO
)
1080 vars
.quick_push (info
);
1082 /* Do two stages to avoid code generation differences for UID
1083 differences but no UID ordering differences. */
1084 vars
.qsort (insert_phi_nodes_compare_var_infos
);
1086 FOR_EACH_VEC_ELT (vars
, i
, info
)
1088 bitmap idf
= compute_idf (info
->info
.def_blocks
.def_blocks
, dfs
);
1089 insert_phi_nodes_for (info
->var
, idf
, false);
1095 timevar_pop (TV_TREE_INSERT_PHI_NODES
);
1099 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1100 register DEF (an SSA_NAME) to be a new definition for SYM. */
1103 register_new_def (tree def
, tree sym
)
1105 common_info_p info
= get_common_info (sym
);
1108 /* If this variable is set in a single basic block and all uses are
1109 dominated by the set(s) in that single basic block, then there is
1110 no reason to record anything for this variable in the block local
1111 definition stacks. Doing so just wastes time and memory.
1113 This is the same test to prune the set of variables which may
1114 need PHI nodes. So we just use that information since it's already
1115 computed and available for us to use. */
1116 if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1118 info
->current_def
= def
;
1122 currdef
= info
->current_def
;
1124 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1125 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1126 in the stack so that we know which symbol is being defined by
1127 this SSA name when we unwind the stack. */
1128 if (currdef
&& !is_gimple_reg (sym
))
1129 block_defs_stack
.safe_push (sym
);
1131 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1132 stack is later used by the dominator tree callbacks to restore
1133 the reaching definitions for all the variables defined in the
1134 block after a recursive visit to all its immediately dominated
1135 blocks. If there is no current reaching definition, then just
1136 record the underlying _DECL node. */
1137 block_defs_stack
.safe_push (currdef
? currdef
: sym
);
1139 /* Set the current reaching definition for SYM to be DEF. */
1140 info
->current_def
= def
;
1144 /* Perform a depth-first traversal of the dominator tree looking for
1145 variables to rename. BB is the block where to start searching.
1146 Renaming is a five step process:
1148 1- Every definition made by PHI nodes at the start of the blocks is
1149 registered as the current definition for the corresponding variable.
1151 2- Every statement in BB is rewritten. USE and VUSE operands are
1152 rewritten with their corresponding reaching definition. DEF and
1153 VDEF targets are registered as new definitions.
1155 3- All the PHI nodes in successor blocks of BB are visited. The
1156 argument corresponding to BB is replaced with its current reaching
1159 4- Recursively rewrite every dominator child block of BB.
1161 5- Restore (in reverse order) the current reaching definition for every
1162 new definition introduced in this block. This is done so that when
1163 we return from the recursive call, all the current reaching
1164 definitions are restored to the names that were valid in the
1165 dominator parent of BB. */
1167 /* Return the current definition for variable VAR. If none is found,
1168 create a new SSA name to act as the zeroth definition for VAR. */
1171 get_reaching_def (tree var
)
1173 common_info_p info
= get_common_info (var
);
1176 /* Lookup the current reaching definition for VAR. */
1177 currdef
= info
->current_def
;
1179 /* If there is no reaching definition for VAR, create and register a
1180 default definition for it (if needed). */
1181 if (currdef
== NULL_TREE
)
1183 tree sym
= DECL_P (var
) ? var
: SSA_NAME_VAR (var
);
1184 currdef
= get_or_create_ssa_default_def (cfun
, sym
);
1187 /* Return the current reaching definition for VAR, or the default
1188 definition, if we had to create one. */
1193 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1196 rewrite_debug_stmt_uses (gimple stmt
)
1198 use_operand_p use_p
;
1200 bool update
= false;
1202 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1204 tree var
= USE_FROM_PTR (use_p
), def
;
1205 common_info_p info
= get_common_info (var
);
1206 gcc_checking_assert (DECL_P (var
));
1207 def
= info
->current_def
;
1210 if (TREE_CODE (var
) == PARM_DECL
&& single_succ_p (ENTRY_BLOCK_PTR
))
1212 gimple_stmt_iterator gsi
1213 = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR
));
1215 /* Search a few source bind stmts at the start of first bb to
1216 see if a DEBUG_EXPR_DECL can't be reused. */
1218 !gsi_end_p (gsi
) && lim
> 0;
1219 gsi_next (&gsi
), lim
--)
1221 gimple gstmt
= gsi_stmt (gsi
);
1222 if (!gimple_debug_source_bind_p (gstmt
))
1224 if (gimple_debug_source_bind_get_value (gstmt
) == var
)
1226 def
= gimple_debug_source_bind_get_var (gstmt
);
1227 if (TREE_CODE (def
) == DEBUG_EXPR_DECL
)
1233 /* If not, add a new source bind stmt. */
1234 if (def
== NULL_TREE
)
1237 def
= make_node (DEBUG_EXPR_DECL
);
1238 def_temp
= gimple_build_debug_source_bind (def
, var
, NULL
);
1239 DECL_ARTIFICIAL (def
) = 1;
1240 TREE_TYPE (def
) = TREE_TYPE (var
);
1241 DECL_MODE (def
) = DECL_MODE (var
);
1242 gsi
= gsi_after_labels (single_succ (ENTRY_BLOCK_PTR
));
1243 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
1250 /* Check if info->current_def can be trusted. */
1251 basic_block bb
= gimple_bb (stmt
);
1253 = SSA_NAME_IS_DEFAULT_DEF (def
)
1254 ? NULL
: gimple_bb (SSA_NAME_DEF_STMT (def
));
1256 /* If definition is in current bb, it is fine. */
1259 /* If definition bb doesn't dominate the current bb,
1260 it can't be used. */
1261 else if (def_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
1263 /* If there is just one definition and dominates the current
1265 else if (info
->need_phi_state
== NEED_PHI_STATE_NO
)
1269 struct def_blocks_d
*db_p
= get_def_blocks_for (info
);
1271 /* If there are some non-debug uses in the current bb,
1273 if (bitmap_bit_p (db_p
->livein_blocks
, bb
->index
))
1275 /* Otherwise give up for now. */
1282 gimple_debug_bind_reset_value (stmt
);
1286 SET_USE (use_p
, def
);
1292 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1293 the block with its immediate reaching definitions. Update the current
1294 definition of a variable when a new real or virtual definition is found. */
1297 rewrite_stmt (gimple_stmt_iterator
*si
)
1299 use_operand_p use_p
;
1300 def_operand_p def_p
;
1302 gimple stmt
= gsi_stmt (*si
);
1304 /* If mark_def_sites decided that we don't need to rewrite this
1305 statement, ignore it. */
1306 gcc_assert (blocks_to_update
== NULL
);
1307 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1310 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1312 fprintf (dump_file
, "Renaming statement ");
1313 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1314 fprintf (dump_file
, "\n");
1317 /* Step 1. Rewrite USES in the statement. */
1318 if (rewrite_uses_p (stmt
))
1320 if (is_gimple_debug (stmt
))
1321 rewrite_debug_stmt_uses (stmt
);
1323 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1325 tree var
= USE_FROM_PTR (use_p
);
1326 gcc_checking_assert (DECL_P (var
));
1327 SET_USE (use_p
, get_reaching_def (var
));
1331 /* Step 2. Register the statement's DEF operands. */
1332 if (register_defs_p (stmt
))
1333 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1335 tree var
= DEF_FROM_PTR (def_p
);
1339 gcc_checking_assert (DECL_P (var
));
1341 if (gimple_clobber_p (stmt
)
1342 && is_gimple_reg (var
))
1344 /* If we rewrite a DECL into SSA form then drop its
1345 clobber stmts and replace uses with a new default def. */
1346 gcc_checking_assert (TREE_CODE (var
) == VAR_DECL
1347 && !gimple_vdef (stmt
));
1348 gsi_replace (si
, gimple_build_nop (), true);
1349 register_new_def (get_or_create_ssa_default_def (cfun
, var
), var
);
1353 name
= make_ssa_name (var
, stmt
);
1354 SET_DEF (def_p
, name
);
1355 register_new_def (DEF_FROM_PTR (def_p
), var
);
1357 tracked_var
= target_for_debug_bind (var
);
1360 gimple note
= gimple_build_debug_bind (tracked_var
, name
, stmt
);
1361 gsi_insert_after (si
, note
, GSI_SAME_STMT
);
1367 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1368 PHI nodes. For every PHI node found, add a new argument containing the
1369 current reaching definition for the variable and the edge through which
1370 that definition is reaching the PHI node. */
1373 rewrite_add_phi_arguments (basic_block bb
)
1378 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1381 gimple_stmt_iterator gsi
;
1383 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
1389 phi
= gsi_stmt (gsi
);
1390 res
= gimple_phi_result (phi
);
1391 currdef
= get_reaching_def (SSA_NAME_VAR (res
));
1392 /* Virtual operand PHI args do not need a location. */
1393 if (virtual_operand_p (res
))
1394 loc
= UNKNOWN_LOCATION
;
1396 loc
= gimple_location (SSA_NAME_DEF_STMT (currdef
));
1397 add_phi_arg (phi
, currdef
, e
, loc
);
1402 class rewrite_dom_walker
: public dom_walker
1405 rewrite_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1407 virtual void before_dom_children (basic_block
);
1408 virtual void after_dom_children (basic_block
);
1411 /* SSA Rewriting Step 1. Initialization, create a block local stack
1412 of reaching definitions for new SSA names produced in this block
1413 (BLOCK_DEFS). Register new definitions for every PHI node in the
1417 rewrite_dom_walker::before_dom_children (basic_block bb
)
1419 gimple_stmt_iterator gsi
;
1421 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1422 fprintf (dump_file
, "\n\nRenaming block #%d\n\n", bb
->index
);
1424 /* Mark the unwind point for this block. */
1425 block_defs_stack
.safe_push (NULL_TREE
);
1427 /* Step 1. Register new definitions for every PHI node in the block.
1428 Conceptually, all the PHI nodes are executed in parallel and each PHI
1429 node introduces a new version for the associated variable. */
1430 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1432 tree result
= gimple_phi_result (gsi_stmt (gsi
));
1433 register_new_def (result
, SSA_NAME_VAR (result
));
1436 /* Step 2. Rewrite every variable used in each statement in the block
1437 with its immediate reaching definitions. Update the current definition
1438 of a variable when a new real or virtual definition is found. */
1439 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
1440 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1441 rewrite_stmt (&gsi
);
1443 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1444 For every PHI node found, add a new argument containing the current
1445 reaching definition for the variable and the edge through which that
1446 definition is reaching the PHI node. */
1447 rewrite_add_phi_arguments (bb
);
1452 /* Called after visiting all the statements in basic block BB and all
1453 of its dominator children. Restore CURRDEFS to its original value. */
1456 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
1458 /* Restore CURRDEFS to its original state. */
1459 while (block_defs_stack
.length () > 0)
1461 tree tmp
= block_defs_stack
.pop ();
1462 tree saved_def
, var
;
1464 if (tmp
== NULL_TREE
)
1467 if (TREE_CODE (tmp
) == SSA_NAME
)
1469 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1470 current definition of its underlying variable. Note that
1471 if the SSA_NAME is not for a GIMPLE register, the symbol
1472 being defined is stored in the next slot in the stack.
1473 This mechanism is needed because an SSA name for a
1474 non-register symbol may be the definition for more than
1475 one symbol (e.g., SFTs, aliased variables, etc). */
1477 var
= SSA_NAME_VAR (saved_def
);
1478 if (!is_gimple_reg (var
))
1479 var
= block_defs_stack
.pop ();
1483 /* If we recorded anything else, it must have been a _DECL
1484 node and its current reaching definition must have been
1490 get_common_info (var
)->current_def
= saved_def
;
1495 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1498 dump_decl_set (FILE *file
, bitmap set
)
1505 fprintf (file
, "{ ");
1507 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
1509 fprintf (file
, "D.%u", i
);
1510 fprintf (file
, " ");
1513 fprintf (file
, "}");
1516 fprintf (file
, "NIL");
1520 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1523 debug_decl_set (bitmap set
)
1525 dump_decl_set (stderr
, set
);
1526 fprintf (stderr
, "\n");
1530 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1531 stack up to a maximum of N levels. If N is -1, the whole stack is
1532 dumped. New levels are created when the dominator tree traversal
1533 used for renaming enters a new sub-tree. */
1536 dump_defs_stack (FILE *file
, int n
)
1540 fprintf (file
, "\n\nRenaming stack");
1542 fprintf (file
, " (up to %d levels)", n
);
1543 fprintf (file
, "\n\n");
1546 fprintf (file
, "Level %d (current level)\n", i
);
1547 for (j
= (int) block_defs_stack
.length () - 1; j
>= 0; j
--)
1551 name
= block_defs_stack
[j
];
1552 if (name
== NULL_TREE
)
1557 fprintf (file
, "\nLevel %d\n", i
);
1568 var
= SSA_NAME_VAR (name
);
1569 if (!is_gimple_reg (var
))
1572 var
= block_defs_stack
[j
];
1576 fprintf (file
, " Previous CURRDEF (");
1577 print_generic_expr (file
, var
, 0);
1578 fprintf (file
, ") = ");
1580 print_generic_expr (file
, name
, 0);
1582 fprintf (file
, "<NIL>");
1583 fprintf (file
, "\n");
1588 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1589 stack up to a maximum of N levels. If N is -1, the whole stack is
1590 dumped. New levels are created when the dominator tree traversal
1591 used for renaming enters a new sub-tree. */
1594 debug_defs_stack (int n
)
1596 dump_defs_stack (stderr
, n
);
1600 /* Dump the current reaching definition of every symbol to FILE. */
1603 dump_currdefs (FILE *file
)
1608 if (symbols_to_rename
.is_empty ())
1611 fprintf (file
, "\n\nCurrent reaching definitions\n\n");
1612 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, var
)
1614 common_info_p info
= get_common_info (var
);
1615 fprintf (file
, "CURRDEF (");
1616 print_generic_expr (file
, var
, 0);
1617 fprintf (file
, ") = ");
1618 if (info
->current_def
)
1619 print_generic_expr (file
, info
->current_def
, 0);
1621 fprintf (file
, "<NIL>");
1622 fprintf (file
, "\n");
1627 /* Dump the current reaching definition of every symbol to stderr. */
1630 debug_currdefs (void)
1632 dump_currdefs (stderr
);
1636 /* Dump SSA information to FILE. */
1639 dump_tree_ssa (FILE *file
)
1641 const char *funcname
1642 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
1644 fprintf (file
, "SSA renaming information for %s\n\n", funcname
);
1646 dump_var_infos (file
);
1647 dump_defs_stack (file
, -1);
1648 dump_currdefs (file
);
1649 dump_tree_ssa_stats (file
);
1653 /* Dump SSA information to stderr. */
1656 debug_tree_ssa (void)
1658 dump_tree_ssa (stderr
);
1662 /* Dump statistics for the hash table HTAB. */
1665 htab_statistics (FILE *file
, hash_table
<var_info_hasher
> htab
)
1667 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1668 (long) htab
.size (),
1669 (long) htab
.elements (),
1670 htab
.collisions ());
1674 /* Dump SSA statistics on FILE. */
1677 dump_tree_ssa_stats (FILE *file
)
1679 if (var_infos
.is_created ())
1681 fprintf (file
, "\nHash table statistics:\n");
1682 fprintf (file
, " var_infos: ");
1683 htab_statistics (file
, var_infos
);
1684 fprintf (file
, "\n");
1689 /* Dump SSA statistics on stderr. */
1692 debug_tree_ssa_stats (void)
1694 dump_tree_ssa_stats (stderr
);
1698 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1701 debug_var_infos_r (var_info_d
**slot
, FILE *file
)
1703 struct var_info_d
*info
= *slot
;
1705 fprintf (file
, "VAR: ");
1706 print_generic_expr (file
, info
->var
, dump_flags
);
1707 bitmap_print (file
, info
->info
.def_blocks
.def_blocks
,
1708 ", DEF_BLOCKS: { ", "}");
1709 bitmap_print (file
, info
->info
.def_blocks
.livein_blocks
,
1710 ", LIVEIN_BLOCKS: { ", "}");
1711 bitmap_print (file
, info
->info
.def_blocks
.phi_blocks
,
1712 ", PHI_BLOCKS: { ", "}\n");
1718 /* Dump the VAR_INFOS hash table on FILE. */
1721 dump_var_infos (FILE *file
)
1723 fprintf (file
, "\n\nDefinition and live-in blocks:\n\n");
1724 if (var_infos
.is_created ())
1725 var_infos
.traverse
<FILE *, debug_var_infos_r
> (file
);
1729 /* Dump the VAR_INFOS hash table on stderr. */
1732 debug_var_infos (void)
1734 dump_var_infos (stderr
);
1738 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1741 register_new_update_single (tree new_name
, tree old_name
)
1743 common_info_p info
= get_common_info (old_name
);
1744 tree currdef
= info
->current_def
;
1746 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1747 This stack is later used by the dominator tree callbacks to
1748 restore the reaching definitions for all the variables
1749 defined in the block after a recursive visit to all its
1750 immediately dominated blocks. */
1751 block_defs_stack
.reserve (2);
1752 block_defs_stack
.quick_push (currdef
);
1753 block_defs_stack
.quick_push (old_name
);
1755 /* Set the current reaching definition for OLD_NAME to be
1757 info
->current_def
= new_name
;
1761 /* Register NEW_NAME to be the new reaching definition for all the
1762 names in OLD_NAMES. Used by the incremental SSA update routines to
1763 replace old SSA names with new ones. */
1766 register_new_update_set (tree new_name
, bitmap old_names
)
1771 EXECUTE_IF_SET_IN_BITMAP (old_names
, 0, i
, bi
)
1772 register_new_update_single (new_name
, ssa_name (i
));
1777 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1778 it is a symbol marked for renaming, replace it with USE_P's current
1779 reaching definition. */
1782 maybe_replace_use (use_operand_p use_p
)
1784 tree rdef
= NULL_TREE
;
1785 tree use
= USE_FROM_PTR (use_p
);
1786 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1788 if (marked_for_renaming (sym
))
1789 rdef
= get_reaching_def (sym
);
1790 else if (is_old_name (use
))
1791 rdef
= get_reaching_def (use
);
1793 if (rdef
&& rdef
!= use
)
1794 SET_USE (use_p
, rdef
);
1798 /* Same as maybe_replace_use, but without introducing default stmts,
1799 returning false to indicate a need to do so. */
1802 maybe_replace_use_in_debug_stmt (use_operand_p use_p
)
1804 tree rdef
= NULL_TREE
;
1805 tree use
= USE_FROM_PTR (use_p
);
1806 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
1808 if (marked_for_renaming (sym
))
1809 rdef
= get_var_info (sym
)->info
.current_def
;
1810 else if (is_old_name (use
))
1812 rdef
= get_ssa_name_ann (use
)->info
.current_def
;
1813 /* We can't assume that, if there's no current definition, the
1814 default one should be used. It could be the case that we've
1815 rearranged blocks so that the earlier definition no longer
1816 dominates the use. */
1817 if (!rdef
&& SSA_NAME_IS_DEFAULT_DEF (use
))
1823 if (rdef
&& rdef
!= use
)
1824 SET_USE (use_p
, rdef
);
1826 return rdef
!= NULL_TREE
;
1830 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1831 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1832 register it as the current definition for the names replaced by
1836 maybe_register_def (def_operand_p def_p
, gimple stmt
,
1837 gimple_stmt_iterator gsi
)
1839 tree def
= DEF_FROM_PTR (def_p
);
1840 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
1842 /* If DEF is a naked symbol that needs renaming, create a new
1844 if (marked_for_renaming (sym
))
1850 def
= make_ssa_name (def
, stmt
);
1851 SET_DEF (def_p
, def
);
1853 tracked_var
= target_for_debug_bind (sym
);
1856 gimple note
= gimple_build_debug_bind (tracked_var
, def
, stmt
);
1857 /* If stmt ends the bb, insert the debug stmt on the single
1858 non-EH edge from the stmt. */
1859 if (gsi_one_before_end_p (gsi
) && stmt_ends_bb_p (stmt
))
1861 basic_block bb
= gsi_bb (gsi
);
1864 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1865 if (!(e
->flags
& EDGE_EH
))
1867 gcc_checking_assert (!ef
);
1870 /* If there are other predecessors to ef->dest, then
1871 there must be PHI nodes for the modified
1872 variable, and therefore there will be debug bind
1873 stmts after the PHI nodes. The debug bind notes
1874 we'd insert would force the creation of a new
1875 block (diverging codegen) and be redundant with
1876 the post-PHI bind stmts, so don't add them.
1878 As for the exit edge, there wouldn't be redundant
1879 bind stmts, but there wouldn't be a PC to bind
1880 them to either, so avoid diverging the CFG. */
1881 if (ef
&& single_pred_p (ef
->dest
)
1882 && ef
->dest
!= EXIT_BLOCK_PTR
)
1884 /* If there were PHI nodes in the node, we'd
1885 have to make sure the value we're binding
1886 doesn't need rewriting. But there shouldn't
1887 be PHI nodes in a single-predecessor block,
1888 so we just add the note. */
1889 gsi_insert_on_edge_immediate (ef
, note
);
1893 gsi_insert_after (&gsi
, note
, GSI_SAME_STMT
);
1897 register_new_update_single (def
, sym
);
1901 /* If DEF is a new name, register it as a new definition
1902 for all the names replaced by DEF. */
1903 if (is_new_name (def
))
1904 register_new_update_set (def
, names_replaced_by (def
));
1906 /* If DEF is an old name, register DEF as a new
1907 definition for itself. */
1908 if (is_old_name (def
))
1909 register_new_update_single (def
, def
);
1914 /* Update every variable used in the statement pointed-to by SI. The
1915 statement is assumed to be in SSA form already. Names in
1916 OLD_SSA_NAMES used by SI will be updated to their current reaching
1917 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1918 will be registered as a new definition for their corresponding name
1919 in OLD_SSA_NAMES. */
1922 rewrite_update_stmt (gimple stmt
, gimple_stmt_iterator gsi
)
1924 use_operand_p use_p
;
1925 def_operand_p def_p
;
1928 /* Only update marked statements. */
1929 if (!rewrite_uses_p (stmt
) && !register_defs_p (stmt
))
1932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1934 fprintf (dump_file
, "Updating SSA information for statement ");
1935 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1938 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1939 symbol is marked for renaming. */
1940 if (rewrite_uses_p (stmt
))
1942 if (is_gimple_debug (stmt
))
1944 bool failed
= false;
1946 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1947 if (!maybe_replace_use_in_debug_stmt (use_p
))
1955 /* DOM sometimes threads jumps in such a way that a
1956 debug stmt ends up referencing a SSA variable that no
1957 longer dominates the debug stmt, but such that all
1958 incoming definitions refer to the same definition in
1959 an earlier dominator. We could try to recover that
1960 definition somehow, but this will have to do for now.
1962 Introducing a default definition, which is what
1963 maybe_replace_use() would do in such cases, may
1964 modify code generation, for the otherwise-unused
1965 default definition would never go away, modifying SSA
1966 version numbers all over. */
1967 gimple_debug_bind_reset_value (stmt
);
1973 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1974 maybe_replace_use (use_p
);
1978 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1979 Also register definitions for names whose underlying symbol is
1980 marked for renaming. */
1981 if (register_defs_p (stmt
))
1982 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
1983 maybe_register_def (def_p
, stmt
, gsi
);
1987 /* Visit all the successor blocks of BB looking for PHI nodes. For
1988 every PHI node found, check if any of its arguments is in
1989 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1990 definition, replace it. */
1993 rewrite_update_phi_arguments (basic_block bb
)
1999 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2004 if (!bitmap_bit_p (blocks_with_phis_to_rewrite
, e
->dest
->index
))
2007 phis
= phis_to_rewrite
[e
->dest
->index
];
2008 FOR_EACH_VEC_ELT (phis
, i
, phi
)
2010 tree arg
, lhs_sym
, reaching_def
= NULL
;
2011 use_operand_p arg_p
;
2013 gcc_checking_assert (rewrite_uses_p (phi
));
2015 arg_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
);
2016 arg
= USE_FROM_PTR (arg_p
);
2018 if (arg
&& !DECL_P (arg
) && TREE_CODE (arg
) != SSA_NAME
)
2021 lhs_sym
= SSA_NAME_VAR (gimple_phi_result (phi
));
2023 if (arg
== NULL_TREE
)
2025 /* When updating a PHI node for a recently introduced
2026 symbol we may find NULL arguments. That's why we
2027 take the symbol from the LHS of the PHI node. */
2028 reaching_def
= get_reaching_def (lhs_sym
);
2033 tree sym
= DECL_P (arg
) ? arg
: SSA_NAME_VAR (arg
);
2035 if (marked_for_renaming (sym
))
2036 reaching_def
= get_reaching_def (sym
);
2037 else if (is_old_name (arg
))
2038 reaching_def
= get_reaching_def (arg
);
2041 /* Update the argument if there is a reaching def. */
2044 source_location locus
;
2045 int arg_i
= PHI_ARG_INDEX_FROM_USE (arg_p
);
2047 SET_USE (arg_p
, reaching_def
);
2049 /* Virtual operands do not need a location. */
2050 if (virtual_operand_p (reaching_def
))
2051 locus
= UNKNOWN_LOCATION
;
2054 gimple stmt
= SSA_NAME_DEF_STMT (reaching_def
);
2056 /* Single element PHI nodes behave like copies, so get the
2057 location from the phi argument. */
2058 if (gimple_code (stmt
) == GIMPLE_PHI
2059 && gimple_phi_num_args (stmt
) == 1)
2060 locus
= gimple_phi_arg_location (stmt
, 0);
2062 locus
= gimple_location (stmt
);
2065 gimple_phi_arg_set_location (phi
, arg_i
, locus
);
2069 if (e
->flags
& EDGE_ABNORMAL
)
2070 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p
)) = 1;
2075 class rewrite_update_dom_walker
: public dom_walker
2078 rewrite_update_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2080 virtual void before_dom_children (basic_block
);
2081 virtual void after_dom_children (basic_block
);
2084 /* Initialization of block data structures for the incremental SSA
2085 update pass. Create a block local stack of reaching definitions
2086 for new SSA names produced in this block (BLOCK_DEFS). Register
2087 new definitions for every PHI node in the block. */
2090 rewrite_update_dom_walker::before_dom_children (basic_block bb
)
2092 bool is_abnormal_phi
;
2093 gimple_stmt_iterator gsi
;
2095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2096 fprintf (dump_file
, "Registering new PHI nodes in block #%d\n",
2099 /* Mark the unwind point for this block. */
2100 block_defs_stack
.safe_push (NULL_TREE
);
2102 if (!bitmap_bit_p (blocks_to_update
, bb
->index
))
2105 /* Mark the LHS if any of the arguments flows through an abnormal
2107 is_abnormal_phi
= bb_has_abnormal_pred (bb
);
2109 /* If any of the PHI nodes is a replacement for a name in
2110 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2111 register it as a new definition for its corresponding name. Also
2112 register definitions for names whose underlying symbols are
2113 marked for renaming. */
2114 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2117 gimple phi
= gsi_stmt (gsi
);
2119 if (!register_defs_p (phi
))
2122 lhs
= gimple_phi_result (phi
);
2123 lhs_sym
= SSA_NAME_VAR (lhs
);
2125 if (marked_for_renaming (lhs_sym
))
2126 register_new_update_single (lhs
, lhs_sym
);
2130 /* If LHS is a new name, register a new definition for all
2131 the names replaced by LHS. */
2132 if (is_new_name (lhs
))
2133 register_new_update_set (lhs
, names_replaced_by (lhs
));
2135 /* If LHS is an OLD name, register it as a new definition
2137 if (is_old_name (lhs
))
2138 register_new_update_single (lhs
, lhs
);
2141 if (is_abnormal_phi
)
2142 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
) = 1;
2145 /* Step 2. Rewrite every variable used in each statement in the block. */
2146 if (bitmap_bit_p (interesting_blocks
, bb
->index
))
2148 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2149 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2150 rewrite_update_stmt (gsi_stmt (gsi
), gsi
);
2153 /* Step 3. Update PHI nodes. */
2154 rewrite_update_phi_arguments (bb
);
2157 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2158 the current reaching definition of every name re-written in BB to
2159 the original reaching definition before visiting BB. This
2160 unwinding must be done in the opposite order to what is done in
2161 register_new_update_set. */
2164 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
2166 while (block_defs_stack
.length () > 0)
2168 tree var
= block_defs_stack
.pop ();
2171 /* NULL indicates the unwind stop point for this block (see
2172 rewrite_update_enter_block). */
2176 saved_def
= block_defs_stack
.pop ();
2177 get_common_info (var
)->current_def
= saved_def
;
2182 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2185 ENTRY indicates the block where to start. Every block dominated by
2186 ENTRY will be rewritten.
2188 WHAT indicates what actions will be taken by the renamer (see enum
2191 BLOCKS are the set of interesting blocks for the dominator walker
2192 to process. If this set is NULL, then all the nodes dominated
2193 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2194 are not present in BLOCKS are ignored. */
2197 rewrite_blocks (basic_block entry
, enum rewrite_mode what
)
2199 /* Rewrite all the basic blocks in the program. */
2200 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS
);
2202 block_defs_stack
.create (10);
2204 /* Recursively walk the dominator tree rewriting each statement in
2205 each basic block. */
2206 if (what
== REWRITE_ALL
)
2207 rewrite_dom_walker (CDI_DOMINATORS
).walk (entry
);
2208 else if (what
== REWRITE_UPDATE
)
2209 rewrite_update_dom_walker (CDI_DOMINATORS
).walk (entry
);
2213 /* Debugging dumps. */
2214 if (dump_file
&& (dump_flags
& TDF_STATS
))
2216 dump_dfa_stats (dump_file
);
2217 if (var_infos
.is_created ())
2218 dump_tree_ssa_stats (dump_file
);
2221 block_defs_stack
.release ();
2223 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS
);
2226 class mark_def_dom_walker
: public dom_walker
2229 mark_def_dom_walker (cdi_direction direction
);
2230 ~mark_def_dom_walker ();
2232 virtual void before_dom_children (basic_block
);
2235 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2236 large enough to accommodate all the variables referenced in the
2237 function, not just the ones we are renaming. */
2241 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction
)
2242 : dom_walker (direction
), kills_ (BITMAP_ALLOC (NULL
))
2246 mark_def_dom_walker::~mark_def_dom_walker ()
2248 BITMAP_FREE (kills_
);
2251 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2252 at the start of each block, and call mark_def_sites for each statement. */
2255 mark_def_dom_walker::before_dom_children (basic_block bb
)
2257 gimple_stmt_iterator gsi
;
2259 bitmap_clear (kills_
);
2260 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2261 mark_def_sites (bb
, gsi_stmt (gsi
), kills_
);
2264 /* Initialize internal data needed during renaming. */
2267 init_ssa_renamer (void)
2269 cfun
->gimple_df
->in_ssa_p
= false;
2271 /* Allocate memory for the DEF_BLOCKS hash table. */
2272 gcc_assert (!var_infos
.is_created ());
2273 var_infos
.create (vec_safe_length (cfun
->local_decls
));
2275 bitmap_obstack_initialize (&update_ssa_obstack
);
2279 /* Deallocate internal data structures used by the renamer. */
2282 fini_ssa_renamer (void)
2284 if (var_infos
.is_created ())
2285 var_infos
.dispose ();
2287 bitmap_obstack_release (&update_ssa_obstack
);
2289 cfun
->gimple_df
->ssa_renaming_needed
= 0;
2290 cfun
->gimple_df
->rename_vops
= 0;
2291 cfun
->gimple_df
->in_ssa_p
= true;
2294 /* Main entry point into the SSA builder. The renaming process
2295 proceeds in four main phases:
2297 1- Compute dominance frontier and immediate dominators, needed to
2298 insert PHI nodes and rename the function in dominator tree
2301 2- Find and mark all the blocks that define variables.
2303 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2305 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2307 Steps 3 and 4 are done using the dominator tree walker
2308 (walk_dominator_tree). */
2311 rewrite_into_ssa (void)
2317 /* Initialize operand data structures. */
2318 init_ssa_operands (cfun
);
2320 /* Initialize internal data needed by the renamer. */
2321 init_ssa_renamer ();
2323 /* Initialize the set of interesting blocks. The callback
2324 mark_def_sites will add to this set those blocks that the renamer
2326 interesting_blocks
= sbitmap_alloc (last_basic_block
);
2327 bitmap_clear (interesting_blocks
);
2329 /* Initialize dominance frontier. */
2330 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
2332 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
2334 /* 1- Compute dominance frontiers. */
2335 calculate_dominance_info (CDI_DOMINATORS
);
2336 compute_dominance_frontiers (dfs
);
2338 /* 2- Find and mark definition sites. */
2339 mark_def_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
2341 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2342 insert_phi_nodes (dfs
);
2344 /* 4- Rename all the blocks. */
2345 rewrite_blocks (ENTRY_BLOCK_PTR
, REWRITE_ALL
);
2347 /* Free allocated memory. */
2349 bitmap_clear (&dfs
[bb
->index
]);
2352 sbitmap_free (interesting_blocks
);
2354 fini_ssa_renamer ();
2356 /* Try to get rid of all gimplifier generated temporaries by making
2357 its SSA names anonymous. This way we can garbage collect them
2358 all after removing unused locals which we do in our TODO. */
2359 for (i
= 1; i
< num_ssa_names
; ++i
)
2361 tree decl
, name
= ssa_name (i
);
2363 || SSA_NAME_IS_DEFAULT_DEF (name
))
2365 decl
= SSA_NAME_VAR (name
);
2367 && TREE_CODE (decl
) == VAR_DECL
2368 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl
)
2369 && DECL_ARTIFICIAL (decl
)
2370 && DECL_IGNORED_P (decl
)
2371 && !DECL_NAME (decl
))
2372 SET_SSA_NAME_VAR_OR_IDENTIFIER (name
, NULL_TREE
);
2378 /* Gate for IPCP optimization. */
2381 gate_into_ssa (void)
2383 /* Do nothing for funcions that was produced already in SSA form. */
2384 return !(cfun
->curr_properties
& PROP_ssa
);
2389 const pass_data pass_data_build_ssa
=
2391 GIMPLE_PASS
, /* type */
2393 OPTGROUP_NONE
, /* optinfo_flags */
2394 true, /* has_gate */
2395 true, /* has_execute */
2396 TV_TREE_SSA_OTHER
, /* tv_id */
2397 PROP_cfg
, /* properties_required */
2398 PROP_ssa
, /* properties_provided */
2399 0, /* properties_destroyed */
2400 0, /* todo_flags_start */
2401 ( TODO_verify_ssa
| TODO_remove_unused_locals
), /* todo_flags_finish */
2404 class pass_build_ssa
: public gimple_opt_pass
2407 pass_build_ssa(gcc::context
*ctxt
)
2408 : gimple_opt_pass(pass_data_build_ssa
, ctxt
)
2411 /* opt_pass methods: */
2412 bool gate () { return gate_into_ssa (); }
2413 unsigned int execute () { return rewrite_into_ssa (); }
2415 }; // class pass_build_ssa
2420 make_pass_build_ssa (gcc::context
*ctxt
)
2422 return new pass_build_ssa (ctxt
);
2426 /* Mark the definition of VAR at STMT and BB as interesting for the
2427 renamer. BLOCKS is the set of blocks that need updating. */
2430 mark_def_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2432 gcc_checking_assert (bitmap_bit_p (blocks_to_update
, bb
->index
));
2433 set_register_defs (stmt
, true);
2437 bool is_phi_p
= gimple_code (stmt
) == GIMPLE_PHI
;
2439 set_def_block (var
, bb
, is_phi_p
);
2441 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2442 site for both itself and all the old names replaced by it. */
2443 if (TREE_CODE (var
) == SSA_NAME
&& is_new_name (var
))
2447 bitmap set
= names_replaced_by (var
);
2449 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
2450 set_def_block (ssa_name (i
), bb
, is_phi_p
);
2456 /* Mark the use of VAR at STMT and BB as interesting for the
2457 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2461 mark_use_interesting (tree var
, gimple stmt
, basic_block bb
, bool insert_phi_p
)
2463 basic_block def_bb
= gimple_bb (stmt
);
2465 mark_block_for_update (def_bb
);
2466 mark_block_for_update (bb
);
2468 if (gimple_code (stmt
) == GIMPLE_PHI
)
2469 mark_phi_for_rewrite (def_bb
, stmt
);
2472 set_rewrite_uses (stmt
, true);
2474 if (is_gimple_debug (stmt
))
2478 /* If VAR has not been defined in BB, then it is live-on-entry
2479 to BB. Note that we cannot just use the block holding VAR's
2480 definition because if VAR is one of the names in OLD_SSA_NAMES,
2481 it will have several definitions (itself and all the names that
2485 struct def_blocks_d
*db_p
= get_def_blocks_for (get_common_info (var
));
2486 if (!bitmap_bit_p (db_p
->def_blocks
, bb
->index
))
2487 set_livein_block (var
, bb
);
2492 /* Do a dominator walk starting at BB processing statements that
2493 reference symbols in SSA operands. This is very similar to
2494 mark_def_sites, but the scan handles statements whose operands may
2495 already be SSA names.
2497 If INSERT_PHI_P is true, mark those uses as live in the
2498 corresponding block. This is later used by the PHI placement
2499 algorithm to make PHI pruning decisions.
2501 FIXME. Most of this would be unnecessary if we could associate a
2502 symbol to all the SSA names that reference it. But that
2503 sounds like it would be expensive to maintain. Still, it
2504 would be interesting to see if it makes better sense to do
2508 prepare_block_for_update (basic_block bb
, bool insert_phi_p
)
2511 gimple_stmt_iterator si
;
2515 mark_block_for_update (bb
);
2517 /* Process PHI nodes marking interesting those that define or use
2518 the symbols that we are interested in. */
2519 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
2521 gimple phi
= gsi_stmt (si
);
2522 tree lhs_sym
, lhs
= gimple_phi_result (phi
);
2524 if (TREE_CODE (lhs
) == SSA_NAME
2525 && (! virtual_operand_p (lhs
)
2526 || ! cfun
->gimple_df
->rename_vops
))
2529 lhs_sym
= DECL_P (lhs
) ? lhs
: SSA_NAME_VAR (lhs
);
2530 mark_for_renaming (lhs_sym
);
2531 mark_def_interesting (lhs_sym
, phi
, bb
, insert_phi_p
);
2533 /* Mark the uses in phi nodes as interesting. It would be more correct
2534 to process the arguments of the phi nodes of the successor edges of
2535 BB at the end of prepare_block_for_update, however, that turns out
2536 to be significantly more expensive. Doing it here is conservatively
2537 correct -- it may only cause us to believe a value to be live in a
2538 block that also contains its definition, and thus insert a few more
2539 phi nodes for it. */
2540 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2541 mark_use_interesting (lhs_sym
, phi
, e
->src
, insert_phi_p
);
2544 /* Process the statements. */
2545 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2549 use_operand_p use_p
;
2550 def_operand_p def_p
;
2552 stmt
= gsi_stmt (si
);
2554 if (cfun
->gimple_df
->rename_vops
2555 && gimple_vuse (stmt
))
2557 tree use
= gimple_vuse (stmt
);
2558 tree sym
= DECL_P (use
) ? use
: SSA_NAME_VAR (use
);
2559 mark_for_renaming (sym
);
2560 mark_use_interesting (sym
, stmt
, bb
, insert_phi_p
);
2563 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, i
, SSA_OP_USE
)
2565 tree use
= USE_FROM_PTR (use_p
);
2568 mark_for_renaming (use
);
2569 mark_use_interesting (use
, stmt
, bb
, insert_phi_p
);
2572 if (cfun
->gimple_df
->rename_vops
2573 && gimple_vdef (stmt
))
2575 tree def
= gimple_vdef (stmt
);
2576 tree sym
= DECL_P (def
) ? def
: SSA_NAME_VAR (def
);
2577 mark_for_renaming (sym
);
2578 mark_def_interesting (sym
, stmt
, bb
, insert_phi_p
);
2581 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, i
, SSA_OP_DEF
)
2583 tree def
= DEF_FROM_PTR (def_p
);
2586 mark_for_renaming (def
);
2587 mark_def_interesting (def
, stmt
, bb
, insert_phi_p
);
2591 /* Now visit all the blocks dominated by BB. */
2592 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2594 son
= next_dom_son (CDI_DOMINATORS
, son
))
2595 prepare_block_for_update (son
, insert_phi_p
);
2599 /* Helper for prepare_names_to_update. Mark all the use sites for
2600 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2601 prepare_names_to_update. */
2604 prepare_use_sites_for (tree name
, bool insert_phi_p
)
2606 use_operand_p use_p
;
2607 imm_use_iterator iter
;
2609 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
2611 gimple stmt
= USE_STMT (use_p
);
2612 basic_block bb
= gimple_bb (stmt
);
2614 if (gimple_code (stmt
) == GIMPLE_PHI
)
2616 int ix
= PHI_ARG_INDEX_FROM_USE (use_p
);
2617 edge e
= gimple_phi_arg_edge (stmt
, ix
);
2618 mark_use_interesting (name
, stmt
, e
->src
, insert_phi_p
);
2622 /* For regular statements, mark this as an interesting use
2624 mark_use_interesting (name
, stmt
, bb
, insert_phi_p
);
2630 /* Helper for prepare_names_to_update. Mark the definition site for
2631 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2632 prepare_names_to_update. */
2635 prepare_def_site_for (tree name
, bool insert_phi_p
)
2640 gcc_checking_assert (names_to_release
== NULL
2641 || !bitmap_bit_p (names_to_release
,
2642 SSA_NAME_VERSION (name
)));
2644 stmt
= SSA_NAME_DEF_STMT (name
);
2645 bb
= gimple_bb (stmt
);
2648 gcc_checking_assert (bb
->index
< last_basic_block
);
2649 mark_block_for_update (bb
);
2650 mark_def_interesting (name
, stmt
, bb
, insert_phi_p
);
2655 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2656 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2657 PHI nodes for newly created names. */
2660 prepare_names_to_update (bool insert_phi_p
)
2664 sbitmap_iterator sbi
;
2666 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2667 remove it from NEW_SSA_NAMES so that we don't try to visit its
2668 defining basic block (which most likely doesn't exist). Notice
2669 that we cannot do the same with names in OLD_SSA_NAMES because we
2670 want to replace existing instances. */
2671 if (names_to_release
)
2672 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2673 bitmap_clear_bit (new_ssa_names
, i
);
2675 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2676 names may be considered to be live-in on blocks that contain
2677 definitions for their replacements. */
2678 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2679 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2681 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2682 OLD_SSA_NAMES, but we have to ignore its definition site. */
2683 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
2685 if (names_to_release
== NULL
|| !bitmap_bit_p (names_to_release
, i
))
2686 prepare_def_site_for (ssa_name (i
), insert_phi_p
);
2687 prepare_use_sites_for (ssa_name (i
), insert_phi_p
);
2692 /* Dump all the names replaced by NAME to FILE. */
2695 dump_names_replaced_by (FILE *file
, tree name
)
2701 print_generic_expr (file
, name
, 0);
2702 fprintf (file
, " -> { ");
2704 old_set
= names_replaced_by (name
);
2705 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, i
, bi
)
2707 print_generic_expr (file
, ssa_name (i
), 0);
2708 fprintf (file
, " ");
2711 fprintf (file
, "}\n");
2715 /* Dump all the names replaced by NAME to stderr. */
2718 debug_names_replaced_by (tree name
)
2720 dump_names_replaced_by (stderr
, name
);
2724 /* Dump SSA update information to FILE. */
2727 dump_update_ssa (FILE *file
)
2732 if (!need_ssa_update_p (cfun
))
2735 if (new_ssa_names
&& bitmap_first_set_bit (new_ssa_names
) >= 0)
2737 sbitmap_iterator sbi
;
2739 fprintf (file
, "\nSSA replacement table\n");
2740 fprintf (file
, "N_i -> { O_1 ... O_j } means that N_i replaces "
2741 "O_1, ..., O_j\n\n");
2743 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names
, 0, i
, sbi
)
2744 dump_names_replaced_by (file
, ssa_name (i
));
2747 if (symbols_to_rename_set
&& !bitmap_empty_p (symbols_to_rename_set
))
2749 fprintf (file
, "\nSymbols to be put in SSA form\n");
2750 dump_decl_set (file
, symbols_to_rename_set
);
2751 fprintf (file
, "\n");
2754 if (names_to_release
&& !bitmap_empty_p (names_to_release
))
2756 fprintf (file
, "\nSSA names to release after updating the SSA web\n\n");
2757 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2759 print_generic_expr (file
, ssa_name (i
), 0);
2760 fprintf (file
, " ");
2762 fprintf (file
, "\n");
2767 /* Dump SSA update information to stderr. */
2770 debug_update_ssa (void)
2772 dump_update_ssa (stderr
);
2776 /* Initialize data structures used for incremental SSA updates. */
2779 init_update_ssa (struct function
*fn
)
2781 /* Reserve more space than the current number of names. The calls to
2782 add_new_name_mapping are typically done after creating new SSA
2783 names, so we'll need to reallocate these arrays. */
2784 old_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2785 bitmap_clear (old_ssa_names
);
2787 new_ssa_names
= sbitmap_alloc (num_ssa_names
+ NAME_SETS_GROWTH_FACTOR
);
2788 bitmap_clear (new_ssa_names
);
2790 bitmap_obstack_initialize (&update_ssa_obstack
);
2792 names_to_release
= NULL
;
2793 update_ssa_initialized_fn
= fn
;
2797 /* Deallocate data structures used for incremental SSA updates. */
2800 delete_update_ssa (void)
2805 sbitmap_free (old_ssa_names
);
2806 old_ssa_names
= NULL
;
2808 sbitmap_free (new_ssa_names
);
2809 new_ssa_names
= NULL
;
2811 BITMAP_FREE (symbols_to_rename_set
);
2812 symbols_to_rename_set
= NULL
;
2813 symbols_to_rename
.release ();
2815 if (names_to_release
)
2817 EXECUTE_IF_SET_IN_BITMAP (names_to_release
, 0, i
, bi
)
2818 release_ssa_name (ssa_name (i
));
2819 BITMAP_FREE (names_to_release
);
2822 clear_ssa_name_info ();
2824 fini_ssa_renamer ();
2826 if (blocks_with_phis_to_rewrite
)
2827 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite
, 0, i
, bi
)
2829 gimple_vec phis
= phis_to_rewrite
[i
];
2831 phis_to_rewrite
[i
].create (0);
2834 BITMAP_FREE (blocks_with_phis_to_rewrite
);
2835 BITMAP_FREE (blocks_to_update
);
2837 update_ssa_initialized_fn
= NULL
;
2841 /* Create a new name for OLD_NAME in statement STMT and replace the
2842 operand pointed to by DEF_P with the newly created name. If DEF_P
2843 is NULL then STMT should be a GIMPLE assignment.
2844 Return the new name and register the replacement mapping <NEW, OLD> in
2845 update_ssa's tables. */
2848 create_new_def_for (tree old_name
, gimple stmt
, def_operand_p def
)
2852 timevar_push (TV_TREE_SSA_INCREMENTAL
);
2854 if (!update_ssa_initialized_fn
)
2855 init_update_ssa (cfun
);
2857 gcc_assert (update_ssa_initialized_fn
== cfun
);
2859 new_name
= duplicate_ssa_name (old_name
, stmt
);
2861 SET_DEF (def
, new_name
);
2863 gimple_assign_set_lhs (stmt
, new_name
);
2865 if (gimple_code (stmt
) == GIMPLE_PHI
)
2867 basic_block bb
= gimple_bb (stmt
);
2869 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2870 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name
) = bb_has_abnormal_pred (bb
);
2873 add_new_name_mapping (new_name
, old_name
);
2875 /* For the benefit of passes that will be updating the SSA form on
2876 their own, set the current reaching definition of OLD_NAME to be
2878 get_ssa_name_ann (old_name
)->info
.current_def
= new_name
;
2880 timevar_pop (TV_TREE_SSA_INCREMENTAL
);
2886 /* Mark virtual operands of FN for renaming by update_ssa. */
2889 mark_virtual_operands_for_renaming (struct function
*fn
)
2891 fn
->gimple_df
->ssa_renaming_needed
= 1;
2892 fn
->gimple_df
->rename_vops
= 1;
2896 /* Return true if there is any work to be done by update_ssa
2900 need_ssa_update_p (struct function
*fn
)
2902 gcc_assert (fn
!= NULL
);
2903 return (update_ssa_initialized_fn
== fn
2904 || (fn
->gimple_df
&& fn
->gimple_df
->ssa_renaming_needed
));
2907 /* Return true if name N has been registered in the replacement table. */
2910 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED
)
2912 if (!update_ssa_initialized_fn
)
2915 gcc_assert (update_ssa_initialized_fn
== cfun
);
2917 return is_new_name (n
) || is_old_name (n
);
2921 /* Mark NAME to be released after update_ssa has finished. */
2924 release_ssa_name_after_update_ssa (tree name
)
2926 gcc_assert (cfun
&& update_ssa_initialized_fn
== cfun
);
2928 if (names_to_release
== NULL
)
2929 names_to_release
= BITMAP_ALLOC (NULL
);
2931 bitmap_set_bit (names_to_release
, SSA_NAME_VERSION (name
));
2935 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2936 frontier information. BLOCKS is the set of blocks to be updated.
2938 This is slightly different than the regular PHI insertion
2939 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2940 real names (i.e., GIMPLE registers) are inserted:
2942 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2943 nodes inside the region affected by the block that defines VAR
2944 and the blocks that define all its replacements. All these
2945 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2947 First, we compute the entry point to the region (ENTRY). This is
2948 given by the nearest common dominator to all the definition
2949 blocks. When computing the iterated dominance frontier (IDF), any
2950 block not strictly dominated by ENTRY is ignored.
2952 We then call the standard PHI insertion algorithm with the pruned
2955 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2956 names is not pruned. PHI nodes are inserted at every IDF block. */
2959 insert_updated_phi_nodes_for (tree var
, bitmap_head
*dfs
, bitmap blocks
,
2960 unsigned update_flags
)
2963 struct def_blocks_d
*db
;
2964 bitmap idf
, pruned_idf
;
2968 if (TREE_CODE (var
) == SSA_NAME
)
2969 gcc_checking_assert (is_old_name (var
));
2971 gcc_checking_assert (marked_for_renaming (var
));
2973 /* Get all the definition sites for VAR. */
2974 db
= find_def_blocks_for (var
);
2976 /* No need to do anything if there were no definitions to VAR. */
2977 if (db
== NULL
|| bitmap_empty_p (db
->def_blocks
))
2980 /* Compute the initial iterated dominance frontier. */
2981 idf
= compute_idf (db
->def_blocks
, dfs
);
2982 pruned_idf
= BITMAP_ALLOC (NULL
);
2984 if (TREE_CODE (var
) == SSA_NAME
)
2986 if (update_flags
== TODO_update_ssa
)
2988 /* If doing regular SSA updates for GIMPLE registers, we are
2989 only interested in IDF blocks dominated by the nearest
2990 common dominator of all the definition blocks. */
2991 entry
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
2993 if (entry
!= ENTRY_BLOCK_PTR
)
2994 EXECUTE_IF_SET_IN_BITMAP (idf
, 0, i
, bi
)
2995 if (BASIC_BLOCK (i
) != entry
2996 && dominated_by_p (CDI_DOMINATORS
, BASIC_BLOCK (i
), entry
))
2997 bitmap_set_bit (pruned_idf
, i
);
3001 /* Otherwise, do not prune the IDF for VAR. */
3002 gcc_checking_assert (update_flags
== TODO_update_ssa_full_phi
);
3003 bitmap_copy (pruned_idf
, idf
);
3008 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3009 for the first time, so we need to compute the full IDF for
3011 bitmap_copy (pruned_idf
, idf
);
3014 if (!bitmap_empty_p (pruned_idf
))
3016 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3017 are included in the region to be updated. The feeding blocks
3018 are important to guarantee that the PHI arguments are renamed
3021 /* FIXME, this is not needed if we are updating symbols. We are
3022 already starting at the ENTRY block anyway. */
3023 bitmap_ior_into (blocks
, pruned_idf
);
3024 EXECUTE_IF_SET_IN_BITMAP (pruned_idf
, 0, i
, bi
)
3028 basic_block bb
= BASIC_BLOCK (i
);
3030 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3031 if (e
->src
->index
>= 0)
3032 bitmap_set_bit (blocks
, e
->src
->index
);
3035 insert_phi_nodes_for (var
, pruned_idf
, true);
3038 BITMAP_FREE (pruned_idf
);
3042 /* Sort symbols_to_rename after their DECL_UID. */
3045 insert_updated_phi_nodes_compare_uids (const void *a
, const void *b
)
3047 const_tree syma
= *(const const_tree
*)a
;
3048 const_tree symb
= *(const const_tree
*)b
;
3049 if (DECL_UID (syma
) == DECL_UID (symb
))
3051 return DECL_UID (syma
) < DECL_UID (symb
) ? -1 : 1;
3054 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3055 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3057 1- The names in OLD_SSA_NAMES dominated by the definitions of
3058 NEW_SSA_NAMES are all re-written to be reached by the
3059 appropriate definition from NEW_SSA_NAMES.
3061 2- If needed, new PHI nodes are added to the iterated dominance
3062 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3064 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3065 calling create_new_def_for to create new defs for names that the
3066 caller wants to replace.
3068 The caller cretaes the new names to be inserted and the names that need
3069 to be replaced by calling create_new_def_for for each old definition
3070 to be replaced. Note that the function assumes that the
3071 new defining statement has already been inserted in the IL.
3073 For instance, given the following code:
3076 2 x_1 = PHI (0, x_5)
3087 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3090 2 x_1 = PHI (0, x_5)
3103 We want to replace all the uses of x_1 with the new definitions of
3104 x_10 and x_11. Note that the only uses that should be replaced are
3105 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3106 *not* be replaced (this is why we cannot just mark symbol 'x' for
3109 Additionally, we may need to insert a PHI node at line 11 because
3110 that is a merge point for x_10 and x_11. So the use of x_1 at line
3111 11 will be replaced with the new PHI node. The insertion of PHI
3112 nodes is optional. They are not strictly necessary to preserve the
3113 SSA form, and depending on what the caller inserted, they may not
3114 even be useful for the optimizers. UPDATE_FLAGS controls various
3115 aspects of how update_ssa operates, see the documentation for
3116 TODO_update_ssa*. */
3119 update_ssa (unsigned update_flags
)
3121 basic_block bb
, start_bb
;
3125 sbitmap_iterator sbi
;
3128 /* Only one update flag should be set. */
3129 gcc_assert (update_flags
== TODO_update_ssa
3130 || update_flags
== TODO_update_ssa_no_phi
3131 || update_flags
== TODO_update_ssa_full_phi
3132 || update_flags
== TODO_update_ssa_only_virtuals
);
3134 if (!need_ssa_update_p (cfun
))
3137 timevar_push (TV_TREE_SSA_INCREMENTAL
);
3139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3140 fprintf (dump_file
, "\nUpdating SSA:\n");
3142 if (!update_ssa_initialized_fn
)
3143 init_update_ssa (cfun
);
3144 else if (update_flags
== TODO_update_ssa_only_virtuals
)
3146 /* If we only need to update virtuals, remove all the mappings for
3147 real names before proceeding. The caller is responsible for
3148 having dealt with the name mappings before calling update_ssa. */
3149 bitmap_clear (old_ssa_names
);
3150 bitmap_clear (new_ssa_names
);
3153 gcc_assert (update_ssa_initialized_fn
== cfun
);
3155 blocks_with_phis_to_rewrite
= BITMAP_ALLOC (NULL
);
3156 if (!phis_to_rewrite
.exists ())
3157 phis_to_rewrite
.create (last_basic_block
+ 1);
3158 blocks_to_update
= BITMAP_ALLOC (NULL
);
3160 /* Ensure that the dominance information is up-to-date. */
3161 calculate_dominance_info (CDI_DOMINATORS
);
3163 insert_phi_p
= (update_flags
!= TODO_update_ssa_no_phi
);
3165 /* If there are names defined in the replacement table, prepare
3166 definition and use sites for all the names in NEW_SSA_NAMES and
3168 if (bitmap_first_set_bit (new_ssa_names
) >= 0)
3170 prepare_names_to_update (insert_phi_p
);
3172 /* If all the names in NEW_SSA_NAMES had been marked for
3173 removal, and there are no symbols to rename, then there's
3174 nothing else to do. */
3175 if (bitmap_first_set_bit (new_ssa_names
) < 0
3176 && !cfun
->gimple_df
->ssa_renaming_needed
)
3180 /* Next, determine the block at which to start the renaming process. */
3181 if (cfun
->gimple_df
->ssa_renaming_needed
)
3183 /* If we rename bare symbols initialize the mapping to
3184 auxiliar info we need to keep track of. */
3185 var_infos
.create (47);
3187 /* If we have to rename some symbols from scratch, we need to
3188 start the process at the root of the CFG. FIXME, it should
3189 be possible to determine the nearest block that had a
3190 definition for each of the symbols that are marked for
3191 updating. For now this seems more work than it's worth. */
3192 start_bb
= ENTRY_BLOCK_PTR
;
3194 /* Traverse the CFG looking for existing definitions and uses of
3195 symbols in SSA operands. Mark interesting blocks and
3196 statements and set local live-in information for the PHI
3197 placement heuristics. */
3198 prepare_block_for_update (start_bb
, insert_phi_p
);
3200 #ifdef ENABLE_CHECKING
3201 for (i
= 1; i
< num_ssa_names
; ++i
)
3203 tree name
= ssa_name (i
);
3205 || virtual_operand_p (name
))
3208 /* For all but virtual operands, which do not have SSA names
3209 with overlapping life ranges, ensure that symbols marked
3210 for renaming do not have existing SSA names associated with
3211 them as we do not re-write them out-of-SSA before going
3212 into SSA for the remaining symbol uses. */
3213 if (marked_for_renaming (SSA_NAME_VAR (name
)))
3215 fprintf (stderr
, "Existing SSA name for symbol marked for "
3217 print_generic_expr (stderr
, name
, TDF_SLIM
);
3218 fprintf (stderr
, "\n");
3219 internal_error ("SSA corruption");
3226 /* Otherwise, the entry block to the region is the nearest
3227 common dominator for the blocks in BLOCKS. */
3228 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3232 /* If requested, insert PHI nodes at the iterated dominance frontier
3233 of every block, creating new definitions for names in OLD_SSA_NAMES
3234 and for symbols found. */
3239 /* If the caller requested PHI nodes to be added, compute
3240 dominance frontiers. */
3241 dfs
= XNEWVEC (bitmap_head
, last_basic_block
);
3243 bitmap_initialize (&dfs
[bb
->index
], &bitmap_default_obstack
);
3244 compute_dominance_frontiers (dfs
);
3246 if (bitmap_first_set_bit (old_ssa_names
) >= 0)
3248 sbitmap_iterator sbi
;
3250 /* insert_update_phi_nodes_for will call add_new_name_mapping
3251 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3252 will grow while we are traversing it (but it will not
3253 gain any new members). Copy OLD_SSA_NAMES to a temporary
3255 sbitmap tmp
= sbitmap_alloc (SBITMAP_SIZE (old_ssa_names
));
3256 bitmap_copy (tmp
, old_ssa_names
);
3257 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, sbi
)
3258 insert_updated_phi_nodes_for (ssa_name (i
), dfs
, blocks_to_update
,
3263 symbols_to_rename
.qsort (insert_updated_phi_nodes_compare_uids
);
3264 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3265 insert_updated_phi_nodes_for (sym
, dfs
, blocks_to_update
,
3269 bitmap_clear (&dfs
[bb
->index
]);
3272 /* Insertion of PHI nodes may have added blocks to the region.
3273 We need to re-compute START_BB to include the newly added
3275 if (start_bb
!= ENTRY_BLOCK_PTR
)
3276 start_bb
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3280 /* Reset the current definition for name and symbol before renaming
3282 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names
, 0, i
, sbi
)
3283 get_ssa_name_ann (ssa_name (i
))->info
.current_def
= NULL_TREE
;
3285 FOR_EACH_VEC_ELT (symbols_to_rename
, i
, sym
)
3286 get_var_info (sym
)->info
.current_def
= NULL_TREE
;
3288 /* Now start the renaming process at START_BB. */
3289 interesting_blocks
= sbitmap_alloc (last_basic_block
);
3290 bitmap_clear (interesting_blocks
);
3291 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3292 bitmap_set_bit (interesting_blocks
, i
);
3294 rewrite_blocks (start_bb
, REWRITE_UPDATE
);
3296 sbitmap_free (interesting_blocks
);
3298 /* Debugging dumps. */
3304 dump_update_ssa (dump_file
);
3306 fprintf (dump_file
, "Incremental SSA update started at block: %d\n",
3310 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3312 fprintf (dump_file
, "Number of blocks in CFG: %d\n", last_basic_block
);
3313 fprintf (dump_file
, "Number of blocks to update: %d (%3.0f%%)\n",
3314 c
, PERCENT (c
, last_basic_block
));
3316 if (dump_flags
& TDF_DETAILS
)
3318 fprintf (dump_file
, "Affected blocks:");
3319 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update
, 0, i
, bi
)
3320 fprintf (dump_file
, " %u", i
);
3321 fprintf (dump_file
, "\n");
3324 fprintf (dump_file
, "\n\n");
3327 /* Free allocated memory. */
3329 delete_update_ssa ();
3331 timevar_pop (TV_TREE_SSA_INCREMENTAL
);