OSDN Git Service

67d0472cc59668c603900702bc87d06b1dfd2b8c
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dce.c
1 /* Dead code elimination pass for the GNU compiler.
2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3    Free Software Foundation, Inc.
4    Contributed by Ben Elliston <bje@redhat.com>
5    and Andrew MacLeod <amacleod@redhat.com>
6    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
7  
8 This file is part of GCC.
9    
10 GCC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 3, or (at your option) any
13 later version.
14    
15 GCC is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 for more details.
19    
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3.  If not see
22 <http://www.gnu.org/licenses/>.  */
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 "ggc.h"
51
52 /* These RTL headers are needed for basic-block.h.  */
53 #include "rtl.h"
54 #include "tm_p.h"
55 #include "hard-reg-set.h"
56 #include "obstack.h"
57 #include "basic-block.h"
58
59 #include "tree.h"
60 #include "diagnostic.h"
61 #include "tree-flow.h"
62 #include "gimple.h"
63 #include "tree-dump.h"
64 #include "tree-pass.h"
65 #include "timevar.h"
66 #include "flags.h"
67 #include "cfgloop.h"
68 #include "tree-scalar-evolution.h"
69
70 static struct stmt_stats
71 {
72   int total;
73   int total_phis;
74   int removed;
75   int removed_phis;
76 } stats;
77
78 #define STMT_NECESSARY GF_PLF_1
79
80 static VEC(gimple,heap) *worklist;
81
82 /* Vector indicating an SSA name has already been processed and marked
83    as necessary.  */
84 static sbitmap processed;
85
86 /* Vector indicating that last_stmt if a basic block has already been
87    marked as necessary.  */
88 static sbitmap last_stmt_necessary;
89
90 /* Vector indicating that BB contains statements that are live.  */
91 static sbitmap bb_contains_live_stmts;
92
93 /* Before we can determine whether a control branch is dead, we need to
94    compute which blocks are control dependent on which edges.
95
96    We expect each block to be control dependent on very few edges so we
97    use a bitmap for each block recording its edges.  An array holds the
98    bitmap.  The Ith bit in the bitmap is set if that block is dependent
99    on the Ith edge.  */
100 static bitmap *control_dependence_map;
101
102 /* Vector indicating that a basic block has already had all the edges
103    processed that it is control dependent on.  */
104 static sbitmap visited_control_parents;
105
106 /* TRUE if this pass alters the CFG (by removing control statements).
107    FALSE otherwise.
108
109    If this pass alters the CFG, then it will arrange for the dominators
110    to be recomputed.  */
111 static bool cfg_altered;
112
113 /* Execute code that follows the macro for each edge (given number
114    EDGE_NUMBER within the CODE) for which the block with index N is
115    control dependent.  */
116 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER)        \
117   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,     \
118                             (EDGE_NUMBER), (BI))
119
120
121 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
122 static inline void
123 set_control_dependence_map_bit (basic_block bb, int edge_index)
124 {
125   if (bb == ENTRY_BLOCK_PTR)
126     return;
127   gcc_assert (bb != EXIT_BLOCK_PTR);
128   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
129 }
130
131 /* Clear all control dependences for block BB.  */
132 static inline void
133 clear_control_dependence_bitmap (basic_block bb)
134 {
135   bitmap_clear (control_dependence_map[bb->index]);
136 }
137
138
139 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
140    This function is necessary because some blocks have negative numbers.  */
141
142 static inline basic_block
143 find_pdom (basic_block block)
144 {
145   gcc_assert (block != ENTRY_BLOCK_PTR);
146
147   if (block == EXIT_BLOCK_PTR)
148     return EXIT_BLOCK_PTR;
149   else
150     {
151       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
152       if (! bb)
153         return EXIT_BLOCK_PTR;
154       return bb;
155     }
156 }
157
158
159 /* Determine all blocks' control dependences on the given edge with edge_list
160    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
161
162 static void
163 find_control_dependence (struct edge_list *el, int edge_index)
164 {
165   basic_block current_block;
166   basic_block ending_block;
167
168   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
169
170   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
171     ending_block = single_succ (ENTRY_BLOCK_PTR);
172   else
173     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
174
175   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
176        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
177        current_block = find_pdom (current_block))
178     {
179       edge e = INDEX_EDGE (el, edge_index);
180
181       /* For abnormal edges, we don't make current_block control
182          dependent because instructions that throw are always necessary
183          anyway.  */
184       if (e->flags & EDGE_ABNORMAL)
185         continue;
186
187       set_control_dependence_map_bit (current_block, edge_index);
188     }
189 }
190
191
192 /* Record all blocks' control dependences on all edges in the edge
193    list EL, ala Morgan, Section 3.6.  */
194
195 static void
196 find_all_control_dependences (struct edge_list *el)
197 {
198   int i;
199
200   for (i = 0; i < NUM_EDGES (el); ++i)
201     find_control_dependence (el, i);
202 }
203
204 /* If STMT is not already marked necessary, mark it, and add it to the
205    worklist if ADD_TO_WORKLIST is true.  */
206 static inline void
207 mark_stmt_necessary (gimple stmt, bool add_to_worklist)
208 {
209   gcc_assert (stmt);
210
211   if (gimple_plf (stmt, STMT_NECESSARY))
212     return;
213
214   if (dump_file && (dump_flags & TDF_DETAILS))
215     {
216       fprintf (dump_file, "Marking useful stmt: ");
217       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
218       fprintf (dump_file, "\n");
219     }
220
221   gimple_set_plf (stmt, STMT_NECESSARY, true);
222   if (add_to_worklist)
223     VEC_safe_push (gimple, heap, worklist, stmt);
224   if (bb_contains_live_stmts && !is_gimple_debug (stmt))
225     SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
226 }
227
228
229 /* Mark the statement defining operand OP as necessary.  */
230
231 static inline void
232 mark_operand_necessary (tree op)
233 {
234   gimple stmt;
235   int ver;
236
237   gcc_assert (op);
238
239   ver = SSA_NAME_VERSION (op);
240   if (TEST_BIT (processed, ver))
241     {
242       stmt = SSA_NAME_DEF_STMT (op);
243       gcc_assert (gimple_nop_p (stmt)
244                   || gimple_plf (stmt, STMT_NECESSARY));
245       return;
246     }
247   SET_BIT (processed, ver);
248
249   stmt = SSA_NAME_DEF_STMT (op);
250   gcc_assert (stmt);
251
252   if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
253     return;
254
255   if (dump_file && (dump_flags & TDF_DETAILS))
256     {
257       fprintf (dump_file, "marking necessary through ");
258       print_generic_expr (dump_file, op, 0);
259       fprintf (dump_file, " stmt ");
260       print_gimple_stmt (dump_file, stmt, 0, 0);
261     }
262
263   gimple_set_plf (stmt, STMT_NECESSARY, true);
264   if (bb_contains_live_stmts)
265     SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
266   VEC_safe_push (gimple, heap, worklist, stmt);
267 }
268
269
270 /* Mark STMT as necessary if it 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 (gimple stmt, bool aggressive)
278 {
279   tree lhs = NULL_TREE;
280   /* With non-call exceptions, we have to assume that all statements could
281      throw.  If a statement may throw, it is inherently necessary.  */
282   if (flag_non_call_exceptions
283       && stmt_could_throw_p (stmt))
284     {
285       mark_stmt_necessary (stmt, true);
286       return;
287     }
288
289   /* Statements that are implicitly live.  Most function calls, asm
290      and return statements are required.  Labels and GIMPLE_BIND nodes
291      are kept because they are control flow, and we have no way of
292      knowing whether they can be removed.  DCE can eliminate all the
293      other statements in a block, and CFG can then remove the block
294      and labels.  */
295   switch (gimple_code (stmt))
296     {
297     case GIMPLE_PREDICT:
298     case GIMPLE_LABEL:
299       mark_stmt_necessary (stmt, false);
300       return;
301
302     case GIMPLE_ASM:
303     case GIMPLE_RESX:
304     case GIMPLE_RETURN:
305       mark_stmt_necessary (stmt, true);
306       return;
307
308     case GIMPLE_CALL:
309       /* Most, but not all function calls are required.  Function calls that
310          produce no result and have no side effects (i.e. const pure
311          functions) are unnecessary.  */
312       if (gimple_has_side_effects (stmt))
313         {
314           mark_stmt_necessary (stmt, true);
315           return;
316         }
317       if (!gimple_call_lhs (stmt))
318         return;
319       lhs = gimple_call_lhs (stmt);
320       /* Fall through */
321
322     case GIMPLE_ASSIGN:
323       if (!lhs)
324         lhs = gimple_assign_lhs (stmt);
325       break;
326
327     case GIMPLE_DEBUG:
328       mark_stmt_necessary (stmt, false);
329       return;
330
331     case GIMPLE_GOTO:
332       gcc_assert (!simple_goto_p (stmt));
333       mark_stmt_necessary (stmt, true);
334       return;
335
336     case GIMPLE_COND:
337       gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
338       /* Fall through.  */
339
340     case GIMPLE_SWITCH:
341       if (! aggressive)
342         mark_stmt_necessary (stmt, true);
343       break;
344
345     default:
346       break;
347     }
348
349   /* If the statement has volatile operands, it needs to be preserved.
350      Same for statements that can alter control flow in unpredictable
351      ways.  */
352   if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
353     {
354       mark_stmt_necessary (stmt, true);
355       return;
356     }
357
358   if (is_hidden_global_store (stmt))
359     {
360       mark_stmt_necessary (stmt, true);
361       return;
362     }
363
364   return;
365 }
366
367
368 /* Make corresponding control dependent edges necessary.  We only
369    have to do this once for each basic block, so we clear the bitmap
370    after we're done.  */
371 static void
372 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
373 {
374   bitmap_iterator bi;
375   unsigned edge_number;
376
377   gcc_assert (bb != EXIT_BLOCK_PTR);
378
379   if (bb == ENTRY_BLOCK_PTR)
380     return;
381
382   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
383     {
384       gimple stmt;
385       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
386
387       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
388         continue;
389       SET_BIT (last_stmt_necessary, cd_bb->index);
390       SET_BIT (bb_contains_live_stmts, cd_bb->index);
391
392       stmt = last_stmt (cd_bb);
393       if (stmt && is_ctrl_stmt (stmt))
394         mark_stmt_necessary (stmt, true);
395     }
396 }
397
398
399 /* Find obviously necessary statements.  These are things like most function
400    calls, and stores to file level variables.
401
402    If EL is NULL, control statements are conservatively marked as
403    necessary.  Otherwise it contains the list of edges used by control
404    dependence analysis.  */
405
406 static void
407 find_obviously_necessary_stmts (struct edge_list *el)
408 {
409   basic_block bb;
410   gimple_stmt_iterator gsi;
411   edge e;
412   gimple phi, stmt;
413
414   FOR_EACH_BB (bb)
415     {
416       /* PHI nodes are never inherently necessary.  */
417       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
418         {
419           phi = gsi_stmt (gsi);
420           gimple_set_plf (phi, STMT_NECESSARY, false);
421         }
422
423       /* Check all statements in the block.  */
424       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
425         {
426           stmt = gsi_stmt (gsi);
427           gimple_set_plf (stmt, STMT_NECESSARY, false);
428           mark_stmt_if_obviously_necessary (stmt, el != NULL);
429         }
430     }
431
432   /* Pure and const functions are finite and thus have no infinite loops in
433      them.  */
434   if ((TREE_READONLY (current_function_decl)
435        || DECL_PURE_P (current_function_decl))
436       && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
437     return;
438
439   /* Prevent the empty possibly infinite loops from being removed.  */
440   if (el)
441     {
442       loop_iterator li;
443       struct loop *loop;
444       scev_initialize ();
445       if (mark_irreducible_loops ())
446         FOR_EACH_BB (bb)
447           {
448             edge_iterator ei;
449             FOR_EACH_EDGE (e, ei, bb->succs)
450               if ((e->flags & EDGE_DFS_BACK)
451                   && (e->flags & EDGE_IRREDUCIBLE_LOOP))
452                 {
453                   if (dump_file)
454                     fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
455                              e->src->index, e->dest->index);
456                   mark_control_dependent_edges_necessary (e->dest, el);
457                 }
458           }
459
460       FOR_EACH_LOOP (li, loop, 0)
461         if (!finite_loop_p (loop))
462           {
463             if (dump_file)
464               fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
465             mark_control_dependent_edges_necessary (loop->latch, el);
466           }
467       scev_finalize ();
468     }
469 }
470
471
472 /* Return true if REF is based on an aliased base, otherwise false.  */
473
474 static bool
475 ref_may_be_aliased (tree ref)
476 {
477   while (handled_component_p (ref))
478     ref = TREE_OPERAND (ref, 0);
479   return !(DECL_P (ref)
480            && !may_be_aliased (ref));
481 }
482
483 static bitmap visited = NULL;
484 static unsigned int longest_chain = 0;
485 static unsigned int total_chain = 0;
486 static bool chain_ovfl = false;
487
488 /* Worker for the walker that marks reaching definitions of REF,
489    which is based on a non-aliased decl, necessary.  It returns
490    true whenever the defining statement of the current VDEF is
491    a kill for REF, as no dominating may-defs are necessary for REF
492    anymore.  DATA points to cached get_ref_base_and_extent data for REF.  */
493
494 static bool
495 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
496                                         void *data ATTRIBUTE_UNUSED)
497 {
498   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
499
500   /* All stmts we visit are necessary.  */
501   mark_operand_necessary (vdef);
502
503   /* If the stmt lhs kills ref, then we can stop walking.  */
504   if (gimple_has_lhs (def_stmt)
505       && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
506     {
507       tree base, lhs = gimple_get_lhs (def_stmt);
508       HOST_WIDE_INT size, offset, max_size;
509       ao_ref_base (ref);
510       base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
511       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
512          so base == refd->base does not always hold.  */
513       if (base == ref->base)
514         {
515           /* For a must-alias check we need to be able to constrain
516              the accesses properly.  */
517           if (size != -1 && size == max_size
518               && ref->max_size != -1)
519             {
520               if (offset <= ref->offset
521                   && offset + size >= ref->offset + ref->max_size)
522                 return true;
523             }
524           /* Or they need to be exactly the same.  */
525           else if (ref->ref
526                    && operand_equal_p (ref->ref, lhs, 0))
527             return true;
528         }
529     }
530
531   /* Otherwise keep walking.  */
532   return false;
533 }
534
535 static void
536 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
537 {
538   unsigned int chain;
539   ao_ref refd;
540   gcc_assert (!chain_ovfl);
541   ao_ref_init (&refd, ref);
542   chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
543                               mark_aliased_reaching_defs_necessary_1,
544                               NULL, NULL);
545   if (chain > longest_chain)
546     longest_chain = chain;
547   total_chain += chain;
548 }
549
550 /* Worker for the walker that marks reaching definitions of REF, which
551    is not based on a non-aliased decl.  For simplicity we need to end
552    up marking all may-defs necessary that are not based on a non-aliased
553    decl.  The only job of this walker is to skip may-defs based on
554    a non-aliased decl.  */
555
556 static bool
557 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
558                                     tree vdef, void *data ATTRIBUTE_UNUSED)
559 {
560   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
561
562   /* We have to skip already visited (and thus necessary) statements
563      to make the chaining work after we dropped back to simple mode.  */
564   if (chain_ovfl
565       && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
566     {
567       gcc_assert (gimple_nop_p (def_stmt)
568                   || gimple_plf (def_stmt, STMT_NECESSARY));
569       return false;
570     }
571
572   /* We want to skip stores to non-aliased variables.  */
573   if (!chain_ovfl
574       && gimple_assign_single_p (def_stmt))
575     {
576       tree lhs = gimple_assign_lhs (def_stmt);
577       if (!ref_may_be_aliased (lhs))
578         return false;
579     }
580
581   mark_operand_necessary (vdef);
582
583   return false;
584 }
585
586 static void
587 mark_all_reaching_defs_necessary (gimple stmt)
588 {
589   walk_aliased_vdefs (NULL, gimple_vuse (stmt),
590                       mark_all_reaching_defs_necessary_1, NULL, &visited);
591 }
592
593 /* Return true for PHI nodes with one or identical arguments
594    can be removed.  */
595 static bool
596 degenerate_phi_p (gimple phi)
597 {
598   unsigned int i;
599   tree op = gimple_phi_arg_def (phi, 0);
600   for (i = 1; i < gimple_phi_num_args (phi); i++)
601     if (gimple_phi_arg_def (phi, i) != op)
602       return false;
603   return true;
604 }
605
606 /* Propagate necessity using the operands of necessary statements.
607    Process the uses on each statement in the worklist, and add all
608    feeding statements which contribute to the calculation of this
609    value to the worklist. 
610
611    In conservative mode, EL is NULL.  */
612
613 static void
614 propagate_necessity (struct edge_list *el)
615 {
616   gimple stmt;
617   bool aggressive = (el ? true : false); 
618
619   if (dump_file && (dump_flags & TDF_DETAILS))
620     fprintf (dump_file, "\nProcessing worklist:\n");
621
622   while (VEC_length (gimple, worklist) > 0)
623     {
624       /* Take STMT from worklist.  */
625       stmt = VEC_pop (gimple, worklist);
626
627       if (dump_file && (dump_flags & TDF_DETAILS))
628         {
629           fprintf (dump_file, "processing: ");
630           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
631           fprintf (dump_file, "\n");
632         }
633
634       if (aggressive)
635         {
636           /* Mark the last statements of the basic blocks that the block
637              containing STMT is control dependent on, but only if we haven't
638              already done so.  */
639           basic_block bb = gimple_bb (stmt);
640           if (bb != ENTRY_BLOCK_PTR
641               && ! TEST_BIT (visited_control_parents, bb->index))
642             {
643               SET_BIT (visited_control_parents, bb->index);
644               mark_control_dependent_edges_necessary (bb, el);
645             }
646         }
647
648       if (gimple_code (stmt) == GIMPLE_PHI
649           /* We do not process virtual PHI nodes nor do we track their
650              necessity.  */
651           && is_gimple_reg (gimple_phi_result (stmt)))
652         {
653           /* PHI nodes are somewhat special in that each PHI alternative has
654              data and control dependencies.  All the statements feeding the
655              PHI node's arguments are always necessary.  In aggressive mode,
656              we also consider the control dependent edges leading to the
657              predecessor block associated with each PHI alternative as
658              necessary.  */
659           size_t k;
660
661           for (k = 0; k < gimple_phi_num_args (stmt); k++)
662             {
663               tree arg = PHI_ARG_DEF (stmt, k);
664               if (TREE_CODE (arg) == SSA_NAME)
665                 mark_operand_necessary (arg);
666             }
667
668           if (aggressive && !degenerate_phi_p (stmt))
669             {
670               for (k = 0; k < gimple_phi_num_args (stmt); k++)
671                 {
672                   basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
673                   if (arg_bb != ENTRY_BLOCK_PTR
674                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
675                     {
676                       SET_BIT (visited_control_parents, arg_bb->index);
677                       mark_control_dependent_edges_necessary (arg_bb, el);
678                     }
679                 }
680             }
681         }
682       else
683         {
684           /* Propagate through the operands.  Examine all the USE, VUSE and
685              VDEF operands in this statement.  Mark all the statements 
686              which feed this statement's uses as necessary.  */
687           ssa_op_iter iter;
688           tree use;
689
690           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
691             mark_operand_necessary (use);
692
693           use = gimple_vuse (stmt);
694           if (!use)
695             continue;
696
697           /* If we dropped to simple mode make all immediately
698              reachable definitions necessary.  */
699           if (chain_ovfl)
700             {
701               mark_all_reaching_defs_necessary (stmt);
702               continue;
703             }
704
705           /* For statements that may load from memory (have a VUSE) we
706              have to mark all reaching (may-)definitions as necessary.
707              We partition this task into two cases:
708               1) explicit loads based on decls that are not aliased
709               2) implicit loads (like calls) and explicit loads not
710                  based on decls that are not aliased (like indirect
711                  references or loads from globals)
712              For 1) we mark all reaching may-defs as necessary, stopping
713              at dominating kills.  For 2) we want to mark all dominating
714              references necessary, but non-aliased ones which we handle
715              in 1).  By keeping a global visited bitmap for references
716              we walk for 2) we avoid quadratic behavior for those.  */
717
718           if (is_gimple_call (stmt))
719             {
720               tree callee = gimple_call_fndecl (stmt);
721               unsigned i;
722
723               /* Calls to functions that are merely acting as barriers
724                  or that only store to memory do not make any previous
725                  stores necessary.  */
726               if (callee != NULL_TREE
727                   && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
728                   && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
729                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
730                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
731                 continue;
732
733               /* Calls implicitly load from memory, their arguments
734                  in addition may explicitly perform memory loads.  */
735               mark_all_reaching_defs_necessary (stmt);
736               for (i = 0; i < gimple_call_num_args (stmt); ++i)
737                 {
738                   tree arg = gimple_call_arg (stmt, i);
739                   if (TREE_CODE (arg) == SSA_NAME
740                       || is_gimple_min_invariant (arg))
741                     continue;
742                   if (!ref_may_be_aliased (arg))
743                     mark_aliased_reaching_defs_necessary (stmt, arg);
744                 }
745             }
746           else if (gimple_assign_single_p (stmt))
747             {
748               tree rhs;
749               bool rhs_aliased = false;
750               /* If this is a load mark things necessary.  */
751               rhs = gimple_assign_rhs1 (stmt);
752               if (TREE_CODE (rhs) != SSA_NAME
753                   && !is_gimple_min_invariant (rhs))
754                 {
755                   if (!ref_may_be_aliased (rhs))
756                     mark_aliased_reaching_defs_necessary (stmt, rhs);
757                   else
758                     rhs_aliased = true;
759                 }
760               if (rhs_aliased)
761                 mark_all_reaching_defs_necessary (stmt);
762             }
763           else if (gimple_code (stmt) == GIMPLE_RETURN)
764             {
765               tree rhs = gimple_return_retval (stmt);
766               /* A return statement may perform a load.  */
767               if (TREE_CODE (rhs) != SSA_NAME
768                   && !is_gimple_min_invariant (rhs))
769                 {
770                   if (!ref_may_be_aliased (rhs))
771                     mark_aliased_reaching_defs_necessary (stmt, rhs);
772                   else
773                     mark_all_reaching_defs_necessary (stmt);
774                 }
775             }
776           else if (gimple_code (stmt) == GIMPLE_ASM)
777             {
778               unsigned i;
779               mark_all_reaching_defs_necessary (stmt);
780               /* Inputs may perform loads.  */
781               for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
782                 {
783                   tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
784                   if (TREE_CODE (op) != SSA_NAME
785                       && !is_gimple_min_invariant (op)
786                       && !ref_may_be_aliased (op))
787                     mark_aliased_reaching_defs_necessary (stmt, op);
788                 }
789             }
790           else
791             gcc_unreachable ();
792
793           /* If we over-used our alias oracle budget drop to simple
794              mode.  The cost metric allows quadratic behavior up to
795              a constant maximal chain and after that falls back to
796              super-linear complexity.  */
797           if (longest_chain > 256
798               && total_chain > 256 * longest_chain)
799             {
800               chain_ovfl = true;
801               if (visited)
802                 bitmap_clear (visited);
803             }
804         }
805     }
806 }
807
808 /* Replace all uses of result of PHI by underlying variable and mark it
809    for renaming.  */
810
811 void
812 mark_virtual_phi_result_for_renaming (gimple phi)
813 {
814   bool used = false;
815   imm_use_iterator iter;
816   use_operand_p use_p;
817   gimple stmt;
818   tree result_ssa, result_var;
819
820   if (dump_file && (dump_flags & TDF_DETAILS))
821     {
822       fprintf (dump_file, "Marking result for renaming : ");
823       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
824       fprintf (dump_file, "\n");
825     }
826
827   result_ssa = gimple_phi_result (phi);
828   result_var = SSA_NAME_VAR (result_ssa);
829   FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
830     {
831       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
832         SET_USE (use_p, result_var);
833       update_stmt (stmt);
834       used = true;
835     }
836   if (used)
837     mark_sym_for_renaming (result_var);
838 }
839
840 /* Remove dead PHI nodes from block BB.  */
841
842 static bool
843 remove_dead_phis (basic_block bb)
844 {
845   bool something_changed = false;
846   gimple_seq phis;
847   gimple phi;
848   gimple_stmt_iterator gsi;
849   phis = phi_nodes (bb);
850
851   for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
852     {
853       stats.total_phis++;
854       phi = gsi_stmt (gsi);
855
856       /* We do not track necessity of virtual PHI nodes.  Instead do
857          very simple dead PHI removal here.  */
858       if (!is_gimple_reg (gimple_phi_result (phi)))
859         {
860           /* Virtual PHI nodes with one or identical arguments
861              can be removed.  */
862           if (degenerate_phi_p (phi))
863             {
864               tree vdef = gimple_phi_result (phi);
865               tree vuse = gimple_phi_arg_def (phi, 0);
866
867               use_operand_p use_p;
868               imm_use_iterator iter;
869               gimple use_stmt;
870               FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
871                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
872                   SET_USE (use_p, vuse);
873               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
874                   && TREE_CODE (vuse) == SSA_NAME)
875                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
876             }
877           else
878             gimple_set_plf (phi, STMT_NECESSARY, true);
879         }
880
881       if (!gimple_plf (phi, STMT_NECESSARY))
882         {
883           something_changed = true;
884           if (dump_file && (dump_flags & TDF_DETAILS))
885             {
886               fprintf (dump_file, "Deleting : ");
887               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
888               fprintf (dump_file, "\n");
889             }
890
891           remove_phi_node (&gsi, true);
892           stats.removed_phis++;
893           continue;
894         }
895
896       gsi_next (&gsi);
897     }
898   return something_changed;
899 }
900
901 /* Find first live post dominator of BB.  */
902
903 static basic_block
904 get_live_post_dom (basic_block bb)
905 {
906   basic_block post_dom_bb;
907
908
909   /* The post dominance info has to be up-to-date.  */
910   gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
911
912   /* Get the immediate post dominator of bb.  */
913   post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
914   /* And look for first live one.  */
915   while (post_dom_bb != EXIT_BLOCK_PTR
916          && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
917     post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
918
919   return post_dom_bb;
920 }
921
922 /* Forward edge E to respective POST_DOM_BB and update PHIs.  */
923
924 static edge
925 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
926 {
927   gimple_stmt_iterator gsi;
928   edge e2 = NULL;
929   edge_iterator ei;
930
931   if (dump_file && (dump_flags & TDF_DETAILS))
932     fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
933              e->dest->index, post_dom_bb->index);
934
935   e2 = redirect_edge_and_branch (e, post_dom_bb);
936   cfg_altered = true;
937
938   /* If edge was already around, no updating is neccesary.  */
939   if (e2 != e)
940     return e2;
941
942   if (phi_nodes (post_dom_bb))
943     {
944       /* We are sure that for every live PHI we are seeing control dependent BB.
945          This means that we can look up the end of control dependent path leading
946          to the PHI itself.  */
947       FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
948         if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
949           break;
950       for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
951         {
952           gimple phi = gsi_stmt (gsi);
953           tree op;
954           source_location locus;
955
956           /* Dead PHI do not imply control dependency.  */
957           if (!gimple_plf (phi, STMT_NECESSARY)
958               && is_gimple_reg (gimple_phi_result (phi)))
959             {
960               gsi_next (&gsi);
961               continue;
962             }
963           if (gimple_phi_arg_def (phi, e->dest_idx))
964             {
965               gsi_next (&gsi);
966               continue;
967             }
968
969           /* We didn't find edge to update.  This can happen for PHIs on virtuals
970              since there is no control dependency relation on them.  We are lost
971              here and must force renaming of the symbol.  */
972           if (!is_gimple_reg (gimple_phi_result (phi)))
973             {
974               mark_virtual_phi_result_for_renaming (phi);
975               remove_phi_node (&gsi, true);
976               continue;
977             }
978           if (!e2)
979             {
980               op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0);
981               locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0);
982             }
983           else
984             {
985               op = gimple_phi_arg_def (phi, e2->dest_idx);
986               locus = gimple_phi_arg_location (phi, e2->dest_idx);
987             }
988           add_phi_arg (phi, op, e, locus);
989           gcc_assert (e2 || degenerate_phi_p (phi));
990           gsi_next (&gsi);
991         }
992     }
993   return e;
994 }
995
996 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
997    containing I so that we don't have to look it up.  */
998
999 static void
1000 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
1001 {
1002   gimple stmt = gsi_stmt (*i);
1003
1004   if (dump_file && (dump_flags & TDF_DETAILS))
1005     {
1006       fprintf (dump_file, "Deleting : ");
1007       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1008       fprintf (dump_file, "\n");
1009     }
1010
1011   stats.removed++;
1012
1013   /* If we have determined that a conditional branch statement contributes
1014      nothing to the program, then we not only remove it, but we also change
1015      the flow graph so that the current block will simply fall-thru to its
1016      immediate post-dominator.  The blocks we are circumventing will be
1017      removed by cleanup_tree_cfg if this change in the flow graph makes them
1018      unreachable.  */
1019   if (is_ctrl_stmt (stmt))
1020     {
1021       basic_block post_dom_bb;
1022       edge e, e2;
1023       edge_iterator ei;
1024
1025       post_dom_bb = get_live_post_dom (bb);
1026
1027       e = find_edge (bb, post_dom_bb);
1028
1029       /* If edge is already there, try to use it.  This avoids need to update
1030          PHI nodes.  Also watch for cases where post dominator does not exists
1031          or is exit block.  These can happen for infinite loops as we create
1032          fake edges in the dominator tree.  */
1033       if (e)
1034         ;
1035       else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
1036         e = EDGE_SUCC (bb, 0);
1037       else
1038         e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1039       gcc_assert (e);
1040       e->probability = REG_BR_PROB_BASE;
1041       e->count = bb->count;
1042
1043       /* The edge is no longer associated with a conditional, so it does
1044          not have TRUE/FALSE flags.  */
1045       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1046
1047       /* The lone outgoing edge from BB will be a fallthru edge.  */
1048       e->flags |= EDGE_FALLTHRU;
1049
1050       /* Remove the remaining outgoing edges.  */
1051       for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1052         if (e != e2)
1053           {
1054             cfg_altered = true;
1055             remove_edge (e2);
1056           }
1057         else
1058           ei_next (&ei);
1059     }
1060
1061   unlink_stmt_vdef (stmt);
1062   gsi_remove (i, true);  
1063   release_defs (stmt); 
1064 }
1065
1066 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1067    contributes nothing to the program, and can be deleted.  */
1068
1069 static bool
1070 eliminate_unnecessary_stmts (void)
1071 {
1072   bool something_changed = false;
1073   basic_block bb;
1074   gimple_stmt_iterator gsi;
1075   gimple stmt;
1076   tree call;
1077   VEC (basic_block, heap) *h;
1078
1079   if (dump_file && (dump_flags & TDF_DETAILS))
1080     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1081
1082   clear_special_calls ();
1083
1084   /* Walking basic blocks and statements in reverse order avoids
1085      releasing SSA names before any other DEFs that refer to them are
1086      released.  This helps avoid loss of debug information, as we get
1087      a chance to propagate all RHSs of removed SSAs into debug uses,
1088      rather than only the latest ones.  E.g., consider:
1089
1090      x_3 = y_1 + z_2;
1091      a_5 = x_3 - b_4;
1092      # DEBUG a => a_5
1093
1094      If we were to release x_3 before a_5, when we reached a_5 and
1095      tried to substitute it into the debug stmt, we'd see x_3 there,
1096      but x_3's DEF, type, etc would have already been disconnected.
1097      By going backwards, the debug stmt first changes to:
1098
1099      # DEBUG a => x_3 - b_4
1100
1101      and then to:
1102
1103      # DEBUG a => y_1 + z_2 - b_4
1104
1105      as desired.  */
1106   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1107   h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
1108
1109   while (VEC_length (basic_block, h))
1110     {
1111       bb = VEC_pop (basic_block, h);
1112
1113       /* Remove dead statements.  */
1114       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1115         {
1116           stmt = gsi_stmt (gsi);
1117
1118           stats.total++;
1119
1120           /* If GSI is not necessary then remove it.  */
1121           if (!gimple_plf (stmt, STMT_NECESSARY))
1122             {
1123               remove_dead_stmt (&gsi, bb);
1124               something_changed = true;
1125
1126               /* If stmt was the last stmt in the block, we want to
1127                  move gsi to the stmt that became the last stmt, but
1128                  gsi_prev would crash.  */
1129               if (gsi_end_p (gsi))
1130                 gsi = gsi_last_bb (bb);
1131               else
1132                 gsi_prev (&gsi);
1133             }
1134           else if (is_gimple_call (stmt))
1135             {
1136               call = gimple_call_fndecl (stmt);
1137               if (call)
1138                 {
1139                   tree name;
1140
1141                   /* When LHS of var = call (); is dead, simplify it into
1142                      call (); saving one operand.  */
1143                   name = gimple_call_lhs (stmt);
1144                   if (name && TREE_CODE (name) == SSA_NAME
1145                            && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1146                     {
1147                       something_changed = true;
1148                       if (dump_file && (dump_flags & TDF_DETAILS))
1149                         {
1150                           fprintf (dump_file, "Deleting LHS of call: ");
1151                           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1152                           fprintf (dump_file, "\n");
1153                         }
1154                       
1155                       gimple_call_set_lhs (stmt, NULL_TREE);
1156                       maybe_clean_or_replace_eh_stmt (stmt, stmt);
1157                       update_stmt (stmt);
1158                       release_ssa_name (name);
1159                     }
1160                   notice_special_calls (stmt);
1161                 }
1162               gsi_prev (&gsi);
1163             }
1164           else
1165             gsi_prev (&gsi);
1166         }
1167     }
1168
1169   VEC_free (basic_block, heap, h);
1170
1171   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1172      rendered some PHI nodes unreachable while they are still in use.
1173      Mark them for renaming.  */
1174   if (cfg_altered)
1175     {
1176       basic_block prev_bb;
1177
1178       find_unreachable_blocks ();
1179
1180       /* Delete all unreachable basic blocks in reverse dominator order.  */
1181       for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
1182         {
1183           prev_bb = bb->prev_bb;
1184
1185           if (!TEST_BIT (bb_contains_live_stmts, bb->index)
1186               || !(bb->flags & BB_REACHABLE))
1187             {
1188               for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1189                 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1190                   {
1191                     bool found = false;
1192                     imm_use_iterator iter;
1193
1194                     FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
1195                       {
1196                         if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1197                           continue;
1198                         if (gimple_code (stmt) == GIMPLE_PHI
1199                             || gimple_plf (stmt, STMT_NECESSARY))
1200                           {
1201                             found = true;
1202                             BREAK_FROM_IMM_USE_STMT (iter);
1203                           }
1204                       }
1205                     if (found)
1206                       mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
1207                   }
1208
1209               if (!(bb->flags & BB_REACHABLE))
1210                 {
1211                   /* Speed up the removal of blocks that don't
1212                      dominate others.  Walking backwards, this should
1213                      be the common case.  ??? Do we need to recompute
1214                      dominators because of cfg_altered?  */
1215                   if (!MAY_HAVE_DEBUG_STMTS
1216                       || !first_dom_son (CDI_DOMINATORS, bb))
1217                     delete_basic_block (bb);
1218                   else
1219                     {
1220                       h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1221
1222                       while (VEC_length (basic_block, h))
1223                         {
1224                           bb = VEC_pop (basic_block, h);
1225                           prev_bb = bb->prev_bb;
1226                           /* Rearrangements to the CFG may have failed
1227                              to update the dominators tree, so that
1228                              formerly-dominated blocks are now
1229                              otherwise reachable.  */
1230                           if (!!(bb->flags & BB_REACHABLE))
1231                             continue;
1232                           delete_basic_block (bb);
1233                         }
1234
1235                       VEC_free (basic_block, heap, h);
1236                     }
1237                 }
1238             }
1239         }
1240     }
1241   FOR_EACH_BB (bb)
1242     {
1243       /* Remove dead PHI nodes.  */
1244       something_changed |= remove_dead_phis (bb);
1245     }
1246
1247   return something_changed;
1248 }
1249
1250
1251 /* Print out removed statement statistics.  */
1252
1253 static void
1254 print_stats (void)
1255 {
1256   float percg;
1257
1258   percg = ((float) stats.removed / (float) stats.total) * 100;
1259   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1260            stats.removed, stats.total, (int) percg);
1261
1262   if (stats.total_phis == 0)
1263     percg = 0;
1264   else
1265     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1266
1267   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1268            stats.removed_phis, stats.total_phis, (int) percg);
1269 }
1270
1271 /* Initialization for this pass.  Set up the used data structures.  */
1272
1273 static void
1274 tree_dce_init (bool aggressive)
1275 {
1276   memset ((void *) &stats, 0, sizeof (stats));
1277
1278   if (aggressive)
1279     {
1280       int i;
1281
1282       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1283       for (i = 0; i < last_basic_block; ++i)
1284         control_dependence_map[i] = BITMAP_ALLOC (NULL);
1285
1286       last_stmt_necessary = sbitmap_alloc (last_basic_block);
1287       sbitmap_zero (last_stmt_necessary);
1288       bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1289       sbitmap_zero (bb_contains_live_stmts);
1290     }
1291
1292   processed = sbitmap_alloc (num_ssa_names + 1);
1293   sbitmap_zero (processed);
1294
1295   worklist = VEC_alloc (gimple, heap, 64);
1296   cfg_altered = false;
1297 }
1298
1299 /* Cleanup after this pass.  */
1300
1301 static void
1302 tree_dce_done (bool aggressive)
1303 {
1304   if (aggressive)
1305     {
1306       int i;
1307
1308       for (i = 0; i < last_basic_block; ++i)
1309         BITMAP_FREE (control_dependence_map[i]);
1310       free (control_dependence_map);
1311
1312       sbitmap_free (visited_control_parents);
1313       sbitmap_free (last_stmt_necessary);
1314       sbitmap_free (bb_contains_live_stmts);
1315       bb_contains_live_stmts = NULL;
1316     }
1317
1318   sbitmap_free (processed);
1319
1320   VEC_free (gimple, heap, worklist);
1321 }
1322
1323 /* Main routine to eliminate dead code.
1324
1325    AGGRESSIVE controls the aggressiveness of the algorithm.
1326    In conservative mode, we ignore control dependence and simply declare
1327    all but the most trivially dead branches necessary.  This mode is fast.
1328    In aggressive mode, control dependences are taken into account, which
1329    results in more dead code elimination, but at the cost of some time.
1330
1331    FIXME: Aggressive mode before PRE doesn't work currently because
1332           the dominance info is not invalidated after DCE1.  This is
1333           not an issue right now because we only run aggressive DCE
1334           as the last tree SSA pass, but keep this in mind when you
1335           start experimenting with pass ordering.  */
1336
1337 static unsigned int
1338 perform_tree_ssa_dce (bool aggressive)
1339 {
1340   struct edge_list *el = NULL;
1341   bool something_changed = 0;
1342
1343   /* Preheaders are needed for SCEV to work.
1344      Simple lateches and recorded exits improve chances that loop will
1345      proved to be finite in testcases such as in loop-15.c and loop-24.c  */
1346   if (aggressive)
1347     loop_optimizer_init (LOOPS_NORMAL
1348                          | LOOPS_HAVE_RECORDED_EXITS);
1349
1350   tree_dce_init (aggressive);
1351
1352   if (aggressive)
1353     {
1354       /* Compute control dependence.  */
1355       timevar_push (TV_CONTROL_DEPENDENCES);
1356       calculate_dominance_info (CDI_POST_DOMINATORS);
1357       el = create_edge_list ();
1358       find_all_control_dependences (el);
1359       timevar_pop (TV_CONTROL_DEPENDENCES);
1360
1361       visited_control_parents = sbitmap_alloc (last_basic_block);
1362       sbitmap_zero (visited_control_parents);
1363
1364       mark_dfs_back_edges ();
1365     }
1366
1367   find_obviously_necessary_stmts (el);
1368
1369   if (aggressive)
1370     loop_optimizer_finalize ();
1371
1372   longest_chain = 0;
1373   total_chain = 0;
1374   chain_ovfl = false;
1375   propagate_necessity (el);
1376   BITMAP_FREE (visited);
1377
1378   something_changed |= eliminate_unnecessary_stmts ();
1379   something_changed |= cfg_altered;
1380
1381   /* We do not update postdominators, so free them unconditionally.  */
1382   free_dominance_info (CDI_POST_DOMINATORS);
1383
1384   /* If we removed paths in the CFG, then we need to update
1385      dominators as well.  I haven't investigated the possibility
1386      of incrementally updating dominators.  */
1387   if (cfg_altered)
1388     free_dominance_info (CDI_DOMINATORS);
1389
1390   statistics_counter_event (cfun, "Statements deleted", stats.removed);
1391   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1392
1393   /* Debugging dumps.  */
1394   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1395     print_stats ();
1396
1397   tree_dce_done (aggressive);
1398
1399   free_edge_list (el);
1400
1401   if (something_changed)
1402     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect 
1403             | TODO_remove_unused_locals);
1404   else
1405     return 0;
1406 }
1407
1408 /* Pass entry points.  */
1409 static unsigned int
1410 tree_ssa_dce (void)
1411 {
1412   return perform_tree_ssa_dce (/*aggressive=*/false);
1413 }
1414
1415 static unsigned int
1416 tree_ssa_dce_loop (void)
1417 {
1418   unsigned int todo;
1419   todo = perform_tree_ssa_dce (/*aggressive=*/false);
1420   if (todo)
1421     {
1422       free_numbers_of_iterations_estimates ();
1423       scev_reset ();
1424     }
1425   return todo;
1426 }
1427
1428 static unsigned int
1429 tree_ssa_cd_dce (void)
1430 {
1431   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1432 }
1433
1434 static bool
1435 gate_dce (void)
1436 {
1437   return flag_tree_dce != 0;
1438 }
1439
1440 struct gimple_opt_pass pass_dce =
1441 {
1442  {
1443   GIMPLE_PASS,
1444   "dce",                                /* name */
1445   gate_dce,                             /* gate */
1446   tree_ssa_dce,                         /* execute */
1447   NULL,                                 /* sub */
1448   NULL,                                 /* next */
1449   0,                                    /* static_pass_number */
1450   TV_TREE_DCE,                          /* tv_id */
1451   PROP_cfg | PROP_ssa,                  /* properties_required */
1452   0,                                    /* properties_provided */
1453   0,                                    /* properties_destroyed */
1454   0,                                    /* todo_flags_start */
1455   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1456  }
1457 };
1458
1459 struct gimple_opt_pass pass_dce_loop =
1460 {
1461  {
1462   GIMPLE_PASS,
1463   "dceloop",                            /* name */
1464   gate_dce,                             /* gate */
1465   tree_ssa_dce_loop,                    /* execute */
1466   NULL,                                 /* sub */
1467   NULL,                                 /* next */
1468   0,                                    /* static_pass_number */
1469   TV_TREE_DCE,                          /* tv_id */
1470   PROP_cfg | PROP_ssa,                  /* properties_required */
1471   0,                                    /* properties_provided */
1472   0,                                    /* properties_destroyed */
1473   0,                                    /* todo_flags_start */
1474   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1475  }
1476 };
1477
1478 struct gimple_opt_pass pass_cd_dce =
1479 {
1480  {
1481   GIMPLE_PASS,
1482   "cddce",                              /* name */
1483   gate_dce,                             /* gate */
1484   tree_ssa_cd_dce,                      /* execute */
1485   NULL,                                 /* sub */
1486   NULL,                                 /* next */
1487   0,                                    /* static_pass_number */
1488   TV_TREE_CD_DCE,                       /* tv_id */
1489   PROP_cfg | PROP_ssa,                  /* properties_required */
1490   0,                                    /* properties_provided */
1491   0,                                    /* properties_destroyed */
1492   0,                                    /* todo_flags_start */
1493   TODO_dump_func | TODO_verify_ssa
1494   | TODO_verify_flow                    /* todo_flags_finish */
1495  }
1496 };