Optimize mutable globals (#2066)

If a global is marked mutable but not assigned to, make it immutable.

If an immutable global is a copy of another, use the original, so we can remove the duplicates.

Fixes #2011

5 files changed, 149 insertions, 4 deletions

diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 935c3bec8..9d98930ed 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -58,6 +58,7 @@ SET(passes_SOURCES
   ReorderFunctions.cpp
   TrapMode.cpp
   SafeHeap.cpp
+  SimplifyGlobals.cpp
   SimplifyLocals.cpp
   Souperify.cpp
   SpillPointers.cpp
diff --git a/src/passes/SimplifyGlobals.cpp b/src/passes/SimplifyGlobals.cpp
new file mode 100644
index 000000000..12c59fefc
--- /dev/null
+++ b/src/passes/SimplifyGlobals.cpp
@@ -0,0 +1,143 @@
+/*
+ * Copyright 2019 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// Simplify and optimize globals and their use.
+//
+//  * Turns never-written and unwritable (not imported or exported)
+//    globals immutable.
+//  * If an immutable global is a copy of another, use the earlier one,
+//    to allow removal of the copies later.
+//
+
+#include <atomic>
+
+#include "pass.h"
+#include "wasm.h"
+
+namespace wasm {
+
+namespace {
+
+struct GlobalInfo {
+  bool imported = false;
+  bool exported = false;
+  std::atomic<bool> written;
+};
+
+using GlobalInfoMap = std::map<Name, GlobalInfo>;
+
+struct GlobalUseScanner : public WalkerPass<PostWalker<GlobalUseScanner>> {
+  bool isFunctionParallel() override { return true; }
+
+  GlobalUseScanner(GlobalInfoMap* infos) : infos(infos) {}
+
+  GlobalUseScanner* create() override { return new GlobalUseScanner(infos); }
+
+  void visitSetGlobal(SetGlobal* curr) { (*infos)[curr->name].written = true; }
+
+private:
+  GlobalInfoMap* infos;
+};
+
+using NameNameMap = std::map<Name, Name>;
+
+struct GlobalUseModifier : public WalkerPass<PostWalker<GlobalUseModifier>> {
+  bool isFunctionParallel() override { return true; }
+
+  GlobalUseModifier(NameNameMap* copiedParentMap)
+    : copiedParentMap(copiedParentMap) {}
+
+  GlobalUseModifier* create() override {
+    return new GlobalUseModifier(copiedParentMap);
+  }
+
+  void visitGetGlobal(GetGlobal* curr) {
+    auto iter = copiedParentMap->find(curr->name);
+    if (iter != copiedParentMap->end()) {
+      curr->name = iter->second;
+    }
+  }
+
+private:
+  NameNameMap* copiedParentMap;
+};
+
+} // anonymous namespace
+
+struct SimplifyGlobals : public Pass {
+  void run(PassRunner* runner, Module* module) override {
+    // First, find out all the relevant info.
+    GlobalInfoMap map;
+    for (auto& global : module->globals) {
+      auto& info = map[global->name];
+      if (global->imported()) {
+        info.imported = true;
+      }
+    }
+    for (auto& ex : module->exports) {
+      if (ex->kind == ExternalKind::Global) {
+        map[ex->value].exported = true;
+      }
+    }
+    {
+      PassRunner subRunner(module, runner->options);
+      subRunner.add<GlobalUseScanner>(&map);
+      subRunner.run();
+    }
+    // We now know which are immutable in practice.
+    for (auto& global : module->globals) {
+      auto& info = map[global->name];
+      if (global->mutable_ && !info.imported && !info.exported &&
+          !info.written) {
+        global->mutable_ = false;
+      }
+    }
+    // Optimize uses of immutable globals, prefer the earlier import when
+    // there is a copy.
+    NameNameMap copiedParentMap;
+    for (auto& global : module->globals) {
+      auto child = global->name;
+      if (!global->mutable_ && !global->imported()) {
+        if (auto* get = global->init->dynCast<GetGlobal>()) {
+          auto parent = get->name;
+          if (!module->getGlobal(get->name)->mutable_) {
+            copiedParentMap[child] = parent;
+          }
+        }
+      }
+    }
+    if (!copiedParentMap.empty()) {
+      // Go all the way back.
+      for (auto& global : module->globals) {
+        auto child = global->name;
+        if (copiedParentMap.count(child)) {
+          while (copiedParentMap.count(copiedParentMap[child])) {
+            copiedParentMap[child] = copiedParentMap[copiedParentMap[child]];
+          }
+        }
+      }
+      // Apply to the gets.
+      PassRunner subRunner(module, runner->options);
+      subRunner.add<GlobalUseModifier>(&copiedParentMap);
+      subRunner.run();
+    }
+  }
+};
+
+Pass* createSimplifyGlobalsPass() { return new SimplifyGlobals(); }
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index e4fbc5343..eb49072ba 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -244,6 +244,9 @@ void PassRegistry::registerPasses() {
   registerPass("safe-heap",
                "instrument loads and stores to check for invalid behavior",
                createSafeHeapPass);
+  registerPass("simplify-globals",
+               "miscellaneous globals-related optimizations",
+               createSimplifyGlobalsPass);
   registerPass("simplify-locals",
                "miscellaneous locals-related optimizations",
                createSimplifyLocalsPass);
@@ -392,6 +395,7 @@ void PassRunner::addDefaultGlobalOptimizationPostPasses() {
   }
   // optimizations show more functions as duplicate
   add("duplicate-function-elimination");
+  add("simplify-globals");
   add("remove-unused-module-elements");
   add("memory-packing");
   // may allow more inlining/dae/etc., need --converge for that
diff --git a/src/passes/passes.h b/src/passes/passes.h
index e562f4a42..cb2950bd4 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -86,6 +86,7 @@ Pass* createReReloopPass();
 Pass* createRedundantSetEliminationPass();
 Pass* createSafeHeapPass();
 Pass* createSimplifyLocalsPass();
+Pass* createSimplifyGlobalsPass();
 Pass* createSimplifyLocalsNoNestingPass();
 Pass* createSimplifyLocalsNoTeePass();
 Pass* createSimplifyLocalsNoStructurePass();
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index cd9eb690a..a869aa08a 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1813,10 +1813,6 @@ void SExpressionWasmBuilder::parseExport(Element& s) {
       ex->kind = ExternalKind::Table;
     } else if (inner[0]->str() == GLOBAL) {
       ex->kind = ExternalKind::Global;
-      if (wasm.getGlobalOrNull(ex->value) &&
-          wasm.getGlobal(ex->value)->mutable_) {
-        throw ParseException("cannot export a mutable global", s.line, s.col);
-      }
     } else {
       throw ParseException("invalid export");
     }