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