[LV] NFC: Decouple foldTailByMasking from isScalarWithPredication.

[sdesmalen]

Summary

isScalarWithPredication assumes that the decision for 'foldTailByMasking'
is already calculated, which may not be true at the point of asking the
question. By passing 'VFIterationIsPredicated' as a separate operand, we can
make this dependency explicit, and use this function earlier on before
it has been finally decided whether tail predication will be used.

This patch also renames isPredicatedInst -> requiresPredication, to avoid
the suggestion that the function only returns true if the instruction
was predicated in the original loop.

[bmahjour]

I like this change, but some of the widening decisions used to feed back to the result of isScalarWithPredication which may alter the result in unexpected ways. I'd suggest you try to remove the VF from that function in a separate patch first. If it doesn't break anything anywhere, then we can move ahead with this patch.

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

262

could you try to make this function const? You'd probably need to propagate it to blockNeedsPredication and a few other places, but it'd be worth it.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5350

CM's isLegalMaskedLoad, isLegalMaskedStore, isLegalMaskedGather, isLegalMaskedScatter can also be removed.

[CarolineConcatto]

Hey Sander,
This patch is a fresh air to my eyes.
Thank you!
I think you need to run git-clang-format and I have one more comment.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1520

This ElementCount VF can go away because it is not being used.

[fhahn]

I'd like to understand the main motivation and the reasons why it cannot be done via cost-modeling a bit better. IIUC the main problem is the case where scalable vectorization is forced by the user via pragmas or options? In the auto-vec case, the cost-model would already just skip scalable VFs in those cases as not profitable?

You mention ... we can't yet fall back on scalarization. From that I gather you plan to add support for that in the future? If we could scalarize arbitrary instructions for scalable vectors, would we need to do the check during the legality checks? If it would be possible to scalarize, even if expensive or hard to estimate, it seems to me that the current code should work without change, right?

[sdesmalen]

• Removed LoopVectorizationCostModel::isLegalMasked*
• Marked canVectorizeWithPredication as const.
• Rebased on rG459c48e04f25 (which also removes VF from isPredicatedInst)

[sdesmalen]

In D102437#2759148, @fhahn wrote:

I'd like to understand the main motivation and the reasons why it cannot be done via cost-modeling a bit better. IIUC the main problem is the case where scalable vectorization is forced by the user via pragmas or options? In the auto-vec case, the cost-model would already just skip scalable VFs in those cases as not profitable?

You mention ... we can't yet fall back on scalarization. From that I gather you plan to add support for that in the future? If we could scalarize arbitrary instructions for scalable vectors, would we need to do the check during the legality checks? If it would be possible to scalarize, even if expensive or hard to estimate, it seems to me that the current code should work without change, right?

That's not really the case. The legalizer will ask if the LV can vectorize the loop. Some scalable operations cannot be legalized, because they'd require scalarization, which doesn't exist and there is no plan to add support for such scalarization, so instead we need to make sure that any IR that's generated can be code-generated. Subsequently, this means that the CostModel should always return a valid cost for scalable operations. This is the conceptual split between legalization and the cost-model. i.e. If something is legal, we must be able to cost it. It is also an extra guard to make sure the cost-model is complete.

This is not the only argument for this patch though. As I tried to explain in the commit message, this refactoring also helps untangle the circular dependence between the [choosing of the] VF from the cost-model, and the decision on whether tail predication is needed. e.g. For a trip-count of 100 and a MaxVF of 8, it would not decide the tail is unnecessary, whereas it could decide per VF whether it needs a tail (e.g. for a VF=4, no tail is needed). So there is a possible improvement here. Having isScalarWithPredication and blockNeedsPredication combine both the "needs tail predication" and "block/instruction needs predication" isn't helpful, hence the reason for splitting the two concerns in this patch.

Note that this same distinction is needed when choosing a scalable VF (we can't decide the tail is unnecessary if we don't know the value of vscale, whereas for a fixed-width VF it would be able to remove the tail, but we can't decide that before calling the cost-model if we don't know whether we choose a fixed-width or scalable VF).

[sdesmalen]

Gentle ping.

@bmahjour are you happy with the patch now that I've split off the possibly functional changes? (which should mean this patch is now NFC)

@fhahn were you satisfied by my reasoning?
If so, then I can create a follow-up patch that addresses the FIXME that I left here, and also improve the cost-model for the case where it currently can't eliminate the tail if the trip-count isn't divisible by the MaxVF (where it might pick a VF where the tail can be eliminated without requiring predication)

[fhahn]

In D102437#2759232, @sdesmalen wrote:

That's not really the case. The legalizer will ask if the LV can vectorize the loop. Some scalable operations cannot be legalized, because they'd require scalarization, which doesn't exist and there is no plan to add support for such scalarization, so instead we need to make sure that any IR that's generated can be code-generated.

I am not sure if it was very clear from my earlier comment, I was referring to scalarization + predicated block generation done directly by LV.

For regular vectors, LV does not rely on the backend for scalarization, but it instead creates a loop that iterates over each index for the VF and in the loop conditionally executes the scalar version of the requested instruction and packs the result in a vector. For fixed width VFs the loop is not explicit in the generated IR, because it is just unrolled for the VF. Is there anything fundamental preventing LV to create a similar explicit loop over the scalable VF at runtime? Figuring out an accurate cost would be expensive of course, but I am curious if such scalarization would be possible.

Not sure if I am missing something, but after a quick glance it seems to me that we should have all required pieces in LLVM IR to write such a loop and lower it https://llvm.godbolt.org/z/rhqh9fz8b

Subsequently, this means that the CostModel should always return a valid cost for scalable operations. This is the conceptual split between legalization and the cost-model. i.e. If something is legal, we must be able to cost it. It is also an extra guard to make sure the cost-model is complete.

Agreed. The direction of my comments tries to figure out if there's something LV can do to scalarize arbitrary operations on scalable vectors or not.

This is not the only argument for this patch though. As I tried to explain in the commit message, this refactoring also helps untangle the circular dependence between the [choosing of the] VF from the cost-model, and the decision on whether tail predication is needed. e.g. For a trip-count of 100 and a MaxVF of 8, it would not decide the tail is unnecessary, whereas it could decide per VF whether it needs a tail (e.g. for a VF=4, no tail is needed). So there is a possible improvement here. Having isScalarWithPredication and blockNeedsPredication combine both the "needs tail predication" and "block/instruction needs predication" isn't helpful, hence the reason for splitting the two concerns in this patch.

My comment is only referring to the 'moving to LVL' part of the patch. Not sure if anything bit of the untangling relies on moving the code?

[fhahn]

In D102437#2776569, @fhahn wrote:

Not sure if I am missing something, but after a quick glance it seems to me that we should have all required pieces in LLVM IR to write such a loop and lower it https://llvm.godbolt.org/z/rhqh9fz8b

Slightly updated link https://llvm.godbolt.org/z/nW8n6sMxr

[sdesmalen]

In D102437#2776569, @fhahn wrote:

I am not sure if it was very clear from my earlier comment, I was referring to scalarization + predicated block generation done directly by LV.

For regular vectors, LV does not rely on the backend for scalarization, but it instead creates a loop that iterates over each index for the VF and in the loop conditionally executes the scalar version of the requested instruction and packs the result in a vector. For fixed width VFs the loop is not explicit in the generated IR, because it is just unrolled for the VF. Is there anything fundamental preventing LV to create a similar explicit loop over the scalable VF at runtime? Figuring out an accurate cost would be expensive of course, but I am curious if such scalarization would be possible.

Not sure if I am missing something, but after a quick glance it seems to me that we should have all required pieces in LLVM IR to write such a loop and lower it https://llvm.godbolt.org/z/rhqh9fz8b

Thanks for clarifying. We have prototyped that approach before and our experiments showed it was never beneficial to use scalarization within a vectorized loop with scalable vectors, so we decided to keep the vectorizer simple and disallow scalable auto-vec when scalarization is required. In the case of operations like SDIV, our plan is to emit a llvm.vp intrinsic which can then be ISel'ed natively (using a native instruction w/ predication). It seemed better to disallow it first to avoid any vectorization failures, and then bring up the implementation to support this case.

Subsequently, this means that the CostModel should always return a valid cost for scalable operations. This is the conceptual split between legalization and the cost-model. i.e. If something is legal, we must be able to cost it. It is also an extra guard to make sure the cost-model is complete.

Agreed. The direction of my comments tries to figure out if there's something LV can do to scalarize arbitrary operations on scalable vectors or not.

Alright, makes sense.

This is not the only argument for this patch though. As I tried to explain in the commit message, this refactoring also helps untangle the circular dependence between the [choosing of the] VF from the cost-model, and the decision on whether tail predication is needed. e.g. For a trip-count of 100 and a MaxVF of 8, it would not decide the tail is unnecessary, whereas it could decide per VF whether it needs a tail (e.g. for a VF=4, no tail is needed). So there is a possible improvement here. Having isScalarWithPredication and blockNeedsPredication combine both the "needs tail predication" and "block/instruction needs predication" isn't helpful, hence the reason for splitting the two concerns in this patch.

My comment is only referring to the 'moving to LVL' part of the patch. Not sure if anything bit of the untangling relies on moving the code?

I guess it could equally live in CM, but my reasoning to move it was more that it has nothing to do with the cost-model, so moving it to LVL avoids it getting polluted with other CM-specific code in the future.

[fhahn]

In D102437#2777338, @sdesmalen wrote:

In D102437#2776569, @fhahn wrote:

I am not sure if it was very clear from my earlier comment, I was referring to scalarization + predicated block generation done directly by LV.

For regular vectors, LV does not rely on the backend for scalarization, but it instead creates a loop that iterates over each index for the VF and in the loop conditionally executes the scalar version of the requested instruction and packs the result in a vector. For fixed width VFs the loop is not explicit in the generated IR, because it is just unrolled for the VF. Is there anything fundamental preventing LV to create a similar explicit loop over the scalable VF at runtime? Figuring out an accurate cost would be expensive of course, but I am curious if such scalarization would be possible.

Not sure if I am missing something, but after a quick glance it seems to me that we should have all required pieces in LLVM IR to write such a loop and lower it https://llvm.godbolt.org/z/rhqh9fz8b

Thanks for clarifying. We have prototyped that approach before and our experiments showed it was never beneficial to use scalarization within a vectorized loop with scalable vectors, so we decided to keep the vectorizer simple and disallow scalable auto-vec when scalarization is required. In the case of operations like SDIV, our plan is to emit a llvm.vp intrinsic which can then be ISel'ed natively (using a native instruction w/ predication). It seemed better to disallow it first to avoid any vectorization failures, and then bring up the implementation to support this case.

I see, thanks for elaborating! I am not sure how much extra work generating such loops would be, but it seems like disallowing scalarization requires quite a bit of extra complexity as a number of recent patches that introduce additional restrictions show.

The extra checks also seem introduce various TTI checks that seem to mirror the interfaces that compute cost. Do you know how this will impact other targets with scalable vectors? Do you know if scalarization is similarly expensive on other scalable targets? The naive predication/scalarization is also very expensive on most fixed vector targets and almost never profitable, but it simplifies the rest of the code, because LV can generate vector IR for almost all instructions mechanically.

My comment is only referring to the 'moving to LVL' part of the patch. Not sure if anything bit of the untangling relies on moving the code?

I guess it could equally live in CM, but my reasoning to move it was more that it has nothing to do with the cost-model, so moving it to LVL avoids it getting polluted with other CM-specific code in the future.

From the discussion above, it seems to me that it is still more of a cost question rather than a legality question, as IIUC from the discussion, they could be vectorized by scalarizing via a loop? Also, it looks like all uses of the functions moved to LVL are in the cost-model. The replacement of isLegalMaskedScatter seems also unrelated and could be submitted separately.

[sdesmalen]

• Rebased patch after splitting out some changes.
• Refactored patch to better split concerns between legalization vs cost-model.

[sdesmalen]

In D102437#2790473, @fhahn wrote:

I see, thanks for elaborating! I am not sure how much extra work generating such loops would be, but it seems like disallowing scalarization requires quite a bit of extra complexity as a number of recent patches that introduce additional restrictions show.

The extra checks also seem introduce various TTI checks that seem to mirror the interfaces that compute cost. Do you know how this will impact other targets with scalable vectors? Do you know if scalarization is similarly expensive on other scalable targets? The naive predication/scalarization is also very expensive on most fixed vector targets and almost never profitable, but it simplifies the rest of the code, because LV can generate vector IR for almost all instructions mechanically.

I'll reply to this separately since it's not the only motivation for this patch.

I guess it could equally live in CM, but my reasoning to move it was more that it has nothing to do with the cost-model, so moving it to LVL avoids it getting polluted with other CM-specific code in the future.

From the discussion above, it seems to me that it is still more of a cost question rather than a legality question, as IIUC from the discussion, they could be vectorized by scalarizing via a loop? Also, it looks like all uses of the functions moved to LVL are in the cost-model. The replacement of isLegalMaskedScatter seems also unrelated and could be submitted separately.

Fair point, I've changed the patch a little bit which in my eyes improves the interfaces and splits out the concerns a bit better by providing interfaces to two distinct questions:

• requiresPredicatedWidening: This answers the question "Does this operation require predication when being widened". I've moved this interface to LVL because it describes a property of the operation and adds a requirement to what capability is needed in order to vectorize it. It does not implement a cost-model choice of how this is eventually widened by the LV. This function was initially coined isPredicatedInst, but I find this name a bit more descriptive (also, the original implementation was 'backward', since it used isScalarWithPredication to determine whether the operation was predicated). If you feel strongly about the original name, or having this in the CM, I'm happy to change that.
• isScalarWithPredication: This answers the question "If this operation needs predication, do we have to fall back on scalarizing it?". This is a LV/cost-model decision, hence why it lives in the CM.

Does this make more sense?

Note that I've committed the changes for isLegalMaskedScatter|Gather separately in rG034503e9d2d66ab75679ab5d2ee0848f4de3cac7.

[SjoerdMeijer]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

1337

Just wanted to check what we mean by speculation here (or why it is relevant here)?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1518

nit: I -> \p I

[SjoerdMeijer]

Hmm, strange some comments went missing when I pushed the button previously.

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

1326

I think this is related to the legal vs. cost-model discussion. I agree that it is probably more a cost-model thing. Does that mean this needs to live in CostModel, where it used to live?

[SjoerdMeijer]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5305

I am confused here about names or some negations in logic, but probably it is names.

Here, if we "do not require predicated widening", we return false for isScalarWithPredication, whereas I probably was expecting true. Ignoring some edge cases, requiresPredicatedWidening returns true for most cases because all operations can be widened safely without predication. So probably I am confused that we are talking about widening and isScalar at the same time, or I am missing something else.

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

1326

Okay, if you feel the same way, I'll just move it to the CostModel!

1337

The reason I initially added the comment was because I would have expected return true; (given that the block needs predication or the VF Iteration is predicated), but it seems LVL uses a more detailed analysis to check whether the operation can be speculatively executed, reflected in isMaskRequired(I).

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5305

requiresPredicatedWidening returns true for most cases because all operations can be widened safely without predication

requiresPredicatedWidening returns false for most cases, because most operations can be widened safely without requiring predication.

I've tried to split up two questions:
requiresPredicatedWidening: Given the use of predication in the loop (either from tail folding, or from the operation being under an actual if-then condition), does widening the operation require predication, or conversely: can the operation speculatively execute all lanes followed by a select on the output. If the answer to the latter question is 'no' (like the case for DIV), then the instruction requires a predicated vector operation (<=> predicated widening).
isScalarWithPredication: Given that the operation needs predicated widening, can we actually widen it, or do we need to scalarise it? If it doesn't require predicated widening, we know it also doesn't need to be scalarised (hence the condition to return false here)

Does that help?

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

1326

Just to clarify the original reason to move it to Legality was for a similar reason as that there exists LoopVectoriztionLegality::blockNeedsPredication, which describes a property of the original loop when vectorizing. The same property could be queried for a specific instruction, as if the interface was named instructionNeedsPredication (instead I named it requiresPredicatedWidening).

Also, by moving it out of the CostModel, we avoid private cost-model info to pollute the code such as the foldTailByMasking(), which this patch tries to split out)

[SjoerdMeijer]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5305

Thanks, that definitely helped, and I now see where I went wrong.

These explanations are better (in my opinion) than the current comments for these functions. If you can update those comments that would be good.

I am now going to read the patch again.

[sdesmalen]

Rebased patch (after having pulled out one of the changes into D113392)

[david-arm]

LGTM! I think this is a sensible refactor and it seems clearer in the code now what's going on.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5305

nit: predication

llvm/include/llvm/IR/Instructions.h

 inline unsigned getLoadStoreAddressSpace(Value *I) {
   assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
          "Expected Load or Store instruction");
   if (auto *LI = dyn_cast<LoadInst>(I))
     return LI->getPointerAddressSpace();
   return cast<StoreInst>(I)->getPointerAddressSpace();
 }
 
+/// A helper function that returns the type of loaded or stored value.
+inline Type *getLoadStoreInstValueType(Value *I) {
+  assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
+         "Expected Load or Store instruction");
+  if (auto *LI = dyn_cast<LoadInst>(I))
+    return LI->getType();
+  return cast<StoreInst>(I)->getValueOperand()->getType();
+}
+
 //===----------------------------------------------------------------------===//
 //                              FreezeInst Class
 //===----------------------------------------------------------------------===//
 
 /// This class represents a freeze function that returns random concrete
 /// value if an operand is either a poison value or an undef value
 class FreezeInst : public UnaryInstruction {
 protected:

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

public:
   /// This does not mean that it is profitable to vectorize this
   /// loop, only that it is legal to do so.
   /// Temporarily taking UseVPlanNativePath parameter. If true, take
   /// the new code path being implemented for outer loop vectorization
   /// (should be functional for inner loop vectorization) based on VPlan.
   /// If false, good old LV code.
   bool canVectorize(bool UseVPlanNativePath);
 
+  /// \return true if the instruction can be vectorized. If \p
+  /// VectorizeWithPredication is true, then the strategy requires predication
+  /// to vectorize the loop.
+  bool canVectorizeWithPredication(Instruction *I,
+                                   bool VectorizeWithPredication);
+
   /// Return true if we can vectorize this loop while folding its tail by
   /// masking, and mark all respective loads/stores for masking.
   /// This object's state is only modified iff this function returns true.
   bool prepareToFoldTailByMasking();
 
   /// Returns the primary induction variable.
   PHINode *getPrimaryInduction() { return PrimaryInduction; }
 

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

bool LoopVectorizationLegality::canVectorizeInstrs() {
   // is the same size. If it's not, unset it here and InnerLoopVectorizer
   // will create another.
   if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
     PrimaryInduction = nullptr;
 
   return true;
 }
 
+/// A helper function for checking whether an integer division-related
+/// instruction may divide by zero (in which case it must be predicated if
+/// executed conditionally in the scalar code).
+/// TODO: It may be worthwhile to generalize and check isKnownNonZero().
+/// Non-zero divisors that are non compile-time constants will not be
+/// converted into multiplication, so we will still end up scalarizing
+/// the division, but can do so w/o predication.
+static bool mayDivideByZero(Instruction &I) {
+  assert((I.getOpcode() == Instruction::UDiv ||
+          I.getOpcode() == Instruction::SDiv ||
+          I.getOpcode() == Instruction::URem ||
+          I.getOpcode() == Instruction::SRem) &&
+         "Unexpected instruction");
+  Value *Divisor = I.getOperand(1);
+  auto *CInt = dyn_cast<ConstantInt>(Divisor);
+  return !CInt || CInt->isZero();
+}
+
+bool LoopVectorizationLegality::canVectorizeWithPredication(
+    Instruction *I, bool VectorizeWithPredication) {
+  switch (I->getOpcode()) {
+  default:
+    break;
+  case Instruction::Load:
+  case Instruction::Store: {
+    // Some instructions can be speculated, even when predication is used
+    // for the block.
+    if (!isMaskRequired(I))
+      return true;
+
+    auto *Ptr = getLoadStorePointerOperand(I);
+    auto *Ty = getLoadStoreInstValueType(I);
+    const Align Alignment = getLoadStoreAlignment(I);
+    return isa<LoadInst>(I) ? ((isConsecutivePtr(Ptr) &&
+                                TTI->isLegalMaskedLoad(Ty, Alignment)) ||
+                               TTI->isLegalMaskedGather(Ty, Alignment))
+                            : ((isConsecutivePtr(Ptr) &&
+                                TTI->isLegalMaskedStore(Ty, Alignment)) ||
+                               TTI->isLegalMaskedScatter(Ty, Alignment));
+  }
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+  case Instruction::SRem:
+  case Instruction::URem:
+    // If predication is used for this block and the operation would otherwise
+    // be guarded, then this requires scalarizing.
+    if (blockNeedsPredication(I->getParent()) || VectorizeWithPredication)
+      return !mayDivideByZero(*I);
+  }
+  return true;
+}
+
 bool LoopVectorizationLegality::canVectorizeMemory() {
   LAI = &(*GetLAA)(*TheLoop);
   const OptimizationRemarkAnalysis *LAR = LAI->getReport();
   if (LAR) {
     ORE->emit([&]() {
       return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(),
                                         "loop not vectorized: ", *LAR);
     });
bool LoopVectorizationLegality::prepareToFoldTailByMasking() {
 
   MaskedOp.insert(TmpMaskedOp.begin(), TmpMaskedOp.end());
   ConditionalAssumes.insert(TmpConditionalAssumes.begin(),
                             TmpConditionalAssumes.end());
 
   return true;
 }
 
 } // namespace llvm

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 //===- LoopVectorize.cpp - A Loop Vectorizer ------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops
cl::opt<bool> llvm::EnableLoopVectorization(
     cl::desc("Run the Loop vectorization passes"));
 
 cl::opt<bool> PrintVPlansInDotFormat(
     "vplan-print-in-dot-format", cl::init(false), cl::Hidden,
     cl::desc("Use dot format instead of plain text when dumping VPlans"));
 
 /// A helper function that returns the type of loaded or stored value.
 static Type *getMemInstValueType(Value *I) {
-  assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
-         "Expected Load or Store instruction");
-  if (auto *LI = dyn_cast<LoadInst>(I))
-    return LI->getType();
-  return cast<StoreInst>(I)->getValueOperand()->getType();
+  return getLoadStoreInstValueType(I);
 }
 
 /// A helper function that returns true if the given type is irregular. The
 /// type is irregular if its allocated size doesn't equal the store size of an
 /// element of the corresponding vector type.
 static bool hasIrregularType(Type *Ty, const DataLayout &DL) {
   // Determine if an array of N elements of type Ty is "bitcast compatible"
   // with a <N x Ty> vector.
return (all_of(Legal->getReductionVars(), [&](auto &Reduction) -> bool {
       RecurrenceDescriptor RdxDesc = Reduction.second;
       return TTI.isLegalToVectorizeReduction(RdxDesc, VF);
     }));
   }
 
   /// Returns true if \p I is an instruction that will be scalarized with
   /// predication. Such instructions include conditional stores and
   /// instructions that may divide by zero.
-  /// If a non-zero VF has been calculated, we check if I will be scalarized
-  /// predication for that VF.
   bool
-  isScalarWithPredication(Instruction *I,
-                          ElementCount VF = ElementCount::getFixed(1)) const;
+  isScalarWithPredication(Instruction *I) const;
 
   // Returns true if \p I is an instruction that will be predicated either
   // through scalar predication or masked load/store or masked gather/scatter.
   // Superset of instructions that return true for isScalarWithPredication.
   bool isPredicatedInst(Instruction *I, ElementCount VF) {
-    if (!blockNeedsPredication(I->getParent()))
+    if (!Legal->blockNeedsPredication(I->getParent()) && !foldTailByMasking())
       return false;
     // Loads and stores that need some form of masked operation are predicated
     // instructions.
     if (isa<LoadInst>(I) || isa<StoreInst>(I))
       return Legal->isMaskRequired(I);
-    return isScalarWithPredication(I, VF);
+    return isScalarWithPredication(I);
   }
 
   /// Returns true if \p I is a memory instruction with consecutive memory
   /// access that can be widened.
   bool
   memoryInstructionCanBeWidened(Instruction *I,
                                 ElementCount VF = ElementCount::getFixed(1));
 
for (unsigned Part = 0; Part < State.UF; ++Part) {
               StartOffset, Builder.CreateVectorSplat(State.VF, ScalarStepValue),
               "vector.gep"));
       State.set(PhiR, GEP, Part);
     }
   }
   }
 }
 
-/// A helper function for checking whether an integer division-related
-/// instruction may divide by zero (in which case it must be predicated if
-/// executed conditionally in the scalar code).
-/// TODO: It may be worthwhile to generalize and check isKnownNonZero().
-/// Non-zero divisors that are non compile-time constants will not be
-/// converted into multiplication, so we will still end up scalarizing
-/// the division, but can do so w/o predication.
-static bool mayDivideByZero(Instruction &I) {
-  assert((I.getOpcode() == Instruction::UDiv ||
-          I.getOpcode() == Instruction::SDiv ||
-          I.getOpcode() == Instruction::URem ||
-          I.getOpcode() == Instruction::SRem) &&
-         "Unexpected instruction");
-  Value *Divisor = I.getOperand(1);
-  auto *CInt = dyn_cast<ConstantInt>(Divisor);
-  return !CInt || CInt->isZero();
-}
-
 void InnerLoopVectorizer::widenInstruction(Instruction &I, VPValue *Def,
                                            VPUser &User,
                                            VPTransformState &State) {
   switch (I.getOpcode()) {
   case Instruction::Call:
   case Instruction::Br:
   case Instruction::PHI:
   case Instruction::GetElementPtr:
for (auto &Induction : Legal->getInductionVars()) {
     LLVM_DEBUG(dbgs() << "LV: Found scalar instruction: " << *Ind << "\n");
     LLVM_DEBUG(dbgs() << "LV: Found scalar instruction: " << *IndUpdate
                       << "\n");
   }
 
   Scalars[VF].insert(Worklist.begin(), Worklist.end());
 }
 
 bool LoopVectorizationCostModel::isScalarWithPredication(
-    Instruction *I, ElementCount VF) const {
-  if (!blockNeedsPredication(I->getParent()))
-    return false;
-  switch(I->getOpcode()) {
-  default:
-    break;
-  case Instruction::Load:
-  case Instruction::Store: {
-    if (!Legal->isMaskRequired(I))
-      return false;
-    auto *Ptr = getLoadStorePointerOperand(I);
-    auto *Ty = getMemInstValueType(I);
-    // We have already decided how to vectorize this instruction, get that
-    // result.
-    if (VF.isVector()) {
-      InstWidening WideningDecision = getWideningDecision(I, VF);
-      assert(WideningDecision != CM_Unknown &&
-             "Widening decision should be ready at this moment");
-      return WideningDecision == CM_Scalarize;
-    }
-    const Align Alignment = getLoadStoreAlignment(I);
-    return isa<LoadInst>(I) ? !(isLegalMaskedLoad(Ty, Ptr, Alignment) ||
-                                isLegalMaskedGather(Ty, Alignment))
-                            : !(isLegalMaskedStore(Ty, Ptr, Alignment) ||
-                                isLegalMaskedScatter(Ty, Alignment));
-  }
-  case Instruction::UDiv:
-  case Instruction::SDiv:
-  case Instruction::SRem:
-  case Instruction::URem:
-    return mayDivideByZero(*I);
-  }
-  return false;
+    Instruction *I) const {
+  return !Legal->canVectorizeWithPredication(I, foldTailByMasking());
 }
 
 bool LoopVectorizationCostModel::interleavedAccessCanBeWidened(
     Instruction *I, ElementCount VF) {
   assert(isAccessInterleaved(I) && "Expecting interleaved access.");
   assert(getWideningDecision(I, VF) == CM_Unknown &&
          "Decision should not be set yet.");
   auto *Group = getInterleavedAccessGroup(I);
void LoopVectorizationCostModel::collectLoopUniforms(ElementCount VF) {
   // replicating region where only a single instance out of VF should be formed.
   // TODO: optimize such seldom cases if found important, see PR40816.
   auto addToWorklistIfAllowed = [&](Instruction *I) -> void {
     if (isOutOfScope(I)) {
       LLVM_DEBUG(dbgs() << "LV: Found not uniform due to scope: "
                         << *I << "\n");
       return;
     }
-    if (isScalarWithPredication(I, VF)) {
+    if (isScalarWithPredication(I)) {
       LLVM_DEBUG(dbgs() << "LV: Found not uniform being ScalarWithPredication: "
                         << *I << "\n");
       return;
     }
     LLVM_DEBUG(dbgs() << "LV: Found uniform instruction: " << *I << "\n");
     Worklist.insert(I);
   };
 
void LoopVectorizationCostModel::collectInstsToScalarize(ElementCount VF) {
   // not profitable to scalarize any instructions, the presence of VF in the
   // map will indicate that we've analyzed it already.
   ScalarCostsTy &ScalarCostsVF = InstsToScalarize[VF];
 
   // Find all the instructions that are scalar with predication in the loop and
   // determine if it would be better to not if-convert the blocks they are in.
   // If so, we also record the instructions to scalarize.
   for (BasicBlock *BB : TheLoop->blocks()) {
-    if (!blockNeedsPredication(BB))
+    if (!Legal->blockNeedsPredication(BB) && !foldTailByMasking())
       continue;
     for (Instruction &I : *BB)
       if (isScalarWithPredication(&I)) {
         ScalarCostsTy ScalarCosts;
         // Do not apply discount logic if hacked cost is needed
         // for emulated masked memrefs.
         if (!useEmulatedMaskMemRefHack(&I) &&
             computePredInstDiscount(&I, ScalarCosts, VF) >= 0)

 Optional<VectorizationFactor>
 LoopVectorizationPlanner::plan(ElementCount UserVF, unsigned UserIC) {
   assert(OrigLoop->isInnermost() && "Inner loop expected.");
   Optional<ElementCount> MaybeMaxVF = CM.computeMaxVF(UserVF, UserIC);
   if (!MaybeMaxVF) // Cases that should not to be vectorized nor interleaved.
     return None;
 
   // Invalidate interleave groups if all blocks of loop will be predicated.
-  if (CM.blockNeedsPredication(OrigLoop->getHeader()) &&
+  if ((Legal->blockNeedsPredication(OrigLoop->getHeader()) ||
+       CM.foldTailByMasking()) &&
       !useMaskedInterleavedAccesses(*TTI)) {
     LLVM_DEBUG(
         dbgs()
         << "LV: Invalidate all interleaved groups due to fold-tail by masking "
            "which requires masked-interleaved support.\n");
     if (CM.InterleaveInfo.invalidateGroups())
       // Invalidating interleave groups also requires invalidating all decisions
       // based on them, which includes widening decisions and uniform and scalar
VPValue *VPRecipeBuilder::createBlockInMask(BasicBlock *BB, VPlanPtr &Plan) {
   if (BCEntryIt != BlockMaskCache.end())
     return BCEntryIt->second;
 
   // All-one mask is modelled as no-mask following the convention for masked
   // load/store/gather/scatter. Initialize BlockMask to no-mask.
   VPValue *BlockMask = nullptr;
 
   if (OrigLoop->getHeader() == BB) {
-    if (!CM.blockNeedsPredication(BB))
+    if (!Legal->blockNeedsPredication(BB) && !CM.foldTailByMasking())
       return BlockMaskCache[BB] = BlockMask; // Loop incoming mask is all-one.
 
     // Create the block in mask as the first non-phi instruction in the block.
     VPBuilder::InsertPointGuard Guard(Builder);
     auto NewInsertionPoint = Builder.getInsertBlock()->getFirstNonPhi();
     Builder.setInsertPoint(Builder.getInsertBlock(), NewInsertionPoint);
 
     // Introduce the early-exit compare IV <= BTC to form header block mask.
VPRecipeOrVPValueTy VPRecipeBuilder::tryToBlend(PHINode *Phi,
   return toVPRecipeResult(new VPBlendRecipe(Phi, OperandsWithMask));
 }
 
 VPWidenCallRecipe *VPRecipeBuilder::tryToWidenCall(CallInst *CI,
                                                    ArrayRef<VPValue *> Operands,
                                                    VFRange &Range) const {
 
   bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
       [this, CI](ElementCount VF) {
-        return CM.isScalarWithPredication(CI, VF);
+        return CM.isScalarWithPredication(CI);
       },
       Range);
 
   if (IsPredicated)
     return nullptr;
 
   Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
   if (ID && (ID == Intrinsic::assume || ID == Intrinsic::lifetime_end ||

 
 bool VPRecipeBuilder::shouldWiden(Instruction *I, VFRange &Range) const {
   assert(!isa<BranchInst>(I) && !isa<PHINode>(I) && !isa<LoadInst>(I) &&
          !isa<StoreInst>(I) && "Instruction should have been handled earlier");
   // Instruction should be widened, unless it is scalar after vectorization,
   // scalarization is profitable or it is predicated.
   auto WillScalarize = [this, I](ElementCount VF) -> bool {
     return CM.isScalarAfterVectorization(I, VF) ||
            CM.isProfitableToScalarize(I, VF) ||
-           CM.isScalarWithPredication(I, VF);
+           CM.isScalarWithPredication(I);
   };
   return !LoopVectorizationPlanner::getDecisionAndClampRange(WillScalarize,
                                                              Range);
 }
 
 VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I,
                                            ArrayRef<VPValue *> Operands) const {
   auto IsVectorizableOpcode = [](unsigned Opcode) {