[polly] Introduce -polly-print-* passes to replace -analyze.

The `opt -analyze` option only works with the legacy pass manager and might be removed in the future, as explained in llvm.org/PR53733. T

[polly] Introduce -polly-print-* passes to replace -analyze.

The `opt -analyze` option only works with the legacy pass manager and might be removed in the future, as explained in llvm.org/PR53733. This patch introduced -polly-print-* passes that print what the pass would print with the `-analyze` option and replaces all uses of `-analyze` in the regression tests.

There are two exceptions: `CodeGen\single_loop_param_less_equal.ll` and `CodeGen\loop_with_condition_nested.ll` use `-analyze on the `-loops` pass which is not part of Polly.

Reviewed By: aeubanks

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

show more ...

Update isl to isl-0.18-1047-g4a20ef8

This update:

- Removes several deprecated functions (e.g., isl_band).
- Improves the pretty-printing of sets by detecting modulos and "false"
equalities

Update isl to isl-0.18-1047-g4a20ef8

This update:

- Removes several deprecated functions (e.g., isl_band).
- Improves the pretty-printing of sets by detecting modulos and "false"
equalities.
- Minor improvements to coalescing and increased robustness of the isl
scheduler.

This update does not yet include isl commit isl-0.18-90-gd00cb45
(isl_pw_*_alloc: add missing check for compatible spaces, Wed Sep 6 12:18:04
2017 +0200), as this additional check is too tight and unfortunately causes
two test case failures in Polly. A patch has been submitted to isl and will be
included in the next isl update for Polly.

llvm-svn: 325557

show more ...

Drop explicit -polly-delinearize parameter

Delinearization is now enabled by default and does not need to explicitly need
to be enabled in our tests.

llvm-svn: 264154

Track assumptions and restrictions separatly

In order to speed up compile time and to avoid random timeouts we now
separately track assumptions and restrictions. In this context
assumptions de

Track assumptions and restrictions separatly

In order to speed up compile time and to avoid random timeouts we now
separately track assumptions and restrictions. In this context
assumptions describe parameter valuations we need and restrictions
describe parameter valuations we do not allow. During AST generation
we create a runtime check for both, whereas the one for the
restrictions is negated before a conjunction is build.

Except the In-Bounds assumptions we currently only track restrictions.

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

llvm-svn: 262328

show more ...

Update to ISL 0.16.1

llvm-svn: 257898

Prepare unit tests for update to ISL 0.16

ISL 0.16 will change how sets are printed which breaks 117 unit tests
that text-compare printed sets. This patch re-formats most of these unit
tests using a

Prepare unit tests for update to ISL 0.16

ISL 0.16 will change how sets are printed which breaks 117 unit tests
that text-compare printed sets. This patch re-formats most of these unit
tests using a script and small manual editing on top of that. When
actually updating ISL, most work is done by just re-running the script
to adapt to the changed output.

Some tests that compare IR and tests with single CHECK-lines that can be
easily updated manually are not included here.

The re-format script will also be committed afterwards. The per-test
formatter invocation command lines options will not be added in the near
future because it is ad hoc and would overwrite the manual edits.
Ideally it also shouldn't be required anymore because ISL's set printing
has become more stable in 0.16.

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

llvm-svn: 257851

show more ...

tests: Drop -polly-detect-unprofitable and -polly-no-early-exit

These flags are now always passed to all tests and need to be disabled if
not needed. Disabling these flags, rather than passing them

tests: Drop -polly-detect-unprofitable and -polly-no-early-exit

These flags are now always passed to all tests and need to be disabled if
not needed. Disabling these flags, rather than passing them to almost all
tests, significantly simplfies our RUN: lines.

llvm-svn: 249422

show more ...

Traverse the SCoP to compute non-loop-carried domain conditions

In order to compute domain conditions for conditionals we will now
traverse the region in the ScopInfo once and build the domains

Traverse the SCoP to compute non-loop-carried domain conditions

In order to compute domain conditions for conditionals we will now
traverse the region in the ScopInfo once and build the domains for
each block in the region. The SCoP statements can then use these
constraints when they build their domain.

The reason behind this change is twofold:
1) This removes a big chunk of preprocessing logic from the
TempScopInfo, namely the Conditionals we used to build there.
Additionally to moving this logic it is also simplified. Instead
of walking the dominance tree up for each basic block in the
region (as we did before), we now traverse the region only
once in order to collect the domain conditions.
2) This is the first step towards the isl based domain creation.
The second step will traverse the region similar to this step,
however it will propagate back edge conditions. Once both are in
place this conditional handling will allow multiple exit loops
additional logic.

Reviewers: grosser

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

llvm-svn: 246398

show more ...

Make the dimension sizes of in ScopArrayInfo available as isl_pw_affs

This makes it easier to reason about the size of an array dimension with isl.

llvm-svn: 244757

Use all available range information for parameters

In the following even full-range information will help to avoid
runtime checks for wrapping integers, hence we enable it now.

llvm-svn: 235823

Remove target triples from test cases

I just learned that target triples prevent test cases to be run on other
architectures. Polly test cases are until now sufficiently target independent
to not re

Remove target triples from test cases

I just learned that target triples prevent test cases to be run on other
architectures. Polly test cases are until now sufficiently target independent
to not require any target triples. Hence, we drop them.

llvm-svn: 235384

show more ...

Rename 'scattering' to 'schedule'

In Polly we used both the term 'scattering' and the term 'schedule' to describe
the execution order of a statement without actually distinguishing between them.
We

Rename 'scattering' to 'schedule'

In Polly we used both the term 'scattering' and the term 'schedule' to describe
the execution order of a statement without actually distinguishing between them.
We now uniformly use the term 'schedule' for the execution order. This
corresponds to the terminology of isl.

History: CLooG introduced the term scattering as the generated code can be used
as a sequential execution order (schedule) or as a parallel dimension
enumerating different threads of execution (placement). In Polly and/or isl the
term placement was never used, but we uniformly refer to an execution order as a
schedule and only later introduce parallelism. When doing so we do not talk
about about specific placement dimensions.

llvm-svn: 235380

show more ...

Delinearization of expressions that contain array size parameters

This allows us to delinerize code such as:

A[][n]

for (i
for (j
A[i][n-j-1] = ...

which would previously have been

Delinearization of expressions that contain array size parameters

This allows us to delinerize code such as:

A[][n]

for (i
for (j
A[i][n-j-1] = ...

which would previously have been delinearize to an access A[i+1][-j-1].

To recover the correct access we apply the piecewise expression:

{ A[i][j] -> A[i-1][i+N]: i < 0; A[i][j] -> A[i][i]: i >= 0}

This approach generalizes to higher dimensions.

llvm-svn: 233566

show more ...

Update Polly tests to handle explicitly typed gep changes in LLVM

llvm-svn: 230784

ScopDetection: Only detect scops that have at least one read and one write

Scops that only read seem generally uninteresting and scops that only write are
most likely initializations where there is

ScopDetection: Only detect scops that have at least one read and one write

Scops that only read seem generally uninteresting and scops that only write are
most likely initializations where there is also little to optimize. To not
waste compile time we bail early.

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

llvm-svn: 229820

show more ...

[NFC] Drop the "scattering" tuple name

llvm-svn: 227801

Drop all constant scheduling dimensions

Schedule dimensions that have the same constant value accross all statements do
not carry any information, but due to the increased dimensionality of the
sche

Drop all constant scheduling dimensions

Schedule dimensions that have the same constant value accross all statements do
not carry any information, but due to the increased dimensionality of the
schedule cost compile time. To not pay this cost, we remove constant dimensions
if possible.

llvm-svn: 225067

show more ...

Derive run-time conditions for delinearization

As our delinearization works optimistically, we need in some cases run-time
checks that verify our optimistic assumptions. A simple example is the
foll

Derive run-time conditions for delinearization

As our delinearization works optimistically, we need in some cases run-time
checks that verify our optimistic assumptions. A simple example is the
following code:

void foo(long n, long m, long o, double A[n][m][o]) {

for (long i = 0; i < 100; i++)
for (long j = 0; j < 150; j++)
for (long k = 0; k < 200; k++)
A[i][j][k] = 1.0;
}

After clang linearized the access to A and we delinearized it again to
A[i][j][k] we need to ensure that we do not access the delinearized array
out of bounds (this information is not available in LLVM-IR). Hence, we
need to verify the following constraints at run-time:

CHECK: Assumed Context:
CHECK: [o, m] -> { : m >= 150 and o >= 200 }
llvm-svn: 212198

show more ...