[LoopUnrolling] Re-prioritize Peeling and Partial unrolling

[mkazantsev]

Summary

In current implementation the loop peeling happens after trip-count based partial unrolling and may
sometimes not happen at all due to it (for example, if trip count is known, but UP.Partial = false). This
is generally bad, the more than there are some situations where peeling is profitable even if the partial
unrolling is disabled.

This patch is a NFC which reorders peeling and partial unrolling application and prepares the code for
implementation of the said optimizations.

[mkuper]

lib/Transforms/Scalar/LoopUnrollPass.cpp

789

The current heuristic is supposed to be that we only peel when we don't know the trip count, but have an approximate one due to profile information. Partial unrolling requires a known trip count. So in the old code, they don't actually compete for priority, and this change looks like it should be NFC.

I'm not sure this is completely NFC, though - I don't remember if computePeelCount actually enforces an unknown trip count, or just assumes it's unknown, because otherwise we'd quit at line 838. So you probably want this to be "if (!TripCount && UP.PeelCount)", or change computePeelCount() to bail on a known trip count. Otherwise, what you may in effect be doing is enabling peeling for loops with a constant low trip count that we chose not to unroll. Which is probably not something you want to do.

[mkazantsev]

lib/Transforms/Scalar/LoopUnrollPass.cpp

789

In fact, even if trip count is known, peeling can still be profitable. One of such cases is shown at https://reviews.llvm.org/D30161, where Phi's back edge input is a constant. Partial unrolling here does not give any benefits, while peeling does. My understanding is following: Peeling should not set peel count unless it has proved that peeling IS profitable. In this case nothing bad happens with small loops that we don't unroll: they will only be peeled if it is good. Maybe it is reasonable to add the following restriction to peeling: TripCount should be either unknown or above some threshold (for example, partial unrolling threshold). Does it make sense for you?

[mkuper]

lib/Transforms/Scalar/LoopUnrollPass.cpp

789

Sorry, I wasn't clear.
I understand that there are cases where peeling is profitable even when the trip count is known - D30161 is a really nice example.

But right now, when we have profile information, we try to peel by the estimated number of iterations. That specific kind of peeling, combined with this patch, has two issues:

1. getLoopEstimatedTripCount() returns the estimated (based on the profile) trip count. This may be imprecise, and at this point, somewhat different from the actual trip count, especially for sampling-based FDO. So you may end up peeling by the "estimated" trip-count even though you know the actual tripcount. That sounds wrong.

2. Even if we fix getLoopEstimatedTripCount() to return the real trip count, when available, you still basically get "let's peel a loop by its real tripcount", which is equivalent to full unrolling. In theory, it shouldn't happen, because full unrolling and peeling should be using the same thresholds, so if we decided not to fully unroll, we'll decide not to "peel" either. But I'm not sure this actually holds.

I'm not saying we should disable any kind of peeling when the real trip count is known. Only that we should disable the "peel by the estimated trip count" heuristic.

[mkuper]

lib/Transforms/Scalar/LoopUnrollPass.cpp

789

This patch doesn't really make sense as a stand-alone, and I'm not sure it's the right way to go as preparation to D30161 either.

I would suggest something like:

1. In this patch, invert the priorities of peeling and partial unrolling, but bail out of computePeelCount when the real trip count is known. This should be NFC.
2. In D30161, change the logic of computePeelCount() to be something like:

if conditions are right:
  peel by 1
else if trip count is known:
  bail out
else:
  check if we should peel by estimated trip count.

lib/Transforms/Utils/LoopUnrollPeel.cpp

75

If you do decide to call this twice - I'd expect this to also get hit only the second time around.

[mkazantsev]

lib/Transforms/Utils/LoopUnrollPeel.cpp

75

No longer calling twice.

[mkuper]

LGTM

include/llvm/Transforms/Utils/UnrollLoop.h

 
 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
                                 bool AllowExpensiveTripCount,
                                 bool UseEpilogRemainder, LoopInfo *LI,
                                 ScalarEvolution *SE, DominatorTree *DT,
                                 bool PreserveLCSSA);
 
 void computePeelCount(Loop *L, unsigned LoopSize,
-                      TargetTransformInfo::UnrollingPreferences &UP);
+                      TargetTransformInfo::UnrollingPreferences &UP,
+                      bool BaseOnTripCount);
 
 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
               DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
 
 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
 }
 
 #endif

lib/Transforms/Scalar/LoopUnrollPass.cpp

if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
           TripCount = FullUnrollTripCount;
           TripMultiple = UP.UpperBound ? 1 : TripMultiple;
           return ExplicitUnroll;
         }
       }
     }
   }
 
-  // 4rd priority is partial unrolling.
+  // 4th priority is loop peeling not basing on trip count.
+  computePeelCount(L, LoopSize, UP, /* BaseOnTripCount */ false);
+  if (UP.PeelCount) {
+    UP.Runtime = false;
+    UP.Count = 1;
+    return ExplicitUnroll;
+  }
+
+  // 5th priority is partial unrolling.
   // Try partial unroll only when TripCount could be staticaly calculated.
   if (TripCount) {
     UP.Partial |= ExplicitUnroll;
     if (!UP.Partial) {
       DEBUG(dbgs() << "  will not try to unroll partially because "
                    << "-unroll-allow-partial not given\n");
       UP.Count = 0;
       return false;
static bool computeUnrollCount(
   if (PragmaFullUnroll)
     ORE->emit(
         OptimizationRemarkMissed(DEBUG_TYPE,
                                  "CantFullUnrollAsDirectedRuntimeTripCount",
                                  L->getStartLoc(), L->getHeader())
         << "Unable to fully unroll loop as directed by unroll(full) pragma "
            "because loop has a runtime trip count.");
 
-  // 5th priority is loop peeling
-  computePeelCount(L, LoopSize, UP);
+  // 6th priority is loop peeling basing on trip count.
+  computePeelCount(L, LoopSize, UP, /* BaseOnTripCount */ true);
   if (UP.PeelCount) {
     UP.Runtime = false;
     UP.Count = 1;
     return ExplicitUnroll;
   }
 
-  // 6th priority is runtime unrolling.
+  // 7th priority is runtime unrolling.
   // Don't unroll a runtime trip count loop when it is disabled.
   if (HasRuntimeUnrollDisablePragma(L)) {
     UP.Count = 0;
     return false;
   }
   
   // Check if the runtime trip count is too small when profile is available.
   if (L->getHeader()->getParent()->getEntryCount()) {

lib/Transforms/Utils/LoopUnrollPeel.cpp

static bool canPeel(Loop *L) {
   if (!L->getExitingBlock() || !L->getUniqueExitBlock())
     return false;
 
   return true;
 }
 
 // Return the number of iterations we want to peel off.
 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
-                            TargetTransformInfo::UnrollingPreferences &UP) {
+                            TargetTransformInfo::UnrollingPreferences &UP,
+                            bool BaseOnTripCount) {
   UP.PeelCount = 0;
   if (!canPeel(L))
     return;
 
   // Only try to peel innermost loops.
   if (!L->empty())
     return;
 
   // If the user provided a peel count, use that.
   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
   if (UserPeelCount) {
     DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
                  << " iterations.\n");
     UP.PeelCount = UnrollForcePeelCount;
     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 (UP.AllowPeeling && L->getHeader()->getParent()->getEntryCount()) {
+  if (BaseOnTripCount && UP.AllowPeeling &&
+      L->getHeader()->getParent()->getEntryCount()) {
     Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
     if (!PeelCount)
       return;
 
     DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
                  << "\n");
 
     if (*PeelCount) {