1//===- StaticValueUtils.cpp - Utilities for dealing with static values ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "mlir/Dialect/Utils/StaticValueUtils.h"
10#include "mlir/IR/Attributes.h"
11#include "mlir/IR/Matchers.h"
12#include "mlir/Support/LLVM.h"
13#include "llvm/ADT/APSInt.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SmallVectorExtras.h"
16#include "llvm/Support/DebugLog.h"
17#include "llvm/Support/MathExtras.h"
18
19namespace mlir {
20
21bool isZeroInteger(OpFoldResult v) { return isConstantIntValue(ofr: v, value: 0); }
22
23bool isZeroFloat(OpFoldResult v) {
24 if (auto attr = dyn_cast<Attribute>(Val&: v)) {
25 if (auto floatAttr = dyn_cast<FloatAttr>(Val&: attr))
26 return floatAttr.getValue().isZero();
27 return false;
28 }
29 return matchPattern(value: cast<Value>(Val&: v), pattern: m_AnyZeroFloat());
30}
31
32bool isZeroIntegerOrFloat(OpFoldResult v) {
33 return isZeroInteger(v) || isZeroFloat(v);
34}
35
36bool isOneInteger(OpFoldResult v) { return isConstantIntValue(ofr: v, value: 1); }
37
38std::tuple<SmallVector<OpFoldResult>, SmallVector<OpFoldResult>,
39 SmallVector<OpFoldResult>>
40getOffsetsSizesAndStrides(ArrayRef<Range> ranges) {
41 SmallVector<OpFoldResult> offsets, sizes, strides;
42 offsets.reserve(N: ranges.size());
43 sizes.reserve(N: ranges.size());
44 strides.reserve(N: ranges.size());
45 for (const auto &[offset, size, stride] : ranges) {
46 offsets.push_back(Elt: offset);
47 sizes.push_back(Elt: size);
48 strides.push_back(Elt: stride);
49 }
50 return std::make_tuple(args&: offsets, args&: sizes, args&: strides);
51}
52
53/// Helper function to dispatch an OpFoldResult into `staticVec` if:
54/// a) it is an IntegerAttr
55/// In other cases, the OpFoldResult is dispached to the `dynamicVec`.
56/// In such dynamic cases, a copy of the `sentinel` value is also pushed to
57/// `staticVec`. This is useful to extract mixed static and dynamic entries that
58/// come from an AttrSizedOperandSegments trait.
59void dispatchIndexOpFoldResult(OpFoldResult ofr,
60 SmallVectorImpl<Value> &dynamicVec,
61 SmallVectorImpl<int64_t> &staticVec) {
62 auto v = llvm::dyn_cast_if_present<Value>(Val&: ofr);
63 if (!v) {
64 APInt apInt = cast<IntegerAttr>(Val: cast<Attribute>(Val&: ofr)).getValue();
65 staticVec.push_back(Elt: apInt.getSExtValue());
66 return;
67 }
68 dynamicVec.push_back(Elt: v);
69 staticVec.push_back(Elt: ShapedType::kDynamic);
70}
71
72std::pair<int64_t, OpFoldResult>
73getSimplifiedOfrAndStaticSizePair(OpFoldResult tileSizeOfr, Builder &b) {
74 int64_t tileSizeForShape =
75 getConstantIntValue(ofr: tileSizeOfr).value_or(u: ShapedType::kDynamic);
76
77 OpFoldResult tileSizeOfrSimplified =
78 (tileSizeForShape != ShapedType::kDynamic)
79 ? b.getIndexAttr(value: tileSizeForShape)
80 : tileSizeOfr;
81
82 return std::pair<int64_t, OpFoldResult>(tileSizeForShape,
83 tileSizeOfrSimplified);
84}
85
86void dispatchIndexOpFoldResults(ArrayRef<OpFoldResult> ofrs,
87 SmallVectorImpl<Value> &dynamicVec,
88 SmallVectorImpl<int64_t> &staticVec) {
89 for (OpFoldResult ofr : ofrs)
90 dispatchIndexOpFoldResult(ofr, dynamicVec, staticVec);
91}
92
93/// Given a value, try to extract a constant Attribute. If this fails, return
94/// the original value.
95OpFoldResult getAsOpFoldResult(Value val) {
96 if (!val)
97 return OpFoldResult();
98 Attribute attr;
99 if (matchPattern(value: val, pattern: m_Constant(bind_value: &attr)))
100 return attr;
101 return val;
102}
103
104/// Given an array of values, try to extract a constant Attribute from each
105/// value. If this fails, return the original value.
106SmallVector<OpFoldResult> getAsOpFoldResult(ValueRange values) {
107 return llvm::map_to_vector(C&: values,
108 F: [](Value v) { return getAsOpFoldResult(val: v); });
109}
110
111/// Convert `arrayAttr` to a vector of OpFoldResult.
112SmallVector<OpFoldResult> getAsOpFoldResult(ArrayAttr arrayAttr) {
113 SmallVector<OpFoldResult> res;
114 res.reserve(N: arrayAttr.size());
115 for (Attribute a : arrayAttr)
116 res.push_back(Elt: a);
117 return res;
118}
119
120OpFoldResult getAsIndexOpFoldResult(MLIRContext *ctx, int64_t val) {
121 return IntegerAttr::get(type: IndexType::get(context: ctx), value: val);
122}
123
124SmallVector<OpFoldResult> getAsIndexOpFoldResult(MLIRContext *ctx,
125 ArrayRef<int64_t> values) {
126 return llvm::map_to_vector(
127 C&: values, F: [ctx](int64_t v) { return getAsIndexOpFoldResult(ctx, val: v); });
128}
129
130/// If ofr is a constant integer or an IntegerAttr, return the integer.
131/// The boolean indicates whether the value is an index type.
132std::optional<std::pair<APInt, bool>> getConstantAPIntValue(OpFoldResult ofr) {
133 // Case 1: Check for Constant integer.
134 if (auto val = llvm::dyn_cast_if_present<Value>(Val&: ofr)) {
135 APInt intVal;
136 if (matchPattern(value: val, pattern: m_ConstantInt(bind_value: &intVal)))
137 return std::make_pair(x&: intVal, y: val.getType().isIndex());
138 return std::nullopt;
139 }
140 // Case 2: Check for IntegerAttr.
141 Attribute attr = llvm::dyn_cast_if_present<Attribute>(Val&: ofr);
142 if (auto intAttr = dyn_cast_or_null<IntegerAttr>(Val&: attr))
143 return std::make_pair(x: intAttr.getValue(), y: intAttr.getType().isIndex());
144 return std::nullopt;
145}
146
147/// If ofr is a constant integer or an IntegerAttr, return the integer.
148std::optional<int64_t> getConstantIntValue(OpFoldResult ofr) {
149 std::optional<std::pair<APInt, bool>> apInt = getConstantAPIntValue(ofr);
150 if (!apInt)
151 return std::nullopt;
152 return apInt->first.getSExtValue();
153}
154
155/// If ofr is a constant integer or an IntegerAttr, return the integer
156/// zero-extended to 64 bits.
157std::optional<uint64_t> getConstantUIntValue(OpFoldResult ofr) {
158 std::optional<std::pair<APInt, bool>> apInt = getConstantAPIntValue(ofr);
159 if (!apInt)
160 return std::nullopt;
161 return apInt->first.getZExtValue();
162}
163
164std::optional<SmallVector<int64_t>>
165getConstantIntValues(ArrayRef<OpFoldResult> ofrs) {
166 SmallVector<int64_t> res;
167 res.reserve(N: ofrs.size());
168 for (OpFoldResult ofr : ofrs) {
169 auto cv = getConstantIntValue(ofr);
170 if (!cv.has_value())
171 return std::nullopt;
172 res.push_back(Elt: cv.value());
173 }
174 return res;
175}
176
177bool isConstantIntValue(OpFoldResult ofr, int64_t value) {
178 return getConstantIntValue(ofr) == value;
179}
180
181bool areAllConstantIntValue(ArrayRef<OpFoldResult> ofrs, int64_t value) {
182 return llvm::all_of(
183 Range&: ofrs, P: [&](OpFoldResult ofr) { return isConstantIntValue(ofr, value); });
184}
185
186bool areConstantIntValues(ArrayRef<OpFoldResult> ofrs,
187 ArrayRef<int64_t> values) {
188 if (ofrs.size() != values.size())
189 return false;
190 std::optional<SmallVector<int64_t>> constOfrs = getConstantIntValues(ofrs);
191 return constOfrs && llvm::equal(LRange&: constOfrs.value(), RRange&: values);
192}
193
194/// Return true if ofr1 and ofr2 are the same integer constant attribute values
195/// or the same SSA value.
196/// Ignore integer bitwidth and type mismatch that come from the fact there is
197/// no IndexAttr and that IndexType has no bitwidth.
198bool isEqualConstantIntOrValue(OpFoldResult ofr1, OpFoldResult ofr2) {
199 auto cst1 = getConstantIntValue(ofr: ofr1), cst2 = getConstantIntValue(ofr: ofr2);
200 if (cst1 && cst2 && *cst1 == *cst2)
201 return true;
202 auto v1 = llvm::dyn_cast_if_present<Value>(Val&: ofr1),
203 v2 = llvm::dyn_cast_if_present<Value>(Val&: ofr2);
204 return v1 && v1 == v2;
205}
206
207bool isEqualConstantIntOrValueArray(ArrayRef<OpFoldResult> ofrs1,
208 ArrayRef<OpFoldResult> ofrs2) {
209 if (ofrs1.size() != ofrs2.size())
210 return false;
211 for (auto [ofr1, ofr2] : llvm::zip_equal(t&: ofrs1, u&: ofrs2))
212 if (!isEqualConstantIntOrValue(ofr1, ofr2))
213 return false;
214 return true;
215}
216
217/// Return a vector of OpFoldResults with the same size as staticValues, but all
218/// elements for which ShapedType::isDynamic is true, will be replaced by
219/// dynamicValues.
220SmallVector<OpFoldResult> getMixedValues(ArrayRef<int64_t> staticValues,
221 ValueRange dynamicValues,
222 MLIRContext *context) {
223 assert(dynamicValues.size() == static_cast<size_t>(llvm::count_if(
224 staticValues, ShapedType::isDynamic)) &&
225 "expected the rank of dynamic values to match the number of "
226 "values known to be dynamic");
227 SmallVector<OpFoldResult> res;
228 res.reserve(N: staticValues.size());
229 unsigned numDynamic = 0;
230 unsigned count = static_cast<unsigned>(staticValues.size());
231 for (unsigned idx = 0; idx < count; ++idx) {
232 int64_t value = staticValues[idx];
233 res.push_back(Elt: ShapedType::isDynamic(dValue: value)
234 ? OpFoldResult{dynamicValues[numDynamic++]}
235 : OpFoldResult{IntegerAttr::get(
236 type: IntegerType::get(context, width: 64), value: staticValues[idx])});
237 }
238 return res;
239}
240SmallVector<OpFoldResult> getMixedValues(ArrayRef<int64_t> staticValues,
241 ValueRange dynamicValues, Builder &b) {
242 return getMixedValues(staticValues, dynamicValues, context: b.getContext());
243}
244
245/// Decompose a vector of mixed static or dynamic values into the corresponding
246/// pair of arrays. This is the inverse function of `getMixedValues`.
247std::pair<SmallVector<int64_t>, SmallVector<Value>>
248decomposeMixedValues(ArrayRef<OpFoldResult> mixedValues) {
249 SmallVector<int64_t> staticValues;
250 SmallVector<Value> dynamicValues;
251 for (const auto &it : mixedValues) {
252 if (auto attr = dyn_cast<Attribute>(Val: it)) {
253 staticValues.push_back(Elt: cast<IntegerAttr>(Val&: attr).getInt());
254 } else {
255 staticValues.push_back(Elt: ShapedType::kDynamic);
256 dynamicValues.push_back(Elt: cast<Value>(Val: it));
257 }
258 }
259 return {staticValues, dynamicValues};
260}
261
262/// Helper to sort `values` according to matching `keys`.
263template <typename K, typename V>
264static SmallVector<V>
265getValuesSortedByKeyImpl(ArrayRef<K> keys, ArrayRef<V> values,
266 llvm::function_ref<bool(K, K)> compare) {
267 if (keys.empty())
268 return SmallVector<V>{values};
269 assert(keys.size() == values.size() && "unexpected mismatching sizes");
270 auto indices = llvm::to_vector(llvm::seq<int64_t>(0, values.size()));
271 llvm::sort(indices,
272 [&](int64_t i, int64_t j) { return compare(keys[i], keys[j]); });
273 SmallVector<V> res;
274 res.reserve(values.size());
275 for (int64_t i = 0, e = indices.size(); i < e; ++i)
276 res.push_back(values[indices[i]]);
277 return res;
278}
279
280SmallVector<Value>
281getValuesSortedByKey(ArrayRef<Attribute> keys, ArrayRef<Value> values,
282 llvm::function_ref<bool(Attribute, Attribute)> compare) {
283 return getValuesSortedByKeyImpl(keys, values, compare);
284}
285
286SmallVector<OpFoldResult>
287getValuesSortedByKey(ArrayRef<Attribute> keys, ArrayRef<OpFoldResult> values,
288 llvm::function_ref<bool(Attribute, Attribute)> compare) {
289 return getValuesSortedByKeyImpl(keys, values, compare);
290}
291
292SmallVector<int64_t>
293getValuesSortedByKey(ArrayRef<Attribute> keys, ArrayRef<int64_t> values,
294 llvm::function_ref<bool(Attribute, Attribute)> compare) {
295 return getValuesSortedByKeyImpl(keys, values, compare);
296}
297
298/// Return the number of iterations for a loop with a lower bound `lb`, upper
299/// bound `ub` and step `step`.
300std::optional<APInt> constantTripCount(
301 OpFoldResult lb, OpFoldResult ub, OpFoldResult step, bool isSigned,
302 llvm::function_ref<std::optional<llvm::APSInt>(Value, Value, bool)>
303 computeUbMinusLb) {
304 // This is the bitwidth used to return 0 when loop does not execute.
305 // We infer it from the type of the bound if it isn't an index type.
306 auto getBitwidth = [&](OpFoldResult ofr) -> std::tuple<int, bool> {
307 if (auto intAttr =
308 dyn_cast_or_null<IntegerAttr>(Val: dyn_cast<Attribute>(Val&: ofr))) {
309 if (auto intType = dyn_cast<IntegerType>(Val: intAttr.getType()))
310 return std::make_tuple(args: intType.getWidth(), args: intType.isIndex());
311 } else {
312 auto val = cast<Value>(Val&: ofr);
313 if (auto intType = dyn_cast<IntegerType>(Val: val.getType()))
314 return std::make_tuple(args: intType.getWidth(), args: intType.isIndex());
315 }
316 return std::make_tuple(args: IndexType::kInternalStorageBitWidth, args: true);
317 };
318 auto [bitwidth, isIndex] = getBitwidth(lb);
319 // This would better be an assert, but unfortunately it breaks scf.for_all
320 // which is missing attributes and SSA value optionally for its bounds, and
321 // uses Index type for the dynamic bounds but i64 for the static bounds. This
322 // is broken...
323 if (std::tie(args&: bitwidth, args&: isIndex) != getBitwidth(ub)) {
324 LDBG() << "mismatch between lb and ub bitwidth/type: " << ub << " vs "
325 << lb;
326 return std::nullopt;
327 }
328 if (lb == ub) {
329 // Fast path: LB == UB. The loop has zero iterations.
330 // Note: LB and UB could match at runtime, even though they are different
331 // SSA values. That case cannot be detected here.
332 return APInt(bitwidth, 0);
333 }
334 if (isZeroInteger(v: lb) && ub == step) {
335 // Fast path: LB == 0 && UB == step. The loop has a single iteration.
336 // Note: LB and UB could match at runtime, even though they are different
337 // SSA values. That case cannot be detected here.
338 return APInt(bitwidth, 1);
339 }
340
341 std::optional<std::pair<APInt, bool>> maybeStepCst =
342 getConstantAPIntValue(ofr: step);
343
344 if (maybeStepCst) {
345 auto &stepCst = maybeStepCst->first;
346 assert(static_cast<int>(stepCst.getBitWidth()) == bitwidth &&
347 "step must have the same bitwidth as lb and ub");
348 if (stepCst.isZero()) {
349 // Step is zero. If LB and UB match, we have zero iterations. Otherwise,
350 // we have an infinite number of iterations. We cannot tell for sure which
351 // case applies, so the static trip count is unknown.
352 return std::nullopt;
353 }
354 }
355
356 if (isIndex) {
357 LDBG()
358 << "Computing loop trip count for index type may break with overflow";
359 // TODO: we can't compute the trip count for index type. We should fix this
360 // but too many tests are failing right now.
361 // return {};
362 }
363
364 /// Compute the difference between the upper and lower bound: either from the
365 /// constant value or using the computeUbMinusLb callback.
366 llvm::APSInt diff;
367 std::optional<std::pair<APInt, bool>> maybeLbCst = getConstantAPIntValue(ofr: lb);
368 std::optional<std::pair<APInt, bool>> maybeUbCst = getConstantAPIntValue(ofr: ub);
369 if (maybeLbCst) {
370 // If one of the bounds is not a constant, we can't compute the trip count.
371 if (!maybeUbCst)
372 return std::nullopt;
373 APSInt lbCst(maybeLbCst->first, /*isUnsigned=*/!isSigned);
374 APSInt ubCst(maybeUbCst->first, /*isUnsigned=*/!isSigned);
375 if (ubCst <= lbCst) {
376 LDBG() << "constantTripCount is 0 because ub <= lb (" << lbCst << "("
377 << lbCst.getBitWidth() << ") <= " << ubCst << "("
378 << ubCst.getBitWidth() << "), "
379 << (isSigned ? "isSigned" : "isUnsigned") << ")";
380 return APInt(bitwidth, 0);
381 }
382 // Compute the difference. Since we've already checked that ub > lb, the
383 // result can be interpreted as an unsigned value without overflow concerns.
384 diff = ubCst - lbCst;
385 // Convert diff to unsigned. This handles cases like i8: ub=127, lb=-128
386 // where the subtraction yields 255, which wraps to -1 in signed i8 but is
387 // correctly represented as 255 when interpreted as unsigned.
388 diff.setIsUnsigned(true);
389 } else {
390 if (maybeUbCst)
391 return std::nullopt;
392
393 /// Non-constant bound, let's try to compute the difference between the
394 /// upper and lower bound
395 std::optional<llvm::APSInt> maybeDiff =
396 computeUbMinusLb(cast<Value>(Val&: lb), cast<Value>(Val&: ub), isSigned);
397 if (!maybeDiff)
398 return std::nullopt;
399 diff = *maybeDiff;
400 }
401 LDBG() << "constantTripCount: " << (isSigned ? "isSigned" : "isUnsigned")
402 << ", ub-lb: " << diff << "(" << diff.getBitWidth() << "b)";
403 if (isSigned && diff.isNegative()) {
404 LDBG() << "constantTripCount is 0 because ub-lb diff is negative";
405 return APInt(bitwidth, 0);
406 }
407 if (!maybeStepCst) {
408 LDBG()
409 << "constantTripCount can't be computed because step is not a constant";
410 return std::nullopt;
411 }
412 auto &stepCst = maybeStepCst->first;
413 // For signed loops, a negative step size could indicate an infinite number of
414 // iterations.
415 if (isSigned && stepCst.isSignBitSet()) {
416 LDBG() << "constantTripCount is infinite because step is negative";
417 return std::nullopt;
418 }
419
420 // Both diff and step are non-negative at this point (negative steps are
421 // rejected earlier), so we use unsigned division regardless of the loop
422 // comparison signedness.
423 llvm::APInt tripCount = diff.udiv(RHS: stepCst);
424 llvm::APInt remainder = diff.urem(RHS: stepCst);
425 if (!remainder.isZero())
426 tripCount = tripCount + 1;
427
428 LDBG() << "constantTripCount found: " << tripCount;
429 return tripCount;
430}
431
432bool hasValidSizesOffsets(SmallVector<int64_t> sizesOrOffsets) {
433 return llvm::none_of(Range&: sizesOrOffsets, P: [](int64_t value) {
434 return ShapedType::isStatic(dValue: value) && value < 0;
435 });
436}
437
438bool hasValidStrides(SmallVector<int64_t> strides) {
439 return llvm::none_of(Range&: strides, P: [](int64_t value) {
440 return ShapedType::isStatic(dValue: value) && value == 0;
441 });
442}
443
444LogicalResult foldDynamicIndexList(SmallVectorImpl<OpFoldResult> &ofrs,
445 bool onlyNonNegative, bool onlyNonZero) {
446 bool valuesChanged = false;
447 for (OpFoldResult &ofr : ofrs) {
448 if (isa<Attribute>(Val: ofr))
449 continue;
450 // Note: All ofrs have index type; the kDynamic sentinel stays dynamic.
451 std::optional<int64_t> intVal = getConstantIntValue(ofr);
452 if (!intVal || *intVal == ShapedType::kDynamic)
453 continue;
454 if (onlyNonNegative && *intVal < 0)
455 continue;
456 if (onlyNonZero && *intVal == 0)
457 continue;
458 ofr = getAsIndexOpFoldResult(ctx: cast<Value>(Val&: ofr).getContext(), val: *intVal);
459 valuesChanged = true;
460 }
461 return success(IsSuccess: valuesChanged);
462}
463
464LogicalResult
465foldDynamicOffsetSizeList(SmallVectorImpl<OpFoldResult> &offsetsOrSizes) {
466 return foldDynamicIndexList(ofrs&: offsetsOrSizes, /*onlyNonNegative=*/true,
467 /*onlyNonZero=*/false);
468}
469
470LogicalResult foldDynamicStrideList(SmallVectorImpl<OpFoldResult> &strides) {
471 return foldDynamicIndexList(ofrs&: strides, /*onlyNonNegative=*/false,
472 /*onlyNonZero=*/true);
473}
474
475MemRefType updateTypeFromMetadata(MemRefType type, OpFoldResult offset,
476 ArrayRef<OpFoldResult> sizes,
477 ArrayRef<OpFoldResult> strides) {
478 SmallVector<OpFoldResult> offsets{offset};
479 SmallVector<int64_t> staticOffsets = decomposeMixedValues(mixedValues: offsets).first;
480 SmallVector<int64_t> staticSizes = decomposeMixedValues(mixedValues: sizes).first;
481 SmallVector<int64_t> staticStrides = decomposeMixedValues(mixedValues: strides).first;
482 auto layout = StridedLayoutAttr::get(context: type.getContext(), offset: staticOffsets.front(),
483 strides: staticStrides);
484 // Build a MemRefType using the original element type and memory space,
485 // but derive its shape, offset, and strides from the supplied metadata.
486 MemRefType updatedType = MemRefType::get(shape: staticSizes, elementType: type.getElementType(),
487 layout, memorySpace: type.getMemorySpace());
488 if (!type.getLayout().isIdentity())
489 return updatedType;
490 MemRefType canonicalType = updatedType.canonicalizeStridedLayout();
491 return canonicalType.getLayout().isIdentity() ? canonicalType : updatedType;
492}
493
494} // namespace mlir
495