[Support] Add computeArrayUnused. NFC.

This function has been extracted from the upcoming DeLICM patch
(https://reviews.llvm.org/D24716).

llvm-svn: 294093

3 files changed, 179 insertions, 0 deletions

diff --git a/polly/include/polly/Support/ISLTools.h b/polly/include/polly/Support/ISLTools.h
index 0cce3cef2d8..57e32f31303 100644
--- a/polly/include/polly/Support/ISLTools.h
+++ b/polly/include/polly/Support/ISLTools.h
@@ -233,6 +233,72 @@ IslPtr<isl_union_map> computeReachingWrite(IslPtr<isl_union_map> Schedule,
                                            bool Reverse, bool InclPrevDef,
                                            bool InclNextDef);
 
+/// Compute the timepoints where the contents of an array element are not used.
+///
+/// An element is unused at a timepoint when the element is overwritten in
+/// the future, but it is not read in between. Another way to express this: the
+/// time from when the element is written, to the most recent read before it, or
+/// infinitely into the past if there is no read before. Such unused elements
+/// can be overwritten by any value without changing the scop's semantics. An
+/// example:
+///
+/// Schedule := { Read[] -> [0]; Write[] -> [10]; Def[] -> [20] }
+/// Writes := { Write[] -> A[5]; Def[] -> A[6] }
+/// Reads := { Read[] -> A[5] }
+///
+/// The result is:
+///
+/// { A[5] -> [i] : 0 < i < 10;
+///   A[6] -> [i] : i < 20 }
+///
+/// That is, A[5] is unused between timepoint 0 (the read) and timepoint 10 (the
+/// write). A[6] is unused before timepoint 20, but might be used after the
+/// scop's execution (A[5] and any other A[i] as well). Use InclLastRead=false
+/// and InclWrite=true to interpret the result as zone.
+///
+/// @param Schedule          { Domain[] -> Scatter[] }
+///                          The schedule of (at least) all statement instances
+///                          occurring in @p Writes or @p Reads. All other
+///                          instances are ignored.
+/// @param Writes            { DomainWrite[] -> Element[] }
+///                          Elements written to by the statement instances.
+/// @param Reads             { DomainRead[] -> Element[] }
+///                          Elements read from by the statement instances.
+/// @param ReadEltInSameInst Whether a load reads the value from a write
+///                          that is scheduled at the same timepoint (Writes
+///                          happen before reads). Otherwise, loads use the
+///                          value of an element that it had before the
+///                          timepoint (Reads before writes). For example:
+///                          { Read[] -> [0]; Write[] -> [0] }
+///                          With ReadEltInSameInst=false it is assumed that the
+///                          read happens before the write, such that the
+///                          element is never unused, or just at timepoint 0,
+///                          depending on InclLastRead/InclWrite.
+///                          With ReadEltInSameInst=false it assumes that the
+///                          value just written is used. Anything before
+///                          timepoint 0 is considered unused.
+/// @param InclLastRead      Whether a timepoint where an element is last read
+///                          counts as unused (the read happens at the beginning
+///                          of its timepoint, and nothing (else) can use it
+///                          during the timepoint). In the example, this option
+///                          adds { A[5] -> [0] } to the result.
+/// @param InclWrite         Whether the timepoint where an element is written
+///                          itself counts as unused (the write happens at the
+///                          end of its timepoint; no (other) operations uses
+///                          the element during the timepoint). In this example,
+///                          this adds
+///                          { A[5] -> [10]; A[6] -> [20] } to the result.
+///
+/// @return { Element[] -> Scatter[] }
+///         The unused timepoints as defined above, or nullptr if either @p
+///         Schedule, @p Writes are @p Reads is nullptr, or the ISL max
+///         operations count is exceeded.
+IslPtr<isl_union_map> computeArrayUnused(IslPtr<isl_union_map> Schedule,
+                                         IslPtr<isl_union_map> Writes,
+                                         IslPtr<isl_union_map> Reads,
+                                         bool ReadEltInSameInst,
+                                         bool InclLastRead, bool InclWrite);
+
 } // namespace polly
 
 #endif /* POLLY_ISLTOOLS_H */
diff --git a/polly/lib/Support/ISLTools.cpp b/polly/lib/Support/ISLTools.cpp
index 37cb146e0af..499fd9217ec 100644
--- a/polly/lib/Support/ISLTools.cpp
+++ b/polly/lib/Support/ISLTools.cpp
@@ -320,3 +320,50 @@ polly::computeReachingWrite(IslPtr<isl_union_map> Schedule,
 
   return ReachableWriteDomain;
 }
+
+IslPtr<isl_union_map> polly::computeArrayUnused(IslPtr<isl_union_map> Schedule,
+                                                IslPtr<isl_union_map> Writes,
+                                                IslPtr<isl_union_map> Reads,
+                                                bool ReadEltInSameInst,
+                                                bool IncludeLastRead,
+                                                bool IncludeWrite) {
+  // { Element[] -> Scatter[] }
+  auto ReadActions =
+      give(isl_union_map_apply_domain(Schedule.copy(), Reads.take()));
+  auto WriteActions =
+      give(isl_union_map_apply_domain(Schedule.copy(), Writes.copy()));
+
+  // { [Element[] -> Scatter[] }
+  auto AfterReads = afterScatter(ReadActions, ReadEltInSameInst);
+  auto WritesBeforeAnyReads =
+      give(isl_union_map_subtract(WriteActions.take(), AfterReads.take()));
+  auto BeforeWritesBeforeAnyReads =
+      beforeScatter(WritesBeforeAnyReads, !IncludeWrite);
+
+  // { [Element[] -> DomainWrite[]] -> Scatter[] }
+  auto EltDomWrites = give(isl_union_map_apply_range(
+      isl_union_map_range_map(isl_union_map_reverse(Writes.copy())),
+      Schedule.copy()));
+
+  // { [Element[] -> Scatter[]] -> DomainWrite[] }
+  auto ReachingOverwrite = computeReachingWrite(
+      Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
+
+  // { [Element[] -> Scatter[]] -> DomainWrite[] }
+  auto ReadsOverwritten = give(isl_union_map_intersect_domain(
+      ReachingOverwrite.take(), isl_union_map_wrap(ReadActions.take())));
+
+  // { [Element[] -> DomainWrite[]] -> Scatter[] }
+  auto ReadsOverwrittenRotated = give(isl_union_map_reverse(
+      isl_union_map_curry(reverseDomain(ReadsOverwritten).take())));
+  auto LastOverwrittenRead =
+      give(isl_union_map_lexmax(ReadsOverwrittenRotated.take()));
+
+  // { [Element[] -> DomainWrite[]] -> Scatter[] }
+  auto BetweenLastReadOverwrite = betweenScatter(
+      LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
+
+  return give(isl_union_map_union(
+      BeforeWritesBeforeAnyReads.take(),
+      isl_union_map_domain_factor_domain(BetweenLastReadOverwrite.take())));
+}
diff --git a/polly/unittests/Isl/IslTest.cpp b/polly/unittests/Isl/IslTest.cpp
index 959415e95ec..667045f296b 100644
--- a/polly/unittests/Isl/IslTest.cpp
+++ b/polly/unittests/Isl/IslTest.cpp
@@ -741,4 +741,70 @@ TEST(DeLICM, computeReachingWrite) {
                            false, true));
 }
 
+TEST(DeLICM, computeArrayUnused) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // The ReadEltInSameInst parameter doesn't matter in simple cases. To also
+  // cover the parameter without duplicating the tests, this loops runs over
+  // other in both settings.
+  for (bool ReadEltInSameInst = false, Done = false; !Done;
+       Done = ReadEltInSameInst, ReadEltInSameInst = true) {
+    // Basic usage: one read, one write
+    EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"),
+              computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
+                                 UMAP("{ Write[] -> Elt[] }"),
+                                 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
+                                 false, false));
+    EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
+              computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
+                                 UMAP("{ Write[] -> Elt[] }"),
+                                 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
+                                 false, true));
+    EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"),
+              computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
+                                 UMAP("{ Write[] -> Elt[] }"),
+                                 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
+                                 true, false));
+    EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"),
+              computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
+                                 UMAP("{ Write[] -> Elt[] }"),
+                                 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
+                                 true, true));
+
+    // Two reads
+    EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
+              computeArrayUnused(
+                  UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"),
+                  UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"),
+                  ReadEltInSameInst, false, true));
+
+    // Corner case: no writes
+    EXPECT_EQ(UMAP("{}"),
+              computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"),
+                                 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
+                                 false, false));
+
+    // Corner case: no reads
+    EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
+              computeArrayUnused(UMAP("{ Write[] -> [0] }"),
+                                 UMAP("{ Write[] -> Elt[] }"), UMAP("{}"),
+                                 ReadEltInSameInst, false, true));
+  }
+
+  // Read and write in same statement
+  EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"),
+            computeArrayUnused(UMAP("{ RW[] -> [0] }"),
+                               UMAP("{ RW[] -> Elt[] }"),
+                               UMAP("{ RW[] -> Elt[] }"), true, false, false));
+  EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
+            computeArrayUnused(UMAP("{ RW[] -> [0] }"),
+                               UMAP("{ RW[] -> Elt[] }"),
+                               UMAP("{ RW[] -> Elt[] }"), true, false, true));
+  EXPECT_EQ(UMAP("{ Elt[] -> [0] }"),
+            computeArrayUnused(UMAP("{ RW[] -> [0] }"),
+                               UMAP("{ RW[] -> Elt[] }"),
+                               UMAP("{ RW[] -> Elt[] }"), false, true, true));
+}
+
 } // anonymous namespace