diff --git a/mlir/examples/toy/Ch2/mlir/MLIRGen.cpp b/mlir/examples/toy/Ch2/mlir/MLIRGen.cpp --- a/mlir/examples/toy/Ch2/mlir/MLIRGen.cpp +++ b/mlir/examples/toy/Ch2/mlir/MLIRGen.cpp @@ -15,7 +15,7 @@ #include "toy/AST.h" #include "toy/Dialect.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Attributes.h" #include "mlir/IR/Builders.h" #include "mlir/IR/Function.h" diff --git a/mlir/examples/toy/Ch2/toyc.cpp b/mlir/examples/toy/Ch2/toyc.cpp --- a/mlir/examples/toy/Ch2/toyc.cpp +++ b/mlir/examples/toy/Ch2/toyc.cpp @@ -15,7 +15,7 @@ #include "toy/Parser.h" #include -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/MLIRContext.h" #include "mlir/IR/Module.h" #include "mlir/Parser.h" diff --git a/mlir/examples/toy/Ch3/mlir/MLIRGen.cpp b/mlir/examples/toy/Ch3/mlir/MLIRGen.cpp --- a/mlir/examples/toy/Ch3/mlir/MLIRGen.cpp +++ b/mlir/examples/toy/Ch3/mlir/MLIRGen.cpp @@ -15,7 +15,7 @@ #include "toy/AST.h" #include "toy/Dialect.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Attributes.h" #include "mlir/IR/Builders.h" #include "mlir/IR/Function.h" diff --git a/mlir/examples/toy/Ch3/toyc.cpp b/mlir/examples/toy/Ch3/toyc.cpp --- a/mlir/examples/toy/Ch3/toyc.cpp +++ b/mlir/examples/toy/Ch3/toyc.cpp @@ -14,7 +14,7 @@ #include "toy/MLIRGen.h" #include "toy/Parser.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/MLIRContext.h" #include "mlir/IR/Module.h" #include "mlir/Parser.h" diff --git a/mlir/examples/toy/Ch4/mlir/MLIRGen.cpp b/mlir/examples/toy/Ch4/mlir/MLIRGen.cpp --- a/mlir/examples/toy/Ch4/mlir/MLIRGen.cpp +++ b/mlir/examples/toy/Ch4/mlir/MLIRGen.cpp @@ -15,7 +15,7 @@ #include "toy/AST.h" #include "toy/Dialect.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Attributes.h" #include "mlir/IR/Builders.h" #include "mlir/IR/Function.h" diff --git a/mlir/examples/toy/Ch4/toyc.cpp b/mlir/examples/toy/Ch4/toyc.cpp --- a/mlir/examples/toy/Ch4/toyc.cpp +++ b/mlir/examples/toy/Ch4/toyc.cpp @@ -15,7 +15,7 @@ #include "toy/Parser.h" #include "toy/Passes.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/MLIRContext.h" #include "mlir/IR/Module.h" #include "mlir/Parser.h" diff --git a/mlir/examples/toy/Ch5/mlir/MLIRGen.cpp b/mlir/examples/toy/Ch5/mlir/MLIRGen.cpp --- a/mlir/examples/toy/Ch5/mlir/MLIRGen.cpp +++ b/mlir/examples/toy/Ch5/mlir/MLIRGen.cpp @@ -15,7 +15,7 @@ #include "toy/AST.h" #include "toy/Dialect.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Attributes.h" #include "mlir/IR/Builders.h" #include "mlir/IR/Function.h" diff --git a/mlir/examples/toy/Ch5/toyc.cpp b/mlir/examples/toy/Ch5/toyc.cpp --- a/mlir/examples/toy/Ch5/toyc.cpp +++ b/mlir/examples/toy/Ch5/toyc.cpp @@ -15,7 +15,7 @@ #include "toy/Parser.h" #include "toy/Passes.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/MLIRContext.h" #include "mlir/IR/Module.h" #include "mlir/InitAllDialects.h" diff --git a/mlir/examples/toy/Ch6/mlir/MLIRGen.cpp b/mlir/examples/toy/Ch6/mlir/MLIRGen.cpp --- a/mlir/examples/toy/Ch6/mlir/MLIRGen.cpp +++ b/mlir/examples/toy/Ch6/mlir/MLIRGen.cpp @@ -15,7 +15,7 @@ #include "toy/AST.h" #include "toy/Dialect.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Attributes.h" #include "mlir/IR/Builders.h" #include "mlir/IR/Function.h" diff --git a/mlir/examples/toy/Ch6/toyc.cpp b/mlir/examples/toy/Ch6/toyc.cpp --- a/mlir/examples/toy/Ch6/toyc.cpp +++ b/mlir/examples/toy/Ch6/toyc.cpp @@ -15,7 +15,7 @@ #include "toy/Parser.h" #include "toy/Passes.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/ExecutionEngine/ExecutionEngine.h" #include "mlir/ExecutionEngine/OptUtils.h" #include "mlir/IR/MLIRContext.h" diff --git a/mlir/examples/toy/Ch7/mlir/MLIRGen.cpp b/mlir/examples/toy/Ch7/mlir/MLIRGen.cpp --- a/mlir/examples/toy/Ch7/mlir/MLIRGen.cpp +++ b/mlir/examples/toy/Ch7/mlir/MLIRGen.cpp @@ -15,7 +15,7 @@ #include "toy/AST.h" #include "toy/Dialect.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Attributes.h" #include "mlir/IR/Builders.h" #include "mlir/IR/Function.h" diff --git a/mlir/examples/toy/Ch7/toyc.cpp b/mlir/examples/toy/Ch7/toyc.cpp --- a/mlir/examples/toy/Ch7/toyc.cpp +++ b/mlir/examples/toy/Ch7/toyc.cpp @@ -15,7 +15,7 @@ #include "toy/Parser.h" #include "toy/Passes.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/ExecutionEngine/ExecutionEngine.h" #include "mlir/ExecutionEngine/OptUtils.h" #include "mlir/IR/MLIRContext.h" diff --git a/mlir/include/mlir/IR/Dominance.h b/mlir/include/mlir/IR/Dominance.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/IR/Dominance.h @@ -0,0 +1,146 @@ +//===- Dominance.h - Dominator analysis for CFGs ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_DOMINANCE_H +#define MLIR_ANALYSIS_DOMINANCE_H + +#include "mlir/IR/RegionGraphTraits.h" +#include "llvm/Support/GenericDomTree.h" + +extern template class llvm::DominatorTreeBase; +extern template class llvm::DominatorTreeBase; + +namespace mlir { +using DominanceInfoNode = llvm::DomTreeNodeBase; +class Operation; + +namespace detail { +template class DominanceInfoBase { + using base = llvm::DominatorTreeBase; + +public: + DominanceInfoBase(Operation *op) { recalculate(op); } + DominanceInfoBase(DominanceInfoBase &&) = default; + DominanceInfoBase &operator=(DominanceInfoBase &&) = default; + + DominanceInfoBase(const DominanceInfoBase &) = delete; + DominanceInfoBase &operator=(const DominanceInfoBase &) = delete; + + /// Recalculate the dominance info. + void recalculate(Operation *op); + + /// Finds the nearest common dominator block for the two given blocks a + /// and b. If no common dominator can be found, this function will return + /// nullptr. + Block *findNearestCommonDominator(Block *a, Block *b) const; + + /// Get the root dominance node of the given region. + DominanceInfoNode *getRootNode(Region *region) { + assert(dominanceInfos.count(region) != 0); + return dominanceInfos[region]->getRootNode(); + } + + /// Return the dominance node from the Region containing block A. + DominanceInfoNode *getNode(Block *a); + +protected: + using super = DominanceInfoBase; + + /// Return true if the specified block A properly dominates block B. + bool properlyDominates(Block *a, Block *b) const; + + /// A mapping of regions to their base dominator tree. + DenseMap> dominanceInfos; +}; +} // end namespace detail + +/// A class for computing basic dominance information. +class DominanceInfo : public detail::DominanceInfoBase { +public: + using super::super; + + /// Return true if operation A properly dominates operation B. + bool properlyDominates(Operation *a, Operation *b) const; + + /// Return true if operation A dominates operation B. + bool dominates(Operation *a, Operation *b) const { + return a == b || properlyDominates(a, b); + } + + /// Return true if value A properly dominates operation B. + bool properlyDominates(Value a, Operation *b) const; + + /// Return true if operation A dominates operation B. + bool dominates(Value a, Operation *b) const { + return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b); + } + + /// Return true if the specified block A dominates block B. + bool dominates(Block *a, Block *b) const { + return a == b || properlyDominates(a, b); + } + + /// Return true if the specified block A properly dominates block B. + bool properlyDominates(Block *a, Block *b) const { + return super::properlyDominates(a, b); + } + + /// Update the internal DFS numbers for the dominance nodes. + void updateDFSNumbers(); +}; + +/// A class for computing basic postdominance information. +class PostDominanceInfo : public detail::DominanceInfoBase { +public: + using super::super; + + /// Return true if operation A properly postdominates operation B. + bool properlyPostDominates(Operation *a, Operation *b); + + /// Return true if operation A postdominates operation B. + bool postDominates(Operation *a, Operation *b) { + return a == b || properlyPostDominates(a, b); + } + + /// Return true if the specified block A properly postdominates block B. + bool properlyPostDominates(Block *a, Block *b) { + return super::properlyDominates(a, b); + } + + /// Return true if the specified block A postdominates block B. + bool postDominates(Block *a, Block *b) { + return a == b || properlyPostDominates(a, b); + } +}; + +} // end namespace mlir + +namespace llvm { + +/// DominatorTree GraphTraits specialization so the DominatorTree can be +/// iterated by generic graph iterators. +template <> struct GraphTraits { + using ChildIteratorType = mlir::DominanceInfoNode::iterator; + using NodeRef = mlir::DominanceInfoNode *; + + static NodeRef getEntryNode(NodeRef N) { return N; } + static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } + static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } +}; + +template <> struct GraphTraits { + using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; + using NodeRef = const mlir::DominanceInfoNode *; + + static NodeRef getEntryNode(NodeRef N) { return N; } + static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } + static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } +}; + +} // end namespace llvm +#endif diff --git a/mlir/include/mlir/IR/Verifier.h b/mlir/include/mlir/IR/Verifier.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/IR/Verifier.h @@ -0,0 +1,22 @@ +//===- Verifier.h - Verifier analysis for MLIR structures -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_VERIFIER_H +#define MLIR_ANALYSIS_VERIFIER_H + +namespace mlir { +struct LogicalResult; +class Operation; + +/// Perform (potentially expensive) checks of invariants, used to detect +/// compiler bugs, on this operation and any nested operations. On error, this +/// reports the error through the MLIRContext and returns failure. +LogicalResult verify(Operation *op); +} // end namespace mlir + +#endif diff --git a/mlir/lib/IR/Dominance.cpp b/mlir/lib/IR/Dominance.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/IR/Dominance.cpp @@ -0,0 +1,255 @@ +//===- Dominance.cpp - Dominator analysis for CFGs ------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Implementation of dominance related classes and instantiations of extern +// templates. +// +//===----------------------------------------------------------------------===// + +#include "mlir/IR/Dominance.h" +#include "mlir/IR/Operation.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/GenericDomTreeConstruction.h" + +using namespace mlir; +using namespace mlir::detail; + +template class llvm::DominatorTreeBase; +template class llvm::DominatorTreeBase; +template class llvm::DomTreeNodeBase; + +//===----------------------------------------------------------------------===// +// DominanceInfoBase +//===----------------------------------------------------------------------===// + +template +void DominanceInfoBase::recalculate(Operation *op) { + dominanceInfos.clear(); + + /// Build the dominance for each of the operation regions. + op->walk([&](Operation *op) { + for (auto ®ion : op->getRegions()) { + // Don't compute dominance if the region is empty. + if (region.empty()) + continue; + auto opDominance = std::make_unique(); + opDominance->recalculate(region); + dominanceInfos.try_emplace(®ion, std::move(opDominance)); + } + }); +} + +/// Walks up the list of containers of the given block and calls the +/// user-defined traversal function for every pair of a region and block that +/// could be found during traversal. If the user-defined function returns true +/// for a given pair, traverseAncestors will return the current block. Nullptr +/// otherwise. +template +Block *traverseAncestors(Block *block, const FuncT &func) { + // Invoke the user-defined traversal function in the beginning for the current + // block. + if (func(block)) + return block; + + Region *region = block->getParent(); + while (region) { + Operation *ancestor = region->getParentOp(); + // If we have reached to top... return. + if (!ancestor || !(block = ancestor->getBlock())) + break; + + // Update the nested region using the new ancestor block. + region = block->getParent(); + + // Invoke the user-defined traversal function and check whether we can + // already return. + if (func(block)) + return block; + } + return nullptr; +} + +/// Tries to update the given block references to live in the same region by +/// exploring the relationship of both blocks with respect to their regions. +static bool tryGetBlocksInSameRegion(Block *&a, Block *&b) { + // If both block do not live in the same region, we will have to check their + // parent operations. + if (a->getParent() == b->getParent()) + return true; + + // Iterate over all ancestors of a and insert them into the map. This allows + // for efficient lookups to find a commonly shared region. + llvm::SmallDenseMap ancestors; + traverseAncestors(a, [&](Block *block) { + ancestors[block->getParent()] = block; + return false; + }); + + // Try to find a common ancestor starting with regionB. + b = traverseAncestors( + b, [&](Block *block) { return ancestors.count(block->getParent()) > 0; }); + + // If there is no match, we will not be able to find a common dominator since + // both regions do not share a common parent region. + if (!b) + return false; + + // We have found a common parent region. Update block a to refer to this + // region. + auto it = ancestors.find(b->getParent()); + assert(it != ancestors.end()); + a = it->second; + return true; +} + +template +Block * +DominanceInfoBase::findNearestCommonDominator(Block *a, + Block *b) const { + // If either a or b are null, then conservatively return nullptr. + if (!a || !b) + return nullptr; + + // Try to find blocks that are in the same region. + if (!tryGetBlocksInSameRegion(a, b)) + return nullptr; + + // Get and verify dominance information of the common parent region. + Region *parentRegion = a->getParent(); + auto infoAIt = dominanceInfos.find(parentRegion); + if (infoAIt == dominanceInfos.end()) + return nullptr; + + // Since the blocks live in the same region, we can rely on already + // existing dominance functionality. + return infoAIt->second->findNearestCommonDominator(a, b); +} + +template +DominanceInfoNode *DominanceInfoBase::getNode(Block *a) { + auto *region = a->getParent(); + assert(dominanceInfos.count(region) != 0); + return dominanceInfos[region]->getNode(a); +} + +/// Return true if the specified block A properly dominates block B. +template +bool DominanceInfoBase::properlyDominates(Block *a, Block *b) const { + // A block dominates itself but does not properly dominate itself. + if (a == b) + return false; + + // If either a or b are null, then conservatively return false. + if (!a || !b) + return false; + + // If both blocks are not in the same region, 'a' properly dominates 'b' if + // 'b' is defined in an operation region that (recursively) ends up being + // dominated by 'a'. Walk up the list of containers enclosing B. + auto *regionA = a->getParent(); + if (regionA != b->getParent()) { + b = traverseAncestors( + b, [&](Block *block) { return block->getParent() == regionA; }); + + // If we could not find a valid block b then it is either a not a dominator + // or a post dominator. + if (!b) + return IsPostDom; + + // Check to see if the ancestor of 'b' is the same block as 'a'. + if (a == b) + return true; + } + + // Otherwise, use the standard dominance functionality. + + // If we don't have a dominance information for this region, assume that b is + // dominated by anything. + auto baseInfoIt = dominanceInfos.find(regionA); + if (baseInfoIt == dominanceInfos.end()) + return true; + return baseInfoIt->second->properlyDominates(a, b); +} + +template class mlir::detail::DominanceInfoBase; +template class mlir::detail::DominanceInfoBase; + +//===----------------------------------------------------------------------===// +// DominanceInfo +//===----------------------------------------------------------------------===// + +/// Return true if operation A properly dominates operation B. +bool DominanceInfo::properlyDominates(Operation *a, Operation *b) const { + auto *aBlock = a->getBlock(), *bBlock = b->getBlock(); + + // If a or b are not within a block, then a does not dominate b. + if (!aBlock || !bBlock) + return false; + + // If the blocks are the same, then check if b is before a in the block. + if (aBlock == bBlock) + return a->isBeforeInBlock(b); + + // Traverse up b's hierarchy to check if b's block is contained in a's. + if (auto *bAncestor = aBlock->findAncestorOpInBlock(*b)) { + // Since we already know that aBlock != bBlock, here bAncestor != b. + // a and bAncestor are in the same block; check if 'a' dominates + // bAncestor. + return dominates(a, bAncestor); + } + + // If the blocks are different, check if a's block dominates b's. + return properlyDominates(aBlock, bBlock); +} + +/// Return true if value A properly dominates operation B. +bool DominanceInfo::properlyDominates(Value a, Operation *b) const { + if (auto *aOp = a.getDefiningOp()) { + // The values defined by an operation do *not* dominate any nested + // operations. + if (aOp->getParentRegion() != b->getParentRegion() && aOp->isAncestor(b)) + return false; + return properlyDominates(aOp, b); + } + + // block arguments properly dominate all operations in their own block, so + // we use a dominates check here, not a properlyDominates check. + return dominates(a.cast().getOwner(), b->getBlock()); +} + +void DominanceInfo::updateDFSNumbers() { + for (auto &iter : dominanceInfos) + iter.second->updateDFSNumbers(); +} + +//===----------------------------------------------------------------------===// +// PostDominanceInfo +//===----------------------------------------------------------------------===// + +/// Returns true if statement 'a' properly postdominates statement b. +bool PostDominanceInfo::properlyPostDominates(Operation *a, Operation *b) { + auto *aBlock = a->getBlock(), *bBlock = b->getBlock(); + + // If a or b are not within a block, then a does not post dominate b. + if (!aBlock || !bBlock) + return false; + + // If the blocks are the same, check if b is before a in the block. + if (aBlock == bBlock) + return b->isBeforeInBlock(a); + + // Traverse up b's hierarchy to check if b's block is contained in a's. + if (auto *bAncestor = a->getBlock()->findAncestorOpInBlock(*b)) + // Since we already know that aBlock != bBlock, here bAncestor != b. + // a and bAncestor are in the same block; check if 'a' postdominates + // bAncestor. + return postDominates(a, bAncestor); + + // If the blocks are different, check if a's block post dominates b's. + return properlyDominates(aBlock, bBlock); +} diff --git a/mlir/lib/IR/Verifier.cpp b/mlir/lib/IR/Verifier.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/IR/Verifier.cpp @@ -0,0 +1,265 @@ +//===- Verifier.cpp - MLIR Verifier Implementation ------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements the verify() methods on the various IR types, performing +// (potentially expensive) checks on the holistic structure of the code. This +// can be used for detecting bugs in compiler transformations and hand written +// .mlir files. +// +// The checks in this file are only for things that can occur as part of IR +// transformations: e.g. violation of dominance information, malformed operation +// attributes, etc. MLIR supports transformations moving IR through locally +// invalid states (e.g. unlinking an operation from a block before re-inserting +// it in a new place), but each transformation must complete with the IR in a +// valid form. +// +// This should not check for things that are always wrong by construction (e.g. +// attributes or other immutable structures that are incorrect), because those +// are not mutable and can be checked at time of construction. +// +//===----------------------------------------------------------------------===// + +#include "mlir/IR/Verifier.h" +#include "mlir/IR/Dominance.h" +#include "mlir/IR/Attributes.h" +#include "mlir/IR/Dialect.h" +#include "mlir/IR/Operation.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/PrettyStackTrace.h" +#include "llvm/Support/Regex.h" + +using namespace mlir; + +namespace { +/// This class encapsulates all the state used to verify an operation region. +class OperationVerifier { +public: + explicit OperationVerifier(MLIRContext *ctx) : ctx(ctx) {} + + /// Verify the given operation. + LogicalResult verify(Operation &op); + + /// Returns the registered dialect for a dialect-specific attribute. + Dialect *getDialectForAttribute(const NamedAttribute &attr) { + assert(attr.first.strref().contains('.') && "expected dialect attribute"); + auto dialectNamePair = attr.first.strref().split('.'); + return ctx->getRegisteredDialect(dialectNamePair.first); + } + +private: + /// Verify the given potentially nested region or block. + LogicalResult verifyRegion(Region ®ion); + LogicalResult verifyBlock(Block &block); + LogicalResult verifyOperation(Operation &op); + + /// Verify the dominance within the given IR unit. + LogicalResult verifyDominance(Region ®ion); + LogicalResult verifyDominance(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); + } + + /// The current context for the verifier. + MLIRContext *ctx; + + /// Dominance information for this operation, when checking dominance. + DominanceInfo *domInfo = nullptr; + + /// Mapping between dialect namespace and if that dialect supports + /// unregistered operations. + llvm::StringMap dialectAllowsUnknownOps; +}; +} // end anonymous namespace + +/// Verify the given operation. +LogicalResult OperationVerifier::verify(Operation &op) { + // Verify the operation first. + if (failed(verifyOperation(op))) + 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 + // verifier to be resilient to malformed code. + DominanceInfo theDomInfo(&op); + domInfo = &theDomInfo; + for (auto ®ion : op.getRegions()) + if (failed(verifyDominance(region))) + 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"); + + // Verify each of the blocks within the region. + for (auto &block : region) + if (failed(verifyBlock(block))) + return failure(); + return success(); +} + +LogicalResult OperationVerifier::verifyBlock(Block &block) { + for (auto arg : block.getArguments()) + if (arg.getOwner() != &block) + return emitError(block, "block argument not owned by block"); + + // Verify that this block has a terminator. + if (block.empty()) + return emitError(block, "block with no terminator"); + + // Verify the non-terminator operations separately so that we can verify + // they has no successors. + for (auto &op : llvm::make_range(block.begin(), std::prev(block.end()))) { + if (op.getNumSuccessors() != 0) + return op.emitError( + "operation with block successors must terminate its parent block"); + + if (failed(verifyOperation(op))) + return failure(); + } + + // Verify the terminator. + if (failed(verifyOperation(block.back()))) + return failure(); + if (block.back().isKnownNonTerminator()) + return emitError(block, "block with no terminator"); + + // Verify that this block is not branching to a block of a different + // region. + for (Block *successor : block.getSuccessors()) + if (successor->getParent() != block.getParent()) + return block.back().emitOpError( + "branching to block of a different region"); + + return success(); +} + +LogicalResult OperationVerifier::verifyOperation(Operation &op) { + // Check that operands are non-nil and structurally ok. + for (auto operand : op.getOperands()) + if (!operand) + return op.emitError("null operand found"); + + /// Verify that all of the attributes are okay. + for (auto attr : op.getAttrs()) { + // Check for any optional dialect specific attributes. + if (!attr.first.strref().contains('.')) + continue; + if (auto *dialect = getDialectForAttribute(attr)) + if (failed(dialect->verifyOperationAttribute(&op, attr))) + return failure(); + } + + // If we can get operation info for this, check the custom hook. + auto *opInfo = op.getAbstractOperation(); + if (opInfo && failed(opInfo->verifyInvariants(&op))) + return failure(); + + // Verify that all child regions are ok. + for (auto ®ion : op.getRegions()) + if (failed(verifyRegion(region))) + return failure(); + + // If this is a registered operation, there is nothing left to do. + if (opInfo) + return success(); + + // Otherwise, verify that the parent dialect allows un-registered operations. + auto dialectPrefix = op.getName().getDialect(); + + // Check for an existing answer for the operation dialect. + auto it = dialectAllowsUnknownOps.find(dialectPrefix); + if (it == dialectAllowsUnknownOps.end()) { + // If the operation dialect is registered, query it directly. + if (auto *dialect = ctx->getRegisteredDialect(dialectPrefix)) + it = dialectAllowsUnknownOps + .try_emplace(dialectPrefix, dialect->allowsUnknownOperations()) + .first; + // Otherwise, unregistered dialects (when allowed by the context) + // conservatively allow unknown operations. + else { + if (!op.getContext()->allowsUnregisteredDialects() && !op.getDialect()) + return op.emitOpError() + << "created with unregistered dialect. If this is " + "intended, please call allowUnregisteredDialects() on the " + "MLIRContext, or use -allow-unregistered-dialect with " + "mlir-opt"; + + it = dialectAllowsUnknownOps.try_emplace(dialectPrefix, true).first; + } + } + + if (!it->second) { + return op.emitError("unregistered operation '") + << op.getName() << "' found in dialect ('" << dialectPrefix + << "') that does not allow unknown operations"; + } + + return success(); +} + +LogicalResult OperationVerifier::verifyDominance(Region ®ion) { + // Verify the dominance of each of the held operations. + for (auto &block : region) + for (auto &op : block) + if (failed(verifyDominance(op))) + return failure(); + return success(); +} + +LogicalResult OperationVerifier::verifyDominance(Operation &op) { + // Check that operands properly dominate this use. + for (unsigned operandNo = 0, e = op.getNumOperands(); operandNo != e; + ++operandNo) { + auto operand = op.getOperand(operandNo); + if (domInfo->properlyDominates(operand, &op)) + continue; + + auto diag = op.emitError("operand #") + << operandNo << " does not dominate this use"; + if (auto *useOp = operand.getDefiningOp()) + diag.attachNote(useOp->getLoc()) << "operand defined here"; + return failure(); + } + + // Verify the dominance of each of the nested blocks within this operation. + for (auto ®ion : op.getRegions()) + if (failed(verifyDominance(region))) + return failure(); + + return success(); +} + +//===----------------------------------------------------------------------===// +// Entrypoint +//===----------------------------------------------------------------------===// + +/// Perform (potentially expensive) checks of invariants, used to detect +/// compiler bugs. On error, this reports the error through the MLIRContext and +/// returns failure. +LogicalResult mlir::verify(Operation *op) { + return OperationVerifier(op->getContext()).verify(*op); +} diff --git a/mlir/lib/Parser/CMakeLists.txt b/mlir/lib/Parser/CMakeLists.txt --- a/mlir/lib/Parser/CMakeLists.txt +++ b/mlir/lib/Parser/CMakeLists.txt @@ -9,4 +9,4 @@ target_link_libraries(MLIRParser PUBLIC MLIRIR - MLIRAnalysis) + ) diff --git a/mlir/lib/Parser/Parser.cpp b/mlir/lib/Parser/Parser.cpp --- a/mlir/lib/Parser/Parser.cpp +++ b/mlir/lib/Parser/Parser.cpp @@ -12,7 +12,7 @@ #include "mlir/Parser.h" #include "Lexer.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/AffineExpr.h" #include "mlir/IR/AffineMap.h" #include "mlir/IR/Attributes.h" diff --git a/mlir/lib/Pass/Pass.cpp b/mlir/lib/Pass/Pass.cpp --- a/mlir/lib/Pass/Pass.cpp +++ b/mlir/lib/Pass/Pass.cpp @@ -12,7 +12,7 @@ #include "mlir/Pass/Pass.h" #include "PassDetail.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Diagnostics.h" #include "mlir/IR/Dialect.h" #include "mlir/IR/Module.h" diff --git a/mlir/lib/Transforms/CSE.cpp b/mlir/lib/Transforms/CSE.cpp --- a/mlir/lib/Transforms/CSE.cpp +++ b/mlir/lib/Transforms/CSE.cpp @@ -12,7 +12,7 @@ //===----------------------------------------------------------------------===// #include "PassDetail.h" -#include "mlir/Analysis/Dominance.h" +#include "mlir/IR/Dominance.h" #include "mlir/Pass/Pass.h" #include "mlir/Transforms/Passes.h" #include "mlir/Transforms/Utils.h" diff --git a/mlir/lib/Transforms/MemRefDataFlowOpt.cpp b/mlir/lib/Transforms/MemRefDataFlowOpt.cpp --- a/mlir/lib/Transforms/MemRefDataFlowOpt.cpp +++ b/mlir/lib/Transforms/MemRefDataFlowOpt.cpp @@ -15,7 +15,7 @@ #include "PassDetail.h" #include "mlir/Analysis/AffineAnalysis.h" -#include "mlir/Analysis/Dominance.h" +#include "mlir/IR/Dominance.h" #include "mlir/Analysis/Utils.h" #include "mlir/Dialect/Affine/IR/AffineOps.h" #include "mlir/Dialect/StandardOps/IR/Ops.h" diff --git a/mlir/lib/Transforms/Utils/Utils.cpp b/mlir/lib/Transforms/Utils/Utils.cpp --- a/mlir/lib/Transforms/Utils/Utils.cpp +++ b/mlir/lib/Transforms/Utils/Utils.cpp @@ -15,7 +15,7 @@ #include "mlir/Analysis/AffineAnalysis.h" #include "mlir/Analysis/AffineStructures.h" -#include "mlir/Analysis/Dominance.h" +#include "mlir/IR/Dominance.h" #include "mlir/Analysis/Utils.h" #include "mlir/Dialect/Affine/IR/AffineOps.h" #include "mlir/IR/Builders.h" diff --git a/mlir/lib/Translation/Translation.cpp b/mlir/lib/Translation/Translation.cpp --- a/mlir/lib/Translation/Translation.cpp +++ b/mlir/lib/Translation/Translation.cpp @@ -11,7 +11,7 @@ //===----------------------------------------------------------------------===// #include "mlir/Translation.h" -#include "mlir/Analysis/Verifier.h" +#include "mlir/IR/Verifier.h" #include "mlir/IR/Module.h" #include "mlir/Parser.h" #include "mlir/Support/LLVM.h"