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