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
) != MODIFY_EXPR
)
539 stmt
= 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 if (TREE_CODE_CLASS (code
) == tcc_binary
)
576 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
577 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
580 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
582 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
585 else if (code
== ADDR_EXPR
)
587 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == ARRAY_REF
588 && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr
, 0), 1)))
591 else if (code
== COMPOUND_EXPR
592 || code
== MODIFY_EXPR
)
595 switch (TREE_CODE (stmt
))
598 op
= TREE_OPERAND (stmt
, 0);
599 if (TREE_CODE (op
) != MODIFY_EXPR
)
601 TREE_OPERAND (stmt
, 0) = expr
;
608 op
= TREE_OPERAND (stmt
, 1);
609 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
611 TREE_OPERAND (stmt
, 1) = expr
;
615 if (!is_gimple_condexpr (expr
))
617 COND_EXPR_COND (stmt
) = expr
;
620 SWITCH_COND (stmt
) = expr
;
623 GOTO_DESTINATION (stmt
) = expr
;
626 LABEL_EXPR_LABEL (stmt
) = expr
;
630 /* Replace the whole statement with EXPR. If EXPR has no side
631 effects, then replace *STMT_P with an empty statement. */
632 ann
= stmt_ann (stmt
);
633 *stmt_p
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
634 (*stmt_p
)->common
.ann
= (tree_ann_t
) ann
;
637 && TREE_SIDE_EFFECTS (expr
))
639 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
641 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_DEFS
)
643 if (TREE_CODE (var
) == SSA_NAME
)
644 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
654 /* Entry point to the propagation engine.
656 VISIT_STMT is called for every statement visited.
657 VISIT_PHI is called for every PHI node visited. */
660 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
661 ssa_prop_visit_phi_fn visit_phi
)
663 ssa_prop_visit_stmt
= visit_stmt
;
664 ssa_prop_visit_phi
= visit_phi
;
668 /* Iterate until the worklists are empty. */
669 while (!cfg_blocks_empty_p ()
670 || VEC_length (tree
, interesting_ssa_edges
) > 0
671 || VEC_length (tree
, varying_ssa_edges
) > 0)
673 if (!cfg_blocks_empty_p ())
675 /* Pull the next block to simulate off the worklist. */
676 basic_block dest_block
= cfg_blocks_get ();
677 simulate_block (dest_block
);
680 /* In order to move things to varying as quickly as
681 possible,process the VARYING_SSA_EDGES worklist first. */
682 process_ssa_edge_worklist (&varying_ssa_edges
);
684 /* Now process the INTERESTING_SSA_EDGES worklist. */
685 process_ssa_edge_worklist (&interesting_ssa_edges
);
692 /* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */
695 first_vdef (tree stmt
)
700 /* Simply return the first operand we arrive at. */
701 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
708 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
709 is a non-volatile pointer dereference, a structure reference or a
710 reference to a single _DECL. Ignore volatile memory references
711 because they are not interesting for the optimizers. */
714 stmt_makes_single_load (tree stmt
)
718 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
721 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VUSE
))
724 rhs
= TREE_OPERAND (stmt
, 1);
727 return (!TREE_THIS_VOLATILE (rhs
)
729 || REFERENCE_CLASS_P (rhs
)));
733 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
734 is a non-volatile pointer dereference, a structure reference or a
735 reference to a single _DECL. Ignore volatile memory references
736 because they are not interesting for the optimizers. */
739 stmt_makes_single_store (tree stmt
)
743 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
746 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VMUSTDEF
))
749 lhs
= TREE_OPERAND (stmt
, 0);
752 return (!TREE_THIS_VOLATILE (lhs
)
754 || REFERENCE_CLASS_P (lhs
)));
758 /* If STMT makes a single memory load and all the virtual use operands
759 have the same value in array VALUES, return it. Otherwise, return
763 get_value_loaded_by (tree stmt
, prop_value_t
*values
)
767 prop_value_t
*prev_val
= NULL
;
768 prop_value_t
*val
= NULL
;
770 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
, SSA_OP_VIRTUAL_USES
)
772 val
= &values
[SSA_NAME_VERSION (vuse
)];
773 if (prev_val
&& prev_val
->value
!= val
->value
)
782 /* Propagation statistics. */
787 long num_pred_folded
;
790 static struct prop_stats_d prop_stats
;
792 /* Replace USE references in statement STMT with the values stored in
793 PROP_VALUE. Return true if at least one reference was replaced. If
794 REPLACED_ADDRESSES_P is given, it will be set to true if an address
795 constant was replaced. */
798 replace_uses_in (tree stmt
, bool *replaced_addresses_p
,
799 prop_value_t
*prop_value
)
801 bool replaced
= false;
805 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
807 tree tuse
= USE_FROM_PTR (use
);
808 tree val
= prop_value
[SSA_NAME_VERSION (tuse
)].value
;
810 if (val
== tuse
|| val
== NULL_TREE
)
813 if (TREE_CODE (stmt
) == ASM_EXPR
814 && !may_propagate_copy_into_asm (tuse
))
817 if (!may_propagate_copy (tuse
, val
))
820 if (TREE_CODE (val
) != SSA_NAME
)
821 prop_stats
.num_const_prop
++;
823 prop_stats
.num_copy_prop
++;
825 propagate_value (use
, val
);
828 if (POINTER_TYPE_P (TREE_TYPE (tuse
)) && replaced_addresses_p
)
829 *replaced_addresses_p
= true;
836 /* Replace the VUSE references in statement STMT with the values
837 stored in PROP_VALUE. Return true if a reference was replaced. If
838 REPLACED_ADDRESSES_P is given, it will be set to true if an address
839 constant was replaced.
841 Replacing VUSE operands is slightly more complex than replacing
842 regular USEs. We are only interested in two types of replacements
845 1- If the value to be replaced is a constant or an SSA name for a
846 GIMPLE register, then we are making a copy/constant propagation
847 from a memory store. For instance,
849 # a_3 = V_MAY_DEF <a_2>
855 This replacement is only possible iff STMT is an assignment
856 whose RHS is identical to the LHS of the statement that created
857 the VUSE(s) that we are replacing. Otherwise, we may do the
860 # a_3 = V_MAY_DEF <a_2>
861 # b_5 = V_MAY_DEF <b_4>
867 Even though 'b_5' acquires the value '10' during propagation,
868 there is no way for the propagator to tell whether the
869 replacement is correct in every reached use, because values are
870 computed at definition sites. Therefore, when doing final
871 substitution of propagated values, we have to check each use
872 site. Since the RHS of STMT ('b') is different from the LHS of
873 the originating statement ('*p'), we cannot replace 'b' with
876 Similarly, when merging values from PHI node arguments,
877 propagators need to take care not to merge the same values
878 stored in different locations:
881 # a_3 = V_MAY_DEF <a_2>
884 # a_4 = V_MAY_DEF <a_2>
886 # a_5 = PHI <a_3, a_4>
888 It would be wrong to propagate '3' into 'a_5' because that
889 operation merges two stores to different memory locations.
892 2- If the value to be replaced is an SSA name for a virtual
893 register, then we simply replace each VUSE operand with its
894 value from PROP_VALUE. This is the same replacement done by
898 replace_vuses_in (tree stmt
, bool *replaced_addresses_p
,
899 prop_value_t
*prop_value
)
901 bool replaced
= false;
905 if (stmt_makes_single_load (stmt
))
907 /* If STMT is an assignment whose RHS is a single memory load,
908 see if we are trying to propagate a constant or a GIMPLE
909 register (case #1 above). */
910 prop_value_t
*val
= get_value_loaded_by (stmt
, prop_value
);
911 tree rhs
= TREE_OPERAND (stmt
, 1);
915 && (is_gimple_reg (val
->value
)
916 || is_gimple_min_invariant (val
->value
))
917 && simple_cst_equal (rhs
, val
->mem_ref
) == 1)
920 /* If we are replacing a constant address, inform our
922 if (TREE_CODE (val
->value
) != SSA_NAME
923 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt
, 1)))
924 && replaced_addresses_p
)
925 *replaced_addresses_p
= true;
927 /* We can only perform the substitution if the load is done
928 from the same memory location as the original store.
929 Since we already know that there are no intervening
930 stores between DEF_STMT and STMT, we only need to check
931 that the RHS of STMT is the same as the memory reference
932 propagated together with the value. */
933 TREE_OPERAND (stmt
, 1) = val
->value
;
935 if (TREE_CODE (val
->value
) != SSA_NAME
)
936 prop_stats
.num_const_prop
++;
938 prop_stats
.num_copy_prop
++;
940 /* Since we have replaced the whole RHS of STMT, there
941 is no point in checking the other VUSEs, as they will
942 all have the same value. */
947 /* Otherwise, the values for every VUSE operand must be other
948 SSA_NAMEs that can be propagated into STMT. */
949 FOR_EACH_SSA_USE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
951 tree var
= USE_FROM_PTR (vuse
);
952 tree val
= prop_value
[SSA_NAME_VERSION (var
)].value
;
954 if (val
== NULL_TREE
|| var
== val
)
957 /* Constants and copies propagated between real and virtual
958 operands are only possible in the cases handled above. They
959 should be ignored in any other context. */
960 if (is_gimple_min_invariant (val
) || is_gimple_reg (val
))
963 propagate_value (vuse
, val
);
964 prop_stats
.num_copy_prop
++;
972 /* Replace propagated values into all the arguments for PHI using the
973 values from PROP_VALUE. */
976 replace_phi_args_in (tree phi
, prop_value_t
*prop_value
)
979 bool replaced
= false;
980 tree prev_phi
= NULL
;
982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
983 prev_phi
= unshare_expr (phi
);
985 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
987 tree arg
= PHI_ARG_DEF (phi
, i
);
989 if (TREE_CODE (arg
) == SSA_NAME
)
991 tree val
= prop_value
[SSA_NAME_VERSION (arg
)].value
;
993 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
995 if (TREE_CODE (val
) != SSA_NAME
)
996 prop_stats
.num_const_prop
++;
998 prop_stats
.num_copy_prop
++;
1000 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
1003 /* If we propagated a copy and this argument flows
1004 through an abnormal edge, update the replacement
1006 if (TREE_CODE (val
) == SSA_NAME
1007 && PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_ABNORMAL
)
1008 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
1013 if (replaced
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1015 fprintf (dump_file
, "Folded PHI node: ");
1016 print_generic_stmt (dump_file
, prev_phi
, TDF_SLIM
);
1017 fprintf (dump_file
, " into: ");
1018 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1019 fprintf (dump_file
, "\n");
1024 /* If STMT has a predicate whose value can be computed using the value
1025 range information computed by VRP, compute its value and return true.
1026 Otherwise, return false. */
1029 fold_predicate_in (tree stmt
)
1031 tree
*pred_p
= NULL
;
1032 bool modify_expr_p
= false;
1035 if (TREE_CODE (stmt
) == MODIFY_EXPR
1036 && COMPARISON_CLASS_P (TREE_OPERAND (stmt
, 1)))
1038 modify_expr_p
= true;
1039 pred_p
= &TREE_OPERAND (stmt
, 1);
1041 else if (TREE_CODE (stmt
) == COND_EXPR
)
1042 pred_p
= &COND_EXPR_COND (stmt
);
1046 val
= vrp_evaluate_conditional (*pred_p
, true);
1050 val
= fold_convert (TREE_TYPE (*pred_p
), val
);
1054 fprintf (dump_file
, "Folding predicate ");
1055 print_generic_expr (dump_file
, *pred_p
, 0);
1056 fprintf (dump_file
, " to ");
1057 print_generic_expr (dump_file
, val
, 0);
1058 fprintf (dump_file
, "\n");
1061 prop_stats
.num_pred_folded
++;
1070 /* Perform final substitution and folding of propagated values.
1072 PROP_VALUE[I] contains the single value that should be substituted
1073 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1076 If USE_RANGES_P is true, statements that contain predicate
1077 expressions are evaluated with a call to vrp_evaluate_conditional.
1078 This will only give meaningful results when called from tree-vrp.c
1079 (the information used by vrp_evaluate_conditional is built by the
1083 substitute_and_fold (prop_value_t
*prop_value
, bool use_ranges_p
)
1087 if (prop_value
== NULL
&& !use_ranges_p
)
1090 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1091 fprintf (dump_file
, "\nSubstituing values and folding statements\n\n");
1093 memset (&prop_stats
, 0, sizeof (prop_stats
));
1095 /* Substitute values in every statement of every basic block. */
1098 block_stmt_iterator i
;
1101 /* Propagate known values into PHI nodes. */
1103 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1104 replace_phi_args_in (phi
, prop_value
);
1106 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
1108 bool replaced_address
, did_replace
;
1109 tree prev_stmt
= NULL
;
1110 tree stmt
= bsi_stmt (i
);
1112 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1113 range information for names and they are discarded
1115 if (TREE_CODE (stmt
) == MODIFY_EXPR
1116 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
1119 /* Replace the statement with its folded version and mark it
1121 did_replace
= false;
1122 replaced_address
= false;
1123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1124 prev_stmt
= unshare_expr (stmt
);
1126 /* If we have range information, see if we can fold
1127 predicate expressions. */
1129 did_replace
= fold_predicate_in (stmt
);
1133 /* Only replace real uses if we couldn't fold the
1134 statement using value range information (value range
1135 information is not collected on virtuals, so we only
1136 need to check this for real uses). */
1138 did_replace
|= replace_uses_in (stmt
, &replaced_address
,
1141 did_replace
|= replace_vuses_in (stmt
, &replaced_address
,
1145 /* If we made a replacement, fold and cleanup the statement. */
1148 tree old_stmt
= stmt
;
1151 fold_stmt (bsi_stmt_ptr (i
));
1152 stmt
= bsi_stmt (i
);
1154 /* If we folded a builtin function, we'll likely
1155 need to rename VDEFs. */
1156 mark_new_vars_to_rename (stmt
);
1158 /* If we cleaned up EH information from the statement,
1160 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1161 tree_purge_dead_eh_edges (bb
);
1163 rhs
= get_rhs (stmt
);
1164 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1165 recompute_tree_invariant_for_addr_expr (rhs
);
1167 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1169 fprintf (dump_file
, "Folded statement: ");
1170 print_generic_stmt (dump_file
, prev_stmt
, TDF_SLIM
);
1171 fprintf (dump_file
, " into: ");
1172 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1173 fprintf (dump_file
, "\n");
1177 /* Some statements may be simplified using ranges. For
1178 example, division may be replaced by shifts, modulo
1179 replaced with bitwise and, etc. Do this after
1180 substituting constants, folding, etc so that we're
1181 presented with a fully propagated, canonicalized
1184 simplify_stmt_using_ranges (stmt
);
1189 if (dump_file
&& (dump_flags
& TDF_STATS
))
1191 fprintf (dump_file
, "Constants propagated: %6ld\n",
1192 prop_stats
.num_const_prop
);
1193 fprintf (dump_file
, "Copies propagated: %6ld\n",
1194 prop_stats
.num_copy_prop
);
1195 fprintf (dump_file
, "Predicates folded: %6ld\n",
1196 prop_stats
.num_pred_folded
);
1200 #include "gt-tree-ssa-propagate.h"