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
= isl::union_set::empty(USet
.get_space());
27 USet
.foreach_set([=, &Result
](isl::set Set
) -> isl::stat
{
28 auto Space
= Set
.get_space();
29 auto Universe
= isl::set::universe(Space
);
30 Result
= Result
.add_set(Universe
);
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
= Universe
.get_space();
41 if (Undef
&& !Occupied
) {
43 Occupied
= Universe
.subtract(Undef
);
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 (!Map
.has_tuple_name(isl::dim::out
))
57 Known
= Known
.add_map(Map
);
64 Undef
= Universe
.subtract(Occupied
);
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
= isl::union_set::empty(isl::space::params_alloc(Ctx
, 0));
102 if (ExistingOccupiedAndKnown
)
103 Universe
= Universe
.unite(ExistingOccupiedAndKnown
.domain());
105 Universe
= Universe
.unite(ExistingUnused
);
107 Universe
= Universe
.unite(ExistingWritten
.domain());
108 if (ProposedOccupiedAndKnown
)
109 Universe
= Universe
.unite(ProposedOccupiedAndKnown
.domain());
111 Universe
= Universe
.unite(ProposedUnused
);
113 Universe
= Universe
.unite(ProposedWritten
.domain());
115 Universe
= unionSpace(Universe
);
117 // Add a space the universe that does not occur anywhere else to ensure
118 // robustness. Use &NewId to ensure that this Id is unique.
119 isl::id NewId
= isl::id::alloc(Ctx
, "Unrelated", &NewId
);
120 // The space must contains at least one dimension to allow order
122 auto NewSpace
= isl::space(Ctx
, 0, 1);
123 NewSpace
= NewSpace
.set_tuple_id(isl::dim::set
, NewId
);
124 auto NewSet
= isl::set::universe(NewSpace
);
125 Universe
= Universe
.add_set(NewSet
);
127 // Using the universe, fill missing data.
128 isl::union_set ExistingOccupied
;
129 isl::union_map ExistingKnown
;
130 completeLifetime(Universe
, ExistingOccupiedAndKnown
, ExistingOccupied
,
131 ExistingKnown
, ExistingUnused
);
133 isl::union_set ProposedOccupied
;
134 isl::union_map ProposedKnown
;
135 completeLifetime(Universe
, ProposedOccupiedAndKnown
, ProposedOccupied
,
136 ProposedKnown
, ProposedUnused
);
138 auto Result
= isConflicting(ExistingOccupied
, ExistingUnused
, ExistingKnown
,
139 ExistingWritten
, ProposedOccupied
, ProposedUnused
,
140 ProposedKnown
, ProposedWritten
);
142 // isConflicting does not require ExistingOccupied nor ProposedUnused and are
143 // implicitly assumed to be the remainder elements. Test the implicitness as
146 isConflicting(ExistingOccupied
, ExistingUnused
, ExistingKnown
,
147 ExistingWritten
, ProposedOccupied
, {}, ProposedKnown
,
150 isConflicting({}, ExistingUnused
, ExistingKnown
, ExistingWritten
,
151 ProposedOccupied
, ProposedUnused
, ProposedKnown
,
153 EXPECT_EQ(Result
, isConflicting({}, ExistingUnused
, ExistingKnown
,
154 ExistingWritten
, ProposedOccupied
, {},
155 ProposedKnown
, ProposedWritten
));
160 bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing
,
161 KnowledgeStr Proposed
) {
162 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
166 auto ExistingOccupiedAndKnown
=
167 parseMapOrNull(Ctx
.get(), Existing
.OccupiedStr
);
168 auto ExistingUnused
= parseSetOrNull(Ctx
.get(), Existing
.UndefStr
);
169 auto ExistingWritten
= parseMapOrNull(Ctx
.get(), Existing
.WrittenStr
);
171 auto ProposedOccupiedAndKnown
=
172 parseMapOrNull(Ctx
.get(), Proposed
.OccupiedStr
);
173 auto ProposedUnused
= parseSetOrNull(Ctx
.get(), Proposed
.UndefStr
);
174 auto ProposedWritten
= parseMapOrNull(Ctx
.get(), Proposed
.WrittenStr
);
176 return checkIsConflictingNonsymmetricCommon(
177 Ctx
.get(), ExistingOccupiedAndKnown
, ExistingUnused
, ExistingWritten
,
178 ProposedOccupiedAndKnown
, ProposedUnused
, ProposedWritten
);
181 bool checkIsConflictingNonsymmetric(KnowledgeStr Existing
,
182 KnowledgeStr Proposed
) {
183 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
187 auto ExistingOccupied
= parseSetOrNull(Ctx
.get(), Existing
.OccupiedStr
);
188 auto ExistingUnused
= parseSetOrNull(Ctx
.get(), Existing
.UndefStr
);
189 auto ExistingWritten
= parseSetOrNull(Ctx
.get(), Existing
.WrittenStr
);
191 auto ProposedOccupied
= parseSetOrNull(Ctx
.get(), Proposed
.OccupiedStr
);
192 auto ProposedUnused
= parseSetOrNull(Ctx
.get(), Proposed
.UndefStr
);
193 auto ProposedWritten
= parseSetOrNull(Ctx
.get(), Proposed
.WrittenStr
);
195 return checkIsConflictingNonsymmetricCommon(
196 Ctx
.get(), isl::union_map::from_domain(ExistingOccupied
), ExistingUnused
,
197 isl::union_map::from_domain(ExistingWritten
),
198 isl::union_map::from_domain(ProposedOccupied
), ProposedUnused
,
199 isl::union_map::from_domain(ProposedWritten
));
202 bool checkIsConflicting(KnowledgeStr Existing
, KnowledgeStr Proposed
) {
203 auto Forward
= checkIsConflictingNonsymmetric(Existing
, Proposed
);
204 auto Backward
= checkIsConflictingNonsymmetric(Proposed
, Existing
);
206 // isConflicting should be symmetric.
207 EXPECT_EQ(Forward
, Backward
);
209 return Forward
|| Backward
;
212 bool checkIsConflictingKnown(KnowledgeStr Existing
, KnowledgeStr Proposed
) {
213 auto Forward
= checkIsConflictingNonsymmetricKnown(Existing
, Proposed
);
214 auto Backward
= checkIsConflictingNonsymmetricKnown(Proposed
, Existing
);
216 // checkIsConflictingKnown should be symmetric.
217 EXPECT_EQ(Forward
, Backward
);
219 return Forward
|| Backward
;
222 TEST(DeLICM
, isConflicting
) {
224 // Check occupied vs. occupied.
226 checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
227 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
228 {"{ Dom[i] }", nullptr, "{}"}));
229 EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
230 {nullptr, "{ Dom[0] }", "{}"}));
231 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
232 {"{ Dom[0] }", nullptr, "{}"}));
234 // Check occupied vs. occupied with known values.
235 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
236 {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
237 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
238 {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));
239 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
240 {"{ Dom[i] -> [] }", nullptr, "{}"}));
241 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[0] -> Val[] }", nullptr, "{}"},
242 {nullptr, "{ Dom[0] }", "{}"}));
243 EXPECT_FALSE(checkIsConflictingKnown(
244 {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
245 {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
247 // An implementation using subtract would have exponential runtime on patterns
249 EXPECT_TRUE(checkIsConflictingKnown(
250 {"{ Dom[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15]"
253 {"[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,q0,"
254 "q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> {"
255 "Dom[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] -> Val[];"
256 "Dom[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15] -> Val[];"
257 "Dom[q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> Val[] }",
260 // Check occupied vs. written.
262 checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
264 checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
266 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
267 {"{}", nullptr, "{ Dom[0] }"}));
268 EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
269 {"{}", nullptr, "{ DomB[0] }"}));
271 // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
272 // 0 such that will have a different value between 0 and 1. Hence it is
273 // conflicting with Existing.
274 EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
275 {"{}", nullptr, "{ Dom[0] }"}));
276 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
277 {"{}", nullptr, "{ Dom[0] }"}));
279 // Check occupied vs. written with known values.
280 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
281 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
282 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
283 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
284 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
285 {"{}", nullptr, "{ Dom[0] -> [] }"}));
286 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> [] }", nullptr, "{}"},
287 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
289 // The same value can be known under multiple names, for instance a PHINode
290 // has the same value as one of the incoming values. One matching pair
292 EXPECT_FALSE(checkIsConflictingKnown(
293 {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
294 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
295 EXPECT_FALSE(checkIsConflictingKnown(
296 {"{ Dom[i] -> Val[] }", nullptr, "{}"},
297 {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
299 // Check written vs. written.
300 EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
301 {"{}", nullptr, "{ Dom[0] }"}));
302 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
303 {"{}", nullptr, "{ Dom[0] }"}));
304 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
305 {"{}", nullptr, "{ Dom[0] }"}));
307 // Check written vs. written with known values.
308 EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
309 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
310 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
311 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
312 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
313 {"{}", nullptr, "{ Dom[0] -> [] }"}));
314 EXPECT_FALSE(checkIsConflictingKnown(
315 {"{}", nullptr, "{ Dom[0] -> Val[]}"},
316 {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
318 } // anonymous namespace