Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 1 | //===- ADCE.cpp - Code to perform aggressive dead code elimination --------===// |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 2 | // |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 3 | // This file implements "aggressive" dead code elimination. ADCE is DCe where |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 4 | // values are assumed to be dead until proven otherwise. This is similar to |
| 5 | // SCCP, except applied to the liveness of values. |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
Chris Lattner | b4cfa7f | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 9 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 10 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | ee420b7 | 2002-07-29 22:31:39 +0000 | [diff] [blame] | 11 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 12 | #include "llvm/Type.h" |
Chris Lattner | 8024bde | 2001-07-06 16:32:07 +0000 | [diff] [blame] | 13 | #include "llvm/Analysis/Dominators.h" |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 14 | #include "llvm/iTerminators.h" |
Chris Lattner | fb5ae02 | 2001-12-03 18:02:31 +0000 | [diff] [blame] | 15 | #include "llvm/iPHINode.h" |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 16 | #include "llvm/Constant.h" |
Chris Lattner | 60a6591 | 2002-02-12 21:07:25 +0000 | [diff] [blame] | 17 | #include "llvm/Support/CFG.h" |
Chris Lattner | 5de2204 | 2001-11-27 00:03:19 +0000 | [diff] [blame] | 18 | #include "Support/STLExtras.h" |
| 19 | #include "Support/DepthFirstIterator.h" |
Chris Lattner | 71cbd42 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 20 | #include "Support/StatisticReporter.h" |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 21 | #include <algorithm> |
Chris Lattner | 7f74a56 | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 22 | #include <iostream> |
| 23 | using std::cerr; |
Anand Shukla | 2bc6419 | 2002-06-25 21:07:58 +0000 | [diff] [blame] | 24 | using std::vector; |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 25 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 26 | static Statistic<> NumBlockRemoved("adce\t\t- Number of basic blocks removed"); |
| 27 | static Statistic<> NumInstRemoved ("adce\t\t- Number of instructions removed"); |
| 28 | |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 29 | namespace { |
| 30 | |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 31 | //===----------------------------------------------------------------------===// |
| 32 | // ADCE Class |
| 33 | // |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 34 | // This class does all of the work of Aggressive Dead Code Elimination. |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 35 | // It's public interface consists of a constructor and a doADCE() method. |
| 36 | // |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 37 | class ADCE : public FunctionPass { |
| 38 | Function *Func; // The function that we are working on |
Chris Lattner | 7f74a56 | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 39 | std::vector<Instruction*> WorkList; // Instructions that just became live |
| 40 | std::set<Instruction*> LiveSet; // The set of live instructions |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 41 | |
| 42 | //===--------------------------------------------------------------------===// |
| 43 | // The public interface for this class |
| 44 | // |
| 45 | public: |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 46 | // Execute the Aggressive Dead Code Elimination Algorithm |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 47 | // |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 48 | virtual bool runOnFunction(Function &F) { |
| 49 | Func = &F; |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 50 | bool Changed = doADCE(); |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 51 | assert(WorkList.empty()); |
| 52 | LiveSet.clear(); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 53 | return Changed; |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 54 | } |
| 55 | // getAnalysisUsage - We require post dominance frontiers (aka Control |
| 56 | // Dependence Graph) |
| 57 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | 64eea74 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 58 | AU.addRequired(PostDominatorTree::ID); |
| 59 | AU.addRequired(PostDominanceFrontier::ID); |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 60 | } |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 61 | |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 62 | |
| 63 | //===--------------------------------------------------------------------===// |
| 64 | // The implementation of this class |
| 65 | // |
| 66 | private: |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 67 | // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 68 | // true if the function was modified. |
| 69 | // |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 70 | bool doADCE(); |
| 71 | |
| 72 | void markBlockAlive(BasicBlock *BB); |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 73 | |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 74 | inline void markInstructionLive(Instruction *I) { |
| 75 | if (LiveSet.count(I)) return; |
Chris Lattner | 71cbd42 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 76 | DEBUG(cerr << "Insn Live: " << I); |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 77 | LiveSet.insert(I); |
| 78 | WorkList.push_back(I); |
| 79 | } |
| 80 | |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 81 | inline void markTerminatorLive(const BasicBlock *BB) { |
Chris Lattner | 71cbd42 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 82 | DEBUG(cerr << "Terminat Live: " << BB->getTerminator()); |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 83 | markInstructionLive((Instruction*)BB->getTerminator()); |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 84 | } |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 85 | }; |
| 86 | |
Chris Lattner | c8b7092 | 2002-07-26 21:12:46 +0000 | [diff] [blame] | 87 | RegisterOpt<ADCE> X("adce", "Aggressive Dead Code Elimination"); |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 88 | } // End of anonymous namespace |
| 89 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 90 | Pass *createAggressiveDCEPass() { return new ADCE(); } |
| 91 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 92 | void ADCE::markBlockAlive(BasicBlock *BB) { |
| 93 | // Mark the basic block as being newly ALIVE... and mark all branches that |
| 94 | // this block is control dependant on as being alive also... |
| 95 | // |
Chris Lattner | 64eea74 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 96 | PostDominanceFrontier &CDG = getAnalysis<PostDominanceFrontier>(); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 97 | |
Chris Lattner | 64eea74 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 98 | PostDominanceFrontier::const_iterator It = CDG.find(BB); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 99 | if (It != CDG.end()) { |
| 100 | // Get the blocks that this node is control dependant on... |
Chris Lattner | 64eea74 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 101 | const PostDominanceFrontier::DomSetType &CDB = It->second; |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 102 | for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live |
| 103 | bind_obj(this, &ADCE::markTerminatorLive)); |
| 104 | } |
| 105 | |
| 106 | // If this basic block is live, then the terminator must be as well! |
| 107 | markTerminatorLive(BB); |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 108 | } |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 109 | |
| 110 | |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 111 | // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning |
Chris Lattner | c8e6654 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 112 | // true if the function was modified. |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 113 | // |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 114 | bool ADCE::doADCE() { |
| 115 | bool MadeChanges = false; |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 116 | |
Chris Lattner | c8e6654 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 117 | // Iterate over all of the instructions in the function, eliminating trivially |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 118 | // dead instructions, and marking instructions live that are known to be |
| 119 | // needed. Perform the walk in depth first order so that we avoid marking any |
| 120 | // instructions live in basic blocks that are unreachable. These blocks will |
| 121 | // be eliminated later, along with the instructions inside. |
| 122 | // |
Chris Lattner | 019f364 | 2002-05-06 17:27:57 +0000 | [diff] [blame] | 123 | for (df_iterator<Function*> BBI = df_begin(Func), BBE = df_end(Func); |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 124 | BBI != BBE; ++BBI) { |
| 125 | BasicBlock *BB = *BBI; |
| 126 | for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 127 | if (II->hasSideEffects() || II->getOpcode() == Instruction::Ret) { |
| 128 | markInstructionLive(II); |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 129 | ++II; // Increment the inst iterator if the inst wasn't deleted |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 130 | } else if (isInstructionTriviallyDead(II)) { |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 131 | // Remove the instruction from it's basic block... |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 132 | II = BB->getInstList().erase(II); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 133 | ++NumInstRemoved; |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 134 | MadeChanges = true; |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 135 | } else { |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 136 | ++II; // Increment the inst iterator if the inst wasn't deleted |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 137 | } |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 138 | } |
| 139 | } |
| 140 | |
Chris Lattner | 71cbd42 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 141 | DEBUG(cerr << "Processing work list\n"); |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 142 | |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 143 | // AliveBlocks - Set of basic blocks that we know have instructions that are |
| 144 | // alive in them... |
| 145 | // |
Chris Lattner | 7f74a56 | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 146 | std::set<BasicBlock*> AliveBlocks; |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 147 | |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 148 | // Process the work list of instructions that just became live... if they |
| 149 | // became live, then that means that all of their operands are neccesary as |
| 150 | // well... make them live as well. |
| 151 | // |
| 152 | while (!WorkList.empty()) { |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 153 | Instruction *I = WorkList.back(); // Get an instruction that became live... |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 154 | WorkList.pop_back(); |
| 155 | |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 156 | BasicBlock *BB = I->getParent(); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 157 | if (!AliveBlocks.count(BB)) { // Basic block not alive yet... |
| 158 | AliveBlocks.insert(BB); // Block is now ALIVE! |
| 159 | markBlockAlive(BB); // Make it so now! |
Chris Lattner | fb8ed0c | 2001-07-08 18:38:36 +0000 | [diff] [blame] | 160 | } |
| 161 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 162 | // PHI nodes are a special case, because the incoming values are actually |
| 163 | // defined in the predecessor nodes of this block, meaning that the PHI |
| 164 | // makes the predecessors alive. |
| 165 | // |
| 166 | if (PHINode *PN = dyn_cast<PHINode>(I)) |
| 167 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) |
| 168 | if (!AliveBlocks.count(*PI)) { |
| 169 | AliveBlocks.insert(BB); // Block is now ALIVE! |
| 170 | markBlockAlive(*PI); |
| 171 | } |
| 172 | |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 173 | // Loop over all of the operands of the live instruction, making sure that |
| 174 | // they are known to be alive as well... |
| 175 | // |
Chris Lattner | c1496bda | 2002-05-07 22:11:39 +0000 | [diff] [blame] | 176 | for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) |
Chris Lattner | 4b717c0 | 2001-10-01 16:18:37 +0000 | [diff] [blame] | 177 | if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op))) |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 178 | markInstructionLive(Operand); |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 179 | } |
| 180 | |
Chris Lattner | 71cbd42 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 181 | if (DebugFlag) { |
| 182 | cerr << "Current Function: X = Live\n"; |
| 183 | for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 184 | for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){ |
| 185 | if (LiveSet.count(BI)) cerr << "X "; |
Chris Lattner | 71cbd42 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 186 | cerr << *BI; |
| 187 | } |
| 188 | } |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 189 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 190 | // Find the first postdominator of the entry node that is alive. Make it the |
| 191 | // new entry node... |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 192 | // |
Chris Lattner | 64eea74 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 193 | PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 194 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 195 | // If there are some blocks dead... |
| 196 | if (AliveBlocks.size() != Func->size()) { |
| 197 | // Insert a new entry node to eliminate the entry node as a special case. |
| 198 | BasicBlock *NewEntry = new BasicBlock(); |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 199 | NewEntry->getInstList().push_back(new BranchInst(&Func->front())); |
| 200 | Func->getBasicBlockList().push_front(NewEntry); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 201 | AliveBlocks.insert(NewEntry); // This block is always alive! |
| 202 | |
| 203 | // Loop over all of the alive blocks in the function. If any successor |
| 204 | // blocks are not alive, we adjust the outgoing branches to branch to the |
| 205 | // first live postdominator of the live block, adjusting any PHI nodes in |
| 206 | // the block to reflect this. |
| 207 | // |
| 208 | for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 209 | if (AliveBlocks.count(I)) { |
| 210 | BasicBlock *BB = I; |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 211 | TerminatorInst *TI = BB->getTerminator(); |
| 212 | |
Chris Lattner | ee420b7 | 2002-07-29 22:31:39 +0000 | [diff] [blame] | 213 | // Loop over all of the successors, looking for ones that are not alive. |
| 214 | // We cannot save the number of successors in the terminator instruction |
| 215 | // here because we may remove them if we don't have a postdominator... |
| 216 | // |
| 217 | for (unsigned i = 0; i != TI->getNumSuccessors(); ++i) |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 218 | if (!AliveBlocks.count(TI->getSuccessor(i))) { |
| 219 | // Scan up the postdominator tree, looking for the first |
| 220 | // postdominator that is alive, and the last postdominator that is |
| 221 | // dead... |
| 222 | // |
Chris Lattner | 64eea74 | 2002-07-26 18:40:14 +0000 | [diff] [blame] | 223 | PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; |
Chris Lattner | ee420b7 | 2002-07-29 22:31:39 +0000 | [diff] [blame] | 224 | |
| 225 | // There is a special case here... if there IS no post-dominator for |
| 226 | // the block we have no owhere to point our branch to. Instead, |
| 227 | // convert it to a return. This can only happen if the code |
| 228 | // branched into an infinite loop. Note that this may not be |
| 229 | // desirable, because we _are_ altering the behavior of the code. |
| 230 | // This is a well known drawback of ADCE, so in the future if we |
| 231 | // choose to revisit the decision, this is where it should be. |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 232 | // |
Chris Lattner | ee420b7 | 2002-07-29 22:31:39 +0000 | [diff] [blame] | 233 | if (LastNode == 0) { // No postdominator! |
| 234 | // Call RemoveSuccessor to transmogrify the terminator instruction |
| 235 | // to not contain the outgoing branch, or to create a new |
| 236 | // terminator if the form fundementally changes (ie unconditional |
| 237 | // branch to return). Note that this will change a branch into an |
| 238 | // infinite loop into a return instruction! |
| 239 | // |
| 240 | RemoveSuccessor(TI, i); |
| 241 | |
| 242 | // RemoveSuccessor may replace TI... make sure we have a fresh |
| 243 | // pointer... and e variable. |
| 244 | // |
| 245 | TI = BB->getTerminator(); |
| 246 | |
| 247 | // Rescan this successor... |
| 248 | --i; |
| 249 | } else { |
| 250 | PostDominatorTree::Node *NextNode = LastNode->getIDom(); |
| 251 | |
| 252 | while (!AliveBlocks.count(NextNode->getNode())) { |
| 253 | LastNode = NextNode; |
| 254 | NextNode = NextNode->getIDom(); |
| 255 | } |
| 256 | |
| 257 | // Get the basic blocks that we need... |
| 258 | BasicBlock *LastDead = LastNode->getNode(); |
| 259 | BasicBlock *NextAlive = NextNode->getNode(); |
| 260 | |
| 261 | // Make the conditional branch now go to the next alive block... |
| 262 | TI->getSuccessor(i)->removePredecessor(BB); |
| 263 | TI->setSuccessor(i, NextAlive); |
| 264 | |
| 265 | // If there are PHI nodes in NextAlive, we need to add entries to |
| 266 | // the PHI nodes for the new incoming edge. The incoming values |
| 267 | // should be identical to the incoming values for LastDead. |
| 268 | // |
| 269 | for (BasicBlock::iterator II = NextAlive->begin(); |
| 270 | PHINode *PN = dyn_cast<PHINode>(&*II); ++II) { |
| 271 | // Get the incoming value for LastDead... |
| 272 | int OldIdx = PN->getBasicBlockIndex(LastDead); |
| 273 | assert(OldIdx != -1 && "LastDead is not a pred of NextAlive!"); |
| 274 | Value *InVal = PN->getIncomingValue(OldIdx); |
| 275 | |
| 276 | // Add an incoming value for BB now... |
| 277 | PN->addIncoming(InVal, BB); |
| 278 | } |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 279 | } |
| 280 | } |
Chris Lattner | bad1b4d | 2002-05-10 15:37:35 +0000 | [diff] [blame] | 281 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 282 | // Now loop over all of the instructions in the basic block, telling |
| 283 | // dead instructions to drop their references. This is so that the next |
| 284 | // sweep over the program can safely delete dead instructions without |
| 285 | // other dead instructions still refering to them. |
| 286 | // |
Chris Lattner | 3be5d0b | 2002-07-29 23:40:46 +0000 | [diff] [blame] | 287 | for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ) |
| 288 | if (!LiveSet.count(I)) { // Is this instruction alive? |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 289 | I->dropAllReferences(); // Nope, drop references... |
Chris Lattner | 3be5d0b | 2002-07-29 23:40:46 +0000 | [diff] [blame] | 290 | if (PHINode *PN = dyn_cast<PHINode>(&*I)) { |
| 291 | // We don't want to leave PHI nodes in the program that have |
| 292 | // #arguments != #predecessors, so we remove them now. |
| 293 | // |
| 294 | PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); |
| 295 | |
| 296 | // Delete the instruction... |
| 297 | I = BB->getInstList().erase(I); |
| 298 | } else { |
| 299 | ++I; |
| 300 | } |
| 301 | } else { |
| 302 | ++I; |
| 303 | } |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 304 | } |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 305 | } |
| 306 | |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 307 | // Loop over all of the basic blocks in the function, dropping references of |
| 308 | // the dead basic blocks |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 309 | // |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 310 | for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) { |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 311 | if (!AliveBlocks.count(BB)) { |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 312 | // Remove all outgoing edges from this basic block and convert the |
| 313 | // terminator into a return instruction. |
| 314 | vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); |
| 315 | |
| 316 | if (!Succs.empty()) { |
| 317 | // Loop over all of the successors, removing this block from PHI node |
| 318 | // entries that might be in the block... |
| 319 | while (!Succs.empty()) { |
| 320 | Succs.back()->removePredecessor(BB); |
| 321 | Succs.pop_back(); |
| 322 | } |
| 323 | |
| 324 | // Delete the old terminator instruction... |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 325 | BB->getInstList().pop_back(); |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 326 | const Type *RetTy = Func->getReturnType(); |
| 327 | Instruction *New = new ReturnInst(RetTy != Type::VoidTy ? |
| 328 | Constant::getNullValue(RetTy) : 0); |
| 329 | BB->getInstList().push_back(New); |
| 330 | } |
| 331 | |
| 332 | BB->dropAllReferences(); |
| 333 | ++NumBlockRemoved; |
| 334 | MadeChanges = true; |
| 335 | } |
| 336 | } |
Chris Lattner | bad1b4d | 2002-05-10 15:37:35 +0000 | [diff] [blame] | 337 | |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 338 | // Now loop through all of the blocks and delete the dead ones. We can safely |
| 339 | // do this now because we know that there are no references to dead blocks |
| 340 | // (because they have dropped all of their references... we also remove dead |
| 341 | // instructions from alive blocks. |
Chris Lattner | acfd27d | 2001-09-09 22:26:47 +0000 | [diff] [blame] | 342 | // |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 343 | for (Function::iterator BI = Func->begin(); BI != Func->end(); ) |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 344 | if (!AliveBlocks.count(BI)) |
| 345 | BI = Func->getBasicBlockList().erase(BI); |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 346 | else { |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 347 | for (BasicBlock::iterator II = BI->begin(); II != --BI->end(); ) |
| 348 | if (!LiveSet.count(II)) { // Is this instruction alive? |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 349 | // Nope... remove the instruction from it's basic block... |
Chris Lattner | 113f4f4 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 350 | II = BI->getInstList().erase(II); |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 351 | ++NumInstRemoved; |
| 352 | MadeChanges = true; |
| 353 | } else { |
| 354 | ++II; |
| 355 | } |
| 356 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 357 | ++BI; // Increment iterator... |
Chris Lattner | 194138c | 2002-05-28 21:38:16 +0000 | [diff] [blame] | 358 | } |
Chris Lattner | bad1b4d | 2002-05-10 15:37:35 +0000 | [diff] [blame] | 359 | |
Chris Lattner | 559f0ee | 2002-05-22 21:32:16 +0000 | [diff] [blame] | 360 | return MadeChanges; |
Chris Lattner | b28986f | 2001-06-30 06:39:11 +0000 | [diff] [blame] | 361 | } |