SmallVector (#1912)

Trying to refactor the code to be simpler and less redundant, I ran into some perf issues that it seems like a small vector, with fixed-size storage and optional additional storage as needed, might help with. This implements that class and uses it in a few places.

This seems to help, I see some 1-2% fewer instructions and cycles in `perf stat`, but it's hard to tell if it really makes a noticeable difference.

7 files changed, 256 insertions, 9 deletions

diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index e2345d303..28c59491a 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -24,7 +24,7 @@ namespace wasm {
 // Given a stack of expressions, checks if the topmost is used as a result.
 // For example, if the parent is a block and the node is before the last position,
 // it is not used.
-bool ExpressionAnalyzer::isResultUsed(std::vector<Expression*> stack, Function* func) {
+bool ExpressionAnalyzer::isResultUsed(ExpressionStack& stack, Function* func) {
   for (int i = int(stack.size()) - 2; i >= 0; i--) {
     auto* curr = stack[i];
     auto* above = stack[i + 1];
@@ -52,7 +52,7 @@ bool ExpressionAnalyzer::isResultUsed(std::vector<Expression*> stack, Function*
 }
 
 // Checks if a value is dropped.
-bool ExpressionAnalyzer::isResultDropped(std::vector<Expression*> stack) {
+bool ExpressionAnalyzer::isResultDropped(ExpressionStack& stack) {
   for (int i = int(stack.size()) - 2; i >= 0; i--) {
     auto* curr = stack[i];
     auto* above = stack[i + 1];
diff --git a/src/ir/utils.h b/src/ir/utils.h
index 85c485552..db437875d 100644
--- a/src/ir/utils.h
+++ b/src/ir/utils.h
@@ -45,10 +45,10 @@ struct ExpressionAnalyzer {
   // Given a stack of expressions, checks if the topmost is used as a result.
   // For example, if the parent is a block and the node is before the last position,
   // it is not used.
-  static bool isResultUsed(std::vector<Expression*> stack, Function* func);
+  static bool isResultUsed(ExpressionStack& stack, Function* func);
 
   // Checks if a value is dropped.
-  static bool isResultDropped(std::vector<Expression*> stack);
+  static bool isResultDropped(ExpressionStack& stack);
 
   // Checks if a break is a simple - no condition, no value, just a plain branching
   static bool isSimple(Break* curr) {
@@ -212,7 +212,7 @@ struct ReFinalizeNode : public OverriddenVisitor<ReFinalizeNode> {
   void visitModule(Module* curr) { WASM_UNREACHABLE(); }
 
   // given a stack of nested expressions, update them all from child to parent
-  static void updateStack(std::vector<Expression*>& expressionStack) {
+  static void updateStack(ExpressionStack& expressionStack) {
     for (int i = int(expressionStack.size()) - 1; i >= 0; i--) {
       auto* curr = expressionStack[i];
       ReFinalizeNode().visit(curr);
diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp
index 91f0f8d4f..a4931f06c 100644
--- a/src/passes/SimplifyLocals.cpp
+++ b/src/passes/SimplifyLocals.cpp
@@ -271,7 +271,7 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
 
   // a full expression stack is used when !allowNesting, so that we can check if
   // a sink would cause nesting
-  std::vector<Expression*> expressionStack;
+  ExpressionStack expressionStack;
 
   static void visitPre(SimplifyLocals<allowTee, allowStructure, allowNesting>* self, Expression** currp) {
     Expression* curr = *currp;
diff --git a/src/support/small_vector.h b/src/support/small_vector.h
new file mode 100644
index 000000000..b919d281b
--- /dev/null
+++ b/src/support/small_vector.h
@@ -0,0 +1,172 @@
+/*
+ * Copyright 2019 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.
+ */
+
+//
+// A vector of elements, which may be small, and uses a fixed space
+// for those small elements.
+//
+
+#ifndef wasm_support_small_vector_h
+#define wasm_support_small_vector_h
+
+#include <array>
+#include <iterator>
+#include <vector>
+
+namespace wasm {
+
+template<typename T, size_t N>
+class SmallVector {
+  // fixed-space storage
+  size_t usedFixed = 0;
+  std::array<T, N> fixed;
+
+  // flexible additional storage
+  std::vector<T> flexible;
+
+public:
+  SmallVector() {}
+
+  T& operator[](size_t i) {
+    if (i < N) {
+      return fixed[i];
+    } else {
+      return flexible[i - N];
+    }
+  }
+
+  T operator[](size_t i) const {
+    if (i < N) {
+      return fixed[i];
+    } else {
+      return flexible[i - N];
+    }
+  }
+
+  void push_back(const T& x) {
+    if (usedFixed < N) {
+      fixed[usedFixed++] = x;
+    } else {
+      flexible.push_back(x);
+    }
+  }
+
+  template <typename... ArgTypes>
+  void emplace_back(ArgTypes &&... Args) {
+    if (usedFixed < N) {
+      new(&fixed[usedFixed++]) T(std::forward<ArgTypes>(Args)...);
+    } else {
+      flexible.emplace_back(std::forward<ArgTypes>(Args)...);
+    }
+  }
+
+  void pop_back() {
+    if (flexible.empty()) {
+      assert(usedFixed > 0);
+      usedFixed--;
+    } else {
+      flexible.pop_back();
+    }
+  }
+
+  T& back() {
+    if (flexible.empty()) {
+      assert(usedFixed > 0);
+      return fixed[usedFixed - 1];
+    } else {
+      return flexible.back();
+    }
+  }
+
+  const T& back() const {
+    if (flexible.empty()) {
+      assert(usedFixed > 0);
+      return fixed[usedFixed - 1];
+    } else {
+      return flexible.back();
+    }
+  }
+
+  size_t size() const {
+    return usedFixed + flexible.size();
+  }
+
+  bool empty() const {
+    return size() == 0;
+  }
+
+  void clear() {
+    usedFixed = 0;
+    flexible.clear();
+  }
+
+  bool operator==(const SmallVector<T, N>& other) const {
+    if (usedFixed != other.usedFixed) return false;
+    for (size_t i = 0; i < usedFixed; i++) {
+      if (fixed[i] != other.fixed[i]) return false;
+    }
+    return flexible == other.flexible;
+  }
+
+  bool operator!=(const SmallVector<T, N>& other) const {
+    return !(*this == other);
+  }
+
+  // iteration
+
+  struct Iterator {
+    typedef T value_type;
+    typedef long difference_type;
+    typedef T& reference;
+
+    const SmallVector<T, N>* parent;
+    size_t index;
+
+    Iterator(const SmallVector<T, N>* parent, size_t index) : parent(parent), index(index) {}
+
+    bool operator!=(const Iterator& other) const {
+      return index != other.index || parent != other.parent;
+    }
+
+    void operator++() {
+      index++;
+    }
+
+    Iterator& operator+=(difference_type off) {
+      index += off;
+      return *this;
+    }
+
+    const Iterator operator+(difference_type off) const {
+      return Iterator(*this) += off;
+    }
+
+    const value_type operator*() const {
+      return (*parent)[index];
+    }
+  };
+
+  Iterator begin() const {
+    return Iterator(static_cast<const SmallVector<T, N>*>(this), 0);
+  }
+  Iterator end() const {
+    return Iterator(static_cast<const SmallVector<T, N>*>(this), size());
+  }
+};
+
+} // namespace wasm
+
+#endif // wasm_support_small_vector_h
diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h
index f569da888..5bd316d89 100644
--- a/src/wasm-traversal.h
+++ b/src/wasm-traversal.h
@@ -28,6 +28,7 @@
 #define wasm_wasm_traversal_h
 
 #include "wasm.h"
+#include "support/small_vector.h"
 #include "support/threads.h"
 
 namespace wasm {
@@ -408,6 +409,7 @@ struct Walker : public VisitorType {
   struct Task {
     TaskFunc func;
     Expression** currp;
+    Task() {}
     Task(TaskFunc func, Expression** currp) : func(func), currp(currp) {}
   };
 
@@ -488,7 +490,7 @@ struct Walker : public VisitorType {
 
 private:
   Expression** replacep = nullptr; // the address of the current node, used to replace it
-  std::vector<Task> stack; // stack of tasks
+  SmallVector<Task, 10> stack; // stack of tasks
   Function* currFunction = nullptr; // current function being processed
   Module* currModule = nullptr; // current module being processed
 };
@@ -716,13 +718,17 @@ struct PostWalker : public Walker<SubType, VisitorType> {
   }
 };
 
+// Stacks of expressions tend to be limited in size (although, sometimes
+// super-nested blocks exist for br_table).
+typedef SmallVector<Expression*, 10> ExpressionStack;
+
 // Traversal with a control-flow stack.
 
 template<typename SubType, typename VisitorType = Visitor<SubType>>
 struct ControlFlowWalker : public PostWalker<SubType, VisitorType> {
   ControlFlowWalker() = default;
 
-  std::vector<Expression*> controlFlowStack; // contains blocks, loops, and ifs
+  ExpressionStack controlFlowStack; // contains blocks, loops, and ifs
 
   // Uses the control flow stack to find the target of a break to a name
   Expression* findBreakTarget(Name name) {
@@ -785,7 +791,7 @@ template<typename SubType, typename VisitorType = Visitor<SubType>>
 struct ExpressionStackWalker : public PostWalker<SubType, VisitorType> {
   ExpressionStackWalker() = default;
 
-  std::vector<Expression*> expressionStack;
+  ExpressionStack expressionStack;
 
   // Uses the control flow stack to find the target of a break to a name
   Expression* findBreakTarget(Name name) {
diff --git a/test/example/small_vector.cpp b/test/example/small_vector.cpp
new file mode 100644
index 000000000..732cbfac3
--- /dev/null
+++ b/test/example/small_vector.cpp
@@ -0,0 +1,68 @@
+#include <iostream>
+#include <cassert>
+
+#include "support/small_vector.h"
+
+using namespace wasm;
+
+template<typename T>
+void test() {
+  {
+    T t;
+    // build up
+    assert(t.empty());
+    assert(t.size() == 0);
+    t.push_back(1);
+    assert(!t.empty());
+    assert(t.size() == 1);
+    t.push_back(2);
+    assert(!t.empty());
+    assert(t.size() == 2);
+    t.push_back(3);
+    assert(!t.empty());
+    // unwind
+    assert(t.size() == 3);
+    assert(t.back() == 3);
+    t.pop_back();
+    assert(t.size() == 2);
+    assert(t.back() == 2);
+    t.pop_back();
+    assert(t.size() == 1);
+    assert(t.back() == 1);
+    t.pop_back();
+    assert(t.size() == 0);
+    assert(t.empty());
+  }
+  {
+    T t;
+    // build up
+    t.push_back(1);
+    t.push_back(2);
+    t.push_back(3);
+    // unwind
+    t.clear();
+    assert(t.size() == 0);
+    assert(t.empty());
+  }
+  {
+    T t, u;
+    assert(t == u);
+    t.push_back(1);
+    assert(t != u);
+    u.push_back(1);
+    assert(t == u);
+    u.pop_back();
+    assert(t != u);
+    u.push_back(2);
+    assert(t != u);
+  }
+}
+
+int main() {
+  test<SmallVector<int, 0>>();
+  test<SmallVector<int, 1>>();
+  test<SmallVector<int, 2>>();
+  test<SmallVector<int, 10>>();
+  std::cout << "ok.\n";
+}
+
diff --git a/test/example/small_vector.txt b/test/example/small_vector.txt
new file mode 100644
index 000000000..90b5016ef
--- /dev/null
+++ b/test/example/small_vector.txt
@@ -0,0 +1 @@
+ok.