Disable loop peeling during full unrolling pass.

[tejohnson]

Summary

Peeling should not occur during the full unrolling invocation early
in the pipeline, but rather later with partial and runtime loop
unrolling. The later loop unrolling invocation will also eventually
utilize profile summary and branch frequency information, which
we would like to use to control peeling. And for ThinLTO we want
to delay peeling until the backend (post thin link) phase, just as
we do for most types of unrolling.

Ensure peeling doesn't occur during the full unrolling invocation
by adding a parameter to the shared implementation function, similar
to the way partial and runtime loop unrolling are disabled.

Performance results for ThinLTO suggest this has a neutral to positive
effect on some internal benchmarks.

[davidxl]

Perhaps it is cleaner to

1. pass the information whether it is a full unroll to tryToUnroll
2. add a internal option FullUnrollAllowPeeling and make it off by default? This will be similar to UnrollAllowPeeling flag, but takes precedence if it is full unroll.

lib/Transforms/Scalar/LoopUnrollPass.cpp

204 ↗

(On Diff #109484)

Move this closer to line 188 above?

[chandlerc]

In D36258#830096, @davidxl wrote:

Perhaps it is cleaner to

1. pass the information whether it is a full unroll to tryToUnroll
2. add a internal option FullUnrollAllowPeeling and make it off by default? This will be similar to UnrollAllowPeeling flag, but takes precedence if it is full unroll.

While I'm somewhat fond of refactoring these interfaces to be less of a mess, would it be better in a follow-up patch? I would also hope it can tackle more than just peeling but encompass several of the numerous parameters.

lib/Transforms/Scalar/LoopUnrollPass.cpp

204 ↗

(On Diff #109484)

I think this location is more consistent with the surrounding code... I'm reluctant to deviate here from what seems like a very consistent pattern.

1289 ↗

(On Diff #109484)

Shouldn't this pass AllowPeeling since you added that variable above?

[davidxl]

lib/Transforms/Scalar/LoopUnrollPass.cpp

204 ↗

(On Diff #109484)

Right. They all should be interleaved so that settings to the same flag should be side by side, but that is not relevant here.

[tejohnson]

In D36258#830100, @chandlerc wrote:

In D36258#830096, @davidxl wrote:

Perhaps it is cleaner to

1. pass the information whether it is a full unroll to tryToUnroll
2. add a internal option FullUnrollAllowPeeling and make it off by default? This will be similar to UnrollAllowPeeling flag, but takes precedence if it is full unroll.

While I'm somewhat fond of refactoring these interfaces to be less of a mess, would it be better in a follow-up patch? I would also hope it can tackle more than just peeling but encompass several of the numerous parameters.

Right, I wanted to be consistent with what is there for other unrolling features and how we disable them during full unrolling.

lib/Transforms/Scalar/LoopUnrollPass.cpp

204 ↗

(On Diff #109484)

Right, I put it here to be consistent.

1289 ↗

(On Diff #109484)

Woops, added that variable then realized I could just pass None directly and forgot to remove it. I'll remove the variable.

[tejohnson]

Remove extraneous variable

[davidxl]

lgtm

[reames]

FYI, this patch causes a somewhat serious regression on one of our internal benchmarks. Given we have a custom pass pipeline, it's definitely our responsibility to adapt to upstream changes not the other way around, but it would have helped us recognize the problem if either of two things had happened along with this patch:

1. The patch had been separated into two pieces: adding the new control know without changing the default and then a small patch changing the default.
2. The change had been announced in some way. An email to llvm-dev probably would have been sufficient.

Given we're hardly the only ones with custom pass pipelines, I'd encourage everyone involved (author, reviewers, etc..) to think about the upgrade path in similar cases which arise in the future.

[hfinkel]

In D36258#878507, @reames wrote:

FYI, this patch causes a somewhat serious regression on one of our internal benchmarks. Given we have a custom pass pipeline, it's definitely our responsibility to adapt to upstream changes not the other way around, but it would have helped us recognize the problem if either of two things had happened along with this patch:

1. The patch had been separated into two pieces: adding the new control know without changing the default and then a small patch changing the default.
2. The change had been announced in some way. An email to llvm-dev probably would have been sufficient.

Given we're hardly the only ones with custom pass pipelines, I'd encourage everyone involved (author, reviewers, etc..) to think about the upgrade path in similar cases which arise in the future.

That's clearly interesting. This change, however, seems like it should be more-or-less a nop. If you're going to fully unroll, why would peeling help? Do you end up with a shorter critical path through the branches if we "peel" first?

[reames]

In D36258#878511, @hfinkel wrote:

That's clearly interesting. This change, however, seems like it should be more-or-less a nop. If you're going to fully unroll, why would peeling help? Do you end up with a shorter critical path through the branches if we "peel" first?

In our pass pipeline, we'd end up with loop-unrolling being quite a bit earlier than upstream. This wasn't so much an intentional choice as an accident of history that we really hadn't evaluated up until now. My best guess is that the peeling was accidentally exposing information to other transformations and that the actual unrolling was incidental to the performance swing. Someone on my team is investigating that a bit further to see what actually happened; what I just said was just an educated guess.

llvm/trunk/include/llvm/Transforms/Scalar.h

 Pass *createLoopInstSimplifyPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopUnroll - This pass is a simple loop unrolling pass.
 //
 Pass *createLoopUnrollPass(int OptLevel = 2, int Threshold = -1, int Count = -1,
                            int AllowPartial = -1, int Runtime = -1,
-                           int UpperBound = -1);
+                           int UpperBound = -1, int AllowPeeling = -1);
 // Create an unrolling pass for full unrolling that uses exact trip count only.
 Pass *createSimpleLoopUnrollPass(int OptLevel = 2);
 
 //===----------------------------------------------------------------------===//
 //
 // LoopReroll - This pass is a simple loop rerolling pass.
 //
 Pass *createLoopRerollPass();

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

 static const unsigned NoThreshold = UINT_MAX;
 
 /// Gather the various unrolling parameters based on the defaults, compiler
 /// flags, TTI overrides and user specified parameters.
 static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
     Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
     Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
-    Optional<bool> UserUpperBound) {
+    Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling) {
   TargetTransformInfo::UnrollingPreferences UP;
 
   // Set up the defaults
   UP.Threshold = OptLevel > 2 ? 300 : 150;
   UP.MaxPercentThresholdBoost = 400;
   UP.OptSizeThreshold = 0;
   UP.PartialThreshold = 150;
   UP.PartialOptSizeThreshold = 0;
static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
   if (UserCount.hasValue())
     UP.Count = *UserCount;
   if (UserAllowPartial.hasValue())
     UP.Partial = *UserAllowPartial;
   if (UserRuntime.hasValue())
     UP.Runtime = *UserRuntime;
   if (UserUpperBound.hasValue())
     UP.UpperBound = *UserUpperBound;
+  if (UserAllowPeeling.hasValue())
+    UP.AllowPeeling = *UserAllowPeeling;
 
   return UP;
 }
 
 namespace {
 /// A struct to densely store the state of an instruction after unrolling at
 /// each iteration.
 ///
#endif
   if (UP.Count > UP.MaxCount)
     UP.Count = UP.MaxCount;
   DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count << "\n");
   if (UP.Count < 2)
     UP.Count = 0;
   return ExplicitUnroll;
 }
 
-static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
-                            ScalarEvolution &SE, const TargetTransformInfo &TTI,
-                            AssumptionCache &AC, OptimizationRemarkEmitter &ORE,
-                            bool PreserveLCSSA, int OptLevel,
-                            Optional<unsigned> ProvidedCount,
-                            Optional<unsigned> ProvidedThreshold,
-                            Optional<bool> ProvidedAllowPartial,
-                            Optional<bool> ProvidedRuntime,
-                            Optional<bool> ProvidedUpperBound) {
+static bool tryToUnrollLoop(
+    Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
+    const TargetTransformInfo &TTI, AssumptionCache &AC,
+    OptimizationRemarkEmitter &ORE, bool PreserveLCSSA, int OptLevel,
+    Optional<unsigned> ProvidedCount, Optional<unsigned> ProvidedThreshold,
+    Optional<bool> ProvidedAllowPartial, Optional<bool> ProvidedRuntime,
+    Optional<bool> ProvidedUpperBound, Optional<bool> ProvidedAllowPeeling) {
   DEBUG(dbgs() << "Loop Unroll: F[" << L->getHeader()->getParent()->getName()
                << "] Loop %" << L->getHeader()->getName() << "\n");
   if (HasUnrollDisablePragma(L)) 
     return false;
   if (!L->isLoopSimplifyForm()) { 
     DEBUG(
         dbgs() << "  Not unrolling loop which is not in loop-simplify form.\n");
     return false;
   }
 
   unsigned NumInlineCandidates;
   bool NotDuplicatable;
   bool Convergent;
   TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
       L, SE, TTI, OptLevel, ProvidedThreshold, ProvidedCount,
-      ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound);
+      ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
+      ProvidedAllowPeeling);
   // Exit early if unrolling is disabled.
   if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0))
     return false;
   unsigned LoopSize = ApproximateLoopSize(
       L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC, UP.BEInsns);
   DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
   if (NotDuplicatable) {
     DEBUG(dbgs() << "  Not unrolling loop which contains non-duplicatable"

 
 namespace {
 class LoopUnroll : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopUnroll(int OptLevel = 2, Optional<unsigned> Threshold = None,
              Optional<unsigned> Count = None,
              Optional<bool> AllowPartial = None, Optional<bool> Runtime = None,
-             Optional<bool> UpperBound = None)
+             Optional<bool> UpperBound = None,
+             Optional<bool> AllowPeeling = None)
       : LoopPass(ID), OptLevel(OptLevel), ProvidedCount(std::move(Count)),
         ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
-        ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound) {
+        ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound),
+        ProvidedAllowPeeling(AllowPeeling) {
     initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
   }
 
   int OptLevel;
   Optional<unsigned> ProvidedCount;
   Optional<unsigned> ProvidedThreshold;
   Optional<bool> ProvidedAllowPartial;
   Optional<bool> ProvidedRuntime;
   Optional<bool> ProvidedUpperBound;
+  Optional<bool> ProvidedAllowPeeling;
 
   bool runOnLoop(Loop *L, LPPassManager &) override {
     if (skipLoop(L))
       return false;
 
     Function &F = *L->getHeader()->getParent();
 
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     const TargetTransformInfo &TTI =
         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
     // pass.  Function analyses need to be preserved across loop transformations
     // but ORE cannot be preserved (see comment before the pass definition).
     OptimizationRemarkEmitter ORE(&F);
     bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 
     return tryToUnrollLoop(L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel,
                            ProvidedCount, ProvidedThreshold,
                            ProvidedAllowPartial, ProvidedRuntime,
-                           ProvidedUpperBound);
+                           ProvidedUpperBound, ProvidedAllowPeeling);
   }
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   ///
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     // FIXME: Loop passes are required to preserve domtree, and for now we just
     // recreate dom info if anything gets unrolled.
     getLoopAnalysisUsage(AU);
   }
 };
 }
 
 char LoopUnroll::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
 
 Pass *llvm::createLoopUnrollPass(int OptLevel, int Threshold, int Count,
-                                 int AllowPartial, int Runtime,
-                                 int UpperBound) {
+                                 int AllowPartial, int Runtime, int UpperBound,
+                                 int AllowPeeling) {
   // TODO: It would make more sense for this function to take the optionals
   // directly, but that's dangerous since it would silently break out of tree
   // callers.
   return new LoopUnroll(
       OptLevel, Threshold == -1 ? None : Optional<unsigned>(Threshold),
       Count == -1 ? None : Optional<unsigned>(Count),
       AllowPartial == -1 ? None : Optional<bool>(AllowPartial),
       Runtime == -1 ? None : Optional<bool>(Runtime),
-      UpperBound == -1 ? None : Optional<bool>(UpperBound));
+      UpperBound == -1 ? None : Optional<bool>(UpperBound),
+      AllowPeeling == -1 ? None : Optional<bool>(AllowPeeling));
 }
 
 Pass *llvm::createSimpleLoopUnrollPass(int OptLevel) {
-  return llvm::createLoopUnrollPass(OptLevel, -1, -1, 0, 0, 0);
+  return llvm::createLoopUnrollPass(OptLevel, -1, -1, 0, 0, 0, 0);
 }
 
 PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
                                           LoopStandardAnalysisResults &AR,
                                           LPMUpdater &Updater) {
   const auto &FAM =
       AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
   Function *F = L.getHeader()->getParent();
if (ParentL)
     OldLoops.insert(ParentL->begin(), ParentL->end());
   else
     OldLoops.insert(AR.LI.begin(), AR.LI.end());
 
   bool Changed =
       tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, *ORE,
                       /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None,
                       /*Threshold*/ None, /*AllowPartial*/ false,
-                      /*Runtime*/ false, /*UpperBound*/ false);
+                      /*Runtime*/ false, /*UpperBound*/ false,
+                      /*AllowPeeling*/ false);
   if (!Changed)
     return PreservedAnalyses::all();
 
   // The parent must not be damaged by unrolling!
 #ifndef NDEBUG
   if (ParentL)
     ParentL->verifyLoop();
 #endif
#endif
     // The API here is quite complex to call, but there are only two interesting
     // states we support: partial and full (or "simple") unrolling. However, to
     // enable these things we actually pass "None" in for the optional to avoid
     // providing an explicit choice.
     Optional<bool> AllowPartialParam, RuntimeParam, UpperBoundParam;
     bool CurChanged = tryToUnrollLoop(
         &L, DT, &LI, SE, TTI, AC, ORE,
         /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None,
-        /*Threshold*/ None, AllowPartialParam, RuntimeParam, UpperBoundParam);
+        /*Threshold*/ None, AllowPartialParam, RuntimeParam, UpperBoundParam,
+        /*AllowPeeling*/ None);
     Changed |= CurChanged;
 
     // The parent must not be damaged by unrolling!
 #ifndef NDEBUG
     if (CurChanged && ParentL)
       ParentL->verifyLoop();
 #endif
   }
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }

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

 ; RUN: opt < %s -S -debug-only=loop-unroll -loop-unroll 2>&1 | FileCheck %s
+; RUN: opt < %s -S -debug-only=loop-unroll -passes='require<opt-remark-emit>,unroll' 2>&1 | FileCheck %s
 ; REQUIRES: asserts
 
 ; Make sure we use the profile information correctly to peel-off 3 iterations
 ; from the loop, and update the branch weights for the peeled loop properly.
 
 ; CHECK: Loop Unroll: F[basic]
 ; CHECK: PEELING loop %for.body with iteration count 3!
 ; CHECK: Loop Unroll: F[optsize]
 ; CHECK-NOT: PEELING
 
+; Confirm that no peeling occurs when we are performing full unrolling.
+; RUN: opt < %s -S -debug-only=loop-unroll -passes='require<opt-remark-emit>,loop(unroll-full)' 2>&1 | FileCheck %s --check-prefix=FULLUNROLL
+; FULLUNROLL-NOT: PEELING
+
 ; CHECK-LABEL: @basic
 ; CHECK: br i1 %{{.*}}, label %[[NEXT0:.*]], label %for.cond.for.end_crit_edge, !prof !1
 ; CHECK: [[NEXT0]]:
 ; CHECK: br i1 %{{.*}}, label %[[NEXT1:.*]], label %for.cond.for.end_crit_edge, !prof !2
 ; CHECK: [[NEXT1]]:
 ; CHECK: br i1 %{{.*}}, label %[[NEXT2:.*]], label %for.cond.for.end_crit_edge, !prof !3
 ; CHECK: [[NEXT2]]:
 ; CHECK: br i1 %{{.*}}, label %for.body, label %{{.*}}, !prof !4