1//===- RuntimeVerifiableOpInterfaceImpl.cpp - Op Verification -------------===//
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/MemRef/Transforms/RuntimeVerifiableOpInterfaceImpl.h"
10
11#include "mlir/Dialect/Affine/IR/AffineDialect.h"
12#include "mlir/Dialect/Arith/IR/Arith.h"
13#include "mlir/Dialect/Arith/Utils/Utils.h"
14#include "mlir/Dialect/ControlFlow/IR/ControlFlow.h"
15#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
16#include "mlir/Dialect/MemRef/IR/MemRef.h"
17#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
18#include "mlir/Dialect/SCF/IR/SCF.h"
19#include "mlir/Interfaces/RuntimeVerifiableOpInterface.h"
20
21using namespace mlir;
22
23namespace mlir {
24namespace memref {
25namespace {
26/// Generate a runtime check for lb <= value < ub.
27Value generateInBoundsCheck(OpBuilder &builder, Location loc, Value value,
28 Value lb, Value ub) {
29 Value inBounds1 = builder.createOrFold<arith::CmpIOp>(
30 location: loc, args: arith::CmpIPredicate::sge, args&: value, args&: lb);
31 Value inBounds2 = builder.createOrFold<arith::CmpIOp>(
32 location: loc, args: arith::CmpIPredicate::slt, args&: value, args&: ub);
33 Value inBounds =
34 builder.createOrFold<arith::AndIOp>(location: loc, args&: inBounds1, args&: inBounds2);
35 return inBounds;
36}
37
38struct AssumeAlignmentOpInterface
39 : public RuntimeVerifiableOpInterface::ExternalModel<
40 AssumeAlignmentOpInterface, AssumeAlignmentOp> {
41 void
42 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
43 function_ref<std::string(Operation *, StringRef)>
44 generateErrorMessage) const {
45 auto assumeOp = cast<AssumeAlignmentOp>(Val: op);
46 Value ptr = ExtractAlignedPointerAsIndexOp::create(builder, location: loc,
47 source: assumeOp.getMemref());
48 Value rest = arith::RemUIOp::create(
49 builder, location: loc, lhs: ptr,
50 rhs: arith::ConstantIndexOp::create(builder, location: loc, value: assumeOp.getAlignment()));
51 Value isAligned =
52 arith::CmpIOp::create(builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: rest,
53 rhs: arith::ConstantIndexOp::create(builder, location: loc, value: 0));
54 cf::AssertOp::create(
55 builder, location: loc, arg: isAligned,
56 msg: generateErrorMessage(op, "memref is not aligned to " +
57 std::to_string(val: assumeOp.getAlignment())));
58 }
59};
60
61struct CastOpInterface
62 : public RuntimeVerifiableOpInterface::ExternalModel<CastOpInterface,
63 CastOp> {
64 void
65 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
66 function_ref<std::string(Operation *, StringRef)>
67 generateErrorMessage) const {
68 auto castOp = cast<CastOp>(Val: op);
69 auto srcType = cast<BaseMemRefType>(Val: castOp.getSource().getType());
70
71 // Nothing to check if the result is an unranked memref.
72 auto resultType = dyn_cast<MemRefType>(Val: castOp.getType());
73 if (!resultType)
74 return;
75
76 if (isa<UnrankedMemRefType>(Val: srcType)) {
77 // Check rank.
78 Value srcRank = RankOp::create(builder, location: loc, memref: castOp.getSource());
79 Value resultRank =
80 arith::ConstantIndexOp::create(builder, location: loc, value: resultType.getRank());
81 Value isSameRank = arith::CmpIOp::create(
82 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: srcRank, rhs: resultRank);
83 cf::AssertOp::create(builder, location: loc, arg: isSameRank,
84 msg: generateErrorMessage(op, "rank mismatch"));
85 }
86
87 // Get source offset and strides. We do not have an op to get offsets and
88 // strides from unranked memrefs, so cast the source to a type with fully
89 // dynamic layout, from which we can then extract the offset and strides.
90 // (Rank was already verified.)
91 int64_t dynamicOffset = ShapedType::kDynamic;
92 SmallVector<int64_t> dynamicShape(resultType.getRank(),
93 ShapedType::kDynamic);
94 auto stridedLayout = StridedLayoutAttr::get(context: builder.getContext(),
95 offset: dynamicOffset, strides: dynamicShape);
96 auto dynStridesType =
97 MemRefType::get(shape: dynamicShape, elementType: resultType.getElementType(),
98 layout: stridedLayout, memorySpace: resultType.getMemorySpace());
99 Value helperCast =
100 CastOp::create(builder, location: loc, dest: dynStridesType, source: castOp.getSource());
101 auto metadataOp =
102 ExtractStridedMetadataOp::create(builder, location: loc, source: helperCast);
103
104 // Check dimension sizes.
105 for (const auto &it : llvm::enumerate(First: resultType.getShape())) {
106 // Static dim size -> static/dynamic dim size does not need verification.
107 if (auto rankedSrcType = dyn_cast<MemRefType>(Val&: srcType))
108 if (!rankedSrcType.isDynamicDim(idx: it.index()))
109 continue;
110
111 // Static/dynamic dim size -> dynamic dim size does not need verification.
112 if (resultType.isDynamicDim(idx: it.index()))
113 continue;
114
115 Value srcDimSz =
116 DimOp::create(builder, location: loc, source: castOp.getSource(), index: it.index());
117 Value resultDimSz =
118 arith::ConstantIndexOp::create(builder, location: loc, value: it.value());
119 Value isSameSz = arith::CmpIOp::create(
120 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: srcDimSz, rhs: resultDimSz);
121 cf::AssertOp::create(
122 builder, location: loc, arg: isSameSz,
123 msg: generateErrorMessage(op, "size mismatch of dim " +
124 std::to_string(val: it.index())));
125 }
126
127 // Get result offset and strides.
128 int64_t resultOffset;
129 SmallVector<int64_t> resultStrides;
130 if (failed(Result: resultType.getStridesAndOffset(strides&: resultStrides, offset&: resultOffset)))
131 return;
132
133 // Check offset.
134 if (resultOffset != ShapedType::kDynamic) {
135 // Static/dynamic offset -> dynamic offset does not need verification.
136 Value srcOffset = metadataOp.getResult(i: 1);
137 Value resultOffsetVal =
138 arith::ConstantIndexOp::create(builder, location: loc, value: resultOffset);
139 Value isSameOffset = arith::CmpIOp::create(
140 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: srcOffset, rhs: resultOffsetVal);
141 cf::AssertOp::create(builder, location: loc, arg: isSameOffset,
142 msg: generateErrorMessage(op, "offset mismatch"));
143 }
144
145 // Check strides.
146 for (const auto &it : llvm::enumerate(First&: resultStrides)) {
147 // Static/dynamic stride -> dynamic stride does not need verification.
148 if (it.value() == ShapedType::kDynamic)
149 continue;
150
151 Value srcStride =
152 metadataOp.getResult(i: 2 + resultType.getRank() + it.index());
153 Value resultStrideVal =
154 arith::ConstantIndexOp::create(builder, location: loc, value: it.value());
155 Value isSameStride = arith::CmpIOp::create(
156 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: srcStride, rhs: resultStrideVal);
157 cf::AssertOp::create(
158 builder, location: loc, arg: isSameStride,
159 msg: generateErrorMessage(op, "stride mismatch of dim " +
160 std::to_string(val: it.index())));
161 }
162 }
163};
164
165struct CopyOpInterface
166 : public RuntimeVerifiableOpInterface::ExternalModel<CopyOpInterface,
167 CopyOp> {
168 void
169 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
170 function_ref<std::string(Operation *, StringRef)>
171 generateErrorMessage) const {
172 auto copyOp = cast<CopyOp>(Val: op);
173 BaseMemRefType sourceType = copyOp.getSource().getType();
174 BaseMemRefType targetType = copyOp.getTarget().getType();
175 auto rankedSourceType = dyn_cast<MemRefType>(Val&: sourceType);
176 auto rankedTargetType = dyn_cast<MemRefType>(Val&: targetType);
177
178 // TODO: Verification for unranked memrefs is not supported yet.
179 if (!rankedSourceType || !rankedTargetType)
180 return;
181
182 assert(sourceType.getRank() == targetType.getRank() && "rank mismatch");
183 for (int64_t i = 0, e = sourceType.getRank(); i < e; ++i) {
184 // Fully static dimensions in both source and target operand are already
185 // verified by the op verifier.
186 if (!rankedSourceType.isDynamicDim(idx: i) &&
187 !rankedTargetType.isDynamicDim(idx: i))
188 continue;
189 auto getDimSize = [&](Value memRef, MemRefType type,
190 int64_t dim) -> Value {
191 return type.isDynamicDim(idx: dim)
192 ? DimOp::create(builder, location: loc, source: memRef, index: dim).getResult()
193 : arith::ConstantIndexOp::create(builder, location: loc,
194 value: type.getDimSize(idx: dim))
195 .getResult();
196 };
197 Value sourceDim = getDimSize(copyOp.getSource(), rankedSourceType, i);
198 Value targetDim = getDimSize(copyOp.getTarget(), rankedTargetType, i);
199 Value sameDimSize = arith::CmpIOp::create(
200 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: sourceDim, rhs: targetDim);
201 cf::AssertOp::create(
202 builder, location: loc, arg: sameDimSize,
203 msg: generateErrorMessage(op, "size of " + std::to_string(val: i) +
204 "-th source/target dim does not match"));
205 }
206 }
207};
208
209struct DimOpInterface
210 : public RuntimeVerifiableOpInterface::ExternalModel<DimOpInterface,
211 DimOp> {
212 void
213 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
214 function_ref<std::string(Operation *, StringRef)>
215 generateErrorMessage) const {
216 auto dimOp = cast<DimOp>(Val: op);
217 Value rank = RankOp::create(builder, location: loc, memref: dimOp.getSource());
218 Value zero = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
219 cf::AssertOp::create(
220 builder, location: loc,
221 arg: generateInBoundsCheck(builder, loc, value: dimOp.getIndex(), lb: zero, ub: rank),
222 msg: generateErrorMessage(op, "index is out of bounds"));
223 }
224};
225
226/// Verifies that the indices on load/store ops are in-bounds of the memref's
227/// index space: 0 <= index#i < dim#i
228template <typename LoadStoreOp>
229struct LoadStoreOpInterface
230 : public RuntimeVerifiableOpInterface::ExternalModel<
231 LoadStoreOpInterface<LoadStoreOp>, LoadStoreOp> {
232 void
233 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
234 function_ref<std::string(Operation *, StringRef)>
235 generateErrorMessage) const {
236 auto loadStoreOp = cast<LoadStoreOp>(op);
237
238 auto memref = loadStoreOp.getMemref();
239 auto rank = memref.getType().getRank();
240 if (rank == 0) {
241 return;
242 }
243 auto indices = loadStoreOp.getIndices();
244
245 auto zero = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
246 Value assertCond;
247 for (auto i : llvm::seq<int64_t>(0, rank)) {
248 Value dimOp = builder.createOrFold<memref::DimOp>(loc, memref, i);
249 Value inBounds =
250 generateInBoundsCheck(builder, loc, indices[i], zero, dimOp);
251 assertCond =
252 i > 0 ? builder.createOrFold<arith::AndIOp>(location: loc, args&: assertCond, args&: inBounds)
253 : inBounds;
254 }
255 cf::AssertOp::create(builder, location: loc, arg: assertCond,
256 msg: generateErrorMessage(op, "out-of-bounds access"));
257 }
258};
259
260struct SubViewOpInterface
261 : public RuntimeVerifiableOpInterface::ExternalModel<SubViewOpInterface,
262 SubViewOp> {
263 void
264 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
265 function_ref<std::string(Operation *, StringRef)>
266 generateErrorMessage) const {
267 auto subView = cast<SubViewOp>(Val: op);
268 MemRefType sourceType = subView.getSource().getType();
269
270 // For each dimension, assert that:
271 // For empty slices (size == 0) : 0 <= offset <= dim_size
272 // For non-empty slices (size > 0): 0 <= offset < dim_size
273 // 0 <= offset + (size - 1) * stride
274 // dim_size
275 Value zero = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
276 Value one = arith::ConstantIndexOp::create(builder, location: loc, value: 1);
277
278 auto metadataOp =
279 ExtractStridedMetadataOp::create(builder, location: loc, source: subView.getSource());
280
281 for (int64_t i : llvm::seq<int64_t>(Begin: 0, End: sourceType.getRank())) {
282 // Reset insertion point to before the operation for each dimension.
283 builder.setInsertionPoint(subView);
284
285 Value offset = getValueOrCreateConstantIndexOp(
286 b&: builder, loc, ofr: subView.getMixedOffsets()[i]);
287 Value size = getValueOrCreateConstantIndexOp(b&: builder, loc,
288 ofr: subView.getMixedSizes()[i]);
289 Value stride = getValueOrCreateConstantIndexOp(
290 b&: builder, loc, ofr: subView.getMixedStrides()[i]);
291 Value dimSize = metadataOp.getSizes()[i];
292
293 // Verify that offset is in-bounds (conditional on slice size).
294 Value sizeIsZero = arith::CmpIOp::create(
295 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: size, rhs: zero);
296 auto offsetCheckIf = scf::IfOp::create(
297 builder, location: loc, cond: sizeIsZero,
298 thenBuilder: [&](OpBuilder &b, Location loc) {
299 // For empty slices, offset can be at the boundary: 0 <= offset <=
300 // dimSize.
301 Value offsetGEZero = arith::CmpIOp::create(
302 builder&: b, location: loc, predicate: arith::CmpIPredicate::sge, lhs: offset, rhs: zero);
303 Value offsetLEDimSize = arith::CmpIOp::create(
304 builder&: b, location: loc, predicate: arith::CmpIPredicate::sle, lhs: offset, rhs: dimSize);
305 Value emptyOffsetValid =
306 arith::AndIOp::create(builder&: b, location: loc, lhs: offsetGEZero, rhs: offsetLEDimSize);
307 scf::YieldOp::create(builder&: b, location: loc, results: emptyOffsetValid);
308 },
309 elseBuilder: [&](OpBuilder &b, Location loc) {
310 // For non-empty slices, offset must be a valid index: 0 <= offset
311 // dimSize.
312 Value offsetInBounds =
313 generateInBoundsCheck(builder&: b, loc, value: offset, lb: zero, ub: dimSize);
314 scf::YieldOp::create(builder&: b, location: loc, results: offsetInBounds);
315 });
316
317 Value offsetCondition = offsetCheckIf.getResult(i: 0);
318 cf::AssertOp::create(builder, location: loc, arg: offsetCondition,
319 msg: generateErrorMessage(op, "offset " +
320 std::to_string(val: i) +
321 " is out-of-bounds"));
322
323 // Verify that the slice endpoint is in-bounds (only for non-empty
324 // slices).
325 Value sizeIsNonZero = arith::CmpIOp::create(
326 builder, location: loc, predicate: arith::CmpIPredicate::sgt, lhs: size, rhs: zero);
327 auto ifOp = scf::IfOp::create(
328 builder, location: loc, cond: sizeIsNonZero,
329 thenBuilder: [&](OpBuilder &b, Location loc) {
330 // Verify that slice does not run out-of-bounds.
331 Value sizeMinusOne = arith::SubIOp::create(builder&: b, location: loc, lhs: size, rhs: one);
332 Value sizeMinusOneTimesStride =
333 arith::MulIOp::create(builder&: b, location: loc, lhs: sizeMinusOne, rhs: stride);
334 Value lastPos =
335 arith::AddIOp::create(builder&: b, location: loc, lhs: offset, rhs: sizeMinusOneTimesStride);
336 Value lastPosInBounds =
337 generateInBoundsCheck(builder&: b, loc, value: lastPos, lb: zero, ub: dimSize);
338 scf::YieldOp::create(builder&: b, location: loc, results: lastPosInBounds);
339 },
340 elseBuilder: [&](OpBuilder &b, Location loc) {
341 Value trueVal =
342 arith::ConstantOp::create(builder&: b, location: loc, value: b.getBoolAttr(value: true));
343 scf::YieldOp::create(builder&: b, location: loc, results: trueVal);
344 });
345
346 Value finalCondition = ifOp.getResult(i: 0);
347 cf::AssertOp::create(
348 builder, location: loc, arg: finalCondition,
349 msg: generateErrorMessage(op,
350 "subview runs out-of-bounds along dimension " +
351 std::to_string(val: i)));
352 }
353 }
354};
355
356struct ExpandShapeOpInterface
357 : public RuntimeVerifiableOpInterface::ExternalModel<ExpandShapeOpInterface,
358 ExpandShapeOp> {
359 void
360 generateRuntimeVerification(Operation *op, OpBuilder &builder, Location loc,
361 function_ref<std::string(Operation *, StringRef)>
362 generateErrorMessage) const {
363 auto expandShapeOp = cast<ExpandShapeOp>(Val: op);
364
365 SmallVector<OpFoldResult> outputShape = expandShapeOp.getMixedOutputShape();
366
367 // Verify that the product of output dim sizes in each reassociation group
368 // equals the corresponding input dim size.
369 for (const auto &it :
370 llvm::enumerate(First: expandShapeOp.getReassociationIndices())) {
371 Value srcDimSz =
372 DimOp::create(builder, location: loc, source: expandShapeOp.getSrc(), index: it.index());
373 Value groupProduct = getValueOrCreateConstantIndexOp(
374 b&: builder, loc, ofr: outputShape[it.value().front()]);
375 for (int64_t resultDim : llvm::drop_begin(RangeOrContainer&: it.value())) {
376 Value dimSz = getValueOrCreateConstantIndexOp(b&: builder, loc,
377 ofr: outputShape[resultDim]);
378 groupProduct = arith::MulIOp::create(builder, location: loc, lhs: groupProduct, rhs: dimSz);
379 }
380 Value isEqual = arith::CmpIOp::create(
381 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: groupProduct, rhs: srcDimSz);
382 cf::AssertOp::create(
383 builder, location: loc, arg: isEqual,
384 msg: generateErrorMessage(op, "product of output dims in reassoc group "
385 "does not equal input dim"));
386 }
387 }
388};
389} // namespace
390} // namespace memref
391} // namespace mlir
392
393void mlir::memref::registerRuntimeVerifiableOpInterfaceExternalModels(
394 DialectRegistry &registry) {
395 registry.addExtension(extensionFn: +[](MLIRContext *ctx, memref::MemRefDialect *dialect) {
396 AssumeAlignmentOp::attachInterface<AssumeAlignmentOpInterface>(context&: *ctx);
397 AtomicRMWOp::attachInterface<LoadStoreOpInterface<AtomicRMWOp>>(context&: *ctx);
398 CastOp::attachInterface<CastOpInterface>(context&: *ctx);
399 CopyOp::attachInterface<CopyOpInterface>(context&: *ctx);
400 DimOp::attachInterface<DimOpInterface>(context&: *ctx);
401 ExpandShapeOp::attachInterface<ExpandShapeOpInterface>(context&: *ctx);
402 GenericAtomicRMWOp::attachInterface<
403 LoadStoreOpInterface<GenericAtomicRMWOp>>(context&: *ctx);
404 LoadOp::attachInterface<LoadStoreOpInterface<LoadOp>>(context&: *ctx);
405 StoreOp::attachInterface<LoadStoreOpInterface<StoreOp>>(context&: *ctx);
406 SubViewOp::attachInterface<SubViewOpInterface>(context&: *ctx);
407 // Note: There is nothing to verify for ReinterpretCastOp.
408
409 // Load additional dialects of which ops may get created.
410 ctx->loadDialect<affine::AffineDialect, arith::ArithDialect,
411 cf::ControlFlowDialect, scf::SCFDialect>();
412 });
413}
414