Chris Lattner | ea54ab9 | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 1 | //===- ADCE.cpp - Code to perform aggressive 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 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source 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 | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | ea54ab9 | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 10 | // This file implements "aggressive" dead code elimination. ADCE is DCe where |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 11 | // values are assumed to be dead until proven otherwise. This is similar to |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 12 | // SCCP, except applied to the liveness of values. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 16 | #define DEBUG_TYPE "adce" |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 18 | #include "llvm/Constants.h" |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 20 | #include "llvm/Analysis/AliasAnalysis.h" |
| 21 | #include "llvm/Analysis/PostDominators.h" |
Chris Lattner | 221d688 | 2002-02-12 21:07:25 +0000 | [diff] [blame] | 22 | #include "llvm/Support/CFG.h" |
Chris Lattner | bd1a90e | 2003-12-19 09:08:34 +0000 | [diff] [blame] | 23 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| 24 | #include "llvm/Transforms/Utils/Local.h" |
| 25 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 26 | #include "llvm/Support/Debug.h" |
| 27 | #include "llvm/ADT/DepthFirstIterator.h" |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 28 | #include "llvm/ADT/SmallVector.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 29 | #include "llvm/ADT/Statistic.h" |
| 30 | #include "llvm/ADT/STLExtras.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 31 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 32 | #include <algorithm> |
Chris Lattner | bd1a90e | 2003-12-19 09:08:34 +0000 | [diff] [blame] | 33 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 34 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 35 | STATISTIC(NumBlockRemoved, "Number of basic blocks removed"); |
| 36 | STATISTIC(NumInstRemoved , "Number of instructions removed"); |
| 37 | STATISTIC(NumCallRemoved , "Number of calls and invokes removed"); |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 38 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 39 | namespace { |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 40 | //===----------------------------------------------------------------------===// |
| 41 | // ADCE Class |
| 42 | // |
Chris Lattner | ea54ab9 | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 43 | // This class does all of the work of Aggressive Dead Code Elimination. |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 44 | // It's public interface consists of a constructor and a doADCE() method. |
| 45 | // |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 46 | class VISIBILITY_HIDDEN ADCE : public FunctionPass { |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 47 | Function *Func; // The function that we are working on |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 48 | std::vector<Instruction*> WorkList; // Instructions that just became live |
| 49 | std::set<Instruction*> LiveSet; // The set of live instructions |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 50 | |
| 51 | //===--------------------------------------------------------------------===// |
| 52 | // The public interface for this class |
| 53 | // |
| 54 | public: |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 55 | static char ID; // Pass identifcation, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 56 | ADCE() : FunctionPass((intptr_t)&ID) {} |
| 57 | |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 58 | // Execute the Aggressive Dead Code Elimination Algorithm |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 59 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 60 | virtual bool runOnFunction(Function &F) { |
| 61 | Func = &F; |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 62 | bool Changed = doADCE(); |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 63 | assert(WorkList.empty()); |
| 64 | LiveSet.clear(); |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 65 | return Changed; |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 66 | } |
| 67 | // getAnalysisUsage - We require post dominance frontiers (aka Control |
| 68 | // Dependence Graph) |
| 69 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | bd1a90e | 2003-12-19 09:08:34 +0000 | [diff] [blame] | 70 | // We require that all function nodes are unified, because otherwise code |
| 71 | // can be marked live that wouldn't necessarily be otherwise. |
| 72 | AU.addRequired<UnifyFunctionExitNodes>(); |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 73 | AU.addRequired<AliasAnalysis>(); |
Owen Anderson | a65064b | 2007-04-18 06:46:57 +0000 | [diff] [blame] | 74 | AU.addRequired<PostDominatorTree>(); |
Chris Lattner | 5f0eb8d | 2002-08-08 19:01:30 +0000 | [diff] [blame] | 75 | AU.addRequired<PostDominanceFrontier>(); |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 76 | } |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 77 | |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 78 | |
| 79 | //===--------------------------------------------------------------------===// |
| 80 | // The implementation of this class |
| 81 | // |
| 82 | private: |
Chris Lattner | ea54ab9 | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 83 | // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 84 | // true if the function was modified. |
| 85 | // |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 86 | bool doADCE(); |
| 87 | |
| 88 | void markBlockAlive(BasicBlock *BB); |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 89 | |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 90 | |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 91 | // deleteDeadInstructionsInLiveBlock - Loop over all of the instructions in |
| 92 | // the specified basic block, deleting ones that are dead according to |
| 93 | // LiveSet. |
| 94 | bool deleteDeadInstructionsInLiveBlock(BasicBlock *BB); |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 95 | |
Chris Lattner | 837e42c | 2003-06-24 23:02:45 +0000 | [diff] [blame] | 96 | TerminatorInst *convertToUnconditionalBranch(TerminatorInst *TI); |
| 97 | |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 98 | inline void markInstructionLive(Instruction *I) { |
Chris Lattner | 188839a | 2004-12-12 22:16:13 +0000 | [diff] [blame] | 99 | if (!LiveSet.insert(I).second) return; |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 100 | DOUT << "Insn Live: " << *I; |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 101 | WorkList.push_back(I); |
| 102 | } |
| 103 | |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 104 | inline void markTerminatorLive(const BasicBlock *BB) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 105 | DOUT << "Terminator Live: " << *BB->getTerminator(); |
Chris Lattner | 545a76c | 2003-09-10 20:38:14 +0000 | [diff] [blame] | 106 | markInstructionLive(const_cast<TerminatorInst*>(BB->getTerminator())); |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 107 | } |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 108 | }; |
| 109 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 110 | char ADCE::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 111 | RegisterPass<ADCE> X("adce", "Aggressive Dead Code Elimination"); |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 112 | } // End of anonymous namespace |
| 113 | |
Chris Lattner | 4b50156 | 2004-09-20 04:43:15 +0000 | [diff] [blame] | 114 | FunctionPass *llvm::createAggressiveDCEPass() { return new ADCE(); } |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 115 | |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 116 | void ADCE::markBlockAlive(BasicBlock *BB) { |
| 117 | // Mark the basic block as being newly ALIVE... and mark all branches that |
Misha Brukman | ef6a6a6 | 2003-08-21 22:14:26 +0000 | [diff] [blame] | 118 | // this block is control dependent on as being alive also... |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 119 | // |
Chris Lattner | ce6ef11 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 120 | PostDominanceFrontier &CDG = getAnalysis<PostDominanceFrontier>(); |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 121 | |
Chris Lattner | ce6ef11 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 122 | PostDominanceFrontier::const_iterator It = CDG.find(BB); |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 123 | if (It != CDG.end()) { |
Misha Brukman | ef6a6a6 | 2003-08-21 22:14:26 +0000 | [diff] [blame] | 124 | // Get the blocks that this node is control dependent on... |
Chris Lattner | ce6ef11 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 125 | const PostDominanceFrontier::DomSetType &CDB = It->second; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 126 | for (PostDominanceFrontier::DomSetType::const_iterator I = |
Chris Lattner | cfa2f8e | 2005-02-22 23:22:58 +0000 | [diff] [blame] | 127 | CDB.begin(), E = CDB.end(); I != E; ++I) |
| 128 | markTerminatorLive(*I); // Mark all their terminators as live |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 129 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 130 | |
Chris Lattner | 99c91e0 | 2003-06-24 21:49:45 +0000 | [diff] [blame] | 131 | // If this basic block is live, and it ends in an unconditional branch, then |
| 132 | // the branch is alive as well... |
| 133 | if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) |
| 134 | if (BI->isUnconditional()) |
| 135 | markTerminatorLive(BB); |
Chris Lattner | dfe81ab | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 136 | } |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 137 | |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 138 | // deleteDeadInstructionsInLiveBlock - Loop over all of the instructions in the |
| 139 | // specified basic block, deleting ones that are dead according to LiveSet. |
| 140 | bool ADCE::deleteDeadInstructionsInLiveBlock(BasicBlock *BB) { |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 141 | bool Changed = false; |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 142 | for (BasicBlock::iterator II = BB->begin(), E = --BB->end(); II != E; ) { |
| 143 | Instruction *I = II++; |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 144 | if (!LiveSet.count(I)) { // Is this instruction alive? |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 145 | if (!I->use_empty()) |
| 146 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
Chris Lattner | 1717760 | 2004-04-10 07:02:02 +0000 | [diff] [blame] | 147 | |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 148 | // Nope... remove the instruction from it's basic block... |
| 149 | if (isa<CallInst>(I)) |
| 150 | ++NumCallRemoved; |
| 151 | else |
Chris Lattner | 27c694b | 2004-04-10 07:27:48 +0000 | [diff] [blame] | 152 | ++NumInstRemoved; |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 153 | BB->getInstList().erase(I); |
| 154 | Changed = true; |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 155 | } |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 156 | } |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 157 | return Changed; |
| 158 | } |
| 159 | |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 160 | |
Chris Lattner | 837e42c | 2003-06-24 23:02:45 +0000 | [diff] [blame] | 161 | /// convertToUnconditionalBranch - Transform this conditional terminator |
| 162 | /// instruction into an unconditional branch because we don't care which of the |
| 163 | /// successors it goes to. This eliminate a use of the condition as well. |
| 164 | /// |
| 165 | TerminatorInst *ADCE::convertToUnconditionalBranch(TerminatorInst *TI) { |
| 166 | BranchInst *NB = new BranchInst(TI->getSuccessor(0), TI); |
| 167 | BasicBlock *BB = TI->getParent(); |
| 168 | |
| 169 | // Remove entries from PHI nodes to avoid confusing ourself later... |
| 170 | for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) |
| 171 | TI->getSuccessor(i)->removePredecessor(BB); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 172 | |
Chris Lattner | 837e42c | 2003-06-24 23:02:45 +0000 | [diff] [blame] | 173 | // Delete the old branch itself... |
| 174 | BB->getInstList().erase(TI); |
| 175 | return NB; |
| 176 | } |
| 177 | |
| 178 | |
Chris Lattner | ea54ab9 | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 179 | // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 180 | // true if the function was modified. |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 181 | // |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 182 | bool ADCE::doADCE() { |
| 183 | bool MadeChanges = false; |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 184 | |
Chris Lattner | a5f4103 | 2004-04-10 18:06:21 +0000 | [diff] [blame] | 185 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 186 | |
| 187 | |
| 188 | // Iterate over all invokes in the function, turning invokes into calls if |
| 189 | // they cannot throw. |
| 190 | for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) |
| 191 | if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) |
| 192 | if (Function *F = II->getCalledFunction()) |
| 193 | if (AA.onlyReadsMemory(F)) { |
| 194 | // The function cannot unwind. Convert it to a call with a branch |
| 195 | // after it to the normal destination. |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 196 | SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); |
| 197 | CallInst *NewCall = new CallInst(F, &Args[0], Args.size(), "", II); |
Chris Lattner | 6934a04 | 2007-02-11 01:23:03 +0000 | [diff] [blame] | 198 | NewCall->takeName(II); |
Chris Lattner | e437026 | 2005-05-14 12:25:32 +0000 | [diff] [blame] | 199 | NewCall->setCallingConv(II->getCallingConv()); |
Chris Lattner | a5f4103 | 2004-04-10 18:06:21 +0000 | [diff] [blame] | 200 | II->replaceAllUsesWith(NewCall); |
| 201 | new BranchInst(II->getNormalDest(), II); |
| 202 | |
| 203 | // Update PHI nodes in the unwind destination |
| 204 | II->getUnwindDest()->removePredecessor(BB); |
| 205 | BB->getInstList().erase(II); |
| 206 | |
| 207 | if (NewCall->use_empty()) { |
| 208 | BB->getInstList().erase(NewCall); |
| 209 | ++NumCallRemoved; |
| 210 | } |
| 211 | } |
| 212 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 213 | // Iterate over all of the instructions in the function, eliminating trivially |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 214 | // dead instructions, and marking instructions live that are known to be |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 215 | // needed. Perform the walk in depth first order so that we avoid marking any |
| 216 | // instructions live in basic blocks that are unreachable. These blocks will |
| 217 | // be eliminated later, along with the instructions inside. |
| 218 | // |
Chris Lattner | b9110c6 | 2004-05-04 17:00:46 +0000 | [diff] [blame] | 219 | std::set<BasicBlock*> ReachableBBs; |
| 220 | for (df_ext_iterator<BasicBlock*> |
| 221 | BBI = df_ext_begin(&Func->front(), ReachableBBs), |
| 222 | BBE = df_ext_end(&Func->front(), ReachableBBs); BBI != BBE; ++BBI) { |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 223 | BasicBlock *BB = *BBI; |
| 224 | for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 225 | Instruction *I = II++; |
| 226 | if (CallInst *CI = dyn_cast<CallInst>(I)) { |
| 227 | Function *F = CI->getCalledFunction(); |
Chris Lattner | a5f4103 | 2004-04-10 18:06:21 +0000 | [diff] [blame] | 228 | if (F && AA.onlyReadsMemory(F)) { |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 229 | if (CI->use_empty()) { |
| 230 | BB->getInstList().erase(CI); |
| 231 | ++NumCallRemoved; |
| 232 | } |
| 233 | } else { |
| 234 | markInstructionLive(I); |
| 235 | } |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 236 | } else if (I->mayWriteToMemory() || isa<ReturnInst>(I) || |
Chris Lattner | c7ff6c8 | 2004-10-17 23:45:06 +0000 | [diff] [blame] | 237 | isa<UnwindInst>(I) || isa<UnreachableInst>(I)) { |
| 238 | // FIXME: Unreachable instructions should not be marked intrinsically |
| 239 | // live here. |
Jeff Cohen | 9d80930 | 2005-04-23 21:38:35 +0000 | [diff] [blame] | 240 | markInstructionLive(I); |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 241 | } else if (isInstructionTriviallyDead(I)) { |
Chris Lattner | ea54ab9 | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 242 | // Remove the instruction from it's basic block... |
Chris Lattner | ede6ac6 | 2004-04-10 06:53:09 +0000 | [diff] [blame] | 243 | BB->getInstList().erase(I); |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 244 | ++NumInstRemoved; |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 245 | } |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 246 | } |
| 247 | } |
| 248 | |
Chris Lattner | 34e353e | 2003-06-16 12:10:45 +0000 | [diff] [blame] | 249 | // Check to ensure we have an exit node for this CFG. If we don't, we won't |
| 250 | // have any post-dominance information, thus we cannot perform our |
| 251 | // transformations safely. |
| 252 | // |
Owen Anderson | a65064b | 2007-04-18 06:46:57 +0000 | [diff] [blame] | 253 | PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); |
| 254 | if (DT[&Func->getEntryBlock()] == 0) { |
Chris Lattner | 34e353e | 2003-06-16 12:10:45 +0000 | [diff] [blame] | 255 | WorkList.clear(); |
| 256 | return MadeChanges; |
| 257 | } |
| 258 | |
Chris Lattner | faa45ce | 2003-11-16 21:39:27 +0000 | [diff] [blame] | 259 | // Scan the function marking blocks without post-dominance information as |
| 260 | // live. Blocks without post-dominance information occur when there is an |
| 261 | // infinite loop in the program. Because the infinite loop could contain a |
| 262 | // function which unwinds, exits or has side-effects, we don't want to delete |
| 263 | // the infinite loop or those blocks leading up to it. |
| 264 | for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) |
Owen Anderson | a65064b | 2007-04-18 06:46:57 +0000 | [diff] [blame] | 265 | if (DT[I] == 0 && ReachableBBs.count(I)) |
Chris Lattner | faa45ce | 2003-11-16 21:39:27 +0000 | [diff] [blame] | 266 | for (pred_iterator PI = pred_begin(I), E = pred_end(I); PI != E; ++PI) |
| 267 | markInstructionLive((*PI)->getTerminator()); |
| 268 | |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 269 | DOUT << "Processing work list\n"; |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 270 | |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 271 | // AliveBlocks - Set of basic blocks that we know have instructions that are |
| 272 | // alive in them... |
| 273 | // |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 274 | std::set<BasicBlock*> AliveBlocks; |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 275 | |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 276 | // Process the work list of instructions that just became live... if they |
Misha Brukman | 5560c9d | 2003-08-18 14:43:39 +0000 | [diff] [blame] | 277 | // became live, then that means that all of their operands are necessary as |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 278 | // well... make them live as well. |
| 279 | // |
| 280 | while (!WorkList.empty()) { |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 281 | Instruction *I = WorkList.back(); // Get an instruction that became live... |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 282 | WorkList.pop_back(); |
| 283 | |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 284 | BasicBlock *BB = I->getParent(); |
Chris Lattner | b9110c6 | 2004-05-04 17:00:46 +0000 | [diff] [blame] | 285 | if (!ReachableBBs.count(BB)) continue; |
Chris Lattner | 4e51ccd | 2004-12-12 22:22:18 +0000 | [diff] [blame] | 286 | if (AliveBlocks.insert(BB).second) // Basic block not alive yet. |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 287 | markBlockAlive(BB); // Make it so now! |
Chris Lattner | 72f1e99 | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 288 | |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 289 | // PHI nodes are a special case, because the incoming values are actually |
| 290 | // defined in the predecessor nodes of this block, meaning that the PHI |
| 291 | // makes the predecessors alive. |
| 292 | // |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 293 | if (PHINode *PN = dyn_cast<PHINode>(I)) { |
| 294 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
| 295 | // If the incoming edge is clearly dead, it won't have control |
| 296 | // dependence information. Do not mark it live. |
| 297 | BasicBlock *PredBB = PN->getIncomingBlock(i); |
| 298 | if (ReachableBBs.count(PredBB)) { |
| 299 | // FIXME: This should mark the control dependent edge as live, not |
| 300 | // necessarily the predecessor itself! |
| 301 | if (AliveBlocks.insert(PredBB).second) |
| 302 | markBlockAlive(PN->getIncomingBlock(i)); // Block is newly ALIVE! |
| 303 | if (Instruction *Op = dyn_cast<Instruction>(PN->getIncomingValue(i))) |
| 304 | markInstructionLive(Op); |
| 305 | } |
| 306 | } |
| 307 | } else { |
| 308 | // Loop over all of the operands of the live instruction, making sure that |
| 309 | // they are known to be alive as well. |
| 310 | // |
| 311 | for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) |
| 312 | if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op))) |
| 313 | markInstructionLive(Operand); |
| 314 | } |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 315 | } |
| 316 | |
Chris Lattner | de579f1 | 2003-05-22 22:00:07 +0000 | [diff] [blame] | 317 | DEBUG( |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 318 | DOUT << "Current Function: X = Live\n"; |
Chris Lattner | 34e353e | 2003-06-16 12:10:45 +0000 | [diff] [blame] | 319 | for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I){ |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 320 | DOUT << I->getName() << ":\t" |
| 321 | << (AliveBlocks.count(I) ? "LIVE\n" : "DEAD\n"); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 322 | for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){ |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 323 | if (LiveSet.count(BI)) DOUT << "X "; |
| 324 | DOUT << *BI; |
Chris Lattner | f016ea4 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 325 | } |
Chris Lattner | 34e353e | 2003-06-16 12:10:45 +0000 | [diff] [blame] | 326 | }); |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 327 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 328 | // All blocks being live is a common case, handle it specially. |
Chris Lattner | 446698b | 2002-07-30 00:22:34 +0000 | [diff] [blame] | 329 | if (AliveBlocks.size() == Func->size()) { // No dead blocks? |
Chris Lattner | 837e42c | 2003-06-24 23:02:45 +0000 | [diff] [blame] | 330 | for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) { |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 331 | // Loop over all of the instructions in the function deleting instructions |
| 332 | // to drop their references. |
| 333 | deleteDeadInstructionsInLiveBlock(I); |
Chris Lattner | 837e42c | 2003-06-24 23:02:45 +0000 | [diff] [blame] | 334 | |
| 335 | // Check to make sure the terminator instruction is live. If it isn't, |
| 336 | // this means that the condition that it branches on (we know it is not an |
| 337 | // unconditional branch), is not needed to make the decision of where to |
| 338 | // go to, because all outgoing edges go to the same place. We must remove |
| 339 | // the use of the condition (because it's probably dead), so we convert |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 340 | // the terminator to an unconditional branch. |
Chris Lattner | 837e42c | 2003-06-24 23:02:45 +0000 | [diff] [blame] | 341 | // |
| 342 | TerminatorInst *TI = I->getTerminator(); |
| 343 | if (!LiveSet.count(TI)) |
| 344 | convertToUnconditionalBranch(TI); |
| 345 | } |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 346 | |
| 347 | return MadeChanges; |
| 348 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 349 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 350 | |
| 351 | // If the entry node is dead, insert a new entry node to eliminate the entry |
| 352 | // node as a special case. |
| 353 | // |
| 354 | if (!AliveBlocks.count(&Func->front())) { |
| 355 | BasicBlock *NewEntry = new BasicBlock(); |
| 356 | new BranchInst(&Func->front(), NewEntry); |
| 357 | Func->getBasicBlockList().push_front(NewEntry); |
| 358 | AliveBlocks.insert(NewEntry); // This block is always alive! |
| 359 | LiveSet.insert(NewEntry->getTerminator()); // The branch is live |
| 360 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 361 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 362 | // Loop over all of the alive blocks in the function. If any successor |
| 363 | // blocks are not alive, we adjust the outgoing branches to branch to the |
| 364 | // first live postdominator of the live block, adjusting any PHI nodes in |
| 365 | // the block to reflect this. |
| 366 | // |
| 367 | for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) |
| 368 | if (AliveBlocks.count(I)) { |
| 369 | BasicBlock *BB = I; |
| 370 | TerminatorInst *TI = BB->getTerminator(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 371 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 372 | // If the terminator instruction is alive, but the block it is contained |
| 373 | // in IS alive, this means that this terminator is a conditional branch on |
| 374 | // a condition that doesn't matter. Make it an unconditional branch to |
| 375 | // ONE of the successors. This has the side effect of dropping a use of |
| 376 | // the conditional value, which may also be dead. |
| 377 | if (!LiveSet.count(TI)) |
| 378 | TI = convertToUnconditionalBranch(TI); |
Chris Lattner | 99c91e0 | 2003-06-24 21:49:45 +0000 | [diff] [blame] | 379 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 380 | // Loop over all of the successors, looking for ones that are not alive. |
| 381 | // We cannot save the number of successors in the terminator instruction |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 382 | // here because we may remove them if we don't have a postdominator. |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 383 | // |
| 384 | for (unsigned i = 0; i != TI->getNumSuccessors(); ++i) |
| 385 | if (!AliveBlocks.count(TI->getSuccessor(i))) { |
| 386 | // Scan up the postdominator tree, looking for the first |
| 387 | // postdominator that is alive, and the last postdominator that is |
| 388 | // dead... |
| 389 | // |
Owen Anderson | a65064b | 2007-04-18 06:46:57 +0000 | [diff] [blame] | 390 | PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; |
| 391 | PostDominatorTree::Node *NextNode = 0; |
| 392 | |
| 393 | if (LastNode) { |
| 394 | NextNode = LastNode->getIDom(); |
| 395 | while (!AliveBlocks.count(NextNode->getBlock())) { |
| 396 | LastNode = NextNode; |
| 397 | NextNode = NextNode->getIDom(); |
| 398 | if (NextNode == 0) { |
| 399 | LastNode = 0; |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 400 | break; |
| 401 | } |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 402 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 403 | } |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 404 | |
| 405 | // There is a special case here... if there IS no post-dominator for |
| 406 | // the block we have nowhere to point our branch to. Instead, convert |
| 407 | // it to a return. This can only happen if the code branched into an |
| 408 | // infinite loop. Note that this may not be desirable, because we |
| 409 | // _are_ altering the behavior of the code. This is a well known |
| 410 | // drawback of ADCE, so in the future if we choose to revisit the |
| 411 | // decision, this is where it should be. |
| 412 | // |
Owen Anderson | a65064b | 2007-04-18 06:46:57 +0000 | [diff] [blame] | 413 | if (LastNode == 0) { // No postdominator! |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 414 | if (!isa<InvokeInst>(TI)) { |
| 415 | // Call RemoveSuccessor to transmogrify the terminator instruction |
| 416 | // to not contain the outgoing branch, or to create a new |
| 417 | // terminator if the form fundamentally changes (i.e., |
| 418 | // unconditional branch to return). Note that this will change a |
| 419 | // branch into an infinite loop into a return instruction! |
| 420 | // |
| 421 | RemoveSuccessor(TI, i); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 422 | |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 423 | // RemoveSuccessor may replace TI... make sure we have a fresh |
| 424 | // pointer. |
| 425 | // |
| 426 | TI = BB->getTerminator(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 427 | |
Chris Lattner | 1a84bd3 | 2005-02-17 19:28:49 +0000 | [diff] [blame] | 428 | // Rescan this successor... |
| 429 | --i; |
| 430 | } else { |
| 431 | |
| 432 | } |
| 433 | } else { |
Owen Anderson | a65064b | 2007-04-18 06:46:57 +0000 | [diff] [blame] | 434 | // Get the basic blocks that we need... |
| 435 | BasicBlock *LastDead = LastNode->getBlock(); |
| 436 | BasicBlock *NextAlive = NextNode->getBlock(); |
| 437 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 438 | // Make the conditional branch now go to the next alive block... |
| 439 | TI->getSuccessor(i)->removePredecessor(BB); |
| 440 | TI->setSuccessor(i, NextAlive); |
Chris Lattner | 011de07 | 2002-07-29 22:31:39 +0000 | [diff] [blame] | 441 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 442 | // If there are PHI nodes in NextAlive, we need to add entries to |
| 443 | // the PHI nodes for the new incoming edge. The incoming values |
| 444 | // should be identical to the incoming values for LastDead. |
| 445 | // |
| 446 | for (BasicBlock::iterator II = NextAlive->begin(); |
| 447 | isa<PHINode>(II); ++II) { |
| 448 | PHINode *PN = cast<PHINode>(II); |
| 449 | if (LiveSet.count(PN)) { // Only modify live phi nodes |
| 450 | // Get the incoming value for LastDead... |
| 451 | int OldIdx = PN->getBasicBlockIndex(LastDead); |
| 452 | assert(OldIdx != -1 &&"LastDead is not a pred of NextAlive!"); |
| 453 | Value *InVal = PN->getIncomingValue(OldIdx); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 454 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 455 | // Add an incoming value for BB now... |
| 456 | PN->addIncoming(InVal, BB); |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 457 | } |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 458 | } |
| 459 | } |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 460 | } |
Chris Lattner | 5554727 | 2002-05-10 15:37:35 +0000 | [diff] [blame] | 461 | |
Chris Lattner | 6b8efcd | 2004-12-12 23:49:37 +0000 | [diff] [blame] | 462 | // Now loop over all of the instructions in the basic block, deleting |
| 463 | // dead instructions. This is so that the next sweep over the program |
| 464 | // can safely delete dead instructions without other dead instructions |
| 465 | // still referring to them. |
| 466 | // |
| 467 | deleteDeadInstructionsInLiveBlock(BB); |
| 468 | } |
Chris Lattner | b8259dd | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 469 | |
Chris Lattner | d7f268d | 2003-01-23 02:12:18 +0000 | [diff] [blame] | 470 | // Loop over all of the basic blocks in the function, dropping references of |
| 471 | // the dead basic blocks. We must do this after the previous step to avoid |
| 472 | // dropping references to PHIs which still have entries... |
| 473 | // |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 474 | std::vector<BasicBlock*> DeadBlocks; |
Chris Lattner | d7f268d | 2003-01-23 02:12:18 +0000 | [diff] [blame] | 475 | for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 476 | if (!AliveBlocks.count(BB)) { |
| 477 | // Remove PHI node entries for this block in live successor blocks. |
| 478 | for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) |
| 479 | if (!SI->empty() && isa<PHINode>(SI->front()) && AliveBlocks.count(*SI)) |
| 480 | (*SI)->removePredecessor(BB); |
| 481 | |
Chris Lattner | d7f268d | 2003-01-23 02:12:18 +0000 | [diff] [blame] | 482 | BB->dropAllReferences(); |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 483 | MadeChanges = true; |
| 484 | DeadBlocks.push_back(BB); |
| 485 | } |
| 486 | |
| 487 | NumBlockRemoved += DeadBlocks.size(); |
Chris Lattner | 5554727 | 2002-05-10 15:37:35 +0000 | [diff] [blame] | 488 | |
Chris Lattner | 84369b3 | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 489 | // Now loop through all of the blocks and delete the dead ones. We can safely |
| 490 | // do this now because we know that there are no references to dead blocks |
Chris Lattner | 387bc13 | 2004-12-12 23:40:17 +0000 | [diff] [blame] | 491 | // (because they have dropped all of their references). |
| 492 | for (std::vector<BasicBlock*>::iterator I = DeadBlocks.begin(), |
| 493 | E = DeadBlocks.end(); I != E; ++I) |
| 494 | Func->getBasicBlockList().erase(*I); |
Chris Lattner | 5554727 | 2002-05-10 15:37:35 +0000 | [diff] [blame] | 495 | |
Chris Lattner | d9036a1 | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 496 | return MadeChanges; |
Chris Lattner | 02e90d5 | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 497 | } |