1 //===- DeLICMTest.cpp ----------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "polly/DeLICM.h"
11 #include "gtest/gtest.h"
14 #include <isl/stream.h>
15 #include <isl/union_map.h>
16 #include <isl/union_set.h>
20 using namespace polly
;
24 /// Get the universes of all spaces in @p USet.
25 isl::union_set
unionSpace(const isl::union_set
&USet
) {
26 auto Result
= give(isl_union_set_empty(isl_union_set_get_space(USet
.keep())));
27 USet
.foreach_set([=, &Result
](isl::set Set
) -> isl::stat
{
28 auto Space
= give(isl_set_get_space(Set
.keep()));
29 auto Universe
= give(isl_set_universe(Space
.take()));
30 Result
= give(isl_union_set_add_set(Result
.take(), Universe
.take()));
36 void completeLifetime(isl::union_set Universe
, isl::union_map OccupiedAndKnown
,
37 isl::union_set
&Occupied
, isl::union_map
&Known
,
38 isl::union_set
&Undef
) {
39 auto ParamSpace
= give(isl_union_set_get_space(Universe
.keep()));
41 if (Undef
&& !Occupied
) {
43 Occupied
= give(isl_union_set_subtract(Universe
.copy(), Undef
.copy()));
46 if (OccupiedAndKnown
) {
49 Known
= isl::union_map::empty(ParamSpace
);
52 Occupied
= OccupiedAndKnown
.domain();
54 OccupiedAndKnown
.foreach_map([&Known
](isl::map Map
) -> isl::stat
{
55 if (isl_map_has_tuple_name(Map
.keep(), isl_dim_out
) != isl_bool_true
)
57 Known
= give(isl_union_map_add_map(Known
.take(), Map
.take()));
64 Undef
= give(isl_union_set_subtract(Universe
.copy(), Occupied
.copy()));
67 if (!Known
) { // By default, nothing is known.
68 Known
= isl::union_map::empty(ParamSpace
);
71 // Conditions that must hold when returning.
78 const char *OccupiedStr
;
80 const char *WrittenStr
;
83 isl::union_set
parseSetOrNull(isl_ctx
*Ctx
, const char *Str
) {
86 return isl::union_set(Ctx
, Str
);
89 isl::union_map
parseMapOrNull(isl_ctx
*Ctx
, const char *Str
) {
92 return isl::union_map(Ctx
, Str
);
95 bool checkIsConflictingNonsymmetricCommon(
96 isl_ctx
*Ctx
, isl::union_map ExistingOccupiedAndKnown
,
97 isl::union_set ExistingUnused
, isl::union_map ExistingWritten
,
98 isl::union_map ProposedOccupiedAndKnown
, isl::union_set ProposedUnused
,
99 isl::union_map ProposedWritten
) {
100 // Determine universe (set of all possible domains).
101 auto Universe
= give(isl_union_set_empty(isl_space_params_alloc(Ctx
, 0)));
102 if (ExistingOccupiedAndKnown
)
103 Universe
= give(isl_union_set_union(
104 Universe
.take(), ExistingOccupiedAndKnown
.domain().take()));
107 give(isl_union_set_union(Universe
.take(), ExistingUnused
.copy()));
110 isl_union_set_union(Universe
.take(), ExistingWritten
.domain().take()));
111 if (ProposedOccupiedAndKnown
)
112 Universe
= give(isl_union_set_union(
113 Universe
.take(), ProposedOccupiedAndKnown
.domain().take()));
116 give(isl_union_set_union(Universe
.take(), ProposedUnused
.copy()));
119 isl_union_set_union(Universe
.take(), ProposedWritten
.domain().take()));
121 Universe
= unionSpace(Universe
);
123 // Add a space the universe that does not occur anywhere else to ensure
124 // robustness. Use &NewId to ensure that this Id is unique.
125 isl::id NewId
= give(isl_id_alloc(Ctx
, "Unrelated", &NewId
));
126 // The space must contains at least one dimension to allow order
128 auto NewSpace
= give(isl_space_set_alloc(Ctx
, 0, 1));
130 give(isl_space_set_tuple_id(NewSpace
.take(), isl_dim_set
, NewId
.copy()));
131 auto NewSet
= give(isl_set_universe(NewSpace
.take()));
132 Universe
= give(isl_union_set_add_set(Universe
.take(), NewSet
.take()));
134 // Using the universe, fill missing data.
135 isl::union_set ExistingOccupied
;
136 isl::union_map ExistingKnown
;
137 completeLifetime(Universe
, ExistingOccupiedAndKnown
, ExistingOccupied
,
138 ExistingKnown
, ExistingUnused
);
140 isl::union_set ProposedOccupied
;
141 isl::union_map ProposedKnown
;
142 completeLifetime(Universe
, ProposedOccupiedAndKnown
, ProposedOccupied
,
143 ProposedKnown
, ProposedUnused
);
145 auto Result
= isConflicting(ExistingOccupied
, ExistingUnused
, ExistingKnown
,
146 ExistingWritten
, ProposedOccupied
, ProposedUnused
,
147 ProposedKnown
, ProposedWritten
);
149 // isConflicting does not require ExistingOccupied nor ProposedUnused and are
150 // implicitly assumed to be the remainder elements. Test the implicitness as
153 isConflicting(ExistingOccupied
, ExistingUnused
, ExistingKnown
,
154 ExistingWritten
, ProposedOccupied
, {}, ProposedKnown
,
157 isConflicting({}, ExistingUnused
, ExistingKnown
, ExistingWritten
,
158 ProposedOccupied
, ProposedUnused
, ProposedKnown
,
160 EXPECT_EQ(Result
, isConflicting({}, ExistingUnused
, ExistingKnown
,
161 ExistingWritten
, ProposedOccupied
, {},
162 ProposedKnown
, ProposedWritten
));
167 bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing
,
168 KnowledgeStr Proposed
) {
169 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
173 auto ExistingOccupiedAndKnown
=
174 parseMapOrNull(Ctx
.get(), Existing
.OccupiedStr
);
175 auto ExistingUnused
= parseSetOrNull(Ctx
.get(), Existing
.UndefStr
);
176 auto ExistingWritten
= parseMapOrNull(Ctx
.get(), Existing
.WrittenStr
);
178 auto ProposedOccupiedAndKnown
=
179 parseMapOrNull(Ctx
.get(), Proposed
.OccupiedStr
);
180 auto ProposedUnused
= parseSetOrNull(Ctx
.get(), Proposed
.UndefStr
);
181 auto ProposedWritten
= parseMapOrNull(Ctx
.get(), Proposed
.WrittenStr
);
183 return checkIsConflictingNonsymmetricCommon(
184 Ctx
.get(), ExistingOccupiedAndKnown
, ExistingUnused
, ExistingWritten
,
185 ProposedOccupiedAndKnown
, ProposedUnused
, ProposedWritten
);
188 bool checkIsConflictingNonsymmetric(KnowledgeStr Existing
,
189 KnowledgeStr Proposed
) {
190 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
194 auto ExistingOccupied
= parseSetOrNull(Ctx
.get(), Existing
.OccupiedStr
);
195 auto ExistingUnused
= parseSetOrNull(Ctx
.get(), Existing
.UndefStr
);
196 auto ExistingWritten
= parseSetOrNull(Ctx
.get(), Existing
.WrittenStr
);
198 auto ProposedOccupied
= parseSetOrNull(Ctx
.get(), Proposed
.OccupiedStr
);
199 auto ProposedUnused
= parseSetOrNull(Ctx
.get(), Proposed
.UndefStr
);
200 auto ProposedWritten
= parseSetOrNull(Ctx
.get(), Proposed
.WrittenStr
);
202 return checkIsConflictingNonsymmetricCommon(
204 isl::manage(isl_union_map_from_domain(ExistingOccupied
.take())),
206 isl::manage(isl_union_map_from_domain(ExistingWritten
.take())),
207 isl::manage(isl_union_map_from_domain(ProposedOccupied
.take())),
209 isl::manage(isl_union_map_from_domain(ProposedWritten
.take())));
212 bool checkIsConflicting(KnowledgeStr Existing
, KnowledgeStr Proposed
) {
213 auto Forward
= checkIsConflictingNonsymmetric(Existing
, Proposed
);
214 auto Backward
= checkIsConflictingNonsymmetric(Proposed
, Existing
);
216 // isConflicting should be symmetric.
217 EXPECT_EQ(Forward
, Backward
);
219 return Forward
|| Backward
;
222 bool checkIsConflictingKnown(KnowledgeStr Existing
, KnowledgeStr Proposed
) {
223 auto Forward
= checkIsConflictingNonsymmetricKnown(Existing
, Proposed
);
224 auto Backward
= checkIsConflictingNonsymmetricKnown(Proposed
, Existing
);
226 // checkIsConflictingKnown should be symmetric.
227 EXPECT_EQ(Forward
, Backward
);
229 return Forward
|| Backward
;
232 TEST(DeLICM
, isConflicting
) {
234 // Check occupied vs. occupied.
236 checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
237 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
238 {"{ Dom[i] }", nullptr, "{}"}));
239 EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
240 {nullptr, "{ Dom[0] }", "{}"}));
241 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
242 {"{ Dom[0] }", nullptr, "{}"}));
244 // Check occupied vs. written.
246 checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
248 checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
250 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
251 {"{}", nullptr, "{ Dom[0] }"}));
252 EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
253 {"{}", nullptr, "{ DomB[0] }"}));
255 // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
256 // 0 such that will have a different value between 0 and 1. Hence it is
257 // conflicting with Existing.
258 EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
259 {"{}", nullptr, "{ Dom[0] }"}));
260 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
261 {"{}", nullptr, "{ Dom[0] }"}));
263 // Check written vs. written.
264 EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
265 {"{}", nullptr, "{ Dom[0] }"}));
266 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
267 {"{}", nullptr, "{ Dom[0] }"}));
268 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
269 {"{}", nullptr, "{ Dom[0] }"}));
271 // Check written vs. written with known values.
272 EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
273 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
274 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
275 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
276 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
277 {"{}", nullptr, "{ Dom[0] -> [] }"}));
279 } // anonymous namespace