1//===- TosaGatherScatterHardening.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// This file implements a pass that clamps gather and scatter indices to the
10// statically known bounds of their indexed tensors.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Tosa/Transforms/Passes.h"
15
16#include "mlir/Dialect/Func/IR/FuncOps.h"
17#include "mlir/Dialect/Tosa/IR/TosaOps.h"
18#include "mlir/IR/Builders.h"
19#include "mlir/IR/BuiltinAttributes.h"
20#include "mlir/IR/BuiltinTypes.h"
21#include "mlir/IR/Matchers.h"
22#include "mlir/IR/PatternMatch.h"
23#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
24#include "llvm/ADT/APInt.h"
25#include "llvm/ADT/STLExtras.h"
26
27#include <algorithm>
28#include <cstdint>
29#include <type_traits>
30
31namespace mlir {
32namespace tosa {
33#define GEN_PASS_DEF_TOSAGATHERSCATTERHARDENINGPASS
34#include "mlir/Dialect/Tosa/Transforms/Passes.h.inc"
35} // namespace tosa
36} // namespace mlir
37
38using namespace mlir;
39using namespace mlir::tosa;
40
41namespace {
42
43/// Returns the effective upper bound when the indexed dimension is static.
44static FailureOr<int64_t> getIndexUpperBound(Operation *op) {
45 Value values = op->getOperand(idx: 0);
46 auto valuesType = dyn_cast<RankedTensorType>(Val: values.getType());
47 if (!valuesType || valuesType.isDynamicDim(idx: 1)) {
48 op->emitOpError(message: "requires a statically known indexed dimension for "
49 "gather/scatter hardening");
50 return failure();
51 }
52
53 auto indicesType = cast<ShapedType>(Val: op->getOperand(idx: 1).getType());
54 auto elementType = cast<IntegerType>(Val: indicesType.getElementType());
55
56 // The upper bound must be representable in the index element type.
57 int64_t maxRepresentable =
58 llvm::APInt::getSignedMaxValue(numBits: elementType.getWidth()).getSExtValue();
59 return std::min(a: valuesType.getDimSize(idx: 1) - 1, b: maxRepresentable);
60}
61
62/// Returns whether the indices already have sufficiently restrictive bounds.
63template <typename OuterOp, typename InnerOp>
64static bool isAlreadyHardened(Value indices, int64_t requiredUpperBound) {
65 static_assert(
66 (std::is_same_v<OuterOp, tosa::MinimumOp> &&
67 std::is_same_v<InnerOp, tosa::MaximumOp>) ||
68 (std::is_same_v<OuterOp, tosa::MaximumOp> &&
69 std::is_same_v<InnerOp, tosa::MinimumOp>),
70 "expected a tosa::MinimumOp/tosa::MaximumOp pair in either order");
71
72 auto outerOp = indices.getDefiningOp<OuterOp>();
73 if (!outerOp)
74 return false;
75
76 // Either operand can be the bound, including when both are constants. A
77 // constant match alone is not enough: try the other operand if it is unsafe.
78 for (unsigned boundOperand = 0; boundOperand < 2; ++boundOperand) {
79 llvm::APInt outerBound;
80 if (!matchPattern(outerOp->getOperand(boundOperand),
81 m_ConstantInt(bind_value: &outerBound)))
82 continue;
83
84 llvm::APInt requiredUpper(outerBound.getBitWidth(),
85 static_cast<uint64_t>(requiredUpperBound));
86 // The outer bound must itself be in range, since it can override the inner
87 // bound, e.g. minimum(maximum(x, 0), -1) would produce -1. This guarantees
88 // the other operand is meeting the outer bound check (e.g. smaller or equal
89 // to the required upper bound if outer op is a minimum). The inner
90 // operation only needs to enforce the opposite bound.
91 if (outerBound.isNegative() || outerBound.sgt(RHS: requiredUpper))
92 continue;
93
94 auto matchesInnerBound = [&](Value value) {
95 llvm::APInt innerBound;
96 if (!matchPattern(value, pattern: m_ConstantInt(bind_value: &innerBound)))
97 return false;
98 return isa<tosa::MinimumOp>(outerOp) ? !innerBound.isNegative()
99 : innerBound.sle(RHS: requiredUpper);
100 };
101
102 // Check whether other operand of the outer op is also a constant and is
103 // meeting the inner bound check. No inner op involved and the result is
104 // therefore completely within bound thanks to the earlier check.
105 Value innerResult = outerOp->getOperand(1 - boundOperand);
106 if (matchesInnerBound(innerResult))
107 return true;
108 // The other outer op operand is not a constant so check that the inner op
109 // enforces inner bound check.
110 if (auto innerOp = innerResult.getDefiningOp<InnerOp>())
111 if (llvm::any_of(innerOp->getOperands(), matchesInnerBound))
112 return true;
113 }
114 return false;
115}
116
117/// Creates a rank-two splat constant suitable for index broadcasting.
118static Value createIndexBoundConstant(OpBuilder &builder, Location loc,
119 IntegerType elementType, int64_t value) {
120 auto type = RankedTensorType::get(shape: {1, 1}, elementType);
121 auto valueAttr =
122 IntegerAttr::get(type: elementType, value: llvm::APInt(elementType.getWidth(),
123 static_cast<uint64_t>(value)));
124 auto values = DenseElementsAttr::get(type, values: valueAttr);
125 return tosa::ConstOp::create(builder, location: loc, output: type, values).getResult();
126}
127
128/// Independently hardens one gather or scatter operation's indices.
129template <typename OpTy>
130struct HardenIndexUsePattern final : OpRewritePattern<OpTy> {
131 HardenIndexUsePattern(MLIRContext *context, bool &hardeningFailed)
132 : OpRewritePattern<OpTy>(context), hardeningFailed(hardeningFailed) {}
133
134 LogicalResult matchAndRewrite(OpTy op,
135 PatternRewriter &rewriter) const override {
136 FailureOr<int64_t> upperBound = getIndexUpperBound(op.getOperation());
137 if (failed(Result: upperBound)) {
138 hardeningFailed = true;
139 return rewriter.notifyMatchFailure(
140 op, "indexed dimension does not have a static upper bound");
141 }
142
143 Value indices = op->getOperand(1);
144 if (isAlreadyHardened<tosa::MinimumOp, tosa::MaximumOp>(indices,
145 requiredUpperBound: *upperBound) ||
146 isAlreadyHardened<tosa::MaximumOp, tosa::MinimumOp>(indices,
147 requiredUpperBound: *upperBound))
148 return rewriter.notifyMatchFailure(op, "indices are already hardened");
149
150 auto indicesType = cast<ShapedType>(Val: indices.getType());
151 auto elementType = cast<IntegerType>(Val: indicesType.getElementType());
152 Value lowerBound =
153 createIndexBoundConstant(rewriter, op.getLoc(), elementType, 0);
154 Value upperBoundValue = createIndexBoundConstant(rewriter, op.getLoc(),
155 elementType, *upperBound);
156 Value nonNegativeIndices =
157 tosa::MaximumOp::create(rewriter, op.getLoc(), indices.getType(),
158 indices, lowerBound)
159 .getResult();
160 Value clampedIndices =
161 tosa::MinimumOp::create(rewriter, op.getLoc(), indices.getType(),
162 nonNegativeIndices, upperBoundValue)
163 .getResult();
164
165 rewriter.modifyOpInPlace(
166 op, [&] { op->setOperand(/*indices=*/1, clampedIndices); });
167 return success();
168 }
169
170private:
171 bool &hardeningFailed;
172};
173
174struct TosaGatherScatterHardeningPass
175 : public tosa::impl::TosaGatherScatterHardeningPassBase<
176 TosaGatherScatterHardeningPass> {
177 using Base::Base;
178
179 void runOnOperation() override {
180 bool hardeningFailed = false;
181 RewritePatternSet patterns(&getContext());
182 patterns.add<HardenIndexUsePattern<tosa::GatherOp>,
183 HardenIndexUsePattern<tosa::ScatterOp>>(arg: &getContext(),
184 args&: hardeningFailed);
185 if (failed(Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns))) ||
186 hardeningFailed)
187 signalPassFailure();
188 }
189};
190
191} // namespace
192