Page MenuHomePhabricator

Partial fix for bug 22589

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



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.
122 ↗(On Diff #20139)

Should we assert that Count is > 0?

314 ↗(On Diff #20139)

Can we use isPowerOf2_32 here?

319 ↗(On Diff #20139)

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.

346 ↗(On Diff #20139)

Extra indentation.

sanjoy added inline comments.Feb 17 2015, 9:31 PM
122 ↗(On Diff #20139)

That's a good idea, will do.

314 ↗(On Diff #20139)

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

319 ↗(On Diff #20139)

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

346 ↗(On Diff #20139)


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
314 ↗(On Diff #20139)

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
124 ↗(On Diff #20142)

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

322 ↗(On Diff #20142)

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

sanjoy added inline comments.Feb 17 2015, 10:26 PM
124 ↗(On Diff #20142)

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.

322 ↗(On Diff #20142)

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.