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/Support/CFG.h" 00029 #include "llvm/ADT/DepthFirstIterator.h" 00030 using namespace llvm; 00031 00032 namespace { 00033 class UnreachableBlockElim : public FunctionPass { 00034 virtual bool runOnFunction(Function &F); 00035 }; 00036 RegisterOpt<UnreachableBlockElim> 00037 X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 00038 } 00039 00040 FunctionPass *llvm::createUnreachableBlockEliminationPass() { 00041 return new UnreachableBlockElim(); 00042 } 00043 00044 bool UnreachableBlockElim::runOnFunction(Function &F) { 00045 std::set<BasicBlock*> Reachable; 00046 00047 // Mark all reachable blocks. 00048 for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 00049 E = df_ext_end(&F, Reachable); I != E; ++I) 00050 /* Mark all reachable blocks */; 00051 00052 // Loop over all dead blocks, remembering them and deleting all instructions 00053 // in them. 00054 std::vector<BasicBlock*> DeadBlocks; 00055 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00056 if (!Reachable.count(I)) { 00057 BasicBlock *BB = I; 00058 DeadBlocks.push_back(BB); 00059 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 00060 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 00061 BB->getInstList().pop_front(); 00062 } 00063 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 00064 (*SI)->removePredecessor(BB); 00065 BB->dropAllReferences(); 00066 } 00067 00068 if (DeadBlocks.empty()) return false; 00069 00070 // Actually remove the blocks now. 00071 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 00072 F.getBasicBlockList().erase(DeadBlocks[i]); 00073 00074 return true; 00075 }