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 <algorithm>
11 #include <cassert>
12 
13 using namespace mlir;
14 using namespace presburger;
15 
16 unsigned PresburgerSpace::getNumIdKind(IdKind kind) const {
17   if (kind == IdKind::Domain)
18     return getNumDomainIds();
19   if (kind == IdKind::Range)
20     return getNumRangeIds();
21   if (kind == IdKind::Symbol)
22     return getNumSymbolIds();
23   if (kind == IdKind::Local)
24     return numLocals;
25   llvm_unreachable("IdKind does not exist!");
26 }
27 
28 unsigned PresburgerSpace::getIdKindOffset(IdKind kind) const {
29   if (kind == IdKind::Domain)
30     return 0;
31   if (kind == IdKind::Range)
32     return getNumDomainIds();
33   if (kind == IdKind::Symbol)
34     return getNumDimIds();
35   if (kind == IdKind::Local)
36     return getNumDimAndSymbolIds();
37   llvm_unreachable("IdKind does not exist!");
38 }
39 
40 unsigned PresburgerSpace::getIdKindEnd(IdKind kind) const {
41   return getIdKindOffset(kind) + getNumIdKind(kind);
42 }
43 
44 unsigned PresburgerSpace::getIdKindOverlap(IdKind kind, unsigned idStart,
45                                            unsigned idLimit) const {
46   unsigned idRangeStart = getIdKindOffset(kind);
47   unsigned idRangeEnd = getIdKindEnd(kind);
48 
49   // Compute number of elements in intersection of the ranges [idStart, idLimit)
50   // and [idRangeStart, idRangeEnd).
51   unsigned overlapStart = std::max(idStart, idRangeStart);
52   unsigned overlapEnd = std::min(idLimit, idRangeEnd);
53 
54   if (overlapStart > overlapEnd)
55     return 0;
56   return overlapEnd - overlapStart;
57 }
58 
59 unsigned PresburgerSpace::insertId(IdKind kind, unsigned pos, unsigned num) {
60   assert(pos <= getNumIdKind(kind));
61 
62   unsigned absolutePos = getIdKindOffset(kind) + pos;
63 
64   if (kind == IdKind::Domain)
65     numDomain += num;
66   else if (kind == IdKind::Range)
67     numRange += num;
68   else if (kind == IdKind::Symbol)
69     numSymbols += num;
70   else
71     llvm_unreachable("PresburgerSpace does not support local identifiers!");
72 
73   return absolutePos;
74 }
75 
76 void PresburgerSpace::removeIdRange(IdKind kind, unsigned idStart,
77                                     unsigned idLimit) {
78   assert(idLimit <= getNumIdKind(kind) && "invalid id limit");
79 
80   if (idStart >= idLimit)
81     return;
82 
83   unsigned numIdsEliminated = idLimit - idStart;
84   if (kind == IdKind::Domain)
85     numDomain -= numIdsEliminated;
86   else if (kind == IdKind::Range)
87     numRange -= numIdsEliminated;
88   else if (kind == IdKind::Symbol)
89     numSymbols -= numIdsEliminated;
90   else
91     llvm_unreachable("PresburgerSpace does not support local identifiers!");
92 }
93 
94 unsigned PresburgerLocalSpace::insertId(IdKind kind, unsigned pos,
95                                         unsigned num) {
96   if (kind == IdKind::Local) {
97     numLocals += num;
98     return getIdKindOffset(IdKind::Local) + pos;
99   }
100   return PresburgerSpace::insertId(kind, pos, num);
101 }
102 
103 void PresburgerLocalSpace::removeIdRange(IdKind kind, unsigned idStart,
104                                          unsigned idLimit) {
105   assert(idLimit <= getNumIdKind(kind) && "invalid id limit");
106 
107   if (idStart >= idLimit)
108     return;
109 
110   if (kind == IdKind::Local)
111     numLocals -= idLimit - idStart;
112   else
113     PresburgerSpace::removeIdRange(kind, idStart, idLimit);
114 }
115 
116 bool PresburgerSpace::isEqual(const PresburgerSpace &other) const {
117   return getNumDomainIds() == other.getNumDomainIds() &&
118          getNumRangeIds() == other.getNumRangeIds() &&
119          getNumSymbolIds() == other.getNumSymbolIds();
120 }
121 
122 bool PresburgerLocalSpace::isEqual(const PresburgerLocalSpace &other) const {
123   return PresburgerSpace::isEqual(other) &&
124          getNumLocalIds() == other.getNumLocalIds();
125 }
126 
127 void PresburgerSpace::setDimSymbolSeparation(unsigned newSymbolCount) {
128   assert(newSymbolCount <= getNumDimAndSymbolIds() &&
129          "invalid separation position");
130   numRange = numRange + numSymbols - newSymbolCount;
131   numSymbols = newSymbolCount;
132 }
133 
134 void PresburgerSpace::print(llvm::raw_ostream &os) const {
135   os << "Domain: " << getNumDomainIds() << ", "
136      << "Range: " << getNumRangeIds() << ", "
137      << "Symbols: " << getNumSymbolIds() << "\n";
138 }
139 
140 void PresburgerSpace::dump() const { print(llvm::errs()); }
141 
142 void PresburgerLocalSpace::print(llvm::raw_ostream &os) const {
143   PresburgerSpace::print(os);
144   os << "Locals: " << getNumLocalIds() << "\n";
145 }
146 
147 void PresburgerLocalSpace::dump() const { print(llvm::errs()); }
148