1//===- PresburgerSpace.cpp - MLIR PresburgerSpace Class -------------------===//
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 "llvm/Support/ErrorHandling.h"
11#include "llvm/Support/raw_ostream.h"
12#include <algorithm>
13#include <cassert>
14
15using namespace mlir;
16using namespace presburger;
17
18bool Identifier::isEqual(const Identifier &other) const {
19 if (value == nullptr || other.value == nullptr)
20 return false;
21#if LLVM_ENABLE_ABI_BREAKING_CHECKS
22 assert(value != other.value ||
23 (value == other.value && idType == other.idType &&
24 "Values of Identifiers are equal but their types do not match."));
25#endif
26 return value == other.value;
27}
28
29void Identifier::print(llvm::raw_ostream &os) const {
30 os << "Id<" << value << ">";
31}
32
33void Identifier::dump() const {
34 print(os&: llvm::errs());
35 llvm::errs() << "\n";
36}
37
38PresburgerSpace PresburgerSpace::getDomainSpace() const {
39 PresburgerSpace newSpace = *this;
40 newSpace.removeVarRange(kind: VarKind::Range, varStart: 0, varLimit: getNumRangeVars());
41 newSpace.convertVarKind(srcKind: VarKind::Domain, srcPos: 0, num: getNumDomainVars(),
42 dstKind: VarKind::SetDim, dstPos: 0);
43 return newSpace;
44}
45
46PresburgerSpace PresburgerSpace::getRangeSpace() const {
47 PresburgerSpace newSpace = *this;
48 newSpace.removeVarRange(kind: VarKind::Domain, varStart: 0, varLimit: getNumDomainVars());
49 return newSpace;
50}
51
52PresburgerSpace PresburgerSpace::getSpaceWithoutLocals() const {
53 PresburgerSpace space = *this;
54 space.removeVarRange(kind: VarKind::Local, varStart: 0, varLimit: getNumLocalVars());
55 return space;
56}
57
58unsigned PresburgerSpace::getNumVarKind(VarKind kind) const {
59 if (kind == VarKind::Domain)
60 return getNumDomainVars();
61 if (kind == VarKind::Range)
62 return getNumRangeVars();
63 if (kind == VarKind::Symbol)
64 return getNumSymbolVars();
65 if (kind == VarKind::Local)
66 return getNumLocalVars();
67 llvm_unreachable("VarKind does not exist!");
68}
69
70unsigned PresburgerSpace::getVarKindOffset(VarKind kind) const {
71 if (kind == VarKind::Domain)
72 return 0;
73 if (kind == VarKind::Range)
74 return getNumDomainVars();
75 if (kind == VarKind::Symbol)
76 return getNumDimVars();
77 if (kind == VarKind::Local)
78 return getNumDimAndSymbolVars();
79 llvm_unreachable("VarKind does not exist!");
80}
81
82unsigned PresburgerSpace::getVarKindEnd(VarKind kind) const {
83 return getVarKindOffset(kind) + getNumVarKind(kind);
84}
85
86unsigned PresburgerSpace::getVarKindOverlap(VarKind kind, unsigned varStart,
87 unsigned varLimit) const {
88 unsigned varRangeStart = getVarKindOffset(kind);
89 unsigned varRangeEnd = getVarKindEnd(kind);
90
91 // Compute number of elements in intersection of the ranges [varStart,
92 // varLimit) and [varRangeStart, varRangeEnd).
93 unsigned overlapStart = std::max(a: varStart, b: varRangeStart);
94 unsigned overlapEnd = std::min(a: varLimit, b: varRangeEnd);
95
96 if (overlapStart > overlapEnd)
97 return 0;
98 return overlapEnd - overlapStart;
99}
100
101VarKind PresburgerSpace::getVarKindAt(unsigned pos) const {
102 assert(pos < getNumVars() && "`pos` should represent a valid var position");
103 if (pos < getVarKindEnd(kind: VarKind::Domain))
104 return VarKind::Domain;
105 if (pos < getVarKindEnd(kind: VarKind::Range))
106 return VarKind::Range;
107 if (pos < getVarKindEnd(kind: VarKind::Symbol))
108 return VarKind::Symbol;
109 if (pos < getVarKindEnd(kind: VarKind::Local))
110 return VarKind::Local;
111 llvm_unreachable("`pos` should represent a valid var position");
112}
113
114unsigned PresburgerSpace::insertVar(VarKind kind, unsigned pos, unsigned num) {
115 assert(pos <= getNumVarKind(kind));
116
117 unsigned absolutePos = getVarKindOffset(kind) + pos;
118
119 if (kind == VarKind::Domain)
120 numDomain += num;
121 else if (kind == VarKind::Range)
122 numRange += num;
123 else if (kind == VarKind::Symbol)
124 numSymbols += num;
125 else
126 numLocals += num;
127
128 // Insert NULL identifiers if `usingIds` and variables inserted are
129 // not locals.
130 if (usingIds && kind != VarKind::Local)
131 identifiers.insert(I: identifiers.begin() + absolutePos, NumToInsert: num, Elt: Identifier());
132
133 return absolutePos;
134}
135
136void PresburgerSpace::removeVarRange(VarKind kind, unsigned varStart,
137 unsigned varLimit) {
138 assert(varLimit <= getNumVarKind(kind) && "invalid var limit");
139
140 if (varStart >= varLimit)
141 return;
142
143 unsigned numVarsEliminated = varLimit - varStart;
144 if (kind == VarKind::Domain)
145 numDomain -= numVarsEliminated;
146 else if (kind == VarKind::Range)
147 numRange -= numVarsEliminated;
148 else if (kind == VarKind::Symbol)
149 numSymbols -= numVarsEliminated;
150 else
151 numLocals -= numVarsEliminated;
152
153 // Remove identifiers if `usingIds` and variables removed are not
154 // locals.
155 if (usingIds && kind != VarKind::Local)
156 identifiers.erase(CS: identifiers.begin() + getVarKindOffset(kind) + varStart,
157 CE: identifiers.begin() + getVarKindOffset(kind) + varLimit);
158}
159
160void PresburgerSpace::convertVarKind(VarKind srcKind, unsigned srcPos,
161 unsigned num, VarKind dstKind,
162 unsigned dstPos) {
163 assert(srcKind != dstKind && "cannot convert variables to the same kind");
164 assert(srcPos + num <= getNumVarKind(srcKind) &&
165 "invalid range for source variables");
166 assert(dstPos <= getNumVarKind(dstKind) &&
167 "invalid position for destination variables");
168
169 // Move identifiers if `usingIds` and variables moved are not locals.
170 unsigned srcOffset = getVarKindOffset(kind: srcKind) + srcPos;
171 unsigned dstOffset = getVarKindOffset(kind: dstKind) + dstPos;
172 if (isUsingIds() && srcKind != VarKind::Local && dstKind != VarKind::Local) {
173 identifiers.insert(I: identifiers.begin() + dstOffset, NumToInsert: num, Elt: Identifier());
174 // Update srcOffset if insertion of new elements invalidates it.
175 if (dstOffset < srcOffset)
176 srcOffset += num;
177 std::move(first: identifiers.begin() + srcOffset,
178 last: identifiers.begin() + srcOffset + num,
179 result: identifiers.begin() + dstOffset);
180 identifiers.erase(CS: identifiers.begin() + srcOffset,
181 CE: identifiers.begin() + srcOffset + num);
182 } else if (isUsingIds() && srcKind != VarKind::Local) {
183 identifiers.erase(CS: identifiers.begin() + srcOffset,
184 CE: identifiers.begin() + srcOffset + num);
185 } else if (isUsingIds() && dstKind != VarKind::Local) {
186 identifiers.insert(I: identifiers.begin() + dstOffset, NumToInsert: num, Elt: Identifier());
187 }
188
189 auto addVars = [&](VarKind kind, int num) {
190 switch (kind) {
191 case VarKind::Domain:
192 numDomain += num;
193 break;
194 case VarKind::Range:
195 numRange += num;
196 break;
197 case VarKind::Symbol:
198 numSymbols += num;
199 break;
200 case VarKind::Local:
201 numLocals += num;
202 break;
203 }
204 };
205
206 addVars(srcKind, -(signed)num);
207 addVars(dstKind, num);
208}
209
210void PresburgerSpace::swapVar(VarKind kindA, VarKind kindB, unsigned posA,
211 unsigned posB) {
212 if (!isUsingIds())
213 return;
214
215 if (kindA == VarKind::Local && kindB == VarKind::Local)
216 return;
217
218 if (kindA == VarKind::Local) {
219 setId(kind: kindB, pos: posB, id: Identifier());
220 return;
221 }
222
223 if (kindB == VarKind::Local) {
224 setId(kind: kindA, pos: posA, id: Identifier());
225 return;
226 }
227
228 std::swap(a&: identifiers[getVarKindOffset(kind: kindA) + posA],
229 b&: identifiers[getVarKindOffset(kind: kindB) + posB]);
230}
231
232bool PresburgerSpace::isCompatible(const PresburgerSpace &other) const {
233 return getNumDomainVars() == other.getNumDomainVars() &&
234 getNumRangeVars() == other.getNumRangeVars() &&
235 getNumSymbolVars() == other.getNumSymbolVars();
236}
237
238bool PresburgerSpace::isEqual(const PresburgerSpace &other) const {
239 return isCompatible(other) && getNumLocalVars() == other.getNumLocalVars();
240}
241
242/// Checks if the number of ids of the given kind in the two spaces are
243/// equal and if the ids are equal. Assumes that both spaces are using
244/// ids.
245static bool areIdsEqual(const PresburgerSpace &spaceA,
246 const PresburgerSpace &spaceB, VarKind kind) {
247 assert(spaceA.isUsingIds() && spaceB.isUsingIds() &&
248 "Both spaces should be using ids");
249 if (spaceA.getNumVarKind(kind) != spaceB.getNumVarKind(kind))
250 return false;
251 if (kind == VarKind::Local)
252 return true; // No ids.
253 return spaceA.getIds(kind) == spaceB.getIds(kind);
254}
255
256bool PresburgerSpace::isAligned(const PresburgerSpace &other) const {
257 // If only one of the spaces is using identifiers, then they are
258 // not aligned.
259 if (isUsingIds() != other.isUsingIds())
260 return false;
261 // If both spaces are using identifiers, then they are aligned if
262 // their identifiers are equal. Identifiers being equal implies
263 // that the number of variables of each kind is same, which implies
264 // compatiblity, so we do not check for that.
265 if (isUsingIds())
266 return areIdsEqual(spaceA: *this, spaceB: other, kind: VarKind::Domain) &&
267 areIdsEqual(spaceA: *this, spaceB: other, kind: VarKind::Range) &&
268 areIdsEqual(spaceA: *this, spaceB: other, kind: VarKind::Symbol);
269 // If neither space is using identifiers, then they are aligned if
270 // they are compatible.
271 return isCompatible(other);
272}
273
274bool PresburgerSpace::isAligned(const PresburgerSpace &other,
275 VarKind kind) const {
276 // If only one of the spaces is using identifiers, then they are
277 // not aligned.
278 if (isUsingIds() != other.isUsingIds())
279 return false;
280 // If both spaces are using identifiers, then they are aligned if
281 // their identifiers are equal. Identifiers being equal implies
282 // that the number of variables of each kind is same, which implies
283 // compatiblity, so we do not check for that
284 if (isUsingIds())
285 return areIdsEqual(spaceA: *this, spaceB: other, kind);
286 // If neither space is using identifiers, then they are aligned if
287 // the number of variable kind is equal.
288 return getNumVarKind(kind) == other.getNumVarKind(kind);
289}
290
291void PresburgerSpace::setVarSymbolSeparation(unsigned newSymbolCount) {
292 assert(newSymbolCount <= getNumDimAndSymbolVars() &&
293 "invalid separation position");
294 numRange = numRange + numSymbols - newSymbolCount;
295 numSymbols = newSymbolCount;
296 // We do not need to change `identifiers` since the ordering of
297 // `identifiers` remains same.
298}
299
300void PresburgerSpace::mergeAndAlignSymbols(PresburgerSpace &other) {
301 assert(usingIds && other.usingIds &&
302 "Both spaces need to have identifers to merge & align");
303
304 // First merge & align identifiers into `other` from `this`.
305 unsigned i = 0;
306 for (const Identifier identifier : getIds(kind: VarKind::Symbol)) {
307 // If the identifier exists in `other`, then align it; otherwise insert it
308 // assuming it is a new identifier. Search in `other` starting at position
309 // `i` since the left of `i` is aligned.
310 auto *findBegin = other.getIds(kind: VarKind::Symbol).begin() + i;
311 auto *findEnd = other.getIds(kind: VarKind::Symbol).end();
312 auto *itr = std::find(first: findBegin, last: findEnd, val: identifier);
313 if (itr != findEnd) {
314 std::swap(a&: findBegin, b&: itr);
315 } else {
316 other.insertVar(kind: VarKind::Symbol, pos: i);
317 other.setId(kind: VarKind::Symbol, pos: i, id: identifier);
318 }
319 ++i;
320 }
321
322 // Finally add identifiers that are in `other`, but not in `this` to `this`.
323 for (unsigned e = other.getNumVarKind(kind: VarKind::Symbol); i < e; ++i) {
324 insertVar(kind: VarKind::Symbol, pos: i);
325 setId(kind: VarKind::Symbol, pos: i, id: other.getId(kind: VarKind::Symbol, pos: i));
326 }
327}
328
329void PresburgerSpace::print(llvm::raw_ostream &os) const {
330 os << "Domain: " << getNumDomainVars() << ", "
331 << "Range: " << getNumRangeVars() << ", "
332 << "Symbols: " << getNumSymbolVars() << ", "
333 << "Locals: " << getNumLocalVars() << "\n";
334
335 if (isUsingIds()) {
336 auto printIds = [&](VarKind kind) {
337 os << " ";
338 for (Identifier id : getIds(kind)) {
339 if (id.hasValue())
340 id.print(os);
341 else
342 os << "None";
343 os << " ";
344 }
345 };
346
347 os << "(";
348 printIds(VarKind::Domain);
349 os << ") -> (";
350 printIds(VarKind::Range);
351 os << ") : [";
352 printIds(VarKind::Symbol);
353 os << "]";
354 }
355}
356
357void PresburgerSpace::dump() const {
358 print(os&: llvm::errs());
359 llvm::errs() << "\n";
360}
361

source code of mlir/lib/Analysis/Presburger/PresburgerSpace.cpp