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