1 //===- AffineStructures.h - MLIR Affine Structures Class --------*- C++ -*-===// 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 // Structures for affine/polyhedral analysis of ML functions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef MLIR_ANALYSIS_AFFINESTRUCTURES_H 14 #define MLIR_ANALYSIS_AFFINESTRUCTURES_H 15 16 #include "mlir/Analysis/Presburger/Matrix.h" 17 #include "mlir/IR/AffineExpr.h" 18 #include "mlir/IR/OpDefinition.h" 19 #include "mlir/Support/LogicalResult.h" 20 21 namespace mlir { 22 23 class AffineCondition; 24 class AffineForOp; 25 class AffineIfOp; 26 class AffineMap; 27 class AffineValueMap; 28 class IntegerSet; 29 class MLIRContext; 30 class Value; 31 class MemRefType; 32 struct MutableAffineMap; 33 34 /// A flat list of affine equalities and inequalities in the form. 35 /// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} >= 0 36 /// Equality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} == 0 37 /// 38 /// FlatAffineConstraints stores coefficients in a contiguous buffer (one buffer 39 /// for equalities and one for inequalities). The size of each buffer is 40 /// numReservedCols * number of inequalities (or equalities). The reserved size 41 /// is numReservedCols * numReservedInequalities (or numReservedEqualities). A 42 /// coefficient (r, c) lives at the location numReservedCols * r + c in the 43 /// buffer. The extra space between getNumCols() and numReservedCols exists to 44 /// prevent frequent movement of data when adding columns, especially at the 45 /// end. 46 /// 47 /// The identifiers x_0, x_1, ... appear in the order: dimensional identifiers, 48 /// symbolic identifiers, and local identifiers. The local identifiers 49 /// correspond to local/internal variables created when converting from 50 /// AffineExpr's containing mod's and div's; they are thus needed to increase 51 /// representational power. Each local identifier is always (by construction) a 52 /// floordiv of a pure add/mul affine function of dimensional, symbolic, and 53 /// other local identifiers, in a non-mutually recursive way. Hence, every local 54 /// identifier can ultimately always be recovered as an affine function of 55 /// dimensional and symbolic identifiers (involving floordiv's); note however 56 /// that some floordiv combinations are converted to mod's by AffineExpr 57 /// construction. 58 /// 59 class FlatAffineConstraints { 60 public: 61 enum IdKind { Dimension, Symbol, Local }; 62 63 /// Constructs a constraint system reserving memory for the specified number 64 /// of constraints and identifiers.. 65 FlatAffineConstraints(unsigned numReservedInequalities, 66 unsigned numReservedEqualities, 67 unsigned numReservedCols, unsigned numDims = 0, 68 unsigned numSymbols = 0, unsigned numLocals = 0, 69 ArrayRef<Optional<Value>> idArgs = {}) 70 : numIds(numDims + numSymbols + numLocals), numDims(numDims), 71 numSymbols(numSymbols), 72 equalities(0, numIds + 1, numReservedEqualities, numReservedCols), 73 inequalities(0, numIds + 1, numReservedInequalities, numReservedCols) { 74 assert(numReservedCols >= numIds + 1); 75 assert(idArgs.empty() || idArgs.size() == numIds); 76 ids.reserve(numReservedCols); 77 if (idArgs.empty()) 78 ids.resize(numIds, None); 79 else 80 ids.append(idArgs.begin(), idArgs.end()); 81 } 82 83 /// Constructs a constraint system with the specified number of 84 /// dimensions and symbols. 85 FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0, 86 unsigned numLocals = 0, 87 ArrayRef<Optional<Value>> idArgs = {}) 88 : FlatAffineConstraints(/*numReservedInequalities=*/0, 89 /*numReservedEqualities=*/0, 90 /*numReservedCols=*/numDims + numSymbols + 91 numLocals + 1, 92 numDims, numSymbols, numLocals, idArgs) {} 93 94 /// Return a system with no constraints, i.e., one which is satisfied by all 95 /// points. 96 static FlatAffineConstraints getUniverse(unsigned numDims = 0, 97 unsigned numSymbols = 0) { 98 return FlatAffineConstraints(numDims, numSymbols); 99 } 100 101 /// Create a flat affine constraint system from an AffineValueMap or a list of 102 /// these. The constructed system will only include equalities. 103 explicit FlatAffineConstraints(const AffineValueMap &avm); 104 explicit FlatAffineConstraints(ArrayRef<const AffineValueMap *> avmRef); 105 106 /// Creates an affine constraint system from an IntegerSet. 107 explicit FlatAffineConstraints(IntegerSet set); 108 109 FlatAffineConstraints(ArrayRef<const AffineValueMap *> avmRef, 110 IntegerSet set); 111 112 FlatAffineConstraints(const MutableAffineMap &map); 113 ~FlatAffineConstraints()114 ~FlatAffineConstraints() {} 115 116 // Clears any existing data and reserves memory for the specified constraints. 117 void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, 118 unsigned numReservedCols, unsigned numDims, unsigned numSymbols, 119 unsigned numLocals = 0, ArrayRef<Value> idArgs = {}); 120 121 void reset(unsigned numDims = 0, unsigned numSymbols = 0, 122 unsigned numLocals = 0, ArrayRef<Value> idArgs = {}); 123 124 /// Appends constraints from 'other' into this. This is equivalent to an 125 /// intersection with no simplification of any sort attempted. 126 void append(const FlatAffineConstraints &other); 127 128 /// Checks for emptiness by performing variable elimination on all 129 /// identifiers, running the GCD test on each equality constraint, and 130 /// checking for invalid constraints. Returns true if the GCD test fails for 131 /// any equality, or if any invalid constraints are discovered on any row. 132 /// Returns false otherwise. 133 bool isEmpty() const; 134 135 /// Runs the GCD test on all equality constraints. Returns 'true' if this test 136 /// fails on any equality. Returns 'false' otherwise. 137 /// This test can be used to disprove the existence of a solution. If it 138 /// returns true, no integer solution to the equality constraints can exist. 139 bool isEmptyByGCDTest() const; 140 141 /// Returns true if the set of constraints is found to have no solution, 142 /// false if a solution exists. Uses the same algorithm as findIntegerSample. 143 bool isIntegerEmpty() const; 144 145 // Returns a matrix where each row is a vector along which the polytope is 146 // bounded. The span of the returned vectors is guaranteed to contain all 147 // such vectors. The returned vectors are NOT guaranteed to be linearly 148 // independent. This function should not be called on empty sets. 149 Matrix getBoundedDirections() const; 150 151 /// Find an integer sample point satisfying the constraints using a 152 /// branch and bound algorithm with generalized basis reduction, with some 153 /// additional processing using Simplex for unbounded sets. 154 /// 155 /// Returns an integer sample point if one exists, or an empty Optional 156 /// otherwise. 157 Optional<SmallVector<int64_t, 8>> findIntegerSample() const; 158 159 /// Returns true if the given point satisfies the constraints, or false 160 /// otherwise. 161 bool containsPoint(ArrayRef<int64_t> point) const; 162 163 // Clones this object. 164 std::unique_ptr<FlatAffineConstraints> clone() const; 165 166 /// Returns the value at the specified equality row and column. atEq(unsigned i,unsigned j)167 inline int64_t atEq(unsigned i, unsigned j) const { return equalities(i, j); } atEq(unsigned i,unsigned j)168 inline int64_t &atEq(unsigned i, unsigned j) { return equalities(i, j); } 169 atIneq(unsigned i,unsigned j)170 inline int64_t atIneq(unsigned i, unsigned j) const { 171 return inequalities(i, j); 172 } 173 atIneq(unsigned i,unsigned j)174 inline int64_t &atIneq(unsigned i, unsigned j) { return inequalities(i, j); } 175 176 /// Returns the number of columns in the constraint system. getNumCols()177 inline unsigned getNumCols() const { return numIds + 1; } 178 getNumEqualities()179 inline unsigned getNumEqualities() const { return equalities.getNumRows(); } 180 getNumInequalities()181 inline unsigned getNumInequalities() const { 182 return inequalities.getNumRows(); 183 } 184 getNumReservedEqualities()185 inline unsigned getNumReservedEqualities() const { 186 return equalities.getNumReservedRows(); 187 } 188 getNumReservedInequalities()189 inline unsigned getNumReservedInequalities() const { 190 return inequalities.getNumReservedRows(); 191 } 192 getEquality(unsigned idx)193 inline ArrayRef<int64_t> getEquality(unsigned idx) const { 194 return equalities.getRow(idx); 195 } 196 getInequality(unsigned idx)197 inline ArrayRef<int64_t> getInequality(unsigned idx) const { 198 return inequalities.getRow(idx); 199 } 200 201 /// Adds constraints (lower and upper bounds) for the specified 'affine.for' 202 /// operation's Value using IR information stored in its bound maps. The 203 /// right identifier is first looked up using forOp's Value. Asserts if the 204 /// Value corresponding to the 'affine.for' operation isn't found in the 205 /// constraint system. Returns failure for the yet unimplemented/unsupported 206 /// cases. Any new identifiers that are found in the bound operands of the 207 /// 'affine.for' operation are added as trailing identifiers (either 208 /// dimensional or symbolic depending on whether the operand is a valid 209 /// symbol). 210 // TODO: add support for non-unit strides. 211 LogicalResult addAffineForOpDomain(AffineForOp forOp); 212 213 /// Adds constraints (lower and upper bounds) for each loop in the loop nest 214 /// described by the bound maps 'lbMaps' and 'ubMaps' of a computation slice. 215 /// Every pair ('lbMaps[i]', 'ubMaps[i]') describes the bounds of a loop in 216 /// the nest, sorted outer-to-inner. 'operands' contains the bound operands 217 /// for a single bound map. All the bound maps will use the same bound 218 /// operands. Note that some loops described by a computation slice might not 219 /// exist yet in the IR so the Value attached to those dimension identifiers 220 /// might be empty. For that reason, this method doesn't perform Value 221 /// look-ups to retrieve the dimension identifier positions. Instead, it 222 /// assumes the position of the dim identifiers in the constraint system is 223 /// the same as the position of the loop in the loop nest. 224 LogicalResult addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps, 225 ArrayRef<AffineMap> ubMaps, 226 ArrayRef<Value> operands); 227 228 /// Adds constraints imposed by the `affine.if` operation. These constraints 229 /// are collected from the IntegerSet attached to the given `affine.if` 230 /// instance argument (`ifOp`). It is asserted that: 231 /// 1) The IntegerSet of the given `affine.if` instance should not contain 232 /// semi-affine expressions, 233 /// 2) The columns of the constraint system created from `ifOp` should match 234 /// the columns in the current one regarding numbers and values. 235 void addAffineIfOpDomain(AffineIfOp ifOp); 236 237 /// Adds a lower or an upper bound for the identifier at the specified 238 /// position with constraints being drawn from the specified bound map and 239 /// operands. If `eq` is true, add a single equality equal to the bound map's 240 /// first result expr. 241 LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap, 242 ValueRange operands, bool eq, 243 bool lower = true); 244 245 /// Returns the bound for the identifier at `pos` from the inequality at 246 /// `ineqPos` as a 1-d affine value map (affine map + operands). The returned 247 /// affine value map can either be a lower bound or an upper bound depending 248 /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does 249 /// not involve the `pos`th identifier. 250 void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos, 251 AffineValueMap &vmap, 252 MLIRContext *context) const; 253 254 /// Returns the constraint system as an integer set. Returns a null integer 255 /// set if the system has no constraints, or if an integer set couldn't be 256 /// constructed as a result of a local variable's explicit representation not 257 /// being known and such a local variable appearing in any of the constraints. 258 IntegerSet getAsIntegerSet(MLIRContext *context) const; 259 260 /// Computes the lower and upper bounds of the first 'num' dimensional 261 /// identifiers (starting at 'offset') as an affine map of the remaining 262 /// identifiers (dimensional and symbolic). This method is able to detect 263 /// identifiers as floordiv's and mod's of affine expressions of other 264 /// identifiers with respect to (positive) constants. Sets bound map to a 265 /// null AffineMap if such a bound can't be found (or yet unimplemented). 266 void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, 267 SmallVectorImpl<AffineMap> *lbMaps, 268 SmallVectorImpl<AffineMap> *ubMaps); 269 270 /// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper 271 /// bounds in 'ubMaps' to each identifier in the constraint system which has 272 /// a value in 'values'. Note that both lower/upper bounds share the same 273 /// operand list 'operands'. 274 /// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size'. 275 /// Note that both lower/upper bounds use operands from 'operands'. 276 LogicalResult addSliceBounds(ArrayRef<Value> values, 277 ArrayRef<AffineMap> lbMaps, 278 ArrayRef<AffineMap> ubMaps, 279 ArrayRef<Value> operands); 280 281 // Adds an inequality (>= 0) from the coefficients specified in inEq. 282 void addInequality(ArrayRef<int64_t> inEq); 283 // Adds an equality from the coefficients specified in eq. 284 void addEquality(ArrayRef<int64_t> eq); 285 286 /// Adds a constant lower bound constraint for the specified identifier. 287 void addConstantLowerBound(unsigned pos, int64_t lb); 288 /// Adds a constant upper bound constraint for the specified identifier. 289 void addConstantUpperBound(unsigned pos, int64_t ub); 290 291 /// Adds a new local identifier as the floordiv of an affine function of other 292 /// identifiers, the coefficients of which are provided in 'dividend' and with 293 /// respect to a positive constant 'divisor'. Two constraints are added to the 294 /// system to capture equivalence with the floordiv: 295 /// q = dividend floordiv c <=> c*q <= dividend <= c*q + c - 1. 296 void addLocalFloorDiv(ArrayRef<int64_t> dividend, int64_t divisor); 297 298 /// Adds a constant lower bound constraint for the specified expression. 299 void addConstantLowerBound(ArrayRef<int64_t> expr, int64_t lb); 300 /// Adds a constant upper bound constraint for the specified expression. 301 void addConstantUpperBound(ArrayRef<int64_t> expr, int64_t ub); 302 303 /// Sets the identifier at the specified position to a constant. 304 void setIdToConstant(unsigned pos, int64_t val); 305 306 /// Sets the identifier corresponding to the specified Value id to a 307 /// constant. Asserts if the 'id' is not found. 308 void setIdToConstant(Value id, int64_t val); 309 310 /// Looks up the position of the identifier with the specified Value. Returns 311 /// true if found (false otherwise). `pos' is set to the (column) position of 312 /// the identifier. 313 bool findId(Value id, unsigned *pos) const; 314 315 /// Returns true if an identifier with the specified Value exists, false 316 /// otherwise. 317 bool containsId(Value id) const; 318 319 /// Swap the posA^th identifier with the posB^th identifier. 320 void swapId(unsigned posA, unsigned posB); 321 322 // Add identifiers of the specified kind - specified positions are relative to 323 // the kind of identifier. The coefficient column corresponding to the added 324 // identifier is initialized to zero. 'id' is the Value corresponding to the 325 // identifier that can optionally be provided. 326 void addDimId(unsigned pos, Value id = nullptr); 327 void addSymbolId(unsigned pos, Value id = nullptr); 328 void addLocalId(unsigned pos); 329 void addId(IdKind kind, unsigned pos, Value id = nullptr); 330 331 /// Add the specified values as a dim or symbol id depending on its nature, if 332 /// it already doesn't exist in the system. `id' has to be either a terminal 333 /// symbol or a loop IV, i.e., it cannot be the result affine.apply of any 334 /// symbols or loop IVs. The identifier is added to the end of the existing 335 /// dims or symbols. Additional information on the identifier is extracted 336 /// from the IR and added to the constraint system. 337 void addInductionVarOrTerminalSymbol(Value id); 338 339 /// Composes the affine value map with this FlatAffineConstrains, adding the 340 /// results of the map as dimensions at the front [0, vMap->getNumResults()) 341 /// and with the dimensions set to the equalities specified by the value map. 342 /// Returns failure if the composition fails (when vMap is a semi-affine map). 343 /// The vMap's operand Value's are used to look up the right positions in 344 /// the FlatAffineConstraints with which to associate. The dimensional and 345 /// symbolic operands of vMap should match 1:1 (in the same order) with those 346 /// of this constraint system, but the latter could have additional trailing 347 /// operands. 348 LogicalResult composeMap(const AffineValueMap *vMap); 349 350 /// Composes an affine map whose dimensions match one to one to the 351 /// dimensions of this FlatAffineConstraints. The results of the map 'other' 352 /// are added as the leading dimensions of this constraint system. Returns 353 /// failure if 'other' is a semi-affine map. 354 LogicalResult composeMatchingMap(AffineMap other); 355 356 /// Projects out (aka eliminates) 'num' identifiers starting at position 357 /// 'pos'. The resulting constraint system is the shadow along the dimensions 358 /// that still exist. This method may not always be integer exact. 359 // TODO: deal with integer exactness when necessary - can return a value to 360 // mark exactness for example. 361 void projectOut(unsigned pos, unsigned num); projectOut(unsigned pos)362 inline void projectOut(unsigned pos) { return projectOut(pos, 1); } 363 364 /// Projects out the identifier that is associate with Value . 365 void projectOut(Value id); 366 367 /// Removes the specified identifier from the system. 368 void removeId(unsigned pos); 369 370 void removeEquality(unsigned pos); 371 void removeInequality(unsigned pos); 372 373 /// Changes the partition between dimensions and symbols. Depending on the new 374 /// symbol count, either a chunk of trailing dimensional identifiers becomes 375 /// symbols, or some of the leading symbols become dimensions. 376 void setDimSymbolSeparation(unsigned newSymbolCount); 377 378 /// Changes all symbol identifiers which are loop IVs to dim identifiers. 379 void convertLoopIVSymbolsToDims(); 380 381 /// Sets the values.size() identifiers starting at pos to the specified values 382 /// and removes them. 383 void setAndEliminate(unsigned pos, ArrayRef<int64_t> values); 384 385 /// Tries to fold the specified identifier to a constant using a trivial 386 /// equality detection; if successful, the constant is substituted for the 387 /// identifier everywhere in the constraint system and then removed from the 388 /// system. 389 LogicalResult constantFoldId(unsigned pos); 390 391 /// This method calls constantFoldId for the specified range of identifiers, 392 /// 'num' identifiers starting at position 'pos'. 393 void constantFoldIdRange(unsigned pos, unsigned num); 394 395 /// Updates the constraints to be the smallest bounding (enclosing) box that 396 /// contains the points of 'this' set and that of 'other', with the symbols 397 /// being treated specially. For each of the dimensions, the min of the lower 398 /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed 399 /// to determine such a bounding box. `other' is expected to have the same 400 /// dimensional identifiers as this constraint system (in the same order). 401 /// 402 /// Eg: if 'this' is {0 <= d0 <= 127}, 'other' is {16 <= d0 <= 192}, the 403 /// output is {0 <= d0 <= 192}. 404 /// 2) 'this' = {s0 + 5 <= d0 <= s0 + 20}, 'other' is {s0 + 1 <= d0 <= s0 + 405 /// 9}, output = {s0 + 1 <= d0 <= s0 + 20}. 406 /// 3) 'this' = {0 <= d0 <= 5, 1 <= d1 <= 9}, 'other' = {2 <= d0 <= 6, 5 <= d1 407 /// <= 15}, output = {0 <= d0 <= 6, 1 <= d1 <= 15}. 408 LogicalResult unionBoundingBox(const FlatAffineConstraints &other); 409 410 /// Returns 'true' if this constraint system and 'other' are in the same 411 /// space, i.e., if they are associated with the same set of identifiers, 412 /// appearing in the same order. Returns 'false' otherwise. 413 bool areIdsAlignedWithOther(const FlatAffineConstraints &other); 414 415 /// Merge and align the identifiers of 'this' and 'other' starting at 416 /// 'offset', so that both constraint systems get the union of the contained 417 /// identifiers that is dimension-wise and symbol-wise unique; both 418 /// constraint systems are updated so that they have the union of all 419 /// identifiers, with this's original identifiers appearing first followed by 420 /// any of other's identifiers that didn't appear in 'this'. Local 421 /// identifiers of each system are by design separate/local and are placed 422 /// one after other (this's followed by other's). 423 // Eg: Input: 'this' has ((%i %j) [%M %N]) 424 // 'other' has (%k, %j) [%P, %N, %M]) 425 // Output: both 'this', 'other' have (%i, %j, %k) [%M, %N, %P] 426 // 427 void mergeAndAlignIdsWithOther(unsigned offset, FlatAffineConstraints *other); 428 getNumConstraints()429 unsigned getNumConstraints() const { 430 return getNumInequalities() + getNumEqualities(); 431 } getNumIds()432 inline unsigned getNumIds() const { return numIds; } getNumDimIds()433 inline unsigned getNumDimIds() const { return numDims; } getNumSymbolIds()434 inline unsigned getNumSymbolIds() const { return numSymbols; } getNumDimAndSymbolIds()435 inline unsigned getNumDimAndSymbolIds() const { return numDims + numSymbols; } getNumLocalIds()436 inline unsigned getNumLocalIds() const { 437 return numIds - numDims - numSymbols; 438 } 439 getIds()440 inline ArrayRef<Optional<Value>> getIds() const { 441 return {ids.data(), ids.size()}; 442 } getIds()443 inline MutableArrayRef<Optional<Value>> getIds() { 444 return {ids.data(), ids.size()}; 445 } 446 447 /// Returns the optional Value corresponding to the pos^th identifier. getId(unsigned pos)448 inline Optional<Value> getId(unsigned pos) const { return ids[pos]; } getId(unsigned pos)449 inline Optional<Value> &getId(unsigned pos) { return ids[pos]; } 450 451 /// Returns the Value associated with the pos^th identifier. Asserts if 452 /// no Value identifier was associated. getIdValue(unsigned pos)453 inline Value getIdValue(unsigned pos) const { 454 assert(ids[pos].hasValue() && "identifier's Value not set"); 455 return ids[pos].getValue(); 456 } 457 458 /// Returns the Values associated with identifiers in range [start, end). 459 /// Asserts if no Value was associated with one of these identifiers. getIdValues(unsigned start,unsigned end,SmallVectorImpl<Value> * values)460 void getIdValues(unsigned start, unsigned end, 461 SmallVectorImpl<Value> *values) const { 462 assert((start < numIds || start == end) && "invalid start position"); 463 assert(end <= numIds && "invalid end position"); 464 values->clear(); 465 values->reserve(end - start); 466 for (unsigned i = start; i < end; i++) { 467 values->push_back(getIdValue(i)); 468 } 469 } getAllIdValues(SmallVectorImpl<Value> * values)470 inline void getAllIdValues(SmallVectorImpl<Value> *values) const { 471 getIdValues(0, numIds, values); 472 } 473 474 /// Sets Value associated with the pos^th identifier. setIdValue(unsigned pos,Value val)475 inline void setIdValue(unsigned pos, Value val) { 476 assert(pos < numIds && "invalid id position"); 477 ids[pos] = val; 478 } 479 /// Sets Values associated with identifiers in the range [start, end). setIdValues(unsigned start,unsigned end,ArrayRef<Value> values)480 void setIdValues(unsigned start, unsigned end, ArrayRef<Value> values) { 481 assert((start < numIds || end == start) && "invalid start position"); 482 assert(end <= numIds && "invalid end position"); 483 assert(values.size() == end - start); 484 for (unsigned i = start; i < end; ++i) 485 ids[i] = values[i - start]; 486 } 487 488 /// Clears this list of constraints and copies other into it. 489 void clearAndCopyFrom(const FlatAffineConstraints &other); 490 491 /// Returns the smallest known constant bound for the extent of the specified 492 /// identifier (pos^th), i.e., the smallest known constant that is greater 493 /// than or equal to 'exclusive upper bound' - 'lower bound' of the 494 /// identifier. This constant bound is guaranteed to be non-negative. Returns 495 /// None if it's not a constant. This method employs trivial (low complexity / 496 /// cost) checks and detection. Symbolic identifiers are treated specially, 497 /// i.e., it looks for constant differences between affine expressions 498 /// involving only the symbolic identifiers. `lb` and `ub` (along with the 499 /// `boundFloorDivisor`) are set to represent the lower and upper bound 500 /// associated with the constant difference: `lb`, `ub` have the coefficients, 501 /// and boundFloorDivisor, their divisor. `minLbPos` and `minUbPos` if 502 /// non-null are set to the position of the constant lower bound and upper 503 /// bound respectively (to the same if they are from an equality). Ex: if the 504 /// lower bound is [(s0 + s2 - 1) floordiv 32] for a system with three 505 /// symbolic identifiers, *lb = [1, 0, 1], lbDivisor = 32. See comments at 506 /// function definition for examples. 507 Optional<int64_t> getConstantBoundOnDimSize( 508 unsigned pos, SmallVectorImpl<int64_t> *lb = nullptr, 509 int64_t *boundFloorDivisor = nullptr, 510 SmallVectorImpl<int64_t> *ub = nullptr, unsigned *minLbPos = nullptr, 511 unsigned *minUbPos = nullptr) const; 512 513 /// Returns the constant lower bound for the pos^th identifier if there is 514 /// one; None otherwise. 515 Optional<int64_t> getConstantLowerBound(unsigned pos) const; 516 517 /// Returns the constant upper bound for the pos^th identifier if there is 518 /// one; None otherwise. 519 Optional<int64_t> getConstantUpperBound(unsigned pos) const; 520 521 /// Gets the lower and upper bound of the `offset` + `pos`th identifier 522 /// treating [0, offset) U [offset + num, symStartPos) as dimensions and 523 /// [symStartPos, getNumDimAndSymbolIds) as symbols, and `pos` lies in 524 /// [0, num). The multi-dimensional maps in the returned pair represent the 525 /// max and min of potentially multiple affine expressions. The upper bound is 526 /// exclusive. `localExprs` holds pre-computed AffineExpr's for all local 527 /// identifiers in the system. 528 std::pair<AffineMap, AffineMap> 529 getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, 530 unsigned symStartPos, ArrayRef<AffineExpr> localExprs, 531 MLIRContext *context) const; 532 533 /// Gather positions of all lower and upper bounds of the identifier at `pos`, 534 /// and optionally any equalities on it. In addition, the bounds are to be 535 /// independent of identifiers in position range [`offset`, `offset` + `num`). 536 void 537 getLowerAndUpperBoundIndices(unsigned pos, 538 SmallVectorImpl<unsigned> *lbIndices, 539 SmallVectorImpl<unsigned> *ubIndices, 540 SmallVectorImpl<unsigned> *eqIndices = nullptr, 541 unsigned offset = 0, unsigned num = 0) const; 542 543 /// Removes constraints that are independent of (i.e., do not have a 544 /// coefficient for) for identifiers in the range [pos, pos + num). 545 void removeIndependentConstraints(unsigned pos, unsigned num); 546 547 /// Returns true if the set can be trivially detected as being 548 /// hyper-rectangular on the specified contiguous set of identifiers. 549 bool isHyperRectangular(unsigned pos, unsigned num) const; 550 551 /// Removes duplicate constraints, trivially true constraints, and constraints 552 /// that can be detected as redundant as a result of differing only in their 553 /// constant term part. A constraint of the form <non-negative constant> >= 0 554 /// is considered trivially true. This method is a linear time method on the 555 /// constraints, does a single scan, and updates in place. It also normalizes 556 /// constraints by their GCD and performs GCD tightening on inequalities. 557 void removeTrivialRedundancy(); 558 559 /// A more expensive check to detect redundant inequalities thatn 560 /// removeTrivialRedundancy. 561 void removeRedundantInequalities(); 562 563 /// Removes redundant constraints using Simplex. Although the algorithm can 564 /// theoretically take exponential time in the worst case (rare), it is known 565 /// to perform much better in the average case. If V is the number of vertices 566 /// in the polytope and C is the number of constraints, the algorithm takes 567 /// O(VC) time. 568 void removeRedundantConstraints(); 569 570 // Removes all equalities and inequalities. 571 void clearConstraints(); 572 573 void print(raw_ostream &os) const; 574 void dump() const; 575 576 private: 577 /// Returns false if the fields corresponding to various identifier counts, or 578 /// equality/inequality buffer sizes aren't consistent; true otherwise. This 579 /// is meant to be used within an assert internally. 580 bool hasConsistentState() const; 581 582 /// Checks all rows of equality/inequality constraints for trivial 583 /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced 584 /// after elimination. Returns 'true' if an invalid constraint is found; 585 /// 'false'otherwise. 586 bool hasInvalidConstraint() const; 587 588 /// Returns the constant lower bound bound if isLower is true, and the upper 589 /// bound if isLower is false. 590 template <bool isLower> 591 Optional<int64_t> computeConstantLowerOrUpperBound(unsigned pos); 592 593 // Eliminates a single identifier at 'position' from equality and inequality 594 // constraints. Returns 'success' if the identifier was eliminated, and 595 // 'failure' otherwise. gaussianEliminateId(unsigned position)596 inline LogicalResult gaussianEliminateId(unsigned position) { 597 return success(gaussianEliminateIds(position, position + 1) == 1); 598 } 599 600 // Eliminates identifiers from equality and inequality constraints 601 // in column range [posStart, posLimit). 602 // Returns the number of variables eliminated. 603 unsigned gaussianEliminateIds(unsigned posStart, unsigned posLimit); 604 605 /// Eliminates identifier at the specified position using Fourier-Motzkin 606 /// variable elimination, but uses Gaussian elimination if there is an 607 /// equality involving that identifier. If the result of the elimination is 608 /// integer exact, *isResultIntegerExact is set to true. If 'darkShadow' is 609 /// set to true, a potential under approximation (subset) of the rational 610 /// shadow / exact integer shadow is computed. 611 // See implementation comments for more details. 612 void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false, 613 bool *isResultIntegerExact = nullptr); 614 615 /// Tightens inequalities given that we are dealing with integer spaces. This 616 /// is similar to the GCD test but applied to inequalities. The constant term 617 /// can be reduced to the preceding multiple of the GCD of the coefficients, 618 /// i.e., 619 /// 64*i - 100 >= 0 => 64*i - 128 >= 0 (since 'i' is an integer). This is a 620 /// fast method (linear in the number of coefficients). 621 void gcdTightenInequalities(); 622 623 /// Normalized each constraints by the GCD of its coefficients. 624 void normalizeConstraintsByGCD(); 625 626 /// Removes identifiers in the column range [idStart, idLimit), and copies any 627 /// remaining valid data into place, updates member variables, and resizes 628 /// arrays as needed. 629 void removeIdRange(unsigned idStart, unsigned idLimit); 630 631 /// Total number of identifiers. 632 unsigned numIds; 633 634 /// Number of identifiers corresponding to real dimensions. 635 unsigned numDims; 636 637 /// Number of identifiers corresponding to symbols (unknown but constant for 638 /// analysis). 639 unsigned numSymbols; 640 641 /// Coefficients of affine equalities (in == 0 form). 642 Matrix equalities; 643 644 /// Coefficients of affine inequalities (in >= 0 form). 645 Matrix inequalities; 646 647 /// Values corresponding to the (column) identifiers of this constraint 648 /// system appearing in the order the identifiers correspond to columns. 649 /// Temporary ones or those that aren't associated to any Value are set to 650 /// None. 651 SmallVector<Optional<Value>, 8> ids; 652 653 /// A parameter that controls detection of an unrealistic number of 654 /// constraints. If the number of constraints is this many times the number of 655 /// variables, we consider such a system out of line with the intended use 656 /// case of FlatAffineConstraints. 657 // The rationale for 32 is that in the typical simplest of cases, an 658 // identifier is expected to have one lower bound and one upper bound 659 // constraint. With a level of tiling or a connection to another identifier 660 // through a div or mod, an extra pair of bounds gets added. As a limit, we 661 // don't expect an identifier to have more than 32 lower/upper/equality 662 // constraints. This is conservatively set low and can be raised if needed. 663 constexpr static unsigned kExplosionFactor = 32; 664 }; 665 666 /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the 667 /// dimensions, symbols, and additional variables that represent floor divisions 668 /// of dimensions, symbols, and in turn other floor divisions. Returns failure 669 /// if 'expr' could not be flattened (i.e., semi-affine is not yet handled). 670 /// 'cst' contains constraints that connect newly introduced local identifiers 671 /// to existing dimensional and symbolic identifiers. See documentation for 672 /// AffineExprFlattener on how mod's and div's are flattened. 673 LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, 674 unsigned numSymbols, 675 SmallVectorImpl<int64_t> *flattenedExpr, 676 FlatAffineConstraints *cst = nullptr); 677 678 /// Flattens the result expressions of the map to their corresponding flattened 679 /// forms and set in 'flattenedExprs'. Returns failure if any expression in the 680 /// map could not be flattened (i.e., semi-affine is not yet handled). 'cst' 681 /// contains constraints that connect newly introduced local identifiers to 682 /// existing dimensional and / symbolic identifiers. See documentation for 683 /// AffineExprFlattener on how mod's and div's are flattened. For all affine 684 /// expressions that share the same operands (like those of an affine map), this 685 /// method should be used instead of repeatedly calling getFlattenedAffineExpr 686 /// since local variables added to deal with div's and mod's will be reused 687 /// across expressions. 688 LogicalResult 689 getFlattenedAffineExprs(AffineMap map, 690 std::vector<SmallVector<int64_t, 8>> *flattenedExprs, 691 FlatAffineConstraints *cst = nullptr); 692 LogicalResult 693 getFlattenedAffineExprs(IntegerSet set, 694 std::vector<SmallVector<int64_t, 8>> *flattenedExprs, 695 FlatAffineConstraints *cst = nullptr); 696 697 } // end namespace mlir. 698 699 #endif // MLIR_ANALYSIS_AFFINESTRUCTURES_H 700