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