[Polly] Store the size of the outermost dimension in case of newly created arrays that require memory allocation.

[gareevroman]

Summary

We do not need the size of the outermost dimension in most cases, but if we allocate memory for newly created arrays, that size is needed.

[Meinersbur]

Thank you for the patch.

lib/Analysis/ScopInfo.cpp

221–225

This is probably not relevant at the moment because updateSizes is only called on previosly existing array:

This unconditionally ignores the first dimension size. I think this is only because NewSizes[0 + ExtraDimsNew] is NULL. not an intrinisic property of sizes.

1086

Wouldn't it be better to already prepend nullptr in Access->Sizes when it is created? We'd have consistently all dimension size arrays having as many elements as array indices, instead some with nullptr as first element, others with one element less.

lib/CodeGen/IslNodeBuilder.cpp

1163

getNumberOfDimensions() return an unsigned int. 0u - 1 is undefined behaviour.

test/Isl/CodeGen/MemAccess/create_arrays.ll

15

Should this be double E[270336][200000]?
You may need to update the print function to only print '*' if sizes[0] is nullptr.

30

Well Done!

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

5

Nice

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

36

Nice

[gareevroman]

A new version updated according to the comments.

[gareevroman]

Hi Michael,

thank you for the comments!

lib/Analysis/ScopInfo.cpp

221–225

This is probably not relevant at the moment because updateSizes is only called on previosly existing array:

I think that it's relevant even in case of previosly existing array. Let's consider, for example, llvm/tools/polly/test/ScopInfo/user_provided_assumptions.ll. In this case, if try to build the following memory access,

            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
                [N, M] -> { Stmt_for_body_22[i0, i1] -> MemRef_C[i0, i1] };

we should be able to update dimension sizes of MemRef_C and change them from [*] to [*], [100].

lib/CodeGen/IslNodeBuilder.cpp

1163

I've added an additional condition to check it.

[Meinersbur]

LGTM

lib/Analysis/ScopInfo.cpp

855

this->Sizes.insert is usually used to get the member instead of the parameter of the same name.

Can you make the caller prepend nullptr entry? I think it makes sense for consistency and in case we create MemoryAccesses with this constructer where we know what the outermost size is.

lib/CodeGen/IslNodeBuilder.cpp

1158–1160

Good idea

[gareevroman]

A new version updated according to the comments.

[gareevroman]

Hi Michael,

thank you for the review!

However, I'm not sure whether we should ignore the first dimension size of all kinds of memory accesses. Should we do it only in case of MK_Arrays that are not newly created? I've added this condition in the new version of patch and also updated the comment that corresponds to ScopArrayInfo::updateSizes.

lib/Analysis/ScopInfo.cpp

855

Maybe the callers of addArrayAccess should prepend nullptr entry. What do you think about it?

[Meinersbur]

In D23991#530013, @gareevroman wrote:

However, I'm not sure whether we should ignore the first dimension size of all kinds of memory accesses. Should we do it only in case of MK_Arrays that are not newly created? I've added this condition in the new version of patch and also updated the comment that corresponds to ScopArrayInfo::updateSizes.

I understand that nullptr as dimension size means "I don't know the dimension's size"/"I it can be any value". updateSizes checks if the new array size is in conflict with the old one and returns false if it is. Seeing nullptr in this interpretation means "I don't know the size yet, but if the caller tells me it is this size, I will update it to this size."

That is, instead of ignoring the first size dimensions on some condition, we should check whether it is nullptr.
If it is nullptr -> No conflict, continue and update size
Not nullptr, same value as new size -> No conflict, continue
Not nullptr, different value than old -> Discordant sizes, bail-out (return false)

This is hypothetical since, AFAIK, updateSizes is only called during polly-scops pass when there are no newly created arrays (yet).

For non-MK_Arrays, the sizes are not relevant. It could have valid values of:

• {} (empty sizes array)
• {nullptr} (unknown size)
• {1} (exactly one element; scalar)

Probably the last is "most accurate", but I don't really have a preference here. Use whatever works best.
Actually, this gives me the idea that would could handle such scalar ScopArrayInfos as a special case of newly created arrays, since for both we are going to create allocas for which we need the size.

What do you think?

Michael

lib/Analysis/ScopInfo.cpp

855

Yes, that's what I meant.

[gareevroman]

A new version updated according to the comments.

[gareevroman]

Hi Michael,

sorry for the late reply.

I understand that nullptr as dimension size means "I don't know the dimension's size"/"I it can be any value". updateSizes checks if the new array size is in conflict with the old one and returns false if it is. Seeing nullptr in this interpretation means "I don't know the size yet, but if the caller tells me it is this size, I will update it to this size."

That is, instead of ignoring the first size dimensions on some condition, we should check whether it is nullptr.
If it is nullptr -> No conflict, continue and update size
Not nullptr, same value as new size -> No conflict, continue
Not nullptr, different value than old -> Discordant sizes, bail-out (return false)

I agree with it. ScopArrayInfo::updateSizes was modified according to these comments.

This is hypothetical since, AFAIK, updateSizes is only called during polly-scops pass when there are no newly created arrays (yet).

If I'm not mistaken, after application of the patch the first dimensions can be nullptr even when there are no newly created arrays. To check it, we can, for example, add the following code to the updateSizes and run 'make check-polly'.

if (DimensionSizes.size() > 0 && !DimensionSizes[0])
  abort();

For non-MK_Arrays, the sizes are not relevant. It could have valid values of:

{} (empty sizes array)
{nullptr} (unknown size)
{1} (exactly one element; scalar)
Probably the last is "most accurate", but I don't really have a preference here. Use whatever works best.
Actually, this gives me the idea that would could handle such scalar ScopArrayInfos as a special case of newly created arrays, since for both we are going to create allocas for which we need the size.

What do you think?

I think that it's reasonable. Should we try to implement it in a separate patch?

[Meinersbur]

In D23991#539885, @gareevroman wrote:

sorry for the late reply.

np.

I agree with it. ScopArrayInfo::updateSizes was modified according to these comments.

The new diff still treats the first dimension specially, although there is nothing special about it (which is the motivation for my remarks). Here is what I had in mind:

for (int i = 0; i < SharedDims; i++) {
  auto &NewSize = NewSizes[i + ExtraDimsNew];
  auto &KnownSize = DimensionSizes[i + ExtraDimsOld];
  if (NewSize && KnownSize && NewSize != KnownSize)
   return false;
}

This is hypothetical since, AFAIK, updateSizes is only called during polly-scops pass when there are no newly created arrays (yet).

If I'm not mistaken, after application of the patch the first dimensions can be nullptr even when there are no newly created arrays. To check it, we can, for example, add the following code to the updateSizes and run 'make check-polly'.

if (DimensionSizes.size() > 0 && !DimensionSizes[0])
  abort();

I think that the first dimensions is always nullptr, and all others are never nullptr. This is what your code is written for, but we can be more general, where nullptr could be at any position.

For non-MK_Arrays, the sizes are not relevant. It could have valid values of:

{} (empty sizes array)
{nullptr} (unknown size)
{1} (exactly one element; scalar)
Probably the last is "most accurate", but I don't really have a preference here. Use whatever works best.
Actually, this gives me the idea that would could handle such scalar ScopArrayInfos as a special case of newly created arrays, since for both we are going to create allocas for which we need the size.

What do you think?

I think that it's reasonable. Should we try to implement it in a separate patch?

If you are interested, do it in a separate patch.

(I already accepted the patch as I think it is already functionally working, so go ahead if you feel to commit; this is only how I think the code could be 'nicer')

[gareevroman]

I think that the first dimensions is always nullptr, and all others are never nullptr. This is what your code is written for, but we can be more general, where nullptr could be at any position.

OK. If this is the case, we should probably add additional checks. For example, as far as I understand, DimSCEVs from IslExprBuilder::createAccessAddress should not be nullptrs.

If you are interested, do it in a separate patch.

(I already accepted the patch as I think it is already functionally working, so go ahead if you feel to commit; this is only how I think the code could be 'nicer')

OK. Thanks for the review!

[Meinersbur]

In D23991#540082, @gareevroman wrote:

I think that the first dimensions is always nullptr, and all others are never nullptr. This is what your code is written for, but we can be more general, where nullptr could be at any position.

OK. If this is the case, we should probably add additional checks. For example, as far as I understand, DimSCEVs from IslExprBuilder::createAccessAddress should not be nullptrs.

This is true. If we hit nullptr at code generation, we don't have collected enough information and should never happen.

OK. Thanks for the review!

Thanks for writing the patch.

include/polly/ScopInfo.h

public:
   const SmallPtrSetImpl<ScopArrayInfo *> &getDerivedSAIs() const {
     return DerivedSAIs;
   }
 
   /// Return the number of dimensions.
   unsigned getNumberOfDimensions() const {
     if (Kind == MK_PHI || Kind == MK_ExitPHI || Kind == MK_Value)
       return 0;
-    return DimensionSizes.size() + 1;
+    return DimensionSizes.size();
   }
 
   /// Return the size of dimension @p dim as SCEV*.
   //
   //  Scalars do not have array dimensions and the first dimension of
   //  a (possibly multi-dimensional) array also does not carry any size
-  //  information.
+  //  information, in case the array is not newly created.
   const SCEV *getDimensionSize(unsigned Dim) const {
-    assert(Dim > 0 && "Only dimensions larger than zero are sized.");
     assert(Dim < getNumberOfDimensions() && "Invalid dimension");
-    return DimensionSizes[Dim - 1];
+    return DimensionSizes[Dim];
   }
 
   /// Return the size of dimension @p dim as isl_pw_aff.
   //
   //  Scalars do not have array dimensions and the first dimension of
   //  a (possibly multi-dimensional) array also does not carry any size
-  //  information.
+  //  information, in case the array is not newly created.
   __isl_give isl_pw_aff *getDimensionSizePw(unsigned Dim) const {
-    assert(Dim > 0 && "Only dimensions larger than zero are sized.");
     assert(Dim < getNumberOfDimensions() && "Invalid dimension");
-    return isl_pw_aff_copy(DimensionSizesPw[Dim - 1]);
+    return isl_pw_aff_copy(DimensionSizesPw[Dim]);
   }
 
   /// Get the canonical element type of this array.
   ///
   /// @returns The canonical element type of this array.
   Type *getElementType() const { return ElementType; }
 
   /// Get element size in bytes.

lib/Analysis/ScopBuilder.cpp

for (auto *Subscript : Subscripts) {
     for (LoadInst *LInst : AccessILS)
       if (!ScopRIL.count(LInst))
         return false;
   }
 
   if (Sizes.empty())
     return false;
 
+  SizesSCEV.push_back(nullptr);
+
   for (auto V : Sizes)
     SizesSCEV.push_back(SE.getSCEV(
         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                  Subscripts, SizesSCEV, Val);
   return true;
 }
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, Loop *L) {
 
   assert(BasePointer && "Could not find base pointer");
 
   auto &InsnToMemAcc = scop->getInsnToMemAccMap();
   auto AccItr = InsnToMemAcc.find(Inst);
   if (AccItr == InsnToMemAcc.end())
     return false;
 
-  std::vector<const SCEV *> Sizes(
-      AccItr->second.Shape->DelinearizedSizes.begin(),
+  std::vector<const SCEV *> Sizes = {nullptr};
+
+  Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
                AccItr->second.Shape->DelinearizedSizes.end());
   // Remove the element size. This information is already provided by the
   // ElementSize parameter. In case the element size of this access and the
   // element size used for delinearization differs the delinearization is
   // incorrect. Hence, we invalidate the scop.
   //
   // TODO: Handle delinearization with differing element sizes.
   auto DelinearizedSize =
       cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L) {
   if (DestAccFunc->isZero())
     return true;
 
   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
   DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
-                 {DestAccFunc, LengthVal}, {}, Inst.getValueOperand());
+                 {DestAccFunc, LengthVal}, {nullptr}, Inst.getValueOperand());
 
   auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
   if (!MemTrans)
     return true;
 
   auto *SrcPtrVal = MemTrans->getSource();
   assert(SrcPtrVal);
 
   auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
   assert(SrcAccFunc);
   // Ignore accesses to "NULL".
   // TODO: See above TODO
   if (SrcAccFunc->isZero())
     return true;
 
   auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
   assert(SrcPtrSCEV);
   SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
-                 {SrcAccFunc, LengthVal}, {}, Inst.getValueOperand());
+                 {SrcAccFunc, LengthVal}, {nullptr}, Inst.getValueOperand());
 
   return true;
 }
 
 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, Loop *L) {
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)
for (const auto &Arg : CI->arg_operands()) {
         continue;
 
       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
       if (ArgSCEV->isZero())
         continue;
 
       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
       addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
-                     ArgBasePtr->getType(), false, {AF}, {}, CI);
+                     ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
     }
     return true;
   }
 
   return true;
 }
 
 void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, Loop *L) {
void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, Loop *L) {
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
-                 {AccessFunction}, {}, Val);
+                 {AccessFunction}, {nullptr}, Val);
 }
 
 void ScopBuilder::buildMemoryAccess(MemAccInst Inst, Loop *L) {
 
   if (buildAccessMemIntrinsic(Inst, L))
     return;
 
   if (buildAccessCallInst(Inst, L))
if (!scop->hasSingleExitEdge())
     buildAccessFunctions(*R.getExit(), nullptr,
                          /* IsExitBlock */ true);
 
   // Create memory accesses for global reads since all arrays are now known.
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
   for (auto *GlobalRead : GlobalReads)
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
-                     BP->getType(), false, {AF}, {}, GlobalRead);
+                     BP->getType(), false, {AF}, {nullptr}, GlobalRead);
 
   scop->init(AA, AC, DT, LI);
 }
 
 ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
                          const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
                          ScopDetection &SD, ScalarEvolution &SE)
     : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {

lib/Analysis/ScopInfo.cpp

if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {
     ElementType = IntegerType::get(ElementType->getContext(), GCD);
   }
 }
 
 bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes) {
   int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
   int ExtraDimsNew = NewSizes.size() - SharedDims;
   int ExtraDimsOld = DimensionSizes.size() - SharedDims;
-  for (int i = 0; i < SharedDims; i++)
+  int i = 0;
+  if (DimensionSizes.size() > 0 && !DimensionSizes[0])
+    i++;
+  for (; i < SharedDims; i++)
     if (NewSizes[i + ExtraDimsNew] != DimensionSizes[i + ExtraDimsOld])
       return false;
 
   if (DimensionSizes.size() >= NewSizes.size())
     return true;
 
   DimensionSizes.clear();
   DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
                         NewSizes.end());
   for (isl_pw_aff *Size : DimensionSizesPw)
     isl_pw_aff_free(Size);
   DimensionSizesPw.clear();
   for (const SCEV *Expr : DimensionSizes) {
+    if (!Expr) {
+      DimensionSizesPw.push_back(nullptr);
+      continue;
+    }
     isl_pw_aff *Size = S.getPwAffOnly(Expr);
     DimensionSizesPw.push_back(Size);
   }
   return true;
 }
 
 ScopArrayInfo::~ScopArrayInfo() {
   isl_id_free(Id);

 __isl_give isl_id *ScopArrayInfo::getBasePtrId() const {
   return isl_id_copy(Id);
 }
 
 void ScopArrayInfo::dump() const { print(errs()); }
 
 void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
   OS.indent(8) << *getElementType() << " " << getName();
-  if (getNumberOfDimensions() > 0)
+  unsigned u = 0;
+  if (getNumberOfDimensions() > 0 && !getDimensionSize(0)) {
     OS << "[*]";
-  for (unsigned u = 1; u < getNumberOfDimensions(); u++) {
+    u++;
+  }
+  for (; u < getNumberOfDimensions(); u++) {
     OS << "[";
 
     if (SizeAsPwAff) {
       auto *Size = getDimensionSizePw(u);
       OS << " " << Size << " ";
       isl_pw_aff_free(Size);
     } else {
       OS << *getDimensionSize(u);
const auto &Loc = getAccessInstruction()
                         : DebugLoc();
   Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
                                            AS_ASSUMPTION);
   isl_space_free(Space);
 }
 
 void MemoryAccess::buildMemIntrinsicAccessRelation() {
   assert(isa<MemIntrinsic>(getAccessInstruction()));
-  assert(Subscripts.size() == 2 && Sizes.size() == 0);
+  assert(Subscripts.size() == 2 && Sizes.size() == 1);
 
   auto *SubscriptPWA = getPwAff(Subscripts[0]);
   auto *SubscriptMap = isl_map_from_pw_aff(SubscriptPWA);
 
   isl_map *LengthMap;
   if (Subscripts[1] == nullptr) {
     LengthMap = isl_map_universe(isl_map_get_space(SubscriptMap));
   } else {

 
 __isl_give isl_map *MemoryAccess::foldAccess(__isl_take isl_map *AccessRelation,
                                              ScopStmt *Statement) {
   int Size = Subscripts.size();
 
   for (int i = Size - 2; i >= 0; --i) {
     isl_space *Space;
     isl_map *MapOne, *MapTwo;
-    isl_pw_aff *DimSize = getPwAff(Sizes[i]);
+    isl_pw_aff *DimSize = getPwAff(Sizes[i + 1]);
 
     isl_space *SpaceSize = isl_pw_aff_get_space(DimSize);
     isl_pw_aff_free(DimSize);
     isl_id *ParamId = isl_space_get_dim_id(SpaceSize, isl_dim_param, 0);
 
     Space = isl_map_get_space(AccessRelation);
     Space = isl_space_map_from_set(isl_space_range(Space));
     Space = isl_space_align_params(Space, SpaceSize);
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   AccessRelation = isl_map_universe(Space);
 
   for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
     isl_pw_aff *Affine = getPwAff(Subscripts[i]);
     isl_map *SubscriptMap = isl_map_from_pw_aff(Affine);
     AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap);
   }
 
-  if (Sizes.size() >= 1 && !isa<SCEVConstant>(Sizes[0]))
+  if (Sizes.size() >= 2 && !isa<SCEVConstant>(Sizes[1]))
     AccessRelation = foldAccess(AccessRelation, Statement);
 
   Space = Statement->getDomainSpace();
   AccessRelation = isl_map_set_tuple_id(
       AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
   AccessRelation =
       isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
 
: Kind(Kind), AccType(AccType), RedType(RT_NONE), Statement(Stmt),
       ElementType(ElementType), Sizes(Sizes.begin(), Sizes.end()),
       AccessInstruction(AccessInst), AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {
   static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
   const std::string Access = TypeStrings[AccType] + utostr(Stmt->size()) + "_";
 
   std::string IdName =
       getIslCompatibleName(Stmt->getBaseName(), Access, BaseName);
   Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
 }
 
 void MemoryAccess::realignParams() {
   auto *Ctx = Statement->getParent()->getContext();
   InvalidDomain = isl_set_gist_params(InvalidDomain, isl_set_copy(Ctx));
   AccessRelation = isl_map_gist_params(AccessRelation, Ctx);
 }
for (MemoryAccess *Access : MemAccs) {
     else if (Access->isExitPHIKind())
       Ty = ScopArrayInfo::MK_ExitPHI;
     else if (Access->isValueKind())
       Ty = ScopArrayInfo::MK_Value;
     else
       Ty = ScopArrayInfo::MK_Array;
 
     auto *SAI = S.getOrCreateScopArrayInfo(Access->getBaseAddr(), ElementType,
                                            Access->Sizes, Ty);
     Access->buildAccessRelation(SAI);
   }
 }
 
 void ScopStmt::addAccess(MemoryAccess *Access) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
   if (Access->isArrayKind()) {

 
 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)
+    if (size)
       SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));
+    else
+      SCEVSizes.push_back(nullptr);
 
   auto *SAI =
       getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
                                ScopArrayInfo::MK_Array, BaseName.c_str());
   return SAI;
 }
 
 const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr,

lib/CodeGen/IslNodeBuilder.cpp

bool IslNodeBuilder::preloadInvariantEquivClass(
   return true;
 }
 
 void IslNodeBuilder::allocateNewArrays() {
   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;
-    for (unsigned i = SAI->getNumberOfDimensions() - 1; i >= 1; i--) {
+    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();
 

lib/CodeGen/PPCGCodeGeneration.cpp

for (long i = 0; i < Kernel->n_array; i++) {
 
     isl_id *Id = isl_space_get_tuple_id(Prog->array[i].space, isl_dim_set);
     const ScopArrayInfo *SAI = ScopArrayInfo::getFromId(isl_id_copy(Id));
     Type *EleTy = SAI->getElementType();
     Value *Val = &*Arg;
     SmallVector<const SCEV *, 4> Sizes;
     isl_ast_build *Build =
         isl_ast_build_from_context(isl_set_copy(Prog->context));
+    Sizes.push_back(nullptr);
     for (long j = 1; j < Kernel->array[i].array->n_index; j++) {
       isl_ast_expr *DimSize = isl_ast_build_expr_from_pw_aff(
           Build, isl_pw_aff_copy(Kernel->array[i].array->bound[j]));
       auto V = ExprBuilder.create(DimSize);
       Sizes.push_back(SE.getSCEV(V));
     }
     const ScopArrayInfo *SAIRep =
         S.getOrCreateScopArrayInfo(Val, EleTy, Sizes, ScopArrayInfo::MK_Array);
void GPUNodeBuilder::createKernelVariables(ppcg_kernel *Kernel, Function *FN) {
   for (int i = 0; i < Kernel->n_var; ++i) {
     struct ppcg_kernel_var &Var = Kernel->var[i];
     isl_id *Id = isl_space_get_tuple_id(Var.array->space, isl_dim_set);
     Type *EleTy = ScopArrayInfo::getFromId(Id)->getElementType();
 
     Type *ArrayTy = EleTy;
     SmallVector<const SCEV *, 4> Sizes;
 
+    Sizes.push_back(nullptr);
     for (unsigned int j = 1; j < Var.array->n_index; ++j) {
       isl_val *Val = isl_vec_get_element_val(Var.size, j);
       long Bound = isl_val_get_num_si(Val);
       isl_val_free(Val);
       Sizes.push_back(S.getSE()->getConstant(Builder.getInt64Ty(), Bound));
     }
 
     for (int j = Var.array->n_index - 1; j >= 0; --j) {

lib/Exchange/JSONExporter.cpp

Json::Value exportArrays(const Scop &S) {
   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++) {
+    unsigned i = 0;
+    if (!SAI->getDimensionSize(i)) {
+      Array["sizes"].append("*");
+      i++;
+    }
+    for (; 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);

 /// 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)
+  if (SAI->getNumberOfDimensions() != Array["sizes"].size())
     return false;
 
-  for (unsigned i = 0; i < Array["sizes"].size(); i++) {
-    SAI->getDimensionSize(i + 1)->print(RawStringOstream);
+  for (unsigned i = 1; i < Array["sizes"].size(); i++) {
+    SAI->getDimensionSize(i)->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;

lib/Transform/ScheduleOptimizer.cpp

MemoryAccess *identifyAccessB(ScopStmt *Stmt) {
   auto *OriginalRel = getMatMulPatternOriginalAccessRelation(Stmt, 2, 1);
   return identifyAccessByAccessRelation(Stmt, OriginalRel);
 }
 
 /// Create an access relation that is specific to
 ///        the matrix multiplication pattern.
 ///
 /// Create an access relation of the following form:
-/// [O0, O1, O2, O3, O4, O5, O6, O7, O8] -> [0, O5 + K * OI, OJ],
+/// [O0, O1, O2, O3, O4, O5, O6, O7, O8] -> [O5 + K * OI, OJ],
 /// where K is @p Coeff, I is @p FirstDim, J is @p SecondDim.
 ///
 /// It can be used, for example, to create relations that helps to consequently
 /// access elements of operands of a matrix multiplication after creation of
 /// the BLIS micro and macro kernels.
 ///
 /// @see ScheduleTreeOptimizer::createMicroKernel
 /// @see ScheduleTreeOptimizer::createMacroKernel

 ///              relation.
 /// @param FirstDim, SecondDim The input dimensions that are used to define
 ///        the specified access relation.
 /// @return The specified access relation.
 __isl_give isl_map *getMatMulAccRel(__isl_take isl_map *MapOldIndVar,
                                     unsigned Coeff, unsigned FirstDim,
                                     unsigned SecondDim) {
   auto *Ctx = isl_map_get_ctx(MapOldIndVar);
-  auto *AccessRelSpace = isl_space_alloc(Ctx, 0, 9, 3);
+  auto *AccessRelSpace = isl_space_alloc(Ctx, 0, 9, 2);
   auto *AccessRel = isl_map_universe(isl_space_copy(AccessRelSpace));
   auto *ConstrSpace = isl_local_space_from_space(AccessRelSpace);
   auto *Constr = isl_constraint_alloc_equality(ConstrSpace);
-  Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_out, 1, -1);
+  Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_out, 0, -1);
   Constr = isl_constraint_set_coefficient_si(Constr, isl_dim_in, 5, 1);
   Constr =
       isl_constraint_set_coefficient_si(Constr, isl_dim_in, FirstDim, Coeff);
   AccessRel = isl_map_add_constraint(AccessRel, Constr);
-  AccessRel = isl_map_fix_si(AccessRel, isl_dim_out, 0, 0);
-  AccessRel = isl_map_equate(AccessRel, isl_dim_in, SecondDim, isl_dim_out, 2);
+  AccessRel = isl_map_equate(AccessRel, isl_dim_in, SecondDim, isl_dim_out, 1);
   return isl_map_apply_range(MapOldIndVar, AccessRel);
 }
 
 /// Apply the packing transformation.
 ///
 /// The packing transformation can be described as a data-layout
 /// transformation that requires to introduce a new array, copy data
 /// to the array, and change memory access locations of the compute kernel

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:        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[0, i2, i0] }' detected in JSCOP file
+; CHECK:New access function '{ Stmt_bb12[i0, i1, i2] -> E[i2, i0] }' detected in JSCOP file
 ;
 ; CODEGEN: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 {
 ; CODEGEN:bb:
 ; CODEGEN:  %beta.s2a = alloca double
 ; CODEGEN:  %D = alloca [270336 x double]
 ; CODEGEN:  %E = alloca [270336 x [200000 x double]]
 ; CODEGEN:  %F = alloca [270336 x i64]
 ; CODEGEN:  br label %bb8
 ;
 ; CODEGEN:  %beta.s2a.reload = load double, double* %beta.s2a
 ; CODEGEN:  %polly.access.cast.E = bitcast [270336 x [200000 x double]]* %E to double*
-; CODEGEN:  %polly.access.add.E = add nsw i64 0, %polly.indvar33
-; CODEGEN:  %polly.access.mul.E = mul nsw i64 %polly.access.add.E, 200000
-; CODEGEN:  %polly.access.add.E36 = add nsw i64 %polly.access.mul.E, %polly.indvar
+; CODEGEN:  %polly.access.mul.E = mul nsw i64 %polly.indvar33, 200000
+; 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

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

 {
    "arrays" : [
       {
          "name" : "MemRef_B",
-         "sizes" : [ "1024" ],
+         "sizes" : [ "*", "1024" ],
          "type" : "double"
       },
       {
          "name" : "MemRef_A",
-         "sizes" : [ "1056" ],
+         "sizes" : [ "*", "1056" ],
          "type" : "double"
       }
    ],
    "context" : "{  :  }",
    "name" : "%bb9---%bb26",
    "statements" : [
       {
          "accesses" : [

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

 {
    "arrays" : [
        {
          "name" : "MemRef_B",
-         "sizes" : [ "1024" ],
+         "sizes" : [ "*", "1024" ],
          "type" : "double"
       },
       {
          "name" : "MemRef_A",
-         "sizes" : [ "1056" ],
+         "sizes" : [ "*", "1056" ],
          "type" : "double"
       },
       {
          "name" : "D",
          "sizes" : [ "270336" ],
          "type" : "double"
       },
       {

    ],
    "context" : "{  :  }",
    "name" : "%bb9---%bb26",
    "statements" : [
       {
          "accesses" : [
             {
                "kind" : "read",
-               "relation" : "{ Stmt_bb12[i0, i1, i2] -> E[0, i2, i0] }"
+               "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] }"
       }
    ]
 }

test/Isl/CodeGen/MemAccess/map_scalar_access___%outer.for---%return.jscop

 {
    "arrays" : [
       {
          "name" : "MemRef_A",
+         "sizes" : [ "*" ],
          "type" : "double"
       }
    ],
    "context" : "{  :  }",
    "name" : "%outer.for---%return",
    "statements" : [
       {
          "accesses" : [

test/Isl/CodeGen/MemAccess/map_scalar_access___%outer.for---%return.jscop.transformed

 {
    "arrays" : [
       {
          "name" : "MemRef_A",
+         "sizes" : [ "*" ],
          "type" : "double"
       }
    ],
    "context" : "{  :  }",
    "name" : "%outer.for---%return",
    "statements" : [
       {
          "accesses" : [

test/ScheduleOptimizer/mat_mul_pattern_data_layout.ll

 ; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-througput-vector-fma=1 -polly-target-latency-vector-fma=8 -polly-target-cache-level-associativity=8,8 -polly-target-cache-level-sizes=32768,262144 -polly-optimized-scops < %s 2>&1 | FileCheck %s
 ;
 ;    /* C := alpha*A*B + beta*C */
 ;    for (i = 0; i < _PB_NI; i++)
 ;      for (j = 0; j < _PB_NJ; j++)
 ;        {
 ;    C[i][j] *= beta;
 ;    for (k = 0; k < _PB_NK; ++k)
 ;      C[i][j] += alpha * A[i][k] * B[k][j];
 ;        }
 ;
-; CHECK:        double Packed_A[*][ { [] -> [(1024)] } ][ { [] -> [(4)] } ]; // Element size 8
-; CHECK:        double Packed_B[*][ { [] -> [(3072)] } ][ { [] -> [(8)] } ]; // Element size 8
+; CHECK:        double Packed_A[ { [] -> [(1024)] } ][ { [] -> [(4)] } ]; // Element size 8
+; CHECK:        double Packed_B[ { [] -> [(3072)] } ][ { [] -> [(8)] } ]; // Element size 8
 ;
 ; CHECK:                { Stmt_bb14[i0, i1, i2] -> MemRef_arg6[i0, i2] };
-; CHECK:           new: { Stmt_bb14[i0, i1, i2] -> Packed_A[0, o1, o2] : 256*floor((-i2 + o1)/256) = -i2 + o1 and 4*floor((-i0 + o2)/4) = -i0 + o2 and 0 <= o2 <= 3 and -3 + i0 - 16*floor((i0)/16) <= 4*floor((o1)/256) <= i0 - 16*floor((i0)/16) };
+; CHECK:           new: { Stmt_bb14[i0, i1, i2] -> Packed_A[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 4*floor((-i0 + o1)/4) = -i0 + o1 and 0 <= o1 <= 3 and -3 + i0 - 16*floor((i0)/16) <= 4*floor((o0)/256) <= i0 - 16*floor((i0)/16) };
 ;
 ; CHECK:                { Stmt_bb14[i0, i1, i2] -> MemRef_arg7[i2, i1] };
-; CHECK:           new: { Stmt_bb14[i0, i1, i2] -> Packed_B[0, o1, o2] : 256*floor((-i2 + o1)/256) = -i2 + o1 and 8*floor((-i1 + o2)/8) = -i1 + o2 and 0 <= o2 <= 7 and -7 + i1 - 96*floor((i1)/96) <= 8*floor((o1)/256) <= i1 - 96*floor((i1)/96) };
+; CHECK:           new: { Stmt_bb14[i0, i1, i2] -> Packed_B[o0, o1] : 256*floor((-i2 + o0)/256) = -i2 + o0 and 8*floor((-i1 + o1)/8) = -i1 + o1 and 0 <= o1 <= 7 and -7 + i1 - 96*floor((i1)/96) <= 8*floor((o0)/256) <= i1 - 96*floor((i1)/96) };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-unknown"
 
 define internal void @kernel_gemm(i32 %arg, i32 %arg1, i32 %arg2, double %arg3, double %arg4, [1056 x double]* %arg5, [1024 x double]* %arg6, [1056 x double]* %arg7) #0 {
 bb:
   br label %bb8