Replace overflow check in loop vectorization with minimum loop iterations check

[wmi]

Summary

llvm vectorizer will vectorize loop when loop iteration numbers are unknown. When the iteration number of a loop is very small and the preparation and rounding-off cost for vectorization is high, such vectorization may degrade performance, sometimes significantly. We find gcc vectorization generates runtime check to ensure loop iteration number is big enough before every vectorized loop.

Now llvm loop vectorizer generates overflow check before every vectorized loop. The overflow check is to check whether BackedgeCount equals to -1, .i.e ExitCount equals to 0. If the return of the check is true, jump to scalar remainder loop. This check can be covered by the minimum loop iterations check, because if overflow happens, the ExitCount number will be 0 and it will be less than the minimum loop iterations threshold.

This patch turns the original overflow check to a minimum loop iterations check, which has no change on correctness and runtime cost, and can be beneficial for performance in some cases.

[aschwaighofer]

This make sense to me.

Please add tests that this also works with interleave factor that is not 1.

Don't use MaxVectorSize but rather the selected unroll factor times the selected vectorization factor (InnerLoopVectorizer::UF * InnerLoopVectorizer::VF) this is the step the loop will iterate by.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

2538–2540

Please don't remove the explanation for the need of checking overflow.

I like your explanation in the review description. Please include an appropriate variant of that here as a comment.

[wmi]

Thanks for the quick response.

Please add tests that this also works with interleave factor that is not 1.

Done

Don't use MaxVectorSize but rather the selected unroll factor times the selected vectorization factor (InnerLoopVectorizer::UF * InnerLoopVectorizer::VF) this is the step the loop will iterate by.

Ah, that is right. Fixed.

Please don't remove the explanation for the need of checking overflow.

Done.

[anemet]

LGTM with some minor changes below.

Also did you see any change in performance?

lib/Transforms/Vectorize/LoopVectorize.cpp

2528–2536

The second paragraph is unnecessarily complicated. It should say something like this:

The minimum iteration check also covers case where the backedge-taken count is uint##_max. Adding one to it will cause overflow and an incorrect loop trip count being generated in the vector body. In this case we also want to directly jump to the scalar remainder loop.

test/Transforms/LoopVectorize/miniters.ll

12

You still have MaxVectorSize mentioned here.

[anemet]

FYI, James, I think you had a similar change in your series.

[wmi]

The second paragraph is unnecessarily complicated. It should say something like this:

Fixed.

You still have MaxVectorSize mentioned here.

Fixed.

did you see any change in performance?

I saw two testcases with perf change steadily:
MultiSource/Benchmarks/FreeBench/pcompress2 +2%
MultiSource/Benchmarks/Ptrdist/ks -15%

The improvement for the first test is caused by the minimum loop iterations check and perf stat shows its dynamic instruction number decreases.
The big regression for the second test is caused by a minor alignment change. The alignment change prevents a cmp and jmp pair inside the kernel loop of the test from being macro-fused, which increases uops-retired events a lot. So the regression is caused by the side-effect of the patch and may not exist after some other changes.

[anemet]

Ok. Thanks for the detailed analysis.

[jmolloy]

Hi,

We do actually already emit such a check - we just emit it late. This new check now makes the later check redundant, so we should remove it.

Cheers,

James

[wmi]

We do actually already emit such a check - we just emit it late. This new check now makes the later check redundant, so we should remove it.

Hi James,

Could you show me where is the check you mentioned? I didn't notice it before.

Thanks,
Wei.

lib/Transforms/Vectorize/LoopVectorize.cpp

    the vectorized instructions while the old loop will continue to run the
    scalar remainder.
 
-       [ ] <-- Back-edge taken count overflow check.
+       [ ] <-- loop iteration number check.
     /   |
    /    v
   |    [ ] <-- vector loop bypass (may consist of multiple blocks).

   // Notice that the pre-header does not change, only the loop body.
   SCEVExpander Exp(*SE, DL, "induction");
 
-  // We need to test whether the backedge-taken count is uint##_max. Adding one
-  // to it will cause overflow and an incorrect loop trip count in the vector
-  // body. In case of overflow we want to directly jump to the scalar remainder
-  // loop.
-  Value *BackedgeCount =
-      Exp.expandCodeFor(BackedgeTakeCount, BackedgeTakeCount->getType(),
-                        VectorPH->getTerminator());
-  if (BackedgeCount->getType()->isPointerTy())
-    BackedgeCount = CastInst::CreatePointerCast(BackedgeCount, IdxTy,
-                                                "backedge.ptrcnt.to.int",
-                                                VectorPH->getTerminator());
-  Instruction *CheckBCOverflow =
-      CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, BackedgeCount,
-                      Constant::getAllOnesValue(BackedgeCount->getType()),
-                      "backedge.overflow", VectorPH->getTerminator());
+  // The loop minimum iterations check below is to ensure the loop has enough
+  // trip count so the generated vector loop will likely be executed and the
+  // preparation and rounding-off costs will likely be worthy.
+  //
+  // The minimum iteration check also covers case where the backedge-taken
+  // count is uint##_max.  Adding one to it will cause overflow and an
+  // incorrect loop trip count being generated in the vector body. In this
+  // case we also want to directly jump to the scalar remainder loop.
+  Value *ExitCountValue = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
+                                            VectorPH->getTerminator());
+  if (ExitCountValue->getType()->isPointerTy())
+    ExitCountValue = CastInst::CreatePointerCast(ExitCountValue, IdxTy,
+                                                 "exitcount.ptrcnt.to.int",
+                                                 VectorPH->getTerminator());
+
+  Instruction *CheckMinIters =
+      CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, ExitCountValue,
+                      ConstantInt::get(ExitCountValue->getType(), VF * UF),
+                      "min.iters.check", VectorPH->getTerminator());
 
   // The loop index does not have to start at Zero. Find the original start
   // value from the induction PHI node. If we don't have an induction variable

   // times the unroll factor (num of SIMD instructions).
   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
 
-  // Generate code to check that the loop's trip count that we computed by
-  // adding one to the backedge-taken count will not overflow.
+  // Generate code to check that the loop's trip count is not less than the
+  // minimum loop iteration number threshold.
   BasicBlock *NewVectorPH =
-      VectorPH->splitBasicBlock(VectorPH->getTerminator(), "overflow.checked");
+      VectorPH->splitBasicBlock(VectorPH->getTerminator(), "min.iters.checked");
   if (ParentLoop)
     ParentLoop->addBasicBlockToLoop(NewVectorPH, *LI);
-  ReplaceInstWithInst(
-      VectorPH->getTerminator(),
-      BranchInst::Create(ScalarPH, NewVectorPH, CheckBCOverflow));
+  ReplaceInstWithInst(VectorPH->getTerminator(),
+                      BranchInst::Create(ScalarPH, NewVectorPH, CheckMinIters));
   VectorPH = NewVectorPH;
 
   // This is the IR builder that we use to add all of the logic for bypassing

test/Transforms/LoopVectorize/induction.ll

 ; condition and branch directly to the scalar loop.
 
 ; CHECK-LABEL: max_i32_backedgetaken
-; CHECK:  %backedge.overflow = icmp eq i32 -1, -1
-; CHECK:  br i1 %backedge.overflow, label %scalar.ph, label %overflow.checked
+; CHECK:  %min.iters.check = icmp ult i32 0, 2
+; CHECK:  br i1 %min.iters.check, label %scalar.ph, label %min.iters.checked
 
 ; CHECK: scalar.ph:
 ; CHECK:  %bc.resume.val = phi i32 [ %resume.val, %middle.block ], [ 0, %0 ]

test/Transforms/LoopVectorize/miniters.ll

+; RUN: opt %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -S | FileCheck %s
+; RUN: opt %s -loop-vectorize -force-vector-interleave=2 -force-vector-width=4 -S | FileCheck %s -check-prefix=UNROLL
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@b = common global [1000 x i32] zeroinitializer, align 16
+@c = common global [1000 x i32] zeroinitializer, align 16
+@a = common global [1000 x i32] zeroinitializer, align 16
+
+; Generate min.iters.check to skip the vector loop and jump to scalar.ph directly when loop iteration number is less than VF * UF.
+; CHECK-LABEL: foo(
+; CHECK: %min.iters.check = icmp ult i64 %N, 4
+; CHECK: br i1 %min.iters.check, label %scalar.ph, label %min.iters.checked
+; UNROLL-LABEL: foo(
+; UNROLL: %min.iters.check = icmp ult i64 %N, 8
+; UNROLL: br i1 %min.iters.check, label %scalar.ph, label %min.iters.checked
+
+define void @foo(i64 %N) {
+entry:
+  %cmp.8 = icmp sgt i64 %N, 0
+  br i1 %cmp.8, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.preheader
+  %i.09 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds [1000 x i32], [1000 x i32]* @b, i64 0, i64 %i.09
+  %tmp = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds [1000 x i32], [1000 x i32]* @c, i64 0, i64 %i.09
+  %tmp1 = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %tmp1, %tmp
+  %arrayidx2 = getelementptr inbounds [1000 x i32], [1000 x i32]* @a, i64 0, i64 %i.09
+  store i32 %add, i32* %arrayidx2, align 4
+  %inc = add nuw nsw i64 %i.09, 1
+  %exitcond = icmp eq i64 %inc, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}