Daily bump.
[official-gcc.git] / gcc / tree-into-ssa.c
blobd4056373f318dfee0714363de5f11c5e1a437005
1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2017 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 "backend.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "tree-pass.h"
29 #include "ssa.h"
30 #include "gimple-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "langhooks.h"
33 #include "cfganal.h"
34 #include "gimple-iterator.h"
35 #include "tree-cfg.h"
36 #include "tree-into-ssa.h"
37 #include "tree-dfa.h"
38 #include "tree-ssa.h"
39 #include "domwalk.h"
40 #include "statistics.h"
41 #include "asan.h"
43 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
45 /* This file builds the SSA form for a function as described in:
46 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
47 Computing Static Single Assignment Form and the Control Dependence
48 Graph. ACM Transactions on Programming Languages and Systems,
49 13(4):451-490, October 1991. */
51 /* Structure to map a variable VAR to the set of blocks that contain
52 definitions for VAR. */
53 struct def_blocks
55 /* Blocks that contain definitions of VAR. Bit I will be set if the
56 Ith block contains a definition of VAR. */
57 bitmap def_blocks;
59 /* Blocks that contain a PHI node for VAR. */
60 bitmap phi_blocks;
62 /* Blocks where VAR is live-on-entry. Similar semantics as
63 DEF_BLOCKS. */
64 bitmap livein_blocks;
67 /* Stack of trees used to restore the global currdefs to its original
68 state after completing rewriting of a block and its dominator
69 children. Its elements have the following properties:
71 - An SSA_NAME (N) indicates that the current definition of the
72 underlying variable should be set to the given SSA_NAME. If the
73 symbol associated with the SSA_NAME is not a GIMPLE register, the
74 next slot in the stack must be a _DECL node (SYM). In this case,
75 the name N in the previous slot is the current reaching
76 definition for SYM.
78 - A _DECL node indicates that the underlying variable has no
79 current definition.
81 - A NULL node at the top entry is used to mark the last slot
82 associated with the current block. */
83 static vec<tree> block_defs_stack;
86 /* Set of existing SSA names being replaced by update_ssa. */
87 static sbitmap old_ssa_names;
89 /* Set of new SSA names being added by update_ssa. Note that both
90 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
91 the operations done on them are presence tests. */
92 static sbitmap new_ssa_names;
94 static sbitmap interesting_blocks;
96 /* Set of SSA names that have been marked to be released after they
97 were registered in the replacement table. They will be finally
98 released after we finish updating the SSA web. */
99 bitmap names_to_release;
101 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
102 the to basic block with index I. Allocated once per compilation, *not*
103 released between different functions. */
104 static vec< vec<gphi *> > phis_to_rewrite;
106 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
107 static bitmap blocks_with_phis_to_rewrite;
109 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
110 to grow as the callers to create_new_def_for will create new names on
111 the fly.
112 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
113 need to find a reasonable growth strategy. */
114 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
117 /* The function the SSA updating data structures have been initialized for.
118 NULL if they need to be initialized by create_new_def_for. */
119 static struct function *update_ssa_initialized_fn = NULL;
121 /* Global data to attach to the main dominator walk structure. */
122 struct mark_def_sites_global_data
124 /* This bitmap contains the variables which are set before they
125 are used in a basic block. */
126 bitmap kills;
129 /* It is advantageous to avoid things like life analysis for variables which
130 do not need PHI nodes. This enum describes whether or not a particular
131 variable may need a PHI node. */
133 enum need_phi_state {
134 /* This is the default. If we are still in this state after finding
135 all the definition and use sites, then we will assume the variable
136 needs PHI nodes. This is probably an overly conservative assumption. */
137 NEED_PHI_STATE_UNKNOWN,
139 /* This state indicates that we have seen one or more sets of the
140 variable in a single basic block and that the sets dominate all
141 uses seen so far. If after finding all definition and use sites
142 we are still in this state, then the variable does not need any
143 PHI nodes. */
144 NEED_PHI_STATE_NO,
146 /* This state indicates that we have either seen multiple definitions of
147 the variable in multiple blocks, or that we encountered a use in a
148 block that was not dominated by the block containing the set(s) of
149 this variable. This variable is assumed to need PHI nodes. */
150 NEED_PHI_STATE_MAYBE
153 /* Information stored for both SSA names and decls. */
154 struct common_info
156 /* This field indicates whether or not the variable may need PHI nodes.
157 See the enum's definition for more detailed information about the
158 states. */
159 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
161 /* The current reaching definition replacing this var. */
162 tree current_def;
164 /* Definitions for this var. */
165 struct def_blocks def_blocks;
168 /* Information stored for decls. */
169 struct var_info
171 /* The variable. */
172 tree var;
174 /* Information stored for both SSA names and decls. */
175 common_info info;
179 /* VAR_INFOS hashtable helpers. */
181 struct var_info_hasher : free_ptr_hash <var_info>
183 static inline hashval_t hash (const value_type &);
184 static inline bool equal (const value_type &, const compare_type &);
187 inline hashval_t
188 var_info_hasher::hash (const value_type &p)
190 return DECL_UID (p->var);
193 inline bool
194 var_info_hasher::equal (const value_type &p1, const compare_type &p2)
196 return p1->var == p2->var;
200 /* Each entry in VAR_INFOS contains an element of type STRUCT
201 VAR_INFO_D. */
202 static hash_table<var_info_hasher> *var_infos;
205 /* Information stored for SSA names. */
206 struct ssa_name_info
208 /* Age of this record (so that info_for_ssa_name table can be cleared
209 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
210 are assumed to be null. */
211 unsigned age;
213 /* Replacement mappings, allocated from update_ssa_obstack. */
214 bitmap repl_set;
216 /* Information stored for both SSA names and decls. */
217 common_info info;
220 static vec<ssa_name_info *> info_for_ssa_name;
221 static unsigned current_info_for_ssa_name_age;
223 static bitmap_obstack update_ssa_obstack;
225 /* The set of blocks affected by update_ssa. */
226 static bitmap blocks_to_update;
228 /* The main entry point to the SSA renamer (rewrite_blocks) may be
229 called several times to do different, but related, tasks.
230 Initially, we need it to rename the whole program into SSA form.
231 At other times, we may need it to only rename into SSA newly
232 exposed symbols. Finally, we can also call it to incrementally fix
233 an already built SSA web. */
234 enum rewrite_mode {
235 /* Convert the whole function into SSA form. */
236 REWRITE_ALL,
238 /* Incrementally update the SSA web by replacing existing SSA
239 names with new ones. See update_ssa for details. */
240 REWRITE_UPDATE
243 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
244 static bitmap symbols_to_rename_set;
245 static vec<tree> symbols_to_rename;
247 /* Mark SYM for renaming. */
249 static void
250 mark_for_renaming (tree sym)
252 if (!symbols_to_rename_set)
253 symbols_to_rename_set = BITMAP_ALLOC (NULL);
254 if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
255 symbols_to_rename.safe_push (sym);
258 /* Return true if SYM is marked for renaming. */
260 static bool
261 marked_for_renaming (tree sym)
263 if (!symbols_to_rename_set || sym == NULL_TREE)
264 return false;
265 return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
269 /* Return true if STMT needs to be rewritten. When renaming a subset
270 of the variables, not all statements will be processed. This is
271 decided in mark_def_sites. */
273 static inline bool
274 rewrite_uses_p (gimple *stmt)
276 return gimple_visited_p (stmt);
280 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
282 static inline void
283 set_rewrite_uses (gimple *stmt, bool rewrite_p)
285 gimple_set_visited (stmt, rewrite_p);
289 /* Return true if the DEFs created by statement STMT should be
290 registered when marking new definition sites. This is slightly
291 different than rewrite_uses_p: it's used by update_ssa to
292 distinguish statements that need to have both uses and defs
293 processed from those that only need to have their defs processed.
294 Statements that define new SSA names only need to have their defs
295 registered, but they don't need to have their uses renamed. */
297 static inline bool
298 register_defs_p (gimple *stmt)
300 return gimple_plf (stmt, GF_PLF_1) != 0;
304 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
306 static inline void
307 set_register_defs (gimple *stmt, bool register_defs_p)
309 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
313 /* Get the information associated with NAME. */
315 static inline ssa_name_info *
316 get_ssa_name_ann (tree name)
318 unsigned ver = SSA_NAME_VERSION (name);
319 unsigned len = info_for_ssa_name.length ();
320 struct ssa_name_info *info;
322 /* Re-allocate the vector at most once per update/into-SSA. */
323 if (ver >= len)
324 info_for_ssa_name.safe_grow_cleared (num_ssa_names);
326 /* But allocate infos lazily. */
327 info = info_for_ssa_name[ver];
328 if (!info)
330 info = XCNEW (struct ssa_name_info);
331 info->age = current_info_for_ssa_name_age;
332 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
333 info_for_ssa_name[ver] = info;
336 if (info->age < current_info_for_ssa_name_age)
338 info->age = current_info_for_ssa_name_age;
339 info->repl_set = NULL;
340 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
341 info->info.current_def = NULL_TREE;
342 info->info.def_blocks.def_blocks = NULL;
343 info->info.def_blocks.phi_blocks = NULL;
344 info->info.def_blocks.livein_blocks = NULL;
347 return info;
350 /* Return and allocate the auxiliar information for DECL. */
352 static inline var_info *
353 get_var_info (tree decl)
355 var_info vi;
356 var_info **slot;
357 vi.var = decl;
358 slot = var_infos->find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
359 if (*slot == NULL)
361 var_info *v = XCNEW (var_info);
362 v->var = decl;
363 *slot = v;
364 return v;
366 return *slot;
370 /* Clears info for SSA names. */
372 static void
373 clear_ssa_name_info (void)
375 current_info_for_ssa_name_age++;
377 /* If current_info_for_ssa_name_age wraps we use stale information.
378 Asser that this does not happen. */
379 gcc_assert (current_info_for_ssa_name_age != 0);
383 /* Get access to the auxiliar information stored per SSA name or decl. */
385 static inline common_info *
386 get_common_info (tree var)
388 if (TREE_CODE (var) == SSA_NAME)
389 return &get_ssa_name_ann (var)->info;
390 else
391 return &get_var_info (var)->info;
395 /* Return the current definition for VAR. */
397 tree
398 get_current_def (tree var)
400 return get_common_info (var)->current_def;
404 /* Sets current definition of VAR to DEF. */
406 void
407 set_current_def (tree var, tree def)
409 get_common_info (var)->current_def = def;
412 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
413 all statements in basic block BB. */
415 static void
416 initialize_flags_in_bb (basic_block bb)
418 gimple *stmt;
419 gimple_stmt_iterator gsi;
421 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
423 gimple *phi = gsi_stmt (gsi);
424 set_rewrite_uses (phi, false);
425 set_register_defs (phi, false);
428 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
430 stmt = gsi_stmt (gsi);
432 /* We are going to use the operand cache API, such as
433 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
434 cache for each statement should be up-to-date. */
435 gcc_checking_assert (!gimple_modified_p (stmt));
436 set_rewrite_uses (stmt, false);
437 set_register_defs (stmt, false);
441 /* Mark block BB as interesting for update_ssa. */
443 static void
444 mark_block_for_update (basic_block bb)
446 gcc_checking_assert (blocks_to_update != NULL);
447 if (!bitmap_set_bit (blocks_to_update, bb->index))
448 return;
449 initialize_flags_in_bb (bb);
452 /* Return the set of blocks where variable VAR is defined and the blocks
453 where VAR is live on entry (livein). If no entry is found in
454 DEF_BLOCKS, a new one is created and returned. */
456 static inline def_blocks *
457 get_def_blocks_for (common_info *info)
459 def_blocks *db_p = &info->def_blocks;
460 if (!db_p->def_blocks)
462 db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
463 db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
464 db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
467 return db_p;
471 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
472 VAR is defined by a PHI node. */
474 static void
475 set_def_block (tree var, basic_block bb, bool phi_p)
477 def_blocks *db_p;
478 common_info *info;
480 info = get_common_info (var);
481 db_p = get_def_blocks_for (info);
483 /* Set the bit corresponding to the block where VAR is defined. */
484 bitmap_set_bit (db_p->def_blocks, bb->index);
485 if (phi_p)
486 bitmap_set_bit (db_p->phi_blocks, bb->index);
488 /* Keep track of whether or not we may need to insert PHI nodes.
490 If we are in the UNKNOWN state, then this is the first definition
491 of VAR. Additionally, we have not seen any uses of VAR yet, so
492 we do not need a PHI node for this variable at this time (i.e.,
493 transition to NEED_PHI_STATE_NO).
495 If we are in any other state, then we either have multiple definitions
496 of this variable occurring in different blocks or we saw a use of the
497 variable which was not dominated by the block containing the
498 definition(s). In this case we may need a PHI node, so enter
499 state NEED_PHI_STATE_MAYBE. */
500 if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
501 info->need_phi_state = NEED_PHI_STATE_NO;
502 else
503 info->need_phi_state = NEED_PHI_STATE_MAYBE;
507 /* Mark block BB as having VAR live at the entry to BB. */
509 static void
510 set_livein_block (tree var, basic_block bb)
512 common_info *info;
513 def_blocks *db_p;
515 info = get_common_info (var);
516 db_p = get_def_blocks_for (info);
518 /* Set the bit corresponding to the block where VAR is live in. */
519 bitmap_set_bit (db_p->livein_blocks, bb->index);
521 /* Keep track of whether or not we may need to insert PHI nodes.
523 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
524 by the single block containing the definition(s) of this variable. If
525 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
526 NEED_PHI_STATE_MAYBE. */
527 if (info->need_phi_state == NEED_PHI_STATE_NO)
529 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
531 if (def_block_index == -1
532 || ! dominated_by_p (CDI_DOMINATORS, bb,
533 BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
534 info->need_phi_state = NEED_PHI_STATE_MAYBE;
536 else
537 info->need_phi_state = NEED_PHI_STATE_MAYBE;
541 /* Return true if NAME is in OLD_SSA_NAMES. */
543 static inline bool
544 is_old_name (tree name)
546 unsigned ver = SSA_NAME_VERSION (name);
547 if (!old_ssa_names)
548 return false;
549 return (ver < SBITMAP_SIZE (old_ssa_names)
550 && bitmap_bit_p (old_ssa_names, ver));
554 /* Return true if NAME is in NEW_SSA_NAMES. */
556 static inline bool
557 is_new_name (tree name)
559 unsigned ver = SSA_NAME_VERSION (name);
560 if (!new_ssa_names)
561 return false;
562 return (ver < SBITMAP_SIZE (new_ssa_names)
563 && bitmap_bit_p (new_ssa_names, ver));
567 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
569 static inline bitmap
570 names_replaced_by (tree new_tree)
572 return get_ssa_name_ann (new_tree)->repl_set;
576 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
578 static inline void
579 add_to_repl_tbl (tree new_tree, tree old)
581 bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
582 if (!*set)
583 *set = BITMAP_ALLOC (&update_ssa_obstack);
584 bitmap_set_bit (*set, SSA_NAME_VERSION (old));
588 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
589 represents the set of names O_1 ... O_j replaced by N_i. This is
590 used by update_ssa and its helpers to introduce new SSA names in an
591 already formed SSA web. */
593 static void
594 add_new_name_mapping (tree new_tree, tree old)
596 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
597 gcc_checking_assert (new_tree != old
598 && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
600 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
601 caller may have created new names since the set was created. */
602 if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
604 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
605 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
606 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
609 /* Update the REPL_TBL table. */
610 add_to_repl_tbl (new_tree, old);
612 /* If OLD had already been registered as a new name, then all the
613 names that OLD replaces should also be replaced by NEW_TREE. */
614 if (is_new_name (old))
615 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
617 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
618 respectively. */
619 bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
620 bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
624 /* Call back for walk_dominator_tree used to collect definition sites
625 for every variable in the function. For every statement S in block
628 1- Variables defined by S in the DEFS of S are marked in the bitmap
629 KILLS.
631 2- If S uses a variable VAR and there is no preceding kill of VAR,
632 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
634 This information is used to determine which variables are live
635 across block boundaries to reduce the number of PHI nodes
636 we create. */
638 static void
639 mark_def_sites (basic_block bb, gimple *stmt, bitmap kills)
641 tree def;
642 use_operand_p use_p;
643 ssa_op_iter iter;
645 /* Since this is the first time that we rewrite the program into SSA
646 form, force an operand scan on every statement. */
647 update_stmt (stmt);
649 gcc_checking_assert (blocks_to_update == NULL);
650 set_register_defs (stmt, false);
651 set_rewrite_uses (stmt, false);
653 if (is_gimple_debug (stmt))
655 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
657 tree sym = USE_FROM_PTR (use_p);
658 gcc_checking_assert (DECL_P (sym));
659 set_rewrite_uses (stmt, true);
661 if (rewrite_uses_p (stmt))
662 bitmap_set_bit (interesting_blocks, bb->index);
663 return;
666 /* If a variable is used before being set, then the variable is live
667 across a block boundary, so mark it live-on-entry to BB. */
668 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
670 tree sym = USE_FROM_PTR (use_p);
671 if (TREE_CODE (sym) == SSA_NAME)
672 continue;
673 gcc_checking_assert (DECL_P (sym));
674 if (!bitmap_bit_p (kills, DECL_UID (sym)))
675 set_livein_block (sym, bb);
676 set_rewrite_uses (stmt, true);
679 /* Now process the defs. Mark BB as the definition block and add
680 each def to the set of killed symbols. */
681 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
683 if (TREE_CODE (def) == SSA_NAME)
684 continue;
685 gcc_checking_assert (DECL_P (def));
686 set_def_block (def, bb, false);
687 bitmap_set_bit (kills, DECL_UID (def));
688 set_register_defs (stmt, true);
691 /* If we found the statement interesting then also mark the block BB
692 as interesting. */
693 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
694 bitmap_set_bit (interesting_blocks, bb->index);
697 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
698 in the dfs numbering of the dominance tree. */
700 struct dom_dfsnum
702 /* Basic block whose index this entry corresponds to. */
703 unsigned bb_index;
705 /* The dfs number of this node. */
706 unsigned dfs_num;
709 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
710 for qsort. */
712 static int
713 cmp_dfsnum (const void *a, const void *b)
715 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
716 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
718 return (int) da->dfs_num - (int) db->dfs_num;
721 /* Among the intervals starting at the N points specified in DEFS, find
722 the one that contains S, and return its bb_index. */
724 static unsigned
725 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
727 unsigned f = 0, t = n, m;
729 while (t > f + 1)
731 m = (f + t) / 2;
732 if (defs[m].dfs_num <= s)
733 f = m;
734 else
735 t = m;
738 return defs[f].bb_index;
741 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
742 KILLS is a bitmap of blocks where the value is defined before any use. */
744 static void
745 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
747 bitmap_iterator bi;
748 unsigned i, b, p, u, top;
749 bitmap live_phis;
750 basic_block def_bb, use_bb;
751 edge e;
752 edge_iterator ei;
753 bitmap to_remove;
754 struct dom_dfsnum *defs;
755 unsigned n_defs, adef;
757 if (bitmap_empty_p (uses))
759 bitmap_clear (phis);
760 return;
763 /* The phi must dominate a use, or an argument of a live phi. Also, we
764 do not create any phi nodes in def blocks, unless they are also livein. */
765 to_remove = BITMAP_ALLOC (NULL);
766 bitmap_and_compl (to_remove, kills, uses);
767 bitmap_and_compl_into (phis, to_remove);
768 if (bitmap_empty_p (phis))
770 BITMAP_FREE (to_remove);
771 return;
774 /* We want to remove the unnecessary phi nodes, but we do not want to compute
775 liveness information, as that may be linear in the size of CFG, and if
776 there are lot of different variables to rewrite, this may lead to quadratic
777 behavior.
779 Instead, we basically emulate standard dce. We put all uses to worklist,
780 then for each of them find the nearest def that dominates them. If this
781 def is a phi node, we mark it live, and if it was not live before, we
782 add the predecessors of its basic block to the worklist.
784 To quickly locate the nearest def that dominates use, we use dfs numbering
785 of the dominance tree (that is already available in order to speed up
786 queries). For each def, we have the interval given by the dfs number on
787 entry to and on exit from the corresponding subtree in the dominance tree.
788 The nearest dominator for a given use is the smallest of these intervals
789 that contains entry and exit dfs numbers for the basic block with the use.
790 If we store the bounds for all the uses to an array and sort it, we can
791 locate the nearest dominating def in logarithmic time by binary search.*/
792 bitmap_ior (to_remove, kills, phis);
793 n_defs = bitmap_count_bits (to_remove);
794 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
795 defs[0].bb_index = 1;
796 defs[0].dfs_num = 0;
797 adef = 1;
798 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
800 def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
801 defs[adef].bb_index = i;
802 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
803 defs[adef + 1].bb_index = i;
804 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
805 adef += 2;
807 BITMAP_FREE (to_remove);
808 gcc_assert (adef == 2 * n_defs + 1);
809 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
810 gcc_assert (defs[0].bb_index == 1);
812 /* Now each DEFS entry contains the number of the basic block to that the
813 dfs number corresponds. Change them to the number of basic block that
814 corresponds to the interval following the dfs number. Also, for the
815 dfs_out numbers, increase the dfs number by one (so that it corresponds
816 to the start of the following interval, not to the end of the current
817 one). We use WORKLIST as a stack. */
818 auto_vec<int> worklist (n_defs + 1);
819 worklist.quick_push (1);
820 top = 1;
821 n_defs = 1;
822 for (i = 1; i < adef; i++)
824 b = defs[i].bb_index;
825 if (b == top)
827 /* This is a closing element. Interval corresponding to the top
828 of the stack after removing it follows. */
829 worklist.pop ();
830 top = worklist[worklist.length () - 1];
831 defs[n_defs].bb_index = top;
832 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
834 else
836 /* Opening element. Nothing to do, just push it to the stack and move
837 it to the correct position. */
838 defs[n_defs].bb_index = defs[i].bb_index;
839 defs[n_defs].dfs_num = defs[i].dfs_num;
840 worklist.quick_push (b);
841 top = b;
844 /* If this interval starts at the same point as the previous one, cancel
845 the previous one. */
846 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
847 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
848 else
849 n_defs++;
851 worklist.pop ();
852 gcc_assert (worklist.is_empty ());
854 /* Now process the uses. */
855 live_phis = BITMAP_ALLOC (NULL);
856 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
858 worklist.safe_push (i);
861 while (!worklist.is_empty ())
863 b = worklist.pop ();
864 if (b == ENTRY_BLOCK)
865 continue;
867 /* If there is a phi node in USE_BB, it is made live. Otherwise,
868 find the def that dominates the immediate dominator of USE_BB
869 (the kill in USE_BB does not dominate the use). */
870 if (bitmap_bit_p (phis, b))
871 p = b;
872 else
874 use_bb = get_immediate_dominator (CDI_DOMINATORS,
875 BASIC_BLOCK_FOR_FN (cfun, b));
876 p = find_dfsnum_interval (defs, n_defs,
877 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
878 if (!bitmap_bit_p (phis, p))
879 continue;
882 /* If the phi node is already live, there is nothing to do. */
883 if (!bitmap_set_bit (live_phis, p))
884 continue;
886 /* Add the new uses to the worklist. */
887 def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
888 FOR_EACH_EDGE (e, ei, def_bb->preds)
890 u = e->src->index;
891 if (bitmap_bit_p (uses, u))
892 continue;
894 /* In case there is a kill directly in the use block, do not record
895 the use (this is also necessary for correctness, as we assume that
896 uses dominated by a def directly in their block have been filtered
897 out before). */
898 if (bitmap_bit_p (kills, u))
899 continue;
901 bitmap_set_bit (uses, u);
902 worklist.safe_push (u);
906 bitmap_copy (phis, live_phis);
907 BITMAP_FREE (live_phis);
908 free (defs);
911 /* Return the set of blocks where variable VAR is defined and the blocks
912 where VAR is live on entry (livein). Return NULL, if no entry is
913 found in DEF_BLOCKS. */
915 static inline def_blocks *
916 find_def_blocks_for (tree var)
918 def_blocks *p = &get_common_info (var)->def_blocks;
919 if (!p->def_blocks)
920 return NULL;
921 return p;
925 /* Marks phi node PHI in basic block BB for rewrite. */
927 static void
928 mark_phi_for_rewrite (basic_block bb, gphi *phi)
930 vec<gphi *> phis;
931 unsigned n, idx = bb->index;
933 if (rewrite_uses_p (phi))
934 return;
936 set_rewrite_uses (phi, true);
938 if (!blocks_with_phis_to_rewrite)
939 return;
941 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
943 n = (unsigned) last_basic_block_for_fn (cfun) + 1;
944 if (phis_to_rewrite.length () < n)
945 phis_to_rewrite.safe_grow_cleared (n);
947 phis = phis_to_rewrite[idx];
948 phis.reserve (10);
950 phis.safe_push (phi);
951 phis_to_rewrite[idx] = phis;
954 /* Insert PHI nodes for variable VAR using the iterated dominance
955 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
956 function assumes that the caller is incrementally updating the
957 existing SSA form, in which case VAR may be an SSA name instead of
958 a symbol.
960 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
961 PHI node for VAR. On exit, only the nodes that received a PHI node
962 for VAR will be present in PHI_INSERTION_POINTS. */
964 static void
965 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
967 unsigned bb_index;
968 edge e;
969 gphi *phi;
970 basic_block bb;
971 bitmap_iterator bi;
972 def_blocks *def_map = find_def_blocks_for (var);
974 /* Remove the blocks where we already have PHI nodes for VAR. */
975 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
977 /* Remove obviously useless phi nodes. */
978 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
979 def_map->livein_blocks);
981 /* And insert the PHI nodes. */
982 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
984 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
985 if (update_p)
986 mark_block_for_update (bb);
988 if (dump_file && (dump_flags & TDF_DETAILS))
990 fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
991 print_generic_expr (dump_file, var, TDF_SLIM);
992 fprintf (dump_file, "\n");
994 phi = NULL;
996 if (TREE_CODE (var) == SSA_NAME)
998 /* If we are rewriting SSA names, create the LHS of the PHI
999 node by duplicating VAR. This is useful in the case of
1000 pointers, to also duplicate pointer attributes (alias
1001 information, in particular). */
1002 edge_iterator ei;
1003 tree new_lhs;
1005 gcc_checking_assert (update_p);
1006 new_lhs = duplicate_ssa_name (var, NULL);
1007 phi = create_phi_node (new_lhs, bb);
1008 add_new_name_mapping (new_lhs, var);
1010 /* Add VAR to every argument slot of PHI. We need VAR in
1011 every argument so that rewrite_update_phi_arguments knows
1012 which name is this PHI node replacing. If VAR is a
1013 symbol marked for renaming, this is not necessary, the
1014 renamer will use the symbol on the LHS to get its
1015 reaching definition. */
1016 FOR_EACH_EDGE (e, ei, bb->preds)
1017 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1019 else
1021 tree tracked_var;
1023 gcc_checking_assert (DECL_P (var));
1024 phi = create_phi_node (var, bb);
1026 tracked_var = target_for_debug_bind (var);
1027 if (tracked_var)
1029 gimple *note = gimple_build_debug_bind (tracked_var,
1030 PHI_RESULT (phi),
1031 phi);
1032 gimple_stmt_iterator si = gsi_after_labels (bb);
1033 gsi_insert_before (&si, note, GSI_SAME_STMT);
1037 /* Mark this PHI node as interesting for update_ssa. */
1038 set_register_defs (phi, true);
1039 mark_phi_for_rewrite (bb, phi);
1043 /* Sort var_infos after DECL_UID of their var. */
1045 static int
1046 insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1048 const var_info *defa = *(var_info * const *)a;
1049 const var_info *defb = *(var_info * const *)b;
1050 if (DECL_UID (defa->var) < DECL_UID (defb->var))
1051 return -1;
1052 else
1053 return 1;
1056 /* Insert PHI nodes at the dominance frontier of blocks with variable
1057 definitions. DFS contains the dominance frontier information for
1058 the flowgraph. */
1060 static void
1061 insert_phi_nodes (bitmap_head *dfs)
1063 hash_table<var_info_hasher>::iterator hi;
1064 unsigned i;
1065 var_info *info;
1067 timevar_push (TV_TREE_INSERT_PHI_NODES);
1069 /* When the gimplifier introduces SSA names it cannot easily avoid
1070 situations where abnormal edges added by CFG construction break
1071 the use-def dominance requirement. For this case rewrite SSA
1072 names with broken use-def dominance out-of-SSA and register them
1073 for PHI insertion. We only need to do this if abnormal edges
1074 can appear in the function. */
1075 tree name;
1076 if (cfun->calls_setjmp
1077 || cfun->has_nonlocal_label)
1078 FOR_EACH_SSA_NAME (i, name, cfun)
1080 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1081 if (SSA_NAME_IS_DEFAULT_DEF (name))
1082 continue;
1084 basic_block def_bb = gimple_bb (def_stmt);
1085 imm_use_iterator it;
1086 gimple *use_stmt;
1087 bool need_phis = false;
1088 FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1090 basic_block use_bb = gimple_bb (use_stmt);
1091 if (use_bb != def_bb
1092 && ! dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
1093 need_phis = true;
1095 if (need_phis)
1097 tree var = create_tmp_reg (TREE_TYPE (name));
1098 use_operand_p use_p;
1099 FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1101 basic_block use_bb = gimple_bb (use_stmt);
1102 FOR_EACH_IMM_USE_ON_STMT (use_p, it)
1103 SET_USE (use_p, var);
1104 update_stmt (use_stmt);
1105 set_livein_block (var, use_bb);
1106 set_rewrite_uses (use_stmt, true);
1107 bitmap_set_bit (interesting_blocks, use_bb->index);
1109 def_operand_p def_p;
1110 ssa_op_iter dit;
1111 FOR_EACH_SSA_DEF_OPERAND (def_p, def_stmt, dit, SSA_OP_DEF)
1112 if (DEF_FROM_PTR (def_p) == name)
1113 SET_DEF (def_p, var);
1114 update_stmt (def_stmt);
1115 set_def_block (var, def_bb, false);
1116 set_register_defs (def_stmt, true);
1117 bitmap_set_bit (interesting_blocks, def_bb->index);
1118 release_ssa_name (name);
1122 auto_vec<var_info *> vars (var_infos->elements ());
1123 FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
1124 if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1125 vars.quick_push (info);
1127 /* Do two stages to avoid code generation differences for UID
1128 differences but no UID ordering differences. */
1129 vars.qsort (insert_phi_nodes_compare_var_infos);
1131 FOR_EACH_VEC_ELT (vars, i, info)
1133 bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1134 insert_phi_nodes_for (info->var, idf, false);
1135 BITMAP_FREE (idf);
1138 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1142 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1143 register DEF (an SSA_NAME) to be a new definition for SYM. */
1145 static void
1146 register_new_def (tree def, tree sym)
1148 common_info *info = get_common_info (sym);
1149 tree currdef;
1151 /* If this variable is set in a single basic block and all uses are
1152 dominated by the set(s) in that single basic block, then there is
1153 no reason to record anything for this variable in the block local
1154 definition stacks. Doing so just wastes time and memory.
1156 This is the same test to prune the set of variables which may
1157 need PHI nodes. So we just use that information since it's already
1158 computed and available for us to use. */
1159 if (info->need_phi_state == NEED_PHI_STATE_NO)
1161 info->current_def = def;
1162 return;
1165 currdef = info->current_def;
1167 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1168 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1169 in the stack so that we know which symbol is being defined by
1170 this SSA name when we unwind the stack. */
1171 if (currdef && !is_gimple_reg (sym))
1172 block_defs_stack.safe_push (sym);
1174 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1175 stack is later used by the dominator tree callbacks to restore
1176 the reaching definitions for all the variables defined in the
1177 block after a recursive visit to all its immediately dominated
1178 blocks. If there is no current reaching definition, then just
1179 record the underlying _DECL node. */
1180 block_defs_stack.safe_push (currdef ? currdef : sym);
1182 /* Set the current reaching definition for SYM to be DEF. */
1183 info->current_def = def;
1187 /* Perform a depth-first traversal of the dominator tree looking for
1188 variables to rename. BB is the block where to start searching.
1189 Renaming is a five step process:
1191 1- Every definition made by PHI nodes at the start of the blocks is
1192 registered as the current definition for the corresponding variable.
1194 2- Every statement in BB is rewritten. USE and VUSE operands are
1195 rewritten with their corresponding reaching definition. DEF and
1196 VDEF targets are registered as new definitions.
1198 3- All the PHI nodes in successor blocks of BB are visited. The
1199 argument corresponding to BB is replaced with its current reaching
1200 definition.
1202 4- Recursively rewrite every dominator child block of BB.
1204 5- Restore (in reverse order) the current reaching definition for every
1205 new definition introduced in this block. This is done so that when
1206 we return from the recursive call, all the current reaching
1207 definitions are restored to the names that were valid in the
1208 dominator parent of BB. */
1210 /* Return the current definition for variable VAR. If none is found,
1211 create a new SSA name to act as the zeroth definition for VAR. */
1213 static tree
1214 get_reaching_def (tree var)
1216 common_info *info = get_common_info (var);
1217 tree currdef;
1219 /* Lookup the current reaching definition for VAR. */
1220 currdef = info->current_def;
1222 /* If there is no reaching definition for VAR, create and register a
1223 default definition for it (if needed). */
1224 if (currdef == NULL_TREE)
1226 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1227 currdef = get_or_create_ssa_default_def (cfun, sym);
1230 /* Return the current reaching definition for VAR, or the default
1231 definition, if we had to create one. */
1232 return currdef;
1236 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1238 static void
1239 rewrite_debug_stmt_uses (gimple *stmt)
1241 use_operand_p use_p;
1242 ssa_op_iter iter;
1243 bool update = false;
1245 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1247 tree var = USE_FROM_PTR (use_p), def;
1248 common_info *info = get_common_info (var);
1249 gcc_checking_assert (DECL_P (var));
1250 def = info->current_def;
1251 if (!def)
1253 if (TREE_CODE (var) == PARM_DECL
1254 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
1256 gimple_stmt_iterator gsi
1258 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1259 int lim;
1260 /* Search a few source bind stmts at the start of first bb to
1261 see if a DEBUG_EXPR_DECL can't be reused. */
1262 for (lim = 32;
1263 !gsi_end_p (gsi) && lim > 0;
1264 gsi_next (&gsi), lim--)
1266 gimple *gstmt = gsi_stmt (gsi);
1267 if (!gimple_debug_source_bind_p (gstmt))
1268 break;
1269 if (gimple_debug_source_bind_get_value (gstmt) == var)
1271 def = gimple_debug_source_bind_get_var (gstmt);
1272 if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1273 break;
1274 else
1275 def = NULL_TREE;
1278 /* If not, add a new source bind stmt. */
1279 if (def == NULL_TREE)
1281 gimple *def_temp;
1282 def = make_node (DEBUG_EXPR_DECL);
1283 def_temp = gimple_build_debug_source_bind (def, var, NULL);
1284 DECL_ARTIFICIAL (def) = 1;
1285 TREE_TYPE (def) = TREE_TYPE (var);
1286 SET_DECL_MODE (def, DECL_MODE (var));
1287 gsi =
1288 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1289 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1291 update = true;
1294 else
1296 /* Check if info->current_def can be trusted. */
1297 basic_block bb = gimple_bb (stmt);
1298 basic_block def_bb
1299 = SSA_NAME_IS_DEFAULT_DEF (def)
1300 ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1302 /* If definition is in current bb, it is fine. */
1303 if (bb == def_bb)
1305 /* If definition bb doesn't dominate the current bb,
1306 it can't be used. */
1307 else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1308 def = NULL;
1309 /* If there is just one definition and dominates the current
1310 bb, it is fine. */
1311 else if (info->need_phi_state == NEED_PHI_STATE_NO)
1313 else
1315 def_blocks *db_p = get_def_blocks_for (info);
1317 /* If there are some non-debug uses in the current bb,
1318 it is fine. */
1319 if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1321 /* Otherwise give up for now. */
1322 else
1323 def = NULL;
1326 if (def == NULL)
1328 gimple_debug_bind_reset_value (stmt);
1329 update_stmt (stmt);
1330 return;
1332 SET_USE (use_p, def);
1334 if (update)
1335 update_stmt (stmt);
1338 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1339 the block with its immediate reaching definitions. Update the current
1340 definition of a variable when a new real or virtual definition is found. */
1342 static void
1343 rewrite_stmt (gimple_stmt_iterator *si)
1345 use_operand_p use_p;
1346 def_operand_p def_p;
1347 ssa_op_iter iter;
1348 gimple *stmt = gsi_stmt (*si);
1350 /* If mark_def_sites decided that we don't need to rewrite this
1351 statement, ignore it. */
1352 gcc_assert (blocks_to_update == NULL);
1353 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1354 return;
1356 if (dump_file && (dump_flags & TDF_DETAILS))
1358 fprintf (dump_file, "Renaming statement ");
1359 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1360 fprintf (dump_file, "\n");
1363 /* Step 1. Rewrite USES in the statement. */
1364 if (rewrite_uses_p (stmt))
1366 if (is_gimple_debug (stmt))
1367 rewrite_debug_stmt_uses (stmt);
1368 else
1369 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1371 tree var = USE_FROM_PTR (use_p);
1372 if (TREE_CODE (var) == SSA_NAME)
1373 continue;
1374 gcc_checking_assert (DECL_P (var));
1375 SET_USE (use_p, get_reaching_def (var));
1379 /* Step 2. Register the statement's DEF operands. */
1380 if (register_defs_p (stmt))
1381 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1383 tree var = DEF_FROM_PTR (def_p);
1384 tree name;
1385 tree tracked_var;
1387 if (TREE_CODE (var) == SSA_NAME)
1388 continue;
1389 gcc_checking_assert (DECL_P (var));
1391 if (gimple_clobber_p (stmt)
1392 && is_gimple_reg (var))
1394 /* If we rewrite a DECL into SSA form then drop its
1395 clobber stmts and replace uses with a new default def. */
1396 gcc_checking_assert (VAR_P (var) && !gimple_vdef (stmt));
1397 gsi_replace (si, gimple_build_nop (), true);
1398 register_new_def (get_or_create_ssa_default_def (cfun, var), var);
1399 break;
1402 name = make_ssa_name (var, stmt);
1403 SET_DEF (def_p, name);
1404 register_new_def (DEF_FROM_PTR (def_p), var);
1406 tracked_var = target_for_debug_bind (var);
1407 if (tracked_var)
1409 gimple *note = gimple_build_debug_bind (tracked_var, name, stmt);
1410 gsi_insert_after (si, note, GSI_SAME_STMT);
1416 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1417 PHI nodes. For every PHI node found, add a new argument containing the
1418 current reaching definition for the variable and the edge through which
1419 that definition is reaching the PHI node. */
1421 static void
1422 rewrite_add_phi_arguments (basic_block bb)
1424 edge e;
1425 edge_iterator ei;
1427 FOR_EACH_EDGE (e, ei, bb->succs)
1429 gphi *phi;
1430 gphi_iterator gsi;
1432 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1433 gsi_next (&gsi))
1435 tree currdef, res, argvar;
1436 location_t loc;
1438 phi = gsi.phi ();
1439 res = gimple_phi_result (phi);
1440 /* If we have pre-existing PHI (via the GIMPLE FE) its args may
1441 be different vars than existing vars and they may be constants
1442 as well. Note the following supports partial SSA for PHI args. */
1443 argvar = gimple_phi_arg_def (phi, e->dest_idx);
1444 if (argvar && ! DECL_P (argvar))
1445 continue;
1446 if (!argvar)
1447 argvar = SSA_NAME_VAR (res);
1448 currdef = get_reaching_def (argvar);
1449 /* Virtual operand PHI args do not need a location. */
1450 if (virtual_operand_p (res))
1451 loc = UNKNOWN_LOCATION;
1452 else
1453 loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1454 add_phi_arg (phi, currdef, e, loc);
1459 class rewrite_dom_walker : public dom_walker
1461 public:
1462 rewrite_dom_walker (cdi_direction direction) : dom_walker (direction) {}
1464 virtual edge before_dom_children (basic_block);
1465 virtual void after_dom_children (basic_block);
1468 /* SSA Rewriting Step 1. Initialization, create a block local stack
1469 of reaching definitions for new SSA names produced in this block
1470 (BLOCK_DEFS). Register new definitions for every PHI node in the
1471 block. */
1473 edge
1474 rewrite_dom_walker::before_dom_children (basic_block bb)
1476 if (dump_file && (dump_flags & TDF_DETAILS))
1477 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1479 /* Mark the unwind point for this block. */
1480 block_defs_stack.safe_push (NULL_TREE);
1482 /* Step 1. Register new definitions for every PHI node in the block.
1483 Conceptually, all the PHI nodes are executed in parallel and each PHI
1484 node introduces a new version for the associated variable. */
1485 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1486 gsi_next (&gsi))
1488 tree result = gimple_phi_result (gsi_stmt (gsi));
1489 register_new_def (result, SSA_NAME_VAR (result));
1492 /* Step 2. Rewrite every variable used in each statement in the block
1493 with its immediate reaching definitions. Update the current definition
1494 of a variable when a new real or virtual definition is found. */
1495 if (bitmap_bit_p (interesting_blocks, bb->index))
1496 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1497 gsi_next (&gsi))
1498 rewrite_stmt (&gsi);
1500 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1501 For every PHI node found, add a new argument containing the current
1502 reaching definition for the variable and the edge through which that
1503 definition is reaching the PHI node. */
1504 rewrite_add_phi_arguments (bb);
1506 return NULL;
1511 /* Called after visiting all the statements in basic block BB and all
1512 of its dominator children. Restore CURRDEFS to its original value. */
1514 void
1515 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1517 /* Restore CURRDEFS to its original state. */
1518 while (block_defs_stack.length () > 0)
1520 tree tmp = block_defs_stack.pop ();
1521 tree saved_def, var;
1523 if (tmp == NULL_TREE)
1524 break;
1526 if (TREE_CODE (tmp) == SSA_NAME)
1528 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1529 current definition of its underlying variable. Note that
1530 if the SSA_NAME is not for a GIMPLE register, the symbol
1531 being defined is stored in the next slot in the stack.
1532 This mechanism is needed because an SSA name for a
1533 non-register symbol may be the definition for more than
1534 one symbol (e.g., SFTs, aliased variables, etc). */
1535 saved_def = tmp;
1536 var = SSA_NAME_VAR (saved_def);
1537 if (!is_gimple_reg (var))
1538 var = block_defs_stack.pop ();
1540 else
1542 /* If we recorded anything else, it must have been a _DECL
1543 node and its current reaching definition must have been
1544 NULL. */
1545 saved_def = NULL;
1546 var = tmp;
1549 get_common_info (var)->current_def = saved_def;
1554 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1556 DEBUG_FUNCTION void
1557 debug_decl_set (bitmap set)
1559 dump_decl_set (stderr, set);
1560 fprintf (stderr, "\n");
1564 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1565 stack up to a maximum of N levels. If N is -1, the whole stack is
1566 dumped. New levels are created when the dominator tree traversal
1567 used for renaming enters a new sub-tree. */
1569 void
1570 dump_defs_stack (FILE *file, int n)
1572 int i, j;
1574 fprintf (file, "\n\nRenaming stack");
1575 if (n > 0)
1576 fprintf (file, " (up to %d levels)", n);
1577 fprintf (file, "\n\n");
1579 i = 1;
1580 fprintf (file, "Level %d (current level)\n", i);
1581 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1583 tree name, var;
1585 name = block_defs_stack[j];
1586 if (name == NULL_TREE)
1588 i++;
1589 if (n > 0 && i > n)
1590 break;
1591 fprintf (file, "\nLevel %d\n", i);
1592 continue;
1595 if (DECL_P (name))
1597 var = name;
1598 name = NULL_TREE;
1600 else
1602 var = SSA_NAME_VAR (name);
1603 if (!is_gimple_reg (var))
1605 j--;
1606 var = block_defs_stack[j];
1610 fprintf (file, " Previous CURRDEF (");
1611 print_generic_expr (file, var);
1612 fprintf (file, ") = ");
1613 if (name)
1614 print_generic_expr (file, name);
1615 else
1616 fprintf (file, "<NIL>");
1617 fprintf (file, "\n");
1622 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1623 stack up to a maximum of N levels. If N is -1, the whole stack is
1624 dumped. New levels are created when the dominator tree traversal
1625 used for renaming enters a new sub-tree. */
1627 DEBUG_FUNCTION void
1628 debug_defs_stack (int n)
1630 dump_defs_stack (stderr, n);
1634 /* Dump the current reaching definition of every symbol to FILE. */
1636 void
1637 dump_currdefs (FILE *file)
1639 unsigned i;
1640 tree var;
1642 if (symbols_to_rename.is_empty ())
1643 return;
1645 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1646 FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1648 common_info *info = get_common_info (var);
1649 fprintf (file, "CURRDEF (");
1650 print_generic_expr (file, var);
1651 fprintf (file, ") = ");
1652 if (info->current_def)
1653 print_generic_expr (file, info->current_def);
1654 else
1655 fprintf (file, "<NIL>");
1656 fprintf (file, "\n");
1661 /* Dump the current reaching definition of every symbol to stderr. */
1663 DEBUG_FUNCTION void
1664 debug_currdefs (void)
1666 dump_currdefs (stderr);
1670 /* Dump SSA information to FILE. */
1672 void
1673 dump_tree_ssa (FILE *file)
1675 const char *funcname
1676 = lang_hooks.decl_printable_name (current_function_decl, 2);
1678 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1680 dump_var_infos (file);
1681 dump_defs_stack (file, -1);
1682 dump_currdefs (file);
1683 dump_tree_ssa_stats (file);
1687 /* Dump SSA information to stderr. */
1689 DEBUG_FUNCTION void
1690 debug_tree_ssa (void)
1692 dump_tree_ssa (stderr);
1696 /* Dump statistics for the hash table HTAB. */
1698 static void
1699 htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
1701 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1702 (long) htab.size (),
1703 (long) htab.elements (),
1704 htab.collisions ());
1708 /* Dump SSA statistics on FILE. */
1710 void
1711 dump_tree_ssa_stats (FILE *file)
1713 if (var_infos)
1715 fprintf (file, "\nHash table statistics:\n");
1716 fprintf (file, " var_infos: ");
1717 htab_statistics (file, *var_infos);
1718 fprintf (file, "\n");
1723 /* Dump SSA statistics on stderr. */
1725 DEBUG_FUNCTION void
1726 debug_tree_ssa_stats (void)
1728 dump_tree_ssa_stats (stderr);
1732 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1735 debug_var_infos_r (var_info **slot, FILE *file)
1737 var_info *info = *slot;
1739 fprintf (file, "VAR: ");
1740 print_generic_expr (file, info->var, dump_flags);
1741 bitmap_print (file, info->info.def_blocks.def_blocks,
1742 ", DEF_BLOCKS: { ", "}");
1743 bitmap_print (file, info->info.def_blocks.livein_blocks,
1744 ", LIVEIN_BLOCKS: { ", "}");
1745 bitmap_print (file, info->info.def_blocks.phi_blocks,
1746 ", PHI_BLOCKS: { ", "}\n");
1748 return 1;
1752 /* Dump the VAR_INFOS hash table on FILE. */
1754 void
1755 dump_var_infos (FILE *file)
1757 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1758 if (var_infos)
1759 var_infos->traverse <FILE *, debug_var_infos_r> (file);
1763 /* Dump the VAR_INFOS hash table on stderr. */
1765 DEBUG_FUNCTION void
1766 debug_var_infos (void)
1768 dump_var_infos (stderr);
1772 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1774 static inline void
1775 register_new_update_single (tree new_name, tree old_name)
1777 common_info *info = get_common_info (old_name);
1778 tree currdef = info->current_def;
1780 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1781 This stack is later used by the dominator tree callbacks to
1782 restore the reaching definitions for all the variables
1783 defined in the block after a recursive visit to all its
1784 immediately dominated blocks. */
1785 block_defs_stack.reserve (2);
1786 block_defs_stack.quick_push (currdef);
1787 block_defs_stack.quick_push (old_name);
1789 /* Set the current reaching definition for OLD_NAME to be
1790 NEW_NAME. */
1791 info->current_def = new_name;
1795 /* Register NEW_NAME to be the new reaching definition for all the
1796 names in OLD_NAMES. Used by the incremental SSA update routines to
1797 replace old SSA names with new ones. */
1799 static inline void
1800 register_new_update_set (tree new_name, bitmap old_names)
1802 bitmap_iterator bi;
1803 unsigned i;
1805 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1806 register_new_update_single (new_name, ssa_name (i));
1811 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1812 it is a symbol marked for renaming, replace it with USE_P's current
1813 reaching definition. */
1815 static inline void
1816 maybe_replace_use (use_operand_p use_p)
1818 tree rdef = NULL_TREE;
1819 tree use = USE_FROM_PTR (use_p);
1820 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1822 if (marked_for_renaming (sym))
1823 rdef = get_reaching_def (sym);
1824 else if (is_old_name (use))
1825 rdef = get_reaching_def (use);
1827 if (rdef && rdef != use)
1828 SET_USE (use_p, rdef);
1832 /* Same as maybe_replace_use, but without introducing default stmts,
1833 returning false to indicate a need to do so. */
1835 static inline bool
1836 maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1838 tree rdef = NULL_TREE;
1839 tree use = USE_FROM_PTR (use_p);
1840 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1842 if (marked_for_renaming (sym))
1843 rdef = get_var_info (sym)->info.current_def;
1844 else if (is_old_name (use))
1846 rdef = get_ssa_name_ann (use)->info.current_def;
1847 /* We can't assume that, if there's no current definition, the
1848 default one should be used. It could be the case that we've
1849 rearranged blocks so that the earlier definition no longer
1850 dominates the use. */
1851 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1852 rdef = use;
1854 else
1855 rdef = use;
1857 if (rdef && rdef != use)
1858 SET_USE (use_p, rdef);
1860 return rdef != NULL_TREE;
1864 /* If DEF has x_5 = ASAN_POISON () as its current def, add
1865 ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1866 a poisoned (out of scope) variable. */
1868 static void
1869 maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
1871 tree cdef = get_current_def (def);
1872 if (cdef != NULL
1873 && TREE_CODE (cdef) == SSA_NAME
1874 && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), IFN_ASAN_POISON))
1876 gcall *call
1877 = gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
1878 gimple_set_location (call, gimple_location (gsi_stmt (*gsi)));
1879 gsi_insert_before (gsi, call, GSI_SAME_STMT);
1884 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1885 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1886 register it as the current definition for the names replaced by
1887 DEF_P. Returns whether the statement should be removed. */
1889 static inline bool
1890 maybe_register_def (def_operand_p def_p, gimple *stmt,
1891 gimple_stmt_iterator gsi)
1893 tree def = DEF_FROM_PTR (def_p);
1894 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1895 bool to_delete = false;
1897 /* If DEF is a naked symbol that needs renaming, create a new
1898 name for it. */
1899 if (marked_for_renaming (sym))
1901 if (DECL_P (def))
1903 if (gimple_clobber_p (stmt) && is_gimple_reg (sym))
1905 gcc_checking_assert (VAR_P (sym));
1906 /* Replace clobber stmts with a default def. This new use of a
1907 default definition may make it look like SSA_NAMEs have
1908 conflicting lifetimes, so we need special code to let them
1909 coalesce properly. */
1910 to_delete = true;
1911 def = get_or_create_ssa_default_def (cfun, sym);
1913 else
1915 if (asan_sanitize_use_after_scope ())
1916 maybe_add_asan_poison_write (def, &gsi);
1917 def = make_ssa_name (def, stmt);
1919 SET_DEF (def_p, def);
1921 tree tracked_var = target_for_debug_bind (sym);
1922 if (tracked_var)
1924 gimple *note = gimple_build_debug_bind (tracked_var, def, stmt);
1925 /* If stmt ends the bb, insert the debug stmt on the single
1926 non-EH edge from the stmt. */
1927 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1929 basic_block bb = gsi_bb (gsi);
1930 edge_iterator ei;
1931 edge e, ef = NULL;
1932 FOR_EACH_EDGE (e, ei, bb->succs)
1933 if (!(e->flags & EDGE_EH))
1935 gcc_checking_assert (!ef);
1936 ef = e;
1938 /* If there are other predecessors to ef->dest, then
1939 there must be PHI nodes for the modified
1940 variable, and therefore there will be debug bind
1941 stmts after the PHI nodes. The debug bind notes
1942 we'd insert would force the creation of a new
1943 block (diverging codegen) and be redundant with
1944 the post-PHI bind stmts, so don't add them.
1946 As for the exit edge, there wouldn't be redundant
1947 bind stmts, but there wouldn't be a PC to bind
1948 them to either, so avoid diverging the CFG. */
1949 if (ef && single_pred_p (ef->dest)
1950 && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1952 /* If there were PHI nodes in the node, we'd
1953 have to make sure the value we're binding
1954 doesn't need rewriting. But there shouldn't
1955 be PHI nodes in a single-predecessor block,
1956 so we just add the note. */
1957 gsi_insert_on_edge_immediate (ef, note);
1960 else
1961 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1965 register_new_update_single (def, sym);
1967 else
1969 /* If DEF is a new name, register it as a new definition
1970 for all the names replaced by DEF. */
1971 if (is_new_name (def))
1972 register_new_update_set (def, names_replaced_by (def));
1974 /* If DEF is an old name, register DEF as a new
1975 definition for itself. */
1976 if (is_old_name (def))
1977 register_new_update_single (def, def);
1980 return to_delete;
1984 /* Update every variable used in the statement pointed-to by SI. The
1985 statement is assumed to be in SSA form already. Names in
1986 OLD_SSA_NAMES used by SI will be updated to their current reaching
1987 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1988 will be registered as a new definition for their corresponding name
1989 in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1991 static bool
1992 rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
1994 use_operand_p use_p;
1995 def_operand_p def_p;
1996 ssa_op_iter iter;
1998 /* Only update marked statements. */
1999 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
2000 return false;
2002 if (dump_file && (dump_flags & TDF_DETAILS))
2004 fprintf (dump_file, "Updating SSA information for statement ");
2005 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2008 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2009 symbol is marked for renaming. */
2010 if (rewrite_uses_p (stmt))
2012 if (is_gimple_debug (stmt))
2014 bool failed = false;
2016 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2017 if (!maybe_replace_use_in_debug_stmt (use_p))
2019 failed = true;
2020 break;
2023 if (failed)
2025 /* DOM sometimes threads jumps in such a way that a
2026 debug stmt ends up referencing a SSA variable that no
2027 longer dominates the debug stmt, but such that all
2028 incoming definitions refer to the same definition in
2029 an earlier dominator. We could try to recover that
2030 definition somehow, but this will have to do for now.
2032 Introducing a default definition, which is what
2033 maybe_replace_use() would do in such cases, may
2034 modify code generation, for the otherwise-unused
2035 default definition would never go away, modifying SSA
2036 version numbers all over. */
2037 gimple_debug_bind_reset_value (stmt);
2038 update_stmt (stmt);
2041 else
2043 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2044 maybe_replace_use (use_p);
2048 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2049 Also register definitions for names whose underlying symbol is
2050 marked for renaming. */
2051 bool to_delete = false;
2052 if (register_defs_p (stmt))
2053 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2054 to_delete |= maybe_register_def (def_p, stmt, gsi);
2056 return to_delete;
2060 /* Visit all the successor blocks of BB looking for PHI nodes. For
2061 every PHI node found, check if any of its arguments is in
2062 OLD_SSA_NAMES. If so, and if the argument has a current reaching
2063 definition, replace it. */
2065 static void
2066 rewrite_update_phi_arguments (basic_block bb)
2068 edge e;
2069 edge_iterator ei;
2070 unsigned i;
2072 FOR_EACH_EDGE (e, ei, bb->succs)
2074 gphi *phi;
2075 vec<gphi *> phis;
2077 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2078 continue;
2080 phis = phis_to_rewrite[e->dest->index];
2081 FOR_EACH_VEC_ELT (phis, i, phi)
2083 tree arg, lhs_sym, reaching_def = NULL;
2084 use_operand_p arg_p;
2086 gcc_checking_assert (rewrite_uses_p (phi));
2088 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2089 arg = USE_FROM_PTR (arg_p);
2091 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2092 continue;
2094 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2096 if (arg == NULL_TREE)
2098 /* When updating a PHI node for a recently introduced
2099 symbol we may find NULL arguments. That's why we
2100 take the symbol from the LHS of the PHI node. */
2101 reaching_def = get_reaching_def (lhs_sym);
2104 else
2106 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2108 if (marked_for_renaming (sym))
2109 reaching_def = get_reaching_def (sym);
2110 else if (is_old_name (arg))
2111 reaching_def = get_reaching_def (arg);
2114 /* Update the argument if there is a reaching def. */
2115 if (reaching_def)
2117 source_location locus;
2118 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2120 SET_USE (arg_p, reaching_def);
2122 /* Virtual operands do not need a location. */
2123 if (virtual_operand_p (reaching_def))
2124 locus = UNKNOWN_LOCATION;
2125 else
2127 gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
2128 gphi *other_phi = dyn_cast <gphi *> (stmt);
2130 /* Single element PHI nodes behave like copies, so get the
2131 location from the phi argument. */
2132 if (other_phi
2133 && gimple_phi_num_args (other_phi) == 1)
2134 locus = gimple_phi_arg_location (other_phi, 0);
2135 else
2136 locus = gimple_location (stmt);
2139 gimple_phi_arg_set_location (phi, arg_i, locus);
2143 if (e->flags & EDGE_ABNORMAL)
2144 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2149 class rewrite_update_dom_walker : public dom_walker
2151 public:
2152 rewrite_update_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2154 virtual edge before_dom_children (basic_block);
2155 virtual void after_dom_children (basic_block);
2158 /* Initialization of block data structures for the incremental SSA
2159 update pass. Create a block local stack of reaching definitions
2160 for new SSA names produced in this block (BLOCK_DEFS). Register
2161 new definitions for every PHI node in the block. */
2163 edge
2164 rewrite_update_dom_walker::before_dom_children (basic_block bb)
2166 bool is_abnormal_phi;
2168 if (dump_file && (dump_flags & TDF_DETAILS))
2169 fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2170 bb->index);
2172 /* Mark the unwind point for this block. */
2173 block_defs_stack.safe_push (NULL_TREE);
2175 if (!bitmap_bit_p (blocks_to_update, bb->index))
2176 return NULL;
2178 /* Mark the LHS if any of the arguments flows through an abnormal
2179 edge. */
2180 is_abnormal_phi = bb_has_abnormal_pred (bb);
2182 /* If any of the PHI nodes is a replacement for a name in
2183 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2184 register it as a new definition for its corresponding name. Also
2185 register definitions for names whose underlying symbols are
2186 marked for renaming. */
2187 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2188 gsi_next (&gsi))
2190 tree lhs, lhs_sym;
2191 gphi *phi = gsi.phi ();
2193 if (!register_defs_p (phi))
2194 continue;
2196 lhs = gimple_phi_result (phi);
2197 lhs_sym = SSA_NAME_VAR (lhs);
2199 if (marked_for_renaming (lhs_sym))
2200 register_new_update_single (lhs, lhs_sym);
2201 else
2204 /* If LHS is a new name, register a new definition for all
2205 the names replaced by LHS. */
2206 if (is_new_name (lhs))
2207 register_new_update_set (lhs, names_replaced_by (lhs));
2209 /* If LHS is an OLD name, register it as a new definition
2210 for itself. */
2211 if (is_old_name (lhs))
2212 register_new_update_single (lhs, lhs);
2215 if (is_abnormal_phi)
2216 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2219 /* Step 2. Rewrite every variable used in each statement in the block. */
2220 if (bitmap_bit_p (interesting_blocks, bb->index))
2222 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2223 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2224 if (rewrite_update_stmt (gsi_stmt (gsi), gsi))
2225 gsi_remove (&gsi, true);
2226 else
2227 gsi_next (&gsi);
2230 /* Step 3. Update PHI nodes. */
2231 rewrite_update_phi_arguments (bb);
2233 return NULL;
2236 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2237 the current reaching definition of every name re-written in BB to
2238 the original reaching definition before visiting BB. This
2239 unwinding must be done in the opposite order to what is done in
2240 register_new_update_set. */
2242 void
2243 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2245 while (block_defs_stack.length () > 0)
2247 tree var = block_defs_stack.pop ();
2248 tree saved_def;
2250 /* NULL indicates the unwind stop point for this block (see
2251 rewrite_update_enter_block). */
2252 if (var == NULL)
2253 return;
2255 saved_def = block_defs_stack.pop ();
2256 get_common_info (var)->current_def = saved_def;
2261 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2262 form.
2264 ENTRY indicates the block where to start. Every block dominated by
2265 ENTRY will be rewritten.
2267 WHAT indicates what actions will be taken by the renamer (see enum
2268 rewrite_mode).
2270 BLOCKS are the set of interesting blocks for the dominator walker
2271 to process. If this set is NULL, then all the nodes dominated
2272 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2273 are not present in BLOCKS are ignored. */
2275 static void
2276 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2278 /* Rewrite all the basic blocks in the program. */
2279 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2281 block_defs_stack.create (10);
2283 /* Recursively walk the dominator tree rewriting each statement in
2284 each basic block. */
2285 if (what == REWRITE_ALL)
2286 rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2287 else if (what == REWRITE_UPDATE)
2288 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2289 else
2290 gcc_unreachable ();
2292 /* Debugging dumps. */
2293 if (dump_file && (dump_flags & TDF_STATS))
2295 dump_dfa_stats (dump_file);
2296 if (var_infos)
2297 dump_tree_ssa_stats (dump_file);
2300 block_defs_stack.release ();
2302 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2305 class mark_def_dom_walker : public dom_walker
2307 public:
2308 mark_def_dom_walker (cdi_direction direction);
2309 ~mark_def_dom_walker ();
2311 virtual edge before_dom_children (basic_block);
2313 private:
2314 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2315 large enough to accommodate all the variables referenced in the
2316 function, not just the ones we are renaming. */
2317 bitmap m_kills;
2320 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2321 : dom_walker (direction), m_kills (BITMAP_ALLOC (NULL))
2325 mark_def_dom_walker::~mark_def_dom_walker ()
2327 BITMAP_FREE (m_kills);
2330 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2331 at the start of each block, and call mark_def_sites for each statement. */
2333 edge
2334 mark_def_dom_walker::before_dom_children (basic_block bb)
2336 gimple_stmt_iterator gsi;
2338 bitmap_clear (m_kills);
2339 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2340 mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2341 return NULL;
2344 /* Initialize internal data needed during renaming. */
2346 static void
2347 init_ssa_renamer (void)
2349 cfun->gimple_df->in_ssa_p = false;
2351 /* Allocate memory for the DEF_BLOCKS hash table. */
2352 gcc_assert (!var_infos);
2353 var_infos = new hash_table<var_info_hasher>
2354 (vec_safe_length (cfun->local_decls));
2356 bitmap_obstack_initialize (&update_ssa_obstack);
2360 /* Deallocate internal data structures used by the renamer. */
2362 static void
2363 fini_ssa_renamer (void)
2365 delete var_infos;
2366 var_infos = NULL;
2368 bitmap_obstack_release (&update_ssa_obstack);
2370 cfun->gimple_df->ssa_renaming_needed = 0;
2371 cfun->gimple_df->rename_vops = 0;
2372 cfun->gimple_df->in_ssa_p = true;
2375 /* Main entry point into the SSA builder. The renaming process
2376 proceeds in four main phases:
2378 1- Compute dominance frontier and immediate dominators, needed to
2379 insert PHI nodes and rename the function in dominator tree
2380 order.
2382 2- Find and mark all the blocks that define variables.
2384 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2386 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2388 Steps 3 and 4 are done using the dominator tree walker
2389 (walk_dominator_tree). */
2391 namespace {
2393 const pass_data pass_data_build_ssa =
2395 GIMPLE_PASS, /* type */
2396 "ssa", /* name */
2397 OPTGROUP_NONE, /* optinfo_flags */
2398 TV_TREE_SSA_OTHER, /* tv_id */
2399 PROP_cfg, /* properties_required */
2400 PROP_ssa, /* properties_provided */
2401 0, /* properties_destroyed */
2402 0, /* todo_flags_start */
2403 TODO_remove_unused_locals, /* todo_flags_finish */
2406 class pass_build_ssa : public gimple_opt_pass
2408 public:
2409 pass_build_ssa (gcc::context *ctxt)
2410 : gimple_opt_pass (pass_data_build_ssa, ctxt)
2413 /* opt_pass methods: */
2414 virtual bool gate (function *fun)
2416 /* Do nothing for funcions that was produced already in SSA form. */
2417 return !(fun->curr_properties & PROP_ssa);
2420 virtual unsigned int execute (function *);
2422 }; // class pass_build_ssa
2424 unsigned int
2425 pass_build_ssa::execute (function *fun)
2427 bitmap_head *dfs;
2428 basic_block bb;
2430 /* Initialize operand data structures. */
2431 init_ssa_operands (fun);
2433 /* Initialize internal data needed by the renamer. */
2434 init_ssa_renamer ();
2436 /* Initialize the set of interesting blocks. The callback
2437 mark_def_sites will add to this set those blocks that the renamer
2438 should process. */
2439 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2440 bitmap_clear (interesting_blocks);
2442 /* Initialize dominance frontier. */
2443 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2444 FOR_EACH_BB_FN (bb, fun)
2445 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2447 /* 1- Compute dominance frontiers. */
2448 calculate_dominance_info (CDI_DOMINATORS);
2449 compute_dominance_frontiers (dfs);
2451 /* 2- Find and mark definition sites. */
2452 mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2454 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2455 insert_phi_nodes (dfs);
2457 /* 4- Rename all the blocks. */
2458 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
2460 /* Free allocated memory. */
2461 FOR_EACH_BB_FN (bb, fun)
2462 bitmap_clear (&dfs[bb->index]);
2463 free (dfs);
2465 sbitmap_free (interesting_blocks);
2467 fini_ssa_renamer ();
2469 /* Try to get rid of all gimplifier generated temporaries by making
2470 its SSA names anonymous. This way we can garbage collect them
2471 all after removing unused locals which we do in our TODO. */
2472 unsigned i;
2473 tree name;
2475 FOR_EACH_SSA_NAME (i, name, cfun)
2477 if (SSA_NAME_IS_DEFAULT_DEF (name))
2478 continue;
2479 tree decl = SSA_NAME_VAR (name);
2480 if (decl
2481 && VAR_P (decl)
2482 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2483 && DECL_IGNORED_P (decl))
2484 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2487 return 0;
2490 } // anon namespace
2492 gimple_opt_pass *
2493 make_pass_build_ssa (gcc::context *ctxt)
2495 return new pass_build_ssa (ctxt);
2499 /* Mark the definition of VAR at STMT and BB as interesting for the
2500 renamer. BLOCKS is the set of blocks that need updating. */
2502 static void
2503 mark_def_interesting (tree var, gimple *stmt, basic_block bb,
2504 bool insert_phi_p)
2506 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2507 set_register_defs (stmt, true);
2509 if (insert_phi_p)
2511 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2513 set_def_block (var, bb, is_phi_p);
2515 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2516 site for both itself and all the old names replaced by it. */
2517 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2519 bitmap_iterator bi;
2520 unsigned i;
2521 bitmap set = names_replaced_by (var);
2522 if (set)
2523 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2524 set_def_block (ssa_name (i), bb, is_phi_p);
2530 /* Mark the use of VAR at STMT and BB as interesting for the
2531 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2532 nodes. */
2534 static inline void
2535 mark_use_interesting (tree var, gimple *stmt, basic_block bb,
2536 bool insert_phi_p)
2538 basic_block def_bb = gimple_bb (stmt);
2540 mark_block_for_update (def_bb);
2541 mark_block_for_update (bb);
2543 if (gimple_code (stmt) == GIMPLE_PHI)
2544 mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt));
2545 else
2547 set_rewrite_uses (stmt, true);
2549 if (is_gimple_debug (stmt))
2550 return;
2553 /* If VAR has not been defined in BB, then it is live-on-entry
2554 to BB. Note that we cannot just use the block holding VAR's
2555 definition because if VAR is one of the names in OLD_SSA_NAMES,
2556 it will have several definitions (itself and all the names that
2557 replace it). */
2558 if (insert_phi_p)
2560 def_blocks *db_p = get_def_blocks_for (get_common_info (var));
2561 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2562 set_livein_block (var, bb);
2567 /* Do a dominator walk starting at BB processing statements that
2568 reference symbols in SSA operands. This is very similar to
2569 mark_def_sites, but the scan handles statements whose operands may
2570 already be SSA names.
2572 If INSERT_PHI_P is true, mark those uses as live in the
2573 corresponding block. This is later used by the PHI placement
2574 algorithm to make PHI pruning decisions.
2576 FIXME. Most of this would be unnecessary if we could associate a
2577 symbol to all the SSA names that reference it. But that
2578 sounds like it would be expensive to maintain. Still, it
2579 would be interesting to see if it makes better sense to do
2580 that. */
2582 static void
2583 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2585 basic_block son;
2586 edge e;
2587 edge_iterator ei;
2589 mark_block_for_update (bb);
2591 /* Process PHI nodes marking interesting those that define or use
2592 the symbols that we are interested in. */
2593 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
2594 gsi_next (&si))
2596 gphi *phi = si.phi ();
2597 tree lhs_sym, lhs = gimple_phi_result (phi);
2599 if (TREE_CODE (lhs) == SSA_NAME
2600 && (! virtual_operand_p (lhs)
2601 || ! cfun->gimple_df->rename_vops))
2602 continue;
2604 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2605 mark_for_renaming (lhs_sym);
2606 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2608 /* Mark the uses in phi nodes as interesting. It would be more correct
2609 to process the arguments of the phi nodes of the successor edges of
2610 BB at the end of prepare_block_for_update, however, that turns out
2611 to be significantly more expensive. Doing it here is conservatively
2612 correct -- it may only cause us to believe a value to be live in a
2613 block that also contains its definition, and thus insert a few more
2614 phi nodes for it. */
2615 FOR_EACH_EDGE (e, ei, bb->preds)
2616 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2619 /* Process the statements. */
2620 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
2621 gsi_next (&si))
2623 gimple *stmt;
2624 ssa_op_iter i;
2625 use_operand_p use_p;
2626 def_operand_p def_p;
2628 stmt = gsi_stmt (si);
2630 if (cfun->gimple_df->rename_vops
2631 && gimple_vuse (stmt))
2633 tree use = gimple_vuse (stmt);
2634 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2635 mark_for_renaming (sym);
2636 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2639 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2641 tree use = USE_FROM_PTR (use_p);
2642 if (!DECL_P (use))
2643 continue;
2644 mark_for_renaming (use);
2645 mark_use_interesting (use, stmt, bb, insert_phi_p);
2648 if (cfun->gimple_df->rename_vops
2649 && gimple_vdef (stmt))
2651 tree def = gimple_vdef (stmt);
2652 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2653 mark_for_renaming (sym);
2654 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2657 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2659 tree def = DEF_FROM_PTR (def_p);
2660 if (!DECL_P (def))
2661 continue;
2662 mark_for_renaming (def);
2663 mark_def_interesting (def, stmt, bb, insert_phi_p);
2667 /* Now visit all the blocks dominated by BB. */
2668 for (son = first_dom_son (CDI_DOMINATORS, bb);
2669 son;
2670 son = next_dom_son (CDI_DOMINATORS, son))
2671 prepare_block_for_update (son, insert_phi_p);
2675 /* Helper for prepare_names_to_update. Mark all the use sites for
2676 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2677 prepare_names_to_update. */
2679 static void
2680 prepare_use_sites_for (tree name, bool insert_phi_p)
2682 use_operand_p use_p;
2683 imm_use_iterator iter;
2685 /* If we rename virtual operands do not update them. */
2686 if (virtual_operand_p (name)
2687 && cfun->gimple_df->rename_vops)
2688 return;
2690 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2692 gimple *stmt = USE_STMT (use_p);
2693 basic_block bb = gimple_bb (stmt);
2695 if (gimple_code (stmt) == GIMPLE_PHI)
2697 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2698 edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix);
2699 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2701 else
2703 /* For regular statements, mark this as an interesting use
2704 for NAME. */
2705 mark_use_interesting (name, stmt, bb, insert_phi_p);
2711 /* Helper for prepare_names_to_update. Mark the definition site for
2712 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2713 prepare_names_to_update. */
2715 static void
2716 prepare_def_site_for (tree name, bool insert_phi_p)
2718 gimple *stmt;
2719 basic_block bb;
2721 gcc_checking_assert (names_to_release == NULL
2722 || !bitmap_bit_p (names_to_release,
2723 SSA_NAME_VERSION (name)));
2725 /* If we rename virtual operands do not update them. */
2726 if (virtual_operand_p (name)
2727 && cfun->gimple_df->rename_vops)
2728 return;
2730 stmt = SSA_NAME_DEF_STMT (name);
2731 bb = gimple_bb (stmt);
2732 if (bb)
2734 gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2735 mark_block_for_update (bb);
2736 mark_def_interesting (name, stmt, bb, insert_phi_p);
2741 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2742 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2743 PHI nodes for newly created names. */
2745 static void
2746 prepare_names_to_update (bool insert_phi_p)
2748 unsigned i = 0;
2749 bitmap_iterator bi;
2750 sbitmap_iterator sbi;
2752 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2753 remove it from NEW_SSA_NAMES so that we don't try to visit its
2754 defining basic block (which most likely doesn't exist). Notice
2755 that we cannot do the same with names in OLD_SSA_NAMES because we
2756 want to replace existing instances. */
2757 if (names_to_release)
2758 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2759 bitmap_clear_bit (new_ssa_names, i);
2761 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2762 names may be considered to be live-in on blocks that contain
2763 definitions for their replacements. */
2764 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2765 prepare_def_site_for (ssa_name (i), insert_phi_p);
2767 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2768 OLD_SSA_NAMES, but we have to ignore its definition site. */
2769 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2771 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2772 prepare_def_site_for (ssa_name (i), insert_phi_p);
2773 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2778 /* Dump all the names replaced by NAME to FILE. */
2780 void
2781 dump_names_replaced_by (FILE *file, tree name)
2783 unsigned i;
2784 bitmap old_set;
2785 bitmap_iterator bi;
2787 print_generic_expr (file, name);
2788 fprintf (file, " -> { ");
2790 old_set = names_replaced_by (name);
2791 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2793 print_generic_expr (file, ssa_name (i));
2794 fprintf (file, " ");
2797 fprintf (file, "}\n");
2801 /* Dump all the names replaced by NAME to stderr. */
2803 DEBUG_FUNCTION void
2804 debug_names_replaced_by (tree name)
2806 dump_names_replaced_by (stderr, name);
2810 /* Dump SSA update information to FILE. */
2812 void
2813 dump_update_ssa (FILE *file)
2815 unsigned i = 0;
2816 bitmap_iterator bi;
2818 if (!need_ssa_update_p (cfun))
2819 return;
2821 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2823 sbitmap_iterator sbi;
2825 fprintf (file, "\nSSA replacement table\n");
2826 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2827 "O_1, ..., O_j\n\n");
2829 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2830 dump_names_replaced_by (file, ssa_name (i));
2833 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2835 fprintf (file, "\nSymbols to be put in SSA form\n");
2836 dump_decl_set (file, symbols_to_rename_set);
2837 fprintf (file, "\n");
2840 if (names_to_release && !bitmap_empty_p (names_to_release))
2842 fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2843 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2845 print_generic_expr (file, ssa_name (i));
2846 fprintf (file, " ");
2848 fprintf (file, "\n");
2853 /* Dump SSA update information to stderr. */
2855 DEBUG_FUNCTION void
2856 debug_update_ssa (void)
2858 dump_update_ssa (stderr);
2862 /* Initialize data structures used for incremental SSA updates. */
2864 static void
2865 init_update_ssa (struct function *fn)
2867 /* Reserve more space than the current number of names. The calls to
2868 add_new_name_mapping are typically done after creating new SSA
2869 names, so we'll need to reallocate these arrays. */
2870 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2871 bitmap_clear (old_ssa_names);
2873 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2874 bitmap_clear (new_ssa_names);
2876 bitmap_obstack_initialize (&update_ssa_obstack);
2878 names_to_release = NULL;
2879 update_ssa_initialized_fn = fn;
2883 /* Deallocate data structures used for incremental SSA updates. */
2885 void
2886 delete_update_ssa (void)
2888 unsigned i;
2889 bitmap_iterator bi;
2891 sbitmap_free (old_ssa_names);
2892 old_ssa_names = NULL;
2894 sbitmap_free (new_ssa_names);
2895 new_ssa_names = NULL;
2897 BITMAP_FREE (symbols_to_rename_set);
2898 symbols_to_rename_set = NULL;
2899 symbols_to_rename.release ();
2901 if (names_to_release)
2903 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2904 release_ssa_name (ssa_name (i));
2905 BITMAP_FREE (names_to_release);
2908 clear_ssa_name_info ();
2910 fini_ssa_renamer ();
2912 if (blocks_with_phis_to_rewrite)
2913 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2915 vec<gphi *> phis = phis_to_rewrite[i];
2916 phis.release ();
2917 phis_to_rewrite[i].create (0);
2920 BITMAP_FREE (blocks_with_phis_to_rewrite);
2921 BITMAP_FREE (blocks_to_update);
2923 update_ssa_initialized_fn = NULL;
2927 /* Create a new name for OLD_NAME in statement STMT and replace the
2928 operand pointed to by DEF_P with the newly created name. If DEF_P
2929 is NULL then STMT should be a GIMPLE assignment.
2930 Return the new name and register the replacement mapping <NEW, OLD> in
2931 update_ssa's tables. */
2933 tree
2934 create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
2936 tree new_name;
2938 timevar_push (TV_TREE_SSA_INCREMENTAL);
2940 if (!update_ssa_initialized_fn)
2941 init_update_ssa (cfun);
2943 gcc_assert (update_ssa_initialized_fn == cfun);
2945 new_name = duplicate_ssa_name (old_name, stmt);
2946 if (def)
2947 SET_DEF (def, new_name);
2948 else
2949 gimple_assign_set_lhs (stmt, new_name);
2951 if (gimple_code (stmt) == GIMPLE_PHI)
2953 basic_block bb = gimple_bb (stmt);
2955 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2956 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2959 add_new_name_mapping (new_name, old_name);
2961 /* For the benefit of passes that will be updating the SSA form on
2962 their own, set the current reaching definition of OLD_NAME to be
2963 NEW_NAME. */
2964 get_ssa_name_ann (old_name)->info.current_def = new_name;
2966 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2968 return new_name;
2972 /* Mark virtual operands of FN for renaming by update_ssa. */
2974 void
2975 mark_virtual_operands_for_renaming (struct function *fn)
2977 fn->gimple_df->ssa_renaming_needed = 1;
2978 fn->gimple_df->rename_vops = 1;
2981 /* Replace all uses of NAME by underlying variable and mark it
2982 for renaming. This assumes the defining statement of NAME is
2983 going to be removed. */
2985 void
2986 mark_virtual_operand_for_renaming (tree name)
2988 tree name_var = SSA_NAME_VAR (name);
2989 bool used = false;
2990 imm_use_iterator iter;
2991 use_operand_p use_p;
2992 gimple *stmt;
2994 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
2995 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
2997 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2998 SET_USE (use_p, name_var);
2999 used = true;
3001 if (used)
3002 mark_virtual_operands_for_renaming (cfun);
3005 /* Replace all uses of the virtual PHI result by its underlying variable
3006 and mark it for renaming. This assumes the PHI node is going to be
3007 removed. */
3009 void
3010 mark_virtual_phi_result_for_renaming (gphi *phi)
3012 if (dump_file && (dump_flags & TDF_DETAILS))
3014 fprintf (dump_file, "Marking result for renaming : ");
3015 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
3016 fprintf (dump_file, "\n");
3019 mark_virtual_operand_for_renaming (gimple_phi_result (phi));
3022 /* Return true if there is any work to be done by update_ssa
3023 for function FN. */
3025 bool
3026 need_ssa_update_p (struct function *fn)
3028 gcc_assert (fn != NULL);
3029 return (update_ssa_initialized_fn == fn
3030 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
3033 /* Return true if name N has been registered in the replacement table. */
3035 bool
3036 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3038 if (!update_ssa_initialized_fn)
3039 return false;
3041 gcc_assert (update_ssa_initialized_fn == cfun);
3043 return is_new_name (n) || is_old_name (n);
3047 /* Mark NAME to be released after update_ssa has finished. */
3049 void
3050 release_ssa_name_after_update_ssa (tree name)
3052 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3054 if (names_to_release == NULL)
3055 names_to_release = BITMAP_ALLOC (NULL);
3057 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3061 /* Insert new PHI nodes to replace VAR. DFS contains dominance
3062 frontier information. BLOCKS is the set of blocks to be updated.
3064 This is slightly different than the regular PHI insertion
3065 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3066 real names (i.e., GIMPLE registers) are inserted:
3068 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3069 nodes inside the region affected by the block that defines VAR
3070 and the blocks that define all its replacements. All these
3071 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3073 First, we compute the entry point to the region (ENTRY). This is
3074 given by the nearest common dominator to all the definition
3075 blocks. When computing the iterated dominance frontier (IDF), any
3076 block not strictly dominated by ENTRY is ignored.
3078 We then call the standard PHI insertion algorithm with the pruned
3079 IDF.
3081 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3082 names is not pruned. PHI nodes are inserted at every IDF block. */
3084 static void
3085 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
3086 unsigned update_flags)
3088 basic_block entry;
3089 def_blocks *db;
3090 bitmap idf, pruned_idf;
3091 bitmap_iterator bi;
3092 unsigned i;
3094 if (TREE_CODE (var) == SSA_NAME)
3095 gcc_checking_assert (is_old_name (var));
3096 else
3097 gcc_checking_assert (marked_for_renaming (var));
3099 /* Get all the definition sites for VAR. */
3100 db = find_def_blocks_for (var);
3102 /* No need to do anything if there were no definitions to VAR. */
3103 if (db == NULL || bitmap_empty_p (db->def_blocks))
3104 return;
3106 /* Compute the initial iterated dominance frontier. */
3107 idf = compute_idf (db->def_blocks, dfs);
3108 pruned_idf = BITMAP_ALLOC (NULL);
3110 if (TREE_CODE (var) == SSA_NAME)
3112 if (update_flags == TODO_update_ssa)
3114 /* If doing regular SSA updates for GIMPLE registers, we are
3115 only interested in IDF blocks dominated by the nearest
3116 common dominator of all the definition blocks. */
3117 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3118 db->def_blocks);
3119 if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3120 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3121 if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3122 && dominated_by_p (CDI_DOMINATORS,
3123 BASIC_BLOCK_FOR_FN (cfun, i), entry))
3124 bitmap_set_bit (pruned_idf, i);
3126 else
3128 /* Otherwise, do not prune the IDF for VAR. */
3129 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3130 bitmap_copy (pruned_idf, idf);
3133 else
3135 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3136 for the first time, so we need to compute the full IDF for
3137 it. */
3138 bitmap_copy (pruned_idf, idf);
3141 if (!bitmap_empty_p (pruned_idf))
3143 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3144 are included in the region to be updated. The feeding blocks
3145 are important to guarantee that the PHI arguments are renamed
3146 properly. */
3148 /* FIXME, this is not needed if we are updating symbols. We are
3149 already starting at the ENTRY block anyway. */
3150 bitmap_ior_into (blocks, pruned_idf);
3151 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3153 edge e;
3154 edge_iterator ei;
3155 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3157 FOR_EACH_EDGE (e, ei, bb->preds)
3158 if (e->src->index >= 0)
3159 bitmap_set_bit (blocks, e->src->index);
3162 insert_phi_nodes_for (var, pruned_idf, true);
3165 BITMAP_FREE (pruned_idf);
3166 BITMAP_FREE (idf);
3169 /* Sort symbols_to_rename after their DECL_UID. */
3171 static int
3172 insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3174 const_tree syma = *(const const_tree *)a;
3175 const_tree symb = *(const const_tree *)b;
3176 if (DECL_UID (syma) == DECL_UID (symb))
3177 return 0;
3178 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3181 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3182 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3184 1- The names in OLD_SSA_NAMES dominated by the definitions of
3185 NEW_SSA_NAMES are all re-written to be reached by the
3186 appropriate definition from NEW_SSA_NAMES.
3188 2- If needed, new PHI nodes are added to the iterated dominance
3189 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3191 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3192 calling create_new_def_for to create new defs for names that the
3193 caller wants to replace.
3195 The caller cretaes the new names to be inserted and the names that need
3196 to be replaced by calling create_new_def_for for each old definition
3197 to be replaced. Note that the function assumes that the
3198 new defining statement has already been inserted in the IL.
3200 For instance, given the following code:
3202 1 L0:
3203 2 x_1 = PHI (0, x_5)
3204 3 if (x_1 < 10)
3205 4 if (x_1 > 7)
3206 5 y_2 = 0
3207 6 else
3208 7 y_3 = x_1 + x_7
3209 8 endif
3210 9 x_5 = x_1 + 1
3211 10 goto L0;
3212 11 endif
3214 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3216 1 L0:
3217 2 x_1 = PHI (0, x_5)
3218 3 if (x_1 < 10)
3219 4 x_10 = ...
3220 5 if (x_1 > 7)
3221 6 y_2 = 0
3222 7 else
3223 8 x_11 = ...
3224 9 y_3 = x_1 + x_7
3225 10 endif
3226 11 x_5 = x_1 + 1
3227 12 goto L0;
3228 13 endif
3230 We want to replace all the uses of x_1 with the new definitions of
3231 x_10 and x_11. Note that the only uses that should be replaced are
3232 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3233 *not* be replaced (this is why we cannot just mark symbol 'x' for
3234 renaming).
3236 Additionally, we may need to insert a PHI node at line 11 because
3237 that is a merge point for x_10 and x_11. So the use of x_1 at line
3238 11 will be replaced with the new PHI node. The insertion of PHI
3239 nodes is optional. They are not strictly necessary to preserve the
3240 SSA form, and depending on what the caller inserted, they may not
3241 even be useful for the optimizers. UPDATE_FLAGS controls various
3242 aspects of how update_ssa operates, see the documentation for
3243 TODO_update_ssa*. */
3245 void
3246 update_ssa (unsigned update_flags)
3248 basic_block bb, start_bb;
3249 bitmap_iterator bi;
3250 unsigned i = 0;
3251 bool insert_phi_p;
3252 sbitmap_iterator sbi;
3253 tree sym;
3255 /* Only one update flag should be set. */
3256 gcc_assert (update_flags == TODO_update_ssa
3257 || update_flags == TODO_update_ssa_no_phi
3258 || update_flags == TODO_update_ssa_full_phi
3259 || update_flags == TODO_update_ssa_only_virtuals);
3261 if (!need_ssa_update_p (cfun))
3262 return;
3264 if (flag_checking)
3266 timevar_push (TV_TREE_STMT_VERIFY);
3268 bool err = false;
3270 FOR_EACH_BB_FN (bb, cfun)
3272 gimple_stmt_iterator gsi;
3273 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3275 gimple *stmt = gsi_stmt (gsi);
3277 ssa_op_iter i;
3278 use_operand_p use_p;
3279 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3281 tree use = USE_FROM_PTR (use_p);
3282 if (TREE_CODE (use) != SSA_NAME)
3283 continue;
3285 if (SSA_NAME_IN_FREE_LIST (use))
3287 error ("statement uses released SSA name:");
3288 debug_gimple_stmt (stmt);
3289 fprintf (stderr, "The use of ");
3290 print_generic_expr (stderr, use);
3291 fprintf (stderr," should have been replaced\n");
3292 err = true;
3298 if (err)
3299 internal_error ("cannot update SSA form");
3301 timevar_pop (TV_TREE_STMT_VERIFY);
3304 timevar_push (TV_TREE_SSA_INCREMENTAL);
3306 if (dump_file && (dump_flags & TDF_DETAILS))
3307 fprintf (dump_file, "\nUpdating SSA:\n");
3309 if (!update_ssa_initialized_fn)
3310 init_update_ssa (cfun);
3311 else if (update_flags == TODO_update_ssa_only_virtuals)
3313 /* If we only need to update virtuals, remove all the mappings for
3314 real names before proceeding. The caller is responsible for
3315 having dealt with the name mappings before calling update_ssa. */
3316 bitmap_clear (old_ssa_names);
3317 bitmap_clear (new_ssa_names);
3320 gcc_assert (update_ssa_initialized_fn == cfun);
3322 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3323 if (!phis_to_rewrite.exists ())
3324 phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3325 blocks_to_update = BITMAP_ALLOC (NULL);
3327 /* Ensure that the dominance information is up-to-date. */
3328 calculate_dominance_info (CDI_DOMINATORS);
3330 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3332 /* If there are names defined in the replacement table, prepare
3333 definition and use sites for all the names in NEW_SSA_NAMES and
3334 OLD_SSA_NAMES. */
3335 if (bitmap_first_set_bit (new_ssa_names) >= 0)
3337 statistics_counter_event (cfun, "Incremental SSA update", 1);
3339 prepare_names_to_update (insert_phi_p);
3341 /* If all the names in NEW_SSA_NAMES had been marked for
3342 removal, and there are no symbols to rename, then there's
3343 nothing else to do. */
3344 if (bitmap_first_set_bit (new_ssa_names) < 0
3345 && !cfun->gimple_df->ssa_renaming_needed)
3346 goto done;
3349 /* Next, determine the block at which to start the renaming process. */
3350 if (cfun->gimple_df->ssa_renaming_needed)
3352 statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
3354 /* If we rename bare symbols initialize the mapping to
3355 auxiliar info we need to keep track of. */
3356 var_infos = new hash_table<var_info_hasher> (47);
3358 /* If we have to rename some symbols from scratch, we need to
3359 start the process at the root of the CFG. FIXME, it should
3360 be possible to determine the nearest block that had a
3361 definition for each of the symbols that are marked for
3362 updating. For now this seems more work than it's worth. */
3363 start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3365 /* Traverse the CFG looking for existing definitions and uses of
3366 symbols in SSA operands. Mark interesting blocks and
3367 statements and set local live-in information for the PHI
3368 placement heuristics. */
3369 prepare_block_for_update (start_bb, insert_phi_p);
3371 tree name;
3373 if (flag_checking)
3374 FOR_EACH_SSA_NAME (i, name, cfun)
3376 if (virtual_operand_p (name))
3377 continue;
3379 /* For all but virtual operands, which do not have SSA names
3380 with overlapping life ranges, ensure that symbols marked
3381 for renaming do not have existing SSA names associated with
3382 them as we do not re-write them out-of-SSA before going
3383 into SSA for the remaining symbol uses. */
3384 if (marked_for_renaming (SSA_NAME_VAR (name)))
3386 fprintf (stderr, "Existing SSA name for symbol marked for "
3387 "renaming: ");
3388 print_generic_expr (stderr, name, TDF_SLIM);
3389 fprintf (stderr, "\n");
3390 internal_error ("SSA corruption");
3394 else
3396 /* Otherwise, the entry block to the region is the nearest
3397 common dominator for the blocks in BLOCKS. */
3398 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3399 blocks_to_update);
3402 /* If requested, insert PHI nodes at the iterated dominance frontier
3403 of every block, creating new definitions for names in OLD_SSA_NAMES
3404 and for symbols found. */
3405 if (insert_phi_p)
3407 bitmap_head *dfs;
3409 /* If the caller requested PHI nodes to be added, compute
3410 dominance frontiers. */
3411 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3412 FOR_EACH_BB_FN (bb, cfun)
3413 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3414 compute_dominance_frontiers (dfs);
3416 if (bitmap_first_set_bit (old_ssa_names) >= 0)
3418 sbitmap_iterator sbi;
3420 /* insert_update_phi_nodes_for will call add_new_name_mapping
3421 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3422 will grow while we are traversing it (but it will not
3423 gain any new members). Copy OLD_SSA_NAMES to a temporary
3424 for traversal. */
3425 auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names));
3426 bitmap_copy (tmp, old_ssa_names);
3427 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3428 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3429 update_flags);
3432 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3433 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3434 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3435 update_flags);
3437 FOR_EACH_BB_FN (bb, cfun)
3438 bitmap_clear (&dfs[bb->index]);
3439 free (dfs);
3441 /* Insertion of PHI nodes may have added blocks to the region.
3442 We need to re-compute START_BB to include the newly added
3443 blocks. */
3444 if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3445 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3446 blocks_to_update);
3449 /* Reset the current definition for name and symbol before renaming
3450 the sub-graph. */
3451 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3452 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3454 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3455 get_var_info (sym)->info.current_def = NULL_TREE;
3457 /* Now start the renaming process at START_BB. */
3458 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3459 bitmap_clear (interesting_blocks);
3460 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3461 bitmap_set_bit (interesting_blocks, i);
3463 rewrite_blocks (start_bb, REWRITE_UPDATE);
3465 sbitmap_free (interesting_blocks);
3467 /* Debugging dumps. */
3468 if (dump_file)
3470 int c;
3471 unsigned i;
3473 dump_update_ssa (dump_file);
3475 fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3476 start_bb->index);
3478 c = 0;
3479 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3480 c++;
3481 fprintf (dump_file, "Number of blocks in CFG: %d\n",
3482 last_basic_block_for_fn (cfun));
3483 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3484 c, PERCENT (c, last_basic_block_for_fn (cfun)));
3486 if (dump_flags & TDF_DETAILS)
3488 fprintf (dump_file, "Affected blocks:");
3489 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3490 fprintf (dump_file, " %u", i);
3491 fprintf (dump_file, "\n");
3494 fprintf (dump_file, "\n\n");
3497 /* Free allocated memory. */
3498 done:
3499 delete_update_ssa ();
3501 timevar_pop (TV_TREE_SSA_INCREMENTAL);