1 //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2 // 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. 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/ADT/DepthFirstIterator.h" 31 using namespace llvm; 32 33 namespace { 34 class UnreachableBlockElim : public FunctionPass { 35 virtual bool runOnFunction(Function &F); 36 }; 37 RegisterOpt<UnreachableBlockElim> 38 X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 39 } 40 41 FunctionPass *llvm::createUnreachableBlockEliminationPass() { 42 return new UnreachableBlockElim(); 43 } 44 45 bool UnreachableBlockElim::runOnFunction(Function &F) { 46 std::set<BasicBlock*> Reachable; 47 48 // Mark all reachable blocks. 49 for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 50 E = df_ext_end(&F, Reachable); I != E; ++I) 51 /* Mark all reachable blocks */; 52 53 // Loop over all dead blocks, remembering them and deleting all instructions 54 // in them. 55 std::vector<BasicBlock*> DeadBlocks; 56 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 57 if (!Reachable.count(I)) { 58 BasicBlock *BB = I; 59 DeadBlocks.push_back(BB); 60 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 61 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 62 BB->getInstList().pop_front(); 63 } 64 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 65 (*SI)->removePredecessor(BB); 66 BB->dropAllReferences(); 67 } 68 69 if (DeadBlocks.empty()) return false; 70 71 // Actually remove the blocks now. 72 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 73 F.getBasicBlockList().erase(DeadBlocks[i]); 74 75 return true; 76 } 77