MLIR  15.0.0git
Verifier.cpp
Go to the documentation of this file.
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"
33 #include "mlir/IR/Threading.h"
34 #include "llvm/ADT/StringMap.h"
35 #include "llvm/Support/FormatVariadic.h"
36 #include "llvm/Support/PrettyStackTrace.h"
37 #include "llvm/Support/Regex.h"
38 #include <atomic>
39 
40 using namespace mlir;
41 
42 namespace {
43 /// This class encapsulates all the state used to verify an operation region.
44 class OperationVerifier {
45 public:
46  /// If `verifyRecursively` is true, then this will also recursively verify
47  /// nested operations.
48  explicit OperationVerifier(bool verifyRecursively)
49  : verifyRecursively(verifyRecursively) {}
50 
51  /// Verify the given operation.
52  LogicalResult verifyOpAndDominance(Operation &op);
53 
54 private:
55  /// Any ops that have regions and are marked as "isolated from above" will be
56  /// returned in the opsWithIsolatedRegions vector.
58  verifyBlock(Block &block,
59  SmallVectorImpl<Operation *> &opsWithIsolatedRegions);
60 
61  /// Verify the properties and dominance relationships of this operation.
62  LogicalResult verifyOperation(Operation &op);
63 
64  /// Verify the dominance property of regions contained within the given
65  /// Operation.
66  LogicalResult verifyDominanceOfContainedRegions(Operation &op,
67  DominanceInfo &domInfo);
68 
69  /// A flag indicating if this verifier should recursively verify nested
70  /// operations.
71  bool verifyRecursively;
72 };
73 } // namespace
74 
75 LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) {
76  // Verify the operation first, collecting any IsolatedFromAbove operations.
77  if (failed(verifyOperation(op)))
78  return failure();
79 
80  // Since everything looks structurally ok to this point, we do a dominance
81  // check for any nested regions. We do this as a second pass since malformed
82  // CFG's can cause dominator analysis construction to crash and we want the
83  // verifier to be resilient to malformed code.
84  if (op.getNumRegions() != 0) {
85  DominanceInfo domInfo;
86  if (failed(verifyDominanceOfContainedRegions(op, domInfo)))
87  return failure();
88  }
89 
90  return success();
91 }
92 
93 /// Returns true if this block may be valid without terminator. That is if:
94 /// - it does not have a parent region.
95 /// - Or the parent region have a single block and:
96 /// - This region does not have a parent op.
97 /// - Or the parent op is unregistered.
98 /// - Or the parent op has the NoTerminator trait.
99 static bool mayBeValidWithoutTerminator(Block *block) {
100  if (!block->getParent())
101  return true;
102  if (!llvm::hasSingleElement(*block->getParent()))
103  return false;
104  Operation *op = block->getParentOp();
105  return !op || op->mightHaveTrait<OpTrait::NoTerminator>();
106 }
107 
108 LogicalResult OperationVerifier::verifyBlock(
109  Block &block, SmallVectorImpl<Operation *> &opsWithIsolatedRegions) {
110 
111  for (auto arg : block.getArguments())
112  if (arg.getOwner() != &block)
113  return emitError(arg.getLoc(), "block argument not owned by block");
114 
115  // Verify that this block has a terminator.
116  if (block.empty()) {
117  if (mayBeValidWithoutTerminator(&block))
118  return success();
119  return emitError(block.getParent()->getLoc(),
120  "empty block: expect at least a terminator");
121  }
122 
123  // Check each operation, and make sure there are no branches out of the
124  // middle of this block.
125  for (Operation &op : block) {
126  // Only the last instructions is allowed to have successors.
127  if (op.getNumSuccessors() != 0 && &op != &block.back())
128  return op.emitError(
129  "operation with block successors must terminate its parent block");
130 
131  // If we aren't verifying recursievly, there is nothing left to check.
132  if (!verifyRecursively)
133  continue;
134 
135  // If this operation has regions and is IsolatedFromAbove, we defer
136  // checking. This allows us to parallelize verification better.
137  if (op.getNumRegions() != 0 &&
139  opsWithIsolatedRegions.push_back(&op);
140 
141  // Otherwise, check the operation inline.
142  } else if (failed(verifyOperation(op))) {
143  return failure();
144  }
145  }
146 
147  // Verify that this block is not branching to a block of a different
148  // region.
149  for (Block *successor : block.getSuccessors())
150  if (successor->getParent() != block.getParent())
151  return block.back().emitOpError(
152  "branching to block of a different region");
153 
154  // If this block doesn't have to have a terminator, don't require it.
155  if (mayBeValidWithoutTerminator(&block))
156  return success();
157 
158  Operation &terminator = block.back();
159  if (!terminator.mightHaveTrait<OpTrait::IsTerminator>())
160  return block.back().emitError("block with no terminator, has ")
161  << terminator;
162 
163  return success();
164 }
165 
166 /// Verify the properties and dominance relationships of this operation,
167 /// stopping region recursion at any "isolated from above operations". Any such
168 /// ops are returned in the opsWithIsolatedRegions vector.
169 LogicalResult OperationVerifier::verifyOperation(Operation &op) {
170  // Check that operands are non-nil and structurally ok.
171  for (auto operand : op.getOperands())
172  if (!operand)
173  return op.emitError("null operand found");
174 
175  /// Verify that all of the attributes are okay.
176  for (auto attr : op.getAttrs()) {
177  // Check for any optional dialect specific attributes.
178  if (auto *dialect = attr.getNameDialect())
179  if (failed(dialect->verifyOperationAttribute(&op, attr)))
180  return failure();
181  }
182 
183  // If we can get operation info for this, check the custom hook.
184  OperationName opName = op.getName();
185  Optional<RegisteredOperationName> registeredInfo = opName.getRegisteredInfo();
186  if (registeredInfo && failed(registeredInfo->verifyInvariants(&op)))
187  return failure();
188 
189  SmallVector<Operation *> opsWithIsolatedRegions;
190 
191  if (unsigned numRegions = op.getNumRegions()) {
192  auto kindInterface = dyn_cast<RegionKindInterface>(op);
193 
194  // Verify that all child regions are ok.
195  MutableArrayRef<Region> regions = op.getRegions();
196  for (unsigned i = 0; i < numRegions; ++i) {
197  Region &region = regions[i];
198  RegionKind kind =
199  kindInterface ? kindInterface.getRegionKind(i) : RegionKind::SSACFG;
200  // Check that Graph Regions only have a single basic block. This is
201  // similar to the code in SingleBlockImplicitTerminator, but doesn't
202  // require the trait to be specified. This arbitrary limitation is
203  // designed to limit the number of cases that have to be handled by
204  // transforms and conversions.
205  if (op.isRegistered() && kind == RegionKind::Graph) {
206  // Non-empty regions must contain a single basic block.
207  if (!region.empty() && !region.hasOneBlock())
208  return op.emitOpError("expects graph region #")
209  << i << " to have 0 or 1 blocks";
210  }
211 
212  if (region.empty())
213  continue;
214 
215  // Verify the first block has no predecessors.
216  Block *firstBB = &region.front();
217  if (!firstBB->hasNoPredecessors())
218  return emitError(op.getLoc(),
219  "entry block of region may not have predecessors");
220 
221  // Verify each of the blocks within the region if we are verifying
222  // recursively.
223  if (verifyRecursively) {
224  for (Block &block : region)
225  if (failed(verifyBlock(block, opsWithIsolatedRegions)))
226  return failure();
227  }
228  }
229  }
230 
231  // Verify the nested ops that are able to be verified in parallel.
233  op.getContext(), opsWithIsolatedRegions,
234  [&](Operation *op) { return verifyOpAndDominance(*op); })))
235  return failure();
236 
237  // After the region ops are verified, run the verifiers that have additional
238  // region invariants need to veirfy.
239  if (registeredInfo && failed(registeredInfo->verifyRegionInvariants(&op)))
240  return failure();
241 
242  // If this is a registered operation, there is nothing left to do.
243  if (registeredInfo)
244  return success();
245 
246  // Otherwise, verify that the parent dialect allows un-registered operations.
247  Dialect *dialect = opName.getDialect();
248  if (!dialect) {
249  if (!op.getContext()->allowsUnregisteredDialects()) {
250  return op.emitOpError()
251  << "created with unregistered dialect. If this is "
252  "intended, please call allowUnregisteredDialects() on the "
253  "MLIRContext, or use -allow-unregistered-dialect with "
254  "the MLIR opt tool used";
255  }
256  return success();
257  }
258 
259  if (!dialect->allowsUnknownOperations()) {
260  return op.emitError("unregistered operation '")
261  << op.getName() << "' found in dialect ('" << dialect->getNamespace()
262  << "') that does not allow unknown operations";
263  }
264 
265  return success();
266 }
267 
268 //===----------------------------------------------------------------------===//
269 // Dominance Checking
270 //===----------------------------------------------------------------------===//
271 
272 /// Emit an error when the specified operand of the specified operation is an
273 /// invalid use because of dominance properties.
274 static void diagnoseInvalidOperandDominance(Operation &op, unsigned operandNo) {
275  InFlightDiagnostic diag = op.emitError("operand #")
276  << operandNo << " does not dominate this use";
277 
278  Value operand = op.getOperand(operandNo);
279 
280  /// Attach a note to an in-flight diagnostic that provide more information
281  /// about where an op operand is defined.
282  if (auto *useOp = operand.getDefiningOp()) {
283  Diagnostic &note = diag.attachNote(useOp->getLoc());
284  note << "operand defined here";
285  Block *block1 = op.getBlock();
286  Block *block2 = useOp->getBlock();
287  Region *region1 = block1->getParent();
288  Region *region2 = block2->getParent();
289  if (block1 == block2)
290  note << " (op in the same block)";
291  else if (region1 == region2)
292  note << " (op in the same region)";
293  else if (region2->isProperAncestor(region1))
294  note << " (op in a parent region)";
295  else if (region1->isProperAncestor(region2))
296  note << " (op in a child region)";
297  else
298  note << " (op is neither in a parent nor in a child region)";
299  return;
300  }
301  // Block argument case.
302  Block *block1 = op.getBlock();
303  Block *block2 = operand.cast<BlockArgument>().getOwner();
304  Region *region1 = block1->getParent();
305  Region *region2 = block2->getParent();
306  Location loc = UnknownLoc::get(op.getContext());
307  if (block2->getParentOp())
308  loc = block2->getParentOp()->getLoc();
309  Diagnostic &note = diag.attachNote(loc);
310  if (!region2) {
311  note << " (block without parent)";
312  return;
313  }
314  if (block1 == block2)
315  llvm::report_fatal_error("Internal error in dominance verification");
316  int index = std::distance(region2->begin(), block2->getIterator());
317  note << "operand defined as a block argument (block #" << index;
318  if (region1 == region2)
319  note << " in the same region)";
320  else if (region2->isProperAncestor(region1))
321  note << " in a parent region)";
322  else if (region1->isProperAncestor(region2))
323  note << " in a child region)";
324  else
325  note << " neither in a parent nor in a child region)";
326 }
327 
328 /// Verify the dominance of each of the nested blocks within the given operation
330 OperationVerifier::verifyDominanceOfContainedRegions(Operation &op,
331  DominanceInfo &domInfo) {
332  for (Region &region : op.getRegions()) {
333  // Verify the dominance of each of the held operations.
334  for (Block &block : region) {
335  // Dominance is only meaningful inside reachable blocks.
336  bool isReachable = domInfo.isReachableFromEntry(&block);
337 
338  for (Operation &op : block) {
339  if (isReachable) {
340  // Check that operands properly dominate this use.
341  for (const auto &operand : llvm::enumerate(op.getOperands())) {
342  if (domInfo.properlyDominates(operand.value(), &op))
343  continue;
344 
345  diagnoseInvalidOperandDominance(op, operand.index());
346  return failure();
347  }
348  }
349 
350  // Recursively verify dominance within each operation in the block, even
351  // if the block itself is not reachable, or we are in a region which
352  // doesn't respect dominance.
353  if (verifyRecursively && op.getNumRegions() != 0) {
354  // If this operation is IsolatedFromAbove, then we'll handle it in the
355  // outer verification loop.
357  continue;
358 
359  if (failed(verifyDominanceOfContainedRegions(op, domInfo)))
360  return failure();
361  }
362  }
363  }
364  }
365  return success();
366 }
367 
368 //===----------------------------------------------------------------------===//
369 // Entrypoint
370 //===----------------------------------------------------------------------===//
371 
372 LogicalResult mlir::verify(Operation *op, bool verifyRecursively) {
373  OperationVerifier verifier(verifyRecursively);
374  return verifier.verifyOpAndDominance(*op);
375 }
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Definition: Dominance.h:130
TODO: Remove this file when SCCP and integer range analysis have been ported to the new framework...
This class contains a list of basic blocks and a link to the parent operation it is attached to...
Definition: Region.h:26
static std::string diag(llvm::Value &v)
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
RegionKind
The kinds of regions contained in an operation.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:478
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
operand_range getOperands()
Returns an iterator on the underlying Value&#39;s.
Definition: Operation.h:302
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:475
This class represents a diagnostic that is inflight and set to be reported.
Definition: Diagnostics.h:311
Block represents an ordered list of Operations.
Definition: Block.h:29
Block & front()
Definition: Region.h:65
ArrayRef< NamedAttribute > getAttrs()
Return all of the attributes on this operation.
Definition: Operation.h:363
Value getOperand(unsigned idx)
Definition: Operation.h:274
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
Definition: LogicalResult.h:72
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:534
A class for computing basic dominance information.
Definition: Dominance.h:117
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:697
unsigned getNumSuccessors()
Definition: Operation.h:504
bool isRegistered()
Returns true if this operation has a registered operation description, otherwise false.
Definition: Operation.h:67
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:151
Region * getParent() const
Provide a &#39;getParent&#39; method for ilist_node_with_parent methods.
Definition: Block.cpp:26
static bool mayBeValidWithoutTerminator(Block *block)
Returns true if this block may be valid without terminator.
Definition: Verifier.cpp:99
bool hasOneBlock()
Return true if this region has exactly one block.
Definition: Region.h:68
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:48
MLIRContext * getContext()
Return the context this operation is associated with.
Definition: Operation.h:154
LogicalResult failableParallelForEach(MLIRContext *context, IteratorT begin, IteratorT end, FuncT &&func)
Invoke the given function on the elements between [begin, end) asynchronously.
Definition: Threading.h:36
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
This class contains all of the information necessary to report a diagnostic to the DiagnosticEngine...
Definition: Diagnostics.h:157
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
bool empty()
Definition: Region.h:60
iterator begin()
Definition: Region.h:55
Diagnostic & attachNote(Optional< Location > noteLoc=llvm::None)
Attaches a note to this diagnostic.
Definition: Diagnostics.h:345
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:526
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:234
Dialects are groups of MLIR operations, types and attributes, as well as behavior associated with the...
Definition: Dialect.h:41
Optional< RegisteredOperationName > getRegisteredInfo() const
If this operation is registered, returns the registered information, None otherwise.
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:161
static void diagnoseInvalidOperandDominance(Operation &op, unsigned operandNo)
Emit an error when the specified operand of the specified operation is an invalid use because of domi...
Definition: Verifier.cpp:274
BlockArgListType getArguments()
Definition: Block.h:76
This class represents an argument of a Block.
Definition: Value.h:300
bool empty()
Definition: Block.h:139
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
This class indicates that the regions associated with this op don&#39;t have terminators.
Definition: OpDefinition.h:693
bool isReachableFromEntry(Block *a) const
Return true if the specified block is reachable from the entry block of its region.
Definition: Dominance.cpp:232
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
This class provides the API for ops that are known to be isolated from above.
StringRef getNamespace() const
Definition: Dialect.h:57
bool isProperAncestor(Region *other)
Return true if this region is a proper ancestor of the other region.
Definition: Region.cpp:50
bool hasNoPredecessors()
Return true if this block has no predecessors.
Definition: Block.h:230
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
bool allowsUnregisteredDialects()
Return true if we allow to create operation for unregistered dialects.
bool allowsUnknownOperations() const
Returns true if this dialect allows for unregistered operations, i.e.
Definition: Dialect.h:65
U cast() const
Definition: Value.h:108
Dialect * getDialect() const
Return the dialect this operation is registered to if the dialect is loaded in the context...
LogicalResult verify(Operation *op, bool verifyRecursively=true)
Perform (potentially expensive) checks of invariants, used to detect compiler bugs, on this operation and any nested operations.
Definition: Verifier.cpp:372
InFlightDiagnostic emitOpError(const Twine &message={})
Emit an error with the op name prefixed, like "&#39;dim&#39; op " which is convenient for verifiers...
Definition: Operation.cpp:518
SuccessorRange getSuccessors()
Definition: Block.h:255
Location getLoc()
Return a location for this region.
Definition: Region.cpp:31
OperationName getName()
The name of an operation is the key identifier for it.
Definition: Operation.h:57
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Definition: Operation.cpp:231