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