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

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