LLVM API Documentation

Scalar/SimplifyCFG.cpp

Go to the documentation of this file.
00001 //===- SimplifyCFG.cpp - CFG Simplification Pass --------------------------===//
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 file implements dead code elimination and basic block merging.
00011 //
00012 // Specifically, this:
00013 //   * removes basic blocks with no predecessors
00014 //   * merges a basic block into its predecessor if there is only one and the
00015 //     predecessor only has one successor.
00016 //   * Eliminates PHI nodes for basic blocks with a single predecessor
00017 //   * Eliminates a basic block that only contains an unconditional branch
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #include "llvm/Transforms/Scalar.h"
00022 #include "llvm/Transforms/Utils/Local.h"
00023 #include "llvm/Constants.h"
00024 #include "llvm/Instructions.h"
00025 #include "llvm/Module.h"
00026 #include "llvm/Support/CFG.h"
00027 #include "llvm/Pass.h"
00028 #include "llvm/ADT/Statistic.h"
00029 #include <set>
00030 using namespace llvm;
00031 
00032 namespace {
00033   Statistic<> NumSimpl("cfgsimplify", "Number of blocks simplified");
00034 
00035   struct CFGSimplifyPass : public FunctionPass {
00036     virtual bool runOnFunction(Function &F);
00037   };
00038   RegisterOpt<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG");
00039 }
00040 
00041 // Public interface to the CFGSimplification pass
00042 FunctionPass *llvm::createCFGSimplificationPass() {
00043   return new CFGSimplifyPass();
00044 }
00045 
00046 static bool MarkAliveBlocks(BasicBlock *BB, std::set<BasicBlock*> &Reachable) {
00047   if (Reachable.count(BB)) return false;
00048   Reachable.insert(BB);
00049 
00050   // Do a quick scan of the basic block, turning any obviously unreachable
00051   // instructions into LLVM unreachable insts.  The instruction combining pass
00052   // canonnicalizes unreachable insts into stores to null or undef.
00053   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ++BBI)
00054     if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
00055       if (isa<ConstantPointerNull>(SI->getOperand(1)) ||
00056           isa<UndefValue>(SI->getOperand(1))) {
00057         // Loop over all of the successors, removing BB's entry from any PHI
00058         // nodes.
00059         for (succ_iterator I = succ_begin(BB), SE = succ_end(BB); I != SE; ++I)
00060           (*I)->removePredecessor(BB);
00061 
00062         new UnreachableInst(SI);
00063 
00064         // All instructions after this are dead.
00065         for (; BBI != E; ) {
00066           if (!BBI->use_empty())
00067             BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
00068           BB->getInstList().erase(BBI++);
00069         }
00070         break;
00071       }
00072 
00073 
00074   bool Changed = ConstantFoldTerminator(BB);
00075   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
00076     MarkAliveBlocks(*SI, Reachable);
00077 
00078   return Changed;
00079 }
00080 
00081 
00082 // It is possible that we may require multiple passes over the code to fully
00083 // simplify the CFG.
00084 //
00085 bool CFGSimplifyPass::runOnFunction(Function &F) {
00086   std::set<BasicBlock*> Reachable;
00087   bool Changed = MarkAliveBlocks(F.begin(), Reachable);
00088 
00089   // If there are unreachable blocks in the CFG...
00090   if (Reachable.size() != F.size()) {
00091     assert(Reachable.size() < F.size());
00092     NumSimpl += F.size()-Reachable.size();
00093 
00094     // Loop over all of the basic blocks that are not reachable, dropping all of
00095     // their internal references...
00096     for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB)
00097       if (!Reachable.count(BB)) {
00098         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI)
00099           if (Reachable.count(*SI))
00100             (*SI)->removePredecessor(BB);
00101         BB->dropAllReferences();
00102       }
00103 
00104     for (Function::iterator I = ++F.begin(); I != F.end();)
00105       if (!Reachable.count(I))
00106         I = F.getBasicBlockList().erase(I);
00107       else
00108         ++I;
00109 
00110     Changed = true;
00111   }
00112 
00113   bool LocalChange = true;
00114   while (LocalChange) {
00115     LocalChange = false;
00116 
00117     // Loop over all of the basic blocks (except the first one) and remove them
00118     // if they are unneeded...
00119     //
00120     for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
00121       if (SimplifyCFG(BBIt++)) {
00122         LocalChange = true;
00123         ++NumSimpl;
00124       }
00125     }
00126     Changed |= LocalChange;
00127   }
00128 
00129   return Changed;
00130 }