OSDN Git Service

6fab4f46242caae3f6cef12d0924e2b3c24fda47
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-propagate.c
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>
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, 59 Temple Place - Suite 330, Boston, MA
20    02111-1307, 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 "errors.h"
34 #include "expr.h"
35 #include "function.h"
36 #include "diagnostic.h"
37 #include "timevar.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"
43 #include "varray.h"
44 #include "vec.h"
45
46 /* This file implements a generic value propagation engine based on
47    the same propagation used by the SSA-CCP algorithm [1].
48
49    Propagation is performed by simulating the execution of every
50    statement that produces the value being propagated.  Simulation
51    proceeds as follows:
52
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).
56
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
59       results:
60
61         SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
62             interest and does not affect any of the work lists.
63
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
68             list.
69
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
75             never simulated.
76
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
79       described in #2.
80
81    4- Three work lists are kept.  Statements are only added to these
82       lists if they produce one of SSA_PROP_INTERESTING or
83       SSA_PROP_VARYING.
84
85         CFG_BLOCKS contains the list of blocks to be simulated.
86             Blocks are added to this list if their incoming edges are
87             found executable.
88
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.
92
93         INTERESTING_SSA_EDGES contains the list of statements that
94             feed from statements that produce an SSA_PROP_INTERESTING
95             result.
96
97    5- Simulation terminates when all three work lists are drained.
98
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.
103
104    It is also important to compute def-use information before calling
105    ssa_propagate.
106
107    References:
108
109      [1] Constant propagation with conditional branches,
110          Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
111
112      [2] Building an Optimizing Compiler,
113          Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
114
115      [3] Advanced Compiler Design and Implementation,
116          Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */
117
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;
121
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)
129
130 /* A bitmap to keep track of executable blocks in the CFG.  */
131 static sbitmap executable_blocks;
132
133 /* Array of control flow edges on the worklist.  */
134 static GTY(()) varray_type cfg_blocks = NULL;
135
136 static unsigned int cfg_blocks_num = 0;
137 static int cfg_blocks_tail;
138 static int cfg_blocks_head;
139
140 static sbitmap bb_in_list;
141
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
145    U.  */
146 static GTY(()) VEC(tree) *interesting_ssa_edges;
147
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).
153
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;
163
164
165 /* Return true if the block worklist empty.  */
166
167 static inline bool
168 cfg_blocks_empty_p (void)
169 {
170   return (cfg_blocks_num == 0);
171 }
172
173
174 /* Add a basic block to the worklist.  The block must not be already
175    in the worklist.  */
176
177 static void 
178 cfg_blocks_add (basic_block bb)
179 {
180   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
181     return;
182
183   gcc_assert (!TEST_BIT (bb_in_list, bb->index));
184
185   if (cfg_blocks_empty_p ())
186     {
187       cfg_blocks_tail = cfg_blocks_head = 0;
188       cfg_blocks_num = 1;
189     }
190   else
191     {
192       cfg_blocks_num++;
193       if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
194         {
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);
198           cfg_blocks_head = 0;
199           VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
200         }
201       else
202         cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
203     }
204
205   VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
206   SET_BIT (bb_in_list, bb->index);
207 }
208
209
210 /* Remove a block from the worklist.  */
211
212 static basic_block
213 cfg_blocks_get (void)
214 {
215   basic_block bb;
216
217   bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
218
219   gcc_assert (!cfg_blocks_empty_p ());
220   gcc_assert (bb);
221
222   cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
223   --cfg_blocks_num;
224   RESET_BIT (bb_in_list, bb->index);
225
226   return bb;
227 }
228
229
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.  */
233
234 static void
235 add_ssa_edge (tree var, bool is_varying)
236 {
237   tree stmt = SSA_NAME_DEF_STMT (var);
238   dataflow_t df = get_immediate_uses (stmt);
239   int num_uses = num_immediate_uses (df);
240   int i;
241
242   for (i = 0; i < num_uses; i++)
243     {
244       tree use_stmt = immediate_use (df, i);
245
246       if (!DONT_SIMULATE_AGAIN (use_stmt)
247           && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt))
248         {
249           STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
250           if (is_varying)
251             VEC_safe_push (tree, varying_ssa_edges, use_stmt);
252           else
253             VEC_safe_push (tree, interesting_ssa_edges, use_stmt);
254         }
255     }
256 }
257
258
259 /* Add edge E to the control flow worklist.  */
260
261 static void
262 add_control_edge (edge e)
263 {
264   basic_block bb = e->dest;
265   if (bb == EXIT_BLOCK_PTR)
266     return;
267
268   /* If the edge had already been executed, skip it.  */
269   if (e->flags & EDGE_EXECUTABLE)
270     return;
271
272   e->flags |= EDGE_EXECUTABLE;
273
274   /* If the block is already in the list, we're done.  */
275   if (TEST_BIT (bb_in_list, bb->index))
276     return;
277
278   cfg_blocks_add (bb);
279
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);
283 }
284
285
286 /* Simulate the execution of STMT and update the work lists accordingly.  */
287
288 static void
289 simulate_stmt (tree stmt)
290 {
291   enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
292   edge taken_edge = NULL;
293   tree output_name = NULL_TREE;
294
295   /* Don't bother visiting statements that are already
296      considered varying by the propagator.  */
297   if (DONT_SIMULATE_AGAIN (stmt))
298     return;
299
300   if (TREE_CODE (stmt) == PHI_NODE)
301     {
302       val = ssa_prop_visit_phi (stmt);
303       output_name = PHI_RESULT (stmt);
304     }
305   else
306     val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
307
308   if (val == SSA_PROP_VARYING)
309     {
310       DONT_SIMULATE_AGAIN (stmt) = 1;
311
312       /* If the statement produced a new varying value, add the SSA
313          edges coming out of OUTPUT_NAME.  */
314       if (output_name)
315         add_ssa_edge (output_name, true);
316
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))
320         {
321           edge e;
322           edge_iterator ei;
323           basic_block bb = bb_for_stmt (stmt);
324           FOR_EACH_EDGE (e, ei, bb->succs)
325             add_control_edge (e);
326         }
327     }
328   else if (val == SSA_PROP_INTERESTING)
329     {
330       /* If the statement produced new value, add the SSA edges coming
331          out of OUTPUT_NAME.  */
332       if (output_name)
333         add_ssa_edge (output_name, false);
334
335       /* If we know which edge is going to be taken out of this block,
336          add it to the CFG work list.  */
337       if (taken_edge)
338         add_control_edge (taken_edge);
339     }
340 }
341
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.  */
347
348 static void
349 process_ssa_edge_worklist (VEC(tree) **worklist)
350 {
351   /* Drain the entire worklist.  */
352   while (VEC_length (tree, *worklist) > 0)
353     {
354       basic_block bb;
355
356       /* Pull the statement to simulate off the worklist.  */
357       tree stmt = VEC_pop (tree, *worklist);
358
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))
362         continue;
363
364       /* STMT is no longer in a worklist.  */
365       STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
366
367       if (dump_file && (dump_flags & TDF_DETAILS))
368         {
369           fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
370           print_generic_stmt (dump_file, stmt, dump_flags);
371         }
372
373       bb = bb_for_stmt (stmt);
374
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);
381     }
382 }
383
384
385 /* Simulate the execution of BLOCK.  Evaluate the statement associated
386    with each variable reference inside the block.  */
387
388 static void
389 simulate_block (basic_block block)
390 {
391   tree phi;
392
393   /* There is nothing to do for the exit block.  */
394   if (block == EXIT_BLOCK_PTR)
395     return;
396
397   if (dump_file && (dump_flags & TDF_DETAILS))
398     fprintf (dump_file, "\nSimulating block %d\n", block->index);
399
400   /* Always simulate PHI nodes, even if we have simulated this block
401      before.  */
402   for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
403     simulate_stmt (phi);
404
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))
408     {
409       block_stmt_iterator j;
410       unsigned int normal_edge_count;
411       edge e, normal_edge;
412       edge_iterator ei;
413
414       /* Note that we have simulated this block.  */
415       SET_BIT (executable_blocks, block->index);
416
417       for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
418         {
419           tree stmt = bsi_stmt (j);
420
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
425              pointless.  */
426           if (STMT_IN_SSA_EDGE_WORKLIST (stmt))
427             STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
428
429           simulate_stmt (stmt);
430         }
431
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.
435
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
438          worklist.  */
439       normal_edge_count = 0;
440       normal_edge = NULL;
441       FOR_EACH_EDGE (e, ei, block->succs)
442         {
443           if (e->flags & EDGE_ABNORMAL)
444             add_control_edge (e);
445           else
446             {
447               normal_edge_count++;
448               normal_edge = e;
449             }
450         }
451
452       if (normal_edge_count == 1)
453         add_control_edge (normal_edge);
454     }
455 }
456
457
458 /* Initialize local data structures and work lists.  */
459
460 static void
461 ssa_prop_init (void)
462 {
463   edge e;
464   edge_iterator ei;
465   basic_block bb;
466
467   /* Worklists of SSA edges.  */
468   interesting_ssa_edges = VEC_alloc (tree, 20);
469   varying_ssa_edges = VEC_alloc (tree, 20);
470
471   executable_blocks = sbitmap_alloc (last_basic_block);
472   sbitmap_zero (executable_blocks);
473
474   bb_in_list = sbitmap_alloc (last_basic_block);
475   sbitmap_zero (bb_in_list);
476
477   if (dump_file && (dump_flags & TDF_DETAILS))
478     dump_immediate_uses (dump_file);
479
480   VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
481
482   /* Initially assume that every edge in the CFG is not executable.  */
483   FOR_EACH_BB (bb)
484     {
485       block_stmt_iterator si;
486
487       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
488         STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
489
490       FOR_EACH_EDGE (e, ei, bb->succs)
491         e->flags &= ~EDGE_EXECUTABLE;
492     }
493
494   /* Seed the algorithm by adding the successors of the entry block to the
495      edge worklist.  */
496   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
497     {
498       if (e->dest != EXIT_BLOCK_PTR)
499         {
500           e->flags |= EDGE_EXECUTABLE;
501           cfg_blocks_add (e->dest);
502         }
503     }
504 }
505
506
507 /* Free allocated storage.  */
508
509 static void
510 ssa_prop_fini (void)
511 {
512   VEC_free (tree, interesting_ssa_edges);
513   VEC_free (tree, varying_ssa_edges);
514   cfg_blocks = NULL;
515   sbitmap_free (bb_in_list);
516   sbitmap_free (executable_blocks);
517   free_df ();
518 }
519
520
521 /* Get the main expression from statement STMT.  */
522
523 tree
524 get_rhs (tree stmt)
525 {
526   enum tree_code code = TREE_CODE (stmt);
527
528   switch (code)
529     {
530     case RETURN_EXPR:
531       stmt = TREE_OPERAND (stmt, 0);
532       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
533         return stmt;
534       /* FALLTHRU */
535
536     case MODIFY_EXPR:
537       stmt = TREE_OPERAND (stmt, 1);
538       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
539         return TREE_OPERAND (stmt, 0);
540       else
541         return stmt;
542
543     case COND_EXPR:
544       return COND_EXPR_COND (stmt);
545     case SWITCH_EXPR:
546       return SWITCH_COND (stmt);
547     case GOTO_EXPR:
548       return GOTO_DESTINATION (stmt);
549     case LABEL_EXPR:
550       return LABEL_EXPR_LABEL (stmt);
551
552     default:
553       return stmt;
554     }
555 }
556
557
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
560    false.  */
561
562 bool
563 set_rhs (tree *stmt_p, tree expr)
564 {
565   tree stmt = *stmt_p, op;
566   enum tree_code code = TREE_CODE (expr);
567   stmt_ann_t ann;
568   tree var;
569   ssa_op_iter iter;
570
571   /* Verify the constant folded result is valid gimple.  */
572   if (TREE_CODE_CLASS (code) == tcc_binary)
573     {
574       if (!is_gimple_val (TREE_OPERAND (expr, 0))
575           || !is_gimple_val (TREE_OPERAND (expr, 1)))
576         return false;
577     }
578   else if (TREE_CODE_CLASS (code) == tcc_unary)
579     {
580       if (!is_gimple_val (TREE_OPERAND (expr, 0)))
581         return false;
582     }
583   else if (code == COMPOUND_EXPR)
584     return false;
585
586   switch (TREE_CODE (stmt))
587     {
588     case RETURN_EXPR:
589       op = TREE_OPERAND (stmt, 0);
590       if (TREE_CODE (op) != MODIFY_EXPR)
591         {
592           TREE_OPERAND (stmt, 0) = expr;
593           break;
594         }
595       stmt = op;
596       /* FALLTHRU */
597
598     case MODIFY_EXPR:
599       op = TREE_OPERAND (stmt, 1);
600       if (TREE_CODE (op) == WITH_SIZE_EXPR)
601         stmt = op;
602       TREE_OPERAND (stmt, 1) = expr;
603       break;
604
605     case COND_EXPR:
606       COND_EXPR_COND (stmt) = expr;
607       break;
608     case SWITCH_EXPR:
609       SWITCH_COND (stmt) = expr;
610       break;
611     case GOTO_EXPR:
612       GOTO_DESTINATION (stmt) = expr;
613       break;
614     case LABEL_EXPR:
615       LABEL_EXPR_LABEL (stmt) = expr;
616       break;
617
618     default:
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;
624
625       if (TREE_SIDE_EFFECTS (expr))
626         {
627           /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
628              replacement.  */
629           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
630             {
631               if (TREE_CODE (var) == SSA_NAME)
632                 SSA_NAME_DEF_STMT (var) = *stmt_p;
633             }
634         }
635       break;
636     }
637
638   return true;
639 }
640
641
642 /* Entry point to the propagation engine.
643
644    VISIT_STMT is called for every statement visited.
645    VISIT_PHI is called for every PHI node visited.  */
646
647 void
648 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
649                ssa_prop_visit_phi_fn visit_phi)
650 {
651   ssa_prop_visit_stmt = visit_stmt;
652   ssa_prop_visit_phi = visit_phi;
653
654   ssa_prop_init ();
655
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)
660     {
661       if (!cfg_blocks_empty_p ())
662         {
663           /* Pull the next block to simulate off the worklist.  */
664           basic_block dest_block = cfg_blocks_get ();
665           simulate_block (dest_block);
666         }
667
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);
671
672       /* Now process the INTERESTING_SSA_EDGES worklist.  */
673       process_ssa_edge_worklist (&interesting_ssa_edges);
674     }
675
676   ssa_prop_fini ();
677 }
678
679 #include "gt-tree-ssa-propagate.h"