ReorderGlobals pass (#4904)

This sorts globals by their usage (and respecting dependencies). If the module has very many globals then using smaller LEBs can matter. If there are fewer than 128 globals then we cannot reduce size, and the pass exits early (so this pass will not slow down MVP builds, which usually have just 1 global, the stack pointer). But with wasm GC it is common to use globals for vtables etc., and often there is a very large number of them.
author: Alon Zakai <azakai@google.com> 2022-11-01 17:12:29 -0700
committer: GitHub <noreply@github.com> 2022-11-02 00:12:29 +0000
commit: 25e5aa67bd16f277ad32d42bfbbf7cd130ddf028 (patch)
tree: 6156f359bfc057a6e36b38ba7512d2ba317c98a3 /src
parent: a030cc7f69a00dc0e699b8b580224126650c738b (diff)
download: binaryen-25e5aa67bd16f277ad32d42bfbbf7cd130ddf028.tar.gz
binaryen-25e5aa67bd16f277ad32d42bfbbf7cd130ddf028.tar.bz2
binaryen-25e5aa67bd16f277ad32d42bfbbf7cd130ddf028.zip
4 files changed, 177 insertions, 1 deletions
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index cedb7d764..cb180179c 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -91,8 +91,9 @@ set(passes_SOURCES
   RemoveUnusedBrs.cpp
   RemoveUnusedNames.cpp
   RemoveUnusedModuleElements.cpp
-  ReorderLocals.cpp
   ReorderFunctions.cpp
+  ReorderGlobals.cpp
+  ReorderLocals.cpp
   ReReloop.cpp
   TrapMode.cpp
   TypeRefining.cpp
diff --git a/src/passes/ReorderGlobals.cpp b/src/passes/ReorderGlobals.cpp
new file mode 100644
index 000000000..d1c26b2cc
--- /dev/null
+++ b/src/passes/ReorderGlobals.cpp
@@ -0,0 +1,164 @@
+/*
+ * Copyright 2022 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.
+ */
+
+//
+// Sorts globals by their static use count. This helps reduce the size of wasm
+// binaries because fewer bytes are needed to encode references to frequently
+// used globals.
+//
+
+#include "memory"
+
+#include "ir/find_all.h"
+#include "pass.h"
+#include "support/topological_sort.h"
+#include "wasm.h"
+
+namespace wasm {
+
+using NameCountMap = std::unordered_map<Name, std::atomic<Index>>;
+
+struct UseCountScanner : public WalkerPass<PostWalker<UseCountScanner>> {
+  bool isFunctionParallel() override { return true; }
+
+  bool modifiesBinaryenIR() override { return false; }
+
+  UseCountScanner(NameCountMap& counts) : counts(counts) {}
+
+  std::unique_ptr<Pass> create() override {
+    return std::make_unique<UseCountScanner>(counts);
+  }
+
+  void visitGlobalGet(GlobalGet* curr) {
+    // We can't add a new element to the map in parallel.
+    assert(counts.count(curr->name) > 0);
+    counts[curr->name]++;
+  }
+  void visitGlobalSet(GlobalSet* curr) {
+    assert(counts.count(curr->name) > 0);
+    counts[curr->name]++;
+  }
+
+private:
+  NameCountMap& counts;
+};
+
+struct ReorderGlobals : public Pass {
+  // Whether to always reorder globals, even if there are very few and the
+  // benefit is minor. That is useful for testing.
+  bool always;
+
+  ReorderGlobals(bool always) : always(always) {}
+
+  void run(Module* module) override {
+    if (module->globals.size() < 128 && !always) {
+      // The module has so few globals that they all fit in a single-byte U32LEB
+      // value, so no reordering we can do can actually decrease code size. Note
+      // that this is the common case with wasm MVP modules where the only
+      // globals are typically the stack pointer and perhaps a handful of others
+      // (however, features like wasm GC there may be a great many globals).
+      return;
+    }
+
+    NameCountMap counts;
+    // Fill in info, as we'll operate on it in parallel.
+    for (auto& global : module->globals) {
+      counts[global->name];
+    }
+
+    // Count uses.
+    UseCountScanner scanner(counts);
+    scanner.run(getPassRunner(), module);
+    scanner.runOnModuleCode(getPassRunner(), module);
+
+    // Do a toplogical sort to ensure we keep dependencies before the things
+    // that need them. For example, if $b's definition depends on $a then $b
+    // must appear later:
+    //
+    //   (global $a i32 (i32.const 10))
+    //   (global $b i32 (global.get $a)) ;; $b depends on $a
+    //
+    struct DependencySort : TopologicalSort<Name, DependencySort> {
+      Module& wasm;
+      const NameCountMap& counts;
+
+      std::unordered_map<Name, std::vector<Name>> deps;
+
+      DependencySort(Module& wasm, const NameCountMap& counts)
+        : wasm(wasm), counts(counts) {
+        // Sort a list of global names by their counts.
+        auto sort = [&](std::vector<Name>& globals) {
+          std::stable_sort(
+            globals.begin(), globals.end(), [&](const Name& a, const Name& b) {
+              return counts.at(a) < counts.at(b);
+            });
+        };
+
+        // Sort the globals.
+        std::vector<Name> sortedNames;
+        for (auto& global : wasm.globals) {
+          sortedNames.push_back(global->name);
+        }
+        sort(sortedNames);
+
+        // Everything is a root (we need to emit all globals).
+        for (auto global : sortedNames) {
+          push(global);
+        }
+
+        // The dependencies are the globals referred to.
+        for (auto& global : wasm.globals) {
+          if (global->imported()) {
+            continue;
+          }
+          std::vector<Name> vec;
+          for (auto* get : FindAll<GlobalGet>(global->init).list) {
+            vec.push_back(get->name);
+          }
+          sort(vec);
+          deps[global->name] = std::move(vec);
+        }
+      }
+
+      void pushPredecessors(Name global) {
+        for (auto pred : deps[global]) {
+          push(pred);
+        }
+      }
+    };
+
+    std::unordered_map<Name, Index> sortedIndexes;
+    for (auto global : DependencySort(*module, counts)) {
+      auto index = sortedIndexes.size();
+      sortedIndexes[global] = index;
+    }
+
+    std::sort(
+      module->globals.begin(),
+      module->globals.end(),
+      [&](const std::unique_ptr<Global>& a, const std::unique_ptr<Global>& b) {
+        return sortedIndexes[a->name] < sortedIndexes[b->name];
+      });
+
+    module->updateMaps();
+  }
+};
+
+Pass* createReorderGlobalsPass() { return new ReorderGlobals(false); }
+
+Pass* createReorderGlobalsAlwaysPass() { return new ReorderGlobals(true); }
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index c6d94ddf7..7190201a1 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -359,6 +359,12 @@ void PassRegistry::registerPasses() {
   registerPass("reorder-functions",
                "sorts functions by access frequency",
                createReorderFunctionsPass);
+  registerPass("reorder-globals",
+               "sorts globals by access frequency",
+               createReorderGlobalsPass);
+  registerTestPass("reorder-globals-always",
+                   "sorts globals by access frequency (even if there are few)",
+                   createReorderGlobalsAlwaysPass);
   registerPass("reorder-locals",
                "sorts locals by access frequency",
                createReorderLocalsPass);
@@ -621,6 +627,9 @@ void PassRunner::addDefaultGlobalOptimizationPostPasses() {
     addIfNoDWARFIssues("simplify-globals");
   }
   addIfNoDWARFIssues("remove-unused-module-elements");
+  if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
+    addIfNoDWARFIssues("reorder-globals");
+  }
   // may allow more inlining/dae/etc., need --converge for that
   addIfNoDWARFIssues("directize");
   // perform Stack IR optimizations here, at the very end of the
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 20dfe0249..12e8b77c7 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -113,6 +113,8 @@ Pass* createRemoveUnusedModuleElementsPass();
 Pass* createRemoveUnusedNonFunctionModuleElementsPass();
 Pass* createRemoveUnusedNamesPass();
 Pass* createReorderFunctionsPass();
+Pass* createReorderGlobalsPass();
+Pass* createReorderGlobalsAlwaysPass();
 Pass* createReorderLocalsPass();
 Pass* createReReloopPass();
 Pass* createRedundantSetEliminationPass();
author	Alon Zakai <azakai@google.com>	2022-11-01 17:12:29 -0700
committer	GitHub <noreply@github.com>	2022-11-02 00:12:29 +0000
commit	25e5aa67bd16f277ad32d42bfbbf7cd130ddf028 (patch)
tree	6156f359bfc057a6e36b38ba7512d2ba317c98a3 /src
parent	a030cc7f69a00dc0e699b8b580224126650c738b (diff)
download	binaryen-25e5aa67bd16f277ad32d42bfbbf7cd130ddf028.tar.gz binaryen-25e5aa67bd16f277ad32d42bfbbf7cd130ddf028.tar.bz2 binaryen-25e5aa67bd16f277ad32d42bfbbf7cd130ddf028.zip