OSDN Git Service

b1d9365a8cbcff72fd0451053c692f77dace0abe
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dce.c
1 /* Dead code elimination pass for the GNU compiler.
2    Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
3    Contributed by Ben Elliston <bje@redhat.com>
4    and Andrew MacLeod <amacleod@redhat.com>
5    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
6  
7 This file is part of GCC.
8    
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
12 later version.
13    
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18    
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 02111-1307, USA.  */
23
24 /* Dead code elimination.
25
26    References:
27
28      Building an Optimizing Compiler,
29      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
30
31      Advanced Compiler Design and Implementation,
32      Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
33
34    Dead-code elimination is the removal of statements which have no
35    impact on the program's output.  "Dead statements" have no impact
36    on the program's output, while "necessary statements" may have
37    impact on the output.
38
39    The algorithm consists of three phases:
40    1. Marking as necessary all statements known to be necessary,
41       e.g. most function calls, writing a value to memory, etc;
42    2. Propagating necessary statements, e.g., the statements
43       giving values to operands in necessary statements; and
44    3. Removing dead statements.  */
45
46 #include "config.h"
47 #include "system.h"
48 #include "coretypes.h"
49 #include "tm.h"
50 #include "errors.h"
51 #include "ggc.h"
52
53 /* These RTL headers are needed for basic-block.h.  */
54 #include "rtl.h"
55 #include "tm_p.h"
56 #include "hard-reg-set.h"
57 #include "basic-block.h"
58
59 #include "tree.h"
60 #include "diagnostic.h"
61 #include "tree-flow.h"
62 #include "tree-gimple.h"
63 #include "tree-dump.h"
64 #include "tree-pass.h"
65 #include "timevar.h"
66 #include "flags.h"
67 \f
68 static struct stmt_stats
69 {
70   int total;
71   int total_phis;
72   int removed;
73   int removed_phis;
74 } stats;
75
76 static varray_type worklist;
77
78 /* Vector indicating an SSA name has already been processed and marked
79    as necessary.  */
80 static sbitmap processed;
81
82 /* Vector indicating that last_stmt if a basic block has already been
83    marked as necessary.  */
84 static sbitmap last_stmt_necessary;
85
86 /* Before we can determine whether a control branch is dead, we need to
87    compute which blocks are control dependent on which edges.
88
89    We expect each block to be control dependent on very few edges so we
90    use a bitmap for each block recording its edges.  An array holds the
91    bitmap.  The Ith bit in the bitmap is set if that block is dependent
92    on the Ith edge.  */
93 bitmap *control_dependence_map;
94
95 /* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
96    for which the block with index N is control dependent.  */
97 #define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE)                    \
98   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, CODE)
99
100 /* Local function prototypes.  */
101 static inline void set_control_dependence_map_bit (basic_block, int);
102 static inline void clear_control_dependence_bitmap (basic_block);
103 static void find_all_control_dependences (struct edge_list *);
104 static void find_control_dependence (struct edge_list *, int);
105 static inline basic_block find_pdom (basic_block);
106
107 static inline void mark_stmt_necessary (tree, bool);
108 static inline void mark_operand_necessary (tree);
109
110 static void mark_stmt_if_obviously_necessary (tree, bool);
111 static void find_obviously_necessary_stmts (struct edge_list *);
112
113 static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
114 static void propagate_necessity (struct edge_list *);
115
116 static void eliminate_unnecessary_stmts (void);
117 static void remove_dead_phis (basic_block);
118 static void remove_dead_stmt (block_stmt_iterator *, basic_block);
119
120 static void print_stats (void);
121 static void tree_dce_init (bool);
122 static void tree_dce_done (bool);
123 \f
124 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
125 static inline void
126 set_control_dependence_map_bit (basic_block bb, int edge_index)
127 {
128   if (bb == ENTRY_BLOCK_PTR)
129     return;
130   if (bb == EXIT_BLOCK_PTR)
131     abort ();
132   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
133 }
134
135 /* Clear all control dependences for block BB.  */
136 static inline
137 void clear_control_dependence_bitmap (basic_block bb)
138 {
139   bitmap_clear (control_dependence_map[bb->index]);
140 }
141
142 /* Record all blocks' control dependences on all edges in the edge
143    list EL, ala Morgan, Section 3.6.  */
144
145 static void
146 find_all_control_dependences (struct edge_list *el)
147 {
148   int i;
149
150   for (i = 0; i < NUM_EDGES (el); ++i)
151     find_control_dependence (el, i);
152 }
153
154 /* Determine all blocks' control dependences on the given edge with edge_list
155    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
156
157 static void
158 find_control_dependence (struct edge_list *el, int edge_index)
159 {
160   basic_block current_block;
161   basic_block ending_block;
162
163 #ifdef ENABLE_CHECKING
164   if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
165     abort ();
166 #endif
167
168   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
169     ending_block = ENTRY_BLOCK_PTR->next_bb;
170   else
171     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
172
173   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
174        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
175        current_block = find_pdom (current_block))
176     {
177       edge e = INDEX_EDGE (el, edge_index);
178
179       /* For abnormal edges, we don't make current_block control
180          dependent because instructions that throw are always necessary
181          anyway.  */
182       if (e->flags & EDGE_ABNORMAL)
183         continue;
184
185       set_control_dependence_map_bit (current_block, edge_index);
186     }
187 }
188
189 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
190    This function is necessary because some blocks have negative numbers.  */
191
192 static inline basic_block
193 find_pdom (basic_block block)
194 {
195   if (block == ENTRY_BLOCK_PTR)
196     abort ();
197   else if (block == EXIT_BLOCK_PTR)
198     return EXIT_BLOCK_PTR;
199   else
200     {
201       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
202       if (! bb)
203         return EXIT_BLOCK_PTR;
204       return bb;
205     }
206 }
207 \f
208 #define NECESSARY(stmt)         stmt->common.asm_written_flag
209
210 /* If STMT is not already marked necessary, mark it, and add it to the
211    worklist if ADD_TO_WORKLIST is true.  */
212 static inline void
213 mark_stmt_necessary (tree stmt, bool add_to_worklist)
214 {
215 #ifdef ENABLE_CHECKING
216   if (stmt == NULL
217       || stmt == error_mark_node
218       || (stmt && DECL_P (stmt)))
219     abort ();
220 #endif
221
222   if (NECESSARY (stmt))
223     return;
224
225   if (dump_file && (dump_flags & TDF_DETAILS))
226     {
227       fprintf (dump_file, "Marking useful stmt: ");
228       print_generic_stmt (dump_file, stmt, TDF_SLIM);
229       fprintf (dump_file, "\n");
230     }
231
232   NECESSARY (stmt) = 1;
233   if (add_to_worklist)
234     VARRAY_PUSH_TREE (worklist, stmt);
235 }
236
237 /* Mark the statement defining operand OP as necessary.  */
238
239 static inline void
240 mark_operand_necessary (tree op)
241 {
242   tree stmt;
243   int ver;
244
245 #ifdef ENABLE_CHECKING
246   if (op == NULL)
247     abort ();
248 #endif
249
250   ver = SSA_NAME_VERSION (op);
251   if (TEST_BIT (processed, ver))
252     return;
253   SET_BIT (processed, ver);
254
255   stmt = SSA_NAME_DEF_STMT (op);
256 #ifdef ENABLE_CHECKING
257   if (stmt == NULL)
258     abort ();
259 #endif
260
261   if (NECESSARY (stmt)
262       || IS_EMPTY_STMT (stmt))
263     return;
264
265   NECESSARY (stmt) = 1;
266   VARRAY_PUSH_TREE (worklist, stmt);
267 }
268 \f
269
270 /* Mark STMT as necessary if it is obviously is.  Add it to the worklist if
271    it can make other statements necessary.
272
273    If AGGRESSIVE is false, control statements are conservatively marked as
274    necessary.  */
275
276 static void
277 mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
278 {
279   v_may_def_optype v_may_defs;
280   v_must_def_optype v_must_defs;
281   stmt_ann_t ann;
282   tree op, def;
283   ssa_op_iter iter;
284
285   /* Statements that are implicitly live.  Most function calls, asm and return
286      statements are required.  Labels and BIND_EXPR nodes are kept because
287      they are control flow, and we have no way of knowing whether they can be
288      removed.  DCE can eliminate all the other statements in a block, and CFG
289      can then remove the block and labels.  */
290   switch (TREE_CODE (stmt))
291     {
292     case BIND_EXPR:
293     case LABEL_EXPR:
294     case CASE_LABEL_EXPR:
295       mark_stmt_necessary (stmt, false);
296       return;
297
298     case ASM_EXPR:
299     case RESX_EXPR:
300     case RETURN_EXPR:
301       mark_stmt_necessary (stmt, true);
302       return;
303
304     case CALL_EXPR:
305       /* Most, but not all function calls are required.  Function calls that
306          produce no result and have no side effects (i.e. const pure
307          functions) are unnecessary.  */
308       if (TREE_SIDE_EFFECTS (stmt))
309         mark_stmt_necessary (stmt, true);
310       return;
311
312     case MODIFY_EXPR:
313       op = get_call_expr_in (stmt);
314       if (op && TREE_SIDE_EFFECTS (op))
315         {
316           mark_stmt_necessary (stmt, true);
317           return;
318         }
319
320       /* These values are mildly magic bits of the EH runtime.  We can't
321          see the entire lifetime of these values until landing pads are
322          generated.  */
323       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR
324           || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR)
325         {
326           mark_stmt_necessary (stmt, true);
327           return;
328         }
329       break;
330
331     case GOTO_EXPR:
332       if (! simple_goto_p (stmt))
333         mark_stmt_necessary (stmt, true);
334       return;
335
336     case COND_EXPR:
337       if (GOTO_DESTINATION (COND_EXPR_THEN (stmt))
338           == GOTO_DESTINATION (COND_EXPR_ELSE (stmt)))
339         {
340           /* A COND_EXPR is obviously dead if the target labels are the same.
341              We cannot kill the statement at this point, so to prevent the
342              statement from being marked necessary, we replace the condition
343              with a constant.  The stmt is killed later on in cfg_cleanup.  */
344           COND_EXPR_COND (stmt) = integer_zero_node;
345           modify_stmt (stmt);
346           return;
347         }
348       /* Fall through.  */
349
350     case SWITCH_EXPR:
351       if (! aggressive)
352         mark_stmt_necessary (stmt, true);
353       break;
354
355     default:
356       break;
357     }
358
359   ann = stmt_ann (stmt);
360
361   /* If the statement has volatile operands, it needs to be preserved.
362      Same for statements that can alter control flow in unpredictable
363      ways.  */
364   if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt))
365     {
366       mark_stmt_necessary (stmt, true);
367       return;
368     }
369
370   get_stmt_operands (stmt);
371
372   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
373     {
374       if (is_global_var (SSA_NAME_VAR (def)))
375         {
376           mark_stmt_necessary (stmt, true);
377           return;
378         }
379     }
380
381   /* Check virtual definitions.  If we get here, the only virtual
382      definitions we should see are those generated by assignment
383      statements.  */
384   v_may_defs = V_MAY_DEF_OPS (ann);
385   v_must_defs = V_MUST_DEF_OPS (ann);
386   if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0)
387     {
388       tree lhs;
389
390 #if defined ENABLE_CHECKING
391       if (TREE_CODE (stmt) != MODIFY_EXPR)
392         abort ();
393 #endif
394
395       /* Note that we must not check the individual virtual operands
396          here.  In particular, if this is an aliased store, we could
397          end up with something like the following (SSA notation
398          redacted for brevity):
399
400                 foo (int *p, int i)
401                 {
402                   int x;
403                   p_1 = (i_2 > 3) ? &x : p_1;
404
405                   # x_4 = V_MAY_DEF <x_3>
406                   *p_1 = 5;
407
408                   return 2;
409                 }
410
411          Notice that the store to '*p_1' should be preserved, if we
412          were to check the virtual definitions in that store, we would
413          not mark it needed.  This is because 'x' is not a global
414          variable.
415
416          Therefore, we check the base address of the LHS.  If the
417          address is a pointer, we check if its name tag or type tag is
418          a global variable.  Otherwise, we check if the base variable
419          is a global.  */
420       lhs = TREE_OPERAND (stmt, 0);
421       if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
422         lhs = get_base_address (lhs);
423
424       if (lhs == NULL_TREE)
425         {
426           /* If LHS is NULL, it means that we couldn't get the base
427              address of the reference.  In which case, we should not
428              remove this store.  */
429           mark_stmt_necessary (stmt, true);
430         }
431       else if (DECL_P (lhs))
432         {
433           /* If the store is to a global symbol, we need to keep it.  */
434           if (is_global_var (lhs))
435             mark_stmt_necessary (stmt, true);
436         }
437       else if (TREE_CODE (lhs) == INDIRECT_REF)
438         {
439           tree ptr = TREE_OPERAND (lhs, 0);
440           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
441           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
442           tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
443
444           /* If either the name tag or the type tag for PTR is a
445              global variable, then the store is necessary.  */
446           if ((nmt && is_global_var (nmt))
447               || (tmt && is_global_var (tmt)))
448             {
449               mark_stmt_necessary (stmt, true);
450               return;
451             }
452         }
453       else
454         abort ();
455     }
456
457   return;
458 }
459 \f
460 /* Find obviously necessary statements.  These are things like most function
461    calls, and stores to file level variables.
462
463    If EL is NULL, control statements are conservatively marked as
464    necessary.  Otherwise it contains the list of edges used by control
465    dependence analysis.  */
466
467 static void
468 find_obviously_necessary_stmts (struct edge_list *el)
469 {
470   basic_block bb;
471   block_stmt_iterator i;
472   edge e;
473
474   FOR_EACH_BB (bb)
475     {
476       tree phi;
477
478       /* Check any PHI nodes in the block.  */
479       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
480         {
481           NECESSARY (phi) = 0;
482
483           /* PHIs for virtual variables do not directly affect code
484              generation and need not be considered inherently necessary
485              regardless of the bits set in their decl.
486
487              Thus, we only need to mark PHIs for real variables which
488              need their result preserved as being inherently necessary.  */
489           if (is_gimple_reg (PHI_RESULT (phi))
490               && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
491             mark_stmt_necessary (phi, true);
492         }
493
494       /* Check all statements in the block.  */
495       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
496         {
497           tree stmt = bsi_stmt (i);
498           NECESSARY (stmt) = 0;
499           mark_stmt_if_obviously_necessary (stmt, el != NULL);
500         }
501
502       /* Mark this basic block as `not visited'.  A block will be marked
503          visited when the edges that it is control dependent on have been
504          marked.  */
505       bb->flags &= ~BB_VISITED;
506     }
507
508   if (el)
509     {
510       /* Prevent the loops from being removed.  We must keep the infinite loops,
511          and we currently do not have a means to recognize the finite ones.  */
512       FOR_EACH_BB (bb)
513         {
514           for (e = bb->succ; e; e = e->succ_next)
515             if (e->flags & EDGE_DFS_BACK)
516               mark_control_dependent_edges_necessary (e->dest, el);
517         }
518     }
519 }
520 \f
521 /* Make corresponding control dependent edges necessary.  We only
522    have to do this once for each basic block, so we clear the bitmap
523    after we're done.  */
524 static void
525 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
526 {
527   int edge_number;
528
529 #ifdef ENABLE_CHECKING
530   if (bb == EXIT_BLOCK_PTR)
531     abort ();
532 #endif
533
534   if (bb == ENTRY_BLOCK_PTR)
535     return;
536
537   EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
538     {
539       tree t;
540       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
541
542       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
543         continue;
544       SET_BIT (last_stmt_necessary, cd_bb->index);
545
546       t = last_stmt (cd_bb);
547       if (t && is_ctrl_stmt (t))
548         mark_stmt_necessary (t, true);
549     });
550 }
551 \f
552 /* Propagate necessity using the operands of necessary statements.  Process
553    the uses on each statement in the worklist, and add all feeding statements
554    which contribute to the calculation of this value to the worklist.
555
556    In conservative mode, EL is NULL.  */
557
558 static void
559 propagate_necessity (struct edge_list *el)
560 {
561   tree i;
562   bool aggressive = (el ? true : false); 
563
564   if (dump_file && (dump_flags & TDF_DETAILS))
565     fprintf (dump_file, "\nProcessing worklist:\n");
566
567   while (VARRAY_ACTIVE_SIZE (worklist) > 0)
568     {
569       /* Take `i' from worklist.  */
570       i = VARRAY_TOP_TREE (worklist);
571       VARRAY_POP (worklist);
572
573       if (dump_file && (dump_flags & TDF_DETAILS))
574         {
575           fprintf (dump_file, "processing: ");
576           print_generic_stmt (dump_file, i, TDF_SLIM);
577           fprintf (dump_file, "\n");
578         }
579
580       if (aggressive)
581         {
582           /* Mark the last statements of the basic blocks that the block
583              containing `i' is control dependent on, but only if we haven't
584              already done so.  */
585           basic_block bb = bb_for_stmt (i);
586           if (! (bb->flags & BB_VISITED))
587             {
588               bb->flags |= BB_VISITED;
589               mark_control_dependent_edges_necessary (bb, el);
590             }
591         }
592
593       if (TREE_CODE (i) == PHI_NODE)
594         {
595           /* PHI nodes are somewhat special in that each PHI alternative has
596              data and control dependencies.  All the statements feeding the
597              PHI node's arguments are always necessary.  In aggressive mode,
598              we also consider the control dependent edges leading to the
599              predecessor block associated with each PHI alternative as
600              necessary.  */
601           int k;
602           for (k = 0; k < PHI_NUM_ARGS (i); k++)
603             {
604               tree arg = PHI_ARG_DEF (i, k);
605               if (TREE_CODE (arg) == SSA_NAME)
606                 mark_operand_necessary (arg);
607             }
608
609           if (aggressive)
610             {
611               for (k = 0; k < PHI_NUM_ARGS (i); k++)
612                 {
613                   basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
614                   if (! (arg_bb->flags & BB_VISITED))
615                     {
616                       arg_bb->flags |= BB_VISITED;
617                       mark_control_dependent_edges_necessary (arg_bb, el);
618                     }
619                 }
620             }
621         }
622       else
623         {
624           /* Propagate through the operands.  Examine all the USE, VUSE and
625              V_MAY_DEF operands in this statement.  Mark all the statements 
626              which feed this statement's uses as necessary.  */
627           ssa_op_iter iter;
628           tree use;
629
630           get_stmt_operands (i);
631
632           /* The operands of V_MAY_DEF expressions are also needed as they
633              represent potential definitions that may reach this
634              statement (V_MAY_DEF operands allow us to follow def-def 
635              links).  */
636
637           FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES)
638             mark_operand_necessary (use);
639         }
640     }
641 }
642 \f
643 /* Eliminate unnecessary statements. Any instruction not marked as necessary
644    contributes nothing to the program, and can be deleted.  */
645
646 static void
647 eliminate_unnecessary_stmts (void)
648 {
649   basic_block bb;
650   block_stmt_iterator i;
651
652   if (dump_file && (dump_flags & TDF_DETAILS))
653     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
654
655   clear_special_calls ();
656   FOR_EACH_BB (bb)
657     {
658       /* Remove dead PHI nodes.  */
659       remove_dead_phis (bb);
660
661       /* Remove dead statements.  */
662       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
663         {
664           tree t = bsi_stmt (i);
665
666           stats.total++;
667
668           /* If `i' is not necessary then remove it.  */
669           if (! NECESSARY (t))
670             remove_dead_stmt (&i, bb);
671           else
672             {
673               tree call = get_call_expr_in (t);
674               if (call)
675                 notice_special_calls (call);
676               bsi_next (&i);
677             }
678         }
679     }
680 }
681 \f
682 /* Remove dead PHI nodes from block BB.  */
683
684 static void
685 remove_dead_phis (basic_block bb)
686 {
687   tree prev, phi;
688
689   prev = NULL_TREE;
690   phi = phi_nodes (bb);
691   while (phi)
692     {
693       stats.total_phis++;
694
695       if (! NECESSARY (phi))
696         {
697           tree next = PHI_CHAIN (phi);
698
699           if (dump_file && (dump_flags & TDF_DETAILS))
700             {
701               fprintf (dump_file, "Deleting : ");
702               print_generic_stmt (dump_file, phi, TDF_SLIM);
703               fprintf (dump_file, "\n");
704             }
705
706           remove_phi_node (phi, prev, bb);
707           stats.removed_phis++;
708           phi = next;
709         }
710       else
711         {
712           prev = phi;
713           phi = PHI_CHAIN (phi);
714         }
715     }
716 }
717 \f
718 /* Remove dead statement pointed by iterator I.  Receives the basic block BB
719    containing I so that we don't have to look it up.  */
720
721 static void
722 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
723 {
724   tree t = bsi_stmt (*i);
725
726   if (dump_file && (dump_flags & TDF_DETAILS))
727     {
728       fprintf (dump_file, "Deleting : ");
729       print_generic_stmt (dump_file, t, TDF_SLIM);
730       fprintf (dump_file, "\n");
731     }
732
733   stats.removed++;
734
735   /* If we have determined that a conditional branch statement contributes
736      nothing to the program, then we not only remove it, but we also change
737      the flow graph so that the current block will simply fall-thru to its
738      immediate post-dominator.  The blocks we are circumventing will be
739      removed by cleaup_cfg if this change in the flow graph makes them
740      unreachable.  */
741   if (is_ctrl_stmt (t))
742     {
743       basic_block post_dom_bb;
744       edge e;
745 #ifdef ENABLE_CHECKING
746       /* The post dominance info has to be up-to-date.  */
747       if (dom_computed[CDI_POST_DOMINATORS] != DOM_OK)
748         abort ();
749 #endif
750       /* Get the immediate post dominator of bb.  */
751       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
752       /* Some blocks don't have an immediate post dominator.  This can happen
753          for example with infinite loops.  Removing an infinite loop is an
754          inappropriate transformation anyway...  */
755       if (! post_dom_bb)
756         {
757           bsi_next (i);
758           return;
759         }
760
761       /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
762       redirect_edge_and_branch (bb->succ, post_dom_bb);
763       PENDING_STMT (bb->succ) = NULL;
764
765       /* The edge is no longer associated with a conditional, so it does
766          not have TRUE/FALSE flags.  */
767       bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
768
769       /* If the edge reaches any block other than the exit, then it is a
770          fallthru edge; if it reaches the exit, then it is not a fallthru
771          edge.  */
772       if (post_dom_bb != EXIT_BLOCK_PTR)
773         bb->succ->flags |= EDGE_FALLTHRU;
774       else
775         bb->succ->flags &= ~EDGE_FALLTHRU;
776
777       /* Remove the remaining the outgoing edges.  */
778       for (e = bb->succ->succ_next; e != NULL;)
779         {
780           edge tmp = e;
781           e = e->succ_next;
782           remove_edge (tmp);
783         }
784     }
785
786   bsi_remove (i);
787   release_defs (t);
788 }
789 \f
790 /* Print out removed statement statistics.  */
791
792 static void
793 print_stats (void)
794 {
795   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
796     {
797       float percg;
798
799       percg = ((float) stats.removed / (float) stats.total) * 100;
800       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
801                stats.removed, stats.total, (int) percg);
802
803       if (stats.total_phis == 0)
804         percg = 0;
805       else
806         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
807
808       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
809                stats.removed_phis, stats.total_phis, (int) percg);
810     }
811 }
812 \f
813 /* Initialization for this pass.  Set up the used data structures.  */
814
815 static void
816 tree_dce_init (bool aggressive)
817 {
818   memset ((void *) &stats, 0, sizeof (stats));
819
820   if (aggressive)
821     {
822       int i;
823
824       control_dependence_map 
825         = xmalloc (last_basic_block * sizeof (bitmap));
826       for (i = 0; i < last_basic_block; ++i)
827         control_dependence_map[i] = BITMAP_XMALLOC ();
828
829       last_stmt_necessary = sbitmap_alloc (last_basic_block);
830       sbitmap_zero (last_stmt_necessary);
831     }
832
833   processed = sbitmap_alloc (num_ssa_names + 1);
834   sbitmap_zero (processed);
835
836   VARRAY_TREE_INIT (worklist, 64, "work list");
837 }
838
839 /* Cleanup after this pass.  */
840
841 static void
842 tree_dce_done (bool aggressive)
843 {
844   if (aggressive)
845     {
846       int i;
847
848       for (i = 0; i < last_basic_block; ++i)
849         BITMAP_XFREE (control_dependence_map[i]);
850       free (control_dependence_map);
851
852       sbitmap_free (last_stmt_necessary);
853     }
854
855   sbitmap_free (processed);
856 }
857 \f
858 /* Main routine to eliminate dead code.
859
860    AGGRESSIVE controls the aggressiveness of the algorithm.
861    In conservative mode, we ignore control dependence and simply declare
862    all but the most trivially dead branches necessary.  This mode is fast.
863    In aggressive mode, control dependences are taken into account, which
864    results in more dead code elimination, but at the cost of some time.
865
866    FIXME: Aggressive mode before PRE doesn't work currently because
867           the dominance info is not invalidated after DCE1.  This is
868           not an issue right now because we only run aggressive DCE
869           as the last tree SSA pass, but keep this in mind when you
870           start experimenting with pass ordering.  */
871
872 static void
873 perform_tree_ssa_dce (bool aggressive)
874 {
875   struct edge_list *el = NULL;
876
877   tree_dce_init (aggressive);
878
879   if (aggressive)
880     {
881       /* Compute control dependence.  */
882       timevar_push (TV_CONTROL_DEPENDENCES);
883       calculate_dominance_info (CDI_POST_DOMINATORS);
884       el = create_edge_list ();
885       find_all_control_dependences (el);
886       timevar_pop (TV_CONTROL_DEPENDENCES);
887
888       mark_dfs_back_edges ();
889     }
890
891   find_obviously_necessary_stmts (el);
892
893   propagate_necessity (el);
894
895   eliminate_unnecessary_stmts ();
896
897   if (aggressive)
898     free_dominance_info (CDI_POST_DOMINATORS);
899
900   cleanup_tree_cfg ();
901
902   /* Debugging dumps.  */
903   if (dump_file)
904     {
905       dump_function_to_file (current_function_decl, dump_file, dump_flags);
906       print_stats ();
907     }
908
909   tree_dce_done (aggressive);
910
911   free_edge_list (el);
912 }
913
914 /* Pass entry points.  */
915 static void
916 tree_ssa_dce (void)
917 {
918   perform_tree_ssa_dce (/*aggressive=*/false);
919 }
920
921 static void
922 tree_ssa_cd_dce (void)
923 {
924   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
925 }
926
927 static bool
928 gate_dce (void)
929 {
930   return flag_tree_dce != 0;
931 }
932
933 struct tree_opt_pass pass_dce =
934 {
935   "dce",                                /* name */
936   gate_dce,                             /* gate */
937   tree_ssa_dce,                         /* execute */
938   NULL,                                 /* sub */
939   NULL,                                 /* next */
940   0,                                    /* static_pass_number */
941   TV_TREE_DCE,                          /* tv_id */
942   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
943   0,                                    /* properties_provided */
944   0,                                    /* properties_destroyed */
945   0,                                    /* todo_flags_start */
946   TODO_ggc_collect | TODO_verify_ssa,   /* todo_flags_finish */
947   0                                     /* letter */
948 };
949
950 struct tree_opt_pass pass_cd_dce =
951 {
952   "cddce",                              /* name */
953   gate_dce,                             /* gate */
954   tree_ssa_cd_dce,                      /* execute */
955   NULL,                                 /* sub */
956   NULL,                                 /* next */
957   0,                                    /* static_pass_number */
958   TV_TREE_CD_DCE,                       /* tv_id */
959   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
960   0,                                    /* properties_provided */
961   0,                                    /* properties_destroyed */
962   0,                                    /* todo_flags_start */
963   TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
964                                         /* todo_flags_finish */
965   0                                     /* letter */
966 };
967