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
13using namespace mlir;
14using namespace presburger;
15
16TEST(PresburgerSpaceTest, insertId) {
17 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 2, numRange: 2, numSymbols: 1);
18
19 // Try inserting 2 domain ids.
20 space.insertVar(kind: VarKind::Domain, pos: 0, num: 2);
21 EXPECT_EQ(space.getNumDomainVars(), 4u);
22
23 // Try inserting 1 range ids.
24 space.insertVar(kind: VarKind::Range, pos: 0, num: 1);
25 EXPECT_EQ(space.getNumRangeVars(), 3u);
26}
27
28TEST(PresburgerSpaceTest, insertIdSet) {
29 PresburgerSpace space = PresburgerSpace::getSetSpace(numDims: 2, numSymbols: 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(kind: VarKind::SetDim, pos: 0, num: 2);
35 EXPECT_EQ(space.getNumRangeVars(), 4u);
36}
37
38TEST(PresburgerSpaceTest, removeIdRange) {
39 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 2, numRange: 1, numSymbols: 3);
40
41 // Remove 1 domain identifier.
42 space.removeVarRange(kind: VarKind::Domain, varStart: 0, varLimit: 1);
43 EXPECT_EQ(space.getNumDomainVars(), 1u);
44
45 // Remove 1 symbol and 1 range identifier.
46 space.removeVarRange(kind: VarKind::Symbol, varStart: 0, varLimit: 1);
47 space.removeVarRange(kind: VarKind::Range, varStart: 0, varLimit: 1);
48 EXPECT_EQ(space.getNumDomainVars(), 1u);
49 EXPECT_EQ(space.getNumRangeVars(), 0u);
50 EXPECT_EQ(space.getNumSymbolVars(), 2u);
51}
52
53TEST(PresburgerSpaceTest, insertVarIdentifier) {
54 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 2, numRange: 2, numSymbols: 1, numLocals: 0);
55
56 int identifiers[2] = {0, 1};
57
58 // Attach identifiers to domain ids.
59 space.setId(kind: VarKind::Domain, pos: 0, id: Identifier(&identifiers[0]));
60 space.setId(kind: VarKind::Domain, pos: 1, id: Identifier(&identifiers[1]));
61
62 // Try inserting 2 domain ids.
63 space.insertVar(kind: VarKind::Domain, pos: 0, num: 2);
64 EXPECT_EQ(space.getNumDomainVars(), 4u);
65
66 // Try inserting 1 range ids.
67 space.insertVar(kind: VarKind::Range, pos: 0, num: 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
75TEST(PresburgerSpaceTest, removeVarRangeIdentifier) {
76 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 2, numRange: 1, numSymbols: 3, numLocals: 0);
77
78 int identifiers[6] = {0, 1, 2, 3, 4, 5};
79
80 // Attach identifiers to domain identifiers.
81 space.setId(kind: VarKind::Domain, pos: 0, id: Identifier(&identifiers[0]));
82 space.setId(kind: VarKind::Domain, pos: 1, id: Identifier(&identifiers[1]));
83
84 // Attach identifiers to range identifiers.
85 space.setId(kind: VarKind::Range, pos: 0, id: Identifier(&identifiers[2]));
86
87 // Attach identifiers to symbol identifiers.
88 space.setId(kind: VarKind::Symbol, pos: 0, id: Identifier(&identifiers[3]));
89 space.setId(kind: VarKind::Symbol, pos: 1, id: Identifier(&identifiers[4]));
90 space.setId(kind: VarKind::Symbol, pos: 2, id: Identifier(&identifiers[5]));
91
92 // Remove 1 domain identifier.
93 space.removeVarRange(kind: VarKind::Domain, varStart: 0, varLimit: 1);
94 EXPECT_EQ(space.getNumDomainVars(), 1u);
95
96 // Remove 1 symbol and 1 range identifier.
97 space.removeVarRange(kind: VarKind::Symbol, varStart: 0, varLimit: 1);
98 space.removeVarRange(kind: VarKind::Range, varStart: 0, varLimit: 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
111TEST(PresburgerSpaceTest, IdentifierIsEqual) {
112 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 1, numRange: 2, numSymbols: 0, numLocals: 0);
113
114 int identifiers[2] = {0, 1};
115 space.setId(kind: VarKind::Domain, pos: 0, id: Identifier(&identifiers[0]));
116 space.setId(kind: VarKind::Range, pos: 0, id: Identifier(&identifiers[0]));
117 space.setId(kind: VarKind::Range, pos: 1, id: 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
124TEST(PresburgerSpaceTest, convertVarKind) {
125 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 2, numRange: 2, numSymbols: 0, numLocals: 0);
126
127 // Attach identifiers.
128 int identifiers[4] = {0, 1, 2, 3};
129 space.setId(kind: VarKind::Domain, pos: 0, id: Identifier(&identifiers[0]));
130 space.setId(kind: VarKind::Domain, pos: 1, id: Identifier(&identifiers[1]));
131 space.setId(kind: VarKind::Range, pos: 0, id: Identifier(&identifiers[2]));
132 space.setId(kind: VarKind::Range, pos: 1, id: Identifier(&identifiers[3]));
133
134 // Convert Range variables to symbols.
135 space.convertVarKind(srcKind: VarKind::Range, srcPos: 0, num: 2, dstKind: VarKind::Symbol, dstPos: 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(srcKind: VarKind::Symbol, srcPos: 1, num: 1, dstKind: VarKind::Range, dstPos: 0);
143
144 // Check if the identifier is moved to range.
145 EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[3]));
146}
147
148TEST(PresburgerSpaceTest, convertVarKindLocals) {
149 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 2, numRange: 2, numSymbols: 0, numLocals: 0);
150
151 // Attach identifiers to range variables.
152 int identifiers[4] = {0, 1};
153 space.setId(kind: VarKind::Range, pos: 0, id: Identifier(&identifiers[0]));
154 space.setId(kind: VarKind::Range, pos: 1, id: Identifier(&identifiers[1]));
155
156 // Convert Range variables to locals i.e. project them out.
157 space.convertVarKind(srcKind: VarKind::Range, srcPos: 0, num: 2, dstKind: VarKind::Local, dstPos: 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(srcKind: VarKind::Local, srcPos: 0, num: 2, dstKind: VarKind::Range, dstPos: 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
171TEST(PresburgerSpaceTest, convertVarKind2) {
172 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 0, numRange: 2, numSymbols: 2, numLocals: 0);
173
174 // Attach identifiers.
175 int identifiers[4] = {0, 1, 2, 3};
176 space.setId(kind: VarKind::Range, pos: 0, id: Identifier(&identifiers[0]));
177 space.setId(kind: VarKind::Range, pos: 1, id: Identifier(&identifiers[1]));
178 space.setId(kind: VarKind::Symbol, pos: 0, id: Identifier(&identifiers[2]));
179 space.setId(kind: VarKind::Symbol, pos: 1, id: Identifier(&identifiers[3]));
180
181 // Convert Range variables to symbols.
182 space.convertVarKind(srcKind: VarKind::Range, srcPos: 0, num: 2, dstKind: VarKind::Symbol, dstPos: 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
191TEST(PresburgerSpaceTest, mergeAndAlignSymbols) {
192 PresburgerSpace space = PresburgerSpace::getRelationSpace(numDomain: 3, numRange: 3, numSymbols: 2, numLocals: 0);
193
194 PresburgerSpace otherSpace = PresburgerSpace::getRelationSpace(numDomain: 3, numRange: 2, numSymbols: 3, numLocals: 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(kind: VarKind::Domain, pos: 0, id: Identifier(&identifiers[0]));
201 space.setId(kind: VarKind::Domain, pos: 1, id: Identifier(&identifiers[1]));
202 // Note the common identifier.
203 space.setId(kind: VarKind::Domain, pos: 2, id: Identifier(&otherIdentifiers[2]));
204 space.setId(kind: VarKind::Range, pos: 0, id: Identifier(&identifiers[2]));
205 space.setId(kind: VarKind::Range, pos: 1, id: Identifier(&identifiers[3]));
206 space.setId(kind: VarKind::Range, pos: 2, id: Identifier(&identifiers[4]));
207 space.setId(kind: VarKind::Symbol, pos: 0, id: Identifier(&identifiers[5]));
208 space.setId(kind: VarKind::Symbol, pos: 1, id: Identifier(&identifiers[6]));
209
210 otherSpace.setId(kind: VarKind::Domain, pos: 0, id: Identifier(&otherIdentifiers[0]));
211 otherSpace.setId(kind: VarKind::Domain, pos: 1, id: Identifier(&otherIdentifiers[1]));
212 otherSpace.setId(kind: VarKind::Domain, pos: 2, id: Identifier(&otherIdentifiers[2]));
213 otherSpace.setId(kind: VarKind::Range, pos: 0, id: Identifier(&otherIdentifiers[3]));
214 otherSpace.setId(kind: VarKind::Range, pos: 1, id: Identifier(&otherIdentifiers[4]));
215 // Note the common identifier.
216 otherSpace.setId(kind: VarKind::Symbol, pos: 0, id: Identifier(&identifiers[6]));
217 otherSpace.setId(kind: VarKind::Symbol, pos: 1, id: Identifier(&otherIdentifiers[5]));
218 otherSpace.setId(kind: VarKind::Symbol, pos: 2, id: Identifier(&otherIdentifiers[7]));
219
220 space.mergeAndAlignSymbols(other&: 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

source code of mlir/unittests/Analysis/Presburger/PresburgerSpaceTest.cpp