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

source code of gcc/tree-ssa-propagate.cc