[LV] Emit new IR intrinsic llvm.get.active.mask for tail-folded loops

[SjoerdMeijer]

Summary

Tail-predication is a new form of predication in MVE for vector loops that implicitely predicates the last vector loop iteration by implicitely setting active/inactive lanes, i.e. the tail loop is predicated. In order to set up a tail-predicated vector loop, we need to know the number of data elements processed by the vector loop, which corresponds the the tripcount of the scalar loop. We would like to propagate the scalar trip count to the backend, so that this can be picked up by the MVE tail-predication pass.

This implements the approach as discussed on the llvm de list, see Eli's comment in http://lists.llvm.org/pipermail/llvm-dev/2020-May/141360.html. The approach is based on emitting an intrinsic for deriving the mask. The vectoriser emits this new intrinsic in the vector preheader block when the new TII hook indicates that the target can lower this intrinsic and that it is desired to do so for this loop. For MVE, we do this when the loop is tail-folded, which is the very first step in tail-predicating a loop. For all the other targets, this intrinsic won't be emitted as the default of the hook is of course not to do this.

This change will be followed up by MVE specific changes to lower this intrinsics.

[SjoerdMeijer]

This is used in the ARM backend, in our tail-predication pass, see D79175.

[SjoerdMeijer]

added a test case, minor fixes in comments.

[SjoerdMeijer]

This was discussed on the list and implements the approach as suggested by @efriedma :

http://lists.llvm.org/pipermail/llvm-dev/2020-May/141360.html

I.e., we now emit a llvm.get.active.mask intrinsic into the vector body, which is used by the masked load/stores, and its operands allows to reconstruct to the required information in backend passes. For example, a relevant snippet of a vector body with the tail-folded looks like this:

%induction = add <4 x i64> %broadcast.splat, <i64 0, i64 1, i64 2, i64 3>
%[[PRED:.*]] = icmp ule <4 x i64> %induction, <i64 429, i64 429, i64 429, i64 429>
%[[MASK:.*]] = call <4 x i1> @llvm.get.active.mask.v4i1.v4i1(<4 x i1> %[[PRED]])
%[[WML1:.*]] = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32({{.*}}<4 x i1> %[[MASK]]
%[[WML2:.*]] = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32({{.*}}<4 x i1> %[[MASK]]

The induction and cmp feed the active.mask intrinsic, which is used by the masked loads/stores. This new intrinsic can now be easily picked up in backend passes, and the 429 in this example represents the backedge taken iteration count of the scalar loop, which we need to set up the tail-predication.

[samparker]

I was expecting the intrinsic to be performing the icmp because it feels as though if a target wants an intrinsic like this, that it would want it to do something?

[SjoerdMeijer]

In D79100#2041646, @samparker wrote:

I was expecting the intrinsic to be performing the icmp because it feels as though if a target wants an intrinsic like this, that it would want it to do something?

That was my initial though too, so started drafting an intrinsic that would take the induction step, backedge taken count, the comparison operator, thus replacing the icmp, and feeding its result into the masked load/stores.
This however, turned out to be a massively invasive change because of the different places where the induction variable is widened which creates the induction step and icmp, and where the masking happens. This change is very minimal, makes explicit exactly the same information, and thus had my preference.

[SjoerdMeijer]

In D79100#2041747, @SjoerdMeijer wrote:

In D79100#2041646, @samparker wrote:

I was expecting the intrinsic to be performing the icmp because it feels as though if a target wants an intrinsic like this, that it would want it to do something?

That was my initial though too, so started drafting an intrinsic that would take the induction step, backedge taken count, the comparison operator, thus replacing the icmp, and feeding its result into the masked load/stores.
This however, turned out to be a massively invasive change because of the different places where the induction variable is widened which creates the induction step and icmp, and where the masking happens. This change is very minimal, makes explicit exactly the same information, and thus had my preference.

Hmm, but thinking about it, after my initial attempt to do this I got some more VPlan plumbing experience, and I now see that I could try again and that that it is perhaps not very different. If it helps for acceptance, I can try this, but I think my previous points still stand that this change is minimal and leaves the IR intact.

[rogfer01]

Tail-predication is a new form of predication in MVE for vector loops that implicitely predicates the last vector loop iteration by implicitely setting active/inactive lanes, i.e. the tail loop is predicated. In order to set up a tail-predicated vector loop, we need to know the number of data elements processed by the vector loop, which corresponds the the tripcount of the scalar loop. We would like to propagate the scalar trip count to the backend, so that this can be picked up by the MVE tail-predication pass.

Just to make sure I understand: is this text still current? Your intrinsic does not seem to propagate the scalar trip count anymore (at least not explicitly). If I understand it correctly, now you communicate the active mask of the current vector iteration which you compute using i <= backedge taken-count. Did I get it right?

llvm/lib/Transforms/Vectorize/VPlan.cpp

386 ↗

(On Diff #264579)

Minor nit:

Here you use TC (as in trip count?) but above when you created this VPInstruction you used BTC (backedge taken count).

This might be confusing for a future reader so I'd suggest to stick to your own convention and use BTC here as well.

This code seems similar to that of VPRecipeBuilder::createBlockInMask (except that one creates the mask for a given block and this one creates a mask similar to the case OrigLoop->getHeader() == BB). That function uses BTC as well.

[efriedma]

What are the semantics of llvm.get.active.mask? I don't see an actual description anywhere beyond "it enables tail folding, somehow".

llvm/include/llvm/IR/Intrinsics.td

1419

I assume you meant to write LLVMMatchType<0>

[vkmr]

llvm/lib/Transforms/Vectorize/VPlan.cpp

389–392 ↗

(On Diff #264579)

Minor nit:

Probably cleaner to use Builder.CreateIntrinsic(Intrinsic::get_active_mask, { V->getType(), V->getType() }, {V}, nullptr, "active.mask");.

[vkmr]

llvm/lib/Transforms/Vectorize/VPlan.cpp

424–439 ↗

(On Diff #264579)

Add case VPInstruction::ActiveMask to print the correct VPInstruction when printing VPLan. You can pass the flag -debug-only=loop-vectorize to opt to see the generated VPlan.

[samparker]

That was my initial though too, so started drafting an intrinsic that would take the induction step, backedge taken count, the comparison operator

If the epilogue folding always uses ULE, then the operator wouldn't be needed. I think it would be really nice not to have the IV and upper limit splatted, plus we could remove the vector add on the IV too.

[SjoerdMeijer]

Thanks all for your comments! I think this addresses all comments:

• I did a rename of ActiveMask to ActiveLaneMask because that describes it better I think,
• The intrinsic now takes 2 arguments: the induction step, and the backedge taken count. It indeed represents the IV <= BTC comparison, thus giving it semantics rather than let it only pass on a value, which I have also clarified with comments at different places,
• The VP instruction is now lowered using Builder.CreateIntrinsic, and have added a case to print it.

[SjoerdMeijer]

llvm/include/llvm/IR/Intrinsics.td

1424

Ah, forgot to say that I am looking into LLVMMatchType<0>, this was giving me some problems. This is very minor, am looking into it, and in the mean time already wanted to show the important changes.

[lebedev.ri]

Semantics are still unspecified. Before adding even more intrinsics,
i'd strongly suggest to specify at least the already-committed ones.
Because as far as i can tell, i don't see anything in langref for any of them.

[SjoerdMeijer]

In D79100#2044165, @lebedev.ri wrote:

Semantics are still unspecified. Before adding even more intrinsics,
i'd strongly suggest to specify at least the already-committed ones.
Because as far as i can tell, i don't see anything in langref for any of them.

This was intentional. With the already-committed ones you mean the hardware loops ones, and they are not meant to be user-facing intrinsics. That is, we don't expect user to play around with e.g. the hwloop.decrement intrinsic; at least these are really meant to be generated by the optimisers.
This new intrinsic here is slightly different, in that it probably is useful as a user facing intrinsic, so don't mind documenting it.

[lebedev.ri]

In D79100#2044289, @SjoerdMeijer wrote:

In D79100#2044165, @lebedev.ri wrote:

Semantics are still unspecified. Before adding even more intrinsics,
i'd strongly suggest to specify at least the already-committed ones.
Because as far as i can tell, i don't see anything in langref for any of them.

This was intentional. With the already-committed ones you mean the hardware loops ones, and they are not meant to be user-facing intrinsics. That is, we don't expect user to play around with e.g. the hwloop.decrement intrinsic; at least these are really meant to be generated by the optimisers.
This new intrinsic here is slightly different, in that it probably is useful as a user facing intrinsic, so don't mind documenting it.

@SjoerdMeijer, i don't believe that is how langref works.

[SjoerdMeijer]

Ok, perhaps I got that wrong then. @samparker can correct me here perhaps, but as I said, for the hardware loop intrinsics I believe this was intentional. But anyway, as I said, will document this new one. As the hardware loop intrinsics are completely separate from this, I will do that separately.

[lebedev.ri]

In D79100#2044530, @SjoerdMeijer wrote:

Ok, perhaps I got that wrong then. @samparker can correct me here perhaps, but as I said, for the hardware loop intrinsics I believe this was intentional. But anyway, as I said, will document this new one. As the hardware loop intrinsics are completely separate from this, I will do that separately.

I think that would still be backwards.
langref is not documentation, it is specification.
To reword, langref is source of truth, not the code.

[SjoerdMeijer]

Understood, and we don't disagree, this will be fixed.

[SjoerdMeijer]

+ LangRef description

[efriedma]

llvm/docs/LangRef.rst

16198 ↗

(On Diff #265018)

Is this semantically equivalent to icmp ule? If it is, you should probably make that more clear, and explain that it's a hint to the backend. If not, this needs a much more thorough explanation.

llvm/include/llvm/IR/Intrinsics.td

1239

Is IntrNoDuplicate here actually semantically significant? The LangRef explanation doesn't really indicate why it needs to be noduplicate.

Please use LLVMMatchType/LLVMScalarOrSameVectorWidth to ensure the argument/result types match.

[SjoerdMeijer]

Thanks @efriedma : added a statement about the equivalence to the langref description, and fixed the intrinsic description.

[simoll]

In D79100#2041782, @SjoerdMeijer wrote:

In D79100#2041747, @SjoerdMeijer wrote:

In D79100#2041646, @samparker wrote:

I was expecting the intrinsic to be performing the icmp because it feels as though if a target wants an intrinsic like this, that it would want it to do something?

That was my initial though too, so started drafting an intrinsic that would take the induction step, backedge taken count, the comparison operator, thus replacing the icmp, and feeding its result into the masked load/stores.
This however, turned out to be a massively invasive change because of the different places where the induction variable is widened which creates the induction step and icmp, and where the masking happens. This change is very minimal, makes explicit exactly the same information, and thus had my preference.

Hmm, but thinking about it, after my initial attempt to do this I got some more VPlan plumbing experience, and I now see that I could try again and that that it is perhaps not very different. If it helps for acceptance, I can try this, but I think my previous points still stand that this change is minimal and leaves the IR intact.

The comparison really should be encapsulated in the intrinsic itself because for scalable types it is not clear how many bits the stepvector type needs to enumerate its lanes without overflow:

%lane_ids = <vscale x 1 x i8> llvm.stepvector() ; This will overflow if 'vscale > 256' at runtime (note that a 'stepvector' intrinsic does not even exist at this point)
%lane_mask = %ule icmp ule %lane_ids, (splat %n)

That is not a problem if you have

%lane_mask = <vscale x 1 x i1> llvm.active.mask(i32 0, i32 %n)

We need such an intrinsic anyway for the VP expansion pass to legalize the EVL parameter of VP intrinsics for targets that have scalable types but no active vector length (tail loop predication).

[SjoerdMeijer]

This patch, this new intrinsic, is a straightforward translation from an icmp. It provides the required information, and exactly the same as in your example, albeit in a slightly different form. Scalable vectors, stepvector intrinsics, etc., are not used yet by the vectoriser and are not yet defined, respectively, so using that at this point is problematic.

As this is such a straightforward translation, with straightforward semantics, this won't block in any way future developments. In fact, this is the first step in that direction, and it is good we get some experience with it. We offer our support to adapt this approach/intrinsic and port it, should this be necessary, which should be straightforward.

[efriedma]

I think all Simon is asking for is that the first argument of the intrinsic should be a scalar, equal to the first lane of the vector induction variable. How much work would that be?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6815

It would be nice to explicitly note here that we're assuming the vector factor is a power of two (so the induction variable can't wrap).

[SjoerdMeijer]

In D79100#2047545, @efriedma wrote:

I think all Simon is asking for is that the first argument of the intrinsic should be a scalar, equal to the first lane of the vector induction variable. How much work would that be?

Ah okay, sorry, I missed that. That should hopefully be straightforward, and if we have everyone on board with this, I will fix that right away tomorrow.

[SjoerdMeijer]

Uploading a new revision to see if we can reach a conclusion on this.

The intrinsic now takes two scalar arguments, the first element of the VIV, and the scalar BTC, hopefully in the way you head in mind.

On the dev list, Ayal pointed out an alternative to rediscover the BTC in the backend (still need spend time to confirm we then don't miss anything). This intrinsic still would have my preference because of its convenience, and as it a general concept it seems to support different uses too (vp intrinsicss, and provides a target independent way of describing the active mask).

[efriedma]

The intrinsic now takes two scalar arguments, the first element of the VIV, and the scalar BTC, hopefully in the way you head in mind.

Yes, this is what I expected.

On the dev list, Ayal pointed out an alternative to rediscover the BTC in the backend (still need spend time to confirm we then don't miss anything). This intrinsic still would have my preference because of its convenience, and as it a general concept it seems to support different uses too (vp intrinsicss, and provides a target independent way of describing the active mask).

In general, given two expressions that are equivalent, there's always some way to pattern-match. For power-of-two fixed-width vectors, the pattern you'd need to match is not that complicated (basically just an icmp where one operand is a vector induction variable, and the other operand is a splat.) But like you say, the intrinsic is more convenient.

If you're dealing with scalable vectors, expanding the intrinsic to arithmetic would result in a very complex expression due to the potential for overflow, so we'll almost certainly want this intrinsic.

---

The changes to VPlan.cpp look a little suspicious, but I'm not really familiar with that code, so I'll let someone else review it.

llvm/docs/LangRef.rst

16202 ↗

(On Diff #265969)

Maybe qualify this with the caveat that it's only equivalent if the vector induction variable doesn't overflow. We probably want to return false in the lanes where it overflows.

[SjoerdMeijer]

Thanks Eli for commenting and explaining.

I guess it was the TODO in VPlan.cpp that looked a bit suspicious. But there wasn't much going on here, that was very straightforward. so fixed that. I.e., Ayal added support for decrementing loops in VPlan recently. The Backedge Taken Count value looks slightly different for these cases, but extracting it is easy which I have added here. As a result, this now also triggers in test/Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll which I updated

[fhahn]

In D79100#2054437, @SjoerdMeijer wrote:

Thanks Eli for commenting and explaining.

I guess it was the TODO in VPlan.cpp that looked a bit suspicious. But there wasn't much going on here, that was very straightforward. so fixed that. I.e., Ayal added support for decrementing loops in VPlan recently. The Backedge Taken Count value looks slightly different for these cases, but extracting it is easy which I have added here. As a result, this now also triggers in test/Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll which I updated

I think introducing a VPInstruction opcode for the new intrinsic makes sense and fits in the current scheme. But I think there's no need to bundle the langref, TTI and LV changes into a single patch. IMO would be good to split at least the LV part off, to focus on discussing the implementation details in LV there.

[SjoerdMeijer]

Many thanks for taking a look Florian!

I think introducing a VPInstruction opcode for the new intrinsic makes sense and fits in the current scheme. But I think there's no need to bundle the langref, TTI and LV changes into a single patch. IMO would be good to split at least the LV part off, to focus on discussing the implementation details in LV there

Ok, but Just double checking that I get this right:

• In the LV part, we do use and check TTI.emitGetActiveLaneMask, so I guess that means we have LV + TTI in one patch,
• and separate we have LangRef.

That looks like a minimal change, but certainly don't mind doing this if that helps.

[fhahn]

In D79100#2055802, @SjoerdMeijer wrote:

Many thanks for taking a look Florian!

I think introducing a VPInstruction opcode for the new intrinsic makes sense and fits in the current scheme. But I think there's no need to bundle the langref, TTI and LV changes into a single patch. IMO would be good to split at least the LV part off, to focus on discussing the implementation details in LV there

Ok, but Just double checking that I get this right:

• In the LV part, we do use and check TTI.emitGetActiveLaneMask, so I guess that means we have LV + TTI in one patch,

I'd just put the LV parts in a separate patch and the TTI stuff in a different patch (the former depending on the latter). The way I see it, those are changes to 2 separate areas of the code, with potentially different people to approve. Also, if there's problem with the LV patch, It can be reverted in isolation.

[SjoerdMeijer]

Ok, thanks, sounds like a plan.

I will keep this as a reference, I think that's convenient, and will split off the different bits and pieces.
I have started with the easiest patch to create, the intrinsic description and documentation: D80596

[SjoerdMeijer]

I have just committed the required scaffolding for this:

• the new intrinsic in rG7fb8a40e5220
• the new TTI hook in rG7480ccbfc9d2

So was wondering if we are happy with this LV part too?

Just FYI, I am addressing comments on our backend support for this intrinsic in D79175. Once that is ready, I will commit this and D79175 at the same time.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

425 ↗

(On Diff #266369)

IIUC we want the first lanes of both the BTC and the IV, right?

If that's the case, I think it would be more straight-forward to just request the specific lane when looking up the values, .e.g something like:

// Get first lane of vector induction variable.
 Value *VIVE0 = State.get(getOperand(0), {Part, 0});
 // Get first lane of backedge-taken-count.
 Value *ScalarBTC = State.get(getOperand(1), {Part, 0});

 auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
 auto *PredTy = VectorType::get(Int1Ty, State.VF);
 Instruction *Call = Builder.CreateIntrinsic(
     Intrinsic::get_active_lane_mask, {PredTy, ScalarBTC->getType()},
     {VIVE0, ScalarBTC}, nullptr, "active.lane.mask");

 State.set(this, Call, Part);

This should have the advantage of re-using some scalar values, if they have been requested already by other recipes.

(Note: this currently crashes unfortunately, as getting lanes for defs managed by VPTransformState does not work, but I put up D80787 to fix that)

llvm/test/Transforms/LoopVectorize/ARM/tail-loop-folding.ll

79

We should also have a test where the unroll-factor/interleave-count > 1 with llvm.get.active.lane.mask (unless that's not possible at the moment)

[fhahn]

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

1313

Just return TailFolded?

side note: what are all the extra parameters needed/used somewhere?

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

1313

Just a quick first comment on your side note:

what are all the extra parameters needed/used somewhere?

That's just to provide an interface consistent with most other TTI functions here. Currently, we only look at TailFolded, the rest is indeed unused. But if (other) targets want to do a bit more analysis here, they most definitely want to look look at L and LI, and possibly SE.

So, as I said, mostly unused at the moment, and added for consistency, which I accept may or may not be a good reason. I have no strong opionions, so will refactor this TTI hook right away if you think that is better/necessary.

I will address your other remarks soon. Thanks for that.

[SjoerdMeijer]

IIUC we want the first lanes of both the BTC and the IV, right?

Yep, exactly that.

If that's the case, I think it would be more straight-forward to just request the specific lane when looking up the values, .e.g something like:
<SNIP>
This should have the advantage of re-using some scalar values, if they have been requested already by other recipes.

(Note: this currently crashes unfortunately, as getting lanes for defs managed by VPTransformState does not work, but I put up D80787 to fix that)

Thanks for that. I took D80787, and that worked like a charm, greatly simplifying things here: I have simplified lowering of VPInstruction::ActiveLaneMask as per your suggestion.

[SjoerdMeijer]

With D80787 committed, and this using that, does this look okay now?

[fhahn]

LGTM with the comment, thanks! Please wait a day or so with committing in case there are additional comments. Also, I might have missed it, but it would be good to have a test case with unroll-factor/interleave-count > 1 (as mentioned in an inline comment).

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

1313

I am not sure, but I think adding all those unused parameters, because they might get used in the future seems a bit odd. I would be easy enough to add them if required.

[SjoerdMeijer]

Many thanks for looking at this!

This needs to be committed together with the backend patch that adds support for lowering this intrinsic. That is nearly done (hopefully), and am expecting a commit somewhere next week, so will definitely wait a few days.

I will add that test case (sorry, I overlooked and missed that), and will follow up to reduce the arguments in the TTI hook.

[mkazantsev]

Hi, seems that this patch is causing some failures:
Failed Tests (2):

LLVM :: Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll
LLVM :: Transforms/LoopVectorize/ARM/tail-loop-folding.ll

[SjoerdMeijer]

I replied by mail, but just for completeness, I had noticed and reverted it, and now recommitted it.

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
 
   /// Query the target whether it would be prefered to create a predicated
   /// vector loop, which can avoid the need to emit a scalar epilogue loop.
   bool preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
                                    AssumptionCache &AC, TargetLibraryInfo *TLI,
                                    DominatorTree *DT,
                                    const LoopAccessInfo *LAI) const;
 
+  /// Query the target whether lowering of the llvm.set.loop.elements intrinsic
+  /// is supported and desired for this loop.
+  bool emitNumElementsVecLoop(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
+                              bool TailFolded) const;
+
   /// @}
 
   /// \name Scalar Target Information
   /// @{
 
   /// Flags indicating the kind of support for population count.
   ///
   /// Compared to the SW implementation, HW support is supposed to
public:
   virtual bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                         AssumptionCache &AC,
                                         TargetLibraryInfo *LibInfo,
                                         HardwareLoopInfo &HWLoopInfo) = 0;
   virtual bool
   preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
                               AssumptionCache &AC, TargetLibraryInfo *TLI,
                               DominatorTree *DT, const LoopAccessInfo *LAI) = 0;
+  virtual bool emitNumElementsVecLoop(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
+                                      bool TailFolded) = 0;
   virtual bool isLegalAddImmediate(int64_t Imm) = 0;
   virtual bool isLegalICmpImmediate(int64_t Imm) = 0;
   virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
                                      int64_t BaseOffset, bool HasBaseReg,
                                      int64_t Scale, unsigned AddrSpace,
                                      Instruction *I) = 0;
   virtual bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
                              TargetTransformInfo::LSRCost &C2) = 0;
bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
     return Impl.isHardwareLoopProfitable(L, SE, AC, LibInfo, HWLoopInfo);
   }
   bool preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
                                    AssumptionCache &AC, TargetLibraryInfo *TLI,
                                    DominatorTree *DT,
                                    const LoopAccessInfo *LAI) override {
     return Impl.preferPredicateOverEpilogue(L, LI, SE, AC, TLI, DT, LAI);
   }
+  bool emitNumElementsVecLoop(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
+                              bool TailFolded) override {
+    return Impl.emitNumElementsVecLoop(L, LI, SE, TailFolded);
+  }
   bool isLegalAddImmediate(int64_t Imm) override {
     return Impl.isLegalAddImmediate(Imm);
   }
   bool isLegalICmpImmediate(int64_t Imm) override {
     return Impl.isLegalICmpImmediate(Imm);
   }
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale, unsigned AddrSpace,

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   bool preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
                                    AssumptionCache &AC, TargetLibraryInfo *TLI,
                                    DominatorTree *DT,
                                    const LoopAccessInfo *LAI) const {
     return false;
   }
 
+  bool emitNumElementsVecLoop(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
+                              bool TailFold) const {
+    return false;
+  }
+
   void getUnrollingPreferences(Loop *, ScalarEvolution &,
                                TTI::UnrollingPreferences &) {}
 
   bool isLegalAddImmediate(int64_t Imm) { return false; }
 
   bool isLegalICmpImmediate(int64_t Imm) { return false; }
 
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,

llvm/include/llvm/CodeGen/BasicTTIImpl.h

public:
 
   bool preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
                                    AssumptionCache &AC, TargetLibraryInfo *TLI,
                                    DominatorTree *DT,
                                    const LoopAccessInfo *LAI) {
     return BaseT::preferPredicateOverEpilogue(L, LI, SE, AC, TLI, DT, LAI);
   }
 
+  bool emitNumElementsVecLoop(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
+                              bool TailFold) {
+    return BaseT::emitNumElementsVecLoop(L, LI, SE, TailFold);
+  }
+
   int getInstructionLatency(const Instruction *I) {
     if (isa<LoadInst>(I))
       return getST()->getSchedModel().DefaultLoadLatency;
 
     return BaseT::getInstructionLatency(I);
   }
 
   virtual Optional<unsigned>

llvm/include/llvm/IR/Intrinsics.td

def int_vp_xor : Intrinsic<[ llvm_anyvector_ty ],
                                LLVMMatchType<0>,
                                LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>,
                                llvm_i32_ty]>;
 
 }
 
 
 //===-------------------------- Masked Intrinsics -------------------------===//
 //
 def int_masked_store : Intrinsic<[], [llvm_anyvector_ty,
                                       LLVMAnyPointerType<LLVMMatchType<0>>,
                                       llvm_i32_ty,
                                       LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>],
                                  [IntrArgMemOnly, IntrWillReturn, ImmArg<2>]>;
 
 def int_masked_load  : Intrinsic<[llvm_anyvector_ty],
                                  [LLVMAnyPointerType<LLVMMatchType<0>>, llvm_i32_ty,

 
 //===---------- Intrinsics to control hardware supported loops ----------===//
 
 // Specify that the value given is the number of iterations that the next loop
 // will execute.
 def int_set_loop_iterations :
   Intrinsic<[], [llvm_anyint_ty], [IntrNoDuplicate]>;
 
+// Specify the number of elements processed by this (vector) loop, which
+// typically corresponds to the iteration count of the scalar loop.
+def int_set_loop_elements:
+  Intrinsic<[], [llvm_anyint_ty], [IntrNoDuplicate]>;
+
 // Specify that the value given is the number of iterations that the next loop
 // will execute. Also test that the given count is not zero, allowing it to
 // control entry to a 'while' loop.
 def int_test_set_loop_iterations :
   Intrinsic<[llvm_i1_ty], [llvm_anyint_ty], [IntrNoDuplicate]>;
 
 // Decrement loop counter by the given argument. Return false if the loop
 // should exit.
 def int_loop_decrement :
   Intrinsic<[llvm_i1_ty], [llvm_anyint_ty], [IntrNoDuplicate]>;
 
 // Decrement the first operand (the loop counter) by the second operand (the

llvm/lib/Analysis/TargetTransformInfo.cpp

 
 bool TargetTransformInfo::preferPredicateOverEpilogue(
     Loop *L, LoopInfo *LI, ScalarEvolution &SE, AssumptionCache &AC,
     TargetLibraryInfo *TLI, DominatorTree *DT,
     const LoopAccessInfo *LAI) const {
   return TTIImpl->preferPredicateOverEpilogue(L, LI, SE, AC, TLI, DT, LAI);
 }
 
+bool TargetTransformInfo::emitNumElementsVecLoop(Loop *L, LoopInfo *LI,
+    ScalarEvolution &SE, bool TailFolded) const {
+  return TTIImpl->emitNumElementsVecLoop(L, LI, SE, TailFolded);
+}
+
 void TargetTransformInfo::getUnrollingPreferences(
     Loop *L, ScalarEvolution &SE, UnrollingPreferences &UP) const {
   return TTIImpl->getUnrollingPreferences(L, SE, UP);
 }
 
 bool TargetTransformInfo::isLegalAddImmediate(int64_t Imm) const {
   return TTIImpl->isLegalAddImmediate(Imm);
 }

llvm/lib/Target/ARM/ARMTargetTransformInfo.h

bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 TargetLibraryInfo *LibInfo,
                                 HardwareLoopInfo &HWLoopInfo);
   bool preferPredicateOverEpilogue(Loop *L, LoopInfo *LI,
                                    ScalarEvolution &SE,
                                    AssumptionCache &AC,
                                    TargetLibraryInfo *TLI,
                                    DominatorTree *DT,
                                    const LoopAccessInfo *LAI);
+
   void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                TTI::UnrollingPreferences &UP);
 
+  bool emitNumElementsVecLoop(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
+                              bool TailFolded) const;
+
   bool shouldBuildLookupTablesForConstant(Constant *C) const {
     // In the ROPI and RWPI relocation models we can't have pointers to global
     // variables or functions in constant data, so don't convert switches to
     // lookup tables if any of the values would need relocation.
     if (ST->isROPI() || ST->isRWPI())
       return !C->needsRelocation();
 
     return true;
   }
   /// @}
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_ARM_ARMTARGETTRANSFORMINFO_H

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

if (!HWLoopInfo.isHardwareLoopCandidate(SE, *LI, *DT)) {
     LLVM_DEBUG(dbgs() << "preferPredicateOverEpilogue: hardware-loop is not "
                          "a candidate.\n");
     return false;
   }
 
   return canTailPredicateLoop(L, LI, SE, DL, LAI);
 }
 
-
+bool ARMTTIImpl::emitNumElementsVecLoop(Loop *L, LoopInfo *LI,
+    ScalarEvolution &SE, bool TailFolded) const {
+  // If this loop is tail-folded, we always want to to emit the
+  // llvm.set.loop.elements intrinsic, so that this can be picked up in the
+  // MVETailPredication pass that needs to know the number of elements
+  // processed by this vector loop.
+  if (TailFolded)
+    return true;
+  return false;
+}
 void ARMTTIImpl::getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                          TTI::UnrollingPreferences &UP) {
   // Only currently enable these preferences for M-Class cores.
   if (!ST->isMClass())
     return BasicTTIImplBase::getUnrollingPreferences(L, SE, UP);
 
   // Disable loop unrolling for Oz and Os.
   UP.OptSizeThreshold = 0;

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
 
   /// Emit a bypass check to see if all of the SCEV assumptions we've
   /// had to make are correct.
   void emitSCEVChecks(Loop *L, BasicBlock *Bypass);
 
   /// Emit bypass checks to check any memory assumptions we may have made.
   void emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass);
 
+  /// Emit the llvm.set.loop.elements IR intrinsic that models the number of
+  /// data elements processed by the vector loop.
+  void emitNumElementsVecLoop(BasicBlock *Bypass, Value *Count);
+
   /// Compute the transformed value of Index at offset StartValue using step
   /// StepValue.
   /// For integer induction, returns StartValue + Index * StepValue.
   /// For pointer induction, returns StartValue[Index * StepValue].
   /// FIXME: The newly created binary instructions should contain nsw/nuw
   /// flags, which can be found from the original scalar operations.
   Value *emitTransformedIndex(IRBuilder<> &B, Value *Index, ScalarEvolution *SE,
                               const DataLayout &DL,
void InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass) {
 
   // We currently don't use LoopVersioning for the actual loop cloning but we
   // still use it to add the noalias metadata.
   LVer = std::make_unique<LoopVersioning>(*Legal->getLAI(), OrigLoop, LI, DT,
                                           PSE.getSE());
   LVer->prepareNoAliasMetadata();
 }
 
+void InnerLoopVectorizer::emitNumElementsVecLoop(BasicBlock *Bypass,
+                                                 Value *Count) {
+  if (EnableVPlanNativePath)
+    return;
+
+  if (!TTI->emitNumElementsVecLoop(OrigLoop, LI, *PSE.getSE(),
+                                   Cost->foldTailByMasking()))
+    return;
+
+  IRBuilder<> Builder(Bypass->getTerminator());
+  Function *NumElems = Intrinsic::getDeclaration(
+      Bypass->getParent()->getParent(), Intrinsic::set_loop_elements,
+      Count->getType());
+  Builder.CreateCall(NumElems, Count);
+}
+
 Value *InnerLoopVectorizer::emitTransformedIndex(
     IRBuilder<> &B, Value *Index, ScalarEvolution *SE, const DataLayout &DL,
     const InductionDescriptor &ID) const {
 
   SCEVExpander Exp(*SE, DL, "induction");
   auto Step = ID.getStep();
   auto StartValue = ID.getStartValue();
   assert(Index->getType() == Step->getType() &&
BasicBlock *InnerLoopVectorizer::createVectorizedLoopSkeleton() {
   // expressions.
   emitSCEVChecks(Lp, LoopScalarPreHeader);
 
   // Generate the code that checks in runtime if arrays overlap. We put the
   // checks into a separate block to make the more common case of few elements
   // faster.
   emitMemRuntimeChecks(Lp, LoopScalarPreHeader);
 
+  // Emit an intrinsic in the vector preheader that represents the number
+  // of data elements processed by the vector loop, which corresponds to
+  // the tripcount of the scalar loop. This queries TTI to check that this
+  // intrinsic is supported by the target.
+  emitNumElementsVecLoop(LoopVectorPreHeader, Count);
+
   // Generate the induction variable.
   // The loop step is equal to the vectorization factor (num of SIMD elements)
   // times the unroll factor (num of SIMD instructions).
   Value *CountRoundDown = getOrCreateVectorTripCount(Lp);
   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
   Induction =
       createInductionVariable(Lp, StartIdx, CountRoundDown, Step,
                               getDebugLocFromInstOrOperands(OldInduction));
VPValue *VPRecipeBuilder::createBlockInMask(BasicBlock *BB, VPlanPtr &Plan) {
   // load/store/gather/scatter. Initialize BlockMask to no-mask.
   VPValue *BlockMask = nullptr;
 
   if (OrigLoop->getHeader() == BB) {
     if (!CM.blockNeedsPredication(BB))
       return BlockMaskCache[BB] = BlockMask; // Loop incoming mask is all-one.
 
     // Introduce the early-exit compare IV <= BTC to form header block mask.
     // This is used instead of IV < TC because TC may wrap, unlike BTC.
     // Start by constructing the desired canonical IV.
     VPValue *IV = nullptr;
     if (Legal->getPrimaryInduction())
       IV = Plan->getVPValue(Legal->getPrimaryInduction());
     else {
       auto IVRecipe = new VPWidenCanonicalIVRecipe();
       Builder.getInsertBlock()->appendRecipe(IVRecipe);
       IV = IVRecipe->getVPValue();

llvm/test/Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll

 ; RUN: opt < %s -loop-vectorize -S | FileCheck %s --check-prefixes=COMMON,DEFAULT
 ; RUN: opt < %s -loop-vectorize -prefer-predicate-over-epilog -S | FileCheck %s --check-prefixes=COMMON,CHECK-TF,CHECK-PREFER
 ; RUN: opt < %s -loop-vectorize -disable-mve-tail-predication=false -S | FileCheck %s --check-prefixes=COMMON,CHECK-TF,CHECK-ENABLE-TP
 
 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "thumbv8.1m.main-arm-unknown-eabihf"
 
 ; This IR corresponds to this type of C-code:
 ;
 ;  void f(char *a, char *b, char *c, int N) {
 ;    while (N-- > 0)
 ;      *c++ = *a++ + *b++;
 ;  }
 ;
 define dso_local void @sgt_loopguard(i8* noalias nocapture readonly %a, i8* noalias nocapture readonly %b, i8* noalias nocapture %c, i32 %N) local_unnamed_addr #0 {
 ; COMMON-LABEL: @sgt_loopguard(
+; CHECK-TF:      %[[TC:.*]] = sub i32 %0, %[[SMIN:.*]]
+; CHECK-TF:       br i1 false, label %scalar.ph, label %vector.ph
+; CHECK-TF:     vector.ph:
+; CHECK-TF:       call void @llvm.set.loop.elements.i32(i32 %[[TC]])
 ; COMMON:       vector.body:
 ; CHECK-TF:     masked.load
 ; CHECK-TF:     masked.load
 ; CHECK-TF:     masked.store
 entry:
   %cmp5 = icmp sgt i32 %N, 0
   br i1 %cmp5, label %while.body.preheader, label %while.end
 

llvm/test/Transforms/LoopVectorize/ARM/tail-loop-folding.ll

 ; RUN: opt < %s -loop-vectorize -S | \
 ; RUN:  FileCheck %s -check-prefixes=COMMON,CHECK
 
 ; RUN: opt < %s -loop-vectorize -prefer-predicate-over-epilog -S | \
 ; RUN:   FileCheck -check-prefixes=COMMON,PREDFLAG %s
 
 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "thumbv8.1m.main-arm-unknown-eabihf"
 
 define dso_local void @tail_folding(i32* noalias nocapture %A, i32* noalias nocapture readonly %B, i32* noalias nocapture readonly %C) #0 {
 ; CHECK-LABEL: tail_folding(
 ; CHECK: vector.body:
-;
-; This needs implementation of TTI::preferPredicateOverEpilogue,
-; then this will be tail-folded too:
-;
+; CHECK-NOT:  call void @llvm.set.loop.elements
 ; CHECK-NOT:  call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(
 ; CHECK-NOT:  call void @llvm.masked.store.v4i32.p0v4i32(
 ; CHECK:      br i1 %{{.*}}, label %{{.*}}, label %vector.body
 entry:
   br label %for.body
 
 for.cond.cleanup:
   ret void
for.body:
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %exitcond = icmp eq i64 %indvars.iv.next, 430
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
 
 define dso_local void @tail_folding_enabled(i32* noalias nocapture %A, i32* noalias nocapture readonly %B, i32* noalias nocapture readonly %C) local_unnamed_addr #0 {
 ; COMMON-LABEL: tail_folding_enabled(
+; COMMON: vector.ph:
+; COMMON:   call void @llvm.set.loop.elements.i64(i64 430)
+; COMMON:   br label %vector.body
 ; COMMON: vector.body:
 ; COMMON:   %[[WML1:.*]] = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(
 ; COMMON:   %[[WML2:.*]] = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(
 ; COMMON:   %[[ADD:.*]] = add nsw <4 x i32> %[[WML2]], %[[WML1]]
 ; COMMON:   call void @llvm.masked.store.v4i32.p0v4i32(<4 x i32> %[[ADD]]
 ; COMMON:   br i1 %12, label %{{.*}}, label %vector.body
 entry:
   br label %for.body

 ; CHECK:      vector.body:
 ; CHECK-NOT:  @llvm.masked.load.v8i32.p0v8i32(
 ; CHECK-NOT:  @llvm.masked.store.v8i32.p0v8i32(
 ; CHECK:      br i1 %{{.*}}, label {{.*}}, label %vector.body
 
 ; PREDFLAG-LABEL: tail_folding_disabled(
 ; PREDFLAG:  vector.body:
 ; PREDFLAG:  %wide.masked.load = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(
 ; PREDFLAG:  %wide.masked.load1 = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(
 ; PREDFLAG:  %{{.*}} = add nsw <4 x i32> %wide.masked.load1, %wide.masked.load
 ; PREDFLAG:  call void @llvm.masked.store.v4i32.p0v4i32(
 ; PREDFLAG:  %index.next = add i64 %index, 4
 ; PREDFLAG:  %12 = icmp eq i64 %index.next, 432
 ; PREDFLAG:  br i1 %{{.*}}, label %middle.block, label %vector.body, !llvm.loop !6
 entry:
   br label %for.body