lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

   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   // Reductions, Inductions and non-header phis 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   // Check whether we are able to set up outer loop induction.
 520   if (!setupOuterLoopInductions()) {
 521     LLVM_DEBUG(
 522         dbgs() << "LV: Not vectorizing: Unsupported outer loop Phi(s).\n");
 523     ORE->emit(createMissedAnalysis("UnsupportedPhi")
 524               << "Unsupported outer loop Phi(s)");
 525     if (DoExtraAnalysis)
 526       Result = false;
 527     else
 528       return false;
 529   }
 530
 531   return Result;
 532 }
 533
 534 void LoopVectorizationLegality::addInductionPhi(
 535     PHINode *Phi, const InductionDescriptor &ID,
 536     SmallPtrSetImpl<Value *> &AllowedExit) {
 537   Inductions[Phi] = ID;
 538
 539   // In case this induction also comes with casts that we know we can ignore
 540   // in the vectorized loop body, record them here. All casts could be recorded
 541   // here for ignoring, but suffices to record only the first (as it is the
 542   // only one that may bw used outside the cast sequence).
 543   const SmallVectorImpl<Instruction *> &Casts = ID.getCastInsts();
 544   if (!Casts.empty())
 545     InductionCastsToIgnore.insert(*Casts.begin());
 546
 547   Type *PhiTy = Phi->getType();
 548   const DataLayout &DL = Phi->getModule()->getDataLayout();
 549
 550   // Get the widest type.
 551   if (!PhiTy->isFloatingPointTy()) {
 552     if (!WidestIndTy)
 553       WidestIndTy = convertPointerToIntegerType(DL, PhiTy);
 554     else
 555       WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy);
 556   }
 557
 558   // Int inductions are special because we only allow one IV.
 559   if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
 560       ID.getConstIntStepValue() && ID.getConstIntStepValue()->isOne() &&
 561       isa<Constant>(ID.getStartValue()) &&
 562       cast<Constant>(ID.getStartValue())->isNullValue()) {
 563
 564     // Use the phi node with the widest type as induction. Use the last
 565     // one if there are multiple (no good reason for doing this other
 566     // than it is expedient). We've checked that it begins at zero and
 567     // steps by one, so this is a canonical induction variable.
 568     if (!PrimaryInduction || PhiTy == WidestIndTy)
 569       PrimaryInduction = Phi;
 570   }
 571
 572   // Both the PHI node itself, and the "post-increment" value feeding
 573   // back into the PHI node may have external users.
 574   // We can allow those uses, except if the SCEVs we have for them rely
 575   // on predicates that only hold within the loop, since allowing the exit
 576   // currently means re-using this SCEV outside the loop (see PR33706 for more
 577   // details).
 578   if (PSE.getUnionPredicate().isAlwaysTrue()) {
 579     AllowedExit.insert(Phi);
 580     AllowedExit.insert(Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()));
 581   }
 582
 583   LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n");
 584 }
 585
 586 bool LoopVectorizationLegality::setupOuterLoopInductions() {
 587   BasicBlock *Header = TheLoop->getHeader();
 588
 589   // Returns true if a given Phi is a supported induction.
 590   auto isSupportedPhi = [&](PHINode &Phi) -> bool {
 591     InductionDescriptor ID;
 592     if (InductionDescriptor::isInductionPHI(&Phi, TheLoop, PSE, ID) &&
 593         ID.getKind() == InductionDescriptor::IK_IntInduction) {
 594       addInductionPhi(&Phi, ID, AllowedExit);
 595       return true;
 596     } else {
 597       // Bail out for any Phi in the outer loop header that is not a supported
 598       // induction.
 599       LLVM_DEBUG(
 600           dbgs()
 601           << "LV: Found unsupported PHI for outer loop vectorization.\n");
 602       return false;
 603     }
 604   };
 605
 606   if (llvm::all_of(Header->phis(), isSupportedPhi))
 607     return true;
 608   else
 609     return false;
 610 }
 611
 612 bool LoopVectorizationLegality::canVectorizeInstrs() {
 613   BasicBlock *Header = TheLoop->getHeader();
 614
 615   // Look for the attribute signaling the absence of NaNs.
 616   Function &F = *Header->getParent();
 617   HasFunNoNaNAttr =
 618       F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 619
 620   // For each block in the loop.
 621   for (BasicBlock *BB : TheLoop->blocks()) {
 622     // Scan the instructions in the block and look for hazards.
 623     for (Instruction &I : *BB) {
 624       if (auto *Phi = dyn_cast<PHINode>(&I)) {
 625         Type *PhiTy = Phi->getType();
 626         // Check that this PHI type is allowed.
 627         if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
 628             !PhiTy->isPointerTy()) {
 629           ORE->emit(createMissedAnalysis("CFGNotUnderstood", Phi)
 630                     << "loop control flow is not understood by vectorizer");
 631           LLVM_DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
 632           return false;
 633         }
 634
 635         // If this PHINode is not in the header block, then we know that we
 636         // can convert it to select during if-conversion. No need to check if
 637         // the PHIs in this block are induction or reduction variables.
 638         if (BB != Header) {
 639           // Non-header phi nodes that have outside uses can be vectorized. Add
 640           // them to the list of allowed exits.
 641           // Unsafe cyclic dependencies with header phis are identified during
 642           // legalization for reduction, induction and first order
 643           // recurrences.
 644           continue;
 645         }
 646
 647         // We only allow if-converted PHIs with exactly two incoming values.
 648         if (Phi->getNumIncomingValues() != 2) {
 649           ORE->emit(createMissedAnalysis("CFGNotUnderstood", Phi)
 650                     << "control flow not understood by vectorizer");
 651           LLVM_DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
 652           return false;
 653         }
 654
 655         RecurrenceDescriptor RedDes;
 656         if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC,
 657                                                  DT)) {
 658           if (RedDes.hasUnsafeAlgebra())
 659             Requirements->addUnsafeAlgebraInst(RedDes.getUnsafeAlgebraInst());
 660           AllowedExit.insert(RedDes.getLoopExitInstr());
 661           Reductions[Phi] = RedDes;
 662           continue;
 663         }
 664
 665         // TODO: Instead of recording the AllowedExit, it would be good to record the
 666         // complementary set: NotAllowedExit. These include (but may not be
 667         // limited to):
 668         // 1. Reduction phis as they represent the one-before-last value, which
 669         // is not available when vectorized
 670         // 2. Induction phis and increment when SCEV predicates cannot be used
 671         // outside the loop - see addInductionPhi
 672         // 3. Non-Phis with outside uses when SCEV predicates cannot be used
 673         // outside the loop - see call to hasOutsideLoopUser in the non-phi
 674         // handling below
 675         // 4. FirstOrderRecurrence phis that can possibly be handled by
 676         // extraction.
 677         // By recording these, we can then reason about ways to vectorize each
 678         // of these NotAllowedExit.
 679         InductionDescriptor ID;
 680         if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID)) {
 681           addInductionPhi(Phi, ID, AllowedExit);
 682           if (ID.hasUnsafeAlgebra() && !HasFunNoNaNAttr)
 683             Requirements->addUnsafeAlgebraInst(ID.getUnsafeAlgebraInst());
 684           continue;
 685         }
 686
 687         if (RecurrenceDescriptor::isFirstOrderRecurrence(Phi, TheLoop,
 688                                                          SinkAfter, DT)) {
 689           FirstOrderRecurrences.insert(Phi);
 690           continue;
 691         }
 692
 693         // As a last resort, coerce the PHI to a AddRec expression
 694         // and re-try classifying it a an induction PHI.
 695         if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID, true)) {
 696           addInductionPhi(Phi, ID, AllowedExit);
 697           continue;
 698         }
 699
 700         ORE->emit(createMissedAnalysis("NonReductionValueUsedOutsideLoop", Phi)
 701                   << "value that could not be identified as "
 702                      "reduction is used outside the loop");
 703         LLVM_DEBUG(dbgs() << "LV: Found an unidentified PHI." << *Phi << "\n");
 704         return false;
 705       } // end of PHI handling
 706
 707       // We handle calls that:
 708       //   * Are debug info intrinsics.
 709       //   * Have a mapping to an IR intrinsic.
 710       //   * Have a vector version available.
 711       auto *CI = dyn_cast<CallInst>(&I);
 712       if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
 713           !isa<DbgInfoIntrinsic>(CI) &&
 714           !(CI->getCalledFunction() && TLI &&
 715             TLI->isFunctionVectorizable(CI->getCalledFunction()->getName()))) {
 716         ORE->emit(createMissedAnalysis("CantVectorizeCall", CI)
 717                   << "call instruction cannot be vectorized");
 718         LLVM_DEBUG(
 719             dbgs() << "LV: Found a non-intrinsic, non-libfunc callsite.\n");
 720         return false;
 721       }
 722
 723       // Intrinsics such as powi,cttz and ctlz are legal to vectorize if the
 724       // second argument is the same (i.e. loop invariant)
 725       if (CI && hasVectorInstrinsicScalarOpd(
 726                     getVectorIntrinsicIDForCall(CI, TLI), 1)) {
 727         auto *SE = PSE.getSE();
 728         if (!SE->isLoopInvariant(PSE.getSCEV(CI->getOperand(1)), TheLoop)) {
 729           ORE->emit(createMissedAnalysis("CantVectorizeIntrinsic", CI)
 730                     << "intrinsic instruction cannot be vectorized");
 731           LLVM_DEBUG(dbgs()
 732                      << "LV: Found unvectorizable intrinsic " << *CI << "\n");
 733           return false;
 734         }
 735       }
 736
 737       // Check that the instruction return type is vectorizable.
 738       // Also, we can't vectorize extractelement instructions.
 739       if ((!VectorType::isValidElementType(I.getType()) &&
 740            !I.getType()->isVoidTy()) ||
 741           isa<ExtractElementInst>(I)) {
 742         ORE->emit(createMissedAnalysis("CantVectorizeInstructionReturnType", &I)
 743                   << "instruction return type cannot be vectorized");
 744         LLVM_DEBUG(dbgs() << "LV: Found unvectorizable type.\n");
 745         return false;
 746       }
 747
 748       // Check that the stored type is vectorizable.
 749       if (auto *ST = dyn_cast<StoreInst>(&I)) {
 750         Type *T = ST->getValueOperand()->getType();
 751         if (!VectorType::isValidElementType(T)) {
 752           ORE->emit(createMissedAnalysis("CantVectorizeStore", ST)
 753                     << "store instruction cannot be vectorized");
 754           return false;
 755         }
 756
 757         // FP instructions can allow unsafe algebra, thus vectorizable by
 758         // non-IEEE-754 compliant SIMD units.
 759         // This applies to floating-point math operations and calls, not memory
 760         // operations, shuffles, or casts, as they don't change precision or
 761         // semantics.
 762       } else if (I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp()) &&
 763                  !I.isFast()) {
 764         LLVM_DEBUG(dbgs() << "LV: Found FP op with unsafe algebra.\n");
 765         Hints->setPotentiallyUnsafe();
 766       }
 767
 768       // Reduction instructions are allowed to have exit users.
 769       // All other instructions must not have external users.
 770       if (hasOutsideLoopUser(TheLoop, &I, AllowedExit)) {
 771         // We can safely vectorize loops where instructions within the loop are
 772         // used outside the loop only if the SCEV predicates within the loop is
 773         // same as outside the loop. Allowing the exit means reusing the SCEV
 774         // outside the loop.
 775         if (PSE.getUnionPredicate().isAlwaysTrue()) {
 776           AllowedExit.insert(&I);
 777           continue;
 778         }
 779         ORE->emit(createMissedAnalysis("ValueUsedOutsideLoop", &I)
 780                   << "value cannot be used outside the loop");
 781         return false;
 782       }
 783     } // next instr.
 784   }
 785
 786   if (!PrimaryInduction) {
 787     LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
 788     if (Inductions.empty()) {
 789       ORE->emit(createMissedAnalysis("NoInductionVariable")
 790                 << "loop induction variable could not be identified");
 791       return false;
 792     }
 793   }
 794
 795   // Now we know the widest induction type, check if our found induction
 796   // is the same size. If it's not, unset it here and InnerLoopVectorizer
 797   // will create another.
 798   if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
 799     PrimaryInduction = nullptr;
 800
 801   return true;
 802 }
 803
 804 bool LoopVectorizationLegality::canVectorizeMemory() {
 805   LAI = &(*GetLAA)(*TheLoop);
 806   const OptimizationRemarkAnalysis *LAR = LAI->getReport();
 807   if (LAR) {
 808     ORE->emit([&]() {
 809       return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(),
 810                                         "loop not vectorized: ", *LAR);
 811     });
 812   }
 813   if (!LAI->canVectorizeMemory())
 814     return false;
 815
 816   if (LAI->hasStoreToLoopInvariantAddress()) {
 817     ORE->emit(createMissedAnalysis("CantVectorizeStoreToLoopInvariantAddress")
 818               << "write to a loop invariant address could not be vectorized");
 819     LLVM_DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
 820     return false;
 821   }
 822
 823   Requirements->addRuntimePointerChecks(LAI->getNumRuntimePointerChecks());
 824   PSE.addPredicate(LAI->getPSE().getUnionPredicate());
 825
 826   return true;
 827 }
 828
 829 bool LoopVectorizationLegality::isInductionPhi(const Value *V) {
 830   Value *In0 = const_cast<Value *>(V);
 831   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
 832   if (!PN)
 833     return false;
 834
 835   return Inductions.count(PN);
 836 }
 837
 838 bool LoopVectorizationLegality::isCastedInductionVariable(const Value *V) {
 839   auto *Inst = dyn_cast<Instruction>(V);
 840   return (Inst && InductionCastsToIgnore.count(Inst));
 841 }
 842
 843 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
 844   return isInductionPhi(V) || isCastedInductionVariable(V);
 845 }
 846
 847 bool LoopVectorizationLegality::isFirstOrderRecurrence(const PHINode *Phi) {
 848   return FirstOrderRecurrences.count(Phi);
 849 }
 850
 851 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB) {
 852   return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
 853 }
 854
 855 bool LoopVectorizationLegality::blockCanBePredicated(
 856     BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs) {
 857   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
 858
 859   for (Instruction &I : *BB) {
 860     // Check that we don't have a constant expression that can trap as operand.
 861     for (Value *Operand : I.operands()) {
 862       if (auto *C = dyn_cast<Constant>(Operand))
 863         if (C->canTrap())
 864           return false;
 865     }
 866     // We might be able to hoist the load.
 867     if (I.mayReadFromMemory()) {
 868       auto *LI = dyn_cast<LoadInst>(&I);
 869       if (!LI)
 870         return false;
 871       if (!SafePtrs.count(LI->getPointerOperand())) {
 872         // !llvm.mem.parallel_loop_access implies if-conversion safety.
 873         // Otherwise, record that the load needs (real or emulated) masking
 874         // and let the cost model decide.
 875         if (!IsAnnotatedParallel)
 876           MaskedOp.insert(LI);
 877         continue;
 878       }
 879     }
 880
 881     if (I.mayWriteToMemory()) {
 882       auto *SI = dyn_cast<StoreInst>(&I);
 883       if (!SI)
 884         return false;
 885       // Predicated store requires some form of masking:
 886       // 1) masked store HW instruction,
 887       // 2) emulation via load-blend-store (only if safe and legal to do so,
 888       //    be aware on the race conditions), or
 889       // 3) element-by-element predicate check and scalar store.
 890       MaskedOp.insert(SI);
 891       continue;
 892     }
 893     if (I.mayThrow())
 894       return false;
 895   }
 896
 897   return true;
 898 }
 899
 900 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
 901   if (!EnableIfConversion) {
 902     ORE->emit(createMissedAnalysis("IfConversionDisabled")
 903               << "if-conversion is disabled");
 904     return false;
 905   }
 906
 907   assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
 908
 909   // A list of pointers that we can safely read and write to.
 910   SmallPtrSet<Value *, 8> SafePointes;
 911
 912   // Collect safe addresses.
 913   for (BasicBlock *BB : TheLoop->blocks()) {
 914     if (blockNeedsPredication(BB))
 915       continue;
 916
 917     for (Instruction &I : *BB)
 918       if (auto *Ptr = getLoadStorePointerOperand(&I))
 919         SafePointes.insert(Ptr);
 920   }
 921
 922   // Collect the blocks that need predication.
 923   BasicBlock *Header = TheLoop->getHeader();
 924   for (BasicBlock *BB : TheLoop->blocks()) {
 925     // We don't support switch statements inside loops.
 926     if (!isa<BranchInst>(BB->getTerminator())) {
 927       ORE->emit(createMissedAnalysis("LoopContainsSwitch", BB->getTerminator())
 928                 << "loop contains a switch statement");
 929       return false;
 930     }
 931
 932     // We must be able to predicate all blocks that need to be predicated.
 933     if (blockNeedsPredication(BB)) {
 934       if (!blockCanBePredicated(BB, SafePointes)) {
 935         ORE->emit(createMissedAnalysis("NoCFGForSelect", BB->getTerminator())
 936                   << "control flow cannot be substituted for a select");
 937         return false;
 938       }
 939     } else if (BB != Header && !canIfConvertPHINodes(BB)) {
 940       ORE->emit(createMissedAnalysis("NoCFGForSelect", BB->getTerminator())
 941                 << "control flow cannot be substituted for a select");
 942       return false;
 943     }
 944   }
 945
 946   // We can if-convert this loop.
 947   return true;
 948 }
 949
 950 // Helper function to canVectorizeLoopNestCFG.
 951 bool LoopVectorizationLegality::canVectorizeLoopCFG(Loop *Lp,
 952                                                     bool UseVPlanNativePath) {
 953   assert((UseVPlanNativePath || Lp->empty()) &&
 954          "VPlan-native path is not enabled.");
 955
 956   // TODO: ORE should be improved to show more accurate information when an
 957   // outer loop can't be vectorized because a nested loop is not understood or
 958   // legal. Something like: "outer_loop_location: loop not vectorized:
 959   // (inner_loop_location) loop control flow is not understood by vectorizer".
 960
 961   // Store the result and return it at the end instead of exiting early, in case
 962   // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
 963   bool Result = true;
 964   bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
 965
 966   // We must have a loop in canonical form. Loops with indirectbr in them cannot
 967   // be canonicalized.
 968   if (!Lp->getLoopPreheader()) {
 969     LLVM_DEBUG(dbgs() << "LV: Loop doesn't have a legal pre-header.\n");
 970     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
 971               << "loop control flow is not understood by vectorizer");
 972     if (DoExtraAnalysis)
 973       Result = false;
 974     else
 975       return false;
 976   }
 977
 978   // We must have a single backedge.
 979   if (Lp->getNumBackEdges() != 1) {
 980     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
 981               << "loop control flow is not understood by vectorizer");
 982     if (DoExtraAnalysis)
 983       Result = false;
 984     else
 985       return false;
 986   }
 987
 988   // We must have a single exiting block.
 989   if (!Lp->getExitingBlock()) {
 990     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
 991               << "loop control flow is not understood by vectorizer");
 992     if (DoExtraAnalysis)
 993       Result = false;
 994     else
 995       return false;
 996   }
 997
 998   // We only handle bottom-tested loops, i.e. loop in which the condition is
 999   // checked at the end of each iteration. With that we can assume that all
1000   // instructions in the loop are executed the same number of times.
1001   if (Lp->getExitingBlock() != Lp->getLoopLatch()) {
1002     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
1003               << "loop control flow is not understood by vectorizer");
1004     if (DoExtraAnalysis)
1005       Result = false;
1006     else
1007       return false;
1008   }
1009
1010   return Result;
1011 }
1012
1013 bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1014     Loop *Lp, bool UseVPlanNativePath) {
1015   // Store the result and return it at the end instead of exiting early, in case
1016   // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1017   bool Result = true;
1018   bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1019   if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1020     if (DoExtraAnalysis)
1021       Result = false;
1022     else
1023       return false;
1024   }
1025
1026   // Recursively check whether the loop control flow of nested loops is
1027   // understood.
1028   for (Loop *SubLp : *Lp)
1029     if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) {
1030       if (DoExtraAnalysis)
1031         Result = false;
1032       else
1033         return false;
1034     }
1035
1036   return Result;
1037 }
1038
1039 bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
1040   // Store the result and return it at the end instead of exiting early, in case
1041   // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1042   bool Result = true;
1043
1044   bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1045   // Check whether the loop-related control flow in the loop nest is expected by
1046   // vectorizer.
1047   if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) {
1048     if (DoExtraAnalysis)
1049       Result = false;
1050     else
1051       return false;
1052   }
1053
1054   // We need to have a loop header.
1055   LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
1056                     << '\n');
1057
1058   // Specific checks for outer loops. We skip the remaining legal checks at this
1059   // point because they don't support outer loops.
1060   if (!TheLoop->empty()) {
1061     assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
1062
1063     if (!canVectorizeOuterLoop()) {
1064       LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Unsupported outer loop.\n");
1065       // TODO: Implement DoExtraAnalysis when subsequent legal checks support
1066       // outer loops.
1067       return false;
1068     }
1069
1070     LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
1071     return Result;
1072   }
1073
1074   assert(TheLoop->empty() && "Inner loop expected.");
1075   // Check if we can if-convert non-single-bb loops.
1076   unsigned NumBlocks = TheLoop->getNumBlocks();
1077   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
1078     LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
1079     if (DoExtraAnalysis)
1080       Result = false;
1081     else
1082       return false;
1083   }
1084
1085   // Check if we can vectorize the instructions and CFG in this loop.
1086   if (!canVectorizeInstrs()) {
1087     LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
1088     if (DoExtraAnalysis)
1089       Result = false;
1090     else
1091       return false;
1092   }
1093
1094   // Go over each instruction and look at memory deps.
1095   if (!canVectorizeMemory()) {
1096     LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
1097     if (DoExtraAnalysis)
1098       Result = false;
1099     else
1100       return false;
1101   }
1102
1103   LLVM_DEBUG(dbgs() << "LV: We can vectorize this loop"
1104                     << (LAI->getRuntimePointerChecking()->Need
1105                             ? " (with a runtime bound check)"
1106                             : "")
1107                     << "!\n");
1108
1109   unsigned SCEVThreshold = VectorizeSCEVCheckThreshold;
1110   if (Hints->getForce() == LoopVectorizeHints::FK_Enabled)
1111     SCEVThreshold = PragmaVectorizeSCEVCheckThreshold;
1112
1113   if (PSE.getUnionPredicate().getComplexity() > SCEVThreshold) {
1114     ORE->emit(createMissedAnalysis("TooManySCEVRunTimeChecks")
1115               << "Too many SCEV assumptions need to be made and checked "
1116               << "at runtime");
1117     LLVM_DEBUG(dbgs() << "LV: Too many SCEV checks needed.\n");
1118     if (DoExtraAnalysis)
1119       Result = false;
1120     else
1121       return false;
1122   }
1123
1124   // Okay! We've done all the tests. If any have failed, return false. Otherwise
1125   // we can vectorize, and at this point we don't have any other mem analysis
1126   // which may limit our maximum vectorization factor, so just return true with
1127   // no restrictions.
1128   return Result;
1129 }
1130
1131 } // namespace llvm