This is an archive of the discontinued LLVM Phabricator instance.

Partial fix for bug 22589
ClosedPublic

Authored by sanjoy on Feb 17 2015, 8:09 PM.

Details

Summary

This change tries to solve the problem solved by revision 222451 in a way that does not require scalarizing the entire iteration space in case of overflow when computing the trip count of a runtime-unrolled loop. It also gets rid of the backedge check in the prologue loop and the extra check for overflowing trip-count.

I'm not familiar with this area, so would appreciate a close review.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 20139.Feb 17 2015, 8:09 PM
sanjoy retitled this revision from to Partial fix for bug 22589.
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: mzolotukhin, hfinkel, spatel.
sanjoy added a subscriber: Unknown Object (MLST).
majnemer added inline comments.
lib/Transforms/Utils/LoopUnrollRuntime.cpp
124

Should we assert that Count is > 0?

316–322

Can we use isPowerOf2_32 here?

327

Would it be cheaper to do Count > (1ULL << BEWidth)? If it isn't, could we use Log2_32? Count is unsigned.

hfinkel edited edge metadata.Feb 17 2015, 8:39 PM

Thanks for working on this.

I think this makes sense as a general simplification. Previously, we were trying to compare TripCount to Count, which required an additional check that TripCount == BECount+1 did not overflow. Comparing BECount to Count-1 is better because we don't need a separate overflow check.

lib/Transforms/Utils/LoopUnrollRuntime.cpp
349

Extra indentation.

sanjoy added inline comments.Feb 17 2015, 9:31 PM
lib/Transforms/Utils/LoopUnrollRuntime.cpp
124

That's a good idea, will do.

316–322

Is it okay to assume that unsigned is 32 bits long? Can it be 64 bits on a platform LLVM runs on?

327

Changed to static_cast<unsigned long long>(Count) > (1ULL << BEWidth).

349

Fixed

sanjoy updated this revision to Diff 20142.Feb 17 2015, 9:32 PM
sanjoy edited edge metadata.

Address review.

majnemer added inline comments.Feb 17 2015, 10:08 PM
lib/Transforms/Utils/LoopUnrollRuntime.cpp
316–322

This assumption is fine. If the distinction would matter, the code would be wrong on LLVM's current platforms because LLVM IR (and transforms on it) shouldn't depend on the compiler host.

majnemer added inline comments.Feb 17 2015, 10:12 PM
lib/Transforms/Utils/LoopUnrollRuntime.cpp
124

If Count is 1, then we are going to have BECount u< 0. Is this possible? If not, we should assert.

328

Using uint64_t instead of unsigned long long might be a little more concise.

sanjoy added inline comments.Feb 17 2015, 10:26 PM
lib/Transforms/Utils/LoopUnrollRuntime.cpp
124

I think that case is fine since if Count is 1 then we *should* unconditionally branch to the original loop. The invariant (AFAICT!) is that we branch to the original loop when the number of iterations that remain is a multiple of Count. That is always true for Count == 1.

I could add an assert but I'm not sure if there are edge cases where this code is called with Count == 1.

328

Will do.

sanjoy updated this revision to Diff 20145.Feb 17 2015, 10:36 PM

Address David's review.

hfinkel accepted this revision.Feb 18 2015, 5:29 AM
hfinkel edited edge metadata.

LGTM, thanks!

This revision is now accepted and ready to land.Feb 18 2015, 5:29 AM
This revision was automatically updated to reflect the committed changes.