This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Teach SCEV some axioms about non-wrapping arithmetic
ClosedPublic

Authored by sanjoy on Oct 12 2015, 9:29 PM.

Details

Summary
  • A s< (A + C)<nsw> if C > 0
  • A s<= (A + C)<nsw> if C >= 0
  • (A + C)<nsw> s< A if C < 0
  • (A + C)<nsw> s<= A if C <= 0

Right now C needs to be a constant, but we can later generalize it to
be a non-constant if needed.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 37212.Oct 12 2015, 9:29 PM
sanjoy retitled this revision from to [SCEV] Teach SCEV some axioms about non-wrapping arithmetic.
sanjoy updated this object.
sanjoy added reviewers: atrick, hfinkel, reames, nlewycky.
sanjoy added a subscriber: llvm-commits.
reames added inline comments.Oct 14 2015, 12:26 PM
include/llvm/Analysis/ScalarEvolution.h
579

The naming of this seems really odd. Possibly: ViaIntegerFacts?

"certian kinds of overflow" is confusing in the comment.

lib/Analysis/ScalarEvolution.cpp
7177

A comment explaining what this matches would help.

7199

Notation wise: X s<= (X +<nsw> C) if C >= 0 would be far more clear.

reames requested changes to this revision.Oct 14 2015, 12:26 PM
reames edited edge metadata.
This revision now requires changes to proceed.Oct 14 2015, 12:26 PM
sanjoy added inline comments.Oct 14 2015, 1:16 PM
include/llvm/Analysis/ScalarEvolution.h
579

ViaIntegerFacts seems just as vague as (if not more) ViaNoOverflow to me. :) There are many integer facts that we can use without proving no overflow (e.g. transitivity of <), but this function focuses on using integer facts that are not valid if the the operation in LHS / RHS overflow. I can work this into the comment if you think that'll help. I can also drop the "certain kinds" bit form the comment and just say "ruling out integer overflow".

lib/Analysis/ScalarEvolution.cpp
7177

Will do.

7199

(A + B)<nsw> is the standard notation used when printing SCEV expressions, so I'd rather keep it that way for consistency.

sanjoy updated this revision to Diff 37629.Oct 16 2015, 1:01 PM
sanjoy edited edge metadata.
sanjoy marked an inline comment as done.
  • address review
reames requested changes to this revision.Oct 21 2015, 6:43 PM
reames edited edge metadata.
reames added inline comments.
lib/Analysis/ScalarEvolution.cpp
7203

Er, this doesn't seem to match either the name or signature of the lambda above?

This revision now requires changes to proceed.Oct 21 2015, 6:43 PM
sanjoy updated this revision to Diff 38074.Oct 21 2015, 7:16 PM
sanjoy edited edge metadata.
  • I accidentally fat fingered the diff upload last time, uploading the correct diff
reames accepted this revision.Oct 22 2015, 11:22 AM
reames edited edge metadata.

LGTM w/minor comment.

test/Transforms/IndVarSimplify/eliminate-comparison.ll
480

A short comment about *what* this is testing for would make it far easier to understand.

This revision is now accepted and ready to land.Oct 22 2015, 11:22 AM
This revision was automatically updated to reflect the committed changes.
rtrieu added a subscriber: rtrieu.Nov 5 2015, 12:40 PM

r251050 may be causing a miscompile. See:
https://llvm.org/bugs/show_bug.cgi?id=25421