UnreachableBlockElim.cpp revision 5b3a4553c1da7e417a240379e2f510c77532c5c1
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" 31using namespace llvm; 32 33namespace { 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 41FunctionPass *llvm::createUnreachableBlockEliminationPass() { 42 return new UnreachableBlockElim(); 43} 44 45bool 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