The changes affect methods that are part of the Pass interface and
  include:
    - Comments that describe the methods purpose.
    - A consistent use of the keywords override and virtual.
  Additionally, the printScop method is now optional and removed from
  SCoP passes that do not implement it.

llvm-svn: 248685

llvm-svn: 248684

After having generated a new user statement a couple of inefficient or
trivially dead instructions may remain. This commit runs instruction
simplification over the newly generated blocks to ensure unneeded
instructions are removed right away.

This commit does adds simplification for non-affine subregions which was not
yet part of 248681.

llvm-svn: 248683

Otherwise, part of the computation will be just simplified away when we add
instruction simplification support to the RegionGenerator.

llvm-svn: 248682

After having generated a new user statement a couple of inefficient or trivially
dead instructions may remain. This commit runs instruction simplification over
the newly generated blocks to ensure unneeded instructions are removed right
away.

This commit does not yet add simplification for non-affine subregions.

llvm-svn: 248681

llvm-svn: 248675

  This commit basically reverts r246427 but still solves the issue
  tackled by that commit. Instead of emitting initialization code in the
  beginning of the start block we now generate parallel code in its own
  block and thereby guarantee separation. This is necessary as we cannot
  generate code for hoisted loads prior to the start block but it still
  needs to be placed prior to everything else.

llvm-svn: 248674

llvm-svn: 248670

The new domain construction algorithm now correctly models this test case (and
derives an empty run-time condition). Add this test case to ensure we do not
regress.

llvm-svn: 248669

  The bug (15771) was fixed already with the new domain generation
  but the test case was not added till now.

llvm-svn: 248668

  When the whole SCoP is a non-affine region we need to use the
  surrounding loop in the construction of the schedule as that is
  the one that will be looked up after the schedule generation.

  This fixes bug 24947

llvm-svn: 248667

This was forgotten in r247928

llvm-svn: 248663

When recovering multi-dimensional memory accesses, it may happen that different
accesses to the same base array are recovered with different dimensionality.
This patch ensures that the dimensionalities are unified by adding zero valued
dimensions to acesses with lower dimensionality. When starting to model
fixed-size arrays as multi-dimensional in 247906, this has not been taken
care of.

llvm-svn: 248662

There are three possible reasons to add a memory memory access: For explicit load and stores, for llvm::Value defs/uses, and to emulate PHI nodes (the latter two called implicit accesses). Previously MemoryAccess only stored IsPHI. Register accesses could be identified through the isScalar() method if it was no IsPHI. isScalar() determined the number of dimensions of the underlaying array, scalars represented by zero dimensions.

For the work on de-LICM, implicit accesses can have more than zero dimensions, making the distinction of isScalars() useless, hence now stored explicitly in the MemoryAccess. Instead, we replace it by isImplicit() and avoid the term scalar for zero-dimensional arrays as it might be confused with llvm::Value which are also often referred to as scalars (or alternatively, as registers).

No behavioral change intended, under the condition that it was impossible to create explicit accesses to zero-dimensional "arrays".

llvm-svn: 248616

This makes the intent of each created object clearer and allows to add more specific asserts. The bug fixed in r248535 has been discovered this way.

No functional change intended; everything should behave as before.

llvm-svn: 248603

This avoids warnings of the form:
  stdint.h:1:20: warning: no newline at end of file [-Wnewline-eof]

llvm-svn: 248570

llvm-svn: 248568

llvm-svn: 248563

This change addresses three issues:

  - Read only scalars that enter a PHI node through an edge that comes from
    outside the scop are not modeled any more, as such PHI nodes will always
    be initialized to this initial value right before the SCoP is entered.
  - For PHI nodes that depend on a scalar value that is defined outside the
    scop, but where the scalar values is passed through an edge that itself
    comes from a BB that is part of the region, we introduce in this basic
    block a read of the out-of-scop value to ensure it's value is available
    to write it into the PHI alloc location.
  - Read only uses of scalars by PHI nodes are ignored in the general read only
    handling code, as they are taken care of by the general PHI node modeling
    code.

llvm-svn: 248535

llvm-svn: 248520

llvm-svn: 248492

Library names in the LLVM framework usually do not contain underscores.

llvm-svn: 248487

After the merge of TempScopInfo into ScopInfo the analysis output 
remained because of the existing unit tests. These remains are removed 
and the units tests converted to match the equivalent output of 
ScopInfo's analysis output. The unit tests are also moved into the
directory of ScopInfo tests.

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

llvm-svn: 248485

Refactor all ISL-related cmake build instructions into its own 
CMakeLists.txt and build as a separate library.

This is useful to apply ISL-related build flags to ISL only and not to 
Polly's files. Also, it the separation of both projects becomes clearer.

Proposed name of the library is Polly_isl. It is not "isl" to avoid 
mix-up with potentially installed libisl.{a|so}.

Tested configurations:
- Windows with cmake 3.2
- Ubuntu with cmake 3.0.2 
- Ubuntu with cmake 3.0.2  BUILD_SHARED_LIBS on
- Ubuntu with cmake 2.8.12.2 (LLVM minimum version)
- Ubuntu out-of-LLVM-tree

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

llvm-svn: 248484

llvm-svn: 248192

A missing return statement that previously did not have a visibly negative
effect caused after some data-structure changes in r248024 multi-dimensional
accesses to be modeled both multi-dimensional as well as linearized. This
commit adds the missing return to avoid the incorrect double modeling as
well as the compile time increases it caused.

llvm-svn: 248171

  If we encounter a <nsw> tagged AddRec for a loop we know the trip count of
  that loop has to be bounded or the semantics is undefined anyway. Hence, we
  only need to add unbounded assumptions if no such AddRec is known.

llvm-svn: 248128

  So far we ignored the unbounded parts of the iteration domain, however
  we need to assume they do not occure at all to remain sound if they do.

llvm-svn: 248126

  We now add loop carried information during the second traversal of the
  region instead of in a intermediate step in-between. This makes the
  generation simpler, removes code and should even be faster.

llvm-svn: 248125

llvm-svn: 248124

  In order to allow multiple back edges we:
    - compute the conditions under which each back edge is taken
    - build the union over all these conditions, thus the condition that
      any back edge is taken
    - apply the same logic to the union we applied to a single back edge

llvm-svn: 248120

  As we currently do not perform any optimizations that targets (or is
  even aware) small trip counts we will skip them when we count the
  loops in a region.

llvm-svn: 248119

llvm-svn: 248118

llvm-svn: 248026

All MemoryAccess objects will be owned by ScopInfo::AccFuncMap which 
previously stored the IRAccess objects. Instead of creating new 
MemoryAccess objects, the already created ones are reused, but their 
order might be different now. Some fields of IRAccess and MemoryAccess 
had the same meaning and are merged.

This is the last step of fusioning TempScopInfo.{h|cpp} and 
ScopInfo.{h.cpp}. Some refactoring might still make sense.

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

llvm-svn: 248024

This currently does not change the behavior in Polly, but it allows us to later
also overwrite the EscapeMap with our GlobalMap.

llvm-svn: 247970

In some cases instcombine introduces bitcasts that slightly obfuscate the
multi-dimensionality of an array. This patch teaches our fixed-size
delinearization how to look through bitcasts.

llvm-svn: 247928

This information is implicitly available through the multi-dimensionality of
memory accesses. This reduces compile time for 3mm from 430ms to 400ms and
should generally benefit compile time for cases where the assumed context
is complex.

llvm-svn: 247907

If the GEP instructions give us enough insights, model scalar accesses as
multi-dimensional (and generate the relevant run-time checks to ensure
correctness). This will allow us to simplify the dependence computation in
a subsequent commit.

llvm-svn: 247906

We currently use this functionality to add run-time assumptions that check its
in-bound property.

llvm-svn: 247893