gcc/
[official-gcc.git] / gcc / tree-ssa-dce.c
blob181626cf979d18eba9464ee881b139924e2b1c60
1 /* Dead code elimination pass for the GNU compiler.
2 Copyright (C) 2002-2015 Free Software Foundation, Inc.
3 Contributed by Ben Elliston <bje@redhat.com>
4 and Andrew MacLeod <amacleod@redhat.com>
5 Adapted to use control dependence by Steven Bosscher, SUSE Labs.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3, or (at your option) any
12 later version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Dead code elimination.
25 References:
27 Building an Optimizing Compiler,
28 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
30 Advanced Compiler Design and Implementation,
31 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
33 Dead-code elimination is the removal of statements which have no
34 impact on the program's output. "Dead statements" have no impact
35 on the program's output, while "necessary statements" may have
36 impact on the output.
38 The algorithm consists of three phases:
39 1. Marking as necessary all statements known to be necessary,
40 e.g. most function calls, writing a value to memory, etc;
41 2. Propagating necessary statements, e.g., the statements
42 giving values to operands in necessary statements; and
43 3. Removing dead statements. */
45 #include "config.h"
46 #include "system.h"
47 #include "coretypes.h"
48 #include "tm.h"
49 #include "alias.h"
50 #include "symtab.h"
51 #include "tree.h"
52 #include "fold-const.h"
53 #include "calls.h"
54 #include "gimple-pretty-print.h"
55 #include "predict.h"
56 #include "hard-reg-set.h"
57 #include "function.h"
58 #include "dominance.h"
59 #include "cfg.h"
60 #include "cfganal.h"
61 #include "basic-block.h"
62 #include "tree-ssa-alias.h"
63 #include "internal-fn.h"
64 #include "tree-eh.h"
65 #include "gimple-expr.h"
66 #include "gimple.h"
67 #include "gimplify.h"
68 #include "gimple-iterator.h"
69 #include "gimple-ssa.h"
70 #include "tree-cfg.h"
71 #include "tree-phinodes.h"
72 #include "ssa-iterators.h"
73 #include "stringpool.h"
74 #include "tree-ssanames.h"
75 #include "tree-ssa-loop-niter.h"
76 #include "tree-into-ssa.h"
77 #include "rtl.h"
78 #include "flags.h"
79 #include "insn-config.h"
80 #include "expmed.h"
81 #include "dojump.h"
82 #include "explow.h"
83 #include "emit-rtl.h"
84 #include "varasm.h"
85 #include "stmt.h"
86 #include "expr.h"
87 #include "tree-dfa.h"
88 #include "tree-pass.h"
89 #include "cfgloop.h"
90 #include "tree-scalar-evolution.h"
91 #include "tree-chkp.h"
92 #include "tree-ssa-propagate.h"
93 #include "gimple-fold.h"
95 static struct stmt_stats
97 int total;
98 int total_phis;
99 int removed;
100 int removed_phis;
101 } stats;
103 #define STMT_NECESSARY GF_PLF_1
105 static vec<gimple> worklist;
107 /* Vector indicating an SSA name has already been processed and marked
108 as necessary. */
109 static sbitmap processed;
111 /* Vector indicating that the last statement of a basic block has already
112 been marked as necessary. */
113 static sbitmap last_stmt_necessary;
115 /* Vector indicating that BB contains statements that are live. */
116 static sbitmap bb_contains_live_stmts;
118 /* Before we can determine whether a control branch is dead, we need to
119 compute which blocks are control dependent on which edges.
121 We expect each block to be control dependent on very few edges so we
122 use a bitmap for each block recording its edges. An array holds the
123 bitmap. The Ith bit in the bitmap is set if that block is dependent
124 on the Ith edge. */
125 static control_dependences *cd;
127 /* Vector indicating that a basic block has already had all the edges
128 processed that it is control dependent on. */
129 static sbitmap visited_control_parents;
131 /* TRUE if this pass alters the CFG (by removing control statements).
132 FALSE otherwise.
134 If this pass alters the CFG, then it will arrange for the dominators
135 to be recomputed. */
136 static bool cfg_altered;
139 /* If STMT is not already marked necessary, mark it, and add it to the
140 worklist if ADD_TO_WORKLIST is true. */
142 static inline void
143 mark_stmt_necessary (gimple stmt, bool add_to_worklist)
145 gcc_assert (stmt);
147 if (gimple_plf (stmt, STMT_NECESSARY))
148 return;
150 if (dump_file && (dump_flags & TDF_DETAILS))
152 fprintf (dump_file, "Marking useful stmt: ");
153 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
154 fprintf (dump_file, "\n");
157 gimple_set_plf (stmt, STMT_NECESSARY, true);
158 if (add_to_worklist)
159 worklist.safe_push (stmt);
160 if (bb_contains_live_stmts && !is_gimple_debug (stmt))
161 bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
165 /* Mark the statement defining operand OP as necessary. */
167 static inline void
168 mark_operand_necessary (tree op)
170 gimple stmt;
171 int ver;
173 gcc_assert (op);
175 ver = SSA_NAME_VERSION (op);
176 if (bitmap_bit_p (processed, ver))
178 stmt = SSA_NAME_DEF_STMT (op);
179 gcc_assert (gimple_nop_p (stmt)
180 || gimple_plf (stmt, STMT_NECESSARY));
181 return;
183 bitmap_set_bit (processed, ver);
185 stmt = SSA_NAME_DEF_STMT (op);
186 gcc_assert (stmt);
188 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
189 return;
191 if (dump_file && (dump_flags & TDF_DETAILS))
193 fprintf (dump_file, "marking necessary through ");
194 print_generic_expr (dump_file, op, 0);
195 fprintf (dump_file, " stmt ");
196 print_gimple_stmt (dump_file, stmt, 0, 0);
199 gimple_set_plf (stmt, STMT_NECESSARY, true);
200 if (bb_contains_live_stmts)
201 bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
202 worklist.safe_push (stmt);
206 /* Mark STMT as necessary if it obviously is. Add it to the worklist if
207 it can make other statements necessary.
209 If AGGRESSIVE is false, control statements are conservatively marked as
210 necessary. */
212 static void
213 mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
215 /* With non-call exceptions, we have to assume that all statements could
216 throw. If a statement could throw, it can be deemed necessary. */
217 if (cfun->can_throw_non_call_exceptions
218 && !cfun->can_delete_dead_exceptions
219 && stmt_could_throw_p (stmt))
221 mark_stmt_necessary (stmt, true);
222 return;
225 /* Statements that are implicitly live. Most function calls, asm
226 and return statements are required. Labels and GIMPLE_BIND nodes
227 are kept because they are control flow, and we have no way of
228 knowing whether they can be removed. DCE can eliminate all the
229 other statements in a block, and CFG can then remove the block
230 and labels. */
231 switch (gimple_code (stmt))
233 case GIMPLE_PREDICT:
234 case GIMPLE_LABEL:
235 mark_stmt_necessary (stmt, false);
236 return;
238 case GIMPLE_ASM:
239 case GIMPLE_RESX:
240 case GIMPLE_RETURN:
241 mark_stmt_necessary (stmt, true);
242 return;
244 case GIMPLE_CALL:
246 tree callee = gimple_call_fndecl (stmt);
247 if (callee != NULL_TREE
248 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
249 switch (DECL_FUNCTION_CODE (callee))
251 case BUILT_IN_MALLOC:
252 case BUILT_IN_ALIGNED_ALLOC:
253 case BUILT_IN_CALLOC:
254 case BUILT_IN_ALLOCA:
255 case BUILT_IN_ALLOCA_WITH_ALIGN:
256 return;
258 default:;
260 /* Most, but not all function calls are required. Function calls that
261 produce no result and have no side effects (i.e. const pure
262 functions) are unnecessary. */
263 if (gimple_has_side_effects (stmt))
265 mark_stmt_necessary (stmt, true);
266 return;
268 if (!gimple_call_lhs (stmt))
269 return;
270 break;
273 case GIMPLE_DEBUG:
274 /* Debug temps without a value are not useful. ??? If we could
275 easily locate the debug temp bind stmt for a use thereof,
276 would could refrain from marking all debug temps here, and
277 mark them only if they're used. */
278 if (!gimple_debug_bind_p (stmt)
279 || gimple_debug_bind_has_value_p (stmt)
280 || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
281 mark_stmt_necessary (stmt, false);
282 return;
284 case GIMPLE_GOTO:
285 gcc_assert (!simple_goto_p (stmt));
286 mark_stmt_necessary (stmt, true);
287 return;
289 case GIMPLE_COND:
290 gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
291 /* Fall through. */
293 case GIMPLE_SWITCH:
294 if (! aggressive)
295 mark_stmt_necessary (stmt, true);
296 break;
298 case GIMPLE_ASSIGN:
299 if (gimple_clobber_p (stmt))
300 return;
301 break;
303 default:
304 break;
307 /* If the statement has volatile operands, it needs to be preserved.
308 Same for statements that can alter control flow in unpredictable
309 ways. */
310 if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
312 mark_stmt_necessary (stmt, true);
313 return;
316 if (stmt_may_clobber_global_p (stmt))
318 mark_stmt_necessary (stmt, true);
319 return;
322 return;
326 /* Mark the last statement of BB as necessary. */
328 static void
329 mark_last_stmt_necessary (basic_block bb)
331 gimple stmt = last_stmt (bb);
333 bitmap_set_bit (last_stmt_necessary, bb->index);
334 bitmap_set_bit (bb_contains_live_stmts, bb->index);
336 /* We actually mark the statement only if it is a control statement. */
337 if (stmt && is_ctrl_stmt (stmt))
338 mark_stmt_necessary (stmt, true);
342 /* Mark control dependent edges of BB as necessary. We have to do this only
343 once for each basic block so we set the appropriate bit after we're done.
345 When IGNORE_SELF is true, ignore BB in the list of control dependences. */
347 static void
348 mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self)
350 bitmap_iterator bi;
351 unsigned edge_number;
352 bool skipped = false;
354 gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
356 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
357 return;
359 EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
360 0, edge_number, bi)
362 basic_block cd_bb = cd->get_edge (edge_number)->src;
364 if (ignore_self && cd_bb == bb)
366 skipped = true;
367 continue;
370 if (!bitmap_bit_p (last_stmt_necessary, cd_bb->index))
371 mark_last_stmt_necessary (cd_bb);
374 if (!skipped)
375 bitmap_set_bit (visited_control_parents, bb->index);
379 /* Find obviously necessary statements. These are things like most function
380 calls, and stores to file level variables.
382 If EL is NULL, control statements are conservatively marked as
383 necessary. Otherwise it contains the list of edges used by control
384 dependence analysis. */
386 static void
387 find_obviously_necessary_stmts (bool aggressive)
389 basic_block bb;
390 gimple_stmt_iterator gsi;
391 edge e;
392 gimple phi, stmt;
393 int flags;
395 FOR_EACH_BB_FN (bb, cfun)
397 /* PHI nodes are never inherently necessary. */
398 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
400 phi = gsi_stmt (gsi);
401 gimple_set_plf (phi, STMT_NECESSARY, false);
404 /* Check all statements in the block. */
405 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
407 stmt = gsi_stmt (gsi);
408 gimple_set_plf (stmt, STMT_NECESSARY, false);
409 mark_stmt_if_obviously_necessary (stmt, aggressive);
413 /* Pure and const functions are finite and thus have no infinite loops in
414 them. */
415 flags = flags_from_decl_or_type (current_function_decl);
416 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
417 return;
419 /* Prevent the empty possibly infinite loops from being removed. */
420 if (aggressive)
422 struct loop *loop;
423 scev_initialize ();
424 if (mark_irreducible_loops ())
425 FOR_EACH_BB_FN (bb, cfun)
427 edge_iterator ei;
428 FOR_EACH_EDGE (e, ei, bb->succs)
429 if ((e->flags & EDGE_DFS_BACK)
430 && (e->flags & EDGE_IRREDUCIBLE_LOOP))
432 if (dump_file)
433 fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
434 e->src->index, e->dest->index);
435 mark_control_dependent_edges_necessary (e->dest, false);
439 FOR_EACH_LOOP (loop, 0)
440 if (!finite_loop_p (loop))
442 if (dump_file)
443 fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
444 mark_control_dependent_edges_necessary (loop->latch, false);
446 scev_finalize ();
451 /* Return true if REF is based on an aliased base, otherwise false. */
453 static bool
454 ref_may_be_aliased (tree ref)
456 gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR);
457 while (handled_component_p (ref))
458 ref = TREE_OPERAND (ref, 0);
459 if (TREE_CODE (ref) == MEM_REF
460 && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
461 ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
462 return !(DECL_P (ref)
463 && !may_be_aliased (ref));
466 static bitmap visited = NULL;
467 static unsigned int longest_chain = 0;
468 static unsigned int total_chain = 0;
469 static unsigned int nr_walks = 0;
470 static bool chain_ovfl = false;
472 /* Worker for the walker that marks reaching definitions of REF,
473 which is based on a non-aliased decl, necessary. It returns
474 true whenever the defining statement of the current VDEF is
475 a kill for REF, as no dominating may-defs are necessary for REF
476 anymore. DATA points to the basic-block that contains the
477 stmt that refers to REF. */
479 static bool
480 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
482 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
484 /* All stmts we visit are necessary. */
485 mark_operand_necessary (vdef);
487 /* If the stmt lhs kills ref, then we can stop walking. */
488 if (gimple_has_lhs (def_stmt)
489 && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
490 /* The assignment is not necessarily carried out if it can throw
491 and we can catch it in the current function where we could inspect
492 the previous value.
493 ??? We only need to care about the RHS throwing. For aggregate
494 assignments or similar calls and non-call exceptions the LHS
495 might throw as well. */
496 && !stmt_can_throw_internal (def_stmt))
498 tree base, lhs = gimple_get_lhs (def_stmt);
499 HOST_WIDE_INT size, offset, max_size;
500 ao_ref_base (ref);
501 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
502 /* We can get MEM[symbol: sZ, index: D.8862_1] here,
503 so base == refd->base does not always hold. */
504 if (base == ref->base)
506 /* For a must-alias check we need to be able to constrain
507 the accesses properly. */
508 if (size != -1 && size == max_size
509 && ref->max_size != -1)
511 if (offset <= ref->offset
512 && offset + size >= ref->offset + ref->max_size)
513 return true;
515 /* Or they need to be exactly the same. */
516 else if (ref->ref
517 /* Make sure there is no induction variable involved
518 in the references (gcc.c-torture/execute/pr42142.c).
519 The simplest way is to check if the kill dominates
520 the use. */
521 /* But when both are in the same block we cannot
522 easily tell whether we came from a backedge
523 unless we decide to compute stmt UIDs
524 (see PR58246). */
525 && (basic_block) data != gimple_bb (def_stmt)
526 && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
527 gimple_bb (def_stmt))
528 && operand_equal_p (ref->ref, lhs, 0))
529 return true;
533 /* Otherwise keep walking. */
534 return false;
537 static void
538 mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
540 unsigned int chain;
541 ao_ref refd;
542 gcc_assert (!chain_ovfl);
543 ao_ref_init (&refd, ref);
544 chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
545 mark_aliased_reaching_defs_necessary_1,
546 gimple_bb (stmt), NULL);
547 if (chain > longest_chain)
548 longest_chain = chain;
549 total_chain += chain;
550 nr_walks++;
553 /* Worker for the walker that marks reaching definitions of REF, which
554 is not based on a non-aliased decl. For simplicity we need to end
555 up marking all may-defs necessary that are not based on a non-aliased
556 decl. The only job of this walker is to skip may-defs based on
557 a non-aliased decl. */
559 static bool
560 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
561 tree vdef, void *data ATTRIBUTE_UNUSED)
563 gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
565 /* We have to skip already visited (and thus necessary) statements
566 to make the chaining work after we dropped back to simple mode. */
567 if (chain_ovfl
568 && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef)))
570 gcc_assert (gimple_nop_p (def_stmt)
571 || gimple_plf (def_stmt, STMT_NECESSARY));
572 return false;
575 /* We want to skip stores to non-aliased variables. */
576 if (!chain_ovfl
577 && gimple_assign_single_p (def_stmt))
579 tree lhs = gimple_assign_lhs (def_stmt);
580 if (!ref_may_be_aliased (lhs))
581 return false;
584 /* We want to skip statments that do not constitute stores but have
585 a virtual definition. */
586 if (is_gimple_call (def_stmt))
588 tree callee = gimple_call_fndecl (def_stmt);
589 if (callee != NULL_TREE
590 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
591 switch (DECL_FUNCTION_CODE (callee))
593 case BUILT_IN_MALLOC:
594 case BUILT_IN_ALIGNED_ALLOC:
595 case BUILT_IN_CALLOC:
596 case BUILT_IN_ALLOCA:
597 case BUILT_IN_ALLOCA_WITH_ALIGN:
598 case BUILT_IN_FREE:
599 return false;
601 default:;
605 mark_operand_necessary (vdef);
607 return false;
610 static void
611 mark_all_reaching_defs_necessary (gimple stmt)
613 walk_aliased_vdefs (NULL, gimple_vuse (stmt),
614 mark_all_reaching_defs_necessary_1, NULL, &visited);
617 /* Return true for PHI nodes with one or identical arguments
618 can be removed. */
619 static bool
620 degenerate_phi_p (gimple phi)
622 unsigned int i;
623 tree op = gimple_phi_arg_def (phi, 0);
624 for (i = 1; i < gimple_phi_num_args (phi); i++)
625 if (gimple_phi_arg_def (phi, i) != op)
626 return false;
627 return true;
630 /* Propagate necessity using the operands of necessary statements.
631 Process the uses on each statement in the worklist, and add all
632 feeding statements which contribute to the calculation of this
633 value to the worklist.
635 In conservative mode, EL is NULL. */
637 static void
638 propagate_necessity (bool aggressive)
640 gimple stmt;
642 if (dump_file && (dump_flags & TDF_DETAILS))
643 fprintf (dump_file, "\nProcessing worklist:\n");
645 while (worklist.length () > 0)
647 /* Take STMT from worklist. */
648 stmt = worklist.pop ();
650 if (dump_file && (dump_flags & TDF_DETAILS))
652 fprintf (dump_file, "processing: ");
653 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
654 fprintf (dump_file, "\n");
657 if (aggressive)
659 /* Mark the last statement of the basic blocks on which the block
660 containing STMT is control dependent, but only if we haven't
661 already done so. */
662 basic_block bb = gimple_bb (stmt);
663 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
664 && !bitmap_bit_p (visited_control_parents, bb->index))
665 mark_control_dependent_edges_necessary (bb, false);
668 if (gimple_code (stmt) == GIMPLE_PHI
669 /* We do not process virtual PHI nodes nor do we track their
670 necessity. */
671 && !virtual_operand_p (gimple_phi_result (stmt)))
673 /* PHI nodes are somewhat special in that each PHI alternative has
674 data and control dependencies. All the statements feeding the
675 PHI node's arguments are always necessary. In aggressive mode,
676 we also consider the control dependent edges leading to the
677 predecessor block associated with each PHI alternative as
678 necessary. */
679 gphi *phi = as_a <gphi *> (stmt);
680 size_t k;
682 for (k = 0; k < gimple_phi_num_args (stmt); k++)
684 tree arg = PHI_ARG_DEF (stmt, k);
685 if (TREE_CODE (arg) == SSA_NAME)
686 mark_operand_necessary (arg);
689 /* For PHI operands it matters from where the control flow arrives
690 to the BB. Consider the following example:
692 a=exp1;
693 b=exp2;
694 if (test)
696 else
698 c=PHI(a,b)
700 We need to mark control dependence of the empty basic blocks, since they
701 contains computation of PHI operands.
703 Doing so is too restrictive in the case the predecestor block is in
704 the loop. Consider:
706 if (b)
708 int i;
709 for (i = 0; i<1000; ++i)
711 j = 0;
713 return j;
715 There is PHI for J in the BB containing return statement.
716 In this case the control dependence of predecestor block (that is
717 within the empty loop) also contains the block determining number
718 of iterations of the block that would prevent removing of empty
719 loop in this case.
721 This scenario can be avoided by splitting critical edges.
722 To save the critical edge splitting pass we identify how the control
723 dependence would look like if the edge was split.
725 Consider the modified CFG created from current CFG by splitting
726 edge B->C. In the postdominance tree of modified CFG, C' is
727 always child of C. There are two cases how chlids of C' can look
728 like:
730 1) C' is leaf
732 In this case the only basic block C' is control dependent on is B.
734 2) C' has single child that is B
736 In this case control dependence of C' is same as control
737 dependence of B in original CFG except for block B itself.
738 (since C' postdominate B in modified CFG)
740 Now how to decide what case happens? There are two basic options:
742 a) C postdominate B. Then C immediately postdominate B and
743 case 2 happens iff there is no other way from B to C except
744 the edge B->C.
746 There is other way from B to C iff there is succesor of B that
747 is not postdominated by B. Testing this condition is somewhat
748 expensive, because we need to iterate all succesors of B.
749 We are safe to assume that this does not happen: we will mark B
750 as needed when processing the other path from B to C that is
751 conrol dependent on B and marking control dependencies of B
752 itself is harmless because they will be processed anyway after
753 processing control statement in B.
755 b) C does not postdominate B. Always case 1 happens since there is
756 path from C to exit that does not go through B and thus also C'. */
758 if (aggressive && !degenerate_phi_p (stmt))
760 for (k = 0; k < gimple_phi_num_args (stmt); k++)
762 basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src;
764 if (gimple_bb (stmt)
765 != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
767 if (!bitmap_bit_p (last_stmt_necessary, arg_bb->index))
768 mark_last_stmt_necessary (arg_bb);
770 else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
771 && !bitmap_bit_p (visited_control_parents,
772 arg_bb->index))
773 mark_control_dependent_edges_necessary (arg_bb, true);
777 else
779 /* Propagate through the operands. Examine all the USE, VUSE and
780 VDEF operands in this statement. Mark all the statements
781 which feed this statement's uses as necessary. */
782 ssa_op_iter iter;
783 tree use;
785 /* If this is a call to free which is directly fed by an
786 allocation function do not mark that necessary through
787 processing the argument. */
788 if (gimple_call_builtin_p (stmt, BUILT_IN_FREE))
790 tree ptr = gimple_call_arg (stmt, 0);
791 gimple def_stmt;
792 tree def_callee;
793 /* If the pointer we free is defined by an allocation
794 function do not add the call to the worklist. */
795 if (TREE_CODE (ptr) == SSA_NAME
796 && is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr))
797 && (def_callee = gimple_call_fndecl (def_stmt))
798 && DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL
799 && (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_ALIGNED_ALLOC
800 || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC
801 || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC))
803 gimple bounds_def_stmt;
804 tree bounds;
806 /* For instrumented calls we should also check used
807 bounds are returned by the same allocation call. */
808 if (!gimple_call_with_bounds_p (stmt)
809 || ((bounds = gimple_call_arg (stmt, 1))
810 && TREE_CODE (bounds) == SSA_NAME
811 && (bounds_def_stmt = SSA_NAME_DEF_STMT (bounds))
812 && chkp_gimple_call_builtin_p (bounds_def_stmt,
813 BUILT_IN_CHKP_BNDRET)
814 && gimple_call_arg (bounds_def_stmt, 0) == ptr))
815 continue;
819 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
820 mark_operand_necessary (use);
822 use = gimple_vuse (stmt);
823 if (!use)
824 continue;
826 /* If we dropped to simple mode make all immediately
827 reachable definitions necessary. */
828 if (chain_ovfl)
830 mark_all_reaching_defs_necessary (stmt);
831 continue;
834 /* For statements that may load from memory (have a VUSE) we
835 have to mark all reaching (may-)definitions as necessary.
836 We partition this task into two cases:
837 1) explicit loads based on decls that are not aliased
838 2) implicit loads (like calls) and explicit loads not
839 based on decls that are not aliased (like indirect
840 references or loads from globals)
841 For 1) we mark all reaching may-defs as necessary, stopping
842 at dominating kills. For 2) we want to mark all dominating
843 references necessary, but non-aliased ones which we handle
844 in 1). By keeping a global visited bitmap for references
845 we walk for 2) we avoid quadratic behavior for those. */
847 if (is_gimple_call (stmt))
849 tree callee = gimple_call_fndecl (stmt);
850 unsigned i;
852 /* Calls to functions that are merely acting as barriers
853 or that only store to memory do not make any previous
854 stores necessary. */
855 if (callee != NULL_TREE
856 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
857 && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
858 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK
859 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
860 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALIGNED_ALLOC
861 || DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC
862 || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE
863 || DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END
864 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA
865 || (DECL_FUNCTION_CODE (callee)
866 == BUILT_IN_ALLOCA_WITH_ALIGN)
867 || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE
868 || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE
869 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
870 continue;
872 /* Calls implicitly load from memory, their arguments
873 in addition may explicitly perform memory loads. */
874 mark_all_reaching_defs_necessary (stmt);
875 for (i = 0; i < gimple_call_num_args (stmt); ++i)
877 tree arg = gimple_call_arg (stmt, i);
878 if (TREE_CODE (arg) == SSA_NAME
879 || is_gimple_min_invariant (arg))
880 continue;
881 if (TREE_CODE (arg) == WITH_SIZE_EXPR)
882 arg = TREE_OPERAND (arg, 0);
883 if (!ref_may_be_aliased (arg))
884 mark_aliased_reaching_defs_necessary (stmt, arg);
887 else if (gimple_assign_single_p (stmt))
889 tree rhs;
890 /* If this is a load mark things necessary. */
891 rhs = gimple_assign_rhs1 (stmt);
892 if (TREE_CODE (rhs) != SSA_NAME
893 && !is_gimple_min_invariant (rhs)
894 && TREE_CODE (rhs) != CONSTRUCTOR)
896 if (!ref_may_be_aliased (rhs))
897 mark_aliased_reaching_defs_necessary (stmt, rhs);
898 else
899 mark_all_reaching_defs_necessary (stmt);
902 else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
904 tree rhs = gimple_return_retval (return_stmt);
905 /* A return statement may perform a load. */
906 if (rhs
907 && TREE_CODE (rhs) != SSA_NAME
908 && !is_gimple_min_invariant (rhs)
909 && TREE_CODE (rhs) != CONSTRUCTOR)
911 if (!ref_may_be_aliased (rhs))
912 mark_aliased_reaching_defs_necessary (stmt, rhs);
913 else
914 mark_all_reaching_defs_necessary (stmt);
917 else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt))
919 unsigned i;
920 mark_all_reaching_defs_necessary (stmt);
921 /* Inputs may perform loads. */
922 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
924 tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
925 if (TREE_CODE (op) != SSA_NAME
926 && !is_gimple_min_invariant (op)
927 && TREE_CODE (op) != CONSTRUCTOR
928 && !ref_may_be_aliased (op))
929 mark_aliased_reaching_defs_necessary (stmt, op);
932 else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
934 /* The beginning of a transaction is a memory barrier. */
935 /* ??? If we were really cool, we'd only be a barrier
936 for the memories touched within the transaction. */
937 mark_all_reaching_defs_necessary (stmt);
939 else
940 gcc_unreachable ();
942 /* If we over-used our alias oracle budget drop to simple
943 mode. The cost metric allows quadratic behavior
944 (number of uses times number of may-defs queries) up to
945 a constant maximal number of queries and after that falls back to
946 super-linear complexity. */
947 if (/* Constant but quadratic for small functions. */
948 total_chain > 128 * 128
949 /* Linear in the number of may-defs. */
950 && total_chain > 32 * longest_chain
951 /* Linear in the number of uses. */
952 && total_chain > nr_walks * 32)
954 chain_ovfl = true;
955 if (visited)
956 bitmap_clear (visited);
962 /* Remove dead PHI nodes from block BB. */
964 static bool
965 remove_dead_phis (basic_block bb)
967 bool something_changed = false;
968 gphi *phi;
969 gphi_iterator gsi;
971 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
973 stats.total_phis++;
974 phi = gsi.phi ();
976 /* We do not track necessity of virtual PHI nodes. Instead do
977 very simple dead PHI removal here. */
978 if (virtual_operand_p (gimple_phi_result (phi)))
980 /* Virtual PHI nodes with one or identical arguments
981 can be removed. */
982 if (degenerate_phi_p (phi))
984 tree vdef = gimple_phi_result (phi);
985 tree vuse = gimple_phi_arg_def (phi, 0);
987 use_operand_p use_p;
988 imm_use_iterator iter;
989 gimple use_stmt;
990 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
991 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
992 SET_USE (use_p, vuse);
993 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
994 && TREE_CODE (vuse) == SSA_NAME)
995 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
997 else
998 gimple_set_plf (phi, STMT_NECESSARY, true);
1001 if (!gimple_plf (phi, STMT_NECESSARY))
1003 something_changed = true;
1004 if (dump_file && (dump_flags & TDF_DETAILS))
1006 fprintf (dump_file, "Deleting : ");
1007 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1008 fprintf (dump_file, "\n");
1011 remove_phi_node (&gsi, true);
1012 stats.removed_phis++;
1013 continue;
1016 gsi_next (&gsi);
1018 return something_changed;
1021 /* Forward edge E to respective POST_DOM_BB and update PHIs. */
1023 static edge
1024 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
1026 gphi_iterator gsi;
1027 edge e2 = NULL;
1028 edge_iterator ei;
1030 if (dump_file && (dump_flags & TDF_DETAILS))
1031 fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
1032 e->dest->index, post_dom_bb->index);
1034 e2 = redirect_edge_and_branch (e, post_dom_bb);
1035 cfg_altered = true;
1037 /* If edge was already around, no updating is necessary. */
1038 if (e2 != e)
1039 return e2;
1041 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
1043 /* We are sure that for every live PHI we are seeing control dependent BB.
1044 This means that we can pick any edge to duplicate PHI args from. */
1045 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
1046 if (e2 != e)
1047 break;
1048 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
1050 gphi *phi = gsi.phi ();
1051 tree op;
1052 source_location locus;
1054 /* PHIs for virtuals have no control dependency relation on them.
1055 We are lost here and must force renaming of the symbol. */
1056 if (virtual_operand_p (gimple_phi_result (phi)))
1058 mark_virtual_phi_result_for_renaming (phi);
1059 remove_phi_node (&gsi, true);
1060 continue;
1063 /* Dead PHI do not imply control dependency. */
1064 if (!gimple_plf (phi, STMT_NECESSARY))
1066 gsi_next (&gsi);
1067 continue;
1070 op = gimple_phi_arg_def (phi, e2->dest_idx);
1071 locus = gimple_phi_arg_location (phi, e2->dest_idx);
1072 add_phi_arg (phi, op, e, locus);
1073 /* The resulting PHI if not dead can only be degenerate. */
1074 gcc_assert (degenerate_phi_p (phi));
1075 gsi_next (&gsi);
1078 return e;
1081 /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1082 containing I so that we don't have to look it up. */
1084 static void
1085 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
1087 gimple stmt = gsi_stmt (*i);
1089 if (dump_file && (dump_flags & TDF_DETAILS))
1091 fprintf (dump_file, "Deleting : ");
1092 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1093 fprintf (dump_file, "\n");
1096 stats.removed++;
1098 /* If we have determined that a conditional branch statement contributes
1099 nothing to the program, then we not only remove it, but we also change
1100 the flow graph so that the current block will simply fall-thru to its
1101 immediate post-dominator. The blocks we are circumventing will be
1102 removed by cleanup_tree_cfg if this change in the flow graph makes them
1103 unreachable. */
1104 if (is_ctrl_stmt (stmt))
1106 basic_block post_dom_bb;
1107 edge e, e2;
1108 edge_iterator ei;
1110 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
1112 e = find_edge (bb, post_dom_bb);
1114 /* If edge is already there, try to use it. This avoids need to update
1115 PHI nodes. Also watch for cases where post dominator does not exists
1116 or is exit block. These can happen for infinite loops as we create
1117 fake edges in the dominator tree. */
1118 if (e)
1120 else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1121 e = EDGE_SUCC (bb, 0);
1122 else
1123 e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1124 gcc_assert (e);
1125 e->probability = REG_BR_PROB_BASE;
1126 e->count = bb->count;
1128 /* The edge is no longer associated with a conditional, so it does
1129 not have TRUE/FALSE flags. */
1130 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1132 /* The lone outgoing edge from BB will be a fallthru edge. */
1133 e->flags |= EDGE_FALLTHRU;
1135 /* Remove the remaining outgoing edges. */
1136 for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1137 if (e != e2)
1139 cfg_altered = true;
1140 /* If we made a BB unconditionally exit a loop then this
1141 transform alters the set of BBs in the loop. Schedule
1142 a fixup. */
1143 if (loop_exit_edge_p (bb->loop_father, e))
1144 loops_state_set (LOOPS_NEED_FIXUP);
1145 remove_edge (e2);
1147 else
1148 ei_next (&ei);
1151 /* If this is a store into a variable that is being optimized away,
1152 add a debug bind stmt if possible. */
1153 if (MAY_HAVE_DEBUG_STMTS
1154 && gimple_assign_single_p (stmt)
1155 && is_gimple_val (gimple_assign_rhs1 (stmt)))
1157 tree lhs = gimple_assign_lhs (stmt);
1158 if ((TREE_CODE (lhs) == VAR_DECL || TREE_CODE (lhs) == PARM_DECL)
1159 && !DECL_IGNORED_P (lhs)
1160 && is_gimple_reg_type (TREE_TYPE (lhs))
1161 && !is_global_var (lhs)
1162 && !DECL_HAS_VALUE_EXPR_P (lhs))
1164 tree rhs = gimple_assign_rhs1 (stmt);
1165 gdebug *note
1166 = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
1167 gsi_insert_after (i, note, GSI_SAME_STMT);
1171 unlink_stmt_vdef (stmt);
1172 gsi_remove (i, true);
1173 release_defs (stmt);
1176 /* Helper for maybe_optimize_arith_overflow. Find in *TP if there are any
1177 uses of data (SSA_NAME) other than REALPART_EXPR referencing it. */
1179 static tree
1180 find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data)
1182 if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR)
1183 *walk_subtrees = 0;
1184 if (*tp == (tree) data)
1185 return *tp;
1186 return NULL_TREE;
1189 /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used,
1190 but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls
1191 into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug
1192 uses. */
1194 static void
1195 maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi,
1196 enum tree_code subcode)
1198 gimple stmt = gsi_stmt (*gsi);
1199 tree lhs = gimple_call_lhs (stmt);
1201 if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME)
1202 return;
1204 imm_use_iterator imm_iter;
1205 use_operand_p use_p;
1206 bool has_debug_uses = false;
1207 bool has_realpart_uses = false;
1208 bool has_other_uses = false;
1209 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1211 gimple use_stmt = USE_STMT (use_p);
1212 if (is_gimple_debug (use_stmt))
1213 has_debug_uses = true;
1214 else if (is_gimple_assign (use_stmt)
1215 && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR
1216 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs)
1217 has_realpart_uses = true;
1218 else
1220 has_other_uses = true;
1221 break;
1225 if (!has_realpart_uses || has_other_uses)
1226 return;
1228 tree arg0 = gimple_call_arg (stmt, 0);
1229 tree arg1 = gimple_call_arg (stmt, 1);
1230 location_t loc = gimple_location (stmt);
1231 tree type = TREE_TYPE (TREE_TYPE (lhs));
1232 tree utype = type;
1233 if (!TYPE_UNSIGNED (type))
1234 utype = build_nonstandard_integer_type (TYPE_PRECISION (type), 1);
1235 tree result = fold_build2_loc (loc, subcode, utype,
1236 fold_convert_loc (loc, utype, arg0),
1237 fold_convert_loc (loc, utype, arg1));
1238 result = fold_convert_loc (loc, type, result);
1240 if (has_debug_uses)
1242 gimple use_stmt;
1243 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
1245 if (!gimple_debug_bind_p (use_stmt))
1246 continue;
1247 tree v = gimple_debug_bind_get_value (use_stmt);
1248 if (walk_tree (&v, find_non_realpart_uses, lhs, NULL))
1250 gimple_debug_bind_reset_value (use_stmt);
1251 update_stmt (use_stmt);
1256 if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result))
1257 result = drop_tree_overflow (result);
1258 tree overflow = build_zero_cst (type);
1259 tree ctype = build_complex_type (type);
1260 if (TREE_CODE (result) == INTEGER_CST)
1261 result = build_complex (ctype, result, overflow);
1262 else
1263 result = build2_loc (gimple_location (stmt), COMPLEX_EXPR,
1264 ctype, result, overflow);
1266 if (dump_file && (dump_flags & TDF_DETAILS))
1268 fprintf (dump_file, "Transforming call: ");
1269 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1270 fprintf (dump_file, "because the overflow result is never used into: ");
1271 print_generic_stmt (dump_file, result, TDF_SLIM);
1272 fprintf (dump_file, "\n");
1275 if (!update_call_from_tree (gsi, result))
1276 gimplify_and_update_call_from_tree (gsi, result);
1279 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1280 contributes nothing to the program, and can be deleted. */
1282 static bool
1283 eliminate_unnecessary_stmts (void)
1285 bool something_changed = false;
1286 basic_block bb;
1287 gimple_stmt_iterator gsi, psi;
1288 gimple stmt;
1289 tree call;
1290 vec<basic_block> h;
1292 if (dump_file && (dump_flags & TDF_DETAILS))
1293 fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1295 clear_special_calls ();
1297 /* Walking basic blocks and statements in reverse order avoids
1298 releasing SSA names before any other DEFs that refer to them are
1299 released. This helps avoid loss of debug information, as we get
1300 a chance to propagate all RHSs of removed SSAs into debug uses,
1301 rather than only the latest ones. E.g., consider:
1303 x_3 = y_1 + z_2;
1304 a_5 = x_3 - b_4;
1305 # DEBUG a => a_5
1307 If we were to release x_3 before a_5, when we reached a_5 and
1308 tried to substitute it into the debug stmt, we'd see x_3 there,
1309 but x_3's DEF, type, etc would have already been disconnected.
1310 By going backwards, the debug stmt first changes to:
1312 # DEBUG a => x_3 - b_4
1314 and then to:
1316 # DEBUG a => y_1 + z_2 - b_4
1318 as desired. */
1319 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1320 h = get_all_dominated_blocks (CDI_DOMINATORS,
1321 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1323 while (h.length ())
1325 bb = h.pop ();
1327 /* Remove dead statements. */
1328 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
1330 stmt = gsi_stmt (gsi);
1332 psi = gsi;
1333 gsi_prev (&psi);
1335 stats.total++;
1337 /* We can mark a call to free as not necessary if the
1338 defining statement of its argument is not necessary
1339 (and thus is getting removed). */
1340 if (gimple_plf (stmt, STMT_NECESSARY)
1341 && gimple_call_builtin_p (stmt, BUILT_IN_FREE))
1343 tree ptr = gimple_call_arg (stmt, 0);
1344 if (TREE_CODE (ptr) == SSA_NAME)
1346 gimple def_stmt = SSA_NAME_DEF_STMT (ptr);
1347 if (!gimple_nop_p (def_stmt)
1348 && !gimple_plf (def_stmt, STMT_NECESSARY))
1349 gimple_set_plf (stmt, STMT_NECESSARY, false);
1351 /* We did not propagate necessity for free calls fed
1352 by allocation function to allow unnecessary
1353 alloc-free sequence elimination. For instrumented
1354 calls it also means we did not mark bounds producer
1355 as necessary and it is time to do it in case free
1356 call is not removed. */
1357 if (gimple_call_with_bounds_p (stmt))
1359 gimple bounds_def_stmt;
1360 tree bounds = gimple_call_arg (stmt, 1);
1361 gcc_assert (TREE_CODE (bounds) == SSA_NAME);
1362 bounds_def_stmt = SSA_NAME_DEF_STMT (bounds);
1363 if (bounds_def_stmt
1364 && !gimple_plf (bounds_def_stmt, STMT_NECESSARY))
1365 gimple_set_plf (bounds_def_stmt, STMT_NECESSARY,
1366 gimple_plf (stmt, STMT_NECESSARY));
1370 /* If GSI is not necessary then remove it. */
1371 if (!gimple_plf (stmt, STMT_NECESSARY))
1373 /* Keep clobbers that we can keep live live. */
1374 if (gimple_clobber_p (stmt))
1376 ssa_op_iter iter;
1377 use_operand_p use_p;
1378 bool dead = false;
1379 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1381 tree name = USE_FROM_PTR (use_p);
1382 if (!SSA_NAME_IS_DEFAULT_DEF (name)
1383 && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)))
1385 dead = true;
1386 break;
1389 if (!dead)
1390 continue;
1392 if (!is_gimple_debug (stmt))
1393 something_changed = true;
1394 remove_dead_stmt (&gsi, bb);
1396 else if (is_gimple_call (stmt))
1398 tree name = gimple_call_lhs (stmt);
1400 notice_special_calls (as_a <gcall *> (stmt));
1402 /* When LHS of var = call (); is dead, simplify it into
1403 call (); saving one operand. */
1404 if (name
1405 && TREE_CODE (name) == SSA_NAME
1406 && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))
1407 /* Avoid doing so for allocation calls which we
1408 did not mark as necessary, it will confuse the
1409 special logic we apply to malloc/free pair removal. */
1410 && (!(call = gimple_call_fndecl (stmt))
1411 || DECL_BUILT_IN_CLASS (call) != BUILT_IN_NORMAL
1412 || (DECL_FUNCTION_CODE (call) != BUILT_IN_ALIGNED_ALLOC
1413 && DECL_FUNCTION_CODE (call) != BUILT_IN_MALLOC
1414 && DECL_FUNCTION_CODE (call) != BUILT_IN_CALLOC
1415 && DECL_FUNCTION_CODE (call) != BUILT_IN_ALLOCA
1416 && (DECL_FUNCTION_CODE (call)
1417 != BUILT_IN_ALLOCA_WITH_ALIGN)))
1418 /* Avoid doing so for bndret calls for the same reason. */
1419 && !chkp_gimple_call_builtin_p (stmt, BUILT_IN_CHKP_BNDRET))
1421 something_changed = true;
1422 if (dump_file && (dump_flags & TDF_DETAILS))
1424 fprintf (dump_file, "Deleting LHS of call: ");
1425 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1426 fprintf (dump_file, "\n");
1429 gimple_call_set_lhs (stmt, NULL_TREE);
1430 maybe_clean_or_replace_eh_stmt (stmt, stmt);
1431 update_stmt (stmt);
1432 release_ssa_name (name);
1434 /* GOMP_SIMD_LANE without lhs is not needed. */
1435 if (gimple_call_internal_p (stmt)
1436 && gimple_call_internal_fn (stmt) == IFN_GOMP_SIMD_LANE)
1437 remove_dead_stmt (&gsi, bb);
1439 else if (gimple_call_internal_p (stmt))
1440 switch (gimple_call_internal_fn (stmt))
1442 case IFN_ADD_OVERFLOW:
1443 maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
1444 break;
1445 case IFN_SUB_OVERFLOW:
1446 maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
1447 break;
1448 case IFN_MUL_OVERFLOW:
1449 maybe_optimize_arith_overflow (&gsi, MULT_EXPR);
1450 break;
1451 default:
1452 break;
1458 h.release ();
1460 /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1461 rendered some PHI nodes unreachable while they are still in use.
1462 Mark them for renaming. */
1463 if (cfg_altered)
1465 basic_block prev_bb;
1467 find_unreachable_blocks ();
1469 /* Delete all unreachable basic blocks in reverse dominator order. */
1470 for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
1471 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb)
1473 prev_bb = bb->prev_bb;
1475 if (!bitmap_bit_p (bb_contains_live_stmts, bb->index)
1476 || !(bb->flags & BB_REACHABLE))
1478 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1479 gsi_next (&gsi))
1480 if (virtual_operand_p (gimple_phi_result (gsi.phi ())))
1482 bool found = false;
1483 imm_use_iterator iter;
1485 FOR_EACH_IMM_USE_STMT (stmt, iter,
1486 gimple_phi_result (gsi.phi ()))
1488 if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1489 continue;
1490 if (gimple_code (stmt) == GIMPLE_PHI
1491 || gimple_plf (stmt, STMT_NECESSARY))
1493 found = true;
1494 BREAK_FROM_IMM_USE_STMT (iter);
1497 if (found)
1498 mark_virtual_phi_result_for_renaming (gsi.phi ());
1501 if (!(bb->flags & BB_REACHABLE))
1503 /* Speed up the removal of blocks that don't
1504 dominate others. Walking backwards, this should
1505 be the common case. ??? Do we need to recompute
1506 dominators because of cfg_altered? */
1507 if (!MAY_HAVE_DEBUG_STMTS
1508 || !first_dom_son (CDI_DOMINATORS, bb))
1509 delete_basic_block (bb);
1510 else
1512 h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1514 while (h.length ())
1516 bb = h.pop ();
1517 prev_bb = bb->prev_bb;
1518 /* Rearrangements to the CFG may have failed
1519 to update the dominators tree, so that
1520 formerly-dominated blocks are now
1521 otherwise reachable. */
1522 if (!!(bb->flags & BB_REACHABLE))
1523 continue;
1524 delete_basic_block (bb);
1527 h.release ();
1533 FOR_EACH_BB_FN (bb, cfun)
1535 /* Remove dead PHI nodes. */
1536 something_changed |= remove_dead_phis (bb);
1539 return something_changed;
1543 /* Print out removed statement statistics. */
1545 static void
1546 print_stats (void)
1548 float percg;
1550 percg = ((float) stats.removed / (float) stats.total) * 100;
1551 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1552 stats.removed, stats.total, (int) percg);
1554 if (stats.total_phis == 0)
1555 percg = 0;
1556 else
1557 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1559 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1560 stats.removed_phis, stats.total_phis, (int) percg);
1563 /* Initialization for this pass. Set up the used data structures. */
1565 static void
1566 tree_dce_init (bool aggressive)
1568 memset ((void *) &stats, 0, sizeof (stats));
1570 if (aggressive)
1572 last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun));
1573 bitmap_clear (last_stmt_necessary);
1574 bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun));
1575 bitmap_clear (bb_contains_live_stmts);
1578 processed = sbitmap_alloc (num_ssa_names + 1);
1579 bitmap_clear (processed);
1581 worklist.create (64);
1582 cfg_altered = false;
1585 /* Cleanup after this pass. */
1587 static void
1588 tree_dce_done (bool aggressive)
1590 if (aggressive)
1592 delete cd;
1593 sbitmap_free (visited_control_parents);
1594 sbitmap_free (last_stmt_necessary);
1595 sbitmap_free (bb_contains_live_stmts);
1596 bb_contains_live_stmts = NULL;
1599 sbitmap_free (processed);
1601 worklist.release ();
1604 /* Main routine to eliminate dead code.
1606 AGGRESSIVE controls the aggressiveness of the algorithm.
1607 In conservative mode, we ignore control dependence and simply declare
1608 all but the most trivially dead branches necessary. This mode is fast.
1609 In aggressive mode, control dependences are taken into account, which
1610 results in more dead code elimination, but at the cost of some time.
1612 FIXME: Aggressive mode before PRE doesn't work currently because
1613 the dominance info is not invalidated after DCE1. This is
1614 not an issue right now because we only run aggressive DCE
1615 as the last tree SSA pass, but keep this in mind when you
1616 start experimenting with pass ordering. */
1618 static unsigned int
1619 perform_tree_ssa_dce (bool aggressive)
1621 bool something_changed = 0;
1623 calculate_dominance_info (CDI_DOMINATORS);
1625 /* Preheaders are needed for SCEV to work.
1626 Simple lateches and recorded exits improve chances that loop will
1627 proved to be finite in testcases such as in loop-15.c and loop-24.c */
1628 if (aggressive)
1629 loop_optimizer_init (LOOPS_NORMAL
1630 | LOOPS_HAVE_RECORDED_EXITS);
1632 tree_dce_init (aggressive);
1634 if (aggressive)
1636 /* Compute control dependence. */
1637 calculate_dominance_info (CDI_POST_DOMINATORS);
1638 cd = new control_dependences (create_edge_list ());
1640 visited_control_parents =
1641 sbitmap_alloc (last_basic_block_for_fn (cfun));
1642 bitmap_clear (visited_control_parents);
1644 mark_dfs_back_edges ();
1647 find_obviously_necessary_stmts (aggressive);
1649 if (aggressive)
1650 loop_optimizer_finalize ();
1652 longest_chain = 0;
1653 total_chain = 0;
1654 nr_walks = 0;
1655 chain_ovfl = false;
1656 visited = BITMAP_ALLOC (NULL);
1657 propagate_necessity (aggressive);
1658 BITMAP_FREE (visited);
1660 something_changed |= eliminate_unnecessary_stmts ();
1661 something_changed |= cfg_altered;
1663 /* We do not update postdominators, so free them unconditionally. */
1664 free_dominance_info (CDI_POST_DOMINATORS);
1666 /* If we removed paths in the CFG, then we need to update
1667 dominators as well. I haven't investigated the possibility
1668 of incrementally updating dominators. */
1669 if (cfg_altered)
1670 free_dominance_info (CDI_DOMINATORS);
1672 statistics_counter_event (cfun, "Statements deleted", stats.removed);
1673 statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1675 /* Debugging dumps. */
1676 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1677 print_stats ();
1679 tree_dce_done (aggressive);
1681 if (something_changed)
1683 free_numbers_of_iterations_estimates ();
1684 if (scev_initialized_p ())
1685 scev_reset ();
1686 return TODO_update_ssa | TODO_cleanup_cfg;
1688 return 0;
1691 /* Pass entry points. */
1692 static unsigned int
1693 tree_ssa_dce (void)
1695 return perform_tree_ssa_dce (/*aggressive=*/false);
1698 static unsigned int
1699 tree_ssa_cd_dce (void)
1701 return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1704 namespace {
1706 const pass_data pass_data_dce =
1708 GIMPLE_PASS, /* type */
1709 "dce", /* name */
1710 OPTGROUP_NONE, /* optinfo_flags */
1711 TV_TREE_DCE, /* tv_id */
1712 ( PROP_cfg | PROP_ssa ), /* properties_required */
1713 0, /* properties_provided */
1714 0, /* properties_destroyed */
1715 0, /* todo_flags_start */
1716 0, /* todo_flags_finish */
1719 class pass_dce : public gimple_opt_pass
1721 public:
1722 pass_dce (gcc::context *ctxt)
1723 : gimple_opt_pass (pass_data_dce, ctxt)
1726 /* opt_pass methods: */
1727 opt_pass * clone () { return new pass_dce (m_ctxt); }
1728 virtual bool gate (function *) { return flag_tree_dce != 0; }
1729 virtual unsigned int execute (function *) { return tree_ssa_dce (); }
1731 }; // class pass_dce
1733 } // anon namespace
1735 gimple_opt_pass *
1736 make_pass_dce (gcc::context *ctxt)
1738 return new pass_dce (ctxt);
1741 namespace {
1743 const pass_data pass_data_cd_dce =
1745 GIMPLE_PASS, /* type */
1746 "cddce", /* name */
1747 OPTGROUP_NONE, /* optinfo_flags */
1748 TV_TREE_CD_DCE, /* tv_id */
1749 ( PROP_cfg | PROP_ssa ), /* properties_required */
1750 0, /* properties_provided */
1751 0, /* properties_destroyed */
1752 0, /* todo_flags_start */
1753 0, /* todo_flags_finish */
1756 class pass_cd_dce : public gimple_opt_pass
1758 public:
1759 pass_cd_dce (gcc::context *ctxt)
1760 : gimple_opt_pass (pass_data_cd_dce, ctxt)
1763 /* opt_pass methods: */
1764 opt_pass * clone () { return new pass_cd_dce (m_ctxt); }
1765 virtual bool gate (function *) { return flag_tree_dce != 0; }
1766 virtual unsigned int execute (function *) { return tree_ssa_cd_dce (); }
1768 }; // class pass_cd_dce
1770 } // anon namespace
1772 gimple_opt_pass *
1773 make_pass_cd_dce (gcc::context *ctxt)
1775 return new pass_cd_dce (ctxt);