[unroll] Split full exact and full bound unroll costing [NFC]

[reames]

Summary

This change should be NFC. It's posted for review mostly to make sure others are happy with the names I'm introducing for "exact full unroll" and "bounded full unroll". The motivation here is that our cost model for bounded unrolling is too aggressive - it gives benefits for exits we aren't going to prune - but I also just think the new version of the code is a lot easier to follow.

[reames]

Further simplify - despite structure of existing code, shouldFullUnroll doesn't modify it's UP param.

[lebedev.ri]

I'm not sure i'm ready to comment on that whole logic, or whether the change is NFC, but the names don't seem particularly wrong there.

[reames]

ping

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

957

nit: it might also be a good opportunity to limit the scope of UnrollFactor to this block, e.g. by if (auto UnrollFactor = shouldFullUnroll(L, TTI, DT, SE, EphValues, TripCount, UCE, UP)) {}

[nikic]

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

951

All copies of some exit test, not necessarily the latch exit test.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

shouldPragmaUnroll(Loop *L, const PragmaInfo &PInfo,
   return None;
 }
 
 static Optional<unsigned> shouldFullUnroll(
     Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT,
     ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
     const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE,
     const TargetTransformInfo::UnrollingPreferences &UP) {
+  assert(FullUnrollTripCount && "should be non-zero!");
 
-  if (!FullUnrollTripCount || FullUnrollTripCount >= UP.FullUnrollMaxCount)
+  if (FullUnrollTripCount >= UP.FullUnrollMaxCount)
     return None;
 
   // When computing the unrolled size, note that BEInsns are not replicated
   // like the rest of the loop body.
   if (UCE.getUnrolledLoopSize(UP) < UP.Threshold)
     return FullUnrollTripCount;
 
   // The loop isn't that small, but we still can fully unroll it if that
if (ExplicitUnroll && TripCount != 0) {
       // 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.
+  // 3rd priority is exact full unrolling.  This will eliminate all copies
+  // of some exit test.
+  UP.Count = 0;
+  if (TripCount) {
+    UP.Count = TripCount;
+    UnrollFactor =
+      shouldFullUnroll(L, TTI, DT, SE, EphValues, TripCount, UCE, UP);
+    if (UnrollFactor) {
+      UP.Count = *UnrollFactor;
+      UseUpperBound = false;
+      return ExplicitUnroll;
+    }
+  }
 
+  // 4th priority is bounded unrolling.
   // 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;
-
+  // Note that the cost of bounded unrolling is always strictly greater than
+  // cost of exact full unrolling.  As such, if we have an exact count and
+  // found it unprofitable, we'll never chose to bounded unroll.
+  if (!TripCount && MaxTripCount && (UP.UpperBound || MaxOrZero) &&
+      MaxTripCount <= UnrollMaxUpperBound) {
+    UP.Count = MaxTripCount;
     UnrollFactor =
-      shouldFullUnroll(L, TTI, DT, SE, EphValues, FullUnrollTripCount, UCE, UP);
-
-  // if shouldFullUnroll can do the unrolling, some side parameteres should be
-  // set
+      shouldFullUnroll(L, TTI, DT, SE, EphValues, MaxTripCount, UCE, UP);
     if (UnrollFactor) {
       UP.Count = *UnrollFactor;
-    UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
+      UseUpperBound = true;
       return ExplicitUnroll;
-  } else {
-    UP.Count = FullUnrollTripCount;
+    }
   }
 
-  // 4th priority is loop peeling.
+  // 5th priority is loop peeling.
   computePeelCount(L, LoopSize, PP, TripCount, DT, SE, UP.Threshold);
   if (PP.PeelCount) {
     UP.Runtime = false;
     UP.Count = 1;
     return ExplicitUnroll;
   }
 
   // Before starting partial unrolling, set up.partial to true,
   // if user explicitly asked  for unrolling
   if (TripCount)
     UP.Partial |= ExplicitUnroll;
 
-  // 5th priority is partial unrolling.
+  // 6th priority is partial unrolling.
   // Try partial unroll only when TripCount could be statically calculated.
   UnrollFactor = shouldPartialUnroll(LoopSize, TripCount, UCE, UP);
 
   if (UnrollFactor) {
     UP.Count = *UnrollFactor;
 
     if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
         UP.Count != TripCount)
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.
+  // 7th 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) {