[Polly][WIP] Fully-Indexed static expansion

[niosega]

Summary

The idea of this patch is to implement a mechanism of fully-indexed static expansion.

The goal of this patch is to be able to expand every memory access to a fully indexed one. For example from this original source code :

 for(int i = 0; i<Ni; i++)
   for(int j = 0; j<Ni; j++)
S:     B[j] = j;
T: A[i] = B[i]

After the pass, we want this :

 for(int i = 0; i<Ni; i++)
   for(int j = 0; j<Ni; j++)
S:     B[i, j] = j;
T: A[i] = B[i, i]

We are, for now, unable to apply expansion on some cases :

• Scalar access
• Multiple writes per SAI
• MayWrite Access
• Expansion that leads to an access to the original array

[niosega]

lib/Transform/MaximalStaticExpansion.cpp

68

By reading and trying to understand the work done in DeLICM and JSONImporter::importAccesses, I had begin the implementation of my pass. But I am stuck in building the new map. For example, if we have the following c code :

 for(int i = 0; i<Ni; i++)
   for(int j = 0; j<Ni; j++)
S:     tmp = A[N+i]*tmp;

After the pass, we want this :

 for(int i = 0; i<Ni; i++)
   for(int j = 0; j<Ni; j++)
T:      tmp[i, j] = A[N+i]*tmp;

This means that I want to transform the map of S, [N] -> {S[i,j] -> tmp}, to the map of T, [N] -> {S[i,j] -> tmp[i, j]}. But i was not able to find a way to do that. Anybody has an idea on how to proceed ?

test/MaximalStaticExpansion/no_optim.ll

1 ↗

(On Diff #105173)

I try to create a test case with the folowing c code :

#define Ni 2000

double mse(double A[Ni], int N) {
  int i;
  double tmp = 2;
  for (i = 0; i < Ni; i++) {
    for (int j = 0; j<Ni; j++) {
      tmp = A[N+i]*tmp;
    }
  }
  return tmp;
}

I use the following commands to generate the IR :

clang -O2 -S -emit-llvm pure_c_main.c
opt -S  -mem2reg -polly-scops -polly-export-jscop pure_c_main.ll

and this command to detect the SCOP :

opt -polly-process-unprofitable  -polly-remarks-minimal  -polly-use-llvm-names -polly-scops -analyze  -polly-export-jscop  no_optim.ll

When I use this commands, polly detects scop but the IR is optimize due to the O2 in clang. I'd like to have a non optimize version of the IR so that the IR is directly linked to the c code. But when I remove the -02, polly does not detect any scop. Anybody has an idea why ?

[niosega]

Fully-Indexed expansion of the write accesses :

• Build the new access map from the current access map
• Create a new SAI for the expanded version of the access array or scalar
• Modify the memory access to the new SAI

Seems to be working for both scalars and non-scalars access.

For now, the test is only based on dump comparison because the code is broken : the reads are still to the old SAI.

[Meinersbur]

lib/Support/RegisterPasses.cpp

319–320

Suggestion: Put it behind DeadCodeElimination? It uses DependenceInfo and should have the same results even before MSE.

lib/Transform/MaximalStaticExpansion.cpp

1

Remove - Expand the memory access. No other header does this.

12

To be consistent with the other files, add an empty line before //===------

[Meinersbur]

lib/Transform/MaximalStaticExpansion.cpp

40

Typo: transformations

85

Check for whther this returns nullptr. At least an assertion.

Suggestion: Get the domain sizes from the writing statement's domain.

105–108

isl_dim_in and isl_dim_out dimensions have no dim_id, so this is not necessary.

111

At this point, in the regression test, we have

{ Stmt_for_cond1_preheader[i0] -> MemRef_tmp_11__phi1_expanded[o0] }

(i0 and o0 are unconnected)

That is, every statement instance accesses all array elements. It should be something like:

{ Stmt_for_cond1_preheader[i0] -> MemRef_tmp_11__phi1_expanded[i0] }

135

Use inline declarations:

bool CorrectWrite = expandWrite(S, MA);

137

We cannot return early with transformations only partially applied. The SCoP representation will be inconsistent and at best passes after this will crash, at worst we miscompile.

Please check in advance if a transformation can be applied before trying to apply it.

In this case, you may want to check to each ScopArrayInfo whether it is applicable. The class ScalarDefUseChains in DeLICM.cpp might be helpful to get the accesses of a SAI. I think we will sooner-or-later integrate it into ScopInfo.

147

runOnScop returns true if and only if the IR has been modified. We only modify the SCoP representation, therefore we only return false.

151

In printScop, you must print to OS. It will print to stdout instead to stderr. This should also make the regression test simpler.

155

You will need to add AU.addRequired<DependenceInfo>(); here at some point.

test/MaximalStaticExpansion/mse___%for.cond1.preheader---%for.end8.jscop

1

What is this file needed for?

[niosega]

In this revision, we have done :

• Use of c++ bindings for isl instead of direct isl
• Implementation of the reads expansion
• Add constraint for the write map so that the in dims are link to the out dims
• Remove useless JSCoP file
• Create a new expanded SAI for each statement
• Add a check method before doing the expansion to avoid partial expansion

Problems :

• Do I have to expand already fully-indexed array (for example, the first write of B in the test case "too-many-writes.ll" ) ?

For now, we can not expand :

• Scalar access
• MayWrite access
• SAI with more than one write
• SAI with read that can cause partial read access (because polly can not handle partial read access)

[Meinersbur]

[Suggestion] Add a regression test where generated LLVM-IR is tested.

include/polly/ScopInfo.h

840–842 ↗

(On Diff #107505)

[Style] Why was this moved?

lib/Transform/MaximalStaticExpansion.cpp

48

[Style] Instead of a set of not expandable arrays, why not using a set of expandable arrays? It feels safer because if an array is just missing in the set for whatever reason, it would not default to expand it.

[Style] std::set is rarely used in LLVM. There are alternitives: See http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallset-h .

52

[Typo] checkExpandability

60–62

[Style] Please make them doxygen comments (///)

The doxygen style for parameters we usually use is.

@param Dependences The RAW dependences of the SCoP @p S.

78

[Style] Negation in variable name and double negation. Why not bool Expandable = true?

125–130

[Style] NumerElementMap = isl_union_map_n_map(CurrentReadWriteDependences.get())

144–145

[Serious] In normal operation, do not print anything. Users expect only clang warnings and errors.

Alternatives are:

1. DEBUG(dbgs() << "") (discurraged for regression tests, this is meant for debugging)
2. Print remarks using -pass-remarks-missed
3. Print information at -analysis
4. STATISTIC

215–219

[Serious] This is not a sufficient condition for full expansion. E.g. one dimension can be a static 0.
There is also more than one possibility for full expansion (e.g. one starting at 0, another at 1). The reads must access the correct element. So if you want to implement this as a heuristic that expansion is not worth it in this case, implement it in checkExpandability such that reads are also not modified.

250–251

[Serious] I think getMaxBackedgeTakenCount can fail in cases where Polly is still able to detect affine loops. Please add at least an assert that SCEV is not SCEVCountNotCompute.

256

[Suggestion] Should this be getLatestScopArrayInfo() ?

298–299

[Remark] The structure I had in mind was

for (array : S.arrays()) {
  if (!checkExpendability(array))
    continue;

  for (ScopStmt &Stmt : S) 
    for (MemoryAccess *MA : Stmt) {
       if (MA->isRead())
         expandRead(MA);
       if (MA->isWrite())
         expandRead(MA);
  }
}

This does not need a NotExpandable set, but has worse asymptotic runtime. So I guess your version has an advantage.

303–305

[Style] We usually do not use parenthesis around single statements:

if (isExpandable(SAI))
  continue;

314

[Style] In Polly's coding style, all sentences end with a dot (but I personally don't care).

[Meinersbur]

Thank you for this mostly working version. I hope my comments are not too daunting.

lib/Transform/MaximalStaticExpansion.cpp

91

[Suggestion] One could skip the check for the current array once it is known to be unexpandable and continue with the next one.

189–200

[Suggestion] Instead of searching for the correct id, you could derive the name as in expandWrite and look it up in ScopArrayNameMap.

[Serious] What if the Id is not found? Please add an assertion for that case.

251

[Suggestion] Or use ScalarEvolution::getAddExpr(SCEV, ScalarEvolution::getConstant(1))

[Serious] I don't see where +1 is added to the ISL version.

test/MaximalStaticExpansion/working_expansion.ll

24 ↗

(On Diff #107505)

Shouldn't this be

MemRef_B_Stmt_for_body3_expanded[2000][3000]

?

[niosega]

include/polly/ScopInfo.h

840–842 ↗

(On Diff #107505)

This was moved from private to public section because I need this method to find the expanded SAI name during read expansion. But if I use the solution you suggest, I will not need it anymore.

lib/Transform/MaximalStaticExpansion.cpp

91

That is what I wanted to do in the beginning. But I didn't find a clean solution to "escape" from the two innermost loops and go to next iteration of the loop that iterate over the SAI

251

We discuss during the last phone call about an other solution that involves methods that are in FlattenAlgo.cpp to get the boundary of the loop iterations variables. That's what I meant by "ISL version". But for now, I can not access the methods from FlattenAlgo.cpp because they are defined inside an unamed namespace.

298–299

If I am not wrong, we must first expand all writes before expanding the reads. Because otherwise problems can happened during trying to find expanded SAI during read expansion.

[Meinersbur]

include/polly/ScopInfo.h

840–842 ↗

(On Diff #107505)

ok.

lib/Transform/MaximalStaticExpansion.cpp

91

A possible solution is to refactor the inner two loops to a function, which can return true/false for a ScopArrayInfo at any point.

bool isExpandable(SAI) {
 for (ScopStmt &Stmt : S) 
      for (MemoryAccess *MA : Stmt) {
         if (MA->isMayWrite())
           return false;
        
           ...
      }     
}

for (auto &SAI : S.arrays()) {
  if (!isExpandable())
    NotExpandables.insert(SAI);
}

251

You may need to modify them anyway, so don't hesitate to copy them over, especially for a prototype.

If later we find they share a significant amount of code, we can find a common file for them.

298–299

Let me refine what I some time ago I had in mind.

for (array : S.arrays()) {
  MemoryAccess *TheWrite = nullptr;
  List<MemoryAccess*> *AllReads;
  if (!isExpandable(array, TheWrite, AllReads))
    continue;
  assert(TheWrite);
  assert(AllReads.size() > 0);

  ScopArrayInfo *ExpandedArray =  expandWrite(TheWrite);

  for (MemoryAccess *MA : AllReads) 
    expandRead(MA, ExpandedArray);
}

[niosega]

Take into account remarks from Michael.

Change the structure of the expansion. Now iterate over SAI of the Scop.
Get the boundaries of the loop iterations variables with ISL.
Style modifications.

Implementation for remarks is in place but not working. One test case is broken due to change in structure. But the output seems to be correct. I will correct it as soon as possible.

[niosega]

Remove debug if condition.

[Meinersbur]

lib/Transform/MaximalStaticExpansion.cpp

194

I get a compile error here. MA->getAccessRelation() has been updated to use C++ object. Please update to Polly trunk.

340

[Suggestion] Pass string as llvm::StringRef (or const std::string & to avoid a copy)

test/MaximalStaticExpansion/partial_access.ll

1 ↗

(On Diff #107946)

[Style] Please remove trailing whitespace.

[simbuerg]

lib/Transform/MaximalStaticExpansion.cpp

182

Reminder: These should/will become diagnostics

253

As far as I remember, this will fail, if there are more than one map in the union_map. I would check that with at least an assert.

259

Where do you use this name?

315

This takes a const string &, no need to go over the c_str().

343

Why 'AssumpRestrict'?

[niosega]

Take into account Michael and Andreas comments.

Diagnostic still does not work.

[niosega]

Emit remarks instead of stderr printing. Test case works.

[Meinersbur]

To have any effect, we need to clear the DependenceInfo, otherwise -polly-opt-isl will still use the unexpanded dependence info and the mse was useless.

DependenceInfo has no facility yet to reset a previous analysis. You might want want to add one into this patch or a follow-up one.

lib/Support/RegisterPasses.cpp

144

[Suggestion] To be consistent with other switches that add passes, name this -polly-enable-mse and the pass itself -polly-mse (instead of -polly-opt-mse)?

lib/Transform/MaximalStaticExpansion.cpp

68

[Style] Use SmallPtrSetImpl<MemoryAccess *> to not require the small size in the parameter.

188

[Typo] extand -> expand

219

The consequence would not be a partial read access, but it would need to read the original value the element had before entering the SCoP. That's a special case similar to having more than one write.

308

[Nit] The UpperBound could overflow a long. Add an assertion for that?

329–332

[Style] This could be simpler using

NewAccessMap = NewAccessMap->equate(isl::dim::in, dim. isl::dim::out, dim);

or, even, better, use basic_map::equal.

348

[Nit] OptimizationRemarkEmitterWrapperPass

358–360

[Style] No braces around single statements.

Also possible:

SmallPtrSet<ScopArrayInfo *, 4> CurrentSAI(S.array_begin(), array_end());

test/MaximalStaticExpansion/partial_access.ll

1 ↗

(On Diff #108256)

The interleaving of stdout (-analyze) and stderr (-pass-remarks-analysis) is undefined. It is better to have two separate RUN lines, one checking analyze, the other -pass-remarks-analysis.

[niosega]

lib/Transform/MaximalStaticExpansion.cpp

219

Are you sure ?

Because if I remember well. Let say that we are analyzing this code :

for (i = 0; i < Ni; i++) {
  B[j] = i;
  for (int j = 0; j<Nj; j++) {
    B[j] = j;
  }
  A[i] = B[i];

When I try to set the new access relation for the B read, the setNewAccessRelation method of class MemoryAccess failed with the assert "Partial READ accesses not supported".

308

How can I efficiently check that there is an overflow ?

329–332

I'd like to use isl_basic_map_equal but I did not find the documentation of this method on the online isl doc. There is also no example of uses in Polly. Can you explain me how it works ?

[Meinersbur]

lib/Transform/MaximalStaticExpansion.cpp

219

How were you able to do that? setNewAccessRelation accepts only an isl_map, not isl_union_map.

Let me explain in more detail.

for (int k = 0; k < M; k+=1) {
  for (int i = 0; i<= N/2; i+=1) {
S:  B[i] = i;
  }
  for (int i = 0; i<N; i+=1) {
T:  = ... B[i]
  }
}

The flow dependence would look something like:

{ T[k, i] -> S[k, i] : 0 < i <= N/2 }

We could naively expand B to B_expanded:

for (int k = 0; k < M; k+=1) {
  for (int i = 0; i<= N/2; i+=1) {
S:  B_expanded[k][i] = i;
  }
  for (int i = 0; i<N; i+=1) {
T:  = ... B_expanded[k][i]
  }
}

The problem here is that B_expanded[k][i] for i > N/2 never gets written (And T would read uninitialized memory). The flow dependence doesn't tell which instance of S wrote it in the first place!! If you try to apply it naively anyway using setNewAccessRelation, we need a source of the value for all instances of S, but we don't have one for i > N/2! This is way partial read accesses are unsupported.

The correct thing to do would be to read the value from the original array B (which then becomes read-only).

{ T[k,i] -> B_expanded[k,i] : i < N/2; T[k,i] -> B[i] : i>=N/2 }

This again is an isl_union_map (NOT a partial access since it is defined for all instances of T), which we currently do not support support.

Please try to understand what the problem with partial read accesses is. Not the partial read accesses are the problem, but the reason why you would want to use one.

308

UpperBound.le(INT_MAX) (I think there is no implicit conversion from int to isl::val, but you gget the idea)

329–332

isl_map_space(SpaceMap.copy(), SpaceMap.dim(isl::in))

should get you a basic_map of that space where the n_equal = SpaceMap.dim(isl::in) in- and out-
dimensions are equal. Something like.

{ Stmt[i0, i1] -> MemRef[o0, o1] : i0 = o0 and i1 = o1 }

However, no documention could mean that the function was not intended to be public.

[niosega]

Take Michael comments into account.

[Meinersbur]

lib/Support/RegisterPasses.cpp

144

I'm ok with the switch name, but doesn't the e in "mse" already stand for "expansion" (therefore expand-mse is short for "expand-maximal-array-expansion")

lib/Transform/MaximalStaticExpansion.cpp

308–309

This assertion fails on Windows (and 32 bit platforms): The isl::val constructor takes a long, which is 32 bit this platforms. UINT_MAX exceeds its range.

310

It has been tested for the range of an unsigned int.

311

If UpperBound.get_num_si() is UINT_MAX, you get an overflow when adding +1.

test/MaximalStaticExpansion/read_from_original.ll

1 ↗

(On Diff #108467)

Nice new testcase!

[niosega]

lib/Transform/MaximalStaticExpansion.cpp

308–309

It's a mistake from my side to compare it with UINT_MAX.

If I replace

std::numeric_limits<unsigned>::max()

with

std::numeric_limits<long>::max()

it should work on every platform, right ?

[Meinersbur]

lib/Transform/MaximalStaticExpansion.cpp

308–309

Except that it is stored into a std::vector<unsigned>. Storing a long into as an unsigned int may get you another overflow.

My suggestion is to stick with the lowest common maximum: std::numeric_limits<int>::max(). I don't think you would want to allocate memory larger than that anyway.

[niosega]

Take into account Michaels comments.
Update setNewAccessRelation call (isl::map as parameter instead of isl map * )

[Meinersbur]

LGTM.

Andreas, do you want to commit?

lib/Transform/MaximalStaticExpansion.cpp

309

Why - 1?

include/polly/LinkAllPasses.h

 llvm::Pass *createCodeGenerationPass();
 #ifdef GPU_CODEGEN
 llvm::Pass *createPPCGCodeGenerationPass(GPUArch Arch = GPUArch::NVPTX64,
                                          GPURuntime Runtime = GPURuntime::CUDA);
 #endif
 llvm::Pass *createIslScheduleOptimizerPass();
 llvm::Pass *createFlattenSchedulePass();
 llvm::Pass *createDeLICMPass();
+llvm::Pass *createMaximalStaticExpansionPass();
 
 extern char &CodePreparationID;
 } // namespace polly
 
 namespace {
 struct PollyForcePassLinking {
   PollyForcePassLinking() {
     // We must reference the passes in such a way that compilers will not
PollyForcePassLinking() {
     polly::createPollyCanonicalizePass();
     polly::createPolyhedralInfoPass();
     polly::createIslAstInfoWrapperPassPass();
     polly::createCodeGenerationPass();
 #ifdef GPU_CODEGEN
     polly::createPPCGCodeGenerationPass();
 #endif
     polly::createIslScheduleOptimizerPass();
+    polly::createMaximalStaticExpansionPass();
     polly::createFlattenSchedulePass();
     polly::createDeLICMPass();
     polly::createDumpModulePass("", true);
     polly::createSimplifyPass();
     polly::createPruneUnprofitablePass();
   }
 } PollyForcePassLinking; // Force link by creating a global definition.
 } // namespace
 
 namespace llvm {
 class PassRegistry;
 void initializeCodePreparationPass(llvm::PassRegistry &);
 void initializeDeadCodeElimPass(llvm::PassRegistry &);
 void initializeJSONExporterPass(llvm::PassRegistry &);
 void initializeJSONImporterPass(llvm::PassRegistry &);
 void initializeIslAstInfoWrapperPassPass(llvm::PassRegistry &);
 void initializeCodeGenerationPass(llvm::PassRegistry &);
 #ifdef GPU_CODEGEN
 void initializePPCGCodeGenerationPass(llvm::PassRegistry &);
 #endif
 void initializeIslScheduleOptimizerPass(llvm::PassRegistry &);
+void initializeMaximalStaticExpanderPass(llvm::PassRegistry &);
 void initializePollyCanonicalizePass(llvm::PassRegistry &);
 void initializeFlattenSchedulePass(llvm::PassRegistry &);
 void initializeDeLICMPass(llvm::PassRegistry &);
 } // namespace llvm
 
 #endif

lib/CMakeLists.txt

add_library(PollyCore OBJECT
   Transform/Canonicalization.cpp
   Transform/CodePreparation.cpp
   Transform/DeadCodeElimination.cpp
   Transform/ScheduleOptimizer.cpp
   Transform/FlattenSchedule.cpp
   Transform/FlattenAlgo.cpp
   Transform/DeLICM.cpp
   Transform/Simplify.cpp
+  Transform/MaximalStaticExpansion.cpp
   ${POLLY_HEADER_FILES}
   )
 set_target_properties(PollyCore PROPERTIES FOLDER "Polly")
 
 # Create the library that can be linked into LLVM's tools and Polly's unittests.
 # It depends on all library it needs, such that with
 # LLVM_POLLY_LINK_INTO_TOOLS=ON, its dependencies like PollyISL are linked as
 # well.

lib/Support/RegisterPasses.cpp

static cl::opt<polly::VectorizerChoice, true> Vectorizer(
     cl::location(PollyVectorizerChoice), cl::init(polly::VECTORIZER_NONE),
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool> ImportJScop(
     "polly-import",
     cl::desc("Import the polyhedral description of the detected Scops"),
     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<bool> FullyIndexedStaticExpansion(
+    "polly-mse",
+    cl::desc("Fully expand the memory accesses of the detected Scops"),
+    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
+
 static cl::opt<bool> ExportJScop(
     "polly-export",
     cl::desc("Export the polyhedral description of the detected Scops"),
     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool> DeadCodeElim("polly-run-dce",
                                   cl::desc("Run the dead code elimination"),
                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
#ifdef GPU_CODEGEN
   LLVMInitializeNVPTXAsmPrinter();
 #endif
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
   initializeDependenceInfoPass(Registry);
   initializeDependenceInfoWrapperPassPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
+  initializeMaximalStaticExpanderPass(Registry);
   initializeIslAstInfoWrapperPassPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializePolyhedralInfoPass(Registry);
   initializeScopDetectionWrapperPassPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
   initializeScopInfoWrapperPassPass(Registry);
   initializeCodegenCleanupPass(Registry);
void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
   if (EnableDeLICM)
     PM.add(polly::createDeLICMPass());
   if (EnableSimplify)
     PM.add(polly::createSimplifyPass());
 
   if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 
+  if (FullyIndexedStaticExpansion)
+    PM.add(polly::createMaximalStaticExpansionPass());
+
   if (DeadCodeElim)
     PM.add(polly::createDeadCodeElimPass());
 
   if (EnablePruneUnprofitable)
     PM.add(polly::createPruneUnprofitablePass());
 
 #ifdef GPU_CODEGEN
   if (Target == TARGET_HYBRID)

lib/Transform/MaximalStaticExpansion.cpp

+//===-  MaximalStaticExpansion.cpp - Expand the memory access -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass fully expand the memory accesses of a Scop to get rid of
+// dependencies.
+//===----------------------------------------------------------------------===//
+
+#include "polly/DependenceInfo.h"
+#include "polly/LinkAllPasses.h"
+#include "polly/Options.h"
+#include "polly/ScopInfo.h"
+#include "polly/Support/GICHelper.h"
+#include "polly/Support/ISLOStream.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+using namespace polly;
+
+namespace {
+class MaximalStaticExpander : public ScopPass {
+public:
+  static char ID;
+  explicit MaximalStaticExpander() : ScopPass(ID) {}
+
+  ~MaximalStaticExpander() {}
+
+  /// Expand the scalar write of the SCoP @p S.
+  bool runOnScop(Scop &S) override;
+
+  /// Print the new schedule for the SCoP @p S.
+  void printScop(raw_ostream &OS, Scop &S) const override;
+
+  /// Register all analyses and transformation required.
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+private:
+  bool expandWrite(Scop &S, MemoryAccess *MA);
+
+  bool expandRead(Scop &S);
+};
+} // namespace
+
+char MaximalStaticExpander::ID = 0;
+
+bool MaximalStaticExpander::expandRead(Scop &S) { return true; }
+
+bool MaximalStaticExpander::expandWrite(Scop &S, MemoryAccess *MA) {
+
+  // Get the current AM
+  isl_map *CurrentAccessMap = MA->getAccessRelation();
+
+  // Get in_dimension of the current AM
+  unsigned in_dimensions = isl_map_dim(CurrentAccessMap, isl_dim_in);
+
+  // Get domain from the current AM
+  auto Domain = isl_map_domain(CurrentAccessMap);
+
+  // Create a new AM from the domain
+  isl_map *NewAccessMap = isl_map_from_domain(Domain);
+
+  // Add dimensions to the new AM according to the current in_dim
+  // Fully indexed expansion
+  NewAccessMap = isl_map_add_dims(NewAccessMap, isl_dim_out, in_dimensions);
+
+  // Create the string representing the name of the new SAI
+  auto CurrentOutId = isl_map_get_tuple_id(CurrentAccessMap, isl_dim_out);
+  std::string CurrentOutIdString = MA->getScopArrayInfo()->getName() +
+                                   std::to_string(in_dimensions) + "_expanded";
+
+  // Set the tuple id for the out dimension
+  NewAccessMap = isl_map_set_tuple_id(NewAccessMap, isl_dim_out, CurrentOutId);
+
+  // Create the size vector
+  std::vector<const SCEV *> SCEVSizes;
+  auto ScopStmt = MA->getStatement();
+  for (unsigned i = 0; i < ScopStmt->getNumIterators(); i++) {
+    auto Loop = ScopStmt->getLoopForDimension(i);
+    auto SCEV = S.getSE()->getMaxBackedgeTakenCount(Loop);
+    SCEVSizes.push_back(SCEV);
+  }
+
+  // Get the ElementType of the current SAI
+  auto ElementType = MA->getOriginalScopArrayInfo()->getElementType();
+
+  // Create the new expanded SAI
+  auto ExpandedSAI =
+      S.getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
+                                 MemoryKind::Array, CurrentOutIdString.c_str());
+  ExpandedSAI->setIsOnHeap(true);
+
+  // Get the out Id of the expanded Array
+  isl_id *NewOutId = ExpandedSAI->getBasePtrId();
+
+  // Set the out id of the new AM to the new SAI out id
+  NewAccessMap = isl_map_set_tuple_id(NewAccessMap, isl_dim_out, NewOutId);
+
+  // Copy the isl_ids for the parameter dimensions to the new AM
+  for (unsigned i = 0; i < isl_map_dim(CurrentAccessMap, isl_dim_param); i++) {
+    isl_id *Id = isl_map_get_dim_id(CurrentAccessMap, isl_dim_param, i);
+    NewAccessMap = isl_map_set_dim_id(NewAccessMap, isl_dim_param, i, Id);
+  }
+
+  // Set the new access relation map
+  MA->setNewAccessRelation(NewAccessMap);
+
+  return true;
+}
+
+// For now, this pass is just expanding the write access of scalar.
+// For instance, the folowing code :
+//
+// for(int i = 0; i<N; i++)
+//   for(int j = 0; j<N; j++)
+//     tmp = A[i]*tmp;
+//
+// is transformed to :
+//
+// for(int i = 0; i<N; i++)
+//   for(int j = 0; j<N; j++)
+//     tmp[i, j] = A[i]*tmp;
+//
+bool MaximalStaticExpander::runOnScop(Scop &S) {
+  bool CorrectWrite;
+  bool CorrectRead;
+  for (ScopStmt &Stmt : S) {
+    for (MemoryAccess *MA : Stmt) {
+      if (MA->isWrite()) {
+        CorrectWrite = expandWrite(S, MA);
+        if (!CorrectWrite) {
+          return false;
+        }
+      } else if (MA->isRead()) {
+        CorrectRead = expandRead(S);
+        if (!CorrectRead) {
+          return false;
+        }
+      }
+    }
+  }
+  return true;
+}
+
+void MaximalStaticExpander::printScop(raw_ostream &OS, Scop &S) const {
+  S.dump();
+}
+
+void MaximalStaticExpander::getAnalysisUsage(AnalysisUsage &AU) const {
+  ScopPass::getAnalysisUsage(AU);
+}
+
+Pass *polly::createMaximalStaticExpansionPass() {
+  return new MaximalStaticExpander();
+}
+
+INITIALIZE_PASS_BEGIN(MaximalStaticExpander, "polly-opt-mse",
+                      "Polly - Maximal static expansion of SCoP", false, false);
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
+INITIALIZE_PASS_END(MaximalStaticExpander, "polly-opt-mse",
+                    "Polly - Maximal static expansion of SCoP", false, false)

test/MaximalStaticExpansion/mse___%for.cond1.preheader---%for.end8.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_B",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%for.cond1.preheader---%for.end8",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_for_cond1_preheader[i0] -> MemRef_tmp_04__phi[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_cond1_preheader[i0] -> MemRef_tmp_11__phi[] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_cond1_preheader[i0] : 0 <= i0 <= 1999 }",
+         "name" : "Stmt_for_cond1_preheader",
+         "schedule" : "{ Stmt_for_cond1_preheader[i0] -> [i0, 0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_tmp_11__phi[] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_tmp_11__phi[] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_B[1 + i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_mul_lcssa__phi[] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_body3[i0, i1] : 0 <= i0 <= 1999 and 0 <= i1 <= 1999 }",
+         "name" : "Stmt_for_body3",
+         "schedule" : "{ Stmt_for_body3[i0, i1] -> [i0, 1, i1] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_inc6[i0] -> MemRef_tmp_04__phi[] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_for_inc6[i0] -> MemRef_mul_lcssa__phi[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_inc6[i0] -> MemRef_mul_lcssa[] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_inc6[i0] : 0 <= i0 <= 1999 }",
+         "name" : "Stmt_for_inc6",
+         "schedule" : "{ Stmt_for_inc6[i0] -> [i0, 2, 0] }"
+      }
+   ]
+}

test/MaximalStaticExpansion/write_accesses_expanded.ll

+; RUN: opt -polly-canonicalize %loadPolly -analyze -polly-opt-mse < %s 2>&1 >/dev/null | FileCheck %s 
+;
+; Verify that the write access are correctly expanded
+;
+; Original source code :
+;
+; #define Ni 2000
+; #define Nj 3000
+;
+; double mse(double A[Ni], double B[Nj]) {
+;   int i;
+;   double tmp = 2;
+;   for (i = 0; i < Ni; i++) {
+;     for (int j = 0; j<Nj; j++) {
+;       tmp = A[i]*tmp;
+;       B[i+1] = tmp;
+;     }
+;  }
+;   return tmp;
+; }
+;
+; Check if the expanded SAI are created
+;
+; CHECK: double MemRef_tmp_11__phi1_expanded[1999]; // Element size 8
+; CHECK: double MemRef_tmp_11__phi2_expanded[1999][2999]; // Element size 8
+; CHECK: double MemRef_B2_expanded[1999][2999]; // Element size 8
+; CHECK: double MemRef_mul_lcssa__phi2_expanded[1999][2999]; // Element size 8
+; CHECK: double MemRef_tmp_04__phi1_expanded[1999]; // Element size 8
+; CHECK: double MemRef_mul_lcssa1_expanded[1999]; // Element size 8
+;
+; Check if the memory accesses are modified
+;
+; CHECK: new: { Stmt_for_cond1_preheader[i0] -> MemRef_tmp_11__phi1_expanded[o0] };
+; CHECK: new: { Stmt_for_body3[i0, i1] -> MemRef_tmp_11__phi2_expanded[o0, o1] };
+; CHECK: new: { Stmt_for_body3[i0, i1] -> MemRef_B2_expanded[o0, o1] };
+; CHECK: new: { Stmt_for_body3[i0, i1] -> MemRef_mul_lcssa__phi2_expanded[o0, o1] };
+; CHECK: new: { Stmt_for_inc6[i0] -> MemRef_tmp_04__phi1_expanded[o0] };
+; CHECK: new: { Stmt_for_inc6[i0] -> MemRef_mul_lcssa1_expanded[o0] };
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline nounwind uwtable
+define double @mse(double* %A, double* %B) {
+entry:
+  %A.addr = alloca double*, align 8
+  %B.addr = alloca double*, align 8
+  %i = alloca i32, align 4
+  %tmp = alloca double, align 8
+  %j = alloca i32, align 4
+  store double* %A, double** %A.addr, align 8
+  store double* %B, double** %B.addr, align 8
+  store double 2.000000e+00, double* %tmp, align 8
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc6, %entry
+  %0 = load i32, i32* %i, align 4
+  %cmp = icmp slt i32 %0, 2000
+  br i1 %cmp, label %for.body, label %for.end8
+
+for.body:                                         ; preds = %for.cond
+  store i32 0, i32* %j, align 4
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %1 = load i32, i32* %j, align 4
+  %cmp2 = icmp slt i32 %1, 3000
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %2 = load double*, double** %A.addr, align 8
+  %3 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %3 to i64
+  %arrayidx = getelementptr inbounds double, double* %2, i64 %idxprom
+  %4 = load double, double* %arrayidx, align 8
+  %5 = load double, double* %tmp, align 8
+  %mul = fmul double %4, %5
+  store double %mul, double* %tmp, align 8
+  %6 = load double, double* %tmp, align 8
+  %7 = load double*, double** %B.addr, align 8
+  %8 = load i32, i32* %i, align 4
+  %add = add nsw i32 %8, 1
+  %idxprom4 = sext i32 %add to i64
+  %arrayidx5 = getelementptr inbounds double, double* %7, i64 %idxprom4
+  store double %6, double* %arrayidx5, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %9 = load i32, i32* %j, align 4
+  %inc = add nsw i32 %9, 1
+  store i32 %inc, i32* %j, align 4
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc6
+
+for.inc6:                                         ; preds = %for.end
+  %10 = load i32, i32* %i, align 4
+  %inc7 = add nsw i32 %10, 1
+  store i32 %inc7, i32* %i, align 4
+  br label %for.cond
+
+for.end8:                                         ; preds = %for.cond
+  %11 = load double, double* %tmp, align 8
+  ret double %11
+}