diff --git a/mlir/lib/IR/Verifier.cpp b/mlir/lib/IR/Verifier.cpp --- a/mlir/lib/IR/Verifier.cpp +++ b/mlir/lib/IR/Verifier.cpp @@ -32,9 +32,9 @@ #include "mlir/IR/RegionKindInterface.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/Parallel.h" #include "llvm/Support/PrettyStackTrace.h" #include "llvm/Support/Regex.h" - #include using namespace mlir; @@ -43,69 +43,73 @@ /// This class encapsulates all the state used to verify an operation region. class OperationVerifier { public: - explicit OperationVerifier() {} + explicit OperationVerifier(MLIRContext *context) + : parallelismEnabled(context->isMultithreadingEnabled()) {} /// Verify the given operation. LogicalResult verifyOpAndDominance(Operation &op); private: - /// Verify the given potentially nested region or block. - LogicalResult verifyRegion(Region ®ion); - LogicalResult verifyBlock(Block &block); - LogicalResult verifyOperation(Operation &op); + LogicalResult + verifyBlock(Block &block, + SmallVectorImpl &opsWithIsolatedRegions); + /// Verify the properties and dominance relationships of this operation, + /// stopping region recursion at any "isolated from above operations". Any + /// such ops are returned in the opsWithIsolatedRegions vector. + LogicalResult + verifyOperation(Operation &op, + SmallVectorImpl &opsWithIsolatedRegions); /// Verify the dominance property of regions contained within the given /// Operation. - LogicalResult verifyDominanceOfContainedRegions(Operation &op); - - /// Emit an error for the given block. - InFlightDiagnostic emitError(Block &bb, const Twine &message) { - // Take the location information for the first operation in the block. - if (!bb.empty()) - return bb.front().emitError(message); - - // Worst case, fall back to using the parent's location. - return mlir::emitError(bb.getParent()->getLoc(), message); - } + LogicalResult verifyDominanceOfContainedRegions(Operation &op, + DominanceInfo &domInfo); - /// Dominance information for this operation, when checking dominance. - DominanceInfo *domInfo = nullptr; + /// This is true if parallelism is enabled on the MLIRContext. + const bool parallelismEnabled; }; } // end anonymous namespace -/// Verify the given operation. LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) { - // Verify the operation first. - if (failed(verifyOperation(op))) + SmallVector opsWithIsolatedRegions; + + // Verify the operation first, collecting any IsolatedFromAbove operations. + if (failed(verifyOperation(op, opsWithIsolatedRegions))) return failure(); // Since everything looks structurally ok to this point, we do a dominance // check for any nested regions. We do this as a second pass since malformed - // CFG's can cause dominator analysis constructure to crash and we want the + // CFG's can cause dominator analysis construction to crash and we want the // verifier to be resilient to malformed code. - DominanceInfo theDomInfo; - domInfo = &theDomInfo; - if (failed(verifyDominanceOfContainedRegions(op))) - return failure(); - - domInfo = nullptr; - return success(); -} - -LogicalResult OperationVerifier::verifyRegion(Region ®ion) { - if (region.empty()) - return success(); - - // Verify the first block has no predecessors. - auto *firstBB = ®ion.front(); - if (!firstBB->hasNoPredecessors()) - return mlir::emitError(region.getLoc(), - "entry block of region may not have predecessors"); + if (op.getNumRegions() != 0) { + DominanceInfo domInfo; + if (failed(verifyDominanceOfContainedRegions(op, domInfo))) + return failure(); + } - // Verify each of the blocks within the region. - for (Block &block : region) - if (failed(verifyBlock(block))) + // Check the dominance properties and invariants of any operations in the + // regions contained by the 'opsWithIsolatedRegions' operations. + if (!parallelismEnabled || opsWithIsolatedRegions.size() <= 1) { + // If parallelism is disabled or if there is only 0/1 operation to do, use + // a simple non-parallel loop. + for (Operation *op : opsWithIsolatedRegions) { + if (failed(verifyOpAndDominance(*op))) + return failure(); + } + } else { + // Otherwise, verify the operations and their bodies in parallel. + ParallelDiagnosticHandler handler(op.getContext()); + std::atomic passFailed(false); + llvm::parallelForEachN(0, opsWithIsolatedRegions.size(), [&](size_t opIdx) { + handler.setOrderIDForThread(opIdx); + if (failed(verifyOpAndDominance(*opsWithIsolatedRegions[opIdx]))) + passFailed = true; + handler.eraseOrderIDForThread(); + }); + if (passFailed) return failure(); + } + return success(); } @@ -124,28 +128,39 @@ return !op || op->mightHaveTrait(); } -LogicalResult OperationVerifier::verifyBlock(Block &block) { +LogicalResult OperationVerifier::verifyBlock( + Block &block, SmallVectorImpl &opsWithIsolatedRegions) { + for (auto arg : block.getArguments()) if (arg.getOwner() != &block) - return emitError(block, "block argument not owned by block"); + return emitError(arg.getLoc(), "block argument not owned by block"); // Verify that this block has a terminator. if (block.empty()) { if (mayBeValidWithoutTerminator(&block)) return success(); - return emitError(block, "empty block: expect at least a terminator"); + return emitError(block.getParent()->getLoc(), + "empty block: expect at least a terminator"); } // Check each operation, and make sure there are no branches out of the // middle of this block. - for (auto &op : llvm::make_range(block.begin(), block.end())) { + for (auto &op : block) { // Only the last instructions is allowed to have successors. if (op.getNumSuccessors() != 0 && &op != &block.back()) return op.emitError( "operation with block successors must terminate its parent block"); - if (failed(verifyOperation(op))) - return failure(); + // If this operation has regions and is IsolatedFromAbove, we defer + // checking. This allows us to parallelize verification better. + if (op.getNumRegions() != 0 && + op.hasTrait()) { + opsWithIsolatedRegions.push_back(&op); + } else { + // Otherwise, check the operation inline. + if (failed(verifyOperation(op, opsWithIsolatedRegions))) + return failure(); + } } // Verify that this block is not branching to a block of a different @@ -167,7 +182,11 @@ return success(); } -LogicalResult OperationVerifier::verifyOperation(Operation &op) { +/// Verify the properties and dominance relationships of this operation, +/// stopping region recursion at any "isolated from above operations". Any such +/// ops are returned in the opsWithIsolatedRegions vector. +LogicalResult OperationVerifier::verifyOperation( + Operation &op, SmallVectorImpl &opsWithIsolatedRegions) { // Check that operands are non-nil and structurally ok. for (auto operand : op.getOperands()) if (!operand) @@ -188,7 +207,7 @@ return failure(); if (unsigned numRegions = op.getNumRegions()) { - auto kindInterface = dyn_cast(op); + auto kindInterface = dyn_cast(op); // Verify that all child regions are ok. for (unsigned i = 0; i < numRegions; ++i) { @@ -201,17 +220,25 @@ // designed to limit the number of cases that have to be handled by // transforms and conversions. if (op.isRegistered() && kind == RegionKind::Graph) { - // Empty regions are fine. - if (region.empty()) - continue; - // Non-empty regions must contain a single basic block. - if (std::next(region.begin()) != region.end()) + if (!region.empty() && !region.hasOneBlock()) return op.emitOpError("expects graph region #") << i << " to have 0 or 1 blocks"; } - if (failed(verifyRegion(region))) - return failure(); + + if (region.empty()) + continue; + + // Verify the first block has no predecessors. + Block *firstBB = ®ion.front(); + if (!firstBB->hasNoPredecessors()) + return emitError(op.getLoc(), + "entry block of region may not have predecessors"); + + // Verify each of the blocks within the region. + for (Block &block : region) + if (failed(verifyBlock(block, opsWithIsolatedRegions))) + return failure(); } } @@ -303,22 +330,22 @@ /// Verify the dominance of each of the nested blocks within the given operation LogicalResult -OperationVerifier::verifyDominanceOfContainedRegions(Operation &op) { +OperationVerifier::verifyDominanceOfContainedRegions(Operation &op, + DominanceInfo &domInfo) { for (Region ®ion : op.getRegions()) { // Verify the dominance of each of the held operations. for (Block &block : region) { // Dominance is only meaningful inside reachable blocks. - bool isReachable = domInfo->isReachableFromEntry(&block); + bool isReachable = domInfo.isReachableFromEntry(&block); for (Operation &op : block) { if (isReachable) { // Check that operands properly dominate this use. - for (unsigned operandNo = 0, e = op.getNumOperands(); operandNo != e; - ++operandNo) { - if (domInfo->properlyDominates(op.getOperand(operandNo), &op)) + for (auto operand : llvm::enumerate(op.getOperands())) { + if (domInfo.properlyDominates(operand.value(), &op)) continue; - diagnoseInvalidOperandDominance(op, operandNo); + diagnoseInvalidOperandDominance(op, operand.index()); return failure(); } } @@ -326,9 +353,15 @@ // Recursively verify dominance within each operation in the // block, even if the block itself is not reachable, or we are in // a region which doesn't respect dominance. - if (op.getNumRegions() != 0) - if (failed(verifyDominanceOfContainedRegions(op))) + if (op.getNumRegions() != 0) { + // If this operation is IsolatedFromAbove, then we'll handle it in the + // outer verification loop. + if (op.hasTrait()) + continue; + + if (failed(verifyDominanceOfContainedRegions(op, domInfo))) return failure(); + } } } } @@ -343,5 +376,5 @@ /// compiler bugs. On error, this reports the error through the MLIRContext and /// returns failure. LogicalResult mlir::verify(Operation *op) { - return OperationVerifier().verifyOpAndDominance(*op); + return OperationVerifier(op->getContext()).verifyOpAndDominance(*op); }