[Polly] [WIP] Introduce ShapeInfo into polly.

[bollu]

Summary

• Create a representation in Polly to disambiguate size based and stride based representations of arrays.

• Need to move ScopDetection code to detect these strided arrays.

• Need to move backend code (PPCGCodeGeneration) to this new representation.

• I have never taught Codegen about strided arrays, so that is something we would need to do as well.

I am backporting code from my branch: https://github.com/bollu/polly/tree/feature.

The branch that I am working on is: https://github.com/bollu/polly/tree/jul-3-port-shapeinfo-to-master

@cs15btech11044, help appreciated in moving code. You can send my repo a pull request into the branch (jul-3-port-shapeinfo-to-master) that moves more code.

[philip.pfaffe]

Before going into the details and nits:

Why isn't ShapeInfo a sum type? If you're worried about this, since both summands would be structurally identical, you can even distinguish using a single tag to save you some implementation time.

[bollu]

• 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.

I had 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.

IMO, the ShapeInfo should ideally only have pw_aff, since we theoretically only
understand affine accesses. However, since we _do_ allow nonaffine indexing,
this does not work. We need some representation that is not as heavy as SCEV (?).

We need some point in the design space which is not so painful to work
with.

[Meinersbur]

What is an array described by strides? What is it used for?

[bollu]

Extract out codegen as well.

This is completely untested :D. I'll run the polly test suite to make
sure that nothing is immediately broken.

This gives no guarantee that the actual code path which we need will
work (the stride code path), but at least tells us that we have not
broken the default code path.

Now, we need to test the stride code path from the chapel source code. I
can also run it on my internal "test base", which I don't think I can
open source. I should be able to add small code snippets from it as I
find bugs for tests, though.

[bollu]

@Meinersbur in polly, we use sizes per dimension, so the sizes data structure actually stores the size of a dimension. In the "stride" version, we rather store the "block size" of each dimension, which is akin to the Fortran representation, and the representation (if I understand the chapel representation correctly).

[cs15btech11044]

lib/CodeGen/IslExprBuilder.cpp

326

[suggestion] Could you change the variable name Map to something more specific? This improves the readability of this code snippet.

[Meinersbur]

In D48874#1150969, @bollu wrote:

@Meinersbur in polly, we use sizes per dimension, so the sizes data structure actually stores the size of a dimension. In the "stride" version, we rather store the "block size" of each dimension, which is akin to the Fortran representation, and the representation (if I understand the chapel representation correctly).

What is "block size"? How is to do with Fortran being column-major/1-indexed? How it an address computed using block sizes? How is non-aliasing ensured?

[bollu]

Abandoned in favour of D49024.

include/polly/CodeGen/IslExprBuilder.h

 ///   signedness for each subexpression during in the isl AST generation and
 ///   to use this information in our IslAstGenerator. Preliminary patches are
 ///   available, but have not been committed yet.
 ///
 class IslExprBuilder {
 public:
   /// A map from isl_ids to llvm::Values.
   typedef llvm::MapVector<isl_id *, llvm::AssertingVH<llvm::Value>> IDToValueTy;
+  /// A map from const SCEV* to llvm::Values
+  typedef llvm::MapVector<const llvm::SCEV *, llvm::AssertingVH<llvm::Value>>
+      SCEVToValueTy;
 
   typedef llvm::MapVector<isl_id *, const ScopArrayInfo *> IDToScopArrayInfoTy;
 
   /// A map from isl_ids to ScopArrayInfo objects.
   ///
   /// This map is used to obtain ScopArrayInfo objects for isl_ids which do not
   /// carry a ScopArrayInfo object in their user pointer. This is useful if the
   /// construction of ScopArrayInfo objects happens only after references (e.g.
public:
   /// @param GlobalMap   A mapping from llvm::Values used in the original scop
   ///                    region to a new set of llvm::Values.
   /// @param DL          DataLayout for the current Module.
   /// @param SE          ScalarEvolution analysis for the current function.
   /// @param DT          DominatorTree analysis for the current function.
   /// @param LI          LoopInfo analysis for the current function.
   /// @param StartBlock The first basic block after the RTC.
   IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue,
-                 ValueMapT &GlobalMap, const llvm::DataLayout &DL,
+    SCEVToValueTy &SCEVToValue, ValueMapT &GlobalMap, const llvm::DataLayout &DL,
                  llvm::ScalarEvolution &SE, llvm::DominatorTree &DT,
                  llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock);
 
   /// Create LLVM-IR for an isl_ast_expr[ession].
   ///
   /// @param Expr The ast expression for which we generate LLVM-IR.
   ///
   /// @return The llvm::Value* containing the result of the computation.
private:
   ///   - Use create(...) for all expressions that should be checked.
   ///   - Call getOverflowState() to get the value representing the current
   ///     state of the overflow flag.
   ///   - To stop tracking call setTrackOverflow(false).
   llvm::Value *OverflowState;
 
   PollyIRBuilder &Builder;
   IDToValueTy &IDToValue;
+  SCEVToValueTy &SCEVToValue;
   ValueMapT &GlobalMap;
 
   const llvm::DataLayout &DL;
   llvm::ScalarEvolution &SE;
   llvm::DominatorTree &DT;
   llvm::LoopInfo &LI;
   llvm::BasicBlock *StartBlock;
 
private:
   ///
   /// @param LHS  The left operand.
   /// @param RHS  The right operand.
   /// @param Name The (base) name of the new IR operations.
   ///
   /// @return A value that represents the result of the multiplication.
   llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS,
                          const llvm::Twine &Name = "");
+
+  // Provide a uniform interface to lookup replacements of the old value
+  // in the various maps we provide.
+  llvm::Value *getLatestValue(llvm::Value *Old);
+
 };
 } // namespace polly
 
 #endif

include/polly/CodeGen/IslNodeBuilder.h

isl_stat addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr,
                                bool CreateScalarRefs = true);
 
 class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
                  DominatorTree &DT, Scop &S, BasicBlock *StartBlock)
       : S(S), Builder(Builder), Annotator(Annotator),
-        ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI,
+        ExprBuilder(S, Builder, IDToValue, SCEVToValue,  ValueMap, DL, SE, DT, LI,
                     StartBlock),
         BlockGen(Builder, LI, SE, DT, ScalarMap, EscapeMap, ValueMap,
                  &ExprBuilder, StartBlock),
         RegionGen(BlockGen), DL(DL), LI(LI), SE(SE), DT(DT),
         StartBlock(StartBlock) {}
 
   virtual ~IslNodeBuilder() = default;
 
protected:
   /// loop iteration.
   LoopToScevMapT OutsideLoopIterations;
 
   // This maps an isl_id* to the Value* it has in the generated program. For now
   // on, the only isl_ids that are stored here are the newly calculated loop
   // ivs.
   IslExprBuilder::IDToValueTy IDToValue;
 
+  // This maps a const SCEV* to the Value* it has in the generated program. For
+  // now, this stores strides and offsets of SAIs.
+  IslExprBuilder::SCEVToValueTy SCEVToValue;
+
   /// A collection of all parallel subfunctions that have been created.
   SmallVector<Function *, 8> ParallelSubfunctions;
 
   /// Generate code for a given SCEV*
   ///
   /// This function generates code for a given SCEV expression. It generated
   /// code is emitted at the end of the basic block our Builder currently
   /// points to and the resulting value is returned.
protected:
   /// @returns False, iff a problem occurred and the value was not materialized.
   bool materializeParameters(__isl_take isl_set *Set);
 
   /// Materialize all parameters in the current scop.
   ///
   /// @returns False, iff a problem occurred and the value was not materialized.
   bool materializeParameters();
 
+  void materializeStridedArraySizes();
+
+
   // Extract the upper bound of this loop
   //
   // The isl code generation can generate arbitrary expressions to check if the
   // upper bound of a loop is reached, but it provides an option to enforce
   // 'atomic' upper bounds. An 'atomic upper bound is always of the form
   // iv <= expr, where expr is an (arbitrary) expression not containing iv.
   //
   // This function extracts 'atomic' upper bounds. Polly, in general, requires

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);
+                      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();
+  }
+
+  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,
+                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
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 Shape.getNumberOfDimensions();
   }
 
   /// 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 {
     assert(Dim < getNumberOfDimensions() && "Invalid dimension");
-    return DimensionSizes[Dim];
+    return Shape.sizes()[Dim];
   }
 
+  const SCEV *getDimensionStride(unsigned Dim) const {
+    assert(Dim < getNumberOfDimensions() && "Invalid dimension");
+    return Shape.strides()[Dim];
+  }
+
+
+  const SCEV *getStrideOffset() const { return Shape.offset(); }
+
   /// 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, in case the array is not newly created.
   isl::pw_aff getDimensionSizePw(unsigned Dim) const {
     assert(Dim < getNumberOfDimensions() && "Invalid dimension");
     return DimensionSizesPw[Dim];
#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:
   Type *ElementType;
 
   /// 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,
+                                              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,
                                      const std::string &BaseName,

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/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},
+                 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},
+                 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 receive
+  // 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,
+    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()) {
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,
+                                 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(), {},
+    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 *>(),
+      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) {
+  if (Shape.isInitialized()) {
+    const SmallVector<const SCEV *, 4> &DimensionSizes = Shape.sizes();
     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++) {
         auto *NewSize = NewSizes[i + ExtraDimsNew];
         auto *KnownSize = DimensionSizes[i + ExtraDimsOld];
         if (NewSize && KnownSize && NewSize != KnownSize)
           return false;
       }
 
       if (DimensionSizes.size() >= NewSizes.size())
         return true;
     }
-
+  }
+  SmallVector<const SCEV *, 4> DimensionSizes;
   DimensionSizes.clear();
   DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
                         NewSizes.end());
+  Shape.setSizes(DimensionSizes);
+
   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);
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
 
   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,
+                           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),
+      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;
 
+  // TODO: again, why do we have an _empty_ list here for size?
   ScopArrayInfo *SAI =
-      Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
+      Parent.getOrCreateScopArrayInfo(V, V->getType(), ShapeInfo::fromSizes({}), MemoryKind::Value);
   Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
-                            true, {}, {}, V, MemoryKind::Value);
+                            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,
+                                              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;

lib/CodeGen/IslExprBuilder.cpp

static cl::opt<OverflowTrackingChoice> OTMode(
     cl::values(clEnumValN(OT_NEVER, "never", "Never track the overflow bit."),
                clEnumValN(OT_REQUEST, "request",
                           "Track the overflow bit if requested."),
                clEnumValN(OT_ALWAYS, "always",
                           "Always track the overflow bit.")),
     cl::Hidden, cl::init(OT_REQUEST), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 IslExprBuilder::IslExprBuilder(Scop &S, PollyIRBuilder &Builder,
-                               IDToValueTy &IDToValue, ValueMapT &GlobalMap,
+                               IDToValueTy &IDToValue, SCEVToValueTy &SCEVToValue,
+                              ValueMapT &GlobalMap,
                                const DataLayout &DL, ScalarEvolution &SE,
                                DominatorTree &DT, LoopInfo &LI,
                                BasicBlock *StartBlock)
-    : S(S), Builder(Builder), IDToValue(IDToValue), GlobalMap(GlobalMap),
+    : S(S), Builder(Builder), IDToValue(IDToValue), SCEVToValue(SCEVToValue), GlobalMap(GlobalMap),
       DL(DL), SE(SE), DT(DT), LI(LI), StartBlock(StartBlock) {
   OverflowState = (OTMode == OT_ALWAYS) ? Builder.getFalse() : nullptr;
 }
 
 void IslExprBuilder::setTrackOverflow(bool Enable) {
   // If potential overflows are tracked always or never we ignore requests
   // to change the behavior.
   if (OTMode != OT_REQUEST)
Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
   if (isl_ast_expr_get_op_n_arg(Expr) == 1) {
     isl_ast_expr_free(Expr);
     if (PollyDebugPrinting)
       RuntimeDebugBuilder::createCPUPrinter(Builder, "\n");
     return Base;
   }
 
   IndexOp = nullptr;
+  
+  // TODO: Oh right, I had forgotten about _this_ amazing hack.
+  // In a nutshell, when we are generating code on the kernel side, we choose to lookup
+  // SCEVtoValueMap.
+  // What we should actually do is to _always_ query SCEVToValueMap, but only populate it
+  // when we are performing codegen on the kernel side.
+  //
+  // Does SCEVExpander automatically take care of this? IIRC, I had tried SCEVExpander but it
+  // failed for some reason. Maybe we should try to replace the SCEVToValueMap with SCEVExpander. 
+  const std::string Name = Builder.GetInsertBlock()->getModule()->getName();
+
+  // TODO: refactor this, remove the nesting. It is confusing to tell WTF is happening
+  // without pen-and-paper. The old code was already not super straightforward, and this just
+  // makes it worse.
+  if (SAI->hasStrides()) {
+    for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++) {
+      Value *NextIndex = create(isl_ast_expr_get_op_arg(Expr, u));
+      assert(NextIndex->getType()->isIntegerTy() &&
+             "Access index should be an integer");
+
+      Type *Ty = [&]() {
+        if (IndexOp)
+          return getWidestType(NextIndex->getType(), IndexOp->getType());
+        else
+          return NextIndex->getType();
+      }();
+
+      if (Ty != NextIndex->getType())
+        NextIndex = Builder.CreateIntCast(NextIndex, Ty, true);
+
+      const SCEV *DimSCEV = SAI->getDimensionStride(u - 1);
+      assert(DimSCEV);
+
+      Value *DimSize = nullptr;
+      llvm::ValueToValueMap Map(GlobalMap.begin(), GlobalMap.end());
+
+      // HACK: we do this because we know the kernel name.
+      if (Name.find("FUNC__") != std::string::npos) {
+        auto OldValue = SCEVToValue.find(DimSCEV);
+        if (OldValue == SCEVToValue.end())
+          assert(false && "!OldValue");
+
+        auto NewDimSizeIt = Map.find(OldValue->second);
+        if (NewDimSizeIt == Map.end())
+          assert(false && "!NewDimSizeIt");
+        DimSize = NewDimSizeIt->second;
+      } else {
+
+        DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV, SE, Map);
+        DimSize = expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
+                                &*Builder.GetInsertPoint(), nullptr,
+                                StartBlock->getSinglePredecessor());
+        DimSize = getLatestValue(DimSize);
+      }
+      assert(DimSize && "dimsize uninitialized");
+
+      if (Ty != NextIndex->getType())
+        NextIndex = Builder.CreateSExtOrTrunc(NextIndex, Ty,
+                                              "polly.access.idxval." + BaseName + std::to_string(u - 1));
+      if (Ty != DimSize->getType())
+        DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,
+                                            "polly.access.stride." + BaseName + std::to_string(u - 1));
+
+      NextIndex = createMul(NextIndex, DimSize, "polly.access.idxval_x_stride." + BaseName + std::to_string(u - 1));
+
+      if (PollyDebugPrinting)
+        RuntimeDebugBuilder::createCPUPrinter(Builder, "[", NextIndex, "]");
+      if (!IndexOp) {
+        IndexOp = NextIndex;
+      } else {
+        if (Ty != IndexOp->getType())
+          IndexOp = Builder.CreateIntCast(IndexOp, Ty, true);
+        IndexOp = createAdd(IndexOp, NextIndex, "polly.access.idx_accum." + BaseName);
+      } // end else
+    }   // end for loop over stride dims
+    assert(IndexOp && "expected correct index op");
+    Value *Offset = nullptr;
+    // If we are in the kernel, then the base pointer has already been
+    // offset correctly so we need not do anything about it.
+    if (Name.find("FUNC__") != std::string::npos) {
+      llvm::ValueToValueMap Map(GlobalMap.begin(), GlobalMap.end());
+        const SCEV *OffsetSCEV = SAI->getStrideOffset();
+        auto OldValue = SCEVToValue.find(OffsetSCEV);
+        if (OldValue == SCEVToValue.end())
+          assert(false && "!OldValue offset");
+
+        auto NewIt = Map.find(OldValue->second);
+        if (NewIt == Map.end()) {
+            Offset = OldValue->second;
+            // errs() << "OldValue: " << *OldValue->second << "\n";
+          // assert(false && "!NewIt offset");
+        }
+        else {
+            Offset = NewIt->second;
+        }
+        assert(Offset);
+        if (auto OffsetInst = dyn_cast<Instruction>(Offset)) {
+            assert(OffsetInst->getModule() == Builder.GetInsertBlock()->getModule());
+        }
+    } else {
+    const SCEV *OffsetSCEV = SAI->getStrideOffset();
+    llvm::ValueToValueMap Map(GlobalMap.begin(), GlobalMap.end());
+
+      // If we are outside a kernel, then we do need to synthesize an offset.
+      OffsetSCEV = SCEVParameterRewriter::rewrite(OffsetSCEV, SE, Map);
+      Offset = expandCodeFor(S, SE, DL, "polly", OffsetSCEV,
+                             OffsetSCEV->getType(), &*Builder.GetInsertPoint(),
+                             nullptr, StartBlock->getSinglePredecessor());
+      Offset = getLatestValue(Offset);
+    }
+    assert(Offset && "dimsize uninitialized");
+    Offset = Builder.CreateIntCast(Offset, IndexOp->getType(), true);
+    IndexOp = createAdd(IndexOp, Offset, "polly.access.offseted." + BaseName);
+  } // end hasStride
+  else {
     for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++) {
       Value *NextIndex = create(isl_ast_expr_get_op_arg(Expr, u));
       assert(NextIndex->getType()->isIntegerTy() &&
              "Access index should be an integer");
 
       if (PollyDebugPrinting)
         RuntimeDebugBuilder::createCPUPrinter(Builder, "[", NextIndex, "]");
 
       if (!IndexOp) {
         IndexOp = NextIndex;
       } else {
         Type *Ty = getWidestType(NextIndex->getType(), IndexOp->getType());
 
         if (Ty != NextIndex->getType())
           NextIndex = Builder.CreateIntCast(NextIndex, Ty, true);
         if (Ty != IndexOp->getType())
           IndexOp = Builder.CreateIntCast(IndexOp, Ty, true);
 
         IndexOp = createAdd(IndexOp, NextIndex, "polly.access.add." + BaseName);
       }
 
       // For every but the last dimension multiply the size, for the last
       // dimension we can exit the loop.
       if (u + 1 >= e)
         break;
 
       const SCEV *DimSCEV = SAI->getDimensionSize(u);
 
       llvm::ValueToValueMap Map(GlobalMap.begin(), GlobalMap.end());
       DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV, SE, Map);
       Value *DimSize =
           expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
                         &*Builder.GetInsertPoint(), nullptr,
                         StartBlock->getSinglePredecessor());
 
       Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType());
 
       if (Ty != IndexOp->getType())
         IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty,
                                             "polly.access.sext." + BaseName);
       if (Ty != DimSize->getType())
         DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,
                                             "polly.access.sext." + BaseName);
       IndexOp = createMul(IndexOp, DimSize, "polly.access.mul." + BaseName);
     }
+  }
 
   Access = Builder.CreateGEP(Base, IndexOp, "polly.access." + BaseName);
 
   if (PollyDebugPrinting)
     RuntimeDebugBuilder::createCPUPrinter(Builder, "\n");
   isl_ast_expr_free(Expr);
   return Access;
 }
Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) {
   case isl_ast_expr_id:
     return createId(Expr);
   case isl_ast_expr_int:
     return createInt(Expr);
   }
 
   llvm_unreachable("Unexpected enum value");
 }
+
+
+llvm::Value *IslExprBuilder::getLatestValue(llvm::Value *Old) {
+    if (GlobalMap.find(Old) != GlobalMap.end())
+        return GlobalMap.find(Old)->second;
+    return Old;
+}

lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::updateValues(ValueMapT &NewValues) {
   for (const auto &I : NewValues) {
     if (Inserted.count(I.first))
       continue;
 
     ValueMap[I.first] = I.second;
   }
 }
 
+
 Value *IslNodeBuilder::getLatestValue(Value *Original) const {
   auto It = ValueMap.find(Original);
   if (It == ValueMap.end())
     return Original;
   return It->second;
 }
 
 void IslNodeBuilder::createUserVector(__isl_take isl_ast_node *User,
Value *FinalValue =
         buildFADOutermostDimensionLoad(FAD, Builder, Array->getName());
     assert(FinalValue && "unable to build Fortran array "
                          "descriptor load of outermost dimension");
     IDToValue[Id] = FinalValue;
     isl_id_free(Id);
   }
   return true;
 }
+void IslNodeBuilder::materializeStridedArraySizes() {
+    for (ScopArrayInfo *Array : S.arrays()) {
+        if (!Array->hasStrides())
+            continue;
+
+
+        for (unsigned i = 0; i < Array->getNumberOfDimensions(); i++) {
+            isl_pw_aff *ParametricPwAff = Array->getDimensionSizePw(i).release();
+            assert(ParametricPwAff && "parametric pw_aff corresponding "
+                    "to outermost dimension does not "
+                    "exist");
+
+            isl_id *Id = isl_pw_aff_get_dim_id(ParametricPwAff, isl_dim_param, 0);
+            isl_pw_aff_free(ParametricPwAff);
+
+            assert(Id && "pw_aff is not parametric");
+
+            LLVM_DEBUG(
+            dbgs() << "-\n";
+            dbgs() << "i: " << i << "\n";
+            dbgs() << "ID: " <<Id << "\n";);
+            const SCEV *StrideSCEV = Array->getDimensionStride(i);
+            // dbgs() << "StrideSCEV: " << *StrideSCEV << "\n";
+
+            Value *Stride = generateSCEV(StrideSCEV);
+            assert(Stride);
+
+            // errs() << "StrideVal: " << *Stride << "\n";
+            IDToValue[Id] = Stride;
+            SCEVToValue[Array->getDimensionStride(i)] = Stride;
+            isl_id_free(Id);
+        }
+
+        const SCEV *OffsetSCEV = Array->getStrideOffset();
+        Value *Offset = generateSCEV(OffsetSCEV);
+        assert(Offset);
+        SCEVToValue[OffsetSCEV] = Offset;
+    }
+}
 
 Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
                                               isl_ast_build *Build,
                                               Instruction *AccInst) {
   isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);
   isl_ast_expr *Access =
       isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
   auto *Address = isl_ast_expr_address_of(Access);
void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
   materializeParameters();
 
   // materialize the outermost dimension parameters for a Fortran array.
   // NOTE: materializeParameters() does not work since it looks through
   // the SCEVs. We don't have a corresponding SCEV for the array size
   // parameter
   materializeFortranArrayOutermostDimension();
 
+
   // Generate values for the current loop iteration for all surrounding loops.
   //
   // We may also reference loops outside of the scop which do not contain the
   // scop itself, but as the number of such scops may be arbitrarily large we do
   // not generate code for them here, but only at the point of code generation
   // where these values are needed.
   Loop *L = LI.getLoopFor(S.getEntry());
 
   while (L != nullptr && S.contains(L))
     L = L->getParentLoop();
 
   while (L != nullptr) {
     materializeNonScopLoopInductionVariable(L);
     L = L->getParentLoop();
   }
 
+  // Materialize the stride information for each array
+  materializeStridedArraySizes();
+
   isl_set_free(Context);
 }
 
 Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
   /// We pass the insert location of our Builder, as Polly ensures during IR
   /// generation that there is always a valid CFG into which instructions are
   /// inserted. As a result, the insertpoint is known to be always followed by a
   /// terminator instruction. This means the insert point may be specified by a

lib/CodeGen/PPCGCodeGeneration.cpp

 }
 
 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 (const auto &I : IDToValue)
     SubtreeValues.insert(I.second);
 
   // NOTE: this is populated in IslNodeBuilder::addParameters
   // See [Code generation of induction variables of loops outside Scops].
   for (const auto &I : OutsideLoopIterations)
     SubtreeValues.insert(cast<SCEVUnknown>(I.second)->getValue());
 
+  for (const auto &I : SCEVToValue)
+    SubtreeValues.insert(I.second);
+
   isl_ast_node_foreach_descendant_top_down(
       Kernel->tree, collectReferencesInGPUStmt, &References);
 
   for (const SCEV *Expr : SCEVs) {
     findValues(Expr, SE, SubtreeValues);
     findLoops(Expr, Loops);
   }
 
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);
+        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;
   }
 }
 

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>(MaybeGEP);
+
+  if (!GEP)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  
+  auto *MaybeCall = GEP->getOperand(GEP->getNumOperands() - 1);
+  assert(MaybeCall);
+  
+  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);
+}
 No newline at end of file

lib/Transform/ForwardOpTree.cpp

MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,
     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);
+                         LI->getType(), true, {}, ShapeInfo::fromSizes(Sizes), LI, MemoryKind::Array);
     S->addAccessFunction(Access);
     Stmt->addAccess(Access, true);
 
     Access->setNewAccessRelation(AccessRelation);
 
     return Access;
   }