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