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/CFG.h" 28 #include "llvm/Analysis/GlobalsModRef.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/Scalar.h" 40 #include "llvm/Transforms/Scalar/SimplifyCFG.h" 41 #include "llvm/Transforms/Utils/Local.h" 42 #include <utility> 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 unsigned BonusInstThreshold) { 132 bool Changed = false; 133 bool LocalChange = true; 134 135 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges; 136 FindFunctionBackedges(F, Edges); 137 SmallPtrSet<BasicBlock *, 16> LoopHeaders; 138 for (unsigned i = 0, e = Edges.size(); i != e; ++i) 139 LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second)); 140 141 while (LocalChange) { 142 LocalChange = false; 143 144 // Loop over all of the basic blocks and remove them if they are unneeded. 145 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { 146 if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, &LoopHeaders)) { 147 LocalChange = true; 148 ++NumSimpl; 149 } 150 } 151 Changed |= LocalChange; 152 } 153 return Changed; 154 } 155 156 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, 157 int BonusInstThreshold) { 158 bool EverChanged = removeUnreachableBlocks(F); 159 EverChanged |= mergeEmptyReturnBlocks(F); 160 EverChanged |= iterativelySimplifyCFG(F, TTI, BonusInstThreshold); 161 162 // If neither pass changed anything, we're done. 163 if (!EverChanged) return false; 164 165 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 166 // removeUnreachableBlocks is needed to nuke them, which means we should 167 // iterate between the two optimizations. We structure the code like this to 168 // avoid rerunning iterativelySimplifyCFG if the second pass of 169 // removeUnreachableBlocks doesn't do anything. 170 if (!removeUnreachableBlocks(F)) 171 return true; 172 173 do { 174 EverChanged = iterativelySimplifyCFG(F, TTI, BonusInstThreshold); 175 EverChanged |= removeUnreachableBlocks(F); 176 } while (EverChanged); 177 178 return true; 179 } 180 181 SimplifyCFGPass::SimplifyCFGPass() 182 : BonusInstThreshold(UserBonusInstThreshold) {} 183 184 SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold) 185 : BonusInstThreshold(BonusInstThreshold) {} 186 187 PreservedAnalyses SimplifyCFGPass::run(Function &F, 188 FunctionAnalysisManager &AM) { 189 auto &TTI = AM.getResult<TargetIRAnalysis>(F); 190 191 if (!simplifyFunctionCFG(F, TTI, BonusInstThreshold)) 192 return PreservedAnalyses::all(); 193 PreservedAnalyses PA; 194 PA.preserve<GlobalsAA>(); 195 return PA; 196 } 197 198 namespace { 199 struct CFGSimplifyPass : public FunctionPass { 200 static char ID; // Pass identification, replacement for typeid 201 unsigned BonusInstThreshold; 202 std::function<bool(const Function &)> PredicateFtor; 203 204 CFGSimplifyPass(int T = -1, 205 std::function<bool(const Function &)> Ftor = nullptr) 206 : FunctionPass(ID), PredicateFtor(std::move(Ftor)) { 207 BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T); 208 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 209 } 210 bool runOnFunction(Function &F) override { 211 if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F))) 212 return false; 213 214 const TargetTransformInfo &TTI = 215 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 216 return simplifyFunctionCFG(F, TTI, BonusInstThreshold); 217 } 218 219 void getAnalysisUsage(AnalysisUsage &AU) const override { 220 AU.addRequired<TargetTransformInfoWrapperPass>(); 221 AU.addPreserved<GlobalsAAWrapperPass>(); 222 } 223 }; 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_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 231 false) 232 233 // Public interface to the CFGSimplification pass 234 FunctionPass * 235 llvm::createCFGSimplificationPass(int Threshold, 236 std::function<bool(const Function &)> Ftor) { 237 return new CFGSimplifyPass(Threshold, std::move(Ftor)); 238 } 239