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