[GSoC 2016][Polly][WIP] Extend the jscop interface to allow the user to declare new arrays and to reference these arrays from access expressions

[gareevroman]

Summary

Extend the jscop interface to allow the user to export arrays. It is required that already existing arrays of the list of arrays correspond to arrays of the SCoP. Each array that is appended to the list will be newly created. Furthermore, we allow the user to modify access expressions to reference any array in case it has the same element type.

[gareevroman]

This is a draft of the path. I think that it has at least the following drawbacks:

1. Type of elements of newly created array is always double, even though it's different according to the extended jscop interface.

If I'm not mistaken, types of elements are represented by primitive types. Should we store their textual representation in JSONExporter to be able to map them to actual types?

2. Type of dimension sizes of newly created arrays is always Int64.

I haven't understood yet how to properly get the type of dimension sizes in the JSONExporter.

3. Dimensions of exported arrays are dimensions of ScopArrayInfos even though actual arrays have a smaller number of dimensions.

Should we try to understand whether new dimensions were introduced during delinearization?

I would be grateful for your comments and ideas.

[grosser]

In D22828#496463, @gareevroman wrote:

This is a draft of the path. I think that it has at least the following drawbacks:

1. Type of elements of newly created array is always double, even though it's different according to the extended jscop interface.

If I'm not mistaken, types of elements are represented by primitive types. Should we store their textual representation in JSONExporter to be able to map them to actual types?

We could, yes.

2. Type of dimension sizes of newly created arrays is always Int64.

I haven't understood yet how to properly get the type of dimension sizes in the JSONExporter.

Which type. The type of the SCEVs given to getOrCreateScopArrayInfo. I believe they can have any (large enough) type. 64 bit should be fine.

3. Dimensions of exported arrays are dimensions of ScopArrayInfos even though actual arrays have a smaller number of dimensions.

Should we try to understand whether new dimensions were introduced during delinearization?

We want to export our model, so we should just export what -polly-scops -analyze prints.

Best,
Tobias

include/polly/ScopInfo.h

2164 ↗

(On Diff #65569)

Maybe call it createScopArrayInfo() to show that this function does the same as the function above.

lib/Analysis/ScopInfo.cpp

246 ↗

(On Diff #65569)

I would prefer to not change the name, but to (optionally) set it when constructing the array.

3517 ↗

(On Diff #65569)

Both cases do exactly the same. This seems wrong?

Do you want to do something like, then you don't even need the ArrayType variable and the condition:

for () {

   ElementType = ArrayType::get(ElementType, ....)

3521 ↗

(On Diff #65569)

getTerminatorInst();

3522 ↗

(On Diff #65569)

Please do not yet touch the IR here. I would prefer to just mark this ScopArrayInfo as 'virtual', e.g. by not having a baseptr and then generating the corresponding IR only in lib/Codegen/CodeGeneration.cpp.

lib/Exchange/JSONExporter.cpp

103 ↗

(On Diff #65569)

This should probably say the new arrays.

336 ↗

(On Diff #65569)

This could fit in polly::Scop

375 ↗

(On Diff #65569)

ScopArrayInfo should have a getId method already.

496 ↗

(On Diff #65569)

http://www.cplusplus.com/reference/string/string/compare/

522 ↗

(On Diff #65569)

Parsing the type is a good idea. Alternatively you could just export the size of the element type and always create an iX of the correct size. (Polly will always cast to the right type for actual memory accesses).

test/ScopInfo/create_arrays.ll

23 ↗

(On Diff #65569)

This is complicated. Could you use a trivial example that just tests this functionality.
In fact, multiple examples that cover the different types, multi-dimensional arrays, ....

Also, please move this into test/Isl/CodeGen/MemAccess/ and add a code-generation test case as well.

test/ScopInfo/kernel_gemm___%bb8---%bb32.jscop

1 ↗

(On Diff #65569)

Please save the original file as .jscop and the transformed file as .jscop.transformed

[mreisinger]

lib/Analysis/ScopInfo.cpp

3508 ↗

(On Diff #65569)

I would say llvm:: can be omitted here since the surrounding uses of Type are unqualified too.

[Meinersbur]

lib/Exchange/JSONExporter.cpp

496 ↗

(On Diff #65569)

RawStringOstream.str() == Array["type"].asString()

523 ↗

(On Diff #65569)

for (;ArrayIdx < Arrays.size(); ArrayIdx+=1)
You might also consider
for (int i = ArrayIdx, End = Arrays.size(); i < End; i+=1)
as the more canonical form.

[gareevroman]

Thanks for the comments! I've tried to address them in this version of the patch.

[gareevroman]

lib/Analysis/ScopInfo.cpp

3511 ↗

(On Diff #65781)

Thanks. The else branch should contain 'ArrayType = ArrayType::get(ArrayType, Sizes.at(Sizes.size() - i - 1));'.

3516 ↗

(On Diff #65781)

Should we rewrite the Scop::getOrCreateScopArrayInfo so it creates a new ScopArrayInfo in case the baseptr is nullptr? Otherwise, it probably always returns the same object.

lib/Exchange/JSONExporter.cpp

512 ↗

(On Diff #65781)

I think that textual representation of types is more intuitive. I've implemented its parsing in the last version of the patch using std::map. However, I'm not sure whether it is appropriate to initialize such a map in a function, where this map is used. What do you think about it?

I have one more question. Should we use StringMap instead of std::map?

[grosser]

Hi Roman, thank you for the update. This clearly goes in the right direction. I added a couple more comments.

Tobias

lib/Analysis/ScopInfo.cpp

3511 ↗

(On Diff #65781)

The bug is fixed, but the code still looks unnecessarily complicated what about:

	​    if (!ArrayType)
               ArrayType = ElementType;

	​    ArrayType = ArrayType::get(ArrayType, Sizes.at(Sizes.size() - i - 1));

3516 ↗

(On Diff #65781)

That seems to make sense, yes. This means we need to keep keep the list of ScopArrayInfo objects in one set and then have a separate map that contains references to map from baseptrs to scoparrayInfo objects that have baseptrs.

lib/Exchange/JSONExporter.cpp

512 ↗

(On Diff #65781)

I am fine with a std::map. This is certainly not performance critical at the moment. I also think it is fine to initialize this in the function. The alternative would be to make this a global variable. This would speed up this very function, but slow down the startup of clang/opt as the map would always need to be initialized. Alternatively, you could make this a sorted array that is only contains strings and function pointers, and just do a binary search over the strings. This is probably the optimal solution in terms of speed, but as we use jscop currently just as a driver for our test cases compile time speed is not so important. Hence, I suggest to go for what you believe is the approach easiest to undertstand.

(We could also use parseType() from AsmParser/Parser.h, but this is only OK if opt, clang and bugpoint all link the AsmParser in already)

test/Isl/CodeGen/MemAccess/create_arrays.ll

21 ↗

(On Diff #65781)

This already looks very good. Two recommendations:

1. It would be great to make this test case really trivial. A single loop with a couple of memory accesses. Then introduce different accesses 1D/2D with different types to ensure the new code is really exercised. This large test case is useful for your GSoC overall goal, but it is larger than necessary for this patch. Also the access functions are unnecessarily complicated.

2. Use array name A/B/C or A1/A2/A3. This is easier to read.

test/Isl/CodeGen/MemAccess/create_arrays___%bb8---%bb32.jscop.transformed

82 ↗

(On Diff #65781)

If there is a benefit in these more complex test cases, please add a comment that states what additional functionality they exercise.

[gareevroman]

Hi Tobias,

thanks for the comments and quick replies!

lib/Exchange/JSONExporter.cpp

513 ↗

(On Diff #66003)

OK. Thanks for the explanation.

[grosser]

Hi Roman,

thanks for the update!

include/polly/ScopInfo.h

1403 ↗

(On Diff #66003)

I would make this a plain pointer and use a unique_ptr to track ownership in ScopArrayInfoSet

Also, you can make this a normal Map (without vector), as we won't iterate over this Map any more (instead we use the vector which contains _all_ arrays).

1415 ↗

(On Diff #66003)

Why do we need a special compare function? The automatically derived comparision that checks for pointer equality and different integers in the second element of the pair should be enough, no?

1418 ↗

(On Diff #66003)

Make this a SetVector, otherwise the iteration order is not clear.

lib/Analysis/ScopInfo.cpp

3493 ↗

(On Diff #66003)

Can BaseName and BasePtr ever be set both? If not, please add an assert and document this.

3498 ↗

(On Diff #66003)

Uff, this is rather involved. You make these arrays comparable via strings to support the case that we want to get back a ScopArrayInfo reference from its string name. As we probably need to support this, I would suggest to make this more explicit using a MapVector from std::string to ScopArrayInfo.

3499 ↗

(On Diff #66003)

BasePtr seems is nullptr here, right? In this case, I do not think it makes sense to add the ScopArrayInfo into this map, as all of the new arrays will overwrite each other, no?

lib/CodeGen/CodeGeneration.cpp

151 ↗

(On Diff #66003)

Can you make this part of IslNodeBuilder. CodeGeneration.cpp is just one user of the IslNodeBuilder (PPCGCodeGeneration is another and there may be more external ones).

156 ↗

(On Diff #66003)

I suggest to move this further down to the area where we actually generate code. Maybe before NodeBuilder.addParameters()?

test/Isl/CodeGen/MemAccess/create_arrays.ll

22 ↗

(On Diff #66003)

Nice.

[gareevroman]

include/polly/ScopInfo.h

1415 ↗

(On Diff #66003)

Yes, I added it to make these arrays comparable via strings.

1418 ↗

(On Diff #66003)

We preserve the order to be able to check that a SCoP contains arrays that we expect. Right?

lib/Analysis/ScopInfo.cpp

3493 ↗

(On Diff #66003)

I thought that it's redundant, but it isn't a mistake. OK. I'll add an assert.

3498 ↗

(On Diff #66003)

Maybe we should store all created arrays in a separate map. What do you think about it? Although it probably requires additional methods to get a new iterator range, it should possibly make maintenance of created arrays easier.

P.S.: I get the following compilation error, if I try to declare 'MapVector<std::string, std::unique_ptr<ScopArrayInfo>> ScopArrayInfoSet2;'. Possibly it doesn't suite for storing std::string.

"In file included from /home/roman/Documents/polly/llvm/include/llvm/Analysis/AliasSetTracker.h:20:0,

from /home/roman/Documents/polly/llvm/tools/polly/include/polly/ScopDetectionDiagnostic.h:26,
from /home/roman/Documents/polly/llvm/tools/polly/include/polly/ScopDetection.h:50,
from /home/roman/Documents/polly/llvm/tools/polly/include/polly/ScopInfo.h:21,
from /home/roman/Documents/polly/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:20:

/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h: In instantiation of ‘void llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::destroyAll() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’:
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:617:5: required from ‘llvm::DenseMap<KeyT, ValueT, KeyInfoT, BucketT>::~DenseMap() [with KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’
/home/roman/Documents/polly/llvm/include/llvm/ADT/MapVector.h:32:7: required from here
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:308:57: error: ‘isEqual’ is not a member of ‘llvm::DenseMapInfo<std::basic_string<char> >’

!KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
                                              ^

/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:307:53: error: ‘isEqual’ is not a member of ‘llvm::DenseMapInfo<std::basic_string<char> >’

if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
                                              ^

/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h: In instantiation of ‘static const KeyT llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::getEmptyKey() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’:
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:305:39: required from ‘void llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::destroyAll() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:617:5: required from ‘llvm::DenseMap<KeyT, ValueT, KeyInfoT, BucketT>::~DenseMap() [with KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’
/home/roman/Documents/polly/llvm/include/llvm/ADT/MapVector.h:32:7: required from here
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:392:34: error: ‘getEmptyKey’ is not a member of ‘llvm::DenseMapInfo<std::basic_string<char> >’

return KeyInfoT::getEmptyKey();
                             ^

/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h: In instantiation of ‘static const KeyT llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::getTombstoneKey() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’:
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:305:73: required from ‘void llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::destroyAll() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:617:5: required from ‘llvm::DenseMap<KeyT, ValueT, KeyInfoT, BucketT>::~DenseMap() [with KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’
/home/roman/Documents/polly/llvm/include/llvm/ADT/MapVector.h:32:7: required from here
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:395:38: error: ‘getTombstoneKey’ is not a member of ‘llvm::DenseMapInfo<std::basic_string<char> >’

return KeyInfoT::getTombstoneKey();
                                 ^

[100%] Generating LLVMLTORevision.h
[100%] Built target LLVMInterpreter
[100%] Built target LLVMAArch64CodeGen
[100%] Built target LLVMAMDGPUCodeGen
[100%] Built target LLVMBPFCodeGen
[100%] Built target LLVMARMCodeGen
[100%] Built target LLVMMSP430CodeGen
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h: In static member function ‘static const KeyT llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::getEmptyKey() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’:
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:393:3: warning: control reaches end of non-void function [-Wreturn-type]

}
^

/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h: In static member function ‘static const KeyT llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::getTombstoneKey() [with DerivedT = llvm::DenseMap<std::basic_string<char>, unsigned int, llvm::DenseMapInfo<std::basic_string<char> >, llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int> >; KeyT = std::basic_string<char>; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo<std::basic_string<char> >; BucketT = llvm::detail::DenseMapPair<std::basic_string<char>, unsigned int>]’:
/home/roman/Documents/polly/llvm/include/llvm/ADT/DenseMap.h:396:3: warning: control reaches end of non-void function [-Wreturn-type]

}"

3499 ↗

(On Diff #66003)

Right.

lib/CodeGen/CodeGeneration.cpp

151 ↗

(On Diff #66003)

OK.

156 ↗

(On Diff #66003)

OK.

[grosser]

Brief comments.

include/polly/ScopInfo.h

1415 ↗

(On Diff #66003)

Right. I personally would prefer to leave SAI comparable via Pointers and use a map from strings to SAI to find the correct SAI for a given string.

1418 ↗

(On Diff #66003)

By using a set vector we ensure a deterministic order when enumerating the elements in this set. This is important to ensure that the order in which you create AllocaInstructions is deterministic and does _not_ depend on the memory allocator on which Polly runs. Otherwise, test case outputs may change between systems or even on the same system.

lib/Analysis/ScopInfo.cpp

3498 ↗

(On Diff #66003)

I would prefer to keep a single set that has ownership of all SAI.

Maybe you could use a StringMap to go from StringToSAI, and a separate std::SetVector to keep ownership of the set of SAI available..

[gareevroman]

I would make this a plain pointer and use a unique_ptr to track ownership in ScopArrayInfoSet

Since we want to use the MapVector, we should probably use plain pointers instead of a unique_ptrs. Otherwise, we get an error that is similar to the one caused by using std::string as a type of its keys.

Maybe we should use a unique_ptr to track ownership in ScopArrayInfoMap and ScopArrayNameMap?

P.S. I generate alloca in split blocks, because after their creation in executeScopConditionally getEnteringBlock returns a pointer to such a block. It seems that they are suitable for us, because, if I'm not mistaken, they are predecessors of SCoPs.

[grosser]

LGTM. Can you please test with POLLY_GPGPU enabled in cmake. If that passes, feel free to commit.

include/polly/CodeGen/IslNodeBuilder.h

58 ↗

(On Diff #66140)

For all NEW arrays ...

lib/CodeGen/BlockGenerators.cpp

490 ↗

(On Diff #66140)

Nice.

[grosser]

lib/CodeGen/IslNodeBuilder.cpp

1178 ↗

(On Diff #66140)

Just realized. This is not correct. Use Builder.GetCurrentBlock()->getParent()->getEntry();

Otherwise, if there is a loop around the scop, we will run out of stack space.

[gareevroman]

lib/CodeGen/IslNodeBuilder.cpp

1178 ↗

(On Diff #66140)

I get the following error:

"error: ‘polly::PollyIRBuilder’ has no member named ‘GetCurrentBlock’"

If I'm not mistaken, IRBuilder doesn't have methods that return basic blocks.

[gareevroman]

I get the following error:

"error: ‘polly::PollyIRBuilder’ has no member named ‘GetCurrentBlock’"

If I'm not mistaken, IRBuilder doesn't have methods that return basic
blocks.

GetInsertBlock()

OK. Thanks for the comment!

P.S.: I've also updated access to arrays of SCoPs from CodeGen/PPCGCodegGeneration.cpp. Please revert the patch, if it's wrong. The last version of the patch passes tests with POLLY_GPGPU enabled and doesn't cause a regression in case of tests from the LNT test suite.

polly/trunk/include/polly/CodeGen/IslNodeBuilder.h

IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  &ExprBuilder),
         RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {}
 
   virtual ~IslNodeBuilder() {}
 
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
 
+  /// @brief Allocate memory for all new arrays created by Polly.
+  void allocateNewArrays();
+
   /// @brief Preload all memory loads that are invariant.
   bool preloadInvariantLoads();
 
   /// @brief Finalize code generation.
   ///
   /// @see BlockGenerator::finalizeSCoP(Scop &S)
   virtual void finalize() { BlockGen.finalizeSCoP(S); }
 

polly/trunk/include/polly/ScopInfo.h

public:
   ///
   /// @param BasePtr        The array base pointer.
   /// @param ElementType    The type of the elements stored in the array.
   /// @param IslCtx         The isl context used to create the base pointer id.
   /// @param DimensionSizes A vector containing the size of each dimension.
   /// @param Kind           The kind of the array object.
   /// @param DL             The data layout of the module.
   /// @param S              The scop this array object belongs to.
+  /// @param BaseName       The optional name of this memory reference.
   ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *IslCtx,
                 ArrayRef<const SCEV *> DimensionSizes, enum MemoryKind Kind,
-                const DataLayout &DL, Scop *S);
+                const DataLayout &DL, Scop *S, const char *BaseName = nullptr);
 
   ///  @brief Update the element type of the ScopArrayInfo object.
   ///
   ///  Memory accesses referencing this ScopArrayInfo object may use
   ///  different element sizes. This function ensures the canonical element type
   ///  stored is small enough to model accesses to the current element type as
   ///  well as to @p NewElementType.
   ///
private:
   DenseMap<BasicBlock *, isl_set *> DomainMap;
 
   /// Constraints on parameters.
   isl_set *Context;
 
   /// @brief The affinator used to translate SCEVs to isl expressions.
   SCEVAffinator Affinator;
 
-  typedef MapVector<std::pair<AssertingVH<const Value>, int>,
-                    std::unique_ptr<ScopArrayInfo>>
+  typedef std::map<std::pair<AssertingVH<const Value>, int>,
       ArrayInfoMapTy;
+
+  typedef StringMap<std::unique_ptr<ScopArrayInfo>> ArrayNameMapTy;
+
+  typedef SetVector<ScopArrayInfo *> ArrayInfoSetTy;
+
   /// @brief A map to remember ScopArrayInfo objects for all base pointers.
   ///
   /// As PHI nodes may have two array info objects associated, we add a flag
   /// that distinguishes between the PHI node specific ArrayInfo object
   /// and the normal one.
   ArrayInfoMapTy ScopArrayInfoMap;
 
+  /// @brief A map to remember ScopArrayInfo objects for all names of memory
+  ///        references.
+  ArrayNameMapTy ScopArrayNameMap;
+
+  /// @brief A set to remember ScopArrayInfo objects.
+  /// @see Scop::ScopArrayInfoMap
+  ArrayInfoSetTy ScopArrayInfoSet;
+
   /// @brief The assumptions under which this scop was built.
   ///
   /// When constructing a scop sometimes the exact representation of a statement
   /// or condition would be very complex, but there is a common case which is a
   /// lot simpler, but which is only valid under certain assumptions. The
   /// assumed context records the assumptions taken during the construction of
   /// this scop and that need to be code generated as a run-time test.
   isl_set *AssumedContext;
public:
 
   /// @brief Take a list of parameters and add the new ones to the scop.
   void addParams(const ParameterSetTy &NewParameters);
 
   /// @brief Return whether this scop is empty, i.e. contains no statements that
   /// could be executed.
   bool isEmpty() const { return Stmts.empty(); }
 
-  typedef ArrayInfoMapTy::iterator array_iterator;
-  typedef ArrayInfoMapTy::const_iterator const_array_iterator;
-  typedef iterator_range<ArrayInfoMapTy::iterator> array_range;
-  typedef iterator_range<ArrayInfoMapTy::const_iterator> const_array_range;
+  typedef ArrayInfoSetTy::iterator array_iterator;
+  typedef ArrayInfoSetTy::const_iterator const_array_iterator;
+  typedef iterator_range<ArrayInfoSetTy::iterator> array_range;
+  typedef iterator_range<ArrayInfoSetTy::const_iterator> const_array_range;
 
-  inline array_iterator array_begin() { return ScopArrayInfoMap.begin(); }
+  inline array_iterator array_begin() { return ScopArrayInfoSet.begin(); }
 
-  inline array_iterator array_end() { return ScopArrayInfoMap.end(); }
+  inline array_iterator array_end() { return ScopArrayInfoSet.end(); }
 
   inline const_array_iterator array_begin() const {
-    return ScopArrayInfoMap.begin();
+    return ScopArrayInfoSet.begin();
   }
 
   inline const_array_iterator array_end() const {
-    return ScopArrayInfoMap.end();
+    return ScopArrayInfoSet.end();
   }
 
   inline array_range arrays() {
     return array_range(array_begin(), array_end());
   }
 
   inline const_array_range arrays() const {
     return const_array_range(array_begin(), array_end());
public:
   }
 
   const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; }
 
   /// @brief Return the (possibly new) ScopArrayInfo object for @p Access.
   ///
   /// @param ElementType The type of the elements stored in this array.
   /// @param Kind        The kind of the array info object.
+  /// @param BaseName    The optional name of this memory reference.
   const ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr,
                                                 Type *ElementType,
                                                 ArrayRef<const SCEV *> Sizes,
-                                                ScopArrayInfo::MemoryKind Kind);
+                                                ScopArrayInfo::MemoryKind Kind,
+                                                const char *BaseName = nullptr);
+
+  /// @brief Create an array and return the corresponding ScopArrayInfo object.
+  ///
+  /// @param ElementType The type of the elements stored in this array.
+  /// @param BaseName    The name of this memory reference.
+  /// @param Sizes       The sizes of dimensions.
+  const ScopArrayInfo *createScopArrayInfo(Type *ElementType,
+                                           const std::string &BaseName,
+                                           const std::vector<unsigned> &Sizes);
 
   /// @brief Return the cached ScopArrayInfo object for @p BasePtr.
   ///
   /// @param BasePtr   The base pointer the object has been stored for.
   /// @param Kind      The kind of array info object.
   const ScopArrayInfo *getScopArrayInfo(Value *BasePtr,
                                         ScopArrayInfo::MemoryKind Kind);
 
   /// @brief Invalidate ScopArrayInfo object for base address.
   ///
   /// @param BasePtr The base pointer of the ScopArrayInfo object to invalidate.
   /// @param Kind    The Kind of the ScopArrayInfo object.
   void invalidateScopArrayInfo(Value *BasePtr, ScopArrayInfo::MemoryKind Kind) {
-    ScopArrayInfoMap.erase(std::make_pair(BasePtr, Kind));
+    auto It = ScopArrayInfoMap.find(std::make_pair(BasePtr, Kind));
+    if (It == ScopArrayInfoMap.end())
+      return;
+    ScopArrayInfoSet.remove(It->second.get());
+    ScopArrayInfoMap.erase(It);
   }
 
   void setContext(isl_set *NewContext);
 
   /// @brief Align the parameters in the statement to the scop context
   void realignParams();
 
   /// @brief Return true if this SCoP can be profitably optimized.
public:
 
   /// @brief Get the depth of a loop relative to the outermost loop in the Scop.
   ///
   /// This will return
   ///    0 if @p L is an outermost loop in the SCoP
   ///   >0 for other loops in the SCoP
   ///   -1 if @p L is nullptr or there is no outermost loop in the SCoP
   int getRelativeLoopDepth(const Loop *L) const;
+
+  /// @brief Find the ScopArrayInfo associated with an isl Id
+  ///        that has name @p Name.
+  ScopArrayInfo *getArrayInfoByName(const std::string BaseName);
 };
 
 /// @brief Print Scop scop to raw_ostream O.
 static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
   scop.print(O);
   return O;
 }
 

polly/trunk/lib/Analysis/ScopInfo.cpp

if (!OriginBaseSCEVUnknown)
     return nullptr;
 
   return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
                              ScopArrayInfo::MK_Array);
 }
 
 ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx,
                              ArrayRef<const SCEV *> Sizes, enum MemoryKind Kind,
-                             const DataLayout &DL, Scop *S)
+                             const DataLayout &DL, Scop *S,
+                             const char *BaseName)
     : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
   std::string BasePtrName =
-      getIslCompatibleName("MemRef_", BasePtr, Kind == MK_PHI ? "__phi" : "");
+      BaseName ? BaseName : getIslCompatibleName("MemRef_", BasePtr,
+                                                 Kind == MK_PHI ? "__phi" : "");
   Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
 
   updateSizes(Sizes);
+
+  if (!BasePtr) {
+    BasePtrOriginSAI = nullptr;
+    return;
+  }
+
   BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
   if (BasePtrOriginSAI)
     const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
 }
 
 __isl_give isl_space *ScopArrayInfo::getSpace() const {
   auto *Space =
       isl_space_set_alloc(isl_id_get_ctx(Id), 0, getNumberOfDimensions());
Scop::~Scop() {
   }
 
   for (const auto &IAClass : InvariantEquivClasses)
     isl_set_free(IAClass.ExecutionContext);
 
   // Explicitly release all Scop objects and the underlying isl objects before
   // we relase the isl context.
   Stmts.clear();
+  ScopArrayInfoSet.clear();
   ScopArrayInfoMap.clear();
+  ScopArrayNameMap.clear();
   AccFuncMap.clear();
 }
 
 void Scop::updateAccessDimensionality() {
   // Check all array accesses for each base pointer and find a (virtual) element
   // size for the base pointer that divides all access functions.
   for (auto &Stmt : *this)
     for (auto *Access : Stmt) {
for (ScopStmt &Stmt : *this) {
     // Transfer the memory access from the statement to the SCoP.
     for (auto InvMA : InvariantAccesses)
       Stmt.removeMemoryAccess(InvMA.MA);
     addInvariantLoads(Stmt, InvariantAccesses);
   }
   isl_union_map_free(Writes);
 }
 
-const ScopArrayInfo *
-Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
-                               ArrayRef<const SCEV *> Sizes,
-                               ScopArrayInfo::MemoryKind Kind) {
-  auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)];
+const ScopArrayInfo *Scop::getOrCreateScopArrayInfo(
+    Value *BasePtr, Type *ElementType, ArrayRef<const SCEV *> Sizes,
+    ScopArrayInfo::MemoryKind Kind, const char *BaseName) {
+  assert((BasePtr || BaseName) &&
+         "BasePtr and BaseName can not be nullptr at the same time.");
+  assert(!(BasePtr && BaseName) && "BaseName is redundant.");
+  auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]
+                      : ScopArrayNameMap[BaseName];
   if (!SAI) {
     auto &DL = getFunction().getParent()->getDataLayout();
     SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
-                                DL, this));
+                                DL, this, BaseName));
+    ScopArrayInfoSet.insert(SAI.get());
   } else {
     SAI->updateElementType(ElementType);
     // In case of mismatching array sizes, we bail out by setting the run-time
     // context to false.
     if (!SAI->updateSizes(Sizes))
       invalidate(DELINEARIZATION, DebugLoc());
   }
   return SAI.get();
 }
 
+const ScopArrayInfo *
+Scop::createScopArrayInfo(Type *ElementType, const std::string &BaseName,
+                          const std::vector<unsigned> &Sizes) {
+  auto *DimSizeType = Type::getInt64Ty(getSE()->getContext());
+  std::vector<const SCEV *> SCEVSizes;
+
+  for (auto size : Sizes)
+    SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));
+
+  auto *SAI =
+      getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
+                               ScopArrayInfo::MK_Array, BaseName.c_str());
+  return SAI;
+}
+
 const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr,
                                             ScopArrayInfo::MemoryKind Kind) {
   auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
   assert(SAI && "No ScopArrayInfo available for this base pointer");
   return SAI;
 }
 
 std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
void Scop::printStatements(raw_ostream &OS) const {
 
   OS.indent(4) << "}\n";
 }
 
 void Scop::printArrayInfo(raw_ostream &OS) const {
   OS << "Arrays {\n";
 
   for (auto &Array : arrays())
-    Array.second->print(OS);
+    Array->print(OS);
 
   OS.indent(4) << "}\n";
 
   OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
 
   for (auto &Array : arrays())
-    Array.second->print(OS, /* SizeAsPwAff */ true);
+    Array->print(OS, /* SizeAsPwAff */ true);
 
   OS.indent(4) << "}\n";
 }
 
 void Scop::print(raw_ostream &OS) const {
   OS.indent(4) << "Function: " << getFunction().getName() << "\n";
   OS.indent(4) << "Region: " << getNameStr() << "\n";
   OS.indent(4) << "Max Loop Depth:  " << getMaxLoopDepth() << "\n";

 int Scop::getRelativeLoopDepth(const Loop *L) const {
   Loop *OuterLoop =
       L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
   if (!OuterLoop)
     return -1;
   return L->getLoopDepth() - OuterLoop->getLoopDepth();
 }
 
+ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {
+  for (auto &SAI : arrays()) {
+    if (SAI->getName() == BaseName)
+      return SAI;
+  }
+  return nullptr;
+}
+
 //===----------------------------------------------------------------------===//
 void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetection>();
   AU.addRequired<AAResultsWrapperPass>();

polly/trunk/lib/CodeGen/BlockGenerators.cpp

void BlockGenerator::createScalarInitialization(Scop &S) {
 
   // Get the start block of the __optimized__ region.
   BasicBlock *StartBB = SplitBBTerm->getSuccessor(0);
   if (StartBB == S.getEntry())
     StartBB = SplitBBTerm->getSuccessor(1);
 
   Builder.SetInsertPoint(StartBB->getTerminator());
 
-  for (auto &Pair : S.arrays()) {
-    auto &Array = Pair.second;
+  for (auto &Array : S.arrays()) {
     if (Array->getNumberOfDimensions() != 0)
       continue;
     if (Array->isPHIKind()) {
       // For PHI nodes, the only values we need to store are the ones that
       // reach the PHI node from outside the region. In general there should
       // only be one such incoming edge and this edge should enter through
       // 'SplitBB'.
       auto PHI = cast<PHINode>(Array->getBasePtr());
for (const auto &EscapeMapping : EscapeMap) {
 
     // Replace all uses of the demoted instruction with the merge PHI.
     for (Instruction *EUser : EscapeUsers)
       EUser->replaceUsesOfWith(EscapeInst, MergePHI);
   }
 }
 
 void BlockGenerator::findOutsideUsers(Scop &S) {
-  for (auto &Pair : S.arrays()) {
-    auto &Array = Pair.second;
+  for (auto &Array : S.arrays()) {
 
     if (Array->getNumberOfDimensions() != 0)
       continue;
 
     if (Array->isPHIKind())
       continue;
 
     auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
void BlockGenerator::createExitPHINodeMerges(Scop &S) {
   auto *MergeBB = S.getExit();
   auto *AfterMergeBB = MergeBB->getSingleSuccessor();
   BasicBlock *OptExitBB = *(pred_begin(MergeBB));
   if (OptExitBB == ExitBB)
     OptExitBB = *(++pred_begin(MergeBB));
 
   Builder.SetInsertPoint(OptExitBB->getTerminator());
 
-  for (auto &Pair : S.arrays()) {
-    auto &SAI = Pair.second;
+  for (auto &SAI : S.arrays()) {
     auto *Val = SAI->getBasePtr();
 
     // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
     // the original PHI's value or the reloaded incoming values from the
     // generated code. An llvm::Value is merged between the original code's
     // value or the generated one.
     if (!SAI->isValueKind() && !SAI->isExitPHIKind())
       continue;

polly/trunk/lib/CodeGen/CodeGeneration.cpp

if (!NodeBuilder.preloadInvariantLoads()) {
       markBlockUnreachable(*ExitingBlock, Builder);
       auto *ExitingBB = S.getExitingBlock();
       assert(ExitingBB);
       DT->changeImmediateDominator(MergeBlock, ExitingBB);
       DT->eraseNode(ExitingBlock);
 
       isl_ast_node_free(AstRoot);
     } else {
+      NodeBuilder.allocateNewArrays();
 
       NodeBuilder.addParameters(S.getContext());
 
       ExprBuilder.setTrackOverflow(true);
       Value *RTC = buildRTC(Builder, ExprBuilder);
       Value *OverflowHappened = Builder.CreateNot(
           ExprBuilder.getOverflowState(), "polly.rtc.overflown");
       RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

for (const MemoryAccess *MA : MAs) {
 
     EscapeMap[MA->getAccessInstruction()] =
         std::make_pair(Alloca, std::move(EscapeUsers));
   }
 
   return true;
 }
 
+void IslNodeBuilder::allocateNewArrays() {
+  for (auto &SAI : S.arrays()) {
+    if (SAI->getBasePtr())
+      continue;
+
+    Type *NewArrayType = nullptr;
+    for (unsigned i = SAI->getNumberOfDimensions() - 1; i >= 1; i--) {
+      auto *DimSize = SAI->getDimensionSize(i);
+      unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize)
+                                     ->getAPInt()
+                                     .getLimitedValue();
+
+      if (!NewArrayType)
+        NewArrayType = SAI->getElementType();
+
+      NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);
+    }
+
+    auto InstIt =
+        Builder.GetInsertBlock()->getParent()->getEntryBlock().getTerminator();
+    Value *CreatedArray =
+        new AllocaInst(NewArrayType, SAI->getName(), &*InstIt);
+    SAI->setBasePtr(CreatedArray);
+  }
+}
+
 bool IslNodeBuilder::preloadInvariantLoads() {
 
   auto &InvariantEquivClasses = S.getInvariantAccesses();
   if (InvariantEquivClasses.empty())
     return true;
 
   BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),
                                      &*Builder.GetInsertPoint(), &DT, &LI);

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

SetVector<Value *> GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
 
   isl_ast_node_foreach_descendant_top_down(
       Kernel->tree, collectReferencesInGPUStmt, &References);
 
   for (const SCEV *Expr : SCEVs)
     findValues(Expr, SE, SubtreeValues);
 
   for (auto &SAI : S.arrays())
-    SubtreeValues.remove(SAI.second->getBasePtr());
+    SubtreeValues.remove(SAI->getBasePtr());
 
   isl_space *Space = S.getParamSpace();
   for (long i = 0; i < isl_space_dim(Space, isl_dim_param); i++) {
     isl_id *Id = isl_space_get_dim_id(Space, isl_dim_param, i);
     assert(IDToValue.count(Id));
     Value *Val = IDToValue[Id];
     SubtreeValues.remove(Val);
     isl_id_free(Id);
__isl_give isl_id_to_ast_expr *getNames() {
     auto *Space = S->getParamSpace();
 
     for (int I = 0, E = S->getNumParams(); I < E; ++I) {
       isl_id *Id = isl_space_get_dim_id(Space, isl_dim_param, I);
       Names = isl_id_to_ast_expr_set(Names, Id, isl_ast_expr_copy(Zero));
     }
 
     for (auto &Array : S->arrays()) {
-      auto Id = Array.second->getBasePtrId();
+      auto Id = Array->getBasePtrId();
       Names = isl_id_to_ast_expr_set(Names, Id, isl_ast_expr_copy(Zero));
     }
 
     isl_space_free(Space);
     isl_ast_expr_free(Zero);
 
     return Names;
   }
void setArrayBounds(gpu_array_info &PPCGArray, ScopArrayInfo *Array) {
     }
   }
 
   /// Create the arrays for @p PPCGProg.
   ///
   /// @param PPCGProg The program to compute the arrays for.
   void createArrays(gpu_prog *PPCGProg) {
     int i = 0;
-    for (auto &Element : S->arrays()) {
-      ScopArrayInfo *Array = Element.second.get();
-
+    for (auto &Array : S->arrays()) {
       std::string TypeName;
       raw_string_ostream OS(TypeName);
 
       OS << *Array->getElementType();
       TypeName = OS.str();
 
       gpu_array_info &PPCGArray = PPCGProg->array[i];
 
public:
   }
 
   /// Create an identity map between the arrays in the scop.
   ///
   /// @returns An identity map between the arrays in the scop.
   isl_union_map *getArrayIdentity() {
     isl_union_map *Maps = isl_union_map_empty(S->getParamSpace());
 
-    for (auto &Item : S->arrays()) {
-      ScopArrayInfo *Array = Item.second.get();
+    for (auto &Array : S->arrays()) {
       isl_space *Space = Array->getSpace();
       Space = isl_space_map_from_set(Space);
       isl_map *Identity = isl_map_identity(Space);
       Maps = isl_union_map_add_map(Maps, Identity);
     }
 
     return Maps;
   }

polly/trunk/lib/Exchange/JSONExporter.cpp

 #include "polly/ScopPass.h"
 #include "polly/Support/ScopLocation.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Support/raw_ostream.h"
 #include "isl/constraint.h"
 #include "isl/map.h"
 #include "isl/printer.h"
 #include "isl/set.h"
 #include "isl/union_map.h"
 #include "json/reader.h"
 #include "json/writer.h"
 #include <memory>
struct JSONImporter : public ScopPass {
   ///
   /// @param S The scop to update.
   /// @param JScop The JScop file describing the new schedule.
   /// @param D The data dependences of the @p S.
   ///
   /// @returns True if the import succeeded, otherwise False.
   bool importSchedule(Scop &S, Json::Value &JScop, const Dependences &D);
 
+  /// Import new arrays from JScop.
+  ///
+  /// @param S The scop to update.
+  /// @param JScop The JScop file describing new arrays.
+  ///
+  /// @returns True if the import succeeded, otherwise False.
+  bool importArrays(Scop &S, Json::Value &JScop);
+
   /// Import new memory accesses from JScop.
   ///
   /// @param S The scop to update.
   /// @param JScop The JScop file describing the new schedule.
   /// @param DL The datalayout to assume.
   ///
   /// @returns True if the import succeeded, otherwise False.
   bool importAccesses(Scop &S, Json::Value &JScop, const DataLayout &DL);

 std::string JSONExporter::getFileName(Scop &S) const {
   std::string FunctionName = S.getFunction().getName();
   std::string FileName = FunctionName + "___" + S.getNameStr() + ".jscop";
   return FileName;
 }
 
 void JSONExporter::printScop(raw_ostream &OS, Scop &S) const { S.print(OS); }
 
+/// Export all arrays from the Scop.
+///
+/// @param S The Scop containing the arrays.
+///
+/// @returns Json::Value containing the arrays.
+Json::Value exportArrays(const Scop &S) {
+  Json::Value Arrays;
+  std::string Buffer;
+  llvm::raw_string_ostream RawStringOstream(Buffer);
+
+  for (auto &SAI : S.arrays()) {
+    if (!SAI->isArrayKind())
+      continue;
+
+    Json::Value Array;
+    Array["name"] = SAI->getName();
+    for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++) {
+      SAI->getDimensionSize(i)->print(RawStringOstream);
+      Array["sizes"].append(RawStringOstream.str());
+      Buffer.clear();
+    }
+    SAI->getElementType()->print(RawStringOstream);
+    Array["type"] = RawStringOstream.str();
+    Buffer.clear();
+    Arrays.append(Array);
+  }
+  return Arrays;
+}
+
 Json::Value JSONExporter::getJSON(Scop &S) const {
   Json::Value root;
   unsigned LineBegin, LineEnd;
   std::string FileName;
 
   getDebugLocation(&S.getRegion(), LineBegin, LineEnd, FileName);
   std::string Location;
   if (LineBegin != (unsigned)-1)
     Location = FileName + ":" + std::to_string(LineBegin) + "-" +
                std::to_string(LineEnd);
 
   root["name"] = S.getNameStr();
   root["context"] = S.getContextStr();
   if (LineBegin != (unsigned)-1)
     root["location"] = Location;
+
+  root["arrays"] = exportArrays(S);
+
   root["statements"];
 
   for (ScopStmt &Stmt : S) {
     Json::Value statement;
 
     statement["name"] = Stmt.getBaseName();
     statement["domain"] = Stmt.getDomainStr();
     statement["schedule"] = Stmt.getScheduleStr();
for (MemoryAccess *MA : Stmt) {
       if (isl_map_dim(NewAccessMap, isl_dim_param) !=
           isl_map_dim(CurrentAccessMap, isl_dim_param)) {
         errs() << "JScop file changes the number of parameter dimensions\n";
         isl_map_free(CurrentAccessMap);
         isl_map_free(NewAccessMap);
         return false;
       }
 
+      isl_id *NewOutId;
+
+      if (MA->isArrayKind()) {
+        NewOutId = isl_map_get_tuple_id(NewAccessMap, isl_dim_out);
+        auto *SAI = S.getArrayInfoByName(isl_id_get_name(NewOutId));
         isl_id *OutId = isl_map_get_tuple_id(CurrentAccessMap, isl_dim_out);
-      NewAccessMap = isl_map_set_tuple_id(NewAccessMap, isl_dim_out, OutId);
+        auto *OutSAI = ScopArrayInfo::getFromId(OutId);
+        if (!SAI || SAI->getElementType() != OutSAI->getElementType()) {
+          errs() << "JScop file contains access function with undeclared "
+                    "ScopArrayInfo\n";
+          isl_map_free(CurrentAccessMap);
+          isl_map_free(NewAccessMap);
+          isl_id_free(NewOutId);
+          return false;
+        }
+        isl_id_free(NewOutId);
+        NewOutId = SAI->getBasePtrId();
+      } else {
+        NewOutId = isl_map_get_tuple_id(CurrentAccessMap, isl_dim_out);
+      }
+
+      NewAccessMap = isl_map_set_tuple_id(NewAccessMap, isl_dim_out, NewOutId);
 
       if (MA->isArrayKind()) {
         // We keep the old alignment, thus we cannot allow accesses to memory
         // locations that were not accessed before if the alignment of the
         // access is not the default alignment.
         bool SpecialAlignment = true;
         if (LoadInst *LoadI = dyn_cast<LoadInst>(MA->getAccessInstruction())) {
           SpecialAlignment =
for (MemoryAccess *MA : Stmt) {
         NewAccessMap = isl_map_set_dim_id(NewAccessMap, isl_dim_param, i, Id);
       }
 
       // Copy the old tuple id. This is necessary to retain the user pointer,
       // that stores the reference to the ScopStmt this access belongs to.
       isl_id *Id = isl_map_get_tuple_id(CurrentAccessMap, isl_dim_in);
       NewAccessMap = isl_map_set_tuple_id(NewAccessMap, isl_dim_in, Id);
 
-      if (!isl_map_has_equal_space(CurrentAccessMap, NewAccessMap)) {
+      auto NewAccessDomain = isl_map_domain(isl_map_copy(NewAccessMap));
+      auto CurrentAccessDomain = isl_map_domain(isl_map_copy(CurrentAccessMap));
+
+      if (!isl_set_has_equal_space(NewAccessDomain, CurrentAccessDomain)) {
         errs() << "JScop file contains access function with incompatible "
                << "dimensions\n";
         isl_map_free(CurrentAccessMap);
         isl_map_free(NewAccessMap);
+        isl_set_free(NewAccessDomain);
+        isl_set_free(CurrentAccessDomain);
         return false;
       }
 
-      auto NewAccessDomain = isl_map_domain(isl_map_copy(NewAccessMap));
-      auto CurrentAccessDomain = isl_map_domain(isl_map_copy(CurrentAccessMap));
-
       NewAccessDomain =
           isl_set_intersect_params(NewAccessDomain, S.getContext());
       CurrentAccessDomain =
           isl_set_intersect_params(CurrentAccessDomain, S.getContext());
 
       if (isl_set_is_subset(CurrentAccessDomain, NewAccessDomain) ==
           isl_bool_false) {
         errs() << "Mapping not defined for all iteration domain elements\n";
for (MemoryAccess *MA : Stmt) {
       MemoryAccessIdx++;
     }
     StatementIdx++;
   }
 
   return true;
 }
 
+/// @brief Check whether @p SAI and @p Array represent the same array.
+bool areArraysEqual(ScopArrayInfo *SAI, Json::Value Array) {
+  std::string Buffer;
+  llvm::raw_string_ostream RawStringOstream(Buffer);
+
+  if (SAI->getName() != Array["name"].asCString())
+    return false;
+
+  if (SAI->getNumberOfDimensions() != Array["sizes"].size() + 1)
+    return false;
+
+  for (unsigned i = 0; i < Array["sizes"].size(); i++) {
+    SAI->getDimensionSize(i + 1)->print(RawStringOstream);
+    if (RawStringOstream.str() != Array["sizes"][i].asCString())
+      return false;
+    Buffer.clear();
+  }
+
+  SAI->getElementType()->print(RawStringOstream);
+  if (RawStringOstream.str() != Array["type"].asCString())
+    return false;
+
+  return true;
+}
+
+/// @brief Get the accepted primitive type from its textual representation
+///        @p TypeTextRepresentation.
+///
+/// @param TypeTextRepresentation The textual representation of the type.
+/// @return The pointer to the primitive type, if this type is accepted
+///         or nullptr otherwise.
+Type *parseTextType(const std::string &TypeTextRepresentation,
+                    LLVMContext &LLVMContext) {
+  std::map<std::string, Type *> MapStrToType = {
+      {"void", Type::getVoidTy(LLVMContext)},
+      {"half", Type::getHalfTy(LLVMContext)},
+      {"float", Type::getFloatTy(LLVMContext)},
+      {"double", Type::getDoubleTy(LLVMContext)},
+      {"x86_fp80", Type::getX86_FP80Ty(LLVMContext)},
+      {"fp128", Type::getFP128Ty(LLVMContext)},
+      {"ppc_fp128", Type::getPPC_FP128Ty(LLVMContext)},
+      {"i1", Type::getInt1Ty(LLVMContext)},
+      {"i8", Type::getInt8Ty(LLVMContext)},
+      {"i16", Type::getInt16Ty(LLVMContext)},
+      {"i32", Type::getInt32Ty(LLVMContext)},
+      {"i64", Type::getInt64Ty(LLVMContext)},
+      {"i128", Type::getInt128Ty(LLVMContext)}};
+
+  auto It = MapStrToType.find(TypeTextRepresentation);
+  if (It != MapStrToType.end())
+    return It->second;
+
+  errs() << "Textual representation can not be parsed: "
+         << TypeTextRepresentation << "\n";
+  return nullptr;
+}
+
+bool JSONImporter::importArrays(Scop &S, Json::Value &JScop) {
+  Json::Value Arrays = JScop["arrays"];
+
+  if (Arrays.size() == 0)
+    return true;
+
+  unsigned ArrayIdx = 0;
+  for (auto &SAI : S.arrays()) {
+    if (!SAI->isArrayKind())
+      continue;
+    if (ArrayIdx + 1 > Arrays.size())
+      return false;
+    if (!areArraysEqual(SAI, Arrays[ArrayIdx]))
+      return false;
+    ArrayIdx++;
+  }
+
+  for (; ArrayIdx < Arrays.size(); ArrayIdx++) {
+    auto *ElementType = parseTextType(Arrays[ArrayIdx]["type"].asCString(),
+                                      S.getSE()->getContext());
+    if (!ElementType)
+      return false;
+    std::vector<unsigned> DimSizes;
+    for (unsigned i = 0; i < Arrays[ArrayIdx]["sizes"].size(); i++)
+      DimSizes.push_back(std::stoi(Arrays[ArrayIdx]["sizes"][i].asCString()));
+    S.createScopArrayInfo(ElementType, Arrays[ArrayIdx]["name"].asCString(),
+                          DimSizes);
+  }
+
+  return true;
+}
+
 bool JSONImporter::runOnScop(Scop &S) {
   const Dependences &D =
       getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
   const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
 
   std::string FileName = ImportDir + "/" + getFileName(S);
 
   std::string FunctionName = S.getFunction().getName();
bool JSONImporter::runOnScop(Scop &S) {
   if (!Success)
     return false;
 
   Success = importSchedule(S, jscop, D);
 
   if (!Success)
     return false;
 
+  Success = importArrays(S, jscop);
+
+  if (!Success)
+    return false;
+
   Success = importAccesses(S, jscop, DL);
 
   if (!Success)
     return false;
 
   return false;
 }
 

polly/trunk/test/Isl/CodeGen/MemAccess/create_arrays.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-import-jscop-dir=%S -polly-import-jscop -polly-import-jscop-postfix=transformed < %s 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-import-jscop-dir=%S -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-codegen -S < %s 2>&1 | FileCheck %s --check-prefix=CODEGEN
+;
+;  for (i = 0; i < _PB_NI; i++)
+;    for (j = 0; j < _PB_NJ; j++)
+;      for (k = 0; k < _PB_NK; ++k)
+;        B[i][j] = beta * A[i][k];
+;
+;
+; CHECK:    Arrays {
+; CHECK:        double MemRef_B[*][1024]; // Element size 8
+; CHECK:        double MemRef_beta; // Element size 8
+; CHECK:        double MemRef_A[*][1056]; // Element size 8
+; CHECK:        double D[*][270336]; // Element size 8
+; CHECK:        double E[*][270336][200000]; // Element size 8
+; CHECK:        i64 F[*][270336]; // Element size 8
+;
+; CHECK:New access function '{ Stmt_bb12[i0, i1, i2] -> E[i2, i0] }'detected in JSCOP file
+;
+;define internal void @create_arrays(i32 %arg, i32 %arg1, i32 %arg2, double %arg3, double %beta, [1056 x double]* %A, [1024 x double]* %B, [1056 x double]* %arg7) #0 {
+;bb:
+;  %beta.s2a = alloca double
+;  %D = alloca [270336 x double]
+;  %E = alloca [270336 x [200000 x double]]
+;  %F = alloca [270336 x i64]
+;  br label %bb8
+;
+; CODEGEN:  %polly.access.cast.E = bitcast [270336 x [200000 x double]]* %E to double*
+; CODEGEN:  %polly.access.mul.E = mul nsw i64 %polly.indvar33, 270336
+; CODEGEN:  %polly.access.add.E = add nsw i64 %polly.access.mul.E, %polly.indvar
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-unknown"
+
+; Function Attrs: nounwind uwtable
+define internal void @create_arrays(i32 %arg, i32 %arg1, i32 %arg2, double %arg3, double %beta, [1056 x double]* %A, [1024 x double]* %B, [1056 x double]* %arg7) #0 {
+bb:
+  br label %bb8
+
+bb8:                                              ; preds = %bb
+  br label %bb9
+
+bb9:                                              ; preds = %bb23, %bb8
+  %tmp = phi i64 [ 0, %bb8 ], [ %tmp24, %bb23 ]
+  br label %bb10
+
+bb10:                                             ; preds = %bb20, %bb9
+  %tmp11 = phi i64 [ 0, %bb9 ], [ %tmp21, %bb20 ]
+  br label %bb12
+
+bb12:                                             ; preds = %bb12, %bb10
+  %tmp13 = phi i64 [ 0, %bb10 ], [ %tmp18, %bb12 ]
+  %tmp14 = getelementptr inbounds [1024 x double], [1024 x double]* %B, i64 %tmp, i64 %tmp13
+  %tmp15 = load double, double* %tmp14, align 8
+  %tmp16 = fmul double %tmp15, %beta
+  %tmp17 = getelementptr inbounds [1056 x double], [1056 x double]* %A, i64 %tmp, i64 %tmp11
+  store double %tmp16, double* %tmp17, align 8
+  %tmp18 = add nuw nsw i64 %tmp13, 1
+  %tmp19 = icmp ne i64 %tmp18, 1024
+  br i1 %tmp19, label %bb12, label %bb20
+
+bb20:                                             ; preds = %bb12
+  %tmp21 = add nuw nsw i64 %tmp11, 1
+  %tmp22 = icmp ne i64 %tmp21, 1056
+  br i1 %tmp22, label %bb10, label %bb23
+
+bb23:                                             ; preds = %bb20
+  %tmp24 = add nuw nsw i64 %tmp, 1
+  %tmp25 = icmp ne i64 %tmp24, 1056
+  br i1 %tmp25, label %bb9, label %bb26
+
+bb26:                                             ; preds = %bb23
+  ret void
+}
+
+attributes #0 = { nounwind uwtable "target-cpu"="x86-64" "target-features"="+aes,+avx,+cmov,+cx16,+fxsr,+mmx,+pclmul,+popcnt,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsaveopt" }

polly/trunk/test/Isl/CodeGen/MemAccess/create_arrays___%bb9---%bb26.jscop

+{
+   "arrays" : [
+     {
+         "name" : "MemRef_B",
+         "sizes" : [ "1024" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "1056" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%bb9---%bb26",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb12[i0, i1, i2] -> MemRef_B[i0, i2] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb12[i0, i1, i2] -> MemRef_beta[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_bb12[i0, i1, i2] -> MemRef_A[i0, i1] }"
+            }
+         ],
+         "domain" : "{ Stmt_bb12[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 1023 }",
+         "name" : "Stmt_bb12",
+         "schedule" : "{ Stmt_bb12[i0, i1, i2] -> [i0, i1, i2] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/MemAccess/create_arrays___%bb9---%bb26.jscop.transformed

+{
+   "arrays" : [
+       {
+         "name" : "MemRef_B",
+         "sizes" : [ "1024" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "1056" ],
+         "type" : "double"
+      },
+      {
+         "name" : "D",
+         "sizes" : [ "270336" ],
+         "type" : "double"
+      },
+      {
+         "name" : "E",
+         "sizes" : [ "270336", "200000" ],
+         "type" : "double"
+      },
+      {
+         "name" : "F",
+         "sizes" : [ "270336" ],
+         "type" : "i64"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%bb9---%bb26",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb12[i0, i1, i2] -> E[i2, i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb12[i0, i1, i2] -> MemRef_beta[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_bb12[i0, i1, i2] -> MemRef_A[i0, i1] }"
+            }
+         ],
+         "domain" : "{ Stmt_bb12[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 1023 }",
+         "name" : "Stmt_bb12",
+         "schedule" : "{ Stmt_bb12[i0, i1, i2] -> [i0, i1, i2] }"
+      }
+   ]
+}