LLVM  mainline
SimplifyCFGPass.cpp
Go to the documentation of this file.
00001 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements dead code elimination and basic block merging, along
00011 // with a collection of other peephole control flow optimizations.  For example:
00012 //
00013 //   * Removes basic blocks with no predecessors.
00014 //   * Merges a basic block into its predecessor if there is only one and the
00015 //     predecessor only has one successor.
00016 //   * Eliminates PHI nodes for basic blocks with a single predecessor.
00017 //   * Eliminates a basic block that only contains an unconditional branch.
00018 //   * Changes invoke instructions to nounwind functions to be calls.
00019 //   * Change things like "if (x) if (y)" into "if (x&y)".
00020 //   * etc..
00021 //
00022 //===----------------------------------------------------------------------===//
00023 
00024 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
00025 #include "llvm/ADT/SmallPtrSet.h"
00026 #include "llvm/ADT/SmallVector.h"
00027 #include "llvm/ADT/Statistic.h"
00028 #include "llvm/Analysis/AssumptionCache.h"
00029 #include "llvm/Analysis/TargetTransformInfo.h"
00030 #include "llvm/IR/Attributes.h"
00031 #include "llvm/IR/CFG.h"
00032 #include "llvm/IR/Constants.h"
00033 #include "llvm/IR/DataLayout.h"
00034 #include "llvm/IR/Instructions.h"
00035 #include "llvm/IR/IntrinsicInst.h"
00036 #include "llvm/IR/Module.h"
00037 #include "llvm/Pass.h"
00038 #include "llvm/Support/CommandLine.h"
00039 #include "llvm/Transforms/Utils/Local.h"
00040 #include "llvm/Transforms/Scalar.h"
00041 using namespace llvm;
00042 
00043 #define DEBUG_TYPE "simplifycfg"
00044 
00045 static cl::opt<unsigned>
00046 UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1),
00047    cl::desc("Control the number of bonus instructions (default = 1)"));
00048 
00049 STATISTIC(NumSimpl, "Number of blocks simplified");
00050 
00051 /// mergeEmptyReturnBlocks - If we have more than one empty (other than phi
00052 /// node) return blocks, merge them together to promote recursive block merging.
00053 static bool mergeEmptyReturnBlocks(Function &F) {
00054   bool Changed = false;
00055 
00056   BasicBlock *RetBlock = nullptr;
00057 
00058   // Scan all the blocks in the function, looking for empty return blocks.
00059   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
00060     BasicBlock &BB = *BBI++;
00061 
00062     // Only look at return blocks.
00063     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
00064     if (!Ret) continue;
00065 
00066     // Only look at the block if it is empty or the only other thing in it is a
00067     // single PHI node that is the operand to the return.
00068     if (Ret != &BB.front()) {
00069       // Check for something else in the block.
00070       BasicBlock::iterator I = Ret;
00071       --I;
00072       // Skip over debug info.
00073       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
00074         --I;
00075       if (!isa<DbgInfoIntrinsic>(I) &&
00076           (!isa<PHINode>(I) || I != BB.begin() ||
00077            Ret->getNumOperands() == 0 ||
00078            Ret->getOperand(0) != I))
00079         continue;
00080     }
00081 
00082     // If this is the first returning block, remember it and keep going.
00083     if (!RetBlock) {
00084       RetBlock = &BB;
00085       continue;
00086     }
00087 
00088     // Otherwise, we found a duplicate return block.  Merge the two.
00089     Changed = true;
00090 
00091     // Case when there is no input to the return or when the returned values
00092     // agree is trivial.  Note that they can't agree if there are phis in the
00093     // blocks.
00094     if (Ret->getNumOperands() == 0 ||
00095         Ret->getOperand(0) ==
00096           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
00097       BB.replaceAllUsesWith(RetBlock);
00098       BB.eraseFromParent();
00099       continue;
00100     }
00101 
00102     // If the canonical return block has no PHI node, create one now.
00103     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
00104     if (!RetBlockPHI) {
00105       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
00106       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
00107       RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
00108                                     std::distance(PB, PE), "merge",
00109                                     &RetBlock->front());
00110 
00111       for (pred_iterator PI = PB; PI != PE; ++PI)
00112         RetBlockPHI->addIncoming(InVal, *PI);
00113       RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
00114     }
00115 
00116     // Turn BB into a block that just unconditionally branches to the return
00117     // block.  This handles the case when the two return blocks have a common
00118     // predecessor but that return different things.
00119     RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
00120     BB.getTerminator()->eraseFromParent();
00121     BranchInst::Create(RetBlock, &BB);
00122   }
00123 
00124   return Changed;
00125 }
00126 
00127 /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
00128 /// iterating until no more changes are made.
00129 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
00130                                    AssumptionCache *AC,
00131                                    unsigned BonusInstThreshold) {
00132   bool Changed = false;
00133   bool LocalChange = true;
00134   while (LocalChange) {
00135     LocalChange = false;
00136 
00137     // Loop over all of the basic blocks and remove them if they are unneeded...
00138     //
00139     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
00140       if (SimplifyCFG(BBIt++, TTI, BonusInstThreshold, AC)) {
00141         LocalChange = true;
00142         ++NumSimpl;
00143       }
00144     }
00145     Changed |= LocalChange;
00146   }
00147   return Changed;
00148 }
00149 
00150 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
00151                                 AssumptionCache *AC, int BonusInstThreshold) {
00152   bool EverChanged = removeUnreachableBlocks(F);
00153   EverChanged |= mergeEmptyReturnBlocks(F);
00154   EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
00155 
00156   // If neither pass changed anything, we're done.
00157   if (!EverChanged) return false;
00158 
00159   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
00160   // removeUnreachableBlocks is needed to nuke them, which means we should
00161   // iterate between the two optimizations.  We structure the code like this to
00162   // avoid reruning iterativelySimplifyCFG if the second pass of
00163   // removeUnreachableBlocks doesn't do anything.
00164   if (!removeUnreachableBlocks(F))
00165     return true;
00166 
00167   do {
00168     EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
00169     EverChanged |= removeUnreachableBlocks(F);
00170   } while (EverChanged);
00171 
00172   return true;
00173 }
00174 
00175 SimplifyCFGPass::SimplifyCFGPass()
00176     : BonusInstThreshold(UserBonusInstThreshold) {}
00177 
00178 SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold)
00179     : BonusInstThreshold(BonusInstThreshold) {}
00180 
00181 PreservedAnalyses SimplifyCFGPass::run(Function &F,
00182                                        AnalysisManager<Function> *AM) {
00183   auto &TTI = AM->getResult<TargetIRAnalysis>(F);
00184   auto &AC = AM->getResult<AssumptionAnalysis>(F);
00185 
00186   if (!simplifyFunctionCFG(F, TTI, &AC, BonusInstThreshold))
00187     return PreservedAnalyses::none();
00188 
00189   return PreservedAnalyses::all();
00190 }
00191 
00192 namespace {
00193 struct CFGSimplifyPass : public FunctionPass {
00194   static char ID; // Pass identification, replacement for typeid
00195   unsigned BonusInstThreshold;
00196   CFGSimplifyPass(int T = -1) : FunctionPass(ID) {
00197     BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T);
00198     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
00199   }
00200   bool runOnFunction(Function &F) override {
00201     if (skipOptnoneFunction(F))
00202       return false;
00203 
00204     AssumptionCache *AC =
00205         &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
00206     const TargetTransformInfo &TTI =
00207         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
00208     return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold);
00209   }
00210 
00211   void getAnalysisUsage(AnalysisUsage &AU) const override {
00212     AU.addRequired<AssumptionCacheTracker>();
00213     AU.addRequired<TargetTransformInfoWrapperPass>();
00214   }
00215 };
00216 }
00217 
00218 char CFGSimplifyPass::ID = 0;
00219 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
00220                       false)
00221 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
00222 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
00223 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
00224                     false)
00225 
00226 // Public interface to the CFGSimplification pass
00227 FunctionPass *llvm::createCFGSimplificationPass(int Threshold) {
00228   return new CFGSimplifyPass(Threshold);
00229 }
00230