[Polly][WIP] Scalar fully indexed expansion

[niosega]

Summary

This patch comes directly after https://reviews.llvm.org/D34982 which allows fully indexed expansion of MemoryKind::Array. This patch allows expansion for MemoryKind::Value and MemoryKind::PHI.

MemoryKind::Value seems to be working with no majors modifications of D34982. A test case has been added. Unfortunatly, no "run time" checks can be done for now because as @Meinersbur explains in a comment on D34982, DependenceInfo need to be cleared and reset to take expansion into account in the remaining part of the Polly pipeline. There is no way to do that in Polly for now.

MemoryKind::PHI is not working. Test case is in place, but not working. To expand MemoryKind::Array, we expand first the write and then after the reads. For MemoryKind::PHI, the idea of the current implementation is to exchange the "roles" of the read and write and expand first the read according to its domain and after the writes.
But with this strategy, I still encounter the problem of union_map in new access map.
For example with the following source code (source code of the test case) :

#define Ni 10000
#define Nj 10000
void mse(double A[Ni], double B[Nj]) {
  int i,j;
  double tmp = 6;
  for (i = 0; i < Ni; i++) {
    for (int j = 0; j<Nj; j++) {
      tmp = tmp + 2;
    }
    B[i] = tmp;
  }
}

Polly gives us the following statements and memory accesses :

Statements {
	Stmt_for_body
        Domain :=
            { Stmt_for_body[i0] : 0 <= i0 <= 9999 };
        Schedule :=
            { Stmt_for_body[i0] -> [i0, 0, 0] };
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_body[i0] -> MemRef_tmp_04__phi[] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_body[i0] -> MemRef_tmp_11__phi[] };
        Instructions {
              %tmp.04 = phi double [ 6.000000e+00, %entry.split ], [ %add.lcssa, %for.end ]
        }
	Stmt_for_inc
        Domain :=
            { Stmt_for_inc[i0, i1] : 0 <= i0 <= 9999 and 0 <= i1 <= 9999 };
        Schedule :=
            { Stmt_for_inc[i0, i1] -> [i0, 1, i1] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi[] };
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi[] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_inc[i0, i1] -> MemRef_add_lcssa__phi[] };
        Instructions {
              %tmp.11 = phi double [ %tmp.04, %for.body ], [ %add, %for.inc ]
              %add = fadd double %tmp.11, 2.000000e+00
              %exitcond = icmp ne i32 %inc, 10000
        }
	Stmt_for_end
        Domain :=
            { Stmt_for_end[i0] : 0 <= i0 <= 9999 };
        Schedule :=
            { Stmt_for_end[i0] -> [i0, 2, 0] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_end[i0] -> MemRef_tmp_04__phi[] };
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 1]
            { Stmt_for_end[i0] -> MemRef_add_lcssa__phi[] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            { Stmt_for_end[i0] -> MemRef_B[i0] };
        Instructions {
              %add.lcssa = phi double [ %add, %for.inc ]
              store double %add.lcssa, double* %arrayidx, align 8
              %exitcond5 = icmp ne i64 %indvars.iv.next, 10000
        }
}

and the following dependences :

{ Stmt_for_inc[i0, 9999] -> Stmt_for_end[i0] : 0 <= i0 <= 9999; 
Stmt_for_inc[i0, i1] -> Stmt_for_inc[i0, 1 + i1] : 0 <= i0 <= 9999 and 0 <= i1 <= 9998; 
Stmt_for_body[i0] -> Stmt_for_inc[i0, 0] : 0 <= i0 <= 9999; 
Stmt_for_end[i0] -> Stmt_for_body[1 + i0] : 0 <= i0 <= 9998 }

When trying to expand this memory access :

{ Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi[] };

The new access map would look like this :

{ Stmt_for_inc[i0, 9999] -> MemRef_tmp_11__phi_exp[i0] : 0 <= i0 <= 9999; Stmt_for_inc[i0, i1] ->MemRef_tmp_11__phi_exp[i0, 1 + i1] : 0 <= i0 <= 9999 and 0 <= i1 <= 9998 }

The idea to implement the expansion for PHI access is an idea from @Meinersbur and I don't understand why my implementation does not work. I should have miss something in the understanding of the idea.

[simbuerg]

We talked about it on Friday but I think I can help out more with a small writeup.

First to your SCoP. The accesses to 'add_lcssa_phi' result from LLVM transforming the loop into "loop closed static single assignment" form, i.e.,
providing a single definition for values that live accross the loop boundaries outside of the loop. LLVM does this by inserting redundant PHI nodes for these values.
That's why you see a PHI node with a single operand in the LLVM IR right after the innermost loop.

You got (roughly) this after LCSSA (actually only tmp_lcssa):

#define Ni 10000
#define Nj 10000
void mse(double A[Ni], double B[Nj]) {
  int i,j;
  double tmp = 6;
  for (i = 0; i < Ni; i++) {
    // Either outside, or previous
    tmp_0 = PHI(tmp, tmp_lcssa);

    for (int j = 0; j<Nj; j++) {
      // Either outside, or previous
      tmp_1 = PHI(tmp_0, tmp_2);
      tmp_2 = tmp_1 + 2;
    }

    // tmp_2's lifetime exceeds the innermost loop
    tmp_lcssa = PHI(tmp_2);
    B[i] = tmp_lcssa;
  }
}

Polly then models each PHI node as a 'load' of new memory that was written at the end of the incoming block (numbering is differnt, sorry).

Statements {
	Stmt_for_body
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 1] // Load current value of 'tmp' (PHI_0)
            { Stmt_for_body[i0] -> MemRef_tmp_04__phi[] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1] // Write for PHI_1
            { Stmt_for_body[i0] -> MemRef_tmp_11__phi[] };
        
	Stmt_for_inc
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1] // Write for PHI_1
            { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi[] };
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 1] // Load current value of 'tmp' (PHI_1)
            { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi[] }; 
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1] // Write for PHI_2
            { Stmt_for_inc[i0, i1] -> MemRef_add_lcssa__phi[] };
        
	Stmt_for_end
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 1] // Write for PHI_0
            { Stmt_for_end[i0] -> MemRef_tmp_04__phi[] };
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 1] // Load current value of 'tmp_lcssa' (PHI_2)
            { Stmt_for_end[i0] -> MemRef_add_lcssa__phi[] };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            { Stmt_for_end[i0] -> MemRef_B[i0] };
}

Now when you switch the roles of Reads and Writes for PHI nodes you should always get a single read and one or more writes (see above). After PHI expansion it should virtually look like this:

void mse(double A[Ni], double B[Nj]) {
  int i,j;
  double tmp = 6;
  for (i = 0; i < Ni; i++) {
    // Either outside, or previous
    tmp_0 = PHI(tmp, tmp_lcssa); // READ: tmp_0[i] (Problem: Nobody is writing this value
                                                        (Copy in required), you should actually bail out on this example).
    // WRITE: tmp_1[i][0] (Initial value).

    for (int j = 0; j<Nj; j++) {
      // Either outside, or previous
      tmp_1 = PHI(tmp_0, tmp_2); // READ: tmp_1[i][j]
      tmp_2 = tmp_1 + 2;

      // WRITE: tmp_1[i][j+1] (We need to write the current value into the 'next' iteration because we will read the value from there).
      // WRITE: tmp_lcssa[i] (Got this one from LCSSA)
    }

    tmp_lcssa = PHI(tmp_2); // READ: tmp_lcssa[i]
    B[i] = tmp_lcssa;

    // WRITE: tmp_0[i+1] (We need to write the current value into the 'next' iteration because we will read the value from there).
  }
}

I can't see yet why your code specifically does the wrong thing, but I hope this helps anyway. @everyone correct me if i missed something, it was late :-)

lib/Transform/MaximalStaticExpansion.cpp

398 ↗

(On Diff #110855)

or not of.

Besides, no need to verbally describe the if statement. Just remove the comment.

406 ↗

(On Diff #110855)

Why 'expandAccordingToDependences'?

Style: I would handle that loop inside expandRead(s) and pass the Reads as parameter (You have to handle them all anyway inside the function, might as well iterate in there).

I think what would make everything clearer (to me at least) would be a naming as follows:

expandAccess (Read/Write): Your expandAccordingToDomain.
redirect/mapAccess (Read/Write): Your expandAccordingToDependences.

The first does the array allocation, the second redirects/maps the access(es) to the new array.

[Meinersbur]

lib/Transform/MaximalStaticExpansion.cpp

84–85 ↗

(On Diff #110855)

[Style] Doxygen expects @param ParameterName, that is, it interprets If as a parameter name.

369–371 ↗

(On Diff #110855)

[Style] No parenthesis around single statements.

test/MaximalStaticExpansion/non_working_phi.ll

1 ↗

(On Diff #110855)

Try not to add other passes than the one you are testing. That makes the test case more robust against changes in those passes (now that -polly-position=before-vectorizer is default, and the new pass manager doesn't even have an "early" extension point, -polly-canonicalize might be removed in the mid-term).

Use opt -polly-canonicalize -S non_working_phi.ll > non_working_phi.ll to produce an .ll file which doesn't need --polly-canonicalize.

If you are using clang, use -polly-dump-before-file=non_working_phi.ll to generate an .ll file that does not need any processing.

[niosega]

Rebase with the new version of master to fix the bug of not correct dependencies (https://reviews.llvm.org/D36791).
Take Michael and Andreas comments into account.

Some test cases for phi expansion need to be added. But the one in place output the expected memory accesses.

I need to add a check before expansion to avoid expansion of Phi which need read from original scalar.

[niosega]

test/MaximalStaticExpansion/working_phi_expansion.ll

22 ↗

(On Diff #111684)

This array should not be expanded because the expansion would lead to a read to the original array.
But the expanded memory accesses look like what is expected from @simbuerg analysis (in a previous comment).

A check before expansion will be added in a next revision.

[niosega]

Add a check that verify, before expansion (in isExpandable) if the expansion would lead to a read from the original value of the scalar.

[niosega]

Add test cases for Phi expansion and one 'non-trivial' for array expansion.

[niosega]

test/MaximalStaticExpansion/working_deps_between_inners_phi.ll

33 ↗

(On Diff #111821)

The arrays are not always coming in the same order. Is there a better solution than CHECK-DAG to handle such checks ?

[Meinersbur]

test/MaximalStaticExpansion/working_deps_between_inners_phi.ll

33 ↗

(On Diff #111821)

If there is an indeterminism, we should make it deterministic. Most ofthen this is because we are using some DenseMap or DenseMap whose iteration order depends on memory addresses. We most commonly resolve this be replacing them by a MapVector/SetVector.

In this case, ArrayInfoSetTy is already a SetVector. Maybe it is where the elements are added.

Fixing that would be nice, but not required.

polly/trunk/lib/Transform/MaximalStaticExpansion.cpp

public:
   /// @param OS The stream where to print.
   /// @param S The SCop that must be printed.
   void printScop(raw_ostream &OS, Scop &S) const override;
 
   /// Register all analyses and transformations required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
-  /// OptimizationRemarkEmitter object for displaying diagnostic remarks
+  /// OptimizationRemarkEmitter object for displaying diagnostic remarks.
   OptimizationRemarkEmitter *ORE;
 
   /// Emit remark
   void emitRemark(StringRef Msg, Instruction *Inst);
 
   /// Return true if the SAI in parameter is expandable.
   ///
   /// @param SAI the SAI that need to be checked.
   /// @param Writes A set that will contains all the write accesses.
   /// @param Reads A set that will contains all the read accesses.
   /// @param S The SCop in which the SAI is in.
   /// @param Dependences The RAW dependences of the SCop.
   bool isExpandable(const ScopArrayInfo *SAI,
                     SmallPtrSetImpl<MemoryAccess *> &Writes,
                     SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S,
                     const isl::union_map &Dependences);
 
-  /// Expand a write memory access.
+  /// Expand the MemoryAccess according to its domain.
   ///
   /// @param S The SCop in which the memory access appears in.
   /// @param MA The memory access that need to be expanded.
-  ScopArrayInfo *expandWrite(Scop &S, MemoryAccess *MA);
-
-  /// Expand the read memory access.
-  ///
-  /// @param S The SCop in which the memory access appears in.
-  /// @param MA The memory access that need to be expanded.
-  /// @param Dependences The RAW dependences of the SCop.
-  /// @param ExpandedSAI The expanded SAI created during write expansion.
-  void expandRead(Scop &S, MemoryAccess *MA, const isl::union_map &Dependences,
-                  ScopArrayInfo *ExpandedSAI);
+  ScopArrayInfo *expandAccess(Scop &S, MemoryAccess *MA);
 
   /// Filter the dependences to have only one related to current memory access.
   ///
   /// @param S The SCop in which the memory access appears in.
   /// @param MapDependences The dependences to filter.
   /// @param MA The memory access that need to be expanded.
   isl::union_map filterDependences(Scop &S,
                                    const isl::union_map &MapDependences,
                                    MemoryAccess *MA);
+
+  /// Expand the MemoryAccess according to Dependences and already expanded
+  /// MemoryAccesses.
+  ///
+  /// @param The SCop in which the memory access appears in.
+  /// @param The memory access that need to be expanded.
+  /// @param Dependences The RAW dependences of the SCop.
+  /// @param ExpandedSAI The expanded SAI created during write expansion.
+  /// @param Reverse if true, the Dependences union_map is reversed before
+  /// intersection.
+  void mapAccess(Scop &S, SmallPtrSetImpl<MemoryAccess *> &Accesses,
+                 const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,
+                 bool Reverse);
+
+  /// Expand PHI memory accesses.
+  ///
+  /// @param The SCop in which the memory access appears in.
+  /// @param The ScopArrayInfo representing the PHI accesses to expand.
+  /// @param Dependences The RAW dependences of the SCop.
+  void expandPhi(Scop &S, const ScopArrayInfo *SAI,
+                 const isl::union_map &Dependences);
 };
 } // namespace
 
 namespace {
 
 #ifndef NDEBUG
 /// Whether a dimension of a set is bounded (lower and upper) by a constant,
 /// i.e. there are two constants Min and Max, such that every value x of the
isl::union_map MaximalStaticExpander::filterDependences(
 
   auto SAI = MA->getLatestScopArrayInfo();
 
   auto AccessDomainSet = MA->getAccessRelation().domain();
   auto AccessDomainId = AccessDomainSet.get_tuple_id();
 
   isl::union_map MapDependences = isl::union_map::empty(S.getParamSpace());
 
-  Dependences.reverse().foreach_map([&MapDependences, &AccessDomainId,
-                                     &SAI](isl::map Map) -> isl::stat {
+  Dependences.foreach_map([&MapDependences, &AccessDomainId,
 
     // Filter out Statement to Statement dependences.
     if (!Map.can_curry())
       return isl::stat::ok;
 
     // Intersect with the relevant SAI.
     auto TmpMapDomainId =
         Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set);
isl::union_map MaximalStaticExpander::filterDependences(
   return MapDependences;
 }
 
 bool MaximalStaticExpander::isExpandable(
     const ScopArrayInfo *SAI, SmallPtrSetImpl<MemoryAccess *> &Writes,
     SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S,
     const isl::union_map &Dependences) {
 
+  if (SAI->isValueKind()) {
+    Writes.insert(S.getValueDef(SAI));
+    for (auto MA : S.getValueUses(SAI))
+      Reads.insert(MA);
+    return true;
+  } else if (SAI->isPHIKind()) {
+    auto Read = S.getPHIRead(SAI);
+
+    auto StmtDomain = isl::union_set(Read->getStatement()->getDomain());
+
+    auto Writes = S.getPHIIncomings(SAI);
+
+    // Get the domain where all the writes are writing to.
+    auto WriteDomain = isl::union_set::empty(S.getParamSpace());
+
+    for (auto Write : Writes) {
+      auto MapDeps = filterDependences(S, Dependences, Write);
+      MapDeps.foreach_map(
+          [&StmtDomain, &WriteDomain](isl::map Map) -> isl::stat {
+            WriteDomain = WriteDomain.add_set(Map.range());
+            return isl::stat::ok;
+          });
+    }
+
+    // For now, read from original scalar is not possible.
+    if (!StmtDomain.is_equal(WriteDomain)) {
+      emitRemark(SAI->getName() + " read from its original value.",
+                 Read->getAccessInstruction());
+      return false;
+    }
+
+    return true;
+  } else if (SAI->isExitPHIKind()) {
+    // For now, we are not able to expand ExitPhi.
+    emitRemark(SAI->getName() + " is a ExitPhi node.",
+               S.getEnteringBlock()->getFirstNonPHI());
+    return false;
+  }
+
   int NumberWrites = 0;
   for (ScopStmt &Stmt : S) {
     auto StmtReads = isl::union_map::empty(S.getParamSpace());
     auto StmtWrites = isl::union_map::empty(S.getParamSpace());
 
     for (MemoryAccess *MA : Stmt) {
 
       // Check if the current MemoryAccess involved the current SAI.
       if (SAI != MA->getLatestScopArrayInfo())
         continue;
 
-      // For now, we are not able to expand Scalar.
-      if (MA->isLatestScalarKind()) {
-        emitRemark(SAI->getName() + " is a Scalar access.",
-                   MA->getAccessInstruction());
-        return false;
-      }
-
       // For now, we are not able to expand array where read come after write
       // (to the same location) in a same statement.
       auto AccRel = isl::union_map(MA->getAccessRelation());
       if (MA->isRead()) {
         // Reject load after store to same location.
         if (!StmtWrites.is_disjoint(AccRel)) {
           emitRemark(SAI->getName() + " has read after write to the same "
                                       "element in same statement. The "
for (MemoryAccess *MA : Stmt) {
         // Get the domain of the current ScopStmt.
         auto StmtDomain = Stmt.getDomain();
 
         // Get the domain of the future Read access.
         auto ReadDomainSet = MA->getAccessRelation().domain();
         auto ReadDomain = isl::union_set(ReadDomainSet);
 
         // Get the dependences relevant for this MA
-        auto MapDependences = filterDependences(S, Dependences, MA);
-        auto DepsDomain = MapDependences.domain();
+        auto MapDependences = filterDependences(S, Dependences.reverse(), MA);
         unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get());
 
+        if (NumberElementMap == 0) {
+          emitRemark("The expansion of " + SAI->getName() +
+                         " would lead to a read from the original array.",
+                     MA->getAccessInstruction());
+          return false;
+        }
+
+        auto DepsDomain = MapDependences.domain();
+
         // If there are multiple maps in the Deps, we cannot handle this case
         // for now.
         if (NumberElementMap != 1) {
           emitRemark(SAI->getName() +
                          " has too many dependences to be handle for now.",
                      MA->getAccessInstruction());
           return false;
         }
if (NumberWrites == 0) {
     emitRemark(SAI->getName() + " has 0 write access.",
                S.getEnteringBlock()->getFirstNonPHI());
     return false;
   }
 
   return true;
 }
 
-void MaximalStaticExpander::expandRead(Scop &S, MemoryAccess *MA,
-                                       const isl::union_map &Dependences,
-                                       ScopArrayInfo *ExpandedSAI) {
+void MaximalStaticExpander::mapAccess(Scop &S,
+                                      SmallPtrSetImpl<MemoryAccess *> &Accesses,
+                                      ScopArrayInfo *ExpandedSAI,
+                                      bool Reverse) {
+
+  for (auto MA : Accesses) {
 
     // Get the current AM.
     auto CurrentAccessMap = MA->getAccessRelation();
 
     // Get RAW dependences for the current WA.
-  auto WriteDomainSet = MA->getAccessRelation().domain();
-  auto WriteDomain = isl::union_set(WriteDomainSet);
+    auto DomainSet = MA->getAccessRelation().domain();
+    auto Domain = isl::union_set(DomainSet);
 
-  // Get the dependences relevant for this MA
-  auto MapDependences = filterDependences(S, Dependences, MA);
+    // Get the dependences relevant for this MA.
+    isl::union_map MapDependences;
+    if (Reverse) {
+      MapDependences = filterDependences(S, Dependences.reverse(), MA);
+    } else {
+      MapDependences = filterDependences(S, Dependences, MA);
+    }
 
     // If no dependences, no need to modify anything.
     if (MapDependences.is_empty())
       return;
 
     assert(isl_union_map_n_map(MapDependences.get()) == 1 &&
            "There are more than one RAW dependencies in the union map.");
     auto NewAccessMap = isl::map::from_union_map(MapDependences);
 
     auto Id = ExpandedSAI->getBasePtrId();
 
     // Replace the out tuple id with the one of the access array.
     NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);
 
     // Set the new access relation.
     MA->setNewAccessRelation(NewAccessMap);
   }
+}
 
-ScopArrayInfo *MaximalStaticExpander::expandWrite(Scop &S, MemoryAccess *MA) {
+ScopArrayInfo *MaximalStaticExpander::expandAccess(Scop &S, MemoryAccess *MA) {
 
   // Get the current AM.
   auto CurrentAccessMap = MA->getAccessRelation();
 
   unsigned in_dimensions = CurrentAccessMap.dim(isl::dim::in);
 
   // Get domain from the current AM.
   auto Domain = CurrentAccessMap.domain();
ScopArrayInfo *MaximalStaticExpander::expandAccess(Scop &S, MemoryAccess *MA) {
   NewAccessMap = isl::map(ConstraintBasicMap);
 
   // Set the new access relation map.
   MA->setNewAccessRelation(NewAccessMap);
 
   return ExpandedSAI;
 }
 
+void MaximalStaticExpander::expandPhi(Scop &S, const ScopArrayInfo *SAI,
+                                      const isl::union_map &Dependences) {
+  SmallPtrSet<MemoryAccess *, 4> Writes;
+  for (auto MA : S.getPHIIncomings(SAI))
+    Writes.insert(MA);
+  auto Read = S.getPHIRead(SAI);
+  auto ExpandedSAI = expandAccess(S, Read);
+
+  mapAccess(S, Writes, Dependences, ExpandedSAI, false);
+}
+
 void MaximalStaticExpander::emitRemark(StringRef Msg, Instruction *Inst) {
   ORE->emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst)
             << Msg);
 }
 
 bool MaximalStaticExpander::runOnScop(Scop &S) {
-
   // Get the ORE from OptimizationRemarkEmitterWrapperPass.
   ORE = &(getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
 
   // Get the RAW Dependences.
   auto &DI = getAnalysis<DependenceInfo>();
   auto &D = DI.getDependences(Dependences::AL_Reference);
   auto Dependences = isl::give(D.getDependences(Dependences::TYPE_RAW));
 
   SmallPtrSet<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
                                              S.arrays().end());
 
   for (auto SAI : CurrentSAI) {
     SmallPtrSet<MemoryAccess *, 4> AllWrites;
     SmallPtrSet<MemoryAccess *, 4> AllReads;
     if (!isExpandable(SAI, AllWrites, AllReads, S, Dependences))
       continue;
 
-    assert(AllWrites.size() == 1);
+    if (SAI->isValueKind() || SAI->isArrayKind()) {
+      assert(AllWrites.size() == 1 || SAI->isValueKind());
 
       auto TheWrite = *(AllWrites.begin());
-    ScopArrayInfo *ExpandedArray = expandWrite(S, TheWrite);
+      ScopArrayInfo *ExpandedArray = expandAccess(S, TheWrite);
 
-    for (MemoryAccess *MA : AllReads)
-      expandRead(S, MA, Dependences, ExpandedArray);
+      mapAccess(S, AllReads, Dependences, ExpandedArray, true);
+    } else if (SAI->isPHIKind()) {
+      expandPhi(S, SAI, Dependences);
+    }
   }
 
   return false;
 }
 
 void MaximalStaticExpander::printScop(raw_ostream &OS, Scop &S) const {
   S.print(OS, false);
 }

polly/trunk/test/MaximalStaticExpansion/working_deps_between_inners.ll

+; RUN: opt %loadPolly -polly-mse -analyze < %s | FileCheck %s
+;
+; Verify that the accesses are correctly expanded for MemoryKind::Array
+;
+; Original source code :
+;
+; #define Ni 2000
+; #define Nj 3000
+; 
+; void tmp3(double A[Ni], double B[Nj]) {
+;   int i,j;
+;   double tmp = 6;
+;   for (i = 0; i < Ni; i++) {
+;
+;     for(int h = 0; h<Nj; h++)
+;      B[h] = h; 
+;    
+;     for(j = 0; j < Nj; j++) {
+;      for(int k=0; k<Nj; k++) {
+;   tmp = i+k+j;
+;   A[i+j] = tmp*B[k];
+;       }
+;     }
+;   }
+; }
+;
+; Check if the expanded SAI are created
+;
+; CHECK: double MemRef_B_Stmt_for_body3_expanded[10000][10000]; // Element size 8
+; CHECK: double MemRef_A_Stmt_for_body11_expanded[10000][10000][10000]; // Element size 8
+;
+; Check if the memory accesses are modified
+;
+; CHECK: new: { Stmt_for_body3[i0, i1] -> MemRef_B_Stmt_for_body3_expanded[i0, i1] };
+; CHECK: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_B_Stmt_for_body3_expanded[i0, i2] };
+; CHECK: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_A_Stmt_for_body11_expanded[i0, i1, i2] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @mse(double* %A, double* %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.inc25
+  %indvars.iv14 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next15, %for.inc25 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.body3
+  %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ]
+  %0 = trunc i64 %indvars.iv to i32
+  %conv = sitofp i32 %0 to double
+  %arrayidx = getelementptr inbounds double, double* %B, i64 %indvars.iv
+  store double %conv, double* %arrayidx, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 10000
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.end:                                          ; preds = %for.body3
+  br label %for.body7
+
+for.body7:                                        ; preds = %for.end, %for.inc22
+  %indvars.iv9 = phi i64 [ 0, %for.end ], [ %indvars.iv.next10, %for.inc22 ]
+  br label %for.body11
+
+for.body11:                                       ; preds = %for.body7, %for.body11
+  %indvars.iv5 = phi i64 [ 0, %for.body7 ], [ %indvars.iv.next6, %for.body11 ]
+  %1 = add nuw nsw i64 %indvars.iv9, %indvars.iv14
+  %2 = add nuw nsw i64 %1, %indvars.iv5
+  %3 = trunc i64 %2 to i32
+  %conv13 = sitofp i32 %3 to double
+  %arrayidx15 = getelementptr inbounds double, double* %B, i64 %indvars.iv5
+  %4 = load double, double* %arrayidx15, align 8
+  %mul = fmul double %4, %conv13
+  %5 = add nuw nsw i64 %indvars.iv9, %indvars.iv14
+  %arrayidx18 = getelementptr inbounds double, double* %A, i64 %5
+  store double %mul, double* %arrayidx18, align 8
+  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
+  %exitcond8 = icmp ne i64 %indvars.iv.next6, 10000
+  br i1 %exitcond8, label %for.body11, label %for.inc22
+
+for.inc22:                                        ; preds = %for.body11
+  %indvars.iv.next10 = add nuw nsw i64 %indvars.iv9, 1
+  %exitcond13 = icmp ne i64 %indvars.iv.next10, 10000
+  br i1 %exitcond13, label %for.body7, label %for.inc25
+
+for.inc25:                                        ; preds = %for.inc22
+  %indvars.iv.next15 = add nuw nsw i64 %indvars.iv14, 1
+  %exitcond16 = icmp ne i64 %indvars.iv.next15, 10000
+  br i1 %exitcond16, label %for.body, label %for.end27
+
+for.end27:                                        ; preds = %for.inc25
+  ret void
+}

polly/trunk/test/MaximalStaticExpansion/working_deps_between_inners_phi.ll

+; RUN: opt %loadPolly -polly-mse -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-mse -pass-remarks-analysis="polly-mse" -analyze < %s 2>&1| FileCheck %s --check-prefix=MSE
+;
+; Verify that the accesses are correctly expanded for MemoryKind::Array and MemoryKind::PHI.
+; tmp_06_phi is not expanded because it need copy in.
+;
+; Original source code :
+;
+; #define Ni 2000
+; #define Nj 3000
+; 
+; void tmp3(double A[Ni], double B[Nj]) {
+;   int i,j;
+;   double tmp = 6;
+;   for (i = 0; i < Ni; i++) {
+; 
+;     for(int h = 0; h<Nj; h++)
+;       B[h] = h;
+;     
+;     for(j = 0; j < Nj; j++) {
+;       for(int k=0; k<Nj; k++) {
+;   tmp = tmp+i+k+j;
+;   A[i+j] = tmp*B[k];
+;       }
+;     }
+;   }
+; }
+;
+; Check if the expanded SAI are created except for tmp_06_phi
+;
+; MSE: MemRef_tmp_06__phi read from its original value.
+;
+; CHECK-DAG: double MemRef_A_Stmt_for_body11_expanded[10000][10000][10000]; // Element size 8
+; CHECK-DAG: double MemRef_add16_lcssa__phi_Stmt_for_inc25_expanded[10000][10000]; // Element size 8
+; CHECK-DAG: double MemRef_B_Stmt_for_body3_expanded[10000][10000]; // Element size 8
+; CHECK-DAG: double MemRef_tmp_06_Stmt_for_body_expanded[10000]; // Element size 8
+; CHECK-DAG: double MemRef_add16_lcssa_lcssa__phi_Stmt_for_inc28_expanded[10000]; // Element size 8
+; CHECK-DAG: double MemRef_tmp_14__phi_Stmt_for_body7_expanded[10000][10000]; // Element size 8
+; CHECK-DAG: double MemRef_tmp_22__phi_Stmt_for_body11_expanded[10000][10000][10000]; // Element size 8
+; CHECK-NOT: double MemRef_tmp_06__phi_Stmt_for_body_expanded[10000]; // Element size 8
+;
+; Check if the memory accesses are modified except those of tmp_06_phi
+;
+; CHECK-NOT: new: { Stmt_for_body[i0] -> MemRef_tmp_06__phi_Stmt_for_body_expanded[i0] };
+; CHECK-DAG: new: { Stmt_for_body[i0] -> MemRef_tmp_06_Stmt_for_body_expanded[i0] };
+; CHECK-DAG: new: { Stmt_for_body3[i0, i1] -> MemRef_B_Stmt_for_body3_expanded[i0, i1] };
+; CHECK-DAG: new: { Stmt_for_end[i0] -> MemRef_tmp_06_Stmt_for_body_expanded[i0] };
+; CHECK-DAG: new: { Stmt_for_end[i0] -> MemRef_tmp_14__phi_Stmt_for_body7_expanded[i0, 0] };
+; CHECK-DAG: new: { Stmt_for_body7[i0, i1] -> MemRef_tmp_14__phi_Stmt_for_body7_expanded[i0, i1] };
+; CHECK-DAG: new: { Stmt_for_body7[i0, i1] -> MemRef_tmp_22__phi_Stmt_for_body11_expanded[i0, i1, 0] };
+; CHECK-DAG: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_tmp_22__phi_Stmt_for_body11_expanded[i0, i1, 1 + i2] : i2 <= 9998 };
+; CHECK-DAG: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_tmp_22__phi_Stmt_for_body11_expanded[i0, i1, i2] };
+; CHECK-DAG: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_B_Stmt_for_body3_expanded[i0, i2] };
+; CHECK-DAG: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_A_Stmt_for_body11_expanded[i0, i1, i2] };
+; CHECK-DAG: new: { Stmt_for_body11[i0, i1, 9999] -> MemRef_add16_lcssa__phi_Stmt_for_inc25_expanded[i0, i1] };
+; CHECK-DAG: new: { Stmt_for_inc25[i0, i1] -> MemRef_tmp_14__phi_Stmt_for_body7_expanded[i0, 1 + i1] : i1 <= 9998 };
+; CHECK-DAG: new: { Stmt_for_inc25[i0, i1] -> MemRef_add16_lcssa__phi_Stmt_for_inc25_expanded[i0, i1] };
+; CHECK-DAG: new: { Stmt_for_inc25[i0, 9999] -> MemRef_add16_lcssa_lcssa__phi_Stmt_for_inc28_expanded[i0] };
+; CHECK-DAG: new: { Stmt_for_inc28[i0] -> MemRef_add16_lcssa_lcssa__phi_Stmt_for_inc28_expanded[i0] };
+; CHECK-NOT: new: { Stmt_for_inc28[i0] -> MemRef_tmp_06__phi_Stmt_for_body_expanded[1 + i0] : i0 <= 9998 };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @mse(double* %A, double* %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.inc28
+  %indvars.iv15 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next16, %for.inc28 ]
+  %tmp.06 = phi double [ 6.000000e+00, %entry.split ], [ %add16.lcssa.lcssa, %for.inc28 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.body3
+  %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ]
+  %0 = trunc i64 %indvars.iv to i32
+  %conv = sitofp i32 %0 to double
+  %arrayidx = getelementptr inbounds double, double* %B, i64 %indvars.iv
+  store double %conv, double* %arrayidx, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 10000
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.end:                                          ; preds = %for.body3
+  br label %for.body7
+
+for.body7:                                        ; preds = %for.end, %for.inc25
+  %indvars.iv11 = phi i64 [ 0, %for.end ], [ %indvars.iv.next12, %for.inc25 ]
+  %tmp.14 = phi double [ %tmp.06, %for.end ], [ %add16.lcssa, %for.inc25 ]
+  br label %for.body11
+
+for.body11:                                       ; preds = %for.body7, %for.body11
+  %indvars.iv8 = phi i64 [ 0, %for.body7 ], [ %indvars.iv.next9, %for.body11 ]
+  %tmp.22 = phi double [ %tmp.14, %for.body7 ], [ %add16, %for.body11 ]
+  %1 = trunc i64 %indvars.iv15 to i32
+  %conv12 = sitofp i32 %1 to double
+  %add = fadd double %tmp.22, %conv12
+  %2 = trunc i64 %indvars.iv8 to i32
+  %conv13 = sitofp i32 %2 to double
+  %add14 = fadd double %add, %conv13
+  %3 = trunc i64 %indvars.iv11 to i32
+  %conv15 = sitofp i32 %3 to double
+  %add16 = fadd double %add14, %conv15
+  %arrayidx18 = getelementptr inbounds double, double* %B, i64 %indvars.iv8
+  %4 = load double, double* %arrayidx18, align 8
+  %mul = fmul double %add16, %4
+  %5 = add nuw nsw i64 %indvars.iv11, %indvars.iv15
+  %arrayidx21 = getelementptr inbounds double, double* %A, i64 %5
+  store double %mul, double* %arrayidx21, align 8
+  %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1
+  %exitcond10 = icmp ne i64 %indvars.iv.next9, 10000
+  br i1 %exitcond10, label %for.body11, label %for.inc25
+
+for.inc25:                                        ; preds = %for.body11
+  %add16.lcssa = phi double [ %add16, %for.body11 ]
+  %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1
+  %exitcond14 = icmp ne i64 %indvars.iv.next12, 10000
+  br i1 %exitcond14, label %for.body7, label %for.inc28
+
+for.inc28:                                        ; preds = %for.inc25
+  %add16.lcssa.lcssa = phi double [ %add16.lcssa, %for.inc25 ]
+  %indvars.iv.next16 = add nuw nsw i64 %indvars.iv15, 1
+  %exitcond17 = icmp ne i64 %indvars.iv.next16, 10000
+  br i1 %exitcond17, label %for.body, label %for.end30
+
+for.end30:                                        ; preds = %for.inc28
+  ret void
+}

polly/trunk/test/MaximalStaticExpansion/working_expansion.ll

 ; RUN: opt %loadPolly -polly-mse -analyze < %s | FileCheck %s
 ;
-; Verify that the accesses are correctly expanded
+; Verify that the accesses are correctly expanded for MemoryKind::Array
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ; 
 ; double mse(double A[Ni], double B[Nj]) {
 ;   int i;

polly/trunk/test/MaximalStaticExpansion/working_phi_expansion.ll

+; RUN: opt %loadPolly -polly-mse -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-mse -pass-remarks-analysis="polly-mse" -analyze < %s 2>&1 | FileCheck %s --check-prefix=MSE
+;
+; Verify that the accesses are correctly expanded for MemoryKind::PHI
+; tmp_04 is not expanded because it need copy-in.
+;
+; Original source code :
+;
+; #define Ni 10000
+; #define Nj 10000
+;
+; void mse(double A[Ni], double B[Nj]) {
+;   int i,j;
+;   double tmp = 6;
+;   for (i = 0; i < Ni; i++) {
+;     for (int j = 0; j<Nj; j++) {
+;       tmp = tmp + 2;
+;     }
+;     B[i] = tmp;
+;   }
+;
+; Check that the pass detects that tmp_04 reads from original value.
+;
+; MSE: MemRef_tmp_04__phi read from its original value.
+;
+; Check that the SAI are created except the expanded SAI of tmp_04.
+;
+; CHECK-NOT: double MemRef_tmp_04__phi_Stmt_for_body_expanded[10000]; // Element size 8
+; CHECK: double MemRef_tmp_11__phi_Stmt_for_inc_expanded[10000][10000]; // Element size
+; CHECK: double MemRef_add_lcssa__phi_Stmt_for_end_expanded[10000]; // Element size 8
+; CHECK: double MemRef_B_Stmt_for_end_expanded[10000]; // Element size 8
+;
+; Check that the memory accesses are modified except those related to tmp_04.
+;
+; CHECK-NOT: new: { Stmt_for_body[i0] -> MemRef_tmp_04__phi_Stmt_for_body_expanded[i0] };
+; CHECK: new: { Stmt_for_body[i0] -> MemRef_tmp_11__phi_Stmt_for_inc_expanded[i0, 0] };
+; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi_Stmt_for_inc_expanded[i0, 1 + i1] : i1 <= 9998 };
+; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi_Stmt_for_inc_expanded[i0, i1] };
+; CHECK: new: { Stmt_for_inc[i0, 9999] -> MemRef_add_lcssa__phi_Stmt_for_end_expanded[i0] };
+; CHECK-NOT: new: { Stmt_for_end[i0] -> MemRef_tmp_04__phi_Stmt_for_body_expanded[1 + i0] : i0 <= 9998 };
+; CHECK: new: { Stmt_for_end[i0] -> MemRef_add_lcssa__phi_Stmt_for_end_expanded[i0] };
+; CHECK: new: { Stmt_for_end[i0] -> MemRef_B_Stmt_for_end_expanded[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @tmp(double* %A, double* %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.end
+  %indvars.iv = phi i64 [ 0, %entry.split ], [ %indvars.iv.next, %for.end ]
+  %tmp.04 = phi double [ 6.000000e+00, %entry.split ], [ %add.lcssa, %for.end ]
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %for.inc
+  %j1.02 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %tmp.11 = phi double [ %tmp.04, %for.body ], [ %add, %for.inc ]
+  %add = fadd double %tmp.11, 2.000000e+00
+  %inc = add nuw nsw i32 %j1.02, 1
+  %exitcond = icmp ne i32 %inc, 10000
+  br i1 %exitcond, label %for.inc, label %for.end
+
+for.end:                                          ; preds = %for.inc
+  %add.lcssa = phi double [ %add, %for.inc ]
+  %arrayidx = getelementptr inbounds double, double* %B, i64 %indvars.iv
+  store double %add.lcssa, double* %arrayidx, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond5 = icmp ne i64 %indvars.iv.next, 10000
+  br i1 %exitcond5, label %for.body, label %for.end7
+
+for.end7:                                         ; preds = %for.end
+  ret void
+}

polly/trunk/test/MaximalStaticExpansion/working_phi_two_scalars.ll

+; RUN: opt %loadPolly -polly-mse -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-mse -pass-remarks-analysis="polly-mse" -analyze < %s 2>&1 | FileCheck %s --check-prefix=MSE
+;
+; Verify that the accesses are correctly expanded for MemoryKind::PHI
+; tmp_05 and tmp2_06 are not expanded because they need copy-in.
+;
+; Original source code :
+;
+; #define Ni 10000
+; #define Nj 10000
+;
+; void mse(double A[Ni], double B[Nj]) {
+;   int i,j;
+;   double tmp = 6;
+;   double tmp2 = 9;
+;   for (i = 0; i < Ni; i++) {
+;     for(j = 0; j < Nj; j++) {
+;       tmp = tmp + tmp2;
+;       tmp2 = i*j;
+;     }
+;   }
+; }
+;
+; Check that the pass detects that tmp_05 and tmp2_06 read from their original values.
+;
+; MSE-DAG: MemRef_tmp_05__phi read from its original value.
+; MSE-DAG: MemRef_tmp2_06__phi read from its original value.
+;
+; Check that the SAI are created except the expanded SAI of tmp_05 and tmp2_06.
+;
+; CHECK-DAG: double MemRef_add_lcssa__phi_Stmt_for_inc4_expanded[10000]; // Element size 8
+; CHECK-DAG: double MemRef_tmp2_13__phi_Stmt_for_inc_expanded[10000][10000]; // Element size
+; CHECK-DAG: double MemRef_conv_lcssa__phi_Stmt_for_inc4_expanded[10000]; // Element size 8
+; CHECK-DAG: double MemRef_tmp_12__phi_Stmt_for_inc_expanded[10000][10000]; // Element size 8
+; CHECK-NOT: double MemRef_tmp_05__phi_Stmt_for_body_expanded[10000]; // Element size 8
+; CHECK-NOT: double MemRef_tmp2_06__phi_Stmt_for_body_expanded[10000]; // Element size 8
+;
+; Check that the memory accesses are modified except those related to tmp_05 and tmp_06.
+;
+; CHECK-NOT: new: { Stmt_for_body[i0] -> MemRef_tmp2_06__phi_Stmt_for_body_expanded[i0] };
+; CHECK-NOT: new: { Stmt_for_body[i0] -> MemRef_tmp_05__phi_Stmt_for_body_expanded[i0] };
+; CHECK: new: { Stmt_for_body[i0] -> MemRef_tmp2_13__phi_Stmt_for_inc_expanded[i0, 0] };
+; CHECK: new: { Stmt_for_body[i0] -> MemRef_tmp_12__phi_Stmt_for_inc_expanded[i0, 0] };
+; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp2_13__phi_Stmt_for_inc_expanded[i0, 1 + i1] : i1 <= 9998 };
+; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp2_13__phi_Stmt_for_inc_expanded[i0, i1] };
+; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp_12__phi_Stmt_for_inc_expanded[i0, 1 + i1] : i1 <= 9998 };
+; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp_12__phi_Stmt_for_inc_expanded[i0, i1] };
+; CHECK: new: { Stmt_for_inc[i0, 9999] -> MemRef_conv_lcssa__phi_Stmt_for_inc4_expanded[i0] };
+; CHECK: new: { Stmt_for_inc[i0, 9999] -> MemRef_add_lcssa__phi_Stmt_for_inc4_expanded[i0] };
+; CHECK-NOT: new: { Stmt_for_inc4[i0] -> MemRef_tmp2_06__phi_Stmt_for_body_expanded[1 + i0] : i0 <= 9998 };
+; CHECK-NOT: new: { Stmt_for_inc4[i0] -> MemRef_tmp_05__phi_Stmt_for_body_expanded[1 + i0] : i0 <= 9998 };
+; CHECK: new: { Stmt_for_inc4[i0] -> MemRef_conv_lcssa__phi_Stmt_for_inc4_expanded[i0] };
+; CHECK: new: { Stmt_for_inc4[i0] -> MemRef_add_lcssa__phi_Stmt_for_inc4_expanded[i0] };
+; 
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @tmp(double* %A, double* %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.inc4
+  %tmp2.06 = phi double [ 9.000000e+00, %entry.split ], [ %conv.lcssa, %for.inc4 ]
+  %tmp.05 = phi double [ 6.000000e+00, %entry.split ], [ %add.lcssa, %for.inc4 ]
+  %i.04 = phi i32 [ 0, %entry.split ], [ %inc5, %for.inc4 ]
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %for.inc
+  %tmp2.13 = phi double [ %tmp2.06, %for.body ], [ %conv, %for.inc ]
+  %tmp.12 = phi double [ %tmp.05, %for.body ], [ %add, %for.inc ]
+  %j.01 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %mul = mul nuw nsw i32 %j.01, %i.04
+  %conv = sitofp i32 %mul to double
+  %add = fadd double %tmp.12, %tmp2.13
+  %inc = add nuw nsw i32 %j.01, 1
+  %exitcond = icmp ne i32 %inc, 10000
+  br i1 %exitcond, label %for.inc, label %for.inc4
+
+for.inc4:                                         ; preds = %for.inc
+  %conv.lcssa = phi double [ %conv, %for.inc ]
+  %add.lcssa = phi double [ %add, %for.inc ]
+  %inc5 = add nuw nsw i32 %i.04, 1
+  %exitcond7 = icmp ne i32 %inc5, 10000
+  br i1 %exitcond7, label %for.body, label %for.end6
+
+for.end6:                                         ; preds = %for.inc4
+  ret void
+}

polly/trunk/test/MaximalStaticExpansion/working_value_expansion.ll

+; RUN: opt %loadPolly -polly-mse -analyze < %s | FileCheck %s
+;
+; Verify that the accesses are correctly expanded for MemoryKind::Value
+;
+; Original source code :
+;
+; #define Ni 10000
+; #define Nj 10000
+;
+; void mse(double A[Ni], double B[Nj]) {
+;   int i,j;
+;   double tmp = 6;
+;   for (i = 0; i < Ni; i++) {
+;     tmp = i;
+;     for (int j = 0; j<Nj; j++) {
+;       A[j] = tmp+3;
+;     }
+;     B[i] = tmp;
+;   }
+; }
+;
+; Check if the expanded SAI are created
+;
+; CHECK: double MemRef_conv_Stmt_for_body_expanded[10000]; // Element size 8
+;
+; Check if the memory accesses are modified
+;
+; CHECK: new: { Stmt_for_body[i0] -> MemRef_conv_Stmt_for_body_expanded[i0] };
+; CHECK: new: { Stmt_for_body5[i0, i1] -> MemRef_conv_Stmt_for_body_expanded[i0] };
+; CHECK: new: { Stmt_for_end[i0] -> MemRef_conv_Stmt_for_body_expanded[i0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @mse(double* %A, double* %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.end
+  %indvars.iv3 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next4, %for.end ]
+  %0 = trunc i64 %indvars.iv3 to i32
+  %conv = sitofp i32 %0 to double
+  br label %for.body5
+
+for.body5:                                        ; preds = %for.body, %for.body5
+  %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body5 ]
+  %add = fadd double %conv, 3.000000e+00
+  %arrayidx = getelementptr inbounds double, double* %A, i64 %indvars.iv
+  store double %add, double* %arrayidx, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 10000
+  br i1 %exitcond, label %for.body5, label %for.end
+
+for.end:                                          ; preds = %for.body5
+  %arrayidx7 = getelementptr inbounds double, double* %B, i64 %indvars.iv3
+  store double %conv, double* %arrayidx7, align 8
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  %exitcond5 = icmp ne i64 %indvars.iv.next4, 10000
+  br i1 %exitcond5, label %for.body, label %for.end10
+
+for.end10:                                        ; preds = %for.end
+  ret void
+}