| 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 | |
| 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 | #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 | |
| 29 | void Identifier::print(llvm::raw_ostream &os) const { |
| 30 | os << "Id<" << value << ">" ; |
| 31 | } |
| 32 | |
| 33 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 34 | void Identifier::dump() const { |
| 35 | print(llvm::errs()); |
| 36 | llvm::errs() << "\n" ; |
| 37 | } |
| 38 | #endif |
| 39 | |
| 40 | PresburgerSpace 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 | |
| 48 | PresburgerSpace PresburgerSpace::getRangeSpace() const { |
| 49 | PresburgerSpace newSpace = *this; |
| 50 | newSpace.removeVarRange(kind: VarKind::Domain, varStart: 0, varLimit: getNumDomainVars()); |
| 51 | return newSpace; |
| 52 | } |
| 53 | |
| 54 | PresburgerSpace PresburgerSpace::getSpaceWithoutLocals() const { |
| 55 | PresburgerSpace space = *this; |
| 56 | space.removeVarRange(kind: VarKind::Local, varStart: 0, varLimit: getNumLocalVars()); |
| 57 | return space; |
| 58 | } |
| 59 | |
| 60 | unsigned 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 | |
| 72 | unsigned 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 | |
| 84 | unsigned PresburgerSpace::getVarKindEnd(VarKind kind) const { |
| 85 | return getVarKindOffset(kind) + getNumVarKind(kind); |
| 86 | } |
| 87 | |
| 88 | unsigned 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 | |
| 103 | VarKind 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 | |
| 116 | unsigned 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 | |
| 138 | void 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 | |
| 162 | void 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 | |
| 212 | void 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 | |
| 234 | bool PresburgerSpace::isCompatible(const PresburgerSpace &other) const { |
| 235 | return getNumDomainVars() == other.getNumDomainVars() && |
| 236 | getNumRangeVars() == other.getNumRangeVars() && |
| 237 | getNumSymbolVars() == other.getNumSymbolVars(); |
| 238 | } |
| 239 | |
| 240 | bool 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. |
| 247 | static 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 | |
| 258 | bool 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 | |
| 276 | bool 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 | |
| 293 | void 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 | |
| 302 | void 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 | |
| 331 | void 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) |
| 360 | void PresburgerSpace::dump() const { |
| 361 | print(llvm::errs()); |
| 362 | llvm::errs() << "\n" ; |
| 363 | } |
| 364 | #endif |
| 365 | |