Bug Summary

File:llvm/lib/Analysis/VectorUtils.cpp
Warning:line 1034, 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 -fuse-init-array -target-cpu x86-64 -dwarf-column-info -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~+201911111502510600c19528f1809/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/include -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/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~+201911111502510600c19528f1809/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809=. -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-2019-12-09-002921-48462-1 -x c++ /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Analysis/VectorUtils.cpp

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

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