LoopGenerators: Construct loops such that they are already loop rotated

                BeforeBB
                   |
                   v
                GuardBB
                /      \
       __  PreHeaderBB  \
      /  \    /         |
   latch  HeaderBB      |
      \  /    \         /
       <       \       /
                \     /
                ExitBB

This does not only remove the need for an explicit loop rotate pass, but it also
gives us the possibility to skip the construction of the guard condition in case
the loop is known to be executed at least once. We do not yet exploit this, but
by implementing this analysis in the isl code generator we should be able to
remove more guards than the generic loop rotate pass can.  Another point is that
loop rotation can introduce additional PHI nodes, which may hide that a loop can
be executed in parallel. This change avoids this complication and will make it
easier to move the openmp code generation into a separate pass.

Merged from https://llvm.org/svn/llvm-project/polly/trunk@181986

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183373 91177308-0d34-0410-b5e6-96231b3b80d8
Update LoopInfo correctly

When the Polly code generation was written we did not correctly update the
LoopInfo data, but still claimed that the loop information is correct. This
does not only lead to missed optimizations, but it can also cause
miscompilations in case passes such as LoopSimplify are run after Polly.

Reported-by: Sergei Larin <slarin@codeaurora.org>

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@181987

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183374 91177308-0d34-0410-b5e6-96231b3b80d8
rename make check target to match the naming convention followed in the other llvm projects

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182171

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183375 91177308-0d34-0410-b5e6-96231b3b80d8
Update matmul example to the latest polly version

As the namings of the scops have changed, polly was not able to read in the user
given .jscop files. By renaming the provided files, polly now finds them again
and can use them to optimize the matmul function. We also update the generated
files to reflect the very latest version of Polly.

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182265

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183376 91177308-0d34-0410-b5e6-96231b3b80d8
independent blocks: when moving Values, invalidate SCEV cached info

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182310

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183377 91177308-0d34-0410-b5e6-96231b3b80d8
Remove .htaccess file

It was initially committed to allow people to get a list of the files used
or generated in the matmul tutorial. Since the documentation does now
point people to the directory in their git checkout, it is not necessary anymore
to make a directory listing available. Especially, as this never worked and
recently the LLVM web server does not deliver files in this directory at all
due to the unsupported .htaccess file.

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182370

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183378 91177308-0d34-0410-b5e6-96231b3b80d8
fix insertion of values in BBMap

In GDB when "step" through generateScalarLoad and "finish" the call, the
returned value is non NULL, however when printing the value contained in
BBMap[Load] after this stmt:

  BBMap[Load] = generateScalarLoad(...);

the value in BBMap[Load] is NULL, and the BBMap.count(Load) is 1.

The only intuitive idea that I have to explain this behavior is that we are
playing with the undefined behavior of eval order of the params for the function
standing for "BBMap[Load] = generateScalarLoad()". "BBMap[Load] = " may be
executed before generateScalarLoad is called.

Here are some other possible explanations from Will Dietz <w@wdtz.org>:

The error is likely due to BBMap[Load] being evaluated first (creating
a {Load -> uninitialized } entry in the DenseMap), then
generateScalarLoad eventually accesses the same element and finds it
to be NULL (DenseMap[Old])..  Offhand I'm not sure if this is
guaranteed to be NULL or if it's uninitialized and happens to be NULL.

The same issue can also go wrong in an even worse way: the second
DenseMap access can trigger a rehash and *invalidate* the an earlier
evaluated expression (for example LHS of the assignment), leading to a
crash when performing the assignment store.

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182655

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183379 91177308-0d34-0410-b5e6-96231b3b80d8
independent blocks: do not insert stores between phi nodes

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182661

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183380 91177308-0d34-0410-b5e6-96231b3b80d8
add comments to clarify the use of a temporary variable in the map insertion

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182662

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183381 91177308-0d34-0410-b5e6-96231b3b80d8
scop detection: only handle functions with loops

to detect scops in functions with no loops, use -polly-detect-scops-in-functions-without-loops

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@182941

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183382 91177308-0d34-0410-b5e6-96231b3b80d8
include missing ISL header file

to be able to compile with ISL master as of today
1df91d8515ec88dc7f7f597168ad0f34f26de5a7

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@183023

git-svn-id: https://llvm.org/svn/llvm-project/polly/branches/release_33@183383 91177308-0d34-0410-b5e6-96231b3b80d8
Test that independent block pass does not transform induction variables

The original test case showed a problem with the independet blocks pass and
we decided to XFAIL it for now. Unfortunately the failure is not detected if
we build without asserts and the verification of the independent block pass
is not run. This change tests now for the actual reason of the failure and
should trigger even in a non asserts build. We did not yet solve the underlying
bug, but this should at least make the test suite behavior consistent.

Merged from: https://llvm.org/svn/llvm-project/polly/trunk@183025

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