[Outlining] StringifyWalker (#5772)

StringifyWalker is a new Walker with UnifiedExpressionVisitor. This walker performs a shallow visit of control-flow (try, if, block, loop) expressions and their simple expression siblings before then visiting the children of each control-flow expression in postorder. As a result, this walker un-nests nested control flow structures, so the expression visit order does not correspond to a normal postorder traversal of the function.

2 files changed, 207 insertions, 0 deletions

diff --git a/src/passes/stringify-walker-impl.h b/src/passes/stringify-walker-impl.h
new file mode 100644
index 000000000..176813179
--- /dev/null
+++ b/src/passes/stringify-walker-impl.h
@@ -0,0 +1,129 @@
+#include "stringify-walker.h"
+
+#ifndef wasm_passes_stringify_walker_impl_h
+#define wasm_passes_stringify_walker_impl_h
+
+namespace wasm {
+
+// This walker supplies its own doWalkModule because it does not make sense to
+// walk anything besides defined functions.
+template<typename SubType>
+inline void StringifyWalker<SubType>::doWalkModule(Module* module) {
+  ModuleUtils::iterDefinedFunctions(
+    *module, [&](Function* func) { this->walkFunction(func); });
+}
+
+template<typename SubType>
+inline void StringifyWalker<SubType>::doWalkFunction(Function* func) {
+  walk(func->body);
+  /*
+   * We add a unique symbol after walking the function body to separate the
+   * string generated from visiting the function body as a single unit from the
+   * subsequent strings that will be generated from visiting the sub-expressions
+   * of the function body. If we did not add this unique symbol and a program
+   * had two functions with the same instructions, we would incorrectly create a
+   * new function with the instructions repeated twice.
+   *
+   * It might be helpful to think of the function body as a block that needs to
+   * be separated from subsequent instructions.
+   */
+  addUniqueSymbol();
+}
+
+template<typename SubType>
+inline void StringifyWalker<SubType>::walk(Expression* curr) {
+  Super::walk(curr);
+  do {
+    addUniqueSymbol();
+    dequeueControlFlow();
+  } while (!controlFlowQueue.empty());
+}
+
+template<typename SubType>
+inline void StringifyWalker<SubType>::scan(SubType* self, Expression** currp) {
+  Expression* curr = *currp;
+  if (Properties::isControlFlowStructure(curr)) {
+    self->controlFlowQueue.push(currp);
+    self->pushTask(doVisitExpression, currp);
+    // The if-condition is a value child consumed by the if control flow, which
+    // makes the if-condition a true sibling rather than part of its contents in
+    // the binary format
+    for (auto*& child : ValueChildIterator(curr)) {
+      Super::scan(self, &child);
+    }
+  } else {
+    Super::scan(self, currp);
+  }
+}
+
+// This dequeueControlFlow is responsible for visiting the children expressions
+// of control flow.
+template<typename SubType> void StringifyWalker<SubType>::dequeueControlFlow() {
+  auto& queue = controlFlowQueue;
+  if (queue.empty()) {
+    return;
+  }
+
+  Expression** currp = queue.front();
+  queue.pop();
+  Expression* curr = *currp;
+
+  // TODO: Issue #5796, Make a ControlChildIterator
+  switch (curr->_id) {
+    case Expression::Id::BlockId: {
+      auto* block = curr->cast<Block>();
+      for (auto& child : block->list) {
+        Super::walk(child);
+      }
+      break;
+    }
+    case Expression::Id::IfId: {
+      auto* iff = curr->cast<If>();
+      Super::walk(iff->ifTrue);
+      if (iff->ifFalse) {
+        addUniqueSymbol();
+        Super::walk(iff->ifFalse);
+      }
+      break;
+    }
+    case Expression::Id::TryId: {
+      auto* tryy = curr->cast<Try>();
+      Super::walk(tryy->body);
+      for (auto& child : tryy->catchBodies) {
+        addUniqueSymbol();
+        Super::walk(child);
+      }
+      break;
+    }
+    case Expression::Id::LoopId: {
+      auto* loop = curr->cast<Loop>();
+      Super::walk(loop->body);
+      break;
+    }
+    default: {
+      assert(Properties::isControlFlowStructure(curr));
+      WASM_UNREACHABLE("unexpected expression");
+    }
+  }
+}
+
+template<typename SubType>
+void StringifyWalker<SubType>::doVisitExpression(SubType* self,
+                                                 Expression** currp) {
+  Expression* curr = *currp;
+  self->visit(curr);
+}
+
+template<typename SubType>
+inline void StringifyWalker<SubType>::addUniqueSymbol() {
+  // TODO: Add the following static_assert when the compilers running our GitHub
+  // actions are updated enough to know that this is a constant condition:
+  // static_assert(&StringifyWalker<SubType>::addUniqueSymbol !=
+  // &SubType::addUniqueSymbol);
+  auto self = static_cast<SubType*>(this);
+  self->addUniqueSymbol();
+}
+
+} // namespace wasm
+
+#endif // wasm_passes_stringify_walker_impl_h
diff --git a/src/passes/stringify-walker.h b/src/passes/stringify-walker.h
new file mode 100644
index 000000000..a7fa02b0b
--- /dev/null
+++ b/src/passes/stringify-walker.h
@@ -0,0 +1,78 @@
+#ifndef wasm_passes_stringify_walker_h
+#define wasm_passes_stringify_walker_h
+
+#include "ir/iteration.h"
+#include "ir/module-utils.h"
+#include "wasm-traversal.h"
+#include <queue>
+
+namespace wasm {
+
+/*
+ * This walker does a normal postorder traversal except that it defers
+ * traversing the contents of control flow structures it encounters. This
+ * effectively un-nests control flow.
+ *
+ * For example, the below (contrived) wat:
+ * 1 : (block
+ * 2 :   (if
+ * 3 :     (i32.const 0)
+ * 4 :     (then (return (i32.const 1)))
+ * 5 :     (else (return (i32.const 0)))))
+ * 6 :   (drop
+ * 7 :     (i32.add
+ * 8 :       (i32.const 20)
+ * 9 :       (i32.const 10)))
+ * 10:   (if
+ * 11:     (i32.const 1)
+ * 12:     (then (return (i32.const 2)))
+ * 14: )
+ * Would have its expressions visited in the following order (based on line
+ * number):
+ * 1, 3, 2, 8, 9, 7, 6, 11, 10, 4, 5, 12
+ *
+ * Of note:
+ *   - The visits to if-True on line 4 and if-False on line 5 are deferred until
+ *     after the rest of the siblings of the if expression on line 2 are visited
+ *   - The if-condition (i32.const 0) on line 3 is visited before the if
+ *     expression on line 2. Similarly, the if-condition (i32.const 1) on line
+ *     11 is visisted before the if expression on line 10.
+ *   - The add (line 7) binary operator's left and right children (lines 8 - 9)
+ *     are visited first as they need to be on the stack before the add
+ *     operation is executed
+ */
+
+template<typename SubType>
+struct StringifyWalker
+  : public PostWalker<SubType, UnifiedExpressionVisitor<SubType>> {
+
+  using Super = PostWalker<SubType, UnifiedExpressionVisitor<SubType>>;
+
+  std::queue<Expression**> controlFlowQueue;
+
+  /*
+   * To initiate the walk, subclasses should call walkModule with a pointer to
+   * the wasm module.
+   *
+   * Member functions addUniqueSymbol and visitExpression are provided as
+   * extension points for subclasses. These functions will be called at
+   * appropriate points during the walk and should be implemented by subclasses.
+   */
+  void visitExpression(Expression* curr);
+  void addUniqueSymbol();
+
+  void doWalkModule(Module* module);
+  void doWalkFunction(Function* func);
+  void walk(Expression* curr);
+  static void scan(SubType* self, Expression** currp);
+  static void doVisitExpression(SubType* self, Expression** currp);
+
+private:
+  void dequeueControlFlow();
+};
+
+} // namespace wasm
+
+#include "stringify-walker-impl.h"
+
+#endif // wasm_passes_stringify_walker_h