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