SimplifyGlobals: Ignore irrelevant effects in read-only-to-write (#4363)

Previously this pass would see something like this and fail:

if (foo() + global) {
  global = 1;
}

The call to foo() has side effects, so we did not optimize. However, in such
a case the side effects are safe: they happen anyhow, regardless of the global
that we are optimizing. That is, "global" is read only to be written, even though
other things also influence the decision to write it. But "global" is not used in a
way that is observable: we can remove it, and nothing will notice (except for
things getting smaller/faster).

In other words, this PR will let us optimize the above example, while it also
needs to avoid optimizing the dangerous cases, like this:

if (foo(global)) {
  global = 1;
}

Here "global" flows into a place that notices its value and may use it aside
from deciding to write that global.

A common case where we want to optimize is combined ifs,

if (foo()) {
  if (global) {
    global = 1;
  }
}

which the optimizer turns into

if (foo() & global) {
  global = 1;
}

With this PR we can handle those things too.

This lets us optimize out some important globals in j2wasm like the initializer
boolean for the Math object, reducing some total 0.5% of code size.

1 files changed, 189 insertions, 40 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 662c2fd05..2bce9050c 100644
--- a/test/lit/passes/simplify-globals-read_only_to_write.wast
+++ b/test/lit/passes/simplify-globals-read_only_to_write.wast
@@ -110,41 +110,6 @@
     )
   )
 )
-;; Side effects in the condition prevent the read-only-to-write optimization.
-(module
-  ;; CHECK:      (type $none_=>_none (func))
-
-  ;; CHECK:      (global $global (mut i32) (i32.const 0))
-  (global $global (mut i32) (i32.const 0))
-  ;; CHECK:      (global $other (mut i32) (i32.const 0))
-  (global $other (mut i32) (i32.const 0))
-  ;; CHECK:      (func $side-effects-in-condition
-  ;; CHECK-NEXT:  (if
-  ;; CHECK-NEXT:   (block $block (result i32)
-  ;; CHECK-NEXT:    (global.set $other
-  ;; CHECK-NEXT:     (i32.const 2)
-  ;; CHECK-NEXT:    )
-  ;; CHECK-NEXT:    (drop
-  ;; CHECK-NEXT:     (i32.const 2)
-  ;; CHECK-NEXT:    )
-  ;; CHECK-NEXT:    (global.get $global)
-  ;; CHECK-NEXT:   )
-  ;; CHECK-NEXT:   (global.set $global
-  ;; CHECK-NEXT:    (i32.const 1)
-  ;; CHECK-NEXT:   )
-  ;; CHECK-NEXT:  )
-  ;; CHECK-NEXT: )
-  (func $side-effects-in-condition
-    (if
-      (block (result i32)
-        (global.set $other (i32.const 2))
-        (drop (global.get $other))
-        (global.get $global)
-      )
-      (global.set $global (i32.const 1))
-    )
-  )
-)
 ;; Side effects in the body prevent the read-only-to-write optimization.
 (module
   ;; CHECK:      (type $none_=>_none (func))
@@ -358,13 +323,14 @@
 (module
   ;; CHECK:      (type $none_=>_none (func))
 
+  ;; CHECK:      (type $i32_=>_i32 (func (param i32) (result i32)))
+
   ;; CHECK:      (global $once (mut i32) (i32.const 0))
   (global $once (mut i32) (i32.const 0))
 
   ;; CHECK:      (func $clinit
   ;; CHECK-NEXT:  (if
-  ;; CHECK-NEXT:   (block $block (result i32)
-  ;; CHECK-NEXT:    (unreachable)
+  ;; CHECK-NEXT:   (call $foo
   ;; CHECK-NEXT:    (global.get $once)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:   (return)
@@ -374,10 +340,10 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT: )
   (func $clinit
-    ;; As above, but the optimization fails because the if body has effects.
+    ;; As above, but the optimization fails because the if condition has effects.
     (if
-      (block (result i32)
-        (unreachable)
+      (call $foo ;; This call may have side effects and it receives the global's
+                 ;; value, which is dangerous.
         (global.get $once)
       )
       (return)
@@ -386,4 +352,187 @@
       (i32.const 1)
     )
   )
+
+  ;; CHECK:      (func $foo (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $foo (param $x i32) (result i32)
+    (unreachable)
+  )
+)
+
+;; Using the global's value in a way that can cause side effects prevents the
+;; read-only-to-write optimization.
+(module
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+  ;; CHECK:      (global $global (mut i32) (i32.const 0))
+  (global $global (mut i32) (i32.const 0))
+  ;; CHECK:      (global $other i32 (i32.const 0))
+  (global $other (mut i32) (i32.const 0))
+  ;; CHECK:      (func $side-effects-in-condition
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (if (result i32)
+  ;; CHECK-NEXT:    (global.get $global)
+  ;; CHECK-NEXT:    (call $foo)
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (global.set $global
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $side-effects-in-condition
+    (if
+      (if (result i32)
+        (global.get $global) ;; the global's value may cause foo() to be called
+        (call $foo)
+        (i32.const 1)
+      )
+      (global.set $global (i32.const 1))
+    )
+  )
+
+  ;; CHECK:      (func $foo (result i32)
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $foo (result i32)
+    (unreachable)
+  )
+)
+
+;; As above, but now the global's value is not the condition of the if, so there
+;; is no problem.
+(module
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+  ;; CHECK:      (global $global i32 (i32.const 0))
+  (global $global (mut i32) (i32.const 0))
+  ;; CHECK:      (global $other i32 (i32.const 0))
+  (global $other (mut i32) (i32.const 0))
+  ;; CHECK:      (func $side-effects-in-condition-2
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (if (result i32)
+  ;; CHECK-NEXT:    (call $foo)
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $side-effects-in-condition-2
+    (if
+      (if (result i32)
+        (call $foo) ;; these side effects are not a problem, as the global's
+                    ;; value cannot reach them.
+        (i32.const 1)
+        (global.get $global) ;; the global's value flows out through the if,
+                             ;; safely
+      )
+      (global.set $global (i32.const 1))
+    )
+  )
+
+  ;; CHECK:      (func $foo (result i32)
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $foo (result i32)
+    (unreachable)
+  )
+)
+
+;; As above, but now the global's value flows into a side effect.
+(module
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (global $global (mut i32) (i32.const 0))
+  (global $global (mut i32) (i32.const 0))
+  ;; CHECK:      (global $other i32 (i32.const 0))
+  (global $other (mut i32) (i32.const 0))
+  ;; CHECK:      (func $side-effects-in-condition-3
+  ;; CHECK-NEXT:  (local $temp i32)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (local.tee $temp
+  ;; CHECK-NEXT:    (global.get $global)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (global.set $global
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $side-effects-in-condition-3
+    (local $temp i32)
+    (if
+      (local.tee $temp
+        (global.get $global) ;; the global's value flows into a place that has
+      )                      ;; side effects, so it may be noticed.
+      (global.set $global (i32.const 1))
+    )
+  )
+)
+
+;; As above, but now the global's value flows through multiple layers of
+;; things that have no side effects and are safe.
+(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 $side-effects-in-condition-4
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $y i32)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (i32.eqz
+  ;; CHECK-NEXT:    (select
+  ;; CHECK-NEXT:     (local.tee $x
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (i32.load
+  ;; CHECK-NEXT:      (i32.const 2)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (i32.add
+  ;; CHECK-NEXT:      (i32.const 0)
+  ;; CHECK-NEXT:      (i32.const 1337)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $side-effects-in-condition-4
+    (local $x i32)
+    (local $y i32)
+    (if
+      (i32.eqz
+        (select
+          (local.tee $x
+            (i32.const 1)
+          )
+          (i32.load
+            (i32.const 2)
+          )
+          (i32.add
+            (global.get $once)
+            (i32.const 1337)
+          )
+        )
+      )
+      (global.set $once
+        (i32.const 1)
+      )
+    )
+  )
 )