1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements dead code elimination and basic block merging, along
10 // with a collection of other peephole control flow optimizations.  For example:
11 //
12 //   * Removes basic blocks with no predecessors.
13 //   * Merges a basic block into its predecessor if there is only one and the
14 //     predecessor only has one successor.
15 //   * Eliminates PHI nodes for basic blocks with a single predecessor.
16 //   * Eliminates a basic block that only contains an unconditional branch.
17 //   * Changes invoke instructions to nounwind functions to be calls.
18 //   * Change things like "if (x) if (y)" into "if (x&y)".
19 //   * etc..
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Statistic.h"
26 #include "llvm/Analysis/AssumptionCache.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/InitializePasses.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> UserBonusInstThreshold(
49     "bonus-inst-threshold", cl::Hidden, cl::init(1),
50     cl::desc("Control the number of bonus instructions (default = 1)"));
51 
52 static cl::opt<bool> UserKeepLoops(
53     "keep-loops", cl::Hidden, cl::init(true),
54     cl::desc("Preserve canonical loop structure (default = true)"));
55 
56 static cl::opt<bool> UserSwitchToLookup(
57     "switch-to-lookup", cl::Hidden, cl::init(false),
58     cl::desc("Convert switches to lookup tables (default = false)"));
59 
60 static cl::opt<bool> UserForwardSwitchCond(
61     "forward-switch-cond", cl::Hidden, cl::init(false),
62     cl::desc("Forward switch condition to phi ops (default = false)"));
63 
64 static cl::opt<bool> UserSinkCommonInsts(
65     "sink-common-insts", cl::Hidden, cl::init(false),
66     cl::desc("Sink common instructions (default = false)"));
67 
68 
69 STATISTIC(NumSimpl, "Number of blocks simplified");
70 
71 /// If we have more than one empty (other than phi node) return blocks,
72 /// merge them together to promote recursive block merging.
73 static bool mergeEmptyReturnBlocks(Function &F) {
74   bool Changed = false;
75 
76   BasicBlock *RetBlock = nullptr;
77 
78   // Scan all the blocks in the function, looking for empty return blocks.
79   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
80     BasicBlock &BB = *BBI++;
81 
82     // Only look at return blocks.
83     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
84     if (!Ret) continue;
85 
86     // Only look at the block if it is empty or the only other thing in it is a
87     // single PHI node that is the operand to the return.
88     if (Ret != &BB.front()) {
89       // Check for something else in the block.
90       BasicBlock::iterator I(Ret);
91       --I;
92       // Skip over debug info.
93       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
94         --I;
95       if (!isa<DbgInfoIntrinsic>(I) &&
96           (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
97            Ret->getOperand(0) != &*I))
98         continue;
99     }
100 
101     // If this is the first returning block, remember it and keep going.
102     if (!RetBlock) {
103       RetBlock = &BB;
104       continue;
105     }
106 
107     // Skip merging if this would result in a CallBr instruction with a
108     // duplicate destination. FIXME: See note in CodeGenPrepare.cpp.
109     bool SkipCallBr = false;
110     for (pred_iterator PI = pred_begin(&BB), E = pred_end(&BB);
111          PI != E && !SkipCallBr; ++PI) {
112       if (auto *CBI = dyn_cast<CallBrInst>((*PI)->getTerminator()))
113         for (unsigned i = 0, e = CBI->getNumSuccessors(); i != e; ++i)
114           if (RetBlock == CBI->getSuccessor(i)) {
115             SkipCallBr = true;
116             break;
117           }
118     }
119     if (SkipCallBr)
120       continue;
121 
122     // Otherwise, we found a duplicate return block.  Merge the two.
123     Changed = true;
124 
125     // Case when there is no input to the return or when the returned values
126     // agree is trivial.  Note that they can't agree if there are phis in the
127     // blocks.
128     if (Ret->getNumOperands() == 0 ||
129         Ret->getOperand(0) ==
130           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
131       BB.replaceAllUsesWith(RetBlock);
132       BB.eraseFromParent();
133       continue;
134     }
135 
136     // If the canonical return block has no PHI node, create one now.
137     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
138     if (!RetBlockPHI) {
139       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
140       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
141       RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
142                                     std::distance(PB, PE), "merge",
143                                     &RetBlock->front());
144 
145       for (pred_iterator PI = PB; PI != PE; ++PI)
146         RetBlockPHI->addIncoming(InVal, *PI);
147       RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
148     }
149 
150     // Turn BB into a block that just unconditionally branches to the return
151     // block.  This handles the case when the two return blocks have a common
152     // predecessor but that return different things.
153     RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
154     BB.getTerminator()->eraseFromParent();
155     BranchInst::Create(RetBlock, &BB);
156   }
157 
158   return Changed;
159 }
160 
161 /// Call SimplifyCFG on all the blocks in the function,
162 /// iterating until no more changes are made.
163 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
164                                    const SimplifyCFGOptions &Options) {
165   bool Changed = false;
166   bool LocalChange = true;
167 
168   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
169   FindFunctionBackedges(F, Edges);
170   SmallPtrSet<BasicBlock *, 16> LoopHeaders;
171   for (unsigned i = 0, e = Edges.size(); i != e; ++i)
172     LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
173 
174   while (LocalChange) {
175     LocalChange = false;
176 
177     // Loop over all of the basic blocks and remove them if they are unneeded.
178     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
179       if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
180         LocalChange = true;
181         ++NumSimpl;
182       }
183     }
184     Changed |= LocalChange;
185   }
186   return Changed;
187 }
188 
189 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
190                                 const SimplifyCFGOptions &Options) {
191   bool EverChanged = removeUnreachableBlocks(F);
192   EverChanged |= mergeEmptyReturnBlocks(F);
193   EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
194 
195   // If neither pass changed anything, we're done.
196   if (!EverChanged) return false;
197 
198   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
199   // removeUnreachableBlocks is needed to nuke them, which means we should
200   // iterate between the two optimizations.  We structure the code like this to
201   // avoid rerunning iterativelySimplifyCFG if the second pass of
202   // removeUnreachableBlocks doesn't do anything.
203   if (!removeUnreachableBlocks(F))
204     return true;
205 
206   do {
207     EverChanged = iterativelySimplifyCFG(F, TTI, Options);
208     EverChanged |= removeUnreachableBlocks(F);
209   } while (EverChanged);
210 
211   return true;
212 }
213 
214 // Command-line settings override compile-time settings.
215 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) {
216   Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
217                                    ? UserBonusInstThreshold
218                                    : Opts.BonusInstThreshold;
219   Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
220                                        ? UserForwardSwitchCond
221                                        : Opts.ForwardSwitchCondToPhi;
222   Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
223                                            ? UserSwitchToLookup
224                                            : Opts.ConvertSwitchToLookupTable;
225   Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
226                                   ? UserKeepLoops
227                                   : Opts.NeedCanonicalLoop;
228   Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
229                                 ? UserSinkCommonInsts
230                                 : Opts.SinkCommonInsts;
231 }
232 
233 PreservedAnalyses SimplifyCFGPass::run(Function &F,
234                                        FunctionAnalysisManager &AM) {
235   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
236   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
237   if (!simplifyFunctionCFG(F, TTI, Options))
238     return PreservedAnalyses::all();
239   PreservedAnalyses PA;
240   PA.preserve<GlobalsAA>();
241   return PA;
242 }
243 
244 namespace {
245 struct CFGSimplifyPass : public FunctionPass {
246   static char ID;
247   SimplifyCFGOptions Options;
248   std::function<bool(const Function &)> PredicateFtor;
249 
250   CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
251                   bool ConvertSwitch = false, bool KeepLoops = true,
252                   bool SinkCommon = false,
253                   std::function<bool(const Function &)> Ftor = nullptr)
254       : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
255 
256     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
257 
258     // Check for command-line overrides of options for debug/customization.
259     Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
260                                     ? UserBonusInstThreshold
261                                     : Threshold;
262 
263     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
264                                          ? UserForwardSwitchCond
265                                          : ForwardSwitchCond;
266 
267     Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
268                                              ? UserSwitchToLookup
269                                              : ConvertSwitch;
270 
271     Options.NeedCanonicalLoop =
272         UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
273 
274     Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
275                                   ? UserSinkCommonInsts
276                                   : SinkCommon;
277   }
278 
279   bool runOnFunction(Function &F) override {
280     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
281       return false;
282 
283     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
284     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
285     return simplifyFunctionCFG(F, TTI, Options);
286   }
287   void getAnalysisUsage(AnalysisUsage &AU) const override {
288     AU.addRequired<AssumptionCacheTracker>();
289     AU.addRequired<TargetTransformInfoWrapperPass>();
290     AU.addPreserved<GlobalsAAWrapperPass>();
291   }
292 };
293 }
294 
295 char CFGSimplifyPass::ID = 0;
296 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
297                       false)
298 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
299 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
300 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
301                     false)
302 
303 // Public interface to the CFGSimplification pass
304 FunctionPass *
305 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
306                                   bool ConvertSwitch, bool KeepLoops,
307                                   bool SinkCommon,
308                                   std::function<bool(const Function &)> Ftor) {
309   return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
310                              KeepLoops, SinkCommon, std::move(Ftor));
311 }
312