[Polly] Heap allocation for new arrays

[niosega]

Summary

This patch aims to implement the option of allocating new arrays created by polly on heap instead of stack.
To enable this option, a key named 'allocation' must be written in the imported json file with the value 'heap'.

We need such a feature because in a next iteration, we will implement a mechanism of maximal static expansion which will need a way to allocate arrays on heap. Indeed, the expansion is very costly in terms of memory and doing the allocation on stack is not worth considering.

The malloc and the free are added respectively at polly.start and polly.exiting such that there is no use-after-free (for instance in case of Scop in a loop) and such that all memory cells allocated with a malloc are free'd when we don't need them anymore.

We also add :

• In the class ScopArrayInfo, we add a boolean as member called IsOnHeap which represents the fact that the array in allocated on heap or not.
• A new branch in the method allocateNewArrays in the ISLNodeBuilder for the case of heap allocation. allocateNewArrays now takes a BBPair containing polly.start and polly.exiting. allocateNewArrays takes this two blocs and add the malloc and free calls respectively to polly.start and polly.exiting.
• As IntPtrTy for the malloc call, we use the DalaLayout one.

To do that, we have modified :

• CreateScopArrayInfo and getOrCreateScopArrayInfo such that it return a non-const SAI, in order to be able to call setIsOnHeap in the JSONImporter.
• executeScopConditionnaly such that it return both start block and end block of the scop, because we need this two blocs to be able to add the malloc and the free calls at the right position.

[simbuerg]

General Note: Can you reduce the size of the test-cases? (Remove the debug metadata with opt -strip-debug, unnecessary attributes).

[simbuerg]

lib/CodeGen/IslNodeBuilder.cpp

1417

Question for my own understanding: We can pin this to 64bits only if we know which malloc implementation we have available on the target machine, right?

[simbuerg]

So far it looks good. I would add tests that take care of error cases: negative sizes, overflow in the size calculation.

lib/CodeGen/IslNodeBuilder.cpp

1413

You already wrote it in your diff-summary: I would make this a property of the SAI and fill this information from the JSON side.

[philip.pfaffe]

lib/CodeGen/IslNodeBuilder.cpp

1417

Why not get the real IntPtrTy from the current DataLayout?

[simbuerg]

lib/CodeGen/IslNodeBuilder.cpp

1417

Well it's not the problem that we don't know the size of the IntPtr. We don't know the argument type that the system's malloc function expects (whatever size_t might be on the target).

Normally you would expect 'unsigned int', then we could just get the size from the DataLayout.
By default CreateMalloc would generate a call to 'void malloc(IntPtrTy)'.

[Meinersbur]

I am wondering why you decided for a global stack-or-heap property. I'd assumed that this is a per-array decision. For instance, Roman's gemm optimization is designed to fit on the stack, there is no reason to allocate it on the heap.

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

Where is the memory free'd?

[niosega]

In D33688#774231, @Meinersbur wrote:

I am wondering why you decided for a global stack-or-heap property. I'd assumed that this is a per-array decision. For instance, Roman's gemm optimization is designed to fit on the stack, there is no reason to allocate it on the heap.

The global stack-or-heap property is just for debugging purpose (as explained in the summary). I publish my code in phabricator so that I can have feedback and remarks on the malloc / free implementation. I am working in parallel on adding the possibility to specify in the json file if we want heap or stack array, as Andreas described in an inline comment.

[Meinersbur]

Thanks for explaining it (again).

You can mark your patch with "WIP" (Work in Progress) if you do not intend to have it committed as-is.

For being commit-ready, I think the test case should be smaller (as already mentioned by Andres), and the malloc'ed memory must also be released.

[simbuerg]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

Good Catch. We just discussed possible locations for the free. The easiest way would be the exit(s) of the SCoP. However, to keep it simple, we would have to do a copy-in/-out to the original array base pointer, right? Everything else (e.g. calculating lexicographic maximal accesses) would give us trouble with non-polyhedral accesses between SCoPs.

[philip.pfaffe]

lib/CodeGen/IslNodeBuilder.cpp

1417

You are right of course. There is no way to obtain the real size_t in the middle end.

I don't have a strong opinion on this, but I'd consider IntPtrTy to be the better default over hard-coding some int type, as AFAICS (u)intptr_t and size_t are the same on basically all platforms.

1423–1427

Couldn't that create use-after-free if the SCoP is within a loop?

[niosega]

Release the memory.

Remove the cli option and now use a JSON property to enable heap allocation.

Remove metadatas in the test case.

[Meinersbur]

include/polly/ScopInfo.h

361

Please add the information that the property is only relevant if the array is allocated by Polly instead of pre-existing. Also, that when it is false, it is allocated using alloca (instead of malloca)

424

... is allocated on the heap. The "False otherwise" does not add any information, it's a boolean.

2610

Please document the new parameter.

Instead of passing to every constructor, you could also defeault-initialize it to false and add a setIsOnHeap accessor (or similar name) to change that property after creation.

2619

Please document the new parameter.

lib/CodeGen/IslNodeBuilder.cpp

1398

On 32-bit platforms and 64-but windows, long has only 32 bits. You test case failsdue to an overflow:

polly\test\Isl\CodeGen\MemAccess\create_arrays_heap.ll:35:12: error: expected string not found in input
; CODEGEN: %malloccall1 = tail call i8* @malloc(i64 432537600000)
           ^
<stdin>:12:2: note: scanning from here
 %malloccall1 = tail call i8* @malloc(i64 20220739584)
 ^

error: command failed with exit status: 1

1423–1427

copy-in/out is not specific to heap arrays. Such things can be done using with additional copy statements.

For scalar expansion, the scalar are not available after the SCoP anyway, with the exception of 'escaping' scalars. In that case only a single value is available to the outside. I suggest to exclude escaping scalars at the moment.

Here, alloca/malloc are generated when entering the Scop. I think free'ing it when exiting it is the most obvious choice.

@gareevroman
Btw, for alloca this location looks to be the wrong choice. alloca's should be in a function's entry block. The SCoP itself could be within the loop, meaning that everytime the SCoP is executed, the stack grows, up to a possible stack overflow.

1423–1427

@gareevroman
I was wrong, the alloca is actually added to the entry block.

This means that also the malloc is in the entry block, but the call to free below is added into last block of the orginal region (where it is not even used). We either have to

1. Add the malloc to the entry block and the free at every ret (or non-returning function call)

• or -

2. Add the malloc to the start of the generated code (polly.start) and the free at the end of it (polly.exiting).

1431

The variable FreedArray isn't used anywhere.

lib/Exchange/JSONExporter.cpp

708

There is no necessity to store temporary StringRef for a literal string. AllocationString == "head" should just work.

test/Isl/CodeGen/MemAccess/create_arrays_heap.ll

2

mem2reg does not need to be part of a test. You can invoke opt create_arrays_heap.ll -mem2reg -S and use that output for the test case.

Does this test require 2>&1?

[simbuerg]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

Wait, if you malloc at function entry and free at every ret of the function you will end up with problems in code that can't be modeled as a SCoP because you cannot map to the correct
'last write' in the expanded array that is required for a memory access outside of the SCoP. Therefore, you will have to do copy-in/-out before/after the SCoP to stay correct, hence you can malloc/free right at the SCoP boundary (because you need to do the copying anyway).

Use-After-Free wouldn't become an issue as soon as you malloc/free at the SCoP boundary.

[simbuerg]

include/polly/ScopInfo.h

2610

I would also recommend going for default initialization to false and provide a setter for the property.

[philip.pfaffe]

lib/CodeGen/IslNodeBuilder.cpp

1432

Scop::getExitingBlock() may return nullptr, for instance when it refers to the TopLevelRegion.

[Meinersbur]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

copy-in/out is not specific to heap arrays. Such things can be done using with additional copy statements.

For scalar expansion, the scalar are not available after the SCoP anyway, with the exception of 'escaping' scalars. In that case only a single value is available to the outside. I suggest to exclude escaping scalars at the moment.

Here, alloca/malloc are generated when entering the Scop. I think free'ing it when exiting it is the most obvious choice.

@gareevroman
Btw, for alloca this location looks to be the wrong choice. alloca's should be in a function's entry block. The SCoP itself could be within the loop, meaning that everytime the SCoP is executed, the stack grows, up to a possible stack overflow.

1423–1427

We have no control about memory accesses outside of a SCoP and should not try to modify them to read from the expanded array itself.

For scalar uses, a single LoadInst is enough for outside uses.

For array uses, one has to copy the data to the original array in any case. It might captured by a function call and/or used after the function containing the SCoP.

void function_with_scop(float A[]) {
#pragma scop
for (int i = 0; i < 128; i+=1) 
  for (int j = 0; j < 128; j+=1) 
    A[j] = ...
#pragma endscop
  print(A[getIndexToPrint()]);
}

int main() {
  float A[128];
  function_with_scop(A[128]);
  print(A[5]);
}

How do you expand A to two dimensions without a copy-back?

I suggest to consider only uses where the array/scalar is entire contained within the SCoP at first. Escaping scalars is easy to add. Copy-back can be implemented afterwards. For special cases we could avoid copy-back like this:

void function_with_scop() {
{ // generated
A_expaned = malloc(128*128*sizeof(float))
for (int i = 0; i < 128; i+=1) 
  for (int j = 0; j < 128; j+=1) 
    A_expaned[i][j] = ...
A = &A[127];
}
  use(A[5]);
}

for which we have to be able to replace all base ptrs of A.

Choice of alternatives:

void scop_in_loop() {
  for (int i = 0; i < 128; i+=1) {
#pragma scop
    for (int j = 0; j < 128; j+=1) 
      A[i] = ...
#pragma endscops
  }
}

we could generate

void scop_in_loop() {
  for (int i = 0; i < 128; i+=1)
{ // generated
  A_expanded = malloc(...);
  ...
  free(A_generated);
}
}

or

void scop_in_loop() {
  A_expanded = malloc(...);
  for (int i = 0; i < 128; i+=1)
{ // generated
  ...
}
  free(A_generated);
}

1. allocates memory multiple times.
2. allocates memory even if it is never used (e.g. SCoP is in an if-conditional). The memory necessary might also depend on a parameter, which is not known at the entry of a function;

void scop_in_loop() {
  int n = array->size();
  for (int i = 0; i < n; i+=1) {
#pragma scop
    for (int j = 0; j < 128; j+=1) 
      A[i] = ...
#pragma endscops
  }
}

There is also alternative 3 where we create a global of the required size:

static float A_expanded[128][128];

The would be memory inside an executable's .bss segment which most operating systems do not assign physical memory to until its first use. No free'ing required here, but we also cannot make the size dependent on some parameter. You are also polluting the host's virtual address space and get issues with threading.

I tend to go towards alternative 2.

[niosega]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

I am currently working on inserting the malloc and the free at the right place (polly.start and polly.exiting) .
But I am having trouble to find how to get the BasicBloc or the Instruction before which I must insert these two calls.
Does anybody know how to get a pointer to them ?

[Meinersbur]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

polly.start: Either pass StartBlock as an argument to allocateNewArrays or, I think the IRBuilder should still be at that position when allocateNewArrays is called.

polly.exiting: PerfMonitoring also has to get the end of the SCoP. It does so in an not-so-elegant way in CodeGeneration.cpp:195

BasicBlock *MergeBlock = SplitBlock->getTerminator()
                             ->getSuccessor(0)
                             ->getUniqueSuccessor()
                             ->getUniqueSuccessor();

At the point when allocateNewArrays is called, polly.exiting should also be just the successor of polly.start (I think). So StartBlock->getUniqueSuccessor() should be enough.

[simbuerg]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

Maybe it would be a smart idea to refactor
executeScopConditionally to return a BBPair with the polly.start, polly.exiting blocks that were created? It returns polly.start already.

[simbuerg]

lib/CodeGen/IslNodeBuilder.cpp

1423–1427

If the malloc/free take place in the freshly inserted blocks polly.start/polly.exiting? That shouldn't be possible, right?

[niosega]

The changes made in this update are the following :

• Default initialization of isOnHeap to false and implementation of a setter
• Add a test case to JSONImporter to check the size of an imported array
• Use the IntPtrTy of the DataLayout
• Remove useless StringRef in JSONImporter
• Remove useless FreedArray variable in ISLNodeBuilder
• Remove useless -mem2reg and 2>1 in test case
• Call to malloc and free at the correct position (polly.start and polly.exiting)

For the malloc and free positions, we have made the following modifications :

• Take into account the patch that modify the signature of executeScopConditionnally (now returning both start and end block)
• Set the InsertPoint before AST building to the end of the block so that the split between newly created branch and old branch is made such that the malloc call is in polly.start

[niosega]

lib/Exchange/JSONExporter.cpp

710

I need to have a pointer to the newly created ScopArrayInfo to call the setter.
But the method createScopArrayInfo returns only a const SAI *. The solution
I found is to query the Scop to obtain the SAI by name.

An alternative would be to pass a parameter to createScopArrayInfo then to
getOrCreateScopArrayInfo that represents the value that isOnHeap must take.

[simbuerg]

lib/CodeGen/CodeGeneration.cpp

241

Maybe something like this:

Explicitly set the insert point to the end of the block to avoid that a split at the builder's current
insert position would move the malloc calls to the wrong BasicBlock. Ideally we would just split
the block during allocation of the new arrays, but this would break the assumption that there are
no blocks between polly.start and polly.exiting (at this point).

No need to mention that the creation on the heap fails, because this is not the problem, this is the
result. Furthermore, polly.loop_exit has nothing to do with this. This is just the block the malloc end up in,
if you do not set the insert location to the end.

What you want to achieve is simply: Preserve the mallocs in the polly.start block. The correct solution would be
to split the BasicBlock, however that would touch all places that assume that there are only polly.start and polly.exiting.
So, this solution works and interferes with as few locations as possible.

[simbuerg]

lib/Exchange/JSONExporter.cpp

710

This is just to circumvent an inconvenient API that you want to add with this patch. I would suggest a simpler way:
Instead of depending on the setter, just add the IsOnHeap property as a function argument to
createScopArrayInfo and pass it through to getOrCreateScopArrayInfo. There you can pass it to the constructor or use
your setter.

[niosega]

lib/Exchange/JSONExporter.cpp

710

To pass the parameter through createScopArrayInfo then getOrCreateScopArrayInfo then to the constructor is what I did in the previous version of the patch. Michael and you agreed that it was not the prettiest solution. Should I change it back ?

[simbuerg]

lib/Exchange/JSONExporter.cpp

710

Well the pass-through is ugly too :-).
So far, I see 3 options:

1. Pass it through everything.
2. Remove the const-ness of createScopArrayInfo
3. Make IsOnHeap mutable.

I just dislike the lookup by name to get a non-const ScopArrayInfo. Michael what do you think?
If nobody is objecting the name-lookup, I'm fine with it as well.

[Meinersbur]

lib/CodeGen/IslNodeBuilder.cpp

1419

There is ScopArrayInfo::getElemSizeInBytes() which should be the standard way to get an element's size, unless you have a reason why you need something different.

lib/Exchange/JSONExporter.cpp

708

The additional range check could be committed separately, it look unrelated.
(Andreas can just commit it with its test case)

710

I prefer removing the const which IMHO serves no purpose. Some of its methods like updateElementType already do modify the SAI, and it should not matter how one gets the reference to it.

Scop::updateAccessDimensionality() already does an const_cast in order to be able to call updateElementType.

[niosega]

This update modify two things :

• Modifying the comment in CodeGeneration about the changes of insert point.
• Remove the constness of CreateScopArrayInfo and getOrCreateScopArrayInfo and call directly the setter setIsOnHeap in JSONImporter.

[simbuerg]

We're getting close IMHO. I will commit the small range-check patch tonight.

lib/Exchange/JSONExporter.cpp

708

I will tonight.

723

You don't need to redirect from CString to StringRef for a simple string comparison.

Try:

for (; ArrayIdx < Arrays.size(0; ArrayIdx++) {
  auto &Array = Arrays[ArrayIdx];
  ... (Replace usage of Arrays[ArrayIdx] with Array ...
  if (Array.isMember("allocation") {
    NewSAI->setIsOnHeap(Array["allocation"].asString() == "heap");
  }

[Meinersbur]

Once you extract the new ImportArrays test case (either create another review or ask Andreas to commit directly), IMHO this is ready to be committed as well.

test/Isl/CodeGen/MemAccess/create_arrays_heap.ll

33–38

Since we had a discussion about this, could you also CHECK for the name of the basic block this is inserted to (such as

CODEGEN: polly.start:

)

42–47

Here as well, e.g.,

CODEGEN: polly.exiting:

test/JSONExporter/ImportArrays/create_arrays_heap___%for.cond1.preheader---%for.end18.jscop.transformed

15

Coul you clean-up the test case by only reducing the size (I think only this line is relevant. the others can be removed by also removing theit accesses in the .ll file)
Also, try to give it a more meaningful name (e.g. rename the function to "ImportArrays_Negative_size") and add the original, unmodified .jscop file as written by -export-jscop.

[niosega]

• Refactor code in JSONExporter for heap allocation detection.
• Remove the test case concerning
• Add CHECK in the test case for malloc/free to check if the inserting positions are correct.

[simbuerg]

Allright, I just committed the size-check with test. From my side this patch is ready as soon as:

• Rebase is done
• Commit message gives a usefull description of what this patch does.

Currently the message is as follows:

Add the option to allocate arrays on heap instead of stack while creating new arrays.

For now, a cli option is used to enable the heap allocation. But at the end, this information will be included in the imported json file.

To allocate on the heap, I use the CreateMalloc function with the following parameters :

Instruction * InsertBefore : The same instruction used for stack allocation.
Type * IntPtrTy : For now, a int64.
Type * AllocTy : The type of an element of the array.
Value * AllocSize : The size of an element of the array.
Value * ArraySize : The product of the size of all dimensions.
Function * MallocF : nullptr to use the default malloc function.
const Twine &Name : The name of the SAI.

What we need here is a description of the patch, something that
answers:

• Where do we add what?
• When is it freed?
• Why do we need this?

[niosega]

Rebase with master to take into account the commit of the check size for JSONImporter.

[Meinersbur]

Could you change getPrimitiveSizeInBits() to getElemSizeInBytes() or explain why getPrimitiveSizeInBits() is needed here? Othewise, LGTM.

[niosega]

There are no valid reasons not to use getElemSizeInBytes instead of getPrimitiveSizeInBits. This solution (with getElemSizeInBytes) is much more cleaner.

[Meinersbur]

LGTM, I am going to commit...

include/polly/CodeGen/IslNodeBuilder.h

public:
   ///
   /// @result An llvm::Value that is true if the condition holds and false
   ///         otherwise.
   Value *createRTC(isl_ast_expr *Condition);
 
   void create(__isl_take isl_ast_node *Node);
 
   /// Allocate memory for all new arrays created by Polly.
-  void allocateNewArrays();
+  void allocateNewArrays(BBPair StartExitBlocks);
 
   /// Preload all memory loads that are invariant.
   bool preloadInvariantLoads();
 
   /// Finalize code generation.
   ///
   /// @see BlockGenerator::finalizeSCoP(Scop &S)
   virtual void finalize() { BlockGen.finalizeSCoP(S); }

include/polly/ScopInfo.h

public:
   ~ScopArrayInfo();
 
   /// Set the base pointer to @p BP.
   void setBasePtr(Value *BP) { BasePtr = BP; }
 
   /// Return the base pointer.
   Value *getBasePtr() const { return BasePtr; }
 
+  // Set IsOnHeap to the value in parameter.
+  void setIsOnHeap(bool value) { IsOnHeap = value; }
+
   /// For indirect accesses return the origin SAI of the BP, else null.
   const ScopArrayInfo *getBasePtrOriginSAI() const { return BasePtrOriginSAI; }
 
   /// The set of derived indirect SAIs for this origin SAI.
   const SmallSetVector<ScopArrayInfo *, 2> &getDerivedSAIs() const {
     return DerivedSAIs;
   }
 
public:
   bool isPHIKind() const { return Kind == MemoryKind::PHI; }
 
   /// Is this array info modeling an MemoryKind::ExitPHI?
   bool isExitPHIKind() const { return Kind == MemoryKind::ExitPHI; }
 
   /// Is this array info modeling an array?
   bool isArrayKind() const { return Kind == MemoryKind::Array; }
 
+  /// Is this array allocated on heap
+  ///
+  /// This property is only relevant if the array is allocated by Polly instead
+  /// of pre-existing. If false, it is allocated using alloca instead malloca.
+  bool isOnHeap() const { return IsOnHeap; }
+
   /// Dump a readable representation to stderr.
   void dump() const;
 
   /// Print a readable representation to @p OS.
   ///
   /// @param SizeAsPwAff Print the size as isl_pw_aff
   void print(raw_ostream &OS, bool SizeAsPwAff = false) const;
 
private:
   /// but the allocation size of the type of the elements loaded/stored from/to
   /// this array needs to be a multiple of the allocation size of the canonical
   /// type.
   Type *ElementType;
 
   /// The isl id for the base pointer.
   isl_id *Id;
 
+  /// True if the newly allocated array is on heap.
+  bool IsOnHeap;
+
   /// The sizes of each dimension as SCEV*.
   SmallVector<const SCEV *, 4> DimensionSizes;
 
   /// The sizes of each dimension as isl_pw_aff.
   SmallVector<isl_pw_aff *, 4> DimensionSizesPw;
 
   /// The type of this scop array info object.
   ///
public:
 
   const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; }
 
   /// 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,
-                                                MemoryKind Kind,
-                                                const char *BaseName = nullptr);
+  ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
 
   /// 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);
+  ScopArrayInfo *createScopArrayInfo(Type *ElementType,
 
   /// 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.
   ///
   /// @returns The ScopArrayInfo pointer or NULL if no such pointer is
   ///          available.

lib/Analysis/ScopInfo.cpp

static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
   return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
                              MemoryKind::Array);
 }
 
 ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx,
                              ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
                              const DataLayout &DL, Scop *S,
                              const char *BaseName)
-    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S),
-      FAD(nullptr) {
+    : BasePtr(BasePtr), ElementType(ElementType), IsOnHeap(false), Kind(Kind),
+      DL(DL), S(*S), FAD(nullptr) {
   std::string BasePtrName =
       BaseName ? BaseName
                : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),
                                       Kind == MemoryKind::PHI ? "__phi" : "",
                                       UseInstructionNames);
   Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
 
   updateSizes(Sizes);
for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
       if (isUsedForIndirectHoistedLoad(this, BasePtrSAI))
         continue;
 
       replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
     }
   }
 }
 
-const ScopArrayInfo *
-Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
-                               ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
+ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
+                                              ArrayRef<const SCEV *> Sizes,
+                                              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, 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,
+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)
     if (size)
       SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));
     else
       SCEVSizes.push_back(nullptr);

lib/CodeGen/CodeGeneration.cpp

static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
 
   removeLifetimeMarkers(R);
   auto *SplitBlock = StartBlock->getSinglePredecessor();
 
   IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
 
   // All arrays must have their base pointers known before
   // ScopAnnotator::buildAliasScopes.
-  NodeBuilder.allocateNewArrays();
+  NodeBuilder.allocateNewArrays(StartExitBlocks);
   Annotator.buildAliasScopes(S);
 
   if (PerfMonitoring) {
     PerfMonitor P(S, EnteringBB->getParent()->getParent());
     P.initialize();
     P.insertRegionStart(SplitBlock->getTerminator());
 
     BasicBlock *MergeBlock = ExitBlock->getUniqueSuccessor();
if (!NodeBuilder.preloadInvariantLoads()) {
     DT.eraseNode(ExitingBlock);
 
     isl_ast_node_free(AstRoot);
   } else {
     NodeBuilder.addParameters(S.getContext());
     Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
 
     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
-    Builder.SetInsertPoint(&StartBlock->front());
+
+    // Explicitly set the insert point to the end of the block to avoid that a
+    // split at the builder's current
+    // insert position would move the malloc calls to the wrong BasicBlock.
+    // Ideally we would just split the block during allocation of the new
+    // arrays, but this would break the assumption that there are no blocks
+    // between polly.start and polly.exiting (at this point).
+    Builder.SetInsertPoint(StartBlock->getTerminator());
 
     NodeBuilder.create(AstRoot);
     NodeBuilder.finalize();
     fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
   }
 
   Function *F = EnteringBB->getParent();
   verifyGeneratedFunction(S, *F, AI);

lib/CodeGen/IslNodeBuilder.cpp

for (const MemoryAccess *MA : MAs) {
 
     EscapeMap[MA->getAccessInstruction()] =
         std::make_pair(Alloca, std::move(EscapeUsers));
   }
 
   return true;
 }
 
-void IslNodeBuilder::allocateNewArrays() {
+void IslNodeBuilder::allocateNewArrays(BBPair StartExitBlocks) {
   for (auto &SAI : S.arrays()) {
     if (SAI->getBasePtr())
       continue;
 
     assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&
            "The size of the outermost dimension is used to declare newly "
            "created arrays that require memory allocation.");
 
     Type *NewArrayType = nullptr;
+
+    // Get the size of the array = size(dim_1)*...*size(dim_n)
+    uint64_t ArraySizeInt = 1;
     for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; 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);
+      ArraySizeInt *= UnsignedDimSize;
     }
 
-    auto InstIt =
-        Builder.GetInsertBlock()->getParent()->getEntryBlock().getTerminator();
+    if (SAI->isOnHeap()) {
+      LLVMContext &Ctx = NewArrayType->getContext();
+
+      // Get the IntPtrTy from the Datalayout
+      auto IntPtrTy = DL.getIntPtrType(Ctx);
+
+      // Get the size of the element type in bits
+      unsigned Size = SAI->getElementType()->getPrimitiveSizeInBits() / 8;
+
+      // Insert the malloc call at polly.start
+      auto InstIt = std::get<0>(StartExitBlocks)->getTerminator();
+      auto *CreatedArray = CallInst::CreateMalloc(
+          &*InstIt, IntPtrTy, SAI->getElementType(),
+          ConstantInt::get(Type::getInt64Ty(Ctx), Size),
+          ConstantInt::get(Type::getInt64Ty(Ctx), ArraySizeInt), nullptr,
+          SAI->getName());
+
+      SAI->setBasePtr(CreatedArray);
+
+      // Insert the free call at polly.exiting
+      CallInst::CreateFree(CreatedArray,
+                           std::get<1>(StartExitBlocks)->getTerminator());
+
+    } else {
+      auto InstIt = Builder.GetInsertBlock()
+                        ->getParent()
+                        ->getEntryBlock()
+                        .getTerminator();
+
       auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(),
                                           SAI->getName(), &*InstIt);
       CreatedArray->setAlignment(PollyTargetFirstLevelCacheLineSize);
       SAI->setBasePtr(CreatedArray);
     }
   }
+}
 
 bool IslNodeBuilder::preloadInvariantLoads() {
 
   auto &InvariantEquivClasses = S.getInvariantAccesses();
   if (InvariantEquivClasses.empty())
     return true;
 
   BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),

lib/Exchange/JSONExporter.cpp

bool JSONImporter::importArrays(Scop &S, Json::Value &JScop) {
   for (; ArrayIdx < Arrays.size(); ArrayIdx++) {
     auto *ElementType = parseTextType(Arrays[ArrayIdx]["type"].asCString(),
                                       S.getSE()->getContext());
     if (!ElementType) {
       errs() << "Error while parsing element type for new array.\n";
       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);
+    for (unsigned i = 0; i < Arrays[ArrayIdx]["sizes"].size(); i++) {
+      auto Size = std::stoi(Arrays[ArrayIdx]["sizes"][i].asCString());
+
+      // Check if the size if positive.
+      if (Size <= 0) {
+        errs() << "The size at index " << i << " is =< 0.\n";
+        return false;
+      }
+      DimSizes.push_back(Size);
+    }
+
+    auto NewSAI = S.createScopArrayInfo(
+        ElementType, Arrays[ArrayIdx]["name"].asCString(), DimSizes);
+
+    if (Arrays[ArrayIdx].isMember("allocation")) {
+      StringRef AllocationString(Arrays[ArrayIdx]["allocation"].asCString());
+      if (AllocationString.compare("heap") == 0) {
+        NewSAI->setIsOnHeap(true);
+      }
+    }
   }
 
   return true;
 }
 
 bool JSONImporter::runOnScop(Scop &S) {
   const Dependences &D =
       getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);

test/Isl/CodeGen/MemAccess/create_arrays_heap.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-import-jscop-dir=%S -polly-import-jscop -polly-import-jscop-postfix=transformed < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-import-jscop-dir=%S -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-codegen -S < %s | FileCheck %s --check-prefix=CODEGEN
+;
+; #define Ni 1056
+; #define Nj 1056
+; #define Nk 1024
+;
+; void create_arrays_heap(double beta, double A[Ni][Nk], double B[Ni][Nj]) {
+;   int i,j,k;
+;
+;   for (i = 0; i < Ni; i++) {
+;     for (j = 0; j < Nj; j++) {
+;       for (k = 0; k < Nk; ++k) {
+;   B[i][j] = beta * A[i][k];
+;       }
+;     }
+;   }
+; }
+;
+; Check if the info from the JSON file has been analysed without errors.
+; CHECK: Arrays {
+; CHECK: double MemRef_A[*][1024]; // Element size 8
+; CHECK: double MemRef_beta; // Element size 8
+; CHECK: double MemRef_B[*][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 if there are the 3 expected malloc calls with the right parameters.
+;   %D : size(D) = product_all_dimensions*sizeof(type) = 270336*8 = 2162688 cast to double*
+; %E : size(E) = 270336*200000*8 = 432537600000 cast to double*
+;   %F : size(F) = 270336*8 = 2162688 cast to i64*
+; CODEGEN: %malloccall = tail call i8* @malloc(i64 2162688)
+; CODEGEN: %D = bitcast i8* %malloccall to double*
+; CODEGEN: %malloccall1 = tail call i8* @malloc(i64 432537600000)
+; CODEGEN: %E = bitcast i8* %malloccall1 to double*
+; CODEGEN: %malloccall2 = tail call i8* @malloc(i64 2162688)
+; CODEGEN: %F = bitcast i8* %malloccall2 to i64*
+;
+; Check if there are the 3 expected malloc calls with the right parameters.
+;   Cast to i8* before freeing because malloc give us a i8 and free is waiting for a i8*
+; CODEGEN: %12 = bitcast double* %D to i8*
+; CODEGEN: tail call void @free(i8* %12)
+; CODEGEN: %13 = bitcast double* %E to i8*
+; CODEGEN: tail call void @free(i8* %13)
+; CODEGEN: %14 = bitcast i64* %F to i8*
+; CODEGEN: tail call void @free(i8* %14)
+;
+; Check if the new access for array E is present.
+; CODEGEN: %polly.access.mul.E = mul nsw i64 %polly.indvar, 200000
+; CODEGEN: %polly.access.add.E = add nsw i64 %polly.access.mul.E, %
+; CODEGEN: %polly.access.E = getelementptr double, double* %E, i64 %polly.access.add.E
+;
+; ModuleID = 'create_arrays_heap.ll'
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @create_arrays_heap(double %beta, [1024 x double]* nocapture readonly %A, [1056 x double]* nocapture %B) local_unnamed_addr {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.inc16, %entry
+  %indvars.iv35 = phi i64 [ 0, %entry ], [ %indvars.iv.next36, %for.inc16 ]
+  br label %for.cond4.preheader
+
+for.cond4.preheader:                              ; preds = %for.inc13, %for.cond1.preheader
+  %indvars.iv32 = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next33, %for.inc13 ]
+  %arrayidx12 = getelementptr inbounds [1056 x double], [1056 x double]* %B, i64 %indvars.iv35, i64 %indvars.iv32
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body6, %for.cond4.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond4.preheader ], [ %indvars.iv.next.3, %for.body6 ]
+  %arrayidx8 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv
+  %0 = load double, double* %arrayidx8, align 8
+  %mul = fmul double %0, %beta
+  store double %mul, double* %arrayidx12, align 8
+  %indvars.iv.next = or i64 %indvars.iv, 1
+  %arrayidx8.1 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv.next
+  %1 = load double, double* %arrayidx8.1, align 8
+  %mul.1 = fmul double %1, %beta
+  store double %mul.1, double* %arrayidx12, align 8
+  %indvars.iv.next.1 = or i64 %indvars.iv, 2
+  %arrayidx8.2 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv.next.1
+  %2 = load double, double* %arrayidx8.2, align 8
+  %mul.2 = fmul double %2, %beta
+  store double %mul.2, double* %arrayidx12, align 8
+  %indvars.iv.next.2 = or i64 %indvars.iv, 3
+  %arrayidx8.3 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv.next.2
+  %3 = load double, double* %arrayidx8.3, align 8
+  %mul.3 = fmul double %3, %beta
+  store double %mul.3, double* %arrayidx12, align 8
+  %indvars.iv.next.3 = add nsw i64 %indvars.iv, 4
+  %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024
+  br i1 %exitcond.3, label %for.inc13, label %for.body6
+
+for.inc13:                                        ; preds = %for.body6
+  %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1
+  %exitcond34 = icmp eq i64 %indvars.iv.next33, 1056
+  br i1 %exitcond34, label %for.inc16, label %for.cond4.preheader
+
+for.inc16:                                        ; preds = %for.inc13
+  %indvars.iv.next36 = add nuw nsw i64 %indvars.iv35, 1
+  %exitcond37 = icmp eq i64 %indvars.iv.next36, 1056
+  br i1 %exitcond37, label %for.end18, label %for.cond1.preheader
+
+for.end18:                                        ; preds = %for.inc16
+  ret void
+}
+

test/Isl/CodeGen/MemAccess/create_arrays_heap___%for.cond1.preheader---%for.end18.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*", "1024" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_B",
+         "sizes" : [ "*", "1056" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "{  :  }",
+   "location" : "pure_c_main.c:11-16",
+   "name" : "%for.cond1.preheader---%for.end18",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_A[i0, 4i2] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_beta[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_A[i0, 1 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_A[i0, 2 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_A[i0, 3 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            }
+         ],
+         "domain" : "{ Stmt2[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 255 }",
+         "name" : "Stmt2",
+         "schedule" : "{ Stmt2[i0, i1, i2] -> [i0, i1, i2] }"
+      }
+   ]
+}

test/Isl/CodeGen/MemAccess/create_arrays_heap___%for.cond1.preheader---%for.end18.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*", "1024" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_B",
+         "sizes" : [ "*", "1056" ],
+         "type" : "double"
+      },
+      {
+         "name" : "D",
+         "sizes" : [ "270336" ],
+         "type" : "double",
+   "allocation" : "heap"
+      },
+      {
+         "name" : "E",
+         "sizes" : [ "270336", "200000" ],
+         "type" : "double",
+   "allocation" : "heap"
+      },
+      {
+         "name" : "F",
+         "sizes" : [ "270336" ],
+         "type" : "i64",
+   "allocation" : "heap"
+      }
+   ],
+   "context" : "{  :  }",
+   "location" : "pure_c_main.c:11-16",
+   "name" : "%for.cond1.preheader---%for.end18",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 4i2] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_beta[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 1 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 2 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 3 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            }
+         ],
+         "domain" : "{ Stmt2[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 255 }",
+         "name" : "Stmt2",
+         "schedule" : "{ Stmt2[i0, i1, i2] -> [i0, i1, i2] }"
+      }
+   ]
+}

test/JSONExporter/ImportArrays/ImportArrays-Negative-size.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
+;
+; #define Ni 1056
+; #define Nj 1056
+; #define Nk 1024
+;
+; void create_arrays_heap(double beta, double A[Ni][Nk], double B[Ni][Nj]) {
+;   int i,j,k;
+;
+;   for (i = 0; i < Ni; i++) {
+;     for (j = 0; j < Nj; j++) {
+;       for (k = 0; k < Nk; ++k) {
+;   B[i][j] = beta * A[i][k];
+;       }
+;     }
+;   }
+; }
+;
+; Verify if the JSONImporter checks if the size of the new array is positive.
+; CHECK: The size at index 0 is =< 0.
+;
+; ModuleID = 'create_arrays_heap.ll'
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @create_arrays_heap(double %beta, [1024 x double]* nocapture readonly %A, [1056 x double]* nocapture %B) local_unnamed_addr {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.inc16, %entry
+  %indvars.iv35 = phi i64 [ 0, %entry ], [ %indvars.iv.next36, %for.inc16 ]
+  br label %for.cond4.preheader
+
+for.cond4.preheader:                              ; preds = %for.inc13, %for.cond1.preheader
+  %indvars.iv32 = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next33, %for.inc13 ]
+  %arrayidx12 = getelementptr inbounds [1056 x double], [1056 x double]* %B, i64 %indvars.iv35, i64 %indvars.iv32
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body6, %for.cond4.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond4.preheader ], [ %indvars.iv.next.3, %for.body6 ]
+  %arrayidx8 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv
+  %0 = load double, double* %arrayidx8, align 8
+  %mul = fmul double %0, %beta
+  store double %mul, double* %arrayidx12, align 8
+  %indvars.iv.next = or i64 %indvars.iv, 1
+  %arrayidx8.1 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv.next
+  %1 = load double, double* %arrayidx8.1, align 8
+  %mul.1 = fmul double %1, %beta
+  store double %mul.1, double* %arrayidx12, align 8
+  %indvars.iv.next.1 = or i64 %indvars.iv, 2
+  %arrayidx8.2 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv.next.1
+  %2 = load double, double* %arrayidx8.2, align 8
+  %mul.2 = fmul double %2, %beta
+  store double %mul.2, double* %arrayidx12, align 8
+  %indvars.iv.next.2 = or i64 %indvars.iv, 3
+  %arrayidx8.3 = getelementptr inbounds [1024 x double], [1024 x double]* %A, i64 %indvars.iv35, i64 %indvars.iv.next.2
+  %3 = load double, double* %arrayidx8.3, align 8
+  %mul.3 = fmul double %3, %beta
+  store double %mul.3, double* %arrayidx12, align 8
+  %indvars.iv.next.3 = add nsw i64 %indvars.iv, 4
+  %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024
+  br i1 %exitcond.3, label %for.inc13, label %for.body6
+
+for.inc13:                                        ; preds = %for.body6
+  %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1
+  %exitcond34 = icmp eq i64 %indvars.iv.next33, 1056
+  br i1 %exitcond34, label %for.inc16, label %for.cond4.preheader
+
+for.inc16:                                        ; preds = %for.inc13
+  %indvars.iv.next36 = add nuw nsw i64 %indvars.iv35, 1
+  %exitcond37 = icmp eq i64 %indvars.iv.next36, 1056
+  br i1 %exitcond37, label %for.end18, label %for.cond1.preheader
+
+for.end18:                                        ; preds = %for.inc16
+  ret void
+}
+

test/JSONExporter/ImportArrays/create_arrays_heap___%for.cond1.preheader---%for.end18.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*", "1024" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_B",
+         "sizes" : [ "*", "1056" ],
+         "type" : "double"
+      },
+      {
+         "name" : "D",
+         "sizes" : [ "-270336" ],
+         "type" : "double",
+   "allocation" : "heap"
+      },
+      {
+         "name" : "E",
+         "sizes" : [ "270336", "200000" ],
+         "type" : "double",
+   "allocation" : "heap"
+      },
+      {
+         "name" : "F",
+         "sizes" : [ "270336" ],
+         "type" : "i64",
+   "allocation" : "heap"
+      }
+   ],
+   "context" : "{  :  }",
+   "location" : "pure_c_main.c:11-16",
+   "name" : "%for.cond1.preheader---%for.end18",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 4i2] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_beta[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 1 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 2 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt2[i0, i1, i2] -> E[i0, 3 + 4i2] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0, i1, i2] -> MemRef_B[i0, i1] }"
+            }
+         ],
+         "domain" : "{ Stmt2[i0, i1, i2] : 0 <= i0 <= 1055 and 0 <= i1 <= 1055 and 0 <= i2 <= 255 }",
+         "name" : "Stmt2",
+         "schedule" : "{ Stmt2[i0, i1, i2] -> [i0, i1, i2] }"
+      }
+   ]
+}