1 //===- PresburgerSpaceTest.cpp - Tests for PresburgerSpace ----------------===//
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 "mlir/Analysis/Presburger/PresburgerSpace.h"
10 #include <gmock/gmock.h>
11 #include <gtest/gtest.h>
12
13 using namespace mlir;
14 using namespace presburger;
15
TEST(PresburgerSpaceTest,insertId)16 TEST(PresburgerSpaceTest, insertId) {
17 PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 1);
18
19 // Try inserting 2 domain ids.
20 space.insertVar(VarKind::Domain, 0, 2);
21 EXPECT_EQ(space.getNumDomainVars(), 4u);
22
23 // Try inserting 1 range ids.
24 space.insertVar(VarKind::Range, 0, 1);
25 EXPECT_EQ(space.getNumRangeVars(), 3u);
26 }
27
TEST(PresburgerSpaceTest,insertIdSet)28 TEST(PresburgerSpaceTest, insertIdSet) {
29 PresburgerSpace space = PresburgerSpace::getSetSpace(2, 1);
30
31 // Try inserting 2 dimension ids. The space should have 4 range ids since
32 // spaces which do not distinguish between domain, range are implemented like
33 // this.
34 space.insertVar(VarKind::SetDim, 0, 2);
35 EXPECT_EQ(space.getNumRangeVars(), 4u);
36 }
37
TEST(PresburgerSpaceTest,removeIdRange)38 TEST(PresburgerSpaceTest, removeIdRange) {
39 PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 1, 3);
40
41 // Remove 1 domain identifier.
42 space.removeVarRange(VarKind::Domain, 0, 1);
43 EXPECT_EQ(space.getNumDomainVars(), 1u);
44
45 // Remove 1 symbol and 1 range identifier.
46 space.removeVarRange(VarKind::Symbol, 0, 1);
47 space.removeVarRange(VarKind::Range, 0, 1);
48 EXPECT_EQ(space.getNumDomainVars(), 1u);
49 EXPECT_EQ(space.getNumRangeVars(), 0u);
50 EXPECT_EQ(space.getNumSymbolVars(), 2u);
51 }
52
TEST(PresburgerSpaceTest,insertVarIdentifier)53 TEST(PresburgerSpaceTest, insertVarIdentifier) {
54 PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 1, 0);
55
56 int identifiers[2] = {0, 1};
57
58 // Attach identifiers to domain ids.
59 space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
60 space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
61
62 // Try inserting 2 domain ids.
63 space.insertVar(VarKind::Domain, 0, 2);
64 EXPECT_EQ(space.getNumDomainVars(), 4u);
65
66 // Try inserting 1 range ids.
67 space.insertVar(VarKind::Range, 0, 1);
68 EXPECT_EQ(space.getNumRangeVars(), 3u);
69
70 // Check if the identifiers for the old ids are still attached properly.
71 EXPECT_EQ(space.getId(VarKind::Domain, 2), Identifier(&identifiers[0]));
72 EXPECT_EQ(space.getId(VarKind::Domain, 3), Identifier(&identifiers[1]));
73 }
74
TEST(PresburgerSpaceTest,removeVarRangeIdentifier)75 TEST(PresburgerSpaceTest, removeVarRangeIdentifier) {
76 PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 1, 3, 0);
77
78 int identifiers[6] = {0, 1, 2, 3, 4, 5};
79
80 // Attach identifiers to domain identifiers.
81 space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
82 space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
83
84 // Attach identifiers to range identifiers.
85 space.setId(VarKind::Range, 0, Identifier(&identifiers[2]));
86
87 // Attach identifiers to symbol identifiers.
88 space.setId(VarKind::Symbol, 0, Identifier(&identifiers[3]));
89 space.setId(VarKind::Symbol, 1, Identifier(&identifiers[4]));
90 space.setId(VarKind::Symbol, 2, Identifier(&identifiers[5]));
91
92 // Remove 1 domain identifier.
93 space.removeVarRange(VarKind::Domain, 0, 1);
94 EXPECT_EQ(space.getNumDomainVars(), 1u);
95
96 // Remove 1 symbol and 1 range identifier.
97 space.removeVarRange(VarKind::Symbol, 0, 1);
98 space.removeVarRange(VarKind::Range, 0, 1);
99 EXPECT_EQ(space.getNumDomainVars(), 1u);
100 EXPECT_EQ(space.getNumRangeVars(), 0u);
101 EXPECT_EQ(space.getNumSymbolVars(), 2u);
102
103 // Check if domain identifiers are attached properly.
104 EXPECT_EQ(space.getId(VarKind::Domain, 0), Identifier(&identifiers[1]));
105
106 // Check if symbol identifiers are attached properly.
107 EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[4]));
108 EXPECT_EQ(space.getId(VarKind::Range, 1), Identifier(&identifiers[5]));
109 }
110
TEST(PresburgerSpaceTest,IdentifierIsEqual)111 TEST(PresburgerSpaceTest, IdentifierIsEqual) {
112 PresburgerSpace space = PresburgerSpace::getRelationSpace(1, 2, 0, 0);
113
114 int identifiers[2] = {0, 1};
115 space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
116 space.setId(VarKind::Range, 0, Identifier(&identifiers[0]));
117 space.setId(VarKind::Range, 1, Identifier(&identifiers[1]));
118
119 EXPECT_EQ(space.getId(VarKind::Domain, 0), space.getId(VarKind::Range, 0));
120 EXPECT_FALSE(
121 space.getId(VarKind::Range, 0).isEqual(space.getId(VarKind::Range, 1)));
122 }
123
TEST(PresburgerSpaceTest,convertVarKind)124 TEST(PresburgerSpaceTest, convertVarKind) {
125 PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 0, 0);
126
127 // Attach identifiers.
128 int identifiers[4] = {0, 1, 2, 3};
129 space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
130 space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
131 space.setId(VarKind::Range, 0, Identifier(&identifiers[2]));
132 space.setId(VarKind::Range, 1, Identifier(&identifiers[3]));
133
134 // Convert Range variables to symbols.
135 space.convertVarKind(VarKind::Range, 0, 2, VarKind::Symbol, 0);
136
137 // Check if the identifiers are moved to symbols.
138 EXPECT_EQ(space.getId(VarKind::Symbol, 0), Identifier(&identifiers[2]));
139 EXPECT_EQ(space.getId(VarKind::Symbol, 1), Identifier(&identifiers[3]));
140
141 // Convert 1 symbol to range identifier.
142 space.convertVarKind(VarKind::Symbol, 1, 1, VarKind::Range, 0);
143
144 // Check if the identifier is moved to range.
145 EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[3]));
146 }
147
TEST(PresburgerSpaceTest,convertVarKindLocals)148 TEST(PresburgerSpaceTest, convertVarKindLocals) {
149 PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 0, 0);
150
151 // Attach identifiers to range variables.
152 int identifiers[4] = {0, 1};
153 space.setId(VarKind::Range, 0, Identifier(&identifiers[0]));
154 space.setId(VarKind::Range, 1, Identifier(&identifiers[1]));
155
156 // Convert Range variables to locals i.e. project them out.
157 space.convertVarKind(VarKind::Range, 0, 2, VarKind::Local, 0);
158
159 // Check if the variables were moved.
160 EXPECT_EQ(space.getNumVarKind(VarKind::Range), 0u);
161 EXPECT_EQ(space.getNumVarKind(VarKind::Local), 2u);
162
163 // Convert the Local variables back to Range variables.
164 space.convertVarKind(VarKind::Local, 0, 2, VarKind::Range, 0);
165
166 // The identifier information should be lost.
167 EXPECT_FALSE(space.getId(VarKind::Range, 0).hasValue());
168 EXPECT_FALSE(space.getId(VarKind::Range, 1).hasValue());
169 }
170
TEST(PresburgerSpaceTest,convertVarKind2)171 TEST(PresburgerSpaceTest, convertVarKind2) {
172 PresburgerSpace space = PresburgerSpace::getRelationSpace(0, 2, 2, 0);
173
174 // Attach identifiers.
175 int identifiers[4] = {0, 1, 2, 3};
176 space.setId(VarKind::Range, 0, Identifier(&identifiers[0]));
177 space.setId(VarKind::Range, 1, Identifier(&identifiers[1]));
178 space.setId(VarKind::Symbol, 0, Identifier(&identifiers[2]));
179 space.setId(VarKind::Symbol, 1, Identifier(&identifiers[3]));
180
181 // Convert Range variables to symbols.
182 space.convertVarKind(VarKind::Range, 0, 2, VarKind::Symbol, 1);
183
184 // Check if the identifiers are moved to symbols.
185 EXPECT_EQ(space.getId(VarKind::Symbol, 0), Identifier(&identifiers[2]));
186 EXPECT_EQ(space.getId(VarKind::Symbol, 1), Identifier(&identifiers[0]));
187 EXPECT_EQ(space.getId(VarKind::Symbol, 2), Identifier(&identifiers[1]));
188 EXPECT_EQ(space.getId(VarKind::Symbol, 3), Identifier(&identifiers[3]));
189 }
190
TEST(PresburgerSpaceTest,mergeAndAlignSymbols)191 TEST(PresburgerSpaceTest, mergeAndAlignSymbols) {
192 PresburgerSpace space = PresburgerSpace::getRelationSpace(3, 3, 2, 0);
193
194 PresburgerSpace otherSpace = PresburgerSpace::getRelationSpace(3, 2, 3, 0);
195
196 // Attach identifiers.
197 int identifiers[7] = {0, 1, 2, 3, 4, 5, 6};
198 int otherIdentifiers[8] = {10, 11, 12, 13, 14, 15, 16, 17};
199
200 space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
201 space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
202 // Note the common identifier.
203 space.setId(VarKind::Domain, 2, Identifier(&otherIdentifiers[2]));
204 space.setId(VarKind::Range, 0, Identifier(&identifiers[2]));
205 space.setId(VarKind::Range, 1, Identifier(&identifiers[3]));
206 space.setId(VarKind::Range, 2, Identifier(&identifiers[4]));
207 space.setId(VarKind::Symbol, 0, Identifier(&identifiers[5]));
208 space.setId(VarKind::Symbol, 1, Identifier(&identifiers[6]));
209
210 otherSpace.setId(VarKind::Domain, 0, Identifier(&otherIdentifiers[0]));
211 otherSpace.setId(VarKind::Domain, 1, Identifier(&otherIdentifiers[1]));
212 otherSpace.setId(VarKind::Domain, 2, Identifier(&otherIdentifiers[2]));
213 otherSpace.setId(VarKind::Range, 0, Identifier(&otherIdentifiers[3]));
214 otherSpace.setId(VarKind::Range, 1, Identifier(&otherIdentifiers[4]));
215 // Note the common identifier.
216 otherSpace.setId(VarKind::Symbol, 0, Identifier(&identifiers[6]));
217 otherSpace.setId(VarKind::Symbol, 1, Identifier(&otherIdentifiers[5]));
218 otherSpace.setId(VarKind::Symbol, 2, Identifier(&otherIdentifiers[7]));
219
220 space.mergeAndAlignSymbols(otherSpace);
221
222 // Check if merge & align is successful.
223 // Check symbol var identifiers.
224 EXPECT_EQ(4u, space.getNumSymbolVars());
225 EXPECT_EQ(4u, otherSpace.getNumSymbolVars());
226 EXPECT_EQ(space.getId(VarKind::Symbol, 0), Identifier(&identifiers[5]));
227 EXPECT_EQ(space.getId(VarKind::Symbol, 1), Identifier(&identifiers[6]));
228 EXPECT_EQ(space.getId(VarKind::Symbol, 2), Identifier(&otherIdentifiers[5]));
229 EXPECT_EQ(space.getId(VarKind::Symbol, 3), Identifier(&otherIdentifiers[7]));
230 EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 0), Identifier(&identifiers[5]));
231 EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 1), Identifier(&identifiers[6]));
232 EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 2),
233 Identifier(&otherIdentifiers[5]));
234 EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 3),
235 Identifier(&otherIdentifiers[7]));
236 // Check that domain and range var identifiers are not affected.
237 EXPECT_EQ(3u, space.getNumDomainVars());
238 EXPECT_EQ(3u, space.getNumRangeVars());
239 EXPECT_EQ(space.getId(VarKind::Domain, 0), Identifier(&identifiers[0]));
240 EXPECT_EQ(space.getId(VarKind::Domain, 1), Identifier(&identifiers[1]));
241 EXPECT_EQ(space.getId(VarKind::Domain, 2), Identifier(&otherIdentifiers[2]));
242 EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[2]));
243 EXPECT_EQ(space.getId(VarKind::Range, 1), Identifier(&identifiers[3]));
244 EXPECT_EQ(space.getId(VarKind::Range, 2), Identifier(&identifiers[4]));
245 EXPECT_EQ(3u, otherSpace.getNumDomainVars());
246 EXPECT_EQ(2u, otherSpace.getNumRangeVars());
247 EXPECT_EQ(otherSpace.getId(VarKind::Domain, 0),
248 Identifier(&otherIdentifiers[0]));
249 EXPECT_EQ(otherSpace.getId(VarKind::Domain, 1),
250 Identifier(&otherIdentifiers[1]));
251 EXPECT_EQ(otherSpace.getId(VarKind::Domain, 2),
252 Identifier(&otherIdentifiers[2]));
253 EXPECT_EQ(otherSpace.getId(VarKind::Range, 0),
254 Identifier(&otherIdentifiers[3]));
255 EXPECT_EQ(otherSpace.getId(VarKind::Range, 1),
256 Identifier(&otherIdentifiers[4]));
257 }
258