1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
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
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
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.
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
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. */
48 #include "coretypes.h"
52 /* These RTL headers are needed for basic-block.h. */
55 #include "hard-reg-set.h"
57 #include "basic-block.h"
60 #include "diagnostic.h"
61 #include "tree-flow.h"
63 #include "tree-dump.h"
64 #include "tree-pass.h"
68 #include "tree-scalar-evolution.h"
70 static struct stmt_stats
78 #define STMT_NECESSARY GF_PLF_1
80 static VEC(gimple,heap) *worklist;
82 /* Vector indicating an SSA name has already been processed and marked
84 static sbitmap processed;
86 /* Vector indicating that last_stmt if a basic block has already been
87 marked as necessary. */
88 static sbitmap last_stmt_necessary;
90 /* Before we can determine whether a control branch is dead, we need to
91 compute which blocks are control dependent on which edges.
93 We expect each block to be control dependent on very few edges so we
94 use a bitmap for each block recording its edges. An array holds the
95 bitmap. The Ith bit in the bitmap is set if that block is dependent
97 static bitmap *control_dependence_map;
99 /* Vector indicating that a basic block has already had all the edges
100 processed that it is control dependent on. */
101 static sbitmap visited_control_parents;
103 /* TRUE if this pass alters the CFG (by removing control statements).
106 If this pass alters the CFG, then it will arrange for the dominators
108 static bool cfg_altered;
110 /* Execute code that follows the macro for each edge (given number
111 EDGE_NUMBER within the CODE) for which the block with index N is
112 control dependent. */
113 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
114 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
118 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
120 set_control_dependence_map_bit (basic_block bb, int edge_index)
122 if (bb == ENTRY_BLOCK_PTR)
124 gcc_assert (bb != EXIT_BLOCK_PTR);
125 bitmap_set_bit (control_dependence_map[bb->index], edge_index);
128 /* Clear all control dependences for block BB. */
130 clear_control_dependence_bitmap (basic_block bb)
132 bitmap_clear (control_dependence_map[bb->index]);
136 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
137 This function is necessary because some blocks have negative numbers. */
139 static inline basic_block
140 find_pdom (basic_block block)
142 gcc_assert (block != ENTRY_BLOCK_PTR);
144 if (block == EXIT_BLOCK_PTR)
145 return EXIT_BLOCK_PTR;
148 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
150 return EXIT_BLOCK_PTR;
156 /* Determine all blocks' control dependences on the given edge with edge_list
157 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
160 find_control_dependence (struct edge_list *el, int edge_index)
162 basic_block current_block;
163 basic_block ending_block;
165 gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
167 if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
168 ending_block = single_succ (ENTRY_BLOCK_PTR);
170 ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
172 for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
173 current_block != ending_block && current_block != EXIT_BLOCK_PTR;
174 current_block = find_pdom (current_block))
176 edge e = INDEX_EDGE (el, edge_index);
178 /* For abnormal edges, we don't make current_block control
179 dependent because instructions that throw are always necessary
181 if (e->flags & EDGE_ABNORMAL)
184 set_control_dependence_map_bit (current_block, edge_index);
189 /* Record all blocks' control dependences on all edges in the edge
190 list EL, ala Morgan, Section 3.6. */
193 find_all_control_dependences (struct edge_list *el)
197 for (i = 0; i < NUM_EDGES (el); ++i)
198 find_control_dependence (el, i);
201 /* If STMT is not already marked necessary, mark it, and add it to the
202 worklist if ADD_TO_WORKLIST is true. */
204 mark_stmt_necessary (gimple stmt, bool add_to_worklist)
208 if (gimple_plf (stmt, STMT_NECESSARY))
211 if (dump_file && (dump_flags & TDF_DETAILS))
213 fprintf (dump_file, "Marking useful stmt: ");
214 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
215 fprintf (dump_file, "\n");
218 gimple_set_plf (stmt, STMT_NECESSARY, true);
220 VEC_safe_push (gimple, heap, worklist, stmt);
224 /* Mark the statement defining operand OP as necessary. */
227 mark_operand_necessary (tree 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));
242 SET_BIT (processed, ver);
244 stmt = SSA_NAME_DEF_STMT (op);
247 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
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 VEC_safe_push (gimple, heap, worklist, stmt);
263 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
264 it can make other statements necessary.
266 If AGGRESSIVE is false, control statements are conservatively marked as
270 mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
272 tree lhs = NULL_TREE;
273 /* With non-call exceptions, we have to assume that all statements could
274 throw. If a statement may throw, it is inherently necessary. */
275 if (flag_non_call_exceptions
276 && stmt_could_throw_p (stmt))
278 mark_stmt_necessary (stmt, true);
282 /* Statements that are implicitly live. Most function calls, asm
283 and return statements are required. Labels and GIMPLE_BIND nodes
284 are kept because they are control flow, and we have no way of
285 knowing whether they can be removed. DCE can eliminate all the
286 other statements in a block, and CFG can then remove the block
288 switch (gimple_code (stmt))
292 mark_stmt_necessary (stmt, false);
298 mark_stmt_necessary (stmt, true);
302 /* Most, but not all function calls are required. Function calls that
303 produce no result and have no side effects (i.e. const pure
304 functions) are unnecessary. */
305 if (gimple_has_side_effects (stmt))
307 mark_stmt_necessary (stmt, true);
310 if (!gimple_call_lhs (stmt))
312 lhs = gimple_call_lhs (stmt);
317 lhs = gimple_assign_lhs (stmt);
318 /* These values are mildly magic bits of the EH runtime. We can't
319 see the entire lifetime of these values until landing pads are
321 if (TREE_CODE (lhs) == EXC_PTR_EXPR
322 || TREE_CODE (lhs) == FILTER_EXPR)
324 mark_stmt_necessary (stmt, true);
330 gcc_assert (!simple_goto_p (stmt));
331 mark_stmt_necessary (stmt, true);
335 gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
340 mark_stmt_necessary (stmt, true);
347 /* If the statement has volatile operands, it needs to be preserved.
348 Same for statements that can alter control flow in unpredictable
350 if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
352 mark_stmt_necessary (stmt, true);
356 if (is_hidden_global_store (stmt))
358 mark_stmt_necessary (stmt, true);
366 /* Make corresponding control dependent edges necessary. We only
367 have to do this once for each basic block, so we clear the bitmap
370 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
373 unsigned edge_number;
375 gcc_assert (bb != EXIT_BLOCK_PTR);
377 if (bb == ENTRY_BLOCK_PTR)
380 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
383 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
385 if (TEST_BIT (last_stmt_necessary, cd_bb->index))
387 SET_BIT (last_stmt_necessary, cd_bb->index);
389 stmt = last_stmt (cd_bb);
390 if (stmt && is_ctrl_stmt (stmt))
391 mark_stmt_necessary (stmt, true);
396 /* Find obviously necessary statements. These are things like most function
397 calls, and stores to file level variables.
399 If EL is NULL, control statements are conservatively marked as
400 necessary. Otherwise it contains the list of edges used by control
401 dependence analysis. */
404 find_obviously_necessary_stmts (struct edge_list *el)
407 gimple_stmt_iterator gsi;
413 /* PHI nodes are never inherently necessary. */
414 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
416 phi = gsi_stmt (gsi);
417 gimple_set_plf (phi, STMT_NECESSARY, false);
420 /* Check all statements in the block. */
421 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
423 stmt = gsi_stmt (gsi);
424 gimple_set_plf (stmt, STMT_NECESSARY, false);
425 mark_stmt_if_obviously_necessary (stmt, el != NULL);
431 /* Prevent the loops from being removed. We must keep the infinite loops,
432 and we currently do not have a means to recognize the finite ones. */
436 FOR_EACH_EDGE (e, ei, bb->succs)
437 if (e->flags & EDGE_DFS_BACK)
438 mark_control_dependent_edges_necessary (e->dest, el);
444 /* Return true if REF is based on an aliased base, otherwise false. */
447 ref_may_be_aliased (tree ref)
449 while (handled_component_p (ref))
450 ref = TREE_OPERAND (ref, 0);
451 return !(DECL_P (ref)
452 && !may_be_aliased (ref));
455 static bitmap visited = NULL;
456 static unsigned int longest_chain = 0;
457 static unsigned int total_chain = 0;
458 static bool chain_ovfl = false;
460 /* Worker for the walker that marks reaching definitions of REF,
461 which is based on a non-aliased decl, necessary. It returns
462 true whenever the defining statement of the current VDEF is
463 a kill for REF, as no dominating may-defs are necessary for REF
464 anymore. DATA points to cached get_ref_base_and_extent data for REF. */
467 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
468 void *data ATTRIBUTE_UNUSED)
470 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
472 /* All stmts we visit are necessary. */
473 mark_operand_necessary (vdef);
475 /* If the stmt lhs kills ref, then we can stop walking. */
476 if (gimple_has_lhs (def_stmt)
477 && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
479 tree base, lhs = gimple_get_lhs (def_stmt);
480 HOST_WIDE_INT size, offset, max_size;
482 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
483 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
484 so base == refd->base does not always hold. */
485 if (base == ref->base)
487 /* For a must-alias check we need to be able to constrain
488 the accesses properly. */
489 if (size != -1 && size == max_size
490 && ref->max_size != -1)
492 if (offset <= ref->offset
493 && offset + size >= ref->offset + ref->max_size)
496 /* Or they need to be exactly the same. */
498 && operand_equal_p (ref->ref, lhs, 0))
503 /* Otherwise keep walking. */
508 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
512 gcc_assert (!chain_ovfl);
513 ao_ref_init (&refd, ref);
514 chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
515 mark_aliased_reaching_defs_necessary_1,
517 if (chain > longest_chain)
518 longest_chain = chain;
519 total_chain += chain;
522 /* Worker for the walker that marks reaching definitions of REF, which
523 is not based on a non-aliased decl. For simplicity we need to end
524 up marking all may-defs necessary that are not based on a non-aliased
525 decl. The only job of this walker is to skip may-defs based on
526 a non-aliased decl. */
529 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
530 tree vdef, void *data ATTRIBUTE_UNUSED)
532 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
534 /* We have to skip already visited (and thus necessary) statements
535 to make the chaining work after we dropped back to simple mode. */
537 && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
539 gcc_assert (gimple_nop_p (def_stmt)
540 || gimple_plf (def_stmt, STMT_NECESSARY));
544 /* We want to skip stores to non-aliased variables. */
546 && gimple_assign_single_p (def_stmt))
548 tree lhs = gimple_assign_lhs (def_stmt);
549 if (!ref_may_be_aliased (lhs))
553 mark_operand_necessary (vdef);
559 mark_all_reaching_defs_necessary (gimple stmt)
561 walk_aliased_vdefs (NULL, gimple_vuse (stmt),
562 mark_all_reaching_defs_necessary_1, NULL, &visited);
565 /* Propagate necessity using the operands of necessary statements.
566 Process the uses on each statement in the worklist, and add all
567 feeding statements which contribute to the calculation of this
568 value to the worklist.
570 In conservative mode, EL is NULL. */
573 propagate_necessity (struct edge_list *el)
576 bool aggressive = (el ? true : false);
578 if (dump_file && (dump_flags & TDF_DETAILS))
579 fprintf (dump_file, "\nProcessing worklist:\n");
581 while (VEC_length (gimple, worklist) > 0)
583 /* Take STMT from worklist. */
584 stmt = VEC_pop (gimple, worklist);
586 if (dump_file && (dump_flags & TDF_DETAILS))
588 fprintf (dump_file, "processing: ");
589 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
590 fprintf (dump_file, "\n");
595 /* Mark the last statements of the basic blocks that the block
596 containing STMT is control dependent on, but only if we haven't
598 basic_block bb = gimple_bb (stmt);
599 if (bb != ENTRY_BLOCK_PTR
600 && ! TEST_BIT (visited_control_parents, bb->index))
602 SET_BIT (visited_control_parents, bb->index);
603 mark_control_dependent_edges_necessary (bb, el);
607 if (gimple_code (stmt) == GIMPLE_PHI
608 /* We do not process virtual PHI nodes nor do we track their
610 && is_gimple_reg (gimple_phi_result (stmt)))
612 /* PHI nodes are somewhat special in that each PHI alternative has
613 data and control dependencies. All the statements feeding the
614 PHI node's arguments are always necessary. In aggressive mode,
615 we also consider the control dependent edges leading to the
616 predecessor block associated with each PHI alternative as
620 for (k = 0; k < gimple_phi_num_args (stmt); k++)
622 tree arg = PHI_ARG_DEF (stmt, k);
623 if (TREE_CODE (arg) == SSA_NAME)
624 mark_operand_necessary (arg);
629 for (k = 0; k < gimple_phi_num_args (stmt); k++)
631 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
632 if (arg_bb != ENTRY_BLOCK_PTR
633 && ! TEST_BIT (visited_control_parents, arg_bb->index))
635 SET_BIT (visited_control_parents, arg_bb->index);
636 mark_control_dependent_edges_necessary (arg_bb, el);
643 /* Propagate through the operands. Examine all the USE, VUSE and
644 VDEF operands in this statement. Mark all the statements
645 which feed this statement's uses as necessary. */
649 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
650 mark_operand_necessary (use);
652 use = gimple_vuse (stmt);
656 /* If we dropped to simple mode make all immediately
657 reachable definitions necessary. */
660 mark_all_reaching_defs_necessary (stmt);
664 /* For statements that may load from memory (have a VUSE) we
665 have to mark all reaching (may-)definitions as necessary.
666 We partition this task into two cases:
667 1) explicit loads based on decls that are not aliased
668 2) implicit loads (like calls) and explicit loads not
669 based on decls that are not aliased (like indirect
670 references or loads from globals)
671 For 1) we mark all reaching may-defs as necessary, stopping
672 at dominating kills. For 2) we want to mark all dominating
673 references necessary, but non-aliased ones which we handle
674 in 1). By keeping a global visited bitmap for references
675 we walk for 2) we avoid quadratic behavior for those. */
677 if (is_gimple_call (stmt))
679 tree callee = gimple_call_fndecl (stmt);
682 /* Calls to functions that are merely acting as barriers
683 or that only store to memory do not make any previous
685 if (callee != NULL_TREE
686 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
687 && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
688 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
689 || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
692 /* Calls implicitly load from memory, their arguments
693 in addition may explicitly perform memory loads. */
694 mark_all_reaching_defs_necessary (stmt);
695 for (i = 0; i < gimple_call_num_args (stmt); ++i)
697 tree arg = gimple_call_arg (stmt, i);
698 if (TREE_CODE (arg) == SSA_NAME
699 || is_gimple_min_invariant (arg))
701 if (!ref_may_be_aliased (arg))
702 mark_aliased_reaching_defs_necessary (stmt, arg);
705 else if (gimple_assign_single_p (stmt))
708 bool rhs_aliased = false;
709 /* If this is a load mark things necessary. */
710 rhs = gimple_assign_rhs1 (stmt);
711 if (TREE_CODE (rhs) != SSA_NAME
712 && !is_gimple_min_invariant (rhs))
714 if (!ref_may_be_aliased (rhs))
715 mark_aliased_reaching_defs_necessary (stmt, rhs);
720 mark_all_reaching_defs_necessary (stmt);
722 else if (gimple_code (stmt) == GIMPLE_RETURN)
724 tree rhs = gimple_return_retval (stmt);
725 /* A return statement may perform a load. */
726 if (TREE_CODE (rhs) != SSA_NAME
727 && !is_gimple_min_invariant (rhs))
729 if (!ref_may_be_aliased (rhs))
730 mark_aliased_reaching_defs_necessary (stmt, rhs);
732 mark_all_reaching_defs_necessary (stmt);
735 else if (gimple_code (stmt) == GIMPLE_ASM)
738 mark_all_reaching_defs_necessary (stmt);
739 /* Inputs may perform loads. */
740 for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
742 tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
743 if (TREE_CODE (op) != SSA_NAME
744 && !is_gimple_min_invariant (op)
745 && !ref_may_be_aliased (op))
746 mark_aliased_reaching_defs_necessary (stmt, op);
752 /* If we over-used our alias oracle budget drop to simple
753 mode. The cost metric allows quadratic behavior up to
754 a constant maximal chain and after that falls back to
755 super-linear complexity. */
756 if (longest_chain > 256
757 && total_chain > 256 * longest_chain)
761 bitmap_clear (visited);
768 /* Remove dead PHI nodes from block BB. */
771 remove_dead_phis (basic_block bb)
773 bool something_changed = false;
776 gimple_stmt_iterator gsi;
777 phis = phi_nodes (bb);
779 for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
782 phi = gsi_stmt (gsi);
784 /* We do not track necessity of virtual PHI nodes. Instead do
785 very simple dead PHI removal here. */
786 if (!is_gimple_reg (gimple_phi_result (phi)))
791 /* Virtual PHI nodes with one or identical arguments
793 vuse = gimple_phi_arg_def (phi, 0);
794 for (i = 1; i < gimple_phi_num_args (phi); ++i)
796 if (gimple_phi_arg_def (phi, i) != vuse)
802 if (vuse != NULL_TREE)
804 tree vdef = gimple_phi_result (phi);
806 imm_use_iterator iter;
808 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
809 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
810 SET_USE (use_p, vuse);
811 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
812 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
815 gimple_set_plf (phi, STMT_NECESSARY, true);
818 if (!gimple_plf (phi, STMT_NECESSARY))
820 something_changed = true;
821 if (dump_file && (dump_flags & TDF_DETAILS))
823 fprintf (dump_file, "Deleting : ");
824 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
825 fprintf (dump_file, "\n");
828 remove_phi_node (&gsi, true);
829 stats.removed_phis++;
835 return something_changed;
839 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
840 containing I so that we don't have to look it up. */
843 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
845 gimple stmt = gsi_stmt (*i);
847 if (dump_file && (dump_flags & TDF_DETAILS))
849 fprintf (dump_file, "Deleting : ");
850 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
851 fprintf (dump_file, "\n");
856 /* If we have determined that a conditional branch statement contributes
857 nothing to the program, then we not only remove it, but we also change
858 the flow graph so that the current block will simply fall-thru to its
859 immediate post-dominator. The blocks we are circumventing will be
860 removed by cleanup_tree_cfg if this change in the flow graph makes them
862 if (is_ctrl_stmt (stmt))
864 basic_block post_dom_bb;
866 /* The post dominance info has to be up-to-date. */
867 gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
868 /* Get the immediate post dominator of bb. */
869 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
871 /* There are three particularly problematical cases.
873 1. Blocks that do not have an immediate post dominator. This
874 can happen with infinite loops.
876 2. Blocks that are only post dominated by the exit block. These
877 can also happen for infinite loops as we create fake edges
878 in the dominator tree.
880 3. If the post dominator has PHI nodes we may be able to compute
881 the right PHI args for them.
883 In each of these cases we must remove the control statement
884 as it may reference SSA_NAMEs which are going to be removed and
885 we remove all but one outgoing edge from the block. */
887 || post_dom_bb == EXIT_BLOCK_PTR
888 || phi_nodes (post_dom_bb))
892 /* Redirect the first edge out of BB to reach POST_DOM_BB. */
893 redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
894 PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
896 /* It is not sufficient to set cfg_altered below during edge
897 removal, in case BB has two successors and one of them
901 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
902 EDGE_SUCC (bb, 0)->count = bb->count;
904 /* The edge is no longer associated with a conditional, so it does
905 not have TRUE/FALSE flags. */
906 EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
908 /* The lone outgoing edge from BB will be a fallthru edge. */
909 EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
911 /* Remove the remaining the outgoing edges. */
912 while (!single_succ_p (bb))
914 /* FIXME. When we remove the edge, we modify the CFG, which
915 in turn modifies the dominator and post-dominator tree.
916 Is it safe to postpone recomputing the dominator and
917 post-dominator tree until the end of this pass given that
918 the post-dominators are used above? */
920 remove_edge (EDGE_SUCC (bb, 1));
924 unlink_stmt_vdef (stmt);
925 gsi_remove (i, true);
930 /* Eliminate unnecessary statements. Any instruction not marked as necessary
931 contributes nothing to the program, and can be deleted. */
934 eliminate_unnecessary_stmts (void)
936 bool something_changed = false;
938 gimple_stmt_iterator gsi;
942 if (dump_file && (dump_flags & TDF_DETAILS))
943 fprintf (dump_file, "\nEliminating unnecessary statements:\n");
945 clear_special_calls ();
949 /* Remove dead statements. */
950 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
952 stmt = gsi_stmt (gsi);
956 /* If GSI is not necessary then remove it. */
957 if (!gimple_plf (stmt, STMT_NECESSARY))
959 remove_dead_stmt (&gsi, bb);
960 something_changed = true;
962 else if (is_gimple_call (stmt))
964 call = gimple_call_fndecl (stmt);
969 /* When LHS of var = call (); is dead, simplify it into
970 call (); saving one operand. */
971 name = gimple_call_lhs (stmt);
972 if (name && TREE_CODE (name) == SSA_NAME
973 && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
975 something_changed = true;
976 if (dump_file && (dump_flags & TDF_DETAILS))
978 fprintf (dump_file, "Deleting LHS of call: ");
979 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
980 fprintf (dump_file, "\n");
983 gimple_call_set_lhs (stmt, NULL_TREE);
984 maybe_clean_or_replace_eh_stmt (stmt, stmt);
986 release_ssa_name (name);
988 notice_special_calls (stmt);
1001 /* Remove dead PHI nodes. */
1002 something_changed |= remove_dead_phis (bb);
1005 return something_changed;
1009 /* Print out removed statement statistics. */
1016 percg = ((float) stats.removed / (float) stats.total) * 100;
1017 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1018 stats.removed, stats.total, (int) percg);
1020 if (stats.total_phis == 0)
1023 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1025 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1026 stats.removed_phis, stats.total_phis, (int) percg);
1029 /* Initialization for this pass. Set up the used data structures. */
1032 tree_dce_init (bool aggressive)
1034 memset ((void *) &stats, 0, sizeof (stats));
1040 control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1041 for (i = 0; i < last_basic_block; ++i)
1042 control_dependence_map[i] = BITMAP_ALLOC (NULL);
1044 last_stmt_necessary = sbitmap_alloc (last_basic_block);
1045 sbitmap_zero (last_stmt_necessary);
1048 processed = sbitmap_alloc (num_ssa_names + 1);
1049 sbitmap_zero (processed);
1051 worklist = VEC_alloc (gimple, heap, 64);
1052 cfg_altered = false;
1055 /* Cleanup after this pass. */
1058 tree_dce_done (bool aggressive)
1064 for (i = 0; i < last_basic_block; ++i)
1065 BITMAP_FREE (control_dependence_map[i]);
1066 free (control_dependence_map);
1068 sbitmap_free (visited_control_parents);
1069 sbitmap_free (last_stmt_necessary);
1072 sbitmap_free (processed);
1074 VEC_free (gimple, heap, worklist);
1077 /* Main routine to eliminate dead code.
1079 AGGRESSIVE controls the aggressiveness of the algorithm.
1080 In conservative mode, we ignore control dependence and simply declare
1081 all but the most trivially dead branches necessary. This mode is fast.
1082 In aggressive mode, control dependences are taken into account, which
1083 results in more dead code elimination, but at the cost of some time.
1085 FIXME: Aggressive mode before PRE doesn't work currently because
1086 the dominance info is not invalidated after DCE1. This is
1087 not an issue right now because we only run aggressive DCE
1088 as the last tree SSA pass, but keep this in mind when you
1089 start experimenting with pass ordering. */
1092 perform_tree_ssa_dce (bool aggressive)
1094 struct edge_list *el = NULL;
1095 bool something_changed = 0;
1097 tree_dce_init (aggressive);
1101 /* Compute control dependence. */
1102 timevar_push (TV_CONTROL_DEPENDENCES);
1103 calculate_dominance_info (CDI_POST_DOMINATORS);
1104 el = create_edge_list ();
1105 find_all_control_dependences (el);
1106 timevar_pop (TV_CONTROL_DEPENDENCES);
1108 visited_control_parents = sbitmap_alloc (last_basic_block);
1109 sbitmap_zero (visited_control_parents);
1111 mark_dfs_back_edges ();
1114 find_obviously_necessary_stmts (el);
1119 propagate_necessity (el);
1120 BITMAP_FREE (visited);
1122 something_changed |= eliminate_unnecessary_stmts ();
1123 something_changed |= cfg_altered;
1125 /* We do not update postdominators, so free them unconditionally. */
1126 free_dominance_info (CDI_POST_DOMINATORS);
1128 /* If we removed paths in the CFG, then we need to update
1129 dominators as well. I haven't investigated the possibility
1130 of incrementally updating dominators. */
1132 free_dominance_info (CDI_DOMINATORS);
1134 statistics_counter_event (cfun, "Statements deleted", stats.removed);
1135 statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1137 /* Debugging dumps. */
1138 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1141 tree_dce_done (aggressive);
1143 free_edge_list (el);
1145 if (something_changed)
1146 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1147 | TODO_remove_unused_locals);
1152 /* Pass entry points. */
1156 return perform_tree_ssa_dce (/*aggressive=*/false);
1160 tree_ssa_dce_loop (void)
1163 todo = perform_tree_ssa_dce (/*aggressive=*/false);
1166 free_numbers_of_iterations_estimates ();
1173 tree_ssa_cd_dce (void)
1175 return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1181 return flag_tree_dce != 0;
1184 struct gimple_opt_pass pass_dce =
1189 gate_dce, /* gate */
1190 tree_ssa_dce, /* execute */
1193 0, /* static_pass_number */
1194 TV_TREE_DCE, /* tv_id */
1195 PROP_cfg | PROP_ssa, /* properties_required */
1196 0, /* properties_provided */
1197 0, /* properties_destroyed */
1198 0, /* todo_flags_start */
1199 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1203 struct gimple_opt_pass pass_dce_loop =
1207 "dceloop", /* name */
1208 gate_dce, /* gate */
1209 tree_ssa_dce_loop, /* execute */
1212 0, /* static_pass_number */
1213 TV_TREE_DCE, /* tv_id */
1214 PROP_cfg | PROP_ssa, /* properties_required */
1215 0, /* properties_provided */
1216 0, /* properties_destroyed */
1217 0, /* todo_flags_start */
1218 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1222 struct gimple_opt_pass pass_cd_dce =
1227 gate_dce, /* gate */
1228 tree_ssa_cd_dce, /* execute */
1231 0, /* static_pass_number */
1232 TV_TREE_CD_DCE, /* tv_id */
1233 PROP_cfg | PROP_ssa, /* properties_required */
1234 0, /* properties_provided */
1235 0, /* properties_destroyed */
1236 0, /* todo_flags_start */
1237 TODO_dump_func | TODO_verify_ssa
1238 | TODO_verify_flow /* todo_flags_finish */