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