[SCEVValidator] Fix loop exit values considered affine.

Index calculations can use the last value that come out of a loop.
Ideally, ScalarEvolution can compute that exit value directly without
depen

[SCEVValidator] Fix loop exit values considered affine.

Index calculations can use the last value that come out of a loop.
Ideally, ScalarEvolution can compute that exit value directly without
depending on the loop induction variable, but not in all cases.

This changes isAffine to not consider such loop exit values as affine to
avoid that SCEVExpander adds uses of the original loop induction
variable.

This fix is analogous to r262404 that applies to general uses of loop
exit values instead of index expressions and loop bouds as in this
patch.

This reduces the number of LNT test-suite fails with
-polly-position=before-vectorizer -polly-unprofitable
from 10 to 8.

llvm-svn: 262665

show more ...

Pass scope and LoopInfo to SCEVValidator. NFC.

The scope will be required in the following fix. This commit separates
the large changes that do not change behaviour from the small, but
functional ch

Pass scope and LoopInfo to SCEVValidator. NFC.

The scope will be required in the following fix. This commit separates
the large changes that do not change behaviour from the small, but
functional change.

llvm-svn: 262664

show more ...

Fix non-synthesizable loop exit values.

Polly recognizes affine loops that ScalarEvolution does not, in
particular those with loop conditions that depend on hoisted invariant
loads. Check for SCEVAd

Fix non-synthesizable loop exit values.

Polly recognizes affine loops that ScalarEvolution does not, in
particular those with loop conditions that depend on hoisted invariant
loads. Check for SCEVAddRec dependencies on such loops and do not
consider their exit values as synthesizable because SCEVExpander would
generate them as expressions that depend on the original induction
variables. These are not available in generated code.

llvm-svn: 262404

show more ...

[SCEVValidator] Remove redundant visit.

SCEVAddRecExpr::getStart() is synonymous to SCEVAddRecExpr::getOperand(0)
which will be visited in the following loop anyway.

llvm-svn: 262375

Separate more constant factors of parameters

So far we separated constant factors from multiplications, however,
only when they are at the outermost level of a parameter SCEV. Now,
we also sep

Separate more constant factors of parameters

So far we separated constant factors from multiplications, however,
only when they are at the outermost level of a parameter SCEV. Now,
we also separate constant factors from the parameter SCEV if the
outermost expression is a SCEVAddRecExpr. With the changes to the
SCEVAffinator we can now improve the extractConstantFactor(...)
function at will without worrying about any other code part. Thus,
if needed we can implement a more comprehensive
extractConstantFactor(...) function that will traverse the SCEV
instead of looking only at the outermost level.

Four test cases were affected. One did not change much and the other
three were simplified.

llvm-svn: 260859

show more ...

Use parameter constraints provided via llvm.assume

If an llvm.assume dominates the SCoP entry block and the assumed condition
can be expressed as an affine inequality we will now add it to the c

Use parameter constraints provided via llvm.assume

If an llvm.assume dominates the SCoP entry block and the assumed condition
can be expressed as an affine inequality we will now add it to the context.

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

llvm-svn: 252851

show more ...

Allow invariant loads in the SCoP description

This patch allows invariant loads to be used in the SCoP description,
e.g., as loop bounds, conditions or in memory access functions.

First we co

Allow invariant loads in the SCoP description

This patch allows invariant loads to be used in the SCoP description,
e.g., as loop bounds, conditions or in memory access functions.

First we collect "required invariant loads" during SCoP detection that
would otherwise make an expression we care about non-affine. To this
end a new level of abstraction was introduced before
SCEVValidator::isAffineExpr() namely ScopDetection::isAffine() and
ScopDetection::onlyValidRequiredInvariantLoads(). Here we can decide
if we want a load inside the region to be optimistically assumed
invariant or not. If we do, it will be marked as required and in the
SCoP generation we bail if it is actually not invariant. If we don't
it will be a non-affine expression as before. At the moment we
optimistically assume all "hoistable" (namely non-loop-carried) loads
to be invariant. This causes us to expand some SCoPs and dismiss them
later but it also allows us to detect a lot we would dismiss directly
if we would ask e.g., AliasAnalysis::canBasicBlockModify(). We also
allow potential aliases between optimistically assumed invariant loads
and other pointers as our runtime alias checks are sound in case the
loads are actually invariant. Together with the invariant checks this
combination allows to handle a lot more than LICM can.

The code generation of the invariant loads had to be extended as we
can now have dependences between parameters and invariant (hoisted)
loads as well as the other way around, e.g.,
test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll
First, it is important to note that we cannot have real cycles but
only dependences from a hoisted load to a parameter and from another
parameter to that hoisted load (and so on). To handle such cases we
materialize llvm::Values for parameters that are referred by a hoisted
load on demand and then materialize the remaining parameters. Second,
there are new kinds of dependences between hoisted loads caused by the
constraints on their execution. If a hoisted load is conditionally
executed it might depend on the value of another hoisted load. To deal
with such situations we sort them already in the ScopInfo such that
they can be generated in the order they are listed in the
Scop::InvariantAccesses list (see compareInvariantAccesses). The
dependences between hoisted loads caused by indirect accesses are
handled the same way as before.

llvm-svn: 249607

show more ...

Revert r247278 "Disable support for modulo expressions"

This reverts commit 00c5b6ca8832439193036aadaaaee92a43236219.

We can handle modulo expressions in the domain again.

llvm-svn: 247542

Disable support for modulo expressions

The support for modulo expressions is not comlete and makes the new
domain generation harder. As the currently broken domain generation
needs to be repla

Disable support for modulo expressions

The support for modulo expressions is not comlete and makes the new
domain generation harder. As the currently broken domain generation
needs to be replaced, we will first swap in the new, fixed domain
generation and make it compatible with the modulo expressions later.

llvm-svn: 247278

show more ...

Disable support for pointer expressions

The support for pointer expressions is broken as it can only handle
some patterns in the IslExprBuilder. We should to treat pointers in
expressions the

Disable support for pointer expressions

The support for pointer expressions is broken as it can only handle
some patterns in the IslExprBuilder. We should to treat pointers in
expressions the same as integers at some point and revert this patch.

llvm-svn: 247147

show more ...

Add support for srem instruction

Remainder operations with constant divisor can be modeled as quasi-affine
expression. This patch adds support for detecting and modeling them. We also
add a test tha

Add support for srem instruction

Remainder operations with constant divisor can be modeled as quasi-affine
expression. This patch adds support for detecting and modeling them. We also
add a test that ensures they are correctly code generated.

This patch was extracted from a larger patch contributed by Johannes Doerfert
in http://reviews.llvm.org/D5293

llvm-svn: 240518

show more ...

Sort include directives

Upcoming revisions of isl require us to include header files explicitly, which
have previously been already transitively included. Before we add them, we sort
the existing in

Sort include directives

Upcoming revisions of isl require us to include header files explicitly, which
have previously been already transitively included. Before we add them, we sort
the existing includes.

Thanks to Chandler for sort_includes.py. A simple, but very convenient script.

llvm-svn: 236930

show more ...

[FIX] Invalid recognition of multidimensional access

In the lnt benchmark MultiSource/Benchmarks/MallocBench/gs/gs with
scalar and PHI modeling we detected the multidimensional accesses
with s

[FIX] Invalid recognition of multidimensional access

In the lnt benchmark MultiSource/Benchmarks/MallocBench/gs/gs with
scalar and PHI modeling we detected the multidimensional accesses
with sizes variant in the SCoP. This will check the sizes for validity.

llvm-svn: 236395

show more ...

Use the original no-wrap flags for normalized AddRecs

llvm-svn: 235822

Do not assume all multi-parameter products are affine

As soon as one operand of the product is invalid, the entire product is invalid.
This happens for example if one of the operands is not loop-inv

Do not assume all multi-parameter products are affine

As soon as one operand of the product is invalid, the entire product is invalid.
This happens for example if one of the operands is not loop-invariant.

This fixes http://llvm.org/PR23125

Reported-by: Jeremy Huddleston Sequoia <jeremyhu@apple.com
llvm-svn: 234119

show more ...

Strip constant factors from SCoP parameters

This will strip the constant factor of a parameter befor we add it to
the SCoP. As a result the access functions are simplified, e.g., for
the attac

Strip constant factors from SCoP parameters

This will strip the constant factor of a parameter befor we add it to
the SCoP. As a result the access functions are simplified, e.g., for
the attached test case.

llvm-svn: 233501

show more ...

Change argument "class" keyword to "const"

llvm-svn: 230666

Allow signed devision in access functions

llvm-svn: 228833

[FIX] Activated a pointer test and removed obsolete comment

llvm-svn: 227524

Add support for pointer types in expressions

llvm-svn: 225464

Add OpenMP code generation to isl backend

This backend supports besides the classical code generation the upcoming SCEV
based code generation (which the existing CLooG backend does not support
robus

Add OpenMP code generation to isl backend

This backend supports besides the classical code generation the upcoming SCEV
based code generation (which the existing CLooG backend does not support
robustly).

OpenMP code generation in the isl backend benefits from our run-time alias
checks such that the set of loops that can possibly be parallelized is a lot
larger.

The code was tested on LNT. We do not regress on builds without -polly-parallel.
When using -polly-parallel most tests work flawlessly, but a few issues still
remain and will be addressed in follow up commits.

SCEV/non-SCEV codegen:
- Compile time failure in ldecod and TimberWolfMC due a problem in our
run-time alias check generation triggered by pointers that escape through
the OpenMP subfunction (OpenMP specific).

- Several execution time failures. Due to the larger set of loops that we now
parallelize (compared to the classical code generation), we currently run
into some timeouts in tests with a lot loops that have a low trip count and
are slowed down by parallelizing them.

SCEV only:

- One existing failure in lencod due to llvm.org/PR21204 (not OpenMP specific)

OpenMP code generation is the last feature that was only available in the CLooG
backend. With the isl backend being the only one supporting features such as
run-time alias checks and delinearization, we will soon switch to use the isl
ast generator by the default and subsequently remove our dependency on CLooG.

http://reviews.llvm.org/D5517

llvm-svn: 222088

show more ...

Use braces in multi-statement DEBUG() code [NFC]

By adding braces into the DEBUG statement we can make clang-format format code
such as:

DEBUG(stmt1(); stmt2())

as multi-line code:

DEBUG({

Use braces in multi-statement DEBUG() code [NFC]

By adding braces into the DEBUG statement we can make clang-format format code
such as:

DEBUG(stmt1(); stmt2())

as multi-line code:

DEBUG({
stmt1();
stmt2();
});

This makes control-flow in debug statements easier to read.

llvm-svn: 220441

show more ...

Revert "Added support for modulo expressions"

This reverts commit 215684. The intention of the commit is great, but
unfortunately it seems to be the cause of 14 LNT test suite failures:

http://lab.

Revert "Added support for modulo expressions"

This reverts commit 215684. The intention of the commit is great, but
unfortunately it seems to be the cause of 14 LNT test suite failures:

http://lab.llvm.org:8011/builders/perf-x86_64-penryn-O3-polly/builds/116

To make our buildbots and performance testers green until this issue is solved,
we temporarily revert this commit.

llvm-svn: 215816

show more ...

Added support for modulo expressions

The support is limited to signed modulo access and condition
expressions with a constant right hand side, e.g., A[i % 2] or
A[i % 9]. Test cases are modifi

Added support for modulo expressions

The support is limited to signed modulo access and condition
expressions with a constant right hand side, e.g., A[i % 2] or
A[i % 9]. Test cases are modified according to this new feature and
new test cases are added.

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

llvm-svn: 215684

show more ...

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

If you want to know more details about this, you can see the recent

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

If you want to know more details about this, you can see the recent
commits to Debug.h in LLVM. This is just the Polly segment of a cleanup
I'm doing globally for this macro.

llvm-svn: 206852

show more ...