This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Improve the run-time checking of the NoWrap predicate
ClosedPublic

Authored by sbaranga on Apr 19 2016, 8:47 AM.

Details

Summary

This implements a new method of run-time checking the NoWrap
SCEV predicates, which should be easier to optimize and nicer
for targets that don't correctly handle multiplication/addition
of large integer types (like i128).

If the AddRec is {a,+,b} and the backedge taken count is c,
the idea is to check that |b| * c doesn't have unsigned overflow,
and depending on the sign of b, that:

a + |b| * c >= a (b >= 0) or
a - |b| * c <= a (b <= 0)

where the comparisons above are signed or unsigned, depending on
the flag that we're checking.

The advantage of doing this is that we avoid extending to a larger
type and we avoid the multiplication of large types (multiplying
i128 can be expensive).

Diff Detail

Event Timeline

sbaranga updated this revision to Diff 54202.Apr 19 2016, 8:47 AM
sbaranga retitled this revision from to [SCEV] Improve the run-time checking of the NoWrap predicate.
sbaranga updated this object.
sbaranga added a reviewer: sanjoy.
sbaranga added a subscriber: llvm-commits.
sanjoy added inline comments.Apr 22 2016, 1:43 AM
lib/Analysis/ScalarEvolutionExpander.cpp
2020

One of these has to include Step == 0.

2021

Spelling: "Step > 0"

2022

Nit: I'd be explicit here about "... doesn't unsigned overflow"

2086

Why not just check if Step < 0? (Assuming later passes don't optimize this) That way we won't have compute -Step if Step is positive.

2102

I'd keep the operands in the same order in both the cases.

2132

Why do you need this extra check? If Step is 0 then won't both the less than and the greater than check return false?

sbaranga added inline comments.Apr 22 2016, 2:55 AM
lib/Analysis/ScalarEvolutionExpander.cpp
2086

Sure, that makes sense.

2132

The problem is that we have an edge case where we discard bits by truncating the backedge taken count and the step is 0. In this case we don't have overflow. It would be better to create it only when we need to truncate the backedge taken count and create the and with the 'BackedgeCount < MAX_UINT(Type(Start))' comparison.

sbaranga updated this revision to Diff 54643.Apr 22 2016, 7:04 AM

Only compare the step with 0 when we need to truncate the backedge taken count.
Otherwise, the case where the step is 0 is correctly handled.

Address the other comments received in the review.

sanjoy accepted this revision.Apr 22 2016, 10:35 PM
sanjoy edited edge metadata.
This revision is now accepted and ready to land.Apr 22 2016, 10:35 PM
This revision was automatically updated to reflect the committed changes.