MLIR  14.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  /// Verify the given operation.
47  LogicalResult verifyOpAndDominance(Operation &op);
48 
49 private:
51  verifyBlock(Block &block,
52  SmallVectorImpl<Operation *> &opsWithIsolatedRegions);
53  /// Verify the properties and dominance relationships of this operation,
54  /// stopping region recursion at any "isolated from above operations". Any
55  /// such ops are returned in the opsWithIsolatedRegions vector.
57  verifyOperation(Operation &op,
58  SmallVectorImpl<Operation *> &opsWithIsolatedRegions);
59 
60  /// Verify the dominance property of regions contained within the given
61  /// Operation.
62  LogicalResult verifyDominanceOfContainedRegions(Operation &op,
63  DominanceInfo &domInfo);
64 };
65 } // namespace
66 
67 LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) {
68  SmallVector<Operation *> opsWithIsolatedRegions;
69 
70  // Verify the operation first, collecting any IsolatedFromAbove operations.
71  if (failed(verifyOperation(op, opsWithIsolatedRegions)))
72  return failure();
73 
74  // Since everything looks structurally ok to this point, we do a dominance
75  // check for any nested regions. We do this as a second pass since malformed
76  // CFG's can cause dominator analysis construction to crash and we want the
77  // verifier to be resilient to malformed code.
78  if (op.getNumRegions() != 0) {
79  DominanceInfo domInfo;
80  if (failed(verifyDominanceOfContainedRegions(op, domInfo)))
81  return failure();
82  }
83 
84  // Check the dominance properties and invariants of any operations in the
85  // regions contained by the 'opsWithIsolatedRegions' operations.
87  op.getContext(), opsWithIsolatedRegions,
88  [&](Operation *op) { return verifyOpAndDominance(*op); });
89 }
90 
91 /// Returns true if this block may be valid without terminator. That is if:
92 /// - it does not have a parent region.
93 /// - Or the parent region have a single block and:
94 /// - This region does not have a parent op.
95 /// - Or the parent op is unregistered.
96 /// - Or the parent op has the NoTerminator trait.
97 static bool mayBeValidWithoutTerminator(Block *block) {
98  if (!block->getParent())
99  return true;
100  if (!llvm::hasSingleElement(*block->getParent()))
101  return false;
102  Operation *op = block->getParentOp();
103  return !op || op->mightHaveTrait<OpTrait::NoTerminator>();
104 }
105 
106 LogicalResult OperationVerifier::verifyBlock(
107  Block &block, SmallVectorImpl<Operation *> &opsWithIsolatedRegions) {
108 
109  for (auto arg : block.getArguments())
110  if (arg.getOwner() != &block)
111  return emitError(arg.getLoc(), "block argument not owned by block");
112 
113  // Verify that this block has a terminator.
114  if (block.empty()) {
115  if (mayBeValidWithoutTerminator(&block))
116  return success();
117  return emitError(block.getParent()->getLoc(),
118  "empty block: expect at least a terminator");
119  }
120 
121  // Check each operation, and make sure there are no branches out of the
122  // middle of this block.
123  for (auto &op : block) {
124  // Only the last instructions is allowed to have successors.
125  if (op.getNumSuccessors() != 0 && &op != &block.back())
126  return op.emitError(
127  "operation with block successors must terminate its parent block");
128 
129  // If this operation has regions and is IsolatedFromAbove, we defer
130  // checking. This allows us to parallelize verification better.
131  if (op.getNumRegions() != 0 &&
133  opsWithIsolatedRegions.push_back(&op);
134  } else {
135  // Otherwise, check the operation inline.
136  if (failed(verifyOperation(op, opsWithIsolatedRegions)))
137  return failure();
138  }
139  }
140 
141  // Verify that this block is not branching to a block of a different
142  // region.
143  for (Block *successor : block.getSuccessors())
144  if (successor->getParent() != block.getParent())
145  return block.back().emitOpError(
146  "branching to block of a different region");
147 
148  // If this block doesn't have to have a terminator, don't require it.
149  if (mayBeValidWithoutTerminator(&block))
150  return success();
151 
152  Operation &terminator = block.back();
153  if (!terminator.mightHaveTrait<OpTrait::IsTerminator>())
154  return block.back().emitError("block with no terminator, has ")
155  << terminator;
156 
157  return success();
158 }
159 
160 /// Verify the properties and dominance relationships of this operation,
161 /// stopping region recursion at any "isolated from above operations". Any such
162 /// ops are returned in the opsWithIsolatedRegions vector.
163 LogicalResult OperationVerifier::verifyOperation(
164  Operation &op, SmallVectorImpl<Operation *> &opsWithIsolatedRegions) {
165  // Check that operands are non-nil and structurally ok.
166  for (auto operand : op.getOperands())
167  if (!operand)
168  return op.emitError("null operand found");
169 
170  /// Verify that all of the attributes are okay.
171  for (auto attr : op.getAttrs()) {
172  // Check for any optional dialect specific attributes.
173  if (auto *dialect = attr.getNameDialect())
174  if (failed(dialect->verifyOperationAttribute(&op, attr)))
175  return failure();
176  }
177 
178  // If we can get operation info for this, check the custom hook.
179  OperationName opName = op.getName();
180  Optional<RegisteredOperationName> registeredInfo = opName.getRegisteredInfo();
181  if (registeredInfo && failed(registeredInfo->verifyInvariants(&op)))
182  return failure();
183 
184  if (unsigned numRegions = op.getNumRegions()) {
185  auto kindInterface = dyn_cast<RegionKindInterface>(op);
186 
187  // Verify that all child regions are ok.
188  for (unsigned i = 0; i < numRegions; ++i) {
189  Region &region = op.getRegion(i);
190  RegionKind kind =
191  kindInterface ? kindInterface.getRegionKind(i) : RegionKind::SSACFG;
192  // Check that Graph Regions only have a single basic block. This is
193  // similar to the code in SingleBlockImplicitTerminator, but doesn't
194  // require the trait to be specified. This arbitrary limitation is
195  // designed to limit the number of cases that have to be handled by
196  // transforms and conversions.
197  if (op.isRegistered() && kind == RegionKind::Graph) {
198  // Non-empty regions must contain a single basic block.
199  if (!region.empty() && !region.hasOneBlock())
200  return op.emitOpError("expects graph region #")
201  << i << " to have 0 or 1 blocks";
202  }
203 
204  if (region.empty())
205  continue;
206 
207  // Verify the first block has no predecessors.
208  Block *firstBB = &region.front();
209  if (!firstBB->hasNoPredecessors())
210  return emitError(op.getLoc(),
211  "entry block of region may not have predecessors");
212 
213  // Verify each of the blocks within the region.
214  for (Block &block : region)
215  if (failed(verifyBlock(block, opsWithIsolatedRegions)))
216  return failure();
217  }
218  }
219 
220  // If this is a registered operation, there is nothing left to do.
221  if (registeredInfo)
222  return success();
223 
224  // Otherwise, verify that the parent dialect allows un-registered operations.
225  Dialect *dialect = opName.getDialect();
226  if (!dialect) {
227  if (!op.getContext()->allowsUnregisteredDialects()) {
228  return op.emitOpError()
229  << "created with unregistered dialect. If this is "
230  "intended, please call allowUnregisteredDialects() on the "
231  "MLIRContext, or use -allow-unregistered-dialect with "
232  "the MLIR opt tool used";
233  }
234  return success();
235  }
236 
237  if (!dialect->allowsUnknownOperations()) {
238  return op.emitError("unregistered operation '")
239  << op.getName() << "' found in dialect ('" << dialect->getNamespace()
240  << "') that does not allow unknown operations";
241  }
242 
243  return success();
244 }
245 
246 //===----------------------------------------------------------------------===//
247 // Dominance Checking
248 //===----------------------------------------------------------------------===//
249 
250 /// Emit an error when the specified operand of the specified operation is an
251 /// invalid use because of dominance properties.
252 static void diagnoseInvalidOperandDominance(Operation &op, unsigned operandNo) {
253  InFlightDiagnostic diag = op.emitError("operand #")
254  << operandNo << " does not dominate this use";
255 
256  Value operand = op.getOperand(operandNo);
257 
258  /// Attach a note to an in-flight diagnostic that provide more information
259  /// about where an op operand is defined.
260  if (auto *useOp = operand.getDefiningOp()) {
261  Diagnostic &note = diag.attachNote(useOp->getLoc());
262  note << "operand defined here";
263  Block *block1 = op.getBlock();
264  Block *block2 = useOp->getBlock();
265  Region *region1 = block1->getParent();
266  Region *region2 = block2->getParent();
267  if (block1 == block2)
268  note << " (op in the same block)";
269  else if (region1 == region2)
270  note << " (op in the same region)";
271  else if (region2->isProperAncestor(region1))
272  note << " (op in a parent region)";
273  else if (region1->isProperAncestor(region2))
274  note << " (op in a child region)";
275  else
276  note << " (op is neither in a parent nor in a child region)";
277  return;
278  }
279  // Block argument case.
280  Block *block1 = op.getBlock();
281  Block *block2 = operand.cast<BlockArgument>().getOwner();
282  Region *region1 = block1->getParent();
283  Region *region2 = block2->getParent();
284  Location loc = UnknownLoc::get(op.getContext());
285  if (block2->getParentOp())
286  loc = block2->getParentOp()->getLoc();
287  Diagnostic &note = diag.attachNote(loc);
288  if (!region2) {
289  note << " (block without parent)";
290  return;
291  }
292  if (block1 == block2)
293  llvm::report_fatal_error("Internal error in dominance verification");
294  int index = std::distance(region2->begin(), block2->getIterator());
295  note << "operand defined as a block argument (block #" << index;
296  if (region1 == region2)
297  note << " in the same region)";
298  else if (region2->isProperAncestor(region1))
299  note << " in a parent region)";
300  else if (region1->isProperAncestor(region2))
301  note << " in a child region)";
302  else
303  note << " neither in a parent nor in a child region)";
304 }
305 
306 /// Verify the dominance of each of the nested blocks within the given operation
308 OperationVerifier::verifyDominanceOfContainedRegions(Operation &op,
309  DominanceInfo &domInfo) {
310  for (Region &region : op.getRegions()) {
311  // Verify the dominance of each of the held operations.
312  for (Block &block : region) {
313  // Dominance is only meaningful inside reachable blocks.
314  bool isReachable = domInfo.isReachableFromEntry(&block);
315 
316  for (Operation &op : block) {
317  if (isReachable) {
318  // Check that operands properly dominate this use.
319  for (const auto &operand : llvm::enumerate(op.getOperands())) {
320  if (domInfo.properlyDominates(operand.value(), &op))
321  continue;
322 
323  diagnoseInvalidOperandDominance(op, operand.index());
324  return failure();
325  }
326  }
327 
328  // Recursively verify dominance within each operation in the
329  // block, even if the block itself is not reachable, or we are in
330  // a region which doesn't respect dominance.
331  if (op.getNumRegions() != 0) {
332  // If this operation is IsolatedFromAbove, then we'll handle it in the
333  // outer verification loop.
335  continue;
336 
337  if (failed(verifyDominanceOfContainedRegions(op, domInfo)))
338  return failure();
339  }
340  }
341  }
342  }
343  return success();
344 }
345 
346 //===----------------------------------------------------------------------===//
347 // Entrypoint
348 //===----------------------------------------------------------------------===//
349 
350 /// Perform (potentially expensive) checks of invariants, used to detect
351 /// compiler bugs. On error, this reports the error through the MLIRContext and
352 /// returns failure.
354  return OperationVerifier().verifyOpAndDominance(*op);
355 }
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
Include the generated interface declarations.
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:423
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:247
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:420
This class represents a diagnostic that is inflight and set to be reported.
Definition: Diagnostics.h:301
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:308
Value getOperand(unsigned idx)
Definition: Operation.h:219
LogicalResult verify(Operation *op)
Perform (potentially expensive) checks of invariants, used to detect compiler bugs, on this operation and any nested operations.
Definition: Verifier.cpp:353
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:477
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:676
unsigned getNumSuccessors()
Definition: Operation.h:449
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:96
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:97
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:99
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:335
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:470
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:206
Dialects are groups of MLIR operations, types and attributes, as well as behavior associated with the...
Definition: Dialect.h:42
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:106
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:252
BlockArgListType getArguments()
Definition: Block.h:76
This class represents an argument of a Block.
Definition: Value.h:298
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:84
This class indicates that the regions associated with this op don&#39;t have terminators.
Definition: OpDefinition.h:672
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:58
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:66
U cast() const
Definition: Value.h:107
Dialect * getDialect() const
Return the dialect this operation is registered to if the dialect is loaded in the context...
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
Region & getRegion(unsigned index)
Returns the region held by this operation at position &#39;index&#39;.
Definition: Operation.h:429