[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 ...

[GSoC 2016]New function pass ScopInfoWrapperPass

This patch adds a new function pass ScopInfoWrapperPass so that the
polyhedral description of a region, the SCoP, can be constructed and
used in a fu

[GSoC 2016]New function pass ScopInfoWrapperPass

This patch adds a new function pass ScopInfoWrapperPass so that the
polyhedral description of a region, the SCoP, can be constructed and
used in a function pass.

Patch by Utpal Bora <[email protected]>

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

llvm-svn: 273856

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

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 ...

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 ...

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 ...

Remove -polly-codegen-scev option and related code

SCEV based code generation has been the default for two weeks after having
been tested for a long time. We now drop the support the non-scev-based

Remove -polly-codegen-scev option and related code

SCEV based code generation has been the default for two weeks after having
been tested for a long time. We now drop the support the non-scev-based code
generation.

llvm-svn: 222978

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 ...

Adjust multidim test cases to not access out-of-bound memory

We do this currently only for test cases where we have integer offsets that
clearly access array dimensions out-of-bound.

-; for (long

Adjust multidim test cases to not access out-of-bound memory

We do this currently only for test cases where we have integer offsets that
clearly access array dimensions out-of-bound.

-; for (long i = 0; i < n; i++)
-; for (long j = 0; j < m; j++)
-; for (long k = 0; k < o; k++)
+; for (long i = 0; i < n - 3; i++)
+; for (long j = 4; j < m; j++)
+; for (long k = 0; k < o - 7; k++)
; A[i+3][j-4][k+7] = 1.0;

This will be helpful if we later want to simplify the access functions under the
assumption that they do not access memory out of bounds.

llvm-svn: 210179

show more ...

delinearize memory access functions

llvm-svn: 205799

ScopInfo: Split start value from SCEVAddRecExpr to enable parameter sharing.

SCoP invariant parameters with the different start value would deter parameter
sharing. For example, when compiling the f

ScopInfo: Split start value from SCEVAddRecExpr to enable parameter sharing.

SCoP invariant parameters with the different start value would deter parameter
sharing. For example, when compiling the following C code:

void foo(float *input) {
for (long j = 0; j < 8; j++) {
// SCoP begin
for (long i = 0; i < 8; i++) {
float x = input[j * 64 + i + 1];
input[j * 64 + i] = x * x;
}
}
}

Polly would creat two parameters for these memory accesses:

p_0: {0,+,256}
p_2: {4,+,256}
[j * 64 + i + 1] => MemRef_input[o0] : 4o0 = p_1 + 4i0
[j * 64 + i] => MemRef_input[o0] : 4o0 = p_0 + 4i0

These parameters only differ from start value. To enable parameter sharing,
we split the start value from SCEVAddRecExpr, so they would share a single
parameter that always has zero start value:

p0: {0,+,256}<%for.cond1.preheader>
[j * 64 + i + 1] => MemRef_input[o0] : 4o0 = 4 + p_1 + 4i0
[j * 64 + i] => MemRef_input[o0] : 4o0 = p_0 + 4i0

Such translation can make the polly-dependence much faster.

Contributed-by: Star Tan <[email protected]>
llvm-svn: 187728

show more ...