Bug Summary

File:llvm/lib/Transforms/Scalar/LICM.cpp
Warning:line 1220, 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 -clear-ast-before-backend -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/lib/Transforms/Scalar -I include -I /build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U 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 -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/= -O3 -Wno-unused-command-line-argument -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~++20220116100644+5f782d25a742/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -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-2022-01-16-232930-107970-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/lib/Transforms/Scalar/LICM.cpp

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

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

/build/llvm-toolchain-snapshot-14~++20220116100644+5f782d25a742/llvm/include/llvm/IR/PatternMatch.h

1//===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file provides a simple and efficient mechanism for performing general
10// tree-based pattern matches on the LLVM IR. The power of these routines is
11// that it allows you to write concise patterns that are expressive and easy to
12// understand. The other major advantage of this is that it allows you to
13// trivially capture/bind elements in the pattern to variables. For example,
14// you can do something like this:
15//
16// Value *Exp = ...
17// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
18// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19// m_And(m_Value(Y), m_ConstantInt(C2))))) {
20// ... Pattern is matched and variables are bound ...
21// }
22//
23// This is primarily useful to things like the instruction combiner, but can
24// also be useful for static analysis tools or code generators.
25//
26//===----------------------------------------------------------------------===//
27
28#ifndef LLVM_IR_PATTERNMATCH_H
29#define LLVM_IR_PATTERNMATCH_H
30
31#include "llvm/ADT/APFloat.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
35#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/InstrTypes.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/IntrinsicInst.h"
40#include "llvm/IR/Intrinsics.h"
41#include "llvm/IR/Operator.h"
42#include "llvm/IR/Value.h"
43#include "llvm/Support/Casting.h"
44#include <cstdint>
45
46namespace llvm {
47namespace PatternMatch {
48
49template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 return const_cast<Pattern &>(P).match(V);
41
Calling 'IntrinsicID_match::match'
45
Returning from 'IntrinsicID_match::match'
46
Returning zero, which participates in a condition later
50
Calling 'IntrinsicID_match::match'
54
Returning from 'IntrinsicID_match::match'
55
Returning zero, which participates in a condition later
51}
52
53template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
54 return const_cast<Pattern &>(P).match(Mask);
55}
56
57template <typename SubPattern_t> struct OneUse_match {
58 SubPattern_t SubPattern;
59
60 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
61
62 template <typename OpTy> bool match(OpTy *V) {
63 return V->hasOneUse() && SubPattern.match(V);
64 }
65};
66
67template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
68 return SubPattern;
69}
70
71template <typename Class> struct class_match {
72 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
73};
74
75/// Match an arbitrary value and ignore it.
76inline class_match<Value> m_Value() { return class_match<Value>(); }
77
78/// Match an arbitrary unary operation and ignore it.
79inline class_match<UnaryOperator> m_UnOp() {
80 return class_match<UnaryOperator>();
81}
82
83/// Match an arbitrary binary operation and ignore it.
84inline class_match<BinaryOperator> m_BinOp() {
85 return class_match<BinaryOperator>();
86}
87
88/// Matches any compare instruction and ignore it.
89inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
90
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 <bool> (NumElts != 0 && "Constant vector with no elements?"
) ? void (0) : __assert_fail ("NumElts != 0 && \"Constant vector with no elements?\""
, "llvm/include/llvm/IR/PatternMatch.h", 342, __extension__ __PRETTY_FUNCTION__
))
;
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.isAllOnes(); }
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.isOne(); }
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.isZero(); }
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.isNegatedPowerOf2(); }
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