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