Use nullptr instead of '0' for pointers

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@221982 91177308-0d34-0410-b5e6-96231b3b80d8
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

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222088 91177308-0d34-0410-b5e6-96231b3b80d8
Remove one incomplete test case accidentally committed

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222089 91177308-0d34-0410-b5e6-96231b3b80d8
Introduce minimalistic cost model for auto parallelization

Instead of parallelizing every parallel outermost loop, we now use a very
minimalistic cost model. Specifically, we assume innermost loops are not
worth parallelising and all non-innermost loops are.

When parallelizing all loops in LNT we got several slowdowns/timeouts due to
us parallelizing innermost loops that are executed only a couple of times
(number of iterations not known statically). With this basic heuristic enabled
LNT does not show any more timeouts, while several interesting loops are still
parallelized.

There are many ways to obtain an improved heuristic. Constructing such an
improvide heuristic from a position of minimal slow-down and zero code size
increase seems to be the best, as it allows us to track progress on LNT.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222096 91177308-0d34-0410-b5e6-96231b3b80d8
Switch default code generation backend to isl

The isl based backend has been tested since a long time and with the recently
commited OpenMP support the last missing piece of functionality was ported from
the CLooG backend.

The isl based backend gives us interesting new functionality:

  - Run-time alias checks (enabled by default)

  Optimize scops that contain possibly aliasing pointers. This feature has
  largely increased the number of loop nests we consider for optimization.

  Thanks Johannes!

  - Delinearization (not yet enabled by default)

  Model accesses to multi-dimensional arrays precisely. This will allow us to
  understand kernels with multi-dimensional VLAs written in Julia, boost::ublas,
  coremark or C99.

  Thanks Sebastian!

  - Generation of higher quality code

  Sven and me spent a long time to optimize the quality of the generated code. A
  major focus were expressions as they result from modulos/divisions or
  piecewise affine expressions (a ? b : c).

  - Full/Partial tile separation, polyhedral unrolling

  The isl code generation provides functionality to generate specialized code
  for core and cleanup loops and to specialize code using polyhedral context
  information while unrolling statements.

  (not yet exploited in Polly)

  - Modifieable access functions

  We can now use standard isl functionality to remap memory accesses to new
  data locations. A standard use case is the use of shared memory, where
  accesses to a larger region in global memory need to be mapped to a smaller
  shared memory region using a modulo mapping.

  (not yet exploited in Polly)

The cloog based code generation is still available for comparision, but is
scheduled for removal.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222101 91177308-0d34-0410-b5e6-96231b3b80d8
Remove an unnecessary ifdef

Reported-by: Johannes Doerfert <doerfert@cs.uni-saarland.de>

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222102 91177308-0d34-0410-b5e6-96231b3b80d8
Independent blocks: SE->forget() scalars translated to arrays

This prevents SCEVs to reference values not valid any more and as a consequence
solves a bug where such values reintroduced during ast generation caused the
independent blocks pass to fail validation.

http://llvm.org/PR21204

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222103 91177308-0d34-0410-b5e6-96231b3b80d8
Fix formatting

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222106 91177308-0d34-0410-b5e6-96231b3b80d8
Make usage of scev based code generation explicit in tests

This is in preparation of using SCEV based codegen by default in polly

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222111 91177308-0d34-0410-b5e6-96231b3b80d8
Modify test cases to work with SCEV based code generation

This patch includes tests where we actually need to adjust the CHECK lines
for SCEV based code generation. Besides these adjustments we add explicit
calls to -polly-codegen-scev=[true|false] and make sure we test both cases.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222112 91177308-0d34-0410-b5e6-96231b3b80d8
Enable SCEV based code generation by default

SCEV based code generation allows Polly to detect and generate code for loops
that do not have an explicit induction variable, but only virtual induction
variables given by SCEV.

Being able to do so has two main benefits:

  - We can detect more scops by default
  - We require less canonicalization before Polly, which means we get closer
    to our goal of not touching the IR before analyzing its properties.
    Specifically, we do not need to run -polly-indvars to introduce explicit
    canonical induction variables.

This switch became possible as both the isl code generation and -polly-parallel
are LNT error free with SCEV based code generation and the isl ast generator.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222113 91177308-0d34-0410-b5e6-96231b3b80d8
Use new Small(Ptr)Set API

This fixes the recent build failures.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222358 91177308-0d34-0410-b5e6-96231b3b80d8
Simplify the SCEVAffinator [NFC]


git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222360 91177308-0d34-0410-b5e6-96231b3b80d8
Change states in the www/todo.html list


git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222362 91177308-0d34-0410-b5e6-96231b3b80d8
todo: We now have OpenMP support in isl backend

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222365 91177308-0d34-0410-b5e6-96231b3b80d8
todo: We can support modifiable memory access functions

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222366 91177308-0d34-0410-b5e6-96231b3b80d8
Fix typo

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222559 91177308-0d34-0410-b5e6-96231b3b80d8
Use isl_schedule_get_ctx

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222560 91177308-0d34-0410-b5e6-96231b3b80d8
Assume GetElementPtr offsets to be inbounds

In case a GEP instruction references into a fixed size array e.g., an access
A[i][j] into an array A[100x100], LLVM-IR does not guarantee that the subscripts
always compute values that are within array bounds. We now derive the set of
parameter values for which all accesses are within bounds and add the assumption
that the scop is only every executed with this set of parameter values.

Example:

void foo(float A[][20], long n, long m {
    for (long i = 0; i < n; i++)
      for (long j = 0; j < m; j++)
        A[i][j] = ...

This loop yields out-of-bound accesses if m is at least 20 and at the same time
at least one iteration of the outer loop is executed. Hence, we assume:

  n <= 0 or m <= 20.

Doing so simplifies the dependence analysis problem, allows us to perform
more optimizations and generate better code.

TODO: The location where the GEP instruction is executed is not necessarily the
location where the memory is actually accessed. As a result scanning for GEP[s]
is imprecise. Even though this is not a correctness problem, this imprecision
may result in missed optimizations or non-optimal run-time checks.

In polybench where this mismatch between parametric loop bounds and fixed size
arrays is common, we see with this patch significant reductions in compile time
(up to 50%) and execution time (up to 70%). We see two significant compile time
regressions (fdtd-2d, jacobi-2d-imper), and one execution time regression
(trmm).  Both regressions arise due to additional optimizations that have been
enabled by this patch. They can be addressed in subsequent commits.

http://reviews.llvm.org/D6369

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222754 91177308-0d34-0410-b5e6-96231b3b80d8
Add PreHeader always to OuterLoop

This fixes a bug introduce in r217525.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@222766 91177308-0d34-0410-b5e6-96231b3b80d8