[libc] implement unistd/getentropy (#122692)
[llvm-project.git] / llvm / lib / Transforms / Scalar / SimplifyCFGPass.cpp
blob4e437e9abeb43e66eeb25879c5f65635ff82a814
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:
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..
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"
45 #include <utility>
46 using namespace llvm;
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),
60 cl::desc(
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");
90 static bool
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.
97 if (BBs.size() < 2)
98 return false;
100 if (Updates)
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
121 // terminator.
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.
144 if (!CommonDebugLoc)
145 CommonDebugLoc = Term->getDebugLoc();
146 else
147 CommonDebugLoc =
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();
156 if (Updates)
157 Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});
160 CanonicalTerm->setDebugLoc(CommonDebugLoc);
162 return true;
165 static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F,
166 DomTreeUpdater *DTU) {
167 SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
168 Structure;
170 // Scan all the blocks in the function, record the interesting-ones.
171 for (BasicBlock &BB : F) {
172 if (DTU && DTU->isBBPendingDeletion(&BB))
173 continue;
175 // We are only interested in function-terminating blocks.
176 if (!succ_empty(&BB))
177 continue;
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:
186 break;
187 default:
188 continue;
191 // We can't tail-merge block that contains a musttail call.
192 if (BB.getTerminatingMustTailCall())
193 continue;
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.
198 if (auto *CI =
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)
203 continue;
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(); }))
210 continue;
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);
223 if (DTU)
224 DTU->applyUpdates(Updates);
226 return Changed;
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,
232 DomTreeUpdater *DTU,
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;
247 (void)IterCnt;
248 while (LocalChange) {
249 assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");
250 LocalChange = false;
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++;
255 if (DTU) {
256 assert(
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))
262 ++BBIt;
264 if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
265 LocalChange = true;
266 ++NumSimpl;
269 Changed |= LocalChange;
271 return Changed;
274 static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
275 DominatorTree *DT,
276 const SimplifyCFGOptions &Options) {
277 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
279 bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
280 EverChanged |=
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))
293 return true;
295 do {
296 EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
297 EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
298 } while (EverChanged);
300 return true;
303 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
304 DominatorTree *DT,
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!");
316 return Changed;
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)
347 : Options(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);
355 OS << '<';
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";
371 OS << '>';
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>();
386 return PA;
389 namespace {
390 struct CFGSimplifyPass : public FunctionPass {
391 static char ID;
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)))
407 return false;
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,
431 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,
436 false)
438 // Public interface to the CFGSimplification pass
439 FunctionPass *
440 llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,
441 std::function<bool(const Function &)> Ftor) {
442 return new CFGSimplifyPass(Options, std::move(Ftor));