contrib/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

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