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