Bug Summary

File:llvm/lib/Transforms/Scalar/LICM.cpp
Warning:line 1252, 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 -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/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-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -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 -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Scalar/LICM.cpp

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

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

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