[Polly][Refactor][NFC] Simplify and clean the handling of (new) access relations

[dpeixott]

include/polly/ScopInfo.h

245 ↗

(On Diff #14663)

Does these two methods need to be public? If not it would be good to make them private to avoid confusion over which method to call (e.g. getAccessRelation, getNewAccessRelation, getNewestAccessRelation). I'm not too familiar with the API, so do whatever makes sense.

Otherwise, LGTM.

[jdoerfert]

include/polly/ScopInfo.h

245 ↗

(On Diff #14663)

I will expose getNewestAccessRelation and replace all uses (only in 2 files outside the ScopInfo itself, at the moment).

I cannot see any reason not to use the newest access function except in the dependence analysi but the importer runs after that pass and nobody else (at least for now) uses the functionality of a new access relation anyway.

Thanks!

[grosser]

include/polly/ScopInfo.h

245 ↗

(On Diff #14663)

I agree the three function names are rather confusing. What about just having getOriginalAccessRelation() and getAccessRelation(), with the last implementing what getNewestAccessRelation currently does?

In general all places in Polly should use the newest access relation which becomes the normal access relation. So even the introduction of getNewAccessRelation was probably a bad idea.

lib/Analysis/ScopInfo.cpp

410 ↗

(On Diff #14663)

I am not sure if pulling this into the MemoryAccess is an improvement. This is a rather complicated sequence of operations that is rather specific to the subsequent use in isl_ast_build_access_from_pw_multi_aff(). As getNewAccessOperand() is rather short and we use this sequence only once, I would suggest to leave the code as it is.

633 ↗

(On Diff #14663)

Having here getAccessRelation() (with the same semantics as now getNewestAccessRelation) seems more understandable. Updates to the access relation should not really affect the code all over polly.

lib/CodeGen/BlockGenerators.cpp

192 ↗

(On Diff #14663)

Nice.

[jdoerfert]

include/polly/ScopInfo.h

245 ↗

(On Diff #14663)

I will do that.

lib/Analysis/ScopInfo.cpp

410 ↗

(On Diff #14663)

Can I leave it here if my next patch uses it? [When I store back the aggregated privatized value I need to access the memory location in the new schedule].

633 ↗

(On Diff #14663)

Do you want getAccessRelation or getOriginalAccessRelation (wrt. your comment above)

[jdoerfert]

Closed by commit rL219612 (authored by @jdoerfert).

polly/trunk/include/polly/ScopInfo.h

private:
   /// @brief The access instruction of this memory access.
   Instruction *Inst;
 
   /// Updated access relation read from JSCOP file.
   isl_map *newAccessRelation;
 
   void assumeNoOutOfBound(const IRAccess &Access);
 
+  /// @brief Get the original access function as read from IR.
+  isl_map *getOriginalAccessRelation() const;
+
+  /// @brief Return the space in which the access relation lives in.
+  __isl_give isl_space *getOriginalAccessRelationSpace() const;
+
+  /// @brief Get the new access function imported or set by a pass
+  isl_map *getNewAccessRelation() const;
+
 public:
   /// @brief Create a memory access from an access in LLVM-IR.
   ///
   /// @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,
public:
   bool isMustWrite() const { return AccType == MemoryAccess::MUST_WRITE; }
 
   /// @brief Is this a may-write memory access?
   bool isMayWrite() const { return AccType == MemoryAccess::MAY_WRITE; }
 
   /// @brief Is this a write memory access?
   bool isWrite() const { return isMustWrite() || isMayWrite(); }
 
-  isl_map *getAccessRelation() const;
+  /// @brief Check if a new access relation was imported or set by a pass.
+  bool hasNewAccessRelation() const { return newAccessRelation; }
 
-  /// @brief Return the space in which the access relation lives in.
-  __isl_give isl_space *getAccessRelationSpace() const;
+  /// @brief Return the newest access relation of this access.
+  ///
+  /// 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_map *getAccessRelation() const {
+    return hasNewAccessRelation() ? getNewAccessRelation()
+                                  : getOriginalAccessRelation();
+  }
 
-  /// @brief Get an isl string representing this access function.
-  std::string getAccessRelationStr() const;
+  /// @brief Return the access relation after the schedule was applied.
+  __isl_give isl_pw_multi_aff *
+  applyScheduleToAccessRelation(__isl_keep isl_union_map *Schedule) const;
+
+  /// @brief Get an isl string representing the access function read from IR.
+  std::string getOriginalAccessRelationStr() 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; }
 
   /// @brief Return the access instruction of this memory access.
   Instruction *getAccessInstruction() const { return Inst; }
 
-  /// @brief Get the new access function imported from JSCOP file
-  isl_map *getNewAccessRelation() const;
-
   /// Get the stride of this memory access in the specified Schedule. Schedule
   /// is a map from the statement to a schedule where the innermost dimension is
   /// the dimension of the innermost loop containing the statement.
   isl_set *getStride(__isl_take const isl_map *Schedule) const;
 
   /// Is the stride of the access equal to a certain width? Schedule is a map
   /// from the statement to a schedule where the innermost dimension is the
   /// dimension of the innermost loop containing the statement.

polly/trunk/lib/Analysis/ScopInfo.cpp

const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
   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 {
+isl_pw_multi_aff *
+MemoryAccess::applyScheduleToAccessRelation(isl_union_map *USchedule) const {
+  isl_map *Schedule, *ScheduledAccRel;
+  isl_union_set *UDomain;
+
+  UDomain = isl_union_set_from_set(getStatement()->getDomain());
+  USchedule = isl_union_map_intersect_domain(USchedule, UDomain);
+  Schedule = isl_map_from_union_map(USchedule);
+  ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule);
+  return isl_pw_multi_aff_from_map(ScheduledAccRel);
+}
+
+isl_map *MemoryAccess::getOriginalAccessRelation() const {
   return isl_map_copy(AccessRelation);
 }
 
-std::string MemoryAccess::getAccessRelationStr() const {
+std::string MemoryAccess::getOriginalAccessRelationStr() const {
   return stringFromIslObj(AccessRelation);
 }
 
-__isl_give isl_space *MemoryAccess::getAccessRelationSpace() const {
+__isl_give isl_space *MemoryAccess::getOriginalAccessRelationSpace() const {
   return isl_map_get_space(AccessRelation);
 }
 
 isl_map *MemoryAccess::getNewAccessRelation() const {
   return isl_map_copy(newAccessRelation);
 }
 
 isl_basic_map *MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {

 // may contain invalid accesses and reduce this set of iterations to the ones
 // that are actually executed by intersecting them with the domain of the
 // 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(const IRAccess &Access) {
-  isl_space *Space = isl_space_range(getAccessRelationSpace());
+  isl_space *Space = isl_space_range(getOriginalAccessRelationSpace());
   isl_set *Outside = isl_set_empty(isl_space_copy(Space));
   for (int i = 1, Size = Access.Subscripts.size(); i < Size; ++i) {
     isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space));
     isl_pw_aff *Var =
         isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i);
     isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS);
 
     isl_set *DimOutside;
void MemoryAccess::print(raw_ostream &OS) const {
   case MUST_WRITE:
     OS.indent(12) << "MustWriteAccess :=\t";
     break;
   case MAY_WRITE:
     OS.indent(12) << "MayWriteAccess :=\t";
     break;
   }
   OS << "[Reduction Type: " << getReductionType() << "]\n";
-  OS.indent(16) << getAccessRelationStr() << ";\n";
+  OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
 }
 
 void MemoryAccess::dump() const { print(errs()); }
 
 // Create a map in the size of the provided set domain, that maps from the
 // one element of the provided set domain to another element of the provided
 // set domain.
 // The mapping is limited to all points that are equal in all but the last
static isl_map *getEqualAndLarger(isl_space *setDomain) {
   Map = isl_map_add_constraint(Map, c);
 
   isl_local_space_free(MapLocalSpace);
   return Map;
 }
 
 isl_set *MemoryAccess::getStride(__isl_take const isl_map *Schedule) const {
   isl_map *S = const_cast<isl_map *>(Schedule);
-  isl_map *AccessRelation = getNewAccessRelation();
-  if (!AccessRelation)
-    AccessRelation = getAccessRelation();
+  isl_map *AccessRelation = getAccessRelation();
   isl_space *Space = isl_space_range(isl_map_get_space(S));
   isl_map *NextScatt = getEqualAndLarger(Space);
 
   S = isl_map_reverse(S);
   NextScatt = isl_map_lexmin(NextScatt);
 
   NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(S));
   NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(AccessRelation));

polly/trunk/lib/CodeGen/BlockGenerators.cpp

void BlockGenerator::copyInstScalar(const Instruction *Inst, ValueMapT &BBMap,
   Builder.Insert(NewInst);
   BBMap[Inst] = NewInst;
 
   if (!NewInst->getType()->isVoidTy())
     NewInst->setName("p_" + Inst->getName());
 }
 
 Value *BlockGenerator::getNewAccessOperand(const MemoryAccess &MA) {
-  isl_pw_multi_aff *PWSchedule, *PWAccRel;
-  isl_union_map *ScheduleU;
-  isl_map *Schedule, *AccRel;
+  isl_pw_multi_aff *PWAccRel;
+  isl_union_map *Schedule;
   isl_ast_expr *Expr;
 
   assert(ExprBuilder && Build &&
          "Cannot generate new value without IslExprBuilder!");
 
-  AccRel = MA.getNewAccessRelation();
-  assert(AccRel && "We generate new code only for new access relations!");
-
-  ScheduleU = isl_ast_build_get_schedule(Build);
-  ScheduleU = isl_union_map_intersect_domain(
-      ScheduleU, isl_union_set_from_set(MA.getStatement()->getDomain()));
-  Schedule = isl_map_from_union_map(ScheduleU);
-
-  PWSchedule = isl_pw_multi_aff_from_map(isl_map_reverse(Schedule));
-  PWAccRel = isl_pw_multi_aff_from_map(AccRel);
-  PWAccRel = isl_pw_multi_aff_pullback_pw_multi_aff(PWAccRel, PWSchedule);
+  Schedule = isl_ast_build_get_schedule(Build);
+  PWAccRel = MA.applyScheduleToAccessRelation(Schedule);
 
   Expr = isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
   Expr = isl_ast_expr_address_of(Expr);
 
   return ExprBuilder->create(Expr);
 }
 
 Value *BlockGenerator::generateLocationAccessed(const Instruction *Inst,
                                                 const Value *Pointer,
                                                 ValueMapT &BBMap,
                                                 ValueMapT &GlobalMap,
                                                 LoopToScevMapT &LTS) {
   const MemoryAccess &MA = Statement.getAccessFor(Inst);
-  isl_map *NewAccRel = MA.getNewAccessRelation();
 
   Value *NewPointer;
-  if (NewAccRel)
+  if (MA.hasNewAccessRelation())
     NewPointer = getNewAccessOperand(MA);
   else
     NewPointer =
         getNewValue(Pointer, BBMap, GlobalMap, LTS, getLoopForInst(Inst));
 
-  isl_map_free(NewAccRel);
   return NewPointer;
 }
 
 Loop *BlockGenerator::getLoopForInst(const llvm::Instruction *Inst) {
   return LI.getLoopFor(Inst->getParent());
 }
 
 Value *BlockGenerator::generateScalarLoad(const LoadInst *Load,

polly/trunk/lib/Exchange/JSONExporter.cpp

for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI) {
     statement["domain"] = Stmt->getDomainStr();
     statement["schedule"] = Stmt->getScatteringStr();
     statement["accesses"];
 
     for (MemoryAccess *MA : *Stmt) {
       Json::Value access;
 
       access["kind"] = MA->isRead() ? "read" : "write";
-      access["relation"] = MA->getAccessRelationStr();
+      access["relation"] = MA->getOriginalAccessRelationStr();
 
       statement["accesses"].append(access);
     }
 
     root["statements"].append(statement);
   }
 
   return root;