[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

761

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?

772

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.

948–952

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

963

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

972

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

978–979

why remove the comment?

1002–1003

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

struct EstimatedUnrollCost {
   /// The estimated cost after unrolling.
   unsigned UnrolledCost;
 
   /// The estimated dynamic cost of executing the instructions in the
   /// rolled form.
   unsigned RolledDynamicCost;
 };
 
+enum class UnrollingOption : bool {
+  Full,
+  Partial,
+};
+
 } // end anonymous namespace
 
 /// Figure out if the loop is worth full unrolling.
 ///
 /// Complete loop unrolling can make some loads constant, and we need to know
 /// if that would expose any further optimization opportunities.  This routine
 /// estimates this optimization.  It computes cost of unrolled loop
 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
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;
   }
 };
 
-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) {
+bool shouldUnroll(UnrollingOption UO, Loop *L, const TargetTransformInfo &TTI,
+                  unsigned LoopSize, unsigned &TripMultiple, unsigned TripCount,
+                  unsigned MaxTripCount, UnrollCostEstimator UCE,
 
-  bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
+  const bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
 
-  bool PragmaFullUnroll = hasUnrollFullPragma(L);
-  unsigned PragmaCount = unrollCountPragmaValue(L);
-  bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
-  bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
+  const bool PragmaFullUnroll = hasUnrollFullPragma(L);
+  const unsigned PragmaCount = unrollCountPragmaValue(L);
+  const bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
+  const bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
                               PragmaEnableUnroll || 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) {
+  if (UO == UnrollingOption::Full) {
 
     // 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;
if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
             UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
             TripCount = FullUnrollTripCount;
             TripMultiple = UP.UpperBound ? 1 : TripMultiple;
             return ExplicitUnroll;
           }
         }
       }
     }
-  } else {
+  }
+
+  if (UO == UnrollingOption::Partial) {
     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 (TripCount) {
                                           "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;
     }
+    DEBUG_WITH_TYPE("mypass", dbgs() << UP.Count);
   }
   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, bool MaxOrZero, unsigned LoopSize, 
-    unsigned &TripMultiple, unsigned &TripCount,  unsigned &MaxTripCount, UnrollCostEstimator UCE, 
-    TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound)
- {
-
-    bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
-
-    bool PragmaFullUnroll = hasUnrollFullPragma(L);
-    unsigned PragmaCount = unrollCountPragmaValue(L);
-    bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
-    bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
-                          PragmaEnableUnroll || 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;
-    }
+    OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount,
+    bool MaxOrZero, unsigned &TripMultiple, unsigned LoopSize,
+    TargetTransformInfo::UnrollingPreferences &UP,
+    TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound) {
 
-  bool tryFullUnroll = true;
+  UnrollCostEstimator UCE(*L, LoopSize);
 
   bool ExplicitUnroll = false;
 
-  ExplicitUnroll = unrollingLogic(tryFullUnroll, L, TTI, DT, SE, EphValues, ORE,
-                                  MaxOrZero, LoopSize, TripMultiple, TripCount,
-                                  MaxTripCount, UCE, UP, PP, UseUpperBound);
+  ExplicitUnroll =
+      shouldUnroll(UnrollingOption::Full, 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);
+  ExplicitUnroll =
+      shouldUnroll(UnrollingOption::Partial, 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.");
 
   // 6th priority is runtime unrolling.
   // Don't unroll a runtime trip count loop when it is disabled.
   if (hasRuntimeUnrollDisablePragma(L)) {
     UP.Count = 0;
if (L->getHeader()->getParent()->hasProfileData()) {
     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;
 
   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)