Bug Summary

File:llvm/lib/Analysis/VectorUtils.cpp
Warning:line 1035, 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-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/include -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/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-10/lib/clang/10.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-10~++20200112100611+7fa5290d5bd/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd=. -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-01-13-084841-49055-1 -x c++ /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp

/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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
310/// Get splat value if the input is a splat vector or return nullptr.
311/// This function is not fully general. It checks only 2 cases:
312/// the input value is (1) a splat constant vector or (2) a sequence
313/// of instructions that broadcasts a scalar at element 0.
314const llvm::Value *llvm::getSplatValue(const Value *V) {
315 if (isa<VectorType>(V->getType()))
316 if (auto *C = dyn_cast<Constant>(V))
317 return C->getSplatValue();
318
319 // shuf (inselt ?, Splat, 0), ?, <0, undef, 0, ...>
320 Value *Splat;
321 if (match(V, m_ShuffleVector(m_InsertElement(m_Value(), m_Value(Splat),
322 m_ZeroInt()),
323 m_Value(), m_ZeroInt())))
324 return Splat;
325
326 return nullptr;
327}
328
329// This setting is based on its counterpart in value tracking, but it could be
330// adjusted if needed.
331const unsigned MaxDepth = 6;
332
333bool llvm::isSplatValue(const Value *V, unsigned Depth) {
334 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 334, __PRETTY_FUNCTION__))
;
335
336 if (isa<VectorType>(V->getType())) {
337 if (isa<UndefValue>(V))
338 return true;
339 // FIXME: Constant splat analysis does not allow undef elements.
340 if (auto *C = dyn_cast<Constant>(V))
341 return C->getSplatValue() != nullptr;
342 }
343
344 // FIXME: Constant splat analysis does not allow undef elements.
345 Constant *Mask;
346 if (match(V, m_ShuffleVector(m_Value(), m_Value(), m_Constant(Mask))))
347 return Mask->getSplatValue() != nullptr;
348
349 // The remaining tests are all recursive, so bail out if we hit the limit.
350 if (Depth++ == MaxDepth)
351 return false;
352
353 // If both operands of a binop are splats, the result is a splat.
354 Value *X, *Y, *Z;
355 if (match(V, m_BinOp(m_Value(X), m_Value(Y))))
356 return isSplatValue(X, Depth) && isSplatValue(Y, Depth);
357
358 // If all operands of a select are splats, the result is a splat.
359 if (match(V, m_Select(m_Value(X), m_Value(Y), m_Value(Z))))
360 return isSplatValue(X, Depth) && isSplatValue(Y, Depth) &&
361 isSplatValue(Z, Depth);
362
363 // TODO: Add support for unary ops (fneg), casts, intrinsics (overflow ops).
364
365 return false;
366}
367
368MapVector<Instruction *, uint64_t>
369llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB,
370 const TargetTransformInfo *TTI) {
371
372 // DemandedBits will give us every value's live-out bits. But we want
373 // to ensure no extra casts would need to be inserted, so every DAG
374 // of connected values must have the same minimum bitwidth.
375 EquivalenceClasses<Value *> ECs;
376 SmallVector<Value *, 16> Worklist;
377 SmallPtrSet<Value *, 4> Roots;
378 SmallPtrSet<Value *, 16> Visited;
379 DenseMap<Value *, uint64_t> DBits;
380 SmallPtrSet<Instruction *, 4> InstructionSet;
381 MapVector<Instruction *, uint64_t> MinBWs;
382
383 // Determine the roots. We work bottom-up, from truncs or icmps.
384 bool SeenExtFromIllegalType = false;
385 for (auto *BB : Blocks)
386 for (auto &I : *BB) {
387 InstructionSet.insert(&I);
388
389 if (TTI && (isa<ZExtInst>(&I) || isa<SExtInst>(&I)) &&
390 !TTI->isTypeLegal(I.getOperand(0)->getType()))
391 SeenExtFromIllegalType = true;
392
393 // Only deal with non-vector integers up to 64-bits wide.
394 if ((isa<TruncInst>(&I) || isa<ICmpInst>(&I)) &&
395 !I.getType()->isVectorTy() &&
396 I.getOperand(0)->getType()->getScalarSizeInBits() <= 64) {
397 // Don't make work for ourselves. If we know the loaded type is legal,
398 // don't add it to the worklist.
399 if (TTI && isa<TruncInst>(&I) && TTI->isTypeLegal(I.getType()))
400 continue;
401
402 Worklist.push_back(&I);
403 Roots.insert(&I);
404 }
405 }
406 // Early exit.
407 if (Worklist.empty() || (TTI && !SeenExtFromIllegalType))
408 return MinBWs;
409
410 // Now proceed breadth-first, unioning values together.
411 while (!Worklist.empty()) {
412 Value *Val = Worklist.pop_back_val();
413 Value *Leader = ECs.getOrInsertLeaderValue(Val);
414
415 if (Visited.count(Val))
416 continue;
417 Visited.insert(Val);
418
419 // Non-instructions terminate a chain successfully.
420 if (!isa<Instruction>(Val))
421 continue;
422 Instruction *I = cast<Instruction>(Val);
423
424 // If we encounter a type that is larger than 64 bits, we can't represent
425 // it so bail out.
426 if (DB.getDemandedBits(I).getBitWidth() > 64)
427 return MapVector<Instruction *, uint64_t>();
428
429 uint64_t V = DB.getDemandedBits(I).getZExtValue();
430 DBits[Leader] |= V;
431 DBits[I] = V;
432
433 // Casts, loads and instructions outside of our range terminate a chain
434 // successfully.
435 if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) ||
436 !InstructionSet.count(I))
437 continue;
438
439 // Unsafe casts terminate a chain unsuccessfully. We can't do anything
440 // useful with bitcasts, ptrtoints or inttoptrs and it'd be unsafe to
441 // transform anything that relies on them.
442 if (isa<BitCastInst>(I) || isa<PtrToIntInst>(I) || isa<IntToPtrInst>(I) ||
443 !I->getType()->isIntegerTy()) {
444 DBits[Leader] |= ~0ULL;
445 continue;
446 }
447
448 // We don't modify the types of PHIs. Reductions will already have been
449 // truncated if possible, and inductions' sizes will have been chosen by
450 // indvars.
451 if (isa<PHINode>(I))
452 continue;
453
454 if (DBits[Leader] == ~0ULL)
455 // All bits demanded, no point continuing.
456 continue;
457
458 for (Value *O : cast<User>(I)->operands()) {
459 ECs.unionSets(Leader, O);
460 Worklist.push_back(O);
461 }
462 }
463
464 // Now we've discovered all values, walk them to see if there are
465 // any users we didn't see. If there are, we can't optimize that
466 // chain.
467 for (auto &I : DBits)
468 for (auto *U : I.first->users())
469 if (U->getType()->isIntegerTy() && DBits.count(U) == 0)
470 DBits[ECs.getOrInsertLeaderValue(I.first)] |= ~0ULL;
471
472 for (auto I = ECs.begin(), E = ECs.end(); I != E; ++I) {
473 uint64_t LeaderDemandedBits = 0;
474 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
475 LeaderDemandedBits |= DBits[*MI];
476
477 uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) -
478 llvm::countLeadingZeros(LeaderDemandedBits);
479 // Round up to a power of 2
480 if (!isPowerOf2_64((uint64_t)MinBW))
481 MinBW = NextPowerOf2(MinBW);
482
483 // We don't modify the types of PHIs. Reductions will already have been
484 // truncated if possible, and inductions' sizes will have been chosen by
485 // indvars.
486 // If we are required to shrink a PHI, abandon this entire equivalence class.
487 bool Abort = false;
488 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
489 if (isa<PHINode>(*MI) && MinBW < (*MI)->getType()->getScalarSizeInBits()) {
490 Abort = true;
491 break;
492 }
493 if (Abort)
494 continue;
495
496 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) {
497 if (!isa<Instruction>(*MI))
498 continue;
499 Type *Ty = (*MI)->getType();
500 if (Roots.count(*MI))
501 Ty = cast<Instruction>(*MI)->getOperand(0)->getType();
502 if (MinBW < Ty->getScalarSizeInBits())
503 MinBWs[cast<Instruction>(*MI)] = MinBW;
504 }
505 }
506
507 return MinBWs;
508}
509
510/// Add all access groups in @p AccGroups to @p List.
511template <typename ListT>
512static void addToAccessGroupList(ListT &List, MDNode *AccGroups) {
513 // Interpret an access group as a list containing itself.
514 if (AccGroups->getNumOperands() == 0) {
515 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 515, __PRETTY_FUNCTION__))
;
516 List.insert(AccGroups);
517 return;
518 }
519
520 for (auto &AccGroupListOp : AccGroups->operands()) {
521 auto *Item = cast<MDNode>(AccGroupListOp.get());
522 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 522, __PRETTY_FUNCTION__))
;
523 List.insert(Item);
524 }
525}
526
527MDNode *llvm::uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2) {
528 if (!AccGroups1)
529 return AccGroups2;
530 if (!AccGroups2)
531 return AccGroups1;
532 if (AccGroups1 == AccGroups2)
533 return AccGroups1;
534
535 SmallSetVector<Metadata *, 4> Union;
536 addToAccessGroupList(Union, AccGroups1);
537 addToAccessGroupList(Union, AccGroups2);
538
539 if (Union.size() == 0)
540 return nullptr;
541 if (Union.size() == 1)
542 return cast<MDNode>(Union.front());
543
544 LLVMContext &Ctx = AccGroups1->getContext();
545 return MDNode::get(Ctx, Union.getArrayRef());
546}
547
548MDNode *llvm::intersectAccessGroups(const Instruction *Inst1,
549 const Instruction *Inst2) {
550 bool MayAccessMem1 = Inst1->mayReadOrWriteMemory();
551 bool MayAccessMem2 = Inst2->mayReadOrWriteMemory();
552
553 if (!MayAccessMem1 && !MayAccessMem2)
554 return nullptr;
555 if (!MayAccessMem1)
556 return Inst2->getMetadata(LLVMContext::MD_access_group);
557 if (!MayAccessMem2)
558 return Inst1->getMetadata(LLVMContext::MD_access_group);
559
560 MDNode *MD1 = Inst1->getMetadata(LLVMContext::MD_access_group);
561 MDNode *MD2 = Inst2->getMetadata(LLVMContext::MD_access_group);
562 if (!MD1 || !MD2)
563 return nullptr;
564 if (MD1 == MD2)
565 return MD1;
566
567 // Use set for scalable 'contains' check.
568 SmallPtrSet<Metadata *, 4> AccGroupSet2;
569 addToAccessGroupList(AccGroupSet2, MD2);
570
571 SmallVector<Metadata *, 4> Intersection;
572 if (MD1->getNumOperands() == 0) {
573 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 573, __PRETTY_FUNCTION__))
;
574 if (AccGroupSet2.count(MD1))
575 Intersection.push_back(MD1);
576 } else {
577 for (const MDOperand &Node : MD1->operands()) {
578 auto *Item = cast<MDNode>(Node.get());
579 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 579, __PRETTY_FUNCTION__))
;
580 if (AccGroupSet2.count(Item))
581 Intersection.push_back(Item);
582 }
583 }
584
585 if (Intersection.size() == 0)
586 return nullptr;
587 if (Intersection.size() == 1)
588 return cast<MDNode>(Intersection.front());
589
590 LLVMContext &Ctx = Inst1->getContext();
591 return MDNode::get(Ctx, Intersection);
592}
593
594/// \returns \p I after propagating metadata from \p VL.
595Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) {
596 Instruction *I0 = cast<Instruction>(VL[0]);
597 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
598 I0->getAllMetadataOtherThanDebugLoc(Metadata);
599
600 for (auto Kind : {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
601 LLVMContext::MD_noalias, LLVMContext::MD_fpmath,
602 LLVMContext::MD_nontemporal, LLVMContext::MD_invariant_load,
603 LLVMContext::MD_access_group}) {
604 MDNode *MD = I0->getMetadata(Kind);
605
606 for (int J = 1, E = VL.size(); MD && J != E; ++J) {
607 const Instruction *IJ = cast<Instruction>(VL[J]);
608 MDNode *IMD = IJ->getMetadata(Kind);
609 switch (Kind) {
610 case LLVMContext::MD_tbaa:
611 MD = MDNode::getMostGenericTBAA(MD, IMD);
612 break;
613 case LLVMContext::MD_alias_scope:
614 MD = MDNode::getMostGenericAliasScope(MD, IMD);
615 break;
616 case LLVMContext::MD_fpmath:
617 MD = MDNode::getMostGenericFPMath(MD, IMD);
618 break;
619 case LLVMContext::MD_noalias:
620 case LLVMContext::MD_nontemporal:
621 case LLVMContext::MD_invariant_load:
622 MD = MDNode::intersect(MD, IMD);
623 break;
624 case LLVMContext::MD_access_group:
625 MD = intersectAccessGroups(Inst, IJ);
626 break;
627 default:
628 llvm_unreachable("unhandled metadata")::llvm::llvm_unreachable_internal("unhandled metadata", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 628)
;
629 }
630 }
631
632 Inst->setMetadata(Kind, MD);
633 }
634
635 return Inst;
636}
637
638Constant *
639llvm::createBitMaskForGaps(IRBuilder<> &Builder, unsigned VF,
640 const InterleaveGroup<Instruction> &Group) {
641 // All 1's means mask is not needed.
642 if (Group.getNumMembers() == Group.getFactor())
643 return nullptr;
644
645 // TODO: support reversed access.
646 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 646, __PRETTY_FUNCTION__))
;
647
648 SmallVector<Constant *, 16> Mask;
649 for (unsigned i = 0; i < VF; i++)
650 for (unsigned j = 0; j < Group.getFactor(); ++j) {
651 unsigned HasMember = Group.getMember(j) ? 1 : 0;
652 Mask.push_back(Builder.getInt1(HasMember));
653 }
654
655 return ConstantVector::get(Mask);
656}
657
658Constant *llvm::createReplicatedMask(IRBuilder<> &Builder,
659 unsigned ReplicationFactor, unsigned VF) {
660 SmallVector<Constant *, 16> MaskVec;
661 for (unsigned i = 0; i < VF; i++)
662 for (unsigned j = 0; j < ReplicationFactor; j++)
663 MaskVec.push_back(Builder.getInt32(i));
664
665 return ConstantVector::get(MaskVec);
666}
667
668Constant *llvm::createInterleaveMask(IRBuilder<> &Builder, unsigned VF,
669 unsigned NumVecs) {
670 SmallVector<Constant *, 16> Mask;
671 for (unsigned i = 0; i < VF; i++)
672 for (unsigned j = 0; j < NumVecs; j++)
673 Mask.push_back(Builder.getInt32(j * VF + i));
674
675 return ConstantVector::get(Mask);
676}
677
678Constant *llvm::createStrideMask(IRBuilder<> &Builder, unsigned Start,
679 unsigned Stride, unsigned VF) {
680 SmallVector<Constant *, 16> Mask;
681 for (unsigned i = 0; i < VF; i++)
682 Mask.push_back(Builder.getInt32(Start + i * Stride));
683
684 return ConstantVector::get(Mask);
685}
686
687Constant *llvm::createSequentialMask(IRBuilder<> &Builder, unsigned Start,
688 unsigned NumInts, unsigned NumUndefs) {
689 SmallVector<Constant *, 16> Mask;
690 for (unsigned i = 0; i < NumInts; i++)
691 Mask.push_back(Builder.getInt32(Start + i));
692
693 Constant *Undef = UndefValue::get(Builder.getInt32Ty());
694 for (unsigned i = 0; i < NumUndefs; i++)
695 Mask.push_back(Undef);
696
697 return ConstantVector::get(Mask);
698}
699
700/// A helper function for concatenating vectors. This function concatenates two
701/// vectors having the same element type. If the second vector has fewer
702/// elements than the first, it is padded with undefs.
703static Value *concatenateTwoVectors(IRBuilder<> &Builder, Value *V1,
704 Value *V2) {
705 VectorType *VecTy1 = dyn_cast<VectorType>(V1->getType());
706 VectorType *VecTy2 = dyn_cast<VectorType>(V2->getType());
707 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 709, __PRETTY_FUNCTION__))
708 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 709, __PRETTY_FUNCTION__))
709 "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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 709, __PRETTY_FUNCTION__))
;
710
711 unsigned NumElts1 = VecTy1->getNumElements();
712 unsigned NumElts2 = VecTy2->getNumElements();
713 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 713, __PRETTY_FUNCTION__))
;
714
715 if (NumElts1 > NumElts2) {
716 // Extend with UNDEFs.
717 Constant *ExtMask =
718 createSequentialMask(Builder, 0, NumElts2, NumElts1 - NumElts2);
719 V2 = Builder.CreateShuffleVector(V2, UndefValue::get(VecTy2), ExtMask);
720 }
721
722 Constant *Mask = createSequentialMask(Builder, 0, NumElts1 + NumElts2, 0);
723 return Builder.CreateShuffleVector(V1, V2, Mask);
724}
725
726Value *llvm::concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value *> Vecs) {
727 unsigned NumVecs = Vecs.size();
728 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 728, __PRETTY_FUNCTION__))
;
729
730 SmallVector<Value *, 8> ResList;
731 ResList.append(Vecs.begin(), Vecs.end());
732 do {
733 SmallVector<Value *, 8> TmpList;
734 for (unsigned i = 0; i < NumVecs - 1; i += 2) {
735 Value *V0 = ResList[i], *V1 = ResList[i + 1];
736 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 737, __PRETTY_FUNCTION__))
737 "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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 737, __PRETTY_FUNCTION__))
;
738
739 TmpList.push_back(concatenateTwoVectors(Builder, V0, V1));
740 }
741
742 // Push the last vector if the total number of vectors is odd.
743 if (NumVecs % 2 != 0)
744 TmpList.push_back(ResList[NumVecs - 1]);
745
746 ResList = TmpList;
747 NumVecs = ResList.size();
748 } while (NumVecs > 1);
749
750 return ResList[0];
751}
752
753bool llvm::maskIsAllZeroOrUndef(Value *Mask) {
754 auto *ConstMask = dyn_cast<Constant>(Mask);
755 if (!ConstMask)
756 return false;
757 if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
758 return true;
759 for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
760 ++I) {
761 if (auto *MaskElt = ConstMask->getAggregateElement(I))
762 if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
763 continue;
764 return false;
765 }
766 return true;
767}
768
769
770bool llvm::maskIsAllOneOrUndef(Value *Mask) {
771 auto *ConstMask = dyn_cast<Constant>(Mask);
772 if (!ConstMask)
773 return false;
774 if (ConstMask->isAllOnesValue() || isa<UndefValue>(ConstMask))
775 return true;
776 for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
777 ++I) {
778 if (auto *MaskElt = ConstMask->getAggregateElement(I))
779 if (MaskElt->isAllOnesValue() || isa<UndefValue>(MaskElt))
780 continue;
781 return false;
782 }
783 return true;
784}
785
786/// TODO: This is a lot like known bits, but for
787/// vectors. Is there something we can common this with?
788APInt llvm::possiblyDemandedEltsInMask(Value *Mask) {
789
790 const unsigned VWidth = cast<VectorType>(Mask->getType())->getNumElements();
791 APInt DemandedElts = APInt::getAllOnesValue(VWidth);
792 if (auto *CV = dyn_cast<ConstantVector>(Mask))
793 for (unsigned i = 0; i < VWidth; i++)
794 if (CV->getAggregateElement(i)->isNullValue())
795 DemandedElts.clearBit(i);
796 return DemandedElts;
797}
798
799bool InterleavedAccessInfo::isStrided(int Stride) {
800 unsigned Factor = std::abs(Stride);
801 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
802}
803
804void InterleavedAccessInfo::collectConstStrideAccesses(
805 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
806 const ValueToValueMap &Strides) {
807 auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
808
809 // Since it's desired that the load/store instructions be maintained in
810 // "program order" for the interleaved access analysis, we have to visit the
811 // blocks in the loop in reverse postorder (i.e., in a topological order).
812 // Such an ordering will ensure that any load/store that may be executed
813 // before a second load/store will precede the second load/store in
814 // AccessStrideInfo.
815 LoopBlocksDFS DFS(TheLoop);
816 DFS.perform(LI);
817 for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
818 for (auto &I : *BB) {
819 auto *LI = dyn_cast<LoadInst>(&I);
820 auto *SI = dyn_cast<StoreInst>(&I);
821 if (!LI && !SI)
822 continue;
823
824 Value *Ptr = getLoadStorePointerOperand(&I);
825 // We don't check wrapping here because we don't know yet if Ptr will be
826 // part of a full group or a group with gaps. Checking wrapping for all
827 // pointers (even those that end up in groups with no gaps) will be overly
828 // conservative. For full groups, wrapping should be ok since if we would
829 // wrap around the address space we would do a memory access at nullptr
830 // even without the transformation. The wrapping checks are therefore
831 // deferred until after we've formed the interleaved groups.
832 int64_t Stride = getPtrStride(PSE, Ptr, TheLoop, Strides,
833 /*Assume=*/true, /*ShouldCheckWrap=*/false);
834
835 const SCEV *Scev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
836 PointerType *PtrTy = cast<PointerType>(Ptr->getType());
837 uint64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());
838
839 // An alignment of 0 means target ABI alignment.
840 MaybeAlign Alignment = MaybeAlign(getLoadStoreAlignment(&I));
841 if (!Alignment)
842 Alignment = Align(DL.getABITypeAlignment(PtrTy->getElementType()));
843
844 AccessStrideInfo[&I] = StrideDescriptor(Stride, Scev, Size, *Alignment);
845 }
846}
847
848// Analyze interleaved accesses and collect them into interleaved load and
849// store groups.
850//
851// When generating code for an interleaved load group, we effectively hoist all
852// loads in the group to the location of the first load in program order. When
853// generating code for an interleaved store group, we sink all stores to the
854// location of the last store. This code motion can change the order of load
855// and store instructions and may break dependences.
856//
857// The code generation strategy mentioned above ensures that we won't violate
858// any write-after-read (WAR) dependences.
859//
860// E.g., for the WAR dependence: a = A[i]; // (1)
861// A[i] = b; // (2)
862//
863// The store group of (2) is always inserted at or below (2), and the load
864// group of (1) is always inserted at or above (1). Thus, the instructions will
865// never be reordered. All other dependences are checked to ensure the
866// correctness of the instruction reordering.
867//
868// The algorithm visits all memory accesses in the loop in bottom-up program
869// order. Program order is established by traversing the blocks in the loop in
870// reverse postorder when collecting the accesses.
871//
872// We visit the memory accesses in bottom-up order because it can simplify the
873// construction of store groups in the presence of write-after-write (WAW)
874// dependences.
875//
876// E.g., for the WAW dependence: A[i] = a; // (1)
877// A[i] = b; // (2)
878// A[i + 1] = c; // (3)
879//
880// We will first create a store group with (3) and (2). (1) can't be added to
881// this group because it and (2) are dependent. However, (1) can be grouped
882// with other accesses that may precede it in program order. Note that a
883// bottom-up order does not imply that WAW dependences should not be checked.
884void InterleavedAccessInfo::analyzeInterleaving(
885 bool EnablePredicatedInterleavedMemAccesses) {
886 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
887 const ValueToValueMap &Strides = LAI->getSymbolicStrides();
888
889 // Holds all accesses with a constant stride.
890 MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
891 collectConstStrideAccesses(AccessStrideInfo, Strides);
892
893 if (AccessStrideInfo.empty())
3
Assuming the condition is false
4
Taking false branch
894 return;
895
896 // Collect the dependences in the loop.
897 collectDependences();
898
899 // Holds all interleaved store groups temporarily.
900 SmallSetVector<InterleaveGroup<Instruction> *, 4> StoreGroups;
901 // Holds all interleaved load groups temporarily.
902 SmallSetVector<InterleaveGroup<Instruction> *, 4> LoadGroups;
903
904 // Search in bottom-up program order for pairs of accesses (A and B) that can
905 // form interleaved load or store groups. In the algorithm below, access A
906 // precedes access B in program order. We initialize a group for B in the
907 // outer loop of the algorithm, and then in the inner loop, we attempt to
908 // insert each A into B's group if:
909 //
910 // 1. A and B have the same stride,
911 // 2. A and B have the same memory object size, and
912 // 3. A belongs in B's group according to its distance from B.
913 //
914 // Special care is taken to ensure group formation will not break any
915 // dependences.
916 for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
15
Loop condition is true. Entering loop body
917 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> > > >>'
918 Instruction *B = BI->first;
919 StrideDescriptor DesB = BI->second;
920
921 // Initialize a group for B if it has an allowable stride. Even if we don't
922 // create a group for B, we continue with the bottom-up algorithm to ensure
923 // we don't break any of B's dependences.
924 InterleaveGroup<Instruction> *Group = nullptr;
16
'Group' initialized to a null pointer value
925 if (isStrided(DesB.Stride) &&
926 (!isPredicated(B->getParent()) || EnablePredicatedInterleavedMemAccesses)) {
927 Group = getInterleaveGroup(B);
928 if (!Group) {
929 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)
930 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Creating an interleave group with:"
<< *B << '\n'; } } while (false)
;
931 Group = createInterleaveGroup(B, DesB.Stride, DesB.Alignment);
932 }
933 if (B->mayWriteToMemory())
934 StoreGroups.insert(Group);
935 else
936 LoadGroups.insert(Group);
937 }
938
939 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
940 Instruction *A = AI->first;
941 StrideDescriptor DesA = AI->second;
942
943 // Our code motion strategy implies that we can't have dependences
944 // between accesses in an interleaved group and other accesses located
945 // between the first and last member of the group. Note that this also
946 // means that a group can't have more than one member at a given offset.
947 // The accesses in a group can have dependences with other accesses, but
948 // we must ensure we don't extend the boundaries of the group such that
949 // we encompass those dependent accesses.
950 //
951 // For example, assume we have the sequence of accesses shown below in a
952 // stride-2 loop:
953 //
954 // (1, 2) is a group | A[i] = a; // (1)
955 // | A[i-1] = b; // (2) |
956 // A[i-3] = c; // (3)
957 // A[i] = d; // (4) | (2, 4) is not a group
958 //
959 // Because accesses (2) and (3) are dependent, we can group (2) with (1)
960 // but not with (4). If we did, the dependent access (3) would be within
961 // the boundaries of the (2, 4) group.
962 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
963 // If a dependence exists and A is already in a group, we know that A
964 // must be a store since A precedes B and WAR dependences are allowed.
965 // Thus, A would be sunk below B. We release A's group to prevent this
966 // illegal code motion. A will then be free to form another group with
967 // instructions that precede it.
968 if (isInterleaved(A)) {
969 InterleaveGroup<Instruction> *StoreGroup = getInterleaveGroup(A);
970
971 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)
972 "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)
;
973
974 StoreGroups.remove(StoreGroup);
975 releaseGroup(StoreGroup);
976 }
977
978 // If a dependence exists and A is not already in a group (or it was
979 // and we just released it), B might be hoisted above A (if B is a
980 // load) or another store might be sunk below A (if B is a store). In
981 // either case, we can't add additional instructions to B's group. B
982 // will only form a group with instructions that it precedes.
983 break;
984 }
985
986 // At this point, we've checked for illegal code motion. If either A or B
987 // isn't strided, there's nothing left to do.
988 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
989 continue;
34
Execution continues on line 939
990
991 // Ignore A if it's already in a group or isn't the same kind of memory
992 // operation as B.
993 // Note that mayReadFromMemory() isn't mutually exclusive to
994 // mayWriteToMemory in the case of atomic loads. We shouldn't see those
995 // here, canVectorizeMemory() should have returned false - except for the
996 // case we asked for optimization remarks.
997 if (isInterleaved(A) ||
63
Assuming the condition is false
66
Taking false branch
998 (A->mayReadFromMemory() != B->mayReadFromMemory()) ||
64
Assuming the condition is false
999 (A->mayWriteToMemory() != B->mayWriteToMemory()))
65
Assuming the condition is false
1000 continue;
1001
1002 // Check rules 1 and 2. Ignore A if its stride or size is different from
1003 // that of B.
1004 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
1005 continue;
1006
1007 // Ignore A if the memory object of A and B don't belong to the same
1008 // address space
1009 if (getLoadStoreAddressSpace(A) != getLoadStoreAddressSpace(B))
70
Assuming the condition is false
71
Taking false branch
1010 continue;
1011
1012 // Calculate the distance from A to B.
1013 const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
72
Assuming the object is a 'SCEVConstant'
1014 PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
1015 if (!DistToB
72.1
'DistToB' is non-null
72.1
'DistToB' is non-null
72.1
'DistToB' is non-null
)
73
Taking false branch
1016 continue;
1017 int64_t DistanceToB = DistToB->getAPInt().getSExtValue();
1018
1019 // Check rule 3. Ignore A if its distance to B is not a multiple of the
1020 // size.
1021 if (DistanceToB % static_cast<int64_t>(DesB.Size))
74
Assuming the condition is false
75
Taking false branch
1022 continue;
1023
1024 // All members of a predicated interleave-group must have the same predicate,
1025 // and currently must reside in the same BB.
1026 BasicBlock *BlockA = A->getParent();
1027 BasicBlock *BlockB = B->getParent();
1028 if ((isPredicated(BlockA) || isPredicated(BlockB)) &&
76
Assuming the condition is true
79
Taking false branch
1029 (!EnablePredicatedInterleavedMemAccesses || BlockA != BlockB))
77
Assuming 'EnablePredicatedInterleavedMemAccesses' is true
78
Assuming 'BlockA' is equal to 'BlockB'
1030 continue;
1031
1032 // The index of A is the index of B plus A's distance to B in multiples
1033 // of the size.
1034 int IndexA =
1035 Group->getIndex(B) + DistanceToB / static_cast<int64_t>(DesB.Size);
80
Called C++ object pointer is null
1036
1037 // Try to insert A into B's group.
1038 if (Group->insertMember(A, IndexA, DesA.Alignment)) {
1039 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)
1040 << " 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)
1041 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Inserted:" << *
A << '\n' << " into the interleave group with"
<< *B << '\n'; } } while (false)
;
1042 InterleaveGroupMap[A] = Group;
1043
1044 // Set the first load in program order as the insert position.
1045 if (A->mayReadFromMemory())
1046 Group->setInsertPos(A);
1047 }
1048 } // Iteration over A accesses.
1049 } // Iteration over B accesses.
1050
1051 // Remove interleaved store groups with gaps.
1052 for (auto *Group : StoreGroups)
1053 if (Group->getNumMembers() != Group->getFactor()) {
1054 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved store group due "
"to gaps.\n"; } } while (false)
1055 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)
1056 "to gaps.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Invalidate candidate interleaved store group due "
"to gaps.\n"; } } while (false)
;
1057 releaseGroup(Group);
1058 }
1059 // Remove interleaved groups with gaps (currently only loads) whose memory
1060 // accesses may wrap around. We have to revisit the getPtrStride analysis,
1061 // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
1062 // not check wrapping (see documentation there).
1063 // FORNOW we use Assume=false;
1064 // TODO: Change to Assume=true but making sure we don't exceed the threshold
1065 // of runtime SCEV assumptions checks (thereby potentially failing to
1066 // vectorize altogether).
1067 // Additional optional optimizations:
1068 // TODO: If we are peeling the loop and we know that the first pointer doesn't
1069 // wrap then we can deduce that all pointers in the group don't wrap.
1070 // This means that we can forcefully peel the loop in order to only have to
1071 // check the first pointer for no-wrap. When we'll change to use Assume=true
1072 // we'll only need at most one runtime check per interleaved group.
1073 for (auto *Group : LoadGroups) {
1074 // Case 1: A full group. Can Skip the checks; For full groups, if the wide
1075 // load would wrap around the address space we would do a memory access at
1076 // nullptr even without the transformation.
1077 if (Group->getNumMembers() == Group->getFactor())
1078 continue;
1079
1080 // Case 2: If first and last members of the group don't wrap this implies
1081 // that all the pointers in the group don't wrap.
1082 // So we check only group member 0 (which is always guaranteed to exist),
1083 // and group member Factor - 1; If the latter doesn't exist we rely on
1084 // peeling (if it is a non-reversed accsess -- see Case 3).
1085 Value *FirstMemberPtr = getLoadStorePointerOperand(Group->getMember(0));
1086 if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /*Assume=*/false,
1087 /*ShouldCheckWrap=*/true)) {
1088 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)
1089 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)
1090 "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)
;
1091 releaseGroup(Group);
1092 continue;
1093 }
1094 Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
1095 if (LastMember) {
1096 Value *LastMemberPtr = getLoadStorePointerOperand(LastMember);
1097 if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /*Assume=*/false,
1098 /*ShouldCheckWrap=*/true)) {
1099 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)
1100 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)
1101 "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)
;
1102 releaseGroup(Group);
1103 }
1104 } else {
1105 // Case 3: A non-reversed interleaved load group with gaps: We need
1106 // to execute at least one scalar epilogue iteration. This will ensure
1107 // we don't speculatively access memory out-of-bounds. We only need
1108 // to look for a member at index factor - 1, since every group must have
1109 // a member at index zero.
1110 if (Group->isReverse()) {
1111 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)
1112 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)
1113 "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)
;
1114 releaseGroup(Group);
1115 continue;
1116 }
1117 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vectorutils")) { dbgs() << "LV: Interleaved group requires epilogue iteration.\n"
; } } while (false)
1118 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)
;
1119 RequiresScalarEpilogue = true;
1120 }
1121 }
1122}
1123
1124void InterleavedAccessInfo::invalidateGroupsRequiringScalarEpilogue() {
1125 // If no group had triggered the requirement to create an epilogue loop,
1126 // there is nothing to do.
1127 if (!requiresScalarEpilogue())
1128 return;
1129
1130 // Avoid releasing a Group twice.
1131 SmallPtrSet<InterleaveGroup<Instruction> *, 4> DelSet;
1132 for (auto &I : InterleaveGroupMap) {
1133 InterleaveGroup<Instruction> *Group = I.second;
1134 if (Group->requiresScalarEpilogue())
1135 DelSet.insert(Group);
1136 }
1137 for (auto *Ptr : DelSet) {
1138 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)
1139 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)
1140 << "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)
1141 "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)
1142 "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)
;
1143 releaseGroup(Ptr);
1144 }
1145
1146 RequiresScalarEpilogue = false;
1147}
1148
1149template <typename InstT>
1150void InterleaveGroup<InstT>::addMetadata(InstT *NewInst) const {
1151 llvm_unreachable("addMetadata can only be used for Instruction")::llvm::llvm_unreachable_internal("addMetadata can only be used for Instruction"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 1151)
;
1152}
1153
1154namespace llvm {
1155template <>
1156void InterleaveGroup<Instruction>::addMetadata(Instruction *NewInst) const {
1157 SmallVector<Value *, 4> VL;
1158 std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
1159 [](std::pair<int, Instruction *> p) { return p.second; });
1160 propagateMetadata(NewInst, VL);
1161}
1162}
1163
1164void VFABI::getVectorVariantNames(
1165 const CallInst &CI, SmallVectorImpl<std::string> &VariantMappings) {
1166 const StringRef S =
1167 CI.getAttribute(AttributeList::FunctionIndex, VFABI::MappingsAttrName)
1168 .getValueAsString();
1169 if (S.empty())
1170 return;
1171
1172 SmallVector<StringRef, 8> ListAttr;
1173 S.split(ListAttr, ",");
1174
1175 for (auto &S : SetVector<StringRef>(ListAttr.begin(), ListAttr.end())) {
1176#ifndef NDEBUG
1177 Optional<VFInfo> Info = VFABI::tryDemangleForVFABI(S);
1178 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 1178, __PRETTY_FUNCTION__))
;
1179 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 1180, __PRETTY_FUNCTION__))
1180 "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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 1180, __PRETTY_FUNCTION__))
;
1181#endif
1182 VariantMappings.push_back(S);
1183 }
1184}
1185
1186bool VFShape::hasValidParameterList() const {
1187 for (unsigned Pos = 0, NumParams = Parameters.size(); Pos < NumParams;
1188 ++Pos) {
1189 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-10~++20200112100611+7fa5290d5bd/llvm/lib/Analysis/VectorUtils.cpp"
, 1189, __PRETTY_FUNCTION__))
;
1190
1191 switch (Parameters[Pos].ParamKind) {
1192 default: // Nothing to check.
1193 break;
1194 case VFParamKind::OMP_Linear:
1195 case VFParamKind::OMP_LinearRef:
1196 case VFParamKind::OMP_LinearVal:
1197 case VFParamKind::OMP_LinearUVal:
1198 // Compile time linear steps must be non-zero.
1199 if (Parameters[Pos].LinearStepOrPos == 0)
1200 return false;
1201 break;
1202 case VFParamKind::OMP_LinearPos:
1203 case VFParamKind::OMP_LinearRefPos:
1204 case VFParamKind::OMP_LinearValPos:
1205 case VFParamKind::OMP_LinearUValPos:
1206 // The runtime linear step must be referring to some other
1207 // parameters in the signature.
1208 if (Parameters[Pos].LinearStepOrPos >= int(NumParams))
1209 return false;
1210 // The linear step parameter must be marked as uniform.
1211 if (Parameters[Parameters[Pos].LinearStepOrPos].ParamKind !=
1212 VFParamKind::OMP_Uniform)
1213 return false;
1214 // The linear step parameter can't point at itself.
1215 if (Parameters[Pos].LinearStepOrPos == int(Pos))
1216 return false;
1217 break;
1218 case VFParamKind::GlobalPredicate:
1219 // The global predicate must be the unique. Can be placed anywhere in the
1220 // signature.
1221 for (unsigned NextPos = Pos + 1; NextPos < NumParams; ++NextPos)
1222 if (Parameters[NextPos].ParamKind == VFParamKind::GlobalPredicate)
1223 return false;
1224 break;
1225 }
1226 }
1227 return true;
1228}

/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-10~++20200112100611+7fa5290d5bd/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/IR/IRBuilder.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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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 StringRef ScalarName; // Scalar Function Name.
121 StringRef 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
135/// Function to contruct a VFInfo out of a mangled names in the
136/// following format:
137///
138/// <VFABI_name>{(<redirection>)}
139///
140/// where <VFABI_name> is the name of the vector function, mangled according
141/// to the rules described in the Vector Function ABI of the target vector
142/// extentsion (or <isa> from now on). The <VFABI_name> is in the following
143/// format:
144///
145/// _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)]
146///
147/// This methods support demangling rules for the following <isa>:
148///
149/// * AArch64: https://developer.arm.com/docs/101129/latest
150///
151/// * x86 (libmvec): https://sourceware.org/glibc/wiki/libmvec and
152/// https://sourceware.org/glibc/wiki/libmvec?action=AttachFile&do=view&target=VectorABI.txt
153///
154/// \param MangledName -> input string in the format
155/// _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)].
156Optional<VFInfo> tryDemangleForVFABI(StringRef MangledName);
157
158/// Retrieve the `VFParamKind` from a string token.
159VFParamKind getVFParamKindFromString(const StringRef Token);
160
161// Name of the attribute where the variant mappings are stored.
162static constexpr char const *MappingsAttrName = "vector-function-abi-variant";
163
164/// Populates a set of strings representing the Vector Function ABI variants
165/// associated to the CallInst CI.
166void getVectorVariantNames(const CallInst &CI,
167 SmallVectorImpl<std::string> &VariantMappings);
168} // end namespace VFABI
169
170template <typename T> class ArrayRef;
171class DemandedBits;
172class GetElementPtrInst;
173template <typename InstTy> class InterleaveGroup;
174class Loop;
175class ScalarEvolution;
176class TargetTransformInfo;
177class Type;
178class Value;
179
180namespace Intrinsic {
181typedef unsigned ID;
182}
183
184/// Identify if the intrinsic is trivially vectorizable.
185/// This method returns true if the intrinsic's argument types are all scalars
186/// for the scalar form of the intrinsic and all vectors (or scalars handled by
187/// hasVectorInstrinsicScalarOpd) for the vector form of the intrinsic.
188bool isTriviallyVectorizable(Intrinsic::ID ID);
189
190/// Identifies if the vector form of the intrinsic has a scalar operand.
191bool hasVectorInstrinsicScalarOpd(Intrinsic::ID ID, unsigned ScalarOpdIdx);
192
193/// Returns intrinsic ID for call.
194/// For the input call instruction it finds mapping intrinsic and returns
195/// its intrinsic ID, in case it does not found it return not_intrinsic.
196Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI,
197 const TargetLibraryInfo *TLI);
198
199/// Find the operand of the GEP that should be checked for consecutive
200/// stores. This ignores trailing indices that have no effect on the final
201/// pointer.
202unsigned getGEPInductionOperand(const GetElementPtrInst *Gep);
203
204/// If the argument is a GEP, then returns the operand identified by
205/// getGEPInductionOperand. However, if there is some other non-loop-invariant
206/// operand, it returns that instead.
207Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp);
208
209/// If a value has only one user that is a CastInst, return it.
210Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty);
211
212/// Get the stride of a pointer access in a loop. Looks for symbolic
213/// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
214Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp);
215
216/// Given a vector and an element number, see if the scalar value is
217/// already around as a register, for example if it were inserted then extracted
218/// from the vector.
219Value *findScalarElement(Value *V, unsigned EltNo);
220
221/// Get splat value if the input is a splat vector or return nullptr.
222/// The value may be extracted from a splat constants vector or from
223/// a sequence of instructions that broadcast a single value into a vector.
224const Value *getSplatValue(const Value *V);
225
226/// Return true if the input value is known to be a vector with all identical
227/// elements (potentially including undefined elements).
228/// This may be more powerful than the related getSplatValue() because it is
229/// not limited by finding a scalar source value to a splatted vector.
230bool isSplatValue(const Value *V, unsigned Depth = 0);
231
232/// Compute a map of integer instructions to their minimum legal type
233/// size.
234///
235/// C semantics force sub-int-sized values (e.g. i8, i16) to be promoted to int
236/// type (e.g. i32) whenever arithmetic is performed on them.
237///
238/// For targets with native i8 or i16 operations, usually InstCombine can shrink
239/// the arithmetic type down again. However InstCombine refuses to create
240/// illegal types, so for targets without i8 or i16 registers, the lengthening
241/// and shrinking remains.
242///
243/// Most SIMD ISAs (e.g. NEON) however support vectors of i8 or i16 even when
244/// their scalar equivalents do not, so during vectorization it is important to
245/// remove these lengthens and truncates when deciding the profitability of
246/// vectorization.
247///
248/// This function analyzes the given range of instructions and determines the
249/// minimum type size each can be converted to. It attempts to remove or
250/// minimize type size changes across each def-use chain, so for example in the
251/// following code:
252///
253/// %1 = load i8, i8*
254/// %2 = add i8 %1, 2
255/// %3 = load i16, i16*
256/// %4 = zext i8 %2 to i32
257/// %5 = zext i16 %3 to i32
258/// %6 = add i32 %4, %5
259/// %7 = trunc i32 %6 to i16
260///
261/// Instruction %6 must be done at least in i16, so computeMinimumValueSizes
262/// will return: {%1: 16, %2: 16, %3: 16, %4: 16, %5: 16, %6: 16, %7: 16}.
263///
264/// If the optional TargetTransformInfo is provided, this function tries harder
265/// to do less work by only looking at illegal types.
266MapVector<Instruction*, uint64_t>
267computeMinimumValueSizes(ArrayRef<BasicBlock*> Blocks,
268 DemandedBits &DB,
269 const TargetTransformInfo *TTI=nullptr);
270
271/// Compute the union of two access-group lists.
272///
273/// If the list contains just one access group, it is returned directly. If the
274/// list is empty, returns nullptr.
275MDNode *uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2);
276
277/// Compute the access-group list of access groups that @p Inst1 and @p Inst2
278/// are both in. If either instruction does not access memory at all, it is
279/// considered to be in every list.
280///
281/// If the list contains just one access group, it is returned directly. If the
282/// list is empty, returns nullptr.
283MDNode *intersectAccessGroups(const Instruction *Inst1,
284 const Instruction *Inst2);
285
286/// Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath,
287/// MD_nontemporal, MD_access_group].
288/// For K in Kinds, we get the MDNode for K from each of the
289/// elements of VL, compute their "intersection" (i.e., the most generic
290/// metadata value that covers all of the individual values), and set I's
291/// metadata for M equal to the intersection value.
292///
293/// This function always sets a (possibly null) value for each K in Kinds.
294Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL);
295
296/// Create a mask that filters the members of an interleave group where there
297/// are gaps.
298///
299/// For example, the mask for \p Group with interleave-factor 3
300/// and \p VF 4, that has only its first member present is:
301///
302/// <1,0,0,1,0,0,1,0,0,1,0,0>
303///
304/// Note: The result is a mask of 0's and 1's, as opposed to the other
305/// create[*]Mask() utilities which create a shuffle mask (mask that
306/// consists of indices).
307Constant *createBitMaskForGaps(IRBuilder<> &Builder, unsigned VF,
308 const InterleaveGroup<Instruction> &Group);
309
310/// Create a mask with replicated elements.
311///
312/// This function creates a shuffle mask for replicating each of the \p VF
313/// elements in a vector \p ReplicationFactor times. It can be used to
314/// transform a mask of \p VF elements into a mask of
315/// \p VF * \p ReplicationFactor elements used by a predicated
316/// interleaved-group of loads/stores whose Interleaved-factor ==
317/// \p ReplicationFactor.
318///
319/// For example, the mask for \p ReplicationFactor=3 and \p VF=4 is:
320///
321/// <0,0,0,1,1,1,2,2,2,3,3,3>
322Constant *createReplicatedMask(IRBuilder<> &Builder, unsigned ReplicationFactor,
323 unsigned VF);
324
325/// Create an interleave shuffle mask.
326///
327/// This function creates a shuffle mask for interleaving \p NumVecs vectors of
328/// vectorization factor \p VF into a single wide vector. The mask is of the
329/// form:
330///
331/// <0, VF, VF * 2, ..., VF * (NumVecs - 1), 1, VF + 1, VF * 2 + 1, ...>
332///
333/// For example, the mask for VF = 4 and NumVecs = 2 is:
334///
335/// <0, 4, 1, 5, 2, 6, 3, 7>.
336Constant *createInterleaveMask(IRBuilder<> &Builder, unsigned VF,
337 unsigned NumVecs);
338
339/// Create a stride shuffle mask.
340///
341/// This function creates a shuffle mask whose elements begin at \p Start and
342/// are incremented by \p Stride. The mask can be used to deinterleave an
343/// interleaved vector into separate vectors of vectorization factor \p VF. The
344/// mask is of the form:
345///
346/// <Start, Start + Stride, ..., Start + Stride * (VF - 1)>
347///
348/// For example, the mask for Start = 0, Stride = 2, and VF = 4 is:
349///
350/// <0, 2, 4, 6>
351Constant *createStrideMask(IRBuilder<> &Builder, unsigned Start,
352 unsigned Stride, unsigned VF);
353
354/// Create a sequential shuffle mask.
355///
356/// This function creates shuffle mask whose elements are sequential and begin
357/// at \p Start. The mask contains \p NumInts integers and is padded with \p
358/// NumUndefs undef values. The mask is of the form:
359///
360/// <Start, Start + 1, ... Start + NumInts - 1, undef_1, ... undef_NumUndefs>
361///
362/// For example, the mask for Start = 0, NumInsts = 4, and NumUndefs = 4 is:
363///
364/// <0, 1, 2, 3, undef, undef, undef, undef>
365Constant *createSequentialMask(IRBuilder<> &Builder, unsigned Start,
366 unsigned NumInts, unsigned NumUndefs);
367
368/// Concatenate a list of vectors.
369///
370/// This function generates code that concatenate the vectors in \p Vecs into a
371/// single large vector. The number of vectors should be greater than one, and
372/// their element types should be the same. The number of elements in the
373/// vectors should also be the same; however, if the last vector has fewer
374/// elements, it will be padded with undefs.
375Value *concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value *> Vecs);
376
377/// Given a mask vector of the form <Y x i1>, Return true if all of the
378/// elements of this predicate mask are false or undef. That is, return true
379/// if all lanes can be assumed inactive.
380bool maskIsAllZeroOrUndef(Value *Mask);
381
382/// Given a mask vector of the form <Y x i1>, Return true if all of the
383/// elements of this predicate mask are true or undef. That is, return true
384/// if all lanes can be assumed active.
385bool maskIsAllOneOrUndef(Value *Mask);
386
387/// Given a mask vector of the form <Y x i1>, return an APInt (of bitwidth Y)
388/// for each lane which may be active.
389APInt possiblyDemandedEltsInMask(Value *Mask);
390
391/// The group of interleaved loads/stores sharing the same stride and
392/// close to each other.
393///
394/// Each member in this group has an index starting from 0, and the largest
395/// index should be less than interleaved factor, which is equal to the absolute
396/// value of the access's stride.
397///
398/// E.g. An interleaved load group of factor 4:
399/// for (unsigned i = 0; i < 1024; i+=4) {
400/// a = A[i]; // Member of index 0
401/// b = A[i+1]; // Member of index 1
402/// d = A[i+3]; // Member of index 3
403/// ...
404/// }
405///
406/// An interleaved store group of factor 4:
407/// for (unsigned i = 0; i < 1024; i+=4) {
408/// ...
409/// A[i] = a; // Member of index 0
410/// A[i+1] = b; // Member of index 1
411/// A[i+2] = c; // Member of index 2
412/// A[i+3] = d; // Member of index 3
413/// }
414///
415/// Note: the interleaved load group could have gaps (missing members), but
416/// the interleaved store group doesn't allow gaps.
417template <typename InstTy> class InterleaveGroup {
418public:
419 InterleaveGroup(uint32_t Factor, bool Reverse, Align Alignment)
420 : Factor(Factor), Reverse(Reverse), Alignment(Alignment),
421 InsertPos(nullptr) {}
422
423 InterleaveGroup(InstTy *Instr, int32_t Stride, Align Alignment)
424 : Alignment(Alignment), InsertPos(Instr) {
425 Factor = std::abs(Stride);
426 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-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 426, __PRETTY_FUNCTION__))
;
427
428 Reverse = Stride < 0;
429 Members[0] = Instr;
430 }
431
432 bool isReverse() const { return Reverse; }
433 uint32_t getFactor() const { return Factor; }
434 uint32_t getAlignment() const { return Alignment.value(); }
435 uint32_t getNumMembers() const { return Members.size(); }
436
437 /// Try to insert a new member \p Instr with index \p Index and
438 /// alignment \p NewAlign. The index is related to the leader and it could be
439 /// negative if it is the new leader.
440 ///
441 /// \returns false if the instruction doesn't belong to the group.
442 bool insertMember(InstTy *Instr, int32_t Index, Align NewAlign) {
443 // Make sure the key fits in an int32_t.
444 Optional<int32_t> MaybeKey = checkedAdd(Index, SmallestKey);
445 if (!MaybeKey)
446 return false;
447 int32_t Key = *MaybeKey;
448
449 // Skip if there is already a member with the same index.
450 if (Members.find(Key) != Members.end())
451 return false;
452
453 if (Key > LargestKey) {
454 // The largest index is always less than the interleave factor.
455 if (Index >= static_cast<int32_t>(Factor))
456 return false;
457
458 LargestKey = Key;
459 } else if (Key < SmallestKey) {
460
461 // Make sure the largest index fits in an int32_t.
462 Optional<int32_t> MaybeLargestIndex = checkedSub(LargestKey, Key);
463 if (!MaybeLargestIndex)
464 return false;
465
466 // The largest index is always less than the interleave factor.
467 if (*MaybeLargestIndex >= static_cast<int64_t>(Factor))
468 return false;
469
470 SmallestKey = Key;
471 }
472
473 // It's always safe to select the minimum alignment.
474 Alignment = std::min(Alignment, NewAlign);
475 Members[Key] = Instr;
476 return true;
477 }
478
479 /// Get the member with the given index \p Index
480 ///
481 /// \returns nullptr if contains no such member.
482 InstTy *getMember(uint32_t Index) const {
483 int32_t Key = SmallestKey + Index;
484 auto Member = Members.find(Key);
485 if (Member == Members.end())
486 return nullptr;
487
488 return Member->second;
489 }
490
491 /// Get the index for the given member. Unlike the key in the member
492 /// map, the index starts from 0.
493 uint32_t getIndex(const InstTy *Instr) const {
494 for (auto I : Members) {
495 if (I.second == Instr)
496 return I.first - SmallestKey;
497 }
498
499 llvm_unreachable("InterleaveGroup contains no such member")::llvm::llvm_unreachable_internal("InterleaveGroup contains no such member"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 499)
;
500 }
501
502 InstTy *getInsertPos() const { return InsertPos; }
503 void setInsertPos(InstTy *Inst) { InsertPos = Inst; }
504
505 /// Add metadata (e.g. alias info) from the instructions in this group to \p
506 /// NewInst.
507 ///
508 /// FIXME: this function currently does not add noalias metadata a'la
509 /// addNewMedata. To do that we need to compute the intersection of the
510 /// noalias info from all members.
511 void addMetadata(InstTy *NewInst) const;
512
513 /// Returns true if this Group requires a scalar iteration to handle gaps.
514 bool requiresScalarEpilogue() const {
515 // If the last member of the Group exists, then a scalar epilog is not
516 // needed for this group.
517 if (getMember(getFactor() - 1))
518 return false;
519
520 // We have a group with gaps. It therefore cannot be a group of stores,
521 // and it can't be a reversed access, because such groups get invalidated.
522 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-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 523, __PRETTY_FUNCTION__))
523 "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-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 523, __PRETTY_FUNCTION__))
;
524 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-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 524, __PRETTY_FUNCTION__))
;
525
526 // This is a group of loads, with gaps, and without a last-member
527 return true;
528 }
529
530private:
531 uint32_t Factor; // Interleave Factor.
532 bool Reverse;
533 Align Alignment;
534 DenseMap<int32_t, InstTy *> Members;
535 int32_t SmallestKey = 0;
536 int32_t LargestKey = 0;
537
538 // To avoid breaking dependences, vectorized instructions of an interleave
539 // group should be inserted at either the first load or the last store in
540 // program order.
541 //
542 // E.g. %even = load i32 // Insert Position
543 // %add = add i32 %even // Use of %even
544 // %odd = load i32
545 //
546 // store i32 %even
547 // %odd = add i32 // Def of %odd
548 // store i32 %odd // Insert Position
549 InstTy *InsertPos;
550};
551
552/// Drive the analysis of interleaved memory accesses in the loop.
553///
554/// Use this class to analyze interleaved accesses only when we can vectorize
555/// a loop. Otherwise it's meaningless to do analysis as the vectorization
556/// on interleaved accesses is unsafe.
557///
558/// The analysis collects interleave groups and records the relationships
559/// between the member and the group in a map.
560class InterleavedAccessInfo {
561public:
562 InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
563 DominatorTree *DT, LoopInfo *LI,
564 const LoopAccessInfo *LAI)
565 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
566
567 ~InterleavedAccessInfo() { reset(); }
568
569 /// Analyze the interleaved accesses and collect them in interleave
570 /// groups. Substitute symbolic strides using \p Strides.
571 /// Consider also predicated loads/stores in the analysis if
572 /// \p EnableMaskedInterleavedGroup is true.
573 void analyzeInterleaving(bool EnableMaskedInterleavedGroup);
574
575 /// Invalidate groups, e.g., in case all blocks in loop will be predicated
576 /// contrary to original assumption. Although we currently prevent group
577 /// formation for predicated accesses, we may be able to relax this limitation
578 /// in the future once we handle more complicated blocks.
579 void reset() {
580 InterleaveGroupMap.clear();
581 for (auto *Ptr : InterleaveGroups)
582 delete Ptr;
583 InterleaveGroups.clear();
584 RequiresScalarEpilogue = false;
585 }
586
587
588 /// Check if \p Instr belongs to any interleave group.
589 bool isInterleaved(Instruction *Instr) const {
590 return InterleaveGroupMap.find(Instr) != InterleaveGroupMap.end();
591 }
592
593 /// Get the interleave group that \p Instr belongs to.
594 ///
595 /// \returns nullptr if doesn't have such group.
596 InterleaveGroup<Instruction> *
597 getInterleaveGroup(const Instruction *Instr) const {
598 if (InterleaveGroupMap.count(Instr))
599 return InterleaveGroupMap.find(Instr)->second;
600 return nullptr;
601 }
602
603 iterator_range<SmallPtrSetIterator<llvm::InterleaveGroup<Instruction> *>>
604 getInterleaveGroups() {
605 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
606 }
607
608 /// Returns true if an interleaved group that may access memory
609 /// out-of-bounds requires a scalar epilogue iteration for correctness.
610 bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }
611
612 /// Invalidate groups that require a scalar epilogue (due to gaps). This can
613 /// happen when optimizing for size forbids a scalar epilogue, and the gap
614 /// cannot be filtered by masking the load/store.
615 void invalidateGroupsRequiringScalarEpilogue();
616
617private:
618 /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
619 /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
620 /// The interleaved access analysis can also add new predicates (for example
621 /// by versioning strides of pointers).
622 PredicatedScalarEvolution &PSE;
623
624 Loop *TheLoop;
625 DominatorTree *DT;
626 LoopInfo *LI;
627 const LoopAccessInfo *LAI;
628
629 /// True if the loop may contain non-reversed interleaved groups with
630 /// out-of-bounds accesses. We ensure we don't speculatively access memory
631 /// out-of-bounds by executing at least one scalar epilogue iteration.
632 bool RequiresScalarEpilogue = false;
633
634 /// Holds the relationships between the members and the interleave group.
635 DenseMap<Instruction *, InterleaveGroup<Instruction> *> InterleaveGroupMap;
636
637 SmallPtrSet<InterleaveGroup<Instruction> *, 4> InterleaveGroups;
638
639 /// Holds dependences among the memory accesses in the loop. It maps a source
640 /// access to a set of dependent sink accesses.
641 DenseMap<Instruction *, SmallPtrSet<Instruction *, 2>> Dependences;
642
643 /// The descriptor for a strided memory access.
644 struct StrideDescriptor {
645 StrideDescriptor() = default;
646 StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,
647 Align Alignment)
648 : Stride(Stride), Scev(Scev), Size(Size), Alignment(Alignment) {}
649
650 // The access's stride. It is negative for a reverse access.
651 int64_t Stride = 0;
652
653 // The scalar expression of this access.
654 const SCEV *Scev = nullptr;
655
656 // The size of the memory object.
657 uint64_t Size = 0;
658
659 // The alignment of this access.
660 Align Alignment;
661 };
662
663 /// A type for holding instructions and their stride descriptors.
664 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
665
666 /// Create a new interleave group with the given instruction \p Instr,
667 /// stride \p Stride and alignment \p Align.
668 ///
669 /// \returns the newly created interleave group.
670 InterleaveGroup<Instruction> *
671 createInterleaveGroup(Instruction *Instr, int Stride, Align Alignment) {
672 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-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 673, __PRETTY_FUNCTION__))
673 "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-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/Analysis/VectorUtils.h"
, 673, __PRETTY_FUNCTION__))
;
674 InterleaveGroupMap[Instr] =
675 new InterleaveGroup<Instruction>(Instr, Stride, Alignment);
676 InterleaveGroups.insert(InterleaveGroupMap[Instr]);
677 return InterleaveGroupMap[Instr];
678 }
679
680 /// Release the group and remove all the relationships.
681 void releaseGroup(InterleaveGroup<Instruction> *Group) {
682 for (unsigned i = 0; i < Group->getFactor(); i++)
683 if (Instruction *Member = Group->getMember(i))
684 InterleaveGroupMap.erase(Member);
685
686 InterleaveGroups.erase(Group);
687 delete Group;
688 }
689
690 /// Collect all the accesses with a constant stride in program order.
691 void collectConstStrideAccesses(
692 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
693 const ValueToValueMap &Strides);
694
695 /// Returns true if \p Stride is allowed in an interleaved group.
696 static bool isStrided(int Stride);
697
698 /// Returns true if \p BB is a predicated block.
699 bool isPredicated(BasicBlock *BB) const {
700 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
701 }
702
703 /// Returns true if LoopAccessInfo can be used for dependence queries.
704 bool areDependencesValid() const {
705 return LAI && LAI->getDepChecker().getDependences();
706 }
707
708 /// Returns true if memory accesses \p A and \p B can be reordered, if
709 /// necessary, when constructing interleaved groups.
710 ///
711 /// \p A must precede \p B in program order. We return false if reordering is
712 /// not necessary or is prevented because \p A and \p B may be dependent.
713 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
714 StrideEntry *B) const {
715 // Code motion for interleaved accesses can potentially hoist strided loads
716 // and sink strided stores. The code below checks the legality of the
717 // following two conditions:
718 //
719 // 1. Potentially moving a strided load (B) before any store (A) that
720 // precedes B, or
721 //
722 // 2. Potentially moving a strided store (A) after any load or store (B)
723 // that A precedes.
724 //
725 // It's legal to reorder A and B if we know there isn't a dependence from A
726 // to B. Note that this determination is conservative since some
727 // dependences could potentially be reordered safely.
728
729 // A is potentially the source of a dependence.
730 auto *Src = A->first;
731 auto SrcDes = A->second;
732
733 // B is potentially the sink of a dependence.
734 auto *Sink = B->first;
735 auto SinkDes = B->second;
736
737 // Code motion for interleaved accesses can't violate WAR dependences.
738 // Thus, reordering is legal if the source isn't a write.
739 if (!Src->mayWriteToMemory())
29
Assuming the condition is true
30
Taking true branch
47
Assuming the condition is true
48
Taking true branch
740 return true;
31
Returning the value 1, which participates in a condition later
49
Returning the value 1, which participates in a condition later
741
742 // At least one of the accesses must be strided.
743 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
744 return true;
745
746 // If dependence information is not available from LoopAccessInfo,
747 // conservatively assume the instructions can't be reordered.
748 if (!areDependencesValid())
749 return false;
750
751 // If we know there is a dependence from source to sink, assume the
752 // instructions can't be reordered. Otherwise, reordering is legal.
753 return Dependences.find(Src) == Dependences.end() ||
754 !Dependences.lookup(Src).count(Sink);
755 }
756
757 /// Collect the dependences from LoopAccessInfo.
758 ///
759 /// We process the dependences once during the interleaved access analysis to
760 /// enable constant-time dependence queries.
761 void collectDependences() {
762 if (!areDependencesValid())
763 return;
764 auto *Deps = LAI->getDepChecker().getDependences();
765 for (auto Dep : *Deps)
766 Dependences[Dep.getSource(*LAI)].insert(Dep.getDestination(*LAI));
767 }
768};
769
770} // llvm namespace
771
772#endif