Repository: tetratelabs/wazero
Pull request #2245 (2024-06-10 19:12:54)

ssa: optimizes findValue function
This removes the unnecessary search and addition of block params.
As a result, the compilation gets faster up to 30% while having no
impacts on the runtime performance like the below

### TinyGo

```
goos: darwin
goarch: arm64
pkg: github.com/tetratelabs/wazero/internal/integration_test/stdlibs
                                      │ old_tinygo.txt │            new_tinygo.txt             │
                                      │     sec/op     │     sec/op      vs base               │
TinyGo/Compile/container_heap.test-10      389.2m ± 0%   305.5m ±  0%    -21.50% (p=0.001 n=7)
TinyGo/Run/container_heap.test-10          14.80m ± 4%   14.24m ±  1%          ~ (p=0.053 n=7)
TinyGo/Compile/container_list.test-10      387.1m ± 0%   304.8m ±  1%    -21.26% (p=0.001 n=7)
TinyGo/Run/container_list.test-10          14.11m ± 1%   14.06m ±  1%          ~ (p=0.902 n=7)
TinyGo/Compile/container_ring.test-10      382.1m ± 0%   299.7m ±  1%    -21.56% (p=0.001 n=7)
TinyGo/Run/container_ring.test-10          14.11m ± 0%   14.09m ±  0%          ~ (p=0.805 n=7)
TinyGo/Compile/crypto_des.test-10          396.7m ± 1%   311.7m ±  0%    -21.43% (p=0.001 n=7)
TinyGo/Run/crypto_des.test-10              18.12m ± 0%   18.08m ±  0%          ~ (p=0.710 n=7)
TinyGo/Compile/crypto_md5.test-10          394.5m ± 0%   308.7m ±  0%    -21.74% (p=0.001 n=7)
TinyGo/Run/crypto_md5.test-10              20.47m ± 1%   20.54m ±  1%          ~ (p=0.805 n=7)
TinyGo/Compile/crypto_rc4.test-10          381.1m ± 1%   297.9m ±  0%    -21.83% (p=0.001 n=7)
TinyGo/Run/crypto_rc4.test-10              160.3m ± 0%   160.6m ±  0%          ~ (p=1.000 n=7)
TinyGo/Compile/crypto_sha1.test-10         394.0m ± 8%   309.9m ±  0%    -21.35% (p=0.001 n=7)
TinyGo/Run/crypto_sha1.test-10             15.85m ± 1%   15.99m ± 10%          ~ (p=0.097 n=7)
TinyGo/Compile/crypto_sha256.test-10       401.2m ± 1%   314.2m ±  1%    -21.68% (p=0.001 n=7)
TinyGo/Run/crypto_sha256.test-10           16.09m ± 3%   16.06m ±  1%          ~ (p=0.383 n=7)
geomean                                    91.52m        87.69m          -11.60%

                                      │ old_tinygo.txt │            new_tinygo.txt            │
                                      │      B/op      │      B/op       vs base              │
TinyGo/Compile/container_heap.test-10     45.03Mi ± 0%   44.09Mi ± 0%    -2.08% (p=0.001 n=7)
TinyGo/Run/container_heap.test-10         16.63Mi ± 0%   16.63Mi ± 0%         ~ (p=0.073 n=7)
TinyGo/Compile/container_list.test-10     45.00Mi ± 0%   44.07Mi ± 0%    -2.07% (p=0.001 n=7)
TinyGo/Run/container_list.test-10         16.40Mi ± 0%   16.40Mi ± 0%         ~ (p=0.383 n=7)
TinyGo/Compile/container_ring.test-10     44.25Mi ± 0%   43.32Mi ± 0%    -2.10% (p=0.001 n=7)
TinyGo/Run/container_ring.test-10         16.30Mi ± 0%   16.30Mi ± 0%         ~ (p=0.710 n=7)
TinyGo/Compile/crypto_des.test-10         45.13Mi ± 0%   44.21Mi ± 0%    -2.04% (p=0.001 n=7)
TinyGo/Run/crypto_des.test-10             16.76Mi ± 0%   16.76Mi ± 0%         ~ (p=0.165 n=7)
TinyGo/Compile/crypto_md5.test-10         45.14Mi ± 0%   44.21Mi ± 0%    -2.06% (p=0.001 n=7)
TinyGo/Run/crypto_md5.test-10             44.97Mi ± 0%   44.97Mi ± 0%         ~ (p=0.710 n=7)
TinyGo/Compile/crypto_rc4.test-10         44.23Mi ± 0%   43.30Mi ± 0%    -2.10% (p=0.001 n=7)
TinyGo/Run/crypto_rc4.test-10             29.28Mi ± 0%   29.28Mi ± 0%         ~ (p=0.165 n=7)
TinyGo/Compile/crypto_sha1.test-10        45.38Mi ± 0%   44.46Mi ± 0%    -2.04% (p=0.001 n=7)
TinyGo/Run/crypto_sha1.test-10            17.44Mi ± 0%   17.44Mi ± 0%         ~ (p=1.000 n=7)
TinyGo/Compile/crypto_sha256.test-10      45.22Mi ± 0%   44.29Mi ± 0%    -2.05% (p=0.001 n=7)
TinyGo/Run/crypto_sha256.test-10          17.53Mi ± 0%   17.53Mi ± 0%         ~ (p=0.165 n=7)
geomean                                   30.27Mi        30.66Mi         -1.04%

                                      │ old_tinygo.txt │            new_tinygo.txt            │
                                      │   allocs/op    │   allocs/op    vs base               │
TinyGo/Compile/container_heap.test-10      81.53k ± 0%   70.79k ± 0%    -13.17% (p=0.001 n=7)
TinyGo/Run/container_heap.test-10          374.9k ± 0%   374.9k ± 0%          ~ (p=0.579 n=7)
TinyGo/Compile/container_list.test-10      81.29k ± 0%   70.59k ± 0%    -13.15% (p=0.001 n=7)
TinyGo/Run/container_list.test-10          370.0k ± 0%   370.0k ± 0%          ~ (p=1.000 n=7)
TinyGo/Compile/container_ring.test-10      81.23k ± 0%   70.53k ± 0%    -13.17% (p=0.001 n=7)
TinyGo/Run/container_ring.test-10          367.6k ± 0%   367.6k ± 0%          ~ (p=0.674 n=7)
TinyGo/Compile/crypto_des.test-10          81.50k ± 0%   70.92k ± 0%    -12.99% (p=0.001 n=7)
TinyGo/Run/crypto_des.test-10              378.1k ± 0%   378.1k ± 0%     -0.00% (p=0.020 n=7)
TinyGo/Compile/crypto_md5.test-10          81.53k ± 0%   70.85k ± 0%    -13.11% (p=0.001 n=7)
TinyGo/Run/crypto_md5.test-10              393.3k ± 0%   393.3k ± 0%          ~ (p=1.000 n=7)
TinyGo/Compile/crypto_rc4.test-10          81.22k ± 0%   70.51k ± 0%    -13.19% (p=0.001 n=7)
TinyGo/Run/crypto_rc4.test-10              367.1k ± 0%   367.1k ± 0%          ~ (p=0.162 n=7)
TinyGo/Compile/crypto_sha1.test-10         81.83k ± 0%   71.14k ± 0%    -13.07% (p=0.001 n=7)
TinyGo/Run/crypto_sha1.test-10             392.7k ± 0%   392.7k ± 0%          ~ (p=0.470 n=7)
TinyGo/Compile/crypto_sha256.test-10       81.58k ± 0%   70.89k ± 0%    -13.11% (p=0.001 n=7)
TinyGo/Run/crypto_sha256.test-10           394.5k ± 0%   394.5k ± 0%          ~ (p=0.429 n=7)
geomean                                    175.9k        156.0k          -6.79%
```

### Wasip1
```
goos: darwin
goarch: arm64
pkg: github.com/tetratelabs/wazero/internal/integration_test/stdlibs
                                            │ old_wasip1.txt │          new_wasip1.txt           │
                                            │     sec/op     │   sec/op     vs base              │
Wasip1/Compile/src_archive_tar.test-10            1.992 ± 0%    1.913 ± 1%  -4.00% (p=0.001 n=7)
Wasip1/Run/src_archive_tar.test-10               399.1m ± 0%   398.9m ± 0%       ~ (p=0.620 n=7)
Wasip1/Compile/src_bufio.test-10                  1.354 ± 0%    1.297 ± 0%  -4.23% (p=0.001 n=7)
Wasip1/Run/src_bufio.test-10                     120.2m ± 1%   120.3m ± 0%       ~ (p=0.805 n=7)
Wasip1/Compile/src_bytes.test-10                  1.403 ± 2%    1.341 ± 0%  -4.39% (p=0.001 n=7)
Wasip1/Run/src_bytes.test-10                     468.2m ± 1%   470.5m ± 0%       ~ (p=0.318 n=7)
Wasip1/Compile/src_context.test-10                1.508 ± 0%    1.442 ± 0%  -4.41% (p=0.001 n=7)
Wasip1/Run/src_context.test-10                   31.62m ± 0%   31.72m ± 3%       ~ (p=0.209 n=7)
Wasip1/Compile/src_encoding_ascii85.test-10       1.215 ± 0%    1.162 ± 0%  -4.37% (p=0.001 n=7)
geomean                                          554.1m        541.4m       -2.31%

                                            │ old_wasip1.txt │           new_wasip1.txt           │
                                            │      B/op      │     B/op      vs base              │
Wasip1/Compile/src_archive_tar.test-10          90.57Mi ± 0%   90.30Mi ± 0%  -0.29% (p=0.001 n=7)
Wasip1/Run/src_archive_tar.test-10              286.0Mi ± 0%   286.0Mi ± 0%       ~ (p=0.640 n=7)
Wasip1/Compile/src_bufio.test-10                70.99Mi ± 0%   70.56Mi ± 0%  -0.60% (p=0.001 n=7)
Wasip1/Run/src_bufio.test-10                    105.3Mi ± 0%   105.3Mi ± 0%       ~ (p=1.000 n=7)
Wasip1/Compile/src_bytes.test-10                72.16Mi ± 0%   71.75Mi ± 0%  -0.57% (p=0.001 n=7)
Wasip1/Run/src_bytes.test-10                    605.0Mi ± 0%   605.0Mi ± 0%       ~ (p=0.834 n=7)
Wasip1/Compile/src_context.test-10              74.88Mi ± 0%   74.45Mi ± 0%  -0.57% (p=0.001 n=7)
Wasip1/Run/src_context.test-10                  71.52Mi ± 0%   71.52Mi ± 0%       ~ (p=0.269 n=7)
Wasip1/Compile/src_encoding_ascii85.test-10     67.27Mi ± 0%   66.87Mi ± 0%  -0.59% (p=0.001 n=7)
geomean                                         113.2Mi        112.8Mi       -0.29%

                                            │ old_wasip1.txt │           new_wasip1.txt            │
                                            │   allocs/op    │  allocs/op   vs base                │
Wasip1/Compile/src_archive_tar.test-10           255.7k ± 0%   252.7k ± 0%  -1.21% (p=0.001 n=7)
Wasip1/Run/src_archive_tar.test-10               7.831k ± 0%   7.830k ± 0%       ~ (p=1.000 n=7)
Wasip1/Compile/src_bufio.test-10                 188.6k ± 0%   182.2k ± 0%  -3.38% (p=0.001 n=7)
Wasip1/Run/src_bufio.test-10                     3.728k ± 0%   3.728k ± 0%       ~ (p=1.000 n=7) ¹
Wasip1/Compile/src_bytes.test-10                 196.6k ± 0%   190.2k ± 0%  -3.25% (p=0.001 n=7)
Wasip1/Run/src_bytes.test-10                     6.377k ± 0%   6.378k ± 0%       ~ (p=1.000 n=7)
Wasip1/Compile/src_context.test-10               213.7k ± 0%   207.3k ± 0%  -3.00% (p=0.001 n=7)
Wasip1/Run/src_context.test-10                   3.814k ± 1%   3.784k ± 1%       ~ (p=0.461 n=7)
Wasip1/Compile/src_encoding_ascii85.test-10      176.1k ± 0%   170.0k ± 0%  -3.49% (p=0.001 n=7)
geomean                                          39.85k        39.18k       -1.69%
¹ all samples are equal
```

### Zig

```
goos: darwin
goarch: arm64
pkg: github.com/tetratelabs/wazero/internal/integration_test/stdlibs
                             │ old_zig.txt │           new_zig.txt            │
                             │   sec/op    │   sec/op    vs base              │
Zig/Compile/test-opt.wasm-10    3.385 ± 1%   3.391 ± 1%       ~ (p=0.485 n=6)
Zig/Run/test-opt.wasm-10        18.73 ± 0%   18.97 ± 1%  +1.25% (p=0.002 n=6)
Zig/Compile/test.wasm-10        4.171 ± 1%   4.200 ± 0%       ~ (p=0.065 n=6)
Zig/Run/test.wasm-10            19.32 ± 1%   19.46 ± 3%       ~ (p=0.310 n=6)
geomean                         8.455        8.515       +0.70%

                             │ old_zig.txt  │            new_zig.txt             │
                             │     B/op     │     B/op      vs base              │
Zig/Compile/test-opt.wasm-10   384.8Mi ± 0%   383.8Mi ± 0%  -0.24% (p=0.002 n=6)
Zig/Run/test-opt.wasm-10       741.7Mi ± 0%   741.7Mi ± 0%       ~ (p=1.000 n=6)
Zig/Compile/test.wasm-10       594.3Mi ± 0%   594.0Mi ± 0%  -0.05% (p=0.002 n=6)
Zig/Run/test.wasm-10           1.296Gi ± 0%   1.296Gi ± 0%       ~ (p=0.253 n=6)
geomean                        688.8Mi        688.4Mi       -0.07%

                             │ old_zig.txt │            new_zig.txt            │
                             │  allocs/op  │  allocs/op   vs base              │
Zig/Compile/test-opt.wasm-10   328.5k ± 0%   322.5k ± 0%  -1.84% (p=0.002 n=6)
Zig/Run/test-opt.wasm-10       51.58k ± 0%   51.58k ± 0%       ~ (p=1.000 n=6)
Zig/Compile/test.wasm-10       278.7k ± 0%   277.3k ± 0%  -0.48% (p=0.002 n=6)
Zig/Run/test.wasm-10           2.156M ± 0%   2.156M ± 0%       ~ (p=0.602 n=6)
geomean                        317.6k        315.8k       -0.58%
```

#2182 


Patch:
diff --git a/internal/engine/wazevo/ssa/builder.go b/internal/engine/wazevo/ssa/builder.go
index 316e6261..0b700c4b 100644
--- a/internal/engine/wazevo/ssa/builder.go
+++ b/internal/engine/wazevo/ssa/builder.go
@@ -518,21 +518,42 @@ func (b *builder) findValue(typ Type, variable Variable, blk *basicBlock) Value
 	// If this block has multiple predecessors, we have to gather the definitions,
 	// and treat them as an argument to this block.
 	//
-	// The first thing is to define a new parameter to this block which may or may not be redundant, but
-	// later we eliminate trivial params in an optimization pass. This must be done before finding the
-	// definitions in the predecessors so that we can break the cycle.
-	paramValue := blk.AddParam(b, typ)
-	b.DefineVariable(variable, paramValue, blk)
-
-	// After the new param is added, we have to manipulate the original branching instructions
-	// in predecessors so that they would pass the definition of `variable` as the argument to
-	// the newly added PHI.
+	// But before that, we have to check if the possible definitions are the same Value.
+	tmpValue := b.allocateValue(typ)
+	// Break the cycle by defining the variable with the tmpValue.
+	b.DefineVariable(variable, tmpValue, blk)
+	// Check all the predecessors if they have the same definition.
+	uniqueValue := ValueInvalid
 	for i := range blk.preds {
-		pred := &blk.preds[i]
-		value := b.findValue(typ, variable, pred.blk)
-		pred.branch.addArgumentBranchInst(b, value)
+		predValue := b.findValue(typ, variable, blk.preds[i].blk)
+		if uniqueValue == ValueInvalid {
+			uniqueValue = predValue
+		} else if uniqueValue != predValue {
+			uniqueValue = ValueInvalid
+			break
+		}
+	}
+
+	if uniqueValue != ValueInvalid {
+		// If all the predecessors have the same definition, we can use that value.
+		b.DefineVariable(variable, uniqueValue, blk)
+		b.alias(tmpValue, uniqueValue)
+		return uniqueValue
+	} else {
+		// Otherwise, add the tmpValue to this block as a parameter which may or may not be redundant, but
+		// later we eliminate trivial params in an optimization pass. This must be done before finding the
+		// definitions in the predecessors so that we can break the cycle.
+		blk.addParamOn(tmpValue)
+		// After the new param is added, we have to manipulate the original branching instructions
+		// in predecessors so that they would pass the definition of `variable` as the argument to
+		// the newly added PHI.
+		for i := range blk.preds {
+			pred := &blk.preds[i]
+			value := b.findValue(typ, variable, pred.blk)
+			pred.branch.addArgumentBranchInst(b, value)
+		}
+		return tmpValue
 	}
-	return paramValue
 }
 
 // Seal implements Builder.Seal.


Test patch:
diff --git a/internal/engine/wazevo/frontend/frontend_test.go b/internal/engine/wazevo/frontend/frontend_test.go
index d1040a4a..b982556d 100644
--- a/internal/engine/wazevo/frontend/frontend_test.go
+++ b/internal/engine/wazevo/frontend/frontend_test.go
@@ -1058,14 +1058,14 @@ blk1: () <-- (blk0)
 	Call f1:sig1, exec_ctx, module_ctx
 	v5:i64 = Load module_ctx, 0x8
 	v6:i64 = Uload32 module_ctx, 0x10
-	Jump blk3, v2
+	Jump blk3
 
 blk2: () <-- (blk0)
-	Jump blk3, v2
+	Jump blk3
 
-blk3: (v7:i32) <-- (blk1,blk2)
+blk3: () <-- (blk1,blk2)
 	v8:i64 = Iconst_64 0x4
-	v9:i64 = UExtend v7, 32->64
+	v9:i64 = UExtend v2, 32->64
 	v10:i64 = Uload32 module_ctx, 0x10
 	v11:i64 = Iadd v9, v8
 	v12:i32 = Icmp lt_u, v10, v11
@@ -2869,7 +2869,7 @@ blk0: (exec_ctx:i64, module_ctx:i64, v2:i32)
 
 blk1: () <-- (blk0)
 	v11:i32 = Load v9, 0x10
-	Jump blk3, v2
+	Jump blk3
 
 blk2: () <-- (blk0)
 	v12:i32 = Load v9, 0x10
@@ -2880,18 +2880,13 @@ blk2: () <-- (blk0)
 	ExitIfTrue v16, exec_ctx, memory_out_of_bounds
 	v17:i32 = Load v9, 0x30
 	v18:i32 = Load v9, 0x25
-	Jump blk3, v2
+	Jump blk3
 
-blk3: (v19:i32) <-- (blk1,blk2)
-	v20:i64 = Iconst_64 0x19
-	v21:i64 = UExtend v19, 32->64
-	v22:i64 = Uload32 module_ctx, 0x10
-	v23:i64 = Iadd v21, v20
-	v24:i32 = Icmp lt_u, v22, v23
-	ExitIfTrue v24, exec_ctx, memory_out_of_bounds
-	v25:i64 = Load module_ctx, 0x8
-	v26:i64 = Iadd v25, v21
-	v27:i32 = Load v26, 0x15
+blk3: () <-- (blk1,blk2)
+	v20:i64 = Load module_ctx, 0x8
+	v21:i64 = UExtend v2, 32->64
+	v22:i64 = Iadd v20, v21
+	v23:i32 = Load v22, 0x15
 	Jump blk_ret
 `,
 		},