1//===- TosaFolders.cpp ----------------------------------------------------===//
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// Fold TOSA operations
10//
11//===----------------------------------------------------------------------===//
12
13#include <functional>
14#include <numeric>
15
16#include "mlir/Dialect/Tosa/IR/TosaOps.h"
17#include "mlir/Dialect/Tosa/Transforms/Passes.h"
18#include "mlir/Dialect/Tosa/Utils/ConversionUtils.h"
19#include "mlir/Dialect/Utils/IndexingUtils.h"
20#include "mlir/IR/BuiltinAttributes.h"
21#include "mlir/IR/BuiltinTypes.h"
22#include "mlir/IR/Matchers.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25
26using namespace mlir;
27using namespace mlir::tosa;
28
29namespace {
30
31/// Apply the given transformation \p toApply to every element of the tensor to
32/// be transformed \p toTransform.
33///
34/// Elements of \p toTransform are extracted as \p SrcValueType.
35///
36/// \returns A tensor with the same size as \p toTransform, containing
37/// \p TargetValueType values of type \p TargetType.
38template <class SrcValType, class TargetValType, class TargetType>
39DenseElementsAttr applyElementWise(
40 const DenseElementsAttr &toTransform,
41 const std::function<TargetValType(const SrcValType &)> &toApply,
42 TargetType targetType) {
43 SmallVector<TargetValType> transformedValues;
44 // We already know the amount of values we will insert, reserve space for
45 // all of them to avoid dynamic resizing
46 transformedValues.reserve(toTransform.getNumElements());
47 for (auto val : toTransform.getValues<SrcValType>()) {
48 auto transformedVal = toApply(val);
49 transformedValues.push_back(transformedVal);
50 }
51
52 // Make sure that the output tensor has the expected output type
53 auto inShape = toTransform.getType();
54 auto outTy = inShape.cloneWith(shape: {}, elementType: targetType);
55
56 return DenseElementsAttr::get(outTy, transformedValues);
57}
58
59template DenseElementsAttr applyElementWise<APFloat, APFloat, FloatType>(
60 const DenseElementsAttr &toTransform,
61 const std::function<APFloat(const APFloat &)> &toApply,
62 FloatType targetType);
63
64/// Function that checks if the type contained in \p toCheck is float.
65LogicalResult notifyIfNotFloat(TypedValue<TensorType> toCheck, TosaOp location,
66 PatternRewriter &rewriter) {
67 if (isa<FloatType>(Val: toCheck.getType().getElementType())) {
68 return success();
69 }
70 return rewriter.notifyMatchFailure(arg&: location,
71 msg: "Unexpected input tensor type: the "
72 "TOSA spec only allows floats");
73}
74
75/// Function that checks if \p toCheck is a dense TOSA constant tensor.
76LogicalResult notifyIfNoTosaDenseConstantTensor(TypedValue<TensorType> toCheck,
77 TosaOp location,
78 PatternRewriter &rewriter) {
79 // Check whether the tensor is constant and dense
80 // TODO We currently ensure the tensor is dense by using the correct type for
81 // the bind_value, however we do not actually need this value. It would be
82 // nicer to only have a check here.
83 DenseElementsAttr tmp;
84 if (!matchPattern(value: toCheck, pattern: m_Constant(bind_value: &tmp))) {
85 return rewriter.notifyMatchFailure(arg&: location,
86 msg: "Non-const or non-dense input tensor");
87 }
88
89 // Make sure it actually is a TOSA constant (the match allows for other
90 // constants as well)
91 if (isa<ConstOp>(Val: toCheck.getDefiningOp())) {
92 return success();
93 }
94
95 return rewriter.notifyMatchFailure(arg&: location,
96 msg: "The reciprocal can only be folded if "
97 "it operates on a TOSA constant");
98}
99
100/// Function that checks if \p toCheck is a dense TOSA constant float tensor.
101LogicalResult notifyIfNotConstantFloatTosaTensor(TypedValue<TensorType> toCheck,
102 TosaOp location,
103 PatternRewriter &rewriter) {
104 auto floatCheck = notifyIfNotFloat(toCheck, location, rewriter);
105 if (failed(Result: floatCheck)) {
106 return floatCheck;
107 }
108 return notifyIfNoTosaDenseConstantTensor(toCheck, location, rewriter);
109}
110
111/// Heuristic to decide when to replace a unary operation on a constant with the
112/// folded value.
113/// Folding operations on constants can lead to an increased memory usage
114/// whenever the input cannot be replaced but a new constant is inserted. Hence,
115/// this will currently only suggest folding when the memory impact is
116/// negligible.
117/// Takes the \p unaryOp and the constant input \p values.
118/// \returns Whether folding should be applied.
119bool constantUnaryOpShouldBeFolded(TosaOp unaryOp, DenseElementsAttr values) {
120 assert(unaryOp->getNumOperands() == 1);
121 auto inputOp = unaryOp->getOperand(idx: 0);
122
123 // If the input is a splat, we don't care for the number of users
124 if (isa<SplatElementsAttr>(Val: values)) {
125 return true;
126 }
127
128 // If this is the only use of the tensor it should be replaced as no
129 // additional memory is required
130 return inputOp.hasOneUse();
131}
132
133template <typename RangeType>
134auto transposeValues(const RangeType &data, ShapedType inputType,
135 ShapedType outputType,
136 llvm::ArrayRef<int64_t> permValues) {
137 using ElementType = std::decay_t<decltype(*std::begin(data))>;
138
139 assert(inputType.getElementType() == outputType.getElementType());
140
141 if (inputType.getNumElements() == 0)
142 return SmallVector<ElementType>{};
143
144 auto inputShape = inputType.getShape();
145
146 // The inverted permutation map and strides of the output are used to compute
147 // the contribution of a given dimension to the destination linear index in
148 // an order-independent way.
149 auto outputStrides = computeStrides(sizes: outputType.getShape());
150 auto invertedPermValues = invertPermutationVector(permutation: permValues);
151
152 auto initialValue = *std::begin(data);
153 SmallVector<ElementType> outputValues(inputType.getNumElements(),
154 initialValue);
155
156 for (const auto &it : llvm::enumerate(data)) {
157 auto srcLinearIndex = it.index();
158
159 uint64_t dstLinearIndex = 0;
160 for (int64_t dim = inputShape.size() - 1; dim >= 0; --dim) {
161 // Compute the index into the current dimension of the source vector.
162 auto sourceIndexForDim = srcLinearIndex % inputShape[dim];
163 srcLinearIndex /= inputShape[dim];
164
165 // Add the contribution of the current dimension to the output using the
166 // permutation map.
167 dstLinearIndex +=
168 outputStrides[invertedPermValues[dim]] * sourceIndexForDim;
169 }
170
171 outputValues[dstLinearIndex] = it.value();
172 }
173
174 return outputValues;
175}
176
177template <typename RangeType>
178DenseElementsAttr transposeType(const RangeType &data, ShapedType inputType,
179 ShapedType outputType,
180 llvm::ArrayRef<int64_t> permValues) {
181 using ElementType = std::decay_t<decltype(*std::begin(data))>;
182 SmallVector<ElementType> outputValues =
183 transposeValues(data, inputType, outputType, permValues);
184 return DenseElementsAttr::get(outputType,
185 llvm::ArrayRef<ElementType>(outputValues));
186}
187
188template <typename RangeType>
189DenseElementsAttr transposeRawType(const RangeType &data, ShapedType inputType,
190 ShapedType outputType,
191 llvm::ArrayRef<int64_t> permValues) {
192 using StorageType = std::decay_t<decltype(*std::begin(data))>;
193 SmallVector<StorageType> outputValues =
194 transposeValues(data, inputType, outputType, permValues);
195 llvm::ArrayRef<char> rawData(
196 reinterpret_cast<const char *>(outputValues.data()),
197 outputValues.size() * sizeof(StorageType));
198 return DenseElementsAttr::getFromRawBuffer(type: outputType, rawBuffer: rawData);
199}
200
201// A type specialized transposition of an ElementsAttr.
202// This implementation tries to operate on the underlying data in its raw
203// representation when possible to avoid allocating a large number of Attribute
204// objects.
205DenseElementsAttr transpose(ElementsAttr attr, ShapedType inputType,
206 ShapedType outputType,
207 llvm::ArrayRef<int64_t> permValues) {
208 // Handle generic ElementsAttr
209 if (auto data = attr.tryGetValues<bool>())
210 return transposeType(data: *data, inputType, outputType, permValues);
211
212 if (auto data = attr.tryGetValues<int8_t>())
213 return transposeType(data: *data, inputType, outputType, permValues);
214
215 if (auto data = attr.tryGetValues<int16_t>())
216 return transposeType(data: *data, inputType, outputType, permValues);
217
218 if (auto data = attr.tryGetValues<int32_t>())
219 return transposeType(data: *data, inputType, outputType, permValues);
220
221 if (auto data = attr.tryGetValues<int64_t>())
222 return transposeType(data: *data, inputType, outputType, permValues);
223
224 if (auto data = attr.tryGetValues<float>())
225 return transposeType(data: *data, inputType, outputType, permValues);
226
227 if (auto data = attr.tryGetValues<APFloat>())
228 return transposeType(data: *data, inputType, outputType, permValues);
229
230 // Handle DenseResourceElementsAttr
231 if (isa<DenseResourceElementsAttr>(Val: attr)) {
232 auto elementTy = attr.getElementType();
233
234 if (auto data = tryGetDenseResourceValues<bool>(attr);
235 data && elementTy.isInteger(width: 1))
236 return transposeType(data: *data, inputType, outputType, permValues);
237
238 if (auto data = tryGetDenseResourceValues<int8_t>(attr);
239 data && elementTy.isInteger(width: 8))
240 return transposeType(data: *data, inputType, outputType, permValues);
241
242 if (auto data = tryGetDenseResourceValues<int16_t>(attr);
243 data && elementTy.isInteger(width: 16))
244 return transposeType(data: *data, inputType, outputType, permValues);
245
246 if (auto data = tryGetDenseResourceValues<int32_t>(attr);
247 data && elementTy.isInteger(width: 32))
248 return transposeType(data: *data, inputType, outputType, permValues);
249
250 if (auto data = tryGetDenseResourceValues<int64_t>(attr);
251 data && elementTy.isInteger(width: 64))
252 return transposeType(data: *data, inputType, outputType, permValues);
253
254 if (auto data = tryGetDenseResourceValues<float>(attr);
255 data && elementTy.isF32())
256 return transposeType(data: *data, inputType, outputType, permValues);
257
258 if (auto data = tryGetDenseResourceValues<uint8_t>(attr);
259 data && isa<Float4E2M1FNType, Float8E4M3FNType, Float8E5M2Type,
260 Float8E8M0FNUType>(Val: elementTy))
261 return transposeRawType(data: *data, inputType, outputType, permValues);
262
263 if (auto data = tryGetDenseResourceValues<uint16_t>(attr);
264 data && isa<Float16Type, BFloat16Type>(Val: elementTy))
265 return transposeRawType(data: *data, inputType, outputType, permValues);
266
267 if (auto data = tryGetDenseResourceValues<double>(attr);
268 data && elementTy.isF64())
269 return transposeType(data: *data, inputType, outputType, permValues);
270 }
271
272 return nullptr;
273}
274
275struct TosaFoldConstantTranspose : public OpRewritePattern<tosa::TransposeOp> {
276 using Base::Base;
277
278 LogicalResult matchAndRewrite(tosa::TransposeOp op,
279 PatternRewriter &rewriter) const override {
280 auto outputType = cast<ShapedType>(Val: op.getType());
281 if (!outputType.hasRank() || !outputType.hasStaticShape())
282 return failure();
283 // TOSA supports quantized types.
284 if (!outputType.getElementType().isIntOrIndexOrFloat())
285 return failure();
286
287 ElementsAttr inputValues;
288 if (!matchPattern(value: op.getInput1(), pattern: m_Constant(bind_value: &inputValues)))
289 return failure();
290 // Make sure the input is a constant that has a single user.
291 if (!llvm::hasSingleElement(C: op.getInput1().getDefiningOp()->getUsers()))
292 return failure();
293
294 auto permValues = llvm::map_to_vector(
295 C: op.getPerms(), F: [](const int32_t v) { return static_cast<int64_t>(v); });
296
297 auto inputType = cast<ShapedType>(Val: op.getInput1().getType());
298
299 auto resultAttr = transpose(attr: inputValues, inputType, outputType, permValues);
300 if (!resultAttr) {
301 return rewriter.notifyMatchFailure(
302 arg&: op, msg: "unsupported attribute or element type");
303 }
304
305 rewriter.replaceOpWithNewOp<tosa::ConstOp>(op, args&: outputType, args&: resultAttr);
306 return success();
307 }
308};
309
310struct TosaFoldConstantReciprocal : public OpRewritePattern<ReciprocalOp> {
311
312 using Base::Base;
313
314 LogicalResult matchAndRewrite(ReciprocalOp recip,
315 PatternRewriter &rewriter) const override {
316 auto inputTensor = recip.getInput1();
317
318 // Check that we can apply folding
319 auto preCondCheck =
320 notifyIfNotConstantFloatTosaTensor(toCheck: inputTensor, location: recip, rewriter);
321 if (failed(Result: preCondCheck)) {
322 return preCondCheck;
323 }
324
325 // Extract the tensor values
326 DenseElementsAttr inputValues;
327 matchPattern(value: inputTensor, pattern: m_Constant(bind_value: &inputValues));
328
329 // Check whether this should be folded.
330 if (!constantUnaryOpShouldBeFolded(unaryOp: recip, values: inputValues)) {
331 return rewriter.notifyMatchFailure(
332 arg&: recip, msg: "Currently, reciprocals will only be folded if the input "
333 "tensor has a single user");
334 }
335
336 if (inputTensor.getType() != recip.getType())
337 return rewriter.notifyMatchFailure(
338 arg&: recip, msg: "input tensor and reciprocal output have different type");
339
340 // Create a new tensor with the updated values
341 auto newTensor = applyElementWise<APFloat, APFloat, FloatType>(
342 toTransform: inputValues, toApply: &ReciprocalOp::calcOneElement,
343 targetType: cast<FloatType>(Val: inputValues.getElementType()));
344
345 // Replace the use of the reciprocal with the transformed tensor
346 rewriter.replaceOpWithNewOp<ConstOp>(op: recip, args: newTensor.getType(), args&: newTensor);
347 return success();
348 }
349};
350
351/// Getting the axes position of the element which is located
352/// in the tensor at the counter index
353
354llvm::SmallVector<int64_t>
355getPositionFromIndex(int64_t index, llvm::ArrayRef<int64_t> tensorShape) {
356 int64_t remaining = index;
357 llvm::SmallVector<int64_t> position(tensorShape.size(), 0);
358 for (int64_t i = tensorShape.size() - 1; i >= 0; --i) {
359 position[i] = remaining % tensorShape[i];
360 remaining /= tensorShape[i];
361 }
362 return position;
363}
364
365/// Getting the index of the element which is located at the
366/// axes position in the tensor
367
368int64_t getIndexFromPosition(llvm::ArrayRef<int64_t> position,
369 llvm::ArrayRef<int64_t> tensorShape) {
370 int64_t index = 0;
371 int64_t multiplierTmp = 1;
372 for (int64_t i = position.size() - 1; i >= 0; --i) {
373 index += position[i] * multiplierTmp;
374 multiplierTmp *= tensorShape[i];
375 }
376 return index;
377}
378
379template <typename OperationType>
380llvm::APInt calculateReducedValue(const mlir::ElementsAttr &oldTensorAttr,
381 llvm::ArrayRef<int64_t> oldShape,
382 int64_t reductionAxis,
383 int64_t reductionIndex) {
384
385 llvm::SmallVector<int64_t> newShape(oldShape);
386 newShape[reductionAxis] = 1;
387 /// Let's calculate the position of the index
388 llvm::SmallVector<int64_t> position =
389 getPositionFromIndex(index: reductionIndex, tensorShape: newShape);
390 auto oldTensor = oldTensorAttr.getValues<llvm::APInt>();
391 /// Starting from the first positon along the reduction axis
392 position[reductionAxis] = 0;
393 int64_t indexAtOldTensor = getIndexFromPosition(position, tensorShape: oldShape);
394 llvm::APInt reducedValue = oldTensor[indexAtOldTensor];
395
396 for (int64_t reductionAxisVal = 1; reductionAxisVal < oldShape[reductionAxis];
397 ++reductionAxisVal) {
398
399 int64_t stride = llvm::product_of(Range: oldShape.drop_front(N: reductionAxis + 1));
400 int64_t index = indexAtOldTensor + stride * reductionAxisVal;
401 reducedValue =
402 OperationType::calcOneElement(reducedValue, oldTensor[index]);
403 }
404 return reducedValue;
405}
406
407template <typename OperationType>
408struct ReduceConstantOptimization : public OpRewritePattern<OperationType> {
409
410 ReduceConstantOptimization(MLIRContext *context,
411 bool aggressiveReduceConstant)
412 : OpRewritePattern<OperationType>(context),
413 aggressiveReduceConstant(aggressiveReduceConstant) {}
414
415 using OpRewritePattern<OperationType>::OpRewritePattern;
416
417 LogicalResult matchAndRewrite(OperationType op,
418 PatternRewriter &rewriter) const override {
419 Value inputOp = op.getInput();
420 auto constOp = inputOp.getDefiningOp<tosa::ConstOp>();
421
422 if (!constOp)
423 return rewriter.notifyMatchFailure(
424 op, "reduce input must be const operation");
425
426 if (!inputOp.hasOneUse() && !this->aggressiveReduceConstant)
427 return rewriter.notifyMatchFailure(
428 op, "input operation has more than one user");
429
430 auto resultType = cast<ShapedType>(op.getOutput().getType());
431
432 if (!resultType.hasStaticShape())
433 return rewriter.notifyMatchFailure(op, "result type shape is not static");
434
435 auto reductionAxis = op.getAxis();
436 const auto denseElementsAttr = constOp.getValues();
437 const auto shapedOldElementsValues =
438 cast<ShapedType>(Val: denseElementsAttr.getType());
439
440 if (!llvm::isa<IntegerType>(Val: shapedOldElementsValues.getElementType()))
441 return rewriter.notifyMatchFailure(
442 op, "reduce input currently supported with integer type");
443
444 auto oldShape = shapedOldElementsValues.getShape();
445 auto newShape = resultType.getShape();
446
447 int64_t newNumOfElements = llvm::product_of(newShape);
448 llvm::SmallVector<APInt> newReducedTensor(newNumOfElements);
449
450 for (int64_t reductionIndex = 0; reductionIndex < newNumOfElements;
451 ++reductionIndex) {
452
453 /// Let's reduce all the elements along this reduction axis
454 newReducedTensor[reductionIndex] = calculateReducedValue<OperationType>(
455 denseElementsAttr, oldShape, reductionAxis, reductionIndex);
456 }
457
458 auto rankedTensorType = cast<RankedTensorType>(resultType);
459 auto denseAttr =
460 mlir::DenseElementsAttr::get(rankedTensorType, newReducedTensor);
461 rewriter.replaceOpWithNewOp<tosa::ConstOp>(op, rankedTensorType, denseAttr);
462 return success();
463 }
464 const bool aggressiveReduceConstant;
465};
466
467} // namespace
468
469void mlir::tosa::populateTosaConstantReduction(MLIRContext *ctx,
470 RewritePatternSet &patterns,
471 bool aggressiveReduceConstant) {
472 patterns.add<ReduceConstantOptimization<ReduceAllOp>>(
473 arg&: ctx, args&: aggressiveReduceConstant);
474 patterns.add<ReduceConstantOptimization<ReduceAnyOp>>(
475 arg&: ctx, args&: aggressiveReduceConstant);
476 patterns.add<ReduceConstantOptimization<ReduceMaxOp>>(
477 arg&: ctx, args&: aggressiveReduceConstant);
478 patterns.add<ReduceConstantOptimization<ReduceMinOp>>(
479 arg&: ctx, args&: aggressiveReduceConstant);
480 patterns.add<ReduceConstantOptimization<ReduceProductOp>>(
481 arg&: ctx, args&: aggressiveReduceConstant);
482 patterns.add<ReduceConstantOptimization<ReduceSumOp>>(
483 arg&: ctx, args&: aggressiveReduceConstant);
484}
485
486void mlir::tosa::populateTosaFoldConstantTransposePatterns(
487 MLIRContext *ctx, RewritePatternSet &patterns) {
488 patterns.add<TosaFoldConstantTranspose>(arg&: ctx);
489}
490
491void mlir::tosa::populateTosaFoldConstantReciprocalPatterns(
492 MLIRContext *ctx, RewritePatternSet &patterns) {
493 patterns.add<TosaFoldConstantReciprocal>(arg&: ctx);
494}
495