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