Unroll restructure

[evstupac]

Summary

Fix potential overflow.
Use BEInsns instead of constant 2.
Add a function checking if LoopSize meet unroll preferences.

make check passed
spec2000 - build same for all

[mzolotukhin]

Hi,

Please find a couple of question/remarks below:

Fix potential overflow.

Is it possible to compose a test for it?

Use BEInsns instead of constant 2.

Why do we need it? At least, we can make it const I think.

Thanks,
Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

701

s/isLoopSizeMeetUP/doesLoopSizeMeetUP/

Also, what about something like isLoopSizeLessThanThreshold?

706–713

Why can't we just pass PragmaUnrollThreshold/UP.PartialThreshold/UP.Threshold instead of ThresholdType TT?

[evstupac]

Fix potential overflow.

Is it possible to compose a test for it?

That is regarding 32 bits multiplication:

(LoopSize - BEInsns) * UP.Count

I don't think we should make a test here. However I think it is possible.

Use BEInsns instead of constant 2.

Why do we need it? At least, we can make it const I think.

That was comment from hfinkel in D19553.
BEInsns makes code easier to read. As for const value, yes it could be const now, but some architectures may have another value. Moreover loop analysis can point us to some other instruction that could be optimized after unroll. Tat way we'll be able to increase BEInsns.

lib/Transforms/Scalar/LoopUnrollPass.cpp

701

isLoopSizeLessThanThreshold

This function check if LoopSize less than threshold but after unrolling. That way Count and BEInsns make differ.

706–713

In most cases Threshold are in UP, so we need to pass only 2 parameters which is less. Also passing structure reference and its field value as different parameters looks strange.

[evstupac]

PING.

[evstupac]

PING2

[evstupac]

PING3

[mzolotukhin]

lib/Transforms/Scalar/LoopUnrollPass.cpp

706–713

I'd rather create a function that would compute (LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns. I don't see a value in passing a threshold and comparing against it inside the function. It causes code duplication inside and requires an additional parameter.

[evstupac]

Changed according to review comments.

[evstupac]

ping

[mzolotukhin]

LGTM with minor nits.

Thanks,
Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

127

It would make sense to add the initialization to getUnrollingPreferences in BasicTTIImpl.h.

694

Please use verbs for function names and start them from lower-case.

743

Is this unused now?

include/llvm/Analysis/TargetTransformInfo.h

struct UnrollingPreferences {
     // using the appropriate cost threshold, but may not exceed this number
     // (set to UINT_MAX to disable). This does not apply in cases where the
     // loop is being fully unrolled.
     unsigned MaxCount;
     /// Set the maximum unrolling factor for full unrolling. Like MaxCount, but
     /// applies even if full unrolling is selected. This allows a target to fall
     /// back to Partial unrolling if full unrolling is above FullUnrollMaxCount.
     unsigned FullUnrollMaxCount;
+    // Represents number of instructions optimized when "back edge"
+    // becomes "fall through" in unrolled loop.
+    // For now we count a conditional branch on a backedge and a comparison
+    // feeding it.
+    unsigned BEInsns;
     /// Allow partial unrolling (unrolling of loops to expand the size of the
     /// loop body, not only to eliminate small constant-trip-count loops).
     bool Partial;
     /// Allow runtime unrolling (unrolling of loops to expand the size of the
     /// loop body even when the number of loop iterations is not known at
     /// compile time).
     bool Runtime;
     /// Allow generation of a loop remainder (extra iterations after unroll).

lib/Transforms/Scalar/LoopUnrollPass.cpp

static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
   UP.PercentDynamicCostSavedThreshold = 50;
   UP.DynamicCostSavingsDiscount = 100;
   UP.OptSizeThreshold = 0;
   UP.PartialThreshold = UP.Threshold;
   UP.PartialOptSizeThreshold = 0;
   UP.Count = 0;
   UP.MaxCount = UINT_MAX;
   UP.FullUnrollMaxCount = UINT_MAX;
+  UP.BEInsns = 2;
   UP.Partial = false;
   UP.Runtime = false;
   UP.AllowRemainder = true;
   UP.AllowExpensiveTripCount = false;
   UP.Force = false;
 
   // Override with any target specific settings
   TTI.getUnrollingPreferences(L, UP);
DEBUG(dbgs() << "Analysis finished:\n"
                << "RolledDynamicCost: " << RolledDynamicCost << "\n");
   return {{UnrolledCost, RolledDynamicCost}};
 }
 
 /// ApproximateLoopSize - Approximate the size of the loop.
 static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
                                     bool &NotDuplicatable, bool &Convergent,
                                     const TargetTransformInfo &TTI,
-                                    AssumptionCache *AC) {
+                                    AssumptionCache *AC, unsigned BEInsns) {
   SmallPtrSet<const Value *, 32> EphValues;
   CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 
   CodeMetrics Metrics;
   for (BasicBlock *BB : L->blocks())
     Metrics.analyzeBasicBlock(BB, TTI, EphValues);
   NumCalls = Metrics.NumInlineCandidates;
   NotDuplicatable = Metrics.notDuplicatable;
   Convergent = Metrics.convergent;
 
   unsigned LoopSize = Metrics.NumInsts;
 
   // Don't allow an estimate of size zero.  This would allows unrolling of loops
   // with huge iteration counts, which is a compile time problem even if it's
   // not a problem for code quality. Also, the code using this size may assume
   // that each loop has at least three instructions (likely a conditional
   // branch, a comparison feeding that branch, and some kind of loop increment
   // feeding that comparison instruction).
-  LoopSize = std::max(LoopSize, 3u);
+  LoopSize = std::max(LoopSize, BEInsns + 1);
 
   return LoopSize;
 }
 
 // Returns the loop hint metadata node with the given name (for example,
 // "llvm.loop.unroll.count").  If no such metadata node exists, then nullptr is
 // returned.
 static MDNode *GetUnrollMetadataForLoop(const Loop *L, StringRef Name) {
DEBUG(dbgs() << "    Percent cost saved threshold: "
                << PercentDynamicCostSavedThreshold << "%\n");
   DEBUG(dbgs() << "    Unrolled cost: " << UnrolledCost << "\n");
   DEBUG(dbgs() << "    Rolled dynamic cost: " << RolledDynamicCost << "\n");
   DEBUG(dbgs() << "    Percent cost saved: " << PercentDynamicCostSaved
                << "\n");
   return false;
 }
 
+// Returns loop size estimation for unrolled loop.
+static uint64_t UnrolledLoopSize(
+    unsigned LoopSize,
+    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.
 static bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
                                DominatorTree &DT, LoopInfo *LI,
                                ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE,
                                unsigned TripCount, unsigned TripMultiple,
                                unsigned LoopSize,
                                TargetTransformInfo::UnrollingPreferences &UP) {
-  // BEInsns represents number of instructions optimized when "back edge"
-  // becomes "fall through" in unrolled loop.
-  // For now we count a conditional branch on a backedge and a comparison
-  // feeding it.
-  unsigned BEInsns = 2;
   // 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 &&
-        (LoopSize - BEInsns) * UP.Count + BEInsns < UP.Threshold)
+    if (UP.AllowRemainder && UnrolledLoopSize(LoopSize, 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 &&
-        (LoopSize - BEInsns) * UP.Count + BEInsns < PragmaUnrollThreshold)
+        UnrolledLoopSize(LoopSize, UP) < PragmaUnrollThreshold)
       return true;
   }
   bool PragmaFullUnroll = HasUnrollFullPragma(L);
   if (PragmaFullUnroll && TripCount != 0) {
     UP.Count = TripCount;
-    if ((LoopSize - BEInsns) * UP.Count + BEInsns < PragmaUnrollThreshold)
+    if (UnrolledLoopSize(LoopSize, UP) < PragmaUnrollThreshold)
       return false;
   }
 
   bool PragmaEnableUnroll = HasUnrollEnablePragma(L);
   bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
                         PragmaEnableUnroll || UserUnrollCount;
 
   uint64_t UnrolledSize;
 
   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 PragmaThreshold 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 make sense only when TripCount could be staticaly calculated.
   // Also we need to check if we exceed FullUnrollMaxCount.
   if (TripCount && TripCount <= UP.FullUnrollMaxCount) {
     // When computing the unrolled size, note that BEInsns are not replicated
     // like the rest of the loop body.
-    UnrolledSize = (uint64_t)(LoopSize - BEInsns) * TripCount + BEInsns;
-    if (canUnrollCompletely(L, UP.Threshold, 100, UP.DynamicCostSavingsDiscount,
-                            UnrolledSize, UnrolledSize)) {
-      UP.Count = TripCount;
+    if (canUnrollCompletely(L, UP.Threshold, 100, UP.DynamicCostSavingsDiscount,
+                            UnrolledLoopSize(LoopSize, UP),
+                            UnrolledLoopSize(LoopSize, UP))) {
       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, TripCount, DT, *SE, TTI,
               UP.Threshold + UP.DynamicCostSavingsDiscount))
         if (canUnrollCompletely(L, UP.Threshold,
                                 UP.PercentDynamicCostSavedThreshold,
                                 UP.DynamicCostSavingsDiscount,
                                 Cost->UnrolledCost, Cost->RolledDynamicCost)) {
-          UP.Count = TripCount;
           return ExplicitUnroll;
         }
     }
   }
 
   // 4rd priority is partial unrolling.
   // Try partial unroll only when TripCount could be staticaly calculated.
   if (TripCount) {
     if (UP.Count == 0)
       UP.Count = TripCount;
     UP.Partial |= ExplicitUnroll;
     if (!UP.Partial) {
       DEBUG(dbgs() << "  will not try to unroll partially because "
                    << "-unroll-allow-partial not given\n");
       UP.Count = 0;
       return false;
     }
     if (UP.PartialThreshold != NoThreshold) {
       // Reduce unroll count to be modulo of TripCount for partial unrolling.
-      UnrolledSize = (uint64_t)(LoopSize - BEInsns) * UP.Count + BEInsns;
-      if (UnrolledSize > UP.PartialThreshold)
-        UP.Count = (std::max(UP.PartialThreshold, 3u) - BEInsns) /
-                   (LoopSize - BEInsns);
+      if (UnrolledLoopSize(LoopSize, 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 = DefaultUnrollRuntimeCount;
-        UnrolledSize = (LoopSize - BEInsns) * UP.Count + BEInsns;
-        while (UP.Count != 0 && UnrolledSize > UP.PartialThreshold) {
+        while (UP.Count != 0 &&
+               UnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
           UP.Count >>= 1;
-          UnrolledSize = (LoopSize - BEInsns) * UP.Count + BEInsns;
-        }
       }
       if (UP.Count < 2) {
         if (PragmaEnableUnroll)
           ORE->emitOptimizationRemarkMissed(
               DEBUG_TYPE, L,
               "Unable to unroll loop as directed by unroll(enable) pragma "
               "because unrolled size is too large.");
         UP.Count = 0;
static bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
   if (!UP.Runtime) {
     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)
     UP.Count = DefaultUnrollRuntimeCount;
-  UnrolledSize = (LoopSize - BEInsns) * UP.Count + BEInsns;
-
   // Reduce unroll count to be the largest power-of-two factor of
   // the original count which satisfies the threshold limit.
-  while (UP.Count != 0 && UnrolledSize > UP.PartialThreshold) {
+  while (UP.Count != 0 && UnrolledLoopSize(LoopSize, UP) > UP.PartialThreshold)
     UP.Count >>= 1;
-    UnrolledSize = (LoopSize - BEInsns) * UP.Count + BEInsns;
-  }
 
 #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)
       UP.Count >>= 1;
DEBUG(dbgs() << "Loop Unroll: F[" << L->getHeader()->getParent()->getName()
                << "] Loop %" << L->getHeader()->getName() << "\n");
   if (HasUnrollDisablePragma(L)) {
     return false;
   }
 
   unsigned NumInlineCandidates;
   bool NotDuplicatable;
   bool Convergent;
+  TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
+      L, TTI, ProvidedThreshold, ProvidedCount, ProvidedAllowPartial,
+      ProvidedRuntime);
   unsigned LoopSize = ApproximateLoopSize(
-      L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC);
+      L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC, UP.BEInsns);
   DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
   if (NotDuplicatable) {
     DEBUG(dbgs() << "  Not unrolling loop which contains non-duplicatable"
                  << " instructions.\n");
     return false;
   }
   if (NumInlineCandidates != 0) {
     DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
   BasicBlock *ExitingBlock = L->getLoopLatch();
   if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
     ExitingBlock = L->getExitingBlock();
   if (ExitingBlock) {
     TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
     TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
   }
 
-  TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
-      L, TTI, ProvidedThreshold, ProvidedCount, ProvidedAllowPartial,
-      ProvidedRuntime);
-
   // Exit early if unrolling is disabled.
   if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0))
     return false;
 
   // If the loop contains a convergent operation, the prelude we'd add
   // to do the first few instructions before we hit the unrolled loop
   // is unsafe -- it adds a control-flow dependency to the convergent
   // operation.  Therefore restrict remainder loop (try unrollig without).