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