diff options
| -rw-r--r-- | polly/include/polly/Support/ISLTools.h | 47 | ||||
| -rw-r--r-- | polly/lib/Support/ISLTools.cpp | 16 | ||||
| -rw-r--r-- | polly/unittests/Isl/IslTest.cpp | 53 |
3 files changed, 116 insertions, 0 deletions
diff --git a/polly/include/polly/Support/ISLTools.h b/polly/include/polly/Support/ISLTools.h index 57e32f31303..6253b9c33a6 100644 --- a/polly/include/polly/Support/ISLTools.h +++ b/polly/include/polly/Support/ISLTools.h @@ -299,6 +299,53 @@ IslPtr<isl_union_map> computeArrayUnused(IslPtr<isl_union_map> Schedule, bool ReadEltInSameInst, bool InclLastRead, bool InclWrite); +/// Convert a zone (range between timepoints) to timepoints. +/// +/// A zone represents the time between (integer) timepoints, but not the +/// timepoints themselves. This function can be used to determine whether a +/// timepoint lies within a zone. +/// +/// For instance, the range (1,3), representing the time between 1 and 3, is +/// represented by the zone +/// +/// { [i] : 1 < i <= 3 } +/// +/// The set of timepoints that lie completely within this range is +/// +/// { [i] : 1 < i < 3 } +/// +/// A typical use-case is the range in which a value written by a store is +/// available until it is overwritten by another value. If the write is at +/// timepoint 1 and its value is overwritten by another value at timepoint 3, +/// the value is available between those timepoints: timepoint 2 in this +/// example. +/// +/// +/// When InclStart is true, the range is interpreted left-inclusive, i.e. adds +/// the timepoint 1 to the result: +/// +/// { [i] : 1 <= i < 3 } +/// +/// In the use-case mentioned above that means that the value written at +/// timepoint 1 is already available in timepoint 1 (write takes place before +/// any read of it even if executed at the same timepoint) +/// +/// When InclEnd is true, the range is interpreted right-inclusive, i.e. adds +/// the timepoint 3 to the result: +/// +/// { [i] : 1 < i <= 3 } +/// +/// In the use-case mentioned above that means that although the value is +/// overwritten in timepoint 3, the old value is still available at timepoint 3 +/// (write takes place after any read even if executed at the same timepoint) +/// +/// @param Zone { Zone[] } +/// @param InclStart Include timepoints adjacent to the beginning of a zone. +/// @param InclEnd Include timepoints adjacent to the ending of a zone. +/// +/// @return { Scatter[] } +IslPtr<isl_union_set> convertZoneToTimepoints(IslPtr<isl_union_set> Zone, + bool InclStart, bool InclEnd); } // namespace polly #endif /* POLLY_ISLTOOLS_H */ diff --git a/polly/lib/Support/ISLTools.cpp b/polly/lib/Support/ISLTools.cpp index 499fd9217ec..4f1b49c0b52 100644 --- a/polly/lib/Support/ISLTools.cpp +++ b/polly/lib/Support/ISLTools.cpp @@ -367,3 +367,19 @@ IslPtr<isl_union_map> polly::computeArrayUnused(IslPtr<isl_union_map> Schedule, BeforeWritesBeforeAnyReads.take(), isl_union_map_domain_factor_domain(BetweenLastReadOverwrite.take()))); } + +IslPtr<isl_union_set> polly::convertZoneToTimepoints(IslPtr<isl_union_set> Zone, + bool InclStart, + bool InclEnd) { + if (!InclStart && InclEnd) + return Zone; + + auto ShiftedZone = shiftDim(Zone, -1, -1); + if (InclStart && !InclEnd) + return ShiftedZone; + else if (!InclStart && !InclEnd) + return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take())); + + assert(InclStart && InclEnd); + return give(isl_union_set_union(Zone.take(), ShiftedZone.take())); +} diff --git a/polly/unittests/Isl/IslTest.cpp b/polly/unittests/Isl/IslTest.cpp index 667045f296b..7d9a8b7ae54 100644 --- a/polly/unittests/Isl/IslTest.cpp +++ b/polly/unittests/Isl/IslTest.cpp @@ -807,4 +807,57 @@ TEST(DeLICM, computeArrayUnused) { UMAP("{ RW[] -> Elt[] }"), false, true, true)); } +TEST(DeLICM, convertZoneToTimepoints) { + std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), + &isl_ctx_free); + + // Corner case: empty set + EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false)); + EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false)); + EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true)); + EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true)); + + // Basic usage + EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false)); + EXPECT_EQ(USET("{ [0] }"), + convertZoneToTimepoints(USET("{ [1] }"), true, false)); + EXPECT_EQ(USET("{ [1] }"), + convertZoneToTimepoints(USET("{ [1] }"), false, true)); + EXPECT_EQ(USET("{ [0]; [1] }"), + convertZoneToTimepoints(USET("{ [1] }"), true, true)); + + // Non-adjacent ranges + EXPECT_EQ(USET("{}"), + convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false)); + EXPECT_EQ(USET("{ [0]; [10] }"), + convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false)); + EXPECT_EQ(USET("{ [1]; [11] }"), + convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true)); + EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"), + convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true)); + + // Adjacent unit ranges + EXPECT_EQ( + USET("{ [i] : 0 < i < 10 }"), + convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false)); + EXPECT_EQ( + USET("{ [i] : 0 <= i < 10 }"), + convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false)); + EXPECT_EQ( + USET("{ [i] : 0 < i <= 10 }"), + convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true)); + EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"), + convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true)); + + // More than one dimension + EXPECT_EQ(USET("{}"), + convertZoneToTimepoints(USET("{ [0,1] }"), false, false)); + EXPECT_EQ(USET("{ [0,0] }"), + convertZoneToTimepoints(USET("{ [0,1] }"), true, false)); + EXPECT_EQ(USET("{ [0,1] }"), + convertZoneToTimepoints(USET("{ [0,1] }"), false, true)); + EXPECT_EQ(USET("{ [0,0]; [0,1] }"), + convertZoneToTimepoints(USET("{ [0,1] }"), true, true)); +} + } // anonymous namespace |
