Bug Summary

File:llvm/lib/Transforms/Scalar/LICM.cpp
Warning:line 1216, column 41
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LICM.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-11-24-172238-38865-1 -x c++ /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp

/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp

1//===-- LICM.cpp - Loop Invariant Code Motion 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 pass performs loop invariant code motion, attempting to remove as much
10// code from the body of a loop as possible. It does this by either hoisting
11// code into the preheader block, or by sinking code to the exit blocks if it is
12// safe. This pass also promotes must-aliased memory locations in the loop to
13// live in registers, thus hoisting and sinking "invariant" loads and stores.
14//
15// This pass uses alias analysis for two purposes:
16//
17// 1. Moving loop invariant loads and calls out of loops. If we can determine
18// that a load or call inside of a loop never aliases anything stored to,
19// we can hoist it or sink it like any other instruction.
20// 2. Scalar Promotion of Memory - If there is a store instruction inside of
21// the loop, we try to move the store to happen AFTER the loop instead of
22// inside of the loop. This can only happen if a few conditions are true:
23// A. The pointer stored through is loop invariant
24// B. There are no stores or loads in the loop which _may_ alias the
25// pointer. There are no calls in the loop which mod/ref the pointer.
26// If these conditions are true, we can promote the loads and stores in the
27// loop of the pointer to use a temporary alloca'd variable. We then use
28// the SSAUpdater to construct the appropriate SSA form for the value.
29//
30//===----------------------------------------------------------------------===//
31
32#include "llvm/Transforms/Scalar/LICM.h"
33#include "llvm/ADT/SetOperations.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/Analysis/AliasAnalysis.h"
36#include "llvm/Analysis/AliasSetTracker.h"
37#include "llvm/Analysis/BasicAliasAnalysis.h"
38#include "llvm/Analysis/BlockFrequencyInfo.h"
39#include "llvm/Analysis/CaptureTracking.h"
40#include "llvm/Analysis/ConstantFolding.h"
41#include "llvm/Analysis/GlobalsModRef.h"
42#include "llvm/Analysis/GuardUtils.h"
43#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
44#include "llvm/Analysis/Loads.h"
45#include "llvm/Analysis/LoopInfo.h"
46#include "llvm/Analysis/LoopIterator.h"
47#include "llvm/Analysis/LoopPass.h"
48#include "llvm/Analysis/MemoryBuiltins.h"
49#include "llvm/Analysis/MemorySSA.h"
50#include "llvm/Analysis/MemorySSAUpdater.h"
51#include "llvm/Analysis/MustExecute.h"
52#include "llvm/Analysis/OptimizationRemarkEmitter.h"
53#include "llvm/Analysis/ScalarEvolution.h"
54#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
55#include "llvm/Analysis/TargetLibraryInfo.h"
56#include "llvm/Analysis/ValueTracking.h"
57#include "llvm/IR/CFG.h"
58#include "llvm/IR/Constants.h"
59#include "llvm/IR/DataLayout.h"
60#include "llvm/IR/DebugInfoMetadata.h"
61#include "llvm/IR/DerivedTypes.h"
62#include "llvm/IR/Dominators.h"
63#include "llvm/IR/Instructions.h"
64#include "llvm/IR/IntrinsicInst.h"
65#include "llvm/IR/LLVMContext.h"
66#include "llvm/IR/Metadata.h"
67#include "llvm/IR/PatternMatch.h"
68#include "llvm/IR/PredIteratorCache.h"
69#include "llvm/InitializePasses.h"
70#include "llvm/Support/CommandLine.h"
71#include "llvm/Support/Debug.h"
72#include "llvm/Support/raw_ostream.h"
73#include "llvm/Transforms/Scalar.h"
74#include "llvm/Transforms/Scalar/LoopPassManager.h"
75#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
76#include "llvm/Transforms/Utils/BasicBlockUtils.h"
77#include "llvm/Transforms/Utils/Local.h"
78#include "llvm/Transforms/Utils/LoopUtils.h"
79#include "llvm/Transforms/Utils/SSAUpdater.h"
80#include <algorithm>
81#include <utility>
82using namespace llvm;
83
84#define DEBUG_TYPE"licm" "licm"
85
86STATISTIC(NumCreatedBlocks, "Number of blocks created")static llvm::Statistic NumCreatedBlocks = {"licm", "NumCreatedBlocks"
, "Number of blocks created"}
;
87STATISTIC(NumClonedBranches, "Number of branches cloned")static llvm::Statistic NumClonedBranches = {"licm", "NumClonedBranches"
, "Number of branches cloned"}
;
88STATISTIC(NumSunk, "Number of instructions sunk out of loop")static llvm::Statistic NumSunk = {"licm", "NumSunk", "Number of instructions sunk out of loop"
}
;
89STATISTIC(NumHoisted, "Number of instructions hoisted out of loop")static llvm::Statistic NumHoisted = {"licm", "NumHoisted", "Number of instructions hoisted out of loop"
}
;
90STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk")static llvm::Statistic NumMovedLoads = {"licm", "NumMovedLoads"
, "Number of load insts hoisted or sunk"}
;
91STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk")static llvm::Statistic NumMovedCalls = {"licm", "NumMovedCalls"
, "Number of call insts hoisted or sunk"}
;
92STATISTIC(NumPromoted, "Number of memory locations promoted to registers")static llvm::Statistic NumPromoted = {"licm", "NumPromoted", "Number of memory locations promoted to registers"
}
;
93
94/// Memory promotion is enabled by default.
95static cl::opt<bool>
96 DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
97 cl::desc("Disable memory promotion in LICM pass"));
98
99static cl::opt<bool> ControlFlowHoisting(
100 "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
101 cl::desc("Enable control flow (and PHI) hoisting in LICM"));
102
103static cl::opt<unsigned> HoistSinkColdnessThreshold(
104 "licm-coldness-threshold", cl::Hidden, cl::init(4),
105 cl::desc("Relative coldness Threshold of hoisting/sinking destination "
106 "block for LICM to be considered beneficial"));
107
108static cl::opt<uint32_t> MaxNumUsesTraversed(
109 "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
110 cl::desc("Max num uses visited for identifying load "
111 "invariance in loop using invariant start (default = 8)"));
112
113// Default value of zero implies we use the regular alias set tracker mechanism
114// instead of the cross product using AA to identify aliasing of the memory
115// location we are interested in.
116static cl::opt<int>
117LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
118 cl::desc("How many instruction to cross product using AA"));
119
120// Experimental option to allow imprecision in LICM in pathological cases, in
121// exchange for faster compile. This is to be removed if MemorySSA starts to
122// address the same issue. This flag applies only when LICM uses MemorySSA
123// instead on AliasSetTracker. LICM calls MemorySSAWalker's
124// getClobberingMemoryAccess, up to the value of the Cap, getting perfect
125// accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
126// which may not be precise, since optimizeUses is capped. The result is
127// correct, but we may not get as "far up" as possible to get which access is
128// clobbering the one queried.
129cl::opt<unsigned> llvm::SetLicmMssaOptCap(
130 "licm-mssa-optimization-cap", cl::init(100), cl::Hidden,
131 cl::desc("Enable imprecision in LICM in pathological cases, in exchange "
132 "for faster compile. Caps the MemorySSA clobbering calls."));
133
134// Experimentally, memory promotion carries less importance than sinking and
135// hoisting. Limit when we do promotion when using MemorySSA, in order to save
136// compile time.
137cl::opt<unsigned> llvm::SetLicmMssaNoAccForPromotionCap(
138 "licm-mssa-max-acc-promotion", cl::init(250), cl::Hidden,
139 cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
140 "effect. When MSSA in LICM is enabled, then this is the maximum "
141 "number of accesses allowed to be present in a loop in order to "
142 "enable memory promotion."));
143
144static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
145static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
146 const LoopSafetyInfo *SafetyInfo,
147 TargetTransformInfo *TTI, bool &FreeInLoop);
148static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
149 BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
150 MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
151 OptimizationRemarkEmitter *ORE);
152static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
153 BlockFrequencyInfo *BFI, const Loop *CurLoop,
154 ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
155 OptimizationRemarkEmitter *ORE);
156static bool isSafeToExecuteUnconditionally(Instruction &Inst,
157 const DominatorTree *DT,
158 const Loop *CurLoop,
159 const LoopSafetyInfo *SafetyInfo,
160 OptimizationRemarkEmitter *ORE,
161 const Instruction *CtxI = nullptr);
162static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
163 AliasSetTracker *CurAST, Loop *CurLoop,
164 AAResults *AA);
165static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
166 Loop *CurLoop, Instruction &I,
167 SinkAndHoistLICMFlags &Flags);
168static bool pointerInvalidatedByBlockWithMSSA(BasicBlock &BB, MemorySSA &MSSA,
169 MemoryUse &MU);
170static Instruction *cloneInstructionInExitBlock(
171 Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
172 const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
173
174static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
175 AliasSetTracker *AST, MemorySSAUpdater *MSSAU);
176
177static void moveInstructionBefore(Instruction &I, Instruction &Dest,
178 ICFLoopSafetyInfo &SafetyInfo,
179 MemorySSAUpdater *MSSAU, ScalarEvolution *SE);
180
181namespace {
182struct LoopInvariantCodeMotion {
183 bool runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
184 BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI,
185 TargetTransformInfo *TTI, ScalarEvolution *SE, MemorySSA *MSSA,
186 OptimizationRemarkEmitter *ORE);
187
188 LoopInvariantCodeMotion(unsigned LicmMssaOptCap,
189 unsigned LicmMssaNoAccForPromotionCap)
190 : LicmMssaOptCap(LicmMssaOptCap),
191 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap) {}
192
193private:
194 unsigned LicmMssaOptCap;
195 unsigned LicmMssaNoAccForPromotionCap;
196
197 std::unique_ptr<AliasSetTracker>
198 collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AAResults *AA);
199 std::unique_ptr<AliasSetTracker>
200 collectAliasInfoForLoopWithMSSA(Loop *L, AAResults *AA,
201 MemorySSAUpdater *MSSAU);
202};
203
204struct LegacyLICMPass : public LoopPass {
205 static char ID; // Pass identification, replacement for typeid
206 LegacyLICMPass(
207 unsigned LicmMssaOptCap = SetLicmMssaOptCap,
208 unsigned LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap)
209 : LoopPass(ID), LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap) {
210 initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
211 }
212
213 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
214 if (skipLoop(L))
215 return false;
216
217 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
218 MemorySSA *MSSA = EnableMSSALoopDependency
219 ? (&getAnalysis<MemorySSAWrapperPass>().getMSSA())
220 : nullptr;
221 bool hasProfileData = L->getHeader()->getParent()->hasProfileData();
222 BlockFrequencyInfo *BFI =
223 hasProfileData ? &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI()
224 : nullptr;
225 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
226 // pass. Function analyses need to be preserved across loop transformations
227 // but ORE cannot be preserved (see comment before the pass definition).
228 OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
229 return LICM.runOnLoop(
230 L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
231 &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
232 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(), BFI,
233 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
234 *L->getHeader()->getParent()),
235 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
236 *L->getHeader()->getParent()),
237 SE ? &SE->getSE() : nullptr, MSSA, &ORE);
238 }
239
240 /// This transformation requires natural loop information & requires that
241 /// loop preheaders be inserted into the CFG...
242 ///
243 void getAnalysisUsage(AnalysisUsage &AU) const override {
244 AU.addPreserved<DominatorTreeWrapperPass>();
245 AU.addPreserved<LoopInfoWrapperPass>();
246 AU.addRequired<TargetLibraryInfoWrapperPass>();
247 if (EnableMSSALoopDependency) {
248 AU.addRequired<MemorySSAWrapperPass>();
249 AU.addPreserved<MemorySSAWrapperPass>();
250 }
251 AU.addRequired<TargetTransformInfoWrapperPass>();
252 getLoopAnalysisUsage(AU);
253 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
254 AU.addPreserved<LazyBlockFrequencyInfoPass>();
255 AU.addPreserved<LazyBranchProbabilityInfoPass>();
256 }
257
258private:
259 LoopInvariantCodeMotion LICM;
260};
261} // namespace
262
263PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
264 LoopStandardAnalysisResults &AR, LPMUpdater &) {
265 // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
266 // pass. Function analyses need to be preserved across loop transformations
267 // but ORE cannot be preserved (see comment before the pass definition).
268 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
269
270 LoopInvariantCodeMotion LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
271 if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, AR.BFI, &AR.TLI, &AR.TTI,
272 &AR.SE, AR.MSSA, &ORE))
273 return PreservedAnalyses::all();
274
275 auto PA = getLoopPassPreservedAnalyses();
276
277 PA.preserve<DominatorTreeAnalysis>();
278 PA.preserve<LoopAnalysis>();
279 if (AR.MSSA)
280 PA.preserve<MemorySSAAnalysis>();
281
282 return PA;
283}
284
285char LegacyLICMPass::ID = 0;
286INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",static void *initializeLegacyLICMPassPassOnce(PassRegistry &
Registry) {
287 false, false)static void *initializeLegacyLICMPassPassOnce(PassRegistry &
Registry) {
288INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
289INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
290INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
291INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
292INITIALIZE_PASS_DEPENDENCY(LazyBFIPass)initializeLazyBFIPassPass(Registry);
293INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,PassInfo *PI = new PassInfo( "Loop Invariant Code Motion", "licm"
, &LegacyLICMPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LegacyLICMPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLegacyLICMPassPassFlag
; void llvm::initializeLegacyLICMPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegacyLICMPassPassFlag, initializeLegacyLICMPassPassOnce
, std::ref(Registry)); }
294 false)PassInfo *PI = new PassInfo( "Loop Invariant Code Motion", "licm"
, &LegacyLICMPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LegacyLICMPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLegacyLICMPassPassFlag
; void llvm::initializeLegacyLICMPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegacyLICMPassPassFlag, initializeLegacyLICMPassPassOnce
, std::ref(Registry)); }
295
296Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
297Pass *llvm::createLICMPass(unsigned LicmMssaOptCap,
298 unsigned LicmMssaNoAccForPromotionCap) {
299 return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
300}
301
302llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(bool IsSink, Loop *L,
303 MemorySSA *MSSA)
304 : SinkAndHoistLICMFlags(SetLicmMssaOptCap, SetLicmMssaNoAccForPromotionCap,
305 IsSink, L, MSSA) {}
306
307llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(
308 unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink,
309 Loop *L, MemorySSA *MSSA)
310 : LicmMssaOptCap(LicmMssaOptCap),
311 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
312 IsSink(IsSink) {
313 assert(((L != nullptr) == (MSSA != nullptr)) &&((((L != nullptr) == (MSSA != nullptr)) && "Unexpected values for SinkAndHoistLICMFlags"
) ? static_cast<void> (0) : __assert_fail ("((L != nullptr) == (MSSA != nullptr)) && \"Unexpected values for SinkAndHoistLICMFlags\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 314, __PRETTY_FUNCTION__))
314 "Unexpected values for SinkAndHoistLICMFlags")((((L != nullptr) == (MSSA != nullptr)) && "Unexpected values for SinkAndHoistLICMFlags"
) ? static_cast<void> (0) : __assert_fail ("((L != nullptr) == (MSSA != nullptr)) && \"Unexpected values for SinkAndHoistLICMFlags\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 314, __PRETTY_FUNCTION__))
;
315 if (!MSSA)
316 return;
317
318 unsigned AccessCapCount = 0;
319 for (auto *BB : L->getBlocks())
320 if (const auto *Accesses = MSSA->getBlockAccesses(BB))
321 for (const auto &MA : *Accesses) {
322 (void)MA;
323 ++AccessCapCount;
324 if (AccessCapCount > LicmMssaNoAccForPromotionCap) {
325 NoOfMemAccTooLarge = true;
326 return;
327 }
328 }
329}
330
331/// Hoist expressions out of the specified loop. Note, alias info for inner
332/// loop is not preserved so it is not a good idea to run LICM multiple
333/// times on one loop.
334bool LoopInvariantCodeMotion::runOnLoop(
335 Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
336 BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
337 ScalarEvolution *SE, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) {
338 bool Changed = false;
339
340 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.")((L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."
) ? static_cast<void> (0) : __assert_fail ("L->isLCSSAForm(*DT) && \"Loop is not in LCSSA form.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 340, __PRETTY_FUNCTION__))
;
341
342 // If this loop has metadata indicating that LICM is not to be performed then
343 // just exit.
344 if (hasDisableLICMTransformsHint(L)) {
345 return false;
346 }
347
348 std::unique_ptr<AliasSetTracker> CurAST;
349 std::unique_ptr<MemorySSAUpdater> MSSAU;
350 std::unique_ptr<SinkAndHoistLICMFlags> Flags;
351
352 if (!MSSA) {
353 LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Using Alias Set Tracker.\n"
; } } while (false)
;
354 CurAST = collectAliasInfoForLoop(L, LI, AA);
355 Flags = std::make_unique<SinkAndHoistLICMFlags>(
356 LicmMssaOptCap, LicmMssaNoAccForPromotionCap, /*IsSink=*/true);
357 } else {
358 LLVM_DEBUG(dbgs() << "LICM: Using MemorySSA.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Using MemorySSA.\n"; } } while
(false)
;
359 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
360 Flags = std::make_unique<SinkAndHoistLICMFlags>(
361 LicmMssaOptCap, LicmMssaNoAccForPromotionCap, /*IsSink=*/true, L, MSSA);
362 }
363
364 // Get the preheader block to move instructions into...
365 BasicBlock *Preheader = L->getLoopPreheader();
366
367 // Compute loop safety information.
368 ICFLoopSafetyInfo SafetyInfo;
369 SafetyInfo.computeLoopSafetyInfo(L);
370
371 // We want to visit all of the instructions in this loop... that are not parts
372 // of our subloops (they have already had their invariants hoisted out of
373 // their loop, into this loop, so there is no need to process the BODIES of
374 // the subloops).
375 //
376 // Traverse the body of the loop in depth first order on the dominator tree so
377 // that we are guaranteed to see definitions before we see uses. This allows
378 // us to sink instructions in one pass, without iteration. After sinking
379 // instructions, we perform another pass to hoist them out of the loop.
380 if (L->hasDedicatedExits())
381 Changed |=
382 sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, TTI, L,
383 CurAST.get(), MSSAU.get(), &SafetyInfo, *Flags.get(), ORE);
384 Flags->setIsSink(false);
385 if (Preheader)
386 Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, L,
387 CurAST.get(), MSSAU.get(), SE, &SafetyInfo,
388 *Flags.get(), ORE);
389
390 // Now that all loop invariants have been removed from the loop, promote any
391 // memory references to scalars that we can.
392 // Don't sink stores from loops without dedicated block exits. Exits
393 // containing indirect branches are not transformed by loop simplify,
394 // make sure we catch that. An additional load may be generated in the
395 // preheader for SSA updater, so also avoid sinking when no preheader
396 // is available.
397 if (!DisablePromotion && Preheader && L->hasDedicatedExits() &&
398 !Flags->tooManyMemoryAccesses()) {
399 // Figure out the loop exits and their insertion points
400 SmallVector<BasicBlock *, 8> ExitBlocks;
401 L->getUniqueExitBlocks(ExitBlocks);
402
403 // We can't insert into a catchswitch.
404 bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
405 return isa<CatchSwitchInst>(Exit->getTerminator());
406 });
407
408 if (!HasCatchSwitch) {
409 SmallVector<Instruction *, 8> InsertPts;
410 SmallVector<MemoryAccess *, 8> MSSAInsertPts;
411 InsertPts.reserve(ExitBlocks.size());
412 if (MSSAU)
413 MSSAInsertPts.reserve(ExitBlocks.size());
414 for (BasicBlock *ExitBlock : ExitBlocks) {
415 InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
416 if (MSSAU)
417 MSSAInsertPts.push_back(nullptr);
418 }
419
420 PredIteratorCache PIC;
421
422 bool Promoted = false;
423
424 // Build an AST using MSSA.
425 if (!CurAST.get())
426 CurAST = collectAliasInfoForLoopWithMSSA(L, AA, MSSAU.get());
427
428 // Loop over all of the alias sets in the tracker object.
429 for (AliasSet &AS : *CurAST) {
430 // We can promote this alias set if it has a store, if it is a "Must"
431 // alias set, if the pointer is loop invariant, and if we are not
432 // eliminating any volatile loads or stores.
433 if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
434 !L->isLoopInvariant(AS.begin()->getValue()))
435 continue;
436
437 assert(((!AS.empty() && "Must alias set should have at least one pointer element in it!"
) ? static_cast<void> (0) : __assert_fail ("!AS.empty() && \"Must alias set should have at least one pointer element in it!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 439, __PRETTY_FUNCTION__))
438 !AS.empty() &&((!AS.empty() && "Must alias set should have at least one pointer element in it!"
) ? static_cast<void> (0) : __assert_fail ("!AS.empty() && \"Must alias set should have at least one pointer element in it!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 439, __PRETTY_FUNCTION__))
439 "Must alias set should have at least one pointer element in it!")((!AS.empty() && "Must alias set should have at least one pointer element in it!"
) ? static_cast<void> (0) : __assert_fail ("!AS.empty() && \"Must alias set should have at least one pointer element in it!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 439, __PRETTY_FUNCTION__))
;
440
441 SmallSetVector<Value *, 8> PointerMustAliases;
442 for (const auto &ASI : AS)
443 PointerMustAliases.insert(ASI.getValue());
444
445 Promoted |= promoteLoopAccessesToScalars(
446 PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC, LI,
447 DT, TLI, L, CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
448 }
449
450 // Once we have promoted values across the loop body we have to
451 // recursively reform LCSSA as any nested loop may now have values defined
452 // within the loop used in the outer loop.
453 // FIXME: This is really heavy handed. It would be a bit better to use an
454 // SSAUpdater strategy during promotion that was LCSSA aware and reformed
455 // it as it went.
456 if (Promoted)
457 formLCSSARecursively(*L, *DT, LI, SE);
458
459 Changed |= Promoted;
460 }
461 }
462
463 // Check that neither this loop nor its parent have had LCSSA broken. LICM is
464 // specifically moving instructions across the loop boundary and so it is
465 // especially in need of sanity checking here.
466 assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!")((L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!"
) ? static_cast<void> (0) : __assert_fail ("L->isLCSSAForm(*DT) && \"Loop not left in LCSSA form after LICM!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 466, __PRETTY_FUNCTION__))
;
467 assert((L->isOutermost() || L->getParentLoop()->isLCSSAForm(*DT)) &&(((L->isOutermost() || L->getParentLoop()->isLCSSAForm
(*DT)) && "Parent loop not left in LCSSA form after LICM!"
) ? static_cast<void> (0) : __assert_fail ("(L->isOutermost() || L->getParentLoop()->isLCSSAForm(*DT)) && \"Parent loop not left in LCSSA form after LICM!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 468, __PRETTY_FUNCTION__))
468 "Parent loop not left in LCSSA form after LICM!")(((L->isOutermost() || L->getParentLoop()->isLCSSAForm
(*DT)) && "Parent loop not left in LCSSA form after LICM!"
) ? static_cast<void> (0) : __assert_fail ("(L->isOutermost() || L->getParentLoop()->isLCSSAForm(*DT)) && \"Parent loop not left in LCSSA form after LICM!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 468, __PRETTY_FUNCTION__))
;
469
470 if (MSSAU.get() && VerifyMemorySSA)
471 MSSAU->getMemorySSA()->verifyMemorySSA();
472
473 if (Changed && SE)
474 SE->forgetLoopDispositions(L);
475 return Changed;
476}
477
478/// Walk the specified region of the CFG (defined by all blocks dominated by
479/// the specified block, and that are in the current loop) in reverse depth
480/// first order w.r.t the DominatorTree. This allows us to visit uses before
481/// definitions, allowing us to sink a loop body in one pass without iteration.
482///
483bool llvm::sinkRegion(DomTreeNode *N, AAResults *AA, LoopInfo *LI,
484 DominatorTree *DT, BlockFrequencyInfo *BFI,
485 TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
486 Loop *CurLoop, AliasSetTracker *CurAST,
487 MemorySSAUpdater *MSSAU, ICFLoopSafetyInfo *SafetyInfo,
488 SinkAndHoistLICMFlags &Flags,
489 OptimizationRemarkEmitter *ORE) {
490
491 // Verify inputs.
492 assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to sinkRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to sinkRegion.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 494, __PRETTY_FUNCTION__))
493 CurLoop != nullptr && SafetyInfo != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to sinkRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to sinkRegion.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 494, __PRETTY_FUNCTION__))
494 "Unexpected input to sinkRegion.")((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to sinkRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to sinkRegion.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 494, __PRETTY_FUNCTION__))
;
495 assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 496, __PRETTY_FUNCTION__))
496 "Either AliasSetTracker or MemorySSA should be initialized.")((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 496, __PRETTY_FUNCTION__))
;
497
498 // We want to visit children before parents. We will enque all the parents
499 // before their children in the worklist and process the worklist in reverse
500 // order.
501 SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, CurLoop);
502
503 bool Changed = false;
504 for (DomTreeNode *DTN : reverse(Worklist)) {
505 BasicBlock *BB = DTN->getBlock();
506 // Only need to process the contents of this block if it is not part of a
507 // subloop (which would already have been processed).
508 if (inSubLoop(BB, CurLoop, LI))
509 continue;
510
511 for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
512 Instruction &I = *--II;
513
514 // If the instruction is dead, we would try to sink it because it isn't
515 // used in the loop, instead, just delete it.
516 if (isInstructionTriviallyDead(&I, TLI)) {
517 LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM deleting dead inst: " <<
I << '\n'; } } while (false)
;
518 salvageKnowledge(&I);
519 salvageDebugInfo(I);
520 ++II;
521 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
522 Changed = true;
523 continue;
524 }
525
526 // Check to see if we can sink this instruction to the exit blocks
527 // of the loop. We can do this if the all users of the instruction are
528 // outside of the loop. In this case, it doesn't even matter if the
529 // operands of the instruction are loop invariant.
530 //
531 bool FreeInLoop = false;
532 if (!I.mayHaveSideEffects() &&
533 isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
534 canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
535 ORE)) {
536 if (sink(I, LI, DT, BFI, CurLoop, SafetyInfo, MSSAU, ORE)) {
537 if (!FreeInLoop) {
538 ++II;
539 salvageDebugInfo(I);
540 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
541 }
542 Changed = true;
543 }
544 }
545 }
546 }
547 if (MSSAU && VerifyMemorySSA)
548 MSSAU->getMemorySSA()->verifyMemorySSA();
549 return Changed;
550}
551
552namespace {
553// This is a helper class for hoistRegion to make it able to hoist control flow
554// in order to be able to hoist phis. The way this works is that we initially
555// start hoisting to the loop preheader, and when we see a loop invariant branch
556// we make note of this. When we then come to hoist an instruction that's
557// conditional on such a branch we duplicate the branch and the relevant control
558// flow, then hoist the instruction into the block corresponding to its original
559// block in the duplicated control flow.
560class ControlFlowHoister {
561private:
562 // Information about the loop we are hoisting from
563 LoopInfo *LI;
564 DominatorTree *DT;
565 Loop *CurLoop;
566 MemorySSAUpdater *MSSAU;
567
568 // A map of blocks in the loop to the block their instructions will be hoisted
569 // to.
570 DenseMap<BasicBlock *, BasicBlock *> HoistDestinationMap;
571
572 // The branches that we can hoist, mapped to the block that marks a
573 // convergence point of their control flow.
574 DenseMap<BranchInst *, BasicBlock *> HoistableBranches;
575
576public:
577 ControlFlowHoister(LoopInfo *LI, DominatorTree *DT, Loop *CurLoop,
578 MemorySSAUpdater *MSSAU)
579 : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
580
581 void registerPossiblyHoistableBranch(BranchInst *BI) {
582 // We can only hoist conditional branches with loop invariant operands.
583 if (!ControlFlowHoisting || !BI->isConditional() ||
584 !CurLoop->hasLoopInvariantOperands(BI))
585 return;
586
587 // The branch destinations need to be in the loop, and we don't gain
588 // anything by duplicating conditional branches with duplicate successors,
589 // as it's essentially the same as an unconditional branch.
590 BasicBlock *TrueDest = BI->getSuccessor(0);
591 BasicBlock *FalseDest = BI->getSuccessor(1);
592 if (!CurLoop->contains(TrueDest) || !CurLoop->contains(FalseDest) ||
593 TrueDest == FalseDest)
594 return;
595
596 // We can hoist BI if one branch destination is the successor of the other,
597 // or both have common successor which we check by seeing if the
598 // intersection of their successors is non-empty.
599 // TODO: This could be expanded to allowing branches where both ends
600 // eventually converge to a single block.
601 SmallPtrSet<BasicBlock *, 4> TrueDestSucc, FalseDestSucc;
602 TrueDestSucc.insert(succ_begin(TrueDest), succ_end(TrueDest));
603 FalseDestSucc.insert(succ_begin(FalseDest), succ_end(FalseDest));
604 BasicBlock *CommonSucc = nullptr;
605 if (TrueDestSucc.count(FalseDest)) {
606 CommonSucc = FalseDest;
607 } else if (FalseDestSucc.count(TrueDest)) {
608 CommonSucc = TrueDest;
609 } else {
610 set_intersect(TrueDestSucc, FalseDestSucc);
611 // If there's one common successor use that.
612 if (TrueDestSucc.size() == 1)
613 CommonSucc = *TrueDestSucc.begin();
614 // If there's more than one pick whichever appears first in the block list
615 // (we can't use the value returned by TrueDestSucc.begin() as it's
616 // unpredicatable which element gets returned).
617 else if (!TrueDestSucc.empty()) {
618 Function *F = TrueDest->getParent();
619 auto IsSucc = [&](BasicBlock &BB) { return TrueDestSucc.count(&BB); };
620 auto It = std::find_if(F->begin(), F->end(), IsSucc);
621 assert(It != F->end() && "Could not find successor in function")((It != F->end() && "Could not find successor in function"
) ? static_cast<void> (0) : __assert_fail ("It != F->end() && \"Could not find successor in function\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 621, __PRETTY_FUNCTION__))
;
622 CommonSucc = &*It;
623 }
624 }
625 // The common successor has to be dominated by the branch, as otherwise
626 // there will be some other path to the successor that will not be
627 // controlled by this branch so any phi we hoist would be controlled by the
628 // wrong condition. This also takes care of avoiding hoisting of loop back
629 // edges.
630 // TODO: In some cases this could be relaxed if the successor is dominated
631 // by another block that's been hoisted and we can guarantee that the
632 // control flow has been replicated exactly.
633 if (CommonSucc && DT->dominates(BI, CommonSucc))
634 HoistableBranches[BI] = CommonSucc;
635 }
636
637 bool canHoistPHI(PHINode *PN) {
638 // The phi must have loop invariant operands.
639 if (!ControlFlowHoisting || !CurLoop->hasLoopInvariantOperands(PN))
640 return false;
641 // We can hoist phis if the block they are in is the target of hoistable
642 // branches which cover all of the predecessors of the block.
643 SmallPtrSet<BasicBlock *, 8> PredecessorBlocks;
644 BasicBlock *BB = PN->getParent();
645 for (BasicBlock *PredBB : predecessors(BB))
646 PredecessorBlocks.insert(PredBB);
647 // If we have less predecessor blocks than predecessors then the phi will
648 // have more than one incoming value for the same block which we can't
649 // handle.
650 // TODO: This could be handled be erasing some of the duplicate incoming
651 // values.
652 if (PredecessorBlocks.size() != pred_size(BB))
653 return false;
654 for (auto &Pair : HoistableBranches) {
655 if (Pair.second == BB) {
656 // Which blocks are predecessors via this branch depends on if the
657 // branch is triangle-like or diamond-like.
658 if (Pair.first->getSuccessor(0) == BB) {
659 PredecessorBlocks.erase(Pair.first->getParent());
660 PredecessorBlocks.erase(Pair.first->getSuccessor(1));
661 } else if (Pair.first->getSuccessor(1) == BB) {
662 PredecessorBlocks.erase(Pair.first->getParent());
663 PredecessorBlocks.erase(Pair.first->getSuccessor(0));
664 } else {
665 PredecessorBlocks.erase(Pair.first->getSuccessor(0));
666 PredecessorBlocks.erase(Pair.first->getSuccessor(1));
667 }
668 }
669 }
670 // PredecessorBlocks will now be empty if for every predecessor of BB we
671 // found a hoistable branch source.
672 return PredecessorBlocks.empty();
673 }
674
675 BasicBlock *getOrCreateHoistedBlock(BasicBlock *BB) {
676 if (!ControlFlowHoisting)
677 return CurLoop->getLoopPreheader();
678 // If BB has already been hoisted, return that
679 if (HoistDestinationMap.count(BB))
680 return HoistDestinationMap[BB];
681
682 // Check if this block is conditional based on a pending branch
683 auto HasBBAsSuccessor =
684 [&](DenseMap<BranchInst *, BasicBlock *>::value_type &Pair) {
685 return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
686 Pair.first->getSuccessor(1) == BB);
687 };
688 auto It = std::find_if(HoistableBranches.begin(), HoistableBranches.end(),
689 HasBBAsSuccessor);
690
691 // If not involved in a pending branch, hoist to preheader
692 BasicBlock *InitialPreheader = CurLoop->getLoopPreheader();
693 if (It == HoistableBranches.end()) {
694 LLVM_DEBUG(dbgs() << "LICM using " << InitialPreheader->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM using " << InitialPreheader
->getName() << " as hoist destination for " <<
BB->getName() << "\n"; } } while (false)
695 << " as hoist destination for " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM using " << InitialPreheader
->getName() << " as hoist destination for " <<
BB->getName() << "\n"; } } while (false)
696 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM using " << InitialPreheader
->getName() << " as hoist destination for " <<
BB->getName() << "\n"; } } while (false)
;
697 HoistDestinationMap[BB] = InitialPreheader;
698 return InitialPreheader;
699 }
700 BranchInst *BI = It->first;
701 assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==((std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor
) == HoistableBranches.end() && "BB is expected to be the target of at most one branch"
) ? static_cast<void> (0) : __assert_fail ("std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) == HoistableBranches.end() && \"BB is expected to be the target of at most one branch\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 703, __PRETTY_FUNCTION__))
702 HoistableBranches.end() &&((std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor
) == HoistableBranches.end() && "BB is expected to be the target of at most one branch"
) ? static_cast<void> (0) : __assert_fail ("std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) == HoistableBranches.end() && \"BB is expected to be the target of at most one branch\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 703, __PRETTY_FUNCTION__))
703 "BB is expected to be the target of at most one branch")((std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor
) == HoistableBranches.end() && "BB is expected to be the target of at most one branch"
) ? static_cast<void> (0) : __assert_fail ("std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) == HoistableBranches.end() && \"BB is expected to be the target of at most one branch\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 703, __PRETTY_FUNCTION__))
;
704
705 LLVMContext &C = BB->getContext();
706 BasicBlock *TrueDest = BI->getSuccessor(0);
707 BasicBlock *FalseDest = BI->getSuccessor(1);
708 BasicBlock *CommonSucc = HoistableBranches[BI];
709 BasicBlock *HoistTarget = getOrCreateHoistedBlock(BI->getParent());
710
711 // Create hoisted versions of blocks that currently don't have them
712 auto CreateHoistedBlock = [&](BasicBlock *Orig) {
713 if (HoistDestinationMap.count(Orig))
714 return HoistDestinationMap[Orig];
715 BasicBlock *New =
716 BasicBlock::Create(C, Orig->getName() + ".licm", Orig->getParent());
717 HoistDestinationMap[Orig] = New;
718 DT->addNewBlock(New, HoistTarget);
719 if (CurLoop->getParentLoop())
720 CurLoop->getParentLoop()->addBasicBlockToLoop(New, *LI);
721 ++NumCreatedBlocks;
722 LLVM_DEBUG(dbgs() << "LICM created " << New->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM created " << New->
getName() << " as hoist destination for " << Orig
->getName() << "\n"; } } while (false)
723 << " as hoist destination for " << Orig->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM created " << New->
getName() << " as hoist destination for " << Orig
->getName() << "\n"; } } while (false)
724 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM created " << New->
getName() << " as hoist destination for " << Orig
->getName() << "\n"; } } while (false)
;
725 return New;
726 };
727 BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
728 BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
729 BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
730
731 // Link up these blocks with branches.
732 if (!HoistCommonSucc->getTerminator()) {
733 // The new common successor we've generated will branch to whatever that
734 // hoist target branched to.
735 BasicBlock *TargetSucc = HoistTarget->getSingleSuccessor();
736 assert(TargetSucc && "Expected hoist target to have a single successor")((TargetSucc && "Expected hoist target to have a single successor"
) ? static_cast<void> (0) : __assert_fail ("TargetSucc && \"Expected hoist target to have a single successor\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 736, __PRETTY_FUNCTION__))
;
737 HoistCommonSucc->moveBefore(TargetSucc);
738 BranchInst::Create(TargetSucc, HoistCommonSucc);
739 }
740 if (!HoistTrueDest->getTerminator()) {
741 HoistTrueDest->moveBefore(HoistCommonSucc);
742 BranchInst::Create(HoistCommonSucc, HoistTrueDest);
743 }
744 if (!HoistFalseDest->getTerminator()) {
745 HoistFalseDest->moveBefore(HoistCommonSucc);
746 BranchInst::Create(HoistCommonSucc, HoistFalseDest);
747 }
748
749 // If BI is being cloned to what was originally the preheader then
750 // HoistCommonSucc will now be the new preheader.
751 if (HoistTarget == InitialPreheader) {
752 // Phis in the loop header now need to use the new preheader.
753 InitialPreheader->replaceSuccessorsPhiUsesWith(HoistCommonSucc);
754 if (MSSAU)
755 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
756 HoistTarget->getSingleSuccessor(), HoistCommonSucc, {HoistTarget});
757 // The new preheader dominates the loop header.
758 DomTreeNode *PreheaderNode = DT->getNode(HoistCommonSucc);
759 DomTreeNode *HeaderNode = DT->getNode(CurLoop->getHeader());
760 DT->changeImmediateDominator(HeaderNode, PreheaderNode);
761 // The preheader hoist destination is now the new preheader, with the
762 // exception of the hoist destination of this branch.
763 for (auto &Pair : HoistDestinationMap)
764 if (Pair.second == InitialPreheader && Pair.first != BI->getParent())
765 Pair.second = HoistCommonSucc;
766 }
767
768 // Now finally clone BI.
769 ReplaceInstWithInst(
770 HoistTarget->getTerminator(),
771 BranchInst::Create(HoistTrueDest, HoistFalseDest, BI->getCondition()));
772 ++NumClonedBranches;
773
774 assert(CurLoop->getLoopPreheader() &&((CurLoop->getLoopPreheader() && "Hoisting blocks should not have destroyed preheader"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->getLoopPreheader() && \"Hoisting blocks should not have destroyed preheader\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 775, __PRETTY_FUNCTION__))
775 "Hoisting blocks should not have destroyed preheader")((CurLoop->getLoopPreheader() && "Hoisting blocks should not have destroyed preheader"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->getLoopPreheader() && \"Hoisting blocks should not have destroyed preheader\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 775, __PRETTY_FUNCTION__))
;
776 return HoistDestinationMap[BB];
777 }
778};
779} // namespace
780
781// Hoisting/sinking instruction out of a loop isn't always beneficial. It's only
782// only worthwhile if the destination block is actually colder than current
783// block.
784static bool worthSinkOrHoistInst(Instruction &I, BasicBlock *DstBlock,
785 OptimizationRemarkEmitter *ORE,
786 BlockFrequencyInfo *BFI) {
787 // Check block frequency only when runtime profile is available
788 // to avoid pathological cases. With static profile, lean towards
789 // hosting because it helps canonicalize the loop for vectorizer.
790 if (!DstBlock->getParent()->hasProfileData())
791 return true;
792
793 if (!HoistSinkColdnessThreshold || !BFI)
794 return true;
795
796 BasicBlock *SrcBlock = I.getParent();
797 if (BFI->getBlockFreq(DstBlock).getFrequency() / HoistSinkColdnessThreshold >
798 BFI->getBlockFreq(SrcBlock).getFrequency()) {
799 ORE->emit([&]() {
800 return OptimizationRemarkMissed(DEBUG_TYPE"licm", "SinkHoistInst", &I)
801 << "failed to sink or hoist instruction because containing block "
802 "has lower frequency than destination block";
803 });
804 return false;
805 }
806
807 return true;
808}
809
810/// Walk the specified region of the CFG (defined by all blocks dominated by
811/// the specified block, and that are in the current loop) in depth first
812/// order w.r.t the DominatorTree. This allows us to visit definitions before
813/// uses, allowing us to hoist a loop body in one pass without iteration.
814///
815bool llvm::hoistRegion(DomTreeNode *N, AAResults *AA, LoopInfo *LI,
816 DominatorTree *DT, BlockFrequencyInfo *BFI,
817 TargetLibraryInfo *TLI, Loop *CurLoop,
818 AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
819 ScalarEvolution *SE, ICFLoopSafetyInfo *SafetyInfo,
820 SinkAndHoistLICMFlags &Flags,
821 OptimizationRemarkEmitter *ORE) {
822 // Verify inputs.
823 assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to hoistRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to hoistRegion.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 825, __PRETTY_FUNCTION__))
824 CurLoop != nullptr && SafetyInfo != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to hoistRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to hoistRegion.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 825, __PRETTY_FUNCTION__))
825 "Unexpected input to hoistRegion.")((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to hoistRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to hoistRegion.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 825, __PRETTY_FUNCTION__))
;
826 assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 827, __PRETTY_FUNCTION__))
827 "Either AliasSetTracker or MemorySSA should be initialized.")((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 827, __PRETTY_FUNCTION__))
;
828
829 ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
830
831 // Keep track of instructions that have been hoisted, as they may need to be
832 // re-hoisted if they end up not dominating all of their uses.
833 SmallVector<Instruction *, 16> HoistedInstructions;
834
835 // For PHI hoisting to work we need to hoist blocks before their successors.
836 // We can do this by iterating through the blocks in the loop in reverse
837 // post-order.
838 LoopBlocksRPO Worklist(CurLoop);
839 Worklist.perform(LI);
840 bool Changed = false;
841 for (BasicBlock *BB : Worklist) {
842 // Only need to process the contents of this block if it is not part of a
843 // subloop (which would already have been processed).
844 if (inSubLoop(BB, CurLoop, LI))
845 continue;
846
847 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
848 Instruction &I = *II++;
849 // Try constant folding this instruction. If all the operands are
850 // constants, it is technically hoistable, but it would be better to
851 // just fold it.
852 if (Constant *C = ConstantFoldInstruction(
853 &I, I.getModule()->getDataLayout(), TLI)) {
854 LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *Cdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM folding inst: " << I <<
" --> " << *C << '\n'; } } while (false)
855 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM folding inst: " << I <<
" --> " << *C << '\n'; } } while (false)
;
856 if (CurAST)
857 CurAST->copyValue(&I, C);
858 // FIXME MSSA: Such replacements may make accesses unoptimized (D51960).
859 I.replaceAllUsesWith(C);
860 if (isInstructionTriviallyDead(&I, TLI))
861 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
862 Changed = true;
863 continue;
864 }
865
866 // Try hoisting the instruction out to the preheader. We can only do
867 // this if all of the operands of the instruction are loop invariant and
868 // if it is safe to hoist the instruction. We also check block frequency
869 // to make sure instruction only gets hoisted into colder blocks.
870 // TODO: It may be safe to hoist if we are hoisting to a conditional block
871 // and we have accurately duplicated the control flow from the loop header
872 // to that block.
873 if (CurLoop->hasLoopInvariantOperands(&I) &&
874 canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
875 ORE) &&
876 worthSinkOrHoistInst(I, CurLoop->getLoopPreheader(), ORE, BFI) &&
877 isSafeToExecuteUnconditionally(
878 I, DT, CurLoop, SafetyInfo, ORE,
879 CurLoop->getLoopPreheader()->getTerminator())) {
880 hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
881 MSSAU, SE, ORE);
882 HoistedInstructions.push_back(&I);
883 Changed = true;
884 continue;
885 }
886
887 // Attempt to remove floating point division out of the loop by
888 // converting it to a reciprocal multiplication.
889 if (I.getOpcode() == Instruction::FDiv && I.hasAllowReciprocal() &&
890 CurLoop->isLoopInvariant(I.getOperand(1))) {
891 auto Divisor = I.getOperand(1);
892 auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
893 auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
894 ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
895 SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
896 ReciprocalDivisor->insertBefore(&I);
897
898 auto Product =
899 BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
900 Product->setFastMathFlags(I.getFastMathFlags());
901 SafetyInfo->insertInstructionTo(Product, I.getParent());
902 Product->insertAfter(&I);
903 I.replaceAllUsesWith(Product);
904 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
905
906 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
907 SafetyInfo, MSSAU, SE, ORE);
908 HoistedInstructions.push_back(ReciprocalDivisor);
909 Changed = true;
910 continue;
911 }
912
913 auto IsInvariantStart = [&](Instruction &I) {
914 using namespace PatternMatch;
915 return I.use_empty() &&
916 match(&I, m_Intrinsic<Intrinsic::invariant_start>());
917 };
918 auto MustExecuteWithoutWritesBefore = [&](Instruction &I) {
919 return SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop) &&
920 SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop);
921 };
922 if ((IsInvariantStart(I) || isGuard(&I)) &&
923 CurLoop->hasLoopInvariantOperands(&I) &&
924 MustExecuteWithoutWritesBefore(I)) {
925 hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
926 MSSAU, SE, ORE);
927 HoistedInstructions.push_back(&I);
928 Changed = true;
929 continue;
930 }
931
932 if (PHINode *PN = dyn_cast<PHINode>(&I)) {
933 if (CFH.canHoistPHI(PN)) {
934 // Redirect incoming blocks first to ensure that we create hoisted
935 // versions of those blocks before we hoist the phi.
936 for (unsigned int i = 0; i < PN->getNumIncomingValues(); ++i)
937 PN->setIncomingBlock(
938 i, CFH.getOrCreateHoistedBlock(PN->getIncomingBlock(i)));
939 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
940 MSSAU, SE, ORE);
941 assert(DT->dominates(PN, BB) && "Conditional PHIs not expected")((DT->dominates(PN, BB) && "Conditional PHIs not expected"
) ? static_cast<void> (0) : __assert_fail ("DT->dominates(PN, BB) && \"Conditional PHIs not expected\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 941, __PRETTY_FUNCTION__))
;
942 Changed = true;
943 continue;
944 }
945 }
946
947 // Remember possibly hoistable branches so we can actually hoist them
948 // later if needed.
949 if (BranchInst *BI = dyn_cast<BranchInst>(&I))
950 CFH.registerPossiblyHoistableBranch(BI);
951 }
952 }
953
954 // If we hoisted instructions to a conditional block they may not dominate
955 // their uses that weren't hoisted (such as phis where some operands are not
956 // loop invariant). If so make them unconditional by moving them to their
957 // immediate dominator. We iterate through the instructions in reverse order
958 // which ensures that when we rehoist an instruction we rehoist its operands,
959 // and also keep track of where in the block we are rehoisting to to make sure
960 // that we rehoist instructions before the instructions that use them.
961 Instruction *HoistPoint = nullptr;
962 if (ControlFlowHoisting) {
963 for (Instruction *I : reverse(HoistedInstructions)) {
964 if (!llvm::all_of(I->uses(),
965 [&](Use &U) { return DT->dominates(I, U); })) {
966 BasicBlock *Dominator =
967 DT->getNode(I->getParent())->getIDom()->getBlock();
968 if (!HoistPoint || !DT->dominates(HoistPoint->getParent(), Dominator)) {
969 if (HoistPoint)
970 assert(DT->dominates(Dominator, HoistPoint->getParent()) &&((DT->dominates(Dominator, HoistPoint->getParent()) &&
"New hoist point expected to dominate old hoist point") ? static_cast
<void> (0) : __assert_fail ("DT->dominates(Dominator, HoistPoint->getParent()) && \"New hoist point expected to dominate old hoist point\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 971, __PRETTY_FUNCTION__))
971 "New hoist point expected to dominate old hoist point")((DT->dominates(Dominator, HoistPoint->getParent()) &&
"New hoist point expected to dominate old hoist point") ? static_cast
<void> (0) : __assert_fail ("DT->dominates(Dominator, HoistPoint->getParent()) && \"New hoist point expected to dominate old hoist point\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 971, __PRETTY_FUNCTION__))
;
972 HoistPoint = Dominator->getTerminator();
973 }
974 LLVM_DEBUG(dbgs() << "LICM rehoisting to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM rehoisting to " << HoistPoint
->getParent()->getName() << ": " << *I <<
"\n"; } } while (false)
975 << HoistPoint->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM rehoisting to " << HoistPoint
->getParent()->getName() << ": " << *I <<
"\n"; } } while (false)
976 << ": " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM rehoisting to " << HoistPoint
->getParent()->getName() << ": " << *I <<
"\n"; } } while (false)
;
977 moveInstructionBefore(*I, *HoistPoint, *SafetyInfo, MSSAU, SE);
978 HoistPoint = I;
979 Changed = true;
980 }
981 }
982 }
983 if (MSSAU && VerifyMemorySSA)
984 MSSAU->getMemorySSA()->verifyMemorySSA();
985
986 // Now that we've finished hoisting make sure that LI and DT are still
987 // valid.
988#ifdef EXPENSIVE_CHECKS
989 if (Changed) {
990 assert(DT->verify(DominatorTree::VerificationLevel::Fast) &&((DT->verify(DominatorTree::VerificationLevel::Fast) &&
"Dominator tree verification failed") ? static_cast<void>
(0) : __assert_fail ("DT->verify(DominatorTree::VerificationLevel::Fast) && \"Dominator tree verification failed\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 991, __PRETTY_FUNCTION__))
991 "Dominator tree verification failed")((DT->verify(DominatorTree::VerificationLevel::Fast) &&
"Dominator tree verification failed") ? static_cast<void>
(0) : __assert_fail ("DT->verify(DominatorTree::VerificationLevel::Fast) && \"Dominator tree verification failed\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 991, __PRETTY_FUNCTION__))
;
992 LI->verify(*DT);
993 }
994#endif
995
996 return Changed;
997}
998
999// Return true if LI is invariant within scope of the loop. LI is invariant if
1000// CurLoop is dominated by an invariant.start representing the same memory
1001// location and size as the memory location LI loads from, and also the
1002// invariant.start has no uses.
1003static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT,
1004 Loop *CurLoop) {
1005 Value *Addr = LI->getOperand(0);
1006 const DataLayout &DL = LI->getModule()->getDataLayout();
1007 const TypeSize LocSizeInBits = DL.getTypeSizeInBits(LI->getType());
1008
1009 // It is not currently possible for clang to generate an invariant.start
1010 // intrinsic with scalable vector types because we don't support thread local
1011 // sizeless types and we don't permit sizeless types in structs or classes.
1012 // Furthermore, even if support is added for this in future the intrinsic
1013 // itself is defined to have a size of -1 for variable sized objects. This
1014 // makes it impossible to verify if the intrinsic envelops our region of
1015 // interest. For example, both <vscale x 32 x i8> and <vscale x 16 x i8>
1016 // types would have a -1 parameter, but the former is clearly double the size
1017 // of the latter.
1018 if (LocSizeInBits.isScalable())
1019 return false;
1020
1021 // if the type is i8 addrspace(x)*, we know this is the type of
1022 // llvm.invariant.start operand
1023 auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
1024 LI->getPointerAddressSpace());
1025 unsigned BitcastsVisited = 0;
1026 // Look through bitcasts until we reach the i8* type (this is invariant.start
1027 // operand type).
1028 while (Addr->getType() != PtrInt8Ty) {
1029 auto *BC = dyn_cast<BitCastInst>(Addr);
1030 // Avoid traversing high number of bitcast uses.
1031 if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
1032 return false;
1033 Addr = BC->getOperand(0);
1034 }
1035
1036 unsigned UsesVisited = 0;
1037 // Traverse all uses of the load operand value, to see if invariant.start is
1038 // one of the uses, and whether it dominates the load instruction.
1039 for (auto *U : Addr->users()) {
1040 // Avoid traversing for Load operand with high number of users.
1041 if (++UsesVisited > MaxNumUsesTraversed)
1042 return false;
1043 IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
1044 // If there are escaping uses of invariant.start instruction, the load maybe
1045 // non-invariant.
1046 if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
1047 !II->use_empty())
1048 continue;
1049 ConstantInt *InvariantSize = cast<ConstantInt>(II->getArgOperand(0));
1050 // The intrinsic supports having a -1 argument for variable sized objects
1051 // so we should check for that here.
1052 if (InvariantSize->isNegative())
1053 continue;
1054 uint64_t InvariantSizeInBits = InvariantSize->getSExtValue() * 8;
1055 // Confirm the invariant.start location size contains the load operand size
1056 // in bits. Also, the invariant.start should dominate the load, and we
1057 // should not hoist the load out of a loop that contains this dominating
1058 // invariant.start.
1059 if (LocSizeInBits.getFixedSize() <= InvariantSizeInBits &&
1060 DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
1061 return true;
1062 }
1063
1064 return false;
1065}
1066
1067namespace {
1068/// Return true if-and-only-if we know how to (mechanically) both hoist and
1069/// sink a given instruction out of a loop. Does not address legality
1070/// concerns such as aliasing or speculation safety.
1071bool isHoistableAndSinkableInst(Instruction &I) {
1072 // Only these instructions are hoistable/sinkable.
1073 return (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
5
Assuming 'I' is a 'LoadInst'
6
Returning the value 1, which participates in a condition later
1074 isa<FenceInst>(I) || isa<CastInst>(I) || isa<UnaryOperator>(I) ||
1075 isa<BinaryOperator>(I) || isa<SelectInst>(I) ||
1076 isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
1077 isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
1078 isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
1079 isa<InsertValueInst>(I) || isa<FreezeInst>(I));
1080}
1081/// Return true if all of the alias sets within this AST are known not to
1082/// contain a Mod, or if MSSA knows thare are no MemoryDefs in the loop.
1083bool isReadOnly(AliasSetTracker *CurAST, const MemorySSAUpdater *MSSAU,
1084 const Loop *L) {
1085 if (CurAST) {
1086 for (AliasSet &AS : *CurAST) {
1087 if (!AS.isForwardingAliasSet() && AS.isMod()) {
1088 return false;
1089 }
1090 }
1091 return true;
1092 } else { /*MSSAU*/
1093 for (auto *BB : L->getBlocks())
1094 if (MSSAU->getMemorySSA()->getBlockDefs(BB))
1095 return false;
1096 return true;
1097 }
1098}
1099
1100/// Return true if I is the only Instruction with a MemoryAccess in L.
1101bool isOnlyMemoryAccess(const Instruction *I, const Loop *L,
1102 const MemorySSAUpdater *MSSAU) {
1103 for (auto *BB : L->getBlocks())
1104 if (auto *Accs = MSSAU->getMemorySSA()->getBlockAccesses(BB)) {
1105 int NotAPhi = 0;
1106 for (const auto &Acc : *Accs) {
1107 if (isa<MemoryPhi>(&Acc))
1108 continue;
1109 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1110 if (MUD->getMemoryInst() != I || NotAPhi++ == 1)
1111 return false;
1112 }
1113 }
1114 return true;
1115}
1116}
1117
1118bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
1119 Loop *CurLoop, AliasSetTracker *CurAST,
1120 MemorySSAUpdater *MSSAU,
1121 bool TargetExecutesOncePerLoop,
1122 SinkAndHoistLICMFlags *Flags,
1123 OptimizationRemarkEmitter *ORE) {
1124 assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1125, __PRETTY_FUNCTION__))
1
Assuming pointer value is null
2
Assuming the condition is true
3
'?' condition is true
1125 "Either AliasSetTracker or MemorySSA should be initialized.")((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1125, __PRETTY_FUNCTION__))
;
1126
1127 // If we don't understand the instruction, bail early.
1128 if (!isHoistableAndSinkableInst(I))
4
Calling 'isHoistableAndSinkableInst'
7
Returning from 'isHoistableAndSinkableInst'
8
Taking false branch
1129 return false;
1130
1131 MemorySSA *MSSA = MSSAU
8.1
'MSSAU' is non-null
8.1
'MSSAU' is non-null
8.1
'MSSAU' is non-null
8.1
'MSSAU' is non-null
8.1
'MSSAU' is non-null
? MSSAU->getMemorySSA() : nullptr;
9
'?' condition is true
10
'MSSA' initialized here
1132 if (MSSA)
11
Assuming 'MSSA' is null
12
Taking false branch
1133 assert(Flags != nullptr && "Flags cannot be null.")((Flags != nullptr && "Flags cannot be null.") ? static_cast
<void> (0) : __assert_fail ("Flags != nullptr && \"Flags cannot be null.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1133, __PRETTY_FUNCTION__))
;
1134
1135 // Loads have extra constraints we have to verify before we can hoist them.
1136 if (LoadInst *LI
13.1
'LI' is null
13.1
'LI' is null
13.1
'LI' is null
13.1
'LI' is null
13.1
'LI' is null
= dyn_cast<LoadInst>(&I)) {
13
Assuming the object is not a 'LoadInst'
14
Taking false branch
1137 if (!LI->isUnordered())
1138 return false; // Don't sink/hoist volatile or ordered atomic loads!
1139
1140 // Loads from constant memory are always safe to move, even if they end up
1141 // in the same alias set as something that ends up being modified.
1142 if (AA->pointsToConstantMemory(LI->getOperand(0)))
1143 return true;
1144 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1145 return true;
1146
1147 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1148 return false; // Don't risk duplicating unordered loads
1149
1150 // This checks for an invariant.start dominating the load.
1151 if (isLoadInvariantInLoop(LI, DT, CurLoop))
1152 return true;
1153
1154 bool Invalidated;
1155 if (CurAST)
1156 Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
1157 CurLoop, AA);
1158 else
1159 Invalidated = pointerInvalidatedByLoopWithMSSA(
1160 MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, I, *Flags);
1161 // Check loop-invariant address because this may also be a sinkable load
1162 // whose address is not necessarily loop-invariant.
1163 if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1164 ORE->emit([&]() {
1165 return OptimizationRemarkMissed(
1166 DEBUG_TYPE"licm", "LoadWithLoopInvariantAddressInvalidated", LI)
1167 << "failed to move load with loop-invariant address "
1168 "because the loop may invalidate its value";
1169 });
1170
1171 return !Invalidated;
1172 } else if (CallInst *CI
15.1
'CI' is non-null
15.1
'CI' is non-null
15.1
'CI' is non-null
15.1
'CI' is non-null
15.1
'CI' is non-null
= dyn_cast<CallInst>(&I)) {
15
Assuming the object is a 'CallInst'
16
Taking true branch
1173 // Don't sink or hoist dbg info; it's legal, but not useful.
1174 if (isa<DbgInfoIntrinsic>(I))
17
Assuming 'I' is not a 'DbgInfoIntrinsic'
18
Taking false branch
1175 return false;
1176
1177 // Don't sink calls which can throw.
1178 if (CI->mayThrow())
19
Assuming the condition is false
20
Taking false branch
1179 return false;
1180
1181 // Convergent attribute has been used on operations that involve
1182 // inter-thread communication which results are implicitly affected by the
1183 // enclosing control flows. It is not safe to hoist or sink such operations
1184 // across control flow.
1185 if (CI->isConvergent())
21
Calling 'CallBase::isConvergent'
37
Returning from 'CallBase::isConvergent'
38
Assuming the condition is false
39
Taking false branch
1186 return false;
1187
1188 using namespace PatternMatch;
1189 if (match(CI, m_Intrinsic<Intrinsic::assume>()))
40
Calling 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
47
Returning from 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
48
Taking false branch
1190 // Assumes don't actually alias anything or throw
1191 return true;
1192
1193 if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
49
Calling 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
56
Returning from 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
57
Taking false branch
1194 // Widenable conditions don't actually alias anything or throw
1195 return true;
1196
1197 // Handle simple cases by querying alias analysis.
1198 FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
1199 if (Behavior == FMRB_DoesNotAccessMemory)
58
Assuming 'Behavior' is not equal to FMRB_DoesNotAccessMemory
59
Taking false branch
1200 return true;
1201 if (AAResults::onlyReadsMemory(Behavior)) {
60
Calling 'AAResults::onlyReadsMemory'
63
Returning from 'AAResults::onlyReadsMemory'
64
Taking true branch
1202 // A readonly argmemonly function only reads from memory pointed to by
1203 // it's arguments with arbitrary offsets. If we can prove there are no
1204 // writes to this memory in the loop, we can hoist or sink.
1205 if (AAResults::onlyAccessesArgPointees(Behavior)) {
65
Calling 'AAResults::onlyAccessesArgPointees'
68
Returning from 'AAResults::onlyAccessesArgPointees'
69
Taking true branch
1206 // TODO: expand to writeable arguments
1207 for (Value *Op : CI->arg_operands())
70
Assuming '__begin5' is not equal to '__end5'
1208 if (Op->getType()->isPointerTy()) {
71
Calling 'Type::isPointerTy'
74
Returning from 'Type::isPointerTy'
75
Taking true branch
1209 bool Invalidated;
1210 if (CurAST
75.1
'CurAST' is null
75.1
'CurAST' is null
75.1
'CurAST' is null
75.1
'CurAST' is null
75.1
'CurAST' is null
)
76
Taking false branch
1211 Invalidated = pointerInvalidatedByLoop(
1212 MemoryLocation(Op, LocationSize::unknown(), AAMDNodes()),
1213 CurAST, CurLoop, AA);
1214 else
1215 Invalidated = pointerInvalidatedByLoopWithMSSA(
1216 MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop, I,
77
Called C++ object pointer is null
1217 *Flags);
1218 if (Invalidated)
1219 return false;
1220 }
1221 return true;
1222 }
1223
1224 // If this call only reads from memory and there are no writes to memory
1225 // in the loop, we can hoist or sink the call as appropriate.
1226 if (isReadOnly(CurAST, MSSAU, CurLoop))
1227 return true;
1228 }
1229
1230 // FIXME: This should use mod/ref information to see if we can hoist or
1231 // sink the call.
1232
1233 return false;
1234 } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
1235 // Fences alias (most) everything to provide ordering. For the moment,
1236 // just give up if there are any other memory operations in the loop.
1237 if (CurAST) {
1238 auto Begin = CurAST->begin();
1239 assert(Begin != CurAST->end() && "must contain FI")((Begin != CurAST->end() && "must contain FI") ? static_cast
<void> (0) : __assert_fail ("Begin != CurAST->end() && \"must contain FI\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1239, __PRETTY_FUNCTION__))
;
1240 if (std::next(Begin) != CurAST->end())
1241 // constant memory for instance, TODO: handle better
1242 return false;
1243 auto *UniqueI = Begin->getUniqueInstruction();
1244 if (!UniqueI)
1245 // other memory op, give up
1246 return false;
1247 (void)FI; // suppress unused variable warning
1248 assert(UniqueI == FI && "AS must contain FI")((UniqueI == FI && "AS must contain FI") ? static_cast
<void> (0) : __assert_fail ("UniqueI == FI && \"AS must contain FI\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1248, __PRETTY_FUNCTION__))
;
1249 return true;
1250 } else // MSSAU
1251 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1252 } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
1253 if (!SI->isUnordered())
1254 return false; // Don't sink/hoist volatile or ordered atomic store!
1255
1256 // We can only hoist a store that we can prove writes a value which is not
1257 // read or overwritten within the loop. For those cases, we fallback to
1258 // load store promotion instead. TODO: We can extend this to cases where
1259 // there is exactly one write to the location and that write dominates an
1260 // arbitrary number of reads in the loop.
1261 if (CurAST) {
1262 auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
1263
1264 if (AS.isRef() || !AS.isMustAlias())
1265 // Quick exit test, handled by the full path below as well.
1266 return false;
1267 auto *UniqueI = AS.getUniqueInstruction();
1268 if (!UniqueI)
1269 // other memory op, give up
1270 return false;
1271 assert(UniqueI == SI && "AS must contain SI")((UniqueI == SI && "AS must contain SI") ? static_cast
<void> (0) : __assert_fail ("UniqueI == SI && \"AS must contain SI\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1271, __PRETTY_FUNCTION__))
;
1272 return true;
1273 } else { // MSSAU
1274 if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1275 return true;
1276 // If there are more accesses than the Promotion cap or no "quota" to
1277 // check clobber, then give up as we're not walking a list that long.
1278 if (Flags->tooManyMemoryAccesses() || Flags->tooManyClobberingCalls())
1279 return false;
1280 // If there are interfering Uses (i.e. their defining access is in the
1281 // loop), or ordered loads (stored as Defs!), don't move this store.
1282 // Could do better here, but this is conservatively correct.
1283 // TODO: Cache set of Uses on the first walk in runOnLoop, update when
1284 // moving accesses. Can also extend to dominating uses.
1285 auto *SIMD = MSSA->getMemoryAccess(SI);
1286 for (auto *BB : CurLoop->getBlocks())
1287 if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
1288 for (const auto &MA : *Accesses)
1289 if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1290 auto *MD = MU->getDefiningAccess();
1291 if (!MSSA->isLiveOnEntryDef(MD) &&
1292 CurLoop->contains(MD->getBlock()))
1293 return false;
1294 // Disable hoisting past potentially interfering loads. Optimized
1295 // Uses may point to an access outside the loop, as getClobbering
1296 // checks the previous iteration when walking the backedge.
1297 // FIXME: More precise: no Uses that alias SI.
1298 if (!Flags->getIsSink() && !MSSA->dominates(SIMD, MU))
1299 return false;
1300 } else if (const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1301 if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1302 (void)LI; // Silence warning.
1303 assert(!LI->isUnordered() && "Expected unordered load")((!LI->isUnordered() && "Expected unordered load")
? static_cast<void> (0) : __assert_fail ("!LI->isUnordered() && \"Expected unordered load\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1303, __PRETTY_FUNCTION__))
;
1304 return false;
1305 }
1306 // Any call, while it may not be clobbering SI, it may be a use.
1307 if (auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1308 // Check if the call may read from the memory locattion written
1309 // to by SI. Check CI's attributes and arguments; the number of
1310 // such checks performed is limited above by NoOfMemAccTooLarge.
1311 ModRefInfo MRI = AA->getModRefInfo(CI, MemoryLocation::get(SI));
1312 if (isModOrRefSet(MRI))
1313 return false;
1314 }
1315 }
1316 }
1317 auto *Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(SI);
1318 Flags->incrementClobberingCalls();
1319 // If there are no clobbering Defs in the loop, store is safe to hoist.
1320 return MSSA->isLiveOnEntryDef(Source) ||
1321 !CurLoop->contains(Source->getBlock());
1322 }
1323 }
1324
1325 assert(!I.mayReadOrWriteMemory() && "unhandled aliasing")((!I.mayReadOrWriteMemory() && "unhandled aliasing") ?
static_cast<void> (0) : __assert_fail ("!I.mayReadOrWriteMemory() && \"unhandled aliasing\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1325, __PRETTY_FUNCTION__))
;
1326
1327 // We've established mechanical ability and aliasing, it's up to the caller
1328 // to check fault safety
1329 return true;
1330}
1331
1332/// Returns true if a PHINode is a trivially replaceable with an
1333/// Instruction.
1334/// This is true when all incoming values are that instruction.
1335/// This pattern occurs most often with LCSSA PHI nodes.
1336///
1337static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
1338 for (const Value *IncValue : PN.incoming_values())
1339 if (IncValue != &I)
1340 return false;
1341
1342 return true;
1343}
1344
1345/// Return true if the instruction is free in the loop.
1346static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop,
1347 const TargetTransformInfo *TTI) {
1348
1349 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1350 if (TTI->getUserCost(GEP, TargetTransformInfo::TCK_SizeAndLatency) !=
1351 TargetTransformInfo::TCC_Free)
1352 return false;
1353 // For a GEP, we cannot simply use getUserCost because currently it
1354 // optimistically assume that a GEP will fold into addressing mode
1355 // regardless of its users.
1356 const BasicBlock *BB = GEP->getParent();
1357 for (const User *U : GEP->users()) {
1358 const Instruction *UI = cast<Instruction>(U);
1359 if (CurLoop->contains(UI) &&
1360 (BB != UI->getParent() ||
1361 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1362 return false;
1363 }
1364 return true;
1365 } else
1366 return TTI->getUserCost(&I, TargetTransformInfo::TCK_SizeAndLatency) ==
1367 TargetTransformInfo::TCC_Free;
1368}
1369
1370/// Return true if the only users of this instruction are outside of
1371/// the loop. If this is true, we can sink the instruction to the exit
1372/// blocks of the loop.
1373///
1374/// We also return true if the instruction could be folded away in lowering.
1375/// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
1376static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
1377 const LoopSafetyInfo *SafetyInfo,
1378 TargetTransformInfo *TTI, bool &FreeInLoop) {
1379 const auto &BlockColors = SafetyInfo->getBlockColors();
1380 bool IsFree = isFreeInLoop(I, CurLoop, TTI);
1381 for (const User *U : I.users()) {
1382 const Instruction *UI = cast<Instruction>(U);
1383 if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1384 const BasicBlock *BB = PN->getParent();
1385 // We cannot sink uses in catchswitches.
1386 if (isa<CatchSwitchInst>(BB->getTerminator()))
1387 return false;
1388
1389 // We need to sink a callsite to a unique funclet. Avoid sinking if the
1390 // phi use is too muddled.
1391 if (isa<CallInst>(I))
1392 if (!BlockColors.empty() &&
1393 BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
1394 return false;
1395 }
1396
1397 if (CurLoop->contains(UI)) {
1398 if (IsFree) {
1399 FreeInLoop = true;
1400 continue;
1401 }
1402 return false;
1403 }
1404 }
1405 return true;
1406}
1407
1408static Instruction *cloneInstructionInExitBlock(
1409 Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
1410 const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU) {
1411 Instruction *New;
1412 if (auto *CI = dyn_cast<CallInst>(&I)) {
1413 const auto &BlockColors = SafetyInfo->getBlockColors();
1414
1415 // Sinking call-sites need to be handled differently from other
1416 // instructions. The cloned call-site needs a funclet bundle operand
1417 // appropriate for its location in the CFG.
1418 SmallVector<OperandBundleDef, 1> OpBundles;
1419 for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1420 BundleIdx != BundleEnd; ++BundleIdx) {
1421 OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
1422 if (Bundle.getTagID() == LLVMContext::OB_funclet)
1423 continue;
1424
1425 OpBundles.emplace_back(Bundle);
1426 }
1427
1428 if (!BlockColors.empty()) {
1429 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1430 assert(CV.size() == 1 && "non-unique color for exit block!")((CV.size() == 1 && "non-unique color for exit block!"
) ? static_cast<void> (0) : __assert_fail ("CV.size() == 1 && \"non-unique color for exit block!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1430, __PRETTY_FUNCTION__))
;
1431 BasicBlock *BBColor = CV.front();
1432 Instruction *EHPad = BBColor->getFirstNonPHI();
1433 if (EHPad->isEHPad())
1434 OpBundles.emplace_back("funclet", EHPad);
1435 }
1436
1437 New = CallInst::Create(CI, OpBundles);
1438 } else {
1439 New = I.clone();
1440 }
1441
1442 ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
1443 if (!I.getName().empty())
1444 New->setName(I.getName() + ".le");
1445
1446 if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
1447 // Create a new MemoryAccess and let MemorySSA set its defining access.
1448 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1449 New, nullptr, New->getParent(), MemorySSA::Beginning);
1450 if (NewMemAcc) {
1451 if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1452 MSSAU->insertDef(MemDef, /*RenameUses=*/true);
1453 else {
1454 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1455 MSSAU->insertUse(MemUse, /*RenameUses=*/true);
1456 }
1457 }
1458 }
1459
1460 // Build LCSSA PHI nodes for any in-loop operands. Note that this is
1461 // particularly cheap because we can rip off the PHI node that we're
1462 // replacing for the number and blocks of the predecessors.
1463 // OPT: If this shows up in a profile, we can instead finish sinking all
1464 // invariant instructions, and then walk their operands to re-establish
1465 // LCSSA. That will eliminate creating PHI nodes just to nuke them when
1466 // sinking bottom-up.
1467 for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
1468 ++OI)
1469 if (Instruction *OInst = dyn_cast<Instruction>(*OI))
1470 if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
1471 if (!OLoop->contains(&PN)) {
1472 PHINode *OpPN =
1473 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
1474 OInst->getName() + ".lcssa", &ExitBlock.front());
1475 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1476 OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
1477 *OI = OpPN;
1478 }
1479 return New;
1480}
1481
1482static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
1483 AliasSetTracker *AST, MemorySSAUpdater *MSSAU) {
1484 if (AST)
1485 AST->deleteValue(&I);
1486 if (MSSAU)
1487 MSSAU->removeMemoryAccess(&I);
1488 SafetyInfo.removeInstruction(&I);
1489 I.eraseFromParent();
1490}
1491
1492static void moveInstructionBefore(Instruction &I, Instruction &Dest,
1493 ICFLoopSafetyInfo &SafetyInfo,
1494 MemorySSAUpdater *MSSAU,
1495 ScalarEvolution *SE) {
1496 SafetyInfo.removeInstruction(&I);
1497 SafetyInfo.insertInstructionTo(&I, Dest.getParent());
1498 I.moveBefore(&Dest);
1499 if (MSSAU)
1500 if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
1501 MSSAU->getMemorySSA()->getMemoryAccess(&I)))
1502 MSSAU->moveToPlace(OldMemAcc, Dest.getParent(),
1503 MemorySSA::BeforeTerminator);
1504 if (SE)
1505 SE->forgetValue(&I);
1506}
1507
1508static Instruction *sinkThroughTriviallyReplaceablePHI(
1509 PHINode *TPN, Instruction *I, LoopInfo *LI,
1510 SmallDenseMap<BasicBlock *, Instruction *, 32> &SunkCopies,
1511 const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
1512 MemorySSAUpdater *MSSAU) {
1513 assert(isTriviallyReplaceablePHI(*TPN, *I) &&((isTriviallyReplaceablePHI(*TPN, *I) && "Expect only trivially replaceable PHI"
) ? static_cast<void> (0) : __assert_fail ("isTriviallyReplaceablePHI(*TPN, *I) && \"Expect only trivially replaceable PHI\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1514, __PRETTY_FUNCTION__))
1514 "Expect only trivially replaceable PHI")((isTriviallyReplaceablePHI(*TPN, *I) && "Expect only trivially replaceable PHI"
) ? static_cast<void> (0) : __assert_fail ("isTriviallyReplaceablePHI(*TPN, *I) && \"Expect only trivially replaceable PHI\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1514, __PRETTY_FUNCTION__))
;
1515 BasicBlock *ExitBlock = TPN->getParent();
1516 Instruction *New;
1517 auto It = SunkCopies.find(ExitBlock);
1518 if (It != SunkCopies.end())
1519 New = It->second;
1520 else
1521 New = SunkCopies[ExitBlock] = cloneInstructionInExitBlock(
1522 *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1523 return New;
1524}
1525
1526static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
1527 BasicBlock *BB = PN->getParent();
1528 if (!BB->canSplitPredecessors())
1529 return false;
1530 // It's not impossible to split EHPad blocks, but if BlockColors already exist
1531 // it require updating BlockColors for all offspring blocks accordingly. By
1532 // skipping such corner case, we can make updating BlockColors after splitting
1533 // predecessor fairly simple.
1534 if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad())
1535 return false;
1536 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
1537 BasicBlock *BBPred = *PI;
1538 if (isa<IndirectBrInst>(BBPred->getTerminator()) ||
1539 isa<CallBrInst>(BBPred->getTerminator()))
1540 return false;
1541 }
1542 return true;
1543}
1544
1545static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
1546 LoopInfo *LI, const Loop *CurLoop,
1547 LoopSafetyInfo *SafetyInfo,
1548 MemorySSAUpdater *MSSAU) {
1549#ifndef NDEBUG
1550 SmallVector<BasicBlock *, 32> ExitBlocks;
1551 CurLoop->getUniqueExitBlocks(ExitBlocks);
1552 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1553 ExitBlocks.end());
1554#endif
1555 BasicBlock *ExitBB = PN->getParent();
1556 assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.")((ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block."
) ? static_cast<void> (0) : __assert_fail ("ExitBlockSet.count(ExitBB) && \"Expect the PHI is in an exit block.\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1556, __PRETTY_FUNCTION__))
;
1557
1558 // Split predecessors of the loop exit to make instructions in the loop are
1559 // exposed to exit blocks through trivially replaceable PHIs while keeping the
1560 // loop in the canonical form where each predecessor of each exit block should
1561 // be contained within the loop. For example, this will convert the loop below
1562 // from
1563 //
1564 // LB1:
1565 // %v1 =
1566 // br %LE, %LB2
1567 // LB2:
1568 // %v2 =
1569 // br %LE, %LB1
1570 // LE:
1571 // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
1572 //
1573 // to
1574 //
1575 // LB1:
1576 // %v1 =
1577 // br %LE.split, %LB2
1578 // LB2:
1579 // %v2 =
1580 // br %LE.split2, %LB1
1581 // LE.split:
1582 // %p1 = phi [%v1, %LB1] <-- trivially replaceable
1583 // br %LE
1584 // LE.split2:
1585 // %p2 = phi [%v2, %LB2] <-- trivially replaceable
1586 // br %LE
1587 // LE:
1588 // %p = phi [%p1, %LE.split], [%p2, %LE.split2]
1589 //
1590 const auto &BlockColors = SafetyInfo->getBlockColors();
1591 SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
1592 while (!PredBBs.empty()) {
1593 BasicBlock *PredBB = *PredBBs.begin();
1594 assert(CurLoop->contains(PredBB) &&((CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->contains(PredBB) && \"Expect all predecessors are in the loop\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1595, __PRETTY_FUNCTION__))
1595 "Expect all predecessors are in the loop")((CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->contains(PredBB) && \"Expect all predecessors are in the loop\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1595, __PRETTY_FUNCTION__))
;
1596 if (PN->getBasicBlockIndex(PredBB) >= 0) {
1597 BasicBlock *NewPred = SplitBlockPredecessors(
1598 ExitBB, PredBB, ".split.loop.exit", DT, LI, MSSAU, true);
1599 // Since we do not allow splitting EH-block with BlockColors in
1600 // canSplitPredecessors(), we can simply assign predecessor's color to
1601 // the new block.
1602 if (!BlockColors.empty())
1603 // Grab a reference to the ColorVector to be inserted before getting the
1604 // reference to the vector we are copying because inserting the new
1605 // element in BlockColors might cause the map to be reallocated.
1606 SafetyInfo->copyColors(NewPred, PredBB);
1607 }
1608 PredBBs.remove(PredBB);
1609 }
1610}
1611
1612/// When an instruction is found to only be used outside of the loop, this
1613/// function moves it to the exit blocks and patches up SSA form as needed.
1614/// This method is guaranteed to remove the original instruction from its
1615/// position, and may either delete it or move it to outside of the loop.
1616///
1617static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
1618 BlockFrequencyInfo *BFI, const Loop *CurLoop,
1619 ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
1620 OptimizationRemarkEmitter *ORE) {
1621 LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM sinking instruction: " <<
I << "\n"; } } while (false)
;
1622 ORE->emit([&]() {
1623 return OptimizationRemark(DEBUG_TYPE"licm", "InstSunk", &I)
1624 << "sinking " << ore::NV("Inst", &I);
1625 });
1626 bool Changed = false;
1627 if (isa<LoadInst>(I))
1628 ++NumMovedLoads;
1629 else if (isa<CallInst>(I))
1630 ++NumMovedCalls;
1631 ++NumSunk;
1632
1633 // Iterate over users to be ready for actual sinking. Replace users via
1634 // unreachable blocks with undef and make all user PHIs trivially replaceable.
1635 SmallPtrSet<Instruction *, 8> VisitedUsers;
1636 for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1637 auto *User = cast<Instruction>(*UI);
1638 Use &U = UI.getUse();
1639 ++UI;
1640
1641 if (VisitedUsers.count(User) || CurLoop->contains(User))
1642 continue;
1643
1644 if (!DT->isReachableFromEntry(User->getParent())) {
1645 U = UndefValue::get(I.getType());
1646 Changed = true;
1647 continue;
1648 }
1649
1650 // The user must be a PHI node.
1651 PHINode *PN = cast<PHINode>(User);
1652
1653 // Surprisingly, instructions can be used outside of loops without any
1654 // exits. This can only happen in PHI nodes if the incoming block is
1655 // unreachable.
1656 BasicBlock *BB = PN->getIncomingBlock(U);
1657 if (!DT->isReachableFromEntry(BB)) {
1658 U = UndefValue::get(I.getType());
1659 Changed = true;
1660 continue;
1661 }
1662
1663 VisitedUsers.insert(PN);
1664 if (isTriviallyReplaceablePHI(*PN, I))
1665 continue;
1666
1667 if (!canSplitPredecessors(PN, SafetyInfo))
1668 return Changed;
1669
1670 // Split predecessors of the PHI so that we can make users trivially
1671 // replaceable.
1672 splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, MSSAU);
1673
1674 // Should rebuild the iterators, as they may be invalidated by
1675 // splitPredecessorsOfLoopExit().
1676 UI = I.user_begin();
1677 UE = I.user_end();
1678 }
1679
1680 if (VisitedUsers.empty())
1681 return Changed;
1682
1683#ifndef NDEBUG
1684 SmallVector<BasicBlock *, 32> ExitBlocks;
1685 CurLoop->getUniqueExitBlocks(ExitBlocks);
1686 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1687 ExitBlocks.end());
1688#endif
1689
1690 // Clones of this instruction. Don't create more than one per exit block!
1691 SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
1692
1693 // If this instruction is only used outside of the loop, then all users are
1694 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1695 // the instruction.
1696 // First check if I is worth sinking for all uses. Sink only when it is worth
1697 // across all uses.
1698 SmallSetVector<User*, 8> Users(I.user_begin(), I.user_end());
1699 SmallVector<PHINode *, 8> ExitPNs;
1700 for (auto *UI : Users) {
1701 auto *User = cast<Instruction>(UI);
1702
1703 if (CurLoop->contains(User))
1704 continue;
1705
1706 PHINode *PN = cast<PHINode>(User);
1707 assert(ExitBlockSet.count(PN->getParent()) &&((ExitBlockSet.count(PN->getParent()) && "The LCSSA PHI is not in an exit block!"
) ? static_cast<void> (0) : __assert_fail ("ExitBlockSet.count(PN->getParent()) && \"The LCSSA PHI is not in an exit block!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1708, __PRETTY_FUNCTION__))
1708 "The LCSSA PHI is not in an exit block!")((ExitBlockSet.count(PN->getParent()) && "The LCSSA PHI is not in an exit block!"
) ? static_cast<void> (0) : __assert_fail ("ExitBlockSet.count(PN->getParent()) && \"The LCSSA PHI is not in an exit block!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1708, __PRETTY_FUNCTION__))
;
1709 if (!worthSinkOrHoistInst(I, PN->getParent(), ORE, BFI)) {
1710 return Changed;
1711 }
1712
1713 ExitPNs.push_back(PN);
1714 }
1715
1716 for (auto *PN : ExitPNs) {
1717
1718 // The PHI must be trivially replaceable.
1719 Instruction *New = sinkThroughTriviallyReplaceablePHI(
1720 PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1721 PN->replaceAllUsesWith(New);
1722 eraseInstruction(*PN, *SafetyInfo, nullptr, nullptr);
1723 Changed = true;
1724 }
1725 return Changed;
1726}
1727
1728/// When an instruction is found to only use loop invariant operands that
1729/// is safe to hoist, this instruction is called to do the dirty work.
1730///
1731static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
1732 BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
1733 MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
1734 OptimizationRemarkEmitter *ORE) {
1735 LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getName() << ": " << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM hoisting to " << Dest
->getName() << ": " << I << "\n"; } } while
(false)
1736 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM hoisting to " << Dest
->getName() << ": " << I << "\n"; } } while
(false)
;
1737 ORE->emit([&]() {
1738 return OptimizationRemark(DEBUG_TYPE"licm", "Hoisted", &I) << "hoisting "
1739 << ore::NV("Inst", &I);
1740 });
1741
1742 // Metadata can be dependent on conditions we are hoisting above.
1743 // Conservatively strip all metadata on the instruction unless we were
1744 // guaranteed to execute I if we entered the loop, in which case the metadata
1745 // is valid in the loop preheader.
1746 if (I.hasMetadataOtherThanDebugLoc() &&
1747 // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1748 // time in isGuaranteedToExecute if we don't actually have anything to
1749 // drop. It is a compile time optimization, not required for correctness.
1750 !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
1751 I.dropUnknownNonDebugMetadata();
1752
1753 if (isa<PHINode>(I))
1754 // Move the new node to the end of the phi list in the destination block.
1755 moveInstructionBefore(I, *Dest->getFirstNonPHI(), *SafetyInfo, MSSAU, SE);
1756 else
1757 // Move the new node to the destination block, before its terminator.
1758 moveInstructionBefore(I, *Dest->getTerminator(), *SafetyInfo, MSSAU, SE);
1759
1760 I.updateLocationAfterHoist();
1761
1762 if (isa<LoadInst>(I))
1763 ++NumMovedLoads;
1764 else if (isa<CallInst>(I))
1765 ++NumMovedCalls;
1766 ++NumHoisted;
1767}
1768
1769/// Only sink or hoist an instruction if it is not a trapping instruction,
1770/// or if the instruction is known not to trap when moved to the preheader.
1771/// or if it is a trapping instruction and is guaranteed to execute.
1772static bool isSafeToExecuteUnconditionally(Instruction &Inst,
1773 const DominatorTree *DT,
1774 const Loop *CurLoop,
1775 const LoopSafetyInfo *SafetyInfo,
1776 OptimizationRemarkEmitter *ORE,
1777 const Instruction *CtxI) {
1778 if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
1779 return true;
1780
1781 bool GuaranteedToExecute =
1782 SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
1783
1784 if (!GuaranteedToExecute) {
1785 auto *LI = dyn_cast<LoadInst>(&Inst);
1786 if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1787 ORE->emit([&]() {
1788 return OptimizationRemarkMissed(
1789 DEBUG_TYPE"licm", "LoadWithLoopInvariantAddressCondExecuted", LI)
1790 << "failed to hoist load with loop-invariant address "
1791 "because load is conditionally executed";
1792 });
1793 }
1794
1795 return GuaranteedToExecute;
1796}
1797
1798namespace {
1799class LoopPromoter : public LoadAndStorePromoter {
1800 Value *SomePtr; // Designated pointer to store to.
1801 const SmallSetVector<Value *, 8> &PointerMustAliases;
1802 SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1803 SmallVectorImpl<Instruction *> &LoopInsertPts;
1804 SmallVectorImpl<MemoryAccess *> &MSSAInsertPts;
1805 PredIteratorCache &PredCache;
1806 AliasSetTracker *AST;
1807 MemorySSAUpdater *MSSAU;
1808 LoopInfo &LI;
1809 DebugLoc DL;
1810 int Alignment;
1811 bool UnorderedAtomic;
1812 AAMDNodes AATags;
1813 ICFLoopSafetyInfo &SafetyInfo;
1814
1815 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
1816 if (Instruction *I = dyn_cast<Instruction>(V))
1817 if (Loop *L = LI.getLoopFor(I->getParent()))
1818 if (!L->contains(BB)) {
1819 // We need to create an LCSSA PHI node for the incoming value and
1820 // store that.
1821 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
1822 I->getName() + ".lcssa", &BB->front());
1823 for (BasicBlock *Pred : PredCache.get(BB))
1824 PN->addIncoming(I, Pred);
1825 return PN;
1826 }
1827 return V;
1828 }
1829
1830public:
1831 LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
1832 const SmallSetVector<Value *, 8> &PMA,
1833 SmallVectorImpl<BasicBlock *> &LEB,
1834 SmallVectorImpl<Instruction *> &LIP,
1835 SmallVectorImpl<MemoryAccess *> &MSSAIP, PredIteratorCache &PIC,
1836 AliasSetTracker *ast, MemorySSAUpdater *MSSAU, LoopInfo &li,
1837 DebugLoc dl, int alignment, bool UnorderedAtomic,
1838 const AAMDNodes &AATags, ICFLoopSafetyInfo &SafetyInfo)
1839 : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
1840 LoopExitBlocks(LEB), LoopInsertPts(LIP), MSSAInsertPts(MSSAIP),
1841 PredCache(PIC), AST(ast), MSSAU(MSSAU), LI(li), DL(std::move(dl)),
1842 Alignment(alignment), UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1843 SafetyInfo(SafetyInfo) {}
1844
1845 bool isInstInList(Instruction *I,
1846 const SmallVectorImpl<Instruction *> &) const override {
1847 Value *Ptr;
1848 if (LoadInst *LI = dyn_cast<LoadInst>(I))
1849 Ptr = LI->getOperand(0);
1850 else
1851 Ptr = cast<StoreInst>(I)->getPointerOperand();
1852 return PointerMustAliases.count(Ptr);
1853 }
1854
1855 void doExtraRewritesBeforeFinalDeletion() override {
1856 // Insert stores after in the loop exit blocks. Each exit block gets a
1857 // store of the live-out values that feed them. Since we've already told
1858 // the SSA updater about the defs in the loop and the preheader
1859 // definition, it is all set and we can start using it.
1860 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1861 BasicBlock *ExitBlock = LoopExitBlocks[i];
1862 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1863 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1864 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1865 Instruction *InsertPos = LoopInsertPts[i];
1866 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1867 if (UnorderedAtomic)
1868 NewSI->setOrdering(AtomicOrdering::Unordered);
1869 NewSI->setAlignment(Align(Alignment));
1870 NewSI->setDebugLoc(DL);
1871 if (AATags)
1872 NewSI->setAAMetadata(AATags);
1873
1874 if (MSSAU) {
1875 MemoryAccess *MSSAInsertPoint = MSSAInsertPts[i];
1876 MemoryAccess *NewMemAcc;
1877 if (!MSSAInsertPoint) {
1878 NewMemAcc = MSSAU->createMemoryAccessInBB(
1879 NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
1880 } else {
1881 NewMemAcc =
1882 MSSAU->createMemoryAccessAfter(NewSI, nullptr, MSSAInsertPoint);
1883 }
1884 MSSAInsertPts[i] = NewMemAcc;
1885 MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true);
1886 // FIXME: true for safety, false may still be correct.
1887 }
1888 }
1889 }
1890
1891 void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
1892 // Update alias analysis.
1893 if (AST)
1894 AST->copyValue(LI, V);
1895 }
1896 void instructionDeleted(Instruction *I) const override {
1897 SafetyInfo.removeInstruction(I);
1898 if (AST)
1899 AST->deleteValue(I);
1900 if (MSSAU)
1901 MSSAU->removeMemoryAccess(I);
1902 }
1903};
1904
1905
1906/// Return true iff we can prove that a caller of this function can not inspect
1907/// the contents of the provided object in a well defined program.
1908bool isKnownNonEscaping(Value *Object, const TargetLibraryInfo *TLI) {
1909 if (isa<AllocaInst>(Object))
1910 // Since the alloca goes out of scope, we know the caller can't retain a
1911 // reference to it and be well defined. Thus, we don't need to check for
1912 // capture.
1913 return true;
1914
1915 // For all other objects we need to know that the caller can't possibly
1916 // have gotten a reference to the object. There are two components of
1917 // that:
1918 // 1) Object can't be escaped by this function. This is what
1919 // PointerMayBeCaptured checks.
1920 // 2) Object can't have been captured at definition site. For this, we
1921 // need to know the return value is noalias. At the moment, we use a
1922 // weaker condition and handle only AllocLikeFunctions (which are
1923 // known to be noalias). TODO
1924 return isAllocLikeFn(Object, TLI) &&
1925 !PointerMayBeCaptured(Object, true, true);
1926}
1927
1928} // namespace
1929
1930/// Try to promote memory values to scalars by sinking stores out of the
1931/// loop and moving loads to before the loop. We do this by looping over
1932/// the stores in the loop, looking for stores to Must pointers which are
1933/// loop invariant.
1934///
1935bool llvm::promoteLoopAccessesToScalars(
1936 const SmallSetVector<Value *, 8> &PointerMustAliases,
1937 SmallVectorImpl<BasicBlock *> &ExitBlocks,
1938 SmallVectorImpl<Instruction *> &InsertPts,
1939 SmallVectorImpl<MemoryAccess *> &MSSAInsertPts, PredIteratorCache &PIC,
1940 LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
1941 Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
1942 ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
1943 // Verify inputs.
1944 assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&((LI != nullptr && DT != nullptr && CurLoop !=
nullptr && SafetyInfo != nullptr && "Unexpected Input to promoteLoopAccessesToScalars"
) ? static_cast<void> (0) : __assert_fail ("LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected Input to promoteLoopAccessesToScalars\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1946, __PRETTY_FUNCTION__))
1945 SafetyInfo != nullptr &&((LI != nullptr && DT != nullptr && CurLoop !=
nullptr && SafetyInfo != nullptr && "Unexpected Input to promoteLoopAccessesToScalars"
) ? static_cast<void> (0) : __assert_fail ("LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected Input to promoteLoopAccessesToScalars\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1946, __PRETTY_FUNCTION__))
1946 "Unexpected Input to promoteLoopAccessesToScalars")((LI != nullptr && DT != nullptr && CurLoop !=
nullptr && SafetyInfo != nullptr && "Unexpected Input to promoteLoopAccessesToScalars"
) ? static_cast<void> (0) : __assert_fail ("LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected Input to promoteLoopAccessesToScalars\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1946, __PRETTY_FUNCTION__))
;
1947
1948 Value *SomePtr = *PointerMustAliases.begin();
1949 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1950
1951 // It is not safe to promote a load/store from the loop if the load/store is
1952 // conditional. For example, turning:
1953 //
1954 // for () { if (c) *P += 1; }
1955 //
1956 // into:
1957 //
1958 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1959 //
1960 // is not safe, because *P may only be valid to access if 'c' is true.
1961 //
1962 // The safety property divides into two parts:
1963 // p1) The memory may not be dereferenceable on entry to the loop. In this
1964 // case, we can't insert the required load in the preheader.
1965 // p2) The memory model does not allow us to insert a store along any dynamic
1966 // path which did not originally have one.
1967 //
1968 // If at least one store is guaranteed to execute, both properties are
1969 // satisfied, and promotion is legal.
1970 //
1971 // This, however, is not a necessary condition. Even if no store/load is
1972 // guaranteed to execute, we can still establish these properties.
1973 // We can establish (p1) by proving that hoisting the load into the preheader
1974 // is safe (i.e. proving dereferenceability on all paths through the loop). We
1975 // can use any access within the alias set to prove dereferenceability,
1976 // since they're all must alias.
1977 //
1978 // There are two ways establish (p2):
1979 // a) Prove the location is thread-local. In this case the memory model
1980 // requirement does not apply, and stores are safe to insert.
1981 // b) Prove a store dominates every exit block. In this case, if an exit
1982 // blocks is reached, the original dynamic path would have taken us through
1983 // the store, so inserting a store into the exit block is safe. Note that this
1984 // is different from the store being guaranteed to execute. For instance,
1985 // if an exception is thrown on the first iteration of the loop, the original
1986 // store is never executed, but the exit blocks are not executed either.
1987
1988 bool DereferenceableInPH = false;
1989 bool SafeToInsertStore = false;
1990
1991 SmallVector<Instruction *, 64> LoopUses;
1992
1993 // We start with an alignment of one and try to find instructions that allow
1994 // us to prove better alignment.
1995 Align Alignment;
1996 // Keep track of which types of access we see
1997 bool SawUnorderedAtomic = false;
1998 bool SawNotAtomic = false;
1999 AAMDNodes AATags;
2000
2001 const DataLayout &MDL = Preheader->getModule()->getDataLayout();
2002
2003 bool IsKnownThreadLocalObject = false;
2004 if (SafetyInfo->anyBlockMayThrow()) {
2005 // If a loop can throw, we have to insert a store along each unwind edge.
2006 // That said, we can't actually make the unwind edge explicit. Therefore,
2007 // we have to prove that the store is dead along the unwind edge. We do
2008 // this by proving that the caller can't have a reference to the object
2009 // after return and thus can't possibly load from the object.
2010 Value *Object = getUnderlyingObject(SomePtr);
2011 if (!isKnownNonEscaping(Object, TLI))
2012 return false;
2013 // Subtlety: Alloca's aren't visible to callers, but *are* potentially
2014 // visible to other threads if captured and used during their lifetimes.
2015 IsKnownThreadLocalObject = !isa<AllocaInst>(Object);
2016 }
2017
2018 // Check that all of the pointers in the alias set have the same type. We
2019 // cannot (yet) promote a memory location that is loaded and stored in
2020 // different sizes. While we are at it, collect alignment and AA info.
2021 for (Value *ASIV : PointerMustAliases) {
2022 // Check that all of the pointers in the alias set have the same type. We
2023 // cannot (yet) promote a memory location that is loaded and stored in
2024 // different sizes.
2025 if (SomePtr->getType() != ASIV->getType())
2026 return false;
2027
2028 for (User *U : ASIV->users()) {
2029 // Ignore instructions that are outside the loop.
2030 Instruction *UI = dyn_cast<Instruction>(U);
2031 if (!UI || !CurLoop->contains(UI))
2032 continue;
2033
2034 // If there is an non-load/store instruction in the loop, we can't promote
2035 // it.
2036 if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2037 if (!Load->isUnordered())
2038 return false;
2039
2040 SawUnorderedAtomic |= Load->isAtomic();
2041 SawNotAtomic |= !Load->isAtomic();
2042
2043 Align InstAlignment = Load->getAlign();
2044
2045 // Note that proving a load safe to speculate requires proving
2046 // sufficient alignment at the target location. Proving it guaranteed
2047 // to execute does as well. Thus we can increase our guaranteed
2048 // alignment as well.
2049 if (!DereferenceableInPH || (InstAlignment > Alignment))
2050 if (isSafeToExecuteUnconditionally(*Load, DT, CurLoop, SafetyInfo,
2051 ORE, Preheader->getTerminator())) {
2052 DereferenceableInPH = true;
2053 Alignment = std::max(Alignment, InstAlignment);
2054 }
2055 } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2056 // Stores *of* the pointer are not interesting, only stores *to* the
2057 // pointer.
2058 if (UI->getOperand(1) != ASIV)
2059 continue;
2060 if (!Store->isUnordered())
2061 return false;
2062
2063 SawUnorderedAtomic |= Store->isAtomic();
2064 SawNotAtomic |= !Store->isAtomic();
2065
2066 // If the store is guaranteed to execute, both properties are satisfied.
2067 // We may want to check if a store is guaranteed to execute even if we
2068 // already know that promotion is safe, since it may have higher
2069 // alignment than any other guaranteed stores, in which case we can
2070 // raise the alignment on the promoted store.
2071 Align InstAlignment = Store->getAlign();
2072
2073 if (!DereferenceableInPH || !SafeToInsertStore ||
2074 (InstAlignment > Alignment)) {
2075 if (SafetyInfo->isGuaranteedToExecute(*UI, DT, CurLoop)) {
2076 DereferenceableInPH = true;
2077 SafeToInsertStore = true;
2078 Alignment = std::max(Alignment, InstAlignment);
2079 }
2080 }
2081
2082 // If a store dominates all exit blocks, it is safe to sink.
2083 // As explained above, if an exit block was executed, a dominating
2084 // store must have been executed at least once, so we are not
2085 // introducing stores on paths that did not have them.
2086 // Note that this only looks at explicit exit blocks. If we ever
2087 // start sinking stores into unwind edges (see above), this will break.
2088 if (!SafeToInsertStore)
2089 SafeToInsertStore = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
2090 return DT->dominates(Store->getParent(), Exit);
2091 });
2092
2093 // If the store is not guaranteed to execute, we may still get
2094 // deref info through it.
2095 if (!DereferenceableInPH) {
2096 DereferenceableInPH = isDereferenceableAndAlignedPointer(
2097 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2098 Store->getAlign(), MDL, Preheader->getTerminator(), DT);
2099 }
2100 } else
2101 return false; // Not a load or store.
2102
2103 // Merge the AA tags.
2104 if (LoopUses.empty()) {
2105 // On the first load/store, just take its AA tags.
2106 UI->getAAMetadata(AATags);
2107 } else if (AATags) {
2108 UI->getAAMetadata(AATags, /* Merge = */ true);
2109 }
2110
2111 LoopUses.push_back(UI);
2112 }
2113 }
2114
2115 // If we found both an unordered atomic instruction and a non-atomic memory
2116 // access, bail. We can't blindly promote non-atomic to atomic since we
2117 // might not be able to lower the result. We can't downgrade since that
2118 // would violate memory model. Also, align 0 is an error for atomics.
2119 if (SawUnorderedAtomic && SawNotAtomic)
2120 return false;
2121
2122 // If we're inserting an atomic load in the preheader, we must be able to
2123 // lower it. We're only guaranteed to be able to lower naturally aligned
2124 // atomics.
2125 auto *SomePtrElemType = SomePtr->getType()->getPointerElementType();
2126 if (SawUnorderedAtomic &&
2127 Alignment < MDL.getTypeStoreSize(SomePtrElemType))
2128 return false;
2129
2130 // If we couldn't prove we can hoist the load, bail.
2131 if (!DereferenceableInPH)
2132 return false;
2133
2134 // We know we can hoist the load, but don't have a guaranteed store.
2135 // Check whether the location is thread-local. If it is, then we can insert
2136 // stores along paths which originally didn't have them without violating the
2137 // memory model.
2138 if (!SafeToInsertStore) {
2139 if (IsKnownThreadLocalObject)
2140 SafeToInsertStore = true;
2141 else {
2142 Value *Object = getUnderlyingObject(SomePtr);
2143 SafeToInsertStore =
2144 (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
2145 !PointerMayBeCaptured(Object, true, true);
2146 }
2147 }
2148
2149 // If we've still failed to prove we can sink the store, give up.
2150 if (!SafeToInsertStore)
2151 return false;
2152
2153 // Otherwise, this is safe to promote, lets do it!
2154 LLVM_DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Promoting value stored to in loop: "
<< *SomePtr << '\n'; } } while (false)
2155 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Promoting value stored to in loop: "
<< *SomePtr << '\n'; } } while (false)
;
2156 ORE->emit([&]() {
2157 return OptimizationRemark(DEBUG_TYPE"licm", "PromoteLoopAccessesToScalar",
2158 LoopUses[0])
2159 << "Moving accesses to memory location out of the loop";
2160 });
2161 ++NumPromoted;
2162
2163 // Look at all the loop uses, and try to merge their locations.
2164 std::vector<const DILocation *> LoopUsesLocs;
2165 for (auto U : LoopUses)
2166 LoopUsesLocs.push_back(U->getDebugLoc().get());
2167 auto DL = DebugLoc(DILocation::getMergedLocations(LoopUsesLocs));
2168
2169 // We use the SSAUpdater interface to insert phi nodes as required.
2170 SmallVector<PHINode *, 16> NewPHIs;
2171 SSAUpdater SSA(&NewPHIs);
2172 LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
2173 InsertPts, MSSAInsertPts, PIC, CurAST, MSSAU, *LI, DL,
2174 Alignment.value(), SawUnorderedAtomic, AATags,
2175 *SafetyInfo);
2176
2177 // Set up the preheader to have a definition of the value. It is the live-out
2178 // value from the preheader that uses in the loop will use.
2179 LoadInst *PreheaderLoad = new LoadInst(
2180 SomePtr->getType()->getPointerElementType(), SomePtr,
2181 SomePtr->getName() + ".promoted", Preheader->getTerminator());
2182 if (SawUnorderedAtomic)
2183 PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
2184 PreheaderLoad->setAlignment(Alignment);
2185 PreheaderLoad->setDebugLoc(DebugLoc());
2186 if (AATags)
2187 PreheaderLoad->setAAMetadata(AATags);
2188 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2189
2190 if (MSSAU) {
2191 MemoryAccess *PreheaderLoadMemoryAccess = MSSAU->createMemoryAccessInBB(
2192 PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
2193 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2194 MSSAU->insertUse(NewMemUse, /*RenameUses=*/true);
2195 }
2196
2197 if (MSSAU && VerifyMemorySSA)
2198 MSSAU->getMemorySSA()->verifyMemorySSA();
2199 // Rewrite all the loads in the loop and remember all the definitions from
2200 // stores in the loop.
2201 Promoter.run(LoopUses);
2202
2203 if (MSSAU && VerifyMemorySSA)
2204 MSSAU->getMemorySSA()->verifyMemorySSA();
2205 // If the SSAUpdater didn't use the load in the preheader, just zap it now.
2206 if (PreheaderLoad->use_empty())
2207 eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, MSSAU);
2208
2209 return true;
2210}
2211
2212/// Returns an owning pointer to an alias set which incorporates aliasing info
2213/// from L and all subloops of L.
2214std::unique_ptr<AliasSetTracker>
2215LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
2216 AAResults *AA) {
2217 auto CurAST = std::make_unique<AliasSetTracker>(*AA);
2218
2219 // Add everything from all the sub loops.
2220 for (Loop *InnerL : L->getSubLoops())
2221 for (BasicBlock *BB : InnerL->blocks())
2222 CurAST->add(*BB);
2223
2224 // And merge in this loop (without anything from inner loops).
2225 for (BasicBlock *BB : L->blocks())
2226 if (LI->getLoopFor(BB) == L)
2227 CurAST->add(*BB);
2228
2229 return CurAST;
2230}
2231
2232std::unique_ptr<AliasSetTracker>
2233LoopInvariantCodeMotion::collectAliasInfoForLoopWithMSSA(
2234 Loop *L, AAResults *AA, MemorySSAUpdater *MSSAU) {
2235 auto *MSSA = MSSAU->getMemorySSA();
2236 auto CurAST = std::make_unique<AliasSetTracker>(*AA, MSSA, L);
2237 CurAST->addAllInstructionsInLoopUsingMSSA();
2238 return CurAST;
2239}
2240
2241static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
2242 AliasSetTracker *CurAST, Loop *CurLoop,
2243 AAResults *AA) {
2244 // First check to see if any of the basic blocks in CurLoop invalidate *V.
2245 bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
2246
2247 if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
2248 return isInvalidatedAccordingToAST;
2249
2250 // Check with a diagnostic analysis if we can refine the information above.
2251 // This is to identify the limitations of using the AST.
2252 // The alias set mechanism used by LICM has a major weakness in that it
2253 // combines all things which may alias into a single set *before* asking
2254 // modref questions. As a result, a single readonly call within a loop will
2255 // collapse all loads and stores into a single alias set and report
2256 // invalidation if the loop contains any store. For example, readonly calls
2257 // with deopt states have this form and create a general alias set with all
2258 // loads and stores. In order to get any LICM in loops containing possible
2259 // deopt states we need a more precise invalidation of checking the mod ref
2260 // info of each instruction within the loop and LI. This has a complexity of
2261 // O(N^2), so currently, it is used only as a diagnostic tool since the
2262 // default value of LICMN2Threshold is zero.
2263
2264 // Don't look at nested loops.
2265 if (CurLoop->begin() != CurLoop->end())
2266 return true;
2267
2268 int N = 0;
2269 for (BasicBlock *BB : CurLoop->getBlocks())
2270 for (Instruction &I : *BB) {
2271 if (N >= LICMN2Theshold) {
2272 LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Alasing N2 threshold exhausted for "
<< *(MemLoc.Ptr) << "\n"; } } while (false)
2273 << *(MemLoc.Ptr) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Alasing N2 threshold exhausted for "
<< *(MemLoc.Ptr) << "\n"; } } while (false)
;
2274 return true;
2275 }
2276 N++;
2277 auto Res = AA->getModRefInfo(&I, MemLoc);
2278 if (isModSet(Res)) {
2279 LLVM_DEBUG(dbgs() << "Aliasing failed on " << I << " for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Aliasing failed on " << I <<
" for " << *(MemLoc.Ptr) << "\n"; } } while (false
)
2280 << *(MemLoc.Ptr) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Aliasing failed on " << I <<
" for " << *(MemLoc.Ptr) << "\n"; } } while (false
)
;
2281 return true;
2282 }
2283 }
2284 LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Aliasing okay for " << *(MemLoc
.Ptr) << "\n"; } } while (false)
;
2285 return false;
2286}
2287
2288bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
2289 Loop *CurLoop, Instruction &I,
2290 SinkAndHoistLICMFlags &Flags) {
2291 // For hoisting, use the walker to determine safety
2292 if (!Flags.getIsSink()) {
2293 MemoryAccess *Source;
2294 // See declaration of SetLicmMssaOptCap for usage details.
2295 if (Flags.tooManyClobberingCalls())
2296 Source = MU->getDefiningAccess();
2297 else {
2298 Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(MU);
2299 Flags.incrementClobberingCalls();
2300 }
2301 return !MSSA->isLiveOnEntryDef(Source) &&
2302 CurLoop->contains(Source->getBlock());
2303 }
2304
2305 // For sinking, we'd need to check all Defs below this use. The getClobbering
2306 // call will look on the backedge of the loop, but will check aliasing with
2307 // the instructions on the previous iteration.
2308 // For example:
2309 // for (i ... )
2310 // load a[i] ( Use (LoE)
2311 // store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
2312 // i++;
2313 // The load sees no clobbering inside the loop, as the backedge alias check
2314 // does phi translation, and will check aliasing against store a[i-1].
2315 // However sinking the load outside the loop, below the store is incorrect.
2316
2317 // For now, only sink if there are no Defs in the loop, and the existing ones
2318 // precede the use and are in the same block.
2319 // FIXME: Increase precision: Safe to sink if Use post dominates the Def;
2320 // needs PostDominatorTreeAnalysis.
2321 // FIXME: More precise: no Defs that alias this Use.
2322 if (Flags.tooManyMemoryAccesses())
2323 return true;
2324 for (auto *BB : CurLoop->getBlocks())
2325 if (pointerInvalidatedByBlockWithMSSA(*BB, *MSSA, *MU))
2326 return true;
2327 // When sinking, the source block may not be part of the loop so check it.
2328 if (!CurLoop->contains(&I))
2329 return pointerInvalidatedByBlockWithMSSA(*I.getParent(), *MSSA, *MU);
2330
2331 return false;
2332}
2333
2334bool pointerInvalidatedByBlockWithMSSA(BasicBlock &BB, MemorySSA &MSSA,
2335 MemoryUse &MU) {
2336 if (const auto *Accesses = MSSA.getBlockDefs(&BB))
2337 for (const auto &MA : *Accesses)
2338 if (const auto *MD = dyn_cast<MemoryDef>(&MA))
2339 if (MU.getBlock() != MD->getBlock() || !MSSA.locallyDominates(MD, &MU))
2340 return true;
2341 return false;
2342}
2343
2344/// Little predicate that returns true if the specified basic block is in
2345/// a subloop of the current one, not the current one itself.
2346///
2347static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
2348 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop")((CurLoop->contains(BB) && "Only valid if BB is IN the loop"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->contains(BB) && \"Only valid if BB is IN the loop\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/LICM.cpp"
, 2348, __PRETTY_FUNCTION__))
;
2349 return LI->getLoopFor(BB) != CurLoop;
2350}

/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h

1//===- llvm/InstrTypes.h - Important Instruction subclasses -----*- C++ -*-===//
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 defines various meta classes of instructions that exist in the VM
10// representation. Specific concrete subclasses of these may be found in the
11// i*.h files...
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_IR_INSTRTYPES_H
16#define LLVM_IR_INSTRTYPES_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/None.h"
20#include "llvm/ADT/Optional.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/StringMap.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/ADT/Twine.h"
25#include "llvm/ADT/iterator_range.h"
26#include "llvm/IR/Attributes.h"
27#include "llvm/IR/CallingConv.h"
28#include "llvm/IR/Constants.h"
29#include "llvm/IR/DerivedTypes.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/Instruction.h"
32#include "llvm/IR/LLVMContext.h"
33#include "llvm/IR/OperandTraits.h"
34#include "llvm/IR/Type.h"
35#include "llvm/IR/User.h"
36#include "llvm/IR/Value.h"
37#include "llvm/Support/Casting.h"
38#include "llvm/Support/ErrorHandling.h"
39#include <algorithm>
40#include <cassert>
41#include <cstddef>
42#include <cstdint>
43#include <iterator>
44#include <string>
45#include <vector>
46
47namespace llvm {
48
49namespace Intrinsic {
50typedef unsigned ID;
51}
52
53//===----------------------------------------------------------------------===//
54// UnaryInstruction Class
55//===----------------------------------------------------------------------===//
56
57class UnaryInstruction : public Instruction {
58protected:
59 UnaryInstruction(Type *Ty, unsigned iType, Value *V,
60 Instruction *IB = nullptr)
61 : Instruction(Ty, iType, &Op<0>(), 1, IB) {
62 Op<0>() = V;
63 }
64 UnaryInstruction(Type *Ty, unsigned iType, Value *V, BasicBlock *IAE)
65 : Instruction(Ty, iType, &Op<0>(), 1, IAE) {
66 Op<0>() = V;
67 }
68
69public:
70 // allocate space for exactly one operand
71 void *operator new(size_t s) {
72 return User::operator new(s, 1);
73 }
74
75 /// Transparently provide more efficient getOperand methods.
76 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value)public: inline Value *getOperand(unsigned) const; inline void
setOperand(unsigned, Value*); inline op_iterator op_begin();
inline const_op_iterator op_begin() const; inline op_iterator
op_end(); inline const_op_iterator op_end() const; protected
: template <int> inline Use &Op(); template <int
> inline const Use &Op() const; public: inline unsigned
getNumOperands() const
;
77
78 // Methods for support type inquiry through isa, cast, and dyn_cast:
79 static bool classof(const Instruction *I) {
80 return I->isUnaryOp() ||
81 I->getOpcode() == Instruction::Alloca ||
82 I->getOpcode() == Instruction::Load ||
83 I->getOpcode() == Instruction::VAArg ||
84 I->getOpcode() == Instruction::ExtractValue ||
85 (I->getOpcode() >= CastOpsBegin && I->getOpcode() < CastOpsEnd);
86 }
87 static bool classof(const Value *V) {
88 return isa<Instruction>(V) && classof(cast<Instruction>(V));
89 }
90};
91
92template <>
93struct OperandTraits<UnaryInstruction> :
94 public FixedNumOperandTraits<UnaryInstruction, 1> {
95};
96
97DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryInstruction, Value)UnaryInstruction::op_iterator UnaryInstruction::op_begin() { return
OperandTraits<UnaryInstruction>::op_begin(this); } UnaryInstruction
::const_op_iterator UnaryInstruction::op_begin() const { return
OperandTraits<UnaryInstruction>::op_begin(const_cast<
UnaryInstruction*>(this)); } UnaryInstruction::op_iterator
UnaryInstruction::op_end() { return OperandTraits<UnaryInstruction
>::op_end(this); } UnaryInstruction::const_op_iterator UnaryInstruction
::op_end() const { return OperandTraits<UnaryInstruction>
::op_end(const_cast<UnaryInstruction*>(this)); } Value *
UnaryInstruction::getOperand(unsigned i_nocapture) const { ((
i_nocapture < OperandTraits<UnaryInstruction>::operands
(this) && "getOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<UnaryInstruction>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 97, __PRETTY_FUNCTION__)); return cast_or_null<Value>
( OperandTraits<UnaryInstruction>::op_begin(const_cast<
UnaryInstruction*>(this))[i_nocapture].get()); } void UnaryInstruction
::setOperand(unsigned i_nocapture, Value *Val_nocapture) { ((
i_nocapture < OperandTraits<UnaryInstruction>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<UnaryInstruction>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 97, __PRETTY_FUNCTION__)); OperandTraits<UnaryInstruction
>::op_begin(this)[i_nocapture] = Val_nocapture; } unsigned
UnaryInstruction::getNumOperands() const { return OperandTraits
<UnaryInstruction>::operands(this); } template <int Idx_nocapture
> Use &UnaryInstruction::Op() { return this->OpFrom
<Idx_nocapture>(this); } template <int Idx_nocapture
> const Use &UnaryInstruction::Op() const { return this
->OpFrom<Idx_nocapture>(this); }
98
99//===----------------------------------------------------------------------===//
100// UnaryOperator Class
101//===----------------------------------------------------------------------===//
102
103class UnaryOperator : public UnaryInstruction {
104 void AssertOK();
105
106protected:
107 UnaryOperator(UnaryOps iType, Value *S, Type *Ty,
108 const Twine &Name, Instruction *InsertBefore);
109 UnaryOperator(UnaryOps iType, Value *S, Type *Ty,
110 const Twine &Name, BasicBlock *InsertAtEnd);
111
112 // Note: Instruction needs to be a friend here to call cloneImpl.
113 friend class Instruction;
114
115 UnaryOperator *cloneImpl() const;
116
117public:
118
119 /// Construct a unary instruction, given the opcode and an operand.
120 /// Optionally (if InstBefore is specified) insert the instruction
121 /// into a BasicBlock right before the specified instruction. The specified
122 /// Instruction is allowed to be a dereferenced end iterator.
123 ///
124 static UnaryOperator *Create(UnaryOps Op, Value *S,
125 const Twine &Name = Twine(),
126 Instruction *InsertBefore = nullptr);
127
128 /// Construct a unary instruction, given the opcode and an operand.
129 /// Also automatically insert this instruction to the end of the
130 /// BasicBlock specified.
131 ///
132 static UnaryOperator *Create(UnaryOps Op, Value *S,
133 const Twine &Name,
134 BasicBlock *InsertAtEnd);
135
136 /// These methods just forward to Create, and are useful when you
137 /// statically know what type of instruction you're going to create. These
138 /// helpers just save some typing.
139#define HANDLE_UNARY_INST(N, OPC, CLASS) \
140 static UnaryOperator *Create##OPC(Value *V, const Twine &Name = "") {\
141 return Create(Instruction::OPC, V, Name);\
142 }
143#include "llvm/IR/Instruction.def"
144#define HANDLE_UNARY_INST(N, OPC, CLASS) \
145 static UnaryOperator *Create##OPC(Value *V, const Twine &Name, \
146 BasicBlock *BB) {\
147 return Create(Instruction::OPC, V, Name, BB);\
148 }
149#include "llvm/IR/Instruction.def"
150#define HANDLE_UNARY_INST(N, OPC, CLASS) \
151 static UnaryOperator *Create##OPC(Value *V, const Twine &Name, \
152 Instruction *I) {\
153 return Create(Instruction::OPC, V, Name, I);\
154 }
155#include "llvm/IR/Instruction.def"
156
157 static UnaryOperator *
158 CreateWithCopiedFlags(UnaryOps Opc, Value *V, Instruction *CopyO,
159 const Twine &Name = "",
160 Instruction *InsertBefore = nullptr) {
161 UnaryOperator *UO = Create(Opc, V, Name, InsertBefore);
162 UO->copyIRFlags(CopyO);
163 return UO;
164 }
165
166 static UnaryOperator *CreateFNegFMF(Value *Op, Instruction *FMFSource,
167 const Twine &Name = "",
168 Instruction *InsertBefore = nullptr) {
169 return CreateWithCopiedFlags(Instruction::FNeg, Op, FMFSource, Name,
170 InsertBefore);
171 }
172
173 UnaryOps getOpcode() const {
174 return static_cast<UnaryOps>(Instruction::getOpcode());
175 }
176
177 // Methods for support type inquiry through isa, cast, and dyn_cast:
178 static bool classof(const Instruction *I) {
179 return I->isUnaryOp();
180 }
181 static bool classof(const Value *V) {
182 return isa<Instruction>(V) && classof(cast<Instruction>(V));
183 }
184};
185
186//===----------------------------------------------------------------------===//
187// BinaryOperator Class
188//===----------------------------------------------------------------------===//
189
190class BinaryOperator : public Instruction {
191 void AssertOK();
192
193protected:
194 BinaryOperator(BinaryOps iType, Value *S1, Value *S2, Type *Ty,
195 const Twine &Name, Instruction *InsertBefore);
196 BinaryOperator(BinaryOps iType, Value *S1, Value *S2, Type *Ty,
197 const Twine &Name, BasicBlock *InsertAtEnd);
198
199 // Note: Instruction needs to be a friend here to call cloneImpl.
200 friend class Instruction;
201
202 BinaryOperator *cloneImpl() const;
203
204public:
205 // allocate space for exactly two operands
206 void *operator new(size_t s) {
207 return User::operator new(s, 2);
208 }
209
210 /// Transparently provide more efficient getOperand methods.
211 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value)public: inline Value *getOperand(unsigned) const; inline void
setOperand(unsigned, Value*); inline op_iterator op_begin();
inline const_op_iterator op_begin() const; inline op_iterator
op_end(); inline const_op_iterator op_end() const; protected
: template <int> inline Use &Op(); template <int
> inline const Use &Op() const; public: inline unsigned
getNumOperands() const
;
212
213 /// Construct a binary instruction, given the opcode and the two
214 /// operands. Optionally (if InstBefore is specified) insert the instruction
215 /// into a BasicBlock right before the specified instruction. The specified
216 /// Instruction is allowed to be a dereferenced end iterator.
217 ///
218 static BinaryOperator *Create(BinaryOps Op, Value *S1, Value *S2,
219 const Twine &Name = Twine(),
220 Instruction *InsertBefore = nullptr);
221
222 /// Construct a binary instruction, given the opcode and the two
223 /// operands. Also automatically insert this instruction to the end of the
224 /// BasicBlock specified.
225 ///
226 static BinaryOperator *Create(BinaryOps Op, Value *S1, Value *S2,
227 const Twine &Name, BasicBlock *InsertAtEnd);
228
229 /// These methods just forward to Create, and are useful when you
230 /// statically know what type of instruction you're going to create. These
231 /// helpers just save some typing.
232#define HANDLE_BINARY_INST(N, OPC, CLASS) \
233 static BinaryOperator *Create##OPC(Value *V1, Value *V2, \
234 const Twine &Name = "") {\
235 return Create(Instruction::OPC, V1, V2, Name);\
236 }
237#include "llvm/IR/Instruction.def"
238#define HANDLE_BINARY_INST(N, OPC, CLASS) \
239 static BinaryOperator *Create##OPC(Value *V1, Value *V2, \
240 const Twine &Name, BasicBlock *BB) {\
241 return Create(Instruction::OPC, V1, V2, Name, BB);\
242 }
243#include "llvm/IR/Instruction.def"
244#define HANDLE_BINARY_INST(N, OPC, CLASS) \
245 static BinaryOperator *Create##OPC(Value *V1, Value *V2, \
246 const Twine &Name, Instruction *I) {\
247 return Create(Instruction::OPC, V1, V2, Name, I);\
248 }
249#include "llvm/IR/Instruction.def"
250
251 static BinaryOperator *CreateWithCopiedFlags(BinaryOps Opc,
252 Value *V1, Value *V2,
253 Instruction *CopyO,
254 const Twine &Name = "") {
255 BinaryOperator *BO = Create(Opc, V1, V2, Name);
256 BO->copyIRFlags(CopyO);
257 return BO;
258 }
259
260 static BinaryOperator *CreateFAddFMF(Value *V1, Value *V2,
261 Instruction *FMFSource,
262 const Twine &Name = "") {
263 return CreateWithCopiedFlags(Instruction::FAdd, V1, V2, FMFSource, Name);
264 }
265 static BinaryOperator *CreateFSubFMF(Value *V1, Value *V2,
266 Instruction *FMFSource,
267 const Twine &Name = "") {
268 return CreateWithCopiedFlags(Instruction::FSub, V1, V2, FMFSource, Name);
269 }
270 static BinaryOperator *CreateFMulFMF(Value *V1, Value *V2,
271 Instruction *FMFSource,
272 const Twine &Name = "") {
273 return CreateWithCopiedFlags(Instruction::FMul, V1, V2, FMFSource, Name);
274 }
275 static BinaryOperator *CreateFDivFMF(Value *V1, Value *V2,
276 Instruction *FMFSource,
277 const Twine &Name = "") {
278 return CreateWithCopiedFlags(Instruction::FDiv, V1, V2, FMFSource, Name);
279 }
280 static BinaryOperator *CreateFRemFMF(Value *V1, Value *V2,
281 Instruction *FMFSource,
282 const Twine &Name = "") {
283 return CreateWithCopiedFlags(Instruction::FRem, V1, V2, FMFSource, Name);
284 }
285
286 static BinaryOperator *CreateNSW(BinaryOps Opc, Value *V1, Value *V2,
287 const Twine &Name = "") {
288 BinaryOperator *BO = Create(Opc, V1, V2, Name);
289 BO->setHasNoSignedWrap(true);
290 return BO;
291 }
292 static BinaryOperator *CreateNSW(BinaryOps Opc, Value *V1, Value *V2,
293 const Twine &Name, BasicBlock *BB) {
294 BinaryOperator *BO = Create(Opc, V1, V2, Name, BB);
295 BO->setHasNoSignedWrap(true);
296 return BO;
297 }
298 static BinaryOperator *CreateNSW(BinaryOps Opc, Value *V1, Value *V2,
299 const Twine &Name, Instruction *I) {
300 BinaryOperator *BO = Create(Opc, V1, V2, Name, I);
301 BO->setHasNoSignedWrap(true);
302 return BO;
303 }
304
305 static BinaryOperator *CreateNUW(BinaryOps Opc, Value *V1, Value *V2,
306 const Twine &Name = "") {
307 BinaryOperator *BO = Create(Opc, V1, V2, Name);
308 BO->setHasNoUnsignedWrap(true);
309 return BO;
310 }
311 static BinaryOperator *CreateNUW(BinaryOps Opc, Value *V1, Value *V2,
312 const Twine &Name, BasicBlock *BB) {
313 BinaryOperator *BO = Create(Opc, V1, V2, Name, BB);
314 BO->setHasNoUnsignedWrap(true);
315 return BO;
316 }
317 static BinaryOperator *CreateNUW(BinaryOps Opc, Value *V1, Value *V2,
318 const Twine &Name, Instruction *I) {
319 BinaryOperator *BO = Create(Opc, V1, V2, Name, I);
320 BO->setHasNoUnsignedWrap(true);
321 return BO;
322 }
323
324 static BinaryOperator *CreateExact(BinaryOps Opc, Value *V1, Value *V2,
325 const Twine &Name = "") {
326 BinaryOperator *BO = Create(Opc, V1, V2, Name);
327 BO->setIsExact(true);
328 return BO;
329 }
330 static BinaryOperator *CreateExact(BinaryOps Opc, Value *V1, Value *V2,
331 const Twine &Name, BasicBlock *BB) {
332 BinaryOperator *BO = Create(Opc, V1, V2, Name, BB);
333 BO->setIsExact(true);
334 return BO;
335 }
336 static BinaryOperator *CreateExact(BinaryOps Opc, Value *V1, Value *V2,
337 const Twine &Name, Instruction *I) {
338 BinaryOperator *BO = Create(Opc, V1, V2, Name, I);
339 BO->setIsExact(true);
340 return BO;
341 }
342
343#define DEFINE_HELPERS(OPC, NUWNSWEXACT) \
344 static BinaryOperator *Create##NUWNSWEXACT##OPC(Value *V1, Value *V2, \
345 const Twine &Name = "") { \
346 return Create##NUWNSWEXACT(Instruction::OPC, V1, V2, Name); \
347 } \
348 static BinaryOperator *Create##NUWNSWEXACT##OPC( \
349 Value *V1, Value *V2, const Twine &Name, BasicBlock *BB) { \
350 return Create##NUWNSWEXACT(Instruction::OPC, V1, V2, Name, BB); \
351 } \
352 static BinaryOperator *Create##NUWNSWEXACT##OPC( \
353 Value *V1, Value *V2, const Twine &Name, Instruction *I) { \
354 return Create##NUWNSWEXACT(Instruction::OPC, V1, V2, Name, I); \
355 }
356
357 DEFINE_HELPERS(Add, NSW) // CreateNSWAdd
358 DEFINE_HELPERS(Add, NUW) // CreateNUWAdd
359 DEFINE_HELPERS(Sub, NSW) // CreateNSWSub
360 DEFINE_HELPERS(Sub, NUW) // CreateNUWSub
361 DEFINE_HELPERS(Mul, NSW) // CreateNSWMul
362 DEFINE_HELPERS(Mul, NUW) // CreateNUWMul
363 DEFINE_HELPERS(Shl, NSW) // CreateNSWShl
364 DEFINE_HELPERS(Shl, NUW) // CreateNUWShl
365
366 DEFINE_HELPERS(SDiv, Exact) // CreateExactSDiv
367 DEFINE_HELPERS(UDiv, Exact) // CreateExactUDiv
368 DEFINE_HELPERS(AShr, Exact) // CreateExactAShr
369 DEFINE_HELPERS(LShr, Exact) // CreateExactLShr
370
371#undef DEFINE_HELPERS
372
373 /// Helper functions to construct and inspect unary operations (NEG and NOT)
374 /// via binary operators SUB and XOR:
375 ///
376 /// Create the NEG and NOT instructions out of SUB and XOR instructions.
377 ///
378 static BinaryOperator *CreateNeg(Value *Op, const Twine &Name = "",
379 Instruction *InsertBefore = nullptr);
380 static BinaryOperator *CreateNeg(Value *Op, const Twine &Name,
381 BasicBlock *InsertAtEnd);
382 static BinaryOperator *CreateNSWNeg(Value *Op, const Twine &Name = "",
383 Instruction *InsertBefore = nullptr);
384 static BinaryOperator *CreateNSWNeg(Value *Op, const Twine &Name,
385 BasicBlock *InsertAtEnd);
386 static BinaryOperator *CreateNUWNeg(Value *Op, const Twine &Name = "",
387 Instruction *InsertBefore = nullptr);
388 static BinaryOperator *CreateNUWNeg(Value *Op, const Twine &Name,
389 BasicBlock *InsertAtEnd);
390 static BinaryOperator *CreateNot(Value *Op, const Twine &Name = "",
391 Instruction *InsertBefore = nullptr);
392 static BinaryOperator *CreateNot(Value *Op, const Twine &Name,
393 BasicBlock *InsertAtEnd);
394
395 BinaryOps getOpcode() const {
396 return static_cast<BinaryOps>(Instruction::getOpcode());
397 }
398
399 /// Exchange the two operands to this instruction.
400 /// This instruction is safe to use on any binary instruction and
401 /// does not modify the semantics of the instruction. If the instruction
402 /// cannot be reversed (ie, it's a Div), then return true.
403 ///
404 bool swapOperands();
405
406 // Methods for support type inquiry through isa, cast, and dyn_cast:
407 static bool classof(const Instruction *I) {
408 return I->isBinaryOp();
409 }
410 static bool classof(const Value *V) {
411 return isa<Instruction>(V) && classof(cast<Instruction>(V));
412 }
413};
414
415template <>
416struct OperandTraits<BinaryOperator> :
417 public FixedNumOperandTraits<BinaryOperator, 2> {
418};
419
420DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryOperator, Value)BinaryOperator::op_iterator BinaryOperator::op_begin() { return
OperandTraits<BinaryOperator>::op_begin(this); } BinaryOperator
::const_op_iterator BinaryOperator::op_begin() const { return
OperandTraits<BinaryOperator>::op_begin(const_cast<
BinaryOperator*>(this)); } BinaryOperator::op_iterator BinaryOperator
::op_end() { return OperandTraits<BinaryOperator>::op_end
(this); } BinaryOperator::const_op_iterator BinaryOperator::op_end
() const { return OperandTraits<BinaryOperator>::op_end
(const_cast<BinaryOperator*>(this)); } Value *BinaryOperator
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
OperandTraits<BinaryOperator>::operands(this) &&
"getOperand() out of range!") ? static_cast<void> (0) :
__assert_fail ("i_nocapture < OperandTraits<BinaryOperator>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 420, __PRETTY_FUNCTION__)); return cast_or_null<Value>
( OperandTraits<BinaryOperator>::op_begin(const_cast<
BinaryOperator*>(this))[i_nocapture].get()); } void BinaryOperator
::setOperand(unsigned i_nocapture, Value *Val_nocapture) { ((
i_nocapture < OperandTraits<BinaryOperator>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<BinaryOperator>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 420, __PRETTY_FUNCTION__)); OperandTraits<BinaryOperator
>::op_begin(this)[i_nocapture] = Val_nocapture; } unsigned
BinaryOperator::getNumOperands() const { return OperandTraits
<BinaryOperator>::operands(this); } template <int Idx_nocapture
> Use &BinaryOperator::Op() { return this->OpFrom<
Idx_nocapture>(this); } template <int Idx_nocapture>
const Use &BinaryOperator::Op() const { return this->
OpFrom<Idx_nocapture>(this); }
421
422//===----------------------------------------------------------------------===//
423// CastInst Class
424//===----------------------------------------------------------------------===//
425
426/// This is the base class for all instructions that perform data
427/// casts. It is simply provided so that instruction category testing
428/// can be performed with code like:
429///
430/// if (isa<CastInst>(Instr)) { ... }
431/// Base class of casting instructions.
432class CastInst : public UnaryInstruction {
433protected:
434 /// Constructor with insert-before-instruction semantics for subclasses
435 CastInst(Type *Ty, unsigned iType, Value *S,
436 const Twine &NameStr = "", Instruction *InsertBefore = nullptr)
437 : UnaryInstruction(Ty, iType, S, InsertBefore) {
438 setName(NameStr);
439 }
440 /// Constructor with insert-at-end-of-block semantics for subclasses
441 CastInst(Type *Ty, unsigned iType, Value *S,
442 const Twine &NameStr, BasicBlock *InsertAtEnd)
443 : UnaryInstruction(Ty, iType, S, InsertAtEnd) {
444 setName(NameStr);
445 }
446
447public:
448 /// Provides a way to construct any of the CastInst subclasses using an
449 /// opcode instead of the subclass's constructor. The opcode must be in the
450 /// CastOps category (Instruction::isCast(opcode) returns true). This
451 /// constructor has insert-before-instruction semantics to automatically
452 /// insert the new CastInst before InsertBefore (if it is non-null).
453 /// Construct any of the CastInst subclasses
454 static CastInst *Create(
455 Instruction::CastOps, ///< The opcode of the cast instruction
456 Value *S, ///< The value to be casted (operand 0)
457 Type *Ty, ///< The type to which cast should be made
458 const Twine &Name = "", ///< Name for the instruction
459 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
460 );
461 /// Provides a way to construct any of the CastInst subclasses using an
462 /// opcode instead of the subclass's constructor. The opcode must be in the
463 /// CastOps category. This constructor has insert-at-end-of-block semantics
464 /// to automatically insert the new CastInst at the end of InsertAtEnd (if
465 /// its non-null).
466 /// Construct any of the CastInst subclasses
467 static CastInst *Create(
468 Instruction::CastOps, ///< The opcode for the cast instruction
469 Value *S, ///< The value to be casted (operand 0)
470 Type *Ty, ///< The type to which operand is casted
471 const Twine &Name, ///< The name for the instruction
472 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
473 );
474
475 /// Create a ZExt or BitCast cast instruction
476 static CastInst *CreateZExtOrBitCast(
477 Value *S, ///< The value to be casted (operand 0)
478 Type *Ty, ///< The type to which cast should be made
479 const Twine &Name = "", ///< Name for the instruction
480 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
481 );
482
483 /// Create a ZExt or BitCast cast instruction
484 static CastInst *CreateZExtOrBitCast(
485 Value *S, ///< The value to be casted (operand 0)
486 Type *Ty, ///< The type to which operand is casted
487 const Twine &Name, ///< The name for the instruction
488 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
489 );
490
491 /// Create a SExt or BitCast cast instruction
492 static CastInst *CreateSExtOrBitCast(
493 Value *S, ///< The value to be casted (operand 0)
494 Type *Ty, ///< The type to which cast should be made
495 const Twine &Name = "", ///< Name for the instruction
496 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
497 );
498
499 /// Create a SExt or BitCast cast instruction
500 static CastInst *CreateSExtOrBitCast(
501 Value *S, ///< The value to be casted (operand 0)
502 Type *Ty, ///< The type to which operand is casted
503 const Twine &Name, ///< The name for the instruction
504 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
505 );
506
507 /// Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
508 static CastInst *CreatePointerCast(
509 Value *S, ///< The pointer value to be casted (operand 0)
510 Type *Ty, ///< The type to which operand is casted
511 const Twine &Name, ///< The name for the instruction
512 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
513 );
514
515 /// Create a BitCast, AddrSpaceCast or a PtrToInt cast instruction.
516 static CastInst *CreatePointerCast(
517 Value *S, ///< The pointer value to be casted (operand 0)
518 Type *Ty, ///< The type to which cast should be made
519 const Twine &Name = "", ///< Name for the instruction
520 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
521 );
522
523 /// Create a BitCast or an AddrSpaceCast cast instruction.
524 static CastInst *CreatePointerBitCastOrAddrSpaceCast(
525 Value *S, ///< The pointer value to be casted (operand 0)
526 Type *Ty, ///< The type to which operand is casted
527 const Twine &Name, ///< The name for the instruction
528 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
529 );
530
531 /// Create a BitCast or an AddrSpaceCast cast instruction.
532 static CastInst *CreatePointerBitCastOrAddrSpaceCast(
533 Value *S, ///< The pointer value to be casted (operand 0)
534 Type *Ty, ///< The type to which cast should be made
535 const Twine &Name = "", ///< Name for the instruction
536 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
537 );
538
539 /// Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
540 ///
541 /// If the value is a pointer type and the destination an integer type,
542 /// creates a PtrToInt cast. If the value is an integer type and the
543 /// destination a pointer type, creates an IntToPtr cast. Otherwise, creates
544 /// a bitcast.
545 static CastInst *CreateBitOrPointerCast(
546 Value *S, ///< The pointer value to be casted (operand 0)
547 Type *Ty, ///< The type to which cast should be made
548 const Twine &Name = "", ///< Name for the instruction
549 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
550 );
551
552 /// Create a ZExt, BitCast, or Trunc for int -> int casts.
553 static CastInst *CreateIntegerCast(
554 Value *S, ///< The pointer value to be casted (operand 0)
555 Type *Ty, ///< The type to which cast should be made
556 bool isSigned, ///< Whether to regard S as signed or not
557 const Twine &Name = "", ///< Name for the instruction
558 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
559 );
560
561 /// Create a ZExt, BitCast, or Trunc for int -> int casts.
562 static CastInst *CreateIntegerCast(
563 Value *S, ///< The integer value to be casted (operand 0)
564 Type *Ty, ///< The integer type to which operand is casted
565 bool isSigned, ///< Whether to regard S as signed or not
566 const Twine &Name, ///< The name for the instruction
567 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
568 );
569
570 /// Create an FPExt, BitCast, or FPTrunc for fp -> fp casts
571 static CastInst *CreateFPCast(
572 Value *S, ///< The floating point value to be casted
573 Type *Ty, ///< The floating point type to cast to
574 const Twine &Name = "", ///< Name for the instruction
575 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
576 );
577
578 /// Create an FPExt, BitCast, or FPTrunc for fp -> fp casts
579 static CastInst *CreateFPCast(
580 Value *S, ///< The floating point value to be casted
581 Type *Ty, ///< The floating point type to cast to
582 const Twine &Name, ///< The name for the instruction
583 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
584 );
585
586 /// Create a Trunc or BitCast cast instruction
587 static CastInst *CreateTruncOrBitCast(
588 Value *S, ///< The value to be casted (operand 0)
589 Type *Ty, ///< The type to which cast should be made
590 const Twine &Name = "", ///< Name for the instruction
591 Instruction *InsertBefore = nullptr ///< Place to insert the instruction
592 );
593
594 /// Create a Trunc or BitCast cast instruction
595 static CastInst *CreateTruncOrBitCast(
596 Value *S, ///< The value to be casted (operand 0)
597 Type *Ty, ///< The type to which operand is casted
598 const Twine &Name, ///< The name for the instruction
599 BasicBlock *InsertAtEnd ///< The block to insert the instruction into
600 );
601
602 /// Check whether it is valid to call getCastOpcode for these types.
603 static bool isCastable(
604 Type *SrcTy, ///< The Type from which the value should be cast.
605 Type *DestTy ///< The Type to which the value should be cast.
606 );
607
608 /// Check whether a bitcast between these types is valid
609 static bool isBitCastable(
610 Type *SrcTy, ///< The Type from which the value should be cast.
611 Type *DestTy ///< The Type to which the value should be cast.
612 );
613
614 /// Check whether a bitcast, inttoptr, or ptrtoint cast between these
615 /// types is valid and a no-op.
616 ///
617 /// This ensures that any pointer<->integer cast has enough bits in the
618 /// integer and any other cast is a bitcast.
619 static bool isBitOrNoopPointerCastable(
620 Type *SrcTy, ///< The Type from which the value should be cast.
621 Type *DestTy, ///< The Type to which the value should be cast.
622 const DataLayout &DL);
623
624 /// Returns the opcode necessary to cast Val into Ty using usual casting
625 /// rules.
626 /// Infer the opcode for cast operand and type
627 static Instruction::CastOps getCastOpcode(
628 const Value *Val, ///< The value to cast
629 bool SrcIsSigned, ///< Whether to treat the source as signed
630 Type *Ty, ///< The Type to which the value should be casted
631 bool DstIsSigned ///< Whether to treate the dest. as signed
632 );
633
634 /// There are several places where we need to know if a cast instruction
635 /// only deals with integer source and destination types. To simplify that
636 /// logic, this method is provided.
637 /// @returns true iff the cast has only integral typed operand and dest type.
638 /// Determine if this is an integer-only cast.
639 bool isIntegerCast() const;
640
641 /// A lossless cast is one that does not alter the basic value. It implies
642 /// a no-op cast but is more stringent, preventing things like int->float,
643 /// long->double, or int->ptr.
644 /// @returns true iff the cast is lossless.
645 /// Determine if this is a lossless cast.
646 bool isLosslessCast() const;
647
648 /// A no-op cast is one that can be effected without changing any bits.
649 /// It implies that the source and destination types are the same size. The
650 /// DataLayout argument is to determine the pointer size when examining casts
651 /// involving Integer and Pointer types. They are no-op casts if the integer
652 /// is the same size as the pointer. However, pointer size varies with
653 /// platform. Note that a precondition of this method is that the cast is
654 /// legal - i.e. the instruction formed with these operands would verify.
655 static bool isNoopCast(
656 Instruction::CastOps Opcode, ///< Opcode of cast
657 Type *SrcTy, ///< SrcTy of cast
658 Type *DstTy, ///< DstTy of cast
659 const DataLayout &DL ///< DataLayout to get the Int Ptr type from.
660 );
661
662 /// Determine if this cast is a no-op cast.
663 ///
664 /// \param DL is the DataLayout to determine pointer size.
665 bool isNoopCast(const DataLayout &DL) const;
666
667 /// Determine how a pair of casts can be eliminated, if they can be at all.
668 /// This is a helper function for both CastInst and ConstantExpr.
669 /// @returns 0 if the CastInst pair can't be eliminated, otherwise
670 /// returns Instruction::CastOps value for a cast that can replace
671 /// the pair, casting SrcTy to DstTy.
672 /// Determine if a cast pair is eliminable
673 static unsigned isEliminableCastPair(
674 Instruction::CastOps firstOpcode, ///< Opcode of first cast
675 Instruction::CastOps secondOpcode, ///< Opcode of second cast
676 Type *SrcTy, ///< SrcTy of 1st cast
677 Type *MidTy, ///< DstTy of 1st cast & SrcTy of 2nd cast
678 Type *DstTy, ///< DstTy of 2nd cast
679 Type *SrcIntPtrTy, ///< Integer type corresponding to Ptr SrcTy, or null
680 Type *MidIntPtrTy, ///< Integer type corresponding to Ptr MidTy, or null
681 Type *DstIntPtrTy ///< Integer type corresponding to Ptr DstTy, or null
682 );
683
684 /// Return the opcode of this CastInst
685 Instruction::CastOps getOpcode() const {
686 return Instruction::CastOps(Instruction::getOpcode());
687 }
688
689 /// Return the source type, as a convenience
690 Type* getSrcTy() const { return getOperand(0)->getType(); }
691 /// Return the destination type, as a convenience
692 Type* getDestTy() const { return getType(); }
693
694 /// This method can be used to determine if a cast from SrcTy to DstTy using
695 /// Opcode op is valid or not.
696 /// @returns true iff the proposed cast is valid.
697 /// Determine if a cast is valid without creating one.
698 static bool castIsValid(Instruction::CastOps op, Type *SrcTy, Type *DstTy);
699 static bool castIsValid(Instruction::CastOps op, Value *S, Type *DstTy) {
700 return castIsValid(op, S->getType(), DstTy);
701 }
702
703 /// Methods for support type inquiry through isa, cast, and dyn_cast:
704 static bool classof(const Instruction *I) {
705 return I->isCast();
706 }
707 static bool classof(const Value *V) {
708 return isa<Instruction>(V) && classof(cast<Instruction>(V));
709 }
710};
711
712//===----------------------------------------------------------------------===//
713// CmpInst Class
714//===----------------------------------------------------------------------===//
715
716/// This class is the base class for the comparison instructions.
717/// Abstract base class of comparison instructions.
718class CmpInst : public Instruction {
719public:
720 /// This enumeration lists the possible predicates for CmpInst subclasses.
721 /// Values in the range 0-31 are reserved for FCmpInst, while values in the
722 /// range 32-64 are reserved for ICmpInst. This is necessary to ensure the
723 /// predicate values are not overlapping between the classes.
724 ///
725 /// Some passes (e.g. InstCombine) depend on the bit-wise characteristics of
726 /// FCMP_* values. Changing the bit patterns requires a potential change to
727 /// those passes.
728 enum Predicate : unsigned {
729 // Opcode U L G E Intuitive operation
730 FCMP_FALSE = 0, ///< 0 0 0 0 Always false (always folded)
731 FCMP_OEQ = 1, ///< 0 0 0 1 True if ordered and equal
732 FCMP_OGT = 2, ///< 0 0 1 0 True if ordered and greater than
733 FCMP_OGE = 3, ///< 0 0 1 1 True if ordered and greater than or equal
734 FCMP_OLT = 4, ///< 0 1 0 0 True if ordered and less than
735 FCMP_OLE = 5, ///< 0 1 0 1 True if ordered and less than or equal
736 FCMP_ONE = 6, ///< 0 1 1 0 True if ordered and operands are unequal
737 FCMP_ORD = 7, ///< 0 1 1 1 True if ordered (no nans)
738 FCMP_UNO = 8, ///< 1 0 0 0 True if unordered: isnan(X) | isnan(Y)
739 FCMP_UEQ = 9, ///< 1 0 0 1 True if unordered or equal
740 FCMP_UGT = 10, ///< 1 0 1 0 True if unordered or greater than
741 FCMP_UGE = 11, ///< 1 0 1 1 True if unordered, greater than, or equal
742 FCMP_ULT = 12, ///< 1 1 0 0 True if unordered or less than
743 FCMP_ULE = 13, ///< 1 1 0 1 True if unordered, less than, or equal
744 FCMP_UNE = 14, ///< 1 1 1 0 True if unordered or not equal
745 FCMP_TRUE = 15, ///< 1 1 1 1 Always true (always folded)
746 FIRST_FCMP_PREDICATE = FCMP_FALSE,
747 LAST_FCMP_PREDICATE = FCMP_TRUE,
748 BAD_FCMP_PREDICATE = FCMP_TRUE + 1,
749 ICMP_EQ = 32, ///< equal
750 ICMP_NE = 33, ///< not equal
751 ICMP_UGT = 34, ///< unsigned greater than
752 ICMP_UGE = 35, ///< unsigned greater or equal
753 ICMP_ULT = 36, ///< unsigned less than
754 ICMP_ULE = 37, ///< unsigned less or equal
755 ICMP_SGT = 38, ///< signed greater than
756 ICMP_SGE = 39, ///< signed greater or equal
757 ICMP_SLT = 40, ///< signed less than
758 ICMP_SLE = 41, ///< signed less or equal
759 FIRST_ICMP_PREDICATE = ICMP_EQ,
760 LAST_ICMP_PREDICATE = ICMP_SLE,
761 BAD_ICMP_PREDICATE = ICMP_SLE + 1
762 };
763 using PredicateField =
764 Bitfield::Element<Predicate, 0, 6, LAST_ICMP_PREDICATE>;
765
766protected:
767 CmpInst(Type *ty, Instruction::OtherOps op, Predicate pred,
768 Value *LHS, Value *RHS, const Twine &Name = "",
769 Instruction *InsertBefore = nullptr,
770 Instruction *FlagsSource = nullptr);
771
772 CmpInst(Type *ty, Instruction::OtherOps op, Predicate pred,
773 Value *LHS, Value *RHS, const Twine &Name,
774 BasicBlock *InsertAtEnd);
775
776public:
777 // allocate space for exactly two operands
778 void *operator new(size_t s) {
779 return User::operator new(s, 2);
780 }
781
782 /// Construct a compare instruction, given the opcode, the predicate and
783 /// the two operands. Optionally (if InstBefore is specified) insert the
784 /// instruction into a BasicBlock right before the specified instruction.
785 /// The specified Instruction is allowed to be a dereferenced end iterator.
786 /// Create a CmpInst
787 static CmpInst *Create(OtherOps Op,
788 Predicate predicate, Value *S1,
789 Value *S2, const Twine &Name = "",
790 Instruction *InsertBefore = nullptr);
791
792 /// Construct a compare instruction, given the opcode, the predicate and the
793 /// two operands. Also automatically insert this instruction to the end of
794 /// the BasicBlock specified.
795 /// Create a CmpInst
796 static CmpInst *Create(OtherOps Op, Predicate predicate, Value *S1,
797 Value *S2, const Twine &Name, BasicBlock *InsertAtEnd);
798
799 /// Get the opcode casted to the right type
800 OtherOps getOpcode() const {
801 return static_cast<OtherOps>(Instruction::getOpcode());
802 }
803
804 /// Return the predicate for this instruction.
805 Predicate getPredicate() const { return getSubclassData<PredicateField>(); }
806
807 /// Set the predicate for this instruction to the specified value.
808 void setPredicate(Predicate P) { setSubclassData<PredicateField>(P); }
809
810 static bool isFPPredicate(Predicate P) {
811 assert(FIRST_FCMP_PREDICATE == 0 &&((FIRST_FCMP_PREDICATE == 0 && "FIRST_FCMP_PREDICATE is required to be 0"
) ? static_cast<void> (0) : __assert_fail ("FIRST_FCMP_PREDICATE == 0 && \"FIRST_FCMP_PREDICATE is required to be 0\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 812, __PRETTY_FUNCTION__))
812 "FIRST_FCMP_PREDICATE is required to be 0")((FIRST_FCMP_PREDICATE == 0 && "FIRST_FCMP_PREDICATE is required to be 0"
) ? static_cast<void> (0) : __assert_fail ("FIRST_FCMP_PREDICATE == 0 && \"FIRST_FCMP_PREDICATE is required to be 0\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 812, __PRETTY_FUNCTION__))
;
813 return P <= LAST_FCMP_PREDICATE;
814 }
815
816 static bool isIntPredicate(Predicate P) {
817 return P >= FIRST_ICMP_PREDICATE && P <= LAST_ICMP_PREDICATE;
818 }
819
820 static StringRef getPredicateName(Predicate P);
821
822 bool isFPPredicate() const { return isFPPredicate(getPredicate()); }
823 bool isIntPredicate() const { return isIntPredicate(getPredicate()); }
824
825 /// For example, EQ -> NE, UGT -> ULE, SLT -> SGE,
826 /// OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
827 /// @returns the inverse predicate for the instruction's current predicate.
828 /// Return the inverse of the instruction's predicate.
829 Predicate getInversePredicate() const {
830 return getInversePredicate(getPredicate());
831 }
832
833 /// For example, EQ -> NE, UGT -> ULE, SLT -> SGE,
834 /// OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
835 /// @returns the inverse predicate for predicate provided in \p pred.
836 /// Return the inverse of a given predicate
837 static Predicate getInversePredicate(Predicate pred);
838
839 /// For example, EQ->EQ, SLE->SGE, ULT->UGT,
840 /// OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
841 /// @returns the predicate that would be the result of exchanging the two
842 /// operands of the CmpInst instruction without changing the result
843 /// produced.
844 /// Return the predicate as if the operands were swapped
845 Predicate getSwappedPredicate() const {
846 return getSwappedPredicate(getPredicate());
847 }
848
849 /// This is a static version that you can use without an instruction
850 /// available.
851 /// Return the predicate as if the operands were swapped.
852 static Predicate getSwappedPredicate(Predicate pred);
853
854 /// For predicate of kind "is X or equal to 0" returns the predicate "is X".
855 /// For predicate of kind "is X" returns the predicate "is X or equal to 0".
856 /// does not support other kind of predicates.
857 /// @returns the predicate that does not contains is equal to zero if
858 /// it had and vice versa.
859 /// Return the flipped strictness of predicate
860 Predicate getFlippedStrictnessPredicate() const {
861 return getFlippedStrictnessPredicate(getPredicate());
862 }
863
864 /// This is a static version that you can use without an instruction
865 /// available.
866 /// Return the flipped strictness of predicate
867 static Predicate getFlippedStrictnessPredicate(Predicate pred);
868
869 /// For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
870 /// Returns the non-strict version of strict comparisons.
871 Predicate getNonStrictPredicate() const {
872 return getNonStrictPredicate(getPredicate());
873 }
874
875 /// This is a static version that you can use without an instruction
876 /// available.
877 /// @returns the non-strict version of comparison provided in \p pred.
878 /// If \p pred is not a strict comparison predicate, returns \p pred.
879 /// Returns the non-strict version of strict comparisons.
880 static Predicate getNonStrictPredicate(Predicate pred);
881
882 /// Provide more efficient getOperand methods.
883 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value)public: inline Value *getOperand(unsigned) const; inline void
setOperand(unsigned, Value*); inline op_iterator op_begin();
inline const_op_iterator op_begin() const; inline op_iterator
op_end(); inline const_op_iterator op_end() const; protected
: template <int> inline Use &Op(); template <int
> inline const Use &Op() const; public: inline unsigned
getNumOperands() const
;
884
885 /// This is just a convenience that dispatches to the subclasses.
886 /// Swap the operands and adjust predicate accordingly to retain
887 /// the same comparison.
888 void swapOperands();
889
890 /// This is just a convenience that dispatches to the subclasses.
891 /// Determine if this CmpInst is commutative.
892 bool isCommutative() const;
893
894 /// Determine if this is an equals/not equals predicate.
895 /// This is a static version that you can use without an instruction
896 /// available.
897 static bool isEquality(Predicate pred);
898
899 /// Determine if this is an equals/not equals predicate.
900 bool isEquality() const { return isEquality(getPredicate()); }
901
902 /// Return true if the predicate is relational (not EQ or NE).
903 static bool isRelational(Predicate P) { return !isEquality(P); }
904
905 /// Return true if the predicate is relational (not EQ or NE).
906 bool isRelational() const { return !isEquality(); }
907
908 /// @returns true if the comparison is signed, false otherwise.
909 /// Determine if this instruction is using a signed comparison.
910 bool isSigned() const {
911 return isSigned(getPredicate());
912 }
913
914 /// @returns true if the comparison is unsigned, false otherwise.
915 /// Determine if this instruction is using an unsigned comparison.
916 bool isUnsigned() const {
917 return isUnsigned(getPredicate());
918 }
919
920 /// For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert
921 /// @returns the signed version of the unsigned predicate pred.
922 /// return the signed version of a predicate
923 static Predicate getSignedPredicate(Predicate pred);
924
925 /// For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert
926 /// @returns the signed version of the predicate for this instruction (which
927 /// has to be an unsigned predicate).
928 /// return the signed version of a predicate
929 Predicate getSignedPredicate() {
930 return getSignedPredicate(getPredicate());
931 }
932
933 /// For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert
934 /// @returns the unsigned version of the signed predicate pred.
935 static Predicate getUnsignedPredicate(Predicate pred);
936
937 /// For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert
938 /// @returns the unsigned version of the predicate for this instruction (which
939 /// has to be an signed predicate).
940 /// return the unsigned version of a predicate
941 Predicate getUnsignedPredicate() {
942 return getUnsignedPredicate(getPredicate());
943 }
944
945 /// For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert
946 /// @returns the unsigned version of the signed predicate pred or
947 /// the signed version of the signed predicate pred.
948 static Predicate getFlippedSignednessPredicate(Predicate pred);
949
950 /// For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert
951 /// @returns the unsigned version of the signed predicate pred or
952 /// the signed version of the signed predicate pred.
953 Predicate getFlippedSignednessPredicate() {
954 return getFlippedSignednessPredicate(getPredicate());
955 }
956
957 /// This is just a convenience.
958 /// Determine if this is true when both operands are the same.
959 bool isTrueWhenEqual() const {
960 return isTrueWhenEqual(getPredicate());
961 }
962
963 /// This is just a convenience.
964 /// Determine if this is false when both operands are the same.
965 bool isFalseWhenEqual() const {
966 return isFalseWhenEqual(getPredicate());
967 }
968
969 /// @returns true if the predicate is unsigned, false otherwise.
970 /// Determine if the predicate is an unsigned operation.
971 static bool isUnsigned(Predicate predicate);
972
973 /// @returns true if the predicate is signed, false otherwise.
974 /// Determine if the predicate is an signed operation.
975 static bool isSigned(Predicate predicate);
976
977 /// Determine if the predicate is an ordered operation.
978 static bool isOrdered(Predicate predicate);
979
980 /// Determine if the predicate is an unordered operation.
981 static bool isUnordered(Predicate predicate);
982
983 /// Determine if the predicate is true when comparing a value with itself.
984 static bool isTrueWhenEqual(Predicate predicate);
985
986 /// Determine if the predicate is false when comparing a value with itself.
987 static bool isFalseWhenEqual(Predicate predicate);
988
989 /// Determine if Pred1 implies Pred2 is true when two compares have matching
990 /// operands.
991 static bool isImpliedTrueByMatchingCmp(Predicate Pred1, Predicate Pred2);
992
993 /// Determine if Pred1 implies Pred2 is false when two compares have matching
994 /// operands.
995 static bool isImpliedFalseByMatchingCmp(Predicate Pred1, Predicate Pred2);
996
997 /// Methods for support type inquiry through isa, cast, and dyn_cast:
998 static bool classof(const Instruction *I) {
999 return I->getOpcode() == Instruction::ICmp ||
1000 I->getOpcode() == Instruction::FCmp;
1001 }
1002 static bool classof(const Value *V) {
1003 return isa<Instruction>(V) && classof(cast<Instruction>(V));
1004 }
1005
1006 /// Create a result type for fcmp/icmp
1007 static Type* makeCmpResultType(Type* opnd_type) {
1008 if (VectorType* vt = dyn_cast<VectorType>(opnd_type)) {
1009 return VectorType::get(Type::getInt1Ty(opnd_type->getContext()),
1010 vt->getElementCount());
1011 }
1012 return Type::getInt1Ty(opnd_type->getContext());
1013 }
1014
1015private:
1016 // Shadow Value::setValueSubclassData with a private forwarding method so that
1017 // subclasses cannot accidentally use it.
1018 void setValueSubclassData(unsigned short D) {
1019 Value::setValueSubclassData(D);
1020 }
1021};
1022
1023// FIXME: these are redundant if CmpInst < BinaryOperator
1024template <>
1025struct OperandTraits<CmpInst> : public FixedNumOperandTraits<CmpInst, 2> {
1026};
1027
1028DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CmpInst, Value)CmpInst::op_iterator CmpInst::op_begin() { return OperandTraits
<CmpInst>::op_begin(this); } CmpInst::const_op_iterator
CmpInst::op_begin() const { return OperandTraits<CmpInst>
::op_begin(const_cast<CmpInst*>(this)); } CmpInst::op_iterator
CmpInst::op_end() { return OperandTraits<CmpInst>::op_end
(this); } CmpInst::const_op_iterator CmpInst::op_end() const {
return OperandTraits<CmpInst>::op_end(const_cast<CmpInst
*>(this)); } Value *CmpInst::getOperand(unsigned i_nocapture
) const { ((i_nocapture < OperandTraits<CmpInst>::operands
(this) && "getOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<CmpInst>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1028, __PRETTY_FUNCTION__)); return cast_or_null<Value>
( OperandTraits<CmpInst>::op_begin(const_cast<CmpInst
*>(this))[i_nocapture].get()); } void CmpInst::setOperand(
unsigned i_nocapture, Value *Val_nocapture) { ((i_nocapture <
OperandTraits<CmpInst>::operands(this) && "setOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<CmpInst>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1028, __PRETTY_FUNCTION__)); OperandTraits<CmpInst>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned CmpInst
::getNumOperands() const { return OperandTraits<CmpInst>
::operands(this); } template <int Idx_nocapture> Use &
CmpInst::Op() { return this->OpFrom<Idx_nocapture>(this
); } template <int Idx_nocapture> const Use &CmpInst
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
1029
1030/// A lightweight accessor for an operand bundle meant to be passed
1031/// around by value.
1032struct OperandBundleUse {
1033 ArrayRef<Use> Inputs;
1034
1035 OperandBundleUse() = default;
1036 explicit OperandBundleUse(StringMapEntry<uint32_t> *Tag, ArrayRef<Use> Inputs)
1037 : Inputs(Inputs), Tag(Tag) {}
1038
1039 /// Return true if the operand at index \p Idx in this operand bundle
1040 /// has the attribute A.
1041 bool operandHasAttr(unsigned Idx, Attribute::AttrKind A) const {
1042 if (isDeoptOperandBundle())
1043 if (A == Attribute::ReadOnly || A == Attribute::NoCapture)
1044 return Inputs[Idx]->getType()->isPointerTy();
1045
1046 // Conservative answer: no operands have any attributes.
1047 return false;
1048 }
1049
1050 /// Return the tag of this operand bundle as a string.
1051 StringRef getTagName() const {
1052 return Tag->getKey();
1053 }
1054
1055 /// Return the tag of this operand bundle as an integer.
1056 ///
1057 /// Operand bundle tags are interned by LLVMContextImpl::getOrInsertBundleTag,
1058 /// and this function returns the unique integer getOrInsertBundleTag
1059 /// associated the tag of this operand bundle to.
1060 uint32_t getTagID() const {
1061 return Tag->getValue();
1062 }
1063
1064 /// Return true if this is a "deopt" operand bundle.
1065 bool isDeoptOperandBundle() const {
1066 return getTagID() == LLVMContext::OB_deopt;
1067 }
1068
1069 /// Return true if this is a "funclet" operand bundle.
1070 bool isFuncletOperandBundle() const {
1071 return getTagID() == LLVMContext::OB_funclet;
1072 }
1073
1074 /// Return true if this is a "cfguardtarget" operand bundle.
1075 bool isCFGuardTargetOperandBundle() const {
1076 return getTagID() == LLVMContext::OB_cfguardtarget;
1077 }
1078
1079private:
1080 /// Pointer to an entry in LLVMContextImpl::getOrInsertBundleTag.
1081 StringMapEntry<uint32_t> *Tag;
1082};
1083
1084/// A container for an operand bundle being viewed as a set of values
1085/// rather than a set of uses.
1086///
1087/// Unlike OperandBundleUse, OperandBundleDefT owns the memory it carries, and
1088/// so it is possible to create and pass around "self-contained" instances of
1089/// OperandBundleDef and ConstOperandBundleDef.
1090template <typename InputTy> class OperandBundleDefT {
1091 std::string Tag;
1092 std::vector<InputTy> Inputs;
1093
1094public:
1095 explicit OperandBundleDefT(std::string Tag, std::vector<InputTy> Inputs)
1096 : Tag(std::move(Tag)), Inputs(std::move(Inputs)) {}
1097 explicit OperandBundleDefT(std::string Tag, ArrayRef<InputTy> Inputs)
1098 : Tag(std::move(Tag)), Inputs(Inputs) {}
1099
1100 explicit OperandBundleDefT(const OperandBundleUse &OBU) {
1101 Tag = std::string(OBU.getTagName());
1102 Inputs.insert(Inputs.end(), OBU.Inputs.begin(), OBU.Inputs.end());
1103 }
1104
1105 ArrayRef<InputTy> inputs() const { return Inputs; }
1106
1107 using input_iterator = typename std::vector<InputTy>::const_iterator;
1108
1109 size_t input_size() const { return Inputs.size(); }
1110 input_iterator input_begin() const { return Inputs.begin(); }
1111 input_iterator input_end() const { return Inputs.end(); }
1112
1113 StringRef getTag() const { return Tag; }
1114};
1115
1116using OperandBundleDef = OperandBundleDefT<Value *>;
1117using ConstOperandBundleDef = OperandBundleDefT<const Value *>;
1118
1119//===----------------------------------------------------------------------===//
1120// CallBase Class
1121//===----------------------------------------------------------------------===//
1122
1123/// Base class for all callable instructions (InvokeInst and CallInst)
1124/// Holds everything related to calling a function.
1125///
1126/// All call-like instructions are required to use a common operand layout:
1127/// - Zero or more arguments to the call,
1128/// - Zero or more operand bundles with zero or more operand inputs each
1129/// bundle,
1130/// - Zero or more subclass controlled operands
1131/// - The called function.
1132///
1133/// This allows this base class to easily access the called function and the
1134/// start of the arguments without knowing how many other operands a particular
1135/// subclass requires. Note that accessing the end of the argument list isn't
1136/// as cheap as most other operations on the base class.
1137class CallBase : public Instruction {
1138protected:
1139 // The first two bits are reserved by CallInst for fast retrieval,
1140 using CallInstReservedField = Bitfield::Element<unsigned, 0, 2>;
1141 using CallingConvField =
1142 Bitfield::Element<CallingConv::ID, CallInstReservedField::NextBit, 10,
1143 CallingConv::MaxID>;
1144 static_assert(
1145 Bitfield::areContiguous<CallInstReservedField, CallingConvField>(),
1146 "Bitfields must be contiguous");
1147
1148 /// The last operand is the called operand.
1149 static constexpr int CalledOperandOpEndIdx = -1;
1150
1151 AttributeList Attrs; ///< parameter attributes for callable
1152 FunctionType *FTy;
1153
1154 template <class... ArgsTy>
1155 CallBase(AttributeList const &A, FunctionType *FT, ArgsTy &&... Args)
1156 : Instruction(std::forward<ArgsTy>(Args)...), Attrs(A), FTy(FT) {}
1157
1158 using Instruction::Instruction;
1159
1160 bool hasDescriptor() const { return Value::HasDescriptor; }
1161
1162 unsigned getNumSubclassExtraOperands() const {
1163 switch (getOpcode()) {
1164 case Instruction::Call:
1165 return 0;
1166 case Instruction::Invoke:
1167 return 2;
1168 case Instruction::CallBr:
1169 return getNumSubclassExtraOperandsDynamic();
1170 }
1171 llvm_unreachable("Invalid opcode!")::llvm::llvm_unreachable_internal("Invalid opcode!", "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1171)
;
1172 }
1173
1174 /// Get the number of extra operands for instructions that don't have a fixed
1175 /// number of extra operands.
1176 unsigned getNumSubclassExtraOperandsDynamic() const;
1177
1178public:
1179 using Instruction::getContext;
1180
1181 /// Create a clone of \p CB with a different set of operand bundles and
1182 /// insert it before \p InsertPt.
1183 ///
1184 /// The returned call instruction is identical \p CB in every way except that
1185 /// the operand bundles for the new instruction are set to the operand bundles
1186 /// in \p Bundles.
1187 static CallBase *Create(CallBase *CB, ArrayRef<OperandBundleDef> Bundles,
1188 Instruction *InsertPt = nullptr);
1189
1190 static bool classof(const Instruction *I) {
1191 return I->getOpcode() == Instruction::Call ||
1192 I->getOpcode() == Instruction::Invoke ||
1193 I->getOpcode() == Instruction::CallBr;
1194 }
1195 static bool classof(const Value *V) {
1196 return isa<Instruction>(V) && classof(cast<Instruction>(V));
1197 }
1198
1199 FunctionType *getFunctionType() const { return FTy; }
1200
1201 void mutateFunctionType(FunctionType *FTy) {
1202 Value::mutateType(FTy->getReturnType());
1203 this->FTy = FTy;
1204 }
1205
1206 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value)public: inline Value *getOperand(unsigned) const; inline void
setOperand(unsigned, Value*); inline op_iterator op_begin();
inline const_op_iterator op_begin() const; inline op_iterator
op_end(); inline const_op_iterator op_end() const; protected
: template <int> inline Use &Op(); template <int
> inline const Use &Op() const; public: inline unsigned
getNumOperands() const
;
1207
1208 /// data_operands_begin/data_operands_end - Return iterators iterating over
1209 /// the call / invoke argument list and bundle operands. For invokes, this is
1210 /// the set of instruction operands except the invoke target and the two
1211 /// successor blocks; and for calls this is the set of instruction operands
1212 /// except the call target.
1213 User::op_iterator data_operands_begin() { return op_begin(); }
1214 User::const_op_iterator data_operands_begin() const {
1215 return const_cast<CallBase *>(this)->data_operands_begin();
1216 }
1217 User::op_iterator data_operands_end() {
1218 // Walk from the end of the operands over the called operand and any
1219 // subclass operands.
1220 return op_end() - getNumSubclassExtraOperands() - 1;
1221 }
1222 User::const_op_iterator data_operands_end() const {
1223 return const_cast<CallBase *>(this)->data_operands_end();
1224 }
1225 iterator_range<User::op_iterator> data_ops() {
1226 return make_range(data_operands_begin(), data_operands_end());
1227 }
1228 iterator_range<User::const_op_iterator> data_ops() const {
1229 return make_range(data_operands_begin(), data_operands_end());
1230 }
1231 bool data_operands_empty() const {
1232 return data_operands_end() == data_operands_begin();
1233 }
1234 unsigned data_operands_size() const {
1235 return std::distance(data_operands_begin(), data_operands_end());
1236 }
1237
1238 bool isDataOperand(const Use *U) const {
1239 assert(this == U->getUser() &&((this == U->getUser() && "Only valid to query with a use of this instruction!"
) ? static_cast<void> (0) : __assert_fail ("this == U->getUser() && \"Only valid to query with a use of this instruction!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1240, __PRETTY_FUNCTION__))
1240 "Only valid to query with a use of this instruction!")((this == U->getUser() && "Only valid to query with a use of this instruction!"
) ? static_cast<void> (0) : __assert_fail ("this == U->getUser() && \"Only valid to query with a use of this instruction!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1240, __PRETTY_FUNCTION__))
;
1241 return data_operands_begin() <= U && U < data_operands_end();
1242 }
1243 bool isDataOperand(Value::const_user_iterator UI) const {
1244 return isDataOperand(&UI.getUse());
1245 }
1246
1247 /// Given a value use iterator, return the data operand corresponding to it.
1248 /// Iterator must actually correspond to a data operand.
1249 unsigned getDataOperandNo(Value::const_user_iterator UI) const {
1250 return getDataOperandNo(&UI.getUse());
1251 }
1252
1253 /// Given a use for a data operand, get the data operand number that
1254 /// corresponds to it.
1255 unsigned getDataOperandNo(const Use *U) const {
1256 assert(isDataOperand(U) && "Data operand # out of range!")((isDataOperand(U) && "Data operand # out of range!")
? static_cast<void> (0) : __assert_fail ("isDataOperand(U) && \"Data operand # out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1256, __PRETTY_FUNCTION__))
;
1257 return U - data_operands_begin();
1258 }
1259
1260 /// Return the iterator pointing to the beginning of the argument list.
1261 User::op_iterator arg_begin() { return op_begin(); }
1262 User::const_op_iterator arg_begin() const {
1263 return const_cast<CallBase *>(this)->arg_begin();
1264 }
1265
1266 /// Return the iterator pointing to the end of the argument list.
1267 User::op_iterator arg_end() {
1268 // From the end of the data operands, walk backwards past the bundle
1269 // operands.
1270 return data_operands_end() - getNumTotalBundleOperands();
1271 }
1272 User::const_op_iterator arg_end() const {
1273 return const_cast<CallBase *>(this)->arg_end();
1274 }
1275
1276 /// Iteration adapter for range-for loops.
1277 iterator_range<User::op_iterator> args() {
1278 return make_range(arg_begin(), arg_end());
1279 }
1280 iterator_range<User::const_op_iterator> args() const {
1281 return make_range(arg_begin(), arg_end());
1282 }
1283 bool arg_empty() const { return arg_end() == arg_begin(); }
1284 unsigned arg_size() const { return arg_end() - arg_begin(); }
1285
1286 // Legacy API names that duplicate the above and will be removed once users
1287 // are migrated.
1288 iterator_range<User::op_iterator> arg_operands() {
1289 return make_range(arg_begin(), arg_end());
1290 }
1291 iterator_range<User::const_op_iterator> arg_operands() const {
1292 return make_range(arg_begin(), arg_end());
1293 }
1294 unsigned getNumArgOperands() const { return arg_size(); }
1295
1296 Value *getArgOperand(unsigned i) const {
1297 assert(i < getNumArgOperands() && "Out of bounds!")((i < getNumArgOperands() && "Out of bounds!") ? static_cast
<void> (0) : __assert_fail ("i < getNumArgOperands() && \"Out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1297, __PRETTY_FUNCTION__))
;
1298 return getOperand(i);
1299 }
1300
1301 void setArgOperand(unsigned i, Value *v) {
1302 assert(i < getNumArgOperands() && "Out of bounds!")((i < getNumArgOperands() && "Out of bounds!") ? static_cast
<void> (0) : __assert_fail ("i < getNumArgOperands() && \"Out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1302, __PRETTY_FUNCTION__))
;
1303 setOperand(i, v);
1304 }
1305
1306 /// Wrappers for getting the \c Use of a call argument.
1307 const Use &getArgOperandUse(unsigned i) const {
1308 assert(i < getNumArgOperands() && "Out of bounds!")((i < getNumArgOperands() && "Out of bounds!") ? static_cast
<void> (0) : __assert_fail ("i < getNumArgOperands() && \"Out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1308, __PRETTY_FUNCTION__))
;
1309 return User::getOperandUse(i);
1310 }
1311 Use &getArgOperandUse(unsigned i) {
1312 assert(i < getNumArgOperands() && "Out of bounds!")((i < getNumArgOperands() && "Out of bounds!") ? static_cast
<void> (0) : __assert_fail ("i < getNumArgOperands() && \"Out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1312, __PRETTY_FUNCTION__))
;
1313 return User::getOperandUse(i);
1314 }
1315
1316 bool isArgOperand(const Use *U) const {
1317 assert(this == U->getUser() &&((this == U->getUser() && "Only valid to query with a use of this instruction!"
) ? static_cast<void> (0) : __assert_fail ("this == U->getUser() && \"Only valid to query with a use of this instruction!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1318, __PRETTY_FUNCTION__))
1318 "Only valid to query with a use of this instruction!")((this == U->getUser() && "Only valid to query with a use of this instruction!"
) ? static_cast<void> (0) : __assert_fail ("this == U->getUser() && \"Only valid to query with a use of this instruction!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1318, __PRETTY_FUNCTION__))
;
1319 return arg_begin() <= U && U < arg_end();
1320 }
1321 bool isArgOperand(Value::const_user_iterator UI) const {
1322 return isArgOperand(&UI.getUse());
1323 }
1324
1325 /// Given a use for a arg operand, get the arg operand number that
1326 /// corresponds to it.
1327 unsigned getArgOperandNo(const Use *U) const {
1328 assert(isArgOperand(U) && "Arg operand # out of range!")((isArgOperand(U) && "Arg operand # out of range!") ?
static_cast<void> (0) : __assert_fail ("isArgOperand(U) && \"Arg operand # out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1328, __PRETTY_FUNCTION__))
;
1329 return U - arg_begin();
1330 }
1331
1332 /// Given a value use iterator, return the arg operand number corresponding to
1333 /// it. Iterator must actually correspond to a data operand.
1334 unsigned getArgOperandNo(Value::const_user_iterator UI) const {
1335 return getArgOperandNo(&UI.getUse());
1336 }
1337
1338 /// Returns true if this CallSite passes the given Value* as an argument to
1339 /// the called function.
1340 bool hasArgument(const Value *V) const {
1341 return llvm::any_of(args(), [V](const Value *Arg) { return Arg == V; });
1342 }
1343
1344 Value *getCalledOperand() const { return Op<CalledOperandOpEndIdx>(); }
1345
1346 const Use &getCalledOperandUse() const { return Op<CalledOperandOpEndIdx>(); }
1347 Use &getCalledOperandUse() { return Op<CalledOperandOpEndIdx>(); }
1348
1349 /// Returns the function called, or null if this is an
1350 /// indirect function invocation.
1351 Function *getCalledFunction() const {
1352 return dyn_cast_or_null<Function>(getCalledOperand());
1353 }
1354
1355 /// Return true if the callsite is an indirect call.
1356 bool isIndirectCall() const;
1357
1358 /// Determine whether the passed iterator points to the callee operand's Use.
1359 bool isCallee(Value::const_user_iterator UI) const {
1360 return isCallee(&UI.getUse());
1361 }
1362
1363 /// Determine whether this Use is the callee operand's Use.
1364 bool isCallee(const Use *U) const { return &getCalledOperandUse() == U; }
1365
1366 /// Helper to get the caller (the parent function).
1367 Function *getCaller();
1368 const Function *getCaller() const {
1369 return const_cast<CallBase *>(this)->getCaller();
1370 }
1371
1372 /// Tests if this call site must be tail call optimized. Only a CallInst can
1373 /// be tail call optimized.
1374 bool isMustTailCall() const;
1375
1376 /// Tests if this call site is marked as a tail call.
1377 bool isTailCall() const;
1378
1379 /// Returns the intrinsic ID of the intrinsic called or
1380 /// Intrinsic::not_intrinsic if the called function is not an intrinsic, or if
1381 /// this is an indirect call.
1382 Intrinsic::ID getIntrinsicID() const;
1383
1384 void setCalledOperand(Value *V) { Op<CalledOperandOpEndIdx>() = V; }
1385
1386 /// Sets the function called, including updating the function type.
1387 void setCalledFunction(Function *Fn) {
1388 setCalledFunction(Fn->getFunctionType(), Fn);
1389 }
1390
1391 /// Sets the function called, including updating the function type.
1392 void setCalledFunction(FunctionCallee Fn) {
1393 setCalledFunction(Fn.getFunctionType(), Fn.getCallee());
1394 }
1395
1396 /// Sets the function called, including updating to the specified function
1397 /// type.
1398 void setCalledFunction(FunctionType *FTy, Value *Fn) {
1399 this->FTy = FTy;
1400 assert(FTy == cast<FunctionType>(((FTy == cast<FunctionType>( cast<PointerType>(Fn
->getType())->getElementType())) ? static_cast<void>
(0) : __assert_fail ("FTy == cast<FunctionType>( cast<PointerType>(Fn->getType())->getElementType())"
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1401, __PRETTY_FUNCTION__))
1401 cast<PointerType>(Fn->getType())->getElementType()))((FTy == cast<FunctionType>( cast<PointerType>(Fn
->getType())->getElementType())) ? static_cast<void>
(0) : __assert_fail ("FTy == cast<FunctionType>( cast<PointerType>(Fn->getType())->getElementType())"
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1401, __PRETTY_FUNCTION__))
;
1402 // This function doesn't mutate the return type, only the function
1403 // type. Seems broken, but I'm just gonna stick an assert in for now.
1404 assert(getType() == FTy->getReturnType())((getType() == FTy->getReturnType()) ? static_cast<void
> (0) : __assert_fail ("getType() == FTy->getReturnType()"
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1404, __PRETTY_FUNCTION__))
;
1405 setCalledOperand(Fn);
1406 }
1407
1408 CallingConv::ID getCallingConv() const {
1409 return getSubclassData<CallingConvField>();
1410 }
1411
1412 void setCallingConv(CallingConv::ID CC) {
1413 setSubclassData<CallingConvField>(CC);
1414 }
1415
1416 /// Check if this call is an inline asm statement.
1417 bool isInlineAsm() const { return isa<InlineAsm>(getCalledOperand()); }
1418
1419 /// \name Attribute API
1420 ///
1421 /// These methods access and modify attributes on this call (including
1422 /// looking through to the attributes on the called function when necessary).
1423 ///@{
1424
1425 /// Return the parameter attributes for this call.
1426 ///
1427 AttributeList getAttributes() const { return Attrs; }
1428
1429 /// Set the parameter attributes for this call.
1430 ///
1431 void setAttributes(AttributeList A) { Attrs = A; }
1432
1433 /// Determine whether this call has the given attribute. If it does not
1434 /// then determine if the called function has the attribute, but only if
1435 /// the attribute is allowed for the call.
1436 bool hasFnAttr(Attribute::AttrKind Kind) const {
1437 assert(Kind != Attribute::NoBuiltin &&((Kind != Attribute::NoBuiltin && "Use CallBase::isNoBuiltin() to check for Attribute::NoBuiltin"
) ? static_cast<void> (0) : __assert_fail ("Kind != Attribute::NoBuiltin && \"Use CallBase::isNoBuiltin() to check for Attribute::NoBuiltin\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1438, __PRETTY_FUNCTION__))
23
'?' condition is true
1438 "Use CallBase::isNoBuiltin() to check for Attribute::NoBuiltin")((Kind != Attribute::NoBuiltin && "Use CallBase::isNoBuiltin() to check for Attribute::NoBuiltin"
) ? static_cast<void> (0) : __assert_fail ("Kind != Attribute::NoBuiltin && \"Use CallBase::isNoBuiltin() to check for Attribute::NoBuiltin\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1438, __PRETTY_FUNCTION__))
;
1439 return hasFnAttrImpl(Kind);
24
Calling 'CallBase::hasFnAttrImpl'
33
Returning from 'CallBase::hasFnAttrImpl'
34
Returning value, which participates in a condition later
1440 }
1441
1442 /// Determine whether this call has the given attribute. If it does not
1443 /// then determine if the called function has the attribute, but only if
1444 /// the attribute is allowed for the call.
1445 bool hasFnAttr(StringRef Kind) const { return hasFnAttrImpl(Kind); }
1446
1447 /// adds the attribute to the list of attributes.
1448 void addAttribute(unsigned i, Attribute::AttrKind Kind) {
1449 AttributeList PAL = getAttributes();
1450 PAL = PAL.addAttribute(getContext(), i, Kind);
1451 setAttributes(PAL);
1452 }
1453
1454 /// adds the attribute to the list of attributes.
1455 void addAttribute(unsigned i, Attribute Attr) {
1456 AttributeList PAL = getAttributes();
1457 PAL = PAL.addAttribute(getContext(), i, Attr);
1458 setAttributes(PAL);
1459 }
1460
1461 /// Adds the attribute to the indicated argument
1462 void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) {
1463 assert(ArgNo < getNumArgOperands() && "Out of bounds")((ArgNo < getNumArgOperands() && "Out of bounds") ?
static_cast<void> (0) : __assert_fail ("ArgNo < getNumArgOperands() && \"Out of bounds\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1463, __PRETTY_FUNCTION__))
;
1464 AttributeList PAL = getAttributes();
1465 PAL = PAL.addParamAttribute(getContext(), ArgNo, Kind);
1466 setAttributes(PAL);
1467 }
1468
1469 /// Adds the attribute to the indicated argument
1470 void addParamAttr(unsigned ArgNo, Attribute Attr) {
1471 assert(ArgNo < getNumArgOperands() && "Out of bounds")((ArgNo < getNumArgOperands() && "Out of bounds") ?
static_cast<void> (0) : __assert_fail ("ArgNo < getNumArgOperands() && \"Out of bounds\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1471, __PRETTY_FUNCTION__))
;
1472 AttributeList PAL = getAttributes();
1473 PAL = PAL.addParamAttribute(getContext(), ArgNo, Attr);
1474 setAttributes(PAL);
1475 }
1476
1477 /// removes the attribute from the list of attributes.
1478 void removeAttribute(unsigned i, Attribute::AttrKind Kind) {
1479 AttributeList PAL = getAttributes();
1480 PAL = PAL.removeAttribute(getContext(), i, Kind);
1481 setAttributes(PAL);
1482 }
1483
1484 /// removes the attribute from the list of attributes.
1485 void removeAttribute(unsigned i, StringRef Kind) {
1486 AttributeList PAL = getAttributes();
1487 PAL = PAL.removeAttribute(getContext(), i, Kind);
1488 setAttributes(PAL);
1489 }
1490
1491 void removeAttributes(unsigned i, const AttrBuilder &Attrs) {
1492 AttributeList PAL = getAttributes();
1493 PAL = PAL.removeAttributes(getContext(), i, Attrs);
1494 setAttributes(PAL);
1495 }
1496
1497 /// Removes the attribute from the given argument
1498 void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) {
1499 assert(ArgNo < getNumArgOperands() && "Out of bounds")((ArgNo < getNumArgOperands() && "Out of bounds") ?
static_cast<void> (0) : __assert_fail ("ArgNo < getNumArgOperands() && \"Out of bounds\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1499, __PRETTY_FUNCTION__))
;
1500 AttributeList PAL = getAttributes();
1501 PAL = PAL.removeParamAttribute(getContext(), ArgNo, Kind);
1502 setAttributes(PAL);
1503 }
1504
1505 /// Removes the attribute from the given argument
1506 void removeParamAttr(unsigned ArgNo, StringRef Kind) {
1507 assert(ArgNo < getNumArgOperands() && "Out of bounds")((ArgNo < getNumArgOperands() && "Out of bounds") ?
static_cast<void> (0) : __assert_fail ("ArgNo < getNumArgOperands() && \"Out of bounds\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1507, __PRETTY_FUNCTION__))
;
1508 AttributeList PAL = getAttributes();
1509 PAL = PAL.removeParamAttribute(getContext(), ArgNo, Kind);
1510 setAttributes(PAL);
1511 }
1512
1513 /// adds the dereferenceable attribute to the list of attributes.
1514 void addDereferenceableAttr(unsigned i, uint64_t Bytes) {
1515 AttributeList PAL = getAttributes();
1516 PAL = PAL.addDereferenceableAttr(getContext(), i, Bytes);
1517 setAttributes(PAL);
1518 }
1519
1520 /// adds the dereferenceable_or_null attribute to the list of
1521 /// attributes.
1522 void addDereferenceableOrNullAttr(unsigned i, uint64_t Bytes) {
1523 AttributeList PAL = getAttributes();
1524 PAL = PAL.addDereferenceableOrNullAttr(getContext(), i, Bytes);
1525 setAttributes(PAL);
1526 }
1527
1528 /// Determine whether the return value has the given attribute.
1529 bool hasRetAttr(Attribute::AttrKind Kind) const;
1530
1531 /// Determine whether the argument or parameter has the given attribute.
1532 bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const;
1533
1534 /// Get the attribute of a given kind at a position.
1535 Attribute getAttribute(unsigned i, Attribute::AttrKind Kind) const {
1536 return getAttributes().getAttribute(i, Kind);
1537 }
1538
1539 /// Get the attribute of a given kind at a position.
1540 Attribute getAttribute(unsigned i, StringRef Kind) const {
1541 return getAttributes().getAttribute(i, Kind);
1542 }
1543
1544 /// Get the attribute of a given kind from a given arg
1545 Attribute getParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) const {
1546 assert(ArgNo < getNumArgOperands() && "Out of bounds")((ArgNo < getNumArgOperands() && "Out of bounds") ?
static_cast<void> (0) : __assert_fail ("ArgNo < getNumArgOperands() && \"Out of bounds\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1546, __PRETTY_FUNCTION__))
;
1547 return getAttributes().getParamAttr(ArgNo, Kind);
1548 }
1549
1550 /// Get the attribute of a given kind from a given arg
1551 Attribute getParamAttr(unsigned ArgNo, StringRef Kind) const {
1552 assert(ArgNo < getNumArgOperands() && "Out of bounds")((ArgNo < getNumArgOperands() && "Out of bounds") ?
static_cast<void> (0) : __assert_fail ("ArgNo < getNumArgOperands() && \"Out of bounds\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1552, __PRETTY_FUNCTION__))
;
1553 return getAttributes().getParamAttr(ArgNo, Kind);
1554 }
1555
1556 /// Return true if the data operand at index \p i has the attribute \p
1557 /// A.
1558 ///
1559 /// Data operands include call arguments and values used in operand bundles,
1560 /// but does not include the callee operand. This routine dispatches to the
1561 /// underlying AttributeList or the OperandBundleUser as appropriate.
1562 ///
1563 /// The index \p i is interpreted as
1564 ///
1565 /// \p i == Attribute::ReturnIndex -> the return value
1566 /// \p i in [1, arg_size + 1) -> argument number (\p i - 1)
1567 /// \p i in [arg_size + 1, data_operand_size + 1) -> bundle operand at index
1568 /// (\p i - 1) in the operand list.
1569 bool dataOperandHasImpliedAttr(unsigned i, Attribute::AttrKind Kind) const {
1570 // Note that we have to add one because `i` isn't zero-indexed.
1571 assert(i < (getNumArgOperands() + getNumTotalBundleOperands() + 1) &&((i < (getNumArgOperands() + getNumTotalBundleOperands() +
1) && "Data operand index out of bounds!") ? static_cast
<void> (0) : __assert_fail ("i < (getNumArgOperands() + getNumTotalBundleOperands() + 1) && \"Data operand index out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1572, __PRETTY_FUNCTION__))
1572 "Data operand index out of bounds!")((i < (getNumArgOperands() + getNumTotalBundleOperands() +
1) && "Data operand index out of bounds!") ? static_cast
<void> (0) : __assert_fail ("i < (getNumArgOperands() + getNumTotalBundleOperands() + 1) && \"Data operand index out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1572, __PRETTY_FUNCTION__))
;
1573
1574 // The attribute A can either be directly specified, if the operand in
1575 // question is a call argument; or be indirectly implied by the kind of its
1576 // containing operand bundle, if the operand is a bundle operand.
1577
1578 if (i == AttributeList::ReturnIndex)
1579 return hasRetAttr(Kind);
1580
1581 // FIXME: Avoid these i - 1 calculations and update the API to use
1582 // zero-based indices.
1583 if (i < (getNumArgOperands() + 1))
1584 return paramHasAttr(i - 1, Kind);
1585
1586 assert(hasOperandBundles() && i >= (getBundleOperandsStartIndex() + 1) &&((hasOperandBundles() && i >= (getBundleOperandsStartIndex
() + 1) && "Must be either a call argument or an operand bundle!"
) ? static_cast<void> (0) : __assert_fail ("hasOperandBundles() && i >= (getBundleOperandsStartIndex() + 1) && \"Must be either a call argument or an operand bundle!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1587, __PRETTY_FUNCTION__))
1587 "Must be either a call argument or an operand bundle!")((hasOperandBundles() && i >= (getBundleOperandsStartIndex
() + 1) && "Must be either a call argument or an operand bundle!"
) ? static_cast<void> (0) : __assert_fail ("hasOperandBundles() && i >= (getBundleOperandsStartIndex() + 1) && \"Must be either a call argument or an operand bundle!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1587, __PRETTY_FUNCTION__))
;
1588 return bundleOperandHasAttr(i - 1, Kind);
1589 }
1590
1591 /// Determine whether this data operand is not captured.
1592 // FIXME: Once this API is no longer duplicated in `CallSite`, rename this to
1593 // better indicate that this may return a conservative answer.
1594 bool doesNotCapture(unsigned OpNo) const {
1595 return dataOperandHasImpliedAttr(OpNo + 1, Attribute::NoCapture);
1596 }
1597
1598 /// Determine whether this argument is passed by value.
1599 bool isByValArgument(unsigned ArgNo) const {
1600 return paramHasAttr(ArgNo, Attribute::ByVal);
1601 }
1602
1603 /// Determine whether this argument is passed in an alloca.
1604 bool isInAllocaArgument(unsigned ArgNo) const {
1605 return paramHasAttr(ArgNo, Attribute::InAlloca);
1606 }
1607
1608 /// Determine whether this argument is passed by value, in an alloca, or is
1609 /// preallocated.
1610 bool isPassPointeeByValueArgument(unsigned ArgNo) const {
1611 return paramHasAttr(ArgNo, Attribute::ByVal) ||
1612 paramHasAttr(ArgNo, Attribute::InAlloca) ||
1613 paramHasAttr(ArgNo, Attribute::Preallocated);
1614 }
1615
1616 /// Determine if there are is an inalloca argument. Only the last argument can
1617 /// have the inalloca attribute.
1618 bool hasInAllocaArgument() const {
1619 return !arg_empty() && paramHasAttr(arg_size() - 1, Attribute::InAlloca);
1620 }
1621
1622 // FIXME: Once this API is no longer duplicated in `CallSite`, rename this to
1623 // better indicate that this may return a conservative answer.
1624 bool doesNotAccessMemory(unsigned OpNo) const {
1625 return dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadNone);
1626 }
1627
1628 // FIXME: Once this API is no longer duplicated in `CallSite`, rename this to
1629 // better indicate that this may return a conservative answer.
1630 bool onlyReadsMemory(unsigned OpNo) const {
1631 return dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadOnly) ||
1632 dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadNone);
1633 }
1634
1635 // FIXME: Once this API is no longer duplicated in `CallSite`, rename this to
1636 // better indicate that this may return a conservative answer.
1637 bool doesNotReadMemory(unsigned OpNo) const {
1638 return dataOperandHasImpliedAttr(OpNo + 1, Attribute::WriteOnly) ||
1639 dataOperandHasImpliedAttr(OpNo + 1, Attribute::ReadNone);
1640 }
1641
1642 LLVM_ATTRIBUTE_DEPRECATED(unsigned getRetAlignment() const,unsigned getRetAlignment() const __attribute__((deprecated("Use getRetAlign() instead"
)))
1643 "Use getRetAlign() instead")unsigned getRetAlignment() const __attribute__((deprecated("Use getRetAlign() instead"
)))
{
1644 if (const auto MA = Attrs.getRetAlignment())
1645 return MA->value();
1646 return 0;
1647 }
1648
1649 /// Extract the alignment of the return value.
1650 MaybeAlign getRetAlign() const { return Attrs.getRetAlignment(); }
1651
1652 /// Extract the alignment for a call or parameter (0=unknown).
1653 LLVM_ATTRIBUTE_DEPRECATED(unsigned getParamAlignment(unsigned ArgNo) const,unsigned getParamAlignment(unsigned ArgNo) const __attribute__
((deprecated("Use getParamAlign() instead")))
1654 "Use getParamAlign() instead")unsigned getParamAlignment(unsigned ArgNo) const __attribute__
((deprecated("Use getParamAlign() instead")))
{
1655 if (const auto MA = Attrs.getParamAlignment(ArgNo))
1656 return MA->value();
1657 return 0;
1658 }
1659
1660 /// Extract the alignment for a call or parameter (0=unknown).
1661 MaybeAlign getParamAlign(unsigned ArgNo) const {
1662 return Attrs.getParamAlignment(ArgNo);
1663 }
1664
1665 /// Extract the byval type for a call or parameter.
1666 Type *getParamByValType(unsigned ArgNo) const {
1667 Type *Ty = Attrs.getParamByValType(ArgNo);
1668 return Ty ? Ty : getArgOperand(ArgNo)->getType()->getPointerElementType();
1669 }
1670
1671 /// Extract the preallocated type for a call or parameter.
1672 Type *getParamPreallocatedType(unsigned ArgNo) const {
1673 Type *Ty = Attrs.getParamPreallocatedType(ArgNo);
1674 return Ty ? Ty : getArgOperand(ArgNo)->getType()->getPointerElementType();
1675 }
1676
1677 /// Extract the number of dereferenceable bytes for a call or
1678 /// parameter (0=unknown).
1679 uint64_t getDereferenceableBytes(unsigned i) const {
1680 return Attrs.getDereferenceableBytes(i);
1681 }
1682
1683 /// Extract the number of dereferenceable_or_null bytes for a call or
1684 /// parameter (0=unknown).
1685 uint64_t getDereferenceableOrNullBytes(unsigned i) const {
1686 return Attrs.getDereferenceableOrNullBytes(i);
1687 }
1688
1689 /// Return true if the return value is known to be not null.
1690 /// This may be because it has the nonnull attribute, or because at least
1691 /// one byte is dereferenceable and the pointer is in addrspace(0).
1692 bool isReturnNonNull() const;
1693
1694 /// Determine if the return value is marked with NoAlias attribute.
1695 bool returnDoesNotAlias() const {
1696 return Attrs.hasAttribute(AttributeList::ReturnIndex, Attribute::NoAlias);
1697 }
1698
1699 /// If one of the arguments has the 'returned' attribute, returns its
1700 /// operand value. Otherwise, return nullptr.
1701 Value *getReturnedArgOperand() const;
1702
1703 /// Return true if the call should not be treated as a call to a
1704 /// builtin.
1705 bool isNoBuiltin() const {
1706 return hasFnAttrImpl(Attribute::NoBuiltin) &&
1707 !hasFnAttrImpl(Attribute::Builtin);
1708 }
1709
1710 /// Determine if the call requires strict floating point semantics.
1711 bool isStrictFP() const { return hasFnAttr(Attribute::StrictFP); }
1712
1713 /// Return true if the call should not be inlined.
1714 bool isNoInline() const { return hasFnAttr(Attribute::NoInline); }
1715 void setIsNoInline() {
1716 addAttribute(AttributeList::FunctionIndex, Attribute::NoInline);
1717 }
1718 /// Determine if the call does not access memory.
1719 bool doesNotAccessMemory() const { return hasFnAttr(Attribute::ReadNone); }
1720 void setDoesNotAccessMemory() {
1721 addAttribute(AttributeList::FunctionIndex, Attribute::ReadNone);
1722 }
1723
1724 /// Determine if the call does not access or only reads memory.
1725 bool onlyReadsMemory() const {
1726 return doesNotAccessMemory() || hasFnAttr(Attribute::ReadOnly);
1727 }
1728 void setOnlyReadsMemory() {
1729 addAttribute(AttributeList::FunctionIndex, Attribute::ReadOnly);
1730 }
1731
1732 /// Determine if the call does not access or only writes memory.
1733 bool doesNotReadMemory() const {
1734 return doesNotAccessMemory() || hasFnAttr(Attribute::WriteOnly);
1735 }
1736 void setDoesNotReadMemory() {
1737 addAttribute(AttributeList::FunctionIndex, Attribute::WriteOnly);
1738 }
1739
1740 /// Determine if the call can access memmory only using pointers based
1741 /// on its arguments.
1742 bool onlyAccessesArgMemory() const {
1743 return hasFnAttr(Attribute::ArgMemOnly);
1744 }
1745 void setOnlyAccessesArgMemory() {
1746 addAttribute(AttributeList::FunctionIndex, Attribute::ArgMemOnly);
1747 }
1748
1749 /// Determine if the function may only access memory that is
1750 /// inaccessible from the IR.
1751 bool onlyAccessesInaccessibleMemory() const {
1752 return hasFnAttr(Attribute::InaccessibleMemOnly);
1753 }
1754 void setOnlyAccessesInaccessibleMemory() {
1755 addAttribute(AttributeList::FunctionIndex, Attribute::InaccessibleMemOnly);
1756 }
1757
1758 /// Determine if the function may only access memory that is
1759 /// either inaccessible from the IR or pointed to by its arguments.
1760 bool onlyAccessesInaccessibleMemOrArgMem() const {
1761 return hasFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
1762 }
1763 void setOnlyAccessesInaccessibleMemOrArgMem() {
1764 addAttribute(AttributeList::FunctionIndex,
1765 Attribute::InaccessibleMemOrArgMemOnly);
1766 }
1767 /// Determine if the call cannot return.
1768 bool doesNotReturn() const { return hasFnAttr(Attribute::NoReturn); }
1769 void setDoesNotReturn() {
1770 addAttribute(AttributeList::FunctionIndex, Attribute::NoReturn);
1771 }
1772
1773 /// Determine if the call should not perform indirect branch tracking.
1774 bool doesNoCfCheck() const { return hasFnAttr(Attribute::NoCfCheck); }
1775
1776 /// Determine if the call cannot unwind.
1777 bool doesNotThrow() const { return hasFnAttr(Attribute::NoUnwind); }
1778 void setDoesNotThrow() {
1779 addAttribute(AttributeList::FunctionIndex, Attribute::NoUnwind);
1780 }
1781
1782 /// Determine if the invoke cannot be duplicated.
1783 bool cannotDuplicate() const { return hasFnAttr(Attribute::NoDuplicate); }
1784 void setCannotDuplicate() {
1785 addAttribute(AttributeList::FunctionIndex, Attribute::NoDuplicate);
1786 }
1787
1788 /// Determine if the call cannot be tail merged.
1789 bool cannotMerge() const { return hasFnAttr(Attribute::NoMerge); }
1790 void setCannotMerge() {
1791 addAttribute(AttributeList::FunctionIndex, Attribute::NoMerge);
1792 }
1793
1794 /// Determine if the invoke is convergent
1795 bool isConvergent() const { return hasFnAttr(Attribute::Convergent); }
22
Calling 'CallBase::hasFnAttr'
35
Returning from 'CallBase::hasFnAttr'
36
Returning value, which participates in a condition later
1796 void setConvergent() {
1797 addAttribute(AttributeList::FunctionIndex, Attribute::Convergent);
1798 }
1799 void setNotConvergent() {
1800 removeAttribute(AttributeList::FunctionIndex, Attribute::Convergent);
1801 }
1802
1803 /// Determine if the call returns a structure through first
1804 /// pointer argument.
1805 bool hasStructRetAttr() const {
1806 if (getNumArgOperands() == 0)
1807 return false;
1808
1809 // Be friendly and also check the callee.
1810 return paramHasAttr(0, Attribute::StructRet);
1811 }
1812
1813 /// Determine if any call argument is an aggregate passed by value.
1814 bool hasByValArgument() const {
1815 return Attrs.hasAttrSomewhere(Attribute::ByVal);
1816 }
1817
1818 ///@{
1819 // End of attribute API.
1820
1821 /// \name Operand Bundle API
1822 ///
1823 /// This group of methods provides the API to access and manipulate operand
1824 /// bundles on this call.
1825 /// @{
1826
1827 /// Return the number of operand bundles associated with this User.
1828 unsigned getNumOperandBundles() const {
1829 return std::distance(bundle_op_info_begin(), bundle_op_info_end());
1830 }
1831
1832 /// Return true if this User has any operand bundles.
1833 bool hasOperandBundles() const { return getNumOperandBundles() != 0; }
1834
1835 /// Return the index of the first bundle operand in the Use array.
1836 unsigned getBundleOperandsStartIndex() const {
1837 assert(hasOperandBundles() && "Don't call otherwise!")((hasOperandBundles() && "Don't call otherwise!") ? static_cast
<void> (0) : __assert_fail ("hasOperandBundles() && \"Don't call otherwise!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1837, __PRETTY_FUNCTION__))
;
1838 return bundle_op_info_begin()->Begin;
1839 }
1840
1841 /// Return the index of the last bundle operand in the Use array.
1842 unsigned getBundleOperandsEndIndex() const {
1843 assert(hasOperandBundles() && "Don't call otherwise!")((hasOperandBundles() && "Don't call otherwise!") ? static_cast
<void> (0) : __assert_fail ("hasOperandBundles() && \"Don't call otherwise!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1843, __PRETTY_FUNCTION__))
;
1844 return bundle_op_info_end()[-1].End;
1845 }
1846
1847 /// Return true if the operand at index \p Idx is a bundle operand.
1848 bool isBundleOperand(unsigned Idx) const {
1849 return hasOperandBundles() && Idx >= getBundleOperandsStartIndex() &&
1850 Idx < getBundleOperandsEndIndex();
1851 }
1852
1853 /// Returns true if the use is a bundle operand.
1854 bool isBundleOperand(const Use *U) const {
1855 assert(this == U->getUser() &&((this == U->getUser() && "Only valid to query with a use of this instruction!"
) ? static_cast<void> (0) : __assert_fail ("this == U->getUser() && \"Only valid to query with a use of this instruction!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1856, __PRETTY_FUNCTION__))
1856 "Only valid to query with a use of this instruction!")((this == U->getUser() && "Only valid to query with a use of this instruction!"
) ? static_cast<void> (0) : __assert_fail ("this == U->getUser() && \"Only valid to query with a use of this instruction!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1856, __PRETTY_FUNCTION__))
;
1857 return hasOperandBundles() && isBundleOperand(U - op_begin());
1858 }
1859 bool isBundleOperand(Value::const_user_iterator UI) const {
1860 return isBundleOperand(&UI.getUse());
1861 }
1862
1863 /// Return the total number operands (not operand bundles) used by
1864 /// every operand bundle in this OperandBundleUser.
1865 unsigned getNumTotalBundleOperands() const {
1866 if (!hasOperandBundles())
1867 return 0;
1868
1869 unsigned Begin = getBundleOperandsStartIndex();
1870 unsigned End = getBundleOperandsEndIndex();
1871
1872 assert(Begin <= End && "Should be!")((Begin <= End && "Should be!") ? static_cast<void
> (0) : __assert_fail ("Begin <= End && \"Should be!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1872, __PRETTY_FUNCTION__))
;
1873 return End - Begin;
1874 }
1875
1876 /// Return the operand bundle at a specific index.
1877 OperandBundleUse getOperandBundleAt(unsigned Index) const {
1878 assert(Index < getNumOperandBundles() && "Index out of bounds!")((Index < getNumOperandBundles() && "Index out of bounds!"
) ? static_cast<void> (0) : __assert_fail ("Index < getNumOperandBundles() && \"Index out of bounds!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1878, __PRETTY_FUNCTION__))
;
1879 return operandBundleFromBundleOpInfo(*(bundle_op_info_begin() + Index));
1880 }
1881
1882 /// Return the number of operand bundles with the tag Name attached to
1883 /// this instruction.
1884 unsigned countOperandBundlesOfType(StringRef Name) const {
1885 unsigned Count = 0;
1886 for (unsigned i = 0, e = getNumOperandBundles(); i != e; ++i)
1887 if (getOperandBundleAt(i).getTagName() == Name)
1888 Count++;
1889
1890 return Count;
1891 }
1892
1893 /// Return the number of operand bundles with the tag ID attached to
1894 /// this instruction.
1895 unsigned countOperandBundlesOfType(uint32_t ID) const {
1896 unsigned Count = 0;
1897 for (unsigned i = 0, e = getNumOperandBundles(); i != e; ++i)
1898 if (getOperandBundleAt(i).getTagID() == ID)
1899 Count++;
1900
1901 return Count;
1902 }
1903
1904 /// Return an operand bundle by name, if present.
1905 ///
1906 /// It is an error to call this for operand bundle types that may have
1907 /// multiple instances of them on the same instruction.
1908 Optional<OperandBundleUse> getOperandBundle(StringRef Name) const {
1909 assert(countOperandBundlesOfType(Name) < 2 && "Precondition violated!")((countOperandBundlesOfType(Name) < 2 && "Precondition violated!"
) ? static_cast<void> (0) : __assert_fail ("countOperandBundlesOfType(Name) < 2 && \"Precondition violated!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1909, __PRETTY_FUNCTION__))
;
1910
1911 for (unsigned i = 0, e = getNumOperandBundles(); i != e; ++i) {
1912 OperandBundleUse U = getOperandBundleAt(i);
1913 if (U.getTagName() == Name)
1914 return U;
1915 }
1916
1917 return None;
1918 }
1919
1920 /// Return an operand bundle by tag ID, if present.
1921 ///
1922 /// It is an error to call this for operand bundle types that may have
1923 /// multiple instances of them on the same instruction.
1924 Optional<OperandBundleUse> getOperandBundle(uint32_t ID) const {
1925 assert(countOperandBundlesOfType(ID) < 2 && "Precondition violated!")((countOperandBundlesOfType(ID) < 2 && "Precondition violated!"
) ? static_cast<void> (0) : __assert_fail ("countOperandBundlesOfType(ID) < 2 && \"Precondition violated!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 1925, __PRETTY_FUNCTION__))
;
1926
1927 for (unsigned i = 0, e = getNumOperandBundles(); i != e; ++i) {
1928 OperandBundleUse U = getOperandBundleAt(i);
1929 if (U.getTagID() == ID)
1930 return U;
1931 }
1932
1933 return None;
1934 }
1935
1936 /// Return the list of operand bundles attached to this instruction as
1937 /// a vector of OperandBundleDefs.
1938 ///
1939 /// This function copies the OperandBundeUse instances associated with this
1940 /// OperandBundleUser to a vector of OperandBundleDefs. Note:
1941 /// OperandBundeUses and OperandBundleDefs are non-trivially *different*
1942 /// representations of operand bundles (see documentation above).
1943 void getOperandBundlesAsDefs(SmallVectorImpl<OperandBundleDef> &Defs) const;
1944
1945 /// Return the operand bundle for the operand at index OpIdx.
1946 ///
1947 /// It is an error to call this with an OpIdx that does not correspond to an
1948 /// bundle operand.
1949 OperandBundleUse getOperandBundleForOperand(unsigned OpIdx) const {
1950 return operandBundleFromBundleOpInfo(getBundleOpInfoForOperand(OpIdx));
1951 }
1952
1953 /// Return true if this operand bundle user has operand bundles that
1954 /// may read from the heap.
1955 bool hasReadingOperandBundles() const {
1956 // Implementation note: this is a conservative implementation of operand
1957 // bundle semantics, where *any* operand bundle forces a callsite to be at
1958 // least readonly.
1959 return hasOperandBundles();
1960 }
1961
1962 /// Return true if this operand bundle user has operand bundles that
1963 /// may write to the heap.
1964 bool hasClobberingOperandBundles() const {
1965 for (auto &BOI : bundle_op_infos()) {
1966 if (BOI.Tag->second == LLVMContext::OB_deopt ||
1967 BOI.Tag->second == LLVMContext::OB_funclet)
1968 continue;
1969
1970 // This instruction has an operand bundle that is not known to us.
1971 // Assume the worst.
1972 return true;
1973 }
1974
1975 return false;
1976 }
1977
1978 /// Return true if the bundle operand at index \p OpIdx has the
1979 /// attribute \p A.
1980 bool bundleOperandHasAttr(unsigned OpIdx, Attribute::AttrKind A) const {
1981 auto &BOI = getBundleOpInfoForOperand(OpIdx);
1982 auto OBU = operandBundleFromBundleOpInfo(BOI);
1983 return OBU.operandHasAttr(OpIdx - BOI.Begin, A);
1984 }
1985
1986 /// Return true if \p Other has the same sequence of operand bundle
1987 /// tags with the same number of operands on each one of them as this
1988 /// OperandBundleUser.
1989 bool hasIdenticalOperandBundleSchema(const CallBase &Other) const {
1990 if (getNumOperandBundles() != Other.getNumOperandBundles())
1991 return false;
1992
1993 return std::equal(bundle_op_info_begin(), bundle_op_info_end(),
1994 Other.bundle_op_info_begin());
1995 }
1996
1997 /// Return true if this operand bundle user contains operand bundles
1998 /// with tags other than those specified in \p IDs.
1999 bool hasOperandBundlesOtherThan(ArrayRef<uint32_t> IDs) const {
2000 for (unsigned i = 0, e = getNumOperandBundles(); i != e; ++i) {
2001 uint32_t ID = getOperandBundleAt(i).getTagID();
2002 if (!is_contained(IDs, ID))
2003 return true;
2004 }
2005 return false;
2006 }
2007
2008 /// Is the function attribute S disallowed by some operand bundle on
2009 /// this operand bundle user?
2010 bool isFnAttrDisallowedByOpBundle(StringRef S) const {
2011 // Operand bundles only possibly disallow readnone, readonly and argmemonly
2012 // attributes. All String attributes are fine.
2013 return false;
2014 }
2015
2016 /// Is the function attribute A disallowed by some operand bundle on
2017 /// this operand bundle user?
2018 bool isFnAttrDisallowedByOpBundle(Attribute::AttrKind A) const {
2019 switch (A) {
28
Control jumps to the 'default' case at line 2020
2020 default:
2021 return false;
29
Returning zero, which participates in a condition later
2022
2023 case Attribute::InaccessibleMemOrArgMemOnly:
2024 return hasReadingOperandBundles();
2025
2026 case Attribute::InaccessibleMemOnly:
2027 return hasReadingOperandBundles();
2028
2029 case Attribute::ArgMemOnly:
2030 return hasReadingOperandBundles();
2031
2032 case Attribute::ReadNone:
2033 return hasReadingOperandBundles();
2034
2035 case Attribute::ReadOnly:
2036 return hasClobberingOperandBundles();
2037 }
2038
2039 llvm_unreachable("switch has a default case!")::llvm::llvm_unreachable_internal("switch has a default case!"
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 2039)
;
2040 }
2041
2042 /// Used to keep track of an operand bundle. See the main comment on
2043 /// OperandBundleUser above.
2044 struct BundleOpInfo {
2045 /// The operand bundle tag, interned by
2046 /// LLVMContextImpl::getOrInsertBundleTag.
2047 StringMapEntry<uint32_t> *Tag;
2048
2049 /// The index in the Use& vector where operands for this operand
2050 /// bundle starts.
2051 uint32_t Begin;
2052
2053 /// The index in the Use& vector where operands for this operand
2054 /// bundle ends.
2055 uint32_t End;
2056
2057 bool operator==(const BundleOpInfo &Other) const {
2058 return Tag == Other.Tag && Begin == Other.Begin && End == Other.End;
2059 }
2060 };
2061
2062 /// Simple helper function to map a BundleOpInfo to an
2063 /// OperandBundleUse.
2064 OperandBundleUse
2065 operandBundleFromBundleOpInfo(const BundleOpInfo &BOI) const {
2066 auto begin = op_begin();
2067 ArrayRef<Use> Inputs(begin + BOI.Begin, begin + BOI.End);
2068 return OperandBundleUse(BOI.Tag, Inputs);
2069 }
2070
2071 using bundle_op_iterator = BundleOpInfo *;
2072 using const_bundle_op_iterator = const BundleOpInfo *;
2073
2074 /// Return the start of the list of BundleOpInfo instances associated
2075 /// with this OperandBundleUser.
2076 ///
2077 /// OperandBundleUser uses the descriptor area co-allocated with the host User
2078 /// to store some meta information about which operands are "normal" operands,
2079 /// and which ones belong to some operand bundle.
2080 ///
2081 /// The layout of an operand bundle user is
2082 ///
2083 /// +-----------uint32_t End-------------------------------------+
2084 /// | |
2085 /// | +--------uint32_t Begin--------------------+ |
2086 /// | | | |
2087 /// ^ ^ v v
2088 /// |------|------|----|----|----|----|----|---------|----|---------|----|-----
2089 /// | BOI0 | BOI1 | .. | DU | U0 | U1 | .. | BOI0_U0 | .. | BOI1_U0 | .. | Un
2090 /// |------|------|----|----|----|----|----|---------|----|---------|----|-----
2091 /// v v ^ ^
2092 /// | | | |
2093 /// | +--------uint32_t Begin------------+ |
2094 /// | |
2095 /// +-----------uint32_t End-----------------------------+
2096 ///
2097 ///
2098 /// BOI0, BOI1 ... are descriptions of operand bundles in this User's use
2099 /// list. These descriptions are installed and managed by this class, and
2100 /// they're all instances of OperandBundleUser<T>::BundleOpInfo.
2101 ///
2102 /// DU is an additional descriptor installed by User's 'operator new' to keep
2103 /// track of the 'BOI0 ... BOIN' co-allocation. OperandBundleUser does not
2104 /// access or modify DU in any way, it's an implementation detail private to
2105 /// User.
2106 ///
2107 /// The regular Use& vector for the User starts at U0. The operand bundle
2108 /// uses are part of the Use& vector, just like normal uses. In the diagram
2109 /// above, the operand bundle uses start at BOI0_U0. Each instance of
2110 /// BundleOpInfo has information about a contiguous set of uses constituting
2111 /// an operand bundle, and the total set of operand bundle uses themselves
2112 /// form a contiguous set of uses (i.e. there are no gaps between uses
2113 /// corresponding to individual operand bundles).
2114 ///
2115 /// This class does not know the location of the set of operand bundle uses
2116 /// within the use list -- that is decided by the User using this class via
2117 /// the BeginIdx argument in populateBundleOperandInfos.
2118 ///
2119 /// Currently operand bundle users with hung-off operands are not supported.
2120 bundle_op_iterator bundle_op_info_begin() {
2121 if (!hasDescriptor())
2122 return nullptr;
2123
2124 uint8_t *BytesBegin = getDescriptor().begin();
2125 return reinterpret_cast<bundle_op_iterator>(BytesBegin);
2126 }
2127
2128 /// Return the start of the list of BundleOpInfo instances associated
2129 /// with this OperandBundleUser.
2130 const_bundle_op_iterator bundle_op_info_begin() const {
2131 auto *NonConstThis = const_cast<CallBase *>(this);
2132 return NonConstThis->bundle_op_info_begin();
2133 }
2134
2135 /// Return the end of the list of BundleOpInfo instances associated
2136 /// with this OperandBundleUser.
2137 bundle_op_iterator bundle_op_info_end() {
2138 if (!hasDescriptor())
2139 return nullptr;
2140
2141 uint8_t *BytesEnd = getDescriptor().end();
2142 return reinterpret_cast<bundle_op_iterator>(BytesEnd);
2143 }
2144
2145 /// Return the end of the list of BundleOpInfo instances associated
2146 /// with this OperandBundleUser.
2147 const_bundle_op_iterator bundle_op_info_end() const {
2148 auto *NonConstThis = const_cast<CallBase *>(this);
2149 return NonConstThis->bundle_op_info_end();
2150 }
2151
2152 /// Return the range [\p bundle_op_info_begin, \p bundle_op_info_end).
2153 iterator_range<bundle_op_iterator> bundle_op_infos() {
2154 return make_range(bundle_op_info_begin(), bundle_op_info_end());
2155 }
2156
2157 /// Return the range [\p bundle_op_info_begin, \p bundle_op_info_end).
2158 iterator_range<const_bundle_op_iterator> bundle_op_infos() const {
2159 return make_range(bundle_op_info_begin(), bundle_op_info_end());
2160 }
2161
2162 /// Populate the BundleOpInfo instances and the Use& vector from \p
2163 /// Bundles. Return the op_iterator pointing to the Use& one past the last
2164 /// last bundle operand use.
2165 ///
2166 /// Each \p OperandBundleDef instance is tracked by a OperandBundleInfo
2167 /// instance allocated in this User's descriptor.
2168 op_iterator populateBundleOperandInfos(ArrayRef<OperandBundleDef> Bundles,
2169 const unsigned BeginIndex);
2170
2171public:
2172 /// Return the BundleOpInfo for the operand at index OpIdx.
2173 ///
2174 /// It is an error to call this with an OpIdx that does not correspond to an
2175 /// bundle operand.
2176 BundleOpInfo &getBundleOpInfoForOperand(unsigned OpIdx);
2177 const BundleOpInfo &getBundleOpInfoForOperand(unsigned OpIdx) const {
2178 return const_cast<CallBase *>(this)->getBundleOpInfoForOperand(OpIdx);
2179 }
2180
2181protected:
2182 /// Return the total number of values used in \p Bundles.
2183 static unsigned CountBundleInputs(ArrayRef<OperandBundleDef> Bundles) {
2184 unsigned Total = 0;
2185 for (auto &B : Bundles)
2186 Total += B.input_size();
2187 return Total;
2188 }
2189
2190 /// @}
2191 // End of operand bundle API.
2192
2193private:
2194 bool hasFnAttrOnCalledFunction(Attribute::AttrKind Kind) const;
2195 bool hasFnAttrOnCalledFunction(StringRef Kind) const;
2196
2197 template <typename AttrKind> bool hasFnAttrImpl(AttrKind Kind) const {
2198 if (Attrs.hasFnAttribute(Kind))
25
Assuming the condition is false
26
Taking false branch
2199 return true;
2200
2201 // Operand bundles override attributes on the called function, but don't
2202 // override attributes directly present on the call instruction.
2203 if (isFnAttrDisallowedByOpBundle(Kind))
27
Calling 'CallBase::isFnAttrDisallowedByOpBundle'
30
Returning from 'CallBase::isFnAttrDisallowedByOpBundle'
31
Taking false branch
2204 return false;
2205
2206 return hasFnAttrOnCalledFunction(Kind);
32
Returning value, which participates in a condition later
2207 }
2208};
2209
2210template <>
2211struct OperandTraits<CallBase> : public VariadicOperandTraits<CallBase, 1> {};
2212
2213DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CallBase, Value)CallBase::op_iterator CallBase::op_begin() { return OperandTraits
<CallBase>::op_begin(this); } CallBase::const_op_iterator
CallBase::op_begin() const { return OperandTraits<CallBase
>::op_begin(const_cast<CallBase*>(this)); } CallBase
::op_iterator CallBase::op_end() { return OperandTraits<CallBase
>::op_end(this); } CallBase::const_op_iterator CallBase::op_end
() const { return OperandTraits<CallBase>::op_end(const_cast
<CallBase*>(this)); } Value *CallBase::getOperand(unsigned
i_nocapture) const { ((i_nocapture < OperandTraits<CallBase
>::operands(this) && "getOperand() out of range!")
? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<CallBase>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 2213, __PRETTY_FUNCTION__)); return cast_or_null<Value>
( OperandTraits<CallBase>::op_begin(const_cast<CallBase
*>(this))[i_nocapture].get()); } void CallBase::setOperand
(unsigned i_nocapture, Value *Val_nocapture) { ((i_nocapture <
OperandTraits<CallBase>::operands(this) && "setOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<CallBase>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 2213, __PRETTY_FUNCTION__)); OperandTraits<CallBase>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned CallBase
::getNumOperands() const { return OperandTraits<CallBase>
::operands(this); } template <int Idx_nocapture> Use &
CallBase::Op() { return this->OpFrom<Idx_nocapture>(
this); } template <int Idx_nocapture> const Use &CallBase
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
2214
2215//===----------------------------------------------------------------------===//
2216// FuncletPadInst Class
2217//===----------------------------------------------------------------------===//
2218class FuncletPadInst : public Instruction {
2219private:
2220 FuncletPadInst(const FuncletPadInst &CPI);
2221
2222 explicit FuncletPadInst(Instruction::FuncletPadOps Op, Value *ParentPad,
2223 ArrayRef<Value *> Args, unsigned Values,
2224 const Twine &NameStr, Instruction *InsertBefore);
2225 explicit FuncletPadInst(Instruction::FuncletPadOps Op, Value *ParentPad,
2226 ArrayRef<Value *> Args, unsigned Values,
2227 const Twine &NameStr, BasicBlock *InsertAtEnd);
2228
2229 void init(Value *ParentPad, ArrayRef<Value *> Args, const Twine &NameStr);
2230
2231protected:
2232 // Note: Instruction needs to be a friend here to call cloneImpl.
2233 friend class Instruction;
2234 friend class CatchPadInst;
2235 friend class CleanupPadInst;
2236
2237 FuncletPadInst *cloneImpl() const;
2238
2239public:
2240 /// Provide fast operand accessors
2241 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value)public: inline Value *getOperand(unsigned) const; inline void
setOperand(unsigned, Value*); inline op_iterator op_begin();
inline const_op_iterator op_begin() const; inline op_iterator
op_end(); inline const_op_iterator op_end() const; protected
: template <int> inline Use &Op(); template <int
> inline const Use &Op() const; public: inline unsigned
getNumOperands() const
;
2242
2243 /// getNumArgOperands - Return the number of funcletpad arguments.
2244 ///
2245 unsigned getNumArgOperands() const { return getNumOperands() - 1; }
2246
2247 /// Convenience accessors
2248
2249 /// Return the outer EH-pad this funclet is nested within.
2250 ///
2251 /// Note: This returns the associated CatchSwitchInst if this FuncletPadInst
2252 /// is a CatchPadInst.
2253 Value *getParentPad() const { return Op<-1>(); }
2254 void setParentPad(Value *ParentPad) {
2255 assert(ParentPad)((ParentPad) ? static_cast<void> (0) : __assert_fail ("ParentPad"
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 2255, __PRETTY_FUNCTION__))
;
2256 Op<-1>() = ParentPad;
2257 }
2258
2259 /// getArgOperand/setArgOperand - Return/set the i-th funcletpad argument.
2260 ///
2261 Value *getArgOperand(unsigned i) const { return getOperand(i); }
2262 void setArgOperand(unsigned i, Value *v) { setOperand(i, v); }
2263
2264 /// arg_operands - iteration adapter for range-for loops.
2265 op_range arg_operands() { return op_range(op_begin(), op_end() - 1); }
2266
2267 /// arg_operands - iteration adapter for range-for loops.
2268 const_op_range arg_operands() const {
2269 return const_op_range(op_begin(), op_end() - 1);
2270 }
2271
2272 // Methods for support type inquiry through isa, cast, and dyn_cast:
2273 static bool classof(const Instruction *I) { return I->isFuncletPad(); }
2274 static bool classof(const Value *V) {
2275 return isa<Instruction>(V) && classof(cast<Instruction>(V));
2276 }
2277};
2278
2279template <>
2280struct OperandTraits<FuncletPadInst>
2281 : public VariadicOperandTraits<FuncletPadInst, /*MINARITY=*/1> {};
2282
2283DEFINE_TRANSPARENT_OPERAND_ACCESSORS(FuncletPadInst, Value)FuncletPadInst::op_iterator FuncletPadInst::op_begin() { return
OperandTraits<FuncletPadInst>::op_begin(this); } FuncletPadInst
::const_op_iterator FuncletPadInst::op_begin() const { return
OperandTraits<FuncletPadInst>::op_begin(const_cast<
FuncletPadInst*>(this)); } FuncletPadInst::op_iterator FuncletPadInst
::op_end() { return OperandTraits<FuncletPadInst>::op_end
(this); } FuncletPadInst::const_op_iterator FuncletPadInst::op_end
() const { return OperandTraits<FuncletPadInst>::op_end
(const_cast<FuncletPadInst*>(this)); } Value *FuncletPadInst
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
OperandTraits<FuncletPadInst>::operands(this) &&
"getOperand() out of range!") ? static_cast<void> (0) :
__assert_fail ("i_nocapture < OperandTraits<FuncletPadInst>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 2283, __PRETTY_FUNCTION__)); return cast_or_null<Value>
( OperandTraits<FuncletPadInst>::op_begin(const_cast<
FuncletPadInst*>(this))[i_nocapture].get()); } void FuncletPadInst
::setOperand(unsigned i_nocapture, Value *Val_nocapture) { ((
i_nocapture < OperandTraits<FuncletPadInst>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<FuncletPadInst>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/InstrTypes.h"
, 2283, __PRETTY_FUNCTION__)); OperandTraits<FuncletPadInst
>::op_begin(this)[i_nocapture] = Val_nocapture; } unsigned
FuncletPadInst::getNumOperands() const { return OperandTraits
<FuncletPadInst>::operands(this); } template <int Idx_nocapture
> Use &FuncletPadInst::Op() { return this->OpFrom<
Idx_nocapture>(this); } template <int Idx_nocapture>
const Use &FuncletPadInst::Op() const { return this->
OpFrom<Idx_nocapture>(this); }
2284
2285} // end namespace llvm
2286
2287#endif // LLVM_IR_INSTRTYPES_H

/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/PatternMatch.h

1//===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
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 provides a simple and efficient mechanism for performing general
10// tree-based pattern matches on the LLVM IR. The power of these routines is
11// that it allows you to write concise patterns that are expressive and easy to
12// understand. The other major advantage of this is that it allows you to
13// trivially capture/bind elements in the pattern to variables. For example,
14// you can do something like this:
15//
16// Value *Exp = ...
17// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
18// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19// m_And(m_Value(Y), m_ConstantInt(C2))))) {
20// ... Pattern is matched and variables are bound ...
21// }
22//
23// This is primarily useful to things like the instruction combiner, but can
24// also be useful for static analysis tools or code generators.
25//
26//===----------------------------------------------------------------------===//
27
28#ifndef LLVM_IR_PATTERNMATCH_H
29#define LLVM_IR_PATTERNMATCH_H
30
31#include "llvm/ADT/APFloat.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
35#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/InstrTypes.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/IntrinsicInst.h"
40#include "llvm/IR/Intrinsics.h"
41#include "llvm/IR/Operator.h"
42#include "llvm/IR/Value.h"
43#include "llvm/Support/Casting.h"
44#include <cstdint>
45
46namespace llvm {
47namespace PatternMatch {
48
49template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 return const_cast<Pattern &>(P).match(V);
41
Calling 'IntrinsicID_match::match'
45
Returning from 'IntrinsicID_match::match'
46
Returning zero, which participates in a condition later
50
Calling 'IntrinsicID_match::match'
54
Returning from 'IntrinsicID_match::match'
55
Returning zero, which participates in a condition later
51}
52
53template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
54 return const_cast<Pattern &>(P).match(Mask);
55}
56
57template <typename SubPattern_t> struct OneUse_match {
58 SubPattern_t SubPattern;
59
60 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
61
62 template <typename OpTy> bool match(OpTy *V) {
63 return V->hasOneUse() && SubPattern.match(V);
64 }
65};
66
67template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
68 return SubPattern;
69}
70
71template <typename Class> struct class_match {
72 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
73};
74
75/// Match an arbitrary value and ignore it.
76inline class_match<Value> m_Value() { return class_match<Value>(); }
77
78/// Match an arbitrary unary operation and ignore it.
79inline class_match<UnaryOperator> m_UnOp() {
80 return class_match<UnaryOperator>();
81}
82
83/// Match an arbitrary binary operation and ignore it.
84inline class_match<BinaryOperator> m_BinOp() {
85 return class_match<BinaryOperator>();
86}
87
88/// Matches any compare instruction and ignore it.
89inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
90
91/// Match an arbitrary ConstantInt and ignore it.
92inline class_match<ConstantInt> m_ConstantInt() {
93 return class_match<ConstantInt>();
94}
95
96/// Match an arbitrary undef constant.
97inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
98
99/// Match an arbitrary Constant and ignore it.
100inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
101
102/// Match an arbitrary basic block value and ignore it.
103inline class_match<BasicBlock> m_BasicBlock() {
104 return class_match<BasicBlock>();
105}
106
107/// Inverting matcher
108template <typename Ty> struct match_unless {
109 Ty M;
110
111 match_unless(const Ty &Matcher) : M(Matcher) {}
112
113 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
114};
115
116/// Match if the inner matcher does *NOT* match.
117template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
118 return match_unless<Ty>(M);
119}
120
121/// Matching combinators
122template <typename LTy, typename RTy> struct match_combine_or {
123 LTy L;
124 RTy R;
125
126 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
127
128 template <typename ITy> bool match(ITy *V) {
129 if (L.match(V))
130 return true;
131 if (R.match(V))
132 return true;
133 return false;
134 }
135};
136
137template <typename LTy, typename RTy> struct match_combine_and {
138 LTy L;
139 RTy R;
140
141 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
142
143 template <typename ITy> bool match(ITy *V) {
144 if (L.match(V))
145 if (R.match(V))
146 return true;
147 return false;
148 }
149};
150
151/// Combine two pattern matchers matching L || R
152template <typename LTy, typename RTy>
153inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
154 return match_combine_or<LTy, RTy>(L, R);
155}
156
157/// Combine two pattern matchers matching L && R
158template <typename LTy, typename RTy>
159inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
160 return match_combine_and<LTy, RTy>(L, R);
161}
162
163struct apint_match {
164 const APInt *&Res;
165 bool AllowUndef;
166
167 apint_match(const APInt *&Res, bool AllowUndef)
168 : Res(Res), AllowUndef(AllowUndef) {}
169
170 template <typename ITy> bool match(ITy *V) {
171 if (auto *CI = dyn_cast<ConstantInt>(V)) {
172 Res = &CI->getValue();
173 return true;
174 }
175 if (V->getType()->isVectorTy())
176 if (const auto *C = dyn_cast<Constant>(V))
177 if (auto *CI = dyn_cast_or_null<ConstantInt>(
178 C->getSplatValue(AllowUndef))) {
179 Res = &CI->getValue();
180 return true;
181 }
182 return false;
183 }
184};
185// Either constexpr if or renaming ConstantFP::getValueAPF to
186// ConstantFP::getValue is needed to do it via single template
187// function for both apint/apfloat.
188struct apfloat_match {
189 const APFloat *&Res;
190 bool AllowUndef;
191
192 apfloat_match(const APFloat *&Res, bool AllowUndef)
193 : Res(Res), AllowUndef(AllowUndef) {}
194
195 template <typename ITy> bool match(ITy *V) {
196 if (auto *CI = dyn_cast<ConstantFP>(V)) {
197 Res = &CI->getValueAPF();
198 return true;
199 }
200 if (V->getType()->isVectorTy())
201 if (const auto *C = dyn_cast<Constant>(V))
202 if (auto *CI = dyn_cast_or_null<ConstantFP>(
203 C->getSplatValue(AllowUndef))) {
204 Res = &CI->getValueAPF();
205 return true;
206 }
207 return false;
208 }
209};
210
211/// Match a ConstantInt or splatted ConstantVector, binding the
212/// specified pointer to the contained APInt.
213inline apint_match m_APInt(const APInt *&Res) {
214 // Forbid undefs by default to maintain previous behavior.
215 return apint_match(Res, /* AllowUndef */ false);
216}
217
218/// Match APInt while allowing undefs in splat vector constants.
219inline apint_match m_APIntAllowUndef(const APInt *&Res) {
220 return apint_match(Res, /* AllowUndef */ true);
221}
222
223/// Match APInt while forbidding undefs in splat vector constants.
224inline apint_match m_APIntForbidUndef(const APInt *&Res) {
225 return apint_match(Res, /* AllowUndef */ false);
226}
227
228/// Match a ConstantFP or splatted ConstantVector, binding the
229/// specified pointer to the contained APFloat.
230inline apfloat_match m_APFloat(const APFloat *&Res) {
231 // Forbid undefs by default to maintain previous behavior.
232 return apfloat_match(Res, /* AllowUndef */ false);
233}
234
235/// Match APFloat while allowing undefs in splat vector constants.
236inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
237 return apfloat_match(Res, /* AllowUndef */ true);
238}
239
240/// Match APFloat while forbidding undefs in splat vector constants.
241inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
242 return apfloat_match(Res, /* AllowUndef */ false);
243}
244
245template <int64_t Val> struct constantint_match {
246 template <typename ITy> bool match(ITy *V) {
247 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
248 const APInt &CIV = CI->getValue();
249 if (Val >= 0)
250 return CIV == static_cast<uint64_t>(Val);
251 // If Val is negative, and CI is shorter than it, truncate to the right
252 // number of bits. If it is larger, then we have to sign extend. Just
253 // compare their negated values.
254 return -CIV == -Val;
255 }
256 return false;
257 }
258};
259
260/// Match a ConstantInt with a specific value.
261template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
262 return constantint_match<Val>();
263}
264
265/// This helper class is used to match constant scalars, vector splats,
266/// and fixed width vectors that satisfy a specified predicate.
267/// For fixed width vector constants, undefined elements are ignored.
268template <typename Predicate, typename ConstantVal>
269struct cstval_pred_ty : public Predicate {
270 template <typename ITy> bool match(ITy *V) {
271 if (const auto *CV = dyn_cast<ConstantVal>(V))
272 return this->isValue(CV->getValue());
273 if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
274 if (const auto *C = dyn_cast<Constant>(V)) {
275 if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
276 return this->isValue(CV->getValue());
277
278 // Number of elements of a scalable vector unknown at compile time
279 auto *FVTy = dyn_cast<FixedVectorType>(VTy);
280 if (!FVTy)
281 return false;
282
283 // Non-splat vector constant: check each element for a match.
284 unsigned NumElts = FVTy->getNumElements();
285 assert(NumElts != 0 && "Constant vector with no elements?")((NumElts != 0 && "Constant vector with no elements?"
) ? static_cast<void> (0) : __assert_fail ("NumElts != 0 && \"Constant vector with no elements?\""
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/PatternMatch.h"
, 285, __PRETTY_FUNCTION__))
;
286 bool HasNonUndefElements = false;
287 for (unsigned i = 0; i != NumElts; ++i) {
288 Constant *Elt = C->getAggregateElement(i);
289 if (!Elt)
290 return false;
291 if (isa<UndefValue>(Elt))
292 continue;
293 auto *CV = dyn_cast<ConstantVal>(Elt);
294 if (!CV || !this->isValue(CV->getValue()))
295 return false;
296 HasNonUndefElements = true;
297 }
298 return HasNonUndefElements;
299 }
300 }
301 return false;
302 }
303};
304
305/// specialization of cstval_pred_ty for ConstantInt
306template <typename Predicate>
307using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
308
309/// specialization of cstval_pred_ty for ConstantFP
310template <typename Predicate>
311using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
312
313/// This helper class is used to match scalar and vector constants that
314/// satisfy a specified predicate, and bind them to an APInt.
315template <typename Predicate> struct api_pred_ty : public Predicate {
316 const APInt *&Res;
317
318 api_pred_ty(const APInt *&R) : Res(R) {}
319
320 template <typename ITy> bool match(ITy *V) {
321 if (const auto *CI = dyn_cast<ConstantInt>(V))
322 if (this->isValue(CI->getValue())) {
323 Res = &CI->getValue();
324 return true;
325 }
326 if (V->getType()->isVectorTy())
327 if (const auto *C = dyn_cast<Constant>(V))
328 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
329 if (this->isValue(CI->getValue())) {
330 Res = &CI->getValue();
331 return true;
332 }
333
334 return false;
335 }
336};
337
338/// This helper class is used to match scalar and vector constants that
339/// satisfy a specified predicate, and bind them to an APFloat.
340/// Undefs are allowed in splat vector constants.
341template <typename Predicate> struct apf_pred_ty : public Predicate {
342 const APFloat *&Res;
343
344 apf_pred_ty(const APFloat *&R) : Res(R) {}
345
346 template <typename ITy> bool match(ITy *V) {
347 if (const auto *CI = dyn_cast<ConstantFP>(V))
348 if (this->isValue(CI->getValue())) {
349 Res = &CI->getValue();
350 return true;
351 }
352 if (V->getType()->isVectorTy())
353 if (const auto *C = dyn_cast<Constant>(V))
354 if (auto *CI = dyn_cast_or_null<ConstantFP>(
355 C->getSplatValue(/* AllowUndef */ true)))
356 if (this->isValue(CI->getValue())) {
357 Res = &CI->getValue();
358 return true;
359 }
360
361 return false;
362 }
363};
364
365///////////////////////////////////////////////////////////////////////////////
366//
367// Encapsulate constant value queries for use in templated predicate matchers.
368// This allows checking if constants match using compound predicates and works
369// with vector constants, possibly with relaxed constraints. For example, ignore
370// undef values.
371//
372///////////////////////////////////////////////////////////////////////////////
373
374struct is_any_apint {
375 bool isValue(const APInt &C) { return true; }
376};
377/// Match an integer or vector with any integral constant.
378/// For vectors, this includes constants with undefined elements.
379inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
380 return cst_pred_ty<is_any_apint>();
381}
382
383struct is_all_ones {
384 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
385};
386/// Match an integer or vector with all bits set.
387/// For vectors, this includes constants with undefined elements.
388inline cst_pred_ty<is_all_ones> m_AllOnes() {
389 return cst_pred_ty<is_all_ones>();
390}
391
392struct is_maxsignedvalue {
393 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
394};
395/// Match an integer or vector with values having all bits except for the high
396/// bit set (0x7f...).
397/// For vectors, this includes constants with undefined elements.
398inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
399 return cst_pred_ty<is_maxsignedvalue>();
400}
401inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
402 return V;
403}
404
405struct is_negative {
406 bool isValue(const APInt &C) { return C.isNegative(); }
407};
408/// Match an integer or vector of negative values.
409/// For vectors, this includes constants with undefined elements.
410inline cst_pred_ty<is_negative> m_Negative() {
411 return cst_pred_ty<is_negative>();
412}
413inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
414 return V;
415}
416
417struct is_nonnegative {
418 bool isValue(const APInt &C) { return C.isNonNegative(); }
419};
420/// Match an integer or vector of non-negative values.
421/// For vectors, this includes constants with undefined elements.
422inline cst_pred_ty<is_nonnegative> m_NonNegative() {
423 return cst_pred_ty<is_nonnegative>();
424}
425inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
426 return V;
427}
428
429struct is_strictlypositive {
430 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
431};
432/// Match an integer or vector of strictly positive values.
433/// For vectors, this includes constants with undefined elements.
434inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
435 return cst_pred_ty<is_strictlypositive>();
436}
437inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
438 return V;
439}
440
441struct is_nonpositive {
442 bool isValue(const APInt &C) { return C.isNonPositive(); }
443};
444/// Match an integer or vector of non-positive values.
445/// For vectors, this includes constants with undefined elements.
446inline cst_pred_ty<is_nonpositive> m_NonPositive() {
447 return cst_pred_ty<is_nonpositive>();
448}
449inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
450
451struct is_one {
452 bool isValue(const APInt &C) { return C.isOneValue(); }
453};
454/// Match an integer 1 or a vector with all elements equal to 1.
455/// For vectors, this includes constants with undefined elements.
456inline cst_pred_ty<is_one> m_One() {
457 return cst_pred_ty<is_one>();
458}
459
460struct is_zero_int {
461 bool isValue(const APInt &C) { return C.isNullValue(); }
462};
463/// Match an integer 0 or a vector with all elements equal to 0.
464/// For vectors, this includes constants with undefined elements.
465inline cst_pred_ty<is_zero_int> m_ZeroInt() {
466 return cst_pred_ty<is_zero_int>();
467}
468
469struct is_zero {
470 template <typename ITy> bool match(ITy *V) {
471 auto *C = dyn_cast<Constant>(V);
472 // FIXME: this should be able to do something for scalable vectors
473 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
474 }
475};
476/// Match any null constant or a vector with all elements equal to 0.
477/// For vectors, this includes constants with undefined elements.
478inline is_zero m_Zero() {
479 return is_zero();
480}
481
482struct is_power2 {
483 bool isValue(const APInt &C) { return C.isPowerOf2(); }
484};
485/// Match an integer or vector power-of-2.
486/// For vectors, this includes constants with undefined elements.
487inline cst_pred_ty<is_power2> m_Power2() {
488 return cst_pred_ty<is_power2>();
489}
490inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
491 return V;
492}
493
494struct is_negated_power2 {
495 bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
496};
497/// Match a integer or vector negated power-of-2.
498/// For vectors, this includes constants with undefined elements.
499inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
500 return cst_pred_ty<is_negated_power2>();
501}
502inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
503 return V;
504}
505
506struct is_power2_or_zero {
507 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
508};
509/// Match an integer or vector of 0 or power-of-2 values.
510/// For vectors, this includes constants with undefined elements.
511inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
512 return cst_pred_ty<is_power2_or_zero>();
513}
514inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
515 return V;
516}
517
518struct is_sign_mask {
519 bool isValue(const APInt &C) { return C.isSignMask(); }
520};
521/// Match an integer or vector with only the sign bit(s) set.
522/// For vectors, this includes constants with undefined elements.
523inline cst_pred_ty<is_sign_mask> m_SignMask() {
524 return cst_pred_ty<is_sign_mask>();
525}
526
527struct is_lowbit_mask {
528 bool isValue(const APInt &C) { return C.isMask(); }
529};
530/// Match an integer or vector with only the low bit(s) set.
531/// For vectors, this includes constants with undefined elements.
532inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
533 return cst_pred_ty<is_lowbit_mask>();
534}
535
536struct icmp_pred_with_threshold {
537 ICmpInst::Predicate Pred;
538 const APInt *Thr;
539 bool isValue(const APInt &C) {
540 switch (Pred) {
541 case ICmpInst::Predicate::ICMP_EQ:
542 return C.eq(*Thr);
543 case ICmpInst::Predicate::ICMP_NE:
544 return C.ne(*Thr);
545 case ICmpInst::Predicate::ICMP_UGT:
546 return C.ugt(*Thr);
547 case ICmpInst::Predicate::ICMP_UGE:
548 return C.uge(*Thr);
549 case ICmpInst::Predicate::ICMP_ULT:
550 return C.ult(*Thr);
551 case ICmpInst::Predicate::ICMP_ULE:
552 return C.ule(*Thr);
553 case ICmpInst::Predicate::ICMP_SGT:
554 return C.sgt(*Thr);
555 case ICmpInst::Predicate::ICMP_SGE:
556 return C.sge(*Thr);
557 case ICmpInst::Predicate::ICMP_SLT:
558 return C.slt(*Thr);
559 case ICmpInst::Predicate::ICMP_SLE:
560 return C.sle(*Thr);
561 default:
562 llvm_unreachable("Unhandled ICmp predicate")::llvm::llvm_unreachable_internal("Unhandled ICmp predicate",
"/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/include/llvm/IR/PatternMatch.h"
, 562)
;
563 }
564 }
565};
566/// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
567/// to Threshold. For vectors, this includes constants with undefined elements.
568inline cst_pred_ty<icmp_pred_with_threshold>
569m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
570 cst_pred_ty<icmp_pred_with_threshold> P;
571 P.Pred = Predicate;
572 P.Thr = &Threshold;
573 return P;
574}
575
576struct is_nan {
577 bool isValue(const APFloat &C) { return C.isNaN(); }
578};
579/// Match an arbitrary NaN constant. This includes quiet and signalling nans.
580/// For vectors, this includes constants with undefined elements.
581inline cstfp_pred_ty<is_nan> m_NaN() {
582 return cstfp_pred_ty<is_nan>();
583}
584
585struct is_nonnan {
586 bool isValue(const APFloat &C) { return !C.isNaN(); }
587};
588/// Match a non-NaN FP constant.
589/// For vectors, this includes constants with undefined elements.
590inline cstfp_pred_ty<is_nonnan> m_NonNaN() {
591 return cstfp_pred_ty<is_nonnan>();
592}
593
594struct is_inf {
595 bool isValue(const APFloat &C) { return C.isInfinity(); }
596};
597/// Match a positive or negative infinity FP constant.
598/// For vectors, this includes constants with undefined elements.
599inline cstfp_pred_ty<is_inf> m_Inf() {
600 return cstfp_pred_ty<is_inf>();
601}
602
603struct is_noninf {
604 bool isValue(const APFloat &C) { return !C.isInfinity(); }
605};
606/// Match a non-infinity FP constant, i.e. finite or NaN.
607/// For vectors, this includes constants with undefined elements.
608inline cstfp_pred_ty<is_noninf> m_NonInf() {
609 return cstfp_pred_ty<is_noninf>();
610}
611
612struct is_finite {
613 bool isValue(const APFloat &C) { return C.isFinite(); }
614};
615/// Match a finite FP constant, i.e. not infinity or NaN.
616/// For vectors, this includes constants with undefined elements.
617inline cstfp_pred_ty<is_finite> m_Finite() {
618 return cstfp_pred_ty<is_finite>();
619}
620inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; }
621
622struct is_finitenonzero {
623 bool isValue(const APFloat &C) { return C.isFiniteNonZero(); }
624};
625/// Match a finite non-zero FP constant.
626/// For vectors, this includes constants with undefined elements.
627inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() {
628 return cstfp_pred_ty<is_finitenonzero>();
629}
630inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) {
631 return V;
632}
633
634struct is_any_zero_fp {
635 bool isValue(const APFloat &C) { return C.isZero(); }
636};
637/// Match a floating-point negative zero or positive zero.
638/// For vectors, this includes constants with undefined elements.
639inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
640 return cstfp_pred_ty<is_any_zero_fp>();
641}
642
643struct is_pos_zero_fp {
644 bool isValue(const APFloat &C) { return C.isPosZero(); }
645};
646/// Match a floating-point positive zero.
647/// For vectors, this includes constants with undefined elements.
648inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
649 return cstfp_pred_ty<is_pos_zero_fp>();
650}
651
652struct is_neg_zero_fp {
653 bool isValue(const APFloat &C) { return C.isNegZero(); }
654};
655/// Match a floating-point negative zero.
656/// For vectors, this includes constants with undefined elements.
657inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
658 return cstfp_pred_ty<is_neg_zero_fp>();
659}
660
661struct is_non_zero_fp {
662 bool isValue(const APFloat &C) { return C.isNonZero(); }
663};
664/// Match a floating-point non-zero.
665/// For vectors, this includes constants with undefined elements.
666inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
667 return cstfp_pred_ty<is_non_zero_fp>();
668}
669
670///////////////////////////////////////////////////////////////////////////////
671
672template <typename Class> struct bind_ty {
673 Class *&VR;
674
675 bind_ty(Class *&V) : VR(V) {}
676
677 template <typename ITy> bool match(ITy *V) {
678 if (auto *CV = dyn_cast<Class>(V)) {
679 VR = CV;
680 return true;
681 }
682 return false;
683 }
684};
685
686/// Match a value, capturing it if we match.
687inline bind_ty<Value> m_Value(Value *&V) { return V; }
688inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
689
690/// Match an instruction, capturing it if we match.
691inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
692/// Match a unary operator, capturing it if we match.
693inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
694/// Match a binary operator, capturing it if we match.
695inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
696/// Match a with overflow intrinsic, capturing it if we match.
697inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
698
699/// Match a ConstantInt, capturing the value if we match.
700inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
701
702/// Match a Constant, capturing the value if we match.
703inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
704
705/// Match a ConstantFP, capturing the value if we match.
706inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
707
708/// Match a basic block value, capturing it if we match.
709inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
710inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
711 return V;
712}
713
714/// Match a specified Value*.
715struct specificval_ty {
716 const Value *Val;
717
718 specificval_ty(const Value *V) : Val(V) {}
719
720 template <typename ITy> bool match(ITy *V) { return V == Val; }
721};
722
723/// Match if we have a specific specified value.
724inline specificval_ty m_Specific(const Value *V) { return V; }
725
726/// Stores a reference to the Value *, not the Value * itself,
727/// thus can be used in commutative matchers.
728template <typename Class> struct deferredval_ty {
729 Class *const &Val;
730
731 deferredval_ty(Class *const &V) : Val(V) {}
732
733 template <typename ITy> bool match(ITy *const V) { return V == Val; }
734};
735
736/// A commutative-friendly version of m_Specific().
737inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
738inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
739 return V;
740}
741
742/// Match a specified floating point value or vector of all elements of
743/// that value.
744struct specific_fpval {
745 double Val;
746
747 specific_fpval(double V) : Val(V) {}
748
749 template <typename ITy> bool match(ITy *V) {
750 if (const auto *CFP = dyn_cast<ConstantFP>(V))
751 return CFP->isExactlyValue(Val);
752 if (V->getType()->isVectorTy())
753 if (const auto *C = dyn_cast<Constant>(V))
754 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
755 return CFP->isExactlyValue(Val);
756 return false;
757 }
758};
759
760/// Match a specific floating point value or vector with all elements
761/// equal to the value.
762inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
763
764/// Match a float 1.0 or vector with all elements equal to 1.0.
765inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
766
767struct bind_const_intval_ty {
768 uint64_t &VR;
769
770 bind_const_intval_ty(uint64_t &V) : VR(V) {}
771
772 template <typename ITy> bool match(ITy *V) {
773 if (const auto *CV = dyn_cast<ConstantInt>(V))
774 if (CV->getValue().ule(UINT64_MAX(18446744073709551615UL))) {
775 VR = CV->getZExtValue();
776 return true;
777 }
778 return false;
779 }
780};
781
782/// Match a specified integer value or vector of all elements of that
783/// value.
784template <bool AllowUndefs>
785struct specific_intval {
786 APInt Val;
787
788 specific_intval(APInt V) : Val(std::move(V)) {}
789
790 template <typename ITy> bool match(ITy *V) {
791 const auto *CI = dyn_cast<ConstantInt>(V);
792 if (!CI && V->getType()->isVectorTy())
793 if (const auto *C = dyn_cast<Constant>(V))
794 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
795
796 return CI && APInt::isSameValue(CI->getValue(), Val);
797 }
798};
799
800/// Match a specific integer value or vector with all elements equal to
801/// the value.
802inline specific_intval<false> m_SpecificInt(APInt V) {
803 return specific_intval<false>(std::move(V));
804}
805
806inline specific_intval<false> m_SpecificInt(uint64_t V) {
807 return m_SpecificInt(APInt(64, V));
808}
809
810inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) {
811 return