1 //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
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
21 //===----------------------------------------------------------------------===//
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"
34 class UnreachableBlockElim : public FunctionPass {
35 virtual bool runOnFunction(Function &F);
37 RegisterOpt<UnreachableBlockElim>
38 X("unreachableblockelim", "Remove unreachable blocks from the CFG");
41 FunctionPass *llvm::createUnreachableBlockEliminationPass() {
42 return new UnreachableBlockElim();
45 bool UnreachableBlockElim::runOnFunction(Function &F) {
46 std::set<BasicBlock*> Reachable;
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 */;
53 // Loop over all dead blocks, remembering them and deleting all instructions
55 std::vector<BasicBlock*> DeadBlocks;
56 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
57 if (!Reachable.count(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();
64 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
65 (*SI)->removePredecessor(BB);
66 BB->dropAllReferences();
69 if (DeadBlocks.empty()) return false;
71 // Actually remove the blocks now.
72 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
73 F.getBasicBlockList().erase(DeadBlocks[i]);