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"
44 /* This file implements a generic value propagation engine based on
45 the same propagation used by the SSA-CCP algorithm [1].
47 Propagation is performed by simulating the execution of every
48 statement that produces the value being propagated. Simulation
51 1- Initially, all edges of the CFG are marked not executable and
52 the CFG worklist is seeded with all the statements in the entry
53 basic block (block 0).
55 2- Every statement S is simulated with a call to the call-back
56 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
59 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
60 interest and does not affect any of the work lists.
62 SSA_PROP_VARYING: The value produced by S cannot be determined
63 at compile time. Further simulation of S is not required.
64 If S is a conditional jump, all the outgoing edges for the
65 block are considered executable and added to the work
68 SSA_PROP_INTERESTING: S produces a value that can be computed
69 at compile time. Its result can be propagated into the
70 statements that feed from S. Furthermore, if S is a
71 conditional jump, only the edge known to be taken is added
72 to the work list. Edges that are known not to execute are
75 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
76 return value from SSA_PROP_VISIT_PHI has the same semantics as
79 4- Three work lists are kept. Statements are only added to these
80 lists if they produce one of SSA_PROP_INTERESTING or
83 CFG_BLOCKS contains the list of blocks to be simulated.
84 Blocks are added to this list if their incoming edges are
87 VARYING_SSA_EDGES contains the list of statements that feed
88 from statements that produce an SSA_PROP_VARYING result.
89 These are simulated first to speed up processing.
91 INTERESTING_SSA_EDGES contains the list of statements that
92 feed from statements that produce an SSA_PROP_INTERESTING
95 5- Simulation terminates when all three work lists are drained.
97 Before calling ssa_propagate, it is important to clear
98 DONT_SIMULATE_AGAIN for all the statements in the program that
99 should be simulated. This initialization allows an implementation
100 to specify which statements should never be simulated.
102 It is also important to compute def-use information before calling
107 [1] Constant propagation with conditional branches,
108 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
110 [2] Building an Optimizing Compiler,
111 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
113 [3] Advanced Compiler Design and Implementation,
114 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
116 /* Function pointers used to parameterize the propagation engine. */
117 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
118 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
120 /* Use the TREE_DEPRECATED bitflag to mark statements that have been
121 added to one of the SSA edges worklists. This flag is used to
122 avoid visiting statements unnecessarily when draining an SSA edge
123 worklist. If while simulating a basic block, we find a statement with
124 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
125 processing from visiting it again. */
126 #define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
128 /* A bitmap to keep track of executable blocks in the CFG. */
129 static sbitmap executable_blocks
;
131 /* Array of control flow edges on the worklist. */
132 static VEC(basic_block
,heap
) *cfg_blocks
;
134 static unsigned int cfg_blocks_num
= 0;
135 static int cfg_blocks_tail
;
136 static int cfg_blocks_head
;
138 static sbitmap bb_in_list
;
140 /* Worklist of SSA edges which will need reexamination as their
141 definition has changed. SSA edges are def-use edges in the SSA
142 web. For each D-U edge, we store the target statement or PHI node
144 static GTY(()) VEC(tree
,gc
) *interesting_ssa_edges
;
146 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
147 list of SSA edges is split into two. One contains all SSA edges
148 who need to be reexamined because their lattice value changed to
149 varying (this worklist), and the other contains all other SSA edges
150 to be reexamined (INTERESTING_SSA_EDGES).
152 Since most values in the program are VARYING, the ideal situation
153 is to move them to that lattice value as quickly as possible.
154 Thus, it doesn't make sense to process any other type of lattice
155 value until all VARYING values are propagated fully, which is one
156 thing using the VARYING worklist achieves. In addition, if we
157 don't use a separate worklist for VARYING edges, we end up with
158 situations where lattice values move from
159 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
160 static GTY(()) VEC(tree
,gc
) *varying_ssa_edges
;
163 /* Return true if the block worklist empty. */
166 cfg_blocks_empty_p (void)
168 return (cfg_blocks_num
== 0);
172 /* Add a basic block to the worklist. The block must not be already
173 in the worklist, and it must not be the ENTRY or EXIT block. */
176 cfg_blocks_add (basic_block bb
)
180 gcc_assert (bb
!= ENTRY_BLOCK_PTR
&& bb
!= EXIT_BLOCK_PTR
);
181 gcc_assert (!TEST_BIT (bb_in_list
, bb
->index
));
183 if (cfg_blocks_empty_p ())
185 cfg_blocks_tail
= cfg_blocks_head
= 0;
191 if (cfg_blocks_num
> VEC_length (basic_block
, cfg_blocks
))
193 /* We have to grow the array now. Adjust to queue to occupy
194 the full space of the original array. We do not need to
195 initialize the newly allocated portion of the array
196 because we keep track of CFG_BLOCKS_HEAD and
198 cfg_blocks_tail
= VEC_length (basic_block
, cfg_blocks
);
200 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 2 * cfg_blocks_tail
);
202 /* Minor optimization: we prefer to see blocks with more
203 predecessors later, because there is more of a chance that
204 the incoming edges will be executable. */
205 else if (EDGE_COUNT (bb
->preds
)
206 >= EDGE_COUNT (VEC_index (basic_block
, cfg_blocks
,
207 cfg_blocks_head
)->preds
))
208 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1)
209 % VEC_length (basic_block
, cfg_blocks
));
212 if (cfg_blocks_head
== 0)
213 cfg_blocks_head
= VEC_length (basic_block
, cfg_blocks
);
219 VEC_replace (basic_block
, cfg_blocks
,
220 head
? cfg_blocks_head
: cfg_blocks_tail
,
222 SET_BIT (bb_in_list
, bb
->index
);
226 /* Remove a block from the worklist. */
229 cfg_blocks_get (void)
233 bb
= VEC_index (basic_block
, cfg_blocks
, cfg_blocks_head
);
235 gcc_assert (!cfg_blocks_empty_p ());
238 cfg_blocks_head
= ((cfg_blocks_head
+ 1)
239 % VEC_length (basic_block
, cfg_blocks
));
241 RESET_BIT (bb_in_list
, bb
->index
);
247 /* We have just defined a new value for VAR. If IS_VARYING is true,
248 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
249 them to INTERESTING_SSA_EDGES. */
252 add_ssa_edge (tree var
, bool is_varying
)
254 imm_use_iterator iter
;
257 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
259 tree use_stmt
= USE_STMT (use_p
);
261 if (!DONT_SIMULATE_AGAIN (use_stmt
)
262 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt
))
264 STMT_IN_SSA_EDGE_WORKLIST (use_stmt
) = 1;
266 VEC_safe_push (tree
, gc
, varying_ssa_edges
, use_stmt
);
268 VEC_safe_push (tree
, gc
, interesting_ssa_edges
, use_stmt
);
274 /* Add edge E to the control flow worklist. */
277 add_control_edge (edge e
)
279 basic_block bb
= e
->dest
;
280 if (bb
== EXIT_BLOCK_PTR
)
283 /* If the edge had already been executed, skip it. */
284 if (e
->flags
& EDGE_EXECUTABLE
)
287 e
->flags
|= EDGE_EXECUTABLE
;
289 /* If the block is already in the list, we're done. */
290 if (TEST_BIT (bb_in_list
, bb
->index
))
295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
297 e
->src
->index
, e
->dest
->index
);
301 /* Simulate the execution of STMT and update the work lists accordingly. */
304 simulate_stmt (tree stmt
)
306 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
307 edge taken_edge
= NULL
;
308 tree output_name
= NULL_TREE
;
310 /* Don't bother visiting statements that are already
311 considered varying by the propagator. */
312 if (DONT_SIMULATE_AGAIN (stmt
))
315 if (TREE_CODE (stmt
) == PHI_NODE
)
317 val
= ssa_prop_visit_phi (stmt
);
318 output_name
= PHI_RESULT (stmt
);
321 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
323 if (val
== SSA_PROP_VARYING
)
325 DONT_SIMULATE_AGAIN (stmt
) = 1;
327 /* If the statement produced a new varying value, add the SSA
328 edges coming out of OUTPUT_NAME. */
330 add_ssa_edge (output_name
, true);
332 /* If STMT transfers control out of its basic block, add
333 all outgoing edges to the work list. */
334 if (stmt_ends_bb_p (stmt
))
338 basic_block bb
= bb_for_stmt (stmt
);
339 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
340 add_control_edge (e
);
343 else if (val
== SSA_PROP_INTERESTING
)
345 /* If the statement produced new value, add the SSA edges coming
346 out of OUTPUT_NAME. */
348 add_ssa_edge (output_name
, false);
350 /* If we know which edge is going to be taken out of this block,
351 add it to the CFG work list. */
353 add_control_edge (taken_edge
);
357 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
358 drain. This pops statements off the given WORKLIST and processes
359 them until there are no more statements on WORKLIST.
360 We take a pointer to WORKLIST because it may be reallocated when an
361 SSA edge is added to it in simulate_stmt. */
364 process_ssa_edge_worklist (VEC(tree
,gc
) **worklist
)
366 /* Drain the entire worklist. */
367 while (VEC_length (tree
, *worklist
) > 0)
371 /* Pull the statement to simulate off the worklist. */
372 tree stmt
= VEC_pop (tree
, *worklist
);
374 /* If this statement was already visited by simulate_block, then
375 we don't need to visit it again here. */
376 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt
))
379 /* STMT is no longer in a worklist. */
380 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
384 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
385 print_generic_stmt (dump_file
, stmt
, dump_flags
);
388 bb
= bb_for_stmt (stmt
);
390 /* PHI nodes are always visited, regardless of whether or not
391 the destination block is executable. Otherwise, visit the
392 statement only if its block is marked executable. */
393 if (TREE_CODE (stmt
) == PHI_NODE
394 || TEST_BIT (executable_blocks
, bb
->index
))
395 simulate_stmt (stmt
);
400 /* Simulate the execution of BLOCK. Evaluate the statement associated
401 with each variable reference inside the block. */
404 simulate_block (basic_block block
)
408 /* There is nothing to do for the exit block. */
409 if (block
== EXIT_BLOCK_PTR
)
412 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
413 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
415 /* Always simulate PHI nodes, even if we have simulated this block
417 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
420 /* If this is the first time we've simulated this block, then we
421 must simulate each of its statements. */
422 if (!TEST_BIT (executable_blocks
, block
->index
))
424 block_stmt_iterator j
;
425 unsigned int normal_edge_count
;
429 /* Note that we have simulated this block. */
430 SET_BIT (executable_blocks
, block
->index
);
432 for (j
= bsi_start (block
); !bsi_end_p (j
); bsi_next (&j
))
434 tree stmt
= bsi_stmt (j
);
436 /* If this statement is already in the worklist then
437 "cancel" it. The reevaluation implied by the worklist
438 entry will produce the same value we generate here and
439 thus reevaluating it again from the worklist is
441 if (STMT_IN_SSA_EDGE_WORKLIST (stmt
))
442 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
444 simulate_stmt (stmt
);
447 /* We can not predict when abnormal edges will be executed, so
448 once a block is considered executable, we consider any
449 outgoing abnormal edges as executable.
451 At the same time, if this block has only one successor that is
452 reached by non-abnormal edges, then add that successor to the
454 normal_edge_count
= 0;
456 FOR_EACH_EDGE (e
, ei
, block
->succs
)
458 if (e
->flags
& EDGE_ABNORMAL
)
459 add_control_edge (e
);
467 if (normal_edge_count
== 1)
468 add_control_edge (normal_edge
);
473 /* Initialize local data structures and work lists. */
483 /* Worklists of SSA edges. */
484 interesting_ssa_edges
= VEC_alloc (tree
, gc
, 20);
485 varying_ssa_edges
= VEC_alloc (tree
, gc
, 20);
487 executable_blocks
= sbitmap_alloc (last_basic_block
);
488 sbitmap_zero (executable_blocks
);
490 bb_in_list
= sbitmap_alloc (last_basic_block
);
491 sbitmap_zero (bb_in_list
);
493 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
494 dump_immediate_uses (dump_file
);
496 cfg_blocks
= VEC_alloc (basic_block
, heap
, 20);
497 VEC_safe_grow (basic_block
, heap
, cfg_blocks
, 20);
499 /* Initialize the values for every SSA_NAME. */
500 for (i
= 1; i
< num_ssa_names
; i
++)
502 SSA_NAME_VALUE (ssa_name (i
)) = NULL_TREE
;
504 /* Initially assume that every edge in the CFG is not executable.
505 (including the edges coming out of ENTRY_BLOCK_PTR). */
508 block_stmt_iterator si
;
510 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
511 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si
)) = 0;
513 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
514 e
->flags
&= ~EDGE_EXECUTABLE
;
517 /* Seed the algorithm by adding the successors of the entry block to the
519 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
520 add_control_edge (e
);
524 /* Free allocated storage. */
529 VEC_free (tree
, gc
, interesting_ssa_edges
);
530 VEC_free (tree
, gc
, varying_ssa_edges
);
531 VEC_free (basic_block
, heap
, cfg_blocks
);
533 sbitmap_free (bb_in_list
);
534 sbitmap_free (executable_blocks
);
538 /* Get the main expression from statement STMT. */
543 enum tree_code code
= TREE_CODE (stmt
);
548 stmt
= TREE_OPERAND (stmt
, 0);
549 if (!stmt
|| TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
553 case GIMPLE_MODIFY_STMT
:
554 stmt
= GENERIC_TREE_OPERAND (stmt
, 1);
555 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
556 return TREE_OPERAND (stmt
, 0);
561 return COND_EXPR_COND (stmt
);
563 return SWITCH_COND (stmt
);
565 return GOTO_DESTINATION (stmt
);
567 return LABEL_EXPR_LABEL (stmt
);
575 /* Return true if EXPR is a valid GIMPLE expression. */
578 valid_gimple_expression_p (tree expr
)
580 enum tree_code code
= TREE_CODE (expr
);
582 switch (TREE_CODE_CLASS (code
))
584 case tcc_declaration
:
585 if (!is_gimple_variable (expr
))
594 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
595 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
600 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
609 tree t
= TREE_OPERAND (expr
, 0);
610 while (handled_component_p (t
))
612 /* ??? More checks needed, see the GIMPLE verifier. */
613 if ((TREE_CODE (t
) == ARRAY_REF
614 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
615 && !is_gimple_val (TREE_OPERAND (t
, 1)))
617 t
= TREE_OPERAND (t
, 0);
619 if (!is_gimple_id (t
))
625 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
632 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
633 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
656 case tcc_exceptional
:
675 /* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
676 GIMPLE expression no changes are done and the function returns
680 set_rhs (tree
*stmt_p
, tree expr
)
682 tree stmt
= *stmt_p
, op
;
687 if (!valid_gimple_expression_p (expr
))
690 if (EXPR_HAS_LOCATION (stmt
)
692 || GIMPLE_STMT_P (expr
))
693 && ! EXPR_HAS_LOCATION (expr
)
694 && TREE_SIDE_EFFECTS (expr
)
695 && TREE_CODE (expr
) != LABEL_EXPR
)
696 SET_EXPR_LOCATION (expr
, EXPR_LOCATION (stmt
));
698 switch (TREE_CODE (stmt
))
701 op
= TREE_OPERAND (stmt
, 0);
702 if (TREE_CODE (op
) != GIMPLE_MODIFY_STMT
)
704 GIMPLE_STMT_OPERAND (stmt
, 0) = expr
;
710 case GIMPLE_MODIFY_STMT
:
711 op
= GIMPLE_STMT_OPERAND (stmt
, 1);
712 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
713 TREE_OPERAND (op
, 0) = expr
;
715 GIMPLE_STMT_OPERAND (stmt
, 1) = expr
;
719 if (!is_gimple_condexpr (expr
))
721 COND_EXPR_COND (stmt
) = expr
;
724 SWITCH_COND (stmt
) = expr
;
727 GOTO_DESTINATION (stmt
) = expr
;
730 LABEL_EXPR_LABEL (stmt
) = expr
;
734 /* Replace the whole statement with EXPR. If EXPR has no side
735 effects, then replace *STMT_P with an empty statement. */
736 ann
= stmt_ann (stmt
);
737 *stmt_p
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
738 (*stmt_p
)->base
.ann
= (tree_ann_t
) ann
;
740 if (gimple_in_ssa_p (cfun
)
741 && TREE_SIDE_EFFECTS (expr
))
743 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
745 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_DEFS
)
747 if (TREE_CODE (var
) == SSA_NAME
)
748 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
751 stmt
->base
.ann
= NULL
;
759 /* Entry point to the propagation engine.
761 VISIT_STMT is called for every statement visited.
762 VISIT_PHI is called for every PHI node visited. */
765 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
766 ssa_prop_visit_phi_fn visit_phi
)
768 ssa_prop_visit_stmt
= visit_stmt
;
769 ssa_prop_visit_phi
= visit_phi
;
773 /* Iterate until the worklists are empty. */
774 while (!cfg_blocks_empty_p ()
775 || VEC_length (tree
, interesting_ssa_edges
) > 0
776 || VEC_length (tree
, varying_ssa_edges
) > 0)
778 if (!cfg_blocks_empty_p ())
780 /* Pull the next block to simulate off the worklist. */
781 basic_block dest_block
= cfg_blocks_get ();
782 simulate_block (dest_block
);
785 /* In order to move things to varying as quickly as
786 possible,process the VARYING_SSA_EDGES worklist first. */
787 process_ssa_edge_worklist (&varying_ssa_edges
);
789 /* Now process the INTERESTING_SSA_EDGES worklist. */
790 process_ssa_edge_worklist (&interesting_ssa_edges
);
797 /* Return the first VDEF operand for STMT. */
800 first_vdef (tree stmt
)
805 /* Simply return the first operand we arrive at. */
806 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
813 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
814 is a non-volatile pointer dereference, a structure reference or a
815 reference to a single _DECL. Ignore volatile memory references
816 because they are not interesting for the optimizers. */
819 stmt_makes_single_load (tree stmt
)
823 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
826 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
|SSA_OP_VUSE
))
829 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
832 return (!TREE_THIS_VOLATILE (rhs
)
834 || REFERENCE_CLASS_P (rhs
)));
838 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
839 is a non-volatile pointer dereference, a structure reference or a
840 reference to a single _DECL. Ignore volatile memory references
841 because they are not interesting for the optimizers. */
844 stmt_makes_single_store (tree stmt
)
848 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
851 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
))
854 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
857 return (!TREE_THIS_VOLATILE (lhs
)
859 || REFERENCE_CLASS_P (lhs
)));
863 /* If STMT makes a single memory load and all the virtual use operands
864 have the same value in array VALUES, return it. Otherwise, return
868 get_value_loaded_by (tree stmt
, prop_value_t
*values
)
872 prop_value_t
*prev_val
= NULL
;
873 prop_value_t
*val
= NULL
;
875 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
, SSA_OP_VIRTUAL_USES
)
877 val
= &values
[SSA_NAME_VERSION (vuse
)];
878 if (prev_val
&& prev_val
->value
!= val
->value
)
887 /* Propagation statistics. */
892 long num_pred_folded
;
895 static struct prop_stats_d prop_stats
;
897 /* Replace USE references in statement STMT with the values stored in
898 PROP_VALUE. Return true if at least one reference was replaced. If
899 REPLACED_ADDRESSES_P is given, it will be set to true if an address
900 constant was replaced. */
903 replace_uses_in (tree stmt
, bool *replaced_addresses_p
,
904 prop_value_t
*prop_value
)
906 bool replaced
= false;
910 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
912 tree tuse
= USE_FROM_PTR (use
);
913 tree val
= prop_value
[SSA_NAME_VERSION (tuse
)].value
;
915 if (val
== tuse
|| val
== NULL_TREE
)
918 if (TREE_CODE (stmt
) == ASM_EXPR
919 && !may_propagate_copy_into_asm (tuse
))
922 if (!may_propagate_copy (tuse
, val
))
925 if (TREE_CODE (val
) != SSA_NAME
)
926 prop_stats
.num_const_prop
++;
928 prop_stats
.num_copy_prop
++;
930 propagate_value (use
, val
);
933 if (POINTER_TYPE_P (TREE_TYPE (tuse
)) && replaced_addresses_p
)
934 *replaced_addresses_p
= true;
941 /* Replace the VUSE references in statement STMT with the values
942 stored in PROP_VALUE. Return true if a reference was replaced. If
943 REPLACED_ADDRESSES_P is given, it will be set to true if an address
944 constant was replaced.
946 Replacing VUSE operands is slightly more complex than replacing
947 regular USEs. We are only interested in two types of replacements
950 1- If the value to be replaced is a constant or an SSA name for a
951 GIMPLE register, then we are making a copy/constant propagation
952 from a memory store. For instance,
960 This replacement is only possible iff STMT is an assignment
961 whose RHS is identical to the LHS of the statement that created
962 the VUSE(s) that we are replacing. Otherwise, we may do the
972 Even though 'b_5' acquires the value '10' during propagation,
973 there is no way for the propagator to tell whether the
974 replacement is correct in every reached use, because values are
975 computed at definition sites. Therefore, when doing final
976 substitution of propagated values, we have to check each use
977 site. Since the RHS of STMT ('b') is different from the LHS of
978 the originating statement ('*p'), we cannot replace 'b' with
981 Similarly, when merging values from PHI node arguments,
982 propagators need to take care not to merge the same values
983 stored in different locations:
991 # a_5 = PHI <a_3, a_4>
993 It would be wrong to propagate '3' into 'a_5' because that
994 operation merges two stores to different memory locations.
997 2- If the value to be replaced is an SSA name for a virtual
998 register, then we simply replace each VUSE operand with its
999 value from PROP_VALUE. This is the same replacement done by
1003 replace_vuses_in (tree stmt
, bool *replaced_addresses_p
,
1004 prop_value_t
*prop_value
)
1006 bool replaced
= false;
1010 if (stmt_makes_single_load (stmt
))
1012 /* If STMT is an assignment whose RHS is a single memory load,
1013 see if we are trying to propagate a constant or a GIMPLE
1014 register (case #1 above). */
1015 prop_value_t
*val
= get_value_loaded_by (stmt
, prop_value
);
1016 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1020 && (is_gimple_reg (val
->value
)
1021 || is_gimple_min_invariant (val
->value
))
1022 && simple_cst_equal (rhs
, val
->mem_ref
) == 1)
1025 /* If we are replacing a constant address, inform our
1027 if (TREE_CODE (val
->value
) != SSA_NAME
1028 && POINTER_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 1)))
1029 && replaced_addresses_p
)
1030 *replaced_addresses_p
= true;
1032 /* We can only perform the substitution if the load is done
1033 from the same memory location as the original store.
1034 Since we already know that there are no intervening
1035 stores between DEF_STMT and STMT, we only need to check
1036 that the RHS of STMT is the same as the memory reference
1037 propagated together with the value. */
1038 GIMPLE_STMT_OPERAND (stmt
, 1) = val
->value
;
1040 if (TREE_CODE (val
->value
) != SSA_NAME
)
1041 prop_stats
.num_const_prop
++;
1043 prop_stats
.num_copy_prop
++;
1045 /* Since we have replaced the whole RHS of STMT, there
1046 is no point in checking the other VUSEs, as they will
1047 all have the same value. */
1052 /* Otherwise, the values for every VUSE operand must be other
1053 SSA_NAMEs that can be propagated into STMT. */
1054 FOR_EACH_SSA_USE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1056 tree var
= USE_FROM_PTR (vuse
);
1057 tree val
= prop_value
[SSA_NAME_VERSION (var
)].value
;
1059 if (val
== NULL_TREE
|| var
== val
)
1062 /* Constants and copies propagated between real and virtual
1063 operands are only possible in the cases handled above. They
1064 should be ignored in any other context. */
1065 if (is_gimple_min_invariant (val
) || is_gimple_reg (val
))
1068 propagate_value (vuse
, val
);
1069 prop_stats
.num_copy_prop
++;
1077 /* Replace propagated values into all the arguments for PHI using the
1078 values from PROP_VALUE. */
1081 replace_phi_args_in (tree phi
, prop_value_t
*prop_value
)
1084 bool replaced
= false;
1085 tree prev_phi
= NULL
;
1087 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1088 prev_phi
= unshare_expr (phi
);
1090 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1092 tree arg
= PHI_ARG_DEF (phi
, i
);
1094 if (TREE_CODE (arg
) == SSA_NAME
)
1096 tree val
= prop_value
[SSA_NAME_VERSION (arg
)].value
;
1098 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
1100 if (TREE_CODE (val
) != SSA_NAME
)
1101 prop_stats
.num_const_prop
++;
1103 prop_stats
.num_copy_prop
++;
1105 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
1108 /* If we propagated a copy and this argument flows
1109 through an abnormal edge, update the replacement
1111 if (TREE_CODE (val
) == SSA_NAME
1112 && PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_ABNORMAL
)
1113 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
1118 if (replaced
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1120 fprintf (dump_file
, "Folded PHI node: ");
1121 print_generic_stmt (dump_file
, prev_phi
, TDF_SLIM
);
1122 fprintf (dump_file
, " into: ");
1123 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1124 fprintf (dump_file
, "\n");
1129 /* If STMT has a predicate whose value can be computed using the value
1130 range information computed by VRP, compute its value and return true.
1131 Otherwise, return false. */
1134 fold_predicate_in (tree stmt
)
1136 tree
*pred_p
= NULL
;
1137 bool modify_stmt_p
= false;
1140 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1141 && COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (stmt
, 1)))
1143 modify_stmt_p
= true;
1144 pred_p
= &GIMPLE_STMT_OPERAND (stmt
, 1);
1146 else if (TREE_CODE (stmt
) == COND_EXPR
)
1147 pred_p
= &COND_EXPR_COND (stmt
);
1151 if (TREE_CODE (*pred_p
) == SSA_NAME
)
1152 val
= vrp_evaluate_conditional (EQ_EXPR
,
1157 val
= vrp_evaluate_conditional (TREE_CODE (*pred_p
),
1158 TREE_OPERAND (*pred_p
, 0),
1159 TREE_OPERAND (*pred_p
, 1),
1165 val
= fold_convert (TREE_TYPE (*pred_p
), val
);
1169 fprintf (dump_file
, "Folding predicate ");
1170 print_generic_expr (dump_file
, *pred_p
, 0);
1171 fprintf (dump_file
, " to ");
1172 print_generic_expr (dump_file
, val
, 0);
1173 fprintf (dump_file
, "\n");
1176 prop_stats
.num_pred_folded
++;
1185 /* Perform final substitution and folding of propagated values.
1187 PROP_VALUE[I] contains the single value that should be substituted
1188 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1191 If USE_RANGES_P is true, statements that contain predicate
1192 expressions are evaluated with a call to vrp_evaluate_conditional.
1193 This will only give meaningful results when called from tree-vrp.c
1194 (the information used by vrp_evaluate_conditional is built by the
1197 Return TRUE when something changed. */
1200 substitute_and_fold (prop_value_t
*prop_value
, bool use_ranges_p
)
1203 bool something_changed
= false;
1205 if (prop_value
== NULL
&& !use_ranges_p
)
1208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1209 fprintf (dump_file
, "\nSubstituing values and folding statements\n\n");
1211 memset (&prop_stats
, 0, sizeof (prop_stats
));
1213 /* Substitute values in every statement of every basic block. */
1216 block_stmt_iterator i
;
1219 /* Propagate known values into PHI nodes. */
1221 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1222 replace_phi_args_in (phi
, prop_value
);
1224 /* Propagate known values into stmts. Do a backward walk to expose
1225 more trivially deletable stmts. */
1226 for (i
= bsi_last (bb
); !bsi_end_p (i
);)
1228 bool replaced_address
, did_replace
;
1229 tree call
, prev_stmt
= NULL
;
1230 tree stmt
= bsi_stmt (i
);
1232 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1233 range information for names and they are discarded
1235 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1236 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
1242 /* No point propagating into a stmt whose result is not used,
1243 but instead we might be able to remove a trivially dead stmt. */
1244 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1245 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 0)) == SSA_NAME
1246 && !stmt_ann (stmt
)->has_volatile_ops
1247 && has_zero_uses (GIMPLE_STMT_OPERAND (stmt
, 0))
1248 && !tree_could_throw_p (stmt
)
1249 && (!(call
= get_call_expr_in (stmt
))
1250 || !TREE_SIDE_EFFECTS (call
)))
1252 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1254 fprintf (dump_file
, "Removing dead stmt ");
1255 print_generic_expr (dump_file
, stmt
, 0);
1256 fprintf (dump_file
, "\n");
1258 bsi_remove (&i
, true);
1259 release_defs (stmt
);
1265 /* Record the state of the statement before replacements. */
1266 push_stmt_changes (bsi_stmt_ptr (i
));
1268 /* Replace the statement with its folded version and mark it
1270 did_replace
= false;
1271 replaced_address
= false;
1272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1273 prev_stmt
= unshare_expr (stmt
);
1275 /* If we have range information, see if we can fold
1276 predicate expressions. */
1278 did_replace
= fold_predicate_in (stmt
);
1282 /* Only replace real uses if we couldn't fold the
1283 statement using value range information (value range
1284 information is not collected on virtuals, so we only
1285 need to check this for real uses). */
1287 did_replace
|= replace_uses_in (stmt
, &replaced_address
,
1290 did_replace
|= replace_vuses_in (stmt
, &replaced_address
,
1294 /* If we made a replacement, fold and cleanup the statement. */
1297 tree old_stmt
= stmt
;
1300 fold_stmt (bsi_stmt_ptr (i
));
1301 stmt
= bsi_stmt (i
);
1303 /* If we cleaned up EH information from the statement,
1305 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1306 tree_purge_dead_eh_edges (bb
);
1308 rhs
= get_rhs (stmt
);
1309 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1310 recompute_tree_invariant_for_addr_expr (rhs
);
1312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1314 fprintf (dump_file
, "Folded statement: ");
1315 print_generic_stmt (dump_file
, prev_stmt
, TDF_SLIM
);
1316 fprintf (dump_file
, " into: ");
1317 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1318 fprintf (dump_file
, "\n");
1321 /* Determine what needs to be done to update the SSA form. */
1322 pop_stmt_changes (bsi_stmt_ptr (i
));
1323 something_changed
= true;
1327 /* The statement was not modified, discard the change buffer. */
1328 discard_stmt_changes (bsi_stmt_ptr (i
));
1331 /* Some statements may be simplified using ranges. For
1332 example, division may be replaced by shifts, modulo
1333 replaced with bitwise and, etc. Do this after
1334 substituting constants, folding, etc so that we're
1335 presented with a fully propagated, canonicalized
1338 simplify_stmt_using_ranges (stmt
);
1344 if (dump_file
&& (dump_flags
& TDF_STATS
))
1346 fprintf (dump_file
, "Constants propagated: %6ld\n",
1347 prop_stats
.num_const_prop
);
1348 fprintf (dump_file
, "Copies propagated: %6ld\n",
1349 prop_stats
.num_copy_prop
);
1350 fprintf (dump_file
, "Predicates folded: %6ld\n",
1351 prop_stats
.num_pred_folded
);
1353 return something_changed
;
1356 #include "gt-tree-ssa-propagate.h"