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