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 : /* We have just defined a new value for VAR. If IS_VARYING is true,
128 : add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
129 : them to INTERESTING_SSA_EDGES. */
130 :
131 : static void
132 288917245 : add_ssa_edge (tree var)
133 : {
134 288917245 : imm_use_iterator iter;
135 288917245 : use_operand_p use_p;
136 :
137 888822214 : FOR_EACH_IMM_USE_FAST (use_p, iter, var)
138 : {
139 599904969 : gimple *use_stmt = USE_STMT (use_p);
140 599904969 : if (!prop_simulate_again_p (use_stmt))
141 254105186 : continue;
142 :
143 : /* If we did not yet simulate the block wait for this to happen
144 : and do not add the stmt to the SSA edge worklist. */
145 345799783 : basic_block use_bb = gimple_bb (use_stmt);
146 345799783 : if (! (use_bb->flags & BB_VISITED))
147 141183280 : continue;
148 :
149 : /* If this is a use on a not yet executable edge do not bother to
150 : queue it. */
151 204616503 : if (gimple_code (use_stmt) == GIMPLE_PHI
152 204616503 : && !(EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->flags
153 67255091 : & EDGE_EXECUTABLE))
154 6426545 : continue;
155 :
156 198189958 : if (bitmap_set_bit (ssa_edge_worklist, gimple_uid (use_stmt)))
157 : {
158 182450754 : uid_to_stmt[gimple_uid (use_stmt)] = use_stmt;
159 182450754 : if (dump_file && (dump_flags & TDF_DETAILS))
160 : {
161 0 : fprintf (dump_file, "ssa_edge_worklist: adding SSA use in ");
162 0 : print_gimple_stmt (dump_file, use_stmt, 0, TDF_SLIM);
163 : }
164 : }
165 288917245 : }
166 288917245 : }
167 :
168 :
169 : /* Add edge E to the control flow worklist. */
170 :
171 : static void
172 139803534 : add_control_edge (edge e)
173 : {
174 139803534 : basic_block bb = e->dest;
175 139803534 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
176 : return;
177 :
178 : /* If the edge had already been executed, skip it. */
179 123918708 : if (e->flags & EDGE_EXECUTABLE)
180 : return;
181 :
182 107343044 : e->flags |= EDGE_EXECUTABLE;
183 :
184 107343044 : int bb_order = bb_to_cfg_order[bb->index];
185 107343044 : bitmap_set_bit (cfg_blocks, bb_order);
186 :
187 107343044 : if (dump_file && (dump_flags & TDF_DETAILS))
188 61 : fprintf (dump_file, "Adding destination of edge (%d -> %d) to worklist\n",
189 61 : e->src->index, e->dest->index);
190 : }
191 :
192 :
193 : /* Simulate the execution of STMT and update the work lists accordingly. */
194 :
195 : void
196 838392098 : ssa_propagation_engine::simulate_stmt (gimple *stmt)
197 : {
198 838392098 : enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
199 838392098 : edge taken_edge = NULL;
200 838392098 : tree output_name = NULL_TREE;
201 :
202 : /* Pull the stmt off the SSA edge worklist. */
203 838392098 : bitmap_clear_bit (ssa_edge_worklist, gimple_uid (stmt));
204 :
205 : /* Don't bother visiting statements that are already
206 : considered varying by the propagator. */
207 838392098 : if (!prop_simulate_again_p (stmt))
208 599625741 : return;
209 :
210 362990921 : if (gimple_code (stmt) == GIMPLE_PHI)
211 : {
212 80849278 : val = visit_phi (as_a <gphi *> (stmt));
213 80849278 : output_name = gimple_phi_result (stmt);
214 : }
215 : else
216 282141643 : val = visit_stmt (stmt, &taken_edge, &output_name);
217 :
218 362990921 : if (val == SSA_PROP_VARYING)
219 : {
220 124224564 : prop_set_simulate_again (stmt, false);
221 :
222 : /* If the statement produced a new varying value, add the SSA
223 : edges coming out of OUTPUT_NAME. */
224 124224564 : if (output_name)
225 74426783 : add_ssa_edge (output_name);
226 :
227 : /* If STMT transfers control out of its basic block, add
228 : all outgoing edges to the work list. */
229 124224564 : if (stmt_ends_bb_p (stmt))
230 : {
231 51234368 : edge e;
232 51234368 : edge_iterator ei;
233 51234368 : basic_block bb = gimple_bb (stmt);
234 131930055 : FOR_EACH_EDGE (e, ei, bb->succs)
235 80695687 : add_control_edge (e);
236 : }
237 : return;
238 : }
239 238766357 : else if (val == SSA_PROP_INTERESTING)
240 : {
241 : /* If the statement produced new value, add the SSA edges coming
242 : out of OUTPUT_NAME. */
243 221152145 : if (output_name)
244 214490462 : add_ssa_edge (output_name);
245 :
246 : /* If we know which edge is going to be taken out of this block,
247 : add it to the CFG work list. */
248 221152145 : if (taken_edge)
249 6661683 : add_control_edge (taken_edge);
250 : }
251 :
252 : /* If there are no SSA uses on the stmt whose defs are simulated
253 : again then this stmt will be never visited again. */
254 238766357 : bool has_simulate_again_uses = false;
255 238766357 : use_operand_p use_p;
256 238766357 : ssa_op_iter iter;
257 238766357 : if (gimple_code (stmt) == GIMPLE_PHI)
258 : {
259 67485220 : edge_iterator ei;
260 67485220 : edge e;
261 67485220 : tree arg;
262 104952227 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
263 103002887 : if (!(e->flags & EDGE_EXECUTABLE)
264 103002887 : || ((arg = PHI_ARG_DEF_FROM_EDGE (stmt, e))
265 94490928 : && TREE_CODE (arg) == SSA_NAME
266 77716827 : && !SSA_NAME_IS_DEFAULT_DEF (arg)
267 77506443 : && prop_simulate_again_p (SSA_NAME_DEF_STMT (arg))))
268 : {
269 : has_simulate_again_uses = true;
270 : break;
271 : }
272 : }
273 : else
274 210441741 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
275 : {
276 169842417 : gimple *def_stmt = SSA_NAME_DEF_STMT (USE_FROM_PTR (use_p));
277 169842417 : if (!gimple_nop_p (def_stmt)
278 169842417 : && prop_simulate_again_p (def_stmt))
279 : {
280 : has_simulate_again_uses = true;
281 : break;
282 : }
283 : }
284 238766357 : if (!has_simulate_again_uses)
285 : {
286 42548664 : if (dump_file && (dump_flags & TDF_DETAILS))
287 40 : fprintf (dump_file, "marking stmt to be not simulated again\n");
288 42548664 : prop_set_simulate_again (stmt, false);
289 : }
290 : }
291 :
292 :
293 : /* Simulate the execution of BLOCK. Evaluate the statement associated
294 : with each variable reference inside the block. */
295 :
296 : void
297 81988026 : ssa_propagation_engine::simulate_block (basic_block block)
298 : {
299 81988026 : gimple_stmt_iterator gsi;
300 :
301 : /* There is nothing to do for the exit block. */
302 81988026 : if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
303 81988026 : return;
304 :
305 81988026 : if (dump_file && (dump_flags & TDF_DETAILS))
306 57 : fprintf (dump_file, "\nSimulating block %d\n", block->index);
307 :
308 : /* Always simulate PHI nodes, even if we have simulated this block
309 : before. */
310 124363883 : for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
311 42375857 : simulate_stmt (gsi_stmt (gsi));
312 :
313 : /* If this is the first time we've simulated this block, then we
314 : must simulate each of its statements. */
315 81988026 : if (! (block->flags & BB_VISITED))
316 : {
317 76712007 : gimple_stmt_iterator j;
318 76712007 : unsigned int normal_edge_count;
319 76712007 : edge e, normal_edge;
320 76712007 : edge_iterator ei;
321 :
322 767103575 : for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
323 613679561 : simulate_stmt (gsi_stmt (j));
324 :
325 : /* Note that we have simulated this block. */
326 76712007 : block->flags |= BB_VISITED;
327 :
328 : /* We cannot predict when abnormal and EH edges will be executed, so
329 : once a block is considered executable, we consider any
330 : outgoing abnormal edges as executable.
331 :
332 : TODO: This is not exactly true. Simplifying statement might
333 : prove it non-throwing and also computed goto can be handled
334 : when destination is known.
335 :
336 : At the same time, if this block has only one successor that is
337 : reached by non-abnormal edges, then add that successor to the
338 : worklist. */
339 76712007 : normal_edge_count = 0;
340 76712007 : normal_edge = NULL;
341 184374203 : FOR_EACH_EDGE (e, ei, block->succs)
342 : {
343 107662196 : if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
344 6890765 : add_control_edge (e);
345 : else
346 : {
347 100771431 : normal_edge_count++;
348 100771431 : normal_edge = e;
349 : }
350 : }
351 :
352 76712007 : if (normal_edge_count == 1)
353 37443915 : add_control_edge (normal_edge);
354 : }
355 : }
356 :
357 :
358 : /* Initialize local data structures and work lists. */
359 :
360 : static void
361 8111484 : ssa_prop_init (void)
362 : {
363 8111484 : edge e;
364 8111484 : edge_iterator ei;
365 8111484 : basic_block bb;
366 :
367 : /* Worklists of SSA edges. */
368 8111484 : ssa_edge_worklist = BITMAP_ALLOC (NULL);
369 8111484 : bitmap_tree_view (ssa_edge_worklist);
370 :
371 : /* Worklist of basic-blocks. */
372 8111484 : bb_to_cfg_order = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
373 8111484 : cfg_order_to_bb = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
374 8111484 : int n = pre_and_rev_post_order_compute_fn (cfun, NULL,
375 : cfg_order_to_bb, false);
376 93503073 : for (int i = 0; i < n; ++i)
377 77280105 : bb_to_cfg_order[cfg_order_to_bb[i]] = i;
378 8111484 : cfg_blocks = BITMAP_ALLOC (NULL);
379 :
380 : /* Initially assume that every edge in the CFG is not executable.
381 : (including the edges coming out of the entry block). Mark blocks
382 : as not visited, blocks not yet visited will have all their statements
383 : simulated once an incoming edge gets executable. */
384 8111484 : set_gimple_stmt_max_uid (cfun, 0);
385 85391589 : for (int i = 0; i < n; ++i)
386 : {
387 77280105 : gimple_stmt_iterator si;
388 77280105 : bb = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb[i]);
389 :
390 108234443 : for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
391 : {
392 30954338 : gimple *stmt = gsi_stmt (si);
393 30954338 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
394 : }
395 :
396 770674420 : for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
397 : {
398 616114210 : gimple *stmt = gsi_stmt (si);
399 616114210 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
400 : }
401 :
402 77280105 : bb->flags &= ~BB_VISITED;
403 185460843 : FOR_EACH_EDGE (e, ei, bb->succs)
404 108180738 : e->flags &= ~EDGE_EXECUTABLE;
405 : }
406 8111484 : uid_to_stmt.safe_grow (gimple_stmt_max_uid (cfun), true);
407 8111484 : }
408 :
409 :
410 : /* Free allocated storage. */
411 :
412 : static void
413 8111484 : ssa_prop_fini (void)
414 : {
415 8111484 : BITMAP_FREE (cfg_blocks);
416 8111484 : free (bb_to_cfg_order);
417 8111484 : free (cfg_order_to_bb);
418 8111484 : BITMAP_FREE (ssa_edge_worklist);
419 8111484 : uid_to_stmt.release ();
420 8111484 : }
421 :
422 :
423 : /* Entry point to the propagation engine.
424 :
425 : The VISIT_STMT virtual function is called for every statement
426 : visited and the VISIT_PHI virtual function is called for every PHI
427 : node visited. */
428 :
429 : void
430 8111484 : ssa_propagation_engine::ssa_propagate (void)
431 : {
432 8111484 : ssa_prop_init ();
433 :
434 : /* Iterate until the worklists are empty. We iterate both blocks
435 : and stmts in RPO order, prioritizing backedge processing.
436 : Seed the algorithm by adding the successors of the entry block to the
437 : edge worklist. */
438 8111484 : edge e;
439 8111484 : edge_iterator ei;
440 16222968 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
441 : {
442 8111484 : e->flags &= ~EDGE_EXECUTABLE;
443 8111484 : add_control_edge (e);
444 : }
445 272436190 : while (1)
446 : {
447 272436190 : int next_block_order = (bitmap_empty_p (cfg_blocks)
448 272436190 : ? -1 : bitmap_first_set_bit (cfg_blocks));
449 272436190 : int next_stmt_uid = (bitmap_empty_p (ssa_edge_worklist)
450 272436190 : ? -1 : bitmap_first_set_bit (ssa_edge_worklist));
451 272436190 : if (next_block_order == -1 && next_stmt_uid == -1)
452 : break;
453 :
454 264324706 : int next_stmt_bb_order = -1;
455 264324706 : gimple *next_stmt = NULL;
456 264324706 : if (next_stmt_uid != -1)
457 : {
458 186083435 : next_stmt = uid_to_stmt[next_stmt_uid];
459 186083435 : next_stmt_bb_order = bb_to_cfg_order[gimple_bb (next_stmt)->index];
460 : }
461 :
462 : /* Pull the next block to simulate off the worklist if it comes first. */
463 264324706 : if (next_block_order != -1
464 230204766 : && (next_stmt_bb_order == -1
465 230204766 : || next_block_order <= next_stmt_bb_order))
466 : {
467 81988026 : bitmap_clear_bit (cfg_blocks, next_block_order);
468 81988026 : basic_block bb
469 81988026 : = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb [next_block_order]);
470 81988026 : simulate_block (bb);
471 81988026 : }
472 : /* Else simulate from the SSA edge worklist. */
473 : else
474 : {
475 182336680 : if (dump_file && (dump_flags & TDF_DETAILS))
476 : {
477 0 : fprintf (dump_file, "\nSimulating statement: ");
478 0 : print_gimple_stmt (dump_file, next_stmt, 0, dump_flags);
479 : }
480 182336680 : simulate_stmt (next_stmt);
481 : }
482 : }
483 :
484 8111484 : ssa_prop_fini ();
485 8111484 : }
486 :
487 : /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
488 : is a non-volatile pointer dereference, a structure reference or a
489 : reference to a single _DECL. Ignore volatile memory references
490 : because they are not interesting for the optimizers. */
491 :
492 : bool
493 33286058 : stmt_makes_single_store (gimple *stmt)
494 : {
495 33286058 : tree lhs;
496 :
497 33286058 : if (gimple_code (stmt) != GIMPLE_ASSIGN
498 33286058 : && gimple_code (stmt) != GIMPLE_CALL)
499 : return false;
500 :
501 33301194 : if (!gimple_vdef (stmt))
502 : return false;
503 :
504 2573084 : lhs = gimple_get_lhs (stmt);
505 :
506 : /* A call statement may have a null LHS. */
507 2573084 : if (!lhs)
508 : return false;
509 :
510 2573084 : return (!TREE_THIS_VOLATILE (lhs)
511 2573084 : && (DECL_P (lhs)
512 2557948 : || REFERENCE_CLASS_P (lhs)));
513 : }
514 :
515 :
516 : /* Propagation statistics. */
517 : struct prop_stats_d
518 : {
519 : long num_const_prop;
520 : long num_copy_prop;
521 : long num_stmts_folded;
522 : };
523 :
524 : static struct prop_stats_d prop_stats;
525 :
526 : // range_query default methods to drive from a value_of_expr() ranther than
527 : // range_of_expr.
528 :
529 : tree
530 57598468 : substitute_and_fold_engine::value_on_edge (edge, tree expr)
531 : {
532 57598468 : return value_of_expr (expr);
533 : }
534 :
535 : tree
536 135267248 : substitute_and_fold_engine::value_of_stmt (gimple *stmt, tree name)
537 : {
538 135267248 : if (!name)
539 0 : name = gimple_get_lhs (stmt);
540 :
541 135267248 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
542 :
543 135267248 : if (name)
544 135267248 : return value_of_expr (name);
545 : return NULL_TREE;
546 : }
547 :
548 : bool
549 505856 : substitute_and_fold_engine::range_of_expr (vrange &, tree, gimple *)
550 : {
551 505856 : return false;
552 : }
553 :
554 : /* Replace USE references in statement STMT with the values stored in
555 : PROP_VALUE. Return true if at least one reference was replaced. */
556 :
557 : bool
558 859057723 : substitute_and_fold_engine::replace_uses_in (gimple *stmt)
559 : {
560 859057723 : bool replaced = false;
561 859057723 : use_operand_p use;
562 859057723 : ssa_op_iter iter;
563 :
564 1251472501 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
565 : {
566 392414778 : tree tuse = USE_FROM_PTR (use);
567 392414778 : tree val = value_of_expr (tuse, stmt);
568 :
569 392414778 : if (val == tuse || val == NULL_TREE)
570 378019466 : continue;
571 :
572 14395312 : if (!may_propagate_copy (tuse, val))
573 645 : continue;
574 :
575 14394667 : if (TREE_CODE (val) != SSA_NAME)
576 5668495 : prop_stats.num_const_prop++;
577 : else
578 8726172 : prop_stats.num_copy_prop++;
579 :
580 14394667 : propagate_value (use, val);
581 :
582 14394667 : replaced = true;
583 : }
584 :
585 859057723 : return replaced;
586 : }
587 :
588 :
589 : /* Replace propagated values into all the arguments for PHI using the
590 : values from PROP_VALUE. */
591 :
592 : bool
593 23396389 : substitute_and_fold_engine::replace_phi_args_in (gphi *phi)
594 : {
595 23396389 : size_t i;
596 23396389 : bool replaced = false;
597 :
598 79359786 : for (i = 0; i < gimple_phi_num_args (phi); i++)
599 : {
600 55963397 : tree arg = gimple_phi_arg_def (phi, i);
601 :
602 55963397 : if (TREE_CODE (arg) == SSA_NAME)
603 : {
604 39699919 : edge e = gimple_phi_arg_edge (phi, i);
605 39699919 : tree val = value_on_edge (e, arg);
606 :
607 39699919 : if (val && val != arg && may_propagate_copy (arg, val))
608 : {
609 1180380 : if (TREE_CODE (val) != SSA_NAME)
610 29293 : prop_stats.num_const_prop++;
611 : else
612 1151087 : prop_stats.num_copy_prop++;
613 :
614 1180380 : propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
615 1180380 : replaced = true;
616 :
617 : /* If we propagated a copy and this argument flows
618 : through an abnormal edge, update the replacement
619 : accordingly. */
620 1180380 : if (TREE_CODE (val) == SSA_NAME
621 1151087 : && e->flags & EDGE_ABNORMAL
622 1180380 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
623 : {
624 : /* This can only occur for virtual operands, since
625 : for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
626 : would prevent replacement. */
627 0 : gcc_checking_assert (virtual_operand_p (val));
628 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
629 : }
630 : }
631 : }
632 : }
633 :
634 23396389 : if (dump_file && (dump_flags & TDF_DETAILS))
635 : {
636 149 : if (!replaced)
637 149 : fprintf (dump_file, "No folding possible\n");
638 : else
639 : {
640 0 : fprintf (dump_file, "Folded into: ");
641 0 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
642 0 : fprintf (dump_file, "\n");
643 : }
644 : }
645 :
646 23396389 : return replaced;
647 : }
648 :
649 :
650 : class substitute_and_fold_dom_walker : public dom_walker
651 : {
652 : public:
653 12505916 : substitute_and_fold_dom_walker (cdi_direction direction,
654 : class substitute_and_fold_engine *engine)
655 : : dom_walker (direction),
656 12505916 : something_changed (false),
657 12505916 : substitute_and_fold_engine (engine)
658 : {
659 12505916 : dceworklist = BITMAP_ALLOC (NULL);
660 12505916 : stmts_to_fixup.create (0);
661 12505916 : need_eh_cleanup = BITMAP_ALLOC (NULL);
662 12505916 : need_ab_cleanup = BITMAP_ALLOC (NULL);
663 12505916 : }
664 12505916 : ~substitute_and_fold_dom_walker ()
665 12505916 : {
666 12505916 : BITMAP_FREE (dceworklist);
667 12505916 : stmts_to_fixup.release ();
668 12505916 : BITMAP_FREE (need_eh_cleanup);
669 12505916 : BITMAP_FREE (need_ab_cleanup);
670 12505916 : }
671 :
672 : edge before_dom_children (basic_block) final override;
673 123235447 : void after_dom_children (basic_block bb) final override
674 : {
675 123235447 : substitute_and_fold_engine->post_fold_bb (bb);
676 123235447 : }
677 :
678 : bool something_changed;
679 : bitmap dceworklist;
680 : vec<gimple *> stmts_to_fixup;
681 : bitmap need_eh_cleanup;
682 : bitmap need_ab_cleanup;
683 :
684 : class substitute_and_fold_engine *substitute_and_fold_engine;
685 :
686 : private:
687 : void foreach_new_stmt_in_bb (gimple_stmt_iterator old_gsi,
688 : gimple_stmt_iterator new_gsi);
689 : };
690 :
691 : /* Call post_new_stmt for each new statement that has been added
692 : to the current BB. OLD_GSI is the statement iterator before the BB
693 : changes occurred. NEW_GSI is the iterator which may contain new
694 : statements. */
695 :
696 : void
697 14931219 : substitute_and_fold_dom_walker::foreach_new_stmt_in_bb
698 : (gimple_stmt_iterator old_gsi,
699 : gimple_stmt_iterator new_gsi)
700 : {
701 14931219 : basic_block bb = gsi_bb (new_gsi);
702 14931219 : if (gsi_end_p (old_gsi))
703 3294282 : old_gsi = gsi_start_bb (bb);
704 : else
705 13284078 : gsi_next (&old_gsi);
706 15003627 : while (gsi_stmt (old_gsi) != gsi_stmt (new_gsi))
707 : {
708 72408 : gimple *stmt = gsi_stmt (old_gsi);
709 72408 : substitute_and_fold_engine->post_new_stmt (stmt);
710 72408 : gsi_next (&old_gsi);
711 : }
712 14931219 : }
713 :
714 : bool
715 123235447 : substitute_and_fold_engine::propagate_into_phi_args (basic_block bb)
716 : {
717 123235447 : edge e;
718 123235447 : edge_iterator ei;
719 123235447 : bool propagated = false;
720 :
721 : /* Visit BB successor PHI nodes and replace PHI args. */
722 290609397 : FOR_EACH_EDGE (e, ei, bb->succs)
723 : {
724 167373950 : for (gphi_iterator gpi = gsi_start_phis (e->dest);
725 278094157 : !gsi_end_p (gpi); gsi_next (&gpi))
726 : {
727 110720207 : gphi *phi = gpi.phi ();
728 110720207 : use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
729 110720207 : tree arg = USE_FROM_PTR (use_p);
730 178367613 : if (TREE_CODE (arg) != SSA_NAME
731 110720207 : || virtual_operand_p (arg))
732 67647406 : continue;
733 43072801 : tree val = value_on_edge (e, arg);
734 43072801 : if (val
735 3143375 : && is_gimple_min_invariant (val)
736 45000580 : && may_propagate_copy (arg, val))
737 : {
738 1925935 : propagate_value (use_p, val);
739 1925935 : propagated = true;
740 : }
741 : }
742 : }
743 123235447 : return propagated;
744 : }
745 :
746 : edge
747 123235447 : substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
748 : {
749 123235447 : substitute_and_fold_engine->pre_fold_bb (bb);
750 :
751 : /* Propagate known values into PHI nodes. */
752 123235447 : for (gphi_iterator i = gsi_start_phis (bb);
753 169012592 : !gsi_end_p (i);
754 45777145 : gsi_next (&i))
755 : {
756 45777145 : gphi *phi = i.phi ();
757 45777145 : tree res = gimple_phi_result (phi);
758 91554290 : if (virtual_operand_p (res))
759 20464395 : continue;
760 25312750 : if (dump_file && (dump_flags & TDF_DETAILS))
761 : {
762 154 : fprintf (dump_file, "Folding PHI node: ");
763 154 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
764 : }
765 25312750 : if (res && TREE_CODE (res) == SSA_NAME)
766 : {
767 25312750 : tree sprime = substitute_and_fold_engine->value_of_expr (res, phi);
768 27229111 : if (sprime
769 25312750 : && sprime != res
770 25312750 : && may_propagate_copy (res, sprime))
771 : {
772 1916361 : if (dump_file && (dump_flags & TDF_DETAILS))
773 : {
774 5 : fprintf (dump_file, "Queued PHI for removal. Folds to: ");
775 5 : print_generic_expr (dump_file, sprime);
776 5 : fprintf (dump_file, "\n");
777 : }
778 1916361 : bitmap_set_bit (dceworklist, SSA_NAME_VERSION (res));
779 : /* As this now constitutes a copy duplicate points-to
780 : and range info appropriately. */
781 1916361 : if (TREE_CODE (sprime) == SSA_NAME)
782 1196687 : maybe_duplicate_ssa_info_at_copy (res, sprime);
783 1916361 : continue;
784 : }
785 : }
786 23396389 : something_changed |= substitute_and_fold_engine->replace_phi_args_in (phi);
787 : }
788 :
789 : /* Propagate known values into stmts. In some case it exposes
790 : more trivially deletable stmts to walk backward. */
791 246470894 : for (gimple_stmt_iterator i = gsi_start_bb (bb);
792 997513641 : !gsi_end_p (i);
793 874278194 : gsi_next (&i))
794 : {
795 874278194 : bool did_replace;
796 874278194 : gimple *stmt = gsi_stmt (i);
797 :
798 874278194 : substitute_and_fold_engine->pre_fold_stmt (stmt);
799 :
800 874278194 : if (dump_file && (dump_flags & TDF_DETAILS))
801 : {
802 1796 : fprintf (dump_file, "Folding statement: ");
803 1796 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
804 : }
805 :
806 : /* No point propagating into a stmt we have a value for we
807 : can propagate into all uses. Mark it for removal instead. */
808 874278194 : tree lhs = gimple_get_lhs (stmt);
809 874278194 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
810 : {
811 184285279 : tree sprime = substitute_and_fold_engine->value_of_stmt (stmt, lhs);
812 199505750 : if (sprime
813 184285279 : && sprime != lhs
814 15239934 : && may_propagate_copy (lhs, sprime)
815 15238567 : && !stmt_could_throw_p (cfun, stmt)
816 199509996 : && !gimple_has_side_effects (stmt))
817 : {
818 15220471 : if (dump_file && (dump_flags & TDF_DETAILS))
819 : {
820 56 : fprintf (dump_file, "Queued stmt for removal. Folds to: ");
821 56 : print_generic_expr (dump_file, sprime);
822 56 : fprintf (dump_file, "\n");
823 : }
824 15220471 : bitmap_set_bit (dceworklist, SSA_NAME_VERSION (lhs));
825 : /* As this now constitutes a copy duplicate points-to
826 : and range info appropriately. */
827 15220471 : if (TREE_CODE (sprime) == SSA_NAME)
828 9020088 : maybe_duplicate_ssa_info_at_copy (lhs, sprime);
829 15220471 : continue;
830 : }
831 : }
832 :
833 : /* Replace the statement with its folded version and mark it
834 : folded. */
835 859057723 : did_replace = false;
836 859057723 : gimple *old_stmt = stmt;
837 859057723 : bool was_noreturn = false;
838 859057723 : bool can_make_abnormal_goto = false;
839 859057723 : if (is_gimple_call (stmt))
840 : {
841 54580982 : was_noreturn = gimple_call_noreturn_p (stmt);
842 54580982 : can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
843 : }
844 :
845 : /* Replace real uses in the statement. */
846 859057723 : did_replace |= substitute_and_fold_engine->replace_uses_in (stmt);
847 :
848 859057723 : gimple_stmt_iterator prev_gsi = i;
849 859057723 : gsi_prev (&prev_gsi);
850 :
851 : /* If we made a replacement, fold the statement. */
852 859057723 : if (did_replace)
853 : {
854 13564263 : update_stmt (stmt);
855 13564263 : fold_stmt (&i, follow_single_use_edges);
856 13564263 : stmt = gsi_stmt (i);
857 13564263 : gimple_set_modified (stmt, true);
858 : }
859 : /* Also fold if we want to fold all statements. */
860 845493460 : else if (substitute_and_fold_engine->fold_all_stmts
861 845493460 : && fold_stmt (&i, follow_single_use_edges))
862 : {
863 0 : did_replace = true;
864 0 : stmt = gsi_stmt (i);
865 0 : gimple_set_modified (stmt, true);
866 : }
867 :
868 : /* Some statements may be simplified using propagator
869 : specific information. Do this before propagating
870 : into the stmt to not disturb pass specific information. */
871 859057723 : update_stmt_if_modified (stmt);
872 859057723 : if (substitute_and_fold_engine->fold_stmt (&i))
873 : {
874 1811002 : did_replace = true;
875 1811002 : prop_stats.num_stmts_folded++;
876 1811002 : stmt = gsi_stmt (i);
877 1811002 : gimple_set_modified (stmt, true);
878 : }
879 :
880 : /* If this is a control statement the propagator left edges
881 : unexecuted on force the condition in a way consistent with
882 : that. See PR66945 for cases where the propagator can end
883 : up with a different idea of a taken edge than folding
884 : (once undefined behavior is involved). */
885 859057723 : if (gimple_code (stmt) == GIMPLE_COND)
886 : {
887 43669964 : if ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE)
888 43669964 : ^ (EDGE_SUCC (bb, 1)->flags & EDGE_EXECUTABLE))
889 : {
890 486795 : if (((EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) != 0)
891 486795 : == ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE) != 0))
892 117481 : gimple_cond_make_true (as_a <gcond *> (stmt));
893 : else
894 369314 : gimple_cond_make_false (as_a <gcond *> (stmt));
895 486795 : gimple_set_modified (stmt, true);
896 486795 : did_replace = true;
897 : }
898 : }
899 :
900 : /* Now cleanup. */
901 859057723 : if (did_replace)
902 : {
903 14931219 : foreach_new_stmt_in_bb (prev_gsi, i);
904 :
905 : /* If we cleaned up EH information from the statement,
906 : remove EH edges. */
907 14931219 : if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
908 155930 : bitmap_set_bit (need_eh_cleanup, bb->index);
909 :
910 : /* If we turned a call with possible abnormal control transfer
911 : into one that doesn't, remove abnormal edges. */
912 14931219 : if (can_make_abnormal_goto
913 14931219 : && !stmt_can_make_abnormal_goto (stmt))
914 3 : bitmap_set_bit (need_ab_cleanup, bb->index);
915 :
916 : /* If we turned a not noreturn call into a noreturn one
917 : schedule it for fixup. */
918 14931219 : if (!was_noreturn
919 14800601 : && is_gimple_call (stmt)
920 16391411 : && gimple_call_noreturn_p (stmt))
921 71 : stmts_to_fixup.safe_push (stmt);
922 :
923 14931219 : if (gimple_assign_single_p (stmt))
924 : {
925 3533318 : tree rhs = gimple_assign_rhs1 (stmt);
926 :
927 3533318 : if (TREE_CODE (rhs) == ADDR_EXPR)
928 390313 : recompute_tree_invariant_for_addr_expr (rhs);
929 : }
930 :
931 : /* Determine what needs to be done to update the SSA form. */
932 14931219 : update_stmt_if_modified (stmt);
933 14931219 : if (!is_gimple_debug (stmt))
934 10835175 : something_changed = true;
935 : }
936 :
937 859057723 : if (dump_file && (dump_flags & TDF_DETAILS))
938 : {
939 1740 : if (did_replace)
940 : {
941 144 : fprintf (dump_file, "Folded into: ");
942 144 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
943 144 : fprintf (dump_file, "\n");
944 : }
945 : else
946 1596 : fprintf (dump_file, "Not folded\n");
947 : }
948 : }
949 :
950 123235447 : something_changed |= substitute_and_fold_engine->propagate_into_phi_args (bb);
951 :
952 123235447 : return NULL;
953 : }
954 :
955 :
956 :
957 : /* Perform final substitution and folding of propagated values.
958 : Process the whole function if BLOCK is null, otherwise only
959 : process the blocks that BLOCK dominates. In the latter case,
960 : it is the caller's responsibility to ensure that dominator
961 : information is available and up-to-date.
962 :
963 : PROP_VALUE[I] contains the single value that should be substituted
964 : at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
965 : substituted.
966 :
967 : If FOLD_FN is non-NULL the function will be invoked on all statements
968 : before propagating values for pass specific simplification.
969 :
970 : DO_DCE is true if trivially dead stmts can be removed.
971 :
972 : If DO_DCE is true, the statements within a BB are walked from
973 : last to first element. Otherwise we scan from first to last element.
974 :
975 : Return TRUE when something changed. */
976 :
977 : bool
978 12505916 : substitute_and_fold_engine::substitute_and_fold (basic_block block)
979 : {
980 12505916 : if (dump_file && (dump_flags & TDF_DETAILS))
981 161 : fprintf (dump_file, "\nSubstituting values and folding statements\n\n");
982 :
983 12505916 : memset (&prop_stats, 0, sizeof (prop_stats));
984 :
985 : /* Don't call calculate_dominance_info when iterating over a subgraph.
986 : Callers that are using the interface this way are likely to want to
987 : iterate over several disjoint subgraphs, and it would be expensive
988 : in enable-checking builds to revalidate the whole dominance tree
989 : each time. */
990 12505916 : if (block)
991 1421 : gcc_assert (dom_info_state (CDI_DOMINATORS));
992 : else
993 12504495 : calculate_dominance_info (CDI_DOMINATORS);
994 12505916 : substitute_and_fold_dom_walker walker (CDI_DOMINATORS, this);
995 12505916 : walker.walk (block ? block : ENTRY_BLOCK_PTR_FOR_FN (cfun));
996 :
997 12505916 : simple_dce_from_worklist (walker.dceworklist, walker.need_eh_cleanup);
998 12505916 : if (!bitmap_empty_p (walker.need_eh_cleanup))
999 36834 : gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup);
1000 12505916 : if (!bitmap_empty_p (walker.need_ab_cleanup))
1001 3 : gimple_purge_all_dead_abnormal_call_edges (walker.need_ab_cleanup);
1002 :
1003 : /* Fixup stmts that became noreturn calls. This may require splitting
1004 : blocks and thus isn't possible during the dominator walk. Do this
1005 : in reverse order so we don't inadvertently remove a stmt we want to
1006 : fixup by visiting a dominating now noreturn call first. */
1007 12505987 : while (!walker.stmts_to_fixup.is_empty ())
1008 : {
1009 71 : gimple *stmt = walker.stmts_to_fixup.pop ();
1010 77 : if (!gimple_bb (stmt))
1011 6 : continue;
1012 65 : if (dump_file && dump_flags & TDF_DETAILS)
1013 : {
1014 0 : fprintf (dump_file, "Fixing up noreturn call ");
1015 0 : print_gimple_stmt (dump_file, stmt, 0);
1016 0 : fprintf (dump_file, "\n");
1017 : }
1018 65 : fixup_noreturn_call (stmt);
1019 : }
1020 :
1021 12505916 : statistics_counter_event (cfun, "Constants propagated",
1022 12505916 : prop_stats.num_const_prop);
1023 12505916 : statistics_counter_event (cfun, "Copies propagated",
1024 12505916 : prop_stats.num_copy_prop);
1025 12505916 : statistics_counter_event (cfun, "Statements folded",
1026 12505916 : prop_stats.num_stmts_folded);
1027 :
1028 12505916 : return walker.something_changed;
1029 12505916 : }
1030 :
1031 :
1032 : /* Return true if we may propagate ORIG into DEST, false otherwise.
1033 : If DEST_NOT_ABNORMAL_PHI_EDGE_P is true then assume the propagation does
1034 : not happen into a PHI argument which flows in from an abnormal edge
1035 : which relaxes some constraints. */
1036 :
1037 : bool
1038 156400613 : may_propagate_copy (tree dest, tree orig, bool dest_not_abnormal_phi_edge_p)
1039 : {
1040 156400613 : tree type_d = TREE_TYPE (dest);
1041 156400613 : tree type_o = TREE_TYPE (orig);
1042 :
1043 : /* If ORIG is a default definition which flows in from an abnormal edge
1044 : then the copy can be propagated. It is important that we do so to avoid
1045 : uninitialized copies. */
1046 156400613 : if (TREE_CODE (orig) == SSA_NAME
1047 108140394 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)
1048 29288 : && SSA_NAME_IS_DEFAULT_DEF (orig)
1049 156403734 : && (SSA_NAME_VAR (orig) == NULL_TREE
1050 3121 : || VAR_P (SSA_NAME_VAR (orig))))
1051 : ;
1052 : /* Otherwise if ORIG just flows in from an abnormal edge then the copy cannot
1053 : be propagated. */
1054 156397895 : else if (TREE_CODE (orig) == SSA_NAME
1055 156397895 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
1056 : return false;
1057 : /* Similarly if DEST flows in from an abnormal edge then the copy cannot be
1058 : propagated. If we know we do not propagate into such a PHI argument this
1059 : does not apply. */
1060 156371325 : else if (!dest_not_abnormal_phi_edge_p
1061 80185084 : && TREE_CODE (dest) == SSA_NAME
1062 236556409 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
1063 : return false;
1064 :
1065 : /* Do not copy between types for which we *do* need a conversion. */
1066 156358486 : if (!useless_type_conversion_p (type_d, type_o))
1067 : return false;
1068 :
1069 : /* Generally propagating virtual operands is not ok as that may
1070 : create overlapping life-ranges. */
1071 156341925 : if (TREE_CODE (dest) == SSA_NAME && virtual_operand_p (dest))
1072 : return false;
1073 :
1074 : /* Keep lhs of [[gnu::musttail]] calls as is, those need to be still
1075 : tail callable. */
1076 155858311 : if (TREE_CODE (dest) == SSA_NAME
1077 155688297 : && is_gimple_call (SSA_NAME_DEF_STMT (dest))
1078 157280349 : && gimple_call_must_tail_p (as_a <gcall *> (SSA_NAME_DEF_STMT (dest))))
1079 948 : return false;
1080 :
1081 : /* Anything else is OK. */
1082 : return true;
1083 : }
1084 :
1085 : /* Like may_propagate_copy, but use as the destination expression
1086 : the principal expression (typically, the RHS) contained in
1087 : statement DEST. This is more efficient when working with the
1088 : gimple tuples representation. */
1089 :
1090 : bool
1091 393473 : may_propagate_copy_into_stmt (gimple *dest, tree orig)
1092 : {
1093 393473 : tree type_d;
1094 393473 : tree type_o;
1095 :
1096 : /* If the statement is a switch or a single-rhs assignment,
1097 : then the expression to be replaced by the propagation may
1098 : be an SSA_NAME. Fortunately, there is an explicit tree
1099 : for the expression, so we delegate to may_propagate_copy. */
1100 :
1101 393473 : if (gimple_assign_single_p (dest))
1102 185002 : return may_propagate_copy (gimple_assign_rhs1 (dest), orig, true);
1103 208471 : else if (gswitch *dest_swtch = dyn_cast <gswitch *> (dest))
1104 0 : return may_propagate_copy (gimple_switch_index (dest_swtch), orig, true);
1105 :
1106 : /* In other cases, the expression is not materialized, so there
1107 : is no destination to pass to may_propagate_copy. On the other
1108 : hand, the expression cannot be an SSA_NAME, so the analysis
1109 : is much simpler. */
1110 :
1111 208471 : if (TREE_CODE (orig) == SSA_NAME
1112 208471 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
1113 : return false;
1114 :
1115 208471 : if (is_gimple_assign (dest))
1116 179098 : type_d = TREE_TYPE (gimple_assign_lhs (dest));
1117 29373 : else if (gimple_code (dest) == GIMPLE_COND)
1118 21152 : type_d = boolean_type_node;
1119 8221 : else if (is_gimple_call (dest)
1120 8221 : && gimple_call_lhs (dest) != NULL_TREE)
1121 8221 : type_d = TREE_TYPE (gimple_call_lhs (dest));
1122 : else
1123 0 : gcc_unreachable ();
1124 :
1125 208471 : type_o = TREE_TYPE (orig);
1126 :
1127 208471 : if (!useless_type_conversion_p (type_d, type_o))
1128 : return false;
1129 :
1130 : return true;
1131 : }
1132 :
1133 : /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
1134 :
1135 : Use this version when not const/copy propagating values. For example,
1136 : PRE uses this version when building expressions as they would appear
1137 : in specific blocks taking into account actions of PHI nodes.
1138 :
1139 : The statement in which an expression has been replaced should be
1140 : folded using fold_stmt_inplace. */
1141 :
1142 : void
1143 57684802 : replace_exp (use_operand_p op_p, tree val)
1144 : {
1145 57684802 : if (TREE_CODE (val) == SSA_NAME || CONSTANT_CLASS_P (val))
1146 53627579 : SET_USE (op_p, val);
1147 : else
1148 4057223 : SET_USE (op_p, unshare_expr (val));
1149 57684802 : }
1150 :
1151 :
1152 : /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1153 : into the operand pointed to by OP_P.
1154 :
1155 : Use this version for const/copy propagation as it will perform additional
1156 : checks to ensure validity of the const/copy propagation. */
1157 :
1158 : void
1159 50228132 : propagate_value (use_operand_p op_p, tree val)
1160 : {
1161 50228132 : if (flag_checking)
1162 : {
1163 50227674 : bool ab = (is_a <gphi *> (USE_STMT (op_p))
1164 66741851 : && (gimple_phi_arg_edge (as_a <gphi *> (USE_STMT (op_p)),
1165 16514177 : PHI_ARG_INDEX_FROM_USE (op_p))
1166 16514177 : ->flags & EDGE_ABNORMAL));
1167 50227674 : gcc_assert (may_propagate_copy (USE_FROM_PTR (op_p), val, !ab));
1168 : }
1169 50228132 : replace_exp (op_p, val);
1170 50228132 : }
1171 :
1172 :
1173 : /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1174 : into the tree pointed to by OP_P.
1175 :
1176 : Use this version for const/copy propagation when SSA operands are not
1177 : available. It will perform the additional checks to ensure validity of
1178 : the const/copy propagation, but will not update any operand information.
1179 : Be sure to mark the stmt as modified. */
1180 :
1181 : void
1182 426916 : propagate_tree_value (tree *op_p, tree val)
1183 : {
1184 426916 : if (TREE_CODE (val) == SSA_NAME)
1185 378486 : *op_p = val;
1186 : else
1187 48430 : *op_p = unshare_expr (val);
1188 426916 : }
1189 :
1190 :
1191 : /* Like propagate_tree_value, but use as the operand to replace
1192 : the principal expression (typically, the RHS) contained in the
1193 : statement referenced by iterator GSI. Note that it is not
1194 : always possible to update the statement in-place, so a new
1195 : statement may be created to replace the original. */
1196 :
1197 : void
1198 426916 : propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
1199 : {
1200 426916 : gimple *stmt = gsi_stmt (*gsi);
1201 :
1202 426916 : if (is_gimple_assign (stmt))
1203 : {
1204 386534 : tree expr = NULL_TREE;
1205 386534 : if (gimple_assign_single_p (stmt))
1206 203477 : expr = gimple_assign_rhs1 (stmt);
1207 386534 : propagate_tree_value (&expr, val);
1208 386534 : gimple_assign_set_rhs_from_tree (gsi, expr);
1209 : }
1210 40382 : else if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1211 : {
1212 27841 : tree lhs = NULL_TREE;
1213 27841 : tree rhs = build_zero_cst (TREE_TYPE (val));
1214 27841 : propagate_tree_value (&lhs, val);
1215 27841 : gimple_cond_set_code (cond_stmt, NE_EXPR);
1216 27841 : gimple_cond_set_lhs (cond_stmt, lhs);
1217 27841 : gimple_cond_set_rhs (cond_stmt, rhs);
1218 : }
1219 12541 : else if (is_gimple_call (stmt)
1220 12541 : && gimple_call_lhs (stmt) != NULL_TREE)
1221 : {
1222 12541 : tree expr = NULL_TREE;
1223 12541 : propagate_tree_value (&expr, val);
1224 12541 : replace_call_with_value (gsi, expr);
1225 : }
1226 0 : else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1227 0 : propagate_tree_value (gimple_switch_index_ptr (swtch_stmt), val);
1228 : else
1229 0 : gcc_unreachable ();
1230 426916 : }
1231 :
1232 : /* Check exits of each loop in FUN, walk over loop closed PHIs in
1233 : each exit basic block and propagate degenerate PHIs. */
1234 :
1235 : unsigned
1236 245651 : clean_up_loop_closed_phi (function *fun)
1237 : {
1238 245651 : gphi *phi;
1239 245651 : tree rhs;
1240 245651 : tree lhs;
1241 245651 : gphi_iterator gsi;
1242 :
1243 : /* Avoid possibly quadratic work when scanning for loop exits across
1244 : all loops of a nest. */
1245 245651 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1246 : return 0;
1247 :
1248 : /* replace_uses_by might purge dead EH edges and we want it to also
1249 : remove dominated blocks. */
1250 245651 : calculate_dominance_info (CDI_DOMINATORS);
1251 :
1252 : /* Walk over loop in function. */
1253 1372832 : for (auto loop : loops_list (fun, 0))
1254 : {
1255 : /* Check each exit edege of loop. */
1256 635879 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1257 3068488 : for (edge e : exits)
1258 1956722 : if (single_pred_p (e->dest))
1259 : /* Walk over loop-closed PHIs. */
1260 1702575 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);)
1261 : {
1262 919566 : phi = gsi.phi ();
1263 919566 : rhs = gimple_phi_arg_def (phi, 0);
1264 919566 : lhs = gimple_phi_result (phi);
1265 :
1266 1838251 : if (virtual_operand_p (rhs))
1267 : {
1268 491608 : imm_use_iterator iter;
1269 491608 : use_operand_p use_p;
1270 491608 : gimple *stmt;
1271 :
1272 1194758 : FOR_EACH_IMM_USE_STMT (stmt, iter, lhs)
1273 1419906 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1274 709953 : SET_USE (use_p, rhs);
1275 :
1276 491608 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1277 48 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
1278 491608 : remove_phi_node (&gsi, true);
1279 : }
1280 427958 : else if (may_propagate_copy (lhs, rhs))
1281 : {
1282 : /* Dump details. */
1283 427908 : if (dump_file && (dump_flags & TDF_DETAILS))
1284 : {
1285 3 : fprintf (dump_file, " Replacing '");
1286 3 : print_generic_expr (dump_file, lhs, dump_flags);
1287 3 : fprintf (dump_file, "' with '");
1288 3 : print_generic_expr (dump_file, rhs, dump_flags);
1289 3 : fprintf (dump_file, "'\n");
1290 : }
1291 :
1292 427908 : replace_uses_by (lhs, rhs);
1293 427908 : remove_phi_node (&gsi, true);
1294 : }
1295 : else
1296 50 : gsi_next (&gsi);
1297 : }
1298 635879 : }
1299 :
1300 245651 : return 0;
1301 : }
|
