1/* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "rtl.h"
26#include "tree.h"
27#include "gimple.h"
28#include "tree-pass.h"
29#include "ssa.h"
30#include "gimple-pretty-print.h"
31#include "diagnostic-core.h"
32#include "langhooks.h"
33#include "cfganal.h"
34#include "gimple-iterator.h"
35#include "tree-cfg.h"
36#include "tree-into-ssa.h"
37#include "tree-dfa.h"
38#include "tree-ssa.h"
39#include "domwalk.h"
40#include "statistics.h"
41#include "stringpool.h"
42#include "attribs.h"
43#include "asan.h"
44
45#define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
46
47/* This file builds the SSA form for a function as described in:
48 R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
49 Computing Static Single Assignment Form and the Control Dependence
50 Graph. ACM Transactions on Programming Languages and Systems,
51 13(4):451-490, October 1991. */
52
53/* Structure to map a variable VAR to the set of blocks that contain
54 definitions for VAR. */
55struct def_blocks
56{
57 /* Blocks that contain definitions of VAR. Bit I will be set if the
58 Ith block contains a definition of VAR. */
59 bitmap def_blocks;
60
61 /* Blocks that contain a PHI node for VAR. */
62 bitmap phi_blocks;
63
64 /* Blocks where VAR is live-on-entry. Similar semantics as
65 DEF_BLOCKS. */
66 bitmap livein_blocks;
67};
68
69/* Stack of trees used to restore the global currdefs to its original
70 state after completing rewriting of a block and its dominator
71 children. Its elements have the following properties:
72
73 - An SSA_NAME (N) indicates that the current definition of the
74 underlying variable should be set to the given SSA_NAME. If the
75 symbol associated with the SSA_NAME is not a GIMPLE register, the
76 next slot in the stack must be a _DECL node (SYM). In this case,
77 the name N in the previous slot is the current reaching
78 definition for SYM.
79
80 - A _DECL node indicates that the underlying variable has no
81 current definition.
82
83 - A NULL node at the top entry is used to mark the last slot
84 associated with the current block. */
85static vec<tree> block_defs_stack;
86
87
88/* Set of existing SSA names being replaced by update_ssa. */
89static sbitmap old_ssa_names;
90
91/* Set of new SSA names being added by update_ssa. Note that both
92 NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
93 the operations done on them are presence tests. */
94static sbitmap new_ssa_names;
95
96static sbitmap interesting_blocks;
97
98/* Set of SSA names that have been marked to be released after they
99 were registered in the replacement table. They will be finally
100 released after we finish updating the SSA web. */
101bitmap names_to_release;
102
103/* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
104 the to basic block with index I. Allocated once per compilation, *not*
105 released between different functions. */
106static vec< vec<gphi *> > phis_to_rewrite;
107
108/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
109static bitmap blocks_with_phis_to_rewrite;
110
111/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
112 to grow as the callers to create_new_def_for will create new names on
113 the fly.
114 FIXME. Currently set to 1/3 to avoid frequent reallocations but still
115 need to find a reasonable growth strategy. */
116#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
117
118
119/* The function the SSA updating data structures have been initialized for.
120 NULL if they need to be initialized by create_new_def_for. */
121static struct function *update_ssa_initialized_fn = NULL;
122
123/* Global data to attach to the main dominator walk structure. */
124struct mark_def_sites_global_data
125{
126 /* This bitmap contains the variables which are set before they
127 are used in a basic block. */
128 bitmap kills;
129};
130
131/* It is advantageous to avoid things like life analysis for variables which
132 do not need PHI nodes. This enum describes whether or not a particular
133 variable may need a PHI node. */
134
135enum need_phi_state {
136 /* This is the default. If we are still in this state after finding
137 all the definition and use sites, then we will assume the variable
138 needs PHI nodes. This is probably an overly conservative assumption. */
139 NEED_PHI_STATE_UNKNOWN,
140
141 /* This state indicates that we have seen one or more sets of the
142 variable in a single basic block and that the sets dominate all
143 uses seen so far. If after finding all definition and use sites
144 we are still in this state, then the variable does not need any
145 PHI nodes. */
146 NEED_PHI_STATE_NO,
147
148 /* This state indicates that we have either seen multiple definitions of
149 the variable in multiple blocks, or that we encountered a use in a
150 block that was not dominated by the block containing the set(s) of
151 this variable. This variable is assumed to need PHI nodes. */
152 NEED_PHI_STATE_MAYBE
153};
154
155/* Information stored for both SSA names and decls. */
156struct common_info
157{
158 /* This field indicates whether or not the variable may need PHI nodes.
159 See the enum's definition for more detailed information about the
160 states. */
161 ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
162
163 /* The current reaching definition replacing this var. */
164 tree current_def;
165
166 /* Definitions for this var. */
167 struct def_blocks def_blocks;
168};
169
170/* Information stored for decls. */
171struct var_info
172{
173 /* The variable. */
174 tree var;
175
176 /* Information stored for both SSA names and decls. */
177 common_info info;
178};
179
180
181/* VAR_INFOS hashtable helpers. */
182
183struct var_info_hasher : free_ptr_hash <var_info>
184{
185 static inline hashval_t hash (const value_type &);
186 static inline bool equal (const value_type &, const compare_type &);
187};
188
189inline hashval_t
190var_info_hasher::hash (const value_type &p)
191{
192 return DECL_UID (p->var);
193}
194
195inline bool
196var_info_hasher::equal (const value_type &p1, const compare_type &p2)
197{
198 return p1->var == p2->var;
199}
200
201
202/* Each entry in VAR_INFOS contains an element of type STRUCT
203 VAR_INFO_D. */
204static hash_table<var_info_hasher> *var_infos;
205
206
207/* Information stored for SSA names. */
208struct ssa_name_info
209{
210 /* Age of this record (so that info_for_ssa_name table can be cleared
211 quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
212 are assumed to be null. */
213 unsigned age;
214
215 /* Replacement mappings, allocated from update_ssa_obstack. */
216 bitmap repl_set;
217
218 /* Information stored for both SSA names and decls. */
219 common_info info;
220};
221
222static vec<ssa_name_info *> info_for_ssa_name;
223static unsigned current_info_for_ssa_name_age;
224
225static bitmap_obstack update_ssa_obstack;
226
227/* The set of blocks affected by update_ssa. */
228static bitmap blocks_to_update;
229
230/* The main entry point to the SSA renamer (rewrite_blocks) may be
231 called several times to do different, but related, tasks.
232 Initially, we need it to rename the whole program into SSA form.
233 At other times, we may need it to only rename into SSA newly
234 exposed symbols. Finally, we can also call it to incrementally fix
235 an already built SSA web. */
236enum rewrite_mode {
237 /* Convert the whole function into SSA form. */
238 REWRITE_ALL,
239
240 /* Incrementally update the SSA web by replacing existing SSA
241 names with new ones. See update_ssa for details. */
242 REWRITE_UPDATE
243};
244
245/* The set of symbols we ought to re-write into SSA form in update_ssa. */
246static bitmap symbols_to_rename_set;
247static vec<tree> symbols_to_rename;
248
249/* Mark SYM for renaming. */
250
251static void
252mark_for_renaming (tree sym)
253{
254 if (!symbols_to_rename_set)
255 symbols_to_rename_set = BITMAP_ALLOC (NULL);
256 if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
257 symbols_to_rename.safe_push (sym);
258}
259
260/* Return true if SYM is marked for renaming. */
261
262static bool
263marked_for_renaming (tree sym)
264{
265 if (!symbols_to_rename_set || sym == NULL_TREE)
266 return false;
267 return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
268}
269
270
271/* Return true if STMT needs to be rewritten. When renaming a subset
272 of the variables, not all statements will be processed. This is
273 decided in mark_def_sites. */
274
275static inline bool
276rewrite_uses_p (gimple *stmt)
277{
278 return gimple_visited_p (stmt);
279}
280
281
282/* Set the rewrite marker on STMT to the value given by REWRITE_P. */
283
284static inline void
285set_rewrite_uses (gimple *stmt, bool rewrite_p)
286{
287 gimple_set_visited (stmt, rewrite_p);
288}
289
290
291/* Return true if the DEFs created by statement STMT should be
292 registered when marking new definition sites. This is slightly
293 different than rewrite_uses_p: it's used by update_ssa to
294 distinguish statements that need to have both uses and defs
295 processed from those that only need to have their defs processed.
296 Statements that define new SSA names only need to have their defs
297 registered, but they don't need to have their uses renamed. */
298
299static inline bool
300register_defs_p (gimple *stmt)
301{
302 return gimple_plf (stmt, GF_PLF_1) != 0;
303}
304
305
306/* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
307
308static inline void
309set_register_defs (gimple *stmt, bool register_defs_p)
310{
311 gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
312}
313
314
315/* Get the information associated with NAME. */
316
317static inline ssa_name_info *
318get_ssa_name_ann (tree name)
319{
320 unsigned ver = SSA_NAME_VERSION (name);
321 unsigned len = info_for_ssa_name.length ();
322 struct ssa_name_info *info;
323
324 /* Re-allocate the vector at most once per update/into-SSA. */
325 if (ver >= len)
326 info_for_ssa_name.safe_grow_cleared (num_ssa_names);
327
328 /* But allocate infos lazily. */
329 info = info_for_ssa_name[ver];
330 if (!info)
331 {
332 info = XCNEW (struct ssa_name_info);
333 info->age = current_info_for_ssa_name_age;
334 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
335 info_for_ssa_name[ver] = info;
336 }
337
338 if (info->age < current_info_for_ssa_name_age)
339 {
340 info->age = current_info_for_ssa_name_age;
341 info->repl_set = NULL;
342 info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
343 info->info.current_def = NULL_TREE;
344 info->info.def_blocks.def_blocks = NULL;
345 info->info.def_blocks.phi_blocks = NULL;
346 info->info.def_blocks.livein_blocks = NULL;
347 }
348
349 return info;
350}
351
352/* Return and allocate the auxiliar information for DECL. */
353
354static inline var_info *
355get_var_info (tree decl)
356{
357 var_info vi;
358 var_info **slot;
359 vi.var = decl;
360 slot = var_infos->find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
361 if (*slot == NULL)
362 {
363 var_info *v = XCNEW (var_info);
364 v->var = decl;
365 *slot = v;
366 return v;
367 }
368 return *slot;
369}
370
371
372/* Clears info for SSA names. */
373
374static void
375clear_ssa_name_info (void)
376{
377 current_info_for_ssa_name_age++;
378
379 /* If current_info_for_ssa_name_age wraps we use stale information.
380 Asser that this does not happen. */
381 gcc_assert (current_info_for_ssa_name_age != 0);
382}
383
384
385/* Get access to the auxiliar information stored per SSA name or decl. */
386
387static inline common_info *
388get_common_info (tree var)
389{
390 if (TREE_CODE (var) == SSA_NAME)
391 return &get_ssa_name_ann (var)->info;
392 else
393 return &get_var_info (var)->info;
394}
395
396
397/* Return the current definition for VAR. */
398
399tree
400get_current_def (tree var)
401{
402 return get_common_info (var)->current_def;
403}
404
405
406/* Sets current definition of VAR to DEF. */
407
408void
409set_current_def (tree var, tree def)
410{
411 get_common_info (var)->current_def = def;
412}
413
414/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
415 all statements in basic block BB. */
416
417static void
418initialize_flags_in_bb (basic_block bb)
419{
420 gimple *stmt;
421 gimple_stmt_iterator gsi;
422
423 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
424 {
425 gimple *phi = gsi_stmt (gsi);
426 set_rewrite_uses (phi, false);
427 set_register_defs (phi, false);
428 }
429
430 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
431 {
432 stmt = gsi_stmt (gsi);
433
434 /* We are going to use the operand cache API, such as
435 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
436 cache for each statement should be up-to-date. */
437 gcc_checking_assert (!gimple_modified_p (stmt));
438 set_rewrite_uses (stmt, false);
439 set_register_defs (stmt, false);
440 }
441}
442
443/* Mark block BB as interesting for update_ssa. */
444
445static void
446mark_block_for_update (basic_block bb)
447{
448 gcc_checking_assert (blocks_to_update != NULL);
449 if (!bitmap_set_bit (blocks_to_update, bb->index))
450 return;
451 initialize_flags_in_bb (bb);
452}
453
454/* Return the set of blocks where variable VAR is defined and the blocks
455 where VAR is live on entry (livein). If no entry is found in
456 DEF_BLOCKS, a new one is created and returned. */
457
458static inline def_blocks *
459get_def_blocks_for (common_info *info)
460{
461 def_blocks *db_p = &info->def_blocks;
462 if (!db_p->def_blocks)
463 {
464 db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
465 db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
466 db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
467 }
468
469 return db_p;
470}
471
472
473/* Mark block BB as the definition site for variable VAR. PHI_P is true if
474 VAR is defined by a PHI node. */
475
476static void
477set_def_block (tree var, basic_block bb, bool phi_p)
478{
479 def_blocks *db_p;
480 common_info *info;
481
482 info = get_common_info (var);
483 db_p = get_def_blocks_for (info);
484
485 /* Set the bit corresponding to the block where VAR is defined. */
486 bitmap_set_bit (db_p->def_blocks, bb->index);
487 if (phi_p)
488 bitmap_set_bit (db_p->phi_blocks, bb->index);
489
490 /* Keep track of whether or not we may need to insert PHI nodes.
491
492 If we are in the UNKNOWN state, then this is the first definition
493 of VAR. Additionally, we have not seen any uses of VAR yet, so
494 we do not need a PHI node for this variable at this time (i.e.,
495 transition to NEED_PHI_STATE_NO).
496
497 If we are in any other state, then we either have multiple definitions
498 of this variable occurring in different blocks or we saw a use of the
499 variable which was not dominated by the block containing the
500 definition(s). In this case we may need a PHI node, so enter
501 state NEED_PHI_STATE_MAYBE. */
502 if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
503 info->need_phi_state = NEED_PHI_STATE_NO;
504 else
505 info->need_phi_state = NEED_PHI_STATE_MAYBE;
506}
507
508
509/* Mark block BB as having VAR live at the entry to BB. */
510
511static void
512set_livein_block (tree var, basic_block bb)
513{
514 common_info *info;
515 def_blocks *db_p;
516
517 info = get_common_info (var);
518 db_p = get_def_blocks_for (info);
519
520 /* Set the bit corresponding to the block where VAR is live in. */
521 bitmap_set_bit (db_p->livein_blocks, bb->index);
522
523 /* Keep track of whether or not we may need to insert PHI nodes.
524
525 If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
526 by the single block containing the definition(s) of this variable. If
527 it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
528 NEED_PHI_STATE_MAYBE. */
529 if (info->need_phi_state == NEED_PHI_STATE_NO)
530 {
531 int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
532
533 if (def_block_index == -1
534 || ! dominated_by_p (CDI_DOMINATORS, bb,
535 BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
536 info->need_phi_state = NEED_PHI_STATE_MAYBE;
537 }
538 else
539 info->need_phi_state = NEED_PHI_STATE_MAYBE;
540}
541
542
543/* Return true if NAME is in OLD_SSA_NAMES. */
544
545static inline bool
546is_old_name (tree name)
547{
548 unsigned ver = SSA_NAME_VERSION (name);
549 if (!old_ssa_names)
550 return false;
551 return (ver < SBITMAP_SIZE (old_ssa_names)
552 && bitmap_bit_p (old_ssa_names, ver));
553}
554
555
556/* Return true if NAME is in NEW_SSA_NAMES. */
557
558static inline bool
559is_new_name (tree name)
560{
561 unsigned ver = SSA_NAME_VERSION (name);
562 if (!new_ssa_names)
563 return false;
564 return (ver < SBITMAP_SIZE (new_ssa_names)
565 && bitmap_bit_p (new_ssa_names, ver));
566}
567
568
569/* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
570
571static inline bitmap
572names_replaced_by (tree new_tree)
573{
574 return get_ssa_name_ann (new_tree)->repl_set;
575}
576
577
578/* Add OLD to REPL_TBL[NEW_TREE].SET. */
579
580static inline void
581add_to_repl_tbl (tree new_tree, tree old)
582{
583 bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
584 if (!*set)
585 *set = BITMAP_ALLOC (&update_ssa_obstack);
586 bitmap_set_bit (*set, SSA_NAME_VERSION (old));
587}
588
589
590/* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
591 represents the set of names O_1 ... O_j replaced by N_i. This is
592 used by update_ssa and its helpers to introduce new SSA names in an
593 already formed SSA web. */
594
595static void
596add_new_name_mapping (tree new_tree, tree old)
597{
598 /* OLD and NEW_TREE must be different SSA names for the same symbol. */
599 gcc_checking_assert (new_tree != old
600 && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
601
602 /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
603 caller may have created new names since the set was created. */
604 if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
605 {
606 unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
607 new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
608 old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
609 }
610
611 /* Update the REPL_TBL table. */
612 add_to_repl_tbl (new_tree, old);
613
614 /* If OLD had already been registered as a new name, then all the
615 names that OLD replaces should also be replaced by NEW_TREE. */
616 if (is_new_name (old))
617 bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
618
619 /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
620 respectively. */
621 bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
622 bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
623}
624
625
626/* Call back for walk_dominator_tree used to collect definition sites
627 for every variable in the function. For every statement S in block
628 BB:
629
630 1- Variables defined by S in the DEFS of S are marked in the bitmap
631 KILLS.
632
633 2- If S uses a variable VAR and there is no preceding kill of VAR,
634 then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
635
636 This information is used to determine which variables are live
637 across block boundaries to reduce the number of PHI nodes
638 we create. */
639
640static void
641mark_def_sites (basic_block bb, gimple *stmt, bitmap kills)
642{
643 tree def;
644 use_operand_p use_p;
645 ssa_op_iter iter;
646
647 /* Since this is the first time that we rewrite the program into SSA
648 form, force an operand scan on every statement. */
649 update_stmt (stmt);
650
651 gcc_checking_assert (blocks_to_update == NULL);
652 set_register_defs (stmt, false);
653 set_rewrite_uses (stmt, false);
654
655 if (is_gimple_debug (stmt))
656 {
657 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
658 {
659 tree sym = USE_FROM_PTR (use_p);
660 gcc_checking_assert (DECL_P (sym));
661 set_rewrite_uses (stmt, true);
662 }
663 if (rewrite_uses_p (stmt))
664 bitmap_set_bit (interesting_blocks, bb->index);
665 return;
666 }
667
668 /* If a variable is used before being set, then the variable is live
669 across a block boundary, so mark it live-on-entry to BB. */
670 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
671 {
672 tree sym = USE_FROM_PTR (use_p);
673 if (TREE_CODE (sym) == SSA_NAME)
674 continue;
675 gcc_checking_assert (DECL_P (sym));
676 if (!bitmap_bit_p (kills, DECL_UID (sym)))
677 set_livein_block (sym, bb);
678 set_rewrite_uses (stmt, true);
679 }
680
681 /* Now process the defs. Mark BB as the definition block and add
682 each def to the set of killed symbols. */
683 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
684 {
685 if (TREE_CODE (def) == SSA_NAME)
686 continue;
687 gcc_checking_assert (DECL_P (def));
688 set_def_block (def, bb, false);
689 bitmap_set_bit (kills, DECL_UID (def));
690 set_register_defs (stmt, true);
691 }
692
693 /* If we found the statement interesting then also mark the block BB
694 as interesting. */
695 if (rewrite_uses_p (stmt) || register_defs_p (stmt))
696 bitmap_set_bit (interesting_blocks, bb->index);
697}
698
699/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
700 in the dfs numbering of the dominance tree. */
701
702struct dom_dfsnum
703{
704 /* Basic block whose index this entry corresponds to. */
705 unsigned bb_index;
706
707 /* The dfs number of this node. */
708 unsigned dfs_num;
709};
710
711/* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
712 for qsort. */
713
714static int
715cmp_dfsnum (const void *a, const void *b)
716{
717 const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
718 const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
719
720 return (int) da->dfs_num - (int) db->dfs_num;
721}
722
723/* Among the intervals starting at the N points specified in DEFS, find
724 the one that contains S, and return its bb_index. */
725
726static unsigned
727find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
728{
729 unsigned f = 0, t = n, m;
730
731 while (t > f + 1)
732 {
733 m = (f + t) / 2;
734 if (defs[m].dfs_num <= s)
735 f = m;
736 else
737 t = m;
738 }
739
740 return defs[f].bb_index;
741}
742
743/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
744 KILLS is a bitmap of blocks where the value is defined before any use. */
745
746static void
747prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
748{
749 bitmap_iterator bi;
750 unsigned i, b, p, u, top;
751 bitmap live_phis;
752 basic_block def_bb, use_bb;
753 edge e;
754 edge_iterator ei;
755 bitmap to_remove;
756 struct dom_dfsnum *defs;
757 unsigned n_defs, adef;
758
759 if (bitmap_empty_p (uses))
760 {
761 bitmap_clear (phis);
762 return;
763 }
764
765 /* The phi must dominate a use, or an argument of a live phi. Also, we
766 do not create any phi nodes in def blocks, unless they are also livein. */
767 to_remove = BITMAP_ALLOC (NULL);
768 bitmap_and_compl (to_remove, kills, uses);
769 bitmap_and_compl_into (phis, to_remove);
770 if (bitmap_empty_p (phis))
771 {
772 BITMAP_FREE (to_remove);
773 return;
774 }
775
776 /* We want to remove the unnecessary phi nodes, but we do not want to compute
777 liveness information, as that may be linear in the size of CFG, and if
778 there are lot of different variables to rewrite, this may lead to quadratic
779 behavior.
780
781 Instead, we basically emulate standard dce. We put all uses to worklist,
782 then for each of them find the nearest def that dominates them. If this
783 def is a phi node, we mark it live, and if it was not live before, we
784 add the predecessors of its basic block to the worklist.
785
786 To quickly locate the nearest def that dominates use, we use dfs numbering
787 of the dominance tree (that is already available in order to speed up
788 queries). For each def, we have the interval given by the dfs number on
789 entry to and on exit from the corresponding subtree in the dominance tree.
790 The nearest dominator for a given use is the smallest of these intervals
791 that contains entry and exit dfs numbers for the basic block with the use.
792 If we store the bounds for all the uses to an array and sort it, we can
793 locate the nearest dominating def in logarithmic time by binary search.*/
794 bitmap_ior (to_remove, kills, phis);
795 n_defs = bitmap_count_bits (to_remove);
796 defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
797 defs[0].bb_index = 1;
798 defs[0].dfs_num = 0;
799 adef = 1;
800 EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
801 {
802 def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
803 defs[adef].bb_index = i;
804 defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
805 defs[adef + 1].bb_index = i;
806 defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
807 adef += 2;
808 }
809 BITMAP_FREE (to_remove);
810 gcc_assert (adef == 2 * n_defs + 1);
811 qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
812 gcc_assert (defs[0].bb_index == 1);
813
814 /* Now each DEFS entry contains the number of the basic block to that the
815 dfs number corresponds. Change them to the number of basic block that
816 corresponds to the interval following the dfs number. Also, for the
817 dfs_out numbers, increase the dfs number by one (so that it corresponds
818 to the start of the following interval, not to the end of the current
819 one). We use WORKLIST as a stack. */
820 auto_vec<int> worklist (n_defs + 1);
821 worklist.quick_push (1);
822 top = 1;
823 n_defs = 1;
824 for (i = 1; i < adef; i++)
825 {
826 b = defs[i].bb_index;
827 if (b == top)
828 {
829 /* This is a closing element. Interval corresponding to the top
830 of the stack after removing it follows. */
831 worklist.pop ();
832 top = worklist[worklist.length () - 1];
833 defs[n_defs].bb_index = top;
834 defs[n_defs].dfs_num = defs[i].dfs_num + 1;
835 }
836 else
837 {
838 /* Opening element. Nothing to do, just push it to the stack and move
839 it to the correct position. */
840 defs[n_defs].bb_index = defs[i].bb_index;
841 defs[n_defs].dfs_num = defs[i].dfs_num;
842 worklist.quick_push (b);
843 top = b;
844 }
845
846 /* If this interval starts at the same point as the previous one, cancel
847 the previous one. */
848 if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
849 defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
850 else
851 n_defs++;
852 }
853 worklist.pop ();
854 gcc_assert (worklist.is_empty ());
855
856 /* Now process the uses. */
857 live_phis = BITMAP_ALLOC (NULL);
858 EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
859 {
860 worklist.safe_push (i);
861 }
862
863 while (!worklist.is_empty ())
864 {
865 b = worklist.pop ();
866 if (b == ENTRY_BLOCK)
867 continue;
868
869 /* If there is a phi node in USE_BB, it is made live. Otherwise,
870 find the def that dominates the immediate dominator of USE_BB
871 (the kill in USE_BB does not dominate the use). */
872 if (bitmap_bit_p (phis, b))
873 p = b;
874 else
875 {
876 use_bb = get_immediate_dominator (CDI_DOMINATORS,
877 BASIC_BLOCK_FOR_FN (cfun, b));
878 p = find_dfsnum_interval (defs, n_defs,
879 bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
880 if (!bitmap_bit_p (phis, p))
881 continue;
882 }
883
884 /* If the phi node is already live, there is nothing to do. */
885 if (!bitmap_set_bit (live_phis, p))
886 continue;
887
888 /* Add the new uses to the worklist. */
889 def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
890 FOR_EACH_EDGE (e, ei, def_bb->preds)
891 {
892 u = e->src->index;
893 if (bitmap_bit_p (uses, u))
894 continue;
895
896 /* In case there is a kill directly in the use block, do not record
897 the use (this is also necessary for correctness, as we assume that
898 uses dominated by a def directly in their block have been filtered
899 out before). */
900 if (bitmap_bit_p (kills, u))
901 continue;
902
903 bitmap_set_bit (uses, u);
904 worklist.safe_push (u);
905 }
906 }
907
908 bitmap_copy (phis, live_phis);
909 BITMAP_FREE (live_phis);
910 free (defs);
911}
912
913/* Return the set of blocks where variable VAR is defined and the blocks
914 where VAR is live on entry (livein). Return NULL, if no entry is
915 found in DEF_BLOCKS. */
916
917static inline def_blocks *
918find_def_blocks_for (tree var)
919{
920 def_blocks *p = &get_common_info (var)->def_blocks;
921 if (!p->def_blocks)
922 return NULL;
923 return p;
924}
925
926
927/* Marks phi node PHI in basic block BB for rewrite. */
928
929static void
930mark_phi_for_rewrite (basic_block bb, gphi *phi)
931{
932 vec<gphi *> phis;
933 unsigned n, idx = bb->index;
934
935 if (rewrite_uses_p (phi))
936 return;
937
938 set_rewrite_uses (phi, true);
939
940 if (!blocks_with_phis_to_rewrite)
941 return;
942
943 bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
944
945 n = (unsigned) last_basic_block_for_fn (cfun) + 1;
946 if (phis_to_rewrite.length () < n)
947 phis_to_rewrite.safe_grow_cleared (n);
948
949 phis = phis_to_rewrite[idx];
950 phis.reserve (10);
951
952 phis.safe_push (phi);
953 phis_to_rewrite[idx] = phis;
954}
955
956/* Insert PHI nodes for variable VAR using the iterated dominance
957 frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
958 function assumes that the caller is incrementally updating the
959 existing SSA form, in which case VAR may be an SSA name instead of
960 a symbol.
961
962 PHI_INSERTION_POINTS is updated to reflect nodes that already had a
963 PHI node for VAR. On exit, only the nodes that received a PHI node
964 for VAR will be present in PHI_INSERTION_POINTS. */
965
966static void
967insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
968{
969 unsigned bb_index;
970 edge e;
971 gphi *phi;
972 basic_block bb;
973 bitmap_iterator bi;
974 def_blocks *def_map = find_def_blocks_for (var);
975
976 /* Remove the blocks where we already have PHI nodes for VAR. */
977 bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
978
979 /* Remove obviously useless phi nodes. */
980 prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
981 def_map->livein_blocks);
982
983 /* And insert the PHI nodes. */
984 EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
985 {
986 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
987 if (update_p)
988 mark_block_for_update (bb);
989
990 if (dump_file && (dump_flags & TDF_DETAILS))
991 {
992 fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
993 print_generic_expr (dump_file, var, TDF_SLIM);
994 fprintf (dump_file, "\n");
995 }
996 phi = NULL;
997
998 if (TREE_CODE (var) == SSA_NAME)
999 {
1000 /* If we are rewriting SSA names, create the LHS of the PHI
1001 node by duplicating VAR. This is useful in the case of
1002 pointers, to also duplicate pointer attributes (alias
1003 information, in particular). */
1004 edge_iterator ei;
1005 tree new_lhs;
1006
1007 gcc_checking_assert (update_p);
1008 new_lhs = duplicate_ssa_name (var, NULL);
1009 phi = create_phi_node (new_lhs, bb);
1010 add_new_name_mapping (new_lhs, var);
1011
1012 /* Add VAR to every argument slot of PHI. We need VAR in
1013 every argument so that rewrite_update_phi_arguments knows
1014 which name is this PHI node replacing. If VAR is a
1015 symbol marked for renaming, this is not necessary, the
1016 renamer will use the symbol on the LHS to get its
1017 reaching definition. */
1018 FOR_EACH_EDGE (e, ei, bb->preds)
1019 add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1020 }
1021 else
1022 {
1023 tree tracked_var;
1024
1025 gcc_checking_assert (DECL_P (var));
1026 phi = create_phi_node (var, bb);
1027
1028 tracked_var = target_for_debug_bind (var);
1029 if (tracked_var)
1030 {
1031 gimple *note = gimple_build_debug_bind (tracked_var,
1032 PHI_RESULT (phi),
1033 phi);
1034 gimple_stmt_iterator si = gsi_after_labels (bb);
1035 gsi_insert_before (&si, note, GSI_SAME_STMT);
1036 }
1037 }
1038
1039 /* Mark this PHI node as interesting for update_ssa. */
1040 set_register_defs (phi, true);
1041 mark_phi_for_rewrite (bb, phi);
1042 }
1043}
1044
1045/* Sort var_infos after DECL_UID of their var. */
1046
1047static int
1048insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1049{
1050 const var_info *defa = *(var_info * const *)a;
1051 const var_info *defb = *(var_info * const *)b;
1052 if (DECL_UID (defa->var) < DECL_UID (defb->var))
1053 return -1;
1054 else
1055 return 1;
1056}
1057
1058/* Insert PHI nodes at the dominance frontier of blocks with variable
1059 definitions. DFS contains the dominance frontier information for
1060 the flowgraph. */
1061
1062static void
1063insert_phi_nodes (bitmap_head *dfs)
1064{
1065 hash_table<var_info_hasher>::iterator hi;
1066 unsigned i;
1067 var_info *info;
1068
1069 timevar_push (TV_TREE_INSERT_PHI_NODES);
1070
1071 /* When the gimplifier introduces SSA names it cannot easily avoid
1072 situations where abnormal edges added by CFG construction break
1073 the use-def dominance requirement. For this case rewrite SSA
1074 names with broken use-def dominance out-of-SSA and register them
1075 for PHI insertion. We only need to do this if abnormal edges
1076 can appear in the function. */
1077 tree name;
1078 if (cfun->calls_setjmp
1079 || cfun->has_nonlocal_label)
1080 FOR_EACH_SSA_NAME (i, name, cfun)
1081 {
1082 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1083 if (SSA_NAME_IS_DEFAULT_DEF (name))
1084 continue;
1085
1086 basic_block def_bb = gimple_bb (def_stmt);
1087 imm_use_iterator it;
1088 gimple *use_stmt;
1089 bool need_phis = false;
1090 FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1091 {
1092 basic_block use_bb = gimple_bb (use_stmt);
1093 if (use_bb != def_bb
1094 && ! dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
1095 need_phis = true;
1096 }
1097 if (need_phis)
1098 {
1099 tree var = create_tmp_reg (TREE_TYPE (name));
1100 use_operand_p use_p;
1101 FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1102 {
1103 basic_block use_bb = gimple_bb (use_stmt);
1104 FOR_EACH_IMM_USE_ON_STMT (use_p, it)
1105 SET_USE (use_p, var);
1106 update_stmt (use_stmt);
1107 set_livein_block (var, use_bb);
1108 set_rewrite_uses (use_stmt, true);
1109 bitmap_set_bit (interesting_blocks, use_bb->index);
1110 }
1111 def_operand_p def_p;
1112 ssa_op_iter dit;
1113 FOR_EACH_SSA_DEF_OPERAND (def_p, def_stmt, dit, SSA_OP_DEF)
1114 if (DEF_FROM_PTR (def_p) == name)
1115 SET_DEF (def_p, var);
1116 update_stmt (def_stmt);
1117 set_def_block (var, def_bb, false);
1118 set_register_defs (def_stmt, true);
1119 bitmap_set_bit (interesting_blocks, def_bb->index);
1120 release_ssa_name (name);
1121 }
1122 }
1123
1124 auto_vec<var_info *> vars (var_infos->elements ());
1125 FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
1126 if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1127 vars.quick_push (info);
1128
1129 /* Do two stages to avoid code generation differences for UID
1130 differences but no UID ordering differences. */
1131 vars.qsort (insert_phi_nodes_compare_var_infos);
1132
1133 FOR_EACH_VEC_ELT (vars, i, info)
1134 {
1135 bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1136 insert_phi_nodes_for (info->var, idf, false);
1137 BITMAP_FREE (idf);
1138 }
1139
1140 timevar_pop (TV_TREE_INSERT_PHI_NODES);
1141}
1142
1143
1144/* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1145 register DEF (an SSA_NAME) to be a new definition for SYM. */
1146
1147static void
1148register_new_def (tree def, tree sym)
1149{
1150 common_info *info = get_common_info (sym);
1151 tree currdef;
1152
1153 /* If this variable is set in a single basic block and all uses are
1154 dominated by the set(s) in that single basic block, then there is
1155 no reason to record anything for this variable in the block local
1156 definition stacks. Doing so just wastes time and memory.
1157
1158 This is the same test to prune the set of variables which may
1159 need PHI nodes. So we just use that information since it's already
1160 computed and available for us to use. */
1161 if (info->need_phi_state == NEED_PHI_STATE_NO)
1162 {
1163 info->current_def = def;
1164 return;
1165 }
1166
1167 currdef = info->current_def;
1168
1169 /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1170 SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1171 in the stack so that we know which symbol is being defined by
1172 this SSA name when we unwind the stack. */
1173 if (currdef && !is_gimple_reg (sym))
1174 block_defs_stack.safe_push (sym);
1175
1176 /* Push the current reaching definition into BLOCK_DEFS_STACK. This
1177 stack is later used by the dominator tree callbacks to restore
1178 the reaching definitions for all the variables defined in the
1179 block after a recursive visit to all its immediately dominated
1180 blocks. If there is no current reaching definition, then just
1181 record the underlying _DECL node. */
1182 block_defs_stack.safe_push (currdef ? currdef : sym);
1183
1184 /* Set the current reaching definition for SYM to be DEF. */
1185 info->current_def = def;
1186}
1187
1188
1189/* Perform a depth-first traversal of the dominator tree looking for
1190 variables to rename. BB is the block where to start searching.
1191 Renaming is a five step process:
1192
1193 1- Every definition made by PHI nodes at the start of the blocks is
1194 registered as the current definition for the corresponding variable.
1195
1196 2- Every statement in BB is rewritten. USE and VUSE operands are
1197 rewritten with their corresponding reaching definition. DEF and
1198 VDEF targets are registered as new definitions.
1199
1200 3- All the PHI nodes in successor blocks of BB are visited. The
1201 argument corresponding to BB is replaced with its current reaching
1202 definition.
1203
1204 4- Recursively rewrite every dominator child block of BB.
1205
1206 5- Restore (in reverse order) the current reaching definition for every
1207 new definition introduced in this block. This is done so that when
1208 we return from the recursive call, all the current reaching
1209 definitions are restored to the names that were valid in the
1210 dominator parent of BB. */
1211
1212/* Return the current definition for variable VAR. If none is found,
1213 create a new SSA name to act as the zeroth definition for VAR. */
1214
1215static tree
1216get_reaching_def (tree var)
1217{
1218 common_info *info = get_common_info (var);
1219 tree currdef;
1220
1221 /* Lookup the current reaching definition for VAR. */
1222 currdef = info->current_def;
1223
1224 /* If there is no reaching definition for VAR, create and register a
1225 default definition for it (if needed). */
1226 if (currdef == NULL_TREE)
1227 {
1228 tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1229 if (! sym)
1230 sym = create_tmp_reg (TREE_TYPE (var));
1231 currdef = get_or_create_ssa_default_def (cfun, sym);
1232 }
1233
1234 /* Return the current reaching definition for VAR, or the default
1235 definition, if we had to create one. */
1236 return currdef;
1237}
1238
1239
1240/* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1241
1242static void
1243rewrite_debug_stmt_uses (gimple *stmt)
1244{
1245 use_operand_p use_p;
1246 ssa_op_iter iter;
1247 bool update = false;
1248
1249 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1250 {
1251 tree var = USE_FROM_PTR (use_p), def;
1252 common_info *info = get_common_info (var);
1253 gcc_checking_assert (DECL_P (var));
1254 def = info->current_def;
1255 if (!def)
1256 {
1257 if (TREE_CODE (var) == PARM_DECL
1258 && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
1259 {
1260 gimple_stmt_iterator gsi
1261 =
1262 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1263 int lim;
1264 /* Search a few source bind stmts at the start of first bb to
1265 see if a DEBUG_EXPR_DECL can't be reused. */
1266 for (lim = 32;
1267 !gsi_end_p (gsi) && lim > 0;
1268 gsi_next (&gsi), lim--)
1269 {
1270 gimple *gstmt = gsi_stmt (gsi);
1271 if (!gimple_debug_source_bind_p (gstmt))
1272 break;
1273 if (gimple_debug_source_bind_get_value (gstmt) == var)
1274 {
1275 def = gimple_debug_source_bind_get_var (gstmt);
1276 if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1277 break;
1278 else
1279 def = NULL_TREE;
1280 }
1281 }
1282 /* If not, add a new source bind stmt. */
1283 if (def == NULL_TREE)
1284 {
1285 gimple *def_temp;
1286 def = make_node (DEBUG_EXPR_DECL);
1287 def_temp = gimple_build_debug_source_bind (def, var, NULL);
1288 DECL_ARTIFICIAL (def) = 1;
1289 TREE_TYPE (def) = TREE_TYPE (var);
1290 SET_DECL_MODE (def, DECL_MODE (var));
1291 gsi =
1292 gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1293 gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1294 }
1295 update = true;
1296 }
1297 }
1298 else
1299 {
1300 /* Check if info->current_def can be trusted. */
1301 basic_block bb = gimple_bb (stmt);
1302 basic_block def_bb
1303 = SSA_NAME_IS_DEFAULT_DEF (def)
1304 ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1305
1306 /* If definition is in current bb, it is fine. */
1307 if (bb == def_bb)
1308 ;
1309 /* If definition bb doesn't dominate the current bb,
1310 it can't be used. */
1311 else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1312 def = NULL;
1313 /* If there is just one definition and dominates the current
1314 bb, it is fine. */
1315 else if (info->need_phi_state == NEED_PHI_STATE_NO)
1316 ;
1317 else
1318 {
1319 def_blocks *db_p = get_def_blocks_for (info);
1320
1321 /* If there are some non-debug uses in the current bb,
1322 it is fine. */
1323 if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1324 ;
1325 /* Otherwise give up for now. */
1326 else
1327 def = NULL;
1328 }
1329 }
1330 if (def == NULL)
1331 {
1332 gimple_debug_bind_reset_value (stmt);
1333 update_stmt (stmt);
1334 return;
1335 }
1336 SET_USE (use_p, def);
1337 }
1338 if (update)
1339 update_stmt (stmt);
1340}
1341
1342/* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1343 the block with its immediate reaching definitions. Update the current
1344 definition of a variable when a new real or virtual definition is found. */
1345
1346static void
1347rewrite_stmt (gimple_stmt_iterator *si)
1348{
1349 use_operand_p use_p;
1350 def_operand_p def_p;
1351 ssa_op_iter iter;
1352 gimple *stmt = gsi_stmt (*si);
1353
1354 /* If mark_def_sites decided that we don't need to rewrite this
1355 statement, ignore it. */
1356 gcc_assert (blocks_to_update == NULL);
1357 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1358 return;
1359
1360 if (dump_file && (dump_flags & TDF_DETAILS))
1361 {
1362 fprintf (dump_file, "Renaming statement ");
1363 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1364 fprintf (dump_file, "\n");
1365 }
1366
1367 /* Step 1. Rewrite USES in the statement. */
1368 if (rewrite_uses_p (stmt))
1369 {
1370 if (is_gimple_debug (stmt))
1371 rewrite_debug_stmt_uses (stmt);
1372 else
1373 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1374 {
1375 tree var = USE_FROM_PTR (use_p);
1376 if (TREE_CODE (var) == SSA_NAME)
1377 continue;
1378 gcc_checking_assert (DECL_P (var));
1379 SET_USE (use_p, get_reaching_def (var));
1380 }
1381 }
1382
1383 /* Step 2. Register the statement's DEF operands. */
1384 if (register_defs_p (stmt))
1385 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1386 {
1387 tree var = DEF_FROM_PTR (def_p);
1388 tree name;
1389 tree tracked_var;
1390
1391 if (TREE_CODE (var) == SSA_NAME)
1392 continue;
1393 gcc_checking_assert (DECL_P (var));
1394
1395 if (gimple_clobber_p (stmt)
1396 && is_gimple_reg (var))
1397 {
1398 /* If we rewrite a DECL into SSA form then drop its
1399 clobber stmts and replace uses with a new default def. */
1400 gcc_checking_assert (VAR_P (var) && !gimple_vdef (stmt));
1401 gsi_replace (si, gimple_build_nop (), true);
1402 register_new_def (get_or_create_ssa_default_def (cfun, var), var);
1403 break;
1404 }
1405
1406 name = make_ssa_name (var, stmt);
1407 SET_DEF (def_p, name);
1408 register_new_def (DEF_FROM_PTR (def_p), var);
1409
1410 tracked_var = target_for_debug_bind (var);
1411 if (tracked_var)
1412 {
1413 gimple *note = gimple_build_debug_bind (tracked_var, name, stmt);
1414 gsi_insert_after (si, note, GSI_SAME_STMT);
1415 }
1416 }
1417}
1418
1419
1420/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1421 PHI nodes. For every PHI node found, add a new argument containing the
1422 current reaching definition for the variable and the edge through which
1423 that definition is reaching the PHI node. */
1424
1425static void
1426rewrite_add_phi_arguments (basic_block bb)
1427{
1428 edge e;
1429 edge_iterator ei;
1430
1431 FOR_EACH_EDGE (e, ei, bb->succs)
1432 {
1433 gphi *phi;
1434 gphi_iterator gsi;
1435
1436 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
1437 gsi_next (&gsi))
1438 {
1439 tree currdef, res, argvar;
1440 location_t loc;
1441
1442 phi = gsi.phi ();
1443 res = gimple_phi_result (phi);
1444 /* If we have pre-existing PHI (via the GIMPLE FE) its args may
1445 be different vars than existing vars and they may be constants
1446 as well. Note the following supports partial SSA for PHI args. */
1447 argvar = gimple_phi_arg_def (phi, e->dest_idx);
1448 if (argvar && ! DECL_P (argvar))
1449 continue;
1450 if (!argvar)
1451 argvar = SSA_NAME_VAR (res);
1452 currdef = get_reaching_def (argvar);
1453 /* Virtual operand PHI args do not need a location. */
1454 if (virtual_operand_p (res))
1455 loc = UNKNOWN_LOCATION;
1456 else
1457 loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1458 add_phi_arg (phi, currdef, e, loc);
1459 }
1460 }
1461}
1462
1463class rewrite_dom_walker : public dom_walker
1464{
1465public:
1466 rewrite_dom_walker (cdi_direction direction) : dom_walker (direction) {}
1467
1468 virtual edge before_dom_children (basic_block);
1469 virtual void after_dom_children (basic_block);
1470};
1471
1472/* SSA Rewriting Step 1. Initialization, create a block local stack
1473 of reaching definitions for new SSA names produced in this block
1474 (BLOCK_DEFS). Register new definitions for every PHI node in the
1475 block. */
1476
1477edge
1478rewrite_dom_walker::before_dom_children (basic_block bb)
1479{
1480 if (dump_file && (dump_flags & TDF_DETAILS))
1481 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1482
1483 /* Mark the unwind point for this block. */
1484 block_defs_stack.safe_push (NULL_TREE);
1485
1486 /* Step 1. Register new definitions for every PHI node in the block.
1487 Conceptually, all the PHI nodes are executed in parallel and each PHI
1488 node introduces a new version for the associated variable. */
1489 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1490 gsi_next (&gsi))
1491 {
1492 tree result = gimple_phi_result (gsi_stmt (gsi));
1493 register_new_def (result, SSA_NAME_VAR (result));
1494 }
1495
1496 /* Step 2. Rewrite every variable used in each statement in the block
1497 with its immediate reaching definitions. Update the current definition
1498 of a variable when a new real or virtual definition is found. */
1499 if (bitmap_bit_p (interesting_blocks, bb->index))
1500 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1501 gsi_next (&gsi))
1502 rewrite_stmt (&gsi);
1503
1504 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1505 For every PHI node found, add a new argument containing the current
1506 reaching definition for the variable and the edge through which that
1507 definition is reaching the PHI node. */
1508 rewrite_add_phi_arguments (bb);
1509
1510 return NULL;
1511}
1512
1513
1514
1515/* Called after visiting all the statements in basic block BB and all
1516 of its dominator children. Restore CURRDEFS to its original value. */
1517
1518void
1519rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1520{
1521 /* Restore CURRDEFS to its original state. */
1522 while (block_defs_stack.length () > 0)
1523 {
1524 tree tmp = block_defs_stack.pop ();
1525 tree saved_def, var;
1526
1527 if (tmp == NULL_TREE)
1528 break;
1529
1530 if (TREE_CODE (tmp) == SSA_NAME)
1531 {
1532 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1533 current definition of its underlying variable. Note that
1534 if the SSA_NAME is not for a GIMPLE register, the symbol
1535 being defined is stored in the next slot in the stack.
1536 This mechanism is needed because an SSA name for a
1537 non-register symbol may be the definition for more than
1538 one symbol (e.g., SFTs, aliased variables, etc). */
1539 saved_def = tmp;
1540 var = SSA_NAME_VAR (saved_def);
1541 if (!is_gimple_reg (var))
1542 var = block_defs_stack.pop ();
1543 }
1544 else
1545 {
1546 /* If we recorded anything else, it must have been a _DECL
1547 node and its current reaching definition must have been
1548 NULL. */
1549 saved_def = NULL;
1550 var = tmp;
1551 }
1552
1553 get_common_info (var)->current_def = saved_def;
1554 }
1555}
1556
1557
1558/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1559
1560DEBUG_FUNCTION void
1561debug_decl_set (bitmap set)
1562{
1563 dump_decl_set (stderr, set);
1564 fprintf (stderr, "\n");
1565}
1566
1567
1568/* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1569 stack up to a maximum of N levels. If N is -1, the whole stack is
1570 dumped. New levels are created when the dominator tree traversal
1571 used for renaming enters a new sub-tree. */
1572
1573void
1574dump_defs_stack (FILE *file, int n)
1575{
1576 int i, j;
1577
1578 fprintf (file, "\n\nRenaming stack");
1579 if (n > 0)
1580 fprintf (file, " (up to %d levels)", n);
1581 fprintf (file, "\n\n");
1582
1583 i = 1;
1584 fprintf (file, "Level %d (current level)\n", i);
1585 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1586 {
1587 tree name, var;
1588
1589 name = block_defs_stack[j];
1590 if (name == NULL_TREE)
1591 {
1592 i++;
1593 if (n > 0 && i > n)
1594 break;
1595 fprintf (file, "\nLevel %d\n", i);
1596 continue;
1597 }
1598
1599 if (DECL_P (name))
1600 {
1601 var = name;
1602 name = NULL_TREE;
1603 }
1604 else
1605 {
1606 var = SSA_NAME_VAR (name);
1607 if (!is_gimple_reg (var))
1608 {
1609 j--;
1610 var = block_defs_stack[j];
1611 }
1612 }
1613
1614 fprintf (file, " Previous CURRDEF (");
1615 print_generic_expr (file, var);
1616 fprintf (file, ") = ");
1617 if (name)
1618 print_generic_expr (file, name);
1619 else
1620 fprintf (file, "<NIL>");
1621 fprintf (file, "\n");
1622 }
1623}
1624
1625
1626/* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1627 stack up to a maximum of N levels. If N is -1, the whole stack is
1628 dumped. New levels are created when the dominator tree traversal
1629 used for renaming enters a new sub-tree. */
1630
1631DEBUG_FUNCTION void
1632debug_defs_stack (int n)
1633{
1634 dump_defs_stack (stderr, n);
1635}
1636
1637
1638/* Dump the current reaching definition of every symbol to FILE. */
1639
1640void
1641dump_currdefs (FILE *file)
1642{
1643 unsigned i;
1644 tree var;
1645
1646 if (symbols_to_rename.is_empty ())
1647 return;
1648
1649 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1650 FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1651 {
1652 common_info *info = get_common_info (var);
1653 fprintf (file, "CURRDEF (");
1654 print_generic_expr (file, var);
1655 fprintf (file, ") = ");
1656 if (info->current_def)
1657 print_generic_expr (file, info->current_def);
1658 else
1659 fprintf (file, "<NIL>");
1660 fprintf (file, "\n");
1661 }
1662}
1663
1664
1665/* Dump the current reaching definition of every symbol to stderr. */
1666
1667DEBUG_FUNCTION void
1668debug_currdefs (void)
1669{
1670 dump_currdefs (stderr);
1671}
1672
1673
1674/* Dump SSA information to FILE. */
1675
1676void
1677dump_tree_ssa (FILE *file)
1678{
1679 const char *funcname
1680 = lang_hooks.decl_printable_name (current_function_decl, 2);
1681
1682 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1683
1684 dump_var_infos (file);
1685 dump_defs_stack (file, -1);
1686 dump_currdefs (file);
1687 dump_tree_ssa_stats (file);
1688}
1689
1690
1691/* Dump SSA information to stderr. */
1692
1693DEBUG_FUNCTION void
1694debug_tree_ssa (void)
1695{
1696 dump_tree_ssa (stderr);
1697}
1698
1699
1700/* Dump statistics for the hash table HTAB. */
1701
1702static void
1703htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
1704{
1705 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1706 (long) htab.size (),
1707 (long) htab.elements (),
1708 htab.collisions ());
1709}
1710
1711
1712/* Dump SSA statistics on FILE. */
1713
1714void
1715dump_tree_ssa_stats (FILE *file)
1716{
1717 if (var_infos)
1718 {
1719 fprintf (file, "\nHash table statistics:\n");
1720 fprintf (file, " var_infos: ");
1721 htab_statistics (file, *var_infos);
1722 fprintf (file, "\n");
1723 }
1724}
1725
1726
1727/* Dump SSA statistics on stderr. */
1728
1729DEBUG_FUNCTION void
1730debug_tree_ssa_stats (void)
1731{
1732 dump_tree_ssa_stats (stderr);
1733}
1734
1735
1736/* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1737
1738int
1739debug_var_infos_r (var_info **slot, FILE *file)
1740{
1741 var_info *info = *slot;
1742
1743 fprintf (file, "VAR: ");
1744 print_generic_expr (file, info->var, dump_flags);
1745 bitmap_print (file, info->info.def_blocks.def_blocks,
1746 ", DEF_BLOCKS: { ", "}");
1747 bitmap_print (file, info->info.def_blocks.livein_blocks,
1748 ", LIVEIN_BLOCKS: { ", "}");
1749 bitmap_print (file, info->info.def_blocks.phi_blocks,
1750 ", PHI_BLOCKS: { ", "}\n");
1751
1752 return 1;
1753}
1754
1755
1756/* Dump the VAR_INFOS hash table on FILE. */
1757
1758void
1759dump_var_infos (FILE *file)
1760{
1761 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1762 if (var_infos)
1763 var_infos->traverse <FILE *, debug_var_infos_r> (file);
1764}
1765
1766
1767/* Dump the VAR_INFOS hash table on stderr. */
1768
1769DEBUG_FUNCTION void
1770debug_var_infos (void)
1771{
1772 dump_var_infos (stderr);
1773}
1774
1775
1776/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1777
1778static inline void
1779register_new_update_single (tree new_name, tree old_name)
1780{
1781 common_info *info = get_common_info (old_name);
1782 tree currdef = info->current_def;
1783
1784 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1785 This stack is later used by the dominator tree callbacks to
1786 restore the reaching definitions for all the variables
1787 defined in the block after a recursive visit to all its
1788 immediately dominated blocks. */
1789 block_defs_stack.reserve (2);
1790 block_defs_stack.quick_push (currdef);
1791 block_defs_stack.quick_push (old_name);
1792
1793 /* Set the current reaching definition for OLD_NAME to be
1794 NEW_NAME. */
1795 info->current_def = new_name;
1796}
1797
1798
1799/* Register NEW_NAME to be the new reaching definition for all the
1800 names in OLD_NAMES. Used by the incremental SSA update routines to
1801 replace old SSA names with new ones. */
1802
1803static inline void
1804register_new_update_set (tree new_name, bitmap old_names)
1805{
1806 bitmap_iterator bi;
1807 unsigned i;
1808
1809 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1810 register_new_update_single (new_name, ssa_name (i));
1811}
1812
1813
1814
1815/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1816 it is a symbol marked for renaming, replace it with USE_P's current
1817 reaching definition. */
1818
1819static inline void
1820maybe_replace_use (use_operand_p use_p)
1821{
1822 tree rdef = NULL_TREE;
1823 tree use = USE_FROM_PTR (use_p);
1824 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1825
1826 if (marked_for_renaming (sym))
1827 rdef = get_reaching_def (sym);
1828 else if (is_old_name (use))
1829 rdef = get_reaching_def (use);
1830
1831 if (rdef && rdef != use)
1832 SET_USE (use_p, rdef);
1833}
1834
1835
1836/* Same as maybe_replace_use, but without introducing default stmts,
1837 returning false to indicate a need to do so. */
1838
1839static inline bool
1840maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1841{
1842 tree rdef = NULL_TREE;
1843 tree use = USE_FROM_PTR (use_p);
1844 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1845
1846 if (marked_for_renaming (sym))
1847 rdef = get_var_info (sym)->info.current_def;
1848 else if (is_old_name (use))
1849 {
1850 rdef = get_ssa_name_ann (use)->info.current_def;
1851 /* We can't assume that, if there's no current definition, the
1852 default one should be used. It could be the case that we've
1853 rearranged blocks so that the earlier definition no longer
1854 dominates the use. */
1855 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1856 rdef = use;
1857 }
1858 else
1859 rdef = use;
1860
1861 if (rdef && rdef != use)
1862 SET_USE (use_p, rdef);
1863
1864 return rdef != NULL_TREE;
1865}
1866
1867
1868/* If DEF has x_5 = ASAN_POISON () as its current def, add
1869 ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1870 a poisoned (out of scope) variable. */
1871
1872static void
1873maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
1874{
1875 tree cdef = get_current_def (def);
1876 if (cdef != NULL
1877 && TREE_CODE (cdef) == SSA_NAME
1878 && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), IFN_ASAN_POISON))
1879 {
1880 gcall *call
1881 = gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
1882 gimple_set_location (call, gimple_location (gsi_stmt (*gsi)));
1883 gsi_insert_before (gsi, call, GSI_SAME_STMT);
1884 }
1885}
1886
1887
1888/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1889 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1890 register it as the current definition for the names replaced by
1891 DEF_P. Returns whether the statement should be removed. */
1892
1893static inline bool
1894maybe_register_def (def_operand_p def_p, gimple *stmt,
1895 gimple_stmt_iterator gsi)
1896{
1897 tree def = DEF_FROM_PTR (def_p);
1898 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1899 bool to_delete = false;
1900
1901 /* If DEF is a naked symbol that needs renaming, create a new
1902 name for it. */
1903 if (marked_for_renaming (sym))
1904 {
1905 if (DECL_P (def))
1906 {
1907 if (gimple_clobber_p (stmt) && is_gimple_reg (sym))
1908 {
1909 gcc_checking_assert (VAR_P (sym));
1910 /* Replace clobber stmts with a default def. This new use of a
1911 default definition may make it look like SSA_NAMEs have
1912 conflicting lifetimes, so we need special code to let them
1913 coalesce properly. */
1914 to_delete = true;
1915 def = get_or_create_ssa_default_def (cfun, sym);
1916 }
1917 else
1918 {
1919 if (asan_sanitize_use_after_scope ())
1920 maybe_add_asan_poison_write (def, &gsi);
1921 def = make_ssa_name (def, stmt);
1922 }
1923 SET_DEF (def_p, def);
1924
1925 tree tracked_var = target_for_debug_bind (sym);
1926 if (tracked_var)
1927 {
1928 gimple *note = gimple_build_debug_bind (tracked_var, def, stmt);
1929 /* If stmt ends the bb, insert the debug stmt on the single
1930 non-EH edge from the stmt. */
1931 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1932 {
1933 basic_block bb = gsi_bb (gsi);
1934 edge_iterator ei;
1935 edge e, ef = NULL;
1936 FOR_EACH_EDGE (e, ei, bb->succs)
1937 if (!(e->flags & EDGE_EH))
1938 {
1939 gcc_checking_assert (!ef);
1940 ef = e;
1941 }
1942 /* If there are other predecessors to ef->dest, then
1943 there must be PHI nodes for the modified
1944 variable, and therefore there will be debug bind
1945 stmts after the PHI nodes. The debug bind notes
1946 we'd insert would force the creation of a new
1947 block (diverging codegen) and be redundant with
1948 the post-PHI bind stmts, so don't add them.
1949
1950 As for the exit edge, there wouldn't be redundant
1951 bind stmts, but there wouldn't be a PC to bind
1952 them to either, so avoid diverging the CFG. */
1953 if (ef && single_pred_p (ef->dest)
1954 && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1955 {
1956 /* If there were PHI nodes in the node, we'd
1957 have to make sure the value we're binding
1958 doesn't need rewriting. But there shouldn't
1959 be PHI nodes in a single-predecessor block,
1960 so we just add the note. */
1961 gsi_insert_on_edge_immediate (ef, note);
1962 }
1963 }
1964 else
1965 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1966 }
1967 }
1968
1969 register_new_update_single (def, sym);
1970 }
1971 else
1972 {
1973 /* If DEF is a new name, register it as a new definition
1974 for all the names replaced by DEF. */
1975 if (is_new_name (def))
1976 register_new_update_set (def, names_replaced_by (def));
1977
1978 /* If DEF is an old name, register DEF as a new
1979 definition for itself. */
1980 if (is_old_name (def))
1981 register_new_update_single (def, def);
1982 }
1983
1984 return to_delete;
1985}
1986
1987
1988/* Update every variable used in the statement pointed-to by SI. The
1989 statement is assumed to be in SSA form already. Names in
1990 OLD_SSA_NAMES used by SI will be updated to their current reaching
1991 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1992 will be registered as a new definition for their corresponding name
1993 in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1994
1995static bool
1996rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
1997{
1998 use_operand_p use_p;
1999 def_operand_p def_p;
2000 ssa_op_iter iter;
2001
2002 /* Only update marked statements. */
2003 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
2004 return false;
2005
2006 if (dump_file && (dump_flags & TDF_DETAILS))
2007 {
2008 fprintf (dump_file, "Updating SSA information for statement ");
2009 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2010 }
2011
2012 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2013 symbol is marked for renaming. */
2014 if (rewrite_uses_p (stmt))
2015 {
2016 if (is_gimple_debug (stmt))
2017 {
2018 bool failed = false;
2019
2020 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2021 if (!maybe_replace_use_in_debug_stmt (use_p))
2022 {
2023 failed = true;
2024 break;
2025 }
2026
2027 if (failed)
2028 {
2029 /* DOM sometimes threads jumps in such a way that a
2030 debug stmt ends up referencing a SSA variable that no
2031 longer dominates the debug stmt, but such that all
2032 incoming definitions refer to the same definition in
2033 an earlier dominator. We could try to recover that
2034 definition somehow, but this will have to do for now.
2035
2036 Introducing a default definition, which is what
2037 maybe_replace_use() would do in such cases, may
2038 modify code generation, for the otherwise-unused
2039 default definition would never go away, modifying SSA
2040 version numbers all over. */
2041 gimple_debug_bind_reset_value (stmt);
2042 update_stmt (stmt);
2043 }
2044 }
2045 else
2046 {
2047 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2048 maybe_replace_use (use_p);
2049 }
2050 }
2051
2052 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2053 Also register definitions for names whose underlying symbol is
2054 marked for renaming. */
2055 bool to_delete = false;
2056 if (register_defs_p (stmt))
2057 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2058 to_delete |= maybe_register_def (def_p, stmt, gsi);
2059
2060 return to_delete;
2061}
2062
2063
2064/* Visit all the successor blocks of BB looking for PHI nodes. For
2065 every PHI node found, check if any of its arguments is in
2066 OLD_SSA_NAMES. If so, and if the argument has a current reaching
2067 definition, replace it. */
2068
2069static void
2070rewrite_update_phi_arguments (basic_block bb)
2071{
2072 edge e;
2073 edge_iterator ei;
2074 unsigned i;
2075
2076 FOR_EACH_EDGE (e, ei, bb->succs)
2077 {
2078 gphi *phi;
2079 vec<gphi *> phis;
2080
2081 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2082 continue;
2083
2084 phis = phis_to_rewrite[e->dest->index];
2085 FOR_EACH_VEC_ELT (phis, i, phi)
2086 {
2087 tree arg, lhs_sym, reaching_def = NULL;
2088 use_operand_p arg_p;
2089
2090 gcc_checking_assert (rewrite_uses_p (phi));
2091
2092 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2093 arg = USE_FROM_PTR (arg_p);
2094
2095 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2096 continue;
2097
2098 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2099
2100 if (arg == NULL_TREE)
2101 {
2102 /* When updating a PHI node for a recently introduced
2103 symbol we may find NULL arguments. That's why we
2104 take the symbol from the LHS of the PHI node. */
2105 reaching_def = get_reaching_def (lhs_sym);
2106
2107 }
2108 else
2109 {
2110 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2111
2112 if (marked_for_renaming (sym))
2113 reaching_def = get_reaching_def (sym);
2114 else if (is_old_name (arg))
2115 reaching_def = get_reaching_def (arg);
2116 }
2117
2118 /* Update the argument if there is a reaching def. */
2119 if (reaching_def)
2120 {
2121 source_location locus;
2122 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2123
2124 SET_USE (arg_p, reaching_def);
2125
2126 /* Virtual operands do not need a location. */
2127 if (virtual_operand_p (reaching_def))
2128 locus = UNKNOWN_LOCATION;
2129 else
2130 {
2131 gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
2132 gphi *other_phi = dyn_cast <gphi *> (stmt);
2133
2134 /* Single element PHI nodes behave like copies, so get the
2135 location from the phi argument. */
2136 if (other_phi
2137 && gimple_phi_num_args (other_phi) == 1)
2138 locus = gimple_phi_arg_location (other_phi, 0);
2139 else
2140 locus = gimple_location (stmt);
2141 }
2142
2143 gimple_phi_arg_set_location (phi, arg_i, locus);
2144 }
2145
2146
2147 if (e->flags & EDGE_ABNORMAL)
2148 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2149 }
2150 }
2151}
2152
2153class rewrite_update_dom_walker : public dom_walker
2154{
2155public:
2156 rewrite_update_dom_walker (cdi_direction direction) : dom_walker (direction) {}
2157
2158 virtual edge before_dom_children (basic_block);
2159 virtual void after_dom_children (basic_block);
2160};
2161
2162/* Initialization of block data structures for the incremental SSA
2163 update pass. Create a block local stack of reaching definitions
2164 for new SSA names produced in this block (BLOCK_DEFS). Register
2165 new definitions for every PHI node in the block. */
2166
2167edge
2168rewrite_update_dom_walker::before_dom_children (basic_block bb)
2169{
2170 bool is_abnormal_phi;
2171
2172 if (dump_file && (dump_flags & TDF_DETAILS))
2173 fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2174 bb->index);
2175
2176 /* Mark the unwind point for this block. */
2177 block_defs_stack.safe_push (NULL_TREE);
2178
2179 if (!bitmap_bit_p (blocks_to_update, bb->index))
2180 return NULL;
2181
2182 /* Mark the LHS if any of the arguments flows through an abnormal
2183 edge. */
2184 is_abnormal_phi = bb_has_abnormal_pred (bb);
2185
2186 /* If any of the PHI nodes is a replacement for a name in
2187 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2188 register it as a new definition for its corresponding name. Also
2189 register definitions for names whose underlying symbols are
2190 marked for renaming. */
2191 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2192 gsi_next (&gsi))
2193 {
2194 tree lhs, lhs_sym;
2195 gphi *phi = gsi.phi ();
2196
2197 if (!register_defs_p (phi))
2198 continue;
2199
2200 lhs = gimple_phi_result (phi);
2201 lhs_sym = SSA_NAME_VAR (lhs);
2202
2203 if (marked_for_renaming (lhs_sym))
2204 register_new_update_single (lhs, lhs_sym);
2205 else
2206 {
2207
2208 /* If LHS is a new name, register a new definition for all
2209 the names replaced by LHS. */
2210 if (is_new_name (lhs))
2211 register_new_update_set (lhs, names_replaced_by (lhs));
2212
2213 /* If LHS is an OLD name, register it as a new definition
2214 for itself. */
2215 if (is_old_name (lhs))
2216 register_new_update_single (lhs, lhs);
2217 }
2218
2219 if (is_abnormal_phi)
2220 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2221 }
2222
2223 /* Step 2. Rewrite every variable used in each statement in the block. */
2224 if (bitmap_bit_p (interesting_blocks, bb->index))
2225 {
2226 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2227 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2228 if (rewrite_update_stmt (gsi_stmt (gsi), gsi))
2229 gsi_remove (&gsi, true);
2230 else
2231 gsi_next (&gsi);
2232 }
2233
2234 /* Step 3. Update PHI nodes. */
2235 rewrite_update_phi_arguments (bb);
2236
2237 return NULL;
2238}
2239
2240/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2241 the current reaching definition of every name re-written in BB to
2242 the original reaching definition before visiting BB. This
2243 unwinding must be done in the opposite order to what is done in
2244 register_new_update_set. */
2245
2246void
2247rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2248{
2249 while (block_defs_stack.length () > 0)
2250 {
2251 tree var = block_defs_stack.pop ();
2252 tree saved_def;
2253
2254 /* NULL indicates the unwind stop point for this block (see
2255 rewrite_update_enter_block). */
2256 if (var == NULL)
2257 return;
2258
2259 saved_def = block_defs_stack.pop ();
2260 get_common_info (var)->current_def = saved_def;
2261 }
2262}
2263
2264
2265/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2266 form.
2267
2268 ENTRY indicates the block where to start. Every block dominated by
2269 ENTRY will be rewritten.
2270
2271 WHAT indicates what actions will be taken by the renamer (see enum
2272 rewrite_mode).
2273
2274 BLOCKS are the set of interesting blocks for the dominator walker
2275 to process. If this set is NULL, then all the nodes dominated
2276 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2277 are not present in BLOCKS are ignored. */
2278
2279static void
2280rewrite_blocks (basic_block entry, enum rewrite_mode what)
2281{
2282 /* Rewrite all the basic blocks in the program. */
2283 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2284
2285 block_defs_stack.create (10);
2286
2287 /* Recursively walk the dominator tree rewriting each statement in
2288 each basic block. */
2289 if (what == REWRITE_ALL)
2290 rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2291 else if (what == REWRITE_UPDATE)
2292 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2293 else
2294 gcc_unreachable ();
2295
2296 /* Debugging dumps. */
2297 if (dump_file && (dump_flags & TDF_STATS))
2298 {
2299 dump_dfa_stats (dump_file);
2300 if (var_infos)
2301 dump_tree_ssa_stats (dump_file);
2302 }
2303
2304 block_defs_stack.release ();
2305
2306 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2307}
2308
2309class mark_def_dom_walker : public dom_walker
2310{
2311public:
2312 mark_def_dom_walker (cdi_direction direction);
2313 ~mark_def_dom_walker ();
2314
2315 virtual edge before_dom_children (basic_block);
2316
2317private:
2318 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2319 large enough to accommodate all the variables referenced in the
2320 function, not just the ones we are renaming. */
2321 bitmap m_kills;
2322};
2323
2324mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2325 : dom_walker (direction), m_kills (BITMAP_ALLOC (NULL))
2326{
2327}
2328
2329mark_def_dom_walker::~mark_def_dom_walker ()
2330{
2331 BITMAP_FREE (m_kills);
2332}
2333
2334/* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2335 at the start of each block, and call mark_def_sites for each statement. */
2336
2337edge
2338mark_def_dom_walker::before_dom_children (basic_block bb)
2339{
2340 gimple_stmt_iterator gsi;
2341
2342 bitmap_clear (m_kills);
2343 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2344 mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2345 return NULL;
2346}
2347
2348/* Initialize internal data needed during renaming. */
2349
2350static void
2351init_ssa_renamer (void)
2352{
2353 cfun->gimple_df->in_ssa_p = false;
2354
2355 /* Allocate memory for the DEF_BLOCKS hash table. */
2356 gcc_assert (!var_infos);
2357 var_infos = new hash_table<var_info_hasher>
2358 (vec_safe_length (cfun->local_decls));
2359
2360 bitmap_obstack_initialize (&update_ssa_obstack);
2361}
2362
2363
2364/* Deallocate internal data structures used by the renamer. */
2365
2366static void
2367fini_ssa_renamer (void)
2368{
2369 delete var_infos;
2370 var_infos = NULL;
2371
2372 bitmap_obstack_release (&update_ssa_obstack);
2373
2374 cfun->gimple_df->ssa_renaming_needed = 0;
2375 cfun->gimple_df->rename_vops = 0;
2376 cfun->gimple_df->in_ssa_p = true;
2377}
2378
2379/* Main entry point into the SSA builder. The renaming process
2380 proceeds in four main phases:
2381
2382 1- Compute dominance frontier and immediate dominators, needed to
2383 insert PHI nodes and rename the function in dominator tree
2384 order.
2385
2386 2- Find and mark all the blocks that define variables.
2387
2388 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2389
2390 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2391
2392 Steps 3 and 4 are done using the dominator tree walker
2393 (walk_dominator_tree). */
2394
2395namespace {
2396
2397const pass_data pass_data_build_ssa =
2398{
2399 GIMPLE_PASS, /* type */
2400 "ssa", /* name */
2401 OPTGROUP_NONE, /* optinfo_flags */
2402 TV_TREE_SSA_OTHER, /* tv_id */
2403 PROP_cfg, /* properties_required */
2404 PROP_ssa, /* properties_provided */
2405 0, /* properties_destroyed */
2406 0, /* todo_flags_start */
2407 TODO_remove_unused_locals, /* todo_flags_finish */
2408};
2409
2410class pass_build_ssa : public gimple_opt_pass
2411{
2412public:
2413 pass_build_ssa (gcc::context *ctxt)
2414 : gimple_opt_pass (pass_data_build_ssa, ctxt)
2415 {}
2416
2417 /* opt_pass methods: */
2418 virtual bool gate (function *fun)
2419 {
2420 /* Do nothing for funcions that was produced already in SSA form. */
2421 return !(fun->curr_properties & PROP_ssa);
2422 }
2423
2424 virtual unsigned int execute (function *);
2425
2426}; // class pass_build_ssa
2427
2428unsigned int
2429pass_build_ssa::execute (function *fun)
2430{
2431 bitmap_head *dfs;
2432 basic_block bb;
2433
2434 /* Initialize operand data structures. */
2435 init_ssa_operands (fun);
2436
2437 /* Initialize internal data needed by the renamer. */
2438 init_ssa_renamer ();
2439
2440 /* Initialize the set of interesting blocks. The callback
2441 mark_def_sites will add to this set those blocks that the renamer
2442 should process. */
2443 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2444 bitmap_clear (interesting_blocks);
2445
2446 /* Initialize dominance frontier. */
2447 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2448 FOR_EACH_BB_FN (bb, fun)
2449 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2450
2451 /* 1- Compute dominance frontiers. */
2452 calculate_dominance_info (CDI_DOMINATORS);
2453 compute_dominance_frontiers (dfs);
2454
2455 /* 2- Find and mark definition sites. */
2456 mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2457
2458 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2459 insert_phi_nodes (dfs);
2460
2461 /* 4- Rename all the blocks. */
2462 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
2463
2464 /* Free allocated memory. */
2465 FOR_EACH_BB_FN (bb, fun)
2466 bitmap_clear (&dfs[bb->index]);
2467 free (dfs);
2468
2469 sbitmap_free (interesting_blocks);
2470
2471 fini_ssa_renamer ();
2472
2473 /* Try to get rid of all gimplifier generated temporaries by making
2474 its SSA names anonymous. This way we can garbage collect them
2475 all after removing unused locals which we do in our TODO. */
2476 unsigned i;
2477 tree name;
2478
2479 FOR_EACH_SSA_NAME (i, name, cfun)
2480 {
2481 if (SSA_NAME_IS_DEFAULT_DEF (name))
2482 continue;
2483 tree decl = SSA_NAME_VAR (name);
2484 if (decl
2485 && VAR_P (decl)
2486 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2487 && DECL_IGNORED_P (decl))
2488 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2489 }
2490
2491 return 0;
2492}
2493
2494} // anon namespace
2495
2496gimple_opt_pass *
2497make_pass_build_ssa (gcc::context *ctxt)
2498{
2499 return new pass_build_ssa (ctxt);
2500}
2501
2502
2503/* Mark the definition of VAR at STMT and BB as interesting for the
2504 renamer. BLOCKS is the set of blocks that need updating. */
2505
2506static void
2507mark_def_interesting (tree var, gimple *stmt, basic_block bb,
2508 bool insert_phi_p)
2509{
2510 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2511 set_register_defs (stmt, true);
2512
2513 if (insert_phi_p)
2514 {
2515 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2516
2517 set_def_block (var, bb, is_phi_p);
2518
2519 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2520 site for both itself and all the old names replaced by it. */
2521 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2522 {
2523 bitmap_iterator bi;
2524 unsigned i;
2525 bitmap set = names_replaced_by (var);
2526 if (set)
2527 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2528 set_def_block (ssa_name (i), bb, is_phi_p);
2529 }
2530 }
2531}
2532
2533
2534/* Mark the use of VAR at STMT and BB as interesting for the
2535 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2536 nodes. */
2537
2538static inline void
2539mark_use_interesting (tree var, gimple *stmt, basic_block bb,
2540 bool insert_phi_p)
2541{
2542 basic_block def_bb = gimple_bb (stmt);
2543
2544 mark_block_for_update (def_bb);
2545 mark_block_for_update (bb);
2546
2547 if (gimple_code (stmt) == GIMPLE_PHI)
2548 mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt));
2549 else
2550 {
2551 set_rewrite_uses (stmt, true);
2552
2553 if (is_gimple_debug (stmt))
2554 return;
2555 }
2556
2557 /* If VAR has not been defined in BB, then it is live-on-entry
2558 to BB. Note that we cannot just use the block holding VAR's
2559 definition because if VAR is one of the names in OLD_SSA_NAMES,
2560 it will have several definitions (itself and all the names that
2561 replace it). */
2562 if (insert_phi_p)
2563 {
2564 def_blocks *db_p = get_def_blocks_for (get_common_info (var));
2565 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2566 set_livein_block (var, bb);
2567 }
2568}
2569
2570
2571/* Do a dominator walk starting at BB processing statements that
2572 reference symbols in SSA operands. This is very similar to
2573 mark_def_sites, but the scan handles statements whose operands may
2574 already be SSA names.
2575
2576 If INSERT_PHI_P is true, mark those uses as live in the
2577 corresponding block. This is later used by the PHI placement
2578 algorithm to make PHI pruning decisions.
2579
2580 FIXME. Most of this would be unnecessary if we could associate a
2581 symbol to all the SSA names that reference it. But that
2582 sounds like it would be expensive to maintain. Still, it
2583 would be interesting to see if it makes better sense to do
2584 that. */
2585
2586static void
2587prepare_block_for_update (basic_block bb, bool insert_phi_p)
2588{
2589 basic_block son;
2590 edge e;
2591 edge_iterator ei;
2592
2593 mark_block_for_update (bb);
2594
2595 /* Process PHI nodes marking interesting those that define or use
2596 the symbols that we are interested in. */
2597 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
2598 gsi_next (&si))
2599 {
2600 gphi *phi = si.phi ();
2601 tree lhs_sym, lhs = gimple_phi_result (phi);
2602
2603 if (TREE_CODE (lhs) == SSA_NAME
2604 && (! virtual_operand_p (lhs)
2605 || ! cfun->gimple_df->rename_vops))
2606 continue;
2607
2608 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2609 mark_for_renaming (lhs_sym);
2610 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2611
2612 /* Mark the uses in phi nodes as interesting. It would be more correct
2613 to process the arguments of the phi nodes of the successor edges of
2614 BB at the end of prepare_block_for_update, however, that turns out
2615 to be significantly more expensive. Doing it here is conservatively
2616 correct -- it may only cause us to believe a value to be live in a
2617 block that also contains its definition, and thus insert a few more
2618 phi nodes for it. */
2619 FOR_EACH_EDGE (e, ei, bb->preds)
2620 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2621 }
2622
2623 /* Process the statements. */
2624 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
2625 gsi_next (&si))
2626 {
2627 gimple *stmt;
2628 ssa_op_iter i;
2629 use_operand_p use_p;
2630 def_operand_p def_p;
2631
2632 stmt = gsi_stmt (si);
2633
2634 if (cfun->gimple_df->rename_vops
2635 && gimple_vuse (stmt))
2636 {
2637 tree use = gimple_vuse (stmt);
2638 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2639 mark_for_renaming (sym);
2640 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2641 }
2642
2643 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2644 {
2645 tree use = USE_FROM_PTR (use_p);
2646 if (!DECL_P (use))
2647 continue;
2648 mark_for_renaming (use);
2649 mark_use_interesting (use, stmt, bb, insert_phi_p);
2650 }
2651
2652 if (cfun->gimple_df->rename_vops
2653 && gimple_vdef (stmt))
2654 {
2655 tree def = gimple_vdef (stmt);
2656 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2657 mark_for_renaming (sym);
2658 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2659 }
2660
2661 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2662 {
2663 tree def = DEF_FROM_PTR (def_p);
2664 if (!DECL_P (def))
2665 continue;
2666 mark_for_renaming (def);
2667 mark_def_interesting (def, stmt, bb, insert_phi_p);
2668 }
2669 }
2670
2671 /* Now visit all the blocks dominated by BB. */
2672 for (son = first_dom_son (CDI_DOMINATORS, bb);
2673 son;
2674 son = next_dom_son (CDI_DOMINATORS, son))
2675 prepare_block_for_update (son, insert_phi_p);
2676}
2677
2678
2679/* Helper for prepare_names_to_update. Mark all the use sites for
2680 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2681 prepare_names_to_update. */
2682
2683static void
2684prepare_use_sites_for (tree name, bool insert_phi_p)
2685{
2686 use_operand_p use_p;
2687 imm_use_iterator iter;
2688
2689 /* If we rename virtual operands do not update them. */
2690 if (virtual_operand_p (name)
2691 && cfun->gimple_df->rename_vops)
2692 return;
2693
2694 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2695 {
2696 gimple *stmt = USE_STMT (use_p);
2697 basic_block bb = gimple_bb (stmt);
2698
2699 if (gimple_code (stmt) == GIMPLE_PHI)
2700 {
2701 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2702 edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix);
2703 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2704 }
2705 else
2706 {
2707 /* For regular statements, mark this as an interesting use
2708 for NAME. */
2709 mark_use_interesting (name, stmt, bb, insert_phi_p);
2710 }
2711 }
2712}
2713
2714
2715/* Helper for prepare_names_to_update. Mark the definition site for
2716 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2717 prepare_names_to_update. */
2718
2719static void
2720prepare_def_site_for (tree name, bool insert_phi_p)
2721{
2722 gimple *stmt;
2723 basic_block bb;
2724
2725 gcc_checking_assert (names_to_release == NULL
2726 || !bitmap_bit_p (names_to_release,
2727 SSA_NAME_VERSION (name)));
2728
2729 /* If we rename virtual operands do not update them. */
2730 if (virtual_operand_p (name)
2731 && cfun->gimple_df->rename_vops)
2732 return;
2733
2734 stmt = SSA_NAME_DEF_STMT (name);
2735 bb = gimple_bb (stmt);
2736 if (bb)
2737 {
2738 gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2739 mark_block_for_update (bb);
2740 mark_def_interesting (name, stmt, bb, insert_phi_p);
2741 }
2742}
2743
2744
2745/* Mark definition and use sites of names in NEW_SSA_NAMES and
2746 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2747 PHI nodes for newly created names. */
2748
2749static void
2750prepare_names_to_update (bool insert_phi_p)
2751{
2752 unsigned i = 0;
2753 bitmap_iterator bi;
2754 sbitmap_iterator sbi;
2755
2756 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2757 remove it from NEW_SSA_NAMES so that we don't try to visit its
2758 defining basic block (which most likely doesn't exist). Notice
2759 that we cannot do the same with names in OLD_SSA_NAMES because we
2760 want to replace existing instances. */
2761 if (names_to_release)
2762 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2763 bitmap_clear_bit (new_ssa_names, i);
2764
2765 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2766 names may be considered to be live-in on blocks that contain
2767 definitions for their replacements. */
2768 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2769 prepare_def_site_for (ssa_name (i), insert_phi_p);
2770
2771 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2772 OLD_SSA_NAMES, but we have to ignore its definition site. */
2773 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2774 {
2775 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2776 prepare_def_site_for (ssa_name (i), insert_phi_p);
2777 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2778 }
2779}
2780
2781
2782/* Dump all the names replaced by NAME to FILE. */
2783
2784void
2785dump_names_replaced_by (FILE *file, tree name)
2786{
2787 unsigned i;
2788 bitmap old_set;
2789 bitmap_iterator bi;
2790
2791 print_generic_expr (file, name);
2792 fprintf (file, " -> { ");
2793
2794 old_set = names_replaced_by (name);
2795 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2796 {
2797 print_generic_expr (file, ssa_name (i));
2798 fprintf (file, " ");
2799 }
2800
2801 fprintf (file, "}\n");
2802}
2803
2804
2805/* Dump all the names replaced by NAME to stderr. */
2806
2807DEBUG_FUNCTION void
2808debug_names_replaced_by (tree name)
2809{
2810 dump_names_replaced_by (stderr, name);
2811}
2812
2813
2814/* Dump SSA update information to FILE. */
2815
2816void
2817dump_update_ssa (FILE *file)
2818{
2819 unsigned i = 0;
2820 bitmap_iterator bi;
2821
2822 if (!need_ssa_update_p (cfun))
2823 return;
2824
2825 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2826 {
2827 sbitmap_iterator sbi;
2828
2829 fprintf (file, "\nSSA replacement table\n");
2830 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2831 "O_1, ..., O_j\n\n");
2832
2833 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2834 dump_names_replaced_by (file, ssa_name (i));
2835 }
2836
2837 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2838 {
2839 fprintf (file, "\nSymbols to be put in SSA form\n");
2840 dump_decl_set (file, symbols_to_rename_set);
2841 fprintf (file, "\n");
2842 }
2843
2844 if (names_to_release && !bitmap_empty_p (names_to_release))
2845 {
2846 fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2847 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2848 {
2849 print_generic_expr (file, ssa_name (i));
2850 fprintf (file, " ");
2851 }
2852 fprintf (file, "\n");
2853 }
2854}
2855
2856
2857/* Dump SSA update information to stderr. */
2858
2859DEBUG_FUNCTION void
2860debug_update_ssa (void)
2861{
2862 dump_update_ssa (stderr);
2863}
2864
2865
2866/* Initialize data structures used for incremental SSA updates. */
2867
2868static void
2869init_update_ssa (struct function *fn)
2870{
2871 /* Reserve more space than the current number of names. The calls to
2872 add_new_name_mapping are typically done after creating new SSA
2873 names, so we'll need to reallocate these arrays. */
2874 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2875 bitmap_clear (old_ssa_names);
2876
2877 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2878 bitmap_clear (new_ssa_names);
2879
2880 bitmap_obstack_initialize (&update_ssa_obstack);
2881
2882 names_to_release = NULL;
2883 update_ssa_initialized_fn = fn;
2884}
2885
2886
2887/* Deallocate data structures used for incremental SSA updates. */
2888
2889void
2890delete_update_ssa (void)
2891{
2892 unsigned i;
2893 bitmap_iterator bi;
2894
2895 sbitmap_free (old_ssa_names);
2896 old_ssa_names = NULL;
2897
2898 sbitmap_free (new_ssa_names);
2899 new_ssa_names = NULL;
2900
2901 BITMAP_FREE (symbols_to_rename_set);
2902 symbols_to_rename_set = NULL;
2903 symbols_to_rename.release ();
2904
2905 if (names_to_release)
2906 {
2907 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2908 release_ssa_name (ssa_name (i));
2909 BITMAP_FREE (names_to_release);
2910 }
2911
2912 clear_ssa_name_info ();
2913
2914 fini_ssa_renamer ();
2915
2916 if (blocks_with_phis_to_rewrite)
2917 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2918 {
2919 vec<gphi *> phis = phis_to_rewrite[i];
2920 phis.release ();
2921 phis_to_rewrite[i].create (0);
2922 }
2923
2924 BITMAP_FREE (blocks_with_phis_to_rewrite);
2925 BITMAP_FREE (blocks_to_update);
2926
2927 update_ssa_initialized_fn = NULL;
2928}
2929
2930
2931/* Create a new name for OLD_NAME in statement STMT and replace the
2932 operand pointed to by DEF_P with the newly created name. If DEF_P
2933 is NULL then STMT should be a GIMPLE assignment.
2934 Return the new name and register the replacement mapping <NEW, OLD> in
2935 update_ssa's tables. */
2936
2937tree
2938create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
2939{
2940 tree new_name;
2941
2942 timevar_push (TV_TREE_SSA_INCREMENTAL);
2943
2944 if (!update_ssa_initialized_fn)
2945 init_update_ssa (cfun);
2946
2947 gcc_assert (update_ssa_initialized_fn == cfun);
2948
2949 new_name = duplicate_ssa_name (old_name, stmt);
2950 if (def)
2951 SET_DEF (def, new_name);
2952 else
2953 gimple_assign_set_lhs (stmt, new_name);
2954
2955 if (gimple_code (stmt) == GIMPLE_PHI)
2956 {
2957 basic_block bb = gimple_bb (stmt);
2958
2959 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2960 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2961 }
2962
2963 add_new_name_mapping (new_name, old_name);
2964
2965 /* For the benefit of passes that will be updating the SSA form on
2966 their own, set the current reaching definition of OLD_NAME to be
2967 NEW_NAME. */
2968 get_ssa_name_ann (old_name)->info.current_def = new_name;
2969
2970 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2971
2972 return new_name;
2973}
2974
2975
2976/* Mark virtual operands of FN for renaming by update_ssa. */
2977
2978void
2979mark_virtual_operands_for_renaming (struct function *fn)
2980{
2981 fn->gimple_df->ssa_renaming_needed = 1;
2982 fn->gimple_df->rename_vops = 1;
2983}
2984
2985/* Replace all uses of NAME by underlying variable and mark it
2986 for renaming. This assumes the defining statement of NAME is
2987 going to be removed. */
2988
2989void
2990mark_virtual_operand_for_renaming (tree name)
2991{
2992 tree name_var = SSA_NAME_VAR (name);
2993 bool used = false;
2994 imm_use_iterator iter;
2995 use_operand_p use_p;
2996 gimple *stmt;
2997
2998 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
2999 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
3000 {
3001 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3002 SET_USE (use_p, name_var);
3003 used = true;
3004 }
3005 if (used)
3006 mark_virtual_operands_for_renaming (cfun);
3007}
3008
3009/* Replace all uses of the virtual PHI result by its underlying variable
3010 and mark it for renaming. This assumes the PHI node is going to be
3011 removed. */
3012
3013void
3014mark_virtual_phi_result_for_renaming (gphi *phi)
3015{
3016 if (dump_file && (dump_flags & TDF_DETAILS))
3017 {
3018 fprintf (dump_file, "Marking result for renaming : ");
3019 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
3020 fprintf (dump_file, "\n");
3021 }
3022
3023 mark_virtual_operand_for_renaming (gimple_phi_result (phi));
3024}
3025
3026/* Return true if there is any work to be done by update_ssa
3027 for function FN. */
3028
3029bool
3030need_ssa_update_p (struct function *fn)
3031{
3032 gcc_assert (fn != NULL);
3033 return (update_ssa_initialized_fn == fn
3034 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
3035}
3036
3037/* Return true if name N has been registered in the replacement table. */
3038
3039bool
3040name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3041{
3042 if (!update_ssa_initialized_fn)
3043 return false;
3044
3045 gcc_assert (update_ssa_initialized_fn == cfun);
3046
3047 return is_new_name (n) || is_old_name (n);
3048}
3049
3050
3051/* Mark NAME to be released after update_ssa has finished. */
3052
3053void
3054release_ssa_name_after_update_ssa (tree name)
3055{
3056 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3057
3058 if (names_to_release == NULL)
3059 names_to_release = BITMAP_ALLOC (NULL);
3060
3061 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3062}
3063
3064
3065/* Insert new PHI nodes to replace VAR. DFS contains dominance
3066 frontier information. BLOCKS is the set of blocks to be updated.
3067
3068 This is slightly different than the regular PHI insertion
3069 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3070 real names (i.e., GIMPLE registers) are inserted:
3071
3072 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3073 nodes inside the region affected by the block that defines VAR
3074 and the blocks that define all its replacements. All these
3075 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3076
3077 First, we compute the entry point to the region (ENTRY). This is
3078 given by the nearest common dominator to all the definition
3079 blocks. When computing the iterated dominance frontier (IDF), any
3080 block not strictly dominated by ENTRY is ignored.
3081
3082 We then call the standard PHI insertion algorithm with the pruned
3083 IDF.
3084
3085 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3086 names is not pruned. PHI nodes are inserted at every IDF block. */
3087
3088static void
3089insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
3090 unsigned update_flags)
3091{
3092 basic_block entry;
3093 def_blocks *db;
3094 bitmap idf, pruned_idf;
3095 bitmap_iterator bi;
3096 unsigned i;
3097
3098 if (TREE_CODE (var) == SSA_NAME)
3099 gcc_checking_assert (is_old_name (var));
3100 else
3101 gcc_checking_assert (marked_for_renaming (var));
3102
3103 /* Get all the definition sites for VAR. */
3104 db = find_def_blocks_for (var);
3105
3106 /* No need to do anything if there were no definitions to VAR. */
3107 if (db == NULL || bitmap_empty_p (db->def_blocks))
3108 return;
3109
3110 /* Compute the initial iterated dominance frontier. */
3111 idf = compute_idf (db->def_blocks, dfs);
3112 pruned_idf = BITMAP_ALLOC (NULL);
3113
3114 if (TREE_CODE (var) == SSA_NAME)
3115 {
3116 if (update_flags == TODO_update_ssa)
3117 {
3118 /* If doing regular SSA updates for GIMPLE registers, we are
3119 only interested in IDF blocks dominated by the nearest
3120 common dominator of all the definition blocks. */
3121 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3122 db->def_blocks);
3123 if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3124 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3125 if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3126 && dominated_by_p (CDI_DOMINATORS,
3127 BASIC_BLOCK_FOR_FN (cfun, i), entry))
3128 bitmap_set_bit (pruned_idf, i);
3129 }
3130 else
3131 {
3132 /* Otherwise, do not prune the IDF for VAR. */
3133 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3134 bitmap_copy (pruned_idf, idf);
3135 }
3136 }
3137 else
3138 {
3139 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3140 for the first time, so we need to compute the full IDF for
3141 it. */
3142 bitmap_copy (pruned_idf, idf);
3143 }
3144
3145 if (!bitmap_empty_p (pruned_idf))
3146 {
3147 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3148 are included in the region to be updated. The feeding blocks
3149 are important to guarantee that the PHI arguments are renamed
3150 properly. */
3151
3152 /* FIXME, this is not needed if we are updating symbols. We are
3153 already starting at the ENTRY block anyway. */
3154 bitmap_ior_into (blocks, pruned_idf);
3155 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3156 {
3157 edge e;
3158 edge_iterator ei;
3159 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3160
3161 FOR_EACH_EDGE (e, ei, bb->preds)
3162 if (e->src->index >= 0)
3163 bitmap_set_bit (blocks, e->src->index);
3164 }
3165
3166 insert_phi_nodes_for (var, pruned_idf, true);
3167 }
3168
3169 BITMAP_FREE (pruned_idf);
3170 BITMAP_FREE (idf);
3171}
3172
3173/* Sort symbols_to_rename after their DECL_UID. */
3174
3175static int
3176insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3177{
3178 const_tree syma = *(const const_tree *)a;
3179 const_tree symb = *(const const_tree *)b;
3180 if (DECL_UID (syma) == DECL_UID (symb))
3181 return 0;
3182 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3183}
3184
3185/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3186 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3187
3188 1- The names in OLD_SSA_NAMES dominated by the definitions of
3189 NEW_SSA_NAMES are all re-written to be reached by the
3190 appropriate definition from NEW_SSA_NAMES.
3191
3192 2- If needed, new PHI nodes are added to the iterated dominance
3193 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3194
3195 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3196 calling create_new_def_for to create new defs for names that the
3197 caller wants to replace.
3198
3199 The caller cretaes the new names to be inserted and the names that need
3200 to be replaced by calling create_new_def_for for each old definition
3201 to be replaced. Note that the function assumes that the
3202 new defining statement has already been inserted in the IL.
3203
3204 For instance, given the following code:
3205
3206 1 L0:
3207 2 x_1 = PHI (0, x_5)
3208 3 if (x_1 < 10)
3209 4 if (x_1 > 7)
3210 5 y_2 = 0
3211 6 else
3212 7 y_3 = x_1 + x_7
3213 8 endif
3214 9 x_5 = x_1 + 1
3215 10 goto L0;
3216 11 endif
3217
3218 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3219
3220 1 L0:
3221 2 x_1 = PHI (0, x_5)
3222 3 if (x_1 < 10)
3223 4 x_10 = ...
3224 5 if (x_1 > 7)
3225 6 y_2 = 0
3226 7 else
3227 8 x_11 = ...
3228 9 y_3 = x_1 + x_7
3229 10 endif
3230 11 x_5 = x_1 + 1
3231 12 goto L0;
3232 13 endif
3233
3234 We want to replace all the uses of x_1 with the new definitions of
3235 x_10 and x_11. Note that the only uses that should be replaced are
3236 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3237 *not* be replaced (this is why we cannot just mark symbol 'x' for
3238 renaming).
3239
3240 Additionally, we may need to insert a PHI node at line 11 because
3241 that is a merge point for x_10 and x_11. So the use of x_1 at line
3242 11 will be replaced with the new PHI node. The insertion of PHI
3243 nodes is optional. They are not strictly necessary to preserve the
3244 SSA form, and depending on what the caller inserted, they may not
3245 even be useful for the optimizers. UPDATE_FLAGS controls various
3246 aspects of how update_ssa operates, see the documentation for
3247 TODO_update_ssa*. */
3248
3249void
3250update_ssa (unsigned update_flags)
3251{
3252 basic_block bb, start_bb;
3253 bitmap_iterator bi;
3254 unsigned i = 0;
3255 bool insert_phi_p;
3256 sbitmap_iterator sbi;
3257 tree sym;
3258
3259 /* Only one update flag should be set. */
3260 gcc_assert (update_flags == TODO_update_ssa
3261 || update_flags == TODO_update_ssa_no_phi
3262 || update_flags == TODO_update_ssa_full_phi
3263 || update_flags == TODO_update_ssa_only_virtuals);
3264
3265 if (!need_ssa_update_p (cfun))
3266 return;
3267
3268 if (flag_checking)
3269 {
3270 timevar_push (TV_TREE_STMT_VERIFY);
3271
3272 bool err = false;
3273
3274 FOR_EACH_BB_FN (bb, cfun)
3275 {
3276 gimple_stmt_iterator gsi;
3277 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3278 {
3279 gimple *stmt = gsi_stmt (gsi);
3280
3281 ssa_op_iter i;
3282 use_operand_p use_p;
3283 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3284 {
3285 tree use = USE_FROM_PTR (use_p);
3286 if (TREE_CODE (use) != SSA_NAME)
3287 continue;
3288
3289 if (SSA_NAME_IN_FREE_LIST (use))
3290 {
3291 error ("statement uses released SSA name:");
3292 debug_gimple_stmt (stmt);
3293 fprintf (stderr, "The use of ");
3294 print_generic_expr (stderr, use);
3295 fprintf (stderr," should have been replaced\n");
3296 err = true;
3297 }
3298 }
3299 }
3300 }
3301
3302 if (err)
3303 internal_error ("cannot update SSA form");
3304
3305 timevar_pop (TV_TREE_STMT_VERIFY);
3306 }
3307
3308 timevar_push (TV_TREE_SSA_INCREMENTAL);
3309
3310 if (dump_file && (dump_flags & TDF_DETAILS))
3311 fprintf (dump_file, "\nUpdating SSA:\n");
3312
3313 if (!update_ssa_initialized_fn)
3314 init_update_ssa (cfun);
3315 else if (update_flags == TODO_update_ssa_only_virtuals)
3316 {
3317 /* If we only need to update virtuals, remove all the mappings for
3318 real names before proceeding. The caller is responsible for
3319 having dealt with the name mappings before calling update_ssa. */
3320 bitmap_clear (old_ssa_names);
3321 bitmap_clear (new_ssa_names);
3322 }
3323
3324 gcc_assert (update_ssa_initialized_fn == cfun);
3325
3326 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3327 if (!phis_to_rewrite.exists ())
3328 phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3329 blocks_to_update = BITMAP_ALLOC (NULL);
3330
3331 /* Ensure that the dominance information is up-to-date. */
3332 calculate_dominance_info (CDI_DOMINATORS);
3333
3334 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3335
3336 /* If there are names defined in the replacement table, prepare
3337 definition and use sites for all the names in NEW_SSA_NAMES and
3338 OLD_SSA_NAMES. */
3339 if (bitmap_first_set_bit (new_ssa_names) >= 0)
3340 {
3341 statistics_counter_event (cfun, "Incremental SSA update", 1);
3342
3343 prepare_names_to_update (insert_phi_p);
3344
3345 /* If all the names in NEW_SSA_NAMES had been marked for
3346 removal, and there are no symbols to rename, then there's
3347 nothing else to do. */
3348 if (bitmap_first_set_bit (new_ssa_names) < 0
3349 && !cfun->gimple_df->ssa_renaming_needed)
3350 goto done;
3351 }
3352
3353 /* Next, determine the block at which to start the renaming process. */
3354 if (cfun->gimple_df->ssa_renaming_needed)
3355 {
3356 statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
3357
3358 /* If we rename bare symbols initialize the mapping to
3359 auxiliar info we need to keep track of. */
3360 var_infos = new hash_table<var_info_hasher> (47);
3361
3362 /* If we have to rename some symbols from scratch, we need to
3363 start the process at the root of the CFG. FIXME, it should
3364 be possible to determine the nearest block that had a
3365 definition for each of the symbols that are marked for
3366 updating. For now this seems more work than it's worth. */
3367 start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3368
3369 /* Traverse the CFG looking for existing definitions and uses of
3370 symbols in SSA operands. Mark interesting blocks and
3371 statements and set local live-in information for the PHI
3372 placement heuristics. */
3373 prepare_block_for_update (start_bb, insert_phi_p);
3374
3375 tree name;
3376
3377 if (flag_checking)
3378 FOR_EACH_SSA_NAME (i, name, cfun)
3379 {
3380 if (virtual_operand_p (name))
3381 continue;
3382
3383 /* For all but virtual operands, which do not have SSA names
3384 with overlapping life ranges, ensure that symbols marked
3385 for renaming do not have existing SSA names associated with
3386 them as we do not re-write them out-of-SSA before going
3387 into SSA for the remaining symbol uses. */
3388 if (marked_for_renaming (SSA_NAME_VAR (name)))
3389 {
3390 fprintf (stderr, "Existing SSA name for symbol marked for "
3391 "renaming: ");
3392 print_generic_expr (stderr, name, TDF_SLIM);
3393 fprintf (stderr, "\n");
3394 internal_error ("SSA corruption");
3395 }
3396 }
3397 }
3398 else
3399 {
3400 /* Otherwise, the entry block to the region is the nearest
3401 common dominator for the blocks in BLOCKS. */
3402 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3403 blocks_to_update);
3404 }
3405
3406 /* If requested, insert PHI nodes at the iterated dominance frontier
3407 of every block, creating new definitions for names in OLD_SSA_NAMES
3408 and for symbols found. */
3409 if (insert_phi_p)
3410 {
3411 bitmap_head *dfs;
3412
3413 /* If the caller requested PHI nodes to be added, compute
3414 dominance frontiers. */
3415 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3416 FOR_EACH_BB_FN (bb, cfun)
3417 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3418 compute_dominance_frontiers (dfs);
3419
3420 if (bitmap_first_set_bit (old_ssa_names) >= 0)
3421 {
3422 sbitmap_iterator sbi;
3423
3424 /* insert_update_phi_nodes_for will call add_new_name_mapping
3425 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3426 will grow while we are traversing it (but it will not
3427 gain any new members). Copy OLD_SSA_NAMES to a temporary
3428 for traversal. */
3429 auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names));
3430 bitmap_copy (tmp, old_ssa_names);
3431 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3432 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3433 update_flags);
3434 }
3435
3436 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3437 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3438 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3439 update_flags);
3440
3441 FOR_EACH_BB_FN (bb, cfun)
3442 bitmap_clear (&dfs[bb->index]);
3443 free (dfs);
3444
3445 /* Insertion of PHI nodes may have added blocks to the region.
3446 We need to re-compute START_BB to include the newly added
3447 blocks. */
3448 if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3449 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3450 blocks_to_update);
3451 }
3452
3453 /* Reset the current definition for name and symbol before renaming
3454 the sub-graph. */
3455 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3456 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3457
3458 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3459 get_var_info (sym)->info.current_def = NULL_TREE;
3460
3461 /* Now start the renaming process at START_BB. */
3462 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3463 bitmap_clear (interesting_blocks);
3464 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3465 bitmap_set_bit (interesting_blocks, i);
3466
3467 rewrite_blocks (start_bb, REWRITE_UPDATE);
3468
3469 sbitmap_free (interesting_blocks);
3470
3471 /* Debugging dumps. */
3472 if (dump_file)
3473 {
3474 int c;
3475 unsigned i;
3476
3477 dump_update_ssa (dump_file);
3478
3479 fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3480 start_bb->index);
3481
3482 c = 0;
3483 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3484 c++;
3485 fprintf (dump_file, "Number of blocks in CFG: %d\n",
3486 last_basic_block_for_fn (cfun));
3487 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3488 c, PERCENT (c, last_basic_block_for_fn (cfun)));
3489
3490 if (dump_flags & TDF_DETAILS)
3491 {
3492 fprintf (dump_file, "Affected blocks:");
3493 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3494 fprintf (dump_file, " %u", i);
3495 fprintf (dump_file, "\n");
3496 }
3497
3498 fprintf (dump_file, "\n\n");
3499 }
3500
3501 /* Free allocated memory. */
3502done:
3503 delete_update_ssa ();
3504
3505 timevar_pop (TV_TREE_SSA_INCREMENTAL);
3506}
3507