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/DomTreeUpdater.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/Dominators.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/Module.h"
39 #include "llvm/IR/ValueHandle.h"
40 #include "llvm/InitializePasses.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Transforms/Scalar.h"
44 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
45 #include "llvm/Transforms/Utils/Local.h"
46 #include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
47 #include <utility>
48 using namespace llvm;
49 
50 #define DEBUG_TYPE "simplifycfg"
51 
52 static cl::opt<unsigned> UserBonusInstThreshold(
53     "bonus-inst-threshold", cl::Hidden, cl::init(1),
54     cl::desc("Control the number of bonus instructions (default = 1)"));
55 
56 static cl::opt<bool> UserKeepLoops(
57     "keep-loops", cl::Hidden, cl::init(true),
58     cl::desc("Preserve canonical loop structure (default = true)"));
59 
60 static cl::opt<bool> UserSwitchToLookup(
61     "switch-to-lookup", cl::Hidden, cl::init(false),
62     cl::desc("Convert switches to lookup tables (default = false)"));
63 
64 static cl::opt<bool> UserForwardSwitchCond(
65     "forward-switch-cond", cl::Hidden, cl::init(false),
66     cl::desc("Forward switch condition to phi ops (default = false)"));
67 
68 static cl::opt<bool> UserHoistCommonInsts(
69     "hoist-common-insts", cl::Hidden, cl::init(false),
70     cl::desc("hoist common instructions (default = false)"));
71 
72 static cl::opt<bool> UserSinkCommonInsts(
73     "sink-common-insts", cl::Hidden, cl::init(false),
74     cl::desc("Sink common instructions (default = false)"));
75 
76 
77 STATISTIC(NumSimpl, "Number of blocks simplified");
78 
79 /// If we have more than one empty (other than phi node) return blocks,
80 /// merge them together to promote recursive block merging.
81 static bool mergeEmptyReturnBlocks(Function &F, DomTreeUpdater *DTU) {
82   bool Changed = false;
83 
84   std::vector<DominatorTree::UpdateType> Updates;
85   SmallVector<BasicBlock *, 8> DeadBlocks;
86 
87   BasicBlock *RetBlock = nullptr;
88 
89   // Scan all the blocks in the function, looking for empty return blocks.
90   for (BasicBlock &BB : make_early_inc_range(F)) {
91     if (DTU && DTU->isBBPendingDeletion(&BB))
92       continue;
93 
94     // Only look at return blocks.
95     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
96     if (!Ret) continue;
97 
98     // Only look at the block if it is empty or the only other thing in it is a
99     // single PHI node that is the operand to the return.
100     if (Ret != &BB.front()) {
101       // Check for something else in the block.
102       BasicBlock::iterator I(Ret);
103       --I;
104       // Skip over debug info.
105       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
106         --I;
107       if (!isa<DbgInfoIntrinsic>(I) &&
108           (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
109            Ret->getOperand(0) != &*I))
110         continue;
111     }
112 
113     // If this is the first returning block, remember it and keep going.
114     if (!RetBlock) {
115       RetBlock = &BB;
116       continue;
117     }
118 
119     // Skip merging if this would result in a CallBr instruction with a
120     // duplicate destination. FIXME: See note in CodeGenPrepare.cpp.
121     bool SkipCallBr = false;
122     for (pred_iterator PI = pred_begin(&BB), E = pred_end(&BB);
123          PI != E && !SkipCallBr; ++PI) {
124       if (auto *CBI = dyn_cast<CallBrInst>((*PI)->getTerminator()))
125         for (unsigned i = 0, e = CBI->getNumSuccessors(); i != e; ++i)
126           if (RetBlock == CBI->getSuccessor(i)) {
127             SkipCallBr = true;
128             break;
129           }
130     }
131     if (SkipCallBr)
132       continue;
133 
134     // Otherwise, we found a duplicate return block.  Merge the two.
135     Changed = true;
136 
137     // Case when there is no input to the return or when the returned values
138     // agree is trivial.  Note that they can't agree if there are phis in the
139     // blocks.
140     if (Ret->getNumOperands() == 0 ||
141         Ret->getOperand(0) ==
142           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
143       // All predecessors of BB should now branch to RetBlock instead.
144       if (DTU) {
145         for (auto *Predecessor : predecessors(&BB)) {
146           // But, iff Predecessor already branches to RetBlock,
147           // don't (re-)add DomTree edge, because it already exists.
148           if (!is_contained(successors(Predecessor), RetBlock))
149             Updates.push_back({DominatorTree::Insert, Predecessor, RetBlock});
150           Updates.push_back({DominatorTree::Delete, Predecessor, &BB});
151         }
152       }
153       BB.replaceAllUsesWith(RetBlock);
154       DeadBlocks.emplace_back(&BB);
155       continue;
156     }
157 
158     // If the canonical return block has no PHI node, create one now.
159     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
160     if (!RetBlockPHI) {
161       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
162       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
163       RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
164                                     std::distance(PB, PE), "merge",
165                                     &RetBlock->front());
166 
167       for (pred_iterator PI = PB; PI != PE; ++PI)
168         RetBlockPHI->addIncoming(InVal, *PI);
169       RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
170     }
171 
172     // Turn BB into a block that just unconditionally branches to the return
173     // block.  This handles the case when the two return blocks have a common
174     // predecessor but that return different things.
175     RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
176     BB.getTerminator()->eraseFromParent();
177     BranchInst::Create(RetBlock, &BB);
178     if (DTU)
179       Updates.push_back({DominatorTree::Insert, &BB, RetBlock});
180   }
181 
182   if (DTU) {
183     DTU->applyUpdates(Updates);
184     for (auto *BB : DeadBlocks)
185       DTU->deleteBB(BB);
186   } else {
187     for (auto *BB : DeadBlocks)
188       BB->eraseFromParent();
189   }
190 
191   return Changed;
192 }
193 
194 /// Call SimplifyCFG on all the blocks in the function,
195 /// iterating until no more changes are made.
196 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
197                                    DomTreeUpdater *DTU,
198                                    const SimplifyCFGOptions &Options) {
199   bool Changed = false;
200   bool LocalChange = true;
201 
202   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
203   FindFunctionBackedges(F, Edges);
204   SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
205   for (unsigned i = 0, e = Edges.size(); i != e; ++i)
206     UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
207 
208   SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),
209                                       UniqueLoopHeaders.end());
210 
211   while (LocalChange) {
212     LocalChange = false;
213 
214     // Loop over all of the basic blocks and remove them if they are unneeded.
215     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
216       BasicBlock &BB = *BBIt++;
217       if (DTU) {
218         assert(
219             !DTU->isBBPendingDeletion(&BB) &&
220             "Should not end up trying to simplify blocks marked for removal.");
221         // Make sure that the advanced iterator does not point at the blocks
222         // that are marked for removal, skip over all such blocks.
223         while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))
224           ++BBIt;
225       }
226       if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
227         LocalChange = true;
228         ++NumSimpl;
229       }
230     }
231     Changed |= LocalChange;
232   }
233   return Changed;
234 }
235 
236 static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
237                                     DominatorTree *DT,
238                                     const SimplifyCFGOptions &Options) {
239   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
240 
241   bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
242   EverChanged |= mergeEmptyReturnBlocks(F, DT ? &DTU : nullptr);
243   EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
244 
245   // If neither pass changed anything, we're done.
246   if (!EverChanged) return false;
247 
248   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
249   // removeUnreachableBlocks is needed to nuke them, which means we should
250   // iterate between the two optimizations.  We structure the code like this to
251   // avoid rerunning iterativelySimplifyCFG if the second pass of
252   // removeUnreachableBlocks doesn't do anything.
253   if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))
254     return true;
255 
256   do {
257     EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
258     EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
259   } while (EverChanged);
260 
261   return true;
262 }
263 
264 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
265                                 DominatorTree *DT,
266                                 const SimplifyCFGOptions &Options) {
267   assert((!RequireAndPreserveDomTree ||
268           (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
269          "Original domtree is invalid?");
270 
271   bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
272 
273   assert((!RequireAndPreserveDomTree ||
274           (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
275          "Failed to maintain validity of domtree!");
276 
277   return Changed;
278 }
279 
280 // Command-line settings override compile-time settings.
281 static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) {
282   if (UserBonusInstThreshold.getNumOccurrences())
283     Options.BonusInstThreshold = UserBonusInstThreshold;
284   if (UserForwardSwitchCond.getNumOccurrences())
285     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
286   if (UserSwitchToLookup.getNumOccurrences())
287     Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
288   if (UserKeepLoops.getNumOccurrences())
289     Options.NeedCanonicalLoop = UserKeepLoops;
290   if (UserHoistCommonInsts.getNumOccurrences())
291     Options.HoistCommonInsts = UserHoistCommonInsts;
292   if (UserSinkCommonInsts.getNumOccurrences())
293     Options.SinkCommonInsts = UserSinkCommonInsts;
294 }
295 
296 SimplifyCFGPass::SimplifyCFGPass() : Options() {
297   applyCommandLineOverridesToOptions(Options);
298 }
299 
300 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)
301     : Options(Opts) {
302   applyCommandLineOverridesToOptions(Options);
303 }
304 
305 PreservedAnalyses SimplifyCFGPass::run(Function &F,
306                                        FunctionAnalysisManager &AM) {
307   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
308   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
309   DominatorTree *DT = nullptr;
310   if (RequireAndPreserveDomTree)
311     DT = &AM.getResult<DominatorTreeAnalysis>(F);
312   if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
313     Options.setSimplifyCondBranch(false).setFoldTwoEntryPHINode(false);
314   } else {
315     Options.setSimplifyCondBranch(true).setFoldTwoEntryPHINode(true);
316   }
317   if (!simplifyFunctionCFG(F, TTI, DT, Options))
318     return PreservedAnalyses::all();
319   PreservedAnalyses PA;
320   if (RequireAndPreserveDomTree)
321     PA.preserve<DominatorTreeAnalysis>();
322   PA.preserve<GlobalsAA>();
323   return PA;
324 }
325 
326 namespace {
327 struct CFGSimplifyPass : public FunctionPass {
328   static char ID;
329   SimplifyCFGOptions Options;
330   std::function<bool(const Function &)> PredicateFtor;
331 
332   CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
333                   std::function<bool(const Function &)> Ftor = nullptr)
334       : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
335 
336     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
337 
338     // Check for command-line overrides of options for debug/customization.
339     applyCommandLineOverridesToOptions(Options);
340   }
341 
342   bool runOnFunction(Function &F) override {
343     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
344       return false;
345 
346     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
347     DominatorTree *DT = nullptr;
348     if (RequireAndPreserveDomTree)
349       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
350     if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
351       Options.setSimplifyCondBranch(false)
352              .setFoldTwoEntryPHINode(false);
353     } else {
354       Options.setSimplifyCondBranch(true)
355              .setFoldTwoEntryPHINode(true);
356     }
357 
358     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
359     return simplifyFunctionCFG(F, TTI, DT, Options);
360   }
361   void getAnalysisUsage(AnalysisUsage &AU) const override {
362     AU.addRequired<AssumptionCacheTracker>();
363     if (RequireAndPreserveDomTree)
364       AU.addRequired<DominatorTreeWrapperPass>();
365     AU.addRequired<TargetTransformInfoWrapperPass>();
366     if (RequireAndPreserveDomTree)
367       AU.addPreserved<DominatorTreeWrapperPass>();
368     AU.addPreserved<GlobalsAAWrapperPass>();
369   }
370 };
371 }
372 
373 char CFGSimplifyPass::ID = 0;
374 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
375                       false)
376 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
377 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
378 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
379 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
380                     false)
381 
382 // Public interface to the CFGSimplification pass
383 FunctionPass *
384 llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,
385                                   std::function<bool(const Function &)> Ftor) {
386   return new CFGSimplifyPass(Options, std::move(Ftor));
387 }
388