LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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/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 }