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 /* Vector indicating that BB contains statements that are live. */
91 static sbitmap bb_contains_live_stmts;
93 /* Before we can determine whether a control branch is dead, we need to
94 compute which blocks are control dependent on which edges.
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
100 static bitmap *control_dependence_map;
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;
106 /* TRUE if this pass alters the CFG (by removing control statements).
109 If this pass alters the CFG, then it will arrange for the dominators
111 static bool cfg_altered;
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, \
121 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
123 set_control_dependence_map_bit (basic_block bb, int edge_index)
125 if (bb == ENTRY_BLOCK_PTR)
127 gcc_assert (bb != EXIT_BLOCK_PTR);
128 bitmap_set_bit (control_dependence_map[bb->index], edge_index);
131 /* Clear all control dependences for block BB. */
133 clear_control_dependence_bitmap (basic_block bb)
135 bitmap_clear (control_dependence_map[bb->index]);
139 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
140 This function is necessary because some blocks have negative numbers. */
142 static inline basic_block
143 find_pdom (basic_block block)
145 gcc_assert (block != ENTRY_BLOCK_PTR);
147 if (block == EXIT_BLOCK_PTR)
148 return EXIT_BLOCK_PTR;
151 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
153 return EXIT_BLOCK_PTR;
159 /* Determine all blocks' control dependences on the given edge with edge_list
160 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
163 find_control_dependence (struct edge_list *el, int edge_index)
165 basic_block current_block;
166 basic_block ending_block;
168 gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
170 if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
171 ending_block = single_succ (ENTRY_BLOCK_PTR);
173 ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
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))
179 edge e = INDEX_EDGE (el, edge_index);
181 /* For abnormal edges, we don't make current_block control
182 dependent because instructions that throw are always necessary
184 if (e->flags & EDGE_ABNORMAL)
187 set_control_dependence_map_bit (current_block, edge_index);
192 /* Record all blocks' control dependences on all edges in the edge
193 list EL, ala Morgan, Section 3.6. */
196 find_all_control_dependences (struct edge_list *el)
200 for (i = 0; i < NUM_EDGES (el); ++i)
201 find_control_dependence (el, i);
204 /* If STMT is not already marked necessary, mark it, and add it to the
205 worklist if ADD_TO_WORKLIST is true. */
207 mark_stmt_necessary (gimple stmt, bool add_to_worklist)
211 if (gimple_plf (stmt, STMT_NECESSARY))
214 if (dump_file && (dump_flags & TDF_DETAILS))
216 fprintf (dump_file, "Marking useful stmt: ");
217 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
218 fprintf (dump_file, "\n");
221 gimple_set_plf (stmt, STMT_NECESSARY, true);
223 VEC_safe_push (gimple, heap, worklist, stmt);
224 if (bb_contains_live_stmts)
225 SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
229 /* Mark the statement defining operand OP as necessary. */
232 mark_operand_necessary (tree op)
239 ver = SSA_NAME_VERSION (op);
240 if (TEST_BIT (processed, ver))
242 stmt = SSA_NAME_DEF_STMT (op);
243 gcc_assert (gimple_nop_p (stmt)
244 || gimple_plf (stmt, STMT_NECESSARY));
247 SET_BIT (processed, ver);
249 stmt = SSA_NAME_DEF_STMT (op);
252 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
255 if (dump_file && (dump_flags & TDF_DETAILS))
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);
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);
270 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
271 it can make other statements necessary.
273 If AGGRESSIVE is false, control statements are conservatively marked as
277 mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
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))
285 mark_stmt_necessary (stmt, true);
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
295 switch (gimple_code (stmt))
299 mark_stmt_necessary (stmt, false);
305 mark_stmt_necessary (stmt, true);
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))
314 mark_stmt_necessary (stmt, true);
317 if (!gimple_call_lhs (stmt))
319 lhs = gimple_call_lhs (stmt);
324 lhs = gimple_assign_lhs (stmt);
325 /* These values are mildly magic bits of the EH runtime. We can't
326 see the entire lifetime of these values until landing pads are
328 if (TREE_CODE (lhs) == EXC_PTR_EXPR
329 || TREE_CODE (lhs) == FILTER_EXPR)
331 mark_stmt_necessary (stmt, true);
337 gcc_assert (!simple_goto_p (stmt));
338 mark_stmt_necessary (stmt, true);
342 gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
347 mark_stmt_necessary (stmt, true);
354 /* If the statement has volatile operands, it needs to be preserved.
355 Same for statements that can alter control flow in unpredictable
357 if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
359 mark_stmt_necessary (stmt, true);
363 if (is_hidden_global_store (stmt))
365 mark_stmt_necessary (stmt, true);
373 /* Make corresponding control dependent edges necessary. We only
374 have to do this once for each basic block, so we clear the bitmap
377 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
380 unsigned edge_number;
382 gcc_assert (bb != EXIT_BLOCK_PTR);
384 if (bb == ENTRY_BLOCK_PTR)
387 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
390 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
392 if (TEST_BIT (last_stmt_necessary, cd_bb->index))
394 SET_BIT (last_stmt_necessary, cd_bb->index);
395 SET_BIT (bb_contains_live_stmts, cd_bb->index);
397 stmt = last_stmt (cd_bb);
398 if (stmt && is_ctrl_stmt (stmt))
399 mark_stmt_necessary (stmt, true);
404 /* Find obviously necessary statements. These are things like most function
405 calls, and stores to file level variables.
407 If EL is NULL, control statements are conservatively marked as
408 necessary. Otherwise it contains the list of edges used by control
409 dependence analysis. */
412 find_obviously_necessary_stmts (struct edge_list *el)
415 gimple_stmt_iterator gsi;
421 /* PHI nodes are never inherently necessary. */
422 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
424 phi = gsi_stmt (gsi);
425 gimple_set_plf (phi, STMT_NECESSARY, false);
428 /* Check all statements in the block. */
429 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
431 stmt = gsi_stmt (gsi);
432 gimple_set_plf (stmt, STMT_NECESSARY, false);
433 mark_stmt_if_obviously_necessary (stmt, el != NULL);
439 /* Prevent the loops from being removed. We must keep the infinite loops,
440 and we currently do not have a means to recognize the finite ones. */
444 FOR_EACH_EDGE (e, ei, bb->succs)
445 if (e->flags & EDGE_DFS_BACK)
446 mark_control_dependent_edges_necessary (e->dest, el);
452 /* Return true if REF is based on an aliased base, otherwise false. */
455 ref_may_be_aliased (tree ref)
457 while (handled_component_p (ref))
458 ref = TREE_OPERAND (ref, 0);
459 return !(DECL_P (ref)
460 && !may_be_aliased (ref));
463 static bitmap visited = NULL;
464 static unsigned int longest_chain = 0;
465 static unsigned int total_chain = 0;
466 static bool chain_ovfl = false;
468 /* Worker for the walker that marks reaching definitions of REF,
469 which is based on a non-aliased decl, necessary. It returns
470 true whenever the defining statement of the current VDEF is
471 a kill for REF, as no dominating may-defs are necessary for REF
472 anymore. DATA points to cached get_ref_base_and_extent data for REF. */
475 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
476 void *data ATTRIBUTE_UNUSED)
478 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
480 /* All stmts we visit are necessary. */
481 mark_operand_necessary (vdef);
483 /* If the stmt lhs kills ref, then we can stop walking. */
484 if (gimple_has_lhs (def_stmt)
485 && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
487 tree base, lhs = gimple_get_lhs (def_stmt);
488 HOST_WIDE_INT size, offset, max_size;
490 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
491 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
492 so base == refd->base does not always hold. */
493 if (base == ref->base)
495 /* For a must-alias check we need to be able to constrain
496 the accesses properly. */
497 if (size != -1 && size == max_size
498 && ref->max_size != -1)
500 if (offset <= ref->offset
501 && offset + size >= ref->offset + ref->max_size)
504 /* Or they need to be exactly the same. */
506 && operand_equal_p (ref->ref, lhs, 0))
511 /* Otherwise keep walking. */
516 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
520 gcc_assert (!chain_ovfl);
521 ao_ref_init (&refd, ref);
522 chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
523 mark_aliased_reaching_defs_necessary_1,
525 if (chain > longest_chain)
526 longest_chain = chain;
527 total_chain += chain;
530 /* Worker for the walker that marks reaching definitions of REF, which
531 is not based on a non-aliased decl. For simplicity we need to end
532 up marking all may-defs necessary that are not based on a non-aliased
533 decl. The only job of this walker is to skip may-defs based on
534 a non-aliased decl. */
537 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
538 tree vdef, void *data ATTRIBUTE_UNUSED)
540 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
542 /* We have to skip already visited (and thus necessary) statements
543 to make the chaining work after we dropped back to simple mode. */
545 && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
547 gcc_assert (gimple_nop_p (def_stmt)
548 || gimple_plf (def_stmt, STMT_NECESSARY));
552 /* We want to skip stores to non-aliased variables. */
554 && gimple_assign_single_p (def_stmt))
556 tree lhs = gimple_assign_lhs (def_stmt);
557 if (!ref_may_be_aliased (lhs))
561 mark_operand_necessary (vdef);
567 mark_all_reaching_defs_necessary (gimple stmt)
569 walk_aliased_vdefs (NULL, gimple_vuse (stmt),
570 mark_all_reaching_defs_necessary_1, NULL, &visited);
573 /* Propagate necessity using the operands of necessary statements.
574 Process the uses on each statement in the worklist, and add all
575 feeding statements which contribute to the calculation of this
576 value to the worklist.
578 In conservative mode, EL is NULL. */
581 propagate_necessity (struct edge_list *el)
584 bool aggressive = (el ? true : false);
586 if (dump_file && (dump_flags & TDF_DETAILS))
587 fprintf (dump_file, "\nProcessing worklist:\n");
589 while (VEC_length (gimple, worklist) > 0)
591 /* Take STMT from worklist. */
592 stmt = VEC_pop (gimple, worklist);
594 if (dump_file && (dump_flags & TDF_DETAILS))
596 fprintf (dump_file, "processing: ");
597 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
598 fprintf (dump_file, "\n");
603 /* Mark the last statements of the basic blocks that the block
604 containing STMT is control dependent on, but only if we haven't
606 basic_block bb = gimple_bb (stmt);
607 if (bb != ENTRY_BLOCK_PTR
608 && ! TEST_BIT (visited_control_parents, bb->index))
610 SET_BIT (visited_control_parents, bb->index);
611 mark_control_dependent_edges_necessary (bb, el);
615 if (gimple_code (stmt) == GIMPLE_PHI
616 /* We do not process virtual PHI nodes nor do we track their
618 && is_gimple_reg (gimple_phi_result (stmt)))
620 /* PHI nodes are somewhat special in that each PHI alternative has
621 data and control dependencies. All the statements feeding the
622 PHI node's arguments are always necessary. In aggressive mode,
623 we also consider the control dependent edges leading to the
624 predecessor block associated with each PHI alternative as
628 for (k = 0; k < gimple_phi_num_args (stmt); k++)
630 tree arg = PHI_ARG_DEF (stmt, k);
631 if (TREE_CODE (arg) == SSA_NAME)
632 mark_operand_necessary (arg);
637 for (k = 0; k < gimple_phi_num_args (stmt); k++)
639 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
640 if (arg_bb != ENTRY_BLOCK_PTR
641 && ! TEST_BIT (visited_control_parents, arg_bb->index))
643 SET_BIT (visited_control_parents, arg_bb->index);
644 mark_control_dependent_edges_necessary (arg_bb, el);
651 /* Propagate through the operands. Examine all the USE, VUSE and
652 VDEF operands in this statement. Mark all the statements
653 which feed this statement's uses as necessary. */
657 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
658 mark_operand_necessary (use);
660 use = gimple_vuse (stmt);
664 /* If we dropped to simple mode make all immediately
665 reachable definitions necessary. */
668 mark_all_reaching_defs_necessary (stmt);
672 /* For statements that may load from memory (have a VUSE) we
673 have to mark all reaching (may-)definitions as necessary.
674 We partition this task into two cases:
675 1) explicit loads based on decls that are not aliased
676 2) implicit loads (like calls) and explicit loads not
677 based on decls that are not aliased (like indirect
678 references or loads from globals)
679 For 1) we mark all reaching may-defs as necessary, stopping
680 at dominating kills. For 2) we want to mark all dominating
681 references necessary, but non-aliased ones which we handle
682 in 1). By keeping a global visited bitmap for references
683 we walk for 2) we avoid quadratic behavior for those. */
685 if (is_gimple_call (stmt))
687 tree callee = gimple_call_fndecl (stmt);
690 /* Calls to functions that are merely acting as barriers
691 or that only store to memory do not make any previous
693 if (callee != NULL_TREE
694 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
695 && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
696 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
697 || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
700 /* Calls implicitly load from memory, their arguments
701 in addition may explicitly perform memory loads. */
702 mark_all_reaching_defs_necessary (stmt);
703 for (i = 0; i < gimple_call_num_args (stmt); ++i)
705 tree arg = gimple_call_arg (stmt, i);
706 if (TREE_CODE (arg) == SSA_NAME
707 || is_gimple_min_invariant (arg))
709 if (!ref_may_be_aliased (arg))
710 mark_aliased_reaching_defs_necessary (stmt, arg);
713 else if (gimple_assign_single_p (stmt))
716 bool rhs_aliased = false;
717 /* If this is a load mark things necessary. */
718 rhs = gimple_assign_rhs1 (stmt);
719 if (TREE_CODE (rhs) != SSA_NAME
720 && !is_gimple_min_invariant (rhs))
722 if (!ref_may_be_aliased (rhs))
723 mark_aliased_reaching_defs_necessary (stmt, rhs);
728 mark_all_reaching_defs_necessary (stmt);
730 else if (gimple_code (stmt) == GIMPLE_RETURN)
732 tree rhs = gimple_return_retval (stmt);
733 /* A return statement may perform a load. */
734 if (TREE_CODE (rhs) != SSA_NAME
735 && !is_gimple_min_invariant (rhs))
737 if (!ref_may_be_aliased (rhs))
738 mark_aliased_reaching_defs_necessary (stmt, rhs);
740 mark_all_reaching_defs_necessary (stmt);
743 else if (gimple_code (stmt) == GIMPLE_ASM)
746 mark_all_reaching_defs_necessary (stmt);
747 /* Inputs may perform loads. */
748 for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
750 tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
751 if (TREE_CODE (op) != SSA_NAME
752 && !is_gimple_min_invariant (op)
753 && !ref_may_be_aliased (op))
754 mark_aliased_reaching_defs_necessary (stmt, op);
760 /* If we over-used our alias oracle budget drop to simple
761 mode. The cost metric allows quadratic behavior up to
762 a constant maximal chain and after that falls back to
763 super-linear complexity. */
764 if (longest_chain > 256
765 && total_chain > 256 * longest_chain)
769 bitmap_clear (visited);
775 /* Replace all uses of result of PHI by underlying variable and mark it
779 mark_virtual_phi_result_for_renaming (gimple phi)
782 imm_use_iterator iter;
785 if (dump_file && (dump_flags & TDF_DETAILS))
787 fprintf (dump_file, "Marking result for renaming : ");
788 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
789 fprintf (dump_file, "\n");
791 FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (phi))
793 if (gimple_code (stmt) != GIMPLE_PHI
794 && !gimple_plf (stmt, STMT_NECESSARY))
796 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
797 SET_USE (use_p, SSA_NAME_VAR (gimple_phi_result (phi)));
802 mark_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (phi)));
805 /* Remove dead PHI nodes from block BB. */
808 remove_dead_phis (basic_block bb)
810 bool something_changed = false;
813 gimple_stmt_iterator gsi;
814 phis = phi_nodes (bb);
816 for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
819 phi = gsi_stmt (gsi);
821 /* We do not track necessity of virtual PHI nodes. Instead do
822 very simple dead PHI removal here. */
823 if (!is_gimple_reg (gimple_phi_result (phi)))
828 /* Virtual PHI nodes with one or identical arguments
830 vuse = gimple_phi_arg_def (phi, 0);
831 for (i = 1; i < gimple_phi_num_args (phi); ++i)
833 if (gimple_phi_arg_def (phi, i) != vuse)
839 if (vuse != NULL_TREE)
841 tree vdef = gimple_phi_result (phi);
843 imm_use_iterator iter;
845 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
846 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
847 SET_USE (use_p, vuse);
848 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
849 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
852 gimple_set_plf (phi, STMT_NECESSARY, true);
855 if (!gimple_plf (phi, STMT_NECESSARY))
857 something_changed = true;
858 if (dump_file && (dump_flags & TDF_DETAILS))
860 fprintf (dump_file, "Deleting : ");
861 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
862 fprintf (dump_file, "\n");
865 remove_phi_node (&gsi, true);
866 stats.removed_phis++;
872 return something_changed;
875 /* Find first live post dominator of BB. */
878 get_live_post_dom (basic_block bb)
880 basic_block post_dom_bb;
883 /* The post dominance info has to be up-to-date. */
884 gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
886 /* Get the immediate post dominator of bb. */
887 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
888 /* And look for first live one. */
889 while (post_dom_bb != EXIT_BLOCK_PTR
890 && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
891 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
896 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
899 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
901 gimple_stmt_iterator gsi;
905 if (dump_file && (dump_flags & TDF_DETAILS))
906 fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
907 e->dest->index, post_dom_bb->index);
909 e2 = redirect_edge_and_branch (e, post_dom_bb);
912 /* If edge was already around, no updating is neccesary. */
916 if (phi_nodes (post_dom_bb))
918 /* We are sure that for every live PHI we are seeing control dependent BB.
919 This means that we can look up the end of control dependent path leading
920 to the PHI itself. */
921 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
922 if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
924 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
926 gimple phi = gsi_stmt (gsi);
928 /* Dead PHI do not imply control dependency. */
929 if (!gimple_plf (phi, STMT_NECESSARY)
930 && is_gimple_reg (gimple_phi_result (phi)))
935 if (gimple_phi_arg_def (phi, e->dest_idx))
941 /* We didn't find edge to update. This can happen for PHIs on virtuals
942 since there is no control dependency relation on them. We are lost
943 here and must force renaming of the symbol. */
944 if (!is_gimple_reg (gimple_phi_result (phi)))
946 mark_virtual_phi_result_for_renaming (phi);
947 remove_phi_node (&gsi, true);
951 add_phi_arg (phi, gimple_phi_arg_def (phi, e2->dest_idx), e);
958 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
959 containing I so that we don't have to look it up. */
962 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
964 gimple stmt = gsi_stmt (*i);
966 if (dump_file && (dump_flags & TDF_DETAILS))
968 fprintf (dump_file, "Deleting : ");
969 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
970 fprintf (dump_file, "\n");
975 /* If we have determined that a conditional branch statement contributes
976 nothing to the program, then we not only remove it, but we also change
977 the flow graph so that the current block will simply fall-thru to its
978 immediate post-dominator. The blocks we are circumventing will be
979 removed by cleanup_tree_cfg if this change in the flow graph makes them
981 if (is_ctrl_stmt (stmt))
983 basic_block post_dom_bb;
987 post_dom_bb = get_live_post_dom (bb);
989 e = find_edge (bb, post_dom_bb);
991 /* If edge is already there, try to use it. This avoids need to update
992 PHI nodes. Also watch for cases where post dominator does not exists
993 or is exit block. These can happen for infinite loops as we create
994 fake edges in the dominator tree. */
997 else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
998 e = EDGE_SUCC (bb, 0);
1000 e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1002 e->probability = REG_BR_PROB_BASE;
1003 e->count = bb->count;
1005 /* The edge is no longer associated with a conditional, so it does
1006 not have TRUE/FALSE flags. */
1007 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1009 /* The lone outgoing edge from BB will be a fallthru edge. */
1010 e->flags |= EDGE_FALLTHRU;
1012 /* Remove the remaining outgoing edges. */
1013 for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1023 unlink_stmt_vdef (stmt);
1024 gsi_remove (i, true);
1025 release_defs (stmt);
1029 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1030 contributes nothing to the program, and can be deleted. */
1033 eliminate_unnecessary_stmts (void)
1035 bool something_changed = false;
1037 gimple_stmt_iterator gsi;
1041 if (dump_file && (dump_flags & TDF_DETAILS))
1042 fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1044 clear_special_calls ();
1048 /* Remove dead statements. */
1049 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1051 stmt = gsi_stmt (gsi);
1055 /* If GSI is not necessary then remove it. */
1056 if (!gimple_plf (stmt, STMT_NECESSARY))
1058 remove_dead_stmt (&gsi, bb);
1059 something_changed = true;
1061 else if (is_gimple_call (stmt))
1063 call = gimple_call_fndecl (stmt);
1068 /* When LHS of var = call (); is dead, simplify it into
1069 call (); saving one operand. */
1070 name = gimple_call_lhs (stmt);
1071 if (name && TREE_CODE (name) == SSA_NAME
1072 && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1074 something_changed = true;
1075 if (dump_file && (dump_flags & TDF_DETAILS))
1077 fprintf (dump_file, "Deleting LHS of call: ");
1078 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1079 fprintf (dump_file, "\n");
1082 gimple_call_set_lhs (stmt, NULL_TREE);
1083 maybe_clean_or_replace_eh_stmt (stmt, stmt);
1085 release_ssa_name (name);
1087 notice_special_calls (stmt);
1100 /* Remove dead PHI nodes. */
1101 something_changed |= remove_dead_phis (bb);
1104 return something_changed;
1108 /* Print out removed statement statistics. */
1115 percg = ((float) stats.removed / (float) stats.total) * 100;
1116 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1117 stats.removed, stats.total, (int) percg);
1119 if (stats.total_phis == 0)
1122 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1124 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1125 stats.removed_phis, stats.total_phis, (int) percg);
1128 /* Initialization for this pass. Set up the used data structures. */
1131 tree_dce_init (bool aggressive)
1133 memset ((void *) &stats, 0, sizeof (stats));
1139 control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1140 for (i = 0; i < last_basic_block; ++i)
1141 control_dependence_map[i] = BITMAP_ALLOC (NULL);
1143 last_stmt_necessary = sbitmap_alloc (last_basic_block);
1144 sbitmap_zero (last_stmt_necessary);
1145 bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1146 sbitmap_zero (bb_contains_live_stmts);
1149 processed = sbitmap_alloc (num_ssa_names + 1);
1150 sbitmap_zero (processed);
1152 worklist = VEC_alloc (gimple, heap, 64);
1153 cfg_altered = false;
1156 /* Cleanup after this pass. */
1159 tree_dce_done (bool aggressive)
1165 for (i = 0; i < last_basic_block; ++i)
1166 BITMAP_FREE (control_dependence_map[i]);
1167 free (control_dependence_map);
1169 sbitmap_free (visited_control_parents);
1170 sbitmap_free (last_stmt_necessary);
1171 sbitmap_free (bb_contains_live_stmts);
1172 bb_contains_live_stmts = NULL;
1175 sbitmap_free (processed);
1177 VEC_free (gimple, heap, worklist);
1180 /* Main routine to eliminate dead code.
1182 AGGRESSIVE controls the aggressiveness of the algorithm.
1183 In conservative mode, we ignore control dependence and simply declare
1184 all but the most trivially dead branches necessary. This mode is fast.
1185 In aggressive mode, control dependences are taken into account, which
1186 results in more dead code elimination, but at the cost of some time.
1188 FIXME: Aggressive mode before PRE doesn't work currently because
1189 the dominance info is not invalidated after DCE1. This is
1190 not an issue right now because we only run aggressive DCE
1191 as the last tree SSA pass, but keep this in mind when you
1192 start experimenting with pass ordering. */
1195 perform_tree_ssa_dce (bool aggressive)
1197 struct edge_list *el = NULL;
1198 bool something_changed = 0;
1200 tree_dce_init (aggressive);
1204 /* Compute control dependence. */
1205 timevar_push (TV_CONTROL_DEPENDENCES);
1206 calculate_dominance_info (CDI_POST_DOMINATORS);
1207 el = create_edge_list ();
1208 find_all_control_dependences (el);
1209 timevar_pop (TV_CONTROL_DEPENDENCES);
1211 visited_control_parents = sbitmap_alloc (last_basic_block);
1212 sbitmap_zero (visited_control_parents);
1214 mark_dfs_back_edges ();
1217 find_obviously_necessary_stmts (el);
1222 propagate_necessity (el);
1223 BITMAP_FREE (visited);
1225 something_changed |= eliminate_unnecessary_stmts ();
1226 something_changed |= cfg_altered;
1228 /* We do not update postdominators, so free them unconditionally. */
1229 free_dominance_info (CDI_POST_DOMINATORS);
1231 /* If we removed paths in the CFG, then we need to update
1232 dominators as well. I haven't investigated the possibility
1233 of incrementally updating dominators. */
1235 free_dominance_info (CDI_DOMINATORS);
1237 statistics_counter_event (cfun, "Statements deleted", stats.removed);
1238 statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1240 /* Debugging dumps. */
1241 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1244 tree_dce_done (aggressive);
1246 free_edge_list (el);
1248 if (something_changed)
1249 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1250 | TODO_remove_unused_locals);
1255 /* Pass entry points. */
1259 return perform_tree_ssa_dce (/*aggressive=*/false);
1263 tree_ssa_dce_loop (void)
1266 todo = perform_tree_ssa_dce (/*aggressive=*/false);
1269 free_numbers_of_iterations_estimates ();
1276 tree_ssa_cd_dce (void)
1278 return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1284 return flag_tree_dce != 0;
1287 struct gimple_opt_pass pass_dce =
1292 gate_dce, /* gate */
1293 tree_ssa_dce, /* execute */
1296 0, /* static_pass_number */
1297 TV_TREE_DCE, /* tv_id */
1298 PROP_cfg | PROP_ssa, /* properties_required */
1299 0, /* properties_provided */
1300 0, /* properties_destroyed */
1301 0, /* todo_flags_start */
1302 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1306 struct gimple_opt_pass pass_dce_loop =
1310 "dceloop", /* name */
1311 gate_dce, /* gate */
1312 tree_ssa_dce_loop, /* execute */
1315 0, /* static_pass_number */
1316 TV_TREE_DCE, /* tv_id */
1317 PROP_cfg | PROP_ssa, /* properties_required */
1318 0, /* properties_provided */
1319 0, /* properties_destroyed */
1320 0, /* todo_flags_start */
1321 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
1325 struct gimple_opt_pass pass_cd_dce =
1330 gate_dce, /* gate */
1331 tree_ssa_cd_dce, /* execute */
1334 0, /* static_pass_number */
1335 TV_TREE_CD_DCE, /* tv_id */
1336 PROP_cfg | PROP_ssa, /* properties_required */
1337 0, /* properties_provided */
1338 0, /* properties_destroyed */
1339 0, /* todo_flags_start */
1340 TODO_dump_func | TODO_verify_ssa
1341 | TODO_verify_flow /* todo_flags_finish */