[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

[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: 251050

show more ...

[SCEV] Commute sign extends through nsw additions

Summary: Depends on D13613.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: llvm-commits

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

[SCEV] Commute sign extends through nsw additions

Summary: Depends on D13613.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: llvm-commits

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

llvm-svn: 251049

show more ...

[SCEV] Mark AddExprs as nsw or nuw if legal

Summary:
This uses `ScalarEvolution::getRange` and not potentially control
dependent `nsw` and `nuw` bits on the arithmetic instruction.

Reviewers: atric

[SCEV] Mark AddExprs as nsw or nuw if legal

Summary:
This uses `ScalarEvolution::getRange` and not potentially control
dependent `nsw` and `nuw` bits on the arithmetic instruction.

Reviewers: atrick, hfinkel, nlewycky

Subscribers: llvm-commits, sanjoy

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

llvm-svn: 251048

show more ...

[SCEV] Fix whitespace issues and remove extra braces; NFC

llvm-svn: 250636

[SCEV] Use std::all_of and std::any_of; NFC

llvm-svn: 250635

[SCEV] Use auto where it helps remove line breaks; NFC

llvm-svn: 250634

[SCEV] Use range for loops; NFC

llvm-svn: 250633

[SCEV] Use `SCEV::isAllOnesValue` directly; NFC.

Instead of `dyn_cast` ing to `SCEVConstant` and checking the contained
`ConstantInteger.

llvm-svn: 250251

[SCEV] Put some utilites in the ScalarEvolution class

In a later commit, `SplitBinaryAdd` will be used outside `IsConstDiff`,
so lift that out. And lift out `IsConstDiff` as
`computeConstantDiffere

[SCEV] Put some utilites in the ScalarEvolution class

In a later commit, `SplitBinaryAdd` will be used outside `IsConstDiff`,
so lift that out. And lift out `IsConstDiff` as
`computeConstantDifference` to keep things clean and to avoid playing
C++ access specifier games.

NFC.

llvm-svn: 250143

show more ...

SCEV: Allow simple AddRec * Parameter products in delinearization

This patch also allows the -delinearize pass to delinearize expressions that do
not have an outermost SCEVAddRec expression. The SCE

SCEV: Allow simple AddRec * Parameter products in delinearization

This patch also allows the -delinearize pass to delinearize expressions that do
not have an outermost SCEVAddRec expression. The SCEV::delinearize
infrastructure allowed this since r240952, but the -delinearize pass was not
updated yet.

llvm-svn: 250018

show more ...

[SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCI

The current implementation of `StrengthenNoWrapFlags` is agnostic to the
order of `Ops`, so this commit should not change anything

[SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCI

The current implementation of `StrengthenNoWrapFlags` is agnostic to the
order of `Ops`, so this commit should not change anything semantic. An
upcoming change will make `StrengthenNoWrapFlags` sensitive to the order
of `Ops`.

llvm-svn: 249802

show more ...

[SCEV] Bring some methods up to coding style; NFC

- Start methods with lower case
- Reflow a comment
- Delete header comment repeated in .cpp file

llvm-svn: 249716

[SCEV] Remove comment repeated in cpp file; NFC

llvm-svn: 249713

[SCEV] Pick backedge values for phi nodes correctly

Summary:
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`
assumed all phi nodes in the loop header have the same order of in

[SCEV] Pick backedge values for phi nodes correctly

Summary:
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`
assumed all phi nodes in the loop header have the same order of incoming
values. This is not correct, and this commit changes
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`
to lookup the backedge value of a phi node using the loop's latch block.

Unfortunately, there is still some code duplication
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`.
At some point in the future we should extract out a helper class /
method that can evolve constant evolution phi nodes across iterations.

Fixes 25060. Thanks to Mattias Eriksson for the spot-on analysis!

Depends on D13457.

Reviewers: atrick, hfinkel

Subscribers: materi, llvm-commits

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

llvm-svn: 249712

show more ...

[SCEV] Check `Pred` first in isKnownPredicateViaSplitting

Comparing `Pred` with `ICmpInst::ICMP_ULT` is cheaper that memory access
-- do that check before loading / storing `ProvingSplitPredicate`.

[SCEV] Check `Pred` first in isKnownPredicateViaSplitting

Comparing `Pred` with `ICmpInst::ICMP_ULT` is cheaper that memory access
-- do that check before loading / storing `ProvingSplitPredicate`.

llvm-svn: 249654

show more ...

[SCEV] Use `auto *` instead of `auto`; NFCI

(As prescribed by the coding style document)

llvm-svn: 249653

Revert "Revert "This patch builds on top of D13378 to handle constant condition.""

This reverts commit r249528 and reapply r249431. The fix for the
fallout has been commited in r249575.

From: Mehdi

Revert "Revert "This patch builds on top of D13378 to handle constant condition.""

This reverts commit r249528 and reapply r249431. The fix for the
fallout has been commited in r249575.

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 249581

show more ...

[SCEV] Use some C++11'ism, NFC

Summary:

Subscribers: llvm-commits

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

llvm-svn: 249574

Revert "This patch builds on top of D13378 to handle constant condition."

This reverts commit r249431. This caused failures in sqlite3: http://lab.llvm.org:8011/builders/clang-native-arm-lnt/builds/

Revert "This patch builds on top of D13378 to handle constant condition."

This reverts commit r249431. This caused failures in sqlite3: http://lab.llvm.org:8011/builders/clang-native-arm-lnt/builds/14453

llvm-svn: 249528

show more ...

This patch builds on top of D13378 to handle constant condition.

With this patch, clang -O3 optimizes correctly providing > 1000x speedup on this artificial benchmark):

for (a=0; a<n; a++)
for

This patch builds on top of D13378 to handle constant condition.

With this patch, clang -O3 optimizes correctly providing > 1000x speedup on this artificial benchmark):

for (a=0; a<n; a++)
for (b=0; b<n; b++)
for (c=0; c<n; c++)
for (d=0; d<n; d++)
for (e=0; e<n; e++)
for (f=0; f<n; f++)
x++;
From test-suite/SingleSource/Benchmarks/Shootout/nestedloop.c

Reviewers: sanjoyd

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

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 249431

show more ...

Try to appease MSVC, NFCI.

This time by lifting the lambda's in `createNodeFromSelectLikePHI` to
the file scope. Looks like there are differences in capture rules
between clang and MSVC?

llvm-svn:

Try to appease MSVC, NFCI.

This time by lifting the lambda's in `createNodeFromSelectLikePHI` to
the file scope. Looks like there are differences in capture rules
between clang and MSVC?

llvm-svn: 249222

show more ...

Try to appease the MSVC bots, NFCI.

llvm-svn: 249219

Try to appease the MSVC bots, NFC.

llvm-svn: 249216

[SCEV] Recognize simple br-phi patterns

Summary:
Teach SCEV to match patterns like

```
br %cond, label %left, label %right
left:
br label %merge
right:
br label %merge
merge:
V = phi [ %

[SCEV] Recognize simple br-phi patterns

Summary:
Teach SCEV to match patterns like

```
br %cond, label %left, label %right
left:
br label %merge
right:
br label %merge
merge:
V = phi [ %x, %left ], [ %y, %right ]
```

as "select %cond, %x, %y". Before this SCEV would match PHI nodes
exclusively to add recurrences.

This addresses PR25005.

Reviewers: joker.eph, joker-eph, atrick

Subscribers: llvm-commits

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

llvm-svn: 249211

show more ...

[SCEV] Refactor out a createNodeForSelect

Summary:
We will shortly re-use this for select-like br-phi pairs.

Reviewers: atrick, joker-eph, joker.eph

Subscribers: sanjoy, llvm-commits

Differential

[SCEV] Refactor out a createNodeForSelect

Summary:
We will shortly re-use this for select-like br-phi pairs.

Reviewers: atrick, joker-eph, joker.eph

Subscribers: sanjoy, llvm-commits

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

llvm-svn: 249177

show more ...