Avoid boilerplate in ExpressionAnalyzer comparing & hashing (#3332)

Expands on #3294:

*   Scope names must be distinguished as either defs or uses.

*   Error when a core #define is missing, which is less error-prone, as
    suggested by @tlively

*   Add DELEGATE_GET_FIELD which lets one define "get the field"
    once and then all the loops can use it. This helps avoid boilerplate for
    loops at least in some cases (when there is a single object on which
    to get the field).

With those, it is possible to replace boilerplate in comparisons and
hashing logic. This also fixes a bug where BrOnExn::sent was not
scanned there.

Add some unit tests for hashing. We didn't have any, and hashing can be
subtly wrong without observable external effects (just more collisions).

5 files changed, 391 insertions, 376 deletions

diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index 043fb259b..88dce6767 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -96,192 +96,6 @@ bool ExpressionAnalyzer::isResultDropped(ExpressionStack& stack) {
   return false;
 }
 
-//
-// Allows visiting the immediate fields of the expression. This is
-// useful for comparisons and hashing.
-//
-// The passed-in visitor object must implement:
-//  * visitScopeName - a Name that represents a block or loop scope
-//  * visitNonScopeName - a non-scope name
-//  * visitInt - anything that has a short enumeration, including
-//               opcodes, # of bytes in a load, bools, etc. - must be
-//               guaranteed to fit in an int32 or less.
-//  * visitLiteral - a Literal
-//  * visitType - a Type
-//  * visitIndex - an Index
-//  * visitAddress - an Address
-//
-
-namespace {
-
-template<typename T> void visitImmediates(Expression* curr, T& visitor) {
-  struct ImmediateVisitor : public OverriddenVisitor<ImmediateVisitor> {
-    T& visitor;
-
-    ImmediateVisitor(Expression* curr, T& visitor) : visitor(visitor) {
-      this->visit(curr);
-    }
-
-    void visitBlock(Block* curr) { visitor.visitScopeName(curr->name); }
-    void visitIf(If* curr) {}
-    void visitLoop(Loop* curr) { visitor.visitScopeName(curr->name); }
-    void visitBreak(Break* curr) { visitor.visitScopeName(curr->name); }
-    void visitSwitch(Switch* curr) {
-      for (auto target : curr->targets) {
-        visitor.visitScopeName(target);
-      }
-      visitor.visitScopeName(curr->default_);
-    }
-    void visitCall(Call* curr) {
-      visitor.visitNonScopeName(curr->target);
-      visitor.visitInt(curr->isReturn);
-    }
-    void visitCallIndirect(CallIndirect* curr) {
-      visitor.visitInt(curr->sig.params.getID());
-      visitor.visitInt(curr->sig.results.getID());
-      visitor.visitInt(curr->isReturn);
-    }
-    void visitLocalGet(LocalGet* curr) { visitor.visitIndex(curr->index); }
-    void visitLocalSet(LocalSet* curr) { visitor.visitIndex(curr->index); }
-    void visitGlobalGet(GlobalGet* curr) {
-      visitor.visitNonScopeName(curr->name);
-    }
-    void visitGlobalSet(GlobalSet* curr) {
-      visitor.visitNonScopeName(curr->name);
-    }
-    void visitLoad(Load* curr) {
-      visitor.visitInt(curr->bytes);
-      if (curr->type != Type::unreachable &&
-          curr->bytes < curr->type.getByteSize()) {
-        visitor.visitInt(curr->signed_);
-      }
-      visitor.visitAddress(curr->offset);
-      visitor.visitAddress(curr->align);
-      visitor.visitInt(curr->isAtomic);
-    }
-    void visitStore(Store* curr) {
-      visitor.visitInt(curr->bytes);
-      visitor.visitAddress(curr->offset);
-      visitor.visitAddress(curr->align);
-      visitor.visitInt(curr->isAtomic);
-      visitor.visitInt(curr->valueType.getID());
-    }
-    void visitAtomicRMW(AtomicRMW* curr) {
-      visitor.visitInt(curr->op);
-      visitor.visitInt(curr->bytes);
-      visitor.visitAddress(curr->offset);
-    }
-    void visitAtomicCmpxchg(AtomicCmpxchg* curr) {
-      visitor.visitInt(curr->bytes);
-      visitor.visitAddress(curr->offset);
-    }
-    void visitAtomicWait(AtomicWait* curr) {
-      visitor.visitAddress(curr->offset);
-      visitor.visitType(curr->expectedType);
-    }
-    void visitAtomicNotify(AtomicNotify* curr) {
-      visitor.visitAddress(curr->offset);
-    }
-    void visitAtomicFence(AtomicFence* curr) { visitor.visitInt(curr->order); }
-    void visitSIMDExtract(SIMDExtract* curr) {
-      visitor.visitInt(curr->op);
-      visitor.visitInt(curr->index);
-    }
-    void visitSIMDReplace(SIMDReplace* curr) {
-      visitor.visitInt(curr->op);
-      visitor.visitInt(curr->index);
-    }
-    void visitSIMDShuffle(SIMDShuffle* curr) {
-      for (auto x : curr->mask) {
-        visitor.visitInt(x);
-      }
-    }
-    void visitSIMDTernary(SIMDTernary* curr) { visitor.visitInt(curr->op); }
-    void visitSIMDShift(SIMDShift* curr) { visitor.visitInt(curr->op); }
-    void visitSIMDLoad(SIMDLoad* curr) {
-      visitor.visitInt(curr->op);
-      visitor.visitAddress(curr->offset);
-      visitor.visitAddress(curr->align);
-    }
-    void visitSIMDLoadStoreLane(SIMDLoadStoreLane* curr) {
-      visitor.visitInt(curr->op);
-      visitor.visitAddress(curr->offset);
-      visitor.visitAddress(curr->align);
-      visitor.visitInt(curr->index);
-    }
-    void visitMemoryInit(MemoryInit* curr) {
-      visitor.visitIndex(curr->segment);
-    }
-    void visitDataDrop(DataDrop* curr) { visitor.visitIndex(curr->segment); }
-    void visitMemoryCopy(MemoryCopy* curr) {}
-    void visitMemoryFill(MemoryFill* curr) {}
-    void visitConst(Const* curr) { visitor.visitLiteral(curr->value); }
-    void visitUnary(Unary* curr) { visitor.visitInt(curr->op); }
-    void visitBinary(Binary* curr) { visitor.visitInt(curr->op); }
-    void visitSelect(Select* curr) {}
-    void visitDrop(Drop* curr) {}
-    void visitReturn(Return* curr) {}
-    void visitMemorySize(MemorySize* curr) {}
-    void visitMemoryGrow(MemoryGrow* curr) {}
-    void visitRefNull(RefNull* curr) { visitor.visitType(curr->type); }
-    void visitRefIsNull(RefIsNull* curr) {}
-    void visitRefFunc(RefFunc* curr) { visitor.visitNonScopeName(curr->func); }
-    void visitRefEq(RefEq* curr) {}
-    void visitTry(Try* curr) {}
-    void visitThrow(Throw* curr) { visitor.visitNonScopeName(curr->event); }
-    void visitRethrow(Rethrow* curr) {}
-    void visitBrOnExn(BrOnExn* curr) {
-      visitor.visitScopeName(curr->name);
-      visitor.visitNonScopeName(curr->event);
-    }
-    void visitNop(Nop* curr) {}
-    void visitUnreachable(Unreachable* curr) {}
-    void visitPop(Pop* curr) {}
-    void visitTupleMake(TupleMake* curr) {}
-    void visitTupleExtract(TupleExtract* curr) {
-      visitor.visitIndex(curr->index);
-    }
-    void visitI31New(I31New* curr) {}
-    void visitI31Get(I31Get* curr) { visitor.visitInt(curr->signed_); }
-    void visitRefTest(RefTest* curr) {
-      WASM_UNREACHABLE("TODO (gc): ref.test");
-    }
-    void visitRefCast(RefCast* curr) {
-      WASM_UNREACHABLE("TODO (gc): ref.cast");
-    }
-    void visitBrOnCast(BrOnCast* curr) {
-      WASM_UNREACHABLE("TODO (gc): br_on_cast");
-    }
-    void visitRttCanon(RttCanon* curr) {
-      WASM_UNREACHABLE("TODO (gc): rtt.canon");
-    }
-    void visitRttSub(RttSub* curr) { WASM_UNREACHABLE("TODO (gc): rtt.sub"); }
-    void visitStructNew(StructNew* curr) {
-      WASM_UNREACHABLE("TODO (gc): struct.new");
-    }
-    void visitStructGet(StructGet* curr) {
-      WASM_UNREACHABLE("TODO (gc): struct.get");
-    }
-    void visitStructSet(StructSet* curr) {
-      WASM_UNREACHABLE("TODO (gc): struct.set");
-    }
-    void visitArrayNew(ArrayNew* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.new");
-    }
-    void visitArrayGet(ArrayGet* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.get");
-    }
-    void visitArraySet(ArraySet* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.set");
-    }
-    void visitArrayLen(ArrayLen* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.len");
-    }
-  } singleton(curr, visitor);
-}
-
-} // namespace
-
 bool ExpressionAnalyzer::flexibleEqual(Expression* left,
                                        Expression* right,
                                        ExprComparer comparer) {
@@ -291,80 +105,6 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left,
     std::vector<Expression*> leftStack;
     std::vector<Expression*> rightStack;
 
-    struct Immediates {
-      Comparer& parent;
-
-      Immediates(Comparer& parent) : parent(parent) {}
-
-      SmallVector<Name, 1> scopeNames;
-      SmallVector<Name, 1> nonScopeNames;
-      SmallVector<int32_t, 3> ints;
-      SmallVector<Literal, 1> literals;
-      SmallVector<Type, 1> types;
-      SmallVector<Index, 1> indexes;
-      SmallVector<Address, 2> addresses;
-
-      void visitScopeName(Name curr) { scopeNames.push_back(curr); }
-      void visitNonScopeName(Name curr) { nonScopeNames.push_back(curr); }
-      void visitInt(int32_t curr) { ints.push_back(curr); }
-      void visitLiteral(Literal curr) { literals.push_back(curr); }
-      void visitType(Type curr) { types.push_back(curr); }
-      void visitIndex(Index curr) { indexes.push_back(curr); }
-      void visitAddress(Address curr) { addresses.push_back(curr); }
-
-      // Comparison is by value, except for names, which must match.
-      bool operator==(const Immediates& other) {
-        if (scopeNames.size() != other.scopeNames.size()) {
-          return false;
-        }
-        for (Index i = 0; i < scopeNames.size(); i++) {
-          auto leftName = scopeNames[i];
-          auto rightName = other.scopeNames[i];
-          auto iter = parent.rightNames.find(leftName);
-          // If it's not found, that means it was defined out of the expression
-          // being compared, in which case we can just treat it literally - it
-          // must be exactly identical.
-          if (iter != parent.rightNames.end()) {
-            leftName = iter->second;
-          }
-          if (leftName != rightName) {
-            return false;
-          }
-        }
-        if (nonScopeNames != other.nonScopeNames) {
-          return false;
-        }
-        if (ints != other.ints) {
-          return false;
-        }
-        if (literals != other.literals) {
-          return false;
-        }
-        if (types != other.types) {
-          return false;
-        }
-        if (indexes != other.indexes) {
-          return false;
-        }
-        if (addresses != other.addresses) {
-          return false;
-        }
-        return true;
-      }
-
-      bool operator!=(const Immediates& other) { return !(*this == other); }
-
-      void clear() {
-        scopeNames.clear();
-        nonScopeNames.clear();
-        ints.clear();
-        literals.clear();
-        types.clear();
-        indexes.clear();
-        addresses.clear();
-      }
-    };
-
     bool noteNames(Name left, Name right) {
       if (left.is() != right.is()) {
         return false;
@@ -377,8 +117,6 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left,
     }
 
     bool compare(Expression* left, Expression* right, ExprComparer comparer) {
-      Immediates leftImmediates(*this), rightImmediates(*this);
-
       // The empty name is the same on both sides.
       rightNames[Name()] = Name();
 
@@ -396,45 +134,16 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left,
         if (!left) {
           continue;
         }
+        // There are actual expressions to compare here. Start with the custom
+        // comparer function that was provided.
         if (comparer(left, right)) {
-          continue; // comparison hook, before all the rest
+          continue;
         }
-        // continue with normal structural comparison
-        if (left->_id != right->_id) {
+        if (left->type != right->type) {
           return false;
         }
-        // Blocks and loops introduce scoping.
-        if (auto* block = left->dynCast<Block>()) {
-          if (!noteNames(block->name, right->cast<Block>()->name)) {
-            return false;
-          }
-        } else if (auto* loop = left->dynCast<Loop>()) {
-          if (!noteNames(loop->name, right->cast<Loop>()->name)) {
-            return false;
-          }
-        } else {
-          // For all other nodes, compare their immediate values
-          visitImmediates(left, leftImmediates);
-          visitImmediates(right, rightImmediates);
-          if (leftImmediates != rightImmediates) {
-            return false;
-          }
-          leftImmediates.clear();
-          rightImmediates.clear();
-        }
-        // Add child nodes.
-        Index counter = 0;
-        for (auto* child : ChildIterator(left)) {
-          leftStack.push_back(child);
-          counter++;
-        }
-        for (auto* child : ChildIterator(right)) {
-          rightStack.push_back(child);
-          counter--;
-        }
-        // The number of child nodes must match (e.g. return has an optional
-        // one).
-        if (counter != 0) {
+        // Do the actual comparison, updating the names and stacks accordingly.
+        if (!compareNodes(left, right)) {
           return false;
         }
       }
@@ -443,6 +152,97 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left,
       }
       return true;
     }
+
+    bool compareNodes(Expression* left, Expression* right) {
+      if (left->_id != right->_id) {
+        return false;
+      }
+
+#define DELEGATE_ID left->_id
+
+// Create cast versions of it for later operations.
+#define DELEGATE_START(id)                                                     \
+  auto* castLeft = left->cast<id>();                                           \
+  WASM_UNUSED(castLeft);                                                       \
+  auto* castRight = right->cast<id>();                                         \
+  WASM_UNUSED(castRight);
+
+// Handle each type of field, comparing it appropriately.
+#define DELEGATE_FIELD_CHILD(id, name)                                         \
+  leftStack.push_back(castLeft->name);                                         \
+  rightStack.push_back(castRight->name);
+
+#define DELEGATE_FIELD_CHILD_VECTOR(id, name)                                  \
+  if (castLeft->name.size() != castRight->name.size()) {                       \
+    return false;                                                              \
+  }                                                                            \
+  for (auto* child : castLeft->name) {                                         \
+    leftStack.push_back(child);                                                \
+  }                                                                            \
+  for (auto* child : castRight->name) {                                        \
+    rightStack.push_back(child);                                               \
+  }
+
+#define COMPARE_FIELD(name)                                                    \
+  if (castLeft->name != castRight->name) {                                     \
+    return false;                                                              \
+  }
+
+#define DELEGATE_FIELD_INT(id, name) COMPARE_FIELD(name)
+#define DELEGATE_FIELD_LITERAL(id, name) COMPARE_FIELD(name)
+#define DELEGATE_FIELD_NAME(id, name) COMPARE_FIELD(name)
+#define DELEGATE_FIELD_SIGNATURE(id, name) COMPARE_FIELD(name)
+#define DELEGATE_FIELD_TYPE(id, name) COMPARE_FIELD(name)
+#define DELEGATE_FIELD_ADDRESS(id, name) COMPARE_FIELD(name)
+
+#define COMPARE_LIST(name)                                                     \
+  if (castLeft->name.size() != castRight->name.size()) {                       \
+    return false;                                                              \
+  }                                                                            \
+  for (Index i = 0; i < castLeft->name.size(); i++) {                          \
+    if (castLeft->name[i] != castRight->name[i]) {                             \
+      return false;                                                            \
+    }                                                                          \
+  }
+
+#define DELEGATE_FIELD_INT_ARRAY(id, name) COMPARE_LIST(name)
+
+#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, name)                                \
+  if (castLeft->name.is() != castRight->name.is()) {                           \
+    return false;                                                              \
+  }                                                                            \
+  rightNames[castLeft->name] = castRight->name;
+
+#define DELEGATE_FIELD_SCOPE_NAME_USE(id, name)                                \
+  if (!compareNames(castLeft->name, castRight->name)) {                        \
+    return false;                                                              \
+  }
+
+#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, name)                         \
+  if (castLeft->name.size() != castRight->name.size()) {                       \
+    return false;                                                              \
+  }                                                                            \
+  for (Index i = 0; i < castLeft->name.size(); i++) {                          \
+    if (!compareNames(castLeft->name[i], castRight->name[i])) {                \
+      return false;                                                            \
+    }                                                                          \
+  }
+
+#include "wasm-delegations-fields.h"
+
+      return true;
+    }
+
+    bool compareNames(Name left, Name right) {
+      auto iter = rightNames.find(left);
+      // If it's not found, that means it was defined out of the expression
+      // being compared, in which case we can just treat it literally - it
+      // must be exactly identical.
+      if (iter != rightNames.end()) {
+        left = iter->second;
+      }
+      return left == right;
+    }
   };
 
   return Comparer().compare(left, right, comparer);
@@ -458,12 +258,6 @@ size_t ExpressionAnalyzer::hash(Expression* curr) {
     std::map<Name, Index> internalNames;
     ExpressionStack stack;
 
-    void noteScopeName(Name curr) {
-      if (curr.is()) {
-        internalNames[curr] = internalCounter++;
-      }
-    }
-
     Hasher(Expression* curr) {
       stack.push_back(curr);
 
@@ -471,6 +265,9 @@ size_t ExpressionAnalyzer::hash(Expression* curr) {
         curr = stack.back();
         stack.pop_back();
         if (!curr) {
+          // This was an optional child that was not present. Hash a 0 to
+          // represent that.
+          rehash(digest, 0);
           continue;
         }
         rehash(digest, curr->_id);
@@ -483,27 +280,51 @@ size_t ExpressionAnalyzer::hash(Expression* curr) {
         // call_imports type, etc. The simplest thing is just to hash the
         // type for all of them.
         rehash(digest, curr->type.getID());
-        // Blocks and loops introduce scoping.
-        if (auto* block = curr->dynCast<Block>()) {
-          noteScopeName(block->name);
-        } else if (auto* loop = curr->dynCast<Loop>()) {
-          noteScopeName(loop->name);
-        } else {
-          // For all other nodes, compare their immediate values
-          visitImmediates(curr, *this);
-        }
-        // Hash children
-        Index counter = 0;
-        for (auto* child : ChildIterator(curr)) {
-          stack.push_back(child);
-          counter++;
-        }
-        // Sometimes children are optional, e.g. return, so we must hash
-        // their number as well.
-        rehash(digest, counter);
+        // Hash the contents of the expression.
+        hashExpression(curr);
       }
     }
 
+    void hashExpression(Expression* curr) {
+
+#define DELEGATE_ID curr->_id
+
+// Create cast versions of it for later operations.
+#define DELEGATE_START(id)                                                     \
+  auto* cast = curr->cast<id>();                                               \
+  WASM_UNUSED(cast);
+
+// Handle each type of field, comparing it appropriately.
+#define DELEGATE_GET_FIELD(id, name) cast->name
+
+#define DELEGATE_FIELD_CHILD(id, name) stack.push_back(cast->name);
+
+#define HASH_FIELD(name) rehash(digest, cast->name);
+
+#define DELEGATE_FIELD_INT(id, name) HASH_FIELD(name)
+#define DELEGATE_FIELD_LITERAL(id, name) HASH_FIELD(name)
+#define DELEGATE_FIELD_SIGNATURE(id, name) HASH_FIELD(name)
+
+#define DELEGATE_FIELD_NAME(id, name) visitNonScopeName(cast->name)
+#define DELEGATE_FIELD_TYPE(id, name) visitType(cast->name);
+#define DELEGATE_FIELD_ADDRESS(id, name) visitAddress(cast->name);
+
+// Note that we only note the scope name, but do not also visit it. That means
+// that (block $x) and (block) get the same hash. In other words, we only change
+// the hash based on uses of scope names, that is when there is a noticeable
+// difference in break targets.
+#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, name) noteScopeName(cast->name);
+
+#define DELEGATE_FIELD_SCOPE_NAME_USE(id, name) visitScopeName(cast->name);
+
+#include "wasm-delegations-fields.h"
+    }
+
+    void noteScopeName(Name curr) {
+      if (curr.is()) {
+        internalNames[curr] = internalCounter++;
+      }
+    }
     void visitScopeName(Name curr) {
       // Names are relative, we give the same hash for
       // (block $x (br $x))
@@ -514,14 +335,7 @@ size_t ExpressionAnalyzer::hash(Expression* curr) {
       rehash(digest, internalNames[curr]);
     }
     void visitNonScopeName(Name curr) { rehash(digest, uint64_t(curr.str)); }
-    void visitInt(int32_t curr) { rehash(digest, curr); }
-    void visitLiteral(Literal curr) { rehash(digest, curr); }
     void visitType(Type curr) { rehash(digest, curr.getID()); }
-    void visitIndex(Index curr) {
-      static_assert(sizeof(Index) == sizeof(uint32_t),
-                    "wasm64 will need changes here");
-      rehash(digest, curr);
-    }
     void visitAddress(Address curr) { rehash(digest, curr.addr); }
   };
 
diff --git a/src/ir/ExpressionManipulator.cpp b/src/ir/ExpressionManipulator.cpp
index 51fc5af27..18c3f2df9 100644
--- a/src/ir/ExpressionManipulator.cpp
+++ b/src/ir/ExpressionManipulator.cpp
@@ -77,7 +77,8 @@ flexibleCopy(Expression* original, Module& wasm, CustomCopier custom) {
 #define DELEGATE_FIELD_INT(id, name) COPY_FIELD(name)
 #define DELEGATE_FIELD_LITERAL(id, name) COPY_FIELD(name)
 #define DELEGATE_FIELD_NAME(id, name) COPY_FIELD(name)
-#define DELEGATE_FIELD_SCOPE_NAME(id, name) COPY_FIELD(name)
+#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, name) COPY_FIELD(name)
+#define DELEGATE_FIELD_SCOPE_NAME_USE(id, name) COPY_FIELD(name)
 #define DELEGATE_FIELD_SIGNATURE(id, name) COPY_FIELD(name)
 #define DELEGATE_FIELD_TYPE(id, name) COPY_FIELD(name)
 #define DELEGATE_FIELD_ADDRESS(id, name) COPY_FIELD(name)
@@ -95,7 +96,7 @@ flexibleCopy(Expression* original, Module& wasm, CustomCopier custom) {
   assert(castCopy->name.size() == castOriginal->name.size());                  \
   COPY_FIELD_LIST(name)
 
-#define DELEGATE_FIELD_SCOPE_NAME_VECTOR(id, name) COPY_VECTOR(name)
+#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, name) COPY_VECTOR(name)
 
 #define DELEGATE_FIELD_INT_ARRAY(id, name) COPY_ARRAY(name)
 
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index fef4a9f7c..df2309474 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -15,89 +15,144 @@
  */
 
 // Implements a switch on an expression class ID, and has a case for each id
-// in which it runs delegates on the fields and immediates. All the delegates
-// are optional, so you can just provide what you want, and no code will be
-// emitted for the others.
+// in which it runs delegates on the fields and immediates. You should include
+// this file after defining the relevant DELEGATE_* macros.
 //
-// (The only mandatory thing to define is DELEGATE_ID which is the key for the
-// switch.)
+// All defines used here are undefed automatically at the end for you.
 //
-// All #defines used here are undefed automatically at the end for you.
+// Most of the defines are necessary, and you will get an error if you forget
+// them, but some are optional and some imply others, see below.
 //
-// Child pointers are emitted in reverse order (which is convenient for walking
-// by pushing them to a stack first).
+// The defines are as follows:
+//
+// DELEGATE_START(id) - called at the start of a case for an expression class.
+//
+// DELEGATE_END(id) - called at the end of a case.
+//
+// DELEGATE_GET_FIELD(id, name) - called to get a field by its name. This must
+//    know the object on which to get it, so it is just useful for the case
+//    where you operate on a single such object, but in that case it is nice
+//    because then other things can be defined automatically for you, see later.
+//
+// DELEGATE_FIELD_CHILD(id, name) - called for each child field (note: children
+//    are visited in reverse order, which is convenient for walking by pushing
+//    them to a stack first).
+//
+// DELEGATE_FIELD_OPTIONAL_CHILD(id, name) - called for a child that may not be
+//    present (like a Return's value). If you do not define this then
+//    DELEGATE_FIELD_CHILD is called.
+//
+// DELEGATE_FIELD_CHILD_VECTOR(id, name) - called for a variable-sized vector of
+//    child pointers. If this is not defined, and DELEGATE_GET_FIELD is, then
+//    DELEGATE_FIELD_CHILD is called on them.
+//
+// DELEGATE_FIELD_INT(id, name) - called for an integer field (bool, enum,
+//    Index, int32, or int64).
+//
+// DELEGATE_FIELD_INT_ARRAY(id, name) - called for a std::array of fixed size of
+//    integer values (like a SIMD mask). If this is not defined, and
+//    DELEGATE_GET_FIELD is, then DELEGATE_FIELD_INT is called on them.
+//
+// DELEGATE_FIELD_LITERAL(id, name) - called for a Literal.
+//
+// DELEGATE_FIELD_NAME(id, name) - called for a Name.
+//
+// DELEGATE_FIELD_SCOPE_NAME_DEF(id, name) - called for a scope name definition
+//    (like a block's name).
+//
+// DELEGATE_FIELD_SCOPE_NAME_USE(id, name) - called for a scope name use (like
+//    a break's target).
+//
+// DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, name) - called for a variable-sized
+//    vector of scope names (like a switch's targets). If this is not defined,
+//    and DELEGATE_GET_FIELD is, then DELEGATE_FIELD_SCOPE_NAME_USE is called on
+//    them.
+//
+// DELEGATE_FIELD_SIGNATURE(id, name) - called for a Signature.
+//
+// DELEGATE_FIELD_TYPE(id, name) - called for a Type.
+//
+// DELEGATE_FIELD_ADDRESS(id, name) - called for an Address.
 
-// Emits code at the start of the case for a class.
 #ifndef DELEGATE_START
 #define DELEGATE_START(id)
 #endif
 
-// Emits code at the end of the case for a class.
 #ifndef DELEGATE_END
 #define DELEGATE_END(id)
 #endif
 
-// Emits code to handle a child pointer.
 #ifndef DELEGATE_FIELD_CHILD
-#define DELEGATE_FIELD_CHILD(id, name)
+#error please define DELEGATE_FIELD_CHILD(id, name)
 #endif
 
-// Emits code to handle an optional child pointer (if this is not defined, then
-// DELEGATE_FIELD_CHILD is called on it).
 #ifndef DELEGATE_FIELD_OPTIONAL_CHILD
 #define DELEGATE_FIELD_OPTIONAL_CHILD(id, name) DELEGATE_FIELD_CHILD(id, name)
 #endif
 
-// Emits code to handle a variable-sized vector of child pointers.
 #ifndef DELEGATE_FIELD_CHILD_VECTOR
-#define DELEGATE_FIELD_CHILD_VECTOR(id, name)
+#ifdef DELEGATE_GET_FIELD
+#define DELEGATE_FIELD_CHILD_VECTOR(id, name)                                  \
+  for (Index i = 0; i < (DELEGATE_GET_FIELD(id, name)).size(); i++) {          \
+    DELEGATE_FIELD_CHILD(id, name[i]);                                         \
+  }
+#else
+#error please define DELEGATE_FIELD_CHILD_VECTOR(id, name)
+#endif
 #endif
 
-// Emits code to handle an integer value (bool, enum, Index, int32, or int64).
 #ifndef DELEGATE_FIELD_INT
-#define DELEGATE_FIELD_INT(id, name)
+#error please define DELEGATE_FIELD_INT(id, name)
 #endif
 
-// Emits code to handle a std::array of fixed size of integer values (like a
-// SIMD mask).
 #ifndef DELEGATE_FIELD_INT_ARRAY
-#define DELEGATE_FIELD_INT_ARRAY(id, name)
+#ifdef DELEGATE_GET_FIELD
+#define DELEGATE_FIELD_INT_ARRAY(id, name)                                     \
+  for (Index i = 0; i < (DELEGATE_GET_FIELD(id, name)).size(); i++) {          \
+    DELEGATE_FIELD_INT(id, name[i]);                                           \
+  }
+#else
+#error please define DELEGATE_FIELD_INT_ARRAY(id, name)
+#endif
 #endif
 
-// Emits code to handle a Literal.
 #ifndef DELEGATE_FIELD_LITERAL
-#define DELEGATE_FIELD_LITERAL(id, name)
+#error please define DELEGATE_FIELD_LITERAL(id, name)
 #endif
 
-// Emits code to handle a name (like a call target).
 #ifndef DELEGATE_FIELD_NAME
-#define DELEGATE_FIELD_NAME(id, name)
+#error please define DELEGATE_FIELD_NAME(id, name)
 #endif
 
-// Emits code to handle a scope name (like a br target).
-#ifndef DELEGATE_FIELD_SCOPE_NAME
-#define DELEGATE_FIELD_SCOPE_NAME(id, name)
+#ifndef DELEGATE_FIELD_SCOPE_NAME_DEF
+#error please define DELEGATE_FIELD_SCOPE_NAME_DEF(id, name)
 #endif
 
-// Emits code to handle a variable-sized vector of scope names (like a switch's
-// targets).
-#ifndef DELEGATE_FIELD_SCOPE_NAME_VECTOR
-#define DELEGATE_FIELD_SCOPE_NAME_VECTOR(id, name)
+#ifndef DELEGATE_FIELD_SCOPE_NAME_USE
+#error please define DELEGATE_FIELD_SCOPE_NAME_USE(id, name)
+#endif
+
+#ifndef DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR
+#ifdef DELEGATE_GET_FIELD
+#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, name)                         \
+  for (Index i = 0; i < (DELEGATE_GET_FIELD(id, name)).size(); i++) {          \
+    DELEGATE_FIELD_SCOPE_NAME_USE(id, name[i]);                                \
+  }
+#else
+#error please define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, name)
+#endif
 #endif
 
-// Emits code to handle a Signature.
 #ifndef DELEGATE_FIELD_SIGNATURE
-#define DELEGATE_FIELD_SIGNATURE(id, name)
+#error please define DELEGATE_FIELD_SIGNATURE(id, name)
 #endif
 
-// Emits code to handle a type.
 #ifndef DELEGATE_FIELD_TYPE
-#define DELEGATE_FIELD_TYPE(id, name)
+#error please define DELEGATE_FIELD_TYPE(id, name)
 #endif
 
-// Emits code to handle an address.
 #ifndef DELEGATE_FIELD_ADDRESS
-#define DELEGATE_FIELD_ADDRESS(id, name)
+#error please define DELEGATE_FIELD_ADDRESS(id, name)
 #endif
 
 switch (DELEGATE_ID) {
@@ -108,7 +163,7 @@ switch (DELEGATE_ID) {
   case Expression::Id::BlockId: {
     DELEGATE_START(Block);
     DELEGATE_FIELD_CHILD_VECTOR(Block, list);
-    DELEGATE_FIELD_SCOPE_NAME(Block, name);
+    DELEGATE_FIELD_SCOPE_NAME_DEF(Block, name);
     DELEGATE_END(Block);
     break;
   }
@@ -123,7 +178,7 @@ switch (DELEGATE_ID) {
   case Expression::Id::LoopId: {
     DELEGATE_START(Loop);
     DELEGATE_FIELD_CHILD(Loop, body);
-    DELEGATE_FIELD_SCOPE_NAME(Loop, name);
+    DELEGATE_FIELD_SCOPE_NAME_DEF(Loop, name);
     DELEGATE_END();
     break;
   }
@@ -131,7 +186,7 @@ switch (DELEGATE_ID) {
     DELEGATE_START(Break);
     DELEGATE_FIELD_OPTIONAL_CHILD(Break, condition);
     DELEGATE_FIELD_OPTIONAL_CHILD(Break, value);
-    DELEGATE_FIELD_SCOPE_NAME(Break, name);
+    DELEGATE_FIELD_SCOPE_NAME_USE(Break, name);
     DELEGATE_END();
     break;
   }
@@ -139,8 +194,8 @@ switch (DELEGATE_ID) {
     DELEGATE_START(Switch);
     DELEGATE_FIELD_CHILD(Switch, condition);
     DELEGATE_FIELD_OPTIONAL_CHILD(Switch, value);
-    DELEGATE_FIELD_SCOPE_NAME(Switch, default_);
-    DELEGATE_FIELD_SCOPE_NAME_VECTOR(Switch, targets);
+    DELEGATE_FIELD_SCOPE_NAME_USE(Switch, default_);
+    DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(Switch, targets);
     DELEGATE_END();
     break;
   }
@@ -447,7 +502,7 @@ switch (DELEGATE_ID) {
   case Expression::Id::BrOnExnId: {
     DELEGATE_START(BrOnExn);
     DELEGATE_FIELD_CHILD(BrOnExn, exnref);
-    DELEGATE_FIELD_SCOPE_NAME(BrOnExn, name);
+    DELEGATE_FIELD_SCOPE_NAME_USE(BrOnExn, name);
     DELEGATE_FIELD_NAME(BrOnExn, event);
     DELEGATE_FIELD_TYPE(BrOnExn, sent);
     DELEGATE_END();
@@ -576,9 +631,11 @@ switch (DELEGATE_ID) {
 #undef DELEGATE_FIELD_CHILD_VECTOR
 #undef DELEGATE_FIELD_INT
 #undef DELEGATE_FIELD_INT_ARRAY
+#undef DELEGATE_FIELD_LITERAL
 #undef DELEGATE_FIELD_NAME
-#undef DELEGATE_FIELD_SCOPE_NAME
-#undef DELEGATE_FIELD_SCOPE_NAME_VECTOR
+#undef DELEGATE_FIELD_SCOPE_NAME_DEF
+#undef DELEGATE_FIELD_SCOPE_NAME_USE
+#undef DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR
 #undef DELEGATE_FIELD_SIGNATURE
 #undef DELEGATE_FIELD_TYPE
 #undef DELEGATE_FIELD_ADDRESS
diff --git a/test/example/hash.cpp b/test/example/hash.cpp
new file mode 100644
index 000000000..7c3882cc9
--- /dev/null
+++ b/test/example/hash.cpp
@@ -0,0 +1,142 @@
+#include <cassert>
+#include <iostream>
+
+#include <ir/utils.h>
+
+using namespace wasm;
+
+#define assertEqual(left, right)                                               \
+  assert(ExpressionAnalyzer::hash(&left) == ExpressionAnalyzer::hash(&right));
+
+#define assertNotEqual(left, right)                                            \
+  assert(ExpressionAnalyzer::hash(&left) != ExpressionAnalyzer::hash(&right));
+
+int main() {
+  {
+    Const x, y;
+    x.set(Literal(int32_t(10)));
+    y.set(Literal(int32_t(10)));
+    assertEqual(x, y);
+  }
+  {
+    // The value matters (with extremely high probability...)
+    Const x, y;
+    x.set(Literal(int32_t(10)));
+    y.set(Literal(int32_t(11)));
+    assertNotEqual(x, y);
+  }
+  {
+    // The type matters.
+    Const x, y;
+    x.set(Literal(int32_t(10)));
+    y.set(Literal(int64_t(10)));
+    assertNotEqual(x, y);
+  }
+  {
+    // Nested child.
+    Drop dx, dy;
+    Const x, y;
+    x.set(Literal(int32_t(10)));
+    y.set(Literal(int32_t(10)));
+    dx.value = &x;
+    dy.value = &y;
+    assertEqual(dx, dy);
+  }
+  {
+    // Nested child.
+    Drop dx, dy;
+    Const x, y;
+    x.set(Literal(int32_t(10)));
+    y.set(Literal(int32_t(11)));
+    dx.value = &x;
+    dy.value = &y;
+    assertNotEqual(dx, dy);
+  }
+  MixedArena arena;
+  {
+    // Blocks
+    Block x(arena);
+    Block y(arena);
+    assertEqual(x, y);
+  }
+  {
+    // Blocks with contents.
+    Block x(arena);
+    Block y(arena);
+    Nop n;
+    y.list.push_back(&n);
+    assertNotEqual(x, y);
+  }
+  {
+    // Blocks with names.
+    Block x(arena);
+    x.name = "foo";
+    Block y(arena);
+    y.name = "foo";
+    assertEqual(x, y);
+  }
+  {
+    // Different block names hash equally - we ignore internal name differences
+    // intentionally.
+    Block x(arena);
+    x.name = "foo";
+    Block y(arena);
+    y.name = "bar";
+    assertEqual(x, y);
+  }
+  {
+    // Different br names are checked relatively as well.
+    Break x;
+    x.name = "foo";
+    Break y;
+    y.name = "bar";
+    Block z(arena);
+    z.name = "foo";
+    z.list.push_back(&x);
+    Block w(arena);
+    w.name = "bar";
+    w.list.push_back(&y);
+    Block outer1(arena);
+    outer1.name = "outer1";
+    outer1.list.push_back(&z);
+    Block outer2(arena);
+    outer2.name = "outer2";
+    outer2.list.push_back(&w);
+    assertEqual(outer1, outer2);
+  }
+  {
+    // But referring to different relative names leads to a difference.
+    Break x;
+    x.name = "outer1"; // instead of x, go to the outer label this time
+    Break y;
+    y.name = "bar";
+    Block z(arena);
+    z.name = "foo";
+    z.list.push_back(&x);
+    Block w(arena);
+    w.name = "bar";
+    w.list.push_back(&y);
+    Block outer1(arena);
+    outer1.name = "outer1";
+    outer1.list.push_back(&z);
+    Block outer2(arena);
+    outer2.name = "outer2";
+    outer2.list.push_back(&w);
+    assertNotEqual(outer1, outer2);
+  }
+  {
+    // Indexes.
+    LocalGet x, y;
+    x.index = 10;
+    y.index = 10;
+    assertEqual(x, y);
+  }
+  {
+    // Indexes.
+    LocalGet x, y;
+    x.index = 10;
+    y.index = 11;
+    assertNotEqual(x, y);
+  }
+  std::cout << "success.\n";
+}
diff --git a/test/example/hash.txt b/test/example/hash.txt
new file mode 100644
index 000000000..b32bb74d2
--- /dev/null
+++ b/test/example/hash.txt
@@ -0,0 +1 @@
+success.