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(Val: 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(Val: 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(Val: 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(Val: 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(Val: 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(Val: false), |
74 | cl::desc("hoist common instructions (default = false)" )); |
75 | |
76 | static cl::opt<bool> UserSinkCommonInsts( |
77 | "sink-common-insts" , cl::Hidden, cl::init(Val: false), |
78 | cl::desc("Sink common instructions (default = false)" )); |
79 | |
80 | |
81 | STATISTIC(NumSimpl, "Number of blocks simplified" ); |
82 | |
83 | static bool |
84 | performBlockTailMerging(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 | |
156 | static 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. |
222 | static 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> ; |
231 | for (const auto &Edge : Edges) |
232 | UniqueLoopHeaders.insert(Ptr: const_cast<BasicBlock *>(Edge.second)); |
233 | |
234 | SmallVector<WeakVH, 16> (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 | |
265 | static 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 | |
294 | static 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. |
311 | static 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 | |
328 | SimplifyCFGPass::SimplifyCFGPass() { |
329 | applyCommandLineOverridesToOptions(Options); |
330 | } |
331 | |
332 | SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) |
333 | : Options(Opts) { |
334 | applyCommandLineOverridesToOptions(Options); |
335 | } |
336 | |
337 | void 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 | |
356 | PreservedAnalyses 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 | |
371 | namespace { |
372 | struct 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 | |
411 | char CFGSimplifyPass::ID = 0; |
412 | INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg" , "Simplify the CFG" , false, |
413 | false) |
414 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) |
415 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) |
416 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
417 | INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg" , "Simplify the CFG" , false, |
418 | false) |
419 | |
420 | // Public interface to the CFGSimplification pass |
421 | FunctionPass * |
422 | llvm::createCFGSimplificationPass(SimplifyCFGOptions Options, |
423 | std::function<bool(const Function &)> Ftor) { |
424 | return new CFGSimplifyPass(Options, std::move(Ftor)); |
425 | } |
426 | |