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

[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.

[skatkov]

Abandon in favor of https://reviews.llvm.org/D64972

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

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.PeelingLevel == PL_All && UP.PeelCount)))
     L->setLoopAlreadyUnrolled();
 
   return UnrollResult;
 }
 
 namespace {
 
 class LoopUnroll : public LoopPass {

llvm/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.PeelingLevel = PL_All;
     return;
   }
 
   // Skip peeling if it's disabled.
   if (UP.PeelingLevel == PL_None)
     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.PeelingLevel = PL_NonProfileBased;
         return;
       }
     }
+  }
 
   // Bail if we know the statically calculated trip count.
   // In this case we rather prefer partial unrolling.
   if (TripCount)
     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.
   if (UP.PeelingLevel == PL_NonProfileBased)
     return;
   // 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;
+        UP.PeelingLevel = PL_All;
         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/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/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/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