2010-07-27 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc/alias-decl.git] / gcc / tree-ssa-dce.c
blobedec49d374ffbcd85f7ae0cd78dd8a2f4a32455e
1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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.
8 This file is part of GCC.
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.
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.
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/>. */
24 /* Dead code elimination.
26 References:
28 Building an Optimizing Compiler,
29 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
31 Advanced Compiler Design and Implementation,
32 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
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.
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. */
46 #include "config.h"
47 #include "system.h"
48 #include "coretypes.h"
49 #include "tm.h"
51 #include "tree.h"
52 #include "tree-pretty-print.h"
53 #include "gimple-pretty-print.h"
54 #include "basic-block.h"
55 #include "tree-flow.h"
56 #include "gimple.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
59 #include "timevar.h"
60 #include "flags.h"
61 #include "cfgloop.h"
62 #include "tree-scalar-evolution.h"
64 static struct stmt_stats
66 int total;
67 int total_phis;
68 int removed;
69 int removed_phis;
70 } stats;
72 #define STMT_NECESSARY GF_PLF_1
74 static VEC(gimple,heap) *worklist;
76 /* Vector indicating an SSA name has already been processed and marked
77 as necessary. */
78 static sbitmap processed;
80 /* Vector indicating that the last statement of a basic block has already
81 been marked as necessary. */
82 static sbitmap last_stmt_necessary;
84 /* Vector indicating that BB contains statements that are live. */
85 static sbitmap bb_contains_live_stmts;
87 /* Before we can determine whether a control branch is dead, we need to
88 compute which blocks are control dependent on which edges.
90 We expect each block to be control dependent on very few edges so we
91 use a bitmap for each block recording its edges. An array holds the
92 bitmap. The Ith bit in the bitmap is set if that block is dependent
93 on the Ith edge. */
94 static bitmap *control_dependence_map;
96 /* Vector indicating that a basic block has already had all the edges
97 processed that it is control dependent on. */
98 static sbitmap visited_control_parents;
100 /* TRUE if this pass alters the CFG (by removing control statements).
101 FALSE otherwise.
103 If this pass alters the CFG, then it will arrange for the dominators
104 to be recomputed. */
105 static bool cfg_altered;
107 /* Execute code that follows the macro for each edge (given number
108 EDGE_NUMBER within the CODE) for which the block with index N is
109 control dependent. */
110 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
111 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
112 (EDGE_NUMBER), (BI))
115 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
116 static inline void
117 set_control_dependence_map_bit (basic_block bb, int edge_index)
119 if (bb == ENTRY_BLOCK_PTR)
120 return;
121 gcc_assert (bb != EXIT_BLOCK_PTR);
122 bitmap_set_bit (control_dependence_map[bb->index], edge_index);
125 /* Clear all control dependences for block BB. */
126 static inline void
127 clear_control_dependence_bitmap (basic_block bb)
129 bitmap_clear (control_dependence_map[bb->index]);
133 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
134 This function is necessary because some blocks have negative numbers. */
136 static inline basic_block
137 find_pdom (basic_block block)
139 gcc_assert (block != ENTRY_BLOCK_PTR);
141 if (block == EXIT_BLOCK_PTR)
142 return EXIT_BLOCK_PTR;
143 else
145 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
146 if (! bb)
147 return EXIT_BLOCK_PTR;
148 return bb;
153 /* Determine all blocks' control dependences on the given edge with edge_list
154 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
156 static void
157 find_control_dependence (struct edge_list *el, int edge_index)
159 basic_block current_block;
160 basic_block ending_block;
162 gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
164 if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
165 ending_block = single_succ (ENTRY_BLOCK_PTR);
166 else
167 ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
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))
173 edge e = INDEX_EDGE (el, edge_index);
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;
181 set_control_dependence_map_bit (current_block, edge_index);
186 /* Record all blocks' control dependences on all edges in the edge
187 list EL, ala Morgan, Section 3.6. */
189 static void
190 find_all_control_dependences (struct edge_list *el)
192 int i;
194 for (i = 0; i < NUM_EDGES (el); ++i)
195 find_control_dependence (el, i);
198 /* If STMT is not already marked necessary, mark it, and add it to the
199 worklist if ADD_TO_WORKLIST is true. */
201 static inline void
202 mark_stmt_necessary (gimple stmt, bool add_to_worklist)
204 gcc_assert (stmt);
206 if (gimple_plf (stmt, STMT_NECESSARY))
207 return;
209 if (dump_file && (dump_flags & TDF_DETAILS))
211 fprintf (dump_file, "Marking useful stmt: ");
212 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
213 fprintf (dump_file, "\n");
216 gimple_set_plf (stmt, STMT_NECESSARY, true);
217 if (add_to_worklist)
218 VEC_safe_push (gimple, heap, worklist, stmt);
219 if (bb_contains_live_stmts && !is_gimple_debug (stmt))
220 SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
224 /* Mark the statement defining operand OP as necessary. */
226 static inline void
227 mark_operand_necessary (tree op)
229 gimple stmt;
230 int ver;
232 gcc_assert (op);
234 ver = SSA_NAME_VERSION (op);
235 if (TEST_BIT (processed, ver))
237 stmt = SSA_NAME_DEF_STMT (op);
238 gcc_assert (gimple_nop_p (stmt)
239 || gimple_plf (stmt, STMT_NECESSARY));
240 return;
242 SET_BIT (processed, ver);
244 stmt = SSA_NAME_DEF_STMT (op);
245 gcc_assert (stmt);
247 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
248 return;
250 if (dump_file && (dump_flags & TDF_DETAILS))
252 fprintf (dump_file, "marking necessary through ");
253 print_generic_expr (dump_file, op, 0);
254 fprintf (dump_file, " stmt ");
255 print_gimple_stmt (dump_file, stmt, 0, 0);
258 gimple_set_plf (stmt, STMT_NECESSARY, true);
259 if (bb_contains_live_stmts)
260 SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
261 VEC_safe_push (gimple, heap, worklist, stmt);
265 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
266 it can make other statements necessary.
268 If AGGRESSIVE is false, control statements are conservatively marked as
269 necessary. */
271 static void
272 mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
274 tree lhs = NULL_TREE;
276 /* With non-call exceptions, we have to assume that all statements could
277 throw. If a statement may throw, it is inherently necessary. */
278 if (cfun->can_throw_non_call_exceptions && stmt_could_throw_p (stmt))
280 mark_stmt_necessary (stmt, true);
281 return;
284 /* Statements that are implicitly live. Most function calls, asm
285 and return statements are required. Labels and GIMPLE_BIND nodes
286 are kept because they are control flow, and we have no way of
287 knowing whether they can be removed. DCE can eliminate all the
288 other statements in a block, and CFG can then remove the block
289 and labels. */
290 switch (gimple_code (stmt))
292 case GIMPLE_PREDICT:
293 case GIMPLE_LABEL:
294 mark_stmt_necessary (stmt, false);
295 return;
297 case GIMPLE_ASM:
298 case GIMPLE_RESX:
299 case GIMPLE_RETURN:
300 mark_stmt_necessary (stmt, true);
301 return;
303 case GIMPLE_CALL:
304 /* Most, but not all function calls are required. Function calls that
305 produce no result and have no side effects (i.e. const pure
306 functions) are unnecessary. */
307 if (gimple_has_side_effects (stmt))
309 mark_stmt_necessary (stmt, true);
310 return;
312 if (!gimple_call_lhs (stmt))
313 return;
314 lhs = gimple_call_lhs (stmt);
315 /* Fall through */
317 case GIMPLE_ASSIGN:
318 if (!lhs)
319 lhs = gimple_assign_lhs (stmt);
320 break;
322 case GIMPLE_DEBUG:
323 /* Debug temps without a value are not useful. ??? If we could
324 easily locate the debug temp bind stmt for a use thereof,
325 would could refrain from marking all debug temps here, and
326 mark them only if they're used. */
327 if (gimple_debug_bind_has_value_p (stmt)
328 || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
329 mark_stmt_necessary (stmt, false);
330 return;
332 case GIMPLE_GOTO:
333 gcc_assert (!simple_goto_p (stmt));
334 mark_stmt_necessary (stmt, true);
335 return;
337 case GIMPLE_COND:
338 gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
339 /* Fall through. */
341 case GIMPLE_SWITCH:
342 if (! aggressive)
343 mark_stmt_necessary (stmt, true);
344 break;
346 default:
347 break;
350 /* If the statement has volatile operands, it needs to be preserved.
351 Same for statements that can alter control flow in unpredictable
352 ways. */
353 if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
355 mark_stmt_necessary (stmt, true);
356 return;
359 if (is_hidden_global_store (stmt))
361 mark_stmt_necessary (stmt, true);
362 return;
365 return;
369 /* Mark the last statement of BB as necessary. */
371 static void
372 mark_last_stmt_necessary (basic_block bb)
374 gimple stmt = last_stmt (bb);
376 SET_BIT (last_stmt_necessary, bb->index);
377 SET_BIT (bb_contains_live_stmts, bb->index);
379 /* We actually mark the statement only if it is a control statement. */
380 if (stmt && is_ctrl_stmt (stmt))
381 mark_stmt_necessary (stmt, true);
385 /* Mark control dependent edges of BB as necessary. We have to do this only
386 once for each basic block so we set the appropriate bit after we're done.
388 When IGNORE_SELF is true, ignore BB in the list of control dependences. */
390 static void
391 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el,
392 bool ignore_self)
394 bitmap_iterator bi;
395 unsigned edge_number;
396 bool skipped = false;
398 gcc_assert (bb != EXIT_BLOCK_PTR);
400 if (bb == ENTRY_BLOCK_PTR)
401 return;
403 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
405 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
407 if (ignore_self && cd_bb == bb)
409 skipped = true;
410 continue;
413 if (!TEST_BIT (last_stmt_necessary, cd_bb->index))
414 mark_last_stmt_necessary (cd_bb);
417 if (!skipped)
418 SET_BIT (visited_control_parents, bb->index);
422 /* Find obviously necessary statements. These are things like most function
423 calls, and stores to file level variables.
425 If EL is NULL, control statements are conservatively marked as
426 necessary. Otherwise it contains the list of edges used by control
427 dependence analysis. */
429 static void
430 find_obviously_necessary_stmts (struct edge_list *el)
432 basic_block bb;
433 gimple_stmt_iterator gsi;
434 edge e;
435 gimple phi, stmt;
437 FOR_EACH_BB (bb)
439 /* PHI nodes are never inherently necessary. */
440 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
442 phi = gsi_stmt (gsi);
443 gimple_set_plf (phi, STMT_NECESSARY, false);
446 /* Check all statements in the block. */
447 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
449 stmt = gsi_stmt (gsi);
450 gimple_set_plf (stmt, STMT_NECESSARY, false);
451 mark_stmt_if_obviously_necessary (stmt, el != NULL);
455 /* Pure and const functions are finite and thus have no infinite loops in
456 them. */
457 if ((TREE_READONLY (current_function_decl)
458 || DECL_PURE_P (current_function_decl))
459 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
460 return;
462 /* Prevent the empty possibly infinite loops from being removed. */
463 if (el)
465 loop_iterator li;
466 struct loop *loop;
467 scev_initialize ();
468 if (mark_irreducible_loops ())
469 FOR_EACH_BB (bb)
471 edge_iterator ei;
472 FOR_EACH_EDGE (e, ei, bb->succs)
473 if ((e->flags & EDGE_DFS_BACK)
474 && (e->flags & EDGE_IRREDUCIBLE_LOOP))
476 if (dump_file)
477 fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
478 e->src->index, e->dest->index);
479 mark_control_dependent_edges_necessary (e->dest, el, false);
483 FOR_EACH_LOOP (li, loop, 0)
484 if (!finite_loop_p (loop))
486 if (dump_file)
487 fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
488 mark_control_dependent_edges_necessary (loop->latch, el, false);
490 scev_finalize ();
495 /* Return true if REF is based on an aliased base, otherwise false. */
497 static bool
498 ref_may_be_aliased (tree ref)
500 while (handled_component_p (ref))
501 ref = TREE_OPERAND (ref, 0);
502 if (TREE_CODE (ref) == MEM_REF
503 && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
504 ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
505 return !(DECL_P (ref)
506 && !may_be_aliased (ref));
509 static bitmap visited = NULL;
510 static unsigned int longest_chain = 0;
511 static unsigned int total_chain = 0;
512 static unsigned int nr_walks = 0;
513 static bool chain_ovfl = false;
515 /* Worker for the walker that marks reaching definitions of REF,
516 which is based on a non-aliased decl, necessary. It returns
517 true whenever the defining statement of the current VDEF is
518 a kill for REF, as no dominating may-defs are necessary for REF
519 anymore. DATA points to the basic-block that contains the
520 stmt that refers to REF. */
522 static bool
523 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
525 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
527 /* All stmts we visit are necessary. */
528 mark_operand_necessary (vdef);
530 /* If the stmt lhs kills ref, then we can stop walking. */
531 if (gimple_has_lhs (def_stmt)
532 && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
534 tree base, lhs = gimple_get_lhs (def_stmt);
535 HOST_WIDE_INT size, offset, max_size;
536 ao_ref_base (ref);
537 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
538 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
539 so base == refd->base does not always hold. */
540 if (base == ref->base)
542 /* For a must-alias check we need to be able to constrain
543 the accesses properly. */
544 if (size != -1 && size == max_size
545 && ref->max_size != -1)
547 if (offset <= ref->offset
548 && offset + size >= ref->offset + ref->max_size)
549 return true;
551 /* Or they need to be exactly the same. */
552 else if (ref->ref
553 /* Make sure there is no induction variable involved
554 in the references (gcc.c-torture/execute/pr42142.c).
555 The simplest way is to check if the kill dominates
556 the use. */
557 && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
558 gimple_bb (def_stmt))
559 && operand_equal_p (ref->ref, lhs, 0))
560 return true;
564 /* Otherwise keep walking. */
565 return false;
568 static void
569 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
571 unsigned int chain;
572 ao_ref refd;
573 gcc_assert (!chain_ovfl);
574 ao_ref_init (&refd, ref);
575 chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
576 mark_aliased_reaching_defs_necessary_1,
577 gimple_bb (stmt), NULL);
578 if (chain > longest_chain)
579 longest_chain = chain;
580 total_chain += chain;
581 nr_walks++;
584 /* Worker for the walker that marks reaching definitions of REF, which
585 is not based on a non-aliased decl. For simplicity we need to end
586 up marking all may-defs necessary that are not based on a non-aliased
587 decl. The only job of this walker is to skip may-defs based on
588 a non-aliased decl. */
590 static bool
591 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
592 tree vdef, void *data ATTRIBUTE_UNUSED)
594 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
596 /* We have to skip already visited (and thus necessary) statements
597 to make the chaining work after we dropped back to simple mode. */
598 if (chain_ovfl
599 && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
601 gcc_assert (gimple_nop_p (def_stmt)
602 || gimple_plf (def_stmt, STMT_NECESSARY));
603 return false;
606 /* We want to skip stores to non-aliased variables. */
607 if (!chain_ovfl
608 && gimple_assign_single_p (def_stmt))
610 tree lhs = gimple_assign_lhs (def_stmt);
611 if (!ref_may_be_aliased (lhs))
612 return false;
615 mark_operand_necessary (vdef);
617 return false;
620 static void
621 mark_all_reaching_defs_necessary (gimple stmt)
623 walk_aliased_vdefs (NULL, gimple_vuse (stmt),
624 mark_all_reaching_defs_necessary_1, NULL, &visited);
627 /* Return true for PHI nodes with one or identical arguments
628 can be removed. */
629 static bool
630 degenerate_phi_p (gimple phi)
632 unsigned int i;
633 tree op = gimple_phi_arg_def (phi, 0);
634 for (i = 1; i < gimple_phi_num_args (phi); i++)
635 if (gimple_phi_arg_def (phi, i) != op)
636 return false;
637 return true;
640 /* Propagate necessity using the operands of necessary statements.
641 Process the uses on each statement in the worklist, and add all
642 feeding statements which contribute to the calculation of this
643 value to the worklist.
645 In conservative mode, EL is NULL. */
647 static void
648 propagate_necessity (struct edge_list *el)
650 gimple stmt;
651 bool aggressive = (el ? true : false);
653 if (dump_file && (dump_flags & TDF_DETAILS))
654 fprintf (dump_file, "\nProcessing worklist:\n");
656 while (VEC_length (gimple, worklist) > 0)
658 /* Take STMT from worklist. */
659 stmt = VEC_pop (gimple, worklist);
661 if (dump_file && (dump_flags & TDF_DETAILS))
663 fprintf (dump_file, "processing: ");
664 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
665 fprintf (dump_file, "\n");
668 if (aggressive)
670 /* Mark the last statement of the basic blocks on which the block
671 containing STMT is control dependent, but only if we haven't
672 already done so. */
673 basic_block bb = gimple_bb (stmt);
674 if (bb != ENTRY_BLOCK_PTR
675 && !TEST_BIT (visited_control_parents, bb->index))
676 mark_control_dependent_edges_necessary (bb, el, false);
679 if (gimple_code (stmt) == GIMPLE_PHI
680 /* We do not process virtual PHI nodes nor do we track their
681 necessity. */
682 && is_gimple_reg (gimple_phi_result (stmt)))
684 /* PHI nodes are somewhat special in that each PHI alternative has
685 data and control dependencies. All the statements feeding the
686 PHI node's arguments are always necessary. In aggressive mode,
687 we also consider the control dependent edges leading to the
688 predecessor block associated with each PHI alternative as
689 necessary. */
690 size_t k;
692 for (k = 0; k < gimple_phi_num_args (stmt); k++)
694 tree arg = PHI_ARG_DEF (stmt, k);
695 if (TREE_CODE (arg) == SSA_NAME)
696 mark_operand_necessary (arg);
699 /* For PHI operands it matters from where the control flow arrives
700 to the BB. Consider the following example:
702 a=exp1;
703 b=exp2;
704 if (test)
706 else
708 c=PHI(a,b)
710 We need to mark control dependence of the empty basic blocks, since they
711 contains computation of PHI operands.
713 Doing so is too restrictive in the case the predecestor block is in
714 the loop. Consider:
716 if (b)
718 int i;
719 for (i = 0; i<1000; ++i)
721 j = 0;
723 return j;
725 There is PHI for J in the BB containing return statement.
726 In this case the control dependence of predecestor block (that is
727 within the empty loop) also contains the block determining number
728 of iterations of the block that would prevent removing of empty
729 loop in this case.
731 This scenario can be avoided by splitting critical edges.
732 To save the critical edge splitting pass we identify how the control
733 dependence would look like if the edge was split.
735 Consider the modified CFG created from current CFG by splitting
736 edge B->C. In the postdominance tree of modified CFG, C' is
737 always child of C. There are two cases how chlids of C' can look
738 like:
740 1) C' is leaf
742 In this case the only basic block C' is control dependent on is B.
744 2) C' has single child that is B
746 In this case control dependence of C' is same as control
747 dependence of B in original CFG except for block B itself.
748 (since C' postdominate B in modified CFG)
750 Now how to decide what case happens? There are two basic options:
752 a) C postdominate B. Then C immediately postdominate B and
753 case 2 happens iff there is no other way from B to C except
754 the edge B->C.
756 There is other way from B to C iff there is succesor of B that
757 is not postdominated by B. Testing this condition is somewhat
758 expensive, because we need to iterate all succesors of B.
759 We are safe to assume that this does not happen: we will mark B
760 as needed when processing the other path from B to C that is
761 conrol dependent on B and marking control dependencies of B
762 itself is harmless because they will be processed anyway after
763 processing control statement in B.
765 b) C does not postdominate B. Always case 1 happens since there is
766 path from C to exit that does not go through B and thus also C'. */
768 if (aggressive && !degenerate_phi_p (stmt))
770 for (k = 0; k < gimple_phi_num_args (stmt); k++)
772 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
774 if (gimple_bb (stmt)
775 != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
777 if (!TEST_BIT (last_stmt_necessary, arg_bb->index))
778 mark_last_stmt_necessary (arg_bb);
780 else if (arg_bb != ENTRY_BLOCK_PTR
781 && !TEST_BIT (visited_control_parents,
782 arg_bb->index))
783 mark_control_dependent_edges_necessary (arg_bb, el, true);
787 else
789 /* Propagate through the operands. Examine all the USE, VUSE and
790 VDEF operands in this statement. Mark all the statements
791 which feed this statement's uses as necessary. */
792 ssa_op_iter iter;
793 tree use;
795 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
796 mark_operand_necessary (use);
798 use = gimple_vuse (stmt);
799 if (!use)
800 continue;
802 /* If we dropped to simple mode make all immediately
803 reachable definitions necessary. */
804 if (chain_ovfl)
806 mark_all_reaching_defs_necessary (stmt);
807 continue;
810 /* For statements that may load from memory (have a VUSE) we
811 have to mark all reaching (may-)definitions as necessary.
812 We partition this task into two cases:
813 1) explicit loads based on decls that are not aliased
814 2) implicit loads (like calls) and explicit loads not
815 based on decls that are not aliased (like indirect
816 references or loads from globals)
817 For 1) we mark all reaching may-defs as necessary, stopping
818 at dominating kills. For 2) we want to mark all dominating
819 references necessary, but non-aliased ones which we handle
820 in 1). By keeping a global visited bitmap for references
821 we walk for 2) we avoid quadratic behavior for those. */
823 if (is_gimple_call (stmt))
825 tree callee = gimple_call_fndecl (stmt);
826 unsigned i;
828 /* Calls to functions that are merely acting as barriers
829 or that only store to memory do not make any previous
830 stores necessary. */
831 if (callee != NULL_TREE
832 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
833 && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
834 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
835 || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
836 continue;
838 /* Calls implicitly load from memory, their arguments
839 in addition may explicitly perform memory loads. */
840 mark_all_reaching_defs_necessary (stmt);
841 for (i = 0; i < gimple_call_num_args (stmt); ++i)
843 tree arg = gimple_call_arg (stmt, i);
844 if (TREE_CODE (arg) == SSA_NAME
845 || is_gimple_min_invariant (arg))
846 continue;
847 if (!ref_may_be_aliased (arg))
848 mark_aliased_reaching_defs_necessary (stmt, arg);
851 else if (gimple_assign_single_p (stmt))
853 tree rhs;
854 bool rhs_aliased = false;
855 /* If this is a load mark things necessary. */
856 rhs = gimple_assign_rhs1 (stmt);
857 if (TREE_CODE (rhs) != SSA_NAME
858 && !is_gimple_min_invariant (rhs))
860 if (!ref_may_be_aliased (rhs))
861 mark_aliased_reaching_defs_necessary (stmt, rhs);
862 else
863 rhs_aliased = true;
865 if (rhs_aliased)
866 mark_all_reaching_defs_necessary (stmt);
868 else if (gimple_code (stmt) == GIMPLE_RETURN)
870 tree rhs = gimple_return_retval (stmt);
871 /* A return statement may perform a load. */
872 if (TREE_CODE (rhs) != SSA_NAME
873 && !is_gimple_min_invariant (rhs))
875 if (!ref_may_be_aliased (rhs))
876 mark_aliased_reaching_defs_necessary (stmt, rhs);
877 else
878 mark_all_reaching_defs_necessary (stmt);
881 else if (gimple_code (stmt) == GIMPLE_ASM)
883 unsigned i;
884 mark_all_reaching_defs_necessary (stmt);
885 /* Inputs may perform loads. */
886 for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
888 tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
889 if (TREE_CODE (op) != SSA_NAME
890 && !is_gimple_min_invariant (op)
891 && !ref_may_be_aliased (op))
892 mark_aliased_reaching_defs_necessary (stmt, op);
895 else
896 gcc_unreachable ();
898 /* If we over-used our alias oracle budget drop to simple
899 mode. The cost metric allows quadratic behavior
900 (number of uses times number of may-defs queries) up to
901 a constant maximal number of queries and after that falls back to
902 super-linear complexity. */
903 if (/* Constant but quadratic for small functions. */
904 total_chain > 128 * 128
905 /* Linear in the number of may-defs. */
906 && total_chain > 32 * longest_chain
907 /* Linear in the number of uses. */
908 && total_chain > nr_walks * 32)
910 chain_ovfl = true;
911 if (visited)
912 bitmap_clear (visited);
918 /* Replace all uses of result of PHI by underlying variable and mark it
919 for renaming. */
921 void
922 mark_virtual_phi_result_for_renaming (gimple phi)
924 bool used = false;
925 imm_use_iterator iter;
926 use_operand_p use_p;
927 gimple stmt;
928 tree result_ssa, result_var;
930 if (dump_file && (dump_flags & TDF_DETAILS))
932 fprintf (dump_file, "Marking result for renaming : ");
933 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
934 fprintf (dump_file, "\n");
937 result_ssa = gimple_phi_result (phi);
938 result_var = SSA_NAME_VAR (result_ssa);
939 FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
941 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
942 SET_USE (use_p, result_var);
943 update_stmt (stmt);
944 used = true;
946 if (used)
947 mark_sym_for_renaming (result_var);
950 /* Remove dead PHI nodes from block BB. */
952 static bool
953 remove_dead_phis (basic_block bb)
955 bool something_changed = false;
956 gimple_seq phis;
957 gimple phi;
958 gimple_stmt_iterator gsi;
959 phis = phi_nodes (bb);
961 for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
963 stats.total_phis++;
964 phi = gsi_stmt (gsi);
966 /* We do not track necessity of virtual PHI nodes. Instead do
967 very simple dead PHI removal here. */
968 if (!is_gimple_reg (gimple_phi_result (phi)))
970 /* Virtual PHI nodes with one or identical arguments
971 can be removed. */
972 if (degenerate_phi_p (phi))
974 tree vdef = gimple_phi_result (phi);
975 tree vuse = gimple_phi_arg_def (phi, 0);
977 use_operand_p use_p;
978 imm_use_iterator iter;
979 gimple use_stmt;
980 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
981 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
982 SET_USE (use_p, vuse);
983 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
984 && TREE_CODE (vuse) == SSA_NAME)
985 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
987 else
988 gimple_set_plf (phi, STMT_NECESSARY, true);
991 if (!gimple_plf (phi, STMT_NECESSARY))
993 something_changed = true;
994 if (dump_file && (dump_flags & TDF_DETAILS))
996 fprintf (dump_file, "Deleting : ");
997 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
998 fprintf (dump_file, "\n");
1001 remove_phi_node (&gsi, true);
1002 stats.removed_phis++;
1003 continue;
1006 gsi_next (&gsi);
1008 return something_changed;
1011 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
1013 static edge
1014 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
1016 gimple_stmt_iterator gsi;
1017 edge e2 = NULL;
1018 edge_iterator ei;
1020 if (dump_file && (dump_flags & TDF_DETAILS))
1021 fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
1022 e->dest->index, post_dom_bb->index);
1024 e2 = redirect_edge_and_branch (e, post_dom_bb);
1025 cfg_altered = true;
1027 /* If edge was already around, no updating is neccesary. */
1028 if (e2 != e)
1029 return e2;
1031 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
1033 /* We are sure that for every live PHI we are seeing control dependent BB.
1034 This means that we can pick any edge to duplicate PHI args from. */
1035 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
1036 if (e2 != e)
1037 break;
1038 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
1040 gimple phi = gsi_stmt (gsi);
1041 tree op;
1042 source_location locus;
1044 /* PHIs for virtuals have no control dependency relation on them.
1045 We are lost here and must force renaming of the symbol. */
1046 if (!is_gimple_reg (gimple_phi_result (phi)))
1048 mark_virtual_phi_result_for_renaming (phi);
1049 remove_phi_node (&gsi, true);
1050 continue;
1053 /* Dead PHI do not imply control dependency. */
1054 if (!gimple_plf (phi, STMT_NECESSARY))
1056 gsi_next (&gsi);
1057 continue;
1060 op = gimple_phi_arg_def (phi, e2->dest_idx);
1061 locus = gimple_phi_arg_location (phi, e2->dest_idx);
1062 add_phi_arg (phi, op, e, locus);
1063 /* The resulting PHI if not dead can only be degenerate. */
1064 gcc_assert (degenerate_phi_p (phi));
1065 gsi_next (&gsi);
1068 return e;
1071 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1072 containing I so that we don't have to look it up. */
1074 static void
1075 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
1077 gimple stmt = gsi_stmt (*i);
1079 if (dump_file && (dump_flags & TDF_DETAILS))
1081 fprintf (dump_file, "Deleting : ");
1082 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1083 fprintf (dump_file, "\n");
1086 stats.removed++;
1088 /* If we have determined that a conditional branch statement contributes
1089 nothing to the program, then we not only remove it, but we also change
1090 the flow graph so that the current block will simply fall-thru to its
1091 immediate post-dominator. The blocks we are circumventing will be
1092 removed by cleanup_tree_cfg if this change in the flow graph makes them
1093 unreachable. */
1094 if (is_ctrl_stmt (stmt))
1096 basic_block post_dom_bb;
1097 edge e, e2;
1098 edge_iterator ei;
1100 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
1102 e = find_edge (bb, post_dom_bb);
1104 /* If edge is already there, try to use it. This avoids need to update
1105 PHI nodes. Also watch for cases where post dominator does not exists
1106 or is exit block. These can happen for infinite loops as we create
1107 fake edges in the dominator tree. */
1108 if (e)
1110 else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
1111 e = EDGE_SUCC (bb, 0);
1112 else
1113 e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1114 gcc_assert (e);
1115 e->probability = REG_BR_PROB_BASE;
1116 e->count = bb->count;
1118 /* The edge is no longer associated with a conditional, so it does
1119 not have TRUE/FALSE flags. */
1120 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1122 /* The lone outgoing edge from BB will be a fallthru edge. */
1123 e->flags |= EDGE_FALLTHRU;
1125 /* Remove the remaining outgoing edges. */
1126 for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1127 if (e != e2)
1129 cfg_altered = true;
1130 remove_edge (e2);
1132 else
1133 ei_next (&ei);
1136 unlink_stmt_vdef (stmt);
1137 gsi_remove (i, true);
1138 release_defs (stmt);
1141 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1142 contributes nothing to the program, and can be deleted. */
1144 static bool
1145 eliminate_unnecessary_stmts (void)
1147 bool something_changed = false;
1148 basic_block bb;
1149 gimple_stmt_iterator gsi, psi;
1150 gimple stmt;
1151 tree call;
1152 VEC (basic_block, heap) *h;
1154 if (dump_file && (dump_flags & TDF_DETAILS))
1155 fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1157 clear_special_calls ();
1159 /* Walking basic blocks and statements in reverse order avoids
1160 releasing SSA names before any other DEFs that refer to them are
1161 released. This helps avoid loss of debug information, as we get
1162 a chance to propagate all RHSs of removed SSAs into debug uses,
1163 rather than only the latest ones. E.g., consider:
1165 x_3 = y_1 + z_2;
1166 a_5 = x_3 - b_4;
1167 # DEBUG a => a_5
1169 If we were to release x_3 before a_5, when we reached a_5 and
1170 tried to substitute it into the debug stmt, we'd see x_3 there,
1171 but x_3's DEF, type, etc would have already been disconnected.
1172 By going backwards, the debug stmt first changes to:
1174 # DEBUG a => x_3 - b_4
1176 and then to:
1178 # DEBUG a => y_1 + z_2 - b_4
1180 as desired. */
1181 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1182 h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
1184 while (VEC_length (basic_block, h))
1186 bb = VEC_pop (basic_block, h);
1188 /* Remove dead statements. */
1189 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
1191 stmt = gsi_stmt (gsi);
1193 psi = gsi;
1194 gsi_prev (&psi);
1196 stats.total++;
1198 /* If GSI is not necessary then remove it. */
1199 if (!gimple_plf (stmt, STMT_NECESSARY))
1201 if (!is_gimple_debug (stmt))
1202 something_changed = true;
1203 remove_dead_stmt (&gsi, bb);
1205 else if (is_gimple_call (stmt))
1207 call = gimple_call_fndecl (stmt);
1208 if (call)
1210 tree name;
1212 /* When LHS of var = call (); is dead, simplify it into
1213 call (); saving one operand. */
1214 name = gimple_call_lhs (stmt);
1215 if (name && TREE_CODE (name) == SSA_NAME
1216 && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1218 something_changed = true;
1219 if (dump_file && (dump_flags & TDF_DETAILS))
1221 fprintf (dump_file, "Deleting LHS of call: ");
1222 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1223 fprintf (dump_file, "\n");
1226 gimple_call_set_lhs (stmt, NULL_TREE);
1227 maybe_clean_or_replace_eh_stmt (stmt, stmt);
1228 update_stmt (stmt);
1229 release_ssa_name (name);
1231 notice_special_calls (stmt);
1237 VEC_free (basic_block, heap, h);
1239 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1240 rendered some PHI nodes unreachable while they are still in use.
1241 Mark them for renaming. */
1242 if (cfg_altered)
1244 basic_block prev_bb;
1246 find_unreachable_blocks ();
1248 /* Delete all unreachable basic blocks in reverse dominator order. */
1249 for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
1251 prev_bb = bb->prev_bb;
1253 if (!TEST_BIT (bb_contains_live_stmts, bb->index)
1254 || !(bb->flags & BB_REACHABLE))
1256 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1257 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1259 bool found = false;
1260 imm_use_iterator iter;
1262 FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
1264 if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1265 continue;
1266 if (gimple_code (stmt) == GIMPLE_PHI
1267 || gimple_plf (stmt, STMT_NECESSARY))
1269 found = true;
1270 BREAK_FROM_IMM_USE_STMT (iter);
1273 if (found)
1274 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
1277 if (!(bb->flags & BB_REACHABLE))
1279 /* Speed up the removal of blocks that don't
1280 dominate others. Walking backwards, this should
1281 be the common case. ??? Do we need to recompute
1282 dominators because of cfg_altered? */
1283 if (!MAY_HAVE_DEBUG_STMTS
1284 || !first_dom_son (CDI_DOMINATORS, bb))
1285 delete_basic_block (bb);
1286 else
1288 h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1290 while (VEC_length (basic_block, h))
1292 bb = VEC_pop (basic_block, h);
1293 prev_bb = bb->prev_bb;
1294 /* Rearrangements to the CFG may have failed
1295 to update the dominators tree, so that
1296 formerly-dominated blocks are now
1297 otherwise reachable. */
1298 if (!!(bb->flags & BB_REACHABLE))
1299 continue;
1300 delete_basic_block (bb);
1303 VEC_free (basic_block, heap, h);
1309 FOR_EACH_BB (bb)
1311 /* Remove dead PHI nodes. */
1312 something_changed |= remove_dead_phis (bb);
1315 return something_changed;
1319 /* Print out removed statement statistics. */
1321 static void
1322 print_stats (void)
1324 float percg;
1326 percg = ((float) stats.removed / (float) stats.total) * 100;
1327 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1328 stats.removed, stats.total, (int) percg);
1330 if (stats.total_phis == 0)
1331 percg = 0;
1332 else
1333 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1335 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1336 stats.removed_phis, stats.total_phis, (int) percg);
1339 /* Initialization for this pass. Set up the used data structures. */
1341 static void
1342 tree_dce_init (bool aggressive)
1344 memset ((void *) &stats, 0, sizeof (stats));
1346 if (aggressive)
1348 int i;
1350 control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1351 for (i = 0; i < last_basic_block; ++i)
1352 control_dependence_map[i] = BITMAP_ALLOC (NULL);
1354 last_stmt_necessary = sbitmap_alloc (last_basic_block);
1355 sbitmap_zero (last_stmt_necessary);
1356 bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1357 sbitmap_zero (bb_contains_live_stmts);
1360 processed = sbitmap_alloc (num_ssa_names + 1);
1361 sbitmap_zero (processed);
1363 worklist = VEC_alloc (gimple, heap, 64);
1364 cfg_altered = false;
1367 /* Cleanup after this pass. */
1369 static void
1370 tree_dce_done (bool aggressive)
1372 if (aggressive)
1374 int i;
1376 for (i = 0; i < last_basic_block; ++i)
1377 BITMAP_FREE (control_dependence_map[i]);
1378 free (control_dependence_map);
1380 sbitmap_free (visited_control_parents);
1381 sbitmap_free (last_stmt_necessary);
1382 sbitmap_free (bb_contains_live_stmts);
1383 bb_contains_live_stmts = NULL;
1386 sbitmap_free (processed);
1388 VEC_free (gimple, heap, worklist);
1391 /* Main routine to eliminate dead code.
1393 AGGRESSIVE controls the aggressiveness of the algorithm.
1394 In conservative mode, we ignore control dependence and simply declare
1395 all but the most trivially dead branches necessary. This mode is fast.
1396 In aggressive mode, control dependences are taken into account, which
1397 results in more dead code elimination, but at the cost of some time.
1399 FIXME: Aggressive mode before PRE doesn't work currently because
1400 the dominance info is not invalidated after DCE1. This is
1401 not an issue right now because we only run aggressive DCE
1402 as the last tree SSA pass, but keep this in mind when you
1403 start experimenting with pass ordering. */
1405 static unsigned int
1406 perform_tree_ssa_dce (bool aggressive)
1408 struct edge_list *el = NULL;
1409 bool something_changed = 0;
1411 /* Preheaders are needed for SCEV to work.
1412 Simple lateches and recorded exits improve chances that loop will
1413 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1414 if (aggressive)
1415 loop_optimizer_init (LOOPS_NORMAL
1416 | LOOPS_HAVE_RECORDED_EXITS);
1418 tree_dce_init (aggressive);
1420 if (aggressive)
1422 /* Compute control dependence. */
1423 timevar_push (TV_CONTROL_DEPENDENCES);
1424 calculate_dominance_info (CDI_POST_DOMINATORS);
1425 el = create_edge_list ();
1426 find_all_control_dependences (el);
1427 timevar_pop (TV_CONTROL_DEPENDENCES);
1429 visited_control_parents = sbitmap_alloc (last_basic_block);
1430 sbitmap_zero (visited_control_parents);
1432 mark_dfs_back_edges ();
1435 find_obviously_necessary_stmts (el);
1437 if (aggressive)
1438 loop_optimizer_finalize ();
1440 longest_chain = 0;
1441 total_chain = 0;
1442 nr_walks = 0;
1443 chain_ovfl = false;
1444 visited = BITMAP_ALLOC (NULL);
1445 propagate_necessity (el);
1446 BITMAP_FREE (visited);
1448 something_changed |= eliminate_unnecessary_stmts ();
1449 something_changed |= cfg_altered;
1451 /* We do not update postdominators, so free them unconditionally. */
1452 free_dominance_info (CDI_POST_DOMINATORS);
1454 /* If we removed paths in the CFG, then we need to update
1455 dominators as well. I haven't investigated the possibility
1456 of incrementally updating dominators. */
1457 if (cfg_altered)
1458 free_dominance_info (CDI_DOMINATORS);
1460 statistics_counter_event (cfun, "Statements deleted", stats.removed);
1461 statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1463 /* Debugging dumps. */
1464 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1465 print_stats ();
1467 tree_dce_done (aggressive);
1469 free_edge_list (el);
1471 if (something_changed)
1472 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1473 | TODO_remove_unused_locals);
1474 else
1475 return 0;
1478 /* Pass entry points. */
1479 static unsigned int
1480 tree_ssa_dce (void)
1482 return perform_tree_ssa_dce (/*aggressive=*/false);
1485 static unsigned int
1486 tree_ssa_dce_loop (void)
1488 unsigned int todo;
1489 todo = perform_tree_ssa_dce (/*aggressive=*/false);
1490 if (todo)
1492 free_numbers_of_iterations_estimates ();
1493 scev_reset ();
1495 return todo;
1498 static unsigned int
1499 tree_ssa_cd_dce (void)
1501 return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1504 static bool
1505 gate_dce (void)
1507 return flag_tree_dce != 0;
1510 struct gimple_opt_pass pass_dce =
1513 GIMPLE_PASS,
1514 "dce", /* name */
1515 gate_dce, /* gate */
1516 tree_ssa_dce, /* execute */
1517 NULL, /* sub */
1518 NULL, /* next */
1519 0, /* static_pass_number */
1520 TV_TREE_DCE, /* tv_id */
1521 PROP_cfg | PROP_ssa, /* properties_required */
1522 0, /* properties_provided */
1523 0, /* properties_destroyed */
1524 0, /* todo_flags_start */
1525 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1529 struct gimple_opt_pass pass_dce_loop =
1532 GIMPLE_PASS,
1533 "dceloop", /* name */
1534 gate_dce, /* gate */
1535 tree_ssa_dce_loop, /* execute */
1536 NULL, /* sub */
1537 NULL, /* next */
1538 0, /* static_pass_number */
1539 TV_TREE_DCE, /* tv_id */
1540 PROP_cfg | PROP_ssa, /* properties_required */
1541 0, /* properties_provided */
1542 0, /* properties_destroyed */
1543 0, /* todo_flags_start */
1544 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1548 struct gimple_opt_pass pass_cd_dce =
1551 GIMPLE_PASS,
1552 "cddce", /* name */
1553 gate_dce, /* gate */
1554 tree_ssa_cd_dce, /* execute */
1555 NULL, /* sub */
1556 NULL, /* next */
1557 0, /* static_pass_number */
1558 TV_TREE_CD_DCE, /* tv_id */
1559 PROP_cfg | PROP_ssa, /* properties_required */
1560 0, /* properties_provided */
1561 0, /* properties_destroyed */
1562 0, /* todo_flags_start */
1563 TODO_dump_func | TODO_verify_ssa
1564 | TODO_verify_flow /* todo_flags_finish */