[SCEV] Don't infinitely recurse on unreachable code

llvm-svn: 277848

Revert r276136 "Use ValueOffsetPair to enhance value reuse during SCEV expansion."

It causes Clang tests to fail after Windows self-host (PR28705).

(Also reverts follow-up r276139.)

llvm-svn: 2768

Revert r276136 "Use ValueOffsetPair to enhance value reuse during SCEV expansion."

It causes Clang tests to fail after Windows self-host (PR28705).

(Also reverts follow-up r276139.)

llvm-svn: 276822

show more ...

[SCEV] Make isImpliedCondOperandsViaRanges smarter

This change lets us prove things like

"{X,+,10} s< 5000" implies "{X+7,+,10} does not sign overflow"

It does this by replacing replacing getCon

[SCEV] Make isImpliedCondOperandsViaRanges smarter

This change lets us prove things like

"{X,+,10} s< 5000" implies "{X+7,+,10} does not sign overflow"

It does this by replacing replacing getConstantDifference by
computeConstantDifference (which is smarter) in
isImpliedCondOperandsViaRanges.

llvm-svn: 276505

show more ...

[SCEV] Change the interface of computeConstantDifference; NFC

This is in preparation of
s/getConstantDifference/computeConstantDifference/ in a later change.

llvm-svn: 276503

[SCEV] Extract out a helper function; NFC

The helper will get smarter in a later change, but right now this is
just code reorganization.

llvm-svn: 276467

Use ValueOffsetPair to enhance value reuse during SCEV expansion.

In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion.
However, const folding and sext/zext distributi

Use ValueOffsetPair to enhance value reuse during SCEV expansion.

In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion.
However, const folding and sext/zext distribution can make the reuse still difficult.

A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and
S1 = S2 + C_a
S3 = S2 + C_b
where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as
V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a
complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused
by the fact that S3 is generated from S1 after const folding.

In order to do that, we represent ExprValueMap as a mapping from SCEV to
ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the
ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first
expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to
V1 - C_a + C_b.

Differential Revision: https://reviews.llvm.org/D21313

llvm-svn: 276136

show more ...

Teach SCEV to look through returned-argument functions

When building SCEVs, if a function is known to return its argument, then we can
build the SCEV using the corresponding argument value.

Differe

Teach SCEV to look through returned-argument functions

When building SCEVs, if a function is known to return its argument, then we can
build the SCEV using the corresponding argument value.

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

llvm-svn: 275037

show more ...

Untabify.

llvm-svn: 274479

Use arrays or initializer lists to feed ArrayRefs instead of SmallVector where possible.

No functionality change intended.

llvm-svn: 274431

[SCEV] Compute max be count from shift operator only if all else fails

In particular, check to see if we can compute a precise trip count by
exhaustively simulating the loop first.

llvm-svn: 274199

Apply clang-tidy's modernize-loop-convert to lib/Analysis.

Only minor manual fixes. No functionality change intended.

llvm-svn: 273816

[SCEV] Fix incorrect trip count computation

The way we elide max expressions when computing trip counts is incorrect
-- it breaks cases like this:

```
static int wrapping_add(int a, int b) {
retu

[SCEV] Fix incorrect trip count computation

The way we elide max expressions when computing trip counts is incorrect
-- it breaks cases like this:

```
static int wrapping_add(int a, int b) {
return (int)((unsigned)a + (unsigned)b);
}

void test() {
volatile int end_buf = 2147483548; // INT_MIN - 100
int end = end_buf;

unsigned counter = 0;
for (int start = wrapping_add(end, 200); start < end; start++)
counter++;

print(counter);
}
```

Note: the `NoWrap` variable that was being tested has little to do with
the values flowing into the max expression; it is a property of the
induction variable.

test/Transforms/LoopUnroll/nsw-tripcount.ll was added to solely test
functionality I'm reverting in this change, so I've deleted the test
fully.

llvm-svn: 273079

show more ...

[SCEV] Use dyn_cast<T> instead of dyn_cast<const T>; NFC

The const is unnecessary.

llvm-svn: 272759

[SCEV] Use cast<> instead of dyn_cast; NFC

llvm-svn: 272758

[SCEV] clang-format some sections

llvm-svn: 272753

[SCEV] Change the interface for SolveQuadraticEquation; NFC

Use Optional<T> to denote the absence of a solution, not
SCEVCouldNotCompute. This makes the usage of SolveQuadraticEquation
somewhat sim

[SCEV] Change the interface for SolveQuadraticEquation; NFC

Use Optional<T> to denote the absence of a solution, not
SCEVCouldNotCompute. This makes the usage of SolveQuadraticEquation
somewhat simpler.

llvm-svn: 272752

show more ...

Minor clean up in loopHasNoAbnormalExits; NFC

llvm-svn: 272238

Be wary of abnormal exits from loop when exploiting UB

We can safely rely on a NoWrap add recurrence causing UB down the road
only if we know the loop does not have a exit expressed in a way that is

Be wary of abnormal exits from loop when exploiting UB

We can safely rely on a NoWrap add recurrence causing UB down the road
only if we know the loop does not have a exit expressed in a way that is
opaque to ScalarEvolution (e.g. by a function call that conditionally
calls exit(0)).

I believe with this change PR28012 is fixed.

Note: I had to change some llvm-lit tests in LoopReroll, since it looks
like they were depending on this incorrect behavior.

llvm-svn: 272237

show more ...

Factor out a loopHasNoAbnormalExits; NFC

llvm-svn: 272236

Apply most suggestions of clang-tidy's performance-unnecessary-value-param

Avoids unnecessary copies. All changes audited & pass tests with asan.
No functional change intended.

llvm-svn: 272190

[SCEV] Break out of loop if there is no more work to do

This is NFC as far as externally visible behavior is concerned, but will
keep us from spinning in the worklist traversal algorithm unnecessari

[SCEV] Break out of loop if there is no more work to do

This is NFC as far as externally visible behavior is concerned, but will
keep us from spinning in the worklist traversal algorithm unnecessarily.

llvm-svn: 272182

show more ...

[SCEV] Track no-abnormal-exits instead of no-throw calls

Absence of may-unwind calls is not enough to guarantee that a
UB-generating use of an add-rec poison in the loop latch will actually
cause UB

[SCEV] Track no-abnormal-exits instead of no-throw calls

Absence of may-unwind calls is not enough to guarantee that a
UB-generating use of an add-rec poison in the loop latch will actually
cause UB. We also need to guard against calls that terminate the thread
or infinite loop themselves.

This partially addresses PR28012.

llvm-svn: 272181

show more ...

Fix a bug in SCEV's poison value propagation

The worklist algorithm introduced in rL271151 didn't check to see if the
direct users of the post-inc add recurrence propagates poison. This
change fixe

Fix a bug in SCEV's poison value propagation

The worklist algorithm introduced in rL271151 didn't check to see if the
direct users of the post-inc add recurrence propagates poison. This
change fixes the problem and makes the code structure more obvious.

Note for release managers: correctness wise, this bug wasn't a
regression introduced by rL271151 -- the behavior of SCEV around
post-inc add recurrences was strictly improved (in terms of correctness)
in rL271151.

llvm-svn: 272179

show more ...

[SCEV] Consolidate comments; NFC

Consolidate documentation by removing comments from the .cpp file where
the comments in the .cpp file were copy-pasted from the header.

llvm-svn: 271157

[SCEV] Rename functions to LLVM style; NFC

llvm-svn: 271156