Home | History | Annotate | Download | only in Scalar 
      1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements dead code elimination and basic block merging, along
     11 // with a collection of other peephole control flow optimizations.  For example:
     12 //
     13 //   * Removes basic blocks with no predecessors.
     14 //   * Merges a basic block into its predecessor if there is only one and the
     15 //     predecessor only has one successor.
     16 //   * Eliminates PHI nodes for basic blocks with a single predecessor.
     17 //   * Eliminates a basic block that only contains an unconditional branch.
     18 //   * Changes invoke instructions to nounwind functions to be calls.
     19 //   * Change things like "if (x) if (y)" into "if (x&y)".
     20 //   * etc..
     21 //
     22 //===----------------------------------------------------------------------===//
     23 
     24 #define DEBUG_TYPE "simplifycfg"
     25 #include "llvm/Transforms/Scalar.h"
     26 #include "llvm/ADT/SmallPtrSet.h"
     27 #include "llvm/ADT/SmallVector.h"
     28 #include "llvm/ADT/Statistic.h"
     29 #include "llvm/Analysis/TargetTransformInfo.h"
     30 #include "llvm/IR/Attributes.h"
     31 #include "llvm/IR/Constants.h"
     32 #include "llvm/IR/DataLayout.h"
     33 #include "llvm/IR/Instructions.h"
     34 #include "llvm/IR/IntrinsicInst.h"
     35 #include "llvm/IR/Module.h"
     36 #include "llvm/Pass.h"
     37 #include "llvm/Support/CFG.h"
     38 #include "llvm/Transforms/Utils/Local.h"
     39 using namespace llvm;
     40 
     41 STATISTIC(NumSimpl, "Number of blocks simplified");
     42 
     43 namespace {
     44   struct CFGSimplifyPass : public FunctionPass {
     45     static char ID; // Pass identification, replacement for typeid
     46     CFGSimplifyPass() : FunctionPass(ID) {
     47       initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
     48     }
     49 
     50     virtual bool runOnFunction(Function &F);
     51 
     52     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     53       AU.addRequired<TargetTransformInfo>();
     54     }
     55   };
     56 }
     57 
     58 char CFGSimplifyPass::ID = 0;
     59 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG",
     60                       false, false)
     61 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
     62 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG",
     63                     false, false)
     64 
     65 // Public interface to the CFGSimplification pass
     66 FunctionPass *llvm::createCFGSimplificationPass() {
     67   return new CFGSimplifyPass();
     68 }
     69 
     70 /// changeToUnreachable - Insert an unreachable instruction before the specified
     71 /// instruction, making it and the rest of the code in the block dead.
     72 static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) {
     73   BasicBlock *BB = I->getParent();
     74   // Loop over all of the successors, removing BB's entry from any PHI
     75   // nodes.
     76   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
     77     (*SI)->removePredecessor(BB);
     78 
     79   // Insert a call to llvm.trap right before this.  This turns the undefined
     80   // behavior into a hard fail instead of falling through into random code.
     81   if (UseLLVMTrap) {
     82     Function *TrapFn =
     83       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
     84     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
     85     CallTrap->setDebugLoc(I->getDebugLoc());
     86   }
     87   new UnreachableInst(I->getContext(), I);
     88 
     89   // All instructions after this are dead.
     90   BasicBlock::iterator BBI = I, BBE = BB->end();
     91   while (BBI != BBE) {
     92     if (!BBI->use_empty())
     93       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
     94     BB->getInstList().erase(BBI++);
     95   }
     96 }
     97 
     98 /// changeToCall - Convert the specified invoke into a normal call.
     99 static void changeToCall(InvokeInst *II) {
    100   SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
    101   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II);
    102   NewCall->takeName(II);
    103   NewCall->setCallingConv(II->getCallingConv());
    104   NewCall->setAttributes(II->getAttributes());
    105   NewCall->setDebugLoc(II->getDebugLoc());
    106   II->replaceAllUsesWith(NewCall);
    107 
    108   // Follow the call by a branch to the normal destination.
    109   BranchInst::Create(II->getNormalDest(), II);
    110 
    111   // Update PHI nodes in the unwind destination
    112   II->getUnwindDest()->removePredecessor(II->getParent());
    113   II->eraseFromParent();
    114 }
    115 
    116 static bool markAliveBlocks(BasicBlock *BB,
    117                             SmallPtrSet<BasicBlock*, 128> &Reachable) {
    118 
    119   SmallVector<BasicBlock*, 128> Worklist;
    120   Worklist.push_back(BB);
    121   Reachable.insert(BB);
    122   bool Changed = false;
    123   do {
    124     BB = Worklist.pop_back_val();
    125 
    126     // Do a quick scan of the basic block, turning any obviously unreachable
    127     // instructions into LLVM unreachable insts.  The instruction combining pass
    128     // canonicalizes unreachable insts into stores to null or undef.
    129     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
    130       if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
    131         if (CI->doesNotReturn()) {
    132           // If we found a call to a no-return function, insert an unreachable
    133           // instruction after it.  Make sure there isn't *already* one there
    134           // though.
    135           ++BBI;
    136           if (!isa<UnreachableInst>(BBI)) {
    137             // Don't insert a call to llvm.trap right before the unreachable.
    138             changeToUnreachable(BBI, false);
    139             Changed = true;
    140           }
    141           break;
    142         }
    143       }
    144 
    145       // Store to undef and store to null are undefined and used to signal that
    146       // they should be changed to unreachable by passes that can't modify the
    147       // CFG.
    148       if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
    149         // Don't touch volatile stores.
    150         if (SI->isVolatile()) continue;
    151 
    152         Value *Ptr = SI->getOperand(1);
    153 
    154         if (isa<UndefValue>(Ptr) ||
    155             (isa<ConstantPointerNull>(Ptr) &&
    156              SI->getPointerAddressSpace() == 0)) {
    157           changeToUnreachable(SI, true);
    158           Changed = true;
    159           break;
    160         }
    161       }
    162     }
    163 
    164     // Turn invokes that call 'nounwind' functions into ordinary calls.
    165     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
    166       Value *Callee = II->getCalledValue();
    167       if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
    168         changeToUnreachable(II, true);
    169         Changed = true;
    170       } else if (II->doesNotThrow()) {
    171         if (II->use_empty() && II->onlyReadsMemory()) {
    172           // jump to the normal destination branch.
    173           BranchInst::Create(II->getNormalDest(), II);
    174           II->getUnwindDest()->removePredecessor(II->getParent());
    175           II->eraseFromParent();
    176         } else
    177           changeToCall(II);
    178         Changed = true;
    179       }
    180     }
    181 
    182     Changed |= ConstantFoldTerminator(BB, true);
    183     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
    184       if (Reachable.insert(*SI))
    185         Worklist.push_back(*SI);
    186   } while (!Worklist.empty());
    187   return Changed;
    188 }
    189 
    190 /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even
    191 /// if they are in a dead cycle.  Return true if a change was made, false
    192 /// otherwise.
    193 static bool removeUnreachableBlocksFromFn(Function &F) {
    194   SmallPtrSet<BasicBlock*, 128> Reachable;
    195   bool Changed = markAliveBlocks(F.begin(), Reachable);
    196 
    197   // If there are unreachable blocks in the CFG...
    198   if (Reachable.size() == F.size())
    199     return Changed;
    200 
    201   assert(Reachable.size() < F.size());
    202   NumSimpl += F.size()-Reachable.size();
    203 
    204   // Loop over all of the basic blocks that are not reachable, dropping all of
    205   // their internal references...
    206   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
    207     if (Reachable.count(BB))
    208       continue;
    209 
    210     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
    211       if (Reachable.count(*SI))
    212         (*SI)->removePredecessor(BB);
    213     BB->dropAllReferences();
    214   }
    215 
    216   for (Function::iterator I = ++F.begin(); I != F.end();)
    217     if (!Reachable.count(I))
    218       I = F.getBasicBlockList().erase(I);
    219     else
    220       ++I;
    221 
    222   return true;
    223 }
    224 
    225 /// mergeEmptyReturnBlocks - If we have more than one empty (other than phi
    226 /// node) return blocks, merge them together to promote recursive block merging.
    227 static bool mergeEmptyReturnBlocks(Function &F) {
    228   bool Changed = false;
    229 
    230   BasicBlock *RetBlock = 0;
    231 
    232   // Scan all the blocks in the function, looking for empty return blocks.
    233   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
    234     BasicBlock &BB = *BBI++;
    235 
    236     // Only look at return blocks.
    237     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
    238     if (Ret == 0) continue;
    239 
    240     // Only look at the block if it is empty or the only other thing in it is a
    241     // single PHI node that is the operand to the return.
    242     if (Ret != &BB.front()) {
    243       // Check for something else in the block.
    244       BasicBlock::iterator I = Ret;
    245       --I;
    246       // Skip over debug info.
    247       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
    248         --I;
    249       if (!isa<DbgInfoIntrinsic>(I) &&
    250           (!isa<PHINode>(I) || I != BB.begin() ||
    251            Ret->getNumOperands() == 0 ||
    252            Ret->getOperand(0) != I))
    253         continue;
    254     }
    255 
    256     // If this is the first returning block, remember it and keep going.
    257     if (RetBlock == 0) {
    258       RetBlock = &BB;
    259       continue;
    260     }
    261 
    262     // Otherwise, we found a duplicate return block.  Merge the two.
    263     Changed = true;
    264 
    265     // Case when there is no input to the return or when the returned values
    266     // agree is trivial.  Note that they can't agree if there are phis in the
    267     // blocks.
    268     if (Ret->getNumOperands() == 0 ||
    269         Ret->getOperand(0) ==
    270           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
    271       BB.replaceAllUsesWith(RetBlock);
    272       BB.eraseFromParent();
    273       continue;
    274     }
    275 
    276     // If the canonical return block has no PHI node, create one now.
    277     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
    278     if (RetBlockPHI == 0) {
    279       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
    280       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
    281       RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
    282                                     std::distance(PB, PE), "merge",
    283                                     &RetBlock->front());
    284 
    285       for (pred_iterator PI = PB; PI != PE; ++PI)
    286         RetBlockPHI->addIncoming(InVal, *PI);
    287       RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
    288     }
    289 
    290     // Turn BB into a block that just unconditionally branches to the return
    291     // block.  This handles the case when the two return blocks have a common
    292     // predecessor but that return different things.
    293     RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
    294     BB.getTerminator()->eraseFromParent();
    295     BranchInst::Create(RetBlock, &BB);
    296   }
    297 
    298   return Changed;
    299 }
    300 
    301 /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
    302 /// iterating until no more changes are made.
    303 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
    304                                    const DataLayout *TD) {
    305   bool Changed = false;
    306   bool LocalChange = true;
    307   while (LocalChange) {
    308     LocalChange = false;
    309 
    310     // Loop over all of the basic blocks and remove them if they are unneeded...
    311     //
    312     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
    313       if (SimplifyCFG(BBIt++, TTI, TD)) {
    314         LocalChange = true;
    315         ++NumSimpl;
    316       }
    317     }
    318     Changed |= LocalChange;
    319   }
    320   return Changed;
    321 }
    322 
    323 // It is possible that we may require multiple passes over the code to fully
    324 // simplify the CFG.
    325 //
    326 bool CFGSimplifyPass::runOnFunction(Function &F) {
    327   const TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
    328   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
    329   bool EverChanged = removeUnreachableBlocksFromFn(F);
    330   EverChanged |= mergeEmptyReturnBlocks(F);
    331   EverChanged |= iterativelySimplifyCFG(F, TTI, TD);
    332 
    333   // If neither pass changed anything, we're done.
    334   if (!EverChanged) return false;
    335 
    336   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
    337   // removeUnreachableBlocksFromFn is needed to nuke them, which means we should
    338   // iterate between the two optimizations.  We structure the code like this to
    339   // avoid reruning iterativelySimplifyCFG if the second pass of
    340   // removeUnreachableBlocksFromFn doesn't do anything.
    341   if (!removeUnreachableBlocksFromFn(F))
    342     return true;
    343 
    344   do {
    345     EverChanged = iterativelySimplifyCFG(F, TTI, TD);
    346     EverChanged |= removeUnreachableBlocksFromFn(F);
    347   } while (EverChanged);
    348 
    349   return true;
    350 }
    351