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