Fix a bug in SCEV's backedge taken count computation from my prior fix in Jan.

This has to do with the trip count computation for loops with multiple
exits, which is quite subtle. Most passes just a

Fix a bug in SCEV's backedge taken count computation from my prior fix in Jan.

This has to do with the trip count computation for loops with multiple
exits, which is quite subtle. Most passes just ask for a single trip
count number, so we must be conservative assuming any exit could be
taken. Normally, we rely on the "exact" trip count, which was
correctly given as "unknown". However, SCEV also gives a "max"
back-edge taken count. The loops max BE taken count is conservatively
a maximum over the max of each exit's non-exiting iterations
count. Note that some exit tests can be skipped so the max loop
back-edge taken count can actually exceed the max non-exiting
iterations for some exits. However, when we know the loop *latch*
cannot be skipped, we can directly use its max taken count
disregarding other exits. I previously took the minimum here without
checking whether the other exit could be skipped. The correct, and
simpler thing to do here is just to directly use the loop latch's max
non-exiting iterations as the loops max back-edge count.

In the problematic test case, the first loop exit had a max of zero
non-exiting iterations, but could be skipped. The loop latch was known
not to be skipped but had max of one non-exiting iteration. We
incorrectly claimed the loop back-edge could be taken zero times, when
it is actually taken one time.

Fixes Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count.
Loop %for.body.i: max backedge-taken count is 1.

llvm-svn: 209358

show more ...

Rename ComputeMaskedBits to computeKnownBits. "Masked" has been
inappropriate since it lost its Mask parameter in r154011.

llvm-svn: 208811

use nullptr instead of NULL

llvm-svn: 208622

do not assert when delinearization fails

llvm-svn: 208615

use isZero()

llvm-svn: 208614

SCEV: Use range-based for loop and fold variable into assert.

llvm-svn: 208476

move findArrayDimensions to ScalarEvolution

we do not use the information from SCEVAddRecExpr to compute the shape of the array,
so a better place for this function is in ScalarEvolution.

llvm-svn:

move findArrayDimensions to ScalarEvolution

we do not use the information from SCEVAddRecExpr to compute the shape of the array,
so a better place for this function is in ScalarEvolution.

llvm-svn: 208456

show more ...

fix typo in debug message

llvm-svn: 208455

Correct formatting.

Sorry for the commit spam. My clang-format crashed on me and the vim
plugin did not print an error, but instead just left the formatting
untouched.

llvm-svn: 208358

Use std::remove_if to remove elements from a vector

Suggested-by: Benjamin Kramer <benny.kra@gmail.com>
llvm-svn: 208357

Revert "SCEV: Use I = vector<>.erase(I) to iterate and delete at the same time"

as committed in r208282. The original commit was incorrect.

llvm-svn: 208286

SCEV: Use I = vector<>.erase(I) to iterate and delete at the same time

llvm-svn: 208282

avoid segfaulting

*Quotient and *Remainder don't have to be initialized.

llvm-svn: 208238

do not collect undef terms

llvm-svn: 208237

split delinearization pass in 3 steps

To compute the dimensions of the array in a unique way, we split the
delinearization analysis in three steps:

- find parametric terms in all memory access func

split delinearization pass in 3 steps

To compute the dimensions of the array in a unique way, we split the
delinearization analysis in three steps:

- find parametric terms in all memory access functions
- compute the array dimensions from the set of terms
- compute the delinearized access functions for each dimension

The first step is executed on all the memory access functions such that we
gather all the patterns in which an array is accessed. The second step reduces
all this information in a unique description of the sizes of the array. The
third step is delinearizing each memory access function following the common
description of the shape of the array computed in step 2.

This rewrite of the delinearization pass also solves a problem we had with the
previous implementation: because the previous algorithm was by induction on the
structure of the SCEV, it would not correctly recognize the shape of the array
when the memory access was not following the nesting of the loops: for example,
see polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll

; void foo(long n, long m, long o, double A[n][m][o]) {
;
; for (long i = 0; i < n; i++)
; for (long j = 0; j < m; j++)
; for (long k = 0; k < o; k++)
; A[i][k][j] = 1.0;

Starting with this patch we no longer delinearize access functions that do not
contain parameters, for example in test/Analysis/DependenceAnalysis/GCD.ll

;; for (long int i = 0; i < 100; i++)
;; for (long int j = 0; j < 100; j++) {
;; A[2*i - 4*j] = i;
;; *B++ = A[6*i + 8*j];

these accesses will not be delinearized as the upper bound of the loops are
constants, and their access functions do not contain SCEVUnknown parameters.

llvm-svn: 208232

show more ...

[C++11] Add NArySCEV->Operands iterator range

llvm-svn: 208158

[Modules] Fix potential ODR violations by sinking the DEBUG_TYPE
definition below all the header #include lines, lib/Analysis/...
edition.

This one has a bit extra as there were *other* #define's be

[Modules] Fix potential ODR violations by sinking the DEBUG_TYPE
definition below all the header #include lines, lib/Analysis/...
edition.

This one has a bit extra as there were *other* #define's before #include
lines in addition to DEBUG_TYPE. I've sunk all of them as a block.

llvm-svn: 206843

show more ...

[C++11] More 'nullptr' conversion. In some cases just using a boolean check instead of comparing to nullptr.

llvm-svn: 206243

divide by the result of the gcd

used to fail with 'Step should divide Start with no remainder.'

llvm-svn: 205802

handle special cases when findGCD returns 1

used to fail with 'Step should divide Start with no remainder.'

llvm-svn: 205801

in findGCD of multiply expr return the gcd

we used to return 1 instead of the gcd

llvm-svn: 205800

ScalarEvolution: Compute exit counts for loops with a power-of-2 step.

If we have a loop of the form
for (unsigned n = 0; n != (k & -32); n += 32) {}
then we know that n is always divisible by 32 an

ScalarEvolution: Compute exit counts for loops with a power-of-2 step.

If we have a loop of the form
for (unsigned n = 0; n != (k & -32); n += 32) {}
then we know that n is always divisible by 32 and the loop must
terminate. Even if we have a condition where the loop counter will
overflow it'll always hold this invariant.

PR19183. Our loop vectorizer creates this pattern and it's also
occasionally formed by loop counters derived from pointers.

llvm-svn: 204728

show more ...

Remove some dead assignements found by scan-build

llvm-svn: 204013

[C++11] Add range based accessors for the Use-Def chain of a Value.

This requires a number of steps.
1) Move value_use_iterator into the Value class as an implementation
detail
2) Change it to ac

[C++11] Add range based accessors for the Use-Def chain of a Value.

This requires a number of steps.
1) Move value_use_iterator into the Value class as an implementation
detail
2) Change it to actually be a *Use* iterator rather than a *User*
iterator.
3) Add an adaptor which is a User iterator that always looks through the
Use to the User.
4) Wrap these in Value::use_iterator and Value::user_iterator typedefs.
5) Add the range adaptors as Value::uses() and Value::users().
6) Update *all* of the callers to correctly distinguish between whether
they wanted a use_iterator (and to explicitly dig out the User when
needed), or a user_iterator which makes the Use itself totally
opaque.

Because #6 requires churning essentially everything that walked the
Use-Def chains, I went ahead and added all of the range adaptors and
switched them to range-based loops where appropriate. Also because the
renaming requires at least churning every line of code, it didn't make
any sense to split these up into multiple commits -- all of which would
touch all of the same lies of code.

The result is still not quite optimal. The Value::use_iterator is a nice
regular iterator, but Value::user_iterator is an iterator over User*s
rather than over the User objects themselves. As a consequence, it fits
a bit awkwardly into the range-based world and it has the weird
extra-dereferencing 'operator->' that so many of our iterators have.
I think this could be fixed by providing something which transforms
a range of T&s into a range of T*s, but that *can* be separated into
another patch, and it isn't yet 100% clear whether this is the right
move.

However, this change gets us most of the benefit and cleans up
a substantial amount of code around Use and User. =]

llvm-svn: 203364

show more ...

Add missing parenthesis in SCEV comment

Contributed-by: Michael Zolutukin <mzolotukhin@apple.com>
llvm-svn: 202963