[Polly] Allow mapping scalar MemoryAccesses to array elements.

[Meinersbur]

Summary

Change the code around setNewAccessRelation to allow to use a an existing array element for memory instead of an ad-hoc malloc. This facility will be used for DeLICM/DeGVN to convert scalar dependencies into regular ones.

The changes necessary include:

• Make the code generator use the implicit locations instead of the alloca ones.
• A test case
• Make the JScop importer accept changes of scalar accesses for that test case.
• Adapt the MemoryAccess interface to the fact that the MemoryKind can change. They are named (get|is)OriginalXXX() to get the status of the memory access before any change by setNewAccessRelation() (some properties such as getIncoming() do not change even if the kind is changed and are still required). To get the modified properties, there is (get|is)LatestXXX(). The old accessors without Original|Latest are synonyms of the (get|is)OriginalXXX() to not make functional changes in unrelated code.

[Meinersbur]

Since we can only change scalar accesses to array accesses (not the other way around), instead of the Original/Latest scheme I could also imagine the following accessors:

isArrayTarget()
getTargetScopArrayInfo()
getTargetBaseAddress()
getTargetAccessRelation()

that would always return the latest information, and keep the old ones.

[grosser]

Hi Michael,

very nice patch. Just one minor comment.

Best,
Tobias

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

1

Could you possibly also commit the original .jscop file. I tried to do this consistently to make it easy to see the changes by just calling 'diff' between the original and the transformed jscop file.

[Meinersbur]

Thank you for the review. Do you have any comment on the get(Original|Latest)XXX naming scheme? It is what I originally used, but it feels clunky. Ideally I'd distinguish between whether the access is explicit (caused by a MemInst)/implicit (cross-Stmt registers+PHIs) and what it accesses (array/scalar alloca).

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

1

OK. Didn't know the purpose of those files.

include/polly/CodeGen/BlockGenerators.h

protected:
   ///
   /// @returns The alloca for @p ScalarBase.
   Value *getOrCreateAlloca(Value *ScalarBase, ScalarAllocaMapTy &Map,
                            const char *NameExt);
 
   /// @brief Generate reload of scalars demoted to memory and needed by @p Stmt.
   ///
   /// @param Stmt  The statement we generate code for.
+  /// @param LTS   A mapping from loops virtual canonical induction
+  ///              variable to their new values.
   /// @param BBMap A mapping from old values to their new values in this block.
-  void generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap);
+  /// @param NewAccesses A map from memory access ids to new ast expressions.
+  void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT &LTS,
+                           ValueMapT &BBMap,
+                           __isl_keep isl_id_to_ast_expr *NewAccesses);
 
   /// @brief Generate the scalar stores for the given statement.
   ///
   /// After the statement @p Stmt was copied all inner-SCoP scalar dependences
   /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
   /// be demoted to memory.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction
   ///              variable to their new values
   ///              (for values recalculated in the new ScoP, but not
   ///               within this basic block)
   /// @param BBMap A mapping from old values to their new values in this block.
+  /// @param NewAccesses A map from memory access ids to new ast expressions.
   virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                    ValueMapT &BBMap);
+                                    ValueMapT &BBMap,
+                                    __isl_keep isl_id_to_ast_expr *NewAccesses);
 
   /// @brief Handle users of @p Inst outside the SCoP.
   ///
   /// @param S         The current SCoP.
   /// @param Inst      The current instruction we check.
   void handleOutsideUsers(const Scop &S, Instruction *Inst);
 
   /// @brief Find scalar statements that have outside users.
protected:
   /// @brief Generate the operand address
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                   ValueMapT &BBMap, LoopToScevMapT &LTS,
                                   isl_id_to_ast_expr *NewAccesses);
 
+  /// @brief Generate the operand address.
+  ///
+  /// @param Stmt         The statement to generate code for.
+  /// @param L            The innermost loop that surrounds the statement.
+  /// @param Pointer      If the access expression is not changed (ie. not found
+  ///                     in @p LTS), use this Pointer from the original code
+  ///                     instead.
+  /// @param BBMap        A mapping from old values to their new values.
+  /// @param LTS          A mapping from loops virtual canonical induction
+  ///                     variable to their new values.
+  /// @param NewAccesses  Ahead-of-time generated access expressions.
+  /// @param Id           Identifier of the MemoryAccess to generate.
+  /// @param ExpectedType The type the returned value should have.
+  ///
+  /// @return The generated address.
+  Value *generateLocationAccessed(ScopStmt &Stmt, Loop *L, Value *Pointer,
+                                  ValueMapT &BBMap, LoopToScevMapT &LTS,
+                                  isl_id_to_ast_expr *NewAccesses,
+                                  __isl_take isl_id *Id, Type *ExpectedType);
+
+  /// @brief Generate the pointer value that is accesses by @p Access.
+  ///
+  /// For write accesses, generate the target address. For read accesses,
+  /// generate the source address.
+  /// The access can be either an array access or a scalar access. In the first
+  /// case, the returned address will point to an element into that array. In
+  /// the scalar case, an alloca is used.
+  /// If a new AccessRelation is set for the MemoryAccess, the new relation will
+  /// be used.
+  ///
+  /// @param Access      The access to generate a pointer for.
+  /// @param L           The innermost loop that surrounds the statement.
+  /// @param LTS         A mapping from loops virtual canonical induction
+  ///                    variable to their new values.
+  /// @param BBMap       A mapping from old values to their new values.
+  /// @param NewAccesses A map from memory access ids to new ast expressions.
+  ///
+  /// @return The generated address.
+  Value *getImplicitAddress(MemoryAccess &Access, Loop *L, LoopToScevMapT &LTS,
+                            ValueMapT &BBMap,
+                            __isl_keep isl_id_to_ast_expr *NewAccesses);
+
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   Value *generateScalarLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap,
                             LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses);
 
   /// @param NewAccesses A map from memory access ids to new ast expressions,
private:
   /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
   /// be demoted to memory.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction variable to
   ///              their new values (for values recalculated in the new ScoP,
   ///              but not within this basic block)
   /// @param BBMap A mapping from old values to their new values in this block.
-  virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                    ValueMapT &BBMAp) override;
+  /// @param LTS   A mapping from loops virtual canonical induction variable to
+  /// their new values.
+  virtual void
+  generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMAp,
+                       __isl_keep isl_id_to_ast_expr *NewAccesses) override;
 
   /// @brief Copy a single PHI instruction.
   ///
   /// This copies a single PHI instruction and updates references to old values
   /// with references to new values, as defined by GlobalMap and BBMap.
   ///
   /// @param Stmt      The statement to code generate.
   /// @param PHI       The PHI instruction to copy.

include/polly/ScopInfo.h

public:
   int getElemSizeInBytes() const;
 
   /// @brief Get the name of this memory reference.
   std::string getName() const;
 
   /// @brief Return the isl id for the base pointer.
   __isl_give isl_id *getBasePtrId() const;
 
+  /// @brief Return what kind of memory this represents.
+  enum MemoryKind getKind() const { return Kind; }
+
   /// @brief Is this array info modeling an llvm::Value?
   bool isValueKind() const { return Kind == MK_Value; }
 
   /// @brief Is this array info modeling special PHI node memory?
   ///
   /// During code generation of PHI nodes, there is a need for two kinds of
   /// virtual storage. The normal one as it is used for all scalar dependences,
   /// where the result of the PHI node is stored and later loaded from as well
public:
   /// There are two possibilities:
   ///   1) The original access relation read from the LLVM-IR.
   ///   2) A new access relation imported from a json file or set by another
   ///      pass (e.g., for privatization).
   ///
   /// As 2) is by construction "newer" than 1) we return the new access
   /// relation if present.
   ///
-  __isl_give isl_map *getAccessRelation() const {
+  __isl_give isl_map *getLatestAccessRelation() const {
     return hasNewAccessRelation() ? getNewAccessRelation()
                                   : getOriginalAccessRelation();
   }
 
+  /// @brief Old name of getLatestAccessRelation().
+  __isl_give isl_map *getAccessRelation() const {
+    return getLatestAccessRelation();
+  }
+
   /// @brief Get an isl map describing the memory address accessed.
   ///
   /// In most cases the memory address accessed is well described by the access
   /// relation obtained with getAccessRelation. However, in case of arrays
   /// accessed with types of different size the access relation maps one access
   /// to multiple smaller address locations. This method returns an isl map that
   /// relates each dynamic statement instance to the unique memory location
   /// that is loaded from / stored to.
public:
   applyScheduleToAccessRelation(__isl_take isl_union_map *Schedule) const;
 
   /// @brief Get an isl string representing the access function read from IR.
   std::string getOriginalAccessRelationStr() const;
 
   /// @brief Get an isl string representing a new access function, if available.
   std::string getNewAccessRelationStr() 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 address of this access (e.g. A for A[i+j]) when
+  /// detected.
+  Value *getOriginalBaseAddr() const {
+    assert(!getOriginalScopArrayInfo() /* may noy yet be initialized */ ||
+           getOriginalScopArrayInfo()->getBasePtr() == BaseAddr);
+    return BaseAddr;
+  }
+
+  /// @brief Get the base address of this access (e.g. A for A[i+j]) after a
+  /// potential change by setNewAccessRelation().
+  Value *getLatestBaseAddr() const {
+    return getLatestScopArrayInfo()->getBasePtr();
+  }
+
+  /// @brief Old name for getOriginalBaseAddr().
+  Value *getBaseAddr() const { return getOriginalBaseAddr(); }
+
+  /// @brief Get the detection-time base array isl_id for this access.
+  __isl_give isl_id *getOriginalArrayId() const;
+
+  /// @brief Get the base array isl_id for this access, modifiable through
+  /// setNewAccessRelation().
+  __isl_give isl_id *getLatestArrayId() const;
 
-  /// @brief Get the base array isl_id for this access.
-  __isl_give isl_id *getArrayId() const;
+  /// @brief Old name of getOriginalArrayId().
+  __isl_give isl_id *getArrayId() const { return getOriginalArrayId(); }
 
-  /// @brief Get the ScopArrayInfo object for the base address.
-  const ScopArrayInfo *getScopArrayInfo() const;
+  /// @brief Get the detection-time ScopArrayInfo object for the base address.
+  const ScopArrayInfo *getOriginalScopArrayInfo() const;
+
+  /// @brief Get the ScopArrayInfo object for the base address, or the one set
+  /// by setNewAccessRelation().
+  const ScopArrayInfo *getLatestScopArrayInfo() const;
+
+  /// @brief Legacy name of getOriginalScopArrayInfo().
+  const ScopArrayInfo *getScopArrayInfo() const {
+    return getOriginalScopArrayInfo();
+  }
 
   /// @brief Return a string representation of the access'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; }
public:
   bool isStrideOne(__isl_take const isl_map *Schedule) const;
 
   /// Is always the same memory accessed for a given statement instance set?
   /// Schedule is a map from the statement to a schedule where the innermost
   /// dimension is the dimension of the innermost loop containing the
   /// statement.
   bool isStrideZero(__isl_take const isl_map *Schedule) const;
 
+  /// @brief Return the kind when this access was first detected.
+  ScopArrayInfo::MemoryKind getOriginalKind() const {
+    assert(!getOriginalScopArrayInfo() /* not yet initialized */ ||
+           getOriginalScopArrayInfo()->getKind() == Kind);
+    return Kind;
+  }
+
+  /// @brief Return the kind considering a potential setNewAccessRelation.
+  ScopArrayInfo::MemoryKind getLatestKind() const {
+    return getLatestScopArrayInfo()->getKind();
+  }
+
   /// @brief Whether this is an access of an explicit load or store in the IR.
-  bool isArrayKind() const { return Kind == ScopArrayInfo::MK_Array; }
+  bool isOriginalArrayKind() const {
+    return getOriginalKind() == ScopArrayInfo::MK_Array;
+  }
+
+  /// @brief Whether storage memory is either an custom .s2a/.phiops alloca
+  /// (false) or an existing pointer into an array (true).
+  bool isLatestArrayKind() const {
+    return getLatestKind() == ScopArrayInfo::MK_Array;
+  }
+
+  /// @brief Old name of isOriginalArrayKind.
+  bool isArrayKind() const { return isOriginalArrayKind(); }
 
-  /// @brief Whether this access is an array to a scalar memory object.
+  /// @brief Whether this access is an array to a scalar memory object, without
+  /// considering changes by setNewAccessRelation.
   ///
   /// Scalar accesses are accesses to MK_Value, MK_PHI or MK_ExitPHI.
-  bool isScalarKind() const { return !isArrayKind(); }
+  bool isOriginalScalarKind() const {
+    return getOriginalKind() != ScopArrayInfo::MK_Array;
+  }
 
-  /// @brief Is this MemoryAccess modeling scalar dependences?
-  bool isValueKind() const { return Kind == ScopArrayInfo::MK_Value; }
+  /// @brief Whether this access is an array to a scalar memory object, also
+  /// considering changes by setNewAccessRelation.
+  bool isLatestScalarKind() const {
+    return getLatestKind() != ScopArrayInfo::MK_Array;
+  }
 
-  /// @brief Is this MemoryAccess modeling special PHI node accesses?
-  bool isPHIKind() const { return Kind == ScopArrayInfo::MK_PHI; }
+  /// @brief Old name of isOriginalScalarKind.
+  bool isScalarKind() const { return isOriginalScalarKind(); }
 
-  /// @brief Is this MemoryAccess modeling the accesses of a PHI node in the
+  /// @brief Was this MemoryAccess detected as a scalar dependences?
+  bool isOriginalValueKind() const {
+    return getOriginalKind() == ScopArrayInfo::MK_Value;
+  }
+
+  /// @brief Is this MemoryAccess currently modeling scalar dependences?
+  bool isLatestValueKind() const {
+    return getLatestKind() == ScopArrayInfo::MK_Value;
+  }
+
+  /// @brief Old name of isOriginalValueKind().
+  bool isValueKind() const { return isOriginalValueKind(); }
+
+  /// @brief Was this MemoryAccess detected as a special PHI node access?
+  bool isOriginalPHIKind() const {
+    return getOriginalKind() == ScopArrayInfo::MK_PHI;
+  }
+
+  /// @brief Is this MemoryAccess modeling special PHI node accesses, also
+  /// considering a potential change by setNewAccessRelation?
+  bool isLatestPHIKind() const {
+    return getLatestKind() == ScopArrayInfo::MK_PHI;
+  }
+
+  /// @brief Old name of isOriginalPHIKind.
+  bool isPHIKind() const { return isOriginalPHIKind(); }
+
+  /// @brief Was this MemoryAccess detected as the accesses of a PHI node in the
   /// SCoP's exit block?
-  bool isExitPHIKind() const { return Kind == ScopArrayInfo::MK_ExitPHI; }
+  bool isOriginalExitPHIKind() const {
+    return getOriginalKind() == ScopArrayInfo::MK_ExitPHI;
+  }
+
+  /// @brief Is this MemoryAccess modeling the accesses of a PHI node in the
+  /// SCoP's exit block? Can be changed to an array access using
+  /// setNewAccessRelation().
+  bool isLatestExitPHIKind() const {
+    return getLatestKind() == ScopArrayInfo::MK_ExitPHI;
+  }
+
+  /// @brief Old name of isOriginalExitPHIKind().
+  bool isExitPHIKind() const { return isOriginalExitPHIKind(); }
+
+  /// @brief Was this access detected as one of the two PHI types?
+  bool isOriginalAnyPHIKind() const {
+    return isOriginalPHIKind() || isOriginalExitPHIKind();
+  }
+
+  /// @brief Does this access orginate from one of the two PHI types? Can be
+  /// changed to an array access using setNewAccessRelation().
+  bool isLatestAnyPHIKind() const {
+    return isLatestPHIKind() || isLatestExitPHIKind();
+  }
 
-  /// @brief Does this access orginate from one of the two PHI types?
-  bool isAnyPHIKind() const { return isPHIKind() || isExitPHIKind(); }
+  /// @brief Old name of isOriginalAnyPHIKind().
+  bool isAnyPHIKind() const { return isOriginalAnyPHIKind(); }
 
   /// @brief Get the statement that contains this memory access.
   ScopStmt *getStatement() const { return Statement; }
 
   /// @brief Get the reduction type of this access
   ReductionType getReductionType() const { return RedType; }
 
   /// @brief Set the updated access relation read from JSCOP file.

lib/Analysis/ScopInfo.cpp

 
 MemoryAccess::~MemoryAccess() {
   isl_id_free(Id);
   isl_set_free(InvalidDomain);
   isl_map_free(AccessRelation);
   isl_map_free(NewAccessRelation);
 }
 
-const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
+const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() 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_give isl_id *MemoryAccess::getArrayId() const {
+const ScopArrayInfo *MemoryAccess::getLatestScopArrayInfo() const {
+  isl_id *ArrayId = getLatestArrayId();
+  void *User = isl_id_get_user(ArrayId);
+  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
+  isl_id_free(ArrayId);
+  return SAI;
+}
+
+__isl_give isl_id *MemoryAccess::getOriginalArrayId() const {
   return isl_map_get_tuple_id(AccessRelation, isl_dim_out);
 }
 
+__isl_give isl_id *MemoryAccess::getLatestArrayId() const {
+  if (!hasNewAccessRelation())
+    return getOriginalArrayId();
+  return isl_map_get_tuple_id(NewAccessRelation, isl_dim_out);
+}
+
 __isl_give isl_map *MemoryAccess::getAddressFunction() const {
   return isl_map_lexmin(getAccessRelation());
 }
 
 __isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation(
     __isl_take isl_union_map *USchedule) const {
   isl_map *Schedule, *ScheduledAccRel;
   isl_union_set *UDomain;

lib/CodeGen/BlockGenerators.cpp

if (!NewInst->getType()->isVoidTy())
     NewInst->setName("p_" + Inst->getName());
 }
 
 Value *
 BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                          ValueMapT &BBMap, LoopToScevMapT &LTS,
                                          isl_id_to_ast_expr *NewAccesses) {
   const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
+  return generateLocationAccessed(
+      Stmt, getLoopForStmt(Stmt),
+      Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS,
+      NewAccesses, MA.getId(), MA.getAccessValue()->getType());
+}
 
-  isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId());
+Value *BlockGenerator::generateLocationAccessed(
+    ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
+    LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,
+    Type *ExpectedType) {
+  isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);
 
   if (AccessExpr) {
     AccessExpr = isl_ast_expr_address_of(AccessExpr);
     auto Address = ExprBuilder->create(AccessExpr);
 
     // Cast the address of this memory access to a pointer type that has the
     // same element type as the original access, but uses the address space of
     // the newly generated pointer.
-    auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo();
+    auto OldPtrTy = ExpectedType->getPointerTo();
     auto NewPtrTy = Address->getType();
     OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
                                 NewPtrTy->getPointerAddressSpace());
 
     if (OldPtrTy != NewPtrTy)
       Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
     return Address;
   }
+  assert(
+      Pointer &&
+      "If expression was not generated, must use the original pointer value");
+  return getNewValue(Stmt, Pointer, BBMap, LTS, L);
+}
 
-  return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
-                     getLoopForStmt(Stmt));
+Value *
+BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
+                                   LoopToScevMapT &LTS, ValueMapT &BBMap,
+                                   __isl_keep isl_id_to_ast_expr *NewAccesses) {
+  if (Access.isLatestArrayKind())
+    return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap,
+                                    LTS, NewAccesses, Access.getId(),
+                                    Access.getAccessValue()->getType());
+
+  if (Access.isLatestValueKind() || Access.isLatestExitPHIKind())
+    return getOrCreateScalarAlloca(Access.getBaseAddr());
+
+  if (Access.isLatestPHIKind())
+    return getOrCreatePHIAlloca(Access.getBaseAddr());
+
+  llvm_unreachable("Unknown access type");
 }
 
 Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
   auto *StmtBB = Stmt.getEntryBlock();
   return LI.getLoopFor(StmtBB);
 }
 
 Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
   return CopyBB;
 }
 
 BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
                                    ValueMapT &BBMap, LoopToScevMapT &LTS,
                                    isl_id_to_ast_expr *NewAccesses) {
   BasicBlock *CopyBB = splitBB(BB);
   Builder.SetInsertPoint(&CopyBB->front());
-  generateScalarLoads(Stmt, BBMap);
+  generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);
 
   copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
 
   // After a basic block was copied store all scalars that escape this block in
   // their alloca.
-  generateScalarStores(Stmt, LTS, BBMap);
+  generateScalarStores(Stmt, LTS, BBMap, NewAccesses);
   return CopyBB;
 }
 
 void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                             ValueMapT &BBMap, LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses) {
   EntryBB = &CopyBB->getParent()->getEntryBlock();
 
void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
 
   // Get or create an escape alloca for this instruction.
   auto *ScalarAddr = getOrCreateScalarAlloca(Inst);
 
   // Remember that this instruction has escape uses and the escape alloca.
   EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
 }
 
-void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
+void BlockGenerator::generateScalarLoads(
+    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isWrite())
+    if (MA->isOriginalArrayKind() || MA->isWrite())
       continue;
 
-    auto *Address = getOrCreateAlloca(*MA);
+    auto *Address =
+        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
     assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     BBMap[MA->getBaseAddr()] =
         Builder.CreateLoad(Address, Address->getName() + ".reload");
   }
 }
 
-void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                          ValueMapT &BBMap) {
+void BlockGenerator::generateScalarStores(
+    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
 
   assert(Stmt.isBlockStmt() && "Region statements need to use the "
                                "generateScalarStores() function in the "
                                "RegionGenerator");
 
   for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isRead())
+    if (MA->isOriginalArrayKind() || MA->isRead())
       continue;
 
     Value *Val = MA->getAccessValue();
     if (MA->isAnyPHIKind()) {
       assert(MA->getIncoming().size() >= 1 &&
              "Block statements have exactly one exiting block, or multiple but "
              "with same incoming block and value");
       assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
                          [&](std::pair<BasicBlock *, Value *> p) -> bool {
                            return p.first == Stmt.getBasicBlock();
                          }) &&
              "Incoming block must be statement's block");
       Val = MA->getIncoming()[0].second;
     }
-    auto *Address = getOrCreateAlloca(*MA);
+    auto Address =
+        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
 
     Val = getNewValue(Stmt, Val, BBMap, LTS, L);
     assert((!isa<Instruction>(Val) ||
             DT.dominates(cast<Instruction>(Val)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   // inputs.
   BasicBlock *EntryBB = R->getEntry();
   BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                        &*Builder.GetInsertPoint(), &DT, &LI);
   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
   Builder.SetInsertPoint(&EntryBBCopy->front());
 
   ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
-  generateScalarLoads(Stmt, EntryBBMap);
+  generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI))
       BlockMap[*PI] = EntryBBCopy;
 
   // Iterate over all blocks in the region in a breadth-first search.
   std::deque<BasicBlock *> Blocks;
   SmallPtrSet<BasicBlock *, 8> SeenBlocks;
for (BasicBlock *BB : SeenBlocks) {
 
     LTS[L] = SE.getUnknown(LoopPHI);
   }
 
   // Continue generating code in the exit block.
   Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
 
   // Write values visible to other statements.
-  generateScalarStores(Stmt, LTS, ValueMap);
+  generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp);
   BlockMap.clear();
   RegionMaps.clear();
   IncompletePHINodeMap.clear();
 }
 
 PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
                                        ValueMapT &BBMap, Loop *L) {
   ScopStmt *Stmt = MA->getStatement();
Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
   }
 
   // MK_Value accesses leaving the subregion must dominate the exit block; just
   // pass the copied value
   Value *OldVal = MA->getAccessValue();
   return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
 }
 
-void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                           ValueMapT &BBMap) {
+void RegionGenerator::generateScalarStores(
+    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   assert(Stmt.getRegion() &&
          "Block statements need to use the generateScalarStores() "
          "function in the BlockGenerator");
 
   for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isRead())
+    if (MA->isOriginalArrayKind() || MA->isRead())
       continue;
 
     Value *NewVal = getExitScalar(MA, LTS, BBMap);
-    Value *Address = getOrCreateAlloca(*MA);
+    Value *Address =
+        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
     assert((!isa<Instruction>(NewVal) ||
             DT.dominates(cast<Instruction>(NewVal)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");

lib/Exchange/JSONExporter.cpp

for (MemoryAccess *MA : Stmt) {
         errs() << "JScop file changes the number of parameter dimensions\n";
         isl_map_free(CurrentAccessMap);
         isl_map_free(NewAccessMap);
         return false;
       }
 
       isl_id *NewOutId;
 
-      if (MA->isArrayKind()) {
+      // If the NewAccessMap has zero dimensions, it is the scalar access; it
+      // must be the same as before.
+      // If it has at least one dimension, it's an array access; search for its
+      // ScopArrayInfo.
+      if (isl_map_dim(NewAccessMap, isl_dim_out) >= 1) {
         NewOutId = isl_map_get_tuple_id(NewAccessMap, isl_dim_out);
         auto *SAI = S.getArrayInfoByName(isl_id_get_name(NewOutId));
         isl_id *OutId = isl_map_get_tuple_id(CurrentAccessMap, isl_dim_out);
         auto *OutSAI = ScopArrayInfo::getFromId(OutId);
         if (!SAI || SAI->getElementType() != OutSAI->getElementType()) {
           errs() << "JScop file contains access function with undeclared "
                     "ScopArrayInfo\n";
           isl_map_free(CurrentAccessMap);
for (MemoryAccess *MA : Stmt) {
 
       if (MA->isArrayKind()) {
         // We keep the old alignment, thus we cannot allow accesses to memory
         // locations that were not accessed before if the alignment of the
         // access is not the default alignment.
         bool SpecialAlignment = true;
         if (LoadInst *LoadI = dyn_cast<LoadInst>(MA->getAccessInstruction())) {
           SpecialAlignment =
+              LoadI->getAlignment() &&
               DL.getABITypeAlignment(LoadI->getType()) != LoadI->getAlignment();
         } else if (StoreInst *StoreI =
                        dyn_cast<StoreInst>(MA->getAccessInstruction())) {
           SpecialAlignment =
+              StoreI->getAlignment() &&
               DL.getABITypeAlignment(StoreI->getValueOperand()->getType()) !=
                   StoreI->getAlignment();
         }
 
         if (SpecialAlignment) {
           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);

test/Isl/CodeGen/MemAccess/map_scalar_access.ll

+; RUN: opt %loadPolly -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-import-jscop -analyze          < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-import-jscop -polly-codegen -S < %s | FileCheck %s --check-prefix=CODEGEN
+
+define void @map_scalar_access(double* noalias nonnull %A) {
+entry:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %entry], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 1
+  br i1 %j.cmp, label %reduction.for, label %outer.exit
+
+
+    reduction.for:
+      %i = phi i32 [0, %outer.for], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %outer.for], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+    body:
+      %add = fadd double %phi, 4.2
+      br label %reduction.inc
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+
+; CHECK:          Arrays {
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:     }
+; CHECK:          Statements {
+; CHECK-NEXT:         Stmt_outer_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_outer_for[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_outer_for[i0] -> [i0, 0, 0, 0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_outer_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_outer_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_reduction_for[0, i1] : 0 <= i1 <= 4 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> [0, 1, i1, 0] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_body[0, i1] : 0 <= i1 <= 3 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> [0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_reduction_inc[0, i1] : 0 <= i1 <= 3 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> [0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_exit
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_reduction_exit[0] };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> [0, 2, 0, 0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[0] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK:      New access function '{ Stmt_outer_for[i0] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_reduction_for[i0, i1] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_reduction_for[i0, i1] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_body[i0, i1] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_body[i0, i1] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_reduction_exit[i0] -> MemRef_A[i0] }' detected in JSCOP file
+; CHECK-NEXT: New access function '{ Stmt_reduction_exit[i0] -> MemRef_A[i0] }' detected in JSCOP file
+
+; CODEGEN:      polly.stmt.outer.for:
+; CODEGEN-NEXT:   %polly.access.A[[R0:[0-9]*]] = getelementptr double, double* %A, i64 %polly.indvar
+; CODEGEN-NEXT:   store double 0.000000e+00, double* %polly.access.A[[R0]]
+; CODEGEN-NEXT:   br label %polly.cond
+
+; CODEGEN:      polly.stmt.reduction.exit:
+; CODEGEN-NEXT:   %polly.access.A[[R1:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   %polly.access.A[[R1]].reload = load double, double* %polly.access.A[[R1]]
+; CODEGEN-NEXT:   %polly.access.A[[R2:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   store double %polly.access.A[[R1]].reload, double* %polly.access.A[[R2]]
+; CODEGEN-NEXT:   br label %polly.merge
+
+; CODEGEN:      polly.stmt.reduction.for:
+; CODEGEN-NEXT:   %polly.access.A[[R3:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   %polly.access.A[[R3]].reload = load double, double* %polly.access.A[[R3]]
+; CODEGEN-NEXT:   %polly.access.A[[R4:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   store double %polly.access.A[[R3]].reload, double* %polly.access.A[[R4]]
+; CODEGEN-NEXT:   br label %polly.cond9
+
+; CODEGEN:      polly.stmt.body:
+; CODEGEN-NEXT:   %polly.access.A[[R5:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   %polly.access.A[[R5]].reload = load double, double* %polly.access.A[[R5]]
+; CODEGEN-NEXT:   %p_add = fadd double %polly.access.A13.reload, 4.200000e+00
+; CODEGEN-NEXT:   %polly.access.A[[R6:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   store double %p_add, double* %polly.access.A[[R6]]
+; CODEGEN-NEXT:   br label %polly.stmt.reduction.inc
+
+; CODEGEN:      polly.stmt.reduction.inc:
+; CODEGEN-NEXT:   %polly.access.A[[R7:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   %polly.access.A[[R7]].reload = load double, double* %polly.access.A[[R7]]
+; CODEGEN-NEXT:   %polly.access.A[[R8:[0-9]*]] = getelementptr double, double* %A, i64 0
+; CODEGEN-NEXT:   store double %polly.access.A[[R7]].reload, double* %polly.access.A[[R8]]
+; CODEGEN-NEXT:   br label %polly.merge10

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

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "type" : "double"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%outer.for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_outer_for[i0] -> MemRef_A[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_outer_for[i0] : 0 <= i0 <= 1 }",
+         "name" : "Stmt_outer_for",
+         "schedule" : "{ Stmt_outer_for[i0] -> [i0, 0, 0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_reduction_for[i0, i1] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_reduction_for[i0, i1] -> MemRef_A[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_reduction_for[0, i1] : 0 <= i1 <= 4 }",
+         "name" : "Stmt_reduction_for",
+         "schedule" : "{ Stmt_reduction_for[i0, i1] -> [0, 1, i1, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_body[i0, i1] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_body[i0, i1] -> MemRef_A[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_body[0, i1] : 0 <= i1 <= 3 }",
+         "name" : "Stmt_body",
+         "schedule" : "{ Stmt_body[i0, i1] -> [0, 1, i1, 1] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_reduction_inc[0, i1] : 0 <= i1 <= 3 }",
+         "name" : "Stmt_reduction_inc",
+         "schedule" : "{ Stmt_reduction_inc[i0, i1] -> [0, 1, i1, 2] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_reduction_exit[i0] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_reduction_exit[i0] -> MemRef_A[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_reduction_exit[0] }",
+         "name" : "Stmt_reduction_exit",
+         "schedule" : "{ Stmt_reduction_exit[i0] -> [0, 2, 0, 0] }"
+      }
+   ]
+}