Daily bump.
[official-gcc.git] / gcc / tree-into-ssa.c
blob3ca2bd10bcf9dea0b2a8fc68daceaf9e775d9f72
1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2014 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 "hash-table.h"
33 #include "tree-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-expr.h"
36 #include "is-a.h"
37 #include "gimple.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
40 #include "tree-cfg.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "tree-into-ssa.h"
46 #include "expr.h"
47 #include "tree-dfa.h"
48 #include "tree-ssa.h"
49 #include "tree-inline.h"
50 #include "tree-pass.h"
51 #include "cfgloop.h"
52 #include "domwalk.h"
53 #include "params.h"
54 #include "diagnostic-core.h"
55 #include "tree-into-ssa.h"
57 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
59 /* This file builds the SSA form for a function as described in:
60 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
61 Computing Static Single Assignment Form and the Control Dependence
62 Graph. ACM Transactions on Programming Languages and Systems,
63 13(4):451-490, October 1991. */
65 /* Structure to map a variable VAR to the set of blocks that contain
66 definitions for VAR. */
67 struct def_blocks_d
69 /* Blocks that contain definitions of VAR. Bit I will be set if the
70 Ith block contains a definition of VAR. */
71 bitmap def_blocks;
73 /* Blocks that contain a PHI node for VAR. */
74 bitmap phi_blocks;
76 /* Blocks where VAR is live-on-entry. Similar semantics as
77 DEF_BLOCKS. */
78 bitmap livein_blocks;
81 typedef struct def_blocks_d *def_blocks_p;
84 /* Stack of trees used to restore the global currdefs to its original
85 state after completing rewriting of a block and its dominator
86 children. Its elements have the following properties:
88 - An SSA_NAME (N) indicates that the current definition of the
89 underlying variable should be set to the given SSA_NAME. If the
90 symbol associated with the SSA_NAME is not a GIMPLE register, the
91 next slot in the stack must be a _DECL node (SYM). In this case,
92 the name N in the previous slot is the current reaching
93 definition for SYM.
95 - A _DECL node indicates that the underlying variable has no
96 current definition.
98 - A NULL node at the top entry is used to mark the last slot
99 associated with the current block. */
100 static vec<tree> block_defs_stack;
103 /* Set of existing SSA names being replaced by update_ssa. */
104 static sbitmap old_ssa_names;
106 /* Set of new SSA names being added by update_ssa. Note that both
107 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
108 the operations done on them are presence tests. */
109 static sbitmap new_ssa_names;
111 static sbitmap interesting_blocks;
113 /* Set of SSA names that have been marked to be released after they
114 were registered in the replacement table. They will be finally
115 released after we finish updating the SSA web. */
116 static bitmap names_to_release;
118 /* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
119 the to basic block with index I. Allocated once per compilation, *not*
120 released between different functions. */
121 static vec<gimple_vec> phis_to_rewrite;
123 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
124 static bitmap blocks_with_phis_to_rewrite;
126 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
127 to grow as the callers to create_new_def_for will create new names on
128 the fly.
129 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
130 need to find a reasonable growth strategy. */
131 #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
134 /* The function the SSA updating data structures have been initialized for.
135 NULL if they need to be initialized by create_new_def_for. */
136 static struct function *update_ssa_initialized_fn = NULL;
138 /* Global data to attach to the main dominator walk structure. */
139 struct mark_def_sites_global_data
141 /* This bitmap contains the variables which are set before they
142 are used in a basic block. */
143 bitmap kills;
146 /* It is advantageous to avoid things like life analysis for variables which
147 do not need PHI nodes. This enum describes whether or not a particular
148 variable may need a PHI node. */
150 enum need_phi_state {
151 /* This is the default. If we are still in this state after finding
152 all the definition and use sites, then we will assume the variable
153 needs PHI nodes. This is probably an overly conservative assumption. */
154 NEED_PHI_STATE_UNKNOWN,
156 /* This state indicates that we have seen one or more sets of the
157 variable in a single basic block and that the sets dominate all
158 uses seen so far. If after finding all definition and use sites
159 we are still in this state, then the variable does not need any
160 PHI nodes. */
161 NEED_PHI_STATE_NO,
163 /* This state indicates that we have either seen multiple definitions of
164 the variable in multiple blocks, or that we encountered a use in a
165 block that was not dominated by the block containing the set(s) of
166 this variable. This variable is assumed to need PHI nodes. */
167 NEED_PHI_STATE_MAYBE
170 /* Information stored for both SSA names and decls. */
171 struct common_info_d
173 /* This field indicates whether or not the variable may need PHI nodes.
174 See the enum's definition for more detailed information about the
175 states. */
176 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
178 /* The current reaching definition replacing this var. */
179 tree current_def;
181 /* Definitions for this var. */
182 struct def_blocks_d def_blocks;
185 /* The information associated with decls and SSA names. */
186 typedef struct common_info_d *common_info_p;
188 /* Information stored for decls. */
189 struct var_info_d
191 /* The variable. */
192 tree var;
194 /* Information stored for both SSA names and decls. */
195 struct common_info_d info;
198 /* The information associated with decls. */
199 typedef struct var_info_d *var_info_p;
202 /* VAR_INFOS hashtable helpers. */
204 struct var_info_hasher : typed_free_remove <var_info_d>
206 typedef var_info_d value_type;
207 typedef var_info_d compare_type;
208 static inline hashval_t hash (const value_type *);
209 static inline bool equal (const value_type *, const compare_type *);
212 inline hashval_t
213 var_info_hasher::hash (const value_type *p)
215 return DECL_UID (p->var);
218 inline bool
219 var_info_hasher::equal (const value_type *p1, const compare_type *p2)
221 return p1->var == p2->var;
225 /* Each entry in VAR_INFOS contains an element of type STRUCT
226 VAR_INFO_D. */
227 static hash_table <var_info_hasher> var_infos;
230 /* Information stored for SSA names. */
231 struct ssa_name_info
233 /* Age of this record (so that info_for_ssa_name table can be cleared
234 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
235 are assumed to be null. */
236 unsigned age;
238 /* Replacement mappings, allocated from update_ssa_obstack. */
239 bitmap repl_set;
241 /* Information stored for both SSA names and decls. */
242 struct common_info_d info;
245 /* The information associated with names. */
246 typedef struct ssa_name_info *ssa_name_info_p;
248 static vec<ssa_name_info_p> info_for_ssa_name;
249 static unsigned current_info_for_ssa_name_age;
251 static bitmap_obstack update_ssa_obstack;
253 /* The set of blocks affected by update_ssa. */
254 static bitmap blocks_to_update;
256 /* The main entry point to the SSA renamer (rewrite_blocks) may be
257 called several times to do different, but related, tasks.
258 Initially, we need it to rename the whole program into SSA form.
259 At other times, we may need it to only rename into SSA newly
260 exposed symbols. Finally, we can also call it to incrementally fix
261 an already built SSA web. */
262 enum rewrite_mode {
263 /* Convert the whole function into SSA form. */
264 REWRITE_ALL,
266 /* Incrementally update the SSA web by replacing existing SSA
267 names with new ones. See update_ssa for details. */
268 REWRITE_UPDATE
271 /* The set of symbols we ought to re-write into SSA form in update_ssa. */
272 static bitmap symbols_to_rename_set;
273 static vec<tree> symbols_to_rename;
275 /* Mark SYM for renaming. */
277 static void
278 mark_for_renaming (tree sym)
280 if (!symbols_to_rename_set)
281 symbols_to_rename_set = BITMAP_ALLOC (NULL);
282 if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
283 symbols_to_rename.safe_push (sym);
286 /* Return true if SYM is marked for renaming. */
288 static bool
289 marked_for_renaming (tree sym)
291 if (!symbols_to_rename_set || sym == NULL_TREE)
292 return false;
293 return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
297 /* Return true if STMT needs to be rewritten. When renaming a subset
298 of the variables, not all statements will be processed. This is
299 decided in mark_def_sites. */
301 static inline bool
302 rewrite_uses_p (gimple stmt)
304 return gimple_visited_p (stmt);
308 /* Set the rewrite marker on STMT to the value given by REWRITE_P. */
310 static inline void
311 set_rewrite_uses (gimple stmt, bool rewrite_p)
313 gimple_set_visited (stmt, rewrite_p);
317 /* Return true if the DEFs created by statement STMT should be
318 registered when marking new definition sites. This is slightly
319 different than rewrite_uses_p: it's used by update_ssa to
320 distinguish statements that need to have both uses and defs
321 processed from those that only need to have their defs processed.
322 Statements that define new SSA names only need to have their defs
323 registered, but they don't need to have their uses renamed. */
325 static inline bool
326 register_defs_p (gimple stmt)
328 return gimple_plf (stmt, GF_PLF_1) != 0;
332 /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
334 static inline void
335 set_register_defs (gimple stmt, bool register_defs_p)
337 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
341 /* Get the information associated with NAME. */
343 static inline ssa_name_info_p
344 get_ssa_name_ann (tree name)
346 unsigned ver = SSA_NAME_VERSION (name);
347 unsigned len = info_for_ssa_name.length ();
348 struct ssa_name_info *info;
350 /* Re-allocate the vector at most once per update/into-SSA. */
351 if (ver >= len)
352 info_for_ssa_name.safe_grow_cleared (num_ssa_names);
354 /* But allocate infos lazily. */
355 info = info_for_ssa_name[ver];
356 if (!info)
358 info = XCNEW (struct ssa_name_info);
359 info->age = current_info_for_ssa_name_age;
360 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
361 info_for_ssa_name[ver] = info;
364 if (info->age < current_info_for_ssa_name_age)
366 info->age = current_info_for_ssa_name_age;
367 info->repl_set = NULL;
368 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
369 info->info.current_def = NULL_TREE;
370 info->info.def_blocks.def_blocks = NULL;
371 info->info.def_blocks.phi_blocks = NULL;
372 info->info.def_blocks.livein_blocks = NULL;
375 return info;
378 /* Return and allocate the auxiliar information for DECL. */
380 static inline var_info_p
381 get_var_info (tree decl)
383 struct var_info_d vi;
384 var_info_d **slot;
385 vi.var = decl;
386 slot = var_infos.find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
387 if (*slot == NULL)
389 var_info_p v = XCNEW (struct var_info_d);
390 v->var = decl;
391 *slot = v;
392 return v;
394 return *slot;
398 /* Clears info for SSA names. */
400 static void
401 clear_ssa_name_info (void)
403 current_info_for_ssa_name_age++;
405 /* If current_info_for_ssa_name_age wraps we use stale information.
406 Asser that this does not happen. */
407 gcc_assert (current_info_for_ssa_name_age != 0);
411 /* Get access to the auxiliar information stored per SSA name or decl. */
413 static inline common_info_p
414 get_common_info (tree var)
416 if (TREE_CODE (var) == SSA_NAME)
417 return &get_ssa_name_ann (var)->info;
418 else
419 return &get_var_info (var)->info;
423 /* Return the current definition for VAR. */
425 tree
426 get_current_def (tree var)
428 return get_common_info (var)->current_def;
432 /* Sets current definition of VAR to DEF. */
434 void
435 set_current_def (tree var, tree def)
437 get_common_info (var)->current_def = def;
440 /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
441 all statements in basic block BB. */
443 static void
444 initialize_flags_in_bb (basic_block bb)
446 gimple stmt;
447 gimple_stmt_iterator gsi;
449 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
451 gimple phi = gsi_stmt (gsi);
452 set_rewrite_uses (phi, false);
453 set_register_defs (phi, false);
456 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
458 stmt = gsi_stmt (gsi);
460 /* We are going to use the operand cache API, such as
461 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
462 cache for each statement should be up-to-date. */
463 gcc_checking_assert (!gimple_modified_p (stmt));
464 set_rewrite_uses (stmt, false);
465 set_register_defs (stmt, false);
469 /* Mark block BB as interesting for update_ssa. */
471 static void
472 mark_block_for_update (basic_block bb)
474 gcc_checking_assert (blocks_to_update != NULL);
475 if (!bitmap_set_bit (blocks_to_update, bb->index))
476 return;
477 initialize_flags_in_bb (bb);
480 /* Return the set of blocks where variable VAR is defined and the blocks
481 where VAR is live on entry (livein). If no entry is found in
482 DEF_BLOCKS, a new one is created and returned. */
484 static inline struct def_blocks_d *
485 get_def_blocks_for (common_info_p info)
487 struct def_blocks_d *db_p = &info->def_blocks;
488 if (!db_p->def_blocks)
490 db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
491 db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
492 db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
495 return db_p;
499 /* Mark block BB as the definition site for variable VAR. PHI_P is true if
500 VAR is defined by a PHI node. */
502 static void
503 set_def_block (tree var, basic_block bb, bool phi_p)
505 struct def_blocks_d *db_p;
506 common_info_p info;
508 info = get_common_info (var);
509 db_p = get_def_blocks_for (info);
511 /* Set the bit corresponding to the block where VAR is defined. */
512 bitmap_set_bit (db_p->def_blocks, bb->index);
513 if (phi_p)
514 bitmap_set_bit (db_p->phi_blocks, bb->index);
516 /* Keep track of whether or not we may need to insert PHI nodes.
518 If we are in the UNKNOWN state, then this is the first definition
519 of VAR. Additionally, we have not seen any uses of VAR yet, so
520 we do not need a PHI node for this variable at this time (i.e.,
521 transition to NEED_PHI_STATE_NO).
523 If we are in any other state, then we either have multiple definitions
524 of this variable occurring in different blocks or we saw a use of the
525 variable which was not dominated by the block containing the
526 definition(s). In this case we may need a PHI node, so enter
527 state NEED_PHI_STATE_MAYBE. */
528 if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
529 info->need_phi_state = NEED_PHI_STATE_NO;
530 else
531 info->need_phi_state = NEED_PHI_STATE_MAYBE;
535 /* Mark block BB as having VAR live at the entry to BB. */
537 static void
538 set_livein_block (tree var, basic_block bb)
540 common_info_p info;
541 struct def_blocks_d *db_p;
543 info = get_common_info (var);
544 db_p = get_def_blocks_for (info);
546 /* Set the bit corresponding to the block where VAR is live in. */
547 bitmap_set_bit (db_p->livein_blocks, bb->index);
549 /* Keep track of whether or not we may need to insert PHI nodes.
551 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
552 by the single block containing the definition(s) of this variable. If
553 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
554 NEED_PHI_STATE_MAYBE. */
555 if (info->need_phi_state == NEED_PHI_STATE_NO)
557 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
559 if (def_block_index == -1
560 || ! dominated_by_p (CDI_DOMINATORS, bb,
561 BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
562 info->need_phi_state = NEED_PHI_STATE_MAYBE;
564 else
565 info->need_phi_state = NEED_PHI_STATE_MAYBE;
569 /* Return true if NAME is in OLD_SSA_NAMES. */
571 static inline bool
572 is_old_name (tree name)
574 unsigned ver = SSA_NAME_VERSION (name);
575 if (!new_ssa_names)
576 return false;
577 return (ver < SBITMAP_SIZE (new_ssa_names)
578 && bitmap_bit_p (old_ssa_names, ver));
582 /* Return true if NAME is in NEW_SSA_NAMES. */
584 static inline bool
585 is_new_name (tree name)
587 unsigned ver = SSA_NAME_VERSION (name);
588 if (!new_ssa_names)
589 return false;
590 return (ver < SBITMAP_SIZE (new_ssa_names)
591 && bitmap_bit_p (new_ssa_names, ver));
595 /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
597 static inline bitmap
598 names_replaced_by (tree new_tree)
600 return get_ssa_name_ann (new_tree)->repl_set;
604 /* Add OLD to REPL_TBL[NEW_TREE].SET. */
606 static inline void
607 add_to_repl_tbl (tree new_tree, tree old)
609 bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
610 if (!*set)
611 *set = BITMAP_ALLOC (&update_ssa_obstack);
612 bitmap_set_bit (*set, SSA_NAME_VERSION (old));
616 /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
617 represents the set of names O_1 ... O_j replaced by N_i. This is
618 used by update_ssa and its helpers to introduce new SSA names in an
619 already formed SSA web. */
621 static void
622 add_new_name_mapping (tree new_tree, tree old)
624 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
625 gcc_checking_assert (new_tree != old
626 && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
628 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
629 caller may have created new names since the set was created. */
630 if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
632 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
633 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
634 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
637 /* Update the REPL_TBL table. */
638 add_to_repl_tbl (new_tree, old);
640 /* If OLD had already been registered as a new name, then all the
641 names that OLD replaces should also be replaced by NEW_TREE. */
642 if (is_new_name (old))
643 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
645 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
646 respectively. */
647 bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
648 bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
652 /* Call back for walk_dominator_tree used to collect definition sites
653 for every variable in the function. For every statement S in block
656 1- Variables defined by S in the DEFS of S are marked in the bitmap
657 KILLS.
659 2- If S uses a variable VAR and there is no preceding kill of VAR,
660 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
662 This information is used to determine which variables are live
663 across block boundaries to reduce the number of PHI nodes
664 we create. */
666 static void
667 mark_def_sites (basic_block bb, gimple stmt, bitmap kills)
669 tree def;
670 use_operand_p use_p;
671 ssa_op_iter iter;
673 /* Since this is the first time that we rewrite the program into SSA
674 form, force an operand scan on every statement. */
675 update_stmt (stmt);
677 gcc_checking_assert (blocks_to_update == NULL);
678 set_register_defs (stmt, false);
679 set_rewrite_uses (stmt, false);
681 if (is_gimple_debug (stmt))
683 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
685 tree sym = USE_FROM_PTR (use_p);
686 gcc_checking_assert (DECL_P (sym));
687 set_rewrite_uses (stmt, true);
689 if (rewrite_uses_p (stmt))
690 bitmap_set_bit (interesting_blocks, bb->index);
691 return;
694 /* If a variable is used before being set, then the variable is live
695 across a block boundary, so mark it live-on-entry to BB. */
696 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
698 tree sym = USE_FROM_PTR (use_p);
699 gcc_checking_assert (DECL_P (sym));
700 if (!bitmap_bit_p (kills, DECL_UID (sym)))
701 set_livein_block (sym, bb);
702 set_rewrite_uses (stmt, true);
705 /* Now process the defs. Mark BB as the definition block and add
706 each def to the set of killed symbols. */
707 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
709 gcc_checking_assert (DECL_P (def));
710 set_def_block (def, bb, false);
711 bitmap_set_bit (kills, DECL_UID (def));
712 set_register_defs (stmt, true);
715 /* If we found the statement interesting then also mark the block BB
716 as interesting. */
717 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
718 bitmap_set_bit (interesting_blocks, bb->index);
721 /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
722 in the dfs numbering of the dominance tree. */
724 struct dom_dfsnum
726 /* Basic block whose index this entry corresponds to. */
727 unsigned bb_index;
729 /* The dfs number of this node. */
730 unsigned dfs_num;
733 /* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
734 for qsort. */
736 static int
737 cmp_dfsnum (const void *a, const void *b)
739 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
740 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
742 return (int) da->dfs_num - (int) db->dfs_num;
745 /* Among the intervals starting at the N points specified in DEFS, find
746 the one that contains S, and return its bb_index. */
748 static unsigned
749 find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
751 unsigned f = 0, t = n, m;
753 while (t > f + 1)
755 m = (f + t) / 2;
756 if (defs[m].dfs_num <= s)
757 f = m;
758 else
759 t = m;
762 return defs[f].bb_index;
765 /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
766 KILLS is a bitmap of blocks where the value is defined before any use. */
768 static void
769 prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
771 bitmap_iterator bi;
772 unsigned i, b, p, u, top;
773 bitmap live_phis;
774 basic_block def_bb, use_bb;
775 edge e;
776 edge_iterator ei;
777 bitmap to_remove;
778 struct dom_dfsnum *defs;
779 unsigned n_defs, adef;
781 if (bitmap_empty_p (uses))
783 bitmap_clear (phis);
784 return;
787 /* The phi must dominate a use, or an argument of a live phi. Also, we
788 do not create any phi nodes in def blocks, unless they are also livein. */
789 to_remove = BITMAP_ALLOC (NULL);
790 bitmap_and_compl (to_remove, kills, uses);
791 bitmap_and_compl_into (phis, to_remove);
792 if (bitmap_empty_p (phis))
794 BITMAP_FREE (to_remove);
795 return;
798 /* We want to remove the unnecessary phi nodes, but we do not want to compute
799 liveness information, as that may be linear in the size of CFG, and if
800 there are lot of different variables to rewrite, this may lead to quadratic
801 behavior.
803 Instead, we basically emulate standard dce. We put all uses to worklist,
804 then for each of them find the nearest def that dominates them. If this
805 def is a phi node, we mark it live, and if it was not live before, we
806 add the predecessors of its basic block to the worklist.
808 To quickly locate the nearest def that dominates use, we use dfs numbering
809 of the dominance tree (that is already available in order to speed up
810 queries). For each def, we have the interval given by the dfs number on
811 entry to and on exit from the corresponding subtree in the dominance tree.
812 The nearest dominator for a given use is the smallest of these intervals
813 that contains entry and exit dfs numbers for the basic block with the use.
814 If we store the bounds for all the uses to an array and sort it, we can
815 locate the nearest dominating def in logarithmic time by binary search.*/
816 bitmap_ior (to_remove, kills, phis);
817 n_defs = bitmap_count_bits (to_remove);
818 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
819 defs[0].bb_index = 1;
820 defs[0].dfs_num = 0;
821 adef = 1;
822 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
824 def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
825 defs[adef].bb_index = i;
826 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
827 defs[adef + 1].bb_index = i;
828 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
829 adef += 2;
831 BITMAP_FREE (to_remove);
832 gcc_assert (adef == 2 * n_defs + 1);
833 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
834 gcc_assert (defs[0].bb_index == 1);
836 /* Now each DEFS entry contains the number of the basic block to that the
837 dfs number corresponds. Change them to the number of basic block that
838 corresponds to the interval following the dfs number. Also, for the
839 dfs_out numbers, increase the dfs number by one (so that it corresponds
840 to the start of the following interval, not to the end of the current
841 one). We use WORKLIST as a stack. */
842 auto_vec<int> worklist (n_defs + 1);
843 worklist.quick_push (1);
844 top = 1;
845 n_defs = 1;
846 for (i = 1; i < adef; i++)
848 b = defs[i].bb_index;
849 if (b == top)
851 /* This is a closing element. Interval corresponding to the top
852 of the stack after removing it follows. */
853 worklist.pop ();
854 top = worklist[worklist.length () - 1];
855 defs[n_defs].bb_index = top;
856 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
858 else
860 /* Opening element. Nothing to do, just push it to the stack and move
861 it to the correct position. */
862 defs[n_defs].bb_index = defs[i].bb_index;
863 defs[n_defs].dfs_num = defs[i].dfs_num;
864 worklist.quick_push (b);
865 top = b;
868 /* If this interval starts at the same point as the previous one, cancel
869 the previous one. */
870 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
871 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
872 else
873 n_defs++;
875 worklist.pop ();
876 gcc_assert (worklist.is_empty ());
878 /* Now process the uses. */
879 live_phis = BITMAP_ALLOC (NULL);
880 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
882 worklist.safe_push (i);
885 while (!worklist.is_empty ())
887 b = worklist.pop ();
888 if (b == ENTRY_BLOCK)
889 continue;
891 /* If there is a phi node in USE_BB, it is made live. Otherwise,
892 find the def that dominates the immediate dominator of USE_BB
893 (the kill in USE_BB does not dominate the use). */
894 if (bitmap_bit_p (phis, b))
895 p = b;
896 else
898 use_bb = get_immediate_dominator (CDI_DOMINATORS,
899 BASIC_BLOCK_FOR_FN (cfun, b));
900 p = find_dfsnum_interval (defs, n_defs,
901 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
902 if (!bitmap_bit_p (phis, p))
903 continue;
906 /* If the phi node is already live, there is nothing to do. */
907 if (!bitmap_set_bit (live_phis, p))
908 continue;
910 /* Add the new uses to the worklist. */
911 def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
912 FOR_EACH_EDGE (e, ei, def_bb->preds)
914 u = e->src->index;
915 if (bitmap_bit_p (uses, u))
916 continue;
918 /* In case there is a kill directly in the use block, do not record
919 the use (this is also necessary for correctness, as we assume that
920 uses dominated by a def directly in their block have been filtered
921 out before). */
922 if (bitmap_bit_p (kills, u))
923 continue;
925 bitmap_set_bit (uses, u);
926 worklist.safe_push (u);
930 bitmap_copy (phis, live_phis);
931 BITMAP_FREE (live_phis);
932 free (defs);
935 /* Return the set of blocks where variable VAR is defined and the blocks
936 where VAR is live on entry (livein). Return NULL, if no entry is
937 found in DEF_BLOCKS. */
939 static inline struct def_blocks_d *
940 find_def_blocks_for (tree var)
942 def_blocks_p p = &get_common_info (var)->def_blocks;
943 if (!p->def_blocks)
944 return NULL;
945 return p;
949 /* Marks phi node PHI in basic block BB for rewrite. */
951 static void
952 mark_phi_for_rewrite (basic_block bb, gimple phi)
954 gimple_vec phis;
955 unsigned n, idx = bb->index;
957 if (rewrite_uses_p (phi))
958 return;
960 set_rewrite_uses (phi, true);
962 if (!blocks_with_phis_to_rewrite)
963 return;
965 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
967 n = (unsigned) last_basic_block_for_fn (cfun) + 1;
968 if (phis_to_rewrite.length () < n)
969 phis_to_rewrite.safe_grow_cleared (n);
971 phis = phis_to_rewrite[idx];
972 phis.reserve (10);
974 phis.safe_push (phi);
975 phis_to_rewrite[idx] = phis;
978 /* Insert PHI nodes for variable VAR using the iterated dominance
979 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
980 function assumes that the caller is incrementally updating the
981 existing SSA form, in which case VAR may be an SSA name instead of
982 a symbol.
984 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
985 PHI node for VAR. On exit, only the nodes that received a PHI node
986 for VAR will be present in PHI_INSERTION_POINTS. */
988 static void
989 insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
991 unsigned bb_index;
992 edge e;
993 gimple phi;
994 basic_block bb;
995 bitmap_iterator bi;
996 struct def_blocks_d *def_map = find_def_blocks_for (var);
998 /* Remove the blocks where we already have PHI nodes for VAR. */
999 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1001 /* Remove obviously useless phi nodes. */
1002 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1003 def_map->livein_blocks);
1005 /* And insert the PHI nodes. */
1006 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1008 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1009 if (update_p)
1010 mark_block_for_update (bb);
1012 if (dump_file && (dump_flags & TDF_DETAILS))
1014 fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
1015 print_generic_expr (dump_file, var, TDF_SLIM);
1016 fprintf (dump_file, "\n");
1018 phi = NULL;
1020 if (TREE_CODE (var) == SSA_NAME)
1022 /* If we are rewriting SSA names, create the LHS of the PHI
1023 node by duplicating VAR. This is useful in the case of
1024 pointers, to also duplicate pointer attributes (alias
1025 information, in particular). */
1026 edge_iterator ei;
1027 tree new_lhs;
1029 gcc_checking_assert (update_p);
1030 new_lhs = duplicate_ssa_name (var, NULL);
1031 phi = create_phi_node (new_lhs, bb);
1032 add_new_name_mapping (new_lhs, var);
1034 /* Add VAR to every argument slot of PHI. We need VAR in
1035 every argument so that rewrite_update_phi_arguments knows
1036 which name is this PHI node replacing. If VAR is a
1037 symbol marked for renaming, this is not necessary, the
1038 renamer will use the symbol on the LHS to get its
1039 reaching definition. */
1040 FOR_EACH_EDGE (e, ei, bb->preds)
1041 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1043 else
1045 tree tracked_var;
1047 gcc_checking_assert (DECL_P (var));
1048 phi = create_phi_node (var, bb);
1050 tracked_var = target_for_debug_bind (var);
1051 if (tracked_var)
1053 gimple note = gimple_build_debug_bind (tracked_var,
1054 PHI_RESULT (phi),
1055 phi);
1056 gimple_stmt_iterator si = gsi_after_labels (bb);
1057 gsi_insert_before (&si, note, GSI_SAME_STMT);
1061 /* Mark this PHI node as interesting for update_ssa. */
1062 set_register_defs (phi, true);
1063 mark_phi_for_rewrite (bb, phi);
1067 /* Sort var_infos after DECL_UID of their var. */
1069 static int
1070 insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1072 const struct var_info_d *defa = *(struct var_info_d * const *)a;
1073 const struct var_info_d *defb = *(struct var_info_d * const *)b;
1074 if (DECL_UID (defa->var) < DECL_UID (defb->var))
1075 return -1;
1076 else
1077 return 1;
1080 /* Insert PHI nodes at the dominance frontier of blocks with variable
1081 definitions. DFS contains the dominance frontier information for
1082 the flowgraph. */
1084 static void
1085 insert_phi_nodes (bitmap_head *dfs)
1087 hash_table <var_info_hasher>::iterator hi;
1088 unsigned i;
1089 var_info_p info;
1091 timevar_push (TV_TREE_INSERT_PHI_NODES);
1093 auto_vec<var_info_p> vars (var_infos.elements ());
1094 FOR_EACH_HASH_TABLE_ELEMENT (var_infos, info, var_info_p, hi)
1095 if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1096 vars.quick_push (info);
1098 /* Do two stages to avoid code generation differences for UID
1099 differences but no UID ordering differences. */
1100 vars.qsort (insert_phi_nodes_compare_var_infos);
1102 FOR_EACH_VEC_ELT (vars, i, info)
1104 bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1105 insert_phi_nodes_for (info->var, idf, false);
1106 BITMAP_FREE (idf);
1109 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1113 /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1114 register DEF (an SSA_NAME) to be a new definition for SYM. */
1116 static void
1117 register_new_def (tree def, tree sym)
1119 common_info_p info = get_common_info (sym);
1120 tree currdef;
1122 /* If this variable is set in a single basic block and all uses are
1123 dominated by the set(s) in that single basic block, then there is
1124 no reason to record anything for this variable in the block local
1125 definition stacks. Doing so just wastes time and memory.
1127 This is the same test to prune the set of variables which may
1128 need PHI nodes. So we just use that information since it's already
1129 computed and available for us to use. */
1130 if (info->need_phi_state == NEED_PHI_STATE_NO)
1132 info->current_def = def;
1133 return;
1136 currdef = info->current_def;
1138 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1139 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1140 in the stack so that we know which symbol is being defined by
1141 this SSA name when we unwind the stack. */
1142 if (currdef && !is_gimple_reg (sym))
1143 block_defs_stack.safe_push (sym);
1145 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1146 stack is later used by the dominator tree callbacks to restore
1147 the reaching definitions for all the variables defined in the
1148 block after a recursive visit to all its immediately dominated
1149 blocks. If there is no current reaching definition, then just
1150 record the underlying _DECL node. */
1151 block_defs_stack.safe_push (currdef ? currdef : sym);
1153 /* Set the current reaching definition for SYM to be DEF. */
1154 info->current_def = def;
1158 /* Perform a depth-first traversal of the dominator tree looking for
1159 variables to rename. BB is the block where to start searching.
1160 Renaming is a five step process:
1162 1- Every definition made by PHI nodes at the start of the blocks is
1163 registered as the current definition for the corresponding variable.
1165 2- Every statement in BB is rewritten. USE and VUSE operands are
1166 rewritten with their corresponding reaching definition. DEF and
1167 VDEF targets are registered as new definitions.
1169 3- All the PHI nodes in successor blocks of BB are visited. The
1170 argument corresponding to BB is replaced with its current reaching
1171 definition.
1173 4- Recursively rewrite every dominator child block of BB.
1175 5- Restore (in reverse order) the current reaching definition for every
1176 new definition introduced in this block. This is done so that when
1177 we return from the recursive call, all the current reaching
1178 definitions are restored to the names that were valid in the
1179 dominator parent of BB. */
1181 /* Return the current definition for variable VAR. If none is found,
1182 create a new SSA name to act as the zeroth definition for VAR. */
1184 static tree
1185 get_reaching_def (tree var)
1187 common_info_p info = get_common_info (var);
1188 tree currdef;
1190 /* Lookup the current reaching definition for VAR. */
1191 currdef = info->current_def;
1193 /* If there is no reaching definition for VAR, create and register a
1194 default definition for it (if needed). */
1195 if (currdef == NULL_TREE)
1197 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1198 currdef = get_or_create_ssa_default_def (cfun, sym);
1201 /* Return the current reaching definition for VAR, or the default
1202 definition, if we had to create one. */
1203 return currdef;
1207 /* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1209 static void
1210 rewrite_debug_stmt_uses (gimple stmt)
1212 use_operand_p use_p;
1213 ssa_op_iter iter;
1214 bool update = false;
1216 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1218 tree var = USE_FROM_PTR (use_p), def;
1219 common_info_p info = get_common_info (var);
1220 gcc_checking_assert (DECL_P (var));
1221 def = info->current_def;
1222 if (!def)
1224 if (TREE_CODE (var) == PARM_DECL
1225 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
1227 gimple_stmt_iterator gsi
1229 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1230 int lim;
1231 /* Search a few source bind stmts at the start of first bb to
1232 see if a DEBUG_EXPR_DECL can't be reused. */
1233 for (lim = 32;
1234 !gsi_end_p (gsi) && lim > 0;
1235 gsi_next (&gsi), lim--)
1237 gimple gstmt = gsi_stmt (gsi);
1238 if (!gimple_debug_source_bind_p (gstmt))
1239 break;
1240 if (gimple_debug_source_bind_get_value (gstmt) == var)
1242 def = gimple_debug_source_bind_get_var (gstmt);
1243 if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1244 break;
1245 else
1246 def = NULL_TREE;
1249 /* If not, add a new source bind stmt. */
1250 if (def == NULL_TREE)
1252 gimple def_temp;
1253 def = make_node (DEBUG_EXPR_DECL);
1254 def_temp = gimple_build_debug_source_bind (def, var, NULL);
1255 DECL_ARTIFICIAL (def) = 1;
1256 TREE_TYPE (def) = TREE_TYPE (var);
1257 DECL_MODE (def) = DECL_MODE (var);
1258 gsi =
1259 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1260 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1262 update = true;
1265 else
1267 /* Check if info->current_def can be trusted. */
1268 basic_block bb = gimple_bb (stmt);
1269 basic_block def_bb
1270 = SSA_NAME_IS_DEFAULT_DEF (def)
1271 ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1273 /* If definition is in current bb, it is fine. */
1274 if (bb == def_bb)
1276 /* If definition bb doesn't dominate the current bb,
1277 it can't be used. */
1278 else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1279 def = NULL;
1280 /* If there is just one definition and dominates the current
1281 bb, it is fine. */
1282 else if (info->need_phi_state == NEED_PHI_STATE_NO)
1284 else
1286 struct def_blocks_d *db_p = get_def_blocks_for (info);
1288 /* If there are some non-debug uses in the current bb,
1289 it is fine. */
1290 if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1292 /* Otherwise give up for now. */
1293 else
1294 def = NULL;
1297 if (def == NULL)
1299 gimple_debug_bind_reset_value (stmt);
1300 update_stmt (stmt);
1301 return;
1303 SET_USE (use_p, def);
1305 if (update)
1306 update_stmt (stmt);
1309 /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1310 the block with its immediate reaching definitions. Update the current
1311 definition of a variable when a new real or virtual definition is found. */
1313 static void
1314 rewrite_stmt (gimple_stmt_iterator *si)
1316 use_operand_p use_p;
1317 def_operand_p def_p;
1318 ssa_op_iter iter;
1319 gimple stmt = gsi_stmt (*si);
1321 /* If mark_def_sites decided that we don't need to rewrite this
1322 statement, ignore it. */
1323 gcc_assert (blocks_to_update == NULL);
1324 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1325 return;
1327 if (dump_file && (dump_flags & TDF_DETAILS))
1329 fprintf (dump_file, "Renaming statement ");
1330 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1331 fprintf (dump_file, "\n");
1334 /* Step 1. Rewrite USES in the statement. */
1335 if (rewrite_uses_p (stmt))
1337 if (is_gimple_debug (stmt))
1338 rewrite_debug_stmt_uses (stmt);
1339 else
1340 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1342 tree var = USE_FROM_PTR (use_p);
1343 gcc_checking_assert (DECL_P (var));
1344 SET_USE (use_p, get_reaching_def (var));
1348 /* Step 2. Register the statement's DEF operands. */
1349 if (register_defs_p (stmt))
1350 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1352 tree var = DEF_FROM_PTR (def_p);
1353 tree name;
1354 tree tracked_var;
1356 gcc_checking_assert (DECL_P (var));
1358 if (gimple_clobber_p (stmt)
1359 && is_gimple_reg (var))
1361 /* If we rewrite a DECL into SSA form then drop its
1362 clobber stmts and replace uses with a new default def. */
1363 gcc_checking_assert (TREE_CODE (var) == VAR_DECL
1364 && !gimple_vdef (stmt));
1365 gsi_replace (si, gimple_build_nop (), true);
1366 register_new_def (get_or_create_ssa_default_def (cfun, var), var);
1367 break;
1370 name = make_ssa_name (var, stmt);
1371 SET_DEF (def_p, name);
1372 register_new_def (DEF_FROM_PTR (def_p), var);
1374 tracked_var = target_for_debug_bind (var);
1375 if (tracked_var)
1377 gimple note = gimple_build_debug_bind (tracked_var, name, stmt);
1378 gsi_insert_after (si, note, GSI_SAME_STMT);
1384 /* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1385 PHI nodes. For every PHI node found, add a new argument containing the
1386 current reaching definition for the variable and the edge through which
1387 that definition is reaching the PHI node. */
1389 static void
1390 rewrite_add_phi_arguments (basic_block bb)
1392 edge e;
1393 edge_iterator ei;
1395 FOR_EACH_EDGE (e, ei, bb->succs)
1397 gimple phi;
1398 gimple_stmt_iterator gsi;
1400 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1401 gsi_next (&gsi))
1403 tree currdef, res;
1404 location_t loc;
1406 phi = gsi_stmt (gsi);
1407 res = gimple_phi_result (phi);
1408 currdef = get_reaching_def (SSA_NAME_VAR (res));
1409 /* Virtual operand PHI args do not need a location. */
1410 if (virtual_operand_p (res))
1411 loc = UNKNOWN_LOCATION;
1412 else
1413 loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1414 add_phi_arg (phi, currdef, e, loc);
1419 class rewrite_dom_walker : public dom_walker
1421 public:
1422 rewrite_dom_walker (cdi_direction direction) : dom_walker (direction) {}
1424 virtual void before_dom_children (basic_block);
1425 virtual void after_dom_children (basic_block);
1428 /* SSA Rewriting Step 1. Initialization, create a block local stack
1429 of reaching definitions for new SSA names produced in this block
1430 (BLOCK_DEFS). Register new definitions for every PHI node in the
1431 block. */
1433 void
1434 rewrite_dom_walker::before_dom_children (basic_block bb)
1436 gimple_stmt_iterator gsi;
1438 if (dump_file && (dump_flags & TDF_DETAILS))
1439 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1441 /* Mark the unwind point for this block. */
1442 block_defs_stack.safe_push (NULL_TREE);
1444 /* Step 1. Register new definitions for every PHI node in the block.
1445 Conceptually, all the PHI nodes are executed in parallel and each PHI
1446 node introduces a new version for the associated variable. */
1447 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1449 tree result = gimple_phi_result (gsi_stmt (gsi));
1450 register_new_def (result, SSA_NAME_VAR (result));
1453 /* Step 2. Rewrite every variable used in each statement in the block
1454 with its immediate reaching definitions. Update the current definition
1455 of a variable when a new real or virtual definition is found. */
1456 if (bitmap_bit_p (interesting_blocks, bb->index))
1457 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1458 rewrite_stmt (&gsi);
1460 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1461 For every PHI node found, add a new argument containing the current
1462 reaching definition for the variable and the edge through which that
1463 definition is reaching the PHI node. */
1464 rewrite_add_phi_arguments (bb);
1469 /* Called after visiting all the statements in basic block BB and all
1470 of its dominator children. Restore CURRDEFS to its original value. */
1472 void
1473 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1475 /* Restore CURRDEFS to its original state. */
1476 while (block_defs_stack.length () > 0)
1478 tree tmp = block_defs_stack.pop ();
1479 tree saved_def, var;
1481 if (tmp == NULL_TREE)
1482 break;
1484 if (TREE_CODE (tmp) == SSA_NAME)
1486 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1487 current definition of its underlying variable. Note that
1488 if the SSA_NAME is not for a GIMPLE register, the symbol
1489 being defined is stored in the next slot in the stack.
1490 This mechanism is needed because an SSA name for a
1491 non-register symbol may be the definition for more than
1492 one symbol (e.g., SFTs, aliased variables, etc). */
1493 saved_def = tmp;
1494 var = SSA_NAME_VAR (saved_def);
1495 if (!is_gimple_reg (var))
1496 var = block_defs_stack.pop ();
1498 else
1500 /* If we recorded anything else, it must have been a _DECL
1501 node and its current reaching definition must have been
1502 NULL. */
1503 saved_def = NULL;
1504 var = tmp;
1507 get_common_info (var)->current_def = saved_def;
1512 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1514 DEBUG_FUNCTION void
1515 debug_decl_set (bitmap set)
1517 dump_decl_set (stderr, set);
1518 fprintf (stderr, "\n");
1522 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1523 stack up to a maximum of N levels. If N is -1, the whole stack is
1524 dumped. New levels are created when the dominator tree traversal
1525 used for renaming enters a new sub-tree. */
1527 void
1528 dump_defs_stack (FILE *file, int n)
1530 int i, j;
1532 fprintf (file, "\n\nRenaming stack");
1533 if (n > 0)
1534 fprintf (file, " (up to %d levels)", n);
1535 fprintf (file, "\n\n");
1537 i = 1;
1538 fprintf (file, "Level %d (current level)\n", i);
1539 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1541 tree name, var;
1543 name = block_defs_stack[j];
1544 if (name == NULL_TREE)
1546 i++;
1547 if (n > 0 && i > n)
1548 break;
1549 fprintf (file, "\nLevel %d\n", i);
1550 continue;
1553 if (DECL_P (name))
1555 var = name;
1556 name = NULL_TREE;
1558 else
1560 var = SSA_NAME_VAR (name);
1561 if (!is_gimple_reg (var))
1563 j--;
1564 var = block_defs_stack[j];
1568 fprintf (file, " Previous CURRDEF (");
1569 print_generic_expr (file, var, 0);
1570 fprintf (file, ") = ");
1571 if (name)
1572 print_generic_expr (file, name, 0);
1573 else
1574 fprintf (file, "<NIL>");
1575 fprintf (file, "\n");
1580 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1581 stack up to a maximum of N levels. If N is -1, the whole stack is
1582 dumped. New levels are created when the dominator tree traversal
1583 used for renaming enters a new sub-tree. */
1585 DEBUG_FUNCTION void
1586 debug_defs_stack (int n)
1588 dump_defs_stack (stderr, n);
1592 /* Dump the current reaching definition of every symbol to FILE. */
1594 void
1595 dump_currdefs (FILE *file)
1597 unsigned i;
1598 tree var;
1600 if (symbols_to_rename.is_empty ())
1601 return;
1603 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1604 FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1606 common_info_p info = get_common_info (var);
1607 fprintf (file, "CURRDEF (");
1608 print_generic_expr (file, var, 0);
1609 fprintf (file, ") = ");
1610 if (info->current_def)
1611 print_generic_expr (file, info->current_def, 0);
1612 else
1613 fprintf (file, "<NIL>");
1614 fprintf (file, "\n");
1619 /* Dump the current reaching definition of every symbol to stderr. */
1621 DEBUG_FUNCTION void
1622 debug_currdefs (void)
1624 dump_currdefs (stderr);
1628 /* Dump SSA information to FILE. */
1630 void
1631 dump_tree_ssa (FILE *file)
1633 const char *funcname
1634 = lang_hooks.decl_printable_name (current_function_decl, 2);
1636 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1638 dump_var_infos (file);
1639 dump_defs_stack (file, -1);
1640 dump_currdefs (file);
1641 dump_tree_ssa_stats (file);
1645 /* Dump SSA information to stderr. */
1647 DEBUG_FUNCTION void
1648 debug_tree_ssa (void)
1650 dump_tree_ssa (stderr);
1654 /* Dump statistics for the hash table HTAB. */
1656 static void
1657 htab_statistics (FILE *file, hash_table <var_info_hasher> htab)
1659 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1660 (long) htab.size (),
1661 (long) htab.elements (),
1662 htab.collisions ());
1666 /* Dump SSA statistics on FILE. */
1668 void
1669 dump_tree_ssa_stats (FILE *file)
1671 if (var_infos.is_created ())
1673 fprintf (file, "\nHash table statistics:\n");
1674 fprintf (file, " var_infos: ");
1675 htab_statistics (file, var_infos);
1676 fprintf (file, "\n");
1681 /* Dump SSA statistics on stderr. */
1683 DEBUG_FUNCTION void
1684 debug_tree_ssa_stats (void)
1686 dump_tree_ssa_stats (stderr);
1690 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1693 debug_var_infos_r (var_info_d **slot, FILE *file)
1695 struct var_info_d *info = *slot;
1697 fprintf (file, "VAR: ");
1698 print_generic_expr (file, info->var, dump_flags);
1699 bitmap_print (file, info->info.def_blocks.def_blocks,
1700 ", DEF_BLOCKS: { ", "}");
1701 bitmap_print (file, info->info.def_blocks.livein_blocks,
1702 ", LIVEIN_BLOCKS: { ", "}");
1703 bitmap_print (file, info->info.def_blocks.phi_blocks,
1704 ", PHI_BLOCKS: { ", "}\n");
1706 return 1;
1710 /* Dump the VAR_INFOS hash table on FILE. */
1712 void
1713 dump_var_infos (FILE *file)
1715 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1716 if (var_infos.is_created ())
1717 var_infos.traverse <FILE *, debug_var_infos_r> (file);
1721 /* Dump the VAR_INFOS hash table on stderr. */
1723 DEBUG_FUNCTION void
1724 debug_var_infos (void)
1726 dump_var_infos (stderr);
1730 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1732 static inline void
1733 register_new_update_single (tree new_name, tree old_name)
1735 common_info_p info = get_common_info (old_name);
1736 tree currdef = info->current_def;
1738 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1739 This stack is later used by the dominator tree callbacks to
1740 restore the reaching definitions for all the variables
1741 defined in the block after a recursive visit to all its
1742 immediately dominated blocks. */
1743 block_defs_stack.reserve (2);
1744 block_defs_stack.quick_push (currdef);
1745 block_defs_stack.quick_push (old_name);
1747 /* Set the current reaching definition for OLD_NAME to be
1748 NEW_NAME. */
1749 info->current_def = new_name;
1753 /* Register NEW_NAME to be the new reaching definition for all the
1754 names in OLD_NAMES. Used by the incremental SSA update routines to
1755 replace old SSA names with new ones. */
1757 static inline void
1758 register_new_update_set (tree new_name, bitmap old_names)
1760 bitmap_iterator bi;
1761 unsigned i;
1763 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1764 register_new_update_single (new_name, ssa_name (i));
1769 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1770 it is a symbol marked for renaming, replace it with USE_P's current
1771 reaching definition. */
1773 static inline void
1774 maybe_replace_use (use_operand_p use_p)
1776 tree rdef = NULL_TREE;
1777 tree use = USE_FROM_PTR (use_p);
1778 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1780 if (marked_for_renaming (sym))
1781 rdef = get_reaching_def (sym);
1782 else if (is_old_name (use))
1783 rdef = get_reaching_def (use);
1785 if (rdef && rdef != use)
1786 SET_USE (use_p, rdef);
1790 /* Same as maybe_replace_use, but without introducing default stmts,
1791 returning false to indicate a need to do so. */
1793 static inline bool
1794 maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1796 tree rdef = NULL_TREE;
1797 tree use = USE_FROM_PTR (use_p);
1798 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1800 if (marked_for_renaming (sym))
1801 rdef = get_var_info (sym)->info.current_def;
1802 else if (is_old_name (use))
1804 rdef = get_ssa_name_ann (use)->info.current_def;
1805 /* We can't assume that, if there's no current definition, the
1806 default one should be used. It could be the case that we've
1807 rearranged blocks so that the earlier definition no longer
1808 dominates the use. */
1809 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1810 rdef = use;
1812 else
1813 rdef = use;
1815 if (rdef && rdef != use)
1816 SET_USE (use_p, rdef);
1818 return rdef != NULL_TREE;
1822 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1823 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1824 register it as the current definition for the names replaced by
1825 DEF_P. */
1827 static inline void
1828 maybe_register_def (def_operand_p def_p, gimple stmt,
1829 gimple_stmt_iterator gsi)
1831 tree def = DEF_FROM_PTR (def_p);
1832 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1834 /* If DEF is a naked symbol that needs renaming, create a new
1835 name for it. */
1836 if (marked_for_renaming (sym))
1838 if (DECL_P (def))
1840 tree tracked_var;
1842 def = make_ssa_name (def, stmt);
1843 SET_DEF (def_p, def);
1845 tracked_var = target_for_debug_bind (sym);
1846 if (tracked_var)
1848 gimple note = gimple_build_debug_bind (tracked_var, def, stmt);
1849 /* If stmt ends the bb, insert the debug stmt on the single
1850 non-EH edge from the stmt. */
1851 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1853 basic_block bb = gsi_bb (gsi);
1854 edge_iterator ei;
1855 edge e, ef = NULL;
1856 FOR_EACH_EDGE (e, ei, bb->succs)
1857 if (!(e->flags & EDGE_EH))
1859 gcc_checking_assert (!ef);
1860 ef = e;
1862 /* If there are other predecessors to ef->dest, then
1863 there must be PHI nodes for the modified
1864 variable, and therefore there will be debug bind
1865 stmts after the PHI nodes. The debug bind notes
1866 we'd insert would force the creation of a new
1867 block (diverging codegen) and be redundant with
1868 the post-PHI bind stmts, so don't add them.
1870 As for the exit edge, there wouldn't be redundant
1871 bind stmts, but there wouldn't be a PC to bind
1872 them to either, so avoid diverging the CFG. */
1873 if (ef && single_pred_p (ef->dest)
1874 && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1876 /* If there were PHI nodes in the node, we'd
1877 have to make sure the value we're binding
1878 doesn't need rewriting. But there shouldn't
1879 be PHI nodes in a single-predecessor block,
1880 so we just add the note. */
1881 gsi_insert_on_edge_immediate (ef, note);
1884 else
1885 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1889 register_new_update_single (def, sym);
1891 else
1893 /* If DEF is a new name, register it as a new definition
1894 for all the names replaced by DEF. */
1895 if (is_new_name (def))
1896 register_new_update_set (def, names_replaced_by (def));
1898 /* If DEF is an old name, register DEF as a new
1899 definition for itself. */
1900 if (is_old_name (def))
1901 register_new_update_single (def, def);
1906 /* Update every variable used in the statement pointed-to by SI. The
1907 statement is assumed to be in SSA form already. Names in
1908 OLD_SSA_NAMES used by SI will be updated to their current reaching
1909 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1910 will be registered as a new definition for their corresponding name
1911 in OLD_SSA_NAMES. */
1913 static void
1914 rewrite_update_stmt (gimple stmt, gimple_stmt_iterator gsi)
1916 use_operand_p use_p;
1917 def_operand_p def_p;
1918 ssa_op_iter iter;
1920 /* Only update marked statements. */
1921 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1922 return;
1924 if (dump_file && (dump_flags & TDF_DETAILS))
1926 fprintf (dump_file, "Updating SSA information for statement ");
1927 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1930 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1931 symbol is marked for renaming. */
1932 if (rewrite_uses_p (stmt))
1934 if (is_gimple_debug (stmt))
1936 bool failed = false;
1938 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1939 if (!maybe_replace_use_in_debug_stmt (use_p))
1941 failed = true;
1942 break;
1945 if (failed)
1947 /* DOM sometimes threads jumps in such a way that a
1948 debug stmt ends up referencing a SSA variable that no
1949 longer dominates the debug stmt, but such that all
1950 incoming definitions refer to the same definition in
1951 an earlier dominator. We could try to recover that
1952 definition somehow, but this will have to do for now.
1954 Introducing a default definition, which is what
1955 maybe_replace_use() would do in such cases, may
1956 modify code generation, for the otherwise-unused
1957 default definition would never go away, modifying SSA
1958 version numbers all over. */
1959 gimple_debug_bind_reset_value (stmt);
1960 update_stmt (stmt);
1963 else
1965 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1966 maybe_replace_use (use_p);
1970 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1971 Also register definitions for names whose underlying symbol is
1972 marked for renaming. */
1973 if (register_defs_p (stmt))
1974 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1975 maybe_register_def (def_p, stmt, gsi);
1979 /* Visit all the successor blocks of BB looking for PHI nodes. For
1980 every PHI node found, check if any of its arguments is in
1981 OLD_SSA_NAMES. If so, and if the argument has a current reaching
1982 definition, replace it. */
1984 static void
1985 rewrite_update_phi_arguments (basic_block bb)
1987 edge e;
1988 edge_iterator ei;
1989 unsigned i;
1991 FOR_EACH_EDGE (e, ei, bb->succs)
1993 gimple phi;
1994 gimple_vec phis;
1996 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1997 continue;
1999 phis = phis_to_rewrite[e->dest->index];
2000 FOR_EACH_VEC_ELT (phis, i, phi)
2002 tree arg, lhs_sym, reaching_def = NULL;
2003 use_operand_p arg_p;
2005 gcc_checking_assert (rewrite_uses_p (phi));
2007 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2008 arg = USE_FROM_PTR (arg_p);
2010 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2011 continue;
2013 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2015 if (arg == NULL_TREE)
2017 /* When updating a PHI node for a recently introduced
2018 symbol we may find NULL arguments. That's why we
2019 take the symbol from the LHS of the PHI node. */
2020 reaching_def = get_reaching_def (lhs_sym);
2023 else
2025 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2027 if (marked_for_renaming (sym))
2028 reaching_def = get_reaching_def (sym);
2029 else if (is_old_name (arg))
2030 reaching_def = get_reaching_def (arg);
2033 /* Update the argument if there is a reaching def. */
2034 if (reaching_def)
2036 source_location locus;
2037 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2039 SET_USE (arg_p, reaching_def);
2041 /* Virtual operands do not need a location. */
2042 if (virtual_operand_p (reaching_def))
2043 locus = UNKNOWN_LOCATION;
2044 else
2046 gimple stmt = SSA_NAME_DEF_STMT (reaching_def);
2048 /* Single element PHI nodes behave like copies, so get the
2049 location from the phi argument. */
2050 if (gimple_code (stmt) == GIMPLE_PHI
2051 && gimple_phi_num_args (stmt) == 1)
2052 locus = gimple_phi_arg_location (stmt, 0);
2053 else
2054 locus = gimple_location (stmt);
2057 gimple_phi_arg_set_location (phi, arg_i, locus);
2061 if (e->flags & EDGE_ABNORMAL)
2062 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2067 class rewrite_update_dom_walker : public dom_walker
2069 public:
2070 rewrite_update_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2072 virtual void before_dom_children (basic_block);
2073 virtual void after_dom_children (basic_block);
2076 /* Initialization of block data structures for the incremental SSA
2077 update pass. Create a block local stack of reaching definitions
2078 for new SSA names produced in this block (BLOCK_DEFS). Register
2079 new definitions for every PHI node in the block. */
2081 void
2082 rewrite_update_dom_walker::before_dom_children (basic_block bb)
2084 bool is_abnormal_phi;
2085 gimple_stmt_iterator gsi;
2087 if (dump_file && (dump_flags & TDF_DETAILS))
2088 fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2089 bb->index);
2091 /* Mark the unwind point for this block. */
2092 block_defs_stack.safe_push (NULL_TREE);
2094 if (!bitmap_bit_p (blocks_to_update, bb->index))
2095 return;
2097 /* Mark the LHS if any of the arguments flows through an abnormal
2098 edge. */
2099 is_abnormal_phi = bb_has_abnormal_pred (bb);
2101 /* If any of the PHI nodes is a replacement for a name in
2102 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2103 register it as a new definition for its corresponding name. Also
2104 register definitions for names whose underlying symbols are
2105 marked for renaming. */
2106 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2108 tree lhs, lhs_sym;
2109 gimple phi = gsi_stmt (gsi);
2111 if (!register_defs_p (phi))
2112 continue;
2114 lhs = gimple_phi_result (phi);
2115 lhs_sym = SSA_NAME_VAR (lhs);
2117 if (marked_for_renaming (lhs_sym))
2118 register_new_update_single (lhs, lhs_sym);
2119 else
2122 /* If LHS is a new name, register a new definition for all
2123 the names replaced by LHS. */
2124 if (is_new_name (lhs))
2125 register_new_update_set (lhs, names_replaced_by (lhs));
2127 /* If LHS is an OLD name, register it as a new definition
2128 for itself. */
2129 if (is_old_name (lhs))
2130 register_new_update_single (lhs, lhs);
2133 if (is_abnormal_phi)
2134 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2137 /* Step 2. Rewrite every variable used in each statement in the block. */
2138 if (bitmap_bit_p (interesting_blocks, bb->index))
2140 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2141 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2142 rewrite_update_stmt (gsi_stmt (gsi), gsi);
2145 /* Step 3. Update PHI nodes. */
2146 rewrite_update_phi_arguments (bb);
2149 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2150 the current reaching definition of every name re-written in BB to
2151 the original reaching definition before visiting BB. This
2152 unwinding must be done in the opposite order to what is done in
2153 register_new_update_set. */
2155 void
2156 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2158 while (block_defs_stack.length () > 0)
2160 tree var = block_defs_stack.pop ();
2161 tree saved_def;
2163 /* NULL indicates the unwind stop point for this block (see
2164 rewrite_update_enter_block). */
2165 if (var == NULL)
2166 return;
2168 saved_def = block_defs_stack.pop ();
2169 get_common_info (var)->current_def = saved_def;
2174 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2175 form.
2177 ENTRY indicates the block where to start. Every block dominated by
2178 ENTRY will be rewritten.
2180 WHAT indicates what actions will be taken by the renamer (see enum
2181 rewrite_mode).
2183 BLOCKS are the set of interesting blocks for the dominator walker
2184 to process. If this set is NULL, then all the nodes dominated
2185 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2186 are not present in BLOCKS are ignored. */
2188 static void
2189 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2191 /* Rewrite all the basic blocks in the program. */
2192 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2194 block_defs_stack.create (10);
2196 /* Recursively walk the dominator tree rewriting each statement in
2197 each basic block. */
2198 if (what == REWRITE_ALL)
2199 rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2200 else if (what == REWRITE_UPDATE)
2201 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2202 else
2203 gcc_unreachable ();
2205 /* Debugging dumps. */
2206 if (dump_file && (dump_flags & TDF_STATS))
2208 dump_dfa_stats (dump_file);
2209 if (var_infos.is_created ())
2210 dump_tree_ssa_stats (dump_file);
2213 block_defs_stack.release ();
2215 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2218 class mark_def_dom_walker : public dom_walker
2220 public:
2221 mark_def_dom_walker (cdi_direction direction);
2222 ~mark_def_dom_walker ();
2224 virtual void before_dom_children (basic_block);
2226 private:
2227 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2228 large enough to accommodate all the variables referenced in the
2229 function, not just the ones we are renaming. */
2230 bitmap m_kills;
2233 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2234 : dom_walker (direction), m_kills (BITMAP_ALLOC (NULL))
2238 mark_def_dom_walker::~mark_def_dom_walker ()
2240 BITMAP_FREE (m_kills);
2243 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2244 at the start of each block, and call mark_def_sites for each statement. */
2246 void
2247 mark_def_dom_walker::before_dom_children (basic_block bb)
2249 gimple_stmt_iterator gsi;
2251 bitmap_clear (m_kills);
2252 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2253 mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2256 /* Initialize internal data needed during renaming. */
2258 static void
2259 init_ssa_renamer (void)
2261 cfun->gimple_df->in_ssa_p = false;
2263 /* Allocate memory for the DEF_BLOCKS hash table. */
2264 gcc_assert (!var_infos.is_created ());
2265 var_infos.create (vec_safe_length (cfun->local_decls));
2267 bitmap_obstack_initialize (&update_ssa_obstack);
2271 /* Deallocate internal data structures used by the renamer. */
2273 static void
2274 fini_ssa_renamer (void)
2276 if (var_infos.is_created ())
2277 var_infos.dispose ();
2279 bitmap_obstack_release (&update_ssa_obstack);
2281 cfun->gimple_df->ssa_renaming_needed = 0;
2282 cfun->gimple_df->rename_vops = 0;
2283 cfun->gimple_df->in_ssa_p = true;
2286 /* Main entry point into the SSA builder. The renaming process
2287 proceeds in four main phases:
2289 1- Compute dominance frontier and immediate dominators, needed to
2290 insert PHI nodes and rename the function in dominator tree
2291 order.
2293 2- Find and mark all the blocks that define variables.
2295 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2297 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2299 Steps 3 and 4 are done using the dominator tree walker
2300 (walk_dominator_tree). */
2302 static unsigned int
2303 rewrite_into_ssa (void)
2305 bitmap_head *dfs;
2306 basic_block bb;
2307 unsigned i;
2309 /* Initialize operand data structures. */
2310 init_ssa_operands (cfun);
2312 /* Initialize internal data needed by the renamer. */
2313 init_ssa_renamer ();
2315 /* Initialize the set of interesting blocks. The callback
2316 mark_def_sites will add to this set those blocks that the renamer
2317 should process. */
2318 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
2319 bitmap_clear (interesting_blocks);
2321 /* Initialize dominance frontier. */
2322 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2323 FOR_EACH_BB_FN (bb, cfun)
2324 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2326 /* 1- Compute dominance frontiers. */
2327 calculate_dominance_info (CDI_DOMINATORS);
2328 compute_dominance_frontiers (dfs);
2330 /* 2- Find and mark definition sites. */
2331 mark_def_dom_walker (CDI_DOMINATORS).walk (cfun->cfg->x_entry_block_ptr);
2333 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2334 insert_phi_nodes (dfs);
2336 /* 4- Rename all the blocks. */
2337 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (cfun), REWRITE_ALL);
2339 /* Free allocated memory. */
2340 FOR_EACH_BB_FN (bb, cfun)
2341 bitmap_clear (&dfs[bb->index]);
2342 free (dfs);
2344 sbitmap_free (interesting_blocks);
2346 fini_ssa_renamer ();
2348 /* Try to get rid of all gimplifier generated temporaries by making
2349 its SSA names anonymous. This way we can garbage collect them
2350 all after removing unused locals which we do in our TODO. */
2351 for (i = 1; i < num_ssa_names; ++i)
2353 tree decl, name = ssa_name (i);
2354 if (!name
2355 || SSA_NAME_IS_DEFAULT_DEF (name))
2356 continue;
2357 decl = SSA_NAME_VAR (name);
2358 if (decl
2359 && TREE_CODE (decl) == VAR_DECL
2360 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2361 && DECL_IGNORED_P (decl))
2362 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2365 return 0;
2368 /* Gate for IPCP optimization. */
2370 static bool
2371 gate_into_ssa (void)
2373 /* Do nothing for funcions that was produced already in SSA form. */
2374 return !(cfun->curr_properties & PROP_ssa);
2377 namespace {
2379 const pass_data pass_data_build_ssa =
2381 GIMPLE_PASS, /* type */
2382 "ssa", /* name */
2383 OPTGROUP_NONE, /* optinfo_flags */
2384 true, /* has_gate */
2385 true, /* has_execute */
2386 TV_TREE_SSA_OTHER, /* tv_id */
2387 PROP_cfg, /* properties_required */
2388 PROP_ssa, /* properties_provided */
2389 0, /* properties_destroyed */
2390 0, /* todo_flags_start */
2391 ( TODO_verify_ssa | TODO_remove_unused_locals ), /* todo_flags_finish */
2394 class pass_build_ssa : public gimple_opt_pass
2396 public:
2397 pass_build_ssa (gcc::context *ctxt)
2398 : gimple_opt_pass (pass_data_build_ssa, ctxt)
2401 /* opt_pass methods: */
2402 bool gate () { return gate_into_ssa (); }
2403 unsigned int execute () { return rewrite_into_ssa (); }
2405 }; // class pass_build_ssa
2407 } // anon namespace
2409 gimple_opt_pass *
2410 make_pass_build_ssa (gcc::context *ctxt)
2412 return new pass_build_ssa (ctxt);
2416 /* Mark the definition of VAR at STMT and BB as interesting for the
2417 renamer. BLOCKS is the set of blocks that need updating. */
2419 static void
2420 mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2422 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2423 set_register_defs (stmt, true);
2425 if (insert_phi_p)
2427 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2429 set_def_block (var, bb, is_phi_p);
2431 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2432 site for both itself and all the old names replaced by it. */
2433 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2435 bitmap_iterator bi;
2436 unsigned i;
2437 bitmap set = names_replaced_by (var);
2438 if (set)
2439 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2440 set_def_block (ssa_name (i), bb, is_phi_p);
2446 /* Mark the use of VAR at STMT and BB as interesting for the
2447 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2448 nodes. */
2450 static inline void
2451 mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
2453 basic_block def_bb = gimple_bb (stmt);
2455 mark_block_for_update (def_bb);
2456 mark_block_for_update (bb);
2458 if (gimple_code (stmt) == GIMPLE_PHI)
2459 mark_phi_for_rewrite (def_bb, stmt);
2460 else
2462 set_rewrite_uses (stmt, true);
2464 if (is_gimple_debug (stmt))
2465 return;
2468 /* If VAR has not been defined in BB, then it is live-on-entry
2469 to BB. Note that we cannot just use the block holding VAR's
2470 definition because if VAR is one of the names in OLD_SSA_NAMES,
2471 it will have several definitions (itself and all the names that
2472 replace it). */
2473 if (insert_phi_p)
2475 struct def_blocks_d *db_p = get_def_blocks_for (get_common_info (var));
2476 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2477 set_livein_block (var, bb);
2482 /* Do a dominator walk starting at BB processing statements that
2483 reference symbols in SSA operands. This is very similar to
2484 mark_def_sites, but the scan handles statements whose operands may
2485 already be SSA names.
2487 If INSERT_PHI_P is true, mark those uses as live in the
2488 corresponding block. This is later used by the PHI placement
2489 algorithm to make PHI pruning decisions.
2491 FIXME. Most of this would be unnecessary if we could associate a
2492 symbol to all the SSA names that reference it. But that
2493 sounds like it would be expensive to maintain. Still, it
2494 would be interesting to see if it makes better sense to do
2495 that. */
2497 static void
2498 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2500 basic_block son;
2501 gimple_stmt_iterator si;
2502 edge e;
2503 edge_iterator ei;
2505 mark_block_for_update (bb);
2507 /* Process PHI nodes marking interesting those that define or use
2508 the symbols that we are interested in. */
2509 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
2511 gimple phi = gsi_stmt (si);
2512 tree lhs_sym, lhs = gimple_phi_result (phi);
2514 if (TREE_CODE (lhs) == SSA_NAME
2515 && (! virtual_operand_p (lhs)
2516 || ! cfun->gimple_df->rename_vops))
2517 continue;
2519 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2520 mark_for_renaming (lhs_sym);
2521 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2523 /* Mark the uses in phi nodes as interesting. It would be more correct
2524 to process the arguments of the phi nodes of the successor edges of
2525 BB at the end of prepare_block_for_update, however, that turns out
2526 to be significantly more expensive. Doing it here is conservatively
2527 correct -- it may only cause us to believe a value to be live in a
2528 block that also contains its definition, and thus insert a few more
2529 phi nodes for it. */
2530 FOR_EACH_EDGE (e, ei, bb->preds)
2531 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2534 /* Process the statements. */
2535 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2537 gimple stmt;
2538 ssa_op_iter i;
2539 use_operand_p use_p;
2540 def_operand_p def_p;
2542 stmt = gsi_stmt (si);
2544 if (cfun->gimple_df->rename_vops
2545 && gimple_vuse (stmt))
2547 tree use = gimple_vuse (stmt);
2548 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2549 mark_for_renaming (sym);
2550 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2553 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2555 tree use = USE_FROM_PTR (use_p);
2556 if (!DECL_P (use))
2557 continue;
2558 mark_for_renaming (use);
2559 mark_use_interesting (use, stmt, bb, insert_phi_p);
2562 if (cfun->gimple_df->rename_vops
2563 && gimple_vdef (stmt))
2565 tree def = gimple_vdef (stmt);
2566 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2567 mark_for_renaming (sym);
2568 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2571 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2573 tree def = DEF_FROM_PTR (def_p);
2574 if (!DECL_P (def))
2575 continue;
2576 mark_for_renaming (def);
2577 mark_def_interesting (def, stmt, bb, insert_phi_p);
2581 /* Now visit all the blocks dominated by BB. */
2582 for (son = first_dom_son (CDI_DOMINATORS, bb);
2583 son;
2584 son = next_dom_son (CDI_DOMINATORS, son))
2585 prepare_block_for_update (son, insert_phi_p);
2589 /* Helper for prepare_names_to_update. Mark all the use sites for
2590 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2591 prepare_names_to_update. */
2593 static void
2594 prepare_use_sites_for (tree name, bool insert_phi_p)
2596 use_operand_p use_p;
2597 imm_use_iterator iter;
2599 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2601 gimple stmt = USE_STMT (use_p);
2602 basic_block bb = gimple_bb (stmt);
2604 if (gimple_code (stmt) == GIMPLE_PHI)
2606 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2607 edge e = gimple_phi_arg_edge (stmt, ix);
2608 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2610 else
2612 /* For regular statements, mark this as an interesting use
2613 for NAME. */
2614 mark_use_interesting (name, stmt, bb, insert_phi_p);
2620 /* Helper for prepare_names_to_update. Mark the definition site for
2621 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2622 prepare_names_to_update. */
2624 static void
2625 prepare_def_site_for (tree name, bool insert_phi_p)
2627 gimple stmt;
2628 basic_block bb;
2630 gcc_checking_assert (names_to_release == NULL
2631 || !bitmap_bit_p (names_to_release,
2632 SSA_NAME_VERSION (name)));
2634 stmt = SSA_NAME_DEF_STMT (name);
2635 bb = gimple_bb (stmt);
2636 if (bb)
2638 gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2639 mark_block_for_update (bb);
2640 mark_def_interesting (name, stmt, bb, insert_phi_p);
2645 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2646 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2647 PHI nodes for newly created names. */
2649 static void
2650 prepare_names_to_update (bool insert_phi_p)
2652 unsigned i = 0;
2653 bitmap_iterator bi;
2654 sbitmap_iterator sbi;
2656 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2657 remove it from NEW_SSA_NAMES so that we don't try to visit its
2658 defining basic block (which most likely doesn't exist). Notice
2659 that we cannot do the same with names in OLD_SSA_NAMES because we
2660 want to replace existing instances. */
2661 if (names_to_release)
2662 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2663 bitmap_clear_bit (new_ssa_names, i);
2665 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2666 names may be considered to be live-in on blocks that contain
2667 definitions for their replacements. */
2668 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2669 prepare_def_site_for (ssa_name (i), insert_phi_p);
2671 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2672 OLD_SSA_NAMES, but we have to ignore its definition site. */
2673 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2675 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2676 prepare_def_site_for (ssa_name (i), insert_phi_p);
2677 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2682 /* Dump all the names replaced by NAME to FILE. */
2684 void
2685 dump_names_replaced_by (FILE *file, tree name)
2687 unsigned i;
2688 bitmap old_set;
2689 bitmap_iterator bi;
2691 print_generic_expr (file, name, 0);
2692 fprintf (file, " -> { ");
2694 old_set = names_replaced_by (name);
2695 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2697 print_generic_expr (file, ssa_name (i), 0);
2698 fprintf (file, " ");
2701 fprintf (file, "}\n");
2705 /* Dump all the names replaced by NAME to stderr. */
2707 DEBUG_FUNCTION void
2708 debug_names_replaced_by (tree name)
2710 dump_names_replaced_by (stderr, name);
2714 /* Dump SSA update information to FILE. */
2716 void
2717 dump_update_ssa (FILE *file)
2719 unsigned i = 0;
2720 bitmap_iterator bi;
2722 if (!need_ssa_update_p (cfun))
2723 return;
2725 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2727 sbitmap_iterator sbi;
2729 fprintf (file, "\nSSA replacement table\n");
2730 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2731 "O_1, ..., O_j\n\n");
2733 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2734 dump_names_replaced_by (file, ssa_name (i));
2737 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2739 fprintf (file, "\nSymbols to be put in SSA form\n");
2740 dump_decl_set (file, symbols_to_rename_set);
2741 fprintf (file, "\n");
2744 if (names_to_release && !bitmap_empty_p (names_to_release))
2746 fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2747 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2749 print_generic_expr (file, ssa_name (i), 0);
2750 fprintf (file, " ");
2752 fprintf (file, "\n");
2757 /* Dump SSA update information to stderr. */
2759 DEBUG_FUNCTION void
2760 debug_update_ssa (void)
2762 dump_update_ssa (stderr);
2766 /* Initialize data structures used for incremental SSA updates. */
2768 static void
2769 init_update_ssa (struct function *fn)
2771 /* Reserve more space than the current number of names. The calls to
2772 add_new_name_mapping are typically done after creating new SSA
2773 names, so we'll need to reallocate these arrays. */
2774 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2775 bitmap_clear (old_ssa_names);
2777 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2778 bitmap_clear (new_ssa_names);
2780 bitmap_obstack_initialize (&update_ssa_obstack);
2782 names_to_release = NULL;
2783 update_ssa_initialized_fn = fn;
2787 /* Deallocate data structures used for incremental SSA updates. */
2789 void
2790 delete_update_ssa (void)
2792 unsigned i;
2793 bitmap_iterator bi;
2795 sbitmap_free (old_ssa_names);
2796 old_ssa_names = NULL;
2798 sbitmap_free (new_ssa_names);
2799 new_ssa_names = NULL;
2801 BITMAP_FREE (symbols_to_rename_set);
2802 symbols_to_rename_set = NULL;
2803 symbols_to_rename.release ();
2805 if (names_to_release)
2807 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2808 release_ssa_name (ssa_name (i));
2809 BITMAP_FREE (names_to_release);
2812 clear_ssa_name_info ();
2814 fini_ssa_renamer ();
2816 if (blocks_with_phis_to_rewrite)
2817 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2819 gimple_vec phis = phis_to_rewrite[i];
2820 phis.release ();
2821 phis_to_rewrite[i].create (0);
2824 BITMAP_FREE (blocks_with_phis_to_rewrite);
2825 BITMAP_FREE (blocks_to_update);
2827 update_ssa_initialized_fn = NULL;
2831 /* Create a new name for OLD_NAME in statement STMT and replace the
2832 operand pointed to by DEF_P with the newly created name. If DEF_P
2833 is NULL then STMT should be a GIMPLE assignment.
2834 Return the new name and register the replacement mapping <NEW, OLD> in
2835 update_ssa's tables. */
2837 tree
2838 create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
2840 tree new_name;
2842 timevar_push (TV_TREE_SSA_INCREMENTAL);
2844 if (!update_ssa_initialized_fn)
2845 init_update_ssa (cfun);
2847 gcc_assert (update_ssa_initialized_fn == cfun);
2849 new_name = duplicate_ssa_name (old_name, stmt);
2850 if (def)
2851 SET_DEF (def, new_name);
2852 else
2853 gimple_assign_set_lhs (stmt, new_name);
2855 if (gimple_code (stmt) == GIMPLE_PHI)
2857 basic_block bb = gimple_bb (stmt);
2859 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2860 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2863 add_new_name_mapping (new_name, old_name);
2865 /* For the benefit of passes that will be updating the SSA form on
2866 their own, set the current reaching definition of OLD_NAME to be
2867 NEW_NAME. */
2868 get_ssa_name_ann (old_name)->info.current_def = new_name;
2870 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2872 return new_name;
2876 /* Mark virtual operands of FN for renaming by update_ssa. */
2878 void
2879 mark_virtual_operands_for_renaming (struct function *fn)
2881 fn->gimple_df->ssa_renaming_needed = 1;
2882 fn->gimple_df->rename_vops = 1;
2885 /* Replace all uses of NAME by underlying variable and mark it
2886 for renaming. This assumes the defining statement of NAME is
2887 going to be removed. */
2889 void
2890 mark_virtual_operand_for_renaming (tree name)
2892 tree name_var = SSA_NAME_VAR (name);
2893 bool used = false;
2894 imm_use_iterator iter;
2895 use_operand_p use_p;
2896 gimple stmt;
2898 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
2899 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
2901 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2902 SET_USE (use_p, name_var);
2903 used = true;
2905 if (used)
2906 mark_virtual_operands_for_renaming (cfun);
2909 /* Replace all uses of the virtual PHI result by its underlying variable
2910 and mark it for renaming. This assumes the PHI node is going to be
2911 removed. */
2913 void
2914 mark_virtual_phi_result_for_renaming (gimple phi)
2916 if (dump_file && (dump_flags & TDF_DETAILS))
2918 fprintf (dump_file, "Marking result for renaming : ");
2919 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
2920 fprintf (dump_file, "\n");
2923 mark_virtual_operand_for_renaming (gimple_phi_result (phi));
2926 /* Return true if there is any work to be done by update_ssa
2927 for function FN. */
2929 bool
2930 need_ssa_update_p (struct function *fn)
2932 gcc_assert (fn != NULL);
2933 return (update_ssa_initialized_fn == fn
2934 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
2937 /* Return true if name N has been registered in the replacement table. */
2939 bool
2940 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
2942 if (!update_ssa_initialized_fn)
2943 return false;
2945 gcc_assert (update_ssa_initialized_fn == cfun);
2947 return is_new_name (n) || is_old_name (n);
2951 /* Mark NAME to be released after update_ssa has finished. */
2953 void
2954 release_ssa_name_after_update_ssa (tree name)
2956 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
2958 if (names_to_release == NULL)
2959 names_to_release = BITMAP_ALLOC (NULL);
2961 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2965 /* Insert new PHI nodes to replace VAR. DFS contains dominance
2966 frontier information. BLOCKS is the set of blocks to be updated.
2968 This is slightly different than the regular PHI insertion
2969 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
2970 real names (i.e., GIMPLE registers) are inserted:
2972 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2973 nodes inside the region affected by the block that defines VAR
2974 and the blocks that define all its replacements. All these
2975 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2977 First, we compute the entry point to the region (ENTRY). This is
2978 given by the nearest common dominator to all the definition
2979 blocks. When computing the iterated dominance frontier (IDF), any
2980 block not strictly dominated by ENTRY is ignored.
2982 We then call the standard PHI insertion algorithm with the pruned
2983 IDF.
2985 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2986 names is not pruned. PHI nodes are inserted at every IDF block. */
2988 static void
2989 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
2990 unsigned update_flags)
2992 basic_block entry;
2993 struct def_blocks_d *db;
2994 bitmap idf, pruned_idf;
2995 bitmap_iterator bi;
2996 unsigned i;
2998 if (TREE_CODE (var) == SSA_NAME)
2999 gcc_checking_assert (is_old_name (var));
3000 else
3001 gcc_checking_assert (marked_for_renaming (var));
3003 /* Get all the definition sites for VAR. */
3004 db = find_def_blocks_for (var);
3006 /* No need to do anything if there were no definitions to VAR. */
3007 if (db == NULL || bitmap_empty_p (db->def_blocks))
3008 return;
3010 /* Compute the initial iterated dominance frontier. */
3011 idf = compute_idf (db->def_blocks, dfs);
3012 pruned_idf = BITMAP_ALLOC (NULL);
3014 if (TREE_CODE (var) == SSA_NAME)
3016 if (update_flags == TODO_update_ssa)
3018 /* If doing regular SSA updates for GIMPLE registers, we are
3019 only interested in IDF blocks dominated by the nearest
3020 common dominator of all the definition blocks. */
3021 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3022 db->def_blocks);
3023 if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3024 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3025 if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3026 && dominated_by_p (CDI_DOMINATORS,
3027 BASIC_BLOCK_FOR_FN (cfun, i), entry))
3028 bitmap_set_bit (pruned_idf, i);
3030 else
3032 /* Otherwise, do not prune the IDF for VAR. */
3033 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3034 bitmap_copy (pruned_idf, idf);
3037 else
3039 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3040 for the first time, so we need to compute the full IDF for
3041 it. */
3042 bitmap_copy (pruned_idf, idf);
3045 if (!bitmap_empty_p (pruned_idf))
3047 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3048 are included in the region to be updated. The feeding blocks
3049 are important to guarantee that the PHI arguments are renamed
3050 properly. */
3052 /* FIXME, this is not needed if we are updating symbols. We are
3053 already starting at the ENTRY block anyway. */
3054 bitmap_ior_into (blocks, pruned_idf);
3055 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3057 edge e;
3058 edge_iterator ei;
3059 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3061 FOR_EACH_EDGE (e, ei, bb->preds)
3062 if (e->src->index >= 0)
3063 bitmap_set_bit (blocks, e->src->index);
3066 insert_phi_nodes_for (var, pruned_idf, true);
3069 BITMAP_FREE (pruned_idf);
3070 BITMAP_FREE (idf);
3073 /* Sort symbols_to_rename after their DECL_UID. */
3075 static int
3076 insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3078 const_tree syma = *(const const_tree *)a;
3079 const_tree symb = *(const const_tree *)b;
3080 if (DECL_UID (syma) == DECL_UID (symb))
3081 return 0;
3082 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3085 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3086 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3088 1- The names in OLD_SSA_NAMES dominated by the definitions of
3089 NEW_SSA_NAMES are all re-written to be reached by the
3090 appropriate definition from NEW_SSA_NAMES.
3092 2- If needed, new PHI nodes are added to the iterated dominance
3093 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3095 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3096 calling create_new_def_for to create new defs for names that the
3097 caller wants to replace.
3099 The caller cretaes the new names to be inserted and the names that need
3100 to be replaced by calling create_new_def_for for each old definition
3101 to be replaced. Note that the function assumes that the
3102 new defining statement has already been inserted in the IL.
3104 For instance, given the following code:
3106 1 L0:
3107 2 x_1 = PHI (0, x_5)
3108 3 if (x_1 < 10)
3109 4 if (x_1 > 7)
3110 5 y_2 = 0
3111 6 else
3112 7 y_3 = x_1 + x_7
3113 8 endif
3114 9 x_5 = x_1 + 1
3115 10 goto L0;
3116 11 endif
3118 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3120 1 L0:
3121 2 x_1 = PHI (0, x_5)
3122 3 if (x_1 < 10)
3123 4 x_10 = ...
3124 5 if (x_1 > 7)
3125 6 y_2 = 0
3126 7 else
3127 8 x_11 = ...
3128 9 y_3 = x_1 + x_7
3129 10 endif
3130 11 x_5 = x_1 + 1
3131 12 goto L0;
3132 13 endif
3134 We want to replace all the uses of x_1 with the new definitions of
3135 x_10 and x_11. Note that the only uses that should be replaced are
3136 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3137 *not* be replaced (this is why we cannot just mark symbol 'x' for
3138 renaming).
3140 Additionally, we may need to insert a PHI node at line 11 because
3141 that is a merge point for x_10 and x_11. So the use of x_1 at line
3142 11 will be replaced with the new PHI node. The insertion of PHI
3143 nodes is optional. They are not strictly necessary to preserve the
3144 SSA form, and depending on what the caller inserted, they may not
3145 even be useful for the optimizers. UPDATE_FLAGS controls various
3146 aspects of how update_ssa operates, see the documentation for
3147 TODO_update_ssa*. */
3149 void
3150 update_ssa (unsigned update_flags)
3152 basic_block bb, start_bb;
3153 bitmap_iterator bi;
3154 unsigned i = 0;
3155 bool insert_phi_p;
3156 sbitmap_iterator sbi;
3157 tree sym;
3159 /* Only one update flag should be set. */
3160 gcc_assert (update_flags == TODO_update_ssa
3161 || update_flags == TODO_update_ssa_no_phi
3162 || update_flags == TODO_update_ssa_full_phi
3163 || update_flags == TODO_update_ssa_only_virtuals);
3165 if (!need_ssa_update_p (cfun))
3166 return;
3168 timevar_push (TV_TREE_SSA_INCREMENTAL);
3170 if (dump_file && (dump_flags & TDF_DETAILS))
3171 fprintf (dump_file, "\nUpdating SSA:\n");
3173 if (!update_ssa_initialized_fn)
3174 init_update_ssa (cfun);
3175 else if (update_flags == TODO_update_ssa_only_virtuals)
3177 /* If we only need to update virtuals, remove all the mappings for
3178 real names before proceeding. The caller is responsible for
3179 having dealt with the name mappings before calling update_ssa. */
3180 bitmap_clear (old_ssa_names);
3181 bitmap_clear (new_ssa_names);
3184 gcc_assert (update_ssa_initialized_fn == cfun);
3186 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3187 if (!phis_to_rewrite.exists ())
3188 phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3189 blocks_to_update = BITMAP_ALLOC (NULL);
3191 /* Ensure that the dominance information is up-to-date. */
3192 calculate_dominance_info (CDI_DOMINATORS);
3194 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3196 /* If there are names defined in the replacement table, prepare
3197 definition and use sites for all the names in NEW_SSA_NAMES and
3198 OLD_SSA_NAMES. */
3199 if (bitmap_first_set_bit (new_ssa_names) >= 0)
3201 prepare_names_to_update (insert_phi_p);
3203 /* If all the names in NEW_SSA_NAMES had been marked for
3204 removal, and there are no symbols to rename, then there's
3205 nothing else to do. */
3206 if (bitmap_first_set_bit (new_ssa_names) < 0
3207 && !cfun->gimple_df->ssa_renaming_needed)
3208 goto done;
3211 /* Next, determine the block at which to start the renaming process. */
3212 if (cfun->gimple_df->ssa_renaming_needed)
3214 /* If we rename bare symbols initialize the mapping to
3215 auxiliar info we need to keep track of. */
3216 var_infos.create (47);
3218 /* If we have to rename some symbols from scratch, we need to
3219 start the process at the root of the CFG. FIXME, it should
3220 be possible to determine the nearest block that had a
3221 definition for each of the symbols that are marked for
3222 updating. For now this seems more work than it's worth. */
3223 start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3225 /* Traverse the CFG looking for existing definitions and uses of
3226 symbols in SSA operands. Mark interesting blocks and
3227 statements and set local live-in information for the PHI
3228 placement heuristics. */
3229 prepare_block_for_update (start_bb, insert_phi_p);
3231 #ifdef ENABLE_CHECKING
3232 for (i = 1; i < num_ssa_names; ++i)
3234 tree name = ssa_name (i);
3235 if (!name
3236 || virtual_operand_p (name))
3237 continue;
3239 /* For all but virtual operands, which do not have SSA names
3240 with overlapping life ranges, ensure that symbols marked
3241 for renaming do not have existing SSA names associated with
3242 them as we do not re-write them out-of-SSA before going
3243 into SSA for the remaining symbol uses. */
3244 if (marked_for_renaming (SSA_NAME_VAR (name)))
3246 fprintf (stderr, "Existing SSA name for symbol marked for "
3247 "renaming: ");
3248 print_generic_expr (stderr, name, TDF_SLIM);
3249 fprintf (stderr, "\n");
3250 internal_error ("SSA corruption");
3253 #endif
3255 else
3257 /* Otherwise, the entry block to the region is the nearest
3258 common dominator for the blocks in BLOCKS. */
3259 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3260 blocks_to_update);
3263 /* If requested, insert PHI nodes at the iterated dominance frontier
3264 of every block, creating new definitions for names in OLD_SSA_NAMES
3265 and for symbols found. */
3266 if (insert_phi_p)
3268 bitmap_head *dfs;
3270 /* If the caller requested PHI nodes to be added, compute
3271 dominance frontiers. */
3272 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3273 FOR_EACH_BB_FN (bb, cfun)
3274 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3275 compute_dominance_frontiers (dfs);
3277 if (bitmap_first_set_bit (old_ssa_names) >= 0)
3279 sbitmap_iterator sbi;
3281 /* insert_update_phi_nodes_for will call add_new_name_mapping
3282 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3283 will grow while we are traversing it (but it will not
3284 gain any new members). Copy OLD_SSA_NAMES to a temporary
3285 for traversal. */
3286 sbitmap tmp = sbitmap_alloc (SBITMAP_SIZE (old_ssa_names));
3287 bitmap_copy (tmp, old_ssa_names);
3288 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3289 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3290 update_flags);
3291 sbitmap_free (tmp);
3294 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3295 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3296 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3297 update_flags);
3299 FOR_EACH_BB_FN (bb, cfun)
3300 bitmap_clear (&dfs[bb->index]);
3301 free (dfs);
3303 /* Insertion of PHI nodes may have added blocks to the region.
3304 We need to re-compute START_BB to include the newly added
3305 blocks. */
3306 if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3307 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3308 blocks_to_update);
3311 /* Reset the current definition for name and symbol before renaming
3312 the sub-graph. */
3313 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3314 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3316 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3317 get_var_info (sym)->info.current_def = NULL_TREE;
3319 /* Now start the renaming process at START_BB. */
3320 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3321 bitmap_clear (interesting_blocks);
3322 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3323 bitmap_set_bit (interesting_blocks, i);
3325 rewrite_blocks (start_bb, REWRITE_UPDATE);
3327 sbitmap_free (interesting_blocks);
3329 /* Debugging dumps. */
3330 if (dump_file)
3332 int c;
3333 unsigned i;
3335 dump_update_ssa (dump_file);
3337 fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3338 start_bb->index);
3340 c = 0;
3341 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3342 c++;
3343 fprintf (dump_file, "Number of blocks in CFG: %d\n",
3344 last_basic_block_for_fn (cfun));
3345 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3346 c, PERCENT (c, last_basic_block_for_fn (cfun)));
3348 if (dump_flags & TDF_DETAILS)
3350 fprintf (dump_file, "Affected blocks:");
3351 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3352 fprintf (dump_file, " %u", i);
3353 fprintf (dump_file, "\n");
3356 fprintf (dump_file, "\n\n");
3359 /* Free allocated memory. */
3360 done:
3361 delete_update_ssa ();
3363 timevar_pop (TV_TREE_SSA_INCREMENTAL);