[analysis] Make it easier to implement a transfer function (#6077)

Combine the `transfer` and `getDependents` methods of a transfer function so
that a transfer function only has to implement `transfer`, which now returns a
range of basic blocks that may need to be re-analyzed.

To make it easier to implement the returned basic block range, change the
requirement so that it provides iterators to `const BasicBlock*` rather than
`BasicBlock`. This allows us to entirely remove cfg-impl.h.

6 files changed, 28 insertions, 190 deletions

diff --git a/src/analysis/cfg-impl.h b/src/analysis/cfg-impl.h
deleted file mode 100644
index 861a4471e..000000000
--- a/src/analysis/cfg-impl.h
+++ /dev/null
@@ -1,149 +0,0 @@
-/*
- * Copyright 2023 WebAssembly Community Group participants
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef wasm_analysis_cfg_impl_h
-#define wasm_analysis_cfg_impl_h
-
-#include "cfg.h"
-
-namespace wasm::analysis {
-
-// An iterator over a sequence of contiguous pointers (represented as a pointer
-// to a pointer in the sequence) that dereferences the pointed-to pointer.
-// TODO: Move this to its own public header if there is ever another use for it.
-template<typename T> struct _indirect_ptr_iterator {
-  using iterator_category = std::random_access_iterator_tag;
-  using value_type = T;
-  using difference_type = off_t;
-  using reference = const T&;
-  using pointer = const T*;
-
-  const T* const* ptr;
-
-  const T& operator*() const { return **ptr; }
-
-  const T& operator[](int n) const { return **(ptr + n); }
-
-  _indirect_ptr_iterator& operator+=(int n) {
-    ptr += n;
-    return *this;
-  }
-
-  _indirect_ptr_iterator& operator-=(int n) {
-    ptr -= n;
-    return *this;
-  }
-
-  _indirect_ptr_iterator& operator++() { return *this += 1; }
-
-  _indirect_ptr_iterator operator++(int) {
-    _indirect_ptr_iterator it = *this;
-    ++(*this);
-    return it;
-  }
-
-  _indirect_ptr_iterator& operator--() { return *this -= 1; }
-
-  _indirect_ptr_iterator operator--(int) {
-    _indirect_ptr_iterator it = *this;
-    --(*this);
-    return it;
-  }
-
-  _indirect_ptr_iterator operator+(int n) const {
-    _indirect_ptr_iterator it = *this;
-    it += n;
-    return it;
-  }
-
-  _indirect_ptr_iterator operator-(int n) const {
-    _indirect_ptr_iterator it = *this;
-    it -= n;
-    return it;
-  }
-
-  off_t operator-(const _indirect_ptr_iterator& other) const {
-    return ptr - other.ptr;
-  }
-
-  bool operator==(const _indirect_ptr_iterator& other) const {
-    return ptr == other.ptr;
-  }
-
-  bool operator!=(const _indirect_ptr_iterator& other) const {
-    return !(*this == other);
-  }
-
-  bool operator<(const _indirect_ptr_iterator& other) const {
-    return ptr < other.ptr;
-  }
-
-  bool operator>(const _indirect_ptr_iterator& other) const {
-    return ptr > other.ptr;
-  }
-
-  bool operator<=(const _indirect_ptr_iterator& other) const {
-    return ptr <= other.ptr;
-  }
-
-  bool operator>=(const _indirect_ptr_iterator& other) const {
-    return ptr >= other.ptr;
-  }
-
-  friend _indirect_ptr_iterator operator+(off_t n,
-                                          const _indirect_ptr_iterator& it) {
-    return it + n;
-  }
-};
-
-#if __cplusplus >= 202002L
-static_assert(std::random_access_iterator<_indirect_ptr_iterator<int>>);
-#endif
-
-template<typename T>
-_indirect_ptr_iterator<T> operator+(int n,
-                                    const _indirect_ptr_iterator<T>& it) {
-  return it + n;
-}
-
-// Wraps a vector of pointers and provides dereferencing iterators for it.
-template<typename T> struct _indirect_ptr_vec {
-  using iterator = _indirect_ptr_iterator<T>;
-
-  const std::vector<T*>& vec;
-
-  _indirect_ptr_vec(const std::vector<T*>& vec) : vec(vec) {}
-
-  iterator begin() const { return {&vec.data()[0]}; }
-  iterator end() const { return {&vec.data()[vec.size()]}; }
-};
-
-struct BasicBlock::BasicBlockIterable : _indirect_ptr_vec<BasicBlock> {
-  BasicBlockIterable(const std::vector<BasicBlock*>& blocks)
-    : _indirect_ptr_vec(blocks) {}
-};
-
-inline BasicBlock::BasicBlockIterable BasicBlock::preds() const {
-  return BasicBlockIterable(predecessors);
-}
-
-inline BasicBlock::BasicBlockIterable BasicBlock::succs() const {
-  return BasicBlockIterable(successors);
-}
-
-} // namespace wasm::analysis
-
-#endif // wasm_analysis_cfg_impl_h
diff --git a/src/analysis/cfg.cpp b/src/analysis/cfg.cpp
index 0d651526b..ba638ec5a 100644
--- a/src/analysis/cfg.cpp
+++ b/src/analysis/cfg.cpp
@@ -80,19 +80,19 @@ void CFG::print(std::ostream& os, Module* wasm) const {
 
 void BasicBlock::print(std::ostream& os, Module* wasm, size_t start) const {
   os << ";; preds: [";
-  for (auto& pred : preds()) {
-    if (&pred != &*preds().begin()) {
+  for (const auto* pred : preds()) {
+    if (pred != *preds().begin()) {
       os << ", ";
     }
-    os << pred.index;
+    os << pred->index;
   }
   os << "], succs: [";
 
-  for (auto& succ : succs()) {
-    if (&succ != &*succs().begin()) {
+  for (const auto* succ : succs()) {
+    if (succ != *succs().begin()) {
       os << ", ";
     }
-    os << succ.index;
+    os << succ->index;
   }
   os << "]\n";
 
diff --git a/src/analysis/cfg.h b/src/analysis/cfg.h
index cd1a60815..baabe9591 100644
--- a/src/analysis/cfg.h
+++ b/src/analysis/cfg.h
@@ -44,10 +44,8 @@ struct BasicBlock {
   reverse_iterator rbegin() const { return insts.rbegin(); }
   reverse_iterator rend() const { return insts.rend(); }
 
-  // Iterables for predecessor and successor blocks.
-  struct BasicBlockIterable;
-  BasicBlockIterable preds() const;
-  BasicBlockIterable succs() const;
+  const std::vector<const BasicBlock*>& preds() const { return predecessors; }
+  const std::vector<const BasicBlock*>& succs() const { return successors; }
 
   void print(std::ostream& os, Module* wasm = nullptr, size_t start = 0) const;
 
@@ -56,8 +54,8 @@ struct BasicBlock {
 private:
   Index index;
   std::vector<Expression*> insts;
-  std::vector<BasicBlock*> predecessors;
-  std::vector<BasicBlock*> successors;
+  std::vector<const BasicBlock*> predecessors;
+  std::vector<const BasicBlock*> successors;
 
   friend CFG;
 };
@@ -109,6 +107,4 @@ private:
 
 } // namespace wasm::analysis
 
-#include "cfg-impl.h"
-
 #endif // wasm_analysis_cfg_h
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index 1f8182908..fc2fbf706 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -37,16 +37,13 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
     Index i = worklist.pop();
 
     // Apply the transfer function to the input state to compute the output
-    // state for the block.
+    // state, then propagate the output state to the dependent blocks.
     auto state = states[i];
-    txfn.transfer(cfg[i], state);
-
-    // Propagate state to the dependent blocks.
-    for (auto& dep : txfn.getDependents(cfg[i])) {
+    for (const auto* dep : txfn.transfer(cfg[i], state)) {
       // If the input state for the dependent block changes, we need to
       // re-analyze it.
-      if (lattice.join(states[dep.getIndex()], state)) {
-        worklist.push(dep.getIndex());
+      if (lattice.join(states[dep->getIndex()], state)) {
+        worklist.push(dep->getIndex());
       }
     }
   }
@@ -73,11 +70,11 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::print(std::ostream& os) {
     os << "Input State: ";
     states[i].print(os);
     for (auto& pred : cfg[i].preds()) {
-      os << " " << pred.getIndex();
+      os << " " << pred->getIndex();
     }
     os << std::endl << "Successors:";
     for (auto& succ : cfg[i].succs()) {
-      os << " " << succ.getIndex();
+      os << " " << succ->getIndex();
     }
     os << "\n";
     txfn.print(os, cfg[i], states[i]);
diff --git a/src/analysis/transfer-function.h b/src/analysis/transfer-function.h
index 3f99f2f08..58d2033ef 100644
--- a/src/analysis/transfer-function.h
+++ b/src/analysis/transfer-function.h
@@ -32,16 +32,15 @@ namespace wasm::analysis {
 template<typename T>
 concept BasicBlockInputRange =
   std::ranges::input_range<T> &&
-  std::is_same<std::ranges::range_value_t<T>, BasicBlock>::value;
+  std::is_same<std::ranges::range_value_t<T>, const BasicBlock*>::value;
 
 template<typename TxFn, typename L>
 concept TransferFunctionImpl = requires(
   TxFn& txfn, const CFG& cfg, const BasicBlock& bb, typename L::Element& elem) {
   // Apply the transfer function to update a lattice element with information
-  // from a basic block.
-  { txfn.transfer(bb, elem) } noexcept -> std::same_as<void>;
-  // Get a range over the basic blocks that depend on the given block.
-  { txfn.getDependents(bb) } noexcept -> BasicBlockInputRange;
+  // from a basic block. Return an object that can be iterated over to get the
+  // basic blocks that may need to be re-analyzed.
+  { txfn.transfer(bb, elem) } noexcept -> BasicBlockInputRange;
 };
 
 #define TransferFunction TransferFunctionImpl<L>
diff --git a/src/analysis/visitor-transfer-function.h b/src/analysis/visitor-transfer-function.h
index d77fc9fcd..6e449baf9 100644
--- a/src/analysis/visitor-transfer-function.h
+++ b/src/analysis/visitor-transfer-function.h
@@ -34,22 +34,11 @@ protected:
   bool collectingResults = false;
 
 public:
-  // Returns an iterable to all the BasicBlocks which depend on currBlock for
-  // information.
-  BasicBlock::BasicBlockIterable
-  getDependents(const BasicBlock& currBlock) noexcept {
-    if constexpr (Direction == AnalysisDirection::Backward) {
-      return currBlock.preds();
-    } else {
-      return currBlock.succs();
-    }
-  }
-
   // Executes the transfer function on all the expressions of the corresponding
   // CFG node, starting with the node's input state, and changes the input state
   // to the final output state of the node in place.
-  void transfer(const BasicBlock& bb,
-                typename L::Element& inputState) noexcept {
+  const std::vector<const BasicBlock*>&
+  transfer(const BasicBlock& bb, typename L::Element& inputState) noexcept {
     // If the block is empty, we propagate the state by inputState =
     // outputState.
 
@@ -64,6 +53,12 @@ public:
       }
     }
     currState = nullptr;
+
+    if constexpr (Direction == AnalysisDirection::Backward) {
+      return bb.preds();
+    } else {
+      return bb.succs();
+    }
   }
 
   // This is for collecting results after solving an analysis. Implemented in