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