[WIP][NFC] factor out unrolling decision logic

[Ali-Sed]

Summary

moving runtime flag to the Logic

minor bug

[WIP] minor bug

[WIP] changes by clang-format

[WIP] merge conflicts

[WIP][UNROLLING] merge conflicts

Merge branch 'main' of github.com:Ali-Sed/llvm-project into main

[Ali-Sed]

[WIP] Reformatting using clang-reformat

[Ali-Sed]

Squashing all commits

[mtrofin]

Could you update the commit message (both git and here) to say what the patch accomplishes, i.e. "[NFC] factor out unrolling decision logic" or something like that - nfc because it should just be a refactoring. The message can clarify why - e.g. so it may simplify exploring alternative decision-making mechanisms.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

756

use verb names for functions, e.g. shouldUnroll. That also explains what the return means.

Also add a comment above it, like computeUnrollCount has.

does MaxTripCount need to be passed by-ref?

could the return of this function be rather a more complex object, where the TripCount and TripMultiple were returned - I haven't looked yet at how it's used, is it that the caller proposes such values, and this adjusts them?

767

nit: if UserUnrollCount doesn't change later, just const - it. The reader then understands this is meant to help with understanding the code. Same below.

828

why remove the comment?

960

capital 'T'.

And/but, if you want to do this for clarity wrt what the params mean, 3 options:

1. no variable name. Instead (the way commonly seen in the codebase):

unrollingLogic(/*TryFullUnroll=*/true, ...)

2. just do this (but it's not common in this codebase)

const bool DoFullUnroll = true;
const bool DoPartialUnroll = false;

3. define an enum class:

enum class UnrollingOption : bool {

Full,
Partial

};

...you see where this is going

968

isn't clear where the 1-3 priorities are, just add a comment about that

977

it seems like the only difference between the first call and this is whether to try full unroll. We could, instead, return an enum from <what's currently called unrollingLogic>.

*or* factor that function in 2: shouldFullyUnroll, shouldPartiallyUnrol

1008–1009

don't comment code, remove it instead (if you don't need it)

[Ali-Sed]

Adding NFC tag

[Ali-Sed]

Solving the problems mentioned in the review

[dmgreen]

The latest revision appears to be missing most of the changes. You may want to squash several commits together in git, and make sure the commit message properly explains the reasoning behind the patch.

Do you intend this to go into LLVM, or are you still experimenting at this point? It may be best to make sure what you come up with will have practical use before making a lot of changes in llvm itself. My understanding is that this code is (overly) complex but it is the order it is for deliberate reasons. All the existing tests have to keep passing, if they are not already.

I would consider runtime unrolling to be the most interesting part of machine learning loop unroll factors, at least on many cpu's.

[Ali-Sed]

[WIP][NFC] Adding enum for unrolling option and adding MyDebug for priting

[Ali-Sed]

In D105173#2861546, @dmgreen wrote:

The latest revision appears to be missing most of the changes. You may want to squash several commits together in git, and make sure the commit message properly explains the reasoning behind the patch.

Do you intend this to go into LLVM, or are you still experimenting at this point? It may be best to make sure what you come up with will have practical use before making a lot of changes in llvm itself. My understanding is that this code is (overly) complex but it is the order it is for deliberate reasons. All the existing tests have to keep passing, if they are not already.

I would consider runtime unrolling to be the most interesting part of machine learning loop unroll factors, at least on many cpu's.

Thanks a lot for your feedback.
I've just squashed all of the commits now and used "arc diff" for a group of commits and it seems it solved the problem.

I've been decoupling the logic, that unrolling pass uses, from the rest of it. So in a near future, I'll be able to replace it with a learning model.

For now, full unrolling and partial unrolling are the main goals. But, yes definitely! the logic behind the runtime unrolling could be a very interesting choice to be replaced with a learning model too.

[Ali-Sed]

"Adding ShouldContinue as the return value of unrolling logic"

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

public:
   // configuration specified by UP.
   uint64_t getUnrolledLoopSize(TargetTransformInfo::UnrollingPreferences &UP) {
     assert(LoopSize >= UP.BEInsns &&
            "LoopSize should not be less than BEInsns!");
     return (uint64_t)(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
   }
 };
 
-// Returns true if unroll count was set explicitly.
-// Calculates unroll count and writes it to UP.Count.
-// Unless IgnoreUser is true, will also use metadata and command-line options
-// that are specific to to the LoopUnroll pass (which, for instance, are
-// irrelevant for the LoopUnrollAndJam pass).
-// FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
-// many LoopUnroll-specific options. The shared functionality should be
-// refactored into it own function.
-bool llvm::computeUnrollCount(
-    Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
-    ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
-    OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount,
-    bool MaxOrZero, unsigned &TripMultiple, unsigned LoopSize,
+bool unrollingLogic(bool FullOrPartial, Loop *L, const TargetTransformInfo &TTI,
+                    DominatorTree &DT, ScalarEvolution &SE,
+                    const SmallPtrSetImpl<const Value *> &EphValues,
+                    OptimizationRemarkEmitter *ORE, bool MaxOrZero,
+                    unsigned LoopSize, unsigned &TripMultiple,
+                    unsigned &TripCount, unsigned &MaxTripCount,
+                    UnrollCostEstimator UCE,
                     TargetTransformInfo::UnrollingPreferences &UP,
-    TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound) {
+                    TargetTransformInfo::PeelingPreferences &PP,
+                    bool &UseUpperBound) {
 
-  UnrollCostEstimator UCE(*L, LoopSize);
+  bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
 
-  // Use an explicit peel count that has been specified for testing. In this
-  // case it's not permitted to also specify an explicit unroll count.
-  if (PP.PeelCount) {
-    if (UnrollCount.getNumOccurrences() > 0) {
-      report_fatal_error("Cannot specify both explicit peel count and "
-                         "explicit unroll count");
-    }
-    UP.Count = 1;
-    UP.Runtime = false;
-    return true;
-  }
+  bool PragmaFullUnroll = hasUnrollFullPragma(L);
+  unsigned PragmaCount = unrollCountPragmaValue(L);
+  bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
+  bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
+                        PragmaEnableUnroll || UserUnrollCount;
 
-  // Check for explicit Count.
-  // 1st priority is unroll count set by "unroll-count" option.
-  bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
-  if (UserUnrollCount) {
+  if (PragmaFullUnroll)
+    ORE->emit([&]() {
+      return 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.";
+    });
+
+  if (FullOrPartial) {
+
+    // Using unroll pragma
+    if (UnrollCount.getNumOccurrences() > 0) {
       UP.Count = UnrollCount;
       UP.AllowExpensiveTripCount = true;
       UP.Force = true;
       if (UP.AllowRemainder && UCE.getUnrolledLoopSize(UP) < UP.Threshold)
         return true;
     }
 
-  // 2nd priority is unroll count set by pragma.
-  unsigned PragmaCount = unrollCountPragmaValue(L);
     if (PragmaCount > 0) {
       UP.Count = PragmaCount;
       UP.Runtime = true;
       UP.AllowExpensiveTripCount = true;
       UP.Force = true;
       if ((UP.AllowRemainder || (TripMultiple % PragmaCount == 0)) &&
           UCE.getUnrolledLoopSize(UP) < PragmaUnrollThreshold)
         return true;
     }
-  bool PragmaFullUnroll = hasUnrollFullPragma(L);
+
     if (PragmaFullUnroll && TripCount != 0) {
       UP.Count = TripCount;
       if (UCE.getUnrolledLoopSize(UP) < PragmaUnrollThreshold)
         return false;
     }
 
-  bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
-  bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
-                        PragmaEnableUnroll || UserUnrollCount;
-
     if (ExplicitUnroll && TripCount != 0) {
       // If the loop has an unrolling pragma, we want to be more aggressive with
       // unrolling limits. Set thresholds to at least the PragmaUnrollThreshold
       // value which is larger than the default limits.
       UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
       UP.PartialThreshold =
           std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
     }
 
-  // 3rd priority is full unroll count.
-  // Full unroll makes sense only when TripCount or its upper bound could be
-  // statically calculated.
-  // Also we need to check if we exceed FullUnrollMaxCount.
-  // If using the upper bound to unroll, TripMultiple should be set to 1 because
-  // we do not know when loop may exit.
-
-  // We can unroll by the upper bound amount if it's generally allowed or if
-  // we know that the loop is executed either the upper bound or zero times.
-  // (MaxOrZero unrolling keeps only the first loop test, so the number of
-  // loop tests remains the same compared to the non-unrolled version, whereas
-  // the generic upper bound unrolling keeps all but the last loop test so the
-  // number of loop tests goes up which may end up being worse on targets with
-  // constrained branch predictor resources so is controlled by an option.)
-  // In addition we only unroll small upper bounds.
     unsigned FullUnrollMaxTripCount = MaxTripCount;
     if (!(UP.UpperBound || MaxOrZero) ||
         FullUnrollMaxTripCount > UnrollMaxUpperBound)
       FullUnrollMaxTripCount = 0;
 
     // UnrollByMaxCount and ExactTripCount cannot both be non zero since we only
     // compute the former when the latter is zero.
     unsigned ExactTripCount = TripCount;
     assert((ExactTripCount == 0 || FullUnrollMaxTripCount == 0) &&
            "ExtractTripCount and UnrollByMaxCount cannot both be non zero.");
 
     unsigned FullUnrollTripCount =
         ExactTripCount ? ExactTripCount : FullUnrollMaxTripCount;
     UP.Count = FullUnrollTripCount;
     if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
       // When computing the unrolled size, note that BEInsns are not replicated
       // like the rest of the loop body.
       if (UCE.getUnrolledLoopSize(UP) < UP.Threshold) {
         UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
         TripCount = FullUnrollTripCount;
         TripMultiple = UP.UpperBound ? 1 : TripMultiple;
         return ExplicitUnroll;
       } else {
         // The loop isn't that small, but we still can fully unroll it if that
         // helps to remove a significant number of instructions.
         // To check that, run additional analysis on the loop.
         if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
                 L, FullUnrollTripCount, DT, SE, EphValues, TTI,
                 UP.Threshold * UP.MaxPercentThresholdBoost / 100,
                 UP.MaxIterationsCountToAnalyze)) {
           unsigned Boost =
               getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
           if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
             UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
             TripCount = FullUnrollTripCount;
             TripMultiple = UP.UpperBound ? 1 : TripMultiple;
             return ExplicitUnroll;
           }
         }
       }
     }
-
-  // 4th priority is loop peeling.
-  computePeelCount(L, LoopSize, PP, TripCount, SE, UP.Threshold);
-  if (PP.PeelCount) {
-    UP.Runtime = false;
-    UP.Count = 1;
-    return ExplicitUnroll;
-  }
-
-  // 5th priority is partial unrolling.
-  // Try partial unroll only when TripCount could be statically calculated.
+  } else {
     if (TripCount) {
       UP.Partial |= ExplicitUnroll;
       if (!UP.Partial) {
         LLVM_DEBUG(dbgs() << "  will not try to unroll partially because "
                           << "-unroll-allow-partial not given\n");
         UP.Count = 0;
         return false;
       }
       if (UP.Count == 0)
         UP.Count = TripCount;
       if (UP.PartialThreshold != NoThreshold) {
         // Reduce unroll count to be modulo of TripCount for partial unrolling.
         if (UCE.getUnrolledLoopSize(UP) > UP.PartialThreshold)
           UP.Count =
               (std::max(UP.PartialThreshold, UP.BEInsns + 1) - UP.BEInsns) /
               (LoopSize - UP.BEInsns);
         if (UP.Count > UP.MaxCount)
           UP.Count = UP.MaxCount;
         while (UP.Count != 0 && TripCount % UP.Count != 0)
           UP.Count--;
         if (UP.AllowRemainder && UP.Count <= 1) {
           // If there is no Count that is modulo of TripCount, set Count to
           // largest power-of-two factor that satisfies the threshold limit.
           // As we'll create fixup loop, do the type of unrolling only if
           // remainder loop is allowed.
           UP.Count = UP.DefaultUnrollRuntimeCount;
           while (UP.Count != 0 &&
                  UCE.getUnrolledLoopSize(UP) > UP.PartialThreshold)
             UP.Count >>= 1;
         }
         if (UP.Count < 2) {
           if (PragmaEnableUnroll)
             ORE->emit([&]() {
               return OptimizationRemarkMissed(DEBUG_TYPE,
                                               "UnrollAsDirectedTooLarge",
                                               L->getStartLoc(), L->getHeader())
                      << "Unable to unroll loop as directed by unroll(enable) "
                         "pragma "
                         "because unrolled size is too large.";
             });
           UP.Count = 0;
         }
       } else {
         UP.Count = TripCount;
       }
       if (UP.Count > UP.MaxCount)
         UP.Count = UP.MaxCount;
       if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
           UP.Count != TripCount)
         ORE->emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE,
                                           "FullUnrollAsDirectedTooLarge",
                                           L->getStartLoc(), L->getHeader())
                  << "Unable to fully unroll loop as directed by unroll pragma "
                     "because "
                     "unrolled size is too large.";
         });
       LLVM_DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count
                         << "\n");
       return ExplicitUnroll;
     }
+  }
+  UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
+
+  return ExplicitUnroll;
+}
+// Returns true if unroll count was set explicitly.
+// Calculates unroll count and writes it to UP.Count.
+// Unless IgnoreUser is true, will also use metadata and command-line options
+// that are specific to to the LoopUnroll pass (which, for instance, are
+// irrelevant for the LoopUnrollAndJam pass).
+// FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
+// many LoopUnroll-specific options. The shared functionality should be
+// refactored into it own function.
+
+bool llvm::computeUnrollCount(
+    Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
+    ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
+    OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount,
+    bool MaxOrZero, unsigned &TripMultiple, unsigned LoopSize,
+    TargetTransformInfo::UnrollingPreferences &UP,
+    TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound) {
+
+  UnrollCostEstimator UCE(*L, LoopSize);
+
+  // Use an explicit peel count that has been specified for testing. In this
+  // case it's not permitted to also specify an explicit unroll count.
+  if (PP.PeelCount) {
+    if (UnrollCount.getNumOccurrences() > 0) {
+      report_fatal_error("Cannot specify both explicit peel count and "
+                         "explicit unroll count");
+    }
+    UP.Count = 1;
+    UP.Runtime = false;
+    return true;
+  }
+
+  bool tryFullUnroll = true;
+
+  bool ExplicitUnroll = false;
+
+  ExplicitUnroll = unrollingLogic(tryFullUnroll, L, TTI, DT, SE, EphValues, ORE,
+                                  MaxOrZero, LoopSize, TripMultiple, TripCount,
+                                  MaxTripCount, UCE, UP, PP, UseUpperBound);
+
+  // 4th priority is loop peeling.
+  computePeelCount(L, LoopSize, PP, TripCount, SE, UP.Threshold);
+  if (PP.PeelCount) {
+    UP.Runtime = false;
+    UP.Count = 1;
+    return ExplicitUnroll;
+  }
+  tryFullUnroll = false;
+
+  ExplicitUnroll = unrollingLogic(tryFullUnroll, L, TTI, DT, SE, EphValues, ORE,
+                                  MaxOrZero, LoopSize, TripMultiple, TripCount,
+                                  MaxTripCount, UCE, UP, PP, UseUpperBound);
+
   assert(TripCount == 0 &&
          "All cases when TripCount is constant should be covered here.");
-  if (PragmaFullUnroll)
-    ORE->emit([&]() {
-      return 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.";
-    });
 
   // 6th priority is runtime unrolling.
   // Don't unroll a runtime trip count loop when it is disabled.
   if (hasRuntimeUnrollDisablePragma(L)) {
     UP.Count = 0;
     return false;
   }
 
if (auto ProfileTripCount = getLoopEstimatedTripCount(L)) {
       if (*ProfileTripCount < FlatLoopTripCountThreshold)
         return false;
       else
         UP.AllowExpensiveTripCount = true;
     }
   }
 
   // Reduce count based on the type of unrolling and the threshold values.
-  UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
+  // UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
+
   if (!UP.Runtime) {
     LLVM_DEBUG(
         dbgs() << "  will not try to unroll loop with runtime trip count "
                << "-unroll-runtime not given\n");
     UP.Count = 0;
     return false;
   }
   if (UP.Count == 0)
LLVM_DEBUG(
                   "specific or because the loop contains a convergent "
                   "instruction), so unroll count must divide the trip "
                   "multiple, "
                << TripMultiple << ".  Reducing unroll count from " << OrigCount
                << " to " << UP.Count << ".\n");
 
     using namespace ore;
 
-    if (PragmaCount > 0 && !UP.AllowRemainder)
+    if (unrollCountPragmaValue(L) > 0 && !UP.AllowRemainder)
       ORE->emit([&]() {
         return OptimizationRemarkMissed(DEBUG_TYPE,
                                         "DifferentUnrollCountFromDirected",
                                         L->getStartLoc(), L->getHeader())
                << "Unable to unroll loop the number of times directed by "
                   "unroll_count pragma because remainder loop is restricted "
                   "(that could architecture specific or because the loop "
                   "contains a convergent instruction) and so must have an "