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/MapVector.h"
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/DomTreeUpdater.h"
30 #include "llvm/Analysis/GlobalsModRef.h"
31 #include "llvm/Analysis/TargetTransformInfo.h"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/CFG.h"
34 #include "llvm/IR/DebugInfoMetadata.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/ValueHandle.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/CommandLine.h"
42 #include "llvm/Transforms/Scalar.h"
43 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
44 #include "llvm/Transforms/Utils/Local.h"
45 #include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
46 #include <utility>
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "simplifycfg"
50 
51 static cl::opt<unsigned> UserBonusInstThreshold(
52     "bonus-inst-threshold", cl::Hidden, cl::init(1),
53     cl::desc("Control the number of bonus instructions (default = 1)"));
54 
55 static cl::opt<bool> UserKeepLoops(
56     "keep-loops", cl::Hidden, cl::init(true),
57     cl::desc("Preserve canonical loop structure (default = true)"));
58 
59 static cl::opt<bool> UserSwitchRangeToICmp(
60     "switch-range-to-icmp", cl::Hidden, cl::init(false),
61     cl::desc(
62         "Convert switches into an integer range comparison (default = false)"));
63 
64 static cl::opt<bool> UserSwitchToLookup(
65     "switch-to-lookup", cl::Hidden, cl::init(false),
66     cl::desc("Convert switches to lookup tables (default = false)"));
67 
68 static cl::opt<bool> UserForwardSwitchCond(
69     "forward-switch-cond", cl::Hidden, cl::init(false),
70     cl::desc("Forward switch condition to phi ops (default = false)"));
71 
72 static cl::opt<bool> UserHoistCommonInsts(
73     "hoist-common-insts", cl::Hidden, cl::init(false),
74     cl::desc("hoist common instructions (default = false)"));
75 
76 static cl::opt<bool> UserSinkCommonInsts(
77     "sink-common-insts", cl::Hidden, cl::init(false),
78     cl::desc("Sink common instructions (default = false)"));
79 
80 
81 STATISTIC(NumSimpl, "Number of blocks simplified");
82 
83 static bool
84 performBlockTailMerging(Function &F, ArrayRef<BasicBlock *> BBs,
85                         std::vector<DominatorTree::UpdateType> *Updates) {
86   SmallVector<PHINode *, 1> NewOps;
87 
88   // We don't want to change IR just because we can.
89   // Only do that if there are at least two blocks we'll tail-merge.
90   if (BBs.size() < 2)
91     return false;
92 
93   if (Updates)
94     Updates->reserve(Updates->size() + BBs.size());
95 
96   BasicBlock *CanonicalBB;
97   Instruction *CanonicalTerm;
98   {
99     auto *Term = BBs[0]->getTerminator();
100 
101     // Create a canonical block for this function terminator type now,
102     // placing it *before* the first block that will branch to it.
103     CanonicalBB = BasicBlock::Create(
104         F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);
105     // We'll also need a PHI node per each operand of the terminator.
106     NewOps.resize(Term->getNumOperands());
107     for (auto I : zip(Term->operands(), NewOps)) {
108       std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),
109                                        /*NumReservedValues=*/BBs.size(),
110                                        CanonicalBB->getName() + ".op");
111       std::get<1>(I)->insertInto(CanonicalBB, CanonicalBB->end());
112     }
113     // Make it so that this canonical block actually has the right
114     // terminator.
115     CanonicalTerm = Term->clone();
116     CanonicalTerm->insertInto(CanonicalBB, CanonicalBB->end());
117     // If the canonical terminator has operands, rewrite it to take PHI's.
118     for (auto I : zip(NewOps, CanonicalTerm->operands()))
119       std::get<1>(I) = std::get<0>(I);
120   }
121 
122   // Now, go through each block (with the current terminator type)
123   // we've recorded, and rewrite it to branch to the new common block.
124   DILocation *CommonDebugLoc = nullptr;
125   for (BasicBlock *BB : BBs) {
126     auto *Term = BB->getTerminator();
127     assert(Term->getOpcode() == CanonicalTerm->getOpcode() &&
128            "All blocks to be tail-merged must be the same "
129            "(function-terminating) terminator type.");
130 
131     // Aha, found a new non-canonical function terminator. If it has operands,
132     // forward them to the PHI nodes in the canonical block.
133     for (auto I : zip(Term->operands(), NewOps))
134       std::get<1>(I)->addIncoming(std::get<0>(I), BB);
135 
136     // Compute the debug location common to all the original terminators.
137     if (!CommonDebugLoc)
138       CommonDebugLoc = Term->getDebugLoc();
139     else
140       CommonDebugLoc =
141           DILocation::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());
142 
143     // And turn BB into a block that just unconditionally branches
144     // to the canonical block.
145     Term->eraseFromParent();
146     BranchInst::Create(CanonicalBB, BB);
147     if (Updates)
148       Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});
149   }
150 
151   CanonicalTerm->setDebugLoc(CommonDebugLoc);
152 
153   return true;
154 }
155 
156 static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F,
157                                                           DomTreeUpdater *DTU) {
158   SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
159       Structure;
160 
161   // Scan all the blocks in the function, record the interesting-ones.
162   for (BasicBlock &BB : F) {
163     if (DTU && DTU->isBBPendingDeletion(&BB))
164       continue;
165 
166     // We are only interested in function-terminating blocks.
167     if (!succ_empty(&BB))
168       continue;
169 
170     auto *Term = BB.getTerminator();
171 
172     // Fow now only support `ret`/`resume` function terminators.
173     // FIXME: lift this restriction.
174     switch (Term->getOpcode()) {
175     case Instruction::Ret:
176     case Instruction::Resume:
177       break;
178     default:
179       continue;
180     }
181 
182     // We can't tail-merge block that contains a musttail call.
183     if (BB.getTerminatingMustTailCall())
184       continue;
185 
186     // Calls to experimental_deoptimize must be followed by a return
187     // of the value computed by experimental_deoptimize.
188     // I.e., we can not change `ret` to `br` for this block.
189     if (auto *CI =
190             dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) {
191       if (Function *F = CI->getCalledFunction())
192         if (Intrinsic::ID ID = F->getIntrinsicID())
193           if (ID == Intrinsic::experimental_deoptimize)
194             continue;
195     }
196 
197     // PHI nodes cannot have token type, so if the terminator has an operand
198     // with token type, we can not tail-merge this kind of function terminators.
199     if (any_of(Term->operands(),
200                [](Value *Op) { return Op->getType()->isTokenTy(); }))
201       continue;
202 
203     // Canonical blocks are uniqued based on the terminator type (opcode).
204     Structure[Term->getOpcode()].emplace_back(&BB);
205   }
206 
207   bool Changed = false;
208 
209   std::vector<DominatorTree::UpdateType> Updates;
210 
211   for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure))
212     Changed |= performBlockTailMerging(F, BBs, DTU ? &Updates : nullptr);
213 
214   if (DTU)
215     DTU->applyUpdates(Updates);
216 
217   return Changed;
218 }
219 
220 /// Call SimplifyCFG on all the blocks in the function,
221 /// iterating until no more changes are made.
222 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
223                                    DomTreeUpdater *DTU,
224                                    const SimplifyCFGOptions &Options) {
225   bool Changed = false;
226   bool LocalChange = true;
227 
228   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
229   FindFunctionBackedges(F, Edges);
230   SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
231   for (const auto &Edge : Edges)
232     UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edge.second));
233 
234   SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),
235                                       UniqueLoopHeaders.end());
236 
237   unsigned IterCnt = 0;
238   (void)IterCnt;
239   while (LocalChange) {
240     assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");
241     LocalChange = false;
242 
243     // Loop over all of the basic blocks and remove them if they are unneeded.
244     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
245       BasicBlock &BB = *BBIt++;
246       if (DTU) {
247         assert(
248             !DTU->isBBPendingDeletion(&BB) &&
249             "Should not end up trying to simplify blocks marked for removal.");
250         // Make sure that the advanced iterator does not point at the blocks
251         // that are marked for removal, skip over all such blocks.
252         while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))
253           ++BBIt;
254       }
255       if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
256         LocalChange = true;
257         ++NumSimpl;
258       }
259     }
260     Changed |= LocalChange;
261   }
262   return Changed;
263 }
264 
265 static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
266                                     DominatorTree *DT,
267                                     const SimplifyCFGOptions &Options) {
268   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
269 
270   bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
271   EverChanged |=
272       tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);
273   EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
274 
275   // If neither pass changed anything, we're done.
276   if (!EverChanged) return false;
277 
278   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
279   // removeUnreachableBlocks is needed to nuke them, which means we should
280   // iterate between the two optimizations.  We structure the code like this to
281   // avoid rerunning iterativelySimplifyCFG if the second pass of
282   // removeUnreachableBlocks doesn't do anything.
283   if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))
284     return true;
285 
286   do {
287     EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
288     EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
289   } while (EverChanged);
290 
291   return true;
292 }
293 
294 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
295                                 DominatorTree *DT,
296                                 const SimplifyCFGOptions &Options) {
297   assert((!RequireAndPreserveDomTree ||
298           (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
299          "Original domtree is invalid?");
300 
301   bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
302 
303   assert((!RequireAndPreserveDomTree ||
304           (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
305          "Failed to maintain validity of domtree!");
306 
307   return Changed;
308 }
309 
310 // Command-line settings override compile-time settings.
311 static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) {
312   if (UserBonusInstThreshold.getNumOccurrences())
313     Options.BonusInstThreshold = UserBonusInstThreshold;
314   if (UserForwardSwitchCond.getNumOccurrences())
315     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
316   if (UserSwitchRangeToICmp.getNumOccurrences())
317     Options.ConvertSwitchRangeToICmp = UserSwitchRangeToICmp;
318   if (UserSwitchToLookup.getNumOccurrences())
319     Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
320   if (UserKeepLoops.getNumOccurrences())
321     Options.NeedCanonicalLoop = UserKeepLoops;
322   if (UserHoistCommonInsts.getNumOccurrences())
323     Options.HoistCommonInsts = UserHoistCommonInsts;
324   if (UserSinkCommonInsts.getNumOccurrences())
325     Options.SinkCommonInsts = UserSinkCommonInsts;
326 }
327 
328 SimplifyCFGPass::SimplifyCFGPass() {
329   applyCommandLineOverridesToOptions(Options);
330 }
331 
332 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)
333     : Options(Opts) {
334   applyCommandLineOverridesToOptions(Options);
335 }
336 
337 void SimplifyCFGPass::printPipeline(
338     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
339   static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline(
340       OS, MapClassName2PassName);
341   OS << '<';
342   OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ';';
343   OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";
344   OS << (Options.ConvertSwitchRangeToICmp ? "" : "no-")
345      << "switch-range-to-icmp;";
346   OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")
347      << "switch-to-lookup;";
348   OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";
349   OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";
350   OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts;";
351   OS << (Options.SpeculateBlocks ? "" : "no-") << "speculate-blocks;";
352   OS << (Options.SimplifyCondBranch ? "" : "no-") << "simplify-cond-branch";
353   OS << '>';
354 }
355 
356 PreservedAnalyses SimplifyCFGPass::run(Function &F,
357                                        FunctionAnalysisManager &AM) {
358   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
359   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
360   DominatorTree *DT = nullptr;
361   if (RequireAndPreserveDomTree)
362     DT = &AM.getResult<DominatorTreeAnalysis>(F);
363   if (!simplifyFunctionCFG(F, TTI, DT, Options))
364     return PreservedAnalyses::all();
365   PreservedAnalyses PA;
366   if (RequireAndPreserveDomTree)
367     PA.preserve<DominatorTreeAnalysis>();
368   return PA;
369 }
370 
371 namespace {
372 struct CFGSimplifyPass : public FunctionPass {
373   static char ID;
374   SimplifyCFGOptions Options;
375   std::function<bool(const Function &)> PredicateFtor;
376 
377   CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
378                   std::function<bool(const Function &)> Ftor = nullptr)
379       : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
380 
381     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
382 
383     // Check for command-line overrides of options for debug/customization.
384     applyCommandLineOverridesToOptions(Options);
385   }
386 
387   bool runOnFunction(Function &F) override {
388     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
389       return false;
390 
391     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
392     DominatorTree *DT = nullptr;
393     if (RequireAndPreserveDomTree)
394       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
395 
396     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
397     return simplifyFunctionCFG(F, TTI, DT, Options);
398   }
399   void getAnalysisUsage(AnalysisUsage &AU) const override {
400     AU.addRequired<AssumptionCacheTracker>();
401     if (RequireAndPreserveDomTree)
402       AU.addRequired<DominatorTreeWrapperPass>();
403     AU.addRequired<TargetTransformInfoWrapperPass>();
404     if (RequireAndPreserveDomTree)
405       AU.addPreserved<DominatorTreeWrapperPass>();
406     AU.addPreserved<GlobalsAAWrapperPass>();
407   }
408 };
409 }
410 
411 char CFGSimplifyPass::ID = 0;
412 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
413                       false)
414 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
415 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
416 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
417 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
418                     false)
419 
420 // Public interface to the CFGSimplification pass
421 FunctionPass *
422 llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,
423                                   std::function<bool(const Function &)> Ftor) {
424   return new CFGSimplifyPass(Options, std::move(Ftor));
425 }
426