[Polly] [WIP] Introduce ShapeInfo into polly for sizes and strides.

[cs15btech11044]

Summary

• Create a representation in Polly to disambiguate size based and stride based representations of arrays.
• I have never taught Codegen about strided arrays, so that is something we would need to do as well.
• Backport code to detect chapel/Fortran style indexing. TODO: Codegen
• There is code in IslExprBuilder which is responsible for actually lowering the multidimensional index expression. This needs to be backported. This will be the next commit.
• Attached a test case, which is causing when the false invalidate line is removed out in buildAccessPollyAbstractIndex()i
• Teaching PPCG codegen about our indexing function
• Fixed the memory allocation and index expression creation issue by modifying ShapeInfo class to take in only dimension sizes from Chapel Frontend and creating instruction in LLVM-IR pertaining to computation of block values from these dimension sizes
  • Modified getArrayOffset() to create proper extents for Chapel Arrays

[cs15btech11044]

Next Steps:

• There was a need to introduce a new kind of value map for this to work, a map from const SCEV * -> Value *. I hugely dislike this design, and would love to change this.

• Ideally the ScopArrayInfo should only save pw_aff. However, since we _do_ allow nonaffine indexing, this is not very sane. We need some point in the design space which is not so painful to work with.

• We need to test the stride code path from the chapel source code.

[philip.pfaffe]

I raised this concern already on Siddharth's version, but if this will succeed that I'll need to repeat it hear: ShapeInfo is pretty spaghetti, this should be fundamentally redesigned.

Why do we need to differentiate between strided and sized arrays? When does it matter? Physically these arrays are identical, so when are they treated differently?

[cs15btech11044]

Updated this patch according to Chapel's intrinsic conventions exclusively, thus it needs to be improved upon.
Only the ScopBuilder and ScopHelper are affected by this update.

[cs15btech11044]

lib/Analysis/ScopBuilder.cpp

752

@bollu. I am talking about this line here

[bollu]

lib/Analysis/ScopBuilder.cpp

752

Yeah, this looks like dead code that was left out. If you remove the line, then what happens?

Regarding Invalidate Scop

You mentioned that you get this error:

Invalidate SCoP because of reason 9

So, the reasons for invalidation are listed in this enum

cpp
enum AssumptionKind {
  ALIASING,
  INBOUNDS,
  WRAPPING,
  UNSIGNED,
  PROFITABLE,
  ERRORBLOCK,
  COMPLEXITY,
  INFINITELOOP,
  INVARIANTLOAD,
  DELINEARIZATION,
};

this is in include/polly/ScopInfo.h:98

Since DELINEARIZATION has enum value 10, it means that it someone called

invalidateScop(..., DELINERALIZATION, ....)

Which is the line you are pointing at. Removing this line should solve the problem.

[cs15btech11044]

lib/Analysis/ScopBuilder.cpp

752

Well, removing this line is causing an assertion failure in isl_map.c.
Whereas keeping it is still showing the SCoP and telling that it is invalidated.

[bollu]

lib/Analysis/ScopBuilder.cpp

752

That is interesting. Could you hunt down the assertion in isl_map.c?? That line is definitely wrong, because it just throws away our delineralisation.

[cs15btech11044]

lib/Analysis/ScopBuilder.cpp

752

The assertion is failing in

for (unsigned i = 0; i < DimsMissing; i++)
    Map = Map.fix_si(isl::dim::out, i, 0);

in updateDimensionality of ScopInfo.cpp.
Assertion "pos < isl_map_dim(map, type)" has failed in isl_map.c

[bollu]

lib/Analysis/ScopBuilder.cpp

752

Could you please create a minimal test case where this occurs?

[cs15btech11044]

Added the minimal test case, which is causing isl_map assertion failure.

[bollu]

lib/Analysis/ScopBuilder.cpp

757

@cs15btech11044, Here is where we add an array access from the Subscripts that we have derived.

If we derive Subscripts incorrectly, we will record an incorrect array shape (and possibly an incorrect array index).

Here is where the "link" between our "intrinsic" and Polly's array modelling happens.

[cs15btech11044]

Updates made in this patch:

• There were some places which were strictly using size representation for their purpose. These failed whenever we relied on stride based representation. Some changes were made to ShapeInfo to allow flexible usage of Sizes or Shapes vector depending on their availability.

Test case is not yet updated. I will update it in the next diff update.

[cs15btech11044]

Updated the test case for reference.

[cs15btech11044]

• Added the changes related to IslNodeBuilder and IslExprBuilder which were using ShapeInfo related information
• In PPCGCodeGeneration, handling of polly_array_index() has been taken care of.
• An extra test case has been added to the GPGPU/ demonstrating the crash related to improper context generation in the SCoP.

[cs15btech11044]

Modified getFortranArrayIds() to check over all dimensions of the array.

[cs15btech11044]

Changes made to this diff

• Fixed the complementing memory allocation and index expression problems by making some design changes in ShapeInfo class. The main reason for this change is that the block values which chapel uses aren't exactly the array sizes per dimension. So there arises a need to include the parameters to ShapeInfo which corresponds to actual array sizes.

[cs15btech11044]

Optimized the previous patch by passing only dimension Sizes and injecting LLVM-IR related to computation of block values from Dimension Sizes

[Meinersbur]

As mentioned in the last phone call, I think we should not use 'Stride' as an alternative to row-major indexing. The primary reason is that there are no unique coordinates for a single memory location which means we cannot accurately compute dependencies. Indeed, the delinearization stuff is all about ensuring that there is no unpredictable aliasing.

If offsets are required, this can be added as padding between rows. The default row-major address computation for a 4-dimensional tensor of size n1×n2×n3×n4 at index (i1,i2,i3,i4) is:

address = base + ((i1*n2 + i2)*n3 + i3)*n4 + i4 = i1*n2*n3*n4 + i2*n3*n4 + i3*n4 + i4*1
                                                     ^~~~~~~^      ^~~~^      ^^      ^ 
                                                     These coefficients are what I interpret as 'strides'

(note that if the strides are precomputed, both representations have the same number of operations)
or

address = base + (((i1*n2 + i2)*n3 + i3)*n4 + i4)*sizeof(*address)

when we compute in byte units.

With padding of p1,p2,p3,p4 bytes between elements (i.e. p4 is the number of bytes we insert after every element) we get an expression such as

address = base + (sizeof(*address) + p4)*i4;
                 ^~~~~~~~~~~~~~~~~~~~~~^
                 size per element incl padding

in one dimension.

address = base + ((sizeof(*address) + p4)*n4 + p3)*i3 + (sizeof(*address) + p4)*i4;
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~^            ^~~~~~~~~~~~~~~~~~~~~~~~~^
                 size of lower-dim line                 Index in that line

in two dimensions.

address = base + (((sizeof(*address) + p4)*n4 + p3)*n3 + p2)*i2 + ((sizeof(*address) + p4)*n4 + p3)*i3 + (sizeof(*address) + p4)*i4;

in three dimensions.

address = base + ((((p4 + sizeof(*address))*n4 + p3)*n3 + p2)*n2 + p1)*i1 + (((p4 + sizeof(*address))*n4 + p3)*n3 + p2)*i2 + ((p4 + sizeof(*address))*n4 + p3)*i3 + (p4 + sizeof(*address))*i4;

in four dimensions. Note that p1 unused (it would be added just once at the end of the tensor; it could be used if we add padding before each element/line/row/column in which case it would represent a constant offset of the first element to the base pointer).

Padding/dimension sizes should be known by higher level languages. If we only have the strides were are back to the delinerization problem.

include/polly/CodeGen/IslExprBuilder.h

280–281 ↗

(On Diff #157873)

Please use doxygen comments for member documentation (triple slashes ////)

[cs15btech11044]

I am following this suggestion. However, I would like to clarify something.
Suppose we are considering a 3-dimensional array named arr (Consider C language for now).
Does the offset/padding solution suggested in the previous comment model the situation where each dimension of the array has its range from 0 to some dimension size value and while accessing the array, we use some arithmetic along with the respective dimension index ( arr[i+1][2*j-1][3*k] for instance)?

Also could you please elaborate on how would the byte-based indexing be more beneficial than the index-based approach?

[Meinersbur]

In D49024#1184317, @cs15btech11044 wrote:

Suppose we are considering a 3-dimensional array named arr (Consider C language for now).
Does the offset/padding solution suggested in the previous comment model the situation where each dimension of the array has its range from 0 to some dimension size value and while accessing the array, we use some arithmetic along with the respective dimension index ( arr[i+1][2*j-1][3*k] for instance)?

In that case i1/i2/i3 would be those expressions (i1=i+1,i2=2*j-1,'i3=3*k'). What matters is that behavior is only defined if each subscript evaluates to something within the size (0<=i1<n1) for its dimension.

Also could you please elaborate on how would the byte-based indexing be more beneficial than the index-based approach?

It would allow padding that is not a multiple of the element size. Take for instance the 24bit BMP image format. Each pixel takes 3 bytes, but each line must start at 4-byte boundaries. E.g. use a 3x5 image (RGB=color value, '.'=padding):

RGBRGBRGBRGBRGB.
RGBRGBRGBRGBRGB.
RGBRGBRGBRGBRGB

Each line has 5*3=15 bytes. To start the next line at a 4-byte boundary, a single byte of padding is added (so each line effectively takes 16 bytes; called getTypeAllocSize in LLVM).

[philip.pfaffe]

On top of my generic concern regarding the unclean implementation of the ShapeInfo itself, I left you a bunch of inline comments, mostly concerning style.

include/polly/CodeGen/IslExprBuilder.h

97 ↗

(On Diff #157873)

Why is this a MapVector instead of a DenseMap?

include/polly/ScopInfo.h

291

Make this an inline friend?

667

This and the comment should be removed.

include/polly/Support/ScopHelper.h

486

StringRef?

lib/Analysis/ScopBuilder.cpp

686

What's the point of this check?

700

Pointless IILE;

749

What's the point of these asserts?

1606

Why {nullptr}?

lib/Analysis/ScopDetection.cpp

546

Why count()?

574

Superfluous braces.

lib/Analysis/ScopInfo.cpp

1069–1070

Is the nullptr intentional?

4006

Should be static.

4024

There is no need to make this an IILE.

4048

Unrelated.

4080

This should really be an error.

lib/CodeGen/IslExprBuilder.cpp

292 ↗

(On Diff #157873)

This entire thing should be broken up into at least three functions.

lib/CodeGen/IslNodeBuilder.cpp

1216 ↗

(On Diff #157873)

Prefer using the c++ API.

lib/CodeGen/PPCGCodeGeneration.cpp

145

I really don't like IILE patterns. It doesn't even save you structure here.

807

Unrelated.

1105

Unrelated.

1112

Unrelated.

1209

Unrelated.

1211

Unrelated.

1465

Should be static.

1777

This seems unsound.

1782

Why 4? This needs documentation.

2022

What does this code even do?

3560

This seems like an unsound or at least unrelated change.

lib/Support/ScopHelper.cpp

708

You can just say None.

723

See above.

726

Why would the operand be null?

731

See above.

733

Why do you count() instead of equality compare?

738

Just return the make_pair.

[cs15btech11044]

lib/CodeGen/PPCGCodeGeneration.cpp

3560

Initially, the RTC's were not passing. So we had temporarily overridden the RTC to be always true, in order to check whether the generated kernel function had proper code.

[cs15btech11044]

For Chapel Arrays with custom dimension ranges (like arr[1..4][1..4] for instance), there were two issues

• For generating OffsetValue in the Kernel function for GPU, there wasn't any reference to the value counterpart given to expandCodeFor() in IslExprBuilder.cpp. It is fixed by passing the GlobalMap to the function.

• While testing the code with arrays as above, there was no need to compute getArrayOffset() for Chapel case, since Chapel internally takes care of its indices to make it 0 based. PPCGCodegen is unaware of this fact and still generates offsets which results in out of bound accesses which are originally valid. For now, I have commented it out, but I would love to have a more concrete solution here. Would having an extra flag for Polly which toggles this change would suffice?

[cs15btech11044]

Addressed @philip.pfaffe 's concern regarding disabling getArrayOffset().

include/polly/ScopBuilder.h

class ScopBuilder {
 
   /// Build a single-dimensional parametric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param Stmt       The parent statement of the instruction
   void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
 
+  bool buildAccessPollyAbstractIndex(MemAccInst Inst, ScopStmt *Stmt);
+
   /// Build an instance of MemoryAccess from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param Stmt       The parent statement of the instruction
   void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Analyze and extract the cross-BB scalar dependences (or, dataflow
   /// dependencies) of an instruction.
class ScopBuilder {
   ///
   /// @return The created MemoryAccess, or nullptr if the access is not within
   ///         the SCoP.
   MemoryAccess *addMemoryAccess(ScopStmt *Stmt, Instruction *Inst,
                                 MemoryAccess::AccessType AccType,
                                 Value *BaseAddress, Type *ElemType, bool Affine,
                                 Value *AccessValue,
                                 ArrayRef<const SCEV *> Subscripts,
-                                ArrayRef<const SCEV *> Sizes, MemoryKind Kind);
+                                ShapeInfo Shape, MemoryKind Kind);
 
   /// Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
   /// @param Stmt        The statement to add the MemoryAccess to.
   /// @param MemAccInst  The LoadInst or StoreInst.
   /// @param AccType     The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemType    The type of the accessed array elements.
   /// @param IsAffine    Whether all subscripts are affine expressions.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
   /// @param AccessValue Value read or written.
   ///
   /// @see MemoryKind
   void addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
                       MemoryAccess::AccessType AccType, Value *BaseAddress,
                       Type *ElemType, bool IsAffine,
-                      ArrayRef<const SCEV *> Subscripts,
-                      ArrayRef<const SCEV *> Sizes, Value *AccessValue);
+                      ArrayRef<const SCEV *> Subscripts, ShapeInfo Shape,
+                      Value *AccessValue);
 
   /// Create a MemoryAccess for writing an llvm::Instruction.
   ///
   /// The access will be created at the position of @p Inst.
   ///
   /// @param Inst The instruction to be written.
   ///
   /// @see ensureValueRead()

include/polly/ScopInfo.h

enum AssumptionKind {
   PROFITABLE,
   ERRORBLOCK,
   COMPLEXITY,
   INFINITELOOP,
   INVARIANTLOAD,
   DELINEARIZATION,
 };
 
+// Abstract over a notion of the shape of an array:
+// Once can compute indeces using both sizes and strides.
+class ShapeInfo {
+private:
+  using SCEVArrayTy = SmallVector<const SCEV *, 4>;
+  using SCEVArrayRefTy = ArrayRef<const SCEV *>;
+
+  using OptionalSCEVArrayTy = Optional<SCEVArrayTy>;
+  using OptionalSCEVArrayRefTy = Optional<SCEVArrayRefTy>;
+
+  llvm::Optional<SmallVector<const SCEV *, 4>> Sizes;
+  llvm::Optional<SmallVector<const SCEV *, 4>> Strides;
+  llvm::Optional<const SCEV *> Offset;
+
+  ShapeInfo(Optional<ArrayRef<const SCEV *>> SizesRef,
+            Optional<ArrayRef<const SCEV *>> StridesRef,
+            llvm::Optional<const SCEV *> Offset)
+      : Offset(Offset) {
+    // Can check for XOR
+    assert(bool(SizesRef) || bool(StridesRef));
+    assert(!(bool(SizesRef) && bool(StridesRef)));
+
+    if (StridesRef || Offset) {
+      assert(Offset);
+      assert(StridesRef);
+    }
+
+    if (SizesRef)
+      Sizes =
+          OptionalSCEVArrayTy(SCEVArrayTy(SizesRef->begin(), SizesRef->end()));
+
+    if (StridesRef)
+      Strides = OptionalSCEVArrayTy(
+          SCEVArrayTy(StridesRef->begin(), StridesRef->end()));
+  }
+
+  ShapeInfo(NoneType) : Sizes(None), Strides(None), Offset(None) {}
+
+public:
+  static ShapeInfo fromSizes(ArrayRef<const SCEV *> Sizes) {
+    return ShapeInfo(OptionalSCEVArrayRefTy(Sizes), None, None);
+  }
+
+  // We have this anti-pattern in polly which does this:
+  // Shape(ShapeInfo::fromSizes({nullptr})
+  // Consider providing a separate constructor for this, which we then
+  // kill in some cleanup.
+
+  ShapeInfo(const ShapeInfo &other) {
+    Sizes = other.Sizes;
+    Strides = other.Strides;
+    Offset = other.Offset;
+  }
+
+  ShapeInfo &operator=(const ShapeInfo &other) {
+    Sizes = other.Sizes;
+    Strides = other.Strides;
+    Offset = other.Offset;
+    return *this;
+  }
+
+  static ShapeInfo fromStrides(ArrayRef<const SCEV *> Strides,
+                               const SCEV *Offset) {
+    assert(Offset && "offset is null");
+    return ShapeInfo(None, OptionalSCEVArrayRefTy(Strides),
+                     Optional<const SCEV *>(Offset));
+  }
+
+  static ShapeInfo none() { return ShapeInfo(None); }
+
+  unsigned getNumberOfDimensions() const {
+    // assert(isInitialized());
+    if (Sizes)
+      return Sizes->size();
+
+    if (Strides)
+      return Strides->size();
+
+    return 0;
+  }
+
+  /// Set the sizes of the Shape. It checks the invariant
+  /// That this shape does not have strides.
+  void setSizes(SmallVector<const SCEV *, 4> NewSizes) {
+    assert(!bool(Strides));
+
+    if (!bool(Sizes)) {
+      Sizes = Optional<SmallVector<const SCEV *, 4>>(
+          SmallVector<const SCEV *, 4>());
+    }
+
+    Sizes = NewSizes;
+  }
+
+  /// Set the strides of the Shape. It checks the invariant
+  /// That this shape does not have sizes.
+  void setStrides(ArrayRef<const SCEV *> NewStrides, const SCEV *NewOffset) {
+    Offset = NewOffset;
+    assert(!bool(Sizes));
+
+    // Be explicit because GCC(5.3.0) is unable to deduce this.
+    if (!Strides)
+      Strides = Optional<SmallVector<const SCEV *, 4>>(
+          SmallVector<const SCEV *, 4>());
+
+    Strides->clear();
+    Strides->insert(Strides->begin(), NewStrides.begin(), NewStrides.end());
+
+    assert(Offset && "offset is null");
+  }
+
+  const SmallVector<const SCEV *, 4> &sizes() const {
+    assert(!bool(Strides));
+    return Sizes.getValue();
+  }
+
+  const SCEV *offset() const { return Offset.getValue(); }
+
+  SmallVector<const SCEV *, 4> &sizes_mut() {
+    assert(!bool(Strides));
+    return Sizes.getValue();
+  }
+
+  bool isInitialized() const { return bool(Sizes) || bool(Strides); }
+
+  const SmallVector<const SCEV *, 4> &strides() const {
+    assert(!bool(Sizes));
+    return Strides.getValue();
+  }
+
+  const SmallVector<const SCEV *, 4> &getSizesOrStrides() {
+    if (Sizes)
+      return Sizes.getValue();
+
+    if (Strides)
+      return Strides.getValue();
+  }
+  bool hasSizes() const { return bool(Sizes); }
+  bool hasStrides() const { return bool(Strides); }
+
+  template <typename Ret>
+  Ret mapSizes(std::function<Ret(SmallVector<const SCEV *, 4> &)> func,
+               Ret otherwise) {
+    if (Sizes)
+      return func(*Sizes);
+
+    return otherwise;
+  }
+
+  void mapSizes(std::function<void(SmallVector<const SCEV *, 4> &)> func) {
+    if (Sizes)
+      func(*Sizes);
+  }
+
+  raw_ostream &print(raw_ostream &OS) const {
+    if (Sizes) {
+      OS << "Sizes: ";
+      for (auto Size : *Sizes) {
+        if (Size)
+          OS << *Size << ", ";
+        else
+          OS << "null"
+             << ", ";
+      }
+      return OS;
+    } else if (Strides) {
+      OS << "Strides: ";
+      for (auto Stride : *Strides) {
+        if (Stride)
+          OS << *Stride << ", ";
+        else
+          OS << "null"
+             << ", ";
+      }
+      return OS;
+    }
+    OS << "Uninitialized.\n";
+    return OS;
+  }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const ShapeInfo &Shape);
+
 /// Enum to distinguish between assumptions and restrictions.
 enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
 
 /// The different memory kinds used in Polly.
 ///
 /// We distinguish between arrays and various scalar memory objects. We use
 /// the term ``array'' to describe memory objects that consist of a set of
 /// individual data elements arranged in a multi-dimensional grid. A scalar

 ///
 class ScopArrayInfo {
 public:
   /// Construct a ScopArrayInfo object.
   ///
   /// @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 ShapeInfo
   /// @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, MemoryKind Kind,
-                const DataLayout &DL, Scop *S, const char *BaseName = nullptr);
+                ShapeInfo Shape, MemoryKind Kind, const DataLayout &DL, Scop *S,
+                const char *BaseName = nullptr);
 
   /// Destructor to free the isl id of the base pointer.
   ~ScopArrayInfo();
 
   ///  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
public:
   ///
   ///  @param Sizes       A vector of array sizes where the rightmost array
   ///                     sizes need to match the innermost array sizes already
   ///                     defined in SAI.
   ///  @param CheckConsistency Update sizes, even if new sizes are inconsistent
   ///                          with old sizes
   bool updateSizes(ArrayRef<const SCEV *> Sizes, bool CheckConsistency = true);
 
+  /// Update the strides of a ScopArrayInfo object, when we had
+  /// initially believed it to be a size based representation, we later
+  /// get a more refined view of the array in terms of strides.
+  /// TODO: Think if this is really necessary. We needed this in COSMO for
+  /// reasons, (IIRC, they would have <baseptr> be a i8*, which they would index
+  /// "correctly"
+  ///  to get to the offset and stride info.)
+  /// Roughly, they had code like this:
+  ///   struct ARRTY { int64 offset; int64 stride_1; int64 stride_2; void
+  ///   *memory; } void * arr; offset = ((int64 *)arr)[0]; stride_1 = ((int64
+  ///   *)arr)[1]; stride_2 = ((int64 *)arr)[1]; memory =
+  ///   fortran_index(((char*)arr+<correct offset>)), offset, stride_1,
+  ///   stride_2, ix1, ix2); In this type of code, we would first see the naked
+  ///   access of "arr" which we would represent in a size based repr, and we
+  ///   would change our view later into the strided version. We should probably
+  ///   disallow this for future clients.
+  void overwriteSizeWithStrides(ArrayRef<const SCEV *> Strides,
+                                const SCEV *Offset);
+
+  /// Update the strides of a ScopArrayInfo object.
+  bool updateStrides(ArrayRef<const SCEV *> Strides, const SCEV *Offset);
+
   /// Make the ScopArrayInfo model a Fortran array.
   /// It receives the Fortran array descriptor and stores this.
   /// It also adds a piecewise expression for the outermost dimension
   /// since this information is available for Fortran arrays at runtime.
   void applyAndSetFAD(Value *FAD);
 
   /// Get the FortranArrayDescriptor corresponding to this array if it exists,
   /// nullptr otherwise.
   Value *getFortranArrayDescriptor() const { return this->FAD; }
 
   /// 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; }
 
+  // get the shape of the ScopArrayInfo
+  ShapeInfo getShape() const { return Shape; }
+
   /// 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;
   }
 
   /// Return the number of dimensions.
   unsigned getNumberOfDimensions() const {
     if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI ||
         Kind == MemoryKind::Value)
       return 0;
-    return DimensionSizes.size();
+    return DimensionSizesPw.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, in case the array is not newly created.
   const SCEV *getDimensionSize(unsigned Dim) const {
#endif
   /// Two arrays are compatible if their dimensionality, the sizes of their
   /// dimensions, and their element sizes match.
   ///
   /// @param Array The array to compare against.
   ///
   /// @returns True, if the arrays are compatible, False otherwise.
   bool isCompatibleWith(const ScopArrayInfo *Array) const;
 
+  bool hasStrides() const { return Shape.hasStrides(); }
+
 private:
   void addDerivedSAI(ScopArrayInfo *DerivedSAI) {
     DerivedSAIs.insert(DerivedSAI);
   }
 
   /// For indirect accesses this is the SAI of the BP origin.
   const ScopArrayInfo *BasePtrOriginSAI;
 
private:
 
   /// The isl id for the base pointer.
   isl::id Id;
 
   /// True if the newly allocated array is on heap.
   bool IsOnHeap = false;
 
   /// 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.
   ///
   /// We distinguish between SCALAR, PHI and ARRAY objects.
   MemoryKind Kind;
 
   /// The data layout of the module.
   const DataLayout &DL;
 
+  /// The sizes of each dimension as SCEV*.
+  ShapeInfo Shape;
+
   /// The scop this SAI object belongs to.
   Scop &S;
 
   /// If this array models a Fortran array, then this points
   /// to the Fortran array descriptor.
   Value *FAD = nullptr;
 };
 
private:
   /// The #BaseAddr of a memory access of kind MemoryKind::Value is the
   /// instruction defining the value.
   AssertingVH<Value> BaseAddr;
 
   /// Type a single array element wrt. this access.
   Type *ElementType;
 
   /// Size of each dimension of the accessed array.
+  ShapeInfo Shape;
+
+  /// Size of each dimension of the accessed array.
   SmallVector<const SCEV *, 4> Sizes;
   // @}
 
   // Properties describing the accessed element.
   // @{
 
   /// The access instruction of this memory access.
   ///
public:
   /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param BaseAddr   The accessed array's address.
   /// @param ElemType   The type of the accessed array elements.
   /// @param AccType    Whether read or write access.
   /// @param IsAffine   Whether the subscripts are affine expressions.
   /// @param Kind       The kind of memory accessed.
   /// @param Subscripts Subscript expressions
-  /// @param Sizes      Dimension lengths of the accessed array.
+  /// @param Shape      Shape of the accessed array.
+
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,
                Value *BaseAddress, Type *ElemType, bool Affine,
-               ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
+               ArrayRef<const SCEV *> Subscripts, ShapeInfo Shape,
                Value *AccessValue, MemoryKind Kind);
 
   /// Create a new MemoryAccess that corresponds to @p AccRel.
   ///
   /// Along with @p Stmt and @p AccType it uses information about dimension
   /// lengths of the accessed array, the type of the accessed array elements,
   /// the name of the accessed array that is derived from the object accessible
   /// via @p AccRel.
public:
   /// Return true if and only if @p R is a non-affine subregion.
   bool isNonAffineSubRegion(const Region *R) {
     return DC.NonAffineSubRegionSet.count(R);
   }
 
   const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; }
 
   /// Return the (possibly new) ScopArrayInfo object for @p Access.
-  ///
+  /// @param BasePtr     The base  pointer of the SAI to add
   /// @param ElementType The type of the elements stored in this array.
+  /// @param Shape       The shape of the SAI.
   /// @param Kind        The kind of the array info object.
   /// @param BaseName    The optional name of this memory reference.
   ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
-                                          ArrayRef<const SCEV *> Sizes,
-                                          MemoryKind Kind,
+                                          ShapeInfo Shape, MemoryKind Kind,
                                           const char *BaseName = nullptr);
 
   /// 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.
   ScopArrayInfo *createScopArrayInfo(Type *ElementType,

include/polly/Support/ScopHelper.h

 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueHandle.h"
 #include <tuple>
 #include <vector>
 
 namespace llvm {
 class LoopInfo;
 class Loop;
 class ScalarEvolution;

 ///       printf("The value of sum at i=%d is %d\n", sum, i);
 ///     }
 bool isDebugCall(llvm::Instruction *Inst);
 
 /// Does the statement contain a call to a debug function?
 ///
 /// Such a statement must not be removed, even if has no side-effects.
 bool hasDebugCall(ScopStmt *Stmt);
+
+/// The name of the array index "intrinsic" interpreted by polly
+static const std::string POLLY_ABSTRACT_INDEX_BASENAME = "polly_array_index";
+
+/// Check if a given MemAccInst models a polly_array_index.
+llvm::Optional<std::pair<llvm::CallInst *, llvm::GEPOperator *>>
+getAbstractIndexingCall(MemAccInst Inst, llvm::ScalarEvolution &SE);
 } // namespace polly
 #endif

lib/Analysis/ScopBuilder.cpp

bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
 
   SizesSCEV.push_back(nullptr);
 
   for (auto V : Sizes)
     SizesSCEV.push_back(SE.getSCEV(
         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
   addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
-                 true, Subscripts, SizesSCEV, Val);
+                 true, Subscripts, ShapeInfo::fromSizes(SizesSCEV), Val);
   return true;
 }
 
 bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   if (!PollyDelinearize)
     return false;
 
   Value *Address = Inst.getPointerOperand();
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   // TODO: Handle delinearization with differing element sizes.
   auto DelinearizedSize =
       cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
   Sizes.pop_back();
   if (ElementSize != DelinearizedSize)
     scop->invalidate(DELINEARIZATION, Inst->getDebugLoc(), Inst->getParent());
 
   addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
-                 true, AccItr->second.DelinearizedSubscripts, Sizes, Val);
+                 true, AccItr->second.DelinearizedSubscripts,
+                 ShapeInfo::fromSizes(Sizes), Val);
   return true;
 }
 
 bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 
   if (MemIntr == nullptr)
     return false;
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   //       the context with
   //          isl_set_complement(isl_set_params(getDomain()))
   //       as we know it would be undefined to execute this instruction anyway.
   if (DestAccFunc->isZero())
     return true;
 
   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
+  // TODO: code smell, why doe we initialize an empty shape? I don't recall the
+  // details
+  //       anymore.
   DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
   addArrayAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(DestPtrVal->getContext()),
-                 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
-                 Inst.getValueOperand());
+                 LengthIsAffine, {DestAccFunc, LengthVal},
+                 ShapeInfo::fromSizes({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(Stmt, Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(SrcPtrVal->getContext()),
-                 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
-                 Inst.getValueOperand());
+                 LengthIsAffine, {SrcAccFunc, LengthVal},
+                 ShapeInfo::fromSizes({nullptr}), Inst.getValueOperand());
 
   return true;
 }
 
 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
+  if (buildAccessPollyAbstractIndex(Inst, Stmt))
+    return true;
+
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)
     return false;
 
   if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI) || isDebugCall(CI))
     return true;
 
   bool ReadOnly = false;
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
   auto *CalledFunction = CI->getCalledFunction();
+
   switch (AA.getModRefBehavior(CalledFunction)) {
   case FMRB_UnknownModRefBehavior:
     llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
   case FMRB_DoesNotAccessMemory:
     return true;
   case FMRB_DoesNotReadMemory:
   case FMRB_OnlyAccessesInaccessibleMem:
   case FMRB_OnlyAccessesInaccessibleOrArgMem:
case FMRB_OnlyAccessesArgumentPointees: {
     for (const auto &Arg : CI->arg_operands()) {
       if (!Arg->getType()->isPointerTy())
         continue;
 
       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
       if (ArgSCEV->isZero())
         continue;
 
+      // TODO: again, why do we create a shape with a nullptr shape?
       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
       addArrayAccess(Stmt, Inst, AccType, ArgBasePtr->getValue(),
-                     ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
+                     ArgBasePtr->getType(), false, {AF},
+                     ShapeInfo::fromSizes({nullptr}), CI);
     }
     return true;
   }
   }
 
   return true;
 }
 
void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
   addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
-                 IsAffine, {AccessFunction}, {nullptr}, Val);
+                 IsAffine, {AccessFunction}, ShapeInfo::fromSizes({nullptr}),
+                 Val);
 }
 
 void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
   if (buildAccessMemIntrinsic(Inst, Stmt))
     return;
 
   if (buildAccessCallInst(Inst, Stmt))
     return;
 
   if (buildAccessMultiDimFixed(Inst, Stmt))
     return;
 
   if (buildAccessMultiDimParam(Inst, Stmt))
     return;
 
   buildAccessSingleDim(Inst, Stmt);
 }
 
+bool ScopBuilder::buildAccessPollyAbstractIndex(MemAccInst Inst,
+                                                ScopStmt *Stmt) {
+  auto optionalCallGEP = getAbstractIndexingCall(Inst, SE);
+  if (!optionalCallGEP)
+    return false;
+
+  CallInst *Call;
+  GEPOperator *GEP;
+  std::tie(Call, GEP) = *optionalCallGEP;
+
+  if ((Call->getNumArgOperands() ) % 2 != 1) {
+    return false;
+  }
+
+  const int NArrayDims = (Call->getNumArgOperands()) / 2;
+
+  Value *BasePtr = GEP->getPointerOperand();
+
+  std::vector<const SCEV *> Subscripts;
+  std::vector<const SCEV *> Strides;
+  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
+
+  InvariantLoadsSetTy AccessILS;
+
+  const SCEV *OffsetSCEV = [&] {
+    Value *Offset = Call->getArgOperand(0);
+    assert(Offset);
+    const SCEV *OffsetSCEV = SE.getSCEV(Offset);
+
+    if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, OffsetSCEV, SE,
+                      &AccessILS)) {
+      return (const SCEV *)nullptr;
+    }
+
+    // Offsets are always loaded from the array, they will get invariant
+    // load hoisted correctly later.
+    for (LoadInst *L : AccessILS) {
+      scop->addRequiredInvariantLoad(L);
+    }
+    AccessILS.clear();
+
+    return OffsetSCEV;
+  }();
+
+  if (!OffsetSCEV)
+    return false;
+
+  for (int i = 0; i < NArrayDims; i++) {
+    Value *Ix = Call->getArgOperand(1 + NArrayDims + i);
+    const SCEV *IxSCEV = SE.getSCEV(Ix);
+    ensureValueRead(Ix, Stmt);
+    Subscripts.push_back(IxSCEV);
+
+    Value *Stride = Call->getArgOperand(1 + i);
+    const SCEV *StrideSCEV = SE.getSCEV(Stride);
+
+    if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, StrideSCEV, SE,
+                      &AccessILS)) {
+      return false;
+    }
+
+    for (LoadInst *L : AccessILS) {
+      scop->addRequiredInvariantLoad(L);
+    }
+    AccessILS.clear();
+
+    Strides.push_back(StrideSCEV);
+  }
+
+  Value *Val = Inst.getValueOperand();
+  Type *ElementType = Val->getType();
+  assert(BasePtr);
+  assert(ElementType);
+
+  enum MemoryAccess::AccessType AccType =
+      isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
+      //scop->invalidate(DELINEARIZATION, Inst->getDebugLoc(), Inst->getParent());
+
+  // NOTE: this should be fromStrides.
+  // NOTE: To be able to change this, we need to teach ScopArrayInfo to recieve
+  // a Shape object. So, do that first.
+  addArrayAccess(Stmt, Inst, AccType, BasePtr, ElementType, /*IsAffine=*/true,
+                 Subscripts, ShapeInfo::fromStrides(Strides, OffsetSCEV), Val);
+
+  return true;
+}
+
 void ScopBuilder::buildAccessFunctions() {
   for (auto &Stmt : *scop) {
     if (Stmt.isBlockStmt()) {
       buildAccessFunctions(&Stmt, *Stmt.getBasicBlock());
       continue;
     }
 
     Region *R = Stmt.getRegion();
for (Instruction &Inst : BB) {
       BuildAccessesForInst(&Inst);
     }
   }
 }
 
 MemoryAccess *ScopBuilder::addMemoryAccess(
     ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType,
     Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
-    ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
-    MemoryKind Kind) {
+    ArrayRef<const SCEV *> Subscripts, ShapeInfo Shape, MemoryKind Kind) {
   bool isKnownMustAccess = false;
 
   // Accesses in single-basic block statements are always executed.
   if (Stmt->isBlockStmt())
     isKnownMustAccess = true;
 
   if (Stmt->isRegionStmt()) {
     // Accesses that dominate the exit block of a non-affine region are always
MemoryAccess *ScopBuilder::addMemoryAccess(
   // overwrite the old value.
   if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)
     isKnownMustAccess = true;
 
   if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
   auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
-                                  Affine, Subscripts, Sizes, AccessValue, Kind);
+                                  Affine, Subscripts, Shape, AccessValue, Kind);
 
   scop->addAccessFunction(Access);
   Stmt->addAccess(Access);
   return Access;
 }
 
 void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
                                  MemoryAccess::AccessType AccType,
                                  Value *BaseAddress, Type *ElementType,
                                  bool IsAffine,
                                  ArrayRef<const SCEV *> Subscripts,
-                                 ArrayRef<const SCEV *> Sizes,
-                                 Value *AccessValue) {
+                                 ShapeInfo Shape, Value *AccessValue) {
   ArrayBasePointers.insert(BaseAddress);
   auto *MemAccess = addMemoryAccess(Stmt, MemAccInst, AccType, BaseAddress,
                                     ElementType, IsAffine, AccessValue,
-                                    Subscripts, Sizes, MemoryKind::Array);
+                                    Subscripts, Shape, MemoryKind::Array);
 
   if (!DetectFortranArrays)
     return;
 
   if (Value *FAD = findFADAllocationInvisible(MemAccInst))
     MemAccess->setFortranArrayDescriptor(FAD);
   else if (Value *FAD = findFADAllocationVisible(MemAccInst))
     MemAccess->setFortranArrayDescriptor(FAD);
if (!Stmt)
     return;
 
   // Do not process further if the instruction is already written.
   if (Stmt->lookupValueWriteOf(Inst))
     return;
 
   addMemoryAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, Inst, Inst->getType(),
                   true, Inst, ArrayRef<const SCEV *>(),
-                  ArrayRef<const SCEV *>(), MemoryKind::Value);
+                  ShapeInfo::fromSizes(ArrayRef<const SCEV *>()),
+                  MemoryKind::Value);
 }
 
 void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
   // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality
   // to be able to replace this one. Currently, there is a split responsibility.
   // In a first step, the MemoryAccess is created, but without the
   // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the
   // AccessRelation is created. At least for scalar accesses, there is no new
void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
   case VirtualUse::Inter:
 
     // Do not create another MemoryAccess for reloading the value if one already
     // exists.
     if (UserStmt->lookupValueReadOf(V))
       break;
 
     addMemoryAccess(UserStmt, nullptr, MemoryAccess::READ, V, V->getType(),
-                    true, V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+                    true, V, ArrayRef<const SCEV *>(),
+                    ShapeInfo::fromSizes(ArrayRef<const SCEV *>()),
                     MemoryKind::Value);
 
     // Inter-statement uses need to write the value in their defining statement.
     if (VUse.isInter())
       ensureValueWrite(cast<Instruction>(V));
     break;
   }
 }
 
 void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt,
                                  BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
   // As the incoming block might turn out to be an error statement ensure we
   // will create an exit PHI SAI object. It is needed during code generation
   // and would be created later anyway.
   if (IsExitBlock)
-    scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
-                                   MemoryKind::ExitPHI);
+    scop->getOrCreateScopArrayInfo(
+        PHI, PHI->getType(), ShapeInfo::fromSizes({}), MemoryKind::ExitPHI);
 
   // This is possible if PHI is in the SCoP's entry block. The incoming blocks
   // from outside the SCoP's region have no statement representation.
   if (!IncomingStmt)
     return;
 
   // Take care for the incoming value being available in the incoming block.
   // This must be done before the check for multiple PHI writes because multiple
   // exiting edges from subregion each can be the effective written value of the
   // subregion. As such, all of them must be made available in the subregion
   // statement.
   ensureValueRead(IncomingValue, IncomingStmt);
 
   // Do not add more than one MemoryAccess per PHINode and ScopStmt.
   if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
     assert(Acc->getAccessInstruction() == PHI);
     Acc->addIncoming(IncomingBlock, IncomingValue);
     return;
   }
 
-  MemoryAccess *Acc = addMemoryAccess(
-      IncomingStmt, PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true,
-      PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+  MemoryAccess *Acc =
+      addMemoryAccess(IncomingStmt, PHI, MemoryAccess::MUST_WRITE, PHI,
+                      PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
+                      ShapeInfo::fromSizes(ArrayRef<const SCEV *>()),
                       IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);
   assert(Acc);
   Acc->addIncoming(IncomingBlock, IncomingValue);
 }
 
 void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) {
   addMemoryAccess(PHIStmt, PHI, MemoryAccess::READ, PHI, PHI->getType(), true,
-                  PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+                  PHI, ArrayRef<const SCEV *>(),
+                  ShapeInfo::fromSizes(ArrayRef<const SCEV *>()),
                   MemoryKind::PHI);
 }
 
 void ScopBuilder::buildDomain(ScopStmt &Stmt) {
   isl::id Id = isl::id::alloc(scop->getIslCtx(), Stmt.getBaseName(), &Stmt);
 
   Stmt.Domain = scop->getDomainConditions(&Stmt);
   Stmt.Domain = Stmt.Domain.set_tuple_id(Id);
for (MemoryAccess *Access : Stmt.MemAccs) {
     else if (Access->isExitPHIKind())
       Ty = MemoryKind::ExitPHI;
     else if (Access->isValueKind())
       Ty = MemoryKind::Value;
     else
       Ty = MemoryKind::Array;
 
     auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),
-                                               ElementType, Access->Sizes, Ty);
+                                               ElementType, Access->Shape, Ty);
     Access->buildAccessRelation(SAI);
     scop->addAccessData(Access);
   }
 }
 
 #ifndef NDEBUG
 static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
   auto PhysUse = VirtualUse::create(S, Op, &LI, false);
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
 
   // Create memory accesses for global reads since all arrays are now known.
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
   for (auto GlobalReadPair : GlobalReads) {
     ScopStmt *GlobalReadStmt = GlobalReadPair.first;
     Instruction *GlobalRead = GlobalReadPair.second;
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,
-                     BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
+                     BP, BP->getType(), false, {AF},
+                     ShapeInfo::fromSizes({nullptr}), GlobalRead);
   }
 
   scop->buildInvariantEquivalenceClasses();
 
   /// A map from basic blocks to their invalid domains.
   DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
 
   if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) {

lib/Analysis/ScopDetection.cpp

if (PtrVals.insert(BasePtrVal).second) {
         if (PtrVal != BasePtrVal && !AA.isNoAlias(PtrVal, BasePtrVal))
           return true;
     }
   }
 
   return false;
 }
 
+/// Return if S is a call to a function that we use to denote multidimensional
+// accesses
+bool isSCEVCallToPollyAbstractIndex(const SCEV *S) {
+  if (isa<SCEVUnknown>(S)) {
+    Value *V = cast<SCEVUnknown>(S)->getValue();
+    CallInst *Call = dyn_cast<CallInst>(V);
+    if (Call && Call->getCalledFunction() &&
+        Call->getCalledFunction()->getName().count(
+            POLLY_ABSTRACT_INDEX_BASENAME))
+      return true;
+  }
+  return false;
+}
+
+/// Return if scev represents a multidim access.
+bool isSCEVMultidimArrayAccess(const SCEV *S) {
+  if (isSCEVCallToPollyAbstractIndex(S))
+    return true;
+  const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S);
+  if (!Mul)
+    return false;
+
+  // TODO: I don't remember why I needed this.
+  // When does a Mul not have two operands? Something like {*, i, *, j, *, k}?
+  if (Mul->getNumOperands() != 2)
+    return false;
+
+  // TODO: I have no memory of why I needed this.
+  return isSCEVCallToPollyAbstractIndex(Mul->getOperand(0)) ||
+         isSCEVCallToPollyAbstractIndex(Mul->getOperand(1));
+}
+
 bool ScopDetection::isAffine(const SCEV *S, Loop *Scope,
                              DetectionContext &Context) const {
+
+  if (isSCEVMultidimArrayAccess(S)) {
+    return true;
+  }
+
   InvariantLoadsSetTy AccessILS;
   if (!isAffineExpr(&Context.CurRegion, Scope, S, SE, &AccessILS))
     return false;
 
   if (!onlyValidRequiredInvariantLoads(AccessILS, Context))
     return false;
 
   return true;
if (CI.doesNotAccessMemory())
     return true;
 
   if (auto *II = dyn_cast<IntrinsicInst>(&CI))
     if (isValidIntrinsicInst(*II, Context))
       return true;
 
   Function *CalledFunction = CI.getCalledFunction();
 
+  // Function being called is a polly indexing function.
+  if (CalledFunction->getName().count(POLLY_ABSTRACT_INDEX_BASENAME)) {
+    return true;
+  }
+
   // Indirect calls are not supported.
   if (CalledFunction == nullptr)
     return false;
 
   if (isDebugCall(&CI)) {
     LLVM_DEBUG(dbgs() << "Allow call to debug function: "
                       << CalledFunction->getName() << '\n');
     return true;
if (!AS.isMustAlias()) {
     return invalid<ReportAlias>(Context, /*Assert=*/true, Inst, AS);
   }
 
   return true;
 }
 
 bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
                                         DetectionContext &Context) const {
+
+  /// If the memory access is modelling a call of
+  /// polly_abstract_array_index(...)
+  if (getAbstractIndexingCall(Inst, SE)) {
+    return true;
+  }
+
   Value *Ptr = Inst.getPointerOperand();
   Loop *L = LI.getLoopFor(Inst->getParent());
   const SCEV *AccessFunction = SE.getSCEVAtScope(Ptr, L);
   const SCEVUnknown *BasePointer;
 
   BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 
   return isValidAccess(Inst, AccessFunction, BasePointer, Context);

lib/Analysis/ScopInfo.cpp

static cl::opt<bool, true> XUseInstructionNames(
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyPrintInstructions(
     "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
     cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
 
 //===----------------------------------------------------------------------===//
 
+raw_ostream &polly::operator<<(raw_ostream &OS, const ShapeInfo &Shape) {
+  return Shape.print(OS);
+}
+
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
   if (!Prev)
     return Succ;
   if (!Succ)
     return Prev;
static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
   if (!OriginBaseSCEVUnknown)
     return nullptr;
 
   return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
                              MemoryKind::Array);
 }
 
 ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx Ctx,
-                             ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
+                             ShapeInfo Shape, MemoryKind Kind,
                              const DataLayout &DL, Scop *S,
                              const char *BaseName)
-    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
+    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL),
+      Shape(ShapeInfo::none()), S(*S) {
   std::string BasePtrName =
       BaseName ? BaseName
                : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),
                                       Kind == MemoryKind::PHI ? "__phi" : "",
                                       UseInstructionNames);
   Id = isl::id::alloc(Ctx, BasePtrName, this);
 
-  updateSizes(Sizes);
+  // TODO: why do we need updateSizes() ? Why don't we set this up in the
+  // ctor?
+  if (Shape.hasSizes())
+    updateSizes(Shape.sizes());
+  else
+    updateStrides(Shape.strides(), Shape.offset());
 
   if (!BasePtr || Kind != MemoryKind::Array) {
     BasePtrOriginSAI = nullptr;
     return;
   }
 
   BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
   if (BasePtrOriginSAI)
void ScopArrayInfo::applyAndSetFAD(Value *FAD) {
 
   Space = Space.set_dim_id(isl::dim::param, 0, IdPwAff);
   isl::pw_aff PwAff =
       isl::aff::var_on_domain(isl::local_space(Space), isl::dim::param, 0);
 
   DimensionSizesPw[0] = PwAff;
 }
 
+void ScopArrayInfo::overwriteSizeWithStrides(ArrayRef<const SCEV *> Strides,
+                                             const SCEV *Offset) {
+
+  // HACK: first set our shape to a stride based shape so that we don't
+  // assert within updateStrides. Move this into a bool parameter of
+  // updateStrides
+  Shape = ShapeInfo::fromStrides(Strides, Offset);
+  updateStrides(Strides, Offset);
+}
+bool ScopArrayInfo::updateStrides(ArrayRef<const SCEV *> Strides,
+                                  const SCEV *Offset) {
+  Shape.setStrides(Strides, Offset);
+  DimensionSizesPw.clear();
+  for (size_t i = 0; i < Shape.getNumberOfDimensions(); i++) {
+    isl::space Space(S.getIslCtx(), 1, 0);
+
+    std::string param_name = getIslCompatibleName(
+        "stride_" + std::to_string(i) + "__", getName(), "");
+    isl::id IdPwAff = isl::id::alloc(S.getIslCtx(), param_name, this);
+
+    Space = Space.set_dim_id(isl::dim::param, 0, IdPwAff);
+    isl::pw_aff PwAff =
+        isl::aff::var_on_domain(isl::local_space(Space), isl::dim::param, 0);
+
+    DimensionSizesPw.push_back(PwAff);
+  }
+  return true;
+}
+
 bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
                                 bool CheckConsistency) {
   int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
   int ExtraDimsNew = NewSizes.size() - SharedDims;
   int ExtraDimsOld = DimensionSizes.size() - SharedDims;
 
   if (CheckConsistency) {
     for (int i = 0; i < SharedDims; i++) {

 void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
   OS.indent(8) << *getElementType() << " " << getName();
   unsigned u = 0;
   // If this is a Fortran array, then we can print the outermost dimension
   // as a isl_pw_aff even though there is no SCEV information.
   bool IsOutermostSizeKnown = SizeAsPwAff && FAD;
 
   if (!IsOutermostSizeKnown && getNumberOfDimensions() > 0 &&
-      !getDimensionSize(0)) {
+      !getDimensionSizePw(0)) {
     OS << "[*]";
     u++;
   }
   for (; u < getNumberOfDimensions(); u++) {
     OS << "[";
 
     if (SizeAsPwAff) {
       isl::pw_aff Size = getDimensionSizePw(u);
void MemoryAccess::assumeNoOutOfBound() {
   if (!PollyPreciseInbounds)
     Outside = Outside.gist_params(Statement->getDomain().params());
   Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
                                            AS_ASSUMPTION);
 }
 
 void MemoryAccess::buildMemIntrinsicAccessRelation() {
   assert(isMemoryIntrinsic());
-  assert(Subscripts.size() == 2 && Sizes.size() == 1);
+  assert(Subscripts.size() == 2 && Shape.sizes().size() == 1);
 
   isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);
   isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);
 
   isl::map LengthMap;
   if (Subscripts[1] == nullptr) {
     LengthMap = isl::map::universe(SubscriptMap.get_space());
   } else {
void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
   isl::map Relation = AccessRelation;
   isl::set AccessRange = Relation.range();
   AccessRange = addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
                                     isl::dim::set);
   AccessRelation = Relation.intersect_range(AccessRange);
 }
 
 void MemoryAccess::foldAccessRelation() {
-  if (Sizes.size() < 2 || isa<SCEVConstant>(Sizes[1]))
+  if (Shape.getNumberOfDimensions() < 2 || isa<SCEVConstant>(Shape.getSizesOrStrides()[1]))
     return;
 
   int Size = Subscripts.size();
 
   isl::map NewAccessRelation = AccessRelation;
 
   for (int i = Size - 2; i >= 0; --i) {
     isl::space Space;
     isl::map MapOne, MapTwo;
-    isl::pw_aff DimSize = getPwAff(Sizes[i + 1]);
+    isl::pw_aff DimSize = getPwAff(Shape.getSizesOrStrides()[i + 1]);
 
     isl::space SpaceSize = DimSize.get_space();
     isl::id ParamId = SpaceSize.get_dim_id(isl::dim::param, 0);
 
     Space = AccessRelation.get_space();
     Space = Space.range().map_from_set();
     Space = Space.align_params(SpaceSize);
 
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
 
   AccessRelation = AccessRelation.gist_domain(Statement->getDomain());
 }
 
 MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
                            AccessType AccType, Value *BaseAddress,
                            Type *ElementType, bool Affine,
-                           ArrayRef<const SCEV *> Subscripts,
-                           ArrayRef<const SCEV *> Sizes, Value *AccessValue,
-                           MemoryKind Kind)
+                           ArrayRef<const SCEV *> Subscripts, ShapeInfo Shape,
+                           Value *AccessValue, MemoryKind Kind)
     : Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(nullptr),
-      BaseAddr(BaseAddress), ElementType(ElementType),
-      Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
-      AccessValue(AccessValue), IsAffine(Affine),
+      BaseAddr(BaseAddress), ElementType(ElementType), Shape(Shape),
+      AccessInstruction(AccessInst), AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr), FAD(nullptr) {
   static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
   const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
 
   std::string IdName = Stmt->getBaseName() + Access;
   Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
 }
 
 MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
     : Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),
-      InvalidDomain(nullptr), AccessRelation(nullptr),
-      NewAccessRelation(AccRel), FAD(nullptr) {
+      InvalidDomain(nullptr), Shape(ShapeInfo::fromSizes({nullptr})),
+      AccessRelation(nullptr), NewAccessRelation(AccRel), FAD(nullptr) {
   isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(isl::dim::out);
   auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);
   Sizes.push_back(nullptr);
   for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
     Sizes.push_back(SAI->getDimensionSize(i));
   ElementType = SAI->getElementType();
   BaseAddr = SAI->getBasePtr();
   static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {
   }
 }
 
 MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
   MemoryAccess *Access = lookupInputAccessOf(V);
   if (Access)
     return Access;
 
-  ScopArrayInfo *SAI =
-      Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
-  Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
-                            true, {}, {}, V, MemoryKind::Value);
+  // TODO: again, why do we have an _empty_ list here for size?
+  ScopArrayInfo *SAI = Parent.getOrCreateScopArrayInfo(
+      V, V->getType(), ShapeInfo::fromSizes({}), MemoryKind::Value);
+  Access =
+      new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(), true,
+                       {}, ShapeInfo::fromSizes({}), V, MemoryKind::Value);
   Parent.addAccessFunction(Access);
   Access->buildAccessRelation(SAI);
   addAccess(Access);
   Parent.addAccessData(Access);
   return Access;
 }
 
 raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {
for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
       if (isUsedForIndirectHoistedLoad(this, BasePtrSAI))
         continue;
 
       replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
     }
   }
 }
 
+Value *getPointerFromLoadOrStore(Value *V) {
+  if (LoadInst *LI = dyn_cast<LoadInst>(V))
+    return LI->getPointerOperand();
+
+  if (StoreInst *SI = dyn_cast<StoreInst>(V))
+    return SI->getPointerOperand();
+  return nullptr;
+}
+
 ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
-                                              ArrayRef<const SCEV *> Sizes,
-                                              MemoryKind Kind,
+                                              ShapeInfo Shape, 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.");
+
+  // We assume that arrays with the strided representation can unify.
+  // Yes this is nuts. Yes I stil want to do this.
+  auto unifyStridedArrayBasePtrs = [&]() -> Value * {
+    if (Shape.hasSizes())
+      return BasePtr;
+
+    const Value *CurBase = getPointerFromLoadOrStore(BasePtr);
+    if (!CurBase)
+      return BasePtr;
+
+    for (ScopArrayInfo *SAI : arrays()) {
+      Value *SAIBase = getPointerFromLoadOrStore(SAI->getBasePtr());
+      if (!SAIBase)
+        continue;
+
+      if (SAIBase == CurBase && SAI->hasStrides())
+        return SAI->getBasePtr();
+    }
+    return BasePtr;
+  };
+
+  BasePtr = unifyStridedArrayBasePtrs();
+
   auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]
                       : ScopArrayNameMap[BaseName];
+
+  // errs() << "Creating: " << (int)Kind << "\n";
+  // BasePtr->dump();
+
   if (!SAI) {
     auto &DL = getFunction().getParent()->getDataLayout();
-    SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
+    SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Shape, 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))
+    if (SAI->hasStrides() != Shape.hasStrides()) {
+      LLVM_DEBUG(dbgs() << "SAI and new shape do not agree:\n");
+      LLVM_DEBUG(dbgs() << "SAI: "; SAI->print(dbgs(), true); dbgs() << "\n");
+      LLVM_DEBUG(dbgs() << "Shape: " << Shape << "\n");
+
+      if (Shape.hasStrides()) {
+        LLVM_DEBUG(
+            dbgs() << "Shape has strides, SAI had size. Overwriting size "
+                      "with strides");
+        SAI->overwriteSizeWithStrides(Shape.strides(), Shape.offset());
+      } else {
+
+        errs() << __PRETTY_FUNCTION__ << "\n"
+               << "SAI has strides, Shape is size based. This should not "
+                  "happen. Ignoring new data for now.";
+        errs() << " SAI:\n";
+        SAI->print(errs(), false);
+        errs() << "Shape:\n";
+        errs() << Shape << "\n";
+        errs() << "---\n";
+        // report_fatal_error("SAI was given sizes when it had strides");
+        return SAI.get();
+      }
+    }
+
+    if (SAI->hasStrides()) {
+      SAI->updateStrides(Shape.strides(), Shape.offset());
+    } else {
+      if (!SAI->updateSizes(Shape.sizes()))
         invalidate(DELINEARIZATION, DebugLoc());
     }
+  }
+
   return SAI.get();
 }
 
 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,
+  auto *SAI = getOrCreateScopArrayInfo(nullptr, ElementType,
+                                       ShapeInfo::fromSizes(SCEVSizes),
                                        MemoryKind::Array, BaseName.c_str());
   return SAI;
 }
 
 const ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr,
                                                   MemoryKind Kind) {
   auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
   return SAI;
void Scop::printStatements(raw_ostream &OS, bool PrintInstructions) const {
 
   OS.indent(4) << "}\n";
 }
 
 void Scop::printArrayInfo(raw_ostream &OS) const {
   OS << "Arrays {\n";
 
   for (auto &Array : arrays())
-    Array->print(OS);
+    Array->print(OS,true);
 
   OS.indent(4) << "}\n";
 
   OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
 
   for (auto &Array : arrays())
     Array->print(OS, /* SizeAsPwAff */ true);
 

lib/CodeGen/PPCGCodeGeneration.cpp

 ///
 /// @see computeLiveRangeReordering
 /// @see GPUNodeBuilder::createPPCGScop
 /// @see GPUNodeBuilder::createPPCGProg
 struct MustKillsInfo {
   /// Collection of all kill statements that will be sequenced at the end of
   /// PPCGScop->schedule.
   ///
   /// The nodes in `KillsSchedule` will be merged using `isl_schedule_set`
   /// which merges schedules in *arbitrary* order.
   /// (we don't care about the order of the kills anyway).
   isl::schedule KillsSchedule;
   /// Map from kill statement instances to scalars that need to be
   /// killed.
   ///
   /// We currently derive kill information for:
   ///  1. phi nodes. PHI nodes are not alive outside the scop and can
if (SizeSCEV->isZero()) {
       errs() << getUniqueScopName(&S)
              << " has computed array size 0: " << *ArraySize
              << " | for array: " << *(ScopArray->getBasePtr())
              << ". This is illegal, exiting.\n";
       report_fatal_error("array size was computed to be 0");
     }
 
     Value *DevArray = createCallAllocateMemoryForDevice(ArraySize);
     DevArray->setName(DevArrayName);
     DeviceAllocations[ScopArray] = DevArray;
   }
 
   isl_ast_build_free(Build);
 }
 
 void GPUNodeBuilder::prepareManagedDeviceArrays() {
   assert(PollyManagedMemory &&

 /// @param Prefix The prefix to look for.
 static bool isPrefix(std::string String, std::string Prefix) {
   return String.find(Prefix) == 0;
 }
 
 Value *GPUNodeBuilder::getArraySize(gpu_array_info *Array) {
   isl::ast_build Build = isl::ast_build::from_context(S.getContext());
   Value *ArraySize = ConstantInt::get(Builder.getInt64Ty(), Array->size);
 
   if (!gpu_array_is_scalar(Array)) {
     isl::multi_pw_aff ArrayBound = isl::manage_copy(Array->bound);
 
     isl::pw_aff OffsetDimZero = ArrayBound.get_pw_aff(0);
     isl::ast_expr Res = Build.expr_from(OffsetDimZero);
 
     for (unsigned int i = 1; i < Array->n_index; i++) {
       isl::pw_aff Bound_I = ArrayBound.get_pw_aff(i);
       isl::ast_expr Expr = Build.expr_from(Bound_I);
       Res = Res.mul(Expr);
     }
 
     Value *NumElements = ExprBuilder.create(Res.release());
     if (NumElements->getType() != ArraySize->getType())
       NumElements = Builder.CreateSExt(NumElements, ArraySize->getType());
void GPUNodeBuilder::createDataTransfer(__isl_take isl_ast_node *TransferStmt,
   if (Offset) {
     Size = Builder.CreateSub(
         Size, Builder.CreateMul(
                   Offset, Builder.getInt64(ScopArray->getElemSizeInBytes())));
   }
 
   if (Direction == HOST_TO_DEVICE)
     createCallCopyFromHostToDevice(HostPtr, DevPtr, Size);
   else
     createCallCopyFromDeviceToHost(DevPtr, HostPtr, Size);
 
   isl_id_free(Id);
   isl_ast_expr_free(Arg);
   isl_ast_expr_free(Expr);
   isl_ast_node_free(TransferStmt);
 }
 
 void GPUNodeBuilder::createUser(__isl_take isl_ast_node *UserStmt) {
   isl_ast_expr *Expr = isl_ast_node_user_get_expr(UserStmt);
if (F) {
              "were present in a kernel.");
       SubtreeFunctions.insert(F);
     }
   }
   return SubtreeFunctions;
 }
 
 std::tuple<SetVector<Value *>, SetVector<Function *>, SetVector<const Loop *>,
            isl::space>
 GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   SetVector<Value *> SubtreeValues;
   SetVector<const SCEV *> SCEVs;
   SetVector<const Loop *> Loops;
   isl::space ParamSpace = isl::space(S.getIslCtx(), 0, 0).params();
   SubtreeReferences References = {
       LI,         SE, S, ValueMap, SubtreeValues, SCEVs, getBlockGenerator(),
       &ParamSpace};
for (auto Fn : SubtreeFunctions) {
     const std::string ClonedFnName = Fn->getName();
     Function *Clone = GPUModule->getFunction(ClonedFnName);
     if (!Clone)
       Clone =
           Function::Create(Fn->getFunctionType(), GlobalValue::ExternalLinkage,
                            ClonedFnName, GPUModule.get());
     assert(Clone && "Expected cloned function to be initialized.");
     assert(ValueMap.find(Fn) == ValueMap.end() &&
            "Fn already present in ValueMap");
     ValueMap[Fn] = Clone;
   }
 }
 void GPUNodeBuilder::createKernel(__isl_take isl_ast_node *KernelStmt) {
   isl_id *Id = isl_ast_node_get_annotation(KernelStmt);
   ppcg_kernel *Kernel = (ppcg_kernel *)isl_id_get_user(Id);
   isl_id_free(Id);
   isl_ast_node_free(KernelStmt);
 
   if (Kernel->n_grid > 1)
     DeepestParallel =
         std::max(DeepestParallel, isl_space_dim(Kernel->space, isl_dim_set));
   else
if (!ppcg_kernel_requires_array_argument(Kernel, i))
       continue;
 
     Arg->setName(Kernel->array[i].array->name);
 
     isl_id *Id = isl_space_get_tuple_id(Prog->array[i].space, isl_dim_set);
     const ScopArrayInfo *SAI = ScopArrayInfo::getFromId(isl::manage_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));
+
+    SmallVector<const SCEV *, 4> Sizes;
+
+    // TODO: take "correct" capture (const & or whatever of SAI)
+    // TODO: this is so fugly, find a better way to express this :(
+    ShapeInfo NewShape = [&](SmallVector<const SCEV *, 4> &Sizes) {
+      if (SAI->hasStrides()) {
+        // TODO: find some way to merge the code? Here, we know the outermose
+        // dimension index so we can start from 0. In the sizes code, we need
+        // to start from 1 to indicate that we do not know the shape of the
+        // outermost dim.
+        for (long j = 0, n = Kernel->array[i].array->n_index; j < n; j++) {
+          isl_ast_expr *DimSize = isl_ast_build_expr_from_pw_aff(
+              Build,
+              isl_multi_pw_aff_get_pw_aff(Kernel->array[i].array->bound, j));
+          auto V = ExprBuilder.create(DimSize);
+          Sizes.push_back(SE.getSCEV(V));
+        }
+        return SAI->getShape();
+      } else {
         Sizes.push_back(nullptr);
         for (long j = 1, n = Kernel->array[i].array->n_index; j < n; j++) {
           isl_ast_expr *DimSize = isl_ast_build_expr_from_pw_aff(
-          Build, isl_multi_pw_aff_get_pw_aff(Kernel->array[i].array->bound, j));
+              Build,
+              isl_multi_pw_aff_get_pw_aff(Kernel->array[i].array->bound, j));
           auto V = ExprBuilder.create(DimSize);
           Sizes.push_back(SE.getSCEV(V));
         }
+        return ShapeInfo::fromSizes(Sizes);
+      }
+    }(Sizes);
+
     const ScopArrayInfo *SAIRep =
-        S.getOrCreateScopArrayInfo(Val, EleTy, Sizes, MemoryKind::Array);
+        S.getOrCreateScopArrayInfo(Val, EleTy, NewShape, MemoryKind::Array);
     LocalArrays.push_back(Val);
 
     isl_ast_build_free(Build);
     KernelIds.push_back(Id);
     IDToSAI[Id] = SAIRep;
     Arg++;
   }
 
for (int i = 0; i < Kernel->n_var; ++i) {
     }
 
     for (int j = Var.array->n_index - 1; j >= 0; --j) {
       isl_val *Val = isl_vec_get_element_val(Var.size, j);
       long Bound = isl_val_get_num_si(Val);
       isl_val_free(Val);
       ArrayTy = ArrayType::get(ArrayTy, Bound);
     }
+    const ShapeInfo NewShape = ShapeInfo::fromSizes(Sizes);
 
     const ScopArrayInfo *SAI;
     Value *Allocation;
     if (Var.type == ppcg_access_shared) {
       auto GlobalVar = new GlobalVariable(
           *M, ArrayTy, false, GlobalValue::InternalLinkage, 0, Var.name,
           nullptr, GlobalValue::ThreadLocalMode::NotThreadLocal, 3);
       GlobalVar->setAlignment(EleTy->getPrimitiveSizeInBits() / 8);
       GlobalVar->setInitializer(Constant::getNullValue(ArrayTy));
 
       Allocation = GlobalVar;
     } else if (Var.type == ppcg_access_private) {
       Allocation = Builder.CreateAlloca(ArrayTy, 0, "private_array");
     } else {
       llvm_unreachable("unknown variable type");
     }
-    SAI =
-        S.getOrCreateScopArrayInfo(Allocation, EleTy, Sizes, MemoryKind::Array);
+    SAI = S.getOrCreateScopArrayInfo(Allocation, EleTy, NewShape,
+                                     MemoryKind::Array);
     Id = isl_id_alloc(S.getIslCtx().get(), Var.name, nullptr);
     IDToValue[Id] = Allocation;
     LocalArrays.push_back(Allocation);
     KernelIds.push_back(Id);
     IDToSAI[Id] = SAI;
   }
 }
 
if (!NodeBuilder.preloadInvariantLoads()) {
         auto *ExitingBlock = StartBlock->getUniqueSuccessor();
         assert(ExitingBlock);
         BasicBlock *MergeBlock = ExitingBlock->getUniqueSuccessor();
         P.insertRegionEnd(MergeBlock->getTerminator());
       }
 
       NodeBuilder.addParameters(S->getContext().release());
       Value *RTC = NodeBuilder.createRTC(Condition);
       Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
 
       Builder.SetInsertPoint(&*StartBlock->begin());
 
       NodeBuilder.create(Root);
     }
 
     /// In case a sequential kernel has more surrounding loops as any parallel
     /// kernel, the SCoP is probably mostly sequential. Hence, there is no

lib/Support/ScopHelper.cpp

bool polly::hasDebugCall(ScopStmt *Stmt) {
   if (Stmt->isRegionStmt()) {
     for (BasicBlock *RBB : Stmt->getRegion()->blocks())
       if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB))
         return true;
   }
 
   return false;
 }
+
+llvm::Optional<std::pair<CallInst *, GEPOperator *>>
+polly::getAbstractIndexingCall(MemAccInst Inst, ScalarEvolution &SE) {
+  //// TODO: I can get rid of all this crap and use SCEV to drill through the
+  //// bitcasts. Alas, this was written when I was more of an LLVM noob than I
+  //// currently am :)
+  //// TODO: clean this up please.
+
+  //// Case 1. (Total size of array not known)
+  //// %2 = tail call i64 @_gfortran_polly_array_index_2(i64 1, i64 %1, i64
+  //// %indvars.iv1, i64 %indvars.iv) #1
+  //// %3 = getelementptr float, float* %0, i64
+  //// %bitcast = bitcast %3 to <otherty>
+  //// %2 store float 2.000000e+00, float* %3, align 4 STORE <val> (GEP <bitcast>)
+  //// (CALL index_2(<strides>, <ixs>)))
+
+  //// Case 2. (Total size of array statically known)
+  //// %4 = tail call i64 @_gfortran_polly_array_index_2(i64 1, i64 5, i64
+  //// %indvars.iv1, i64 %indvars.iv) #1 %5 = getelementptr [25 x float], [25 x
+  //// float]* @__m_MOD_g_arr_const_5_5, i64 0, i64 %4 store float 4.200000e+01,
+  //// float* %5, align 4
+
+  Value *MaybeBitcast = Inst.getPointerOperand();
+  if (!MaybeBitcast)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  //// If we have a bitcast as the parameter to the instruction, strip off the
+  //// bitcast. Otherwise, return the original instruction operand.
+  //Value *MaybeGEP = [&]() -> Value * {
+  //  BitCastOperator *Bitcast = dyn_cast<BitCastOperator>(MaybeBitcast);
+  //  if (Bitcast) {
+  //    return Bitcast->getOperand(0);
+  //  }
+  //  return Inst.getPointerOperand();
+  //}();
+
+  GEPOperator *GEP = dyn_cast<GEPOperator>(MaybeBitcast);
+
+  if (!GEP)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  auto *MaybeCall = GEP->getOperand(GEP->getNumOperands() - 1);
+  assert(MaybeCall);
+
+  //GEPOperator *GEP = dyn_cast<GEPOperator>(MaybeBitcast);
+  CallInst *Call = dyn_cast<CallInst>(MaybeCall);
+  if (!Call)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  if (!Call->getCalledFunction()->getName().count(
+          POLLY_ABSTRACT_INDEX_BASENAME))
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  std::pair<CallInst *, GEPOperator *> p = std::make_pair(Call, GEP);
+  return Optional<std::pair<CallInst *, GEPOperator *>>(p);
+}

lib/Transform/ForwardOpTree.cpp

MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,
     Sizes.reserve(SAI->getNumberOfDimensions());
     SmallVector<const SCEV *, 4> Subscripts;
     Subscripts.reserve(SAI->getNumberOfDimensions());
     for (unsigned i = 0; i < SAI->getNumberOfDimensions(); i += 1) {
       Sizes.push_back(SAI->getDimensionSize(i));
       Subscripts.push_back(nullptr);
     }
 
-    MemoryAccess *Access =
-        new MemoryAccess(Stmt, LI, MemoryAccess::READ, SAI->getBasePtr(),
-                         LI->getType(), true, {}, Sizes, LI, MemoryKind::Array);
+    MemoryAccess *Access = new MemoryAccess(
+        Stmt, LI, MemoryAccess::READ, SAI->getBasePtr(), LI->getType(), true,
+        {}, ShapeInfo::fromSizes(Sizes), LI, MemoryKind::Array);
     S->addAccessFunction(Access);
     Stmt->addAccess(Access, true);
 
     Access->setNewAccessRelation(AccessRelation);
 
     return Access;
   }
 

test/ScopInfo/chpl_2d_init_shapeinfo.ll

+;RUN: opt -polly-only-func=test_chpl -polly-scops -polly-invariant-load-hoisting -analyze < %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%array_ty = type { i64, %array_ptr*, i8 }
+%array_ptr = type { [2 x i64], [2 x i64], [2 x i64], i64, double*, double*, i8 }
+
+; Function Attrs: readnone
+define internal i64 @polly_array_index(i64 %arg1, i64 %arg2, i64 %arg3, i64 %arg4, i64 %arg5) #0 {
+  %tmp = mul nsw i64 %arg4, %arg2
+  %tmp8 = add nsw i64 %tmp, %arg1
+  %tmp9 = mul nsw i64 %arg5, %arg3
+  %tmp10 = add nsw i64 %tmp8, %tmp9
+  ret i64 %tmp10
+}
+
+
+; Function Attrs: noinline
+define weak dso_local void @test_chpl(%array_ty* nonnull %arg) #1 {
+bb:
+  br label %bb23
+
+bb23:                                             ; preds = %bb, %bb37
+  %.0 = phi i64 [ 0, %bb ], [ %tmp38, %bb37 ]
+  br label %bb24
+
+bb24:                                             ; preds = %bb23, %bb24
+  %.01 = phi i64 [ 0, %bb23 ], [ %tmp36, %bb24 ]
+  %tmp25 = getelementptr inbounds %array_ty, %array_ty* %arg, i64 0, i32 1
+  %tmp26 = load %array_ptr*, %array_ptr** %tmp25, align 8
+  %tmp27 = getelementptr inbounds %array_ptr, %array_ptr* %tmp26, i64 0, i32 1, i64 1
+  store i64 1, i64* %tmp27, align 8
+  %tmp28 = getelementptr inbounds %array_ptr, %array_ptr* %tmp26, i64 0, i32 1, i64 0
+  %tmp29 = load i64, i64* %tmp28, align 8
+  %tmp30 = call i64 @polly_array_index(i64 0, i64 %tmp29, i64 1, i64 %.0, i64 %.01)
+  %tmp31 = getelementptr inbounds %array_ptr, %array_ptr* %tmp26, i64 0, i32 5
+  %tmp32 = load double*, double** %tmp31, align 8
+  %tmp33 = getelementptr inbounds double, double* %tmp32, i64 %tmp30
+  %tmp34 = add nuw nsw i64 %.01, %.0
+  %tmp35 = sitofp i64 %tmp34 to double
+  store double %tmp35, double* %tmp33, align 8
+  %tmp36 = add nuw nsw i64 %.01, 1
+  %exitcond = icmp ne i64 %tmp36, 1000
+  br i1 %exitcond, label %bb24, label %bb37
+
+bb37:                                             ; preds = %bb24
+  %tmp38 = add nuw nsw i64 %.0, 1
+  %exitcond8 = icmp ne i64 %tmp38, 1000
+  br i1 %exitcond8, label %bb23, label %bb39
+
+bb39:                                             ; preds = %bb37
+  ret void
+}
+
+attributes #0 = { readnone }
+attributes #1 = { noinline }