[Polly][DependenceInfo] Simplify creation and subsequent use of AccessSchedule

[bollu]

Summary

We only ever use the wrapped domain of AccessSchedule, so stop
creating an entire union_map and then pulling the domain out.

[grosser]

Dear Siddharth,

thanks for the patch. The changes itself look very good, however we should probably still update the comment above the lines you change. Also, it might sense to rename AccessSchedule to ReductionTagMap. After this patch, AccessSchedule does not contain any schedule any more.

Also:

• Please mark patches that do not change functionality with a '[NFC]' tag at the end of the title line.
• Add me also as a reviewer (the command I gave you did not add my own name)
• Add [Polly] at the beginning of the subject line, such that people know for which project this patch is for.

Please update the patch (use --update flag in arc). I will then go over it once more, and commit it if no other changes are needed.

[bollu]

Updating D30179: [Polly][DependenceInfo] Simplify creation and subsequent use of AccessSchedule

renamed AccessSchedule to ReductionTagMap, edited the comment in collectInfo to reflect what is happening after the change.

[grosser]

Good. Just one minor comment also needs updating.

Also please add '[NFC]' into the subject line of this change.

lib/Analysis/DependenceInfo.cpp

330–331

This comment still needs to be updated.

[bollu]

update comment that explained what ReductionTags does and how it is created.

[bollu]

collecting all diffs together into a patch.

lib/Analysis/DependenceInfo.cpp

static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA,
 
   // No need to tag at the statement level.
   return Relation;
 }
 
 /// Collect information about the SCoP @p S.
 static void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write,
                         isl_union_map **MayWrite,
-                        isl_union_map **AccessSchedule,
+                        isl_union_map **ReductionTagMap,
                         isl_union_map **StmtSchedule,
                         Dependences::AnalysisLevel Level) {
   isl_space *Space = S.getParamSpace();
   *Read = isl_union_map_empty(isl_space_copy(Space));
   *Write = isl_union_map_empty(isl_space_copy(Space));
   *MayWrite = isl_union_map_empty(isl_space_copy(Space));
-  *AccessSchedule = isl_union_map_empty(isl_space_copy(Space));
+  *ReductionTagMap = isl_union_map_empty(isl_space_copy(Space));
   *StmtSchedule = isl_union_map_empty(Space);
 
   SmallPtrSet<const ScopArrayInfo *, 8> ReductionArrays;
   if (UseReductions)
     for (ScopStmt &Stmt : S)
       for (MemoryAccess *MA : Stmt)
         if (MA->isReductionLike())
           ReductionArrays.insert(MA->getScopArrayInfo());
 
   for (ScopStmt &Stmt : S) {
     for (MemoryAccess *MA : Stmt) {
       isl_set *domcp = Stmt.getDomain();
       isl_map *accdom = MA->getAccessRelation();
 
       accdom = isl_map_intersect_domain(accdom, domcp);
 
       if (ReductionArrays.count(MA->getScopArrayInfo())) {
         // Wrap the access domain and adjust the schedule accordingly.
         //
         // An access domain like
         //   Stmt[i0, i1] -> MemAcc_A[i0 + i1]
         // will be transformed into
         //   [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1]
         //
-        // The original schedule looks like
-        //   Stmt[i0, i1] -> [0, i0, 2, i1, 0]
-        // but as we transformed the access domain we need the schedule
-        // to match the new access domains, thus we need
-        //   [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> [0, i0, 2, i1, 0]
-        isl_map *Schedule = Stmt.getSchedule();
-        assert(Schedule &&
-               "Schedules that contain extension nodes require special "
-               "handling.");
-        Schedule = isl_map_apply_domain(
-            Schedule,
-            isl_map_reverse(isl_map_domain_map(isl_map_copy(accdom))));
-        accdom = isl_map_range_map(accdom);
+        // We collect all the access domains in the ReductionTagMap.
+        // This is used in Dependences::calculateDependences to create
+        // a tagged Schedule tree.
 
-        *AccessSchedule = isl_union_map_add_map(*AccessSchedule, Schedule);
+        *ReductionTagMap = isl_union_map_add_map(*ReductionTagMap, isl_map_copy(accdom));
+        accdom = isl_map_range_map(accdom);
       } else {
         accdom = tag(accdom, MA, Level);
         if (Level > Dependences::AL_Statement) {
           auto *StmtScheduleMap = Stmt.getSchedule();
           assert(StmtScheduleMap &&
                  "Schedules that contain extension nodes require special "
                  "handling.");
           isl_map *Schedule = tag(StmtScheduleMap, MA, Level);
for (ScopStmt &Stmt : S) {
 
     if (!ReductionArrays.empty() && Level == Dependences::AL_Statement)
       *StmtSchedule = isl_union_map_add_map(*StmtSchedule, Stmt.getSchedule());
   }
 
   *StmtSchedule =
       isl_union_map_intersect_params(*StmtSchedule, S.getAssumedContext());
 
+  *ReductionTagMap = isl_union_map_coalesce(*ReductionTagMap);
   *Read = isl_union_map_coalesce(*Read);
   *Write = isl_union_map_coalesce(*Write);
   *MayWrite = isl_union_map_coalesce(*MayWrite);
 }
 
 /// Fix all dimension of @p Zero to 0 and add it to @p user
 static isl_stat fixSetToZero(__isl_take isl_set *Zero, void *user) {
   isl_union_set **User = (isl_union_set **)user;
static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,
   auto Flow = isl_union_access_info_compute_flow(AI);
   DEBUG(if (!Flow) dbgs() << "last error: "
                           << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))
                           << '\n';);
   return Flow;
 }
 
 void Dependences::calculateDependences(Scop &S) {
-  isl_union_map *Read, *Write, *MayWrite, *AccessSchedule, *StmtSchedule;
+  isl_union_map *Read, *Write, *MayWrite, *ReductionTagMap, *StmtSchedule;
   isl_schedule *Schedule;
 
   DEBUG(dbgs() << "Scop: \n" << S << "\n");
 
-  collectInfo(S, &Read, &Write, &MayWrite, &AccessSchedule, &StmtSchedule,
+  collectInfo(S, &Read, &Write, &MayWrite, &ReductionTagMap, &StmtSchedule,
               Level);
 
-  bool HasReductions = !isl_union_map_is_empty(AccessSchedule);
+  bool HasReductions = !isl_union_map_is_empty(ReductionTagMap);
 
   DEBUG(dbgs() << "Read: " << Read << '\n';
         dbgs() << "Write: " << Write << '\n';
         dbgs() << "MayWrite: " << MayWrite << '\n';
-        dbgs() << "AccessSchedule: " << AccessSchedule << '\n';
+        dbgs() << "ReductionTagMap: " << ReductionTagMap << '\n';
         dbgs() << "StmtSchedule: " << StmtSchedule << '\n';);
 
   Schedule = S.getScheduleTree();
 
   if (!HasReductions) {
-    isl_union_map_free(AccessSchedule);
+    isl_union_map_free(ReductionTagMap);
     // Tag the schedule tree if we want fine-grain dependence info
     if (Level > AL_Statement) {
       auto TaggedDom = isl_union_map_domain((isl_union_map_copy(StmtSchedule)));
       auto TaggedMap = isl_union_set_unwrap(TaggedDom);
       auto Tags = isl_union_map_domain_map_union_pw_multi_aff(TaggedMap);
       Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
     }
   } else {
-    isl_union_set *ReductionDom, *IdentityDom;
-    isl_union_map *ReductionMap, *IdentityMap;
+    isl_union_set *IdentityDom;
+    isl_union_map *IdentityMap;
     isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags;
 
-    // Extract reduction tags from the access schedule. The result is a map that
-    // maps each tagged element in the domain to the memory location it
+
+    // Extract Reduction tags from the combined access domains in the given SCoP.
+    // The result is a map that maps each tagged element in the domain to the memory location it
     // accesses.
-    //
     // ReductionTags = {[Stmt[i] -> Array[f(i)]] -> Stmt[i] }
-    ReductionDom = isl_union_map_domain((AccessSchedule));
-    ReductionMap = isl_union_set_unwrap(ReductionDom);
-    ReductionTags = isl_union_map_domain_map_union_pw_multi_aff(ReductionMap);
+    ReductionTags = isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap);
 
     // Compute an identity map from each statement in domain to itself.
     // IdentityTags = { [Stmt[i] -> Stmt[i] }
     IdentityDom = isl_union_map_domain(isl_union_map_copy(StmtSchedule));
     IdentityMap = isl_union_set_identity(IdentityDom);
     IdentityTags = isl_union_pw_multi_aff_from_union_map(IdentityMap);
 
     Tags = isl_union_pw_multi_aff_union_add(ReductionTags, IdentityTags);