[MLIR] Move Verifier and Dominance Analysis from /Analysis to /IR

[stephenneuendorffer]

Summary

These libraries are distinct from other things in Analysis in that they
operate only on core IR concepts. This also simplifies dependencies
so that Dialect -> Analysis -> Parser -> IR. Previously, the parser depended
on portions of the the Analysis directory as well, which sometimes
caused issues with the way the cmake makefile generator discovers
dependencies on generated files during compilation.

[rriddle]

The files are marked as being added, but I would have expected something to mark the original locations as being moved/deleted.

mlir/examples/toy/Ch2/mlir/MLIRGen.cpp

18

Can you fix these include orderings now? I would expect a run of clang-format to handle it.

mlir/include/mlir/IR/Dominance.h

9

MLIR_IR_ Now

mlir/include/mlir/IR/Verifier.h

9

MLIR_IR

[rriddle]

mlir/lib/IR/Verifier.cpp

31

This one is an exception, generally if there is a matching header it should be included first.

[stephenneuendorffer]

mlir/lib/IR/Verifier.cpp

31

And I was confused by the fact that git clang-format did something wierd with it!

mlir/examples/toy/Ch2/mlir/MLIRGen.cpp

 // for the Toy language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/IR/StandardTypes.h"
 
 #include "llvm/ADT/STLExtras.h"

mlir/examples/toy/Ch2/toyc.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/Dialect.h"
 #include "toy/MLIRGen.h"
 #include "toy/Parser.h"
 #include <memory>
 
-#include "mlir/Analysis/Verifier.h"
+#include "mlir/IR/Verifier.h"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/Parser.h"
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"

mlir/examples/toy/Ch3/mlir/MLIRGen.cpp

 // for the Toy language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/IR/StandardTypes.h"
 
 #include "llvm/ADT/STLExtras.h"

mlir/examples/toy/Ch3/toyc.cpp

 //===- toyc.cpp - The Toy Compiler ----------------------------------------===//
 //
 // 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 entry point for the Toy compiler.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/Dialect.h"
 #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"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Pass/PassManager.h"
 #include "mlir/Transforms/Passes.h"
 
 #include "llvm/ADT/StringRef.h"

mlir/examples/toy/Ch4/mlir/MLIRGen.cpp

 // for the Toy language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/IR/StandardTypes.h"
 
 #include "llvm/ADT/STLExtras.h"

mlir/examples/toy/Ch4/toyc.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/Dialect.h"
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Pass/PassManager.h"
 #include "mlir/Transforms/Passes.h"
 
 #include "llvm/ADT/StringRef.h"

mlir/examples/toy/Ch5/mlir/MLIRGen.cpp

 // for the Toy language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/IR/StandardTypes.h"
 
 #include "llvm/ADT/STLExtras.h"

mlir/examples/toy/Ch5/toyc.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/Dialect.h"
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/Parser.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Pass/PassManager.h"
 #include "mlir/Transforms/Passes.h"
 

mlir/examples/toy/Ch6/mlir/MLIRGen.cpp

 // for the Toy language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/IR/StandardTypes.h"
 
 #include "llvm/ADT/STLExtras.h"

mlir/examples/toy/Ch6/toyc.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/Dialect.h"
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/Module.h"
 #include "mlir/InitAllDialects.h"
 #include "mlir/Parser.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Pass/PassManager.h"

mlir/examples/toy/Ch7/mlir/MLIRGen.cpp

 // for the Toy language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/MLIRContext.h"
 #include "mlir/IR/Module.h"
 #include "mlir/IR/StandardTypes.h"
 
 #include "llvm/ADT/STLExtras.h"

mlir/examples/toy/Ch7/toyc.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "toy/Dialect.h"
 #include "toy/MLIRGen.h"
 #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"
 #include "mlir/IR/Module.h"
 #include "mlir/InitAllDialects.h"
 #include "mlir/Parser.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Pass/PassManager.h"

mlir/include/mlir/IR/Dominance.h

+//===- 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<mlir::Block, false>;
+extern template class llvm::DominatorTreeBase<mlir::Block, true>;
+
+namespace mlir {
+using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
+class Operation;
+
+namespace detail {
+template <bool IsPostDom> class DominanceInfoBase {
+  using base = llvm::DominatorTreeBase<Block, IsPostDom>;
+
+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<IsPostDom>;
+
+  /// 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<Region *, std::unique_ptr<base>> dominanceInfos;
+};
+} // end namespace detail
+
+/// A class for computing basic dominance information.
+class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
+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</*IsPostDom=*/true> {
+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<mlir::DominanceInfoNode *> {
+  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<const mlir::DominanceInfoNode *> {
+  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

mlir/include/mlir/IR/Verifier.h

+//===- 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

mlir/lib/IR/Dominance.cpp

+//===- 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<Block, /*IsPostDom=*/false>;
+template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/true>;
+template class llvm::DomTreeNodeBase<Block>;
+
+//===----------------------------------------------------------------------===//
+// DominanceInfoBase
+//===----------------------------------------------------------------------===//
+
+template <bool IsPostDom>
+void DominanceInfoBase<IsPostDom>::recalculate(Operation *op) {
+  dominanceInfos.clear();
+
+  /// Build the dominance for each of the operation regions.
+  op->walk([&](Operation *op) {
+    for (auto &region : op->getRegions()) {
+      // Don't compute dominance if the region is empty.
+      if (region.empty())
+        continue;
+      auto opDominance = std::make_unique<base>();
+      opDominance->recalculate(region);
+      dominanceInfos.try_emplace(&region, 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 <typename FuncT>
+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<Region *, Block *, 4> 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 <bool IsPostDom>
+Block *
+DominanceInfoBase<IsPostDom>::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 <bool IsPostDom>
+DominanceInfoNode *DominanceInfoBase<IsPostDom>::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 IsPostDom>
+bool DominanceInfoBase<IsPostDom>::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</*IsPostDom=*/true>;
+template class mlir::detail::DominanceInfoBase</*IsPostDom=*/false>;
+
+//===----------------------------------------------------------------------===//
+// 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<BlockArgument>().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);
+}

mlir/lib/IR/Verifier.cpp

+//===- 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 &region);
+  LogicalResult verifyBlock(Block &block);
+  LogicalResult verifyOperation(Operation &op);
+
+  /// Verify the dominance within the given IR unit.
+  LogicalResult verifyDominance(Region &region);
+  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<bool> 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 &region : op.getRegions())
+    if (failed(verifyDominance(region)))
+      return failure();
+
+  domInfo = nullptr;
+  return success();
+}
+
+LogicalResult OperationVerifier::verifyRegion(Region &region) {
+  if (region.empty())
+    return success();
+
+  // Verify the first block has no predecessors.
+  auto *firstBB = &region.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 &region : 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 &region) {
+  // 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 &region : 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);
+}

mlir/lib/Parser/CMakeLists.txt

 add_mlir_library(MLIRParser
   Lexer.cpp
   Parser.cpp
   Token.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${MLIR_MAIN_INCLUDE_DIR}/mlir/Parser
   )
 target_link_libraries(MLIRParser
   PUBLIC
   MLIRIR
-  MLIRAnalysis)
+  )

mlir/lib/Parser/Parser.cpp

 //===- Parser.cpp - MLIR Parser 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 parser for the MLIR textual form.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "mlir/IR/Builders.h"
 #include "mlir/IR/Dialect.h"
 #include "mlir/IR/DialectImplementation.h"
 #include "mlir/IR/IntegerSet.h"
 #include "mlir/IR/Location.h"

mlir/lib/Pass/Pass.cpp

 //===- Pass.cpp - Pass infrastructure 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 common pass infrastructure.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "mlir/Support/FileUtilities.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/CrashRecoveryContext.h"
 #include "llvm/Support/Mutex.h"

mlir/lib/Transforms/CSE.cpp

 //===- CSE.cpp - Common Sub-expression Elimination ------------------------===//
 //
 // 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 transformation pass performs a simple common sub-expression elimination
 // algorithm on operations within a region.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/ScopedHashTable.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/RecyclingAllocator.h"

mlir/lib/Transforms/MemRefDataFlowOpt.cpp

 // potentially getting rid of intermediate memref's entirely.
 // TODO(mlir-team): In the future, similar techniques could be used to eliminate
 // dead memref store's and perform more complex forwarding when support for
 // SSA scalars live out of 'affine.for'/'affine.if' statements is available.
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "mlir/Transforms/Passes.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include <algorithm>
 
 #define DEBUG_TYPE "memref-dataflow-opt"

mlir/lib/Transforms/Utils/Utils.cpp

 // structures.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Transforms/Utils.h"
 
 #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"
 #include "mlir/IR/Function.h"
 #include "mlir/IR/Module.h"
 #include "mlir/Support/MathExtras.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/TypeSwitch.h"

mlir/lib/Translation/Translation.cpp

 //===- Translation.cpp - Translation registry -----------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Definitions of the translation registry.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/Support/SourceMgr.h"
 
 using namespace mlir;
 
 //===----------------------------------------------------------------------===//