* c-c++-common/ubsan/float-cast-overflow-6.c: Add i?86-*-* target.
[official-gcc.git] / gcc / tree-ssa-propagate.c
blob9f4d3811f2872ac06babd177ba53e3b6e395efb2
1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004-2014 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
10 later version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "tm_p.h"
28 #include "predict.h"
29 #include "vec.h"
30 #include "hashtab.h"
31 #include "hash-set.h"
32 #include "machmode.h"
33 #include "hard-reg-set.h"
34 #include "input.h"
35 #include "function.h"
36 #include "dominance.h"
37 #include "cfg.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
40 #include "dumpfile.h"
41 #include "bitmap.h"
42 #include "sbitmap.h"
43 #include "tree-ssa-alias.h"
44 #include "internal-fn.h"
45 #include "gimple-fold.h"
46 #include "tree-eh.h"
47 #include "gimple-expr.h"
48 #include "is-a.h"
49 #include "gimple.h"
50 #include "gimplify.h"
51 #include "gimple-iterator.h"
52 #include "gimple-ssa.h"
53 #include "tree-cfg.h"
54 #include "tree-phinodes.h"
55 #include "ssa-iterators.h"
56 #include "stringpool.h"
57 #include "tree-ssanames.h"
58 #include "tree-ssa.h"
59 #include "tree-ssa-propagate.h"
60 #include "langhooks.h"
61 #include "value-prof.h"
62 #include "domwalk.h"
64 /* This file implements a generic value propagation engine based on
65 the same propagation used by the SSA-CCP algorithm [1].
67 Propagation is performed by simulating the execution of every
68 statement that produces the value being propagated. Simulation
69 proceeds as follows:
71 1- Initially, all edges of the CFG are marked not executable and
72 the CFG worklist is seeded with all the statements in the entry
73 basic block (block 0).
75 2- Every statement S is simulated with a call to the call-back
76 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
77 results:
79 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
80 interest and does not affect any of the work lists.
82 SSA_PROP_VARYING: The value produced by S cannot be determined
83 at compile time. Further simulation of S is not required.
84 If S is a conditional jump, all the outgoing edges for the
85 block are considered executable and added to the work
86 list.
88 SSA_PROP_INTERESTING: S produces a value that can be computed
89 at compile time. Its result can be propagated into the
90 statements that feed from S. Furthermore, if S is a
91 conditional jump, only the edge known to be taken is added
92 to the work list. Edges that are known not to execute are
93 never simulated.
95 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
96 return value from SSA_PROP_VISIT_PHI has the same semantics as
97 described in #2.
99 4- Three work lists are kept. Statements are only added to these
100 lists if they produce one of SSA_PROP_INTERESTING or
101 SSA_PROP_VARYING.
103 CFG_BLOCKS contains the list of blocks to be simulated.
104 Blocks are added to this list if their incoming edges are
105 found executable.
107 VARYING_SSA_EDGES contains the list of statements that feed
108 from statements that produce an SSA_PROP_VARYING result.
109 These are simulated first to speed up processing.
111 INTERESTING_SSA_EDGES contains the list of statements that
112 feed from statements that produce an SSA_PROP_INTERESTING
113 result.
115 5- Simulation terminates when all three work lists are drained.
117 Before calling ssa_propagate, it is important to clear
118 prop_simulate_again_p for all the statements in the program that
119 should be simulated. This initialization allows an implementation
120 to specify which statements should never be simulated.
122 It is also important to compute def-use information before calling
123 ssa_propagate.
125 References:
127 [1] Constant propagation with conditional branches,
128 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
130 [2] Building an Optimizing Compiler,
131 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
133 [3] Advanced Compiler Design and Implementation,
134 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
136 /* Function pointers used to parameterize the propagation engine. */
137 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
138 static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
140 /* Keep track of statements that have been added to one of the SSA
141 edges worklists. This flag is used to avoid visiting statements
142 unnecessarily when draining an SSA edge worklist. If while
143 simulating a basic block, we find a statement with
144 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
145 processing from visiting it again.
147 NOTE: users of the propagation engine are not allowed to use
148 the GF_PLF_1 flag. */
149 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
151 /* A bitmap to keep track of executable blocks in the CFG. */
152 static sbitmap executable_blocks;
154 /* Array of control flow edges on the worklist. */
155 static vec<basic_block> cfg_blocks;
157 static unsigned int cfg_blocks_num = 0;
158 static int cfg_blocks_tail;
159 static int cfg_blocks_head;
161 static sbitmap bb_in_list;
163 /* Worklist of SSA edges which will need reexamination as their
164 definition has changed. SSA edges are def-use edges in the SSA
165 web. For each D-U edge, we store the target statement or PHI node
166 U. */
167 static vec<gimple> interesting_ssa_edges;
169 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
170 list of SSA edges is split into two. One contains all SSA edges
171 who need to be reexamined because their lattice value changed to
172 varying (this worklist), and the other contains all other SSA edges
173 to be reexamined (INTERESTING_SSA_EDGES).
175 Since most values in the program are VARYING, the ideal situation
176 is to move them to that lattice value as quickly as possible.
177 Thus, it doesn't make sense to process any other type of lattice
178 value until all VARYING values are propagated fully, which is one
179 thing using the VARYING worklist achieves. In addition, if we
180 don't use a separate worklist for VARYING edges, we end up with
181 situations where lattice values move from
182 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
183 static vec<gimple> varying_ssa_edges;
186 /* Return true if the block worklist empty. */
188 static inline bool
189 cfg_blocks_empty_p (void)
191 return (cfg_blocks_num == 0);
195 /* Add a basic block to the worklist. The block must not be already
196 in the worklist, and it must not be the ENTRY or EXIT block. */
198 static void
199 cfg_blocks_add (basic_block bb)
201 bool head = false;
203 gcc_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
204 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
205 gcc_assert (!bitmap_bit_p (bb_in_list, bb->index));
207 if (cfg_blocks_empty_p ())
209 cfg_blocks_tail = cfg_blocks_head = 0;
210 cfg_blocks_num = 1;
212 else
214 cfg_blocks_num++;
215 if (cfg_blocks_num > cfg_blocks.length ())
217 /* We have to grow the array now. Adjust to queue to occupy
218 the full space of the original array. We do not need to
219 initialize the newly allocated portion of the array
220 because we keep track of CFG_BLOCKS_HEAD and
221 CFG_BLOCKS_HEAD. */
222 cfg_blocks_tail = cfg_blocks.length ();
223 cfg_blocks_head = 0;
224 cfg_blocks.safe_grow (2 * cfg_blocks_tail);
226 /* Minor optimization: we prefer to see blocks with more
227 predecessors later, because there is more of a chance that
228 the incoming edges will be executable. */
229 else if (EDGE_COUNT (bb->preds)
230 >= EDGE_COUNT (cfg_blocks[cfg_blocks_head]->preds))
231 cfg_blocks_tail = ((cfg_blocks_tail + 1) % cfg_blocks.length ());
232 else
234 if (cfg_blocks_head == 0)
235 cfg_blocks_head = cfg_blocks.length ();
236 --cfg_blocks_head;
237 head = true;
241 cfg_blocks[head ? cfg_blocks_head : cfg_blocks_tail] = bb;
242 bitmap_set_bit (bb_in_list, bb->index);
246 /* Remove a block from the worklist. */
248 static basic_block
249 cfg_blocks_get (void)
251 basic_block bb;
253 bb = cfg_blocks[cfg_blocks_head];
255 gcc_assert (!cfg_blocks_empty_p ());
256 gcc_assert (bb);
258 cfg_blocks_head = ((cfg_blocks_head + 1) % cfg_blocks.length ());
259 --cfg_blocks_num;
260 bitmap_clear_bit (bb_in_list, bb->index);
262 return bb;
266 /* We have just defined a new value for VAR. If IS_VARYING is true,
267 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
268 them to INTERESTING_SSA_EDGES. */
270 static void
271 add_ssa_edge (tree var, bool is_varying)
273 imm_use_iterator iter;
274 use_operand_p use_p;
276 FOR_EACH_IMM_USE_FAST (use_p, iter, var)
278 gimple use_stmt = USE_STMT (use_p);
280 if (prop_simulate_again_p (use_stmt)
281 && !gimple_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST))
283 gimple_set_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST, true);
284 if (is_varying)
285 varying_ssa_edges.safe_push (use_stmt);
286 else
287 interesting_ssa_edges.safe_push (use_stmt);
293 /* Add edge E to the control flow worklist. */
295 static void
296 add_control_edge (edge e)
298 basic_block bb = e->dest;
299 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
300 return;
302 /* If the edge had already been executed, skip it. */
303 if (e->flags & EDGE_EXECUTABLE)
304 return;
306 e->flags |= EDGE_EXECUTABLE;
308 /* If the block is already in the list, we're done. */
309 if (bitmap_bit_p (bb_in_list, bb->index))
310 return;
312 cfg_blocks_add (bb);
314 if (dump_file && (dump_flags & TDF_DETAILS))
315 fprintf (dump_file, "\nAdding Destination of edge (%d -> %d) to worklist\n",
316 e->src->index, e->dest->index);
320 /* Simulate the execution of STMT and update the work lists accordingly. */
322 static void
323 simulate_stmt (gimple stmt)
325 enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
326 edge taken_edge = NULL;
327 tree output_name = NULL_TREE;
329 /* Don't bother visiting statements that are already
330 considered varying by the propagator. */
331 if (!prop_simulate_again_p (stmt))
332 return;
334 if (gimple_code (stmt) == GIMPLE_PHI)
336 val = ssa_prop_visit_phi (stmt);
337 output_name = gimple_phi_result (stmt);
339 else
340 val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
342 if (val == SSA_PROP_VARYING)
344 prop_set_simulate_again (stmt, false);
346 /* If the statement produced a new varying value, add the SSA
347 edges coming out of OUTPUT_NAME. */
348 if (output_name)
349 add_ssa_edge (output_name, true);
351 /* If STMT transfers control out of its basic block, add
352 all outgoing edges to the work list. */
353 if (stmt_ends_bb_p (stmt))
355 edge e;
356 edge_iterator ei;
357 basic_block bb = gimple_bb (stmt);
358 FOR_EACH_EDGE (e, ei, bb->succs)
359 add_control_edge (e);
362 else if (val == SSA_PROP_INTERESTING)
364 /* If the statement produced new value, add the SSA edges coming
365 out of OUTPUT_NAME. */
366 if (output_name)
367 add_ssa_edge (output_name, false);
369 /* If we know which edge is going to be taken out of this block,
370 add it to the CFG work list. */
371 if (taken_edge)
372 add_control_edge (taken_edge);
376 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
377 drain. This pops statements off the given WORKLIST and processes
378 them until there are no more statements on WORKLIST.
379 We take a pointer to WORKLIST because it may be reallocated when an
380 SSA edge is added to it in simulate_stmt. */
382 static void
383 process_ssa_edge_worklist (vec<gimple> *worklist)
385 /* Drain the entire worklist. */
386 while (worklist->length () > 0)
388 basic_block bb;
390 /* Pull the statement to simulate off the worklist. */
391 gimple stmt = worklist->pop ();
393 /* If this statement was already visited by simulate_block, then
394 we don't need to visit it again here. */
395 if (!gimple_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST))
396 continue;
398 /* STMT is no longer in a worklist. */
399 gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
401 if (dump_file && (dump_flags & TDF_DETAILS))
403 fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
404 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
407 bb = gimple_bb (stmt);
409 /* PHI nodes are always visited, regardless of whether or not
410 the destination block is executable. Otherwise, visit the
411 statement only if its block is marked executable. */
412 if (gimple_code (stmt) == GIMPLE_PHI
413 || bitmap_bit_p (executable_blocks, bb->index))
414 simulate_stmt (stmt);
419 /* Simulate the execution of BLOCK. Evaluate the statement associated
420 with each variable reference inside the block. */
422 static void
423 simulate_block (basic_block block)
425 gimple_stmt_iterator gsi;
427 /* There is nothing to do for the exit block. */
428 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
429 return;
431 if (dump_file && (dump_flags & TDF_DETAILS))
432 fprintf (dump_file, "\nSimulating block %d\n", block->index);
434 /* Always simulate PHI nodes, even if we have simulated this block
435 before. */
436 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
437 simulate_stmt (gsi_stmt (gsi));
439 /* If this is the first time we've simulated this block, then we
440 must simulate each of its statements. */
441 if (!bitmap_bit_p (executable_blocks, block->index))
443 gimple_stmt_iterator j;
444 unsigned int normal_edge_count;
445 edge e, normal_edge;
446 edge_iterator ei;
448 /* Note that we have simulated this block. */
449 bitmap_set_bit (executable_blocks, block->index);
451 for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
453 gimple stmt = gsi_stmt (j);
455 /* If this statement is already in the worklist then
456 "cancel" it. The reevaluation implied by the worklist
457 entry will produce the same value we generate here and
458 thus reevaluating it again from the worklist is
459 pointless. */
460 if (gimple_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST))
461 gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
463 simulate_stmt (stmt);
466 /* We can not predict when abnormal and EH edges will be executed, so
467 once a block is considered executable, we consider any
468 outgoing abnormal edges as executable.
470 TODO: This is not exactly true. Simplifying statement might
471 prove it non-throwing and also computed goto can be handled
472 when destination is known.
474 At the same time, if this block has only one successor that is
475 reached by non-abnormal edges, then add that successor to the
476 worklist. */
477 normal_edge_count = 0;
478 normal_edge = NULL;
479 FOR_EACH_EDGE (e, ei, block->succs)
481 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
482 add_control_edge (e);
483 else
485 normal_edge_count++;
486 normal_edge = e;
490 if (normal_edge_count == 1)
491 add_control_edge (normal_edge);
496 /* Initialize local data structures and work lists. */
498 static void
499 ssa_prop_init (void)
501 edge e;
502 edge_iterator ei;
503 basic_block bb;
505 /* Worklists of SSA edges. */
506 interesting_ssa_edges.create (20);
507 varying_ssa_edges.create (20);
509 executable_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
510 bitmap_clear (executable_blocks);
512 bb_in_list = sbitmap_alloc (last_basic_block_for_fn (cfun));
513 bitmap_clear (bb_in_list);
515 if (dump_file && (dump_flags & TDF_DETAILS))
516 dump_immediate_uses (dump_file);
518 cfg_blocks.create (20);
519 cfg_blocks.safe_grow_cleared (20);
521 /* Initially assume that every edge in the CFG is not executable.
522 (including the edges coming out of the entry block). */
523 FOR_ALL_BB_FN (bb, cfun)
525 gimple_stmt_iterator si;
527 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
528 gimple_set_plf (gsi_stmt (si), STMT_IN_SSA_EDGE_WORKLIST, false);
530 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
531 gimple_set_plf (gsi_stmt (si), STMT_IN_SSA_EDGE_WORKLIST, false);
533 FOR_EACH_EDGE (e, ei, bb->succs)
534 e->flags &= ~EDGE_EXECUTABLE;
537 /* Seed the algorithm by adding the successors of the entry block to the
538 edge worklist. */
539 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
540 add_control_edge (e);
544 /* Free allocated storage. */
546 static void
547 ssa_prop_fini (void)
549 interesting_ssa_edges.release ();
550 varying_ssa_edges.release ();
551 cfg_blocks.release ();
552 sbitmap_free (bb_in_list);
553 sbitmap_free (executable_blocks);
557 /* Return true if EXPR is an acceptable right-hand-side for a
558 GIMPLE assignment. We validate the entire tree, not just
559 the root node, thus catching expressions that embed complex
560 operands that are not permitted in GIMPLE. This function
561 is needed because the folding routines in fold-const.c
562 may return such expressions in some cases, e.g., an array
563 access with an embedded index addition. It may make more
564 sense to have folding routines that are sensitive to the
565 constraints on GIMPLE operands, rather than abandoning any
566 any attempt to fold if the usual folding turns out to be too
567 aggressive. */
569 bool
570 valid_gimple_rhs_p (tree expr)
572 enum tree_code code = TREE_CODE (expr);
574 switch (TREE_CODE_CLASS (code))
576 case tcc_declaration:
577 if (!is_gimple_variable (expr))
578 return false;
579 break;
581 case tcc_constant:
582 /* All constants are ok. */
583 break;
585 case tcc_comparison:
586 /* GENERIC allows comparisons with non-boolean types, reject
587 those for GIMPLE. Let vector-typed comparisons pass - rules
588 for GENERIC and GIMPLE are the same here. */
589 if (!(INTEGRAL_TYPE_P (TREE_TYPE (expr))
590 && (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE
591 || TYPE_PRECISION (TREE_TYPE (expr)) == 1))
592 && ! VECTOR_TYPE_P (TREE_TYPE (expr)))
593 return false;
595 /* Fallthru. */
596 case tcc_binary:
597 if (!is_gimple_val (TREE_OPERAND (expr, 0))
598 || !is_gimple_val (TREE_OPERAND (expr, 1)))
599 return false;
600 break;
602 case tcc_unary:
603 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
604 return false;
605 break;
607 case tcc_expression:
608 switch (code)
610 case ADDR_EXPR:
612 tree t;
613 if (is_gimple_min_invariant (expr))
614 return true;
615 t = TREE_OPERAND (expr, 0);
616 while (handled_component_p (t))
618 /* ??? More checks needed, see the GIMPLE verifier. */
619 if ((TREE_CODE (t) == ARRAY_REF
620 || TREE_CODE (t) == ARRAY_RANGE_REF)
621 && !is_gimple_val (TREE_OPERAND (t, 1)))
622 return false;
623 t = TREE_OPERAND (t, 0);
625 if (!is_gimple_id (t))
626 return false;
628 break;
630 default:
631 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
633 if (((code == VEC_COND_EXPR || code == COND_EXPR)
634 ? !is_gimple_condexpr (TREE_OPERAND (expr, 0))
635 : !is_gimple_val (TREE_OPERAND (expr, 0)))
636 || !is_gimple_val (TREE_OPERAND (expr, 1))
637 || !is_gimple_val (TREE_OPERAND (expr, 2)))
638 return false;
639 break;
641 return false;
643 break;
645 case tcc_vl_exp:
646 return false;
648 case tcc_exceptional:
649 if (code == CONSTRUCTOR)
651 unsigned i;
652 tree elt;
653 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (expr), i, elt)
654 if (!is_gimple_val (elt))
655 return false;
656 return true;
658 if (code != SSA_NAME)
659 return false;
660 break;
662 case tcc_reference:
663 if (code == BIT_FIELD_REF)
664 return is_gimple_val (TREE_OPERAND (expr, 0));
665 return false;
667 default:
668 return false;
671 return true;
675 /* Return true if EXPR is a CALL_EXPR suitable for representation
676 as a single GIMPLE_CALL statement. If the arguments require
677 further gimplification, return false. */
679 static bool
680 valid_gimple_call_p (tree expr)
682 unsigned i, nargs;
684 if (TREE_CODE (expr) != CALL_EXPR)
685 return false;
687 nargs = call_expr_nargs (expr);
688 for (i = 0; i < nargs; i++)
690 tree arg = CALL_EXPR_ARG (expr, i);
691 if (is_gimple_reg_type (TREE_TYPE (arg)))
693 if (!is_gimple_val (arg))
694 return false;
696 else
697 if (!is_gimple_lvalue (arg))
698 return false;
701 return true;
705 /* Make SSA names defined by OLD_STMT point to NEW_STMT
706 as their defining statement. */
708 void
709 move_ssa_defining_stmt_for_defs (gimple new_stmt, gimple old_stmt)
711 tree var;
712 ssa_op_iter iter;
714 if (gimple_in_ssa_p (cfun))
716 /* Make defined SSA_NAMEs point to the new
717 statement as their definition. */
718 FOR_EACH_SSA_TREE_OPERAND (var, old_stmt, iter, SSA_OP_ALL_DEFS)
720 if (TREE_CODE (var) == SSA_NAME)
721 SSA_NAME_DEF_STMT (var) = new_stmt;
726 /* Helper function for update_gimple_call and update_call_from_tree.
727 A GIMPLE_CALL STMT is being replaced with GIMPLE_CALL NEW_STMT. */
729 static void
730 finish_update_gimple_call (gimple_stmt_iterator *si_p, gimple new_stmt,
731 gimple stmt)
733 gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt));
734 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
735 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
736 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
737 gimple_set_location (new_stmt, gimple_location (stmt));
738 if (gimple_block (new_stmt) == NULL_TREE)
739 gimple_set_block (new_stmt, gimple_block (stmt));
740 gsi_replace (si_p, new_stmt, false);
743 /* Update a GIMPLE_CALL statement at iterator *SI_P to call to FN
744 with number of arguments NARGS, where the arguments in GIMPLE form
745 follow NARGS argument. */
747 bool
748 update_gimple_call (gimple_stmt_iterator *si_p, tree fn, int nargs, ...)
750 va_list ap;
751 gimple new_stmt, stmt = gsi_stmt (*si_p);
753 gcc_assert (is_gimple_call (stmt));
754 va_start (ap, nargs);
755 new_stmt = gimple_build_call_valist (fn, nargs, ap);
756 finish_update_gimple_call (si_p, new_stmt, stmt);
757 va_end (ap);
758 return true;
761 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
762 value of EXPR, which is expected to be the result of folding the
763 call. This can only be done if EXPR is a CALL_EXPR with valid
764 GIMPLE operands as arguments, or if it is a suitable RHS expression
765 for a GIMPLE_ASSIGN. More complex expressions will require
766 gimplification, which will introduce additional statements. In this
767 event, no update is performed, and the function returns false.
768 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
769 replace the statement at *SI_P with an entirely new statement.
770 The new statement need not be a call, e.g., if the original call
771 folded to a constant. */
773 bool
774 update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
776 gimple stmt = gsi_stmt (*si_p);
778 if (valid_gimple_call_p (expr))
780 /* The call has simplified to another call. */
781 tree fn = CALL_EXPR_FN (expr);
782 unsigned i;
783 unsigned nargs = call_expr_nargs (expr);
784 vec<tree> args = vNULL;
785 gimple new_stmt;
787 if (nargs > 0)
789 args.create (nargs);
790 args.safe_grow_cleared (nargs);
792 for (i = 0; i < nargs; i++)
793 args[i] = CALL_EXPR_ARG (expr, i);
796 new_stmt = gimple_build_call_vec (fn, args);
797 finish_update_gimple_call (si_p, new_stmt, stmt);
798 args.release ();
800 return true;
802 else if (valid_gimple_rhs_p (expr))
804 tree lhs = gimple_call_lhs (stmt);
805 gimple new_stmt;
807 /* The call has simplified to an expression
808 that cannot be represented as a GIMPLE_CALL. */
809 if (lhs)
811 /* A value is expected.
812 Introduce a new GIMPLE_ASSIGN statement. */
813 STRIP_USELESS_TYPE_CONVERSION (expr);
814 new_stmt = gimple_build_assign (lhs, expr);
815 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
816 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
817 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
819 else if (!TREE_SIDE_EFFECTS (expr))
821 /* No value is expected, and EXPR has no effect.
822 Replace it with an empty statement. */
823 new_stmt = gimple_build_nop ();
824 if (gimple_in_ssa_p (cfun))
826 unlink_stmt_vdef (stmt);
827 release_defs (stmt);
830 else
832 /* No value is expected, but EXPR has an effect,
833 e.g., it could be a reference to a volatile
834 variable. Create an assignment statement
835 with a dummy (unused) lhs variable. */
836 STRIP_USELESS_TYPE_CONVERSION (expr);
837 if (gimple_in_ssa_p (cfun))
838 lhs = make_ssa_name (TREE_TYPE (expr), NULL);
839 else
840 lhs = create_tmp_var (TREE_TYPE (expr), NULL);
841 new_stmt = gimple_build_assign (lhs, expr);
842 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
843 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
844 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
846 gimple_set_location (new_stmt, gimple_location (stmt));
847 gsi_replace (si_p, new_stmt, false);
848 return true;
850 else
851 /* The call simplified to an expression that is
852 not a valid GIMPLE RHS. */
853 return false;
857 /* Entry point to the propagation engine.
859 VISIT_STMT is called for every statement visited.
860 VISIT_PHI is called for every PHI node visited. */
862 void
863 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
864 ssa_prop_visit_phi_fn visit_phi)
866 ssa_prop_visit_stmt = visit_stmt;
867 ssa_prop_visit_phi = visit_phi;
869 ssa_prop_init ();
871 /* Iterate until the worklists are empty. */
872 while (!cfg_blocks_empty_p ()
873 || interesting_ssa_edges.length () > 0
874 || varying_ssa_edges.length () > 0)
876 if (!cfg_blocks_empty_p ())
878 /* Pull the next block to simulate off the worklist. */
879 basic_block dest_block = cfg_blocks_get ();
880 simulate_block (dest_block);
883 /* In order to move things to varying as quickly as
884 possible,process the VARYING_SSA_EDGES worklist first. */
885 process_ssa_edge_worklist (&varying_ssa_edges);
887 /* Now process the INTERESTING_SSA_EDGES worklist. */
888 process_ssa_edge_worklist (&interesting_ssa_edges);
891 ssa_prop_fini ();
895 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
896 is a non-volatile pointer dereference, a structure reference or a
897 reference to a single _DECL. Ignore volatile memory references
898 because they are not interesting for the optimizers. */
900 bool
901 stmt_makes_single_store (gimple stmt)
903 tree lhs;
905 if (gimple_code (stmt) != GIMPLE_ASSIGN
906 && gimple_code (stmt) != GIMPLE_CALL)
907 return false;
909 if (!gimple_vdef (stmt))
910 return false;
912 lhs = gimple_get_lhs (stmt);
914 /* A call statement may have a null LHS. */
915 if (!lhs)
916 return false;
918 return (!TREE_THIS_VOLATILE (lhs)
919 && (DECL_P (lhs)
920 || REFERENCE_CLASS_P (lhs)));
924 /* Propagation statistics. */
925 struct prop_stats_d
927 long num_const_prop;
928 long num_copy_prop;
929 long num_stmts_folded;
930 long num_dce;
933 static struct prop_stats_d prop_stats;
935 /* Replace USE references in statement STMT with the values stored in
936 PROP_VALUE. Return true if at least one reference was replaced. */
938 static bool
939 replace_uses_in (gimple stmt, ssa_prop_get_value_fn get_value)
941 bool replaced = false;
942 use_operand_p use;
943 ssa_op_iter iter;
945 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
947 tree tuse = USE_FROM_PTR (use);
948 tree val = (*get_value) (tuse);
950 if (val == tuse || val == NULL_TREE)
951 continue;
953 if (gimple_code (stmt) == GIMPLE_ASM
954 && !may_propagate_copy_into_asm (tuse))
955 continue;
957 if (!may_propagate_copy (tuse, val))
958 continue;
960 if (TREE_CODE (val) != SSA_NAME)
961 prop_stats.num_const_prop++;
962 else
963 prop_stats.num_copy_prop++;
965 propagate_value (use, val);
967 replaced = true;
970 return replaced;
974 /* Replace propagated values into all the arguments for PHI using the
975 values from PROP_VALUE. */
977 static bool
978 replace_phi_args_in (gimple phi, ssa_prop_get_value_fn get_value)
980 size_t i;
981 bool replaced = false;
983 if (dump_file && (dump_flags & TDF_DETAILS))
985 fprintf (dump_file, "Folding PHI node: ");
986 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
989 for (i = 0; i < gimple_phi_num_args (phi); i++)
991 tree arg = gimple_phi_arg_def (phi, i);
993 if (TREE_CODE (arg) == SSA_NAME)
995 tree val = (*get_value) (arg);
997 if (val && val != arg && may_propagate_copy (arg, val))
999 if (TREE_CODE (val) != SSA_NAME)
1000 prop_stats.num_const_prop++;
1001 else
1002 prop_stats.num_copy_prop++;
1004 propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
1005 replaced = true;
1007 /* If we propagated a copy and this argument flows
1008 through an abnormal edge, update the replacement
1009 accordingly. */
1010 if (TREE_CODE (val) == SSA_NAME
1011 && gimple_phi_arg_edge (phi, i)->flags & EDGE_ABNORMAL)
1012 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1017 if (dump_file && (dump_flags & TDF_DETAILS))
1019 if (!replaced)
1020 fprintf (dump_file, "No folding possible\n");
1021 else
1023 fprintf (dump_file, "Folded into: ");
1024 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1025 fprintf (dump_file, "\n");
1029 return replaced;
1033 class substitute_and_fold_dom_walker : public dom_walker
1035 public:
1036 substitute_and_fold_dom_walker (cdi_direction direction,
1037 ssa_prop_get_value_fn get_value_fn_,
1038 ssa_prop_fold_stmt_fn fold_fn_,
1039 bool do_dce_)
1040 : dom_walker (direction), get_value_fn (get_value_fn_),
1041 fold_fn (fold_fn_), do_dce (do_dce_), something_changed (false)
1043 stmts_to_remove.create (0);
1044 need_eh_cleanup = BITMAP_ALLOC (NULL);
1046 ~substitute_and_fold_dom_walker ()
1048 stmts_to_remove.release ();
1049 BITMAP_FREE (need_eh_cleanup);
1052 virtual void before_dom_children (basic_block);
1053 virtual void after_dom_children (basic_block) {}
1055 ssa_prop_get_value_fn get_value_fn;
1056 ssa_prop_fold_stmt_fn fold_fn;
1057 bool do_dce;
1058 bool something_changed;
1059 vec<gimple> stmts_to_remove;
1060 bitmap need_eh_cleanup;
1063 void
1064 substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
1066 gimple_stmt_iterator i;
1068 /* Propagate known values into PHI nodes. */
1069 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
1071 gimple phi = gsi_stmt (i);
1072 tree res = gimple_phi_result (phi);
1073 if (virtual_operand_p (res))
1074 continue;
1075 if (do_dce
1076 && res && TREE_CODE (res) == SSA_NAME)
1078 tree sprime = get_value_fn (res);
1079 if (sprime
1080 && sprime != res
1081 && may_propagate_copy (res, sprime))
1083 stmts_to_remove.safe_push (phi);
1084 continue;
1087 something_changed |= replace_phi_args_in (phi, get_value_fn);
1090 /* Propagate known values into stmts. In some case it exposes
1091 more trivially deletable stmts to walk backward. */
1092 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1094 bool did_replace;
1095 gimple stmt = gsi_stmt (i);
1096 gimple old_stmt;
1097 enum gimple_code code = gimple_code (stmt);
1099 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1100 range information for names and they are discarded
1101 afterwards. */
1103 if (code == GIMPLE_ASSIGN
1104 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
1105 continue;
1107 /* No point propagating into a stmt we have a value for we
1108 can propagate into all uses. Mark it for removal instead. */
1109 tree lhs = gimple_get_lhs (stmt);
1110 if (do_dce
1111 && lhs && TREE_CODE (lhs) == SSA_NAME)
1113 tree sprime = get_value_fn (lhs);
1114 if (sprime
1115 && sprime != lhs
1116 && may_propagate_copy (lhs, sprime)
1117 && !stmt_could_throw_p (stmt)
1118 && !gimple_has_side_effects (stmt))
1120 stmts_to_remove.safe_push (stmt);
1121 continue;
1125 /* Replace the statement with its folded version and mark it
1126 folded. */
1127 did_replace = false;
1128 if (dump_file && (dump_flags & TDF_DETAILS))
1130 fprintf (dump_file, "Folding statement: ");
1131 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1134 old_stmt = stmt;
1136 /* Some statements may be simplified using propagator
1137 specific information. Do this before propagating
1138 into the stmt to not disturb pass specific information. */
1139 if (fold_fn
1140 && (*fold_fn)(&i))
1142 did_replace = true;
1143 prop_stats.num_stmts_folded++;
1144 stmt = gsi_stmt (i);
1145 update_stmt (stmt);
1148 /* Replace real uses in the statement. */
1149 did_replace |= replace_uses_in (stmt, get_value_fn);
1151 /* If we made a replacement, fold the statement. */
1152 if (did_replace)
1153 fold_stmt (&i, follow_single_use_edges);
1155 /* Now cleanup. */
1156 if (did_replace)
1158 stmt = gsi_stmt (i);
1160 /* If we cleaned up EH information from the statement,
1161 remove EH edges. */
1162 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1163 bitmap_set_bit (need_eh_cleanup, bb->index);
1165 if (is_gimple_assign (stmt)
1166 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1167 == GIMPLE_SINGLE_RHS))
1169 tree rhs = gimple_assign_rhs1 (stmt);
1171 if (TREE_CODE (rhs) == ADDR_EXPR)
1172 recompute_tree_invariant_for_addr_expr (rhs);
1175 /* Determine what needs to be done to update the SSA form. */
1176 update_stmt (stmt);
1177 if (!is_gimple_debug (stmt))
1178 something_changed = true;
1181 if (dump_file && (dump_flags & TDF_DETAILS))
1183 if (did_replace)
1185 fprintf (dump_file, "Folded into: ");
1186 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1187 fprintf (dump_file, "\n");
1189 else
1190 fprintf (dump_file, "Not folded\n");
1197 /* Perform final substitution and folding of propagated values.
1199 PROP_VALUE[I] contains the single value that should be substituted
1200 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1201 substituted.
1203 If FOLD_FN is non-NULL the function will be invoked on all statements
1204 before propagating values for pass specific simplification.
1206 DO_DCE is true if trivially dead stmts can be removed.
1208 If DO_DCE is true, the statements within a BB are walked from
1209 last to first element. Otherwise we scan from first to last element.
1211 Return TRUE when something changed. */
1213 bool
1214 substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
1215 ssa_prop_fold_stmt_fn fold_fn,
1216 bool do_dce)
1218 gcc_assert (get_value_fn);
1220 if (dump_file && (dump_flags & TDF_DETAILS))
1221 fprintf (dump_file, "\nSubstituting values and folding statements\n\n");
1223 memset (&prop_stats, 0, sizeof (prop_stats));
1225 calculate_dominance_info (CDI_DOMINATORS);
1226 substitute_and_fold_dom_walker walker(CDI_DOMINATORS,
1227 get_value_fn, fold_fn, do_dce);
1228 walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1230 /* We cannot remove stmts during the BB walk, especially not release
1231 SSA names there as that destroys the lattice of our callers.
1232 Remove stmts in reverse order to make debug stmt creation possible. */
1233 while (!walker.stmts_to_remove.is_empty ())
1235 gimple stmt = walker.stmts_to_remove.pop ();
1236 if (dump_file && dump_flags & TDF_DETAILS)
1238 fprintf (dump_file, "Removing dead stmt ");
1239 print_gimple_stmt (dump_file, stmt, 0, 0);
1240 fprintf (dump_file, "\n");
1242 prop_stats.num_dce++;
1243 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1244 if (gimple_code (stmt) == GIMPLE_PHI)
1245 remove_phi_node (&gsi, true);
1246 else
1248 unlink_stmt_vdef (stmt);
1249 gsi_remove (&gsi, true);
1250 release_defs (stmt);
1254 if (!bitmap_empty_p (walker.need_eh_cleanup))
1255 gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup);
1257 statistics_counter_event (cfun, "Constants propagated",
1258 prop_stats.num_const_prop);
1259 statistics_counter_event (cfun, "Copies propagated",
1260 prop_stats.num_copy_prop);
1261 statistics_counter_event (cfun, "Statements folded",
1262 prop_stats.num_stmts_folded);
1263 statistics_counter_event (cfun, "Statements deleted",
1264 prop_stats.num_dce);
1266 return walker.something_changed;
1270 /* Return true if we may propagate ORIG into DEST, false otherwise. */
1272 bool
1273 may_propagate_copy (tree dest, tree orig)
1275 tree type_d = TREE_TYPE (dest);
1276 tree type_o = TREE_TYPE (orig);
1278 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */
1279 if (TREE_CODE (orig) == SSA_NAME
1280 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)
1281 /* If it is the default definition and an automatic variable then
1282 we can though and it is important that we do to avoid
1283 uninitialized regular copies. */
1284 && !(SSA_NAME_IS_DEFAULT_DEF (orig)
1285 && (SSA_NAME_VAR (orig) == NULL_TREE
1286 || TREE_CODE (SSA_NAME_VAR (orig)) == VAR_DECL)))
1287 return false;
1289 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
1290 cannot be replaced. */
1291 if (TREE_CODE (dest) == SSA_NAME
1292 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
1293 return false;
1295 /* Do not copy between types for which we *do* need a conversion. */
1296 if (!useless_type_conversion_p (type_d, type_o))
1297 return false;
1299 /* Generally propagating virtual operands is not ok as that may
1300 create overlapping life-ranges. */
1301 if (TREE_CODE (dest) == SSA_NAME && virtual_operand_p (dest))
1302 return false;
1304 /* Anything else is OK. */
1305 return true;
1308 /* Like may_propagate_copy, but use as the destination expression
1309 the principal expression (typically, the RHS) contained in
1310 statement DEST. This is more efficient when working with the
1311 gimple tuples representation. */
1313 bool
1314 may_propagate_copy_into_stmt (gimple dest, tree orig)
1316 tree type_d;
1317 tree type_o;
1319 /* If the statement is a switch or a single-rhs assignment,
1320 then the expression to be replaced by the propagation may
1321 be an SSA_NAME. Fortunately, there is an explicit tree
1322 for the expression, so we delegate to may_propagate_copy. */
1324 if (gimple_assign_single_p (dest))
1325 return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
1326 else if (gimple_code (dest) == GIMPLE_SWITCH)
1327 return may_propagate_copy (gimple_switch_index (dest), orig);
1329 /* In other cases, the expression is not materialized, so there
1330 is no destination to pass to may_propagate_copy. On the other
1331 hand, the expression cannot be an SSA_NAME, so the analysis
1332 is much simpler. */
1334 if (TREE_CODE (orig) == SSA_NAME
1335 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
1336 return false;
1338 if (is_gimple_assign (dest))
1339 type_d = TREE_TYPE (gimple_assign_lhs (dest));
1340 else if (gimple_code (dest) == GIMPLE_COND)
1341 type_d = boolean_type_node;
1342 else if (is_gimple_call (dest)
1343 && gimple_call_lhs (dest) != NULL_TREE)
1344 type_d = TREE_TYPE (gimple_call_lhs (dest));
1345 else
1346 gcc_unreachable ();
1348 type_o = TREE_TYPE (orig);
1350 if (!useless_type_conversion_p (type_d, type_o))
1351 return false;
1353 return true;
1356 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
1358 bool
1359 may_propagate_copy_into_asm (tree dest ATTRIBUTE_UNUSED)
1361 return true;
1365 /* Common code for propagate_value and replace_exp.
1367 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
1368 replacement is done to propagate a value or not. */
1370 static void
1371 replace_exp_1 (use_operand_p op_p, tree val,
1372 bool for_propagation ATTRIBUTE_UNUSED)
1374 #if defined ENABLE_CHECKING
1375 tree op = USE_FROM_PTR (op_p);
1377 gcc_assert (!(for_propagation
1378 && TREE_CODE (op) == SSA_NAME
1379 && TREE_CODE (val) == SSA_NAME
1380 && !may_propagate_copy (op, val)));
1381 #endif
1383 if (TREE_CODE (val) == SSA_NAME)
1384 SET_USE (op_p, val);
1385 else
1386 SET_USE (op_p, unshare_expr (val));
1390 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1391 into the operand pointed to by OP_P.
1393 Use this version for const/copy propagation as it will perform additional
1394 checks to ensure validity of the const/copy propagation. */
1396 void
1397 propagate_value (use_operand_p op_p, tree val)
1399 replace_exp_1 (op_p, val, true);
1402 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
1404 Use this version when not const/copy propagating values. For example,
1405 PRE uses this version when building expressions as they would appear
1406 in specific blocks taking into account actions of PHI nodes.
1408 The statement in which an expression has been replaced should be
1409 folded using fold_stmt_inplace. */
1411 void
1412 replace_exp (use_operand_p op_p, tree val)
1414 replace_exp_1 (op_p, val, false);
1418 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
1419 into the tree pointed to by OP_P.
1421 Use this version for const/copy propagation when SSA operands are not
1422 available. It will perform the additional checks to ensure validity of
1423 the const/copy propagation, but will not update any operand information.
1424 Be sure to mark the stmt as modified. */
1426 void
1427 propagate_tree_value (tree *op_p, tree val)
1429 if (TREE_CODE (val) == SSA_NAME)
1430 *op_p = val;
1431 else
1432 *op_p = unshare_expr (val);
1436 /* Like propagate_tree_value, but use as the operand to replace
1437 the principal expression (typically, the RHS) contained in the
1438 statement referenced by iterator GSI. Note that it is not
1439 always possible to update the statement in-place, so a new
1440 statement may be created to replace the original. */
1442 void
1443 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
1445 gimple stmt = gsi_stmt (*gsi);
1447 if (is_gimple_assign (stmt))
1449 tree expr = NULL_TREE;
1450 if (gimple_assign_single_p (stmt))
1451 expr = gimple_assign_rhs1 (stmt);
1452 propagate_tree_value (&expr, val);
1453 gimple_assign_set_rhs_from_tree (gsi, expr);
1455 else if (gimple_code (stmt) == GIMPLE_COND)
1457 tree lhs = NULL_TREE;
1458 tree rhs = build_zero_cst (TREE_TYPE (val));
1459 propagate_tree_value (&lhs, val);
1460 gimple_cond_set_code (stmt, NE_EXPR);
1461 gimple_cond_set_lhs (stmt, lhs);
1462 gimple_cond_set_rhs (stmt, rhs);
1464 else if (is_gimple_call (stmt)
1465 && gimple_call_lhs (stmt) != NULL_TREE)
1467 tree expr = NULL_TREE;
1468 bool res;
1469 propagate_tree_value (&expr, val);
1470 res = update_call_from_tree (gsi, expr);
1471 gcc_assert (res);
1473 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1474 propagate_tree_value (gimple_switch_index_ptr (stmt), val);
1475 else
1476 gcc_unreachable ();