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