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/Function.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/CFG.h"
27 #include "Support/DepthFirstIterator.h"
31 class UnreachableBlockElim : public FunctionPass {
32 virtual bool runOnFunction(Function &F);
34 RegisterOpt<UnreachableBlockElim>
35 X("unreachableblockelim", "Remove unreachable blocks from the CFG");
38 FunctionPass *llvm::createUnreachableBlockEliminationPass() {
39 return new UnreachableBlockElim();
42 bool UnreachableBlockElim::runOnFunction(Function &F) {
43 std::set<BasicBlock*> Reachable;
45 // Mark all reachable blocks.
46 for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable),
47 E = df_ext_end(&F, Reachable); I != E; ++I)
48 /* Mark all reachable blocks */;
50 // Loop over all dead blocks, remembering them and deleting all instructions
52 std::vector<BasicBlock*> DeadBlocks;
53 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
54 if (!Reachable.count(I)) {
55 DeadBlocks.push_back(I);
56 for (succ_iterator SI = succ_begin(&*I), E = succ_end(&*I); SI != E; ++SI)
57 (*SI)->removePredecessor(I);
58 I->dropAllReferences();
61 if (DeadBlocks.empty()) return false;
63 // Actually remove the blocks now.
64 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
65 F.getBasicBlockList().erase(DeadBlocks[i]);