[polly][NFC] Compute WAR dependence info using ISL kills

[bin.narwal]

Summary

Hi,
When reading code of Dependences::calculateDependences, I noticed that WAR is computed specifically by
buildWAR. Given ISL now supports "kills" in approximate dataflow analysis, this patch takes advantage of it.
Though I don't know if it's intended not using the ISL "kills" functionality.

This patch also cleans up a couple lines redundant codes. Any comments?

Thanks,

[Meinersbur]

LGTM. Please add "NFC" to the title for "No Functional Change" intended.

Please add a message if/when I can commit this for you.

lib/Analysis/DependenceInfo.cpp

289–291 ↗

(On Diff #217137)

[nit] It would be nice to keep the union_map's together and have schedule as the last argument.

[bin.narwal]

Hi Michael, thanks for reviewing. I updated the diff according to your comments.
And yes, please help commit this for me.

Thanks,

[Meinersbur]

Very useful contribution. Thank you!

polly/trunk/lib/Analysis/DependenceInfo.cpp

void Dependences::addPrivatizationDependences() {
   }
 
   isl_union_set_free(Universe);
 }
 
 static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,
                                             __isl_keep isl_union_map *Src,
                                             __isl_keep isl_union_map *MaySrc,
+                                            __isl_keep isl_union_map *Kill,
                                             __isl_keep isl_schedule *Schedule) {
   isl_union_access_info *AI;
 
   AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));
   if (MaySrc)
     AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));
   if (Src)
     AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src));
+  if (Kill)
+    AI = isl_union_access_info_set_kill(AI, isl_union_map_copy(Kill));
   AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));
   auto Flow = isl_union_access_info_compute_flow(AI);
   LLVM_DEBUG(if (!Flow) dbgs()
                  << "last error: "
                  << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))
                  << '\n';);
   return Flow;
 }
 
-/// Compute exact WAR dependences
-/// We need exact WAR dependences. That is, if there are
-/// dependences of the form:
-/// must-W2 (sink) <- must-W1 (sink) <- R (source)
-/// We wish to generate *ONLY*:
-/// { R -> W1 },
-/// NOT:
-/// { R -> W2, R -> W1 }
-///
-/// However, in the case of may-writes, we do *not* wish to allow
-/// may-writes to block must-writes. This makes sense, since perhaps the
-/// may-write will not happen. In that case, the exact dependence will
-/// be the (read -> must-write).
-/// Example:
-/// must-W2 (sink) <- may-W1 (sink) <- R (source)
-/// We wish to generate:
-/// { R-> W1, R -> W2 }
-///
-/// We use the fact that may dependences are not allowed to flow
-/// through a must source. That way, reads will be stopped by intermediate
-/// must-writes.
-/// However, may-sources may not interfere with one another. Hence, reads
-/// will not block each other from generating dependences.
-///
-/// Write (Sink) <- MustWrite (Must-Source) <- Read (MaySource) is
-/// present, then the dependence
-///    { Write <- Read }
-/// is not tracked.
-///
-/// We would like to specify the Must-Write as kills, source as Read
-/// and sink as Write.
-/// ISL does not have the functionality currently to support "kills".
-/// Use the Must-Source as a way to specify "kills".
-/// The drawback is that we will have both
-///   { Write <- MustWrite, Write <- Read }
-///
-/// We need to filter this to track only { Write <- Read }.
-///
-/// Filtering { Write <- Read } from WAROverestimated:
-/// --------------------------------------------------
-/// isl_union_flow_get_full_may_dependence gives us dependences of the form
-///   WAROverestimated = { Read+MustWrite -> [Write -> MemoryAccess]}
-///
-///  We need to intersect the domain with Read to get only
-///  Read dependences.
-///    Read = { Read -> MemoryAccess }
-///
-///
-/// 1. Construct:
-///   WARMemAccesses = { Read+Write -> [Read+Write -> MemoryAccess] }
-/// This takes a Read+Write from WAROverestimated and maps it to the
-/// corresponding wrapped memory access from WAROverestimated.
-///
-/// 2. Apply WARMemAcesses to the domain of WAR Overestimated to give:
-///   WAR = { [Read+Write -> MemoryAccess] -> [Write -> MemoryAccess] }
-///
-/// WAR is in a state where we can intersect with Read, since they
-/// have the same structure.
-///
-/// 3. Intersect this with a wrapped Read. Read is wrapped
-/// to ensure the domains look the same.
-///   WAR = WAR \intersect (wrapped Read)
-///   WAR = { [Read -> MemoryAccesss] -> [Write -> MemoryAccess] }
-///
-///  4. Project out the memory access in the domain to get
-///  WAR = { Read -> Write }
-static isl_union_map *buildWAR(isl_union_map *Write, isl_union_map *MustWrite,
-                               isl_union_map *Read, isl_schedule *Schedule) {
-  isl_union_flow *Flow = buildFlow(Write, MustWrite, Read, Schedule);
-  auto *WAROverestimated = isl_union_flow_get_full_may_dependence(Flow);
-
-  // 1. Constructing WARMemAccesses
-  // WarMemAccesses = { Read+Write -> [Write -> MemAccess] }
-  // Range factor of range product
-  //     { Read+Write -> MemAcesss }
-  // Domain projection
-  //     { [Read+Write -> MemAccess] -> Read+Write }
-  // Reverse
-  //     { Read+Write -> [Read+Write -> MemAccess] }
-  auto WARMemAccesses =
-      isl_union_map_range_factor_range(isl_union_map_copy(WAROverestimated));
-  WARMemAccesses = isl_union_map_domain_map(WARMemAccesses);
-  WARMemAccesses = isl_union_map_reverse(WARMemAccesses);
-
-  // 2. Apply to get domain tagged with memory accesses
-  isl_union_map *WAR =
-      isl_union_map_apply_domain(WAROverestimated, WARMemAccesses);
-
-  // 3. Intersect with Read to extract only reads
-  auto ReadWrapped = isl_union_map_wrap(isl_union_map_copy(Read));
-  WAR = isl_union_map_intersect_domain(WAR, ReadWrapped);
-
-  // 4. Project out memory accesses to get usual style dependences
-  WAR = isl_union_map_range_factor_domain(WAR);
-  WAR = isl_union_map_domain_factor_domain(WAR);
-
-  isl_union_flow_free(Flow);
-  return WAR;
-}
-
 void Dependences::calculateDependences(Scop &S) {
   isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;
   isl_schedule *Schedule;
   isl_union_set *TaggedStmtDomain;
 
   LLVM_DEBUG(dbgs() << "Scop: \n" << S << "\n");
 
   collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,
isl_union_map *StrictWAW = nullptr;
     // Example:
     //     void f(int *sum, int A[N], int B[N]) {
     //       for (int i = 0; i < N; i++) {
     //         *sum += A[i]; < the store and the load is not tagged as a
     //         B[i] = *sum;  < reduction-like access due to the overlap.
     //       }
     //     }
 
-    isl_union_flow *Flow = buildFlow(Write, Write, Read, Schedule);
+    isl_union_flow *Flow = buildFlow(Write, Write, Read, nullptr, Schedule);
     StrictWAW = isl_union_flow_get_must_dependence(Flow);
     isl_union_flow_free(Flow);
 
     if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
-      Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
+      Flow = buildFlow(Read, MustWrite, MayWrite, nullptr, Schedule);
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
-      Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
+      Flow = buildFlow(Write, MustWrite, MayWrite, nullptr, Schedule);
       WAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
-      WAR = buildWAR(Write, MustWrite, Read, Schedule);
-      isl_union_map_free(Write);
-      isl_schedule_free(Schedule);
+      // ISL now supports "kills" in approximate dataflow analysis, we can
+      // specify the MustWrite as kills, Read as source and Write as sink.
+      Flow = buildFlow(Write, nullptr, Read, MustWrite, Schedule);
+      WAR = isl_union_flow_get_may_dependence(Flow);
+      isl_union_flow_free(Flow);
     } else {
-      isl_union_flow *Flow;
-
-      Flow = buildFlow(Read, nullptr, Write, Schedule);
+      Flow = buildFlow(Read, nullptr, Write, nullptr, Schedule);
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
-      Flow = buildFlow(Write, nullptr, Read, Schedule);
+      Flow = buildFlow(Write, nullptr, Read, nullptr, Schedule);
       WAR = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
-      Flow = buildFlow(Write, nullptr, Write, Schedule);
+      Flow = buildFlow(Write, nullptr, Write, nullptr, Schedule);
       WAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
-
-      isl_union_map_free(Write);
-      isl_schedule_free(Schedule);
     }
 
+    isl_union_map_free(Write);
     isl_union_map_free(MustWrite);
     isl_union_map_free(MayWrite);
     isl_union_map_free(Read);
+    isl_schedule_free(Schedule);
 
     RAW = isl_union_map_coalesce(RAW);
     WAW = isl_union_map_coalesce(WAW);
     WAR = isl_union_map_coalesce(WAR);
 
     // End of max_operations scope.
   }