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 namespace { 200 struct CFGSimplifyPass : public FunctionPass { 201 static char ID; // Pass identification, replacement for typeid 202 unsigned BonusInstThreshold; 203 std::function<bool(const Function &)> PredicateFtor; 204 205 CFGSimplifyPass(int T = -1, 206 std::function<bool(const Function &)> Ftor = nullptr) 207 : FunctionPass(ID), PredicateFtor(Ftor) { 208 BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T); 209 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 210 } 211 bool runOnFunction(Function &F) override { 212 if (PredicateFtor && !PredicateFtor(F)) 213 return false; 214 215 if (skipOptnoneFunction(F)) 216 return false; 217 218 AssumptionCache *AC = 219 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 220 const TargetTransformInfo &TTI = 221 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 222 return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold); 223 } 224 225 void getAnalysisUsage(AnalysisUsage &AU) const override { 226 AU.addRequired<AssumptionCacheTracker>(); 227 AU.addRequired<TargetTransformInfoWrapperPass>(); 228 AU.addPreserved<GlobalsAAWrapperPass>(); 229 } 230 }; 231 } 232 233 char CFGSimplifyPass::ID = 0; 234 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 235 false) 236 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 237 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 238 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 239 false) 240 241 // Public interface to the CFGSimplification pass 242 FunctionPass * 243 llvm::createCFGSimplificationPass(int Threshold, 244 std::function<bool(const Function &)> Ftor) { 245 return new CFGSimplifyPass(Threshold, Ftor); 246 } 247