OSDN Git Service

* tree-ssa-propagate.c (cfg_blocks_add) Assert we're not trying
[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, and it must not be the ENTRY or EXIT block.  */
176
177 static void 
178 cfg_blocks_add (basic_block bb)
179 {
180   gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
181   gcc_assert (!TEST_BIT (bb_in_list, bb->index));
182
183   if (cfg_blocks_empty_p ())
184     {
185       cfg_blocks_tail = cfg_blocks_head = 0;
186       cfg_blocks_num = 1;
187     }
188   else
189     {
190       cfg_blocks_num++;
191       if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
192         {
193           /* We have to grow the array now.  Adjust to queue to occupy the
194              full space of the original array.  */
195           cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
196           cfg_blocks_head = 0;
197           VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
198         }
199       else
200         cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
201     }
202
203   VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
204   SET_BIT (bb_in_list, bb->index);
205 }
206
207
208 /* Remove a block from the worklist.  */
209
210 static basic_block
211 cfg_blocks_get (void)
212 {
213   basic_block bb;
214
215   bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
216
217   gcc_assert (!cfg_blocks_empty_p ());
218   gcc_assert (bb);
219
220   cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
221   --cfg_blocks_num;
222   RESET_BIT (bb_in_list, bb->index);
223
224   return bb;
225 }
226
227
228 /* We have just defined a new value for VAR.  If IS_VARYING is true,
229    add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
230    them to INTERESTING_SSA_EDGES.  */
231
232 static void
233 add_ssa_edge (tree var, bool is_varying)
234 {
235   tree stmt = SSA_NAME_DEF_STMT (var);
236   dataflow_t df = get_immediate_uses (stmt);
237   int num_uses = num_immediate_uses (df);
238   int i;
239
240   for (i = 0; i < num_uses; i++)
241     {
242       tree use_stmt = immediate_use (df, i);
243
244       if (!DONT_SIMULATE_AGAIN (use_stmt)
245           && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt))
246         {
247           STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
248           if (is_varying)
249             VEC_safe_push (tree, varying_ssa_edges, use_stmt);
250           else
251             VEC_safe_push (tree, interesting_ssa_edges, use_stmt);
252         }
253     }
254 }
255
256
257 /* Add edge E to the control flow worklist.  */
258
259 static void
260 add_control_edge (edge e)
261 {
262   basic_block bb = e->dest;
263   if (bb == EXIT_BLOCK_PTR)
264     return;
265
266   /* If the edge had already been executed, skip it.  */
267   if (e->flags & EDGE_EXECUTABLE)
268     return;
269
270   e->flags |= EDGE_EXECUTABLE;
271
272   /* If the block is already in the list, we're done.  */
273   if (TEST_BIT (bb_in_list, bb->index))
274     return;
275
276   cfg_blocks_add (bb);
277
278   if (dump_file && (dump_flags & TDF_DETAILS))
279     fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
280         e->src->index, e->dest->index);
281 }
282
283
284 /* Simulate the execution of STMT and update the work lists accordingly.  */
285
286 static void
287 simulate_stmt (tree stmt)
288 {
289   enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
290   edge taken_edge = NULL;
291   tree output_name = NULL_TREE;
292
293   /* Don't bother visiting statements that are already
294      considered varying by the propagator.  */
295   if (DONT_SIMULATE_AGAIN (stmt))
296     return;
297
298   if (TREE_CODE (stmt) == PHI_NODE)
299     {
300       val = ssa_prop_visit_phi (stmt);
301       output_name = PHI_RESULT (stmt);
302     }
303   else
304     val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
305
306   if (val == SSA_PROP_VARYING)
307     {
308       DONT_SIMULATE_AGAIN (stmt) = 1;
309
310       /* If the statement produced a new varying value, add the SSA
311          edges coming out of OUTPUT_NAME.  */
312       if (output_name)
313         add_ssa_edge (output_name, true);
314
315       /* If STMT transfers control out of its basic block, add
316          all outgoing edges to the work list.  */
317       if (stmt_ends_bb_p (stmt))
318         {
319           edge e;
320           edge_iterator ei;
321           basic_block bb = bb_for_stmt (stmt);
322           FOR_EACH_EDGE (e, ei, bb->succs)
323             add_control_edge (e);
324         }
325     }
326   else if (val == SSA_PROP_INTERESTING)
327     {
328       /* If the statement produced new value, add the SSA edges coming
329          out of OUTPUT_NAME.  */
330       if (output_name)
331         add_ssa_edge (output_name, false);
332
333       /* If we know which edge is going to be taken out of this block,
334          add it to the CFG work list.  */
335       if (taken_edge)
336         add_control_edge (taken_edge);
337     }
338 }
339
340 /* Process an SSA edge worklist.  WORKLIST is the SSA edge worklist to
341    drain.  This pops statements off the given WORKLIST and processes
342    them until there are no more statements on WORKLIST.
343    We take a pointer to WORKLIST because it may be reallocated when an
344    SSA edge is added to it in simulate_stmt.  */
345
346 static void
347 process_ssa_edge_worklist (VEC(tree) **worklist)
348 {
349   /* Drain the entire worklist.  */
350   while (VEC_length (tree, *worklist) > 0)
351     {
352       basic_block bb;
353
354       /* Pull the statement to simulate off the worklist.  */
355       tree stmt = VEC_pop (tree, *worklist);
356
357       /* If this statement was already visited by simulate_block, then
358          we don't need to visit it again here.  */
359       if (!STMT_IN_SSA_EDGE_WORKLIST (stmt))
360         continue;
361
362       /* STMT is no longer in a worklist.  */
363       STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
364
365       if (dump_file && (dump_flags & TDF_DETAILS))
366         {
367           fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
368           print_generic_stmt (dump_file, stmt, dump_flags);
369         }
370
371       bb = bb_for_stmt (stmt);
372
373       /* PHI nodes are always visited, regardless of whether or not
374          the destination block is executable.  Otherwise, visit the
375          statement only if its block is marked executable.  */
376       if (TREE_CODE (stmt) == PHI_NODE
377           || TEST_BIT (executable_blocks, bb->index))
378         simulate_stmt (stmt);
379     }
380 }
381
382
383 /* Simulate the execution of BLOCK.  Evaluate the statement associated
384    with each variable reference inside the block.  */
385
386 static void
387 simulate_block (basic_block block)
388 {
389   tree phi;
390
391   /* There is nothing to do for the exit block.  */
392   if (block == EXIT_BLOCK_PTR)
393     return;
394
395   if (dump_file && (dump_flags & TDF_DETAILS))
396     fprintf (dump_file, "\nSimulating block %d\n", block->index);
397
398   /* Always simulate PHI nodes, even if we have simulated this block
399      before.  */
400   for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
401     simulate_stmt (phi);
402
403   /* If this is the first time we've simulated this block, then we
404      must simulate each of its statements.  */
405   if (!TEST_BIT (executable_blocks, block->index))
406     {
407       block_stmt_iterator j;
408       unsigned int normal_edge_count;
409       edge e, normal_edge;
410       edge_iterator ei;
411
412       /* Note that we have simulated this block.  */
413       SET_BIT (executable_blocks, block->index);
414
415       for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
416         {
417           tree stmt = bsi_stmt (j);
418
419           /* If this statement is already in the worklist then
420              "cancel" it.  The reevaluation implied by the worklist
421              entry will produce the same value we generate here and
422              thus reevaluating it again from the worklist is
423              pointless.  */
424           if (STMT_IN_SSA_EDGE_WORKLIST (stmt))
425             STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
426
427           simulate_stmt (stmt);
428         }
429
430       /* We can not predict when abnormal edges will be executed, so
431          once a block is considered executable, we consider any
432          outgoing abnormal edges as executable.
433
434          At the same time, if this block has only one successor that is
435          reached by non-abnormal edges, then add that successor to the
436          worklist.  */
437       normal_edge_count = 0;
438       normal_edge = NULL;
439       FOR_EACH_EDGE (e, ei, block->succs)
440         {
441           if (e->flags & EDGE_ABNORMAL)
442             add_control_edge (e);
443           else
444             {
445               normal_edge_count++;
446               normal_edge = e;
447             }
448         }
449
450       if (normal_edge_count == 1)
451         add_control_edge (normal_edge);
452     }
453 }
454
455
456 /* Initialize local data structures and work lists.  */
457
458 static void
459 ssa_prop_init (void)
460 {
461   edge e;
462   edge_iterator ei;
463   basic_block bb;
464
465   /* Worklists of SSA edges.  */
466   interesting_ssa_edges = VEC_alloc (tree, 20);
467   varying_ssa_edges = VEC_alloc (tree, 20);
468
469   executable_blocks = sbitmap_alloc (last_basic_block);
470   sbitmap_zero (executable_blocks);
471
472   bb_in_list = sbitmap_alloc (last_basic_block);
473   sbitmap_zero (bb_in_list);
474
475   if (dump_file && (dump_flags & TDF_DETAILS))
476     dump_immediate_uses (dump_file);
477
478   VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
479
480   /* Initially assume that every edge in the CFG is not executable.  */
481   FOR_EACH_BB (bb)
482     {
483       block_stmt_iterator si;
484
485       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
486         STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
487
488       FOR_EACH_EDGE (e, ei, bb->succs)
489         e->flags &= ~EDGE_EXECUTABLE;
490     }
491
492   /* Seed the algorithm by adding the successors of the entry block to the
493      edge worklist.  */
494   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
495     add_control_edge (e);
496 }
497
498
499 /* Free allocated storage.  */
500
501 static void
502 ssa_prop_fini (void)
503 {
504   VEC_free (tree, interesting_ssa_edges);
505   VEC_free (tree, varying_ssa_edges);
506   cfg_blocks = NULL;
507   sbitmap_free (bb_in_list);
508   sbitmap_free (executable_blocks);
509   free_df ();
510 }
511
512
513 /* Get the main expression from statement STMT.  */
514
515 tree
516 get_rhs (tree stmt)
517 {
518   enum tree_code code = TREE_CODE (stmt);
519
520   switch (code)
521     {
522     case RETURN_EXPR:
523       stmt = TREE_OPERAND (stmt, 0);
524       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
525         return stmt;
526       /* FALLTHRU */
527
528     case MODIFY_EXPR:
529       stmt = TREE_OPERAND (stmt, 1);
530       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
531         return TREE_OPERAND (stmt, 0);
532       else
533         return stmt;
534
535     case COND_EXPR:
536       return COND_EXPR_COND (stmt);
537     case SWITCH_EXPR:
538       return SWITCH_COND (stmt);
539     case GOTO_EXPR:
540       return GOTO_DESTINATION (stmt);
541     case LABEL_EXPR:
542       return LABEL_EXPR_LABEL (stmt);
543
544     default:
545       return stmt;
546     }
547 }
548
549
550 /* Set the main expression of *STMT_P to EXPR.  If EXPR is not a valid
551    GIMPLE expression no changes are done and the function returns
552    false.  */
553
554 bool
555 set_rhs (tree *stmt_p, tree expr)
556 {
557   tree stmt = *stmt_p, op;
558   enum tree_code code = TREE_CODE (expr);
559   stmt_ann_t ann;
560   tree var;
561   ssa_op_iter iter;
562
563   /* Verify the constant folded result is valid gimple.  */
564   if (TREE_CODE_CLASS (code) == tcc_binary)
565     {
566       if (!is_gimple_val (TREE_OPERAND (expr, 0))
567           || !is_gimple_val (TREE_OPERAND (expr, 1)))
568         return false;
569     }
570   else if (TREE_CODE_CLASS (code) == tcc_unary)
571     {
572       if (!is_gimple_val (TREE_OPERAND (expr, 0)))
573         return false;
574     }
575   else if (code == COMPOUND_EXPR)
576     return false;
577
578   switch (TREE_CODE (stmt))
579     {
580     case RETURN_EXPR:
581       op = TREE_OPERAND (stmt, 0);
582       if (TREE_CODE (op) != MODIFY_EXPR)
583         {
584           TREE_OPERAND (stmt, 0) = expr;
585           break;
586         }
587       stmt = op;
588       /* FALLTHRU */
589
590     case MODIFY_EXPR:
591       op = TREE_OPERAND (stmt, 1);
592       if (TREE_CODE (op) == WITH_SIZE_EXPR)
593         stmt = op;
594       TREE_OPERAND (stmt, 1) = expr;
595       break;
596
597     case COND_EXPR:
598       COND_EXPR_COND (stmt) = expr;
599       break;
600     case SWITCH_EXPR:
601       SWITCH_COND (stmt) = expr;
602       break;
603     case GOTO_EXPR:
604       GOTO_DESTINATION (stmt) = expr;
605       break;
606     case LABEL_EXPR:
607       LABEL_EXPR_LABEL (stmt) = expr;
608       break;
609
610     default:
611       /* Replace the whole statement with EXPR.  If EXPR has no side
612          effects, then replace *STMT_P with an empty statement.  */
613       ann = stmt_ann (stmt);
614       *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
615       (*stmt_p)->common.ann = (tree_ann_t) ann;
616
617       if (TREE_SIDE_EFFECTS (expr))
618         {
619           /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
620              replacement.  */
621           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
622             {
623               if (TREE_CODE (var) == SSA_NAME)
624                 SSA_NAME_DEF_STMT (var) = *stmt_p;
625             }
626         }
627       break;
628     }
629
630   return true;
631 }
632
633
634 /* Entry point to the propagation engine.
635
636    VISIT_STMT is called for every statement visited.
637    VISIT_PHI is called for every PHI node visited.  */
638
639 void
640 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
641                ssa_prop_visit_phi_fn visit_phi)
642 {
643   ssa_prop_visit_stmt = visit_stmt;
644   ssa_prop_visit_phi = visit_phi;
645
646   ssa_prop_init ();
647
648   /* Iterate until the worklists are empty.  */
649   while (!cfg_blocks_empty_p () 
650          || VEC_length (tree, interesting_ssa_edges) > 0
651          || VEC_length (tree, varying_ssa_edges) > 0)
652     {
653       if (!cfg_blocks_empty_p ())
654         {
655           /* Pull the next block to simulate off the worklist.  */
656           basic_block dest_block = cfg_blocks_get ();
657           simulate_block (dest_block);
658         }
659
660       /* In order to move things to varying as quickly as
661          possible,process the VARYING_SSA_EDGES worklist first.  */
662       process_ssa_edge_worklist (&varying_ssa_edges);
663
664       /* Now process the INTERESTING_SSA_EDGES worklist.  */
665       process_ssa_edge_worklist (&interesting_ssa_edges);
666     }
667
668   ssa_prop_fini ();
669 }
670
671 #include "gt-tree-ssa-propagate.h"