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/Dialect.h"
30#include "mlir/IR/Dominance.h"
31#include "mlir/IR/Operation.h"
32#include "mlir/IR/RegionKindInterface.h"
33#include "mlir/IR/Threading.h"
34#include "llvm/ADT/DenseMapInfoVariant.h"
35#include "llvm/ADT/StringMap.h"
36#include "llvm/Support/FormatVariadic.h"
37#include "llvm/Support/PrettyStackTrace.h"
38#include "llvm/Support/Regex.h"
39#include <atomic>
40#include <optional>
41
42using namespace mlir;
43
44namespace {
45/// This class encapsulates all the state used to verify an operation region.
46class OperationVerifier {
47public:
48 /// If `verifyRecursively` is true, then this will also recursively verify
49 /// nested operations.
50 explicit OperationVerifier(bool verifyRecursively)
51 : verifyRecursively(verifyRecursively) {}
52
53 /// Verify the given operation.
54 LogicalResult verifyOpAndDominance(Operation &op);
55
56private:
57 using WorkItem = llvm::PointerUnion<Operation *, Block *>;
58
59 /// This verifier uses a DFS of the tree of operations/blocks. The method
60 /// verifyOnEntrance is invoked when we visit a node for the first time, i.e.
61 /// before visiting its children. The method verifyOnExit is invoked
62 /// upon exit from the subtree, i.e. when we visit a node for the second time.
63 LogicalResult verifyOnEntrance(Block &block);
64 LogicalResult verifyOnEntrance(Operation &op);
65
66 LogicalResult verifyOnExit(Block &block);
67 LogicalResult verifyOnExit(Operation &op);
68
69 /// Verify the properties and dominance relationships of this operation.
70 LogicalResult verifyOperation(Operation &op);
71
72 /// Verify the dominance property of regions contained within the given
73 /// Operation.
74 LogicalResult verifyDominanceOfContainedRegions(Operation &op,
75 DominanceInfo &domInfo);
76
77 /// A flag indicating if this verifier should recursively verify nested
78 /// operations.
79 bool verifyRecursively;
80};
81} // namespace
82
83LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) {
84 // Verify the operation first, collecting any IsolatedFromAbove operations.
85 if (failed(result: verifyOperation(op)))
86 return failure();
87
88 // Since everything looks structurally ok to this point, we do a dominance
89 // check for any nested regions. We do this as a second pass since malformed
90 // CFG's can cause dominator analysis construction to crash and we want the
91 // verifier to be resilient to malformed code.
92 if (op.getNumRegions() != 0) {
93 DominanceInfo domInfo;
94 if (failed(result: verifyDominanceOfContainedRegions(op, domInfo)))
95 return failure();
96 }
97
98 return success();
99}
100
101/// Returns true if this block may be valid without terminator. That is if:
102/// - it does not have a parent region.
103/// - Or the parent region have a single block and:
104/// - This region does not have a parent op.
105/// - Or the parent op is unregistered.
106/// - Or the parent op has the NoTerminator trait.
107static bool mayBeValidWithoutTerminator(Block *block) {
108 if (!block->getParent())
109 return true;
110 if (!llvm::hasSingleElement(C&: *block->getParent()))
111 return false;
112 Operation *op = block->getParentOp();
113 return !op || op->mightHaveTrait<OpTrait::NoTerminator>();
114}
115
116LogicalResult OperationVerifier::verifyOnEntrance(Block &block) {
117 for (auto arg : block.getArguments())
118 if (arg.getOwner() != &block)
119 return emitError(loc: arg.getLoc(), message: "block argument not owned by block");
120
121 // Verify that this block has a terminator.
122 if (block.empty()) {
123 if (mayBeValidWithoutTerminator(block: &block))
124 return success();
125 return emitError(loc: block.getParent()->getLoc(),
126 message: "empty block: expect at least a terminator");
127 }
128
129 // Check each operation, and make sure there are no branches out of the
130 // middle of this block.
131 for (Operation &op : block) {
132 // Only the last instructions is allowed to have successors.
133 if (op.getNumSuccessors() != 0 && &op != &block.back())
134 return op.emitError(
135 message: "operation with block successors must terminate its parent block");
136 }
137
138 return success();
139}
140
141LogicalResult OperationVerifier::verifyOnExit(Block &block) {
142 // Verify that this block is not branching to a block of a different
143 // region.
144 for (Block *successor : block.getSuccessors())
145 if (successor->getParent() != block.getParent())
146 return block.back().emitOpError(
147 message: "branching to block of a different region");
148
149 // If this block doesn't have to have a terminator, don't require it.
150 if (mayBeValidWithoutTerminator(block: &block))
151 return success();
152
153 Operation &terminator = block.back();
154 if (!terminator.mightHaveTrait<OpTrait::IsTerminator>())
155 return block.back().emitError(message: "block with no terminator, has ")
156 << terminator;
157
158 return success();
159}
160
161LogicalResult OperationVerifier::verifyOnEntrance(Operation &op) {
162 // Check that operands are non-nil and structurally ok.
163 for (auto operand : op.getOperands())
164 if (!operand)
165 return op.emitError(message: "null operand found");
166
167 /// Verify that all of the attributes are okay.
168 for (auto attr : op.getDiscardableAttrDictionary()) {
169 // Check for any optional dialect specific attributes.
170 if (auto *dialect = attr.getNameDialect())
171 if (failed(dialect->verifyOperationAttribute(&op, attr)))
172 return failure();
173 }
174
175 // If we can get operation info for this, check the custom hook.
176 OperationName opName = op.getName();
177 std::optional<RegisteredOperationName> registeredInfo =
178 opName.getRegisteredInfo();
179 if (registeredInfo && failed(result: registeredInfo->verifyInvariants(op: &op)))
180 return failure();
181
182 unsigned numRegions = op.getNumRegions();
183 if (!numRegions)
184 return success();
185 auto kindInterface = dyn_cast<RegionKindInterface>(&op);
186 SmallVector<Operation *> opsWithIsolatedRegions;
187 // Verify that all child regions are ok.
188 MutableArrayRef<Region> regions = op.getRegions();
189 for (unsigned i = 0; i < numRegions; ++i) {
190 Region &region = regions[i];
191 RegionKind kind =
192 kindInterface ? kindInterface.getRegionKind(i) : RegionKind::SSACFG;
193 // Check that Graph Regions only have a single basic block. This is
194 // similar to the code in SingleBlockImplicitTerminator, but doesn't
195 // require the trait to be specified. This arbitrary limitation is
196 // designed to limit the number of cases that have to be handled by
197 // transforms and conversions.
198 if (op.isRegistered() && kind == RegionKind::Graph) {
199 // Non-empty regions must contain a single basic block.
200 if (!region.empty() && !region.hasOneBlock())
201 return op.emitOpError(message: "expects graph region #")
202 << i << " to have 0 or 1 blocks";
203 }
204
205 if (region.empty())
206 continue;
207
208 // Verify the first block has no predecessors.
209 Block *firstBB = &region.front();
210 if (!firstBB->hasNoPredecessors())
211 return emitError(loc: op.getLoc(),
212 message: "entry block of region may not have predecessors");
213 }
214 return success();
215}
216
217LogicalResult OperationVerifier::verifyOnExit(Operation &op) {
218 SmallVector<Operation *> opsWithIsolatedRegions;
219 if (verifyRecursively) {
220 for (Region &region : op.getRegions())
221 for (Block &block : region)
222 for (Operation &o : block)
223 if (o.getNumRegions() != 0 &&
224 o.hasTrait<OpTrait::IsIsolatedFromAbove>())
225 opsWithIsolatedRegions.push_back(Elt: &o);
226 }
227 if (failed(result: failableParallelForEach(
228 context: op.getContext(), range&: opsWithIsolatedRegions,
229 func: [&](Operation *o) { return verifyOpAndDominance(op&: *o); })))
230 return failure();
231 OperationName opName = op.getName();
232 std::optional<RegisteredOperationName> registeredInfo =
233 opName.getRegisteredInfo();
234 // After the region ops are verified, run the verifiers that have additional
235 // region invariants need to veirfy.
236 if (registeredInfo && failed(result: registeredInfo->verifyRegionInvariants(op: &op)))
237 return failure();
238
239 // If this is a registered operation, there is nothing left to do.
240 if (registeredInfo)
241 return success();
242
243 // Otherwise, verify that the parent dialect allows un-registered operations.
244 Dialect *dialect = opName.getDialect();
245 if (!dialect) {
246 if (!op.getContext()->allowsUnregisteredDialects()) {
247 return op.emitOpError()
248 << "created with unregistered dialect. If this is "
249 "intended, please call allowUnregisteredDialects() on the "
250 "MLIRContext, or use -allow-unregistered-dialect with "
251 "the MLIR opt tool used";
252 }
253 return success();
254 }
255
256 if (!dialect->allowsUnknownOperations()) {
257 return op.emitError(message: "unregistered operation '")
258 << op.getName() << "' found in dialect ('" << dialect->getNamespace()
259 << "') that does not allow unknown operations";
260 }
261
262 return success();
263}
264
265/// Verify the properties and dominance relationships of this operation,
266/// stopping region "recursion" at any "isolated from above operations".
267/// Such ops are collected separately and verified inside
268/// verifyBlockPostChildren.
269LogicalResult OperationVerifier::verifyOperation(Operation &op) {
270 SmallVector<WorkItem> worklist{{&op}};
271 DenseSet<WorkItem> seen;
272 while (!worklist.empty()) {
273 WorkItem top = worklist.back();
274
275 auto visit = [](auto &&visitor, WorkItem w) {
276 if (w.is<Operation *>())
277 return visitor(w.get<Operation *>());
278 return visitor(w.get<Block *>());
279 };
280
281 const bool isExit = !seen.insert(V: top).second;
282 // 2nd visit of this work item ("exit").
283 if (isExit) {
284 worklist.pop_back();
285 if (failed(result: visit(
286 [this](auto *workItem) { return verifyOnExit(*workItem); }, top)))
287 return failure();
288 continue;
289 }
290
291 // 1st visit of this work item ("entrance").
292 if (failed(result: visit(
293 [this](auto *workItem) { return verifyOnEntrance(*workItem); },
294 top)))
295 return failure();
296
297 if (top.is<Block *>()) {
298 Block &currentBlock = *top.get<Block *>();
299 // Skip "isolated from above operations".
300 for (Operation &o : llvm::reverse(C&: currentBlock)) {
301 if (o.getNumRegions() == 0 ||
302 !o.hasTrait<OpTrait::IsIsolatedFromAbove>())
303 worklist.emplace_back(Args: &o);
304 }
305 continue;
306 }
307
308 Operation &currentOp = *top.get<Operation *>();
309 if (verifyRecursively)
310 for (Region &region : llvm::reverse(C: currentOp.getRegions()))
311 for (Block &block : llvm::reverse(C&: region))
312 worklist.emplace_back(Args: &block);
313 }
314 return success();
315}
316
317//===----------------------------------------------------------------------===//
318// Dominance Checking
319//===----------------------------------------------------------------------===//
320
321/// Emit an error when the specified operand of the specified operation is an
322/// invalid use because of dominance properties.
323static void diagnoseInvalidOperandDominance(Operation &op, unsigned operandNo) {
324 InFlightDiagnostic diag = op.emitError(message: "operand #")
325 << operandNo << " does not dominate this use";
326
327 Value operand = op.getOperand(idx: operandNo);
328
329 /// Attach a note to an in-flight diagnostic that provide more information
330 /// about where an op operand is defined.
331 if (auto *useOp = operand.getDefiningOp()) {
332 Diagnostic &note = diag.attachNote(noteLoc: useOp->getLoc());
333 note << "operand defined here";
334 Block *block1 = op.getBlock();
335 Block *block2 = useOp->getBlock();
336 Region *region1 = block1->getParent();
337 Region *region2 = block2->getParent();
338 if (block1 == block2)
339 note << " (op in the same block)";
340 else if (region1 == region2)
341 note << " (op in the same region)";
342 else if (region2->isProperAncestor(other: region1))
343 note << " (op in a parent region)";
344 else if (region1->isProperAncestor(other: region2))
345 note << " (op in a child region)";
346 else
347 note << " (op is neither in a parent nor in a child region)";
348 return;
349 }
350 // Block argument case.
351 Block *block1 = op.getBlock();
352 Block *block2 = llvm::cast<BlockArgument>(Val&: operand).getOwner();
353 Region *region1 = block1->getParent();
354 Region *region2 = block2->getParent();
355 Location loc = UnknownLoc::get(op.getContext());
356 if (block2->getParentOp())
357 loc = block2->getParentOp()->getLoc();
358 Diagnostic &note = diag.attachNote(noteLoc: loc);
359 if (!region2) {
360 note << " (block without parent)";
361 return;
362 }
363 if (block1 == block2)
364 llvm::report_fatal_error(reason: "Internal error in dominance verification");
365 int index = std::distance(first: region2->begin(), last: block2->getIterator());
366 note << "operand defined as a block argument (block #" << index;
367 if (region1 == region2)
368 note << " in the same region)";
369 else if (region2->isProperAncestor(other: region1))
370 note << " in a parent region)";
371 else if (region1->isProperAncestor(other: region2))
372 note << " in a child region)";
373 else
374 note << " neither in a parent nor in a child region)";
375}
376
377/// Verify the dominance of each of the nested blocks within the given operation
378LogicalResult
379OperationVerifier::verifyDominanceOfContainedRegions(Operation &op,
380 DominanceInfo &domInfo) {
381 llvm::SmallVector<Operation *, 8> worklist{&op};
382 while (!worklist.empty()) {
383 auto *op = worklist.pop_back_val();
384 for (auto &region : op->getRegions())
385 for (auto &block : region.getBlocks()) {
386 // Dominance is only meaningful inside reachable blocks.
387 bool isReachable = domInfo.isReachableFromEntry(a: &block);
388 for (auto &op : block) {
389 if (isReachable) {
390 // Check that operands properly dominate this use.
391 for (const auto &operand : llvm::enumerate(First: op.getOperands())) {
392 if (domInfo.properlyDominates(a: operand.value(), b: &op))
393 continue;
394
395 diagnoseInvalidOperandDominance(op, operandNo: operand.index());
396 return failure();
397 }
398 }
399
400 // Recursively verify dominance within each operation in the block,
401 // even if the block itself is not reachable, or we are in a region
402 // which doesn't respect dominance.
403 if (verifyRecursively && op.getNumRegions() != 0) {
404 // If this operation is IsolatedFromAbove, then we'll handle it in
405 // the outer verification loop.
406 if (op.hasTrait<OpTrait::IsIsolatedFromAbove>())
407 continue;
408 worklist.push_back(Elt: &op);
409 }
410 }
411 }
412 }
413
414 return success();
415}
416
417//===----------------------------------------------------------------------===//
418// Entrypoint
419//===----------------------------------------------------------------------===//
420
421LogicalResult mlir::verify(Operation *op, bool verifyRecursively) {
422 OperationVerifier verifier(verifyRecursively);
423 return verifier.verifyOpAndDominance(op&: *op);
424}
425

source code of mlir/lib/IR/Verifier.cpp