Line data Source code
1 : /* Generic SSA value propagation engine.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 : Contributed by Diego Novillo <dnovillo@redhat.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by the
9 : Free Software Foundation; either version 3, or (at your option) any
10 : later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT
13 : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : 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 "tree.h"
26 : #include "gimple.h"
27 : #include "ssa.h"
28 : #include "gimple-pretty-print.h"
29 : #include "dumpfile.h"
30 : #include "gimple-iterator.h"
31 : #include "gimple-fold.h"
32 : #include "tree-eh.h"
33 : #include "tree-cfg.h"
34 : #include "tree-ssa.h"
35 : #include "tree-ssa-propagate.h"
36 : #include "domwalk.h"
37 : #include "cfgloop.h"
38 : #include "tree-cfgcleanup.h"
39 : #include "cfganal.h"
40 : #include "tree-ssa-dce.h"
41 :
42 : /* This file implements a generic value propagation engine based on
43 : the same propagation used by the SSA-CCP algorithm [1].
44 :
45 : Propagation is performed by simulating the execution of every
46 : statement that produces the value being propagated. Simulation
47 : proceeds as follows:
48 :
49 : 1- Initially, all edges of the CFG are marked not executable and
50 : the CFG worklist is seeded with all the statements in the entry
51 : basic block (block 0).
52 :
53 : 2- Every statement S is simulated with a call to the call-back
54 : function SSA_PROP_VISIT_STMT. This evaluation may produce 3
55 : results:
56 :
57 : SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
58 : interest and does not affect any of the work lists.
59 : The statement may be simulated again if any of its input
60 : operands change in future iterations of the simulator.
61 :
62 : SSA_PROP_VARYING: The value produced by S cannot be determined
63 : at compile time. Further simulation of S is not required.
64 : If S is a conditional jump, all the outgoing edges for the
65 : block are considered executable and added to the work
66 : list.
67 :
68 : SSA_PROP_INTERESTING: S produces a value that can be computed
69 : at compile time. Its result can be propagated into the
70 : statements that feed from S. Furthermore, if S is a
71 : conditional jump, only the edge known to be taken is added
72 : to the work list. Edges that are known not to execute are
73 : never simulated.
74 :
75 : 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
76 : return value from SSA_PROP_VISIT_PHI has the same semantics as
77 : described in #2.
78 :
79 : 4- Three work lists are kept. Statements are only added to these
80 : lists if they produce one of SSA_PROP_INTERESTING or
81 : SSA_PROP_VARYING.
82 :
83 : CFG_BLOCKS contains the list of blocks to be simulated.
84 : Blocks are added to this list if their incoming edges are
85 : found executable.
86 :
87 : SSA_EDGE_WORKLIST contains the list of statements that we
88 : need to revisit.
89 :
90 : 5- Simulation terminates when all three work lists are drained.
91 :
92 : Before calling ssa_propagate, it is important to clear
93 : prop_simulate_again_p for all the statements in the program that
94 : should be simulated. This initialization allows an implementation
95 : to specify which statements should never be simulated.
96 :
97 : It is also important to compute def-use information before calling
98 : ssa_propagate.
99 :
100 : References:
101 :
102 : [1] Constant propagation with conditional branches,
103 : Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
104 :
105 : [2] Building an Optimizing Compiler,
106 : Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
107 :
108 : [3] Advanced Compiler Design and Implementation,
109 : Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
110 :
111 : /* Worklists of control flow edge destinations. This contains
112 : the CFG order number of the blocks so we can iterate in CFG
113 : order by visiting in bit-order. We use two worklists to
114 : first make forward progress before iterating. */
115 : static bitmap cfg_blocks;
116 : static int *bb_to_cfg_order;
117 : static int *cfg_order_to_bb;
118 :
119 : /* Worklists of SSA edges which will need reexamination as their
120 : definition has changed. SSA edges are def-use edges in the SSA
121 : web. For each D-U edge, we store the target statement or PHI node
122 : UID in a bitmap. UIDs order stmts in execution order. We use
123 : two worklists to first make forward progress before iterating. */
124 : static bitmap ssa_edge_worklist;
125 : static vec<gimple *> uid_to_stmt;
126 :
127 : /* Current RPO index in the iteration. */
128 : static int curr_order;
129 :
130 :
131 : /* We have just defined a new value for VAR. If IS_VARYING is true,
132 : add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
133 : them to INTERESTING_SSA_EDGES. */
134 :
135 : static void
136 281373184 : add_ssa_edge (tree var)
137 : {
138 281373184 : imm_use_iterator iter;
139 281373184 : use_operand_p use_p;
140 :
141 1144740842 : FOR_EACH_IMM_USE_FAST (use_p, iter, var)
142 : {
143 581994474 : gimple *use_stmt = USE_STMT (use_p);
144 581994474 : if (!prop_simulate_again_p (use_stmt))
145 246275520 : continue;
146 :
147 : /* If we did not yet simulate the block wait for this to happen
148 : and do not add the stmt to the SSA edge worklist. */
149 335718954 : basic_block use_bb = gimple_bb (use_stmt);
150 335718954 : if (! (use_bb->flags & BB_VISITED))
151 136970823 : continue;
152 :
153 : /* If this is a use on a not yet executable edge do not bother to
154 : queue it. */
155 198748131 : if (gimple_code (use_stmt) == GIMPLE_PHI
156 198748131 : && !(EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->flags
157 64352902 : & EDGE_EXECUTABLE))
158 5835397 : continue;
159 :
160 192912734 : if (bitmap_set_bit (ssa_edge_worklist, gimple_uid (use_stmt)))
161 : {
162 178523982 : uid_to_stmt[gimple_uid (use_stmt)] = use_stmt;
163 178523982 : if (dump_file && (dump_flags & TDF_DETAILS))
164 : {
165 0 : fprintf (dump_file, "ssa_edge_worklist: adding SSA use in ");
166 0 : print_gimple_stmt (dump_file, use_stmt, 0, TDF_SLIM);
167 : }
168 : }
169 281373184 : }
170 281373184 : }
171 :
172 :
173 : /* Add edge E to the control flow worklist. */
174 :
175 : static void
176 135158421 : add_control_edge (edge e)
177 : {
178 135158421 : basic_block bb = e->dest;
179 135158421 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
180 : return;
181 :
182 : /* If the edge had already been executed, skip it. */
183 119678005 : if (e->flags & EDGE_EXECUTABLE)
184 : return;
185 :
186 103559502 : e->flags |= EDGE_EXECUTABLE;
187 :
188 103559502 : int bb_order = bb_to_cfg_order[bb->index];
189 103559502 : bitmap_set_bit (cfg_blocks, bb_order);
190 :
191 103559502 : if (dump_file && (dump_flags & TDF_DETAILS))
192 61 : fprintf (dump_file, "Adding destination of edge (%d -> %d) to worklist\n",
193 61 : e->src->index, e->dest->index);
194 : }
195 :
196 :
197 : /* Simulate the execution of STMT and update the work lists accordingly. */
198 :
199 : void
200 795077325 : ssa_propagation_engine::simulate_stmt (gimple *stmt)
201 : {
202 795077325 : enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
203 795077325 : edge taken_edge = NULL;
204 795077325 : tree output_name = NULL_TREE;
205 :
206 : /* Pull the stmt off the SSA edge worklist. */
207 795077325 : bitmap_clear_bit (ssa_edge_worklist, gimple_uid (stmt));
208 :
209 : /* Don't bother visiting statements that are already
210 : considered varying by the propagator. */
211 795077325 : if (!prop_simulate_again_p (stmt))
212 562163996 : return;
213 :
214 353275831 : if (gimple_code (stmt) == GIMPLE_PHI)
215 : {
216 78463063 : val = visit_phi (as_a <gphi *> (stmt));
217 78463063 : output_name = gimple_phi_result (stmt);
218 : }
219 : else
220 274812768 : val = visit_stmt (stmt, &taken_edge, &output_name);
221 :
222 353275831 : if (val == SSA_PROP_VARYING)
223 : {
224 120362502 : prop_set_simulate_again (stmt, false);
225 :
226 : /* If the statement produced a new varying value, add the SSA
227 : edges coming out of OUTPUT_NAME. */
228 120362502 : if (output_name)
229 71943091 : add_ssa_edge (output_name);
230 :
231 : /* If STMT transfers control out of its basic block, add
232 : all outgoing edges to the work list. */
233 120362502 : if (stmt_ends_bb_p (stmt))
234 : {
235 49831353 : edge e;
236 49831353 : edge_iterator ei;
237 49831353 : basic_block bb = gimple_bb (stmt);
238 128226299 : FOR_EACH_EDGE (e, ei, bb->succs)
239 78394946 : add_control_edge (e);
240 : }
241 120362502 : return;
242 : }
243 232913329 : else if (val == SSA_PROP_INTERESTING)
244 : {
245 : /* If the statement produced new value, add the SSA edges coming
246 : out of OUTPUT_NAME. */
247 215974224 : if (output_name)
248 209430093 : add_ssa_edge (output_name);
249 :
250 : /* If we know which edge is going to be taken out of this block,
251 : add it to the CFG work list. */
252 215974224 : if (taken_edge)
253 6544131 : add_control_edge (taken_edge);
254 : }
255 :
256 : /* If there are no SSA uses on the stmt whose defs are simulated
257 : again then this stmt will be never visited again. */
258 232913329 : bool has_simulate_again_uses = false;
259 232913329 : use_operand_p use_p;
260 232913329 : ssa_op_iter iter;
261 232913329 : if (gimple_code (stmt) == GIMPLE_PHI)
262 : {
263 65462086 : edge_iterator ei;
264 65462086 : edge e;
265 65462086 : tree arg;
266 102027661 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
267 100215144 : if (!(e->flags & EDGE_EXECUTABLE)
268 100215144 : || ((arg = PHI_ARG_DEF_FROM_EDGE (stmt, e))
269 92177552 : && TREE_CODE (arg) == SSA_NAME
270 75721477 : && !SSA_NAME_IS_DEFAULT_DEF (arg)
271 75515590 : && prop_simulate_again_p (SSA_NAME_DEF_STMT (arg))))
272 : {
273 : has_simulate_again_uses = true;
274 : break;
275 : }
276 : }
277 : else
278 205353780 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
279 : {
280 166235644 : gimple *def_stmt = SSA_NAME_DEF_STMT (USE_FROM_PTR (use_p));
281 166235644 : if (!gimple_nop_p (def_stmt)
282 166235644 : && prop_simulate_again_p (def_stmt))
283 : {
284 : has_simulate_again_uses = true;
285 : break;
286 : }
287 : }
288 232913329 : if (!has_simulate_again_uses)
289 : {
290 40930653 : if (dump_file && (dump_flags & TDF_DETAILS))
291 40 : fprintf (dump_file, "marking stmt to be not simulated again\n");
292 40930653 : prop_set_simulate_again (stmt, false);
293 : }
294 : }
295 :
296 :
297 : /* Simulate the execution of BLOCK. Evaluate the statement associated
298 : with each variable reference inside the block. */
299 :
300 : void
301 79017795 : ssa_propagation_engine::simulate_block (basic_block block)
302 : {
303 79017795 : gimple_stmt_iterator gsi;
304 :
305 : /* There is nothing to do for the exit block. */
306 79017795 : if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
307 79017795 : return;
308 :
309 79017795 : if (dump_file && (dump_flags & TDF_DETAILS))
310 57 : fprintf (dump_file, "\nSimulating block %d\n", block->index);
311 :
312 : /* Always simulate PHI nodes, even if we have simulated this block
313 : before. */
314 120142104 : for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
315 41124309 : simulate_stmt (gsi_stmt (gsi));
316 :
317 : /* If this is the first time we've simulated this block, then we
318 : must simulate each of its statements. */
319 79017795 : if (! (block->flags & BB_VISITED))
320 : {
321 73845695 : gimple_stmt_iterator j;
322 73845695 : unsigned int normal_edge_count;
323 73845695 : edge e, normal_edge;
324 73845695 : edge_iterator ei;
325 :
326 723226571 : for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
327 575535181 : simulate_stmt (gsi_stmt (j));
328 :
329 : /* Note that we have simulated this block. */
330 73845695 : block->flags |= BB_VISITED;
331 :
332 : /* We cannot predict when abnormal and EH edges will be executed, so
333 : once a block is considered executable, we consider any
334 : outgoing abnormal edges as executable.
335 :
336 : TODO: This is not exactly true. Simplifying statement might
337 : prove it non-throwing and also computed goto can be handled
338 : when destination is known.
339 :
340 : At the same time, if this block has only one successor that is
341 : reached by non-abnormal edges, then add that successor to the
342 : worklist. */
343 73845695 : normal_edge_count = 0;
344 73845695 : normal_edge = NULL;
345 177688935 : FOR_EACH_EDGE (e, ei, block->succs)
346 : {
347 103843240 : if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
348 6641883 : add_control_edge (e);
349 : else
350 : {
351 97201357 : normal_edge_count++;
352 97201357 : normal_edge = e;
353 : }
354 : }
355 :
356 73845695 : if (normal_edge_count == 1)
357 35670338 : add_control_edge (normal_edge);
358 : }
359 : }
360 :
361 :
362 : /* Initialize local data structures and work lists. */
363 :
364 : static void
365 7907123 : ssa_prop_init (void)
366 : {
367 7907123 : edge e;
368 7907123 : edge_iterator ei;
369 7907123 : basic_block bb;
370 :
371 : /* Worklists of SSA edges. */
372 7907123 : ssa_edge_worklist = BITMAP_ALLOC (NULL);
373 7907123 : bitmap_tree_view (ssa_edge_worklist);
374 :
375 : /* Worklist of basic-blocks. */
376 7907123 : bb_to_cfg_order = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
377 7907123 : cfg_order_to_bb = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
378 7907123 : int n = pre_and_rev_post_order_compute_fn (cfun, NULL,
379 : cfg_order_to_bb, false);
380 82313120 : for (int i = 0; i < n; ++i)
381 74405997 : bb_to_cfg_order[cfg_order_to_bb[i]] = i;
382 7907123 : cfg_blocks = BITMAP_ALLOC (NULL);
383 :
384 : /* Initially assume that every edge in the CFG is not executable.
385 : (including the edges coming out of the entry block). Mark blocks
386 : as not visited, blocks not yet visited will have all their statements
387 : simulated once an incoming edge gets executable. */
388 7907123 : set_gimple_stmt_max_uid (cfun, 0);
389 82313120 : for (int i = 0; i < n; ++i)
390 : {
391 74405997 : gimple_stmt_iterator si;
392 74405997 : bb = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb[i]);
393 :
394 104372437 : for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
395 : {
396 29966440 : gimple *stmt = gsi_stmt (si);
397 29966440 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
398 : }
399 :
400 726730184 : for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
401 : {
402 577918190 : gimple *stmt = gsi_stmt (si);
403 577918190 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
404 : }
405 :
406 74405997 : bb->flags &= ~BB_VISITED;
407 178773522 : FOR_EACH_EDGE (e, ei, bb->succs)
408 104367525 : e->flags &= ~EDGE_EXECUTABLE;
409 : }
410 7907123 : uid_to_stmt.safe_grow (gimple_stmt_max_uid (cfun), true);
411 7907123 : }
412 :
413 :
414 : /* Free allocated storage. */
415 :
416 : static void
417 7907123 : ssa_prop_fini (void)
418 : {
419 7907123 : BITMAP_FREE (cfg_blocks);
420 7907123 : free (bb_to_cfg_order);
421 7907123 : free (cfg_order_to_bb);
422 7907123 : BITMAP_FREE (ssa_edge_worklist);
423 7907123 : uid_to_stmt.release ();
424 7907123 : }
425 :
426 :
427 : /* Entry point to the propagation engine.
428 :
429 : The VISIT_STMT virtual function is called for every statement
430 : visited and the VISIT_PHI virtual function is called for every PHI
431 : node visited. */
432 :
433 : void
434 7907123 : ssa_propagation_engine::ssa_propagate (void)
435 : {
436 7907123 : ssa_prop_init ();
437 :
438 7907123 : curr_order = 0;
439 :
440 : /* Iterate until the worklists are empty. We iterate both blocks
441 : and stmts in RPO order, prioritizing backedge processing.
442 : Seed the algorithm by adding the successors of the entry block to the
443 : edge worklist. */
444 7907123 : edge e;
445 7907123 : edge_iterator ei;
446 15814246 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
447 : {
448 7907123 : e->flags &= ~EDGE_EXECUTABLE;
449 7907123 : add_control_edge (e);
450 : }
451 265342753 : while (1)
452 : {
453 265342753 : int next_block_order = (bitmap_empty_p (cfg_blocks)
454 265342753 : ? -1 : bitmap_first_set_bit (cfg_blocks));
455 265342753 : int next_stmt_uid = (bitmap_empty_p (ssa_edge_worklist)
456 265342753 : ? -1 : bitmap_first_set_bit (ssa_edge_worklist));
457 265342753 : if (next_block_order == -1 && next_stmt_uid == -1)
458 : break;
459 :
460 257435630 : int next_stmt_bb_order = -1;
461 257435630 : gimple *next_stmt = NULL;
462 257435630 : if (next_stmt_uid != -1)
463 : {
464 182011883 : next_stmt = uid_to_stmt[next_stmt_uid];
465 182011883 : next_stmt_bb_order = bb_to_cfg_order[gimple_bb (next_stmt)->index];
466 : }
467 :
468 : /* Pull the next block to simulate off the worklist if it comes first. */
469 257435630 : if (next_block_order != -1
470 227039652 : && (next_stmt_bb_order == -1
471 227039652 : || next_block_order <= next_stmt_bb_order))
472 : {
473 79017795 : curr_order = next_block_order;
474 79017795 : bitmap_clear_bit (cfg_blocks, next_block_order);
475 79017795 : basic_block bb
476 79017795 : = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb [next_block_order]);
477 79017795 : simulate_block (bb);
478 79017795 : }
479 : /* Else simulate from the SSA edge worklist. */
480 : else
481 : {
482 178417835 : curr_order = next_stmt_bb_order;
483 178417835 : if (dump_file && (dump_flags & TDF_DETAILS))
484 : {
485 0 : fprintf (dump_file, "\nSimulating statement: ");
486 0 : print_gimple_stmt (dump_file, next_stmt, 0, dump_flags);
487 : }
488 178417835 : simulate_stmt (next_stmt);
489 : }
490 : }
491 :
492 7907123 : ssa_prop_fini ();
493 7907123 : }
494 :
495 : /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
496 : is a non-volatile pointer dereference, a structure reference or a
497 : reference to a single _DECL. Ignore volatile memory references
498 : because they are not interesting for the optimizers. */
499 :
500 : bool
501 30851536 : stmt_makes_single_store (gimple *stmt)
502 : {
503 30851536 : tree lhs;
504 :
505 30851536 : if (gimple_code (stmt) != GIMPLE_ASSIGN
506 30851536 : && gimple_code (stmt) != GIMPLE_CALL)
507 : return false;
508 :
509 30866196 : if (!gimple_vdef (stmt))
510 : return false;
511 :
512 2497380 : lhs = gimple_get_lhs (stmt);
513 :
514 : /* A call statement may have a null LHS. */
515 2497380 : if (!lhs)
516 : return false;
517 :
518 2497380 : return (!TREE_THIS_VOLATILE (lhs)
519 2497380 : && (DECL_P (lhs)
520 2482720 : || REFERENCE_CLASS_P (lhs)));
521 : }
522 :
523 :
524 : /* Propagation statistics. */
525 : struct prop_stats_d
526 : {
527 : long num_const_prop;
528 : long num_copy_prop;
529 : long num_stmts_folded;
530 : };
531 :
532 : static struct prop_stats_d prop_stats;
533 :
534 : // range_query default methods to drive from a value_of_expr() ranther than
535 : // range_of_expr.
536 :
537 : tree
538 55462269 : substitute_and_fold_engine::value_on_edge (edge, tree expr)
539 : {
540 55462269 : return value_of_expr (expr);
541 : }
542 :
543 : tree
544 131020009 : substitute_and_fold_engine::value_of_stmt (gimple *stmt, tree name)
545 : {
546 131020009 : if (!name)
547 0 : name = gimple_get_lhs (stmt);
548 :
549 131020009 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
550 :
551 131020009 : if (name)
552 131020009 : return value_of_expr (name);
553 : return NULL_TREE;
554 : }
555 :
556 : bool
557 0 : substitute_and_fold_engine::range_of_expr (vrange &, tree, gimple *)
558 : {
559 0 : return false;
560 : }
561 :
562 : /* Replace USE references in statement STMT with the values stored in
563 : PROP_VALUE. Return true if at least one reference was replaced. */
564 :
565 : bool
566 803773543 : substitute_and_fold_engine::replace_uses_in (gimple *stmt)
567 : {
568 803773543 : bool replaced = false;
569 803773543 : use_operand_p use;
570 803773543 : ssa_op_iter iter;
571 :
572 1181417838 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
573 : {
574 377644295 : tree tuse = USE_FROM_PTR (use);
575 377644295 : tree val = value_of_expr (tuse, stmt);
576 :
577 377644295 : if (val == tuse || val == NULL_TREE)
578 363842290 : continue;
579 :
580 13802005 : if (!may_propagate_copy (tuse, val))
581 522 : continue;
582 :
583 13801483 : if (TREE_CODE (val) != SSA_NAME)
584 5403700 : prop_stats.num_const_prop++;
585 : else
586 8397783 : prop_stats.num_copy_prop++;
587 :
588 13801483 : propagate_value (use, val);
589 :
590 13801483 : replaced = true;
591 : }
592 :
593 803773543 : return replaced;
594 : }
595 :
596 :
597 : /* Replace propagated values into all the arguments for PHI using the
598 : values from PROP_VALUE. */
599 :
600 : bool
601 22634540 : substitute_and_fold_engine::replace_phi_args_in (gphi *phi)
602 : {
603 22634540 : size_t i;
604 22634540 : bool replaced = false;
605 :
606 76527528 : for (i = 0; i < gimple_phi_num_args (phi); i++)
607 : {
608 53892988 : tree arg = gimple_phi_arg_def (phi, i);
609 :
610 53892988 : if (TREE_CODE (arg) == SSA_NAME)
611 : {
612 38162883 : edge e = gimple_phi_arg_edge (phi, i);
613 38162883 : tree val = value_on_edge (e, arg);
614 :
615 38162883 : if (val && val != arg && may_propagate_copy (arg, val))
616 : {
617 1126919 : if (TREE_CODE (val) != SSA_NAME)
618 31021 : prop_stats.num_const_prop++;
619 : else
620 1095898 : prop_stats.num_copy_prop++;
621 :
622 1126919 : propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
623 1126919 : replaced = true;
624 :
625 : /* If we propagated a copy and this argument flows
626 : through an abnormal edge, update the replacement
627 : accordingly. */
628 1126919 : if (TREE_CODE (val) == SSA_NAME
629 1095898 : && e->flags & EDGE_ABNORMAL
630 1126919 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
631 : {
632 : /* This can only occur for virtual operands, since
633 : for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
634 : would prevent replacement. */
635 0 : gcc_checking_assert (virtual_operand_p (val));
636 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
637 : }
638 : }
639 : }
640 : }
641 :
642 22634540 : if (dump_file && (dump_flags & TDF_DETAILS))
643 : {
644 147 : if (!replaced)
645 147 : fprintf (dump_file, "No folding possible\n");
646 : else
647 : {
648 0 : fprintf (dump_file, "Folded into: ");
649 0 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
650 0 : fprintf (dump_file, "\n");
651 : }
652 : }
653 :
654 22634540 : return replaced;
655 : }
656 :
657 :
658 : class substitute_and_fold_dom_walker : public dom_walker
659 : {
660 : public:
661 12159767 : substitute_and_fold_dom_walker (cdi_direction direction,
662 : class substitute_and_fold_engine *engine)
663 12159767 : : dom_walker (direction),
664 12159767 : something_changed (false),
665 12159767 : substitute_and_fold_engine (engine)
666 : {
667 12159767 : dceworklist = BITMAP_ALLOC (NULL);
668 12159767 : stmts_to_fixup.create (0);
669 12159767 : need_eh_cleanup = BITMAP_ALLOC (NULL);
670 12159767 : need_ab_cleanup = BITMAP_ALLOC (NULL);
671 12159767 : }
672 12159767 : ~substitute_and_fold_dom_walker ()
673 12159767 : {
674 12159767 : BITMAP_FREE (dceworklist);
675 12159767 : stmts_to_fixup.release ();
676 12159767 : BITMAP_FREE (need_eh_cleanup);
677 12159767 : BITMAP_FREE (need_ab_cleanup);
678 12159767 : }
679 :
680 : edge before_dom_children (basic_block) final override;
681 119000060 : void after_dom_children (basic_block bb) final override
682 : {
683 119000060 : substitute_and_fold_engine->post_fold_bb (bb);
684 119000060 : }
685 :
686 : bool something_changed;
687 : bitmap dceworklist;
688 : vec<gimple *> stmts_to_fixup;
689 : bitmap need_eh_cleanup;
690 : bitmap need_ab_cleanup;
691 :
692 : class substitute_and_fold_engine *substitute_and_fold_engine;
693 :
694 : private:
695 : void foreach_new_stmt_in_bb (gimple_stmt_iterator old_gsi,
696 : gimple_stmt_iterator new_gsi);
697 : };
698 :
699 : /* Call post_new_stmt for each new statement that has been added
700 : to the current BB. OLD_GSI is the statement iterator before the BB
701 : changes ocurred. NEW_GSI is the iterator which may contain new
702 : statements. */
703 :
704 : void
705 14337419 : substitute_and_fold_dom_walker::foreach_new_stmt_in_bb
706 : (gimple_stmt_iterator old_gsi,
707 : gimple_stmt_iterator new_gsi)
708 : {
709 14337419 : basic_block bb = gsi_bb (new_gsi);
710 14337419 : if (gsi_end_p (old_gsi))
711 3157102 : old_gsi = gsi_start_bb (bb);
712 : else
713 12758868 : gsi_next (&old_gsi);
714 14402545 : while (gsi_stmt (old_gsi) != gsi_stmt (new_gsi))
715 : {
716 65126 : gimple *stmt = gsi_stmt (old_gsi);
717 65126 : substitute_and_fold_engine->post_new_stmt (stmt);
718 65126 : gsi_next (&old_gsi);
719 : }
720 14337419 : }
721 :
722 : bool
723 119000060 : substitute_and_fold_engine::propagate_into_phi_args (basic_block bb)
724 : {
725 119000060 : edge e;
726 119000060 : edge_iterator ei;
727 119000060 : bool propagated = false;
728 :
729 : /* Visit BB successor PHI nodes and replace PHI args. */
730 280790880 : FOR_EACH_EDGE (e, ei, bb->succs)
731 : {
732 161790820 : for (gphi_iterator gpi = gsi_start_phis (e->dest);
733 268665846 : !gsi_end_p (gpi); gsi_next (&gpi))
734 : {
735 106875026 : gphi *phi = gpi.phi ();
736 106875026 : use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
737 106875026 : tree arg = USE_FROM_PTR (use_p);
738 172403102 : if (TREE_CODE (arg) != SSA_NAME
739 106875026 : || virtual_operand_p (arg))
740 65528076 : continue;
741 41346950 : tree val = value_on_edge (e, arg);
742 41346950 : if (val
743 2987379 : && is_gimple_min_invariant (val)
744 43189761 : && may_propagate_copy (arg, val))
745 : {
746 1840881 : propagate_value (use_p, val);
747 1840881 : propagated = true;
748 : }
749 : }
750 : }
751 119000060 : return propagated;
752 : }
753 :
754 : edge
755 119000060 : substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
756 : {
757 119000060 : substitute_and_fold_engine->pre_fold_bb (bb);
758 :
759 : /* Propagate known values into PHI nodes. */
760 119000060 : for (gphi_iterator i = gsi_start_phis (bb);
761 163202519 : !gsi_end_p (i);
762 44202459 : gsi_next (&i))
763 : {
764 44202459 : gphi *phi = i.phi ();
765 44202459 : tree res = gimple_phi_result (phi);
766 88404918 : if (virtual_operand_p (res))
767 19828991 : continue;
768 24373468 : if (dump_file && (dump_flags & TDF_DETAILS))
769 : {
770 151 : fprintf (dump_file, "Folding PHI node: ");
771 151 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
772 : }
773 24373468 : if (res && TREE_CODE (res) == SSA_NAME)
774 : {
775 24373468 : tree sprime = substitute_and_fold_engine->value_of_expr (res, phi);
776 26112396 : if (sprime
777 24373468 : && sprime != res
778 24373468 : && may_propagate_copy (res, sprime))
779 : {
780 1738928 : if (dump_file && (dump_flags & TDF_DETAILS))
781 : {
782 4 : fprintf (dump_file, "Queued PHI for removal. Folds to: ");
783 4 : print_generic_expr (dump_file, sprime);
784 4 : fprintf (dump_file, "\n");
785 : }
786 1738928 : bitmap_set_bit (dceworklist, SSA_NAME_VERSION (res));
787 : /* As this now constitutes a copy duplicate points-to
788 : and range info appropriately. */
789 1738928 : if (TREE_CODE (sprime) == SSA_NAME)
790 1119574 : maybe_duplicate_ssa_info_at_copy (res, sprime);
791 1738928 : continue;
792 : }
793 : }
794 22634540 : something_changed |= substitute_and_fold_engine->replace_phi_args_in (phi);
795 : }
796 :
797 : /* Propagate known values into stmts. In some case it exposes
798 : more trivially deletable stmts to walk backward. */
799 238000120 : for (gimple_stmt_iterator i = gsi_start_bb (bb);
800 937373539 : !gsi_end_p (i);
801 818373479 : gsi_next (&i))
802 : {
803 818373479 : bool did_replace;
804 818373479 : gimple *stmt = gsi_stmt (i);
805 :
806 818373479 : substitute_and_fold_engine->pre_fold_stmt (stmt);
807 :
808 818373479 : if (dump_file && (dump_flags & TDF_DETAILS))
809 : {
810 1779 : fprintf (dump_file, "Folding statement: ");
811 1779 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
812 : }
813 :
814 : /* No point propagating into a stmt we have a value for we
815 : can propagate into all uses. Mark it for removal instead. */
816 818373479 : tree lhs = gimple_get_lhs (stmt);
817 818373479 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
818 : {
819 178269472 : tree sprime = substitute_and_fold_engine->value_of_stmt (stmt, lhs);
820 192869408 : if (sprime
821 178269472 : && sprime != lhs
822 14618840 : && may_propagate_copy (lhs, sprime)
823 14617446 : && !stmt_could_throw_p (cfun, stmt)
824 192873648 : && !gimple_has_side_effects (stmt))
825 : {
826 14599936 : if (dump_file && (dump_flags & TDF_DETAILS))
827 : {
828 54 : fprintf (dump_file, "Queued stmt for removal. Folds to: ");
829 54 : print_generic_expr (dump_file, sprime);
830 54 : fprintf (dump_file, "\n");
831 : }
832 14599936 : bitmap_set_bit (dceworklist, SSA_NAME_VERSION (lhs));
833 : /* As this now constitutes a copy duplicate points-to
834 : and range info appropriately. */
835 14599936 : if (TREE_CODE (sprime) == SSA_NAME)
836 8658252 : maybe_duplicate_ssa_info_at_copy (lhs, sprime);
837 14599936 : continue;
838 : }
839 : }
840 :
841 : /* Replace the statement with its folded version and mark it
842 : folded. */
843 803773543 : did_replace = false;
844 803773543 : gimple *old_stmt = stmt;
845 803773543 : bool was_noreturn = false;
846 803773543 : bool can_make_abnormal_goto = false;
847 803773543 : if (is_gimple_call (stmt))
848 : {
849 53115202 : was_noreturn = gimple_call_noreturn_p (stmt);
850 53115202 : can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
851 : }
852 :
853 : /* Replace real uses in the statement. */
854 803773543 : did_replace |= substitute_and_fold_engine->replace_uses_in (stmt);
855 :
856 803773543 : gimple_stmt_iterator prev_gsi = i;
857 803773543 : gsi_prev (&prev_gsi);
858 :
859 : /* If we made a replacement, fold the statement. */
860 803773543 : if (did_replace)
861 : {
862 12994579 : update_stmt (stmt);
863 12994579 : fold_stmt (&i, follow_single_use_edges);
864 12994579 : stmt = gsi_stmt (i);
865 12994579 : gimple_set_modified (stmt, true);
866 : }
867 : /* Also fold if we want to fold all statements. */
868 790778964 : else if (substitute_and_fold_engine->fold_all_stmts
869 790778964 : && fold_stmt (&i, follow_single_use_edges))
870 : {
871 0 : did_replace = true;
872 0 : stmt = gsi_stmt (i);
873 0 : gimple_set_modified (stmt, true);
874 : }
875 :
876 : /* Some statements may be simplified using propagator
877 : specific information. Do this before propagating
878 : into the stmt to not disturb pass specific information. */
879 803773543 : update_stmt_if_modified (stmt);
880 803773543 : if (substitute_and_fold_engine->fold_stmt (&i))
881 : {
882 1772844 : did_replace = true;
883 1772844 : prop_stats.num_stmts_folded++;
884 1772844 : stmt = gsi_stmt (i);
885 1772844 : gimple_set_modified (stmt, true);
886 : }
887 :
888 : /* If this is a control statement the propagator left edges
889 : unexecuted on force the condition in a way consistent with
890 : that. See PR66945 for cases where the propagator can end
891 : up with a different idea of a taken edge than folding
892 : (once undefined behavior is involved). */
893 803773543 : if (gimple_code (stmt) == GIMPLE_COND)
894 : {
895 42471120 : if ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE)
896 42471120 : ^ (EDGE_SUCC (bb, 1)->flags & EDGE_EXECUTABLE))
897 : {
898 449239 : if (((EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) != 0)
899 449239 : == ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE) != 0))
900 101851 : gimple_cond_make_true (as_a <gcond *> (stmt));
901 : else
902 347388 : gimple_cond_make_false (as_a <gcond *> (stmt));
903 449239 : gimple_set_modified (stmt, true);
904 449239 : did_replace = true;
905 : }
906 : }
907 :
908 : /* Now cleanup. */
909 803773543 : if (did_replace)
910 : {
911 14337419 : foreach_new_stmt_in_bb (prev_gsi, i);
912 :
913 : /* If we cleaned up EH information from the statement,
914 : remove EH edges. */
915 14337419 : if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
916 155807 : bitmap_set_bit (need_eh_cleanup, bb->index);
917 :
918 : /* If we turned a call with possible abnormal control transfer
919 : into one that doesn't, remove abnormal edges. */
920 14337419 : if (can_make_abnormal_goto
921 14337419 : && !stmt_can_make_abnormal_goto (stmt))
922 3 : bitmap_set_bit (need_ab_cleanup, bb->index);
923 :
924 : /* If we turned a not noreturn call into a noreturn one
925 : schedule it for fixup. */
926 14337419 : if (!was_noreturn
927 14207202 : && is_gimple_call (stmt)
928 15745885 : && gimple_call_noreturn_p (stmt))
929 70 : stmts_to_fixup.safe_push (stmt);
930 :
931 14337419 : if (gimple_assign_single_p (stmt))
932 : {
933 3428264 : tree rhs = gimple_assign_rhs1 (stmt);
934 :
935 3428264 : if (TREE_CODE (rhs) == ADDR_EXPR)
936 375505 : recompute_tree_invariant_for_addr_expr (rhs);
937 : }
938 :
939 : /* Determine what needs to be done to update the SSA form. */
940 14337419 : update_stmt_if_modified (stmt);
941 14337419 : if (!is_gimple_debug (stmt))
942 10474655 : something_changed = true;
943 : }
944 :
945 803773543 : if (dump_file && (dump_flags & TDF_DETAILS))
946 : {
947 1725 : if (did_replace)
948 : {
949 141 : fprintf (dump_file, "Folded into: ");
950 141 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
951 141 : fprintf (dump_file, "\n");
952 : }
953 : else
954 1584 : fprintf (dump_file, "Not folded\n");
955 : }
956 : }
957 :
958 119000060 : something_changed |= substitute_and_fold_engine->propagate_into_phi_args (bb);
959 :
960 119000060 : return NULL;
961 : }
962 :
963 :
964 :
965 : /* Perform final substitution and folding of propagated values.
966 : Process the whole function if BLOCK is null, otherwise only
967 : process the blocks that BLOCK dominates. In the latter case,
968 : it is the caller's responsibility to ensure that dominator
969 : information is available and up-to-date.
970 :
971 : PROP_VALUE[I] contains the single value that should be substituted
972 : at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
973 : substituted.
974 :
975 : If FOLD_FN is non-NULL the function will be invoked on all statements
976 : before propagating values for pass specific simplification.
977 :
978 : DO_DCE is true if trivially dead stmts can be removed.
979 :
980 : If DO_DCE is true, the statements within a BB are walked from
981 : last to first element. Otherwise we scan from first to last element.
982 :
983 : Return TRUE when something changed. */
984 :
985 : bool
986 12159767 : substitute_and_fold_engine::substitute_and_fold (basic_block block)
987 : {
988 12159767 : if (dump_file && (dump_flags & TDF_DETAILS))
989 158 : fprintf (dump_file, "\nSubstituting values and folding statements\n\n");
990 :
991 12159767 : memset (&prop_stats, 0, sizeof (prop_stats));
992 :
993 : /* Don't call calculate_dominance_info when iterating over a subgraph.
994 : Callers that are using the interface this way are likely to want to
995 : iterate over several disjoint subgraphs, and it would be expensive
996 : in enable-checking builds to revalidate the whole dominance tree
997 : each time. */
998 12159767 : if (block)
999 1345 : gcc_assert (dom_info_state (CDI_DOMINATORS));
1000 : else
1001 12158422 : calculate_dominance_info (CDI_DOMINATORS);
1002 12159767 : substitute_and_fold_dom_walker walker (CDI_DOMINATORS, this);
1003 12159767 : walker.walk (block ? block : ENTRY_BLOCK_PTR_FOR_FN (cfun));
1004 :
1005 12159767 : simple_dce_from_worklist (walker.dceworklist, walker.need_eh_cleanup);
1006 12159767 : if (!bitmap_empty_p (walker.need_eh_cleanup))
1007 36773 : gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup);
1008 12159767 : if (!bitmap_empty_p (walker.need_ab_cleanup))
1009 3 : gimple_purge_all_dead_abnormal_call_edges (walker.need_ab_cleanup);
1010 :
1011 : /* Fixup stmts that became noreturn calls. This may require splitting
1012 : blocks and thus isn't possible during the dominator walk. Do this
1013 : in reverse order so we don't inadvertedly remove a stmt we want to
1014 : fixup by visiting a dominating now noreturn call first. */
1015 12159837 : while (!walker.stmts_to_fixup.is_empty ())
1016 : {
1017 70 : gimple *stmt = walker.stmts_to_fixup.pop ();
1018 76 : if (!gimple_bb (stmt))
1019 6 : continue;
1020 64 : if (dump_file && dump_flags & TDF_DETAILS)
1021 : {
1022 0 : fprintf (dump_file, "Fixing up noreturn call ");
1023 0 : print_gimple_stmt (dump_file, stmt, 0);
1024 0 : fprintf (dump_file, "\n");
1025 : }
1026 64 : fixup_noreturn_call (stmt);
1027 : }
1028 :
1029 12159767 : statistics_counter_event (cfun, "Constants propagated",
1030 12159767 : prop_stats.num_const_prop);
1031 12159767 : statistics_counter_event (cfun, "Copies propagated",
1032 12159767 : prop_stats.num_copy_prop);
1033 12159767 : statistics_counter_event (cfun, "Statements folded",
1034 12159767 : prop_stats.num_stmts_folded);
1035 :
1036 12159767 : return walker.something_changed;
1037 12159767 : }
1038 :
1039 :
1040 : /* Return true if we may propagate ORIG into DEST, false otherwise.
1041 : If DEST_NOT_ABNORMAL_PHI_EDGE_P is true then assume the propagation does
1042 : not happen into a PHI argument which flows in from an abnormal edge
1043 : which relaxes some constraints. */
1044 :
1045 : bool
1046 149226080 : may_propagate_copy (tree dest, tree orig, bool dest_not_abnormal_phi_edge_p)
1047 : {
1048 149226080 : tree type_d = TREE_TYPE (dest);
1049 149226080 : tree type_o = TREE_TYPE (orig);
1050 :
1051 : /* If ORIG is a default definition which flows in from an abnormal edge
1052 : then the copy can be propagated. It is important that we do so to avoid
1053 : uninitialized copies. */
1054 149226080 : if (TREE_CODE (orig) == SSA_NAME
1055 103627589 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)
1056 29329 : && SSA_NAME_IS_DEFAULT_DEF (orig)
1057 149229321 : && (SSA_NAME_VAR (orig) == NULL_TREE
1058 3241 : || VAR_P (SSA_NAME_VAR (orig))))
1059 : ;
1060 : /* Otherwise if ORIG just flows in from an abnormal edge then the copy cannot
1061 : be propagated. */
1062 149223242 : else if (TREE_CODE (orig) == SSA_NAME
1063 149223242 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
1064 : return false;
1065 : /* Similarly if DEST flows in from an abnormal edge then the copy cannot be
1066 : propagated. If we know we do not propagate into such a PHI argument this
1067 : does not apply. */
1068 149196751 : else if (!dest_not_abnormal_phi_edge_p
1069 76543593 : && TREE_CODE (dest) == SSA_NAME
1070 225740344 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
1071 : return false;
1072 :
1073 : /* Do not copy between types for which we *do* need a conversion. */
1074 149183895 : if (!useless_type_conversion_p (type_d, type_o))
1075 : return false;
1076 :
1077 : /* Generally propagating virtual operands is not ok as that may
1078 : create overlapping life-ranges. */
1079 149169199 : if (TREE_CODE (dest) == SSA_NAME && virtual_operand_p (dest))
1080 : return false;
1081 :
1082 : /* Keep lhs of [[gnu::musttail]] calls as is, those need to be still
1083 : tail callable. */
1084 148731716 : if (TREE_CODE (dest) == SSA_NAME
1085 148559603 : && is_gimple_call (SSA_NAME_DEF_STMT (dest))
1086 150055369 : && gimple_call_must_tail_p (as_a <gcall *> (SSA_NAME_DEF_STMT (dest))))
1087 : return false;
1088 :
1089 : /* Anything else is OK. */
1090 : return true;
1091 : }
1092 :
1093 : /* Like may_propagate_copy, but use as the destination expression
1094 : the principal expression (typically, the RHS) contained in
1095 : statement DEST. This is more efficient when working with the
1096 : gimple tuples representation. */
1097 :
1098 : bool
1099 388992 : may_propagate_copy_into_stmt (gimple *dest, tree orig)
1100 : {
1101 388992 : tree type_d;
1102 388992 : tree type_o;
1103 :
1104 : /* If the statement is a switch or a single-rhs assignment,
1105 : then the expression to be replaced by the propagation may
1106 : be an SSA_NAME. Fortunately, there is an explicit tree
1107 : for the expression, so we delegate to may_propagate_copy. */
1108 :
1109 388992 : if (gimple_assign_single_p (dest))
1110 185385 : return may_propagate_copy (gimple_assign_rhs1 (dest), orig, true);
1111 203607 : else if (gswitch *dest_swtch = dyn_cast <gswitch *> (dest))
1112 0 : return may_propagate_copy (gimple_switch_index (dest_swtch), orig, true);
1113 :
1114 : /* In other cases, the expression is not materialized, so there
1115 : is no destination to pass to may_propagate_copy. On the other
1116 : hand, the expression cannot be an SSA_NAME, so the analysis
1117 : is much simpler. */
1118 :
1119 203607 : if (TREE_CODE (orig) == SSA_NAME
1120 203607 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
1121 : return false;
1122 :
1123 203607 : if (is_gimple_assign (dest))
1124 172240 : type_d = TREE_TYPE (gimple_assign_lhs (dest));
1125 31367 : else if (gimple_code (dest) == GIMPLE_COND)
1126 26111 : type_d = boolean_type_node;
1127 5256 : else if (is_gimple_call (dest)
1128 5256 : && gimple_call_lhs (dest) != NULL_TREE)
1129 5256 : type_d = TREE_TYPE (gimple_call_lhs (dest));
1130 : else
1131 0 : gcc_unreachable ();
1132 :
1133 203607 : type_o = TREE_TYPE (orig);
1134 :
1135 203607 : if (!useless_type_conversion_p (type_d, type_o))
1136 : return false;
1137 :
1138 : return true;
1139 : }
1140 :
1141 : /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
1142 :
1143 : Use this version when not const/copy propagating values. For example,
1144 : PRE uses this version when building expressions as they would appear
1145 : in specific blocks taking into account actions of PHI nodes.
1146 :
1147 : The statement in which an expression has been replaced should be
1148 : folded using fold_stmt_inplace. */
1149 :
1150 : void
1151 53953959 : replace_exp (use_operand_p op_p, tree val)
1152 : {
1153 53953959 : if (TREE_CODE (val) == SSA_NAME || CONSTANT_CLASS_P (val))
1154 50138916 : SET_USE (op_p, val);
1155 : else
1156 3815043 : SET_USE (op_p, unshare_expr (val));
1157 53953959 : }
1158 :
1159 :
1160 : /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1161 : into the operand pointed to by OP_P.
1162 :
1163 : Use this version for const/copy propagation as it will perform additional
1164 : checks to ensure validity of the const/copy propagation. */
1165 :
1166 : void
1167 47797249 : propagate_value (use_operand_p op_p, tree val)
1168 : {
1169 47797249 : if (flag_checking)
1170 : {
1171 47796789 : bool ab = (is_a <gphi *> (USE_STMT (op_p))
1172 63684475 : && (gimple_phi_arg_edge (as_a <gphi *> (USE_STMT (op_p)),
1173 15887686 : PHI_ARG_INDEX_FROM_USE (op_p))
1174 15887686 : ->flags & EDGE_ABNORMAL));
1175 47796789 : gcc_assert (may_propagate_copy (USE_FROM_PTR (op_p), val, !ab));
1176 : }
1177 47797249 : replace_exp (op_p, val);
1178 47797249 : }
1179 :
1180 :
1181 : /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1182 : into the tree pointed to by OP_P.
1183 :
1184 : Use this version for const/copy propagation when SSA operands are not
1185 : available. It will perform the additional checks to ensure validity of
1186 : the const/copy propagation, but will not update any operand information.
1187 : Be sure to mark the stmt as modified. */
1188 :
1189 : void
1190 416664 : propagate_tree_value (tree *op_p, tree val)
1191 : {
1192 416664 : if (TREE_CODE (val) == SSA_NAME)
1193 375721 : *op_p = val;
1194 : else
1195 40943 : *op_p = unshare_expr (val);
1196 416664 : }
1197 :
1198 :
1199 : /* Like propagate_tree_value, but use as the operand to replace
1200 : the principal expression (typically, the RHS) contained in the
1201 : statement referenced by iterator GSI. Note that it is not
1202 : always possible to update the statement in-place, so a new
1203 : statement may be created to replace the original. */
1204 :
1205 : void
1206 416664 : propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
1207 : {
1208 416664 : gimple *stmt = gsi_stmt (*gsi);
1209 :
1210 416664 : if (is_gimple_assign (stmt))
1211 : {
1212 379811 : tree expr = NULL_TREE;
1213 379811 : if (gimple_assign_single_p (stmt))
1214 203604 : expr = gimple_assign_rhs1 (stmt);
1215 379811 : propagate_tree_value (&expr, val);
1216 379811 : gimple_assign_set_rhs_from_tree (gsi, expr);
1217 : }
1218 36853 : else if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1219 : {
1220 29489 : tree lhs = NULL_TREE;
1221 29489 : tree rhs = build_zero_cst (TREE_TYPE (val));
1222 29489 : propagate_tree_value (&lhs, val);
1223 29489 : gimple_cond_set_code (cond_stmt, NE_EXPR);
1224 29489 : gimple_cond_set_lhs (cond_stmt, lhs);
1225 29489 : gimple_cond_set_rhs (cond_stmt, rhs);
1226 : }
1227 7364 : else if (is_gimple_call (stmt)
1228 7364 : && gimple_call_lhs (stmt) != NULL_TREE)
1229 : {
1230 7364 : tree expr = NULL_TREE;
1231 7364 : propagate_tree_value (&expr, val);
1232 7364 : replace_call_with_value (gsi, expr);
1233 : }
1234 0 : else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1235 0 : propagate_tree_value (gimple_switch_index_ptr (swtch_stmt), val);
1236 : else
1237 0 : gcc_unreachable ();
1238 416664 : }
1239 :
1240 : /* Check exits of each loop in FUN, walk over loop closed PHIs in
1241 : each exit basic block and propagate degenerate PHIs. */
1242 :
1243 : unsigned
1244 241709 : clean_up_loop_closed_phi (function *fun)
1245 : {
1246 241709 : gphi *phi;
1247 241709 : tree rhs;
1248 241709 : tree lhs;
1249 241709 : gphi_iterator gsi;
1250 :
1251 : /* Avoid possibly quadratic work when scanning for loop exits across
1252 : all loops of a nest. */
1253 241709 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1254 : return 0;
1255 :
1256 : /* replace_uses_by might purge dead EH edges and we want it to also
1257 : remove dominated blocks. */
1258 241709 : calculate_dominance_info (CDI_DOMINATORS);
1259 :
1260 : /* Walk over loop in function. */
1261 1353278 : for (auto loop : loops_list (fun, 0))
1262 : {
1263 : /* Check each exit edege of loop. */
1264 628151 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1265 3023015 : for (edge e : exits)
1266 1918597 : if (single_pred_p (e->dest))
1267 : /* Walk over loop-closed PHIs. */
1268 1672367 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);)
1269 : {
1270 905020 : phi = gsi.phi ();
1271 905020 : rhs = gimple_phi_arg_def (phi, 0);
1272 905020 : lhs = gimple_phi_result (phi);
1273 :
1274 1809170 : if (virtual_operand_p (rhs))
1275 : {
1276 480765 : imm_use_iterator iter;
1277 480765 : use_operand_p use_p;
1278 480765 : gimple *stmt;
1279 :
1280 1646713 : FOR_EACH_IMM_USE_STMT (stmt, iter, lhs)
1281 2069273 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1282 692045 : SET_USE (use_p, rhs);
1283 :
1284 480765 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1285 48 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
1286 480765 : remove_phi_node (&gsi, true);
1287 : }
1288 424255 : else if (may_propagate_copy (lhs, rhs))
1289 : {
1290 : /* Dump details. */
1291 424214 : if (dump_file && (dump_flags & TDF_DETAILS))
1292 : {
1293 3 : fprintf (dump_file, " Replacing '");
1294 3 : print_generic_expr (dump_file, lhs, dump_flags);
1295 3 : fprintf (dump_file, "' with '");
1296 3 : print_generic_expr (dump_file, rhs, dump_flags);
1297 3 : fprintf (dump_file, "'\n");
1298 : }
1299 :
1300 424214 : replace_uses_by (lhs, rhs);
1301 424214 : remove_phi_node (&gsi, true);
1302 : }
1303 : else
1304 41 : gsi_next (&gsi);
1305 : }
1306 628151 : }
1307 :
1308 241709 : return 0;
1309 : }
|
