1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
33 #include "tree-flow.h"
34 #include "tree-ssa-propagate.h"
35 #include "langhooks.h"
37 #include "value-prof.h"
40 /* This file implements a generic value propagation engine based on
41 the same propagation used by the SSA-CCP algorithm [1].
43 Propagation is performed by simulating the execution of every
44 statement that produces the value being propagated. Simulation
47 1- Initially, all edges of the CFG are marked not executable and
48 the CFG worklist is seeded with all the statements in the entry
49 basic block (block 0).
51 2- Every statement S is simulated with a call to the call-back
52 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
55 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
56 interest and does not affect any of the work lists.
58 SSA_PROP_VARYING: The value produced by S cannot be determined
59 at compile time. Further simulation of S is not required.
60 If S is a conditional jump, all the outgoing edges for the
61 block are considered executable and added to the work
64 SSA_PROP_INTERESTING: S produces a value that can be computed
65 at compile time. Its result can be propagated into the
66 statements that feed from S. Furthermore, if S is a
67 conditional jump, only the edge known to be taken is added
68 to the work list. Edges that are known not to execute are
71 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
72 return value from SSA_PROP_VISIT_PHI has the same semantics as
75 4- Three work lists are kept. Statements are only added to these
76 lists if they produce one of SSA_PROP_INTERESTING or
79 CFG_BLOCKS contains the list of blocks to be simulated.
80 Blocks are added to this list if their incoming edges are
83 VARYING_SSA_EDGES contains the list of statements that feed
84 from statements that produce an SSA_PROP_VARYING result.
85 These are simulated first to speed up processing.
87 INTERESTING_SSA_EDGES contains the list of statements that
88 feed from statements that produce an SSA_PROP_INTERESTING
91 5- Simulation terminates when all three work lists are drained.
93 Before calling ssa_propagate, it is important to clear
94 prop_simulate_again_p for all the statements in the program that
95 should be simulated. This initialization allows an implementation
96 to specify which statements should never be simulated.
98 It is also important to compute def-use information before calling
103 [1] Constant propagation with conditional branches,
104 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
106 [2] Building an Optimizing Compiler,
107 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
109 [3] Advanced Compiler Design and Implementation,
110 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
112 /* Function pointers used to parameterize the propagation engine. */
113 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
114 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
116 /* Keep track of statements that have been added to one of the SSA
117 edges worklists. This flag is used to avoid visiting statements
118 unnecessarily when draining an SSA edge worklist. If while
119 simulating a basic block, we find a statement with
120 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
121 processing from visiting it again.
123 NOTE: users of the propagation engine are not allowed to use
124 the GF_PLF_1 flag. */
125 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
127 /* A bitmap to keep track of executable blocks in the CFG. */
128 static sbitmap executable_blocks
;
130 /* Array of control flow edges on the worklist. */
131 static vec
<basic_block
> cfg_blocks
;
133 static unsigned int cfg_blocks_num
= 0;
134 static int cfg_blocks_tail
;
135 static int cfg_blocks_head
;
137 static sbitmap bb_in_list
;
139 /* Worklist of SSA edges which will need reexamination as their
140 definition has changed. SSA edges are def-use edges in the SSA
141 web. For each D-U edge, we store the target statement or PHI node
143 static GTY(()) vec
<gimple
, va_gc
> *interesting_ssa_edges
;
145 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
146 list of SSA edges is split into two. One contains all SSA edges
147 who need to be reexamined because their lattice value changed to
148 varying (this worklist), and the other contains all other SSA edges
149 to be reexamined (INTERESTING_SSA_EDGES).
151 Since most values in the program are VARYING, the ideal situation
152 is to move them to that lattice value as quickly as possible.
153 Thus, it doesn't make sense to process any other type of lattice
154 value until all VARYING values are propagated fully, which is one
155 thing using the VARYING worklist achieves. In addition, if we
156 don't use a separate worklist for VARYING edges, we end up with
157 situations where lattice values move from
158 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
159 static GTY(()) vec
<gimple
, va_gc
> *varying_ssa_edges
;
162 /* Return true if the block worklist empty. */
165 cfg_blocks_empty_p (void)
167 return (cfg_blocks_num
== 0);
171 /* Add a basic block to the worklist. The block must not be already
172 in the worklist, and it must not be the ENTRY or EXIT block. */
175 cfg_blocks_add (basic_block bb
)
179 gcc_assert (bb
!= ENTRY_BLOCK_PTR
&& bb
!= EXIT_BLOCK_PTR
);
180 gcc_assert (!bitmap_bit_p (bb_in_list
, bb
->index
));
182 if (cfg_blocks_empty_p ())
184 cfg_blocks_tail
= cfg_blocks_head
= 0;
190 if (cfg_blocks_num
> cfg_blocks
.length ())
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
= cfg_blocks
.length ();
199 cfg_blocks
.safe_grow (2 * cfg_blocks_tail
);
201 /* Minor optimization: we prefer to see blocks with more
202 predecessors later, because there is more of a chance that
203 the incoming edges will be executable. */
204 else if (EDGE_COUNT (bb
->preds
)
205 >= EDGE_COUNT (cfg_blocks
[cfg_blocks_head
]->preds
))
206 cfg_blocks_tail
= ((cfg_blocks_tail
+ 1) % cfg_blocks
.length ());
209 if (cfg_blocks_head
== 0)
210 cfg_blocks_head
= cfg_blocks
.length ();
216 cfg_blocks
[head
? cfg_blocks_head
: cfg_blocks_tail
] = bb
;
217 bitmap_set_bit (bb_in_list
, bb
->index
);
221 /* Remove a block from the worklist. */
224 cfg_blocks_get (void)
228 bb
= cfg_blocks
[cfg_blocks_head
];
230 gcc_assert (!cfg_blocks_empty_p ());
233 cfg_blocks_head
= ((cfg_blocks_head
+ 1) % cfg_blocks
.length ());
235 bitmap_clear_bit (bb_in_list
, bb
->index
);
241 /* We have just defined a new value for VAR. If IS_VARYING is true,
242 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
243 them to INTERESTING_SSA_EDGES. */
246 add_ssa_edge (tree var
, bool is_varying
)
248 imm_use_iterator iter
;
251 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
253 gimple use_stmt
= USE_STMT (use_p
);
255 if (prop_simulate_again_p (use_stmt
)
256 && !gimple_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
258 gimple_set_plf (use_stmt
, STMT_IN_SSA_EDGE_WORKLIST
, true);
260 vec_safe_push (varying_ssa_edges
, use_stmt
);
262 vec_safe_push (interesting_ssa_edges
, use_stmt
);
268 /* Add edge E to the control flow worklist. */
271 add_control_edge (edge e
)
273 basic_block bb
= e
->dest
;
274 if (bb
== EXIT_BLOCK_PTR
)
277 /* If the edge had already been executed, skip it. */
278 if (e
->flags
& EDGE_EXECUTABLE
)
281 e
->flags
|= EDGE_EXECUTABLE
;
283 /* If the block is already in the list, we're done. */
284 if (bitmap_bit_p (bb_in_list
, bb
->index
))
289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
290 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
291 e
->src
->index
, e
->dest
->index
);
295 /* Simulate the execution of STMT and update the work lists accordingly. */
298 simulate_stmt (gimple stmt
)
300 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
301 edge taken_edge
= NULL
;
302 tree output_name
= NULL_TREE
;
304 /* Don't bother visiting statements that are already
305 considered varying by the propagator. */
306 if (!prop_simulate_again_p (stmt
))
309 if (gimple_code (stmt
) == GIMPLE_PHI
)
311 val
= ssa_prop_visit_phi (stmt
);
312 output_name
= gimple_phi_result (stmt
);
315 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
317 if (val
== SSA_PROP_VARYING
)
319 prop_set_simulate_again (stmt
, false);
321 /* If the statement produced a new varying value, add the SSA
322 edges coming out of OUTPUT_NAME. */
324 add_ssa_edge (output_name
, true);
326 /* If STMT transfers control out of its basic block, add
327 all outgoing edges to the work list. */
328 if (stmt_ends_bb_p (stmt
))
332 basic_block bb
= gimple_bb (stmt
);
333 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
334 add_control_edge (e
);
337 else if (val
== SSA_PROP_INTERESTING
)
339 /* If the statement produced new value, add the SSA edges coming
340 out of OUTPUT_NAME. */
342 add_ssa_edge (output_name
, false);
344 /* If we know which edge is going to be taken out of this block,
345 add it to the CFG work list. */
347 add_control_edge (taken_edge
);
351 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
352 drain. This pops statements off the given WORKLIST and processes
353 them until there are no more statements on WORKLIST.
354 We take a pointer to WORKLIST because it may be reallocated when an
355 SSA edge is added to it in simulate_stmt. */
358 process_ssa_edge_worklist (vec
<gimple
, va_gc
> **worklist
)
360 /* Drain the entire worklist. */
361 while ((*worklist
)->length () > 0)
365 /* Pull the statement to simulate off the worklist. */
366 gimple stmt
= (*worklist
)->pop ();
368 /* If this statement was already visited by simulate_block, then
369 we don't need to visit it again here. */
370 if (!gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
373 /* STMT is no longer in a worklist. */
374 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
378 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
379 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
382 bb
= gimple_bb (stmt
);
384 /* PHI nodes are always visited, regardless of whether or not
385 the destination block is executable. Otherwise, visit the
386 statement only if its block is marked executable. */
387 if (gimple_code (stmt
) == GIMPLE_PHI
388 || bitmap_bit_p (executable_blocks
, bb
->index
))
389 simulate_stmt (stmt
);
394 /* Simulate the execution of BLOCK. Evaluate the statement associated
395 with each variable reference inside the block. */
398 simulate_block (basic_block block
)
400 gimple_stmt_iterator gsi
;
402 /* There is nothing to do for the exit block. */
403 if (block
== EXIT_BLOCK_PTR
)
406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
407 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
409 /* Always simulate PHI nodes, even if we have simulated this block
411 for (gsi
= gsi_start_phis (block
); !gsi_end_p (gsi
); gsi_next (&gsi
))
412 simulate_stmt (gsi_stmt (gsi
));
414 /* If this is the first time we've simulated this block, then we
415 must simulate each of its statements. */
416 if (!bitmap_bit_p (executable_blocks
, block
->index
))
418 gimple_stmt_iterator j
;
419 unsigned int normal_edge_count
;
423 /* Note that we have simulated this block. */
424 bitmap_set_bit (executable_blocks
, block
->index
);
426 for (j
= gsi_start_bb (block
); !gsi_end_p (j
); gsi_next (&j
))
428 gimple stmt
= gsi_stmt (j
);
430 /* If this statement is already in the worklist then
431 "cancel" it. The reevaluation implied by the worklist
432 entry will produce the same value we generate here and
433 thus reevaluating it again from the worklist is
435 if (gimple_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
))
436 gimple_set_plf (stmt
, STMT_IN_SSA_EDGE_WORKLIST
, false);
438 simulate_stmt (stmt
);
441 /* We can not predict when abnormal and EH edges will be executed, so
442 once a block is considered executable, we consider any
443 outgoing abnormal edges as executable.
445 TODO: This is not exactly true. Simplifying statement might
446 prove it non-throwing and also computed goto can be handled
447 when destination is known.
449 At the same time, if this block has only one successor that is
450 reached by non-abnormal edges, then add that successor to the
452 normal_edge_count
= 0;
454 FOR_EACH_EDGE (e
, ei
, block
->succs
)
456 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
457 add_control_edge (e
);
465 if (normal_edge_count
== 1)
466 add_control_edge (normal_edge
);
471 /* Initialize local data structures and work lists. */
480 /* Worklists of SSA edges. */
481 vec_alloc (interesting_ssa_edges
, 20);
482 vec_alloc (varying_ssa_edges
, 20);
484 executable_blocks
= sbitmap_alloc (last_basic_block
);
485 bitmap_clear (executable_blocks
);
487 bb_in_list
= sbitmap_alloc (last_basic_block
);
488 bitmap_clear (bb_in_list
);
490 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
491 dump_immediate_uses (dump_file
);
493 cfg_blocks
.create (20);
494 cfg_blocks
.safe_grow_cleared (20);
496 /* Initially assume that every edge in the CFG is not executable.
497 (including the edges coming out of ENTRY_BLOCK_PTR). */
500 gimple_stmt_iterator si
;
502 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
503 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
505 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
506 gimple_set_plf (gsi_stmt (si
), STMT_IN_SSA_EDGE_WORKLIST
, false);
508 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
509 e
->flags
&= ~EDGE_EXECUTABLE
;
512 /* Seed the algorithm by adding the successors of the entry block to the
514 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
515 add_control_edge (e
);
519 /* Free allocated storage. */
524 vec_free (interesting_ssa_edges
);
525 vec_free (varying_ssa_edges
);
526 cfg_blocks
.release ();
527 sbitmap_free (bb_in_list
);
528 sbitmap_free (executable_blocks
);
532 /* Return true if EXPR is an acceptable right-hand-side for a
533 GIMPLE assignment. We validate the entire tree, not just
534 the root node, thus catching expressions that embed complex
535 operands that are not permitted in GIMPLE. This function
536 is needed because the folding routines in fold-const.c
537 may return such expressions in some cases, e.g., an array
538 access with an embedded index addition. It may make more
539 sense to have folding routines that are sensitive to the
540 constraints on GIMPLE operands, rather than abandoning any
541 any attempt to fold if the usual folding turns out to be too
545 valid_gimple_rhs_p (tree expr
)
547 enum tree_code code
= TREE_CODE (expr
);
549 switch (TREE_CODE_CLASS (code
))
551 case tcc_declaration
:
552 if (!is_gimple_variable (expr
))
557 /* All constants are ok. */
562 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
563 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
568 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
578 if (is_gimple_min_invariant (expr
))
580 t
= TREE_OPERAND (expr
, 0);
581 while (handled_component_p (t
))
583 /* ??? More checks needed, see the GIMPLE verifier. */
584 if ((TREE_CODE (t
) == ARRAY_REF
585 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
586 && !is_gimple_val (TREE_OPERAND (t
, 1)))
588 t
= TREE_OPERAND (t
, 0);
590 if (!is_gimple_id (t
))
596 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
598 if (((code
== VEC_COND_EXPR
|| code
== COND_EXPR
)
599 ? !is_gimple_condexpr (TREE_OPERAND (expr
, 0))
600 : !is_gimple_val (TREE_OPERAND (expr
, 0)))
601 || !is_gimple_val (TREE_OPERAND (expr
, 1))
602 || !is_gimple_val (TREE_OPERAND (expr
, 2)))
613 case tcc_exceptional
:
614 if (code
== CONSTRUCTOR
)
618 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (expr
), i
, elt
)
619 if (!is_gimple_val (elt
))
623 if (code
!= SSA_NAME
)
628 if (code
== BIT_FIELD_REF
)
629 return is_gimple_val (TREE_OPERAND (expr
, 0));
640 /* Return true if EXPR is a CALL_EXPR suitable for representation
641 as a single GIMPLE_CALL statement. If the arguments require
642 further gimplification, return false. */
645 valid_gimple_call_p (tree expr
)
649 if (TREE_CODE (expr
) != CALL_EXPR
)
652 nargs
= call_expr_nargs (expr
);
653 for (i
= 0; i
< nargs
; i
++)
655 tree arg
= CALL_EXPR_ARG (expr
, i
);
656 if (is_gimple_reg_type (arg
))
658 if (!is_gimple_val (arg
))
662 if (!is_gimple_lvalue (arg
))
670 /* Make SSA names defined by OLD_STMT point to NEW_STMT
671 as their defining statement. */
674 move_ssa_defining_stmt_for_defs (gimple new_stmt
, gimple old_stmt
)
679 if (gimple_in_ssa_p (cfun
))
681 /* Make defined SSA_NAMEs point to the new
682 statement as their definition. */
683 FOR_EACH_SSA_TREE_OPERAND (var
, old_stmt
, iter
, SSA_OP_ALL_DEFS
)
685 if (TREE_CODE (var
) == SSA_NAME
)
686 SSA_NAME_DEF_STMT (var
) = new_stmt
;
691 /* Helper function for update_gimple_call and update_call_from_tree.
692 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
695 finish_update_gimple_call (gimple_stmt_iterator
*si_p
, gimple new_stmt
,
698 gimple_call_set_lhs (new_stmt
, gimple_call_lhs (stmt
));
699 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
700 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
701 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
702 gimple_set_location (new_stmt
, gimple_location (stmt
));
703 if (gimple_block (new_stmt
) == NULL_TREE
)
704 gimple_set_block (new_stmt
, gimple_block (stmt
));
705 gsi_replace (si_p
, new_stmt
, false);
708 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
709 with number of arguments NARGS, where the arguments in GIMPLE form
710 follow NARGS argument. */
713 update_gimple_call (gimple_stmt_iterator
*si_p
, tree fn
, int nargs
, ...)
716 gimple new_stmt
, stmt
= gsi_stmt (*si_p
);
718 gcc_assert (is_gimple_call (stmt
));
719 va_start (ap
, nargs
);
720 new_stmt
= gimple_build_call_valist (fn
, nargs
, ap
);
721 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
726 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
727 value of EXPR, which is expected to be the result of folding the
728 call. This can only be done if EXPR is a CALL_EXPR with valid
729 GIMPLE operands as arguments, or if it is a suitable RHS expression
730 for a GIMPLE_ASSIGN. More complex expressions will require
731 gimplification, which will introduce additional statements. In this
732 event, no update is performed, and the function returns false.
733 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
734 replace the statement at *SI_P with an entirely new statement.
735 The new statement need not be a call, e.g., if the original call
736 folded to a constant. */
739 update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
741 gimple stmt
= gsi_stmt (*si_p
);
743 if (valid_gimple_call_p (expr
))
745 /* The call has simplified to another call. */
746 tree fn
= CALL_EXPR_FN (expr
);
748 unsigned nargs
= call_expr_nargs (expr
);
749 vec
<tree
> args
= vNULL
;
755 args
.safe_grow_cleared (nargs
);
757 for (i
= 0; i
< nargs
; i
++)
758 args
[i
] = CALL_EXPR_ARG (expr
, i
);
761 new_stmt
= gimple_build_call_vec (fn
, args
);
762 finish_update_gimple_call (si_p
, new_stmt
, stmt
);
767 else if (valid_gimple_rhs_p (expr
))
769 tree lhs
= gimple_call_lhs (stmt
);
772 /* The call has simplified to an expression
773 that cannot be represented as a GIMPLE_CALL. */
776 /* A value is expected.
777 Introduce a new GIMPLE_ASSIGN statement. */
778 STRIP_USELESS_TYPE_CONVERSION (expr
);
779 new_stmt
= gimple_build_assign (lhs
, expr
);
780 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
781 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
782 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
784 else if (!TREE_SIDE_EFFECTS (expr
))
786 /* No value is expected, and EXPR has no effect.
787 Replace it with an empty statement. */
788 new_stmt
= gimple_build_nop ();
789 if (gimple_in_ssa_p (cfun
))
791 unlink_stmt_vdef (stmt
);
797 /* No value is expected, but EXPR has an effect,
798 e.g., it could be a reference to a volatile
799 variable. Create an assignment statement
800 with a dummy (unused) lhs variable. */
801 STRIP_USELESS_TYPE_CONVERSION (expr
);
802 if (gimple_in_ssa_p (cfun
))
803 lhs
= make_ssa_name (TREE_TYPE (expr
), NULL
);
805 lhs
= create_tmp_var (TREE_TYPE (expr
), NULL
);
806 new_stmt
= gimple_build_assign (lhs
, expr
);
807 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
808 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
809 move_ssa_defining_stmt_for_defs (new_stmt
, stmt
);
811 gimple_set_location (new_stmt
, gimple_location (stmt
));
812 gsi_replace (si_p
, new_stmt
, false);
816 /* The call simplified to an expression that is
817 not a valid GIMPLE RHS. */
822 /* Entry point to the propagation engine.
824 VISIT_STMT is called for every statement visited.
825 VISIT_PHI is called for every PHI node visited. */
828 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
829 ssa_prop_visit_phi_fn visit_phi
)
831 ssa_prop_visit_stmt
= visit_stmt
;
832 ssa_prop_visit_phi
= visit_phi
;
836 /* Iterate until the worklists are empty. */
837 while (!cfg_blocks_empty_p ()
838 || interesting_ssa_edges
->length () > 0
839 || varying_ssa_edges
->length () > 0)
841 if (!cfg_blocks_empty_p ())
843 /* Pull the next block to simulate off the worklist. */
844 basic_block dest_block
= cfg_blocks_get ();
845 simulate_block (dest_block
);
848 /* In order to move things to varying as quickly as
849 possible,process the VARYING_SSA_EDGES worklist first. */
850 process_ssa_edge_worklist (&varying_ssa_edges
);
852 /* Now process the INTERESTING_SSA_EDGES worklist. */
853 process_ssa_edge_worklist (&interesting_ssa_edges
);
860 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
861 is a non-volatile pointer dereference, a structure reference or a
862 reference to a single _DECL. Ignore volatile memory references
863 because they are not interesting for the optimizers. */
866 stmt_makes_single_store (gimple stmt
)
870 if (gimple_code (stmt
) != GIMPLE_ASSIGN
871 && gimple_code (stmt
) != GIMPLE_CALL
)
874 if (!gimple_vdef (stmt
))
877 lhs
= gimple_get_lhs (stmt
);
879 /* A call statement may have a null LHS. */
883 return (!TREE_THIS_VOLATILE (lhs
)
885 || REFERENCE_CLASS_P (lhs
)));
889 /* Propagation statistics. */
894 long num_stmts_folded
;
898 static struct prop_stats_d prop_stats
;
900 /* Replace USE references in statement STMT with the values stored in
901 PROP_VALUE. Return true if at least one reference was replaced. */
904 replace_uses_in (gimple stmt
, ssa_prop_get_value_fn get_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
= (*get_value
) (tuse
);
915 if (val
== tuse
|| val
== NULL_TREE
)
918 if (gimple_code (stmt
) == GIMPLE_ASM
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
);
939 /* Replace propagated values into all the arguments for PHI using the
940 values from PROP_VALUE. */
943 replace_phi_args_in (gimple phi
, ssa_prop_get_value_fn get_value
)
946 bool replaced
= false;
948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
950 fprintf (dump_file
, "Folding PHI node: ");
951 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
954 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
956 tree arg
= gimple_phi_arg_def (phi
, i
);
958 if (TREE_CODE (arg
) == SSA_NAME
)
960 tree val
= (*get_value
) (arg
);
962 if (val
&& val
!= arg
&& may_propagate_copy (arg
, val
))
964 if (TREE_CODE (val
) != SSA_NAME
)
965 prop_stats
.num_const_prop
++;
967 prop_stats
.num_copy_prop
++;
969 propagate_value (PHI_ARG_DEF_PTR (phi
, i
), val
);
972 /* If we propagated a copy and this argument flows
973 through an abnormal edge, update the replacement
975 if (TREE_CODE (val
) == SSA_NAME
976 && gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_ABNORMAL
)
977 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val
) = 1;
982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 fprintf (dump_file
, "No folding possible\n");
988 fprintf (dump_file
, "Folded into: ");
989 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
990 fprintf (dump_file
, "\n");
996 /* Perform final substitution and folding of propagated values.
998 PROP_VALUE[I] contains the single value that should be substituted
999 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1002 If FOLD_FN is non-NULL the function will be invoked on all statements
1003 before propagating values for pass specific simplification.
1005 DO_DCE is true if trivially dead stmts can be removed.
1007 If DO_DCE is true, the statements within a BB are walked from
1008 last to first element. Otherwise we scan from first to last element.
1010 Return TRUE when something changed. */
1013 substitute_and_fold (ssa_prop_get_value_fn get_value_fn
,
1014 ssa_prop_fold_stmt_fn fold_fn
,
1018 bool something_changed
= false;
1021 if (!get_value_fn
&& !fold_fn
)
1024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1025 fprintf (dump_file
, "\nSubstituting values and folding statements\n\n");
1027 memset (&prop_stats
, 0, sizeof (prop_stats
));
1029 /* Substitute lattice values at definition sites. */
1031 for (i
= 1; i
< num_ssa_names
; ++i
)
1033 tree name
= ssa_name (i
);
1036 gimple_stmt_iterator gsi
;
1039 || virtual_operand_p (name
))
1042 def_stmt
= SSA_NAME_DEF_STMT (name
);
1043 if (gimple_nop_p (def_stmt
)
1044 /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */
1045 || (gimple_assign_single_p (def_stmt
)
1046 && gimple_assign_rhs_code (def_stmt
) == ASSERT_EXPR
)
1047 || !(val
= (*get_value_fn
) (name
))
1048 || !may_propagate_copy (name
, val
))
1051 gsi
= gsi_for_stmt (def_stmt
);
1052 if (is_gimple_assign (def_stmt
))
1054 gimple_assign_set_rhs_with_ops (&gsi
, TREE_CODE (val
),
1056 gcc_assert (gsi_stmt (gsi
) == def_stmt
);
1057 if (maybe_clean_eh_stmt (def_stmt
))
1058 gimple_purge_dead_eh_edges (gimple_bb (def_stmt
));
1059 update_stmt (def_stmt
);
1061 else if (is_gimple_call (def_stmt
))
1063 int flags
= gimple_call_flags (def_stmt
);
1065 /* Don't optimize away calls that have side-effects. */
1066 if ((flags
& (ECF_CONST
|ECF_PURE
)) == 0
1067 || (flags
& ECF_LOOPING_CONST_OR_PURE
))
1069 if (update_call_from_tree (&gsi
, val
)
1070 && maybe_clean_or_replace_eh_stmt (def_stmt
, gsi_stmt (gsi
)))
1071 gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi
)));
1073 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
1075 gimple new_stmt
= gimple_build_assign (name
, val
);
1076 gimple_stmt_iterator gsi2
;
1077 SSA_NAME_DEF_STMT (name
) = new_stmt
;
1078 gsi2
= gsi_after_labels (gimple_bb (def_stmt
));
1079 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
1080 remove_phi_node (&gsi
, false);
1083 something_changed
= true;
1086 /* Propagate into all uses and fold. */
1089 gimple_stmt_iterator i
;
1091 /* Propagate known values into PHI nodes. */
1093 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
1094 replace_phi_args_in (gsi_stmt (i
), get_value_fn
);
1096 /* Propagate known values into stmts. Do a backward walk if
1097 do_dce is true. In some case it exposes
1098 more trivially deletable stmts to walk backward. */
1099 for (i
= (do_dce
? gsi_last_bb (bb
) : gsi_start_bb (bb
)); !gsi_end_p (i
);)
1102 gimple stmt
= gsi_stmt (i
);
1104 enum gimple_code code
= gimple_code (stmt
);
1105 gimple_stmt_iterator oldi
;
1113 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1114 range information for names and they are discarded
1117 if (code
== GIMPLE_ASSIGN
1118 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
1121 /* No point propagating into a stmt whose result is not used,
1122 but instead we might be able to remove a trivially dead stmt.
1123 Don't do this when called from VRP, since the SSA_NAME which
1124 is going to be released could be still referenced in VRP
1127 && gimple_get_lhs (stmt
)
1128 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1129 && has_zero_uses (gimple_get_lhs (stmt
))
1130 && !stmt_could_throw_p (stmt
)
1131 && !gimple_has_side_effects (stmt
))
1133 gimple_stmt_iterator i2
;
1135 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1137 fprintf (dump_file
, "Removing dead stmt ");
1138 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1139 fprintf (dump_file
, "\n");
1141 prop_stats
.num_dce
++;
1142 i2
= gsi_for_stmt (stmt
);
1143 gsi_remove (&i2
, true);
1144 release_defs (stmt
);
1148 /* Replace the statement with its folded version and mark it
1150 did_replace
= false;
1151 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1153 fprintf (dump_file
, "Folding statement: ");
1154 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1159 /* Some statements may be simplified using propagator
1160 specific information. Do this before propagating
1161 into the stmt to not disturb pass specific information. */
1163 && (*fold_fn
)(&oldi
))
1166 prop_stats
.num_stmts_folded
++;
1167 stmt
= gsi_stmt (oldi
);
1171 /* Replace real uses in the statement. */
1173 did_replace
|= replace_uses_in (stmt
, get_value_fn
);
1175 /* If we made a replacement, fold the statement. */
1182 stmt
= gsi_stmt (oldi
);
1184 /* If we cleaned up EH information from the statement,
1186 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1187 gimple_purge_dead_eh_edges (bb
);
1189 if (is_gimple_assign (stmt
)
1190 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1191 == GIMPLE_SINGLE_RHS
))
1193 tree rhs
= gimple_assign_rhs1 (stmt
);
1195 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1196 recompute_tree_invariant_for_addr_expr (rhs
);
1199 /* Determine what needs to be done to update the SSA form. */
1201 if (!is_gimple_debug (stmt
))
1202 something_changed
= true;
1205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1209 fprintf (dump_file
, "Folded into: ");
1210 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1211 fprintf (dump_file
, "\n");
1214 fprintf (dump_file
, "Not folded\n");
1219 statistics_counter_event (cfun
, "Constants propagated",
1220 prop_stats
.num_const_prop
);
1221 statistics_counter_event (cfun
, "Copies propagated",
1222 prop_stats
.num_copy_prop
);
1223 statistics_counter_event (cfun
, "Statements folded",
1224 prop_stats
.num_stmts_folded
);
1225 statistics_counter_event (cfun
, "Statements deleted",
1226 prop_stats
.num_dce
);
1227 return something_changed
;
1230 #include "gt-tree-ssa-propagate.h"