1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements dead code elimination and basic block merging, along
10 // with a collection of other peephole control flow optimizations. For example:
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)".
21 //===----------------------------------------------------------------------===//
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/ValueHandle.h"
38 #include "llvm/InitializePasses.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Transforms/Scalar.h"
42 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
43 #include "llvm/Transforms/Utils/Local.h"
44 #include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
48 #define DEBUG_TYPE "simplifycfg"
50 static cl::opt
<unsigned> UserBonusInstThreshold(
51 "bonus-inst-threshold", cl::Hidden
, cl::init(1),
52 cl::desc("Control the number of bonus instructions (default = 1)"));
54 static cl::opt
<bool> UserKeepLoops(
55 "keep-loops", cl::Hidden
, cl::init(true),
56 cl::desc("Preserve canonical loop structure (default = true)"));
58 static cl::opt
<bool> UserSwitchRangeToICmp(
59 "switch-range-to-icmp", cl::Hidden
, cl::init(false),
61 "Convert switches into an integer range comparison (default = false)"));
63 static cl::opt
<bool> UserSwitchToLookup(
64 "switch-to-lookup", cl::Hidden
, cl::init(false),
65 cl::desc("Convert switches to lookup tables (default = false)"));
67 static cl::opt
<bool> UserForwardSwitchCond(
68 "forward-switch-cond", cl::Hidden
, cl::init(false),
69 cl::desc("Forward switch condition to phi ops (default = false)"));
71 static cl::opt
<bool> UserHoistCommonInsts(
72 "hoist-common-insts", cl::Hidden
, cl::init(false),
73 cl::desc("hoist common instructions (default = false)"));
75 static cl::opt
<bool> UserHoistLoadsStoresWithCondFaulting(
76 "hoist-loads-stores-with-cond-faulting", cl::Hidden
, cl::init(false),
77 cl::desc("Hoist loads/stores if the target supports conditional faulting "
78 "(default = false)"));
80 static cl::opt
<bool> UserSinkCommonInsts(
81 "sink-common-insts", cl::Hidden
, cl::init(false),
82 cl::desc("Sink common instructions (default = false)"));
84 static cl::opt
<bool> UserSpeculateUnpredictables(
85 "speculate-unpredictables", cl::Hidden
, cl::init(false),
86 cl::desc("Speculate unpredictable branches (default = false)"));
88 STATISTIC(NumSimpl
, "Number of blocks simplified");
91 performBlockTailMerging(Function
&F
, ArrayRef
<BasicBlock
*> BBs
,
92 std::vector
<DominatorTree::UpdateType
> *Updates
) {
93 SmallVector
<PHINode
*, 1> NewOps
;
95 // We don't want to change IR just because we can.
96 // Only do that if there are at least two blocks we'll tail-merge.
101 Updates
->reserve(Updates
->size() + BBs
.size());
103 BasicBlock
*CanonicalBB
;
104 Instruction
*CanonicalTerm
;
106 auto *Term
= BBs
[0]->getTerminator();
108 // Create a canonical block for this function terminator type now,
109 // placing it *before* the first block that will branch to it.
110 CanonicalBB
= BasicBlock::Create(
111 F
.getContext(), Twine("common.") + Term
->getOpcodeName(), &F
, BBs
[0]);
112 // We'll also need a PHI node per each operand of the terminator.
113 NewOps
.resize(Term
->getNumOperands());
114 for (auto I
: zip(Term
->operands(), NewOps
)) {
115 std::get
<1>(I
) = PHINode::Create(std::get
<0>(I
)->getType(),
116 /*NumReservedValues=*/BBs
.size(),
117 CanonicalBB
->getName() + ".op");
118 std::get
<1>(I
)->insertInto(CanonicalBB
, CanonicalBB
->end());
120 // Make it so that this canonical block actually has the right
122 CanonicalTerm
= Term
->clone();
123 CanonicalTerm
->insertInto(CanonicalBB
, CanonicalBB
->end());
124 // If the canonical terminator has operands, rewrite it to take PHI's.
125 for (auto I
: zip(NewOps
, CanonicalTerm
->operands()))
126 std::get
<1>(I
) = std::get
<0>(I
);
129 // Now, go through each block (with the current terminator type)
130 // we've recorded, and rewrite it to branch to the new common block.
131 DILocation
*CommonDebugLoc
= nullptr;
132 for (BasicBlock
*BB
: BBs
) {
133 auto *Term
= BB
->getTerminator();
134 assert(Term
->getOpcode() == CanonicalTerm
->getOpcode() &&
135 "All blocks to be tail-merged must be the same "
136 "(function-terminating) terminator type.");
138 // Aha, found a new non-canonical function terminator. If it has operands,
139 // forward them to the PHI nodes in the canonical block.
140 for (auto I
: zip(Term
->operands(), NewOps
))
141 std::get
<1>(I
)->addIncoming(std::get
<0>(I
), BB
);
143 // Compute the debug location common to all the original terminators.
145 CommonDebugLoc
= Term
->getDebugLoc();
148 DILocation::getMergedLocation(CommonDebugLoc
, Term
->getDebugLoc());
150 // And turn BB into a block that just unconditionally branches
151 // to the canonical block.
152 Instruction
*BI
= BranchInst::Create(CanonicalBB
, BB
);
153 BI
->setDebugLoc(Term
->getDebugLoc());
154 Term
->eraseFromParent();
157 Updates
->push_back({DominatorTree::Insert
, BB
, CanonicalBB
});
160 CanonicalTerm
->setDebugLoc(CommonDebugLoc
);
165 static bool tailMergeBlocksWithSimilarFunctionTerminators(Function
&F
,
166 DomTreeUpdater
*DTU
) {
167 SmallMapVector
<unsigned /*TerminatorOpcode*/, SmallVector
<BasicBlock
*, 2>, 4>
170 // Scan all the blocks in the function, record the interesting-ones.
171 for (BasicBlock
&BB
: F
) {
172 if (DTU
&& DTU
->isBBPendingDeletion(&BB
))
175 // We are only interested in function-terminating blocks.
176 if (!succ_empty(&BB
))
179 auto *Term
= BB
.getTerminator();
181 // Fow now only support `ret`/`resume` function terminators.
182 // FIXME: lift this restriction.
183 switch (Term
->getOpcode()) {
184 case Instruction::Ret
:
185 case Instruction::Resume
:
191 // We can't tail-merge block that contains a musttail call.
192 if (BB
.getTerminatingMustTailCall())
195 // Calls to experimental_deoptimize must be followed by a return
196 // of the value computed by experimental_deoptimize.
197 // I.e., we can not change `ret` to `br` for this block.
199 dyn_cast_or_null
<CallInst
>(Term
->getPrevNonDebugInstruction())) {
200 if (Function
*F
= CI
->getCalledFunction())
201 if (Intrinsic::ID ID
= F
->getIntrinsicID())
202 if (ID
== Intrinsic::experimental_deoptimize
)
206 // PHI nodes cannot have token type, so if the terminator has an operand
207 // with token type, we can not tail-merge this kind of function terminators.
208 if (any_of(Term
->operands(),
209 [](Value
*Op
) { return Op
->getType()->isTokenTy(); }))
212 // Canonical blocks are uniqued based on the terminator type (opcode).
213 Structure
[Term
->getOpcode()].emplace_back(&BB
);
216 bool Changed
= false;
218 std::vector
<DominatorTree::UpdateType
> Updates
;
220 for (ArrayRef
<BasicBlock
*> BBs
: make_second_range(Structure
))
221 Changed
|= performBlockTailMerging(F
, BBs
, DTU
? &Updates
: nullptr);
224 DTU
->applyUpdates(Updates
);
229 /// Call SimplifyCFG on all the blocks in the function,
230 /// iterating until no more changes are made.
231 static bool iterativelySimplifyCFG(Function
&F
, const TargetTransformInfo
&TTI
,
233 const SimplifyCFGOptions
&Options
) {
234 bool Changed
= false;
235 bool LocalChange
= true;
237 SmallVector
<std::pair
<const BasicBlock
*, const BasicBlock
*>, 32> Edges
;
238 FindFunctionBackedges(F
, Edges
);
239 SmallPtrSet
<BasicBlock
*, 16> UniqueLoopHeaders
;
240 for (const auto &Edge
: Edges
)
241 UniqueLoopHeaders
.insert(const_cast<BasicBlock
*>(Edge
.second
));
243 SmallVector
<WeakVH
, 16> LoopHeaders(UniqueLoopHeaders
.begin(),
244 UniqueLoopHeaders
.end());
246 unsigned IterCnt
= 0;
248 while (LocalChange
) {
249 assert(IterCnt
++ < 1000 && "Iterative simplification didn't converge!");
252 // Loop over all of the basic blocks and remove them if they are unneeded.
253 for (Function::iterator BBIt
= F
.begin(); BBIt
!= F
.end(); ) {
254 BasicBlock
&BB
= *BBIt
++;
257 !DTU
->isBBPendingDeletion(&BB
) &&
258 "Should not end up trying to simplify blocks marked for removal.");
259 // Make sure that the advanced iterator does not point at the blocks
260 // that are marked for removal, skip over all such blocks.
261 while (BBIt
!= F
.end() && DTU
->isBBPendingDeletion(&*BBIt
))
264 if (simplifyCFG(&BB
, TTI
, DTU
, Options
, LoopHeaders
)) {
269 Changed
|= LocalChange
;
274 static bool simplifyFunctionCFGImpl(Function
&F
, const TargetTransformInfo
&TTI
,
276 const SimplifyCFGOptions
&Options
) {
277 DomTreeUpdater
DTU(DT
, DomTreeUpdater::UpdateStrategy::Eager
);
279 bool EverChanged
= removeUnreachableBlocks(F
, DT
? &DTU
: nullptr);
281 tailMergeBlocksWithSimilarFunctionTerminators(F
, DT
? &DTU
: nullptr);
282 EverChanged
|= iterativelySimplifyCFG(F
, TTI
, DT
? &DTU
: nullptr, Options
);
284 // If neither pass changed anything, we're done.
285 if (!EverChanged
) return false;
287 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
288 // removeUnreachableBlocks is needed to nuke them, which means we should
289 // iterate between the two optimizations. We structure the code like this to
290 // avoid rerunning iterativelySimplifyCFG if the second pass of
291 // removeUnreachableBlocks doesn't do anything.
292 if (!removeUnreachableBlocks(F
, DT
? &DTU
: nullptr))
296 EverChanged
= iterativelySimplifyCFG(F
, TTI
, DT
? &DTU
: nullptr, Options
);
297 EverChanged
|= removeUnreachableBlocks(F
, DT
? &DTU
: nullptr);
298 } while (EverChanged
);
303 static bool simplifyFunctionCFG(Function
&F
, const TargetTransformInfo
&TTI
,
305 const SimplifyCFGOptions
&Options
) {
306 assert((!RequireAndPreserveDomTree
||
307 (DT
&& DT
->verify(DominatorTree::VerificationLevel::Full
))) &&
308 "Original domtree is invalid?");
310 bool Changed
= simplifyFunctionCFGImpl(F
, TTI
, DT
, Options
);
312 assert((!RequireAndPreserveDomTree
||
313 (DT
&& DT
->verify(DominatorTree::VerificationLevel::Full
))) &&
314 "Failed to maintain validity of domtree!");
319 // Command-line settings override compile-time settings.
320 static void applyCommandLineOverridesToOptions(SimplifyCFGOptions
&Options
) {
321 if (UserBonusInstThreshold
.getNumOccurrences())
322 Options
.BonusInstThreshold
= UserBonusInstThreshold
;
323 if (UserForwardSwitchCond
.getNumOccurrences())
324 Options
.ForwardSwitchCondToPhi
= UserForwardSwitchCond
;
325 if (UserSwitchRangeToICmp
.getNumOccurrences())
326 Options
.ConvertSwitchRangeToICmp
= UserSwitchRangeToICmp
;
327 if (UserSwitchToLookup
.getNumOccurrences())
328 Options
.ConvertSwitchToLookupTable
= UserSwitchToLookup
;
329 if (UserKeepLoops
.getNumOccurrences())
330 Options
.NeedCanonicalLoop
= UserKeepLoops
;
331 if (UserHoistCommonInsts
.getNumOccurrences())
332 Options
.HoistCommonInsts
= UserHoistCommonInsts
;
333 if (UserHoistLoadsStoresWithCondFaulting
.getNumOccurrences())
334 Options
.HoistLoadsStoresWithCondFaulting
=
335 UserHoistLoadsStoresWithCondFaulting
;
336 if (UserSinkCommonInsts
.getNumOccurrences())
337 Options
.SinkCommonInsts
= UserSinkCommonInsts
;
338 if (UserSpeculateUnpredictables
.getNumOccurrences())
339 Options
.SpeculateUnpredictables
= UserSpeculateUnpredictables
;
342 SimplifyCFGPass::SimplifyCFGPass() {
343 applyCommandLineOverridesToOptions(Options
);
346 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions
&Opts
)
348 applyCommandLineOverridesToOptions(Options
);
351 void SimplifyCFGPass::printPipeline(
352 raw_ostream
&OS
, function_ref
<StringRef(StringRef
)> MapClassName2PassName
) {
353 static_cast<PassInfoMixin
<SimplifyCFGPass
> *>(this)->printPipeline(
354 OS
, MapClassName2PassName
);
356 OS
<< "bonus-inst-threshold=" << Options
.BonusInstThreshold
<< ';';
357 OS
<< (Options
.ForwardSwitchCondToPhi
? "" : "no-") << "forward-switch-cond;";
358 OS
<< (Options
.ConvertSwitchRangeToICmp
? "" : "no-")
359 << "switch-range-to-icmp;";
360 OS
<< (Options
.ConvertSwitchToLookupTable
? "" : "no-")
361 << "switch-to-lookup;";
362 OS
<< (Options
.NeedCanonicalLoop
? "" : "no-") << "keep-loops;";
363 OS
<< (Options
.HoistCommonInsts
? "" : "no-") << "hoist-common-insts;";
364 OS
<< (Options
.HoistLoadsStoresWithCondFaulting
? "" : "no-")
365 << "hoist-loads-stores-with-cond-faulting;";
366 OS
<< (Options
.SinkCommonInsts
? "" : "no-") << "sink-common-insts;";
367 OS
<< (Options
.SpeculateBlocks
? "" : "no-") << "speculate-blocks;";
368 OS
<< (Options
.SimplifyCondBranch
? "" : "no-") << "simplify-cond-branch;";
369 OS
<< (Options
.SpeculateUnpredictables
? "" : "no-")
370 << "speculate-unpredictables";
374 PreservedAnalyses
SimplifyCFGPass::run(Function
&F
,
375 FunctionAnalysisManager
&AM
) {
376 auto &TTI
= AM
.getResult
<TargetIRAnalysis
>(F
);
377 Options
.AC
= &AM
.getResult
<AssumptionAnalysis
>(F
);
378 DominatorTree
*DT
= nullptr;
379 if (RequireAndPreserveDomTree
)
380 DT
= &AM
.getResult
<DominatorTreeAnalysis
>(F
);
381 if (!simplifyFunctionCFG(F
, TTI
, DT
, Options
))
382 return PreservedAnalyses::all();
383 PreservedAnalyses PA
;
384 if (RequireAndPreserveDomTree
)
385 PA
.preserve
<DominatorTreeAnalysis
>();
390 struct CFGSimplifyPass
: public FunctionPass
{
392 SimplifyCFGOptions Options
;
393 std::function
<bool(const Function
&)> PredicateFtor
;
395 CFGSimplifyPass(SimplifyCFGOptions Options_
= SimplifyCFGOptions(),
396 std::function
<bool(const Function
&)> Ftor
= nullptr)
397 : FunctionPass(ID
), Options(Options_
), PredicateFtor(std::move(Ftor
)) {
399 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
401 // Check for command-line overrides of options for debug/customization.
402 applyCommandLineOverridesToOptions(Options
);
405 bool runOnFunction(Function
&F
) override
{
406 if (skipFunction(F
) || (PredicateFtor
&& !PredicateFtor(F
)))
409 Options
.AC
= &getAnalysis
<AssumptionCacheTracker
>().getAssumptionCache(F
);
410 DominatorTree
*DT
= nullptr;
411 if (RequireAndPreserveDomTree
)
412 DT
= &getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
414 auto &TTI
= getAnalysis
<TargetTransformInfoWrapperPass
>().getTTI(F
);
415 return simplifyFunctionCFG(F
, TTI
, DT
, Options
);
417 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
418 AU
.addRequired
<AssumptionCacheTracker
>();
419 if (RequireAndPreserveDomTree
)
420 AU
.addRequired
<DominatorTreeWrapperPass
>();
421 AU
.addRequired
<TargetTransformInfoWrapperPass
>();
422 if (RequireAndPreserveDomTree
)
423 AU
.addPreserved
<DominatorTreeWrapperPass
>();
424 AU
.addPreserved
<GlobalsAAWrapperPass
>();
429 char CFGSimplifyPass::ID
= 0;
430 INITIALIZE_PASS_BEGIN(CFGSimplifyPass
, "simplifycfg", "Simplify the CFG", false,
432 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass
)
433 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker
)
434 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
)
435 INITIALIZE_PASS_END(CFGSimplifyPass
, "simplifycfg", "Simplify the CFG", false,
438 // Public interface to the CFGSimplification pass
440 llvm::createCFGSimplificationPass(SimplifyCFGOptions Options
,
441 std::function
<bool(const Function
&)> Ftor
) {
442 return new CFGSimplifyPass(Options
, std::move(Ftor
));