tree-vrp.c (simplify_using_ranges): Kill.
[gcc.git] / gcc / tree-ssa-propagate.c
1 /* Generic SSA value propagation engine.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
10 later version.
11
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.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "ggc.h"
31 #include "basic-block.h"
32 #include "output.h"
33 #include "expr.h"
34 #include "function.h"
35 #include "diagnostic.h"
36 #include "timevar.h"
37 #include "tree-dump.h"
38 #include "tree-flow.h"
39 #include "tree-pass.h"
40 #include "tree-ssa-propagate.h"
41 #include "langhooks.h"
42 #include "varray.h"
43 #include "vec.h"
44
45 /* This file implements a generic value propagation engine based on
46 the same propagation used by the SSA-CCP algorithm [1].
47
48 Propagation is performed by simulating the execution of every
49 statement that produces the value being propagated. Simulation
50 proceeds as follows:
51
52 1- Initially, all edges of the CFG are marked not executable and
53 the CFG worklist is seeded with all the statements in the entry
54 basic block (block 0).
55
56 2- Every statement S is simulated with a call to the call-back
57 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
58 results:
59
60 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
61 interest and does not affect any of the work lists.
62
63 SSA_PROP_VARYING: The value produced by S cannot be determined
64 at compile time. Further simulation of S is not required.
65 If S is a conditional jump, all the outgoing edges for the
66 block are considered executable and added to the work
67 list.
68
69 SSA_PROP_INTERESTING: S produces a value that can be computed
70 at compile time. Its result can be propagated into the
71 statements that feed from S. Furthermore, if S is a
72 conditional jump, only the edge known to be taken is added
73 to the work list. Edges that are known not to execute are
74 never simulated.
75
76 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
77 return value from SSA_PROP_VISIT_PHI has the same semantics as
78 described in #2.
79
80 4- Three work lists are kept. Statements are only added to these
81 lists if they produce one of SSA_PROP_INTERESTING or
82 SSA_PROP_VARYING.
83
84 CFG_BLOCKS contains the list of blocks to be simulated.
85 Blocks are added to this list if their incoming edges are
86 found executable.
87
88 VARYING_SSA_EDGES contains the list of statements that feed
89 from statements that produce an SSA_PROP_VARYING result.
90 These are simulated first to speed up processing.
91
92 INTERESTING_SSA_EDGES contains the list of statements that
93 feed from statements that produce an SSA_PROP_INTERESTING
94 result.
95
96 5- Simulation terminates when all three work lists are drained.
97
98 Before calling ssa_propagate, it is important to clear
99 DONT_SIMULATE_AGAIN for all the statements in the program that
100 should be simulated. This initialization allows an implementation
101 to specify which statements should never be simulated.
102
103 It is also important to compute def-use information before calling
104 ssa_propagate.
105
106 References:
107
108 [1] Constant propagation with conditional branches,
109 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
110
111 [2] Building an Optimizing Compiler,
112 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
113
114 [3] Advanced Compiler Design and Implementation,
115 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
116
117 /* Function pointers used to parameterize the propagation engine. */
118 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
119 static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
120
121 /* Use the TREE_DEPRECATED bitflag to mark statements that have been
122 added to one of the SSA edges worklists. This flag is used to
123 avoid visiting statements unnecessarily when draining an SSA edge
124 worklist. If while simulating a basic block, we find a statement with
125 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
126 processing from visiting it again. */
127 #define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
128
129 /* A bitmap to keep track of executable blocks in the CFG. */
130 static sbitmap executable_blocks;
131
132 /* Array of control flow edges on the worklist. */
133 static GTY(()) varray_type cfg_blocks = NULL;
134
135 static unsigned int cfg_blocks_num = 0;
136 static int cfg_blocks_tail;
137 static int cfg_blocks_head;
138
139 static sbitmap bb_in_list;
140
141 /* Worklist of SSA edges which will need reexamination as their
142 definition has changed. SSA edges are def-use edges in the SSA
143 web. For each D-U edge, we store the target statement or PHI node
144 U. */
145 static GTY(()) VEC(tree,gc) *interesting_ssa_edges;
146
147 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
148 list of SSA edges is split into two. One contains all SSA edges
149 who need to be reexamined because their lattice value changed to
150 varying (this worklist), and the other contains all other SSA edges
151 to be reexamined (INTERESTING_SSA_EDGES).
152
153 Since most values in the program are VARYING, the ideal situation
154 is to move them to that lattice value as quickly as possible.
155 Thus, it doesn't make sense to process any other type of lattice
156 value until all VARYING values are propagated fully, which is one
157 thing using the VARYING worklist achieves. In addition, if we
158 don't use a separate worklist for VARYING edges, we end up with
159 situations where lattice values move from
160 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
161 static GTY(()) VEC(tree,gc) *varying_ssa_edges;
162
163
164 /* Return true if the block worklist empty. */
165
166 static inline bool
167 cfg_blocks_empty_p (void)
168 {
169 return (cfg_blocks_num == 0);
170 }
171
172
173 /* Add a basic block to the worklist. The block must not be already
174 in the worklist, and it must not be the ENTRY or EXIT block. */
175
176 static void
177 cfg_blocks_add (basic_block bb)
178 {
179 gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
180 gcc_assert (!TEST_BIT (bb_in_list, bb->index));
181
182 if (cfg_blocks_empty_p ())
183 {
184 cfg_blocks_tail = cfg_blocks_head = 0;
185 cfg_blocks_num = 1;
186 }
187 else
188 {
189 cfg_blocks_num++;
190 if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
191 {
192 /* We have to grow the array now. Adjust to queue to occupy the
193 full space of the original array. */
194 cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
195 cfg_blocks_head = 0;
196 VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
197 }
198 else
199 cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
200 }
201
202 VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
203 SET_BIT (bb_in_list, bb->index);
204 }
205
206
207 /* Remove a block from the worklist. */
208
209 static basic_block
210 cfg_blocks_get (void)
211 {
212 basic_block bb;
213
214 bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
215
216 gcc_assert (!cfg_blocks_empty_p ());
217 gcc_assert (bb);
218
219 cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
220 --cfg_blocks_num;
221 RESET_BIT (bb_in_list, bb->index);
222
223 return bb;
224 }
225
226
227 /* We have just defined a new value for VAR. If IS_VARYING is true,
228 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
229 them to INTERESTING_SSA_EDGES. */
230
231 static void
232 add_ssa_edge (tree var, bool is_varying)
233 {
234 imm_use_iterator iter;
235 use_operand_p use_p;
236
237 FOR_EACH_IMM_USE_FAST (use_p, iter, var)
238 {
239 tree use_stmt = USE_STMT (use_p);
240
241 if (!DONT_SIMULATE_AGAIN (use_stmt)
242 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt))
243 {
244 STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
245 if (is_varying)
246 VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt);
247 else
248 VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt);
249 }
250 }
251 }
252
253
254 /* Add edge E to the control flow worklist. */
255
256 static void
257 add_control_edge (edge e)
258 {
259 basic_block bb = e->dest;
260 if (bb == EXIT_BLOCK_PTR)
261 return;
262
263 /* If the edge had already been executed, skip it. */
264 if (e->flags & EDGE_EXECUTABLE)
265 return;
266
267 e->flags |= EDGE_EXECUTABLE;
268
269 /* If the block is already in the list, we're done. */
270 if (TEST_BIT (bb_in_list, bb->index))
271 return;
272
273 cfg_blocks_add (bb);
274
275 if (dump_file && (dump_flags & TDF_DETAILS))
276 fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
277 e->src->index, e->dest->index);
278 }
279
280
281 /* Simulate the execution of STMT and update the work lists accordingly. */
282
283 static void
284 simulate_stmt (tree stmt)
285 {
286 enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
287 edge taken_edge = NULL;
288 tree output_name = NULL_TREE;
289
290 /* Don't bother visiting statements that are already
291 considered varying by the propagator. */
292 if (DONT_SIMULATE_AGAIN (stmt))
293 return;
294
295 if (TREE_CODE (stmt) == PHI_NODE)
296 {
297 val = ssa_prop_visit_phi (stmt);
298 output_name = PHI_RESULT (stmt);
299 }
300 else
301 val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
302
303 if (val == SSA_PROP_VARYING)
304 {
305 DONT_SIMULATE_AGAIN (stmt) = 1;
306
307 /* If the statement produced a new varying value, add the SSA
308 edges coming out of OUTPUT_NAME. */
309 if (output_name)
310 add_ssa_edge (output_name, true);
311
312 /* If STMT transfers control out of its basic block, add
313 all outgoing edges to the work list. */
314 if (stmt_ends_bb_p (stmt))
315 {
316 edge e;
317 edge_iterator ei;
318 basic_block bb = bb_for_stmt (stmt);
319 FOR_EACH_EDGE (e, ei, bb->succs)
320 add_control_edge (e);
321 }
322 }
323 else if (val == SSA_PROP_INTERESTING)
324 {
325 /* If the statement produced new value, add the SSA edges coming
326 out of OUTPUT_NAME. */
327 if (output_name)
328 add_ssa_edge (output_name, false);
329
330 /* If we know which edge is going to be taken out of this block,
331 add it to the CFG work list. */
332 if (taken_edge)
333 add_control_edge (taken_edge);
334 }
335 }
336
337 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
338 drain. This pops statements off the given WORKLIST and processes
339 them until there are no more statements on WORKLIST.
340 We take a pointer to WORKLIST because it may be reallocated when an
341 SSA edge is added to it in simulate_stmt. */
342
343 static void
344 process_ssa_edge_worklist (VEC(tree,gc) **worklist)
345 {
346 /* Drain the entire worklist. */
347 while (VEC_length (tree, *worklist) > 0)
348 {
349 basic_block bb;
350
351 /* Pull the statement to simulate off the worklist. */
352 tree stmt = VEC_pop (tree, *worklist);
353
354 /* If this statement was already visited by simulate_block, then
355 we don't need to visit it again here. */
356 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt))
357 continue;
358
359 /* STMT is no longer in a worklist. */
360 STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
361
362 if (dump_file && (dump_flags & TDF_DETAILS))
363 {
364 fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
365 print_generic_stmt (dump_file, stmt, dump_flags);
366 }
367
368 bb = bb_for_stmt (stmt);
369
370 /* PHI nodes are always visited, regardless of whether or not
371 the destination block is executable. Otherwise, visit the
372 statement only if its block is marked executable. */
373 if (TREE_CODE (stmt) == PHI_NODE
374 || TEST_BIT (executable_blocks, bb->index))
375 simulate_stmt (stmt);
376 }
377 }
378
379
380 /* Simulate the execution of BLOCK. Evaluate the statement associated
381 with each variable reference inside the block. */
382
383 static void
384 simulate_block (basic_block block)
385 {
386 tree phi;
387
388 /* There is nothing to do for the exit block. */
389 if (block == EXIT_BLOCK_PTR)
390 return;
391
392 if (dump_file && (dump_flags & TDF_DETAILS))
393 fprintf (dump_file, "\nSimulating block %d\n", block->index);
394
395 /* Always simulate PHI nodes, even if we have simulated this block
396 before. */
397 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
398 simulate_stmt (phi);
399
400 /* If this is the first time we've simulated this block, then we
401 must simulate each of its statements. */
402 if (!TEST_BIT (executable_blocks, block->index))
403 {
404 block_stmt_iterator j;
405 unsigned int normal_edge_count;
406 edge e, normal_edge;
407 edge_iterator ei;
408
409 /* Note that we have simulated this block. */
410 SET_BIT (executable_blocks, block->index);
411
412 for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
413 {
414 tree stmt = bsi_stmt (j);
415
416 /* If this statement is already in the worklist then
417 "cancel" it. The reevaluation implied by the worklist
418 entry will produce the same value we generate here and
419 thus reevaluating it again from the worklist is
420 pointless. */
421 if (STMT_IN_SSA_EDGE_WORKLIST (stmt))
422 STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
423
424 simulate_stmt (stmt);
425 }
426
427 /* We can not predict when abnormal edges will be executed, so
428 once a block is considered executable, we consider any
429 outgoing abnormal edges as executable.
430
431 At the same time, if this block has only one successor that is
432 reached by non-abnormal edges, then add that successor to the
433 worklist. */
434 normal_edge_count = 0;
435 normal_edge = NULL;
436 FOR_EACH_EDGE (e, ei, block->succs)
437 {
438 if (e->flags & EDGE_ABNORMAL)
439 add_control_edge (e);
440 else
441 {
442 normal_edge_count++;
443 normal_edge = e;
444 }
445 }
446
447 if (normal_edge_count == 1)
448 add_control_edge (normal_edge);
449 }
450 }
451
452
453 /* Initialize local data structures and work lists. */
454
455 static void
456 ssa_prop_init (void)
457 {
458 edge e;
459 edge_iterator ei;
460 basic_block bb;
461 size_t i;
462
463 /* Worklists of SSA edges. */
464 interesting_ssa_edges = VEC_alloc (tree, gc, 20);
465 varying_ssa_edges = VEC_alloc (tree, gc, 20);
466
467 executable_blocks = sbitmap_alloc (last_basic_block);
468 sbitmap_zero (executable_blocks);
469
470 bb_in_list = sbitmap_alloc (last_basic_block);
471 sbitmap_zero (bb_in_list);
472
473 if (dump_file && (dump_flags & TDF_DETAILS))
474 dump_immediate_uses (dump_file);
475
476 VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
477
478 /* Initialize the values for every SSA_NAME. */
479 for (i = 1; i < num_ssa_names; i++)
480 if (ssa_name (i))
481 SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE;
482
483 /* Initially assume that every edge in the CFG is not executable.
484 (including the edges coming out of ENTRY_BLOCK_PTR). */
485 FOR_ALL_BB (bb)
486 {
487 block_stmt_iterator si;
488
489 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
490 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
491
492 FOR_EACH_EDGE (e, ei, bb->succs)
493 e->flags &= ~EDGE_EXECUTABLE;
494 }
495
496 /* Seed the algorithm by adding the successors of the entry block to the
497 edge worklist. */
498 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
499 add_control_edge (e);
500 }
501
502
503 /* Free allocated storage. */
504
505 static void
506 ssa_prop_fini (void)
507 {
508 VEC_free (tree, gc, interesting_ssa_edges);
509 VEC_free (tree, gc, varying_ssa_edges);
510 cfg_blocks = NULL;
511 sbitmap_free (bb_in_list);
512 sbitmap_free (executable_blocks);
513 }
514
515
516 /* Get the main expression from statement STMT. */
517
518 tree
519 get_rhs (tree stmt)
520 {
521 enum tree_code code = TREE_CODE (stmt);
522
523 switch (code)
524 {
525 case RETURN_EXPR:
526 stmt = TREE_OPERAND (stmt, 0);
527 if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
528 return stmt;
529 /* FALLTHRU */
530
531 case MODIFY_EXPR:
532 stmt = TREE_OPERAND (stmt, 1);
533 if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
534 return TREE_OPERAND (stmt, 0);
535 else
536 return stmt;
537
538 case COND_EXPR:
539 return COND_EXPR_COND (stmt);
540 case SWITCH_EXPR:
541 return SWITCH_COND (stmt);
542 case GOTO_EXPR:
543 return GOTO_DESTINATION (stmt);
544 case LABEL_EXPR:
545 return LABEL_EXPR_LABEL (stmt);
546
547 default:
548 return stmt;
549 }
550 }
551
552
553 /* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
554 GIMPLE expression no changes are done and the function returns
555 false. */
556
557 bool
558 set_rhs (tree *stmt_p, tree expr)
559 {
560 tree stmt = *stmt_p, op;
561 enum tree_code code = TREE_CODE (expr);
562 stmt_ann_t ann;
563 tree var;
564 ssa_op_iter iter;
565
566 /* Verify the constant folded result is valid gimple. */
567 if (TREE_CODE_CLASS (code) == tcc_binary)
568 {
569 if (!is_gimple_val (TREE_OPERAND (expr, 0))
570 || !is_gimple_val (TREE_OPERAND (expr, 1)))
571 return false;
572 }
573 else if (TREE_CODE_CLASS (code) == tcc_unary)
574 {
575 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
576 return false;
577 }
578 else if (code == ADDR_EXPR)
579 {
580 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF
581 && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1)))
582 return false;
583 }
584 else if (code == COMPOUND_EXPR)
585 return false;
586
587 switch (TREE_CODE (stmt))
588 {
589 case RETURN_EXPR:
590 op = TREE_OPERAND (stmt, 0);
591 if (TREE_CODE (op) != MODIFY_EXPR)
592 {
593 TREE_OPERAND (stmt, 0) = expr;
594 break;
595 }
596 stmt = op;
597 /* FALLTHRU */
598
599 case MODIFY_EXPR:
600 op = TREE_OPERAND (stmt, 1);
601 if (TREE_CODE (op) == WITH_SIZE_EXPR)
602 stmt = op;
603 TREE_OPERAND (stmt, 1) = expr;
604 break;
605
606 case COND_EXPR:
607 COND_EXPR_COND (stmt) = expr;
608 break;
609 case SWITCH_EXPR:
610 SWITCH_COND (stmt) = expr;
611 break;
612 case GOTO_EXPR:
613 GOTO_DESTINATION (stmt) = expr;
614 break;
615 case LABEL_EXPR:
616 LABEL_EXPR_LABEL (stmt) = expr;
617 break;
618
619 default:
620 /* Replace the whole statement with EXPR. If EXPR has no side
621 effects, then replace *STMT_P with an empty statement. */
622 ann = stmt_ann (stmt);
623 *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
624 (*stmt_p)->common.ann = (tree_ann_t) ann;
625
626 if (TREE_SIDE_EFFECTS (expr))
627 {
628 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
629 replacement. */
630 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
631 {
632 if (TREE_CODE (var) == SSA_NAME)
633 SSA_NAME_DEF_STMT (var) = *stmt_p;
634 }
635 }
636 break;
637 }
638
639 return true;
640 }
641
642
643 /* Entry point to the propagation engine.
644
645 VISIT_STMT is called for every statement visited.
646 VISIT_PHI is called for every PHI node visited. */
647
648 void
649 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
650 ssa_prop_visit_phi_fn visit_phi)
651 {
652 ssa_prop_visit_stmt = visit_stmt;
653 ssa_prop_visit_phi = visit_phi;
654
655 ssa_prop_init ();
656
657 /* Iterate until the worklists are empty. */
658 while (!cfg_blocks_empty_p ()
659 || VEC_length (tree, interesting_ssa_edges) > 0
660 || VEC_length (tree, varying_ssa_edges) > 0)
661 {
662 if (!cfg_blocks_empty_p ())
663 {
664 /* Pull the next block to simulate off the worklist. */
665 basic_block dest_block = cfg_blocks_get ();
666 simulate_block (dest_block);
667 }
668
669 /* In order to move things to varying as quickly as
670 possible,process the VARYING_SSA_EDGES worklist first. */
671 process_ssa_edge_worklist (&varying_ssa_edges);
672
673 /* Now process the INTERESTING_SSA_EDGES worklist. */
674 process_ssa_edge_worklist (&interesting_ssa_edges);
675 }
676
677 ssa_prop_fini ();
678 }
679
680
681 /* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */
682
683 tree
684 first_vdef (tree stmt)
685 {
686 ssa_op_iter iter;
687 tree op;
688
689 /* Simply return the first operand we arrive at. */
690 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
691 return (op);
692
693 gcc_unreachable ();
694 }
695
696
697 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
698 is a non-volatile pointer dereference, a structure reference or a
699 reference to a single _DECL. Ignore volatile memory references
700 because they are not interesting for the optimizers. */
701
702 bool
703 stmt_makes_single_load (tree stmt)
704 {
705 tree rhs;
706
707 if (TREE_CODE (stmt) != MODIFY_EXPR)
708 return false;
709
710 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE))
711 return false;
712
713 rhs = TREE_OPERAND (stmt, 1);
714 STRIP_NOPS (rhs);
715
716 return (!TREE_THIS_VOLATILE (rhs)
717 && (DECL_P (rhs)
718 || REFERENCE_CLASS_P (rhs)));
719 }
720
721
722 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
723 is a non-volatile pointer dereference, a structure reference or a
724 reference to a single _DECL. Ignore volatile memory references
725 because they are not interesting for the optimizers. */
726
727 bool
728 stmt_makes_single_store (tree stmt)
729 {
730 tree lhs;
731
732 if (TREE_CODE (stmt) != MODIFY_EXPR)
733 return false;
734
735 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
736 return false;
737
738 lhs = TREE_OPERAND (stmt, 0);
739 STRIP_NOPS (lhs);
740
741 return (!TREE_THIS_VOLATILE (lhs)
742 && (DECL_P (lhs)
743 || REFERENCE_CLASS_P (lhs)));
744 }
745
746
747 /* If STMT makes a single memory load and all the virtual use operands
748 have the same value in array VALUES, return it. Otherwise, return
749 NULL. */
750
751 prop_value_t *
752 get_value_loaded_by (tree stmt, prop_value_t *values)
753 {
754 ssa_op_iter i;
755 tree vuse;
756 prop_value_t *prev_val = NULL;
757 prop_value_t *val = NULL;
758
759 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
760 {
761 val = &values[SSA_NAME_VERSION (vuse)];
762 if (prev_val && prev_val->value != val->value)
763 return NULL;
764 prev_val = val;
765 }
766
767 return val;
768 }
769
770
771 /* Propagation statistics. */
772 struct prop_stats_d
773 {
774 long num_const_prop;
775 long num_copy_prop;
776 long num_pred_folded;
777 };
778
779 static struct prop_stats_d prop_stats;
780
781 /* Replace USE references in statement STMT with the values stored in
782 PROP_VALUE. Return true if at least one reference was replaced. If
783 REPLACED_ADDRESSES_P is given, it will be set to true if an address
784 constant was replaced. */
785
786 bool
787 replace_uses_in (tree stmt, bool *replaced_addresses_p,
788 prop_value_t *prop_value)
789 {
790 bool replaced = false;
791 use_operand_p use;
792 ssa_op_iter iter;
793
794 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
795 {
796 tree tuse = USE_FROM_PTR (use);
797 tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
798
799 if (val == tuse || val == NULL_TREE)
800 continue;
801
802 if (TREE_CODE (stmt) == ASM_EXPR
803 && !may_propagate_copy_into_asm (tuse))
804 continue;
805
806 if (!may_propagate_copy (tuse, val))
807 continue;
808
809 if (TREE_CODE (val) != SSA_NAME)
810 prop_stats.num_const_prop++;
811 else
812 prop_stats.num_copy_prop++;
813
814 propagate_value (use, val);
815
816 replaced = true;
817 if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
818 *replaced_addresses_p = true;
819 }
820
821 return replaced;
822 }
823
824
825 /* Replace the VUSE references in statement STMT with the values
826 stored in PROP_VALUE. Return true if a reference was replaced. If
827 REPLACED_ADDRESSES_P is given, it will be set to true if an address
828 constant was replaced.
829
830 Replacing VUSE operands is slightly more complex than replacing
831 regular USEs. We are only interested in two types of replacements
832 here:
833
834 1- If the value to be replaced is a constant or an SSA name for a
835 GIMPLE register, then we are making a copy/constant propagation
836 from a memory store. For instance,
837
838 # a_3 = V_MAY_DEF <a_2>
839 a.b = x_1;
840 ...
841 # VUSE <a_3>
842 y_4 = a.b;
843
844 This replacement is only possible iff STMT is an assignment
845 whose RHS is identical to the LHS of the statement that created
846 the VUSE(s) that we are replacing. Otherwise, we may do the
847 wrong replacement:
848
849 # a_3 = V_MAY_DEF <a_2>
850 # b_5 = V_MAY_DEF <b_4>
851 *p = 10;
852 ...
853 # VUSE <b_5>
854 x_8 = b;
855
856 Even though 'b_5' acquires the value '10' during propagation,
857 there is no way for the propagator to tell whether the
858 replacement is correct in every reached use, because values are
859 computed at definition sites. Therefore, when doing final
860 substitution of propagated values, we have to check each use
861 site. Since the RHS of STMT ('b') is different from the LHS of
862 the originating statement ('*p'), we cannot replace 'b' with
863 '10'.
864
865 Similarly, when merging values from PHI node arguments,
866 propagators need to take care not to merge the same values
867 stored in different locations:
868
869 if (...)
870 # a_3 = V_MAY_DEF <a_2>
871 a.b = 3;
872 else
873 # a_4 = V_MAY_DEF <a_2>
874 a.c = 3;
875 # a_5 = PHI <a_3, a_4>
876
877 It would be wrong to propagate '3' into 'a_5' because that
878 operation merges two stores to different memory locations.
879
880
881 2- If the value to be replaced is an SSA name for a virtual
882 register, then we simply replace each VUSE operand with its
883 value from PROP_VALUE. This is the same replacement done by
884 replace_uses_in. */
885
886 static bool
887 replace_vuses_in (tree stmt, bool *replaced_addresses_p,
888 prop_value_t *prop_value)
889 {
890 bool replaced = false;
891 ssa_op_iter iter;
892 use_operand_p vuse;
893
894 if (stmt_makes_single_load (stmt))
895 {
896 /* If STMT is an assignment whose RHS is a single memory load,
897 see if we are trying to propagate a constant or a GIMPLE
898 register (case #1 above). */
899 prop_value_t *val = get_value_loaded_by (stmt, prop_value);
900 tree rhs = TREE_OPERAND (stmt, 1);
901
902 if (val
903 && val->value
904 && (is_gimple_reg (val->value)
905 || is_gimple_min_invariant (val->value))
906 && simple_cst_equal (rhs, val->mem_ref) == 1)
907
908 {
909 /* If we are replacing a constant address, inform our
910 caller. */
911 if (TREE_CODE (val->value) != SSA_NAME
912 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
913 && replaced_addresses_p)
914 *replaced_addresses_p = true;
915
916 /* We can only perform the substitution if the load is done
917 from the same memory location as the original store.
918 Since we already know that there are no intervening
919 stores between DEF_STMT and STMT, we only need to check
920 that the RHS of STMT is the same as the memory reference
921 propagated together with the value. */
922 TREE_OPERAND (stmt, 1) = val->value;
923
924 if (TREE_CODE (val->value) != SSA_NAME)
925 prop_stats.num_const_prop++;
926 else
927 prop_stats.num_copy_prop++;
928
929 /* Since we have replaced the whole RHS of STMT, there
930 is no point in checking the other VUSEs, as they will
931 all have the same value. */
932 return true;
933 }
934 }
935
936 /* Otherwise, the values for every VUSE operand must be other
937 SSA_NAMEs that can be propagated into STMT. */
938 FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
939 {
940 tree var = USE_FROM_PTR (vuse);
941 tree val = prop_value[SSA_NAME_VERSION (var)].value;
942
943 if (val == NULL_TREE || var == val)
944 continue;
945
946 /* Constants and copies propagated between real and virtual
947 operands are only possible in the cases handled above. They
948 should be ignored in any other context. */
949 if (is_gimple_min_invariant (val) || is_gimple_reg (val))
950 continue;
951
952 propagate_value (vuse, val);
953 prop_stats.num_copy_prop++;
954 replaced = true;
955 }
956
957 return replaced;
958 }
959
960
961 /* Replace propagated values into all the arguments for PHI using the
962 values from PROP_VALUE. */
963
964 static void
965 replace_phi_args_in (tree phi, prop_value_t *prop_value)
966 {
967 int i;
968 bool replaced = false;
969 tree prev_phi = NULL;
970
971 if (dump_file && (dump_flags & TDF_DETAILS))
972 prev_phi = unshare_expr (phi);
973
974 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
975 {
976 tree arg = PHI_ARG_DEF (phi, i);
977
978 if (TREE_CODE (arg) == SSA_NAME)
979 {
980 tree val = prop_value[SSA_NAME_VERSION (arg)].value;
981
982 if (val && val != arg && may_propagate_copy (arg, val))
983 {
984 if (TREE_CODE (val) != SSA_NAME)
985 prop_stats.num_const_prop++;
986 else
987 prop_stats.num_copy_prop++;
988
989 propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
990 replaced = true;
991
992 /* If we propagated a copy and this argument flows
993 through an abnormal edge, update the replacement
994 accordingly. */
995 if (TREE_CODE (val) == SSA_NAME
996 && PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
997 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
998 }
999 }
1000 }
1001
1002 if (replaced && dump_file && (dump_flags & TDF_DETAILS))
1003 {
1004 fprintf (dump_file, "Folded PHI node: ");
1005 print_generic_stmt (dump_file, prev_phi, TDF_SLIM);
1006 fprintf (dump_file, " into: ");
1007 print_generic_stmt (dump_file, phi, TDF_SLIM);
1008 fprintf (dump_file, "\n");
1009 }
1010 }
1011
1012
1013 /* If STMT has a predicate whose value can be computed using the value
1014 range information computed by VRP, compute its value and return true.
1015 Otherwise, return false. */
1016
1017 static bool
1018 fold_predicate_in (tree stmt)
1019 {
1020 tree *pred_p = NULL;
1021 tree val;
1022
1023 if (TREE_CODE (stmt) == MODIFY_EXPR
1024 && COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1)))
1025 pred_p = &TREE_OPERAND (stmt, 1);
1026 else if (TREE_CODE (stmt) == COND_EXPR)
1027 pred_p = &COND_EXPR_COND (stmt);
1028 else
1029 return false;
1030
1031 val = vrp_evaluate_conditional (*pred_p, true);
1032 if (val)
1033 {
1034 if (dump_file)
1035 {
1036 fprintf (dump_file, "Folding predicate ");
1037 print_generic_expr (dump_file, *pred_p, 0);
1038 fprintf (dump_file, " to ");
1039 print_generic_expr (dump_file, val, 0);
1040 fprintf (dump_file, "\n");
1041 }
1042
1043 prop_stats.num_pred_folded++;
1044 *pred_p = val;
1045 return true;
1046 }
1047
1048 return false;
1049 }
1050
1051
1052 /* Perform final substitution and folding of propagated values.
1053
1054 PROP_VALUE[I] contains the single value that should be substituted
1055 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
1056 substituted.
1057
1058 If USE_RANGES_P is true, statements that contain predicate
1059 expressions are evaluated with a call to vrp_evaluate_conditional.
1060 This will only give meaningful results when called from tree-vrp.c
1061 (the information used by vrp_evaluate_conditional is built by the
1062 VRP pass). */
1063
1064 void
1065 substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
1066 {
1067 basic_block bb;
1068
1069 if (prop_value == NULL && !use_ranges_p)
1070 return;
1071
1072 if (dump_file && (dump_flags & TDF_DETAILS))
1073 fprintf (dump_file, "\nSubstituing values and folding statements\n\n");
1074
1075 memset (&prop_stats, 0, sizeof (prop_stats));
1076
1077 /* Substitute values in every statement of every basic block. */
1078 FOR_EACH_BB (bb)
1079 {
1080 block_stmt_iterator i;
1081 tree phi;
1082
1083 /* Propagate known values into PHI nodes. */
1084 if (prop_value)
1085 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1086 replace_phi_args_in (phi, prop_value);
1087
1088 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
1089 {
1090 bool replaced_address, did_replace;
1091 tree prev_stmt = NULL;
1092 tree stmt = bsi_stmt (i);
1093
1094 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
1095 range information for names and they are discarded
1096 afterwards. */
1097 if (TREE_CODE (stmt) == MODIFY_EXPR
1098 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1099 continue;
1100
1101 /* Replace the statement with its folded version and mark it
1102 folded. */
1103 did_replace = false;
1104 replaced_address = false;
1105 if (dump_file && (dump_flags & TDF_DETAILS))
1106 prev_stmt = unshare_expr (stmt);
1107
1108 /* If we have range information, see if we can fold
1109 predicate expressions. */
1110 if (use_ranges_p)
1111 {
1112 did_replace = fold_predicate_in (stmt);
1113
1114 /* Some statements may be simplified using ranges. For
1115 example, division may be replaced by shifts, modulo
1116 replaced with bitwise and, etc. */
1117 simplify_stmt_using_ranges (stmt);
1118 }
1119
1120 if (prop_value)
1121 {
1122 /* Only replace real uses if we couldn't fold the
1123 statement using value range information (value range
1124 information is not collected on virtuals, so we only
1125 need to check this for real uses). */
1126 if (!did_replace)
1127 did_replace |= replace_uses_in (stmt, &replaced_address,
1128 prop_value);
1129
1130 did_replace |= replace_vuses_in (stmt, &replaced_address,
1131 prop_value);
1132 }
1133
1134 /* If we made a replacement, fold and cleanup the statement. */
1135 if (did_replace)
1136 {
1137 tree old_stmt = stmt;
1138 tree rhs;
1139
1140 fold_stmt (bsi_stmt_ptr (i));
1141 stmt = bsi_stmt (i);
1142
1143 /* If we folded a builtin function, we'll likely
1144 need to rename VDEFs. */
1145 mark_new_vars_to_rename (stmt);
1146
1147 /* If we cleaned up EH information from the statement,
1148 remove EH edges. */
1149 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1150 tree_purge_dead_eh_edges (bb);
1151
1152 rhs = get_rhs (stmt);
1153 if (TREE_CODE (rhs) == ADDR_EXPR)
1154 recompute_tree_invarant_for_addr_expr (rhs);
1155
1156 if (dump_file && (dump_flags & TDF_DETAILS))
1157 {
1158 fprintf (dump_file, "Folded statement: ");
1159 print_generic_stmt (dump_file, prev_stmt, TDF_SLIM);
1160 fprintf (dump_file, " into: ");
1161 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1162 fprintf (dump_file, "\n");
1163 }
1164 }
1165 }
1166 }
1167
1168 if (dump_file && (dump_flags & TDF_STATS))
1169 {
1170 fprintf (dump_file, "Constants propagated: %6ld\n",
1171 prop_stats.num_const_prop);
1172 fprintf (dump_file, "Copies propagated: %6ld\n",
1173 prop_stats.num_copy_prop);
1174 fprintf (dump_file, "Predicates folded: %6ld\n",
1175 prop_stats.num_pred_folded);
1176 }
1177 }
1178
1179 #include "gt-tree-ssa-propagate.h"