1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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
))
612 case tcc_exceptional
:
613 if (code
!= SSA_NAME
)
625 /* Return true if EXPR is a CALL_EXPR suitable for representation
626 as a single GIMPLE_CALL statement. If the arguments require
627 further gimplification, return false. */
630 valid_gimple_call_p (tree expr
)
634 if (TREE_CODE (expr
) != CALL_EXPR
)
637 nargs
= call_expr_nargs (expr
);
638 for (i
= 0; i
< nargs
; i
++)
640 tree arg
= CALL_EXPR_ARG (expr
, i
);
641 if (is_gimple_reg_type (arg
))
643 if (!is_gimple_val (arg
))
647 if (!is_gimple_lvalue (arg
))
655 /* Make SSA names defined by OLD_STMT point to NEW_STMT
656 as their defining statement. */
659 move_ssa_defining_stmt_for_defs (gimple new_stmt
, gimple old_stmt
)
664 if (gimple_in_ssa_p (cfun
))
666 /* Make defined SSA_NAMEs point to the new
667 statement as their definition. */
668 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
670 if (TREE_CODE (var
) == SSA_NAME
)
671 SSA_NAME_DEF_STMT (var
) = new_stmt
;
676 /* Helper function for update_gimple_call and update_call_from_tree.
677 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
680 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple new_stmt
,
683 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
684 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
685 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
686 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
687 gimple_set_location (new_stmt
, gimple_location (stmt
));
688 if (gimple_block (new_stmt
) == NULL_TREE
)
689 gimple_set_block (new_stmt
, gimple_block (stmt
));
690 gsi_replace (si_p
, new_stmt
, false);
693 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
694 with number of arguments NARGS, where the arguments in GIMPLE form
695 follow NARGS argument. */
698 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
701 gimple new_stmt
, stmt
= gsi_stmt (*si_p
);
703 gcc_assert (is_gimple_call (stmt
));
704 va_start (ap
, nargs
);
705 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
706 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
711 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
712 value of EXPR, which is expected to be the result of folding the
713 call. This can only be done if EXPR is a CALL_EXPR with valid
714 GIMPLE operands as arguments, or if it is a suitable RHS expression
715 for a GIMPLE_ASSIGN. More complex expressions will require
716 gimplification, which will introduce addtional statements. In this
717 event, no update is performed, and the function returns false.
718 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
719 replace the statement at *SI_P with an entirely new statement.
720 The new statement need not be a call, e.g., if the original call
721 folded to a constant. */
724 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
726 gimple stmt
= gsi_stmt (*si_p
);
728 if (valid_gimple_call_p (expr
))
730 /* The call has simplified to another call. */
731 tree fn
= CALL_EXPR_FN (expr
);
733 unsigned nargs
= call_expr_nargs (expr
);
734 VEC(tree
, heap
) *args
= NULL
;
739 args
= VEC_alloc (tree
, heap
, nargs
);
740 VEC_safe_grow (tree
, heap
, args
, nargs
);
742 for (i
= 0; i
< nargs
; i
++)
743 VEC_replace (tree
, args
, i
, CALL_EXPR_ARG (expr
, i
));
746 new_stmt
= gimple_build_call_vec (fn
, args
);
747 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
748 VEC_free (tree
, heap
, args
);
752 else if (valid_gimple_rhs_p (expr
))
754 tree lhs
= gimple_call_lhs (stmt
);
757 /* The call has simplified to an expression
758 that cannot be represented as a GIMPLE_CALL. */
761 /* A value is expected.
762 Introduce a new GIMPLE_ASSIGN statement. */
763 STRIP_USELESS_TYPE_CONVERSION (expr
);
764 new_stmt
= gimple_build_assign (lhs
, expr
);
765 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
766 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
767 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
769 else if (!TREE_SIDE_EFFECTS (expr
))
771 /* No value is expected, and EXPR has no effect.
772 Replace it with an empty statement. */
773 new_stmt
= gimple_build_nop ();
774 if (gimple_in_ssa_p (cfun
))
776 unlink_stmt_vdef (stmt
);
782 /* No value is expected, but EXPR has an effect,
783 e.g., it could be a reference to a volatile
784 variable. Create an assignment statement
785 with a dummy (unused) lhs variable. */
786 STRIP_USELESS_TYPE_CONVERSION (expr
);
787 lhs
= create_tmp_var (TREE_TYPE (expr
), NULL
);
788 new_stmt
= gimple_build_assign (lhs
, expr
);
789 add_referenced_var (lhs
);
790 if (gimple_in_ssa_p (cfun
))
791 lhs
= make_ssa_name (lhs
, new_stmt
);
792 gimple_assign_set_lhs (new_stmt
, lhs
);
793 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
794 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
795 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
797 gimple_set_location (new_stmt
, gimple_location (stmt
));
798 gsi_replace (si_p
, new_stmt
, false);
802 /* The call simplified to an expression that is
803 not a valid GIMPLE RHS. */
808 /* Entry point to the propagation engine.
810 VISIT_STMT is called for every statement visited.
811 VISIT_PHI is called for every PHI node visited. */
814 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
815 ssa_prop_visit_phi_fn visit_phi
)
817 ssa_prop_visit_stmt
= visit_stmt
;
818 ssa_prop_visit_phi
= visit_phi
;
822 /* Iterate until the worklists are empty. */
823 while (!cfg_blocks_empty_p ()
824 || VEC_length (gimple
, interesting_ssa_edges
) > 0
825 || VEC_length (gimple
, varying_ssa_edges
) > 0)
827 if (!cfg_blocks_empty_p ())
829 /* Pull the next block to simulate off the worklist. */
830 basic_block dest_block
= cfg_blocks_get ();
831 simulate_block (dest_block
);
834 /* In order to move things to varying as quickly as
835 possible,process the VARYING_SSA_EDGES worklist first. */
836 process_ssa_edge_worklist (&varying_ssa_edges
);
838 /* Now process the INTERESTING_SSA_EDGES worklist. */
839 process_ssa_edge_worklist (&interesting_ssa_edges
);
846 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
847 is a non-volatile pointer dereference, a structure reference or a
848 reference to a single _DECL. Ignore volatile memory references
849 because they are not interesting for the optimizers. */
852 stmt_makes_single_store (gimple stmt
)
856 if (gimple_code (stmt
) != GIMPLE_ASSIGN
857 && gimple_code (stmt
) != GIMPLE_CALL
)
860 if (!gimple_vdef (stmt
))
863 lhs
= gimple_get_lhs (stmt
);
865 /* A call statement may have a null LHS. */
869 return (!TREE_THIS_VOLATILE (lhs
)
871 || REFERENCE_CLASS_P (lhs
)));
875 /* Propagation statistics. */
880 long num_stmts_folded
;
884 static struct prop_stats_d prop_stats
;
886 /* Replace USE references in statement STMT with the values stored in
887 PROP_VALUE. Return true if at least one reference was replaced. */
890 replace_uses_in (gimple stmt
, ssa_prop_get_value_fn get_value
)
892 bool replaced
= false;
896 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
898 tree tuse
= USE_FROM_PTR (use
);
899 tree val
= (*get_value
) (tuse
);
901 if (val
== tuse
|| val
== NULL_TREE
)
904 if (gimple_code (stmt
) == GIMPLE_ASM
905 && !may_propagate_copy_into_asm (tuse
))
908 if (!may_propagate_copy (tuse
, val
))
911 if (TREE_CODE (val
) != SSA_NAME
)
912 prop_stats
.num_const_prop
++;
914 prop_stats
.num_copy_prop
++;
916 propagate_value (use
, val
);
925 /* Replace propagated values into all the arguments for PHI using the
926 values from PROP_VALUE. */
929 replace_phi_args_in (gimple phi
, ssa_prop_get_value_fn get_value
)
932 bool replaced
= false;
934 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
936 fprintf (dump_file
, "Folding PHI node: ");
937 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
940 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
942 tree arg
= gimple_phi_arg_def (phi
, i
);
944 if (TREE_CODE (arg
) == SSA_NAME
)
946 tree val
= (*get_value
) (arg
);
948 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
950 if (TREE_CODE (val
) != SSA_NAME
)
951 prop_stats
.num_const_prop
++;
953 prop_stats
.num_copy_prop
++;
955 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
958 /* If we propagated a copy and this argument flows
959 through an abnormal edge, update the replacement
961 if (TREE_CODE (val
) == SSA_NAME
962 && gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_ABNORMAL
)
963 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
971 fprintf (dump_file
, "No folding possible\n");
974 fprintf (dump_file
, "Folded into: ");
975 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
976 fprintf (dump_file
, "\n");
982 /* Perform final substitution and folding of propagated values.
984 PROP_VALUE[I] contains the single value that should be substituted
985 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
988 If FOLD_FN is non-NULL the function will be invoked on all statements
989 before propagating values for pass specific simplification.
991 DO_DCE is true if trivially dead stmts can be removed.
993 If DO_DCE is true, the statements within a BB are walked from
994 last to first element. Otherwise we scan from first to last element.
996 Return TRUE when something changed. */
999 substitute_and_fold (ssa_prop_get_value_fn get_value_fn
,
1000 ssa_prop_fold_stmt_fn fold_fn
,
1004 bool something_changed
= false;
1007 if (!get_value_fn
&& !fold_fn
)
1010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1011 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1013 memset (&prop_stats
, 0, sizeof (prop_stats
));
1015 /* Substitute lattice values at definition sites. */
1017 for (i
= 1; i
< num_ssa_names
; ++i
)
1019 tree name
= ssa_name (i
);
1022 gimple_stmt_iterator gsi
;
1025 || !is_gimple_reg (name
))
1028 def_stmt
= SSA_NAME_DEF_STMT (name
);
1029 if (gimple_nop_p (def_stmt
)
1030 /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */
1031 || (gimple_assign_single_p (def_stmt
)
1032 && gimple_assign_rhs_code (def_stmt
) == ASSERT_EXPR
)
1033 || !(val
= (*get_value_fn
) (name
))
1034 || !may_propagate_copy (name
, val
))
1037 gsi
= gsi_for_stmt (def_stmt
);
1038 if (is_gimple_assign (def_stmt
))
1040 gimple_assign_set_rhs_with_ops (&gsi
, TREE_CODE (val
),
1042 gcc_assert (gsi_stmt (gsi
) == def_stmt
);
1043 if (maybe_clean_eh_stmt (def_stmt
))
1044 gimple_purge_dead_eh_edges (gimple_bb (def_stmt
));
1045 update_stmt (def_stmt
);
1047 else if (is_gimple_call (def_stmt
))
1049 if (update_call_from_tree (&gsi
, val
)
1050 && maybe_clean_or_replace_eh_stmt (def_stmt
, gsi_stmt (gsi
)))
1051 gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi
)));
1053 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
1055 gimple new_stmt
= gimple_build_assign (name
, val
);
1056 gimple_stmt_iterator gsi2
;
1057 SSA_NAME_DEF_STMT (name
) = new_stmt
;
1058 gsi2
= gsi_after_labels (gimple_bb (def_stmt
));
1059 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
1060 remove_phi_node (&gsi
, false);
1063 something_changed
= true;
1066 /* Propagate into all uses and fold. */
1069 gimple_stmt_iterator i
;
1071 /* Propagate known values into PHI nodes. */
1073 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
1074 replace_phi_args_in (gsi_stmt (i
), get_value_fn
);
1076 /* Propagate known values into stmts. Do a backward walk if
1077 do_dce is true. In some case it exposes
1078 more trivially deletable stmts to walk backward. */
1079 for (i
= (do_dce
? gsi_last_bb (bb
) : gsi_start_bb (bb
)); !gsi_end_p (i
);)
1082 gimple stmt
= gsi_stmt (i
);
1084 enum gimple_code code
= gimple_code (stmt
);
1085 gimple_stmt_iterator oldi
;
1093 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1094 range information for names and they are discarded
1097 if (code
== GIMPLE_ASSIGN
1098 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
1101 /* No point propagating into a stmt whose result is not used,
1102 but instead we might be able to remove a trivially dead stmt.
1103 Don't do this when called from VRP, since the SSA_NAME which
1104 is going to be released could be still referenced in VRP
1107 && gimple_get_lhs (stmt
)
1108 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1109 && has_zero_uses (gimple_get_lhs (stmt
))
1110 && !stmt_could_throw_p (stmt
)
1111 && !gimple_has_side_effects (stmt
))
1113 gimple_stmt_iterator i2
;
1115 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1117 fprintf (dump_file
, "Removing dead stmt ");
1118 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1119 fprintf (dump_file
, "\n");
1121 prop_stats
.num_dce
++;
1122 i2
= gsi_for_stmt (stmt
);
1123 gsi_remove (&i2
, true);
1124 release_defs (stmt
);
1128 /* Replace the statement with its folded version and mark it
1130 did_replace
= false;
1131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1133 fprintf (dump_file
, "Folding statement: ");
1134 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1139 /* Some statements may be simplified using propagator
1140 specific information. Do this before propagating
1141 into the stmt to not disturb pass specific information. */
1143 && (*fold_fn
)(&oldi
))
1146 prop_stats
.num_stmts_folded
++;
1147 stmt
= gsi_stmt (oldi
);
1151 /* Replace real uses in the statement. */
1153 did_replace
|= replace_uses_in (stmt
, get_value_fn
);
1155 /* If we made a replacement, fold the statement. */
1162 stmt
= gsi_stmt (oldi
);
1164 /* If we cleaned up EH information from the statement,
1166 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1167 gimple_purge_dead_eh_edges (bb
);
1169 if (is_gimple_assign (stmt
)
1170 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1171 == GIMPLE_SINGLE_RHS
))
1173 tree rhs
= gimple_assign_rhs1 (stmt
);
1175 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1176 recompute_tree_invariant_for_addr_expr (rhs
);
1179 /* Determine what needs to be done to update the SSA form. */
1181 if (!is_gimple_debug (stmt
))
1182 something_changed
= true;
1185 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1189 fprintf (dump_file
, "Folded into: ");
1190 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1191 fprintf (dump_file
, "\n");
1194 fprintf (dump_file
, "Not folded\n");
1199 statistics_counter_event (cfun
, "Constants propagated",
1200 prop_stats
.num_const_prop
);
1201 statistics_counter_event (cfun
, "Copies propagated",
1202 prop_stats
.num_copy_prop
);
1203 statistics_counter_event (cfun
, "Statements folded",
1204 prop_stats
.num_stmts_folded
);
1205 statistics_counter_event (cfun
, "Statements deleted",
1206 prop_stats
.num_dce
);
1207 return something_changed
;
1210 #include "gt-tree-ssa-propagate.h"