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