MLIR  16.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 <algorithm>
11 #include <cassert>
12 
13 using namespace mlir;
14 using namespace presburger;
15 
17  // TODO: Preserve identifiers here.
18  return PresburgerSpace::getSetSpace(numDomain, numSymbols, numLocals);
19 }
20 
22  return PresburgerSpace::getSetSpace(numRange, numSymbols, numLocals);
23 }
24 
26  if (kind == VarKind::Domain)
27  return getNumDomainVars();
28  if (kind == VarKind::Range)
29  return getNumRangeVars();
30  if (kind == VarKind::Symbol)
31  return getNumSymbolVars();
32  if (kind == VarKind::Local)
33  return numLocals;
34  llvm_unreachable("VarKind does not exist!");
35 }
36 
38  if (kind == VarKind::Domain)
39  return 0;
40  if (kind == VarKind::Range)
41  return getNumDomainVars();
42  if (kind == VarKind::Symbol)
43  return getNumDimVars();
44  if (kind == VarKind::Local)
45  return getNumDimAndSymbolVars();
46  llvm_unreachable("VarKind does not exist!");
47 }
48 
50  return getVarKindOffset(kind) + getNumVarKind(kind);
51 }
52 
53 unsigned PresburgerSpace::getVarKindOverlap(VarKind kind, unsigned varStart,
54  unsigned varLimit) const {
55  unsigned varRangeStart = getVarKindOffset(kind);
56  unsigned varRangeEnd = getVarKindEnd(kind);
57 
58  // Compute number of elements in intersection of the ranges [varStart,
59  // varLimit) and [varRangeStart, varRangeEnd).
60  unsigned overlapStart = std::max(varStart, varRangeStart);
61  unsigned overlapEnd = std::min(varLimit, varRangeEnd);
62 
63  if (overlapStart > overlapEnd)
64  return 0;
65  return overlapEnd - overlapStart;
66 }
67 
69  assert(pos < getNumVars() && "`pos` should represent a valid var position");
70  if (pos < getVarKindEnd(VarKind::Domain))
71  return VarKind::Domain;
72  if (pos < getVarKindEnd(VarKind::Range))
73  return VarKind::Range;
74  if (pos < getVarKindEnd(VarKind::Symbol))
75  return VarKind::Symbol;
76  if (pos < getVarKindEnd(VarKind::Local))
77  return VarKind::Local;
78  llvm_unreachable("`pos` should represent a valid var position");
79 }
80 
81 unsigned PresburgerSpace::insertVar(VarKind kind, unsigned pos, unsigned num) {
82  assert(pos <= getNumVarKind(kind));
83 
84  unsigned absolutePos = getVarKindOffset(kind) + pos;
85 
86  if (kind == VarKind::Domain)
87  numDomain += num;
88  else if (kind == VarKind::Range)
89  numRange += num;
90  else if (kind == VarKind::Symbol)
91  numSymbols += num;
92  else
93  numLocals += num;
94 
95  // Insert NULL identifiers if `usingIds` and variables inserted are
96  // not locals.
97  if (usingIds && kind != VarKind::Local)
98  identifiers.insert(identifiers.begin() + absolutePos, num, nullptr);
99 
100  return absolutePos;
101 }
102 
103 void PresburgerSpace::removeVarRange(VarKind kind, unsigned varStart,
104  unsigned varLimit) {
105  assert(varLimit <= getNumVarKind(kind) && "invalid var limit");
106 
107  if (varStart >= varLimit)
108  return;
109 
110  unsigned numVarsEliminated = varLimit - varStart;
111  if (kind == VarKind::Domain)
112  numDomain -= numVarsEliminated;
113  else if (kind == VarKind::Range)
114  numRange -= numVarsEliminated;
115  else if (kind == VarKind::Symbol)
116  numSymbols -= numVarsEliminated;
117  else
118  numLocals -= numVarsEliminated;
119 
120  // Remove identifiers if `usingIds` and variables removed are not
121  // locals.
122  if (usingIds && kind != VarKind::Local)
123  identifiers.erase(identifiers.begin() + getVarKindOffset(kind) + varStart,
124  identifiers.begin() + getVarKindOffset(kind) + varLimit);
125 }
126 
127 void PresburgerSpace::swapVar(VarKind kindA, VarKind kindB, unsigned posA,
128  unsigned posB) {
129 
130  if (!usingIds)
131  return;
132 
133  if (kindA == VarKind::Local && kindB == VarKind::Local)
134  return;
135 
136  if (kindA == VarKind::Local) {
137  atId(kindB, posB) = nullptr;
138  return;
139  }
140 
141  if (kindB == VarKind::Local) {
142  atId(kindA, posA) = nullptr;
143  return;
144  }
145 
146  std::swap(atId(kindA, posA), atId(kindB, posB));
147 }
148 
150  return getNumDomainVars() == other.getNumDomainVars() &&
151  getNumRangeVars() == other.getNumRangeVars() &&
152  getNumSymbolVars() == other.getNumSymbolVars();
153 }
154 
155 bool PresburgerSpace::isEqual(const PresburgerSpace &other) const {
156  return isCompatible(other) && getNumLocalVars() == other.getNumLocalVars();
157 }
158 
159 bool PresburgerSpace::isAligned(const PresburgerSpace &other) const {
160  assert(isUsingIds() && other.isUsingIds() &&
161  "Both spaces should be using identifiers to check for "
162  "alignment.");
163  return isCompatible(other) && identifiers == other.identifiers;
164 }
165 
167  VarKind kind) const {
168  assert(isUsingIds() && other.isUsingIds() &&
169  "Both spaces should be using identifiers to check for "
170  "alignment.");
171 
172  ArrayRef<void *> kindAttachments =
173  makeArrayRef(identifiers)
174  .slice(getVarKindOffset(kind), getNumVarKind(kind));
175  ArrayRef<void *> otherKindAttachments =
176  makeArrayRef(other.identifiers)
177  .slice(other.getVarKindOffset(kind), other.getNumVarKind(kind));
178  return kindAttachments == otherKindAttachments;
179 }
180 
181 void PresburgerSpace::setVarSymbolSeperation(unsigned newSymbolCount) {
182  assert(newSymbolCount <= getNumDimAndSymbolVars() &&
183  "invalid separation position");
184  numRange = numRange + numSymbols - newSymbolCount;
185  numSymbols = newSymbolCount;
186  // We do not need to change `identifiers` since the ordering of
187  // `identifiers` remains same.
188 }
189 
190 void PresburgerSpace::print(llvm::raw_ostream &os) const {
191  os << "Domain: " << getNumDomainVars() << ", "
192  << "Range: " << getNumRangeVars() << ", "
193  << "Symbols: " << getNumSymbolVars() << ", "
194  << "Locals: " << getNumLocalVars() << "\n";
195 
196  if (usingIds) {
197 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
198  os << "TypeID of identifiers: " << idType.getAsOpaquePointer() << "\n";
199 #endif
200 
201  os << "(";
202  for (void *identifier : identifiers)
203  os << identifier << " ";
204  os << ")\n";
205  }
206 }
207 
208 void PresburgerSpace::dump() const { print(llvm::errs()); }
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
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
bool isUsingIds() const
Returns if identifiers are being used.
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).
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
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, as well as have the same identifiers for each variable.
void *& atId(VarKind kind, unsigned i)
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.