[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 ↗

(On Diff #150400)

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

732 ↗

(On Diff #150400)

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

lib/Analysis/ScalarEvolution.cpp

6407

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

6414

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 ↗

(On Diff #150400)

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.

lib/Analysis/ScalarEvolution.cpp

unsigned ScalarEvolution::getSmallConstantTripCount(const Loop *L,
   const SCEVConstant *ExitCount =
       dyn_cast<SCEVConstant>(getExitCount(L, ExitingBlock));
   return getConstantTripCount(ExitCount);
 }
 
 unsigned ScalarEvolution::getSmallConstantMaxTripCount(const Loop *L) {
   const auto *MaxExitCount =
       dyn_cast<SCEVConstant>(getMaxBackedgeTakenCount(L));
-  return getConstantTripCount(MaxExitCount);
+  if (unsigned C = getConstantTripCount(MaxExitCount))
+    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;
 }
 
 /// Returns the largest constant divisor of the trip count of this loop as a
 /// 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!).
 ///
 /// Returns 1 if the trip count is unknown or not guaranteed to be the
 /// multiple of a constant (which is also the case if the trip count is simply
 /// constant, use getSmallConstantTripCount for that case), Will also return 1
 /// if the trip count is very large (>= 2^32).
 ///
 /// As explained in the comments for getSmallConstantTripCount, this assumes
 /// that control exits the loop via ExitingBlock.