commit 1feddcb33ea08ecebb2931e23fbd1c06d958ae0a
author Karthika Devi C <quic_kartc@quicinc.com> Fri Dec 08 03:34:52 2023 +0530
committer Copybara-Service <copybara-worker@google.com> Thu Dec 07 14:05:30 2023 -0800
tree 07b6b647699db48eb9de06ae8dbc531bab0029b6
parent fc365592411a2972efc0c29433b41c42c2fd5996

[polly][NFC] Refactor reduction detection code for modularity (#72343)

This patch pulls out the memory checks from the base reduction detection
algorithm. This is the first one in the reduction patch series, to
reduce the difference in future patches.

GitOrigin-RevId: 7ddd3d776402f9cc7d5f13b5940ba38a285223c2

lib/Analysis/ScopBuilder.cpp

diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp
index c344138..0af0f69 100644
--- a/lib/Analysis/ScopBuilder.cpp
+++ b/lib/Analysis/ScopBuilder.cpp
@@ -2510,6 +2510,48 @@
   }
 }
 
+///  True if @p AllAccs intersects with @p MemAccs execpt @p LoadMA and @p
+///  StoreMA
+bool hasIntersectingAccesses(isl::set AllAccs, MemoryAccess *LoadMA,
+                             MemoryAccess *StoreMA, isl::set Domain,
+                             SmallVector<MemoryAccess *, 8> &MemAccs) {
+  bool HasIntersectingAccs = false;
+  for (MemoryAccess *MA : MemAccs) {
+    if (MA == LoadMA || MA == StoreMA)
+      continue;
+
+    isl::map AccRel = MA->getAccessRelation().intersect_domain(Domain);
+    isl::set Accs = AccRel.range();
+
+    if (AllAccs.has_equal_space(Accs)) {
+      isl::set OverlapAccs = Accs.intersect(AllAccs);
+      bool DoesIntersect = !OverlapAccs.is_empty();
+      HasIntersectingAccs |= DoesIntersect;
+    }
+  }
+  return HasIntersectingAccs;
+}
+
+///  Test if the accesses of @p LoadMA and @p StoreMA can form a reduction
+bool checkCandidatePairAccesses(MemoryAccess *LoadMA, MemoryAccess *StoreMA,
+                                isl::set Domain,
+                                SmallVector<MemoryAccess *, 8> &MemAccs) {
+  isl::map LoadAccs = LoadMA->getAccessRelation();
+  isl::map StoreAccs = StoreMA->getAccessRelation();
+
+  // Skip those with obviously unequal base addresses.
+  bool Valid = LoadAccs.has_equal_space(StoreAccs);
+
+  // And check if the remaining for overlap with other memory accesses.
+  if (Valid) {
+    isl::map AllAccsRel = LoadAccs.unite(StoreAccs);
+    AllAccsRel = AllAccsRel.intersect_domain(Domain);
+    isl::set AllAccs = AllAccsRel.range();
+    Valid = !hasIntersectingAccesses(AllAccs, LoadMA, StoreMA, Domain, MemAccs);
+  }
+  return Valid;
+}
+
 void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
   SmallVector<MemoryAccess *, 2> Loads;
   SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
@@ -2528,34 +2570,10 @@
 
   // Then check each possible candidate pair.
   for (const auto &CandidatePair : Candidates) {
-    bool Valid = true;
-    isl::map LoadAccs = CandidatePair.first->getAccessRelation();
-    isl::map StoreAccs = CandidatePair.second->getAccessRelation();
-
-    // Skip those with obviously unequal base addresses.
-    if (!LoadAccs.has_equal_space(StoreAccs)) {
-      continue;
-    }
-
-    // And check if the remaining for overlap with other memory accesses.
-    isl::map AllAccsRel = LoadAccs.unite(StoreAccs);
-    AllAccsRel = AllAccsRel.intersect_domain(Stmt.getDomain());
-    isl::set AllAccs = AllAccsRel.range();
-
-    for (MemoryAccess *MA : Stmt) {
-      if (MA == CandidatePair.first || MA == CandidatePair.second)
-        continue;
-
-      isl::map AccRel =
-          MA->getAccessRelation().intersect_domain(Stmt.getDomain());
-      isl::set Accs = AccRel.range();
-
-      if (AllAccs.has_equal_space(Accs)) {
-        isl::set OverlapAccs = Accs.intersect(AllAccs);
-        Valid = Valid && OverlapAccs.is_empty();
-      }
-    }
-
+    MemoryAccess *LoadMA = CandidatePair.first;
+    MemoryAccess *StoreMA = CandidatePair.second;
+    bool Valid = checkCandidatePairAccesses(LoadMA, StoreMA, Stmt.getDomain(),
+                                            Stmt.MemAccs);
     if (!Valid)
       continue;
 
@@ -2566,8 +2584,8 @@
 
     // If no overlapping access was found we mark the load and store as
     // reduction like.
-    CandidatePair.first->markAsReductionLike(RT);
-    CandidatePair.second->markAsReductionLike(RT);
+    LoadMA->markAsReductionLike(RT);
+    StoreMA->markAsReductionLike(RT);
   }
 }