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 const DataLayout *DL, 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, DL, 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 const DataLayout *DL, AssumptionCache *AC, 152 int BonusInstThreshold) { 153 bool EverChanged = removeUnreachableBlocks(F); 154 EverChanged |= mergeEmptyReturnBlocks(F); 155 EverChanged |= iterativelySimplifyCFG(F, TTI, DL, AC, BonusInstThreshold); 156 157 // If neither pass changed anything, we're done. 158 if (!EverChanged) return false; 159 160 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 161 // removeUnreachableBlocks is needed to nuke them, which means we should 162 // iterate between the two optimizations. We structure the code like this to 163 // avoid reruning iterativelySimplifyCFG if the second pass of 164 // removeUnreachableBlocks doesn't do anything. 165 if (!removeUnreachableBlocks(F)) 166 return true; 167 168 do { 169 EverChanged = iterativelySimplifyCFG(F, TTI, DL, AC, BonusInstThreshold); 170 EverChanged |= removeUnreachableBlocks(F); 171 } while (EverChanged); 172 173 return true; 174 } 175 176 SimplifyCFGPass::SimplifyCFGPass() 177 : BonusInstThreshold(UserBonusInstThreshold) {} 178 179 SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold) 180 : BonusInstThreshold(BonusInstThreshold) {} 181 182 PreservedAnalyses SimplifyCFGPass::run(Function &F, 183 AnalysisManager<Function> *AM) { 184 auto *DL = F.getParent()->getDataLayout(); 185 auto &TTI = AM->getResult<TargetIRAnalysis>(F); 186 auto &AC = AM->getResult<AssumptionAnalysis>(F); 187 188 if (!simplifyFunctionCFG(F, TTI, DL, &AC, BonusInstThreshold)) 189 return PreservedAnalyses::none(); 190 191 return PreservedAnalyses::all(); 192 } 193 194 namespace { 195 struct CFGSimplifyPass : public FunctionPass { 196 static char ID; // Pass identification, replacement for typeid 197 unsigned BonusInstThreshold; 198 CFGSimplifyPass(int T = -1) : FunctionPass(ID) { 199 BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T); 200 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 201 } 202 bool runOnFunction(Function &F) override { 203 if (skipOptnoneFunction(F)) 204 return false; 205 206 AssumptionCache *AC = 207 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 208 const TargetTransformInfo &TTI = 209 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(); 210 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 211 const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; 212 return simplifyFunctionCFG(F, TTI, DL, AC, BonusInstThreshold); 213 } 214 215 void getAnalysisUsage(AnalysisUsage &AU) const override { 216 AU.addRequired<AssumptionCacheTracker>(); 217 AU.addRequired<TargetTransformInfoWrapperPass>(); 218 } 219 }; 220 } 221 222 char CFGSimplifyPass::ID = 0; 223 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 224 false) 225 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 226 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 227 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 228 false) 229 230 // Public interface to the CFGSimplification pass 231 FunctionPass *llvm::createCFGSimplificationPass(int Threshold) { 232 return new CFGSimplifyPass(Threshold); 233 } 234 235