1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements dead code elimination and basic block merging, along
11 // with a collection of other peephole control flow optimizations. For example:
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)".
22 //===----------------------------------------------------------------------===//
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"
46 #define DEBUG_TYPE "simplifycfg"
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)"));
52 STATISTIC(NumSimpl, "Number of blocks simplified");
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) {
59 BasicBlock *RetBlock = nullptr;
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++;
65 // Only look at return blocks.
66 ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
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);
75 // Skip over debug info.
76 while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
78 if (!isa<DbgInfoIntrinsic>(I) &&
79 (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
80 Ret->getOperand(0) != &*I))
84 // If this is the first returning block, remember it and keep going.
90 // Otherwise, we found a duplicate return block. Merge the two.
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
96 if (Ret->getNumOperands() == 0 ||
98 cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
99 BB.replaceAllUsesWith(RetBlock);
100 BB.eraseFromParent();
104 // If the canonical return block has no PHI node, create one now.
105 PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
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",
113 for (pred_iterator PI = PB; PI != PE; ++PI)
114 RetBlockPHI->addIncoming(InVal, *PI);
115 RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
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);
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,
133 unsigned BonusInstThreshold,
134 bool LateSimplifyCFG) {
135 bool Changed = false;
136 bool LocalChange = true;
138 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
139 FindFunctionBackedges(F, Edges);
140 SmallPtrSet<BasicBlock *, 16> LoopHeaders;
141 for (unsigned i = 0, e = Edges.size(); i != e; ++i)
142 LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
144 while (LocalChange) {
147 // Loop over all of the basic blocks and remove them if they are unneeded.
148 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
149 if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC, &LoopHeaders, LateSimplifyCFG)) {
154 Changed |= LocalChange;
159 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
160 AssumptionCache *AC, int BonusInstThreshold,
161 bool LateSimplifyCFG) {
162 bool EverChanged = removeUnreachableBlocks(F);
163 EverChanged |= mergeEmptyReturnBlocks(F);
164 EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold,
167 // If neither pass changed anything, we're done.
168 if (!EverChanged) return false;
170 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
171 // removeUnreachableBlocks is needed to nuke them, which means we should
172 // iterate between the two optimizations. We structure the code like this to
173 // avoid rerunning iterativelySimplifyCFG if the second pass of
174 // removeUnreachableBlocks doesn't do anything.
175 if (!removeUnreachableBlocks(F))
179 EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold,
181 EverChanged |= removeUnreachableBlocks(F);
182 } while (EverChanged);
187 SimplifyCFGPass::SimplifyCFGPass()
188 : BonusInstThreshold(UserBonusInstThreshold),
189 LateSimplifyCFG(true) {}
191 SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold, bool LateSimplifyCFG)
192 : BonusInstThreshold(BonusInstThreshold),
193 LateSimplifyCFG(LateSimplifyCFG) {}
195 PreservedAnalyses SimplifyCFGPass::run(Function &F,
196 FunctionAnalysisManager &AM) {
197 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
198 auto &AC = AM.getResult<AssumptionAnalysis>(F);
200 if (!simplifyFunctionCFG(F, TTI, &AC, BonusInstThreshold, LateSimplifyCFG))
201 return PreservedAnalyses::all();
202 PreservedAnalyses PA;
203 PA.preserve<GlobalsAA>();
208 struct BaseCFGSimplifyPass : public FunctionPass {
209 unsigned BonusInstThreshold;
210 std::function<bool(const Function &)> PredicateFtor;
211 bool LateSimplifyCFG;
213 BaseCFGSimplifyPass(int T, bool LateSimplifyCFG,
214 std::function<bool(const Function &)> Ftor,
216 : FunctionPass(ID), PredicateFtor(std::move(Ftor)),
217 LateSimplifyCFG(LateSimplifyCFG) {
218 BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T);
220 bool runOnFunction(Function &F) override {
221 if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
224 AssumptionCache *AC =
225 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
226 const TargetTransformInfo &TTI =
227 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
228 return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold, LateSimplifyCFG);
231 void getAnalysisUsage(AnalysisUsage &AU) const override {
232 AU.addRequired<AssumptionCacheTracker>();
233 AU.addRequired<TargetTransformInfoWrapperPass>();
234 AU.addPreserved<GlobalsAAWrapperPass>();
238 struct CFGSimplifyPass : public BaseCFGSimplifyPass {
239 static char ID; // Pass identification, replacement for typeid
241 CFGSimplifyPass(int T = -1,
242 std::function<bool(const Function &)> Ftor = nullptr)
243 : BaseCFGSimplifyPass(T, false, Ftor, ID) {
244 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
248 struct LateCFGSimplifyPass : public BaseCFGSimplifyPass {
249 static char ID; // Pass identification, replacement for typeid
251 LateCFGSimplifyPass(int T = -1,
252 std::function<bool(const Function &)> Ftor = nullptr)
253 : BaseCFGSimplifyPass(T, true, Ftor, ID) {
254 initializeLateCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
259 char CFGSimplifyPass::ID = 0;
260 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
262 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
263 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
264 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
267 char LateCFGSimplifyPass::ID = 0;
268 INITIALIZE_PASS_BEGIN(LateCFGSimplifyPass, "latesimplifycfg",
269 "Simplify the CFG more aggressively", false, false)
270 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
271 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
272 INITIALIZE_PASS_END(LateCFGSimplifyPass, "latesimplifycfg",
273 "Simplify the CFG more aggressively", false, false)
275 // Public interface to the CFGSimplification pass
277 llvm::createCFGSimplificationPass(int Threshold,
278 std::function<bool(const Function &)> Ftor) {
279 return new CFGSimplifyPass(Threshold, std::move(Ftor));
282 // Public interface to the LateCFGSimplification pass
284 llvm::createLateCFGSimplificationPass(int Threshold,
285 std::function<bool(const Function &)> Ftor) {
286 return new LateCFGSimplifyPass(Threshold, std::move(Ftor));