1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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"
43 #include "value-prof.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 prop_simulate_again_p 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 /* Keep track of statements that have been added to one of the SSA
123 edges worklists. This flag is used to avoid visiting statements
124 unnecessarily when draining an SSA edge worklist. If while
125 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.
129 NOTE: users of the propagation engine are not allowed to use
130 the GF_PLF_1 flag. */
131 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
133 /* A bitmap to keep track of executable blocks in the CFG. */
134 static sbitmap executable_blocks;
136 /* Array of control flow edges on the worklist. */
137 static VEC(basic_block,heap) *cfg_blocks;
139 static unsigned int cfg_blocks_num = 0;
140 static int cfg_blocks_tail;
141 static int cfg_blocks_head;
143 static sbitmap bb_in_list;
145 /* Worklist of SSA edges which will need reexamination as their
146 definition has changed. SSA edges are def-use edges in the SSA
147 web. For each D-U edge, we store the target statement or PHI node
149 static GTY(()) VEC(gimple,gc) *interesting_ssa_edges;
151 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
152 list of SSA edges is split into two. One contains all SSA edges
153 who need to be reexamined because their lattice value changed to
154 varying (this worklist), and the other contains all other SSA edges
155 to be reexamined (INTERESTING_SSA_EDGES).
157 Since most values in the program are VARYING, the ideal situation
158 is to move them to that lattice value as quickly as possible.
159 Thus, it doesn't make sense to process any other type of lattice
160 value until all VARYING values are propagated fully, which is one
161 thing using the VARYING worklist achieves. In addition, if we
162 don't use a separate worklist for VARYING edges, we end up with
163 situations where lattice values move from
164 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
165 static GTY(()) VEC(gimple,gc) *varying_ssa_edges;
168 /* Return true if the block worklist empty. */
171 cfg_blocks_empty_p (void)
173 return (cfg_blocks_num == 0);
177 /* Add a basic block to the worklist. The block must not be already
178 in the worklist, and it must not be the ENTRY or EXIT block. */
181 cfg_blocks_add (basic_block bb)
185 gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
186 gcc_assert (!TEST_BIT (bb_in_list, bb->index));
188 if (cfg_blocks_empty_p ())
190 cfg_blocks_tail = cfg_blocks_head = 0;
196 if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks))
198 /* We have to grow the array now. Adjust to queue to occupy
199 the full space of the original array. We do not need to
200 initialize the newly allocated portion of the array
201 because we keep track of CFG_BLOCKS_HEAD and
203 cfg_blocks_tail = VEC_length (basic_block, cfg_blocks);
205 VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
207 /* Minor optimization: we prefer to see blocks with more
208 predecessors later, because there is more of a chance that
209 the incoming edges will be executable. */
210 else if (EDGE_COUNT (bb->preds)
211 >= EDGE_COUNT (VEC_index (basic_block, cfg_blocks,
212 cfg_blocks_head)->preds))
213 cfg_blocks_tail = ((cfg_blocks_tail + 1)
214 % VEC_length (basic_block, cfg_blocks));
217 if (cfg_blocks_head == 0)
218 cfg_blocks_head = VEC_length (basic_block, cfg_blocks);
224 VEC_replace (basic_block, cfg_blocks,
225 head ? cfg_blocks_head : cfg_blocks_tail,
227 SET_BIT (bb_in_list, bb->index);
231 /* Remove a block from the worklist. */
234 cfg_blocks_get (void)
238 bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head);
240 gcc_assert (!cfg_blocks_empty_p ());
243 cfg_blocks_head = ((cfg_blocks_head + 1)
244 % VEC_length (basic_block, cfg_blocks));
246 RESET_BIT (bb_in_list, bb->index);
252 /* We have just defined a new value for VAR. If IS_VARYING is true,
253 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
254 them to INTERESTING_SSA_EDGES. */
257 add_ssa_edge (tree var, bool is_varying)
259 imm_use_iterator iter;
262 FOR_EACH_IMM_USE_FAST (use_p, iter, var)
264 gimple use_stmt = USE_STMT (use_p);
266 if (prop_simulate_again_p (use_stmt)
267 && !gimple_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST))
269 gimple_set_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST, true);
271 VEC_safe_push (gimple, gc, varying_ssa_edges, use_stmt);
273 VEC_safe_push (gimple, gc, interesting_ssa_edges, use_stmt);
279 /* Add edge E to the control flow worklist. */
282 add_control_edge (edge e)
284 basic_block bb = e->dest;
285 if (bb == EXIT_BLOCK_PTR)
288 /* If the edge had already been executed, skip it. */
289 if (e->flags & EDGE_EXECUTABLE)
292 e->flags |= EDGE_EXECUTABLE;
294 /* If the block is already in the list, we're done. */
295 if (TEST_BIT (bb_in_list, bb->index))
300 if (dump_file && (dump_flags & TDF_DETAILS))
301 fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
302 e->src->index, e->dest->index);
306 /* Simulate the execution of STMT and update the work lists accordingly. */
309 simulate_stmt (gimple stmt)
311 enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
312 edge taken_edge = NULL;
313 tree output_name = NULL_TREE;
315 /* Don't bother visiting statements that are already
316 considered varying by the propagator. */
317 if (!prop_simulate_again_p (stmt))
320 if (gimple_code (stmt) == GIMPLE_PHI)
322 val = ssa_prop_visit_phi (stmt);
323 output_name = gimple_phi_result (stmt);
326 val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
328 if (val == SSA_PROP_VARYING)
330 prop_set_simulate_again (stmt, false);
332 /* If the statement produced a new varying value, add the SSA
333 edges coming out of OUTPUT_NAME. */
335 add_ssa_edge (output_name, true);
337 /* If STMT transfers control out of its basic block, add
338 all outgoing edges to the work list. */
339 if (stmt_ends_bb_p (stmt))
343 basic_block bb = gimple_bb (stmt);
344 FOR_EACH_EDGE (e, ei, bb->succs)
345 add_control_edge (e);
348 else if (val == SSA_PROP_INTERESTING)
350 /* If the statement produced new value, add the SSA edges coming
351 out of OUTPUT_NAME. */
353 add_ssa_edge (output_name, false);
355 /* If we know which edge is going to be taken out of this block,
356 add it to the CFG work list. */
358 add_control_edge (taken_edge);
362 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
363 drain. This pops statements off the given WORKLIST and processes
364 them until there are no more statements on WORKLIST.
365 We take a pointer to WORKLIST because it may be reallocated when an
366 SSA edge is added to it in simulate_stmt. */
369 process_ssa_edge_worklist (VEC(gimple,gc) **worklist)
371 /* Drain the entire worklist. */
372 while (VEC_length (gimple, *worklist) > 0)
376 /* Pull the statement to simulate off the worklist. */
377 gimple stmt = VEC_pop (gimple, *worklist);
379 /* If this statement was already visited by simulate_block, then
380 we don't need to visit it again here. */
381 if (!gimple_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST))
384 /* STMT is no longer in a worklist. */
385 gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
387 if (dump_file && (dump_flags & TDF_DETAILS))
389 fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
390 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
393 bb = gimple_bb (stmt);
395 /* PHI nodes are always visited, regardless of whether or not
396 the destination block is executable. Otherwise, visit the
397 statement only if its block is marked executable. */
398 if (gimple_code (stmt) == GIMPLE_PHI
399 || TEST_BIT (executable_blocks, bb->index))
400 simulate_stmt (stmt);
405 /* Simulate the execution of BLOCK. Evaluate the statement associated
406 with each variable reference inside the block. */
409 simulate_block (basic_block block)
411 gimple_stmt_iterator gsi;
413 /* There is nothing to do for the exit block. */
414 if (block == EXIT_BLOCK_PTR)
417 if (dump_file && (dump_flags & TDF_DETAILS))
418 fprintf (dump_file, "\nSimulating block %d\n", block->index);
420 /* Always simulate PHI nodes, even if we have simulated this block
422 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
423 simulate_stmt (gsi_stmt (gsi));
425 /* If this is the first time we've simulated this block, then we
426 must simulate each of its statements. */
427 if (!TEST_BIT (executable_blocks, block->index))
429 gimple_stmt_iterator j;
430 unsigned int normal_edge_count;
434 /* Note that we have simulated this block. */
435 SET_BIT (executable_blocks, block->index);
437 for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
439 gimple stmt = gsi_stmt (j);
441 /* If this statement is already in the worklist then
442 "cancel" it. The reevaluation implied by the worklist
443 entry will produce the same value we generate here and
444 thus reevaluating it again from the worklist is
446 if (gimple_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST))
447 gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
449 simulate_stmt (stmt);
452 /* We can not predict when abnormal edges will be executed, so
453 once a block is considered executable, we consider any
454 outgoing abnormal edges as executable.
456 At the same time, if this block has only one successor that is
457 reached by non-abnormal edges, then add that successor to the
459 normal_edge_count = 0;
461 FOR_EACH_EDGE (e, ei, block->succs)
463 if (e->flags & EDGE_ABNORMAL)
464 add_control_edge (e);
472 if (normal_edge_count == 1)
473 add_control_edge (normal_edge);
478 /* Initialize local data structures and work lists. */
488 /* Worklists of SSA edges. */
489 interesting_ssa_edges = VEC_alloc (gimple, gc, 20);
490 varying_ssa_edges = VEC_alloc (gimple, gc, 20);
492 executable_blocks = sbitmap_alloc (last_basic_block);
493 sbitmap_zero (executable_blocks);
495 bb_in_list = sbitmap_alloc (last_basic_block);
496 sbitmap_zero (bb_in_list);
498 if (dump_file && (dump_flags & TDF_DETAILS))
499 dump_immediate_uses (dump_file);
501 cfg_blocks = VEC_alloc (basic_block, heap, 20);
502 VEC_safe_grow (basic_block, heap, cfg_blocks, 20);
504 /* Initialize the values for every SSA_NAME. */
505 for (i = 1; i < num_ssa_names; i++)
507 SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE;
509 /* Initially assume that every edge in the CFG is not executable.
510 (including the edges coming out of ENTRY_BLOCK_PTR). */
513 gimple_stmt_iterator si;
515 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
516 gimple_set_plf (gsi_stmt (si), STMT_IN_SSA_EDGE_WORKLIST, false);
518 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
519 gimple_set_plf (gsi_stmt (si), STMT_IN_SSA_EDGE_WORKLIST, false);
521 FOR_EACH_EDGE (e, ei, bb->succs)
522 e->flags &= ~EDGE_EXECUTABLE;
525 /* Seed the algorithm by adding the successors of the entry block to the
527 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
528 add_control_edge (e);
532 /* Free allocated storage. */
537 VEC_free (gimple, gc, interesting_ssa_edges);
538 VEC_free (gimple, gc, varying_ssa_edges);
539 VEC_free (basic_block, heap, cfg_blocks);
541 sbitmap_free (bb_in_list);
542 sbitmap_free (executable_blocks);
546 /* Return true if EXPR is an acceptable right-hand-side for a
547 GIMPLE assignment. We validate the entire tree, not just
548 the root node, thus catching expressions that embed complex
549 operands that are not permitted in GIMPLE. This function
550 is needed because the folding routines in fold-const.c
551 may return such expressions in some cases, e.g., an array
552 access with an embedded index addition. It may make more
553 sense to have folding routines that are sensitive to the
554 constraints on GIMPLE operands, rather than abandoning any
555 any attempt to fold if the usual folding turns out to be too
559 valid_gimple_rhs_p (tree expr)
561 enum tree_code code = TREE_CODE (expr);
563 switch (TREE_CODE_CLASS (code))
565 case tcc_declaration:
566 if (!is_gimple_variable (expr))
571 /* All constants are ok. */
576 if (!is_gimple_val (TREE_OPERAND (expr, 0))
577 || !is_gimple_val (TREE_OPERAND (expr, 1)))
582 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
592 if (is_gimple_min_invariant (expr))
594 t = TREE_OPERAND (expr, 0);
595 while (handled_component_p (t))
597 /* ??? More checks needed, see the GIMPLE verifier. */
598 if ((TREE_CODE (t) == ARRAY_REF
599 || TREE_CODE (t) == ARRAY_RANGE_REF)
600 && !is_gimple_val (TREE_OPERAND (t, 1)))
602 t = TREE_OPERAND (t, 0);
604 if (!is_gimple_id (t))
610 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
617 if (!is_gimple_val (TREE_OPERAND (expr, 0))
618 || !is_gimple_val (TREE_OPERAND (expr, 1)))
634 case tcc_exceptional:
635 if (code != SSA_NAME)
647 /* Return true if EXPR is a CALL_EXPR suitable for representation
648 as a single GIMPLE_CALL statement. If the arguments require
649 further gimplification, return false. */
652 valid_gimple_call_p (tree expr)
656 if (TREE_CODE (expr) != CALL_EXPR)
659 nargs = call_expr_nargs (expr);
660 for (i = 0; i < nargs; i++)
661 if (! is_gimple_operand (CALL_EXPR_ARG (expr, i)))
668 /* Make SSA names defined by OLD_STMT point to NEW_STMT
669 as their defining statement. */
672 move_ssa_defining_stmt_for_defs (gimple new_stmt, gimple old_stmt)
677 if (gimple_in_ssa_p (cfun))
679 /* Make defined SSA_NAMEs point to the new
680 statement as their definition. */
681 FOR_EACH_SSA_TREE_OPERAND (var, old_stmt, iter, SSA_OP_ALL_DEFS)
683 if (TREE_CODE (var) == SSA_NAME)
684 SSA_NAME_DEF_STMT (var) = new_stmt;
690 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
691 value of EXPR, which is expected to be the result of folding the
692 call. This can only be done if EXPR is a CALL_EXPR with valid
693 GIMPLE operands as arguments, or if it is a suitable RHS expression
694 for a GIMPLE_ASSIGN. More complex expressions will require
695 gimplification, which will introduce addtional statements. In this
696 event, no update is performed, and the function returns false.
697 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
698 replace the statement at *SI_P with an entirely new statement.
699 The new statement need not be a call, e.g., if the original call
700 folded to a constant. */
703 update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
707 gimple stmt = gsi_stmt (*si_p);
709 gcc_assert (is_gimple_call (stmt));
711 lhs = gimple_call_lhs (stmt);
713 if (valid_gimple_call_p (expr))
715 /* The call has simplified to another call. */
716 tree fn = CALL_EXPR_FN (expr);
718 unsigned nargs = call_expr_nargs (expr);
719 VEC(tree, heap) *args = NULL;
724 args = VEC_alloc (tree, heap, nargs);
725 VEC_safe_grow (tree, heap, args, nargs);
727 for (i = 0; i < nargs; i++)
728 VEC_replace (tree, args, i, CALL_EXPR_ARG (expr, i));
731 new_stmt = gimple_build_call_vec (fn, args);
732 gimple_call_set_lhs (new_stmt, lhs);
733 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
734 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
735 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
736 gimple_set_location (new_stmt, gimple_location (stmt));
737 gsi_replace (si_p, new_stmt, false);
738 VEC_free (tree, heap, args);
742 else if (valid_gimple_rhs_p (expr))
746 /* The call has simplified to an expression
747 that cannot be represented as a GIMPLE_CALL. */
750 /* A value is expected.
751 Introduce a new GIMPLE_ASSIGN statement. */
752 STRIP_USELESS_TYPE_CONVERSION (expr);
753 new_stmt = gimple_build_assign (lhs, expr);
754 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
755 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
756 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
758 else if (!TREE_SIDE_EFFECTS (expr))
760 /* No value is expected, and EXPR has no effect.
761 Replace it with an empty statement. */
762 new_stmt = gimple_build_nop ();
763 unlink_stmt_vdef (stmt);
768 /* No value is expected, but EXPR has an effect,
769 e.g., it could be a reference to a volatile
770 variable. Create an assignment statement
771 with a dummy (unused) lhs variable. */
772 STRIP_USELESS_TYPE_CONVERSION (expr);
773 lhs = create_tmp_var (TREE_TYPE (expr), NULL);
774 new_stmt = gimple_build_assign (lhs, expr);
775 add_referenced_var (lhs);
776 lhs = make_ssa_name (lhs, new_stmt);
777 gimple_assign_set_lhs (new_stmt, lhs);
778 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
779 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
780 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
782 gimple_set_location (new_stmt, gimple_location (stmt));
783 gsi_replace (si_p, new_stmt, false);
787 /* The call simplified to an expression that is
788 not a valid GIMPLE RHS. */
793 /* Entry point to the propagation engine.
795 VISIT_STMT is called for every statement visited.
796 VISIT_PHI is called for every PHI node visited. */
799 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
800 ssa_prop_visit_phi_fn visit_phi)
802 ssa_prop_visit_stmt = visit_stmt;
803 ssa_prop_visit_phi = visit_phi;
807 /* Iterate until the worklists are empty. */
808 while (!cfg_blocks_empty_p ()
809 || VEC_length (gimple, interesting_ssa_edges) > 0
810 || VEC_length (gimple, varying_ssa_edges) > 0)
812 if (!cfg_blocks_empty_p ())
814 /* Pull the next block to simulate off the worklist. */
815 basic_block dest_block = cfg_blocks_get ();
816 simulate_block (dest_block);
819 /* In order to move things to varying as quickly as
820 possible,process the VARYING_SSA_EDGES worklist first. */
821 process_ssa_edge_worklist (&varying_ssa_edges);
823 /* Now process the INTERESTING_SSA_EDGES worklist. */
824 process_ssa_edge_worklist (&interesting_ssa_edges);
831 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
832 is a non-volatile pointer dereference, a structure reference or a
833 reference to a single _DECL. Ignore volatile memory references
834 because they are not interesting for the optimizers. */
837 stmt_makes_single_store (gimple stmt)
841 if (gimple_code (stmt) != GIMPLE_ASSIGN
842 && gimple_code (stmt) != GIMPLE_CALL)
845 if (!gimple_vdef (stmt))
848 lhs = gimple_get_lhs (stmt);
850 /* A call statement may have a null LHS. */
854 return (!TREE_THIS_VOLATILE (lhs)
856 || REFERENCE_CLASS_P (lhs)));
860 /* Propagation statistics. */
865 long num_pred_folded;
869 static struct prop_stats_d prop_stats;
871 /* Replace USE references in statement STMT with the values stored in
872 PROP_VALUE. Return true if at least one reference was replaced. */
875 replace_uses_in (gimple stmt, prop_value_t *prop_value)
877 bool replaced = false;
881 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
883 tree tuse = USE_FROM_PTR (use);
884 tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
886 if (val == tuse || val == NULL_TREE)
889 if (gimple_code (stmt) == GIMPLE_ASM
890 && !may_propagate_copy_into_asm (tuse))
893 if (!may_propagate_copy (tuse, val))
896 if (TREE_CODE (val) != SSA_NAME)
897 prop_stats.num_const_prop++;
899 prop_stats.num_copy_prop++;
901 propagate_value (use, val);
910 /* Replace propagated values into all the arguments for PHI using the
911 values from PROP_VALUE. */
914 replace_phi_args_in (gimple phi, prop_value_t *prop_value)
917 bool replaced = false;
919 if (dump_file && (dump_flags & TDF_DETAILS))
921 fprintf (dump_file, "Folding PHI node: ");
922 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
925 for (i = 0; i < gimple_phi_num_args (phi); i++)
927 tree arg = gimple_phi_arg_def (phi, i);
929 if (TREE_CODE (arg) == SSA_NAME)
931 tree val = prop_value[SSA_NAME_VERSION (arg)].value;
933 if (val && val != arg && may_propagate_copy (arg, val))
935 if (TREE_CODE (val) != SSA_NAME)
936 prop_stats.num_const_prop++;
938 prop_stats.num_copy_prop++;
940 propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
943 /* If we propagated a copy and this argument flows
944 through an abnormal edge, update the replacement
946 if (TREE_CODE (val) == SSA_NAME
947 && gimple_phi_arg_edge (phi, i)->flags & EDGE_ABNORMAL)
948 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
953 if (dump_file && (dump_flags & TDF_DETAILS))
956 fprintf (dump_file, "No folding possible\n");
959 fprintf (dump_file, "Folded into: ");
960 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
961 fprintf (dump_file, "\n");
967 /* If the statement pointed by SI has a predicate whose value can be
968 computed using the value range information computed by VRP, compute
969 its value and return true. Otherwise, return false. */
972 fold_predicate_in (gimple_stmt_iterator *si)
974 bool assignment_p = false;
976 gimple stmt = gsi_stmt (*si);
978 if (is_gimple_assign (stmt)
979 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
982 val = vrp_evaluate_conditional (gimple_assign_rhs_code (stmt),
983 gimple_assign_rhs1 (stmt),
984 gimple_assign_rhs2 (stmt),
987 else if (gimple_code (stmt) == GIMPLE_COND)
988 val = vrp_evaluate_conditional (gimple_cond_code (stmt),
989 gimple_cond_lhs (stmt),
990 gimple_cond_rhs (stmt),
999 val = fold_convert (gimple_expr_type (stmt), val);
1003 fprintf (dump_file, "Folding predicate ");
1004 print_gimple_expr (dump_file, stmt, 0, 0);
1005 fprintf (dump_file, " to ");
1006 print_generic_expr (dump_file, val, 0);
1007 fprintf (dump_file, "\n");
1010 prop_stats.num_pred_folded++;
1012 if (is_gimple_assign (stmt))
1013 gimple_assign_set_rhs_from_tree (si, val);
1016 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
1017 if (integer_zerop (val))
1018 gimple_cond_make_false (stmt);
1019 else if (integer_onep (val))
1020 gimple_cond_make_true (stmt);
1032 /* Perform final substitution and folding of propagated values.
1034 PROP_VALUE[I] contains the single value that should be substituted
1035 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1038 If USE_RANGES_P is true, statements that contain predicate
1039 expressions are evaluated with a call to vrp_evaluate_conditional.
1040 This will only give meaningful results when called from tree-vrp.c
1041 (the information used by vrp_evaluate_conditional is built by the
1044 Return TRUE when something changed. */
1047 substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
1050 bool something_changed = false;
1052 if (prop_value == NULL && !use_ranges_p)
1055 if (dump_file && (dump_flags & TDF_DETAILS))
1056 fprintf (dump_file, "\nSubstituting values and folding statements\n\n");
1058 memset (&prop_stats, 0, sizeof (prop_stats));
1060 /* Substitute values in every statement of every basic block. */
1063 gimple_stmt_iterator i;
1065 /* Propagate known values into PHI nodes. */
1067 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
1068 replace_phi_args_in (gsi_stmt (i), prop_value);
1070 /* Propagate known values into stmts. Do a backward walk to expose
1071 more trivially deletable stmts. */
1072 for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1075 gimple stmt = gsi_stmt (i);
1077 enum gimple_code code = gimple_code (stmt);
1079 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1080 range information for names and they are discarded
1083 if (code == GIMPLE_ASSIGN
1084 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
1090 /* No point propagating into a stmt whose result is not used,
1091 but instead we might be able to remove a trivially dead stmt. */
1092 if (gimple_get_lhs (stmt)
1093 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
1094 && has_zero_uses (gimple_get_lhs (stmt))
1095 && !stmt_could_throw_p (stmt)
1096 && !gimple_has_side_effects (stmt))
1098 gimple_stmt_iterator i2;
1100 if (dump_file && dump_flags & TDF_DETAILS)
1102 fprintf (dump_file, "Removing dead stmt ");
1103 print_gimple_stmt (dump_file, stmt, 0, 0);
1104 fprintf (dump_file, "\n");
1106 prop_stats.num_dce++;
1108 i2 = gsi_for_stmt (stmt);
1109 gsi_remove (&i2, true);
1110 release_defs (stmt);
1114 /* Record the state of the statement before replacements. */
1115 push_stmt_changes (gsi_stmt_ptr (&i));
1117 /* Replace the statement with its folded version and mark it
1119 did_replace = false;
1120 if (dump_file && (dump_flags & TDF_DETAILS))
1122 fprintf (dump_file, "Folding statement: ");
1123 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1126 /* If we have range information, see if we can fold
1127 predicate expressions. */
1130 did_replace = fold_predicate_in (&i);
1131 /* fold_predicate_in should not have reallocated STMT. */
1132 gcc_assert (gsi_stmt (i) == stmt);
1135 /* Only replace real uses if we couldn't fold the
1136 statement using value range information. */
1139 did_replace |= replace_uses_in (stmt, prop_value);
1141 /* If we made a replacement, fold the statement. */
1147 /* Some statements may be simplified using ranges. For
1148 example, division may be replaced by shifts, modulo
1149 replaced with bitwise and, etc. Do this after
1150 substituting constants, folding, etc so that we're
1151 presented with a fully propagated, canonicalized
1154 did_replace |= simplify_stmt_using_ranges (&i);
1159 stmt = gsi_stmt (i);
1161 /* If we cleaned up EH information from the statement,
1163 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1164 gimple_purge_dead_eh_edges (bb);
1166 if (is_gimple_assign (stmt)
1167 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1168 == GIMPLE_SINGLE_RHS))
1170 tree rhs = gimple_assign_rhs1 (stmt);
1172 if (TREE_CODE (rhs) == ADDR_EXPR)
1173 recompute_tree_invariant_for_addr_expr (rhs);
1176 /* Determine what needs to be done to update the SSA form. */
1177 pop_stmt_changes (gsi_stmt_ptr (&i));
1178 something_changed = true;
1182 /* The statement was not modified, discard the change buffer. */
1183 discard_stmt_changes (gsi_stmt_ptr (&i));
1186 if (dump_file && (dump_flags & TDF_DETAILS))
1190 fprintf (dump_file, "Folded into: ");
1191 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1192 fprintf (dump_file, "\n");
1195 fprintf (dump_file, "Not folded\n");
1202 statistics_counter_event (cfun, "Constants propagated",
1203 prop_stats.num_const_prop);
1204 statistics_counter_event (cfun, "Copies propagated",
1205 prop_stats.num_copy_prop);
1206 statistics_counter_event (cfun, "Predicates folded",
1207 prop_stats.num_pred_folded);
1208 statistics_counter_event (cfun, "Statements deleted",
1209 prop_stats.num_dce);
1210 return something_changed;
1213 #include "gt-tree-ssa-propagate.h"