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
17#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
18#include "LoopVectorizationPlanner.h"
19#include "llvm/Analysis/AliasAnalysis.h"
20#include "llvm/Analysis/Loads.h"
21#include "llvm/Analysis/LoopInfo.h"
22#include "llvm/Analysis/MustExecute.h"
23#include "llvm/Analysis/OptimizationRemarkEmitter.h"
24#include "llvm/Analysis/ScalarEvolutionExpressions.h"
25#include "llvm/Analysis/TargetLibraryInfo.h"
26#include "llvm/Analysis/TargetTransformInfo.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/Analysis/VectorUtils.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/IR/PatternMatch.h"
32#include "llvm/Transforms/Utils/SizeOpts.h"
33#include "llvm/Transforms/Vectorize/LoopVectorize.h"
34
35using namespace llvm;
36using namespace PatternMatch;
37using namespace LoopVectorizationUtils;
38
39#define LV_NAME "loop-vectorize"
40#define DEBUG_TYPE LV_NAME
41
42static cl::opt<bool>
43 EnableIfConversion("enable-if-conversion", cl::init(Val: true), cl::Hidden,
44 cl::desc("Enable if-conversion during vectorization."));
45
46static cl::opt<bool>
47AllowStridedPointerIVs("lv-strided-pointer-ivs", cl::init(Val: false), cl::Hidden,
48 cl::desc("Enable recognition of non-constant strided "
49 "pointer induction variables."));
50
51static cl::opt<bool>
52 HintsAllowReordering("hints-allow-reordering", cl::init(Val: true), cl::Hidden,
53 cl::desc("Allow enabling loop hints to reorder "
54 "FP operations during vectorization."));
55
56static cl::opt<LoopVectorizeHints::ScalableForceKind>
57 ForceScalableVectorization(
58 "scalable-vectorization", cl::init(Val: LoopVectorizeHints::SK_Unspecified),
59 cl::Hidden,
60 cl::desc("Control whether the compiler can use scalable vectors to "
61 "vectorize a loop"),
62 cl::values(
63 clEnumValN(LoopVectorizeHints::SK_FixedWidthOnly, "off",
64 "Scalable vectorization is disabled."),
65 clEnumValN(
66 LoopVectorizeHints::SK_PreferScalable, "preferred",
67 "Scalable vectorization is available and favored when the "
68 "cost is inconclusive."),
69 clEnumValN(
70 LoopVectorizeHints::SK_PreferScalable, "on",
71 "Scalable vectorization is available and favored when the "
72 "cost is inconclusive."),
73 clEnumValN(
74 LoopVectorizeHints::SK_AlwaysScalable, "always",
75 "Scalable vectorization is available and always favored when "
76 "feasible")));
77
78static cl::opt<bool> EnableHistogramVectorization(
79 "enable-histogram-loop-vectorization", cl::init(Val: false), cl::Hidden,
80 cl::desc("Enables autovectorization of some loops containing histograms"));
81
82/// Maximum vectorization interleave count.
83static const unsigned MaxInterleaveFactor = 16;
84
85namespace llvm {
86
87bool LoopVectorizeHints::Hint::validate(unsigned Val) {
88 switch (Kind) {
89 case HK_WIDTH:
90 return isPowerOf2_32(Value: Val) && Val <= VectorizerParams::MaxVectorWidth;
91 case HK_INTERLEAVE:
92 return isPowerOf2_32(Value: Val) && Val <= MaxInterleaveFactor;
93 case HK_ISVECTORIZED:
94 return (Val == 0 || Val == 1);
95 }
96 return false;
97}
98
99LoopVectorizeHints::LoopVectorizeHints(const Loop *L,
100 bool InterleaveOnlyWhenForced,
101 OptimizationRemarkEmitter &ORE,
102 const TargetTransformInfo *TTI)
103 : Width("vectorize.width",
104 VectorizerParams::VectorizationFactor.getKnownMinValue(), HK_WIDTH),
105 Interleave("interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE),
106 Force(FK_Undefined), IsVectorized("isvectorized", 0, HK_ISVECTORIZED),
107 Predicate(FK_Undefined), Scalable(SK_Unspecified), TheLoop(L), ORE(ORE) {
108 // Populate values with existing loop metadata.
109 getHintsFromMetadata();
110
111 // force-vector-interleave overrides DisableInterleaving.
112 if (VectorizerParams::isInterleaveForced())
113 Interleave.Value = VectorizerParams::VectorizationInterleave;
114
115 // If the metadata doesn't explicitly specify whether to enable scalable
116 // vectorization, then decide based on the following criteria (increasing
117 // level of priority):
118 // - Target default
119 // - Metadata width
120 // - Force option (always overrides)
121 if ((LoopVectorizeHints::ScalableForceKind)Scalable == SK_Unspecified) {
122 if (TTI)
123 Scalable = TTI->enableScalableVectorization() ? SK_PreferScalable
124 : SK_FixedWidthOnly;
125
126 if (Width.Value)
127 // If the width is set, but the metadata says nothing about the scalable
128 // property, then assume it concerns only a fixed-width UserVF.
129 // If width is not set, the flag takes precedence.
130 Scalable = SK_FixedWidthOnly;
131 }
132
133 // If the flag is set to force any use of scalable vectors, override the loop
134 // hints.
135 if (ForceScalableVectorization.getValue() !=
136 LoopVectorizeHints::SK_Unspecified)
137 Scalable = ForceScalableVectorization.getValue();
138
139 // If force-vector-width is scalable, force scalable vectorization.
140 if (VectorizerParams::VectorizationFactor.isScalable())
141 Scalable = SK_AlwaysScalable;
142
143 // Scalable vectorization is disabled if no preference is specified.
144 if ((LoopVectorizeHints::ScalableForceKind)Scalable == SK_Unspecified)
145 Scalable = SK_FixedWidthOnly;
146
147 if (IsVectorized.Value != 1)
148 // If the vectorization width and interleaving count are both 1 then
149 // consider the loop to have been already vectorized because there's
150 // nothing more that we can do.
151 IsVectorized.Value =
152 getWidth() == ElementCount::getFixed(MinVal: 1) && getInterleave() == 1;
153 LLVM_DEBUG(if (InterleaveOnlyWhenForced && getInterleave() == 1) dbgs()
154 << "LV: Interleaving disabled by the pass manager\n");
155}
156
157void LoopVectorizeHints::setAlreadyVectorized() {
158 TheLoop->addIntLoopAttribute(Name: "llvm.loop.isvectorized", Value: 1,
159 RemovePrefixes: {Twine(Prefix(), "vectorize.").str(),
160 Twine(Prefix(), "interleave.").str()});
161
162 // Update internal cache.
163 IsVectorized.Value = 1;
164}
165
166void LoopVectorizeHints::reportDisallowedVectorization(
167 const StringRef DebugMsg, const StringRef RemarkName,
168 const StringRef RemarkMsg, const Loop *L) const {
169 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: " << DebugMsg << ".\n");
170 ORE.emit(OptDiag: OptimizationRemarkMissed(LV_NAME, RemarkName, L->getStartLoc(),
171 L->getHeader())
172 << "loop not vectorized: " << RemarkMsg);
173}
174
175bool LoopVectorizeHints::allowVectorization(
176 Function *F, Loop *L, bool VectorizeOnlyWhenForced) const {
177 if (getForce() == LoopVectorizeHints::FK_Disabled) {
178 if (Force == LoopVectorizeHints::FK_Disabled) {
179 reportDisallowedVectorization(DebugMsg: "#pragma vectorize disable",
180 RemarkName: "MissedExplicitlyDisabled",
181 RemarkMsg: "vectorization is explicitly disabled", L);
182 } else if (hasDisableAllTransformsHint(L)) {
183 reportDisallowedVectorization(DebugMsg: "loop hasDisableAllTransformsHint",
184 RemarkName: "MissedTransformsDisabled",
185 RemarkMsg: "loop transformations are disabled", L);
186 } else {
187 llvm_unreachable("loop vect disabled for an unknown reason");
188 }
189 return false;
190 }
191
192 if (VectorizeOnlyWhenForced && getForce() != LoopVectorizeHints::FK_Enabled) {
193 reportDisallowedVectorization(
194 DebugMsg: "VectorizeOnlyWhenForced is set, and no #pragma vectorize enable",
195 RemarkName: "MissedForceOnly", RemarkMsg: "only vectorizing loops that explicitly request it",
196 L);
197 return false;
198 }
199
200 if (getIsVectorized() == 1) {
201 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
202 // FIXME: Add interleave.disable metadata. This will allow
203 // vectorize.disable to be used without disabling the pass and errors
204 // to differentiate between disabled vectorization and a width of 1.
205 ORE.emit(RemarkBuilder: [&]() {
206 return OptimizationRemarkAnalysis(LV_NAME, "AllDisabled",
207 L->getStartLoc(), L->getHeader())
208 << "loop not vectorized: vectorization and interleaving are "
209 "explicitly disabled, or the loop has already been "
210 "vectorized";
211 });
212 return false;
213 }
214
215 return true;
216}
217
218void LoopVectorizeHints::emitRemarkWithHints() const {
219 using namespace ore;
220
221 ORE.emit(RemarkBuilder: [&]() {
222 if (Force == LoopVectorizeHints::FK_Disabled)
223 return OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled",
224 TheLoop->getStartLoc(),
225 TheLoop->getHeader())
226 << "loop not vectorized: vectorization is explicitly disabled";
227
228 OptimizationRemarkMissed R(LV_NAME, "MissedDetails", TheLoop->getStartLoc(),
229 TheLoop->getHeader());
230 R << "loop not vectorized";
231 if (Force == LoopVectorizeHints::FK_Enabled) {
232 R << " (Force=" << NV("Force", true);
233 if (Width.Value != 0)
234 R << ", Vector Width=" << NV("VectorWidth", getWidth());
235 if (getInterleave() != 0)
236 R << ", Interleave Count=" << NV("InterleaveCount", getInterleave());
237 R << ")";
238 }
239 return R;
240 });
241}
242
243bool LoopVectorizeHints::allowReordering() const {
244 // Allow the vectorizer to change the order of operations if enabling
245 // loop hints are provided
246 ElementCount EC = getWidth();
247 return HintsAllowReordering &&
248 (getForce() == LoopVectorizeHints::FK_Enabled ||
249 EC.getKnownMinValue() > 1);
250}
251
252void LoopVectorizeHints::getHintsFromMetadata() {
253 MDNode *LoopID = TheLoop->getLoopID();
254 if (!LoopID)
255 return;
256
257 // First operand should refer to the loop id itself.
258 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
259 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
260
261 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) {
262 const MDString *S = nullptr;
263 SmallVector<Metadata *, 4> Args;
264
265 // The expected hint is either a MDString or a MDNode with the first
266 // operand a MDString.
267 if (const MDNode *MD = dyn_cast<MDNode>(Val: MDO)) {
268 if (!MD || MD->getNumOperands() == 0)
269 continue;
270 S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
271 for (unsigned Idx = 1; Idx < MD->getNumOperands(); ++Idx)
272 Args.push_back(Elt: MD->getOperand(I: Idx));
273 } else {
274 S = dyn_cast<MDString>(Val: MDO);
275 assert(Args.size() == 0 && "too many arguments for MDString");
276 }
277
278 if (!S)
279 continue;
280
281 // Check if the hint starts with the loop metadata prefix.
282 StringRef Name = S->getString();
283 // The single-operand enable/disable pair carries no argument.
284 if (Args.empty()) {
285 if (Name == "llvm.loop.vectorize.enable")
286 Force = FK_Enabled;
287 else if (Name == "llvm.loop.vectorize.disable")
288 Force = FK_Disabled;
289 else if (Name == "llvm.loop.vectorize.predicate.enable")
290 Predicate = FK_Enabled;
291 else if (Name == "llvm.loop.vectorize.predicate.disable")
292 Predicate = FK_Disabled;
293 else if (Name == "llvm.loop.vectorize.scalable.enable")
294 Scalable = SK_PreferScalable;
295 else if (Name == "llvm.loop.vectorize.scalable.disable")
296 Scalable = SK_FixedWidthOnly;
297 continue;
298 }
299 if (Args.size() == 1)
300 setHint(Name, Arg: Args[0]);
301 }
302}
303
304void LoopVectorizeHints::setHint(StringRef Name, Metadata *Arg) {
305 if (!Name.consume_front(Prefix: Prefix()))
306 return;
307
308 const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(MD&: Arg);
309 if (!C)
310 return;
311 unsigned Val = C->getZExtValue();
312
313 // Force, Predicate, and Scalable are omitted: they are only spelled as
314 // single-operand enable/disable nodes, which never reach setHint().
315 Hint *Hints[] = {&Width, &Interleave, &IsVectorized};
316 for (auto *H : Hints) {
317 if (Name == H->Name) {
318 if (H->validate(Val))
319 H->Value = Val;
320 else
321 LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
322 break;
323 }
324 }
325}
326
327// Return true if the inner loop \p Lp is uniform with regard to the outer loop
328// \p OuterLp (i.e., if the outer loop is vectorized, all the vector lanes
329// executing the inner loop will execute the same iterations). This check is
330// very constrained for now but it will be relaxed in the future. \p Lp is
331// considered uniform if it meets all the following conditions:
332// 1) it has a canonical IV (starting from 0 and with stride 1),
333// 2) its latch terminator is a conditional branch and,
334// 3) its latch condition is a compare instruction whose operands are the
335// canonical IV and an OuterLp invariant.
336// This check doesn't take into account the uniformity of other conditions not
337// related to the loop latch because they don't affect the loop uniformity.
338//
339// NOTE: We decided to keep all these checks and its associated documentation
340// together so that we can easily have a picture of the current supported loop
341// nests. However, some of the current checks don't depend on \p OuterLp and
342// would be redundantly executed for each \p Lp if we invoked this function for
343// different candidate outer loops. This is not the case for now because we
344// don't currently have the infrastructure to evaluate multiple candidate outer
345// loops and \p OuterLp will be a fixed parameter while we only support explicit
346// outer loop vectorization. It's also very likely that these checks go away
347// before introducing the aforementioned infrastructure. However, if this is not
348// the case, we should move the \p OuterLp independent checks to a separate
349// function that is only executed once for each \p Lp.
350static bool isUniformLoop(Loop *Lp, Loop *OuterLp) {
351 assert(Lp->getLoopLatch() && "Expected loop with a single latch.");
352
353 // If Lp is the outer loop, it's uniform by definition.
354 if (Lp == OuterLp)
355 return true;
356 assert(OuterLp->contains(Lp) && "OuterLp must contain Lp.");
357
358 // 1.
359 PHINode *IV = Lp->getCanonicalInductionVariable();
360 if (!IV) {
361 LLVM_DEBUG(dbgs() << "LV: Canonical IV not found.\n");
362 return false;
363 }
364
365 // 2.
366 BasicBlock *Latch = Lp->getLoopLatch();
367 auto *LatchBr = dyn_cast<CondBrInst>(Val: Latch->getTerminator());
368 if (!LatchBr) {
369 LLVM_DEBUG(dbgs() << "LV: Unsupported loop latch branch.\n");
370 return false;
371 }
372
373 // 3.
374 auto *LatchCmp = dyn_cast<CmpInst>(Val: LatchBr->getCondition());
375 if (!LatchCmp) {
376 LLVM_DEBUG(
377 dbgs() << "LV: Loop latch condition is not a compare instruction.\n");
378 return false;
379 }
380
381 Value *CondOp0 = LatchCmp->getOperand(i_nocapture: 0);
382 Value *CondOp1 = LatchCmp->getOperand(i_nocapture: 1);
383 Value *IVUpdate = IV->getIncomingValueForBlock(BB: Latch);
384 if (!(CondOp0 == IVUpdate && OuterLp->isLoopInvariant(V: CondOp1)) &&
385 !(CondOp1 == IVUpdate && OuterLp->isLoopInvariant(V: CondOp0))) {
386 LLVM_DEBUG(dbgs() << "LV: Loop latch condition is not uniform.\n");
387 return false;
388 }
389
390 return true;
391}
392
393// Return true if \p Lp and all its nested loops are uniform with regard to \p
394// OuterLp.
395static bool isUniformLoopNest(Loop *Lp, Loop *OuterLp) {
396 if (!isUniformLoop(Lp, OuterLp))
397 return false;
398
399 // Check if nested loops are uniform.
400 for (Loop *SubLp : *Lp)
401 if (!isUniformLoopNest(Lp: SubLp, OuterLp))
402 return false;
403
404 return true;
405}
406
407static IntegerType *getInductionIntegerTy(const DataLayout &DL, Type *Ty) {
408 assert(Ty->isIntOrPtrTy() && "Expected integer or pointer type");
409
410 if (Ty->isPointerTy())
411 return DL.getIntPtrType(C&: Ty->getContext(), AddressSpace: Ty->getPointerAddressSpace());
412
413 // It is possible that char's or short's overflow when we ask for the loop's
414 // trip count, work around this by changing the type size.
415 if (Ty->getScalarSizeInBits() < 32)
416 return Type::getInt32Ty(C&: Ty->getContext());
417
418 return cast<IntegerType>(Val: Ty);
419}
420
421static IntegerType *getWiderInductionTy(const DataLayout &DL, Type *Ty0,
422 Type *Ty1) {
423 IntegerType *TyA = getInductionIntegerTy(DL, Ty: Ty0);
424 IntegerType *TyB = getInductionIntegerTy(DL, Ty: Ty1);
425 return TyA->getScalarSizeInBits() > TyB->getScalarSizeInBits() ? TyA : TyB;
426}
427
428/// Returns true if A and B have same pointer operands or same SCEVs addresses
429static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A,
430 StoreInst *B) {
431 // Compare store
432 if (A == B)
433 return true;
434
435 // Otherwise Compare pointers
436 Value *APtr = A->getPointerOperand();
437 Value *BPtr = B->getPointerOperand();
438 if (APtr == BPtr)
439 return true;
440
441 // Otherwise compare address SCEVs
442 return SE->getSCEV(V: APtr) == SE->getSCEV(V: BPtr);
443}
444
445void LoopVectorizationLegality::collectUnitStridePredicates() const {
446 if (!AllowRuntimeSCEVChecks || !TheLoop->isInnermost())
447 return;
448
449 for (BasicBlock *BB : TheLoop->blocks())
450 for (Instruction &I : *BB)
451 if (Value *Ptr = getLoadStorePointerOperand(V: &I))
452 isConsecutivePtr(AccessTy: getLoadStoreType(I: &I), Ptr);
453}
454
455int LoopVectorizationLegality::isConsecutivePtr(Type *AccessTy,
456 Value *Ptr) const {
457 // FIXME: Currently, the set of symbolic strides is sometimes queried before
458 // it's collected. This happens from canVectorizeWithIfConvert, when the
459 // pointer is checked to reference consecutive elements suitable for a
460 // masked access.
461 // Stride versioning requires adding a SCEV equality predicate; only consult
462 // the symbolic strides when runtime SCEV checks are permitted.
463 const auto &Strides = LAI && AllowRuntimeSCEVChecks
464 ? LAI->getSymbolicStrides()
465 : DenseMap<Value *, const SCEV *>();
466 SmallVector<const SCEVPredicate *> Predicates;
467 int Stride = getPtrStride(PSE, AccessTy, Ptr, Lp: TheLoop, DT: *DT, StridesMap: Strides, ShouldCheckWrap: false,
468 Predicates: AllowRuntimeSCEVChecks ? &Predicates : nullptr)
469 .value_or(u: 0);
470 if (Stride != 1 && Stride != -1)
471 return 0;
472 PSE.addPredicates(Preds: Predicates);
473 return Stride;
474}
475
476bool LoopVectorizationLegality::isInvariant(Value *V) const {
477 return LAI->isInvariant(V);
478}
479
480namespace {
481/// A rewriter to build the SCEVs for each of the VF lanes in the expected
482/// vectorized loop, which can then be compared to detect their uniformity. This
483/// is done by replacing the AddRec SCEVs of the original scalar loop (TheLoop)
484/// with new AddRecs where the step is multiplied by StepMultiplier and Offset *
485/// Step is added. Also checks if all sub-expressions are analyzable w.r.t.
486/// uniformity.
487class SCEVAddRecForUniformityRewriter
488 : public SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter> {
489 /// Multiplier to be applied to the step of AddRecs in TheLoop.
490 unsigned StepMultiplier;
491
492 /// Offset to be added to the AddRecs in TheLoop.
493 unsigned Offset;
494
495 /// Loop for which to rewrite AddRecsFor.
496 Loop *TheLoop;
497
498 /// Is any sub-expressions not analyzable w.r.t. uniformity?
499 bool CannotAnalyze = false;
500
501 bool canAnalyze() const { return !CannotAnalyze; }
502
503public:
504 SCEVAddRecForUniformityRewriter(ScalarEvolution &SE, unsigned StepMultiplier,
505 unsigned Offset, Loop *TheLoop)
506 : SCEVRewriteVisitor(SE), StepMultiplier(StepMultiplier), Offset(Offset),
507 TheLoop(TheLoop) {}
508
509 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
510 assert(Expr->getLoop() == TheLoop &&
511 "addrec outside of TheLoop must be invariant and should have been "
512 "handled earlier");
513 // Build a new AddRec by multiplying the step by StepMultiplier and
514 // incrementing the start by Offset * step.
515 Type *Ty = Expr->getType();
516 const SCEV *Step = Expr->getStepRecurrence(SE);
517 if (!SE.isLoopInvariant(S: Step, L: TheLoop)) {
518 CannotAnalyze = true;
519 return Expr;
520 }
521 const SCEV *NewStep =
522 SE.getMulExpr(LHS: Step, RHS: SE.getConstant(Ty, V: StepMultiplier));
523 const SCEV *ScaledOffset = SE.getMulExpr(LHS: Step, RHS: SE.getConstant(Ty, V: Offset));
524 const SCEV *NewStart =
525 SE.getAddExpr(LHS: Expr->getStart(), RHS: SCEVUse(ScaledOffset));
526 return SE.getAddRecExpr(Start: NewStart, Step: NewStep, L: TheLoop, Flags: SCEV::FlagAnyWrap);
527 }
528
529 const SCEV *visit(const SCEV *S) {
530 if (CannotAnalyze || SE.isLoopInvariant(S, L: TheLoop))
531 return S;
532 return SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter>::visit(S);
533 }
534
535 const SCEV *visitUnknown(const SCEVUnknown *S) {
536 if (SE.isLoopInvariant(S, L: TheLoop))
537 return S;
538 // The value could vary across iterations.
539 CannotAnalyze = true;
540 return S;
541 }
542
543 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *S) {
544 // Could not analyze the expression.
545 CannotAnalyze = true;
546 return S;
547 }
548
549 static const SCEV *rewrite(const SCEV *S, ScalarEvolution &SE,
550 unsigned StepMultiplier, unsigned Offset,
551 Loop *TheLoop) {
552 /// Bail out if the expression does not contain an UDiv expression.
553 /// Uniform values which are not loop invariant require operations to strip
554 /// out the lowest bits. For now just look for UDivs and use it to avoid
555 /// re-writing UDIV-free expressions for other lanes to limit compile time.
556 if (!SCEVExprContains(Root: S,
557 Pred: [](const SCEV *S) { return isa<SCEVUDivExpr>(Val: S); }))
558 return SE.getCouldNotCompute();
559
560 SCEVAddRecForUniformityRewriter Rewriter(SE, StepMultiplier, Offset,
561 TheLoop);
562 const SCEV *Result = Rewriter.visit(S);
563
564 if (Rewriter.canAnalyze())
565 return Result;
566 return SE.getCouldNotCompute();
567 }
568};
569
570} // namespace
571
572bool LoopVectorizationLegality::isUniform(
573 Value *V, std::optional<ElementCount> VF) const {
574 if (isInvariant(V))
575 return true;
576 if (!VF || VF->isScalable())
577 return false;
578 if (VF->isScalar())
579 return true;
580
581 // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
582 // never considered uniform.
583 auto *SE = PSE.getSE();
584 if (!SE->isSCEVable(Ty: V->getType()))
585 return false;
586 const SCEV *S = SE->getSCEV(V);
587
588 // Rewrite AddRecs in TheLoop to step by VF and check if the expression for
589 // lane 0 matches the expressions for all other lanes.
590 unsigned FixedVF = VF->getKnownMinValue();
591 const SCEV *FirstLaneExpr =
592 SCEVAddRecForUniformityRewriter::rewrite(S, SE&: *SE, StepMultiplier: FixedVF, Offset: 0, TheLoop);
593 if (isa<SCEVCouldNotCompute>(Val: FirstLaneExpr))
594 return false;
595
596 // Make sure the expressions for lanes FixedVF-1..1 match the expression for
597 // lane 0. We check lanes in reverse order for compile-time, as frequently
598 // checking the last lane is sufficient to rule out uniformity.
599 return all_of(Range: reverse(C: seq<unsigned>(Begin: 1, End: FixedVF)), P: [&](unsigned I) {
600 const SCEV *IthLaneExpr =
601 SCEVAddRecForUniformityRewriter::rewrite(S, SE&: *SE, StepMultiplier: FixedVF, Offset: I, TheLoop);
602 return FirstLaneExpr == IthLaneExpr;
603 });
604}
605
606bool LoopVectorizationLegality::isUniformMemOp(
607 Instruction &I, std::optional<ElementCount> VF) const {
608 Value *Ptr = getLoadStorePointerOperand(V: &I);
609 if (!Ptr)
610 return false;
611 // Note: There's nothing inherent which prevents predicated loads and
612 // stores from being uniform. The current lowering simply doesn't handle
613 // it; in particular, the cost model distinguishes scatter/gather from
614 // scalar w/predication, and we currently rely on the scalar path.
615 return isUniform(V: Ptr, VF) && !blockNeedsPredication(BB: I.getParent());
616}
617
618bool LoopVectorizationLegality::canVectorizeOuterLoop() {
619 assert(!TheLoop->isInnermost() && "We are not vectorizing an outer loop.");
620 // Store the result and return it at the end instead of exiting early, in case
621 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
622 bool Result = true;
623 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
624
625 for (BasicBlock *BB : TheLoop->blocks()) {
626 // Check whether the BB terminator is a branch. Any other terminator is
627 // not supported yet.
628 Instruction *Term = BB->getTerminator();
629 if (!isa<UncondBrInst, CondBrInst>(Val: Term)) {
630 reportVectorizationFailure(
631 DebugMsg: "Unsupported basic block terminator",
632 OREMsg: "loop control flow is not understood by vectorizer",
633 ORETag: "CFGNotUnderstood", ORE, TheLoop);
634 if (DoExtraAnalysis)
635 Result = false;
636 else
637 return false;
638 }
639
640 // Check whether the branch is a supported one. Only unconditional
641 // branches, conditional branches with an outer loop invariant condition or
642 // backedges are supported.
643 // FIXME: We skip these checks when VPlan predication is enabled as we
644 // want to allow divergent branches. This whole check will be removed
645 // once VPlan predication is on by default.
646 auto *Br = dyn_cast<CondBrInst>(Val: Term);
647 if (Br && !TheLoop->isLoopInvariant(V: Br->getCondition()) &&
648 !LI->isLoopHeader(BB: Br->getSuccessor(i: 0)) &&
649 !LI->isLoopHeader(BB: Br->getSuccessor(i: 1))) {
650 reportVectorizationFailure(
651 DebugMsg: "Unsupported conditional branch",
652 OREMsg: "loop control flow is not understood by vectorizer",
653 ORETag: "CFGNotUnderstood", ORE, TheLoop);
654 if (DoExtraAnalysis)
655 Result = false;
656 else
657 return false;
658 }
659 }
660
661 // Each nested loop must exit via its latch only, as a region with the latch
662 // as its only exiting block is created for it. Note that the branch check
663 // above rejects divergent exits, but exits with an outer-loop invariant
664 // condition are allowed through.
665 SmallVector<Loop *, 4> LoopNest = TheLoop->getLoopsInPreorder();
666 for (Loop *Lp : drop_begin(RangeOrContainer&: LoopNest)) {
667 if (Lp->getExitingBlock() != Lp->getLoopLatch()) {
668 reportVectorizationFailure(
669 DebugMsg: "Nested loop does not exit via its latch",
670 OREMsg: "loop control flow is not understood by vectorizer",
671 ORETag: "CFGNotUnderstood", ORE, TheLoop);
672 if (DoExtraAnalysis)
673 Result = false;
674 else
675 return false;
676 }
677 }
678
679 // Check whether inner loops are uniform. At this point, we only support
680 // simple outer loops scenarios with uniform nested loops.
681 if (!isUniformLoopNest(Lp: TheLoop /*loop nest*/,
682 OuterLp: TheLoop /*context outer loop*/)) {
683 reportVectorizationFailure(
684 DebugMsg: "Outer loop contains divergent loops",
685 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
686 ORE, TheLoop);
687 if (DoExtraAnalysis)
688 Result = false;
689 else
690 return false;
691 }
692
693 // Check whether we are able to set up outer loop induction.
694 if (!setupOuterLoopInductions()) {
695 reportVectorizationFailure(DebugMsg: "Unsupported outer loop Phi(s)",
696 ORETag: "UnsupportedPhi", ORE, TheLoop);
697 if (DoExtraAnalysis)
698 Result = false;
699 else
700 return false;
701 }
702
703 return Result;
704}
705
706void LoopVectorizationLegality::addInductionPhi(PHINode *Phi,
707 const InductionDescriptor &ID) {
708 Inductions[Phi] = ID;
709
710 // In case this induction also comes with casts that we know we can ignore
711 // in the vectorized loop body, record them here. All casts could be recorded
712 // here for ignoring, but suffices to record only the first (as it is the
713 // only one that may bw used outside the cast sequence).
714 ArrayRef<Instruction *> Casts = ID.getCastInsts();
715 if (!Casts.empty())
716 InductionCastsToIgnore.insert(Ptr: *Casts.begin());
717
718 Type *PhiTy = Phi->getType();
719 const DataLayout &DL = Phi->getDataLayout();
720
721 assert((PhiTy->isIntOrPtrTy() || PhiTy->isFloatingPointTy()) &&
722 "Expected int, ptr, or FP induction phi type");
723
724 // Get the widest type.
725 if (PhiTy->isIntOrPtrTy()) {
726 if (!WidestIndTy)
727 WidestIndTy = getInductionIntegerTy(DL, Ty: PhiTy);
728 else
729 WidestIndTy = getWiderInductionTy(DL, Ty0: PhiTy, Ty1: WidestIndTy);
730 }
731
732 // Int inductions are special because we only allow one IV.
733 if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
734 ID.getConstIntStepValue() && ID.getConstIntStepValue()->isOne() &&
735 isa<Constant>(Val: ID.getStartValue()) &&
736 cast<Constant>(Val: ID.getStartValue())->isNullValue()) {
737
738 // Use the phi node with the widest type as induction. Use the last
739 // one if there are multiple (no good reason for doing this other
740 // than it is expedient). We've checked that it begins at zero and
741 // steps by one, so this is a canonical induction variable.
742 if (!PrimaryInduction || PhiTy == WidestIndTy)
743 PrimaryInduction = Phi;
744 }
745
746 LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n");
747}
748
749bool LoopVectorizationLegality::setupOuterLoopInductions() {
750 BasicBlock *Header = TheLoop->getHeader();
751
752 // Returns true if a given Phi is a supported induction.
753 auto IsSupportedPhi = [&](PHINode &Phi) -> bool {
754 InductionDescriptor ID;
755 if (InductionDescriptor::isInductionPHI(Phi: &Phi, L: TheLoop, PSE, D&: ID) &&
756 ID.getKind() == InductionDescriptor::IK_IntInduction) {
757 addInductionPhi(Phi: &Phi, ID);
758 return true;
759 }
760 // Bail out for any Phi in the outer loop header that is not a supported
761 // induction.
762 LLVM_DEBUG(
763 dbgs() << "LV: Found unsupported PHI for outer loop vectorization.\n");
764 return false;
765 };
766
767 return llvm::all_of(Range: Header->phis(), P: IsSupportedPhi);
768}
769
770/// Checks if a function is scalarizable according to the TLI, in
771/// the sense that it should be vectorized and then expanded in
772/// multiple scalar calls. This is represented in the
773/// TLI via mappings that do not specify a vector name, as in the
774/// following example:
775///
776/// const VecDesc VecIntrinsics[] = {
777/// {"llvm.phx.abs.i32", "", 4}
778/// };
779static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI) {
780 const StringRef ScalarName = CI.getCalledFunction()->getName();
781 bool Scalarize = TLI.isFunctionVectorizable(F: ScalarName);
782 // Check that all known VFs are not associated to a vector
783 // function, i.e. the vector name is emty.
784 if (Scalarize) {
785 ElementCount WidestFixedVF, WidestScalableVF;
786 TLI.getWidestVF(ScalarF: ScalarName, FixedVF&: WidestFixedVF, ScalableVF&: WidestScalableVF);
787 for (ElementCount VF = ElementCount::getFixed(MinVal: 2);
788 ElementCount::isKnownLE(LHS: VF, RHS: WidestFixedVF); VF *= 2)
789 Scalarize &= !TLI.isFunctionVectorizable(F: ScalarName, VF);
790 for (ElementCount VF = ElementCount::getScalable(MinVal: 1);
791 ElementCount::isKnownLE(LHS: VF, RHS: WidestScalableVF); VF *= 2)
792 Scalarize &= !TLI.isFunctionVectorizable(F: ScalarName, VF);
793 assert((WidestScalableVF.isZero() || !Scalarize) &&
794 "Caller may decide to scalarize a variant using a scalable VF");
795 }
796 return Scalarize;
797}
798
799bool LoopVectorizationLegality::canVectorizeInstrs() {
800 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
801 bool Result = true;
802
803 // For each block in the loop.
804 for (BasicBlock *BB : TheLoop->blocks()) {
805 // Scan the instructions in the block and look for hazards.
806 for (Instruction &I : *BB) {
807 Result &= canVectorizeInstr(I);
808 if (!DoExtraAnalysis && !Result)
809 return false;
810 }
811 }
812
813 if (!PrimaryInduction) {
814 if (Inductions.empty()) {
815 reportVectorizationFailure(
816 DebugMsg: "Did not find one integer induction var",
817 OREMsg: "loop induction variable could not be identified",
818 ORETag: "NoInductionVariable", ORE, TheLoop);
819 return false;
820 }
821 if (!WidestIndTy) {
822 reportVectorizationFailure(
823 DebugMsg: "Did not find one integer induction var",
824 OREMsg: "integer loop induction variable could not be identified",
825 ORETag: "NoIntegerInductionVariable", ORE, TheLoop);
826 return false;
827 }
828 LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
829 }
830
831 // Now we know the widest induction type, check if our found induction
832 // is the same size. If it's not, unset it here and InnerLoopVectorizer
833 // will create another.
834 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
835 PrimaryInduction = nullptr;
836
837 return Result;
838}
839
840bool LoopVectorizationLegality::canVectorizeInstr(Instruction &I) {
841 BasicBlock *BB = I.getParent();
842 BasicBlock *Header = TheLoop->getHeader();
843
844 if (auto *Phi = dyn_cast<PHINode>(Val: &I)) {
845 Type *PhiTy = Phi->getType();
846 // Check that this PHI type is allowed.
847 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
848 !PhiTy->isPointerTy()) {
849 reportVectorizationFailure(
850 DebugMsg: "Found a non-int non-pointer PHI",
851 OREMsg: "loop control flow is not understood by vectorizer",
852 ORETag: "CFGNotUnderstood", ORE, TheLoop);
853 return false;
854 }
855
856 // If this PHINode is not in the header block, then we know that we
857 // can convert it to select during if-conversion. No need to check if
858 // the PHIs in this block are induction or reduction variables.
859 if (BB != Header) {
860 // Non-header phi nodes that have outside uses can be vectorized. Unsafe
861 // cyclic dependencies with header phis are identified during legalization
862 // for reduction, induction and fixed order recurrences.
863 return true;
864 }
865
866 // We only allow if-converted PHIs with exactly two incoming values.
867 if (Phi->getNumIncomingValues() != 2) {
868 reportVectorizationFailure(
869 DebugMsg: "Found an invalid PHI",
870 OREMsg: "loop control flow is not understood by vectorizer",
871 ORETag: "CFGNotUnderstood", ORE, TheLoop, I: Phi);
872 return false;
873 }
874
875 RecurrenceDescriptor RedDes;
876 if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC, DT,
877 SE: PSE.getSE())) {
878 Requirements->addExactFPMathInst(I: RedDes.getExactFPMathInst());
879 Reductions[Phi] = std::move(RedDes);
880 assert((!RedDes.hasUsesOutsideReductionChain() ||
881 RecurrenceDescriptor::isMinMaxRecurrenceKind(
882 RedDes.getRecurrenceKind())) &&
883 "Only min/max recurrences are allowed to have multiple uses "
884 "currently");
885 return true;
886 }
887
888 // We prevent matching non-constant strided pointer IVS to preserve
889 // historical vectorizer behavior after a generalization of the
890 // IVDescriptor code. The intent is to remove this check, but we
891 // have to fix issues around code quality for such loops first.
892 auto IsDisallowedStridedPointerInduction =
893 [](const InductionDescriptor &ID) {
894 if (AllowStridedPointerIVs)
895 return false;
896 return ID.getKind() == InductionDescriptor::IK_PtrInduction &&
897 ID.getConstIntStepValue() == nullptr;
898 };
899
900 InductionDescriptor ID;
901 if (InductionDescriptor::isInductionPHI(Phi, L: TheLoop, PSE, D&: ID) &&
902 !IsDisallowedStridedPointerInduction(ID)) {
903 addInductionPhi(Phi, ID);
904 Requirements->addExactFPMathInst(I: ID.getExactFPMathInst());
905 return true;
906 }
907
908 if (RecurrenceDescriptor::isFixedOrderRecurrence(Phi, TheLoop, DT)) {
909 FixedOrderRecurrences.insert(Ptr: Phi);
910 return true;
911 }
912
913 // As a last resort, coerce the PHI to a AddRec expression
914 // and re-try classifying it a an induction PHI.
915 if (InductionDescriptor::isInductionPHI(Phi, L: TheLoop, PSE, D&: ID, Assume: true) &&
916 !IsDisallowedStridedPointerInduction(ID)) {
917 addInductionPhi(Phi, ID);
918 return true;
919 }
920
921 reportVectorizationFailure(DebugMsg: "Found an unidentified PHI",
922 OREMsg: "value that could not be identified as "
923 "reduction is used outside the loop",
924 ORETag: "NonReductionValueUsedOutsideLoop", ORE, TheLoop,
925 I: Phi);
926 return false;
927 } // end of PHI handling
928
929 // We handle calls that:
930 // * Have a mapping to an IR intrinsic.
931 // * Have a vector version available.
932 auto *CI = dyn_cast<CallInst>(Val: &I);
933
934 if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
935 !(CI->getCalledFunction() && TLI &&
936 (!VFDatabase::getMappings(CI: *CI).empty() || isTLIScalarize(TLI: *TLI, CI: *CI)))) {
937 // If the call is a recognized math libary call, it is likely that
938 // we can vectorize it given loosened floating-point constraints.
939 bool IsMathLibCall =
940 TLI && CI->getCalledFunction() && CI->getType()->isFloatingPointTy() &&
941 TLI->hasOptimizedCodeGen(
942 F: TLI->getLibFunc(funcName: CI->getCalledFunction()->getName()));
943
944 if (IsMathLibCall) {
945 // TODO: Ideally, we should not use clang-specific language here,
946 // but it's hard to provide meaningful yet generic advice.
947 // Also, should this be guarded by allowExtraAnalysis() and/or be part
948 // of the returned info from isFunctionVectorizable()?
949 reportVectorizationFailure(
950 DebugMsg: "Found a non-intrinsic callsite",
951 OREMsg: "library call cannot be vectorized. "
952 "Try compiling with -fno-math-errno, -ffast-math, "
953 "or similar flags",
954 ORETag: "CantVectorizeLibcall", ORE, TheLoop, I: CI);
955 } else {
956 reportVectorizationFailure(DebugMsg: "Found a non-intrinsic callsite",
957 OREMsg: "call instruction cannot be vectorized",
958 ORETag: "CantVectorizeLibcall", ORE, TheLoop, I: CI);
959 }
960 return false;
961 }
962
963 // Some intrinsics have scalar arguments and should be same in order for
964 // them to be vectorized (i.e. loop invariant).
965 if (CI) {
966 auto *SE = PSE.getSE();
967 Intrinsic::ID IntrinID = getVectorIntrinsicIDForCall(CI, TLI);
968 for (unsigned Idx = 0; Idx < CI->arg_size(); ++Idx)
969 if (isVectorIntrinsicWithScalarOpAtArg(ID: IntrinID, ScalarOpdIdx: Idx, TTI)) {
970 if (!SE->isLoopInvariant(S: PSE.getSCEV(V: CI->getOperand(i_nocapture: Idx)), L: TheLoop)) {
971 reportVectorizationFailure(
972 DebugMsg: "Found unvectorizable intrinsic",
973 OREMsg: "intrinsic instruction cannot be vectorized",
974 ORETag: "CantVectorizeIntrinsic", ORE, TheLoop, I: CI);
975 return false;
976 }
977 }
978 }
979
980 // If we found a vectorized variant of a function, note that so LV can
981 // make better decisions about maximum VF.
982 if (CI && !VFDatabase::getMappings(CI: *CI).empty())
983 VecCallVariantsFound = true;
984
985 auto CanWidenInstructionTy = [](Instruction const &Inst) {
986 Type *InstTy = Inst.getType();
987 if (!isa<StructType>(Val: InstTy))
988 return canVectorizeTy(Ty: InstTy);
989
990 // For now, we only recognize struct values returned from calls where
991 // all users are extractvalue as vectorizable. All element types of the
992 // struct must be types that can be widened.
993 return isa<CallInst>(Val: Inst) && canVectorizeTy(Ty: InstTy) &&
994 all_of(Range: Inst.users(), P: IsaPred<ExtractValueInst>);
995 };
996
997 // Check that the instruction return type is vectorizable.
998 // We can't vectorize casts from vector type to scalar type.
999 // Also, we can't vectorize extractelement instructions.
1000 if (!CanWidenInstructionTy(I) ||
1001 (isa<CastInst>(Val: I) &&
1002 !VectorType::isValidElementType(ElemTy: I.getOperand(i: 0)->getType())) ||
1003 isa<ExtractElementInst>(Val: I)) {
1004 reportVectorizationFailure(DebugMsg: "Found unvectorizable type",
1005 OREMsg: "instruction return type cannot be vectorized",
1006 ORETag: "CantVectorizeInstructionReturnType", ORE,
1007 TheLoop, I: &I);
1008 return false;
1009 }
1010
1011 // Check that the stored type is vectorizable.
1012 if (auto *ST = dyn_cast<StoreInst>(Val: &I)) {
1013 Type *T = ST->getValueOperand()->getType();
1014 if (!VectorType::isValidElementType(ElemTy: T)) {
1015 reportVectorizationFailure(DebugMsg: "Store instruction cannot be vectorized",
1016 ORETag: "CantVectorizeStore", ORE, TheLoop, I: ST);
1017 return false;
1018 }
1019
1020 // For nontemporal stores, check that a nontemporal vector version is
1021 // supported on the target.
1022 if (ST->getMetadata(KindID: LLVMContext::MD_nontemporal)) {
1023 // Arbitrarily try a vector of 2 elements.
1024 auto *VecTy = FixedVectorType::get(ElementType: T, /*NumElts=*/2);
1025 assert(VecTy && "did not find vectorized version of stored type");
1026 if (!TTI->isLegalNTStore(DataType: VecTy, Alignment: ST->getAlign())) {
1027 reportVectorizationFailure(
1028 DebugMsg: "nontemporal store instruction cannot be vectorized",
1029 ORETag: "CantVectorizeNontemporalStore", ORE, TheLoop, I: ST);
1030 return false;
1031 }
1032 }
1033
1034 } else if (auto *LD = dyn_cast<LoadInst>(Val: &I)) {
1035 if (LD->getMetadata(KindID: LLVMContext::MD_nontemporal)) {
1036 // For nontemporal loads, check that a nontemporal vector version is
1037 // supported on the target (arbitrarily try a vector of 2 elements).
1038 auto *VecTy = FixedVectorType::get(ElementType: I.getType(), /*NumElts=*/2);
1039 assert(VecTy && "did not find vectorized version of load type");
1040 if (!TTI->isLegalNTLoad(DataType: VecTy, Alignment: LD->getAlign())) {
1041 reportVectorizationFailure(
1042 DebugMsg: "nontemporal load instruction cannot be vectorized",
1043 ORETag: "CantVectorizeNontemporalLoad", ORE, TheLoop, I: LD);
1044 return false;
1045 }
1046 }
1047
1048 // FP instructions can allow unsafe algebra, thus vectorizable by
1049 // non-IEEE-754 compliant SIMD units.
1050 // This applies to floating-point math operations and calls, not memory
1051 // operations, shuffles, or casts, as they don't change precision or
1052 // semantics.
1053 } else if (I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp()) &&
1054 !I.isFast()) {
1055 LLVM_DEBUG(dbgs() << "LV: Found FP op with unsafe algebra.\n");
1056 Hints->setPotentiallyUnsafe();
1057 }
1058
1059 return true;
1060}
1061
1062/// Find histogram operations that match high-level code in loops:
1063/// \code
1064/// buckets[indices[i]]+=step;
1065/// \endcode
1066///
1067/// It matches a pattern starting from \p HSt, which Stores to the 'buckets'
1068/// array the computed histogram. It uses a BinOp to sum all counts, storing
1069/// them using a loop-variant index Load from the 'indices' input array.
1070///
1071/// On successful matches it updates the STATISTIC 'HistogramsDetected',
1072/// regardless of hardware support. When there is support, it additionally
1073/// stores the BinOp/Load pairs in \p HistogramCounts, as well the pointers
1074/// used to update histogram in \p HistogramPtrs.
1075static bool findHistogram(LoadInst *LI, StoreInst *HSt, Loop *TheLoop,
1076 const PredicatedScalarEvolution &PSE,
1077 SmallVectorImpl<HistogramInfo> &Histograms) {
1078
1079 // Store value must come from a Binary Operation.
1080 Instruction *HPtrInstr = nullptr;
1081 BinaryOperator *HBinOp = nullptr;
1082 if (!match(V: HSt, P: m_Store(ValueOp: m_BinOp(I&: HBinOp), PointerOp: m_Instruction(I&: HPtrInstr))))
1083 return false;
1084
1085 // BinOp must be an Add or a Sub modifying the bucket value by a
1086 // loop invariant amount.
1087 // FIXME: We assume the loop invariant term is on the RHS.
1088 // Fine for an immediate/constant, but maybe not a generic value?
1089 Value *HIncVal = nullptr;
1090 if (!match(V: HBinOp, P: m_Add(L: m_Load(Op: m_Specific(V: HPtrInstr)), R: m_Value(V&: HIncVal))) &&
1091 !match(V: HBinOp, P: m_Sub(L: m_Load(Op: m_Specific(V: HPtrInstr)), R: m_Value(V&: HIncVal))))
1092 return false;
1093
1094 // Make sure the increment value is loop invariant.
1095 if (!TheLoop->isLoopInvariant(V: HIncVal))
1096 return false;
1097
1098 // The address to store is calculated through a GEP Instruction.
1099 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: HPtrInstr);
1100 if (!GEP)
1101 return false;
1102
1103 // Restrict address calculation to constant indices except for the last term.
1104 Value *HIdx = nullptr;
1105 for (Value *Index : GEP->indices()) {
1106 if (HIdx)
1107 return false;
1108 if (!isa<ConstantInt>(Val: Index))
1109 HIdx = Index;
1110 }
1111
1112 if (!HIdx)
1113 return false;
1114
1115 // Check that the index is calculated by loading from another array. Ignore
1116 // any extensions.
1117 // FIXME: Support indices from other sources than a linear load from memory?
1118 // We're currently trying to match an operation looping over an array
1119 // of indices, but there could be additional levels of indirection
1120 // in place, or possibly some additional calculation to form the index
1121 // from the loaded data.
1122 Value *VPtrVal;
1123 if (!match(V: HIdx, P: m_ZExtOrSExtOrSelf(Op: m_Load(Op: m_Value(V&: VPtrVal)))))
1124 return false;
1125
1126 // Make sure the index address varies in this loop, not an outer loop.
1127 const auto *AR = dyn_cast<SCEVAddRecExpr>(Val: PSE.getSE()->getSCEV(V: VPtrVal));
1128 if (!AR || AR->getLoop() != TheLoop)
1129 return false;
1130
1131 // Ensure we'll have the same mask by checking that all parts of the histogram
1132 // (gather load, update, scatter store) are in the same block.
1133 LoadInst *IndexedLoad = cast<LoadInst>(Val: HBinOp->getOperand(i_nocapture: 0));
1134 BasicBlock *LdBB = IndexedLoad->getParent();
1135 if (LdBB != HBinOp->getParent() || LdBB != HSt->getParent())
1136 return false;
1137
1138 // The bucket value and its update must not be used outside the histogram.
1139 if (!IndexedLoad->hasOneUse() || !HBinOp->hasOneUse())
1140 return false;
1141
1142 LLVM_DEBUG(dbgs() << "LV: Found histogram for: " << *HSt << "\n");
1143
1144 // Store the operations that make up the histogram.
1145 Histograms.emplace_back(Args&: IndexedLoad, Args&: HBinOp, Args&: HSt);
1146 return true;
1147}
1148
1149bool LoopVectorizationLegality::canVectorizeIndirectUnsafeDependences() {
1150 // For now, we only support an IndirectUnsafe dependency that calculates
1151 // a histogram
1152 if (!EnableHistogramVectorization)
1153 return false;
1154
1155 // Find a single IndirectUnsafe dependency.
1156 const MemoryDepChecker::Dependence *IUDep = nullptr;
1157 const MemoryDepChecker &DepChecker = LAI->getDepChecker();
1158 const auto *Deps = DepChecker.getDependences();
1159 // If there were too many dependences, LAA abandons recording them. We can't
1160 // proceed safely if we don't know what the dependences are.
1161 if (!Deps)
1162 return false;
1163
1164 for (const MemoryDepChecker::Dependence &Dep : *Deps) {
1165 // Ignore dependencies that are either known to be safe or can be
1166 // checked at runtime.
1167 if (MemoryDepChecker::Dependence::isSafeForVectorization(Type: Dep.Type) !=
1168 MemoryDepChecker::VectorizationSafetyStatus::Unsafe)
1169 continue;
1170
1171 // We're only interested in IndirectUnsafe dependencies here, where the
1172 // address might come from a load from memory. We also only want to handle
1173 // one such dependency, at least for now.
1174 if (Dep.Type != MemoryDepChecker::Dependence::IndirectUnsafe || IUDep)
1175 return false;
1176
1177 IUDep = &Dep;
1178 }
1179 if (!IUDep)
1180 return false;
1181
1182 // For now only normal loads and stores are supported.
1183 LoadInst *LI = dyn_cast<LoadInst>(Val: IUDep->getSource(DepChecker));
1184 StoreInst *SI = dyn_cast<StoreInst>(Val: IUDep->getDestination(DepChecker));
1185
1186 if (!LI || !SI)
1187 return false;
1188
1189 LLVM_DEBUG(dbgs() << "LV: Checking for a histogram on: " << *SI << "\n");
1190 return findHistogram(LI, HSt: SI, TheLoop, PSE: LAI->getPSE(), Histograms);
1191}
1192
1193bool LoopVectorizationLegality::canVectorizeMemory() {
1194 LAI = &LAIs.getInfo(L&: *TheLoop);
1195 const OptimizationRemarkAnalysis *LAR = LAI->getReport();
1196 if (LAR) {
1197 ORE->emit(RemarkBuilder: [&]() {
1198 return OptimizationRemarkAnalysis(LV_NAME, "loop not vectorized: ", *LAR);
1199 });
1200 }
1201
1202 if (!LAI->canVectorizeMemory()) {
1203 if (hasUncountableExitWithSideEffects()) {
1204 reportVectorizationFailure(
1205 DebugMsg: "Cannot vectorize unsafe dependencies in uncountable exit loop with "
1206 "side effects",
1207 ORETag: "CantVectorizeUnsafeDependencyForEELoopWithSideEffects", ORE,
1208 TheLoop);
1209 return false;
1210 }
1211
1212 return canVectorizeIndirectUnsafeDependences();
1213 }
1214
1215 if (LAI->hasLoadStoreDependenceInvolvingLoopInvariantAddress()) {
1216 reportVectorizationFailure(DebugMsg: "We don't allow storing to uniform addresses",
1217 OREMsg: "write to a loop invariant address could not "
1218 "be vectorized",
1219 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE,
1220 TheLoop);
1221 return false;
1222 }
1223
1224 // We can vectorize stores to invariant address when final reduction value is
1225 // guaranteed to be stored at the end of the loop. Also, if decision to
1226 // vectorize loop is made, runtime checks are added so as to make sure that
1227 // invariant address won't alias with any other objects.
1228 if (!LAI->getStoresToInvariantAddresses().empty()) {
1229 // For each invariant address, check if last stored value is unconditional
1230 // and the address is not calculated inside the loop.
1231 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1232 if (!isInvariantStoreOfReduction(SI))
1233 continue;
1234
1235 if (blockNeedsPredication(BB: SI->getParent())) {
1236 reportVectorizationFailure(
1237 DebugMsg: "We don't allow storing to uniform addresses",
1238 OREMsg: "write of conditional recurring variant value to a loop "
1239 "invariant address could not be vectorized",
1240 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1241 return false;
1242 }
1243
1244 // Invariant address should be defined outside of loop. LICM pass usually
1245 // makes sure it happens, but in rare cases it does not, we do not want
1246 // to overcomplicate vectorization to support this case.
1247 if (Instruction *Ptr = dyn_cast<Instruction>(Val: SI->getPointerOperand())) {
1248 if (TheLoop->contains(Inst: Ptr)) {
1249 reportVectorizationFailure(
1250 DebugMsg: "Invariant address is calculated inside the loop",
1251 OREMsg: "write to a loop invariant address could not "
1252 "be vectorized",
1253 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1254 return false;
1255 }
1256 }
1257 }
1258
1259 if (LAI->hasStoreStoreDependenceInvolvingLoopInvariantAddress()) {
1260 // For each invariant address, check its last stored value is the result
1261 // of one of our reductions.
1262 //
1263 // We do not check if dependence with loads exists because that is already
1264 // checked via hasLoadStoreDependenceInvolvingLoopInvariantAddress.
1265 ScalarEvolution *SE = PSE.getSE();
1266 SmallVector<StoreInst *, 4> UnhandledStores;
1267 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1268 if (isInvariantStoreOfReduction(SI)) {
1269 // Earlier stores to this address are effectively deadcode.
1270 // With opaque pointers it is possible for one pointer to be used with
1271 // different sizes of stored values:
1272 // store i32 0, ptr %x
1273 // store i8 0, ptr %x
1274 // The latest store doesn't complitely overwrite the first one in the
1275 // example. That is why we have to make sure that types of stored
1276 // values are same.
1277 // TODO: Check that bitwidth of unhandled store is smaller then the
1278 // one that overwrites it and add a test.
1279 erase_if(C&: UnhandledStores, P: [SE, SI](StoreInst *I) {
1280 return storeToSameAddress(SE, A: SI, B: I) &&
1281 I->getValueOperand()->getType() ==
1282 SI->getValueOperand()->getType();
1283 });
1284 continue;
1285 }
1286 UnhandledStores.push_back(Elt: SI);
1287 }
1288
1289 bool IsOK = UnhandledStores.empty();
1290 // TODO: we should also validate against InvariantMemSets.
1291 if (!IsOK) {
1292 reportVectorizationFailure(
1293 DebugMsg: "We don't allow storing to uniform addresses",
1294 OREMsg: "write to a loop invariant address could not "
1295 "be vectorized",
1296 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1297 return false;
1298 }
1299 }
1300 }
1301
1302 PSE.addPredicate(Pred: LAI->getPSE().getPredicate());
1303 return true;
1304}
1305
1306bool LoopVectorizationLegality::canVectorizeFPMath(
1307 bool EnableStrictReductions) {
1308
1309 // First check if there is any ExactFP math or if we allow reassociations
1310 if (!Requirements->getExactFPInst() || Hints->allowReordering())
1311 return true;
1312
1313 // If the above is false, we have ExactFPMath & do not allow reordering.
1314 // If the EnableStrictReductions flag is set, first check if we have any
1315 // Exact FP induction vars, which we cannot vectorize.
1316 if (!EnableStrictReductions ||
1317 any_of(Range: getInductionVars(), P: [&](auto &Induction) -> bool {
1318 InductionDescriptor IndDesc = Induction.second;
1319 return IndDesc.getExactFPMathInst();
1320 }))
1321 return false;
1322
1323 // We can now only vectorize if all reductions with Exact FP math also
1324 // have the isOrdered flag set, which indicates that we can move the
1325 // reduction operations in-loop.
1326 return (all_of(Range: getReductionVars(), P: [&](auto &Reduction) -> bool {
1327 const RecurrenceDescriptor &RdxDesc = Reduction.second;
1328 return !RdxDesc.hasExactFPMath() || RdxDesc.isOrdered();
1329 }));
1330}
1331
1332bool LoopVectorizationLegality::isInvariantStoreOfReduction(StoreInst *SI) {
1333 return any_of(Range: getReductionVars(), P: [&](auto &Reduction) -> bool {
1334 const RecurrenceDescriptor &RdxDesc = Reduction.second;
1335 return RdxDesc.IntermediateStore == SI;
1336 });
1337}
1338
1339bool LoopVectorizationLegality::isInvariantAddressOfReduction(Value *V) {
1340 return any_of(Range: getReductionVars(), P: [&](auto &Reduction) -> bool {
1341 const RecurrenceDescriptor &RdxDesc = Reduction.second;
1342 if (!RdxDesc.IntermediateStore)
1343 return false;
1344
1345 ScalarEvolution *SE = PSE.getSE();
1346 Value *InvariantAddress = RdxDesc.IntermediateStore->getPointerOperand();
1347 return V == InvariantAddress ||
1348 SE->getSCEV(V) == SE->getSCEV(V: InvariantAddress);
1349 });
1350}
1351
1352bool LoopVectorizationLegality::isInductionPhi(const Value *V) const {
1353 Value *In0 = const_cast<Value *>(V);
1354 PHINode *PN = dyn_cast_or_null<PHINode>(Val: In0);
1355 if (!PN)
1356 return false;
1357
1358 return Inductions.count(Key: PN);
1359}
1360
1361bool LoopVectorizationLegality::isCastedInductionVariable(
1362 const Value *V) const {
1363 auto *Inst = dyn_cast<Instruction>(Val: V);
1364 return (Inst && InductionCastsToIgnore.count(Ptr: Inst));
1365}
1366
1367bool LoopVectorizationLegality::isInductionVariable(const Value *V) const {
1368 return isInductionPhi(V) || isCastedInductionVariable(V);
1369}
1370
1371bool LoopVectorizationLegality::isFixedOrderRecurrence(
1372 const PHINode *Phi) const {
1373 return FixedOrderRecurrences.count(Ptr: Phi);
1374}
1375
1376bool LoopVectorizationLegality::blockNeedsPredication(
1377 const BasicBlock *BB) const {
1378 BasicBlock *Latch = TheLoop->getLoopLatch();
1379
1380 // Without a latch, we cannot properly answer blockNeedsPredication,
1381 // return early.
1382 if (!Latch) {
1383 assert(ORE->allowExtraAnalysis(DEBUG_TYPE) &&
1384 !canVectorizeLoopCFG(TheLoop, /*UseVPlanNativePath=*/false) &&
1385 "Loop shape should have been rejected by earlier checks");
1386 return false;
1387 }
1388
1389 // When vectorizing early exits, create predicates for the latch block only.
1390 // For a single early exit, it must be a direct predecessor of the latch.
1391 // For multiple early exits, they form a chain where each exiting block
1392 // dominates all subsequent blocks up to the latch.
1393 if (hasUncountableEarlyExit())
1394 return BB == Latch;
1395 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
1396}
1397
1398bool LoopVectorizationLegality::blockCanBePredicated(
1399 BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs,
1400 SmallPtrSetImpl<const Instruction *> &MaskedOp) const {
1401 for (Instruction &I : *BB) {
1402 // We can predicate blocks with calls to assume, as long as we drop them in
1403 // case we flatten the CFG via predication.
1404 if (match(V: &I, P: m_Intrinsic<Intrinsic::assume>())) {
1405 MaskedOp.insert(Ptr: &I);
1406 continue;
1407 }
1408
1409 // Do not let llvm.experimental.noalias.scope.decl block the vectorization.
1410 // TODO: there might be cases that it should block the vectorization. Let's
1411 // ignore those for now.
1412 if (isa<NoAliasScopeDeclInst>(Val: &I))
1413 continue;
1414
1415 // We can allow masked calls if there's at least one vector variant, even
1416 // if we end up scalarizing due to the cost model calculations.
1417 // TODO: Allow other calls if they have appropriate attributes... readonly
1418 // and argmemonly?
1419 if (CallInst *CI = dyn_cast<CallInst>(Val: &I))
1420 if (VFDatabase::hasMaskedVariant(CI: *CI)) {
1421 MaskedOp.insert(Ptr: CI);
1422 continue;
1423 }
1424
1425 // Loads are handled via masking (or speculated if safe to do so.)
1426 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
1427 if (!SafePtrs.count(Ptr: LI->getPointerOperand()))
1428 MaskedOp.insert(Ptr: LI);
1429 continue;
1430 }
1431
1432 // Predicated store requires some form of masking:
1433 // 1) masked store HW instruction,
1434 // 2) emulation via load-blend-store (only if safe and legal to do so,
1435 // be aware on the race conditions), or
1436 // 3) element-by-element predicate check and scalar store.
1437 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1438 MaskedOp.insert(Ptr: SI);
1439 continue;
1440 }
1441
1442 if (I.mayReadFromMemory() || I.mayWriteToMemory() || I.mayThrow())
1443 return false;
1444 }
1445
1446 return true;
1447}
1448
1449bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
1450 if (!EnableIfConversion) {
1451 reportVectorizationFailure(DebugMsg: "If-conversion is disabled",
1452 ORETag: "IfConversionDisabled", ORE, TheLoop);
1453 return false;
1454 }
1455
1456 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
1457
1458 // A list of pointers which are known to be dereferenceable within scope of
1459 // the loop body for each iteration of the loop which executes. That is,
1460 // the memory pointed to can be dereferenced (with the access size implied by
1461 // the value's type) unconditionally within the loop header without
1462 // introducing a new fault.
1463 SmallPtrSet<Value *, 8> SafePointers;
1464
1465 // Collect safe addresses.
1466 for (BasicBlock *BB : TheLoop->blocks()) {
1467 if (!blockNeedsPredication(BB)) {
1468 for (Instruction &I : *BB)
1469 if (auto *Ptr = getLoadStorePointerOperand(V: &I))
1470 SafePointers.insert(Ptr);
1471 continue;
1472 }
1473
1474 // For a block which requires predication, a address may be safe to access
1475 // in the loop w/o predication if we can prove dereferenceability facts
1476 // sufficient to ensure it'll never fault within the loop. For the moment,
1477 // we restrict this to loads; stores are more complicated due to
1478 // concurrency restrictions.
1479 ScalarEvolution &SE = *PSE.getSE();
1480 SmallVector<const SCEVPredicate *, 4> Predicates;
1481 for (Instruction &I : *BB) {
1482 LoadInst *LI = dyn_cast<LoadInst>(Val: &I);
1483
1484 // Make sure we can execute all computations feeding into Ptr in the loop
1485 // w/o triggering UB and that none of the out-of-loop operands are poison.
1486 // We do not need to check if operations inside the loop can produce
1487 // poison due to flags (e.g. due to an inbounds GEP going out of bounds),
1488 // because flags will be dropped when executing them unconditionally.
1489 // TODO: Results could be improved by considering poison-propagation
1490 // properties of visited ops.
1491 auto CanSpeculatePointerOp = [this](Value *Ptr) {
1492 SmallVector<Value *> Worklist = {Ptr};
1493 SmallPtrSet<Value *, 4> Visited;
1494 while (!Worklist.empty()) {
1495 Value *CurrV = Worklist.pop_back_val();
1496 if (!Visited.insert(Ptr: CurrV).second)
1497 continue;
1498
1499 auto *CurrI = dyn_cast<Instruction>(Val: CurrV);
1500 if (!CurrI || !TheLoop->contains(Inst: CurrI)) {
1501 BasicBlock *LoopPred = TheLoop->getLoopPredecessor();
1502 Instruction *CtxI = LoopPred ? LoopPred->getTerminator() : nullptr;
1503 assert((CtxI || ORE->allowExtraAnalysis(DEBUG_TYPE)) &&
1504 "Loop with multiple predecessors should have been rejected "
1505 "early.");
1506 // If operands from outside the loop may be poison then Ptr may also
1507 // be poison.
1508 if (!isGuaranteedNotToBePoison(V: CurrV, AC, CtxI, DT))
1509 return false;
1510 continue;
1511 }
1512
1513 // A loaded value may be poison, independent of any flags.
1514 if (isa<LoadInst>(Val: CurrI) && !isGuaranteedNotToBePoison(V: CurrV, AC))
1515 return false;
1516
1517 // For other ops, assume poison can only be introduced via flags,
1518 // which can be dropped.
1519 if (!isa<PHINode>(Val: CurrI) && !isSafeToSpeculativelyExecute(I: CurrI))
1520 return false;
1521 append_range(C&: Worklist, R: CurrI->operands());
1522 }
1523 return true;
1524 };
1525 // Pass the Predicates pointer to isDereferenceableAndAlignedInLoop so
1526 // that it will consider loops that need guarding by SCEV checks. The
1527 // vectoriser will generate these checks if we decide to vectorise.
1528 if (LI && !LI->getType()->isVectorTy() && !mustSuppressSpeculation(LI: *LI) &&
1529 CanSpeculatePointerOp(LI->getPointerOperand()) &&
1530 isDereferenceableAndAlignedInLoop(LI, L: TheLoop, SE, DT&: *DT, AC,
1531 Predicates: &Predicates))
1532 SafePointers.insert(Ptr: LI->getPointerOperand());
1533 Predicates.clear();
1534 }
1535 }
1536
1537 // Collect the blocks that need predication.
1538 for (BasicBlock *BB : TheLoop->blocks()) {
1539 // We support only branches and switch statements as terminators inside the
1540 // loop.
1541 if (isa<SwitchInst>(Val: BB->getTerminator())) {
1542 if (TheLoop->isLoopExiting(BB)) {
1543 reportVectorizationFailure(DebugMsg: "Loop contains an unsupported switch",
1544 ORETag: "LoopContainsUnsupportedSwitch", ORE,
1545 TheLoop, I: BB->getTerminator());
1546 return false;
1547 }
1548 } else if (!isa<UncondBrInst, CondBrInst>(Val: BB->getTerminator())) {
1549 reportVectorizationFailure(DebugMsg: "Loop contains an unsupported terminator",
1550 ORETag: "LoopContainsUnsupportedTerminator", ORE,
1551 TheLoop, I: BB->getTerminator());
1552 return false;
1553 }
1554
1555 // We must be able to predicate all blocks that need to be predicated.
1556 if (blockNeedsPredication(BB) &&
1557 !blockCanBePredicated(BB, SafePtrs&: SafePointers, MaskedOp&: ConditionallyExecutedOps)) {
1558 reportVectorizationFailure(
1559 DebugMsg: "Control flow cannot be substituted for a select", ORETag: "NoCFGForSelect",
1560 ORE, TheLoop, I: BB->getTerminator());
1561 return false;
1562 }
1563 }
1564
1565 // We can if-convert this loop.
1566 return true;
1567}
1568
1569// Helper function to canVectorizeLoopNestCFG.
1570bool LoopVectorizationLegality::canVectorizeLoopCFG(
1571 Loop *Lp, bool UseVPlanNativePath) const {
1572 assert((UseVPlanNativePath || Lp->isInnermost()) &&
1573 "VPlan-native path is not enabled.");
1574
1575 // TODO: ORE should be improved to show more accurate information when an
1576 // outer loop can't be vectorized because a nested loop is not understood or
1577 // legal. Something like: "outer_loop_location: loop not vectorized:
1578 // (inner_loop_location) loop control flow is not understood by vectorizer".
1579
1580 // Store the result and return it at the end instead of exiting early, in case
1581 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1582 bool Result = true;
1583 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1584
1585 // We must have a loop in canonical form. Loops with indirectbr in them cannot
1586 // be canonicalized.
1587 if (!Lp->getLoopPreheader()) {
1588 reportVectorizationFailure(
1589 DebugMsg: "Loop doesn't have a legal pre-header",
1590 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
1591 ORE, TheLoop);
1592 if (DoExtraAnalysis)
1593 Result = false;
1594 else
1595 return false;
1596 }
1597
1598 // We must have a single backedge.
1599 if (Lp->getNumBackEdges() != 1) {
1600 reportVectorizationFailure(
1601 DebugMsg: "The loop must have a single backedge",
1602 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
1603 ORE, TheLoop);
1604 if (DoExtraAnalysis)
1605 Result = false;
1606 else
1607 return false;
1608 }
1609
1610 // The latch must be terminated by a branch.
1611 BasicBlock *Latch = Lp->getLoopLatch();
1612 if (Latch && !isa<UncondBrInst, CondBrInst>(Val: Latch->getTerminator())) {
1613 reportVectorizationFailure(
1614 DebugMsg: "The loop latch terminator is not a UncondBrInst/CondBrInst",
1615 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
1616 ORE, TheLoop);
1617 if (DoExtraAnalysis)
1618 Result = false;
1619 else
1620 return false;
1621 }
1622
1623 return Result;
1624}
1625
1626bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1627 Loop *Lp, bool UseVPlanNativePath) {
1628 // Store the result and return it at the end instead of exiting early, in case
1629 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1630 bool Result = true;
1631 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1632 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1633 if (DoExtraAnalysis)
1634 Result = false;
1635 else
1636 return false;
1637 }
1638
1639 // Recursively check whether the loop control flow of nested loops is
1640 // understood.
1641 for (Loop *SubLp : *Lp)
1642 if (!canVectorizeLoopNestCFG(Lp: SubLp, UseVPlanNativePath)) {
1643 if (DoExtraAnalysis)
1644 Result = false;
1645 else
1646 return false;
1647 }
1648
1649 return Result;
1650}
1651
1652bool LoopVectorizationLegality::isVectorizableEarlyExitLoop() {
1653 BasicBlock *LatchBB = TheLoop->getLoopLatch();
1654 if (!LatchBB) {
1655 reportVectorizationFailure(DebugMsg: "Loop does not have a latch",
1656 OREMsg: "Cannot vectorize early exit loop",
1657 ORETag: "NoLatchEarlyExit", ORE, TheLoop);
1658 return false;
1659 }
1660
1661 if (Reductions.size() || FixedOrderRecurrences.size()) {
1662 reportVectorizationFailure(
1663 DebugMsg: "Found reductions or recurrences in early-exit loop",
1664 OREMsg: "Cannot vectorize early exit loop with reductions or recurrences",
1665 ORETag: "RecurrencesInEarlyExitLoop", ORE, TheLoop);
1666 return false;
1667 }
1668
1669 SmallVector<BasicBlock *, 8> ExitingBlocks;
1670 TheLoop->getExitingBlocks(ExitingBlocks);
1671
1672 // Keep a record of all the exiting blocks.
1673 SmallVector<const SCEVPredicate *, 4> Predicates;
1674 SmallVector<BasicBlock *> UncountableExitingBlocks;
1675 for (BasicBlock *BB : ExitingBlocks) {
1676 const SCEV *EC =
1677 PSE.getSE()->getPredicatedExitCount(L: TheLoop, ExitingBlock: BB, Predicates: &Predicates);
1678 if (isa<SCEVCouldNotCompute>(Val: EC)) {
1679 if (size(Range: successors(BB)) != 2) {
1680 reportVectorizationFailure(
1681 DebugMsg: "Early exiting block does not have exactly two successors",
1682 OREMsg: "Incorrect number of successors from early exiting block",
1683 ORETag: "EarlyExitTooManySuccessors", ORE, TheLoop);
1684 return false;
1685 }
1686
1687 UncountableExitingBlocks.push_back(Elt: BB);
1688 } else
1689 CountableExitingBlocks.push_back(Elt: BB);
1690 }
1691 // We can safely ignore the predicates here because when vectorizing the loop
1692 // the PredicatatedScalarEvolution class will keep track of all predicates
1693 // for each exiting block anyway. This happens when calling
1694 // PSE.getSymbolicMaxBackedgeTakenCount() below.
1695 Predicates.clear();
1696
1697 if (UncountableExitingBlocks.empty()) {
1698 LLVM_DEBUG(dbgs() << "LV: Could not find any uncountable exits");
1699 return false;
1700 }
1701
1702 // The latch block must have a countable exit.
1703 if (isa<SCEVCouldNotCompute>(
1704 Val: PSE.getSE()->getPredicatedExitCount(L: TheLoop, ExitingBlock: LatchBB, Predicates: &Predicates))) {
1705 reportVectorizationFailure(
1706 DebugMsg: "Cannot determine exact exit count for latch block",
1707 OREMsg: "Cannot vectorize early exit loop",
1708 ORETag: "UnknownLatchExitCountEarlyExitLoop", ORE, TheLoop);
1709 return false;
1710 }
1711 assert(llvm::is_contained(CountableExitingBlocks, LatchBB) &&
1712 "Latch block not found in list of countable exits!");
1713
1714 // Check to see if there are instructions that could potentially generate
1715 // exceptions or have side-effects.
1716 auto IsSafeOperation = [](Instruction *I) -> bool {
1717 switch (I->getOpcode()) {
1718 case Instruction::Load:
1719 case Instruction::Store:
1720 case Instruction::PHI:
1721 case Instruction::UncondBr:
1722 case Instruction::CondBr:
1723 // These are checked separately.
1724 return true;
1725 default:
1726 return isSafeToSpeculativelyExecute(I);
1727 }
1728 };
1729
1730 bool HasSideEffects = false;
1731 for (auto *BB : TheLoop->blocks())
1732 for (auto &I : *BB) {
1733 if (I.mayWriteToMemory()) {
1734 if (isa<StoreInst>(Val: &I) && cast<StoreInst>(Val: &I)->isSimple()) {
1735 HasSideEffects = true;
1736 continue;
1737 }
1738
1739 // We don't support complex writes to memory.
1740 reportVectorizationFailure(
1741 DebugMsg: "Complex writes to memory unsupported in early exit loops",
1742 OREMsg: "Cannot vectorize early exit loop with complex writes to memory",
1743 ORETag: "WritesInEarlyExitLoop", ORE, TheLoop);
1744 return false;
1745 }
1746
1747 if (!IsSafeOperation(&I)) {
1748 reportVectorizationFailure(DebugMsg: "Early exit loop contains operations that "
1749 "cannot be speculatively executed",
1750 ORETag: "UnsafeOperationsEarlyExitLoop", ORE,
1751 TheLoop);
1752 return false;
1753 }
1754 }
1755
1756 SmallVector<LoadInst *, 4> NonDerefLoads;
1757 // TODO: Handle loops that may fault.
1758 if (!HasSideEffects) {
1759 // Read-only loop.
1760 Predicates.clear();
1761 if (!isReadOnlyLoop(L: TheLoop, SE: PSE.getSE(), DT, AC, NonDereferenceableAndAlignedLoads&: NonDerefLoads,
1762 Predicates: &Predicates)) {
1763 reportVectorizationFailure(
1764 DebugMsg: "Loop may fault", OREMsg: "Cannot vectorize non-read-only early exit loop",
1765 ORETag: "NonReadOnlyEarlyExitLoop", ORE, TheLoop);
1766 return false;
1767 }
1768 } else {
1769 // Check all uncountable exiting blocks for movable loads.
1770 for (BasicBlock *ExitingBB : UncountableExitingBlocks) {
1771 if (!canUncountableExitConditionLoadBeMoved(ExitingBlock: ExitingBB))
1772 return false;
1773 }
1774 }
1775
1776 // Check non-dereferenceable loads if any.
1777 for (LoadInst *LI : NonDerefLoads) {
1778 // Only support unit-stride access for now.
1779 int Stride = isConsecutivePtr(AccessTy: LI->getType(), Ptr: LI->getPointerOperand());
1780 if (Stride != 1) {
1781 reportVectorizationFailure(
1782 DebugMsg: "Loop contains potentially faulting strided load",
1783 OREMsg: "Cannot vectorize early exit loop with "
1784 "strided fault-only-first load",
1785 ORETag: "EarlyExitLoopWithStridedFaultOnlyFirstLoad", ORE, TheLoop);
1786 return false;
1787 }
1788 }
1789
1790 [[maybe_unused]] const SCEV *SymbolicMaxBTC =
1791 PSE.getSymbolicMaxBackedgeTakenCount();
1792 // Since we have an exact exit count for the latch and the early exit
1793 // dominates the latch, then this should guarantee a computed SCEV value.
1794 assert(!isa<SCEVCouldNotCompute>(SymbolicMaxBTC) &&
1795 "Failed to get symbolic expression for backedge taken count");
1796 LLVM_DEBUG(dbgs() << "LV: Found an early exit loop with symbolic max "
1797 "backedge taken count: "
1798 << *SymbolicMaxBTC << '\n');
1799 UncountableExitType = HasSideEffects ? UncountableExitTrait::ReadWrite
1800 : UncountableExitTrait::ReadOnly;
1801 return true;
1802}
1803
1804bool LoopVectorizationLegality::canUncountableExitConditionLoadBeMoved(
1805 BasicBlock *ExitingBlock) {
1806 // Try to find a load in the critical path for the uncountable exit condition.
1807 // This is currently matching about the simplest form we can, expecting
1808 // only one in-loop load, the result of which is directly compared against
1809 // a loop-invariant value.
1810 // FIXME: We're insisting on a single use for now, because otherwise we will
1811 // need to make PHI nodes for other users. That can be done once the initial
1812 // transform code lands.
1813 auto *Br = cast<CondBrInst>(Val: ExitingBlock->getTerminator());
1814
1815 using namespace llvm::PatternMatch;
1816 Instruction *L = nullptr;
1817 Value *Ptr = nullptr;
1818 Value *R = nullptr;
1819 // The exit-condition load can appear on either side of the icmp.
1820 if (!match(V: Br->getCondition(),
1821 P: m_OneUse(SubPattern: m_c_ICmp(L: m_OneUse(SubPattern: m_Instruction(I&: L, P: m_Load(Op: m_Value(V&: Ptr)))),
1822 R: m_Value(V&: R))))) {
1823 reportVectorizationFailure(
1824 DebugMsg: "Early exit loop with store but no supported condition load",
1825 ORETag: "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1826 return false;
1827 }
1828
1829 if (!TheLoop->isLoopInvariant(V: R)) {
1830 reportVectorizationFailure(
1831 DebugMsg: "Early exit loop with store but no supported condition load",
1832 ORETag: "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1833 return false;
1834 }
1835
1836 // Make sure that the load address is not loop invariant; we want an
1837 // address calculation that we can rotate to the next vector iteration.
1838 const auto *AR = dyn_cast<SCEVAddRecExpr>(Val: PSE.getSE()->getSCEV(V: Ptr));
1839 if (!AR || AR->getLoop() != TheLoop || !AR->isAffine()) {
1840 reportVectorizationFailure(
1841 DebugMsg: "Uncountable exit condition depends on load with an address that is "
1842 "not an add recurrence in the loop",
1843 ORETag: "EarlyExitLoadInvariantAddress", ORE, TheLoop);
1844 return false;
1845 }
1846
1847 ICFLoopSafetyInfo SafetyInfo;
1848 SafetyInfo.computeLoopSafetyInfo(CurLoop: TheLoop);
1849 LoadInst *Load = cast<LoadInst>(Val: L);
1850 // We need to know that load will be executed before we can hoist a
1851 // copy out to run just before the first iteration.
1852 if (!SafetyInfo.isGuaranteedToExecute(Inst: *Load, DT, CurLoop: TheLoop)) {
1853 reportVectorizationFailure(
1854 DebugMsg: "Load for uncountable exit not guaranteed to execute",
1855 ORETag: "ConditionalUncountableExitLoad", ORE, TheLoop);
1856 return false;
1857 }
1858
1859 // Prohibit any potential aliasing with any instruction in the loop which
1860 // might store to memory.
1861 // FIXME: Relax this constraint where possible.
1862 for (auto *BB : TheLoop->blocks()) {
1863 for (auto &I : *BB) {
1864 if (&I == Load)
1865 continue;
1866
1867 if (I.mayReadOrWriteMemory()) {
1868 // We need to mask all other memory ops.
1869 ConditionallyExecutedOps.insert(Ptr: &I);
1870 if (isa<LoadInst>(Val: &I))
1871 continue;
1872 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1873 AliasResult AR = AA->alias(V1: Ptr, V2: SI->getPointerOperand());
1874 if (AR == AliasResult::NoAlias)
1875 continue;
1876 }
1877
1878 reportVectorizationFailure(
1879 DebugMsg: "Cannot determine whether critical uncountable exit load address "
1880 "does not alias with a memory write",
1881 ORETag: "CantVectorizeAliasWithCriticalUncountableExitLoad", ORE, TheLoop);
1882 return false;
1883 }
1884 }
1885 }
1886
1887 return true;
1888}
1889
1890bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
1891 // Store the result and return it at the end instead of exiting early, in case
1892 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1893 bool Result = true;
1894
1895 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1896 // Check whether the loop-related control flow in the loop nest is expected by
1897 // vectorizer.
1898 if (!canVectorizeLoopNestCFG(Lp: TheLoop, UseVPlanNativePath)) {
1899 if (DoExtraAnalysis) {
1900 LLVM_DEBUG(dbgs() << "LV: legality check failed: loop nest");
1901 Result = false;
1902 } else {
1903 return false;
1904 }
1905 }
1906
1907 // We need to have a loop header.
1908 LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
1909 << '\n');
1910
1911 // Specific checks for outer loops. We skip the remaining legal checks at this
1912 // point because they don't support outer loops.
1913 if (!TheLoop->isInnermost()) {
1914 assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
1915
1916 if (!canVectorizeOuterLoop()) {
1917 reportVectorizationFailure(DebugMsg: "Unsupported outer loop",
1918 ORETag: "UnsupportedOuterLoop", ORE, TheLoop);
1919 // TODO: Implement DoExtraAnalysis when subsequent legal checks support
1920 // outer loops.
1921 return false;
1922 }
1923
1924 LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
1925 return Result;
1926 }
1927
1928 assert(TheLoop->isInnermost() && "Inner loop expected.");
1929 // Check if we can if-convert non-single-bb loops.
1930 unsigned NumBlocks = TheLoop->getNumBlocks();
1931 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
1932 LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
1933 if (DoExtraAnalysis)
1934 Result = false;
1935 else
1936 return false;
1937 }
1938
1939 // Check if we can vectorize the instructions and CFG in this loop.
1940 if (!canVectorizeInstrs()) {
1941 LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
1942 if (DoExtraAnalysis)
1943 Result = false;
1944 else
1945 return false;
1946 }
1947
1948 if (isa<SCEVCouldNotCompute>(Val: PSE.getBackedgeTakenCount())) {
1949 if (TheLoop->getExitingBlock()) {
1950 reportVectorizationFailure(DebugMsg: "Cannot vectorize uncountable loop",
1951 ORETag: "UnsupportedUncountableLoop", ORE, TheLoop);
1952 if (DoExtraAnalysis)
1953 Result = false;
1954 else
1955 return false;
1956 } else {
1957 if (!isVectorizableEarlyExitLoop()) {
1958 assert(UncountableExitType == UncountableExitTrait::None &&
1959 "Must be false without vectorizable early-exit loop");
1960 if (DoExtraAnalysis)
1961 Result = false;
1962 else
1963 return false;
1964 }
1965 }
1966 }
1967
1968 // Go over each instruction and look at memory deps.
1969 if (!canVectorizeMemory()) {
1970 LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
1971 if (DoExtraAnalysis)
1972 Result = false;
1973 else
1974 return false;
1975 }
1976
1977 // TODO: Remove this restriction, should be straightforward to support.
1978 if (UncountableExitType != UncountableExitTrait::None &&
1979 !LAI->getStoresToInvariantAddresses().empty()) {
1980 LLVM_DEBUG(dbgs() << "LV: Cannot vectorize early exit loops with stores to "
1981 "loop-invariant addresses\n");
1982 reportVectorizationFailure(DebugMsg: "Cannot vectorize early exit loops with stores "
1983 "to loop-invariant addresses",
1984 ORETag: "LoopInvariantStoresInEELoop", ORE, TheLoop);
1985 return false;
1986 }
1987
1988 if (Result) {
1989 LLVM_DEBUG(dbgs() << "LV: We can vectorize this loop"
1990 << (LAI->getRuntimePointerChecking()->Need
1991 ? " (with a runtime bound check)"
1992 : "")
1993 << "!\n");
1994 }
1995
1996 // Okay! We've done all the tests. If any have failed, return false. Otherwise
1997 // we can vectorize, and at this point we don't have any other mem analysis
1998 // which may limit our maximum vectorization factor, so just return true with
1999 // no restrictions.
2000 return Result;
2001}
2002
2003bool LoopVectorizationLegality::canFoldTailByMasking() const {
2004 // The only loops we can vectorize without a scalar epilogue, are loops with
2005 // a bottom-test and a single exiting block. We'd have to handle the fact
2006 // that not every instruction executes on the last iteration. This will
2007 // require a lane mask which varies through the vector loop body. (TODO)
2008 if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
2009 LLVM_DEBUG(
2010 dbgs()
2011 << "LV: Cannot fold tail by masking. Requires a singe latch exit\n");
2012 return false;
2013 }
2014
2015 LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n");
2016
2017 // The list of pointers that we can safely read and write to remains empty.
2018 SmallPtrSet<Value *, 8> SafePointers;
2019
2020 // Check all blocks for predication, including those that ordinarily do not
2021 // need predication such as the header block.
2022 SmallPtrSet<const Instruction *, 8> TmpMaskedOp;
2023 for (BasicBlock *BB : TheLoop->blocks()) {
2024 if (!blockCanBePredicated(BB, SafePtrs&: SafePointers, MaskedOp&: TmpMaskedOp)) {
2025 LLVM_DEBUG(dbgs() << "LV: Cannot fold tail by masking.\n");
2026 return false;
2027 }
2028 }
2029
2030 LLVM_DEBUG(dbgs() << "LV: can fold tail by masking.\n");
2031
2032 return true;
2033}
2034
2035void LoopVectorizationLegality::prepareToFoldTailByMasking() {
2036 // The list of pointers that we can safely read and write to remains empty.
2037 SmallPtrSet<Value *, 8> SafePointers;
2038
2039 // Mark all blocks for predication, including those that ordinarily do not
2040 // need predication such as the header block, and collect instructions needing
2041 // predication in TailFoldedMaskedOp.
2042 for (BasicBlock *BB : TheLoop->blocks()) {
2043 [[maybe_unused]] bool R =
2044 blockCanBePredicated(BB, SafePtrs&: SafePointers, MaskedOp&: TailFoldedMaskedOp);
2045 assert(R && "Must be able to predicate block when tail-folding.");
2046 }
2047}
2048
2049} // namespace llvm
2050