[Polly] [Strided arrays, multidimensional indexing, fortran support] Teach Polly multidimensional strided array indexing. [WIP]

[bollu]

Summary

Please do not try to review this patch, I'm putting it up so I can chip
away at this and remove all the hacks. Once that is done, I'll split it up
into managable patches.

This patch teaches:

• Polly to interpret multidimensional index expressions.
• ScopArrayInfo to use a ShapeInfo class to store info based on size / stride based representation.
• PPCGCodeGen to codegen for these strided arrays.
• IslNodeBuilder, IslExprBuilder, et. al about strided arrays.

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;
+  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,
-                 llvm::ScalarEvolution &SE, llvm::DominatorTree &DT,
-                 llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock);
+                 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.
   llvm::Value *create(__isl_take isl_ast_expr *Expr);
 
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;
 

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,
-                    StartBlock),
+        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;
 
   void addParameters(__isl_take isl_set *Context);
 
   /// Create Values which hold the sizes of the outermost dimension of all
   /// Fortran arrays in the current scop.
   ///
   /// @returns False, if a problem occurred and a Fortran array was not
   /// materialized. True otherwise.
   bool materializeFortranArrayOutermostDimension();
 
+  Value *extractStrideFromFAD(GlobalValue *FAD, int dimension);
+  Value *extractOffsetFromFAD(GlobalValue *FAD);
+  void materializeStridedArraySizes();
+
   /// Generate code that evaluates @p Condition at run-time.
   ///
   /// This function is typically called to generate the LLVM-IR for the
   /// run-time condition of the scop, that verifies that all the optimistic
   /// assumptions we have taken during scop modeling and transformation
   /// hold at run-time.
   ///
   /// @param Condition The condition to evaluate
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.

include/polly/ScopBuilder.h

class ScopBuilder {
   Value *findFADAllocationVisible(MemAccInst Inst);
 
   // @}
 
   // Build the SCoP for Region @p R.
   void buildScop(Region &R, AssumptionCache &AC,
                  OptimizationRemarkEmitter &ORE);
 
+  /// Try to build an index expression from a load of an abstract location
+  /// Load/Store <array> (GEP <function idx>)
+  ///
+  /// @param Inst       The Load/Store instruction that access the memory
+  /// @param Stmt       The parent statement of the instruction
+  bool buildAccessPollyAbstractMatrix(MemAccInst Inst, ScopStmt *Stmt);
+
   /// Try to build a multi-dimensional fixed 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
   ///
   /// @returns True if the access could be built, False otherwise.
   bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt);
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

 
 #include "polly/ScopDetection.h"
 #include "polly/Support/SCEVAffinator.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DebugLoc.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;
+
+  llvm::Optional<GlobalValue *>HackFAD;
+
+  ShapeInfo(Optional<ArrayRef<const SCEV *>> SizesRef,
+            Optional<ArrayRef<const SCEV *>> StridesRef,
+            llvm::Optional<const SCEV *> Offset, 
+            llvm::Optional<GlobalValue *>HackFAD)
+      : Offset(Offset), HackFAD(HackFAD) {
+    // 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), HackFAD(None) {}
+
+public:
+  static ShapeInfo fromSizes(ArrayRef<const SCEV *> Sizes) {
+    return ShapeInfo(OptionalSCEVArrayRefTy(Sizes), None, None, None);
+  }
+
+  ShapeInfo(const ShapeInfo &other) {
+    Sizes = other.Sizes;
+    Strides = other.Strides;
+    Offset = other.Offset;
+    HackFAD = other.HackFAD;
+  }
+
+  ShapeInfo &operator=(const ShapeInfo &other) {
+    Sizes = other.Sizes;
+    Strides = other.Strides;
+    Offset = other.Offset;
+    HackFAD = other.HackFAD;
+    return *this;
+  }
+
+  static ShapeInfo fromStrides(ArrayRef<const SCEV *> Strides,
+                               const SCEV *Offset,
+                               GlobalValue *FAD) {
+    assert(Offset && "offset is null");
+    return ShapeInfo(None, OptionalSCEVArrayRefTy(Strides),
+                     Optional<const SCEV *>(Offset),
+                     Optional<GlobalValue *>(FAD));
+  }
+
+  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, GlobalValue *NewHackFAD) {
+    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());
+
+    HackFAD = NewHackFAD;
+
+    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(); }
+
+
+  GlobalValue *hackFAD() const { return HackFAD.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
public:
   /// @param ElementType    The type of the elements stored in the array.
   /// @param IslCtx         The isl context used to create the base pointer id.
   /// @param DimensionSizes A vector containing the size of each dimension.
   /// @param Kind           The kind of the array object.
   /// @param DL             The data layout of the module.
   /// @param S              The scop this array object belongs to.
   /// @param BaseName       The optional name of this memory reference.
   ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx IslCtx,
-                ArrayRef<const SCEV *> DimensionSizes, 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.
+  void overwriteSizeWithStrides(ArrayRef<const SCEV *> Strides,
+                                const SCEV *Offset, GlobalValue *HackFAD);
+
+  /// Update the strides of a ScopArrayInfo object.
+  bool updateStrides(ArrayRef<const SCEV *> Strides, const SCEV *Offset, GlobalValue *HackFAD);
+
   /// 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.
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();
   }
 
+  ShapeInfo getShape() const { return Shape; }
+
   /// 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];
   }
 
+  isl::id getDimensionSizeId(unsigned Dim) const {
+    isl_pw_aff *ParametricPwAff = getDimensionSizePw(Dim).release();
+    assert(ParametricPwAff && "parametric pw_aff corresponding "
+                              "to 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");
+    return isl::manage(Id);
+  };
+
   /// Get the canonical element type of this array.
   ///
   /// @returns The canonical element type of this array.
   Type *getElementType() const { return ElementType; }
 
   /// Get element size in bytes.
   int getElemSizeInBytes() 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:
   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.
-  SmallVector<const SCEV *, 4> Sizes;
+  ShapeInfo Shape;
   // @}
 
   // Properties describing the accessed element.
   // @{
 
   /// The access instruction of this memory access.
   ///
   /// For memory accesses of kind MemoryKind::Array the access instruction is
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 ShapeInfo  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 Sizes,
                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:
   const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; }
 
   /// Return the (possibly new) ScopArrayInfo object for @p Access.
   ///
   /// @param ElementType The type of the elements stored in this array.
   /// @param Kind        The kind of the array info object.
   /// @param BaseName    The optional name of this memory reference.
   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

 // Small functions that help with LLVM-IR.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.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;

 // first non-boxed surrounding loop for Polly. If the loop is affine, return
 // the loop itself.
 //
 // @param BB            Pointer to the Basic Block to analyze.
 // @param LI            Reference to the LoopInfo.
 // @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
 llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
                                     const BoxedLoopsSetTy &BoxedLoops);
+
+static const std::string POLLY_ABSTRACT_INDEX_BASENAME = "polly_array_index";
+llvm::Optional<std::pair<llvm::CallInst *, llvm::GEPOperator *>>
+getAbstractMatrixCall(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) {
   if (DestAccFunc->isZero())
     return true;
 
   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
   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) {
   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 
   if (CI == nullptr)
     return false;
 
   if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
     return true;
 
+
   bool ReadOnly = false;
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
   auto *CalledFunction = CI->getCalledFunction();
+  if (CalledFunction->getName().count(POLLY_ABSTRACT_INDEX_BASENAME)) 
+      return true;
+
   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:
for (const auto &Arg : CI->arg_operands()) {
         continue;
 
       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
       if (ArgSCEV->isZero())
         continue;
 
       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
       addArrayAccess(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 (buildAccessPollyAbstractMatrix(Inst, Stmt))
+    return;
+
   if (buildAccessMemIntrinsic(Inst, Stmt))
     return;
 
   if (buildAccessCallInst(Inst, Stmt))
     return;
 
   if (buildAccessMultiDimFixed(Inst, Stmt))
     return;
 
   if (buildAccessMultiDimParam(Inst, Stmt))
     return;
 
   buildAccessSingleDim(Inst, Stmt);
 }
+static const bool AbstractMatrixDebug = false;
+
+// %v = bitcast (%w)
+// %v = %w
+// return %w in both cases.
+Value *unwrapPossibleBitcast(Value *V) {
+    if (isa<BitCastOperator>(V))
+        return cast<BitCastOperator>(V)->getOperand(0);
+    return V;
+}
+
+//Return @__data_radiation_MOD_cobi from stride %7
+// %indvars.iv = phi i64 [ %indvars.iv.next, %"4" ], [ -10, %"3" ]
+// %0 = load float*, float** bitcast (%"struct.array2_real(kind=4)"* @__m_MOD_g_arr to float**), align 32
+// %1 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=4)", %"struct.array2_real(kind=4)"* @__m_MOD_g_arr, i64 0, i32 3, i64 1, i32 0), align 8
+// %2 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=4)", %"struct.array2_real(kind=4)"* @__m_MOD_g_arr, i64 0, i32 1), align 8
+// %3 = tail call i64 @_gfortran_polly_array_index_2(i64 %2, i64 %1, i64 1, i64 %indvars.iv, i64 %indvars.iv1) #3
+GlobalValue *getBasePtrForVariableStride(Value *V) {
+  if(AbstractMatrixDebug) errs() << __PRETTY_FUNCTION__ << ":" << __LINE__ << "\n";
+  LoadInst *LI; 
+  LI = dyn_cast<LoadInst>(V);
+  if (!LI) return nullptr;
+
+  if(AbstractMatrixDebug) errs() << "LoadInst: " << *LI << "\n";
+  Value *LoadBase = LI->getOperand(0);
+  if(AbstractMatrixDebug) errs() << "LoadBase: " << *LI << "\n";
+  Value *CleanedLoadBase = unwrapPossibleBitcast(LoadBase);
+  if(AbstractMatrixDebug) errs() << "CleanedLoadBase: " << *CleanedLoadBase << "\n";
+
+  GEPOperator *GEP = nullptr;
+  GEP = dyn_cast<GEPOperator>(CleanedLoadBase);
+  if (!GEP) return nullptr;
+  if(AbstractMatrixDebug) errs() << "GEP: " << *GEP << "\n";
+
+  return dyn_cast<GlobalValue>(GEP->getPointerOperand());
+}
+bool ScopBuilder::buildAccessPollyAbstractMatrix(MemAccInst Inst,
+                                                 ScopStmt *Stmt) {
+
+  auto optionalCallGEP = getAbstractMatrixCall(Inst, SE);
+  if (!optionalCallGEP)
+    return false;
+
+  CallInst *Call;
+  GEPOperator *GEP;
+  std::tie(Call, GEP) = *optionalCallGEP;
+
+  if (AbstractMatrixDebug) {
+      errs() << "MemAccInst: " << *Inst << "\n";
+      errs() << "Call: " << *Call << "\n";
+      errs() << "GEP: " << *GEP << "\n";
+  }
+
+  assert(Call->getNumArgOperands() % 2 == 1 &&
+         "expect offset, stride, index pairs\n");
+  const int NArrayDims = Call->getNumArgOperands() / 2;
+  if (AbstractMatrixDebug)
+    errs() << "Num array dims: " << NArrayDims << "\n";
+
+  // F(stride1, stride2, .., strideN, ix1, ix2, ..., ixN)
+
+  Value *BasePtr = GEP->getPointerOperand();
+
+  std::vector<const SCEV *> Subscripts;
+  std::vector<const SCEV *> Strides;
+
+  if (isa<UndefValue>(Call->getArgOperand(0)))
+    return false;
+
+  const SCEV *Offset = SE.getSCEV(Call->getArgOperand(0));
+  if (AbstractMatrixDebug)
+    errs() << "Offset: " << *Offset << "\n";
+
+  // If all the strides are constants, then we don't need the FAD.
+  // Otherwise, we need the FAD to load the correct values of strides
+  // and offset.
+  GlobalValue *FAD = nullptr;
+  for (int i = 0; i < NArrayDims; i++) {
+    Value *Ix = Call->getArgOperand(1 + NArrayDims + i);
+    Value *Stride = Call->getArgOperand(1 + i);
+    if (isa<UndefValue>(Ix) || isa<UndefValue>(Stride))
+      return false;
+
+    if (AbstractMatrixDebug)
+      errs() << i << " |Raw Ix: " << *Ix << " |Raw Stride: " << *Stride << "\n";
+    Subscripts.push_back(SE.getSCEV(Ix));
+    const SCEV *StrideSCEV = SE.getSCEV(Stride);
+
+    // Try to get an FAD from a stride.
+    if (!isa<SCEVConstant>(StrideSCEV) && FAD == nullptr) {
+        FAD = getBasePtrForVariableStride(Stride);
+        // assert(FAD && "need legal FAD");
+    }
+    Strides.push_back(StrideSCEV);
+  }
+
+  for (unsigned i = 0; i < Subscripts.size(); ++i) {
+    if (AbstractMatrixDebug)
+      errs() << i << "| "
+             << " Sub: " << *Subscripts[i] << " |Stride: " << *Strides[i]
+             << "\n";
+  }
+
+
+  Value *Val = Inst.getValueOperand();
+  Type *ElementType = Val->getType();
+  assert(BasePtr);
+  assert(ElementType);
+
+  if (AbstractMatrixDebug)
+    errs() << "GEPInto / BasePtr (array): " << *BasePtr << "\n";
+  if (AbstractMatrixDebug)
+    errs() << "ElementType: " << *ElementType << "\n";
+
+  if (AbstractMatrixDebug)
+    errs() << "Val: " << *Val << "\n";
+
+  enum MemoryAccess::AccessType AccType =
+      isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
+
+
+  if (AbstractMatrixDebug) {
+    errs() << "AccType: ";
+    switch (AccType) {
+    case MemoryAccess::AccessType::READ:
+      errs() << "ReadAccess\n";
+      break;
+    case MemoryAccess::AccessType::MUST_WRITE:
+      errs() << "MustWriteAccess\n";
+      break;
+    default:
+      report_fatal_error("expected only READ/MUST_WRITE");
+    }
+  }
+
+  /*
+   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);
+ */
+
+  // 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, true, Subscripts,
+                 ShapeInfo::fromStrides(Strides, Offset, FAD), Val);
+
+  if (AbstractMatrixDebug)
+    errs() << "Added array access successfully!\n";
+
+  return true;
+}
 
 void ScopBuilder::buildAccessFunctions() {
   for (auto &Stmt : *scop) {
     if (Stmt.isBlockStmt()) {
       buildAccessFunctions(&Stmt, *Stmt.getBasicBlock());
       continue;
     }
 
for (Instruction &Inst : BB) {
     if (!IsExitBlock)
       buildEscapingDependences(&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) {
+
+ //   DEBUG(
+ //    dbgs() << "\n" << __PRETTY_FUNCTION__ << ":" << __LINE__ << "\n";
+ //    dbgs() << "\t-BaseAddr: " << *BaseAddress << "\n";
+ //    dbgs() << "\t-ElemType: " << *ElementType << "\n";
+ //    dbgs() << "\t-AccessValue: " << *AccessValue << "\n";);
   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);
if (Access->isPHIKind())
       Ty = MemoryKind::PHI;
     else if (Access->isExitPHIKind())
       Ty = MemoryKind::ExitPHI;
     else if (Access->isValueKind())
       Ty = MemoryKind::Value;
     else
       Ty = MemoryKind::Array;
 
+    // NOTE: This is why We need to teach ScopArrayInfo to accept Shape.
     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()->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;
+  if (Mul->getNumOperands() != 2)
+    return false;
+  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();
 
+
   // Indirect calls are not supported.
   if (CalledFunction == nullptr)
     return false;
   
+  // Function being called is a polly indexing function.
+  if (CalledFunction->getName().count(POLLY_ABSTRACT_INDEX_BASENAME)) {
+      return true;
+  }
+
   if (AllowModrefCall) {
     switch (AA.getModRefBehavior(CalledFunction)) {
     case FMRB_UnknownModRefBehavior:
       return false;
     case FMRB_DoesNotAccessMemory:
     case FMRB_OnlyReadsMemory:
       // Implicitly disable delinearization since we have an unknown
       // accesses with an unknown access function.
if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
       if (auto *Load = dyn_cast<LoadInst>(V)) {
         if (Context.CurRegion.contains(Load) &&
             isHoistableLoad(Load, CurRegion, LI, SE, DT))
           Context.RequiredILS.insert(Load);
         continue;
       }
     }
     if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion, Scope, false,
-                                  Context.RequiredILS))
+                                  Context.RequiredILS)) {
+
       return invalid<ReportNonAffineAccess>(
           Context, /*Assert=*/true, DelinearizedSize,
           Context.Accesses[BasePointer].front().first, BaseValue);
     }
+  }
 
   // No array shape derived.
   if (Sizes.empty()) {
     if (AllowNonAffine)
       return true;
 
     for (const auto &Pair : Context.Accesses[BasePointer]) {
       const Instruction *Insn = Pair.first;

 // delinearized we continue. Otherwise, we either report a failure or, if
 // non-affine accesses are allowed, we drop the information. In case the
 // information is dropped the memory accesses need to be overapproximated
 // when translated to a polyhedral representation.
 bool ScopDetection::computeAccessFunctions(
     DetectionContext &Context, const SCEVUnknown *BasePointer,
     std::shared_ptr<ArrayShape> Shape) const {
   Value *BaseValue = BasePointer->getValue();
+
   bool BasePtrHasNonAffine = false;
   MapInsnToMemAcc TempMemoryAccesses;
   for (const auto &Pair : Context.Accesses[BasePointer]) {
     const Instruction *Insn = Pair.first;
     auto *AF = Pair.second;
     AF = SCEVRemoveMax::rewrite(AF, SE);
     bool IsNonAffine = false;
     TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape)));
     MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
     auto *Scope = LI.getLoopFor(Insn->getParent());
 
     if (!AF) {
       if (isAffine(Pair.second, Scope, Context))
         Acc->DelinearizedSubscripts.push_back(Pair.second);
-      else
+      else {
         IsNonAffine = true;
+      }
     } else {
       if (Shape->DelinearizedSizes.size() == 0) {
         Acc->DelinearizedSubscripts.push_back(AF);
       } else {
         SE.computeAccessFunctions(AF, Acc->DelinearizedSubscripts,
                                   Shape->DelinearizedSizes);
-        if (Acc->DelinearizedSubscripts.size() == 0)
+        if (Acc->DelinearizedSubscripts.size() == 0) {
           IsNonAffine = true;
         }
+      }
       for (const SCEV *S : Acc->DelinearizedSubscripts)
         if (!isAffine(S, Scope, Context))
           IsNonAffine = true;
     }
 
     // (Possibly) report non affine access
     if (IsNonAffine) {
       BasePtrHasNonAffine = true;
-      if (!AllowNonAffine)
+      if (!AllowNonAffine) {
         invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
                                        Insn, BaseValue);
+      }
+
       if (!KeepGoing && !AllowNonAffine)
         return false;
     }
   }
 
   if (!BasePtrHasNonAffine)
     Context.InsnToMemAcc.insert(TempMemoryAccesses.begin(),
                                 TempMemoryAccesses.end());
for (auto &Pair : Context.NonAffineAccesses) {
     }
   }
   return true;
 }
 
 bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF,
                                   const SCEVUnknown *BP,
                                   DetectionContext &Context) const {
-
   if (!BP)
     return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, Inst);
 
   auto *BV = BP->getValue();
   if (isa<UndefValue>(BV))
     return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, Inst);
 
   // FIXME: Think about allowing IntToPtrInst
if (!AS.isMustAlias()) {
     return invalid<ReportAlias>(Context, /*Assert=*/true, Inst, AS);
   }
 
   return true;
 }
 
 bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
                                         DetectionContext &Context) const {
+  if (getAbstractMatrixCall(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_give isl_schedule *
 combineInSequence(__isl_take isl_schedule *Prev,
                   __isl_take isl_schedule *Succ) {
   if (!Prev)
     return Succ;
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);
+  /*
+  errs() << "\n" << __PRETTY_FUNCTION__<< ":" << __LINE__<< "\n";
+  if(BasePtr) errs() << "\t-BasePtr: " << *BasePtr << "\n";
+  if(BaseName) errs() << "\t-BaseName: " << BaseName << "\n";
+  errs() << "\t-ElementType: " << *ElementType << "\n";
+  */
+
+  
+  // Shape.mapSizes([&] (SmallVector<const SCEV*, 4> &Sizes)  {
+  // this->updateSizes(Sizes); });
+  if (Shape.hasSizes())
+    updateSizes(Shape.sizes());
+  else
+    updateStrides(Shape.strides(), Shape.offset(), Shape.hackFAD());
 
   if (!BasePtr || Kind != MemoryKind::Array) {
     BasePtrOriginSAI = nullptr;
     return;
   }
 
   BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
   if (BasePtrOriginSAI)

 
 bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo *Array) const {
   if (Array->getElementType() != getElementType())
     return false;
 
   if (Array->getNumberOfDimensions() != getNumberOfDimensions())
     return false;
 
+  if (this->hasStrides() != Array->hasStrides())
+    return false;
+
+  if (this->hasStrides()) {
+    for (unsigned i = 0; i < getNumberOfDimensions(); i++)
+      if (Array->getDimensionStride(i) != getDimensionStride(i))
+        return false;
+  } else {
     for (unsigned i = 0; i < getNumberOfDimensions(); i++)
       if (Array->getDimensionSize(i) != getDimensionSize(i))
         return false;
+  }
 
   return true;
 }
 
 void ScopArrayInfo::updateElementType(Type *NewElementType) {
   if (NewElementType == ElementType)
     return;
 

 void ScopArrayInfo::applyAndSetFAD(Value *FAD) {
   assert(FAD && "got invalid Fortran array descriptor");
   if (this->FAD) {
     assert(this->FAD == FAD &&
            "receiving different array descriptors for same array");
     return;
   }
 
+  if (!this->hasStrides()) {
+    errs() << "WARNING: Fortran SAI: " << getName()
+           << "does not have strides!\n";
     assert(DimensionSizesPw.size() > 0 && !DimensionSizesPw[0]);
     assert(!this->FAD);
     this->FAD = FAD;
 
     isl::space Space(S.getIslCtx(), 1, 0);
 
     std::string param_name = getName();
     param_name += "_fortranarr_size";
     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[0] = PwAff;
   }
+}
+
+void ScopArrayInfo::overwriteSizeWithStrides(ArrayRef<const SCEV *> Strides,
+                                             const SCEV *Offset,
+                                             GlobalValue *FAD) {
+
+  // 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, FAD);
+  updateStrides(Strides, Offset, FAD);
+}
+bool ScopArrayInfo::updateStrides(ArrayRef<const SCEV *> Strides,
+                                  const SCEV *Offset,
+                                  GlobalValue *FAD) {
+  Shape.setStrides(Strides, Offset, FAD);
+  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 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 (Shape.hasSizes()) {
+    // OS << "(Sizes)";
     if (!IsOutermostSizeKnown && getNumberOfDimensions() > 0 &&
         !getDimensionSize(0)) {
       OS << "[*]";
       u++;
     }
     for (; u < getNumberOfDimensions(); u++) {
       OS << "[";
 
       if (SizeAsPwAff) {
         isl::pw_aff Size = getDimensionSizePw(u);
         OS << " " << Size << " ";
       } else {
         OS << *getDimensionSize(u);
       }
 
       OS << "]";
     }
+  } else {
+    OS << "(Strides)";
+    for (; u < getNumberOfDimensions(); u++) {
+      OS << "[";
+      if (SizeAsPwAff) {
+        isl::pw_aff Size = getDimensionSizePw(u);
+        OS << " " << Size << " ";
+      } else {
+        const SCEV *Stride = Shape.strides()[u];
+        assert(Stride);
+        OS << *Stride;
+      }
+      OS << "]";
+    }
+    OS << ";[Offset: " << *Shape.offset() << "]";
+  }
 
   OS << ";";
 
   if (BasePtrOriginSAI)
     OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
 
   OS << " // Element size " << getElemSizeInBytes() << "\n";
 }
void MemoryAccess::wrapConstantDimensions() {
   Relation = Relation.apply_range(isl::map::from_multi_aff(DivModAff));
   Relation = Relation.detect_equalities();
   AccessRelation = Relation;
 }
 
 void MemoryAccess::updateDimensionality() {
   auto *SAI = getScopArrayInfo();
   isl::space ArraySpace = SAI->getSpace();
+
   isl::space AccessSpace = AccessRelation.get_space().range();
   isl::ctx Ctx = ArraySpace.get_ctx();
 
   auto DimsArray = ArraySpace.dim(isl::dim::set);
   auto DimsAccess = AccessSpace.dim(isl::dim::set);
   auto DimsMissing = DimsArray - DimsAccess;
 
   auto *BB = getStatement()->getEntryBlock();

 // statement. If we now project out all loop dimensions, we obtain a set of
 // parameters that may cause statement instances to be executed that may
 // possibly yield out of bound memory accesses. The complement of these
 // constraints is the set of constraints that needs to be assumed to ensure such
 // statement instances are never executed.
 void MemoryAccess::assumeNoOutOfBound() {
   if (PollyIgnoreInbounds)
     return;
+  if (Shape.hasStrides())
+    return;
+
   auto *SAI = getScopArrayInfo();
   isl::space Space = getOriginalAccessRelationSpace().range();
   isl::set Outside = isl::set::empty(Space);
   for (int i = 1, Size = Space.dim(isl::dim::set); i < Size; ++i) {
     isl::local_space LS(Space);
     isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);
     isl::pw_aff Zero = isl::pw_aff(LS);
 
void MemoryAccess::assumeNoOutOfBound() {
   if (!PollyPreciseInbounds)
     Outside = Outside.gist_params(Statement->getDomain().params());
   Statement->getParent()->recordAssumption(INBOUNDS, Outside.release(), Loc,
                                            AS_ASSUMPTION);
 }
 
 void MemoryAccess::buildMemIntrinsicAccessRelation() {
   assert(isMemoryIntrinsic());
-  assert(Subscripts.size() == 2 && Sizes.size() == 1);
+  assert(Subscripts.size() == 2 && Shape.getNumberOfDimensions() == 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 we are stride-based, it makes no sense to deliniearlise;
+  if (Shape.hasStrides())
+    return;
+
+  if (Shape.getNumberOfDimensions() < 2 || isa<SCEVConstant>(Shape.sizes()[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.sizes()[i + 1]);
 
     isl::space SpaceSize = DimSize.get_space();
     isl::id ParamId =
         give(isl_space_get_dim_id(SpaceSize.get(), 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);
+  // Sizes.push_back(nullptr);
+  SmallVector<const SCEV *, 4> &Sizes = Shape.sizes_mut();
   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"};
   const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
 
   std::string IdName = Stmt->getBaseName() + Access;
void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA) {
   }
 }
 
 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);
+  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) {
Context =
         addRangeBoundsToSet(give(Context), SRange, PDim++, isl::dim::param)
             .release();
   }
 }
 
 static std::vector<isl::id> getFortranArrayIds(Scop::array_range Arrays) {
   std::vector<isl::id> OutermostSizeIds;
   for (auto Array : Arrays) {
+    if (Array->hasStrides())
+      continue;
     // To check if an array is a Fortran array, we check if it has a isl_pw_aff
     // for its outermost dimension. Fortran arrays will have this since the
     // outermost dimension size can be picked up from their runtime description.
     // TODO: actually need to check if it has a FAD, but for now this works.
     if (Array->getNumberOfDimensions() > 0) {
       isl::pw_aff PwAff = Array->getDimensionSizePw(0);
       if (!PwAff)
         continue;
buildMinMaxAccess(isl::set Set, Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
   isl::pw_multi_aff MinPMA, MaxPMA;
   isl::pw_aff LastDimAff;
   isl::aff OneAff;
   unsigned Pos;
   isl::ctx Ctx = Set.get_ctx();
 
   Set = Set.remove_divs();
 
-  if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain)
+  if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
     return isl::stat::error;
+  }
 
   // Restrict the number of parameters involved in the access as the lexmin/
   // lexmax computation will take too long if this number is high.
   //
   // Experiments with a simple test case using an i7 4800MQ:
   //
   //  #Parameters involved | Time (in sec)
   //            6          |     0.01
   //            7          |     0.04
   //            8          |     0.12
   //            9          |     0.40
   //           10          |     1.54
   //           11          |     6.78
   //           12          |    30.38
   //
   if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
     unsigned InvolvedParams = 0;
     for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
       if (Set.involves_dims(isl::dim::param, u, 1))
         InvolvedParams++;
 
-    if (InvolvedParams > RunTimeChecksMaxParameters)
+    if (InvolvedParams > RunTimeChecksMaxParameters) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
       return isl::stat::error;
     }
+  }
 
-  if (isl_set_n_basic_set(Set.get()) > RunTimeChecksMaxAccessDisjuncts)
+  if (isl_set_n_basic_set(Set.get()) > RunTimeChecksMaxAccessDisjuncts) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
     return isl::stat::error;
+  }
 
   MinPMA = Set.lexmin_pw_multi_aff();
   MaxPMA = Set.lexmax_pw_multi_aff();
 
-  if (isl_ctx_last_error(Ctx.get()) == isl_error_quota)
+  if (isl_ctx_last_error(Ctx.get()) == isl_error_quota) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
     return isl::stat::error;
+  }
 
   MinPMA = MinPMA.coalesce();
   MaxPMA = MaxPMA.coalesce();
 
   // Adjust the last dimension of the maximal access by one as we want to
   // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
   // we test during code generation might now point after the end of the
   // allocated array but we will never dereference it anyway.
static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S,
   Accesses = Accesses.intersect_domain(Domains);
   isl::union_set Locations = Accesses.range();
   Locations = Locations.coalesce();
   Locations = Locations.detect_equalities();
 
   auto Lambda = [&MinMaxAccesses, &S](isl::set Set) -> isl::stat {
     return buildMinMaxAccess(Set, MinMaxAccesses, S);
   };
-  return Locations.foreach_set(Lambda) == isl::stat::ok;
+  bool Valid =  Locations.foreach_set(Lambda) == isl::stat::ok;
+
+  return Valid;
 }
 
 /// Helper to treat non-affine regions and basic blocks the same.
 ///
 ///{
 
 /// Return the block that is the representing block for @p RN.
 static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
bool Scop::buildAliasGroups(AliasAnalysis &AA) {
   AliasGroupVectorTy AliasGroups;
   DenseSet<const ScopArrayInfo *> HasWriteAccess;
 
   std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses(AA);
 
   splitAliasGroupsByDomain(AliasGroups);
 
   for (AliasGroupTy &AG : AliasGroups) {
-    if (!hasFeasibleRuntimeContext())
+    if (!hasFeasibleRuntimeContext()) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
       return false;
+    }
 
     {
       IslMaxOperationsGuard MaxOpGuard(getIslCtx(), OptComputeOut);
       bool Valid = buildAliasGroup(AG, HasWriteAccess);
-      if (!Valid)
+      if (!Valid) {
+          errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
         return false;
       }
+    }
     if (isl_ctx_last_error(getIslCtx()) == isl_error_quota) {
       invalidate(COMPLEXITY, DebugLoc());
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
       return false;
     }
   }
 
   return true;
 }
 
 bool Scop::buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
if (ReadWriteArrays.empty())
     return true;
 
   // For non-affine accesses, no alias check can be generated as we cannot
   // compute a sufficiently tight lower and upper bound: bail out.
   for (MemoryAccess *MA : AliasGroup) {
     if (!MA->isAffine()) {
       invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),
                  MA->getAccessInstruction()->getParent());
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
       return false;
     }
   }
 
   // Ensure that for all memory accesses for which we generate alias checks,
   // their base pointers are available.
   for (MemoryAccess *MA : AliasGroup) {
     if (MemoryAccess *BasePtrMA = lookupBasePtrAccess(MA))
       addRequiredInvariantLoad(
           cast<LoadInst>(BasePtrMA->getAccessInstruction()));
   }
 
   MinMaxAliasGroups.emplace_back();
   MinMaxVectorPairTy &pair = MinMaxAliasGroups.back();
   MinMaxVectorTy &MinMaxAccessesReadWrite = pair.first;
   MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second;
 
   bool Valid;
 
   Valid =
       calculateMinMaxAccess(ReadWriteAccesses, *this, MinMaxAccessesReadWrite);
 
-  if (!Valid)
+  if (!Valid) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
     return false;
+  }
 
   // Bail out if the number of values we need to compare is too large.
   // This is important as the number of comparisons grows quadratically with
   // the number of values we need to compare.
   if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
-      RunTimeChecksMaxArraysPerGroup)
+      RunTimeChecksMaxArraysPerGroup) {
     return false;
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
+  }
 
   Valid =
       calculateMinMaxAccess(ReadOnlyAccesses, *this, MinMaxAccessesReadOnly);
 
-  if (!Valid)
+  if (!Valid) {
+      errs() << "@@@" << __PRETTY_FUNCTION__ << __LINE__ << "\n";
     return false;
+  }
 
   return true;
 }
 
 /// Get the smallest loop that contains @p S but is not in @p S.
 static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
   // Start with the smallest loop containing the entry and expand that
   // loop until it contains all blocks in the region. If there is a loop

 
 void Scop::foldSizeConstantsToRight() {
   isl_union_set *Accessed = isl_union_map_range(getAccesses().release());
 
   for (auto Array : arrays()) {
     if (Array->getNumberOfDimensions() <= 1)
       continue;
 
+    if (Array->hasStrides())
+      continue;
+
     isl_space *Space = Array->getSpace().release();
 
     Space = isl_space_align_params(Space, isl_union_set_get_space(Accessed));
 
     if (!isl_union_set_contains(Accessed, Space)) {
       isl_space_free(Space);
       continue;
     }

 
 void Scop::updateAccessDimensionality() {
   // Check all array accesses for each base pointer and find a (virtual) element
   // size for the base pointer that divides all access functions.
   for (ScopStmt &Stmt : *this)
     for (MemoryAccess *Access : Stmt) {
       if (!Access->isArrayKind())
         continue;
+
       ScopArrayInfo *Array =
           const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());
+      if (Array->hasStrides())
+        continue;
 
       if (Array->getNumberOfDimensions() != 1)
         continue;
       unsigned DivisibleSize = Array->getElemSizeInBytes();
       const SCEV *Subscript = Access->getSubscript(0);
       while (!isDivisible(Subscript, DivisibleSize, *SE))
         DivisibleSize /= 2;
       auto *Ty = IntegerType::get(SE->getContext(), DivisibleSize * 8);
for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
         continue;
 
       replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
     }
   }
 }
 
 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.");
   auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]
                       : ScopArrayNameMap[BaseName];
   if (!SAI) {
     auto &DL = getFunction().getParent()->getDataLayout();
-    SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
+    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()) {
+      DEBUG(dbgs() << "SAI and new shape do not agree:\n");
+      DEBUG(dbgs() << "SAI: "; SAI->print(dbgs(), true); dbgs() << "\n");
+      DEBUG(dbgs() << "Shape: " << Shape << "\n");
+
+      if (Shape.hasStrides()) {
+        DEBUG(dbgs() << "Shape has strides, SAI had size. Overwriting size "
+                        "with strides");
+        SAI->overwriteSizeWithStrides(Shape.strides(), Shape.offset(), Shape.hackFAD());
+      } else {
+        report_fatal_error(
+            "SAI has strides, Shape is size based. This should not happen");
+      }
+    }
+    if (SAI->hasStrides()) {
+      SAI->updateStrides(Shape.strides(), Shape.offset(), Shape.hackFAD());
+    } 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;

 
 isl::set Scop::getContext() const { return isl::manage(isl_set_copy(Context)); }
 isl::space Scop::getParamSpace() const { return getContext().get_space(); }
 
 isl::space Scop::getFullParamSpace() const {
   std::vector<isl::id> FortranIDs;
   FortranIDs = getFortranArrayIds(arrays());
 
+  std::vector<isl::id> StrideIDs;
+
+  for(ScopArrayInfo *Array : arrays()) {
+      if (!Array->hasStrides()) continue;
+      for(int i = 0 ; i < Array->getNumberOfDimensions(); i++) {
+          isl::id Id = Array->getDimensionSizeId(i);
+          StrideIDs.push_back(Id);
+      }
+  }
+
   isl::space Space = isl::space::params_alloc(
-      getIslCtx(), ParameterIds.size() + FortranIDs.size());
+      getIslCtx(), ParameterIds.size() + FortranIDs.size() + StrideIDs.size());
 
   unsigned PDim = 0;
   for (const SCEV *Parameter : Parameters) {
     isl::id Id = getIdForParam(Parameter);
     Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
   }
 
   for (isl::id Id : FortranIDs)
     Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
 
+  for (isl::id Id : StrideIDs) {
+    Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
+  }
+
+  /*
+  errs() << __PRETTY_FUNCTION__ << __LINE__ << " ParamSpace:\n";
+  Space.dump();
+  */
   return Space;
 }
 
 isl::set Scop::getAssumedContext() const {
   assert(AssumedContext && "Assumed context not yet built");
   return isl::manage(isl_set_copy(AssumedContext));
 }
 

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),
-      DL(DL), SE(SE), DT(DT), LI(LI), StartBlock(StartBlock) {
+    : 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)
     return;
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;
+  const std::string Name = Builder.GetInsertBlock()->getModule()->getName();
+  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());
+      }
+      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())
+          assert(false && "!NewIt offset");
+        Offset = NewIt->second;
+    } 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 = Builder.CreateIntCast(Offset, IndexOp->getType(), true);
+    }
+    assert(Offset && "dimsize uninitialized");
+    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::createOpAccess(isl_ast_expr *Expr) {
   Value *Addr = createAccessAddress(Expr);
   assert(Addr && "Could not create op access address");
-  return Builder.CreateLoad(Addr, Addr->getName() + ".load");
+  auto LoadVal = Builder.CreateLoad(Addr, Addr->getName() + ".load");
+  return LoadVal;
 }
 
 Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
   Value *LHS, *RHS, *Res;
   Type *MaxType;
   isl_ast_op_type OpType;
 
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&

lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For,
 
   Init = isl_ast_node_for_get_init(For);
   Inc = isl_ast_node_for_get_inc(For);
   Iterator = isl_ast_node_for_get_iterator(For);
   IteratorID = isl_ast_expr_get_id(Iterator);
   UB = getUpperBound(For, Predicate);
 
   ValueLB = ExprBuilder.create(Init);
+  ValueLB = getLatestValue(ValueLB);
+
   ValueUB = ExprBuilder.create(UB);
+  ValueUB = getLatestValue(ValueUB);
+
   ValueInc = ExprBuilder.create(Inc);
+  ValueInc = getLatestValue(ValueInc);
 
   MaxType = ExprBuilder.getType(Iterator);
   MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
 
   if (MaxType != ValueLB->getType())
     ValueLB = Builder.CreateSExt(ValueLB, MaxType);
for (ScopArrayInfo *Array : S.arrays()) {
     assert(FinalValue && "unable to build Fortran array "
                          "descriptor load of outermost dimension");
     IDToValue[Id] = FinalValue;
     isl_id_free(Id);
   }
   return true;
 }
 
+// given a scev of the form baseptr + offset(constant), return baseptr
+Value *getBasePtrFromConstIndexSCEV(const SCEV *S) {
+    errs() << "S:" << *S << "\n";
+    const SCEVAddExpr *Add = cast<SCEVAddExpr>(S);
+    assert(Add->getNumOperands() == 2);
+    if (isa<SCEVUnknown>(Add->getOperand(0)))
+            return cast<SCEVUnknown>(Add->getOperand(0))->getValue();
+
+    if (isa<SCEVUnknown>(Add->getOperand(1)))
+            return cast<SCEVUnknown>(Add->getOperand(1))->getValue();
+    assert(false);
+}
+
+/*
+    struct gfc_array_descriptor
+    {
+      array *data
+      index offset;
+      index dtype;
+      struct descriptor_dimension dimension[N_DIM];
+    }
+
+    struct descriptor_dimension
+    {
+      index stride;
+      index lbound;
+      index ubound;
+    }
+*/
+Value *IslNodeBuilder::extractStrideFromFAD(GlobalValue *FAD, int dimension) {
+    Type *Ity = Builder.getInt32Ty();
+    std::vector<Value *> Idxs =  { ConstantInt::get(Ity, 0), //global idx
+        ConstantInt::get(Ity, 3), // location of descriptor dim array
+        ConstantInt::get(Ity, dimension),//nth descriptor dim array,
+        ConstantInt::get(Ity, 0) // stride 
+    };
+    Value *Loc = Builder.CreateGEP(FAD, Idxs, "stride." + std::to_string(dimension) + ".loc");
+    return Builder.CreateLoad(Loc);
+}
+
+Value *IslNodeBuilder::extractOffsetFromFAD(GlobalValue *FAD) {
+    Type *Ity = Builder.getInt32Ty();
+    std::vector<Value *> Idxs = {ConstantInt::get(Ity, 0) // global idx
+        , ConstantInt::get(Ity, 1) // offset loc
+    };
+    Value *OffsetLoc = Builder.CreateGEP(FAD, Idxs, "offset.loc");
+    return Builder.CreateLoad(OffsetLoc);
+}
+
+void IslNodeBuilder::materializeStridedArraySizes() {
+    for (ScopArrayInfo *Array : S.arrays()) {
+        if (!Array->hasStrides())
+            continue;
+
+        GlobalValue *FAD = nullptr;
+
+        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");
+
+            DEBUG(
+            dbgs() << "-\n";
+            dbgs() << "i: " << i << "\n";
+            dbgs() << "ID: " <<Id << "\n";);
+            const SCEV *StrideSCEV = Array->getDimensionStride(i);
+            // dbgs() << "StrideSCEV: " << *StrideSCEV << "\n";
+
+            Value *Stride = nullptr;
+            if (FAD) {
+                assert(false);
+                // We need to pass a SCEV to the IslExprBuilder for
+                // kernel strides. We can't synthesize a value because it would be
+                // different across host and kernel code.
+                Stride = extractStrideFromFAD(FAD, Array->getNumberOfDimensions() - 1 -i);
+            }
+            else {
+                // assert(isa<SCEVConstant>(StrideSCEV));
+                Stride = generateSCEV(StrideSCEV);
+            }
+            assert(Stride);
+
+            // errs() << "StrideVal: " << *Stride << "\n";
+            IDToValue[Id] = Stride;
+            SCEVToValue[Array->getDimensionStride(i)] = Stride;
+            isl_id_free(Id);
+        }
+
+        Value *Offset = nullptr;
+        const SCEV *OffsetSCEV = Array->getStrideOffset();
+        if (FAD) {
+            assert(false);
+            Offset = extractOffsetFromFAD(FAD);
+        } else {
+            // assert(isa<SCEVConstant>(OffsetSCEV));
+            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);
   auto *AddressValue = ExprBuilder.create(Address);
if (auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr())) {
     // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
     // we need to refine the ExecutionCtx.
     isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
     ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
   }
 
   // If the size of a dimension is dependent on another class, make sure it is
   // preloaded.
-  for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
-    const SCEV *Dim = SAI->getDimensionSize(i);
+  auto PreloadSCEV = [&](const SCEV *ToPreload) {
     SetVector<Value *> Values;
-    findValues(Dim, SE, Values);
+    findValues(ToPreload, SE, Values);
     for (auto *Val : Values) {
       if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {
         if (!preloadInvariantEquivClass(*BaseIAClass))
           return false;
 
         // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx
         // and we need to refine the ExecutionCtx.
         isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
         ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
       }
     }
+    return true;
+  };
+
+  if (SAI->hasStrides()) {
+    if (!PreloadSCEV(SAI->getStrideOffset()))
+      return false;
+    for (unsigned i = 0, e = SAI->getNumberOfDimensions(); i < e; ++i) {
+      if (!PreloadSCEV(SAI->getDimensionStride(i)))
+        return false;
+    }
+  } else {
+    for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
+      if (!PreloadSCEV(SAI->getDimensionSize(i)))
+        return false;
+    }
   }
 
   Instruction *AccInst = MA->getAccessInstruction();
   Type *AccInstTy = AccInst->getType();
 
   Value *PreloadVal = preloadInvariantLoad(*MA, isl_set_copy(ExecutionCtx));
   if (!PreloadVal)
     return false;
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();
 
+  materializeStridedArraySizes();
+
   // 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());
 

lib/CodeGen/PPCGCodeGeneration.cpp

 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/Linker/Linker.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
+#include "polly/Support/ISLOStream.h"
 #include "isl/union_map.h"
 
 extern "C" {
 #include "ppcg/cuda.h"
 #include "ppcg/gpu.h"
 #include "ppcg/gpu_print.h"
 #include "ppcg/ppcg.h"
 #include "ppcg/schedule.h"
private:
   ///
   ///   for (long i = 0; i < 100; i++)
   ///     A[i + 42] += ...
   ///
   ///   getArrayOffset(A) results in 42.
   ///
   /// @param Array The array for which to compute the offset.
   /// @returns An llvm::Value that contains the offset of the array.
-  Value *getArrayOffset(gpu_array_info *Array);
+  Value *getArrayOffset(const ScopArrayInfo *SAI, gpu_array_info *Array);
 
   /// Prepare the kernel arguments for kernel code generation
   ///
   /// @param Kernel The kernel to generate code for.
   /// @param FN     The function created for the kernel.
   void prepareKernelArguments(ppcg_kernel *Kernel, Function *FN);
 
   /// Create kernel function.
void GPUNodeBuilder::allocateDeviceArrays() {
 
   for (int i = 0; i < Prog->n_array; ++i) {
     gpu_array_info *Array = &Prog->array[i];
     auto *ScopArray = (ScopArrayInfo *)Array->user;
     std::string DevArrayName("p_dev_array_");
     DevArrayName.append(Array->name);
 
     Value *ArraySize = getArraySize(Array);
-    Value *Offset = getArrayOffset(Array);
+    Value *Offset = getArrayOffset(ScopArray, Array);
     if (Offset)
       ArraySize = Builder.CreateSub(
           ArraySize,
           Builder.CreateMul(Offset,
                             Builder.getInt64(ScopArray->getElemSizeInBytes())));
     const SCEV *SizeSCEV = SE.getSCEV(ArraySize);
     // It makes no sense to have an array of size 0. The CUDA API will
     // throw an error anyway if we invoke `cuMallocManaged` with size `0`. We
     // choose to be defensive and catch this at the compile phase. It is
     // most likely that we are doing something wrong with size computation.
     if (SizeSCEV->isZero()) {
-      errs() << getUniqueScopName(&S)
-             << " has computed array size 0: " << *ArraySize
-             << " | for array: " << *(ScopArray->getBasePtr())
-             << ". This is illegal, exiting.\n";
+      errs() << getUniqueScopName(&S) << " has array size 0.\n "
+             << "Array with size 0: " << *(ScopArray->getBasePtr())
+             << "Size expression: " << *ArraySize
+             << "\nThis is illegal, exiting.\n";
       report_fatal_error("array size was computed to be 0");
     }
 
     Value *DevArray = createCallAllocateMemoryForDevice(ArraySize);
     DevArray->setName(DevArrayName);
     DeviceAllocations[ScopArray] = DevArray;
   }
 
for (int i = 0; i < Prog->n_array; ++i) {
     Value *HostPtr;
 
     if (gpu_array_is_scalar(Array))
       HostPtr = BlockGen.getOrCreateAlloca(ScopArray);
     else
       HostPtr = ScopArray->getBasePtr();
     HostPtr = getLatestValue(HostPtr);
 
-    Value *Offset = getArrayOffset(Array);
+    /*
+    Value *Offset = getArrayOffset(ScopArray, Array);
     if (Offset) {
       HostPtr = Builder.CreatePointerCast(
           HostPtr, ScopArray->getElementType()->getPointerTo());
       HostPtr = Builder.CreateGEP(HostPtr, Offset);
     }
 
     HostPtr = Builder.CreatePointerCast(HostPtr, Builder.getInt8PtrTy());
+    */
     DeviceAllocations[ScopArray] = HostPtr;
   }
 }
 
 void GPUNodeBuilder::addCUDAAnnotations(Module *M, Value *BlockDimX,
                                         Value *BlockDimY, Value *BlockDimZ) {
   auto AnnotationNode = M->getOrInsertNamedMetadata("nvvm.annotations");
 
Value *GPUNodeBuilder::createCallInitContext() {
   const char *Name;
 
   switch (Runtime) {
   case GPURuntime::CUDA:
     Name = "polly_initContextCUDA";
     break;
   case GPURuntime::OpenCL:
     Name = "polly_initContextCL";
+
     break;
   }
 
   Module *M = Builder.GetInsertBlock()->getParent()->getParent();
   Function *F = M->getFunction(Name);
 
   // If F is not available, declare it.
   if (!F) {
if (!gpu_array_is_scalar(Array)) {
     Value *NumElements = ExprBuilder.create(Res.release());
     if (NumElements->getType() != ArraySize->getType())
       NumElements = Builder.CreateSExt(NumElements, ArraySize->getType());
     ArraySize = Builder.CreateMul(ArraySize, NumElements);
   }
   return ArraySize;
 }
 
-Value *GPUNodeBuilder::getArrayOffset(gpu_array_info *Array) {
+Value *GPUNodeBuilder::getArrayOffset(const ScopArrayInfo *SAI,
+                                      gpu_array_info *Array) {
   if (gpu_array_is_scalar(Array))
     return nullptr;
 
+  if (SAI->hasStrides()) {
+      return nullptr;
+    // return generateSCEV(SAI->getStrideOffset());
+  }
+
   isl::ast_build Build = isl::ast_build::from_context(S.getContext());
 
   isl::set Min = isl::manage(isl_set_copy(Array->extent)).lexmin();
 
   isl::set ZeroSet = isl::set::universe(Min.get_space());
 
   for (long i = 0, n = Min.dim(isl::dim::set); i < n; i++)
     ZeroSet = ZeroSet.fix_si(isl::dim::set, i, 0);
void GPUNodeBuilder::createDataTransfer(__isl_take isl_ast_node *TransferStmt,
   assert(!PollyManagedMemory && "Managed memory needs no data transfers");
   isl_ast_expr *Expr = isl_ast_node_user_get_expr(TransferStmt);
   isl_ast_expr *Arg = isl_ast_expr_get_op_arg(Expr, 0);
   isl_id *Id = isl_ast_expr_get_id(Arg);
   auto Array = (gpu_array_info *)isl_id_get_user(Id);
   auto ScopArray = (ScopArrayInfo *)(Array->user);
 
   Value *Size = getArraySize(Array);
-  Value *Offset = getArrayOffset(Array);
+  Value *Offset = getArrayOffset(ScopArray, Array);
   Value *DevPtr = DeviceAllocations[ScopArray];
 
   Value *HostPtr;
 
   if (gpu_array_is_scalar(Array))
     HostPtr = BlockGen.getOrCreateAlloca(ScopArray);
   else
     HostPtr = ScopArray->getBasePtr();
static bool isValidFunctionInKernel(llvm::Function *F, bool AllowLibDevice) {
   // We string compare against the name of the function to allow
   // all variants of the intrinsic "llvm.sqrt.*", "llvm.fabs", and
   // "llvm.copysign".
   const StringRef Name = F->getName();
 
   if (AllowLibDevice && getCUDALibDeviceFuntion(F).length() > 0)
     return true;
 
+  if (Name.count("polly_array_index"))
+    return true;
+
   return F->isIntrinsic() &&
          (Name.startswith("llvm.sqrt") || Name.startswith("llvm.fabs") ||
           Name.startswith("llvm.copysign"));
 }
 
 /// Do not take `Function` as a subtree value.
 ///
 /// We try to take the reference of all subtree values and pass them along
GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   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);
 
+  for (const auto &I : SCEVToValue)
+    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());
 
   isl_ast_node_foreach_descendant_top_down(
       Kernel->tree, collectReferencesInGPUStmt, &References);
 
for (long i = 0; i < Prog->n_array; i++) {
     Value *DevArray = nullptr;
     if (PollyManagedMemory) {
       DevArray = getManagedDeviceArray(&Prog->array[i],
                                        const_cast<ScopArrayInfo *>(SAI));
     } else {
       DevArray = DeviceAllocations[const_cast<ScopArrayInfo *>(SAI)];
       DevArray = createCallGetDevicePtr(DevArray);
     }
-    assert(DevArray != nullptr && "Array to be offloaded to device not "
-                                  "initialized");
-    Value *Offset = getArrayOffset(&Prog->array[i]);
+
+    Value *Offset = getArrayOffset(SAI, &Prog->array[i]);
 
     if (Offset) {
       DevArray = Builder.CreatePointerCast(
           DevArray, SAI->getElementType()->getPointerTo());
+
+      // NO NEGATION FOR STRIDES ARRAY.
+      if (SAI->hasStrides())
+        DevArray = Builder.CreateGEP(DevArray, Offset);
+      else
         DevArray = Builder.CreateGEP(DevArray, Builder.CreateNeg(Offset));
       DevArray = Builder.CreatePointerCast(DevArray, Builder.getInt8PtrTy());
     }
+    assert(DevArray != nullptr && "Array to be offloaded to device not "
+                                  "initialized");
     Value *Slot = Builder.CreateGEP(
         Parameters, {Builder.getInt64(0), Builder.getInt64(Index)});
 
     if (gpu_array_is_read_only_scalar(&Prog->array[i])) {
       Value *ValPtr = nullptr;
       if (PollyManagedMemory)
         ValPtr = DevArray;
       else
         ValPtr = BlockGen.getOrCreateAlloca(SAI);
 
       assert(ValPtr != nullptr && "ValPtr that should point to a valid object"
                                   " to be stored into Parameters");
       Value *ValPtrCast =
           Builder.CreatePointerCast(ValPtr, Builder.getInt8PtrTy());
       Builder.CreateStore(ValPtrCast, Slot);
     } else {
       Instruction *Param =
           new AllocaInst(Builder.getInt8PtrTy(), AddressSpace,
                          Launch + "_param_" + std::to_string(Index),
                          EntryBlock->getTerminator());
-      Builder.CreateStore(DevArray, Param);
+      Value *DevArrayCast =
+          Builder.CreatePointerCast(DevArray, Builder.getInt8PtrTy());
+      Builder.CreateStore(DevArrayCast, Param);
       Value *ParamTyped =
           Builder.CreatePointerCast(Param, Builder.getInt8PtrTy());
       Builder.CreateStore(ParamTyped, Slot);
     }
     Index++;
   }
 
   int NumHostIters = isl_space_dim(Kernel->space, isl_dim_set);
void GPUNodeBuilder::setupKernelSubtreeFunctions(
     SetVector<Function *> SubtreeFunctions) {
   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());
+
+    // For our polly_array_index function, we need readnone attribute so that
+    // dead code elimination nukes it. In general, it is good practice
+    // to copy over attributes.
+    Clone->setAttributes(Fn->getAttributes());
+
     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);
for (long i = 0; i < Kernel->n_array; i++) {
     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(isl_id_copy(Id)));
     Type *EleTy = SAI->getElementType();
     Value *Val = &*Arg;
     SmallVector<const SCEV *, 4> Sizes;
+    ShapeInfo NewShape = ShapeInfo::none();
     isl_ast_build *Build =
         isl_ast_build_from_context(isl_set_copy(Prog->context));
+
+    if (SAI->hasStrides()) {
+      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));
+      }
+      NewShape = SAI->getShape();
+      // NewShape = ShapeInfo::fromStrides(Sizes, SAI->getStrideOffset());
+    } 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));
       }
+      NewShape = ShapeInfo::fromSizes(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++;
   }
 
void GPUNodeBuilder::finalizeKernelArguments(ppcg_kernel *Kernel) {
   }
 
   if (StoredScalar) {
     /// In case more than one thread contains scalar stores, the generated
     /// code might be incorrect, if we only store at the end of the kernel.
     /// To support this case we need to store these scalars back at each
     /// memory store or at least before each kernel barrier.
     if (Kernel->n_block != 0 || Kernel->n_grid != 0) {
-      BuildSuccessful = 0;
-      DEBUG(
-          dbgs() << getUniqueScopName(&S)
-                 << " has a store to a scalar value that"
-                    " would be undefined to run in parallel. Bailing out.\n";);
+      // BuildSuccessful = 0;
+      DEBUG(dbgs() << __PRETTY_FUNCTION__ << "HACK: disabling bailout on StoredScalar\n";);
+      //DEBUG(
+      //    dbgs() << getUniqueScopName(&S)
+      //           << " has a store to a scalar value that"
+      //              " would be undefined to run in parallel. Bailing out.\n";);
     }
   }
 }
 
 void GPUNodeBuilder::createKernelVariables(ppcg_kernel *Kernel, Function *FN) {
   Module *M = Builder.GetInsertBlock()->getParent()->getParent();
 
   for (int i = 0; i < Kernel->n_var; ++i) {
     struct ppcg_kernel_var &Var = Kernel->var[i];
     isl_id *Id = isl_space_get_tuple_id(Var.array->space, isl_dim_set);
+    const ScopArrayInfo *OriginalSAI =
+        ScopArrayInfo::getFromId(isl::manage(isl_id_copy(Id)));
+    assert(OriginalSAI);
+
     Type *EleTy = ScopArrayInfo::getFromId(isl::manage(Id))->getElementType();
 
     Type *ArrayTy = EleTy;
-    SmallVector<const SCEV *, 4> Sizes;
+    ShapeInfo NewShape = ShapeInfo::none();
+    if (OriginalSAI->hasStrides()) {
+      SmallVector<const SCEV *, 4> Strides;
+      for (unsigned int j = 0; j < Var.array->n_index; ++j) {
+        isl_val *Val = isl_vec_get_element_val(Var.size, j);
+        long Bound = isl_val_get_num_si(Val);
+        isl_val_free(Val);
+        Strides.push_back(S.getSE()->getConstant(Builder.getInt64Ty(), Bound));
+      }
 
+      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);
+      }
+
+      NewShape = OriginalSAI->getShape();
+      // NewShape =
+      //     ShapeInfo::fromStrides(Strides, OriginalSAI->getStrideOffset());
+    } else {
+      SmallVector<const SCEV *, 4> Sizes;
       Sizes.push_back(nullptr);
       for (unsigned int j = 1; j < Var.array->n_index; ++j) {
         isl_val *Val = isl_vec_get_element_val(Var.size, j);
         long Bound = isl_val_get_num_si(Val);
         isl_val_free(Val);
         Sizes.push_back(S.getSE()->getConstant(Builder.getInt64Ty(), Bound));
       }
 
+      // ASK TOBIAS: what is going on here?
       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);
       }
+      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(), Var.name, nullptr);
     IDToValue[Id] = Allocation;
     LocalArrays.push_back(Allocation);
     KernelIds.push_back(Id);
     IDToSAI[Id] = SAI;
   }
 }
 
if (requiresCUDALibDevice()) {
     // Set an nvptx64 target triple to avoid linker warnings. The original
     // triple of the libdevice files are nvptx-unknown-unknown.
     LibDeviceModule->setTargetTriple(Triple::normalize("nvptx64-nvidia-cuda"));
     L.linkInModule(std::move(LibDeviceModule), Linker::LinkOnlyNeeded);
   }
 }
 
 std::string GPUNodeBuilder::finalizeKernelFunction() {
+  {
+    // NOTE: We currently copy all uses of gfortran_polly_array_index.
+    // However, these are unsused, but they refer to host side values
+    // So, ADCE them out.
+    // For correctness, we should probably add these to
+    // BlockGenerators.cpp - polly::isIgnoredIntrinsic.
+    llvm::legacy::PassManager OptPasses;
+    OptPasses.add(createAggressiveDCEPass());
+    // Comment this to allow tests to pass:
+    // Polly :: GPGPU/host-control-flow.ll
+    // Polly :: GPGPU/kernel-params-only-some-arrays.ll
+    // Polly :: GPGPU/live-range-reordering-with-privatization.ll
+    // Polly :: GPGPU/phi-nodes-in-kernel.ll
+    OptPasses.run(*GPUModule);
+  }
 
   if (verifyModule(*GPUModule)) {
     DEBUG(dbgs() << "verifyModule failed on module:\n";
           GPUModule->print(dbgs(), nullptr); dbgs() << "\n";);
     DEBUG(dbgs() << "verifyModule Error:\n";
           verifyModule(*GPUModule, &dbgs()););
 
     if (FailOnVerifyModuleFailure)
isl::set getExtent(ScopArrayInfo *Array) {
     isl::set Extent = isl::set::universe(Array->getSpace());
 
     Extent = Extent.intersect(OuterMin.le_set(Val));
     Extent = Extent.intersect(OuterMax.ge_set(Val));
 
     for (unsigned i = 1; i < NumDims; ++i)
       Extent = Extent.lower_bound_si(isl::dim::set, i, 0);
 
+    if (!Array->hasStrides()) {
       for (unsigned i = 0; i < NumDims; ++i) {
         isl::pw_aff PwAff = Array->getDimensionSizePw(i);
 
         // isl_pw_aff can be NULL for zero dimension. Only in the case of a
         // Fortran array will we have a legitimate dimension.
         if (PwAff.is_null()) {
-        assert(i == 0 && "invalid dimension isl_pw_aff for nonzero dimension");
+          assert(i == 0 &&
+                 "invalid dimension isl_pw_aff for nonzero dimension");
           continue;
         }
 
         isl::pw_aff Val = isl::aff::var_on_domain(
             isl::local_space(Array->getSpace()), isl::dim::set, i);
         PwAff = PwAff.add_dims(isl::dim::in, Val.dim(isl::dim::in));
-      PwAff = PwAff.set_tuple_id(isl::dim::in, Val.get_tuple_id(isl::dim::in));
+        PwAff =
+            PwAff.set_tuple_id(isl::dim::in, Val.get_tuple_id(isl::dim::in));
         isl::set Set = PwAff.gt_set(Val);
         Extent = Set.intersect(Extent);
       }
+    }
 
     return Extent;
   }
 
   /// Derive the bounds of an array.
   ///
   /// For the first dimension we derive the bound of the array from the extent
   /// of this dimension. For inner dimensions we obtain their size directly from
   /// ScopArrayInfo.
   ///
   /// @param PPCGArray The array to compute bounds for.
   /// @param Array The polly array from which to take the information.
   void setArrayBounds(gpu_array_info &PPCGArray, ScopArrayInfo *Array) {
     std::vector<isl_pw_aff *> Bounds;
 
+    if (!Array->hasStrides()) {
       if (PPCGArray.n_index > 0) {
         if (isl_set_is_empty(PPCGArray.extent)) {
           isl_set *Dom = isl_set_copy(PPCGArray.extent);
           isl_local_space *LS = isl_local_space_from_space(
               isl_space_params(isl_set_get_space(Dom)));
           isl_set_free(Dom);
           isl_pw_aff *Zero = isl_pw_aff_from_aff(isl_aff_zero_on_domain(LS));
           Bounds.push_back(Zero);
         } else {
           isl_set *Dom = isl_set_copy(PPCGArray.extent);
           Dom = isl_set_project_out(Dom, isl_dim_set, 1, PPCGArray.n_index - 1);
           isl_pw_aff *Bound = isl_set_dim_max(isl_set_copy(Dom), 0);
           isl_set_free(Dom);
           Dom = isl_pw_aff_domain(isl_pw_aff_copy(Bound));
           isl_local_space *LS =
               isl_local_space_from_space(isl_set_get_space(Dom));
           isl_aff *One = isl_aff_zero_on_domain(LS);
           One = isl_aff_add_constant_si(One, 1);
           Bound = isl_pw_aff_add(Bound, isl_pw_aff_alloc(Dom, One));
           Bound = isl_pw_aff_gist(Bound, S->getContext().release());
           Bounds.push_back(Bound);
         }
       }
+    }
 
-    for (unsigned i = 1; i < PPCGArray.n_index; ++i) {
+    const int BeginIndex = Array->hasStrides() ? 0 : 1;
+    for (unsigned i = BeginIndex; i < PPCGArray.n_index; ++i) {
       isl_pw_aff *Bound = Array->getDimensionSizePw(i).release();
       auto LS = isl_pw_aff_get_domain_space(Bound);
       auto Aff = isl_multi_aff_zero(LS);
+
+      // We need types to work out, which is why we perform this weird dance
+      // with `Aff` and `Bound`. Consider this example:
+
+      // LS: [p] -> { [] }
+      // Zero: [p] -> { [] } | Implicitly, is [p] -> { ~ -> [] }.
+      // This `~` is used to denote a "null space" (which is different from
+      // a *zero dimensional* space), which is something that ISL does not
+      // show you when pretty printing.
+
+      // Bound: [p] -> { [] -> [(10p)] } | Here, the [] is a *zero
+      // dimensional* space, not a "null space" which does not exist at all.
+
+      // When we pullback (precompose) `Bound` with `Zero`, we get:
+      // Bound . Zero =
+      //     ([p] -> { [] -> [(10p)] }) . ([p] -> {~ -> [] }) =
+      //     [p] -> { ~ -> [(10p)] } =
+      //     [p] -> [(10p)] (as ISL pretty prints it)
+      // Bound Pullback: [p] -> { [(10p)] }
+
+      // We want this kind of an expression for Bound, without a
+      // zero dimensional input, but with a "null space" input for the types
+      // to work out later on, as far as I (Siddharth Bhat) understand.
+      // I was unable to find a reference to this in the ISL manual.
+      // References: Tobias Grosser.
+
       Bound = isl_pw_aff_pullback_multi_aff(Bound, Aff);
       Bounds.push_back(Bound);
     }
 
     /// To construct a `isl_multi_pw_aff`, we need all the indivisual `pw_aff`
     /// to have the same parameter dimensions. So, we need to align them to an
     /// appropriate space.
     /// Scop::Context is _not_ an appropriate space, because when we have
     /// `-polly-ignore-parameter-bounds` enabled, the Scop::Context does not
     /// contain all parameter dimensions.
     /// So, use the helper `alignPwAffs` to align all the `isl_pw_aff` together.
-    isl_space *SeedAlignSpace = S->getParamSpace().release();
+    isl_space *SeedAlignSpace = S->getFullParamSpace().release();
     SeedAlignSpace = isl_space_add_dims(SeedAlignSpace, isl_dim_set, 1);
+    SeedAlignSpace = isl_space_align_params(
+        SeedAlignSpace, isl_set_get_space(PPCGArray.extent));
 
     isl_space *AlignSpace = nullptr;
     std::vector<isl_pw_aff *> AlignedBounds;
     std::tie(AlignSpace, AlignedBounds) =
         alignPwAffs(std::move(Bounds), SeedAlignSpace);
 
     assert(AlignSpace && "alignPwAffs did not initialise AlignSpace");
 
gpu_gen *generateGPU(ppcg_scop *PPCGScop, gpu_prog *PPCGProg) {
     isl_options_set_schedule_whole_component(PPCGGen->ctx, false);
 
     isl_schedule *Schedule = get_schedule(PPCGGen);
 
     int has_permutable = has_any_permutable_node(Schedule);
 
     Schedule =
         isl_schedule_align_params(Schedule, S->getFullParamSpace().release());
+    // errs() << S->getFullParamSpace() << "\n";
+    // report_fatal_error("see full param space");
 
     if (!has_permutable || has_permutable < 0) {
       Schedule = isl_schedule_free(Schedule);
       DEBUG(dbgs() << getUniqueScopName(S)
                    << " does not have permutable bands. Bailing out\n";);
     } else {
       const bool CreateTransferToFromDevice = !PollyManagedMemory;
       Schedule = map_to_device(PPCGGen, Schedule, CreateTransferToFromDevice);

lib/External/isl/isl_map.c

static isl_stat check_basic_map_compatible_range_multi_aff(
   __isl_keep isl_basic_map *bmap, enum isl_dim_type type,
   __isl_keep isl_multi_aff *ma)
 {
   isl_bool m;
   isl_space *ma_space;
 
   ma_space = isl_multi_aff_get_space(ma);
 
+    /*
+    isl_printer *PRINTER = isl_printer_to_str(isl_basic_map_get_ctx(bmap));
+    isl_printer_print_basic_map(PRINTER, bmap);
+    fprintf(stderr, "PRINTER%s%d:\n%s\n", __PRETTY_FUNCTION__, __LINE__, isl_printer_get_str(PRINTER));
+    PRINTER = isl_printer_flush(PRINTER);
+
+    isl_printer_print_multi_aff(PRINTER, ma);
+    fprintf(stderr, "PRINTER%s%d:\n%s\n", __PRETTY_FUNCTION__, __LINE__, isl_printer_get_str(PRINTER));
+    PRINTER = isl_printer_flush(PRINTER);
+    */
+
   m = isl_space_has_equal_params(bmap->dim, ma_space);
   if (m < 0)
     goto error;
-  if (!m)
+  if (!m) {
     isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
       "parameters don't match", goto error);
+    }
   m = isl_space_tuple_is_equal(bmap->dim, type, ma_space, isl_dim_out);
   if (m < 0)
     goto error;
   if (!m)
     isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
       "spaces don't match", goto error);
 
   isl_space_free(ma_space);

lib/Support/ScopHelper.cpp

 }
 
 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
                                            llvm::LoopInfo &LI,
                                            const BoxedLoopsSetTy &BoxedLoops) {
   Loop *L = LI.getLoopFor(BB);
   return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
 }
+
+static const bool AbstractMatrixDebug = false;
+llvm::Optional<std::pair<CallInst *, GEPOperator *>>
+polly::getAbstractMatrixCall(MemAccInst Inst, ScalarEvolution &SE) {
+  // 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
+
+  if (AbstractMatrixDebug) {
+    errs() << "@@@" << __PRETTY_FUNCTION__ << "\n";
+    errs() << "\nInst: " << *Inst.get() << "\n";
+  }
+
+  Value *MaybeBitcast = Inst.getPointerOperand();
+  if (!MaybeBitcast)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  if (AbstractMatrixDebug)
+    errs() << "Bitcast(maybe): " << *MaybeBitcast << "\n";
+
+  // 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();
+  }();
+
+  if (AbstractMatrixDebug)
+    errs() << "\tGEP(maybe): " << *MaybeGEP << "\n";
+
+  GEPOperator *GEP = dyn_cast<GEPOperator>(MaybeGEP);
+
+  if (!GEP)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+
+  if (AbstractMatrixDebug)
+    errs() << "\tGEP(for sure): " << *GEP << "\n";
+
+  auto *MaybeCall = GEP->getOperand(GEP->getNumOperands() - 1);
+  assert(MaybeCall);
+  if (AbstractMatrixDebug)
+    errs() << "\tCall(maybe): " << *MaybeCall << "\n";
+
+  CallInst *Call = dyn_cast<CallInst>(MaybeCall);
+  if (!Call)
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+  if (AbstractMatrixDebug)
+    errs() << "\tCall(for sure): " << *Call << "\n";
+
+  if (!Call->getCalledFunction()->getName().count(
+          POLLY_ABSTRACT_INDEX_BASENAME))
+    return Optional<std::pair<CallInst *, GEPOperator *>>(None);
+  if (AbstractMatrixDebug)
+    errs() << "Called name: " << Call->getCalledFunction()->getName() << "\n";
+
+  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/GPGPU/09-12-failing-testcase-array-inv-load-hoist.ll

+; RUN: opt %loadPolly \
+; RUN: -polly-invariant-load-hoisting \
+; RUN: -polly-detect-fortran-arrays \
+; RUN: -polly-codegen-ppcg \
+; RUN: -polly-acc-codegen-managed-memory \
+; RUN: -polly-acc-fail-on-verify-module-failure \
+; RUN: -debug-only=polly-codegen-ppcg,polly-scops \
+; RUN: -S \
+; RUN: -pass-remarks=polly
+
+; CHECK: foo
+; CONTAINS
+;     SUBROUTINE f(arr, bloop, eloop, barr, earr, arrinp, arrinp2)
+;         INTEGER, INTENT(IN) :: &
+;             bloop, eloop, barr, earr
+;         REAL, INTENT(IN) :: &
+;             ! arrinp(barr:earr, ki3sd:ki3ed), &
+;             arrinp(barr:earr, barr:earr), &
+;             arrinp2(barr:earr, barr:earr)
+;         REAL, INTENT(INOUT) :: &
+;             arr(barr:earr)
+;         INTEGER :: &
+;             i, i3
+;         REAL :: &
+;             coeff
+;
+;         DO i=bloop, eloop
+;               arr(i) = arrinp(0, 0) + arrinp2(i, 0)
+;         END DO
+;     END SUBROUTINE f
+; END MODULE m
+
+; ModuleID = 'm.ll'
+source_filename = "m.bc"
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+; Function Attrs: nounwind uwtable
+define void @__m_MOD_f([0 x float]* noalias %arr, i32* noalias %bloop, i32* noalias %eloop, i32* noalias %barr, i32* noalias %earr, [0 x float]* noalias %arrinp, [0 x float]* noalias %arrinp2) unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %0 = load i32, i32* %barr, align 4
+  %1 = sext i32 %0 to i64
+  %2 = load i32, i32* %earr, align 4
+  %3 = sext i32 %2 to i64
+  %4 = sub nsw i64 1, %1
+  %5 = add nsw i64 %4, %3
+  %6 = icmp sgt i64 %5, 0
+  %7 = select i1 %6, i64 %5, i64 0
+  %8 = sub nsw i64 0, %1
+  %9 = mul i64 %7, %1
+  %10 = sub i64 %8, %9
+  %11 = load i32, i32* %bloop, align 4
+  %12 = load i32, i32* %eloop, align 4
+  %13 = icmp sgt i32 %11, %12
+  br i1 %13, label %return, label %"3.preheader"
+
+"3.preheader":                                    ; preds = %entry.split
+  br label %"3"
+
+"3":                                              ; preds = %"3", %"3.preheader"
+  %14 = phi i32 [ %26, %"3" ], [ %11, %"3.preheader" ]
+  %15 = sext i32 %14 to i64
+  %16 = tail call i64 @_gfortran_polly_array_index_1(i64 %8, i64 1, i64 %15) #1
+  %17 = tail call i64 @_gfortran_polly_array_index_2(i64 %10, i64 %7, i64 1, i64 0, i64 0) #1
+  %18 = getelementptr [0 x float], [0 x float]* %arrinp, i64 0, i64 %17
+  %19 = load float, float* %18, align 4
+  %20 = tail call i64 @_gfortran_polly_array_index_2(i64 %10, i64 %7, i64 1, i64 0, i64 %15) #1
+  %21 = getelementptr [0 x float], [0 x float]* %arrinp2, i64 0, i64 %20
+  %22 = load float, float* %21, align 4
+  %23 = fadd float %19, %22
+  %24 = getelementptr [0 x float], [0 x float]* %arr, i64 0, i64 %16
+  store float %23, float* %24, align 4
+  %25 = icmp eq i32 %14, %12
+  %26 = add i32 %14, 1
+  br i1 %25, label %return.loopexit, label %"3"
+
+return.loopexit:                                  ; preds = %"3"
+  br label %return
+
+return:                                           ; preds = %return.loopexit, %entry.split
+  ret void
+}
+
+declare i64 @_gfortran_polly_array_index_1(i64, i64, i64) #2
+
+declare i64 @_gfortran_polly_array_index_2(i64, i64, i64, i64, i64) #2
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { readnone }

test/GPGPU/09-13-coe-th-referring-to-arg-in-another-fn.ll

+; RUN: opt %loadPolly \
+; RUN: -polly-invariant-load-hoisting \
+; RUN: -polly-detect-fortran-arrays \
+; RUN: -polly-codegen-ppcg \
+; RUN: -polly-acc-codegen-managed-memory \
+; RUN: -polly-acc-fail-on-verify-module-failure \
+; RUN: -debug-only=polly-codegen-ppcg,polly-scops \
+; RUN: -S \
+; RUN: -pass-remarks=polly \
+; RUN: < %s
+
+; MODULE m
+; IMPLICIT NONE
+;
+; CONTAINS
+;     SUBROUTINE f(arr, arr_input, bloop, eloop)
+;         INTEGER, INTENT(IN) :: &
+;             bloop, eloop
+;         REAL, INTENT(IN) :: &
+;             arr_input(bloop:eloop)
+;         REAL, INTENT(INOUT) :: &
+;             arr(bloop:eloop)
+;         INTEGER :: &
+;             i
+;         REAL :: &
+;             cmp_val, final_val
+;
+;         DO i=bloop, eloop
+;             cmp_val = arr_input(i)
+;             IF (cmp_val .LT. 42) THEN
+;                 final_val = EXP (cmp_val)
+;             ELSE
+;                 final_val = 100
+;             END IF
+;
+;             arr(i)=final_val
+;         END DO
+;     END SUBROUTINE f
+; END MODULE m;
+
+; Error:
+;     verifyModule Error:
+;     Referring to an argument in another function!
+;       %p_1 = getelementptr [0 x float], [0 x float]* %arr_input, i64 0, i64 %p_
+;     VerifyModule failed.
+
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+; Function Attrs: nounwind uwtable
+define void @__m_MOD_f([0 x float]* noalias %arr, [0 x float]* noalias %arr_input, i32* noalias %bloop, i32* noalias %eloop) unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %0 = load i32, i32* %bloop, align 4
+  %1 = sext i32 %0 to i64
+  %2 = load i32, i32* %eloop, align 4
+  %3 = sub nsw i64 0, %1
+  %4 = icmp sgt i32 %0, %2
+  br i1 %4, label %return, label %"3.preheader"
+
+"3.preheader":                                    ; preds = %entry.split
+  br label %"3"
+
+"3":                                              ; preds = %"6", %"3.preheader"
+  %5 = phi i32 [ %16, %"6" ], [ %0, %"3.preheader" ]
+  %6 = sext i32 %5 to i64
+  %7 = tail call i64 @_gfortran_polly_array_index_1(i64 %3, i64 1, i64 %6) #2
+  %8 = getelementptr [0 x float], [0 x float]* %arr_input, i64 0, i64 %7
+  %9 = load float, float* %8, align 4
+  %10 = fcmp olt float %9, 4.2e+02
+  br i1 %10, label %"4", label %"6"
+
+"4":                                              ; preds = %"3"
+  %11 = tail call float @expf(float %9) #1
+  br label %"6"
+
+"6":                                              ; preds = %"3", %"4"
+  %12 = phi float [ %11, %"4" ], [ 1.000000e+02, %"3" ]
+  %13 = tail call i64 @_gfortran_polly_array_index_1(i64 %3, i64 1, i64 %6) #2
+  %14 = getelementptr [0 x float], [0 x float]* %arr, i64 0, i64 %13
+  store float %12, float* %14, align 4
+  %15 = icmp eq i32 %5, %2
+  %16 = add i32 %5, 1
+  br i1 %15, label %return.loopexit, label %"3"
+
+return.loopexit:                                  ; preds = %"6"
+  br label %return
+
+return:                                           ; preds = %return.loopexit, %entry.split
+  ret void
+}
+
+declare i64 @_gfortran_polly_array_index_1(i64, i64, i64) #2
+
+; Function Attrs: nounwind readnone
+declare float @expf(float) #1
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind readnone }
+attributes #2 = { nounwind }
+attributes #2 = { readnone }

test/GPGPU/09-13-unbounded-optimium.ll

+; MODULE m
+; IMPLICIT NONE
+;
+; CONTAINS
+;     SUBROUTINE f(arr, bloop, eloop, arrinp)
+;         INTEGER, INTENT(IN) :: &
+;             bloop, eloop
+;         REAL, INTENT(IN) :: &
+;             arrinp(bloop:eloop)
+;         REAL, INTENT(INOUT) :: &
+;             arr(bloop:eloop)
+;         INTEGER :: &
+;             i
+;
+;         DO i=bloop, eloop
+;               arr(i) = arrinp(i)
+;         END DO
+;     END SUBROUTINE f
+; END MODULE m
+
+; RUN: opt %loadPolly \
+; RUN: -polly-invariant-load-hoisting \
+; RUN: -polly-detect-fortran-arrays \
+; RUN: -polly-codegen-ppcg \
+; RUN: -polly-acc-codegen-managed-memory \
+; RUN: -polly-acc-fail-on-verify-module-failure \
+; RUN: -debug-only=polly-codegen-ppcg,polly-scops \
+; RUN: -S \
+; RUN: -pass-remarks=polly \
+; RUN: < %s
+
+; ModuleID = 'm.ll'
+source_filename = "m.bc"
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+; Function Attrs: nounwind uwtable
+define void @__m_MOD_f([0 x float]* noalias %arr, i32* noalias %bloop, i32* noalias %eloop, [0 x float]* noalias %arrinp) unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %0 = load i32, i32* %bloop, align 4
+  %1 = sext i32 %0 to i64
+  %2 = load i32, i32* %eloop, align 4
+  %3 = sub nsw i64 0, %1
+  %4 = icmp sgt i32 %0, %2
+  br i1 %4, label %return, label %"3.preheader"
+
+"3.preheader":                                    ; preds = %entry.split
+  br label %"3"
+
+"3":                                              ; preds = %"3", %"3.preheader"
+  %5 = phi i32 [ %15, %"3" ], [ %0, %"3.preheader" ]
+  %6 = sext i32 %5 to i64
+  %7 = tail call i64 @_gfortran_polly_array_index_1(i64 %3, i64 1, i64 %6) #1
+  %8 = tail call i64 @_gfortran_polly_array_index_1(i64 %3, i64 1, i64 %6) #1
+  %9 = getelementptr [0 x float], [0 x float]* %arrinp, i64 0, i64 %8
+  %10 = bitcast float* %9 to i32*
+  %11 = load i32, i32* %10, align 4
+  %12 = getelementptr [0 x float], [0 x float]* %arr, i64 0, i64 %7
+  %13 = bitcast float* %12 to i32*
+  store i32 %11, i32* %13, align 4
+  %14 = icmp eq i32 %5, %2
+  %15 = add i32 %5, 1
+  br i1 %14, label %return.loopexit, label %"3"
+
+return.loopexit:                                  ; preds = %"3"
+  br label %return
+
+return:                                           ; preds = %return.loopexit, %entry.split
+  ret void
+}
+
+declare i64 @_gfortran_polly_array_index_1(i64, i64, i64) #2
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { readnone }
+

test/GPGPU/abstract-index-function-simple.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-allow-nonaffine \
+; RUN: -polly-ignore-aliasing -polly-use-llvm-names \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=SCOP
+
+; RUN: opt %loadPolly -S -polly-allow-nonaffine \
+; RUN: -polly-acc-codegen-managed-memory \
+; RUN: -polly-ignore-aliasing -polly-use-llvm-names \
+; RUN: -polly-invariant-load-hoisting -polly-codegen-ppcg \
+; RUN:  -polly-acc-fail-on-verify-module-failure < %s\
+; RUN: | FileCheck %s -check-prefix=HOST-IR
+
+; RUN: opt %loadPolly  -disable-output -polly-acc-dump-kernel-ir \
+; RUN: -polly-acc-codegen-managed-memory \
+; RUN: -polly-allow-nonaffine \
+; RUN: -polly-ignore-aliasing -polly-use-llvm-names \
+; RUN: -polly-invariant-load-hoisting -polly-codegen-ppcg \
+; RUN: -polly-acc-fail-on-verify-module-failure < %s \
+; RUN: | FileCheck %s -check-prefix=KERNEL-IR
+
+; SCOP:    Function: __m_MOD_f
+; SCOP-NEXT:    Region: %"3"---%return
+; SCOP-NEXT:    Max Loop Depth:  2
+
+; HOST-IR: polly_getKernel
+
+; Check that the call to polly_array_index has been eliminated.
+; KERNEL-IR-NOT: call i64 @_gfortran_polly_array_index_2
+
+; MODULE m
+; IMPLICIT NONE
+;     ! REAL :: &
+;     !     g_arr_const_5_5(5, 5)
+;     REAL, ALLOCATABLE :: &
+;         g_arr(:,:)
+;
+; CONTAINS
+;     SUBROUTINE f()
+;         INTEGER :: &
+;             i, j
+;
+;         REAL :: &
+;             coeff
+;
+;         DO i=1,3
+;            DO j=1,3
+;               g_arr(i*5, j*2) = 100
+;            END DO
+;         END DO
+;     END SUBROUTINE f
+; END MODULE m
+; ModuleID = 'm.ll'
+source_filename = "m.bc"
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+%"struct.array2_real(kind=4)" = type { i8*, i64, i64, [2 x %struct.descriptor_dimension] }
+%struct.descriptor_dimension = type { i64, i64, i64 }
+
+@__m_MOD_g_arr = unnamed_addr global %"struct.array2_real(kind=4)" zeroinitializer, align 32
+
+; Function Attrs: nounwind uwtable
+define void @__m_MOD_f() unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %"3"
+
+"3":                                              ; preds = %"6", %entry.split
+  %indvars.iv1 = phi i64 [ %indvars.iv.next2, %"6" ], [ 1, %entry.split ]
+  br label %"4"
+
+"4":                                              ; preds = %"4", %"3"
+  %indvars.iv = phi i64 [ %indvars.iv.next, %"4" ], [ 1, %"3" ]
+  %0 = load float*, float** bitcast (%"struct.array2_real(kind=4)"* @__m_MOD_g_arr to float**), align 32
+  %1 = mul nuw nsw i64 %indvars.iv1, 5
+  %2 = shl i64 %indvars.iv, 1
+  %3 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=4)", %"struct.array2_real(kind=4)"* @__m_MOD_g_arr, i64 0, i32 3, i64 1, i32 0), align 8
+  %4 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=4)", %"struct.array2_real(kind=4)"* @__m_MOD_g_arr, i64 0, i32 1), align 8
+  %5 = tail call i64 @_gfortran_polly_array_index_2(i64 %4, i64 %3, i64 1, i64 %2, i64 %1) #1
+  %6 = getelementptr float, float* %0, i64 %5
+  store float 1.000000e+02, float* %6, align 4
+  %7 = icmp eq i64 %indvars.iv, 3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br i1 %7, label %"6", label %"4"
+
+"6":                                              ; preds = %"4"
+  %8 = icmp eq i64 %indvars.iv1, 3
+  %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1
+  br i1 %8, label %return, label %"3"
+
+return:                                           ; preds = %"6"
+  ret void
+}
+
+declare i64 @_gfortran_polly_array_index_2(i64, i64, i64, i64, i64) #2
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { readnone }
+

test/ScopInfo/abstract-index-function-simple.ll

+; RUN: opt %loadPolly -polly-scops -analyze \
+; RUN: -polly-ignore-aliasing -polly-use-llvm-names \
+; RUN: -polly-invariant-load-hoisting  < %s  | FileCheck %s
+
+
+; Check that we detect the scop.
+; CHECK:    Function: __m_MOD_f
+; CHECK:    Region: %"3"---%return
+; CHECK:    Max Loop Depth:  2
+
+; Check that we generate pw_affs for strides.
+; CHECK:       Arrays {
+; CHECK-NEXT:      float* MemRef___m_MOD_g_arr[*]; // Element size 8
+; CHECK-NEXT:      float MemRef1(Strides)[%3][1];[Offset: %4]; [BasePtrOrigin: MemRef___m_MOD_g_arr] // Element size 4
+; CHECK-NEXT:  }
+; CHECK-NEXT:  Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:      float* MemRef___m_MOD_g_arr[*]; // Element size 8
+; CHECK-NEXT:      float MemRef1(Strides)[ [0_param_stride_size] -> { [] -> [(0_param_stride_size)] } ][ [1_param_stride_size] -> { [] -> [(1_param_stride_size)] } ];[Offset: %4]; [BasePtrOrigin: MemRef___m_MOD_g_arr] // Element size 4
+; CHECK-NEXT:  }
+
+
+; MODULE m
+; IMPLICIT NONE
+;     ! REAL :: &
+;     !     g_arr_const_5_5(5, 5)
+;     REAL, ALLOCATABLE :: &
+;         g_arr(:,:)
+;
+; CONTAINS
+;     SUBROUTINE f()
+;         INTEGER :: &
+;             i, j
+;
+;         REAL :: &
+;             coeff
+;
+;         DO i=1,3
+;            DO j=1,3
+;               g_arr(i*5, j*2) = 100
+;            END DO
+;         END DO
+;     END SUBROUTINE f
+; END MODULE m
+; ModuleID = 'm.ll'
+source_filename = "m.bc"
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+%"struct.array2_real(kind=4)" = type { i8*, i64, i64, [2 x %struct.descriptor_dimension] }
+%struct.descriptor_dimension = type { i64, i64, i64 }
+
+@__m_MOD_g_arr = unnamed_addr global %"struct.array2_real(kind=4)" zeroinitializer, align 32
+
+; Function Attrs: nounwind uwtable
+define void @__m_MOD_f() unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %"3"
+
+"3":                                              ; preds = %"6", %entry.split
+  %indvars.iv1 = phi i64 [ %indvars.iv.next2, %"6" ], [ 1, %entry.split ]
+  br label %"4"
+
+"4":                                              ; preds = %"4", %"3"
+  %indvars.iv = phi i64 [ %indvars.iv.next, %"4" ], [ 1, %"3" ]
+  %0 = load float*, float** bitcast (%"struct.array2_real(kind=4)"* @__m_MOD_g_arr to float**), align 32
+  %1 = mul nuw nsw i64 %indvars.iv1, 5
+  %2 = shl i64 %indvars.iv, 1
+  %3 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=4)", %"struct.array2_real(kind=4)"* @__m_MOD_g_arr, i64 0, i32 3, i64 1, i32 0), align 8
+  %4 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=4)", %"struct.array2_real(kind=4)"* @__m_MOD_g_arr, i64 0, i32 1), align 8
+  %5 = tail call i64 @_gfortran_polly_array_index_2(i64 %4, i64 %3, i64 1, i64 %2, i64 %1) #1
+  %6 = getelementptr float, float* %0, i64 %5
+  store float 1.000000e+02, float* %6, align 4
+  %7 = icmp eq i64 %indvars.iv, 3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br i1 %7, label %"6", label %"4"
+
+"6":                                              ; preds = %"4"
+  %8 = icmp eq i64 %indvars.iv1, 3
+  %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1
+  br i1 %8, label %return, label %"3"
+
+return:                                           ; preds = %"6"
+  ret void
+}
+
+declare i64 @_gfortran_polly_array_index_2(i64, i64, i64, i64, i64) #2
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { readnone }

tools/GPURuntime/GPUJIT.c

 }
 
 void polly_launchKernel(PollyGPUFunction *Kernel, unsigned int GridDimX,
                         unsigned int GridDimY, unsigned int BlockDimX,
                         unsigned int BlockDimY, unsigned int BlockDimZ,
                         void **Parameters) {
   dump_function();
 
+  /*
+  void **kernel = (void **)Parameters[0];
+  for(int i = 0; i < 4; i++) {
+      fprintf(stderr, "\tParam[%d] = %p\n", i, Parameters[i]);
+  }
+
+  fprintf(stderr, "\t\tKERNEL: %p\n", *kernel);
+  fprintf(stderr, "\t\tSTRIDE0: %d\n", *((int *)(Parameters[1])));
+  fprintf(stderr, "\t\tSTRIDE1: %d\n", *((int *)(Parameters[2])));
+  fprintf(stderr, "\t\tOFFSET: %d\n", *((int *)(Parameters[3])));
+  */
+
   switch (Runtime) {
 #ifdef HAS_LIBCUDART
   case RUNTIME_CUDA:
     launchKernelCUDA(Kernel, GridDimX, GridDimY, BlockDimX, BlockDimY,
                      BlockDimZ, Parameters);
     break;
 #endif /* HAS_LIBCUDART */
 #ifdef HAS_LIBOPENCL
#else
   exit(-1);
 #endif
 }
 
 void *polly_mallocManaged(size_t size) {
   dump_function();
 
 #ifdef HAS_LIBCUDART
-  return mallocManagedCUDA(size);
+  void *mem =  mallocManagedCUDA(size);
+  // fprintf(stderr, "\tMallocManaged: %zu | %p \n", size, mem);
+ return mem;
 #else
   fprintf(stderr, "No CUDA Runtime. Managed memory only supported by CUDA\n");
   exit(-1);
 #endif
 }
 
 /* Initialize GPUJIT with CUDA as runtime library. */
 PollyGPUContext *polly_initContextCUDA() {