[Verifier] Significantly speed up IsolatedFromAbove checking. NFC.

[lattner]

Summary

The implementation had a couple of problems, including checking
"isProperAncestor" in an inefficient way. It also recursed into
other "isolated from above" ops. In the case of CIRCT, we get
three levels of isolated ops:

mlir::ModuleOp
  firrtl::CircuitOp
     firrtl::FModuleOp

The verification for module would recurse into the circuits and
fmodules checking them. The verifier hook for circuit would
recurse into all the modules reverifying them, fmoduleop would
then reverify them. The same happens for mlir::ModuleOp and Func.

While here, fix an old design problem: IsolatedFromAbove checking
was implemented by a method on the Region class, which isn't
actually general and isn't used by anything else. Move it over
to be a trait impl verifier method like the others and specialize
it for its task.

[rriddle]

mlir/lib/IR/Operation.cpp

1110–1112

This comment seems off, e.g. there is no noteLoc provided here.

1137–1138

Seems like this is just !region.isAncestor(operandRegion).

[lattner]

Thank you for the quick review!

mlir/lib/IR/Operation.cpp

1110–1112

Indeed, fixed!

1137–1138

Oh nice. Thanks!

[lattner]

Improvements suggested by River

mlir/include/mlir/IR/OpDefinition.h

 LogicalResult verifyZeroSuccessor(Operation *op);
 LogicalResult verifyOneSuccessor(Operation *op);
 LogicalResult verifyNSuccessors(Operation *op, unsigned numSuccessors);
 LogicalResult verifyAtLeastNSuccessors(Operation *op, unsigned numSuccessors);
 LogicalResult verifyOperandSizeAttr(Operation *op, StringRef sizeAttrName);
 LogicalResult verifyResultSizeAttr(Operation *op, StringRef sizeAttrName);
 LogicalResult verifyNoRegionArguments(Operation *op);
 LogicalResult verifyElementwise(Operation *op);
+LogicalResult verifyIsIsolatedFromAbove(Operation *op);
 } // namespace impl
 
 /// Helper class for implementing traits.  Clients are not expected to interact
 /// with this directly, so its members are all protected.
 template <typename ConcreteType, template <typename> class TraitType>
 class TraitBase {
 protected:
   /// Return the ultimate Operation being worked on.

 
 /// This class provides the API for ops that are known to be isolated from
 /// above.
 template <typename ConcreteType>
 class IsIsolatedFromAbove
     : public TraitBase<ConcreteType, IsIsolatedFromAbove> {
 public:
   static LogicalResult verifyTrait(Operation *op) {
-    for (auto &region : op->getRegions())
-      if (!region.isIsolatedFromAbove(op->getLoc()))
-        return failure();
-    return success();
+    return impl::verifyIsIsolatedFromAbove(op);
   }
 };
 
 /// A trait of region holding operations that defines a new scope for polyhedral
 /// optimization purposes. Any SSA values of 'index' type that either dominate
 /// such an operation or are used at the top-level of such an operation
 /// automatically become valid symbols for the polyhedral scope defined by that
 /// operation. For more details, see `Traits.md#AffineScope`.
private:
   template <typename T, typename... Args>
   using has_single_result_fold =
       decltype(std::declval<T>().fold(std::declval<ArrayRef<Attribute>>()));
   template <typename T>
   using detect_has_single_result_fold =
       llvm::is_detected<has_single_result_fold, T>;
   /// Trait to check if T provides a general 'fold' method.
   template <typename T, typename... Args>
-  using has_fold = decltype(
-      std::declval<T>().fold(std::declval<ArrayRef<Attribute>>(),
-                             std::declval<SmallVectorImpl<OpFoldResult> &>()));
+  using has_fold = decltype(std::declval<T>().fold(
+      std::declval<ArrayRef<Attribute>>(),
   template <typename T>
   using detect_has_fold = llvm::is_detected<has_fold, T>;
   /// Trait to check if T provides a 'print' method.
   template <typename T, typename... Args>
   using has_print =
       decltype(std::declval<T>().print(std::declval<OpAsmPrinter &>()));
   template <typename T>
   using detect_has_print = llvm::is_detected<has_print, T>;

mlir/include/mlir/IR/Region.h

public:
   /// Return iterators that walk the operations nested directly within this
   /// region.
   OpIterator op_begin() { return OpIterator(this); }
   OpIterator op_end() { return OpIterator(this, /*end=*/true); }
   iterator_range<OpIterator> getOps() { return {op_begin(), op_end()}; }
 
   /// Return iterators that walk operations of type 'T' nested directly within
   /// this region.
-  template <typename OpT> op_iterator<OpT> op_begin() {
+  template <typename OpT>
+  op_iterator<OpT> op_begin() {
     return detail::op_filter_iterator<OpT, OpIterator>(op_begin(), op_end());
   }
-  template <typename OpT> op_iterator<OpT> op_end() {
+  template <typename OpT>
+  op_iterator<OpT> op_end() {
     return detail::op_filter_iterator<OpT, OpIterator>(op_end(), op_end());
   }
-  template <typename OpT> iterator_range<op_iterator<OpT>> getOps() {
+  template <typename OpT>
+  iterator_range<op_iterator<OpT>> getOps() {
     auto endIt = op_end();
     return {detail::op_filter_iterator<OpT, OpIterator>(op_begin(), endIt),
             detail::op_filter_iterator<OpT, OpIterator>(endIt, endIt)};
   }
 
   //===--------------------------------------------------------------------===//
   // Misc. utilities
   //===--------------------------------------------------------------------===//
 
   /// Return the region containing this region or nullptr if the region is
   /// attached to a top-level operation.
   Region *getParentRegion();
 
   /// Return the parent operation this region is attached to.
   Operation *getParentOp();
 
   /// Find the first parent operation of the given type, or nullptr if there is
   /// no ancestor operation.
-  template <typename ParentT> ParentT getParentOfType() {
+  template <typename ParentT>
+  ParentT getParentOfType() {
     auto *region = this;
     do {
       if (auto parent = dyn_cast_or_null<ParentT>(region->container))
         return parent;
     } while ((region = region->getParentRegion()));
     return ParentT();
   }
 
public:
 
   /// Takes body of another region (that region will have no body after this
   /// operation completes).  The current body of this region is cleared.
   void takeBody(Region &other) {
     blocks.clear();
     blocks.splice(blocks.end(), other.getBlocks());
   }
 
-  /// Check that this does not use any value defined outside it.
-  /// Emit errors if `noteLoc` is provided; this location is used to point
-  /// to the operation containing the region, the actual error is reported at
-  /// the operation with an offending use.
-  bool isIsolatedFromAbove(Optional<Location> noteLoc = llvm::None);
-
   /// Returns 'block' if 'block' lies in this region, or otherwise finds the
   /// ancestor of 'block' that lies in this region. Returns nullptr if the
   /// latter fails.
   Block *findAncestorBlockInRegion(Block &block);
 
   /// Drop all operand uses from operations within this region, which is
   /// an essential step in breaking cyclic dependences between references when
   /// they are to be deleted.

mlir/lib/IR/Operation.cpp

if (!llvm::all_of(types,
       failed(verifyCompatibleShapes(types))) {
     return op->emitOpError() << "all non-scalar operands/results must have the "
                                 "same shape and base type";
   }
 
   return success();
 }
 
+/// Check for any values used by operations regions attached to the
+/// specified "IsIsolatedFromAbove" operation defined outside of it.
+LogicalResult OpTrait::impl::verifyIsIsolatedFromAbove(Operation *isolatedOp) {
+  assert(isolatedOp->hasTrait<OpTrait::IsIsolatedFromAbove>() &&
+         "Intended to check IsolatedFromAbove ops");
+
+  // List of regions to analyze.  Each region is processed independently, with
+  // respect to the common `limit` region, so we can look at them in any order.
+  // Therefore, use a simple vector and push/pop back the current region.
+  SmallVector<Region *, 8> pendingRegions;
+  for (auto &region : isolatedOp->getRegions()) {
+    pendingRegions.push_back(&region);
+
+    // Traverse all operations in the region.
+    while (!pendingRegions.empty()) {
+      for (Operation &op : pendingRegions.pop_back_val()->getOps()) {
+        for (Value operand : op.getOperands()) {
+          // operand should be non-null here if the IR is well-formed. But
+          // we don't assert here as this function is called from the verifier
+          // and so could be called on invalid IR.
+          if (!operand)
+            return op.emitOpError("operation's operand is null");
+
+          // Check that any value that is used by an operation is defined in the
+          // same region as either an operation result.
+          auto *operandRegion = operand.getParentRegion();
+          if (!region.isAncestor(operandRegion)) {
+            return op.emitOpError("using value defined outside the region")
+                       .attachNote(isolatedOp->getLoc())
+                   << "required by region isolation constraints";
+          }
+        }
+
+        // Schedule any regions in the operation for further checking.  Don't
+        // recurse into other IsolatedFromAbove ops, because they will check
+        // themselves.
+        if (op.getNumRegions() &&
+            !op.hasTrait<OpTrait::IsIsolatedFromAbove>()) {
+          for (Region &subRegion : op.getRegions())
+            pendingRegions.push_back(&subRegion);
+        }
+      }
+    }
+  }
+
+  return success();
+}
+
 bool OpTrait::hasElementwiseMappableTraits(Operation *op) {
   return op->hasTrait<Elementwise>() && op->hasTrait<Scalarizable>() &&
          op->hasTrait<Vectorizable>() && op->hasTrait<Tensorizable>();
 }
 
 //===----------------------------------------------------------------------===//
 // BinaryOp implementation
 //===----------------------------------------------------------------------===//

mlir/lib/IR/Region.cpp

Block *Region::findAncestorBlockInRegion(Block &block) {
   return currBlock;
 }
 
 void Region::dropAllReferences() {
   for (Block &b : *this)
     b.dropAllReferences();
 }
 
-/// Check if there are any values used by operations in `region` defined
-/// outside its ancestor region `limit`.  That is, given `A{B{C{}}}` with region
-/// `C` and limit `B`, the values defined in `B` can be used but the values
-/// defined in `A` cannot.  Emit errors if `noteLoc` is provided; this location
-/// is used to point to the operation containing the region, the actual error is
-/// reported at the operation with an offending use.
-static bool isIsolatedAbove(Region &region, Region &limit,
-                            Optional<Location> noteLoc) {
-  assert(limit.isAncestor(&region) &&
-         "expected isolation limit to be an ancestor of the given region");
-
-  // List of regions to analyze.  Each region is processed independently, with
-  // respect to the common `limit` region, so we can look at them in any order.
-  // Therefore, use a simple vector and push/pop back the current region.
-  SmallVector<Region *, 8> pendingRegions;
-  pendingRegions.push_back(&region);
-
-  // Traverse all operations in the region.
-  while (!pendingRegions.empty()) {
-    for (Operation &op : pendingRegions.pop_back_val()->getOps()) {
-      for (Value operand : op.getOperands()) {
-        // operand should be non-null here if the IR is well-formed. But
-        // we don't assert here as this function is called from the verifier
-        // and so could be called on invalid IR.
-        if (!operand) {
-          if (noteLoc)
-            op.emitOpError("block's operand not defined").attachNote(noteLoc);
-          return false;
-        }
-
-        // Check that any value that is used by an operation is defined in the
-        // same region as either an operation result or a block argument.
-        if (operand.getParentRegion()->isProperAncestor(&limit)) {
-          if (noteLoc) {
-            op.emitOpError("using value defined outside the region")
-                    .attachNote(noteLoc)
-                << "required by region isolation constraints";
-          }
-          return false;
-        }
-      }
-      // Schedule any regions the operations contain for further checking.
-      pendingRegions.reserve(pendingRegions.size() + op.getNumRegions());
-      for (Region &subRegion : op.getRegions())
-        pendingRegions.push_back(&subRegion);
-    }
-  }
-  return true;
-}
-
-bool Region::isIsolatedFromAbove(Optional<Location> noteLoc) {
-  return isIsolatedAbove(*this, *this, noteLoc);
-}
-
 Region *llvm::ilist_traits<::mlir::Block>::getParentRegion() {
   size_t Offset(
       size_t(&((Region *)nullptr->*Region::getSublistAccess(nullptr))));
   iplist<Block> *Anchor(static_cast<iplist<Block> *>(this));
   return reinterpret_cast<Region *>(reinterpret_cast<char *>(Anchor) - Offset);
 }
 
 /// This is a trait method invoked when a basic block is added to a region.