[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

29–31

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

 
 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
                           DependenceInfo &DI);
 
 bool computeUnrollCount(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,
+                        unsigned MaxTripCount, bool MaxOrZero,
+                        unsigned &TripMultiple, unsigned LoopSize,
                         TargetTransformInfo::UnrollingPreferences &UP,
                         bool &UseUpperBound);
 
 void remapInstruction(Instruction *I, ValueToValueMapTy &VMap);
 
 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
                              ScalarEvolution *SE, DominatorTree *DT,
                              AssumptionCache *AC);

lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

static bool computeUnrollAndJamCount(
   // First up use computeUnrollCount from the loop unroller to get a count
   // for unrolling the outer loop, plus any loops requiring explicit
   // unrolling we leave to the unroller. This uses UP.Threshold /
   // UP.PartialThreshold / UP.MaxCount to come up with sensible loop values.
   // We have already checked that the loop has no unroll.* pragmas.
   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
     // for the unroller instead.
     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; explicit count set by "
                          "computeUnrollCount\n");
     UP.Count = 0;
     return false;

lib/Transforms/Scalar/LoopUnrollPass.cpp

 // irrelevant for the LoopUnrollAndJam pass).
 // FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
 // many LoopUnroll-specific options. The shared functionality should be
 // refactored into it own function.
 bool llvm::computeUnrollCount(
     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.
   // 1st priority is unroll count set by "unroll-count" option.
   bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
   if (UserUnrollCount) {
     UP.Count = UnrollCount;
     UP.AllowExpensiveTripCount = true;
bool llvm::computeUnrollCount(
   }
 
   // 3rd priority is full unroll count.
   // Full unroll makes sense only when TripCount or its upper bound could be
   // statically calculated.
   // 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;
     } else {
       // The loop isn't that small, but we still can fully unroll it if that
       // helps to remove a significant number of instructions.
       // To check that, run additional analysis on the loop.
       if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
               L, FullUnrollTripCount, DT, SE, EphValues, TTI,
               UP.Threshold * UP.MaxPercentThresholdBoost / 100)) {
         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;
         }
       }
     }
   }
 
bool llvm::computeUnrollCount(
 
   // 6th priority is runtime unrolling.
   // Don't unroll a runtime trip count loop when it is disabled.
   if (HasRuntimeUnrollDisablePragma(L)) {
     UP.Count = 0;
     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 (*ProfileTripCount < FlatLoopTripCountThreshold)
         return false;
       else
         UP.AllowExpensiveTripCount = true;
     }
if (PragmaCount > 0 && !UP.AllowRemainder)
                   "count that divides the loop trip multiple of "
                << NV("TripMultiple", TripMultiple) << ".  Unrolling instead "
                << NV("UnrollCount", UP.Count) << " time(s).";
       });
   }
 
   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)
     UP.Count = 0;
   return ExplicitUnroll;
 }
 
 static LoopUnrollResult tryToUnrollLoop(
static LoopUnrollResult tryToUnrollLoop(
 
   if (NumInlineCandidates != 0) {
     LLVM_DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
     return LoopUnrollResult::Unmodified;
   }
 
   // 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
   // block for the trip count estimation.
   BasicBlock *ExitingBlock = L->getLoopLatch();
   if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
     ExitingBlock = L->getExitingBlock();
   if (ExitingBlock) {
static LoopUnrollResult tryToUnrollLoop(
   // Assuming n is the same on all threads, any kind of unrolling is
   // safe.  But currently llvm's notion of convergence isn't powerful
   // enough to express this.
   if (Convergent)
     UP.AllowRemainder = false;
 
   // 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;
   // Unroll factor (Count) must be less or equal to TripCount.
   if (TripCount && UP.Count > TripCount)
     UP.Count = TripCount;
 
   // Save loop properties before it is transformed.

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
+}