scop detection: properly instantiate SCEVs to the place where they are used

Fix inspired from c2d4a0627e95c34a819b9d4ffb4db62daa78dade.

    Given the following code

        for (i = 0; i < 10; i++) {
          ;
        }

    S:  A[i] = 0

    When translate the data reference A[i] in statement S using scev, we need to
    retrieve the scev of 'i' at the location of 'S'. If we do not do this the
    scev that we obtain will be expressed as {0,+,1}_for and will reference loop
    iterators that do not surround 'S'. What we really want is the scev to be
    instantiated to the value of 'i' after the loop. This value is {10}.

This used to crash in:

    int loopDimension = getLoopDepth(Expr->getLoop());

    isl_aff *LAff = isl_aff_set_coefficient_si(
        isl_aff_zero_on_domain(LocalSpace), isl_dim_in, loopDimension, 1);

(gdb) p Expr->dump()
{8,+,8}<nw><%do.body>

(gdb) p getLoopDepth(Expr->getLoop())
$5 = 0

    isl_space *Space = isl_space_set_alloc(Ctx, 0, NbLoopSpaces);
    isl_local_space *LocalSpace = isl_local_space_from_space(Space);

As we are trying to create a memory access in a stmt that is outside all loops,
LocalSpace has 0 dimensions:

(gdb) p NbLoopSpaces
$12 = 0

(gdb) p Statement.BB->dump()

if.then:                                          ; preds = %do.end
  %0 = load float* %add.ptr, align 4
  store float %0, float* %q.1.reg2mem, align 4
  br label %if.end.single_exit

and so the scev for %add.ptr should be taken at the place where it is used,
i.e., it should be the value on the last iteration of the do.body loop, and not
"{8,+,8}<nw><%do.body>".

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

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@179149 91177308-0d34-0410-b5e6-96231b3b80d8
Codegen: Replace region exit and entries recursively

During code generation we split the original entry and exit basic blocks
of the scop to make room for the newly generated code. To keep the region tree
up to date, we need to update the region tree. This patch ensures that not only
the region of the scop is updated, but also all child regions that share the
same entry or exit block.

We have now test case here, as the bug is only exposed by the subsequent commit.
The test cases of that commit also cover this bug.

Contributed-by: Star Tan <tanmx_star@yeah.net>

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@179158 91177308-0d34-0410-b5e6-96231b3b80d8
Support SCoPs with multiple exit edges

Regions that have multiple exit edges are very common. A simple if condition
yields e.g. such a region:

        if
      /   \
  then     else
      \   /
      after

Region: if -> after

This regions contains the bbs 'if', 'then', 'else', but not 'after'. It has
two exit edges 'then' -> 'after' and 'else' -> 'after'.

Previously we scheduled the RegionSimplify pass to translate such regions into
simple regions. With this patch, we now support them natively.

Contributed-by: Star Tan <tanmx_star@yeah.net>

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@179159 91177308-0d34-0410-b5e6-96231b3b80d8
Update formatting to latest version of clang-format

git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@179160 91177308-0d34-0410-b5e6-96231b3b80d8
ScopDetect: Allow multiplications of the form <param> * <param>

We handle these by treating this result of the multiplication as an additional
parameter.

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