This is an archive of the discontinued LLVM Phabricator instance.

SCEVExpander incorrectly marks increment operations as no-wrap
ClosedPublic

Authored by sanjoy on Feb 19 2015, 5:58 PM.

Details

Summary

When emitting the increment operation, SCEVExpander marks the
operation as nuw or nsw based on the flags on the preincrement SCEV.
This is incorrect because, for instance, it is possible that {-6,+,1}
is <nuw> while {-6,+,1}+1 = {-5,+,1} is not.

This change teaches SCEV to mark the increment as nuw/nsw only if it
can explicitly prove that the increment operation won't overflow.

Apart from the attached test case, another (more realistic) manifestation
of the bug can be seen in Transforms/IndVarSimplify/pr20680.ll.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 20361.Feb 19 2015, 5:58 PM
sanjoy retitled this revision from to SCEVExpander incorrectly marks increment operations as no-wrap.
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: atrick, majnemer, hfinkel.
sanjoy added a subscriber: Unknown Object (MLST).
atrick accepted this revision.Feb 23 2015, 11:51 AM
atrick edited edge metadata.

LGTM

This revision is now accepted and ready to land.Feb 23 2015, 11:51 AM
This revision was automatically updated to reflect the committed changes.

Another related problem is with how SCEVExpander will sometimes emit
subtractions instead of additions. As you know, nuw and nsw flags
don't carry over from 'add X (-Y)' to 'sub X Y'. There are two
obvious ways out of this:

  • don't generate subtractions
  • if you do generate a subtraction, don't tag it with nuw/nsw even if

the addition is nuw/nsw.

The question I do not have the answer to is why SCEVExpander generates
subtractions at all. Is the a code-gen issue?

Sub X Y is the canonical form though, so what SCEVExpander does makes sense, particularly if it's trying to avoid emitting redundant instructions. But it's not very smart to throw away the nuw/nsw flags unless we know they can be inferred again later.

You're right that changing this could affect codegen. Probably only for fast-isel though, and only if InstCombine isn't going to be run. So it really only matters for LoopStrengthReduce, which probably won't be run with fast-isel.

SCEVExpander could have a mode that attempts to preserve flags, and a mode where it just always generates the sub. Or you can try to generate the sub whenever it doesn't lose the flags. However, I vote for keeping it simple and just always generating the add and letting InstCombine cleanup if it actually matters. You might then want to fix InstCombine so it doesn't convert to sub and drop the flags in these cases. (actually there should be a TargetInstCombine that drops the flags just before isel, but I digress).

Incidentally, are you more often relying on nsw/nuw to be inferred within SCEV, or are you relying more on your frontend to generate them in special situations?

SCEVExpander could have a mode that attempts to preserve flags, and a mode where it just always generates the sub. Or you can try to generate the sub whenever it doesn't lose the flags. However, I vote for keeping it simple and just always generating the add and letting InstCombine cleanup if it actually matters.

I agree -- I'll put up a patch for review shortly.

Incidentally, are you more often relying on nsw/nuw to be inferred within SCEV, or are you relying more on your frontend to generate them in special situations?

All Java-level integer arithmetic gets lowered into
potentially-wrapping operations, and it is up to scalar evolution to
prove when overflow does not happen.

Slight tangent: I noticed is that LFTR will not happen for a loop
with multiple exiting blocks. Most of the interesting loops we
generate have multiple exiting blocks due to range checks and null
checks, so this may yet be another area where we end up missing some
optimizations because of non-canonical IR.

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7778

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/