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