MergeSimilarFunctions optimization pass (#4414)

Merge similar functions that only differs constant values (like immediate
operand of const and call insts) by parameterization.
Performing this pass at post-link time can merge more functions across
objects. Inspired by Swift compiler's optimization which is derived from
LLVM's one:
https://github.com/apple/swift/blob/main/lib/LLVMPasses/LLVMMergeFunctions.cpp
https://github.com/llvm/llvm-project/blob/main/llvm/docs/MergeFunctions.rst

The basic ideas here are constant value parameterization and direct callee
parameterization by indirection.

Constant value parameterization is like below:

;;  Before
(func $big-const-42 (result i32)
  [[many instr 1]]
  (i32.const 44)
  [[many instr 2]]
)
(func $big-const-43 (result i32)
  [[many instr 1]]
  (i32.const 45)
  [[many instr 2]]
)

;; After
(func $byn$mgfn-shared$big-const-42 (result i32)
  [[many instr 1]]
  (local.get $0) ;; parameterized!!
  [[many instr 2]]
)
(func $big-const-42 (result i32)
  (call $byn$mgfn-shared$big-const-42
   (i32.const 42)
  )
)
(func $big-const-43 (result i32)
  (call $byn$mgfn-shared$big-const-42
   (i32.const 43)
  )
)

Direct callee parameterization is similar to the constant value parameterization,
but it parameterizes callee function i by ref.func instead. Therefore it is enabled
only when reference-types and typed-function-references features are enabled.

I saw 1 ~ 2 % reduction for SwiftWasm binary and Ruby's wasm port
using wasi-sdk, and 3 ~ 4.5% reduction for Unity WebGL binary when -Oz.

1 files changed, 13 insertions, 5 deletions

diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index a4b1efde1..acd446acc 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -262,7 +262,10 @@ struct Hasher {
   std::map<Name, Index> internalNames;
   ExpressionStack stack;
 
-  Hasher(Expression* curr, bool visitChildren) : visitChildren(visitChildren) {
+  Hasher(Expression* curr,
+         bool visitChildren,
+         ExpressionAnalyzer::ExprHasher custom)
+    : visitChildren(visitChildren) {
     stack.push_back(curr);
     // DELEGATE_CALLER_TARGET is a fake target used to denote delegating to
     // the caller. Add it here to prevent the unknown name error.
@@ -287,7 +290,11 @@ struct Hasher {
       // call_imports type, etc. The simplest thing is just to hash the
       // type for all of them.
       rehash(digest, curr->type.getID());
-      // Hash the contents of the expression.
+      // If the custom hasher handled this expr, then we have nothing to do.
+      if (custom(curr, digest)) {
+        continue;
+      }
+      // Hash the contents of the expression normally.
       hashExpression(curr);
     }
   }
@@ -365,12 +372,13 @@ struct Hasher {
 
 } // anonymous namespace
 
-size_t ExpressionAnalyzer::hash(Expression* curr) {
-  return Hasher(curr, true).digest;
+size_t ExpressionAnalyzer::flexibleHash(Expression* curr,
+                                        ExpressionAnalyzer::ExprHasher custom) {
+  return Hasher(curr, true, custom).digest;
 }
 
 size_t ExpressionAnalyzer::shallowHash(Expression* curr) {
-  return Hasher(curr, false).digest;
+  return Hasher(curr, false, ExpressionAnalyzer::nothingHasher).digest;
 }
 
 } // namespace wasm