LLVM API Documentation
00001 //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass is an extremely simple version of the SimplifyCFG pass. Its sole 00011 // job is to delete LLVM basic blocks that are not reachable from the entry 00012 // node. To do this, it performs a simple depth first traversal of the CFG, 00013 // then deletes any unvisited nodes. 00014 // 00015 // Note that this pass is really a hack. In particular, the instruction 00016 // selectors for various targets should just not generate code for unreachable 00017 // blocks. Until LLVM has a more systematic way of defining instruction 00018 // selectors, however, we cannot really expect them to handle additional 00019 // complexity. 00020 // 00021 //===----------------------------------------------------------------------===// 00022 00023 #include "llvm/CodeGen/Passes.h" 00024 #include "llvm/Constant.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Function.h" 00027 #include "llvm/Pass.h" 00028 #include "llvm/Type.h" 00029 #include "llvm/Support/CFG.h" 00030 #include "llvm/ADT/DepthFirstIterator.h" 00031 using namespace llvm; 00032 00033 namespace { 00034 class UnreachableBlockElim : public FunctionPass { 00035 virtual bool runOnFunction(Function &F); 00036 }; 00037 RegisterOpt<UnreachableBlockElim> 00038 X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 00039 } 00040 00041 FunctionPass *llvm::createUnreachableBlockEliminationPass() { 00042 return new UnreachableBlockElim(); 00043 } 00044 00045 bool UnreachableBlockElim::runOnFunction(Function &F) { 00046 std::set<BasicBlock*> Reachable; 00047 00048 // Mark all reachable blocks. 00049 for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 00050 E = df_ext_end(&F, Reachable); I != E; ++I) 00051 /* Mark all reachable blocks */; 00052 00053 // Loop over all dead blocks, remembering them and deleting all instructions 00054 // in them. 00055 std::vector<BasicBlock*> DeadBlocks; 00056 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00057 if (!Reachable.count(I)) { 00058 BasicBlock *BB = I; 00059 DeadBlocks.push_back(BB); 00060 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 00061 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 00062 BB->getInstList().pop_front(); 00063 } 00064 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 00065 (*SI)->removePredecessor(BB); 00066 BB->dropAllReferences(); 00067 } 00068 00069 if (DeadBlocks.empty()) return false; 00070 00071 // Actually remove the blocks now. 00072 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 00073 F.getBasicBlockList().erase(DeadBlocks[i]); 00074 00075 return true; 00076 }