[MLIR] Add const iterator and isLegalToHoist to Block

[wsmoses]

Summary

It is desirable to use several implementation-agnostic utilities for control flow graphs (such as loops) implemented in LLVM. This PR adds two common functions (a const iterator, and isLegalToHoist) to better allow MLIR blocks work with such API's

[rriddle]

mlir/include/mlir/IR/Block.h

261

What is the justification here? This seems like the wrong place for this.

[rriddle]

mlir/include/mlir/IR/Block.h

133

This const API goes against the MLIR rationale: https://mlir.llvm.org/docs/Rationale/UsageOfConst/

Can you elaborate on the "why" of this patch? It isn't clear what exactly you are trying to do.

[wsmoses]

mlir/include/mlir/IR/Block.h

261

This function, verbatim, is required by LoopInfo (https://llvm.org/doxygen/LoopInfoImpl_8h_source.html). I'm open to other suggestions.

template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
  assert(!isInvalid() && "Loop not in a valid state!");
  // Keep track of nodes outside the loop branching to the header...
  BlockT *Out = getLoopPredecessor();
  if (!Out)
    return nullptr;
 
  // Make sure we are allowed to hoist instructions into the predecessor.
  if (!Out->isLegalToHoistInto())
    return nullptr;
 
  // Make sure there is only one exit out of the preheader.
  typedef GraphTraits<BlockT *> BlockTraits;
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
  ++SI;
  if (SI != BlockTraits::child_end(Out))
    return nullptr; // Multiple exits from the block, must not be a preheader.
 
  // The predecessor has exactly one successor, so it is a preheader.
  return Out;
}

I have a subsequent PR that uses llvm LoopInfo to create SCF loops out of CFG loops (hence the need for loop analysis)

[rriddle]

mlir/include/mlir/IR/Block.h

261

Have you considered changing the structure of those analyses instead of adding these methods to MLIR (e.g. via traits)? I'm a bit wary of adding stub functions to the core IR to satisfy the needs of a templated analysis.

[wsmoses]

Working around elsewhere.

mlir/include/mlir/IR/Block.h

public:
   //===--------------------------------------------------------------------===//
 
   /// This is the list of operations in the block.
   using OpListType = llvm::iplist<Operation>;
   OpListType &getOperations() { return operations; }
 
   // Iteration over the operations in the block.
   using iterator = OpListType::iterator;
+  using const_iterator = OpListType::const_iterator;
   using reverse_iterator = OpListType::reverse_iterator;
 
   iterator begin() { return operations.begin(); }
   iterator end() { return operations.end(); }
+  const_iterator begin() const { return operations.begin(); }
+  const_iterator end() const { return operations.end(); }
   reverse_iterator rbegin() { return operations.rbegin(); }
   reverse_iterator rend() { return operations.rend(); }
 
   bool empty() { return operations.empty(); }
   void push_back(Operation *op) { operations.push_back(op); }
   void push_front(Operation *op) { operations.push_front(op); }
 
   Operation &back() { return operations.back(); }
public:
   Block *getSuccessor(unsigned i);
 
   // Successor iteration.
   using succ_iterator = SuccessorRange::iterator;
   succ_iterator succ_begin() { return getSuccessors().begin(); }
   succ_iterator succ_end() { return getSuccessors().end(); }
   SuccessorRange getSuccessors() { return SuccessorRange(this); }
 
+  bool isLegalToHoistInto() const;
+
   //===--------------------------------------------------------------------===//
   // Operation Walkers
   //===--------------------------------------------------------------------===//
 
   /// Walk the operations in this block. The callback method is called for each
   /// nested region, block or operation, depending on the callback provided.
   /// Regions, blocks and operations at the same nesting level are visited in
   /// lexicographical order. The walk order for enclosing regions, blocks and

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;
 };
 
+/// This class implements the constant successor iterators for Block.
+class ConstSuccessorRange final
+    : public llvm::detail::indexed_accessor_range_base<
+          ConstSuccessorRange, const BlockOperand *, const Block *,
+          const Block *, const Block *> {
+public:
+  using RangeBaseT::RangeBaseT;
+  ConstSuccessorRange(Block *block);
+  ConstSuccessorRange(Operation *term);
+
+private:
+  /// See `llvm::detail::indexed_accessor_range_base` for details.
+  static const BlockOperand *offset_base(const BlockOperand *object,
+                                         ptrdiff_t index) {
+    return object + index;
+  }
+  /// See `llvm::detail::indexed_accessor_range_base` for details.
+  static const Block *dereference_iterator(const BlockOperand *object,
+                                           ptrdiff_t index) {
+    return object[index].get();
+  }
+
+  /// Allow access to `offset_base` and `dereference_iterator`.
+  friend RangeBaseT;
+};
+
 //===----------------------------------------------------------------------===//
 // BlockRange
 //===----------------------------------------------------------------------===//
 
 /// This class provides an abstraction over the different types of ranges over
 /// Blocks. In many cases, this prevents the need to explicitly materialize a
 /// SmallVector/std::vector. This class should be used in places that are not
 /// suitable for a more derived type (e.g. ArrayRef) or a template range

mlir/lib/IR/Block.cpp

 }
 
 /// See `llvm::detail::indexed_accessor_range_base` for details.
 Block *BlockRange::dereference_iterator(OwnerT object, ptrdiff_t index) {
   if (const auto *operand = object.dyn_cast<BlockOperand *>())
     return operand[index].get();
   return object.dyn_cast<Block *const *>()[index];
 }
+
+bool Block::isLegalToHoistInto() const { return true; }