[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.

796–804

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

810–811

why remove the comment?

861–862

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

864

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;
   }
 };
 
-
-
-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 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 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){
+  if (FullOrPartial) {
 
     // Using unroll pragma
-    if (UnrollCount.getNumOccurrences() > 0){
+    if (UnrollCount.getNumOccurrences() > 0) {
       UP.Count = UnrollCount;
       UP.AllowExpensiveTripCount = true;
       UP.Force = true;
       if (UP.AllowRemainder && UCE.getUnrolledLoopSize(UP) < UP.Threshold)
         return true;
     }
 
     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;
     }
 
     if (PragmaFullUnroll && TripCount != 0) {
       UP.Count = TripCount;
       if (UCE.getUnrolledLoopSize(UP) < PragmaUnrollThreshold)
         return false;
     }
 
-
-    
     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);
     }
 
     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) {
if (FullUnrollTripCount && FullUnrollTripCount <= UP.FullUnrollMaxCount) {
           if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
             UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
             TripCount = FullUnrollTripCount;
             TripMultiple = UP.UpperBound ? 1 : TripMultiple;
             return ExplicitUnroll;
           }
         }
       }
     }
-  }
-  else{
+  } 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);
-
+  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);
-
-
+  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.");
 
-
   // 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;
   }
 
   // Don't unroll a small upper bound loop unless user or TTI asked to do so.
   if (MaxTripCount && !UP.Force && MaxTripCount < UnrollMaxUpperBound) {
     UP.Count = 0;
     return false;
   }
 
   // Check if the runtime trip count is too small when profile is available.
   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)