lib/Transforms/Scalar/SimplifyCFGPass.cpp

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