[Polly] Introduce the ScopArrayInfo class.

[jdoerfert]

Summary

This class allows to store information about the arrays in the SCoP.
For each base pointer in the SCoP one object is created storing the
type and dimension sizes of the array. The objects can be obtained via
the SCoP, a MemoryAccess or the isl_id associated with the output
dimension of a MemoryAccess (the description of what is accessed).

So far we use the information in the IslExprBuilder to create the
right base type before indexing into the base array. This fixes the
bug http://llvm.org/bugs/show_bug.cgi?id=21113 (both test cases are
included). On top of that we can now build runtime alias checks for
delinearized arrays as the dimension sizes are also part of the
ScopArrayInfo objects.

[grosser]

Very nice. Besides fixing two important bugs in the run-time alias checks, this is also conceptually a big step forward. Thanks for working on this last night!

The patch looks great, with just some test-case changes that I unfortunately do not understand.

I also added a couple (3-4) of minor comments on your code. None of them has correctness implications and the original code is already very nice, so just include them as you like.

include/polly/CodeGen/IslExprBuilder.h

84

It is unclear to me why the IslExpr Builder would need a SCoP now.

lib/Analysis/ScopInfo.cpp

294

A similar function that takes an isl_id and returns the ScopArrayInfo might be handy too. (See later comment on how to obtain the BasePtr/ElementType of an isl_ast_op_access).

475

Conceptually it probably makes sense to allocate one isl_id in the ScopArrayInfo class and then give users the option to obtain copies of this id. This makes clear that all these isl_ids are identical. (The current code also works at the moment AFAIK, as isl assumes two ids are identical if their name and the user pointer are identical).

lib/CodeGen/IslCodeGeneration.cpp

58

I am surprised we need the Scop here.

lib/CodeGen/IslExprBuilder.cpp

113

Instead of passing the scop to this place and use the base ptr to look up the ScopArrayInfo, you could possibly also obtain the isl_id from the isl_ast_expr_get_op_arg(Expr, 0) and then use a "static ScopArrayInfo::getFromid(Id)" function.

Also, instead of obtaining the Base pointer by calling create(), we could obtain
it directly from this ScopArrayInfo object. This would allow us to remove
IslNodeBuilder::addMemoryAccesses(), which was mostly added due to us missing a ScopArrayInfo class.

137

Nice cleanup!

test/Isl/CodeGen/MemAccess/codegen_simple.ll

43

It is unclear to me why this test case needs to be modified and especially why the generated IR now can be have one of two forms. Is the IR we generate not supposed to be predictable?

[jdoerfert]

Responses. I would try to change the code according to the comments but I still like the changes to the tests ({{(i32}i64)}} instread of i32)

include/polly/CodeGen/IslExprBuilder.h

84

To access the ScopInfoArray for a base pointer.

lib/Analysis/ScopInfo.cpp

475

I'll change that. Good point.

lib/CodeGen/IslCodeGeneration.cpp

58

Just to pass it on to the IslExprBuilder.

lib/CodeGen/IslExprBuilder.cpp

113

True, I'll try that and keep it if it works

test/Isl/CodeGen/MemAccess/codegen_simple.ll

43

It has a different form now because for A[100]

CreateBitcast(A[0]) == yields ==> getelemenptr inbounds [100 x i32]* @A, i32 0, i32 0

where the indices are of type i32.

Before the patch we added the indices and used the typ of the only real index op to create "zeros" (thus they were i64). Now I don't want to hardcode i32 because a change in the bitcast function or in our code could revert this or mix the indice types without a semantical change, thus I don't see the reason to fix one type here.

[jdoerfert]

Updated according to the comments (except test cases)

[jdoerfert]

Closed by commit rL219077 (authored by @jdoerfert).

include/polly/CodeGen/IslExprBuilder.h

 /// enough).
 class IslExprBuilder {
 public:
   /// @brief A map from isl_ids to llvm::Values.
   typedef std::map<isl_id *, llvm::Value *> IDToValueTy;
 
   /// @brief Construct an IslExprBuilder.
   ///
+  /// @param S       The current SCoP.
   /// @param Builder The IRBuilder used to construct the isl_ast_expr[ession].
   ///                The insert location of this IRBuilder defines WHERE the
   ///                corresponding LLVM-IR is generated.
   ///
   /// @param IDToValue The isl_ast_expr[ession] may reference parameters or
   ///                  variables (identified by an isl_id). The IDTOValue map
   ///                  specifies the LLVM-IR Values that correspond to these
   ///                  parameters and variables.
-  IslExprBuilder(PollyIRBuilder &Builder, IDToValueTy &IDToValue)
-      : Builder(Builder), IDToValue(IDToValue) {}
+  IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue)
+      : S(S), Builder(Builder), IDToValue(IDToValue) {}
 
   /// @brief 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);
 
public:
   /// The type needs to be large enough to hold all possible input and all
   /// possible output values.
   ///
   /// @param Expr The expression for which to find the type.
   /// @return The type with which the expression should be computed.
   llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr);
 
 private:
+  /// @brief The current SCoP.
+  Scop &S;
+
   PollyIRBuilder &Builder;
   std::map<isl_id *, llvm::Value *> &IDToValue;
 
   llvm::Value *createOp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);

include/polly/ScopInfo.h

 class IRAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 class TempScop;
 class SCEVAffFunc;
 class Comparison;
 
-//===----------------------------------------------------------------------===//
+/// @brief A class to store information about arrays in the SCoP.
+///
+/// Objects are accessible via the ScoP, MemoryAccess or the id associated with
+/// the MemoryAccess access function.
+///
+class ScopArrayInfo {
+public:
+  /// @brief Construct a ScopArrayInfo object.
+  ///
+  /// @param BasePtr        The array base pointer.
+  /// @param AccessType     The type used to access this array.
+  /// @param DimensionSizes A vector containing the size of each dimension.
+  ScopArrayInfo(Value *BasePtr, Type *AccessType,
+                const SmallVector<const SCEV *, 4> &DimensionSizes)
+      : BasePtr(BasePtr), AccessType(AccessType),
+        DimensionSizes(DimensionSizes) {}
+
+  /// @brief Return the base pointer.
+  Value *getBasePtr() const { return BasePtr; }
+
+  /// @brief Return the number of dimensions.
+  unsigned getNumberOfDimensions() const { return DimensionSizes.size(); }
+
+  /// @brief Return the size of dimension @p dim.
+  const SCEV *getDimensionSize(unsigned dim) const {
+    assert(dim < getNumberOfDimensions() && "Invalid dimension");
+    return DimensionSizes[dim];
+  }
+
+  /// @brief Return the type used to access this array in the SCoP.
+  Type *getType() const { return AccessType; }
+
+  /// @brief Dump a readable representation to stderr.
+  void dump() const;
+
+  /// @brief Print a readable representation to @p OS.
+  void print(raw_ostream &OS) const;
+
+  /// @brief Access the ScopArrayInfo associated with an access function.
+  static const ScopArrayInfo *
+  getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA);
+
+private:
+  /// @brief The base pointer.
+  Value *BasePtr;
+
+  /// @brief The type used to access this array.
+  Type *AccessType;
+
+  /// @brief The sizes of each dimension.
+  SmallVector<const SCEV *, 4> DimensionSizes;
+};
+
 /// @brief Represent memory accesses in statements.
 class MemoryAccess {
 public:
   /// @brief The access type of a memory access
   ///
   /// There are three kind of access types:
   ///
   /// * A read access
private:
   /// Updated access relation read from JSCOP file.
   isl_map *newAccessRelation;
 
   void assumeNoOutOfBound(const IRAccess &Access);
 
 public:
   /// @brief Create a memory access from an access in LLVM-IR.
   ///
-  /// @param Access     The memory access.
-  /// @param Statement  The statement that contains the access.
-  /// @param SE         The ScalarEvolution analysis.
+  /// @param Access    The memory access.
+  /// @param AccInst   The access instruction.
+  /// @param Statement The statement that contains the access.
+  /// @param SAI       The ScopArrayInfo object for this base pointer.
   MemoryAccess(const IRAccess &Access, Instruction *AccInst,
-               ScopStmt *Statement);
+               ScopStmt *Statement, const ScopArrayInfo *SAI);
 
   ~MemoryAccess();
 
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return Type; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
public:
   std::string getAccessRelationStr() const;
 
   /// @brief Get the base address of this access (e.g. A for A[i+j]).
   Value *getBaseAddr() const { return BaseAddr; }
 
   /// @brief Get the base array isl_id for this access.
   __isl_give isl_id *getArrayId() const;
 
+  /// @brief Get the ScopArrayInfo object for the base address.
+  const ScopArrayInfo *getScopArrayInfo() const;
+
   /// @brief Return a string representation of the accesse's reduction type.
   const std::string getReductionOperatorStr() const;
 
   /// @brief Return a string representation of the reduction type @p RT.
   static const std::string getReductionOperatorStr(ReductionType RT);
 
   const std::string &getBaseName() const { return BaseName; }
 
private:
   ParamIdType ParameterIds;
 
   /// Isl context.
   isl_ctx *IslCtx;
 
   /// Constraints on parameters.
   isl_set *Context;
 
+  /// @brief A map to remember ScopArrayInfo objects for all base pointers.
+  DenseMap<const Value *, const ScopArrayInfo *> ScopArrayInfoMap;
+
   /// @brief The assumptions under which this scop was built.
   ///
   /// When constructing a scop sometimes the exact representation of a statement
   /// or condition would be very complex, but there is a common case which is a
   /// lot simpler, but which is only valid under certain assumptions. The
   /// assumed context records the assumptions taken during the construction of
   /// this scop and that need to be code generated as a run-time test.
   isl_set *AssumedContext;
public:
   typedef StmtSet::const_reverse_iterator const_reverse_iterator;
 
   reverse_iterator rbegin() { return Stmts.rbegin(); }
   reverse_iterator rend() { return Stmts.rend(); }
   const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
   const_reverse_iterator rend() const { return Stmts.rend(); }
   //@}
 
+  /// @brief Return the (possibly new) ScopArrayInfo object for @p Access.
+  const ScopArrayInfo *getOrCreateScopArrayInfo(const IRAccess &Access,
+                                                Instruction *AccessInst);
+
+  /// @brief Return the cached ScopArrayInfo object for @p BasePtr.
+  const ScopArrayInfo *getScopArrayInfo(Value *BasePtr);
+
   void setContext(isl_set *NewContext);
 
   /// @brief Align the parameters in the statement to the scop context
   void realignParams();
 
   /// @brief Print the static control part.
   ///
   /// @param OS The output stream the static control part is printed to.

lib/Analysis/ScopInfo.cpp

 }
 
 int SCEVAffinator::getLoopDepth(const Loop *L) {
   Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
   assert(outerLoop && "Scop does not contain this loop");
   return L->getLoopDepth() - outerLoop->getLoopDepth();
 }
 
+void ScopArrayInfo::dump() const { print(errs()); }
+
+void ScopArrayInfo::print(raw_ostream &OS) const {
+  OS << "ScopArrayInfo:\n";
+  OS << "  Base: " << *getBasePtr() << "\n";
+  OS << "  Type: " << *getType() << "\n";
+  OS << "  Dimension Sizes:\n";
+  for (unsigned u = 0; u < getNumberOfDimensions(); u++)
+    OS << "    " << u << ") " << *DimensionSizes[u] << "\n";
+  OS << "\n";
+}
+
+const ScopArrayInfo *
+ScopArrayInfo::getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA) {
+  isl_id *Id = isl_pw_multi_aff_get_tuple_id(PMA, isl_dim_out);
+  assert(Id && "Output dimension didn't have an ID");
+  void *User = isl_id_get_user(Id);
+  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
+  isl_id_free(Id);
+  return SAI;
+}
+
 const std::string
 MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
   switch (RT) {
   case MemoryAccess::RT_NONE:
     llvm_unreachable("Requested a reduction operator string for a memory "
                      "access which isn't a reduction");
   case MemoryAccess::RT_ADD:
     return "+";
static MemoryAccess::AccessType getMemoryAccessType(const IRAccess &Access) {
   case IRAccess::MUST_WRITE:
     return MemoryAccess::MUST_WRITE;
   case IRAccess::MAY_WRITE:
     return MemoryAccess::MAY_WRITE;
   }
   llvm_unreachable("Unknown IRAccess type!");
 }
 
+const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
+  isl_id *ArrayId = getArrayId();
+  void *User = isl_id_get_user(ArrayId);
+  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
+  isl_id_free(ArrayId);
+  return SAI;
+}
+
 isl_id *MemoryAccess::getArrayId() const {
   return isl_map_get_tuple_id(AccessRelation, isl_dim_out);
 }
 
 isl_map *MemoryAccess::getAccessRelation() const {
   return isl_map_copy(AccessRelation);
 }
 
void MemoryAccess::assumeNoOutOfBound(const IRAccess &Access) {
   Outside = isl_set_intersect(Outside, Statement->getDomain());
   Outside = isl_set_params(Outside);
   Outside = isl_set_complement(Outside);
   Statement->getParent()->addAssumption(Outside);
   isl_space_free(Space);
 }
 
 MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst,
-                           ScopStmt *Statement)
+                           ScopStmt *Statement, const ScopArrayInfo *SAI)
     : Type(getMemoryAccessType(Access)), Statement(Statement), Inst(AccInst),
       newAccessRelation(nullptr) {
 
   isl_ctx *Ctx = Statement->getIslCtx();
   BaseAddr = Access.getBase();
   BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
-  isl_id *BaseAddrId = isl_id_alloc(Ctx, getBaseName().c_str(), nullptr);
+
+  void *User = const_cast<ScopArrayInfo *>(SAI);
+  isl_id *BaseAddrId = isl_id_alloc(Ctx, getBaseName().c_str(), User);
 
   if (!Access.isAffine()) {
     // We overapproximate non-affine accesses with a possible access to the
     // whole array. For read accesses it does not make a difference, if an
     // access must or may happen. However, for write accesses it is important to
     // differentiate between writes that must happen and writes that may happen.
     AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
     AccessRelation =
void ScopStmt::buildScattering(SmallVectorImpl<unsigned> &Scatter) {
   // Fill scattering dimensions.
   for (unsigned i = 2 * NbIterators + 1; i < NbScatteringDims; ++i)
     Scattering = isl_map_fix_si(Scattering, isl_dim_out, i, 0);
 
   Scattering = isl_map_align_params(Scattering, Parent.getParamSpace());
 }
 
 void ScopStmt::buildAccesses(TempScop &tempScop, const Region &CurRegion) {
-  for (auto &&Access : *tempScop.getAccessFunctions(BB)) {
-    MemAccs.push_back(new MemoryAccess(Access.first, Access.second, this));
+  for (const auto &AccessPair : *tempScop.getAccessFunctions(BB)) {
+    const IRAccess &Access = AccessPair.first;
+    Instruction *AccessInst = AccessPair.second;
+
+    const ScopArrayInfo *SAI =
+        getParent()->getOrCreateScopArrayInfo(Access, AccessInst);
+    MemAccs.push_back(new MemoryAccess(Access, AccessInst, this, SAI));
 
     // We do not track locations for scalar memory accesses at the moment.
     //
     // We do not have a use for this information at the moment. If we need this
     // at some point, the "instruction -> access" mapping needs to be enhanced
     // as a single instruction could then possibly perform multiple accesses.
-    if (!Access.first.isScalar()) {
-      assert(!InstructionToAccess.count(Access.second) &&
+    if (!Access.isScalar()) {
+      assert(!InstructionToAccess.count(AccessInst) &&
              "Unexpected 1-to-N mapping on instruction to access map!");
-      InstructionToAccess[Access.second] = MemAccs.back();
+      InstructionToAccess[AccessInst] = MemAccs.back();
     }
   }
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 

 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
 
   // Free the statements;
   for (ScopStmt *Stmt : *this)
     delete Stmt;
 
+  // Free the ScopArrayInfo objects.
+  for (auto &ScopArrayInfoPair : ScopArrayInfoMap)
+    delete ScopArrayInfoPair.second;
+
   // Free the alias groups
   for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
     for (MinMaxAccessTy &MMA : *MinMaxAccesses) {
       isl_pw_multi_aff_free(MMA.first);
       isl_pw_multi_aff_free(MMA.second);
     }
     delete MinMaxAccesses;
   }
 }
 
+const ScopArrayInfo *Scop::getOrCreateScopArrayInfo(const IRAccess &Access,
+                                                    Instruction *AccessInst) {
+  Value *BasePtr = Access.getBase();
+  const ScopArrayInfo *&SAI = ScopArrayInfoMap[BasePtr];
+  if (!SAI) {
+    Type *AccessType = getPointerOperand(*AccessInst)->getType();
+    SAI = new ScopArrayInfo(BasePtr, AccessType, Access.Sizes);
+  }
+  return SAI;
+}
+
+const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr) {
+  const SCEV *PtrSCEV = SE->getSCEV(BasePtr);
+  const SCEVUnknown *PtrBaseSCEV =
+      cast<SCEVUnknown>(SE->getPointerBase(PtrSCEV));
+  const ScopArrayInfo *SAI = ScopArrayInfoMap[PtrBaseSCEV->getValue()];
+  assert(SAI && "No ScopArrayInfo available for this base pointer");
+  return SAI;
+}
+
 std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
 std::string Scop::getAssumedContextStr() const {
   return stringFromIslObj(AssumedContext);
 }
 
 std::string Scop::getNameStr() const {
   std::string ExitName, EntryName;
   raw_string_ostream ExitStr(ExitName);

lib/CodeGen/IslCodeGeneration.cpp

 // its code in the new execution order defined by the changed scattering.
 //
 //===----------------------------------------------------------------------===//
 #include "polly/Config/config.h"
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/BlockGenerators.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/IslAst.h"
-#include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/LoopGenerators.h"
 #include "polly/CodeGen/Utils.h"
 #include "polly/Dependences.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/TempScopInfo.h"

 
 using namespace polly;
 using namespace llvm;
 
 #define DEBUG_TYPE "polly-codegen-isl"
 
 class IslNodeBuilder {
 public:
-  IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
-                 LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT)
-      : Builder(Builder), Annotator(Annotator), ExprBuilder(Builder, IDToValue),
-        P(P), LI(LI), SE(SE), DT(DT) {}
+  IslNodeBuilder(Scop &S, PollyIRBuilder &Builder, ScopAnnotator &Annotator,
+                 Pass *P, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT)
+      : Builder(Builder), Annotator(Annotator),
+        ExprBuilder(S, Builder, IDToValue), P(P), LI(LI), SE(SE), DT(DT) {}
 
   /// @brief Add the mappings from array id's to array llvm::Value's.
   void addMemoryAccesses(Scop &S);
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
   IslExprBuilder &getExprBuilder() { return ExprBuilder; }
 
 private:
bool runOnScop(Scop &S) {
 
     // Build the alias scopes for annotations first.
     if (PollyAnnotateAliasScopes)
       Annotator.buildAliasScopes(S);
 
     BasicBlock *EnteringBB = simplifyRegion(&S, this);
     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
-    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *LI, *SE, *DT);
+    IslNodeBuilder NodeBuilder(S, Builder, Annotator, this, *LI, *SE, *DT);
     NodeBuilder.addMemoryAccesses(S);
     NodeBuilder.addParameters(S.getContext());
 
     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
     BasicBlock *StartBlock = executeScopConditionally(S, this, RTC);
     Builder.SetInsertPoint(StartBlock->begin());
 
     NodeBuilder.create(AI->getAst());

lib/CodeGen/IslExprBuilder.cpp

 //===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/CodeGen/IslExprBuilder.h"
 
+#include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 using namespace polly;
 
 Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) {
assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_access &&
          "not an access isl ast expression");
   assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 &&
          "We need at least two operands to create a member access.");
 
   // TODO: Support for multi-dimensional array.
   assert(isl_ast_expr_get_op_n_arg(Expr) == 2 &&
          "Multidimensional access functions are not supported yet");
 
-  Value *Base, *IndexOp, *Zero, *Access;
-  SmallVector<Value *, 4> Indices;
-  Type *PtrElTy;
+  Value *Base, *IndexOp, *Access;
 
   Base = create(isl_ast_expr_get_op_arg(Expr, 0));
   assert(Base->getType()->isPointerTy() && "Access base should be a pointer");
+  const Twine &BaseName = Base->getName();
+
+  const ScopArrayInfo *SAI = S.getScopArrayInfo(Base);
+  if (Base->getType() != SAI->getType())
+    Base = Builder.CreateBitCast(Base, SAI->getType(),
+                                 "polly.access.cast." + BaseName);
 
   IndexOp = create(isl_ast_expr_get_op_arg(Expr, 1));
   assert(IndexOp->getType()->isIntegerTy() &&
          "Access index should be an integer");
-  Zero = ConstantInt::getNullValue(IndexOp->getType());
-
-  // If base is a array type like,
-  //   int A[N][M][K];
-  // we have to adjust the GEP. The easiest way is to transform accesses like,
-  //   A[i][j][k]
-  // into equivalent ones like,
-  //   A[0][0][ i*N*M + j*M + k]
-  // because SCEV already folded the "peudo dimensions" into one. Thus our index
-  // operand will be 'i*N*M + j*M + k' anyway.
-  PtrElTy = Base->getType()->getPointerElementType();
-  while (PtrElTy->isArrayTy()) {
-    Indices.push_back(Zero);
-    PtrElTy = PtrElTy->getArrayElementType();
-  }
-
-  Indices.push_back(IndexOp);
-  assert((PtrElTy->isIntOrIntVectorTy() || PtrElTy->isFPOrFPVectorTy() ||
-          PtrElTy->isPtrOrPtrVectorTy()) &&
-         "We do not yet change the type of the access base during code "
-         "generation.");
 
-  Access = Builder.CreateGEP(Base, Indices, "polly.access." + Base->getName());
+  Access = Builder.CreateGEP(Base, IndexOp, "polly.access." + BaseName);
 
   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");

lib/Exchange/JSONExporter.cpp

for (MemoryAccess *MA : *Stmt) {
       if (isl_map_dim(newAccessMap, isl_dim_param) !=
           isl_map_dim(currentAccessMap, isl_dim_param)) {
         errs() << "JScop file changes the number of parameter dimensions\n";
         isl_map_free(currentAccessMap);
         isl_map_free(newAccessMap);
         return false;
       }
 
+      isl_id *OutId = isl_map_get_tuple_id(currentAccessMap, isl_dim_out);
+      newAccessMap = isl_map_set_tuple_id(newAccessMap, isl_dim_out, OutId);
+
       // We keep the old alignment, thus we cannot allow accesses to memory
       // locations that were not accessed before.
       isl_set *newAccessSet = isl_map_range(isl_map_copy(newAccessMap));
       isl_set *currentAccessSet = isl_map_range(isl_map_copy(currentAccessMap));
       bool isSubset = isl_set_is_subset(newAccessSet, currentAccessSet);
       isl_set_free(newAccessSet);
       isl_set_free(currentAccessSet);
 

test/Isl/CodeGen/MemAccess/codegen_constant_offset.ll

 
 for.inc:                                          ; preds = %for.body
   %inc = add nsw i32 %tmp1, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret i32 0
 }
-; CHECK: load i32* getelementptr inbounds ([100 x i32]* @A, i64 0, i64 10)
+; CHECK: load i32* getelementptr inbounds ([100 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 10)

test/Isl/CodeGen/MemAccess/codegen_simple.ll

 
 for.inc:                                          ; preds = %for.body
   %inc = add nsw i32 %tmp1, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret i32 0
 }
-; CHECK: load i32* getelementptr inbounds ([100 x i32]* @A, i64 0, i64 0)
+; CHECK: load i32* getelementptr inbounds ([100 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0)

test/Isl/CodeGen/MemAccess/codegen_simple_float.ll

 
 for.inc:                                          ; preds = %for.body
   %inc = add nsw i32 %tmp1, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret i32 0
 }
-; CHECK: load float* getelementptr inbounds ([100 x float]* @A, i64 0, i64 0)
+; CHECK: load float* getelementptr inbounds ([100 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0)

test/Isl/CodeGen/MemAccess/codegen_simple_md.ll

 }
 
 ; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
 ; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
 ; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
 ; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i64 %[[SUM1]], 5
-; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr [1040 x i32]* @A, i64 0, i64 %[[SUM2]]
+; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr i32* getelementptr inbounds ([1040 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i{{(32|64)}} %[[SUM2]]
 ; WITHCONST:  store i32 100, i32* %[[ACC]]
 
 ; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
 ; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
 ; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
-; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr [1040 x i32]* @A, i64 0, i64 %[[SUM1]]
+; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr i32* getelementptr inbounds ([1040 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i{{(32|64)}} %[[SUM1]]
 ; WITHOUTCONST:  store i32 100, i32* %[[ACC]]

test/Isl/CodeGen/MemAccess/codegen_simple_md_float.ll

 }
 
 ; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
 ; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
 ; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
 ; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i64 %[[SUM1]], 5
-; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr [1040 x float]* @A, i64 0, i64 %[[SUM2]]
+; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr float* getelementptr inbounds ([1040 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i{{(32|64)}} %[[SUM2]]
 ; WITHCONST:  store float 1.000000e+02, float* %[[ACC]]
 
 ; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
 ; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
 ; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
 ; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
-; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr [1040 x float]* @A, i64 0, i64 %[[SUM1]]
+; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr float* getelementptr inbounds ([1040 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i{{(32|64)}} %[[SUM1]]
 ; WITHOUTCONST:  store float 1.000000e+02, float* %[[ACC]]

test/Isl/CodeGen/aliasing_different_base_and_access_type.ll

+; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s
+;
+; We have to cast %B to "short *" before we create RTCs.
+;
+; CHECK:      entry:
+; CHECK-NEXT:   %polly.access.cast.B = bitcast i32* %B to i16*
+; CHECK-NEXT:   %polly.access.B = getelementptr i16* %polly.access.cast.B, i64 1024
+;
+; We should never access %B as an i32 pointer:
+;
+; CHECK-NOT: getelementptr i32* %B
+;
+;    void jd(int *A, int *B) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = ((short *)B)[i];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = bitcast i32* %B to i16*
+  %arrayidx = getelementptr inbounds i16* %tmp, i64 %indvars.iv
+  %tmp1 = load i16* %arrayidx, align 2
+  %conv = sext i16 %tmp1 to i32
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %conv, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/aliasing_struct_element.ll

+; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s
+;
+; We should only access (or compute the address of) "the first element" of %S
+; as it is a single struct not a struct array. The maximal access to S, thus
+; S->B[1023] is for ScalarEvolution an access with offset of 1423, 1023 for the
+; index inside the B part of S and 400 to skip the Dummy array in S. Note that
+; these numbers are relative to the actual type of &S->B[i] (char*) not to the
+; type of S (struct st *) or something else.
+;
+; Verify that we do not use the offset 1423 into a non existent S array when we
+; compute runtime alias checks but treat it as if it was a char array.
+;
+; CHECK: %polly.access.cast.S = bitcast %struct.st* %S to i8*
+; CHECK: %polly.access.S = getelementptr i8* %polly.access.cast.S, i64 1424
+;
+;    struct st {
+;      int Dummy[100];
+;      char B[100];
+;    };
+;
+;    void jd(int *A, struct st *S) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = S->B[i];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.st = type { [100 x i32], [100 x i8] }
+
+define void @jd(i32* %A, %struct.st* %S) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds %struct.st* %S, i64 0, i32 1, i64 %indvars.iv
+  %tmp = load i8* %arrayidx, align 1
+  %conv = sext i8 %tmp to i32
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %conv, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}