1 /* Rewrite a program in Normal form into SSA.
2 Copyright (C) 2001-2019 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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. */
55 struct 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. */
85 static vec<tree> block_defs_stack;
86
87
88 /* Set of existing SSA names being replaced by update_ssa. */
89 static 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. */
94 static sbitmap new_ssa_names;
95
96 static 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. */
101 bitmap 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. */
106 static vec< vec<gphi *> > phis_to_rewrite;
107
108 /* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
109 static 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. */
121 static struct function *update_ssa_initialized_fn = NULL;
122
123 /* Global data to attach to the main dominator walk structure. */
124 struct 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
135 enum 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. */
156 struct 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. */
171 struct 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
183 struct 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
189 inline hashval_t
hash(const value_type & p)190 var_info_hasher::hash (const value_type &p)
191 {
192 return DECL_UID (p->var);
193 }
194
195 inline bool
equal(const value_type & p1,const compare_type & p2)196 var_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. */
204 static hash_table<var_info_hasher> *var_infos;
205
206
207 /* Information stored for SSA names. */
208 struct 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
222 static vec<ssa_name_info *> info_for_ssa_name;
223 static unsigned current_info_for_ssa_name_age;
224
225 static bitmap_obstack update_ssa_obstack;
226
227 /* The set of blocks affected by update_ssa. */
228 static 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. */
236 enum 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. */
246 static bitmap symbols_to_rename_set;
247 static vec<tree> symbols_to_rename;
248
249 /* Mark SYM for renaming. */
250
251 static void
mark_for_renaming(tree sym)252 mark_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
262 static bool
marked_for_renaming(tree sym)263 marked_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
275 static inline bool
rewrite_uses_p(gimple * stmt)276 rewrite_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
284 static inline void
set_rewrite_uses(gimple * stmt,bool rewrite_p)285 set_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
299 static inline bool
register_defs_p(gimple * stmt)300 register_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
308 static inline void
set_register_defs(gimple * stmt,bool register_defs_p)309 set_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
317 static inline ssa_name_info *
get_ssa_name_ann(tree name)318 get_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
354 static inline var_info *
get_var_info(tree decl)355 get_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
374 static void
clear_ssa_name_info(void)375 clear_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
387 static inline common_info *
get_common_info(tree var)388 get_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
399 tree
get_current_def(tree var)400 get_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
408 void
set_current_def(tree var,tree def)409 set_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
417 static void
initialize_flags_in_bb(basic_block bb)418 initialize_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
445 static void
mark_block_for_update(basic_block bb)446 mark_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
458 static inline def_blocks *
get_def_blocks_for(common_info * info)459 get_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
476 static void
set_def_block(tree var,basic_block bb,bool phi_p)477 set_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
511 static void
set_livein_block(tree var,basic_block bb)512 set_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
545 static inline bool
is_old_name(tree name)546 is_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
558 static inline bool
is_new_name(tree name)559 is_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
571 static inline bitmap
names_replaced_by(tree new_tree)572 names_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
580 static inline void
add_to_repl_tbl(tree new_tree,tree old)581 add_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
595 static void
add_new_name_mapping(tree new_tree,tree old)596 add_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
640 static void
mark_def_sites(basic_block bb,gimple * stmt,bitmap kills)641 mark_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
702 struct 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
714 static int
cmp_dfsnum(const void * a,const void * b)715 cmp_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
726 static unsigned
find_dfsnum_interval(struct dom_dfsnum * defs,unsigned n,unsigned s)727 find_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
746 static void
prune_unused_phi_nodes(bitmap phis,bitmap kills,bitmap uses)747 prune_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
917 static inline def_blocks *
find_def_blocks_for(tree var)918 find_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
929 static void
mark_phi_for_rewrite(basic_block bb,gphi * phi)930 mark_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
966 static void
insert_phi_nodes_for(tree var,bitmap phi_insertion_points,bool update_p)967 insert_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
1047 static int
insert_phi_nodes_compare_var_infos(const void * a,const void * b)1048 insert_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
1062 static void
insert_phi_nodes(bitmap_head * dfs)1063 insert_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
1147 static void
register_new_def(tree def,tree sym)1148 register_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
1215 static tree
get_reaching_def(tree var)1216 get_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
1242 static void
rewrite_debug_stmt_uses(gimple * stmt)1243 rewrite_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
1346 static void
rewrite_stmt(gimple_stmt_iterator * si)1347 rewrite_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
1425 static void
rewrite_add_phi_arguments(basic_block bb)1426 rewrite_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;
1440 location_t loc;
1441
1442 phi = gsi.phi ();
1443 res = gimple_phi_result (phi);
1444 currdef = get_reaching_def (SSA_NAME_VAR (res));
1445 /* Virtual operand PHI args do not need a location. */
1446 if (virtual_operand_p (res))
1447 loc = UNKNOWN_LOCATION;
1448 else
1449 loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1450 add_phi_arg (phi, currdef, e, loc);
1451 }
1452 }
1453 }
1454
1455 class rewrite_dom_walker : public dom_walker
1456 {
1457 public:
rewrite_dom_walker(cdi_direction direction)1458 rewrite_dom_walker (cdi_direction direction)
1459 : dom_walker (direction, ALL_BLOCKS, NULL) {}
1460
1461 virtual edge before_dom_children (basic_block);
1462 virtual void after_dom_children (basic_block);
1463 };
1464
1465 /* SSA Rewriting Step 1. Initialization, create a block local stack
1466 of reaching definitions for new SSA names produced in this block
1467 (BLOCK_DEFS). Register new definitions for every PHI node in the
1468 block. */
1469
1470 edge
before_dom_children(basic_block bb)1471 rewrite_dom_walker::before_dom_children (basic_block bb)
1472 {
1473 if (dump_file && (dump_flags & TDF_DETAILS))
1474 fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1475
1476 /* Mark the unwind point for this block. */
1477 block_defs_stack.safe_push (NULL_TREE);
1478
1479 /* Step 1. Register new definitions for every PHI node in the block.
1480 Conceptually, all the PHI nodes are executed in parallel and each PHI
1481 node introduces a new version for the associated variable. */
1482 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1483 gsi_next (&gsi))
1484 {
1485 tree result = gimple_phi_result (gsi_stmt (gsi));
1486 register_new_def (result, SSA_NAME_VAR (result));
1487 }
1488
1489 /* Step 2. Rewrite every variable used in each statement in the block
1490 with its immediate reaching definitions. Update the current definition
1491 of a variable when a new real or virtual definition is found. */
1492 if (bitmap_bit_p (interesting_blocks, bb->index))
1493 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1494 gsi_next (&gsi))
1495 rewrite_stmt (&gsi);
1496
1497 /* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1498 For every PHI node found, add a new argument containing the current
1499 reaching definition for the variable and the edge through which that
1500 definition is reaching the PHI node. */
1501 rewrite_add_phi_arguments (bb);
1502
1503 return NULL;
1504 }
1505
1506
1507
1508 /* Called after visiting all the statements in basic block BB and all
1509 of its dominator children. Restore CURRDEFS to its original value. */
1510
1511 void
after_dom_children(basic_block bb ATTRIBUTE_UNUSED)1512 rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1513 {
1514 /* Restore CURRDEFS to its original state. */
1515 while (block_defs_stack.length () > 0)
1516 {
1517 tree tmp = block_defs_stack.pop ();
1518 tree saved_def, var;
1519
1520 if (tmp == NULL_TREE)
1521 break;
1522
1523 if (TREE_CODE (tmp) == SSA_NAME)
1524 {
1525 /* If we recorded an SSA_NAME, then make the SSA_NAME the
1526 current definition of its underlying variable. Note that
1527 if the SSA_NAME is not for a GIMPLE register, the symbol
1528 being defined is stored in the next slot in the stack.
1529 This mechanism is needed because an SSA name for a
1530 non-register symbol may be the definition for more than
1531 one symbol (e.g., SFTs, aliased variables, etc). */
1532 saved_def = tmp;
1533 var = SSA_NAME_VAR (saved_def);
1534 if (!is_gimple_reg (var))
1535 var = block_defs_stack.pop ();
1536 }
1537 else
1538 {
1539 /* If we recorded anything else, it must have been a _DECL
1540 node and its current reaching definition must have been
1541 NULL. */
1542 saved_def = NULL;
1543 var = tmp;
1544 }
1545
1546 get_common_info (var)->current_def = saved_def;
1547 }
1548 }
1549
1550
1551 /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1552
1553 DEBUG_FUNCTION void
debug_decl_set(bitmap set)1554 debug_decl_set (bitmap set)
1555 {
1556 dump_decl_set (stderr, set);
1557 fprintf (stderr, "\n");
1558 }
1559
1560
1561 /* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1562 stack up to a maximum of N levels. If N is -1, the whole stack is
1563 dumped. New levels are created when the dominator tree traversal
1564 used for renaming enters a new sub-tree. */
1565
1566 void
dump_defs_stack(FILE * file,int n)1567 dump_defs_stack (FILE *file, int n)
1568 {
1569 int i, j;
1570
1571 fprintf (file, "\n\nRenaming stack");
1572 if (n > 0)
1573 fprintf (file, " (up to %d levels)", n);
1574 fprintf (file, "\n\n");
1575
1576 i = 1;
1577 fprintf (file, "Level %d (current level)\n", i);
1578 for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1579 {
1580 tree name, var;
1581
1582 name = block_defs_stack[j];
1583 if (name == NULL_TREE)
1584 {
1585 i++;
1586 if (n > 0 && i > n)
1587 break;
1588 fprintf (file, "\nLevel %d\n", i);
1589 continue;
1590 }
1591
1592 if (DECL_P (name))
1593 {
1594 var = name;
1595 name = NULL_TREE;
1596 }
1597 else
1598 {
1599 var = SSA_NAME_VAR (name);
1600 if (!is_gimple_reg (var))
1601 {
1602 j--;
1603 var = block_defs_stack[j];
1604 }
1605 }
1606
1607 fprintf (file, " Previous CURRDEF (");
1608 print_generic_expr (file, var);
1609 fprintf (file, ") = ");
1610 if (name)
1611 print_generic_expr (file, name);
1612 else
1613 fprintf (file, "<NIL>");
1614 fprintf (file, "\n");
1615 }
1616 }
1617
1618
1619 /* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1620 stack up to a maximum of N levels. If N is -1, the whole stack is
1621 dumped. New levels are created when the dominator tree traversal
1622 used for renaming enters a new sub-tree. */
1623
1624 DEBUG_FUNCTION void
debug_defs_stack(int n)1625 debug_defs_stack (int n)
1626 {
1627 dump_defs_stack (stderr, n);
1628 }
1629
1630
1631 /* Dump the current reaching definition of every symbol to FILE. */
1632
1633 void
dump_currdefs(FILE * file)1634 dump_currdefs (FILE *file)
1635 {
1636 unsigned i;
1637 tree var;
1638
1639 if (symbols_to_rename.is_empty ())
1640 return;
1641
1642 fprintf (file, "\n\nCurrent reaching definitions\n\n");
1643 FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
1644 {
1645 common_info *info = get_common_info (var);
1646 fprintf (file, "CURRDEF (");
1647 print_generic_expr (file, var);
1648 fprintf (file, ") = ");
1649 if (info->current_def)
1650 print_generic_expr (file, info->current_def);
1651 else
1652 fprintf (file, "<NIL>");
1653 fprintf (file, "\n");
1654 }
1655 }
1656
1657
1658 /* Dump the current reaching definition of every symbol to stderr. */
1659
1660 DEBUG_FUNCTION void
debug_currdefs(void)1661 debug_currdefs (void)
1662 {
1663 dump_currdefs (stderr);
1664 }
1665
1666
1667 /* Dump SSA information to FILE. */
1668
1669 void
dump_tree_ssa(FILE * file)1670 dump_tree_ssa (FILE *file)
1671 {
1672 const char *funcname
1673 = lang_hooks.decl_printable_name (current_function_decl, 2);
1674
1675 fprintf (file, "SSA renaming information for %s\n\n", funcname);
1676
1677 dump_var_infos (file);
1678 dump_defs_stack (file, -1);
1679 dump_currdefs (file);
1680 dump_tree_ssa_stats (file);
1681 }
1682
1683
1684 /* Dump SSA information to stderr. */
1685
1686 DEBUG_FUNCTION void
debug_tree_ssa(void)1687 debug_tree_ssa (void)
1688 {
1689 dump_tree_ssa (stderr);
1690 }
1691
1692
1693 /* Dump statistics for the hash table HTAB. */
1694
1695 static void
htab_statistics(FILE * file,const hash_table<var_info_hasher> & htab)1696 htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
1697 {
1698 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1699 (long) htab.size (),
1700 (long) htab.elements (),
1701 htab.collisions ());
1702 }
1703
1704
1705 /* Dump SSA statistics on FILE. */
1706
1707 void
dump_tree_ssa_stats(FILE * file)1708 dump_tree_ssa_stats (FILE *file)
1709 {
1710 if (var_infos)
1711 {
1712 fprintf (file, "\nHash table statistics:\n");
1713 fprintf (file, " var_infos: ");
1714 htab_statistics (file, *var_infos);
1715 fprintf (file, "\n");
1716 }
1717 }
1718
1719
1720 /* Dump SSA statistics on stderr. */
1721
1722 DEBUG_FUNCTION void
debug_tree_ssa_stats(void)1723 debug_tree_ssa_stats (void)
1724 {
1725 dump_tree_ssa_stats (stderr);
1726 }
1727
1728
1729 /* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1730
1731 int
debug_var_infos_r(var_info ** slot,FILE * file)1732 debug_var_infos_r (var_info **slot, FILE *file)
1733 {
1734 var_info *info = *slot;
1735
1736 fprintf (file, "VAR: ");
1737 print_generic_expr (file, info->var, dump_flags);
1738 bitmap_print (file, info->info.def_blocks.def_blocks,
1739 ", DEF_BLOCKS: { ", "}");
1740 bitmap_print (file, info->info.def_blocks.livein_blocks,
1741 ", LIVEIN_BLOCKS: { ", "}");
1742 bitmap_print (file, info->info.def_blocks.phi_blocks,
1743 ", PHI_BLOCKS: { ", "}\n");
1744
1745 return 1;
1746 }
1747
1748
1749 /* Dump the VAR_INFOS hash table on FILE. */
1750
1751 void
dump_var_infos(FILE * file)1752 dump_var_infos (FILE *file)
1753 {
1754 fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
1755 if (var_infos)
1756 var_infos->traverse <FILE *, debug_var_infos_r> (file);
1757 }
1758
1759
1760 /* Dump the VAR_INFOS hash table on stderr. */
1761
1762 DEBUG_FUNCTION void
debug_var_infos(void)1763 debug_var_infos (void)
1764 {
1765 dump_var_infos (stderr);
1766 }
1767
1768
1769 /* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1770
1771 static inline void
register_new_update_single(tree new_name,tree old_name)1772 register_new_update_single (tree new_name, tree old_name)
1773 {
1774 common_info *info = get_common_info (old_name);
1775 tree currdef = info->current_def;
1776
1777 /* Push the current reaching definition into BLOCK_DEFS_STACK.
1778 This stack is later used by the dominator tree callbacks to
1779 restore the reaching definitions for all the variables
1780 defined in the block after a recursive visit to all its
1781 immediately dominated blocks. */
1782 block_defs_stack.reserve (2);
1783 block_defs_stack.quick_push (currdef);
1784 block_defs_stack.quick_push (old_name);
1785
1786 /* Set the current reaching definition for OLD_NAME to be
1787 NEW_NAME. */
1788 info->current_def = new_name;
1789 }
1790
1791
1792 /* Register NEW_NAME to be the new reaching definition for all the
1793 names in OLD_NAMES. Used by the incremental SSA update routines to
1794 replace old SSA names with new ones. */
1795
1796 static inline void
register_new_update_set(tree new_name,bitmap old_names)1797 register_new_update_set (tree new_name, bitmap old_names)
1798 {
1799 bitmap_iterator bi;
1800 unsigned i;
1801
1802 EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1803 register_new_update_single (new_name, ssa_name (i));
1804 }
1805
1806
1807
1808 /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1809 it is a symbol marked for renaming, replace it with USE_P's current
1810 reaching definition. */
1811
1812 static inline void
maybe_replace_use(use_operand_p use_p)1813 maybe_replace_use (use_operand_p use_p)
1814 {
1815 tree rdef = NULL_TREE;
1816 tree use = USE_FROM_PTR (use_p);
1817 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1818
1819 if (marked_for_renaming (sym))
1820 rdef = get_reaching_def (sym);
1821 else if (is_old_name (use))
1822 rdef = get_reaching_def (use);
1823
1824 if (rdef && rdef != use)
1825 SET_USE (use_p, rdef);
1826 }
1827
1828
1829 /* Same as maybe_replace_use, but without introducing default stmts,
1830 returning false to indicate a need to do so. */
1831
1832 static inline bool
maybe_replace_use_in_debug_stmt(use_operand_p use_p)1833 maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1834 {
1835 tree rdef = NULL_TREE;
1836 tree use = USE_FROM_PTR (use_p);
1837 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1838
1839 if (marked_for_renaming (sym))
1840 rdef = get_var_info (sym)->info.current_def;
1841 else if (is_old_name (use))
1842 {
1843 rdef = get_ssa_name_ann (use)->info.current_def;
1844 /* We can't assume that, if there's no current definition, the
1845 default one should be used. It could be the case that we've
1846 rearranged blocks so that the earlier definition no longer
1847 dominates the use. */
1848 if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1849 rdef = use;
1850 }
1851 else
1852 rdef = use;
1853
1854 if (rdef && rdef != use)
1855 SET_USE (use_p, rdef);
1856
1857 return rdef != NULL_TREE;
1858 }
1859
1860
1861 /* If DEF has x_5 = ASAN_POISON () as its current def, add
1862 ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1863 a poisoned (out of scope) variable. */
1864
1865 static void
maybe_add_asan_poison_write(tree def,gimple_stmt_iterator * gsi)1866 maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
1867 {
1868 tree cdef = get_current_def (def);
1869 if (cdef != NULL
1870 && TREE_CODE (cdef) == SSA_NAME
1871 && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), IFN_ASAN_POISON))
1872 {
1873 gcall *call
1874 = gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
1875 gimple_set_location (call, gimple_location (gsi_stmt (*gsi)));
1876 gsi_insert_before (gsi, call, GSI_SAME_STMT);
1877 }
1878 }
1879
1880
1881 /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1882 or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1883 register it as the current definition for the names replaced by
1884 DEF_P. Returns whether the statement should be removed. */
1885
1886 static inline bool
maybe_register_def(def_operand_p def_p,gimple * stmt,gimple_stmt_iterator gsi)1887 maybe_register_def (def_operand_p def_p, gimple *stmt,
1888 gimple_stmt_iterator gsi)
1889 {
1890 tree def = DEF_FROM_PTR (def_p);
1891 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1892 bool to_delete = false;
1893
1894 /* If DEF is a naked symbol that needs renaming, create a new
1895 name for it. */
1896 if (marked_for_renaming (sym))
1897 {
1898 if (DECL_P (def))
1899 {
1900 if (gimple_clobber_p (stmt) && is_gimple_reg (sym))
1901 {
1902 gcc_checking_assert (VAR_P (sym));
1903 /* Replace clobber stmts with a default def. This new use of a
1904 default definition may make it look like SSA_NAMEs have
1905 conflicting lifetimes, so we need special code to let them
1906 coalesce properly. */
1907 to_delete = true;
1908 def = get_or_create_ssa_default_def (cfun, sym);
1909 }
1910 else
1911 {
1912 if (asan_sanitize_use_after_scope ())
1913 maybe_add_asan_poison_write (def, &gsi);
1914 def = make_ssa_name (def, stmt);
1915 }
1916 SET_DEF (def_p, def);
1917
1918 tree tracked_var = target_for_debug_bind (sym);
1919 if (tracked_var)
1920 {
1921 gimple *note = gimple_build_debug_bind (tracked_var, def, stmt);
1922 /* If stmt ends the bb, insert the debug stmt on the single
1923 non-EH edge from the stmt. */
1924 if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
1925 {
1926 basic_block bb = gsi_bb (gsi);
1927 edge_iterator ei;
1928 edge e, ef = NULL;
1929 FOR_EACH_EDGE (e, ei, bb->succs)
1930 if (!(e->flags & EDGE_EH))
1931 {
1932 gcc_checking_assert (!ef);
1933 ef = e;
1934 }
1935 /* If there are other predecessors to ef->dest, then
1936 there must be PHI nodes for the modified
1937 variable, and therefore there will be debug bind
1938 stmts after the PHI nodes. The debug bind notes
1939 we'd insert would force the creation of a new
1940 block (diverging codegen) and be redundant with
1941 the post-PHI bind stmts, so don't add them.
1942
1943 As for the exit edge, there wouldn't be redundant
1944 bind stmts, but there wouldn't be a PC to bind
1945 them to either, so avoid diverging the CFG. */
1946 if (ef && single_pred_p (ef->dest)
1947 && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1948 {
1949 /* If there were PHI nodes in the node, we'd
1950 have to make sure the value we're binding
1951 doesn't need rewriting. But there shouldn't
1952 be PHI nodes in a single-predecessor block,
1953 so we just add the note. */
1954 gsi_insert_on_edge_immediate (ef, note);
1955 }
1956 }
1957 else
1958 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1959 }
1960 }
1961
1962 register_new_update_single (def, sym);
1963 }
1964 else
1965 {
1966 /* If DEF is a new name, register it as a new definition
1967 for all the names replaced by DEF. */
1968 if (is_new_name (def))
1969 register_new_update_set (def, names_replaced_by (def));
1970
1971 /* If DEF is an old name, register DEF as a new
1972 definition for itself. */
1973 if (is_old_name (def))
1974 register_new_update_single (def, def);
1975 }
1976
1977 return to_delete;
1978 }
1979
1980
1981 /* Update every variable used in the statement pointed-to by SI. The
1982 statement is assumed to be in SSA form already. Names in
1983 OLD_SSA_NAMES used by SI will be updated to their current reaching
1984 definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1985 will be registered as a new definition for their corresponding name
1986 in OLD_SSA_NAMES. Returns whether STMT should be removed. */
1987
1988 static bool
rewrite_update_stmt(gimple * stmt,gimple_stmt_iterator gsi)1989 rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
1990 {
1991 use_operand_p use_p;
1992 def_operand_p def_p;
1993 ssa_op_iter iter;
1994
1995 /* Only update marked statements. */
1996 if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1997 return false;
1998
1999 if (dump_file && (dump_flags & TDF_DETAILS))
2000 {
2001 fprintf (dump_file, "Updating SSA information for statement ");
2002 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2003 }
2004
2005 /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2006 symbol is marked for renaming. */
2007 if (rewrite_uses_p (stmt))
2008 {
2009 if (is_gimple_debug (stmt))
2010 {
2011 bool failed = false;
2012
2013 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2014 if (!maybe_replace_use_in_debug_stmt (use_p))
2015 {
2016 failed = true;
2017 break;
2018 }
2019
2020 if (failed)
2021 {
2022 /* DOM sometimes threads jumps in such a way that a
2023 debug stmt ends up referencing a SSA variable that no
2024 longer dominates the debug stmt, but such that all
2025 incoming definitions refer to the same definition in
2026 an earlier dominator. We could try to recover that
2027 definition somehow, but this will have to do for now.
2028
2029 Introducing a default definition, which is what
2030 maybe_replace_use() would do in such cases, may
2031 modify code generation, for the otherwise-unused
2032 default definition would never go away, modifying SSA
2033 version numbers all over. */
2034 gimple_debug_bind_reset_value (stmt);
2035 update_stmt (stmt);
2036 }
2037 }
2038 else
2039 {
2040 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2041 maybe_replace_use (use_p);
2042 }
2043 }
2044
2045 /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2046 Also register definitions for names whose underlying symbol is
2047 marked for renaming. */
2048 bool to_delete = false;
2049 if (register_defs_p (stmt))
2050 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2051 to_delete |= maybe_register_def (def_p, stmt, gsi);
2052
2053 return to_delete;
2054 }
2055
2056
2057 /* Visit all the successor blocks of BB looking for PHI nodes. For
2058 every PHI node found, check if any of its arguments is in
2059 OLD_SSA_NAMES. If so, and if the argument has a current reaching
2060 definition, replace it. */
2061
2062 static void
rewrite_update_phi_arguments(basic_block bb)2063 rewrite_update_phi_arguments (basic_block bb)
2064 {
2065 edge e;
2066 edge_iterator ei;
2067 unsigned i;
2068
2069 FOR_EACH_EDGE (e, ei, bb->succs)
2070 {
2071 gphi *phi;
2072 vec<gphi *> phis;
2073
2074 if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2075 continue;
2076
2077 phis = phis_to_rewrite[e->dest->index];
2078 FOR_EACH_VEC_ELT (phis, i, phi)
2079 {
2080 tree arg, lhs_sym, reaching_def = NULL;
2081 use_operand_p arg_p;
2082
2083 gcc_checking_assert (rewrite_uses_p (phi));
2084
2085 arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2086 arg = USE_FROM_PTR (arg_p);
2087
2088 if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2089 continue;
2090
2091 lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2092
2093 if (arg == NULL_TREE)
2094 {
2095 /* When updating a PHI node for a recently introduced
2096 symbol we may find NULL arguments. That's why we
2097 take the symbol from the LHS of the PHI node. */
2098 reaching_def = get_reaching_def (lhs_sym);
2099
2100 }
2101 else
2102 {
2103 tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2104
2105 if (marked_for_renaming (sym))
2106 reaching_def = get_reaching_def (sym);
2107 else if (is_old_name (arg))
2108 reaching_def = get_reaching_def (arg);
2109 }
2110
2111 /* Update the argument if there is a reaching def. */
2112 if (reaching_def)
2113 {
2114 location_t locus;
2115 int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2116
2117 SET_USE (arg_p, reaching_def);
2118
2119 /* Virtual operands do not need a location. */
2120 if (virtual_operand_p (reaching_def))
2121 locus = UNKNOWN_LOCATION;
2122 else
2123 {
2124 gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
2125 gphi *other_phi = dyn_cast <gphi *> (stmt);
2126
2127 /* Single element PHI nodes behave like copies, so get the
2128 location from the phi argument. */
2129 if (other_phi
2130 && gimple_phi_num_args (other_phi) == 1)
2131 locus = gimple_phi_arg_location (other_phi, 0);
2132 else
2133 locus = gimple_location (stmt);
2134 }
2135
2136 gimple_phi_arg_set_location (phi, arg_i, locus);
2137 }
2138
2139
2140 if (e->flags & EDGE_ABNORMAL)
2141 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2142 }
2143 }
2144 }
2145
2146 class rewrite_update_dom_walker : public dom_walker
2147 {
2148 public:
rewrite_update_dom_walker(cdi_direction direction)2149 rewrite_update_dom_walker (cdi_direction direction)
2150 : dom_walker (direction, ALL_BLOCKS, NULL) {}
2151
2152 virtual edge before_dom_children (basic_block);
2153 virtual void after_dom_children (basic_block);
2154 };
2155
2156 /* Initialization of block data structures for the incremental SSA
2157 update pass. Create a block local stack of reaching definitions
2158 for new SSA names produced in this block (BLOCK_DEFS). Register
2159 new definitions for every PHI node in the block. */
2160
2161 edge
before_dom_children(basic_block bb)2162 rewrite_update_dom_walker::before_dom_children (basic_block bb)
2163 {
2164 bool is_abnormal_phi;
2165
2166 if (dump_file && (dump_flags & TDF_DETAILS))
2167 fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
2168 bb->index);
2169
2170 /* Mark the unwind point for this block. */
2171 block_defs_stack.safe_push (NULL_TREE);
2172
2173 if (!bitmap_bit_p (blocks_to_update, bb->index))
2174 return NULL;
2175
2176 /* Mark the LHS if any of the arguments flows through an abnormal
2177 edge. */
2178 is_abnormal_phi = bb_has_abnormal_pred (bb);
2179
2180 /* If any of the PHI nodes is a replacement for a name in
2181 OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2182 register it as a new definition for its corresponding name. Also
2183 register definitions for names whose underlying symbols are
2184 marked for renaming. */
2185 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
2186 gsi_next (&gsi))
2187 {
2188 tree lhs, lhs_sym;
2189 gphi *phi = gsi.phi ();
2190
2191 if (!register_defs_p (phi))
2192 continue;
2193
2194 lhs = gimple_phi_result (phi);
2195 lhs_sym = SSA_NAME_VAR (lhs);
2196
2197 if (marked_for_renaming (lhs_sym))
2198 register_new_update_single (lhs, lhs_sym);
2199 else
2200 {
2201
2202 /* If LHS is a new name, register a new definition for all
2203 the names replaced by LHS. */
2204 if (is_new_name (lhs))
2205 register_new_update_set (lhs, names_replaced_by (lhs));
2206
2207 /* If LHS is an OLD name, register it as a new definition
2208 for itself. */
2209 if (is_old_name (lhs))
2210 register_new_update_single (lhs, lhs);
2211 }
2212
2213 if (is_abnormal_phi)
2214 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2215 }
2216
2217 /* Step 2. Rewrite every variable used in each statement in the block. */
2218 if (bitmap_bit_p (interesting_blocks, bb->index))
2219 {
2220 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2221 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2222 if (rewrite_update_stmt (gsi_stmt (gsi), gsi))
2223 gsi_remove (&gsi, true);
2224 else
2225 gsi_next (&gsi);
2226 }
2227
2228 /* Step 3. Update PHI nodes. */
2229 rewrite_update_phi_arguments (bb);
2230
2231 return NULL;
2232 }
2233
2234 /* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2235 the current reaching definition of every name re-written in BB to
2236 the original reaching definition before visiting BB. This
2237 unwinding must be done in the opposite order to what is done in
2238 register_new_update_set. */
2239
2240 void
after_dom_children(basic_block bb ATTRIBUTE_UNUSED)2241 rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2242 {
2243 while (block_defs_stack.length () > 0)
2244 {
2245 tree var = block_defs_stack.pop ();
2246 tree saved_def;
2247
2248 /* NULL indicates the unwind stop point for this block (see
2249 rewrite_update_enter_block). */
2250 if (var == NULL)
2251 return;
2252
2253 saved_def = block_defs_stack.pop ();
2254 get_common_info (var)->current_def = saved_def;
2255 }
2256 }
2257
2258
2259 /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2260 form.
2261
2262 ENTRY indicates the block where to start. Every block dominated by
2263 ENTRY will be rewritten.
2264
2265 WHAT indicates what actions will be taken by the renamer (see enum
2266 rewrite_mode).
2267
2268 BLOCKS are the set of interesting blocks for the dominator walker
2269 to process. If this set is NULL, then all the nodes dominated
2270 by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2271 are not present in BLOCKS are ignored. */
2272
2273 static void
rewrite_blocks(basic_block entry,enum rewrite_mode what)2274 rewrite_blocks (basic_block entry, enum rewrite_mode what)
2275 {
2276 /* Rewrite all the basic blocks in the program. */
2277 timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
2278
2279 block_defs_stack.create (10);
2280
2281 /* Recursively walk the dominator tree rewriting each statement in
2282 each basic block. */
2283 if (what == REWRITE_ALL)
2284 rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2285 else if (what == REWRITE_UPDATE)
2286 rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2287 else
2288 gcc_unreachable ();
2289
2290 /* Debugging dumps. */
2291 if (dump_file && (dump_flags & TDF_STATS))
2292 {
2293 dump_dfa_stats (dump_file);
2294 if (var_infos)
2295 dump_tree_ssa_stats (dump_file);
2296 }
2297
2298 block_defs_stack.release ();
2299
2300 timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
2301 }
2302
2303 class mark_def_dom_walker : public dom_walker
2304 {
2305 public:
2306 mark_def_dom_walker (cdi_direction direction);
2307 ~mark_def_dom_walker ();
2308
2309 virtual edge before_dom_children (basic_block);
2310
2311 private:
2312 /* Notice that this bitmap is indexed using variable UIDs, so it must be
2313 large enough to accommodate all the variables referenced in the
2314 function, not just the ones we are renaming. */
2315 bitmap m_kills;
2316 };
2317
mark_def_dom_walker(cdi_direction direction)2318 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2319 : dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL))
2320 {
2321 }
2322
~mark_def_dom_walker()2323 mark_def_dom_walker::~mark_def_dom_walker ()
2324 {
2325 BITMAP_FREE (m_kills);
2326 }
2327
2328 /* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2329 at the start of each block, and call mark_def_sites for each statement. */
2330
2331 edge
before_dom_children(basic_block bb)2332 mark_def_dom_walker::before_dom_children (basic_block bb)
2333 {
2334 gimple_stmt_iterator gsi;
2335
2336 bitmap_clear (m_kills);
2337 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2338 mark_def_sites (bb, gsi_stmt (gsi), m_kills);
2339 return NULL;
2340 }
2341
2342 /* Initialize internal data needed during renaming. */
2343
2344 static void
init_ssa_renamer(void)2345 init_ssa_renamer (void)
2346 {
2347 cfun->gimple_df->in_ssa_p = false;
2348
2349 /* Allocate memory for the DEF_BLOCKS hash table. */
2350 gcc_assert (!var_infos);
2351 var_infos = new hash_table<var_info_hasher>
2352 (vec_safe_length (cfun->local_decls));
2353
2354 bitmap_obstack_initialize (&update_ssa_obstack);
2355 }
2356
2357
2358 /* Deallocate internal data structures used by the renamer. */
2359
2360 static void
fini_ssa_renamer(void)2361 fini_ssa_renamer (void)
2362 {
2363 delete var_infos;
2364 var_infos = NULL;
2365
2366 bitmap_obstack_release (&update_ssa_obstack);
2367
2368 cfun->gimple_df->ssa_renaming_needed = 0;
2369 cfun->gimple_df->rename_vops = 0;
2370 cfun->gimple_df->in_ssa_p = true;
2371 }
2372
2373 /* Main entry point into the SSA builder. The renaming process
2374 proceeds in four main phases:
2375
2376 1- Compute dominance frontier and immediate dominators, needed to
2377 insert PHI nodes and rename the function in dominator tree
2378 order.
2379
2380 2- Find and mark all the blocks that define variables.
2381
2382 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2383
2384 4- Rename all the blocks (rewrite_blocks) and statements in the program.
2385
2386 Steps 3 and 4 are done using the dominator tree walker
2387 (walk_dominator_tree). */
2388
2389 namespace {
2390
2391 const pass_data pass_data_build_ssa =
2392 {
2393 GIMPLE_PASS, /* type */
2394 "ssa", /* name */
2395 OPTGROUP_NONE, /* optinfo_flags */
2396 TV_TREE_SSA_OTHER, /* tv_id */
2397 PROP_cfg, /* properties_required */
2398 PROP_ssa, /* properties_provided */
2399 0, /* properties_destroyed */
2400 0, /* todo_flags_start */
2401 TODO_remove_unused_locals, /* todo_flags_finish */
2402 };
2403
2404 class pass_build_ssa : public gimple_opt_pass
2405 {
2406 public:
pass_build_ssa(gcc::context * ctxt)2407 pass_build_ssa (gcc::context *ctxt)
2408 : gimple_opt_pass (pass_data_build_ssa, ctxt)
2409 {}
2410
2411 /* opt_pass methods: */
gate(function * fun)2412 virtual bool gate (function *fun)
2413 {
2414 /* Do nothing for funcions that was produced already in SSA form. */
2415 return !(fun->curr_properties & PROP_ssa);
2416 }
2417
2418 virtual unsigned int execute (function *);
2419
2420 }; // class pass_build_ssa
2421
2422 unsigned int
execute(function * fun)2423 pass_build_ssa::execute (function *fun)
2424 {
2425 bitmap_head *dfs;
2426 basic_block bb;
2427
2428 /* Initialize operand data structures. */
2429 init_ssa_operands (fun);
2430
2431 /* Initialize internal data needed by the renamer. */
2432 init_ssa_renamer ();
2433
2434 /* Initialize the set of interesting blocks. The callback
2435 mark_def_sites will add to this set those blocks that the renamer
2436 should process. */
2437 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2438 bitmap_clear (interesting_blocks);
2439
2440 /* Initialize dominance frontier. */
2441 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2442 FOR_EACH_BB_FN (bb, fun)
2443 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
2444
2445 /* 1- Compute dominance frontiers. */
2446 calculate_dominance_info (CDI_DOMINATORS);
2447 compute_dominance_frontiers (dfs);
2448
2449 /* 2- Find and mark definition sites. */
2450 mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2451
2452 /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2453 insert_phi_nodes (dfs);
2454
2455 /* 4- Rename all the blocks. */
2456 rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
2457
2458 /* Free allocated memory. */
2459 FOR_EACH_BB_FN (bb, fun)
2460 bitmap_clear (&dfs[bb->index]);
2461 free (dfs);
2462
2463 sbitmap_free (interesting_blocks);
2464
2465 fini_ssa_renamer ();
2466
2467 /* Try to get rid of all gimplifier generated temporaries by making
2468 its SSA names anonymous. This way we can garbage collect them
2469 all after removing unused locals which we do in our TODO. */
2470 unsigned i;
2471 tree name;
2472
2473 FOR_EACH_SSA_NAME (i, name, cfun)
2474 {
2475 if (SSA_NAME_IS_DEFAULT_DEF (name))
2476 continue;
2477 tree decl = SSA_NAME_VAR (name);
2478 if (decl
2479 && VAR_P (decl)
2480 && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2481 && DECL_IGNORED_P (decl))
2482 SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2483 }
2484
2485 /* Initialize SSA_NAME_POINTS_TO_READONLY_MEMORY. */
2486 tree fnspec = lookup_attribute ("fn spec",
2487 TYPE_ATTRIBUTES (TREE_TYPE (fun->decl)));
2488 if (fnspec)
2489 {
2490 fnspec = TREE_VALUE (TREE_VALUE (fnspec));
2491 unsigned i = 1;
2492 for (tree arg = DECL_ARGUMENTS (cfun->decl);
2493 arg; arg = DECL_CHAIN (arg), ++i)
2494 {
2495 if (i >= (unsigned) TREE_STRING_LENGTH (fnspec))
2496 break;
2497 if (TREE_STRING_POINTER (fnspec)[i] == 'R'
2498 || TREE_STRING_POINTER (fnspec)[i] == 'r')
2499 {
2500 tree name = ssa_default_def (fun, arg);
2501 if (name)
2502 SSA_NAME_POINTS_TO_READONLY_MEMORY (name) = 1;
2503 }
2504 }
2505 }
2506
2507 return 0;
2508 }
2509
2510 } // anon namespace
2511
2512 gimple_opt_pass *
make_pass_build_ssa(gcc::context * ctxt)2513 make_pass_build_ssa (gcc::context *ctxt)
2514 {
2515 return new pass_build_ssa (ctxt);
2516 }
2517
2518
2519 /* Mark the definition of VAR at STMT and BB as interesting for the
2520 renamer. BLOCKS is the set of blocks that need updating. */
2521
2522 static void
mark_def_interesting(tree var,gimple * stmt,basic_block bb,bool insert_phi_p)2523 mark_def_interesting (tree var, gimple *stmt, basic_block bb,
2524 bool insert_phi_p)
2525 {
2526 gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2527 set_register_defs (stmt, true);
2528
2529 if (insert_phi_p)
2530 {
2531 bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
2532
2533 set_def_block (var, bb, is_phi_p);
2534
2535 /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2536 site for both itself and all the old names replaced by it. */
2537 if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2538 {
2539 bitmap_iterator bi;
2540 unsigned i;
2541 bitmap set = names_replaced_by (var);
2542 if (set)
2543 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2544 set_def_block (ssa_name (i), bb, is_phi_p);
2545 }
2546 }
2547 }
2548
2549
2550 /* Mark the use of VAR at STMT and BB as interesting for the
2551 renamer. INSERT_PHI_P is true if we are going to insert new PHI
2552 nodes. */
2553
2554 static inline void
mark_use_interesting(tree var,gimple * stmt,basic_block bb,bool insert_phi_p)2555 mark_use_interesting (tree var, gimple *stmt, basic_block bb,
2556 bool insert_phi_p)
2557 {
2558 basic_block def_bb = gimple_bb (stmt);
2559
2560 mark_block_for_update (def_bb);
2561 mark_block_for_update (bb);
2562
2563 if (gimple_code (stmt) == GIMPLE_PHI)
2564 mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt));
2565 else
2566 {
2567 set_rewrite_uses (stmt, true);
2568
2569 if (is_gimple_debug (stmt))
2570 return;
2571 }
2572
2573 /* If VAR has not been defined in BB, then it is live-on-entry
2574 to BB. Note that we cannot just use the block holding VAR's
2575 definition because if VAR is one of the names in OLD_SSA_NAMES,
2576 it will have several definitions (itself and all the names that
2577 replace it). */
2578 if (insert_phi_p)
2579 {
2580 def_blocks *db_p = get_def_blocks_for (get_common_info (var));
2581 if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2582 set_livein_block (var, bb);
2583 }
2584 }
2585
2586
2587 /* Do a dominator walk starting at BB processing statements that
2588 reference symbols in SSA operands. This is very similar to
2589 mark_def_sites, but the scan handles statements whose operands may
2590 already be SSA names.
2591
2592 If INSERT_PHI_P is true, mark those uses as live in the
2593 corresponding block. This is later used by the PHI placement
2594 algorithm to make PHI pruning decisions.
2595
2596 FIXME. Most of this would be unnecessary if we could associate a
2597 symbol to all the SSA names that reference it. But that
2598 sounds like it would be expensive to maintain. Still, it
2599 would be interesting to see if it makes better sense to do
2600 that. */
2601
2602 static void
prepare_block_for_update(basic_block bb,bool insert_phi_p)2603 prepare_block_for_update (basic_block bb, bool insert_phi_p)
2604 {
2605 basic_block son;
2606 edge e;
2607 edge_iterator ei;
2608
2609 mark_block_for_update (bb);
2610
2611 /* Process PHI nodes marking interesting those that define or use
2612 the symbols that we are interested in. */
2613 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
2614 gsi_next (&si))
2615 {
2616 gphi *phi = si.phi ();
2617 tree lhs_sym, lhs = gimple_phi_result (phi);
2618
2619 if (TREE_CODE (lhs) == SSA_NAME
2620 && (! virtual_operand_p (lhs)
2621 || ! cfun->gimple_df->rename_vops))
2622 continue;
2623
2624 lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2625 mark_for_renaming (lhs_sym);
2626 mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2627
2628 /* Mark the uses in phi nodes as interesting. It would be more correct
2629 to process the arguments of the phi nodes of the successor edges of
2630 BB at the end of prepare_block_for_update, however, that turns out
2631 to be significantly more expensive. Doing it here is conservatively
2632 correct -- it may only cause us to believe a value to be live in a
2633 block that also contains its definition, and thus insert a few more
2634 phi nodes for it. */
2635 FOR_EACH_EDGE (e, ei, bb->preds)
2636 mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2637 }
2638
2639 /* Process the statements. */
2640 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
2641 gsi_next (&si))
2642 {
2643 gimple *stmt;
2644 ssa_op_iter i;
2645 use_operand_p use_p;
2646 def_operand_p def_p;
2647
2648 stmt = gsi_stmt (si);
2649
2650 if (cfun->gimple_df->rename_vops
2651 && gimple_vuse (stmt))
2652 {
2653 tree use = gimple_vuse (stmt);
2654 tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2655 mark_for_renaming (sym);
2656 mark_use_interesting (sym, stmt, bb, insert_phi_p);
2657 }
2658
2659 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2660 {
2661 tree use = USE_FROM_PTR (use_p);
2662 if (!DECL_P (use))
2663 continue;
2664 mark_for_renaming (use);
2665 mark_use_interesting (use, stmt, bb, insert_phi_p);
2666 }
2667
2668 if (cfun->gimple_df->rename_vops
2669 && gimple_vdef (stmt))
2670 {
2671 tree def = gimple_vdef (stmt);
2672 tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2673 mark_for_renaming (sym);
2674 mark_def_interesting (sym, stmt, bb, insert_phi_p);
2675 }
2676
2677 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2678 {
2679 tree def = DEF_FROM_PTR (def_p);
2680 if (!DECL_P (def))
2681 continue;
2682 mark_for_renaming (def);
2683 mark_def_interesting (def, stmt, bb, insert_phi_p);
2684 }
2685 }
2686
2687 /* Now visit all the blocks dominated by BB. */
2688 for (son = first_dom_son (CDI_DOMINATORS, bb);
2689 son;
2690 son = next_dom_son (CDI_DOMINATORS, son))
2691 prepare_block_for_update (son, insert_phi_p);
2692 }
2693
2694
2695 /* Helper for prepare_names_to_update. Mark all the use sites for
2696 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2697 prepare_names_to_update. */
2698
2699 static void
prepare_use_sites_for(tree name,bool insert_phi_p)2700 prepare_use_sites_for (tree name, bool insert_phi_p)
2701 {
2702 use_operand_p use_p;
2703 imm_use_iterator iter;
2704
2705 /* If we rename virtual operands do not update them. */
2706 if (virtual_operand_p (name)
2707 && cfun->gimple_df->rename_vops)
2708 return;
2709
2710 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2711 {
2712 gimple *stmt = USE_STMT (use_p);
2713 basic_block bb = gimple_bb (stmt);
2714
2715 if (gimple_code (stmt) == GIMPLE_PHI)
2716 {
2717 int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2718 edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix);
2719 mark_use_interesting (name, stmt, e->src, insert_phi_p);
2720 }
2721 else
2722 {
2723 /* For regular statements, mark this as an interesting use
2724 for NAME. */
2725 mark_use_interesting (name, stmt, bb, insert_phi_p);
2726 }
2727 }
2728 }
2729
2730
2731 /* Helper for prepare_names_to_update. Mark the definition site for
2732 NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2733 prepare_names_to_update. */
2734
2735 static void
prepare_def_site_for(tree name,bool insert_phi_p)2736 prepare_def_site_for (tree name, bool insert_phi_p)
2737 {
2738 gimple *stmt;
2739 basic_block bb;
2740
2741 gcc_checking_assert (names_to_release == NULL
2742 || !bitmap_bit_p (names_to_release,
2743 SSA_NAME_VERSION (name)));
2744
2745 /* If we rename virtual operands do not update them. */
2746 if (virtual_operand_p (name)
2747 && cfun->gimple_df->rename_vops)
2748 return;
2749
2750 stmt = SSA_NAME_DEF_STMT (name);
2751 bb = gimple_bb (stmt);
2752 if (bb)
2753 {
2754 gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2755 mark_block_for_update (bb);
2756 mark_def_interesting (name, stmt, bb, insert_phi_p);
2757 }
2758 }
2759
2760
2761 /* Mark definition and use sites of names in NEW_SSA_NAMES and
2762 OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2763 PHI nodes for newly created names. */
2764
2765 static void
prepare_names_to_update(bool insert_phi_p)2766 prepare_names_to_update (bool insert_phi_p)
2767 {
2768 unsigned i = 0;
2769 bitmap_iterator bi;
2770 sbitmap_iterator sbi;
2771
2772 /* If a name N from NEW_SSA_NAMES is also marked to be released,
2773 remove it from NEW_SSA_NAMES so that we don't try to visit its
2774 defining basic block (which most likely doesn't exist). Notice
2775 that we cannot do the same with names in OLD_SSA_NAMES because we
2776 want to replace existing instances. */
2777 if (names_to_release)
2778 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2779 bitmap_clear_bit (new_ssa_names, i);
2780
2781 /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2782 names may be considered to be live-in on blocks that contain
2783 definitions for their replacements. */
2784 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2785 prepare_def_site_for (ssa_name (i), insert_phi_p);
2786
2787 /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2788 OLD_SSA_NAMES, but we have to ignore its definition site. */
2789 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2790 {
2791 if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2792 prepare_def_site_for (ssa_name (i), insert_phi_p);
2793 prepare_use_sites_for (ssa_name (i), insert_phi_p);
2794 }
2795 }
2796
2797
2798 /* Dump all the names replaced by NAME to FILE. */
2799
2800 void
dump_names_replaced_by(FILE * file,tree name)2801 dump_names_replaced_by (FILE *file, tree name)
2802 {
2803 unsigned i;
2804 bitmap old_set;
2805 bitmap_iterator bi;
2806
2807 print_generic_expr (file, name);
2808 fprintf (file, " -> { ");
2809
2810 old_set = names_replaced_by (name);
2811 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2812 {
2813 print_generic_expr (file, ssa_name (i));
2814 fprintf (file, " ");
2815 }
2816
2817 fprintf (file, "}\n");
2818 }
2819
2820
2821 /* Dump all the names replaced by NAME to stderr. */
2822
2823 DEBUG_FUNCTION void
debug_names_replaced_by(tree name)2824 debug_names_replaced_by (tree name)
2825 {
2826 dump_names_replaced_by (stderr, name);
2827 }
2828
2829
2830 /* Dump SSA update information to FILE. */
2831
2832 void
dump_update_ssa(FILE * file)2833 dump_update_ssa (FILE *file)
2834 {
2835 unsigned i = 0;
2836 bitmap_iterator bi;
2837
2838 if (!need_ssa_update_p (cfun))
2839 return;
2840
2841 if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
2842 {
2843 sbitmap_iterator sbi;
2844
2845 fprintf (file, "\nSSA replacement table\n");
2846 fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2847 "O_1, ..., O_j\n\n");
2848
2849 EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2850 dump_names_replaced_by (file, ssa_name (i));
2851 }
2852
2853 if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
2854 {
2855 fprintf (file, "\nSymbols to be put in SSA form\n");
2856 dump_decl_set (file, symbols_to_rename_set);
2857 fprintf (file, "\n");
2858 }
2859
2860 if (names_to_release && !bitmap_empty_p (names_to_release))
2861 {
2862 fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
2863 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2864 {
2865 print_generic_expr (file, ssa_name (i));
2866 fprintf (file, " ");
2867 }
2868 fprintf (file, "\n");
2869 }
2870 }
2871
2872
2873 /* Dump SSA update information to stderr. */
2874
2875 DEBUG_FUNCTION void
debug_update_ssa(void)2876 debug_update_ssa (void)
2877 {
2878 dump_update_ssa (stderr);
2879 }
2880
2881
2882 /* Initialize data structures used for incremental SSA updates. */
2883
2884 static void
init_update_ssa(struct function * fn)2885 init_update_ssa (struct function *fn)
2886 {
2887 /* Reserve more space than the current number of names. The calls to
2888 add_new_name_mapping are typically done after creating new SSA
2889 names, so we'll need to reallocate these arrays. */
2890 old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2891 bitmap_clear (old_ssa_names);
2892
2893 new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2894 bitmap_clear (new_ssa_names);
2895
2896 bitmap_obstack_initialize (&update_ssa_obstack);
2897
2898 names_to_release = NULL;
2899 update_ssa_initialized_fn = fn;
2900 }
2901
2902
2903 /* Deallocate data structures used for incremental SSA updates. */
2904
2905 void
delete_update_ssa(void)2906 delete_update_ssa (void)
2907 {
2908 unsigned i;
2909 bitmap_iterator bi;
2910
2911 sbitmap_free (old_ssa_names);
2912 old_ssa_names = NULL;
2913
2914 sbitmap_free (new_ssa_names);
2915 new_ssa_names = NULL;
2916
2917 BITMAP_FREE (symbols_to_rename_set);
2918 symbols_to_rename_set = NULL;
2919 symbols_to_rename.release ();
2920
2921 if (names_to_release)
2922 {
2923 EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2924 release_ssa_name (ssa_name (i));
2925 BITMAP_FREE (names_to_release);
2926 }
2927
2928 clear_ssa_name_info ();
2929
2930 fini_ssa_renamer ();
2931
2932 if (blocks_with_phis_to_rewrite)
2933 EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
2934 {
2935 vec<gphi *> phis = phis_to_rewrite[i];
2936 phis.release ();
2937 phis_to_rewrite[i].create (0);
2938 }
2939
2940 BITMAP_FREE (blocks_with_phis_to_rewrite);
2941 BITMAP_FREE (blocks_to_update);
2942
2943 update_ssa_initialized_fn = NULL;
2944 }
2945
2946
2947 /* Create a new name for OLD_NAME in statement STMT and replace the
2948 operand pointed to by DEF_P with the newly created name. If DEF_P
2949 is NULL then STMT should be a GIMPLE assignment.
2950 Return the new name and register the replacement mapping <NEW, OLD> in
2951 update_ssa's tables. */
2952
2953 tree
create_new_def_for(tree old_name,gimple * stmt,def_operand_p def)2954 create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
2955 {
2956 tree new_name;
2957
2958 timevar_push (TV_TREE_SSA_INCREMENTAL);
2959
2960 if (!update_ssa_initialized_fn)
2961 init_update_ssa (cfun);
2962
2963 gcc_assert (update_ssa_initialized_fn == cfun);
2964
2965 new_name = duplicate_ssa_name (old_name, stmt);
2966 if (def)
2967 SET_DEF (def, new_name);
2968 else
2969 gimple_assign_set_lhs (stmt, new_name);
2970
2971 if (gimple_code (stmt) == GIMPLE_PHI)
2972 {
2973 basic_block bb = gimple_bb (stmt);
2974
2975 /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2976 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
2977 }
2978
2979 add_new_name_mapping (new_name, old_name);
2980
2981 /* For the benefit of passes that will be updating the SSA form on
2982 their own, set the current reaching definition of OLD_NAME to be
2983 NEW_NAME. */
2984 get_ssa_name_ann (old_name)->info.current_def = new_name;
2985
2986 timevar_pop (TV_TREE_SSA_INCREMENTAL);
2987
2988 return new_name;
2989 }
2990
2991
2992 /* Mark virtual operands of FN for renaming by update_ssa. */
2993
2994 void
mark_virtual_operands_for_renaming(struct function * fn)2995 mark_virtual_operands_for_renaming (struct function *fn)
2996 {
2997 fn->gimple_df->ssa_renaming_needed = 1;
2998 fn->gimple_df->rename_vops = 1;
2999 }
3000
3001 /* Replace all uses of NAME by underlying variable and mark it
3002 for renaming. This assumes the defining statement of NAME is
3003 going to be removed. */
3004
3005 void
mark_virtual_operand_for_renaming(tree name)3006 mark_virtual_operand_for_renaming (tree name)
3007 {
3008 tree name_var = SSA_NAME_VAR (name);
3009 bool used = false;
3010 imm_use_iterator iter;
3011 use_operand_p use_p;
3012 gimple *stmt;
3013
3014 gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
3015 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
3016 {
3017 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3018 SET_USE (use_p, name_var);
3019 used = true;
3020 }
3021 if (used)
3022 mark_virtual_operands_for_renaming (cfun);
3023 }
3024
3025 /* Replace all uses of the virtual PHI result by its underlying variable
3026 and mark it for renaming. This assumes the PHI node is going to be
3027 removed. */
3028
3029 void
mark_virtual_phi_result_for_renaming(gphi * phi)3030 mark_virtual_phi_result_for_renaming (gphi *phi)
3031 {
3032 if (dump_file && (dump_flags & TDF_DETAILS))
3033 {
3034 fprintf (dump_file, "Marking result for renaming : ");
3035 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
3036 fprintf (dump_file, "\n");
3037 }
3038
3039 mark_virtual_operand_for_renaming (gimple_phi_result (phi));
3040 }
3041
3042 /* Return true if there is any work to be done by update_ssa
3043 for function FN. */
3044
3045 bool
need_ssa_update_p(struct function * fn)3046 need_ssa_update_p (struct function *fn)
3047 {
3048 gcc_assert (fn != NULL);
3049 return (update_ssa_initialized_fn == fn
3050 || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
3051 }
3052
3053 /* Return true if name N has been registered in the replacement table. */
3054
3055 bool
name_registered_for_update_p(tree n ATTRIBUTE_UNUSED)3056 name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3057 {
3058 if (!update_ssa_initialized_fn)
3059 return false;
3060
3061 gcc_assert (update_ssa_initialized_fn == cfun);
3062
3063 return is_new_name (n) || is_old_name (n);
3064 }
3065
3066
3067 /* Mark NAME to be released after update_ssa has finished. */
3068
3069 void
release_ssa_name_after_update_ssa(tree name)3070 release_ssa_name_after_update_ssa (tree name)
3071 {
3072 gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3073
3074 if (names_to_release == NULL)
3075 names_to_release = BITMAP_ALLOC (NULL);
3076
3077 bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3078 }
3079
3080
3081 /* Insert new PHI nodes to replace VAR. DFS contains dominance
3082 frontier information. BLOCKS is the set of blocks to be updated.
3083
3084 This is slightly different than the regular PHI insertion
3085 algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3086 real names (i.e., GIMPLE registers) are inserted:
3087
3088 - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3089 nodes inside the region affected by the block that defines VAR
3090 and the blocks that define all its replacements. All these
3091 definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3092
3093 First, we compute the entry point to the region (ENTRY). This is
3094 given by the nearest common dominator to all the definition
3095 blocks. When computing the iterated dominance frontier (IDF), any
3096 block not strictly dominated by ENTRY is ignored.
3097
3098 We then call the standard PHI insertion algorithm with the pruned
3099 IDF.
3100
3101 - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3102 names is not pruned. PHI nodes are inserted at every IDF block. */
3103
3104 static void
insert_updated_phi_nodes_for(tree var,bitmap_head * dfs,bitmap blocks,unsigned update_flags)3105 insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
3106 unsigned update_flags)
3107 {
3108 basic_block entry;
3109 def_blocks *db;
3110 bitmap idf, pruned_idf;
3111 bitmap_iterator bi;
3112 unsigned i;
3113
3114 if (TREE_CODE (var) == SSA_NAME)
3115 gcc_checking_assert (is_old_name (var));
3116 else
3117 gcc_checking_assert (marked_for_renaming (var));
3118
3119 /* Get all the definition sites for VAR. */
3120 db = find_def_blocks_for (var);
3121
3122 /* No need to do anything if there were no definitions to VAR. */
3123 if (db == NULL || bitmap_empty_p (db->def_blocks))
3124 return;
3125
3126 /* Compute the initial iterated dominance frontier. */
3127 idf = compute_idf (db->def_blocks, dfs);
3128 pruned_idf = BITMAP_ALLOC (NULL);
3129
3130 if (TREE_CODE (var) == SSA_NAME)
3131 {
3132 if (update_flags == TODO_update_ssa)
3133 {
3134 /* If doing regular SSA updates for GIMPLE registers, we are
3135 only interested in IDF blocks dominated by the nearest
3136 common dominator of all the definition blocks. */
3137 entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3138 db->def_blocks);
3139 if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3140 EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3141 if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3142 && dominated_by_p (CDI_DOMINATORS,
3143 BASIC_BLOCK_FOR_FN (cfun, i), entry))
3144 bitmap_set_bit (pruned_idf, i);
3145 }
3146 else
3147 {
3148 /* Otherwise, do not prune the IDF for VAR. */
3149 gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3150 bitmap_copy (pruned_idf, idf);
3151 }
3152 }
3153 else
3154 {
3155 /* Otherwise, VAR is a symbol that needs to be put into SSA form
3156 for the first time, so we need to compute the full IDF for
3157 it. */
3158 bitmap_copy (pruned_idf, idf);
3159 }
3160
3161 if (!bitmap_empty_p (pruned_idf))
3162 {
3163 /* Make sure that PRUNED_IDF blocks and all their feeding blocks
3164 are included in the region to be updated. The feeding blocks
3165 are important to guarantee that the PHI arguments are renamed
3166 properly. */
3167
3168 /* FIXME, this is not needed if we are updating symbols. We are
3169 already starting at the ENTRY block anyway. */
3170 bitmap_ior_into (blocks, pruned_idf);
3171 EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3172 {
3173 edge e;
3174 edge_iterator ei;
3175 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3176
3177 FOR_EACH_EDGE (e, ei, bb->preds)
3178 if (e->src->index >= 0)
3179 bitmap_set_bit (blocks, e->src->index);
3180 }
3181
3182 insert_phi_nodes_for (var, pruned_idf, true);
3183 }
3184
3185 BITMAP_FREE (pruned_idf);
3186 BITMAP_FREE (idf);
3187 }
3188
3189 /* Sort symbols_to_rename after their DECL_UID. */
3190
3191 static int
insert_updated_phi_nodes_compare_uids(const void * a,const void * b)3192 insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3193 {
3194 const_tree syma = *(const const_tree *)a;
3195 const_tree symb = *(const const_tree *)b;
3196 if (DECL_UID (syma) == DECL_UID (symb))
3197 return 0;
3198 return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3199 }
3200
3201 /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3202 existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3203
3204 1- The names in OLD_SSA_NAMES dominated by the definitions of
3205 NEW_SSA_NAMES are all re-written to be reached by the
3206 appropriate definition from NEW_SSA_NAMES.
3207
3208 2- If needed, new PHI nodes are added to the iterated dominance
3209 frontier of the blocks where each of NEW_SSA_NAMES are defined.
3210
3211 The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3212 calling create_new_def_for to create new defs for names that the
3213 caller wants to replace.
3214
3215 The caller cretaes the new names to be inserted and the names that need
3216 to be replaced by calling create_new_def_for for each old definition
3217 to be replaced. Note that the function assumes that the
3218 new defining statement has already been inserted in the IL.
3219
3220 For instance, given the following code:
3221
3222 1 L0:
3223 2 x_1 = PHI (0, x_5)
3224 3 if (x_1 < 10)
3225 4 if (x_1 > 7)
3226 5 y_2 = 0
3227 6 else
3228 7 y_3 = x_1 + x_7
3229 8 endif
3230 9 x_5 = x_1 + 1
3231 10 goto L0;
3232 11 endif
3233
3234 Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3235
3236 1 L0:
3237 2 x_1 = PHI (0, x_5)
3238 3 if (x_1 < 10)
3239 4 x_10 = ...
3240 5 if (x_1 > 7)
3241 6 y_2 = 0
3242 7 else
3243 8 x_11 = ...
3244 9 y_3 = x_1 + x_7
3245 10 endif
3246 11 x_5 = x_1 + 1
3247 12 goto L0;
3248 13 endif
3249
3250 We want to replace all the uses of x_1 with the new definitions of
3251 x_10 and x_11. Note that the only uses that should be replaced are
3252 those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3253 *not* be replaced (this is why we cannot just mark symbol 'x' for
3254 renaming).
3255
3256 Additionally, we may need to insert a PHI node at line 11 because
3257 that is a merge point for x_10 and x_11. So the use of x_1 at line
3258 11 will be replaced with the new PHI node. The insertion of PHI
3259 nodes is optional. They are not strictly necessary to preserve the
3260 SSA form, and depending on what the caller inserted, they may not
3261 even be useful for the optimizers. UPDATE_FLAGS controls various
3262 aspects of how update_ssa operates, see the documentation for
3263 TODO_update_ssa*. */
3264
3265 void
update_ssa(unsigned update_flags)3266 update_ssa (unsigned update_flags)
3267 {
3268 basic_block bb, start_bb;
3269 bitmap_iterator bi;
3270 unsigned i = 0;
3271 bool insert_phi_p;
3272 sbitmap_iterator sbi;
3273 tree sym;
3274
3275 /* Only one update flag should be set. */
3276 gcc_assert (update_flags == TODO_update_ssa
3277 || update_flags == TODO_update_ssa_no_phi
3278 || update_flags == TODO_update_ssa_full_phi
3279 || update_flags == TODO_update_ssa_only_virtuals);
3280
3281 if (!need_ssa_update_p (cfun))
3282 return;
3283
3284 if (flag_checking)
3285 {
3286 timevar_push (TV_TREE_STMT_VERIFY);
3287
3288 bool err = false;
3289
3290 FOR_EACH_BB_FN (bb, cfun)
3291 {
3292 gimple_stmt_iterator gsi;
3293 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3294 {
3295 gimple *stmt = gsi_stmt (gsi);
3296
3297 ssa_op_iter i;
3298 use_operand_p use_p;
3299 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3300 {
3301 tree use = USE_FROM_PTR (use_p);
3302 if (TREE_CODE (use) != SSA_NAME)
3303 continue;
3304
3305 if (SSA_NAME_IN_FREE_LIST (use))
3306 {
3307 error ("statement uses released SSA name:");
3308 debug_gimple_stmt (stmt);
3309 fprintf (stderr, "The use of ");
3310 print_generic_expr (stderr, use);
3311 fprintf (stderr," should have been replaced\n");
3312 err = true;
3313 }
3314 }
3315 }
3316 }
3317
3318 if (err)
3319 internal_error ("cannot update SSA form");
3320
3321 timevar_pop (TV_TREE_STMT_VERIFY);
3322 }
3323
3324 timevar_push (TV_TREE_SSA_INCREMENTAL);
3325
3326 if (dump_file && (dump_flags & TDF_DETAILS))
3327 fprintf (dump_file, "\nUpdating SSA:\n");
3328
3329 if (!update_ssa_initialized_fn)
3330 init_update_ssa (cfun);
3331 else if (update_flags == TODO_update_ssa_only_virtuals)
3332 {
3333 /* If we only need to update virtuals, remove all the mappings for
3334 real names before proceeding. The caller is responsible for
3335 having dealt with the name mappings before calling update_ssa. */
3336 bitmap_clear (old_ssa_names);
3337 bitmap_clear (new_ssa_names);
3338 }
3339
3340 gcc_assert (update_ssa_initialized_fn == cfun);
3341
3342 blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3343 if (!phis_to_rewrite.exists ())
3344 phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3345 blocks_to_update = BITMAP_ALLOC (NULL);
3346
3347 /* Ensure that the dominance information is up-to-date. */
3348 calculate_dominance_info (CDI_DOMINATORS);
3349
3350 insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3351
3352 /* If there are names defined in the replacement table, prepare
3353 definition and use sites for all the names in NEW_SSA_NAMES and
3354 OLD_SSA_NAMES. */
3355 if (bitmap_first_set_bit (new_ssa_names) >= 0)
3356 {
3357 statistics_counter_event (cfun, "Incremental SSA update", 1);
3358
3359 prepare_names_to_update (insert_phi_p);
3360
3361 /* If all the names in NEW_SSA_NAMES had been marked for
3362 removal, and there are no symbols to rename, then there's
3363 nothing else to do. */
3364 if (bitmap_first_set_bit (new_ssa_names) < 0
3365 && !cfun->gimple_df->ssa_renaming_needed)
3366 goto done;
3367 }
3368
3369 /* Next, determine the block at which to start the renaming process. */
3370 if (cfun->gimple_df->ssa_renaming_needed)
3371 {
3372 statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
3373
3374 /* If we rename bare symbols initialize the mapping to
3375 auxiliar info we need to keep track of. */
3376 var_infos = new hash_table<var_info_hasher> (47);
3377
3378 /* If we have to rename some symbols from scratch, we need to
3379 start the process at the root of the CFG. FIXME, it should
3380 be possible to determine the nearest block that had a
3381 definition for each of the symbols that are marked for
3382 updating. For now this seems more work than it's worth. */
3383 start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3384
3385 /* Traverse the CFG looking for existing definitions and uses of
3386 symbols in SSA operands. Mark interesting blocks and
3387 statements and set local live-in information for the PHI
3388 placement heuristics. */
3389 prepare_block_for_update (start_bb, insert_phi_p);
3390
3391 tree name;
3392
3393 if (flag_checking)
3394 FOR_EACH_SSA_NAME (i, name, cfun)
3395 {
3396 if (virtual_operand_p (name))
3397 continue;
3398
3399 /* For all but virtual operands, which do not have SSA names
3400 with overlapping life ranges, ensure that symbols marked
3401 for renaming do not have existing SSA names associated with
3402 them as we do not re-write them out-of-SSA before going
3403 into SSA for the remaining symbol uses. */
3404 if (marked_for_renaming (SSA_NAME_VAR (name)))
3405 {
3406 fprintf (stderr, "Existing SSA name for symbol marked for "
3407 "renaming: ");
3408 print_generic_expr (stderr, name, TDF_SLIM);
3409 fprintf (stderr, "\n");
3410 internal_error ("SSA corruption");
3411 }
3412 }
3413 }
3414 else
3415 {
3416 /* Otherwise, the entry block to the region is the nearest
3417 common dominator for the blocks in BLOCKS. */
3418 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3419 blocks_to_update);
3420 }
3421
3422 /* If requested, insert PHI nodes at the iterated dominance frontier
3423 of every block, creating new definitions for names in OLD_SSA_NAMES
3424 and for symbols found. */
3425 if (insert_phi_p)
3426 {
3427 bitmap_head *dfs;
3428
3429 /* If the caller requested PHI nodes to be added, compute
3430 dominance frontiers. */
3431 dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3432 FOR_EACH_BB_FN (bb, cfun)
3433 bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
3434 compute_dominance_frontiers (dfs);
3435
3436 if (bitmap_first_set_bit (old_ssa_names) >= 0)
3437 {
3438 sbitmap_iterator sbi;
3439
3440 /* insert_update_phi_nodes_for will call add_new_name_mapping
3441 when inserting new PHI nodes, so the set OLD_SSA_NAMES
3442 will grow while we are traversing it (but it will not
3443 gain any new members). Copy OLD_SSA_NAMES to a temporary
3444 for traversal. */
3445 auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names));
3446 bitmap_copy (tmp, old_ssa_names);
3447 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
3448 insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3449 update_flags);
3450 }
3451
3452 symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3453 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3454 insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
3455 update_flags);
3456
3457 FOR_EACH_BB_FN (bb, cfun)
3458 bitmap_clear (&dfs[bb->index]);
3459 free (dfs);
3460
3461 /* Insertion of PHI nodes may have added blocks to the region.
3462 We need to re-compute START_BB to include the newly added
3463 blocks. */
3464 if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3465 start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3466 blocks_to_update);
3467 }
3468
3469 /* Reset the current definition for name and symbol before renaming
3470 the sub-graph. */
3471 EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3472 get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3473
3474 FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3475 get_var_info (sym)->info.current_def = NULL_TREE;
3476
3477 /* Now start the renaming process at START_BB. */
3478 interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3479 bitmap_clear (interesting_blocks);
3480 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3481 bitmap_set_bit (interesting_blocks, i);
3482
3483 rewrite_blocks (start_bb, REWRITE_UPDATE);
3484
3485 sbitmap_free (interesting_blocks);
3486
3487 /* Debugging dumps. */
3488 if (dump_file)
3489 {
3490 int c;
3491 unsigned i;
3492
3493 dump_update_ssa (dump_file);
3494
3495 fprintf (dump_file, "Incremental SSA update started at block: %d\n",
3496 start_bb->index);
3497
3498 c = 0;
3499 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3500 c++;
3501 fprintf (dump_file, "Number of blocks in CFG: %d\n",
3502 last_basic_block_for_fn (cfun));
3503 fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
3504 c, PERCENT (c, last_basic_block_for_fn (cfun)));
3505
3506 if (dump_flags & TDF_DETAILS)
3507 {
3508 fprintf (dump_file, "Affected blocks:");
3509 EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3510 fprintf (dump_file, " %u", i);
3511 fprintf (dump_file, "\n");
3512 }
3513
3514 fprintf (dump_file, "\n\n");
3515 }
3516
3517 /* Free allocated memory. */
3518 done:
3519 delete_update_ssa ();
3520
3521 timevar_pop (TV_TREE_SSA_INCREMENTAL);
3522 }
3523