1//===- ReifyValueBounds.cpp --- Reify value bounds with arith ops -------*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include <utility>
10
11#include "mlir/Dialect/Arith/Transforms/Transforms.h"
12
13#include "mlir/Dialect/Arith/IR/Arith.h"
14#include "mlir/Dialect/MemRef/IR/MemRef.h"
15#include "mlir/Dialect/Tensor/IR/Tensor.h"
16#include "mlir/Interfaces/ValueBoundsOpInterface.h"
17
18using namespace mlir;
19using namespace mlir::arith;
20
21[[maybe_unused]] static bool isIndexLikeType(Type type,
22 ValueBoundsOptions options) {
23 return type.isIndex() || (options.allowIntegerType && type.isInteger());
24}
25
26static Value castToIndexValue(OpBuilder &b, Location loc, Value value) {
27 if (value.getType().isIndex())
28 return value;
29 assert(value.getType().isSignlessInteger() &&
30 "expected index or signless integer type");
31 return IndexCastOp::create(builder&: b, location: loc, out: b.getIndexType(), in: value);
32}
33
34/// Build Arith IR for the given affine map and its operands.
35static Value buildArithValue(OpBuilder &b, Location loc, AffineMap map,
36 ValueRange operands) {
37 assert(map.getNumResults() == 1 && "multiple results not supported yet");
38 std::function<Value(AffineExpr)> buildExpr = [&](AffineExpr e) -> Value {
39 switch (e.getKind()) {
40 case AffineExprKind::Constant:
41 return ConstantIndexOp::create(builder&: b, location: loc,
42 value: cast<AffineConstantExpr>(Val&: e).getValue());
43 case AffineExprKind::DimId:
44 return castToIndexValue(b, loc,
45 value: operands[cast<AffineDimExpr>(Val&: e).getPosition()]);
46 case AffineExprKind::SymbolId:
47 return castToIndexValue(
48 b, loc,
49 value: operands[cast<AffineSymbolExpr>(Val&: e).getPosition() + map.getNumDims()]);
50 case AffineExprKind::Add: {
51 auto binaryExpr = cast<AffineBinaryOpExpr>(Val&: e);
52 return AddIOp::create(builder&: b, location: loc, lhs: buildExpr(binaryExpr.getLHS()),
53 rhs: buildExpr(binaryExpr.getRHS()));
54 }
55 case AffineExprKind::Mul: {
56 auto binaryExpr = cast<AffineBinaryOpExpr>(Val&: e);
57 return MulIOp::create(builder&: b, location: loc, lhs: buildExpr(binaryExpr.getLHS()),
58 rhs: buildExpr(binaryExpr.getRHS()));
59 }
60 case AffineExprKind::FloorDiv: {
61 auto binaryExpr = cast<AffineBinaryOpExpr>(Val&: e);
62 return DivSIOp::create(builder&: b, location: loc, lhs: buildExpr(binaryExpr.getLHS()),
63 rhs: buildExpr(binaryExpr.getRHS()));
64 }
65 case AffineExprKind::CeilDiv: {
66 auto binaryExpr = cast<AffineBinaryOpExpr>(Val&: e);
67 return CeilDivSIOp::create(builder&: b, location: loc, lhs: buildExpr(binaryExpr.getLHS()),
68 rhs: buildExpr(binaryExpr.getRHS()));
69 }
70 case AffineExprKind::Mod: {
71 auto binaryExpr = cast<AffineBinaryOpExpr>(Val&: e);
72 return RemSIOp::create(builder&: b, location: loc, lhs: buildExpr(binaryExpr.getLHS()),
73 rhs: buildExpr(binaryExpr.getRHS()));
74 }
75 }
76 llvm_unreachable("unsupported AffineExpr kind");
77 };
78 return buildExpr(map.getResult(idx: 0));
79}
80
81FailureOr<OpFoldResult> mlir::arith::reifyValueBound(
82 OpBuilder &b, Location loc, presburger::BoundType type,
83 const ValueBoundsConstraintSet::Variable &var,
84 ValueBoundsConstraintSet::StopConditionFn stopCondition,
85 ValueBoundsOptions options) {
86 // Compute bound.
87 AffineMap boundMap;
88 ValueDimList mapOperands;
89 if (failed(Result: ValueBoundsConstraintSet::computeBound(
90 resultMap&: boundMap, mapOperands, type, var, stopCondition: std::move(stopCondition), options)))
91 return failure();
92
93 // Materialize tensor.dim/memref.dim ops.
94 SmallVector<Value> operands;
95 for (auto valueDim : mapOperands) {
96 Value value = valueDim.first;
97 std::optional<int64_t> dim = valueDim.second;
98
99 if (!dim.has_value()) {
100 // This is an index-typed/integer-typed value.
101 assert(isIndexLikeType(value.getType(), options) &&
102 "expected index or integer type");
103 operands.push_back(Elt: value);
104 continue;
105 }
106
107 assert(cast<ShapedType>(value.getType()).isDynamicDim(*dim) &&
108 "expected dynamic dim");
109 if (isa<RankedTensorType>(Val: value.getType())) {
110 // A tensor dimension is used: generate a tensor.dim.
111 operands.push_back(Elt: tensor::DimOp::create(builder&: b, location: loc, source: value, index: *dim));
112 } else if (isa<MemRefType>(Val: value.getType())) {
113 // A memref dimension is used: generate a memref.dim.
114 operands.push_back(Elt: memref::DimOp::create(builder&: b, location: loc, source: value, index: *dim));
115 } else {
116 llvm_unreachable("cannot generate DimOp for unsupported shaped type");
117 }
118 }
119
120 // Check for special cases where no arith ops are needed.
121 if (boundMap.isSingleConstant()) {
122 // Bound is a constant: return an IntegerAttr.
123 return static_cast<OpFoldResult>(
124 b.getIndexAttr(value: boundMap.getSingleConstantResult()));
125 }
126 // No arith ops are needed if the bound is a single SSA value.
127 if (auto expr = dyn_cast<AffineDimExpr>(Val: boundMap.getResult(idx: 0)))
128 return static_cast<OpFoldResult>(
129 castToIndexValue(b, loc, value: operands[expr.getPosition()]));
130 if (auto expr = dyn_cast<AffineSymbolExpr>(Val: boundMap.getResult(idx: 0)))
131 return static_cast<OpFoldResult>(castToIndexValue(
132 b, loc, value: operands[expr.getPosition() + boundMap.getNumDims()]));
133 // General case: build Arith ops.
134 return static_cast<OpFoldResult>(buildArithValue(b, loc, map: boundMap, operands));
135}
136
137FailureOr<OpFoldResult> mlir::arith::reifyShapedValueDimBound(
138 OpBuilder &b, Location loc, presburger::BoundType type, Value value,
139 int64_t dim, const ValueBoundsConstraintSet::StopConditionFn &stopCondition,
140 ValueBoundsOptions options) {
141 auto reifyToOperands = [&](Value v, std::optional<int64_t> d,
142 ValueBoundsConstraintSet &cstr) {
143 // We are trying to reify a bound for `value` in terms of the owning op's
144 // operands. Construct a stop condition that evaluates to "true" for any SSA
145 // value expect for `value`. I.e., the bound will be computed in terms of
146 // any SSA values expect for `value`. The first such values are operands of
147 // the owner of `value`.
148 return v != value;
149 };
150 return reifyValueBound(b, loc, type, var: {value, dim},
151 stopCondition: stopCondition ? stopCondition : reifyToOperands,
152 options);
153}
154
155FailureOr<OpFoldResult> mlir::arith::reifyIndexValueBound(
156 OpBuilder &b, Location loc, presburger::BoundType type, Value value,
157 const ValueBoundsConstraintSet::StopConditionFn &stopCondition,
158 ValueBoundsOptions options) {
159 auto reifyToOperands = [&](Value v, std::optional<int64_t> d,
160 ValueBoundsConstraintSet &cstr) {
161 return v != value;
162 };
163 return reifyValueBound(b, loc, type, var: value,
164 stopCondition: stopCondition ? stopCondition : reifyToOperands,
165 options);
166}
167