[LV] Handle Fold-Tail of loops with vectorizarion factor (VF) equal to 1

[anhtuyen]

Summary

When handling loops whose VF is 1, fold-tail vectorization sets the backedge taken count of the original loop with a vector of a single element. This approach will cause type-mismatch during instruction generartion, as reported in https://reviews.llvm.org/D78847#2029339

Based on discussion with Ayal @Ayal , I provide this patch to address the case of VF==1.

[Ayal]

Thanks for taking care of this, only a couple of nits.

llvm/lib/Transforms/Vectorize/VPlan.cpp

444

nit: using auto VF = State->VF will help shorten this to 2 lines.

820

nit: can move VF = State.VF to be reused above and below.

822

nit: ConstantInt::get(STy, Part) was already pushed inside Indices, can retrieve it e.g. via Indices.back().

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

3

Would be good to explain what this test is for; e.g., that fold-tail produces correct scalar code when LV is only unrolling w/o vectorizing.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-vector.ll

3

Better have both tests in the same file, briefly explain what this tests - possibly using an informative function name rather than "foo".

[bmahjour]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

How is it that the original loop executes 15 iterations, but the vector loop iterates 16? It seems the minimum iteration count check branch at the top should branch to the scalar loop instead of vector.ph.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-vector.ll

37

Can the undef values be replaced with some valid values (such as an incoming parameter)?

[Ayal]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

15

continue CHECK-NEXTing the scalar icmp ule's

17

(Thanks for asking, reminded to check above and below that fold-tail emits the desired scalar icmp ule's, which are the focus of this patch.)

Fold-tail is responsible for rounding-up the trip count from 15 to 16, see https://reviews.llvm.org/D50480.
Regarding minimum iteration count check branch, fold-tail is also responsible in general for branching directly to vector.ph w/o an "if (trip-count < VF*UF)", which in this case is known to be false anyhow.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-vector.ll

23

continue CHECK-NEXTing the scalar icmp ule's

[anhtuyen]

llvm/lib/Transforms/Vectorize/VPlan.cpp

444

I will update it shortly.

820

I will update it shortly.

822

I will update it shortly.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

3

I will update it shortly.

15

Good catch! I will add them.

17

Ayal @Ayal , thank you very much for your help to clarify. My guess is that Bardia @bmahjour might have been concerned whether by any chance the effective addition of the 16th iteration would affect the correctness of the generated code. Because I have neither evidence nor counterevidence to address his concern, if you can shed some light on it when you have some time, that will be great.

Back to this patch but given the fact that the value of the trip-count is not the main focus hereof, I take the liberty of omitting its value from the checks. If that is not acceptable to any of us here, please let me know.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-vector.ll

3

I will update it shortly.

23

I will update it shortly.

37

I will update it shortly.

[bmahjour]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

I guess I would understand how the rounding-up would work, if the instructions in the body were somehow predicated, but I don't see any predication in the output IR. Is that because there are no instructions in this test case with side-effects, read/writes, etc?

[anhtuyen]

This patch includes all the changes recommended by the reviewers - thank you very much!
I also added a new LIT test, which uses the ORE to confirm which pass has the impact.
In terms of testing, I have run a number of test-cases with it, and all were successful.

[fhahn]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

yes, this would probably need some actual instructions in the loop body, so there is something to predicate. @anhtuyen could you add a small vectorizable body, e.g. just storing to ptr+induction?

[fhahn]

The issue has also been reported as https://bugs.llvm.org/show_bug.cgi?id=45943

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

111 ↗

(On Diff #264443)

metadata here and below unused?

[anhtuyen]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

I will add it later tonight.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

111 ↗

(On Diff #264443)

Hi Florian @fhahn, The short answer is yes, we need it.
As you can see on https://reviews.llvm.org/D78847, it is simple to create a minimal reproducer asserting when going through function VPlan::execute(). It is, however, a bit tricky to craft a minimal LIT test which exhibits the same problem when going through the other function VPWidenCanonicalIVRecipe::execute(). I came up with an idea to use profile data for the function online 57

define void @vectorize-factor-1-vector-bound(double* %pt1) !prof !12 {

to guide it through VPWidenCanonicalIVRecipe::execute(). Although I made the data up. I am sure almost any meaningful values will serve the purpose.

[anhtuyen]

In D79976#2040304, @fhahn wrote:

The issue has also been reported as https://bugs.llvm.org/show_bug.cgi?id=45943

Thank you @fhahn for linking the bug report to this patch.
I have requested a password reset from Bugzilla since earlier last week to open a bug report, but I still have not received any thing from the server.

[anhtuyen]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

111 ↗

(On Diff #264443)

I have just found simple way to alter the 2nd function in this LIT test so that it still goes through VPWidenCanonicalIVRecipe::execute() even without the meta data. The new test-case is also clearer. I will upload the new patch shortly.

[anhtuyen]

Similar to the 2nd patch earlier, this patch includes all the changes recommended by the reviewers.
Also, I

• modified the 2nd function of the LIT test to make it clearer and simpler, and
• added ORE to confirm which pass has/does not have the impact.

[anhtuyen]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

Hi Florian @fhahn, This is testcase, which I modified along the way you had suggested. It has a trip count of 15. However, I cannot make it go through Fold-Tail.

define void @foo(double* %paramP) {
entry:
  %localP = getelementptr inbounds double, double* %paramP, i64 15
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %addr = phi double* [ %indP, %for.body ], [ %paramP, %entry ]
  %indP = getelementptr inbounds double, double* %addr, i64 1
  %cond = icmp eq double* %indP, %localP
  store double 3.14, double* %indP              ;<======== I added this line
  br i1 %cond, label %for.cond.cleanup, label %for.body
}

Do you have some hints, which I could use ?

[Ayal]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

However, I cannot make it go through Fold-Tail.

That is due to bug in Fold-Tail, namely PR45679, which should be fixed by D80085. Specifically, using only type double on default target leads to internally computed MaxVF=1.
The test added in D80085, pr45679-fold-tail-by-masking.ll, should be extended by this patch to also handle VF=1, UF=4 case.

[anhtuyen]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

17

Ah, thank you! Please let me know if there any thing else you like me to further in this patch. Monday May 18 will be a statutory holiday in Canada, and I will be away, but I will respond the following day.

[anhtuyen]

Hello,
I write to ask if there is any thing else in this patch you like me to address. If not, please see if you could approve it. A number of testcases I am running are affected and it will be great if I can get them pass with this patch. Thank you very much!

[Ayal]

This looks good to me, thanks! Please wait a day or so if @fhahn has further comments.

As noted, it would now be good to also extend pr45679-fold-tail-by-masking.ll with an additional RUN of -force-vector-width=1 and -force-vector-interleave=4.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

107 ↗

(On Diff #264468)

Interesting; this test w/o a primary IV seems to work ok w/o the patch; comparing pairs of vectors of size 1...

[anhtuyen]

In D79976#2045007, @Ayal wrote:

This looks good to me, thanks! Please wait a day or so if @fhahn has further comments.

As noted, it would now be good to also extend pr45679-fold-tail-by-masking.ll with an additional RUN of -force-vector-width=1 and -force-vector-interleave=4.

It is very kind of you, Ayal @Ayal , and I thank you very much. As you have mentioned, I surely will wait a day or two to see whether Florian and Bardia might have further comments.
About pr45679-fold-tail-by-masking.ll, do you want me to add it for completeness?
With VF=1, the testcase does not go through the code changed by this patch (b/c its BackedgeTakenCount is null).

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

107 ↗

(On Diff #264468)

Yes, this test should pass without this patch b/c it compares a pair of vectors size 1. When we decided to replace VTCMO with TCMO when State->VF == 1, we also updated VPWidenCanonicalIVRecipe::execute() , and it now compares two scalars. Did I mis-understand your above comment about its interesting-ness?

[anhtuyen]

In D79976#2045738, @anhtuyen wrote:

In D79976#2045007, @Ayal wrote:

This looks good to me, thanks! Please wait a day or so if @fhahn has further comments.

As noted, it would now be good to also extend pr45679-fold-tail-by-masking.ll with an additional RUN of -force-vector-width=1 and -force-vector-interleave=4.

It is very kind of you, Ayal @Ayal , and I thank you very much. As you have mentioned, I surely will wait a day or two to see whether Florian and Bardia might have further comments.
About pr45679-fold-tail-by-masking.ll, do you want me to add it for completeness?
With VF=1, the testcase does not go through the code changed by this patch (b/c its BackedgeTakenCount is null).

Oh, I think I know what you meant now: adding the test pr45679-fold-tail-by-masking.ll AFTER applying your patch https://reviews.llvm.org/D80085. I will do.

[anhtuyen]

Extend pr45679-fold-tail-by-masking.ll with an additional RUN of -force-vector-width=1 and -force-vector-interleave=4 from https://reviews.llvm.org/D80085.

[Ayal]

In D79976#2045766, @anhtuyen wrote:

In D79976#2045738, @anhtuyen wrote:

In D79976#2045007, @Ayal wrote:

This looks good to me, thanks! Please wait a day or so if @fhahn has further comments.

As noted, it would now be good to also extend pr45679-fold-tail-by-masking.ll with an additional RUN of -force-vector-width=1 and -force-vector-interleave=4.

It is very kind of you, Ayal @Ayal , and I thank you very much. As you have mentioned, I surely will wait a day or two to see whether Florian and Bardia might have further comments.
About pr45679-fold-tail-by-masking.ll, do you want me to add it for completeness?
With VF=1, the testcase does not go through the code changed by this patch (b/c its BackedgeTakenCount is null).

Oh, I think I know what you meant now: adding the test pr45679-fold-tail-by-masking.ll AFTER applying your patch https://reviews.llvm.org/D80085. I will do.

Yes, thanks.
Sorry for the confusion; before D80085 this test generated wrong code with VF=1, afterwards the compiler crashes, with this patch it generates correct code.

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

107 ↗

(On Diff #264468)

Right. Just noted that the original motivation was to fix crashing cases, and this test shows it also helps to improve correct code cases.

[Ayal]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

114 ↗

(On Diff #265735)

Ah, suffice to add to pr45679-fold-tail-by-masking.ll a RUN of -force-vector-width=1 -force-vector-interleave=4 along with its CHECK-VF1's, instead of replicating test @pr45679 here. Note that all (3) tests here will be compiled by all (3) RUNs, some w/o any corresponding CHECK's.

[anhtuyen]

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1.ll

114 ↗

(On Diff #265735)

Thanks Ayal @Ayal for pointing this out. I will move it with patch https://reviews.llvm.org/D80446
I thought the test was to address Bardia's and Florian's comments about needing "some actual instructions in the loop body, so there is something to predicate", so I added it to the test in this patch. I then only CHECK-ed for details of interest and thus omitted those covered by the other CHECKs.

llvm/lib/Transforms/Vectorize/VPlan.cpp

 /// basic-blocks as needed, and fill them all.
 void VPlan::execute(VPTransformState *State) {
   // -1. Check if the backedge taken count is needed, and if so build it.
   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
     Value *TC = State->TripCount;
     IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
     auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
                                    "trip.count.minus.1");
-    Value *VTCMO = Builder.CreateVectorSplat(State->VF, TCMO, "broadcast");
+    Value *VTCMO = State->VF == 1 ? TCMO
+                                  : Builder.CreateVectorSplat(State->VF, TCMO,
+                                                              "broadcast");
     for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
       State->set(BackedgeTakenCount, VTCMO, Part);
   }
 
   // 0. Set the reverse mapping from VPValues to Values for code generation.
   for (auto &Entry : Value2VPValue)
     State->VPValue2Value[Entry.second] = Entry.first;
 
if (Mask) {
     Mask->printAsOperand(O, SlotTracker);
   }
 }
 
 void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
   Value *CanonicalIV = State.CanonicalIV;
   Type *STy = CanonicalIV->getType();
   IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
-  Value *VStart = Builder.CreateVectorSplat(State.VF, CanonicalIV, "broadcast");
+  Value *VStart =
+      State.VF == 1
+          ? CanonicalIV
+          : Builder.CreateVectorSplat(State.VF, CanonicalIV, "broadcast");
   for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
     SmallVector<Constant *, 8> Indices;
     for (unsigned Lane = 0, VF = State.VF; Lane < VF; ++Lane)
       Indices.push_back(ConstantInt::get(STy, Part * VF + Lane));
-    Constant *VStep = ConstantVector::get(Indices);
+    Constant *VStep = State.VF == 1 ? ConstantInt::get(STy, Part)
+                                    : ConstantVector::get(Indices);
     // Add the consecutive indices to the vector value.
     Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
     State.set(getVPValue(), CanonicalVectorIV, Part);
   }
 }
 
 void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
                                      VPSlotTracker &SlotTracker) const {

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-scalar.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s  -loop-vectorize -force-vector-interleave=4 -S | FileCheck %s
+
+define void @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[INDUCTION:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[INDUCTION1:%.*]] = add i64 [[INDEX]], 1
+; CHECK-NEXT:    [[INDUCTION2:%.*]] = add i64 [[INDEX]], 2
+; CHECK-NEXT:    [[INDUCTION3:%.*]] = add i64 [[INDEX]], 3
+; CHECK:         [[INDEX_NEXT]] = add i64 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[INDEX_NEXT]], 16
+; CHECK-NEXT:    br i1 [[TMP4]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
+; CHECK:       middle.block:
+; CHECK-NEXT:    br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 16, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 15
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], !llvm.loop !2
+;
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 15
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}

llvm/test/Transforms/LoopVectorize/tail-folding-vectorization-factor-1-vector.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s  -loop-vectorize -force-vector-interleave=4 -S | FileCheck %s
+
+define void @foo() !prof !12 {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[NEXT_GEP:%.*]] = getelementptr double, double* undef, i64 [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[INDEX]], 1
+; CHECK-NEXT:    [[NEXT_GEP1:%.*]] = getelementptr double, double* undef, i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[INDEX]], 2
+; CHECK-NEXT:    [[NEXT_GEP2:%.*]] = getelementptr double, double* undef, i64 [[TMP2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = add i64 [[INDEX]], 3
+; CHECK-NEXT:    [[NEXT_GEP3:%.*]] = getelementptr double, double* undef, i64 [[TMP3]]
+; CHECK-NEXT:    [[VEC_IV:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[VEC_IV4:%.*]] = add i64 [[INDEX]], 1
+; CHECK-NEXT:    [[VEC_IV5:%.*]] = add i64 [[INDEX]], 2
+; CHECK-NEXT:    [[VEC_IV6:%.*]] = add i64 [[INDEX]], 3
+; CHECK:         [[INDEX_NEXT]] = add i64 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], {{[0-9]*}}
+; CHECK-NEXT:    br i1 [[TMP8]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !13
+; CHECK:       middle.block:
+; CHECK-NEXT:    br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi double* [ undef, [[MIDDLE_BLOCK]] ], [ undef, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[ADDR:%.*]] = phi double* [ [[PTR:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
+; CHECK-NEXT:    [[PTR]] = getelementptr inbounds double, double* [[ADDR]], i64 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq double* [[PTR]], undef
+; CHECK-NEXT:    br i1 [[COND]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], !llvm.loop !15
+;
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %addr = phi double* [ %ptr, %for.body ], [ undef, %entry ]
+  %ptr = getelementptr inbounds double, double* %addr, i64 1
+  %cond = icmp eq double* %ptr, undef
+  br i1 %cond, label %for.cond.cleanup, label %for.body
+}
+
+!llvm.module.flags = !{!0}
+
+!0 = !{i32 1, !"ProfileSummary", !1}
+!1 = !{!2, !3, !4, !5, !6, !7, !8, !9}
+!2 = !{!"ProfileFormat", !"InstrProf"}
+!3 = !{!"TotalCount", i64 10}
+!4 = !{!"MaxCount", i64 20}
+!5 = !{!"MaxInternalCount", i64 30}
+!6 = !{!"MaxFunctionCount", i64 40}
+!7 = !{!"NumCounts", i64 50}
+!8 = !{!"NumFunctions", i64 60}
+!9 = !{!"DetailedSummary", !10}
+!10 = !{!11}
+!11 = !{i32 999999, i64 70, i32 80}
+!12 = !{!"function_entry_count", i64 0}