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/GlobalsModRef.h"
     29 #include "llvm/Analysis/AssumptionCache.h"
     30 #include "llvm/Analysis/TargetTransformInfo.h"
     31 #include "llvm/IR/Attributes.h"
     32 #include "llvm/IR/CFG.h"
     33 #include "llvm/IR/Constants.h"
     34 #include "llvm/IR/DataLayout.h"
     35 #include "llvm/IR/Instructions.h"
     36 #include "llvm/IR/IntrinsicInst.h"
     37 #include "llvm/IR/Module.h"
     38 #include "llvm/Pass.h"
     39 #include "llvm/Support/CommandLine.h"
     40 #include "llvm/Transforms/Utils/Local.h"
     41 #include "llvm/Transforms/Scalar.h"
     42 using namespace llvm;
     43 
     44 #define DEBUG_TYPE "simplifycfg"
     45 
     46 static cl::opt<unsigned>
     47 UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1),
     48    cl::desc("Control the number of bonus instructions (default = 1)"));
     49 
     50 STATISTIC(NumSimpl, "Number of blocks simplified");
     51 
     52 /// If we have more than one empty (other than phi node) return blocks,
     53 /// merge them together to promote recursive block merging.
     54 static bool mergeEmptyReturnBlocks(Function &F) {
     55   bool Changed = false;
     56 
     57   BasicBlock *RetBlock = nullptr;
     58 
     59   // Scan all the blocks in the function, looking for empty return blocks.
     60   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
     61     BasicBlock &BB = *BBI++;
     62 
     63     // Only look at return blocks.
     64     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
     65     if (!Ret) continue;
     66 
     67     // Only look at the block if it is empty or the only other thing in it is a
     68     // single PHI node that is the operand to the return.
     69     if (Ret != &BB.front()) {
     70       // Check for something else in the block.
     71       BasicBlock::iterator I(Ret);
     72       --I;
     73       // Skip over debug info.
     74       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
     75         --I;
     76       if (!isa<DbgInfoIntrinsic>(I) &&
     77           (!isa<PHINode>(I) || I != BB.begin() || 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 /// 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     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
    139       if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC)) {
    140         LocalChange = true;
    141         ++NumSimpl;
    142       }
    143     }
    144     Changed |= LocalChange;
    145   }
    146   return Changed;
    147 }
    148 
    149 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
    150                                 AssumptionCache *AC, int BonusInstThreshold) {
    151   bool EverChanged = removeUnreachableBlocks(F);
    152   EverChanged |= mergeEmptyReturnBlocks(F);
    153   EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
    154 
    155   // If neither pass changed anything, we're done.
    156   if (!EverChanged) return false;
    157 
    158   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
    159   // removeUnreachableBlocks is needed to nuke them, which means we should
    160   // iterate between the two optimizations.  We structure the code like this to
    161   // avoid rerunning iterativelySimplifyCFG if the second pass of
    162   // removeUnreachableBlocks doesn't do anything.
    163   if (!removeUnreachableBlocks(F))
    164     return true;
    165 
    166   do {
    167     EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
    168     EverChanged |= removeUnreachableBlocks(F);
    169   } while (EverChanged);
    170 
    171   return true;
    172 }
    173 
    174 SimplifyCFGPass::SimplifyCFGPass()
    175     : BonusInstThreshold(UserBonusInstThreshold) {}
    176 
    177 SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold)
    178     : BonusInstThreshold(BonusInstThreshold) {}
    179 
    180 PreservedAnalyses SimplifyCFGPass::run(Function &F,
    181                                        AnalysisManager<Function> *AM) {
    182   auto &TTI = AM->getResult<TargetIRAnalysis>(F);
    183   auto &AC = AM->getResult<AssumptionAnalysis>(F);
    184 
    185   if (!simplifyFunctionCFG(F, TTI, &AC, BonusInstThreshold))
    186     return PreservedAnalyses::none();
    187 
    188   return PreservedAnalyses::all();
    189 }
    190 
    191 namespace {
    192 struct CFGSimplifyPass : public FunctionPass {
    193   static char ID; // Pass identification, replacement for typeid
    194   unsigned BonusInstThreshold;
    195   std::function<bool(const Function &)> PredicateFtor;
    196 
    197   CFGSimplifyPass(int T = -1,
    198                   std::function<bool(const Function &)> Ftor = nullptr)
    199       : FunctionPass(ID), PredicateFtor(Ftor) {
    200     BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T);
    201     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
    202   }
    203   bool runOnFunction(Function &F) override {
    204     if (PredicateFtor && !PredicateFtor(F))
    205       return false;
    206 
    207     if (skipOptnoneFunction(F))
    208       return false;
    209 
    210     AssumptionCache *AC =
    211         &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
    212     const TargetTransformInfo &TTI =
    213         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
    214     return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold);
    215   }
    216 
    217   void getAnalysisUsage(AnalysisUsage &AU) const override {
    218     AU.addRequired<AssumptionCacheTracker>();
    219     AU.addRequired<TargetTransformInfoWrapperPass>();
    220     AU.addPreserved<GlobalsAAWrapperPass>();
    221   }
    222 };
    223 }
    224 
    225 char CFGSimplifyPass::ID = 0;
    226 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
    227                       false)
    228 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
    229 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
    230 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
    231                     false)
    232 
    233 // Public interface to the CFGSimplification pass
    234 FunctionPass *
    235 llvm::createCFGSimplificationPass(int Threshold,
    236                                   std::function<bool(const Function &)> Ftor) {
    237   return new CFGSimplifyPass(Threshold, Ftor);
    238 }
    239 
    240