[LoopUnroll] Discount uniform instructions in cost models

[reames]

Summary

This patch updates the cost models for loop unrolling to discount the cost of a loop invariant expression on all but one iteration. The reasoning here is that such an expression (as determined by SCEV) will be CSEd once the loop is unrolled. Note that SCEVs reasoning will find things which can be invariant, not simply those outside the loop.

Note that unrolling currently has two cost models. One very very simple for partial and runtime unrolling, one much more complicated for full unrolling. The second was already handled, this case is the former.

[fhahn]

Reviewers, I am not entirely sure this is the right approach. The obvious alternative is to generalize the full unrolling cost model to handle partial unrolling. As detailed below, the alternative looks non-trivial, and I decided against it. I do see the argument for that being the right approach though, so if you want to just reject this patch outright, I won't argue.

Agreed, this is going to be tricky, as the full unrolling cost-model tries hard to estimate what can be eliminated through full unrolling, which would need a lot of adjustments for partial unrolling. Moving forward with improving them separately seems reasonable to me for now.

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

40 ↗

(On Diff #305320)

Unless I am missing something, It seems like there's a test case missing for this change? Would it be possible to add one?

This could also be split into 2 separate patches, to make it slightly easier to pin-point potential regressions, but I am not sure if that's worth it.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

831

LoopSizeEstimator iterates over the whole loop body on construction, but it might not be used. Would it be possible to change it to compute the size on demand and cache it for further accesses?

[xbolva00]

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

747

Typo

[reames]

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

40 ↗

(On Diff #305320)

Yep, I missed a test, thanks for catching.

I wanted them grouped since the full unroll does use the estimator along one path. It felt "odd" to have some looks fully unrolled on uniform, and some not. No strong preference though.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

747

Will fix, thanks.

831

Can do. Need to do that for the follow on, I just tried to keep this one simple.

[reames]

Address review comments

[samparker]

This looks sensible to me and a step in the right direction. Have you ran any benchmarks? Would be good to know, at least, that this isn't causing any obvious regressions.

[reames]

In D91481#2410666, @samparker wrote:

This looks sensible to me and a step in the right direction. Have you ran any benchmarks? Would be good to know, at least, that this isn't causing any obvious regressions.

I haven't. I'm not particularly setup to do so easily either.

[fhahn]

In D91481#2411958, @reames wrote:

In D91481#2410666, @samparker wrote:

This looks sensible to me and a step in the right direction. Have you ran any benchmarks? Would be good to know, at least, that this isn't causing any obvious regressions.

I haven't. I'm not particularly setup to do so easily either.

It might be helpful to build llvm-test-suite and check the impact on the number of unrolled loops using statistics (-DTEST_SUITE_COLLECT_STATS)? That should give a rough idea on how broad the impact is going to be, without having actual HW for benchmarking.

[reames]

In D91481#2412365, @fhahn wrote:

In D91481#2411958, @reames wrote:

In D91481#2410666, @samparker wrote:

This looks sensible to me and a step in the right direction. Have you ran any benchmarks? Would be good to know, at least, that this isn't causing any obvious regressions.

I haven't. I'm not particularly setup to do so easily either.

It might be helpful to build llvm-test-suite and check the impact on the number of unrolled loops using statistics (-DTEST_SUITE_COLLECT_STATS)? That should give a rough idea on how broad the impact is going to be, without having actual HW for benchmarking.

This seems like overkill. We have no reason to expect the impact from this to be high or negative for that matter. I would strongly prefer simply landing and watching the bots.

[Whitney]

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

778

Do we need a test case for this case where the loop is not unrolled because the entire loop body is uniform?

[reames]

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

778

Any suggestions on how to write one? This was mostly defensive programming. Every loop structure I can think of is either a) infinite, or b) involves at least two instructions. Given BEInst is configurable (why?) the later isn't quite enough to fully disallow the case.

[Whitney]

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

778

I was having problem picturing this scenario, that's why was thinking a test case would help.
BEInsns is configureable due to it is compared with results from TTI?

794

Given that unsigned LoopSize = Metrics.NumInsts;, and NumInsts += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);, should we increment Count by TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize); instead of 1?

[reames]

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

794

Yes, yes we should. Thank you for catching this!

[reames]

Address review comment on costing.

I didn't add a separate test, mostly because it's not clear to me which cases the cost model returns a interesting result. If anyone has a suggestion, happy to add.

[reames]

Appears to have bit rotten while waiting for review.

[reames]

Refresh - still missing a dedicated test, expect that tomorrow.

[reames]

Add a test to demonstrate effect.

[reames]

ping

[reames]

ping

[reames]

ping x3

[fhahn]

LGTM, thanks!

[nikic]

The reasoning here is that such an expression (as determined by SCEV) will be CSEd once the loop is unrolled.

Is that really the case? I don't think unrolling itself does any CSE, and runtime unrolling is run at the very end of the pipeline, so we don't have any EarlyCSE or GVN passes after it.

Also, the converse question: Why have invariant instructions not been hoisted by LICM before unrolling is reached?

[reames]

In D91481#2783436, @nikic wrote:

The reasoning here is that such an expression (as determined by SCEV) will be CSEd once the loop is unrolled.

Is that really the case? I don't think unrolling itself does any CSE, and runtime unrolling is run at the very end of the pipeline, so we don't have any EarlyCSE or GVN passes after it.

If this is a problem in practice, we can add simple CSE to the unroll transform.

Also, the converse question: Why have invariant instructions not been hoisted by LICM before unrolling is reached?

This uses SCEV's notion of invariant, not Loops. As an example, LIV udiv LIV2 is invariant, but can't be hoisted unless we can prove LIV2 != 0.

[nikic]

In D91481#2783449, @reames wrote:

In D91481#2783436, @nikic wrote:

The reasoning here is that such an expression (as determined by SCEV) will be CSEd once the loop is unrolled.

Is that really the case? I don't think unrolling itself does any CSE, and runtime unrolling is run at the very end of the pipeline, so we don't have any EarlyCSE or GVN passes after it.

If this is a problem in practice, we can add simple CSE to the unroll transform.

Without having a CSE after unrolling, it's not immediately clear to me why this change would make sense from a cost-modelling perspective. It models these instructions as free, but (without CSE) they will not be free.

Also, the converse question: Why have invariant instructions not been hoisted by LICM before unrolling is reached?

This uses SCEV's notion of invariant, not Loops. As an example, LIV udiv LIV2 is invariant, but can't be hoisted unless we can prove LIV2 != 0.

Unfortunately, using SCEVs notion of invariance is rather problematic here, because it requires creating SCEV expressions for every single instruction in the loop. This has predictable impact on compile-time: https://llvm-compile-time-tracker.com/compare.php?from=963495f0d4b5a0707f82b6c6454f42f3aa52da9b&to=39492e37b8285c2ccc8a58136191a011c590470c&stat=instructions

[reames]

Restructured for compile time.

[reames]

Further optimize for compile time.

@nikic Could you share new numbers for this version please?

[nikic]

New compile-time: https://llvm-compile-time-tracker.com/compare.php?from=33e41eaecdd7f71184b0bc9dbfdc2892aa45534a&to=bdf43c851f0f5f99df40af83f2d696df8babe7a8&stat=instructions

It's worth mentioning that contrary to your first patch (which had near zero impact on CTMark codegen), I'm seeing some significant code size changes with the new version: https://llvm-compile-time-tracker.com/compare.php?from=33e41eaecdd7f71184b0bc9dbfdc2892aa45534a&to=bdf43c851f0f5f99df40af83f2d696df8babe7a8&stat=size-text This might indicate a bug in the new implementation.

[reames]

Closing stale phabricator review. No longer actively working on this, if someone wants to pick it up, feel free.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

else
     return MaxPercentThresholdBoost;
 }
 
 // Produce an estimate of the unrolled cost of the specified loop.  This
 // is used to a) produce a cost estimate for partial unrolling and b) to
 // cheaply estimate cost for full unrolling when we don't want to symbolically
 // evaluate all iterations.
 class UnrollCostEstimator {
+  Loop &TheLoop;
+  const TargetTransformInfo &TTI;
+  ScalarEvolution &SE;
+  // Note: Both "size" fields here are in units of TTI->getUserCost(, CodeSize),
+  // not instruction counts.
   const unsigned LoopSize;
+  Optional<unsigned> UniformSize;
 
 public:
-  UnrollCostEstimator(Loop &L, unsigned LoopSize) : LoopSize(LoopSize) {}
+  UnrollCostEstimator(Loop &L, const TargetTransformInfo &TTI,
+                      ScalarEvolution &SE, unsigned LoopSize)
+    : TheLoop(L), TTI(TTI), SE(SE), LoopSize(LoopSize) {}
+
+
+  bool
+  isUnrolledLoopUnderThreshold(TargetTransformInfo::UnrollingPreferences &UP,
+                               unsigned Threshold) {
+    // Check the cheap form first before falling back to the expensive
+    // SCEV queries.  Most loops are small, so the expensive path should
+    // rarely run.
+    if (getUnrolledLoopSize(UP, false) < Threshold)
+      return true;
+    return getUnrolledLoopSize(UP, true) < Threshold;
+  }
+
+private:
 
   // Returns loop size estimation for unrolled loop, given the unrolling
   // configuration specified by UP.
-  uint64_t getUnrolledLoopSize(TargetTransformInfo::UnrollingPreferences &UP) {
-    assert(LoopSize >= UP.BEInsns &&
+  uint64_t getUnrolledLoopSize(TargetTransformInfo::UnrollingPreferences &UP,
+                               bool UseUniform) {
+    unsigned UniformSize = UseUniform ? computeUniformInstCost() : 0;
+    assert(LoopSize >= (UP.BEInsns + UniformSize) &&
            "LoopSize should not be less than BEInsns!");
-    return (uint64_t)(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
+    return (uint64_t)(LoopSize - UP.BEInsns - UniformSize) * UP.Count +
+      UP.BEInsns + UniformSize;
+  }
+
+  unsigned computeUniformInstCost() {
+    if (UniformSize)
+      return *UniformSize;
+
+    // We want to use SCEV's notion of invariance to handle cases such as:
+    // loop:
+    //   %a = udiv i32 %arg1, %arg2
+    //   %b = zext i32 %a to i64
+    // (both a and b are invariant)
+    // However, computing SCEVs is expensive.  We defer that work until
+    // we've found at least one trivially invariant operation.  For an
+    // example like the above, we must have at least one trivially
+    // invariant instruction (%a in this example).
+    const bool CouldBeInvariant =
+      llvm::any_of(TheLoop.blocks(),
+                   [&](BasicBlock *BB) {
+                     return llvm::any_of(*BB, [&](Instruction &I) {
+                       return TheLoop.hasLoopInvariantOperands(&I);
+                     });
+                   });
+    if (!CouldBeInvariant) {
+      UniformSize = 0;
+      return *UniformSize;
+    }
+    InstructionCost Size = 0;
+    for (BasicBlock *BB : TheLoop.blocks())
+      for (Instruction &I : *BB)
+        if (SE.isSCEVable(I.getType()) &&
+            SE.isLoopInvariant(SE.getSCEV(&I), &TheLoop))
+          Size += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
+    UniformSize = *Size.getValue();
+    return *UniformSize;
   }
 };
 
 // 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);
+  UnrollCostEstimator UCE(*L, TTI, SE, LoopSize);
 
   // Check for explicit Count.
   // 1st priority is unroll count set by "unroll-count" option.
   bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
   if (UserUnrollCount) {
     UP.Count = UnrollCount;
     UP.AllowExpensiveTripCount = true;
     UP.Force = true;
-    if (UP.AllowRemainder && UCE.getUnrolledLoopSize(UP) < UP.Threshold)
+    if (UP.AllowRemainder && UCE.isUnrolledLoopUnderThreshold(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)
+        UCE.isUnrolledLoopUnderThreshold(UP, PragmaUnrollThreshold))
       return true;
   }
   bool PragmaFullUnroll = hasUnrollFullPragma(L);
   if (PragmaFullUnroll && TripCount != 0) {
     UP.Count = TripCount;
-    if (UCE.getUnrolledLoopSize(UP) < PragmaUnrollThreshold)
+    if (UCE.isUnrolledLoopUnderThreshold(UP, PragmaUnrollThreshold))
       return false;
   }
 
   bool PragmaEnableUnroll = hasUnrollEnablePragma(L);
   bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
                         PragmaEnableUnroll || UserUnrollCount;
 
   if (ExplicitUnroll && TripCount != 0) {
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 (UCE.isUnrolledLoopUnderThreshold(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 (!UP.Partial) {
                         << "-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)
+      if (!UCE.isUnrolledLoopUnderThreshold(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)
+               !UCE.isUnrolledLoopUnderThreshold(UP, UP.PartialThreshold))
           UP.Count >>= 1;
       }
       if (UP.Count < 2) {
         if (PragmaEnableUnroll)
           ORE->emit([&]() {
             return OptimizationRemarkMissed(DEBUG_TYPE,
                                             "UnrollAsDirectedTooLarge",
                                             L->getStartLoc(), L->getHeader())
if (!UP.Runtime) {
     return false;
   }
   if (UP.Count == 0)
     UP.Count = UP.DefaultUnrollRuntimeCount;
 
   // Reduce unroll count to be the largest power-of-two factor of
   // the original count which satisfies the threshold limit.
   while (UP.Count != 0 &&
-         UCE.getUnrolledLoopSize(UP) > UP.PartialThreshold)
+         !UCE.isUnrolledLoopUnderThreshold(UP, UP.PartialThreshold))
     UP.Count >>= 1;
 
 #ifndef NDEBUG
   unsigned OrigCount = UP.Count;
 #endif
 
   if (!UP.AllowRemainder && UP.Count != 0 && (TripMultiple % UP.Count) != 0) {
     while (UP.Count != 0 && TripMultiple % UP.Count != 0)