SimplifyGlobals: Handle nested read-only-to-write patterns (#4365)

The general pattern is

if (!global) { global = 1 }

This PR generalizes that to handle nested appearances,

if ({
  if (!global) { global = 1 }
  !global
}) {
  global = 1
}

With this I can finally see no more "once" global operations on the hottest
function in the currently slowest j2wasm benchmark ("filter").

Also added a failing testcase for something we do not handle yet.

1 files changed, 269 insertions, 0 deletions

diff --git a/test/lit/passes/simplify-globals-read_only_to_write.wast b/test/lit/passes/simplify-globals-read_only_to_write.wast
index 2bce9050c..149dd2dfb 100644
--- a/test/lit/passes/simplify-globals-read_only_to_write.wast
+++ b/test/lit/passes/simplify-globals-read_only_to_write.wast
@@ -536,3 +536,272 @@
     )
   )
 )
+
+(module
+  (memory 1 1)
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (global $once i32 (i32.const 0))
+  (global $once (mut i32) (i32.const 0))
+
+  ;; CHECK:      (memory $0 1 1)
+
+  ;; CHECK:      (func $nested-pattern
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $y i32)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (block $block (result i32)
+  ;; CHECK-NEXT:    (if
+  ;; CHECK-NEXT:     (i32.eqz
+  ;; CHECK-NEXT:      (i32.const 0)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (drop
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.eq
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-pattern
+    (local $x i32)
+    (local $y i32)
+    (if
+      (block (result i32)
+        ;; Another appearance of the pattern nested inside this one. This should
+        ;; not prevent us from optimizing.
+        (if
+          (i32.eqz
+            (global.get $once)
+          )
+          (global.set $once
+            (i32.const 1)
+          )
+        )
+        (i32.eq
+          (global.get $once)
+          (i32.const 0)
+        )
+      )
+      (global.set $once
+        (i32.const 1)
+      )
+    )
+  )
+)
+
+(module
+  (memory 1 1)
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (global $once (mut i32) (i32.const 0))
+  (global $once (mut i32) (i32.const 0))
+
+  ;; CHECK:      (memory $0 1 1)
+
+  ;; CHECK:      (func $almost-nested-pattern
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $y i32)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (block $block (result i32)
+  ;; CHECK-NEXT:    (if
+  ;; CHECK-NEXT:     (i32.eqz
+  ;; CHECK-NEXT:      (global.get $once)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (global.set $once
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (nop)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.eq
+  ;; CHECK-NEXT:     (global.get $once)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (global.set $once
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $almost-nested-pattern
+    (local $x i32)
+    (local $y i32)
+    (if
+      (block (result i32)
+        ;; This is almost the nested pattern, but not quite, as it has an
+        ;; "else" arm.
+        (if
+          (i32.eqz
+            (global.get $once)
+          )
+          (global.set $once
+            (i32.const 1)
+          )
+          (nop) ;; This breaks the pattern we are looking for.
+        )
+        (i32.eq
+          (global.get $once)
+          (i32.const 0)
+        )
+      )
+      (global.set $once
+        (i32.const 1)
+      )
+    )
+  )
+)
+
+(module
+  (memory 1 1)
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (global $once i32 (i32.const 0))
+  (global $once (mut i32) (i32.const 0))
+
+  ;; CHECK:      (memory $0 1 1)
+
+  ;; CHECK:      (func $nested-pattern-thrice
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $y i32)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (block $block (result i32)
+  ;; CHECK-NEXT:    (if
+  ;; CHECK-NEXT:     (i32.eqz
+  ;; CHECK-NEXT:      (block $block1 (result i32)
+  ;; CHECK-NEXT:       (if
+  ;; CHECK-NEXT:        (i32.const 0)
+  ;; CHECK-NEXT:        (drop
+  ;; CHECK-NEXT:         (i32.const 1)
+  ;; CHECK-NEXT:        )
+  ;; CHECK-NEXT:       )
+  ;; CHECK-NEXT:       (i32.const 0)
+  ;; CHECK-NEXT:      )
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (drop
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.eq
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-pattern-thrice
+    (local $x i32)
+    (local $y i32)
+    (if
+      (block (result i32)
+        (if
+          (i32.eqz
+            (block (result i32)
+              ;; A third nested appearance.
+              (if
+                (global.get $once)
+                (global.set $once
+                  (i32.const 1)
+                )
+              )
+              (global.get $once)
+            )
+          )
+          (global.set $once
+            (i32.const 1)
+          )
+        )
+        (i32.eq
+          (global.get $once)
+          (i32.const 0)
+        )
+      )
+      (global.set $once
+        (i32.const 1)
+      )
+    )
+  )
+)
+
+(module
+  (memory 1 1)
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (global $once (mut i32) (i32.const 0))
+  (global $once (mut i32) (i32.const 0))
+
+  ;; CHECK:      (memory $0 1 1)
+
+  ;; CHECK:      (func $nested-pattern
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $y i32)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (block $block (result i32)
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (global.get $once)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (if
+  ;; CHECK-NEXT:     (i32.eqz
+  ;; CHECK-NEXT:      (global.get $once)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (global.set $once
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.eq
+  ;; CHECK-NEXT:     (global.get $once)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (global.set $once
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-pattern
+    (local $x i32)
+    (local $y i32)
+    (if
+      (block (result i32)
+
+        ;; As above, but adding a drop of another get. This is *not* the
+        ;; pattern we are looking for, and it will prevent us from
+        ;; optimizing as we will no longer see that the number of gets
+        ;; matches the number of read-only-to-write patterns. In the
+        ;; future we could do a more complex counting operation to handle
+        ;; this too.
+        (drop
+          (global.get $once)
+        )
+
+        (if
+          (i32.eqz
+            (global.get $once)
+          )
+          (global.set $once
+            (i32.const 1)
+          )
+        )
+        (i32.eq
+          (global.get $once)
+          (i32.const 0)
+        )
+      )
+      (global.set $once
+        (i32.const 1)
+      )
+    )
+  )
+)