1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004-2019 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
28 #include "gimple-pretty-print.h"
30 #include "gimple-fold.h"
33 #include "gimple-iterator.h"
36 #include "tree-ssa-propagate.h"
39 #include "tree-cfgcleanup.h"
42 /* This file implements a generic value propagation engine based on
43 the same propagation used by the SSA-CCP algorithm [1].
45 Propagation is performed by simulating the execution of every
46 statement that produces the value being propagated. Simulation
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).
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
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.
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
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
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
79 4- Three work lists are kept. Statements are only added to these
80 lists if they produce one of SSA_PROP_INTERESTING or
83 CFG_BLOCKS contains the list of blocks to be simulated.
84 Blocks are added to this list if their incoming edges are
87 SSA_EDGE_WORKLIST contains the list of statements that we
90 5- Simulation terminates when all three work lists are drained.
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.
97 It is also important to compute def-use information before calling
102 [1] Constant propagation with conditional branches,
103 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
105 [2] Building an Optimizing Compiler,
106 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
108 [3] Advanced Compiler Design and Implementation,
109 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
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 bitmap cfg_blocks_back
;
117 static int *bb_to_cfg_order
;
118 static int *cfg_order_to_bb
;
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. */
125 static bitmap ssa_edge_worklist
;
126 static bitmap ssa_edge_worklist_back
;
127 static vec
<gimple
*> uid_to_stmt
;
129 /* Current RPO index in the iteration. */
130 static int curr_order
;
133 /* We have just defined a new value for VAR. If IS_VARYING is true,
134 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
135 them to INTERESTING_SSA_EDGES. */
138 add_ssa_edge (tree var
)
140 imm_use_iterator iter
;
143 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
145 gimple
*use_stmt
= USE_STMT (use_p
);
146 if (!prop_simulate_again_p (use_stmt
))
149 /* If we did not yet simulate the block wait for this to happen
150 and do not add the stmt to the SSA edge worklist. */
151 basic_block use_bb
= gimple_bb (use_stmt
);
152 if (! (use_bb
->flags
& BB_VISITED
))
155 /* If this is a use on a not yet executable edge do not bother to
157 if (gimple_code (use_stmt
) == GIMPLE_PHI
158 && !(EDGE_PRED (use_bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->flags
163 if (bb_to_cfg_order
[gimple_bb (use_stmt
)->index
] < curr_order
)
164 worklist
= ssa_edge_worklist_back
;
166 worklist
= ssa_edge_worklist
;
167 if (bitmap_set_bit (worklist
, gimple_uid (use_stmt
)))
169 uid_to_stmt
[gimple_uid (use_stmt
)] = use_stmt
;
170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
172 fprintf (dump_file
, "ssa_edge_worklist: adding SSA use in ");
173 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_SLIM
);
180 /* Add edge E to the control flow worklist. */
183 add_control_edge (edge e
)
185 basic_block bb
= e
->dest
;
186 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
189 /* If the edge had already been executed, skip it. */
190 if (e
->flags
& EDGE_EXECUTABLE
)
193 e
->flags
|= EDGE_EXECUTABLE
;
195 int bb_order
= bb_to_cfg_order
[bb
->index
];
196 if (bb_order
< curr_order
)
197 bitmap_set_bit (cfg_blocks_back
, bb_order
);
199 bitmap_set_bit (cfg_blocks
, bb_order
);
201 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
202 fprintf (dump_file
, "Adding destination of edge (%d -> %d) to worklist\n",
203 e
->src
->index
, e
->dest
->index
);
207 /* Simulate the execution of STMT and update the work lists accordingly. */
210 ssa_propagation_engine::simulate_stmt (gimple
*stmt
)
212 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
213 edge taken_edge
= NULL
;
214 tree output_name
= NULL_TREE
;
216 /* Pull the stmt off the SSA edge worklist. */
217 bitmap_clear_bit (ssa_edge_worklist
, gimple_uid (stmt
));
219 /* Don't bother visiting statements that are already
220 considered varying by the propagator. */
221 if (!prop_simulate_again_p (stmt
))
224 if (gimple_code (stmt
) == GIMPLE_PHI
)
226 val
= visit_phi (as_a
<gphi
*> (stmt
));
227 output_name
= gimple_phi_result (stmt
);
230 val
= visit_stmt (stmt
, &taken_edge
, &output_name
);
232 if (val
== SSA_PROP_VARYING
)
234 prop_set_simulate_again (stmt
, false);
236 /* If the statement produced a new varying value, add the SSA
237 edges coming out of OUTPUT_NAME. */
239 add_ssa_edge (output_name
);
241 /* If STMT transfers control out of its basic block, add
242 all outgoing edges to the work list. */
243 if (stmt_ends_bb_p (stmt
))
247 basic_block bb
= gimple_bb (stmt
);
248 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
249 add_control_edge (e
);
253 else if (val
== SSA_PROP_INTERESTING
)
255 /* If the statement produced new value, add the SSA edges coming
256 out of OUTPUT_NAME. */
258 add_ssa_edge (output_name
);
260 /* If we know which edge is going to be taken out of this block,
261 add it to the CFG work list. */
263 add_control_edge (taken_edge
);
266 /* If there are no SSA uses on the stmt whose defs are simulated
267 again then this stmt will be never visited again. */
268 bool has_simulate_again_uses
= false;
271 if (gimple_code (stmt
) == GIMPLE_PHI
)
276 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
277 if (!(e
->flags
& EDGE_EXECUTABLE
)
278 || ((arg
= PHI_ARG_DEF_FROM_EDGE (stmt
, e
))
279 && TREE_CODE (arg
) == SSA_NAME
280 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
281 && prop_simulate_again_p (SSA_NAME_DEF_STMT (arg
))))
283 has_simulate_again_uses
= true;
288 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
290 gimple
*def_stmt
= SSA_NAME_DEF_STMT (USE_FROM_PTR (use_p
));
291 if (!gimple_nop_p (def_stmt
)
292 && prop_simulate_again_p (def_stmt
))
294 has_simulate_again_uses
= true;
298 if (!has_simulate_again_uses
)
300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
301 fprintf (dump_file
, "marking stmt to be not simulated again\n");
302 prop_set_simulate_again (stmt
, false);
307 /* Simulate the execution of BLOCK. Evaluate the statement associated
308 with each variable reference inside the block. */
311 ssa_propagation_engine::simulate_block (basic_block block
)
313 gimple_stmt_iterator gsi
;
315 /* There is nothing to do for the exit block. */
316 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
320 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
322 /* Always simulate PHI nodes, even if we have simulated this block
324 for (gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
325 simulate_stmt (gsi_stmt (gsi
));
327 /* If this is the first time we've simulated this block, then we
328 must simulate each of its statements. */
329 if (! (block
->flags
& BB_VISITED
))
331 gimple_stmt_iterator j
;
332 unsigned int normal_edge_count
;
336 for (j
= gsi_start_bb (block
); !gsi_end_p (j
); gsi_next (&j
))
337 simulate_stmt (gsi_stmt (j
));
339 /* Note that we have simulated this block. */
340 block
->flags
|= BB_VISITED
;
342 /* We cannot predict when abnormal and EH edges will be executed, so
343 once a block is considered executable, we consider any
344 outgoing abnormal edges as executable.
346 TODO: This is not exactly true. Simplifying statement might
347 prove it non-throwing and also computed goto can be handled
348 when destination is known.
350 At the same time, if this block has only one successor that is
351 reached by non-abnormal edges, then add that successor to the
353 normal_edge_count
= 0;
355 FOR_EACH_EDGE (e
, ei
, block
->succs
)
357 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
358 add_control_edge (e
);
366 if (normal_edge_count
== 1)
367 add_control_edge (normal_edge
);
372 /* Initialize local data structures and work lists. */
381 /* Worklists of SSA edges. */
382 ssa_edge_worklist
= BITMAP_ALLOC (NULL
);
383 ssa_edge_worklist_back
= BITMAP_ALLOC (NULL
);
384 bitmap_tree_view (ssa_edge_worklist
);
385 bitmap_tree_view (ssa_edge_worklist_back
);
387 /* Worklist of basic-blocks. */
388 bb_to_cfg_order
= XNEWVEC (int, last_basic_block_for_fn (cfun
) + 1);
389 cfg_order_to_bb
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
390 int n
= pre_and_rev_post_order_compute_fn (cfun
, NULL
,
391 cfg_order_to_bb
, false);
392 for (int i
= 0; i
< n
; ++i
)
393 bb_to_cfg_order
[cfg_order_to_bb
[i
]] = i
;
394 cfg_blocks
= BITMAP_ALLOC (NULL
);
395 cfg_blocks_back
= BITMAP_ALLOC (NULL
);
397 /* Initially assume that every edge in the CFG is not executable.
398 (including the edges coming out of the entry block). Mark blocks
399 as not visited, blocks not yet visited will have all their statements
400 simulated once an incoming edge gets executable. */
401 set_gimple_stmt_max_uid (cfun
, 0);
402 for (int i
= 0; i
< n
; ++i
)
404 gimple_stmt_iterator si
;
405 bb
= BASIC_BLOCK_FOR_FN (cfun
, cfg_order_to_bb
[i
]);
407 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
409 gimple
*stmt
= gsi_stmt (si
);
410 gimple_set_uid (stmt
, inc_gimple_stmt_max_uid (cfun
));
413 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
415 gimple
*stmt
= gsi_stmt (si
);
416 gimple_set_uid (stmt
, inc_gimple_stmt_max_uid (cfun
));
419 bb
->flags
&= ~BB_VISITED
;
420 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
421 e
->flags
&= ~EDGE_EXECUTABLE
;
423 uid_to_stmt
.safe_grow (gimple_stmt_max_uid (cfun
));
425 /* Seed the algorithm by adding the successors of the entry block to the
427 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
429 e
->flags
&= ~EDGE_EXECUTABLE
;
430 add_control_edge (e
);
435 /* Free allocated storage. */
440 BITMAP_FREE (cfg_blocks
);
441 BITMAP_FREE (cfg_blocks_back
);
442 free (bb_to_cfg_order
);
443 free (cfg_order_to_bb
);
444 BITMAP_FREE (ssa_edge_worklist
);
445 BITMAP_FREE (ssa_edge_worklist_back
);
446 uid_to_stmt
.release ();
450 /* Return true if EXPR is an acceptable right-hand-side for a
451 GIMPLE assignment. We validate the entire tree, not just
452 the root node, thus catching expressions that embed complex
453 operands that are not permitted in GIMPLE. This function
454 is needed because the folding routines in fold-const.c
455 may return such expressions in some cases, e.g., an array
456 access with an embedded index addition. It may make more
457 sense to have folding routines that are sensitive to the
458 constraints on GIMPLE operands, rather than abandoning any
459 any attempt to fold if the usual folding turns out to be too
463 valid_gimple_rhs_p (tree expr
)
465 enum tree_code code
= TREE_CODE (expr
);
467 switch (TREE_CODE_CLASS (code
))
469 case tcc_declaration
:
470 if (!is_gimple_variable (expr
))
475 /* All constants are ok. */
479 /* GENERIC allows comparisons with non-boolean types, reject
480 those for GIMPLE. Let vector-typed comparisons pass - rules
481 for GENERIC and GIMPLE are the same here. */
482 if (!(INTEGRAL_TYPE_P (TREE_TYPE (expr
))
483 && (TREE_CODE (TREE_TYPE (expr
)) == BOOLEAN_TYPE
484 || TYPE_PRECISION (TREE_TYPE (expr
)) == 1))
485 && ! VECTOR_TYPE_P (TREE_TYPE (expr
)))
490 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
491 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
496 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
506 if (is_gimple_min_invariant (expr
))
508 t
= TREE_OPERAND (expr
, 0);
509 while (handled_component_p (t
))
511 /* ??? More checks needed, see the GIMPLE verifier. */
512 if ((TREE_CODE (t
) == ARRAY_REF
513 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
514 && !is_gimple_val (TREE_OPERAND (t
, 1)))
516 t
= TREE_OPERAND (t
, 0);
518 if (!is_gimple_id (t
))
524 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
526 if (((code
== VEC_COND_EXPR
|| code
== COND_EXPR
)
527 ? !is_gimple_condexpr (TREE_OPERAND (expr
, 0))
528 : !is_gimple_val (TREE_OPERAND (expr
, 0)))
529 || !is_gimple_val (TREE_OPERAND (expr
, 1))
530 || !is_gimple_val (TREE_OPERAND (expr
, 2)))
541 case tcc_exceptional
:
542 if (code
== CONSTRUCTOR
)
546 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (expr
), i
, elt
)
547 if (!is_gimple_val (elt
))
551 if (code
!= SSA_NAME
)
556 if (code
== BIT_FIELD_REF
)
557 return is_gimple_val (TREE_OPERAND (expr
, 0));
568 /* Return true if EXPR is a CALL_EXPR suitable for representation
569 as a single GIMPLE_CALL statement. If the arguments require
570 further gimplification, return false. */
573 valid_gimple_call_p (tree expr
)
577 if (TREE_CODE (expr
) != CALL_EXPR
)
580 nargs
= call_expr_nargs (expr
);
581 for (i
= 0; i
< nargs
; i
++)
583 tree arg
= CALL_EXPR_ARG (expr
, i
);
584 if (is_gimple_reg_type (TREE_TYPE (arg
)))
586 if (!is_gimple_val (arg
))
590 if (!is_gimple_lvalue (arg
))
598 /* Make SSA names defined by OLD_STMT point to NEW_STMT
599 as their defining statement. */
602 move_ssa_defining_stmt_for_defs (gimple
*new_stmt
, gimple
*old_stmt
)
607 if (gimple_in_ssa_p (cfun
))
609 /* Make defined SSA_NAMEs point to the new
610 statement as their definition. */
611 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
613 if (TREE_CODE (var
) == SSA_NAME
)
614 SSA_NAME_DEF_STMT (var
) = new_stmt
;
619 /* Helper function for update_gimple_call and update_call_from_tree.
620 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
623 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple
*new_stmt
,
626 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
627 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
628 gimple_move_vops (new_stmt
, stmt
);
629 gimple_set_location (new_stmt
, gimple_location (stmt
));
630 if (gimple_block (new_stmt
) == NULL_TREE
)
631 gimple_set_block (new_stmt
, gimple_block (stmt
));
632 gsi_replace (si_p
, new_stmt
, false);
635 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
636 with number of arguments NARGS, where the arguments in GIMPLE form
637 follow NARGS argument. */
640 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
643 gcall
*new_stmt
, *stmt
= as_a
<gcall
*> (gsi_stmt (*si_p
));
645 gcc_assert (is_gimple_call (stmt
));
646 va_start (ap
, nargs
);
647 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
648 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
653 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
654 value of EXPR, which is expected to be the result of folding the
655 call. This can only be done if EXPR is a CALL_EXPR with valid
656 GIMPLE operands as arguments, or if it is a suitable RHS expression
657 for a GIMPLE_ASSIGN. More complex expressions will require
658 gimplification, which will introduce additional statements. In this
659 event, no update is performed, and the function returns false.
660 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
661 replace the statement at *SI_P with an entirely new statement.
662 The new statement need not be a call, e.g., if the original call
663 folded to a constant. */
666 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
668 gimple
*stmt
= gsi_stmt (*si_p
);
670 if (valid_gimple_call_p (expr
))
672 /* The call has simplified to another call. */
673 tree fn
= CALL_EXPR_FN (expr
);
675 unsigned nargs
= call_expr_nargs (expr
);
676 vec
<tree
> args
= vNULL
;
682 args
.safe_grow_cleared (nargs
);
684 for (i
= 0; i
< nargs
; i
++)
685 args
[i
] = CALL_EXPR_ARG (expr
, i
);
688 new_stmt
= gimple_build_call_vec (fn
, args
);
689 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
694 else if (valid_gimple_rhs_p (expr
))
696 tree lhs
= gimple_call_lhs (stmt
);
699 /* The call has simplified to an expression
700 that cannot be represented as a GIMPLE_CALL. */
703 /* A value is expected.
704 Introduce a new GIMPLE_ASSIGN statement. */
705 STRIP_USELESS_TYPE_CONVERSION (expr
);
706 new_stmt
= gimple_build_assign (lhs
, expr
);
707 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
708 gimple_move_vops (new_stmt
, stmt
);
710 else if (!TREE_SIDE_EFFECTS (expr
))
712 /* No value is expected, and EXPR has no effect.
713 Replace it with an empty statement. */
714 new_stmt
= gimple_build_nop ();
715 if (gimple_in_ssa_p (cfun
))
717 unlink_stmt_vdef (stmt
);
723 /* No value is expected, but EXPR has an effect,
724 e.g., it could be a reference to a volatile
725 variable. Create an assignment statement
726 with a dummy (unused) lhs variable. */
727 STRIP_USELESS_TYPE_CONVERSION (expr
);
728 if (gimple_in_ssa_p (cfun
))
729 lhs
= make_ssa_name (TREE_TYPE (expr
));
731 lhs
= create_tmp_var (TREE_TYPE (expr
));
732 new_stmt
= gimple_build_assign (lhs
, expr
);
733 gimple_move_vops (new_stmt
, stmt
);
734 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
736 gimple_set_location (new_stmt
, gimple_location (stmt
));
737 gsi_replace (si_p
, new_stmt
, false);
741 /* The call simplified to an expression that is
742 not a valid GIMPLE RHS. */
746 /* Entry point to the propagation engine.
748 The VISIT_STMT virtual function is called for every statement
749 visited and the VISIT_PHI virtual function is called for every PHI
753 ssa_propagation_engine::ssa_propagate (void)
759 /* Iterate until the worklists are empty. We iterate both blocks
760 and stmts in RPO order, using sets of two worklists to first
761 complete the current iteration before iterating over backedges. */
764 int next_block_order
= (bitmap_empty_p (cfg_blocks
)
765 ? -1 : bitmap_first_set_bit (cfg_blocks
));
766 int next_stmt_uid
= (bitmap_empty_p (ssa_edge_worklist
)
767 ? -1 : bitmap_first_set_bit (ssa_edge_worklist
));
768 if (next_block_order
== -1 && next_stmt_uid
== -1)
770 if (bitmap_empty_p (cfg_blocks_back
)
771 && bitmap_empty_p (ssa_edge_worklist_back
))
774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
775 fprintf (dump_file
, "Regular worklists empty, now processing "
776 "backedge destinations\n");
777 std::swap (cfg_blocks
, cfg_blocks_back
);
778 std::swap (ssa_edge_worklist
, ssa_edge_worklist_back
);
782 int next_stmt_bb_order
= -1;
783 gimple
*next_stmt
= NULL
;
784 if (next_stmt_uid
!= -1)
786 next_stmt
= uid_to_stmt
[next_stmt_uid
];
787 next_stmt_bb_order
= bb_to_cfg_order
[gimple_bb (next_stmt
)->index
];
790 /* Pull the next block to simulate off the worklist if it comes first. */
791 if (next_block_order
!= -1
792 && (next_stmt_bb_order
== -1
793 || next_block_order
<= next_stmt_bb_order
))
795 curr_order
= next_block_order
;
796 bitmap_clear_bit (cfg_blocks
, next_block_order
);
798 = BASIC_BLOCK_FOR_FN (cfun
, cfg_order_to_bb
[next_block_order
]);
801 /* Else simulate from the SSA edge worklist. */
804 curr_order
= next_stmt_bb_order
;
805 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
807 fprintf (dump_file
, "\nSimulating statement: ");
808 print_gimple_stmt (dump_file
, next_stmt
, 0, dump_flags
);
810 simulate_stmt (next_stmt
);
818 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
819 is a non-volatile pointer dereference, a structure reference or a
820 reference to a single _DECL. Ignore volatile memory references
821 because they are not interesting for the optimizers. */
824 stmt_makes_single_store (gimple
*stmt
)
828 if (gimple_code (stmt
) != GIMPLE_ASSIGN
829 && gimple_code (stmt
) != GIMPLE_CALL
)
832 if (!gimple_vdef (stmt
))
835 lhs
= gimple_get_lhs (stmt
);
837 /* A call statement may have a null LHS. */
841 return (!TREE_THIS_VOLATILE (lhs
)
843 || REFERENCE_CLASS_P (lhs
)));
847 /* Propagation statistics. */
852 long num_stmts_folded
;
856 static struct prop_stats_d prop_stats
;
858 /* Replace USE references in statement STMT with the values stored in
859 PROP_VALUE. Return true if at least one reference was replaced. */
862 substitute_and_fold_engine::replace_uses_in (gimple
*stmt
)
864 bool replaced
= false;
868 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
870 tree tuse
= USE_FROM_PTR (use
);
871 tree val
= get_value (tuse
);
873 if (val
== tuse
|| val
== NULL_TREE
)
876 if (gimple_code (stmt
) == GIMPLE_ASM
877 && !may_propagate_copy_into_asm (tuse
))
880 if (!may_propagate_copy (tuse
, val
))
883 if (TREE_CODE (val
) != SSA_NAME
)
884 prop_stats
.num_const_prop
++;
886 prop_stats
.num_copy_prop
++;
888 propagate_value (use
, val
);
897 /* Replace propagated values into all the arguments for PHI using the
898 values from PROP_VALUE. */
901 substitute_and_fold_engine::replace_phi_args_in (gphi
*phi
)
904 bool replaced
= false;
906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
908 fprintf (dump_file
, "Folding PHI node: ");
909 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
912 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
914 tree arg
= gimple_phi_arg_def (phi
, i
);
916 if (TREE_CODE (arg
) == SSA_NAME
)
918 tree val
= get_value (arg
);
920 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
922 edge e
= gimple_phi_arg_edge (phi
, i
);
924 if (TREE_CODE (val
) != SSA_NAME
)
925 prop_stats
.num_const_prop
++;
927 prop_stats
.num_copy_prop
++;
929 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
932 /* If we propagated a copy and this argument flows
933 through an abnormal edge, update the replacement
935 if (TREE_CODE (val
) == SSA_NAME
936 && e
->flags
& EDGE_ABNORMAL
937 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
))
939 /* This can only occur for virtual operands, since
940 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
941 would prevent replacement. */
942 gcc_checking_assert (virtual_operand_p (val
));
943 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
952 fprintf (dump_file
, "No folding possible\n");
955 fprintf (dump_file
, "Folded into: ");
956 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
957 fprintf (dump_file
, "\n");
965 class substitute_and_fold_dom_walker
: public dom_walker
968 substitute_and_fold_dom_walker (cdi_direction direction
,
969 class substitute_and_fold_engine
*engine
)
970 : dom_walker (direction
),
971 something_changed (false),
972 substitute_and_fold_engine (engine
)
974 stmts_to_remove
.create (0);
975 stmts_to_fixup
.create (0);
976 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
978 ~substitute_and_fold_dom_walker ()
980 stmts_to_remove
.release ();
981 stmts_to_fixup
.release ();
982 BITMAP_FREE (need_eh_cleanup
);
985 virtual edge
before_dom_children (basic_block
);
986 virtual void after_dom_children (basic_block
) {}
988 bool something_changed
;
989 vec
<gimple
*> stmts_to_remove
;
990 vec
<gimple
*> stmts_to_fixup
;
991 bitmap need_eh_cleanup
;
993 class substitute_and_fold_engine
*substitute_and_fold_engine
;
997 substitute_and_fold_dom_walker::before_dom_children (basic_block bb
)
999 /* Propagate known values into PHI nodes. */
1000 for (gphi_iterator i
= gsi_start_phis (bb
);
1004 gphi
*phi
= i
.phi ();
1005 tree res
= gimple_phi_result (phi
);
1006 if (virtual_operand_p (res
))
1008 if (res
&& TREE_CODE (res
) == SSA_NAME
)
1010 tree sprime
= substitute_and_fold_engine
->get_value (res
);
1013 && may_propagate_copy (res
, sprime
))
1015 stmts_to_remove
.safe_push (phi
);
1019 something_changed
|= substitute_and_fold_engine
->replace_phi_args_in (phi
);
1022 /* Propagate known values into stmts. In some case it exposes
1023 more trivially deletable stmts to walk backward. */
1024 for (gimple_stmt_iterator i
= gsi_start_bb (bb
);
1029 gimple
*stmt
= gsi_stmt (i
);
1031 /* No point propagating into a stmt we have a value for we
1032 can propagate into all uses. Mark it for removal instead. */
1033 tree lhs
= gimple_get_lhs (stmt
);
1034 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1036 tree sprime
= substitute_and_fold_engine
->get_value (lhs
);
1039 && may_propagate_copy (lhs
, sprime
)
1040 && !stmt_could_throw_p (cfun
, stmt
)
1041 && !gimple_has_side_effects (stmt
)
1042 /* We have to leave ASSERT_EXPRs around for jump-threading. */
1043 && (!is_gimple_assign (stmt
)
1044 || gimple_assign_rhs_code (stmt
) != ASSERT_EXPR
))
1046 stmts_to_remove
.safe_push (stmt
);
1051 /* Replace the statement with its folded version and mark it
1053 did_replace
= false;
1054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1056 fprintf (dump_file
, "Folding statement: ");
1057 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1060 gimple
*old_stmt
= stmt
;
1061 bool was_noreturn
= (is_gimple_call (stmt
)
1062 && gimple_call_noreturn_p (stmt
));
1064 /* Replace real uses in the statement. */
1065 did_replace
|= substitute_and_fold_engine
->replace_uses_in (stmt
);
1067 /* If we made a replacement, fold the statement. */
1070 fold_stmt (&i
, follow_single_use_edges
);
1071 stmt
= gsi_stmt (i
);
1072 gimple_set_modified (stmt
, true);
1075 /* Some statements may be simplified using propagator
1076 specific information. Do this before propagating
1077 into the stmt to not disturb pass specific information. */
1078 update_stmt_if_modified (stmt
);
1079 if (substitute_and_fold_engine
->fold_stmt(&i
))
1082 prop_stats
.num_stmts_folded
++;
1083 stmt
= gsi_stmt (i
);
1084 gimple_set_modified (stmt
, true);
1087 /* If this is a control statement the propagator left edges
1088 unexecuted on force the condition in a way consistent with
1089 that. See PR66945 for cases where the propagator can end
1090 up with a different idea of a taken edge than folding
1091 (once undefined behavior is involved). */
1092 if (gimple_code (stmt
) == GIMPLE_COND
)
1094 if ((EDGE_SUCC (bb
, 0)->flags
& EDGE_EXECUTABLE
)
1095 ^ (EDGE_SUCC (bb
, 1)->flags
& EDGE_EXECUTABLE
))
1097 if (((EDGE_SUCC (bb
, 0)->flags
& EDGE_TRUE_VALUE
) != 0)
1098 == ((EDGE_SUCC (bb
, 0)->flags
& EDGE_EXECUTABLE
) != 0))
1099 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
1101 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
1102 gimple_set_modified (stmt
, true);
1110 /* If we cleaned up EH information from the statement,
1112 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1113 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1115 /* If we turned a not noreturn call into a noreturn one
1116 schedule it for fixup. */
1118 && is_gimple_call (stmt
)
1119 && gimple_call_noreturn_p (stmt
))
1120 stmts_to_fixup
.safe_push (stmt
);
1122 if (gimple_assign_single_p (stmt
))
1124 tree rhs
= gimple_assign_rhs1 (stmt
);
1126 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1127 recompute_tree_invariant_for_addr_expr (rhs
);
1130 /* Determine what needs to be done to update the SSA form. */
1131 update_stmt_if_modified (stmt
);
1132 if (!is_gimple_debug (stmt
))
1133 something_changed
= true;
1136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1140 fprintf (dump_file
, "Folded into: ");
1141 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1142 fprintf (dump_file
, "\n");
1145 fprintf (dump_file
, "Not folded\n");
1153 /* Perform final substitution and folding of propagated values.
1154 Process the whole function if BLOCK is null, otherwise only
1155 process the blocks that BLOCK dominates. In the latter case,
1156 it is the caller's responsibility to ensure that dominator
1157 information is available and up-to-date.
1159 PROP_VALUE[I] contains the single value that should be substituted
1160 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1163 If FOLD_FN is non-NULL the function will be invoked on all statements
1164 before propagating values for pass specific simplification.
1166 DO_DCE is true if trivially dead stmts can be removed.
1168 If DO_DCE is true, the statements within a BB are walked from
1169 last to first element. Otherwise we scan from first to last element.
1171 Return TRUE when something changed. */
1174 substitute_and_fold_engine::substitute_and_fold (basic_block block
)
1176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1177 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1179 memset (&prop_stats
, 0, sizeof (prop_stats
));
1181 /* Don't call calculate_dominance_info when iterating over a subgraph.
1182 Callers that are using the interface this way are likely to want to
1183 iterate over several disjoint subgraphs, and it would be expensive
1184 in enable-checking builds to revalidate the whole dominance tree
1187 gcc_assert (dom_info_state (CDI_DOMINATORS
));
1189 calculate_dominance_info (CDI_DOMINATORS
);
1190 substitute_and_fold_dom_walker
walker (CDI_DOMINATORS
, this);
1191 walker
.walk (block
? block
: ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1193 /* We cannot remove stmts during the BB walk, especially not release
1194 SSA names there as that destroys the lattice of our callers.
1195 Remove stmts in reverse order to make debug stmt creation possible. */
1196 while (!walker
.stmts_to_remove
.is_empty ())
1198 gimple
*stmt
= walker
.stmts_to_remove
.pop ();
1199 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1201 fprintf (dump_file
, "Removing dead stmt ");
1202 print_gimple_stmt (dump_file
, stmt
, 0);
1203 fprintf (dump_file
, "\n");
1205 prop_stats
.num_dce
++;
1206 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1207 if (gimple_code (stmt
) == GIMPLE_PHI
)
1208 remove_phi_node (&gsi
, true);
1211 unlink_stmt_vdef (stmt
);
1212 gsi_remove (&gsi
, true);
1213 release_defs (stmt
);
1217 if (!bitmap_empty_p (walker
.need_eh_cleanup
))
1218 gimple_purge_all_dead_eh_edges (walker
.need_eh_cleanup
);
1220 /* Fixup stmts that became noreturn calls. This may require splitting
1221 blocks and thus isn't possible during the dominator walk. Do this
1222 in reverse order so we don't inadvertedly remove a stmt we want to
1223 fixup by visiting a dominating now noreturn call first. */
1224 while (!walker
.stmts_to_fixup
.is_empty ())
1226 gimple
*stmt
= walker
.stmts_to_fixup
.pop ();
1227 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1229 fprintf (dump_file
, "Fixing up noreturn call ");
1230 print_gimple_stmt (dump_file
, stmt
, 0);
1231 fprintf (dump_file
, "\n");
1233 fixup_noreturn_call (stmt
);
1236 statistics_counter_event (cfun
, "Constants propagated",
1237 prop_stats
.num_const_prop
);
1238 statistics_counter_event (cfun
, "Copies propagated",
1239 prop_stats
.num_copy_prop
);
1240 statistics_counter_event (cfun
, "Statements folded",
1241 prop_stats
.num_stmts_folded
);
1242 statistics_counter_event (cfun
, "Statements deleted",
1243 prop_stats
.num_dce
);
1245 return walker
.something_changed
;
1249 /* Return true if we may propagate ORIG into DEST, false otherwise. */
1252 may_propagate_copy (tree dest
, tree orig
)
1254 tree type_d
= TREE_TYPE (dest
);
1255 tree type_o
= TREE_TYPE (orig
);
1257 /* If ORIG is a default definition which flows in from an abnormal edge
1258 then the copy can be propagated. It is important that we do so to avoid
1259 uninitialized copies. */
1260 if (TREE_CODE (orig
) == SSA_NAME
1261 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
)
1262 && SSA_NAME_IS_DEFAULT_DEF (orig
)
1263 && (SSA_NAME_VAR (orig
) == NULL_TREE
1264 || TREE_CODE (SSA_NAME_VAR (orig
)) == VAR_DECL
))
1266 /* Otherwise if ORIG just flows in from an abnormal edge then the copy cannot
1268 else if (TREE_CODE (orig
) == SSA_NAME
1269 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
))
1271 /* Similarly if DEST flows in from an abnormal edge then the copy cannot be
1273 else if (TREE_CODE (dest
) == SSA_NAME
1274 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest
))
1277 /* Do not copy between types for which we *do* need a conversion. */
1278 if (!useless_type_conversion_p (type_d
, type_o
))
1281 /* Generally propagating virtual operands is not ok as that may
1282 create overlapping life-ranges. */
1283 if (TREE_CODE (dest
) == SSA_NAME
&& virtual_operand_p (dest
))
1286 /* Anything else is OK. */
1290 /* Like may_propagate_copy, but use as the destination expression
1291 the principal expression (typically, the RHS) contained in
1292 statement DEST. This is more efficient when working with the
1293 gimple tuples representation. */
1296 may_propagate_copy_into_stmt (gimple
*dest
, tree orig
)
1301 /* If the statement is a switch or a single-rhs assignment,
1302 then the expression to be replaced by the propagation may
1303 be an SSA_NAME. Fortunately, there is an explicit tree
1304 for the expression, so we delegate to may_propagate_copy. */
1306 if (gimple_assign_single_p (dest
))
1307 return may_propagate_copy (gimple_assign_rhs1 (dest
), orig
);
1308 else if (gswitch
*dest_swtch
= dyn_cast
<gswitch
*> (dest
))
1309 return may_propagate_copy (gimple_switch_index (dest_swtch
), orig
);
1311 /* In other cases, the expression is not materialized, so there
1312 is no destination to pass to may_propagate_copy. On the other
1313 hand, the expression cannot be an SSA_NAME, so the analysis
1316 if (TREE_CODE (orig
) == SSA_NAME
1317 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
))
1320 if (is_gimple_assign (dest
))
1321 type_d
= TREE_TYPE (gimple_assign_lhs (dest
));
1322 else if (gimple_code (dest
) == GIMPLE_COND
)
1323 type_d
= boolean_type_node
;
1324 else if (is_gimple_call (dest
)
1325 && gimple_call_lhs (dest
) != NULL_TREE
)
1326 type_d
= TREE_TYPE (gimple_call_lhs (dest
));
1330 type_o
= TREE_TYPE (orig
);
1332 if (!useless_type_conversion_p (type_d
, type_o
))
1338 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
1341 may_propagate_copy_into_asm (tree dest ATTRIBUTE_UNUSED
)
1347 /* Common code for propagate_value and replace_exp.
1349 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
1350 replacement is done to propagate a value or not. */
1353 replace_exp_1 (use_operand_p op_p
, tree val
,
1354 bool for_propagation ATTRIBUTE_UNUSED
)
1358 tree op
= USE_FROM_PTR (op_p
);
1359 gcc_assert (!(for_propagation
1360 && TREE_CODE (op
) == SSA_NAME
1361 && TREE_CODE (val
) == SSA_NAME
1362 && !may_propagate_copy (op
, val
)));
1365 if (TREE_CODE (val
) == SSA_NAME
)
1366 SET_USE (op_p
, val
);
1368 SET_USE (op_p
, unshare_expr (val
));
1372 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1373 into the operand pointed to by OP_P.
1375 Use this version for const/copy propagation as it will perform additional
1376 checks to ensure validity of the const/copy propagation. */
1379 propagate_value (use_operand_p op_p
, tree val
)
1381 replace_exp_1 (op_p
, val
, true);
1384 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
1386 Use this version when not const/copy propagating values. For example,
1387 PRE uses this version when building expressions as they would appear
1388 in specific blocks taking into account actions of PHI nodes.
1390 The statement in which an expression has been replaced should be
1391 folded using fold_stmt_inplace. */
1394 replace_exp (use_operand_p op_p
, tree val
)
1396 replace_exp_1 (op_p
, val
, false);
1400 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1401 into the tree pointed to by OP_P.
1403 Use this version for const/copy propagation when SSA operands are not
1404 available. It will perform the additional checks to ensure validity of
1405 the const/copy propagation, but will not update any operand information.
1406 Be sure to mark the stmt as modified. */
1409 propagate_tree_value (tree
*op_p
, tree val
)
1411 if (TREE_CODE (val
) == SSA_NAME
)
1414 *op_p
= unshare_expr (val
);
1418 /* Like propagate_tree_value, but use as the operand to replace
1419 the principal expression (typically, the RHS) contained in the
1420 statement referenced by iterator GSI. Note that it is not
1421 always possible to update the statement in-place, so a new
1422 statement may be created to replace the original. */
1425 propagate_tree_value_into_stmt (gimple_stmt_iterator
*gsi
, tree val
)
1427 gimple
*stmt
= gsi_stmt (*gsi
);
1429 if (is_gimple_assign (stmt
))
1431 tree expr
= NULL_TREE
;
1432 if (gimple_assign_single_p (stmt
))
1433 expr
= gimple_assign_rhs1 (stmt
);
1434 propagate_tree_value (&expr
, val
);
1435 gimple_assign_set_rhs_from_tree (gsi
, expr
);
1437 else if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
1439 tree lhs
= NULL_TREE
;
1440 tree rhs
= build_zero_cst (TREE_TYPE (val
));
1441 propagate_tree_value (&lhs
, val
);
1442 gimple_cond_set_code (cond_stmt
, NE_EXPR
);
1443 gimple_cond_set_lhs (cond_stmt
, lhs
);
1444 gimple_cond_set_rhs (cond_stmt
, rhs
);
1446 else if (is_gimple_call (stmt
)
1447 && gimple_call_lhs (stmt
) != NULL_TREE
)
1449 tree expr
= NULL_TREE
;
1451 propagate_tree_value (&expr
, val
);
1452 res
= update_call_from_tree (gsi
, expr
);
1455 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1456 propagate_tree_value (gimple_switch_index_ptr (swtch_stmt
), val
);