427 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the verify() methods on the various IR types, performing10// (potentially expensive) checks on the holistic structure of the code. This11// can be used for detecting bugs in compiler transformations and hand written12// .mlir files.13//14// The checks in this file are only for things that can occur as part of IR15// transformations: e.g. violation of dominance information, malformed operation16// attributes, etc. MLIR supports transformations moving IR through locally17// invalid states (e.g. unlinking an operation from a block before re-inserting18// it in a new place), but each transformation must complete with the IR in a19// 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 those23// 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 verify44 /// 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 method56 /// verifyOnEntrance is invoked when we visit a node for the first time, i.e.57 /// before visiting its children. The method verifyOnExit is invoked58 /// 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 given69 /// Operation.70 LogicalResult verifyDominanceOfContainedRegions(Operation &op,71 DominanceInfo &domInfo);72 73 /// A flag indicating if this verifier should recursively verify nested74 /// operations.75 bool verifyRecursively;76};77} // namespace78 79LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) {80 // Verify the operation first, collecting any IsolatedFromAbove operations.81 if (failed(verifyOperation(op)))82 return failure();83 84 // Since everything looks structurally ok to this point, we do a dominance85 // check for any nested regions. We do this as a second pass since malformed86 // CFG's can cause dominator analysis construction to crash and we want the87 // verifier to be resilient to malformed code.88 if (op.getNumRegions() != 0) {89 DominanceInfo domInfo;90 if (failed(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(*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(arg.getLoc(), "block argument not owned by block");116 117 // Verify that this block has a terminator.118 if (block.empty()) {119 if (mayBeValidWithoutTerminator(&block))120 return success();121 return emitError(block.getParent()->getLoc(),122 "empty block: expect at least a terminator");123 }124 125 // Check each operation, and make sure there are no branches out of the126 // 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 "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 different139 // region.140 for (Block *successor : block.getSuccessors())141 if (successor->getParent() != block.getParent())142 return block.back().emitOpError(143 "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))147 return success();148 149 Operation &terminator = block.back();150 if (!terminator.mightHaveTrait<OpTrait::IsTerminator>())151 return block.back().emitError("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("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(registeredInfo->verifyInvariants(&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 ®ion = regions[i];186 RegionKind kind =187 kindInterface ? kindInterface.getRegionKind(i) : RegionKind::SSACFG;188 // Check that Graph Regions only have a single basic block. This is189 // similar to the code in SingleBlockImplicitTerminator, but doesn't190 // require the trait to be specified. This arbitrary limitation is191 // designed to limit the number of cases that have to be handled by192 // 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("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 = ®ion.front();205 if (!firstBB->hasNoPredecessors())206 return emitError(op.getLoc(),207 "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 ®ion : 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(&o);221 }222 223 std::atomic<bool> opFailedVerify = false;224 parallelForEach(op.getContext(), opsWithIsolatedRegions, [&](Operation *o) {225 if (failed(verifyOpAndDominance(*o)))226 opFailedVerify.store(true, std::memory_order_relaxed);227 });228 if (opFailedVerify.load(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 additional235 // region invariants need to veirfy.236 if (registeredInfo && failed(registeredInfo->verifyRegionInvariants(&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("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 inside268/// 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 *>(w))276 return visitor(o);277 return visitor(cast<Block *>(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 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(visit(296 [this](auto *workItem) { return verifyOnEntrance(*workItem); },297 item)))298 return failure();299 300 if (Block *currentBlock = dyn_cast<Block *>(item)) {301 // Skip "isolated from above operations".302 for (Operation &o : llvm::reverse(*currentBlock)) {303 if (o.getNumRegions() == 0 ||304 !o.hasTrait<OpTrait::IsIsolatedFromAbove>())305 worklist.emplace_back(&o);306 }307 continue;308 }309 310 Operation ¤tOp = *cast<Operation *>(item);311 if (verifyRecursively)312 for (Region ®ion : llvm::reverse(currentOp.getRegions()))313 for (Block &block : llvm::reverse(region))314 worklist.emplace_back(&block);315 }316 return success();317}318 319//===----------------------------------------------------------------------===//320// Dominance Checking321//===----------------------------------------------------------------------===//322 323/// Emit an error when the specified operand of the specified operation is an324/// invalid use because of dominance properties.325static void diagnoseInvalidOperandDominance(Operation &op, unsigned operandNo) {326 InFlightDiagnostic diag = op.emitError("operand #")327 << operandNo << " does not dominate this use";328 329 Value operand = op.getOperand(operandNo);330 331 /// Attach a note to an in-flight diagnostic that provide more information332 /// about where an op operand is defined.333 if (auto *useOp = operand.getDefiningOp()) {334 Diagnostic ¬e = diag.attachNote(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(region1))345 note << " (op in a parent region)";346 else if (region1->isProperAncestor(region2))347 note << " (op in a child region)";348 else349 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>(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 ¬e = diag.attachNote(loc);361 if (!region2) {362 note << " (block without parent)";363 return;364 }365 if (block1 == block2)366 llvm::report_fatal_error("Internal error in dominance verification");367 int index = std::distance(region2->begin(), 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(region1))372 note << " in a parent region)";373 else if (region1->isProperAncestor(region2))374 note << " in a child region)";375 else376 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 operation380LogicalResult381OperationVerifier::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 ®ion : op->getRegions())387 for (auto &block : region.getBlocks()) {388 // Dominance is only meaningful inside reachable blocks.389 bool isReachable = domInfo.isReachableFromEntry(&block);390 for (auto &op : block) {391 if (isReachable) {392 // Check that operands properly dominate this use.393 for (const auto &operand : llvm::enumerate(op.getOperands())) {394 if (domInfo.properlyDominates(operand.value(), &op))395 continue;396 397 diagnoseInvalidOperandDominance(op, 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 region404 // which doesn't respect dominance.405 if (verifyRecursively && op.getNumRegions() != 0) {406 // If this operation is IsolatedFromAbove, then we'll handle it in407 // the outer verification loop.408 if (op.hasTrait<OpTrait::IsIsolatedFromAbove>())409 continue;410 worklist.push_back(&op);411 }412 }413 }414 }415 416 return success();417}418 419//===----------------------------------------------------------------------===//420// Entrypoint421//===----------------------------------------------------------------------===//422 423LogicalResult mlir::verify(Operation *op, bool verifyRecursively) {424 OperationVerifier verifier(verifyRecursively);425 return verifier.verifyOpAndDominance(*op);426}427