Allow optimizing with global function effects (#5040)

This adds a map of function name => the effects of that function to the
PassOptions structure. That lets us compute those effects once and then
use them in multiple passes afterwards. For example, that lets us optimize
away a call to a function that has no effects:

(drop (call $nothing))

[..]

(func $nothing
  ;; .. lots of stuff but no effects, only a returned value ..
)

Vacuum will remove that dropped call if we tell it that the called function has
no effects. Note that a nice result of adding this to the PassOptions struct
is that all passes will use the extra info automatically.

This is not enabled by default as the benefits seem rather minor, though it
does help in a small but noticeable way on J2Wasm code, where we use
call.without.effects and have situations like this:

(func $foo
  (call $bar)
)
(func $bar
  (call.without.effects ..)
)

The call to bar looks like it has effects, normally, but with global effect info
we know it actually doesn't.

To use this, one would do

--generate-global-effects [.. some passes that use the effects ..] --discard-global-effects

Discarding is not necessary, but if there is a pass later that adds effects, then not
discarding could lead to bugs, since we'd think there are fewer effects than there are.
(However, normal optimization passes never add effects, only remove them.)

It's also possible to call this multiple times:

--generate-global-effects -O3 --generate-global-effects -O3

That computes affects after the first -O3, and may find fewer effects than earlier.

This doesn't compute the full transitive closure of the effects across functions. That is,
when computing a function's effects, we don't look into its own calls. The simple case
so far is enough to handle the call.without.effects example from before (though it
may take multiple optimization cycles).

3 files changed, 333 insertions, 0 deletions

diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test
index 6bc5bf770..64119ecd2 100644
--- a/test/lit/help/wasm-opt.test
+++ b/test/lit/help/wasm-opt.test
@@ -129,6 +129,8 @@
 ;; CHECK-NEXT:   --directize                                   turns indirect calls into direct
 ;; CHECK-NEXT:                                                 ones
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --discard-global-effects                      discards global effect info
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --duplicate-function-elimination              removes duplicate functions
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --duplicate-import-elimination                removes duplicate imports
@@ -157,6 +159,9 @@
 ;; CHECK-NEXT:   --generate-dyncalls                           generate dynCall fuctions used
 ;; CHECK-NEXT:                                                 by emscripten ABI
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --generate-global-effects                     generate global effect info
+;; CHECK-NEXT:                                                 (helps later passes)
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --generate-i64-dyncalls                       generate dynCall functions used
 ;; CHECK-NEXT:                                                 by emscripten ABI, but only for
 ;; CHECK-NEXT:                                                 functions with i64 in their
diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test
index 3d483206a..e4ceab4b7 100644
--- a/test/lit/help/wasm2js.test
+++ b/test/lit/help/wasm2js.test
@@ -88,6 +88,8 @@
 ;; CHECK-NEXT:   --directize                                   turns indirect calls into direct
 ;; CHECK-NEXT:                                                 ones
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --discard-global-effects                      discards global effect info
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --duplicate-function-elimination              removes duplicate functions
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --duplicate-import-elimination                removes duplicate imports
@@ -116,6 +118,9 @@
 ;; CHECK-NEXT:   --generate-dyncalls                           generate dynCall fuctions used
 ;; CHECK-NEXT:                                                 by emscripten ABI
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --generate-global-effects                     generate global effect info
+;; CHECK-NEXT:                                                 (helps later passes)
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --generate-i64-dyncalls                       generate dynCall functions used
 ;; CHECK-NEXT:                                                 by emscripten ABI, but only for
 ;; CHECK-NEXT:                                                 functions with i64 in their
diff --git a/test/lit/passes/global-effects.wast b/test/lit/passes/global-effects.wast
new file mode 100644
index 000000000..4207ae01f
--- /dev/null
+++ b/test/lit/passes/global-effects.wast
@@ -0,0 +1,323 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; Run without global effects, and run with, and also run with but discard them
+;; first (to check that discard works; that should be the same as without).
+
+;; RUN: foreach %s %t wasm-opt -all                                                    --vacuum -S -o - | filecheck %s --check-prefix WITHOUT
+;; RUN: foreach %s %t wasm-opt -all --generate-global-effects                          --vacuum -S -o - | filecheck %s --check-prefix INCLUDE
+;; RUN: foreach %s %t wasm-opt -all --generate-global-effects --discard-global-effects --vacuum -S -o - | filecheck %s --check-prefix DISCARD
+
+(module
+  ;; WITHOUT:      (type $none_=>_none (func))
+
+  ;; WITHOUT:      (type $none_=>_i32 (func (result i32)))
+
+  ;; WITHOUT:      (type $i32_=>_none (func (param i32)))
+
+  ;; WITHOUT:      (tag $tag (param))
+  ;; INCLUDE:      (type $none_=>_none (func))
+
+  ;; INCLUDE:      (type $none_=>_i32 (func (result i32)))
+
+  ;; INCLUDE:      (type $i32_=>_none (func (param i32)))
+
+  ;; INCLUDE:      (tag $tag (param))
+  ;; DISCARD:      (type $none_=>_none (func))
+
+  ;; DISCARD:      (type $none_=>_i32 (func (result i32)))
+
+  ;; DISCARD:      (type $i32_=>_none (func (param i32)))
+
+  ;; DISCARD:      (tag $tag (param))
+  (tag $tag)
+
+  ;; WITHOUT:      (func $main
+  ;; WITHOUT-NEXT:  (call $nop)
+  ;; WITHOUT-NEXT:  (call $unreachable)
+  ;; WITHOUT-NEXT:  (call $call-nop)
+  ;; WITHOUT-NEXT:  (call $call-unreachable)
+  ;; WITHOUT-NEXT:  (drop
+  ;; WITHOUT-NEXT:   (call $unimportant-effects)
+  ;; WITHOUT-NEXT:  )
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $main
+  ;; INCLUDE-NEXT:  (call $unreachable)
+  ;; INCLUDE-NEXT:  (call $call-nop)
+  ;; INCLUDE-NEXT:  (call $call-unreachable)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $main
+  ;; DISCARD-NEXT:  (call $nop)
+  ;; DISCARD-NEXT:  (call $unreachable)
+  ;; DISCARD-NEXT:  (call $call-nop)
+  ;; DISCARD-NEXT:  (call $call-unreachable)
+  ;; DISCARD-NEXT:  (drop
+  ;; DISCARD-NEXT:   (call $unimportant-effects)
+  ;; DISCARD-NEXT:  )
+  ;; DISCARD-NEXT: )
+  (func $main
+    ;; Calling a function with no effects can be optimized away in INCLUDE (but
+    ;; not WITHOUT or DISCARD, where the global effect info is not available).
+    (call $nop)
+    ;; Calling a function with effects cannot.
+    (call $unreachable)
+    ;; Calling something that calls something with no effects can be optimized
+    ;; away in principle, but atm we don't look that far, so this is not
+    ;; optimized.
+    (call $call-nop)
+    ;; Calling something that calls something with effects cannot.
+    (call $call-unreachable)
+    ;; Calling something that only has unimportant effects can be optimized
+    ;; (see below for details).
+    (drop
+      (call $unimportant-effects)
+    )
+  )
+
+  ;; WITHOUT:      (func $cycle
+  ;; WITHOUT-NEXT:  (call $cycle)
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $cycle
+  ;; INCLUDE-NEXT:  (call $cycle)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $cycle
+  ;; DISCARD-NEXT:  (call $cycle)
+  ;; DISCARD-NEXT: )
+  (func $cycle
+    ;; Calling a function with no effects in a cycle cannot be optimized out -
+    ;; this must keep hanging forever.
+    (call $cycle)
+  )
+
+  ;; WITHOUT:      (func $nop
+  ;; WITHOUT-NEXT:  (nop)
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $nop
+  ;; INCLUDE-NEXT:  (nop)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $nop
+  ;; DISCARD-NEXT:  (nop)
+  ;; DISCARD-NEXT: )
+  (func $nop
+    (nop)
+  )
+
+  ;; WITHOUT:      (func $unreachable
+  ;; WITHOUT-NEXT:  (unreachable)
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $unreachable
+  ;; INCLUDE-NEXT:  (unreachable)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $unreachable
+  ;; DISCARD-NEXT:  (unreachable)
+  ;; DISCARD-NEXT: )
+  (func $unreachable
+    (unreachable)
+  )
+
+  ;; WITHOUT:      (func $call-nop
+  ;; WITHOUT-NEXT:  (call $nop)
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $call-nop
+  ;; INCLUDE-NEXT:  (nop)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $call-nop
+  ;; DISCARD-NEXT:  (call $nop)
+  ;; DISCARD-NEXT: )
+  (func $call-nop
+    ;; This call to a nop can be optimized out, as above, in INCLUDE.
+    (call $nop)
+  )
+
+  ;; WITHOUT:      (func $call-unreachable
+  ;; WITHOUT-NEXT:  (call $unreachable)
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $call-unreachable
+  ;; INCLUDE-NEXT:  (call $unreachable)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $call-unreachable
+  ;; DISCARD-NEXT:  (call $unreachable)
+  ;; DISCARD-NEXT: )
+  (func $call-unreachable
+    (call $unreachable)
+  )
+
+  ;; WITHOUT:      (func $unimportant-effects (result i32)
+  ;; WITHOUT-NEXT:  (local $x i32)
+  ;; WITHOUT-NEXT:  (local.set $x
+  ;; WITHOUT-NEXT:   (i32.const 100)
+  ;; WITHOUT-NEXT:  )
+  ;; WITHOUT-NEXT:  (return
+  ;; WITHOUT-NEXT:   (local.get $x)
+  ;; WITHOUT-NEXT:  )
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $unimportant-effects (result i32)
+  ;; INCLUDE-NEXT:  (local $x i32)
+  ;; INCLUDE-NEXT:  (local.set $x
+  ;; INCLUDE-NEXT:   (i32.const 100)
+  ;; INCLUDE-NEXT:  )
+  ;; INCLUDE-NEXT:  (return
+  ;; INCLUDE-NEXT:   (local.get $x)
+  ;; INCLUDE-NEXT:  )
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $unimportant-effects (result i32)
+  ;; DISCARD-NEXT:  (local $x i32)
+  ;; DISCARD-NEXT:  (local.set $x
+  ;; DISCARD-NEXT:   (i32.const 100)
+  ;; DISCARD-NEXT:  )
+  ;; DISCARD-NEXT:  (return
+  ;; DISCARD-NEXT:   (local.get $x)
+  ;; DISCARD-NEXT:  )
+  ;; DISCARD-NEXT: )
+  (func $unimportant-effects (result i32)
+    (local $x i32)
+    ;; Operations on locals should not prevent optimization, as when we return
+    ;; from the function they no longer matter.
+    (local.set $x
+      (i32.const 100)
+    )
+    ;; A return is an effect that no longer matters once we exit the function.
+    (return
+      (local.get $x)
+    )
+  )
+
+  ;; WITHOUT:      (func $call-throw-and-catch
+  ;; WITHOUT-NEXT:  (try $try
+  ;; WITHOUT-NEXT:   (do
+  ;; WITHOUT-NEXT:    (call $throw)
+  ;; WITHOUT-NEXT:   )
+  ;; WITHOUT-NEXT:   (catch_all
+  ;; WITHOUT-NEXT:    (nop)
+  ;; WITHOUT-NEXT:   )
+  ;; WITHOUT-NEXT:  )
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $call-throw-and-catch
+  ;; INCLUDE-NEXT:  (nop)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $call-throw-and-catch
+  ;; DISCARD-NEXT:  (try $try
+  ;; DISCARD-NEXT:   (do
+  ;; DISCARD-NEXT:    (call $throw)
+  ;; DISCARD-NEXT:   )
+  ;; DISCARD-NEXT:   (catch_all
+  ;; DISCARD-NEXT:    (nop)
+  ;; DISCARD-NEXT:   )
+  ;; DISCARD-NEXT:  )
+  ;; DISCARD-NEXT: )
+  (func $call-throw-and-catch
+    (try
+      (do
+        ;; This call cannot be optimized out, as the target throws. However, the
+        ;; entire try-catch can be, since the call's only effect is to throw,
+        ;; and the catch_all catches that.
+        (call $throw)
+      )
+      (catch_all)
+    )
+  )
+
+  ;; WITHOUT:      (func $call-unreachable-and-catch
+  ;; WITHOUT-NEXT:  (try $try
+  ;; WITHOUT-NEXT:   (do
+  ;; WITHOUT-NEXT:    (call $unreachable)
+  ;; WITHOUT-NEXT:   )
+  ;; WITHOUT-NEXT:   (catch_all
+  ;; WITHOUT-NEXT:    (nop)
+  ;; WITHOUT-NEXT:   )
+  ;; WITHOUT-NEXT:  )
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $call-unreachable-and-catch
+  ;; INCLUDE-NEXT:  (call $unreachable)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $call-unreachable-and-catch
+  ;; DISCARD-NEXT:  (try $try
+  ;; DISCARD-NEXT:   (do
+  ;; DISCARD-NEXT:    (call $unreachable)
+  ;; DISCARD-NEXT:   )
+  ;; DISCARD-NEXT:   (catch_all
+  ;; DISCARD-NEXT:    (nop)
+  ;; DISCARD-NEXT:   )
+  ;; DISCARD-NEXT:  )
+  ;; DISCARD-NEXT: )
+  (func $call-unreachable-and-catch
+    (try
+      (do
+        ;; This call has a non-throw effect. We can optimize away the try-catch
+        ;; (since no exception can be thrown anyhow), but we must leave the
+        ;; call.
+        (call $unreachable)
+      )
+      (catch_all)
+    )
+  )
+
+  ;; WITHOUT:      (func $call-throw-or-unreachable-and-catch (param $x i32)
+  ;; WITHOUT-NEXT:  (try $try
+  ;; WITHOUT-NEXT:   (do
+  ;; WITHOUT-NEXT:    (if
+  ;; WITHOUT-NEXT:     (local.get $x)
+  ;; WITHOUT-NEXT:     (call $throw)
+  ;; WITHOUT-NEXT:     (call $unreachable)
+  ;; WITHOUT-NEXT:    )
+  ;; WITHOUT-NEXT:   )
+  ;; WITHOUT-NEXT:   (catch_all
+  ;; WITHOUT-NEXT:    (nop)
+  ;; WITHOUT-NEXT:   )
+  ;; WITHOUT-NEXT:  )
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $call-throw-or-unreachable-and-catch (param $x i32)
+  ;; INCLUDE-NEXT:  (try $try
+  ;; INCLUDE-NEXT:   (do
+  ;; INCLUDE-NEXT:    (if
+  ;; INCLUDE-NEXT:     (local.get $x)
+  ;; INCLUDE-NEXT:     (call $throw)
+  ;; INCLUDE-NEXT:     (call $unreachable)
+  ;; INCLUDE-NEXT:    )
+  ;; INCLUDE-NEXT:   )
+  ;; INCLUDE-NEXT:   (catch_all
+  ;; INCLUDE-NEXT:    (nop)
+  ;; INCLUDE-NEXT:   )
+  ;; INCLUDE-NEXT:  )
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $call-throw-or-unreachable-and-catch (param $x i32)
+  ;; DISCARD-NEXT:  (try $try
+  ;; DISCARD-NEXT:   (do
+  ;; DISCARD-NEXT:    (if
+  ;; DISCARD-NEXT:     (local.get $x)
+  ;; DISCARD-NEXT:     (call $throw)
+  ;; DISCARD-NEXT:     (call $unreachable)
+  ;; DISCARD-NEXT:    )
+  ;; DISCARD-NEXT:   )
+  ;; DISCARD-NEXT:   (catch_all
+  ;; DISCARD-NEXT:    (nop)
+  ;; DISCARD-NEXT:   )
+  ;; DISCARD-NEXT:  )
+  ;; DISCARD-NEXT: )
+  (func $call-throw-or-unreachable-and-catch (param $x i32)
+    ;; This try-catch-all's body will either call a throw or an unreachable.
+    ;; Since we have both possible effects, we cannot optimize anything here.
+    (try
+      (do
+        (if
+          (local.get $x)
+          (call $throw)
+          (call $unreachable)
+        )
+      )
+      (catch_all)
+    )
+  )
+
+  ;; WITHOUT:      (func $throw
+  ;; WITHOUT-NEXT:  (throw $tag)
+  ;; WITHOUT-NEXT: )
+  ;; INCLUDE:      (func $throw
+  ;; INCLUDE-NEXT:  (throw $tag)
+  ;; INCLUDE-NEXT: )
+  ;; DISCARD:      (func $throw
+  ;; DISCARD-NEXT:  (throw $tag)
+  ;; DISCARD-NEXT: )
+  (func $throw
+    (throw $tag)
+  )
+)