Optimize LocalCSE hash computations using a stack. NFC (#4091)

Before, we'd compute the hash of a child, then store that in a map, then
the parent would find the child's hash in the map using the pointer to the
child. But as we do a simple postorder walk, we can use a stack, and
avoid hashing the child pointers.

This makes it 10% faster or so.

2 files changed, 44 insertions, 8 deletions

diff --git a/src/ir/properties.h b/src/ir/properties.h
index 4909dfbc8..dbf2715ef 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -310,6 +310,41 @@ inline Expression* getFallthrough(Expression* curr,
   }
 }
 
+inline Index getNumChildren(Expression* curr) {
+  Index ret = 0;
+
+#define DELEGATE_ID curr->_id
+
+#define DELEGATE_START(id)                                                     \
+  auto* cast = curr->cast<id>();                                               \
+  WASM_UNUSED(cast);
+
+#define DELEGATE_GET_FIELD(id, name) cast->name
+
+#define DELEGATE_FIELD_CHILD(id, name) ret++;
+
+#define DELEGATE_FIELD_OPTIONAL_CHILD(id, name)                                \
+  if (cast->name) {                                                            \
+    ret++;                                                                     \
+  }
+
+#define DELEGATE_FIELD_INT(id, name)
+#define DELEGATE_FIELD_INT_ARRAY(id, name)
+#define DELEGATE_FIELD_LITERAL(id, name)
+#define DELEGATE_FIELD_NAME(id, name)
+#define DELEGATE_FIELD_NAME_VECTOR(id, name)
+#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, name)
+#define DELEGATE_FIELD_SCOPE_NAME_USE(id, name)
+#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, name)
+#define DELEGATE_FIELD_SIGNATURE(id, name)
+#define DELEGATE_FIELD_TYPE(id, name)
+#define DELEGATE_FIELD_ADDRESS(id, name)
+
+#include "wasm-delegations-fields.def"
+
+  return ret;
+}
+
 // Returns whether the resulting value here must fall through without being
 // modified. For example, a tee always does so. That is, this returns false if
 // and only if the return value may have some computation performed on it to
diff --git a/src/passes/LocalCSE.cpp b/src/passes/LocalCSE.cpp
index 1ae77d155..a233517c5 100644
--- a/src/passes/LocalCSE.cpp
+++ b/src/passes/LocalCSE.cpp
@@ -219,9 +219,9 @@ struct Scanner
   // original expression that we request from.
   HashedExprs activeExprs;
 
-  // Hash values of all active expressions. We store these so that we do not end
-  // up recomputing hashes of children in an N^2 manner.
-  std::unordered_map<Expression*, size_t> activeHashes;
+  // Stack of hash values of all active expressions. We store these so that we
+  // do not end up recomputing hashes of children in an N^2 manner.
+  SmallVector<size_t, 10> activeHashes;
 
   static void doNoteNonLinear(Scanner* self, Expression** currp) {
     // We are starting a new basic block. Forget all the currently-hashed
@@ -240,17 +240,18 @@ struct Scanner
     //
     // Note that we must compute the hash first, as we need it even for things
     // that are not isRelevant() (if they are the children of a relevant thing).
+    auto numChildren = Properties::getNumChildren(curr);
     auto hash = ExpressionAnalyzer::shallowHash(curr);
-    for (auto* child : ChildIterator(curr)) {
-      auto iter = activeHashes.find(child);
-      if (iter == activeHashes.end()) {
+    for (Index i = 0; i < numChildren; i++) {
+      if (activeHashes.empty()) {
         // The child was in another block, so this expression cannot be
         // optimized.
         return;
       }
-      hash_combine(hash, iter->second);
+      hash_combine(hash, activeHashes.back());
+      activeHashes.pop_back();
     }
-    activeHashes[curr] = hash;
+    activeHashes.push_back(hash);
 
     // Check if this is something relevant for optimization.
     if (!isRelevant(curr)) {