LLVM API Documentation

UnreachableBlockElim.cpp

Go to the documentation of this file.
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 }