1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005, 2006, 2007 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"
30 #include "basic-block.h"
34 #include "diagnostic.h"
36 #include "tree-dump.h"
37 #include "tree-flow.h"
38 #include "tree-pass.h"
39 #include "tree-ssa-propagate.h"
40 #include "langhooks.h"
43 #include "value-prof.h"
45 /* This file implements a generic value propagation engine based on
46 the same propagation used by the SSA-CCP algorithm [1].
48 Propagation is performed by simulating the execution of every
49 statement that produces the value being propagated. Simulation
52 1- Initially, all edges of the CFG are marked not executable and
53 the CFG worklist is seeded with all the statements in the entry
54 basic block (block 0).
56 2- Every statement S is simulated with a call to the call-back
57 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
60 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
61 interest and does not affect any of the work lists.
63 SSA_PROP_VARYING: The value produced by S cannot be determined
64 at compile time. Further simulation of S is not required.
65 If S is a conditional jump, all the outgoing edges for the
66 block are considered executable and added to the work
69 SSA_PROP_INTERESTING: S produces a value that can be computed
70 at compile time. Its result can be propagated into the
71 statements that feed from S. Furthermore, if S is a
72 conditional jump, only the edge known to be taken is added
73 to the work list. Edges that are known not to execute are
76 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
77 return value from SSA_PROP_VISIT_PHI has the same semantics as
80 4- Three work lists are kept. Statements are only added to these
81 lists if they produce one of SSA_PROP_INTERESTING or
84 CFG_BLOCKS contains the list of blocks to be simulated.
85 Blocks are added to this list if their incoming edges are
88 VARYING_SSA_EDGES contains the list of statements that feed
89 from statements that produce an SSA_PROP_VARYING result.
90 These are simulated first to speed up processing.
92 INTERESTING_SSA_EDGES contains the list of statements that
93 feed from statements that produce an SSA_PROP_INTERESTING
96 5- Simulation terminates when all three work lists are drained.
98 Before calling ssa_propagate, it is important to clear
99 DONT_SIMULATE_AGAIN for all the statements in the program that
100 should be simulated. This initialization allows an implementation
101 to specify which statements should never be simulated.
103 It is also important to compute def-use information before calling
108 [1] Constant propagation with conditional branches,
109 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
111 [2] Building an Optimizing Compiler,
112 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
114 [3] Advanced Compiler Design and Implementation,
115 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
117 /* Function pointers used to parameterize the propagation engine. */
118 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
119 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
121 /* Use the deprecated flag to mark statements that have been
122 added to one of the SSA edges worklists. This flag is used to
123 avoid visiting statements unnecessarily when draining an SSA edge
124 worklist. If while simulating a basic block, we find a statement with
125 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
126 processing from visiting it again. */
127 #define STMT_IN_SSA_EDGE_WORKLIST(T) ((T)->base.deprecated_flag)
129 /* A bitmap to keep track of executable blocks in the CFG. */
130 static sbitmap executable_blocks
;
132 /* Array of control flow edges on the worklist. */
133 static VEC(basic_block
,heap
) *cfg_blocks
;
135 static unsigned int cfg_blocks_num
= 0;
136 static int cfg_blocks_tail
;
137 static int cfg_blocks_head
;
139 static sbitmap bb_in_list
;
141 /* Worklist of SSA edges which will need reexamination as their
142 definition has changed. SSA edges are def-use edges in the SSA
143 web. For each D-U edge, we store the target statement or PHI node
145 static GTY(()) VEC(tree
,gc
) *interesting_ssa_edges
;
147 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
148 list of SSA edges is split into two. One contains all SSA edges
149 who need to be reexamined because their lattice value changed to
150 varying (this worklist), and the other contains all other SSA edges
151 to be reexamined (INTERESTING_SSA_EDGES).
153 Since most values in the program are VARYING, the ideal situation
154 is to move them to that lattice value as quickly as possible.
155 Thus, it doesn't make sense to process any other type of lattice
156 value until all VARYING values are propagated fully, which is one
157 thing using the VARYING worklist achieves. In addition, if we
158 don't use a separate worklist for VARYING edges, we end up with
159 situations where lattice values move from
160 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
161 static GTY(()) VEC(tree
,gc
) *varying_ssa_edges
;
164 /* Return true if the block worklist empty. */
167 cfg_blocks_empty_p (void)
169 return (cfg_blocks_num
== 0);
173 /* Add a basic block to the worklist. The block must not be already
174 in the worklist, and it must not be the ENTRY or EXIT block. */
177 cfg_blocks_add (basic_block bb
)
181 gcc_assert (bb
!= ENTRY_BLOCK_PTR
&& bb
!= EXIT_BLOCK_PTR
);
182 gcc_assert (!TEST_BIT (bb_in_list
, bb
->index
));
184 if (cfg_blocks_empty_p ())
186 cfg_blocks_tail
= cfg_blocks_head
= 0;
192 if (cfg_blocks_num
> VEC_length (basic_block
, cfg_blocks
))
194 /* We have to grow the array now. Adjust to queue to occupy
195 the full space of the original array. We do not need to
196 initialize the newly allocated portion of the array
197 because we keep track of CFG_BLOCKS_HEAD and
199 cfg_blocks_tail
= VEC_length (basic_block
, cfg_blocks
);
201 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 2 * cfg_blocks_tail
);
203 /* Minor optimization: we prefer to see blocks with more
204 predecessors later, because there is more of a chance that
205 the incoming edges will be executable. */
206 else if (EDGE_COUNT (bb
->preds
)
207 >= EDGE_COUNT (VEC_index (basic_block
, cfg_blocks
,
208 cfg_blocks_head
)->preds
))
209 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1)
210 % VEC_length (basic_block
, cfg_blocks
));
213 if (cfg_blocks_head
== 0)
214 cfg_blocks_head
= VEC_length (basic_block
, cfg_blocks
);
220 VEC_replace (basic_block
, cfg_blocks
,
221 head
? cfg_blocks_head
: cfg_blocks_tail
,
223 SET_BIT (bb_in_list
, bb
->index
);
227 /* Remove a block from the worklist. */
230 cfg_blocks_get (void)
234 bb
= VEC_index (basic_block
, cfg_blocks
, cfg_blocks_head
);
236 gcc_assert (!cfg_blocks_empty_p ());
239 cfg_blocks_head
= ((cfg_blocks_head
+ 1)
240 % VEC_length (basic_block
, cfg_blocks
));
242 RESET_BIT (bb_in_list
, bb
->index
);
248 /* We have just defined a new value for VAR. If IS_VARYING is true,
249 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
250 them to INTERESTING_SSA_EDGES. */
253 add_ssa_edge (tree var
, bool is_varying
)
255 imm_use_iterator iter
;
258 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
260 tree use_stmt
= USE_STMT (use_p
);
262 if (!DONT_SIMULATE_AGAIN (use_stmt
)
263 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt
))
265 STMT_IN_SSA_EDGE_WORKLIST (use_stmt
) = 1;
267 VEC_safe_push (tree
, gc
, varying_ssa_edges
, use_stmt
);
269 VEC_safe_push (tree
, gc
, interesting_ssa_edges
, use_stmt
);
275 /* Add edge E to the control flow worklist. */
278 add_control_edge (edge e
)
280 basic_block bb
= e
->dest
;
281 if (bb
== EXIT_BLOCK_PTR
)
284 /* If the edge had already been executed, skip it. */
285 if (e
->flags
& EDGE_EXECUTABLE
)
288 e
->flags
|= EDGE_EXECUTABLE
;
290 /* If the block is already in the list, we're done. */
291 if (TEST_BIT (bb_in_list
, bb
->index
))
296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
297 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
298 e
->src
->index
, e
->dest
->index
);
302 /* Simulate the execution of STMT and update the work lists accordingly. */
305 simulate_stmt (tree stmt
)
307 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
308 edge taken_edge
= NULL
;
309 tree output_name
= NULL_TREE
;
311 /* Don't bother visiting statements that are already
312 considered varying by the propagator. */
313 if (DONT_SIMULATE_AGAIN (stmt
))
316 if (TREE_CODE (stmt
) == PHI_NODE
)
318 val
= ssa_prop_visit_phi (stmt
);
319 output_name
= PHI_RESULT (stmt
);
322 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
324 if (val
== SSA_PROP_VARYING
)
326 DONT_SIMULATE_AGAIN (stmt
) = 1;
328 /* If the statement produced a new varying value, add the SSA
329 edges coming out of OUTPUT_NAME. */
331 add_ssa_edge (output_name
, true);
333 /* If STMT transfers control out of its basic block, add
334 all outgoing edges to the work list. */
335 if (stmt_ends_bb_p (stmt
))
339 basic_block bb
= bb_for_stmt (stmt
);
340 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
341 add_control_edge (e
);
344 else if (val
== SSA_PROP_INTERESTING
)
346 /* If the statement produced new value, add the SSA edges coming
347 out of OUTPUT_NAME. */
349 add_ssa_edge (output_name
, false);
351 /* If we know which edge is going to be taken out of this block,
352 add it to the CFG work list. */
354 add_control_edge (taken_edge
);
358 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
359 drain. This pops statements off the given WORKLIST and processes
360 them until there are no more statements on WORKLIST.
361 We take a pointer to WORKLIST because it may be reallocated when an
362 SSA edge is added to it in simulate_stmt. */
365 process_ssa_edge_worklist (VEC(tree
,gc
) **worklist
)
367 /* Drain the entire worklist. */
368 while (VEC_length (tree
, *worklist
) > 0)
372 /* Pull the statement to simulate off the worklist. */
373 tree stmt
= VEC_pop (tree
, *worklist
);
375 /* If this statement was already visited by simulate_block, then
376 we don't need to visit it again here. */
377 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt
))
380 /* STMT is no longer in a worklist. */
381 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
385 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
386 print_generic_stmt (dump_file
, stmt
, dump_flags
);
389 bb
= bb_for_stmt (stmt
);
391 /* PHI nodes are always visited, regardless of whether or not
392 the destination block is executable. Otherwise, visit the
393 statement only if its block is marked executable. */
394 if (TREE_CODE (stmt
) == PHI_NODE
395 || TEST_BIT (executable_blocks
, bb
->index
))
396 simulate_stmt (stmt
);
401 /* Simulate the execution of BLOCK. Evaluate the statement associated
402 with each variable reference inside the block. */
405 simulate_block (basic_block block
)
409 /* There is nothing to do for the exit block. */
410 if (block
== EXIT_BLOCK_PTR
)
413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
414 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
416 /* Always simulate PHI nodes, even if we have simulated this block
418 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
421 /* If this is the first time we've simulated this block, then we
422 must simulate each of its statements. */
423 if (!TEST_BIT (executable_blocks
, block
->index
))
425 block_stmt_iterator j
;
426 unsigned int normal_edge_count
;
430 /* Note that we have simulated this block. */
431 SET_BIT (executable_blocks
, block
->index
);
433 for (j
= bsi_start (block
); !bsi_end_p (j
); bsi_next (&j
))
435 tree stmt
= bsi_stmt (j
);
437 /* If this statement is already in the worklist then
438 "cancel" it. The reevaluation implied by the worklist
439 entry will produce the same value we generate here and
440 thus reevaluating it again from the worklist is
442 if (STMT_IN_SSA_EDGE_WORKLIST (stmt
))
443 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
445 simulate_stmt (stmt
);
448 /* We can not predict when abnormal edges will be executed, so
449 once a block is considered executable, we consider any
450 outgoing abnormal edges as executable.
452 At the same time, if this block has only one successor that is
453 reached by non-abnormal edges, then add that successor to the
455 normal_edge_count
= 0;
457 FOR_EACH_EDGE (e
, ei
, block
->succs
)
459 if (e
->flags
& EDGE_ABNORMAL
)
460 add_control_edge (e
);
468 if (normal_edge_count
== 1)
469 add_control_edge (normal_edge
);
474 /* Initialize local data structures and work lists. */
484 /* Worklists of SSA edges. */
485 interesting_ssa_edges
= VEC_alloc (tree
, gc
, 20);
486 varying_ssa_edges
= VEC_alloc (tree
, gc
, 20);
488 executable_blocks
= sbitmap_alloc (last_basic_block
);
489 sbitmap_zero (executable_blocks
);
491 bb_in_list
= sbitmap_alloc (last_basic_block
);
492 sbitmap_zero (bb_in_list
);
494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
495 dump_immediate_uses (dump_file
);
497 cfg_blocks
= VEC_alloc (basic_block
, heap
, 20);
498 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 20);
500 /* Initialize the values for every SSA_NAME. */
501 for (i
= 1; i
< num_ssa_names
; i
++)
503 SSA_NAME_VALUE (ssa_name (i
)) = NULL_TREE
;
505 /* Initially assume that every edge in the CFG is not executable.
506 (including the edges coming out of ENTRY_BLOCK_PTR). */
509 block_stmt_iterator si
;
511 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
512 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si
)) = 0;
514 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
515 e
->flags
&= ~EDGE_EXECUTABLE
;
518 /* Seed the algorithm by adding the successors of the entry block to the
520 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
521 add_control_edge (e
);
525 /* Free allocated storage. */
530 VEC_free (tree
, gc
, interesting_ssa_edges
);
531 VEC_free (tree
, gc
, varying_ssa_edges
);
532 VEC_free (basic_block
, heap
, cfg_blocks
);
534 sbitmap_free (bb_in_list
);
535 sbitmap_free (executable_blocks
);
539 /* Get the main expression from statement STMT. */
544 enum tree_code code
= TREE_CODE (stmt
);
549 stmt
= TREE_OPERAND (stmt
, 0);
550 if (!stmt
|| TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
554 case GIMPLE_MODIFY_STMT
:
555 stmt
= GENERIC_TREE_OPERAND (stmt
, 1);
556 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
557 return TREE_OPERAND (stmt
, 0);
562 return COND_EXPR_COND (stmt
);
564 return SWITCH_COND (stmt
);
566 return GOTO_DESTINATION (stmt
);
568 return LABEL_EXPR_LABEL (stmt
);
576 /* Return true if EXPR is a valid GIMPLE expression. */
579 valid_gimple_expression_p (tree expr
)
581 enum tree_code code
= TREE_CODE (expr
);
583 switch (TREE_CODE_CLASS (code
))
585 case tcc_declaration
:
586 if (!is_gimple_variable (expr
))
595 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
596 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
601 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
610 tree t
= TREE_OPERAND (expr
, 0);
611 while (handled_component_p (t
))
613 /* ??? More checks needed, see the GIMPLE verifier. */
614 if ((TREE_CODE (t
) == ARRAY_REF
615 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
616 && !is_gimple_val (TREE_OPERAND (t
, 1)))
618 t
= TREE_OPERAND (t
, 0);
620 if (!is_gimple_id (t
))
626 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
633 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
634 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
657 case tcc_exceptional
:
676 /* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
677 GIMPLE expression no changes are done and the function returns
681 set_rhs (tree
*stmt_p
, tree expr
)
683 tree stmt
= *stmt_p
, op
;
689 if (!valid_gimple_expression_p (expr
))
692 if (EXPR_HAS_LOCATION (stmt
)
694 || GIMPLE_STMT_P (expr
))
695 && ! EXPR_HAS_LOCATION (expr
)
696 && TREE_SIDE_EFFECTS (expr
)
697 && TREE_CODE (expr
) != LABEL_EXPR
)
698 SET_EXPR_LOCATION (expr
, EXPR_LOCATION (stmt
));
700 switch (TREE_CODE (stmt
))
703 op
= TREE_OPERAND (stmt
, 0);
704 if (TREE_CODE (op
) != GIMPLE_MODIFY_STMT
)
706 GIMPLE_STMT_OPERAND (stmt
, 0) = expr
;
712 case GIMPLE_MODIFY_STMT
:
713 op
= GIMPLE_STMT_OPERAND (stmt
, 1);
714 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
715 TREE_OPERAND (op
, 0) = expr
;
717 GIMPLE_STMT_OPERAND (stmt
, 1) = expr
;
721 if (!is_gimple_condexpr (expr
))
723 COND_EXPR_COND (stmt
) = expr
;
726 SWITCH_COND (stmt
) = expr
;
729 GOTO_DESTINATION (stmt
) = expr
;
732 LABEL_EXPR_LABEL (stmt
) = expr
;
736 /* Replace the whole statement with EXPR. If EXPR has no side
737 effects, then replace *STMT_P with an empty statement. */
738 new_stmt
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
741 /* Preserve the annotation, the histograms and the EH region information
742 associated with the original statement. The EH information
743 needs to be preserved only if the new statement still can throw. */
744 new_stmt
->base
.ann
= (tree_ann_t
) stmt_ann (stmt
);
745 gimple_move_stmt_histograms (cfun
, new_stmt
, stmt
);
746 if (tree_could_throw_p (new_stmt
))
748 eh_region
= lookup_stmt_eh_region (stmt
);
749 /* We couldn't possibly turn a nothrow into a throw statement. */
750 gcc_assert (eh_region
>= 0);
751 remove_stmt_from_eh_region (stmt
);
752 add_stmt_to_eh_region (new_stmt
, eh_region
);
755 if (gimple_in_ssa_p (cfun
)
756 && TREE_SIDE_EFFECTS (expr
))
758 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
760 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_DEFS
)
762 if (TREE_CODE (var
) == SSA_NAME
)
763 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
766 stmt
->base
.ann
= NULL
;
774 /* Entry point to the propagation engine.
776 VISIT_STMT is called for every statement visited.
777 VISIT_PHI is called for every PHI node visited. */
780 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
781 ssa_prop_visit_phi_fn visit_phi
)
783 ssa_prop_visit_stmt
= visit_stmt
;
784 ssa_prop_visit_phi
= visit_phi
;
788 /* Iterate until the worklists are empty. */
789 while (!cfg_blocks_empty_p ()
790 || VEC_length (tree
, interesting_ssa_edges
) > 0
791 || VEC_length (tree
, varying_ssa_edges
) > 0)
793 if (!cfg_blocks_empty_p ())
795 /* Pull the next block to simulate off the worklist. */
796 basic_block dest_block
= cfg_blocks_get ();
797 simulate_block (dest_block
);
800 /* In order to move things to varying as quickly as
801 possible,process the VARYING_SSA_EDGES worklist first. */
802 process_ssa_edge_worklist (&varying_ssa_edges
);
804 /* Now process the INTERESTING_SSA_EDGES worklist. */
805 process_ssa_edge_worklist (&interesting_ssa_edges
);
812 /* Return the first VDEF operand for STMT. */
815 first_vdef (tree stmt
)
820 /* Simply return the first operand we arrive at. */
821 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
828 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
829 is a non-volatile pointer dereference, a structure reference or a
830 reference to a single _DECL. Ignore volatile memory references
831 because they are not interesting for the optimizers. */
834 stmt_makes_single_load (tree stmt
)
838 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
841 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
|SSA_OP_VUSE
))
844 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
847 return (!TREE_THIS_VOLATILE (rhs
)
849 || REFERENCE_CLASS_P (rhs
)));
853 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
854 is a non-volatile pointer dereference, a structure reference or a
855 reference to a single _DECL. Ignore volatile memory references
856 because they are not interesting for the optimizers. */
859 stmt_makes_single_store (tree stmt
)
863 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
866 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
))
869 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
872 return (!TREE_THIS_VOLATILE (lhs
)
874 || REFERENCE_CLASS_P (lhs
)));
878 /* If STMT makes a single memory load and all the virtual use operands
879 have the same value in array VALUES, return it. Otherwise, return
883 get_value_loaded_by (tree stmt
, prop_value_t
*values
)
887 prop_value_t
*prev_val
= NULL
;
888 prop_value_t
*val
= NULL
;
890 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
, SSA_OP_VIRTUAL_USES
)
892 val
= &values
[SSA_NAME_VERSION (vuse
)];
893 if (prev_val
&& prev_val
->value
!= val
->value
)
902 /* Propagation statistics. */
907 long num_pred_folded
;
911 static struct prop_stats_d prop_stats
;
913 /* Replace USE references in statement STMT with the values stored in
914 PROP_VALUE. Return true if at least one reference was replaced. If
915 REPLACED_ADDRESSES_P is given, it will be set to true if an address
916 constant was replaced. */
919 replace_uses_in (tree stmt
, bool *replaced_addresses_p
,
920 prop_value_t
*prop_value
)
922 bool replaced
= false;
926 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
928 tree tuse
= USE_FROM_PTR (use
);
929 tree val
= prop_value
[SSA_NAME_VERSION (tuse
)].value
;
931 if (val
== tuse
|| val
== NULL_TREE
)
934 if (TREE_CODE (stmt
) == ASM_EXPR
935 && !may_propagate_copy_into_asm (tuse
))
938 if (!may_propagate_copy (tuse
, val
))
941 if (TREE_CODE (val
) != SSA_NAME
)
942 prop_stats
.num_const_prop
++;
944 prop_stats
.num_copy_prop
++;
946 propagate_value (use
, val
);
949 if (POINTER_TYPE_P (TREE_TYPE (tuse
)) && replaced_addresses_p
)
950 *replaced_addresses_p
= true;
957 /* Replace the VUSE references in statement STMT with the values
958 stored in PROP_VALUE. Return true if a reference was replaced. If
959 REPLACED_ADDRESSES_P is given, it will be set to true if an address
960 constant was replaced.
962 Replacing VUSE operands is slightly more complex than replacing
963 regular USEs. We are only interested in two types of replacements
966 1- If the value to be replaced is a constant or an SSA name for a
967 GIMPLE register, then we are making a copy/constant propagation
968 from a memory store. For instance,
976 This replacement is only possible iff STMT is an assignment
977 whose RHS is identical to the LHS of the statement that created
978 the VUSE(s) that we are replacing. Otherwise, we may do the
988 Even though 'b_5' acquires the value '10' during propagation,
989 there is no way for the propagator to tell whether the
990 replacement is correct in every reached use, because values are
991 computed at definition sites. Therefore, when doing final
992 substitution of propagated values, we have to check each use
993 site. Since the RHS of STMT ('b') is different from the LHS of
994 the originating statement ('*p'), we cannot replace 'b' with
997 Similarly, when merging values from PHI node arguments,
998 propagators need to take care not to merge the same values
999 stored in different locations:
1007 # a_5 = PHI <a_3, a_4>
1009 It would be wrong to propagate '3' into 'a_5' because that
1010 operation merges two stores to different memory locations.
1013 2- If the value to be replaced is an SSA name for a virtual
1014 register, then we simply replace each VUSE operand with its
1015 value from PROP_VALUE. This is the same replacement done by
1019 replace_vuses_in (tree stmt
, bool *replaced_addresses_p
,
1020 prop_value_t
*prop_value
)
1022 bool replaced
= false;
1026 if (stmt_makes_single_load (stmt
))
1028 /* If STMT is an assignment whose RHS is a single memory load,
1029 see if we are trying to propagate a constant or a GIMPLE
1030 register (case #1 above). */
1031 prop_value_t
*val
= get_value_loaded_by (stmt
, prop_value
);
1032 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1036 && (is_gimple_reg (val
->value
)
1037 || is_gimple_min_invariant (val
->value
))
1038 && simple_cst_equal (rhs
, val
->mem_ref
) == 1)
1041 /* If we are replacing a constant address, inform our
1043 if (TREE_CODE (val
->value
) != SSA_NAME
1044 && POINTER_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 1)))
1045 && replaced_addresses_p
)
1046 *replaced_addresses_p
= true;
1048 /* We can only perform the substitution if the load is done
1049 from the same memory location as the original store.
1050 Since we already know that there are no intervening
1051 stores between DEF_STMT and STMT, we only need to check
1052 that the RHS of STMT is the same as the memory reference
1053 propagated together with the value. */
1054 GIMPLE_STMT_OPERAND (stmt
, 1) = val
->value
;
1056 if (TREE_CODE (val
->value
) != SSA_NAME
)
1057 prop_stats
.num_const_prop
++;
1059 prop_stats
.num_copy_prop
++;
1061 /* Since we have replaced the whole RHS of STMT, there
1062 is no point in checking the other VUSEs, as they will
1063 all have the same value. */
1068 /* Otherwise, the values for every VUSE operand must be other
1069 SSA_NAMEs that can be propagated into STMT. */
1070 FOR_EACH_SSA_USE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1072 tree var
= USE_FROM_PTR (vuse
);
1073 tree val
= prop_value
[SSA_NAME_VERSION (var
)].value
;
1075 if (val
== NULL_TREE
|| var
== val
)
1078 /* Constants and copies propagated between real and virtual
1079 operands are only possible in the cases handled above. They
1080 should be ignored in any other context. */
1081 if (is_gimple_min_invariant (val
) || is_gimple_reg (val
))
1084 propagate_value (vuse
, val
);
1085 prop_stats
.num_copy_prop
++;
1093 /* Replace propagated values into all the arguments for PHI using the
1094 values from PROP_VALUE. */
1097 replace_phi_args_in (tree phi
, prop_value_t
*prop_value
)
1100 bool replaced
= false;
1101 tree prev_phi
= NULL
;
1103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1104 prev_phi
= unshare_expr (phi
);
1106 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1108 tree arg
= PHI_ARG_DEF (phi
, i
);
1110 if (TREE_CODE (arg
) == SSA_NAME
)
1112 tree val
= prop_value
[SSA_NAME_VERSION (arg
)].value
;
1114 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
1116 if (TREE_CODE (val
) != SSA_NAME
)
1117 prop_stats
.num_const_prop
++;
1119 prop_stats
.num_copy_prop
++;
1121 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
1124 /* If we propagated a copy and this argument flows
1125 through an abnormal edge, update the replacement
1127 if (TREE_CODE (val
) == SSA_NAME
1128 && PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_ABNORMAL
)
1129 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
1134 if (replaced
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1136 fprintf (dump_file
, "Folded PHI node: ");
1137 print_generic_stmt (dump_file
, prev_phi
, TDF_SLIM
);
1138 fprintf (dump_file
, " into: ");
1139 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1140 fprintf (dump_file
, "\n");
1145 /* If STMT has a predicate whose value can be computed using the value
1146 range information computed by VRP, compute its value and return true.
1147 Otherwise, return false. */
1150 fold_predicate_in (tree stmt
)
1152 tree
*pred_p
= NULL
;
1153 bool modify_stmt_p
= false;
1156 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1157 && COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (stmt
, 1)))
1159 modify_stmt_p
= true;
1160 pred_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
1162 else if (TREE_CODE (stmt
) == COND_EXPR
)
1163 pred_p
= &COND_EXPR_COND (stmt
);
1167 if (TREE_CODE (*pred_p
) == SSA_NAME
)
1168 val
= vrp_evaluate_conditional (EQ_EXPR
,
1173 val
= vrp_evaluate_conditional (TREE_CODE (*pred_p
),
1174 TREE_OPERAND (*pred_p
, 0),
1175 TREE_OPERAND (*pred_p
, 1),
1181 val
= fold_convert (TREE_TYPE (*pred_p
), val
);
1185 fprintf (dump_file
, "Folding predicate ");
1186 print_generic_expr (dump_file
, *pred_p
, 0);
1187 fprintf (dump_file
, " to ");
1188 print_generic_expr (dump_file
, val
, 0);
1189 fprintf (dump_file
, "\n");
1192 prop_stats
.num_pred_folded
++;
1201 /* Perform final substitution and folding of propagated values.
1203 PROP_VALUE[I] contains the single value that should be substituted
1204 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1207 If USE_RANGES_P is true, statements that contain predicate
1208 expressions are evaluated with a call to vrp_evaluate_conditional.
1209 This will only give meaningful results when called from tree-vrp.c
1210 (the information used by vrp_evaluate_conditional is built by the
1213 Return TRUE when something changed. */
1216 substitute_and_fold (prop_value_t
*prop_value
, bool use_ranges_p
)
1219 bool something_changed
= false;
1221 if (prop_value
== NULL
&& !use_ranges_p
)
1224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1225 fprintf (dump_file
, "\nSubstituing values and folding statements\n\n");
1227 memset (&prop_stats
, 0, sizeof (prop_stats
));
1229 /* Substitute values in every statement of every basic block. */
1232 block_stmt_iterator i
;
1235 /* Propagate known values into PHI nodes. */
1237 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1238 replace_phi_args_in (phi
, prop_value
);
1240 /* Propagate known values into stmts. Do a backward walk to expose
1241 more trivially deletable stmts. */
1242 for (i
= bsi_last (bb
); !bsi_end_p (i
);)
1244 bool replaced_address
, did_replace
;
1245 tree call
, prev_stmt
= NULL
;
1246 tree stmt
= bsi_stmt (i
);
1248 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1249 range information for names and they are discarded
1251 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1252 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
1258 /* No point propagating into a stmt whose result is not used,
1259 but instead we might be able to remove a trivially dead stmt. */
1260 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1261 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
1262 && !stmt_ann (stmt
)->has_volatile_ops
1263 && has_zero_uses (GIMPLE_STMT_OPERAND (stmt
, 0))
1264 && !tree_could_throw_p (stmt
)
1265 && (!(call
= get_call_expr_in (stmt
))
1266 || !TREE_SIDE_EFFECTS (call
)))
1268 block_stmt_iterator i2
;
1269 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1271 fprintf (dump_file
, "Removing dead stmt ");
1272 print_generic_expr (dump_file
, stmt
, 0);
1273 fprintf (dump_file
, "\n");
1275 prop_stats
.num_dce
++;
1277 i2
= bsi_for_stmt (stmt
);
1278 bsi_remove (&i2
, true);
1279 release_defs (stmt
);
1283 /* Record the state of the statement before replacements. */
1284 push_stmt_changes (bsi_stmt_ptr (i
));
1286 /* Replace the statement with its folded version and mark it
1288 did_replace
= false;
1289 replaced_address
= false;
1290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1291 prev_stmt
= unshare_expr (stmt
);
1293 /* If we have range information, see if we can fold
1294 predicate expressions. */
1296 did_replace
= fold_predicate_in (stmt
);
1300 /* Only replace real uses if we couldn't fold the
1301 statement using value range information (value range
1302 information is not collected on virtuals, so we only
1303 need to check this for real uses). */
1305 did_replace
|= replace_uses_in (stmt
, &replaced_address
,
1308 did_replace
|= replace_vuses_in (stmt
, &replaced_address
,
1312 /* If we made a replacement, fold and cleanup the statement. */
1315 tree old_stmt
= stmt
;
1318 fold_stmt (bsi_stmt_ptr (i
));
1319 stmt
= bsi_stmt (i
);
1321 /* If we cleaned up EH information from the statement,
1323 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1324 tree_purge_dead_eh_edges (bb
);
1326 rhs
= get_rhs (stmt
);
1327 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1328 recompute_tree_invariant_for_addr_expr (rhs
);
1330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1332 fprintf (dump_file
, "Folded statement: ");
1333 print_generic_stmt (dump_file
, prev_stmt
, TDF_SLIM
);
1334 fprintf (dump_file
, " into: ");
1335 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1336 fprintf (dump_file
, "\n");
1339 /* Determine what needs to be done to update the SSA form. */
1340 pop_stmt_changes (bsi_stmt_ptr (i
));
1341 something_changed
= true;
1345 /* The statement was not modified, discard the change buffer. */
1346 discard_stmt_changes (bsi_stmt_ptr (i
));
1349 /* Some statements may be simplified using ranges. For
1350 example, division may be replaced by shifts, modulo
1351 replaced with bitwise and, etc. Do this after
1352 substituting constants, folding, etc so that we're
1353 presented with a fully propagated, canonicalized
1356 simplify_stmt_using_ranges (stmt
);
1362 statistics_counter_event (cfun
, "Constants propagated",
1363 prop_stats
.num_const_prop
);
1364 statistics_counter_event (cfun
, "Copies propagated",
1365 prop_stats
.num_copy_prop
);
1366 statistics_counter_event (cfun
, "Predicates folded",
1367 prop_stats
.num_pred_folded
);
1368 statistics_counter_event (cfun
, "Statements deleted",
1369 prop_stats
.num_dce
);
1370 return something_changed
;
1373 #include "gt-tree-ssa-propagate.h"