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"
32 #include "gimple-pretty-print.h"
34 #include "tree-dump.h"
35 #include "tree-flow.h"
36 #include "tree-pass.h"
37 #include "tree-ssa-propagate.h"
38 #include "langhooks.h"
40 #include "value-prof.h"
43 /* This file implements a generic value propagation engine based on
44 the same propagation used by the SSA-CCP algorithm [1].
46 Propagation is performed by simulating the execution of every
47 statement that produces the value being propagated. Simulation
50 1- Initially, all edges of the CFG are marked not executable and
51 the CFG worklist is seeded with all the statements in the entry
52 basic block (block 0).
54 2- Every statement S is simulated with a call to the call-back
55 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
58 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
59 interest and does not affect any of the work lists.
61 SSA_PROP_VARYING: The value produced by S cannot be determined
62 at compile time. Further simulation of S is not required.
63 If S is a conditional jump, all the outgoing edges for the
64 block are considered executable and added to the work
67 SSA_PROP_INTERESTING: S produces a value that can be computed
68 at compile time. Its result can be propagated into the
69 statements that feed from S. Furthermore, if S is a
70 conditional jump, only the edge known to be taken is added
71 to the work list. Edges that are known not to execute are
74 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
75 return value from SSA_PROP_VISIT_PHI has the same semantics as
78 4- Three work lists are kept. Statements are only added to these
79 lists if they produce one of SSA_PROP_INTERESTING or
82 CFG_BLOCKS contains the list of blocks to be simulated.
83 Blocks are added to this list if their incoming edges are
86 VARYING_SSA_EDGES contains the list of statements that feed
87 from statements that produce an SSA_PROP_VARYING result.
88 These are simulated first to speed up processing.
90 INTERESTING_SSA_EDGES contains the list of statements that
91 feed from statements that produce an SSA_PROP_INTERESTING
94 5- Simulation terminates when all three work lists are drained.
96 Before calling ssa_propagate, it is important to clear
97 prop_simulate_again_p for all the statements in the program that
98 should be simulated. This initialization allows an implementation
99 to specify which statements should never be simulated.
101 It is also important to compute def-use information before calling
106 [1] Constant propagation with conditional branches,
107 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
109 [2] Building an Optimizing Compiler,
110 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
112 [3] Advanced Compiler Design and Implementation,
113 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
115 /* Function pointers used to parameterize the propagation engine. */
116 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
117 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
119 /* Keep track of statements that have been added to one of the SSA
120 edges worklists. This flag is used to avoid visiting statements
121 unnecessarily when draining an SSA edge worklist. If while
122 simulating a basic block, we find a statement with
123 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
124 processing from visiting it again.
126 NOTE: users of the propagation engine are not allowed to use
127 the GF_PLF_1 flag. */
128 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
130 /* A bitmap to keep track of executable blocks in the CFG. */
131 static sbitmap executable_blocks
;
133 /* Array of control flow edges on the worklist. */
134 static VEC(basic_block
,heap
) *cfg_blocks
;
136 static unsigned int cfg_blocks_num
= 0;
137 static int cfg_blocks_tail
;
138 static int cfg_blocks_head
;
140 static sbitmap bb_in_list
;
142 /* Worklist of SSA edges which will need reexamination as their
143 definition has changed. SSA edges are def-use edges in the SSA
144 web. For each D-U edge, we store the target statement or PHI node
146 static GTY(()) VEC(gimple
,gc
) *interesting_ssa_edges
;
148 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
149 list of SSA edges is split into two. One contains all SSA edges
150 who need to be reexamined because their lattice value changed to
151 varying (this worklist), and the other contains all other SSA edges
152 to be reexamined (INTERESTING_SSA_EDGES).
154 Since most values in the program are VARYING, the ideal situation
155 is to move them to that lattice value as quickly as possible.
156 Thus, it doesn't make sense to process any other type of lattice
157 value until all VARYING values are propagated fully, which is one
158 thing using the VARYING worklist achieves. In addition, if we
159 don't use a separate worklist for VARYING edges, we end up with
160 situations where lattice values move from
161 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
162 static GTY(()) VEC(gimple
,gc
) *varying_ssa_edges
;
165 /* Return true if the block worklist empty. */
168 cfg_blocks_empty_p (void)
170 return (cfg_blocks_num
== 0);
174 /* Add a basic block to the worklist. The block must not be already
175 in the worklist, and it must not be the ENTRY or EXIT block. */
178 cfg_blocks_add (basic_block bb
)
182 gcc_assert (bb
!= ENTRY_BLOCK_PTR
&& bb
!= EXIT_BLOCK_PTR
);
183 gcc_assert (!TEST_BIT (bb_in_list
, bb
->index
));
185 if (cfg_blocks_empty_p ())
187 cfg_blocks_tail
= cfg_blocks_head
= 0;
193 if (cfg_blocks_num
> VEC_length (basic_block
, cfg_blocks
))
195 /* We have to grow the array now. Adjust to queue to occupy
196 the full space of the original array. We do not need to
197 initialize the newly allocated portion of the array
198 because we keep track of CFG_BLOCKS_HEAD and
200 cfg_blocks_tail
= VEC_length (basic_block
, cfg_blocks
);
202 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 2 * cfg_blocks_tail
);
204 /* Minor optimization: we prefer to see blocks with more
205 predecessors later, because there is more of a chance that
206 the incoming edges will be executable. */
207 else if (EDGE_COUNT (bb
->preds
)
208 >= EDGE_COUNT (VEC_index (basic_block
, cfg_blocks
,
209 cfg_blocks_head
)->preds
))
210 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1)
211 % VEC_length (basic_block
, cfg_blocks
));
214 if (cfg_blocks_head
== 0)
215 cfg_blocks_head
= VEC_length (basic_block
, cfg_blocks
);
221 VEC_replace (basic_block
, cfg_blocks
,
222 head
? cfg_blocks_head
: cfg_blocks_tail
,
224 SET_BIT (bb_in_list
, bb
->index
);
228 /* Remove a block from the worklist. */
231 cfg_blocks_get (void)
235 bb
= VEC_index (basic_block
, cfg_blocks
, cfg_blocks_head
);
237 gcc_assert (!cfg_blocks_empty_p ());
240 cfg_blocks_head
= ((cfg_blocks_head
+ 1)
241 % VEC_length (basic_block
, cfg_blocks
));
243 RESET_BIT (bb_in_list
, bb
->index
);
249 /* We have just defined a new value for VAR. If IS_VARYING is true,
250 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
251 them to INTERESTING_SSA_EDGES. */
254 add_ssa_edge (tree var
, bool is_varying
)
256 imm_use_iterator iter
;
259 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
261 gimple use_stmt
= USE_STMT (use_p
);
263 if (prop_simulate_again_p (use_stmt
)
264 && !gimple_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
266 gimple_set_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
, true);
268 VEC_safe_push (gimple
, gc
, varying_ssa_edges
, use_stmt
);
270 VEC_safe_push (gimple
, gc
, interesting_ssa_edges
, use_stmt
);
276 /* Add edge E to the control flow worklist. */
279 add_control_edge (edge e
)
281 basic_block bb
= e
->dest
;
282 if (bb
== EXIT_BLOCK_PTR
)
285 /* If the edge had already been executed, skip it. */
286 if (e
->flags
& EDGE_EXECUTABLE
)
289 e
->flags
|= EDGE_EXECUTABLE
;
291 /* If the block is already in the list, we're done. */
292 if (TEST_BIT (bb_in_list
, bb
->index
))
297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
298 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
299 e
->src
->index
, e
->dest
->index
);
303 /* Simulate the execution of STMT and update the work lists accordingly. */
306 simulate_stmt (gimple stmt
)
308 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
309 edge taken_edge
= NULL
;
310 tree output_name
= NULL_TREE
;
312 /* Don't bother visiting statements that are already
313 considered varying by the propagator. */
314 if (!prop_simulate_again_p (stmt
))
317 if (gimple_code (stmt
) == GIMPLE_PHI
)
319 val
= ssa_prop_visit_phi (stmt
);
320 output_name
= gimple_phi_result (stmt
);
323 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
325 if (val
== SSA_PROP_VARYING
)
327 prop_set_simulate_again (stmt
, false);
329 /* If the statement produced a new varying value, add the SSA
330 edges coming out of OUTPUT_NAME. */
332 add_ssa_edge (output_name
, true);
334 /* If STMT transfers control out of its basic block, add
335 all outgoing edges to the work list. */
336 if (stmt_ends_bb_p (stmt
))
340 basic_block bb
= gimple_bb (stmt
);
341 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
342 add_control_edge (e
);
345 else if (val
== SSA_PROP_INTERESTING
)
347 /* If the statement produced new value, add the SSA edges coming
348 out of OUTPUT_NAME. */
350 add_ssa_edge (output_name
, false);
352 /* If we know which edge is going to be taken out of this block,
353 add it to the CFG work list. */
355 add_control_edge (taken_edge
);
359 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
360 drain. This pops statements off the given WORKLIST and processes
361 them until there are no more statements on WORKLIST.
362 We take a pointer to WORKLIST because it may be reallocated when an
363 SSA edge is added to it in simulate_stmt. */
366 process_ssa_edge_worklist (VEC(gimple
,gc
) **worklist
)
368 /* Drain the entire worklist. */
369 while (VEC_length (gimple
, *worklist
) > 0)
373 /* Pull the statement to simulate off the worklist. */
374 gimple stmt
= VEC_pop (gimple
, *worklist
);
376 /* If this statement was already visited by simulate_block, then
377 we don't need to visit it again here. */
378 if (!gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
381 /* STMT is no longer in a worklist. */
382 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
384 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
386 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
387 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
390 bb
= gimple_bb (stmt
);
392 /* PHI nodes are always visited, regardless of whether or not
393 the destination block is executable. Otherwise, visit the
394 statement only if its block is marked executable. */
395 if (gimple_code (stmt
) == GIMPLE_PHI
396 || TEST_BIT (executable_blocks
, bb
->index
))
397 simulate_stmt (stmt
);
402 /* Simulate the execution of BLOCK. Evaluate the statement associated
403 with each variable reference inside the block. */
406 simulate_block (basic_block block
)
408 gimple_stmt_iterator gsi
;
410 /* There is nothing to do for the exit block. */
411 if (block
== EXIT_BLOCK_PTR
)
414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
415 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
417 /* Always simulate PHI nodes, even if we have simulated this block
419 for (gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
420 simulate_stmt (gsi_stmt (gsi
));
422 /* If this is the first time we've simulated this block, then we
423 must simulate each of its statements. */
424 if (!TEST_BIT (executable_blocks
, block
->index
))
426 gimple_stmt_iterator j
;
427 unsigned int normal_edge_count
;
431 /* Note that we have simulated this block. */
432 SET_BIT (executable_blocks
, block
->index
);
434 for (j
= gsi_start_bb (block
); !gsi_end_p (j
); gsi_next (&j
))
436 gimple stmt
= gsi_stmt (j
);
438 /* If this statement is already in the worklist then
439 "cancel" it. The reevaluation implied by the worklist
440 entry will produce the same value we generate here and
441 thus reevaluating it again from the worklist is
443 if (gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
444 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
446 simulate_stmt (stmt
);
449 /* We can not predict when abnormal and EH edges will be executed, so
450 once a block is considered executable, we consider any
451 outgoing abnormal edges as executable.
453 TODO: This is not exactly true. Simplifying statement might
454 prove it non-throwing and also computed goto can be handled
455 when destination is known.
457 At the same time, if this block has only one successor that is
458 reached by non-abnormal edges, then add that successor to the
460 normal_edge_count
= 0;
462 FOR_EACH_EDGE (e
, ei
, block
->succs
)
464 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
465 add_control_edge (e
);
473 if (normal_edge_count
== 1)
474 add_control_edge (normal_edge
);
479 /* Initialize local data structures and work lists. */
488 /* Worklists of SSA edges. */
489 interesting_ssa_edges
= VEC_alloc (gimple
, gc
, 20);
490 varying_ssa_edges
= VEC_alloc (gimple
, gc
, 20);
492 executable_blocks
= sbitmap_alloc (last_basic_block
);
493 sbitmap_zero (executable_blocks
);
495 bb_in_list
= sbitmap_alloc (last_basic_block
);
496 sbitmap_zero (bb_in_list
);
498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
499 dump_immediate_uses (dump_file
);
501 cfg_blocks
= VEC_alloc (basic_block
, heap
, 20);
502 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 20);
504 /* Initially assume that every edge in the CFG is not executable.
505 (including the edges coming out of ENTRY_BLOCK_PTR). */
508 gimple_stmt_iterator si
;
510 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
511 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
513 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
514 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
516 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
517 e
->flags
&= ~EDGE_EXECUTABLE
;
520 /* Seed the algorithm by adding the successors of the entry block to the
522 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
523 add_control_edge (e
);
527 /* Free allocated storage. */
532 VEC_free (gimple
, gc
, interesting_ssa_edges
);
533 VEC_free (gimple
, gc
, varying_ssa_edges
);
534 VEC_free (basic_block
, heap
, cfg_blocks
);
536 sbitmap_free (bb_in_list
);
537 sbitmap_free (executable_blocks
);
541 /* Return true if EXPR is an acceptable right-hand-side for a
542 GIMPLE assignment. We validate the entire tree, not just
543 the root node, thus catching expressions that embed complex
544 operands that are not permitted in GIMPLE. This function
545 is needed because the folding routines in fold-const.c
546 may return such expressions in some cases, e.g., an array
547 access with an embedded index addition. It may make more
548 sense to have folding routines that are sensitive to the
549 constraints on GIMPLE operands, rather than abandoning any
550 any attempt to fold if the usual folding turns out to be too
554 valid_gimple_rhs_p (tree expr
)
556 enum tree_code code
= TREE_CODE (expr
);
558 switch (TREE_CODE_CLASS (code
))
560 case tcc_declaration
:
561 if (!is_gimple_variable (expr
))
566 /* All constants are ok. */
571 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
572 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
577 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
587 if (is_gimple_min_invariant (expr
))
589 t
= TREE_OPERAND (expr
, 0);
590 while (handled_component_p (t
))
592 /* ??? More checks needed, see the GIMPLE verifier. */
593 if ((TREE_CODE (t
) == ARRAY_REF
594 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
595 && !is_gimple_val (TREE_OPERAND (t
, 1)))
597 t
= TREE_OPERAND (t
, 0);
599 if (!is_gimple_id (t
))
605 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
607 if (((code
== VEC_COND_EXPR
|| code
== COND_EXPR
)
608 ? !is_gimple_condexpr (TREE_OPERAND (expr
, 0))
609 : !is_gimple_val (TREE_OPERAND (expr
, 0)))
610 || !is_gimple_val (TREE_OPERAND (expr
, 1))
611 || !is_gimple_val (TREE_OPERAND (expr
, 2)))
622 case tcc_exceptional
:
623 if (code
!= SSA_NAME
)
635 /* Return true if EXPR is a CALL_EXPR suitable for representation
636 as a single GIMPLE_CALL statement. If the arguments require
637 further gimplification, return false. */
640 valid_gimple_call_p (tree expr
)
644 if (TREE_CODE (expr
) != CALL_EXPR
)
647 nargs
= call_expr_nargs (expr
);
648 for (i
= 0; i
< nargs
; i
++)
650 tree arg
= CALL_EXPR_ARG (expr
, i
);
651 if (is_gimple_reg_type (arg
))
653 if (!is_gimple_val (arg
))
657 if (!is_gimple_lvalue (arg
))
665 /* Make SSA names defined by OLD_STMT point to NEW_STMT
666 as their defining statement. */
669 move_ssa_defining_stmt_for_defs (gimple new_stmt
, gimple old_stmt
)
674 if (gimple_in_ssa_p (cfun
))
676 /* Make defined SSA_NAMEs point to the new
677 statement as their definition. */
678 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
680 if (TREE_CODE (var
) == SSA_NAME
)
681 SSA_NAME_DEF_STMT (var
) = new_stmt
;
686 /* Helper function for update_gimple_call and update_call_from_tree.
687 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
690 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple new_stmt
,
693 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
694 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
695 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
696 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
697 gimple_set_location (new_stmt
, gimple_location (stmt
));
698 if (gimple_block (new_stmt
) == NULL_TREE
)
699 gimple_set_block (new_stmt
, gimple_block (stmt
));
700 gsi_replace (si_p
, new_stmt
, false);
703 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
704 with number of arguments NARGS, where the arguments in GIMPLE form
705 follow NARGS argument. */
708 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
711 gimple new_stmt
, stmt
= gsi_stmt (*si_p
);
713 gcc_assert (is_gimple_call (stmt
));
714 va_start (ap
, nargs
);
715 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
716 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
721 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
722 value of EXPR, which is expected to be the result of folding the
723 call. This can only be done if EXPR is a CALL_EXPR with valid
724 GIMPLE operands as arguments, or if it is a suitable RHS expression
725 for a GIMPLE_ASSIGN. More complex expressions will require
726 gimplification, which will introduce addtional statements. In this
727 event, no update is performed, and the function returns false.
728 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
729 replace the statement at *SI_P with an entirely new statement.
730 The new statement need not be a call, e.g., if the original call
731 folded to a constant. */
734 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
736 gimple stmt
= gsi_stmt (*si_p
);
738 if (valid_gimple_call_p (expr
))
740 /* The call has simplified to another call. */
741 tree fn
= CALL_EXPR_FN (expr
);
743 unsigned nargs
= call_expr_nargs (expr
);
744 VEC(tree
, heap
) *args
= NULL
;
749 args
= VEC_alloc (tree
, heap
, nargs
);
750 VEC_safe_grow (tree
, heap
, args
, nargs
);
752 for (i
= 0; i
< nargs
; i
++)
753 VEC_replace (tree
, args
, i
, CALL_EXPR_ARG (expr
, i
));
756 new_stmt
= gimple_build_call_vec (fn
, args
);
757 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
758 VEC_free (tree
, heap
, args
);
762 else if (valid_gimple_rhs_p (expr
))
764 tree lhs
= gimple_call_lhs (stmt
);
767 /* The call has simplified to an expression
768 that cannot be represented as a GIMPLE_CALL. */
771 /* A value is expected.
772 Introduce a new GIMPLE_ASSIGN statement. */
773 STRIP_USELESS_TYPE_CONVERSION (expr
);
774 new_stmt
= gimple_build_assign (lhs
, expr
);
775 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
776 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
777 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
779 else if (!TREE_SIDE_EFFECTS (expr
))
781 /* No value is expected, and EXPR has no effect.
782 Replace it with an empty statement. */
783 new_stmt
= gimple_build_nop ();
784 if (gimple_in_ssa_p (cfun
))
786 unlink_stmt_vdef (stmt
);
792 /* No value is expected, but EXPR has an effect,
793 e.g., it could be a reference to a volatile
794 variable. Create an assignment statement
795 with a dummy (unused) lhs variable. */
796 STRIP_USELESS_TYPE_CONVERSION (expr
);
797 lhs
= create_tmp_var (TREE_TYPE (expr
), NULL
);
798 new_stmt
= gimple_build_assign (lhs
, expr
);
799 add_referenced_var (lhs
);
800 if (gimple_in_ssa_p (cfun
))
801 lhs
= make_ssa_name (lhs
, new_stmt
);
802 gimple_assign_set_lhs (new_stmt
, lhs
);
803 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
804 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
805 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
807 gimple_set_location (new_stmt
, gimple_location (stmt
));
808 gsi_replace (si_p
, new_stmt
, false);
812 /* The call simplified to an expression that is
813 not a valid GIMPLE RHS. */
818 /* Entry point to the propagation engine.
820 VISIT_STMT is called for every statement visited.
821 VISIT_PHI is called for every PHI node visited. */
824 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
825 ssa_prop_visit_phi_fn visit_phi
)
827 ssa_prop_visit_stmt
= visit_stmt
;
828 ssa_prop_visit_phi
= visit_phi
;
832 /* Iterate until the worklists are empty. */
833 while (!cfg_blocks_empty_p ()
834 || VEC_length (gimple
, interesting_ssa_edges
) > 0
835 || VEC_length (gimple
, varying_ssa_edges
) > 0)
837 if (!cfg_blocks_empty_p ())
839 /* Pull the next block to simulate off the worklist. */
840 basic_block dest_block
= cfg_blocks_get ();
841 simulate_block (dest_block
);
844 /* In order to move things to varying as quickly as
845 possible,process the VARYING_SSA_EDGES worklist first. */
846 process_ssa_edge_worklist (&varying_ssa_edges
);
848 /* Now process the INTERESTING_SSA_EDGES worklist. */
849 process_ssa_edge_worklist (&interesting_ssa_edges
);
856 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
857 is a non-volatile pointer dereference, a structure reference or a
858 reference to a single _DECL. Ignore volatile memory references
859 because they are not interesting for the optimizers. */
862 stmt_makes_single_store (gimple stmt
)
866 if (gimple_code (stmt
) != GIMPLE_ASSIGN
867 && gimple_code (stmt
) != GIMPLE_CALL
)
870 if (!gimple_vdef (stmt
))
873 lhs
= gimple_get_lhs (stmt
);
875 /* A call statement may have a null LHS. */
879 return (!TREE_THIS_VOLATILE (lhs
)
881 || REFERENCE_CLASS_P (lhs
)));
885 /* Propagation statistics. */
890 long num_stmts_folded
;
894 static struct prop_stats_d prop_stats
;
896 /* Replace USE references in statement STMT with the values stored in
897 PROP_VALUE. Return true if at least one reference was replaced. */
900 replace_uses_in (gimple stmt
, ssa_prop_get_value_fn get_value
)
902 bool replaced
= false;
906 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
908 tree tuse
= USE_FROM_PTR (use
);
909 tree val
= (*get_value
) (tuse
);
911 if (val
== tuse
|| val
== NULL_TREE
)
914 if (gimple_code (stmt
) == GIMPLE_ASM
915 && !may_propagate_copy_into_asm (tuse
))
918 if (!may_propagate_copy (tuse
, val
))
921 if (TREE_CODE (val
) != SSA_NAME
)
922 prop_stats
.num_const_prop
++;
924 prop_stats
.num_copy_prop
++;
926 propagate_value (use
, val
);
935 /* Replace propagated values into all the arguments for PHI using the
936 values from PROP_VALUE. */
939 replace_phi_args_in (gimple phi
, ssa_prop_get_value_fn get_value
)
942 bool replaced
= false;
944 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
946 fprintf (dump_file
, "Folding PHI node: ");
947 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
950 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
952 tree arg
= gimple_phi_arg_def (phi
, i
);
954 if (TREE_CODE (arg
) == SSA_NAME
)
956 tree val
= (*get_value
) (arg
);
958 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
960 if (TREE_CODE (val
) != SSA_NAME
)
961 prop_stats
.num_const_prop
++;
963 prop_stats
.num_copy_prop
++;
965 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
968 /* If we propagated a copy and this argument flows
969 through an abnormal edge, update the replacement
971 if (TREE_CODE (val
) == SSA_NAME
972 && gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_ABNORMAL
)
973 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
981 fprintf (dump_file
, "No folding possible\n");
984 fprintf (dump_file
, "Folded into: ");
985 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
986 fprintf (dump_file
, "\n");
992 /* Perform final substitution and folding of propagated values.
994 PROP_VALUE[I] contains the single value that should be substituted
995 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
998 If FOLD_FN is non-NULL the function will be invoked on all statements
999 before propagating values for pass specific simplification.
1001 DO_DCE is true if trivially dead stmts can be removed.
1003 If DO_DCE is true, the statements within a BB are walked from
1004 last to first element. Otherwise we scan from first to last element.
1006 Return TRUE when something changed. */
1009 substitute_and_fold (ssa_prop_get_value_fn get_value_fn
,
1010 ssa_prop_fold_stmt_fn fold_fn
,
1014 bool something_changed
= false;
1017 if (!get_value_fn
&& !fold_fn
)
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1021 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1023 memset (&prop_stats
, 0, sizeof (prop_stats
));
1025 /* Substitute lattice values at definition sites. */
1027 for (i
= 1; i
< num_ssa_names
; ++i
)
1029 tree name
= ssa_name (i
);
1032 gimple_stmt_iterator gsi
;
1035 || !is_gimple_reg (name
))
1038 def_stmt
= SSA_NAME_DEF_STMT (name
);
1039 if (gimple_nop_p (def_stmt
)
1040 /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */
1041 || (gimple_assign_single_p (def_stmt
)
1042 && gimple_assign_rhs_code (def_stmt
) == ASSERT_EXPR
)
1043 || !(val
= (*get_value_fn
) (name
))
1044 || !may_propagate_copy (name
, val
))
1047 gsi
= gsi_for_stmt (def_stmt
);
1048 if (is_gimple_assign (def_stmt
))
1050 gimple_assign_set_rhs_with_ops (&gsi
, TREE_CODE (val
),
1052 gcc_assert (gsi_stmt (gsi
) == def_stmt
);
1053 if (maybe_clean_eh_stmt (def_stmt
))
1054 gimple_purge_dead_eh_edges (gimple_bb (def_stmt
));
1055 update_stmt (def_stmt
);
1057 else if (is_gimple_call (def_stmt
))
1059 int flags
= gimple_call_flags (def_stmt
);
1061 /* Don't optimize away calls that have side-effects. */
1062 if ((flags
& (ECF_CONST
|ECF_PURE
)) == 0
1063 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
1065 if (update_call_from_tree (&gsi
, val
)
1066 && maybe_clean_or_replace_eh_stmt (def_stmt
, gsi_stmt (gsi
)))
1067 gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi
)));
1069 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
1071 gimple new_stmt
= gimple_build_assign (name
, val
);
1072 gimple_stmt_iterator gsi2
;
1073 SSA_NAME_DEF_STMT (name
) = new_stmt
;
1074 gsi2
= gsi_after_labels (gimple_bb (def_stmt
));
1075 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
1076 remove_phi_node (&gsi
, false);
1079 something_changed
= true;
1082 /* Propagate into all uses and fold. */
1085 gimple_stmt_iterator i
;
1087 /* Propagate known values into PHI nodes. */
1089 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
1090 replace_phi_args_in (gsi_stmt (i
), get_value_fn
);
1092 /* Propagate known values into stmts. Do a backward walk if
1093 do_dce is true. In some case it exposes
1094 more trivially deletable stmts to walk backward. */
1095 for (i
= (do_dce
? gsi_last_bb (bb
) : gsi_start_bb (bb
)); !gsi_end_p (i
);)
1098 gimple stmt
= gsi_stmt (i
);
1100 enum gimple_code code
= gimple_code (stmt
);
1101 gimple_stmt_iterator oldi
;
1109 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1110 range information for names and they are discarded
1113 if (code
== GIMPLE_ASSIGN
1114 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
1117 /* No point propagating into a stmt whose result is not used,
1118 but instead we might be able to remove a trivially dead stmt.
1119 Don't do this when called from VRP, since the SSA_NAME which
1120 is going to be released could be still referenced in VRP
1123 && gimple_get_lhs (stmt
)
1124 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1125 && has_zero_uses (gimple_get_lhs (stmt
))
1126 && !stmt_could_throw_p (stmt
)
1127 && !gimple_has_side_effects (stmt
))
1129 gimple_stmt_iterator i2
;
1131 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1133 fprintf (dump_file
, "Removing dead stmt ");
1134 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1135 fprintf (dump_file
, "\n");
1137 prop_stats
.num_dce
++;
1138 i2
= gsi_for_stmt (stmt
);
1139 gsi_remove (&i2
, true);
1140 release_defs (stmt
);
1144 /* Replace the statement with its folded version and mark it
1146 did_replace
= false;
1147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1149 fprintf (dump_file
, "Folding statement: ");
1150 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1155 /* Some statements may be simplified using propagator
1156 specific information. Do this before propagating
1157 into the stmt to not disturb pass specific information. */
1159 && (*fold_fn
)(&oldi
))
1162 prop_stats
.num_stmts_folded
++;
1163 stmt
= gsi_stmt (oldi
);
1167 /* Replace real uses in the statement. */
1169 did_replace
|= replace_uses_in (stmt
, get_value_fn
);
1171 /* If we made a replacement, fold the statement. */
1178 stmt
= gsi_stmt (oldi
);
1180 /* If we cleaned up EH information from the statement,
1182 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1183 gimple_purge_dead_eh_edges (bb
);
1185 if (is_gimple_assign (stmt
)
1186 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1187 == GIMPLE_SINGLE_RHS
))
1189 tree rhs
= gimple_assign_rhs1 (stmt
);
1191 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1192 recompute_tree_invariant_for_addr_expr (rhs
);
1195 /* Determine what needs to be done to update the SSA form. */
1197 if (!is_gimple_debug (stmt
))
1198 something_changed
= true;
1201 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1205 fprintf (dump_file
, "Folded into: ");
1206 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1207 fprintf (dump_file
, "\n");
1210 fprintf (dump_file
, "Not folded\n");
1215 statistics_counter_event (cfun
, "Constants propagated",
1216 prop_stats
.num_const_prop
);
1217 statistics_counter_event (cfun
, "Copies propagated",
1218 prop_stats
.num_copy_prop
);
1219 statistics_counter_event (cfun
, "Statements folded",
1220 prop_stats
.num_stmts_folded
);
1221 statistics_counter_event (cfun
, "Statements deleted",
1222 prop_stats
.num_dce
);
1223 return something_changed
;
1226 #include "gt-tree-ssa-propagate.h"