gcc/
[official-gcc.git] / gcc / tree-into-ssa.c
blob24cca2cf9b1fdaefd5539fa989267c1ae7c1dd37
1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2015 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "alias.h"
26 #include "symtab.h"
27 #include "tree.h"
28 #include "fold-const.h"
29 #include "flags.h"
30 #include "tm_p.h"
31 #include "langhooks.h"
32 #include "predict.h"
33 #include "hard-reg-set.h"
34 #include "function.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "cfganal.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
40 #include "tree-ssa-alias.h"
41 #include "internal-fn.h"
42 #include "gimple-expr.h"
43 #include "gimple.h"
44 #include "gimple-iterator.h"
45 #include "gimple-ssa.h"
46 #include "tree-cfg.h"
47 #include "tree-phinodes.h"
48 #include "ssa-iterators.h"
49 #include "stringpool.h"
50 #include "tree-ssanames.h"
51 #include "tree-into-ssa.h"
52 #include "rtl.h"
53 #include "insn-config.h"
54 #include "expmed.h"
55 #include "dojump.h"
56 #include "explow.h"
57 #include "calls.h"
58 #include "emit-rtl.h"
59 #include "varasm.h"
60 #include "stmt.h"
61 #include "expr.h"
62 #include "tree-dfa.h"
63 #include "tree-ssa.h"
64 #include "tree-inline.h"
65 #include "tree-pass.h"
66 #include "cfgloop.h"
67 #include "domwalk.h"
68 #include "params.h"
69 #include "diagnostic-core.h"
71 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
73 /* This file builds the SSA form for a function as described in:
74 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
75 Computing Static Single Assignment Form and the Control Dependence
76 Graph. ACM Transactions on Programming Languages and Systems,
77 13(4):451-490, October 1991. */
79 /* Structure to map a variable VAR to the set of blocks that contain
80 definitions for VAR. */
81 struct def_blocks_d
83 /* Blocks that contain definitions of VAR. Bit I will be set if the
84 Ith block contains a definition of VAR. */
85 bitmap def_blocks;
87 /* Blocks that contain a PHI node for VAR. */
88 bitmap phi_blocks;
90 /* Blocks where VAR is live-on-entry. Similar semantics as
91 DEF_BLOCKS. */
92 bitmap livein_blocks;
95 typedef struct def_blocks_d *def_blocks_p;
98 /* Stack of trees used to restore the global currdefs to its original
99 state after completing rewriting of a block and its dominator
100 children. Its elements have the following properties:
102 - An SSA_NAME (N) indicates that the current definition of the
103 underlying variable should be set to the given SSA_NAME. If the
104 symbol associated with the SSA_NAME is not a GIMPLE register, the
105 next slot in the stack must be a _DECL node (SYM). In this case,
106 the name N in the previous slot is the current reaching
107 definition for SYM.
109 - A _DECL node indicates that the underlying variable has no
110 current definition.
112 - A NULL node at the top entry is used to mark the last slot
113 associated with the current block. */
114 static vec<tree> block_defs_stack;
117 /* Set of existing SSA names being replaced by update_ssa. */
118 static sbitmap old_ssa_names;
120 /* Set of new SSA names being added by update_ssa. Note that both
121 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
122 the operations done on them are presence tests. */
123 static sbitmap new_ssa_names;
125 static sbitmap interesting_blocks;
127 /* Set of SSA names that have been marked to be released after they
128 were registered in the replacement table. They will be finally
129 released after we finish updating the SSA web. */
130 static bitmap names_to_release;
132 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
133 the to basic block with index I. Allocated once per compilation, *not*
134 released between different functions. */
135 static vec< vec<gphi *> > phis_to_rewrite;
137 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
138 static bitmap blocks_with_phis_to_rewrite;
140 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
141 to grow as the callers to create_new_def_for will create new names on
142 the fly.
143 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
144 need to find a reasonable growth strategy. */
145 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
148 /* The function the SSA updating data structures have been initialized for.
149 NULL if they need to be initialized by create_new_def_for. */
150 static struct function *update_ssa_initialized_fn = NULL;
152 /* Global data to attach to the main dominator walk structure. */
153 struct mark_def_sites_global_data
155 /* This bitmap contains the variables which are set before they
156 are used in a basic block. */
157 bitmap kills;
160 /* It is advantageous to avoid things like life analysis for variables which
161 do not need PHI nodes. This enum describes whether or not a particular
162 variable may need a PHI node. */
164 enum need_phi_state {
165 /* This is the default. If we are still in this state after finding
166 all the definition and use sites, then we will assume the variable
167 needs PHI nodes. This is probably an overly conservative assumption. */
168 NEED_PHI_STATE_UNKNOWN,
170 /* This state indicates that we have seen one or more sets of the
171 variable in a single basic block and that the sets dominate all
172 uses seen so far. If after finding all definition and use sites
173 we are still in this state, then the variable does not need any
174 PHI nodes. */
175 NEED_PHI_STATE_NO,
177 /* This state indicates that we have either seen multiple definitions of
178 the variable in multiple blocks, or that we encountered a use in a
179 block that was not dominated by the block containing the set(s) of
180 this variable. This variable is assumed to need PHI nodes. */
181 NEED_PHI_STATE_MAYBE
184 /* Information stored for both SSA names and decls. */
185 struct common_info_d
187 /* This field indicates whether or not the variable may need PHI nodes.
188 See the enum's definition for more detailed information about the
189 states. */
190 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
192 /* The current reaching definition replacing this var. */
193 tree current_def;
195 /* Definitions for this var. */
196 struct def_blocks_d def_blocks;
199 /* The information associated with decls and SSA names. */
200 typedef struct common_info_d *common_info_p;
202 /* Information stored for decls. */
203 struct var_info_d
205 /* The variable. */
206 tree var;
208 /* Information stored for both SSA names and decls. */
209 struct common_info_d info;
212 /* The information associated with decls. */
213 typedef struct var_info_d *var_info_p;
216 /* VAR_INFOS hashtable helpers. */
218 struct var_info_hasher : free_ptr_hash <var_info_d>
220 static inline hashval_t hash (const value_type &);
221 static inline bool equal (const value_type &, const compare_type &);
224 inline hashval_t
225 var_info_hasher::hash (const value_type &p)
227 return DECL_UID (p->var);
230 inline bool
231 var_info_hasher::equal (const value_type &p1, const compare_type &p2)
233 return p1->var == p2->var;
237 /* Each entry in VAR_INFOS contains an element of type STRUCT
238 VAR_INFO_D. */
239 static hash_table<var_info_hasher> *var_infos;
242 /* Information stored for SSA names. */
243 struct ssa_name_info
245 /* Age of this record (so that info_for_ssa_name table can be cleared
246 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
247 are assumed to be null. */
248 unsigned age;
250 /* Replacement mappings, allocated from update_ssa_obstack. */
251 bitmap repl_set;
253 /* Information stored for both SSA names and decls. */
254 struct common_info_d info;
257 /* The information associated with names. */
258 typedef struct ssa_name_info *ssa_name_info_p;
260 static vec<ssa_name_info_p> info_for_ssa_name;
261 static unsigned current_info_for_ssa_name_age;
263 static bitmap_obstack update_ssa_obstack;
265 /* The set of blocks affected by update_ssa. */
266 static bitmap blocks_to_update;
268 /* The main entry point to the SSA renamer (rewrite_blocks) may be
269 called several times to do different, but related, tasks.
270 Initially, we need it to rename the whole program into SSA form.
271 At other times, we may need it to only rename into SSA newly
272 exposed symbols. Finally, we can also call it to incrementally fix
273 an already built SSA web. */
274 enum rewrite_mode {
275 /* Convert the whole function into SSA form. */
276 REWRITE_ALL,
278 /* Incrementally update the SSA web by replacing existing SSA
279 names with new ones. See update_ssa for details. */
280 REWRITE_UPDATE
283 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
284 static bitmap symbols_to_rename_set;
285 static vec<tree> symbols_to_rename;
287 /* Mark SYM for renaming. */
289 static void
290 mark_for_renaming (tree sym)
292 if (!symbols_to_rename_set)
293 symbols_to_rename_set = BITMAP_ALLOC (NULL);
294 if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
295 symbols_to_rename.safe_push (sym);
298 /* Return true if SYM is marked for renaming. */
300 static bool
301 marked_for_renaming (tree sym)
303 if (!symbols_to_rename_set || sym == NULL_TREE)
304 return false;
305 return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
309 /* Return true if STMT needs to be rewritten. When renaming a subset
310 of the variables, not all statements will be processed. This is
311 decided in mark_def_sites. */
313 static inline bool
314 rewrite_uses_p (gimple stmt)
316 return gimple_visited_p (stmt);
320 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
322 static inline void
323 set_rewrite_uses (gimple stmt, bool rewrite_p)
325 gimple_set_visited (stmt, rewrite_p);
329 /* Return true if the DEFs created by statement STMT should be
330 registered when marking new definition sites. This is slightly
331 different than rewrite_uses_p: it's used by update_ssa to
332 distinguish statements that need to have both uses and defs
333 processed from those that only need to have their defs processed.
334 Statements that define new SSA names only need to have their defs
335 registered, but they don't need to have their uses renamed. */
337 static inline bool
338 register_defs_p (gimple stmt)
340 return gimple_plf (stmt, GF_PLF_1) != 0;
344 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
346 static inline void
347 set_register_defs (gimple stmt, bool register_defs_p)
349 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
353 /* Get the information associated with NAME. */
355 static inline ssa_name_info_p
356 get_ssa_name_ann (tree name)
358 unsigned ver = SSA_NAME_VERSION (name);
359 unsigned len = info_for_ssa_name.length ();
360 struct ssa_name_info *info;
362 /* Re-allocate the vector at most once per update/into-SSA. */
363 if (ver >= len)
364 info_for_ssa_name.safe_grow_cleared (num_ssa_names);
366 /* But allocate infos lazily. */
367 info = info_for_ssa_name[ver];
368 if (!info)
370 info = XCNEW (struct ssa_name_info);
371 info->age = current_info_for_ssa_name_age;
372 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
373 info_for_ssa_name[ver] = info;
376 if (info->age < current_info_for_ssa_name_age)
378 info->age = current_info_for_ssa_name_age;
379 info->repl_set = NULL;
380 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
381 info->info.current_def = NULL_TREE;
382 info->info.def_blocks.def_blocks = NULL;
383 info->info.def_blocks.phi_blocks = NULL;
384 info->info.def_blocks.livein_blocks = NULL;
387 return info;
390 /* Return and allocate the auxiliar information for DECL. */
392 static inline var_info_p
393 get_var_info (tree decl)
395 struct var_info_d vi;
396 var_info_d **slot;
397 vi.var = decl;
398 slot = var_infos->find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
399 if (*slot == NULL)
401 var_info_p v = XCNEW (struct var_info_d);
402 v->var = decl;
403 *slot = v;
404 return v;
406 return *slot;
410 /* Clears info for SSA names. */
412 static void
413 clear_ssa_name_info (void)
415 current_info_for_ssa_name_age++;
417 /* If current_info_for_ssa_name_age wraps we use stale information.
418 Asser that this does not happen. */
419 gcc_assert (current_info_for_ssa_name_age != 0);
423 /* Get access to the auxiliar information stored per SSA name or decl. */
425 static inline common_info_p
426 get_common_info (tree var)
428 if (TREE_CODE (var) == SSA_NAME)
429 return &get_ssa_name_ann (var)->info;
430 else
431 return &get_var_info (var)->info;
435 /* Return the current definition for VAR. */
437 tree
438 get_current_def (tree var)
440 return get_common_info (var)->current_def;
444 /* Sets current definition of VAR to DEF. */
446 void
447 set_current_def (tree var, tree def)
449 get_common_info (var)->current_def = def;
452 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
453 all statements in basic block BB. */
455 static void
456 initialize_flags_in_bb (basic_block bb)
458 gimple stmt;
459 gimple_stmt_iterator gsi;
461 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
463 gimple phi = gsi_stmt (gsi);
464 set_rewrite_uses (phi, false);
465 set_register_defs (phi, false);
468 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
470 stmt = gsi_stmt (gsi);
472 /* We are going to use the operand cache API, such as
473 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
474 cache for each statement should be up-to-date. */
475 gcc_checking_assert (!gimple_modified_p (stmt));
476 set_rewrite_uses (stmt, false);
477 set_register_defs (stmt, false);
481 /* Mark block BB as interesting for update_ssa. */
483 static void
484 mark_block_for_update (basic_block bb)
486 gcc_checking_assert (blocks_to_update != NULL);
487 if (!bitmap_set_bit (blocks_to_update, bb->index))
488 return;
489 initialize_flags_in_bb (bb);
492 /* Return the set of blocks where variable VAR is defined and the blocks
493 where VAR is live on entry (livein). If no entry is found in
494 DEF_BLOCKS, a new one is created and returned. */
496 static inline struct def_blocks_d *
497 get_def_blocks_for (common_info_p info)
499 struct def_blocks_d *db_p = &info->def_blocks;
500 if (!db_p->def_blocks)
502 db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
503 db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
504 db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
507 return db_p;
511 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
512 VAR is defined by a PHI node. */
514 static void
515 set_def_block (tree var, basic_block bb, bool phi_p)
517 struct def_blocks_d *db_p;
518 common_info_p info;
520 info = get_common_info (var);
521 db_p = get_def_blocks_for (info);
523 /* Set the bit corresponding to the block where VAR is defined. */
524 bitmap_set_bit (db_p->def_blocks, bb->index);
525 if (phi_p)
526 bitmap_set_bit (db_p->phi_blocks, bb->index);
528 /* Keep track of whether or not we may need to insert PHI nodes.
530 If we are in the UNKNOWN state, then this is the first definition
531 of VAR. Additionally, we have not seen any uses of VAR yet, so
532 we do not need a PHI node for this variable at this time (i.e.,
533 transition to NEED_PHI_STATE_NO).
535 If we are in any other state, then we either have multiple definitions
536 of this variable occurring in different blocks or we saw a use of the
537 variable which was not dominated by the block containing the
538 definition(s). In this case we may need a PHI node, so enter
539 state NEED_PHI_STATE_MAYBE. */
540 if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
541 info->need_phi_state = NEED_PHI_STATE_NO;
542 else
543 info->need_phi_state = NEED_PHI_STATE_MAYBE;
547 /* Mark block BB as having VAR live at the entry to BB. */
549 static void
550 set_livein_block (tree var, basic_block bb)
552 common_info_p info;
553 struct def_blocks_d *db_p;
555 info = get_common_info (var);
556 db_p = get_def_blocks_for (info);
558 /* Set the bit corresponding to the block where VAR is live in. */
559 bitmap_set_bit (db_p->livein_blocks, bb->index);
561 /* Keep track of whether or not we may need to insert PHI nodes.
563 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
564 by the single block containing the definition(s) of this variable. If
565 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
566 NEED_PHI_STATE_MAYBE. */
567 if (info->need_phi_state == NEED_PHI_STATE_NO)
569 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
571 if (def_block_index == -1
572 || ! dominated_by_p (CDI_DOMINATORS, bb,
573 BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
574 info->need_phi_state = NEED_PHI_STATE_MAYBE;
576 else
577 info->need_phi_state = NEED_PHI_STATE_MAYBE;
581 /* Return true if NAME is in OLD_SSA_NAMES. */
583 static inline bool
584 is_old_name (tree name)
586 unsigned ver = SSA_NAME_VERSION (name);
587 if (!old_ssa_names)
588 return false;
589 return (ver < SBITMAP_SIZE (old_ssa_names)
590 && bitmap_bit_p (old_ssa_names, ver));
594 /* Return true if NAME is in NEW_SSA_NAMES. */
596 static inline bool
597 is_new_name (tree name)
599 unsigned ver = SSA_NAME_VERSION (name);
600 if (!new_ssa_names)
601 return false;
602 return (ver < SBITMAP_SIZE (new_ssa_names)
603 && bitmap_bit_p (new_ssa_names, ver));
607 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
609 static inline bitmap
610 names_replaced_by (tree new_tree)
612 return get_ssa_name_ann (new_tree)->repl_set;
616 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
618 static inline void
619 add_to_repl_tbl (tree new_tree, tree old)
621 bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
622 if (!*set)
623 *set = BITMAP_ALLOC (&update_ssa_obstack);
624 bitmap_set_bit (*set, SSA_NAME_VERSION (old));
628 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
629 represents the set of names O_1 ... O_j replaced by N_i. This is
630 used by update_ssa and its helpers to introduce new SSA names in an
631 already formed SSA web. */
633 static void
634 add_new_name_mapping (tree new_tree, tree old)
636 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
637 gcc_checking_assert (new_tree != old
638 && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
640 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
641 caller may have created new names since the set was created. */
642 if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
644 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
645 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
646 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
649 /* Update the REPL_TBL table. */
650 add_to_repl_tbl (new_tree, old);
652 /* If OLD had already been registered as a new name, then all the
653 names that OLD replaces should also be replaced by NEW_TREE. */
654 if (is_new_name (old))
655 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
657 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
658 respectively. */
659 bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
660 bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
664 /* Call back for walk_dominator_tree used to collect definition sites
665 for every variable in the function. For every statement S in block
668 1- Variables defined by S in the DEFS of S are marked in the bitmap
669 KILLS.
671 2- If S uses a variable VAR and there is no preceding kill of VAR,
672 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
674 This information is used to determine which variables are live
675 across block boundaries to reduce the number of PHI nodes
676 we create. */
678 static void
679 mark_def_sites (basic_block bb, gimple stmt, bitmap kills)
681 tree def;
682 use_operand_p use_p;
683 ssa_op_iter iter;
685 /* Since this is the first time that we rewrite the program into SSA
686 form, force an operand scan on every statement. */
687 update_stmt (stmt);
689 gcc_checking_assert (blocks_to_update == NULL);
690 set_register_defs (stmt, false);
691 set_rewrite_uses (stmt, false);
693 if (is_gimple_debug (stmt))
695 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
697 tree sym = USE_FROM_PTR (use_p);
698 gcc_checking_assert (DECL_P (sym));
699 set_rewrite_uses (stmt, true);
701 if (rewrite_uses_p (stmt))
702 bitmap_set_bit (interesting_blocks, bb->index);
703 return;
706 /* If a variable is used before being set, then the variable is live
707 across a block boundary, so mark it live-on-entry to BB. */
708 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
710 tree sym = USE_FROM_PTR (use_p);
711 gcc_checking_assert (DECL_P (sym));
712 if (!bitmap_bit_p (kills, DECL_UID (sym)))
713 set_livein_block (sym, bb);
714 set_rewrite_uses (stmt, true);
717 /* Now process the defs. Mark BB as the definition block and add
718 each def to the set of killed symbols. */
719 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
721 gcc_checking_assert (DECL_P (def));
722 set_def_block (def, bb, false);
723 bitmap_set_bit (kills, DECL_UID (def));
724 set_register_defs (stmt, true);
727 /* If we found the statement interesting then also mark the block BB
728 as interesting. */
729 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
730 bitmap_set_bit (interesting_blocks, bb->index);
733 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
734 in the dfs numbering of the dominance tree. */
736 struct dom_dfsnum
738 /* Basic block whose index this entry corresponds to. */
739 unsigned bb_index;
741 /* The dfs number of this node. */
742 unsigned dfs_num;
745 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
746 for qsort. */
748 static int
749 cmp_dfsnum (const void *a, const void *b)
751 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
752 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
754 return (int) da->dfs_num - (int) db->dfs_num;
757 /* Among the intervals starting at the N points specified in DEFS, find
758 the one that contains S, and return its bb_index. */
760 static unsigned
761 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
763 unsigned f = 0, t = n, m;
765 while (t > f + 1)
767 m = (f + t) / 2;
768 if (defs[m].dfs_num <= s)
769 f = m;
770 else
771 t = m;
774 return defs[f].bb_index;
777 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
778 KILLS is a bitmap of blocks where the value is defined before any use. */
780 static void
781 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
783 bitmap_iterator bi;
784 unsigned i, b, p, u, top;
785 bitmap live_phis;
786 basic_block def_bb, use_bb;
787 edge e;
788 edge_iterator ei;
789 bitmap to_remove;
790 struct dom_dfsnum *defs;
791 unsigned n_defs, adef;
793 if (bitmap_empty_p (uses))
795 bitmap_clear (phis);
796 return;
799 /* The phi must dominate a use, or an argument of a live phi. Also, we
800 do not create any phi nodes in def blocks, unless they are also livein. */
801 to_remove = BITMAP_ALLOC (NULL);
802 bitmap_and_compl (to_remove, kills, uses);
803 bitmap_and_compl_into (phis, to_remove);
804 if (bitmap_empty_p (phis))
806 BITMAP_FREE (to_remove);
807 return;
810 /* We want to remove the unnecessary phi nodes, but we do not want to compute
811 liveness information, as that may be linear in the size of CFG, and if
812 there are lot of different variables to rewrite, this may lead to quadratic
813 behavior.
815 Instead, we basically emulate standard dce. We put all uses to worklist,
816 then for each of them find the nearest def that dominates them. If this
817 def is a phi node, we mark it live, and if it was not live before, we
818 add the predecessors of its basic block to the worklist.
820 To quickly locate the nearest def that dominates use, we use dfs numbering
821 of the dominance tree (that is already available in order to speed up
822 queries). For each def, we have the interval given by the dfs number on
823 entry to and on exit from the corresponding subtree in the dominance tree.
824 The nearest dominator for a given use is the smallest of these intervals
825 that contains entry and exit dfs numbers for the basic block with the use.
826 If we store the bounds for all the uses to an array and sort it, we can
827 locate the nearest dominating def in logarithmic time by binary search.*/
828 bitmap_ior (to_remove, kills, phis);
829 n_defs = bitmap_count_bits (to_remove);
830 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
831 defs[0].bb_index = 1;
832 defs[0].dfs_num = 0;
833 adef = 1;
834 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
836 def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
837 defs[adef].bb_index = i;
838 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
839 defs[adef + 1].bb_index = i;
840 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
841 adef += 2;
843 BITMAP_FREE (to_remove);
844 gcc_assert (adef == 2 * n_defs + 1);
845 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
846 gcc_assert (defs[0].bb_index == 1);
848 /* Now each DEFS entry contains the number of the basic block to that the
849 dfs number corresponds. Change them to the number of basic block that
850 corresponds to the interval following the dfs number. Also, for the
851 dfs_out numbers, increase the dfs number by one (so that it corresponds
852 to the start of the following interval, not to the end of the current
853 one). We use WORKLIST as a stack. */
854 auto_vec<int> worklist (n_defs + 1);
855 worklist.quick_push (1);
856 top = 1;
857 n_defs = 1;
858 for (i = 1; i < adef; i++)
860 b = defs[i].bb_index;
861 if (b == top)
863 /* This is a closing element. Interval corresponding to the top
864 of the stack after removing it follows. */
865 worklist.pop ();
866 top = worklist[worklist.length () - 1];
867 defs[n_defs].bb_index = top;
868 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
870 else
872 /* Opening element. Nothing to do, just push it to the stack and move
873 it to the correct position. */
874 defs[n_defs].bb_index = defs[i].bb_index;
875 defs[n_defs].dfs_num = defs[i].dfs_num;
876 worklist.quick_push (b);
877 top = b;
880 /* If this interval starts at the same point as the previous one, cancel
881 the previous one. */
882 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
883 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
884 else
885 n_defs++;
887 worklist.pop ();
888 gcc_assert (worklist.is_empty ());
890 /* Now process the uses. */
891 live_phis = BITMAP_ALLOC (NULL);
892 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
894 worklist.safe_push (i);
897 while (!worklist.is_empty ())
899 b = worklist.pop ();
900 if (b == ENTRY_BLOCK)
901 continue;
903 /* If there is a phi node in USE_BB, it is made live. Otherwise,
904 find the def that dominates the immediate dominator of USE_BB
905 (the kill in USE_BB does not dominate the use). */
906 if (bitmap_bit_p (phis, b))
907 p = b;
908 else
910 use_bb = get_immediate_dominator (CDI_DOMINATORS,
911 BASIC_BLOCK_FOR_FN (cfun, b));
912 p = find_dfsnum_interval (defs, n_defs,
913 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
914 if (!bitmap_bit_p (phis, p))
915 continue;
918 /* If the phi node is already live, there is nothing to do. */
919 if (!bitmap_set_bit (live_phis, p))
920 continue;
922 /* Add the new uses to the worklist. */
923 def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
924 FOR_EACH_EDGE (e, ei, def_bb->preds)
926 u = e->src->index;
927 if (bitmap_bit_p (uses, u))
928 continue;
930 /* In case there is a kill directly in the use block, do not record
931 the use (this is also necessary for correctness, as we assume that
932 uses dominated by a def directly in their block have been filtered
933 out before). */
934 if (bitmap_bit_p (kills, u))
935 continue;
937 bitmap_set_bit (uses, u);
938 worklist.safe_push (u);
942 bitmap_copy (phis, live_phis);
943 BITMAP_FREE (live_phis);
944 free (defs);
947 /* Return the set of blocks where variable VAR is defined and the blocks
948 where VAR is live on entry (livein). Return NULL, if no entry is
949 found in DEF_BLOCKS. */
951 static inline struct def_blocks_d *
952 find_def_blocks_for (tree var)
954 def_blocks_p p = &get_common_info (var)->def_blocks;
955 if (!p->def_blocks)
956 return NULL;
957 return p;
961 /* Marks phi node PHI in basic block BB for rewrite. */
963 static void
964 mark_phi_for_rewrite (basic_block bb, gphi *phi)
966 vec<gphi *> phis;
967 unsigned n, idx = bb->index;
969 if (rewrite_uses_p (phi))
970 return;
972 set_rewrite_uses (phi, true);
974 if (!blocks_with_phis_to_rewrite)
975 return;
977 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
979 n = (unsigned) last_basic_block_for_fn (cfun) + 1;
980 if (phis_to_rewrite.length () < n)
981 phis_to_rewrite.safe_grow_cleared (n);
983 phis = phis_to_rewrite[idx];
984 phis.reserve (10);
986 phis.safe_push (phi);
987 phis_to_rewrite[idx] = phis;
990 /* Insert PHI nodes for variable VAR using the iterated dominance
991 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
992 function assumes that the caller is incrementally updating the
993 existing SSA form, in which case VAR may be an SSA name instead of
994 a symbol.
996 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
997 PHI node for VAR. On exit, only the nodes that received a PHI node
998 for VAR will be present in PHI_INSERTION_POINTS. */
1000 static void
1001 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
1003 unsigned bb_index;
1004 edge e;
1005 gphi *phi;
1006 basic_block bb;
1007 bitmap_iterator bi;
1008 struct def_blocks_d *def_map = find_def_blocks_for (var);
1010 /* Remove the blocks where we already have PHI nodes for VAR. */
1011 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1013 /* Remove obviously useless phi nodes. */
1014 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1015 def_map->livein_blocks);
1017 /* And insert the PHI nodes. */
1018 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1020 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1021 if (update_p)
1022 mark_block_for_update (bb);
1024 if (dump_file && (dump_flags & TDF_DETAILS))
1026 fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
1027 print_generic_expr (dump_file, var, TDF_SLIM);
1028 fprintf (dump_file, "\n");
1030 phi = NULL;
1032 if (TREE_CODE (var) == SSA_NAME)
1034 /* If we are rewriting SSA names, create the LHS of the PHI
1035 node by duplicating VAR. This is useful in the case of
1036 pointers, to also duplicate pointer attributes (alias
1037 information, in particular). */
1038 edge_iterator ei;
1039 tree new_lhs;
1041 gcc_checking_assert (update_p);
1042 new_lhs = duplicate_ssa_name (var, NULL);
1043 phi = create_phi_node (new_lhs, bb);
1044 add_new_name_mapping (new_lhs, var);
1046 /* Add VAR to every argument slot of PHI. We need VAR in
1047 every argument so that rewrite_update_phi_arguments knows
1048 which name is this PHI node replacing. If VAR is a
1049 symbol marked for renaming, this is not necessary, the
1050 renamer will use the symbol on the LHS to get its
1051 reaching definition. */
1052 FOR_EACH_EDGE (e, ei, bb->preds)
1053 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1055 else
1057 tree tracked_var;
1059 gcc_checking_assert (DECL_P (var));
1060 phi = create_phi_node (var, bb);
1062 tracked_var = target_for_debug_bind (var);
1063 if (tracked_var)
1065 gimple note = gimple_build_debug_bind (tracked_var,
1066 PHI_RESULT (phi),
1067 phi);
1068 gimple_stmt_iterator si = gsi_after_labels (bb);
1069 gsi_insert_before (&si, note, GSI_SAME_STMT);
1073 /* Mark this PHI node as interesting for update_ssa. */
1074 set_register_defs (phi, true);
1075 mark_phi_for_rewrite (bb, phi);
1079 /* Sort var_infos after DECL_UID of their var. */
1081 static int
1082 insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1084 const struct var_info_d *defa = *(struct var_info_d * const *)a;
1085 const struct var_info_d *defb = *(struct var_info_d * const *)b;
1086 if (DECL_UID (defa->var) < DECL_UID (defb->var))
1087 return -1;
1088 else
1089 return 1;
1092 /* Insert PHI nodes at the dominance frontier of blocks with variable
1093 definitions. DFS contains the dominance frontier information for
1094 the flowgraph. */
1096 static void
1097 insert_phi_nodes (bitmap_head *dfs)
1099 hash_table<var_info_hasher>::iterator hi;
1100 unsigned i;
1101 var_info_p info;
1103 timevar_push (TV_TREE_INSERT_PHI_NODES);
1105 auto_vec<var_info_p> vars (var_infos->elements ());
1106 FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
1107 if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1108 vars.quick_push (info);
1110 /* Do two stages to avoid code generation differences for UID
1111 differences but no UID ordering differences. */
1112 vars.qsort (insert_phi_nodes_compare_var_infos);
1114 FOR_EACH_VEC_ELT (vars, i, info)
1116 bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1117 insert_phi_nodes_for (info->var, idf, false);
1118 BITMAP_FREE (idf);
1121 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1125 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1126 register DEF (an SSA_NAME) to be a new definition for SYM. */
1128 static void
1129 register_new_def (tree def, tree sym)
1131 common_info_p info = get_common_info (sym);
1132 tree currdef;
1134 /* If this variable is set in a single basic block and all uses are
1135 dominated by the set(s) in that single basic block, then there is
1136 no reason to record anything for this variable in the block local
1137 definition stacks. Doing so just wastes time and memory.
1139 This is the same test to prune the set of variables which may
1140 need PHI nodes. So we just use that information since it's already
1141 computed and available for us to use. */
1142 if (info->need_phi_state == NEED_PHI_STATE_NO)
1144 info->current_def = def;
1145 return;
1148 currdef = info->current_def;
1150 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1151 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1152 in the stack so that we know which symbol is being defined by
1153 this SSA name when we unwind the stack. */
1154 if (currdef && !is_gimple_reg (sym))
1155 block_defs_stack.safe_push (sym);
1157 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1158 stack is later used by the dominator tree callbacks to restore
1159 the reaching definitions for all the variables defined in the
1160 block after a recursive visit to all its immediately dominated
1161 blocks. If there is no current reaching definition, then just
1162 record the underlying _DECL node. */
1163 block_defs_stack.safe_push (currdef ? currdef : sym);
1165 /* Set the current reaching definition for SYM to be DEF. */
1166 info->current_def = def;
1170 /* Perform a depth-first traversal of the dominator tree looking for
1171 variables to rename. BB is the block where to start searching.
1172 Renaming is a five step process:
1174 1- Every definition made by PHI nodes at the start of the blocks is
1175 registered as the current definition for the corresponding variable.
1177 2- Every statement in BB is rewritten. USE and VUSE operands are
1178 rewritten with their corresponding reaching definition. DEF and
1179 VDEF targets are registered as new definitions.
1181 3- All the PHI nodes in successor blocks of BB are visited. The
1182 argument corresponding to BB is replaced with its current reaching
1183 definition.
1185 4- Recursively rewrite every dominator child block of BB.
1187 5- Restore (in reverse order) the current reaching definition for every
1188 new definition introduced in this block. This is done so that when
1189 we return from the recursive call, all the current reaching
1190 definitions are restored to the names that were valid in the
1191 dominator parent of BB. */
1193 /* Return the current definition for variable VAR. If none is found,
1194 create a new SSA name to act as the zeroth definition for VAR. */
1196 static tree
1197 get_reaching_def (tree var)
1199 common_info_p info = get_common_info (var);
1200 tree currdef;
1202 /* Lookup the current reaching definition for VAR. */
1203 currdef = info->current_def;
1205 /* If there is no reaching definition for VAR, create and register a
1206 default definition for it (if needed). */
1207 if (currdef == NULL_TREE)
1209 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1210 currdef = get_or_create_ssa_default_def (cfun, sym);
1213 /* Return the current reaching definition for VAR, or the default
1214 definition, if we had to create one. */
1215 return currdef;
1219 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1221 static void
1222 rewrite_debug_stmt_uses (gimple stmt)
1224 use_operand_p use_p;
1225 ssa_op_iter iter;
1226 bool update = false;
1228 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1230 tree var = USE_FROM_PTR (use_p), def;
1231 common_info_p info = get_common_info (var);
1232 gcc_checking_assert (DECL_P (var));
1233 def = info->current_def;
1234 if (!def)
1236 if (TREE_CODE (var) == PARM_DECL
1237 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
1239 gimple_stmt_iterator gsi
1241 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1242 int lim;
1243 /* Search a few source bind stmts at the start of first bb to
1244 see if a DEBUG_EXPR_DECL can't be reused. */
1245 for (lim = 32;
1246 !gsi_end_p (gsi) && lim > 0;
1247 gsi_next (&gsi), lim--)
1249 gimple gstmt = gsi_stmt (gsi);
1250 if (!gimple_debug_source_bind_p (gstmt))
1251 break;
1252 if (gimple_debug_source_bind_get_value (gstmt) == var)
1254 def = gimple_debug_source_bind_get_var (gstmt);
1255 if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1256 break;
1257 else
1258 def = NULL_TREE;
1261 /* If not, add a new source bind stmt. */
1262 if (def == NULL_TREE)
1264 gimple def_temp;
1265 def = make_node (DEBUG_EXPR_DECL);
1266 def_temp = gimple_build_debug_source_bind (def, var, NULL);
1267 DECL_ARTIFICIAL (def) = 1;
1268 TREE_TYPE (def) = TREE_TYPE (var);
1269 DECL_MODE (def) = DECL_MODE (var);
1270 gsi =
1271 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1272 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1274 update = true;
1277 else
1279 /* Check if info->current_def can be trusted. */
1280 basic_block bb = gimple_bb (stmt);
1281 basic_block def_bb
1282 = SSA_NAME_IS_DEFAULT_DEF (def)
1283 ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1285 /* If definition is in current bb, it is fine. */
1286 if (bb == def_bb)
1288 /* If definition bb doesn't dominate the current bb,
1289 it can't be used. */
1290 else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1291 def = NULL;
1292 /* If there is just one definition and dominates the current
1293 bb, it is fine. */
1294 else if (info->need_phi_state == NEED_PHI_STATE_NO)
1296 else
1298 struct def_blocks_d *db_p = get_def_blocks_for (info);
1300 /* If there are some non-debug uses in the current bb,
1301 it is fine. */
1302 if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1304 /* Otherwise give up for now. */
1305 else
1306 def = NULL;
1309 if (def == NULL)
1311 gimple_debug_bind_reset_value (stmt);
1312 update_stmt (stmt);
1313 return;
1315 SET_USE (use_p, def);
1317 if (update)
1318 update_stmt (stmt);
1321 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1322 the block with its immediate reaching definitions. Update the current
1323 definition of a variable when a new real or virtual definition is found. */
1325 static void
1326 rewrite_stmt (gimple_stmt_iterator *si)
1328 use_operand_p use_p;
1329 def_operand_p def_p;
1330 ssa_op_iter iter;
1331 gimple stmt = gsi_stmt (*si);
1333 /* If mark_def_sites decided that we don't need to rewrite this
1334 statement, ignore it. */
1335 gcc_assert (blocks_to_update == NULL);
1336 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1337 return;
1339 if (dump_file && (dump_flags & TDF_DETAILS))
1341 fprintf (dump_file, "Renaming statement ");
1342 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1343 fprintf (dump_file, "\n");
1346 /* Step 1. Rewrite USES in the statement. */
1347 if (rewrite_uses_p (stmt))
1349 if (is_gimple_debug (stmt))
1350 rewrite_debug_stmt_uses (stmt);
1351 else
1352 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1354 tree var = USE_FROM_PTR (use_p);
1355 gcc_checking_assert (DECL_P (var));
1356 SET_USE (use_p, get_reaching_def (var));
1360 /* Step 2. Register the statement's DEF operands. */
1361 if (register_defs_p (stmt))
1362 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1364 tree var = DEF_FROM_PTR (def_p);
1365 tree name;
1366 tree tracked_var;
1368 gcc_checking_assert (DECL_P (var));
1370 if (gimple_clobber_p (stmt)
1371 && is_gimple_reg (var))
1373 /* If we rewrite a DECL into SSA form then drop its
1374 clobber stmts and replace uses with a new default def. */
1375 gcc_checking_assert (TREE_CODE (var) == VAR_DECL
1376 && !gimple_vdef (stmt));
1377 gsi_replace (si, gimple_build_nop (), true);
1378 register_new_def (get_or_create_ssa_default_def (cfun, var), var);
1379 break;
1382 name = make_ssa_name (var, stmt);
1383 SET_DEF (def_p, name);
1384 register_new_def (DEF_FROM_PTR (def_p), var);
1386 tracked_var = target_for_debug_bind (var);
1387 if (tracked_var)
1389 gimple note = gimple_build_debug_bind (tracked_var, name, stmt);
1390 gsi_insert_after (si, note, GSI_SAME_STMT);
1396 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1397 PHI nodes. For every PHI node found, add a new argument containing the
1398 current reaching definition for the variable and the edge through which
1399 that definition is reaching the PHI node. */
1401 static void
1402 rewrite_add_phi_arguments (basic_block bb)
1404 edge e;
1405 edge_iterator ei;
1407 FOR_EACH_EDGE (e, ei, bb->succs)
1409 gphi *phi;
1410 gphi_iterator gsi;
1412 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1413 gsi_next (&gsi))
1415 tree currdef, res;
1416 location_t loc;
1418 phi = gsi.phi ();
1419 res = gimple_phi_result (phi);
1420 currdef = get_reaching_def (SSA_NAME_VAR (res));
1421 /* Virtual operand PHI args do not need a location. */
1422 if (virtual_operand_p (res))
1423 loc = UNKNOWN_LOCATION;
1424 else
1425 loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1426 add_phi_arg (phi, currdef, e, loc);
1431 class rewrite_dom_walker : public dom_walker
1433 public:
1434 rewrite_dom_walker (cdi_direction direction) : dom_walker (direction) {}
1436 virtual void before_dom_children (basic_block);
1437 virtual void after_dom_children (basic_block);
1440 /* SSA Rewriting Step 1. Initialization, create a block local stack
1441 of reaching definitions for new SSA names produced in this block
1442 (BLOCK_DEFS). Register new definitions for every PHI node in the
1443 block. */
1445 void
1446 rewrite_dom_walker::before_dom_children (basic_block bb)
1448 if (dump_file && (dump_flags & TDF_DETAILS))
1449 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1451 /* Mark the unwind point for this block. */
1452 block_defs_stack.safe_push (NULL_TREE);
1454 /* Step 1. Register new definitions for every PHI node in the block.
1455 Conceptually, all the PHI nodes are executed in parallel and each PHI
1456 node introduces a new version for the associated variable. */
1457 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1458 gsi_next (&gsi))
1460 tree result = gimple_phi_result (gsi_stmt (gsi));
1461 register_new_def (result, SSA_NAME_VAR (result));
1464 /* Step 2. Rewrite every variable used in each statement in the block
1465 with its immediate reaching definitions. Update the current definition
1466 of a variable when a new real or virtual definition is found. */
1467 if (bitmap_bit_p (interesting_blocks, bb->index))
1468 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1469 gsi_next (&gsi))
1470 rewrite_stmt (&gsi);
1472 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1473 For every PHI node found, add a new argument containing the current
1474 reaching definition for the variable and the edge through which that
1475 definition is reaching the PHI node. */
1476 rewrite_add_phi_arguments (bb);
1481 /* Called after visiting all the statements in basic block BB and all
1482 of its dominator children. Restore CURRDEFS to its original value. */
1484 void
1485 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1487 /* Restore CURRDEFS to its original state. */
1488 while (block_defs_stack.length () > 0)
1490 tree tmp = block_defs_stack.pop ();
1491 tree saved_def, var;
1493 if (tmp == NULL_TREE)
1494 break;
1496 if (TREE_CODE (tmp) == SSA_NAME)
1498 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1499 current definition of its underlying variable. Note that
1500 if the SSA_NAME is not for a GIMPLE register, the symbol
1501 being defined is stored in the next slot in the stack.
1502 This mechanism is needed because an SSA name for a
1503 non-register symbol may be the definition for more than
1504 one symbol (e.g., SFTs, aliased variables, etc). */
1505 saved_def = tmp;
1506 var = SSA_NAME_VAR (saved_def);
1507 if (!is_gimple_reg (var))
1508 var = block_defs_stack.pop ();
1510 else
1512 /* If we recorded anything else, it must have been a _DECL
1513 node and its current reaching definition must have been
1514 NULL. */
1515 saved_def = NULL;
1516 var = tmp;
1519 get_common_info (var)->current_def = saved_def;
1524 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1526 DEBUG_FUNCTION void
1527 debug_decl_set (bitmap set)
1529 dump_decl_set (stderr, set);
1530 fprintf (stderr, "\n");
1534 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1535 stack up to a maximum of N levels. If N is -1, the whole stack is
1536 dumped. New levels are created when the dominator tree traversal
1537 used for renaming enters a new sub-tree. */
1539 void
1540 dump_defs_stack (FILE *file, int n)
1542 int i, j;
1544 fprintf (file, "\n\nRenaming stack");
1545 if (n > 0)
1546 fprintf (file, " (up to %d levels)", n);
1547 fprintf (file, "\n\n");
1549 i = 1;
1550 fprintf (file, "Level %d (current level)\n", i);
1551 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1553 tree name, var;
1555 name = block_defs_stack[j];
1556 if (name == NULL_TREE)
1558 i++;
1559 if (n > 0 && i > n)
1560 break;
1561 fprintf (file, "\nLevel %d\n", i);
1562 continue;
1565 if (DECL_P (name))
1567 var = name;
1568 name = NULL_TREE;
1570 else
1572 var = SSA_NAME_VAR (name);
1573 if (!is_gimple_reg (var))
1575 j--;
1576 var = block_defs_stack[j];
1580 fprintf (file, " Previous CURRDEF (");
1581 print_generic_expr (file, var, 0);
1582 fprintf (file, ") = ");
1583 if (name)
1584 print_generic_expr (file, name, 0);
1585 else
1586 fprintf (file, "<NIL>");
1587 fprintf (file, "\n");
1592 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1593 stack up to a maximum of N levels. If N is -1, the whole stack is
1594 dumped. New levels are created when the dominator tree traversal
1595 used for renaming enters a new sub-tree. */
1597 DEBUG_FUNCTION void
1598 debug_defs_stack (int n)
1600 dump_defs_stack (stderr, n);
1604 /* Dump the current reaching definition of every symbol to FILE. */
1606 void
1607 dump_currdefs (FILE *file)
1609 unsigned i;
1610 tree var;
1612 if (symbols_to_rename.is_empty ())
1613 return;
1615 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1616 FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1618 common_info_p info = get_common_info (var);
1619 fprintf (file, "CURRDEF (");
1620 print_generic_expr (file, var, 0);
1621 fprintf (file, ") = ");
1622 if (info->current_def)
1623 print_generic_expr (file, info->current_def, 0);
1624 else
1625 fprintf (file, "<NIL>");
1626 fprintf (file, "\n");
1631 /* Dump the current reaching definition of every symbol to stderr. */
1633 DEBUG_FUNCTION void
1634 debug_currdefs (void)
1636 dump_currdefs (stderr);
1640 /* Dump SSA information to FILE. */
1642 void
1643 dump_tree_ssa (FILE *file)
1645 const char *funcname
1646 = lang_hooks.decl_printable_name (current_function_decl, 2);
1648 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1650 dump_var_infos (file);
1651 dump_defs_stack (file, -1);
1652 dump_currdefs (file);
1653 dump_tree_ssa_stats (file);
1657 /* Dump SSA information to stderr. */
1659 DEBUG_FUNCTION void
1660 debug_tree_ssa (void)
1662 dump_tree_ssa (stderr);
1666 /* Dump statistics for the hash table HTAB. */
1668 static void
1669 htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
1671 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1672 (long) htab.size (),
1673 (long) htab.elements (),
1674 htab.collisions ());
1678 /* Dump SSA statistics on FILE. */
1680 void
1681 dump_tree_ssa_stats (FILE *file)
1683 if (var_infos)
1685 fprintf (file, "\nHash table statistics:\n");
1686 fprintf (file, " var_infos: ");
1687 htab_statistics (file, *var_infos);
1688 fprintf (file, "\n");
1693 /* Dump SSA statistics on stderr. */
1695 DEBUG_FUNCTION void
1696 debug_tree_ssa_stats (void)
1698 dump_tree_ssa_stats (stderr);
1702 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1705 debug_var_infos_r (var_info_d **slot, FILE *file)
1707 struct var_info_d *info = *slot;
1709 fprintf (file, "VAR: ");
1710 print_generic_expr (file, info->var, dump_flags);
1711 bitmap_print (file, info->info.def_blocks.def_blocks,
1712 ", DEF_BLOCKS: { ", "}");
1713 bitmap_print (file, info->info.def_blocks.livein_blocks,
1714 ", LIVEIN_BLOCKS: { ", "}");
1715 bitmap_print (file, info->info.def_blocks.phi_blocks,
1716 ", PHI_BLOCKS: { ", "}\n");
1718 return 1;
1722 /* Dump the VAR_INFOS hash table on FILE. */
1724 void
1725 dump_var_infos (FILE *file)
1727 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1728 if (var_infos)
1729 var_infos->traverse <FILE *, debug_var_infos_r> (file);
1733 /* Dump the VAR_INFOS hash table on stderr. */
1735 DEBUG_FUNCTION void
1736 debug_var_infos (void)
1738 dump_var_infos (stderr);
1742 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1744 static inline void
1745 register_new_update_single (tree new_name, tree old_name)
1747 common_info_p info = get_common_info (old_name);
1748 tree currdef = info->current_def;
1750 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1751 This stack is later used by the dominator tree callbacks to
1752 restore the reaching definitions for all the variables
1753 defined in the block after a recursive visit to all its
1754 immediately dominated blocks. */
1755 block_defs_stack.reserve (2);
1756 block_defs_stack.quick_push (currdef);
1757 block_defs_stack.quick_push (old_name);
1759 /* Set the current reaching definition for OLD_NAME to be
1760 NEW_NAME. */
1761 info->current_def = new_name;
1765 /* Register NEW_NAME to be the new reaching definition for all the
1766 names in OLD_NAMES. Used by the incremental SSA update routines to
1767 replace old SSA names with new ones. */
1769 static inline void
1770 register_new_update_set (tree new_name, bitmap old_names)
1772 bitmap_iterator bi;
1773 unsigned i;
1775 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1776 register_new_update_single (new_name, ssa_name (i));
1781 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1782 it is a symbol marked for renaming, replace it with USE_P's current
1783 reaching definition. */
1785 static inline void
1786 maybe_replace_use (use_operand_p use_p)
1788 tree rdef = NULL_TREE;
1789 tree use = USE_FROM_PTR (use_p);
1790 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1792 if (marked_for_renaming (sym))
1793 rdef = get_reaching_def (sym);
1794 else if (is_old_name (use))
1795 rdef = get_reaching_def (use);
1797 if (rdef && rdef != use)
1798 SET_USE (use_p, rdef);
1802 /* Same as maybe_replace_use, but without introducing default stmts,
1803 returning false to indicate a need to do so. */
1805 static inline bool
1806 maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1808 tree rdef = NULL_TREE;
1809 tree use = USE_FROM_PTR (use_p);
1810 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1812 if (marked_for_renaming (sym))
1813 rdef = get_var_info (sym)->info.current_def;
1814 else if (is_old_name (use))
1816 rdef = get_ssa_name_ann (use)->info.current_def;
1817 /* We can't assume that, if there's no current definition, the
1818 default one should be used. It could be the case that we've
1819 rearranged blocks so that the earlier definition no longer
1820 dominates the use. */
1821 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1822 rdef = use;
1824 else
1825 rdef = use;
1827 if (rdef && rdef != use)
1828 SET_USE (use_p, rdef);
1830 return rdef != NULL_TREE;
1834 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1835 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1836 register it as the current definition for the names replaced by
1837 DEF_P. Returns whether the statement should be removed. */
1839 static inline bool
1840 maybe_register_def (def_operand_p def_p, gimple stmt,
1841 gimple_stmt_iterator gsi)
1843 tree def = DEF_FROM_PTR (def_p);
1844 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1845 bool to_delete = false;
1847 /* If DEF is a naked symbol that needs renaming, create a new
1848 name for it. */
1849 if (marked_for_renaming (sym))
1851 if (DECL_P (def))
1853 if (gimple_clobber_p (stmt) && is_gimple_reg (sym))
1855 gcc_checking_assert (TREE_CODE (sym) == VAR_DECL);
1856 /* Replace clobber stmts with a default def. This new use of a
1857 default definition may make it look like SSA_NAMEs have
1858 conflicting lifetimes, so we need special code to let them
1859 coalesce properly. */
1860 to_delete = true;
1861 def = get_or_create_ssa_default_def (cfun, sym);
1863 else
1864 def = make_ssa_name (def, stmt);
1865 SET_DEF (def_p, def);
1867 tree tracked_var = target_for_debug_bind (sym);
1868 if (tracked_var)
1870 gimple note = gimple_build_debug_bind (tracked_var, def, stmt);
1871 /* If stmt ends the bb, insert the debug stmt on the single
1872 non-EH edge from the stmt. */
1873 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1875 basic_block bb = gsi_bb (gsi);
1876 edge_iterator ei;
1877 edge e, ef = NULL;
1878 FOR_EACH_EDGE (e, ei, bb->succs)
1879 if (!(e->flags & EDGE_EH))
1881 gcc_checking_assert (!ef);
1882 ef = e;
1884 /* If there are other predecessors to ef->dest, then
1885 there must be PHI nodes for the modified
1886 variable, and therefore there will be debug bind
1887 stmts after the PHI nodes. The debug bind notes
1888 we'd insert would force the creation of a new
1889 block (diverging codegen) and be redundant with
1890 the post-PHI bind stmts, so don't add them.
1892 As for the exit edge, there wouldn't be redundant
1893 bind stmts, but there wouldn't be a PC to bind
1894 them to either, so avoid diverging the CFG. */
1895 if (ef && single_pred_p (ef->dest)
1896 && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1898 /* If there were PHI nodes in the node, we'd
1899 have to make sure the value we're binding
1900 doesn't need rewriting. But there shouldn't
1901 be PHI nodes in a single-predecessor block,
1902 so we just add the note. */
1903 gsi_insert_on_edge_immediate (ef, note);
1906 else
1907 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1911 register_new_update_single (def, sym);
1913 else
1915 /* If DEF is a new name, register it as a new definition
1916 for all the names replaced by DEF. */
1917 if (is_new_name (def))
1918 register_new_update_set (def, names_replaced_by (def));
1920 /* If DEF is an old name, register DEF as a new
1921 definition for itself. */
1922 if (is_old_name (def))
1923 register_new_update_single (def, def);
1926 return to_delete;
1930 /* Update every variable used in the statement pointed-to by SI. The
1931 statement is assumed to be in SSA form already. Names in
1932 OLD_SSA_NAMES used by SI will be updated to their current reaching
1933 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1934 will be registered as a new definition for their corresponding name
1935 in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1937 static bool
1938 rewrite_update_stmt (gimple stmt, gimple_stmt_iterator gsi)
1940 use_operand_p use_p;
1941 def_operand_p def_p;
1942 ssa_op_iter iter;
1944 /* Only update marked statements. */
1945 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1946 return false;
1948 if (dump_file && (dump_flags & TDF_DETAILS))
1950 fprintf (dump_file, "Updating SSA information for statement ");
1951 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1954 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1955 symbol is marked for renaming. */
1956 if (rewrite_uses_p (stmt))
1958 if (is_gimple_debug (stmt))
1960 bool failed = false;
1962 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1963 if (!maybe_replace_use_in_debug_stmt (use_p))
1965 failed = true;
1966 break;
1969 if (failed)
1971 /* DOM sometimes threads jumps in such a way that a
1972 debug stmt ends up referencing a SSA variable that no
1973 longer dominates the debug stmt, but such that all
1974 incoming definitions refer to the same definition in
1975 an earlier dominator. We could try to recover that
1976 definition somehow, but this will have to do for now.
1978 Introducing a default definition, which is what
1979 maybe_replace_use() would do in such cases, may
1980 modify code generation, for the otherwise-unused
1981 default definition would never go away, modifying SSA
1982 version numbers all over. */
1983 gimple_debug_bind_reset_value (stmt);
1984 update_stmt (stmt);
1987 else
1989 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1990 maybe_replace_use (use_p);
1994 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1995 Also register definitions for names whose underlying symbol is
1996 marked for renaming. */
1997 bool to_delete = false;
1998 if (register_defs_p (stmt))
1999 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2000 to_delete |= maybe_register_def (def_p, stmt, gsi);
2002 return to_delete;
2006 /* Visit all the successor blocks of BB looking for PHI nodes. For
2007 every PHI node found, check if any of its arguments is in
2008 OLD_SSA_NAMES. If so, and if the argument has a current reaching
2009 definition, replace it. */
2011 static void
2012 rewrite_update_phi_arguments (basic_block bb)
2014 edge e;
2015 edge_iterator ei;
2016 unsigned i;
2018 FOR_EACH_EDGE (e, ei, bb->succs)
2020 gphi *phi;
2021 vec<gphi *> phis;
2023 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2024 continue;
2026 phis = phis_to_rewrite[e->dest->index];
2027 FOR_EACH_VEC_ELT (phis, i, phi)
2029 tree arg, lhs_sym, reaching_def = NULL;
2030 use_operand_p arg_p;
2032 gcc_checking_assert (rewrite_uses_p (phi));
2034 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2035 arg = USE_FROM_PTR (arg_p);
2037 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2038 continue;
2040 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2042 if (arg == NULL_TREE)
2044 /* When updating a PHI node for a recently introduced
2045 symbol we may find NULL arguments. That's why we
2046 take the symbol from the LHS of the PHI node. */
2047 reaching_def = get_reaching_def (lhs_sym);
2050 else
2052 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2054 if (marked_for_renaming (sym))
2055 reaching_def = get_reaching_def (sym);
2056 else if (is_old_name (arg))
2057 reaching_def = get_reaching_def (arg);
2060 /* Update the argument if there is a reaching def. */
2061 if (reaching_def)
2063 source_location locus;
2064 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2066 SET_USE (arg_p, reaching_def);
2068 /* Virtual operands do not need a location. */
2069 if (virtual_operand_p (reaching_def))
2070 locus = UNKNOWN_LOCATION;
2071 else
2073 gimple stmt = SSA_NAME_DEF_STMT (reaching_def);
2074 gphi *other_phi = dyn_cast <gphi *> (stmt);
2076 /* Single element PHI nodes behave like copies, so get the
2077 location from the phi argument. */
2078 if (other_phi
2079 && gimple_phi_num_args (other_phi) == 1)
2080 locus = gimple_phi_arg_location (other_phi, 0);
2081 else
2082 locus = gimple_location (stmt);
2085 gimple_phi_arg_set_location (phi, arg_i, locus);
2089 if (e->flags & EDGE_ABNORMAL)
2090 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2095 class rewrite_update_dom_walker : public dom_walker
2097 public:
2098 rewrite_update_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2100 virtual void before_dom_children (basic_block);
2101 virtual void after_dom_children (basic_block);
2104 /* Initialization of block data structures for the incremental SSA
2105 update pass. Create a block local stack of reaching definitions
2106 for new SSA names produced in this block (BLOCK_DEFS). Register
2107 new definitions for every PHI node in the block. */
2109 void
2110 rewrite_update_dom_walker::before_dom_children (basic_block bb)
2112 bool is_abnormal_phi;
2114 if (dump_file && (dump_flags & TDF_DETAILS))
2115 fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2116 bb->index);
2118 /* Mark the unwind point for this block. */
2119 block_defs_stack.safe_push (NULL_TREE);
2121 if (!bitmap_bit_p (blocks_to_update, bb->index))
2122 return;
2124 /* Mark the LHS if any of the arguments flows through an abnormal
2125 edge. */
2126 is_abnormal_phi = bb_has_abnormal_pred (bb);
2128 /* If any of the PHI nodes is a replacement for a name in
2129 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2130 register it as a new definition for its corresponding name. Also
2131 register definitions for names whose underlying symbols are
2132 marked for renaming. */
2133 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2134 gsi_next (&gsi))
2136 tree lhs, lhs_sym;
2137 gphi *phi = gsi.phi ();
2139 if (!register_defs_p (phi))
2140 continue;
2142 lhs = gimple_phi_result (phi);
2143 lhs_sym = SSA_NAME_VAR (lhs);
2145 if (marked_for_renaming (lhs_sym))
2146 register_new_update_single (lhs, lhs_sym);
2147 else
2150 /* If LHS is a new name, register a new definition for all
2151 the names replaced by LHS. */
2152 if (is_new_name (lhs))
2153 register_new_update_set (lhs, names_replaced_by (lhs));
2155 /* If LHS is an OLD name, register it as a new definition
2156 for itself. */
2157 if (is_old_name (lhs))
2158 register_new_update_single (lhs, lhs);
2161 if (is_abnormal_phi)
2162 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2165 /* Step 2. Rewrite every variable used in each statement in the block. */
2166 if (bitmap_bit_p (interesting_blocks, bb->index))
2168 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2169 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2170 if (rewrite_update_stmt (gsi_stmt (gsi), gsi))
2171 gsi_remove (&gsi, true);
2172 else
2173 gsi_next (&gsi);
2176 /* Step 3. Update PHI nodes. */
2177 rewrite_update_phi_arguments (bb);
2180 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2181 the current reaching definition of every name re-written in BB to
2182 the original reaching definition before visiting BB. This
2183 unwinding must be done in the opposite order to what is done in
2184 register_new_update_set. */
2186 void
2187 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2189 while (block_defs_stack.length () > 0)
2191 tree var = block_defs_stack.pop ();
2192 tree saved_def;
2194 /* NULL indicates the unwind stop point for this block (see
2195 rewrite_update_enter_block). */
2196 if (var == NULL)
2197 return;
2199 saved_def = block_defs_stack.pop ();
2200 get_common_info (var)->current_def = saved_def;
2205 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2206 form.
2208 ENTRY indicates the block where to start. Every block dominated by
2209 ENTRY will be rewritten.
2211 WHAT indicates what actions will be taken by the renamer (see enum
2212 rewrite_mode).
2214 BLOCKS are the set of interesting blocks for the dominator walker
2215 to process. If this set is NULL, then all the nodes dominated
2216 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2217 are not present in BLOCKS are ignored. */
2219 static void
2220 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2222 /* Rewrite all the basic blocks in the program. */
2223 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2225 block_defs_stack.create (10);
2227 /* Recursively walk the dominator tree rewriting each statement in
2228 each basic block. */
2229 if (what == REWRITE_ALL)
2230 rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2231 else if (what == REWRITE_UPDATE)
2232 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2233 else
2234 gcc_unreachable ();
2236 /* Debugging dumps. */
2237 if (dump_file && (dump_flags & TDF_STATS))
2239 dump_dfa_stats (dump_file);
2240 if (var_infos)
2241 dump_tree_ssa_stats (dump_file);
2244 block_defs_stack.release ();
2246 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2249 class mark_def_dom_walker : public dom_walker
2251 public:
2252 mark_def_dom_walker (cdi_direction direction);
2253 ~mark_def_dom_walker ();
2255 virtual void before_dom_children (basic_block);
2257 private:
2258 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2259 large enough to accommodate all the variables referenced in the
2260 function, not just the ones we are renaming. */
2261 bitmap m_kills;
2264 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2265 : dom_walker (direction), m_kills (BITMAP_ALLOC (NULL))
2269 mark_def_dom_walker::~mark_def_dom_walker ()
2271 BITMAP_FREE (m_kills);
2274 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2275 at the start of each block, and call mark_def_sites for each statement. */
2277 void
2278 mark_def_dom_walker::before_dom_children (basic_block bb)
2280 gimple_stmt_iterator gsi;
2282 bitmap_clear (m_kills);
2283 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2284 mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2287 /* Initialize internal data needed during renaming. */
2289 static void
2290 init_ssa_renamer (void)
2292 cfun->gimple_df->in_ssa_p = false;
2294 /* Allocate memory for the DEF_BLOCKS hash table. */
2295 gcc_assert (!var_infos);
2296 var_infos = new hash_table<var_info_hasher>
2297 (vec_safe_length (cfun->local_decls));
2299 bitmap_obstack_initialize (&update_ssa_obstack);
2303 /* Deallocate internal data structures used by the renamer. */
2305 static void
2306 fini_ssa_renamer (void)
2308 delete var_infos;
2309 var_infos = NULL;
2311 bitmap_obstack_release (&update_ssa_obstack);
2313 cfun->gimple_df->ssa_renaming_needed = 0;
2314 cfun->gimple_df->rename_vops = 0;
2315 cfun->gimple_df->in_ssa_p = true;
2318 /* Main entry point into the SSA builder. The renaming process
2319 proceeds in four main phases:
2321 1- Compute dominance frontier and immediate dominators, needed to
2322 insert PHI nodes and rename the function in dominator tree
2323 order.
2325 2- Find and mark all the blocks that define variables.
2327 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2329 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2331 Steps 3 and 4 are done using the dominator tree walker
2332 (walk_dominator_tree). */
2334 namespace {
2336 const pass_data pass_data_build_ssa =
2338 GIMPLE_PASS, /* type */
2339 "ssa", /* name */
2340 OPTGROUP_NONE, /* optinfo_flags */
2341 TV_TREE_SSA_OTHER, /* tv_id */
2342 PROP_cfg, /* properties_required */
2343 PROP_ssa, /* properties_provided */
2344 0, /* properties_destroyed */
2345 0, /* todo_flags_start */
2346 TODO_remove_unused_locals, /* todo_flags_finish */
2349 class pass_build_ssa : public gimple_opt_pass
2351 public:
2352 pass_build_ssa (gcc::context *ctxt)
2353 : gimple_opt_pass (pass_data_build_ssa, ctxt)
2356 /* opt_pass methods: */
2357 virtual bool gate (function *fun)
2359 /* Do nothing for funcions that was produced already in SSA form. */
2360 return !(fun->curr_properties & PROP_ssa);
2363 virtual unsigned int execute (function *);
2365 }; // class pass_build_ssa
2367 unsigned int
2368 pass_build_ssa::execute (function *fun)
2370 bitmap_head *dfs;
2371 basic_block bb;
2372 unsigned i;
2374 /* Initialize operand data structures. */
2375 init_ssa_operands (fun);
2377 /* Initialize internal data needed by the renamer. */
2378 init_ssa_renamer ();
2380 /* Initialize the set of interesting blocks. The callback
2381 mark_def_sites will add to this set those blocks that the renamer
2382 should process. */
2383 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2384 bitmap_clear (interesting_blocks);
2386 /* Initialize dominance frontier. */
2387 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2388 FOR_EACH_BB_FN (bb, fun)
2389 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2391 /* 1- Compute dominance frontiers. */
2392 calculate_dominance_info (CDI_DOMINATORS);
2393 compute_dominance_frontiers (dfs);
2395 /* 2- Find and mark definition sites. */
2396 mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2398 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2399 insert_phi_nodes (dfs);
2401 /* 4- Rename all the blocks. */
2402 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
2404 /* Free allocated memory. */
2405 FOR_EACH_BB_FN (bb, fun)
2406 bitmap_clear (&dfs[bb->index]);
2407 free (dfs);
2409 sbitmap_free (interesting_blocks);
2411 fini_ssa_renamer ();
2413 /* Try to get rid of all gimplifier generated temporaries by making
2414 its SSA names anonymous. This way we can garbage collect them
2415 all after removing unused locals which we do in our TODO. */
2416 for (i = 1; i < num_ssa_names; ++i)
2418 tree decl, name = ssa_name (i);
2419 if (!name
2420 || SSA_NAME_IS_DEFAULT_DEF (name))
2421 continue;
2422 decl = SSA_NAME_VAR (name);
2423 if (decl
2424 && TREE_CODE (decl) == VAR_DECL
2425 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2426 && DECL_IGNORED_P (decl))
2427 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2430 return 0;
2433 } // anon namespace
2435 gimple_opt_pass *
2436 make_pass_build_ssa (gcc::context *ctxt)
2438 return new pass_build_ssa (ctxt);
2442 /* Mark the definition of VAR at STMT and BB as interesting for the
2443 renamer. BLOCKS is the set of blocks that need updating. */
2445 static void
2446 mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2448 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2449 set_register_defs (stmt, true);
2451 if (insert_phi_p)
2453 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2455 set_def_block (var, bb, is_phi_p);
2457 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2458 site for both itself and all the old names replaced by it. */
2459 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2461 bitmap_iterator bi;
2462 unsigned i;
2463 bitmap set = names_replaced_by (var);
2464 if (set)
2465 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2466 set_def_block (ssa_name (i), bb, is_phi_p);
2472 /* Mark the use of VAR at STMT and BB as interesting for the
2473 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2474 nodes. */
2476 static inline void
2477 mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2479 basic_block def_bb = gimple_bb (stmt);
2481 mark_block_for_update (def_bb);
2482 mark_block_for_update (bb);
2484 if (gimple_code (stmt) == GIMPLE_PHI)
2485 mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt));
2486 else
2488 set_rewrite_uses (stmt, true);
2490 if (is_gimple_debug (stmt))
2491 return;
2494 /* If VAR has not been defined in BB, then it is live-on-entry
2495 to BB. Note that we cannot just use the block holding VAR's
2496 definition because if VAR is one of the names in OLD_SSA_NAMES,
2497 it will have several definitions (itself and all the names that
2498 replace it). */
2499 if (insert_phi_p)
2501 struct def_blocks_d *db_p = get_def_blocks_for (get_common_info (var));
2502 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2503 set_livein_block (var, bb);
2508 /* Do a dominator walk starting at BB processing statements that
2509 reference symbols in SSA operands. This is very similar to
2510 mark_def_sites, but the scan handles statements whose operands may
2511 already be SSA names.
2513 If INSERT_PHI_P is true, mark those uses as live in the
2514 corresponding block. This is later used by the PHI placement
2515 algorithm to make PHI pruning decisions.
2517 FIXME. Most of this would be unnecessary if we could associate a
2518 symbol to all the SSA names that reference it. But that
2519 sounds like it would be expensive to maintain. Still, it
2520 would be interesting to see if it makes better sense to do
2521 that. */
2523 static void
2524 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2526 basic_block son;
2527 edge e;
2528 edge_iterator ei;
2530 mark_block_for_update (bb);
2532 /* Process PHI nodes marking interesting those that define or use
2533 the symbols that we are interested in. */
2534 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
2535 gsi_next (&si))
2537 gphi *phi = si.phi ();
2538 tree lhs_sym, lhs = gimple_phi_result (phi);
2540 if (TREE_CODE (lhs) == SSA_NAME
2541 && (! virtual_operand_p (lhs)
2542 || ! cfun->gimple_df->rename_vops))
2543 continue;
2545 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2546 mark_for_renaming (lhs_sym);
2547 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2549 /* Mark the uses in phi nodes as interesting. It would be more correct
2550 to process the arguments of the phi nodes of the successor edges of
2551 BB at the end of prepare_block_for_update, however, that turns out
2552 to be significantly more expensive. Doing it here is conservatively
2553 correct -- it may only cause us to believe a value to be live in a
2554 block that also contains its definition, and thus insert a few more
2555 phi nodes for it. */
2556 FOR_EACH_EDGE (e, ei, bb->preds)
2557 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2560 /* Process the statements. */
2561 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
2562 gsi_next (&si))
2564 gimple stmt;
2565 ssa_op_iter i;
2566 use_operand_p use_p;
2567 def_operand_p def_p;
2569 stmt = gsi_stmt (si);
2571 if (cfun->gimple_df->rename_vops
2572 && gimple_vuse (stmt))
2574 tree use = gimple_vuse (stmt);
2575 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2576 mark_for_renaming (sym);
2577 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2580 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2582 tree use = USE_FROM_PTR (use_p);
2583 if (!DECL_P (use))
2584 continue;
2585 mark_for_renaming (use);
2586 mark_use_interesting (use, stmt, bb, insert_phi_p);
2589 if (cfun->gimple_df->rename_vops
2590 && gimple_vdef (stmt))
2592 tree def = gimple_vdef (stmt);
2593 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2594 mark_for_renaming (sym);
2595 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2598 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2600 tree def = DEF_FROM_PTR (def_p);
2601 if (!DECL_P (def))
2602 continue;
2603 mark_for_renaming (def);
2604 mark_def_interesting (def, stmt, bb, insert_phi_p);
2608 /* Now visit all the blocks dominated by BB. */
2609 for (son = first_dom_son (CDI_DOMINATORS, bb);
2610 son;
2611 son = next_dom_son (CDI_DOMINATORS, son))
2612 prepare_block_for_update (son, insert_phi_p);
2616 /* Helper for prepare_names_to_update. Mark all the use sites for
2617 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2618 prepare_names_to_update. */
2620 static void
2621 prepare_use_sites_for (tree name, bool insert_phi_p)
2623 use_operand_p use_p;
2624 imm_use_iterator iter;
2626 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2628 gimple stmt = USE_STMT (use_p);
2629 basic_block bb = gimple_bb (stmt);
2631 if (gimple_code (stmt) == GIMPLE_PHI)
2633 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2634 edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix);
2635 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2637 else
2639 /* For regular statements, mark this as an interesting use
2640 for NAME. */
2641 mark_use_interesting (name, stmt, bb, insert_phi_p);
2647 /* Helper for prepare_names_to_update. Mark the definition site for
2648 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2649 prepare_names_to_update. */
2651 static void
2652 prepare_def_site_for (tree name, bool insert_phi_p)
2654 gimple stmt;
2655 basic_block bb;
2657 gcc_checking_assert (names_to_release == NULL
2658 || !bitmap_bit_p (names_to_release,
2659 SSA_NAME_VERSION (name)));
2661 stmt = SSA_NAME_DEF_STMT (name);
2662 bb = gimple_bb (stmt);
2663 if (bb)
2665 gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2666 mark_block_for_update (bb);
2667 mark_def_interesting (name, stmt, bb, insert_phi_p);
2672 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2673 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2674 PHI nodes for newly created names. */
2676 static void
2677 prepare_names_to_update (bool insert_phi_p)
2679 unsigned i = 0;
2680 bitmap_iterator bi;
2681 sbitmap_iterator sbi;
2683 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2684 remove it from NEW_SSA_NAMES so that we don't try to visit its
2685 defining basic block (which most likely doesn't exist). Notice
2686 that we cannot do the same with names in OLD_SSA_NAMES because we
2687 want to replace existing instances. */
2688 if (names_to_release)
2689 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2690 bitmap_clear_bit (new_ssa_names, i);
2692 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2693 names may be considered to be live-in on blocks that contain
2694 definitions for their replacements. */
2695 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2696 prepare_def_site_for (ssa_name (i), insert_phi_p);
2698 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2699 OLD_SSA_NAMES, but we have to ignore its definition site. */
2700 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2702 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2703 prepare_def_site_for (ssa_name (i), insert_phi_p);
2704 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2709 /* Dump all the names replaced by NAME to FILE. */
2711 void
2712 dump_names_replaced_by (FILE *file, tree name)
2714 unsigned i;
2715 bitmap old_set;
2716 bitmap_iterator bi;
2718 print_generic_expr (file, name, 0);
2719 fprintf (file, " -> { ");
2721 old_set = names_replaced_by (name);
2722 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2724 print_generic_expr (file, ssa_name (i), 0);
2725 fprintf (file, " ");
2728 fprintf (file, "}\n");
2732 /* Dump all the names replaced by NAME to stderr. */
2734 DEBUG_FUNCTION void
2735 debug_names_replaced_by (tree name)
2737 dump_names_replaced_by (stderr, name);
2741 /* Dump SSA update information to FILE. */
2743 void
2744 dump_update_ssa (FILE *file)
2746 unsigned i = 0;
2747 bitmap_iterator bi;
2749 if (!need_ssa_update_p (cfun))
2750 return;
2752 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2754 sbitmap_iterator sbi;
2756 fprintf (file, "\nSSA replacement table\n");
2757 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2758 "O_1, ..., O_j\n\n");
2760 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2761 dump_names_replaced_by (file, ssa_name (i));
2764 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2766 fprintf (file, "\nSymbols to be put in SSA form\n");
2767 dump_decl_set (file, symbols_to_rename_set);
2768 fprintf (file, "\n");
2771 if (names_to_release && !bitmap_empty_p (names_to_release))
2773 fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2774 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2776 print_generic_expr (file, ssa_name (i), 0);
2777 fprintf (file, " ");
2779 fprintf (file, "\n");
2784 /* Dump SSA update information to stderr. */
2786 DEBUG_FUNCTION void
2787 debug_update_ssa (void)
2789 dump_update_ssa (stderr);
2793 /* Initialize data structures used for incremental SSA updates. */
2795 static void
2796 init_update_ssa (struct function *fn)
2798 /* Reserve more space than the current number of names. The calls to
2799 add_new_name_mapping are typically done after creating new SSA
2800 names, so we'll need to reallocate these arrays. */
2801 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2802 bitmap_clear (old_ssa_names);
2804 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2805 bitmap_clear (new_ssa_names);
2807 bitmap_obstack_initialize (&update_ssa_obstack);
2809 names_to_release = NULL;
2810 update_ssa_initialized_fn = fn;
2814 /* Deallocate data structures used for incremental SSA updates. */
2816 void
2817 delete_update_ssa (void)
2819 unsigned i;
2820 bitmap_iterator bi;
2822 sbitmap_free (old_ssa_names);
2823 old_ssa_names = NULL;
2825 sbitmap_free (new_ssa_names);
2826 new_ssa_names = NULL;
2828 BITMAP_FREE (symbols_to_rename_set);
2829 symbols_to_rename_set = NULL;
2830 symbols_to_rename.release ();
2832 if (names_to_release)
2834 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2835 release_ssa_name (ssa_name (i));
2836 BITMAP_FREE (names_to_release);
2839 clear_ssa_name_info ();
2841 fini_ssa_renamer ();
2843 if (blocks_with_phis_to_rewrite)
2844 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2846 vec<gphi *> phis = phis_to_rewrite[i];
2847 phis.release ();
2848 phis_to_rewrite[i].create (0);
2851 BITMAP_FREE (blocks_with_phis_to_rewrite);
2852 BITMAP_FREE (blocks_to_update);
2854 update_ssa_initialized_fn = NULL;
2858 /* Create a new name for OLD_NAME in statement STMT and replace the
2859 operand pointed to by DEF_P with the newly created name. If DEF_P
2860 is NULL then STMT should be a GIMPLE assignment.
2861 Return the new name and register the replacement mapping <NEW, OLD> in
2862 update_ssa's tables. */
2864 tree
2865 create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
2867 tree new_name;
2869 timevar_push (TV_TREE_SSA_INCREMENTAL);
2871 if (!update_ssa_initialized_fn)
2872 init_update_ssa (cfun);
2874 gcc_assert (update_ssa_initialized_fn == cfun);
2876 new_name = duplicate_ssa_name (old_name, stmt);
2877 if (def)
2878 SET_DEF (def, new_name);
2879 else
2880 gimple_assign_set_lhs (stmt, new_name);
2882 if (gimple_code (stmt) == GIMPLE_PHI)
2884 basic_block bb = gimple_bb (stmt);
2886 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2887 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2890 add_new_name_mapping (new_name, old_name);
2892 /* For the benefit of passes that will be updating the SSA form on
2893 their own, set the current reaching definition of OLD_NAME to be
2894 NEW_NAME. */
2895 get_ssa_name_ann (old_name)->info.current_def = new_name;
2897 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2899 return new_name;
2903 /* Mark virtual operands of FN for renaming by update_ssa. */
2905 void
2906 mark_virtual_operands_for_renaming (struct function *fn)
2908 fn->gimple_df->ssa_renaming_needed = 1;
2909 fn->gimple_df->rename_vops = 1;
2912 /* Replace all uses of NAME by underlying variable and mark it
2913 for renaming. This assumes the defining statement of NAME is
2914 going to be removed. */
2916 void
2917 mark_virtual_operand_for_renaming (tree name)
2919 tree name_var = SSA_NAME_VAR (name);
2920 bool used = false;
2921 imm_use_iterator iter;
2922 use_operand_p use_p;
2923 gimple stmt;
2925 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
2926 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
2928 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2929 SET_USE (use_p, name_var);
2930 used = true;
2932 if (used)
2933 mark_virtual_operands_for_renaming (cfun);
2936 /* Replace all uses of the virtual PHI result by its underlying variable
2937 and mark it for renaming. This assumes the PHI node is going to be
2938 removed. */
2940 void
2941 mark_virtual_phi_result_for_renaming (gphi *phi)
2943 if (dump_file && (dump_flags & TDF_DETAILS))
2945 fprintf (dump_file, "Marking result for renaming : ");
2946 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
2947 fprintf (dump_file, "\n");
2950 mark_virtual_operand_for_renaming (gimple_phi_result (phi));
2953 /* Return true if there is any work to be done by update_ssa
2954 for function FN. */
2956 bool
2957 need_ssa_update_p (struct function *fn)
2959 gcc_assert (fn != NULL);
2960 return (update_ssa_initialized_fn == fn
2961 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
2964 /* Return true if name N has been registered in the replacement table. */
2966 bool
2967 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
2969 if (!update_ssa_initialized_fn)
2970 return false;
2972 gcc_assert (update_ssa_initialized_fn == cfun);
2974 return is_new_name (n) || is_old_name (n);
2978 /* Mark NAME to be released after update_ssa has finished. */
2980 void
2981 release_ssa_name_after_update_ssa (tree name)
2983 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
2985 if (names_to_release == NULL)
2986 names_to_release = BITMAP_ALLOC (NULL);
2988 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2992 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2993 frontier information. BLOCKS is the set of blocks to be updated.
2995 This is slightly different than the regular PHI insertion
2996 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2997 real names (i.e., GIMPLE registers) are inserted:
2999 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3000 nodes inside the region affected by the block that defines VAR
3001 and the blocks that define all its replacements. All these
3002 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3004 First, we compute the entry point to the region (ENTRY). This is
3005 given by the nearest common dominator to all the definition
3006 blocks. When computing the iterated dominance frontier (IDF), any
3007 block not strictly dominated by ENTRY is ignored.
3009 We then call the standard PHI insertion algorithm with the pruned
3010 IDF.
3012 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3013 names is not pruned. PHI nodes are inserted at every IDF block. */
3015 static void
3016 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
3017 unsigned update_flags)
3019 basic_block entry;
3020 struct def_blocks_d *db;
3021 bitmap idf, pruned_idf;
3022 bitmap_iterator bi;
3023 unsigned i;
3025 if (TREE_CODE (var) == SSA_NAME)
3026 gcc_checking_assert (is_old_name (var));
3027 else
3028 gcc_checking_assert (marked_for_renaming (var));
3030 /* Get all the definition sites for VAR. */
3031 db = find_def_blocks_for (var);
3033 /* No need to do anything if there were no definitions to VAR. */
3034 if (db == NULL || bitmap_empty_p (db->def_blocks))
3035 return;
3037 /* Compute the initial iterated dominance frontier. */
3038 idf = compute_idf (db->def_blocks, dfs);
3039 pruned_idf = BITMAP_ALLOC (NULL);
3041 if (TREE_CODE (var) == SSA_NAME)
3043 if (update_flags == TODO_update_ssa)
3045 /* If doing regular SSA updates for GIMPLE registers, we are
3046 only interested in IDF blocks dominated by the nearest
3047 common dominator of all the definition blocks. */
3048 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3049 db->def_blocks);
3050 if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3051 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3052 if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3053 && dominated_by_p (CDI_DOMINATORS,
3054 BASIC_BLOCK_FOR_FN (cfun, i), entry))
3055 bitmap_set_bit (pruned_idf, i);
3057 else
3059 /* Otherwise, do not prune the IDF for VAR. */
3060 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3061 bitmap_copy (pruned_idf, idf);
3064 else
3066 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3067 for the first time, so we need to compute the full IDF for
3068 it. */
3069 bitmap_copy (pruned_idf, idf);
3072 if (!bitmap_empty_p (pruned_idf))
3074 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3075 are included in the region to be updated. The feeding blocks
3076 are important to guarantee that the PHI arguments are renamed
3077 properly. */
3079 /* FIXME, this is not needed if we are updating symbols. We are
3080 already starting at the ENTRY block anyway. */
3081 bitmap_ior_into (blocks, pruned_idf);
3082 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3084 edge e;
3085 edge_iterator ei;
3086 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3088 FOR_EACH_EDGE (e, ei, bb->preds)
3089 if (e->src->index >= 0)
3090 bitmap_set_bit (blocks, e->src->index);
3093 insert_phi_nodes_for (var, pruned_idf, true);
3096 BITMAP_FREE (pruned_idf);
3097 BITMAP_FREE (idf);
3100 /* Sort symbols_to_rename after their DECL_UID. */
3102 static int
3103 insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3105 const_tree syma = *(const const_tree *)a;
3106 const_tree symb = *(const const_tree *)b;
3107 if (DECL_UID (syma) == DECL_UID (symb))
3108 return 0;
3109 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3112 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3113 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3115 1- The names in OLD_SSA_NAMES dominated by the definitions of
3116 NEW_SSA_NAMES are all re-written to be reached by the
3117 appropriate definition from NEW_SSA_NAMES.
3119 2- If needed, new PHI nodes are added to the iterated dominance
3120 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3122 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3123 calling create_new_def_for to create new defs for names that the
3124 caller wants to replace.
3126 The caller cretaes the new names to be inserted and the names that need
3127 to be replaced by calling create_new_def_for for each old definition
3128 to be replaced. Note that the function assumes that the
3129 new defining statement has already been inserted in the IL.
3131 For instance, given the following code:
3133 1 L0:
3134 2 x_1 = PHI (0, x_5)
3135 3 if (x_1 < 10)
3136 4 if (x_1 > 7)
3137 5 y_2 = 0
3138 6 else
3139 7 y_3 = x_1 + x_7
3140 8 endif
3141 9 x_5 = x_1 + 1
3142 10 goto L0;
3143 11 endif
3145 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3147 1 L0:
3148 2 x_1 = PHI (0, x_5)
3149 3 if (x_1 < 10)
3150 4 x_10 = ...
3151 5 if (x_1 > 7)
3152 6 y_2 = 0
3153 7 else
3154 8 x_11 = ...
3155 9 y_3 = x_1 + x_7
3156 10 endif
3157 11 x_5 = x_1 + 1
3158 12 goto L0;
3159 13 endif
3161 We want to replace all the uses of x_1 with the new definitions of
3162 x_10 and x_11. Note that the only uses that should be replaced are
3163 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3164 *not* be replaced (this is why we cannot just mark symbol 'x' for
3165 renaming).
3167 Additionally, we may need to insert a PHI node at line 11 because
3168 that is a merge point for x_10 and x_11. So the use of x_1 at line
3169 11 will be replaced with the new PHI node. The insertion of PHI
3170 nodes is optional. They are not strictly necessary to preserve the
3171 SSA form, and depending on what the caller inserted, they may not
3172 even be useful for the optimizers. UPDATE_FLAGS controls various
3173 aspects of how update_ssa operates, see the documentation for
3174 TODO_update_ssa*. */
3176 void
3177 update_ssa (unsigned update_flags)
3179 basic_block bb, start_bb;
3180 bitmap_iterator bi;
3181 unsigned i = 0;
3182 bool insert_phi_p;
3183 sbitmap_iterator sbi;
3184 tree sym;
3186 /* Only one update flag should be set. */
3187 gcc_assert (update_flags == TODO_update_ssa
3188 || update_flags == TODO_update_ssa_no_phi
3189 || update_flags == TODO_update_ssa_full_phi
3190 || update_flags == TODO_update_ssa_only_virtuals);
3192 if (!need_ssa_update_p (cfun))
3193 return;
3195 #ifdef ENABLE_CHECKING
3196 timevar_push (TV_TREE_STMT_VERIFY);
3198 bool err = false;
3200 FOR_EACH_BB_FN (bb, cfun)
3202 gimple_stmt_iterator gsi;
3203 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3205 gimple stmt = gsi_stmt (gsi);
3207 ssa_op_iter i;
3208 use_operand_p use_p;
3209 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3211 tree use = USE_FROM_PTR (use_p);
3212 if (TREE_CODE (use) != SSA_NAME)
3213 continue;
3215 if (SSA_NAME_IN_FREE_LIST (use))
3217 error ("statement uses released SSA name:");
3218 debug_gimple_stmt (stmt);
3219 fprintf (stderr, "The use of ");
3220 print_generic_expr (stderr, use, 0);
3221 fprintf (stderr," should have been replaced\n");
3222 err = true;
3228 if (err)
3229 internal_error ("cannot update SSA form");
3231 timevar_pop (TV_TREE_STMT_VERIFY);
3232 #endif
3234 timevar_push (TV_TREE_SSA_INCREMENTAL);
3236 if (dump_file && (dump_flags & TDF_DETAILS))
3237 fprintf (dump_file, "\nUpdating SSA:\n");
3239 if (!update_ssa_initialized_fn)
3240 init_update_ssa (cfun);
3241 else if (update_flags == TODO_update_ssa_only_virtuals)
3243 /* If we only need to update virtuals, remove all the mappings for
3244 real names before proceeding. The caller is responsible for
3245 having dealt with the name mappings before calling update_ssa. */
3246 bitmap_clear (old_ssa_names);
3247 bitmap_clear (new_ssa_names);
3250 gcc_assert (update_ssa_initialized_fn == cfun);
3252 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3253 if (!phis_to_rewrite.exists ())
3254 phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3255 blocks_to_update = BITMAP_ALLOC (NULL);
3257 /* Ensure that the dominance information is up-to-date. */
3258 calculate_dominance_info (CDI_DOMINATORS);
3260 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3262 /* If there are names defined in the replacement table, prepare
3263 definition and use sites for all the names in NEW_SSA_NAMES and
3264 OLD_SSA_NAMES. */
3265 if (bitmap_first_set_bit (new_ssa_names) >= 0)
3267 prepare_names_to_update (insert_phi_p);
3269 /* If all the names in NEW_SSA_NAMES had been marked for
3270 removal, and there are no symbols to rename, then there's
3271 nothing else to do. */
3272 if (bitmap_first_set_bit (new_ssa_names) < 0
3273 && !cfun->gimple_df->ssa_renaming_needed)
3274 goto done;
3277 /* Next, determine the block at which to start the renaming process. */
3278 if (cfun->gimple_df->ssa_renaming_needed)
3280 /* If we rename bare symbols initialize the mapping to
3281 auxiliar info we need to keep track of. */
3282 var_infos = new hash_table<var_info_hasher> (47);
3284 /* If we have to rename some symbols from scratch, we need to
3285 start the process at the root of the CFG. FIXME, it should
3286 be possible to determine the nearest block that had a
3287 definition for each of the symbols that are marked for
3288 updating. For now this seems more work than it's worth. */
3289 start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3291 /* Traverse the CFG looking for existing definitions and uses of
3292 symbols in SSA operands. Mark interesting blocks and
3293 statements and set local live-in information for the PHI
3294 placement heuristics. */
3295 prepare_block_for_update (start_bb, insert_phi_p);
3297 #ifdef ENABLE_CHECKING
3298 for (i = 1; i < num_ssa_names; ++i)
3300 tree name = ssa_name (i);
3301 if (!name
3302 || virtual_operand_p (name))
3303 continue;
3305 /* For all but virtual operands, which do not have SSA names
3306 with overlapping life ranges, ensure that symbols marked
3307 for renaming do not have existing SSA names associated with
3308 them as we do not re-write them out-of-SSA before going
3309 into SSA for the remaining symbol uses. */
3310 if (marked_for_renaming (SSA_NAME_VAR (name)))
3312 fprintf (stderr, "Existing SSA name for symbol marked for "
3313 "renaming: ");
3314 print_generic_expr (stderr, name, TDF_SLIM);
3315 fprintf (stderr, "\n");
3316 internal_error ("SSA corruption");
3319 #endif
3321 else
3323 /* Otherwise, the entry block to the region is the nearest
3324 common dominator for the blocks in BLOCKS. */
3325 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3326 blocks_to_update);
3329 /* If requested, insert PHI nodes at the iterated dominance frontier
3330 of every block, creating new definitions for names in OLD_SSA_NAMES
3331 and for symbols found. */
3332 if (insert_phi_p)
3334 bitmap_head *dfs;
3336 /* If the caller requested PHI nodes to be added, compute
3337 dominance frontiers. */
3338 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3339 FOR_EACH_BB_FN (bb, cfun)
3340 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3341 compute_dominance_frontiers (dfs);
3343 if (bitmap_first_set_bit (old_ssa_names) >= 0)
3345 sbitmap_iterator sbi;
3347 /* insert_update_phi_nodes_for will call add_new_name_mapping
3348 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3349 will grow while we are traversing it (but it will not
3350 gain any new members). Copy OLD_SSA_NAMES to a temporary
3351 for traversal. */
3352 sbitmap tmp = sbitmap_alloc (SBITMAP_SIZE (old_ssa_names));
3353 bitmap_copy (tmp, old_ssa_names);
3354 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3355 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3356 update_flags);
3357 sbitmap_free (tmp);
3360 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3361 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3362 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3363 update_flags);
3365 FOR_EACH_BB_FN (bb, cfun)
3366 bitmap_clear (&dfs[bb->index]);
3367 free (dfs);
3369 /* Insertion of PHI nodes may have added blocks to the region.
3370 We need to re-compute START_BB to include the newly added
3371 blocks. */
3372 if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3373 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3374 blocks_to_update);
3377 /* Reset the current definition for name and symbol before renaming
3378 the sub-graph. */
3379 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3380 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3382 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3383 get_var_info (sym)->info.current_def = NULL_TREE;
3385 /* Now start the renaming process at START_BB. */
3386 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3387 bitmap_clear (interesting_blocks);
3388 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3389 bitmap_set_bit (interesting_blocks, i);
3391 rewrite_blocks (start_bb, REWRITE_UPDATE);
3393 sbitmap_free (interesting_blocks);
3395 /* Debugging dumps. */
3396 if (dump_file)
3398 int c;
3399 unsigned i;
3401 dump_update_ssa (dump_file);
3403 fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3404 start_bb->index);
3406 c = 0;
3407 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3408 c++;
3409 fprintf (dump_file, "Number of blocks in CFG: %d\n",
3410 last_basic_block_for_fn (cfun));
3411 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3412 c, PERCENT (c, last_basic_block_for_fn (cfun)));
3414 if (dump_flags & TDF_DETAILS)
3416 fprintf (dump_file, "Affected blocks:");
3417 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3418 fprintf (dump_file, " %u", i);
3419 fprintf (dump_file, "\n");
3422 fprintf (dump_file, "\n\n");
3425 /* Free allocated memory. */
3426 done:
3427 delete_update_ssa ();
3429 timevar_pop (TV_TREE_SSA_INCREMENTAL);