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 "llvm/Analysis/Loads.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 21 #include "llvm/Analysis/TargetLibraryInfo.h" 22 #include "llvm/Analysis/TargetTransformInfo.h" 23 #include "llvm/Analysis/ValueTracking.h" 24 #include "llvm/Analysis/VectorUtils.h" 25 #include "llvm/IR/IntrinsicInst.h" 26 #include "llvm/IR/PatternMatch.h" 27 #include "llvm/Transforms/Utils/SizeOpts.h" 28 #include "llvm/Transforms/Vectorize/LoopVectorize.h" 29 30 using namespace llvm; 31 using namespace PatternMatch; 32 33 #define LV_NAME "loop-vectorize" 34 #define DEBUG_TYPE LV_NAME 35 36 static cl::opt<bool> 37 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden, 38 cl::desc("Enable if-conversion during vectorization.")); 39 40 static cl::opt<bool> 41 AllowStridedPointerIVs("lv-strided-pointer-ivs", cl::init(false), cl::Hidden, 42 cl::desc("Enable recognition of non-constant strided " 43 "pointer induction variables.")); 44 45 namespace llvm { 46 cl::opt<bool> 47 HintsAllowReordering("hints-allow-reordering", cl::init(true), cl::Hidden, 48 cl::desc("Allow enabling loop hints to reorder " 49 "FP operations during vectorization.")); 50 } 51 52 // TODO: Move size-based thresholds out of legality checking, make cost based 53 // decisions instead of hard thresholds. 54 static cl::opt<unsigned> VectorizeSCEVCheckThreshold( 55 "vectorize-scev-check-threshold", cl::init(16), cl::Hidden, 56 cl::desc("The maximum number of SCEV checks allowed.")); 57 58 static cl::opt<unsigned> PragmaVectorizeSCEVCheckThreshold( 59 "pragma-vectorize-scev-check-threshold", cl::init(128), cl::Hidden, 60 cl::desc("The maximum number of SCEV checks allowed with a " 61 "vectorize(enable) pragma")); 62 63 static cl::opt<LoopVectorizeHints::ScalableForceKind> 64 ForceScalableVectorization( 65 "scalable-vectorization", cl::init(LoopVectorizeHints::SK_Unspecified), 66 cl::Hidden, 67 cl::desc("Control whether the compiler can use scalable vectors to " 68 "vectorize a loop"), 69 cl::values( 70 clEnumValN(LoopVectorizeHints::SK_FixedWidthOnly, "off", 71 "Scalable vectorization is disabled."), 72 clEnumValN( 73 LoopVectorizeHints::SK_PreferScalable, "preferred", 74 "Scalable vectorization is available and favored when the " 75 "cost is inconclusive."), 76 clEnumValN( 77 LoopVectorizeHints::SK_PreferScalable, "on", 78 "Scalable vectorization is available and favored when the " 79 "cost is inconclusive."))); 80 81 /// Maximum vectorization interleave count. 82 static const unsigned MaxInterleaveFactor = 16; 83 84 namespace llvm { 85 86 bool LoopVectorizeHints::Hint::validate(unsigned Val) { 87 switch (Kind) { 88 case HK_WIDTH: 89 return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth; 90 case HK_INTERLEAVE: 91 return isPowerOf2_32(Val) && Val <= MaxInterleaveFactor; 92 case HK_FORCE: 93 return (Val <= 1); 94 case HK_ISVECTORIZED: 95 case HK_PREDICATE: 96 case HK_SCALABLE: 97 return (Val == 0 || Val == 1); 98 } 99 return false; 100 } 101 102 LoopVectorizeHints::LoopVectorizeHints(const Loop *L, 103 bool InterleaveOnlyWhenForced, 104 OptimizationRemarkEmitter &ORE, 105 const TargetTransformInfo *TTI) 106 : Width("vectorize.width", VectorizerParams::VectorizationFactor, HK_WIDTH), 107 Interleave("interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE), 108 Force("vectorize.enable", FK_Undefined, HK_FORCE), 109 IsVectorized("isvectorized", 0, HK_ISVECTORIZED), 110 Predicate("vectorize.predicate.enable", FK_Undefined, HK_PREDICATE), 111 Scalable("vectorize.scalable.enable", SK_Unspecified, HK_SCALABLE), 112 TheLoop(L), ORE(ORE) { 113 // Populate values with existing loop metadata. 114 getHintsFromMetadata(); 115 116 // force-vector-interleave overrides DisableInterleaving. 117 if (VectorizerParams::isInterleaveForced()) 118 Interleave.Value = VectorizerParams::VectorizationInterleave; 119 120 // If the metadata doesn't explicitly specify whether to enable scalable 121 // vectorization, then decide based on the following criteria (increasing 122 // level of priority): 123 // - Target default 124 // - Metadata width 125 // - Force option (always overrides) 126 if ((LoopVectorizeHints::ScalableForceKind)Scalable.Value == SK_Unspecified) { 127 if (TTI) 128 Scalable.Value = TTI->enableScalableVectorization() ? SK_PreferScalable 129 : SK_FixedWidthOnly; 130 131 if (Width.Value) 132 // If the width is set, but the metadata says nothing about the scalable 133 // property, then assume it concerns only a fixed-width UserVF. 134 // If width is not set, the flag takes precedence. 135 Scalable.Value = SK_FixedWidthOnly; 136 } 137 138 // If the flag is set to force any use of scalable vectors, override the loop 139 // hints. 140 if (ForceScalableVectorization.getValue() != 141 LoopVectorizeHints::SK_Unspecified) 142 Scalable.Value = ForceScalableVectorization.getValue(); 143 144 // Scalable vectorization is disabled if no preference is specified. 145 if ((LoopVectorizeHints::ScalableForceKind)Scalable.Value == SK_Unspecified) 146 Scalable.Value = 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(1) && getInterleave() == 1; 154 LLVM_DEBUG(if (InterleaveOnlyWhenForced && getInterleave() == 1) dbgs() 155 << "LV: Interleaving disabled by the pass manager\n"); 156 } 157 158 void LoopVectorizeHints::setAlreadyVectorized() { 159 LLVMContext &Context = TheLoop->getHeader()->getContext(); 160 161 MDNode *IsVectorizedMD = MDNode::get( 162 Context, 163 {MDString::get(Context, "llvm.loop.isvectorized"), 164 ConstantAsMetadata::get(ConstantInt::get(Context, APInt(32, 1)))}); 165 MDNode *LoopID = TheLoop->getLoopID(); 166 MDNode *NewLoopID = 167 makePostTransformationMetadata(Context, LoopID, 168 {Twine(Prefix(), "vectorize.").str(), 169 Twine(Prefix(), "interleave.").str()}, 170 {IsVectorizedMD}); 171 TheLoop->setLoopID(NewLoopID); 172 173 // Update internal cache. 174 IsVectorized.Value = 1; 175 } 176 177 bool LoopVectorizeHints::allowVectorization( 178 Function *F, Loop *L, bool VectorizeOnlyWhenForced) const { 179 if (getForce() == LoopVectorizeHints::FK_Disabled) { 180 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n"); 181 emitRemarkWithHints(); 182 return false; 183 } 184 185 if (VectorizeOnlyWhenForced && getForce() != LoopVectorizeHints::FK_Enabled) { 186 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n"); 187 emitRemarkWithHints(); 188 return false; 189 } 190 191 if (getIsVectorized() == 1) { 192 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n"); 193 // FIXME: Add interleave.disable metadata. This will allow 194 // vectorize.disable to be used without disabling the pass and errors 195 // to differentiate between disabled vectorization and a width of 1. 196 ORE.emit([&]() { 197 return OptimizationRemarkAnalysis(vectorizeAnalysisPassName(), 198 "AllDisabled", L->getStartLoc(), 199 L->getHeader()) 200 << "loop not vectorized: vectorization and interleaving are " 201 "explicitly disabled, or the loop has already been " 202 "vectorized"; 203 }); 204 return false; 205 } 206 207 return true; 208 } 209 210 void LoopVectorizeHints::emitRemarkWithHints() const { 211 using namespace ore; 212 213 ORE.emit([&]() { 214 if (Force.Value == LoopVectorizeHints::FK_Disabled) 215 return OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled", 216 TheLoop->getStartLoc(), 217 TheLoop->getHeader()) 218 << "loop not vectorized: vectorization is explicitly disabled"; 219 else { 220 OptimizationRemarkMissed R(LV_NAME, "MissedDetails", 221 TheLoop->getStartLoc(), TheLoop->getHeader()); 222 R << "loop not vectorized"; 223 if (Force.Value == LoopVectorizeHints::FK_Enabled) { 224 R << " (Force=" << NV("Force", true); 225 if (Width.Value != 0) 226 R << ", Vector Width=" << NV("VectorWidth", getWidth()); 227 if (getInterleave() != 0) 228 R << ", Interleave Count=" << NV("InterleaveCount", getInterleave()); 229 R << ")"; 230 } 231 return R; 232 } 233 }); 234 } 235 236 const char *LoopVectorizeHints::vectorizeAnalysisPassName() const { 237 if (getWidth() == ElementCount::getFixed(1)) 238 return LV_NAME; 239 if (getForce() == LoopVectorizeHints::FK_Disabled) 240 return LV_NAME; 241 if (getForce() == LoopVectorizeHints::FK_Undefined && getWidth().isZero()) 242 return LV_NAME; 243 return OptimizationRemarkAnalysis::AlwaysPrint; 244 } 245 246 bool LoopVectorizeHints::allowReordering() const { 247 // Allow the vectorizer to change the order of operations if enabling 248 // loop hints are provided 249 ElementCount EC = getWidth(); 250 return HintsAllowReordering && 251 (getForce() == LoopVectorizeHints::FK_Enabled || 252 EC.getKnownMinValue() > 1); 253 } 254 255 void LoopVectorizeHints::getHintsFromMetadata() { 256 MDNode *LoopID = TheLoop->getLoopID(); 257 if (!LoopID) 258 return; 259 260 // First operand should refer to the loop id itself. 261 assert(LoopID->getNumOperands() > 0 && "requires at least one operand"); 262 assert(LoopID->getOperand(0) == LoopID && "invalid loop id"); 263 264 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { 265 const MDString *S = nullptr; 266 SmallVector<Metadata *, 4> Args; 267 268 // The expected hint is either a MDString or a MDNode with the first 269 // operand a MDString. 270 if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) { 271 if (!MD || MD->getNumOperands() == 0) 272 continue; 273 S = dyn_cast<MDString>(MD->getOperand(0)); 274 for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i) 275 Args.push_back(MD->getOperand(i)); 276 } else { 277 S = dyn_cast<MDString>(LoopID->getOperand(i)); 278 assert(Args.size() == 0 && "too many arguments for MDString"); 279 } 280 281 if (!S) 282 continue; 283 284 // Check if the hint starts with the loop metadata prefix. 285 StringRef Name = S->getString(); 286 if (Args.size() == 1) 287 setHint(Name, Args[0]); 288 } 289 } 290 291 void LoopVectorizeHints::setHint(StringRef Name, Metadata *Arg) { 292 if (!Name.startswith(Prefix())) 293 return; 294 Name = Name.substr(Prefix().size(), StringRef::npos); 295 296 const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(Arg); 297 if (!C) 298 return; 299 unsigned Val = C->getZExtValue(); 300 301 Hint *Hints[] = {&Width, &Interleave, &Force, 302 &IsVectorized, &Predicate, &Scalable}; 303 for (auto *H : Hints) { 304 if (Name == H->Name) { 305 if (H->validate(Val)) 306 H->Value = Val; 307 else 308 LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n"); 309 break; 310 } 311 } 312 } 313 314 // Return true if the inner loop \p Lp is uniform with regard to the outer loop 315 // \p OuterLp (i.e., if the outer loop is vectorized, all the vector lanes 316 // executing the inner loop will execute the same iterations). This check is 317 // very constrained for now but it will be relaxed in the future. \p Lp is 318 // considered uniform if it meets all the following conditions: 319 // 1) it has a canonical IV (starting from 0 and with stride 1), 320 // 2) its latch terminator is a conditional branch and, 321 // 3) its latch condition is a compare instruction whose operands are the 322 // canonical IV and an OuterLp invariant. 323 // This check doesn't take into account the uniformity of other conditions not 324 // related to the loop latch because they don't affect the loop uniformity. 325 // 326 // NOTE: We decided to keep all these checks and its associated documentation 327 // together so that we can easily have a picture of the current supported loop 328 // nests. However, some of the current checks don't depend on \p OuterLp and 329 // would be redundantly executed for each \p Lp if we invoked this function for 330 // different candidate outer loops. This is not the case for now because we 331 // don't currently have the infrastructure to evaluate multiple candidate outer 332 // loops and \p OuterLp will be a fixed parameter while we only support explicit 333 // outer loop vectorization. It's also very likely that these checks go away 334 // before introducing the aforementioned infrastructure. However, if this is not 335 // the case, we should move the \p OuterLp independent checks to a separate 336 // function that is only executed once for each \p Lp. 337 static bool isUniformLoop(Loop *Lp, Loop *OuterLp) { 338 assert(Lp->getLoopLatch() && "Expected loop with a single latch."); 339 340 // If Lp is the outer loop, it's uniform by definition. 341 if (Lp == OuterLp) 342 return true; 343 assert(OuterLp->contains(Lp) && "OuterLp must contain Lp."); 344 345 // 1. 346 PHINode *IV = Lp->getCanonicalInductionVariable(); 347 if (!IV) { 348 LLVM_DEBUG(dbgs() << "LV: Canonical IV not found.\n"); 349 return false; 350 } 351 352 // 2. 353 BasicBlock *Latch = Lp->getLoopLatch(); 354 auto *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator()); 355 if (!LatchBr || LatchBr->isUnconditional()) { 356 LLVM_DEBUG(dbgs() << "LV: Unsupported loop latch branch.\n"); 357 return false; 358 } 359 360 // 3. 361 auto *LatchCmp = dyn_cast<CmpInst>(LatchBr->getCondition()); 362 if (!LatchCmp) { 363 LLVM_DEBUG( 364 dbgs() << "LV: Loop latch condition is not a compare instruction.\n"); 365 return false; 366 } 367 368 Value *CondOp0 = LatchCmp->getOperand(0); 369 Value *CondOp1 = LatchCmp->getOperand(1); 370 Value *IVUpdate = IV->getIncomingValueForBlock(Latch); 371 if (!(CondOp0 == IVUpdate && OuterLp->isLoopInvariant(CondOp1)) && 372 !(CondOp1 == IVUpdate && OuterLp->isLoopInvariant(CondOp0))) { 373 LLVM_DEBUG(dbgs() << "LV: Loop latch condition is not uniform.\n"); 374 return false; 375 } 376 377 return true; 378 } 379 380 // Return true if \p Lp and all its nested loops are uniform with regard to \p 381 // OuterLp. 382 static bool isUniformLoopNest(Loop *Lp, Loop *OuterLp) { 383 if (!isUniformLoop(Lp, OuterLp)) 384 return false; 385 386 // Check if nested loops are uniform. 387 for (Loop *SubLp : *Lp) 388 if (!isUniformLoopNest(SubLp, OuterLp)) 389 return false; 390 391 return true; 392 } 393 394 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) { 395 if (Ty->isPointerTy()) 396 return DL.getIntPtrType(Ty); 397 398 // It is possible that char's or short's overflow when we ask for the loop's 399 // trip count, work around this by changing the type size. 400 if (Ty->getScalarSizeInBits() < 32) 401 return Type::getInt32Ty(Ty->getContext()); 402 403 return Ty; 404 } 405 406 static Type *getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) { 407 Ty0 = convertPointerToIntegerType(DL, Ty0); 408 Ty1 = convertPointerToIntegerType(DL, Ty1); 409 if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits()) 410 return Ty0; 411 return Ty1; 412 } 413 414 /// Check that the instruction has outside loop users and is not an 415 /// identified reduction variable. 416 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst, 417 SmallPtrSetImpl<Value *> &AllowedExit) { 418 // Reductions, Inductions and non-header phis are allowed to have exit users. All 419 // other instructions must not have external users. 420 if (!AllowedExit.count(Inst)) 421 // Check that all of the users of the loop are inside the BB. 422 for (User *U : Inst->users()) { 423 Instruction *UI = cast<Instruction>(U); 424 // This user may be a reduction exit value. 425 if (!TheLoop->contains(UI)) { 426 LLVM_DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n'); 427 return true; 428 } 429 } 430 return false; 431 } 432 433 /// Returns true if A and B have same pointer operands or same SCEVs addresses 434 static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A, 435 StoreInst *B) { 436 // Compare store 437 if (A == B) 438 return true; 439 440 // Otherwise Compare pointers 441 Value *APtr = A->getPointerOperand(); 442 Value *BPtr = B->getPointerOperand(); 443 if (APtr == BPtr) 444 return true; 445 446 // Otherwise compare address SCEVs 447 if (SE->getSCEV(APtr) == SE->getSCEV(BPtr)) 448 return true; 449 450 return false; 451 } 452 453 int LoopVectorizationLegality::isConsecutivePtr(Type *AccessTy, 454 Value *Ptr) const { 455 // FIXME: Currently, the set of symbolic strides is sometimes queried before 456 // it's collected. This happens from canVectorizeWithIfConvert, when the 457 // pointer is checked to reference consecutive elements suitable for a 458 // masked access. 459 const auto &Strides = 460 LAI ? LAI->getSymbolicStrides() : DenseMap<Value *, const SCEV *>(); 461 462 Function *F = TheLoop->getHeader()->getParent(); 463 bool OptForSize = F->hasOptSize() || 464 llvm::shouldOptimizeForSize(TheLoop->getHeader(), PSI, BFI, 465 PGSOQueryType::IRPass); 466 bool CanAddPredicate = !OptForSize; 467 int Stride = getPtrStride(PSE, AccessTy, Ptr, TheLoop, Strides, 468 CanAddPredicate, false).value_or(0); 469 if (Stride == 1 || Stride == -1) 470 return Stride; 471 return 0; 472 } 473 474 bool LoopVectorizationLegality::isInvariant(Value *V) const { 475 return LAI->isInvariant(V); 476 } 477 478 namespace { 479 /// A rewriter to build the SCEVs for each of the VF lanes in the expected 480 /// vectorized loop, which can then be compared to detect their uniformity. This 481 /// is done by replacing the AddRec SCEVs of the original scalar loop (TheLoop) 482 /// with new AddRecs where the step is multiplied by StepMultiplier and Offset * 483 /// Step is added. Also checks if all sub-expressions are analyzable w.r.t. 484 /// uniformity. 485 class SCEVAddRecForUniformityRewriter 486 : public SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter> { 487 /// Multiplier to be applied to the step of AddRecs in TheLoop. 488 unsigned StepMultiplier; 489 490 /// Offset to be added to the AddRecs in TheLoop. 491 unsigned Offset; 492 493 /// Loop for which to rewrite AddRecsFor. 494 Loop *TheLoop; 495 496 /// Is any sub-expressions not analyzable w.r.t. uniformity? 497 bool CannotAnalyze = false; 498 499 bool canAnalyze() const { return !CannotAnalyze; } 500 501 public: 502 SCEVAddRecForUniformityRewriter(ScalarEvolution &SE, unsigned StepMultiplier, 503 unsigned Offset, Loop *TheLoop) 504 : SCEVRewriteVisitor(SE), StepMultiplier(StepMultiplier), Offset(Offset), 505 TheLoop(TheLoop) {} 506 507 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 508 assert(Expr->getLoop() == TheLoop && 509 "addrec outside of TheLoop must be invariant and should have been " 510 "handled earlier"); 511 // Build a new AddRec by multiplying the step by StepMultiplier and 512 // incrementing the start by Offset * step. 513 Type *Ty = Expr->getType(); 514 auto *Step = Expr->getStepRecurrence(SE); 515 if (!SE.isLoopInvariant(Step, TheLoop)) { 516 CannotAnalyze = true; 517 return Expr; 518 } 519 auto *NewStep = SE.getMulExpr(Step, SE.getConstant(Ty, StepMultiplier)); 520 auto *ScaledOffset = SE.getMulExpr(Step, SE.getConstant(Ty, Offset)); 521 auto *NewStart = SE.getAddExpr(Expr->getStart(), ScaledOffset); 522 return SE.getAddRecExpr(NewStart, NewStep, TheLoop, SCEV::FlagAnyWrap); 523 } 524 525 const SCEV *visit(const SCEV *S) { 526 if (CannotAnalyze || SE.isLoopInvariant(S, TheLoop)) 527 return S; 528 return SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter>::visit(S); 529 } 530 531 const SCEV *visitUnknown(const SCEVUnknown *S) { 532 if (SE.isLoopInvariant(S, TheLoop)) 533 return S; 534 // The value could vary across iterations. 535 CannotAnalyze = true; 536 return S; 537 } 538 539 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *S) { 540 // Could not analyze the expression. 541 CannotAnalyze = true; 542 return S; 543 } 544 545 static const SCEV *rewrite(const SCEV *S, ScalarEvolution &SE, 546 unsigned StepMultiplier, unsigned Offset, 547 Loop *TheLoop) { 548 /// Bail out if the expression does not contain an UDiv expression. 549 /// Uniform values which are not loop invariant require operations to strip 550 /// out the lowest bits. For now just look for UDivs and use it to avoid 551 /// re-writing UDIV-free expressions for other lanes to limit compile time. 552 if (!SCEVExprContains(S, 553 [](const SCEV *S) { return isa<SCEVUDivExpr>(S); })) 554 return SE.getCouldNotCompute(); 555 556 SCEVAddRecForUniformityRewriter Rewriter(SE, StepMultiplier, Offset, 557 TheLoop); 558 const SCEV *Result = Rewriter.visit(S); 559 560 if (Rewriter.canAnalyze()) 561 return Result; 562 return SE.getCouldNotCompute(); 563 } 564 }; 565 566 } // namespace 567 568 bool LoopVectorizationLegality::isUniform(Value *V, ElementCount VF) const { 569 if (isInvariant(V)) 570 return true; 571 if (VF.isScalable()) 572 return false; 573 if (VF.isScalar()) 574 return true; 575 576 // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is 577 // never considered uniform. 578 auto *SE = PSE.getSE(); 579 if (!SE->isSCEVable(V->getType())) 580 return false; 581 const SCEV *S = SE->getSCEV(V); 582 583 // Rewrite AddRecs in TheLoop to step by VF and check if the expression for 584 // lane 0 matches the expressions for all other lanes. 585 unsigned FixedVF = VF.getKnownMinValue(); 586 const SCEV *FirstLaneExpr = 587 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF, 0, TheLoop); 588 if (isa<SCEVCouldNotCompute>(FirstLaneExpr)) 589 return false; 590 591 // Make sure the expressions for lanes FixedVF-1..1 match the expression for 592 // lane 0. We check lanes in reverse order for compile-time, as frequently 593 // checking the last lane is sufficient to rule out uniformity. 594 return all_of(reverse(seq<unsigned>(1, FixedVF)), [&](unsigned I) { 595 const SCEV *IthLaneExpr = 596 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF, I, TheLoop); 597 return FirstLaneExpr == IthLaneExpr; 598 }); 599 } 600 601 bool LoopVectorizationLegality::isUniformMemOp(Instruction &I, 602 ElementCount VF) const { 603 Value *Ptr = getLoadStorePointerOperand(&I); 604 if (!Ptr) 605 return false; 606 // Note: There's nothing inherent which prevents predicated loads and 607 // stores from being uniform. The current lowering simply doesn't handle 608 // it; in particular, the cost model distinguishes scatter/gather from 609 // scalar w/predication, and we currently rely on the scalar path. 610 return isUniform(Ptr, VF) && !blockNeedsPredication(I.getParent()); 611 } 612 613 bool LoopVectorizationLegality::canVectorizeOuterLoop() { 614 assert(!TheLoop->isInnermost() && "We are not vectorizing an outer loop."); 615 // Store the result and return it at the end instead of exiting early, in case 616 // allowExtraAnalysis is used to report multiple reasons for not vectorizing. 617 bool Result = true; 618 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE); 619 620 for (BasicBlock *BB : TheLoop->blocks()) { 621 // Check whether the BB terminator is a BranchInst. Any other terminator is 622 // not supported yet. 623 auto *Br = dyn_cast<BranchInst>(BB->getTerminator()); 624 if (!Br) { 625 reportVectorizationFailure("Unsupported basic block terminator", 626 "loop control flow is not understood by vectorizer", 627 "CFGNotUnderstood", ORE, TheLoop); 628 if (DoExtraAnalysis) 629 Result = false; 630 else 631 return false; 632 } 633 634 // Check whether the BranchInst is a supported one. Only unconditional 635 // branches, conditional branches with an outer loop invariant condition or 636 // backedges are supported. 637 // FIXME: We skip these checks when VPlan predication is enabled as we 638 // want to allow divergent branches. This whole check will be removed 639 // once VPlan predication is on by default. 640 if (Br && Br->isConditional() && 641 !TheLoop->isLoopInvariant(Br->getCondition()) && 642 !LI->isLoopHeader(Br->getSuccessor(0)) && 643 !LI->isLoopHeader(Br->getSuccessor(1))) { 644 reportVectorizationFailure("Unsupported conditional branch", 645 "loop control flow is not understood by vectorizer", 646 "CFGNotUnderstood", ORE, TheLoop); 647 if (DoExtraAnalysis) 648 Result = false; 649 else 650 return false; 651 } 652 } 653 654 // Check whether inner loops are uniform. At this point, we only support 655 // simple outer loops scenarios with uniform nested loops. 656 if (!isUniformLoopNest(TheLoop /*loop nest*/, 657 TheLoop /*context outer loop*/)) { 658 reportVectorizationFailure("Outer loop contains divergent loops", 659 "loop control flow is not understood by vectorizer", 660 "CFGNotUnderstood", ORE, TheLoop); 661 if (DoExtraAnalysis) 662 Result = false; 663 else 664 return false; 665 } 666 667 // Check whether we are able to set up outer loop induction. 668 if (!setupOuterLoopInductions()) { 669 reportVectorizationFailure("Unsupported outer loop Phi(s)", 670 "Unsupported outer loop Phi(s)", 671 "UnsupportedPhi", ORE, TheLoop); 672 if (DoExtraAnalysis) 673 Result = false; 674 else 675 return false; 676 } 677 678 return Result; 679 } 680 681 void LoopVectorizationLegality::addInductionPhi( 682 PHINode *Phi, const InductionDescriptor &ID, 683 SmallPtrSetImpl<Value *> &AllowedExit) { 684 Inductions[Phi] = ID; 685 686 // In case this induction also comes with casts that we know we can ignore 687 // in the vectorized loop body, record them here. All casts could be recorded 688 // here for ignoring, but suffices to record only the first (as it is the 689 // only one that may bw used outside the cast sequence). 690 const SmallVectorImpl<Instruction *> &Casts = ID.getCastInsts(); 691 if (!Casts.empty()) 692 InductionCastsToIgnore.insert(*Casts.begin()); 693 694 Type *PhiTy = Phi->getType(); 695 const DataLayout &DL = Phi->getModule()->getDataLayout(); 696 697 // Get the widest type. 698 if (!PhiTy->isFloatingPointTy()) { 699 if (!WidestIndTy) 700 WidestIndTy = convertPointerToIntegerType(DL, PhiTy); 701 else 702 WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy); 703 } 704 705 // Int inductions are special because we only allow one IV. 706 if (ID.getKind() == InductionDescriptor::IK_IntInduction && 707 ID.getConstIntStepValue() && ID.getConstIntStepValue()->isOne() && 708 isa<Constant>(ID.getStartValue()) && 709 cast<Constant>(ID.getStartValue())->isNullValue()) { 710 711 // Use the phi node with the widest type as induction. Use the last 712 // one if there are multiple (no good reason for doing this other 713 // than it is expedient). We've checked that it begins at zero and 714 // steps by one, so this is a canonical induction variable. 715 if (!PrimaryInduction || PhiTy == WidestIndTy) 716 PrimaryInduction = Phi; 717 } 718 719 // Both the PHI node itself, and the "post-increment" value feeding 720 // back into the PHI node may have external users. 721 // We can allow those uses, except if the SCEVs we have for them rely 722 // on predicates that only hold within the loop, since allowing the exit 723 // currently means re-using this SCEV outside the loop (see PR33706 for more 724 // details). 725 if (PSE.getPredicate().isAlwaysTrue()) { 726 AllowedExit.insert(Phi); 727 AllowedExit.insert(Phi->getIncomingValueForBlock(TheLoop->getLoopLatch())); 728 } 729 730 LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n"); 731 } 732 733 bool LoopVectorizationLegality::setupOuterLoopInductions() { 734 BasicBlock *Header = TheLoop->getHeader(); 735 736 // Returns true if a given Phi is a supported induction. 737 auto isSupportedPhi = [&](PHINode &Phi) -> bool { 738 InductionDescriptor ID; 739 if (InductionDescriptor::isInductionPHI(&Phi, TheLoop, PSE, ID) && 740 ID.getKind() == InductionDescriptor::IK_IntInduction) { 741 addInductionPhi(&Phi, ID, AllowedExit); 742 return true; 743 } else { 744 // Bail out for any Phi in the outer loop header that is not a supported 745 // induction. 746 LLVM_DEBUG( 747 dbgs() 748 << "LV: Found unsupported PHI for outer loop vectorization.\n"); 749 return false; 750 } 751 }; 752 753 if (llvm::all_of(Header->phis(), isSupportedPhi)) 754 return true; 755 else 756 return false; 757 } 758 759 /// Checks if a function is scalarizable according to the TLI, in 760 /// the sense that it should be vectorized and then expanded in 761 /// multiple scalar calls. This is represented in the 762 /// TLI via mappings that do not specify a vector name, as in the 763 /// following example: 764 /// 765 /// const VecDesc VecIntrinsics[] = { 766 /// {"llvm.phx.abs.i32", "", 4} 767 /// }; 768 static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI) { 769 const StringRef ScalarName = CI.getCalledFunction()->getName(); 770 bool Scalarize = TLI.isFunctionVectorizable(ScalarName); 771 // Check that all known VFs are not associated to a vector 772 // function, i.e. the vector name is emty. 773 if (Scalarize) { 774 ElementCount WidestFixedVF, WidestScalableVF; 775 TLI.getWidestVF(ScalarName, WidestFixedVF, WidestScalableVF); 776 for (ElementCount VF = ElementCount::getFixed(2); 777 ElementCount::isKnownLE(VF, WidestFixedVF); VF *= 2) 778 Scalarize &= !TLI.isFunctionVectorizable(ScalarName, VF); 779 for (ElementCount VF = ElementCount::getScalable(1); 780 ElementCount::isKnownLE(VF, WidestScalableVF); VF *= 2) 781 Scalarize &= !TLI.isFunctionVectorizable(ScalarName, VF); 782 assert((WidestScalableVF.isZero() || !Scalarize) && 783 "Caller may decide to scalarize a variant using a scalable VF"); 784 } 785 return Scalarize; 786 } 787 788 bool LoopVectorizationLegality::canVectorizeInstrs() { 789 BasicBlock *Header = TheLoop->getHeader(); 790 791 // For each block in the loop. 792 for (BasicBlock *BB : TheLoop->blocks()) { 793 // Scan the instructions in the block and look for hazards. 794 for (Instruction &I : *BB) { 795 if (auto *Phi = dyn_cast<PHINode>(&I)) { 796 Type *PhiTy = Phi->getType(); 797 // Check that this PHI type is allowed. 798 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() && 799 !PhiTy->isPointerTy()) { 800 reportVectorizationFailure("Found a non-int non-pointer PHI", 801 "loop control flow is not understood by vectorizer", 802 "CFGNotUnderstood", ORE, TheLoop); 803 return false; 804 } 805 806 // If this PHINode is not in the header block, then we know that we 807 // can convert it to select during if-conversion. No need to check if 808 // the PHIs in this block are induction or reduction variables. 809 if (BB != Header) { 810 // Non-header phi nodes that have outside uses can be vectorized. Add 811 // them to the list of allowed exits. 812 // Unsafe cyclic dependencies with header phis are identified during 813 // legalization for reduction, induction and fixed order 814 // recurrences. 815 AllowedExit.insert(&I); 816 continue; 817 } 818 819 // We only allow if-converted PHIs with exactly two incoming values. 820 if (Phi->getNumIncomingValues() != 2) { 821 reportVectorizationFailure("Found an invalid PHI", 822 "loop control flow is not understood by vectorizer", 823 "CFGNotUnderstood", ORE, TheLoop, Phi); 824 return false; 825 } 826 827 RecurrenceDescriptor RedDes; 828 if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC, 829 DT, PSE.getSE())) { 830 Requirements->addExactFPMathInst(RedDes.getExactFPMathInst()); 831 AllowedExit.insert(RedDes.getLoopExitInstr()); 832 Reductions[Phi] = RedDes; 833 continue; 834 } 835 836 // We prevent matching non-constant strided pointer IVS to preserve 837 // historical vectorizer behavior after a generalization of the 838 // IVDescriptor code. The intent is to remove this check, but we 839 // have to fix issues around code quality for such loops first. 840 auto isDisallowedStridedPointerInduction = 841 [](const InductionDescriptor &ID) { 842 if (AllowStridedPointerIVs) 843 return false; 844 return ID.getKind() == InductionDescriptor::IK_PtrInduction && 845 ID.getConstIntStepValue() == nullptr; 846 }; 847 848 // TODO: Instead of recording the AllowedExit, it would be good to 849 // record the complementary set: NotAllowedExit. These include (but may 850 // not be limited to): 851 // 1. Reduction phis as they represent the one-before-last value, which 852 // is not available when vectorized 853 // 2. Induction phis and increment when SCEV predicates cannot be used 854 // outside the loop - see addInductionPhi 855 // 3. Non-Phis with outside uses when SCEV predicates cannot be used 856 // outside the loop - see call to hasOutsideLoopUser in the non-phi 857 // handling below 858 // 4. FixedOrderRecurrence phis that can possibly be handled by 859 // extraction. 860 // By recording these, we can then reason about ways to vectorize each 861 // of these NotAllowedExit. 862 InductionDescriptor ID; 863 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID) && 864 !isDisallowedStridedPointerInduction(ID)) { 865 addInductionPhi(Phi, ID, AllowedExit); 866 Requirements->addExactFPMathInst(ID.getExactFPMathInst()); 867 continue; 868 } 869 870 if (RecurrenceDescriptor::isFixedOrderRecurrence(Phi, TheLoop, DT)) { 871 AllowedExit.insert(Phi); 872 FixedOrderRecurrences.insert(Phi); 873 continue; 874 } 875 876 // As a last resort, coerce the PHI to a AddRec expression 877 // and re-try classifying it a an induction PHI. 878 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID, true) && 879 !isDisallowedStridedPointerInduction(ID)) { 880 addInductionPhi(Phi, ID, AllowedExit); 881 continue; 882 } 883 884 reportVectorizationFailure("Found an unidentified PHI", 885 "value that could not be identified as " 886 "reduction is used outside the loop", 887 "NonReductionValueUsedOutsideLoop", ORE, TheLoop, Phi); 888 return false; 889 } // end of PHI handling 890 891 // We handle calls that: 892 // * Are debug info intrinsics. 893 // * Have a mapping to an IR intrinsic. 894 // * Have a vector version available. 895 auto *CI = dyn_cast<CallInst>(&I); 896 897 if (CI && !getVectorIntrinsicIDForCall(CI, TLI) && 898 !isa<DbgInfoIntrinsic>(CI) && 899 !(CI->getCalledFunction() && TLI && 900 (!VFDatabase::getMappings(*CI).empty() || 901 isTLIScalarize(*TLI, *CI)))) { 902 // If the call is a recognized math libary call, it is likely that 903 // we can vectorize it given loosened floating-point constraints. 904 LibFunc Func; 905 bool IsMathLibCall = 906 TLI && CI->getCalledFunction() && 907 CI->getType()->isFloatingPointTy() && 908 TLI->getLibFunc(CI->getCalledFunction()->getName(), Func) && 909 TLI->hasOptimizedCodeGen(Func); 910 911 if (IsMathLibCall) { 912 // TODO: Ideally, we should not use clang-specific language here, 913 // but it's hard to provide meaningful yet generic advice. 914 // Also, should this be guarded by allowExtraAnalysis() and/or be part 915 // of the returned info from isFunctionVectorizable()? 916 reportVectorizationFailure( 917 "Found a non-intrinsic callsite", 918 "library call cannot be vectorized. " 919 "Try compiling with -fno-math-errno, -ffast-math, " 920 "or similar flags", 921 "CantVectorizeLibcall", ORE, TheLoop, CI); 922 } else { 923 reportVectorizationFailure("Found a non-intrinsic callsite", 924 "call instruction cannot be vectorized", 925 "CantVectorizeLibcall", ORE, TheLoop, CI); 926 } 927 return false; 928 } 929 930 // Some intrinsics have scalar arguments and should be same in order for 931 // them to be vectorized (i.e. loop invariant). 932 if (CI) { 933 auto *SE = PSE.getSE(); 934 Intrinsic::ID IntrinID = getVectorIntrinsicIDForCall(CI, TLI); 935 for (unsigned i = 0, e = CI->arg_size(); i != e; ++i) 936 if (isVectorIntrinsicWithScalarOpAtArg(IntrinID, i)) { 937 if (!SE->isLoopInvariant(PSE.getSCEV(CI->getOperand(i)), TheLoop)) { 938 reportVectorizationFailure("Found unvectorizable intrinsic", 939 "intrinsic instruction cannot be vectorized", 940 "CantVectorizeIntrinsic", ORE, TheLoop, CI); 941 return false; 942 } 943 } 944 } 945 946 // Check that the instruction return type is vectorizable. 947 // Also, we can't vectorize extractelement instructions. 948 if ((!VectorType::isValidElementType(I.getType()) && 949 !I.getType()->isVoidTy()) || 950 isa<ExtractElementInst>(I)) { 951 reportVectorizationFailure("Found unvectorizable type", 952 "instruction return type cannot be vectorized", 953 "CantVectorizeInstructionReturnType", ORE, TheLoop, &I); 954 return false; 955 } 956 957 // Check that the stored type is vectorizable. 958 if (auto *ST = dyn_cast<StoreInst>(&I)) { 959 Type *T = ST->getValueOperand()->getType(); 960 if (!VectorType::isValidElementType(T)) { 961 reportVectorizationFailure("Store instruction cannot be vectorized", 962 "store instruction cannot be vectorized", 963 "CantVectorizeStore", ORE, TheLoop, ST); 964 return false; 965 } 966 967 // For nontemporal stores, check that a nontemporal vector version is 968 // supported on the target. 969 if (ST->getMetadata(LLVMContext::MD_nontemporal)) { 970 // Arbitrarily try a vector of 2 elements. 971 auto *VecTy = FixedVectorType::get(T, /*NumElts=*/2); 972 assert(VecTy && "did not find vectorized version of stored type"); 973 if (!TTI->isLegalNTStore(VecTy, ST->getAlign())) { 974 reportVectorizationFailure( 975 "nontemporal store instruction cannot be vectorized", 976 "nontemporal store instruction cannot be vectorized", 977 "CantVectorizeNontemporalStore", ORE, TheLoop, ST); 978 return false; 979 } 980 } 981 982 } else if (auto *LD = dyn_cast<LoadInst>(&I)) { 983 if (LD->getMetadata(LLVMContext::MD_nontemporal)) { 984 // For nontemporal loads, check that a nontemporal vector version is 985 // supported on the target (arbitrarily try a vector of 2 elements). 986 auto *VecTy = FixedVectorType::get(I.getType(), /*NumElts=*/2); 987 assert(VecTy && "did not find vectorized version of load type"); 988 if (!TTI->isLegalNTLoad(VecTy, LD->getAlign())) { 989 reportVectorizationFailure( 990 "nontemporal load instruction cannot be vectorized", 991 "nontemporal load instruction cannot be vectorized", 992 "CantVectorizeNontemporalLoad", ORE, TheLoop, LD); 993 return false; 994 } 995 } 996 997 // FP instructions can allow unsafe algebra, thus vectorizable by 998 // non-IEEE-754 compliant SIMD units. 999 // This applies to floating-point math operations and calls, not memory 1000 // operations, shuffles, or casts, as they don't change precision or 1001 // semantics. 1002 } else if (I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp()) && 1003 !I.isFast()) { 1004 LLVM_DEBUG(dbgs() << "LV: Found FP op with unsafe algebra.\n"); 1005 Hints->setPotentiallyUnsafe(); 1006 } 1007 1008 // Reduction instructions are allowed to have exit users. 1009 // All other instructions must not have external users. 1010 if (hasOutsideLoopUser(TheLoop, &I, AllowedExit)) { 1011 // We can safely vectorize loops where instructions within the loop are 1012 // used outside the loop only if the SCEV predicates within the loop is 1013 // same as outside the loop. Allowing the exit means reusing the SCEV 1014 // outside the loop. 1015 if (PSE.getPredicate().isAlwaysTrue()) { 1016 AllowedExit.insert(&I); 1017 continue; 1018 } 1019 reportVectorizationFailure("Value cannot be used outside the loop", 1020 "value cannot be used outside the loop", 1021 "ValueUsedOutsideLoop", ORE, TheLoop, &I); 1022 return false; 1023 } 1024 } // next instr. 1025 } 1026 1027 if (!PrimaryInduction) { 1028 if (Inductions.empty()) { 1029 reportVectorizationFailure("Did not find one integer induction var", 1030 "loop induction variable could not be identified", 1031 "NoInductionVariable", ORE, TheLoop); 1032 return false; 1033 } else if (!WidestIndTy) { 1034 reportVectorizationFailure("Did not find one integer induction var", 1035 "integer loop induction variable could not be identified", 1036 "NoIntegerInductionVariable", ORE, TheLoop); 1037 return false; 1038 } else { 1039 LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n"); 1040 } 1041 } 1042 1043 // Now we know the widest induction type, check if our found induction 1044 // is the same size. If it's not, unset it here and InnerLoopVectorizer 1045 // will create another. 1046 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType()) 1047 PrimaryInduction = nullptr; 1048 1049 return true; 1050 } 1051 1052 bool LoopVectorizationLegality::canVectorizeMemory() { 1053 LAI = &LAIs.getInfo(*TheLoop); 1054 const OptimizationRemarkAnalysis *LAR = LAI->getReport(); 1055 if (LAR) { 1056 ORE->emit([&]() { 1057 return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(), 1058 "loop not vectorized: ", *LAR); 1059 }); 1060 } 1061 1062 if (!LAI->canVectorizeMemory()) 1063 return false; 1064 1065 // We can vectorize stores to invariant address when final reduction value is 1066 // guaranteed to be stored at the end of the loop. Also, if decision to 1067 // vectorize loop is made, runtime checks are added so as to make sure that 1068 // invariant address won't alias with any other objects. 1069 if (!LAI->getStoresToInvariantAddresses().empty()) { 1070 // For each invariant address, check if last stored value is unconditional 1071 // and the address is not calculated inside the loop. 1072 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) { 1073 if (!isInvariantStoreOfReduction(SI)) 1074 continue; 1075 1076 if (blockNeedsPredication(SI->getParent())) { 1077 reportVectorizationFailure( 1078 "We don't allow storing to uniform addresses", 1079 "write of conditional recurring variant value to a loop " 1080 "invariant address could not be vectorized", 1081 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop); 1082 return false; 1083 } 1084 1085 // Invariant address should be defined outside of loop. LICM pass usually 1086 // makes sure it happens, but in rare cases it does not, we do not want 1087 // to overcomplicate vectorization to support this case. 1088 if (Instruction *Ptr = dyn_cast<Instruction>(SI->getPointerOperand())) { 1089 if (TheLoop->contains(Ptr)) { 1090 reportVectorizationFailure( 1091 "Invariant address is calculated inside the loop", 1092 "write to a loop invariant address could not " 1093 "be vectorized", 1094 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop); 1095 return false; 1096 } 1097 } 1098 } 1099 1100 if (LAI->hasDependenceInvolvingLoopInvariantAddress()) { 1101 // For each invariant address, check its last stored value is the result 1102 // of one of our reductions. 1103 // 1104 // We do not check if dependence with loads exists because they are 1105 // currently rejected earlier in LoopAccessInfo::analyzeLoop. In case this 1106 // behaviour changes we have to modify this code. 1107 ScalarEvolution *SE = PSE.getSE(); 1108 SmallVector<StoreInst *, 4> UnhandledStores; 1109 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) { 1110 if (isInvariantStoreOfReduction(SI)) { 1111 // Earlier stores to this address are effectively deadcode. 1112 // With opaque pointers it is possible for one pointer to be used with 1113 // different sizes of stored values: 1114 // store i32 0, ptr %x 1115 // store i8 0, ptr %x 1116 // The latest store doesn't complitely overwrite the first one in the 1117 // example. That is why we have to make sure that types of stored 1118 // values are same. 1119 // TODO: Check that bitwidth of unhandled store is smaller then the 1120 // one that overwrites it and add a test. 1121 erase_if(UnhandledStores, [SE, SI](StoreInst *I) { 1122 return storeToSameAddress(SE, SI, I) && 1123 I->getValueOperand()->getType() == 1124 SI->getValueOperand()->getType(); 1125 }); 1126 continue; 1127 } 1128 UnhandledStores.push_back(SI); 1129 } 1130 1131 bool IsOK = UnhandledStores.empty(); 1132 // TODO: we should also validate against InvariantMemSets. 1133 if (!IsOK) { 1134 reportVectorizationFailure( 1135 "We don't allow storing to uniform addresses", 1136 "write to a loop invariant address could not " 1137 "be vectorized", 1138 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop); 1139 return false; 1140 } 1141 } 1142 } 1143 1144 PSE.addPredicate(LAI->getPSE().getPredicate()); 1145 return true; 1146 } 1147 1148 bool LoopVectorizationLegality::canVectorizeFPMath( 1149 bool EnableStrictReductions) { 1150 1151 // First check if there is any ExactFP math or if we allow reassociations 1152 if (!Requirements->getExactFPInst() || Hints->allowReordering()) 1153 return true; 1154 1155 // If the above is false, we have ExactFPMath & do not allow reordering. 1156 // If the EnableStrictReductions flag is set, first check if we have any 1157 // Exact FP induction vars, which we cannot vectorize. 1158 if (!EnableStrictReductions || 1159 any_of(getInductionVars(), [&](auto &Induction) -> bool { 1160 InductionDescriptor IndDesc = Induction.second; 1161 return IndDesc.getExactFPMathInst(); 1162 })) 1163 return false; 1164 1165 // We can now only vectorize if all reductions with Exact FP math also 1166 // have the isOrdered flag set, which indicates that we can move the 1167 // reduction operations in-loop. 1168 return (all_of(getReductionVars(), [&](auto &Reduction) -> bool { 1169 const RecurrenceDescriptor &RdxDesc = Reduction.second; 1170 return !RdxDesc.hasExactFPMath() || RdxDesc.isOrdered(); 1171 })); 1172 } 1173 1174 bool LoopVectorizationLegality::isInvariantStoreOfReduction(StoreInst *SI) { 1175 return any_of(getReductionVars(), [&](auto &Reduction) -> bool { 1176 const RecurrenceDescriptor &RdxDesc = Reduction.second; 1177 return RdxDesc.IntermediateStore == SI; 1178 }); 1179 } 1180 1181 bool LoopVectorizationLegality::isInvariantAddressOfReduction(Value *V) { 1182 return any_of(getReductionVars(), [&](auto &Reduction) -> bool { 1183 const RecurrenceDescriptor &RdxDesc = Reduction.second; 1184 if (!RdxDesc.IntermediateStore) 1185 return false; 1186 1187 ScalarEvolution *SE = PSE.getSE(); 1188 Value *InvariantAddress = RdxDesc.IntermediateStore->getPointerOperand(); 1189 return V == InvariantAddress || 1190 SE->getSCEV(V) == SE->getSCEV(InvariantAddress); 1191 }); 1192 } 1193 1194 bool LoopVectorizationLegality::isInductionPhi(const Value *V) const { 1195 Value *In0 = const_cast<Value *>(V); 1196 PHINode *PN = dyn_cast_or_null<PHINode>(In0); 1197 if (!PN) 1198 return false; 1199 1200 return Inductions.count(PN); 1201 } 1202 1203 const InductionDescriptor * 1204 LoopVectorizationLegality::getIntOrFpInductionDescriptor(PHINode *Phi) const { 1205 if (!isInductionPhi(Phi)) 1206 return nullptr; 1207 auto &ID = getInductionVars().find(Phi)->second; 1208 if (ID.getKind() == InductionDescriptor::IK_IntInduction || 1209 ID.getKind() == InductionDescriptor::IK_FpInduction) 1210 return &ID; 1211 return nullptr; 1212 } 1213 1214 const InductionDescriptor * 1215 LoopVectorizationLegality::getPointerInductionDescriptor(PHINode *Phi) const { 1216 if (!isInductionPhi(Phi)) 1217 return nullptr; 1218 auto &ID = getInductionVars().find(Phi)->second; 1219 if (ID.getKind() == InductionDescriptor::IK_PtrInduction) 1220 return &ID; 1221 return nullptr; 1222 } 1223 1224 bool LoopVectorizationLegality::isCastedInductionVariable( 1225 const Value *V) const { 1226 auto *Inst = dyn_cast<Instruction>(V); 1227 return (Inst && InductionCastsToIgnore.count(Inst)); 1228 } 1229 1230 bool LoopVectorizationLegality::isInductionVariable(const Value *V) const { 1231 return isInductionPhi(V) || isCastedInductionVariable(V); 1232 } 1233 1234 bool LoopVectorizationLegality::isFixedOrderRecurrence( 1235 const PHINode *Phi) const { 1236 return FixedOrderRecurrences.count(Phi); 1237 } 1238 1239 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB) const { 1240 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT); 1241 } 1242 1243 bool LoopVectorizationLegality::blockCanBePredicated( 1244 BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs, 1245 SmallPtrSetImpl<const Instruction *> &MaskedOp, 1246 SmallPtrSetImpl<Instruction *> &ConditionalAssumes) const { 1247 for (Instruction &I : *BB) { 1248 // We can predicate blocks with calls to assume, as long as we drop them in 1249 // case we flatten the CFG via predication. 1250 if (match(&I, m_Intrinsic<Intrinsic::assume>())) { 1251 ConditionalAssumes.insert(&I); 1252 continue; 1253 } 1254 1255 // Do not let llvm.experimental.noalias.scope.decl block the vectorization. 1256 // TODO: there might be cases that it should block the vectorization. Let's 1257 // ignore those for now. 1258 if (isa<NoAliasScopeDeclInst>(&I)) 1259 continue; 1260 1261 // We can allow masked calls if there's at least one vector variant, even 1262 // if we end up scalarizing due to the cost model calculations. 1263 // TODO: Allow other calls if they have appropriate attributes... readonly 1264 // and argmemonly? 1265 if (CallInst *CI = dyn_cast<CallInst>(&I)) 1266 if (VFDatabase::hasMaskedVariant(*CI)) { 1267 MaskedOp.insert(CI); 1268 continue; 1269 } 1270 1271 // Loads are handled via masking (or speculated if safe to do so.) 1272 if (auto *LI = dyn_cast<LoadInst>(&I)) { 1273 if (!SafePtrs.count(LI->getPointerOperand())) 1274 MaskedOp.insert(LI); 1275 continue; 1276 } 1277 1278 // Predicated store requires some form of masking: 1279 // 1) masked store HW instruction, 1280 // 2) emulation via load-blend-store (only if safe and legal to do so, 1281 // be aware on the race conditions), or 1282 // 3) element-by-element predicate check and scalar store. 1283 if (auto *SI = dyn_cast<StoreInst>(&I)) { 1284 MaskedOp.insert(SI); 1285 continue; 1286 } 1287 1288 if (I.mayReadFromMemory() || I.mayWriteToMemory() || I.mayThrow()) 1289 return false; 1290 } 1291 1292 return true; 1293 } 1294 1295 bool LoopVectorizationLegality::canVectorizeWithIfConvert() { 1296 if (!EnableIfConversion) { 1297 reportVectorizationFailure("If-conversion is disabled", 1298 "if-conversion is disabled", 1299 "IfConversionDisabled", 1300 ORE, TheLoop); 1301 return false; 1302 } 1303 1304 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable"); 1305 1306 // A list of pointers which are known to be dereferenceable within scope of 1307 // the loop body for each iteration of the loop which executes. That is, 1308 // the memory pointed to can be dereferenced (with the access size implied by 1309 // the value's type) unconditionally within the loop header without 1310 // introducing a new fault. 1311 SmallPtrSet<Value *, 8> SafePointers; 1312 1313 // Collect safe addresses. 1314 for (BasicBlock *BB : TheLoop->blocks()) { 1315 if (!blockNeedsPredication(BB)) { 1316 for (Instruction &I : *BB) 1317 if (auto *Ptr = getLoadStorePointerOperand(&I)) 1318 SafePointers.insert(Ptr); 1319 continue; 1320 } 1321 1322 // For a block which requires predication, a address may be safe to access 1323 // in the loop w/o predication if we can prove dereferenceability facts 1324 // sufficient to ensure it'll never fault within the loop. For the moment, 1325 // we restrict this to loads; stores are more complicated due to 1326 // concurrency restrictions. 1327 ScalarEvolution &SE = *PSE.getSE(); 1328 for (Instruction &I : *BB) { 1329 LoadInst *LI = dyn_cast<LoadInst>(&I); 1330 if (LI && !LI->getType()->isVectorTy() && !mustSuppressSpeculation(*LI) && 1331 isDereferenceableAndAlignedInLoop(LI, TheLoop, SE, *DT, AC)) 1332 SafePointers.insert(LI->getPointerOperand()); 1333 } 1334 } 1335 1336 // Collect the blocks that need predication. 1337 for (BasicBlock *BB : TheLoop->blocks()) { 1338 // We don't support switch statements inside loops. 1339 if (!isa<BranchInst>(BB->getTerminator())) { 1340 reportVectorizationFailure("Loop contains a switch statement", 1341 "loop contains a switch statement", 1342 "LoopContainsSwitch", ORE, TheLoop, 1343 BB->getTerminator()); 1344 return false; 1345 } 1346 1347 // We must be able to predicate all blocks that need to be predicated. 1348 if (blockNeedsPredication(BB)) { 1349 if (!blockCanBePredicated(BB, SafePointers, MaskedOp, 1350 ConditionalAssumes)) { 1351 reportVectorizationFailure( 1352 "Control flow cannot be substituted for a select", 1353 "control flow cannot be substituted for a select", 1354 "NoCFGForSelect", ORE, TheLoop, 1355 BB->getTerminator()); 1356 return false; 1357 } 1358 } 1359 } 1360 1361 // We can if-convert this loop. 1362 return true; 1363 } 1364 1365 // Helper function to canVectorizeLoopNestCFG. 1366 bool LoopVectorizationLegality::canVectorizeLoopCFG(Loop *Lp, 1367 bool UseVPlanNativePath) { 1368 assert((UseVPlanNativePath || Lp->isInnermost()) && 1369 "VPlan-native path is not enabled."); 1370 1371 // TODO: ORE should be improved to show more accurate information when an 1372 // outer loop can't be vectorized because a nested loop is not understood or 1373 // legal. Something like: "outer_loop_location: loop not vectorized: 1374 // (inner_loop_location) loop control flow is not understood by vectorizer". 1375 1376 // Store the result and return it at the end instead of exiting early, in case 1377 // allowExtraAnalysis is used to report multiple reasons for not vectorizing. 1378 bool Result = true; 1379 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE); 1380 1381 // We must have a loop in canonical form. Loops with indirectbr in them cannot 1382 // be canonicalized. 1383 if (!Lp->getLoopPreheader()) { 1384 reportVectorizationFailure("Loop doesn't have a legal pre-header", 1385 "loop control flow is not understood by vectorizer", 1386 "CFGNotUnderstood", ORE, TheLoop); 1387 if (DoExtraAnalysis) 1388 Result = false; 1389 else 1390 return false; 1391 } 1392 1393 // We must have a single backedge. 1394 if (Lp->getNumBackEdges() != 1) { 1395 reportVectorizationFailure("The loop must have a single backedge", 1396 "loop control flow is not understood by vectorizer", 1397 "CFGNotUnderstood", ORE, TheLoop); 1398 if (DoExtraAnalysis) 1399 Result = false; 1400 else 1401 return false; 1402 } 1403 1404 return Result; 1405 } 1406 1407 bool LoopVectorizationLegality::canVectorizeLoopNestCFG( 1408 Loop *Lp, bool UseVPlanNativePath) { 1409 // Store the result and return it at the end instead of exiting early, in case 1410 // allowExtraAnalysis is used to report multiple reasons for not vectorizing. 1411 bool Result = true; 1412 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE); 1413 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) { 1414 if (DoExtraAnalysis) 1415 Result = false; 1416 else 1417 return false; 1418 } 1419 1420 // Recursively check whether the loop control flow of nested loops is 1421 // understood. 1422 for (Loop *SubLp : *Lp) 1423 if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) { 1424 if (DoExtraAnalysis) 1425 Result = false; 1426 else 1427 return false; 1428 } 1429 1430 return Result; 1431 } 1432 1433 bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) { 1434 // Store the result and return it at the end instead of exiting early, in case 1435 // allowExtraAnalysis is used to report multiple reasons for not vectorizing. 1436 bool Result = true; 1437 1438 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE); 1439 // Check whether the loop-related control flow in the loop nest is expected by 1440 // vectorizer. 1441 if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) { 1442 if (DoExtraAnalysis) 1443 Result = false; 1444 else 1445 return false; 1446 } 1447 1448 // We need to have a loop header. 1449 LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName() 1450 << '\n'); 1451 1452 // Specific checks for outer loops. We skip the remaining legal checks at this 1453 // point because they don't support outer loops. 1454 if (!TheLoop->isInnermost()) { 1455 assert(UseVPlanNativePath && "VPlan-native path is not enabled."); 1456 1457 if (!canVectorizeOuterLoop()) { 1458 reportVectorizationFailure("Unsupported outer loop", 1459 "unsupported outer loop", 1460 "UnsupportedOuterLoop", 1461 ORE, TheLoop); 1462 // TODO: Implement DoExtraAnalysis when subsequent legal checks support 1463 // outer loops. 1464 return false; 1465 } 1466 1467 LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n"); 1468 return Result; 1469 } 1470 1471 assert(TheLoop->isInnermost() && "Inner loop expected."); 1472 // Check if we can if-convert non-single-bb loops. 1473 unsigned NumBlocks = TheLoop->getNumBlocks(); 1474 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) { 1475 LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n"); 1476 if (DoExtraAnalysis) 1477 Result = false; 1478 else 1479 return false; 1480 } 1481 1482 // Check if we can vectorize the instructions and CFG in this loop. 1483 if (!canVectorizeInstrs()) { 1484 LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n"); 1485 if (DoExtraAnalysis) 1486 Result = false; 1487 else 1488 return false; 1489 } 1490 1491 // Go over each instruction and look at memory deps. 1492 if (!canVectorizeMemory()) { 1493 LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n"); 1494 if (DoExtraAnalysis) 1495 Result = false; 1496 else 1497 return false; 1498 } 1499 1500 LLVM_DEBUG(dbgs() << "LV: We can vectorize this loop" 1501 << (LAI->getRuntimePointerChecking()->Need 1502 ? " (with a runtime bound check)" 1503 : "") 1504 << "!\n"); 1505 1506 unsigned SCEVThreshold = VectorizeSCEVCheckThreshold; 1507 if (Hints->getForce() == LoopVectorizeHints::FK_Enabled) 1508 SCEVThreshold = PragmaVectorizeSCEVCheckThreshold; 1509 1510 if (PSE.getPredicate().getComplexity() > SCEVThreshold) { 1511 reportVectorizationFailure("Too many SCEV checks needed", 1512 "Too many SCEV assumptions need to be made and checked at runtime", 1513 "TooManySCEVRunTimeChecks", ORE, TheLoop); 1514 if (DoExtraAnalysis) 1515 Result = false; 1516 else 1517 return false; 1518 } 1519 1520 // Okay! We've done all the tests. If any have failed, return false. Otherwise 1521 // we can vectorize, and at this point we don't have any other mem analysis 1522 // which may limit our maximum vectorization factor, so just return true with 1523 // no restrictions. 1524 return Result; 1525 } 1526 1527 bool LoopVectorizationLegality::prepareToFoldTailByMasking() { 1528 1529 LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n"); 1530 1531 SmallPtrSet<const Value *, 8> ReductionLiveOuts; 1532 1533 for (const auto &Reduction : getReductionVars()) 1534 ReductionLiveOuts.insert(Reduction.second.getLoopExitInstr()); 1535 1536 // TODO: handle non-reduction outside users when tail is folded by masking. 1537 for (auto *AE : AllowedExit) { 1538 // Check that all users of allowed exit values are inside the loop or 1539 // are the live-out of a reduction. 1540 if (ReductionLiveOuts.count(AE)) 1541 continue; 1542 for (User *U : AE->users()) { 1543 Instruction *UI = cast<Instruction>(U); 1544 if (TheLoop->contains(UI)) 1545 continue; 1546 LLVM_DEBUG( 1547 dbgs() 1548 << "LV: Cannot fold tail by masking, loop has an outside user for " 1549 << *UI << "\n"); 1550 return false; 1551 } 1552 } 1553 1554 // The list of pointers that we can safely read and write to remains empty. 1555 SmallPtrSet<Value *, 8> SafePointers; 1556 1557 SmallPtrSet<const Instruction *, 8> TmpMaskedOp; 1558 SmallPtrSet<Instruction *, 8> TmpConditionalAssumes; 1559 1560 // Check and mark all blocks for predication, including those that ordinarily 1561 // do not need predication such as the header block. 1562 for (BasicBlock *BB : TheLoop->blocks()) { 1563 if (!blockCanBePredicated(BB, SafePointers, TmpMaskedOp, 1564 TmpConditionalAssumes)) { 1565 LLVM_DEBUG(dbgs() << "LV: Cannot fold tail by masking as requested.\n"); 1566 return false; 1567 } 1568 } 1569 1570 LLVM_DEBUG(dbgs() << "LV: can fold tail by masking.\n"); 1571 1572 MaskedOp.insert(TmpMaskedOp.begin(), TmpMaskedOp.end()); 1573 ConditionalAssumes.insert(TmpConditionalAssumes.begin(), 1574 TmpConditionalAssumes.end()); 1575 1576 return true; 1577 } 1578 1579 } // namespace llvm 1580