UnreachableBlockElim.cpp revision 089efffd7d1ca0d10522ace38d36e0a67f4fac2d
1//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 11// job is to delete LLVM basic blocks that are not reachable from the entry 12// node. To do this, it performs a simple depth first traversal of the CFG, 13// then deletes any unvisited nodes. 14// 15// Note that this pass is really a hack. In particular, the instruction 16// selectors for various targets should just not generate code for unreachable 17// blocks. Until LLVM has a more systematic way of defining instruction 18// selectors, however, we cannot really expect them to handle additional 19// complexity. 20// 21//===----------------------------------------------------------------------===// 22 23#include "llvm/CodeGen/Passes.h" 24#include "llvm/Constant.h" 25#include "llvm/Instructions.h" 26#include "llvm/Function.h" 27#include "llvm/Pass.h" 28#include "llvm/Type.h" 29#include "llvm/Support/CFG.h" 30#include "llvm/Support/Compiler.h" 31#include "llvm/ADT/DepthFirstIterator.h" 32using namespace llvm; 33 34namespace { 35 class VISIBILITY_HIDDEN UnreachableBlockElim : public FunctionPass { 36 virtual bool runOnFunction(Function &F); 37 public: 38 static char ID; // Pass identification, replacement for typeid 39 UnreachableBlockElim() : FunctionPass((intptr_t)&ID) {} 40 }; 41} 42char UnreachableBlockElim::ID = 0; 43static RegisterPass<UnreachableBlockElim> 44X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 45 46FunctionPass *llvm::createUnreachableBlockEliminationPass() { 47 return new UnreachableBlockElim(); 48} 49 50bool UnreachableBlockElim::runOnFunction(Function &F) { 51 std::set<BasicBlock*> Reachable; 52 53 // Mark all reachable blocks. 54 for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 55 E = df_ext_end(&F, Reachable); I != E; ++I) 56 /* Mark all reachable blocks */; 57 58 // Loop over all dead blocks, remembering them and deleting all instructions 59 // in them. 60 std::vector<BasicBlock*> DeadBlocks; 61 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 62 if (!Reachable.count(I)) { 63 BasicBlock *BB = I; 64 DeadBlocks.push_back(BB); 65 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 66 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 67 BB->getInstList().pop_front(); 68 } 69 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 70 (*SI)->removePredecessor(BB); 71 BB->dropAllReferences(); 72 } 73 74 if (DeadBlocks.empty()) return false; 75 76 // Actually remove the blocks now. 77 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 78 F.getBasicBlockList().erase(DeadBlocks[i]); 79 80 return true; 81} 82