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> 44using namespace llvm; 45 46#define DEBUG_TYPE "simplifycfg" 47 48static cl::opt<unsigned> 49UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1), 50 cl::desc("Control the number of bonus instructions (default = 1)")); 51 52STATISTIC(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. 56static 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. 131static 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 158static 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 183SimplifyCFGPass::SimplifyCFGPass() 184 : BonusInstThreshold(UserBonusInstThreshold) {} 185 186SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold) 187 : BonusInstThreshold(BonusInstThreshold) {} 188 189PreservedAnalyses 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::all(); 196 PreservedAnalyses PA; 197 PA.preserve<GlobalsAA>(); 198 return PA; 199} 200 201namespace { 202struct CFGSimplifyPass : public FunctionPass { 203 static char ID; // Pass identification, replacement for typeid 204 unsigned BonusInstThreshold; 205 std::function<bool(const Function &)> PredicateFtor; 206 207 CFGSimplifyPass(int T = -1, 208 std::function<bool(const Function &)> Ftor = nullptr) 209 : FunctionPass(ID), PredicateFtor(std::move(Ftor)) { 210 BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T); 211 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 212 } 213 bool runOnFunction(Function &F) override { 214 if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F))) 215 return false; 216 217 AssumptionCache *AC = 218 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 219 const TargetTransformInfo &TTI = 220 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 221 return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold); 222 } 223 224 void getAnalysisUsage(AnalysisUsage &AU) const override { 225 AU.addRequired<AssumptionCacheTracker>(); 226 AU.addRequired<TargetTransformInfoWrapperPass>(); 227 AU.addPreserved<GlobalsAAWrapperPass>(); 228 } 229}; 230} 231 232char CFGSimplifyPass::ID = 0; 233INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 234 false) 235INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 236INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 237INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 238 false) 239 240// Public interface to the CFGSimplification pass 241FunctionPass * 242llvm::createCFGSimplificationPass(int Threshold, 243 std::function<bool(const Function &)> Ftor) { 244 return new CFGSimplifyPass(Threshold, std::move(Ftor)); 245} 246