1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
35 #include "gimple-iterator.h"
36 #include "gimple-ssa.h"
38 #include "tree-phinodes.h"
39 #include "ssa-iterators.h"
40 #include "stringpool.h"
41 #include "tree-ssanames.h"
43 #include "tree-ssa-propagate.h"
44 #include "langhooks.h"
46 #include "value-prof.h"
48 /* This file implements a generic value propagation engine based on
49 the same propagation used by the SSA-CCP algorithm [1].
51 Propagation is performed by simulating the execution of every
52 statement that produces the value being propagated. Simulation
55 1- Initially, all edges of the CFG are marked not executable and
56 the CFG worklist is seeded with all the statements in the entry
57 basic block (block 0).
59 2- Every statement S is simulated with a call to the call-back
60 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
63 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
64 interest and does not affect any of the work lists.
66 SSA_PROP_VARYING: The value produced by S cannot be determined
67 at compile time. Further simulation of S is not required.
68 If S is a conditional jump, all the outgoing edges for the
69 block are considered executable and added to the work
72 SSA_PROP_INTERESTING: S produces a value that can be computed
73 at compile time. Its result can be propagated into the
74 statements that feed from S. Furthermore, if S is a
75 conditional jump, only the edge known to be taken is added
76 to the work list. Edges that are known not to execute are
79 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
80 return value from SSA_PROP_VISIT_PHI has the same semantics as
83 4- Three work lists are kept. Statements are only added to these
84 lists if they produce one of SSA_PROP_INTERESTING or
87 CFG_BLOCKS contains the list of blocks to be simulated.
88 Blocks are added to this list if their incoming edges are
91 VARYING_SSA_EDGES contains the list of statements that feed
92 from statements that produce an SSA_PROP_VARYING result.
93 These are simulated first to speed up processing.
95 INTERESTING_SSA_EDGES contains the list of statements that
96 feed from statements that produce an SSA_PROP_INTERESTING
99 5- Simulation terminates when all three work lists are drained.
101 Before calling ssa_propagate, it is important to clear
102 prop_simulate_again_p for all the statements in the program that
103 should be simulated. This initialization allows an implementation
104 to specify which statements should never be simulated.
106 It is also important to compute def-use information before calling
111 [1] Constant propagation with conditional branches,
112 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
114 [2] Building an Optimizing Compiler,
115 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
117 [3] Advanced Compiler Design and Implementation,
118 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
120 /* Function pointers used to parameterize the propagation engine. */
121 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
122 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
124 /* Keep track of statements that have been added to one of the SSA
125 edges worklists. This flag is used to avoid visiting statements
126 unnecessarily when draining an SSA edge worklist. If while
127 simulating a basic block, we find a statement with
128 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
129 processing from visiting it again.
131 NOTE: users of the propagation engine are not allowed to use
132 the GF_PLF_1 flag. */
133 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
135 /* A bitmap to keep track of executable blocks in the CFG. */
136 static sbitmap executable_blocks
;
138 /* Array of control flow edges on the worklist. */
139 static vec
<basic_block
> cfg_blocks
;
141 static unsigned int cfg_blocks_num
= 0;
142 static int cfg_blocks_tail
;
143 static int cfg_blocks_head
;
145 static sbitmap bb_in_list
;
147 /* Worklist of SSA edges which will need reexamination as their
148 definition has changed. SSA edges are def-use edges in the SSA
149 web. For each D-U edge, we store the target statement or PHI node
151 static GTY(()) vec
<gimple
, va_gc
> *interesting_ssa_edges
;
153 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
154 list of SSA edges is split into two. One contains all SSA edges
155 who need to be reexamined because their lattice value changed to
156 varying (this worklist), and the other contains all other SSA edges
157 to be reexamined (INTERESTING_SSA_EDGES).
159 Since most values in the program are VARYING, the ideal situation
160 is to move them to that lattice value as quickly as possible.
161 Thus, it doesn't make sense to process any other type of lattice
162 value until all VARYING values are propagated fully, which is one
163 thing using the VARYING worklist achieves. In addition, if we
164 don't use a separate worklist for VARYING edges, we end up with
165 situations where lattice values move from
166 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
167 static GTY(()) vec
<gimple
, va_gc
> *varying_ssa_edges
;
170 /* Return true if the block worklist empty. */
173 cfg_blocks_empty_p (void)
175 return (cfg_blocks_num
== 0);
179 /* Add a basic block to the worklist. The block must not be already
180 in the worklist, and it must not be the ENTRY or EXIT block. */
183 cfg_blocks_add (basic_block bb
)
187 gcc_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
188 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
189 gcc_assert (!bitmap_bit_p (bb_in_list
, bb
->index
));
191 if (cfg_blocks_empty_p ())
193 cfg_blocks_tail
= cfg_blocks_head
= 0;
199 if (cfg_blocks_num
> cfg_blocks
.length ())
201 /* We have to grow the array now. Adjust to queue to occupy
202 the full space of the original array. We do not need to
203 initialize the newly allocated portion of the array
204 because we keep track of CFG_BLOCKS_HEAD and
206 cfg_blocks_tail
= cfg_blocks
.length ();
208 cfg_blocks
.safe_grow (2 * cfg_blocks_tail
);
210 /* Minor optimization: we prefer to see blocks with more
211 predecessors later, because there is more of a chance that
212 the incoming edges will be executable. */
213 else if (EDGE_COUNT (bb
->preds
)
214 >= EDGE_COUNT (cfg_blocks
[cfg_blocks_head
]->preds
))
215 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1) % cfg_blocks
.length ());
218 if (cfg_blocks_head
== 0)
219 cfg_blocks_head
= cfg_blocks
.length ();
225 cfg_blocks
[head
? cfg_blocks_head
: cfg_blocks_tail
] = bb
;
226 bitmap_set_bit (bb_in_list
, bb
->index
);
230 /* Remove a block from the worklist. */
233 cfg_blocks_get (void)
237 bb
= cfg_blocks
[cfg_blocks_head
];
239 gcc_assert (!cfg_blocks_empty_p ());
242 cfg_blocks_head
= ((cfg_blocks_head
+ 1) % cfg_blocks
.length ());
244 bitmap_clear_bit (bb_in_list
, bb
->index
);
250 /* We have just defined a new value for VAR. If IS_VARYING is true,
251 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
252 them to INTERESTING_SSA_EDGES. */
255 add_ssa_edge (tree var
, bool is_varying
)
257 imm_use_iterator iter
;
260 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
262 gimple use_stmt
= USE_STMT (use_p
);
264 if (prop_simulate_again_p (use_stmt
)
265 && !gimple_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
267 gimple_set_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
, true);
269 vec_safe_push (varying_ssa_edges
, use_stmt
);
271 vec_safe_push (interesting_ssa_edges
, use_stmt
);
277 /* Add edge E to the control flow worklist. */
280 add_control_edge (edge e
)
282 basic_block bb
= e
->dest
;
283 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
286 /* If the edge had already been executed, skip it. */
287 if (e
->flags
& EDGE_EXECUTABLE
)
290 e
->flags
|= EDGE_EXECUTABLE
;
292 /* If the block is already in the list, we're done. */
293 if (bitmap_bit_p (bb_in_list
, bb
->index
))
298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
299 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
300 e
->src
->index
, e
->dest
->index
);
304 /* Simulate the execution of STMT and update the work lists accordingly. */
307 simulate_stmt (gimple stmt
)
309 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
310 edge taken_edge
= NULL
;
311 tree output_name
= NULL_TREE
;
313 /* Don't bother visiting statements that are already
314 considered varying by the propagator. */
315 if (!prop_simulate_again_p (stmt
))
318 if (gimple_code (stmt
) == GIMPLE_PHI
)
320 val
= ssa_prop_visit_phi (stmt
);
321 output_name
= gimple_phi_result (stmt
);
324 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
326 if (val
== SSA_PROP_VARYING
)
328 prop_set_simulate_again (stmt
, false);
330 /* If the statement produced a new varying value, add the SSA
331 edges coming out of OUTPUT_NAME. */
333 add_ssa_edge (output_name
, true);
335 /* If STMT transfers control out of its basic block, add
336 all outgoing edges to the work list. */
337 if (stmt_ends_bb_p (stmt
))
341 basic_block bb
= gimple_bb (stmt
);
342 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
343 add_control_edge (e
);
346 else if (val
== SSA_PROP_INTERESTING
)
348 /* If the statement produced new value, add the SSA edges coming
349 out of OUTPUT_NAME. */
351 add_ssa_edge (output_name
, false);
353 /* If we know which edge is going to be taken out of this block,
354 add it to the CFG work list. */
356 add_control_edge (taken_edge
);
360 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
361 drain. This pops statements off the given WORKLIST and processes
362 them until there are no more statements on WORKLIST.
363 We take a pointer to WORKLIST because it may be reallocated when an
364 SSA edge is added to it in simulate_stmt. */
367 process_ssa_edge_worklist (vec
<gimple
, va_gc
> **worklist
)
369 /* Drain the entire worklist. */
370 while ((*worklist
)->length () > 0)
374 /* Pull the statement to simulate off the worklist. */
375 gimple stmt
= (*worklist
)->pop ();
377 /* If this statement was already visited by simulate_block, then
378 we don't need to visit it again here. */
379 if (!gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
382 /* STMT is no longer in a worklist. */
383 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
387 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
388 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
391 bb
= gimple_bb (stmt
);
393 /* PHI nodes are always visited, regardless of whether or not
394 the destination block is executable. Otherwise, visit the
395 statement only if its block is marked executable. */
396 if (gimple_code (stmt
) == GIMPLE_PHI
397 || bitmap_bit_p (executable_blocks
, bb
->index
))
398 simulate_stmt (stmt
);
403 /* Simulate the execution of BLOCK. Evaluate the statement associated
404 with each variable reference inside the block. */
407 simulate_block (basic_block block
)
409 gimple_stmt_iterator gsi
;
411 /* There is nothing to do for the exit block. */
412 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
416 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
418 /* Always simulate PHI nodes, even if we have simulated this block
420 for (gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
421 simulate_stmt (gsi_stmt (gsi
));
423 /* If this is the first time we've simulated this block, then we
424 must simulate each of its statements. */
425 if (!bitmap_bit_p (executable_blocks
, block
->index
))
427 gimple_stmt_iterator j
;
428 unsigned int normal_edge_count
;
432 /* Note that we have simulated this block. */
433 bitmap_set_bit (executable_blocks
, block
->index
);
435 for (j
= gsi_start_bb (block
); !gsi_end_p (j
); gsi_next (&j
))
437 gimple stmt
= gsi_stmt (j
);
439 /* If this statement is already in the worklist then
440 "cancel" it. The reevaluation implied by the worklist
441 entry will produce the same value we generate here and
442 thus reevaluating it again from the worklist is
444 if (gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
445 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
447 simulate_stmt (stmt
);
450 /* We can not predict when abnormal and EH edges will be executed, so
451 once a block is considered executable, we consider any
452 outgoing abnormal edges as executable.
454 TODO: This is not exactly true. Simplifying statement might
455 prove it non-throwing and also computed goto can be handled
456 when destination is known.
458 At the same time, if this block has only one successor that is
459 reached by non-abnormal edges, then add that successor to the
461 normal_edge_count
= 0;
463 FOR_EACH_EDGE (e
, ei
, block
->succs
)
465 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
466 add_control_edge (e
);
474 if (normal_edge_count
== 1)
475 add_control_edge (normal_edge
);
480 /* Initialize local data structures and work lists. */
489 /* Worklists of SSA edges. */
490 vec_alloc (interesting_ssa_edges
, 20);
491 vec_alloc (varying_ssa_edges
, 20);
493 executable_blocks
= sbitmap_alloc (last_basic_block
);
494 bitmap_clear (executable_blocks
);
496 bb_in_list
= sbitmap_alloc (last_basic_block
);
497 bitmap_clear (bb_in_list
);
499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
500 dump_immediate_uses (dump_file
);
502 cfg_blocks
.create (20);
503 cfg_blocks
.safe_grow_cleared (20);
505 /* Initially assume that every edge in the CFG is not executable.
506 (including the edges coming out of the entry block). */
509 gimple_stmt_iterator si
;
511 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
512 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
514 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
515 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
517 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
518 e
->flags
&= ~EDGE_EXECUTABLE
;
521 /* Seed the algorithm by adding the successors of the entry block to the
523 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
524 add_control_edge (e
);
528 /* Free allocated storage. */
533 vec_free (interesting_ssa_edges
);
534 vec_free (varying_ssa_edges
);
535 cfg_blocks
.release ();
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
== CONSTRUCTOR
)
627 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (expr
), i
, elt
)
628 if (!is_gimple_val (elt
))
632 if (code
!= SSA_NAME
)
637 if (code
== BIT_FIELD_REF
)
638 return is_gimple_val (TREE_OPERAND (expr
, 0));
649 /* Return true if EXPR is a CALL_EXPR suitable for representation
650 as a single GIMPLE_CALL statement. If the arguments require
651 further gimplification, return false. */
654 valid_gimple_call_p (tree expr
)
658 if (TREE_CODE (expr
) != CALL_EXPR
)
661 nargs
= call_expr_nargs (expr
);
662 for (i
= 0; i
< nargs
; i
++)
664 tree arg
= CALL_EXPR_ARG (expr
, i
);
665 if (is_gimple_reg_type (arg
))
667 if (!is_gimple_val (arg
))
671 if (!is_gimple_lvalue (arg
))
679 /* Make SSA names defined by OLD_STMT point to NEW_STMT
680 as their defining statement. */
683 move_ssa_defining_stmt_for_defs (gimple new_stmt
, gimple old_stmt
)
688 if (gimple_in_ssa_p (cfun
))
690 /* Make defined SSA_NAMEs point to the new
691 statement as their definition. */
692 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
694 if (TREE_CODE (var
) == SSA_NAME
)
695 SSA_NAME_DEF_STMT (var
) = new_stmt
;
700 /* Helper function for update_gimple_call and update_call_from_tree.
701 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
704 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple new_stmt
,
707 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
708 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
709 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
710 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
711 gimple_set_location (new_stmt
, gimple_location (stmt
));
712 if (gimple_block (new_stmt
) == NULL_TREE
)
713 gimple_set_block (new_stmt
, gimple_block (stmt
));
714 gsi_replace (si_p
, new_stmt
, false);
717 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
718 with number of arguments NARGS, where the arguments in GIMPLE form
719 follow NARGS argument. */
722 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
725 gimple new_stmt
, stmt
= gsi_stmt (*si_p
);
727 gcc_assert (is_gimple_call (stmt
));
728 va_start (ap
, nargs
);
729 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
730 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
735 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
736 value of EXPR, which is expected to be the result of folding the
737 call. This can only be done if EXPR is a CALL_EXPR with valid
738 GIMPLE operands as arguments, or if it is a suitable RHS expression
739 for a GIMPLE_ASSIGN. More complex expressions will require
740 gimplification, which will introduce additional statements. In this
741 event, no update is performed, and the function returns false.
742 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
743 replace the statement at *SI_P with an entirely new statement.
744 The new statement need not be a call, e.g., if the original call
745 folded to a constant. */
748 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
750 gimple stmt
= gsi_stmt (*si_p
);
752 if (valid_gimple_call_p (expr
))
754 /* The call has simplified to another call. */
755 tree fn
= CALL_EXPR_FN (expr
);
757 unsigned nargs
= call_expr_nargs (expr
);
758 vec
<tree
> args
= vNULL
;
764 args
.safe_grow_cleared (nargs
);
766 for (i
= 0; i
< nargs
; i
++)
767 args
[i
] = CALL_EXPR_ARG (expr
, i
);
770 new_stmt
= gimple_build_call_vec (fn
, args
);
771 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
776 else if (valid_gimple_rhs_p (expr
))
778 tree lhs
= gimple_call_lhs (stmt
);
781 /* The call has simplified to an expression
782 that cannot be represented as a GIMPLE_CALL. */
785 /* A value is expected.
786 Introduce a new GIMPLE_ASSIGN statement. */
787 STRIP_USELESS_TYPE_CONVERSION (expr
);
788 new_stmt
= gimple_build_assign (lhs
, expr
);
789 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
790 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
791 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
793 else if (!TREE_SIDE_EFFECTS (expr
))
795 /* No value is expected, and EXPR has no effect.
796 Replace it with an empty statement. */
797 new_stmt
= gimple_build_nop ();
798 if (gimple_in_ssa_p (cfun
))
800 unlink_stmt_vdef (stmt
);
806 /* No value is expected, but EXPR has an effect,
807 e.g., it could be a reference to a volatile
808 variable. Create an assignment statement
809 with a dummy (unused) lhs variable. */
810 STRIP_USELESS_TYPE_CONVERSION (expr
);
811 if (gimple_in_ssa_p (cfun
))
812 lhs
= make_ssa_name (TREE_TYPE (expr
), NULL
);
814 lhs
= create_tmp_var (TREE_TYPE (expr
), NULL
);
815 new_stmt
= gimple_build_assign (lhs
, expr
);
816 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
817 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
818 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
820 gimple_set_location (new_stmt
, gimple_location (stmt
));
821 gsi_replace (si_p
, new_stmt
, false);
825 /* The call simplified to an expression that is
826 not a valid GIMPLE RHS. */
831 /* Entry point to the propagation engine.
833 VISIT_STMT is called for every statement visited.
834 VISIT_PHI is called for every PHI node visited. */
837 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
838 ssa_prop_visit_phi_fn visit_phi
)
840 ssa_prop_visit_stmt
= visit_stmt
;
841 ssa_prop_visit_phi
= visit_phi
;
845 /* Iterate until the worklists are empty. */
846 while (!cfg_blocks_empty_p ()
847 || interesting_ssa_edges
->length () > 0
848 || varying_ssa_edges
->length () > 0)
850 if (!cfg_blocks_empty_p ())
852 /* Pull the next block to simulate off the worklist. */
853 basic_block dest_block
= cfg_blocks_get ();
854 simulate_block (dest_block
);
857 /* In order to move things to varying as quickly as
858 possible,process the VARYING_SSA_EDGES worklist first. */
859 process_ssa_edge_worklist (&varying_ssa_edges
);
861 /* Now process the INTERESTING_SSA_EDGES worklist. */
862 process_ssa_edge_worklist (&interesting_ssa_edges
);
869 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
870 is a non-volatile pointer dereference, a structure reference or a
871 reference to a single _DECL. Ignore volatile memory references
872 because they are not interesting for the optimizers. */
875 stmt_makes_single_store (gimple stmt
)
879 if (gimple_code (stmt
) != GIMPLE_ASSIGN
880 && gimple_code (stmt
) != GIMPLE_CALL
)
883 if (!gimple_vdef (stmt
))
886 lhs
= gimple_get_lhs (stmt
);
888 /* A call statement may have a null LHS. */
892 return (!TREE_THIS_VOLATILE (lhs
)
894 || REFERENCE_CLASS_P (lhs
)));
898 /* Propagation statistics. */
903 long num_stmts_folded
;
907 static struct prop_stats_d prop_stats
;
909 /* Replace USE references in statement STMT with the values stored in
910 PROP_VALUE. Return true if at least one reference was replaced. */
913 replace_uses_in (gimple stmt
, ssa_prop_get_value_fn get_value
)
915 bool replaced
= false;
919 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
921 tree tuse
= USE_FROM_PTR (use
);
922 tree val
= (*get_value
) (tuse
);
924 if (val
== tuse
|| val
== NULL_TREE
)
927 if (gimple_code (stmt
) == GIMPLE_ASM
928 && !may_propagate_copy_into_asm (tuse
))
931 if (!may_propagate_copy (tuse
, val
))
934 if (TREE_CODE (val
) != SSA_NAME
)
935 prop_stats
.num_const_prop
++;
937 prop_stats
.num_copy_prop
++;
939 propagate_value (use
, val
);
948 /* Replace propagated values into all the arguments for PHI using the
949 values from PROP_VALUE. */
952 replace_phi_args_in (gimple phi
, ssa_prop_get_value_fn get_value
)
955 bool replaced
= false;
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
959 fprintf (dump_file
, "Folding PHI node: ");
960 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
963 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
965 tree arg
= gimple_phi_arg_def (phi
, i
);
967 if (TREE_CODE (arg
) == SSA_NAME
)
969 tree val
= (*get_value
) (arg
);
971 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
973 if (TREE_CODE (val
) != SSA_NAME
)
974 prop_stats
.num_const_prop
++;
976 prop_stats
.num_copy_prop
++;
978 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
981 /* If we propagated a copy and this argument flows
982 through an abnormal edge, update the replacement
984 if (TREE_CODE (val
) == SSA_NAME
985 && gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_ABNORMAL
)
986 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
994 fprintf (dump_file
, "No folding possible\n");
997 fprintf (dump_file
, "Folded into: ");
998 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
999 fprintf (dump_file
, "\n");
1005 /* Perform final substitution and folding of propagated values.
1007 PROP_VALUE[I] contains the single value that should be substituted
1008 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1011 If FOLD_FN is non-NULL the function will be invoked on all statements
1012 before propagating values for pass specific simplification.
1014 DO_DCE is true if trivially dead stmts can be removed.
1016 If DO_DCE is true, the statements within a BB are walked from
1017 last to first element. Otherwise we scan from first to last element.
1019 Return TRUE when something changed. */
1022 substitute_and_fold (ssa_prop_get_value_fn get_value_fn
,
1023 ssa_prop_fold_stmt_fn fold_fn
,
1027 bool something_changed
= false;
1030 if (!get_value_fn
&& !fold_fn
)
1033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1034 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1036 memset (&prop_stats
, 0, sizeof (prop_stats
));
1038 /* Substitute lattice values at definition sites. */
1040 for (i
= 1; i
< num_ssa_names
; ++i
)
1042 tree name
= ssa_name (i
);
1045 gimple_stmt_iterator gsi
;
1048 || virtual_operand_p (name
))
1051 def_stmt
= SSA_NAME_DEF_STMT (name
);
1052 if (gimple_nop_p (def_stmt
)
1053 /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */
1054 || (gimple_assign_single_p (def_stmt
)
1055 && gimple_assign_rhs_code (def_stmt
) == ASSERT_EXPR
)
1056 || !(val
= (*get_value_fn
) (name
))
1057 || !may_propagate_copy (name
, val
))
1060 gsi
= gsi_for_stmt (def_stmt
);
1061 if (is_gimple_assign (def_stmt
))
1063 gimple_assign_set_rhs_with_ops (&gsi
, TREE_CODE (val
),
1065 gcc_assert (gsi_stmt (gsi
) == def_stmt
);
1066 if (maybe_clean_eh_stmt (def_stmt
))
1067 gimple_purge_dead_eh_edges (gimple_bb (def_stmt
));
1068 update_stmt (def_stmt
);
1070 else if (is_gimple_call (def_stmt
))
1072 int flags
= gimple_call_flags (def_stmt
);
1074 /* Don't optimize away calls that have side-effects. */
1075 if ((flags
& (ECF_CONST
|ECF_PURE
)) == 0
1076 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
1078 if (update_call_from_tree (&gsi
, val
)
1079 && maybe_clean_or_replace_eh_stmt (def_stmt
, gsi_stmt (gsi
)))
1080 gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi
)));
1082 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
1084 gimple new_stmt
= gimple_build_assign (name
, val
);
1085 gimple_stmt_iterator gsi2
;
1086 gsi2
= gsi_after_labels (gimple_bb (def_stmt
));
1087 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
1088 remove_phi_node (&gsi
, false);
1091 something_changed
= true;
1094 /* Propagate into all uses and fold. */
1097 gimple_stmt_iterator i
;
1099 /* Propagate known values into PHI nodes. */
1101 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
1102 replace_phi_args_in (gsi_stmt (i
), get_value_fn
);
1104 /* Propagate known values into stmts. Do a backward walk if
1105 do_dce is true. In some case it exposes
1106 more trivially deletable stmts to walk backward. */
1107 for (i
= (do_dce
? gsi_last_bb (bb
) : gsi_start_bb (bb
)); !gsi_end_p (i
);)
1110 gimple stmt
= gsi_stmt (i
);
1112 enum gimple_code code
= gimple_code (stmt
);
1113 gimple_stmt_iterator oldi
;
1121 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1122 range information for names and they are discarded
1125 if (code
== GIMPLE_ASSIGN
1126 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
1129 /* No point propagating into a stmt whose result is not used,
1130 but instead we might be able to remove a trivially dead stmt.
1131 Don't do this when called from VRP, since the SSA_NAME which
1132 is going to be released could be still referenced in VRP
1135 && gimple_get_lhs (stmt
)
1136 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1137 && has_zero_uses (gimple_get_lhs (stmt
))
1138 && !stmt_could_throw_p (stmt
)
1139 && !gimple_has_side_effects (stmt
))
1141 gimple_stmt_iterator i2
;
1143 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1145 fprintf (dump_file
, "Removing dead stmt ");
1146 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1147 fprintf (dump_file
, "\n");
1149 prop_stats
.num_dce
++;
1150 i2
= gsi_for_stmt (stmt
);
1151 gsi_remove (&i2
, true);
1152 release_defs (stmt
);
1156 /* Replace the statement with its folded version and mark it
1158 did_replace
= false;
1159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1161 fprintf (dump_file
, "Folding statement: ");
1162 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1167 /* Some statements may be simplified using propagator
1168 specific information. Do this before propagating
1169 into the stmt to not disturb pass specific information. */
1171 && (*fold_fn
)(&oldi
))
1174 prop_stats
.num_stmts_folded
++;
1175 stmt
= gsi_stmt (oldi
);
1179 /* Replace real uses in the statement. */
1181 did_replace
|= replace_uses_in (stmt
, get_value_fn
);
1183 /* If we made a replacement, fold the statement. */
1190 stmt
= gsi_stmt (oldi
);
1192 /* If we cleaned up EH information from the statement,
1194 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1195 gimple_purge_dead_eh_edges (bb
);
1197 if (is_gimple_assign (stmt
)
1198 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1199 == GIMPLE_SINGLE_RHS
))
1201 tree rhs
= gimple_assign_rhs1 (stmt
);
1203 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1204 recompute_tree_invariant_for_addr_expr (rhs
);
1207 /* Determine what needs to be done to update the SSA form. */
1209 if (!is_gimple_debug (stmt
))
1210 something_changed
= true;
1213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1217 fprintf (dump_file
, "Folded into: ");
1218 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1219 fprintf (dump_file
, "\n");
1222 fprintf (dump_file
, "Not folded\n");
1227 statistics_counter_event (cfun
, "Constants propagated",
1228 prop_stats
.num_const_prop
);
1229 statistics_counter_event (cfun
, "Copies propagated",
1230 prop_stats
.num_copy_prop
);
1231 statistics_counter_event (cfun
, "Statements folded",
1232 prop_stats
.num_stmts_folded
);
1233 statistics_counter_event (cfun
, "Statements deleted",
1234 prop_stats
.num_dce
);
1235 return something_changed
;
1239 /* Return true if we may propagate ORIG into DEST, false otherwise. */
1242 may_propagate_copy (tree dest
, tree orig
)
1244 tree type_d
= TREE_TYPE (dest
);
1245 tree type_o
= TREE_TYPE (orig
);
1247 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */
1248 if (TREE_CODE (orig
) == SSA_NAME
1249 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
)
1250 /* If it is the default definition and an automatic variable then
1251 we can though and it is important that we do to avoid
1252 uninitialized regular copies. */
1253 && !(SSA_NAME_IS_DEFAULT_DEF (orig
)
1254 && (SSA_NAME_VAR (orig
) == NULL_TREE
1255 || TREE_CODE (SSA_NAME_VAR (orig
)) == VAR_DECL
)))
1258 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
1259 cannot be replaced. */
1260 if (TREE_CODE (dest
) == SSA_NAME
1261 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest
))
1264 /* Do not copy between types for which we *do* need a conversion. */
1265 if (!useless_type_conversion_p (type_d
, type_o
))
1268 /* Generally propagating virtual operands is not ok as that may
1269 create overlapping life-ranges. */
1270 if (TREE_CODE (dest
) == SSA_NAME
&& virtual_operand_p (dest
))
1273 /* Anything else is OK. */
1277 /* Like may_propagate_copy, but use as the destination expression
1278 the principal expression (typically, the RHS) contained in
1279 statement DEST. This is more efficient when working with the
1280 gimple tuples representation. */
1283 may_propagate_copy_into_stmt (gimple dest
, tree orig
)
1288 /* If the statement is a switch or a single-rhs assignment,
1289 then the expression to be replaced by the propagation may
1290 be an SSA_NAME. Fortunately, there is an explicit tree
1291 for the expression, so we delegate to may_propagate_copy. */
1293 if (gimple_assign_single_p (dest
))
1294 return may_propagate_copy (gimple_assign_rhs1 (dest
), orig
);
1295 else if (gimple_code (dest
) == GIMPLE_SWITCH
)
1296 return may_propagate_copy (gimple_switch_index (dest
), orig
);
1298 /* In other cases, the expression is not materialized, so there
1299 is no destination to pass to may_propagate_copy. On the other
1300 hand, the expression cannot be an SSA_NAME, so the analysis
1303 if (TREE_CODE (orig
) == SSA_NAME
1304 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig
))
1307 if (is_gimple_assign (dest
))
1308 type_d
= TREE_TYPE (gimple_assign_lhs (dest
));
1309 else if (gimple_code (dest
) == GIMPLE_COND
)
1310 type_d
= boolean_type_node
;
1311 else if (is_gimple_call (dest
)
1312 && gimple_call_lhs (dest
) != NULL_TREE
)
1313 type_d
= TREE_TYPE (gimple_call_lhs (dest
));
1317 type_o
= TREE_TYPE (orig
);
1319 if (!useless_type_conversion_p (type_d
, type_o
))
1325 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
1328 may_propagate_copy_into_asm (tree dest ATTRIBUTE_UNUSED
)
1334 /* Common code for propagate_value and replace_exp.
1336 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
1337 replacement is done to propagate a value or not. */
1340 replace_exp_1 (use_operand_p op_p
, tree val
,
1341 bool for_propagation ATTRIBUTE_UNUSED
)
1343 #if defined ENABLE_CHECKING
1344 tree op
= USE_FROM_PTR (op_p
);
1346 gcc_assert (!(for_propagation
1347 && TREE_CODE (op
) == SSA_NAME
1348 && TREE_CODE (val
) == SSA_NAME
1349 && !may_propagate_copy (op
, val
)));
1352 if (TREE_CODE (val
) == SSA_NAME
)
1353 SET_USE (op_p
, val
);
1355 SET_USE (op_p
, unshare_expr (val
));
1359 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1360 into the operand pointed to by OP_P.
1362 Use this version for const/copy propagation as it will perform additional
1363 checks to ensure validity of the const/copy propagation. */
1366 propagate_value (use_operand_p op_p
, tree val
)
1368 replace_exp_1 (op_p
, val
, true);
1371 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
1373 Use this version when not const/copy propagating values. For example,
1374 PRE uses this version when building expressions as they would appear
1375 in specific blocks taking into account actions of PHI nodes.
1377 The statement in which an expression has been replaced should be
1378 folded using fold_stmt_inplace. */
1381 replace_exp (use_operand_p op_p
, tree val
)
1383 replace_exp_1 (op_p
, val
, false);
1387 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1388 into the tree pointed to by OP_P.
1390 Use this version for const/copy propagation when SSA operands are not
1391 available. It will perform the additional checks to ensure validity of
1392 the const/copy propagation, but will not update any operand information.
1393 Be sure to mark the stmt as modified. */
1396 propagate_tree_value (tree
*op_p
, tree val
)
1398 gcc_checking_assert (!(TREE_CODE (val
) == SSA_NAME
1400 && TREE_CODE (*op_p
) == SSA_NAME
1401 && !may_propagate_copy (*op_p
, val
)));
1403 if (TREE_CODE (val
) == SSA_NAME
)
1406 *op_p
= unshare_expr (val
);
1410 /* Like propagate_tree_value, but use as the operand to replace
1411 the principal expression (typically, the RHS) contained in the
1412 statement referenced by iterator GSI. Note that it is not
1413 always possible to update the statement in-place, so a new
1414 statement may be created to replace the original. */
1417 propagate_tree_value_into_stmt (gimple_stmt_iterator
*gsi
, tree val
)
1419 gimple stmt
= gsi_stmt (*gsi
);
1421 if (is_gimple_assign (stmt
))
1423 tree expr
= NULL_TREE
;
1424 if (gimple_assign_single_p (stmt
))
1425 expr
= gimple_assign_rhs1 (stmt
);
1426 propagate_tree_value (&expr
, val
);
1427 gimple_assign_set_rhs_from_tree (gsi
, expr
);
1429 else if (gimple_code (stmt
) == GIMPLE_COND
)
1431 tree lhs
= NULL_TREE
;
1432 tree rhs
= build_zero_cst (TREE_TYPE (val
));
1433 propagate_tree_value (&lhs
, val
);
1434 gimple_cond_set_code (stmt
, NE_EXPR
);
1435 gimple_cond_set_lhs (stmt
, lhs
);
1436 gimple_cond_set_rhs (stmt
, rhs
);
1438 else if (is_gimple_call (stmt
)
1439 && gimple_call_lhs (stmt
) != NULL_TREE
)
1441 tree expr
= NULL_TREE
;
1443 propagate_tree_value (&expr
, val
);
1444 res
= update_call_from_tree (gsi
, expr
);
1447 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
1448 propagate_tree_value (gimple_switch_index_ptr (stmt
), val
);
1453 #include "gt-tree-ssa-propagate.h"