1//===- Verifier.cpp - MLIR Verifier Implementation ------------------------===//
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 the verify() methods on the various IR types, performing
10// (potentially expensive) checks on the holistic structure of the code. This
11// can be used for detecting bugs in compiler transformations and hand written
12// .mlir files.
13//
14// The checks in this file are only for things that can occur as part of IR
15// transformations: e.g. violation of dominance information, malformed operation
16// attributes, etc. MLIR supports transformations moving IR through locally
17// invalid states (e.g. unlinking an operation from a block before re-inserting
18// it in a new place), but each transformation must complete with the IR in a
19// valid form.
20//
21// This should not check for things that are always wrong by construction (e.g.
22// attributes or other immutable structures that are incorrect), because those
23// are not mutable and can be checked at time of construction.
24//
25//===----------------------------------------------------------------------===//
26
27#include "mlir/IR/Verifier.h"
28#include "mlir/IR/Attributes.h"
29#include "mlir/IR/BuiltinTypes.h"
30#include "mlir/IR/Dialect.h"
31#include "mlir/IR/Dominance.h"
32#include "mlir/IR/Operation.h"
33#include "mlir/IR/RegionKindInterface.h"
34#include "mlir/IR/Threading.h"
35#include "llvm/ADT/PointerIntPair.h"
36#include <optional>
37
38using namespace mlir;
39
40namespace {
41/// This class encapsulates all the state used to verify an operation region.
42class OperationVerifier {
43public:
44 /// If `verifyRecursively` is true, then this will also recursively verify
45 /// nested operations.
46 OperationVerifier(MLIRContext *ctx, bool verifyRecursively)
47 : tokenType(TokenType::get(ctx)), verifyRecursively(verifyRecursively) {}
48
49 /// Verify the given operation.
50 LogicalResult verifyOpAndDominance(Operation &op);
51
52private:
53 using WorkItem = llvm::PointerUnion<Operation *, Block *>;
54 using WorkItemEntry = llvm::PointerIntPair<WorkItem, 1, bool>;
55
56 /// This verifier uses a DFS of the tree of operations/blocks. The method
57 /// verifyOnEntrance is invoked when we visit a node for the first time, i.e.
58 /// before visiting its children. The method verifyOnExit is invoked
59 /// upon exit from the subtree, i.e. when we visit a node for the second time.
60 LogicalResult verifyOnEntrance(Block &block);
61 LogicalResult verifyOnEntrance(Operation &op);
62 LogicalResult
63 verifyTokenValue(Operation &producer, Value value,
64 function_ref<InFlightDiagnostic()> emitProducerError);
65 LogicalResult verifyTokenValues(Operation &op);
66 LogicalResult verifyTokenBlockArgument(Block &block, BlockArgument arg,
67 unsigned idx);
68
69 LogicalResult verifyOnExit(Block &block);
70 LogicalResult verifyOnExit(Operation &op);
71
72 /// Verify the properties and dominance relationships of this operation.
73 LogicalResult verifyOperation(Operation &op);
74
75 /// Verify the dominance property of regions contained within the given
76 /// Operation.
77 LogicalResult verifyDominanceOfContainedRegions(Operation &op,
78 DominanceInfo &domInfo);
79
80 /// The cached instance of the builtin token type.
81 TokenType tokenType;
82
83 /// A flag indicating if this verifier should recursively verify nested
84 /// operations.
85 bool verifyRecursively;
86};
87} // namespace
88
89LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) {
90 // Verify the operation first, collecting any IsolatedFromAbove operations.
91 if (failed(Result: verifyOperation(op)))
92 return failure();
93
94 // Since everything looks structurally ok to this point, we do a dominance
95 // check for any nested regions. We do this as a second pass since malformed
96 // CFG's can cause dominator analysis construction to crash and we want the
97 // verifier to be resilient to malformed code.
98 if (op.getNumRegions() != 0) {
99 DominanceInfo domInfo;
100 if (failed(Result: verifyDominanceOfContainedRegions(op, domInfo)))
101 return failure();
102 }
103
104 return success();
105}
106
107/// Returns true if this block may be valid without terminator. That is if:
108/// - it does not have a parent region.
109/// - Or the parent region have a single block and:
110/// - This region does not have a parent op.
111/// - Or the parent op is unregistered.
112/// - Or the parent op has the NoTerminator trait.
113static bool mayBeValidWithoutTerminator(Block *block) {
114 if (!block->getParent())
115 return true;
116 if (!llvm::hasSingleElement(C&: *block->getParent()))
117 return false;
118 Operation *op = block->getParentOp();
119 return !op || op->mightHaveTrait<OpTrait::NoTerminator>();
120}
121
122LogicalResult OperationVerifier::verifyTokenValue(
123 Operation &producer, Value value,
124 function_ref<InFlightDiagnostic()> emitProducerError) {
125 if (value.getType() != tokenType)
126 return success();
127
128 if (!producer.mightHaveTrait<OpTrait::TokenProducerTrait>())
129 return emitProducerError();
130
131 for (OpOperand &use : value.getUses()) {
132 Operation *user = use.getOwner();
133 if (user->mightHaveTrait<OpTrait::TokenConsumerTrait>())
134 continue;
135
136 return user->emitOpError()
137 << "consumes token operand #" << use.getOperandNumber()
138 << " but does not have the TokenConsumerTrait";
139 }
140
141 return success();
142}
143
144LogicalResult OperationVerifier::verifyTokenValues(Operation &op) {
145 for (auto resultIt : llvm::enumerate(First: op.getResults())) {
146 unsigned idx = resultIt.index();
147 OpResult result = resultIt.value();
148 if (failed(Result: verifyTokenValue(producer&: op, value: result, emitProducerError: [&]() {
149 return op.emitOpError()
150 << "produces token result #" << idx
151 << " but does not have the TokenProducerTrait";
152 })))
153 return failure();
154 }
155
156 for (Region &region : op.getRegions()) {
157 if (region.empty())
158 continue;
159
160 Block &entryBlock = region.front();
161 for (auto argIt : llvm::enumerate(First: entryBlock.getArguments())) {
162 unsigned idx = argIt.index();
163 BlockArgument arg = argIt.value();
164 if (failed(Result: verifyTokenValue(producer&: op, value: arg, emitProducerError: [&]() {
165 return emitError(loc: arg.getLoc(), message: "token entry block argument #")
166 << idx << " requires the parent operation to have the "
167 << "TokenProducerTrait";
168 })))
169 return failure();
170 }
171 }
172
173 return success();
174}
175
176LogicalResult OperationVerifier::verifyTokenBlockArgument(Block &block,
177 BlockArgument arg,
178 unsigned idx) {
179 if (arg.getType() != tokenType)
180 return success();
181
182 // The producer-trait check on the parent op (and the token consumer check
183 // on the uses) is performed by `verifyTokenValues` when it iterates the
184 // entry block arguments of an op's regions. Here we only enforce that
185 // tokens are not used as non-entry block arguments.
186 if (!block.getParent() || !block.isEntryBlock())
187 return emitError(loc: arg.getLoc(), message: "token block argument #")
188 << idx << " is only allowed in a region entry block";
189
190 return success();
191}
192
193LogicalResult OperationVerifier::verifyOnEntrance(Block &block) {
194 // Get the parent op and context for cross-context checks. Both are available
195 // whenever the block lives inside a region that has a parent operation.
196 Operation *parentOp = block.getParentOp();
197 MLIRContext *blockCtx = parentOp ? parentOp->getContext() : nullptr;
198
199 for (auto [idx, arg] : llvm::enumerate(First: block.getArguments())) {
200 if (arg.getOwner() != &block)
201 return emitError(loc: arg.getLoc(), message: "block argument not owned by block");
202 if (blockCtx) {
203 // Check the location first; if it is wrong we must use the parent op's
204 // location to emit the error (the arg location would route to the wrong
205 // context's diagnostic handler).
206 if (arg.getLoc().getContext() != blockCtx)
207 return emitError(loc: parentOp->getLoc(), message: "block argument #")
208 << idx
209 << " location from a different MLIRContext than its "
210 "parent operation";
211 if (arg.getType().getContext() != blockCtx)
212 return emitError(loc: arg.getLoc(), message: "block argument #")
213 << idx
214 << " type from a different MLIRContext than its "
215 "parent operation";
216 }
217 if (failed(Result: verifyTokenBlockArgument(block, arg, idx)))
218 return failure();
219 }
220
221 // Verify that this block has a terminator.
222 if (block.empty()) {
223 if (mayBeValidWithoutTerminator(block: &block))
224 return success();
225 return emitError(loc: block.getParent()->getLoc(),
226 message: "empty block: expect at least a terminator");
227 }
228
229 // Check each operation, and make sure there are no branches out of the
230 // middle of this block.
231 for (Operation &op : block) {
232 // Only the last instructions is allowed to have successors.
233 if (op.getNumSuccessors() != 0 && &op != &block.back())
234 return op.emitError(
235 message: "operation with block successors must terminate its parent block");
236 // Check that each op's location (which defines its context) is from the
237 // same MLIRContext as the enclosing block. We cannot use op.emitError()
238 // here because op's context is the wrong one; emit via the parent op's
239 // location instead.
240 if (blockCtx && op.getContext() != blockCtx) {
241 emitError(loc: parentOp->getLoc(), message: "operation '")
242 << op.getName()
243 << "' has a location from a different MLIRContext than its "
244 "enclosing block";
245 return failure();
246 }
247 }
248
249 return success();
250}
251
252LogicalResult OperationVerifier::verifyOnExit(Block &block) {
253 // Verify that this block is not branching to a block of a different
254 // region.
255 for (Block *successor : block.getSuccessors())
256 if (successor->getParent() != block.getParent())
257 return block.back().emitOpError(
258 message: "branching to block of a different region");
259
260 // If this block doesn't have to have a terminator, don't require it.
261 if (mayBeValidWithoutTerminator(block: &block))
262 return success();
263
264 Operation &terminator = block.back();
265 if (!terminator.mightHaveTrait<OpTrait::IsTerminator>())
266 return block.back().emitError(message: "block with no terminator, has ")
267 << terminator;
268
269 return success();
270}
271
272LogicalResult OperationVerifier::verifyOnEntrance(Operation &op) {
273 // op.getContext() is defined as location->getContext(), so opCtx is the
274 // location's context by construction. The OperationName, however, carries
275 // its own context reference and can independently point elsewhere.
276 MLIRContext *opCtx = op.getContext();
277 if (op.getName().getContext() != opCtx)
278 return op.emitError(
279 message: "operation name from a different MLIRContext than this operation");
280
281 // Check result types are from the same context as the operation.
282 for (auto [i, result] : llvm::enumerate(First: op.getResults())) {
283 if (result.getType().getContext() != opCtx)
284 return op.emitOpError()
285 << "result #" << i
286 << " type from a different MLIRContext than this operation";
287 }
288
289 // Check that operands are non-nil and their types are from the same context.
290 for (auto [i, operand] : llvm::enumerate(First: op.getOperands())) {
291 if (!operand)
292 return op.emitError(message: "null operand found");
293 if (operand.getType().getContext() != opCtx)
294 return op.emitOpError()
295 << "operand #" << i
296 << " type from a different MLIRContext than this operation";
297 }
298
299 /// Verify that all of the attributes are okay.
300 for (auto attr : op.getDiscardableAttrDictionary()) {
301 if (attr.getValue().getContext() != opCtx)
302 return op.emitOpError()
303 << "discardable attribute '" << attr.getName()
304 << "' value from a different MLIRContext than this operation";
305 // Check for any optional dialect specific attributes.
306 if (auto *dialect = attr.getNameDialect())
307 if (failed(Result: dialect->verifyOperationAttribute(&op, attr)))
308 return failure();
309 }
310
311 // If we can get operation info for this, check the custom hook.
312 OperationName opName = op.getName();
313 std::optional<RegisteredOperationName> registeredInfo =
314 opName.getRegisteredInfo();
315 if (registeredInfo && failed(Result: registeredInfo->verifyInvariants(op: &op)))
316 return failure();
317
318 if (failed(Result: verifyTokenValues(op)))
319 return failure();
320
321 unsigned numRegions = op.getNumRegions();
322 if (!numRegions)
323 return success();
324 auto kindInterface = dyn_cast<RegionKindInterface>(Val: &op);
325 // Verify that all child regions are ok.
326 MutableArrayRef<Region> regions = op.getRegions();
327 for (unsigned i = 0; i < numRegions; ++i) {
328 Region &region = regions[i];
329 RegionKind kind =
330 kindInterface ? kindInterface.getRegionKind(index: i) : RegionKind::SSACFG;
331 // Check that Graph Regions only have a single basic block. This is
332 // similar to the code in SingleBlockImplicitTerminator, but doesn't
333 // require the trait to be specified. This arbitrary limitation is
334 // designed to limit the number of cases that have to be handled by
335 // transforms and conversions.
336 if (op.isRegistered() && kind == RegionKind::Graph) {
337 // Non-empty regions must contain a single basic block.
338 if (!region.empty() && !region.hasOneBlock())
339 return op.emitOpError(message: "expects graph region #")
340 << i << " to have 0 or 1 blocks";
341 }
342
343 if (region.empty())
344 continue;
345
346 // Verify the first block has no predecessors.
347 Block *firstBB = &region.front();
348 if (!firstBB->hasNoPredecessors())
349 return emitError(loc: op.getLoc(),
350 message: "entry block of region may not have predecessors");
351 }
352 return success();
353}
354
355LogicalResult OperationVerifier::verifyOnExit(Operation &op) {
356 SmallVector<Operation *> opsWithIsolatedRegions;
357 if (verifyRecursively) {
358 for (Region &region : op.getRegions())
359 for (Block &block : region)
360 for (Operation &o : block)
361 if (o.getNumRegions() != 0 &&
362 o.hasTrait<OpTrait::IsIsolatedFromAbove>())
363 opsWithIsolatedRegions.push_back(Elt: &o);
364 }
365
366 std::atomic<bool> opFailedVerify = false;
367 parallelForEach(context: op.getContext(), range&: opsWithIsolatedRegions, func: [&](Operation *o) {
368 if (failed(Result: verifyOpAndDominance(op&: *o)))
369 opFailedVerify.store(i: true, m: std::memory_order_relaxed);
370 });
371 if (opFailedVerify.load(m: std::memory_order_relaxed))
372 return failure();
373
374 OperationName opName = op.getName();
375 std::optional<RegisteredOperationName> registeredInfo =
376 opName.getRegisteredInfo();
377 // After the region ops are verified, run the verifiers that have additional
378 // region invariants need to veirfy.
379 if (registeredInfo && failed(Result: registeredInfo->verifyRegionInvariants(op: &op)))
380 return failure();
381
382 // If this is a registered operation, there is nothing left to do.
383 if (registeredInfo)
384 return success();
385
386 // Otherwise, verify that the parent dialect allows un-registered operations.
387 Dialect *dialect = opName.getDialect();
388 if (!dialect) {
389 if (!op.getContext()->allowsUnregisteredDialects()) {
390 return op.emitOpError()
391 << "created with unregistered dialect. If this is "
392 "intended, please call allowUnregisteredDialects() on the "
393 "MLIRContext, or use -allow-unregistered-dialect with "
394 "the MLIR opt tool used";
395 }
396 return success();
397 }
398
399 if (!dialect->allowsUnknownOperations()) {
400 return op.emitError(message: "unregistered operation '")
401 << op.getName() << "' found in dialect ('" << dialect->getNamespace()
402 << "') that does not allow unknown operations";
403 }
404
405 return success();
406}
407
408/// Verify the properties and dominance relationships of this operation,
409/// stopping region "recursion" at any "isolated from above operations".
410/// Such ops are collected separately and verified inside
411/// verifyBlockPostChildren.
412LogicalResult OperationVerifier::verifyOperation(Operation &op) {
413 SmallVector<WorkItemEntry> worklist{{&op, false}};
414 while (!worklist.empty()) {
415 WorkItemEntry &top = worklist.back();
416
417 auto visit = [](auto &&visitor, WorkItem w) {
418 if (auto *o = dyn_cast<Operation *>(Val&: w))
419 return visitor(o);
420 return visitor(cast<Block *>(Val&: w));
421 };
422
423 const bool isExit = top.getInt();
424 top.setInt(true);
425 auto item = top.getPointer();
426
427 // 2nd visit of this work item ("exit").
428 if (isExit) {
429 if (failed(
430 Result: visit([this](auto *workItem) { return verifyOnExit(*workItem); },
431 item)))
432 return failure();
433 worklist.pop_back();
434 continue;
435 }
436
437 // 1st visit of this work item ("entrance").
438 if (failed(Result: visit(
439 [this](auto *workItem) { return verifyOnEntrance(*workItem); },
440 item)))
441 return failure();
442
443 if (Block *currentBlock = dyn_cast<Block *>(Val&: item)) {
444 // Skip "isolated from above operations".
445 for (Operation &o : llvm::reverse(C&: *currentBlock)) {
446 if (o.getNumRegions() == 0 ||
447 !o.hasTrait<OpTrait::IsIsolatedFromAbove>())
448 worklist.emplace_back(Args: &o);
449 }
450 continue;
451 }
452
453 Operation &currentOp = *cast<Operation *>(Val&: item);
454 if (verifyRecursively)
455 for (Region &region : llvm::reverse(C: currentOp.getRegions()))
456 for (Block &block : llvm::reverse(C&: region))
457 worklist.emplace_back(Args: &block);
458 }
459 return success();
460}
461
462//===----------------------------------------------------------------------===//
463// Dominance Checking
464//===----------------------------------------------------------------------===//
465
466/// Emit an error when the specified operand of the specified operation is an
467/// invalid use because of dominance properties.
468static void diagnoseInvalidOperandDominance(Operation &op, unsigned operandNo) {
469 InFlightDiagnostic diag = op.emitError(message: "operand #")
470 << operandNo << " does not dominate this use";
471
472 Value operand = op.getOperand(idx: operandNo);
473
474 /// Attach a note to an in-flight diagnostic that provide more information
475 /// about where an op operand is defined.
476 if (auto *useOp = operand.getDefiningOp()) {
477 Diagnostic &note = diag.attachNote(noteLoc: useOp->getLoc());
478 note << "operand defined here";
479 Block *block1 = op.getBlock();
480 Block *block2 = useOp->getBlock();
481 Region *region1 = block1->getParent();
482 Region *region2 = block2->getParent();
483 if (block1 == block2)
484 note << " (op in the same block)";
485 else if (region1 == region2)
486 note << " (op in the same region)";
487 else if (region2->isProperAncestor(other: region1))
488 note << " (op in a parent region)";
489 else if (region1->isProperAncestor(other: region2))
490 note << " (op in a child region)";
491 else
492 note << " (op is neither in a parent nor in a child region)";
493 return;
494 }
495 // Block argument case.
496 Block *block1 = op.getBlock();
497 Block *block2 = llvm::cast<BlockArgument>(Val&: operand).getOwner();
498 Region *region1 = block1->getParent();
499 Region *region2 = block2->getParent();
500 Location loc = UnknownLoc::get(context: op.getContext());
501 if (block2->getParentOp())
502 loc = block2->getParentOp()->getLoc();
503 Diagnostic &note = diag.attachNote(noteLoc: loc);
504 if (!region2) {
505 note << " (block without parent)";
506 return;
507 }
508 if (block1 == block2)
509 llvm::report_fatal_error(reason: "Internal error in dominance verification");
510 unsigned index = block2->computeBlockNumber();
511 note << "operand defined as a block argument (block #" << index;
512 if (region1 == region2)
513 note << " in the same region)";
514 else if (region2->isProperAncestor(other: region1))
515 note << " in a parent region)";
516 else if (region1->isProperAncestor(other: region2))
517 note << " in a child region)";
518 else
519 note << " neither in a parent nor in a child region)";
520}
521
522/// Verify the dominance of each of the nested blocks within the given operation
523LogicalResult
524OperationVerifier::verifyDominanceOfContainedRegions(Operation &op,
525 DominanceInfo &domInfo) {
526 llvm::SmallVector<Operation *, 8> worklist{&op};
527 while (!worklist.empty()) {
528 auto *op = worklist.pop_back_val();
529 for (auto &region : op->getRegions())
530 for (auto &block : region.getBlocks()) {
531 // Dominance is only meaningful inside reachable blocks.
532 bool isReachable = domInfo.isReachableFromEntry(a: &block);
533 for (auto &op : block) {
534 if (isReachable) {
535 // Check that operands properly dominate this use.
536 for (const auto &operand : llvm::enumerate(First: op.getOperands())) {
537 if (domInfo.properlyDominates(a: operand.value(), b: &op))
538 continue;
539
540 diagnoseInvalidOperandDominance(op, operandNo: operand.index());
541 return failure();
542 }
543 }
544
545 // Recursively verify dominance within each operation in the block,
546 // even if the block itself is not reachable, or we are in a region
547 // which doesn't respect dominance.
548 if (verifyRecursively && op.getNumRegions() != 0) {
549 // If this operation is IsolatedFromAbove, then we'll handle it in
550 // the outer verification loop.
551 if (op.hasTrait<OpTrait::IsIsolatedFromAbove>())
552 continue;
553 worklist.push_back(Elt: &op);
554 }
555 }
556 }
557 }
558
559 return success();
560}
561
562//===----------------------------------------------------------------------===//
563// Entrypoint
564//===----------------------------------------------------------------------===//
565
566LogicalResult mlir::verify(Operation *op, bool verifyRecursively) {
567 OperationVerifier verifier(op->getContext(), verifyRecursively);
568 return verifier.verifyOpAndDominance(op&: *op);
569}
570