LLVM API Documentation

SimplifyCFGPass.cpp

Go to the documentation of this file.
00001 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements dead code elimination and basic block merging, along
00011 // with a collection of other peephole control flow optimizations.  For example:
00012 //
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 //   * Changes invoke instructions to nounwind functions to be calls.
00019 //   * Change things like "if (x) if (y)" into "if (x&y)".
00020 //   * etc..
00021 //
00022 //===----------------------------------------------------------------------===//
00023 
00024 #define DEBUG_TYPE "simplifycfg"
00025 #include "llvm/Transforms/Scalar.h"
00026 #include "llvm/Transforms/Utils/Local.h"
00027 #include "llvm/Constants.h"
00028 #include "llvm/Instructions.h"
00029 #include "llvm/LLVMContext.h"
00030 #include "llvm/Module.h"
00031 #include "llvm/Attributes.h"
00032 #include "llvm/Support/CFG.h"
00033 #include "llvm/Support/Compiler.h"
00034 #include "llvm/Pass.h"
00035 #include "llvm/ADT/SmallVector.h"
00036 #include "llvm/ADT/SmallPtrSet.h"
00037 #include "llvm/ADT/Statistic.h"
00038 using namespace llvm;
00039 
00040 STATISTIC(NumSimpl, "Number of blocks simplified");
00041 
00042 namespace {
00043   struct VISIBILITY_HIDDEN CFGSimplifyPass : public FunctionPass {
00044     static char ID; // Pass identification, replacement for typeid
00045     CFGSimplifyPass() : FunctionPass(&ID) {}
00046 
00047     virtual bool runOnFunction(Function &F);
00048   };
00049 }
00050 
00051 char CFGSimplifyPass::ID = 0;
00052 static RegisterPass<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG");
00053 
00054 // Public interface to the CFGSimplification pass
00055 FunctionPass *llvm::createCFGSimplificationPass() {
00056   return new CFGSimplifyPass();
00057 }
00058 
00059 /// ChangeToUnreachable - Insert an unreachable instruction before the specified
00060 /// instruction, making it and the rest of the code in the block dead.
00061 static void ChangeToUnreachable(Instruction *I, LLVMContext &Context) {
00062   BasicBlock *BB = I->getParent();
00063   // Loop over all of the successors, removing BB's entry from any PHI
00064   // nodes.
00065   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
00066     (*SI)->removePredecessor(BB);
00067   
00068   new UnreachableInst(I->getContext(), I);
00069   
00070   // All instructions after this are dead.
00071   BasicBlock::iterator BBI = I, BBE = BB->end();
00072   while (BBI != BBE) {
00073     if (!BBI->use_empty())
00074       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
00075     BB->getInstList().erase(BBI++);
00076   }
00077 }
00078 
00079 /// ChangeToCall - Convert the specified invoke into a normal call.
00080 static void ChangeToCall(InvokeInst *II) {
00081   BasicBlock *BB = II->getParent();
00082   SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
00083   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(),
00084                                        Args.end(), "", II);
00085   NewCall->takeName(II);
00086   NewCall->setCallingConv(II->getCallingConv());
00087   NewCall->setAttributes(II->getAttributes());
00088   II->replaceAllUsesWith(NewCall);
00089 
00090   // Follow the call by a branch to the normal destination.
00091   BranchInst::Create(II->getNormalDest(), II);
00092 
00093   // Update PHI nodes in the unwind destination
00094   II->getUnwindDest()->removePredecessor(BB);
00095   BB->getInstList().erase(II);
00096 }
00097 
00098 static bool MarkAliveBlocks(BasicBlock *BB,
00099                             SmallPtrSet<BasicBlock*, 128> &Reachable,
00100                             LLVMContext &Context) {
00101   
00102   SmallVector<BasicBlock*, 128> Worklist;
00103   Worklist.push_back(BB);
00104   bool Changed = false;
00105   while (!Worklist.empty()) {
00106     BB = Worklist.back();
00107     Worklist.pop_back();
00108     
00109     if (!Reachable.insert(BB))
00110       continue;
00111 
00112     // Do a quick scan of the basic block, turning any obviously unreachable
00113     // instructions into LLVM unreachable insts.  The instruction combining pass
00114     // canonicalizes unreachable insts into stores to null or undef.
00115     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
00116       if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
00117         if (CI->doesNotReturn()) {
00118           // If we found a call to a no-return function, insert an unreachable
00119           // instruction after it.  Make sure there isn't *already* one there
00120           // though.
00121           ++BBI;
00122           if (!isa<UnreachableInst>(BBI)) {
00123             ChangeToUnreachable(BBI, Context);
00124             Changed = true;
00125           }
00126           break;
00127         }
00128       }
00129       
00130       if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
00131         Value *Ptr = SI->getOperand(1);
00132         
00133         if (isa<UndefValue>(Ptr) ||
00134             (isa<ConstantPointerNull>(Ptr) &&
00135              cast<PointerType>(Ptr->getType())->getAddressSpace() == 0)) {
00136           ChangeToUnreachable(SI, Context);
00137           Changed = true;
00138           break;
00139         }
00140       }
00141     }
00142 
00143     // Turn invokes that call 'nounwind' functions into ordinary calls.
00144     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
00145       if (II->doesNotThrow()) {
00146         ChangeToCall(II);
00147         Changed = true;
00148       }
00149 
00150     Changed |= ConstantFoldTerminator(BB);
00151     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
00152       Worklist.push_back(*SI);
00153   }
00154   return Changed;
00155 }
00156 
00157 /// RemoveUnreachableBlocksFromFn - Remove blocks that are not reachable, even 
00158 /// if they are in a dead cycle.  Return true if a change was made, false 
00159 /// otherwise.
00160 static bool RemoveUnreachableBlocksFromFn(Function &F) {
00161   SmallPtrSet<BasicBlock*, 128> Reachable;
00162   bool Changed = MarkAliveBlocks(F.begin(), Reachable, F.getContext());
00163   
00164   // If there are unreachable blocks in the CFG...
00165   if (Reachable.size() == F.size())
00166     return Changed;
00167   
00168   assert(Reachable.size() < F.size());
00169   NumSimpl += F.size()-Reachable.size();
00170   
00171   // Loop over all of the basic blocks that are not reachable, dropping all of
00172   // their internal references...
00173   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
00174     if (Reachable.count(BB))
00175       continue;
00176     
00177     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
00178       if (Reachable.count(*SI))
00179         (*SI)->removePredecessor(BB);
00180     BB->dropAllReferences();
00181   }
00182   
00183   for (Function::iterator I = ++F.begin(); I != F.end();)
00184     if (!Reachable.count(I))
00185       I = F.getBasicBlockList().erase(I);
00186     else
00187       ++I;
00188   
00189   return true;
00190 }
00191 
00192 /// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function,
00193 /// iterating until no more changes are made.
00194 static bool IterativeSimplifyCFG(Function &F) {
00195   bool Changed = false;
00196   bool LocalChange = true;
00197   while (LocalChange) {
00198     LocalChange = false;
00199     
00200     // Loop over all of the basic blocks (except the first one) and remove them
00201     // if they are unneeded...
00202     //
00203     for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
00204       if (SimplifyCFG(BBIt++)) {
00205         LocalChange = true;
00206         ++NumSimpl;
00207       }
00208     }
00209     Changed |= LocalChange;
00210   }
00211   return Changed;
00212 }
00213 
00214 // It is possible that we may require multiple passes over the code to fully
00215 // simplify the CFG.
00216 //
00217 bool CFGSimplifyPass::runOnFunction(Function &F) {
00218   bool EverChanged = RemoveUnreachableBlocksFromFn(F);
00219   EverChanged |= IterativeSimplifyCFG(F);
00220   
00221   // If neither pass changed anything, we're done.
00222   if (!EverChanged) return false;
00223 
00224   // IterativeSimplifyCFG can (rarely) make some loops dead.  If this happens,
00225   // RemoveUnreachableBlocksFromFn is needed to nuke them, which means we should
00226   // iterate between the two optimizations.  We structure the code like this to
00227   // avoid reruning IterativeSimplifyCFG if the second pass of 
00228   // RemoveUnreachableBlocksFromFn doesn't do anything.
00229   if (!RemoveUnreachableBlocksFromFn(F))
00230     return true;
00231   
00232   do {
00233     EverChanged = IterativeSimplifyCFG(F);
00234     EverChanged |= RemoveUnreachableBlocksFromFn(F);
00235   } while (EverChanged);
00236   
00237   return true;
00238 }