[SCEV] Try to prove predicates by splitting them

Summary:
This change teaches SCEV that to prove `A u< B` it is sufficient to
prove each of these facts individually:

- B >= 0
- A s< B
- A >= 0

[SCEV] Try to prove predicates by splitting them

Summary:
This change teaches SCEV that to prove `A u< B` it is sufficient to
prove each of these facts individually:

- B >= 0
- A s< B
- A >= 0

In practice, SCEV sometimes finds it easier to prove these facts
individually than to prove `A u< B` as one atomic step.

Reviewers: reames, atrick, nlewycky, hfinkel

Subscribers: sanjoy, llvm-commits

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

llvm-svn: 249168

show more ...

[SCEV] Don't crash on pointer comparisons

`ScalarEvolution::isImpliedCondOperandsViaNoOverflow` tries to cast the
operand type of the comparison it is given to an `IntegerType`. This is
incorrect b

[SCEV] Don't crash on pointer comparisons

`ScalarEvolution::isImpliedCondOperandsViaNoOverflow` tries to cast the
operand type of the comparison it is given to an `IntegerType`. This is
incorrect because it could actually be simplifying a comparison between
two pointers. Switch it to using `getTypeSizeInBits` instead, which
does the right thing for both pointers and integers.

Fixed PR24956.

llvm-svn: 248743

show more ...

[SCEV] identical instructions don't compute equal values

Before this change `HasSameValue` would return true for distinct
`alloca` instructions if they happened to be allocating the same
type (`allo

[SCEV] identical instructions don't compute equal values

Before this change `HasSameValue` would return true for distinct
`alloca` instructions if they happened to be allocating the same
type (`alloca` instructions are not specified as reading memory). This
change adds an explicit whitelist of instruction types for which
"identical" instructions compute the same value.

Fixes PR24952.

llvm-svn: 248690

show more ...

[SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'

Summary:
If the trip count of a specific backedge is `N`, then we know that
backedge is effectively guarded by the condition

[SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'

Summary:
If the trip count of a specific backedge is `N`, then we know that
backedge is effectively guarded by the condition `{0,+,1} u< N`. This
change teaches SCEV to use this condition to prove things in
`isLoopBackedgeGuardedByCond`.

Depends on D12948
Depends on D12949

The original checkin, r248608 had to be backed out due to an issue with
a ObjCXX unit test. That issue is now fixed, so re-landing.

Reviewers: atrick, reames, majnemer, hfinkel

Subscribers: llvm-commits

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

llvm-svn: 248638

show more ...

[SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'

Summary:

This change teaches SCEV's `isImpliedCond` two new identities:

A u< B u< -C => (A + C) u< (B + C)
A s< B s< INT

[SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'

Summary:

This change teaches SCEV's `isImpliedCond` two new identities:

A u< B u< -C => (A + C) u< (B + C)
A s< B s< INT_MIN - C => (A + C) s< (B + C)

While these are useful on their own, they're really intended to support
D12950.

The original checkin, r248606 had to be backed out due to an issue with
a ObjCXX unit test. That issue is now fixed, so re-landing.

Reviewers: atrick, reames, majnemer, nlewycky, hfinkel

Subscribers: aadg, sanjoy, llvm-commits

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

llvm-svn: 248637

show more ...

Revert two SCEV changes that caused test failures in clang.

r248606: "[SCEV] Exploit A < B => (A+K) < (B+K) when possible"
r248608: "[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts."

Revert two SCEV changes that caused test failures in clang.

r248606: "[SCEV] Exploit A < B => (A+K) < (B+K) when possible"
r248608: "[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts."
llvm-svn: 248614

show more ...

[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.

Summary:
If the trip count of a specific backedge is `N`, then we know that
backedge is effectively guarded by the condition `{0,+,1}

[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.

Summary:
If the trip count of a specific backedge is `N`, then we know that
backedge is effectively guarded by the condition `{0,+,1} u< N`. This
change teaches SCEV to use this condition to prove things in
`isLoopBackedgeGuardedByCond`.

Depends on D12948
Depends on D12949

Reviewers: atrick, reames, majnemer, hfinkel

Subscribers: llvm-commits

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

llvm-svn: 248608

show more ...

[SCEV] Extract helper function from isImpliedCond; NFC

Summary:
This new helper routine will be used in a subsequent change.

Reviewers: hfinkel

Subscribers: hfinkel, sanjoy, llvm-commits

Differen

[SCEV] Extract helper function from isImpliedCond; NFC

Summary:
This new helper routine will be used in a subsequent change.

Reviewers: hfinkel

Subscribers: hfinkel, sanjoy, llvm-commits

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

llvm-svn: 248607

show more ...

[SCEV] Exploit A < B => (A+K) < (B+K) when possible

Summary:

This change teaches SCEV's `isImpliedCond` two new identities:

A u< B u< -C => (A + C) u< (B + C)
A s< B s< INT_MIN - C =

[SCEV] Exploit A < B => (A+K) < (B+K) when possible

Summary:

This change teaches SCEV's `isImpliedCond` two new identities:

A u< B u< -C => (A + C) u< (B + C)
A s< B s< INT_MIN - C => (A + C) s< (B + C)

While these are useful on their own, they're really intended to support
D12950.

Reviewers: atrick, reames, majnemer, nlewycky, hfinkel

Subscribers: aadg, sanjoy, llvm-commits

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

llvm-svn: 248606

show more ...

[SCEV] Introduce ScalarEvolution::getOne and getZero.

Summary:
It is fairly common to call SE->getConstant(Ty, 0) or
SE->getConstant(Ty, 1); this change makes such uses a little bit
briefer.

I've r

[SCEV] Introduce ScalarEvolution::getOne and getZero.

Summary:
It is fairly common to call SE->getConstant(Ty, 0) or
SE->getConstant(Ty, 1); this change makes such uses a little bit
briefer.

I've refactored the call sites I could find easily to use getZero /
getOne.

Reviewers: hfinkel, majnemer, reames

Subscribers: sanjoy, llvm-commits

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

llvm-svn: 248362

show more ...

[SCEV] Use SaveAndRestore<T> instead of a hand rolled struct; NFCI.

`ClearWalkingBEDominatingCondsOnExit` is exactly `SaveAndRestore<bool>`,
so use `SaveAndRestore<bool>` instead.

llvm-svn: 248227

[SCEV] Use auto instead of full iterator type; NFCI.

llvm-svn: 247919

ScalarEvolution: added tmp to avoid use-after-dtor in for loop.

Summary:
For loop destroyed current instance before invoking next.
Temporary variable added to prevent use-after-dtor when invoke
dest

ScalarEvolution: added tmp to avoid use-after-dtor in for loop.

Summary:
For loop destroyed current instance before invoking next.
Temporary variable added to prevent use-after-dtor when invoke
destructor on current instance.

Reviewers: eugenis

Subscribers: llvm-commits, sanjoy

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

Rename temp var.

llvm-svn: 247867

show more ...

[SCEV] Consistently Handle Expressions That Cannot Be Divided

This patch addresses the issue of SCEV division asserting on some
input expressions (e.g., non-affine expressions) and quietly giving
up

[SCEV] Consistently Handle Expressions That Cannot Be Divided

This patch addresses the issue of SCEV division asserting on some
input expressions (e.g., non-affine expressions) and quietly giving
up on others. When giving up, we set the quotient to be equal to
zero and the remainder to be equal to the numerator. With this
patch, we always quietly give up when we cannot perform the
division.

This patch also adds a test case for DependenceAnalysis that
previously caused an assertion.

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

llvm-svn: 247314

show more ...

[ScalarEvolution] Fix PR24757.

Summary:
PR24757 was caused by some incorect math in
`ScalarEvolution::HowFarToZero` -- the smallest unsigned solution for X
in

2^N * A = 2^N * X

is not necessaril

[ScalarEvolution] Fix PR24757.

Summary:
PR24757 was caused by some incorect math in
`ScalarEvolution::HowFarToZero` -- the smallest unsigned solution for X
in

2^N * A = 2^N * X

is not necessarily A.

Reviewers: atrick, majnemer, meheff

Subscribers: llvm-commits, sanjoy

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

llvm-svn: 247242

show more ...

ScalarEvolution assume hanging bugfix

http://reviews.llvm.org/D12719

llvm-svn: 247184

[SCEV] Fix GCC 4.8.0 ICE in lambda function

Rewrite some code to not use a lambda function. The non-lambda code is just
about as clean as the original, and not any longer. The lambda function causes

[SCEV] Fix GCC 4.8.0 ICE in lambda function

Rewrite some code to not use a lambda function. The non-lambda code is just
about as clean as the original, and not any longer. The lambda function causes
an internal compiler error in GCC 4.8.0, and it is not worth breaking support
for that compiler over this. NFC.

llvm-svn: 245466

show more ...

Make ScalarEvolution::isKnownPredicate a little smarter

Here we make ScalarEvolution::isKnownPredicate, indirectly, a little smarter.
Given some relational comparison operator OP, and two AddRec SCE

Make ScalarEvolution::isKnownPredicate a little smarter

Here we make ScalarEvolution::isKnownPredicate, indirectly, a little smarter.
Given some relational comparison operator OP, and two AddRec SCEVs, {I,+,S} OP
{J,+,T}, we can reduce this to the comparison I OP J when S == T, both AddRecs
are for the same loop, and both are known not to wrap.

As it turns out, because of the way that backedge-guard expressions can be
leveraged when computing known predicates, this allows indvars to simplify the
if-statement comparison in this loop:

void foo (int *a, int *b, int n) {
for (int i = 0; i < n; ++i) {
if (i > n)
a[i] = b[i] + 1;
}
}

which, somewhat surprisingly, we were not previously optimizing away.

llvm-svn: 245400

show more ...

[PM] Port ScalarEvolution to the new pass manager.

This change makes ScalarEvolution a stand-alone object and just produces
one from a pass as needed. Making this work well requires making the
objec

[PM] Port ScalarEvolution to the new pass manager.

This change makes ScalarEvolution a stand-alone object and just produces
one from a pass as needed. Making this work well requires making the
object movable, using references instead of overwritten pointers in
a number of places, and other refactorings.

I've also wired it up to the new pass manager and added a RUN line to
a test to exercise it under the new pass manager. This includes basic
printing support much like with other analyses.

But there is a big and somewhat scary change here. Prior to this patch
ScalarEvolution was never *actually* invalidated!!! Re-running the pass
just re-wired up the various other analyses and didn't remove any of the
existing entries in the SCEV caches or clear out anything at all. This
might seem OK as everything in SCEV that can uses ValueHandles to track
updates to the values that serve as SCEV keys. However, this still means
that as we ran SCEV over each function in the module, we kept
accumulating more and more SCEVs into the cache. At the end, we would
have a SCEV cache with every value that we ever needed a SCEV for in the
entire module!!! Yowzers. The releaseMemory routine would dump all of
this, but that isn't realy called during normal runs of the pipeline as
far as I can see.

To make matters worse, there *is* actually a key that we don't update
with value handles -- there is a map keyed off of Loop*s. Because
LoopInfo *does* release its memory from run to run, it is entirely
possible to run SCEV over one function, then over another function, and
then lookup a Loop* from the second function but find an entry inserted
for the first function! Ouch.

To make matters still worse, there are plenty of updates that *don't*
trip a value handle. It seems incredibly unlikely that today GVN or
another pass that invalidates SCEV can update values in *just* such
a way that a subsequent run of SCEV will incorrectly find lookups in
a cache, but it is theoretically possible and would be a nightmare to
debug.

With this refactoring, I've fixed all this by actually destroying and
recreating the ScalarEvolution object from run to run. Technically, this
could increase the amount of malloc traffic we see, but then again it is
also technically correct. ;] I don't actually think we're suffering from
tons of malloc traffic from SCEV because if we were, the fact that we
never clear the memory would seem more likely to have come up as an
actual problem before now. So, I've made the simple fix here. If in fact
there are serious issues with too much allocation and deallocation,
I can work on a clever fix that preserves the allocations (while
clearing the data) between each run, but I'd prefer to do that kind of
optimization with a test case / benchmark that shows why we need such
cleverness (and that can test that we actually make it faster). It's
possible that this will make some things faster by making the SCEV
caches have higher locality (due to being significantly smaller) so
until there is a clear benchmark, I think the simple change is best.

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

llvm-svn: 245193

show more ...

[SCEV] Apply NSW and NUW flags via poison value analysis for sub, mul and shl

Summary:
http://reviews.llvm.org/D11212 made Scalar Evolution able to propagate NSW and NUW flags from instructions to S

[SCEV] Apply NSW and NUW flags via poison value analysis for sub, mul and shl

Summary:
http://reviews.llvm.org/D11212 made Scalar Evolution able to propagate NSW and NUW flags from instructions to SCEVs for add instructions. This patch expands that to sub, mul and shl instructions.

This change makes LSR able to generate pointer induction variables for loops like these, where the index is 32 bit and the pointer is 64 bit:

for (int i = 0; i < numIterations; ++i)
sum += ptr[i - offset];

for (int i = 0; i < numIterations; ++i)
sum += ptr[i * stride];

for (int i = 0; i < numIterations; ++i)
sum += ptr[3 * (i << 7)];


Reviewers: atrick, sanjoy

Subscribers: sanjoy, majnemer, hfinkel, llvm-commits, meheff, jingyue, eliben

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

llvm-svn: 245118

show more ...

[IndVars] Fix PR24356.

Unsigned predicates increase or decrease agnostic of the signs of their
increments.

llvm-svn: 244265

Convert a bunch of loops to foreach. NFC.

After r244074, we now have a successors() method to iterate over
all the successors of a TerminatorInst. This commit changes a bunch
of eligible loops to

Convert a bunch of loops to foreach. NFC.

After r244074, we now have a successors() method to iterate over
all the successors of a TerminatorInst. This commit changes a bunch
of eligible loops to use it.

llvm-svn: 244260

show more ...

[SCEV] Apply NSW and NUW flags via poison value analysis

Summary:
Make Scalar Evolution able to propagate NSW and NUW flags from instructions to SCEVs in some cases. This is based on reasoning about

[SCEV] Apply NSW and NUW flags via poison value analysis

Summary:
Make Scalar Evolution able to propagate NSW and NUW flags from instructions to SCEVs in some cases. This is based on reasoning about when poison from instructions with these flags would trigger undefined behavior. This gives a 13% speed-up on some Eigen3-based Google-internal microbenchmarks for NVPTX.

There does not seem to be clear agreement about when poison should be considered to propagate through instructions. In this analysis, poison propagates only in cases where that should be uncontroversial.

This change makes LSR able to create induction variables for expressions like &ptr[i + offset] for loops like this:

for (int i = 0; i < limit; ++i) {
sum += ptr[i + offset];
}

Here ptr is a 64 bit pointer and offset is a 32 bit integer. For NVPTX, LSR currently creates an induction variable for i + offset instead, which is not as fast. Improving this situation is what brings the 13% speed-up on some Eigen3-based Google-internal microbenchmarks for NVPTX.


There are more details in this discussion on llvmdev.
June: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/thread.html#87234
July: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-July/thread.html#87392

Patch by Bjarke Roune

Reviewers: eliben, atrick, sanjoy

Subscribers: majnemer, hfinkel, jingyue, meheff, llvm-commits

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

llvm-svn: 243460

show more ...

[IndVars] Make loop varying predicates loop invariant.

Summary:
Was D9784: "Remove loop variant range check when induction variable is
strictly increasing"

This change re-implements D9784 with the

[IndVars] Make loop varying predicates loop invariant.

Summary:
Was D9784: "Remove loop variant range check when induction variable is
strictly increasing"

This change re-implements D9784 with the two differences:

1. It does not use SCEVExpander and does not generate new
instructions. Instead, it does a quick local search for existing
`llvm::Value`s that it needs when modifying the `icmp`
instruction.

2. It is more general -- it deals with both increasing and decreasing
induction variables.

I've added all of the tests included with D9784, and two more.

As an example on what this change does (copied from D9784):

Given C code:

```
for (int i = M; i < N; i++) // i is known not to overflow
if (i < 0) break;
a[i] = 0;
}
```

This transformation produces:

```
for (int i = M; i < N; i++)
if (M < 0) break;
a[i] = 0;
}
```

Which can be unswitched into:

```
if (!(M < 0))
for (int i = M; i < N; i++)
a[i] = 0;
}
```

I went back and forth on whether the top level logic should live in
`SimplifyIndvar::eliminateIVComparison` or be put into its own
routine. Right now I've put it under `eliminateIVComparison` because
even though the `icmp` is not *eliminated*, it no longer is an IV
comparison. I'm open to putting it in its own helper routine if you
think that is better.

Reviewers: reames, nicholas, atrick

Subscribers: llvm-commits

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

llvm-svn: 243331

show more ...

[ScalarEvolution] Change addRequired to addRequiredTransitive on two passes where ScalarEvolution stores long lived raw pointers to objects those passes own.

This prevents the pointers from dangling

[ScalarEvolution] Change addRequired to addRequiredTransitive on two passes where ScalarEvolution stores long lived raw pointers to objects those passes own.

This prevents the pointers from dangling when those passes are freed.

http://reviews.llvm.org/D11236
Patch by Steve King.

llvm-svn: 242989

show more ...