SimplifyCFGPass.cpp revision 6948897e478cbd66626159776a8017b3c18579b9
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" 41using namespace llvm; 42 43#define DEBUG_TYPE "simplifycfg" 44 45static cl::opt<unsigned> 46UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1), 47 cl::desc("Control the number of bonus instructions (default = 1)")); 48 49STATISTIC(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. 53static 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. 129static 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 150static 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 175SimplifyCFGPass::SimplifyCFGPass() 176 : BonusInstThreshold(UserBonusInstThreshold) {} 177 178SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold) 179 : BonusInstThreshold(BonusInstThreshold) {} 180 181PreservedAnalyses 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 192namespace { 193struct CFGSimplifyPass : public FunctionPass { 194 static char ID; // Pass identification, replacement for typeid 195 unsigned BonusInstThreshold; 196 std::function<bool(const Function &)> PredicateFtor; 197 198 CFGSimplifyPass(int T = -1, 199 std::function<bool(const Function &)> Ftor = nullptr) 200 : FunctionPass(ID), PredicateFtor(Ftor) { 201 BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T); 202 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 203 } 204 bool runOnFunction(Function &F) override { 205 if (PredicateFtor && !PredicateFtor(F)) 206 return false; 207 208 if (skipOptnoneFunction(F)) 209 return false; 210 211 AssumptionCache *AC = 212 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 213 const TargetTransformInfo &TTI = 214 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 215 return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold); 216 } 217 218 void getAnalysisUsage(AnalysisUsage &AU) const override { 219 AU.addRequired<AssumptionCacheTracker>(); 220 AU.addRequired<TargetTransformInfoWrapperPass>(); 221 } 222}; 223} 224 225char CFGSimplifyPass::ID = 0; 226INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 227 false) 228INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 229INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 230INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 231 false) 232 233// Public interface to the CFGSimplification pass 234FunctionPass * 235llvm::createCFGSimplificationPass(int Threshold, 236 std::function<bool(const Function &)> Ftor) { 237 return new CFGSimplifyPass(Threshold, Ftor); 238} 239 240