Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 1 | //===- DCE.cpp - Code to perform dead code elimination --------------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 10 | // This file implements dead inst elimination and dead code elimination. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 11 | // |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 12 | // Dead Inst Elimination performs a single pass over the function removing |
| 13 | // instructions that are obviously dead. Dead Code Elimination is similar, but |
| 14 | // it rechecks instructions that were used by removed instructions to see if |
| 15 | // they are newly dead. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 16 | // |
| 17 | //===----------------------------------------------------------------------===// |
| 18 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 19 | #define DEBUG_TYPE "dce" |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 20 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 2ed01d8 | 2002-05-07 18:10:55 +0000 | [diff] [blame] | 21 | #include "llvm/Transforms/Utils/Local.h" |
| 22 | #include "llvm/Instruction.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 23 | #include "llvm/Pass.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 24 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 25 | #include "llvm/Support/InstIterator.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 26 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 27 | #include <set> |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 28 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 29 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 30 | STATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); |
| 31 | STATISTIC(DCEEliminated, "Number of insts removed"); |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 32 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 33 | namespace { |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 34 | //===--------------------------------------------------------------------===// |
| 35 | // DeadInstElimination pass implementation |
| 36 | // |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 37 | struct VISIBILITY_HIDDEN DeadInstElimination : public BasicBlockPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 38 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 39 | DeadInstElimination() : BasicBlockPass(intptr_t(&ID)) {} |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 40 | virtual bool runOnBasicBlock(BasicBlock &BB) { |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 41 | bool Changed = false; |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 42 | for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) |
Chris Lattner | 16da494 | 2002-05-26 20:18:18 +0000 | [diff] [blame] | 43 | if (dceInstruction(DI)) { |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 44 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 45 | ++DIEEliminated; |
| 46 | } else |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 47 | ++DI; |
| 48 | return Changed; |
| 49 | } |
| 50 | |
| 51 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | cb2610e | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 52 | AU.setPreservesCFG(); |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 53 | } |
| 54 | }; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 55 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 56 | char DeadInstElimination::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 57 | RegisterPass<DeadInstElimination> X("die", "Dead Instruction Elimination"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 58 | } |
| 59 | |
Devang Patel | 4d447f5 | 2007-01-25 23:23:25 +0000 | [diff] [blame] | 60 | Pass *llvm::createDeadInstEliminationPass() { |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 61 | return new DeadInstElimination(); |
Chris Lattner | c560f88 | 2002-01-23 05:48:24 +0000 | [diff] [blame] | 62 | } |
| 63 | |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 64 | |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 65 | namespace { |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 66 | //===--------------------------------------------------------------------===// |
| 67 | // DeadCodeElimination pass implementation |
| 68 | // |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 69 | struct DCE : public FunctionPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 70 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 71 | DCE() : FunctionPass((intptr_t)&ID) {} |
| 72 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 73 | virtual bool runOnFunction(Function &F); |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 74 | |
| 75 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | cb2610e | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 76 | AU.setPreservesCFG(); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 77 | } |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 78 | }; |
Chris Lattner | f629309 | 2002-07-23 18:06:35 +0000 | [diff] [blame] | 79 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 80 | char DCE::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 81 | RegisterPass<DCE> Y("dce", "Dead Code Elimination"); |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 82 | } |
| 83 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 84 | bool DCE::runOnFunction(Function &F) { |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 85 | // Start out with all of the instructions in the worklist... |
Chris Lattner | 6ffe551 | 2004-04-27 15:13:33 +0000 | [diff] [blame] | 86 | std::vector<Instruction*> WorkList; |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 87 | for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) |
| 88 | WorkList.push_back(&*i); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 89 | |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 90 | // Loop over the worklist finding instructions that are dead. If they are |
| 91 | // dead make them drop all of their uses, making other instructions |
| 92 | // potentially dead, and work until the worklist is empty. |
| 93 | // |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 94 | bool MadeChange = false; |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 95 | while (!WorkList.empty()) { |
| 96 | Instruction *I = WorkList.back(); |
| 97 | WorkList.pop_back(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 98 | |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 99 | if (isInstructionTriviallyDead(I)) { // If the instruction is dead. |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 100 | // Loop over all of the values that the instruction uses, if there are |
| 101 | // instructions being used, add them to the worklist, because they might |
| 102 | // go dead after this one is removed. |
| 103 | // |
Chris Lattner | 4e5f036 | 2004-04-21 22:29:37 +0000 | [diff] [blame] | 104 | for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) |
| 105 | if (Instruction *Used = dyn_cast<Instruction>(*OI)) |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 106 | WorkList.push_back(Used); |
| 107 | |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 108 | // Remove the instruction. |
| 109 | I->eraseFromParent(); |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 110 | |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 111 | // Remove the instruction from the worklist if it still exists in it. |
David Greene | 08d5fd9 | 2007-12-17 17:39:51 +0000 | [diff] [blame] | 112 | for (std::vector<Instruction*>::iterator WI = WorkList.begin(); |
| 113 | WI != WorkList.end(); ++WI) |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 114 | if (*WI == I) { |
David Greene | 08d5fd9 | 2007-12-17 17:39:51 +0000 | [diff] [blame] | 115 | WI = WorkList.erase(WI); |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 116 | --WI; |
| 117 | } |
| 118 | |
| 119 | MadeChange = true; |
| 120 | ++DCEEliminated; |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 121 | } |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 122 | } |
Chris Lattner | 9281282 | 2005-05-08 18:45:26 +0000 | [diff] [blame] | 123 | return MadeChange; |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 124 | } |
| 125 | |
Brian Gaeke | 96d4bf7 | 2004-07-27 17:43:21 +0000 | [diff] [blame] | 126 | FunctionPass *llvm::createDeadCodeEliminationPass() { |
Chris Lattner | 92deeaf | 2002-05-07 04:24:11 +0000 | [diff] [blame] | 127 | return new DCE(); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 128 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 129 | |