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>
47using namespace llvm;
48
49#define DEBUG_TYPE "simplifycfg"
50
51static cl::opt<unsigned> UserBonusInstThreshold(
52 "bonus-inst-threshold", cl::Hidden, cl::init(Val: 1),
53 cl::desc("Control the number of bonus instructions (default = 1)"));
54
55static cl::opt<bool> UserKeepLoops(
56 "keep-loops", cl::Hidden, cl::init(Val: true),
57 cl::desc("Preserve canonical loop structure (default = true)"));
58
59static cl::opt<bool> UserSwitchRangeToICmp(
60 "switch-range-to-icmp", cl::Hidden, cl::init(Val: false),
61 cl::desc(
62 "Convert switches into an integer range comparison (default = false)"));
63
64static cl::opt<bool> UserSwitchToLookup(
65 "switch-to-lookup", cl::Hidden, cl::init(Val: false),
66 cl::desc("Convert switches to lookup tables (default = false)"));
67
68static cl::opt<bool> UserForwardSwitchCond(
69 "forward-switch-cond", cl::Hidden, cl::init(Val: false),
70 cl::desc("Forward switch condition to phi ops (default = false)"));
71
72static cl::opt<bool> UserHoistCommonInsts(
73 "hoist-common-insts", cl::Hidden, cl::init(Val: false),
74 cl::desc("hoist common instructions (default = false)"));
75
76static cl::opt<bool> UserSinkCommonInsts(
77 "sink-common-insts", cl::Hidden, cl::init(Val: false),
78 cl::desc("Sink common instructions (default = false)"));
79
80
81STATISTIC(NumSimpl, "Number of blocks simplified");
82
83static bool
84performBlockTailMerging(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(n: 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 Context&: F.getContext(), Name: Twine("common.") + Term->getOpcodeName(), Parent: &F, InsertBefore: BBs[0]);
105 // We'll also need a PHI node per each operand of the terminator.
106 NewOps.resize(N: Term->getNumOperands());
107 for (auto I : zip(t: Term->operands(), u&: NewOps)) {
108 std::get<1>(t&: I) = PHINode::Create(Ty: std::get<0>(t&: I)->getType(),
109 /*NumReservedValues=*/BBs.size(),
110 NameStr: CanonicalBB->getName() + ".op");
111 std::get<1>(t&: I)->insertInto(ParentBB: CanonicalBB, It: CanonicalBB->end());
112 }
113 // Make it so that this canonical block actually has the right
114 // terminator.
115 CanonicalTerm = Term->clone();
116 CanonicalTerm->insertInto(ParentBB: CanonicalBB, It: CanonicalBB->end());
117 // If the canonical terminator has operands, rewrite it to take PHI's.
118 for (auto I : zip(t&: NewOps, u: CanonicalTerm->operands()))
119 std::get<1>(t&: I) = std::get<0>(t&: 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(t: Term->operands(), u&: NewOps))
134 std::get<1>(t&: I)->addIncoming(V: std::get<0>(t&: 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(LocA: CommonDebugLoc, LocB: 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(IfTrue: CanonicalBB, InsertAtEnd: BB);
147 if (Updates)
148 Updates->push_back(x: {DominatorTree::Insert, BB, CanonicalBB});
149 }
150
151 CanonicalTerm->setDebugLoc(CommonDebugLoc);
152
153 return true;
154}
155
156static 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(DelBB: &BB))
164 continue;
165
166 // We are only interested in function-terminating blocks.
167 if (!succ_empty(BB: &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>(Val: 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(Range: Term->operands(),
200 P: [](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(Args: &BB);
205 }
206
207 bool Changed = false;
208
209 std::vector<DominatorTree::UpdateType> Updates;
210
211 for (ArrayRef<BasicBlock *> BBs : make_second_range(c&: Structure))
212 Changed |= performBlockTailMerging(F, BBs, Updates: 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.
222static 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, Result&: Edges);
230 SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
231 for (const auto &Edge : Edges)
232 UniqueLoopHeaders.insert(Ptr: 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(DelBB: &*BBIt))
253 ++BBIt;
254 }
255 if (simplifyCFG(BB: &BB, TTI, DTU, Options, LoopHeaders)) {
256 LocalChange = true;
257 ++NumSimpl;
258 }
259 }
260 Changed |= LocalChange;
261 }
262 return Changed;
263}
264
265static 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, DTU: DT ? &DTU : nullptr);
271 EverChanged |=
272 tailMergeBlocksWithSimilarFunctionTerminators(F, DTU: DT ? &DTU : nullptr);
273 EverChanged |= iterativelySimplifyCFG(F, TTI, DTU: 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, DTU: DT ? &DTU : nullptr))
284 return true;
285
286 do {
287 EverChanged = iterativelySimplifyCFG(F, TTI, DTU: DT ? &DTU : nullptr, Options);
288 EverChanged |= removeUnreachableBlocks(F, DTU: DT ? &DTU : nullptr);
289 } while (EverChanged);
290
291 return true;
292}
293
294static 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.
311static 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
328SimplifyCFGPass::SimplifyCFGPass() {
329 applyCommandLineOverridesToOptions(Options);
330}
331
332SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)
333 : Options(Opts) {
334 applyCommandLineOverridesToOptions(Options);
335}
336
337void 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
356PreservedAnalyses SimplifyCFGPass::run(Function &F,
357 FunctionAnalysisManager &AM) {
358 auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
359 Options.AC = &AM.getResult<AssumptionAnalysis>(IR&: F);
360 DominatorTree *DT = nullptr;
361 if (RequireAndPreserveDomTree)
362 DT = &AM.getResult<DominatorTreeAnalysis>(IR&: 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
371namespace {
372struct 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
411char CFGSimplifyPass::ID = 0;
412INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
413 false)
414INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
415INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
416INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
417INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
418 false)
419
420// Public interface to the CFGSimplification pass
421FunctionPass *
422llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,
423 std::function<bool(const Function &)> Ftor) {
424 return new CFGSimplifyPass(Options, std::move(Ftor));
425}
426

source code of llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp