1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
33 #include "tree-dump.h"
34 #include "tree-flow.h"
35 #include "tree-pass.h"
36 #include "tree-ssa-propagate.h"
37 #include "langhooks.h"
39 #include "value-prof.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.
60 SSA_PROP_VARYING: The value produced by S cannot be determined
61 at compile time. Further simulation of S is not required.
62 If S is a conditional jump, all the outgoing edges for the
63 block are considered executable and added to the work
66 SSA_PROP_INTERESTING: S produces a value that can be computed
67 at compile time. Its result can be propagated into the
68 statements that feed from S. Furthermore, if S is a
69 conditional jump, only the edge known to be taken is added
70 to the work list. Edges that are known not to execute are
73 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
74 return value from SSA_PROP_VISIT_PHI has the same semantics as
77 4- Three work lists are kept. Statements are only added to these
78 lists if they produce one of SSA_PROP_INTERESTING or
81 CFG_BLOCKS contains the list of blocks to be simulated.
82 Blocks are added to this list if their incoming edges are
85 VARYING_SSA_EDGES contains the list of statements that feed
86 from statements that produce an SSA_PROP_VARYING result.
87 These are simulated first to speed up processing.
89 INTERESTING_SSA_EDGES contains the list of statements that
90 feed from statements that produce an SSA_PROP_INTERESTING
93 5- Simulation terminates when all three work lists are drained.
95 Before calling ssa_propagate, it is important to clear
96 prop_simulate_again_p for all the statements in the program that
97 should be simulated. This initialization allows an implementation
98 to specify which statements should never be simulated.
100 It is also important to compute def-use information before calling
105 [1] Constant propagation with conditional branches,
106 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
108 [2] Building an Optimizing Compiler,
109 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
111 [3] Advanced Compiler Design and Implementation,
112 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
114 /* Function pointers used to parameterize the propagation engine. */
115 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
116 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
118 /* Keep track of statements that have been added to one of the SSA
119 edges worklists. This flag is used to avoid visiting statements
120 unnecessarily when draining an SSA edge worklist. If while
121 simulating a basic block, we find a statement with
122 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
123 processing from visiting it again.
125 NOTE: users of the propagation engine are not allowed to use
126 the GF_PLF_1 flag. */
127 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
129 /* A bitmap to keep track of executable blocks in the CFG. */
130 static sbitmap executable_blocks
;
132 /* Array of control flow edges on the worklist. */
133 static VEC(basic_block
,heap
) *cfg_blocks
;
135 static unsigned int cfg_blocks_num
= 0;
136 static int cfg_blocks_tail
;
137 static int cfg_blocks_head
;
139 static sbitmap bb_in_list
;
141 /* Worklist of SSA edges which will need reexamination as their
142 definition has changed. SSA edges are def-use edges in the SSA
143 web. For each D-U edge, we store the target statement or PHI node
145 static GTY(()) VEC(gimple
,gc
) *interesting_ssa_edges
;
147 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
148 list of SSA edges is split into two. One contains all SSA edges
149 who need to be reexamined because their lattice value changed to
150 varying (this worklist), and the other contains all other SSA edges
151 to be reexamined (INTERESTING_SSA_EDGES).
153 Since most values in the program are VARYING, the ideal situation
154 is to move them to that lattice value as quickly as possible.
155 Thus, it doesn't make sense to process any other type of lattice
156 value until all VARYING values are propagated fully, which is one
157 thing using the VARYING worklist achieves. In addition, if we
158 don't use a separate worklist for VARYING edges, we end up with
159 situations where lattice values move from
160 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
161 static GTY(()) VEC(gimple
,gc
) *varying_ssa_edges
;
164 /* Return true if the block worklist empty. */
167 cfg_blocks_empty_p (void)
169 return (cfg_blocks_num
== 0);
173 /* Add a basic block to the worklist. The block must not be already
174 in the worklist, and it must not be the ENTRY or EXIT block. */
177 cfg_blocks_add (basic_block bb
)
181 gcc_assert (bb
!= ENTRY_BLOCK_PTR
&& bb
!= EXIT_BLOCK_PTR
);
182 gcc_assert (!TEST_BIT (bb_in_list
, bb
->index
));
184 if (cfg_blocks_empty_p ())
186 cfg_blocks_tail
= cfg_blocks_head
= 0;
192 if (cfg_blocks_num
> VEC_length (basic_block
, cfg_blocks
))
194 /* We have to grow the array now. Adjust to queue to occupy
195 the full space of the original array. We do not need to
196 initialize the newly allocated portion of the array
197 because we keep track of CFG_BLOCKS_HEAD and
199 cfg_blocks_tail
= VEC_length (basic_block
, cfg_blocks
);
201 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 2 * cfg_blocks_tail
);
203 /* Minor optimization: we prefer to see blocks with more
204 predecessors later, because there is more of a chance that
205 the incoming edges will be executable. */
206 else if (EDGE_COUNT (bb
->preds
)
207 >= EDGE_COUNT (VEC_index (basic_block
, cfg_blocks
,
208 cfg_blocks_head
)->preds
))
209 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1)
210 % VEC_length (basic_block
, cfg_blocks
));
213 if (cfg_blocks_head
== 0)
214 cfg_blocks_head
= VEC_length (basic_block
, cfg_blocks
);
220 VEC_replace (basic_block
, cfg_blocks
,
221 head
? cfg_blocks_head
: cfg_blocks_tail
,
223 SET_BIT (bb_in_list
, bb
->index
);
227 /* Remove a block from the worklist. */
230 cfg_blocks_get (void)
234 bb
= VEC_index (basic_block
, cfg_blocks
, cfg_blocks_head
);
236 gcc_assert (!cfg_blocks_empty_p ());
239 cfg_blocks_head
= ((cfg_blocks_head
+ 1)
240 % VEC_length (basic_block
, cfg_blocks
));
242 RESET_BIT (bb_in_list
, bb
->index
);
248 /* We have just defined a new value for VAR. If IS_VARYING is true,
249 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
250 them to INTERESTING_SSA_EDGES. */
253 add_ssa_edge (tree var
, bool is_varying
)
255 imm_use_iterator iter
;
258 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
260 gimple use_stmt
= USE_STMT (use_p
);
262 if (prop_simulate_again_p (use_stmt
)
263 && !gimple_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
265 gimple_set_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
, true);
267 VEC_safe_push (gimple
, gc
, varying_ssa_edges
, use_stmt
);
269 VEC_safe_push (gimple
, gc
, interesting_ssa_edges
, use_stmt
);
275 /* Add edge E to the control flow worklist. */
278 add_control_edge (edge e
)
280 basic_block bb
= e
->dest
;
281 if (bb
== EXIT_BLOCK_PTR
)
284 /* If the edge had already been executed, skip it. */
285 if (e
->flags
& EDGE_EXECUTABLE
)
288 e
->flags
|= EDGE_EXECUTABLE
;
290 /* If the block is already in the list, we're done. */
291 if (TEST_BIT (bb_in_list
, bb
->index
))
296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
297 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
298 e
->src
->index
, e
->dest
->index
);
302 /* Simulate the execution of STMT and update the work lists accordingly. */
305 simulate_stmt (gimple stmt
)
307 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
308 edge taken_edge
= NULL
;
309 tree output_name
= NULL_TREE
;
311 /* Don't bother visiting statements that are already
312 considered varying by the propagator. */
313 if (!prop_simulate_again_p (stmt
))
316 if (gimple_code (stmt
) == GIMPLE_PHI
)
318 val
= ssa_prop_visit_phi (stmt
);
319 output_name
= gimple_phi_result (stmt
);
322 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
324 if (val
== SSA_PROP_VARYING
)
326 prop_set_simulate_again (stmt
, false);
328 /* If the statement produced a new varying value, add the SSA
329 edges coming out of OUTPUT_NAME. */
331 add_ssa_edge (output_name
, true);
333 /* If STMT transfers control out of its basic block, add
334 all outgoing edges to the work list. */
335 if (stmt_ends_bb_p (stmt
))
339 basic_block bb
= gimple_bb (stmt
);
340 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
341 add_control_edge (e
);
344 else if (val
== SSA_PROP_INTERESTING
)
346 /* If the statement produced new value, add the SSA edges coming
347 out of OUTPUT_NAME. */
349 add_ssa_edge (output_name
, false);
351 /* If we know which edge is going to be taken out of this block,
352 add it to the CFG work list. */
354 add_control_edge (taken_edge
);
358 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
359 drain. This pops statements off the given WORKLIST and processes
360 them until there are no more statements on WORKLIST.
361 We take a pointer to WORKLIST because it may be reallocated when an
362 SSA edge is added to it in simulate_stmt. */
365 process_ssa_edge_worklist (VEC(gimple
,gc
) **worklist
)
367 /* Drain the entire worklist. */
368 while (VEC_length (gimple
, *worklist
) > 0)
372 /* Pull the statement to simulate off the worklist. */
373 gimple stmt
= VEC_pop (gimple
, *worklist
);
375 /* If this statement was already visited by simulate_block, then
376 we don't need to visit it again here. */
377 if (!gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
380 /* STMT is no longer in a worklist. */
381 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
385 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
386 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
389 bb
= gimple_bb (stmt
);
391 /* PHI nodes are always visited, regardless of whether or not
392 the destination block is executable. Otherwise, visit the
393 statement only if its block is marked executable. */
394 if (gimple_code (stmt
) == GIMPLE_PHI
395 || TEST_BIT (executable_blocks
, bb
->index
))
396 simulate_stmt (stmt
);
401 /* Simulate the execution of BLOCK. Evaluate the statement associated
402 with each variable reference inside the block. */
405 simulate_block (basic_block block
)
407 gimple_stmt_iterator gsi
;
409 /* There is nothing to do for the exit block. */
410 if (block
== EXIT_BLOCK_PTR
)
413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
414 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
416 /* Always simulate PHI nodes, even if we have simulated this block
418 for (gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
419 simulate_stmt (gsi_stmt (gsi
));
421 /* If this is the first time we've simulated this block, then we
422 must simulate each of its statements. */
423 if (!TEST_BIT (executable_blocks
, block
->index
))
425 gimple_stmt_iterator j
;
426 unsigned int normal_edge_count
;
430 /* Note that we have simulated this block. */
431 SET_BIT (executable_blocks
, block
->index
);
433 for (j
= gsi_start_bb (block
); !gsi_end_p (j
); gsi_next (&j
))
435 gimple stmt
= gsi_stmt (j
);
437 /* If this statement is already in the worklist then
438 "cancel" it. The reevaluation implied by the worklist
439 entry will produce the same value we generate here and
440 thus reevaluating it again from the worklist is
442 if (gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
443 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
445 simulate_stmt (stmt
);
448 /* We can not predict when abnormal and EH edges will be executed, so
449 once a block is considered executable, we consider any
450 outgoing abnormal edges as executable.
452 TODO: This is not exactly true. Simplifying statement might
453 prove it non-throwing and also computed goto can be handled
454 when destination is known.
456 At the same time, if this block has only one successor that is
457 reached by non-abnormal edges, then add that successor to the
459 normal_edge_count
= 0;
461 FOR_EACH_EDGE (e
, ei
, block
->succs
)
463 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
464 add_control_edge (e
);
472 if (normal_edge_count
== 1)
473 add_control_edge (normal_edge
);
478 /* Initialize local data structures and work lists. */
487 /* Worklists of SSA edges. */
488 interesting_ssa_edges
= VEC_alloc (gimple
, gc
, 20);
489 varying_ssa_edges
= VEC_alloc (gimple
, gc
, 20);
491 executable_blocks
= sbitmap_alloc (last_basic_block
);
492 sbitmap_zero (executable_blocks
);
494 bb_in_list
= sbitmap_alloc (last_basic_block
);
495 sbitmap_zero (bb_in_list
);
497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
498 dump_immediate_uses (dump_file
);
500 cfg_blocks
= VEC_alloc (basic_block
, heap
, 20);
501 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 20);
503 /* Initially assume that every edge in the CFG is not executable.
504 (including the edges coming out of ENTRY_BLOCK_PTR). */
507 gimple_stmt_iterator si
;
509 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
510 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
512 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
513 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
515 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
516 e
->flags
&= ~EDGE_EXECUTABLE
;
519 /* Seed the algorithm by adding the successors of the entry block to the
521 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
522 add_control_edge (e
);
526 /* Free allocated storage. */
531 VEC_free (gimple
, gc
, interesting_ssa_edges
);
532 VEC_free (gimple
, gc
, varying_ssa_edges
);
533 VEC_free (basic_block
, heap
, cfg_blocks
);
535 sbitmap_free (bb_in_list
);
536 sbitmap_free (executable_blocks
);
540 /* Return true if EXPR is an acceptable right-hand-side for a
541 GIMPLE assignment. We validate the entire tree, not just
542 the root node, thus catching expressions that embed complex
543 operands that are not permitted in GIMPLE. This function
544 is needed because the folding routines in fold-const.c
545 may return such expressions in some cases, e.g., an array
546 access with an embedded index addition. It may make more
547 sense to have folding routines that are sensitive to the
548 constraints on GIMPLE operands, rather than abandoning any
549 any attempt to fold if the usual folding turns out to be too
553 valid_gimple_rhs_p (tree expr
)
555 enum tree_code code
= TREE_CODE (expr
);
557 switch (TREE_CODE_CLASS (code
))
559 case tcc_declaration
:
560 if (!is_gimple_variable (expr
))
565 /* All constants are ok. */
570 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
571 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
576 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
586 if (is_gimple_min_invariant (expr
))
588 t
= TREE_OPERAND (expr
, 0);
589 while (handled_component_p (t
))
591 /* ??? More checks needed, see the GIMPLE verifier. */
592 if ((TREE_CODE (t
) == ARRAY_REF
593 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
594 && !is_gimple_val (TREE_OPERAND (t
, 1)))
596 t
= TREE_OPERAND (t
, 0);
598 if (!is_gimple_id (t
))
604 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
606 if (((code
== VEC_COND_EXPR
|| code
== COND_EXPR
)
607 ? !is_gimple_condexpr (TREE_OPERAND (expr
, 0))
608 : !is_gimple_val (TREE_OPERAND (expr
, 0)))
609 || !is_gimple_val (TREE_OPERAND (expr
, 1))
610 || !is_gimple_val (TREE_OPERAND (expr
, 2)))
621 case tcc_exceptional
:
622 if (code
!= SSA_NAME
)
634 /* Return true if EXPR is a CALL_EXPR suitable for representation
635 as a single GIMPLE_CALL statement. If the arguments require
636 further gimplification, return false. */
639 valid_gimple_call_p (tree expr
)
643 if (TREE_CODE (expr
) != CALL_EXPR
)
646 nargs
= call_expr_nargs (expr
);
647 for (i
= 0; i
< nargs
; i
++)
649 tree arg
= CALL_EXPR_ARG (expr
, i
);
650 if (is_gimple_reg_type (arg
))
652 if (!is_gimple_val (arg
))
656 if (!is_gimple_lvalue (arg
))
664 /* Make SSA names defined by OLD_STMT point to NEW_STMT
665 as their defining statement. */
668 move_ssa_defining_stmt_for_defs (gimple new_stmt
, gimple old_stmt
)
673 if (gimple_in_ssa_p (cfun
))
675 /* Make defined SSA_NAMEs point to the new
676 statement as their definition. */
677 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
679 if (TREE_CODE (var
) == SSA_NAME
)
680 SSA_NAME_DEF_STMT (var
) = new_stmt
;
685 /* Helper function for update_gimple_call and update_call_from_tree.
686 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
689 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple new_stmt
,
692 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
693 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
694 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
695 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
696 gimple_set_location (new_stmt
, gimple_location (stmt
));
697 if (gimple_block (new_stmt
) == NULL_TREE
)
698 gimple_set_block (new_stmt
, gimple_block (stmt
));
699 gsi_replace (si_p
, new_stmt
, false);
702 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
703 with number of arguments NARGS, where the arguments in GIMPLE form
704 follow NARGS argument. */
707 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
710 gimple new_stmt
, stmt
= gsi_stmt (*si_p
);
712 gcc_assert (is_gimple_call (stmt
));
713 va_start (ap
, nargs
);
714 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
715 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
720 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
721 value of EXPR, which is expected to be the result of folding the
722 call. This can only be done if EXPR is a CALL_EXPR with valid
723 GIMPLE operands as arguments, or if it is a suitable RHS expression
724 for a GIMPLE_ASSIGN. More complex expressions will require
725 gimplification, which will introduce additional statements. In this
726 event, no update is performed, and the function returns false.
727 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
728 replace the statement at *SI_P with an entirely new statement.
729 The new statement need not be a call, e.g., if the original call
730 folded to a constant. */
733 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
735 gimple stmt
= gsi_stmt (*si_p
);
737 if (valid_gimple_call_p (expr
))
739 /* The call has simplified to another call. */
740 tree fn
= CALL_EXPR_FN (expr
);
742 unsigned nargs
= call_expr_nargs (expr
);
743 VEC(tree
, heap
) *args
= NULL
;
748 args
= VEC_alloc (tree
, heap
, nargs
);
749 VEC_safe_grow (tree
, heap
, args
, nargs
);
751 for (i
= 0; i
< nargs
; i
++)
752 VEC_replace (tree
, args
, i
, CALL_EXPR_ARG (expr
, i
));
755 new_stmt
= gimple_build_call_vec (fn
, args
);
756 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
757 VEC_free (tree
, heap
, args
);
761 else if (valid_gimple_rhs_p (expr
))
763 tree lhs
= gimple_call_lhs (stmt
);
766 /* The call has simplified to an expression
767 that cannot be represented as a GIMPLE_CALL. */
770 /* A value is expected.
771 Introduce a new GIMPLE_ASSIGN statement. */
772 STRIP_USELESS_TYPE_CONVERSION (expr
);
773 new_stmt
= gimple_build_assign (lhs
, expr
);
774 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
775 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
776 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
778 else if (!TREE_SIDE_EFFECTS (expr
))
780 /* No value is expected, and EXPR has no effect.
781 Replace it with an empty statement. */
782 new_stmt
= gimple_build_nop ();
783 if (gimple_in_ssa_p (cfun
))
785 unlink_stmt_vdef (stmt
);
791 /* No value is expected, but EXPR has an effect,
792 e.g., it could be a reference to a volatile
793 variable. Create an assignment statement
794 with a dummy (unused) lhs variable. */
795 STRIP_USELESS_TYPE_CONVERSION (expr
);
796 lhs
= create_tmp_var (TREE_TYPE (expr
), NULL
);
797 new_stmt
= gimple_build_assign (lhs
, expr
);
798 add_referenced_var (lhs
);
799 if (gimple_in_ssa_p (cfun
))
800 lhs
= make_ssa_name (lhs
, new_stmt
);
801 gimple_assign_set_lhs (new_stmt
, lhs
);
802 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
803 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
804 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
806 gimple_set_location (new_stmt
, gimple_location (stmt
));
807 gsi_replace (si_p
, new_stmt
, false);
811 /* The call simplified to an expression that is
812 not a valid GIMPLE RHS. */
817 /* Entry point to the propagation engine.
819 VISIT_STMT is called for every statement visited.
820 VISIT_PHI is called for every PHI node visited. */
823 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
824 ssa_prop_visit_phi_fn visit_phi
)
826 ssa_prop_visit_stmt
= visit_stmt
;
827 ssa_prop_visit_phi
= visit_phi
;
831 /* Iterate until the worklists are empty. */
832 while (!cfg_blocks_empty_p ()
833 || VEC_length (gimple
, interesting_ssa_edges
) > 0
834 || VEC_length (gimple
, varying_ssa_edges
) > 0)
836 if (!cfg_blocks_empty_p ())
838 /* Pull the next block to simulate off the worklist. */
839 basic_block dest_block
= cfg_blocks_get ();
840 simulate_block (dest_block
);
843 /* In order to move things to varying as quickly as
844 possible,process the VARYING_SSA_EDGES worklist first. */
845 process_ssa_edge_worklist (&varying_ssa_edges
);
847 /* Now process the INTERESTING_SSA_EDGES worklist. */
848 process_ssa_edge_worklist (&interesting_ssa_edges
);
855 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
856 is a non-volatile pointer dereference, a structure reference or a
857 reference to a single _DECL. Ignore volatile memory references
858 because they are not interesting for the optimizers. */
861 stmt_makes_single_store (gimple stmt
)
865 if (gimple_code (stmt
) != GIMPLE_ASSIGN
866 && gimple_code (stmt
) != GIMPLE_CALL
)
869 if (!gimple_vdef (stmt
))
872 lhs
= gimple_get_lhs (stmt
);
874 /* A call statement may have a null LHS. */
878 return (!TREE_THIS_VOLATILE (lhs
)
880 || REFERENCE_CLASS_P (lhs
)));
884 /* Propagation statistics. */
889 long num_stmts_folded
;
893 static struct prop_stats_d prop_stats
;
895 /* Replace USE references in statement STMT with the values stored in
896 PROP_VALUE. Return true if at least one reference was replaced. */
899 replace_uses_in (gimple stmt
, ssa_prop_get_value_fn get_value
)
901 bool replaced
= false;
905 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
907 tree tuse
= USE_FROM_PTR (use
);
908 tree val
= (*get_value
) (tuse
);
910 if (val
== tuse
|| val
== NULL_TREE
)
913 if (gimple_code (stmt
) == GIMPLE_ASM
914 && !may_propagate_copy_into_asm (tuse
))
917 if (!may_propagate_copy (tuse
, val
))
920 if (TREE_CODE (val
) != SSA_NAME
)
921 prop_stats
.num_const_prop
++;
923 prop_stats
.num_copy_prop
++;
925 propagate_value (use
, val
);
934 /* Replace propagated values into all the arguments for PHI using the
935 values from PROP_VALUE. */
938 replace_phi_args_in (gimple phi
, ssa_prop_get_value_fn get_value
)
941 bool replaced
= false;
943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
945 fprintf (dump_file
, "Folding PHI node: ");
946 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
949 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
951 tree arg
= gimple_phi_arg_def (phi
, i
);
953 if (TREE_CODE (arg
) == SSA_NAME
)
955 tree val
= (*get_value
) (arg
);
957 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
959 if (TREE_CODE (val
) != SSA_NAME
)
960 prop_stats
.num_const_prop
++;
962 prop_stats
.num_copy_prop
++;
964 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
967 /* If we propagated a copy and this argument flows
968 through an abnormal edge, update the replacement
970 if (TREE_CODE (val
) == SSA_NAME
971 && gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_ABNORMAL
)
972 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
980 fprintf (dump_file
, "No folding possible\n");
983 fprintf (dump_file
, "Folded into: ");
984 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
985 fprintf (dump_file
, "\n");
991 /* Perform final substitution and folding of propagated values.
993 PROP_VALUE[I] contains the single value that should be substituted
994 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
997 If FOLD_FN is non-NULL the function will be invoked on all statements
998 before propagating values for pass specific simplification.
1000 DO_DCE is true if trivially dead stmts can be removed.
1002 If DO_DCE is true, the statements within a BB are walked from
1003 last to first element. Otherwise we scan from first to last element.
1005 Return TRUE when something changed. */
1008 substitute_and_fold (ssa_prop_get_value_fn get_value_fn
,
1009 ssa_prop_fold_stmt_fn fold_fn
,
1013 bool something_changed
= false;
1016 if (!get_value_fn
&& !fold_fn
)
1019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1020 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1022 memset (&prop_stats
, 0, sizeof (prop_stats
));
1024 /* Substitute lattice values at definition sites. */
1026 for (i
= 1; i
< num_ssa_names
; ++i
)
1028 tree name
= ssa_name (i
);
1031 gimple_stmt_iterator gsi
;
1034 || !is_gimple_reg (name
))
1037 def_stmt
= SSA_NAME_DEF_STMT (name
);
1038 if (gimple_nop_p (def_stmt
)
1039 /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */
1040 || (gimple_assign_single_p (def_stmt
)
1041 && gimple_assign_rhs_code (def_stmt
) == ASSERT_EXPR
)
1042 || !(val
= (*get_value_fn
) (name
))
1043 || !may_propagate_copy (name
, val
))
1046 gsi
= gsi_for_stmt (def_stmt
);
1047 if (is_gimple_assign (def_stmt
))
1049 gimple_assign_set_rhs_with_ops (&gsi
, TREE_CODE (val
),
1051 gcc_assert (gsi_stmt (gsi
) == def_stmt
);
1052 if (maybe_clean_eh_stmt (def_stmt
))
1053 gimple_purge_dead_eh_edges (gimple_bb (def_stmt
));
1054 update_stmt (def_stmt
);
1056 else if (is_gimple_call (def_stmt
))
1058 int flags
= gimple_call_flags (def_stmt
);
1060 /* Don't optimize away calls that have side-effects. */
1061 if ((flags
& (ECF_CONST
|ECF_PURE
)) == 0
1062 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
1064 if (update_call_from_tree (&gsi
, val
)
1065 && maybe_clean_or_replace_eh_stmt (def_stmt
, gsi_stmt (gsi
)))
1066 gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi
)));
1068 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
1070 gimple new_stmt
= gimple_build_assign (name
, val
);
1071 gimple_stmt_iterator gsi2
;
1072 SSA_NAME_DEF_STMT (name
) = new_stmt
;
1073 gsi2
= gsi_after_labels (gimple_bb (def_stmt
));
1074 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
1075 remove_phi_node (&gsi
, false);
1078 something_changed
= true;
1081 /* Propagate into all uses and fold. */
1084 gimple_stmt_iterator i
;
1086 /* Propagate known values into PHI nodes. */
1088 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
1089 replace_phi_args_in (gsi_stmt (i
), get_value_fn
);
1091 /* Propagate known values into stmts. Do a backward walk if
1092 do_dce is true. In some case it exposes
1093 more trivially deletable stmts to walk backward. */
1094 for (i
= (do_dce
? gsi_last_bb (bb
) : gsi_start_bb (bb
)); !gsi_end_p (i
);)
1097 gimple stmt
= gsi_stmt (i
);
1099 enum gimple_code code
= gimple_code (stmt
);
1100 gimple_stmt_iterator oldi
;
1108 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1109 range information for names and they are discarded
1112 if (code
== GIMPLE_ASSIGN
1113 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
1116 /* No point propagating into a stmt whose result is not used,
1117 but instead we might be able to remove a trivially dead stmt.
1118 Don't do this when called from VRP, since the SSA_NAME which
1119 is going to be released could be still referenced in VRP
1122 && gimple_get_lhs (stmt
)
1123 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1124 && has_zero_uses (gimple_get_lhs (stmt
))
1125 && !stmt_could_throw_p (stmt
)
1126 && !gimple_has_side_effects (stmt
))
1128 gimple_stmt_iterator i2
;
1130 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1132 fprintf (dump_file
, "Removing dead stmt ");
1133 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1134 fprintf (dump_file
, "\n");
1136 prop_stats
.num_dce
++;
1137 i2
= gsi_for_stmt (stmt
);
1138 gsi_remove (&i2
, true);
1139 release_defs (stmt
);
1143 /* Replace the statement with its folded version and mark it
1145 did_replace
= false;
1146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1148 fprintf (dump_file
, "Folding statement: ");
1149 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1154 /* Some statements may be simplified using propagator
1155 specific information. Do this before propagating
1156 into the stmt to not disturb pass specific information. */
1158 && (*fold_fn
)(&oldi
))
1161 prop_stats
.num_stmts_folded
++;
1162 stmt
= gsi_stmt (oldi
);
1166 /* Replace real uses in the statement. */
1168 did_replace
|= replace_uses_in (stmt
, get_value_fn
);
1170 /* If we made a replacement, fold the statement. */
1177 stmt
= gsi_stmt (oldi
);
1179 /* If we cleaned up EH information from the statement,
1181 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1182 gimple_purge_dead_eh_edges (bb
);
1184 if (is_gimple_assign (stmt
)
1185 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1186 == GIMPLE_SINGLE_RHS
))
1188 tree rhs
= gimple_assign_rhs1 (stmt
);
1190 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1191 recompute_tree_invariant_for_addr_expr (rhs
);
1194 /* Determine what needs to be done to update the SSA form. */
1196 if (!is_gimple_debug (stmt
))
1197 something_changed
= true;
1200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1204 fprintf (dump_file
, "Folded into: ");
1205 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1206 fprintf (dump_file
, "\n");
1209 fprintf (dump_file
, "Not folded\n");
1214 statistics_counter_event (cfun
, "Constants propagated",
1215 prop_stats
.num_const_prop
);
1216 statistics_counter_event (cfun
, "Copies propagated",
1217 prop_stats
.num_copy_prop
);
1218 statistics_counter_event (cfun
, "Statements folded",
1219 prop_stats
.num_stmts_folded
);
1220 statistics_counter_event (cfun
, "Statements deleted",
1221 prop_stats
.num_dce
);
1222 return something_changed
;
1225 #include "gt-tree-ssa-propagate.h"