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).

6 files changed, 155 insertions, 5 deletions

diff --git a/src/ir/effects.h b/src/ir/effects.h
index ad3ab235d..5578b3b3b 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -31,7 +31,8 @@ public:
                  Module& module,
                  Expression* ast = nullptr)
     : ignoreImplicitTraps(passOptions.ignoreImplicitTraps),
-      trapsNeverHappen(passOptions.trapsNeverHappen), module(module),
+      trapsNeverHappen(passOptions.trapsNeverHappen),
+      funcEffectsMap(passOptions.funcEffectsMap), module(module),
       features(module.features) {
     if (ast) {
       walk(ast);
@@ -40,6 +41,7 @@ public:
 
   bool ignoreImplicitTraps;
   bool trapsNeverHappen;
+  std::shared_ptr<FuncEffectsMap> funcEffectsMap;
   Module& module;
   FeatureSet features;
 
@@ -261,7 +263,7 @@ public:
     return false;
   }
 
-  void mergeIn(EffectAnalyzer& other) {
+  void mergeIn(const EffectAnalyzer& other) {
     branchesOut = branchesOut || other.branchesOut;
     calls = calls || other.calls;
     readsMemory = readsMemory || other.readsMemory;
@@ -422,14 +424,35 @@ private:
         return;
       }
 
+      if (curr->isReturn) {
+        parent.branchesOut = true;
+      }
+
+      if (parent.funcEffectsMap) {
+        auto iter = parent.funcEffectsMap->find(curr->target);
+        if (iter != parent.funcEffectsMap->end()) {
+          // We have effect information for this call target, and can just use
+          // that. The one change we may want to make is to remove throws_, if
+          // the target function throws and we know that will be caught anyhow,
+          // the same as the code below for the general path.
+          const auto& targetEffects = iter->second;
+          if (targetEffects.throws_ && parent.tryDepth > 0) {
+            auto filteredEffects = targetEffects;
+            filteredEffects.throws_ = false;
+            parent.mergeIn(filteredEffects);
+          } else {
+            // Just merge in all the effects.
+            parent.mergeIn(targetEffects);
+          }
+          return;
+        }
+      }
+
       parent.calls = true;
       // When EH is enabled, any call can throw.
       if (parent.features.hasExceptionHandling() && parent.tryDepth == 0) {
         parent.throws_ = true;
       }
-      if (curr->isReturn) {
-        parent.branchesOut = true;
-      }
     }
     void visitCallIndirect(CallIndirect* curr) {
       parent.calls = true;
diff --git a/src/pass.h b/src/pass.h
index 6769c91ee..041b80321 100644
--- a/src/pass.h
+++ b/src/pass.h
@@ -95,6 +95,11 @@ struct InliningOptions {
   Index partialInliningIfs = 0;
 };
 
+// Forward declaration for FuncEffectsMap.
+class EffectAnalyzer;
+
+using FuncEffectsMap = std::unordered_map<Name, EffectAnalyzer>;
+
 struct PassOptions {
   // Run passes in debug mode, doing extra validation and timing checks.
   bool debug = false;
@@ -166,6 +171,14 @@ struct PassOptions {
   // passes.
   std::map<std::string, std::string> arguments;
 
+  // Effect info computed for functions. One pass can generate this and then
+  // other passes later can benefit from it. It is up to the sequence of passes
+  // to update or discard this when necessary - in particular, when new effects
+  // are added to a function this must be changed or we may optimize
+  // incorrectly (however, it is extremely rare for a pass to *add* effects;
+  // passes normally only remove effects).
+  std::shared_ptr<FuncEffectsMap> funcEffectsMap;
+
   // -Os is our default
   static constexpr const int DEFAULT_OPTIMIZE_LEVEL = 2;
   static constexpr const int DEFAULT_SHRINK_LEVEL = 1;
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 9379fbe27..152594431 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -37,6 +37,7 @@ set(passes_SOURCES
   Flatten.cpp
   FuncCastEmulation.cpp
   GenerateDynCalls.cpp
+  GlobalEffects.cpp
   GlobalRefining.cpp
   GlobalStructInference.cpp
   GlobalTypeOptimization.cpp
diff --git a/src/passes/GlobalEffects.cpp b/src/passes/GlobalEffects.cpp
new file mode 100644
index 000000000..1dd91e5d7
--- /dev/null
+++ b/src/passes/GlobalEffects.cpp
@@ -0,0 +1,101 @@
+/*
+ * 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.
+ */
+
+//
+// Handle the computation of global effects. The effects are stored on the
+// PassOptions structure; see more details there.
+//
+
+#include "ir/module-utils.h"
+#include "pass.h"
+#include "wasm.h"
+
+namespace wasm {
+
+struct GenerateGlobalEffects : public Pass {
+  void run(PassRunner* runner, Module* module) override {
+    // TODO: Full transitive closure of effects. For now, we just look at each
+    //       function by itself.
+
+    auto& funcEffectsMap = runner->options.funcEffectsMap;
+
+    // First, clear any previous effects.
+    funcEffectsMap.reset();
+
+    // When we find useful effects, we'll save them. If we can't find anything,
+    // the final map we emit will not have an entry there at all.
+    using PossibleEffects = std::unique_ptr<EffectAnalyzer>;
+
+    ModuleUtils::ParallelFunctionAnalysis<PossibleEffects> analysis(
+      *module, [&](Function* func, PossibleEffects& storedEffects) {
+        if (func->imported()) {
+          // Imports can do anything, so we need to assume the worst anyhow,
+          // which is the same as not specifying any effects for them in the
+          // map.
+          return;
+        }
+
+        // Gather the effects.
+        auto effects = std::make_unique<EffectAnalyzer>(
+          runner->options, *module, func->body);
+
+        // If the body has a call, give up - that means we can't infer a more
+        // specific set of effects than the pessimistic case of just assuming
+        // any call to here is an arbitrary call. (See the TODO above for
+        // improvements.)
+        if (effects->calls) {
+          return;
+        }
+
+        // We can ignore branching out of the function body - this can only be
+        // a return, and that is only noticeable in the function, not outside.
+        effects->branchesOut = false;
+
+        // Ignore local effects - when the function exits, those become
+        // unnoticeable anyhow.
+        effects->localsWritten.clear();
+        effects->localsRead.clear();
+
+        // Save the useful effects we found.
+        storedEffects = std::move(effects);
+      });
+
+    // Generate the final data structure.
+    for (auto& [func, possibleEffects] : analysis.map) {
+      if (possibleEffects) {
+        // Only allocate a new funcEffectsMap if we actually have data for it
+        // (which might make later effect computation slightly faster, to
+        // quickly skip the funcEffectsMap code path).
+        if (!funcEffectsMap) {
+          funcEffectsMap = std::make_shared<FuncEffectsMap>();
+        }
+        funcEffectsMap->emplace(func->name, *possibleEffects);
+      }
+    }
+  }
+};
+
+struct DiscardGlobalEffects : public Pass {
+  void run(PassRunner* runner, Module* module) override {
+    runner->options.funcEffectsMap.reset();
+  }
+};
+
+Pass* createGenerateGlobalEffectsPass() { return new GenerateGlobalEffects(); }
+
+Pass* createDiscardGlobalEffectsPass() { return new DiscardGlobalEffects(); }
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index eaf20eb51..c548b66c5 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -128,6 +128,9 @@ void PassRegistry::registerPasses() {
                createDeNaNPass);
   registerPass(
     "directize", "turns indirect calls into direct ones", createDirectizePass);
+  registerPass("discard-global-effects",
+               "discards global effect info",
+               createDiscardGlobalEffectsPass);
   registerPass(
     "dfo", "optimizes using the DataFlow SSA IR", createDataFlowOptsPass);
   registerPass("dwarfdump",
@@ -165,6 +168,9 @@ void PassRegistry::registerPasses() {
     "functions with i64 in their signature (which cannot be invoked "
     "via the wasm table without JavaScript BigInt support).",
     createGenerateI64DynCallsPass);
+  registerPass("generate-global-effects",
+               "generate global effect info (helps later passes)",
+               createGenerateGlobalEffectsPass);
   registerPass(
     "generate-stack-ir", "generate Stack IR", createGenerateStackIRPass);
   registerPass(
@@ -581,6 +587,10 @@ void PassRunner::addDefaultGlobalOptimizationPrePasses() {
     addIfNoDWARFIssues("cfp");
     addIfNoDWARFIssues("gsi");
   }
+  // TODO: generate-global-effects here, right before function passes, then
+  //       discard in addDefaultGlobalOptimizationPostPasses? the benefit seems
+  //       quite minor so far, except perhaps when using call.without.effects
+  //       which can lead to more opportunities for global effects to matter.
 }
 
 void PassRunner::addDefaultGlobalOptimizationPostPasses() {
diff --git a/src/passes/passes.h b/src/passes/passes.h
index d665939ac..99ee87553 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -38,6 +38,7 @@ Pass* createDeadCodeEliminationPass();
 Pass* createDeNaNPass();
 Pass* createDeAlignPass();
 Pass* createDirectizePass();
+Pass* createDiscardGlobalEffectsPass();
 Pass* createDWARFDumpPass();
 Pass* createDuplicateImportEliminationPass();
 Pass* createDuplicateFunctionEliminationPass();
@@ -50,6 +51,7 @@ Pass* createFullPrinterPass();
 Pass* createFunctionMetricsPass();
 Pass* createGenerateDynCallsPass();
 Pass* createGenerateI64DynCallsPass();
+Pass* createGenerateGlobalEffectsPass();
 Pass* createGenerateStackIRPass();
 Pass* createGlobalRefiningPass();
 Pass* createGlobalStructInferencePass();