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
performBlockTailMerging(Function & F,ArrayRef<BasicBlock * > BBs,std::vector<DominatorTree::UpdateType> * Updates)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
tailMergeBlocksWithSimilarFunctionTerminators(Function & F,DomTreeUpdater * DTU)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.
iterativelySimplifyCFG(Function & F,const TargetTransformInfo & TTI,DomTreeUpdater * DTU,const SimplifyCFGOptions & Options)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
simplifyFunctionCFGImpl(Function & F,const TargetTransformInfo & TTI,DominatorTree * DT,const SimplifyCFGOptions & Options)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
simplifyFunctionCFG(Function & F,const TargetTransformInfo & TTI,DominatorTree * DT,const SimplifyCFGOptions & Options)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.
applyCommandLineOverridesToOptions(SimplifyCFGOptions & Options)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
SimplifyCFGPass()335 SimplifyCFGPass::SimplifyCFGPass() {
336 applyCommandLineOverridesToOptions(Options);
337 }
338
SimplifyCFGPass(const SimplifyCFGOptions & Opts)339 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)
340 : Options(Opts) {
341 applyCommandLineOverridesToOptions(Options);
342 }
343
printPipeline(raw_ostream & OS,function_ref<StringRef (StringRef)> MapClassName2PassName)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
run(Function & F,FunctionAnalysisManager & AM)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
CFGSimplifyPass__anond21748470211::CFGSimplifyPass386 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
runOnFunction__anond21748470211::CFGSimplifyPass396 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 }
getAnalysisUsage__anond21748470211::CFGSimplifyPass408 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)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)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