[mlir][IR] Add a Region::getOps method that returns a range of immediately nested operations

[rriddle]

Summary

This allows for walking the operations nested directly within a region, without traversing nested regions.

[herhut]

Nice!

mlir/include/mlir/IR/Block.h

public:
 
   /// Verifies the current ordering of child operations matches the
   /// validOpOrder flag. Returns false if the order is valid, true otherwise.
   bool verifyOpOrder();
 
   /// Recomputes the ordering of child operations within the block.
   void recomputeOpOrder();
 
-private:
-  /// A utility iterator that filters out operations that are not 'OpT'.
-  template <typename OpT>
-  class op_filter_iterator
-      : public llvm::filter_iterator<Block::iterator, bool (*)(Operation &)> {
-    static bool filter(Operation &op) { return llvm::isa<OpT>(op); }
-
-  public:
-    op_filter_iterator(Block::iterator it, Block::iterator end)
-        : llvm::filter_iterator<Block::iterator, bool (*)(Operation &)>(
-              it, end, &filter) {}
-
-    /// Allow implicit conversion to the underlying block iterator.
-    operator Block::iterator() const { return this->wrapped(); }
-  };
-
-public:
   /// This class provides iteration over the held operations of a block for a
   /// specific operation type.
   template <typename OpT>
-  class op_iterator : public llvm::mapped_iterator<op_filter_iterator<OpT>,
-                                                   OpT (*)(Operation &)> {
-    static OpT unwrap(Operation &op) { return cast<OpT>(op); }
-
-  public:
-    using reference = OpT;
-
-    /// Initializes the iterator to the specified filter iterator.
-    op_iterator(op_filter_iterator<OpT> it)
-        : llvm::mapped_iterator<op_filter_iterator<OpT>, OpT (*)(Operation &)>(
-              it, &unwrap) {}
-
-    /// Allow implicit conversion to the underlying block iterator.
-    operator Block::iterator() const { return this->wrapped(); }
-  };
+  using op_iterator = detail::op_iterator<OpT, iterator>;
 
   /// Return an iterator range over the operations within this block that are of
   /// 'OpT'.
   template <typename OpT> iterator_range<op_iterator<OpT>> getOps() {
     auto endIt = end();
-    return {op_filter_iterator<OpT>(begin(), endIt),
-            op_filter_iterator<OpT>(endIt, endIt)};
+    return {detail::op_filter_iterator<OpT, iterator>(begin(), endIt),
+            detail::op_filter_iterator<OpT, iterator>(endIt, endIt)};
   }
   template <typename OpT> op_iterator<OpT> op_begin() {
-    return op_filter_iterator<OpT>(begin(), end());
+    return detail::op_filter_iterator<OpT, iterator>(begin(), end());
   }
   template <typename OpT> op_iterator<OpT> op_end() {
-    return op_filter_iterator<OpT>(end(), end());
+    return detail::op_filter_iterator<OpT, iterator>(end(), end());
   }
 
   /// Return an iterator range over the operation within this block excluding
   /// the terminator operation at the end.
   iterator_range<iterator> without_terminator() {
     if (begin() == end())
       return {begin(), end()};
     auto endIt = --end();

mlir/include/mlir/IR/BlockSupport.h

private:
   static Block *dereference_iterator(BlockOperand *object, ptrdiff_t index) {
     return object[index].get();
   }
 
   /// Allow access to `offset_base` and `dereference_iterator`.
   friend RangeBaseT;
 };
 
+//===----------------------------------------------------------------------===//
+// Operation Iterators
+//===----------------------------------------------------------------------===//
+
+namespace detail {
+/// A utility iterator that filters out operations that are not 'OpT'.
+template <typename OpT, typename IteratorT>
+class op_filter_iterator
+    : public llvm::filter_iterator<IteratorT, bool (*)(Operation &)> {
+  static bool filter(Operation &op) { return llvm::isa<OpT>(op); }
+
+public:
+  op_filter_iterator(IteratorT it, IteratorT end)
+      : llvm::filter_iterator<IteratorT, bool (*)(Operation &)>(it, end,
+                                                                &filter) {}
+
+  /// Allow implicit conversion to the underlying iterator.
+  operator IteratorT() const { return this->wrapped(); }
+};
+
+/// This class provides iteration over the held operations of a block for a
+/// specific operation type.
+template <typename OpT, typename IteratorT>
+class op_iterator
+    : public llvm::mapped_iterator<op_filter_iterator<OpT, IteratorT>,
+                                   OpT (*)(Operation &)> {
+  static OpT unwrap(Operation &op) { return cast<OpT>(op); }
+
+public:
+  using reference = OpT;
+
+  /// Initializes the iterator to the specified filter iterator.
+  op_iterator(op_filter_iterator<OpT, IteratorT> it)
+      : llvm::mapped_iterator<op_filter_iterator<OpT, IteratorT>,
+                              OpT (*)(Operation &)>(it, &unwrap) {}
+
+  /// Allow implicit conversion to the underlying block iterator.
+  operator IteratorT() const { return this->wrapped(); }
+};
+} // end namespace detail
 } // end namespace mlir
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
 // ilist_traits for Operation
 //===----------------------------------------------------------------------===//
 

mlir/include/mlir/IR/Function.h

 
 /// FuncOp represents a function, or an operation containing one region that
 /// forms a CFG(Control Flow Graph). The region of a function is not allowed to
 /// implicitly capture global values, and all external references must use
 /// Function arguments or attributes that establish a symbolic connection(e.g.
 /// symbols referenced by name via a string attribute).
 class FuncOp
     : public Op<FuncOp, OpTrait::ZeroOperands, OpTrait::ZeroResult,
-                OpTrait::IsIsolatedFromAbove, OpTrait::FunctionLike,
-                OpTrait::AutomaticAllocationScope, OpTrait::PolyhedralScope,
-                CallableOpInterface::Trait, SymbolOpInterface::Trait> {
+                OpTrait::OneRegion, OpTrait::IsIsolatedFromAbove,
+                OpTrait::FunctionLike, OpTrait::AutomaticAllocationScope,
+                OpTrait::PolyhedralScope, CallableOpInterface::Trait,
+                SymbolOpInterface::Trait> {
 public:
   using Op::Op;
   using Op::print;
 
   static StringRef getOperationName() { return "func"; }
 
   static FuncOp create(Location location, StringRef name, FunctionType type,
                        ArrayRef<NamedAttribute> attrs = {});

mlir/include/mlir/IR/OpDefinition.h

 } // end namespace detail
 
 /// This class provides APIs for ops that are known to have a single region.
 template <typename ConcreteType>
 class OneRegion : public TraitBase<ConcreteType, OneRegion> {
 public:
   Region &getRegion() { return this->getOperation()->getRegion(0); }
 
+  /// Returns a range of operations within the region of this operation.
+  auto getOps() { return getRegion().getOps(); }
+  template <typename OpT>
+  auto getOps() {
+    return getRegion().template getOps<OpT>();
+  }
+
   static LogicalResult verifyTrait(Operation *op) {
     return impl::verifyOneRegion(op);
   }
 };
 
 /// This class provides the API for ops that are known to have a specified
 /// number of regions.
 template <unsigned N> class NRegions {

mlir/include/mlir/IR/Region.h

public:
   /// Return the context this region is inserted in.  The region must have a
   /// valid parent container.
   MLIRContext *getContext();
 
   /// Return a location for this region. This is the location attached to the
   /// parent container. The region must have a valid parent container.
   Location getLoc();
 
+  //===--------------------------------------------------------------------===//
+  // Block list management
+  //===--------------------------------------------------------------------===//
+
   using BlockListType = llvm::iplist<Block>;
   BlockListType &getBlocks() { return blocks; }
 
   // Iteration over the blocks in the region.
   using iterator = BlockListType::iterator;
   using reverse_iterator = BlockListType::reverse_iterator;
 
   iterator begin() { return blocks.begin(); }
   iterator end() { return blocks.end(); }
   reverse_iterator rbegin() { return blocks.rbegin(); }
   reverse_iterator rend() { return blocks.rend(); }
 
   bool empty() { return blocks.empty(); }
   void push_back(Block *block) { blocks.push_back(block); }
   void push_front(Block *block) { blocks.push_front(block); }
 
   Block &back() { return blocks.back(); }
   Block &front() { return blocks.front(); }
 
   /// getSublistAccess() - Returns pointer to member of region.
   static BlockListType Region::*getSublistAccess(Block *) {
     return &Region::blocks;
   }
 
+  //===--------------------------------------------------------------------===//
+  // Operation list utilities
+  //===--------------------------------------------------------------------===//
+
+  /// This class provides iteration over the held operations of blocks directly
+  /// within a region.
+  class OpIterator final
+      : public llvm::iterator_facade_base<OpIterator, std::forward_iterator_tag,
+                                          Operation> {
+  public:
+    /// Initialize OpIterator for a region, specify `end` to return the iterator
+    /// to last operation.
+    explicit OpIterator(Region *region, bool end = false);
+
+    using llvm::iterator_facade_base<OpIterator, std::forward_iterator_tag,
+                                     Operation>::operator++;
+    OpIterator &operator++();
+    Operation *operator->() const { return &*operation; }
+    Operation &operator*() const { return *operation; }
+
+    /// Compare this iterator with another.
+    bool operator==(const OpIterator &rhs) const {
+      return operation == rhs.operation;
+    }
+    bool operator!=(const OpIterator &rhs) const { return !(*this == rhs); }
+
+  private:
+    void skipOverBlocksWithNoOps();
+
+    /// The region whose operations are being iterated over.
+    Region *region;
+    /// The block of 'region' whose operations are being iterated over.
+    Region::iterator block;
+    /// The current operation within 'block'.
+    Block::iterator operation;
+  };
+
+  /// This class provides iteration over the held operations of a region for a
+  /// specific operation type.
+  template <typename OpT>
+  using op_iterator = detail::op_iterator<OpT, OpIterator>;
+
+  /// 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() {
+    return detail::op_filter_iterator<OpT, OpIterator>(op_begin(), 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() {
+    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
public:
   /// 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.
   void dropAllReferences();
 
+  //===--------------------------------------------------------------------===//
+  // Operation Walkers
+  //===--------------------------------------------------------------------===//
+
   /// Walk the operations in this region in postorder, calling the callback for
   /// each operation. This method is invoked for void-returning callbacks.
   /// See Operation::walk for more details.
   template <typename FnT, typename RetT = detail::walkResultType<FnT>>
   typename std::enable_if<std::is_same<RetT, void>::value, RetT>::type
   walk(FnT &&callback) {
     for (auto &block : *this)
       block.walk(callback);
   }
 
   /// Walk the operations in this region in postorder, calling the callback for
   /// each operation. This method is invoked for interruptible callbacks.
   /// See Operation::walk for more details.
   template <typename FnT, typename RetT = detail::walkResultType<FnT>>
   typename std::enable_if<std::is_same<RetT, WalkResult>::value, RetT>::type
   walk(FnT &&callback) {
     for (auto &block : *this)
       if (block.walk(callback).wasInterrupted())
         return WalkResult::interrupt();
     return WalkResult::advance();
   }
 
+  //===--------------------------------------------------------------------===//
+  // CFG view utilities
+  //===--------------------------------------------------------------------===//
+
   /// Displays the CFG in a window. This is for use from the debugger and
   /// depends on Graphviz to generate the graph.
   /// This function is defined in ViewRegionGraph and only works with that
   /// target linked.
   void viewGraph(const Twine &regionName);
   void viewGraph();
 
 private:

mlir/lib/Analysis/CallGraph.cpp

static void computeCallGraph(Operation *op, CallGraph &cg,
   if (CallableOpInterface callable = dyn_cast<CallableOpInterface>(op)) {
     if (auto *callableRegion = callable.getCallableRegion())
       parentNode = cg.getOrAddNode(callableRegion, parentNode);
     else
       return;
   }
 
   for (Region &region : op->getRegions())
-    for (Block &block : region)
-      for (Operation &nested : block)
-        computeCallGraph(&nested, cg, parentNode, resolveCalls);
+    for (Operation &nested : region.getOps())
 }
 
 CallGraph::CallGraph(Operation *op) : externalNode(/*callableRegion=*/nullptr) {
   // Make two passes over the graph, one to compute the callables and one to
   // resolve the calls. We split these up as we may have nested callable objects
   // that need to be reserved before the calls.
   computeCallGraph(op, *this, /*parentNode=*/nullptr, /*resolveCalls=*/false);
   computeCallGraph(op, *this, /*parentNode=*/nullptr, /*resolveCalls=*/true);

mlir/lib/Conversion/LoopsToGPU/LoopsToGPUPass.cpp

 struct ForLoopMapper : public ConvertSimpleLoopsToGPUBase<ForLoopMapper> {
   ForLoopMapper() = default;
   ForLoopMapper(unsigned numBlockDims, unsigned numThreadDims) {
     this->numBlockDims = numBlockDims;
     this->numThreadDims = numThreadDims;
   }
 
   void runOnFunction() override {
-    for (Block &block : getFunction())
-      for (Operation &op : llvm::make_early_inc_range(block)) {
-        if (auto forOp = dyn_cast<AffineForOp>(&op)) {
-          if (failed(convertAffineLoopNestToGPULaunch(forOp, numBlockDims,
-                                                      numThreadDims)))
-            signalPassFailure();
-        } else if (auto forOp = dyn_cast<ForOp>(&op)) {
-          if (failed(convertLoopNestToGPULaunch(forOp, numBlockDims,
-                                                numThreadDims)))
-            signalPassFailure();
-        }
-      }
+    for (Operation &op : llvm::make_early_inc_range(getFunction().getOps())) {
+        if (failed(
+                convertLoopNestToGPULaunch(forOp, numBlockDims, numThreadDims)))
   }
 };
 
 // A pass that traverses top-level loops in the function and convertes them to
 // GPU launch operations. The top-level loops itself does not have to be
 // perfectly nested. The only requirement is that there be as many perfectly
 // nested loops as the size of `numWorkGroups`. Within these any loop nest has
 // to be perfectly nested upto depth equal to size of `workGroupSize`.
for (auto val : numWorkGroups) {
           funcOp.getLoc(), builder.getIntegerAttr(builder.getIndexType(), val));
       numWorkGroupsVal.push_back(constOp);
     }
     for (auto val : workGroupSize) {
       auto constOp = builder.create<ConstantOp>(
           funcOp.getLoc(), builder.getIntegerAttr(builder.getIndexType(), val));
       workGroupSizeVal.push_back(constOp);
     }
-    for (Block &block : getFunction()) {
-      for (Operation &op : llvm::make_early_inc_range(block)) {
-        if (auto forOp = dyn_cast<ForOp>(&op)) {
-          if (failed(convertLoopToGPULaunch(forOp, numWorkGroupsVal,
-                                            workGroupSizeVal))) {
-            return signalPassFailure();
-          }
-        }
-      }
-    }
-  }
+    for (ForOp forOp : llvm::make_early_inc_range(funcOp.getOps<ForOp>())) {
 };
 
 struct ParallelLoopToGpuPass
     : public ConvertParallelLoopToGpuBase<ParallelLoopToGpuPass> {
   void runOnOperation() override {
     OwningRewritePatternList patterns;
     populateParallelLoopToGPUPatterns(patterns, &getContext());
     ConversionTarget target(getContext());

mlir/lib/IR/Region.cpp

static bool isIsolatedAbove(Region &region, Region &limit,
   // 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 (Block &block : *pendingRegions.pop_back_val()) {
-      for (Operation &op : block) {
-        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;
-          }
+    for (Operation &op : pendingRegions.pop_back_val()->getOps()) {
 
-          // 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() {
if (curParent == otherList.getParentRegion())
     return;
 
   // Update the 'parent' member of each Block.
   for (; first != last; ++first)
     first->parentValidOpOrderPair.setPointer(curParent);
 }
 
 //===----------------------------------------------------------------------===//
+// Region::OpIterator
+//===----------------------------------------------------------------------===//
+
+Region::OpIterator::OpIterator(Region *region, bool end)
+    : region(region), block(end ? region->end() : region->begin()) {
+  if (!region->empty())
+    skipOverBlocksWithNoOps();
+}
+
+Region::OpIterator &Region::OpIterator::operator++() {
+  // We increment over operations, if we reach the last use then move to next
+  // block.
+  if (operation != block->end())
+    ++operation;
+  if (operation == block->end()) {
+    ++block;
+    skipOverBlocksWithNoOps();
+  }
+  return *this;
+}
+
+void Region::OpIterator::skipOverBlocksWithNoOps() {
+  while (block != region->end() && block->empty())
+    ++block;
+
+  // If we are at the last block, then set the operation to first operation of
+  // next block (sentinel value used for end).
+  if (block == region->end())
+    operation = {};
+  else
+    operation = block->begin();
+}
+
+//===----------------------------------------------------------------------===//
 // RegionRange
 //===----------------------------------------------------------------------===//
 
 RegionRange::RegionRange(MutableArrayRef<Region> regions)
     : RegionRange(regions.data(), regions.size()) {}
 RegionRange::RegionRange(ArrayRef<std::unique_ptr<Region>> regions)
     : RegionRange(regions.data(), regions.size()) {}
 

mlir/lib/IR/SymbolTable.cpp

 /// regions of 'symbolTableOp'. 'symbolTableOp' is required to be an operation
 /// with the 'OpTrait::SymbolTable' trait. Returns nullptr if no valid symbol
 /// was found.
 Operation *SymbolTable::lookupSymbolIn(Operation *symbolTableOp,
                                        StringRef symbol) {
   assert(symbolTableOp->hasTrait<OpTrait::SymbolTable>());
 
   // Look for a symbol with the given name.
-  for (auto &block : symbolTableOp->getRegion(0)) {
-    for (auto &op : block)
-      if (getNameIfSymbol(&op) == symbol)
-        return &op;
-  }
+  for (auto &op : symbolTableOp->getRegion(0).front().without_terminator())
   return nullptr;
 }
 Operation *SymbolTable::lookupSymbolIn(Operation *symbolTableOp,
                                        SymbolRefAttr symbol) {
   SmallVector<Operation *, 4> resolvedSymbols;
   if (failed(lookupSymbolIn(symbolTableOp, symbol, resolvedSymbols)))
     return nullptr;
   return resolvedSymbols.back();

 /// Walk all of the uses, for any symbol, that are nested within the given
 /// regions, invoking the provided callback for each. This does not traverse
 /// into any nested symbol tables.
 static Optional<WalkResult> walkSymbolUses(
     MutableArrayRef<Region> regions,
     function_ref<WalkResult(SymbolTable::SymbolUse, ArrayRef<int>)> callback) {
   SmallVector<Region *, 1> worklist(llvm::make_pointer_range(regions));
   while (!worklist.empty()) {
-    for (Block &block : *worklist.pop_back_val()) {
-      for (Operation &op : block) {
-        if (walkSymbolRefs(&op, callback).wasInterrupted())
-          return WalkResult::interrupt();
+    for (Operation &op : worklist.pop_back_val()->getOps()) {
 
-        // Check that this isn't a potentially unknown symbol table.
-        if (isPotentiallyUnknownSymbolTable(&op))
-          return llvm::None;
 
-        // If this op defines a new symbol table scope, we can't traverse. Any
-        // symbol references nested within 'op' are different semantically.
-        if (!op.hasTrait<OpTrait::SymbolTable>()) {
-          for (Region &region : op.getRegions())
-            worklist.push_back(&region);
-        }
-      }
-    }
-  }
   return WalkResult::advance();
 }
 /// Walk all of the uses, for any symbol, that are nested within the given
 /// operation 'from', invoking the provided callback for each. This does not
 /// traverse into any nested symbol tables.
 static Optional<WalkResult> walkSymbolUses(
     Operation *from,
     function_ref<WalkResult(SymbolTable::SymbolUse, ArrayRef<int>)> callback) {

mlir/lib/Transforms/Inliner.cpp

 } // end anonymous namespace
 
 CGUseList::CGUseList(Operation *op, CallGraph &cg) {
   /// A set of callgraph nodes that are always known to be live during inlining.
   DenseMap<Attribute, CallGraphNode *> alwaysLiveNodes;
 
   // Walk each of the symbol tables looking for discardable callgraph nodes.
   auto walkFn = [&](Operation *symbolTableOp, bool allUsesVisible) {
-    for (Block &block : symbolTableOp->getRegion(0)) {
-      for (Operation &op : block) {
-        // If this is a callgraph operation, check to see if it is discardable.
-        if (auto callable = dyn_cast<CallableOpInterface>(&op)) {
-          if (auto *node = cg.lookupNode(callable.getCallableRegion())) {
-            SymbolOpInterface symbol = dyn_cast<SymbolOpInterface>(&op);
-            if (symbol && (allUsesVisible || symbol.isPrivate()) &&
-                symbol.canDiscardOnUseEmpty()) {
-              discardableSymNodeUses.try_emplace(node, 0);
-            }
-            continue;
-          }
-        }
-        // Otherwise, check for any referenced nodes. These will be always-live.
-        walkReferencedSymbolNodes(&op, cg, alwaysLiveNodes,
-                                  [](CallGraphNode *, Operation *) {});
-      }
-    }
+    for (Operation &op : symbolTableOp->getRegion(0).getOps()) {
   };
   SymbolTable::walkSymbolTables(op, /*allSymUsesVisible=*/!op->getBlock(),
                                 walkFn);
 
   // Drop the use information for any discardable nodes that are always live.
   for (auto &it : alwaysLiveNodes)
     discardableSymNodeUses.erase(it.second);