1 //===- DeLICMTest.cpp ----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "polly/DeLICM.h"
10 #include "polly/Support/ISLTools.h"
11 #include "gtest/gtest.h"
12 #include <isl/map.h>
13 #include <isl/set.h>
14 #include <isl/stream.h>
15 #include <isl/union_map.h>
16 #include <isl/union_set.h>
17 #include <memory>
18
19 using namespace llvm;
20 using namespace polly;
21
22 namespace {
23
24 /// Get the universes of all spaces in @p USet.
unionSpace(const isl::union_set & USet)25 isl::union_set unionSpace(const isl::union_set &USet) {
26 auto Result = isl::union_set::empty(USet.get_space());
27 for (isl::set Set : USet.get_set_list()) {
28 isl::space Space = Set.get_space();
29 isl::set Universe = isl::set::universe(Space);
30 Result = Result.add_set(Universe);
31 }
32 return Result;
33 }
34
completeLifetime(isl::union_set Universe,isl::union_map OccupiedAndKnown,isl::union_set & Occupied,isl::union_map & Known,isl::union_set & Undef)35 void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown,
36 isl::union_set &Occupied, isl::union_map &Known,
37 isl::union_set &Undef) {
38 auto ParamSpace = Universe.get_space();
39
40 if (Undef && !Occupied) {
41 assert(!Occupied);
42 Occupied = Universe.subtract(Undef);
43 }
44
45 if (OccupiedAndKnown) {
46 assert(!Known);
47
48 Known = isl::union_map::empty(ParamSpace);
49
50 if (!Occupied)
51 Occupied = OccupiedAndKnown.domain();
52
53 for (isl::map Map : OccupiedAndKnown.get_map_list()) {
54 if (!Map.has_tuple_name(isl::dim::out))
55 continue;
56 Known = Known.add_map(Map);
57 }
58 }
59
60 if (!Undef) {
61 assert(Occupied);
62 Undef = Universe.subtract(Occupied);
63 }
64
65 if (!Known) { // By default, nothing is known.
66 Known = isl::union_map::empty(ParamSpace);
67 }
68
69 // Conditions that must hold when returning.
70 assert(Occupied);
71 assert(Undef);
72 assert(Known);
73 }
74
75 typedef struct {
76 const char *OccupiedStr;
77 const char *UndefStr;
78 const char *WrittenStr;
79 } KnowledgeStr;
80
parseSetOrNull(isl_ctx * Ctx,const char * Str)81 isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) {
82 if (!Str)
83 return nullptr;
84 return isl::union_set(Ctx, Str);
85 }
86
parseMapOrNull(isl_ctx * Ctx,const char * Str)87 isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) {
88 if (!Str)
89 return nullptr;
90 return isl::union_map(Ctx, Str);
91 }
92
checkIsConflictingNonsymmetricCommon(isl_ctx * Ctx,isl::union_map ExistingOccupiedAndKnown,isl::union_set ExistingUnused,isl::union_map ExistingWritten,isl::union_map ProposedOccupiedAndKnown,isl::union_set ProposedUnused,isl::union_map ProposedWritten)93 bool checkIsConflictingNonsymmetricCommon(
94 isl_ctx *Ctx, isl::union_map ExistingOccupiedAndKnown,
95 isl::union_set ExistingUnused, isl::union_map ExistingWritten,
96 isl::union_map ProposedOccupiedAndKnown, isl::union_set ProposedUnused,
97 isl::union_map ProposedWritten) {
98 // Determine universe (set of all possible domains).
99 auto Universe = isl::union_set::empty(isl::space::params_alloc(Ctx, 0));
100 if (ExistingOccupiedAndKnown)
101 Universe = Universe.unite(ExistingOccupiedAndKnown.domain());
102 if (ExistingUnused)
103 Universe = Universe.unite(ExistingUnused);
104 if (ExistingWritten)
105 Universe = Universe.unite(ExistingWritten.domain());
106 if (ProposedOccupiedAndKnown)
107 Universe = Universe.unite(ProposedOccupiedAndKnown.domain());
108 if (ProposedUnused)
109 Universe = Universe.unite(ProposedUnused);
110 if (ProposedWritten)
111 Universe = Universe.unite(ProposedWritten.domain());
112
113 Universe = unionSpace(Universe);
114
115 // Add a space the universe that does not occur anywhere else to ensure
116 // robustness. Use &NewId to ensure that this Id is unique.
117 isl::id NewId = isl::id::alloc(Ctx, "Unrelated", &NewId);
118 // The space must contains at least one dimension to allow order
119 // modifications.
120 auto NewSpace = isl::space(Ctx, 0, 1);
121 NewSpace = NewSpace.set_tuple_id(isl::dim::set, NewId);
122 auto NewSet = isl::set::universe(NewSpace);
123 Universe = Universe.add_set(NewSet);
124
125 // Using the universe, fill missing data.
126 isl::union_set ExistingOccupied;
127 isl::union_map ExistingKnown;
128 completeLifetime(Universe, ExistingOccupiedAndKnown, ExistingOccupied,
129 ExistingKnown, ExistingUnused);
130
131 isl::union_set ProposedOccupied;
132 isl::union_map ProposedKnown;
133 completeLifetime(Universe, ProposedOccupiedAndKnown, ProposedOccupied,
134 ProposedKnown, ProposedUnused);
135
136 auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
137 ExistingWritten, ProposedOccupied, ProposedUnused,
138 ProposedKnown, ProposedWritten);
139
140 // isConflicting does not require ExistingOccupied nor ProposedUnused and are
141 // implicitly assumed to be the remainder elements. Test the implicitness as
142 // well.
143 EXPECT_EQ(Result,
144 isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
145 ExistingWritten, ProposedOccupied, {}, ProposedKnown,
146 ProposedWritten));
147 EXPECT_EQ(Result,
148 isConflicting({}, ExistingUnused, ExistingKnown, ExistingWritten,
149 ProposedOccupied, ProposedUnused, ProposedKnown,
150 ProposedWritten));
151 EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingKnown,
152 ExistingWritten, ProposedOccupied, {},
153 ProposedKnown, ProposedWritten));
154
155 return Result;
156 }
157
checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing,KnowledgeStr Proposed)158 bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing,
159 KnowledgeStr Proposed) {
160 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
161 &isl_ctx_free);
162
163 // Parse knowledge.
164 auto ExistingOccupiedAndKnown =
165 parseMapOrNull(Ctx.get(), Existing.OccupiedStr);
166 auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
167 auto ExistingWritten = parseMapOrNull(Ctx.get(), Existing.WrittenStr);
168
169 auto ProposedOccupiedAndKnown =
170 parseMapOrNull(Ctx.get(), Proposed.OccupiedStr);
171 auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
172 auto ProposedWritten = parseMapOrNull(Ctx.get(), Proposed.WrittenStr);
173
174 return checkIsConflictingNonsymmetricCommon(
175 Ctx.get(), ExistingOccupiedAndKnown, ExistingUnused, ExistingWritten,
176 ProposedOccupiedAndKnown, ProposedUnused, ProposedWritten);
177 }
178
checkIsConflictingNonsymmetric(KnowledgeStr Existing,KnowledgeStr Proposed)179 bool checkIsConflictingNonsymmetric(KnowledgeStr Existing,
180 KnowledgeStr Proposed) {
181 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
182 &isl_ctx_free);
183
184 // Parse knowledge.
185 auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr);
186 auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
187 auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr);
188
189 auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr);
190 auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
191 auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr);
192
193 return checkIsConflictingNonsymmetricCommon(
194 Ctx.get(), isl::union_map::from_domain(ExistingOccupied), ExistingUnused,
195 isl::union_map::from_domain(ExistingWritten),
196 isl::union_map::from_domain(ProposedOccupied), ProposedUnused,
197 isl::union_map::from_domain(ProposedWritten));
198 }
199
checkIsConflicting(KnowledgeStr Existing,KnowledgeStr Proposed)200 bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) {
201 auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed);
202 auto Backward = checkIsConflictingNonsymmetric(Proposed, Existing);
203
204 // isConflicting should be symmetric.
205 EXPECT_EQ(Forward, Backward);
206
207 return Forward || Backward;
208 }
209
checkIsConflictingKnown(KnowledgeStr Existing,KnowledgeStr Proposed)210 bool checkIsConflictingKnown(KnowledgeStr Existing, KnowledgeStr Proposed) {
211 auto Forward = checkIsConflictingNonsymmetricKnown(Existing, Proposed);
212 auto Backward = checkIsConflictingNonsymmetricKnown(Proposed, Existing);
213
214 // checkIsConflictingKnown should be symmetric.
215 EXPECT_EQ(Forward, Backward);
216
217 return Forward || Backward;
218 }
219
TEST(DeLICM,isConflicting)220 TEST(DeLICM, isConflicting) {
221
222 // Check occupied vs. occupied.
223 EXPECT_TRUE(
224 checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
225 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
226 {"{ Dom[i] }", nullptr, "{}"}));
227 EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
228 {nullptr, "{ Dom[0] }", "{}"}));
229 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
230 {"{ Dom[0] }", nullptr, "{}"}));
231
232 // Check occupied vs. occupied with known values.
233 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
234 {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
235 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
236 {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));
237 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
238 {"{ Dom[i] -> [] }", nullptr, "{}"}));
239 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[0] -> Val[] }", nullptr, "{}"},
240 {nullptr, "{ Dom[0] }", "{}"}));
241 EXPECT_FALSE(checkIsConflictingKnown(
242 {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
243 {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
244
245 // An implementation using subtract would have exponential runtime on patterns
246 // such as this one.
247 EXPECT_TRUE(checkIsConflictingKnown(
248 {"{ Dom[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15]"
249 "-> Val[] }",
250 nullptr, "{}"},
251 {"[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,q0,"
252 "q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> {"
253 "Dom[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] -> Val[];"
254 "Dom[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15] -> Val[];"
255 "Dom[q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> Val[] }",
256 "{}", "{}"}));
257
258 // Check occupied vs. written.
259 EXPECT_TRUE(
260 checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
261 EXPECT_FALSE(
262 checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
263
264 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
265 {"{}", nullptr, "{ Dom[0] }"}));
266 EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
267 {"{}", nullptr, "{ DomB[0] }"}));
268
269 // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
270 // 0 such that will have a different value between 0 and 1. Hence it is
271 // conflicting with Existing.
272 EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
273 {"{}", nullptr, "{ Dom[0] }"}));
274 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
275 {"{}", nullptr, "{ Dom[0] }"}));
276
277 // Check occupied vs. written with known values.
278 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
279 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
280 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
281 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
282 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
283 {"{}", nullptr, "{ Dom[0] -> [] }"}));
284 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> [] }", nullptr, "{}"},
285 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
286
287 // The same value can be known under multiple names, for instance a PHINode
288 // has the same value as one of the incoming values. One matching pair
289 // suffices.
290 EXPECT_FALSE(checkIsConflictingKnown(
291 {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
292 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
293 EXPECT_FALSE(checkIsConflictingKnown(
294 {"{ Dom[i] -> Val[] }", nullptr, "{}"},
295 {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
296
297 // Check written vs. written.
298 EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
299 {"{}", nullptr, "{ Dom[0] }"}));
300 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
301 {"{}", nullptr, "{ Dom[0] }"}));
302 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
303 {"{}", nullptr, "{ Dom[0] }"}));
304
305 // Check written vs. written with known values.
306 EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
307 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
308 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
309 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
310 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
311 {"{}", nullptr, "{ Dom[0] -> [] }"}));
312 EXPECT_FALSE(checkIsConflictingKnown(
313 {"{}", nullptr, "{ Dom[0] -> Val[]}"},
314 {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
315 }
316 } // anonymous namespace
317