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