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