1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005 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, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
31 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-flow.h"
40 #include "tree-pass.h"
41 #include "tree-ssa-propagate.h"
42 #include "langhooks.h"
46 /* This file implements a generic value propagation engine based on
47 the same propagation used by the SSA-CCP algorithm [1].
49 Propagation is performed by simulating the execution of every
50 statement that produces the value being propagated. Simulation
53 1- Initially, all edges of the CFG are marked not executable and
54 the CFG worklist is seeded with all the statements in the entry
55 basic block (block 0).
57 2- Every statement S is simulated with a call to the call-back
58 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
61 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
62 interest and does not affect any of the work lists.
64 SSA_PROP_VARYING: The value produced by S cannot be determined
65 at compile time. Further simulation of S is not required.
66 If S is a conditional jump, all the outgoing edges for the
67 block are considered executable and added to the work
70 SSA_PROP_INTERESTING: S produces a value that can be computed
71 at compile time. Its result can be propagated into the
72 statements that feed from S. Furthermore, if S is a
73 conditional jump, only the edge known to be taken is added
74 to the work list. Edges that are known not to execute are
77 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
78 return value from SSA_PROP_VISIT_PHI has the same semantics as
81 4- Three work lists are kept. Statements are only added to these
82 lists if they produce one of SSA_PROP_INTERESTING or
85 CFG_BLOCKS contains the list of blocks to be simulated.
86 Blocks are added to this list if their incoming edges are
89 VARYING_SSA_EDGES contains the list of statements that feed
90 from statements that produce an SSA_PROP_VARYING result.
91 These are simulated first to speed up processing.
93 INTERESTING_SSA_EDGES contains the list of statements that
94 feed from statements that produce an SSA_PROP_INTERESTING
97 5- Simulation terminates when all three work lists are drained.
99 Before calling ssa_propagate, it is important to clear
100 DONT_SIMULATE_AGAIN for all the statements in the program that
101 should be simulated. This initialization allows an implementation
102 to specify which statements should never be simulated.
104 It is also important to compute def-use information before calling
109 [1] Constant propagation with conditional branches,
110 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
112 [2] Building an Optimizing Compiler,
113 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
115 [3] Advanced Compiler Design and Implementation,
116 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
118 /* Function pointers used to parameterize the propagation engine. */
119 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
120 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
122 /* Use the TREE_DEPRECATED bitflag to mark statements that have been
123 added to one of the SSA edges worklists. This flag is used to
124 avoid visiting statements unnecessarily when draining an SSA edge
125 worklist. If while simulating a basic block, we find a statement with
126 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
127 processing from visiting it again. */
128 #define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
130 /* A bitmap to keep track of executable blocks in the CFG. */
131 static sbitmap executable_blocks
;
133 /* Array of control flow edges on the worklist. */
134 static GTY(()) varray_type cfg_blocks
= NULL
;
136 static unsigned int cfg_blocks_num
= 0;
137 static int cfg_blocks_tail
;
138 static int cfg_blocks_head
;
140 static sbitmap bb_in_list
;
142 /* Worklist of SSA edges which will need reexamination as their
143 definition has changed. SSA edges are def-use edges in the SSA
144 web. For each D-U edge, we store the target statement or PHI node
146 static GTY(()) VEC(tree
,gc
) *interesting_ssa_edges
;
148 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
149 list of SSA edges is split into two. One contains all SSA edges
150 who need to be reexamined because their lattice value changed to
151 varying (this worklist), and the other contains all other SSA edges
152 to be reexamined (INTERESTING_SSA_EDGES).
154 Since most values in the program are VARYING, the ideal situation
155 is to move them to that lattice value as quickly as possible.
156 Thus, it doesn't make sense to process any other type of lattice
157 value until all VARYING values are propagated fully, which is one
158 thing using the VARYING worklist achieves. In addition, if we
159 don't use a separate worklist for VARYING edges, we end up with
160 situations where lattice values move from
161 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
162 static GTY(()) VEC(tree
,gc
) *varying_ssa_edges
;
165 /* Return true if the block worklist empty. */
168 cfg_blocks_empty_p (void)
170 return (cfg_blocks_num
== 0);
174 /* Add a basic block to the worklist. The block must not be already
175 in the worklist, and it must not be the ENTRY or EXIT block. */
178 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
> VARRAY_SIZE (cfg_blocks
))
193 /* We have to grow the array now. Adjust to queue to occupy the
194 full space of the original array. */
195 cfg_blocks_tail
= VARRAY_SIZE (cfg_blocks
);
197 VARRAY_GROW (cfg_blocks
, 2 * VARRAY_SIZE (cfg_blocks
));
200 cfg_blocks_tail
= (cfg_blocks_tail
+ 1) % VARRAY_SIZE (cfg_blocks
);
203 VARRAY_BB (cfg_blocks
, cfg_blocks_tail
) = bb
;
204 SET_BIT (bb_in_list
, bb
->index
);
208 /* Remove a block from the worklist. */
211 cfg_blocks_get (void)
215 bb
= VARRAY_BB (cfg_blocks
, cfg_blocks_head
);
217 gcc_assert (!cfg_blocks_empty_p ());
220 cfg_blocks_head
= (cfg_blocks_head
+ 1) % VARRAY_SIZE (cfg_blocks
);
222 RESET_BIT (bb_in_list
, bb
->index
);
228 /* We have just defined a new value for VAR. If IS_VARYING is true,
229 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
230 them to INTERESTING_SSA_EDGES. */
233 add_ssa_edge (tree var
, bool is_varying
)
235 imm_use_iterator iter
;
238 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
240 tree use_stmt
= USE_STMT (use_p
);
242 if (!DONT_SIMULATE_AGAIN (use_stmt
)
243 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt
))
245 STMT_IN_SSA_EDGE_WORKLIST (use_stmt
) = 1;
247 VEC_safe_push (tree
, gc
, varying_ssa_edges
, use_stmt
);
249 VEC_safe_push (tree
, gc
, interesting_ssa_edges
, use_stmt
);
255 /* Add edge E to the control flow worklist. */
258 add_control_edge (edge e
)
260 basic_block bb
= e
->dest
;
261 if (bb
== EXIT_BLOCK_PTR
)
264 /* If the edge had already been executed, skip it. */
265 if (e
->flags
& EDGE_EXECUTABLE
)
268 e
->flags
|= EDGE_EXECUTABLE
;
270 /* If the block is already in the list, we're done. */
271 if (TEST_BIT (bb_in_list
, bb
->index
))
276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
277 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
278 e
->src
->index
, e
->dest
->index
);
282 /* Simulate the execution of STMT and update the work lists accordingly. */
285 simulate_stmt (tree stmt
)
287 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
288 edge taken_edge
= NULL
;
289 tree output_name
= NULL_TREE
;
291 /* Don't bother visiting statements that are already
292 considered varying by the propagator. */
293 if (DONT_SIMULATE_AGAIN (stmt
))
296 if (TREE_CODE (stmt
) == PHI_NODE
)
298 val
= ssa_prop_visit_phi (stmt
);
299 output_name
= PHI_RESULT (stmt
);
302 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
304 if (val
== SSA_PROP_VARYING
)
306 DONT_SIMULATE_AGAIN (stmt
) = 1;
308 /* If the statement produced a new varying value, add the SSA
309 edges coming out of OUTPUT_NAME. */
311 add_ssa_edge (output_name
, true);
313 /* If STMT transfers control out of its basic block, add
314 all outgoing edges to the work list. */
315 if (stmt_ends_bb_p (stmt
))
319 basic_block bb
= bb_for_stmt (stmt
);
320 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
321 add_control_edge (e
);
324 else if (val
== SSA_PROP_INTERESTING
)
326 /* If the statement produced new value, add the SSA edges coming
327 out of OUTPUT_NAME. */
329 add_ssa_edge (output_name
, false);
331 /* If we know which edge is going to be taken out of this block,
332 add it to the CFG work list. */
334 add_control_edge (taken_edge
);
338 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
339 drain. This pops statements off the given WORKLIST and processes
340 them until there are no more statements on WORKLIST.
341 We take a pointer to WORKLIST because it may be reallocated when an
342 SSA edge is added to it in simulate_stmt. */
345 process_ssa_edge_worklist (VEC(tree
,gc
) **worklist
)
347 /* Drain the entire worklist. */
348 while (VEC_length (tree
, *worklist
) > 0)
352 /* Pull the statement to simulate off the worklist. */
353 tree stmt
= VEC_pop (tree
, *worklist
);
355 /* If this statement was already visited by simulate_block, then
356 we don't need to visit it again here. */
357 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt
))
360 /* STMT is no longer in a worklist. */
361 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
365 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
366 print_generic_stmt (dump_file
, stmt
, dump_flags
);
369 bb
= bb_for_stmt (stmt
);
371 /* PHI nodes are always visited, regardless of whether or not
372 the destination block is executable. Otherwise, visit the
373 statement only if its block is marked executable. */
374 if (TREE_CODE (stmt
) == PHI_NODE
375 || TEST_BIT (executable_blocks
, bb
->index
))
376 simulate_stmt (stmt
);
381 /* Simulate the execution of BLOCK. Evaluate the statement associated
382 with each variable reference inside the block. */
385 simulate_block (basic_block block
)
389 /* There is nothing to do for the exit block. */
390 if (block
== EXIT_BLOCK_PTR
)
393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
394 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
396 /* Always simulate PHI nodes, even if we have simulated this block
398 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
401 /* If this is the first time we've simulated this block, then we
402 must simulate each of its statements. */
403 if (!TEST_BIT (executable_blocks
, block
->index
))
405 block_stmt_iterator j
;
406 unsigned int normal_edge_count
;
410 /* Note that we have simulated this block. */
411 SET_BIT (executable_blocks
, block
->index
);
413 for (j
= bsi_start (block
); !bsi_end_p (j
); bsi_next (&j
))
415 tree stmt
= bsi_stmt (j
);
417 /* If this statement is already in the worklist then
418 "cancel" it. The reevaluation implied by the worklist
419 entry will produce the same value we generate here and
420 thus reevaluating it again from the worklist is
422 if (STMT_IN_SSA_EDGE_WORKLIST (stmt
))
423 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
425 simulate_stmt (stmt
);
428 /* We can not predict when abnormal edges will be executed, so
429 once a block is considered executable, we consider any
430 outgoing abnormal edges as executable.
432 At the same time, if this block has only one successor that is
433 reached by non-abnormal edges, then add that successor to the
435 normal_edge_count
= 0;
437 FOR_EACH_EDGE (e
, ei
, block
->succs
)
439 if (e
->flags
& EDGE_ABNORMAL
)
440 add_control_edge (e
);
448 if (normal_edge_count
== 1)
449 add_control_edge (normal_edge
);
454 /* Initialize local data structures and work lists. */
464 /* Worklists of SSA edges. */
465 interesting_ssa_edges
= VEC_alloc (tree
, gc
, 20);
466 varying_ssa_edges
= VEC_alloc (tree
, gc
, 20);
468 executable_blocks
= sbitmap_alloc (last_basic_block
);
469 sbitmap_zero (executable_blocks
);
471 bb_in_list
= sbitmap_alloc (last_basic_block
);
472 sbitmap_zero (bb_in_list
);
474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
475 dump_immediate_uses (dump_file
);
477 VARRAY_BB_INIT (cfg_blocks
, 20, "cfg_blocks");
479 /* Initialize the values for every SSA_NAME. */
480 for (i
= 1; i
< num_ssa_names
; i
++)
482 SSA_NAME_VALUE (ssa_name (i
)) = NULL_TREE
;
484 /* Initially assume that every edge in the CFG is not executable.
485 (including the edges coming out of ENTRY_BLOCK_PTR). */
488 block_stmt_iterator si
;
490 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
491 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si
)) = 0;
493 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
494 e
->flags
&= ~EDGE_EXECUTABLE
;
497 /* Seed the algorithm by adding the successors of the entry block to the
499 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
500 add_control_edge (e
);
504 /* Free allocated storage. */
509 VEC_free (tree
, gc
, interesting_ssa_edges
);
510 VEC_free (tree
, gc
, varying_ssa_edges
);
512 sbitmap_free (bb_in_list
);
513 sbitmap_free (executable_blocks
);
517 /* Get the main expression from statement STMT. */
522 enum tree_code code
= TREE_CODE (stmt
);
527 stmt
= TREE_OPERAND (stmt
, 0);
528 if (!stmt
|| TREE_CODE (stmt
) != MODIFY_EXPR
)
533 stmt
= TREE_OPERAND (stmt
, 1);
534 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
535 return TREE_OPERAND (stmt
, 0);
540 return COND_EXPR_COND (stmt
);
542 return SWITCH_COND (stmt
);
544 return GOTO_DESTINATION (stmt
);
546 return LABEL_EXPR_LABEL (stmt
);
554 /* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
555 GIMPLE expression no changes are done and the function returns
559 set_rhs (tree
*stmt_p
, tree expr
)
561 tree stmt
= *stmt_p
, op
;
562 enum tree_code code
= TREE_CODE (expr
);
567 /* Verify the constant folded result is valid gimple. */
568 if (TREE_CODE_CLASS (code
) == tcc_binary
)
570 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
571 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
574 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
576 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
579 else if (code
== ADDR_EXPR
)
581 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == ARRAY_REF
582 && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr
, 0), 1)))
585 else if (code
== COMPOUND_EXPR
)
588 switch (TREE_CODE (stmt
))
591 op
= TREE_OPERAND (stmt
, 0);
592 if (TREE_CODE (op
) != MODIFY_EXPR
)
594 TREE_OPERAND (stmt
, 0) = expr
;
601 op
= TREE_OPERAND (stmt
, 1);
602 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
604 TREE_OPERAND (stmt
, 1) = expr
;
608 COND_EXPR_COND (stmt
) = expr
;
611 SWITCH_COND (stmt
) = expr
;
614 GOTO_DESTINATION (stmt
) = expr
;
617 LABEL_EXPR_LABEL (stmt
) = expr
;
621 /* Replace the whole statement with EXPR. If EXPR has no side
622 effects, then replace *STMT_P with an empty statement. */
623 ann
= stmt_ann (stmt
);
624 *stmt_p
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
625 (*stmt_p
)->common
.ann
= (tree_ann_t
) ann
;
627 if (TREE_SIDE_EFFECTS (expr
))
629 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
631 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_DEFS
)
633 if (TREE_CODE (var
) == SSA_NAME
)
634 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
644 /* Entry point to the propagation engine.
646 VISIT_STMT is called for every statement visited.
647 VISIT_PHI is called for every PHI node visited. */
650 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
651 ssa_prop_visit_phi_fn visit_phi
)
653 ssa_prop_visit_stmt
= visit_stmt
;
654 ssa_prop_visit_phi
= visit_phi
;
658 /* Iterate until the worklists are empty. */
659 while (!cfg_blocks_empty_p ()
660 || VEC_length (tree
, interesting_ssa_edges
) > 0
661 || VEC_length (tree
, varying_ssa_edges
) > 0)
663 if (!cfg_blocks_empty_p ())
665 /* Pull the next block to simulate off the worklist. */
666 basic_block dest_block
= cfg_blocks_get ();
667 simulate_block (dest_block
);
670 /* In order to move things to varying as quickly as
671 possible,process the VARYING_SSA_EDGES worklist first. */
672 process_ssa_edge_worklist (&varying_ssa_edges
);
674 /* Now process the INTERESTING_SSA_EDGES worklist. */
675 process_ssa_edge_worklist (&interesting_ssa_edges
);
682 /* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */
685 first_vdef (tree stmt
)
690 /* Simply return the first operand we arrive at. */
691 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
698 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
699 is a non-volatile pointer dereference, a structure reference or a
700 reference to a single _DECL. Ignore volatile memory references
701 because they are not interesting for the optimizers. */
704 stmt_makes_single_load (tree stmt
)
708 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
711 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VUSE
))
714 rhs
= TREE_OPERAND (stmt
, 1);
717 return (!TREE_THIS_VOLATILE (rhs
)
719 || REFERENCE_CLASS_P (rhs
)));
723 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
724 is a non-volatile pointer dereference, a structure reference or a
725 reference to a single _DECL. Ignore volatile memory references
726 because they are not interesting for the optimizers. */
729 stmt_makes_single_store (tree stmt
)
733 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
736 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
|SSA_OP_VMUSTDEF
))
739 lhs
= TREE_OPERAND (stmt
, 0);
742 return (!TREE_THIS_VOLATILE (lhs
)
744 || REFERENCE_CLASS_P (lhs
)));
748 /* If STMT makes a single memory load and all the virtual use operands
749 have the same value in array VALUES, return it. Otherwise, return
753 get_value_loaded_by (tree stmt
, prop_value_t
*values
)
757 prop_value_t
*prev_val
= NULL
;
758 prop_value_t
*val
= NULL
;
760 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, i
, SSA_OP_VIRTUAL_USES
)
762 val
= &values
[SSA_NAME_VERSION (vuse
)];
763 if (prev_val
&& prev_val
->value
!= val
->value
)
772 /* Propagation statistics. */
779 static struct prop_stats_d prop_stats
;
781 /* Replace USE references in statement STMT with the values stored in
782 PROP_VALUE. Return true if at least one reference was replaced. If
783 REPLACED_ADDRESSES_P is given, it will be set to true if an address
784 constant was replaced. */
787 replace_uses_in (tree stmt
, bool *replaced_addresses_p
,
788 prop_value_t
*prop_value
)
790 bool replaced
= false;
794 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
796 tree tuse
= USE_FROM_PTR (use
);
797 tree val
= prop_value
[SSA_NAME_VERSION (tuse
)].value
;
799 if (val
== tuse
|| val
== NULL_TREE
)
802 if (TREE_CODE (stmt
) == ASM_EXPR
803 && !may_propagate_copy_into_asm (tuse
))
806 if (!may_propagate_copy (tuse
, val
))
809 if (TREE_CODE (val
) != SSA_NAME
)
810 prop_stats
.num_const_prop
++;
812 prop_stats
.num_copy_prop
++;
814 propagate_value (use
, val
);
817 if (POINTER_TYPE_P (TREE_TYPE (tuse
)) && replaced_addresses_p
)
818 *replaced_addresses_p
= true;
825 /* Replace the VUSE references in statement STMT with the values
826 stored in PROP_VALUE. Return true if a reference was replaced. If
827 REPLACED_ADDRESSES_P is given, it will be set to true if an address
828 constant was replaced.
830 Replacing VUSE operands is slightly more complex than replacing
831 regular USEs. We are only interested in two types of replacements
834 1- If the value to be replaced is a constant or an SSA name for a
835 GIMPLE register, then we are making a copy/constant propagation
836 from a memory store. For instance,
838 # a_3 = V_MAY_DEF <a_2>
844 This replacement is only possible iff STMT is an assignment
845 whose RHS is identical to the LHS of the statement that created
846 the VUSE(s) that we are replacing. Otherwise, we may do the
849 # a_3 = V_MAY_DEF <a_2>
850 # b_5 = V_MAY_DEF <b_4>
856 Even though 'b_5' acquires the value '10' during propagation,
857 there is no way for the propagator to tell whether the
858 replacement is correct in every reached use, because values are
859 computed at definition sites. Therefore, when doing final
860 substitution of propagated values, we have to check each use
861 site. Since the RHS of STMT ('b') is different from the LHS of
862 the originating statement ('*p'), we cannot replace 'b' with
865 Similarly, when merging values from PHI node arguments,
866 propagators need to take care not to merge the same values
867 stored in different locations:
870 # a_3 = V_MAY_DEF <a_2>
873 # a_4 = V_MAY_DEF <a_2>
875 # a_5 = PHI <a_3, a_4>
877 It would be wrong to propagate '3' into 'a_5' because that
878 operation merges two stores to different memory locations.
881 2- If the value to be replaced is an SSA name for a virtual
882 register, then we simply replace each VUSE operand with its
883 value from PROP_VALUE. This is the same replacement done by
887 replace_vuses_in (tree stmt
, bool *replaced_addresses_p
,
888 prop_value_t
*prop_value
)
890 bool replaced
= false;
894 if (stmt_makes_single_load (stmt
))
896 /* If STMT is an assignment whose RHS is a single memory load,
897 see if we are trying to propagate a constant or a GIMPLE
898 register (case #1 above). */
899 prop_value_t
*val
= get_value_loaded_by (stmt
, prop_value
);
900 tree rhs
= TREE_OPERAND (stmt
, 1);
904 && (is_gimple_reg (val
->value
)
905 || is_gimple_min_invariant (val
->value
))
906 && simple_cst_equal (rhs
, val
->mem_ref
) == 1)
909 /* If we are replacing a constant address, inform our
911 if (TREE_CODE (val
->value
) != SSA_NAME
912 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt
, 1)))
913 && replaced_addresses_p
)
914 *replaced_addresses_p
= true;
916 /* We can only perform the substitution if the load is done
917 from the same memory location as the original store.
918 Since we already know that there are no intervening
919 stores between DEF_STMT and STMT, we only need to check
920 that the RHS of STMT is the same as the memory reference
921 propagated together with the value. */
922 TREE_OPERAND (stmt
, 1) = val
->value
;
924 if (TREE_CODE (val
->value
) != SSA_NAME
)
925 prop_stats
.num_const_prop
++;
927 prop_stats
.num_copy_prop
++;
929 /* Since we have replaced the whole RHS of STMT, there
930 is no point in checking the other VUSEs, as they will
931 all have the same value. */
936 /* Otherwise, the values for every VUSE operand must be other
937 SSA_NAMEs that can be propagated into STMT. */
938 FOR_EACH_SSA_USE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
940 tree var
= USE_FROM_PTR (vuse
);
941 tree val
= prop_value
[SSA_NAME_VERSION (var
)].value
;
943 if (val
== NULL_TREE
|| var
== val
)
946 /* Constants and copies propagated between real and virtual
947 operands are only possible in the cases handled above. They
948 should be ignored in any other context. */
949 if (is_gimple_min_invariant (val
) || is_gimple_reg (val
))
952 propagate_value (vuse
, val
);
953 prop_stats
.num_copy_prop
++;
961 /* Replace propagated values into all the arguments for PHI using the
962 values from PROP_VALUE. */
965 replace_phi_args_in (tree phi
, prop_value_t
*prop_value
)
969 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
971 tree arg
= PHI_ARG_DEF (phi
, i
);
973 if (TREE_CODE (arg
) == SSA_NAME
)
975 tree val
= prop_value
[SSA_NAME_VERSION (arg
)].value
;
977 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
979 if (TREE_CODE (val
) != SSA_NAME
)
980 prop_stats
.num_const_prop
++;
982 prop_stats
.num_copy_prop
++;
984 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
986 /* If we propagated a copy and this argument flows
987 through an abnormal edge, update the replacement
989 if (TREE_CODE (val
) == SSA_NAME
990 && PHI_ARG_EDGE (phi
, i
)->flags
& EDGE_ABNORMAL
)
991 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
998 /* Perform final substitution and folding of propagated values. */
1001 substitute_and_fold (prop_value_t
*prop_value
)
1005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1007 "\nSubstituing values and folding statements\n\n");
1009 memset (&prop_stats
, 0, sizeof (prop_stats
));
1011 /* Substitute values in every statement of every basic block. */
1014 block_stmt_iterator i
;
1017 /* Propagate our known values into PHI nodes. */
1018 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1022 fprintf (dump_file
, "Replaced ");
1023 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1026 replace_phi_args_in (phi
, prop_value
);
1028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, " with ");
1031 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
1032 fprintf (dump_file
, "\n");
1036 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
1038 bool replaced_address
, did_replace
;
1039 tree stmt
= bsi_stmt (i
);
1041 /* Replace the statement with its folded version and mark it
1043 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1045 fprintf (dump_file
, "Replaced ");
1046 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1049 replaced_address
= false;
1050 did_replace
= replace_uses_in (stmt
, &replaced_address
, prop_value
);
1051 did_replace
|= replace_vuses_in (stmt
, &replaced_address
, prop_value
);
1054 fold_stmt (bsi_stmt_ptr (i
));
1057 /* If we folded a builtin function, we'll likely
1058 need to rename VDEFs. */
1059 mark_new_vars_to_rename (stmt
);
1061 /* If we cleaned up EH information from the statement,
1063 if (maybe_clean_eh_stmt (stmt
))
1064 tree_purge_dead_eh_edges (bb
);
1067 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1069 fprintf (dump_file
, " with ");
1070 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1071 fprintf (dump_file
, "\n");
1076 if (dump_file
&& (dump_flags
& TDF_STATS
))
1078 fprintf (dump_file
, "Constants propagated: %6ld\n",
1079 prop_stats
.num_const_prop
);
1080 fprintf (dump_file
, "Copies propagated: %6ld\n",
1081 prop_stats
.num_copy_prop
);
1084 #include "gt-tree-ssa-propagate.h"