Effects: Differentiate mutable from immutable globals (#4286)

Similar to what we do with structs, if a global is immutable then we know it
cannot interact with calls.

This changes the JS API for getSideEffects(). That was actually broken,
as passing in the optional module param would just pass it along to the
compiled C code, so it was coerced to 0 or 1, and not a pointer to a module.
To fix that, this now does module.ptr to actually get the pointer, and this is
now actually tested as without a module we cannot compute the effects of a
global. This PR also makes the module param mandatory in the JS API,
as again, without a module we can't compute global effects. (The module
param has already been mandatory in the C++ API for some time.)

9 files changed, 179 insertions, 31 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 95dea3c5b..140a8e1b5 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -15,6 +15,10 @@ full changeset diff at the end of each section.
 Current Trunk
 -------------
 
+- The EffectAnalyzer now takes advantage of immutability of globals. To achieve
+  that it must have access to the module. That is already the case in the C++
+  API, but the JS API allowed one to optionally not add a module when calling
+  `getSideEffects()`. It is now mandatory to pass in the module.
 - JS and Wasm builds now emit ECMAScript modules. New usage is:
   ```js
   import Binaryen from "path/to/binaryen.js";
diff --git a/src/ir/effects.h b/src/ir/effects.h
index e33a33818..f24f0ac3f 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -71,7 +71,8 @@ public:
   bool calls = false;
   std::set<Index> localsRead;
   std::set<Index> localsWritten;
-  std::set<Name> globalsRead;
+  std::set<Name> mutableGlobalsRead;
+  std::set<Name> immutableGlobalsRead;
   std::set<Name> globalsWritten;
   bool readsMemory = false;
   bool writesMemory = false;
@@ -128,8 +129,11 @@ public:
   bool accessesLocal() const {
     return localsRead.size() + localsWritten.size() > 0;
   }
+  bool accessesMutableGlobal() const {
+    return globalsWritten.size() + mutableGlobalsRead.size() > 0;
+  }
   bool accessesGlobal() const {
-    return globalsRead.size() + globalsWritten.size() > 0;
+    return accessesMutableGlobal() + immutableGlobalsRead.size() > 0;
   }
   bool accessesMemory() const { return calls || readsMemory || writesMemory; }
   bool accessesTable() const { return calls || readsTable || writesTable; }
@@ -156,10 +160,9 @@ public:
     return globalsWritten.size() || writesMemory || writesTable ||
            writesStruct || writesArray || isAtomic || calls;
   }
-  bool readsGlobalState() const {
-    return globalsRead.size() || readsMemory || readsTable ||
-           readsMutableStruct || readsImmutableStruct || readsArray ||
-           isAtomic || calls;
+  bool readsMutableGlobalState() const {
+    return mutableGlobalsRead.size() || readsMemory || readsTable ||
+           readsMutableStruct || readsArray || isAtomic || calls;
   }
 
   bool hasNonTrapSideEffects() const {
@@ -233,17 +236,17 @@ public:
         return true;
       }
     }
-    if ((other.calls && accessesGlobal()) ||
-        (calls && other.accessesGlobal())) {
+    if ((other.calls && accessesMutableGlobal()) ||
+        (calls && other.accessesMutableGlobal())) {
       return true;
     }
     for (auto global : globalsWritten) {
-      if (other.globalsRead.count(global) ||
+      if (other.mutableGlobalsRead.count(global) ||
           other.globalsWritten.count(global)) {
         return true;
       }
     }
-    for (auto global : globalsRead) {
+    for (auto global : mutableGlobalsRead) {
       if (other.globalsWritten.count(global)) {
         return true;
       }
@@ -292,8 +295,11 @@ public:
     for (auto i : other.localsWritten) {
       localsWritten.insert(i);
     }
-    for (auto i : other.globalsRead) {
-      globalsRead.insert(i);
+    for (auto i : other.mutableGlobalsRead) {
+      mutableGlobalsRead.insert(i);
+    }
+    for (auto i : other.immutableGlobalsRead) {
+      immutableGlobalsRead.insert(i);
     }
     for (auto i : other.globalsWritten) {
       globalsWritten.insert(i);
@@ -445,7 +451,11 @@ private:
       parent.localsWritten.insert(curr->index);
     }
     void visitGlobalGet(GlobalGet* curr) {
-      parent.globalsRead.insert(curr->name);
+      if (parent.module.getGlobal(curr->name)->mutable_ == Mutable) {
+        parent.mutableGlobalsRead.insert(curr->name);
+      } else {
+        parent.immutableGlobalsRead.insert(curr->name);
+      }
     }
     void visitGlobalSet(GlobalSet* curr) {
       parent.globalsWritten.insert(curr->name);
@@ -768,7 +778,7 @@ public:
     if (localsWritten.size() > 0) {
       effects |= SideEffects::WritesLocal;
     }
-    if (globalsRead.size() > 0) {
+    if (mutableGlobalsRead.size() + immutableGlobalsRead.size() > 0) {
       effects |= SideEffects::ReadsGlobal;
     }
     if (globalsWritten.size() > 0) {
diff --git a/src/js/binaryen.js-post.js b/src/js/binaryen.js-post.js
index 3f8b6545b..ee90aa1fc 100644
--- a/src/js/binaryen.js-post.js
+++ b/src/js/binaryen.js-post.js
@@ -3181,7 +3181,9 @@ Module['getExpressionInfo'] = function(expr) {
 
 // Gets the side effects of the specified expression
 Module['getSideEffects'] = function(expr, module) {
-  return Module['_BinaryenExpressionGetSideEffects'](expr, module);
+  assert(module); // guard against incorrect old API usage: a module must be
+                  // provided here.
+  return Module['_BinaryenExpressionGetSideEffects'](expr, module['ptr']);
 };
 
 Module['createType'] = function(types) {
diff --git a/src/passes/LoopInvariantCodeMotion.cpp b/src/passes/LoopInvariantCodeMotion.cpp
index 1007e57b3..f339f8126 100644
--- a/src/passes/LoopInvariantCodeMotion.cpp
+++ b/src/passes/LoopInvariantCodeMotion.cpp
@@ -120,9 +120,10 @@ struct LoopInvariantCodeMotion
         // The rest of the loop's effects matter too, we must also
         // take into account global state like interacting loads and
         // stores.
-        bool unsafeToMove =
-          effects.writesGlobalState() || effectsSoFar.invalidates(effects) ||
-          (effects.readsGlobalState() && loopEffects.writesGlobalState());
+        bool unsafeToMove = effects.writesGlobalState() ||
+                            effectsSoFar.invalidates(effects) ||
+                            (effects.readsMutableGlobalState() &&
+                             loopEffects.writesGlobalState());
         // TODO: look into optimizing this with exceptions. for now, disallow
         if (effects.throws || loopEffects.throws) {
           unsafeToMove = true;
diff --git a/src/passes/SimplifyGlobals.cpp b/src/passes/SimplifyGlobals.cpp
index 0943c04fe..be7cc6ca1 100644
--- a/src/passes/SimplifyGlobals.cpp
+++ b/src/passes/SimplifyGlobals.cpp
@@ -123,11 +123,19 @@ struct GlobalUseScanner : public WalkerPass<PostWalker<GlobalUseScanner>> {
     // See if reading a specific global is the only effect the first has.
     EffectAnalyzer firstEffects(getPassOptions(), *getModule(), first);
 
-    if (firstEffects.globalsRead.size() != 1) {
+    if (firstEffects.immutableGlobalsRead.size() +
+          firstEffects.mutableGlobalsRead.size() !=
+        1) {
       return Name();
     }
-    auto global = *firstEffects.globalsRead.begin();
-    firstEffects.globalsRead.clear();
+    Name global;
+    if (firstEffects.immutableGlobalsRead.size() == 1) {
+      global = *firstEffects.immutableGlobalsRead.begin();
+      firstEffects.immutableGlobalsRead.clear();
+    } else {
+      global = *firstEffects.mutableGlobalsRead.begin();
+      firstEffects.mutableGlobalsRead.clear();
+    }
     if (firstEffects.hasAnything()) {
       return Name();
     }
diff --git a/test/binaryen.js/sideffects.js b/test/binaryen.js/sideffects.js
index 654c51608..e3187041d 100644
--- a/test/binaryen.js/sideffects.js
+++ b/test/binaryen.js/sideffects.js
@@ -19,28 +19,32 @@ console.log("SideEffects.Any=" + binaryen.SideEffects.Any);
 var module = new binaryen.Module();
 assert(
   binaryen.getSideEffects(
-    module.i32.const(1)
+    module.i32.const(1),
+    module
   )
   ==
   binaryen.SideEffects.None
 );
 assert(
   binaryen.getSideEffects(
-    module.br("test")
+    module.br("test"),
+    module
   )
   ==
   binaryen.SideEffects.Branches
 );
 assert(
   binaryen.getSideEffects(
-    module.call("test", [], binaryen.i32)
+    module.call("test", [], binaryen.i32),
+    module
   )
   ==
   binaryen.SideEffects.Calls
 );
 assert(
   binaryen.getSideEffects(
-    module.local.get("test", binaryen.i32)
+    module.local.get("test", binaryen.i32),
+    module
   )
   ==
   binaryen.SideEffects.ReadsLocal
@@ -49,21 +53,28 @@ assert(
   binaryen.getSideEffects(
     module.local.set("test",
       module.i32.const(1)
-    )
+    ),
+    module
   )
   ==
   binaryen.SideEffects.WritesLocal
 );
+
+// Add a global for the test, as computing side effects will look for it.
+module.addGlobal('test', binaryen.i32, true, module.i32.const(42));
+
 assert(
   binaryen.getSideEffects(
-    module.global.get("test", binaryen.i32)
+    module.global.get("test", binaryen.i32),
+    module
   )
   ==
   binaryen.SideEffects.ReadsGlobal
 );
 assert(
   binaryen.getSideEffects(
-    module.global.set("test", module.i32.const(1))
+    module.global.set("test", module.i32.const(1)),
+    module
   )
   ==
   binaryen.SideEffects.WritesGlobal
@@ -72,7 +83,8 @@ assert(
   binaryen.getSideEffects(
     module.i32.load(0, 0,
       module.i32.const(0)
-    )
+    ),
+    module
   )
   ==
   binaryen.SideEffects.ReadsMemory | binaryen.SideEffects.ImplicitTrap
@@ -82,7 +94,8 @@ assert(
     module.i32.store(0, 0,
       module.i32.const(0),
       module.i32.const(1)
-    )
+    ),
+    module
   )
   ==
   binaryen.SideEffects.WritesMemory | binaryen.SideEffects.ImplicitTrap
@@ -92,7 +105,8 @@ assert(
     module.i32.div_s(
       module.i32.const(1),
       module.i32.const(0)
-    )
+    ),
+    module
   )
   ==
   binaryen.SideEffects.ImplicitTrap
diff --git a/test/lit/passes/simplify-locals-global.wast b/test/lit/passes/simplify-locals-global.wast
new file mode 100644
index 000000000..215b32a3c
--- /dev/null
+++ b/test/lit/passes/simplify-locals-global.wast
@@ -0,0 +1,51 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
+;; RUN: wasm-opt %s --simplify-locals -S -o - | filecheck %s
+
+(module
+  ;; CHECK:      (global $imm-glob i32 (i32.const 1234))
+  (global $imm-glob i32 (i32.const 1234))
+
+  ;; CHECK:      (global $mut-glob (mut i32) (i32.const 5678))
+  (global $mut-glob (mut i32) (i32.const 5678))
+
+  ;; CHECK:      (func $reorder-of-immmutable-global (result i32)
+  ;; CHECK-NEXT:  (local $temp i32)
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT:  (call $helper)
+  ;; CHECK-NEXT:  (global.get $imm-glob)
+  ;; CHECK-NEXT: )
+  (func $reorder-of-immmutable-global (result i32)
+    (local $temp i32)
+    ;; As the global is immutable, it cannot be modified in the call, and we can
+    ;; reorder here.
+    (local.set $temp
+      (global.get $imm-glob)
+    )
+    (call $helper)
+    (local.get $temp)
+  )
+
+  ;; CHECK:      (func $no-reorder-of-mutable-global (result i32)
+  ;; CHECK-NEXT:  (local $temp i32)
+  ;; CHECK-NEXT:  (local.set $temp
+  ;; CHECK-NEXT:   (global.get $mut-glob)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (call $helper)
+  ;; CHECK-NEXT:  (local.get $temp)
+  ;; CHECK-NEXT: )
+  (func $no-reorder-of-mutable-global (result i32)
+    (local $temp i32)
+    ;; As the global is mutable, it can be modified in the call, and we cannot
+    ;; reorder here.
+    (local.set $temp
+      (global.get $mut-glob)
+    )
+    (call $helper)
+    (local.get $temp)
+  )
+
+  ;; CHECK:      (func $helper
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $helper)
+)
diff --git a/test/passes/licm.txt b/test/passes/licm.txt
index 956f6365e..0ad7af771 100644
--- a/test/passes/licm.txt
+++ b/test/passes/licm.txt
@@ -5,6 +5,7 @@
  (type $i32_=>_none (func (param i32)))
  (type $i32_=>_i32 (func (param i32) (result i32)))
  (global $glob (mut i32) (i32.const 1))
+ (global $glob-imm i32 (i32.const 1))
  (memory $0 1)
  (func $loop1
   (drop
@@ -692,4 +693,36 @@
    )
   )
  )
+ (func $global-call
+  (local $x i32)
+  (loop $loop
+   (local.set $x
+    (global.get $glob)
+   )
+   (call $global)
+   (drop
+    (local.get $x)
+   )
+   (br_if $loop
+    (local.get $x)
+   )
+  )
+ )
+ (func $global-call-immutable
+  (local $x i32)
+  (local.set $x
+   (global.get $glob-imm)
+  )
+  (drop
+   (local.get $x)
+  )
+  (loop $loop
+   (nop)
+   (call $global)
+   (nop)
+   (br_if $loop
+    (local.get $x)
+   )
+  )
+ )
 )
diff --git a/test/passes/licm.wast b/test/passes/licm.wast
index 6c5c747bd..c4fbfcd99 100644
--- a/test/passes/licm.wast
+++ b/test/passes/licm.wast
@@ -1,6 +1,7 @@
 (module
   (memory 1)
   (global $glob (mut i32) (i32.const 1))
+  (global $glob-imm i32 (i32.const 1))
   (func $loop1
     (loop $loop
       (drop (i32.const 10))
@@ -393,9 +394,33 @@
   (func $global
     (local $x i32)
     (loop $loop
+      ;; Moving this global.get out of the loop is ok. It is mutable, but there
+      ;; is no possible place where it can be set in the loop.
       (local.set $x (global.get $glob))
       (drop (local.get $x))
       (br_if $loop (local.get $x))
     )
   )
+  (func $global-call
+    (local $x i32)
+    (loop $loop
+      ;; As above, but now the loop does a call, which might in theory change
+      ;; mutable global state, so we cannot optimize.
+      (local.set $x (global.get $glob))
+      (call $global)
+      (drop (local.get $x))
+      (br_if $loop (local.get $x))
+    )
+  )
+  (func $global-call-immutable
+    (local $x i32)
+    (loop $loop
+      ;; As above, but now the global is immutable, so the call does not
+      ;; prevent us from optimizing.
+      (local.set $x (global.get $glob-imm))
+      (call $global)
+      (drop (local.get $x))
+      (br_if $loop (local.get $x))
+    )
+  )
 )