[LV] Fix bug when unrolling (only) a loop with non-latch exit

[reames]

Summary

If we unroll a loop in the vectorizer (without vectorizing), and the cost model requires a epilogue be generated for correctness, the code generation must actually do so.

The included test case on an unmodified opt will access memory one past the expected bound.

I believe this to be the root cause of the issues seen with 3e5ce49e, but even if it isn't, it's definitely a bug.

[lebedev.ri]

llvm/test/Transforms/LoopVectorize/unroll_nonlatch.ll

2

I don't think bug-reduced.ll is correct here

[reames]

llvm/test/Transforms/LoopVectorize/unroll_nonlatch.ll

2

Er, oops. No. I'm surprised the autoupdate worked with that typo. That should be %s.

[reames]

Fix silly typo in test.

[nemanjai]

We will be happy to test this on both our LE and BE systems. @stefanp do you have time to test this out or should I do it?

[reames]

In D103700#2799338, @nemanjai wrote:

We will be happy to test this on both our LE and BE systems. @stefanp do you have time to test this out or should I do it?

Seems like overkill for this one given the change is trivial and the test is target independent.

I'd save that for when I go to reapply the original patch that exposed this.

[nemanjai]

In D103700#2799340, @reames wrote:

In D103700#2799338, @nemanjai wrote:

We will be happy to test this on both our LE and BE systems. @stefanp do you have time to test this out or should I do it?

Seems like overkill for this one given the change is trivial and the test is target independent.

I'd save that for when I go to reapply the original patch that exposed this.

Oh, sorry. I meant to say that we'd test with this patch and the reverted one applied together.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3190

What if a loop has a single exiting block - the loop latch, and an interleave group that requires a scalar epilog, but we decide to unroll the loop w/o vectorizing it? Such a (test)case should be unrolled w/o a scalar epilog.

Note that InterleaveInfo.requiresScalarEpilogue() is relevant only when vectorizing but is otherwise independent of VF, so should force a scalar epilog in conjunction with the original "if (VF > 1)" of D19487. Exiting from a non-latch block, OTOH, as introduced in D93317, should force a scalar epilog for any VF, including 1.

Also curious if D94892 should be applicable to epilog vectorization, as commented there.

[stefanp]

In D103700#2799532, @nemanjai wrote:

In D103700#2799340, @reames wrote:

In D103700#2799338, @nemanjai wrote:

We will be happy to test this on both our LE and BE systems. @stefanp do you have time to test this out or should I do it?

Seems like overkill for this one given the change is trivial and the test is target independent.

I'd save that for when I go to reapply the original patch that exposed this.

Oh, sorry. I meant to say that we'd test with this patch and the reverted one applied together.

I added both patches and I did a quick test on the Big Endian Power PC buildbot machine.
This patch does seem to fix the original issue. However, after adding the two patches I have 4 new LIT test failues:

LLVM :: Transforms/LoopVectorize/first-order-recurrence-complex.ll
LLVM :: Transforms/LoopVectorize/loop-form.ll
LLVM :: Transforms/LoopVectorize/multiple-exits-versioning.ll
LLVM :: Transforms/LoopVectorize/unroll_nonlatch.ll

[reames]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3190

What if a loop has a single exiting block - the loop latch, and an interleave group that requires a scalar epilog, but we decide to unroll the loop w/o vectorizing it? Such a (test)case should be unrolled w/o a scalar epilog.

We could reasonably decide that such a loop does not require a scalar epilogue, but if the cost model decides it does (as it might today), code generation had better be consistent about it. That's all this patch does.

Note that InterleaveInfo.requiresScalarEpilogue() is relevant only when vectorizing but is otherwise independent of VF, so should force a scalar epilog in conjunction with the original "if (VF > 1)" of D19487. Exiting from a non-latch block, OTOH, as introduced in D93317, should force a scalar epilog for any VF, including 1.

I don't follow your comment here. As demonstrated by the test case, we do need to generate an epilogue loop in some cases even when not vectorizing.

Also curious if D94892 should be applicable to epilog vectorization, as commented there.

(will reply there)

[reames]

In D103700#2802779, @stefanp wrote:

In D103700#2799532, @nemanjai wrote:

In D103700#2799340, @reames wrote:

In D103700#2799338, @nemanjai wrote:

We will be happy to test this on both our LE and BE systems. @stefanp do you have time to test this out or should I do it?

Seems like overkill for this one given the change is trivial and the test is target independent.

I'd save that for when I go to reapply the original patch that exposed this.

Oh, sorry. I meant to say that we'd test with this patch and the reverted one applied together.

I added both patches and I did a quick test on the Big Endian Power PC buildbot machine.
This patch does seem to fix the original issue. However, after adding the two patches I have 4 new LIT test failues:

LLVM :: Transforms/LoopVectorize/first-order-recurrence-complex.ll
LLVM :: Transforms/LoopVectorize/loop-form.ll
LLVM :: Transforms/LoopVectorize/multiple-exits-versioning.ll
LLVM :: Transforms/LoopVectorize/unroll_nonlatch.ll

The original patch would definitely need rebased over changed tests, so that's not surprising.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3190

What if a loop has a single exiting block - the loop latch, and an interleave group that requires a scalar epilog, but we decide to unroll the loop w/o vectorizing it? Such a (test)case should be unrolled w/o a scalar epilog.

We could reasonably decide that such a loop does not require a scalar epilogue, but if the cost model decides it does (as it might today), code generation had better be consistent about it. That's all this patch does.

We do decide rightfully that such a loop does not require a scalar epilogue today; this patch causes it
to have a scalar epilogue.
Take for example test case even_load_static_tc from interleaved-accesses.ll, where instead of "-force-vector-width=4 -force-vector-interleave=1" (which requires an epilog) we run it with "-force-vector-width=1 -force-vector-interleave=4" (which does not require an epilog).

Note that InterleaveInfo.requiresScalarEpilogue() is relevant only when vectorizing but is otherwise independent of VF, so should force a scalar epilog in conjunction with the original "if (VF > 1)" of D19487. Exiting from a non-latch block, OTOH, as introduced in D93317, should force a scalar epilog for any VF, including 1.

I don't follow your comment here. As demonstrated by the test case, we do need to generate an epilogue loop in some cases even when not vectorizing.

Sorry if the comment is unclear. The logic for forcing a scalar epilog should conceptually be

((getExitingBlock() != getLoopLatch()) ||
 (VF.isVector() && InterleaveInfo.requiresScalarEpilogue()))

, right?
Asserting that isScalarEpilogueAllowed() holds if the above condition is true: because if an epilog is not allowed, Legal should have prevented vectoring a loop with a non-latch exiting block, and interleave groups requiring epilog should not have been formed.

To have Cost->requiresScalarEpilogue() fully convey this logic, one could directly pass it VF or VF.isVector(); or reset InterleaveInfo's requiresScalarEpilogue earlier when VF is set to 1, e.g., by invalidating all its groups.

[reames]

@Ayal If I'm understanding you even partially correctly, it sounds like you're raising a code quality issue. That is, we may generate a dead epilogue loop (e.g. with a condition statically known to result in the epilogue being untaken, but emitted as a condition) when we didn't need to. Is that correct?

If so, I request that we land this patch - which is fixing a functional bug - and handle the code quality issue in a separate patch.

I really don't understand the interweaving code, and would really rather not have to. :)

[gilr]

In D103700#2813906, @reames wrote:

@Ayal If I'm understanding you even partially correctly, it sounds like you're raising a code quality issue. That is, we may generate a dead epilogue loop (e.g. with a condition statically known to result in the epilogue being untaken, but emitted as a condition) when we didn't need to. Is that correct?

No, the emitted code in this case would be explicitly leaving some iterations to the epilogue even if the trip count is a multiple of the unroll factor. So the epilogue is alive and will not be optimized away later.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1576

To have Cost->requiresScalarEpilogue() fully convey this logic, one could directly pass it VF

That seems like the simplest way to both fix the bug and avoid pessimizing the unroll-only case, i.e.:

return VF.isVector() && InterleaveInfo.requiresScalarEpilogue();

[reames]

Attempt to incorporate review feedback.

@Ayal, @gilr - I still don't understand your comments on the review. I think this was what you were asking for (right?), and it doesn't seem to do any harm, but I'm not sure why you think this was needed for correctness. That doesn't seem to match the code. If this was not what you had in mind, can I ask you to simply fix the bug proven by the test case yourself? We don't appear to be making progress here in terms of me understanding the point you're getting at.

[reames]

(include full test diff as opposed to diff from last revision)

[Ayal]

This was indeed what was suggested, thanks for following up! The patch correctly fixes the bug raised by the test case, right? I.e., the last iteration of the "vector" (unrolled) loop is peeled into UF(*VF) iterations of the scalar epilog.
While keeping even_load_static_tc test case of interleaved-accesses.ll without this peeling, when run with "-force-vector-width=1 -force-vector-interleave=4"; unlike the original patch. Suggest to include this test case "run" in the patch.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8321–8322

"VF" should be "ForEpilogue ? EPI.EpilogueVF : VF" here, judging from VFactor above.

8465–8466

"VF" should be EPI.EpilogueVF here.

[reames]

In D103700#2839620, @Ayal wrote:

This was indeed what was suggested, thanks for following up! The patch correctly fixes the bug raised by the test case, right? I.e., the last iteration of the "vector" (unrolled) loop is peeled into UF(*VF) iterations of the scalar epilog.
While keeping even_load_static_tc test case of interleaved-accesses.ll without this peeling, when run with "-force-vector-width=1 -force-vector-interleave=4"; unlike the original patch. Suggest to include this test case "run" in the patch.

@Ayal - I'm sorry, but I'm having a really hard time understanding you.

To restate, the correctness issue this is fixing is that the "vectorized" (really unrolled) loop in the test case was running more iterations than the original loop. It did this because different parts of the vectorizer disagreed about whether a scalar epilogue loop was required. That disagreement is the bug being fixed. There is no change in peeling policy intended or desired. This is a fix for a miscompile, nothing more.

@Ayal - I don't feel that we are making useful progress on this review. You seem to have a very specific view of how you want this fixed, and that is not translating well for me. Instead of continuing to waste both our times, can I ask you to fix the bug yourself? At the moment, I feel we're both wasting time on this conversation.

[Ayal]

In D103700#2841557, @reames wrote:

In D103700#2839620, @Ayal wrote:

This was indeed what was suggested, thanks for following up! The patch correctly fixes the bug raised by the test case, right? I.e., the last iteration of the "vector" (unrolled) loop is peeled into UF(*VF) iterations of the scalar epilog.
While keeping even_load_static_tc test case of interleaved-accesses.ll without this peeling, when run with "-force-vector-width=1 -force-vector-interleave=4"; unlike the original patch. Suggest to include this test case "run" in the patch.

@Ayal - I'm sorry, but I'm having a really hard time understanding you.

To restate, the correctness issue this is fixing is that the "vectorized" (really unrolled) loop in the test case was running more iterations than the original loop. It did this because different parts of the vectorizer disagreed about whether a scalar epilogue loop was required. That disagreement is the bug being fixed. There is no change in peeling policy intended or desired. This is a fix for a miscompile, nothing more.

@Ayal - I don't feel that we are making useful progress on this review. You seem to have a very specific view of how you want this fixed, and that is not translating well for me. Instead of continuing to waste both our times, can I ask you to fix the bug yourself? At the moment, I feel we're both wasting time on this conversation.

@reames, your patch is practically ready to land, it just needs Epilog vectorizer to pass the correct VF as noted; do we agree?
The suggestion to include an extra test case can be ignored, if desired.

[reames]

Address review comment. Additionally rebase over landed test, don't know why I didn't land that a while ago.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// Get the interleaved access group that \p Instr belongs to.
   const InterleaveGroup<Instruction> *
   getInterleavedAccessGroup(Instruction *Instr) {
     return InterleaveInfo.getInterleaveGroup(Instr);
   }
 
   /// Returns true if we're required to use a scalar epilogue for at least
   /// the final iteration of the original loop.
-  bool requiresScalarEpilogue() const {
+  bool requiresScalarEpilogue(ElementCount VF) const {
     if (!isScalarEpilogueAllowed())
       return false;
     // If we might exit from anywhere but the latch, must run the exiting
     // iteration in scalar form.
     if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch())
       return true;
-    return InterleaveInfo.requiresScalarEpilogue();
+    return VF.isVector() && InterleaveInfo.requiresScalarEpilogue();
   }
 
   /// Returns true if a scalar epilogue is not allowed due to optsize or a
   /// loop hint annotation.
   bool isScalarEpilogueAllowed() const {
     return ScalarEpilogueStatus == CM_ScalarEpilogueAllowed;
   }
 
Value *InnerLoopVectorizer::getOrCreateVectorTripCount(Loop *L) {
 
   // Now we need to generate the expression for the part of the loop that the
   // vectorized body will execute. This is equal to N - (N % Step) if scalar
   // iterations are not required for correctness, or N - Step, otherwise. Step
   // is equal to the vectorization factor (number of SIMD elements) times the
   // unroll factor (number of SIMD instructions).
   Value *R = Builder.CreateURem(TC, Step, "n.mod.vf");
 
-  // There are two cases where we need to ensure (at least) the last iteration
-  // runs in the scalar remainder loop. Thus, if the step evenly divides
-  // the trip count, we set the remainder to be equal to the step. If the step
-  // does not evenly divide the trip count, no adjustment is necessary since
-  // there will already be scalar iterations. Note that the minimum iterations
-  // check ensures that N >= Step. The cases are:
-  // 1) If there is a non-reversed interleaved group that may speculatively
-  //    access memory out-of-bounds.
-  // 2) If any instruction may follow a conditionally taken exit. That is, if
-  //    the loop contains multiple exiting blocks, or a single exiting block
-  //    which is not the latch.
-  if (VF.isVector() && Cost->requiresScalarEpilogue()) {
+  // There are cases where we *must* run at least one iteration in the remainder
+  // loop.  See the cost model for when this can happen.  If the step evenly
+  // divides the trip count, we set the remainder to be equal to the step. If
+  // the step does not evenly divide the trip count, no adjustment is necessary
+  // since there will already be scalar iterations. Note that the minimum
+  // iterations check ensures that N >= Step.
+  if (Cost->requiresScalarEpilogue(VF)) {
     auto *IsZero = Builder.CreateICmpEQ(R, ConstantInt::get(R->getType(), 0));
     R = Builder.CreateSelect(IsZero, Step, R);
   }
 
   VectorTripCount = Builder.CreateSub(TC, R, "n.vec");
 
   return VectorTripCount;
 }
void InnerLoopVectorizer::emitMinimumIterationCountCheck(Loop *L,
   BasicBlock *const TCCheckBlock = LoopVectorPreHeader;
   IRBuilder<> Builder(TCCheckBlock->getTerminator());
 
   // Generate code to check if the loop's trip count is less than VF * UF, or
   // equal to it in case a scalar epilogue is required; this implies that the
   // vector trip count is zero. This check also covers the case where adding one
   // to the backedge-taken count overflowed leading to an incorrect trip count
   // of zero. In this case we will also jump to the scalar loop.
-  auto P = Cost->requiresScalarEpilogue() ? ICmpInst::ICMP_ULE
+  auto P = Cost->requiresScalarEpilogue(VF) ? ICmpInst::ICMP_ULE
                                             : ICmpInst::ICMP_ULT;
 
   // If tail is to be folded, vector loop takes care of all iterations.
   Value *CheckMinIters = Builder.getFalse();
   if (!Cost->foldTailByMasking()) {
     Value *Step =
         createStepForVF(Builder, ConstantInt::get(Count->getType(), UF), VF);
     CheckMinIters = Builder.CreateICmp(P, Count, Step, "min.iters.check");
   }
BasicBlock *EpilogueVectorizerMainLoop::emitMinimumIterationCountCheck(
   Value *Count = getOrCreateTripCount(L);
   // Reuse existing vector loop preheader for TC checks.
   // Note that new preheader block is generated for vector loop.
   BasicBlock *const TCCheckBlock = LoopVectorPreHeader;
   IRBuilder<> Builder(TCCheckBlock->getTerminator());
 
   // Generate code to check if the loop's trip count is less than VF * UF of the
   // main vector loop.
-  auto P =
-      Cost->requiresScalarEpilogue() ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
+  auto P = Cost->requiresScalarEpilogue(ForEpilogue ? EPI.EpilogueVF : VF) ?
+      ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
 
   Value *CheckMinIters = Builder.CreateICmp(
       P, Count, ConstantInt::get(Count->getType(), VFactor * UFactor),
       "min.iters.check");
 
   if (!ForEpilogue)
     TCCheckBlock->setName("vector.main.loop.iter.check");
 
assert(
        DT->dominates(cast<Instruction>(EPI.TripCount)->getParent(), Insert)) &&
       "saved trip count does not dominate insertion point.");
   Value *TC = EPI.TripCount;
   IRBuilder<> Builder(Insert->getTerminator());
   Value *Count = Builder.CreateSub(TC, EPI.VectorTripCount, "n.vec.remaining");
 
   // Generate code to check if the loop's trip count is less than VF * UF of the
   // vector epilogue loop.
-  auto P =
-      Cost->requiresScalarEpilogue() ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
+  auto P = Cost->requiresScalarEpilogue(EPI.EpilogueVF) ?
+      ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
 
   Value *CheckMinIters = Builder.CreateICmp(
       P, Count,
       ConstantInt::get(Count->getType(),
                        EPI.EpilogueVF.getKnownMinValue() * EPI.EpilogueUF),
       "min.epilog.iters.check");
 
   ReplaceInstWithInst(

llvm/test/Transforms/LoopVectorize/unroll_nonlatch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -S -loop-vectorize -force-vector-interleave=2 | FileCheck %s
 
 ; Demonstrate a case where we unroll a loop, but don't vectorize it.
-; This currently reveals a miscompile.  The original loop runs stores in
-; the latch block on iterations 0 to 1022, and exits when %indvars.iv = 1023.
-; Currently, the unrolled loop produced by the vectorizer runs the iteration
-; where %indvar.iv = 1023 in the vector.body loop before exiting.  This results
-; in an out of bounds access..
+; The original loop runs stores in the latch block on iterations 0 to 1022,
+; and exits when %indvars.iv = 1023. (That is, it actually runs the stores
+; for an odd number of iterations.)  If we unroll by two in the "vector.body"
+; loop, we must exit to the epilogue on iteration with %indvars.iv = 1022 to
+; avoid an out of bounds access.
 
 define void @test(double* %data) {
 ; CHECK-LABEL: @test(
 ; 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:    [[TMP0:%.*]] = shl nuw nsw i64 [[INDUCTION]], 1
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[INDUCTION1]], 1
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i64 [[TMP0]], 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP1]], 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds double, double* [[DATA:%.*]], i64 [[TMP2]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds double, double* [[DATA]], i64 [[TMP3]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = load double, double* [[TMP4]], align 8
 ; CHECK-NEXT:    [[TMP7:%.*]] = load double, double* [[TMP5]], align 8
 ; CHECK-NEXT:    [[TMP8:%.*]] = fneg double [[TMP6]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = fneg double [[TMP7]]
 ; CHECK-NEXT:    store double [[TMP8]], double* [[TMP4]], align 8
 ; CHECK-NEXT:    store double [[TMP9]], double* [[TMP5]], align 8
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2
-; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1024
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1022
 ; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1024, 1024
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1024, 1022
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
-; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 1024, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 1022, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 1024
 ; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_END]], label [[FOR_LATCH]]
 ; CHECK:       for.latch:
 ; CHECK-NEXT:    [[T15:%.*]] = shl nuw nsw i64 [[INDVARS_IV]], 1