summaryrefslogtreecommitdiffstats
path: root/polly
diff options
context:
space:
mode:
Diffstat (limited to 'polly')
-rw-r--r--polly/include/polly/Support/ISLTools.h58
-rw-r--r--polly/lib/Support/ISLTools.cpp60
-rw-r--r--polly/unittests/Isl/IslTest.cpp104
3 files changed, 222 insertions, 0 deletions
diff --git a/polly/include/polly/Support/ISLTools.h b/polly/include/polly/Support/ISLTools.h
index f0fb8d9deac..0cce3cef2d8 100644
--- a/polly/include/polly/Support/ISLTools.h
+++ b/polly/include/polly/Support/ISLTools.h
@@ -175,6 +175,64 @@ void simplify(IslPtr<isl_map> &Map);
/// Simplify a union map inplace.
void simplify(IslPtr<isl_union_map> &UMap);
+/// Compute the reaching definition statement or the next overwrite for each
+/// definition of an array element.
+///
+/// The reaching definition of an array element at a specific timepoint is the
+/// statement instance that has written the current element's content.
+/// Alternatively, this function determines for each timepoint and element which
+/// write is going to overwrite an element at a future timepoint. This can be
+/// seen as "reaching definition in reverse" where definitions are found in the
+/// past.
+///
+/// For example:
+///
+/// Schedule := { Write[] -> [0]; Overwrite[] -> [10] }
+/// Defs := { Write[] -> A[5]; Overwrite[] -> A[5] }
+///
+/// If index 5 of array A is written at timepoint 0 and 10, the resulting
+/// reaching definitions are:
+///
+/// { [A[5] -> [i]] -> Write[] : 0 < i < 10;
+/// [A[5] -> [i]] -> Overwrite[] : 10 < i }
+///
+/// Between timepoint 0 (Write[]) and timepoint 10 (Overwrite[]), the
+/// content of A[5] is written by statement instance Write[] and after
+/// timepoint 10 by Overwrite[]. Values not defined in the map have no known
+/// definition. This includes the statement instance timepoints themselves,
+/// because reads at those timepoints could either read the old or the new
+/// value, defined only by the statement itself. But this can be changed by @p
+/// InclPrevDef and @p InclNextDef. InclPrevDef=false and InclNextDef=true
+/// returns a zone. Unless @p InclPrevDef and @p InclNextDef are both true,
+/// there is only one unique definition per element and timepoint.
+///
+/// @param Schedule { DomainWrite[] -> Scatter[] }
+/// Schedule of (at least) all array writes. Instances not in
+/// @p Writes are ignored.
+/// @param Writes { DomainWrite[] -> Element[] }
+/// Elements written to by the statement instances.
+/// @param Reverse If true, look for definitions in the future. That is,
+/// find the write that is overwrites the current value.
+/// @param InclPrevDef Include the definition's timepoint to the set of
+/// well-defined elements (any load at that timepoint happen
+/// at the writes). In the example, enabling this option adds
+/// {[A[5] -> [0]] -> Write[]; [A[5] -> [10]] -> Overwrite[]}
+/// to the result.
+/// @param InclNextDef Whether to assume that at the timepoint where an element
+/// is overwritten, it still contains the old value (any load
+/// at that timepoint would happen before the overwrite). In
+/// this example, enabling this adds
+/// { [A[] -> [10]] -> Write[] } to the result.
+///
+/// @return { [Element[] -> Scatter[]] -> DomainWrite[] }
+/// The reaching definitions or future overwrite as described above, or
+/// nullptr if either @p Schedule or @p Writes is nullptr, or the isl
+/// max operations count has exceeded.
+IslPtr<isl_union_map> computeReachingWrite(IslPtr<isl_union_map> Schedule,
+ IslPtr<isl_union_map> Writes,
+ bool Reverse, bool InclPrevDef,
+ bool InclNextDef);
+
} // namespace polly
#endif /* POLLY_ISLTOOLS_H */
diff --git a/polly/lib/Support/ISLTools.cpp b/polly/lib/Support/ISLTools.cpp
index c50580a0edc..37cb146e0af 100644
--- a/polly/lib/Support/ISLTools.cpp
+++ b/polly/lib/Support/ISLTools.cpp
@@ -260,3 +260,63 @@ void polly::simplify(IslPtr<isl_union_map> &UMap) {
UMap = give(isl_union_map_detect_equalities(UMap.take()));
UMap = give(isl_union_map_coalesce(UMap.take()));
}
+
+IslPtr<isl_union_map>
+polly::computeReachingWrite(IslPtr<isl_union_map> Schedule,
+ IslPtr<isl_union_map> Writes, bool Reverse,
+ bool InclPrevDef, bool InclNextDef) {
+
+ // { Scatter[] }
+ auto ScatterSpace = getScatterSpace(Schedule);
+
+ // { ScatterRead[] -> ScatterWrite[] }
+ IslPtr<isl_map> Relation;
+ if (Reverse)
+ Relation = give(InclPrevDef ? isl_map_lex_lt(ScatterSpace.take())
+ : isl_map_lex_le(ScatterSpace.take()));
+ else
+ Relation = give(InclNextDef ? isl_map_lex_gt(ScatterSpace.take())
+ : isl_map_lex_ge(ScatterSpace.take()));
+
+ // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
+ auto RelationMap = give(isl_map_reverse(isl_map_range_map(Relation.take())));
+
+ // { Element[] -> ScatterWrite[] }
+ auto WriteAction =
+ give(isl_union_map_apply_domain(Schedule.copy(), Writes.take()));
+
+ // { ScatterWrite[] -> Element[] }
+ auto WriteActionRev = give(isl_union_map_reverse(WriteAction.copy()));
+
+ // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
+ auto DefSchedRelation = give(isl_union_map_apply_domain(
+ isl_union_map_from_map(RelationMap.take()), WriteActionRev.take()));
+
+ // For each element, at every point in time, map to the times of previous
+ // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
+ auto ReachableWrites = give(isl_union_map_uncurry(DefSchedRelation.take()));
+ if (Reverse)
+ ReachableWrites = give(isl_union_map_lexmin(ReachableWrites.copy()));
+ else
+ ReachableWrites = give(isl_union_map_lexmax(ReachableWrites.copy()));
+
+ // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
+ auto SelfUse = give(isl_union_map_range_map(WriteAction.take()));
+
+ if (InclPrevDef && InclNextDef) {
+ // Add the Def itself to the solution.
+ ReachableWrites =
+ give(isl_union_map_union(ReachableWrites.take(), SelfUse.take()));
+ ReachableWrites = give(isl_union_map_coalesce(ReachableWrites.take()));
+ } else if (!InclPrevDef && !InclNextDef) {
+ // Remove Def itself from the solution.
+ ReachableWrites =
+ give(isl_union_map_subtract(ReachableWrites.take(), SelfUse.take()));
+ }
+
+ // { [Element[] -> ScatterRead[]] -> Domain[] }
+ auto ReachableWriteDomain = give(isl_union_map_apply_range(
+ ReachableWrites.take(), isl_union_map_reverse(Schedule.take())));
+
+ return ReachableWriteDomain;
+}
diff --git a/polly/unittests/Isl/IslTest.cpp b/polly/unittests/Isl/IslTest.cpp
index c1490929865..959415e95ec 100644
--- a/polly/unittests/Isl/IslTest.cpp
+++ b/polly/unittests/Isl/IslTest.cpp
@@ -637,4 +637,108 @@ TEST(ISLTools, shiftDim) {
EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
}
+TEST(DeLICM, computeReachingWrite) {
+ std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+ &isl_ctx_free);
+
+ // Basic usage
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), false, false,
+ false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), false, false,
+ true));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), false, true,
+ false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), false, true,
+ false));
+
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), true, false,
+ false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), true, false,
+ true));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), true, true,
+ false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
+ computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
+ UMAP("{ Dom[] -> Elt[] }"), true, true, true));
+
+ // Two writes
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> "
+ "Dom2[] : 10 < i }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ false, false, false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> "
+ "Dom2[] : 10 <= i }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ false, true, false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> "
+ "Dom2[] : 10 < i }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ false, false, true));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
+ "Dom2[] : 10 <= i }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ false, true, true));
+
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> "
+ "Dom1[] : i < 0 }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ true, false, false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> "
+ "Dom1[] : i < 0 }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ true, true, false));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> "
+ "Dom1[] : i <= 0 }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ true, false, true));
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
+ "Dom1[] : i <= 0 }"),
+ computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
+ UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
+ true, true, true));
+
+ // Domain in same space
+ EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> "
+ "Dom[2] : 10 < i }"),
+ computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"),
+ UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"),
+ false, false, true));
+
+ // Parametric
+ EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"),
+ computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"),
+ UMAP("{ Dom[] -> Elt[] }"), false, false,
+ false));
+
+ // More realistic example (from reduction_embedded.ll)
+ EXPECT_EQ(
+ UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] "
+ ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> "
+ "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"),
+ computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"),
+ UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false,
+ false, true));
+}
+
} // anonymous namespace
OpenPOWER on IntegriCloud