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 #include "llvm/Transforms/Scalar.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/Analysis/AssumptionCache.h"
  29 #include "llvm/Analysis/TargetTransformInfo.h"
  30 #include "llvm/IR/Attributes.h"
  31 #include "llvm/IR/CFG.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/CommandLine.h"
  39 #include "llvm/Transforms/Utils/Local.h"
  40 using namespace llvm;
  41
  42 #define DEBUG_TYPE "simplifycfg"
  43
  44 static cl::opt<unsigned>
  45 UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1),
  46    cl::desc("Control the number of bonus instructions (default = 1)"));
  47
  48 STATISTIC(NumSimpl, "Number of blocks simplified");
  49
  50 namespace {
  51 struct CFGSimplifyPass : public FunctionPass {
  52   static char ID; // Pass identification, replacement for typeid
  53   unsigned BonusInstThreshold;
  54   CFGSimplifyPass(int T = -1) : FunctionPass(ID) {
  55     BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T);
  56     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
  57   }
  58   bool runOnFunction(Function &F) override;
  59
  60   void getAnalysisUsage(AnalysisUsage &AU) const override {
  61     AU.addRequired<AssumptionCacheTracker>();
  62     AU.addRequired<TargetTransformInfoWrapperPass>();
  63   }
  64 };
  65 }
  66
  67 char CFGSimplifyPass::ID = 0;
  68 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
  69                       false)
  70 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
  71 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  72 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
  73                     false)
  74
  75 // Public interface to the CFGSimplification pass
  76 FunctionPass *llvm::createCFGSimplificationPass(int Threshold) {
  77   return new CFGSimplifyPass(Threshold);
  78 }
  79
  80 /// mergeEmptyReturnBlocks - If we have more than one empty (other than phi
  81 /// node) return blocks, merge them together to promote recursive block merging.
  82 static bool mergeEmptyReturnBlocks(Function &F) {
  83   bool Changed = false;
  84
  85   BasicBlock *RetBlock = nullptr;
  86
  87   // Scan all the blocks in the function, looking for empty return blocks.
  88   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
  89     BasicBlock &BB = *BBI++;
  90
  91     // Only look at return blocks.
  92     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
  93     if (!Ret) continue;
  94
  95     // Only look at the block if it is empty or the only other thing in it is a
  96     // single PHI node that is the operand to the return.
  97     if (Ret != &BB.front()) {
  98       // Check for something else in the block.
  99       BasicBlock::iterator I = Ret;
 100       --I;
 101       // Skip over debug info.
 102       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
 103         --I;
 104       if (!isa<DbgInfoIntrinsic>(I) &&
 105           (!isa<PHINode>(I) || I != BB.begin() ||
 106            Ret->getNumOperands() == 0 ||
 107            Ret->getOperand(0) != I))
 108         continue;
 109     }
 110
 111     // If this is the first returning block, remember it and keep going.
 112     if (!RetBlock) {
 113       RetBlock = &BB;
 114       continue;
 115     }
 116
 117     // Otherwise, we found a duplicate return block.  Merge the two.
 118     Changed = true;
 119
 120     // Case when there is no input to the return or when the returned values
 121     // agree is trivial.  Note that they can't agree if there are phis in the
 122     // blocks.
 123     if (Ret->getNumOperands() == 0 ||
 124         Ret->getOperand(0) ==
 125           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
 126       BB.replaceAllUsesWith(RetBlock);
 127       BB.eraseFromParent();
 128       continue;
 129     }
 130
 131     // If the canonical return block has no PHI node, create one now.
 132     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
 133     if (!RetBlockPHI) {
 134       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
 135       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
 136       RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
 137                                     std::distance(PB, PE), "merge",
 138                                     &RetBlock->front());
 139
 140       for (pred_iterator PI = PB; PI != PE; ++PI)
 141         RetBlockPHI->addIncoming(InVal, *PI);
 142       RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
 143     }
 144
 145     // Turn BB into a block that just unconditionally branches to the return
 146     // block.  This handles the case when the two return blocks have a common
 147     // predecessor but that return different things.
 148     RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
 149     BB.getTerminator()->eraseFromParent();
 150     BranchInst::Create(RetBlock, &BB);
 151   }
 152
 153   return Changed;
 154 }
 155
 156 /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
 157 /// iterating until no more changes are made.
 158 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
 159                                    const DataLayout *DL, AssumptionCache *AC,
 160                                    unsigned BonusInstThreshold) {
 161   bool Changed = false;
 162   bool LocalChange = true;
 163   while (LocalChange) {
 164     LocalChange = false;
 165
 166     // Loop over all of the basic blocks and remove them if they are unneeded...
 167     //
 168     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
 169       if (SimplifyCFG(BBIt++, TTI, BonusInstThreshold, DL, AC)) {
 170         LocalChange = true;
 171         ++NumSimpl;
 172       }
 173     }
 174     Changed |= LocalChange;
 175   }
 176   return Changed;
 177 }
 178
 179 // It is possible that we may require multiple passes over the code to fully
 180 // simplify the CFG.
 181 //
 182 bool CFGSimplifyPass::runOnFunction(Function &F) {
 183   if (skipOptnoneFunction(F))
 184     return false;
 185
 186   AssumptionCache *AC =
 187       &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 188   const TargetTransformInfo &TTI =
 189       getAnalysis<TargetTransformInfoWrapperPass>().getTTI();
 190   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
 191   const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr;
 192   bool EverChanged = removeUnreachableBlocks(F);
 193   EverChanged |= mergeEmptyReturnBlocks(F);
 194   EverChanged |= iterativelySimplifyCFG(F, TTI, DL, AC, BonusInstThreshold);
 195
 196   // If neither pass changed anything, we're done.
 197   if (!EverChanged) return false;
 198
 199   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
 200   // removeUnreachableBlocks is needed to nuke them, which means we should
 201   // iterate between the two optimizations.  We structure the code like this to
 202   // avoid reruning iterativelySimplifyCFG if the second pass of
 203   // removeUnreachableBlocks doesn't do anything.
 204   if (!removeUnreachableBlocks(F))
 205     return true;
 206
 207   do {
 208     EverChanged = iterativelySimplifyCFG(F, TTI, DL, AC, BonusInstThreshold);
 209     EverChanged |= removeUnreachableBlocks(F);
 210   } while (EverChanged);
 211
 212   return true;
 213 }