* Makefile.in (C_COMMON_OBJS): Depend on c-cilkplus.o.
[official-gcc.git] / gcc / tree-into-ssa.c
blobe7c5d50da0cd40ea32d5466b1602f6f10cd8e7a5
1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "tm_p.h"
28 #include "langhooks.h"
29 #include "basic-block.h"
30 #include "function.h"
31 #include "gimple-pretty-print.h"
32 #include "gimple.h"
33 #include "gimple-iterator.h"
34 #include "gimple-ssa.h"
35 #include "tree-cfg.h"
36 #include "tree-phinodes.h"
37 #include "ssa-iterators.h"
38 #include "tree-ssanames.h"
39 #include "tree-into-ssa.h"
40 #include "tree-dfa.h"
41 #include "tree-ssa.h"
42 #include "tree-inline.h"
43 #include "hash-table.h"
44 #include "tree-pass.h"
45 #include "cfgloop.h"
46 #include "domwalk.h"
47 #include "params.h"
48 #include "diagnostic-core.h"
49 #include "tree-into-ssa.h"
52 /* This file builds the SSA form for a function as described in:
53 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
54 Computing Static Single Assignment Form and the Control Dependence
55 Graph. ACM Transactions on Programming Languages and Systems,
56 13(4):451-490, October 1991. */
58 /* Structure to map a variable VAR to the set of blocks that contain
59 definitions for VAR. */
60 struct def_blocks_d
62 /* Blocks that contain definitions of VAR. Bit I will be set if the
63 Ith block contains a definition of VAR. */
64 bitmap def_blocks;
66 /* Blocks that contain a PHI node for VAR. */
67 bitmap phi_blocks;
69 /* Blocks where VAR is live-on-entry. Similar semantics as
70 DEF_BLOCKS. */
71 bitmap livein_blocks;
74 typedef struct def_blocks_d *def_blocks_p;
77 /* Stack of trees used to restore the global currdefs to its original
78 state after completing rewriting of a block and its dominator
79 children. Its elements have the following properties:
81 - An SSA_NAME (N) indicates that the current definition of the
82 underlying variable should be set to the given SSA_NAME. If the
83 symbol associated with the SSA_NAME is not a GIMPLE register, the
84 next slot in the stack must be a _DECL node (SYM). In this case,
85 the name N in the previous slot is the current reaching
86 definition for SYM.
88 - A _DECL node indicates that the underlying variable has no
89 current definition.
91 - A NULL node at the top entry is used to mark the last slot
92 associated with the current block. */
93 static vec<tree> block_defs_stack;
96 /* Set of existing SSA names being replaced by update_ssa. */
97 static sbitmap old_ssa_names;
99 /* Set of new SSA names being added by update_ssa. Note that both
100 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
101 the operations done on them are presence tests. */
102 static sbitmap new_ssa_names;
104 static sbitmap interesting_blocks;
106 /* Set of SSA names that have been marked to be released after they
107 were registered in the replacement table. They will be finally
108 released after we finish updating the SSA web. */
109 static bitmap names_to_release;
111 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
112 the to basic block with index I. Allocated once per compilation, *not*
113 released between different functions. */
114 static vec<gimple_vec> phis_to_rewrite;
116 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
117 static bitmap blocks_with_phis_to_rewrite;
119 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
120 to grow as the callers to create_new_def_for will create new names on
121 the fly.
122 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
123 need to find a reasonable growth strategy. */
124 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
127 /* The function the SSA updating data structures have been initialized for.
128 NULL if they need to be initialized by create_new_def_for. */
129 static struct function *update_ssa_initialized_fn = NULL;
131 /* Global data to attach to the main dominator walk structure. */
132 struct mark_def_sites_global_data
134 /* This bitmap contains the variables which are set before they
135 are used in a basic block. */
136 bitmap kills;
139 /* It is advantageous to avoid things like life analysis for variables which
140 do not need PHI nodes. This enum describes whether or not a particular
141 variable may need a PHI node. */
143 enum need_phi_state {
144 /* This is the default. If we are still in this state after finding
145 all the definition and use sites, then we will assume the variable
146 needs PHI nodes. This is probably an overly conservative assumption. */
147 NEED_PHI_STATE_UNKNOWN,
149 /* This state indicates that we have seen one or more sets of the
150 variable in a single basic block and that the sets dominate all
151 uses seen so far. If after finding all definition and use sites
152 we are still in this state, then the variable does not need any
153 PHI nodes. */
154 NEED_PHI_STATE_NO,
156 /* This state indicates that we have either seen multiple definitions of
157 the variable in multiple blocks, or that we encountered a use in a
158 block that was not dominated by the block containing the set(s) of
159 this variable. This variable is assumed to need PHI nodes. */
160 NEED_PHI_STATE_MAYBE
163 /* Information stored for both SSA names and decls. */
164 struct common_info_d
166 /* This field indicates whether or not the variable may need PHI nodes.
167 See the enum's definition for more detailed information about the
168 states. */
169 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
171 /* The current reaching definition replacing this var. */
172 tree current_def;
174 /* Definitions for this var. */
175 struct def_blocks_d def_blocks;
178 /* The information associated with decls and SSA names. */
179 typedef struct common_info_d *common_info_p;
181 /* Information stored for decls. */
182 struct var_info_d
184 /* The variable. */
185 tree var;
187 /* Information stored for both SSA names and decls. */
188 struct common_info_d info;
191 /* The information associated with decls. */
192 typedef struct var_info_d *var_info_p;
195 /* VAR_INFOS hashtable helpers. */
197 struct var_info_hasher : typed_free_remove <var_info_d>
199 typedef var_info_d value_type;
200 typedef var_info_d compare_type;
201 static inline hashval_t hash (const value_type *);
202 static inline bool equal (const value_type *, const compare_type *);
205 inline hashval_t
206 var_info_hasher::hash (const value_type *p)
208 return DECL_UID (p->var);
211 inline bool
212 var_info_hasher::equal (const value_type *p1, const compare_type *p2)
214 return p1->var == p2->var;
218 /* Each entry in VAR_INFOS contains an element of type STRUCT
219 VAR_INFO_D. */
220 static hash_table <var_info_hasher> var_infos;
223 /* Information stored for SSA names. */
224 struct ssa_name_info
226 /* Age of this record (so that info_for_ssa_name table can be cleared
227 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
228 are assumed to be null. */
229 unsigned age;
231 /* Replacement mappings, allocated from update_ssa_obstack. */
232 bitmap repl_set;
234 /* Information stored for both SSA names and decls. */
235 struct common_info_d info;
238 /* The information associated with names. */
239 typedef struct ssa_name_info *ssa_name_info_p;
241 static vec<ssa_name_info_p> info_for_ssa_name;
242 static unsigned current_info_for_ssa_name_age;
244 static bitmap_obstack update_ssa_obstack;
246 /* The set of blocks affected by update_ssa. */
247 static bitmap blocks_to_update;
249 /* The main entry point to the SSA renamer (rewrite_blocks) may be
250 called several times to do different, but related, tasks.
251 Initially, we need it to rename the whole program into SSA form.
252 At other times, we may need it to only rename into SSA newly
253 exposed symbols. Finally, we can also call it to incrementally fix
254 an already built SSA web. */
255 enum rewrite_mode {
256 /* Convert the whole function into SSA form. */
257 REWRITE_ALL,
259 /* Incrementally update the SSA web by replacing existing SSA
260 names with new ones. See update_ssa for details. */
261 REWRITE_UPDATE
264 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
265 static bitmap symbols_to_rename_set;
266 static vec<tree> symbols_to_rename;
268 /* Mark SYM for renaming. */
270 static void
271 mark_for_renaming (tree sym)
273 if (!symbols_to_rename_set)
274 symbols_to_rename_set = BITMAP_ALLOC (NULL);
275 if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
276 symbols_to_rename.safe_push (sym);
279 /* Return true if SYM is marked for renaming. */
281 static bool
282 marked_for_renaming (tree sym)
284 if (!symbols_to_rename_set || sym == NULL_TREE)
285 return false;
286 return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
290 /* Return true if STMT needs to be rewritten. When renaming a subset
291 of the variables, not all statements will be processed. This is
292 decided in mark_def_sites. */
294 static inline bool
295 rewrite_uses_p (gimple stmt)
297 return gimple_visited_p (stmt);
301 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
303 static inline void
304 set_rewrite_uses (gimple stmt, bool rewrite_p)
306 gimple_set_visited (stmt, rewrite_p);
310 /* Return true if the DEFs created by statement STMT should be
311 registered when marking new definition sites. This is slightly
312 different than rewrite_uses_p: it's used by update_ssa to
313 distinguish statements that need to have both uses and defs
314 processed from those that only need to have their defs processed.
315 Statements that define new SSA names only need to have their defs
316 registered, but they don't need to have their uses renamed. */
318 static inline bool
319 register_defs_p (gimple stmt)
321 return gimple_plf (stmt, GF_PLF_1) != 0;
325 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
327 static inline void
328 set_register_defs (gimple stmt, bool register_defs_p)
330 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
334 /* Get the information associated with NAME. */
336 static inline ssa_name_info_p
337 get_ssa_name_ann (tree name)
339 unsigned ver = SSA_NAME_VERSION (name);
340 unsigned len = info_for_ssa_name.length ();
341 struct ssa_name_info *info;
343 /* Re-allocate the vector at most once per update/into-SSA. */
344 if (ver >= len)
345 info_for_ssa_name.safe_grow_cleared (num_ssa_names);
347 /* But allocate infos lazily. */
348 info = info_for_ssa_name[ver];
349 if (!info)
351 info = XCNEW (struct ssa_name_info);
352 info->age = current_info_for_ssa_name_age;
353 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
354 info_for_ssa_name[ver] = info;
357 if (info->age < current_info_for_ssa_name_age)
359 info->age = current_info_for_ssa_name_age;
360 info->repl_set = NULL;
361 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
362 info->info.current_def = NULL_TREE;
363 info->info.def_blocks.def_blocks = NULL;
364 info->info.def_blocks.phi_blocks = NULL;
365 info->info.def_blocks.livein_blocks = NULL;
368 return info;
371 /* Return and allocate the auxiliar information for DECL. */
373 static inline var_info_p
374 get_var_info (tree decl)
376 struct var_info_d vi;
377 var_info_d **slot;
378 vi.var = decl;
379 slot = var_infos.find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
380 if (*slot == NULL)
382 var_info_p v = XCNEW (struct var_info_d);
383 v->var = decl;
384 *slot = v;
385 return v;
387 return *slot;
391 /* Clears info for SSA names. */
393 static void
394 clear_ssa_name_info (void)
396 current_info_for_ssa_name_age++;
398 /* If current_info_for_ssa_name_age wraps we use stale information.
399 Asser that this does not happen. */
400 gcc_assert (current_info_for_ssa_name_age != 0);
404 /* Get access to the auxiliar information stored per SSA name or decl. */
406 static inline common_info_p
407 get_common_info (tree var)
409 if (TREE_CODE (var) == SSA_NAME)
410 return &get_ssa_name_ann (var)->info;
411 else
412 return &get_var_info (var)->info;
416 /* Return the current definition for VAR. */
418 tree
419 get_current_def (tree var)
421 return get_common_info (var)->current_def;
425 /* Sets current definition of VAR to DEF. */
427 void
428 set_current_def (tree var, tree def)
430 get_common_info (var)->current_def = def;
433 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
434 all statements in basic block BB. */
436 static void
437 initialize_flags_in_bb (basic_block bb)
439 gimple stmt;
440 gimple_stmt_iterator gsi;
442 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
444 gimple phi = gsi_stmt (gsi);
445 set_rewrite_uses (phi, false);
446 set_register_defs (phi, false);
449 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
451 stmt = gsi_stmt (gsi);
453 /* We are going to use the operand cache API, such as
454 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
455 cache for each statement should be up-to-date. */
456 gcc_checking_assert (!gimple_modified_p (stmt));
457 set_rewrite_uses (stmt, false);
458 set_register_defs (stmt, false);
462 /* Mark block BB as interesting for update_ssa. */
464 static void
465 mark_block_for_update (basic_block bb)
467 gcc_checking_assert (blocks_to_update != NULL);
468 if (!bitmap_set_bit (blocks_to_update, bb->index))
469 return;
470 initialize_flags_in_bb (bb);
473 /* Return the set of blocks where variable VAR is defined and the blocks
474 where VAR is live on entry (livein). If no entry is found in
475 DEF_BLOCKS, a new one is created and returned. */
477 static inline struct def_blocks_d *
478 get_def_blocks_for (common_info_p info)
480 struct def_blocks_d *db_p = &info->def_blocks;
481 if (!db_p->def_blocks)
483 db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
484 db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
485 db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
488 return db_p;
492 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
493 VAR is defined by a PHI node. */
495 static void
496 set_def_block (tree var, basic_block bb, bool phi_p)
498 struct def_blocks_d *db_p;
499 common_info_p info;
501 info = get_common_info (var);
502 db_p = get_def_blocks_for (info);
504 /* Set the bit corresponding to the block where VAR is defined. */
505 bitmap_set_bit (db_p->def_blocks, bb->index);
506 if (phi_p)
507 bitmap_set_bit (db_p->phi_blocks, bb->index);
509 /* Keep track of whether or not we may need to insert PHI nodes.
511 If we are in the UNKNOWN state, then this is the first definition
512 of VAR. Additionally, we have not seen any uses of VAR yet, so
513 we do not need a PHI node for this variable at this time (i.e.,
514 transition to NEED_PHI_STATE_NO).
516 If we are in any other state, then we either have multiple definitions
517 of this variable occurring in different blocks or we saw a use of the
518 variable which was not dominated by the block containing the
519 definition(s). In this case we may need a PHI node, so enter
520 state NEED_PHI_STATE_MAYBE. */
521 if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
522 info->need_phi_state = NEED_PHI_STATE_NO;
523 else
524 info->need_phi_state = NEED_PHI_STATE_MAYBE;
528 /* Mark block BB as having VAR live at the entry to BB. */
530 static void
531 set_livein_block (tree var, basic_block bb)
533 common_info_p info;
534 struct def_blocks_d *db_p;
536 info = get_common_info (var);
537 db_p = get_def_blocks_for (info);
539 /* Set the bit corresponding to the block where VAR is live in. */
540 bitmap_set_bit (db_p->livein_blocks, bb->index);
542 /* Keep track of whether or not we may need to insert PHI nodes.
544 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
545 by the single block containing the definition(s) of this variable. If
546 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
547 NEED_PHI_STATE_MAYBE. */
548 if (info->need_phi_state == NEED_PHI_STATE_NO)
550 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
552 if (def_block_index == -1
553 || ! dominated_by_p (CDI_DOMINATORS, bb,
554 BASIC_BLOCK (def_block_index)))
555 info->need_phi_state = NEED_PHI_STATE_MAYBE;
557 else
558 info->need_phi_state = NEED_PHI_STATE_MAYBE;
562 /* Return true if NAME is in OLD_SSA_NAMES. */
564 static inline bool
565 is_old_name (tree name)
567 unsigned ver = SSA_NAME_VERSION (name);
568 if (!new_ssa_names)
569 return false;
570 return (ver < SBITMAP_SIZE (new_ssa_names)
571 && bitmap_bit_p (old_ssa_names, ver));
575 /* Return true if NAME is in NEW_SSA_NAMES. */
577 static inline bool
578 is_new_name (tree name)
580 unsigned ver = SSA_NAME_VERSION (name);
581 if (!new_ssa_names)
582 return false;
583 return (ver < SBITMAP_SIZE (new_ssa_names)
584 && bitmap_bit_p (new_ssa_names, ver));
588 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
590 static inline bitmap
591 names_replaced_by (tree new_tree)
593 return get_ssa_name_ann (new_tree)->repl_set;
597 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
599 static inline void
600 add_to_repl_tbl (tree new_tree, tree old)
602 bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
603 if (!*set)
604 *set = BITMAP_ALLOC (&update_ssa_obstack);
605 bitmap_set_bit (*set, SSA_NAME_VERSION (old));
609 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
610 represents the set of names O_1 ... O_j replaced by N_i. This is
611 used by update_ssa and its helpers to introduce new SSA names in an
612 already formed SSA web. */
614 static void
615 add_new_name_mapping (tree new_tree, tree old)
617 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
618 gcc_checking_assert (new_tree != old
619 && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
621 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
622 caller may have created new names since the set was created. */
623 if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
625 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
626 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
627 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
630 /* Update the REPL_TBL table. */
631 add_to_repl_tbl (new_tree, old);
633 /* If OLD had already been registered as a new name, then all the
634 names that OLD replaces should also be replaced by NEW_TREE. */
635 if (is_new_name (old))
636 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
638 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
639 respectively. */
640 bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
641 bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
645 /* Call back for walk_dominator_tree used to collect definition sites
646 for every variable in the function. For every statement S in block
649 1- Variables defined by S in the DEFS of S are marked in the bitmap
650 KILLS.
652 2- If S uses a variable VAR and there is no preceding kill of VAR,
653 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
655 This information is used to determine which variables are live
656 across block boundaries to reduce the number of PHI nodes
657 we create. */
659 static void
660 mark_def_sites (basic_block bb, gimple stmt, bitmap kills)
662 tree def;
663 use_operand_p use_p;
664 ssa_op_iter iter;
666 /* Since this is the first time that we rewrite the program into SSA
667 form, force an operand scan on every statement. */
668 update_stmt (stmt);
670 gcc_checking_assert (blocks_to_update == NULL);
671 set_register_defs (stmt, false);
672 set_rewrite_uses (stmt, false);
674 if (is_gimple_debug (stmt))
676 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
678 tree sym = USE_FROM_PTR (use_p);
679 gcc_checking_assert (DECL_P (sym));
680 set_rewrite_uses (stmt, true);
682 if (rewrite_uses_p (stmt))
683 bitmap_set_bit (interesting_blocks, bb->index);
684 return;
687 /* If a variable is used before being set, then the variable is live
688 across a block boundary, so mark it live-on-entry to BB. */
689 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
691 tree sym = USE_FROM_PTR (use_p);
692 gcc_checking_assert (DECL_P (sym));
693 if (!bitmap_bit_p (kills, DECL_UID (sym)))
694 set_livein_block (sym, bb);
695 set_rewrite_uses (stmt, true);
698 /* Now process the defs. Mark BB as the definition block and add
699 each def to the set of killed symbols. */
700 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
702 gcc_checking_assert (DECL_P (def));
703 set_def_block (def, bb, false);
704 bitmap_set_bit (kills, DECL_UID (def));
705 set_register_defs (stmt, true);
708 /* If we found the statement interesting then also mark the block BB
709 as interesting. */
710 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
711 bitmap_set_bit (interesting_blocks, bb->index);
714 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
715 in the dfs numbering of the dominance tree. */
717 struct dom_dfsnum
719 /* Basic block whose index this entry corresponds to. */
720 unsigned bb_index;
722 /* The dfs number of this node. */
723 unsigned dfs_num;
726 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
727 for qsort. */
729 static int
730 cmp_dfsnum (const void *a, const void *b)
732 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
733 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
735 return (int) da->dfs_num - (int) db->dfs_num;
738 /* Among the intervals starting at the N points specified in DEFS, find
739 the one that contains S, and return its bb_index. */
741 static unsigned
742 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
744 unsigned f = 0, t = n, m;
746 while (t > f + 1)
748 m = (f + t) / 2;
749 if (defs[m].dfs_num <= s)
750 f = m;
751 else
752 t = m;
755 return defs[f].bb_index;
758 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
759 KILLS is a bitmap of blocks where the value is defined before any use. */
761 static void
762 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
764 vec<int> worklist;
765 bitmap_iterator bi;
766 unsigned i, b, p, u, top;
767 bitmap live_phis;
768 basic_block def_bb, use_bb;
769 edge e;
770 edge_iterator ei;
771 bitmap to_remove;
772 struct dom_dfsnum *defs;
773 unsigned n_defs, adef;
775 if (bitmap_empty_p (uses))
777 bitmap_clear (phis);
778 return;
781 /* The phi must dominate a use, or an argument of a live phi. Also, we
782 do not create any phi nodes in def blocks, unless they are also livein. */
783 to_remove = BITMAP_ALLOC (NULL);
784 bitmap_and_compl (to_remove, kills, uses);
785 bitmap_and_compl_into (phis, to_remove);
786 if (bitmap_empty_p (phis))
788 BITMAP_FREE (to_remove);
789 return;
792 /* We want to remove the unnecessary phi nodes, but we do not want to compute
793 liveness information, as that may be linear in the size of CFG, and if
794 there are lot of different variables to rewrite, this may lead to quadratic
795 behavior.
797 Instead, we basically emulate standard dce. We put all uses to worklist,
798 then for each of them find the nearest def that dominates them. If this
799 def is a phi node, we mark it live, and if it was not live before, we
800 add the predecessors of its basic block to the worklist.
802 To quickly locate the nearest def that dominates use, we use dfs numbering
803 of the dominance tree (that is already available in order to speed up
804 queries). For each def, we have the interval given by the dfs number on
805 entry to and on exit from the corresponding subtree in the dominance tree.
806 The nearest dominator for a given use is the smallest of these intervals
807 that contains entry and exit dfs numbers for the basic block with the use.
808 If we store the bounds for all the uses to an array and sort it, we can
809 locate the nearest dominating def in logarithmic time by binary search.*/
810 bitmap_ior (to_remove, kills, phis);
811 n_defs = bitmap_count_bits (to_remove);
812 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
813 defs[0].bb_index = 1;
814 defs[0].dfs_num = 0;
815 adef = 1;
816 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
818 def_bb = BASIC_BLOCK (i);
819 defs[adef].bb_index = i;
820 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
821 defs[adef + 1].bb_index = i;
822 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
823 adef += 2;
825 BITMAP_FREE (to_remove);
826 gcc_assert (adef == 2 * n_defs + 1);
827 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
828 gcc_assert (defs[0].bb_index == 1);
830 /* Now each DEFS entry contains the number of the basic block to that the
831 dfs number corresponds. Change them to the number of basic block that
832 corresponds to the interval following the dfs number. Also, for the
833 dfs_out numbers, increase the dfs number by one (so that it corresponds
834 to the start of the following interval, not to the end of the current
835 one). We use WORKLIST as a stack. */
836 worklist.create (n_defs + 1);
837 worklist.quick_push (1);
838 top = 1;
839 n_defs = 1;
840 for (i = 1; i < adef; i++)
842 b = defs[i].bb_index;
843 if (b == top)
845 /* This is a closing element. Interval corresponding to the top
846 of the stack after removing it follows. */
847 worklist.pop ();
848 top = worklist[worklist.length () - 1];
849 defs[n_defs].bb_index = top;
850 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
852 else
854 /* Opening element. Nothing to do, just push it to the stack and move
855 it to the correct position. */
856 defs[n_defs].bb_index = defs[i].bb_index;
857 defs[n_defs].dfs_num = defs[i].dfs_num;
858 worklist.quick_push (b);
859 top = b;
862 /* If this interval starts at the same point as the previous one, cancel
863 the previous one. */
864 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
865 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
866 else
867 n_defs++;
869 worklist.pop ();
870 gcc_assert (worklist.is_empty ());
872 /* Now process the uses. */
873 live_phis = BITMAP_ALLOC (NULL);
874 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
876 worklist.safe_push (i);
879 while (!worklist.is_empty ())
881 b = worklist.pop ();
882 if (b == ENTRY_BLOCK)
883 continue;
885 /* If there is a phi node in USE_BB, it is made live. Otherwise,
886 find the def that dominates the immediate dominator of USE_BB
887 (the kill in USE_BB does not dominate the use). */
888 if (bitmap_bit_p (phis, b))
889 p = b;
890 else
892 use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
893 p = find_dfsnum_interval (defs, n_defs,
894 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
895 if (!bitmap_bit_p (phis, p))
896 continue;
899 /* If the phi node is already live, there is nothing to do. */
900 if (!bitmap_set_bit (live_phis, p))
901 continue;
903 /* Add the new uses to the worklist. */
904 def_bb = BASIC_BLOCK (p);
905 FOR_EACH_EDGE (e, ei, def_bb->preds)
907 u = e->src->index;
908 if (bitmap_bit_p (uses, u))
909 continue;
911 /* In case there is a kill directly in the use block, do not record
912 the use (this is also necessary for correctness, as we assume that
913 uses dominated by a def directly in their block have been filtered
914 out before). */
915 if (bitmap_bit_p (kills, u))
916 continue;
918 bitmap_set_bit (uses, u);
919 worklist.safe_push (u);
923 worklist.release ();
924 bitmap_copy (phis, live_phis);
925 BITMAP_FREE (live_phis);
926 free (defs);
929 /* Return the set of blocks where variable VAR is defined and the blocks
930 where VAR is live on entry (livein). Return NULL, if no entry is
931 found in DEF_BLOCKS. */
933 static inline struct def_blocks_d *
934 find_def_blocks_for (tree var)
936 def_blocks_p p = &get_common_info (var)->def_blocks;
937 if (!p->def_blocks)
938 return NULL;
939 return p;
943 /* Marks phi node PHI in basic block BB for rewrite. */
945 static void
946 mark_phi_for_rewrite (basic_block bb, gimple phi)
948 gimple_vec phis;
949 unsigned n, idx = bb->index;
951 if (rewrite_uses_p (phi))
952 return;
954 set_rewrite_uses (phi, true);
956 if (!blocks_with_phis_to_rewrite)
957 return;
959 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
961 n = (unsigned) last_basic_block + 1;
962 if (phis_to_rewrite.length () < n)
963 phis_to_rewrite.safe_grow_cleared (n);
965 phis = phis_to_rewrite[idx];
966 phis.reserve (10);
968 phis.safe_push (phi);
969 phis_to_rewrite[idx] = phis;
972 /* Insert PHI nodes for variable VAR using the iterated dominance
973 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
974 function assumes that the caller is incrementally updating the
975 existing SSA form, in which case VAR may be an SSA name instead of
976 a symbol.
978 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
979 PHI node for VAR. On exit, only the nodes that received a PHI node
980 for VAR will be present in PHI_INSERTION_POINTS. */
982 static void
983 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
985 unsigned bb_index;
986 edge e;
987 gimple phi;
988 basic_block bb;
989 bitmap_iterator bi;
990 struct def_blocks_d *def_map = find_def_blocks_for (var);
992 /* Remove the blocks where we already have PHI nodes for VAR. */
993 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
995 /* Remove obviously useless phi nodes. */
996 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
997 def_map->livein_blocks);
999 /* And insert the PHI nodes. */
1000 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1002 bb = BASIC_BLOCK (bb_index);
1003 if (update_p)
1004 mark_block_for_update (bb);
1006 if (dump_file && (dump_flags & TDF_DETAILS))
1008 fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
1009 print_generic_expr (dump_file, var, TDF_SLIM);
1010 fprintf (dump_file, "\n");
1012 phi = NULL;
1014 if (TREE_CODE (var) == SSA_NAME)
1016 /* If we are rewriting SSA names, create the LHS of the PHI
1017 node by duplicating VAR. This is useful in the case of
1018 pointers, to also duplicate pointer attributes (alias
1019 information, in particular). */
1020 edge_iterator ei;
1021 tree new_lhs;
1023 gcc_checking_assert (update_p);
1024 new_lhs = duplicate_ssa_name (var, NULL);
1025 phi = create_phi_node (new_lhs, bb);
1026 add_new_name_mapping (new_lhs, var);
1028 /* Add VAR to every argument slot of PHI. We need VAR in
1029 every argument so that rewrite_update_phi_arguments knows
1030 which name is this PHI node replacing. If VAR is a
1031 symbol marked for renaming, this is not necessary, the
1032 renamer will use the symbol on the LHS to get its
1033 reaching definition. */
1034 FOR_EACH_EDGE (e, ei, bb->preds)
1035 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1037 else
1039 tree tracked_var;
1041 gcc_checking_assert (DECL_P (var));
1042 phi = create_phi_node (var, bb);
1044 tracked_var = target_for_debug_bind (var);
1045 if (tracked_var)
1047 gimple note = gimple_build_debug_bind (tracked_var,
1048 PHI_RESULT (phi),
1049 phi);
1050 gimple_stmt_iterator si = gsi_after_labels (bb);
1051 gsi_insert_before (&si, note, GSI_SAME_STMT);
1055 /* Mark this PHI node as interesting for update_ssa. */
1056 set_register_defs (phi, true);
1057 mark_phi_for_rewrite (bb, phi);
1061 /* Sort var_infos after DECL_UID of their var. */
1063 static int
1064 insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1066 const struct var_info_d *defa = *(struct var_info_d * const *)a;
1067 const struct var_info_d *defb = *(struct var_info_d * const *)b;
1068 if (DECL_UID (defa->var) < DECL_UID (defb->var))
1069 return -1;
1070 else
1071 return 1;
1074 /* Insert PHI nodes at the dominance frontier of blocks with variable
1075 definitions. DFS contains the dominance frontier information for
1076 the flowgraph. */
1078 static void
1079 insert_phi_nodes (bitmap_head *dfs)
1081 hash_table <var_info_hasher>::iterator hi;
1082 unsigned i;
1083 var_info_p info;
1084 vec<var_info_p> vars;
1086 timevar_push (TV_TREE_INSERT_PHI_NODES);
1088 vars.create (var_infos.elements ());
1089 FOR_EACH_HASH_TABLE_ELEMENT (var_infos, info, var_info_p, hi)
1090 if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1091 vars.quick_push (info);
1093 /* Do two stages to avoid code generation differences for UID
1094 differences but no UID ordering differences. */
1095 vars.qsort (insert_phi_nodes_compare_var_infos);
1097 FOR_EACH_VEC_ELT (vars, i, info)
1099 bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1100 insert_phi_nodes_for (info->var, idf, false);
1101 BITMAP_FREE (idf);
1104 vars.release ();
1106 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1110 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1111 register DEF (an SSA_NAME) to be a new definition for SYM. */
1113 static void
1114 register_new_def (tree def, tree sym)
1116 common_info_p info = get_common_info (sym);
1117 tree currdef;
1119 /* If this variable is set in a single basic block and all uses are
1120 dominated by the set(s) in that single basic block, then there is
1121 no reason to record anything for this variable in the block local
1122 definition stacks. Doing so just wastes time and memory.
1124 This is the same test to prune the set of variables which may
1125 need PHI nodes. So we just use that information since it's already
1126 computed and available for us to use. */
1127 if (info->need_phi_state == NEED_PHI_STATE_NO)
1129 info->current_def = def;
1130 return;
1133 currdef = info->current_def;
1135 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1136 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1137 in the stack so that we know which symbol is being defined by
1138 this SSA name when we unwind the stack. */
1139 if (currdef && !is_gimple_reg (sym))
1140 block_defs_stack.safe_push (sym);
1142 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1143 stack is later used by the dominator tree callbacks to restore
1144 the reaching definitions for all the variables defined in the
1145 block after a recursive visit to all its immediately dominated
1146 blocks. If there is no current reaching definition, then just
1147 record the underlying _DECL node. */
1148 block_defs_stack.safe_push (currdef ? currdef : sym);
1150 /* Set the current reaching definition for SYM to be DEF. */
1151 info->current_def = def;
1155 /* Perform a depth-first traversal of the dominator tree looking for
1156 variables to rename. BB is the block where to start searching.
1157 Renaming is a five step process:
1159 1- Every definition made by PHI nodes at the start of the blocks is
1160 registered as the current definition for the corresponding variable.
1162 2- Every statement in BB is rewritten. USE and VUSE operands are
1163 rewritten with their corresponding reaching definition. DEF and
1164 VDEF targets are registered as new definitions.
1166 3- All the PHI nodes in successor blocks of BB are visited. The
1167 argument corresponding to BB is replaced with its current reaching
1168 definition.
1170 4- Recursively rewrite every dominator child block of BB.
1172 5- Restore (in reverse order) the current reaching definition for every
1173 new definition introduced in this block. This is done so that when
1174 we return from the recursive call, all the current reaching
1175 definitions are restored to the names that were valid in the
1176 dominator parent of BB. */
1178 /* Return the current definition for variable VAR. If none is found,
1179 create a new SSA name to act as the zeroth definition for VAR. */
1181 static tree
1182 get_reaching_def (tree var)
1184 common_info_p info = get_common_info (var);
1185 tree currdef;
1187 /* Lookup the current reaching definition for VAR. */
1188 currdef = info->current_def;
1190 /* If there is no reaching definition for VAR, create and register a
1191 default definition for it (if needed). */
1192 if (currdef == NULL_TREE)
1194 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1195 currdef = get_or_create_ssa_default_def (cfun, sym);
1198 /* Return the current reaching definition for VAR, or the default
1199 definition, if we had to create one. */
1200 return currdef;
1204 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1206 static void
1207 rewrite_debug_stmt_uses (gimple stmt)
1209 use_operand_p use_p;
1210 ssa_op_iter iter;
1211 bool update = false;
1213 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1215 tree var = USE_FROM_PTR (use_p), def;
1216 common_info_p info = get_common_info (var);
1217 gcc_checking_assert (DECL_P (var));
1218 def = info->current_def;
1219 if (!def)
1221 if (TREE_CODE (var) == PARM_DECL && single_succ_p (ENTRY_BLOCK_PTR))
1223 gimple_stmt_iterator gsi
1224 = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
1225 int lim;
1226 /* Search a few source bind stmts at the start of first bb to
1227 see if a DEBUG_EXPR_DECL can't be reused. */
1228 for (lim = 32;
1229 !gsi_end_p (gsi) && lim > 0;
1230 gsi_next (&gsi), lim--)
1232 gimple gstmt = gsi_stmt (gsi);
1233 if (!gimple_debug_source_bind_p (gstmt))
1234 break;
1235 if (gimple_debug_source_bind_get_value (gstmt) == var)
1237 def = gimple_debug_source_bind_get_var (gstmt);
1238 if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1239 break;
1240 else
1241 def = NULL_TREE;
1244 /* If not, add a new source bind stmt. */
1245 if (def == NULL_TREE)
1247 gimple def_temp;
1248 def = make_node (DEBUG_EXPR_DECL);
1249 def_temp = gimple_build_debug_source_bind (def, var, NULL);
1250 DECL_ARTIFICIAL (def) = 1;
1251 TREE_TYPE (def) = TREE_TYPE (var);
1252 DECL_MODE (def) = DECL_MODE (var);
1253 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
1254 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1256 update = true;
1259 else
1261 /* Check if info->current_def can be trusted. */
1262 basic_block bb = gimple_bb (stmt);
1263 basic_block def_bb
1264 = SSA_NAME_IS_DEFAULT_DEF (def)
1265 ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1267 /* If definition is in current bb, it is fine. */
1268 if (bb == def_bb)
1270 /* If definition bb doesn't dominate the current bb,
1271 it can't be used. */
1272 else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1273 def = NULL;
1274 /* If there is just one definition and dominates the current
1275 bb, it is fine. */
1276 else if (info->need_phi_state == NEED_PHI_STATE_NO)
1278 else
1280 struct def_blocks_d *db_p = get_def_blocks_for (info);
1282 /* If there are some non-debug uses in the current bb,
1283 it is fine. */
1284 if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1286 /* Otherwise give up for now. */
1287 else
1288 def = NULL;
1291 if (def == NULL)
1293 gimple_debug_bind_reset_value (stmt);
1294 update_stmt (stmt);
1295 return;
1297 SET_USE (use_p, def);
1299 if (update)
1300 update_stmt (stmt);
1303 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1304 the block with its immediate reaching definitions. Update the current
1305 definition of a variable when a new real or virtual definition is found. */
1307 static void
1308 rewrite_stmt (gimple_stmt_iterator *si)
1310 use_operand_p use_p;
1311 def_operand_p def_p;
1312 ssa_op_iter iter;
1313 gimple stmt = gsi_stmt (*si);
1315 /* If mark_def_sites decided that we don't need to rewrite this
1316 statement, ignore it. */
1317 gcc_assert (blocks_to_update == NULL);
1318 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1319 return;
1321 if (dump_file && (dump_flags & TDF_DETAILS))
1323 fprintf (dump_file, "Renaming statement ");
1324 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1325 fprintf (dump_file, "\n");
1328 /* Step 1. Rewrite USES in the statement. */
1329 if (rewrite_uses_p (stmt))
1331 if (is_gimple_debug (stmt))
1332 rewrite_debug_stmt_uses (stmt);
1333 else
1334 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1336 tree var = USE_FROM_PTR (use_p);
1337 gcc_checking_assert (DECL_P (var));
1338 SET_USE (use_p, get_reaching_def (var));
1342 /* Step 2. Register the statement's DEF operands. */
1343 if (register_defs_p (stmt))
1344 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1346 tree var = DEF_FROM_PTR (def_p);
1347 tree name;
1348 tree tracked_var;
1350 gcc_checking_assert (DECL_P (var));
1352 if (gimple_clobber_p (stmt)
1353 && is_gimple_reg (var))
1355 /* If we rewrite a DECL into SSA form then drop its
1356 clobber stmts and replace uses with a new default def. */
1357 gcc_checking_assert (TREE_CODE (var) == VAR_DECL
1358 && !gimple_vdef (stmt));
1359 gsi_replace (si, gimple_build_nop (), true);
1360 register_new_def (get_or_create_ssa_default_def (cfun, var), var);
1361 break;
1364 name = make_ssa_name (var, stmt);
1365 SET_DEF (def_p, name);
1366 register_new_def (DEF_FROM_PTR (def_p), var);
1368 tracked_var = target_for_debug_bind (var);
1369 if (tracked_var)
1371 gimple note = gimple_build_debug_bind (tracked_var, name, stmt);
1372 gsi_insert_after (si, note, GSI_SAME_STMT);
1378 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1379 PHI nodes. For every PHI node found, add a new argument containing the
1380 current reaching definition for the variable and the edge through which
1381 that definition is reaching the PHI node. */
1383 static void
1384 rewrite_add_phi_arguments (basic_block bb)
1386 edge e;
1387 edge_iterator ei;
1389 FOR_EACH_EDGE (e, ei, bb->succs)
1391 gimple phi;
1392 gimple_stmt_iterator gsi;
1394 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1395 gsi_next (&gsi))
1397 tree currdef, res;
1398 location_t loc;
1400 phi = gsi_stmt (gsi);
1401 res = gimple_phi_result (phi);
1402 currdef = get_reaching_def (SSA_NAME_VAR (res));
1403 /* Virtual operand PHI args do not need a location. */
1404 if (virtual_operand_p (res))
1405 loc = UNKNOWN_LOCATION;
1406 else
1407 loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1408 add_phi_arg (phi, currdef, e, loc);
1413 class rewrite_dom_walker : public dom_walker
1415 public:
1416 rewrite_dom_walker (cdi_direction direction) : dom_walker (direction) {}
1418 virtual void before_dom_children (basic_block);
1419 virtual void after_dom_children (basic_block);
1422 /* SSA Rewriting Step 1. Initialization, create a block local stack
1423 of reaching definitions for new SSA names produced in this block
1424 (BLOCK_DEFS). Register new definitions for every PHI node in the
1425 block. */
1427 void
1428 rewrite_dom_walker::before_dom_children (basic_block bb)
1430 gimple_stmt_iterator gsi;
1432 if (dump_file && (dump_flags & TDF_DETAILS))
1433 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1435 /* Mark the unwind point for this block. */
1436 block_defs_stack.safe_push (NULL_TREE);
1438 /* Step 1. Register new definitions for every PHI node in the block.
1439 Conceptually, all the PHI nodes are executed in parallel and each PHI
1440 node introduces a new version for the associated variable. */
1441 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1443 tree result = gimple_phi_result (gsi_stmt (gsi));
1444 register_new_def (result, SSA_NAME_VAR (result));
1447 /* Step 2. Rewrite every variable used in each statement in the block
1448 with its immediate reaching definitions. Update the current definition
1449 of a variable when a new real or virtual definition is found. */
1450 if (bitmap_bit_p (interesting_blocks, bb->index))
1451 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1452 rewrite_stmt (&gsi);
1454 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1455 For every PHI node found, add a new argument containing the current
1456 reaching definition for the variable and the edge through which that
1457 definition is reaching the PHI node. */
1458 rewrite_add_phi_arguments (bb);
1463 /* Called after visiting all the statements in basic block BB and all
1464 of its dominator children. Restore CURRDEFS to its original value. */
1466 void
1467 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1469 /* Restore CURRDEFS to its original state. */
1470 while (block_defs_stack.length () > 0)
1472 tree tmp = block_defs_stack.pop ();
1473 tree saved_def, var;
1475 if (tmp == NULL_TREE)
1476 break;
1478 if (TREE_CODE (tmp) == SSA_NAME)
1480 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1481 current definition of its underlying variable. Note that
1482 if the SSA_NAME is not for a GIMPLE register, the symbol
1483 being defined is stored in the next slot in the stack.
1484 This mechanism is needed because an SSA name for a
1485 non-register symbol may be the definition for more than
1486 one symbol (e.g., SFTs, aliased variables, etc). */
1487 saved_def = tmp;
1488 var = SSA_NAME_VAR (saved_def);
1489 if (!is_gimple_reg (var))
1490 var = block_defs_stack.pop ();
1492 else
1494 /* If we recorded anything else, it must have been a _DECL
1495 node and its current reaching definition must have been
1496 NULL. */
1497 saved_def = NULL;
1498 var = tmp;
1501 get_common_info (var)->current_def = saved_def;
1506 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1508 DEBUG_FUNCTION void
1509 debug_decl_set (bitmap set)
1511 dump_decl_set (stderr, set);
1512 fprintf (stderr, "\n");
1516 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1517 stack up to a maximum of N levels. If N is -1, the whole stack is
1518 dumped. New levels are created when the dominator tree traversal
1519 used for renaming enters a new sub-tree. */
1521 void
1522 dump_defs_stack (FILE *file, int n)
1524 int i, j;
1526 fprintf (file, "\n\nRenaming stack");
1527 if (n > 0)
1528 fprintf (file, " (up to %d levels)", n);
1529 fprintf (file, "\n\n");
1531 i = 1;
1532 fprintf (file, "Level %d (current level)\n", i);
1533 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1535 tree name, var;
1537 name = block_defs_stack[j];
1538 if (name == NULL_TREE)
1540 i++;
1541 if (n > 0 && i > n)
1542 break;
1543 fprintf (file, "\nLevel %d\n", i);
1544 continue;
1547 if (DECL_P (name))
1549 var = name;
1550 name = NULL_TREE;
1552 else
1554 var = SSA_NAME_VAR (name);
1555 if (!is_gimple_reg (var))
1557 j--;
1558 var = block_defs_stack[j];
1562 fprintf (file, " Previous CURRDEF (");
1563 print_generic_expr (file, var, 0);
1564 fprintf (file, ") = ");
1565 if (name)
1566 print_generic_expr (file, name, 0);
1567 else
1568 fprintf (file, "<NIL>");
1569 fprintf (file, "\n");
1574 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1575 stack up to a maximum of N levels. If N is -1, the whole stack is
1576 dumped. New levels are created when the dominator tree traversal
1577 used for renaming enters a new sub-tree. */
1579 DEBUG_FUNCTION void
1580 debug_defs_stack (int n)
1582 dump_defs_stack (stderr, n);
1586 /* Dump the current reaching definition of every symbol to FILE. */
1588 void
1589 dump_currdefs (FILE *file)
1591 unsigned i;
1592 tree var;
1594 if (symbols_to_rename.is_empty ())
1595 return;
1597 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1598 FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1600 common_info_p info = get_common_info (var);
1601 fprintf (file, "CURRDEF (");
1602 print_generic_expr (file, var, 0);
1603 fprintf (file, ") = ");
1604 if (info->current_def)
1605 print_generic_expr (file, info->current_def, 0);
1606 else
1607 fprintf (file, "<NIL>");
1608 fprintf (file, "\n");
1613 /* Dump the current reaching definition of every symbol to stderr. */
1615 DEBUG_FUNCTION void
1616 debug_currdefs (void)
1618 dump_currdefs (stderr);
1622 /* Dump SSA information to FILE. */
1624 void
1625 dump_tree_ssa (FILE *file)
1627 const char *funcname
1628 = lang_hooks.decl_printable_name (current_function_decl, 2);
1630 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1632 dump_var_infos (file);
1633 dump_defs_stack (file, -1);
1634 dump_currdefs (file);
1635 dump_tree_ssa_stats (file);
1639 /* Dump SSA information to stderr. */
1641 DEBUG_FUNCTION void
1642 debug_tree_ssa (void)
1644 dump_tree_ssa (stderr);
1648 /* Dump statistics for the hash table HTAB. */
1650 static void
1651 htab_statistics (FILE *file, hash_table <var_info_hasher> htab)
1653 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1654 (long) htab.size (),
1655 (long) htab.elements (),
1656 htab.collisions ());
1660 /* Dump SSA statistics on FILE. */
1662 void
1663 dump_tree_ssa_stats (FILE *file)
1665 if (var_infos.is_created ())
1667 fprintf (file, "\nHash table statistics:\n");
1668 fprintf (file, " var_infos: ");
1669 htab_statistics (file, var_infos);
1670 fprintf (file, "\n");
1675 /* Dump SSA statistics on stderr. */
1677 DEBUG_FUNCTION void
1678 debug_tree_ssa_stats (void)
1680 dump_tree_ssa_stats (stderr);
1684 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1687 debug_var_infos_r (var_info_d **slot, FILE *file)
1689 struct var_info_d *info = *slot;
1691 fprintf (file, "VAR: ");
1692 print_generic_expr (file, info->var, dump_flags);
1693 bitmap_print (file, info->info.def_blocks.def_blocks,
1694 ", DEF_BLOCKS: { ", "}");
1695 bitmap_print (file, info->info.def_blocks.livein_blocks,
1696 ", LIVEIN_BLOCKS: { ", "}");
1697 bitmap_print (file, info->info.def_blocks.phi_blocks,
1698 ", PHI_BLOCKS: { ", "}\n");
1700 return 1;
1704 /* Dump the VAR_INFOS hash table on FILE. */
1706 void
1707 dump_var_infos (FILE *file)
1709 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1710 if (var_infos.is_created ())
1711 var_infos.traverse <FILE *, debug_var_infos_r> (file);
1715 /* Dump the VAR_INFOS hash table on stderr. */
1717 DEBUG_FUNCTION void
1718 debug_var_infos (void)
1720 dump_var_infos (stderr);
1724 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1726 static inline void
1727 register_new_update_single (tree new_name, tree old_name)
1729 common_info_p info = get_common_info (old_name);
1730 tree currdef = info->current_def;
1732 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1733 This stack is later used by the dominator tree callbacks to
1734 restore the reaching definitions for all the variables
1735 defined in the block after a recursive visit to all its
1736 immediately dominated blocks. */
1737 block_defs_stack.reserve (2);
1738 block_defs_stack.quick_push (currdef);
1739 block_defs_stack.quick_push (old_name);
1741 /* Set the current reaching definition for OLD_NAME to be
1742 NEW_NAME. */
1743 info->current_def = new_name;
1747 /* Register NEW_NAME to be the new reaching definition for all the
1748 names in OLD_NAMES. Used by the incremental SSA update routines to
1749 replace old SSA names with new ones. */
1751 static inline void
1752 register_new_update_set (tree new_name, bitmap old_names)
1754 bitmap_iterator bi;
1755 unsigned i;
1757 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1758 register_new_update_single (new_name, ssa_name (i));
1763 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1764 it is a symbol marked for renaming, replace it with USE_P's current
1765 reaching definition. */
1767 static inline void
1768 maybe_replace_use (use_operand_p use_p)
1770 tree rdef = NULL_TREE;
1771 tree use = USE_FROM_PTR (use_p);
1772 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1774 if (marked_for_renaming (sym))
1775 rdef = get_reaching_def (sym);
1776 else if (is_old_name (use))
1777 rdef = get_reaching_def (use);
1779 if (rdef && rdef != use)
1780 SET_USE (use_p, rdef);
1784 /* Same as maybe_replace_use, but without introducing default stmts,
1785 returning false to indicate a need to do so. */
1787 static inline bool
1788 maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1790 tree rdef = NULL_TREE;
1791 tree use = USE_FROM_PTR (use_p);
1792 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1794 if (marked_for_renaming (sym))
1795 rdef = get_var_info (sym)->info.current_def;
1796 else if (is_old_name (use))
1798 rdef = get_ssa_name_ann (use)->info.current_def;
1799 /* We can't assume that, if there's no current definition, the
1800 default one should be used. It could be the case that we've
1801 rearranged blocks so that the earlier definition no longer
1802 dominates the use. */
1803 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1804 rdef = use;
1806 else
1807 rdef = use;
1809 if (rdef && rdef != use)
1810 SET_USE (use_p, rdef);
1812 return rdef != NULL_TREE;
1816 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1817 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1818 register it as the current definition for the names replaced by
1819 DEF_P. */
1821 static inline void
1822 maybe_register_def (def_operand_p def_p, gimple stmt,
1823 gimple_stmt_iterator gsi)
1825 tree def = DEF_FROM_PTR (def_p);
1826 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1828 /* If DEF is a naked symbol that needs renaming, create a new
1829 name for it. */
1830 if (marked_for_renaming (sym))
1832 if (DECL_P (def))
1834 tree tracked_var;
1836 def = make_ssa_name (def, stmt);
1837 SET_DEF (def_p, def);
1839 tracked_var = target_for_debug_bind (sym);
1840 if (tracked_var)
1842 gimple note = gimple_build_debug_bind (tracked_var, def, stmt);
1843 /* If stmt ends the bb, insert the debug stmt on the single
1844 non-EH edge from the stmt. */
1845 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1847 basic_block bb = gsi_bb (gsi);
1848 edge_iterator ei;
1849 edge e, ef = NULL;
1850 FOR_EACH_EDGE (e, ei, bb->succs)
1851 if (!(e->flags & EDGE_EH))
1853 gcc_checking_assert (!ef);
1854 ef = e;
1856 /* If there are other predecessors to ef->dest, then
1857 there must be PHI nodes for the modified
1858 variable, and therefore there will be debug bind
1859 stmts after the PHI nodes. The debug bind notes
1860 we'd insert would force the creation of a new
1861 block (diverging codegen) and be redundant with
1862 the post-PHI bind stmts, so don't add them.
1864 As for the exit edge, there wouldn't be redundant
1865 bind stmts, but there wouldn't be a PC to bind
1866 them to either, so avoid diverging the CFG. */
1867 if (ef && single_pred_p (ef->dest)
1868 && ef->dest != EXIT_BLOCK_PTR)
1870 /* If there were PHI nodes in the node, we'd
1871 have to make sure the value we're binding
1872 doesn't need rewriting. But there shouldn't
1873 be PHI nodes in a single-predecessor block,
1874 so we just add the note. */
1875 gsi_insert_on_edge_immediate (ef, note);
1878 else
1879 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1883 register_new_update_single (def, sym);
1885 else
1887 /* If DEF is a new name, register it as a new definition
1888 for all the names replaced by DEF. */
1889 if (is_new_name (def))
1890 register_new_update_set (def, names_replaced_by (def));
1892 /* If DEF is an old name, register DEF as a new
1893 definition for itself. */
1894 if (is_old_name (def))
1895 register_new_update_single (def, def);
1900 /* Update every variable used in the statement pointed-to by SI. The
1901 statement is assumed to be in SSA form already. Names in
1902 OLD_SSA_NAMES used by SI will be updated to their current reaching
1903 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1904 will be registered as a new definition for their corresponding name
1905 in OLD_SSA_NAMES. */
1907 static void
1908 rewrite_update_stmt (gimple stmt, gimple_stmt_iterator gsi)
1910 use_operand_p use_p;
1911 def_operand_p def_p;
1912 ssa_op_iter iter;
1914 /* Only update marked statements. */
1915 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1916 return;
1918 if (dump_file && (dump_flags & TDF_DETAILS))
1920 fprintf (dump_file, "Updating SSA information for statement ");
1921 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1924 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1925 symbol is marked for renaming. */
1926 if (rewrite_uses_p (stmt))
1928 if (is_gimple_debug (stmt))
1930 bool failed = false;
1932 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1933 if (!maybe_replace_use_in_debug_stmt (use_p))
1935 failed = true;
1936 break;
1939 if (failed)
1941 /* DOM sometimes threads jumps in such a way that a
1942 debug stmt ends up referencing a SSA variable that no
1943 longer dominates the debug stmt, but such that all
1944 incoming definitions refer to the same definition in
1945 an earlier dominator. We could try to recover that
1946 definition somehow, but this will have to do for now.
1948 Introducing a default definition, which is what
1949 maybe_replace_use() would do in such cases, may
1950 modify code generation, for the otherwise-unused
1951 default definition would never go away, modifying SSA
1952 version numbers all over. */
1953 gimple_debug_bind_reset_value (stmt);
1954 update_stmt (stmt);
1957 else
1959 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1960 maybe_replace_use (use_p);
1964 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1965 Also register definitions for names whose underlying symbol is
1966 marked for renaming. */
1967 if (register_defs_p (stmt))
1968 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1969 maybe_register_def (def_p, stmt, gsi);
1973 /* Visit all the successor blocks of BB looking for PHI nodes. For
1974 every PHI node found, check if any of its arguments is in
1975 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1976 definition, replace it. */
1978 static void
1979 rewrite_update_phi_arguments (basic_block bb)
1981 edge e;
1982 edge_iterator ei;
1983 unsigned i;
1985 FOR_EACH_EDGE (e, ei, bb->succs)
1987 gimple phi;
1988 gimple_vec phis;
1990 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1991 continue;
1993 phis = phis_to_rewrite[e->dest->index];
1994 FOR_EACH_VEC_ELT (phis, i, phi)
1996 tree arg, lhs_sym, reaching_def = NULL;
1997 use_operand_p arg_p;
1999 gcc_checking_assert (rewrite_uses_p (phi));
2001 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2002 arg = USE_FROM_PTR (arg_p);
2004 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2005 continue;
2007 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2009 if (arg == NULL_TREE)
2011 /* When updating a PHI node for a recently introduced
2012 symbol we may find NULL arguments. That's why we
2013 take the symbol from the LHS of the PHI node. */
2014 reaching_def = get_reaching_def (lhs_sym);
2017 else
2019 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2021 if (marked_for_renaming (sym))
2022 reaching_def = get_reaching_def (sym);
2023 else if (is_old_name (arg))
2024 reaching_def = get_reaching_def (arg);
2027 /* Update the argument if there is a reaching def. */
2028 if (reaching_def)
2030 source_location locus;
2031 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2033 SET_USE (arg_p, reaching_def);
2035 /* Virtual operands do not need a location. */
2036 if (virtual_operand_p (reaching_def))
2037 locus = UNKNOWN_LOCATION;
2038 else
2040 gimple stmt = SSA_NAME_DEF_STMT (reaching_def);
2042 /* Single element PHI nodes behave like copies, so get the
2043 location from the phi argument. */
2044 if (gimple_code (stmt) == GIMPLE_PHI
2045 && gimple_phi_num_args (stmt) == 1)
2046 locus = gimple_phi_arg_location (stmt, 0);
2047 else
2048 locus = gimple_location (stmt);
2051 gimple_phi_arg_set_location (phi, arg_i, locus);
2055 if (e->flags & EDGE_ABNORMAL)
2056 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2061 class rewrite_update_dom_walker : public dom_walker
2063 public:
2064 rewrite_update_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2066 virtual void before_dom_children (basic_block);
2067 virtual void after_dom_children (basic_block);
2070 /* Initialization of block data structures for the incremental SSA
2071 update pass. Create a block local stack of reaching definitions
2072 for new SSA names produced in this block (BLOCK_DEFS). Register
2073 new definitions for every PHI node in the block. */
2075 void
2076 rewrite_update_dom_walker::before_dom_children (basic_block bb)
2078 bool is_abnormal_phi;
2079 gimple_stmt_iterator gsi;
2081 if (dump_file && (dump_flags & TDF_DETAILS))
2082 fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2083 bb->index);
2085 /* Mark the unwind point for this block. */
2086 block_defs_stack.safe_push (NULL_TREE);
2088 if (!bitmap_bit_p (blocks_to_update, bb->index))
2089 return;
2091 /* Mark the LHS if any of the arguments flows through an abnormal
2092 edge. */
2093 is_abnormal_phi = bb_has_abnormal_pred (bb);
2095 /* If any of the PHI nodes is a replacement for a name in
2096 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2097 register it as a new definition for its corresponding name. Also
2098 register definitions for names whose underlying symbols are
2099 marked for renaming. */
2100 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2102 tree lhs, lhs_sym;
2103 gimple phi = gsi_stmt (gsi);
2105 if (!register_defs_p (phi))
2106 continue;
2108 lhs = gimple_phi_result (phi);
2109 lhs_sym = SSA_NAME_VAR (lhs);
2111 if (marked_for_renaming (lhs_sym))
2112 register_new_update_single (lhs, lhs_sym);
2113 else
2116 /* If LHS is a new name, register a new definition for all
2117 the names replaced by LHS. */
2118 if (is_new_name (lhs))
2119 register_new_update_set (lhs, names_replaced_by (lhs));
2121 /* If LHS is an OLD name, register it as a new definition
2122 for itself. */
2123 if (is_old_name (lhs))
2124 register_new_update_single (lhs, lhs);
2127 if (is_abnormal_phi)
2128 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2131 /* Step 2. Rewrite every variable used in each statement in the block. */
2132 if (bitmap_bit_p (interesting_blocks, bb->index))
2134 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2135 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2136 rewrite_update_stmt (gsi_stmt (gsi), gsi);
2139 /* Step 3. Update PHI nodes. */
2140 rewrite_update_phi_arguments (bb);
2143 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2144 the current reaching definition of every name re-written in BB to
2145 the original reaching definition before visiting BB. This
2146 unwinding must be done in the opposite order to what is done in
2147 register_new_update_set. */
2149 void
2150 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2152 while (block_defs_stack.length () > 0)
2154 tree var = block_defs_stack.pop ();
2155 tree saved_def;
2157 /* NULL indicates the unwind stop point for this block (see
2158 rewrite_update_enter_block). */
2159 if (var == NULL)
2160 return;
2162 saved_def = block_defs_stack.pop ();
2163 get_common_info (var)->current_def = saved_def;
2168 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2169 form.
2171 ENTRY indicates the block where to start. Every block dominated by
2172 ENTRY will be rewritten.
2174 WHAT indicates what actions will be taken by the renamer (see enum
2175 rewrite_mode).
2177 BLOCKS are the set of interesting blocks for the dominator walker
2178 to process. If this set is NULL, then all the nodes dominated
2179 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2180 are not present in BLOCKS are ignored. */
2182 static void
2183 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2185 /* Rewrite all the basic blocks in the program. */
2186 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2188 block_defs_stack.create (10);
2190 /* Recursively walk the dominator tree rewriting each statement in
2191 each basic block. */
2192 if (what == REWRITE_ALL)
2193 rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2194 else if (what == REWRITE_UPDATE)
2195 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2196 else
2197 gcc_unreachable ();
2199 /* Debugging dumps. */
2200 if (dump_file && (dump_flags & TDF_STATS))
2202 dump_dfa_stats (dump_file);
2203 if (var_infos.is_created ())
2204 dump_tree_ssa_stats (dump_file);
2207 block_defs_stack.release ();
2209 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2212 class mark_def_dom_walker : public dom_walker
2214 public:
2215 mark_def_dom_walker (cdi_direction direction);
2216 ~mark_def_dom_walker ();
2218 virtual void before_dom_children (basic_block);
2220 private:
2221 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2222 large enough to accommodate all the variables referenced in the
2223 function, not just the ones we are renaming. */
2224 bitmap m_kills;
2227 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2228 : dom_walker (direction), m_kills (BITMAP_ALLOC (NULL))
2232 mark_def_dom_walker::~mark_def_dom_walker ()
2234 BITMAP_FREE (m_kills);
2237 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2238 at the start of each block, and call mark_def_sites for each statement. */
2240 void
2241 mark_def_dom_walker::before_dom_children (basic_block bb)
2243 gimple_stmt_iterator gsi;
2245 bitmap_clear (m_kills);
2246 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2247 mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2250 /* Initialize internal data needed during renaming. */
2252 static void
2253 init_ssa_renamer (void)
2255 cfun->gimple_df->in_ssa_p = false;
2257 /* Allocate memory for the DEF_BLOCKS hash table. */
2258 gcc_assert (!var_infos.is_created ());
2259 var_infos.create (vec_safe_length (cfun->local_decls));
2261 bitmap_obstack_initialize (&update_ssa_obstack);
2265 /* Deallocate internal data structures used by the renamer. */
2267 static void
2268 fini_ssa_renamer (void)
2270 if (var_infos.is_created ())
2271 var_infos.dispose ();
2273 bitmap_obstack_release (&update_ssa_obstack);
2275 cfun->gimple_df->ssa_renaming_needed = 0;
2276 cfun->gimple_df->rename_vops = 0;
2277 cfun->gimple_df->in_ssa_p = true;
2280 /* Main entry point into the SSA builder. The renaming process
2281 proceeds in four main phases:
2283 1- Compute dominance frontier and immediate dominators, needed to
2284 insert PHI nodes and rename the function in dominator tree
2285 order.
2287 2- Find and mark all the blocks that define variables.
2289 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2291 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2293 Steps 3 and 4 are done using the dominator tree walker
2294 (walk_dominator_tree). */
2296 static unsigned int
2297 rewrite_into_ssa (void)
2299 bitmap_head *dfs;
2300 basic_block bb;
2301 unsigned i;
2303 /* Initialize operand data structures. */
2304 init_ssa_operands (cfun);
2306 /* Initialize internal data needed by the renamer. */
2307 init_ssa_renamer ();
2309 /* Initialize the set of interesting blocks. The callback
2310 mark_def_sites will add to this set those blocks that the renamer
2311 should process. */
2312 interesting_blocks = sbitmap_alloc (last_basic_block);
2313 bitmap_clear (interesting_blocks);
2315 /* Initialize dominance frontier. */
2316 dfs = XNEWVEC (bitmap_head, last_basic_block);
2317 FOR_EACH_BB (bb)
2318 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2320 /* 1- Compute dominance frontiers. */
2321 calculate_dominance_info (CDI_DOMINATORS);
2322 compute_dominance_frontiers (dfs);
2324 /* 2- Find and mark definition sites. */
2325 mark_def_dom_walker (CDI_DOMINATORS).walk (cfun->cfg->x_entry_block_ptr);
2327 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2328 insert_phi_nodes (dfs);
2330 /* 4- Rename all the blocks. */
2331 rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL);
2333 /* Free allocated memory. */
2334 FOR_EACH_BB (bb)
2335 bitmap_clear (&dfs[bb->index]);
2336 free (dfs);
2338 sbitmap_free (interesting_blocks);
2340 fini_ssa_renamer ();
2342 /* Try to get rid of all gimplifier generated temporaries by making
2343 its SSA names anonymous. This way we can garbage collect them
2344 all after removing unused locals which we do in our TODO. */
2345 for (i = 1; i < num_ssa_names; ++i)
2347 tree decl, name = ssa_name (i);
2348 if (!name
2349 || SSA_NAME_IS_DEFAULT_DEF (name))
2350 continue;
2351 decl = SSA_NAME_VAR (name);
2352 if (decl
2353 && TREE_CODE (decl) == VAR_DECL
2354 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2355 && DECL_IGNORED_P (decl))
2356 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2359 return 0;
2362 /* Gate for IPCP optimization. */
2364 static bool
2365 gate_into_ssa (void)
2367 /* Do nothing for funcions that was produced already in SSA form. */
2368 return !(cfun->curr_properties & PROP_ssa);
2371 namespace {
2373 const pass_data pass_data_build_ssa =
2375 GIMPLE_PASS, /* type */
2376 "ssa", /* name */
2377 OPTGROUP_NONE, /* optinfo_flags */
2378 true, /* has_gate */
2379 true, /* has_execute */
2380 TV_TREE_SSA_OTHER, /* tv_id */
2381 PROP_cfg, /* properties_required */
2382 PROP_ssa, /* properties_provided */
2383 0, /* properties_destroyed */
2384 0, /* todo_flags_start */
2385 ( TODO_verify_ssa | TODO_remove_unused_locals ), /* todo_flags_finish */
2388 class pass_build_ssa : public gimple_opt_pass
2390 public:
2391 pass_build_ssa (gcc::context *ctxt)
2392 : gimple_opt_pass (pass_data_build_ssa, ctxt)
2395 /* opt_pass methods: */
2396 bool gate () { return gate_into_ssa (); }
2397 unsigned int execute () { return rewrite_into_ssa (); }
2399 }; // class pass_build_ssa
2401 } // anon namespace
2403 gimple_opt_pass *
2404 make_pass_build_ssa (gcc::context *ctxt)
2406 return new pass_build_ssa (ctxt);
2410 /* Mark the definition of VAR at STMT and BB as interesting for the
2411 renamer. BLOCKS is the set of blocks that need updating. */
2413 static void
2414 mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2416 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2417 set_register_defs (stmt, true);
2419 if (insert_phi_p)
2421 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2423 set_def_block (var, bb, is_phi_p);
2425 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2426 site for both itself and all the old names replaced by it. */
2427 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2429 bitmap_iterator bi;
2430 unsigned i;
2431 bitmap set = names_replaced_by (var);
2432 if (set)
2433 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2434 set_def_block (ssa_name (i), bb, is_phi_p);
2440 /* Mark the use of VAR at STMT and BB as interesting for the
2441 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2442 nodes. */
2444 static inline void
2445 mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2447 basic_block def_bb = gimple_bb (stmt);
2449 mark_block_for_update (def_bb);
2450 mark_block_for_update (bb);
2452 if (gimple_code (stmt) == GIMPLE_PHI)
2453 mark_phi_for_rewrite (def_bb, stmt);
2454 else
2456 set_rewrite_uses (stmt, true);
2458 if (is_gimple_debug (stmt))
2459 return;
2462 /* If VAR has not been defined in BB, then it is live-on-entry
2463 to BB. Note that we cannot just use the block holding VAR's
2464 definition because if VAR is one of the names in OLD_SSA_NAMES,
2465 it will have several definitions (itself and all the names that
2466 replace it). */
2467 if (insert_phi_p)
2469 struct def_blocks_d *db_p = get_def_blocks_for (get_common_info (var));
2470 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2471 set_livein_block (var, bb);
2476 /* Do a dominator walk starting at BB processing statements that
2477 reference symbols in SSA operands. This is very similar to
2478 mark_def_sites, but the scan handles statements whose operands may
2479 already be SSA names.
2481 If INSERT_PHI_P is true, mark those uses as live in the
2482 corresponding block. This is later used by the PHI placement
2483 algorithm to make PHI pruning decisions.
2485 FIXME. Most of this would be unnecessary if we could associate a
2486 symbol to all the SSA names that reference it. But that
2487 sounds like it would be expensive to maintain. Still, it
2488 would be interesting to see if it makes better sense to do
2489 that. */
2491 static void
2492 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2494 basic_block son;
2495 gimple_stmt_iterator si;
2496 edge e;
2497 edge_iterator ei;
2499 mark_block_for_update (bb);
2501 /* Process PHI nodes marking interesting those that define or use
2502 the symbols that we are interested in. */
2503 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
2505 gimple phi = gsi_stmt (si);
2506 tree lhs_sym, lhs = gimple_phi_result (phi);
2508 if (TREE_CODE (lhs) == SSA_NAME
2509 && (! virtual_operand_p (lhs)
2510 || ! cfun->gimple_df->rename_vops))
2511 continue;
2513 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2514 mark_for_renaming (lhs_sym);
2515 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2517 /* Mark the uses in phi nodes as interesting. It would be more correct
2518 to process the arguments of the phi nodes of the successor edges of
2519 BB at the end of prepare_block_for_update, however, that turns out
2520 to be significantly more expensive. Doing it here is conservatively
2521 correct -- it may only cause us to believe a value to be live in a
2522 block that also contains its definition, and thus insert a few more
2523 phi nodes for it. */
2524 FOR_EACH_EDGE (e, ei, bb->preds)
2525 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2528 /* Process the statements. */
2529 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2531 gimple stmt;
2532 ssa_op_iter i;
2533 use_operand_p use_p;
2534 def_operand_p def_p;
2536 stmt = gsi_stmt (si);
2538 if (cfun->gimple_df->rename_vops
2539 && gimple_vuse (stmt))
2541 tree use = gimple_vuse (stmt);
2542 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2543 mark_for_renaming (sym);
2544 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2547 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2549 tree use = USE_FROM_PTR (use_p);
2550 if (!DECL_P (use))
2551 continue;
2552 mark_for_renaming (use);
2553 mark_use_interesting (use, stmt, bb, insert_phi_p);
2556 if (cfun->gimple_df->rename_vops
2557 && gimple_vdef (stmt))
2559 tree def = gimple_vdef (stmt);
2560 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2561 mark_for_renaming (sym);
2562 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2565 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2567 tree def = DEF_FROM_PTR (def_p);
2568 if (!DECL_P (def))
2569 continue;
2570 mark_for_renaming (def);
2571 mark_def_interesting (def, stmt, bb, insert_phi_p);
2575 /* Now visit all the blocks dominated by BB. */
2576 for (son = first_dom_son (CDI_DOMINATORS, bb);
2577 son;
2578 son = next_dom_son (CDI_DOMINATORS, son))
2579 prepare_block_for_update (son, insert_phi_p);
2583 /* Helper for prepare_names_to_update. Mark all the use sites for
2584 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2585 prepare_names_to_update. */
2587 static void
2588 prepare_use_sites_for (tree name, bool insert_phi_p)
2590 use_operand_p use_p;
2591 imm_use_iterator iter;
2593 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2595 gimple stmt = USE_STMT (use_p);
2596 basic_block bb = gimple_bb (stmt);
2598 if (gimple_code (stmt) == GIMPLE_PHI)
2600 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2601 edge e = gimple_phi_arg_edge (stmt, ix);
2602 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2604 else
2606 /* For regular statements, mark this as an interesting use
2607 for NAME. */
2608 mark_use_interesting (name, stmt, bb, insert_phi_p);
2614 /* Helper for prepare_names_to_update. Mark the definition site for
2615 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2616 prepare_names_to_update. */
2618 static void
2619 prepare_def_site_for (tree name, bool insert_phi_p)
2621 gimple stmt;
2622 basic_block bb;
2624 gcc_checking_assert (names_to_release == NULL
2625 || !bitmap_bit_p (names_to_release,
2626 SSA_NAME_VERSION (name)));
2628 stmt = SSA_NAME_DEF_STMT (name);
2629 bb = gimple_bb (stmt);
2630 if (bb)
2632 gcc_checking_assert (bb->index < last_basic_block);
2633 mark_block_for_update (bb);
2634 mark_def_interesting (name, stmt, bb, insert_phi_p);
2639 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2640 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2641 PHI nodes for newly created names. */
2643 static void
2644 prepare_names_to_update (bool insert_phi_p)
2646 unsigned i = 0;
2647 bitmap_iterator bi;
2648 sbitmap_iterator sbi;
2650 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2651 remove it from NEW_SSA_NAMES so that we don't try to visit its
2652 defining basic block (which most likely doesn't exist). Notice
2653 that we cannot do the same with names in OLD_SSA_NAMES because we
2654 want to replace existing instances. */
2655 if (names_to_release)
2656 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2657 bitmap_clear_bit (new_ssa_names, i);
2659 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2660 names may be considered to be live-in on blocks that contain
2661 definitions for their replacements. */
2662 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2663 prepare_def_site_for (ssa_name (i), insert_phi_p);
2665 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2666 OLD_SSA_NAMES, but we have to ignore its definition site. */
2667 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2669 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2670 prepare_def_site_for (ssa_name (i), insert_phi_p);
2671 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2676 /* Dump all the names replaced by NAME to FILE. */
2678 void
2679 dump_names_replaced_by (FILE *file, tree name)
2681 unsigned i;
2682 bitmap old_set;
2683 bitmap_iterator bi;
2685 print_generic_expr (file, name, 0);
2686 fprintf (file, " -> { ");
2688 old_set = names_replaced_by (name);
2689 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2691 print_generic_expr (file, ssa_name (i), 0);
2692 fprintf (file, " ");
2695 fprintf (file, "}\n");
2699 /* Dump all the names replaced by NAME to stderr. */
2701 DEBUG_FUNCTION void
2702 debug_names_replaced_by (tree name)
2704 dump_names_replaced_by (stderr, name);
2708 /* Dump SSA update information to FILE. */
2710 void
2711 dump_update_ssa (FILE *file)
2713 unsigned i = 0;
2714 bitmap_iterator bi;
2716 if (!need_ssa_update_p (cfun))
2717 return;
2719 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2721 sbitmap_iterator sbi;
2723 fprintf (file, "\nSSA replacement table\n");
2724 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2725 "O_1, ..., O_j\n\n");
2727 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2728 dump_names_replaced_by (file, ssa_name (i));
2731 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2733 fprintf (file, "\nSymbols to be put in SSA form\n");
2734 dump_decl_set (file, symbols_to_rename_set);
2735 fprintf (file, "\n");
2738 if (names_to_release && !bitmap_empty_p (names_to_release))
2740 fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2741 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2743 print_generic_expr (file, ssa_name (i), 0);
2744 fprintf (file, " ");
2746 fprintf (file, "\n");
2751 /* Dump SSA update information to stderr. */
2753 DEBUG_FUNCTION void
2754 debug_update_ssa (void)
2756 dump_update_ssa (stderr);
2760 /* Initialize data structures used for incremental SSA updates. */
2762 static void
2763 init_update_ssa (struct function *fn)
2765 /* Reserve more space than the current number of names. The calls to
2766 add_new_name_mapping are typically done after creating new SSA
2767 names, so we'll need to reallocate these arrays. */
2768 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2769 bitmap_clear (old_ssa_names);
2771 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2772 bitmap_clear (new_ssa_names);
2774 bitmap_obstack_initialize (&update_ssa_obstack);
2776 names_to_release = NULL;
2777 update_ssa_initialized_fn = fn;
2781 /* Deallocate data structures used for incremental SSA updates. */
2783 void
2784 delete_update_ssa (void)
2786 unsigned i;
2787 bitmap_iterator bi;
2789 sbitmap_free (old_ssa_names);
2790 old_ssa_names = NULL;
2792 sbitmap_free (new_ssa_names);
2793 new_ssa_names = NULL;
2795 BITMAP_FREE (symbols_to_rename_set);
2796 symbols_to_rename_set = NULL;
2797 symbols_to_rename.release ();
2799 if (names_to_release)
2801 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2802 release_ssa_name (ssa_name (i));
2803 BITMAP_FREE (names_to_release);
2806 clear_ssa_name_info ();
2808 fini_ssa_renamer ();
2810 if (blocks_with_phis_to_rewrite)
2811 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2813 gimple_vec phis = phis_to_rewrite[i];
2814 phis.release ();
2815 phis_to_rewrite[i].create (0);
2818 BITMAP_FREE (blocks_with_phis_to_rewrite);
2819 BITMAP_FREE (blocks_to_update);
2821 update_ssa_initialized_fn = NULL;
2825 /* Create a new name for OLD_NAME in statement STMT and replace the
2826 operand pointed to by DEF_P with the newly created name. If DEF_P
2827 is NULL then STMT should be a GIMPLE assignment.
2828 Return the new name and register the replacement mapping <NEW, OLD> in
2829 update_ssa's tables. */
2831 tree
2832 create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
2834 tree new_name;
2836 timevar_push (TV_TREE_SSA_INCREMENTAL);
2838 if (!update_ssa_initialized_fn)
2839 init_update_ssa (cfun);
2841 gcc_assert (update_ssa_initialized_fn == cfun);
2843 new_name = duplicate_ssa_name (old_name, stmt);
2844 if (def)
2845 SET_DEF (def, new_name);
2846 else
2847 gimple_assign_set_lhs (stmt, new_name);
2849 if (gimple_code (stmt) == GIMPLE_PHI)
2851 basic_block bb = gimple_bb (stmt);
2853 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2854 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2857 add_new_name_mapping (new_name, old_name);
2859 /* For the benefit of passes that will be updating the SSA form on
2860 their own, set the current reaching definition of OLD_NAME to be
2861 NEW_NAME. */
2862 get_ssa_name_ann (old_name)->info.current_def = new_name;
2864 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2866 return new_name;
2870 /* Mark virtual operands of FN for renaming by update_ssa. */
2872 void
2873 mark_virtual_operands_for_renaming (struct function *fn)
2875 fn->gimple_df->ssa_renaming_needed = 1;
2876 fn->gimple_df->rename_vops = 1;
2879 /* Replace all uses of NAME by underlying variable and mark it
2880 for renaming. This assumes the defining statement of NAME is
2881 going to be removed. */
2883 void
2884 mark_virtual_operand_for_renaming (tree name)
2886 tree name_var = SSA_NAME_VAR (name);
2887 bool used = false;
2888 imm_use_iterator iter;
2889 use_operand_p use_p;
2890 gimple stmt;
2892 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
2893 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
2895 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2896 SET_USE (use_p, name_var);
2897 used = true;
2899 if (used)
2900 mark_virtual_operands_for_renaming (cfun);
2903 /* Replace all uses of the virtual PHI result by its underlying variable
2904 and mark it for renaming. This assumes the PHI node is going to be
2905 removed. */
2907 void
2908 mark_virtual_phi_result_for_renaming (gimple phi)
2910 if (dump_file && (dump_flags & TDF_DETAILS))
2912 fprintf (dump_file, "Marking result for renaming : ");
2913 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
2914 fprintf (dump_file, "\n");
2917 mark_virtual_operand_for_renaming (gimple_phi_result (phi));
2920 /* Return true if there is any work to be done by update_ssa
2921 for function FN. */
2923 bool
2924 need_ssa_update_p (struct function *fn)
2926 gcc_assert (fn != NULL);
2927 return (update_ssa_initialized_fn == fn
2928 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
2931 /* Return true if name N has been registered in the replacement table. */
2933 bool
2934 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
2936 if (!update_ssa_initialized_fn)
2937 return false;
2939 gcc_assert (update_ssa_initialized_fn == cfun);
2941 return is_new_name (n) || is_old_name (n);
2945 /* Mark NAME to be released after update_ssa has finished. */
2947 void
2948 release_ssa_name_after_update_ssa (tree name)
2950 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
2952 if (names_to_release == NULL)
2953 names_to_release = BITMAP_ALLOC (NULL);
2955 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2959 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2960 frontier information. BLOCKS is the set of blocks to be updated.
2962 This is slightly different than the regular PHI insertion
2963 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2964 real names (i.e., GIMPLE registers) are inserted:
2966 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2967 nodes inside the region affected by the block that defines VAR
2968 and the blocks that define all its replacements. All these
2969 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2971 First, we compute the entry point to the region (ENTRY). This is
2972 given by the nearest common dominator to all the definition
2973 blocks. When computing the iterated dominance frontier (IDF), any
2974 block not strictly dominated by ENTRY is ignored.
2976 We then call the standard PHI insertion algorithm with the pruned
2977 IDF.
2979 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2980 names is not pruned. PHI nodes are inserted at every IDF block. */
2982 static void
2983 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
2984 unsigned update_flags)
2986 basic_block entry;
2987 struct def_blocks_d *db;
2988 bitmap idf, pruned_idf;
2989 bitmap_iterator bi;
2990 unsigned i;
2992 if (TREE_CODE (var) == SSA_NAME)
2993 gcc_checking_assert (is_old_name (var));
2994 else
2995 gcc_checking_assert (marked_for_renaming (var));
2997 /* Get all the definition sites for VAR. */
2998 db = find_def_blocks_for (var);
3000 /* No need to do anything if there were no definitions to VAR. */
3001 if (db == NULL || bitmap_empty_p (db->def_blocks))
3002 return;
3004 /* Compute the initial iterated dominance frontier. */
3005 idf = compute_idf (db->def_blocks, dfs);
3006 pruned_idf = BITMAP_ALLOC (NULL);
3008 if (TREE_CODE (var) == SSA_NAME)
3010 if (update_flags == TODO_update_ssa)
3012 /* If doing regular SSA updates for GIMPLE registers, we are
3013 only interested in IDF blocks dominated by the nearest
3014 common dominator of all the definition blocks. */
3015 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3016 db->def_blocks);
3017 if (entry != ENTRY_BLOCK_PTR)
3018 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3019 if (BASIC_BLOCK (i) != entry
3020 && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
3021 bitmap_set_bit (pruned_idf, i);
3023 else
3025 /* Otherwise, do not prune the IDF for VAR. */
3026 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3027 bitmap_copy (pruned_idf, idf);
3030 else
3032 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3033 for the first time, so we need to compute the full IDF for
3034 it. */
3035 bitmap_copy (pruned_idf, idf);
3038 if (!bitmap_empty_p (pruned_idf))
3040 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3041 are included in the region to be updated. The feeding blocks
3042 are important to guarantee that the PHI arguments are renamed
3043 properly. */
3045 /* FIXME, this is not needed if we are updating symbols. We are
3046 already starting at the ENTRY block anyway. */
3047 bitmap_ior_into (blocks, pruned_idf);
3048 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3050 edge e;
3051 edge_iterator ei;
3052 basic_block bb = BASIC_BLOCK (i);
3054 FOR_EACH_EDGE (e, ei, bb->preds)
3055 if (e->src->index >= 0)
3056 bitmap_set_bit (blocks, e->src->index);
3059 insert_phi_nodes_for (var, pruned_idf, true);
3062 BITMAP_FREE (pruned_idf);
3063 BITMAP_FREE (idf);
3066 /* Sort symbols_to_rename after their DECL_UID. */
3068 static int
3069 insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3071 const_tree syma = *(const const_tree *)a;
3072 const_tree symb = *(const const_tree *)b;
3073 if (DECL_UID (syma) == DECL_UID (symb))
3074 return 0;
3075 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3078 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3079 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3081 1- The names in OLD_SSA_NAMES dominated by the definitions of
3082 NEW_SSA_NAMES are all re-written to be reached by the
3083 appropriate definition from NEW_SSA_NAMES.
3085 2- If needed, new PHI nodes are added to the iterated dominance
3086 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3088 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3089 calling create_new_def_for to create new defs for names that the
3090 caller wants to replace.
3092 The caller cretaes the new names to be inserted and the names that need
3093 to be replaced by calling create_new_def_for for each old definition
3094 to be replaced. Note that the function assumes that the
3095 new defining statement has already been inserted in the IL.
3097 For instance, given the following code:
3099 1 L0:
3100 2 x_1 = PHI (0, x_5)
3101 3 if (x_1 < 10)
3102 4 if (x_1 > 7)
3103 5 y_2 = 0
3104 6 else
3105 7 y_3 = x_1 + x_7
3106 8 endif
3107 9 x_5 = x_1 + 1
3108 10 goto L0;
3109 11 endif
3111 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3113 1 L0:
3114 2 x_1 = PHI (0, x_5)
3115 3 if (x_1 < 10)
3116 4 x_10 = ...
3117 5 if (x_1 > 7)
3118 6 y_2 = 0
3119 7 else
3120 8 x_11 = ...
3121 9 y_3 = x_1 + x_7
3122 10 endif
3123 11 x_5 = x_1 + 1
3124 12 goto L0;
3125 13 endif
3127 We want to replace all the uses of x_1 with the new definitions of
3128 x_10 and x_11. Note that the only uses that should be replaced are
3129 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3130 *not* be replaced (this is why we cannot just mark symbol 'x' for
3131 renaming).
3133 Additionally, we may need to insert a PHI node at line 11 because
3134 that is a merge point for x_10 and x_11. So the use of x_1 at line
3135 11 will be replaced with the new PHI node. The insertion of PHI
3136 nodes is optional. They are not strictly necessary to preserve the
3137 SSA form, and depending on what the caller inserted, they may not
3138 even be useful for the optimizers. UPDATE_FLAGS controls various
3139 aspects of how update_ssa operates, see the documentation for
3140 TODO_update_ssa*. */
3142 void
3143 update_ssa (unsigned update_flags)
3145 basic_block bb, start_bb;
3146 bitmap_iterator bi;
3147 unsigned i = 0;
3148 bool insert_phi_p;
3149 sbitmap_iterator sbi;
3150 tree sym;
3152 /* Only one update flag should be set. */
3153 gcc_assert (update_flags == TODO_update_ssa
3154 || update_flags == TODO_update_ssa_no_phi
3155 || update_flags == TODO_update_ssa_full_phi
3156 || update_flags == TODO_update_ssa_only_virtuals);
3158 if (!need_ssa_update_p (cfun))
3159 return;
3161 timevar_push (TV_TREE_SSA_INCREMENTAL);
3163 if (dump_file && (dump_flags & TDF_DETAILS))
3164 fprintf (dump_file, "\nUpdating SSA:\n");
3166 if (!update_ssa_initialized_fn)
3167 init_update_ssa (cfun);
3168 else if (update_flags == TODO_update_ssa_only_virtuals)
3170 /* If we only need to update virtuals, remove all the mappings for
3171 real names before proceeding. The caller is responsible for
3172 having dealt with the name mappings before calling update_ssa. */
3173 bitmap_clear (old_ssa_names);
3174 bitmap_clear (new_ssa_names);
3177 gcc_assert (update_ssa_initialized_fn == cfun);
3179 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3180 if (!phis_to_rewrite.exists ())
3181 phis_to_rewrite.create (last_basic_block + 1);
3182 blocks_to_update = BITMAP_ALLOC (NULL);
3184 /* Ensure that the dominance information is up-to-date. */
3185 calculate_dominance_info (CDI_DOMINATORS);
3187 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3189 /* If there are names defined in the replacement table, prepare
3190 definition and use sites for all the names in NEW_SSA_NAMES and
3191 OLD_SSA_NAMES. */
3192 if (bitmap_first_set_bit (new_ssa_names) >= 0)
3194 prepare_names_to_update (insert_phi_p);
3196 /* If all the names in NEW_SSA_NAMES had been marked for
3197 removal, and there are no symbols to rename, then there's
3198 nothing else to do. */
3199 if (bitmap_first_set_bit (new_ssa_names) < 0
3200 && !cfun->gimple_df->ssa_renaming_needed)
3201 goto done;
3204 /* Next, determine the block at which to start the renaming process. */
3205 if (cfun->gimple_df->ssa_renaming_needed)
3207 /* If we rename bare symbols initialize the mapping to
3208 auxiliar info we need to keep track of. */
3209 var_infos.create (47);
3211 /* If we have to rename some symbols from scratch, we need to
3212 start the process at the root of the CFG. FIXME, it should
3213 be possible to determine the nearest block that had a
3214 definition for each of the symbols that are marked for
3215 updating. For now this seems more work than it's worth. */
3216 start_bb = ENTRY_BLOCK_PTR;
3218 /* Traverse the CFG looking for existing definitions and uses of
3219 symbols in SSA operands. Mark interesting blocks and
3220 statements and set local live-in information for the PHI
3221 placement heuristics. */
3222 prepare_block_for_update (start_bb, insert_phi_p);
3224 #ifdef ENABLE_CHECKING
3225 for (i = 1; i < num_ssa_names; ++i)
3227 tree name = ssa_name (i);
3228 if (!name
3229 || virtual_operand_p (name))
3230 continue;
3232 /* For all but virtual operands, which do not have SSA names
3233 with overlapping life ranges, ensure that symbols marked
3234 for renaming do not have existing SSA names associated with
3235 them as we do not re-write them out-of-SSA before going
3236 into SSA for the remaining symbol uses. */
3237 if (marked_for_renaming (SSA_NAME_VAR (name)))
3239 fprintf (stderr, "Existing SSA name for symbol marked for "
3240 "renaming: ");
3241 print_generic_expr (stderr, name, TDF_SLIM);
3242 fprintf (stderr, "\n");
3243 internal_error ("SSA corruption");
3246 #endif
3248 else
3250 /* Otherwise, the entry block to the region is the nearest
3251 common dominator for the blocks in BLOCKS. */
3252 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3253 blocks_to_update);
3256 /* If requested, insert PHI nodes at the iterated dominance frontier
3257 of every block, creating new definitions for names in OLD_SSA_NAMES
3258 and for symbols found. */
3259 if (insert_phi_p)
3261 bitmap_head *dfs;
3263 /* If the caller requested PHI nodes to be added, compute
3264 dominance frontiers. */
3265 dfs = XNEWVEC (bitmap_head, last_basic_block);
3266 FOR_EACH_BB (bb)
3267 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3268 compute_dominance_frontiers (dfs);
3270 if (bitmap_first_set_bit (old_ssa_names) >= 0)
3272 sbitmap_iterator sbi;
3274 /* insert_update_phi_nodes_for will call add_new_name_mapping
3275 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3276 will grow while we are traversing it (but it will not
3277 gain any new members). Copy OLD_SSA_NAMES to a temporary
3278 for traversal. */
3279 sbitmap tmp = sbitmap_alloc (SBITMAP_SIZE (old_ssa_names));
3280 bitmap_copy (tmp, old_ssa_names);
3281 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3282 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3283 update_flags);
3284 sbitmap_free (tmp);
3287 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3288 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3289 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3290 update_flags);
3292 FOR_EACH_BB (bb)
3293 bitmap_clear (&dfs[bb->index]);
3294 free (dfs);
3296 /* Insertion of PHI nodes may have added blocks to the region.
3297 We need to re-compute START_BB to include the newly added
3298 blocks. */
3299 if (start_bb != ENTRY_BLOCK_PTR)
3300 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3301 blocks_to_update);
3304 /* Reset the current definition for name and symbol before renaming
3305 the sub-graph. */
3306 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3307 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3309 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3310 get_var_info (sym)->info.current_def = NULL_TREE;
3312 /* Now start the renaming process at START_BB. */
3313 interesting_blocks = sbitmap_alloc (last_basic_block);
3314 bitmap_clear (interesting_blocks);
3315 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3316 bitmap_set_bit (interesting_blocks, i);
3318 rewrite_blocks (start_bb, REWRITE_UPDATE);
3320 sbitmap_free (interesting_blocks);
3322 /* Debugging dumps. */
3323 if (dump_file)
3325 int c;
3326 unsigned i;
3328 dump_update_ssa (dump_file);
3330 fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3331 start_bb->index);
3333 c = 0;
3334 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3335 c++;
3336 fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
3337 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3338 c, PERCENT (c, last_basic_block));
3340 if (dump_flags & TDF_DETAILS)
3342 fprintf (dump_file, "Affected blocks:");
3343 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3344 fprintf (dump_file, " %u", i);
3345 fprintf (dump_file, "\n");
3348 fprintf (dump_file, "\n\n");
3351 /* Free allocated memory. */
3352 done:
3353 delete_update_ssa ();
3355 timevar_pop (TV_TREE_SSA_INCREMENTAL);