1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005, 2006 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
31 #include "basic-block.h"
35 #include "diagnostic.h"
37 #include "tree-dump.h"
38 #include "tree-flow.h"
39 #include "tree-pass.h"
40 #include "tree-ssa-propagate.h"
41 #include "langhooks.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 TREE_DEPRECATED bitflag 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) TREE_DEPRECATED (T)
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
)
179 gcc_assert (bb
!= ENTRY_BLOCK_PTR
&& bb
!= EXIT_BLOCK_PTR
);
180 gcc_assert (!TEST_BIT (bb_in_list
, bb
->index
));
182 if (cfg_blocks_empty_p ())
184 cfg_blocks_tail
= cfg_blocks_head
= 0;
190 if (cfg_blocks_num
> VEC_length (basic_block
, cfg_blocks
))
192 /* We have to grow the array now. Adjust to queue to occupy
193 the full space of the original array. We do not need to
194 initialize the newly allocated portion of the array
195 because we keep track of CFG_BLOCKS_HEAD and
197 cfg_blocks_tail
= VEC_length (basic_block
, cfg_blocks
);
199 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 2 * cfg_blocks_tail
);
202 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1)
203 % VEC_length (basic_block
, cfg_blocks
));
206 VEC_replace (basic_block
, cfg_blocks
, cfg_blocks_tail
, bb
);
207 SET_BIT (bb_in_list
, bb
->index
);
211 /* Remove a block from the worklist. */
214 cfg_blocks_get (void)
218 bb
= VEC_index (basic_block
, cfg_blocks
, cfg_blocks_head
);
220 gcc_assert (!cfg_blocks_empty_p ());
223 cfg_blocks_head
= ((cfg_blocks_head
+ 1)
224 % VEC_length (basic_block
, cfg_blocks
));
226 RESET_BIT (bb_in_list
, bb
->index
);
232 /* We have just defined a new value for VAR. If IS_VARYING is true,
233 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
234 them to INTERESTING_SSA_EDGES. */
237 add_ssa_edge (tree var
, bool is_varying
)
239 imm_use_iterator iter
;
242 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
244 tree use_stmt
= USE_STMT (use_p
);
246 if (!DONT_SIMULATE_AGAIN (use_stmt
)
247 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt
))
249 STMT_IN_SSA_EDGE_WORKLIST (use_stmt
) = 1;
251 VEC_safe_push (tree
, gc
, varying_ssa_edges
, use_stmt
);
253 VEC_safe_push (tree
, gc
, interesting_ssa_edges
, use_stmt
);
259 /* Add edge E to the control flow worklist. */
262 add_control_edge (edge e
)
264 basic_block bb
= e
->dest
;
265 if (bb
== EXIT_BLOCK_PTR
)
268 /* If the edge had already been executed, skip it. */
269 if (e
->flags
& EDGE_EXECUTABLE
)
272 e
->flags
|= EDGE_EXECUTABLE
;
274 /* If the block is already in the list, we're done. */
275 if (TEST_BIT (bb_in_list
, bb
->index
))
280 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
281 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
282 e
->src
->index
, e
->dest
->index
);
286 /* Simulate the execution of STMT and update the work lists accordingly. */
289 simulate_stmt (tree stmt
)
291 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
292 edge taken_edge
= NULL
;
293 tree output_name
= NULL_TREE
;
295 /* Don't bother visiting statements that are already
296 considered varying by the propagator. */
297 if (DONT_SIMULATE_AGAIN (stmt
))
300 if (TREE_CODE (stmt
) == PHI_NODE
)
302 val
= ssa_prop_visit_phi (stmt
);
303 output_name
= PHI_RESULT (stmt
);
306 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
308 if (val
== SSA_PROP_VARYING
)
310 DONT_SIMULATE_AGAIN (stmt
) = 1;
312 /* If the statement produced a new varying value, add the SSA
313 edges coming out of OUTPUT_NAME. */
315 add_ssa_edge (output_name
, true);
317 /* If STMT transfers control out of its basic block, add
318 all outgoing edges to the work list. */
319 if (stmt_ends_bb_p (stmt
))
323 basic_block bb
= bb_for_stmt (stmt
);
324 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
325 add_control_edge (e
);
328 else if (val
== SSA_PROP_INTERESTING
)
330 /* If the statement produced new value, add the SSA edges coming
331 out of OUTPUT_NAME. */
333 add_ssa_edge (output_name
, false);
335 /* If we know which edge is going to be taken out of this block,
336 add it to the CFG work list. */
338 add_control_edge (taken_edge
);
342 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
343 drain. This pops statements off the given WORKLIST and processes
344 them until there are no more statements on WORKLIST.
345 We take a pointer to WORKLIST because it may be reallocated when an
346 SSA edge is added to it in simulate_stmt. */
349 process_ssa_edge_worklist (VEC(tree
,gc
) **worklist
)
351 /* Drain the entire worklist. */
352 while (VEC_length (tree
, *worklist
) > 0)
356 /* Pull the statement to simulate off the worklist. */
357 tree stmt
= VEC_pop (tree
, *worklist
);
359 /* If this statement was already visited by simulate_block, then
360 we don't need to visit it again here. */
361 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt
))
364 /* STMT is no longer in a worklist. */
365 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
369 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
370 print_generic_stmt (dump_file
, stmt
, dump_flags
);
373 bb
= bb_for_stmt (stmt
);
375 /* PHI nodes are always visited, regardless of whether or not
376 the destination block is executable. Otherwise, visit the
377 statement only if its block is marked executable. */
378 if (TREE_CODE (stmt
) == PHI_NODE
379 || TEST_BIT (executable_blocks
, bb
->index
))
380 simulate_stmt (stmt
);
385 /* Simulate the execution of BLOCK. Evaluate the statement associated
386 with each variable reference inside the block. */
389 simulate_block (basic_block block
)
393 /* There is nothing to do for the exit block. */
394 if (block
== EXIT_BLOCK_PTR
)
397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
398 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
400 /* Always simulate PHI nodes, even if we have simulated this block
402 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
405 /* If this is the first time we've simulated this block, then we
406 must simulate each of its statements. */
407 if (!TEST_BIT (executable_blocks
, block
->index
))
409 block_stmt_iterator j
;
410 unsigned int normal_edge_count
;
414 /* Note that we have simulated this block. */
415 SET_BIT (executable_blocks
, block
->index
);
417 for (j
= bsi_start (block
); !bsi_end_p (j
); bsi_next (&j
))
419 tree stmt
= bsi_stmt (j
);
421 /* If this statement is already in the worklist then
422 "cancel" it. The reevaluation implied by the worklist
423 entry will produce the same value we generate here and
424 thus reevaluating it again from the worklist is
426 if (STMT_IN_SSA_EDGE_WORKLIST (stmt
))
427 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
429 simulate_stmt (stmt
);
432 /* We can not predict when abnormal edges will be executed, so
433 once a block is considered executable, we consider any
434 outgoing abnormal edges as executable.
436 At the same time, if this block has only one successor that is
437 reached by non-abnormal edges, then add that successor to the
439 normal_edge_count
= 0;
441 FOR_EACH_EDGE (e
, ei
, block
->succs
)
443 if (e
->flags
& EDGE_ABNORMAL
)
444 add_control_edge (e
);
452 if (normal_edge_count
== 1)
453 add_control_edge (normal_edge
);
458 /* Initialize local data structures and work lists. */
468 /* Worklists of SSA edges. */
469 interesting_ssa_edges
= VEC_alloc (tree
, gc
, 20);
470 varying_ssa_edges
= VEC_alloc (tree
, gc
, 20);
472 executable_blocks
= sbitmap_alloc (last_basic_block
);
473 sbitmap_zero (executable_blocks
);
475 bb_in_list
= sbitmap_alloc (last_basic_block
);
476 sbitmap_zero (bb_in_list
);
478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
479 dump_immediate_uses (dump_file
);
481 cfg_blocks
= VEC_alloc (basic_block
, heap
, 20);
482 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 20);
484 /* Initialize the values for every SSA_NAME. */
485 for (i
= 1; i
< num_ssa_names
; i
++)
487 SSA_NAME_VALUE (ssa_name (i
)) = NULL_TREE
;
489 /* Initially assume that every edge in the CFG is not executable.
490 (including the edges coming out of ENTRY_BLOCK_PTR). */
493 block_stmt_iterator si
;
495 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
496 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si
)) = 0;
498 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
499 e
->flags
&= ~EDGE_EXECUTABLE
;
502 /* Seed the algorithm by adding the successors of the entry block to the
504 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
505 add_control_edge (e
);
509 /* Free allocated storage. */
514 VEC_free (tree
, gc
, interesting_ssa_edges
);
515 VEC_free (tree
, gc
, varying_ssa_edges
);
516 VEC_free (basic_block
, heap
, cfg_blocks
);
518 sbitmap_free (bb_in_list
);
519 sbitmap_free (executable_blocks
);
523 /* Get the main expression from statement STMT. */
528 enum tree_code code
= TREE_CODE (stmt
);
533 stmt
= TREE_OPERAND (stmt
, 0);
534 if (!stmt
|| TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
538 case GIMPLE_MODIFY_STMT
:
539 stmt
= GENERIC_TREE_OPERAND (stmt
, 1);
540 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
541 return TREE_OPERAND (stmt
, 0);
546 return COND_EXPR_COND (stmt
);
548 return SWITCH_COND (stmt
);
550 return GOTO_DESTINATION (stmt
);
552 return LABEL_EXPR_LABEL (stmt
);
560 /* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
561 GIMPLE expression no changes are done and the function returns
565 set_rhs (tree
*stmt_p
, tree expr
)
567 tree stmt
= *stmt_p
, op
;
568 enum tree_code code
= TREE_CODE (expr
);
573 /* Verify the constant folded result is valid gimple. */
574 switch (TREE_CODE_CLASS (code
))
576 case tcc_declaration
:
577 if (!is_gimple_variable(expr
))
586 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
587 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
592 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
600 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == ARRAY_REF
601 && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr
, 0), 1)))
606 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
613 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
614 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
628 case tcc_exceptional
:
643 if (EXPR_HAS_LOCATION (stmt
)
645 || GIMPLE_STMT_P (expr
))
646 && ! EXPR_HAS_LOCATION (expr
)
647 && TREE_SIDE_EFFECTS (expr
)
648 && TREE_CODE (expr
) != LABEL_EXPR
)
649 SET_EXPR_LOCATION (expr
, EXPR_LOCATION (stmt
));
651 switch (TREE_CODE (stmt
))
654 op
= TREE_OPERAND (stmt
, 0);
655 if (TREE_CODE (op
) != GIMPLE_MODIFY_STMT
)
657 GIMPLE_STMT_OPERAND (stmt
, 0) = expr
;
663 case GIMPLE_MODIFY_STMT
:
664 op
= GIMPLE_STMT_OPERAND (stmt
, 1);
665 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
668 TREE_OPERAND (stmt
, 1) = expr
;
671 GIMPLE_STMT_OPERAND (stmt
, 1) = expr
;
675 if (!is_gimple_condexpr (expr
))
677 COND_EXPR_COND (stmt
) = expr
;
680 SWITCH_COND (stmt
) = expr
;
683 GOTO_DESTINATION (stmt
) = expr
;
686 LABEL_EXPR_LABEL (stmt
) = expr
;
690 /* Replace the whole statement with EXPR. If EXPR has no side
691 effects, then replace *STMT_P with an empty statement. */
692 ann
= stmt_ann (stmt
);
693 *stmt_p
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
694 (*stmt_p
)->base
.ann
= (tree_ann_t
) ann
;
696 if (gimple_in_ssa_p (cfun
)
697 && TREE_SIDE_EFFECTS (expr
))
699 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
701 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_DEFS
)
703 if (TREE_CODE (var
) == SSA_NAME
)
704 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
714 /* Entry point to the propagation engine.
716 VISIT_STMT is called for every statement visited.
717 VISIT_PHI is called for every PHI node visited. */
720 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
721 ssa_prop_visit_phi_fn visit_phi
)
723 ssa_prop_visit_stmt
= visit_stmt
;
724 ssa_prop_visit_phi
= visit_phi
;
728 /* Iterate until the worklists are empty. */
729 while (!cfg_blocks_empty_p ()
730 || VEC_length (tree
, interesting_ssa_edges
) > 0
731 || VEC_length (tree
, varying_ssa_edges
) > 0)
733 if (!cfg_blocks_empty_p ())
735 /* Pull the next block to simulate off the worklist. */
736 basic_block dest_block
= cfg_blocks_get ();
737 simulate_block (dest_block
);
740 /* In order to move things to varying as quickly as
741 possible,process the VARYING_SSA_EDGES worklist first. */
742 process_ssa_edge_worklist (&varying_ssa_edges
);
744 /* Now process the INTERESTING_SSA_EDGES worklist. */
745 process_ssa_edge_worklist (&interesting_ssa_edges
);
752 /* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */
755 first_vdef (tree stmt
)
760 /* Simply return the first operand we arrive at. */
761 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
768 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
769 is a non-volatile pointer dereference, a structure reference or a
770 reference to a single _DECL. Ignore volatile memory references
771 because they are not interesting for the optimizers. */
774 stmt_makes_single_load (tree stmt
)
778 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
781 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VUSE
))
784 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
787 return (!TREE_THIS_VOLATILE (rhs
)
789 || REFERENCE_CLASS_P (rhs
)));
793 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
794 is a non-volatile pointer dereference, a structure reference or a
795 reference to a single _DECL. Ignore volatile memory references
796 because they are not interesting for the optimizers. */
799 stmt_makes_single_store (tree stmt
)
803 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
806 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VMUSTDEF
))
809 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
812 return (!TREE_THIS_VOLATILE (lhs
)
814 || REFERENCE_CLASS_P (lhs
)));
818 /* If STMT makes a single memory load and all the virtual use operands
819 have the same value in array VALUES, return it. Otherwise, return
823 get_value_loaded_by (tree stmt
, prop_value_t
*values
)
827 prop_value_t
*prev_val
= NULL
;
828 prop_value_t
*val
= NULL
;
830 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
, SSA_OP_VIRTUAL_USES
)
832 val
= &values
[SSA_NAME_VERSION (vuse
)];
833 if (prev_val
&& prev_val
->value
!= val
->value
)
842 /* Propagation statistics. */
847 long num_pred_folded
;
850 static struct prop_stats_d prop_stats
;
852 /* Replace USE references in statement STMT with the values stored in
853 PROP_VALUE. Return true if at least one reference was replaced. If
854 REPLACED_ADDRESSES_P is given, it will be set to true if an address
855 constant was replaced. */
858 replace_uses_in (tree stmt
, bool *replaced_addresses_p
,
859 prop_value_t
*prop_value
)
861 bool replaced
= false;
865 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
867 tree tuse
= USE_FROM_PTR (use
);
868 tree val
= prop_value
[SSA_NAME_VERSION (tuse
)].value
;
870 if (val
== tuse
|| val
== NULL_TREE
)
873 if (TREE_CODE (stmt
) == ASM_EXPR
874 && !may_propagate_copy_into_asm (tuse
))
877 if (!may_propagate_copy (tuse
, val
))
880 if (TREE_CODE (val
) != SSA_NAME
)
881 prop_stats
.num_const_prop
++;
883 prop_stats
.num_copy_prop
++;
885 propagate_value (use
, val
);
888 if (POINTER_TYPE_P (TREE_TYPE (tuse
)) && replaced_addresses_p
)
889 *replaced_addresses_p
= true;
896 /* Replace the VUSE references in statement STMT with the values
897 stored in PROP_VALUE. Return true if a reference was replaced. If
898 REPLACED_ADDRESSES_P is given, it will be set to true if an address
899 constant was replaced.
901 Replacing VUSE operands is slightly more complex than replacing
902 regular USEs. We are only interested in two types of replacements
905 1- If the value to be replaced is a constant or an SSA name for a
906 GIMPLE register, then we are making a copy/constant propagation
907 from a memory store. For instance,
909 # a_3 = V_MAY_DEF <a_2>
915 This replacement is only possible iff STMT is an assignment
916 whose RHS is identical to the LHS of the statement that created
917 the VUSE(s) that we are replacing. Otherwise, we may do the
920 # a_3 = V_MAY_DEF <a_2>
921 # b_5 = V_MAY_DEF <b_4>
927 Even though 'b_5' acquires the value '10' during propagation,
928 there is no way for the propagator to tell whether the
929 replacement is correct in every reached use, because values are
930 computed at definition sites. Therefore, when doing final
931 substitution of propagated values, we have to check each use
932 site. Since the RHS of STMT ('b') is different from the LHS of
933 the originating statement ('*p'), we cannot replace 'b' with
936 Similarly, when merging values from PHI node arguments,
937 propagators need to take care not to merge the same values
938 stored in different locations:
941 # a_3 = V_MAY_DEF <a_2>
944 # a_4 = V_MAY_DEF <a_2>
946 # a_5 = PHI <a_3, a_4>
948 It would be wrong to propagate '3' into 'a_5' because that
949 operation merges two stores to different memory locations.
952 2- If the value to be replaced is an SSA name for a virtual
953 register, then we simply replace each VUSE operand with its
954 value from PROP_VALUE. This is the same replacement done by
958 replace_vuses_in (tree stmt
, bool *replaced_addresses_p
,
959 prop_value_t
*prop_value
)
961 bool replaced
= false;
965 if (stmt_makes_single_load (stmt
))
967 /* If STMT is an assignment whose RHS is a single memory load,
968 see if we are trying to propagate a constant or a GIMPLE
969 register (case #1 above). */
970 prop_value_t
*val
= get_value_loaded_by (stmt
, prop_value
);
971 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
975 && (is_gimple_reg (val
->value
)
976 || is_gimple_min_invariant (val
->value
))
977 && simple_cst_equal (rhs
, val
->mem_ref
) == 1)
980 /* If we are replacing a constant address, inform our
982 if (TREE_CODE (val
->value
) != SSA_NAME
983 && POINTER_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 1)))
984 && replaced_addresses_p
)
985 *replaced_addresses_p
= true;
987 /* We can only perform the substitution if the load is done
988 from the same memory location as the original store.
989 Since we already know that there are no intervening
990 stores between DEF_STMT and STMT, we only need to check
991 that the RHS of STMT is the same as the memory reference
992 propagated together with the value. */
993 GIMPLE_STMT_OPERAND (stmt
, 1) = val
->value
;
995 if (TREE_CODE (val
->value
) != SSA_NAME
)
996 prop_stats
.num_const_prop
++;
998 prop_stats
.num_copy_prop
++;
1000 /* Since we have replaced the whole RHS of STMT, there
1001 is no point in checking the other VUSEs, as they will
1002 all have the same value. */
1007 /* Otherwise, the values for every VUSE operand must be other
1008 SSA_NAMEs that can be propagated into STMT. */
1009 FOR_EACH_SSA_USE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1011 tree var
= USE_FROM_PTR (vuse
);
1012 tree val
= prop_value
[SSA_NAME_VERSION (var
)].value
;
1014 if (val
== NULL_TREE
|| var
== val
)
1017 /* Constants and copies propagated between real and virtual
1018 operands are only possible in the cases handled above. They
1019 should be ignored in any other context. */
1020 if (is_gimple_min_invariant (val
) || is_gimple_reg (val
))
1023 propagate_value (vuse
, val
);
1024 prop_stats
.num_copy_prop
++;
1032 /* Replace propagated values into all the arguments for PHI using the
1033 values from PROP_VALUE. */
1036 replace_phi_args_in (tree phi
, prop_value_t
*prop_value
)
1039 bool replaced
= false;
1040 tree prev_phi
= NULL
;
1042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1043 prev_phi
= unshare_expr (phi
);
1045 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1047 tree arg
= PHI_ARG_DEF (phi
, i
);
1049 if (TREE_CODE (arg
) == SSA_NAME
)
1051 tree val
= prop_value
[SSA_NAME_VERSION (arg
)].value
;
1053 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
1055 if (TREE_CODE (val
) != SSA_NAME
)
1056 prop_stats
.num_const_prop
++;
1058 prop_stats
.num_copy_prop
++;
1060 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
1063 /* If we propagated a copy and this argument flows
1064 through an abnormal edge, update the replacement
1066 if (TREE_CODE (val
) == SSA_NAME
1067 && PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_ABNORMAL
)
1068 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
1073 if (replaced
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1075 fprintf (dump_file
, "Folded PHI node: ");
1076 print_generic_stmt (dump_file
, prev_phi
, TDF_SLIM
);
1077 fprintf (dump_file
, " into: ");
1078 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1079 fprintf (dump_file
, "\n");
1084 /* If STMT has a predicate whose value can be computed using the value
1085 range information computed by VRP, compute its value and return true.
1086 Otherwise, return false. */
1089 fold_predicate_in (tree stmt
)
1091 tree
*pred_p
= NULL
;
1092 bool modify_stmt_p
= false;
1095 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1096 && COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (stmt
, 1)))
1098 modify_stmt_p
= true;
1099 pred_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
1101 else if (TREE_CODE (stmt
) == COND_EXPR
)
1102 pred_p
= &COND_EXPR_COND (stmt
);
1106 val
= vrp_evaluate_conditional (*pred_p
, true);
1110 val
= fold_convert (TREE_TYPE (*pred_p
), val
);
1114 fprintf (dump_file
, "Folding predicate ");
1115 print_generic_expr (dump_file
, *pred_p
, 0);
1116 fprintf (dump_file
, " to ");
1117 print_generic_expr (dump_file
, val
, 0);
1118 fprintf (dump_file
, "\n");
1121 prop_stats
.num_pred_folded
++;
1130 /* Perform final substitution and folding of propagated values.
1132 PROP_VALUE[I] contains the single value that should be substituted
1133 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1136 If USE_RANGES_P is true, statements that contain predicate
1137 expressions are evaluated with a call to vrp_evaluate_conditional.
1138 This will only give meaningful results when called from tree-vrp.c
1139 (the information used by vrp_evaluate_conditional is built by the
1143 substitute_and_fold (prop_value_t
*prop_value
, bool use_ranges_p
)
1147 if (prop_value
== NULL
&& !use_ranges_p
)
1150 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1151 fprintf (dump_file
, "\nSubstituing values and folding statements\n\n");
1153 memset (&prop_stats
, 0, sizeof (prop_stats
));
1155 /* Substitute values in every statement of every basic block. */
1158 block_stmt_iterator i
;
1161 /* Propagate known values into PHI nodes. */
1163 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1164 replace_phi_args_in (phi
, prop_value
);
1166 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
1168 bool replaced_address
, did_replace
;
1169 tree prev_stmt
= NULL
;
1170 tree stmt
= bsi_stmt (i
);
1172 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1173 range information for names and they are discarded
1175 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1176 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
1179 /* Record the state of the statement before replacements. */
1180 push_stmt_changes (bsi_stmt_ptr (i
));
1182 /* Replace the statement with its folded version and mark it
1184 did_replace
= false;
1185 replaced_address
= false;
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1187 prev_stmt
= unshare_expr (stmt
);
1189 /* If we have range information, see if we can fold
1190 predicate expressions. */
1192 did_replace
= fold_predicate_in (stmt
);
1196 /* Only replace real uses if we couldn't fold the
1197 statement using value range information (value range
1198 information is not collected on virtuals, so we only
1199 need to check this for real uses). */
1201 did_replace
|= replace_uses_in (stmt
, &replaced_address
,
1204 did_replace
|= replace_vuses_in (stmt
, &replaced_address
,
1208 /* If we made a replacement, fold and cleanup the statement. */
1211 tree old_stmt
= stmt
;
1214 fold_stmt (bsi_stmt_ptr (i
));
1215 stmt
= bsi_stmt (i
);
1217 /* If we cleaned up EH information from the statement,
1219 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1220 tree_purge_dead_eh_edges (bb
);
1222 rhs
= get_rhs (stmt
);
1223 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1224 recompute_tree_invariant_for_addr_expr (rhs
);
1226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1228 fprintf (dump_file
, "Folded statement: ");
1229 print_generic_stmt (dump_file
, prev_stmt
, TDF_SLIM
);
1230 fprintf (dump_file
, " into: ");
1231 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1232 fprintf (dump_file
, "\n");
1235 /* Determine what needs to be done to update the SSA form. */
1236 pop_stmt_changes (bsi_stmt_ptr (i
));
1240 /* The statement was not modified, discard the change buffer. */
1241 discard_stmt_changes (bsi_stmt_ptr (i
));
1244 /* Some statements may be simplified using ranges. For
1245 example, division may be replaced by shifts, modulo
1246 replaced with bitwise and, etc. Do this after
1247 substituting constants, folding, etc so that we're
1248 presented with a fully propagated, canonicalized
1251 simplify_stmt_using_ranges (stmt
);
1255 if (dump_file
&& (dump_flags
& TDF_STATS
))
1257 fprintf (dump_file
, "Constants propagated: %6ld\n",
1258 prop_stats
.num_const_prop
);
1259 fprintf (dump_file
, "Copies propagated: %6ld\n",
1260 prop_stats
.num_copy_prop
);
1261 fprintf (dump_file
, "Predicates folded: %6ld\n",
1262 prop_stats
.num_pred_folded
);
1266 #include "gt-tree-ssa-propagate.h"