1//===- PWMAFunction.cpp - MLIR PWMAFunction 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/PWMAFunction.h"
10#include "mlir/Analysis/Presburger/IntegerRelation.h"
11#include "mlir/Analysis/Presburger/PresburgerRelation.h"
12#include "mlir/Analysis/Presburger/PresburgerSpace.h"
13#include "mlir/Analysis/Presburger/Utils.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/STLFunctionalExtras.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/Support/raw_ostream.h"
18#include <algorithm>
19#include <cassert>
20#include <optional>
21
22using namespace mlir;
23using namespace presburger;
24
25void MultiAffineFunction::assertIsConsistent() const {
26 assert(space.getNumVars() - space.getNumRangeVars() + 1 ==
27 output.getNumColumns() &&
28 "Inconsistent number of output columns");
29 assert(space.getNumDomainVars() + space.getNumSymbolVars() ==
30 divs.getNumNonDivs() &&
31 "Inconsistent number of non-division variables in divs");
32 assert(space.getNumRangeVars() == output.getNumRows() &&
33 "Inconsistent number of output rows");
34 assert(space.getNumLocalVars() == divs.getNumDivs() &&
35 "Inconsistent number of divisions.");
36 assert(divs.hasAllReprs() && "All divisions should have a representation");
37}
38
39// Return the result of subtracting the two given vectors pointwise.
40// The vectors must be of the same size.
41// e.g., [3, 4, 6] - [2, 5, 1] = [1, -1, 5].
42static SmallVector<DynamicAPInt, 8> subtractExprs(ArrayRef<DynamicAPInt> vecA,
43 ArrayRef<DynamicAPInt> vecB) {
44 assert(vecA.size() == vecB.size() &&
45 "Cannot subtract vectors of differing lengths!");
46 SmallVector<DynamicAPInt, 8> result;
47 result.reserve(N: vecA.size());
48 for (unsigned i = 0, e = vecA.size(); i < e; ++i)
49 result.emplace_back(Args: vecA[i] - vecB[i]);
50 return result;
51}
52
53PresburgerSet PWMAFunction::getDomain() const {
54 PresburgerSet domain = PresburgerSet::getEmpty(space: getDomainSpace());
55 for (const Piece &piece : pieces)
56 domain.unionInPlace(set: piece.domain);
57 return domain;
58}
59
60void MultiAffineFunction::print(raw_ostream &os) const {
61 space.print(os);
62 os << "Division Representation:\n";
63 divs.print(os);
64 os << "Output:\n";
65 output.print(os);
66}
67
68#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
69void MultiAffineFunction::dump() const { print(llvm::errs()); }
70#endif
71
72SmallVector<DynamicAPInt, 8>
73MultiAffineFunction::valueAt(ArrayRef<DynamicAPInt> point) const {
74 assert(point.size() == getNumDomainVars() + getNumSymbolVars() &&
75 "Point has incorrect dimensionality!");
76
77 SmallVector<DynamicAPInt, 8> pointHomogenous{llvm::to_vector(Range&: point)};
78 // Get the division values at this point.
79 SmallVector<std::optional<DynamicAPInt>, 8> divValues =
80 divs.divValuesAt(point);
81 // The given point didn't include the values of the divs which the output is a
82 // function of; we have computed one possible set of values and use them here.
83 pointHomogenous.reserve(N: pointHomogenous.size() + divValues.size());
84 for (const std::optional<DynamicAPInt> &divVal : divValues)
85 pointHomogenous.emplace_back(Args: *divVal);
86 // The matrix `output` has an affine expression in the ith row, corresponding
87 // to the expression for the ith value in the output vector. The last column
88 // of the matrix contains the constant term. Let v be the input point with
89 // a 1 appended at the end. We can see that output * v gives the desired
90 // output vector.
91 pointHomogenous.emplace_back(Args: 1);
92 SmallVector<DynamicAPInt, 8> result =
93 output.postMultiplyWithColumn(colVec: pointHomogenous);
94 assert(result.size() == getNumOutputs());
95 return result;
96}
97
98bool MultiAffineFunction::isEqual(const MultiAffineFunction &other) const {
99 assert(space.isCompatible(other.space) &&
100 "Spaces should be compatible for equality check.");
101 return getAsRelation().isEqual(other: other.getAsRelation());
102}
103
104bool MultiAffineFunction::isEqual(const MultiAffineFunction &other,
105 const IntegerPolyhedron &domain) const {
106 assert(space.isCompatible(other.space) &&
107 "Spaces should be compatible for equality check.");
108 IntegerRelation restrictedThis = getAsRelation();
109 restrictedThis.intersectDomain(poly: domain);
110
111 IntegerRelation restrictedOther = other.getAsRelation();
112 restrictedOther.intersectDomain(poly: domain);
113
114 return restrictedThis.isEqual(other: restrictedOther);
115}
116
117bool MultiAffineFunction::isEqual(const MultiAffineFunction &other,
118 const PresburgerSet &domain) const {
119 assert(space.isCompatible(other.space) &&
120 "Spaces should be compatible for equality check.");
121 return llvm::all_of(Range: domain.getAllDisjuncts(),
122 P: [&](const IntegerRelation &disjunct) {
123 return isEqual(other, domain: IntegerPolyhedron(disjunct));
124 });
125}
126
127void MultiAffineFunction::removeOutputs(unsigned start, unsigned end) {
128 assert(end <= getNumOutputs() && "Invalid range");
129
130 if (start >= end)
131 return;
132
133 space.removeVarRange(kind: VarKind::Range, varStart: start, varLimit: end);
134 output.removeRows(pos: start, count: end - start);
135}
136
137void MultiAffineFunction::mergeDivs(MultiAffineFunction &other) {
138 assert(space.isCompatible(other.space) && "Functions should be compatible");
139
140 unsigned nDivs = getNumDivs();
141 unsigned divOffset = divs.getDivOffset();
142
143 other.divs.insertDiv(pos: 0, num: nDivs);
144
145 SmallVector<DynamicAPInt, 8> div(other.divs.getNumVars() + 1);
146 for (unsigned i = 0; i < nDivs; ++i) {
147 // Zero fill.
148 llvm::fill(Range&: div, Value: 0);
149 // Fill div with dividend from `divs`. Do not fill the constant.
150 std::copy(first: divs.getDividend(i).begin(), last: divs.getDividend(i).end() - 1,
151 result: div.begin());
152 // Fill constant.
153 div.back() = divs.getDividend(i).back();
154 other.divs.setDiv(i, dividend: div, divisor: divs.getDenom(i));
155 }
156
157 other.space.insertVar(kind: VarKind::Local, pos: 0, num: nDivs);
158 other.output.insertColumns(pos: divOffset, count: nDivs);
159
160 auto merge = [&](unsigned i, unsigned j) {
161 // We only merge from local at pos j to local at pos i, where j > i.
162 if (i >= j)
163 return false;
164
165 // If i < nDivs, we are trying to merge duplicate divs in `this`. Since we
166 // do not want to merge duplicates in `this`, we ignore this call.
167 if (j < nDivs)
168 return false;
169
170 // Merge things in space and output.
171 other.space.removeVarRange(kind: VarKind::Local, varStart: j, varLimit: j + 1);
172 other.output.addToColumn(sourceColumn: divOffset + i, targetColumn: divOffset + j, scale: 1);
173 other.output.removeColumn(pos: divOffset + j);
174 return true;
175 };
176
177 other.divs.removeDuplicateDivs(merge);
178
179 unsigned newDivs = other.divs.getNumDivs() - nDivs;
180
181 space.insertVar(kind: VarKind::Local, pos: nDivs, num: newDivs);
182 output.insertColumns(pos: divOffset + nDivs, count: newDivs);
183 divs = other.divs;
184
185 // Check consistency.
186 assertIsConsistent();
187 other.assertIsConsistent();
188}
189
190PresburgerSet
191MultiAffineFunction::getLexSet(OrderingKind comp,
192 const MultiAffineFunction &other) const {
193 assert(getSpace().isCompatible(other.getSpace()) &&
194 "Output space of funcs should be compatible");
195
196 // Create copies of functions and merge their local space.
197 MultiAffineFunction funcA = *this;
198 MultiAffineFunction funcB = other;
199 funcA.mergeDivs(other&: funcB);
200
201 // We first create the set `result`, corresponding to the set where output
202 // of funcA is lexicographically larger/smaller than funcB. This is done by
203 // creating a PresburgerSet with the following constraints:
204 //
205 // (outA[0] > outB[0]) U
206 // (outA[0] = outB[0], outA[1] > outA[1]) U
207 // (outA[0] = outB[0], outA[1] = outA[1], outA[2] > outA[2]) U
208 // ...
209 // (outA[0] = outB[0], ..., outA[n-2] = outB[n-2], outA[n-1] > outB[n-1])
210 //
211 // where `n` is the number of outputs.
212 // If `lexMin` is set, the complement inequality is used:
213 //
214 // (outA[0] < outB[0]) U
215 // (outA[0] = outB[0], outA[1] < outA[1]) U
216 // (outA[0] = outB[0], outA[1] = outA[1], outA[2] < outA[2]) U
217 // ...
218 // (outA[0] = outB[0], ..., outA[n-2] = outB[n-2], outA[n-1] < outB[n-1])
219 PresburgerSpace resultSpace = funcA.getDomainSpace();
220 PresburgerSet result =
221 PresburgerSet::getEmpty(space: resultSpace.getSpaceWithoutLocals());
222 IntegerPolyhedron levelSet(
223 /*numReservedInequalities=*/1 + 2 * resultSpace.getNumLocalVars(),
224 /*numReservedEqualities=*/funcA.getNumOutputs(),
225 /*numReservedCols=*/resultSpace.getNumVars() + 1, resultSpace);
226
227 // Add division inequalities to `levelSet`.
228 for (unsigned i = 0, e = funcA.getNumDivs(); i < e; ++i) {
229 levelSet.addInequality(inEq: getDivUpperBound(dividend: funcA.divs.getDividend(i),
230 divisor: funcA.divs.getDenom(i),
231 localVarIdx: funcA.divs.getDivOffset() + i));
232 levelSet.addInequality(inEq: getDivLowerBound(dividend: funcA.divs.getDividend(i),
233 divisor: funcA.divs.getDenom(i),
234 localVarIdx: funcA.divs.getDivOffset() + i));
235 }
236
237 for (unsigned level = 0; level < funcA.getNumOutputs(); ++level) {
238 // Create the expression `outA - outB` for this level.
239 SmallVector<DynamicAPInt, 8> subExpr =
240 subtractExprs(vecA: funcA.getOutputExpr(i: level), vecB: funcB.getOutputExpr(i: level));
241
242 // TODO: Implement all comparison cases.
243 switch (comp) {
244 case OrderingKind::LT:
245 // For less than, we add an upper bound of -1:
246 // outA - outB <= -1
247 // outA <= outB - 1
248 // outA < outB
249 levelSet.addBound(type: BoundType::UB, expr: subExpr, value: DynamicAPInt(-1));
250 break;
251 case OrderingKind::GT:
252 // For greater than, we add a lower bound of 1:
253 // outA - outB >= 1
254 // outA > outB + 1
255 // outA > outB
256 levelSet.addBound(type: BoundType::LB, expr: subExpr, value: DynamicAPInt(1));
257 break;
258 case OrderingKind::GE:
259 case OrderingKind::LE:
260 case OrderingKind::EQ:
261 case OrderingKind::NE:
262 assert(false && "Not implemented case");
263 }
264
265 // Union the set with the result.
266 result.unionInPlace(disjunct: levelSet);
267 // The last inequality in `levelSet` is the bound we inserted. We remove
268 // that for next iteration.
269 levelSet.removeInequality(pos: levelSet.getNumInequalities() - 1);
270 // Add equality `outA - outB == 0` for this level for next iteration.
271 levelSet.addEquality(eq: subExpr);
272 }
273
274 return result;
275}
276
277/// Two PWMAFunctions are equal if they have the same dimensionalities,
278/// the same domain, and take the same value at every point in the domain.
279bool PWMAFunction::isEqual(const PWMAFunction &other) const {
280 if (!space.isCompatible(other: other.space))
281 return false;
282
283 if (!this->getDomain().isEqual(set: other.getDomain()))
284 return false;
285
286 // Check if, whenever the domains of a piece of `this` and a piece of `other`
287 // overlap, they take the same output value. If `this` and `other` have the
288 // same domain (checked above), then this check passes iff the two functions
289 // have the same output at every point in the domain.
290 return llvm::all_of(Range: this->pieces, P: [&other](const Piece &pieceA) {
291 return llvm::all_of(Range: other.pieces, P: [&pieceA](const Piece &pieceB) {
292 PresburgerSet commonDomain = pieceA.domain.intersect(set: pieceB.domain);
293 return pieceA.output.isEqual(other: pieceB.output, domain: commonDomain);
294 });
295 });
296}
297
298void PWMAFunction::addPiece(const Piece &piece) {
299 assert(piece.isConsistent() && "Piece should be consistent");
300 assert(piece.domain.intersect(getDomain()).isIntegerEmpty() &&
301 "Piece should be disjoint from the function");
302 pieces.emplace_back(Args: piece);
303}
304
305void PWMAFunction::print(raw_ostream &os) const {
306 space.print(os);
307 os << getNumPieces() << " pieces:\n";
308 for (const Piece &piece : pieces) {
309 os << "Domain of piece:\n";
310 piece.domain.print(os);
311 os << "Output of piece\n";
312 piece.output.print(os);
313 }
314}
315
316#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
317void PWMAFunction::dump() const { print(llvm::errs()); }
318#endif
319
320PWMAFunction PWMAFunction::unionFunction(
321 const PWMAFunction &func,
322 llvm::function_ref<PresburgerSet(Piece maf1, Piece maf2)> tiebreak) const {
323 assert(getNumOutputs() == func.getNumOutputs() &&
324 "Ranges of functions should be same.");
325 assert(getSpace().isCompatible(func.getSpace()) &&
326 "Space is not compatible.");
327
328 // The algorithm used here is as follows:
329 // - Add the output of pieceB for the part of the domain where both pieceA and
330 // pieceB are defined, and `tiebreak` chooses the output of pieceB.
331 // - Add the output of pieceA, where pieceB is not defined or `tiebreak`
332 // chooses
333 // pieceA over pieceB.
334 // - Add the output of pieceB, where pieceA is not defined.
335
336 // Add parts of the common domain where pieceB's output is used. Also
337 // add all the parts where pieceA's output is used, both common and
338 // non-common.
339 PWMAFunction result(getSpace());
340 for (const Piece &pieceA : pieces) {
341 PresburgerSet dom(pieceA.domain);
342 for (const Piece &pieceB : func.pieces) {
343 PresburgerSet better = tiebreak(pieceB, pieceA);
344 if (better.isIntegerEmpty())
345 continue;
346
347 // Add the output of pieceB, where it is better than output of pieceA.
348 // The disjuncts in "better" will be disjoint as tiebreak should gurantee
349 // that.
350 result.addPiece(piece: {.domain: better, .output: pieceB.output});
351 dom = dom.subtract(set: better);
352 }
353 // Add output of pieceA, where it is better than pieceB, or pieceB is not
354 // defined.
355 //
356 // `dom` here is guranteed to be disjoint from already added pieces
357 // because the pieces added before are either:
358 // - Subsets of the domain of other MAFs in `this`, which are guranteed
359 // to be disjoint from `dom`, or
360 // - They are one of the pieces added for `pieceB`, and we have been
361 // subtracting all such pieces from `dom`, so `dom` is disjoint from those
362 // pieces as well.
363 result.addPiece(piece: {.domain: dom, .output: pieceA.output});
364 }
365
366 // Add parts of pieceB which are not shared with pieceA.
367 PresburgerSet dom = getDomain();
368 for (const Piece &pieceB : func.pieces)
369 result.addPiece(piece: {.domain: pieceB.domain.subtract(set: dom), .output: pieceB.output});
370
371 return result;
372}
373
374/// A tiebreak function which breaks ties by comparing the outputs
375/// lexicographically based on the given comparison operator.
376/// This is templated since it is passed as a lambda.
377template <OrderingKind comp>
378static PresburgerSet tiebreakLex(const PWMAFunction::Piece &pieceA,
379 const PWMAFunction::Piece &pieceB) {
380 PresburgerSet result = pieceA.output.getLexSet(comp, other: pieceB.output);
381 result = result.intersect(set: pieceA.domain).intersect(set: pieceB.domain);
382
383 return result;
384}
385
386PWMAFunction PWMAFunction::unionLexMin(const PWMAFunction &func) {
387 return unionFunction(func, tiebreak: tiebreakLex</*comp=*/OrderingKind::LT>);
388}
389
390PWMAFunction PWMAFunction::unionLexMax(const PWMAFunction &func) {
391 return unionFunction(func, tiebreak: tiebreakLex</*comp=*/OrderingKind::GT>);
392}
393
394void MultiAffineFunction::subtract(const MultiAffineFunction &other) {
395 assert(space.isCompatible(other.space) &&
396 "Spaces should be compatible for subtraction.");
397
398 MultiAffineFunction copyOther = other;
399 mergeDivs(other&: copyOther);
400 for (unsigned i = 0, e = getNumOutputs(); i < e; ++i)
401 output.addToRow(row: i, rowVec: copyOther.getOutputExpr(i), scale: DynamicAPInt(-1));
402
403 // Check consistency.
404 assertIsConsistent();
405}
406
407/// Adds division constraints corresponding to local variables, given a
408/// relation and division representations of the local variables in the
409/// relation.
410static void addDivisionConstraints(IntegerRelation &rel,
411 const DivisionRepr &divs) {
412 assert(divs.hasAllReprs() &&
413 "All divisions in divs should have a representation");
414 assert(rel.getNumVars() == divs.getNumVars() &&
415 "Relation and divs should have the same number of vars");
416 assert(rel.getNumLocalVars() == divs.getNumDivs() &&
417 "Relation and divs should have the same number of local vars");
418
419 for (unsigned i = 0, e = divs.getNumDivs(); i < e; ++i) {
420 rel.addInequality(inEq: getDivUpperBound(dividend: divs.getDividend(i), divisor: divs.getDenom(i),
421 localVarIdx: divs.getDivOffset() + i));
422 rel.addInequality(inEq: getDivLowerBound(dividend: divs.getDividend(i), divisor: divs.getDenom(i),
423 localVarIdx: divs.getDivOffset() + i));
424 }
425}
426
427IntegerRelation MultiAffineFunction::getAsRelation() const {
428 // Create a relation corressponding to the input space plus the divisions
429 // used in outputs.
430 IntegerRelation result(PresburgerSpace::getRelationSpace(
431 numDomain: space.getNumDomainVars(), numRange: 0, numSymbols: space.getNumSymbolVars(),
432 numLocals: space.getNumLocalVars()));
433 // Add division constraints corresponding to divisions used in outputs.
434 addDivisionConstraints(rel&: result, divs);
435 // The outputs are represented as range variables in the relation. We add
436 // range variables for the outputs.
437 result.insertVar(kind: VarKind::Range, pos: 0, num: getNumOutputs());
438
439 // Add equalities such that the i^th range variable is equal to the i^th
440 // output expression.
441 SmallVector<DynamicAPInt, 8> eq(result.getNumCols());
442 for (unsigned i = 0, e = getNumOutputs(); i < e; ++i) {
443 // TODO: Add functions to get VarKind offsets in output in MAF and use them
444 // here.
445 // The output expression does not contain range variables, while the
446 // equality does. So, we need to copy all variables and mark all range
447 // variables as 0 in the equality.
448 ArrayRef<DynamicAPInt> expr = getOutputExpr(i);
449 // Copy domain variables in `expr` to domain variables in `eq`.
450 std::copy(first: expr.begin(), last: expr.begin() + getNumDomainVars(), result: eq.begin());
451 // Fill the range variables in `eq` as zero.
452 std::fill(first: eq.begin() + result.getVarKindOffset(kind: VarKind::Range),
453 last: eq.begin() + result.getVarKindEnd(kind: VarKind::Range), value: 0);
454 // Copy remaining variables in `expr` to the remaining variables in `eq`.
455 std::copy(first: expr.begin() + getNumDomainVars(), last: expr.end(),
456 result: eq.begin() + result.getVarKindEnd(kind: VarKind::Range));
457
458 // Set the i^th range var to -1 in `eq` to equate the output expression to
459 // this range var.
460 eq[result.getVarKindOffset(kind: VarKind::Range) + i] = -1;
461 // Add the equality `rangeVar_i = output[i]`.
462 result.addEquality(eq);
463 }
464
465 return result;
466}
467
468void PWMAFunction::removeOutputs(unsigned start, unsigned end) {
469 space.removeVarRange(kind: VarKind::Range, varStart: start, varLimit: end);
470 for (Piece &piece : pieces)
471 piece.output.removeOutputs(start, end);
472}
473
474std::optional<SmallVector<DynamicAPInt, 8>>
475PWMAFunction::valueAt(ArrayRef<DynamicAPInt> point) const {
476 assert(point.size() == getNumDomainVars() + getNumSymbolVars());
477
478 for (const Piece &piece : pieces)
479 if (piece.domain.containsPoint(point))
480 return piece.output.valueAt(point);
481 return std::nullopt;
482}
483