1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004-2015 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 "double-int.h"
35 #include "fold-const.h"
39 #include "hard-reg-set.h"
42 #include "dominance.h"
44 #include "basic-block.h"
45 #include "gimple-pretty-print.h"
49 #include "tree-ssa-alias.h"
50 #include "internal-fn.h"
51 #include "gimple-fold.h"
53 #include "gimple-expr.h"
57 #include "gimple-iterator.h"
58 #include "gimple-ssa.h"
60 #include "tree-phinodes.h"
61 #include "ssa-iterators.h"
62 #include "stringpool.h"
63 #include "tree-ssanames.h"
65 #include "tree-ssa-propagate.h"
66 #include "langhooks.h"
67 #include "value-prof.h"
71 /* This file implements a generic value propagation engine based on
72 the same propagation used by the SSA-CCP algorithm [1].
74 Propagation is performed by simulating the execution of every
75 statement that produces the value being propagated. Simulation
78 1- Initially, all edges of the CFG are marked not executable and
79 the CFG worklist is seeded with all the statements in the entry
80 basic block (block 0).
82 2- Every statement S is simulated with a call to the call-back
83 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
86 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
87 interest and does not affect any of the work lists.
89 SSA_PROP_VARYING: The value produced by S cannot be determined
90 at compile time. Further simulation of S is not required.
91 If S is a conditional jump, all the outgoing edges for the
92 block are considered executable and added to the work
95 SSA_PROP_INTERESTING: S produces a value that can be computed
96 at compile time. Its result can be propagated into the
97 statements that feed from S. Furthermore, if S is a
98 conditional jump, only the edge known to be taken is added
99 to the work list. Edges that are known not to execute are
102 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
103 return value from SSA_PROP_VISIT_PHI has the same semantics as
106 4- Three work lists are kept. Statements are only added to these
107 lists if they produce one of SSA_PROP_INTERESTING or
110 CFG_BLOCKS contains the list of blocks to be simulated.
111 Blocks are added to this list if their incoming edges are
114 VARYING_SSA_EDGES contains the list of statements that feed
115 from statements that produce an SSA_PROP_VARYING result.
116 These are simulated first to speed up processing.
118 INTERESTING_SSA_EDGES contains the list of statements that
119 feed from statements that produce an SSA_PROP_INTERESTING
122 5- Simulation terminates when all three work lists are drained.
124 Before calling ssa_propagate, it is important to clear
125 prop_simulate_again_p for all the statements in the program that
126 should be simulated. This initialization allows an implementation
127 to specify which statements should never be simulated.
129 It is also important to compute def-use information before calling
134 [1] Constant propagation with conditional branches,
135 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
137 [2] Building an Optimizing Compiler,
138 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
140 [3] Advanced Compiler Design and Implementation,
141 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
143 /* Function pointers used to parameterize the propagation engine. */
144 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
145 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
147 /* Keep track of statements that have been added to one of the SSA
148 edges worklists. This flag is used to avoid visiting statements
149 unnecessarily when draining an SSA edge worklist. If while
150 simulating a basic block, we find a statement with
151 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
152 processing from visiting it again.
154 NOTE: users of the propagation engine are not allowed to use
155 the GF_PLF_1 flag. */
156 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
158 /* A bitmap to keep track of executable blocks in the CFG. */
159 static sbitmap executable_blocks
;
161 /* Array of control flow edges on the worklist. */
162 static vec
<basic_block
> cfg_blocks
;
164 static unsigned int cfg_blocks_num
= 0;
165 static int cfg_blocks_tail
;
166 static int cfg_blocks_head
;
168 static sbitmap bb_in_list
;
170 /* Worklist of SSA edges which will need reexamination as their
171 definition has changed. SSA edges are def-use edges in the SSA
172 web. For each D-U edge, we store the target statement or PHI node
174 static vec
<gimple
> interesting_ssa_edges
;
176 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
177 list of SSA edges is split into two. One contains all SSA edges
178 who need to be reexamined because their lattice value changed to
179 varying (this worklist), and the other contains all other SSA edges
180 to be reexamined (INTERESTING_SSA_EDGES).
182 Since most values in the program are VARYING, the ideal situation
183 is to move them to that lattice value as quickly as possible.
184 Thus, it doesn't make sense to process any other type of lattice
185 value until all VARYING values are propagated fully, which is one
186 thing using the VARYING worklist achieves. In addition, if we
187 don't use a separate worklist for VARYING edges, we end up with
188 situations where lattice values move from
189 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
190 static vec
<gimple
> varying_ssa_edges
;
193 /* Return true if the block worklist empty. */
196 cfg_blocks_empty_p (void)
198 return (cfg_blocks_num
== 0);
202 /* Add a basic block to the worklist. The block must not be already
203 in the worklist, and it must not be the ENTRY or EXIT block. */
206 cfg_blocks_add (basic_block bb
)
210 gcc_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
211 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
212 gcc_assert (!bitmap_bit_p (bb_in_list
, bb
->index
));
214 if (cfg_blocks_empty_p ())
216 cfg_blocks_tail
= cfg_blocks_head
= 0;
222 if (cfg_blocks_num
> cfg_blocks
.length ())
224 /* We have to grow the array now. Adjust to queue to occupy
225 the full space of the original array. We do not need to
226 initialize the newly allocated portion of the array
227 because we keep track of CFG_BLOCKS_HEAD and
229 cfg_blocks_tail
= cfg_blocks
.length ();
231 cfg_blocks
.safe_grow (2 * cfg_blocks_tail
);
233 /* Minor optimization: we prefer to see blocks with more
234 predecessors later, because there is more of a chance that
235 the incoming edges will be executable. */
236 else if (EDGE_COUNT (bb
->preds
)
237 >= EDGE_COUNT (cfg_blocks
[cfg_blocks_head
]->preds
))
238 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1) % cfg_blocks
.length ());
241 if (cfg_blocks_head
== 0)
242 cfg_blocks_head
= cfg_blocks
.length ();
248 cfg_blocks
[head
? cfg_blocks_head
: cfg_blocks_tail
] = bb
;
249 bitmap_set_bit (bb_in_list
, bb
->index
);
253 /* Remove a block from the worklist. */
256 cfg_blocks_get (void)
260 bb
= cfg_blocks
[cfg_blocks_head
];
262 gcc_assert (!cfg_blocks_empty_p ());
265 cfg_blocks_head
= ((cfg_blocks_head
+ 1) % cfg_blocks
.length ());
267 bitmap_clear_bit (bb_in_list
, bb
->index
);
273 /* We have just defined a new value for VAR. If IS_VARYING is true,
274 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
275 them to INTERESTING_SSA_EDGES. */
278 add_ssa_edge (tree var
, bool is_varying
)
280 imm_use_iterator iter
;
283 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
285 gimple use_stmt
= USE_STMT (use_p
);
287 if (prop_simulate_again_p (use_stmt
)
288 && !gimple_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
290 gimple_set_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
, true);
292 varying_ssa_edges
.safe_push (use_stmt
);
294 interesting_ssa_edges
.safe_push (use_stmt
);
300 /* Add edge E to the control flow worklist. */
303 add_control_edge (edge e
)
305 basic_block bb
= e
->dest
;
306 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
309 /* If the edge had already been executed, skip it. */
310 if (e
->flags
& EDGE_EXECUTABLE
)
313 e
->flags
|= EDGE_EXECUTABLE
;
315 /* If the block is already in the list, we're done. */
316 if (bitmap_bit_p (bb_in_list
, bb
->index
))
321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
322 fprintf (dump_file
, "\nAdding Destination of edge (%d -> %d) to worklist\n",
323 e
->src
->index
, e
->dest
->index
);
327 /* Simulate the execution of STMT and update the work lists accordingly. */
330 simulate_stmt (gimple stmt
)
332 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
333 edge taken_edge
= NULL
;
334 tree output_name
= NULL_TREE
;
336 /* Don't bother visiting statements that are already
337 considered varying by the propagator. */
338 if (!prop_simulate_again_p (stmt
))
341 if (gimple_code (stmt
) == GIMPLE_PHI
)
343 val
= ssa_prop_visit_phi (as_a
<gphi
*> (stmt
));
344 output_name
= gimple_phi_result (stmt
);
347 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
349 if (val
== SSA_PROP_VARYING
)
351 prop_set_simulate_again (stmt
, false);
353 /* If the statement produced a new varying value, add the SSA
354 edges coming out of OUTPUT_NAME. */
356 add_ssa_edge (output_name
, true);
358 /* If STMT transfers control out of its basic block, add
359 all outgoing edges to the work list. */
360 if (stmt_ends_bb_p (stmt
))
364 basic_block bb
= gimple_bb (stmt
);
365 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
366 add_control_edge (e
);
369 else if (val
== SSA_PROP_INTERESTING
)
371 /* If the statement produced new value, add the SSA edges coming
372 out of OUTPUT_NAME. */
374 add_ssa_edge (output_name
, false);
376 /* If we know which edge is going to be taken out of this block,
377 add it to the CFG work list. */
379 add_control_edge (taken_edge
);
383 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
384 drain. This pops statements off the given WORKLIST and processes
385 them until there are no more statements on WORKLIST.
386 We take a pointer to WORKLIST because it may be reallocated when an
387 SSA edge is added to it in simulate_stmt. */
390 process_ssa_edge_worklist (vec
<gimple
> *worklist
)
392 /* Drain the entire worklist. */
393 while (worklist
->length () > 0)
397 /* Pull the statement to simulate off the worklist. */
398 gimple stmt
= worklist
->pop ();
400 /* If this statement was already visited by simulate_block, then
401 we don't need to visit it again here. */
402 if (!gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
405 /* STMT is no longer in a worklist. */
406 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
410 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
411 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
414 bb
= gimple_bb (stmt
);
416 /* PHI nodes are always visited, regardless of whether or not
417 the destination block is executable. Otherwise, visit the
418 statement only if its block is marked executable. */
419 if (gimple_code (stmt
) == GIMPLE_PHI
420 || bitmap_bit_p (executable_blocks
, bb
->index
))
421 simulate_stmt (stmt
);
426 /* Simulate the execution of BLOCK. Evaluate the statement associated
427 with each variable reference inside the block. */
430 simulate_block (basic_block block
)
432 gimple_stmt_iterator gsi
;
434 /* There is nothing to do for the exit block. */
435 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
439 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
441 /* Always simulate PHI nodes, even if we have simulated this block
443 for (gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
444 simulate_stmt (gsi_stmt (gsi
));
446 /* If this is the first time we've simulated this block, then we
447 must simulate each of its statements. */
448 if (!bitmap_bit_p (executable_blocks
, block
->index
))
450 gimple_stmt_iterator j
;
451 unsigned int normal_edge_count
;
455 /* Note that we have simulated this block. */
456 bitmap_set_bit (executable_blocks
, block
->index
);
458 for (j
= gsi_start_bb (block
); !gsi_end_p (j
); gsi_next (&j
))
460 gimple stmt
= gsi_stmt (j
);
462 /* If this statement is already in the worklist then
463 "cancel" it. The reevaluation implied by the worklist
464 entry will produce the same value we generate here and
465 thus reevaluating it again from the worklist is
467 if (gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
468 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
470 simulate_stmt (stmt
);
473 /* We can not predict when abnormal and EH edges will be executed, so
474 once a block is considered executable, we consider any
475 outgoing abnormal edges as executable.
477 TODO: This is not exactly true. Simplifying statement might
478 prove it non-throwing and also computed goto can be handled
479 when destination is known.
481 At the same time, if this block has only one successor that is
482 reached by non-abnormal edges, then add that successor to the
484 normal_edge_count
= 0;
486 FOR_EACH_EDGE (e
, ei
, block
->succs
)
488 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
489 add_control_edge (e
);
497 if (normal_edge_count
== 1)
498 add_control_edge (normal_edge
);
503 /* Initialize local data structures and work lists. */
512 /* Worklists of SSA edges. */
513 interesting_ssa_edges
.create (20);
514 varying_ssa_edges
.create (20);
516 executable_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
517 bitmap_clear (executable_blocks
);
519 bb_in_list
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
520 bitmap_clear (bb_in_list
);
522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
523 dump_immediate_uses (dump_file
);
525 cfg_blocks
.create (20);
526 cfg_blocks
.safe_grow_cleared (20);
528 /* Initially assume that every edge in the CFG is not executable.
529 (including the edges coming out of the entry block). */
530 FOR_ALL_BB_FN (bb
, cfun
)
532 gimple_stmt_iterator si
;
534 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
535 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
537 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
538 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
540 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
541 e
->flags
&= ~EDGE_EXECUTABLE
;
544 /* Seed the algorithm by adding the successors of the entry block to the
546 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
547 add_control_edge (e
);
551 /* Free allocated storage. */
556 interesting_ssa_edges
.release ();
557 varying_ssa_edges
.release ();
558 cfg_blocks
.release ();
559 sbitmap_free (bb_in_list
);
560 sbitmap_free (executable_blocks
);
564 /* Return true if EXPR is an acceptable right-hand-side for a
565 GIMPLE assignment. We validate the entire tree, not just
566 the root node, thus catching expressions that embed complex
567 operands that are not permitted in GIMPLE. This function
568 is needed because the folding routines in fold-const.c
569 may return such expressions in some cases, e.g., an array
570 access with an embedded index addition. It may make more
571 sense to have folding routines that are sensitive to the
572 constraints on GIMPLE operands, rather than abandoning any
573 any attempt to fold if the usual folding turns out to be too
577 valid_gimple_rhs_p (tree expr
)
579 enum tree_code code
= TREE_CODE (expr
);
581 switch (TREE_CODE_CLASS (code
))
583 case tcc_declaration
:
584 if (!is_gimple_variable (expr
))
589 /* All constants are ok. */
593 /* GENERIC allows comparisons with non-boolean types, reject
594 those for GIMPLE. Let vector-typed comparisons pass - rules
595 for GENERIC and GIMPLE are the same here. */
596 if (!(INTEGRAL_TYPE_P (TREE_TYPE (expr
))
597 && (TREE_CODE (TREE_TYPE (expr
)) == BOOLEAN_TYPE
598 || TYPE_PRECISION (TREE_TYPE (expr
)) == 1))
599 && ! VECTOR_TYPE_P (TREE_TYPE (expr
)))
604 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
605 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
610 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
620 if (is_gimple_min_invariant (expr
))
622 t
= TREE_OPERAND (expr
, 0);
623 while (handled_component_p (t
))
625 /* ??? More checks needed, see the GIMPLE verifier. */
626 if ((TREE_CODE (t
) == ARRAY_REF
627 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
628 && !is_gimple_val (TREE_OPERAND (t
, 1)))
630 t
= TREE_OPERAND (t
, 0);
632 if (!is_gimple_id (t
))
638 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
640 if (((code
== VEC_COND_EXPR
|| code
== COND_EXPR
)
641 ? !is_gimple_condexpr (TREE_OPERAND (expr
, 0))
642 : !is_gimple_val (TREE_OPERAND (expr
, 0)))
643 || !is_gimple_val (TREE_OPERAND (expr
, 1))
644 || !is_gimple_val (TREE_OPERAND (expr
, 2)))
655 case tcc_exceptional
:
656 if (code
== CONSTRUCTOR
)
660 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (expr
), i
, elt
)
661 if (!is_gimple_val (elt
))
665 if (code
!= SSA_NAME
)
670 if (code
== BIT_FIELD_REF
)
671 return is_gimple_val (TREE_OPERAND (expr
, 0));
682 /* Return true if EXPR is a CALL_EXPR suitable for representation
683 as a single GIMPLE_CALL statement. If the arguments require
684 further gimplification, return false. */
687 valid_gimple_call_p (tree expr
)
691 if (TREE_CODE (expr
) != CALL_EXPR
)
694 nargs
= call_expr_nargs (expr
);
695 for (i
= 0; i
< nargs
; i
++)
697 tree arg
= CALL_EXPR_ARG (expr
, i
);
698 if (is_gimple_reg_type (TREE_TYPE (arg
)))
700 if (!is_gimple_val (arg
))
704 if (!is_gimple_lvalue (arg
))
712 /* Make SSA names defined by OLD_STMT point to NEW_STMT
713 as their defining statement. */
716 move_ssa_defining_stmt_for_defs (gimple new_stmt
, gimple old_stmt
)
721 if (gimple_in_ssa_p (cfun
))
723 /* Make defined SSA_NAMEs point to the new
724 statement as their definition. */
725 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
727 if (TREE_CODE (var
) == SSA_NAME
)
728 SSA_NAME_DEF_STMT (var
) = new_stmt
;
733 /* Helper function for update_gimple_call and update_call_from_tree.
734 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
737 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple new_stmt
,
740 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
741 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
742 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
743 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
744 gimple_set_location (new_stmt
, gimple_location (stmt
));
745 if (gimple_block (new_stmt
) == NULL_TREE
)
746 gimple_set_block (new_stmt
, gimple_block (stmt
));
747 gsi_replace (si_p
, new_stmt
, false);
750 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
751 with number of arguments NARGS, where the arguments in GIMPLE form
752 follow NARGS argument. */
755 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
758 gcall
*new_stmt
, *stmt
= as_a
<gcall
*> (gsi_stmt (*si_p
));
760 gcc_assert (is_gimple_call (stmt
));
761 va_start (ap
, nargs
);
762 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
763 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
768 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
769 value of EXPR, which is expected to be the result of folding the
770 call. This can only be done if EXPR is a CALL_EXPR with valid
771 GIMPLE operands as arguments, or if it is a suitable RHS expression
772 for a GIMPLE_ASSIGN. More complex expressions will require
773 gimplification, which will introduce additional statements. In this
774 event, no update is performed, and the function returns false.
775 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
776 replace the statement at *SI_P with an entirely new statement.
777 The new statement need not be a call, e.g., if the original call
778 folded to a constant. */
781 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
783 gimple stmt
= gsi_stmt (*si_p
);
785 if (valid_gimple_call_p (expr
))
787 /* The call has simplified to another call. */
788 tree fn
= CALL_EXPR_FN (expr
);
790 unsigned nargs
= call_expr_nargs (expr
);
791 vec
<tree
> args
= vNULL
;
797 args
.safe_grow_cleared (nargs
);
799 for (i
= 0; i
< nargs
; i
++)
800 args
[i
] = CALL_EXPR_ARG (expr
, i
);
803 new_stmt
= gimple_build_call_vec (fn
, args
);
804 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
809 else if (valid_gimple_rhs_p (expr
))
811 tree lhs
= gimple_call_lhs (stmt
);
814 /* The call has simplified to an expression
815 that cannot be represented as a GIMPLE_CALL. */
818 /* A value is expected.
819 Introduce a new GIMPLE_ASSIGN statement. */
820 STRIP_USELESS_TYPE_CONVERSION (expr
);
821 new_stmt
= gimple_build_assign (lhs
, expr
);
822 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
823 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
824 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
826 else if (!TREE_SIDE_EFFECTS (expr
))
828 /* No value is expected, and EXPR has no effect.
829 Replace it with an empty statement. */
830 new_stmt
= gimple_build_nop ();
831 if (gimple_in_ssa_p (cfun
))
833 unlink_stmt_vdef (stmt
);
839 /* No value is expected, but EXPR has an effect,
840 e.g., it could be a reference to a volatile
841 variable. Create an assignment statement
842 with a dummy (unused) lhs variable. */
843 STRIP_USELESS_TYPE_CONVERSION (expr
);
844 if (gimple_in_ssa_p (cfun
))
845 lhs
= make_ssa_name (TREE_TYPE (expr
));
847 lhs
= create_tmp_var (TREE_TYPE (expr
));
848 new_stmt
= gimple_build_assign (lhs
, expr
);
849 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
850 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
851 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
853 gimple_set_location (new_stmt
, gimple_location (stmt
));
854 gsi_replace (si_p
, new_stmt
, false);
858 /* The call simplified to an expression that is
859 not a valid GIMPLE RHS. */
864 /* Entry point to the propagation engine.
866 VISIT_STMT is called for every statement visited.
867 VISIT_PHI is called for every PHI node visited. */
870 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
871 ssa_prop_visit_phi_fn visit_phi
)
873 ssa_prop_visit_stmt
= visit_stmt
;
874 ssa_prop_visit_phi
= visit_phi
;
878 /* Iterate until the worklists are empty. */
879 while (!cfg_blocks_empty_p ()
880 || interesting_ssa_edges
.length () > 0
881 || varying_ssa_edges
.length () > 0)
883 if (!cfg_blocks_empty_p ())
885 /* Pull the next block to simulate off the worklist. */
886 basic_block dest_block
= cfg_blocks_get ();
887 simulate_block (dest_block
);
890 /* In order to move things to varying as quickly as
891 possible,process the VARYING_SSA_EDGES worklist first. */
892 process_ssa_edge_worklist (&varying_ssa_edges
);
894 /* Now process the INTERESTING_SSA_EDGES worklist. */
895 process_ssa_edge_worklist (&interesting_ssa_edges
);
902 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
903 is a non-volatile pointer dereference, a structure reference or a
904 reference to a single _DECL. Ignore volatile memory references
905 because they are not interesting for the optimizers. */
908 stmt_makes_single_store (gimple stmt
)
912 if (gimple_code (stmt
) != GIMPLE_ASSIGN
913 && gimple_code (stmt
) != GIMPLE_CALL
)
916 if (!gimple_vdef (stmt
))
919 lhs
= gimple_get_lhs (stmt
);
921 /* A call statement may have a null LHS. */
925 return (!TREE_THIS_VOLATILE (lhs
)
927 || REFERENCE_CLASS_P (lhs
)));
931 /* Propagation statistics. */
936 long num_stmts_folded
;
940 static struct prop_stats_d prop_stats
;
942 /* Replace USE references in statement STMT with the values stored in
943 PROP_VALUE. Return true if at least one reference was replaced. */
946 replace_uses_in (gimple stmt
, ssa_prop_get_value_fn get_value
)
948 bool replaced
= false;
952 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
954 tree tuse
= USE_FROM_PTR (use
);
955 tree val
= (*get_value
) (tuse
);
957 if (val
== tuse
|| val
== NULL_TREE
)
960 if (gimple_code (stmt
) == GIMPLE_ASM
961 && !may_propagate_copy_into_asm (tuse
))
964 if (!may_propagate_copy (tuse
, val
))
967 if (TREE_CODE (val
) != SSA_NAME
)
968 prop_stats
.num_const_prop
++;
970 prop_stats
.num_copy_prop
++;
972 propagate_value (use
, val
);
981 /* Replace propagated values into all the arguments for PHI using the
982 values from PROP_VALUE. */
985 replace_phi_args_in (gphi
*phi
, ssa_prop_get_value_fn get_value
)
988 bool replaced
= false;
990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
992 fprintf (dump_file
, "Folding PHI node: ");
993 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
996 basic_block bb
= gimple_bb (phi
);
997 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
999 tree arg
= gimple_phi_arg_def (phi
, i
);
1001 if (TREE_CODE (arg
) == SSA_NAME
)
1003 tree val
= (*get_value
) (arg
);
1005 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
1007 edge e
= gimple_phi_arg_edge (phi
, i
);
1009 /* Avoid propagating constants into loop latch edge
1010 PHI arguments as this makes coalescing the copy
1011 across this edge impossible. If the argument is
1012 defined by an assert - otherwise the stmt will
1013 get removed without replacing its uses. */
1014 if (TREE_CODE (val
) != SSA_NAME
1015 && bb
->loop_father
->header
== bb
1016 && dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
)
1017 && is_gimple_assign (SSA_NAME_DEF_STMT (arg
))
1018 && (gimple_assign_rhs_code (SSA_NAME_DEF_STMT (arg
))
1022 if (TREE_CODE (val
) != SSA_NAME
)
1023 prop_stats
.num_const_prop
++;
1025 prop_stats
.num_copy_prop
++;
1027 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
1030 /* If we propagated a copy and this argument flows
1031 through an abnormal edge, update the replacement
1033 if (TREE_CODE (val
) == SSA_NAME
1034 && e
->flags
& EDGE_ABNORMAL
1035 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
))
1037 /* This can only occur for virtual operands, since
1038 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))
1039 would prevent replacement. */
1040 gcc_checking_assert (virtual_operand_p (val
));
1041 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
1047 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1050 fprintf (dump_file
, "No folding possible\n");
1053 fprintf (dump_file
, "Folded into: ");
1054 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1055 fprintf (dump_file
, "\n");
1063 class substitute_and_fold_dom_walker
: public dom_walker
1066 substitute_and_fold_dom_walker (cdi_direction direction
,
1067 ssa_prop_get_value_fn get_value_fn_
,
1068 ssa_prop_fold_stmt_fn fold_fn_
,
1070 : dom_walker (direction
), get_value_fn (get_value_fn_
),
1071 fold_fn (fold_fn_
), do_dce (do_dce_
), something_changed (false)
1073 stmts_to_remove
.create (0);
1074 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
1076 ~substitute_and_fold_dom_walker ()
1078 stmts_to_remove
.release ();
1079 BITMAP_FREE (need_eh_cleanup
);
1082 virtual void before_dom_children (basic_block
);
1083 virtual void after_dom_children (basic_block
) {}
1085 ssa_prop_get_value_fn get_value_fn
;
1086 ssa_prop_fold_stmt_fn fold_fn
;
1088 bool something_changed
;
1089 vec
<gimple
> stmts_to_remove
;
1090 bitmap need_eh_cleanup
;
1094 substitute_and_fold_dom_walker::before_dom_children (basic_block bb
)
1096 /* Propagate known values into PHI nodes. */
1097 for (gphi_iterator i
= gsi_start_phis (bb
);
1101 gphi
*phi
= i
.phi ();
1102 tree res
= gimple_phi_result (phi
);
1103 if (virtual_operand_p (res
))
1106 && res
&& TREE_CODE (res
) == SSA_NAME
)
1108 tree sprime
= get_value_fn (res
);
1111 && may_propagate_copy (res
, sprime
))
1113 stmts_to_remove
.safe_push (phi
);
1117 something_changed
|= replace_phi_args_in (phi
, get_value_fn
);
1120 /* Propagate known values into stmts. In some case it exposes
1121 more trivially deletable stmts to walk backward. */
1122 for (gimple_stmt_iterator i
= gsi_start_bb (bb
);
1127 gimple stmt
= gsi_stmt (i
);
1129 enum gimple_code code
= gimple_code (stmt
);
1131 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1132 range information for names and they are discarded
1135 if (code
== GIMPLE_ASSIGN
1136 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
1139 /* No point propagating into a stmt we have a value for we
1140 can propagate into all uses. Mark it for removal instead. */
1141 tree lhs
= gimple_get_lhs (stmt
);
1143 && lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1145 tree sprime
= get_value_fn (lhs
);
1148 && may_propagate_copy (lhs
, sprime
)
1149 && !stmt_could_throw_p (stmt
)
1150 && !gimple_has_side_effects (stmt
))
1152 stmts_to_remove
.safe_push (stmt
);
1157 /* Replace the statement with its folded version and mark it
1159 did_replace
= false;
1160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1162 fprintf (dump_file
, "Folding statement: ");
1163 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1168 /* Some statements may be simplified using propagator
1169 specific information. Do this before propagating
1170 into the stmt to not disturb pass specific information. */
1175 prop_stats
.num_stmts_folded
++;
1176 stmt
= gsi_stmt (i
);
1180 /* Replace real uses in the statement. */
1181 did_replace
|= replace_uses_in (stmt
, get_value_fn
);
1183 /* If we made a replacement, fold the statement. */
1185 fold_stmt (&i
, follow_single_use_edges
);
1190 stmt
= gsi_stmt (i
);
1192 /* If we cleaned up EH information from the statement,
1194 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1195 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1197 if (is_gimple_assign (stmt
)
1198 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1199 == GIMPLE_SINGLE_RHS
))
1201 tree rhs
= gimple_assign_rhs1 (stmt
);
1203 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1204 recompute_tree_invariant_for_addr_expr (rhs
);
1207 /* Determine what needs to be done to update the SSA form. */
1209 if (!is_gimple_debug (stmt
))
1210 something_changed
= true;
1213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1217 fprintf (dump_file
, "Folded into: ");
1218 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1219 fprintf (dump_file
, "\n");
1222 fprintf (dump_file
, "Not folded\n");
1229 /* Perform final substitution and folding of propagated values.
1231 PROP_VALUE[I] contains the single value that should be substituted
1232 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1235 If FOLD_FN is non-NULL the function will be invoked on all statements
1236 before propagating values for pass specific simplification.
1238 DO_DCE is true if trivially dead stmts can be removed.
1240 If DO_DCE is true, the statements within a BB are walked from
1241 last to first element. Otherwise we scan from first to last element.
1243 Return TRUE when something changed. */
1246 substitute_and_fold (ssa_prop_get_value_fn get_value_fn
,
1247 ssa_prop_fold_stmt_fn fold_fn
,
1250 gcc_assert (get_value_fn
);
1252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1253 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1255 memset (&prop_stats
, 0, sizeof (prop_stats
));
1257 calculate_dominance_info (CDI_DOMINATORS
);
1258 substitute_and_fold_dom_walker
walker(CDI_DOMINATORS
,
1259 get_value_fn
, fold_fn
, do_dce
);
1260 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1262 /* We cannot remove stmts during the BB walk, especially not release
1263 SSA names there as that destroys the lattice of our callers.
1264 Remove stmts in reverse order to make debug stmt creation possible. */
1265 while (!walker
.stmts_to_remove
.is_empty ())
1267 gimple stmt
= walker
.stmts_to_remove
.pop ();
1268 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1270 fprintf (dump_file
, "Removing dead stmt ");
1271 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1272 fprintf (dump_file
, "\n");
1274 prop_stats
.num_dce
++;
1275 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1276 if (gimple_code (stmt
) == GIMPLE_PHI
)
1277 remove_phi_node (&gsi
, true);
1280 unlink_stmt_vdef (stmt
);
1281 gsi_remove (&gsi
, true);
1282 release_defs (stmt
);
1286 if (!bitmap_empty_p (walker
.need_eh_cleanup
))
1287 gimple_purge_all_dead_eh_edges (walker
.need_eh_cleanup
);
1289 statistics_counter_event (cfun
, "Constants propagated",
1290 prop_stats
.num_const_prop
);
1291 statistics_counter_event (cfun
, "Copies propagated",
1292 prop_stats
.num_copy_prop
);
1293 statistics_counter_event (cfun
, "Statements folded",
1294 prop_stats
.num_stmts_folded
);
1295 statistics_counter_event (cfun
, "Statements deleted",
1296 prop_stats
.num_dce
);
1298 return walker
.something_changed
;
1302 /* Return true if we may propagate ORIG into DEST, false otherwise. */
1305 may_propagate_copy (tree dest
, tree orig
)
1307 tree type_d
= TREE_TYPE (dest
);
1308 tree type_o
= TREE_TYPE (orig
);
1310 /* If ORIG is a default definition which flows in from an abnormal edge
1311 then the copy can be propagated. It is important that we do so to avoid
1312 uninitialized copies. */
1313 if (TREE_CODE (orig
) == SSA_NAME
1314 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
)
1315 && SSA_NAME_IS_DEFAULT_DEF (orig
)
1316 && (SSA_NAME_VAR (orig
) == NULL_TREE
1317 || TREE_CODE (SSA_NAME_VAR (orig
)) == VAR_DECL
))
1319 /* Otherwise if ORIG just flows in from an abnormal edge then the copy cannot
1321 else if (TREE_CODE (orig
) == SSA_NAME
1322 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
))
1324 /* Similarly if DEST flows in from an abnormal edge then the copy cannot be
1326 else if (TREE_CODE (dest
) == SSA_NAME
1327 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest
))
1330 /* Do not copy between types for which we *do* need a conversion. */
1331 if (!useless_type_conversion_p (type_d
, type_o
))
1334 /* Generally propagating virtual operands is not ok as that may
1335 create overlapping life-ranges. */
1336 if (TREE_CODE (dest
) == SSA_NAME
&& virtual_operand_p (dest
))
1339 /* Anything else is OK. */
1343 /* Like may_propagate_copy, but use as the destination expression
1344 the principal expression (typically, the RHS) contained in
1345 statement DEST. This is more efficient when working with the
1346 gimple tuples representation. */
1349 may_propagate_copy_into_stmt (gimple dest
, tree orig
)
1354 /* If the statement is a switch or a single-rhs assignment,
1355 then the expression to be replaced by the propagation may
1356 be an SSA_NAME. Fortunately, there is an explicit tree
1357 for the expression, so we delegate to may_propagate_copy. */
1359 if (gimple_assign_single_p (dest
))
1360 return may_propagate_copy (gimple_assign_rhs1 (dest
), orig
);
1361 else if (gswitch
*dest_swtch
= dyn_cast
<gswitch
*> (dest
))
1362 return may_propagate_copy (gimple_switch_index (dest_swtch
), orig
);
1364 /* In other cases, the expression is not materialized, so there
1365 is no destination to pass to may_propagate_copy. On the other
1366 hand, the expression cannot be an SSA_NAME, so the analysis
1369 if (TREE_CODE (orig
) == SSA_NAME
1370 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
))
1373 if (is_gimple_assign (dest
))
1374 type_d
= TREE_TYPE (gimple_assign_lhs (dest
));
1375 else if (gimple_code (dest
) == GIMPLE_COND
)
1376 type_d
= boolean_type_node
;
1377 else if (is_gimple_call (dest
)
1378 && gimple_call_lhs (dest
) != NULL_TREE
)
1379 type_d
= TREE_TYPE (gimple_call_lhs (dest
));
1383 type_o
= TREE_TYPE (orig
);
1385 if (!useless_type_conversion_p (type_d
, type_o
))
1391 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
1394 may_propagate_copy_into_asm (tree dest ATTRIBUTE_UNUSED
)
1400 /* Common code for propagate_value and replace_exp.
1402 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
1403 replacement is done to propagate a value or not. */
1406 replace_exp_1 (use_operand_p op_p
, tree val
,
1407 bool for_propagation ATTRIBUTE_UNUSED
)
1409 #if defined ENABLE_CHECKING
1410 tree op
= USE_FROM_PTR (op_p
);
1412 gcc_assert (!(for_propagation
1413 && TREE_CODE (op
) == SSA_NAME
1414 && TREE_CODE (val
) == SSA_NAME
1415 && !may_propagate_copy (op
, val
)));
1418 if (TREE_CODE (val
) == SSA_NAME
)
1419 SET_USE (op_p
, val
);
1421 SET_USE (op_p
, unshare_expr (val
));
1425 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1426 into the operand pointed to by OP_P.
1428 Use this version for const/copy propagation as it will perform additional
1429 checks to ensure validity of the const/copy propagation. */
1432 propagate_value (use_operand_p op_p
, tree val
)
1434 replace_exp_1 (op_p
, val
, true);
1437 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
1439 Use this version when not const/copy propagating values. For example,
1440 PRE uses this version when building expressions as they would appear
1441 in specific blocks taking into account actions of PHI nodes.
1443 The statement in which an expression has been replaced should be
1444 folded using fold_stmt_inplace. */
1447 replace_exp (use_operand_p op_p
, tree val
)
1449 replace_exp_1 (op_p
, val
, false);
1453 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1454 into the tree pointed to by OP_P.
1456 Use this version for const/copy propagation when SSA operands are not
1457 available. It will perform the additional checks to ensure validity of
1458 the const/copy propagation, but will not update any operand information.
1459 Be sure to mark the stmt as modified. */
1462 propagate_tree_value (tree
*op_p
, tree val
)
1464 if (TREE_CODE (val
) == SSA_NAME
)
1467 *op_p
= unshare_expr (val
);
1471 /* Like propagate_tree_value, but use as the operand to replace
1472 the principal expression (typically, the RHS) contained in the
1473 statement referenced by iterator GSI. Note that it is not
1474 always possible to update the statement in-place, so a new
1475 statement may be created to replace the original. */
1478 propagate_tree_value_into_stmt (gimple_stmt_iterator
*gsi
, tree val
)
1480 gimple stmt
= gsi_stmt (*gsi
);
1482 if (is_gimple_assign (stmt
))
1484 tree expr
= NULL_TREE
;
1485 if (gimple_assign_single_p (stmt
))
1486 expr
= gimple_assign_rhs1 (stmt
);
1487 propagate_tree_value (&expr
, val
);
1488 gimple_assign_set_rhs_from_tree (gsi
, expr
);
1490 else if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
1492 tree lhs
= NULL_TREE
;
1493 tree rhs
= build_zero_cst (TREE_TYPE (val
));
1494 propagate_tree_value (&lhs
, val
);
1495 gimple_cond_set_code (cond_stmt
, NE_EXPR
);
1496 gimple_cond_set_lhs (cond_stmt
, lhs
);
1497 gimple_cond_set_rhs (cond_stmt
, rhs
);
1499 else if (is_gimple_call (stmt
)
1500 && gimple_call_lhs (stmt
) != NULL_TREE
)
1502 tree expr
= NULL_TREE
;
1504 propagate_tree_value (&expr
, val
);
1505 res
= update_call_from_tree (gsi
, expr
);
1508 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1509 propagate_tree_value (gimple_switch_index_ptr (swtch_stmt
), val
);