LLVM 24.0.0git
LoopVectorizationLegality.cpp
Go to the documentation of this file.
1//===- LoopVectorizationLegality.cpp --------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file provides loop vectorization legality analysis. Original code
10// resided in LoopVectorize.cpp for a long time.
11//
12// At this point, it is implemented as a utility class, not as an analysis
13// pass. It should be easy to create an analysis pass around it if there
14// is a need (but D45420 needs to happen first).
15//
16
19#include "VectorizeOptions.h"
21#include "llvm/Analysis/Loads.h"
31#include "llvm/IR/Dominators.h"
36
37using namespace llvm;
38using namespace PatternMatch;
39using namespace LoopVectorizationUtils;
40
41#define LV_NAME "loop-vectorize"
42#define DEBUG_TYPE LV_NAME
43
44/// Maximum vectorization interleave count.
45static const unsigned MaxInterleaveFactor = 16;
46
47namespace llvm {
48
49bool LoopVectorizeHints::Hint::validate(unsigned Val) {
50 switch (Kind) {
51 case HK_WIDTH:
53 case HK_INTERLEAVE:
54 return isPowerOf2_32(Val) && Val <= MaxInterleaveFactor;
55 case HK_ISVECTORIZED:
56 return (Val == 0 || Val == 1);
57 }
58 return false;
59}
60
61LoopVectorizeHints::LoopVectorizeHints(const VectorizeOptions &Opts,
62 const Loop *L,
63 bool InterleaveOnlyWhenForced,
66 : Opts(Opts),
67 Width("vectorize.width",
68 VectorizerParams::VectorizationFactor.getKnownMinValue(), HK_WIDTH),
69 Interleave("interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE),
70 Force(FK_Undefined), IsVectorized("isvectorized", 0, HK_ISVECTORIZED),
71 Predicate(FK_Undefined), Scalable(SK_Unspecified), FPUnsafe(FK_Undefined),
72 TheLoop(L), ORE(ORE) {
73 // Populate values with existing loop metadata.
74 getHintsFromMetadata();
75
76 // force-vector-interleave overrides DisableInterleaving.
79
80 // Decide whether to enable scalable vectorization.
81 auto ComputeScalable =
82 [TTI](ScalableForceKind ForceScalableHint,
83 ScalableForceKind ForceScalableOpt, unsigned ForceWidth,
84 ElementCount ForceWidthOpt) -> ScalableForceKind {
85 // Loop hints have the highest precedence.
86 assert(ForceScalableHint != SK_AlwaysScalable && "Unexpected loop hint.");
87 if (ForceScalableHint == SK_PreferScalable ||
88 ForceScalableHint == SK_FixedWidthOnly)
89 return ForceScalableHint;
90
91 // Then, consider -scalable-vectorization=(always|off|on).
92 if (ForceScalableOpt != SK_Unspecified)
93 return ForceScalableOpt;
94
95 // Then, infer scalability from a preferred VF.
96 if (ForceWidthOpt.isScalable())
97 return SK_AlwaysScalable;
98 if (ForceWidth)
99 return SK_FixedWidthOnly;
100
101 // Finally, listen to TTI.
102 if (TTI && TTI->enableScalableVectorization())
103 return SK_PreferScalable;
104
105 // Preference unspecified, fallback to fixed-length vectorization.
106 return SK_FixedWidthOnly;
107 };
108 Scalable =
109 ComputeScalable(ScalableForceKind(Scalable), Opts.scalable_vectorization,
111
112 if (IsVectorized.Value != 1)
113 // If the vectorization width and interleaving count are both 1 then
114 // consider the loop to have been already vectorized because there's
115 // nothing more that we can do.
116 IsVectorized.Value =
118 LLVM_DEBUG(if (InterleaveOnlyWhenForced && getInterleave() == 1) dbgs()
119 << "LV: Interleaving disabled by the pass manager\n");
120}
121
123 TheLoop->addIntLoopAttribute("llvm.loop.isvectorized", 1,
124 {Twine(Prefix(), "vectorize.").str(),
125 Twine(Prefix(), "interleave.").str()});
126
127 // Update internal cache.
128 IsVectorized.Value = 1;
129}
130
131void LoopVectorizeHints::reportDisallowedVectorization(
132 const StringRef DebugMsg, const StringRef RemarkName,
133 const StringRef RemarkMsg, const Loop *L) const {
134 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: " << DebugMsg << ".\n");
135 ORE.emit(OptimizationRemarkMissed(LV_NAME, RemarkName, L->getStartLoc(),
136 L->getHeader())
137 << "loop not vectorized: " << RemarkMsg);
138}
139
141 Loop *L, bool VectorizeOnlyWhenForced) const {
143 if (Force == LoopVectorizeHints::FK_Disabled) {
144 reportDisallowedVectorization("#pragma vectorize disable",
145 "MissedExplicitlyDisabled",
146 "vectorization is explicitly disabled", L);
147 } else if (hasDisableAllTransformsHint(L)) {
148 reportDisallowedVectorization("loop hasDisableAllTransformsHint",
149 "MissedTransformsDisabled",
150 "loop transformations are disabled", L);
151 } else {
152 llvm_unreachable("loop vect disabled for an unknown reason");
153 }
154 return false;
155 }
156
157 if (VectorizeOnlyWhenForced && getForce() != LoopVectorizeHints::FK_Enabled) {
158 reportDisallowedVectorization(
159 "VectorizeOnlyWhenForced is set, and no #pragma vectorize enable",
160 "MissedForceOnly", "only vectorizing loops that explicitly request it",
161 L);
162 return false;
163 }
164
165 if (getIsVectorized() == 1) {
166 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
167 // FIXME: Add interleave.disable metadata. This will allow
168 // vectorize.disable to be used without disabling the pass and errors
169 // to differentiate between disabled vectorization and a width of 1.
170 ORE.emit([&]() {
171 return OptimizationRemarkAnalysis(LV_NAME, "AllDisabled",
172 L->getStartLoc(), L->getHeader())
173 << "loop not vectorized: vectorization and interleaving are "
174 "explicitly disabled, or the loop has already been "
175 "vectorized";
176 });
177 return false;
178 }
179
180 return true;
181}
182
184 using namespace ore;
185
186 ORE.emit([&]() {
188 return OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled",
189 TheLoop->getStartLoc(),
190 TheLoop->getHeader())
191 << "loop not vectorized: vectorization is explicitly disabled";
192
193 OptimizationRemarkMissed R(LV_NAME, "MissedDetails", TheLoop->getStartLoc(),
194 TheLoop->getHeader());
195 R << "loop not vectorized";
196 if (Force == LoopVectorizeHints::FK_Enabled) {
197 R << " (Force=" << NV("Force", true);
198 if (Width.Value != 0)
199 R << ", Vector Width=" << NV("VectorWidth", getWidth());
200 if (getInterleave() != 0)
201 R << ", Interleave Count=" << NV("InterleaveCount", getInterleave());
202 R << ")";
203 }
204 return R;
205 });
206}
207
209 // An explicit fp_unsafe hint takes precedence over the vectorize.enable
210 // default.
211 if (FPUnsafe != FK_Undefined)
212 return FPUnsafe == FK_Enabled;
213
214 // Allow the vectorizer to change the order of operations if enabling
215 // loop hints are provided
216 ElementCount EC = getWidth();
217 return Opts.hints_allow_reordering &&
219 EC.getKnownMinValue() > 1);
220}
221
222void LoopVectorizeHints::getHintsFromMetadata() {
223 MDNode *LoopID = TheLoop->getLoopID();
224 if (!LoopID)
225 return;
226
227 // First operand should refer to the loop id itself.
228 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
229 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
230
231 for (const MDOperand &MDO : llvm::drop_begin(LoopID->operands())) {
232 const MDString *S = nullptr;
234
235 // The expected hint is either a MDString or a MDNode with the first
236 // operand a MDString.
237 if (const MDNode *MD = dyn_cast<MDNode>(MDO)) {
238 if (!MD || MD->getNumOperands() == 0)
239 continue;
240 S = dyn_cast<MDString>(MD->getOperand(0));
241 for (unsigned Idx = 1; Idx < MD->getNumOperands(); ++Idx)
242 Args.push_back(MD->getOperand(Idx));
243 } else {
244 S = dyn_cast<MDString>(MDO);
245 assert(Args.size() == 0 && "too many arguments for MDString");
246 }
247
248 if (!S)
249 continue;
250
251 // Check if the hint starts with the loop metadata prefix.
252 StringRef Name = S->getString();
253 // The single-operand enable/disable pair carries no argument.
254 if (Args.empty()) {
255 if (Name == "llvm.loop.vectorize.enable")
256 Force = FK_Enabled;
257 else if (Name == "llvm.loop.vectorize.disable")
258 Force = FK_Disabled;
259 else if (Name == "llvm.loop.vectorize.fp_unsafe.enable")
260 FPUnsafe = FK_Enabled;
261 else if (Name == "llvm.loop.vectorize.fp_unsafe.disable")
262 FPUnsafe = FK_Disabled;
263 else if (Name == "llvm.loop.vectorize.predicate.enable")
264 Predicate = FK_Enabled;
265 else if (Name == "llvm.loop.vectorize.predicate.disable")
266 Predicate = FK_Disabled;
267 else if (Name == "llvm.loop.vectorize.scalable.enable")
268 Scalable = SK_PreferScalable;
269 else if (Name == "llvm.loop.vectorize.scalable.disable")
270 Scalable = SK_FixedWidthOnly;
271 continue;
272 }
273 if (Args.size() == 1)
274 setHint(Name, Args[0]);
275 }
276}
277
278void LoopVectorizeHints::setHint(StringRef Name, Metadata *Arg) {
279 if (!Name.consume_front(Prefix()))
280 return;
281
282 const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(Arg);
283 if (!C)
284 return;
285 unsigned Val = C->getZExtValue();
286
287 // Force, Predicate, Scalable and FPUnsafe are omitted: they are only
288 // spelled as single-operand enable/disable nodes, which never reach
289 // setHint().
290 Hint *Hints[] = {&Width, &Interleave, &IsVectorized};
291 for (auto *H : Hints) {
292 if (Name == H->Name) {
293 if (H->validate(Val))
294 H->Value = Val;
295 else
296 LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
297 break;
298 }
299 }
300}
301
303 assert(Ty->isIntOrPtrTy() && "Expected integer or pointer type");
304
305 if (Ty->isPointerTy())
306 return DL.getIntPtrType(Ty->getContext(), Ty->getPointerAddressSpace());
307
308 // It is possible that char's or short's overflow when we ask for the loop's
309 // trip count, work around this by changing the type size.
310 if (Ty->getScalarSizeInBits() < 32)
311 return Type::getInt32Ty(Ty->getContext());
312
313 return cast<IntegerType>(Ty);
314}
315
317 Type *Ty1) {
320 return TyA->getScalarSizeInBits() > TyB->getScalarSizeInBits() ? TyA : TyB;
321}
322
323/// Returns true if A and B have same pointer operands or same SCEVs addresses
325 StoreInst *B) {
326 // Compare store
327 if (A == B)
328 return true;
329
330 // Otherwise Compare pointers
331 Value *APtr = A->getPointerOperand();
332 Value *BPtr = B->getPointerOperand();
333 if (APtr == BPtr)
334 return true;
335
336 // Otherwise compare address SCEVs
337 return SE->getSCEV(APtr) == SE->getSCEV(BPtr);
338}
339
341 if (!AllowRuntimeSCEVChecks || !TheLoop->isInnermost())
342 return;
343
344 for (BasicBlock *BB : TheLoop->blocks())
345 for (Instruction &I : *BB)
348}
349
351 Value *Ptr) const {
352 // FIXME: Currently, the set of symbolic strides is sometimes queried before
353 // it's collected. This happens from canVectorizeWithIfConvert, when the
354 // pointer is checked to reference consecutive elements suitable for a
355 // masked access.
356 // Stride versioning requires adding a SCEV equality predicate; only consult
357 // the symbolic strides when runtime SCEV checks are permitted.
358 const auto &Strides = LAI && AllowRuntimeSCEVChecks
359 ? LAI->getSymbolicStrides()
362 int Stride = getPtrStride(PSE, AccessTy, Ptr, TheLoop, *DT, Strides, false,
363 AllowRuntimeSCEVChecks ? &Predicates : nullptr)
364 .value_or(0);
365 if (Stride != 1 && Stride != -1)
366 return 0;
367 PSE.addPredicates(Predicates);
368 return Stride;
369}
370
372 return LAI->isInvariant(V);
373}
374
375namespace {
376/// A rewriter to build the SCEVs for each of the VF lanes in the expected
377/// vectorized loop, which can then be compared to detect their uniformity. This
378/// is done by replacing the AddRec SCEVs of the original scalar loop (TheLoop)
379/// with new AddRecs where the step is multiplied by StepMultiplier and Offset *
380/// Step is added. Also checks if all sub-expressions are analyzable w.r.t.
381/// uniformity.
382class SCEVAddRecForUniformityRewriter
383 : public SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter> {
384 /// Multiplier to be applied to the step of AddRecs in TheLoop.
385 unsigned StepMultiplier;
386
387 /// Offset to be added to the AddRecs in TheLoop.
388 unsigned Offset;
389
390 /// Loop for which to rewrite AddRecsFor.
391 Loop *TheLoop;
392
393 /// Is any sub-expressions not analyzable w.r.t. uniformity?
394 bool CannotAnalyze = false;
395
396 bool canAnalyze() const { return !CannotAnalyze; }
397
398public:
399 SCEVAddRecForUniformityRewriter(ScalarEvolution &SE, unsigned StepMultiplier,
400 unsigned Offset, Loop *TheLoop)
401 : SCEVRewriteVisitor(SE), StepMultiplier(StepMultiplier), Offset(Offset),
402 TheLoop(TheLoop) {}
403
404 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
405 assert(Expr->getLoop() == TheLoop &&
406 "addrec outside of TheLoop must be invariant and should have been "
407 "handled earlier");
408 // Build a new AddRec by multiplying the step by StepMultiplier and
409 // incrementing the start by Offset * step.
410 Type *Ty = Expr->getType();
411 const SCEV *Step = Expr->getStepRecurrence(SE);
412 if (!SE.isLoopInvariant(Step, TheLoop)) {
413 CannotAnalyze = true;
414 return Expr;
415 }
416 const SCEV *NewStep =
417 SE.getMulExpr(Step, SE.getConstant(Ty, StepMultiplier));
418 const SCEV *ScaledOffset = SE.getMulExpr(Step, SE.getConstant(Ty, Offset));
419 const SCEV *NewStart =
420 SE.getAddExpr(Expr->getStart(), SCEVUse(ScaledOffset));
421 return SE.getAddRecExpr(NewStart, NewStep, TheLoop, SCEV::FlagNone);
422 }
423
424 const SCEV *visit(const SCEV *S) {
425 if (CannotAnalyze || SE.isLoopInvariant(S, TheLoop))
426 return S;
428 }
429
430 const SCEV *visitUnknown(const SCEVUnknown *S) {
431 if (SE.isLoopInvariant(S, TheLoop))
432 return S;
433 // The value could vary across iterations.
434 CannotAnalyze = true;
435 return S;
436 }
437
438 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *S) {
439 // Could not analyze the expression.
440 CannotAnalyze = true;
441 return S;
442 }
443
444 static const SCEV *rewrite(const SCEV *S, ScalarEvolution &SE,
445 unsigned StepMultiplier, unsigned Offset,
446 Loop *TheLoop) {
447 /// Bail out if the expression does not contain an UDiv expression.
448 /// Uniform values which are not loop invariant require operations to strip
449 /// out the lowest bits. For now just look for UDivs and use it to avoid
450 /// re-writing UDIV-free expressions for other lanes to limit compile time.
451 if (!SCEVExprContains(S,
452 [](const SCEV *S) { return isa<SCEVUDivExpr>(S); }))
453 return SE.getCouldNotCompute();
454
455 SCEVAddRecForUniformityRewriter Rewriter(SE, StepMultiplier, Offset,
456 TheLoop);
457 const SCEV *Result = Rewriter.visit(S);
458
459 if (Rewriter.canAnalyze())
460 return Result;
461 return SE.getCouldNotCompute();
462 }
463};
464
465} // namespace
466
468 Value *V, std::optional<ElementCount> VF) const {
469 if (isInvariant(V))
470 return true;
471 if (!VF || VF->isScalable())
472 return false;
473 if (VF->isScalar())
474 return true;
475
476 // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
477 // never considered uniform.
478 auto *SE = PSE.getSE();
479 if (!SE->isSCEVable(V->getType()))
480 return false;
481 const SCEV *S = SE->getSCEV(V);
482
483 // Rewrite AddRecs in TheLoop to step by VF and check if the expression for
484 // lane 0 matches the expressions for all other lanes.
485 unsigned FixedVF = VF->getKnownMinValue();
486 const SCEV *FirstLaneExpr =
487 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF, 0, TheLoop);
488 if (isa<SCEVCouldNotCompute>(FirstLaneExpr))
489 return false;
490
491 // Make sure the expressions for lanes FixedVF-1..1 match the expression for
492 // lane 0. We check lanes in reverse order for compile-time, as frequently
493 // checking the last lane is sufficient to rule out uniformity.
494 return all_of(reverse(seq<unsigned>(1, FixedVF)), [&](unsigned I) {
495 const SCEV *IthLaneExpr =
496 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF, I, TheLoop);
497 return FirstLaneExpr == IthLaneExpr;
498 });
499}
500
502 Instruction &I, std::optional<ElementCount> VF) const {
504 if (!Ptr)
505 return false;
506 // Note: There's nothing inherent which prevents predicated loads and
507 // stores from being uniform. The current lowering simply doesn't handle
508 // it; in particular, the cost model distinguishes scatter/gather from
509 // scalar w/predication, and we currently rely on the scalar path.
510 return isUniform(Ptr, VF) && !blockNeedsPredication(I.getParent());
511}
512
513/// Returns true if the type produced by \p I can be widened. Casts from vector
514/// types and extractelement instructions cannot be widened. Struct results are
515/// only supported if \p AllowStructCalls is set, for calls whose users are all
516/// extractvalue instructions and whose struct element types can be widened.
517static bool canWidenResultType(const Instruction &I, bool AllowStructCalls) {
519 (isa<CastInst>(I) &&
520 !VectorType::isValidElementType(I.getOperand(0)->getType())))
521 return false;
522 Type *Ty = I.getType();
523 if (!isa<StructType>(Ty))
524 return canVectorizeTy(Ty);
525 return AllowStructCalls && isa<CallInst>(I) && canVectorizeTy(Ty) &&
527}
528
529/// Returns true if the types produced and stored by \p I can be widened,
530/// otherwise reports a vectorization failure for \p TheLoop and returns false.
531static bool canWidenTypes(Instruction &I, bool AllowStructCalls,
532 OptimizationRemarkEmitter *ORE, Loop *TheLoop) {
533 if (!canWidenResultType(I, AllowStructCalls)) {
534 reportVectorizationFailure("Found unvectorizable type",
535 "instruction return type cannot be vectorized",
536 "CantVectorizeInstructionReturnType", ORE,
537 TheLoop, &I);
538 return false;
539 }
540 auto *SI = dyn_cast<StoreInst>(&I);
541 if (SI && !VectorType::isValidElementType(SI->getValueOperand()->getType())) {
542 reportVectorizationFailure("Store instruction cannot be vectorized",
543 "CantVectorizeStore", ORE, TheLoop, SI);
544 return false;
545 }
546 return true;
547}
548
549/// Returns true if \p I does not use a swifterror value, otherwise reports a
550/// vectorization failure for \p TheLoop and returns false.
551/// TODO: Allow unmasked uniform accesses through loop-invariant swifterror
552/// pointers once memory operations on them are guaranteed to stay scalar.
555 Loop *TheLoop) {
556 if (none_of(I.operands(), [](Value *Op) { return Op->isSwiftError(); }))
557 return true;
558 reportVectorizationFailure("Found a use of a swifterror value",
559 "swifterror value cannot be vectorized",
560 "CantVectorizeSwiftError", ORE, TheLoop, &I);
561 return false;
562}
563
564/// Calls with operand bundles other than llvm.assume cannot be widened.
567 Loop *TheLoop) {
568 auto *CB = dyn_cast<CallBase>(&I);
569 if (!CB || !CB->hasOperandBundles() || isa<AssumeInst>(CB))
570 return true;
571 reportVectorizationFailure("Found a call with operand bundles",
572 "call with operand bundles cannot be vectorized",
573 "CantVectorizeOperandBundles", ORE, TheLoop, &I);
574 return false;
575}
576
577bool LoopVectorizationLegality::canVectorizeOuterLoop() {
578 assert(!TheLoop->isInnermost() && "We are not vectorizing an outer loop.");
579 // Store the result and return it at the end instead of exiting early, in case
580 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
581 bool Result = true;
582 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
583
584 for (BasicBlock *BB : TheLoop->blocks()) {
585 // Instructions in the loop nest are widened, so the types they produce and
586 // store must be widenable. Struct-returning calls are not supported yet.
587 // Uses of swifterror values must remain scalar. Calls with operand bundles
588 // cannot be widened.
589 for (Instruction &I : *BB) {
590 if (canWidenTypes(I, /*AllowStructCalls=*/false, ORE, TheLoop) &&
591 canVectorizeSwiftErrorUses(I, ORE, TheLoop) &&
592 canVectorizeOperandBundles(I, ORE, TheLoop))
593 continue;
594 if (!DoExtraAnalysis)
595 return false;
596 Result = false;
597 }
598
599 // Don't try to vectorize outer loops with atomic or volatile accesses.
600 for (Instruction &I : *BB) {
601 if (!I.isAtomic() && !I.isVolatile())
602 continue;
604 "Unsupported volatile or atomic memory operation",
605 "instruction cannot be vectorized", "CantVectorizeInstruction", ORE,
606 TheLoop, &I);
607 if (DoExtraAnalysis)
608 Result = false;
609 else
610 return false;
611 }
612
613 // Check whether the BB terminator is a branch. Any other terminator is
614 // not supported yet.
615 Instruction *Term = BB->getTerminator();
618 "Unsupported basic block terminator",
619 "loop control flow is not understood by vectorizer",
620 "CFGNotUnderstood", ORE, TheLoop);
621 if (DoExtraAnalysis)
622 Result = false;
623 else
624 return false;
625 }
626
627 // Check whether the branch is a supported one. Only unconditional
628 // branches, conditional branches with an outer loop uniform condition or
629 // backedges are supported.
630 // FIXME: We skip these checks when VPlan predication is enabled as we
631 // want to allow divergent branches. This whole check will be removed
632 // once VPlan predication is on by default.
633 auto *Br = dyn_cast<CondBrInst>(Term);
634 if (Br && !TheLoop->isLoopLatch(BB)) {
635 bool IsUniformCondBr = TheLoop->isLoopInvariant(Br->getCondition());
636
637 Value *Lhs = nullptr;
638 Value *Rhs = nullptr;
639 auto *SE = PSE.getSE();
640 if (match(Br->getCondition(), m_c_ICmp(m_Value(Lhs), m_Value(Rhs))) &&
641 !IsUniformCondBr && SE->isSCEVable(Lhs->getType())) {
642 const SCEV *LhsExpr = PSE.getSCEV(Lhs);
643 const SCEV *RhsExpr = PSE.getSCEV(Rhs);
644 IsUniformCondBr |= (SE->isLoopUniform(LhsExpr, TheLoop) &&
645 SE->isLoopUniform(RhsExpr, TheLoop));
646 }
647
648 // If the condition is not uniform, report a failure. We currently require
649 // uniform conditions to avoid the complexity of vectorizing divergent
650 // control flow in the outer loop.
651 if (!IsUniformCondBr) {
653 "Outer loop contains divergent conditional branch",
654 "loop control flow is not understood by vectorizer",
655 "CFGNotUnderstood", ORE, TheLoop);
656 if (DoExtraAnalysis)
657 Result = false;
658 else
659 return false;
660 }
661 }
662 }
663
664 // Each nested loop must exit via its latch only, as a region with the latch
665 // as its only exiting block is created for it. Note that the branch check
666 // rejects divergent exits, but exits with an outer-loop uniform condition
667 // are allowed through.
668 SmallVector<Loop *, 4> LoopNest = TheLoop->getLoopsInPreorder();
669 for (Loop *Lp : drop_begin(LoopNest)) {
670 if (Lp->getExitingBlock() != Lp->getLoopLatch()) {
672 "Nested loop does not exit via its latch",
673 "loop control flow is not understood by vectorizer",
674 "CFGNotUnderstood", ORE, TheLoop);
675 if (DoExtraAnalysis)
676 Result = false;
677 else
678 return false;
679 }
680 }
681
682 // Check whether we are able to set up outer loop induction.
683 if (!setupOuterLoopInductions()) {
684 reportVectorizationFailure("Unsupported outer loop Phi(s)",
685 "UnsupportedPhi", ORE, TheLoop);
686 if (DoExtraAnalysis)
687 Result = false;
688 else
689 return false;
690 }
691
692 // Like for inner loops, the widest induction type is used for the canonical
693 // IV and trip count.
694 if (!canDetermineWidestInductionType())
695 return false;
696
697 return Result;
698}
699
700bool LoopVectorizationLegality::canDetermineWidestInductionType() {
701 if (Inductions.empty()) {
703 "Did not find one integer induction var",
704 "loop induction variable could not be identified",
705 "NoInductionVariable", ORE, TheLoop);
706 return false;
707 }
708 if (!WidestIndTy) {
710 "Did not find one integer induction var",
711 "integer loop induction variable could not be identified",
712 "NoIntegerInductionVariable", ORE, TheLoop);
713 return false;
714 }
715 return true;
716}
717
718void LoopVectorizationLegality::addInductionPhi(PHINode *Phi,
719 const InductionDescriptor &ID) {
720 Inductions[Phi] = ID;
721
722 Type *PhiTy = Phi->getType();
723 const DataLayout &DL = Phi->getDataLayout();
724
725 assert((PhiTy->isIntOrPtrTy() || PhiTy->isFloatingPointTy()) &&
726 "Expected int, ptr, or FP induction phi type");
727
728 // Get the widest type.
729 if (PhiTy->isIntOrPtrTy()) {
730 if (!WidestIndTy)
731 WidestIndTy = getInductionIntegerTy(DL, PhiTy);
732 else
733 WidestIndTy = getWiderInductionTy(DL, PhiTy, WidestIndTy);
734 }
735
736 // Int inductions are special because we only allow one IV.
737 if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
738 ID.getConstStepValue() && ID.getConstStepValue()->isOne() &&
739 isa<Constant>(ID.getStartValue()) &&
740 cast<Constant>(ID.getStartValue())->isNullValue()) {
741
742 // Use the phi node with the widest type as induction. Use the last
743 // one if there are multiple (no good reason for doing this other
744 // than it is expedient). We've checked that it begins at zero and
745 // steps by one, so this is a canonical induction variable.
746 if (!PrimaryInduction || PhiTy == WidestIndTy)
747 PrimaryInduction = Phi;
748 }
749
750 LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n");
751}
752
753bool LoopVectorizationLegality::addConditionalInduction(
754 PHINode *Phi, const ConditionalInductionDescriptor &CondID) {
755 DenseMap<Value *, const SCEVAddRecExpr *> CompressedPtrsForCondID;
756 if (!collectCompressedPtrs(CompressedPtrsForCondID, *TheLoop, CondID,
757 *PSE.getSE())) {
759 "Unsupported user of conditional induction found",
760 "UnsupportedConditionalInductionUse", ORE, TheLoop);
761 return false;
762 }
763
764 ConditionalInductions[Phi] = CondID;
765
766 for (auto [Ptr, PtrAddRec] : CompressedPtrsForCondID) {
767 LLVM_DEBUG(dbgs() << "LV: Found compressed pointer: " << *Ptr << '\n');
768 assert(PtrAddRec->isAffine() && "Expected affine SCEVAddRecExpr");
769 CompressedPtrs[Ptr] = CompressedPtrInfo{Phi, PtrAddRec};
770 }
771
772 return true;
773}
774
775/// Returns true if \p ID is a pointer induction with a non-constant step. Such
776/// inductions are rejected unless -lv-strided-pointer-ivs is set, to preserve
777/// historical vectorizer behavior after a generalization of the IVDescriptor
778/// code. The intent is to remove this check, but issues around code quality
779/// for such loops have to be fixed first.
781 const VectorizeOptions &Opts) {
782 if (Opts.lv_strided_pointer_ivs)
783 return false;
784 return ID.getKind() == InductionDescriptor::IK_PtrInduction &&
785 !ID.getConstStepValue();
786}
787
788bool LoopVectorizationLegality::setupOuterLoopInductions() {
789 BasicBlock *Header = TheLoop->getHeader();
790
791 // Returns true if a given Phi is a supported induction.
792 auto IsSupportedPhi = [&](PHINode &Phi) -> bool {
794 if (InductionDescriptor::isInductionPHI(&Phi, TheLoop, PSE, ID) &&
795 (ID.getKind() == InductionDescriptor::IK_IntInduction ||
796 ID.getKind() == InductionDescriptor::IK_PtrInduction) &&
798 addInductionPhi(&Phi, ID);
799 return true;
800 }
801 // Bail out for any Phi in the outer loop header that is not a supported
802 // induction.
804 dbgs() << "LV: Found unsupported PHI for outer loop vectorization.\n");
805 return false;
806 };
807
808 return llvm::all_of(Header->phis(), IsSupportedPhi);
809}
810
811/// Checks if a function is scalarizable according to the TLI, in
812/// the sense that it should be vectorized and then expanded in
813/// multiple scalar calls. This is represented in the
814/// TLI via mappings that do not specify a vector name, as in the
815/// following example:
816///
817/// const VecDesc VecIntrinsics[] = {
818/// {"llvm.phx.abs.i32", "", 4}
819/// };
820static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI) {
821 const StringRef ScalarName = CI.getCalledFunction()->getName();
822 bool Scalarize = TLI.isFunctionVectorizable(ScalarName);
823 // Check that all known VFs are not associated to a vector
824 // function, i.e. the vector name is emty.
825 if (Scalarize) {
826 ElementCount WidestFixedVF, WidestScalableVF;
827 TLI.getWidestVF(ScalarName, WidestFixedVF, WidestScalableVF);
829 ElementCount::isKnownLE(VF, WidestFixedVF); VF *= 2)
830 Scalarize &= !TLI.isFunctionVectorizable(ScalarName, VF);
832 ElementCount::isKnownLE(VF, WidestScalableVF); VF *= 2)
833 Scalarize &= !TLI.isFunctionVectorizable(ScalarName, VF);
834 assert((WidestScalableVF.isZero() || !Scalarize) &&
835 "Caller may decide to scalarize a variant using a scalable VF");
836 }
837 return Scalarize;
838}
839
840bool LoopVectorizationLegality::canVectorizeInstrs() {
841 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
842 bool Result = true;
843
844 // For each block in the loop.
845 for (BasicBlock *BB : TheLoop->blocks()) {
846 // Scan the instructions in the block and look for hazards.
847 for (Instruction &I : *BB) {
848 Result &= canVectorizeInstr(I);
849 if (!DoExtraAnalysis && !Result)
850 return false;
851 }
852 }
853
854 if (!PrimaryInduction) {
855 if (!canDetermineWidestInductionType())
856 return false;
857 LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
858 }
859
860 // Now we know the widest induction type, check if our found induction
861 // is the same size. If it's not, unset it here.
862 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
863 PrimaryInduction = nullptr;
864
865 return Result;
866}
867
868bool LoopVectorizationLegality::canVectorizeInstr(Instruction &I) {
869 BasicBlock *BB = I.getParent();
870 BasicBlock *Header = TheLoop->getHeader();
871
872 if (auto *Phi = dyn_cast<PHINode>(&I)) {
873 Type *PhiTy = Phi->getType();
874 // Check that this PHI type is allowed.
875 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
876 !PhiTy->isPointerTy()) {
878 "Found a non-int non-pointer PHI",
879 "loop control flow is not understood by vectorizer",
880 "CFGNotUnderstood", ORE, TheLoop);
881 return false;
882 }
883
884 // If this PHINode is not in the header block, then we know that we
885 // can convert it to select during if-conversion. No need to check if
886 // the PHIs in this block are induction or reduction variables.
887 if (BB != Header) {
888 // Non-header phi nodes that have outside uses can be vectorized. Unsafe
889 // cyclic dependencies with header phis are identified during legalization
890 // for reduction, induction and fixed order recurrences.
891 return true;
892 }
893
894 // We only allow if-converted PHIs with exactly two incoming values.
895 if (Phi->getNumIncomingValues() != 2) {
897 "Found an invalid PHI",
898 "loop control flow is not understood by vectorizer",
899 "CFGNotUnderstood", ORE, TheLoop, Phi);
900 return false;
901 }
902
903 RecurrenceDescriptor RedDes;
904 if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC, DT,
905 PSE.getSE())) {
906 Requirements->addExactFPMathInst(RedDes.getExactFPMathInst());
907 Reductions[Phi] = std::move(RedDes);
910 RedDes.getRecurrenceKind())) &&
911 "Only min/max recurrences are allowed to have multiple uses "
912 "currently");
913 return true;
914 }
915
916 InductionDescriptor ID;
917 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID) &&
919 addInductionPhi(Phi, ID);
920 Requirements->addExactFPMathInst(ID.getExactFPMathInst());
921 return true;
922 }
923
924 ConditionalInductionDescriptor CondID;
925 if (Opts.lv_compressing_patterns &&
927 Phi, TheLoop, CondID, *PSE.getSE())) {
928 return addConditionalInduction(Phi, CondID);
929 }
930
931 if (RecurrenceDescriptor::isFixedOrderRecurrence(Phi, TheLoop, DT)) {
932 FixedOrderRecurrences.insert(Phi);
933 return true;
934 }
935
936 // As a last resort, coerce the PHI to a AddRec expression
937 // and re-try classifying it a an induction PHI.
938 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID, true) &&
940 addInductionPhi(Phi, ID);
941 return true;
942 }
943
945 reportVectorizationFailure("Found a disallowed pointer induction",
946 "pointer induction with a non-constant step "
947 "could not be vectorized",
948 "StridedPointerInduction", ORE, TheLoop, Phi);
949 return false;
950 }
951
952 reportVectorizationFailure("Found an unidentified PHI",
953 "value that could not be identified as "
954 "reduction is used outside the loop",
955 "NonReductionValueUsedOutsideLoop", ORE, TheLoop,
956 Phi);
957 return false;
958 } // end of PHI handling
959
960 if (!canVectorizeSwiftErrorUses(I, ORE, TheLoop) ||
961 !canVectorizeOperandBundles(I, ORE, TheLoop))
962 return false;
963
964 // We handle calls that:
965 // * Have a mapping to an IR intrinsic.
966 // * Have a vector version available.
967 auto *CI = dyn_cast<CallInst>(&I);
968
969 if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
970 !(CI->getCalledFunction() && TLI &&
971 (!VFDatabase::getMappings(*CI).empty() || isTLIScalarize(*TLI, *CI)))) {
972 // If the call is a recognized math libary call, it is likely that
973 // we can vectorize it given loosened floating-point constraints.
974 bool IsMathLibCall =
975 TLI && CI->getCalledFunction() && CI->getType()->isFloatingPointTy() &&
976 TLI->hasOptimizedCodeGen(
977 TLI->getLibFunc(CI->getCalledFunction()->getName()));
978
979 if (IsMathLibCall) {
980 // TODO: Ideally, we should not use clang-specific language here,
981 // but it's hard to provide meaningful yet generic advice.
982 // Also, should this be guarded by allowExtraAnalysis() and/or be part
983 // of the returned info from isFunctionVectorizable()?
985 "Found a non-intrinsic callsite",
986 "library call cannot be vectorized. "
987 "Try compiling with -fno-math-errno, -ffast-math, "
988 "or similar flags",
989 "CantVectorizeLibcall", ORE, TheLoop, CI);
990 } else {
991 reportVectorizationFailure("Found a non-intrinsic callsite",
992 "call instruction cannot be vectorized",
993 "CantVectorizeLibcall", ORE, TheLoop, CI);
994 }
995 return false;
996 }
997
998 // Some intrinsics have scalar arguments and should be same in order for
999 // them to be vectorized (i.e. loop invariant).
1000 if (CI) {
1001 auto *SE = PSE.getSE();
1002 Intrinsic::ID IntrinID = getVectorIntrinsicIDForCall(CI, TLI);
1003 for (unsigned Idx = 0; Idx < CI->arg_size(); ++Idx)
1004 if (isVectorIntrinsicWithScalarOpAtArg(IntrinID, Idx, TTI)) {
1005 if (!SE->isLoopInvariant(PSE.getSCEV(CI->getOperand(Idx)), TheLoop)) {
1007 "Found unvectorizable intrinsic",
1008 "intrinsic instruction cannot be vectorized",
1009 "CantVectorizeIntrinsic", ORE, TheLoop, CI);
1010 return false;
1011 }
1012 }
1013 }
1014
1015 // If we found a vectorized variant of a function, note that so LV can
1016 // make better decisions about maximum VF.
1017 if (CI && !VFDatabase::getMappings(*CI).empty())
1018 VecCallVariantsFound = true;
1019
1020 // Check that the instruction return and stored types are vectorizable.
1021 if (!canWidenTypes(I, /*AllowStructCalls=*/true, ORE, TheLoop))
1022 return false;
1023
1024 if (auto *ST = dyn_cast<StoreInst>(&I)) {
1025 // For nontemporal stores, check that a nontemporal vector version is
1026 // supported on the target.
1027 if (ST->getMetadata(LLVMContext::MD_nontemporal)) {
1028 // Arbitrarily try a vector of 2 elements.
1029 auto *VecTy =
1030 FixedVectorType::get(ST->getValueOperand()->getType(), /*NumElts=*/2);
1031 assert(VecTy && "did not find vectorized version of stored type");
1032 if (!TTI->isLegalNTStore(VecTy, ST->getAlign())) {
1034 "nontemporal store instruction cannot be vectorized",
1035 "CantVectorizeNontemporalStore", ORE, TheLoop, ST);
1036 return false;
1037 }
1038 }
1039
1040 } else if (auto *LD = dyn_cast<LoadInst>(&I)) {
1041 if (LD->getMetadata(LLVMContext::MD_nontemporal)) {
1042 // For nontemporal loads, check that a nontemporal vector version is
1043 // supported on the target (arbitrarily try a vector of 2 elements).
1044 auto *VecTy = FixedVectorType::get(I.getType(), /*NumElts=*/2);
1045 assert(VecTy && "did not find vectorized version of load type");
1046 if (!TTI->isLegalNTLoad(VecTy, LD->getAlign())) {
1048 "nontemporal load instruction cannot be vectorized",
1049 "CantVectorizeNontemporalLoad", ORE, TheLoop, LD);
1050 return false;
1051 }
1052 }
1053
1054 // FP instructions can allow unsafe algebra, thus vectorizable by
1055 // non-IEEE-754 compliant SIMD units.
1056 // This applies to floating-point math operations, calls and compares
1057 // other than NaN checks, not memory operations, shuffles, or casts, as they
1058 // don't change precision or semantics.
1059 } else if (((I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp())) ||
1060 (isa<FCmpInst>(I) &&
1062 cast<FCmpInst>(I).getPredicate()))) &&
1063 !I.isFast()) {
1064 LLVM_DEBUG(dbgs() << "LV: Found potentially unsafe FP op.\n");
1065 Hints->setPotentiallyUnsafe();
1066 }
1067
1068 return true;
1069}
1070
1071/// Find histogram operations that match high-level code in loops:
1072/// \code
1073/// buckets[indices[i]] = UpdateOp(buckets[indices[i]], Val);
1074/// \endcode
1075/// Where UpdateOp can be add, sub, uadd.sat, umax, or umin.
1076///
1077/// It matches a pattern starting from \p HSt, which Stores to the 'buckets'
1078/// array the computed histogram. It uses an update instruction to update all
1079/// counts, storing them using a loop-variant index Load from the 'indices'
1080/// input array.
1081///
1082/// On successful matches it updates the STATISTIC 'HistogramsDetected',
1083/// regardless of hardware support. When there is support, it additionally
1084/// stores the UpdateOp/Load pairs in \p HistogramCounts, as well the pointers
1085/// used to update histogram in \p HistogramPtrs.
1086static bool findHistogram(LoadInst *LI, StoreInst *HSt, Loop *TheLoop,
1087 const PredicatedScalarEvolution &PSE,
1088 SmallVectorImpl<HistogramInfo> &Histograms) {
1089
1090 // Store value must come from an update operation (binary op or intrinsic).
1091 Instruction *HPtrInstr = nullptr;
1092 Instruction *HUpdateOp = nullptr;
1093 if (!match(HSt, m_Store(m_Instruction(HUpdateOp), m_Instruction(HPtrInstr))))
1094 return false;
1095
1096 // The update operation must modify the bucket value by a loop invariant
1097 // amount. Supported operations: add, sub, uadd.sat, umax, umin.
1098 // FIXME: We assume the loop invariant term is on the RHS.
1099 // Fine for an immediate/constant, but maybe not a generic value?
1100 Value *HIncVal = nullptr;
1101 HistogramUpdateKind UpdateKind;
1102 auto Bucket = m_Load(m_Specific(HPtrInstr));
1103 if (match(HUpdateOp, m_Add(Bucket, m_Value(HIncVal))))
1104 UpdateKind = HistogramUpdateKind::Add;
1105 else if (match(HUpdateOp, m_Sub(Bucket, m_Value(HIncVal))))
1106 UpdateKind = HistogramUpdateKind::Sub;
1107 else if (match(HUpdateOp,
1108 m_Intrinsic<Intrinsic::uadd_sat>(Bucket, m_Value(HIncVal))))
1109 UpdateKind = HistogramUpdateKind::UAddSat;
1110 else if (match(HUpdateOp, m_UMax(Bucket, m_Value(HIncVal))))
1111 UpdateKind = HistogramUpdateKind::UMax;
1112 else if (match(HUpdateOp, m_UMin(Bucket, m_Value(HIncVal))))
1113 UpdateKind = HistogramUpdateKind::UMin;
1114 else
1115 return false;
1116
1117 // Make sure the increment value is loop invariant.
1118 if (!TheLoop->isLoopInvariant(HIncVal))
1119 return false;
1120
1121 // The address to store is calculated through a GEP Instruction.
1123 if (!GEP)
1124 return false;
1125
1126 // Restrict address calculation to constant indices except for the last term.
1127 Value *HIdx = nullptr;
1128 for (Value *Index : GEP->indices()) {
1129 if (HIdx)
1130 return false;
1131 if (!isa<ConstantInt>(Index))
1132 HIdx = Index;
1133 }
1134
1135 if (!HIdx)
1136 return false;
1137
1138 // Check that the index is calculated by loading from another array. Ignore
1139 // any extensions.
1140 // FIXME: Support indices from other sources than a linear load from memory?
1141 // We're currently trying to match an operation looping over an array
1142 // of indices, but there could be additional levels of indirection
1143 // in place, or possibly some additional calculation to form the index
1144 // from the loaded data.
1145 Value *VPtrVal;
1146 if (!match(HIdx, m_ZExtOrSExtOrSelf(m_Load(m_Value(VPtrVal)))))
1147 return false;
1148
1149 // Make sure the index address varies in this loop, not an outer loop.
1150 const auto *AR = dyn_cast<SCEVAddRecExpr>(PSE.getSE()->getSCEV(VPtrVal));
1151 if (!AR || AR->getLoop() != TheLoop)
1152 return false;
1153
1154 // Ensure we'll have the same mask by checking that all parts of the histogram
1155 // (gather load, update, scatter store) are in the same block.
1156 LoadInst *IndexedLoad = cast<LoadInst>(HUpdateOp->getOperand(0));
1157 BasicBlock *LdBB = IndexedLoad->getParent();
1158 if (LdBB != HUpdateOp->getParent() || LdBB != HSt->getParent())
1159 return false;
1160
1161 // The bucket value and its update must not be used outside the histogram.
1162 if (!IndexedLoad->hasOneUse() || !HUpdateOp->hasOneUse())
1163 return false;
1164
1165 LLVM_DEBUG(dbgs() << "LV: Found histogram for: " << *HSt << "\n");
1166
1167 // Store the operations that make up the histogram.
1168 Histograms.emplace_back(IndexedLoad, HUpdateOp, HSt, UpdateKind);
1169 return true;
1170}
1171
1172bool LoopVectorizationLegality::canVectorizeIndirectUnsafeDependences() {
1173 // For now, we only support an IndirectUnsafe dependency that calculates
1174 // a histogram
1175 if (!Opts.enable_histogram_loop_vectorization)
1176 return false;
1177
1178 // Find a single IndirectUnsafe dependency.
1179 const MemoryDepChecker::Dependence *IUDep = nullptr;
1180 const MemoryDepChecker &DepChecker = LAI->getDepChecker();
1181 const auto *Deps = DepChecker.getDependences();
1182 // If there were too many dependences, LAA abandons recording them. We can't
1183 // proceed safely if we don't know what the dependences are.
1184 if (!Deps)
1185 return false;
1186
1187 for (const MemoryDepChecker::Dependence &Dep : *Deps) {
1188 // Ignore dependencies that are either known to be safe or can be
1189 // checked at runtime.
1192 continue;
1193
1194 // We're only interested in IndirectUnsafe dependencies here, where the
1195 // address might come from a load from memory. We also only want to handle
1196 // one such dependency, at least for now.
1197 if (Dep.Type != MemoryDepChecker::Dependence::IndirectUnsafe || IUDep)
1198 return false;
1199
1200 IUDep = &Dep;
1201 }
1202 if (!IUDep)
1203 return false;
1204
1205 // For now only normal loads and stores are supported.
1206 LoadInst *LI = dyn_cast<LoadInst>(IUDep->getSource(DepChecker));
1207 StoreInst *SI = dyn_cast<StoreInst>(IUDep->getDestination(DepChecker));
1208
1209 if (!LI || !SI)
1210 return false;
1211
1212 LLVM_DEBUG(dbgs() << "LV: Checking for a histogram on: " << *SI << "\n");
1213 return findHistogram(LI, SI, TheLoop, LAI->getPSE(), Histograms);
1214}
1215
1216bool LoopVectorizationLegality::canVectorizeMemory() {
1217 LAI = &LAIs.getInfo(*TheLoop);
1218 const OptimizationRemarkAnalysis *LAR = LAI->getReport();
1219 if (LAR) {
1220 ORE->emit([&]() {
1221 return OptimizationRemarkAnalysis(LV_NAME, "loop not vectorized: ", *LAR);
1222 });
1223 }
1224
1225 // We can vectorize stores to invariant address when final reduction value is
1226 // guaranteed to be stored at the end of the loop. Also, if decision to
1227 // vectorize loop is made, runtime checks are added so as to make sure that
1228 // invariant address won't alias with any other objects.
1229 if (!LAI->getStoresToInvariantAddresses().empty()) {
1230 // For each invariant address, check if last stored value is unconditional
1231 // and the address is not calculated inside the loop.
1232 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1234 continue;
1235
1236 if (blockNeedsPredication(SI->getParent())) {
1238 "We don't allow storing to uniform addresses",
1239 "write of conditional recurring variant value to a loop "
1240 "invariant address could not be vectorized",
1241 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1242 return false;
1243 }
1244
1245 // Invariant address should be defined outside of loop. LICM pass usually
1246 // makes sure it happens, but in rare cases it does not, we do not want
1247 // to overcomplicate vectorization to support this case.
1248 if (Instruction *Ptr = dyn_cast<Instruction>(SI->getPointerOperand())) {
1249 if (TheLoop->contains(Ptr)) {
1251 "Invariant address is calculated inside the loop",
1252 "write to a loop invariant address could not "
1253 "be vectorized",
1254 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1255 return false;
1256 }
1257 }
1258 }
1259
1260 if (LAI->hasStoreStoreDependenceInvolvingLoopInvariantAddress()) {
1261 // For each invariant address, check its last stored value is the result
1262 // of one of our reductions.
1263 //
1264 // We do not check if dependence with loads exists because that is already
1265 // checked via hasLoadStoreDependenceInvolvingLoopInvariantAddress.
1266 ScalarEvolution *SE = PSE.getSE();
1267 SmallVector<StoreInst *, 4> UnhandledStores;
1268 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1270 // Earlier stores to this address are effectively deadcode.
1271 // With opaque pointers it is possible for one pointer to be used with
1272 // different sizes of stored values:
1273 // store i32 0, ptr %x
1274 // store i8 0, ptr %x
1275 // The latest store doesn't complitely overwrite the first one in the
1276 // example. That is why we have to make sure that types of stored
1277 // values are same.
1278 // TODO: Check that bitwidth of unhandled store is smaller then the
1279 // one that overwrites it and add a test.
1280 erase_if(UnhandledStores, [SE, SI](StoreInst *I) {
1281 return storeToSameAddress(SE, SI, I) &&
1282 I->getValueOperand()->getType() ==
1283 SI->getValueOperand()->getType();
1284 });
1285 continue;
1286 }
1287 UnhandledStores.push_back(SI);
1288 }
1289
1290 bool IsOK = UnhandledStores.empty();
1291 // TODO: we should also validate against InvariantMemSets.
1292 if (!IsOK) {
1294 "We don't allow storing to uniform addresses",
1295 "write to a loop invariant address could not "
1296 "be vectorized",
1297 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1298 return false;
1299 }
1300 }
1301 }
1302
1303 if (!LAI->canVectorizeMemory()) {
1306 "Cannot vectorize unsafe dependencies in uncountable exit loop with "
1307 "side effects",
1308 "CantVectorizeUnsafeDependencyForEELoopWithSideEffects", ORE,
1309 TheLoop);
1310 return false;
1311 }
1312
1313 return canVectorizeIndirectUnsafeDependences();
1314 }
1315
1316 if (LAI->hasLoadStoreDependenceInvolvingLoopInvariantAddress()) {
1317 reportVectorizationFailure("We don't allow storing to uniform addresses",
1318 "write to a loop invariant address could not "
1319 "be vectorized",
1320 "CantVectorizeStoreToLoopInvariantAddress", ORE,
1321 TheLoop);
1322 return false;
1323 }
1324
1325 PSE.addPredicate(LAI->getPSE().getPredicate());
1326 return true;
1327}
1328
1330 bool EnableStrictReductions) {
1331
1332 // First check if there is any ExactFP math or if we allow reassociations
1333 if (!Requirements->getExactFPInst() || Hints->allowReordering())
1334 return true;
1335
1336 // If the above is false, we have ExactFPMath & do not allow reordering.
1337 // If the EnableStrictReductions flag is set, first check if we have any
1338 // Exact FP induction vars, which we cannot vectorize.
1339 if (!EnableStrictReductions ||
1340 any_of(getInductionVars().values(),
1341 [](const InductionDescriptor &IndDesc) -> bool {
1342 return IndDesc.getExactFPMathInst();
1343 }))
1344 return false;
1345
1346 // We can now only vectorize if all reductions with Exact FP math also
1347 // have the isOrdered flag set, which indicates that we can move the
1348 // reduction operations in-loop.
1349 return (all_of(getReductionVars().values(),
1350 [](const RecurrenceDescriptor &RdxDesc) -> bool {
1351 return !RdxDesc.hasExactFPMath() || RdxDesc.isOrdered();
1352 }));
1353}
1354
1356 return any_of(getReductionVars().values(),
1357 [&](const RecurrenceDescriptor &RdxDesc) -> bool {
1358 return RdxDesc.IntermediateStore == SI;
1359 });
1360}
1361
1363 return any_of(getReductionVars().values(),
1364 [&](const RecurrenceDescriptor &RdxDesc) -> bool {
1365 if (!RdxDesc.IntermediateStore)
1366 return false;
1367
1368 ScalarEvolution *SE = PSE.getSE();
1369 Value *InvariantAddress =
1371 return V == InvariantAddress ||
1372 SE->getSCEV(V) == SE->getSCEV(InvariantAddress);
1373 });
1374}
1375
1377 Value *In0 = const_cast<Value *>(V);
1379 if (!PN)
1380 return false;
1381
1382 return Inductions.count(PN);
1383}
1384
1386 const PHINode *Phi) const {
1387 return FixedOrderRecurrences.count(Phi);
1388}
1389
1391 const BasicBlock *BB) const {
1392 BasicBlock *Latch = TheLoop->getLoopLatch();
1393
1394 // Without a latch, we cannot properly answer blockNeedsPredication,
1395 // return early.
1396 if (!Latch) {
1397 assert(ORE->allowExtraAnalysis(DEBUG_TYPE) &&
1398 !canVectorizeLoopCFG(TheLoop, /*UseVPlanNativePath=*/false) &&
1399 "Loop shape should have been rejected by earlier checks");
1400 return false;
1401 }
1402
1403 // When vectorizing early exits, create predicates for the latch block only.
1404 // For a single early exit, it must be a direct predecessor of the latch.
1405 // For multiple early exits, they form a chain where each exiting block
1406 // dominates all subsequent blocks up to the latch.
1408 return BB == Latch;
1409 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
1410}
1411
1412bool LoopVectorizationLegality::blockCanBePredicated(
1413 BasicBlock *BB, SafeAccessesTy &SafeAccesses,
1414 SmallPtrSetImpl<const Instruction *> &MaskedOp) const {
1415 for (Instruction &I : *BB) {
1416 // We can predicate blocks with calls to assume, as long as we drop them in
1417 // case we flatten the CFG via predication.
1419 MaskedOp.insert(&I);
1420 continue;
1421 }
1422
1423 // Do not let llvm.experimental.noalias.scope.decl block the vectorization.
1424 // TODO: there might be cases that it should block the vectorization. Let's
1425 // ignore those for now.
1427 continue;
1428
1429 // We can allow masked calls if there's at least one vector variant, even
1430 // if we end up scalarizing due to the cost model calculations.
1431 // TODO: Allow other calls if they have appropriate attributes... readonly
1432 // and argmemonly?
1433 if (CallInst *CI = dyn_cast<CallInst>(&I))
1435 MaskedOp.insert(CI);
1436 continue;
1437 }
1438
1439 // Loads are handled via masking (or speculated if safe to do so.)
1440 if (auto *LI = dyn_cast<LoadInst>(&I)) {
1441 auto It = SafeAccesses.find(LI->getPointerOperand());
1442 TypeSize Size = LI->getDataLayout().getTypeStoreSize(LI->getType());
1443 if (Size.isScalable() || It == SafeAccesses.end() ||
1444 It->second.MaxAlign < LI->getAlign() ||
1445 It->second.MaxSizeInBytes < Size.getFixedValue())
1446 MaskedOp.insert(LI);
1447 continue;
1448 }
1449
1450 // Predicated store requires some form of masking:
1451 // 1) masked store HW instruction,
1452 // 2) emulation via load-blend-store (only if safe and legal to do so,
1453 // be aware on the race conditions), or
1454 // 3) element-by-element predicate check and scalar store.
1455 if (auto *SI = dyn_cast<StoreInst>(&I)) {
1456 MaskedOp.insert(SI);
1457 continue;
1458 }
1459
1460 if (I.mayReadFromMemory() || I.mayWriteToMemory() || I.mayThrow())
1461 return false;
1462 }
1463
1464 return true;
1465}
1466
1467bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
1468 if (!Opts.enable_if_conversion) {
1469 reportVectorizationFailure("If-conversion is disabled",
1470 "IfConversionDisabled", ORE, TheLoop);
1471 return false;
1472 }
1473
1474 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
1475
1476 // Record the maximum fixed access size and alignment known to be safe for
1477 // each pointer in every executed iteration. A conditional load can execute
1478 // unconditionally if its size and alignment do not exceed these bounds.
1479 // Scalable accesses do not establish either size or alignment.
1480 SafeAccessesTy SafeAccesses;
1481 auto RecordSafeAccess = [&SafeAccesses](Instruction &I) {
1483 if (!Ptr)
1484 return;
1485 TypeSize Size = I.getDataLayout().getTypeStoreSize(getLoadStoreType(&I));
1486 if (Size.isScalable())
1487 return;
1489 auto &Info = SafeAccesses[Ptr];
1490 Info.MaxAlign = std::max(Info.MaxAlign, Alignment);
1491 Info.MaxSizeInBytes = std::max(Info.MaxSizeInBytes, Size.getFixedValue());
1492 };
1493
1494 // Collect safe accesses.
1495 for (BasicBlock *BB : TheLoop->blocks()) {
1496 if (!blockNeedsPredication(BB)) {
1497 for (Instruction &I : *BB)
1498 RecordSafeAccess(I);
1499 continue;
1500 }
1501
1502 // For a block which requires predication, a address may be safe to access
1503 // in the loop w/o predication if we can prove dereferenceability facts
1504 // sufficient to ensure it'll never fault within the loop. For the moment,
1505 // we restrict this to loads; stores are more complicated due to
1506 // concurrency restrictions.
1507 ScalarEvolution &SE = *PSE.getSE();
1509 for (Instruction &I : *BB) {
1510 LoadInst *LI = dyn_cast<LoadInst>(&I);
1511
1512 // Make sure we can execute all computations feeding into Ptr in the loop
1513 // w/o triggering UB and that none of the out-of-loop operands are poison.
1514 // We do not need to check if operations inside the loop can produce
1515 // poison due to flags (e.g. due to an inbounds GEP going out of bounds),
1516 // because flags will be dropped when executing them unconditionally.
1517 // TODO: Results could be improved by considering poison-propagation
1518 // properties of visited ops.
1519 auto CanSpeculatePointerOp = [this](Value *Ptr) {
1520 SmallVector<Value *> Worklist = {Ptr};
1521 SmallPtrSet<Value *, 4> Visited;
1522 while (!Worklist.empty()) {
1523 Value *CurrV = Worklist.pop_back_val();
1524 if (!Visited.insert(CurrV).second)
1525 continue;
1526
1527 auto *CurrI = dyn_cast<Instruction>(CurrV);
1528 if (!CurrI || !TheLoop->contains(CurrI)) {
1529 BasicBlock *LoopPred = TheLoop->getLoopPredecessor();
1530 Instruction *CtxI = LoopPred ? LoopPred->getTerminator() : nullptr;
1531 assert((CtxI || ORE->allowExtraAnalysis(DEBUG_TYPE)) &&
1532 "Loop with multiple predecessors should have been rejected "
1533 "early.");
1534 // If operands from outside the loop may be poison then Ptr may also
1535 // be poison.
1536 if (!isGuaranteedNotToBePoison(CurrV, AC, CtxI, DT))
1537 return false;
1538 continue;
1539 }
1540
1541 // A loaded value may be poison, independent of any flags.
1542 if (isa<LoadInst>(CurrI) && !isGuaranteedNotToBePoison(CurrV, AC))
1543 return false;
1544
1545 // For other ops, assume poison can only be introduced via flags,
1546 // which can be dropped.
1547 if (!isa<PHINode>(CurrI) && !isSafeToSpeculativelyExecute(CurrI))
1548 return false;
1549 append_range(Worklist, CurrI->operands());
1550 }
1551 return true;
1552 };
1553 // Pass the Predicates pointer to isDereferenceableAndAlignedInLoop so
1554 // that it will consider loops that need guarding by SCEV checks. The
1555 // vectoriser will generate these checks if we decide to vectorise.
1556 if (LI && !LI->getType()->isVectorTy() && !mustSuppressSpeculation(*LI) &&
1557 CanSpeculatePointerOp(LI->getPointerOperand()) &&
1558 isDereferenceableAndAlignedInLoop(LI, TheLoop, SE, *DT, AC,
1559 &Predicates))
1560 RecordSafeAccess(*LI);
1561 Predicates.clear();
1562 }
1563 }
1564
1565 // Collect the blocks that need predication.
1566 for (BasicBlock *BB : TheLoop->blocks()) {
1567 // We support only branches and switch statements as terminators inside the
1568 // loop.
1569 if (isa<SwitchInst>(BB->getTerminator())) {
1570 if (TheLoop->isLoopExiting(BB)) {
1571 reportVectorizationFailure("Loop contains an unsupported switch",
1572 "LoopContainsUnsupportedSwitch", ORE,
1573 TheLoop, BB->getTerminator());
1574 return false;
1575 }
1576 } else if (!isa<UncondBrInst, CondBrInst>(BB->getTerminator())) {
1577 reportVectorizationFailure("Loop contains an unsupported terminator",
1578 "LoopContainsUnsupportedTerminator", ORE,
1579 TheLoop, BB->getTerminator());
1580 return false;
1581 }
1582
1583 // We must be able to predicate all blocks that need to be predicated.
1584 if (blockNeedsPredication(BB) &&
1585 !blockCanBePredicated(BB, SafeAccesses, ConditionallyExecutedOps)) {
1587 "Control flow cannot be substituted for a select", "NoCFGForSelect",
1588 ORE, TheLoop, BB->getTerminator());
1589 return false;
1590 }
1591 }
1592
1593 // We can if-convert this loop.
1594 return true;
1595}
1596
1597// Helper function to canVectorizeLoopNestCFG.
1598bool LoopVectorizationLegality::canVectorizeLoopCFG(
1599 Loop *Lp, bool UseVPlanNativePath) const {
1600 assert((UseVPlanNativePath || Lp->isInnermost()) &&
1601 "VPlan-native path is not enabled.");
1602
1603 // TODO: ORE should be improved to show more accurate information when an
1604 // outer loop can't be vectorized because a nested loop is not understood or
1605 // legal. Something like: "outer_loop_location: loop not vectorized:
1606 // (inner_loop_location) loop control flow is not understood by vectorizer".
1607
1608 // Store the result and return it at the end instead of exiting early, in case
1609 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1610 bool Result = true;
1611 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1612
1613 // We must have a loop in canonical form. Loops with indirectbr in them cannot
1614 // be canonicalized. The preheader must also be terminated by an unconditional
1615 // branch, which gets replaced when creating the vector loop.
1616 BasicBlock *Preheader = Lp->getLoopPreheader();
1617 if (!Preheader || !isa<UncondBrInst>(Preheader->getTerminator())) {
1619 "Loop doesn't have a legal pre-header",
1620 "loop control flow is not understood by vectorizer", "CFGNotUnderstood",
1621 ORE, TheLoop);
1622 if (DoExtraAnalysis)
1623 Result = false;
1624 else
1625 return false;
1626 }
1627
1628 // We must have a single backedge.
1629 if (Lp->getNumBackEdges() != 1) {
1631 "The loop must have a single backedge",
1632 "loop control flow is not understood by vectorizer", "CFGNotUnderstood",
1633 ORE, TheLoop);
1634 if (DoExtraAnalysis)
1635 Result = false;
1636 else
1637 return false;
1638 }
1639
1640 // The latch must be terminated by a branch.
1641 BasicBlock *Latch = Lp->getLoopLatch();
1642 if (Latch && !isa<UncondBrInst, CondBrInst>(Latch->getTerminator())) {
1644 "The loop latch terminator is not a UncondBrInst/CondBrInst",
1645 "loop control flow is not understood by vectorizer", "CFGNotUnderstood",
1646 ORE, TheLoop);
1647 if (DoExtraAnalysis)
1648 Result = false;
1649 else
1650 return false;
1651 }
1652
1653 return Result;
1654}
1655
1656bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1657 Loop *Lp, bool UseVPlanNativePath) {
1658 // Store the result and return it at the end instead of exiting early, in case
1659 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1660 bool Result = true;
1661 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1662 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1663 if (DoExtraAnalysis)
1664 Result = false;
1665 else
1666 return false;
1667 }
1668
1669 // Recursively check whether the loop control flow of nested loops is
1670 // understood.
1671 for (Loop *SubLp : *Lp)
1672 if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) {
1673 if (DoExtraAnalysis)
1674 Result = false;
1675 else
1676 return false;
1677 }
1678
1679 return Result;
1680}
1681
1682/// Matches an exit condition formed by comparing a value loaded from memory
1683/// with another term. Binds the pointer, load, and the other comparison term.
1685 Instruction *&Load, Value *&Other) {
1686 return match(
1688}
1689
1690/// Matches an exit condition formed by comparing the current value of an
1691/// affine add recurrence in the given loop with a stride of 1 against a
1692/// loop-invariant term.
1694 Loop *TheLoop) {
1695 using namespace llvm::SCEVPatternMatch;
1696 Value *IVUpdate, *Limit;
1697 return match(Cond, m_c_ICmp(m_Value(IVUpdate, m_Add(m_Value(), m_Value())),
1698 m_Value(Limit))) &&
1699 TheLoop->isLoopInvariant(Limit) &&
1700 SCEVPatternMatch::match(SE.getSCEV(IVUpdate),
1702 m_SpecificLoop(TheLoop)));
1703}
1704
1705/// Matches a combined exit condition consisting of an uncountable condition and
1706/// a countable condition, combined by an or. Binds the pointer, load, the
1707/// second comparison term for the uncountable condition, and the comparison for
1708/// the countable condition.
1709static bool matchCombinedExitCondition(Value *Cond, Instruction *&CountableCond,
1710 Value *&Ptr, Instruction *&Load,
1712 Loop *TheLoop) {
1713 Value *L, *R;
1714 if (!match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
1715 return false;
1716
1717 if (matchCountableExitCondition(L, SE, TheLoop) &&
1719 CountableCond = cast<Instruction>(L);
1720 return true;
1721 }
1722
1723 if (matchCountableExitCondition(R, SE, TheLoop) &&
1725 CountableCond = cast<Instruction>(R);
1726 return true;
1727 }
1728
1729 return false;
1730}
1731
1734 Value *Cond) const {
1735 Value *Ptr, *Other;
1736 Instruction *Load, *CountableCmp;
1737 if (matchCombinedExitCondition(Cond, CountableCmp, Ptr, Load, Other,
1738 *PSE.getSE(), TheLoop))
1739 return CountableCmp;
1740
1741 return nullptr;
1742}
1743
1744bool LoopVectorizationLegality::isVectorizableEarlyExitLoop() {
1745 BasicBlock *LatchBB = TheLoop->getLoopLatch();
1746 if (!LatchBB) {
1747 reportVectorizationFailure("Loop does not have a latch",
1748 "Cannot vectorize early exit loop",
1749 "NoLatchEarlyExit", ORE, TheLoop);
1750 return false;
1751 }
1752
1753 if (!FixedOrderRecurrences.empty()) {
1755 "Found fixed-order recurrences in early-exit loop",
1756 "Cannot vectorize early exit loop with fixed-order recurrences",
1757 "RecurrencesInEarlyExitLoop", ORE, TheLoop);
1758 return false;
1759 }
1760
1761 SmallVector<BasicBlock *, 8> ExitingBlocks;
1762 TheLoop->getExitingBlocks(ExitingBlocks);
1763
1764 // Keep a record of all the exiting blocks.
1766 SmallVector<BasicBlock *> UncountableExitingBlocks;
1767 for (BasicBlock *BB : ExitingBlocks) {
1768 const SCEV *EC =
1769 PSE.getSE()->getPredicatedExitCount(TheLoop, BB, &Predicates);
1770 if (isa<SCEVCouldNotCompute>(EC)) {
1771 if (size(successors(BB)) != 2) {
1773 "Early exiting block does not have exactly two successors",
1774 "Incorrect number of successors from early exiting block",
1775 "EarlyExitTooManySuccessors", ORE, TheLoop);
1776 return false;
1777 }
1778
1779 UncountableExitingBlocks.push_back(BB);
1780 } else
1781 CountableExitingBlocks.push_back(BB);
1782 }
1783 // We can safely ignore the predicates here because when vectorizing the loop
1784 // the PredicatatedScalarEvolution class will keep track of all predicates
1785 // for each exiting block anyway. This happens when calling
1786 // PSE.getSymbolicMaxBackedgeTakenCount() below.
1787 Predicates.clear();
1788
1789 if (UncountableExitingBlocks.empty()) {
1790 LLVM_DEBUG(dbgs() << "LV: Could not find any uncountable exits\n");
1791 return false;
1792 }
1793
1794 // The latch block must have a countable exit.
1795 if (isa<SCEVCouldNotCompute>(PSE.getSE()->getPredicatedExitCount(
1796 TheLoop, LatchBB, &Predicates, ScalarEvolution::SymbolicMaximum))) {
1798 "Cannot determine symbolic max exit count for latch block",
1799 "Cannot vectorize early exit loop",
1800 "UnknownLatchExitCountEarlyExitLoop", ORE, TheLoop);
1801 return false;
1802 }
1803
1804 if (!is_contained(CountableExitingBlocks, LatchBB)) {
1805 // If not a separate counted exit in the latch, then check for a combined
1806 // countable and uncountable exit.
1807 auto *Br = dyn_cast<CondBrInst>(LatchBB->getTerminator());
1808 if (!Br ||
1809 !findCountableComparisonInCombinedCondition(Br->getCondition())) {
1811 "Latch block does not have a countable exit condition",
1812 "NoCountableConditionInLatchBlock", ORE, TheLoop);
1813 return false;
1814 }
1815 }
1816
1817 // Check to see if there are instructions that could potentially generate
1818 // exceptions or have side-effects.
1819 auto IsSafeOperation = [](Instruction *I) -> bool {
1820 switch (I->getOpcode()) {
1821 case Instruction::Load:
1822 case Instruction::Store:
1823 case Instruction::PHI:
1824 case Instruction::UncondBr:
1825 case Instruction::CondBr:
1826 // These are checked separately.
1827 return true;
1828 default:
1830 }
1831 };
1832
1833 bool HasSideEffects = false;
1834 for (auto *BB : TheLoop->blocks())
1835 for (auto &I : *BB) {
1837 continue;
1838 if (I.mayWriteToMemory()) {
1839 if (isa<StoreInst>(&I) && cast<StoreInst>(&I)->isSimple()) {
1840 HasSideEffects = true;
1841 continue;
1842 }
1843
1844 // We don't support complex writes to memory.
1846 "Complex writes to memory unsupported in early exit loops",
1847 "Cannot vectorize early exit loop with complex writes to memory",
1848 "WritesInEarlyExitLoop", ORE, TheLoop);
1849 return false;
1850 }
1851
1852 if (!IsSafeOperation(&I)) {
1853 reportVectorizationFailure("Early exit loop contains operations that "
1854 "cannot be speculatively executed",
1855 "UnsafeOperationsEarlyExitLoop", ORE,
1856 TheLoop);
1857 return false;
1858 }
1859 }
1860
1861 SmallVector<LoadInst *, 4> NonDerefLoads;
1862 // TODO: Handle loops that may fault.
1863 if (!HasSideEffects) {
1864 // Read-only loop.
1865 Predicates.clear();
1866 if (!isReadOnlyLoop(TheLoop, PSE.getSE(), DT, AC, NonDerefLoads,
1867 &Predicates)) {
1869 "Loop may fault", "Cannot vectorize non-read-only early exit loop",
1870 "NonReadOnlyEarlyExitLoop", ORE, TheLoop);
1871 return false;
1872 }
1873 } else {
1874 // Check all uncountable exiting blocks for movable loads.
1875 for (BasicBlock *ExitingBB : UncountableExitingBlocks) {
1876 if (!canUncountableExitConditionLoadBeMoved(ExitingBB))
1877 return false;
1878 }
1879 }
1880
1881 // Check non-dereferenceable loads if any.
1882 for (LoadInst *LI : NonDerefLoads) {
1883 // Only support unit-stride access for now.
1884 int Stride = isConsecutivePtr(LI->getType(), LI->getPointerOperand());
1885 if (Stride != 1) {
1887 "Loop contains potentially faulting strided load",
1888 "Cannot vectorize early exit loop with "
1889 "strided fault-only-first load",
1890 "EarlyExitLoopWithStridedFaultOnlyFirstLoad", ORE, TheLoop);
1891 return false;
1892 }
1893 }
1894
1895 // We're only handling combined exit conditions via masking at present, which
1896 // is used for loops with side effects.
1897 // TODO: Support readonly loops with combined exit conditions.
1898 // TODO: Decouple style from the presence of side effects.
1899 if (!llvm::is_contained(CountableExitingBlocks, LatchBB) && !HasSideEffects)
1900 return false;
1901
1902 [[maybe_unused]] const SCEV *SymbolicMaxBTC =
1903 PSE.getSymbolicMaxBackedgeTakenCount();
1904 // Since we have an exact exit count for the latch and the early exit
1905 // dominates the latch, then this should guarantee a computed SCEV value.
1906 assert(!isa<SCEVCouldNotCompute>(SymbolicMaxBTC) &&
1907 "Failed to get symbolic expression for backedge taken count");
1908 LLVM_DEBUG(dbgs() << "LV: Found an early exit loop with symbolic max "
1909 "backedge taken count: "
1910 << *SymbolicMaxBTC << '\n');
1911 UncountableExitType = HasSideEffects ? UncountableExitTrait::ReadWrite
1913 return true;
1914}
1915
1916bool LoopVectorizationLegality::canUncountableExitConditionLoadBeMoved(
1917 BasicBlock *ExitingBlock) {
1918 // Try to find a load in the critical path for the uncountable exit condition.
1919 // This is currently matching about the simplest form we can, expecting
1920 // only one in-loop load, the result of which is directly compared against
1921 // a loop-invariant value.
1922 auto *Br = cast<CondBrInst>(ExitingBlock->getTerminator());
1923
1924 using namespace llvm::PatternMatch;
1925 Value *Ptr, *Other;
1926 Instruction *L, *CountableCond;
1927 // We want to match either an uncounted condition (loaded value compared
1928 // against a loop invariant value) or the combination (via logical or) of
1929 // an uncounted condition with a counted condition (integer comparison of
1930 // an induction variable for which we can identify an add recurrence within
1931 // this loop).
1932 if (!matchUncountableExitCondition(Br->getCondition(), Ptr, L, Other) &&
1933 !matchCombinedExitCondition(Br->getCondition(), CountableCond, Ptr, L,
1934 Other, *PSE.getSE(), TheLoop)) {
1936 "Early exit loop with store but no supported condition load",
1937 "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1938 return false;
1939 }
1940
1941 // Bail if the uncountable exit load is compared against a non-invariant
1942 // value.
1943 // TODO: Remove this restriction.
1944 if (!TheLoop->isLoopInvariant(Other)) {
1946 "Early exit loop with store but no supported condition load",
1947 "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1948 return false;
1949 }
1950
1951 // Make sure that the load address is not loop invariant; we want an
1952 // address calculation that we can rotate to the next vector iteration.
1953 const auto *AR = dyn_cast<SCEVAddRecExpr>(PSE.getSE()->getSCEV(Ptr));
1954 if (!AR || AR->getLoop() != TheLoop || !AR->isAffine()) {
1956 "Uncountable exit condition depends on load with an address that is "
1957 "not an add recurrence in the loop",
1958 "EarlyExitLoadInvariantAddress", ORE, TheLoop);
1959 return false;
1960 }
1961
1962 ICFLoopSafetyInfo SafetyInfo(TheLoop);
1963 LoadInst *Load = cast<LoadInst>(L);
1964 // We need to know that load will be executed before we can hoist a
1965 // copy out to run just before the first iteration.
1966 if (!SafetyInfo.isGuaranteedToExecute(*Load, DT)) {
1968 "Load for uncountable exit not guaranteed to execute",
1969 "ConditionalUncountableExitLoad", ORE, TheLoop);
1970 return false;
1971 }
1972
1973 // Prohibit any potential aliasing with any instruction in the loop which
1974 // might store to memory.
1975 // FIXME: Relax this constraint where possible.
1976 for (auto *BB : TheLoop->blocks()) {
1977 for (auto &I : *BB) {
1978 if (&I == Load)
1979 continue;
1980
1981 // Pseudo-probes are placeholders with no real memory
1982 // access, so they cannot alias the exit condition load and do not need
1983 // to be masked.
1985 continue;
1986
1987 if (I.mayReadOrWriteMemory()) {
1988 // We need to mask all other memory ops.
1989 ConditionallyExecutedOps.insert(&I);
1990 if (isa<LoadInst>(&I))
1991 continue;
1992 if (auto *SI = dyn_cast<StoreInst>(&I)) {
1993 AliasResult AR = AA->alias(Ptr, SI->getPointerOperand());
1994 if (AR == AliasResult::NoAlias)
1995 continue;
1996 }
1997
1999 "Cannot determine whether critical uncountable exit load address "
2000 "does not alias with a memory write",
2001 "CantVectorizeAliasWithCriticalUncountableExitLoad", ORE, TheLoop);
2002 return false;
2003 }
2004 }
2005 }
2006
2007 return true;
2008}
2009
2010bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
2011 // Store the result and return it at the end instead of exiting early, in case
2012 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
2013 bool Result = true;
2014
2015 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
2016 // Check whether the loop-related control flow in the loop nest is expected by
2017 // vectorizer.
2018 if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) {
2019 if (DoExtraAnalysis) {
2020 LLVM_DEBUG(dbgs() << "LV: legality check failed: loop nest");
2021 Result = false;
2022 } else {
2023 return false;
2024 }
2025 }
2026
2027 // We need to have a loop header.
2028 LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
2029 << '\n');
2030
2031 // Specific checks for outer loops. We skip the remaining legal checks at this
2032 // point because they don't support outer loops.
2033 if (!TheLoop->isInnermost()) {
2034 assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
2035
2036 if (!canVectorizeOuterLoop()) {
2037 reportVectorizationFailure("Unsupported outer loop",
2038 "UnsupportedOuterLoop", ORE, TheLoop);
2039 // TODO: Implement DoExtraAnalysis when subsequent legal checks support
2040 // outer loops.
2041 return false;
2042 }
2043
2044 LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
2045 return Result;
2046 }
2047
2048 assert(TheLoop->isInnermost() && "Inner loop expected.");
2049 // Check if we can if-convert non-single-bb loops.
2050 unsigned NumBlocks = TheLoop->getNumBlocks();
2051 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
2052 LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
2053 if (DoExtraAnalysis)
2054 Result = false;
2055 else
2056 return false;
2057 }
2058
2059 // Check if we can vectorize the instructions and CFG in this loop.
2060 if (!canVectorizeInstrs()) {
2061 LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
2062 if (DoExtraAnalysis)
2063 Result = false;
2064 else
2065 return false;
2066 }
2067
2068 if (isa<SCEVCouldNotCompute>(PSE.getBackedgeTakenCount()) &&
2069 !isVectorizableEarlyExitLoop()) {
2070 assert(UncountableExitType == UncountableExitTrait::None &&
2071 "Must be false without vectorizable early-exit loop");
2072 if (TheLoop->getExitingBlock())
2073 reportVectorizationFailure("Cannot vectorize uncountable loop",
2074 "UnsupportedUncountableLoop", ORE, TheLoop);
2075 if (DoExtraAnalysis)
2076 Result = false;
2077 else
2078 return false;
2079 }
2080
2081 // Go over each instruction and look at memory deps.
2082 if (!canVectorizeMemory()) {
2083 LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
2084 if (DoExtraAnalysis)
2085 Result = false;
2086 else
2087 return false;
2088 }
2089
2090 // TODO: Remove this restriction, should be straightforward to support.
2091 if (UncountableExitType != UncountableExitTrait::None &&
2092 !LAI->getStoresToInvariantAddresses().empty()) {
2093 LLVM_DEBUG(dbgs() << "LV: Cannot vectorize early exit loops with stores to "
2094 "loop-invariant addresses\n");
2095 reportVectorizationFailure("Cannot vectorize early exit loops with stores "
2096 "to loop-invariant addresses",
2097 "LoopInvariantStoresInEELoop", ORE, TheLoop);
2098 return false;
2099 }
2100
2101 if (Result) {
2102 LLVM_DEBUG(dbgs() << "LV: Loop passed LoopVectorizationLegality checks"
2103 << (LAI->getRuntimePointerChecking()->Need
2104 ? " (with a runtime bound check)"
2105 : "")
2106 << "!\n");
2107 }
2108
2109 // Okay! We've done all the tests. If any have failed, return false. Otherwise
2110 // we can vectorize, and at this point we don't have any other mem analysis
2111 // which may limit our maximum vectorization factor, so just return true with
2112 // no restrictions.
2113 return Result;
2114}
2115
2117 // The only loops we can vectorize without a scalar epilogue, are loops with
2118 // a bottom-test and a single exiting block. We'd have to handle the fact
2119 // that not every instruction executes on the last iteration. This will
2120 // require a lane mask which varies through the vector loop body. (TODO)
2121 if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
2122 LLVM_DEBUG(
2123 dbgs()
2124 << "LV: Cannot fold tail by masking. Requires a singe latch exit\n");
2125 return false;
2126 }
2127
2128 // TODO: Support tail folding with uncountable exits.
2130 LLVM_DEBUG(dbgs() << "LV: Cannot tail fold by masking. Loop contains an "
2131 "uncountable early exit.\n");
2132 return false;
2133 }
2134
2135 LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n");
2136
2137 // No accesses are known to be safe in inactive lanes of the folded tail.
2138 SafeAccessesTy SafeAccesses;
2139
2140 // Check all blocks for predication, including those that ordinarily do not
2141 // need predication such as the header block.
2143 for (BasicBlock *BB : TheLoop->blocks()) {
2144 if (!blockCanBePredicated(BB, SafeAccesses, TmpMaskedOp)) {
2145 LLVM_DEBUG(dbgs() << "LV: Cannot fold tail by masking.\n");
2146 return false;
2147 }
2148 }
2149
2150 LLVM_DEBUG(dbgs() << "LV: can fold tail by masking.\n");
2151
2152 return true;
2153}
2154
2156 // No accesses are known to be safe in inactive lanes of the folded tail.
2157 SafeAccessesTy SafeAccesses;
2158
2159 // Mark all blocks for predication, including those that ordinarily do not
2160 // need predication such as the header block, and collect instructions needing
2161 // predication in TailFoldedMaskedOp.
2162 for (BasicBlock *BB : TheLoop->blocks()) {
2163 [[maybe_unused]] bool R =
2164 blockCanBePredicated(BB, SafeAccesses, TailFoldedMaskedOp);
2165 assert(R && "Must be able to predicate block when tail-folding.");
2166 }
2167}
2168
2169} // namespace llvm
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define DEBUG_TYPE
Hexagon Common GEP
#define LV_NAME
static const unsigned MaxInterleaveFactor
Maximum vectorization interleave count.
This file defines the LoopVectorizationLegality class.
This file provides a LoopVectorizationPlanner class.
#define I(x, y, z)
Definition MD5.cpp:57
#define H(x, y, z)
Definition MD5.cpp:56
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
SmallVector< MachineOperand, 4 > Cond
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
#define LLVM_DEBUG(...)
Definition Debug.h:119
This pass exposes codegen information to IR-level passes.
virt reg Virtual Register Rewriter
@ NoAlias
The two locations do not alias at all.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
This class represents a function call, abstracting a target machine's calling convention.
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
Definition InstrTypes.h:749
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition InstrTypes.h:750
Describes a conditional induction variable: an induction variable that is updated only on loop iterat...
static LLVM_ABI bool isConditionalInductionPHI(PHINode *PN, const Loop *L, ConditionalInductionDescriptor &Desc, ScalarEvolution &SE)
Returns true if PN is a conditional induction variable in the loop L.
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
static constexpr ElementCount getScalable(ScalarTy MinVal)
Definition TypeSize.h:309
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition TypeSize.h:306
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition Type.cpp:838
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
A struct for saving information about induction variables.
Instruction * getExactFPMathInst() const
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
static LLVM_ABI bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, ArrayRef< const SCEVPredicate * > NoWrapPreds={}, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
Class to represent integer types.
An instruction for reading from memory.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
static LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB, const Loop *TheLoop, const DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
BlockT * getHeader() const
iterator_range< block_iterator > blocks() const
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
LLVM_ABI bool isInvariantStoreOfReduction(StoreInst *SI)
Returns True if given store is a final invariant store of one of the reductions found in the loop.
LLVM_ABI void collectUnitStridePredicates() const
Add unit stride predicates for memory accesses to PSE, if runtime checks are allowed and an inner loo...
LLVM_ABI bool isInvariantAddressOfReduction(Value *V)
Returns True if given address is invariant and is used to store recurrent expression.
LLVM_ABI bool canVectorize(bool UseVPlanNativePath)
Returns true if it is legal to vectorize this loop.
LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB) const
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
LLVM_ABI int isConsecutivePtr(Type *AccessTy, Value *Ptr) const
Check if this pointer is consecutive when vectorizing.
bool hasUncountableExitWithSideEffects() const
Returns true if this is an early exit loop with state-changing or potentially-faulting operations and...
LLVM_ABI bool canVectorizeFPMath(bool EnableStrictReductions)
Returns true if it is legal to vectorize the FP math operations in this loop.
LLVM_ABI bool isFixedOrderRecurrence(const PHINode *Phi) const
Returns True if Phi is a fixed-order recurrence in this loop.
LLVM_ABI bool isInductionPhi(const Value *V) const
Returns True if V is a Phi node of an induction variable in this loop.
LLVM_ABI Instruction * findCountableComparisonInCombinedCondition(Value *Cond) const
If Cond is a combined exit condition featuring uncountable and countable comparisons,...
const InductionList & getInductionVars() const
Returns the induction variables found in the loop.
LLVM_ABI bool isInvariant(Value *V) const
Returns true if V is invariant across all loop iterations according to SCEV.
const ReductionList & getReductionVars() const
Returns the reduction variables found in the loop.
LLVM_ABI bool canFoldTailByMasking() const
Return true if we can vectorize this loop while folding its tail by masking.
LLVM_ABI void prepareToFoldTailByMasking()
Mark all respective loads/stores for masking.
bool hasUncountableEarlyExit() const
Returns true if the loop has uncountable early exits, i.e.
LLVM_ABI bool isUniformMemOp(Instruction &I, std::optional< ElementCount > VF) const
A uniform memory op is a load or store which accesses the same memory location on all VF lanes,...
LLVM_ABI bool isUniform(Value *V, std::optional< ElementCount > VF) const
Returns true if value V is uniform across VF lanes, when VF is provided, and otherwise if V is invari...
@ SK_PreferScalable
Vectorize loops using scalable vectors or fixed-width vectors, but favor scalable vectors when the co...
@ SK_AlwaysScalable
Always vectorize loops using scalable vectors if feasible (i.e.
@ SK_FixedWidthOnly
Disables vectorization with scalable vectors.
LLVM_ABI bool allowReordering() const
When enabling loop hints are provided we allow the vectorizer to change the order of operations that ...
LLVM_ABI LoopVectorizeHints(const VectorizeOptions &Opts, const Loop *L, bool InterleaveOnlyWhenForced, OptimizationRemarkEmitter &ORE, const TargetTransformInfo *TTI=nullptr)
LLVM_ABI void emitRemarkWithHints() const
Dumps all the hint information.
LLVM_ABI bool allowVectorization(Loop *L, bool VectorizeOnlyWhenForced) const
LLVM_ABI void setAlreadyVectorized()
Mark the loop L as already vectorized by setting the width to 1.
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
LLVM_ABI bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition LoopInfo.cpp:64
LLVM_ABI MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition LoopInfo.cpp:553
Metadata node.
Definition Metadata.h:1087
const MDOperand & getOperand(unsigned I) const
Definition Metadata.h:1443
ArrayRef< MDOperand > operands() const
Definition Metadata.h:1441
unsigned getNumOperands() const
Return number of MDNode operands.
Definition Metadata.h:1449
Tracking metadata reference owned by Metadata.
Definition Metadata.h:908
A single uniqued string.
Definition Metadata.h:734
LLVM_ABI StringRef getString() const
Definition Metadata.cpp:613
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
Root of the metadata hierarchy.
Definition Metadata.h:65
Diagnostic information for optimization analysis remarks.
The optimization diagnostic interface.
bool allowExtraAnalysis(StringRef PassName) const
Whether we allow for extra compile-time budget to perform more analysis to produce fewer false positi...
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
static LLVM_ABI bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
bool hasExactFPMath() const
Returns true if the recurrence has floating-point math that requires precise (ordered) operations.
static LLVM_ABI bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction in TheLoop.
bool hasUsesOutsideReductionChain() const
Returns true if the reduction PHI has any uses outside the reduction chain.
RecurKind getRecurrenceKind() const
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visit(const SCEV *S)
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
static constexpr auto FlagNone
The main scalar evolution driver.
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getCouldNotCompute()
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
LLVM_ABI std::string str() const
Return the twine contents as a std::string.
Definition Twine.cpp:17
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
Definition Type.cpp:294
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition Type.h:186
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
Definition Type.h:265
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
Value * getOperand(unsigned i) const
Definition User.h:207
static bool hasMaskedVariant(const CallInst &CI, std::optional< ElementCount > VF=std::nullopt)
Definition VectorUtils.h:87
static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)
Retrieve all the VFInfo instances associated to the CallInst CI.
Definition VectorUtils.h:76
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition Value.h:441
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
static LLVM_ABI bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
static constexpr bool isKnownLE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition TypeSize.h:231
constexpr bool isZero() const
Definition TypeSize.h:154
const ParentTy * getParent() const
Definition ilist_node.h:34
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
void reportVectorizationFailure(const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag, OptimizationRemarkEmitter *ORE, const Loop *TheLoop, Instruction *I=nullptr)
Reports a vectorization failure: print DebugMsg for debugging purposes along with the corresponding o...
TwoOps_match< ValueOpTy, PointerOpTy, Instruction::Store > m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp)
Matches StoreInst.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
CmpClass_match< LHS, RHS, CmpInst, true > m_c_Cmp(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
auto m_UMax(const Opnd0 &Op0, const Opnd1 &Op1)
auto m_Value()
Match an arbitrary value and ignore it.
match_combine_or< match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > >, OpTy > m_ZExtOrSExtOrSelf(const OpTy &Op)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
bool match(const SCEV *S, const Pattern &P)
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > dyn_extract(Y &&MD)
Extract a Value from Metadata, if any.
Definition Metadata.h:708
Add a small namespace to avoid name clashes with the classes used in the streaming interface.
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
bool isSimple(Instruction *I)
Definition SLPUtils.cpp:843
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
LLVM_ABI bool collectCompressedPtrs(DenseMap< Value *, const SCEVAddRecExpr * > &CompressedPtrs, const Loop &L, const ConditionalInductionDescriptor &CondID, ScalarEvolution &SE)
Collect pointer values used by loads and stores whose addresses are derived from the conditional indu...
@ Offset
Definition DWP.cpp:577
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition STLExtras.h:1685
LLVM_ABI Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ Load
The value being inserted comes from a load (InsertElement only).
static bool canWidenTypes(Instruction &I, bool AllowStructCalls, OptimizationRemarkEmitter *ORE, Loop *TheLoop)
Returns true if the types produced and stored by I can be widened, otherwise reports a vectorization ...
static bool canVectorizeOperandBundles(Instruction &I, OptimizationRemarkEmitter *ORE, Loop *TheLoop)
Calls with operand bundles other than llvm.assume cannot be widened.
static bool matchCombinedExitCondition(Value *Cond, Instruction *&CountableCond, Value *&Ptr, Instruction *&Load, Value *&Other, ScalarEvolution &SE, Loop *TheLoop)
Matches a combined exit condition consisting of an uncountable condition and a countable condition,...
HistogramUpdateKind
The kind of update operation performed on the buckets of a histogram, i.e.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2229
LLVM_ABI bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
Definition Loads.cpp:452
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM_ABI std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DominatorTree &DT, const SymbolicStrideMap &StridesMap=SymbolicStrideMap(), bool ShouldCheckWrap=true, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
If the pointer has a constant stride return it in units of the access type size.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition MathExtras.h:280
DenseMap< Value *, const SCEVUnknown * > SymbolicStrideMap
Maps a pointer to its symbolic (non-constant) stride.
static IntegerType * getWiderInductionTy(const DataLayout &DL, Type *Ty0, Type *Ty1)
static IntegerType * getInductionIntegerTy(const DataLayout &DL, Type *Ty)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1769
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A, StoreInst *B)
Returns true if A and B have same pointer operands or same SCEVs addresses.
@ Other
Any other memory.
Definition ModRef.h:68
bool canVectorizeTy(Type *Ty)
Returns true if Ty is a valid vector element type, void, or an unpacked literal struct where all elem...
TargetTransformInfo TTI
static bool isDisallowedStridedPointerInduction(const InductionDescriptor &ID, const VectorizeOptions &Opts)
Returns true if ID is a pointer induction with a non-constant step.
LLVM_ABI bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic has a scalar operand.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
static bool canVectorizeSwiftErrorUses(Instruction &I, OptimizationRemarkEmitter *ORE, Loop *TheLoop)
Returns true if I does not use a swifterror value, otherwise reports a vectorization failure for TheL...
LLVM_ABI bool isReadOnlyLoop(Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, SmallVectorImpl< LoadInst * > &NonDereferenceableAndAlignedLoads, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns true if the loop contains read-only memory accesses and doesn't throw.
Definition Loads.cpp:956
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
Definition Sequence.h:341
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition STLExtras.h:2210
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
static bool matchUncountableExitCondition(Value *Cond, Value *&Ptr, Instruction *&Load, Value *&Other)
Matches an exit condition formed by comparing a value loaded from memory with another term.
static bool findHistogram(LoadInst *LI, StoreInst *HSt, Loop *TheLoop, const PredicatedScalarEvolution &PSE, SmallVectorImpl< HistogramInfo > &Histograms)
Find histogram operations that match high-level code in loops:
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI)
Checks if a function is scalarizable according to the TLI, in the sense that it should be vectorized ...
static bool matchCountableExitCondition(Value *Cond, ScalarEvolution &SE, Loop *TheLoop)
Matches an exit condition formed by comparing the current value of an affine add recurrence in the gi...
LLVM_ABI bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC=nullptr, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
Definition Loads.cpp:306
static bool canWidenResultType(const Instruction &I, bool AllowStructCalls)
Returns true if the type produced by I can be widened.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
Definition Casting.h:866
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Dependece between memory access instructions.
Instruction * getDestination(const MemoryDepChecker &DepChecker) const
Return the destination instruction of the dependence.
Instruction * getSource(const MemoryDepChecker &DepChecker) const
Return the source instruction of the dependence.
static LLVM_ABI VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
TODO: The following VectorizationFactor was pulled out of LoopVectorizationCostModel class.
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
static LLVM_ABI const unsigned MaxVectorWidth
Maximum SIMD width.
static LLVM_ABI bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
static LLVM_ABI unsigned VectorizationInterleave
Interleave factor as overridden by the user.
static LLVM_ABI ElementCount VectorizationFactor
VF as overridden by the user.