Bug Summary

File:llvm/lib/Analysis/VectorUtils.cpp
Warning:line 1065, column 11
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name VectorUtils.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 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp

1//===----------- VectorUtils.cpp - Vectorizer utility functions -----------===//
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 vectorizer utilities.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/VectorUtils.h"
14#include "llvm/ADT/EquivalenceClasses.h"
15#include "llvm/Analysis/DemandedBits.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/LoopIterator.h"
18#include "llvm/Analysis/ScalarEvolution.h"
19#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20#include "llvm/Analysis/TargetTransformInfo.h"
21#include "llvm/Analysis/ValueTracking.h"
22#include "llvm/IR/Constants.h"
23#include "llvm/IR/GetElementPtrTypeIterator.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/PatternMatch.h"
26#include "llvm/IR/Value.h"
27#include "llvm/Support/CommandLine.h"
28
29#define DEBUG_TYPE"vectorutils" "vectorutils"
30
31using namespace llvm;
32using namespace llvm::PatternMatch;
33
34/// Maximum factor for an interleaved memory access.
35static cl::opt<unsigned> MaxInterleaveGroupFactor(
36 "max-interleave-group-factor", cl::Hidden,
37 cl::desc("Maximum factor for an interleaved access group (default = 8)"),
38 cl::init(8));
39
40/// Return true if all of the intrinsic's arguments and return type are scalars
41/// for the scalar form of the intrinsic, and vectors for the vector form of the
42/// intrinsic (except operands that are marked as always being scalar by
43/// hasVectorInstrinsicScalarOpd).
44bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {
45 switch (ID) {
46 case Intrinsic::bswap: // Begin integer bit-manipulation.
47 case Intrinsic::bitreverse:
48 case Intrinsic::ctpop:
49 case Intrinsic::ctlz:
50 case Intrinsic::cttz:
51 case Intrinsic::fshl:
52 case Intrinsic::fshr:
53 case Intrinsic::sadd_sat:
54 case Intrinsic::ssub_sat:
55 case Intrinsic::uadd_sat:
56 case Intrinsic::usub_sat:
57 case Intrinsic::smul_fix:
58 case Intrinsic::smul_fix_sat:
59 case Intrinsic::umul_fix:
60 case Intrinsic::umul_fix_sat:
61 case Intrinsic::sqrt: // Begin floating-point.
62 case Intrinsic::sin:
63 case Intrinsic::cos:
64 case Intrinsic::exp:
65 case Intrinsic::exp2:
66 case Intrinsic::log:
67 case Intrinsic::log10:
68 case Intrinsic::log2:
69 case Intrinsic::fabs:
70 case Intrinsic::minnum:
71 case Intrinsic::maxnum:
72 case Intrinsic::minimum:
73 case Intrinsic::maximum:
74 case Intrinsic::copysign:
75 case Intrinsic::floor:
76 case Intrinsic::ceil:
77 case Intrinsic::trunc:
78 case Intrinsic::rint:
79 case Intrinsic::nearbyint:
80 case Intrinsic::round:
81 case Intrinsic::pow:
82 case Intrinsic::fma:
83 case Intrinsic::fmuladd:
84 case Intrinsic::powi:
85 case Intrinsic::canonicalize:
86 return true;
87 default:
88 return false;
89 }
90}
91
92/// Identifies if the vector form of the intrinsic has a scalar operand.
93bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,
94 unsigned ScalarOpdIdx) {
95 switch (ID) {
96 case Intrinsic::ctlz:
97 case Intrinsic::cttz:
98 case Intrinsic::powi:
99 return (ScalarOpdIdx == 1);
100 case Intrinsic::smul_fix:
101 case Intrinsic::smul_fix_sat:
102 case Intrinsic::umul_fix:
103 case Intrinsic::umul_fix_sat:
104 return (ScalarOpdIdx == 2);
105 default:
106 return false;
107 }
108}
109
110/// Returns intrinsic ID for call.
111/// For the input call instruction it finds mapping intrinsic and returns
112/// its ID, in case it does not found it return not_intrinsic.
113Intrinsic::ID llvm::getVectorIntrinsicIDForCall(const CallInst *CI,
114 const TargetLibraryInfo *TLI) {
115 Intrinsic::ID ID = getIntrinsicForCallSite(CI, TLI);
116 if (ID == Intrinsic::not_intrinsic)
117 return Intrinsic::not_intrinsic;
118
119 if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
120 ID == Intrinsic::lifetime_end || ID == Intrinsic::assume ||
121 ID == Intrinsic::sideeffect)
122 return ID;
123 return Intrinsic::not_intrinsic;
124}
125
126/// Find the operand of the GEP that should be checked for consecutive
127/// stores. This ignores trailing indices that have no effect on the final
128/// pointer.
129unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) {
130 const DataLayout &DL = Gep->getModule()->getDataLayout();
131 unsigned LastOperand = Gep->getNumOperands() - 1;
132 unsigned GEPAllocSize = DL.getTypeAllocSize(Gep->getResultElementType());
133
134 // Walk backwards and try to peel off zeros.
135 while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
136 // Find the type we're currently indexing into.
137 gep_type_iterator GEPTI = gep_type_begin(Gep);
138 std::advance(GEPTI, LastOperand - 2);
139
140 // If it's a type with the same allocation size as the result of the GEP we
141 // can peel off the zero index.
142 if (DL.getTypeAllocSize(GEPTI.getIndexedType()) != GEPAllocSize)
143 break;
144 --LastOperand;
145 }
146
147 return LastOperand;
148}
149
150/// If the argument is a GEP, then returns the operand identified by
151/// getGEPInductionOperand. However, if there is some other non-loop-invariant
152/// operand, it returns that instead.
153Value *llvm::stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
154 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
155 if (!GEP)
156 return Ptr;
157
158 unsigned InductionOperand = getGEPInductionOperand(GEP);
159
160 // Check that all of the gep indices are uniform except for our induction
161 // operand.
162 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
163 if (i != InductionOperand &&
164 !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
165 return Ptr;
166 return GEP->getOperand(InductionOperand);
167}
168
169/// If a value has only one user that is a CastInst, return it.
170Value *llvm::getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
171 Value *UniqueCast = nullptr;
172 for (User *U : Ptr->users()) {
173 CastInst *CI = dyn_cast<CastInst>(U);
174 if (CI && CI->getType() == Ty) {
175 if (!UniqueCast)
176 UniqueCast = CI;
177 else
178 return nullptr;
179 }
180 }
181 return UniqueCast;
182}
183
184/// Get the stride of a pointer access in a loop. Looks for symbolic
185/// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
186Value *llvm::getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
187 auto *PtrTy = dyn_cast<PointerType>(Ptr->getType());
188 if (!PtrTy || PtrTy->isAggregateType())
189 return nullptr;
190
191 // Try to remove a gep instruction to make the pointer (actually index at this
192 // point) easier analyzable. If OrigPtr is equal to Ptr we are analyzing the
193 // pointer, otherwise, we are analyzing the index.
194 Value *OrigPtr = Ptr;
195
196 // The size of the pointer access.
197 int64_t PtrAccessSize = 1;
198
199 Ptr = stripGetElementPtr(Ptr, SE, Lp);
200 const SCEV *V = SE->getSCEV(Ptr);
201
202 if (Ptr != OrigPtr)
203 // Strip off casts.
204 while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
205 V = C->getOperand();
206
207 const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
208 if (!S)
209 return nullptr;
210
211 V = S->getStepRecurrence(*SE);
212 if (!V)
213 return nullptr;
214
215 // Strip off the size of access multiplication if we are still analyzing the
216 // pointer.
217 if (OrigPtr == Ptr) {
218 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
219 if (M->getOperand(0)->getSCEVType() != scConstant)
220 return nullptr;
221
222 const APInt &APStepVal = cast<SCEVConstant>(M->getOperand(0))->getAPInt();
223
224 // Huge step value - give up.
225 if (APStepVal.getBitWidth() > 64)
226 return nullptr;
227
228 int64_t StepVal = APStepVal.getSExtValue();
229 if (PtrAccessSize != StepVal)
230 return nullptr;
231 V = M->getOperand(1);
232 }
233 }
234
235 // Strip off casts.
236 Type *StripedOffRecurrenceCast = nullptr;
237 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
238 StripedOffRecurrenceCast = C->getType();
239 V = C->getOperand();
240 }
241
242 // Look for the loop invariant symbolic value.
243 const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
244 if (!U)
245 return nullptr;
246
247 Value *Stride = U->getValue();
248 if (!Lp->isLoopInvariant(Stride))
249 return nullptr;
250
251 // If we have stripped off the recurrence cast we have to make sure that we
252 // return the value that is used in this loop so that we can replace it later.
253 if (StripedOffRecurrenceCast)
254 Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
255
256 return Stride;
257}
258
259/// Given a vector and an element number, see if the scalar value is
260/// already around as a register, for example if it were inserted then extracted
261/// from the vector.
262Value *llvm::findScalarElement(Value *V, unsigned EltNo) {
263 assert(V->getType()->isVectorTy() && "Not looking at a vector?")((V->getType()->isVectorTy() && "Not looking at a vector?"
) ? static_cast<void> (0) : __assert_fail ("V->getType()->isVectorTy() && \"Not looking at a vector?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 263, __PRETTY_FUNCTION__))
;
264 VectorType *VTy = cast<VectorType>(V->getType());
265 unsigned Width = VTy->getNumElements();
266 if (EltNo >= Width) // Out of range access.
267 return UndefValue::get(VTy->getElementType());
268
269 if (Constant *C = dyn_cast<Constant>(V))
270 return C->getAggregateElement(EltNo);
271
272 if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
273 // If this is an insert to a variable element, we don't know what it is.
274 if (!isa<ConstantInt>(III->getOperand(2)))
275 return nullptr;
276 unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
277
278 // If this is an insert to the element we are looking for, return the
279 // inserted value.
280 if (EltNo == IIElt)
281 return III->getOperand(1);
282
283 // Otherwise, the insertelement doesn't modify the value, recurse on its
284 // vector input.
285 return findScalarElement(III->getOperand(0), EltNo);
286 }
287
288 if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
289 unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements();
290 int InEl = SVI->getMaskValue(EltNo);
291 if (InEl < 0)
292 return UndefValue::get(VTy->getElementType());
293 if (InEl < (int)LHSWidth)
294 return findScalarElement(SVI->getOperand(0), InEl);
295 return findScalarElement(SVI->getOperand(1), InEl - LHSWidth);
296 }
297
298 // Extract a value from a vector add operation with a constant zero.
299 // TODO: Use getBinOpIdentity() to generalize this.
300 Value *Val; Constant *C;
301 if (match(V, m_Add(m_Value(Val), m_Constant(C))))
302 if (Constant *Elt = C->getAggregateElement(EltNo))
303 if (Elt->isNullValue())
304 return findScalarElement(Val, EltNo);
305
306 // Otherwise, we don't know.
307 return nullptr;
308}
309
310int llvm::getSplatIndex(ArrayRef<int> Mask) {
311 int SplatIndex = -1;
312 for (int M : Mask) {
313 // Ignore invalid (undefined) mask elements.
314 if (M < 0)
315 continue;
316
317 // There can be only 1 non-negative mask element value if this is a splat.
318 if (SplatIndex != -1 && SplatIndex != M)
319 return -1;
320
321 // Initialize the splat index to the 1st non-negative mask element.
322 SplatIndex = M;
323 }
324 assert((SplatIndex == -1 || SplatIndex >= 0) && "Negative index?")(((SplatIndex == -1 || SplatIndex >= 0) && "Negative index?"
) ? static_cast<void> (0) : __assert_fail ("(SplatIndex == -1 || SplatIndex >= 0) && \"Negative index?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 324, __PRETTY_FUNCTION__))
;
325 return SplatIndex;
326}
327
328/// Get splat value if the input is a splat vector or return nullptr.
329/// This function is not fully general. It checks only 2 cases:
330/// the input value is (1) a splat constant vector or (2) a sequence
331/// of instructions that broadcasts a scalar at element 0.
332const llvm::Value *llvm::getSplatValue(const Value *V) {
333 if (isa<VectorType>(V->getType()))
334 if (auto *C = dyn_cast<Constant>(V))
335 return C->getSplatValue();
336
337 // shuf (inselt ?, Splat, 0), ?, <0, undef, 0, ...>
338 Value *Splat;
339 if (match(V, m_ShuffleVector(m_InsertElement(m_Value(), m_Value(Splat),
340 m_ZeroInt()),
341 m_Value(), m_ZeroInt())))
342 return Splat;
343
344 return nullptr;
345}
346
347// This setting is based on its counterpart in value tracking, but it could be
348// adjusted if needed.
349const unsigned MaxDepth = 6;
350
351bool llvm::isSplatValue(const Value *V, int Index, unsigned Depth) {
352 assert(Depth <= MaxDepth && "Limit Search Depth")((Depth <= MaxDepth && "Limit Search Depth") ? static_cast
<void> (0) : __assert_fail ("Depth <= MaxDepth && \"Limit Search Depth\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 352, __PRETTY_FUNCTION__))
;
353
354 if (isa<VectorType>(V->getType())) {
355 if (isa<UndefValue>(V))
356 return true;
357 // FIXME: We can allow undefs, but if Index was specified, we may want to
358 // check that the constant is defined at that index.
359 if (auto *C = dyn_cast<Constant>(V))
360 return C->getSplatValue() != nullptr;
361 }
362
363 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(V)) {
364 // FIXME: We can safely allow undefs here. If Index was specified, we will
365 // check that the mask elt is defined at the required index.
366 if (!Shuf->getMask()->getSplatValue())
367 return false;
368
369 // Match any index.
370 if (Index == -1)
371 return true;
372
373 // Match a specific element. The mask should be defined at and match the
374 // specified index.
375 return Shuf->getMaskValue(Index) == Index;
376 }
377
378 // The remaining tests are all recursive, so bail out if we hit the limit.
379 if (Depth++ == MaxDepth)
380 return false;
381
382 // If both operands of a binop are splats, the result is a splat.
383 Value *X, *Y, *Z;
384 if (match(V, m_BinOp(m_Value(X), m_Value(Y))))
385 return isSplatValue(X, Index, Depth) && isSplatValue(Y, Index, Depth);
386
387 // If all operands of a select are splats, the result is a splat.
388 if (match(V, m_Select(m_Value(X), m_Value(Y), m_Value(Z))))
389 return isSplatValue(X, Index, Depth) && isSplatValue(Y, Index, Depth) &&
390 isSplatValue(Z, Index, Depth);
391
392 // TODO: Add support for unary ops (fneg), casts, intrinsics (overflow ops).
393
394 return false;
395}
396
397MapVector<Instruction *, uint64_t>
398llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB,
399 const TargetTransformInfo *TTI) {
400
401 // DemandedBits will give us every value's live-out bits. But we want
402 // to ensure no extra casts would need to be inserted, so every DAG
403 // of connected values must have the same minimum bitwidth.
404 EquivalenceClasses<Value *> ECs;
405 SmallVector<Value *, 16> Worklist;
406 SmallPtrSet<Value *, 4> Roots;
407 SmallPtrSet<Value *, 16> Visited;
408 DenseMap<Value *, uint64_t> DBits;
409 SmallPtrSet<Instruction *, 4> InstructionSet;
410 MapVector<Instruction *, uint64_t> MinBWs;
411
412 // Determine the roots. We work bottom-up, from truncs or icmps.
413 bool SeenExtFromIllegalType = false;
414 for (auto *BB : Blocks)
415 for (auto &I : *BB) {
416 InstructionSet.insert(&I);
417
418 if (TTI && (isa<ZExtInst>(&I) || isa<SExtInst>(&I)) &&
419 !TTI->isTypeLegal(I.getOperand(0)->getType()))
420 SeenExtFromIllegalType = true;
421
422 // Only deal with non-vector integers up to 64-bits wide.
423 if ((isa<TruncInst>(&I) || isa<ICmpInst>(&I)) &&
424 !I.getType()->isVectorTy() &&
425 I.getOperand(0)->getType()->getScalarSizeInBits() <= 64) {
426 // Don't make work for ourselves. If we know the loaded type is legal,
427 // don't add it to the worklist.
428 if (TTI && isa<TruncInst>(&I) && TTI->isTypeLegal(I.getType()))
429 continue;
430
431 Worklist.push_back(&I);
432 Roots.insert(&I);
433 }
434 }
435 // Early exit.
436 if (Worklist.empty() || (TTI && !SeenExtFromIllegalType))
437 return MinBWs;
438
439 // Now proceed breadth-first, unioning values together.
440 while (!Worklist.empty()) {
441 Value *Val = Worklist.pop_back_val();
442 Value *Leader = ECs.getOrInsertLeaderValue(Val);
443
444 if (Visited.count(Val))
445 continue;
446 Visited.insert(Val);
447
448 // Non-instructions terminate a chain successfully.
449 if (!isa<Instruction>(Val))
450 continue;
451 Instruction *I = cast<Instruction>(Val);
452
453 // If we encounter a type that is larger than 64 bits, we can't represent
454 // it so bail out.
455 if (DB.getDemandedBits(I).getBitWidth() > 64)
456 return MapVector<Instruction *, uint64_t>();
457
458 uint64_t V = DB.getDemandedBits(I).getZExtValue();
459 DBits[Leader] |= V;
460 DBits[I] = V;
461
462 // Casts, loads and instructions outside of our range terminate a chain
463 // successfully.
464 if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) ||
465 !InstructionSet.count(I))
466 continue;
467
468 // Unsafe casts terminate a chain unsuccessfully. We can't do anything
469 // useful with bitcasts, ptrtoints or inttoptrs and it'd be unsafe to
470 // transform anything that relies on them.
471 if (isa<BitCastInst>(I) || isa<PtrToIntInst>(I) || isa<IntToPtrInst>(I) ||
472 !I->getType()->isIntegerTy()) {
473 DBits[Leader] |= ~0ULL;
474 continue;
475 }
476
477 // We don't modify the types of PHIs. Reductions will already have been
478 // truncated if possible, and inductions' sizes will have been chosen by
479 // indvars.
480 if (isa<PHINode>(I))
481 continue;
482
483 if (DBits[Leader] == ~0ULL)
484 // All bits demanded, no point continuing.
485 continue;
486
487 for (Value *O : cast<User>(I)->operands()) {
488 ECs.unionSets(Leader, O);
489 Worklist.push_back(O);
490 }
491 }
492
493 // Now we've discovered all values, walk them to see if there are
494 // any users we didn't see. If there are, we can't optimize that
495 // chain.
496 for (auto &I : DBits)
497 for (auto *U : I.first->users())
498 if (U->getType()->isIntegerTy() && DBits.count(U) == 0)
499 DBits[ECs.getOrInsertLeaderValue(I.first)] |= ~0ULL;
500
501 for (auto I = ECs.begin(), E = ECs.end(); I != E; ++I) {
502 uint64_t LeaderDemandedBits = 0;
503 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
504 LeaderDemandedBits |= DBits[*MI];
505
506 uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) -
507 llvm::countLeadingZeros(LeaderDemandedBits);
508 // Round up to a power of 2
509 if (!isPowerOf2_64((uint64_t)MinBW))
510 MinBW = NextPowerOf2(MinBW);
511
512 // We don't modify the types of PHIs. Reductions will already have been
513 // truncated if possible, and inductions' sizes will have been chosen by
514 // indvars.
515 // If we are required to shrink a PHI, abandon this entire equivalence class.
516 bool Abort = false;
517 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
518 if (isa<PHINode>(*MI) && MinBW < (*MI)->getType()->getScalarSizeInBits()) {
519 Abort = true;
520 break;
521 }
522 if (Abort)
523 continue;
524
525 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) {
526 if (!isa<Instruction>(*MI))
527 continue;
528 Type *Ty = (*MI)->getType();
529 if (Roots.count(*MI))
530 Ty = cast<Instruction>(*MI)->getOperand(0)->getType();
531 if (MinBW < Ty->getScalarSizeInBits())
532 MinBWs[cast<Instruction>(*MI)] = MinBW;
533 }
534 }
535
536 return MinBWs;
537}
538
539/// Add all access groups in @p AccGroups to @p List.
540template <typename ListT>
541static void addToAccessGroupList(ListT &List, MDNode *AccGroups) {
542 // Interpret an access group as a list containing itself.
543 if (AccGroups->getNumOperands() == 0) {
544 assert(isValidAsAccessGroup(AccGroups) && "Node must be an access group")((isValidAsAccessGroup(AccGroups) && "Node must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroups) && \"Node must be an access group\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 544, __PRETTY_FUNCTION__))
;
545 List.insert(AccGroups);
546 return;
547 }
548
549 for (auto &AccGroupListOp : AccGroups->operands()) {
550 auto *Item = cast<MDNode>(AccGroupListOp.get());
551 assert(isValidAsAccessGroup(Item) && "List item must be an access group")((isValidAsAccessGroup(Item) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(Item) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 551, __PRETTY_FUNCTION__))
;
552 List.insert(Item);
553 }
554}
555
556MDNode *llvm::uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2) {
557 if (!AccGroups1)
558 return AccGroups2;
559 if (!AccGroups2)
560 return AccGroups1;
561 if (AccGroups1 == AccGroups2)
562 return AccGroups1;
563
564 SmallSetVector<Metadata *, 4> Union;
565 addToAccessGroupList(Union, AccGroups1);
566 addToAccessGroupList(Union, AccGroups2);
567
568 if (Union.size() == 0)
569 return nullptr;
570 if (Union.size() == 1)
571 return cast<MDNode>(Union.front());
572
573 LLVMContext &Ctx = AccGroups1->getContext();
574 return MDNode::get(Ctx, Union.getArrayRef());
575}
576
577MDNode *llvm::intersectAccessGroups(const Instruction *Inst1,
578 const Instruction *Inst2) {
579 bool MayAccessMem1 = Inst1->mayReadOrWriteMemory();
580 bool MayAccessMem2 = Inst2->mayReadOrWriteMemory();
581
582 if (!MayAccessMem1 && !MayAccessMem2)
583 return nullptr;
584 if (!MayAccessMem1)
585 return Inst2->getMetadata(LLVMContext::MD_access_group);
586 if (!MayAccessMem2)
587 return Inst1->getMetadata(LLVMContext::MD_access_group);
588
589 MDNode *MD1 = Inst1->getMetadata(LLVMContext::MD_access_group);
590 MDNode *MD2 = Inst2->getMetadata(LLVMContext::MD_access_group);
591 if (!MD1 || !MD2)
592 return nullptr;
593 if (MD1 == MD2)
594 return MD1;
595
596 // Use set for scalable 'contains' check.
597 SmallPtrSet<Metadata *, 4> AccGroupSet2;
598 addToAccessGroupList(AccGroupSet2, MD2);
599
600 SmallVector<Metadata *, 4> Intersection;
601 if (MD1->getNumOperands() == 0) {
602 assert(isValidAsAccessGroup(MD1) && "Node must be an access group")((isValidAsAccessGroup(MD1) && "Node must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(MD1) && \"Node must be an access group\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 602, __PRETTY_FUNCTION__))
;
603 if (AccGroupSet2.count(MD1))
604 Intersection.push_back(MD1);
605 } else {
606 for (const MDOperand &Node : MD1->operands()) {
607 auto *Item = cast<MDNode>(Node.get());
608 assert(isValidAsAccessGroup(Item) && "List item must be an access group")((isValidAsAccessGroup(Item) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(Item) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 608, __PRETTY_FUNCTION__))
;
609 if (AccGroupSet2.count(Item))
610 Intersection.push_back(Item);
611 }
612 }
613
614 if (Intersection.size() == 0)
615 return nullptr;
616 if (Intersection.size() == 1)
617 return cast<MDNode>(Intersection.front());
618
619 LLVMContext &Ctx = Inst1->getContext();
620 return MDNode::get(Ctx, Intersection);
621}
622
623/// \returns \p I after propagating metadata from \p VL.
624Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) {
625 Instruction *I0 = cast<Instruction>(VL[0]);
626 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
627 I0->getAllMetadataOtherThanDebugLoc(Metadata);
628
629 for (auto Kind : {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
630 LLVMContext::MD_noalias, LLVMContext::MD_fpmath,
631 LLVMContext::MD_nontemporal, LLVMContext::MD_invariant_load,
632 LLVMContext::MD_access_group}) {
633 MDNode *MD = I0->getMetadata(Kind);
634
635 for (int J = 1, E = VL.size(); MD && J != E; ++J) {
636 const Instruction *IJ = cast<Instruction>(VL[J]);
637 MDNode *IMD = IJ->getMetadata(Kind);
638 switch (Kind) {
639 case LLVMContext::MD_tbaa:
640 MD = MDNode::getMostGenericTBAA(MD, IMD);
641 break;
642 case LLVMContext::MD_alias_scope:
643 MD = MDNode::getMostGenericAliasScope(MD, IMD);
644 break;
645 case LLVMContext::MD_fpmath:
646 MD = MDNode::getMostGenericFPMath(MD, IMD);
647 break;
648 case LLVMContext::MD_noalias:
649 case LLVMContext::MD_nontemporal:
650 case LLVMContext::MD_invariant_load:
651 MD = MDNode::intersect(MD, IMD);
652 break;
653 case LLVMContext::MD_access_group:
654 MD = intersectAccessGroups(Inst, IJ);
655 break;
656 default:
657 llvm_unreachable("unhandled metadata")::llvm::llvm_unreachable_internal("unhandled metadata", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 657)
;
658 }
659 }
660
661 Inst->setMetadata(Kind, MD);
662 }
663
664 return Inst;
665}
666
667Constant *
668llvm::createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF,
669 const InterleaveGroup<Instruction> &Group) {
670 // All 1's means mask is not needed.
671 if (Group.getNumMembers() == Group.getFactor())
672 return nullptr;
673
674 // TODO: support reversed access.
675 assert(!Group.isReverse() && "Reversed group not supported.")((!Group.isReverse() && "Reversed group not supported."
) ? static_cast<void> (0) : __assert_fail ("!Group.isReverse() && \"Reversed group not supported.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 675, __PRETTY_FUNCTION__))
;
676
677 SmallVector<Constant *, 16> Mask;
678 for (unsigned i = 0; i < VF; i++)
679 for (unsigned j = 0; j < Group.getFactor(); ++j) {
680 unsigned HasMember = Group.getMember(j) ? 1 : 0;
681 Mask.push_back(Builder.getInt1(HasMember));
682 }
683
684 return ConstantVector::get(Mask);
685}
686
687Constant *llvm::createReplicatedMask(IRBuilderBase &Builder,
688 unsigned ReplicationFactor, unsigned VF) {
689 SmallVector<Constant *, 16> MaskVec;
690 for (unsigned i = 0; i < VF; i++)
691 for (unsigned j = 0; j < ReplicationFactor; j++)
692 MaskVec.push_back(Builder.getInt32(i));
693
694 return ConstantVector::get(MaskVec);
695}
696
697Constant *llvm::createInterleaveMask(IRBuilderBase &Builder, unsigned VF,
698 unsigned NumVecs) {
699 SmallVector<Constant *, 16> Mask;
700 for (unsigned i = 0; i < VF; i++)
701 for (unsigned j = 0; j < NumVecs; j++)
702 Mask.push_back(Builder.getInt32(j * VF + i));
703
704 return ConstantVector::get(Mask);
705}
706
707Constant *llvm::createStrideMask(IRBuilderBase &Builder, unsigned Start,
708 unsigned Stride, unsigned VF) {
709 SmallVector<Constant *, 16> Mask;
710 for (unsigned i = 0; i < VF; i++)
711 Mask.push_back(Builder.getInt32(Start + i * Stride));
712
713 return ConstantVector::get(Mask);
714}
715
716Constant *llvm::createSequentialMask(IRBuilderBase &Builder, unsigned Start,
717 unsigned NumInts, unsigned NumUndefs) {
718 SmallVector<Constant *, 16> Mask;
719 for (unsigned i = 0; i < NumInts; i++)
720 Mask.push_back(Builder.getInt32(Start + i));
721
722 Constant *Undef = UndefValue::get(Builder.getInt32Ty());
723 for (unsigned i = 0; i < NumUndefs; i++)
724 Mask.push_back(Undef);
725
726 return ConstantVector::get(Mask);
727}
728
729/// A helper function for concatenating vectors. This function concatenates two
730/// vectors having the same element type. If the second vector has fewer
731/// elements than the first, it is padded with undefs.
732static Value *concatenateTwoVectors(IRBuilderBase &Builder, Value *V1,
733 Value *V2) {
734 VectorType *VecTy1 = dyn_cast<VectorType>(V1->getType());
735 VectorType *VecTy2 = dyn_cast<VectorType>(V2->getType());
736 assert(VecTy1 && VecTy2 &&((VecTy1 && VecTy2 && VecTy1->getScalarType
() == VecTy2->getScalarType() && "Expect two vectors with the same element type"
) ? static_cast<void> (0) : __assert_fail ("VecTy1 && VecTy2 && VecTy1->getScalarType() == VecTy2->getScalarType() && \"Expect two vectors with the same element type\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 738, __PRETTY_FUNCTION__))
737 VecTy1->getScalarType() == VecTy2->getScalarType() &&((VecTy1 && VecTy2 && VecTy1->getScalarType
() == VecTy2->getScalarType() && "Expect two vectors with the same element type"
) ? static_cast<void> (0) : __assert_fail ("VecTy1 && VecTy2 && VecTy1->getScalarType() == VecTy2->getScalarType() && \"Expect two vectors with the same element type\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 738, __PRETTY_FUNCTION__))
738 "Expect two vectors with the same element type")((VecTy1 && VecTy2 && VecTy1->getScalarType
() == VecTy2->getScalarType() && "Expect two vectors with the same element type"
) ? static_cast<void> (0) : __assert_fail ("VecTy1 && VecTy2 && VecTy1->getScalarType() == VecTy2->getScalarType() && \"Expect two vectors with the same element type\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 738, __PRETTY_FUNCTION__))
;
739
740 unsigned NumElts1 = VecTy1->getNumElements();
741 unsigned NumElts2 = VecTy2->getNumElements();
742 assert(NumElts1 >= NumElts2 && "Unexpect the first vector has less elements")((NumElts1 >= NumElts2 && "Unexpect the first vector has less elements"
) ? static_cast<void> (0) : __assert_fail ("NumElts1 >= NumElts2 && \"Unexpect the first vector has less elements\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 742, __PRETTY_FUNCTION__))
;
743
744 if (NumElts1 > NumElts2) {
745 // Extend with UNDEFs.
746 Constant *ExtMask =
747 createSequentialMask(Builder, 0, NumElts2, NumElts1 - NumElts2);
748 V2 = Builder.CreateShuffleVector(V2, UndefValue::get(VecTy2), ExtMask);
749 }
750
751 Constant *Mask = createSequentialMask(Builder, 0, NumElts1 + NumElts2, 0);
752 return Builder.CreateShuffleVector(V1, V2, Mask);
753}
754
755Value *llvm::concatenateVectors(IRBuilderBase &Builder,
756 ArrayRef<Value *> Vecs) {
757 unsigned NumVecs = Vecs.size();
758 assert(NumVecs > 1 && "Should be at least two vectors")((NumVecs > 1 && "Should be at least two vectors")
? static_cast<void> (0) : __assert_fail ("NumVecs > 1 && \"Should be at least two vectors\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 758, __PRETTY_FUNCTION__))
;
759
760 SmallVector<Value *, 8> ResList;
761 ResList.append(Vecs.begin(), Vecs.end());
762 do {
763 SmallVector<Value *, 8> TmpList;
764 for (unsigned i = 0; i < NumVecs - 1; i += 2) {
765 Value *V0 = ResList[i], *V1 = ResList[i + 1];
766 assert((V0->getType() == V1->getType() || i == NumVecs - 2) &&(((V0->getType() == V1->getType() || i == NumVecs - 2) &&
"Only the last vector may have a different type") ? static_cast
<void> (0) : __assert_fail ("(V0->getType() == V1->getType() || i == NumVecs - 2) && \"Only the last vector may have a different type\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 767, __PRETTY_FUNCTION__))
767 "Only the last vector may have a different type")(((V0->getType() == V1->getType() || i == NumVecs - 2) &&
"Only the last vector may have a different type") ? static_cast
<void> (0) : __assert_fail ("(V0->getType() == V1->getType() || i == NumVecs - 2) && \"Only the last vector may have a different type\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 767, __PRETTY_FUNCTION__))
;
768
769 TmpList.push_back(concatenateTwoVectors(Builder, V0, V1));
770 }
771
772 // Push the last vector if the total number of vectors is odd.
773 if (NumVecs % 2 != 0)
774 TmpList.push_back(ResList[NumVecs - 1]);
775
776 ResList = TmpList;
777 NumVecs = ResList.size();
778 } while (NumVecs > 1);
779
780 return ResList[0];
781}
782
783bool llvm::maskIsAllZeroOrUndef(Value *Mask) {
784 auto *ConstMask = dyn_cast<Constant>(Mask);
785 if (!ConstMask)
786 return false;
787 if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
788 return true;
789 for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
790 ++I) {
791 if (auto *MaskElt = ConstMask->getAggregateElement(I))
792 if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
793 continue;
794 return false;
795 }
796 return true;
797}
798
799
800bool llvm::maskIsAllOneOrUndef(Value *Mask) {
801 auto *ConstMask = dyn_cast<Constant>(Mask);
802 if (!ConstMask)
803 return false;
804 if (ConstMask->isAllOnesValue() || isa<UndefValue>(ConstMask))
805 return true;
806 for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
807 ++I) {
808 if (auto *MaskElt = ConstMask->getAggregateElement(I))
809 if (MaskElt->isAllOnesValue() || isa<UndefValue>(MaskElt))
810 continue;
811 return false;
812 }
813 return true;
814}
815
816/// TODO: This is a lot like known bits, but for
817/// vectors. Is there something we can common this with?
818APInt llvm::possiblyDemandedEltsInMask(Value *Mask) {
819
820 const unsigned VWidth = cast<VectorType>(Mask->getType())->getNumElements();
821 APInt DemandedElts = APInt::getAllOnesValue(VWidth);
822 if (auto *CV = dyn_cast<ConstantVector>(Mask))
823 for (unsigned i = 0; i < VWidth; i++)
824 if (CV->getAggregateElement(i)->isNullValue())
825 DemandedElts.clearBit(i);
826 return DemandedElts;
827}
828
829bool InterleavedAccessInfo::isStrided(int Stride) {
830 unsigned Factor = std::abs(Stride);
831 return Factor >= 2 && Factor <= MaxInterleaveGroupFactor;
53
Assuming 'Factor' is >= 2
54
Assuming the condition is true
55
Returning the value 1, which participates in a condition later
58
Assuming 'Factor' is >= 2
59
Assuming the condition is true
60
Returning the value 1, which participates in a condition later
832}
833
834void InterleavedAccessInfo::collectConstStrideAccesses(
835 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
836 const ValueToValueMap &Strides) {
837 auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
838
839 // Since it's desired that the load/store instructions be maintained in
840 // "program order" for the interleaved access analysis, we have to visit the
841 // blocks in the loop in reverse postorder (i.e., in a topological order).
842 // Such an ordering will ensure that any load/store that may be executed
843 // before a second load/store will precede the second load/store in
844 // AccessStrideInfo.
845 LoopBlocksDFS DFS(TheLoop);
846 DFS.perform(LI);
847 for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
848 for (auto &I : *BB) {
849 auto *LI = dyn_cast<LoadInst>(&I);
850 auto *SI = dyn_cast<StoreInst>(&I);
851 if (!LI && !SI)
852 continue;
853
854 Value *Ptr = getLoadStorePointerOperand(&I);
855 // We don't check wrapping here because we don't know yet if Ptr will be
856 // part of a full group or a group with gaps. Checking wrapping for all
857 // pointers (even those that end up in groups with no gaps) will be overly
858 // conservative. For full groups, wrapping should be ok since if we would
859 // wrap around the address space we would do a memory access at nullptr
860 // even without the transformation. The wrapping checks are therefore
861 // deferred until after we've formed the interleaved groups.
862 int64_t Stride = getPtrStride(PSE, Ptr, TheLoop, Strides,
863 /*Assume=*/true, /*ShouldCheckWrap=*/false);
864
865 const SCEV *Scev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
866 PointerType *PtrTy = cast<PointerType>(Ptr->getType());
867 uint64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());
868
869 // An alignment of 0 means target ABI alignment.
870 MaybeAlign Alignment = MaybeAlign(getLoadStoreAlignment(&I));
871 if (!Alignment)
872 Alignment = Align(DL.getABITypeAlignment(PtrTy->getElementType()));
873
874 AccessStrideInfo[&I] = StrideDescriptor(Stride, Scev, Size, *Alignment);
875 }
876}
877
878// Analyze interleaved accesses and collect them into interleaved load and
879// store groups.
880//
881// When generating code for an interleaved load group, we effectively hoist all
882// loads in the group to the location of the first load in program order. When
883// generating code for an interleaved store group, we sink all stores to the
884// location of the last store. This code motion can change the order of load
885// and store instructions and may break dependences.
886//
887// The code generation strategy mentioned above ensures that we won't violate
888// any write-after-read (WAR) dependences.
889//
890// E.g., for the WAR dependence: a = A[i]; // (1)
891// A[i] = b; // (2)
892//
893// The store group of (2) is always inserted at or below (2), and the load
894// group of (1) is always inserted at or above (1). Thus, the instructions will
895// never be reordered. All other dependences are checked to ensure the
896// correctness of the instruction reordering.
897//
898// The algorithm visits all memory accesses in the loop in bottom-up program
899// order. Program order is established by traversing the blocks in the loop in
900// reverse postorder when collecting the accesses.
901//
902// We visit the memory accesses in bottom-up order because it can simplify the
903// construction of store groups in the presence of write-after-write (WAW)
904// dependences.
905//
906// E.g., for the WAW dependence: A[i] = a; // (1)
907// A[i] = b; // (2)
908// A[i + 1] = c; // (3)
909//
910// We will first create a store group with (3) and (2). (1) can't be added to
911// this group because it and (2) are dependent. However, (1) can be grouped
912// with other accesses that may precede it in program order. Note that a
913// bottom-up order does not imply that WAW dependences should not be checked.
914void InterleavedAccessInfo::analyzeInterleaving(
915 bool EnablePredicatedInterleavedMemAccesses) {
916 LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Analyzing interleaved accesses...\n"
; } } while (false)
;
1
Assuming 'DebugFlag' is false
2
Loop condition is false. Exiting loop
917 const ValueToValueMap &Strides = LAI->getSymbolicStrides();
918
919 // Holds all accesses with a constant stride.
920 MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
921 collectConstStrideAccesses(AccessStrideInfo, Strides);
922
923 if (AccessStrideInfo.empty())
3
Assuming the condition is false
4
Taking false branch
924 return;
925
926 // Collect the dependences in the loop.
927 collectDependences();
928
929 // Holds all interleaved store groups temporarily.
930 SmallSetVector<InterleaveGroup<Instruction> *, 4> StoreGroups;
931 // Holds all interleaved load groups temporarily.
932 SmallSetVector<InterleaveGroup<Instruction> *, 4> LoadGroups;
933
934 // Search in bottom-up program order for pairs of accesses (A and B) that can
935 // form interleaved load or store groups. In the algorithm below, access A
936 // precedes access B in program order. We initialize a group for B in the
937 // outer loop of the algorithm, and then in the inner loop, we attempt to
938 // insert each A into B's group if:
939 //
940 // 1. A and B have the same stride,
941 // 2. A and B have the same memory object size, and
942 // 3. A belongs in B's group according to its distance from B.
943 //
944 // Special care is taken to ensure group formation will not break any
945 // dependences.
946 for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
15
Loop condition is true. Entering loop body
947 BI != E; ++BI) {
5
Calling 'operator!=<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
14
Returning from 'operator!=<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
948 Instruction *B = BI->first;
949 StrideDescriptor DesB = BI->second;
950
951 // Initialize a group for B if it has an allowable stride. Even if we don't
952 // create a group for B, we continue with the bottom-up algorithm to ensure
953 // we don't break any of B's dependences.
954 InterleaveGroup<Instruction> *Group = nullptr;
16
'Group' initialized to a null pointer value
955 if (isStrided(DesB.Stride) &&
956 (!isPredicated(B->getParent()) || EnablePredicatedInterleavedMemAccesses)) {
957 Group = getInterleaveGroup(B);
958 if (!Group) {
959 LLVM_DEBUG(dbgs() << "LV: Creating an interleave group with:" << *Bdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Creating an interleave group with:"
<< *B << '\n'; } } while (false)
960 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Creating an interleave group with:"
<< *B << '\n'; } } while (false)
;
961 Group = createInterleaveGroup(B, DesB.Stride, DesB.Alignment);
962 }
963 if (B->mayWriteToMemory())
964 StoreGroups.insert(Group);
965 else
966 LoadGroups.insert(Group);
967 }
968
969 for (auto AI = std::next(BI); AI != E; ++AI) {
17
Calling 'operator!=<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
26
Returning from 'operator!=<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
27
Loop condition is true. Entering loop body
35
Calling 'operator!=<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
44
Returning from 'operator!=<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
45
Loop condition is true. Entering loop body
970 Instruction *A = AI->first;
971 StrideDescriptor DesA = AI->second;
972
973 // Our code motion strategy implies that we can't have dependences
974 // between accesses in an interleaved group and other accesses located
975 // between the first and last member of the group. Note that this also
976 // means that a group can't have more than one member at a given offset.
977 // The accesses in a group can have dependences with other accesses, but
978 // we must ensure we don't extend the boundaries of the group such that
979 // we encompass those dependent accesses.
980 //
981 // For example, assume we have the sequence of accesses shown below in a
982 // stride-2 loop:
983 //
984 // (1, 2) is a group | A[i] = a; // (1)
985 // | A[i-1] = b; // (2) |
986 // A[i-3] = c; // (3)
987 // A[i] = d; // (4) | (2, 4) is not a group
988 //
989 // Because accesses (2) and (3) are dependent, we can group (2) with (1)
990 // but not with (4). If we did, the dependent access (3) would be within
991 // the boundaries of the (2, 4) group.
992 if (!canReorderMemAccessesForInterleavedGroups(&*AI, &*BI)) {
28
Calling 'InterleavedAccessInfo::canReorderMemAccessesForInterleavedGroups'
32
Returning from 'InterleavedAccessInfo::canReorderMemAccessesForInterleavedGroups'
33
Taking false branch
46
Calling 'InterleavedAccessInfo::canReorderMemAccessesForInterleavedGroups'
50
Returning from 'InterleavedAccessInfo::canReorderMemAccessesForInterleavedGroups'
51
Taking false branch
993 // If a dependence exists and A is already in a group, we know that A
994 // must be a store since A precedes B and WAR dependences are allowed.
995 // Thus, A would be sunk below B. We release A's group to prevent this
996 // illegal code motion. A will then be free to form another group with
997 // instructions that precede it.
998 if (isInterleaved(A)) {
999 InterleaveGroup<Instruction> *StoreGroup = getInterleaveGroup(A);
1000
1001 LLVM_DEBUG(dbgs() << "LV: Invalidated store group due to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidated store group due to "
"dependence between " << *A << " and "<< *
B << '\n'; } } while (false)
1002 "dependence between " << *A << " and "<< *B << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidated store group due to "
"dependence between " << *A << " and "<< *
B << '\n'; } } while (false)
;
1003
1004 StoreGroups.remove(StoreGroup);
1005 releaseGroup(StoreGroup);
1006 }
1007
1008 // If a dependence exists and A is not already in a group (or it was
1009 // and we just released it), B might be hoisted above A (if B is a
1010 // load) or another store might be sunk below A (if B is a store). In
1011 // either case, we can't add additional instructions to B's group. B
1012 // will only form a group with instructions that it precedes.
1013 break;
1014 }
1015
1016 // At this point, we've checked for illegal code motion. If either A or B
1017 // isn't strided, there's nothing left to do.
1018 if (!isStrided(DesA.Stride) || !isStrided(DesB.Stride))
52
Calling 'InterleavedAccessInfo::isStrided'
56
Returning from 'InterleavedAccessInfo::isStrided'
57
Calling 'InterleavedAccessInfo::isStrided'
61
Returning from 'InterleavedAccessInfo::isStrided'
62
Taking false branch
1019 continue;
34
Execution continues on line 969
1020
1021 // Ignore A if it's already in a group or isn't the same kind of memory
1022 // operation as B.
1023 // Note that mayReadFromMemory() isn't mutually exclusive to
1024 // mayWriteToMemory in the case of atomic loads. We shouldn't see those
1025 // here, canVectorizeMemory() should have returned false - except for the
1026 // case we asked for optimization remarks.
1027 if (isInterleaved(A) ||
63
Assuming the condition is false
66
Taking false branch
1028 (A->mayReadFromMemory() != B->mayReadFromMemory()) ||
64
Assuming the condition is false
1029 (A->mayWriteToMemory() != B->mayWriteToMemory()))
65
Assuming the condition is false
1030 continue;
1031
1032 // Check rules 1 and 2. Ignore A if its stride or size is different from
1033 // that of B.
1034 if (DesA.Stride != DesB.Stride || DesA.Size != DesB.Size)
67
Assuming 'DesA.Stride' is equal to 'DesB.Stride'
68
Assuming 'DesA.Size' is equal to 'DesB.Size'
69
Taking false branch
1035 continue;
1036
1037 // Ignore A if the memory object of A and B don't belong to the same
1038 // address space
1039 if (getLoadStoreAddressSpace(A) != getLoadStoreAddressSpace(B))
70
Assuming the condition is false
71
Taking false branch
1040 continue;
1041
1042 // Calculate the distance from A to B.
1043 const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
72
Assuming the object is a 'SCEVConstant'
1044 PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
1045 if (!DistToB
72.1
'DistToB' is non-null
72.1
'DistToB' is non-null
72.1
'DistToB' is non-null
)
73
Taking false branch
1046 continue;
1047 int64_t DistanceToB = DistToB->getAPInt().getSExtValue();
1048
1049 // Check rule 3. Ignore A if its distance to B is not a multiple of the
1050 // size.
1051 if (DistanceToB % static_cast<int64_t>(DesB.Size))
74
Assuming the condition is false
75
Taking false branch
1052 continue;
1053
1054 // All members of a predicated interleave-group must have the same predicate,
1055 // and currently must reside in the same BB.
1056 BasicBlock *BlockA = A->getParent();
1057 BasicBlock *BlockB = B->getParent();
1058 if ((isPredicated(BlockA) || isPredicated(BlockB)) &&
76
Assuming the condition is true
79
Taking false branch
1059 (!EnablePredicatedInterleavedMemAccesses || BlockA != BlockB))
77
Assuming 'EnablePredicatedInterleavedMemAccesses' is true
78
Assuming 'BlockA' is equal to 'BlockB'
1060 continue;
1061
1062 // The index of A is the index of B plus A's distance to B in multiples
1063 // of the size.
1064 int IndexA =
1065 Group->getIndex(B) + DistanceToB / static_cast<int64_t>(DesB.Size);
80
Called C++ object pointer is null
1066
1067 // Try to insert A into B's group.
1068 if (Group->insertMember(A, IndexA, DesA.Alignment)) {
1069 LLVM_DEBUG(dbgs() << "LV: Inserted:" << *A << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Inserted:" << *
A << '\n' << " into the interleave group with"
<< *B << '\n'; } } while (false)
1070 << " into the interleave group with" << *Bdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Inserted:" << *
A << '\n' << " into the interleave group with"
<< *B << '\n'; } } while (false)
1071 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Inserted:" << *
A << '\n' << " into the interleave group with"
<< *B << '\n'; } } while (false)
;
1072 InterleaveGroupMap[A] = Group;
1073
1074 // Set the first load in program order as the insert position.
1075 if (A->mayReadFromMemory())
1076 Group->setInsertPos(A);
1077 }
1078 } // Iteration over A accesses.
1079 } // Iteration over B accesses.
1080
1081 // Remove interleaved store groups with gaps.
1082 for (auto *Group : StoreGroups)
1083 if (Group->getNumMembers() != Group->getFactor()) {
1084 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved store group due "
"to gaps.\n"; } } while (false)
1085 dbgs() << "LV: Invalidate candidate interleaved store group due "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved store group due "
"to gaps.\n"; } } while (false)
1086 "to gaps.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved store group due "
"to gaps.\n"; } } while (false)
;
1087 releaseGroup(Group);
1088 }
1089 // Remove interleaved groups with gaps (currently only loads) whose memory
1090 // accesses may wrap around. We have to revisit the getPtrStride analysis,
1091 // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
1092 // not check wrapping (see documentation there).
1093 // FORNOW we use Assume=false;
1094 // TODO: Change to Assume=true but making sure we don't exceed the threshold
1095 // of runtime SCEV assumptions checks (thereby potentially failing to
1096 // vectorize altogether).
1097 // Additional optional optimizations:
1098 // TODO: If we are peeling the loop and we know that the first pointer doesn't
1099 // wrap then we can deduce that all pointers in the group don't wrap.
1100 // This means that we can forcefully peel the loop in order to only have to
1101 // check the first pointer for no-wrap. When we'll change to use Assume=true
1102 // we'll only need at most one runtime check per interleaved group.
1103 for (auto *Group : LoadGroups) {
1104 // Case 1: A full group. Can Skip the checks; For full groups, if the wide
1105 // load would wrap around the address space we would do a memory access at
1106 // nullptr even without the transformation.
1107 if (Group->getNumMembers() == Group->getFactor())
1108 continue;
1109
1110 // Case 2: If first and last members of the group don't wrap this implies
1111 // that all the pointers in the group don't wrap.
1112 // So we check only group member 0 (which is always guaranteed to exist),
1113 // and group member Factor - 1; If the latter doesn't exist we rely on
1114 // peeling (if it is a non-reversed accsess -- see Case 3).
1115 Value *FirstMemberPtr = getLoadStorePointerOperand(Group->getMember(0));
1116 if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /*Assume=*/false,
1117 /*ShouldCheckWrap=*/true)) {
1118 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"first group member potentially pointer-wrapping.\n"; } } while
(false)
1119 dbgs() << "LV: Invalidate candidate interleaved group due to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"first group member potentially pointer-wrapping.\n"; } } while
(false)
1120 "first group member potentially pointer-wrapping.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"first group member potentially pointer-wrapping.\n"; } } while
(false)
;
1121 releaseGroup(Group);
1122 continue;
1123 }
1124 Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
1125 if (LastMember) {
1126 Value *LastMemberPtr = getLoadStorePointerOperand(LastMember);
1127 if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /*Assume=*/false,
1128 /*ShouldCheckWrap=*/true)) {
1129 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"last group member potentially pointer-wrapping.\n"; } } while
(false)
1130 dbgs() << "LV: Invalidate candidate interleaved group due to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"last group member potentially pointer-wrapping.\n"; } } while
(false)
1131 "last group member potentially pointer-wrapping.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"last group member potentially pointer-wrapping.\n"; } } while
(false)
;
1132 releaseGroup(Group);
1133 }
1134 } else {
1135 // Case 3: A non-reversed interleaved load group with gaps: We need
1136 // to execute at least one scalar epilogue iteration. This will ensure
1137 // we don't speculatively access memory out-of-bounds. We only need
1138 // to look for a member at index factor - 1, since every group must have
1139 // a member at index zero.
1140 if (Group->isReverse()) {
1141 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"a reverse access with gaps.\n"; } } while (false)
1142 dbgs() << "LV: Invalidate candidate interleaved group due to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"a reverse access with gaps.\n"; } } while (false)
1143 "a reverse access with gaps.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to "
"a reverse access with gaps.\n"; } } while (false)
;
1144 releaseGroup(Group);
1145 continue;
1146 }
1147 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Interleaved group requires epilogue iteration.\n"
; } } while (false)
1148 dbgs() << "LV: Interleaved group requires epilogue iteration.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Interleaved group requires epilogue iteration.\n"
; } } while (false)
;
1149 RequiresScalarEpilogue = true;
1150 }
1151 }
1152}
1153
1154void InterleavedAccessInfo::invalidateGroupsRequiringScalarEpilogue() {
1155 // If no group had triggered the requirement to create an epilogue loop,
1156 // there is nothing to do.
1157 if (!requiresScalarEpilogue())
1158 return;
1159
1160 // Avoid releasing a Group twice.
1161 SmallPtrSet<InterleaveGroup<Instruction> *, 4> DelSet;
1162 for (auto &I : InterleaveGroupMap) {
1163 InterleaveGroup<Instruction> *Group = I.second;
1164 if (Group->requiresScalarEpilogue())
1165 DelSet.insert(Group);
1166 }
1167 for (auto *Ptr : DelSet) {
1168 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to gaps that "
"require a scalar epilogue (not allowed under optsize) and cannot "
"be masked (not enabled). \n"; } } while (false)
1169 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to gaps that "
"require a scalar epilogue (not allowed under optsize) and cannot "
"be masked (not enabled). \n"; } } while (false)
1170 << "LV: Invalidate candidate interleaved group due to gaps that "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to gaps that "
"require a scalar epilogue (not allowed under optsize) and cannot "
"be masked (not enabled). \n"; } } while (false)
1171 "require a scalar epilogue (not allowed under optsize) and cannot "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to gaps that "
"require a scalar epilogue (not allowed under optsize) and cannot "
"be masked (not enabled). \n"; } } while (false)
1172 "be masked (not enabled). \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved group due to gaps that "
"require a scalar epilogue (not allowed under optsize) and cannot "
"be masked (not enabled). \n"; } } while (false)
;
1173 releaseGroup(Ptr);
1174 }
1175
1176 RequiresScalarEpilogue = false;
1177}
1178
1179template <typename InstT>
1180void InterleaveGroup<InstT>::addMetadata(InstT *NewInst) const {
1181 llvm_unreachable("addMetadata can only be used for Instruction")::llvm::llvm_unreachable_internal("addMetadata can only be used for Instruction"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 1181)
;
1182}
1183
1184namespace llvm {
1185template <>
1186void InterleaveGroup<Instruction>::addMetadata(Instruction *NewInst) const {
1187 SmallVector<Value *, 4> VL;
1188 std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
1189 [](std::pair<int, Instruction *> p) { return p.second; });
1190 propagateMetadata(NewInst, VL);
1191}
1192}
1193
1194void VFABI::getVectorVariantNames(
1195 const CallInst &CI, SmallVectorImpl<std::string> &VariantMappings) {
1196 const StringRef S =
1197 CI.getAttribute(AttributeList::FunctionIndex, VFABI::MappingsAttrName)
1198 .getValueAsString();
1199 if (S.empty())
1200 return;
1201
1202 SmallVector<StringRef, 8> ListAttr;
1203 S.split(ListAttr, ",");
1204
1205 for (auto &S : SetVector<StringRef>(ListAttr.begin(), ListAttr.end())) {
1206#ifndef NDEBUG
1207 LLVM_DEBUG(dbgs() << "VFABI: adding mapping '" << S << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "VFABI: adding mapping '" <<
S << "'\n"; } } while (false)
;
1208 Optional<VFInfo> Info = VFABI::tryDemangleForVFABI(S, *(CI.getModule()));
1209 assert(Info.hasValue() && "Invalid name for a VFABI variant.")((Info.hasValue() && "Invalid name for a VFABI variant."
) ? static_cast<void> (0) : __assert_fail ("Info.hasValue() && \"Invalid name for a VFABI variant.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 1209, __PRETTY_FUNCTION__))
;
1210 assert(CI.getModule()->getFunction(Info.getValue().VectorName) &&((CI.getModule()->getFunction(Info.getValue().VectorName) &&
"Vector function is missing.") ? static_cast<void> (0)
: __assert_fail ("CI.getModule()->getFunction(Info.getValue().VectorName) && \"Vector function is missing.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 1211, __PRETTY_FUNCTION__))
1211 "Vector function is missing.")((CI.getModule()->getFunction(Info.getValue().VectorName) &&
"Vector function is missing.") ? static_cast<void> (0)
: __assert_fail ("CI.getModule()->getFunction(Info.getValue().VectorName) && \"Vector function is missing.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 1211, __PRETTY_FUNCTION__))
;
1212#endif
1213 VariantMappings.push_back(std::string(S));
1214 }
1215}
1216
1217bool VFShape::hasValidParameterList() const {
1218 for (unsigned Pos = 0, NumParams = Parameters.size(); Pos < NumParams;
1219 ++Pos) {
1220 assert(Parameters[Pos].ParamPos == Pos && "Broken parameter list.")((Parameters[Pos].ParamPos == Pos && "Broken parameter list."
) ? static_cast<void> (0) : __assert_fail ("Parameters[Pos].ParamPos == Pos && \"Broken parameter list.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Analysis/VectorUtils.cpp"
, 1220, __PRETTY_FUNCTION__))
;
1221
1222 switch (Parameters[Pos].ParamKind) {
1223 default: // Nothing to check.
1224 break;
1225 case VFParamKind::OMP_Linear:
1226 case VFParamKind::OMP_LinearRef:
1227 case VFParamKind::OMP_LinearVal:
1228 case VFParamKind::OMP_LinearUVal:
1229 // Compile time linear steps must be non-zero.
1230 if (Parameters[Pos].LinearStepOrPos == 0)
1231 return false;
1232 break;
1233 case VFParamKind::OMP_LinearPos:
1234 case VFParamKind::OMP_LinearRefPos:
1235 case VFParamKind::OMP_LinearValPos:
1236 case VFParamKind::OMP_LinearUValPos:
1237 // The runtime linear step must be referring to some other
1238 // parameters in the signature.
1239 if (Parameters[Pos].LinearStepOrPos >= int(NumParams))
1240 return false;
1241 // The linear step parameter must be marked as uniform.
1242 if (Parameters[Parameters[Pos].LinearStepOrPos].ParamKind !=
1243 VFParamKind::OMP_Uniform)
1244 return false;
1245 // The linear step parameter can't point at itself.
1246 if (Parameters[Pos].LinearStepOrPos == int(Pos))
1247 return false;
1248 break;
1249 case VFParamKind::GlobalPredicate:
1250 // The global predicate must be the unique. Can be placed anywhere in the
1251 // signature.
1252 for (unsigned NextPos = Pos + 1; NextPos < NumParams; ++NextPos)
1253 if (Parameters[NextPos].ParamKind == VFParamKind::GlobalPredicate)
1254 return false;
1255 break;
1256 }
1257 }
1258 return true;
1259}

/usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/bits/stl_iterator.h

1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_iterator.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{iterator}
54 *
55 * This file implements reverse_iterator, back_insert_iterator,
56 * front_insert_iterator, insert_iterator, __normal_iterator, and their
57 * supporting functions and overloaded operators.
58 */
59
60#ifndef _STL_ITERATOR_H1
61#define _STL_ITERATOR_H1 1
62
63#include <bits/cpp_type_traits.h>
64#include <ext/type_traits.h>
65#include <bits/move.h>
66#include <bits/ptr_traits.h>
67
68namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
69{
70_GLIBCXX_BEGIN_NAMESPACE_VERSION
71
72 /**
73 * @addtogroup iterators
74 * @{
75 */
76
77 // 24.4.1 Reverse iterators
78 /**
79 * Bidirectional and random access iterators have corresponding reverse
80 * %iterator adaptors that iterate through the data structure in the
81 * opposite direction. They have the same signatures as the corresponding
82 * iterators. The fundamental relation between a reverse %iterator and its
83 * corresponding %iterator @c i is established by the identity:
84 * @code
85 * &*(reverse_iterator(i)) == &*(i - 1)
86 * @endcode
87 *
88 * <em>This mapping is dictated by the fact that while there is always a
89 * pointer past the end of an array, there might not be a valid pointer
90 * before the beginning of an array.</em> [24.4.1]/1,2
91 *
92 * Reverse iterators can be tricky and surprising at first. Their
93 * semantics make sense, however, and the trickiness is a side effect of
94 * the requirement that the iterators must be safe.
95 */
96 template<typename _Iterator>
97 class reverse_iterator
98 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
99 typename iterator_traits<_Iterator>::value_type,
100 typename iterator_traits<_Iterator>::difference_type,
101 typename iterator_traits<_Iterator>::pointer,
102 typename iterator_traits<_Iterator>::reference>
103 {
104 protected:
105 _Iterator current;
106
107 typedef iterator_traits<_Iterator> __traits_type;
108
109 public:
110 typedef _Iterator iterator_type;
111 typedef typename __traits_type::difference_type difference_type;
112 typedef typename __traits_type::pointer pointer;
113 typedef typename __traits_type::reference reference;
114
115 /**
116 * The default constructor value-initializes member @p current.
117 * If it is a pointer, that means it is zero-initialized.
118 */
119 // _GLIBCXX_RESOLVE_LIB_DEFECTS
120 // 235 No specification of default ctor for reverse_iterator
121 reverse_iterator() : current() { }
122
123 /**
124 * This %iterator will move in the opposite direction that @p x does.
125 */
126 explicit
127 reverse_iterator(iterator_type __x) : current(__x) { }
128
129 /**
130 * The copy constructor is normal.
131 */
132 reverse_iterator(const reverse_iterator& __x)
133 : current(__x.current) { }
134
135 /**
136 * A %reverse_iterator across other types can be copied if the
137 * underlying %iterator can be converted to the type of @c current.
138 */
139 template<typename _Iter>
140 reverse_iterator(const reverse_iterator<_Iter>& __x)
141 : current(__x.base()) { }
142
143 /**
144 * @return @c current, the %iterator used for underlying work.
145 */
146 iterator_type
147 base() const
148 { return current; }
149
150 /**
151 * @return A reference to the value at @c --current
152 *
153 * This requires that @c --current is dereferenceable.
154 *
155 * @warning This implementation requires that for an iterator of the
156 * underlying iterator type, @c x, a reference obtained by
157 * @c *x remains valid after @c x has been modified or
158 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
159 */
160 reference
161 operator*() const
162 {
163 _Iterator __tmp = current;
164 return *--__tmp;
165 }
166
167 /**
168 * @return A pointer to the value at @c --current
169 *
170 * This requires that @c --current is dereferenceable.
171 */
172 pointer
173 operator->() const
174 { return &(operator*()); }
175
176 /**
177 * @return @c *this
178 *
179 * Decrements the underlying iterator.
180 */
181 reverse_iterator&
182 operator++()
183 {
184 --current;
185 return *this;
186 }
187
188 /**
189 * @return The original value of @c *this
190 *
191 * Decrements the underlying iterator.
192 */
193 reverse_iterator
194 operator++(int)
195 {
196 reverse_iterator __tmp = *this;
197 --current;
198 return __tmp;
199 }
200
201 /**
202 * @return @c *this
203 *
204 * Increments the underlying iterator.
205 */
206 reverse_iterator&
207 operator--()
208 {
209 ++current;
210 return *this;
211 }
212
213 /**
214 * @return A reverse_iterator with the previous value of @c *this
215 *
216 * Increments the underlying iterator.
217 */
218 reverse_iterator
219 operator--(int)
220 {
221 reverse_iterator __tmp = *this;
222 ++current;
223 return __tmp;
224 }
225
226 /**
227 * @return A reverse_iterator that refers to @c current - @a __n
228 *
229 * The underlying iterator must be a Random Access Iterator.
230 */
231 reverse_iterator
232 operator+(difference_type __n) const
233 { return reverse_iterator(current - __n); }
234
235 /**
236 * @return *this
237 *
238 * Moves the underlying iterator backwards @a __n steps.
239 * The underlying iterator must be a Random Access Iterator.
240 */
241 reverse_iterator&
242 operator+=(difference_type __n)
243 {
244 current -= __n;
245 return *this;
246 }
247
248 /**
249 * @return A reverse_iterator that refers to @c current - @a __n
250 *
251 * The underlying iterator must be a Random Access Iterator.
252 */
253 reverse_iterator
254 operator-(difference_type __n) const
255 { return reverse_iterator(current + __n); }
256
257 /**
258 * @return *this
259 *
260 * Moves the underlying iterator forwards @a __n steps.
261 * The underlying iterator must be a Random Access Iterator.
262 */
263 reverse_iterator&
264 operator-=(difference_type __n)
265 {
266 current += __n;
267 return *this;
268 }
269
270 /**
271 * @return The value at @c current - @a __n - 1
272 *
273 * The underlying iterator must be a Random Access Iterator.
274 */
275 reference
276 operator[](difference_type __n) const
277 { return *(*this + __n); }
278 };
279
280 //@{
281 /**
282 * @param __x A %reverse_iterator.
283 * @param __y A %reverse_iterator.
284 * @return A simple bool.
285 *
286 * Reverse iterators forward many operations to their underlying base()
287 * iterators. Others are implemented in terms of one another.
288 *
289 */
290 template<typename _Iterator>
291 inline bool
292 operator==(const reverse_iterator<_Iterator>& __x,
293 const reverse_iterator<_Iterator>& __y)
294 { return __x.base() == __y.base(); }
7
Calling 'operator==<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > >>'
10
Returning from 'operator==<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > >>'
11
Returning zero, which participates in a condition later
19
Calling 'operator==<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > >>'
22
Returning from 'operator==<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > >>'
23
Returning zero, which participates in a condition later
37
Calling 'operator==<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > >>'
40
Returning from 'operator==<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > >>'
41
Returning zero, which participates in a condition later
295
296 template<typename _Iterator>
297 inline bool
298 operator<(const reverse_iterator<_Iterator>& __x,
299 const reverse_iterator<_Iterator>& __y)
300 { return __y.base() < __x.base(); }
301
302 template<typename _Iterator>
303 inline bool
304 operator!=(const reverse_iterator<_Iterator>& __x,
305 const reverse_iterator<_Iterator>& __y)
306 { return !(__x == __y); }
6
Calling 'operator==<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
12
Returning from 'operator==<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
13
Returning the value 1, which participates in a condition later
18
Calling 'operator==<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
24
Returning from 'operator==<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
25
Returning the value 1, which participates in a condition later
36
Calling 'operator==<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
42
Returning from 'operator==<__gnu_cxx::__normal_iterator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> *, std::vector<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor>, std::allocator<std::pair<llvm::Instruction *, llvm::InterleavedAccessInfo::StrideDescriptor> > > >>'
43
Returning the value 1, which participates in a condition later
307
308 template<typename _Iterator>
309 inline bool
310 operator>(const reverse_iterator<_Iterator>& __x,
311 const reverse_iterator<_Iterator>& __y)
312 { return __y < __x; }
313
314 template<typename _Iterator>
315 inline bool
316 operator<=(const reverse_iterator<_Iterator>& __x,
317 const reverse_iterator<_Iterator>& __y)
318 { return !(__y < __x); }
319
320 template<typename _Iterator>
321 inline bool
322 operator>=(const reverse_iterator<_Iterator>& __x,
323 const reverse_iterator<_Iterator>& __y)
324 { return !(__x < __y); }
325
326 template<typename _Iterator>
327#if __cplusplus201402L < 201103L
328 inline typename reverse_iterator<_Iterator>::difference_type
329 operator-(const reverse_iterator<_Iterator>& __x,
330 const reverse_iterator<_Iterator>& __y)
331#else
332 inline auto
333 operator-(const reverse_iterator<_Iterator>& __x,
334 const reverse_iterator<_Iterator>& __y)
335 -> decltype(__x.base() - __y.base())
336#endif
337 { return __y.base() - __x.base(); }
338
339 template<typename _Iterator>
340 inline reverse_iterator<_Iterator>
341 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
342 const reverse_iterator<_Iterator>& __x)
343 { return reverse_iterator<_Iterator>(__x.base() - __n); }
344
345 // _GLIBCXX_RESOLVE_LIB_DEFECTS
346 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
347 template<typename _IteratorL, typename _IteratorR>
348 inline bool
349 operator==(const reverse_iterator<_IteratorL>& __x,
350 const reverse_iterator<_IteratorR>& __y)
351 { return __x.base() == __y.base(); }
352
353 template<typename _IteratorL, typename _IteratorR>
354 inline bool
355 operator<(const reverse_iterator<_IteratorL>& __x,
356 const reverse_iterator<_IteratorR>& __y)
357 { return __y.base() < __x.base(); }
358
359 template<typename _IteratorL, typename _IteratorR>
360 inline bool
361 operator!=(const reverse_iterator<_IteratorL>& __x,
362 const reverse_iterator<_IteratorR>& __y)
363 { return !(__x == __y); }
364
365 template<typename _IteratorL, typename _IteratorR>
366 inline bool
367 operator>(const reverse_iterator<_IteratorL>& __x,
368 const reverse_iterator<_IteratorR>& __y)
369 { return __y < __x; }
370
371 template<typename _IteratorL, typename _IteratorR>
372 inline bool
373 operator<=(const reverse_iterator<_IteratorL>& __x,
374 const reverse_iterator<_IteratorR>& __y)
375 { return !(__y < __x); }
376
377 template<typename _IteratorL, typename _IteratorR>
378 inline bool
379 operator>=(const reverse_iterator<_IteratorL>& __x,
380 const reverse_iterator<_IteratorR>& __y)
381 { return !(__x < __y); }
382
383 template<typename _IteratorL, typename _IteratorR>
384#if __cplusplus201402L >= 201103L
385 // DR 685.
386 inline auto
387 operator-(const reverse_iterator<_IteratorL>& __x,
388 const reverse_iterator<_IteratorR>& __y)
389 -> decltype(__y.base() - __x.base())
390#else
391 inline typename reverse_iterator<_IteratorL>::difference_type
392 operator-(const reverse_iterator<_IteratorL>& __x,
393 const reverse_iterator<_IteratorR>& __y)
394#endif
395 { return __y.base() - __x.base(); }
396 //@}
397
398#if __cplusplus201402L >= 201103L
399 // Same as C++14 make_reverse_iterator but used in C++03 mode too.
400 template<typename _Iterator>
401 inline reverse_iterator<_Iterator>
402 __make_reverse_iterator(_Iterator __i)
403 { return reverse_iterator<_Iterator>(__i); }
404
405# if __cplusplus201402L > 201103L
406# define __cpp_lib_make_reverse_iterator201402 201402
407
408 // _GLIBCXX_RESOLVE_LIB_DEFECTS
409 // DR 2285. make_reverse_iterator
410 /// Generator function for reverse_iterator.
411 template<typename _Iterator>
412 inline reverse_iterator<_Iterator>
413 make_reverse_iterator(_Iterator __i)
414 { return reverse_iterator<_Iterator>(__i); }
415# endif
416#endif
417
418#if __cplusplus201402L >= 201103L
419 template<typename _Iterator>
420 auto
421 __niter_base(reverse_iterator<_Iterator> __it)
422 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
423 { return __make_reverse_iterator(__niter_base(__it.base())); }
424
425 template<typename _Iterator>
426 struct __is_move_iterator<reverse_iterator<_Iterator> >
427 : __is_move_iterator<_Iterator>
428 { };
429
430 template<typename _Iterator>
431 auto
432 __miter_base(reverse_iterator<_Iterator> __it)
433 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
434 { return __make_reverse_iterator(__miter_base(__it.base())); }
435#endif
436
437 // 24.4.2.2.1 back_insert_iterator
438 /**
439 * @brief Turns assignment into insertion.
440 *
441 * These are output iterators, constructed from a container-of-T.
442 * Assigning a T to the iterator appends it to the container using
443 * push_back.
444 *
445 * Tip: Using the back_inserter function to create these iterators can
446 * save typing.
447 */
448 template<typename _Container>
449 class back_insert_iterator
450 : public iterator<output_iterator_tag, void, void, void, void>
451 {
452 protected:
453 _Container* container;
454
455 public:
456 /// A nested typedef for the type of whatever container you used.
457 typedef _Container container_type;
458
459 /// The only way to create this %iterator is with a container.
460 explicit
461 back_insert_iterator(_Container& __x)
462 : container(std::__addressof(__x)) { }
463
464 /**
465 * @param __value An instance of whatever type
466 * container_type::const_reference is; presumably a
467 * reference-to-const T for container<T>.
468 * @return This %iterator, for chained operations.
469 *
470 * This kind of %iterator doesn't really have a @a position in the
471 * container (you can think of the position as being permanently at
472 * the end, if you like). Assigning a value to the %iterator will
473 * always append the value to the end of the container.
474 */
475#if __cplusplus201402L < 201103L
476 back_insert_iterator&
477 operator=(typename _Container::const_reference __value)
478 {
479 container->push_back(__value);
480 return *this;
481 }
482#else
483 back_insert_iterator&
484 operator=(const typename _Container::value_type& __value)
485 {
486 container->push_back(__value);
487 return *this;
488 }
489
490 back_insert_iterator&
491 operator=(typename _Container::value_type&& __value)
492 {
493 container->push_back(std::move(__value));
494 return *this;
495 }
496#endif
497
498 /// Simply returns *this.
499 back_insert_iterator&
500 operator*()
501 { return *this; }
502
503 /// Simply returns *this. (This %iterator does not @a move.)
504 back_insert_iterator&
505 operator++()
506 { return *this; }
507
508 /// Simply returns *this. (This %iterator does not @a move.)
509 back_insert_iterator
510 operator++(int)
511 { return *this; }
512 };
513
514 /**
515 * @param __x A container of arbitrary type.
516 * @return An instance of back_insert_iterator working on @p __x.
517 *
518 * This wrapper function helps in creating back_insert_iterator instances.
519 * Typing the name of the %iterator requires knowing the precise full
520 * type of the container, which can be tedious and impedes generic
521 * programming. Using this function lets you take advantage of automatic
522 * template parameter deduction, making the compiler match the correct
523 * types for you.
524 */
525 template<typename _Container>
526 inline back_insert_iterator<_Container>
527 back_inserter(_Container& __x)
528 { return back_insert_iterator<_Container>(__x); }
529
530 /**
531 * @brief Turns assignment into insertion.
532 *
533 * These are output iterators, constructed from a container-of-T.
534 * Assigning a T to the iterator prepends it to the container using
535 * push_front.
536 *
537 * Tip: Using the front_inserter function to create these iterators can
538 * save typing.
539 */
540 template<typename _Container>
541 class front_insert_iterator
542 : public iterator<output_iterator_tag, void, void, void, void>
543 {
544 protected:
545 _Container* container;
546
547 public:
548 /// A nested typedef for the type of whatever container you used.
549 typedef _Container container_type;
550
551 /// The only way to create this %iterator is with a container.
552 explicit front_insert_iterator(_Container& __x)
553 : container(std::__addressof(__x)) { }
554
555 /**
556 * @param __value An instance of whatever type
557 * container_type::const_reference is; presumably a
558 * reference-to-const T for container<T>.
559 * @return This %iterator, for chained operations.
560 *
561 * This kind of %iterator doesn't really have a @a position in the
562 * container (you can think of the position as being permanently at
563 * the front, if you like). Assigning a value to the %iterator will
564 * always prepend the value to the front of the container.
565 */
566#if __cplusplus201402L < 201103L
567 front_insert_iterator&
568 operator=(typename _Container::const_reference __value)
569 {
570 container->push_front(__value);
571 return *this;
572 }
573#else
574 front_insert_iterator&
575 operator=(const typename _Container::value_type& __value)
576 {
577 container->push_front(__value);
578 return *this;
579 }
580
581 front_insert_iterator&
582 operator=(typename _Container::value_type&& __value)
583 {
584 container->push_front(std::move(__value));
585 return *this;
586 }
587#endif
588
589 /// Simply returns *this.
590 front_insert_iterator&
591 operator*()
592 { return *this; }
593
594 /// Simply returns *this. (This %iterator does not @a move.)
595 front_insert_iterator&
596 operator++()
597 { return *this; }
598
599 /// Simply returns *this. (This %iterator does not @a move.)
600 front_insert_iterator
601 operator++(int)
602 { return *this; }
603 };
604
605 /**
606 * @param __x A container of arbitrary type.
607 * @return An instance of front_insert_iterator working on @p x.
608 *
609 * This wrapper function helps in creating front_insert_iterator instances.
610 * Typing the name of the %iterator requires knowing the precise full
611 * type of the container, which can be tedious and impedes generic
612 * programming. Using this function lets you take advantage of automatic
613 * template parameter deduction, making the compiler match the correct
614 * types for you.
615 */
616 template<typename _Container>
617 inline front_insert_iterator<_Container>
618 front_inserter(_Container& __x)
619 { return front_insert_iterator<_Container>(__x); }
620
621 /**
622 * @brief Turns assignment into insertion.
623 *
624 * These are output iterators, constructed from a container-of-T.
625 * Assigning a T to the iterator inserts it in the container at the
626 * %iterator's position, rather than overwriting the value at that
627 * position.
628 *
629 * (Sequences will actually insert a @e copy of the value before the
630 * %iterator's position.)
631 *
632 * Tip: Using the inserter function to create these iterators can
633 * save typing.
634 */
635 template<typename _Container>
636 class insert_iterator
637 : public iterator<output_iterator_tag, void, void, void, void>
638 {
639 protected:
640 _Container* container;
641 typename _Container::iterator iter;
642
643 public:
644 /// A nested typedef for the type of whatever container you used.
645 typedef _Container container_type;
646
647 /**
648 * The only way to create this %iterator is with a container and an
649 * initial position (a normal %iterator into the container).
650 */
651 insert_iterator(_Container& __x, typename _Container::iterator __i)
652 : container(std::__addressof(__x)), iter(__i) {}
653
654 /**
655 * @param __value An instance of whatever type
656 * container_type::const_reference is; presumably a
657 * reference-to-const T for container<T>.
658 * @return This %iterator, for chained operations.
659 *
660 * This kind of %iterator maintains its own position in the
661 * container. Assigning a value to the %iterator will insert the
662 * value into the container at the place before the %iterator.
663 *
664 * The position is maintained such that subsequent assignments will
665 * insert values immediately after one another. For example,
666 * @code
667 * // vector v contains A and Z
668 *
669 * insert_iterator i (v, ++v.begin());
670 * i = 1;
671 * i = 2;
672 * i = 3;
673 *
674 * // vector v contains A, 1, 2, 3, and Z
675 * @endcode
676 */
677#if __cplusplus201402L < 201103L
678 insert_iterator&
679 operator=(typename _Container::const_reference __value)
680 {
681 iter = container->insert(iter, __value);
682 ++iter;
683 return *this;
684 }
685#else
686 insert_iterator&
687 operator=(const typename _Container::value_type& __value)
688 {
689 iter = container->insert(iter, __value);
690 ++iter;
691 return *this;
692 }
693
694 insert_iterator&
695 operator=(typename _Container::value_type&& __value)
696 {
697 iter = container->insert(iter, std::move(__value));
698 ++iter;
699 return *this;
700 }
701#endif
702
703 /// Simply returns *this.
704 insert_iterator&
705 operator*()
706 { return *this; }
707
708 /// Simply returns *this. (This %iterator does not @a move.)
709 insert_iterator&
710 operator++()
711 { return *this; }
712
713 /// Simply returns *this. (This %iterator does not @a move.)
714 insert_iterator&
715 operator++(int)
716 { return *this; }
717 };
718
719 /**
720 * @param __x A container of arbitrary type.
721 * @return An instance of insert_iterator working on @p __x.
722 *
723 * This wrapper function helps in creating insert_iterator instances.
724 * Typing the name of the %iterator requires knowing the precise full
725 * type of the container, which can be tedious and impedes generic
726 * programming. Using this function lets you take advantage of automatic
727 * template parameter deduction, making the compiler match the correct
728 * types for you.
729 */
730 template<typename _Container, typename _Iterator>
731 inline insert_iterator<_Container>
732 inserter(_Container& __x, _Iterator __i)
733 {
734 return insert_iterator<_Container>(__x,
735 typename _Container::iterator(__i));
736 }
737
738 // @} group iterators
739
740_GLIBCXX_END_NAMESPACE_VERSION
741} // namespace
742
743namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
744{
745_GLIBCXX_BEGIN_NAMESPACE_VERSION
746
747 // This iterator adapter is @a normal in the sense that it does not
748 // change the semantics of any of the operators of its iterator
749 // parameter. Its primary purpose is to convert an iterator that is
750 // not a class, e.g. a pointer, into an iterator that is a class.
751 // The _Container parameter exists solely so that different containers
752 // using this template can instantiate different types, even if the
753 // _Iterator parameter is the same.
754 using std::iterator_traits;
755 using std::iterator;
756 template<typename _Iterator, typename _Container>
757 class __normal_iterator
758 {
759 protected:
760 _Iterator _M_current;
761
762 typedef iterator_traits<_Iterator> __traits_type;
763
764 public:
765 typedef _Iterator iterator_type;
766 typedef typename __traits_type::iterator_category iterator_category;
767 typedef typename __traits_type::value_type value_type;
768 typedef typename __traits_type::difference_type difference_type;
769 typedef typename __traits_type::reference reference;
770 typedef typename __traits_type::pointer pointer;
771
772 _GLIBCXX_CONSTEXPRconstexpr __normal_iterator() _GLIBCXX_NOEXCEPTnoexcept
773 : _M_current(_Iterator()) { }
774
775 explicit
776 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPTnoexcept
777 : _M_current(__i) { }
778
779 // Allow iterator to const_iterator conversion
780 template<typename _Iter>
781 __normal_iterator(const __normal_iterator<_Iter,
782 typename __enable_if<
783 (std::__are_same<_Iter, typename _Container::pointer>::__value),
784 _Container>::__type>& __i) _GLIBCXX_NOEXCEPTnoexcept
785 : _M_current(__i.base()) { }
786
787 // Forward iterator requirements
788 reference
789 operator*() const _GLIBCXX_NOEXCEPTnoexcept
790 { return *_M_current; }
791
792 pointer
793 operator->() const _GLIBCXX_NOEXCEPTnoexcept
794 { return _M_current; }
795
796 __normal_iterator&
797 operator++() _GLIBCXX_NOEXCEPTnoexcept
798 {
799 ++_M_current;
800 return *this;
801 }
802
803 __normal_iterator
804 operator++(int) _GLIBCXX_NOEXCEPTnoexcept
805 { return __normal_iterator(_M_current++); }
806
807 // Bidirectional iterator requirements
808 __normal_iterator&
809 operator--() _GLIBCXX_NOEXCEPTnoexcept
810 {
811 --_M_current;
812 return *this;
813 }
814
815 __normal_iterator
816 operator--(int) _GLIBCXX_NOEXCEPTnoexcept
817 { return __normal_iterator(_M_current--); }
818
819 // Random access iterator requirements
820 reference
821 operator[](difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
822 { return _M_current[__n]; }
823
824 __normal_iterator&
825 operator+=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
826 { _M_current += __n; return *this; }
827
828 __normal_iterator
829 operator+(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
830 { return __normal_iterator(_M_current + __n); }
831
832 __normal_iterator&
833 operator-=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
834 { _M_current -= __n; return *this; }
835
836 __normal_iterator
837 operator-(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
838 { return __normal_iterator(_M_current - __n); }
839
840 const _Iterator&
841 base() const _GLIBCXX_NOEXCEPTnoexcept
842 { return _M_current; }
843 };
844
845 // Note: In what follows, the left- and right-hand-side iterators are
846 // allowed to vary in types (conceptually in cv-qualification) so that
847 // comparison between cv-qualified and non-cv-qualified iterators be
848 // valid. However, the greedy and unfriendly operators in std::rel_ops
849 // will make overload resolution ambiguous (when in scope) if we don't
850 // provide overloads whose operands are of the same type. Can someone
851 // remind me what generic programming is about? -- Gaby
852
853 // Forward iterator requirements
854 template<typename _IteratorL, typename _IteratorR, typename _Container>
855 inline bool
856 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
857 const __normal_iterator<_IteratorR, _Container>& __rhs)
858 _GLIBCXX_NOEXCEPTnoexcept
859 { return __lhs.base() == __rhs.base(); }
860
861 template<typename _Iterator, typename _Container>
862 inline bool
863 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
864 const __normal_iterator<_Iterator, _Container>& __rhs)
865 _GLIBCXX_NOEXCEPTnoexcept
866 { return __lhs.base() == __rhs.base(); }
8
Assuming the condition is false
9
Returning zero, which participates in a condition later
20
Assuming the condition is false
21
Returning zero, which participates in a condition later
38
Assuming the condition is false
39
Returning zero, which participates in a condition later
867
868 template<typename _IteratorL, typename _IteratorR, typename _Container>
869 inline bool
870 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
871 const __normal_iterator<_IteratorR, _Container>& __rhs)
872 _GLIBCXX_NOEXCEPTnoexcept
873 { return __lhs.base() != __rhs.base(); }
874
875 template<typename _Iterator, typename _Container>
876 inline bool
877 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
878 const __normal_iterator<_Iterator, _Container>& __rhs)
879 _GLIBCXX_NOEXCEPTnoexcept
880 { return __lhs.base() != __rhs.base(); }
881
882 // Random access iterator requirements
883 template<typename _IteratorL, typename _IteratorR, typename _Container>
884 inline bool
885 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
886 const __normal_iterator<_IteratorR, _Container>& __rhs)
887 _GLIBCXX_NOEXCEPTnoexcept
888 { return __lhs.base() < __rhs.base(); }
889
890 template<typename _Iterator, typename _Container>
891 inline bool
892 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
893 const __normal_iterator<_Iterator, _Container>& __rhs)
894 _GLIBCXX_NOEXCEPTnoexcept
895 { return __lhs.base() < __rhs.base(); }
896
897 template<typename _IteratorL, typename _IteratorR, typename _Container>
898 inline bool
899 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
900 const __normal_iterator<_IteratorR, _Container>& __rhs)
901 _GLIBCXX_NOEXCEPTnoexcept
902 { return __lhs.base() > __rhs.base(); }
903
904 template<typename _Iterator, typename _Container>
905 inline bool
906 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
907 const __normal_iterator<_Iterator, _Container>& __rhs)
908 _GLIBCXX_NOEXCEPTnoexcept
909 { return __lhs.base() > __rhs.base(); }
910
911 template<typename _IteratorL, typename _IteratorR, typename _Container>
912 inline bool
913 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
914 const __normal_iterator<_IteratorR, _Container>& __rhs)
915 _GLIBCXX_NOEXCEPTnoexcept
916 { return __lhs.base() <= __rhs.base(); }
917
918 template<typename _Iterator, typename _Container>
919 inline bool
920 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
921 const __normal_iterator<_Iterator, _Container>& __rhs)
922 _GLIBCXX_NOEXCEPTnoexcept
923 { return __lhs.base() <= __rhs.base(); }
924
925 template<typename _IteratorL, typename _IteratorR, typename _Container>
926 inline bool
927 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
928 const __normal_iterator<_IteratorR, _Container>& __rhs)
929 _GLIBCXX_NOEXCEPTnoexcept
930 { return __lhs.base() >= __rhs.base(); }
931
932 template<typename _Iterator, typename _Container>
933 inline bool
934 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
935 const __normal_iterator<_Iterator, _Container>& __rhs)
936 _GLIBCXX_NOEXCEPTnoexcept
937 { return __lhs.base() >= __rhs.base(); }
938
939 // _GLIBCXX_RESOLVE_LIB_DEFECTS
940 // According to the resolution of DR179 not only the various comparison
941 // operators but also operator- must accept mixed iterator/const_iterator
942 // parameters.
943 template<typename _IteratorL, typename _IteratorR, typename _Container>
944#if __cplusplus201402L >= 201103L
945 // DR 685.
946 inline auto
947 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
948 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
949 -> decltype(__lhs.base() - __rhs.base())
950#else
951 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
952 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
953 const __normal_iterator<_IteratorR, _Container>& __rhs)
954#endif
955 { return __lhs.base() - __rhs.base(); }
956
957 template<typename _Iterator, typename _Container>
958 inline typename __normal_iterator<_Iterator, _Container>::difference_type
959 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
960 const __normal_iterator<_Iterator, _Container>& __rhs)
961 _GLIBCXX_NOEXCEPTnoexcept
962 { return __lhs.base() - __rhs.base(); }
963
964 template<typename _Iterator, typename _Container>
965 inline __normal_iterator<_Iterator, _Container>
966 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
967 __n, const __normal_iterator<_Iterator, _Container>& __i)
968 _GLIBCXX_NOEXCEPTnoexcept
969 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
970
971_GLIBCXX_END_NAMESPACE_VERSION
972} // namespace
973
974namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
975{
976_GLIBCXX_BEGIN_NAMESPACE_VERSION
977
978 template<typename _Iterator, typename _Container>
979 _Iterator
980 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
981 { return __it.base(); }
982
983_GLIBCXX_END_NAMESPACE_VERSION
984} // namespace
985
986#if __cplusplus201402L >= 201103L
987
988namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
989{
990_GLIBCXX_BEGIN_NAMESPACE_VERSION
991
992 /**
993 * @addtogroup iterators
994 * @{
995 */
996
997 // 24.4.3 Move iterators
998 /**
999 * Class template move_iterator is an iterator adapter with the same
1000 * behavior as the underlying iterator except that its dereference
1001 * operator implicitly converts the value returned by the underlying
1002 * iterator's dereference operator to an rvalue reference. Some
1003 * generic algorithms can be called with move iterators to replace
1004 * copying with moving.
1005 */
1006 template<typename _Iterator>
1007 class move_iterator
1008 {
1009 protected:
1010 _Iterator _M_current;
1011
1012 typedef iterator_traits<_Iterator> __traits_type;
1013 typedef typename __traits_type::reference __base_ref;
1014
1015 public:
1016 typedef _Iterator iterator_type;
1017 typedef typename __traits_type::iterator_category iterator_category;
1018 typedef typename __traits_type::value_type value_type;
1019 typedef typename __traits_type::difference_type difference_type;
1020 // NB: DR 680.
1021 typedef _Iterator pointer;
1022 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1023 // 2106. move_iterator wrapping iterators returning prvalues
1024 typedef typename conditional<is_reference<__base_ref>::value,
1025 typename remove_reference<__base_ref>::type&&,
1026 __base_ref>::type reference;
1027
1028 move_iterator()
1029 : _M_current() { }
1030
1031 explicit
1032 move_iterator(iterator_type __i)
1033 : _M_current(__i) { }
1034
1035 template<typename _Iter>
1036 move_iterator(const move_iterator<_Iter>& __i)
1037 : _M_current(__i.base()) { }
1038
1039 iterator_type
1040 base() const
1041 { return _M_current; }
1042
1043 reference
1044 operator*() const
1045 { return static_cast<reference>(*_M_current); }
1046
1047 pointer
1048 operator->() const
1049 { return _M_current; }
1050
1051 move_iterator&
1052 operator++()
1053 {
1054 ++_M_current;
1055 return *this;
1056 }
1057
1058 move_iterator
1059 operator++(int)
1060 {
1061 move_iterator __tmp = *this;
1062 ++_M_current;
1063 return __tmp;
1064 }
1065
1066 move_iterator&
1067 operator--()
1068 {
1069 --_M_current;
1070 return *this;
1071 }
1072
1073 move_iterator
1074 operator--(int)
1075 {
1076 move_iterator __tmp = *this;
1077 --_M_current;
1078 return __tmp;
1079 }
1080
1081 move_iterator
1082 operator+(difference_type __n) const
1083 { return move_iterator(_M_current + __n); }
1084
1085 move_iterator&
1086 operator+=(difference_type __n)
1087 {
1088 _M_current += __n;
1089 return *this;
1090 }
1091
1092 move_iterator
1093 operator-(difference_type __n) const
1094 { return move_iterator(_M_current - __n); }
1095
1096 move_iterator&
1097 operator-=(difference_type __n)
1098 {
1099 _M_current -= __n;
1100 return *this;
1101 }
1102
1103 reference
1104 operator[](difference_type __n) const
1105 { return std::move(_M_current[__n]); }
1106 };
1107
1108 // Note: See __normal_iterator operators note from Gaby to understand
1109 // why there are always 2 versions for most of the move_iterator
1110 // operators.
1111 template<typename _IteratorL, typename _IteratorR>
1112 inline bool
1113 operator==(const move_iterator<_IteratorL>& __x,
1114 const move_iterator<_IteratorR>& __y)
1115 { return __x.base() == __y.base(); }
1116
1117 template<typename _Iterator>
1118 inline bool
1119 operator==(const move_iterator<_Iterator>& __x,
1120 const move_iterator<_Iterator>& __y)
1121 { return __x.base() == __y.base(); }
1122
1123 template<typename _IteratorL, typename _IteratorR>
1124 inline bool
1125 operator!=(const move_iterator<_IteratorL>& __x,
1126 const move_iterator<_IteratorR>& __y)
1127 { return !(__x == __y); }
1128
1129 template<typename _Iterator>
1130 inline bool
1131 operator!=(const move_iterator<_Iterator>& __x,
1132 const move_iterator<_Iterator>& __y)
1133 { return !(__x == __y); }
1134
1135 template<typename _IteratorL, typename _IteratorR>
1136 inline bool
1137 operator<(const move_iterator<_IteratorL>& __x,
1138 const move_iterator<_IteratorR>& __y)
1139 { return __x.base() < __y.base(); }
1140
1141 template<typename _Iterator>
1142 inline bool
1143 operator<(const move_iterator<_Iterator>& __x,
1144 const move_iterator<_Iterator>& __y)
1145 { return __x.base() < __y.base(); }
1146
1147 template<typename _IteratorL, typename _IteratorR>
1148 inline bool
1149 operator<=(const move_iterator<_IteratorL>& __x,
1150 const move_iterator<_IteratorR>& __y)
1151 { return !(__y < __x); }
1152
1153 template<typename _Iterator>
1154 inline bool
1155 operator<=(const move_iterator<_Iterator>& __x,
1156 const move_iterator<_Iterator>& __y)
1157 { return !(__y < __x); }
1158
1159 template<typename _IteratorL, typename _IteratorR>
1160 inline bool
1161 operator>(const move_iterator<_IteratorL>& __x,
1162 const move_iterator<_IteratorR>& __y)
1163 { return __y < __x; }
1164
1165 template<typename _Iterator>
1166 inline bool
1167 operator>(const move_iterator<_Iterator>& __x,
1168 const move_iterator<_Iterator>& __y)
1169 { return __y < __x; }
1170
1171 template<typename _IteratorL, typename _IteratorR>
1172 inline bool
1173 operator>=(const move_iterator<_IteratorL>& __x,
1174 const move_iterator<_IteratorR>& __y)
1175 { return !(__x < __y); }
1176
1177 template<typename _Iterator>
1178 inline bool
1179 operator>=(const move_iterator<_Iterator>& __x,
1180 const move_iterator<_Iterator>& __y)
1181 { return !(__x < __y); }
1182
1183 // DR 685.
1184 template<typename _IteratorL, typename _IteratorR>
1185 inline auto
1186 operator-(const move_iterator<_IteratorL>& __x,
1187 const move_iterator<_IteratorR>& __y)
1188 -> decltype(__x.base() - __y.base())
1189 { return __x.base() - __y.base(); }
1190
1191 template<typename _Iterator>
1192 inline auto
1193 operator-(const move_iterator<_Iterator>& __x,
1194 const move_iterator<_Iterator>& __y)
1195 -> decltype(__x.base() - __y.base())
1196 { return __x.base() - __y.base(); }
1197
1198 template<typename _Iterator>
1199 inline move_iterator<_Iterator>
1200 operator+(typename move_iterator<_Iterator>::difference_type __n,
1201 const move_iterator<_Iterator>& __x)
1202 { return __x + __n; }
1203
1204 template<typename _Iterator>
1205 inline move_iterator<_Iterator>
1206 make_move_iterator(_Iterator __i)
1207 { return move_iterator<_Iterator>(__i); }
1208
1209 template<typename _Iterator, typename _ReturnType
1210 = typename conditional<__move_if_noexcept_cond
1211 <typename iterator_traits<_Iterator>::value_type>::value,
1212 _Iterator, move_iterator<_Iterator>>::type>
1213 inline _ReturnType
1214 __make_move_if_noexcept_iterator(_Iterator __i)
1215 { return _ReturnType(__i); }
1216
1217 // Overload for pointers that matches std::move_if_noexcept more closely,
1218 // returning a constant iterator when we don't want to move.
1219 template<typename _Tp, typename _ReturnType
1220 = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1221 const _Tp*, move_iterator<_Tp*>>::type>
1222 inline _ReturnType
1223 __make_move_if_noexcept_iterator(_Tp* __i)
1224 { return _ReturnType(__i); }
1225
1226 // @} group iterators
1227
1228 template<typename _Iterator>
1229 auto
1230 __niter_base(move_iterator<_Iterator> __it)
1231 -> decltype(make_move_iterator(__niter_base(__it.base())))
1232 { return make_move_iterator(__niter_base(__it.base())); }
1233
1234 template<typename _Iterator>
1235 struct __is_move_iterator<move_iterator<_Iterator> >
1236 {
1237 enum { __value = 1 };
1238 typedef __true_type __type;
1239 };
1240
1241 template<typename _Iterator>
1242 auto
1243 __miter_base(move_iterator<_Iterator> __it)
1244 -> decltype(__miter_base(__it.base()))
1245 { return __miter_base(__it.base()); }
1246
1247_GLIBCXX_END_NAMESPACE_VERSION
1248} // namespace
1249
1250#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) std::make_move_iterator(_Iter)
1251#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) \
1252 std::__make_move_if_noexcept_iterator(_Iter)
1253#else
1254#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) (_Iter)
1255#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) (_Iter)
1256#endif // C++11
1257
1258#ifdef _GLIBCXX_DEBUG
1259# include <debug/stl_iterator.h>
1260#endif
1261
1262#endif

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h

1//===- llvm/Analysis/VectorUtils.h - Vector utilities -----------*- 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 some vectorizer utilities.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ANALYSIS_VECTORUTILS_H
14#define LLVM_ANALYSIS_VECTORUTILS_H
15
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/SmallSet.h"
18#include "llvm/Analysis/LoopAccessAnalysis.h"
19#include "llvm/Analysis/TargetLibraryInfo.h"
20#include "llvm/Support/CheckedArithmetic.h"
21
22namespace llvm {
23
24/// Describes the type of Parameters
25enum class VFParamKind {
26 Vector, // No semantic information.
27 OMP_Linear, // declare simd linear(i)
28 OMP_LinearRef, // declare simd linear(ref(i))
29 OMP_LinearVal, // declare simd linear(val(i))
30 OMP_LinearUVal, // declare simd linear(uval(i))
31 OMP_LinearPos, // declare simd linear(i:c) uniform(c)
32 OMP_LinearValPos, // declare simd linear(val(i:c)) uniform(c)
33 OMP_LinearRefPos, // declare simd linear(ref(i:c)) uniform(c)
34 OMP_LinearUValPos, // declare simd linear(uval(i:c)) uniform(c
35 OMP_Uniform, // declare simd uniform(i)
36 GlobalPredicate, // Global logical predicate that acts on all lanes
37 // of the input and output mask concurrently. For
38 // example, it is implied by the `M` token in the
39 // Vector Function ABI mangled name.
40 Unknown
41};
42
43/// Describes the type of Instruction Set Architecture
44enum class VFISAKind {
45 AdvancedSIMD, // AArch64 Advanced SIMD (NEON)
46 SVE, // AArch64 Scalable Vector Extension
47 SSE, // x86 SSE
48 AVX, // x86 AVX
49 AVX2, // x86 AVX2
50 AVX512, // x86 AVX512
51 LLVM, // LLVM internal ISA for functions that are not
52 // attached to an existing ABI via name mangling.
53 Unknown // Unknown ISA
54};
55
56/// Encapsulates information needed to describe a parameter.
57///
58/// The description of the parameter is not linked directly to
59/// OpenMP or any other vector function description. This structure
60/// is extendible to handle other paradigms that describe vector
61/// functions and their parameters.
62struct VFParameter {
63 unsigned ParamPos; // Parameter Position in Scalar Function.
64 VFParamKind ParamKind; // Kind of Parameter.
65 int LinearStepOrPos = 0; // Step or Position of the Parameter.
66 Align Alignment = Align(); // Optional aligment in bytes, defaulted to 1.
67
68 // Comparison operator.
69 bool operator==(const VFParameter &Other) const {
70 return std::tie(ParamPos, ParamKind, LinearStepOrPos, Alignment) ==
71 std::tie(Other.ParamPos, Other.ParamKind, Other.LinearStepOrPos,
72 Other.Alignment);
73 }
74};
75
76/// Contains the information about the kind of vectorization
77/// available.
78///
79/// This object in independent on the paradigm used to
80/// represent vector functions. in particular, it is not attached to
81/// any target-specific ABI.
82struct VFShape {
83 unsigned VF; // Vectorization factor.
84 bool IsScalable; // True if the function is a scalable function.
85 SmallVector<VFParameter, 8> Parameters; // List of parameter informations.
86 // Comparison operator.
87 bool operator==(const VFShape &Other) const {
88 return std::tie(VF, IsScalable, Parameters) ==
89 std::tie(Other.VF, Other.IsScalable, Other.Parameters);
90 }
91
92 /// Update the parameter in position P.ParamPos to P.
93 void updateParam(VFParameter P) {
94 assert(P.ParamPos < Parameters.size() && "Invalid parameter position.")((P.ParamPos < Parameters.size() && "Invalid parameter position."
) ? static_cast<void> (0) : __assert_fail ("P.ParamPos < Parameters.size() && \"Invalid parameter position.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 94, __PRETTY_FUNCTION__))
;
95 Parameters[P.ParamPos] = P;
96 assert(hasValidParameterList() && "Invalid parameter list")((hasValidParameterList() && "Invalid parameter list"
) ? static_cast<void> (0) : __assert_fail ("hasValidParameterList() && \"Invalid parameter list\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 96, __PRETTY_FUNCTION__))
;
97 }
98
99 // Retrieve the basic vectorization shape of the function, where all
100 // parameters are mapped to VFParamKind::Vector with \p EC
101 // lanes. Specifies whether the function has a Global Predicate
102 // argument via \p HasGlobalPred.
103 static VFShape get(const CallInst &CI, ElementCount EC, bool HasGlobalPred) {
104 SmallVector<VFParameter, 8> Parameters;
105 for (unsigned I = 0; I < CI.arg_size(); ++I)
106 Parameters.push_back(VFParameter({I, VFParamKind::Vector}));
107 if (HasGlobalPred)
108 Parameters.push_back(
109 VFParameter({CI.arg_size(), VFParamKind::GlobalPredicate}));
110
111 return {EC.Min, EC.Scalable, Parameters};
112 }
113 /// Sanity check on the Parameters in the VFShape.
114 bool hasValidParameterList() const;
115};
116
117/// Holds the VFShape for a specific scalar to vector function mapping.
118struct VFInfo {
119 VFShape Shape; /// Classification of the vector function.
120 std::string ScalarName; /// Scalar Function Name.
121 std::string VectorName; /// Vector Function Name associated to this VFInfo.
122 VFISAKind ISA; /// Instruction Set Architecture.
123
124 // Comparison operator.
125 bool operator==(const VFInfo &Other) const {
126 return std::tie(Shape, ScalarName, VectorName, ISA) ==
127 std::tie(Shape, Other.ScalarName, Other.VectorName, Other.ISA);
128 }
129};
130
131namespace VFABI {
132/// LLVM Internal VFABI ISA token for vector functions.
133static constexpr char const *_LLVM_ = "_LLVM_";
134/// Prefix for internal name redirection for vector function that
135/// tells the compiler to scalarize the call using the scalar name
136/// of the function. For example, a mangled name like
137/// `_ZGV_LLVM_N2v_foo(_LLVM_Scalarize_foo)` would tell the
138/// vectorizer to vectorize the scalar call `foo`, and to scalarize
139/// it once vectorization is done.
140static constexpr char const *_LLVM_Scalarize_ = "_LLVM_Scalarize_";
141
142/// Function to contruct a VFInfo out of a mangled names in the
143/// following format:
144///
145/// <VFABI_name>{(<redirection>)}
146///
147/// where <VFABI_name> is the name of the vector function, mangled according
148/// to the rules described in the Vector Function ABI of the target vector
149/// extentsion (or <isa> from now on). The <VFABI_name> is in the following
150/// format:
151///
152/// _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)]
153///
154/// This methods support demangling rules for the following <isa>:
155///
156/// * AArch64: https://developer.arm.com/docs/101129/latest
157///
158/// * x86 (libmvec): https://sourceware.org/glibc/wiki/libmvec and
159/// https://sourceware.org/glibc/wiki/libmvec?action=AttachFile&do=view&target=VectorABI.txt
160///
161/// \param MangledName -> input string in the format
162/// _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)].
163/// \param M -> Module used to retrive informations about the vector
164/// function that are not possible to retrieve from the mangled
165/// name. At the moment, this parameter is needed only to retrive the
166/// Vectorization Factor of scalable vector functions from their
167/// respective IR declarations.
168Optional<VFInfo> tryDemangleForVFABI(StringRef MangledName, const Module &M);
169
170/// Retrieve the `VFParamKind` from a string token.
171VFParamKind getVFParamKindFromString(const StringRef Token);
172
173// Name of the attribute where the variant mappings are stored.
174static constexpr char const *MappingsAttrName = "vector-function-abi-variant";
175
176/// Populates a set of strings representing the Vector Function ABI variants
177/// associated to the CallInst CI.
178void getVectorVariantNames(const CallInst &CI,
179 SmallVectorImpl<std::string> &VariantMappings);
180} // end namespace VFABI
181
182/// The Vector Function Database.
183///
184/// Helper class used to find the vector functions associated to a
185/// scalar CallInst.
186class VFDatabase {
187 /// The Module of the CallInst CI.
188 const Module *M;
189 /// List of vector functions descritors associated to the call
190 /// instruction.
191 const SmallVector<VFInfo, 8> ScalarToVectorMappings;
192
193 /// Retreive the scalar-to-vector mappings associated to the rule of
194 /// a vector Function ABI.
195 static void getVFABIMappings(const CallInst &CI,
196 SmallVectorImpl<VFInfo> &Mappings) {
197 const StringRef ScalarName = CI.getCalledFunction()->getName();
198 const StringRef S =
199 CI.getAttribute(AttributeList::FunctionIndex, VFABI::MappingsAttrName)
200 .getValueAsString();
201 if (S.empty())
202 return;
203
204 SmallVector<std::string, 8> ListOfStrings;
205 VFABI::getVectorVariantNames(CI, ListOfStrings);
206 for (const auto &MangledName : ListOfStrings) {
207 const Optional<VFInfo> Shape =
208 VFABI::tryDemangleForVFABI(MangledName, *(CI.getModule()));
209 // A match is found via scalar and vector names, and also by
210 // ensuring that the variant described in the attribute has a
211 // corresponding definition or declaration of the vector
212 // function in the Module M.
213 if (Shape.hasValue() && (Shape.getValue().ScalarName == ScalarName)) {
214 assert(CI.getModule()->getFunction(Shape.getValue().VectorName) &&((CI.getModule()->getFunction(Shape.getValue().VectorName)
&& "Vector function is missing.") ? static_cast<void
> (0) : __assert_fail ("CI.getModule()->getFunction(Shape.getValue().VectorName) && \"Vector function is missing.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 215, __PRETTY_FUNCTION__))
215 "Vector function is missing.")((CI.getModule()->getFunction(Shape.getValue().VectorName)
&& "Vector function is missing.") ? static_cast<void
> (0) : __assert_fail ("CI.getModule()->getFunction(Shape.getValue().VectorName) && \"Vector function is missing.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 215, __PRETTY_FUNCTION__))
;
216 Mappings.push_back(Shape.getValue());
217 }
218 }
219 }
220
221public:
222 /// Retrieve all the VFInfo instances associated to the CallInst CI.
223 static SmallVector<VFInfo, 8> getMappings(const CallInst &CI) {
224 SmallVector<VFInfo, 8> Ret;
225
226 // Get mappings from the Vector Function ABI variants.
227 getVFABIMappings(CI, Ret);
228
229 // Other non-VFABI variants should be retrieved here.
230
231 return Ret;
232 }
233
234 /// Constructor, requires a CallInst instance.
235 VFDatabase(CallInst &CI)
236 : M(CI.getModule()), ScalarToVectorMappings(VFDatabase::getMappings(CI)) {
237 }
238 /// \defgroup VFDatabase query interface.
239 ///
240 /// @{
241 /// Retrieve the Function with VFShape \p Shape.
242 Function *getVectorizedFunction(const VFShape &Shape) const {
243 for (const auto &Info : ScalarToVectorMappings)
244 if (Info.Shape == Shape)
245 return M->getFunction(Info.VectorName);
246
247 return nullptr;
248 }
249 /// @}
250};
251
252template <typename T> class ArrayRef;
253class DemandedBits;
254class GetElementPtrInst;
255template <typename InstTy> class InterleaveGroup;
256class IRBuilderBase;
257class Loop;
258class ScalarEvolution;
259class TargetTransformInfo;
260class Type;
261class Value;
262
263namespace Intrinsic {
264typedef unsigned ID;
265}
266
267/// A helper function for converting Scalar types to vector types.
268/// If the incoming type is void, we return void. If the VF is 1, we return
269/// the scalar type.
270inline Type *ToVectorTy(Type *Scalar, unsigned VF, bool isScalable = false) {
271 if (Scalar->isVoidTy() || VF == 1)
272 return Scalar;
273 return VectorType::get(Scalar, {VF, isScalable});
274}
275
276/// Identify if the intrinsic is trivially vectorizable.
277/// This method returns true if the intrinsic's argument types are all scalars
278/// for the scalar form of the intrinsic and all vectors (or scalars handled by
279/// hasVectorInstrinsicScalarOpd) for the vector form of the intrinsic.
280bool isTriviallyVectorizable(Intrinsic::ID ID);
281
282/// Identifies if the vector form of the intrinsic has a scalar operand.
283bool hasVectorInstrinsicScalarOpd(Intrinsic::ID ID, unsigned ScalarOpdIdx);
284
285/// Returns intrinsic ID for call.
286/// For the input call instruction it finds mapping intrinsic and returns
287/// its intrinsic ID, in case it does not found it return not_intrinsic.
288Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI,
289 const TargetLibraryInfo *TLI);
290
291/// Find the operand of the GEP that should be checked for consecutive
292/// stores. This ignores trailing indices that have no effect on the final
293/// pointer.
294unsigned getGEPInductionOperand(const GetElementPtrInst *Gep);
295
296/// If the argument is a GEP, then returns the operand identified by
297/// getGEPInductionOperand. However, if there is some other non-loop-invariant
298/// operand, it returns that instead.
299Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp);
300
301/// If a value has only one user that is a CastInst, return it.
302Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty);
303
304/// Get the stride of a pointer access in a loop. Looks for symbolic
305/// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
306Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp);
307
308/// Given a vector and an element number, see if the scalar value is
309/// already around as a register, for example if it were inserted then extracted
310/// from the vector.
311Value *findScalarElement(Value *V, unsigned EltNo);
312
313/// If all non-negative \p Mask elements are the same value, return that value.
314/// If all elements are negative (undefined) or \p Mask contains different
315/// non-negative values, return -1.
316int getSplatIndex(ArrayRef<int> Mask);
317
318/// Get splat value if the input is a splat vector or return nullptr.
319/// The value may be extracted from a splat constants vector or from
320/// a sequence of instructions that broadcast a single value into a vector.
321const Value *getSplatValue(const Value *V);
322
323/// Return true if each element of the vector value \p V is poisoned or equal to
324/// every other non-poisoned element. If an index element is specified, either
325/// every element of the vector is poisoned or the element at that index is not
326/// poisoned and equal to every other non-poisoned element.
327/// This may be more powerful than the related getSplatValue() because it is
328/// not limited by finding a scalar source value to a splatted vector.
329bool isSplatValue(const Value *V, int Index = -1, unsigned Depth = 0);
330
331/// Compute a map of integer instructions to their minimum legal type
332/// size.
333///
334/// C semantics force sub-int-sized values (e.g. i8, i16) to be promoted to int
335/// type (e.g. i32) whenever arithmetic is performed on them.
336///
337/// For targets with native i8 or i16 operations, usually InstCombine can shrink
338/// the arithmetic type down again. However InstCombine refuses to create
339/// illegal types, so for targets without i8 or i16 registers, the lengthening
340/// and shrinking remains.
341///
342/// Most SIMD ISAs (e.g. NEON) however support vectors of i8 or i16 even when
343/// their scalar equivalents do not, so during vectorization it is important to
344/// remove these lengthens and truncates when deciding the profitability of
345/// vectorization.
346///
347/// This function analyzes the given range of instructions and determines the
348/// minimum type size each can be converted to. It attempts to remove or
349/// minimize type size changes across each def-use chain, so for example in the
350/// following code:
351///
352/// %1 = load i8, i8*
353/// %2 = add i8 %1, 2
354/// %3 = load i16, i16*
355/// %4 = zext i8 %2 to i32
356/// %5 = zext i16 %3 to i32
357/// %6 = add i32 %4, %5
358/// %7 = trunc i32 %6 to i16
359///
360/// Instruction %6 must be done at least in i16, so computeMinimumValueSizes
361/// will return: {%1: 16, %2: 16, %3: 16, %4: 16, %5: 16, %6: 16, %7: 16}.
362///
363/// If the optional TargetTransformInfo is provided, this function tries harder
364/// to do less work by only looking at illegal types.
365MapVector<Instruction*, uint64_t>
366computeMinimumValueSizes(ArrayRef<BasicBlock*> Blocks,
367 DemandedBits &DB,
368 const TargetTransformInfo *TTI=nullptr);
369
370/// Compute the union of two access-group lists.
371///
372/// If the list contains just one access group, it is returned directly. If the
373/// list is empty, returns nullptr.
374MDNode *uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2);
375
376/// Compute the access-group list of access groups that @p Inst1 and @p Inst2
377/// are both in. If either instruction does not access memory at all, it is
378/// considered to be in every list.
379///
380/// If the list contains just one access group, it is returned directly. If the
381/// list is empty, returns nullptr.
382MDNode *intersectAccessGroups(const Instruction *Inst1,
383 const Instruction *Inst2);
384
385/// Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath,
386/// MD_nontemporal, MD_access_group].
387/// For K in Kinds, we get the MDNode for K from each of the
388/// elements of VL, compute their "intersection" (i.e., the most generic
389/// metadata value that covers all of the individual values), and set I's
390/// metadata for M equal to the intersection value.
391///
392/// This function always sets a (possibly null) value for each K in Kinds.
393Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL);
394
395/// Create a mask that filters the members of an interleave group where there
396/// are gaps.
397///
398/// For example, the mask for \p Group with interleave-factor 3
399/// and \p VF 4, that has only its first member present is:
400///
401/// <1,0,0,1,0,0,1,0,0,1,0,0>
402///
403/// Note: The result is a mask of 0's and 1's, as opposed to the other
404/// create[*]Mask() utilities which create a shuffle mask (mask that
405/// consists of indices).
406Constant *createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF,
407 const InterleaveGroup<Instruction> &Group);
408
409/// Create a mask with replicated elements.
410///
411/// This function creates a shuffle mask for replicating each of the \p VF
412/// elements in a vector \p ReplicationFactor times. It can be used to
413/// transform a mask of \p VF elements into a mask of
414/// \p VF * \p ReplicationFactor elements used by a predicated
415/// interleaved-group of loads/stores whose Interleaved-factor ==
416/// \p ReplicationFactor.
417///
418/// For example, the mask for \p ReplicationFactor=3 and \p VF=4 is:
419///
420/// <0,0,0,1,1,1,2,2,2,3,3,3>
421Constant *createReplicatedMask(IRBuilderBase &Builder,
422 unsigned ReplicationFactor, unsigned VF);
423
424/// Create an interleave shuffle mask.
425///
426/// This function creates a shuffle mask for interleaving \p NumVecs vectors of
427/// vectorization factor \p VF into a single wide vector. The mask is of the
428/// form:
429///
430/// <0, VF, VF * 2, ..., VF * (NumVecs - 1), 1, VF + 1, VF * 2 + 1, ...>
431///
432/// For example, the mask for VF = 4 and NumVecs = 2 is:
433///
434/// <0, 4, 1, 5, 2, 6, 3, 7>.
435Constant *createInterleaveMask(IRBuilderBase &Builder, unsigned VF,
436 unsigned NumVecs);
437
438/// Create a stride shuffle mask.
439///
440/// This function creates a shuffle mask whose elements begin at \p Start and
441/// are incremented by \p Stride. The mask can be used to deinterleave an
442/// interleaved vector into separate vectors of vectorization factor \p VF. The
443/// mask is of the form:
444///
445/// <Start, Start + Stride, ..., Start + Stride * (VF - 1)>
446///
447/// For example, the mask for Start = 0, Stride = 2, and VF = 4 is:
448///
449/// <0, 2, 4, 6>
450Constant *createStrideMask(IRBuilderBase &Builder, unsigned Start,
451 unsigned Stride, unsigned VF);
452
453/// Create a sequential shuffle mask.
454///
455/// This function creates shuffle mask whose elements are sequential and begin
456/// at \p Start. The mask contains \p NumInts integers and is padded with \p
457/// NumUndefs undef values. The mask is of the form:
458///
459/// <Start, Start + 1, ... Start + NumInts - 1, undef_1, ... undef_NumUndefs>
460///
461/// For example, the mask for Start = 0, NumInsts = 4, and NumUndefs = 4 is:
462///
463/// <0, 1, 2, 3, undef, undef, undef, undef>
464Constant *createSequentialMask(IRBuilderBase &Builder, unsigned Start,
465 unsigned NumInts, unsigned NumUndefs);
466
467/// Concatenate a list of vectors.
468///
469/// This function generates code that concatenate the vectors in \p Vecs into a
470/// single large vector. The number of vectors should be greater than one, and
471/// their element types should be the same. The number of elements in the
472/// vectors should also be the same; however, if the last vector has fewer
473/// elements, it will be padded with undefs.
474Value *concatenateVectors(IRBuilderBase &Builder, ArrayRef<Value *> Vecs);
475
476/// Given a mask vector of the form <Y x i1>, Return true if all of the
477/// elements of this predicate mask are false or undef. That is, return true
478/// if all lanes can be assumed inactive.
479bool maskIsAllZeroOrUndef(Value *Mask);
480
481/// Given a mask vector of the form <Y x i1>, Return true if all of the
482/// elements of this predicate mask are true or undef. That is, return true
483/// if all lanes can be assumed active.
484bool maskIsAllOneOrUndef(Value *Mask);
485
486/// Given a mask vector of the form <Y x i1>, return an APInt (of bitwidth Y)
487/// for each lane which may be active.
488APInt possiblyDemandedEltsInMask(Value *Mask);
489
490/// The group of interleaved loads/stores sharing the same stride and
491/// close to each other.
492///
493/// Each member in this group has an index starting from 0, and the largest
494/// index should be less than interleaved factor, which is equal to the absolute
495/// value of the access's stride.
496///
497/// E.g. An interleaved load group of factor 4:
498/// for (unsigned i = 0; i < 1024; i+=4) {
499/// a = A[i]; // Member of index 0
500/// b = A[i+1]; // Member of index 1
501/// d = A[i+3]; // Member of index 3
502/// ...
503/// }
504///
505/// An interleaved store group of factor 4:
506/// for (unsigned i = 0; i < 1024; i+=4) {
507/// ...
508/// A[i] = a; // Member of index 0
509/// A[i+1] = b; // Member of index 1
510/// A[i+2] = c; // Member of index 2
511/// A[i+3] = d; // Member of index 3
512/// }
513///
514/// Note: the interleaved load group could have gaps (missing members), but
515/// the interleaved store group doesn't allow gaps.
516template <typename InstTy> class InterleaveGroup {
517public:
518 InterleaveGroup(uint32_t Factor, bool Reverse, Align Alignment)
519 : Factor(Factor), Reverse(Reverse), Alignment(Alignment),
520 InsertPos(nullptr) {}
521
522 InterleaveGroup(InstTy *Instr, int32_t Stride, Align Alignment)
523 : Alignment(Alignment), InsertPos(Instr) {
524 Factor = std::abs(Stride);
525 assert(Factor > 1 && "Invalid interleave factor")((Factor > 1 && "Invalid interleave factor") ? static_cast
<void> (0) : __assert_fail ("Factor > 1 && \"Invalid interleave factor\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 525, __PRETTY_FUNCTION__))
;
526
527 Reverse = Stride < 0;
528 Members[0] = Instr;
529 }
530
531 bool isReverse() const { return Reverse; }
532 uint32_t getFactor() const { return Factor; }
533 uint32_t getAlignment() const { return Alignment.value(); }
534 Align getAlign() const { return Alignment; }
535 uint32_t getNumMembers() const { return Members.size(); }
536
537 /// Try to insert a new member \p Instr with index \p Index and
538 /// alignment \p NewAlign. The index is related to the leader and it could be
539 /// negative if it is the new leader.
540 ///
541 /// \returns false if the instruction doesn't belong to the group.
542 bool insertMember(InstTy *Instr, int32_t Index, Align NewAlign) {
543 // Make sure the key fits in an int32_t.
544 Optional<int32_t> MaybeKey = checkedAdd(Index, SmallestKey);
545 if (!MaybeKey)
546 return false;
547 int32_t Key = *MaybeKey;
548
549 // Skip if there is already a member with the same index.
550 if (Members.find(Key) != Members.end())
551 return false;
552
553 if (Key > LargestKey) {
554 // The largest index is always less than the interleave factor.
555 if (Index >= static_cast<int32_t>(Factor))
556 return false;
557
558 LargestKey = Key;
559 } else if (Key < SmallestKey) {
560
561 // Make sure the largest index fits in an int32_t.
562 Optional<int32_t> MaybeLargestIndex = checkedSub(LargestKey, Key);
563 if (!MaybeLargestIndex)
564 return false;
565
566 // The largest index is always less than the interleave factor.
567 if (*MaybeLargestIndex >= static_cast<int64_t>(Factor))
568 return false;
569
570 SmallestKey = Key;
571 }
572
573 // It's always safe to select the minimum alignment.
574 Alignment = std::min(Alignment, NewAlign);
575 Members[Key] = Instr;
576 return true;
577 }
578
579 /// Get the member with the given index \p Index
580 ///
581 /// \returns nullptr if contains no such member.
582 InstTy *getMember(uint32_t Index) const {
583 int32_t Key = SmallestKey + Index;
584 auto Member = Members.find(Key);
585 if (Member == Members.end())
586 return nullptr;
587
588 return Member->second;
589 }
590
591 /// Get the index for the given member. Unlike the key in the member
592 /// map, the index starts from 0.
593 uint32_t getIndex(const InstTy *Instr) const {
594 for (auto I : Members) {
595 if (I.second == Instr)
596 return I.first - SmallestKey;
597 }
598
599 llvm_unreachable("InterleaveGroup contains no such member")::llvm::llvm_unreachable_internal("InterleaveGroup contains no such member"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 599)
;
600 }
601
602 InstTy *getInsertPos() const { return InsertPos; }
603 void setInsertPos(InstTy *Inst) { InsertPos = Inst; }
604
605 /// Add metadata (e.g. alias info) from the instructions in this group to \p
606 /// NewInst.
607 ///
608 /// FIXME: this function currently does not add noalias metadata a'la
609 /// addNewMedata. To do that we need to compute the intersection of the
610 /// noalias info from all members.
611 void addMetadata(InstTy *NewInst) const;
612
613 /// Returns true if this Group requires a scalar iteration to handle gaps.
614 bool requiresScalarEpilogue() const {
615 // If the last member of the Group exists, then a scalar epilog is not
616 // needed for this group.
617 if (getMember(getFactor() - 1))
618 return false;
619
620 // We have a group with gaps. It therefore cannot be a group of stores,
621 // and it can't be a reversed access, because such groups get invalidated.
622 assert(!getMember(0)->mayWriteToMemory() &&((!getMember(0)->mayWriteToMemory() && "Group should have been invalidated"
) ? static_cast<void> (0) : __assert_fail ("!getMember(0)->mayWriteToMemory() && \"Group should have been invalidated\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 623, __PRETTY_FUNCTION__))
623 "Group should have been invalidated")((!getMember(0)->mayWriteToMemory() && "Group should have been invalidated"
) ? static_cast<void> (0) : __assert_fail ("!getMember(0)->mayWriteToMemory() && \"Group should have been invalidated\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 623, __PRETTY_FUNCTION__))
;
624 assert(!isReverse() && "Group should have been invalidated")((!isReverse() && "Group should have been invalidated"
) ? static_cast<void> (0) : __assert_fail ("!isReverse() && \"Group should have been invalidated\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 624, __PRETTY_FUNCTION__))
;
625
626 // This is a group of loads, with gaps, and without a last-member
627 return true;
628 }
629
630private:
631 uint32_t Factor; // Interleave Factor.
632 bool Reverse;
633 Align Alignment;
634 DenseMap<int32_t, InstTy *> Members;
635 int32_t SmallestKey = 0;
636 int32_t LargestKey = 0;
637
638 // To avoid breaking dependences, vectorized instructions of an interleave
639 // group should be inserted at either the first load or the last store in
640 // program order.
641 //
642 // E.g. %even = load i32 // Insert Position
643 // %add = add i32 %even // Use of %even
644 // %odd = load i32
645 //
646 // store i32 %even
647 // %odd = add i32 // Def of %odd
648 // store i32 %odd // Insert Position
649 InstTy *InsertPos;
650};
651
652/// Drive the analysis of interleaved memory accesses in the loop.
653///
654/// Use this class to analyze interleaved accesses only when we can vectorize
655/// a loop. Otherwise it's meaningless to do analysis as the vectorization
656/// on interleaved accesses is unsafe.
657///
658/// The analysis collects interleave groups and records the relationships
659/// between the member and the group in a map.
660class InterleavedAccessInfo {
661public:
662 InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
663 DominatorTree *DT, LoopInfo *LI,
664 const LoopAccessInfo *LAI)
665 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
666
667 ~InterleavedAccessInfo() { reset(); }
668
669 /// Analyze the interleaved accesses and collect them in interleave
670 /// groups. Substitute symbolic strides using \p Strides.
671 /// Consider also predicated loads/stores in the analysis if
672 /// \p EnableMaskedInterleavedGroup is true.
673 void analyzeInterleaving(bool EnableMaskedInterleavedGroup);
674
675 /// Invalidate groups, e.g., in case all blocks in loop will be predicated
676 /// contrary to original assumption. Although we currently prevent group
677 /// formation for predicated accesses, we may be able to relax this limitation
678 /// in the future once we handle more complicated blocks.
679 void reset() {
680 InterleaveGroupMap.clear();
681 for (auto *Ptr : InterleaveGroups)
682 delete Ptr;
683 InterleaveGroups.clear();
684 RequiresScalarEpilogue = false;
685 }
686
687
688 /// Check if \p Instr belongs to any interleave group.
689 bool isInterleaved(Instruction *Instr) const {
690 return InterleaveGroupMap.find(Instr) != InterleaveGroupMap.end();
691 }
692
693 /// Get the interleave group that \p Instr belongs to.
694 ///
695 /// \returns nullptr if doesn't have such group.
696 InterleaveGroup<Instruction> *
697 getInterleaveGroup(const Instruction *Instr) const {
698 if (InterleaveGroupMap.count(Instr))
699 return InterleaveGroupMap.find(Instr)->second;
700 return nullptr;
701 }
702
703 iterator_range<SmallPtrSetIterator<llvm::InterleaveGroup<Instruction> *>>
704 getInterleaveGroups() {
705 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
706 }
707
708 /// Returns true if an interleaved group that may access memory
709 /// out-of-bounds requires a scalar epilogue iteration for correctness.
710 bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }
711
712 /// Invalidate groups that require a scalar epilogue (due to gaps). This can
713 /// happen when optimizing for size forbids a scalar epilogue, and the gap
714 /// cannot be filtered by masking the load/store.
715 void invalidateGroupsRequiringScalarEpilogue();
716
717private:
718 /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
719 /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
720 /// The interleaved access analysis can also add new predicates (for example
721 /// by versioning strides of pointers).
722 PredicatedScalarEvolution &PSE;
723
724 Loop *TheLoop;
725 DominatorTree *DT;
726 LoopInfo *LI;
727 const LoopAccessInfo *LAI;
728
729 /// True if the loop may contain non-reversed interleaved groups with
730 /// out-of-bounds accesses. We ensure we don't speculatively access memory
731 /// out-of-bounds by executing at least one scalar epilogue iteration.
732 bool RequiresScalarEpilogue = false;
733
734 /// Holds the relationships between the members and the interleave group.
735 DenseMap<Instruction *, InterleaveGroup<Instruction> *> InterleaveGroupMap;
736
737 SmallPtrSet<InterleaveGroup<Instruction> *, 4> InterleaveGroups;
738
739 /// Holds dependences among the memory accesses in the loop. It maps a source
740 /// access to a set of dependent sink accesses.
741 DenseMap<Instruction *, SmallPtrSet<Instruction *, 2>> Dependences;
742
743 /// The descriptor for a strided memory access.
744 struct StrideDescriptor {
745 StrideDescriptor() = default;
746 StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,
747 Align Alignment)
748 : Stride(Stride), Scev(Scev), Size(Size), Alignment(Alignment) {}
749
750 // The access's stride. It is negative for a reverse access.
751 int64_t Stride = 0;
752
753 // The scalar expression of this access.
754 const SCEV *Scev = nullptr;
755
756 // The size of the memory object.
757 uint64_t Size = 0;
758
759 // The alignment of this access.
760 Align Alignment;
761 };
762
763 /// A type for holding instructions and their stride descriptors.
764 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
765
766 /// Create a new interleave group with the given instruction \p Instr,
767 /// stride \p Stride and alignment \p Align.
768 ///
769 /// \returns the newly created interleave group.
770 InterleaveGroup<Instruction> *
771 createInterleaveGroup(Instruction *Instr, int Stride, Align Alignment) {
772 assert(!InterleaveGroupMap.count(Instr) &&((!InterleaveGroupMap.count(Instr) && "Already in an interleaved access group"
) ? static_cast<void> (0) : __assert_fail ("!InterleaveGroupMap.count(Instr) && \"Already in an interleaved access group\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 773, __PRETTY_FUNCTION__))
773 "Already in an interleaved access group")((!InterleaveGroupMap.count(Instr) && "Already in an interleaved access group"
) ? static_cast<void> (0) : __assert_fail ("!InterleaveGroupMap.count(Instr) && \"Already in an interleaved access group\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/VectorUtils.h"
, 773, __PRETTY_FUNCTION__))
;
774 InterleaveGroupMap[Instr] =
775 new InterleaveGroup<Instruction>(Instr, Stride, Alignment);
776 InterleaveGroups.insert(InterleaveGroupMap[Instr]);
777 return InterleaveGroupMap[Instr];
778 }
779
780 /// Release the group and remove all the relationships.
781 void releaseGroup(InterleaveGroup<Instruction> *Group) {
782 for (unsigned i = 0; i < Group->getFactor(); i++)
783 if (Instruction *Member = Group->getMember(i))
784 InterleaveGroupMap.erase(Member);
785
786 InterleaveGroups.erase(Group);
787 delete Group;
788 }
789
790 /// Collect all the accesses with a constant stride in program order.
791 void collectConstStrideAccesses(
792 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
793 const ValueToValueMap &Strides);
794
795 /// Returns true if \p Stride is allowed in an interleaved group.
796 static bool isStrided(int Stride);
797
798 /// Returns true if \p BB is a predicated block.
799 bool isPredicated(BasicBlock *BB) const {
800 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
801 }
802
803 /// Returns true if LoopAccessInfo can be used for dependence queries.
804 bool areDependencesValid() const {
805 return LAI && LAI->getDepChecker().getDependences();
806 }
807
808 /// Returns true if memory accesses \p A and \p B can be reordered, if
809 /// necessary, when constructing interleaved groups.
810 ///
811 /// \p A must precede \p B in program order. We return false if reordering is
812 /// not necessary or is prevented because \p A and \p B may be dependent.
813 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
814 StrideEntry *B) const {
815 // Code motion for interleaved accesses can potentially hoist strided loads
816 // and sink strided stores. The code below checks the legality of the
817 // following two conditions:
818 //
819 // 1. Potentially moving a strided load (B) before any store (A) that
820 // precedes B, or
821 //
822 // 2. Potentially moving a strided store (A) after any load or store (B)
823 // that A precedes.
824 //
825 // It's legal to reorder A and B if we know there isn't a dependence from A
826 // to B. Note that this determination is conservative since some
827 // dependences could potentially be reordered safely.
828
829 // A is potentially the source of a dependence.
830 auto *Src = A->first;
831 auto SrcDes = A->second;
832
833 // B is potentially the sink of a dependence.
834 auto *Sink = B->first;
835 auto SinkDes = B->second;
836
837 // Code motion for interleaved accesses can't violate WAR dependences.
838 // Thus, reordering is legal if the source isn't a write.
839 if (!Src->mayWriteToMemory())
29
Assuming the condition is true
30
Taking true branch
47
Assuming the condition is true
48
Taking true branch
840 return true;
31
Returning the value 1, which participates in a condition later
49
Returning the value 1, which participates in a condition later
841
842 // At least one of the accesses must be strided.
843 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
844 return true;
845
846 // If dependence information is not available from LoopAccessInfo,
847 // conservatively assume the instructions can't be reordered.
848 if (!areDependencesValid())
849 return false;
850
851 // If we know there is a dependence from source to sink, assume the
852 // instructions can't be reordered. Otherwise, reordering is legal.
853 return Dependences.find(Src) == Dependences.end() ||
854 !Dependences.lookup(Src).count(Sink);
855 }
856
857 /// Collect the dependences from LoopAccessInfo.
858 ///
859 /// We process the dependences once during the interleaved access analysis to
860 /// enable constant-time dependence queries.
861 void collectDependences() {
862 if (!areDependencesValid())
863 return;
864 auto *Deps = LAI->getDepChecker().getDependences();
865 for (auto Dep : *Deps)
866 Dependences[Dep.getSource(*LAI)].insert(Dep.getDestination(*LAI));
867 }
868};
869
870} // llvm namespace
871
872#endif