[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

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

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

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

321

Sink this debug output under your if please.

llvm/include/llvm/Analysis/TargetTransformInfo.h

struct UnrollingPreferences {
     /// Allow using trip count upper bound to unroll loops.
     bool UpperBound;
     /// Allow peeling off loop iterations for loops with low dynamic tripcount.
     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 full peeling. Uses to enable peeling off all iterations which
+    /// closes further unroll/peeling optimizations on the loop.
+    /// If the value is true the peeling cost model can decide to peel only
+    /// some iteration and in this case it will set this to false.
+    bool FullPeeling;
     /// 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/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.FullPeeling = 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 (NewLoopID.hasValue()) {
       // Do not setLoopAlreadyUnrolled if loop attributes have been specified
       // explicitly.
       return UnrollResult;
     }
   }
 
   // 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.FullPeeling && UP.PeelCount)))
     L->setLoopAlreadyUnrolled();
 
   return UnrollResult;
 }
 
 namespace {
 
 class LoopUnroll : public LoopPass {

llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp

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.FullPeeling = true;
     return;
   }
 
   // Skip peeling if it's disabled.
   if (!UP.AllowPeeling)
     return;
 
   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
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?");
       LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
                         << " iteration(s) to turn"
                         << " some Phis into invariants.\n");
       UP.PeelCount = DesiredPeelCount;
+      UP.FullPeeling = 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.FullPeeling)
+    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)