Unroll pass restructure.

[evstupac]

Summary

The patch restructure unroll pass (a part where decision on unroll Count is made).
It adds some comments and early exits when unroll Count decision is obvious.
The patch does not affect trunk, but can affect architectures where unroll remainder is not allowed. However it is easy to disable it in Unroll Preferences structure.

I've got build same on all spec benchmarks for x86.

[mzolotukhin]

Hi Evgeny,

Thanks for doing this, I agree that this place is like a big mess now. Please find some comments inline.

Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

83–87

Do we need unroll-runtime at all if we have this option? Also, I'd suggest to separate code restructuring from adding new stuff, like new command line options.

528

I would rename it to computeUnrollCount, findUnrollCount, or something like this. It looks to me that we're doing much more work in this function than just 'get'.

536–538

We set these parameters here, but we're not guaranteed to early exit. Is this intentional? Maybe set them only if we're going to return?
Also, do we need to set UP.Runtime = true as we do below?

661–665

Can we assert(UP.Count == TripCount) here? If yes, it would emphasize the logic, if not, the logic seems flawed.

696–707

Is this comment relevant now? And where did the convergence checks go?

784

s/isCountSetExplicitly/IsCountSetExplicitly/

lib/Transforms/Utils/LoopUnroll.cpp

202

This change might also be in a separate patch, right?

[evstupac]

Hi Michael,

Thanks for looking into proposed new structure.
I'll submit a set of patches for restructure. Finally I want to move all checks preventing unroll from "lib/Transforms/Utils/LoopUnroll.cpp" to "lib/Transforms/Scalar/LoopUnrollPass.cpp".

See my answers inline.

Thanks,
Evgeny

lib/Transforms/Scalar/LoopUnrollPass.cpp

83–87

This is to structure case with "Convergent" operation in a loop and face needs of architectures that suffers from generated remainder.
However I agree that option itself could be removed from the patch if UP.AllowRemainder remain "true" by default.

536–538

We set these parameters here, but we're not guaranteed to early exit. Is this intentional?

Yes, since user requested unroll. Only exceeded pragma threshold or unsafe transformation can prevent unroll here. When pragma threshold is exceeded we still allow all kinds of unroll, but with less Count.

Also, do we need to set UP.Runtime = true as we do below?

Yes UP.Runtime whold be reasonable here. However that will cause some tests fail. I'll request this in next patch. Right now I tried to keep current logic to highlight places like this.

661–665

assert(TripCount) will be more accurate as UP.Count could be 0

696–707

lines 781 - 782. I agree it is better to move the comment (with corresponding changes) there.

lib/Transforms/Utils/LoopUnroll.cpp

202

Yes. But I'd like to keep it in this patch. That is related to current "-unroll-count" and "#pragma unroll" behavior.

Now:
"-unroll-count" forces "full unroll", "partial" and skips "runtime", so go directly to forced unroll when TripCount is runtime.
"#pragma unroll" forces "full unroll", "partial" and "runtime" and skip forced unroll even if runtime has failed

So to make current behavior clear I'd like to keep this. However you are right this could be done in separate patch.

[evstupac]

Updated according latest comments: variables rename, comments fix.

[zzheng]

Can we have consolidated unrolled-size computation or threshold enforcement?

Also, please elaborate on forced unroll of runtime loops.

Thanks

lib/Transforms/Scalar/LoopUnrollPass.cpp

539

This formula appears several times... It'll be better to have a consolidated function that computes the unrolled size or enforces the threshold.

563

This feels a little awkward. I would use

bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
...

if (HasPragma || UserUnrollCount)

lib/Transforms/Utils/LoopUnroll.cpp

304

I don't understand this part. If UnrollRuntimeLoopRemainder() returned false, remainder loop is not generated. How do we ensure correctness if we 'force' a loop that has runtime tripcount of 6 to by unrolled by 4?

[evstupac]

Thanks for taking a look on the patch.
Please find my answers inline.

lib/Transforms/Scalar/LoopUnrollPass.cpp

539

Good point.
We can create something like IsCountMeetThreshold(UP, LoopSize)

563

Agree. This is better.

lib/Transforms/Utils/LoopUnroll.cpp

304

Actually that is the way how -unroll-count works now when runtime unroll is disabled.
For this type of unrolling we do not remove conditional branches from unrolled loop. For example unroll by 2:

for.body

...
cmp
br for.body1, exit

for.body1

...
cmp
br for.body, exit

exit

My changes do not change current behavior.
In my next patch I'll request runtime unroll to be enabled when -unroll-count passed.

There could be positive effects of this type of unrolling (like reduced number of executed backward branches). So if user wants a loop to be unrolled compiler should do this (when it is safe).

[evstupac]

rebased after recent changes in unroll, fixed some var names.

[evstupac]

lib/Transforms/Scalar/LoopUnrollPass.cpp

539

Currently the formula have different parameters at different places. I'm planing to unify this, but this will change current behavior. So this is still a good point, but I'd like to fix this in separate patch.

[evstupac]

PING

[mzolotukhin]

lib/Transforms/Scalar/LoopUnrollPass.cpp

536–543

I find it a bit confusing that we change values in UP even if we don't exit the function. Can we rewrite it to something like:

If (condition1) {
  UP = ...;
  return true; // We only change UP when we are going to return
}
if (condition2) {
  UP = ...;
  return true;
}

as opposed to

if (condition1) {
  UP = ...
  if (condition)
    return true;
  // Here we changed UP, but didn't return
}

[evstupac]

lib/Transforms/Scalar/LoopUnrollPass.cpp

536–543

We can do so, but still we need to enable all the properties somehow.
For "condition1" it will look like:

If (condition1) {
  UP = ...;
  return true; // We only change UP when we are going to return
}
if (condition1)
  UP = ...;

That is because if user specified count that exceed threshold we are reducing it, but still allow some certain level of unrolling (Runtime, Full, Force....)

Personally I'd better disable unroll and warn user in that case (telling how to enable specified unroll by increasing pragma threshold or reducing count). That will resolve the issue, but change current behavior:

if (condition1) {
  if (condition) {
    UP = ...
  } else {
    UP.Count = 1;
    Warn();
  }
  return true;
}

Now it is very annoying when I tell compiler to unroll by 8, but it unrolls by 4 just because of some heuristics without any warnings.

[mzolotukhin]

lib/Transforms/Scalar/LoopUnrollPass.cpp

536–543

Personally, I like what you suggested as well. I think when pragmas are used, the user wants full control over what happens and currently we don't provide that. Also, I really like that the code will be much simpler in this case.

Others might have different views on that though.

[evstupac]

Let's wait for other suggestions/comments. However the patch is here 20 days without significant changes.
So there could be more comments only after commit.

lib/Transforms/Scalar/LoopUnrollPass.cpp

536–543

Anyway to stress current logic and ask for changes the code need to be refactored first.

[evstupac]

PING.

[hfinkel]

This certainly looks cleaner, thanks!

My one request, since we're refactoring anyway, could we make some named constant for the number of latch-associated instructions and use it instead of putting '2' everywhere?

[evstupac]

Thank you for the review and accept.
The patch is important for further improvements.

could we make some named constant for the number of latch-associated instructions and use it instead of putting '2' everywhere?

That's a good point. I'll add a variable for this. However, generally it is not a constant value. It depends on loop instructions and unroll factor. We could have more recurrences to optimize. Say, "s ^= 1" will become constant for every unroll factor which is multiple of 2. I'm going to address this in one of further patches.

[evstupac]

Here the version committed.
Added BEInsns var which represents number of optimized instructions when "back edge" becomes "fall through". It replaced constant "2" used for this in all calculations.

[evstupac]

committed revision 271071.

[Gerolf]

lib/Transforms/Scalar/LoopUnrollPass.cpp

546

Please move (LoopSize - BEInsns) * UP.Count + BEInsns to a function and comment properly. It will be invoked many times as the estimated size of the unrolled loop gets checked repeatedly.

637

Isn't that simply UP.Count = max(UP.PartialThreshold - BEInsns/ LoopSize -BEInsns -1, 0)? Probably it also needs a check that LoopSize > BEInsns, but that should probably be an assertion anyway. And for UP.PartialThreshold - BEInsns/LoopSize - BEInsns should probably be fit into a function since there is a similar instance above. It makes sense to do all this now since the intent of this patch is a code cleanup.

752

see above

[evstupac]

lib/Transforms/Scalar/LoopUnrollPass.cpp

637

This code was introduced previously, not in this patch. I'm only refactoring places I've noticed. And yes, there is a lot more places to refactor.
That is not just max you've mentioned.
Currently LoopSize is defined as max (3, "estimated loop size"), BEInsns is just "2". So LoopSize is always greater than BEInsns.
However I agree, that moving UnrolledSize calculation into function and adding the assert to the function is a good point.
What I want to do is to move the whole threshold check to a function. And that requires modifications that would change current behavior - so that will go to the next patch.
You can look into previous comment for the discussion.

[mehdi_amini]

lib/Transforms/Scalar/LoopUnrollPass.cpp

546

I believe this hasn't been done.

And there is a discrepancy since some places are doing the arithmetic in 64 bits while others are doing it in 32 bits:

UnrolledSize = (uint64_t)(LoopSize - BEInsns) * TripCount + BEInsns; vs UnrolledSize = (LoopSize - BEInsns) * UP.Count + BEInsns;

Coverity reports possible overflows:

CID 1356133:    (OVERFLOW_BEFORE_WIDEN)
Potentially overflowing expression "(LoopSize - BEInsns) * UP.Count" with type "unsigned int" (32 bits, unsigned) is evaluated using 32-bit arithmetic, and then used in a context that expects an expression of type "uint64_t" (64 bits, unsigned).

include/llvm/Analysis/TargetTransformInfo.h

struct UnrollingPreferences {
     unsigned FullUnrollMaxCount;
     /// 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).
+    bool AllowRemainder;
     /// Allow emitting expensive instructions (such as divisions) when computing
     /// the trip count of a loop for runtime unrolling.
     bool AllowExpensiveTripCount;
+    /// Apply loop unroll on any kind of loop
+    /// (mainly to loops that fail runtime unrolling).
+    bool Force;
   };
 
   /// \brief Get target-customized preferences for the generic loop unrolling
   /// transformation. The caller will initialize UP with the current
   /// target-independent defaults.
   void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) const;
 
   /// @}

include/llvm/Transforms/Utils/UnrollLoop.h

 class DominatorTree;
 class Loop;
 class LoopInfo;
 class LPPassManager;
 class MDNode;
 class Pass;
 class ScalarEvolution;
 
-bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool AllowRuntime,
-                bool AllowExpensiveTripCount, unsigned TripMultiple,
-                LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
-                AssumptionCache *AC, bool PreserveLCSSA);
+bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force,
+                bool AllowRuntime, bool AllowExpensiveTripCount,
+                unsigned TripMultiple, LoopInfo *LI, ScalarEvolution *SE,
+                DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
 
 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
                                 bool AllowExpensiveTripCount,
                                 bool UseEpilogRemainder, LoopInfo *LI,
                                 ScalarEvolution *SE, DominatorTree *DT,
                                 bool PreserveLCSSA);
 
 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
 }
 
 #endif

lib/Transforms/Scalar/LoopUnrollPass.cpp

UnrollFullMaxCount("unroll-full-max-count", cl::Hidden,
   cl::desc("Set the max unroll count for full unrolling, for testing purposes"));
 
 static cl::opt<bool>
 UnrollAllowPartial("unroll-allow-partial", cl::Hidden,
   cl::desc("Allows loops to be partially unrolled until "
            "-unroll-threshold loop size is reached."));
 
 static cl::opt<bool>
+UnrollAllowRemainder("unroll-allow-remainder", cl::Hidden,
+  cl::desc("Allow generation of a loop remainder (extra iterations) "
+           "when unrolling a loop."));
+
+static cl::opt<bool>
 UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden,
   cl::desc("Unroll loops with run-time trip counts"));
 
 static cl::opt<unsigned>
 PragmaUnrollThreshold("pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden,
   cl::desc("Unrolled size limit for loops with an unroll(full) or "
            "unroll_count pragma."));
 
 
 /// A magic value for use with the Threshold parameter to indicate
 /// that the loop unroll should be performed regardless of how much
 /// code expansion would result.
 static const unsigned NoThreshold = UINT_MAX;
 
 /// Default unroll count for loops with run-time trip count if
 /// -unroll-count is not set
 static const unsigned DefaultUnrollRuntimeCount = 8;
 
 /// Gather the various unrolling parameters based on the defaults, compiler
-/// flags, TTI overrides, pragmas, and user specified parameters.
+/// flags, TTI overrides and user specified parameters.
 static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
     Loop *L, const TargetTransformInfo &TTI, Optional<unsigned> UserThreshold,
     Optional<unsigned> UserCount, Optional<bool> UserAllowPartial,
-    Optional<bool> UserRuntime, unsigned PragmaCount, bool PragmaFullUnroll,
-    bool PragmaEnableUnroll, unsigned TripCount) {
+    Optional<bool> UserRuntime) {
   TargetTransformInfo::UnrollingPreferences UP;
 
   // Set up the defaults
   UP.Threshold = 150;
   UP.PercentDynamicCostSavedThreshold = 20;
   UP.DynamicCostSavingsDiscount = 2000;
   UP.OptSizeThreshold = 50;
   UP.PartialThreshold = UP.Threshold;
   UP.PartialOptSizeThreshold = UP.OptSizeThreshold;
   UP.Count = 0;
   UP.MaxCount = UINT_MAX;
   UP.FullUnrollMaxCount = UINT_MAX;
   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);
 
   // Apply size attributes
   if (L->getHeader()->getParent()->optForSize()) {
     UP.Threshold = UP.OptSizeThreshold;
     UP.PartialThreshold = UP.PartialOptSizeThreshold;
   }
 
-  // Apply unroll count pragmas
-  if (PragmaCount)
-    UP.Count = PragmaCount;
-  else if (PragmaFullUnroll)
-    UP.Count = TripCount;
-
   // Apply any user values specified by cl::opt
   if (UnrollThreshold.getNumOccurrences() > 0) {
     UP.Threshold = UnrollThreshold;
     UP.PartialThreshold = UnrollThreshold;
   }
   if (UnrollPercentDynamicCostSavedThreshold.getNumOccurrences() > 0)
     UP.PercentDynamicCostSavedThreshold =
         UnrollPercentDynamicCostSavedThreshold;
   if (UnrollDynamicCostSavingsDiscount.getNumOccurrences() > 0)
     UP.DynamicCostSavingsDiscount = UnrollDynamicCostSavingsDiscount;
-  if (UnrollCount.getNumOccurrences() > 0)
-    UP.Count = UnrollCount;
   if (UnrollMaxCount.getNumOccurrences() > 0)
     UP.MaxCount = UnrollMaxCount;
   if (UnrollFullMaxCount.getNumOccurrences() > 0)
     UP.FullUnrollMaxCount = UnrollFullMaxCount;
   if (UnrollAllowPartial.getNumOccurrences() > 0)
     UP.Partial = UnrollAllowPartial;
+  if (UnrollAllowRemainder.getNumOccurrences() > 0)
+    UP.AllowRemainder = UnrollAllowRemainder;
   if (UnrollRuntime.getNumOccurrences() > 0)
     UP.Runtime = UnrollRuntime;
 
   // Apply user values provided by argument
   if (UserThreshold.hasValue()) {
     UP.Threshold = *UserThreshold;
     UP.PartialThreshold = *UserThreshold;
   }
   if (UserCount.hasValue())
     UP.Count = *UserCount;
   if (UserAllowPartial.hasValue())
     UP.Partial = *UserAllowPartial;
   if (UserRuntime.hasValue())
     UP.Runtime = *UserRuntime;
 
-  if (PragmaCount > 0 ||
-      ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount != 0)) {
-    // If the loop has an unrolling pragma, we want to be more aggressive with
-    // unrolling limits. Set thresholds to at least the PragmaTheshold value
-    // which is larger than the default limits.
-    if (UP.Threshold != NoThreshold)
-      UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
-    if (UP.PartialThreshold != NoThreshold)
-      UP.PartialThreshold =
-          std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
-  }
-
   return UP;
 }
 
 namespace {
 struct EstimatedUnrollCost {
   /// \brief The estimated cost after unrolling.
   int UnrolledCost;
 
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;
 }
 
-static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
-                            ScalarEvolution *SE, const TargetTransformInfo &TTI,
-                            AssumptionCache &AC, bool PreserveLCSSA,
-                            Optional<unsigned> ProvidedCount,
-                            Optional<unsigned> ProvidedThreshold,
-                            Optional<bool> ProvidedAllowPartial,
-                            Optional<bool> ProvidedRuntime) {
-  BasicBlock *Header = L->getHeader();
-  DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName()
-        << "] Loop %" << Header->getName() << "\n");
+// Returns true if unroll count was set explicitly.
+// Calculates unroll count and writes it to UP.Count.
+static bool getUnrollCount(Loop *L, const TargetTransformInfo &TTI,
+                           DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE,
+                           unsigned TripCount, unsigned TripMultiple,
+                           unsigned LoopSize,
+                           TargetTransformInfo::UnrollingPreferences &UP) {
+  // Check for explicit Count.
+  // 1st priority is unroll count set by "unroll-count" option.
+  if (UnrollCount.getNumOccurrences() > 0) {
+    UP.Count = UnrollCount;
+    UP.AllowExpensiveTripCount = true;
+    UP.Force = true;
+    if ((LoopSize - 2) * UP.Count + 2 < UP.Threshold
+        && UP.AllowRemainder)
+      return true;
+  }
 
-  if (HasUnrollDisablePragma(L)) {
-    return false;
+  // 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 ((LoopSize - 2) * UP.Count + 2 < PragmaUnrollThreshold &&
+        UP.AllowRemainder)
+      return true;
   }
   bool PragmaFullUnroll = HasUnrollFullPragma(L);
-  bool PragmaEnableUnroll = HasUnrollEnablePragma(L);
-  unsigned PragmaCount = UnrollCountPragmaValue(L);
-  bool HasPragma = PragmaFullUnroll || PragmaEnableUnroll || PragmaCount > 0;
-
-  // Find trip count and trip multiple if count is not available
-  unsigned TripCount = 0;
-  unsigned TripMultiple = 1;
-  // If there are multiple exiting blocks but one of them is the latch, use the
-  // latch for the trip count estimation. Otherwise insist on a single exiting
-  // block for the trip count estimation.
-  BasicBlock *ExitingBlock = L->getLoopLatch();
-  if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
-    ExitingBlock = L->getExitingBlock();
-  if (ExitingBlock) {
-    TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
-    TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
+  if (PragmaFullUnroll && TripCount != 0) {
+    UP.Count = TripCount;
+    if ((LoopSize - 2) * UP.Count + 2 < PragmaUnrollThreshold)
+      return false;
   }
 
-  TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
-      L, TTI, ProvidedThreshold, ProvidedCount, ProvidedAllowPartial,
-      ProvidedRuntime, PragmaCount, PragmaFullUnroll, PragmaEnableUnroll,
-      TripCount);
+  bool PragmaEnableUnroll = HasUnrollEnablePragma(L);
+  bool HasPragma = PragmaCount > 0 || PragmaFullUnroll || PragmaEnableUnroll ||
+                   UnrollCount.getNumOccurrences() > 0;
 
-  unsigned Count = UP.Count;
-  bool CountSetExplicitly = Count != 0;
-  // Use a heuristic count if we didn't set anything explicitly.
-  if (!CountSetExplicitly)
-    Count = TripCount == 0 ? DefaultUnrollRuntimeCount : TripCount;
-  if (TripCount && Count > TripCount)
-    Count = TripCount;
-  Count = std::min(Count, UP.FullUnrollMaxCount);
+  uint64_t UnrolledSize;
+  DebugLoc LoopLoc = L->getStartLoc();
+  Function *F = L->getHeader()->getParent();
+  LLVMContext &Ctx = F->getContext();
 
-  unsigned NumInlineCandidates;
-  bool NotDuplicatable;
-  bool Convergent;
-  unsigned LoopSize = ApproximateLoopSize(
-      L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC);
-  DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
+  if (HasPragma && 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 the conditional branch on the
     // backedge and the comparison feeding it are not replicated like the rest of
     // the loop body (which is why 2 is subtracted).
-  uint64_t UnrolledSize = (uint64_t)(LoopSize-2) * Count + 2;
-  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");
-    return false;
-  }
-
-  // Given Count, TripCount and thresholds determine the type of
-  // unrolling which is to be performed.
-  enum { Full = 0, Partial = 1, Runtime = 2 };
-  int Unrolling;
-  if (TripCount && Count == TripCount) {
-    Unrolling = Partial;
-    // If the loop is really small, we don't need to run an expensive analysis.
+    UnrolledSize = (uint64_t)(LoopSize - 2) * TripCount + 2;
     if (canUnrollCompletely(L, UP.Threshold, 100, UP.DynamicCostSavingsDiscount,
                             UnrolledSize, UnrolledSize)) {
-      Unrolling = Full;
+      UP.Count = TripCount;
+      return HasPragma;
     } 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)) {
-          Unrolling = Full;
+          UP.Count = TripCount;
+          return HasPragma;
         }
     }
-  } else if (TripCount && Count < TripCount) {
-    Unrolling = Partial;
-  } else {
-    Unrolling = Runtime;
   }
 
-  // Reduce count based on the type of unrolling and the threshold values.
-  unsigned OriginalCount = Count;
-  bool AllowRuntime = PragmaEnableUnroll || (PragmaCount > 0) || UP.Runtime;
-  // Don't unroll a runtime trip count loop with unroll full pragma.
-  if (HasRuntimeUnrollDisablePragma(L) || PragmaFullUnroll) {
-    AllowRuntime = false;
-  }
-  bool DecreasedCountDueToConvergence = false;
-  if (Unrolling == Partial) {
-    bool AllowPartial = PragmaEnableUnroll || UP.Partial;
-    if (!AllowPartial && !CountSetExplicitly) {
+  // 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 |= HasPragma;
+    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 && Count > 1) {
+    if (UP.PartialThreshold != NoThreshold) {
       // Reduce unroll count to be modulo of TripCount for partial unrolling.
+      UnrolledSize = (uint64_t)(LoopSize - 2) * UP.Count + 2;
       if (UnrolledSize > UP.PartialThreshold)
-        Count = (std::max(UP.PartialThreshold, 3u) - 2) / (LoopSize - 2);
-      if (Count > UP.MaxCount)
-        Count = UP.MaxCount;
-      while (Count != 0 && TripCount % Count != 0)
-        Count--;
-      if (AllowRuntime && Count <= 1) {
+        UP.Count = (std::max(UP.PartialThreshold, 3u) - 2) / (LoopSize - 2);
+      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
-        // runtime unrolling is allowed.
-        Count = DefaultUnrollRuntimeCount;
-        UnrolledSize = (LoopSize - 2) * Count + 2;
-        while (Count != 0 && UnrolledSize > UP.PartialThreshold) {
-          Count >>= 1;
-          UnrolledSize = (LoopSize - 2) * Count + 2;
-        }
+        // remainder loop is allowed.
+        UP.Count = DefaultUnrollRuntimeCount;
+        UnrolledSize = (LoopSize - 2) * UP.Count + 2;
+        while (UP.Count != 0 && UnrolledSize > UP.PartialThreshold) {
+          UP.Count >>= 1;
+          UnrolledSize = (LoopSize - 2) * UP.Count + 2;
+        }
+      if (UP.Count < 2) {
+        if (PragmaEnableUnroll)
+          emitOptimizationRemarkMissed(
+              Ctx, DEBUG_TYPE, *F, LoopLoc,
+              "Unable to unroll loop as directed by unroll(enable) pragma "
+              "because unrolled size is too large.");
+        UP.Count = 0;
       }
+    } else {
+      UP.Count = TripCount;
     }
-  } else if (Unrolling == Runtime) {
-    if (!AllowRuntime && !CountSetExplicitly) {
-      DEBUG(dbgs() << "  will not try to unroll loop with runtime trip count "
-                   << "-unroll-runtime not given\n");
-      return false;
-    }
+    if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
+               UP.Count != TripCount)
+      emitOptimizationRemarkMissed(
+          Ctx, DEBUG_TYPE, *F, LoopLoc,
+          "Unable to fully unroll loop as directed by unroll pragma because "
+          "unrolled size is too large.");
+    return HasPragma;
+  }
+  if (PragmaFullUnroll)
+      emitOptimizationRemarkMissed(
+          Ctx, DEBUG_TYPE, *F, LoopLoc,
+          "Unable to fully unroll loop as directed by unroll(full) pragma "
+          "because loop has a runtime trip count.");
+
+  // 5th priority is runtime unrolling.
+  // Don't unroll a runtime trip count loop when it is disabled.
+  if (HasRuntimeUnrollDisablePragma(L)) {
+    UP.Count = 0;
+    return false;
+  }
+  // Reduce count based on the type of unrolling and the threshold values.
+  UP.Runtime |= PragmaEnableUnroll || PragmaCount > 0 ||
+                UnrollCount.getNumOccurrences() > 0;
+  if (!UP.Runtime) {
+    UP.Count = 0;
+  if (UP.Count == 0)
+    UP.Count = DefaultUnrollRuntimeCount;
+  UnrolledSize = (LoopSize - 2) * UP.Count + 2;
 
-    // Reduce unroll count to be the largest power-of-two factor of
-    // the original count which satisfies the threshold limit.
-    while (Count != 0 && UnrolledSize > UP.PartialThreshold) {
-      Count >>= 1;
-      UnrolledSize = (LoopSize-2) * Count + 2;
-    }
+  while (UP.Count != 0 && UnrolledSize > UP.PartialThreshold) {
+    UP.Count >>= 1;
+    UnrolledSize = (LoopSize - 2) * UP.Count + 2;
 
-    if (Count > UP.MaxCount)
-      Count = UP.MaxCount;
+  unsigned OrigCount = UP.Count;
 
+  if (!UP.AllowRemainder && UP.Count != 0 && (TripMultiple % UP.Count) != 0) {
     // 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 Count must divide TripMultiple.
     //
     // TODO: This is quite conservative.  In practice, convergent_op()
     // is likely to be called unconditionally in the loop.  In this
     // case, the program would be ill-formed (on most architectures)
     // unless n were the same on all threads in a thread group.
     // Assuming n is the same on all threads, any kind of unrolling is
     // safe.  But currently llvm's notion of convergence isn't powerful
     // enough to express this.
-    unsigned OrigCount = Count;
-    while (Convergent && Count != 0 && TripMultiple % Count != 0) {
-      DecreasedCountDueToConvergence = true;
-      Count >>= 1;
-    }
-    if (OrigCount > Count) {
-      DEBUG(dbgs() << "  loop contains a convergent instruction, so unroll "
+    while (UP.Count != 0 && TripMultiple % UP.Count != 0)
+      UP.Count >>= 1;
                       "count must divide the trip multiple, "
                    << TripMultiple << ".  Reducing unroll count from "
-                   << OrigCount << " to " << Count << ".\n");
-    }
-    DEBUG(dbgs() << "  partially unrolling with count: " << Count << "\n");
-  }
-
-  if (HasPragma) {
-    // Emit optimization remarks if we are unable to unroll the loop
-    // as directed by a pragma.
-    DebugLoc LoopLoc = L->getStartLoc();
-    Function *F = Header->getParent();
-    LLVMContext &Ctx = F->getContext();
-    if (PragmaCount > 0 && DecreasedCountDueToConvergence) {
+                   << OrigCount << " to " << UP.Count << ".\n");
+    if (PragmaCount > 0 && !UP.AllowRemainder)
       emitOptimizationRemarkMissed(
           Ctx, DEBUG_TYPE, *F, LoopLoc,
           Twine("Unable to unroll loop the number of times directed by "
                 "unroll_count pragma because the loop contains a convergent "
                 "instruction, and so must have an unroll count that divides "
                 "the loop trip multiple of ") +
-              Twine(TripMultiple) + ".  Unrolling instead " + Twine(Count) +
+              Twine(TripMultiple) + ".  Unrolling instead " + Twine(UP.Count) +
               " time(s).");
-    } else if ((PragmaCount > 0) && Count != OriginalCount) {
-      emitOptimizationRemarkMissed(
-          Ctx, DEBUG_TYPE, *F, LoopLoc,
-          "Unable to unroll loop the number of times directed by "
-          "unroll_count pragma because unrolled size is too large.");
-    } else if (PragmaFullUnroll && !TripCount) {
-      emitOptimizationRemarkMissed(
-          Ctx, DEBUG_TYPE, *F, LoopLoc,
-          "Unable to fully unroll loop as directed by unroll(full) pragma "
-          "because loop has a runtime trip count.");
-    } else if (PragmaEnableUnroll && Count != TripCount && Count < 2) {
-      emitOptimizationRemarkMissed(
-          Ctx, DEBUG_TYPE, *F, LoopLoc,
-          "Unable to unroll loop as directed by unroll(enable) pragma because "
-          "unrolled size is too large.");
-    } else if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
-               Count != TripCount) {
-      emitOptimizationRemarkMissed(
-          Ctx, DEBUG_TYPE, *F, LoopLoc,
-          "Unable to fully unroll loop as directed by unroll pragma because "
-          "unrolled size is too large.");
-    }
+
+  }
+
+  if (UP.Count > UP.MaxCount)
+    UP.Count = UP.MaxCount;
+  DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count << "\n");
+  if (UP.Count < 2)
+    UP.Count = 0;
+  return HasPragma;
+
+static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
+                            ScalarEvolution *SE, const TargetTransformInfo &TTI,
+                            AssumptionCache &AC, bool PreserveLCSSA,
+                            Optional<unsigned> ProvidedCount,
+                            Optional<unsigned> ProvidedThreshold,
+                            Optional<bool> ProvidedAllowPartial,
+                            Optional<bool> ProvidedRuntime) {
+  BasicBlock *Header = L->getHeader();
+  DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName()
+        << "] Loop %" << Header->getName() << "\n");
+  if (HasUnrollDisablePragma(L)) {
+    return false;
   }
 
-  if (Unrolling != Full && Count < 2) {
-    // Partial unrolling by 1 is a nop.  For full unrolling, a factor
-    // of 1 makes sense because loop control can be eliminated.
+  unsigned NumInlineCandidates;
+  bool NotDuplicatable;
+  bool Convergent;
+  unsigned LoopSize = ApproximateLoopSize(
+      L, NumInlineCandidates, NotDuplicatable, Convergent, TTI, &AC);
+  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");
+    return false;
+  }
+
+  // Find trip count and trip multiple if count is not available
+  unsigned TripCount = 0;
+  unsigned TripMultiple = 1;
+  // If there are multiple exiting blocks but one of them is the latch, use the
+  // latch for the trip count estimation. Otherwise insist on a single exiting
+  // block for the trip count estimation.
+  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);
+  if (Convergent)
+    UP.AllowRemainder = false;
+
+  bool isCountSetExplicitly =
+      getUnrollCount(L, TTI, DT, LI, SE, TripCount, TripMultiple, LoopSize, UP);
+
+  if (!UP.Count)
+    return false;
+  // Unroll factor (Count) must be less or equal to TripCount.
+  if (TripCount && UP.Count > TripCount)
+    UP.Count = TripCount;
 
   // Unroll the loop.
-  if (!UnrollLoop(L, Count, TripCount, AllowRuntime, UP.AllowExpensiveTripCount,
-                  TripMultiple, LI, SE, &DT, &AC, PreserveLCSSA))
+  if (!UnrollLoop(L, UP.Count, TripCount, UP.Force, UP.Runtime,
+                  UP.AllowExpensiveTripCount, TripMultiple, LI, SE, &DT, &AC,
+                  PreserveLCSSA))
     return false;
 
-  // If loop has an unroll count pragma mark loop as unrolled to prevent
-  // unrolling beyond that requested by the pragma.
-  if (HasPragma && PragmaCount != 0)
+  // If loop has an unroll count pragma or unrolled by explicitly set count
+  // mark loop as unrolled to prevent unrolling beyond that requested.
+  if (isCountSetExplicitly)
     SetLoopAlreadyUnrolled(L);
   return true;
 }
 
 namespace {
 class LoopUnroll : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid

lib/Transforms/Utils/LoopUnroll.cpp

 /// iterations before branching into the unrolled loop.  UnrollLoop will not
 /// runtime-unroll the loop if computing RuntimeTripCount will be expensive and
 /// AllowExpensiveTripCount is false.
 ///
 /// The LoopInfo Analysis that is passed will be kept consistent.
 ///
 /// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
 /// DominatorTree if they are non-null.
-bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
+bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force,
                       bool AllowRuntime, bool AllowExpensiveTripCount,
                       unsigned TripMultiple, LoopInfo *LI, ScalarEvolution *SE,
                       DominatorTree *DT, AssumptionCache *AC,
                       bool PreserveLCSSA) {
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) {
     DEBUG(dbgs() << "  Can't unroll; loop preheader-insertion failed.\n");
     return false;
DEBUG(
                "operation.");
       });
   // Don't output the runtime loop remainder if Count is a multiple of
   // TripMultiple.  Such a remainder is never needed, and is unsafe if the loop
   // contains a convergent instruction.
   if (RuntimeTripCount && TripMultiple % Count != 0 &&
       !UnrollRuntimeLoopRemainder(L, Count, AllowExpensiveTripCount,
                                   UnrollRuntimeEpilog, LI, SE, DT, 
-                                  PreserveLCSSA))
+                                  PreserveLCSSA)) {
+    if (Force)
+      RuntimeTripCount = false;
+    else
       return false;
-
+  }
   // Notify ScalarEvolution that the loop will be substantially changed,
   // if not outright eliminated.
   if (SE)
     SE->forgetLoop(L);
 
   // If we know the trip count, we know the multiple...
   unsigned BreakoutTrip = 0;
   if (TripCount != 0) {

test/Transforms/LoopUnroll/partial-unroll-const-bounds.ll

-; RUN: opt < %s -S -unroll-threshold=20 -loop-unroll -unroll-allow-partial -unroll-runtime | FileCheck %s
+; RUN: opt < %s -S -unroll-threshold=20 -loop-unroll -unroll-allow-partial -unroll-allow-remainder | FileCheck %s
 
 ; The Loop TripCount is 9. However unroll factors 3 or 9 exceed given threshold.
 ; The test checks that we choose a smaller, power-of-two, unroll count and do not give up on unrolling.
 
 ; CHECK: for.body:
 ; CHECK: store
 ; CHECK: for.body.1:
 ; CHECK: store