ADCE.cpp revision 697954c15da58bd8b186dbafdedd8b06db770201
1//===- ADCE.cpp - Code to perform agressive dead code elimination ---------===// 2// 3// This file implements "agressive" dead code elimination. ADCE is DCe where 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 9#include "llvm/Optimizations/DCE.h" 10#include "llvm/Instruction.h" 11#include "llvm/Type.h" 12#include "llvm/Analysis/Dominators.h" 13#include "llvm/Analysis/Writer.h" 14#include "llvm/iTerminators.h" 15#include "llvm/iPHINode.h" 16#include "Support/STLExtras.h" 17#include "Support/DepthFirstIterator.h" 18#include <set> 19#include <algorithm> 20#include <iostream> 21using std::cerr; 22 23#define DEBUG_ADCE 1 24 25//===----------------------------------------------------------------------===// 26// ADCE Class 27// 28// This class does all of the work of Agressive Dead Code Elimination. 29// It's public interface consists of a constructor and a doADCE() method. 30// 31class ADCE { 32 Method *M; // The method that we are working on... 33 std::vector<Instruction*> WorkList; // Instructions that just became live 34 std::set<Instruction*> LiveSet; // The set of live instructions 35 bool MadeChanges; 36 37 //===--------------------------------------------------------------------===// 38 // The public interface for this class 39 // 40public: 41 // ADCE Ctor - Save the method to operate on... 42 inline ADCE(Method *m) : M(m), MadeChanges(false) {} 43 44 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning 45 // true if the method was modified. 46 bool doADCE(); 47 48 //===--------------------------------------------------------------------===// 49 // The implementation of this class 50 // 51private: 52 inline void markInstructionLive(Instruction *I) { 53 if (LiveSet.count(I)) return; 54#ifdef DEBUG_ADCE 55 cerr << "Insn Live: " << I; 56#endif 57 LiveSet.insert(I); 58 WorkList.push_back(I); 59 } 60 61 inline void markTerminatorLive(const BasicBlock *BB) { 62#ifdef DEBUG_ADCE 63 cerr << "Terminat Live: " << BB->getTerminator(); 64#endif 65 markInstructionLive((Instruction*)BB->getTerminator()); 66 } 67 68 // fixupCFG - Walk the CFG in depth first order, eliminating references to 69 // dead blocks. 70 // 71 BasicBlock *fixupCFG(BasicBlock *Head, std::set<BasicBlock*> &VisitedBlocks, 72 const std::set<BasicBlock*> &AliveBlocks); 73}; 74 75 76 77// doADCE() - Run the Agressive Dead Code Elimination algorithm, returning 78// true if the method was modified. 79// 80bool ADCE::doADCE() { 81 // Compute the control dependence graph... Note that this has a side effect 82 // on the CFG: a new return bb is added and all returns are merged here. 83 // 84 cfg::DominanceFrontier CDG(cfg::DominatorSet(M, true)); 85 86#ifdef DEBUG_ADCE 87 cerr << "Method: " << M; 88#endif 89 90 // Iterate over all of the instructions in the method, eliminating trivially 91 // dead instructions, and marking instructions live that are known to be 92 // needed. Perform the walk in depth first order so that we avoid marking any 93 // instructions live in basic blocks that are unreachable. These blocks will 94 // be eliminated later, along with the instructions inside. 95 // 96 for (df_iterator<Method*> BBI = df_begin(M), 97 BBE = df_end(M); 98 BBI != BBE; ++BBI) { 99 BasicBlock *BB = *BBI; 100 for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { 101 Instruction *I = *II; 102 103 if (I->hasSideEffects() || I->getOpcode() == Instruction::Ret) { 104 markInstructionLive(I); 105 } else { 106 // Check to see if anything is trivially dead 107 if (I->use_size() == 0 && I->getType() != Type::VoidTy) { 108 // Remove the instruction from it's basic block... 109 delete BB->getInstList().remove(II); 110 MadeChanges = true; 111 continue; // Don't increment the iterator past the current slot 112 } 113 } 114 115 ++II; // Increment the inst iterator if the inst wasn't deleted 116 } 117 } 118 119#ifdef DEBUG_ADCE 120 cerr << "Processing work list\n"; 121#endif 122 123 // AliveBlocks - Set of basic blocks that we know have instructions that are 124 // alive in them... 125 // 126 std::set<BasicBlock*> AliveBlocks; 127 128 // Process the work list of instructions that just became live... if they 129 // became live, then that means that all of their operands are neccesary as 130 // well... make them live as well. 131 // 132 while (!WorkList.empty()) { 133 Instruction *I = WorkList.back(); // Get an instruction that became live... 134 WorkList.pop_back(); 135 136 BasicBlock *BB = I->getParent(); 137 if (AliveBlocks.count(BB) == 0) { // Basic block not alive yet... 138 // Mark the basic block as being newly ALIVE... and mark all branches that 139 // this block is control dependant on as being alive also... 140 // 141 AliveBlocks.insert(BB); // Block is now ALIVE! 142 cfg::DominanceFrontier::const_iterator It = CDG.find(BB); 143 if (It != CDG.end()) { 144 // Get the blocks that this node is control dependant on... 145 const cfg::DominanceFrontier::DomSetType &CDB = It->second; 146 for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live 147 bind_obj(this, &ADCE::markTerminatorLive)); 148 } 149 150 // If this basic block is live, then the terminator must be as well! 151 markTerminatorLive(BB); 152 } 153 154 // Loop over all of the operands of the live instruction, making sure that 155 // they are known to be alive as well... 156 // 157 for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) { 158 if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op))) 159 markInstructionLive(Operand); 160 } 161 } 162 163#ifdef DEBUG_ADCE 164 cerr << "Current Method: X = Live\n"; 165 for (Method::inst_iterator IL = M->inst_begin(); IL != M->inst_end(); ++IL) { 166 if (LiveSet.count(*IL)) cerr << "X "; 167 cerr << *IL; 168 } 169#endif 170 171 // After the worklist is processed, recursively walk the CFG in depth first 172 // order, patching up references to dead blocks... 173 // 174 std::set<BasicBlock*> VisitedBlocks; 175 BasicBlock *EntryBlock = fixupCFG(M->front(), VisitedBlocks, AliveBlocks); 176 if (EntryBlock && EntryBlock != M->front()) { 177 if (isa<PHINode>(EntryBlock->front())) { 178 // Cannot make the first block be a block with a PHI node in it! Instead, 179 // strip the first basic block of the method to contain no instructions, 180 // then add a simple branch to the "real" entry node... 181 // 182 BasicBlock *E = M->front(); 183 if (!isa<TerminatorInst>(E->front()) || // Check for an actual change... 184 cast<TerminatorInst>(E->front())->getNumSuccessors() != 1 || 185 cast<TerminatorInst>(E->front())->getSuccessor(0) != EntryBlock) { 186 E->getInstList().delete_all(); // Delete all instructions in block 187 E->getInstList().push_back(new BranchInst(EntryBlock)); 188 MadeChanges = true; 189 } 190 AliveBlocks.insert(E); 191 192 // Next we need to change any PHI nodes in the entry block to refer to the 193 // new predecessor node... 194 195 196 } else { 197 // We need to move the new entry block to be the first bb of the method. 198 Method::iterator EBI = find(M->begin(), M->end(), EntryBlock); 199 std::swap(*EBI, *M->begin());// Exchange old location with start of method 200 MadeChanges = true; 201 } 202 } 203 204 // Now go through and tell dead blocks to drop all of their references so they 205 // can be safely deleted. 206 // 207 for (Method::iterator BI = M->begin(), BE = M->end(); BI != BE; ++BI) { 208 BasicBlock *BB = *BI; 209 if (!AliveBlocks.count(BB)) { 210 BB->dropAllReferences(); 211 } 212 } 213 214 // Now loop through all of the blocks and delete them. We can safely do this 215 // now because we know that there are no references to dead blocks (because 216 // they have dropped all of their references... 217 // 218 for (Method::iterator BI = M->begin(); BI != M->end();) { 219 if (!AliveBlocks.count(*BI)) { 220 delete M->getBasicBlocks().remove(BI); 221 MadeChanges = true; 222 continue; // Don't increment iterator 223 } 224 ++BI; // Increment iterator... 225 } 226 227 return MadeChanges; 228} 229 230 231// fixupCFG - Walk the CFG in depth first order, eliminating references to 232// dead blocks: 233// If the BB is alive (in AliveBlocks): 234// 1. Eliminate all dead instructions in the BB 235// 2. Recursively traverse all of the successors of the BB: 236// - If the returned successor is non-null, update our terminator to 237// reference the returned BB 238// 3. Return 0 (no update needed) 239// 240// If the BB is dead (not in AliveBlocks): 241// 1. Add the BB to the dead set 242// 2. Recursively traverse all of the successors of the block: 243// - Only one shall return a nonnull value (or else this block should have 244// been in the alive set). 245// 3. Return the nonnull child, or 0 if no non-null children. 246// 247BasicBlock *ADCE::fixupCFG(BasicBlock *BB, std::set<BasicBlock*> &VisitedBlocks, 248 const std::set<BasicBlock*> &AliveBlocks) { 249 if (VisitedBlocks.count(BB)) return 0; // Revisiting a node? No update. 250 VisitedBlocks.insert(BB); // We have now visited this node! 251 252#ifdef DEBUG_ADCE 253 cerr << "Fixing up BB: " << BB; 254#endif 255 256 if (AliveBlocks.count(BB)) { // Is the block alive? 257 // Yes it's alive: loop through and eliminate all dead instructions in block 258 for (BasicBlock::iterator II = BB->begin(); II != BB->end()-1; ) { 259 Instruction *I = *II; 260 if (!LiveSet.count(I)) { // Is this instruction alive? 261 // Nope... remove the instruction from it's basic block... 262 delete BB->getInstList().remove(II); 263 MadeChanges = true; 264 continue; // Don't increment II 265 } 266 ++II; 267 } 268 269 // Recursively traverse successors of this basic block. 270 BasicBlock::succ_iterator SI = BB->succ_begin(), SE = BB->succ_end(); 271 for (; SI != SE; ++SI) { 272 BasicBlock *Succ = *SI; 273 BasicBlock *Repl = fixupCFG(Succ, VisitedBlocks, AliveBlocks); 274 if (Repl && Repl != Succ) { // We have to replace the successor 275 Succ->replaceAllUsesWith(Repl); 276 MadeChanges = true; 277 } 278 } 279 return BB; 280 } else { // Otherwise the block is dead... 281 BasicBlock *ReturnBB = 0; // Default to nothing live down here 282 283 // Recursively traverse successors of this basic block. 284 BasicBlock::succ_iterator SI = BB->succ_begin(), SE = BB->succ_end(); 285 for (; SI != SE; ++SI) { 286 BasicBlock *RetBB = fixupCFG(*SI, VisitedBlocks, AliveBlocks); 287 if (RetBB) { 288 assert(ReturnBB == 0 && "One one live child allowed!"); 289 ReturnBB = RetBB; 290 } 291 } 292 return ReturnBB; // Return the result of traversal 293 } 294} 295 296 297 298// doADCE - Execute the Agressive Dead Code Elimination Algorithm 299// 300bool opt::AgressiveDCE::doADCE(Method *M) { 301 if (M->isExternal()) return false; 302 ADCE DCE(M); 303 return DCE.doADCE(); 304} 305