[SCEV] Use range version of all_of; NFC

llvm-svn: 254275

[SCEV] Use C++11'isms

llvm-svn: 253837

ScalarEvolution: do not set nuw when creating exprs of form <expr> + <all-ones>.

The nuw constraint will not be satisfied unless <expr> == 0.

This bug has been around since r102234 (in 2010!), but

ScalarEvolution: do not set nuw when creating exprs of form <expr> + <all-ones>.

The nuw constraint will not be satisfied unless <expr> == 0.

This bug has been around since r102234 (in 2010!), but was uncovered by
r251052, which introduced more aggressive optimization of nuw scev expressions.

Differential Revision: http://reviews.llvm.org/D14850

llvm-svn: 253627

show more ...

Move helper classes into anonymous namespaces. NFC.

llvm-svn: 253189

Re-apply r251050 with a for PR25421

The bug: I missed adding break statements in the switch / case.

Original commit message:

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

Summary:

Re-apply r251050 with a for PR25421

The bug: I missed adding break statements in the switch / case.

Original commit message:

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

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.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: sanjoy, llvm-commits

Differential Revision: http://reviews.llvm.org/D13686

llvm-svn: 252236

show more ...

Revert r251050 to fix miscompile when running Clang -O1

See bug for details: https://llvm.org/bugs/show_bug.cgi?id=25421
Some comparisons were incorrectly replaced with a constant value.

llvm-svn:

Revert r251050 to fix miscompile when running Clang -O1

See bug for details: https://llvm.org/bugs/show_bug.cgi?id=25421
Some comparisons were incorrectly replaced with a constant value.

llvm-svn: 252231

show more ...

Refactor: Simplify boolean conditional return statements in llvm/lib/Analysis

Patch by Richard Thomson!

Differential revision: http://reviews.llvm.org/D9967

llvm-svn: 252209

[SCEV][LV] Add SCEV Predicates and use them to re-implement stride versioning

Summary:
SCEV Predicates represent conditions that typically cannot be derived from
static analysis, but can be used to

[SCEV][LV] Add SCEV Predicates and use them to re-implement stride versioning

Summary:
SCEV Predicates represent conditions that typically cannot be derived from
static analysis, but can be used to reduce SCEV expressions to forms which are
usable for different optimizers.

ScalarEvolution now has the rewriteUsingPredicate method which can simplify a
SCEV expression using a SCEVPredicateSet. The normal workflow of a pass using
SCEVPredicates would be to hold a SCEVPredicateSet and every time assumptions
need to be made a new SCEV Predicate would be created and added to the set.
Each time after calling getSCEV, the user will call the rewriteUsingPredicate
method.

We add two types of predicates
SCEVPredicateSet - implements a set of predicates
SCEVEqualPredicate - tests for equality between two SCEV expressions

We use the SCEVEqualPredicate to re-implement stride versioning. Every time we
version a stride, we will add a SCEVEqualPredicate to the context.
Instead of adding specific stride checks, LoopVectorize now adds a more
generic SCEV check.

We only need to add support for this in the LoopVectorizer since this is the
only pass that will do stride versioning.

Reviewers: mzolotukhin, anemet, hfinkel, sanjoy

Subscribers: sanjoy, hfinkel, rengolin, jmolloy, llvm-commits

Differential Revision: http://reviews.llvm.org/D13595

llvm-svn: 251800

show more ...

[SCEV] Fix PR25369

Have `getConstantEvolutionLoopExitValue` work correctly with multiple
entry loops.

As far as I can tell, `getConstantEvolutionLoopExitValue` never did the
right thing for multipl

[SCEV] Fix PR25369

Have `getConstantEvolutionLoopExitValue` work correctly with multiple
entry loops.

As far as I can tell, `getConstantEvolutionLoopExitValue` never did the
right thing for multiple entry loops; and before r249712 it would
silently return an incorrect answer. r249712 changed SCEV to fail an
assert on a multiple entry loop, and this change fixes the underlying
issue.

llvm-svn: 251770

show more ...

[SCEV] Don't create SCEV expressions that break LCSSA

Prevent `createNodeFromSelectLikePHI` from creating SCEV expressions
that break LCSSA.

A better fix for the same issue is to teach SCEVExpander

[SCEV] Don't create SCEV expressions that break LCSSA

Prevent `createNodeFromSelectLikePHI` from creating SCEV expressions
that break LCSSA.

A better fix for the same issue is to teach SCEVExpander to not break
LCSSA by inserting PHI nodes at appropriate places. That's planned for
the future.

Fixes PR25360.

llvm-svn: 251756

show more ...

[SCEV] Use auto and range for; NFC

llvm-svn: 251755

[SCEV] Generalize the SCEV algorithm for creating expressions for PHI nodes

Summary:
When forming expressions for phi nodes having an incoming value from
outside the loop A and a value coming from t

[SCEV] Generalize the SCEV algorithm for creating expressions for PHI nodes

Summary:
When forming expressions for phi nodes having an incoming value from
outside the loop A and a value coming from the previous iteration B
we were forming an AddRec if:
- B was an AddRec
- the value A was equal to the value for B at iteration -1 (or equal
to the value of B shifted by one iteration, at iteration 0)

In this case, we were computing the expression to be the expression of
B, shifted by one iteration.

This changes generalizes the logic above by removing the restriction that
B needs to be an AddRec. For this we introduce two expression rewriters
that allow us to
- shift an expression by one iteration
- get the value of an expression at iteration 0

This allows us to get SCEV expressions for PHI nodes when these expressions
are not AddRecExprs.

Reviewers: sanjoy

Subscribers: llvm-commits, sanjoy

Differential Revision: http://reviews.llvm.org/D14175

llvm-svn: 251700

show more ...

[SCEV] Compute max backedge count for loops with "shift ivs"

This teaches SCEV to compute //max// backedge taken counts for loops
like

for (int i = k; i != 0; i >>>= 1)
whatever();

SCEV

[SCEV] Compute max backedge count for loops with "shift ivs"

This teaches SCEV to compute //max// backedge taken counts for loops
like

for (int i = k; i != 0; i >>>= 1)
whatever();

SCEV yet cannot represent the exact backedge count for these loops, and
this patch does not change that. This is really geared towards teaching
SCEV that loops like the above are *not* infinite.

llvm-svn: 251558

show more ...

Put global classes into the appropriate namespace.

Most of the cases belong into an anonymous namespace. No
functionality change intended.

llvm-svn: 251515

[SCEV] Refactor out ScalarEvolution::getDataLayout; NFC

llvm-svn: 251375

[ScalarEvolution] Throw away dead code.

llvm-svn: 251256

[ScalarEvolution] Get rid of NDEBUG in header (correctly this time).

llvm-svn: 251255

[ScalarEvolution] Get rid of NDEBUG in header.

llvm-svn: 251249

Extract out getConstantRangeFromMetadata; NFC

The loop idiom creating a ConstantRange is repeated twice in the
codebase, time to give it a name and a home.

The loop is also repeated in `rangeMetada

Extract out getConstantRangeFromMetadata; NFC

The loop idiom creating a ConstantRange is repeated twice in the
codebase, time to give it a name and a home.

The loop is also repeated in `rangeMetadataExcludesValue`, but using
`getConstantRangeFromMetadata` there would not be an NFC -- the range
returned by `getConstantRangeFromMetadata` may contain a value that none
of the subranges did.

llvm-svn: 251180

show more ...

Fix whitespace issues in two places; NFC

llvm-svn: 251179

[SCEV] Fix stylistic issue in MatchBinaryAddToConst; NFCI

Instead of checking `(FlagsPresent & ExpectedFlags) != 0`, check
`(FlagsPresent & ExpectedFlags) == ExpectedFlags`. Right now they're
equiv

[SCEV] Fix stylistic issue in MatchBinaryAddToConst; NFCI

Instead of checking `(FlagsPresent & ExpectedFlags) != 0`, check
`(FlagsPresent & ExpectedFlags) == ExpectedFlags`. Right now they're
equivalent since `ExpectedFlags` can only be either `FlagNUW` or
`FlagNSW`, but if we ever pass in `ExpectedFlags` as `FlagNUW | FlagNSW`
then checking `(FlagsPresent & ExpectedFlags) != 0` would be wrong.

llvm-svn: 251142

show more ...

[SCEV] Get rid of an unnecessary lambda; NFC

llvm-svn: 251099

[SCEV] Fix a latent bug in `getPreStartForExtend`

I could not come up a way to test this -- I think this bug is latent
today, and will not actually result in a miscompile.

In `getPreStartForExtend`

[SCEV] Fix a latent bug in `getPreStartForExtend`

I could not come up a way to test this -- I think this bug is latent
today, and will not actually result in a miscompile.

In `getPreStartForExtend`, SCEV constructs `PreStart` as a sum of all of
`SA`'s operands except `Op`. It also uses `SA`'s no-wrap flags, and
this is problematic because removing an element from an add expression
can make it signed-wrap. E.g. if `SA` was `(127 + 1 + -1)`, then it
could safely be `<nsw>` (since `sext(127) + sext(1) + sext(-1)` ==
`sext(127 + 1 + -1)`), but `(127 + 1)` (== `PreStart` if `Op` is `-1`)
is not `<nsw>`.

Transferring `<nuw>` from `SA` to `PreStart` is safe, as far as I can
tell.

llvm-svn: 251097

show more ...

[SCEV] Commute zero extends through <nuw> additions

llvm-svn: 251052

[SCEV] Opportunistically interpret unsigned constraints as signed

Summary:
An unsigned comparision is equivalent to is corresponding signed version
if both the operands being compared are positive.

[SCEV] Opportunistically interpret unsigned constraints as signed

Summary:
An unsigned comparision is equivalent to is corresponding signed version
if both the operands being compared are positive. Teach SCEV to use
this fact when profitable.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D13687

llvm-svn: 251051

show more ...