Clean up XFAILed test cases

We had a set of test cases that have been incomplete and XFAILED. This patch
completes a couple of the interesting ones and removes the ones which seem
redundant or not sufficiently reduced to be useful.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211670 91177308-0d34-0410-b5e6-96231b3b80d8
test/ScopInfo: Remove %defaultOpts and list passes explicitly

Due to bad habit we sometimes used a variable %defaultOpts that listed
a set of passes commonly run to prepare for Polly. None of these test cases
actually needs special preparation and only two of them need the 'basicaa' to
be scheduled. Scheduling the required alias analysis explicitly makes the test
cases clearer.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211671 91177308-0d34-0410-b5e6-96231b3b80d8
Support the new DiagnosticRemarks

Add support for generating optimization remarks after completing the
detection of Scops.
The goal is to provide end-users with useful hints about opportunities that
help to increase the size of the detected Scops in their code.

By default the remark is unspecified and the debug location is empty. Future
patches have to expand on the messages generated.

This patch brings a simple test case for ReportFuncCall to demonstrate the
feature.

Reports all missed opportunities to increase the size/number of valid
Scops:
 clang <...> -Rpass-missed="polly-detect" <...>
 opt <...> -pass-remarks-missed="polly-detect" <...>

Reports beginning and end of all valid Scops:
 clang <...> -Rpass="polly-detect" <...>
 opt <...> -pass-remarks="polly-detect" <...>

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

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211769 91177308-0d34-0410-b5e6-96231b3b80d8
Support for LLVM-style RTTI isa<...>, dyn_cast<...> et al.

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

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211773 91177308-0d34-0410-b5e6-96231b3b80d8
Add diagnostic remark for ReportVariantBasePtr

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211777 91177308-0d34-0410-b5e6-96231b3b80d8
Use own class for storing the RejectLogs

Use a container class to store the reject logs. Delegating most calls to
the internal std::map and add a few convenient shortcuts (e.g.,
hasErrors()).

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

  This dependency analysis will keep track of memory accesses if they might be
  part of a reduction. If not, the dependences are tracked on a statement level.
  The main reason to do this is to reduce the compile time while beeing able to
  distinguish the effects of reduction and non-reduction accesses.

  + Adjusted two test cases


git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211794 91177308-0d34-0410-b5e6-96231b3b80d8
Use wrapped reduction dependences

  This change will ease the transision to multiple reductions per statement as
  we can now distinguish the effects of multiple reductions in the same
  statement.

  + Wrapped reduction dependences are used to compute privatization dependences
  + Modified test cases to account for the change



git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211795 91177308-0d34-0410-b5e6-96231b3b80d8
[Refactor] Change memory access dump to preserve space


git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211796 91177308-0d34-0410-b5e6-96231b3b80d8
[Fix] Broken tests after r211796.


git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211797 91177308-0d34-0410-b5e6-96231b3b80d8
[Refactor] Make the used dependence types explicit


git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211803 91177308-0d34-0410-b5e6-96231b3b80d8
Don't expand to invalid Scops with -polly-detect-keep-going

Enabling -keep-going in ScopDetection causes expansion to an invalid
Scop candidate.

Region A     <- Valid candidate
   |
Region B     <- Invalid candidate

If -keep-going is enabled, ScopDetection would expand A to A+B because
the RejectLog is never checked for errors during expansion.

With this patch only A becomes a valid Scop.

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211875 91177308-0d34-0410-b5e6-96231b3b80d8
Allow multiple reductions per statement

  Iterate over all store memory accesses and check for valid binary reduction
  candidate loads by following the operands of the stored value.  For each
  candidate pair we check if they have the same base address and there are no
  other accesses which may overlap with them. This ensures that no intermediate
  value can escape into other memory locations or is overwritten at some point.

  + 17 test cases for reduction detection and reduction dependency modeling



git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211957 91177308-0d34-0410-b5e6-96231b3b80d8
[Fix] Deleted renamed test after r211957

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211964 91177308-0d34-0410-b5e6-96231b3b80d8
Remove redundant code and use C++ range fors

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211980 91177308-0d34-0410-b5e6-96231b3b80d8
[C++11] Use more range based fors

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@211981 91177308-0d34-0410-b5e6-96231b3b80d8
[FIX] Don't consider reductions which are partially outside the SCoP

  + Test case


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

  This change is particularly useful in the code generation as we need
  to know which binary operator/identity element we need to combine/initialize
  the privatization locations.

  + Print the reduction type for each memory access
  + Adjusted the test cases to comply with the new output format and
    to test for the right reduction type



git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@212126 91177308-0d34-0410-b5e6-96231b3b80d8
Use arguments of user statements to perform induction variable substitution

To translate the old induction variables as they exist before Polly to new
new induction variables introduced during AST code generation we need to
generate code that computes the new values from the old ones. We can do this
by just looking at the arguments isl generates in each scheduled statement.

Example:

  // Old
  for i
    S(i)

  // New
  for c0
    for c1
      S(c0 + c1)

To get the value of i, we need to compute 'c0 + c1'. This expression is readily
available in the user statements generated by isl and just needs to be
translated to LLVM-IR.

This replaces an old confusing construct that constructed during ast generation
an isl multi affine expression that described this relation and which was then
again ast generated for each statement and argument when translating the isl ast
to LLVM-IR. This approach was difficult to understand and the additional ast
generation calls where entirely redundant as isl provides the relevant
expressions as arguments of the generated user statements.

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