[Loop Peeling] Do not close further unroll/peel if profile based peeling was not used

[skatkov]

Summary

Current peeling cost model can decide to peel off not all iterations
but only some of them to eliminate conditions on phi. At the same time
if any peeling happens the door for further unroll/peel optimizations on that
loop closes because the part of the code thinks that if peeling happened
it is profile based peeling and all iterations are peeled off.

To resolve this inconsistency the patch provides the flag which states whether
the full peeling basing on profile is enabled or not and peeling cost model
is able to modify this field like it does not PeelCount.

In a separate patch I will introduce an option to allow/disallow peeling basing
on profile.

To avoid infinite loop peeling the patch tracks the total number of peeled iteration
through llvm.loop.peeled.count loop metadata.

[reames]

I'm not quite sure this is the right macro approach.

The comment near the code your modifying makes me thing the whole reasoning behind disabling future peeling and unrolling after the first peel may be flawed. It doesn't make sense to "use up" profiling information. Assuming we correctly updated our profiling when doing the transform, the resulting profile for the loop should indicate that it's cold and thus not profitable to further peel/unroll. If that's not happening, maybe there's another issue in play? (I wonder if your other profile bug fix may help here?)

p.s. I'm opened to being convinced that this is a practical answer, even if not an ideal one. Just make the argument. :)

llvm/include/llvm/Analysis/TargetTransformInfo.h

478 ↗

(On Diff #210743)

Naming wise: Please call this something other than "Full" peeling. Full peeling sounds like full unrolling which would imply we were able to entirely eliminate the loop structure.

Maybe: PeelProfiledIterations?

[reames]

(Marking as RC for tracking purposes only)

[skatkov]

In D64972#1593826, @reames wrote:

I'm not quite sure this is the right macro approach.

The comment near the code your modifying makes me thing the whole reasoning behind disabling future peeling and unrolling after the first peel may be flawed. It doesn't make sense to "use up" profiling information. Assuming we correctly updated our profiling when doing the transform, the resulting profile for the loop should indicate that it's cold and thus not profitable to further peel/unroll. If that's not happening, maybe there's another issue in play? (I wonder if your other profile bug fix may help here?)

p.s. I'm opened to being convinced that this is a practical answer, even if not an ideal one. Just make the argument. :)

Hi Philip, the story is the following.

Let's we have a loop which does 5 iteration according to profile but also one of its condition can be simplified by peeling and to simplify condition we need only 1 iteration peeled off.
According to current implementation Loop Peeling cost model will decide that we should peel off one iteration.
One iteration is peeled off and weights are updated correctly (now estimated trip count is 5 - 1 == 4)
But we mark the loop as llvm.loop.unroll.disable unconditionally if we do any peeling.

As a result another potential LoopUnroll pass will not even consider this loop for peeling while if it does it would detect that we can peel additional 4 iterations.

So this patch fixes this part: if we did not peel all iteration basing on profile we should mark this loop as no consider for future peel/unroll.

Will update the patch soon with modified proposed name of variable which really makes the intention clearer.

llvm/include/llvm/Analysis/TargetTransformInfo.h

478 ↗

(On Diff #210743)

Agreed.

[skatkov]

Test is updated to show what this patch changes.

[skatkov]

Added the guard to not exceed the UnrollPeelMaxCount limit.

[reames]

Having both the enable flag and the AlreadyPeeled variable is really confusing. Is there a way we could combine them? Maybe replace the boolean with the AlreadyPeeledViaProfiling count or something?

[skatkov]

In D64972#1606836, @reames wrote:

Having both the enable flag and the AlreadyPeeled variable is really confusing. Is there a way we could combine them? Maybe replace the boolean with the AlreadyPeeledViaProfiling count or something?

To me the flag AllowPeeling is to disable peeling at all while AlreadyPeeledViaProfiling is for disablement of part of the peeling.
In this term I would update the comment for AllowPeeling:
/ Allow peeling off loop iterations for loops with low dynamic tripcount.
to
/ Allow peeling off loop iterations.
taking into account that it is not now true (before my change as well).

If we really want to combine these options it makes sense to introduce enum with possible levels of peeling (say None, NonProfileBased, All).
Coding this enum with integer is not something really reducing the confusion.
However this enum will not be aligned with different unroll options. Also this will require some modifications in options handling - Different ways to set the desired level of peeling needs to support this new enum.

Let me know if we really want to introduce this.

[skatkov]

Philip, please take a look at https://reviews.llvm.org/D65501 which introduces the peeling level as possible solution to handle your comment.

[skatkov]

In D64972#1607909, @skatkov wrote:

Philip, please take a look at https://reviews.llvm.org/D65501 which introduces the peeling level as possible solution to handle your comment.

See https://reviews.llvm.org/D65503. It is the same patch but based on D65501.

[skatkov]

In D64972#1607998, @skatkov wrote:

In D64972#1607909, @skatkov wrote:

Philip, please take a look at https://reviews.llvm.org/D65501 which introduces the peeling level as possible solution to handle your comment.

See https://reviews.llvm.org/D65503. It is the same patch but based on D65501.

I personally prefer this variant.

[reames]

LGTM.

Serguei and I spent a fair amount of time talking about this one offline. Neither of us are completely happy with the structure of this patch, but since it's using the same pattern as what was already there (just a bit more fine grained), I decide to approve this so as to unblock Serguei's other work.

He and I are planning to continuing thinking about the code structure here, and may come back with an NFC for the whole area if we can find a design that seems cleaner. Ideas welcome.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

1140 ↗

(On Diff #211690)

The more I look at this comment, the more it just feels wrong. Absolutely not a blocking item for this patch though!

llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp

330 ↗

(On Diff #211690)

Sink this debug output under your if please.

llvm/trunk/include/llvm/Analysis/TargetTransformInfo.h

struct UnrollingPreferences {
     /// Allow emitting expensive instructions (such as divisions) when computing
     /// the trip count of a loop for runtime unrolling.
     bool AllowExpensiveTripCount;
     /// Apply loop unroll on any kind of loop
     /// (mainly to loops that fail runtime unrolling).
     bool Force;
     /// Allow using trip count upper bound to unroll loops.
     bool UpperBound;
-    /// Allow peeling off loop iterations for loops with low dynamic tripcount.
+    /// Allow peeling off loop iterations.
     bool AllowPeeling;
     /// Allow unrolling of all the iterations of the runtime loop remainder.
     bool UnrollRemainder;
     /// Allow unroll and jam. Used to enable unroll and jam for the target.
     bool UnrollAndJam;
+    /// Allow peeling basing on profile. Uses to enable peeling off all
+    /// iterations basing on provided profile.
+    /// If the value is true the peeling cost model can decide to peel only
+    /// some iterations and in this case it will set this to false.
+    bool PeelProfiledIterations;
     /// Threshold for unroll and jam, for inner loop size. The 'Threshold'
     /// value above is used during unroll and jam for the outer loop size.
     /// This value is used in the same manner to limit the size of the inner
     /// loop.
     unsigned UnrollAndJamInnerLoopThreshold;
   };
 
   /// Get target-customized preferences for the generic loop unrolling

llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp

TargetTransformInfo::UnrollingPreferences llvm::gatherUnrollingPreferences(
   UP.Runtime = false;
   UP.AllowRemainder = true;
   UP.UnrollRemainder = false;
   UP.AllowExpensiveTripCount = false;
   UP.Force = false;
   UP.UpperBound = false;
   UP.AllowPeeling = true;
   UP.UnrollAndJam = false;
+  UP.PeelProfiledIterations = true;
   UP.UnrollAndJamInnerLoopThreshold = 60;
 
   // Override with any target specific settings
   TTI.getUnrollingPreferences(L, SE, UP);
 
   // Apply size attributes
   bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
                     llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI);
if (UnrollResult != LoopUnrollResult::FullyUnrolled) {
     }
   }
 
   // If loop has an unroll count pragma or unrolled by explicitly set count
   // mark loop as unrolled to prevent unrolling beyond that requested.
   // If the loop was peeled, we already "used up" the profile information
   // we had, so we don't want to unroll or peel again.
   if (UnrollResult != LoopUnrollResult::FullyUnrolled &&
-      (IsCountSetExplicitly || UP.PeelCount))
+      (IsCountSetExplicitly || (UP.PeelProfiledIterations && UP.PeelCount)))
     L->setLoopAlreadyUnrolled();
 
   return UnrollResult;
 }
 
 namespace {
 
 class LoopUnroll : public LoopPass {

llvm/trunk/lib/Transforms/Utils/LoopUnrollPeel.cpp

 static cl::opt<unsigned> UnrollForcePeelCount(
     "unroll-force-peel-count", cl::init(0), cl::Hidden,
     cl::desc("Force a peel count regardless of profiling information."));
 
 static cl::opt<bool> UnrollPeelMultiDeoptExit(
     "unroll-peel-multi-deopt-exit", cl::init(true), cl::Hidden,
     cl::desc("Allow peeling of loops with multiple deopt exits."));
 
+static const char *PeeledCountMetaData = "llvm.loop.peeled.count";
+
 // Designates that a Phi is estimated to become invariant after an "infinite"
 // number of loop iterations (i.e. only may become an invariant if the loop is
 // fully unrolled).
 static const unsigned InfiniteIterationsToInvariance =
     std::numeric_limits<unsigned>::max();
 
 // Check whether we are capable of peeling this loop.
 bool llvm::canPeel(Loop *L) {
if (!L->empty())
     return;
 
   // If the user provided a peel count, use that.
   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
   if (UserPeelCount) {
     LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
                       << " iterations.\n");
     UP.PeelCount = UnrollForcePeelCount;
+    UP.PeelProfiledIterations = true;
     return;
   }
 
   // Skip peeling if it's disabled.
   if (!UP.AllowPeeling)
     return;
 
+  unsigned AlreadyPeeled = 0;
+  if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
+    AlreadyPeeled = *Peeled;
+  // Stop if we already peeled off the maximum number of iterations.
+  if (AlreadyPeeled >= UnrollPeelMaxCount)
+    return;
+
   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
   // iterations of the loop. For this we compute the number for iterations after
   // which every Phi is guaranteed to become an invariant, and try to peel the
   // maximum number of iterations among these values, thus turning all those
   // Phis into invariants.
   // First, check that we can peel at least one iteration.
   if (2 * LoopSize <= UP.Threshold && UnrollPeelMaxCount > 0) {
     // Store the pre-calculated values here.
if (2 * LoopSize <= UP.Threshold && UnrollPeelMaxCount > 0) {
 
     DesiredPeelCount = std::max(DesiredPeelCount,
                                 countToEliminateCompares(*L, MaxPeelCount, SE));
 
     if (DesiredPeelCount > 0) {
       DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
       // Consider max peel count limitation.
       assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
+      if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) {
         LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
                           << " iteration(s) to turn"
                           << " some Phis into invariants.\n");
         UP.PeelCount = DesiredPeelCount;
+        UP.PeelProfiledIterations = false;
         return;
       }
     }
+  }
 
   // Bail if we know the statically calculated trip count.
   // In this case we rather prefer partial unrolling.
   if (TripCount)
     return;
 
+  // Do not apply profile base peeling if it is disabled.
+  if (!UP.PeelProfiledIterations)
+    return;
   // If we don't know the trip count, but have reason to believe the average
   // trip count is low, peeling should be beneficial, since we will usually
   // hit the peeled section.
   // We only do this in the presence of profile information, since otherwise
   // our estimates of the trip count are not reliable enough.
   if (L->getHeader()->getParent()->hasProfileData()) {
     Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
     if (!PeelCount)
       return;
 
     LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
                       << "\n");
 
     if (*PeelCount) {
-      if ((*PeelCount <= UnrollPeelMaxCount) &&
+      if ((*PeelCount + AlreadyPeeled <= UnrollPeelMaxCount) &&
           (LoopSize * (*PeelCount + 1) <= UP.Threshold)) {
         LLVM_DEBUG(dbgs() << "Peeling first " << *PeelCount
                           << " iterations.\n");
         UP.PeelCount = *PeelCount;
         return;
       }
       LLVM_DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
+      LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");
       LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
       LLVM_DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1)
                         << "\n");
       LLVM_DEBUG(dbgs() << "Max peel cost: " << UP.Threshold << "\n");
     }
   }
 }
 
#endif
   // Finally DomtTree must be correct.
   assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 
   // FIXME: Incrementally update loop-simplify
   simplifyLoop(L, DT, LI, SE, AC, nullptr, PreserveLCSSA);
 
   NumPeeled++;
 
+  // Update Metadata for count of peeled off iterations.
+  unsigned AlreadyPeeled = 0;
+  if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
+    AlreadyPeeled = *Peeled;
+  addStringMetadataToLoop(L, PeeledCountMetaData, AlreadyPeeled + PeelCount);
+
   return true;
 }

llvm/trunk/test/Transforms/LoopUnroll/peel-loop-conditions-pgo-1.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -loop-unroll -loop-unroll -verify-dom-info -debug-only=loop-unroll -unroll-peel-max-count=7 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+declare void @f1()
+declare void @f2()
+
+; Check that we can peel off iterations that make conditions true.
+; The second invocation of loop-unroll will do profile based peeling of
+; remained iterations.
+define void @test1(i32 %k) !prof !4 {
+; CHECK: Loop Unroll: F[test1] Loop %for.body
+; CHECK: PEELING loop %for.body with iteration count 2!
+; CHECK: PEELING loop %for.body with iteration count 4!
+; CHECK: llvm.loop.unroll.disable
+for.body.lr.ph:
+  br label %for.body
+
+for.body:
+  %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp ult i32 %i.05, 2
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  call void @f1()
+  br label %for.inc
+
+if.else:
+  call void @f2()
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.05, 1
+  %cmp = icmp slt i32 %inc, %k
+  br i1 %cmp, label %for.body, label %for.end, !llvm.loop !1, !prof !2
+
+for.end:
+  ret void
+}
+
+!1 = distinct !{!1}
+!2 = !{!"branch_weights", i32 6, i32 1}
+!4 = !{!"function_entry_count", i64 1}

llvm/trunk/test/Transforms/LoopUnroll/peel-loop-conditions-pgo-2.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -loop-unroll -loop-unroll -verify-dom-info -debug-only=loop-unroll -unroll-peel-max-count=7 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+declare void @f1()
+declare void @f2()
+
+; Check that we can peel off iterations that make conditions true.
+; The second invocation of loop-unroll will NOT do profile based peeling of
+; remained iterations because the total number of peeled iterations exceeds
+; threashold specified with -unroll-peel-max-count=7.
+define void @test2(i32 %k) !prof !4 {
+; CHECK: Loop Unroll: F[test2] Loop %for.body
+; CHECK: PEELING loop %for.body with iteration count 2!
+; CHECK-NOT: llvm.loop.unroll.disable
+for.body.lr.ph:
+  br label %for.body
+
+for.body:
+  %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp ult i32 %i.05, 2
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  call void @f1()
+  br label %for.inc
+
+if.else:
+  call void @f2()
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.05, 1
+  %cmp = icmp slt i32 %inc, %k
+  br i1 %cmp, label %for.body, label %for.end, !llvm.loop !1, !prof !3
+
+for.end:
+  ret void
+}
+
+!1 = distinct !{!1}
+!3 = !{!"branch_weights", i32 8, i32 1}
+!4 = !{!"function_entry_count", i64 1}

llvm/trunk/test/Transforms/LoopUnroll/peel-loop-conditions.ll

 for.inc:
   %inc = add i32 %i.05, 1
   %cmp = icmp slt i32 %inc, %k
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
+; CHECK-NOT: llvm.loop.unroll.disable
 No newline at end of file