MLIR  18.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 
30  ArrayRef<OpFoldResult> strides)
31  : mixedOffsets(offsets), mixedSizes(sizes), mixedStrides(strides) {
32  assert(offsets.size() == sizes.size() &&
33  "expected same number of offsets, sizes, strides");
34  assert(offsets.size() == strides.size() &&
35  "expected same number of offsets, sizes, strides");
36 }
37 
40  : mixedOffsets(offsets), mixedSizes(sizes) {
41  assert(offsets.size() == sizes.size() &&
42  "expected same number of offsets and sizes");
43  // Assume that all strides are 1.
44  if (offsets.empty())
45  return;
46  MLIRContext *ctx = offsets.front().getContext();
47  mixedStrides.append(offsets.size(), Builder(ctx).getIndexAttr(1));
48 }
49 
50 HyperrectangularSlice::HyperrectangularSlice(OffsetSizeAndStrideOpInterface op)
51  : HyperrectangularSlice(op.getMixedOffsets(), op.getMixedSizes(),
52  op.getMixedStrides()) {}
53 
54 /// If ofr is a constant integer or an IntegerAttr, return the integer.
55 static std::optional<int64_t> getConstantIntValue(OpFoldResult ofr) {
56  // Case 1: Check for Constant integer.
57  if (auto val = llvm::dyn_cast_if_present<Value>(ofr)) {
58  APSInt intVal;
59  if (matchPattern(val, m_ConstantInt(&intVal)))
60  return intVal.getSExtValue();
61  return std::nullopt;
62  }
63  // Case 2: Check for IntegerAttr.
64  Attribute attr = llvm::dyn_cast_if_present<Attribute>(ofr);
65  if (auto intAttr = dyn_cast_or_null<IntegerAttr>(attr))
66  return intAttr.getValue().getSExtValue();
67  return std::nullopt;
68 }
69 
71  : builder(ctx) {}
72 
73 #ifndef NDEBUG
74 static void assertValidValueDim(Value value, std::optional<int64_t> dim) {
75  if (value.getType().isIndex()) {
76  assert(!dim.has_value() && "invalid dim value");
77  } else if (auto shapedType = dyn_cast<ShapedType>(value.getType())) {
78  assert(*dim >= 0 && "invalid dim value");
79  if (shapedType.hasRank())
80  assert(*dim < shapedType.getRank() && "invalid dim value");
81  } else {
82  llvm_unreachable("unsupported type");
83  }
84 }
85 #endif // NDEBUG
86 
88  AffineExpr expr) {
89  LogicalResult status = cstr.addBound(
90  type, pos,
92  if (failed(status)) {
93  // Non-pure (e.g., semi-affine) expressions are not yet supported by
94  // FlatLinearConstraints. However, we can just ignore such failures here.
95  // Even without this bound, there may be enough information in the
96  // constraint system to compute the requested bound. In case this bound is
97  // actually needed, `computeBound` will return `failure`.
98  LLVM_DEBUG(llvm::dbgs() << "Failed to add bound: " << expr << "\n");
99  }
100 }
101 
103  std::optional<int64_t> dim) {
104 #ifndef NDEBUG
105  assertValidValueDim(value, dim);
106 #endif // NDEBUG
107 
108  auto shapedType = dyn_cast<ShapedType>(value.getType());
109  if (shapedType) {
110  // Static dimension: return constant directly.
111  if (shapedType.hasRank() && !shapedType.isDynamicDim(*dim))
112  return builder.getAffineConstantExpr(shapedType.getDimSize(*dim));
113  } else {
114  // Constant index value: return directly.
115  if (auto constInt = ::getConstantIntValue(value))
116  return builder.getAffineConstantExpr(*constInt);
117  }
118 
119  // Dynamic value: add to constraint set.
120  ValueDim valueDim = std::make_pair(value, dim.value_or(kIndexValue));
121  if (!valueDimToPosition.contains(valueDim))
122  (void)insert(value, dim);
123  int64_t pos = getPos(value, dim);
124  return pos < cstr.getNumDimVars()
127 }
128 
130  if (Value value = llvm::dyn_cast_if_present<Value>(ofr))
131  return getExpr(value, /*dim=*/std::nullopt);
132  auto constInt = ::getConstantIntValue(ofr);
133  assert(constInt.has_value() && "expected Integer constant");
134  return builder.getAffineConstantExpr(*constInt);
135 }
136 
138  return builder.getAffineConstantExpr(constant);
139 }
140 
142  std::optional<int64_t> dim,
143  bool isSymbol) {
144 #ifndef NDEBUG
145  assertValidValueDim(value, dim);
146 #endif // NDEBUG
147 
148  ValueDim valueDim = std::make_pair(value, dim.value_or(kIndexValue));
149  assert(!valueDimToPosition.contains(valueDim) && "already mapped");
150  int64_t pos = isSymbol ? cstr.appendVar(VarKind::Symbol)
151  : cstr.appendVar(VarKind::SetDim);
152  positionToValueDim.insert(positionToValueDim.begin() + pos, valueDim);
153  // Update reverse mapping.
154  for (int64_t i = pos, e = positionToValueDim.size(); i < e; ++i)
155  if (positionToValueDim[i].has_value())
157 
158  worklist.push(pos);
159  return pos;
160 }
161 
162 int64_t ValueBoundsConstraintSet::insert(bool isSymbol) {
163  int64_t pos = isSymbol ? cstr.appendVar(VarKind::Symbol)
164  : cstr.appendVar(VarKind::SetDim);
165  positionToValueDim.insert(positionToValueDim.begin() + pos, std::nullopt);
166  // Update reverse mapping.
167  for (int64_t i = pos, e = positionToValueDim.size(); i < e; ++i)
168  if (positionToValueDim[i].has_value())
170  return pos;
171 }
172 
174  std::optional<int64_t> dim) const {
175 #ifndef NDEBUG
176  assertValidValueDim(value, dim);
177  assert((isa<OpResult>(value) ||
178  cast<BlockArgument>(value).getOwner()->isEntryBlock()) &&
179  "unstructured control flow is not supported");
180 #endif // NDEBUG
181 
182  auto it =
183  valueDimToPosition.find(std::make_pair(value, dim.value_or(kIndexValue)));
184  assert(it != valueDimToPosition.end() && "expected mapped entry");
185  return it->second;
186 }
187 
189  if (auto bbArg = dyn_cast<BlockArgument>(value))
190  return bbArg.getOwner()->getParentOp();
191  return value.getDefiningOp();
192 }
193 
195  while (!worklist.empty()) {
196  int64_t pos = worklist.front();
197  worklist.pop();
198  assert(positionToValueDim[pos].has_value() &&
199  "did not expect std::nullopt on worklist");
200  ValueDim valueDim = *positionToValueDim[pos];
201  Value value = valueDim.first;
202  int64_t dim = valueDim.second;
203 
204  // Check for static dim size.
205  if (dim != kIndexValue) {
206  auto shapedType = cast<ShapedType>(value.getType());
207  if (shapedType.hasRank() && !shapedType.isDynamicDim(dim)) {
208  bound(value)[dim] == getExpr(shapedType.getDimSize(dim));
209  continue;
210  }
211  }
212 
213  // Do not process any further if the stop condition is met.
214  auto maybeDim = dim == kIndexValue ? std::nullopt : std::make_optional(dim);
215  if (stopCondition(value, maybeDim))
216  continue;
217 
218  // Query `ValueBoundsOpInterface` for constraints. New items may be added to
219  // the worklist.
220  auto valueBoundsOp =
221  dyn_cast<ValueBoundsOpInterface>(getOwnerOfValue(value));
222  if (valueBoundsOp) {
223  if (dim == kIndexValue) {
224  valueBoundsOp.populateBoundsForIndexValue(value, *this);
225  } else {
226  valueBoundsOp.populateBoundsForShapedValueDim(value, dim, *this);
227  }
228  continue;
229  }
230 
231  // If the op does not implement `ValueBoundsOpInterface`, check if it
232  // implements the `DestinationStyleOpInterface`. OpResults of such ops are
233  // tied to OpOperands. Tied values have the same shape.
234  auto dstOp = value.getDefiningOp<DestinationStyleOpInterface>();
235  if (!dstOp || dim == kIndexValue)
236  continue;
237  Value tiedOperand = dstOp.getTiedOpOperand(cast<OpResult>(value))->get();
238  bound(value)[dim] == getExpr(tiedOperand, dim);
239  }
240 }
241 
243  assert(pos >= 0 && pos < static_cast<int64_t>(positionToValueDim.size()) &&
244  "invalid position");
245  cstr.projectOut(pos);
246  if (positionToValueDim[pos].has_value()) {
247  bool erased = valueDimToPosition.erase(*positionToValueDim[pos]);
248  (void)erased;
249  assert(erased && "inconsistent reverse mapping");
250  }
251  positionToValueDim.erase(positionToValueDim.begin() + pos);
252  // Update reverse mapping.
253  for (int64_t i = pos, e = positionToValueDim.size(); i < e; ++i)
254  if (positionToValueDim[i].has_value())
256 }
257 
259  function_ref<bool(ValueDim)> condition) {
260  int64_t nextPos = 0;
261  while (nextPos < static_cast<int64_t>(positionToValueDim.size())) {
262  if (positionToValueDim[nextPos].has_value() &&
263  condition(*positionToValueDim[nextPos])) {
264  projectOut(nextPos);
265  // The column was projected out so another column is now at that position.
266  // Do not increase the counter.
267  } else {
268  ++nextPos;
269  }
270  }
271 }
272 
274  AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type,
275  Value value, std::optional<int64_t> dim, StopConditionFn stopCondition,
276  bool closedUB) {
277 #ifndef NDEBUG
278  assertValidValueDim(value, dim);
279  assert(!stopCondition(value, dim) &&
280  "stop condition should not be satisfied for starting point");
281 #endif // NDEBUG
282 
283  int64_t ubAdjustment = closedUB ? 0 : 1;
284  Builder b(value.getContext());
285  mapOperands.clear();
286 
287  if (stopCondition(value, dim)) {
288  // Special case: If the stop condition is satisfied for the input
289  // value/dimension, directly return it.
290  mapOperands.push_back(std::make_pair(value, dim));
292  if (type == BoundType::UB)
293  bound = bound + ubAdjustment;
294  resultMap = AffineMap::get(/*dimCount=*/1, /*symbolCount=*/0,
295  b.getAffineDimExpr(0));
296  return success();
297  }
298 
299  // Process the backward slice of `value` (i.e., reverse use-def chain) until
300  // `stopCondition` is met.
301  ValueDim valueDim = std::make_pair(value, dim.value_or(kIndexValue));
303  int64_t pos = cstr.insert(value, dim, /*isSymbol=*/false);
304  cstr.processWorklist(stopCondition);
305 
306  // Project out all variables (apart from `valueDim`) that do not match the
307  // stop condition.
308  cstr.projectOut([&](ValueDim p) {
309  // Do not project out `valueDim`.
310  if (valueDim == p)
311  return false;
312  auto maybeDim =
313  p.second == kIndexValue ? std::nullopt : std::make_optional(p.second);
314  return !stopCondition(p.first, maybeDim);
315  });
316 
317  // Compute lower and upper bounds for `valueDim`.
318  SmallVector<AffineMap> lb(1), ub(1);
319  cstr.cstr.getSliceBounds(pos, 1, value.getContext(), &lb, &ub,
320  /*getClosedUB=*/true);
321 
322  // Note: There are TODOs in the implementation of `getSliceBounds`. In such a
323  // case, no lower/upper bound can be computed at the moment.
324  // EQ, UB bounds: upper bound is needed.
325  if ((type != BoundType::LB) &&
326  (ub.empty() || !ub[0] || ub[0].getNumResults() == 0))
327  return failure();
328  // EQ, LB bounds: lower bound is needed.
329  if ((type != BoundType::UB) &&
330  (lb.empty() || !lb[0] || lb[0].getNumResults() == 0))
331  return failure();
332 
333  // TODO: Generate an affine map with multiple results.
334  if (type != BoundType::LB)
335  assert(ub.size() == 1 && ub[0].getNumResults() == 1 &&
336  "multiple bounds not supported");
337  if (type != BoundType::UB)
338  assert(lb.size() == 1 && lb[0].getNumResults() == 1 &&
339  "multiple bounds not supported");
340 
341  // EQ bound: lower and upper bound must match.
342  if (type == BoundType::EQ && ub[0] != lb[0])
343  return failure();
344 
346  if (type == BoundType::EQ || type == BoundType::LB) {
347  bound = lb[0];
348  } else {
349  // Computed UB is a closed bound.
350  bound = AffineMap::get(ub[0].getNumDims(), ub[0].getNumSymbols(),
351  ub[0].getResult(0) + ubAdjustment);
352  }
353 
354  // Gather all SSA values that are used in the computed bound.
355  assert(cstr.cstr.getNumDimAndSymbolVars() == cstr.positionToValueDim.size() &&
356  "inconsistent mapping state");
357  SmallVector<AffineExpr> replacementDims, replacementSymbols;
358  int64_t numDims = 0, numSymbols = 0;
359  for (int64_t i = 0; i < cstr.cstr.getNumDimAndSymbolVars(); ++i) {
360  // Skip `value`.
361  if (i == pos)
362  continue;
363  // Check if the position `i` is used in the generated bound. If so, it must
364  // be included in the generated affine.apply op.
365  bool used = false;
366  bool isDim = i < cstr.cstr.getNumDimVars();
367  if (isDim) {
368  if (bound.isFunctionOfDim(i))
369  used = true;
370  } else {
371  if (bound.isFunctionOfSymbol(i - cstr.cstr.getNumDimVars()))
372  used = true;
373  }
374 
375  if (!used) {
376  // Not used: Remove dim/symbol from the result.
377  if (isDim) {
378  replacementDims.push_back(b.getAffineConstantExpr(0));
379  } else {
380  replacementSymbols.push_back(b.getAffineConstantExpr(0));
381  }
382  continue;
383  }
384 
385  if (isDim) {
386  replacementDims.push_back(b.getAffineDimExpr(numDims++));
387  } else {
388  replacementSymbols.push_back(b.getAffineSymbolExpr(numSymbols++));
389  }
390 
391  assert(cstr.positionToValueDim[i].has_value() &&
392  "cannot build affine map in terms of anonymous column");
393  ValueBoundsConstraintSet::ValueDim valueDim = *cstr.positionToValueDim[i];
394  Value value = valueDim.first;
395  int64_t dim = valueDim.second;
397  // An index-type value is used: can be used directly in the affine.apply
398  // op.
399  assert(value.getType().isIndex() && "expected index type");
400  mapOperands.push_back(std::make_pair(value, std::nullopt));
401  continue;
402  }
403 
404  assert(cast<ShapedType>(value.getType()).isDynamicDim(dim) &&
405  "expected dynamic dim");
406  mapOperands.push_back(std::make_pair(value, dim));
407  }
408 
409  resultMap = bound.replaceDimsAndSymbols(replacementDims, replacementSymbols,
410  numDims, numSymbols);
411  return success();
412 }
413 
415  AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type,
416  Value value, std::optional<int64_t> dim, ValueDimList dependencies,
417  bool closedUB) {
418  return computeBound(
419  resultMap, mapOperands, type, value, dim,
420  [&](Value v, std::optional<int64_t> d) {
421  return llvm::is_contained(dependencies, std::make_pair(v, d));
422  },
423  closedUB);
424 }
425 
427  AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type,
428  Value value, std::optional<int64_t> dim, ValueRange independencies,
429  bool closedUB) {
430  // Return "true" if the given value is independent of all values in
431  // `independencies`. I.e., neither the value itself nor any value in the
432  // backward slice (reverse use-def chain) is contained in `independencies`.
433  auto isIndependent = [&](Value v) {
435  DenseSet<Value> visited;
436  worklist.push_back(v);
437  while (!worklist.empty()) {
438  Value next = worklist.pop_back_val();
439  if (visited.contains(next))
440  continue;
441  visited.insert(next);
442  if (llvm::is_contained(independencies, next))
443  return false;
444  // TODO: DominanceInfo could be used to stop the traversal early.
445  Operation *op = next.getDefiningOp();
446  if (!op)
447  continue;
448  worklist.append(op->getOperands().begin(), op->getOperands().end());
449  }
450  return true;
451  };
452 
453  // Reify bounds in terms of any independent values.
454  return computeBound(
455  resultMap, mapOperands, type, value, dim,
456  [&](Value v, std::optional<int64_t> d) { return isIndependent(v); },
457  closedUB);
458 }
459 
461  presburger::BoundType type, Value value, std::optional<int64_t> dim,
462  StopConditionFn stopCondition, bool closedUB) {
463 #ifndef NDEBUG
464  assertValidValueDim(value, dim);
465 #endif // NDEBUG
466 
467  AffineMap map =
468  AffineMap::get(/*dimCount=*/1, /*symbolCount=*/0,
469  Builder(value.getContext()).getAffineDimExpr(0));
470  return computeConstantBound(type, map, {{value, dim}}, stopCondition,
471  closedUB);
472 }
473 
475  presburger::BoundType type, AffineMap map, ValueDimList operands,
476  StopConditionFn stopCondition, bool closedUB) {
477  assert(map.getNumResults() == 1 && "expected affine map with one result");
479  int64_t pos = cstr.insert(/*isSymbol=*/false);
480 
481  // Add map and operands to the constraint set. Dimensions are converted to
482  // symbols. All operands are added to the worklist.
483  auto mapper = [&](std::pair<Value, std::optional<int64_t>> v) {
484  return cstr.getExpr(v.first, v.second);
485  };
486  SmallVector<AffineExpr> dimReplacements = llvm::to_vector(
487  llvm::map_range(ArrayRef(operands).take_front(map.getNumDims()), mapper));
488  SmallVector<AffineExpr> symReplacements = llvm::to_vector(
489  llvm::map_range(ArrayRef(operands).drop_front(map.getNumDims()), mapper));
490  cstr.addBound(
492  map.getResult(0).replaceDimsAndSymbols(dimReplacements, symReplacements));
493 
494  // Process the backward slice of `operands` (i.e., reverse use-def chain)
495  // until `stopCondition` is met.
496  if (stopCondition) {
497  cstr.processWorklist(stopCondition);
498  } else {
499  // No stop condition specified: Keep adding constraints until a bound could
500  // be computed.
501  cstr.processWorklist(
502  /*stopCondition=*/[&](Value v, std::optional<int64_t> dim) {
503  return cstr.cstr.getConstantBound64(type, pos).has_value();
504  });
505  }
506 
507  // Compute constant bound for `valueDim`.
508  int64_t ubAdjustment = closedUB ? 0 : 1;
509  if (auto bound = cstr.cstr.getConstantBound64(type, pos))
510  return type == BoundType::UB ? *bound + ubAdjustment : *bound;
511  return failure();
512 }
513 
515  presburger::BoundType type, AffineMap map, ArrayRef<Value> operands,
516  StopConditionFn stopCondition, bool closedUB) {
517  ValueDimList valueDims;
518  for (Value v : operands) {
519  assert(v.getType().isIndex() && "expected index type");
520  valueDims.emplace_back(v, std::nullopt);
521  }
522  return computeConstantBound(type, map, valueDims, stopCondition, closedUB);
523 }
524 
527  std::optional<int64_t> dim1,
528  std::optional<int64_t> dim2) {
529 #ifndef NDEBUG
530  assertValidValueDim(value1, dim1);
531  assertValidValueDim(value2, dim2);
532 #endif // NDEBUG
533 
534  Builder b(value1.getContext());
535  AffineMap map = AffineMap::get(/*dimCount=*/2, /*symbolCount=*/0,
536  b.getAffineDimExpr(0) - b.getAffineDimExpr(1));
538  {{value1, dim1}, {value2, dim2}});
539 }
540 
543  std::optional<int64_t> dim1,
544  std::optional<int64_t> dim2) {
545  // Subtract the two values/dimensions from each other. If the result is 0,
546  // both are equal.
547  FailureOr<int64_t> delta = computeConstantDelta(value1, value2, dim1, dim2);
548  if (failed(delta))
549  return failure();
550  return *delta == 0;
551 }
552 
554  OpFoldResult ofr2) {
555  Builder b(ofr1.getContext());
556  AffineMap map =
557  AffineMap::get(/*dimCount=*/0, /*symbolCount=*/2,
559  SmallVector<OpFoldResult> ofrOperands;
560  ofrOperands.push_back(ofr1);
561  ofrOperands.push_back(ofr2);
562  SmallVector<Value> valueOperands;
563  AffineMap foldedMap =
564  foldAttributesIntoMap(b, map, ofrOperands, valueOperands);
565  ValueDimList valueDims;
566  for (Value v : valueOperands) {
567  assert(v.getType().isIndex() && "expected index type");
568  valueDims.emplace_back(v, std::nullopt);
569  }
570  FailureOr<int64_t> delta =
571  computeConstantBound(presburger::BoundType::EQ, foldedMap, valueDims);
572  if (failed(delta))
573  return failure();
574  return *delta == 0;
575 }
576 
579  HyperrectangularSlice slice1,
580  HyperrectangularSlice slice2) {
581  assert(slice1.getMixedOffsets().size() == slice1.getMixedOffsets().size() &&
582  "expected slices of same rank");
583  assert(slice1.getMixedSizes().size() == slice1.getMixedSizes().size() &&
584  "expected slices of same rank");
585  assert(slice1.getMixedStrides().size() == slice1.getMixedStrides().size() &&
586  "expected slices of same rank");
587 
588  Builder b(ctx);
589  bool foundUnknownBound = false;
590  for (int64_t i = 0, e = slice1.getMixedOffsets().size(); i < e; ++i) {
591  AffineMap map =
592  AffineMap::get(/*dimCount=*/0, /*symbolCount=*/4,
593  b.getAffineSymbolExpr(0) +
595  b.getAffineSymbolExpr(3));
596  {
597  // Case 1: Slices are guaranteed to be non-overlapping if
598  // offset1 + size1 * stride1 <= offset2 (for at least one dimension).
599  SmallVector<OpFoldResult> ofrOperands;
600  ofrOperands.push_back(slice1.getMixedOffsets()[i]);
601  ofrOperands.push_back(slice1.getMixedSizes()[i]);
602  ofrOperands.push_back(slice1.getMixedStrides()[i]);
603  ofrOperands.push_back(slice2.getMixedOffsets()[i]);
604  SmallVector<Value> valueOperands;
605  AffineMap foldedMap =
606  foldAttributesIntoMap(b, map, ofrOperands, valueOperands);
608  presburger::BoundType::EQ, foldedMap, valueOperands);
609  foundUnknownBound |= failed(constBound);
610  if (succeeded(constBound) && *constBound <= 0)
611  return false;
612  }
613  {
614  // Case 2: Slices are guaranteed to be non-overlapping if
615  // offset2 + size2 * stride2 <= offset1 (for at least one dimension).
616  SmallVector<OpFoldResult> ofrOperands;
617  ofrOperands.push_back(slice2.getMixedOffsets()[i]);
618  ofrOperands.push_back(slice2.getMixedSizes()[i]);
619  ofrOperands.push_back(slice2.getMixedStrides()[i]);
620  ofrOperands.push_back(slice1.getMixedOffsets()[i]);
621  SmallVector<Value> valueOperands;
622  AffineMap foldedMap =
623  foldAttributesIntoMap(b, map, ofrOperands, valueOperands);
625  presburger::BoundType::EQ, foldedMap, valueOperands);
626  foundUnknownBound |= failed(constBound);
627  if (succeeded(constBound) && *constBound <= 0)
628  return false;
629  }
630  }
631 
632  // If at least one bound could not be computed, we cannot be certain that the
633  // slices are really overlapping.
634  if (foundUnknownBound)
635  return failure();
636 
637  // All bounds could be computed and none of the above cases applied.
638  // Therefore, the slices are guaranteed to overlap.
639  return true;
640 }
641 
644  HyperrectangularSlice slice1,
645  HyperrectangularSlice slice2) {
646  assert(slice1.getMixedOffsets().size() == slice1.getMixedOffsets().size() &&
647  "expected slices of same rank");
648  assert(slice1.getMixedSizes().size() == slice1.getMixedSizes().size() &&
649  "expected slices of same rank");
650  assert(slice1.getMixedStrides().size() == slice1.getMixedStrides().size() &&
651  "expected slices of same rank");
652 
653  // The two slices are equivalent if all of their offsets, sizes and strides
654  // are equal. If equality cannot be determined for at least one of those
655  // values, equivalence cannot be determined and this function returns
656  // "failure".
657  for (auto [offset1, offset2] :
658  llvm::zip_equal(slice1.getMixedOffsets(), slice2.getMixedOffsets())) {
659  FailureOr<bool> equal = areEqual(offset1, offset2);
660  if (failed(equal))
661  return failure();
662  if (!equal.value())
663  return false;
664  }
665  for (auto [size1, size2] :
666  llvm::zip_equal(slice1.getMixedSizes(), slice2.getMixedSizes())) {
667  FailureOr<bool> equal = areEqual(size1, size2);
668  if (failed(equal))
669  return failure();
670  if (!equal.value())
671  return false;
672  }
673  for (auto [stride1, stride2] :
674  llvm::zip_equal(slice1.getMixedStrides(), slice2.getMixedStrides())) {
675  FailureOr<bool> equal = areEqual(stride1, stride2);
676  if (failed(equal))
677  return failure();
678  if (!equal.value())
679  return false;
680  }
681  return true;
682 }
683 
686  assert(!this->dim.has_value() && "dim was already set");
687  this->dim = dim;
688 #ifndef NDEBUG
689  assertValidValueDim(value, this->dim);
690 #endif // NDEBUG
691  return *this;
692 }
693 
695 #ifndef NDEBUG
696  assertValidValueDim(value, this->dim);
697 #endif // NDEBUG
698  cstr.addBound(BoundType::UB, cstr.getPos(value, this->dim), expr);
699 }
700 
702  operator<(expr + 1);
703 }
704 
706  operator>=(expr + 1);
707 }
708 
710 #ifndef NDEBUG
711  assertValidValueDim(value, this->dim);
712 #endif // NDEBUG
713  cstr.addBound(BoundType::LB, cstr.getPos(value, this->dim), expr);
714 }
715 
717 #ifndef NDEBUG
718  assertValidValueDim(value, this->dim);
719 #endif // NDEBUG
720  cstr.addBound(BoundType::EQ, cstr.getPos(value, this->dim), expr);
721 }
722 
724  operator<(cstr.getExpr(ofr));
725 }
726 
728  operator<=(cstr.getExpr(ofr));
729 }
730 
732  operator>(cstr.getExpr(ofr));
733 }
734 
736  operator>=(cstr.getExpr(ofr));
737 }
738 
740  operator==(cstr.getExpr(ofr));
741 }
742 
744  operator<(cstr.getExpr(i));
745 }
746 
748  operator<=(cstr.getExpr(i));
749 }
750 
752  operator>(cstr.getExpr(i));
753 }
754 
756  operator>=(cstr.getExpr(i));
757 }
758 
760  operator==(cstr.getExpr(i));
761 }
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:66
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:47
MLIRContext * getContext() const
Definition: AffineMap.cpp:321
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumDims() const
Definition: AffineMap.cpp:374
unsigned getNumResults() const
Definition: AffineMap.cpp:382
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:391
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:357
AffineExpr getAffineConstantExpr(int64_t constant)
Definition: Builders.cpp:361
AffineExpr getAffineDimExpr(unsigned position)
Definition: Builders.cpp:353
This class provides support for representing a failure result, or a valid value of type T.
Definition: LogicalResult.h:78
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
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...
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:266
MLIRContext * getContext() const
Definition: OpDefinition.h:272
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
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:373
bool isIndex() const
Definition: Types.cpp:56
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 helper class to be used with ValueBoundsOpInterface.
DenseMap< ValueDim, int64_t > valueDimToPosition
Reverse mapping of values/shape dimensions to columns.
static FailureOr< bool > areEqual(Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
Compute whether the given values/dimensions are equal.
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 computeBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, StopConditionFn stopCondition, bool closedUB=false)
Compute a bound for the given index-typed value or shape dimension size.
int64_t insert(Value value, std::optional< int64_t > dim, bool isSymbol=true)
Insert a value/dimension into the constraint set.
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.
void addBound(presburger::BoundType type, int64_t pos, AffineExpr expr)
Bound the given column in the underlying constraint set by the given expression.
BoundBuilder bound(Value value)
Add a bound for the given index-typed value or shaped value.
int64_t getPos(Value value, std::optional< int64_t > dim=std::nullopt) const
Return the column position of the given value/dimension.
std::queue< int64_t > worklist
Worklist of values/shape dimensions that have not been processed yet.
FlatLinearConstraints cstr
Constraint system of equalities and inequalities.
void processWorklist(StopConditionFn stopCondition)
Iteratively process all elements on the worklist until an index-typed value or shaped value meets sto...
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.
static LogicalResult computeDependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, ValueDimList dependencies, bool closedUB=false)
Compute a bound in terms of the values/dimensions in dependencies.
static FailureOr< bool > areOverlappingSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be overlapping.
Builder builder
Builder for constructing affine expressions.
static LogicalResult computeIndependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, ValueRange independencies, bool closedUB=false)
Compute a bound in that is independent of all values in independencies.
static FailureOr< int64_t > computeConstantBound(presburger::BoundType type, Value value, std::optional< int64_t > dim=std::nullopt, StopConditionFn stopCondition=nullptr, bool closedUB=false)
Compute a constant bound for the given affine map, where dims and symbols are bound to the given oper...
static constexpr int64_t kIndexValue
Dimension identifier to indicate a value is index-typed.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:378
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:128
Type getType() const
Return the type of this value.
Definition: Value.h:125
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.
void projectOut(unsigned pos, unsigned num)
Projects out (aka eliminates) num variables starting at position pos.
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:96
bool operator<(const Fraction &x, const Fraction &y)
Definition: Fraction.h:80
bool operator>=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:100
bool operator<=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:84
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
Definition: Matchers.h:401
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
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:438
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...
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
Definition: LogicalResult.h:68
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
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:702
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26