This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Implement (non-exact) getSmallConstantTripCountUpperBound
AbandonedPublic

Authored by kparzysz on Jun 7 2018, 12:04 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

kparzysz created this revision.Jun 7 2018, 12:04 PM
efriedma added inline comments.
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.

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.

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

kparzysz updated this revision to Diff 150400.Jun 7 2018, 1:31 PM
kparzysz retitled this revision from [SCEV] Estimate upper bound of trip count from predicated backedge count to [SCEV] Implement (non-exact) getSmallConstantTripCountUpperBound.
kparzysz edited the summary of this revision. (Show Details)

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

kparzysz added a reviewer: dcaballe.

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.

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.

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 abandoned this revision.Jun 8 2018, 9:11 AM

This needs to be reworked.