1 /* Generic SSA value propagation engine.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
31 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-flow.h"
40 #include "tree-pass.h"
41 #include "tree-ssa-propagate.h"
42 #include "langhooks.h"
46 /* This file implements a generic value propagation engine based on
47 the same propagation used by the SSA-CCP algorithm [1].
49 Propagation is performed by simulating the execution of every
50 statement that produces the value being propagated. Simulation
53 1- Initially, all edges of the CFG are marked not executable and
54 the CFG worklist is seeded with all the statements in the entry
55 basic block (block 0).
57 2- Every statement S is simulated with a call to the call-back
58 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
61 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
62 interest and does not affect any of the work lists.
64 SSA_PROP_VARYING: The value produced by S cannot be determined
65 at compile time. Further simulation of S is not required.
66 If S is a conditional jump, all the outgoing edges for the
67 block are considered executable and added to the work
70 SSA_PROP_INTERESTING: S produces a value that can be computed
71 at compile time. Its result can be propagated into the
72 statements that feed from S. Furthermore, if S is a
73 conditional jump, only the edge known to be taken is added
74 to the work list. Edges that are known not to execute are
77 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
78 return value from SSA_PROP_VISIT_PHI has the same semantics as
81 4- Three work lists are kept. Statements are only added to these
82 lists if they produce one of SSA_PROP_INTERESTING or
85 CFG_BLOCKS contains the list of blocks to be simulated.
86 Blocks are added to this list if their incoming edges are
89 VARYING_SSA_EDGES contains the list of statements that feed
90 from statements that produce an SSA_PROP_VARYING result.
91 These are simulated first to speed up processing.
93 INTERESTING_SSA_EDGES contains the list of statements that
94 feed from statements that produce an SSA_PROP_INTERESTING
97 5- Simulation terminates when all three work lists are drained.
99 Before calling ssa_propagate, it is important to clear
100 DONT_SIMULATE_AGAIN for all the statements in the program that
101 should be simulated. This initialization allows an implementation
102 to specify which statements should never be simulated.
104 It is also important to compute def-use information before calling
109 [1] Constant propagation with conditional branches,
110 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
112 [2] Building an Optimizing Compiler,
113 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
115 [3] Advanced Compiler Design and Implementation,
116 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
118 /* Function pointers used to parameterize the propagation engine. */
119 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt
;
120 static ssa_prop_visit_phi_fn ssa_prop_visit_phi
;
122 /* Use the TREE_DEPRECATED bitflag to mark statements that have been
123 added to one of the SSA edges worklists. This flag is used to
124 avoid visiting statements unnecessarily when draining an SSA edge
125 worklist. If while simulating a basic block, we find a statement with
126 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
127 processing from visiting it again. */
128 #define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
130 /* A bitmap to keep track of executable blocks in the CFG. */
131 static sbitmap executable_blocks
;
133 /* Array of control flow edges on the worklist. */
134 static GTY(()) varray_type cfg_blocks
= NULL
;
136 static unsigned int cfg_blocks_num
= 0;
137 static int cfg_blocks_tail
;
138 static int cfg_blocks_head
;
140 static sbitmap bb_in_list
;
142 /* Worklist of SSA edges which will need reexamination as their
143 definition has changed. SSA edges are def-use edges in the SSA
144 web. For each D-U edge, we store the target statement or PHI node
146 static GTY(()) VEC(tree
) *interesting_ssa_edges
;
148 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
149 list of SSA edges is split into two. One contains all SSA edges
150 who need to be reexamined because their lattice value changed to
151 varying (this worklist), and the other contains all other SSA edges
152 to be reexamined (INTERESTING_SSA_EDGES).
154 Since most values in the program are VARYING, the ideal situation
155 is to move them to that lattice value as quickly as possible.
156 Thus, it doesn't make sense to process any other type of lattice
157 value until all VARYING values are propagated fully, which is one
158 thing using the VARYING worklist achieves. In addition, if we
159 don't use a separate worklist for VARYING edges, we end up with
160 situations where lattice values move from
161 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
162 static GTY(()) VEC(tree
) *varying_ssa_edges
;
165 /* Return true if the block worklist empty. */
168 cfg_blocks_empty_p (void)
170 return (cfg_blocks_num
== 0);
174 /* Add a basic block to the worklist. The block must not be already
178 cfg_blocks_add (basic_block bb
)
180 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
183 gcc_assert (!TEST_BIT (bb_in_list
, bb
->index
));
185 if (cfg_blocks_empty_p ())
187 cfg_blocks_tail
= cfg_blocks_head
= 0;
193 if (cfg_blocks_num
> VARRAY_SIZE (cfg_blocks
))
195 /* We have to grow the array now. Adjust to queue to occupy the
196 full space of the original array. */
197 cfg_blocks_tail
= VARRAY_SIZE (cfg_blocks
);
199 VARRAY_GROW (cfg_blocks
, 2 * VARRAY_SIZE (cfg_blocks
));
202 cfg_blocks_tail
= (cfg_blocks_tail
+ 1) % VARRAY_SIZE (cfg_blocks
);
205 VARRAY_BB (cfg_blocks
, cfg_blocks_tail
) = bb
;
206 SET_BIT (bb_in_list
, bb
->index
);
210 /* Remove a block from the worklist. */
213 cfg_blocks_get (void)
217 bb
= VARRAY_BB (cfg_blocks
, cfg_blocks_head
);
219 gcc_assert (!cfg_blocks_empty_p ());
222 cfg_blocks_head
= (cfg_blocks_head
+ 1) % VARRAY_SIZE (cfg_blocks
);
224 RESET_BIT (bb_in_list
, bb
->index
);
230 /* We have just defined a new value for VAR. If IS_VARYING is true,
231 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
232 them to INTERESTING_SSA_EDGES. */
235 add_ssa_edge (tree var
, bool is_varying
)
237 tree stmt
= SSA_NAME_DEF_STMT (var
);
238 dataflow_t df
= get_immediate_uses (stmt
);
239 int num_uses
= num_immediate_uses (df
);
242 for (i
= 0; i
< num_uses
; i
++)
244 tree use_stmt
= immediate_use (df
, i
);
246 if (!DONT_SIMULATE_AGAIN (use_stmt
)
247 && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt
))
249 STMT_IN_SSA_EDGE_WORKLIST (use_stmt
) = 1;
251 VEC_safe_push (tree
, varying_ssa_edges
, use_stmt
);
253 VEC_safe_push (tree
, interesting_ssa_edges
, use_stmt
);
259 /* Add edge E to the control flow worklist. */
262 add_control_edge (edge e
)
264 basic_block bb
= e
->dest
;
265 if (bb
== EXIT_BLOCK_PTR
)
268 /* If the edge had already been executed, skip it. */
269 if (e
->flags
& EDGE_EXECUTABLE
)
272 e
->flags
|= EDGE_EXECUTABLE
;
274 /* If the block is already in the list, we're done. */
275 if (TEST_BIT (bb_in_list
, bb
->index
))
280 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
281 fprintf (dump_file
, "Adding Destination of edge (%d -> %d) to worklist\n\n",
282 e
->src
->index
, e
->dest
->index
);
286 /* Simulate the execution of STMT and update the work lists accordingly. */
289 simulate_stmt (tree stmt
)
291 enum ssa_prop_result val
= SSA_PROP_NOT_INTERESTING
;
292 edge taken_edge
= NULL
;
293 tree output_name
= NULL_TREE
;
295 /* Don't bother visiting statements that are already
296 considered varying by the propagator. */
297 if (DONT_SIMULATE_AGAIN (stmt
))
300 if (TREE_CODE (stmt
) == PHI_NODE
)
302 val
= ssa_prop_visit_phi (stmt
);
303 output_name
= PHI_RESULT (stmt
);
306 val
= ssa_prop_visit_stmt (stmt
, &taken_edge
, &output_name
);
308 if (val
== SSA_PROP_VARYING
)
310 DONT_SIMULATE_AGAIN (stmt
) = 1;
312 /* If the statement produced a new varying value, add the SSA
313 edges coming out of OUTPUT_NAME. */
315 add_ssa_edge (output_name
, true);
317 /* If STMT transfers control out of its basic block, add
318 all outgoing edges to the work list. */
319 if (stmt_ends_bb_p (stmt
))
323 basic_block bb
= bb_for_stmt (stmt
);
324 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
325 add_control_edge (e
);
328 else if (val
== SSA_PROP_INTERESTING
)
330 /* If the statement produced new value, add the SSA edges coming
331 out of OUTPUT_NAME. */
333 add_ssa_edge (output_name
, false);
335 /* If we know which edge is going to be taken out of this block,
336 add it to the CFG work list. */
338 add_control_edge (taken_edge
);
342 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
343 drain. This pops statements off the given WORKLIST and processes
344 them until there are no more statements on WORKLIST.
345 We take a pointer to WORKLIST because it may be reallocated when an
346 SSA edge is added to it in simulate_stmt. */
349 process_ssa_edge_worklist (VEC(tree
) **worklist
)
351 /* Drain the entire worklist. */
352 while (VEC_length (tree
, *worklist
) > 0)
356 /* Pull the statement to simulate off the worklist. */
357 tree stmt
= VEC_pop (tree
, *worklist
);
359 /* If this statement was already visited by simulate_block, then
360 we don't need to visit it again here. */
361 if (!STMT_IN_SSA_EDGE_WORKLIST (stmt
))
364 /* STMT is no longer in a worklist. */
365 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
369 fprintf (dump_file
, "\nSimulating statement (from ssa_edges): ");
370 print_generic_stmt (dump_file
, stmt
, dump_flags
);
373 bb
= bb_for_stmt (stmt
);
375 /* PHI nodes are always visited, regardless of whether or not
376 the destination block is executable. Otherwise, visit the
377 statement only if its block is marked executable. */
378 if (TREE_CODE (stmt
) == PHI_NODE
379 || TEST_BIT (executable_blocks
, bb
->index
))
380 simulate_stmt (stmt
);
385 /* Simulate the execution of BLOCK. Evaluate the statement associated
386 with each variable reference inside the block. */
389 simulate_block (basic_block block
)
393 /* There is nothing to do for the exit block. */
394 if (block
== EXIT_BLOCK_PTR
)
397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
398 fprintf (dump_file
, "\nSimulating block %d\n", block
->index
);
400 /* Always simulate PHI nodes, even if we have simulated this block
402 for (phi
= phi_nodes (block
); phi
; phi
= PHI_CHAIN (phi
))
405 /* If this is the first time we've simulated this block, then we
406 must simulate each of its statements. */
407 if (!TEST_BIT (executable_blocks
, block
->index
))
409 block_stmt_iterator j
;
410 unsigned int normal_edge_count
;
414 /* Note that we have simulated this block. */
415 SET_BIT (executable_blocks
, block
->index
);
417 for (j
= bsi_start (block
); !bsi_end_p (j
); bsi_next (&j
))
419 tree stmt
= bsi_stmt (j
);
421 /* If this statement is already in the worklist then
422 "cancel" it. The reevaluation implied by the worklist
423 entry will produce the same value we generate here and
424 thus reevaluating it again from the worklist is
426 if (STMT_IN_SSA_EDGE_WORKLIST (stmt
))
427 STMT_IN_SSA_EDGE_WORKLIST (stmt
) = 0;
429 simulate_stmt (stmt
);
432 /* We can not predict when abnormal edges will be executed, so
433 once a block is considered executable, we consider any
434 outgoing abnormal edges as executable.
436 At the same time, if this block has only one successor that is
437 reached by non-abnormal edges, then add that successor to the
439 normal_edge_count
= 0;
441 FOR_EACH_EDGE (e
, ei
, block
->succs
)
443 if (e
->flags
& EDGE_ABNORMAL
)
444 add_control_edge (e
);
452 if (normal_edge_count
== 1)
453 add_control_edge (normal_edge
);
458 /* Initialize local data structures and work lists. */
467 /* Worklists of SSA edges. */
468 interesting_ssa_edges
= VEC_alloc (tree
, 20);
469 varying_ssa_edges
= VEC_alloc (tree
, 20);
471 executable_blocks
= sbitmap_alloc (last_basic_block
);
472 sbitmap_zero (executable_blocks
);
474 bb_in_list
= sbitmap_alloc (last_basic_block
);
475 sbitmap_zero (bb_in_list
);
477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
478 dump_immediate_uses (dump_file
);
480 VARRAY_BB_INIT (cfg_blocks
, 20, "cfg_blocks");
482 /* Initially assume that every edge in the CFG is not executable. */
485 block_stmt_iterator si
;
487 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
488 STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si
)) = 0;
490 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
491 e
->flags
&= ~EDGE_EXECUTABLE
;
494 /* Seed the algorithm by adding the successors of the entry block to the
496 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
498 if (e
->dest
!= EXIT_BLOCK_PTR
)
500 e
->flags
|= EDGE_EXECUTABLE
;
501 cfg_blocks_add (e
->dest
);
507 /* Free allocated storage. */
512 VEC_free (tree
, interesting_ssa_edges
);
513 VEC_free (tree
, varying_ssa_edges
);
515 sbitmap_free (bb_in_list
);
516 sbitmap_free (executable_blocks
);
521 /* Get the main expression from statement STMT. */
526 enum tree_code code
= TREE_CODE (stmt
);
531 stmt
= TREE_OPERAND (stmt
, 0);
532 if (!stmt
|| TREE_CODE (stmt
) != MODIFY_EXPR
)
537 stmt
= TREE_OPERAND (stmt
, 1);
538 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
539 return TREE_OPERAND (stmt
, 0);
544 return COND_EXPR_COND (stmt
);
546 return SWITCH_COND (stmt
);
548 return GOTO_DESTINATION (stmt
);
550 return LABEL_EXPR_LABEL (stmt
);
558 /* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
559 GIMPLE expression no changes are done and the function returns
563 set_rhs (tree
*stmt_p
, tree expr
)
565 tree stmt
= *stmt_p
, op
;
566 enum tree_code code
= TREE_CODE (expr
);
571 /* Verify the constant folded result is valid gimple. */
572 if (TREE_CODE_CLASS (code
) == tcc_binary
)
574 if (!is_gimple_val (TREE_OPERAND (expr
, 0))
575 || !is_gimple_val (TREE_OPERAND (expr
, 1)))
578 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
580 if (!is_gimple_val (TREE_OPERAND (expr
, 0)))
583 else if (code
== COMPOUND_EXPR
)
586 switch (TREE_CODE (stmt
))
589 op
= TREE_OPERAND (stmt
, 0);
590 if (TREE_CODE (op
) != MODIFY_EXPR
)
592 TREE_OPERAND (stmt
, 0) = expr
;
599 op
= TREE_OPERAND (stmt
, 1);
600 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
602 TREE_OPERAND (stmt
, 1) = expr
;
606 COND_EXPR_COND (stmt
) = expr
;
609 SWITCH_COND (stmt
) = expr
;
612 GOTO_DESTINATION (stmt
) = expr
;
615 LABEL_EXPR_LABEL (stmt
) = expr
;
619 /* Replace the whole statement with EXPR. If EXPR has no side
620 effects, then replace *STMT_P with an empty statement. */
621 ann
= stmt_ann (stmt
);
622 *stmt_p
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
623 (*stmt_p
)->common
.ann
= (tree_ann_t
) ann
;
625 if (TREE_SIDE_EFFECTS (expr
))
627 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
629 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_DEFS
)
631 if (TREE_CODE (var
) == SSA_NAME
)
632 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
642 /* Entry point to the propagation engine.
644 VISIT_STMT is called for every statement visited.
645 VISIT_PHI is called for every PHI node visited. */
648 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt
,
649 ssa_prop_visit_phi_fn visit_phi
)
651 ssa_prop_visit_stmt
= visit_stmt
;
652 ssa_prop_visit_phi
= visit_phi
;
656 /* Iterate until the worklists are empty. */
657 while (!cfg_blocks_empty_p ()
658 || VEC_length (tree
, interesting_ssa_edges
) > 0
659 || VEC_length (tree
, varying_ssa_edges
) > 0)
661 if (!cfg_blocks_empty_p ())
663 /* Pull the next block to simulate off the worklist. */
664 basic_block dest_block
= cfg_blocks_get ();
665 simulate_block (dest_block
);
668 /* In order to move things to varying as quickly as
669 possible,process the VARYING_SSA_EDGES worklist first. */
670 process_ssa_edge_worklist (&varying_ssa_edges
);
672 /* Now process the INTERESTING_SSA_EDGES worklist. */
673 process_ssa_edge_worklist (&interesting_ssa_edges
);
679 #include "gt-tree-ssa-propagate.h"