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
19using namespace llvm;
20using namespace polly;
21
22namespace {
23
24/// Get the universes of all spaces in @p USet.
25isl::union_set unionSpace(const isl::union_set &USet) {
26 auto Result = isl::union_set::empty(ctx: USet.ctx());
27 for (isl::set Set : USet.get_set_list()) {
28 isl::space Space = Set.get_space();
29 isl::set Universe = isl::set::universe(space: Space);
30 Result = Result.unite(uset2: Universe);
31 }
32 return Result;
33}
34
35void 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.is_null() && Occupied.is_null()) {
41 assert(Occupied.is_null());
42 Occupied = Universe.subtract(uset2: Undef);
43 }
44
45 if (!OccupiedAndKnown.is_null()) {
46 assert(Known.is_null());
47
48 Known = isl::union_map::empty(ctx: ParamSpace.ctx());
49
50 if (Occupied.is_null())
51 Occupied = OccupiedAndKnown.domain();
52
53 for (isl::map Map : OccupiedAndKnown.get_map_list()) {
54 if (!Map.has_tuple_name(type: isl::dim::out))
55 continue;
56 Known = Known.unite(umap2: Map);
57 }
58 }
59
60 if (Undef.is_null()) {
61 assert(!Occupied.is_null());
62 Undef = Universe.subtract(uset2: Occupied);
63 }
64
65 if (Known.is_null()) { // By default, nothing is known.
66 Known = isl::union_map::empty(ctx: ParamSpace.ctx());
67 }
68
69 // Conditions that must hold when returning.
70 assert(!Occupied.is_null());
71 assert(!Undef.is_null());
72 assert(!Known.is_null());
73}
74
75typedef struct {
76 const char *OccupiedStr;
77 const char *UndefStr;
78 const char *WrittenStr;
79} KnowledgeStr;
80
81isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) {
82 if (!Str)
83 return {};
84 return isl::union_set(Ctx, Str);
85}
86
87isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) {
88 if (!Str)
89 return {};
90 return isl::union_map(Ctx, Str);
91}
92
93bool 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(ctx: Ctx);
100 if (!ExistingOccupiedAndKnown.is_null())
101 Universe = Universe.unite(uset2: ExistingOccupiedAndKnown.domain());
102 if (!ExistingUnused.is_null())
103 Universe = Universe.unite(uset2: ExistingUnused);
104 if (!ExistingWritten.is_null())
105 Universe = Universe.unite(uset2: ExistingWritten.domain());
106 if (!ProposedOccupiedAndKnown.is_null())
107 Universe = Universe.unite(uset2: ProposedOccupiedAndKnown.domain());
108 if (!ProposedUnused.is_null())
109 Universe = Universe.unite(uset2: ProposedUnused);
110 if (!ProposedWritten.is_null())
111 Universe = Universe.unite(uset2: ProposedWritten.domain());
112
113 Universe = unionSpace(USet: 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: Ctx, name: "Unrelated", user: &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(type: isl::dim::set, id: NewId);
122 auto NewSet = isl::set::universe(space: NewSpace);
123 Universe = Universe.unite(uset2: NewSet);
124
125 // Using the universe, fill missing data.
126 isl::union_set ExistingOccupied;
127 isl::union_map ExistingKnown;
128 completeLifetime(Universe, OccupiedAndKnown: ExistingOccupiedAndKnown, Occupied&: ExistingOccupied,
129 Known&: ExistingKnown, Undef&: ExistingUnused);
130
131 isl::union_set ProposedOccupied;
132 isl::union_map ProposedKnown;
133 completeLifetime(Universe, OccupiedAndKnown: ProposedOccupiedAndKnown, Occupied&: ProposedOccupied,
134 Known&: ProposedKnown, Undef&: ProposedUnused);
135
136 auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
137 ExistingWrites: ExistingWritten, ProposedOccupied, ProposedUnused,
138 ProposedKnown, ProposedWrites: 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
158bool 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: Ctx.get(), Str: Existing.OccupiedStr);
166 auto ExistingUnused = parseSetOrNull(Ctx: Ctx.get(), Str: Existing.UndefStr);
167 auto ExistingWritten = parseMapOrNull(Ctx: Ctx.get(), Str: Existing.WrittenStr);
168
169 auto ProposedOccupiedAndKnown =
170 parseMapOrNull(Ctx: Ctx.get(), Str: Proposed.OccupiedStr);
171 auto ProposedUnused = parseSetOrNull(Ctx: Ctx.get(), Str: Proposed.UndefStr);
172 auto ProposedWritten = parseMapOrNull(Ctx: Ctx.get(), Str: Proposed.WrittenStr);
173
174 return checkIsConflictingNonsymmetricCommon(
175 Ctx: Ctx.get(), ExistingOccupiedAndKnown, ExistingUnused, ExistingWritten,
176 ProposedOccupiedAndKnown, ProposedUnused, ProposedWritten);
177}
178
179bool 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: Ctx.get(), Str: Existing.OccupiedStr);
186 auto ExistingUnused = parseSetOrNull(Ctx: Ctx.get(), Str: Existing.UndefStr);
187 auto ExistingWritten = parseSetOrNull(Ctx: Ctx.get(), Str: Existing.WrittenStr);
188
189 auto ProposedOccupied = parseSetOrNull(Ctx: Ctx.get(), Str: Proposed.OccupiedStr);
190 auto ProposedUnused = parseSetOrNull(Ctx: Ctx.get(), Str: Proposed.UndefStr);
191 auto ProposedWritten = parseSetOrNull(Ctx: Ctx.get(), Str: Proposed.WrittenStr);
192
193 return checkIsConflictingNonsymmetricCommon(
194 Ctx: Ctx.get(), ExistingOccupiedAndKnown: isl::union_map::from_domain(uset: ExistingOccupied), ExistingUnused,
195 ExistingWritten: isl::union_map::from_domain(uset: ExistingWritten),
196 ProposedOccupiedAndKnown: isl::union_map::from_domain(uset: ProposedOccupied), ProposedUnused,
197 ProposedWritten: isl::union_map::from_domain(uset: ProposedWritten));
198}
199
200bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) {
201 auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed);
202 auto Backward = checkIsConflictingNonsymmetric(Existing: Proposed, Proposed: Existing);
203
204 // isConflicting should be symmetric.
205 EXPECT_EQ(Forward, Backward);
206
207 return Forward || Backward;
208}
209
210bool checkIsConflictingKnown(KnowledgeStr Existing, KnowledgeStr Proposed) {
211 auto Forward = checkIsConflictingNonsymmetricKnown(Existing, Proposed);
212 auto Backward = checkIsConflictingNonsymmetricKnown(Existing: Proposed, Proposed: Existing);
213
214 // checkIsConflictingKnown should be symmetric.
215 EXPECT_EQ(Forward, Backward);
216
217 return Forward || Backward;
218}
219
220TEST(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

source code of polly/unittests/DeLICM/DeLICMTest.cpp