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