MLIR  21.0.0git
ValueBoundsOpInterface.cpp
Go to the documentation of this file.
1 //===- ValueBoundsOpInterface.cpp - Value Bounds -------------------------===//
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 
11 #include "mlir/IR/BuiltinTypes.h"
12 #include "mlir/IR/Matchers.h"
15 #include "llvm/ADT/APSInt.h"
16 #include "llvm/Support/Debug.h"
17 
18 #define DEBUG_TYPE "value-bounds-op-interface"
19 
20 using namespace mlir;
23 
24 namespace mlir {
25 #include "mlir/Interfaces/ValueBoundsOpInterface.cpp.inc"
26 } // namespace mlir
27 
29  if (auto bbArg = dyn_cast<BlockArgument>(value))
30  return bbArg.getOwner()->getParentOp();
31  return value.getDefiningOp();
32 }
33 
36  ArrayRef<OpFoldResult> strides)
37  : mixedOffsets(offsets), mixedSizes(sizes), mixedStrides(strides) {
38  assert(offsets.size() == sizes.size() &&
39  "expected same number of offsets, sizes, strides");
40  assert(offsets.size() == strides.size() &&
41  "expected same number of offsets, sizes, strides");
42 }
43 
46  : mixedOffsets(offsets), mixedSizes(sizes) {
47  assert(offsets.size() == sizes.size() &&
48  "expected same number of offsets and sizes");
49  // Assume that all strides are 1.
50  if (offsets.empty())
51  return;
52  MLIRContext *ctx = offsets.front().getContext();
53  mixedStrides.append(offsets.size(), Builder(ctx).getIndexAttr(1));
54 }
55 
56 HyperrectangularSlice::HyperrectangularSlice(OffsetSizeAndStrideOpInterface op)
57  : HyperrectangularSlice(op.getMixedOffsets(), op.getMixedSizes(),
58  op.getMixedStrides()) {}
59 
60 /// If ofr is a constant integer or an IntegerAttr, return the integer.
61 static std::optional<int64_t> getConstantIntValue(OpFoldResult ofr) {
62  // Case 1: Check for Constant integer.
63  if (auto val = llvm::dyn_cast_if_present<Value>(ofr)) {
64  APSInt intVal;
65  if (matchPattern(val, m_ConstantInt(&intVal)))
66  return intVal.getSExtValue();
67  return std::nullopt;
68  }
69  // Case 2: Check for IntegerAttr.
70  Attribute attr = llvm::dyn_cast_if_present<Attribute>(ofr);
71  if (auto intAttr = dyn_cast_or_null<IntegerAttr>(attr))
72  return intAttr.getValue().getSExtValue();
73  return std::nullopt;
74 }
75 
77  : Variable(ofr, std::nullopt) {}
78 
80  : Variable(static_cast<OpFoldResult>(indexValue)) {}
81 
83  : Variable(static_cast<OpFoldResult>(shapedValue), std::optional(dim)) {}
84 
86  std::optional<int64_t> dim) {
87  Builder b(ofr.getContext());
88  if (auto constInt = ::getConstantIntValue(ofr)) {
89  assert(!dim && "expected no dim for index-typed values");
90  map = AffineMap::get(/*dimCount=*/0, /*symbolCount=*/0,
91  b.getAffineConstantExpr(*constInt));
92  return;
93  }
94  Value value = cast<Value>(ofr);
95 #ifndef NDEBUG
96  if (dim) {
97  assert(isa<ShapedType>(value.getType()) && "expected shaped type");
98  } else {
99  assert(value.getType().isIndex() && "expected index type");
100  }
101 #endif // NDEBUG
102  map = AffineMap::get(/*dimCount=*/0, /*symbolCount=*/1,
103  b.getAffineSymbolExpr(0));
104  mapOperands.emplace_back(value, dim);
105 }
106 
108  ArrayRef<Variable> mapOperands) {
109  assert(map.getNumResults() == 1 && "expected single result");
110 
111  // Turn all dims into symbols.
112  Builder b(map.getContext());
113  SmallVector<AffineExpr> dimReplacements, symReplacements;
114  for (int64_t i = 0, e = map.getNumDims(); i < e; ++i)
115  dimReplacements.push_back(b.getAffineSymbolExpr(i));
116  for (int64_t i = 0, e = map.getNumSymbols(); i < e; ++i)
117  symReplacements.push_back(b.getAffineSymbolExpr(i + map.getNumDims()));
118  AffineMap tmpMap = map.replaceDimsAndSymbols(
119  dimReplacements, symReplacements, /*numResultDims=*/0,
120  /*numResultSyms=*/map.getNumSymbols() + map.getNumDims());
121 
122  // Inline operands.
124  for (auto [index, var] : llvm::enumerate(mapOperands)) {
125  assert(var.map.getNumResults() == 1 && "expected single result");
126  assert(var.map.getNumDims() == 0 && "expected only symbols");
127  SmallVector<AffineExpr> symReplacements;
128  for (auto valueDim : var.mapOperands) {
129  auto it = llvm::find(this->mapOperands, valueDim);
130  if (it != this->mapOperands.end()) {
131  // There is already a symbol for this operand.
132  symReplacements.push_back(b.getAffineSymbolExpr(
133  std::distance(this->mapOperands.begin(), it)));
134  } else {
135  // This is a new operand: add a new symbol.
136  symReplacements.push_back(
137  b.getAffineSymbolExpr(this->mapOperands.size()));
138  this->mapOperands.push_back(valueDim);
139  }
140  }
141  replacements[b.getAffineSymbolExpr(index)] =
142  var.map.getResult(0).replaceSymbols(symReplacements);
143  }
144  this->map = tmpMap.replace(replacements, /*numResultDims=*/0,
145  /*numResultSyms=*/this->mapOperands.size());
146 }
147 
149  ValueRange mapOperands)
150  : Variable(map, llvm::map_to_vector(mapOperands,
151  [](Value v) { return Variable(v); })) {}
152 
158  assert(stopCondition && "expected non-null stop condition");
159 }
160 
162 
163 #ifndef NDEBUG
164 static void assertValidValueDim(Value value, std::optional<int64_t> dim) {
165  if (value.getType().isIndex()) {
166  assert(!dim.has_value() && "invalid dim value");
167  } else if (auto shapedType = dyn_cast<ShapedType>(value.getType())) {
168  assert(*dim >= 0 && "invalid dim value");
169  if (shapedType.hasRank())
170  assert(*dim < shapedType.getRank() && "invalid dim value");
171  } else {
172  llvm_unreachable("unsupported type");
173  }
174 }
175 #endif // NDEBUG
176 
178  AffineExpr expr) {
179  // Note: If `addConservativeSemiAffineBounds` is true then the bound
180  // computation function needs to handle the case that the constraints set
181  // could become empty. This is because the conservative bounds add assumptions
182  // (e.g. for `mod` it assumes `rhs > 0`). If these constraints are later found
183  // not to hold, then the bound is invalid.
184  LogicalResult status = cstr.addBound(
185  type, pos,
190  if (failed(status)) {
191  // Not all semi-affine expressions are not yet supported by
192  // FlatLinearConstraints. However, we can just ignore such failures here.
193  // Even without this bound, there may be enough information in the
194  // constraint system to compute the requested bound. In case this bound is
195  // actually needed, `computeBound` will return `failure`.
196  LLVM_DEBUG(llvm::dbgs() << "Failed to add bound: " << expr << "\n");
197  }
198 }
199 
201  std::optional<int64_t> dim) {
202 #ifndef NDEBUG
203  assertValidValueDim(value, dim);
204 #endif // NDEBUG
205 
206  // Check if the value/dim is statically known. In that case, an affine
207  // constant expression should be returned. This allows us to support
208  // multiplications with constants. (Multiplications of two columns in the
209  // constraint set is not supported.)
210  std::optional<int64_t> constSize = std::nullopt;
211  auto shapedType = dyn_cast<ShapedType>(value.getType());
212  if (shapedType) {
213  if (shapedType.hasRank() && !shapedType.isDynamicDim(*dim))
214  constSize = shapedType.getDimSize(*dim);
215  } else if (auto constInt = ::getConstantIntValue(value)) {
216  constSize = *constInt;
217  }
218 
219  // If the value/dim is already mapped, return the corresponding expression
220  // directly.
221  ValueDim valueDim = std::make_pair(value, dim.value_or(kIndexValue));
222  if (valueDimToPosition.contains(valueDim)) {
223  // If it is a constant, return an affine constant expression. Otherwise,
224  // return an affine expression that represents the respective column in the
225  // constraint set.
226  if (constSize)
227  return builder.getAffineConstantExpr(*constSize);
228  return getPosExpr(getPos(value, dim));
229  }
230 
231  if (constSize) {
232  // Constant index value/dim: add column to the constraint set, add EQ bound
233  // and return an affine constant expression without pushing the newly added
234  // column to the worklist.
235  (void)insert(value, dim, /*isSymbol=*/true, /*addToWorklist=*/false);
236  if (shapedType)
237  bound(value)[*dim] == *constSize;
238  else
239  bound(value) == *constSize;
240  return builder.getAffineConstantExpr(*constSize);
241  }
242 
243  // Dynamic value/dim: insert column to the constraint set and put it on the
244  // worklist. Return an affine expression that represents the newly inserted
245  // column in the constraint set.
246  return getPosExpr(insert(value, dim, /*isSymbol=*/true));
247 }
248 
250  if (Value value = llvm::dyn_cast_if_present<Value>(ofr))
251  return getExpr(value, /*dim=*/std::nullopt);
252  auto constInt = ::getConstantIntValue(ofr);
253  assert(constInt.has_value() && "expected Integer constant");
254  return builder.getAffineConstantExpr(*constInt);
255 }
256 
258  return builder.getAffineConstantExpr(constant);
259 }
260 
262  std::optional<int64_t> dim,
263  bool isSymbol, bool addToWorklist) {
264 #ifndef NDEBUG
265  assertValidValueDim(value, dim);
266 #endif // NDEBUG
267 
268  ValueDim valueDim = std::make_pair(value, dim.value_or(kIndexValue));
269  assert(!valueDimToPosition.contains(valueDim) && "already mapped");
270  int64_t pos = isSymbol ? cstr.appendVar(VarKind::Symbol)
271  : cstr.appendVar(VarKind::SetDim);
272  LLVM_DEBUG(llvm::dbgs() << "Inserting constraint set column " << pos
273  << " for: " << value
274  << " (dim: " << dim.value_or(kIndexValue)
275  << ", owner: " << getOwnerOfValue(value)->getName()
276  << ")\n");
277  positionToValueDim.insert(positionToValueDim.begin() + pos, valueDim);
278  // Update reverse mapping.
279  for (int64_t i = pos, e = positionToValueDim.size(); i < e; ++i)
280  if (positionToValueDim[i].has_value())
282 
283  if (addToWorklist) {
284  LLVM_DEBUG(llvm::dbgs() << "Push to worklist: " << value
285  << " (dim: " << dim.value_or(kIndexValue) << ")\n");
286  worklist.push(pos);
287  }
288 
289  return pos;
290 }
291 
292 int64_t ValueBoundsConstraintSet::insert(bool isSymbol) {
293  int64_t pos = isSymbol ? cstr.appendVar(VarKind::Symbol)
294  : cstr.appendVar(VarKind::SetDim);
295  LLVM_DEBUG(llvm::dbgs() << "Inserting anonymous constraint set column " << pos
296  << "\n");
297  positionToValueDim.insert(positionToValueDim.begin() + pos, std::nullopt);
298  // Update reverse mapping.
299  for (int64_t i = pos, e = positionToValueDim.size(); i < e; ++i)
300  if (positionToValueDim[i].has_value())
302  return pos;
303 }
304 
306  bool isSymbol) {
307  assert(map.getNumResults() == 1 && "expected affine map with one result");
308  int64_t pos = insert(isSymbol);
309 
310  // Add map and operands to the constraint set. Dimensions are converted to
311  // symbols. All operands are added to the worklist (unless they were already
312  // processed).
313  auto mapper = [&](std::pair<Value, std::optional<int64_t>> v) {
314  return getExpr(v.first, v.second);
315  };
316  SmallVector<AffineExpr> dimReplacements = llvm::to_vector(
317  llvm::map_range(ArrayRef(operands).take_front(map.getNumDims()), mapper));
318  SmallVector<AffineExpr> symReplacements = llvm::to_vector(
319  llvm::map_range(ArrayRef(operands).drop_front(map.getNumDims()), mapper));
320  addBound(
322  map.getResult(0).replaceDimsAndSymbols(dimReplacements, symReplacements));
323 
324  return pos;
325 }
326 
327 int64_t ValueBoundsConstraintSet::insert(const Variable &var, bool isSymbol) {
328  return insert(var.map, var.mapOperands, isSymbol);
329 }
330 
332  std::optional<int64_t> dim) const {
333 #ifndef NDEBUG
334  assertValidValueDim(value, dim);
335  assert((isa<OpResult>(value) ||
336  cast<BlockArgument>(value).getOwner()->isEntryBlock()) &&
337  "unstructured control flow is not supported");
338 #endif // NDEBUG
339  LLVM_DEBUG(llvm::dbgs() << "Getting pos for: " << value
340  << " (dim: " << dim.value_or(kIndexValue)
341  << ", owner: " << getOwnerOfValue(value)->getName()
342  << ")\n");
343  auto it =
344  valueDimToPosition.find(std::make_pair(value, dim.value_or(kIndexValue)));
345  assert(it != valueDimToPosition.end() && "expected mapped entry");
346  return it->second;
347 }
348 
350  assert(pos >= 0 && pos < cstr.getNumDimAndSymbolVars() && "invalid position");
351  return pos < cstr.getNumDimVars()
354 }
355 
357  std::optional<int64_t> dim) const {
358  auto it =
359  valueDimToPosition.find(std::make_pair(value, dim.value_or(kIndexValue)));
360  return it != valueDimToPosition.end();
361 }
362 
364  LLVM_DEBUG(llvm::dbgs() << "Processing value bounds worklist...\n");
365  while (!worklist.empty()) {
366  int64_t pos = worklist.front();
367  worklist.pop();
368  assert(positionToValueDim[pos].has_value() &&
369  "did not expect std::nullopt on worklist");
370  ValueDim valueDim = *positionToValueDim[pos];
371  Value value = valueDim.first;
372  int64_t dim = valueDim.second;
373 
374  // Check for static dim size.
375  if (dim != kIndexValue) {
376  auto shapedType = cast<ShapedType>(value.getType());
377  if (shapedType.hasRank() && !shapedType.isDynamicDim(dim)) {
378  bound(value)[dim] == getExpr(shapedType.getDimSize(dim));
379  continue;
380  }
381  }
382 
383  // Do not process any further if the stop condition is met.
384  auto maybeDim = dim == kIndexValue ? std::nullopt : std::make_optional(dim);
385  if (stopCondition(value, maybeDim, *this)) {
386  LLVM_DEBUG(llvm::dbgs() << "Stop condition met for: " << value
387  << " (dim: " << maybeDim << ")\n");
388  continue;
389  }
390 
391  // Query `ValueBoundsOpInterface` for constraints. New items may be added to
392  // the worklist.
393  auto valueBoundsOp =
394  dyn_cast<ValueBoundsOpInterface>(getOwnerOfValue(value));
395  LLVM_DEBUG(llvm::dbgs()
396  << "Query value bounds for: " << value
397  << " (owner: " << getOwnerOfValue(value)->getName() << ")\n");
398  if (valueBoundsOp) {
399  if (dim == kIndexValue) {
400  valueBoundsOp.populateBoundsForIndexValue(value, *this);
401  } else {
402  valueBoundsOp.populateBoundsForShapedValueDim(value, dim, *this);
403  }
404  continue;
405  }
406  LLVM_DEBUG(llvm::dbgs() << "--> ValueBoundsOpInterface not implemented\n");
407 
408  // If the op does not implement `ValueBoundsOpInterface`, check if it
409  // implements the `DestinationStyleOpInterface`. OpResults of such ops are
410  // tied to OpOperands. Tied values have the same shape.
411  auto dstOp = value.getDefiningOp<DestinationStyleOpInterface>();
412  if (!dstOp || dim == kIndexValue)
413  continue;
414  Value tiedOperand = dstOp.getTiedOpOperand(cast<OpResult>(value))->get();
415  bound(value)[dim] == getExpr(tiedOperand, dim);
416  }
417 }
418 
420  assert(pos >= 0 && pos < static_cast<int64_t>(positionToValueDim.size()) &&
421  "invalid position");
422  cstr.projectOut(pos);
423  if (positionToValueDim[pos].has_value()) {
424  bool erased = valueDimToPosition.erase(*positionToValueDim[pos]);
425  (void)erased;
426  assert(erased && "inconsistent reverse mapping");
427  }
428  positionToValueDim.erase(positionToValueDim.begin() + pos);
429  // Update reverse mapping.
430  for (int64_t i = pos, e = positionToValueDim.size(); i < e; ++i)
431  if (positionToValueDim[i].has_value())
433 }
434 
436  function_ref<bool(ValueDim)> condition) {
437  int64_t nextPos = 0;
438  while (nextPos < static_cast<int64_t>(positionToValueDim.size())) {
439  if (positionToValueDim[nextPos].has_value() &&
440  condition(*positionToValueDim[nextPos])) {
441  projectOut(nextPos);
442  // The column was projected out so another column is now at that position.
443  // Do not increase the counter.
444  } else {
445  ++nextPos;
446  }
447  }
448 }
449 
451  std::optional<int64_t> except) {
452  int64_t nextPos = 0;
453  while (nextPos < static_cast<int64_t>(positionToValueDim.size())) {
454  if (positionToValueDim[nextPos].has_value() || except == nextPos) {
455  ++nextPos;
456  } else {
457  projectOut(nextPos);
458  // The column was projected out so another column is now at that position.
459  // Do not increase the counter.
460  }
461  }
462 }
463 
465  AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type,
466  const Variable &var, StopConditionFn stopCondition, bool closedUB) {
467  MLIRContext *ctx = var.getContext();
468  int64_t ubAdjustment = closedUB ? 0 : 1;
469  Builder b(ctx);
470  mapOperands.clear();
471 
472  // Process the backward slice of `value` (i.e., reverse use-def chain) until
473  // `stopCondition` is met.
475  int64_t pos = cstr.insert(var, /*isSymbol=*/false);
476  assert(pos == 0 && "expected first column");
477  cstr.processWorklist();
478 
479  // Project out all variables (apart from `valueDim`) that do not match the
480  // stop condition.
481  cstr.projectOut([&](ValueDim p) {
482  auto maybeDim =
483  p.second == kIndexValue ? std::nullopt : std::make_optional(p.second);
484  return !stopCondition(p.first, maybeDim, cstr);
485  });
486  cstr.projectOutAnonymous(/*except=*/pos);
487 
488  // Compute lower and upper bounds for `valueDim`.
489  SmallVector<AffineMap> lb(1), ub(1);
490  cstr.cstr.getSliceBounds(pos, 1, ctx, &lb, &ub,
491  /*closedUB=*/true);
492 
493  // Note: There are TODOs in the implementation of `getSliceBounds`. In such a
494  // case, no lower/upper bound can be computed at the moment.
495  // EQ, UB bounds: upper bound is needed.
496  if ((type != BoundType::LB) &&
497  (ub.empty() || !ub[0] || ub[0].getNumResults() == 0))
498  return failure();
499  // EQ, LB bounds: lower bound is needed.
500  if ((type != BoundType::UB) &&
501  (lb.empty() || !lb[0] || lb[0].getNumResults() == 0))
502  return failure();
503 
504  // TODO: Generate an affine map with multiple results.
505  if (type != BoundType::LB)
506  assert(ub.size() == 1 && ub[0].getNumResults() == 1 &&
507  "multiple bounds not supported");
508  if (type != BoundType::UB)
509  assert(lb.size() == 1 && lb[0].getNumResults() == 1 &&
510  "multiple bounds not supported");
511 
512  // EQ bound: lower and upper bound must match.
513  if (type == BoundType::EQ && ub[0] != lb[0])
514  return failure();
515 
517  if (type == BoundType::EQ || type == BoundType::LB) {
518  bound = lb[0];
519  } else {
520  // Computed UB is a closed bound.
521  bound = AffineMap::get(ub[0].getNumDims(), ub[0].getNumSymbols(),
522  ub[0].getResult(0) + ubAdjustment);
523  }
524 
525  // Gather all SSA values that are used in the computed bound.
526  assert(cstr.cstr.getNumDimAndSymbolVars() == cstr.positionToValueDim.size() &&
527  "inconsistent mapping state");
528  SmallVector<AffineExpr> replacementDims, replacementSymbols;
529  int64_t numDims = 0, numSymbols = 0;
530  for (int64_t i = 0; i < cstr.cstr.getNumDimAndSymbolVars(); ++i) {
531  // Skip `value`.
532  if (i == pos)
533  continue;
534  // Check if the position `i` is used in the generated bound. If so, it must
535  // be included in the generated affine.apply op.
536  bool used = false;
537  bool isDim = i < cstr.cstr.getNumDimVars();
538  if (isDim) {
539  if (bound.isFunctionOfDim(i))
540  used = true;
541  } else {
542  if (bound.isFunctionOfSymbol(i - cstr.cstr.getNumDimVars()))
543  used = true;
544  }
545 
546  if (!used) {
547  // Not used: Remove dim/symbol from the result.
548  if (isDim) {
549  replacementDims.push_back(b.getAffineConstantExpr(0));
550  } else {
551  replacementSymbols.push_back(b.getAffineConstantExpr(0));
552  }
553  continue;
554  }
555 
556  if (isDim) {
557  replacementDims.push_back(b.getAffineDimExpr(numDims++));
558  } else {
559  replacementSymbols.push_back(b.getAffineSymbolExpr(numSymbols++));
560  }
561 
562  assert(cstr.positionToValueDim[i].has_value() &&
563  "cannot build affine map in terms of anonymous column");
564  ValueBoundsConstraintSet::ValueDim valueDim = *cstr.positionToValueDim[i];
565  Value value = valueDim.first;
566  int64_t dim = valueDim.second;
568  // An index-type value is used: can be used directly in the affine.apply
569  // op.
570  assert(value.getType().isIndex() && "expected index type");
571  mapOperands.push_back(std::make_pair(value, std::nullopt));
572  continue;
573  }
574 
575  assert(cast<ShapedType>(value.getType()).isDynamicDim(dim) &&
576  "expected dynamic dim");
577  mapOperands.push_back(std::make_pair(value, dim));
578  }
579 
580  resultMap = bound.replaceDimsAndSymbols(replacementDims, replacementSymbols,
581  numDims, numSymbols);
582  return success();
583 }
584 
586  AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type,
587  const Variable &var, ValueDimList dependencies, bool closedUB) {
588  return computeBound(
589  resultMap, mapOperands, type, var,
590  [&](Value v, std::optional<int64_t> d, ValueBoundsConstraintSet &cstr) {
591  return llvm::is_contained(dependencies, std::make_pair(v, d));
592  },
593  closedUB);
594 }
595 
597  AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type,
598  const Variable &var, ValueRange independencies, bool closedUB) {
599  // Return "true" if the given value is independent of all values in
600  // `independencies`. I.e., neither the value itself nor any value in the
601  // backward slice (reverse use-def chain) is contained in `independencies`.
602  auto isIndependent = [&](Value v) {
604  DenseSet<Value> visited;
605  worklist.push_back(v);
606  while (!worklist.empty()) {
607  Value next = worklist.pop_back_val();
608  if (!visited.insert(next).second)
609  continue;
610  if (llvm::is_contained(independencies, next))
611  return false;
612  // TODO: DominanceInfo could be used to stop the traversal early.
613  Operation *op = next.getDefiningOp();
614  if (!op)
615  continue;
616  worklist.append(op->getOperands().begin(), op->getOperands().end());
617  }
618  return true;
619  };
620 
621  // Reify bounds in terms of any independent values.
622  return computeBound(
623  resultMap, mapOperands, type, var,
624  [&](Value v, std::optional<int64_t> d, ValueBoundsConstraintSet &cstr) {
625  return isIndependent(v);
626  },
627  closedUB);
628 }
629 
631  presburger::BoundType type, const Variable &var,
632  StopConditionFn stopCondition, bool closedUB) {
633  // Default stop condition if none was specified: Keep adding constraints until
634  // a bound could be computed.
635  int64_t pos = 0;
636  auto defaultStopCondition = [&](Value v, std::optional<int64_t> dim,
638  return cstr.cstr.getConstantBound64(type, pos).has_value();
639  };
640 
642  var.getContext(), stopCondition ? stopCondition : defaultStopCondition);
643  pos = cstr.populateConstraints(var.map, var.mapOperands);
644  assert(pos == 0 && "expected `map` is the first column");
645 
646  // Compute constant bound for `valueDim`.
647  int64_t ubAdjustment = closedUB ? 0 : 1;
648  if (auto bound = cstr.cstr.getConstantBound64(type, pos))
649  return type == BoundType::UB ? *bound + ubAdjustment : *bound;
650  return failure();
651 }
652 
654  std::optional<int64_t> dim) {
655 #ifndef NDEBUG
656  assertValidValueDim(value, dim);
657 #endif // NDEBUG
658 
659  // `getExpr` pushes the value/dim onto the worklist (unless it was already
660  // analyzed).
661  (void)getExpr(value, dim);
662  // Process all values/dims on the worklist. This may traverse and analyze
663  // additional IR, depending the current stop function.
664  processWorklist();
665 }
666 
668  ValueDimList operands) {
669  int64_t pos = insert(map, operands, /*isSymbol=*/false);
670  // Process the backward slice of `operands` (i.e., reverse use-def chain)
671  // until `stopCondition` is met.
672  processWorklist();
673  return pos;
674 }
675 
676 FailureOr<int64_t>
678  std::optional<int64_t> dim1,
679  std::optional<int64_t> dim2) {
680 #ifndef NDEBUG
681  assertValidValueDim(value1, dim1);
682  assertValidValueDim(value2, dim2);
683 #endif // NDEBUG
684 
685  Builder b(value1.getContext());
686  AffineMap map = AffineMap::get(/*dimCount=*/2, /*symbolCount=*/0,
687  b.getAffineDimExpr(0) - b.getAffineDimExpr(1));
689  Variable(map, {{value1, dim1}, {value2, dim2}}));
690 }
691 
693  ComparisonOperator cmp,
694  int64_t rhsPos) {
695  // This function returns "true" if "lhs CMP rhs" is proven to hold.
696  //
697  // Example for ComparisonOperator::LE and index-typed values: We would like to
698  // prove that lhs <= rhs. Proof by contradiction: add the inverse
699  // relation (lhs > rhs) to the constraint set and check if the resulting
700  // constraint set is "empty" (i.e. has no solution). In that case,
701  // lhs > rhs must be incorrect and we can deduce that lhs <= rhs holds.
702 
703  // We cannot prove anything if the constraint set is already empty.
704  if (cstr.isEmpty()) {
705  LLVM_DEBUG(
706  llvm::dbgs()
707  << "cannot compare value/dims: constraint system is already empty");
708  return false;
709  }
710 
711  // EQ can be expressed as LE and GE.
712  if (cmp == EQ)
713  return comparePos(lhsPos, ComparisonOperator::LE, rhsPos) &&
714  comparePos(lhsPos, ComparisonOperator::GE, rhsPos);
715 
716  // Construct inequality.
718  if (cmp == LT || cmp == LE) {
719  ++eq[lhsPos];
720  --eq[rhsPos];
721  } else if (cmp == GT || cmp == GE) {
722  --eq[lhsPos];
723  ++eq[rhsPos];
724  } else {
725  llvm_unreachable("unsupported comparison operator");
726  }
727  if (cmp == LE || cmp == GE)
728  eq[cstr.getNumCols() - 1] -= 1;
729 
730  // Add inequality to the constraint set and check if it made the constraint
731  // set empty.
732  int64_t ineqPos = cstr.getNumInequalities();
733  cstr.addInequality(eq);
734  bool isEmpty = cstr.isEmpty();
735  cstr.removeInequality(ineqPos);
736  return isEmpty;
737 }
738 
740  int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos) {
741  auto strongCmp = [&](ComparisonOperator cmp,
742  ComparisonOperator negCmp) -> FailureOr<bool> {
743  if (comparePos(lhsPos, cmp, rhsPos))
744  return true;
745  if (comparePos(lhsPos, negCmp, rhsPos))
746  return false;
747  return failure();
748  };
749  switch (cmp) {
750  case ComparisonOperator::LT:
751  return strongCmp(ComparisonOperator::LT, ComparisonOperator::GE);
752  case ComparisonOperator::LE:
753  return strongCmp(ComparisonOperator::LE, ComparisonOperator::GT);
754  case ComparisonOperator::GT:
755  return strongCmp(ComparisonOperator::GT, ComparisonOperator::LE);
756  case ComparisonOperator::GE:
757  return strongCmp(ComparisonOperator::GE, ComparisonOperator::LT);
758  case ComparisonOperator::EQ: {
759  std::optional<bool> le =
760  strongComparePos(lhsPos, ComparisonOperator::LE, rhsPos);
761  if (!le)
762  return failure();
763  if (!*le)
764  return false;
765  std::optional<bool> ge =
766  strongComparePos(lhsPos, ComparisonOperator::GE, rhsPos);
767  if (!ge)
768  return failure();
769  if (!*ge)
770  return false;
771  return true;
772  }
773  }
774  llvm_unreachable("invalid comparison operator");
775 }
776 
778  ComparisonOperator cmp,
779  const Variable &rhs) {
780  int64_t lhsPos = populateConstraints(lhs.map, lhs.mapOperands);
781  int64_t rhsPos = populateConstraints(rhs.map, rhs.mapOperands);
782  return comparePos(lhsPos, cmp, rhsPos);
783 }
784 
786  ComparisonOperator cmp,
787  const Variable &rhs) {
788  int64_t lhsPos = -1, rhsPos = -1;
789  auto stopCondition = [&](Value v, std::optional<int64_t> dim,
791  // Keep processing as long as lhs/rhs were not processed.
792  if (size_t(lhsPos) >= cstr.positionToValueDim.size() ||
793  size_t(rhsPos) >= cstr.positionToValueDim.size())
794  return false;
795  // Keep processing as long as the relation cannot be proven.
796  return cstr.comparePos(lhsPos, cmp, rhsPos);
797  };
799  lhsPos = cstr.populateConstraints(lhs.map, lhs.mapOperands);
800  rhsPos = cstr.populateConstraints(rhs.map, rhs.mapOperands);
801  return cstr.comparePos(lhsPos, cmp, rhsPos);
802 }
803 
805  ComparisonOperator cmp,
806  const Variable &rhs) {
807  int64_t lhsPos = -1, rhsPos = -1;
808  auto stopCondition = [&](Value v, std::optional<int64_t> dim,
810  // Keep processing as long as lhs/rhs were not processed.
811  if (size_t(lhsPos) >= cstr.positionToValueDim.size() ||
812  size_t(rhsPos) >= cstr.positionToValueDim.size())
813  return false;
814  // Keep processing as long as the strong relation cannot be proven.
815  FailureOr<bool> ordered = cstr.strongComparePos(lhsPos, cmp, rhsPos);
816  return failed(ordered) ? true : false;
817  };
819  lhsPos = cstr.populateConstraints(lhs.map, lhs.mapOperands);
820  rhsPos = cstr.populateConstraints(rhs.map, rhs.mapOperands);
821  return cstr.strongComparePos(lhsPos, cmp, rhsPos);
822 }
823 
824 FailureOr<bool> ValueBoundsConstraintSet::areEqual(const Variable &var1,
825  const Variable &var2) {
826  return strongCompare(var1, ComparisonOperator::EQ, var2);
827 }
828 
829 FailureOr<bool>
831  HyperrectangularSlice slice1,
832  HyperrectangularSlice slice2) {
833  assert(slice1.getMixedOffsets().size() == slice2.getMixedOffsets().size() &&
834  "expected slices of same rank");
835  assert(slice1.getMixedSizes().size() == slice2.getMixedSizes().size() &&
836  "expected slices of same rank");
837  assert(slice1.getMixedStrides().size() == slice2.getMixedStrides().size() &&
838  "expected slices of same rank");
839 
840  Builder b(ctx);
841  bool foundUnknownBound = false;
842  for (int64_t i = 0, e = slice1.getMixedOffsets().size(); i < e; ++i) {
843  AffineMap map =
844  AffineMap::get(/*dimCount=*/0, /*symbolCount=*/4,
845  b.getAffineSymbolExpr(0) +
847  b.getAffineSymbolExpr(3));
848  {
849  // Case 1: Slices are guaranteed to be non-overlapping if
850  // offset1 + size1 * stride1 <= offset2 (for at least one dimension).
851  SmallVector<OpFoldResult> ofrOperands;
852  ofrOperands.push_back(slice1.getMixedOffsets()[i]);
853  ofrOperands.push_back(slice1.getMixedSizes()[i]);
854  ofrOperands.push_back(slice1.getMixedStrides()[i]);
855  ofrOperands.push_back(slice2.getMixedOffsets()[i]);
856  SmallVector<Value> valueOperands;
857  AffineMap foldedMap =
858  foldAttributesIntoMap(b, map, ofrOperands, valueOperands);
859  FailureOr<int64_t> constBound = computeConstantBound(
860  presburger::BoundType::EQ, Variable(foldedMap, valueOperands));
861  foundUnknownBound |= failed(constBound);
862  if (succeeded(constBound) && *constBound <= 0)
863  return false;
864  }
865  {
866  // Case 2: Slices are guaranteed to be non-overlapping if
867  // offset2 + size2 * stride2 <= offset1 (for at least one dimension).
868  SmallVector<OpFoldResult> ofrOperands;
869  ofrOperands.push_back(slice2.getMixedOffsets()[i]);
870  ofrOperands.push_back(slice2.getMixedSizes()[i]);
871  ofrOperands.push_back(slice2.getMixedStrides()[i]);
872  ofrOperands.push_back(slice1.getMixedOffsets()[i]);
873  SmallVector<Value> valueOperands;
874  AffineMap foldedMap =
875  foldAttributesIntoMap(b, map, ofrOperands, valueOperands);
876  FailureOr<int64_t> constBound = computeConstantBound(
877  presburger::BoundType::EQ, Variable(foldedMap, valueOperands));
878  foundUnknownBound |= failed(constBound);
879  if (succeeded(constBound) && *constBound <= 0)
880  return false;
881  }
882  }
883 
884  // If at least one bound could not be computed, we cannot be certain that the
885  // slices are really overlapping.
886  if (foundUnknownBound)
887  return failure();
888 
889  // All bounds could be computed and none of the above cases applied.
890  // Therefore, the slices are guaranteed to overlap.
891  return true;
892 }
893 
894 FailureOr<bool>
896  HyperrectangularSlice slice1,
897  HyperrectangularSlice slice2) {
898  assert(slice1.getMixedOffsets().size() == slice2.getMixedOffsets().size() &&
899  "expected slices of same rank");
900  assert(slice1.getMixedSizes().size() == slice2.getMixedSizes().size() &&
901  "expected slices of same rank");
902  assert(slice1.getMixedStrides().size() == slice2.getMixedStrides().size() &&
903  "expected slices of same rank");
904 
905  // The two slices are equivalent if all of their offsets, sizes and strides
906  // are equal. If equality cannot be determined for at least one of those
907  // values, equivalence cannot be determined and this function returns
908  // "failure".
909  for (auto [offset1, offset2] :
910  llvm::zip_equal(slice1.getMixedOffsets(), slice2.getMixedOffsets())) {
911  FailureOr<bool> equal = areEqual(offset1, offset2);
912  if (failed(equal))
913  return failure();
914  if (!equal.value())
915  return false;
916  }
917  for (auto [size1, size2] :
918  llvm::zip_equal(slice1.getMixedSizes(), slice2.getMixedSizes())) {
919  FailureOr<bool> equal = areEqual(size1, size2);
920  if (failed(equal))
921  return failure();
922  if (!equal.value())
923  return false;
924  }
925  for (auto [stride1, stride2] :
926  llvm::zip_equal(slice1.getMixedStrides(), slice2.getMixedStrides())) {
927  FailureOr<bool> equal = areEqual(stride1, stride2);
928  if (failed(equal))
929  return failure();
930  if (!equal.value())
931  return false;
932  }
933  return true;
934 }
935 
937  llvm::errs() << "==========\nColumns:\n";
938  llvm::errs() << "(column\tdim\tvalue)\n";
939  for (auto [index, valueDim] : llvm::enumerate(positionToValueDim)) {
940  llvm::errs() << " " << index << "\t";
941  if (valueDim) {
942  if (valueDim->second == kIndexValue) {
943  llvm::errs() << "n/a\t";
944  } else {
945  llvm::errs() << valueDim->second << "\t";
946  }
947  llvm::errs() << getOwnerOfValue(valueDim->first)->getName() << " ";
948  if (OpResult result = dyn_cast<OpResult>(valueDim->first)) {
949  llvm::errs() << "(result " << result.getResultNumber() << ")";
950  } else {
951  llvm::errs() << "(bbarg "
952  << cast<BlockArgument>(valueDim->first).getArgNumber()
953  << ")";
954  }
955  llvm::errs() << "\n";
956  } else {
957  llvm::errs() << "n/a\tn/a\n";
958  }
959  }
960  llvm::errs() << "\nConstraint set:\n";
961  cstr.dump();
962  llvm::errs() << "==========\n";
963 }
964 
967  assert(!this->dim.has_value() && "dim was already set");
968  this->dim = dim;
969 #ifndef NDEBUG
970  assertValidValueDim(value, this->dim);
971 #endif // NDEBUG
972  return *this;
973 }
974 
976 #ifndef NDEBUG
977  assertValidValueDim(value, this->dim);
978 #endif // NDEBUG
979  cstr.addBound(BoundType::UB, cstr.getPos(value, this->dim), expr);
980 }
981 
983  operator<(expr + 1);
984 }
985 
987  operator>=(expr + 1);
988 }
989 
991 #ifndef NDEBUG
992  assertValidValueDim(value, this->dim);
993 #endif // NDEBUG
994  cstr.addBound(BoundType::LB, cstr.getPos(value, this->dim), expr);
995 }
996 
998 #ifndef NDEBUG
999  assertValidValueDim(value, this->dim);
1000 #endif // NDEBUG
1001  cstr.addBound(BoundType::EQ, cstr.getPos(value, this->dim), expr);
1002 }
1003 
1005  operator<(cstr.getExpr(ofr));
1006 }
1007 
1009  operator<=(cstr.getExpr(ofr));
1010 }
1011 
1013  operator>(cstr.getExpr(ofr));
1014 }
1015 
1017  operator>=(cstr.getExpr(ofr));
1018 }
1019 
1021  operator==(cstr.getExpr(ofr));
1022 }
1023 
1025  operator<(cstr.getExpr(i));
1026 }
1027 
1029  operator<=(cstr.getExpr(i));
1030 }
1031 
1033  operator>(cstr.getExpr(i));
1034 }
1035 
1037  operator>=(cstr.getExpr(i));
1038 }
1039 
1041  operator==(cstr.getExpr(i));
1042 }
static Operation * getOwnerOfValue(Value value)
static void assertValidValueDim(Value value, std::optional< int64_t > dim)
Base type for affine expression.
Definition: AffineExpr.h:68
AffineExpr replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements) const
This method substitutes any uses of dimensions and symbols (e.g.
Definition: AffineExpr.cpp:89
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:46
MLIRContext * getContext() const
Definition: AffineMap.cpp:339
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumSymbols() const
Definition: AffineMap.cpp:394
unsigned getNumDims() const
Definition: AffineMap.cpp:390
unsigned getNumResults() const
Definition: AffineMap.cpp:398
AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const
This method substitutes any uses of dimensions and symbols (e.g.
Definition: AffineMap.cpp:496
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:407
AffineMap replace(AffineExpr expr, AffineExpr replacement, unsigned numResultDims, unsigned numResultSyms) const
Sparse replace method.
Definition: AffineMap.cpp:511
Attributes are known-constant values of operations.
Definition: Attributes.h:25
This class is a general helper class for creating context-global objects like types,...
Definition: Builders.h:50
AffineExpr getAffineSymbolExpr(unsigned position)
Definition: Builders.cpp:363
AffineExpr getAffineConstantExpr(int64_t constant)
Definition: Builders.cpp:367
AffineExpr getAffineDimExpr(unsigned position)
Definition: Builders.cpp:359
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
A hyperrectangular slice, represented as a list of offsets, sizes and strides.
HyperrectangularSlice(ArrayRef< OpFoldResult > offsets, ArrayRef< OpFoldResult > sizes, ArrayRef< OpFoldResult > strides)
ArrayRef< OpFoldResult > getMixedOffsets() const
ArrayRef< OpFoldResult > getMixedSizes() const
ArrayRef< OpFoldResult > getMixedStrides() const
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
This class represents a single result from folding an operation.
Definition: OpDefinition.h:271
MLIRContext * getContext() const
Definition: OpDefinition.h:277
This is a value defined by a result of an operation.
Definition: Value.h:447
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:234
OperationName getName()
The name of an operation is the key identifier for it.
Definition: Operation.h:119
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:378
bool isIndex() const
Definition: Types.cpp:54
Helper class that builds a bound for a shaped value dimension or index-typed value.
BoundBuilder & operator[](int64_t dim)
Specify a dimension, assuming that the underlying value is a shaped value.
A variable that can be added to the constraint set as a "column".
Variable(OpFoldResult ofr)
Construct a variable for an index-typed attribute or SSA value.
A helper class to be used with ValueBoundsOpInterface.
static bool compare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
Return "true" if "lhs cmp rhs" was proven to hold.
static FailureOr< bool > areEqual(const Variable &var1, const Variable &var2)
Compute whether the given variables are equal.
DenseMap< ValueDim, int64_t > valueDimToPosition
Reverse mapping of values/shape dimensions to columns.
void processWorklist()
Iteratively process all elements on the worklist until an index-typed value or shaped value meets sto...
bool addConservativeSemiAffineBounds
Should conservative bounds be added for semi-affine expressions.
AffineExpr getExpr(Value value, std::optional< int64_t > dim=std::nullopt)
Return an expression that represents the given index-typed value or shaped value dimension.
SmallVector< std::optional< ValueDim > > positionToValueDim
Mapping of columns to values/shape dimensions.
static LogicalResult computeIndependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueRange independencies, bool closedUB=false)
Compute a bound in that is independent of all values in independencies.
ValueBoundsConstraintSet(MLIRContext *ctx, StopConditionFn stopCondition, bool addConservativeSemiAffineBounds=false)
void projectOut(int64_t pos)
Project out the given column in the constraint set.
static FailureOr< int64_t > computeConstantDelta(Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
Compute a constant delta between the given two values.
static llvm::FailureOr< bool > strongCompare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
This function is similar to ValueBoundsConstraintSet::compare, except that it returns false if !...
void addBound(presburger::BoundType type, int64_t pos, AffineExpr expr)
Bound the given column in the underlying constraint set by the given expression.
StopConditionFn stopCondition
The current stop condition function.
ComparisonOperator
Comparison operator for ValueBoundsConstraintSet::compare.
BoundBuilder bound(Value value)
Add a bound for the given index-typed value or shaped value.
static LogicalResult computeBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, StopConditionFn stopCondition, bool closedUB=false)
Compute a bound for the given variable.
int64_t getPos(Value value, std::optional< int64_t > dim=std::nullopt) const
Return the column position of the given value/dimension.
int64_t insert(Value value, std::optional< int64_t > dim, bool isSymbol=true, bool addToWorklist=true)
Insert a value/dimension into the constraint set.
bool comparePos(int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)
Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to ho...
static FailureOr< int64_t > computeConstantBound(presburger::BoundType type, const Variable &var, StopConditionFn stopCondition=nullptr, bool closedUB=false)
Compute a constant bound for the given variable.
void dump() const
Debugging only: Dump the constraint set and the column-to-value/dim mapping to llvm::errs.
std::queue< int64_t > worklist
Worklist of values/shape dimensions that have not been processed yet.
FlatLinearConstraints cstr
Constraint system of equalities and inequalities.
bool isMapped(Value value, std::optional< int64_t > dim=std::nullopt) const
Return "true" if the given value/dim is mapped (i.e., has a corresponding column in the constraint sy...
llvm::FailureOr< bool > strongComparePos(int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)
Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to ho...
AffineExpr getPosExpr(int64_t pos)
Return an affine expression that represents column pos in the constraint set.
void projectOutAnonymous(std::optional< int64_t > except=std::nullopt)
static FailureOr< bool > areEquivalentSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be equivalent.
std::pair< Value, int64_t > ValueDim
An index-typed value or the dimension of a shaped-type value.
void populateConstraints(Value value, std::optional< int64_t > dim)
Traverse the IR starting from the given value/dim and populate constraints as long as the stop condit...
static FailureOr< bool > areOverlappingSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be overlapping.
std::function< bool(Value, std::optional< int64_t >, ValueBoundsConstraintSet &cstr)> StopConditionFn
The stop condition when traversing the backward slice of a shaped value/ index-type value.
Builder builder
Builder for constructing affine expressions.
bool populateAndCompare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
Populate constraints for lhs/rhs (until the stop condition is met).
static constexpr int64_t kIndexValue
Dimension identifier to indicate a value is index-typed.
static LogicalResult computeDependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueDimList dependencies, bool closedUB=false)
Compute a bound in terms of the values/dimensions in dependencies.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
MLIRContext * getContext() const
Utility to get the associated MLIRContext that this value is defined in.
Definition: Value.h:108
Type getType() const
Return the type of this value.
Definition: Value.h:105
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned appendVar(VarKind kind, unsigned num=1)
Append num variables of the specified kind after the last variable of that kind.
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
unsigned getNumCols() const
Returns the number of columns in the constraint system.
void projectOut(unsigned pos, unsigned num)
Projects out (aka eliminates) num variables starting at position pos.
void addInequality(ArrayRef< DynamicAPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
The OpAsmOpInterface, see OpAsmInterface.td for more details.
Definition: CallGraph.h:229
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:344
SmallVector< OpFoldResult > getMixedSizes(OpBuilder &builder, Location loc, Value value)
Return the dimensions of the given memref value.
Definition: MemRefOps.cpp:77
BoundType
The type of bound: equal, lower bound or upper bound.
VarKind
Kind of variable.
bool operator>(const Fraction &x, const Fraction &y)
Definition: Fraction.h:99
bool operator<(const Fraction &x, const Fraction &y)
Definition: Fraction.h:83
bool operator>=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:103
bool operator<=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:87
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
Definition: Matchers.h:490
detail::constant_int_value_binder m_ConstantInt(IntegerAttr::ValueType *bind_value)
Matches a constant holding a scalar/vector/tensor integer (splat) and writes the integer value to bin...
Definition: Matchers.h:527
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
bool operator==(StringAttr lhs, std::nullptr_t)
Define comparisons for StringAttr against nullptr and itself to avoid the StringRef overloads from be...
SmallVector< std::pair< Value, std::optional< int64_t > >> ValueDimList
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
AffineMap foldAttributesIntoMap(Builder &b, AffineMap map, ArrayRef< OpFoldResult > operands, SmallVector< Value > &remainingValues)
Fold all attributes among the given operands into the affine map.
Definition: AffineMap.cpp:738