OSDN Git Service

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