[Unroll] Do NOT unroll a loop with small runtime upperbound

[zzheng]

Summary

For a runtime loop if we can compute its trip count upperbound:

Don't unroll if:

1. loop is not guaranteed to run either zero or upperbound iterations; and
2. trip count upperbound is less than UnrollMaxUpperBound

Unless user or TTI asked to do so.

If unrolling, limit unroll factor to loop's trip count upperbound.

[fhahn]

Could you please re-upload the patch with more context (https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface)?

[zzheng]

Re-upload patch with full context.

[Meinersbur]

What problem is this solving?

test/Transforms/LoopUnroll/runtime-small-upperbound.ll

30–32

Is it necessary ro have the store from/to the global here? Without it, you could could just

CHECK: store
CHECK-NOT: store

[zzheng]

define dso_local void @hoge_3(i8 %arg) {
entry:
  %x = load i32, i32* @global, align 4
  %y = load i8*, i8** @global.1, align 4
  %0 = icmp ult i32 %x, 17
  br i1 %0, label %loop, label %exit

loop:
  %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ]
  %ptr = phi i8* [ %y, %entry ], [ %ptr.next, %loop ]
  %iv.next = add nuw i32 %iv, 8
  %ptr.next = getelementptr inbounds i8, i8* %ptr, i32 1
  store i8 %arg, i8* %ptr.next, align 1
  %1 = icmp ult i32 %iv.next, 17
  br i1 %1, label %loop, label %exit

exit:
  ret void
}

This loop has a runtime trip count upper bound of 3.

It's NOT guaranteed this loop will run either 0 or 3 iterations, so computeUnrollCount() chooses not to full-unroll it since icmp and br in each duplicated loop body cannot be removed.

computeUnrollCount() then decides to unroll it by 8 (runtime unrolling). But the unrolled loop will never execute, wasting code size, and runtime check.

If user/TTI really want it unrolled, we need to limit unroll factor by the upper bound.

[zzheng]

In D62989#1534692, @Meinersbur wrote:

What problem is this solving?

Unwanted (or excessive) unrolling of loops with small runtime trip count upper bound.

[Meinersbur]

In D62989#1534884, @zzheng wrote:

Unwanted (or excessive) unrolling of loops with small runtime trip count upper bound.

Wouldn't I want to (fully) unroll loops especially those with low trip count to reduce overhead/enable further optimizations?

Do you have performance/code size numbers?

[zzheng]

Wouldn't I want to (fully) unroll loops especially those with low trip count to reduce overhead/enable further optimizations?

Do you have performance/code size numbers?

The overhead of loop exit check will not be reduced after full unroll:

// Try to find the trip count upper bound if we cannot find the exact trip
// count.
bool MaxOrZero = false;
if (!TripCount) {
  MaxTripCount = SE.getSmallConstantMaxTripCount(L);
  MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
  // We can unroll by the upper bound amount if it's generally allowed or if
  // we know that the loop is executed either the upper bound or zero times.
  // (MaxOrZero unrolling keeps only the first loop test, so the number of
  // loop tests remains the same compared to the non-unrolled version, whereas
  // the generic upper bound unrolling keeps all but the last loop test so the
  // number of loop tests goes up which may end up being worse on targets with
  // constrained branch predictor resources so is controlled by an option.)
  // In addition we only unroll small upper bounds.
  if (!(UP.UpperBound || MaxOrZero) || MaxTripCount > UnrollMaxUpperBound) {
    MaxTripCount = 0;
  }
}

This loop was found from an internal workload, unrolling it impact performance negatively.

[hfinkel]

lib/Transforms/Scalar/LoopUnrollPass.cpp

795

Did you make this new variable so that you could apply this !(UP.UpperBound || MaxOrZero) || UnrollByMaxCount > UnrollMaxUpperBound condition only to full-unrolling case and not to the partial unrolling case?

1097

Why did this move down here?

[zzheng]

lib/Transforms/Scalar/LoopUnrollPass.cpp

795

No, new variable UnrollByMaxCount replaces use of MaxTripCount in full-unrolling case.

We only full-unroll a runtime loop by its upper bound if MaxOrZero is true; otherwise runtime unrolling will handle it, sometimes unroll more than MaxTripCount. Runtime unrolling needs to know MaxTripCount, so we cannot set it to zero here.

https://reviews.llvm.org/D63064 is trying to solve the same problem for ARM target.

I'm confuse why this relevant to partial unrolling, which only applies to known TripCount. We only calculate MaxTripCount and MaxOrZero if TripCount is 0.

1097

To move it close to use, like MaxOrZero.

[hfinkel]

lib/Transforms/Scalar/LoopUnrollPass.cpp

795

I'm confuse why this relevant to partial unrolling, which only applies to known TripCount. We only calculate MaxTripCount and MaxOrZero if TripCount is 0.

I asked because the following conditional is added in this patch (before the pre-existing debug output), which seems to apply MaxTripCount to limit partial unrolling (at least if the debug output below the conditional is accurate). Maybe the debug output should say runtime unrolling?

if (MaxTripCount && UP.Count > MaxTripCount)
  UP.Count = MaxTripCount;

LLVM_DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count
                  << "\n");

new variable UnrollByMaxCount replaces use of MaxTripCount in full-unrolling case.

Okay. If UnrollByMaxCount is only used during full unrolling, then can we name it FullUnrollMaxCount, or similar, to make that clear?

[zzheng]

Renamed UnrollByMaxCount to FullUnrollMaxTripCount, note this is not to be confused with member variable UP.FullUnrollMaxCount.
Changed debug output to accurately reflect partial or runtime unrolling.

[zzheng]

ping?

[zzheng]

ping...

[efriedma]

ping

[hfinkel]

LGTM

lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

168

Can you please add a comment here next to false so that it is clear what this is

/*MaxOrZero*/ false

include/llvm/Transforms/Utils/UnrollLoop.h

                         DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
                         const SmallPtrSetImpl<const Value *> &EphValues,
                         OptimizationRemarkEmitter *ORE, unsigned &TripCount,
-                        unsigned MaxTripCount, unsigned &TripMultiple,
-                        unsigned LoopSize,
+                        unsigned MaxTripCount, bool MaxOrZero,
+                        unsigned &TripMultiple, unsigned LoopSize,
                         TargetTransformInfo::UnrollingPreferences &UP,
                         bool &UseUpperBound);
 

lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

   unsigned MaxTripCount = 0;
   bool UseUpperBound = false;
   bool ExplicitUnroll = computeUnrollCount(
-      L, TTI, DT, LI, SE, EphValues, ORE, OuterTripCount, MaxTripCount,
+      L, TTI, DT, LI, SE, EphValues, ORE, OuterTripCount, MaxTripCount, false,
       OuterTripMultiple, OuterLoopSize, UP, UseUpperBound);
   if (ExplicitUnroll || UseUpperBound) {
     // If the user explicitly set the loop as unrolled, dont UnJ it. Leave it

lib/Transforms/Scalar/LoopUnrollPass.cpp

     Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
     ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
     OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount,
-    unsigned &TripMultiple, unsigned LoopSize,
+    bool MaxOrZero, unsigned &TripMultiple, unsigned LoopSize,
     TargetTransformInfo::UnrollingPreferences &UP, bool &UseUpperBound) {
 
   // Check for explicit Count.

   // Also we need to check if we exceed FullUnrollMaxCount.
   // If using the upper bound to unroll, TripMultiple should be set to 1 because
   // we do not know when loop may exit.
-  // MaxTripCount and ExactTripCount cannot both be non zero since we only
+
+  // We can unroll by the upper bound amount if it's generally allowed or if
+  // we know that the loop is executed either the upper bound or zero times.
+  // (MaxOrZero unrolling keeps only the first loop test, so the number of
+  // loop tests remains the same compared to the non-unrolled version, whereas
+  // the generic upper bound unrolling keeps all but the last loop test so the
+  // number of loop tests goes up which may end up being worse on targets with
+  // constrained branch predictor resources so is controlled by an option.)
+  // In addition we only unroll small upper bounds.
+  unsigned UnrollByMaxCount = MaxTripCount;
+  if (!(UP.UpperBound || MaxOrZero) || UnrollByMaxCount > UnrollMaxUpperBound)
+    UnrollByMaxCount = 0;
+
+  // UnrollByMaxCount and ExactTripCount cannot both be non zero since we only
   // compute the former when the latter is zero.
   unsigned ExactTripCount = TripCount;
-  assert((ExactTripCount == 0 || MaxTripCount == 0) &&
-         "ExtractTripCount and MaxTripCount cannot both be non zero.");
-  unsigned FullUnrollTripCount = ExactTripCount ? ExactTripCount : MaxTripCount;
+  assert((ExactTripCount == 0 || UnrollByMaxCount == 0) &&
+         "ExtractTripCount and UnrollByMaxCount cannot both be non zero.");
+
+  unsigned FullUnrollTripCount =
+      ExactTripCount ? ExactTripCount : UnrollByMaxCount;
   UP.Count = FullUnrollTripCount;
   if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
     // When computing the unrolled size, note that BEInsns are not replicated
     // like the rest of the loop body.
     if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
-      UseUpperBound = (MaxTripCount == FullUnrollTripCount);
+      UseUpperBound = (UnrollByMaxCount == FullUnrollTripCount);
       TripCount = FullUnrollTripCount;
       TripMultiple = UP.UpperBound ? 1 : TripMultiple;
       return ExplicitUnroll;

         unsigned Boost =
             getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
         if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
-          UseUpperBound = (MaxTripCount == FullUnrollTripCount);
+          UseUpperBound = (UnrollByMaxCount == FullUnrollTripCount);
           TripCount = FullUnrollTripCount;
           TripMultiple = UP.UpperBound ? 1 : TripMultiple;
           return ExplicitUnroll;

     return false;
   }
 
+  // Don't unroll a small upper bound loop unless user or TTI asked to do so.
+  if (MaxTripCount && !UP.Force && MaxTripCount < UnrollMaxUpperBound) {
+    UP.Count = 0;
+    return false;
+  }
+
   // Check if the runtime trip count is too small when profile is available.
   if (L->getHeader()->getParent()->hasProfileData()) {
     if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {

 
   if (UP.Count > UP.MaxCount)
     UP.Count = UP.MaxCount;
+
+  if (MaxTripCount && UP.Count > MaxTripCount)
+    UP.Count = MaxTripCount;
+
   LLVM_DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count
                     << "\n");
   if (UP.Count < 2)

 
   // Find trip count and trip multiple if count is not available
   unsigned TripCount = 0;
-  unsigned MaxTripCount = 0;
   unsigned TripMultiple = 1;
   // If there are multiple exiting blocks but one of them is the latch, use the
   // latch for the trip count estimation. Otherwise insist on a single exiting

 
   // Try to find the trip count upper bound if we cannot find the exact trip
   // count.
+  unsigned MaxTripCount = 0;
   bool MaxOrZero = false;
   if (!TripCount) {
     MaxTripCount = SE.getSmallConstantMaxTripCount(L);
     MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
-    // We can unroll by the upper bound amount if it's generally allowed or if
-    // we know that the loop is executed either the upper bound or zero times.
-    // (MaxOrZero unrolling keeps only the first loop test, so the number of
-    // loop tests remains the same compared to the non-unrolled version, whereas
-    // the generic upper bound unrolling keeps all but the last loop test so the
-    // number of loop tests goes up which may end up being worse on targets with
-    // constrained branch predictor resources so is controlled by an option.)
-    // In addition we only unroll small upper bounds.
-    if (!(UP.UpperBound || MaxOrZero) || MaxTripCount > UnrollMaxUpperBound) {
-      MaxTripCount = 0;
-    }
   }
 
   // computeUnrollCount() decides whether it is beneficial to use upper bound to
   // fully unroll the loop.
   bool UseUpperBound = false;
   bool IsCountSetExplicitly = computeUnrollCount(
-      L, TTI, DT, LI, SE, EphValues, &ORE, TripCount, MaxTripCount,
+      L, TTI, DT, LI, SE, EphValues, &ORE, TripCount, MaxTripCount, MaxOrZero,
       TripMultiple, LoopSize, UP, UseUpperBound);
   if (!UP.Count)
     return LoopUnrollResult::Unmodified;

test/Transforms/LoopUnroll/runtime-small-upperbound.ll

+; RUN: opt -S -loop-unroll -unroll-runtime %s -o - | FileCheck %s
+; RUN: opt -S -loop-unroll -unroll-runtime -unroll-max-upperbound=6 %s -o - | FileCheck %s --check-prefix=UPPER
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+@global = dso_local local_unnamed_addr global i32 0, align 4
+@global.1 = dso_local local_unnamed_addr global i8* null, align 4
+
+; Check that loop in hoge_3, with a runtime upperbound of 3, is not unrolled.
+; CHECK-LABEL: hoge_3
+; CHECK: loop:
+; CHECK: store i8 %arg
+; CHECK-NOT: store i8 %arg
+; CHECK: br i1 %{{.*}}, label %loop
+; UPPER-LABEL: hoge_3
+; UPPER: loop:
+; UPPER: store i8 %arg
+; UPPER-NOT: store i8 %arg
+; UPPER: br i1 %{{.*}}, label %loop
+define dso_local void @hoge_3(i8 %arg) {
+entry:
+  %x = load i32, i32* @global, align 4
+  %0 = icmp ult i32 %x, 17
+  br i1 %0, label %loop, label %exit
+
+loop:
+  %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ]
+  %iv.next = add nuw i32 %iv, 8
+  %1 = load i8*, i8** @global.1, align 4
+  %2 = getelementptr inbounds i8, i8* %1, i32 1
+  store i8* %2, i8** @global.1, align 4
+  store i8 %arg, i8* %1, align 1
+  %3 = icmp ult i32 %iv.next, 17
+  br i1 %3, label %loop, label %exit
+
+exit:                                             ; preds = %bb12, %bb
+  ret void
+}
+
+; Check that loop in hoge_5, with a runtime upperbound of 5, is unrolled when -unroll-max-upperbound=4
+; CHECK-LABEL: hoge_5
+; CHECK: loop:
+; CHECK: store i8 %arg
+; CHECK-NOT: store i8 %arg
+; CHECK: br i1 %{{.*}}, label %loop
+; UPPER-LABEL: hoge_5
+; UPPER: loop:
+; UPPER: store i8 %arg
+; UPPER: store i8 %arg
+; UPPER: store i8 %arg
+; UPPER: br i1 %{{.*}}, label %loop
+define dso_local void @hoge_5(i8 %arg) {
+entry:
+  %x = load i32, i32* @global, align 4
+  %0 = icmp ult i32 %x, 17
+  br i1 %0, label %loop, label %exit
+
+loop:
+  %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ]
+  %iv.next = add nuw i32 %iv, 4
+  %1 = load i8*, i8** @global.1, align 4
+  %2 = getelementptr inbounds i8, i8* %1, i32 1
+  store i8* %2, i8** @global.1, align 4
+  store i8 %arg, i8* %1, align 1
+  %3 = icmp ult i32 %iv.next, 17
+  br i1 %3, label %loop, label %exit
+
+exit:                                             ; preds = %bb12, %bb
+  ret void
+}