This is an archive of the discontinued LLVM Phabricator instance.

Use ISL to Determine Loop Trip Count
ClosedPublic

Authored by mssimpso on May 1 2015, 2:05 PM.

Details

Summary

Use ISL to compute the loop trip count when scalar evolution is
unable to do so.

Patch originally by Johannes Doerfert!

Diff Detail

Event Timeline

mssimpso updated this revision to Diff 24829.May 1 2015, 2:05 PM
mssimpso retitled this revision from to [Polly] Use ISL to Determine Loop Trip Count.
mssimpso updated this object.
mssimpso edited the test plan for this revision. (Show Details)
mssimpso added a project: Restricted Project.
mssimpso removed a project: Restricted Project.
mssimpso added subscribers: Unknown Object (MLST), Restricted Project.
mssimpso updated this object.May 1 2015, 2:22 PM
jdoerfert edited edge metadata.May 4 2015, 6:19 AM

Some comments are inlined. Except those and the test coverage we could improve the patch LGTM.

We should probably add a test case for the nsw problem, e.g., that we do not check for nsw and therefore can assume an unconstrainted loop. The example should probably look similar to the one below, however we would need to force ScalarEvolution to not recognize the loop trip count.

// Infinite loop for N < 0 in a non-wrapping world.
for (int i = 0; i < N; i++)
  A[i] = i;
lib/Analysis/ScopDetection.cpp
804

move this in the if of the next line

1039

I don't think we need this as the loops we now allow are "affine" hence the hasAffineLoops should be set to true if we encountered one. If not we want to bail even if we would allow such loops.

lib/Analysis/ScopInfo.cpp
99

I know there was no documentation for this function before, but maybe you could write a short one that explains that this computes not the real loop-depth (in the sence of Loop/LoopInfo) but a relative one in the SCoP.

602

I don't get this change. If the input space (setDomain) was 0-dimensional we return a map like: [ ] -> [ ] ?

Could you give me some intuition why?

750

Our virtual loops (i0,i1,..) always start at 0. We should keep it that way otherwise we will soon end up with an offset by 1 mess. This should also simplify this code block a bit.

761

We should not enforce unsigned conditions, they are/will be supported soon (at least under a flag).

test/ScopInfo/isl_trip_count.ll
3 ↗(On Diff #24829)

see offset-by-one comment above.

grosser edited edge metadata.May 19 2015, 9:13 AM

Is this patch waiting for some kind of feedback from my side? Johannes already gave a good review so feel free to follow up with him.

One comment:

  1. We should enable this by default to ensure we get enough test coverage.
mssimpso updated this revision to Diff 32987.Aug 24 2015, 12:23 PM
mssimpso edited edge metadata.

Rebased and addressed comments. Thanks for the reviews!

@grosser:

Flag is now enabled by default.

@jdoerfert:

My apologies for waiting so long to update this patch. I've addressed your
comments, added an additional test case, and performed some additional
refactoring. Regarding the actual computation of the trip count, I made a small
adjustment to the expression given in the PET paper. I now simplify the
condition on the domain to remove unnecessary constraints. This corrects the
"offset-by-one" issue you pointed out in the original test case and also fixes
some cases we saw in our internal testing.

mssimpso updated this object.Aug 24 2015, 12:26 PM
mssimpso marked 5 inline comments as done.Aug 24 2015, 12:32 PM
mssimpso added inline comments.
lib/Analysis/ScopDetection.cpp
804

I moved this to canUseISLTripCount.

1039

Agreed. I now set Context.hasAffineLoops = true if canUseISLTripCount succeeds.

lib/Analysis/ScopInfo.cpp
99

I made this utility a member of Scop since SCEVAffinator was factored out since the initial revision.

602

This was a mistake.

750

See comment above. I simplify the condition on the domain to remove unnecessary constraints.

mssimpso retitled this revision from [Polly] Use ISL to Determine Loop Trip Count to Use ISL to Determine Loop Trip Count.Aug 24 2015, 12:55 PM
jdoerfert accepted this revision.Aug 24 2015, 8:52 PM
jdoerfert edited edge metadata.

LGTM, if it passes LNT (and maybe even your internal test). I will work on the domain modeling again soon but this is a really good starting point.

lib/Analysis/ScopDetection.cpp
784

For now we can be restrictive but could you explain to me why do we need this part? I want to refactor the Domain creation soon and any information you have would be usefull.

This revision is now accepted and ready to land.Aug 24 2015, 8:52 PM
mssimpso marked 4 inline comments as done.Aug 25 2015, 7:02 AM
mssimpso added inline comments.
lib/Analysis/ScopDetection.cpp
784

Without the invariant check, we were hitting cases like for (int i=0; i < A[i]; i++) (e.g., in test/ScopDetect/non-affine-loop.ll). This was previously rejected because the trip count could not be computed by SCEV.

798

I think the refactoring was a bit too aggressive here. If the trip count is computable by SCEV, but it is not affine, we still need to reject. I will post an update shortly.

mssimpso updated this revision to Diff 33076.Aug 25 2015, 7:23 AM
mssimpso edited edge metadata.

Removed some refactoring to restore correct behavior.

@jdoerfert:

Please feel free to commit this change when you're satisfied with it, as I do
not yet have commit access. Thanks!

This revision was automatically updated to reflect the committed changes.