Effects: Clarify trap effect meaning, and consider infinite loops to trap due to timeout (#5039)

I think this simplifies the logic behind what we consider to trap. Before we had kind of
a hack in visitLoop that now has a more clear reasoning behind it: we consider as
trapping things that trap in all VMs all the time, or will eventually. So a single allocation
doesn't trap, but an unbounded amount can, and an infinite loop is considered to
trap as well (a timeout in a VM will be hit eventually, somehow).

This means we cannot optimize way a trivial infinite loop with no effects in it,

while (1) {}

But we can optimize it out in trapsNeverHappen mode. In any event, such a loop
is not a realistic situation; an infinite loop with some other effect in it, like a call to
an import, will not be optimized out, of course.

Also clarify some other things regarding traps and trapsNeverHappen following
recent discussions in https://github.com/emscripten-core/emscripten/issues/17732
Specifically, TNH will never be allowed to remove calls to imports.

6 files changed, 233 insertions, 60 deletions

diff --git a/src/ir/effects.h b/src/ir/effects.h
index 5578b3b3b..aa8a458d0 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -90,18 +90,20 @@ public:
   // each other, but it is not ok to remove them or reorder them with other
   // effects in a noticeable way.
   //
-  // Note also that we ignore runtime-dependent traps, such as hitting a
-  // recursion limit or running out of memory. Such traps are not part of wasm's
-  // official semantics, and they can occur anywhere: *any* instruction could in
-  // theory be implemented by a VM call (as will be the case when running in an
-  // interpreter), and such a call could run out of stack or memory in
-  // principle. To put it another way, an i32 division by zero is the program
-  // doing something bad that causes a trap, but the VM running out of memory is
-  // the VM doing something bad - and therefore the VM behaving in a way that is
-  // not according to the wasm semantics - and we do not model such things. Note
-  // that as a result we do *not* mark things like GC allocation instructions as
-  // having side effects, which has the nice benefit of making it possible to
-  // eliminate an allocation whose result is not captured.
+  // Note also that we ignore *optional* runtime-specific traps: we only
+  // consider as trapping something that will trap in *all* VMs, and *all* the
+  // time. For example, a single allocation might trap in a VM in a particular
+  // execution, if it happens to run out of memory just there, but that is not
+  // enough for us to mark it as having a trap effect. (Note that not marking
+  // each allocation as possibly trapping has the nice benefit of making it
+  // possible to eliminate an allocation whose result is not captured.) OTOH, we
+  // *do* mark a potentially infinite number of allocations as trapping, as all
+  // VMs would trap eventually, and the same for potentially infinite recursion,
+  // etc.
+  //   * We assume that VMs will timeout eventually, so any loop that we cannot
+  //     prove terminates is considered to trap. (Some VMs might not have
+  //     such timeouts, but even they will error before the heat death of the
+  //     universe, which is a kind of trap.)
   bool trap = false;
   // A trap from an instruction like a load or div/rem, which may trap on corner
   // cases. If we do not ignore implicit traps then these are counted as a trap.
@@ -394,20 +396,13 @@ private:
     }
     void visitIf(If* curr) {}
     void visitLoop(Loop* curr) {
-      if (curr->name.is()) {
-        parent.breakTargets.erase(curr->name); // these were internal breaks
-      }
-      // if the loop is unreachable, then there is branching control flow:
-      //  (1) if the body is unreachable because of a (return), uncaught (br)
-      //      etc., then we already noted branching, so it is ok to mark it
-      //      again (if we have *caught* (br)s, then they did not lead to the
-      //      loop body being unreachable). (same logic applies to blocks)
-      //  (2) if the loop is unreachable because it only has branches up to the
-      //      loop top, but no way to get out, then it is an infinite loop, and
-      //      we consider that a branching side effect (note how the same logic
-      //      does not apply to blocks).
-      if (curr->type == Type::unreachable) {
-        parent.branchesOut = true;
+      if (curr->name.is() && parent.breakTargets.erase(curr->name) > 0) {
+        // Breaks to this loop exist, which we just removed as they do not have
+        // further effect outside of this loop. One additional thing we need to
+        // take into account is infinite looping, which is a noticeable side
+        // effect we can't normally remove - eventually the VM will time out and
+        // error (see more details in the comment on trapping above).
+        parent.implicitTrap = true;
       }
     }
     void visitBreak(Break* curr) { parent.breakTargets.insert(curr->name); }
diff --git a/src/pass.h b/src/pass.h
index 041b80321..623c1f971 100644
--- a/src/pass.h
+++ b/src/pass.h
@@ -145,6 +145,25 @@ struct PassOptions {
   // neither of those can happen (and it is undefined behavior if they do).
   //
   // TODO: deprecate and remove ignoreImplicitTraps.
+  //
+  // Since trapsNeverHappen assumes a trap is never reached, it can in principle
+  // remove code like this:
+  //
+  //   (i32.store ..)
+  //   (unreachable)
+  //
+  // The trap isn't reached, by assumption, and if we reach the store then we'd
+  // reach the trap, so we can assume that isn't reached either, and TNH can
+  // remove both. We do have a specific limitation here, however, which is that
+  // trapsNeverHappen cannot remove calls to *imports*. We assume that an import
+  // might do things we cannot understand, so we never eliminate it. For
+  // example, in LLVM output we might see this:
+  //
+  //   (call $abort) ;; a noreturn import - the process is halted with an error
+  //   (unreachable)
+  //
+  // That trap is never actually reached since the abort halts execution. In TNH
+  // we can remove the trap but not the call right before it.
   bool trapsNeverHappen = false;
   // Optimize assuming that the low 1K of memory is not valid memory for the
   // application to use. In that case, we can optimize load/store offsets in
diff --git a/test/lit/passes/vacuum-tnh.wast b/test/lit/passes/vacuum-tnh.wast
index 83cb298c2..5558735f4 100644
--- a/test/lit/passes/vacuum-tnh.wast
+++ b/test/lit/passes/vacuum-tnh.wast
@@ -1,15 +1,50 @@
 ;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
-;; RUN: wasm-opt %s --vacuum --traps-never-happen -all -S -o - | filecheck %s
+
+;; Run in both TNH and non-TNH mode.
+
+;; RUN: wasm-opt %s --vacuum --traps-never-happen -all -S -o - | filecheck %s --check-prefix=YESTNH
+;; RUN: wasm-opt %s --vacuum                      -all -S -o - | filecheck %s --check-prefix=NO_TNH
 
 (module
   (memory 1 1)
 
-  ;; CHECK:      (type $struct (struct (field (mut i32))))
+  ;; YESTNH:      (type $struct (struct (field (mut i32))))
+  ;; NO_TNH:      (type $struct (struct (field (mut i32))))
   (type $struct (struct (field (mut i32))))
 
-  ;; CHECK:      (func $drop (param $x i32) (param $y anyref)
-  ;; CHECK-NEXT:  (nop)
-  ;; CHECK-NEXT: )
+  ;; YESTNH:      (func $drop (param $x i32) (param $y anyref)
+  ;; YESTNH-NEXT:  (nop)
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $drop (param $x i32) (param $y anyref)
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (i32.load
+  ;; NO_TNH-NEXT:    (local.get $x)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (ref.as_non_null
+  ;; NO_TNH-NEXT:    (local.get $y)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (ref.as_func
+  ;; NO_TNH-NEXT:    (local.get $y)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (ref.as_data
+  ;; NO_TNH-NEXT:    (local.get $y)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (ref.as_i31
+  ;; NO_TNH-NEXT:    (local.get $y)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (unreachable)
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT: )
   (func $drop (param $x i32) (param $y anyref)
     ;; A load might trap, normally, but if traps never happen then we can
     ;; remove it.
@@ -48,17 +83,35 @@
   )
 
   ;; Other side effects prevent us making any changes.
-  ;; CHECK:      (func $other-side-effects (param $x i32) (result i32)
-  ;; CHECK-NEXT:  (drop
-  ;; CHECK-NEXT:   (call $other-side-effects
-  ;; CHECK-NEXT:    (i32.const 1)
-  ;; CHECK-NEXT:   )
-  ;; CHECK-NEXT:  )
-  ;; CHECK-NEXT:  (local.set $x
-  ;; CHECK-NEXT:   (i32.const 2)
-  ;; CHECK-NEXT:  )
-  ;; CHECK-NEXT:  (i32.const 1)
-  ;; CHECK-NEXT: )
+  ;; YESTNH:      (func $other-side-effects (param $x i32) (result i32)
+  ;; YESTNH-NEXT:  (drop
+  ;; YESTNH-NEXT:   (call $other-side-effects
+  ;; YESTNH-NEXT:    (i32.const 1)
+  ;; YESTNH-NEXT:   )
+  ;; YESTNH-NEXT:  )
+  ;; YESTNH-NEXT:  (local.set $x
+  ;; YESTNH-NEXT:   (i32.const 2)
+  ;; YESTNH-NEXT:  )
+  ;; YESTNH-NEXT:  (i32.const 1)
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $other-side-effects (param $x i32) (result i32)
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (call $other-side-effects
+  ;; NO_TNH-NEXT:    (i32.const 1)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (block (result i32)
+  ;; NO_TNH-NEXT:    (local.set $x
+  ;; NO_TNH-NEXT:     (i32.const 2)
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:    (i32.load
+  ;; NO_TNH-NEXT:     (local.get $x)
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (i32.const 1)
+  ;; NO_TNH-NEXT: )
   (func $other-side-effects (param $x i32) (result i32)
     ;; A call has all manner of other side effects.
     (drop
@@ -78,20 +131,40 @@
   )
 
   ;; A helper function for the above, that returns nothing.
-  ;; CHECK:      (func $return-nothing
-  ;; CHECK-NEXT:  (nop)
-  ;; CHECK-NEXT: )
+  ;; YESTNH:      (func $return-nothing
+  ;; YESTNH-NEXT:  (nop)
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $return-nothing
+  ;; NO_TNH-NEXT:  (nop)
+  ;; NO_TNH-NEXT: )
   (func $return-nothing)
 
-  ;; CHECK:      (func $partial (param $x (ref $struct))
-  ;; CHECK-NEXT:  (local $y (ref null $struct))
-  ;; CHECK-NEXT:  (local.set $y
-  ;; CHECK-NEXT:   (local.get $x)
-  ;; CHECK-NEXT:  )
-  ;; CHECK-NEXT:  (local.set $y
-  ;; CHECK-NEXT:   (local.get $x)
-  ;; CHECK-NEXT:  )
-  ;; CHECK-NEXT: )
+  ;; YESTNH:      (func $partial (param $x (ref $struct))
+  ;; YESTNH-NEXT:  (local $y (ref null $struct))
+  ;; YESTNH-NEXT:  (local.set $y
+  ;; YESTNH-NEXT:   (local.get $x)
+  ;; YESTNH-NEXT:  )
+  ;; YESTNH-NEXT:  (local.set $y
+  ;; YESTNH-NEXT:   (local.get $x)
+  ;; YESTNH-NEXT:  )
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $partial (param $x (ref $struct))
+  ;; NO_TNH-NEXT:  (local $y (ref null $struct))
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (struct.get $struct 0
+  ;; NO_TNH-NEXT:    (local.tee $y
+  ;; NO_TNH-NEXT:     (local.get $x)
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (struct.get $struct 0
+  ;; NO_TNH-NEXT:    (local.tee $y
+  ;; NO_TNH-NEXT:     (local.get $x)
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT: )
   (func $partial (param $x (ref $struct))
     (local $y (ref null $struct))
     ;; The struct.get's side effect can be ignored due to tnh, and the value is
@@ -117,12 +190,89 @@
     )
   )
 
-  ;; CHECK:      (func $toplevel
-  ;; CHECK-NEXT:  (nop)
-  ;; CHECK-NEXT: )
+  ;; YESTNH:      (func $toplevel
+  ;; YESTNH-NEXT:  (nop)
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $toplevel
+  ;; NO_TNH-NEXT:  (unreachable)
+  ;; NO_TNH-NEXT: )
   (func $toplevel
     ;; A removable side effect at the top level of a function. We can turn this
     ;; into a nop.
     (unreachable)
   )
+
+  ;; YESTNH:      (func $drop-loop
+  ;; YESTNH-NEXT:  (nop)
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $drop-loop
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (loop $loop (result i32)
+  ;; NO_TNH-NEXT:    (br_if $loop
+  ;; NO_TNH-NEXT:     (i32.const 1)
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:    (i32.const 10)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT: )
+  (func $drop-loop
+    ;; A loop has effects, since it might infinite loop (and hit a timeout trap
+    ;; eventually), so we do not vacuum it out unless we are ignoring traps.
+    (drop
+      (loop $loop (result i32)
+        (br_if $loop
+          (i32.const 1)
+        )
+        (i32.const 10)
+      )
+    )
+  )
+
+  ;; YESTNH:      (func $loop-effects
+  ;; YESTNH-NEXT:  (drop
+  ;; YESTNH-NEXT:   (loop $loop (result i32)
+  ;; YESTNH-NEXT:    (drop
+  ;; YESTNH-NEXT:     (i32.atomic.load
+  ;; YESTNH-NEXT:      (i32.const 0)
+  ;; YESTNH-NEXT:     )
+  ;; YESTNH-NEXT:    )
+  ;; YESTNH-NEXT:    (br_if $loop
+  ;; YESTNH-NEXT:     (i32.const 1)
+  ;; YESTNH-NEXT:    )
+  ;; YESTNH-NEXT:    (i32.const 10)
+  ;; YESTNH-NEXT:   )
+  ;; YESTNH-NEXT:  )
+  ;; YESTNH-NEXT: )
+  ;; NO_TNH:      (func $loop-effects
+  ;; NO_TNH-NEXT:  (drop
+  ;; NO_TNH-NEXT:   (loop $loop (result i32)
+  ;; NO_TNH-NEXT:    (drop
+  ;; NO_TNH-NEXT:     (i32.atomic.load
+  ;; NO_TNH-NEXT:      (i32.const 0)
+  ;; NO_TNH-NEXT:     )
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:    (br_if $loop
+  ;; NO_TNH-NEXT:     (i32.const 1)
+  ;; NO_TNH-NEXT:    )
+  ;; NO_TNH-NEXT:    (i32.const 10)
+  ;; NO_TNH-NEXT:   )
+  ;; NO_TNH-NEXT:  )
+  ;; NO_TNH-NEXT: )
+  (func $loop-effects
+    ;; As above, but the loop also has an atomic load effect. That prevents
+    ;; optimization.
+    (drop
+      (loop $loop (result i32)
+        (drop
+          (i32.atomic.load
+            (i32.const 0)
+          )
+        )
+        (br_if $loop
+          (i32.const 1)
+        )
+        (i32.const 10)
+      )
+    )
+  )
 )
diff --git a/test/passes/remove-unused-names_remove-unused-brs_vacuum.txt b/test/passes/remove-unused-names_remove-unused-brs_vacuum.txt
index 83be83c5a..ca856396e 100644
--- a/test/passes/remove-unused-names_remove-unused-brs_vacuum.txt
+++ b/test/passes/remove-unused-names_remove-unused-brs_vacuum.txt
@@ -71,8 +71,12 @@
    (block $label$3
     (block
      (if
-      (i32.eqz
-       (local.get $var$8)
+      (local.get $var$8)
+      (loop $label$8
+       (if
+        (local.get $var$3)
+        (br $label$8)
+       )
       )
       (if
        (i32.eqz
diff --git a/test/wasm2js/br_table_to_loop.2asm.js.opt b/test/wasm2js/br_table_to_loop.2asm.js.opt
index fb8e7f956..cac6dc28c 100644
--- a/test/wasm2js/br_table_to_loop.2asm.js.opt
+++ b/test/wasm2js/br_table_to_loop.2asm.js.opt
@@ -1,4 +1,6 @@
 
+function wasm2js_trap() { throw new Error('abort'); }
+
 function asmFunc(importObject) {
  var env = importObject.env || importObject;
  var Math_imul = Math.imul;
@@ -14,7 +16,7 @@ function asmFunc(importObject) {
  var nan = NaN;
  var infinity = Infinity;
  function $0() {
-  while (1) continue;
+  wasm2js_trap();
  }
  
  function $1() {
diff --git a/test/wasm2js/br_table_to_loop.wast b/test/wasm2js/br_table_to_loop.wast
index 83d3702c2..a74d5ffe0 100644
--- a/test/wasm2js/br_table_to_loop.wast
+++ b/test/wasm2js/br_table_to_loop.wast
@@ -1,6 +1,8 @@
 (module
  (func "exp1"
   (block $block
+   ;; An infinite loop. When optimizing, wasm2js enables ignore-implicit-traps
+   ;; and so it can simplify this.
    (loop $loop
     (br_table $block $loop $block (i32.const 1))
    )
@@ -8,6 +10,7 @@
  )
  (func "exp2"
   (block $block
+   ;; A loop that never executes. This can be optimized into a nop.
    (loop $loop
     (br_table $loop $block $loop (i32.const 1))
    )