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 290579865 : add_ssa_edge (tree var)
133 : {
134 290579865 : imm_use_iterator iter;
135 290579865 : use_operand_p use_p;
136 :
137 894408758 : FOR_EACH_IMM_USE_FAST (use_p, iter, var)
138 : {
139 603828893 : gimple *use_stmt = USE_STMT (use_p);
140 603828893 : if (!prop_simulate_again_p (use_stmt))
141 256222487 : 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 347606406 : basic_block use_bb = gimple_bb (use_stmt);
146 347606406 : if (! (use_bb->flags & BB_VISITED))
147 142249356 : continue;
148 :
149 : /* If this is a use on a not yet executable edge do not bother to
150 : queue it. */
151 205357050 : if (gimple_code (use_stmt) == GIMPLE_PHI
152 205357050 : && !(EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->flags
153 67621017 : & EDGE_EXECUTABLE))
154 6480746 : continue;
155 :
156 198876304 : if (bitmap_set_bit (ssa_edge_worklist, gimple_uid (use_stmt)))
157 : {
158 183175650 : uid_to_stmt[gimple_uid (use_stmt)] = use_stmt;
159 183175650 : 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 290579865 : }
166 290579865 : }
167 :
168 :
169 : /* Add edge E to the control flow worklist. */
170 :
171 : static void
172 141993665 : add_control_edge (edge e)
173 : {
174 141993665 : basic_block bb = e->dest;
175 141993665 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
176 : return;
177 :
178 : /* If the edge had already been executed, skip it. */
179 125999461 : if (e->flags & EDGE_EXECUTABLE)
180 : return;
181 :
182 108855027 : e->flags |= EDGE_EXECUTABLE;
183 :
184 108855027 : int bb_order = bb_to_cfg_order[bb->index];
185 108855027 : bitmap_set_bit (cfg_blocks, bb_order);
186 :
187 108855027 : 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 850657760 : ssa_propagation_engine::simulate_stmt (gimple *stmt)
197 : {
198 850657760 : enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
199 850657760 : edge taken_edge = NULL;
200 850657760 : tree output_name = NULL_TREE;
201 :
202 : /* Pull the stmt off the SSA edge worklist. */
203 850657760 : 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 850657760 : if (!prop_simulate_again_p (stmt))
208 610776042 : return;
209 :
210 365394098 : if (gimple_code (stmt) == GIMPLE_PHI)
211 : {
212 81314251 : val = visit_phi (as_a <gphi *> (stmt));
213 81314251 : output_name = gimple_phi_result (stmt);
214 : }
215 : else
216 284079847 : val = visit_stmt (stmt, &taken_edge, &output_name);
217 :
218 365394098 : if (val == SSA_PROP_VARYING)
219 : {
220 125512380 : 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 125512380 : if (output_name)
225 75046253 : 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 125512380 : if (stmt_ends_bb_p (stmt))
230 : {
231 51969386 : edge e;
232 51969386 : edge_iterator ei;
233 51969386 : basic_block bb = gimple_bb (stmt);
234 133866892 : FOR_EACH_EDGE (e, ei, bb->succs)
235 81897506 : add_control_edge (e);
236 : }
237 : return;
238 : }
239 239881718 : 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 222222029 : if (output_name)
244 215533612 : 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 222222029 : if (taken_edge)
249 6688417 : 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 239881718 : bool has_simulate_again_uses = false;
255 239881718 : use_operand_p use_p;
256 239881718 : ssa_op_iter iter;
257 239881718 : if (gimple_code (stmt) == GIMPLE_PHI)
258 : {
259 67819530 : edge_iterator ei;
260 67819530 : edge e;
261 67819530 : tree arg;
262 105497555 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
263 103525962 : if (!(e->flags & EDGE_EXECUTABLE)
264 103525962 : || ((arg = PHI_ARG_DEF_FROM_EDGE (stmt, e))
265 94948512 : && TREE_CODE (arg) == SSA_NAME
266 78075759 : && !SSA_NAME_IS_DEFAULT_DEF (arg)
267 77864010 : && prop_simulate_again_p (SSA_NAME_DEF_STMT (arg))))
268 : {
269 : has_simulate_again_uses = true;
270 : break;
271 : }
272 : }
273 : else
274 211493918 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
275 : {
276 170617018 : gimple *def_stmt = SSA_NAME_DEF_STMT (USE_FROM_PTR (use_p));
277 170617018 : if (!gimple_nop_p (def_stmt)
278 170617018 : && prop_simulate_again_p (def_stmt))
279 : {
280 : has_simulate_again_uses = true;
281 : break;
282 : }
283 : }
284 239881718 : if (!has_simulate_again_uses)
285 : {
286 42848493 : if (dump_file && (dump_flags & TDF_DETAILS))
287 39 : fprintf (dump_file, "marking stmt to be not simulated again\n");
288 42848493 : 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 83072148 : ssa_propagation_engine::simulate_block (basic_block block)
298 : {
299 83072148 : gimple_stmt_iterator gsi;
300 :
301 : /* There is nothing to do for the exit block. */
302 83072148 : if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
303 83072148 : return;
304 :
305 83072148 : 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 125879860 : for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
311 42807712 : 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 83072148 : if (! (block->flags & BB_VISITED))
316 : {
317 77749141 : gimple_stmt_iterator j;
318 77749141 : unsigned int normal_edge_count;
319 77749141 : edge e, normal_edge;
320 77749141 : edge_iterator ei;
321 :
322 780289308 : for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
323 624791026 : simulate_stmt (gsi_stmt (j));
324 :
325 : /* Note that we have simulated this block. */
326 77749141 : 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 77749141 : normal_edge_count = 0;
340 77749141 : normal_edge = NULL;
341 186926016 : FOR_EACH_EDGE (e, ei, block->succs)
342 : {
343 109176875 : if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
344 7209791 : add_control_edge (e);
345 : else
346 : {
347 101967084 : normal_edge_count++;
348 101967084 : normal_edge = e;
349 : }
350 : }
351 :
352 77749141 : if (normal_edge_count == 1)
353 38031028 : add_control_edge (normal_edge);
354 : }
355 : }
356 :
357 :
358 : /* Initialize local data structures and work lists. */
359 :
360 : static void
361 8166923 : ssa_prop_init (void)
362 : {
363 8166923 : edge e;
364 8166923 : edge_iterator ei;
365 8166923 : basic_block bb;
366 :
367 : /* Worklists of SSA edges. */
368 8166923 : ssa_edge_worklist = BITMAP_ALLOC (NULL);
369 8166923 : bitmap_tree_view (ssa_edge_worklist);
370 :
371 : /* Worklist of basic-blocks. */
372 8166923 : bb_to_cfg_order = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
373 8166923 : cfg_order_to_bb = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
374 8166923 : int n = pre_and_rev_post_order_compute_fn (cfun, NULL,
375 : cfg_order_to_bb, false);
376 94653871 : for (int i = 0; i < n; ++i)
377 78320025 : bb_to_cfg_order[cfg_order_to_bb[i]] = i;
378 8166923 : 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 8166923 : set_gimple_stmt_max_uid (cfun, 0);
385 86486948 : for (int i = 0; i < n; ++i)
386 : {
387 78320025 : gimple_stmt_iterator si;
388 78320025 : bb = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb[i]);
389 :
390 109614770 : for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
391 : {
392 31294745 : gimple *stmt = gsi_stmt (si);
393 31294745 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
394 : }
395 :
396 783793332 : for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
397 : {
398 627153282 : gimple *stmt = gsi_stmt (si);
399 627153282 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
400 : }
401 :
402 78320025 : bb->flags &= ~BB_VISITED;
403 188017475 : FOR_EACH_EDGE (e, ei, bb->succs)
404 109697450 : e->flags &= ~EDGE_EXECUTABLE;
405 : }
406 8166923 : uid_to_stmt.safe_grow (gimple_stmt_max_uid (cfun), true);
407 8166923 : }
408 :
409 :
410 : /* Free allocated storage. */
411 :
412 : static void
413 8166923 : ssa_prop_fini (void)
414 : {
415 8166923 : BITMAP_FREE (cfg_blocks);
416 8166923 : free (bb_to_cfg_order);
417 8166923 : free (cfg_order_to_bb);
418 8166923 : BITMAP_FREE (ssa_edge_worklist);
419 8166923 : uid_to_stmt.release ();
420 8166923 : }
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 8166923 : ssa_propagation_engine::ssa_propagate (void)
431 : {
432 8166923 : 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 8166923 : edge e;
439 8166923 : edge_iterator ei;
440 16333846 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
441 : {
442 8166923 : e->flags &= ~EDGE_EXECUTABLE;
443 8166923 : add_control_edge (e);
444 : }
445 274298093 : while (1)
446 : {
447 274298093 : int next_block_order = (bitmap_empty_p (cfg_blocks)
448 274298093 : ? -1 : bitmap_first_set_bit (cfg_blocks));
449 274298093 : int next_stmt_uid = (bitmap_empty_p (ssa_edge_worklist)
450 274298093 : ? -1 : bitmap_first_set_bit (ssa_edge_worklist));
451 274298093 : if (next_block_order == -1 && next_stmt_uid == -1)
452 : break;
453 :
454 266131170 : int next_stmt_bb_order = -1;
455 266131170 : gimple *next_stmt = NULL;
456 266131170 : if (next_stmt_uid != -1)
457 : {
458 186888717 : next_stmt = uid_to_stmt[next_stmt_uid];
459 186888717 : 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 266131170 : if (next_block_order != -1
464 231867212 : && (next_stmt_bb_order == -1
465 231867212 : || next_block_order <= next_stmt_bb_order))
466 : {
467 83072148 : bitmap_clear_bit (cfg_blocks, next_block_order);
468 83072148 : basic_block bb
469 83072148 : = BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb [next_block_order]);
470 83072148 : simulate_block (bb);
471 83072148 : }
472 : /* Else simulate from the SSA edge worklist. */
473 : else
474 : {
475 183059022 : 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 183059022 : simulate_stmt (next_stmt);
481 : }
482 : }
483 :
484 8166923 : ssa_prop_fini ();
485 8166923 : }
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 34543601 : stmt_makes_single_store (gimple *stmt)
494 : {
495 34543601 : tree lhs;
496 :
497 34543601 : if (gimple_code (stmt) != GIMPLE_ASSIGN
498 34543601 : && gimple_code (stmt) != GIMPLE_CALL)
499 : return false;
500 :
501 34559249 : if (!gimple_vdef (stmt))
502 : return false;
503 :
504 2619496 : lhs = gimple_get_lhs (stmt);
505 :
506 : /* A call statement may have a null LHS. */
507 2619496 : if (!lhs)
508 : return false;
509 :
510 2619496 : return (!TREE_THIS_VOLATILE (lhs)
511 2619496 : && (DECL_P (lhs)
512 2603848 : || 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 58202854 : substitute_and_fold_engine::value_on_edge (edge, tree expr)
531 : {
532 58202854 : return value_of_expr (expr);
533 : }
534 :
535 : tree
536 136333426 : substitute_and_fold_engine::value_of_stmt (gimple *stmt, tree name)
537 : {
538 136333426 : if (!name)
539 0 : name = gimple_get_lhs (stmt);
540 :
541 136333426 : gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
542 :
543 136333426 : if (name)
544 136333426 : return value_of_expr (name);
545 : return NULL_TREE;
546 : }
547 :
548 : bool
549 508501 : substitute_and_fold_engine::range_of_expr (vrange &, tree, gimple *)
550 : {
551 508501 : 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 874516118 : substitute_and_fold_engine::replace_uses_in (gimple *stmt)
559 : {
560 874516118 : bool replaced = false;
561 874516118 : use_operand_p use;
562 874516118 : ssa_op_iter iter;
563 :
564 1271121114 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
565 : {
566 396604996 : tree tuse = USE_FROM_PTR (use);
567 396604996 : tree val = value_of_expr (tuse, stmt);
568 :
569 396604996 : if (val == tuse || val == NULL_TREE)
570 381987487 : continue;
571 :
572 14617509 : if (!may_propagate_copy (tuse, val))
573 645 : continue;
574 :
575 14616864 : if (TREE_CODE (val) != SSA_NAME)
576 5744392 : prop_stats.num_const_prop++;
577 : else
578 8872472 : prop_stats.num_copy_prop++;
579 :
580 14616864 : propagate_value (use, val);
581 :
582 14616864 : replaced = true;
583 : }
584 :
585 874516118 : 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 23611854 : substitute_and_fold_engine::replace_phi_args_in (gphi *phi)
594 : {
595 23611854 : size_t i;
596 23611854 : bool replaced = false;
597 :
598 80117281 : for (i = 0; i < gimple_phi_num_args (phi); i++)
599 : {
600 56505427 : tree arg = gimple_phi_arg_def (phi, i);
601 :
602 56505427 : if (TREE_CODE (arg) == SSA_NAME)
603 : {
604 40112409 : edge e = gimple_phi_arg_edge (phi, i);
605 40112409 : tree val = value_on_edge (e, arg);
606 :
607 40112409 : if (val && val != arg && may_propagate_copy (arg, val))
608 : {
609 1199411 : if (TREE_CODE (val) != SSA_NAME)
610 29375 : prop_stats.num_const_prop++;
611 : else
612 1170036 : prop_stats.num_copy_prop++;
613 :
614 1199411 : propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
615 1199411 : replaced = true;
616 :
617 : /* If we propagated a copy and this argument flows
618 : through an abnormal edge, update the replacement
619 : accordingly. */
620 1199411 : if (TREE_CODE (val) == SSA_NAME
621 1170036 : && e->flags & EDGE_ABNORMAL
622 1199411 : && !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 23611854 : 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 23611854 : return replaced;
647 : }
648 :
649 :
650 : class substitute_and_fold_dom_walker : public dom_walker
651 : {
652 : public:
653 12596222 : substitute_and_fold_dom_walker (cdi_direction direction,
654 : class substitute_and_fold_engine *engine)
655 : : dom_walker (direction),
656 12596222 : something_changed (false),
657 12596222 : substitute_and_fold_engine (engine)
658 : {
659 12596222 : dceworklist = BITMAP_ALLOC (NULL);
660 12596222 : stmts_to_fixup.create (0);
661 12596222 : need_eh_cleanup = BITMAP_ALLOC (NULL);
662 12596222 : need_ab_cleanup = BITMAP_ALLOC (NULL);
663 12596222 : }
664 12596222 : ~substitute_and_fold_dom_walker ()
665 12596222 : {
666 12596222 : BITMAP_FREE (dceworklist);
667 12596222 : stmts_to_fixup.release ();
668 12596222 : BITMAP_FREE (need_eh_cleanup);
669 12596222 : BITMAP_FREE (need_ab_cleanup);
670 12596222 : }
671 :
672 : edge before_dom_children (basic_block) final override;
673 124820687 : void after_dom_children (basic_block bb) final override
674 : {
675 124820687 : substitute_and_fold_engine->post_fold_bb (bb);
676 124820687 : }
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 15150895 : substitute_and_fold_dom_walker::foreach_new_stmt_in_bb
698 : (gimple_stmt_iterator old_gsi,
699 : gimple_stmt_iterator new_gsi)
700 : {
701 15150895 : basic_block bb = gsi_bb (new_gsi);
702 15150895 : if (gsi_end_p (old_gsi))
703 3343746 : old_gsi = gsi_start_bb (bb);
704 : else
705 13479022 : gsi_next (&old_gsi);
706 15223693 : while (gsi_stmt (old_gsi) != gsi_stmt (new_gsi))
707 : {
708 72798 : gimple *stmt = gsi_stmt (old_gsi);
709 72798 : substitute_and_fold_engine->post_new_stmt (stmt);
710 72798 : gsi_next (&old_gsi);
711 : }
712 15150895 : }
713 :
714 : bool
715 124820687 : substitute_and_fold_engine::propagate_into_phi_args (basic_block bb)
716 : {
717 124820687 : edge e;
718 124820687 : edge_iterator ei;
719 124820687 : bool propagated = false;
720 :
721 : /* Visit BB successor PHI nodes and replace PHI args. */
722 294460733 : FOR_EACH_EDGE (e, ei, bb->succs)
723 : {
724 169640046 : for (gphi_iterator gpi = gsi_start_phis (e->dest);
725 281787315 : !gsi_end_p (gpi); gsi_next (&gpi))
726 : {
727 112147269 : gphi *phi = gpi.phi ();
728 112147269 : use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
729 112147269 : tree arg = USE_FROM_PTR (use_p);
730 180778495 : if (TREE_CODE (arg) != SSA_NAME
731 112147269 : || virtual_operand_p (arg))
732 68631226 : continue;
733 43516043 : tree val = value_on_edge (e, arg);
734 43516043 : if (val
735 3175002 : && is_gimple_min_invariant (val)
736 45454472 : && may_propagate_copy (arg, val))
737 : {
738 1936585 : propagate_value (use_p, val);
739 1936585 : propagated = true;
740 : }
741 : }
742 : }
743 124820687 : return propagated;
744 : }
745 :
746 : edge
747 124820687 : substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
748 : {
749 124820687 : substitute_and_fold_engine->pre_fold_bb (bb);
750 :
751 : /* Propagate known values into PHI nodes. */
752 124820687 : for (gphi_iterator i = gsi_start_phis (bb);
753 171093779 : !gsi_end_p (i);
754 46273092 : gsi_next (&i))
755 : {
756 46273092 : gphi *phi = i.phi ();
757 46273092 : tree res = gimple_phi_result (phi);
758 92546184 : if (virtual_operand_p (res))
759 20722748 : continue;
760 25550344 : 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 25550344 : if (res && TREE_CODE (res) == SSA_NAME)
766 : {
767 25550344 : tree sprime = substitute_and_fold_engine->value_of_expr (res, phi);
768 27488834 : if (sprime
769 25550344 : && sprime != res
770 25550344 : && may_propagate_copy (res, sprime))
771 : {
772 1938490 : 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 1938490 : bitmap_set_bit (dceworklist, SSA_NAME_VERSION (res));
779 : /* As this now constitutes a copy duplicate points-to
780 : and range info appropriately. */
781 1938490 : if (TREE_CODE (sprime) == SSA_NAME)
782 1213181 : maybe_duplicate_ssa_info_at_copy (res, sprime);
783 1938490 : continue;
784 : }
785 : }
786 23611854 : 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 249641374 : for (gimple_stmt_iterator i = gsi_start_bb (bb);
792 1014709596 : !gsi_end_p (i);
793 889888909 : gsi_next (&i))
794 : {
795 889888909 : bool did_replace;
796 889888909 : gimple *stmt = gsi_stmt (i);
797 :
798 889888909 : substitute_and_fold_engine->pre_fold_stmt (stmt);
799 :
800 889888909 : 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 889888909 : tree lhs = gimple_get_lhs (stmt);
809 889888909 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
810 : {
811 185672507 : tree sprime = substitute_and_fold_engine->value_of_stmt (stmt, lhs);
812 201045298 : if (sprime
813 185672507 : && sprime != lhs
814 15392008 : && may_propagate_copy (lhs, sprime)
815 15390641 : && !stmt_could_throw_p (cfun, stmt)
816 201049545 : && !gimple_has_side_effects (stmt))
817 : {
818 15372791 : 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 15372791 : bitmap_set_bit (dceworklist, SSA_NAME_VERSION (lhs));
825 : /* As this now constitutes a copy duplicate points-to
826 : and range info appropriately. */
827 15372791 : if (TREE_CODE (sprime) == SSA_NAME)
828 9110102 : maybe_duplicate_ssa_info_at_copy (lhs, sprime);
829 15372791 : continue;
830 : }
831 : }
832 :
833 : /* Replace the statement with its folded version and mark it
834 : folded. */
835 874516118 : did_replace = false;
836 874516118 : gimple *old_stmt = stmt;
837 874516118 : bool was_noreturn = false;
838 874516118 : bool can_make_abnormal_goto = false;
839 874516118 : if (is_gimple_call (stmt))
840 : {
841 55459761 : was_noreturn = gimple_call_noreturn_p (stmt);
842 55459761 : can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
843 : }
844 :
845 : /* Replace real uses in the statement. */
846 874516118 : did_replace |= substitute_and_fold_engine->replace_uses_in (stmt);
847 :
848 874516118 : gimple_stmt_iterator prev_gsi = i;
849 874516118 : gsi_prev (&prev_gsi);
850 :
851 : /* If we made a replacement, fold the statement. */
852 874516118 : if (did_replace)
853 : {
854 13779814 : update_stmt (stmt);
855 13779814 : fold_stmt (&i, follow_single_use_edges);
856 13779814 : stmt = gsi_stmt (i);
857 13779814 : gimple_set_modified (stmt, true);
858 : }
859 : /* Also fold if we want to fold all statements. */
860 860736304 : else if (substitute_and_fold_engine->fold_all_stmts
861 860736304 : && 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 874516118 : update_stmt_if_modified (stmt);
872 874516118 : if (substitute_and_fold_engine->fold_stmt (&i))
873 : {
874 1819652 : did_replace = true;
875 1819652 : prop_stats.num_stmts_folded++;
876 1819652 : stmt = gsi_stmt (i);
877 1819652 : 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 874516118 : if (gimple_code (stmt) == GIMPLE_COND)
886 : {
887 44077608 : if ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE)
888 44077608 : ^ (EDGE_SUCC (bb, 1)->flags & EDGE_EXECUTABLE))
889 : {
890 490235 : if (((EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) != 0)
891 490235 : == ((EDGE_SUCC (bb, 0)->flags & EDGE_EXECUTABLE) != 0))
892 118746 : gimple_cond_make_true (as_a <gcond *> (stmt));
893 : else
894 371489 : gimple_cond_make_false (as_a <gcond *> (stmt));
895 490235 : gimple_set_modified (stmt, true);
896 490235 : did_replace = true;
897 : }
898 : }
899 :
900 : /* Now cleanup. */
901 874516118 : if (did_replace)
902 : {
903 15150895 : foreach_new_stmt_in_bb (prev_gsi, i);
904 :
905 : /* If we cleaned up EH information from the statement,
906 : remove EH edges. */
907 15150895 : if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
908 155975 : 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 15150895 : if (can_make_abnormal_goto
913 15150895 : && !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 15150895 : if (!was_noreturn
919 15018158 : && is_gimple_call (stmt)
920 16647381 : && gimple_call_noreturn_p (stmt))
921 71 : stmts_to_fixup.safe_push (stmt);
922 :
923 15150895 : if (gimple_assign_single_p (stmt))
924 : {
925 3568136 : tree rhs = gimple_assign_rhs1 (stmt);
926 :
927 3568136 : if (TREE_CODE (rhs) == ADDR_EXPR)
928 397274 : recompute_tree_invariant_for_addr_expr (rhs);
929 : }
930 :
931 : /* Determine what needs to be done to update the SSA form. */
932 15150895 : update_stmt_if_modified (stmt);
933 15150895 : if (!is_gimple_debug (stmt))
934 10966568 : something_changed = true;
935 : }
936 :
937 874516118 : 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 124820687 : something_changed |= substitute_and_fold_engine->propagate_into_phi_args (bb);
951 :
952 124820687 : 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 12596222 : substitute_and_fold_engine::substitute_and_fold (basic_block block)
979 : {
980 12596222 : if (dump_file && (dump_flags & TDF_DETAILS))
981 161 : fprintf (dump_file, "\nSubstituting values and folding statements\n\n");
982 :
983 12596222 : 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 12596222 : if (block)
991 1423 : gcc_assert (dom_info_state (CDI_DOMINATORS));
992 : else
993 12594799 : calculate_dominance_info (CDI_DOMINATORS);
994 12596222 : substitute_and_fold_dom_walker walker (CDI_DOMINATORS, this);
995 12596222 : walker.walk (block ? block : ENTRY_BLOCK_PTR_FOR_FN (cfun));
996 :
997 12596222 : simple_dce_from_worklist (walker.dceworklist, walker.need_eh_cleanup);
998 12596222 : if (!bitmap_empty_p (walker.need_eh_cleanup))
999 36878 : gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup);
1000 12596222 : 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 12596293 : 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 12596222 : statistics_counter_event (cfun, "Constants propagated",
1022 12596222 : prop_stats.num_const_prop);
1023 12596222 : statistics_counter_event (cfun, "Copies propagated",
1024 12596222 : prop_stats.num_copy_prop);
1025 12596222 : statistics_counter_event (cfun, "Statements folded",
1026 12596222 : prop_stats.num_stmts_folded);
1027 :
1028 12596222 : return walker.something_changed;
1029 12596222 : }
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 157820667 : may_propagate_copy (tree dest, tree orig, bool dest_not_abnormal_phi_edge_p)
1039 : {
1040 157820667 : tree type_d = TREE_TYPE (dest);
1041 157820667 : 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 157820667 : if (TREE_CODE (orig) == SSA_NAME
1047 109157968 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)
1048 29280 : && SSA_NAME_IS_DEFAULT_DEF (orig)
1049 157823787 : && (SSA_NAME_VAR (orig) == NULL_TREE
1050 3120 : || 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 157817950 : else if (TREE_CODE (orig) == SSA_NAME
1055 157817950 : && 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 157791387 : else if (!dest_not_abnormal_phi_edge_p
1061 80876513 : && TREE_CODE (dest) == SSA_NAME
1062 238667900 : && 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 157778509 : 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 157762186 : 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 157272078 : if (TREE_CODE (dest) == SSA_NAME
1077 157101995 : && is_gimple_call (SSA_NAME_DEF_STMT (dest))
1078 158720035 : && 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 395603 : may_propagate_copy_into_stmt (gimple *dest, tree orig)
1092 : {
1093 395603 : tree type_d;
1094 395603 : 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 395603 : if (gimple_assign_single_p (dest))
1102 184833 : return may_propagate_copy (gimple_assign_rhs1 (dest), orig, true);
1103 210770 : 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 210770 : if (TREE_CODE (orig) == SSA_NAME
1112 210770 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
1113 : return false;
1114 :
1115 210770 : if (is_gimple_assign (dest))
1116 181087 : type_d = TREE_TYPE (gimple_assign_lhs (dest));
1117 29683 : else if (gimple_code (dest) == GIMPLE_COND)
1118 21522 : type_d = boolean_type_node;
1119 8161 : else if (is_gimple_call (dest)
1120 8161 : && gimple_call_lhs (dest) != NULL_TREE)
1121 8161 : type_d = TREE_TYPE (gimple_call_lhs (dest));
1122 : else
1123 0 : gcc_unreachable ();
1124 :
1125 210770 : type_o = TREE_TYPE (orig);
1126 :
1127 210770 : 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 58238182 : replace_exp (use_operand_p op_p, tree val)
1144 : {
1145 58238182 : if (TREE_CODE (val) == SSA_NAME || CONSTANT_CLASS_P (val))
1146 54131165 : SET_USE (op_p, val);
1147 : else
1148 4107017 : SET_USE (op_p, unshare_expr (val));
1149 58238182 : }
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 50715397 : propagate_value (use_operand_p op_p, tree val)
1160 : {
1161 50715397 : if (flag_checking)
1162 : {
1163 50714939 : bool ab = (is_a <gphi *> (USE_STMT (op_p))
1164 67398535 : && (gimple_phi_arg_edge (as_a <gphi *> (USE_STMT (op_p)),
1165 16683596 : PHI_ARG_INDEX_FROM_USE (op_p))
1166 16683596 : ->flags & EDGE_ABNORMAL));
1167 50714939 : gcc_assert (may_propagate_copy (USE_FROM_PTR (op_p), val, !ab));
1168 : }
1169 50715397 : replace_exp (op_p, val);
1170 50715397 : }
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 944720 : propagate_tree_value (tree *op_p, tree val)
1183 : {
1184 944720 : if (TREE_CODE (val) == SSA_NAME)
1185 380854 : *op_p = val;
1186 : else
1187 563866 : *op_p = unshare_expr (val);
1188 944720 : }
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 944720 : propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
1199 : {
1200 944720 : gimple *stmt = gsi_stmt (*gsi);
1201 :
1202 944720 : if (is_gimple_assign (stmt))
1203 : {
1204 877033 : tree expr = NULL_TREE;
1205 877033 : if (gimple_assign_single_p (stmt))
1206 676026 : expr = gimple_assign_rhs1 (stmt);
1207 877033 : propagate_tree_value (&expr, val);
1208 877033 : gimple_assign_set_rhs_from_tree (gsi, expr);
1209 : }
1210 67687 : else if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1211 : {
1212 55226 : tree lhs = NULL_TREE;
1213 55226 : tree rhs = build_zero_cst (TREE_TYPE (val));
1214 55226 : propagate_tree_value (&lhs, val);
1215 55226 : gimple_cond_set_code (cond_stmt, NE_EXPR);
1216 55226 : gimple_cond_set_lhs (cond_stmt, lhs);
1217 55226 : gimple_cond_set_rhs (cond_stmt, rhs);
1218 : }
1219 12461 : else if (is_gimple_call (stmt)
1220 12461 : && gimple_call_lhs (stmt) != NULL_TREE)
1221 : {
1222 12461 : tree expr = NULL_TREE;
1223 12461 : propagate_tree_value (&expr, val);
1224 12461 : 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 944720 : }
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 247687 : clean_up_loop_closed_phi (function *fun)
1237 : {
1238 247687 : gphi *phi;
1239 247687 : tree rhs;
1240 247687 : tree lhs;
1241 247687 : gphi_iterator gsi;
1242 :
1243 : /* Avoid possibly quadratic work when scanning for loop exits across
1244 : all loops of a nest. */
1245 247687 : 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 247687 : calculate_dominance_info (CDI_DOMINATORS);
1251 :
1252 : /* Walk over loop in function. */
1253 1384670 : for (auto loop : loops_list (fun, 0))
1254 : {
1255 : /* Check each exit edege of loop. */
1256 641609 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1257 3104634 : for (edge e : exits)
1258 1986113 : if (single_pred_p (e->dest))
1259 : /* Walk over loop-closed PHIs. */
1260 1724034 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);)
1261 : {
1262 930600 : phi = gsi.phi ();
1263 930600 : rhs = gimple_phi_arg_def (phi, 0);
1264 930600 : lhs = gimple_phi_result (phi);
1265 :
1266 1860250 : if (virtual_operand_p (rhs))
1267 : {
1268 497419 : imm_use_iterator iter;
1269 497419 : use_operand_p use_p;
1270 497419 : gimple *stmt;
1271 :
1272 1207281 : FOR_EACH_IMM_USE_STMT (stmt, iter, lhs)
1273 1433608 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1274 716804 : SET_USE (use_p, rhs);
1275 :
1276 497419 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1277 48 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
1278 497419 : remove_phi_node (&gsi, true);
1279 : }
1280 433181 : else if (may_propagate_copy (lhs, rhs))
1281 : {
1282 : /* Dump details. */
1283 433131 : 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 433131 : replace_uses_by (lhs, rhs);
1293 433131 : remove_phi_node (&gsi, true);
1294 : }
1295 : else
1296 50 : gsi_next (&gsi);
1297 : }
1298 641609 : }
1299 :
1300 247687 : return 0;
1301 : }
|
