[SCEV] Implement (non-exact) getSmallConstantTripCountUpperBound

[kparzysz]

Summary

This function will calculate an upper bound for the loop trip count. The returned value does not have to be exact: the loop may iterate fewer times in all circumstances.

Motivation:

This loop came from a customer code:

struct S {
  unsigned X;
  int Y;
};

int fred(int A, int B, struct S *P) {
  int C = A - 1;
  while ((B & 3) != 0) {
    P->X = C * 128;
    P->Y = 0;
    P++;
    B++;
  }
  return 0;
}

Regardless of what B is, the loop will execute at most 4 times, however the upper bound returned from getSmallConstantMaxTripCount is CouldNotCompute. This loop ends up getting interleaved by the loop vectorizer, which causes a needless code growth.

The maximum can actually be computed from the predicated backedge taken count, and patch uses that information to calculate another estimate of the upper bound.

As is, this patch will break a few lit tests. Right now I just want to get initial feedback on whether this is the right approach.

[efriedma]

lib/Analysis/ScalarEvolution.cpp

6393

You can't throw away this list of predicates; the computed trip count isn't valid in general, only under the computed predicates, which might not be true.

[efriedma]

In case it wasn't clear, getSmallConstantMaxTripCount must be conservatively correct: we use it to unroll loops with an unknown trip count, so we'll miscompile if the trip count at runtime is larger. We could add a separate method for an "estimated" maximum trip count, using a heuristic like this, if it would be useful for the vectorizer.

[kparzysz]

Ah, I thought it's just an upper bound. Ok, I'll add another function that finds the estimate.

[kparzysz]

Added a new function to ScalarEvolution to estimate the trip count upper bound.

[efriedma]

The predicated trip count computation isn't modeling the loop in your example well; it thinks the maximum trip count is 2. But I guess that's okay.

include/llvm/Analysis/ScalarEvolution.h

731

The comment is backwards: the important thing is that actual trip count may be larger than the upper bound.

732

I think I'd prefer something like "getSmallConstantTripCountEstimate()"? Not sure.

lib/Analysis/ScalarEvolution.cpp

6397

This is redundant: if the trip count is known, the max trip count is also known.

6404

getPredicatedBackedgeTakenInfo(L).getMax(L, this, PS) would compute what you want more directly.

[kparzysz]

In D47899#1125720, @efriedma wrote:

The predicated trip count computation isn't modeling the loop in your example well; it thinks the maximum trip count is 2. But I guess that's okay.

It was 4 yesterday. I'll check it tomorrow when I'm back at work.

include/llvm/Analysis/ScalarEvolution.h

731

The actual trip count must be less than or equal than the upper bound. It wouldn't make any sense otherwise.

[kparzysz]

In D47899#1125752, @kparzysz wrote:

In D47899#1125720, @efriedma wrote:

The predicated trip count computation isn't modeling the loop in your example well; it thinks the maximum trip count is 2. But I guess that's okay.

It was 4 yesterday. I'll check it tomorrow when I'm back at work.

Confirmed: it computes it as 4.

[kparzysz]

This needs to be reworked.

include/llvm/Analysis/ScalarEvolution.h

public:
   /// normal unsigned value, if possible. This means that the actual trip
   /// count is always a multiple of the returned value (don't forget the trip
   /// count could very well be zero as well!). As explained in the comments
   /// for getSmallConstantTripCount, this assumes that control exits the loop
   /// via ExitingBlock.
   unsigned getSmallConstantTripMultiple(const Loop *L,
                                         BasicBlock *ExitingBlock);
 
+  /// Returns the upper bound of the loop trip count as a normal unsigned
+  /// value. The upper bound may be larger than the actual trip count.
+  /// Returns 0 if the trip count is unknown or cannot be estimated.
+  unsigned getSmallConstantTripCountUpperBound(const Loop *L);
+
   /// Get the expression for the number of loop iterations for which this loop
   /// is guaranteed not to exit via ExitingBlock. Otherwise return
   /// SCEVCouldNotCompute.
   const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
 
   /// If the specified loop has a predictable backedge-taken count, return it,
   /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
   /// the number of times the loop header will be branched to from within the

lib/Analysis/ScalarEvolution.cpp

 }
 
 unsigned ScalarEvolution::getSmallConstantMaxTripCount(const Loop *L) {
   const auto *MaxExitCount =
       dyn_cast<SCEVConstant>(getMaxBackedgeTakenCount(L));
   return getConstantTripCount(MaxExitCount);
 }
 
+unsigned ScalarEvolution::getSmallConstantTripCountUpperBound(const Loop *L) {
+  if (const SCEVConstant *TakenCount =
+          dyn_cast<SCEVConstant>(getBackedgeTakenCount(L))) {
+    if (unsigned C = getConstantTripCount(TakenCount))
+      return C;
+  }
+
+  if (unsigned C = getSmallConstantMaxTripCount(L))
+    return C;
+
+  SCEVUnionPredicate Ps;
+  const SCEV *PredBEC = getPredicatedBackedgeTakenCount(L, Ps);
+  if (PredBEC != getCouldNotCompute()) {
+    APInt S = getUnsignedRange(PredBEC).getSetSize();
+    if (S.getActiveBits() < 32)
+      return S.getZExtValue();
+  }
+
+  return 0;
+}
+
 unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L) {
   if (BasicBlock *ExitingBB = L->getExitingBlock())
     return getSmallConstantTripMultiple(L, ExitingBB);
 
   // No trip multiple information for multiple exits.
   return 0;
 }
 

lib/Transforms/Vectorize/LoopVectorize.cpp

unsigned LoopVectorizationCostModel::selectInterleaveCount(bool OptForSize,
   if (OptForSize)
     return 1;
 
   // We used the distance for the interleave count.
   if (Legal->getMaxSafeDepDistBytes() != -1U)
     return 1;
 
   // Do not interleave loops with a relatively small trip count.
-  unsigned TC = PSE.getSE()->getSmallConstantTripCount(TheLoop);
+  unsigned TC = PSE.getSE()->getSmallConstantTripCountUpperBound(TheLoop);
   if (TC > 1 && TC < TinyTripCountInterleaveThreshold)
     return 1;
 
   unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1);
   LLVM_DEBUG(dbgs() << "LV: The target has " << TargetNumRegisters
                     << " registers\n");
 
   if (VF == 1) {
#endif /* NDEBUG */
   if (!HasExpectedTC && LoopVectorizeWithBlockFrequency) {
     auto EstimatedTC = getLoopEstimatedTripCount(L);
     if (EstimatedTC) {
       ExpectedTC = *EstimatedTC;
       HasExpectedTC = true;
     }
   }
   if (!HasExpectedTC) {
-    ExpectedTC = SE->getSmallConstantMaxTripCount(L);
+    ExpectedTC = SE->getSmallConstantTripCountUpperBound(L);
     HasExpectedTC = (ExpectedTC > 0);
   }
 
   if (HasExpectedTC && ExpectedTC < TinyTripCountVectorThreshold) {
     LLVM_DEBUG(dbgs() << "LV: Found a loop with a very small trip count. "
                       << "This loop is worth vectorizing only if no scalar "
                       << "iteration overheads are incurred.");
     if (Hints.getForce() == LoopVectorizeHints::FK_Enabled)