Refactor a CallGraphPropertyAnalysis helper [NFC] (#2441)

This moves code out of Asyncify into a general helper class. The class
automates scanning the functions for a property, then propagating it to
functions that call them. In Asyncify, the property is "may call something
that leads to sleep", and we propagate backwards to callers, to find
all those that may sleep.

This will be useful in a future exceptions-optimizing pass I want to write,
where the property will be "may throw". We will then be able to remove
exceptions overhead in cases that definitely do not throw.

2 files changed, 103 insertions, 61 deletions

diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 16ecd54b0..52765035c 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -20,6 +20,7 @@
 #include "ir/find_all.h"
 #include "ir/manipulation.h"
 #include "pass.h"
+#include "support/unique_deferring_queue.h"
 #include "wasm.h"
 
 namespace wasm {
@@ -288,22 +289,33 @@ template<typename T> inline void iterDefinedEvents(Module& wasm, T visitor) {
   }
 }
 
-// Performs a parallel map on function in the module, emitting a map object
-// of function => result.
-// TODO: use in inlining and elsewhere
-template<typename T> struct ParallelFunctionMap {
+// Helper class for analyzing the call graph.
+//
+// Provides hooks for running some initial calculation on each function (which
+// is done in parallel), writing to a FunctionInfo structure for each function.
+// Then you can call propagateBack() to propagate a property of interest to the
+// calling functions, transitively.
+//
+// For example, if some functions are known to call an import "foo", then you
+// can use this to find which functions call something that might eventually
+// reach foo, by initially marking the direct callers as "calling foo" and
+// propagating that backwards.
+template<typename T> struct CallGraphPropertyAnalysis {
+  Module& wasm;
+
+  // The basic information for each function about whom it calls and who is
+  // called by it.
+  struct FunctionInfo {
+    std::set<Function*> callsTo;
+    std::set<Function*> calledBy;
+  };
 
   typedef std::map<Function*, T> Map;
   Map map;
 
   typedef std::function<void(Function*, T&)> Func;
 
-  struct Info {
-    Map* map;
-    Func work;
-  };
-
-  ParallelFunctionMap(Module& wasm, Func work) {
+  CallGraphPropertyAnalysis(Module& wasm, Func work) : wasm(wasm) {
     // Fill in map, as we operate on it in parallel (each function to its own
     // entry).
     for (auto& func : wasm.functions) {
@@ -317,27 +329,65 @@ template<typename T> struct ParallelFunctionMap {
       }
     }
 
-    // Run on the implemented functions.
     struct Mapper : public WalkerPass<PostWalker<Mapper>> {
       bool isFunctionParallel() override { return true; }
 
-      Mapper(Info* info) : info(info) {}
+      Mapper(Module* module, Map* map, Func work)
+        : module(module), map(map), work(work) {}
+
+      Mapper* create() override { return new Mapper(module, map, work); }
 
-      Mapper* create() override { return new Mapper(info); }
+      void visitCall(Call* curr) {
+        (*map)[this->getFunction()].callsTo.insert(
+          module->getFunction(curr->target));
+      }
 
-      void doWalkFunction(Function* curr) {
-        assert((*info->map).count(curr));
-        info->work(curr, (*info->map)[curr]);
+      void visitFunction(Function* curr) {
+        assert((*map).count(curr));
+        work(curr, (*map)[curr]);
       }
 
     private:
-      Info* info;
+      Module* module;
+      Map* map;
+      Func work;
     };
 
-    Info info = {&map, work};
-
     PassRunner runner(&wasm);
-    Mapper(&info).run(&runner, &wasm);
+    Mapper(&wasm, &map, work).run(&runner, &wasm);
+
+    // Find what is called by what.
+    for (auto& pair : map) {
+      auto* func = pair.first;
+      auto& info = pair.second;
+      for (auto* target : info.callsTo) {
+        map[target].calledBy.insert(func);
+      }
+    }
+  }
+
+  // Propagate a property from a function to those that call it.
+  void propagateBack(std::function<bool(const T&)> hasProperty,
+                     std::function<bool(const T&)> canHaveProperty,
+                     std::function<void(T&)> addProperty) {
+    // The work queue contains items we just learned can change the state.
+    UniqueDeferredQueue<Function*> work;
+    for (auto& func : wasm.functions) {
+      if (hasProperty(map[func.get()])) {
+        work.push(func.get());
+      }
+    }
+    while (!work.empty()) {
+      auto* func = work.pop();
+      for (auto* caller : map[func].calledBy) {
+        // If we don't already have the property, and we are not forbidden
+        // from getting it, then it propagates back to us now.
+        if (!hasProperty(map[caller]) && canHaveProperty(map[caller])) {
+          addProperty(map[caller]);
+          work.push(caller);
+        }
+      }
+    }
   }
 };
 
diff --git a/src/passes/Asyncify.cpp b/src/passes/Asyncify.cpp
index c4e1c58bd..dd8845577 100644
--- a/src/passes/Asyncify.cpp
+++ b/src/passes/Asyncify.cpp
@@ -261,7 +261,6 @@
 #include "pass.h"
 #include "support/file.h"
 #include "support/string.h"
-#include "support/unique_deferring_queue.h"
 #include "wasm-builder.h"
 #include "wasm.h"
 
@@ -405,7 +404,8 @@ class ModuleAnalyzer {
   Module& module;
   bool canIndirectChangeState;
 
-  struct Info {
+  struct Info
+    : public ModuleUtils::CallGraphPropertyAnalysis<Info>::FunctionInfo {
     // If this function can start an unwind/rewind.
     bool canChangeState = false;
     // If this function is part of the runtime that receives an unwinding
@@ -419,8 +419,7 @@ class ModuleAnalyzer {
     // the top-most part is still marked as changing the state; so things
     // that call it are instrumented. This is not done for the bottom.
     bool isTopMostRuntime = false;
-    std::set<Function*> callsTo;
-    std::set<Function*> calledBy;
+    bool inBlacklist = false;
   };
 
   typedef std::map<Function*, Info> Map;
@@ -443,7 +442,7 @@ public:
     // Also handle the asyncify imports, removing them (as we will implement
     // them later), and replace calls to them with calls to the later proper
     // name.
-    ModuleUtils::ParallelFunctionMap<Info> scanner(
+    ModuleUtils::CallGraphPropertyAnalysis<Info> scanner(
       module, [&](Function* func, Info& info) {
         if (func->imported()) {
           // The relevant asyncify imports can definitely change the state.
@@ -482,9 +481,7 @@ public:
                 Fatal() << "call to unidenfied asyncify import: "
                         << target->base;
               }
-              return;
             }
-            info->callsTo.insert(target);
           }
           void visitCallIndirect(CallIndirect* curr) {
             if (curr->isReturn) {
@@ -515,52 +512,47 @@ public:
         }
       });
 
-    map.swap(scanner.map);
-
     // Functions in the blacklist are assumed to not change the state.
-    for (auto& name : blacklist.names) {
-      if (auto* func = module.getFunctionOrNull(name)) {
-        map[func].canChangeState = false;
+    for (auto& pair : scanner.map) {
+      auto* func = pair.first;
+      auto& info = pair.second;
+      if (blacklist.match(func->name)) {
+        info.inBlacklist = true;
+        info.canChangeState = false;
       }
     }
 
-    // Remove the asyncify imports, if any.
-    for (auto& pair : map) {
+    // Remove the asyncify imports, if any, and any calls to them.
+    std::vector<Name> funcsToDelete;
+    for (auto& pair : scanner.map) {
       auto* func = pair.first;
+      auto& callsTo = pair.second.callsTo;
       if (func->imported() && func->module == ASYNCIFY) {
-        module.removeFunction(func->name);
+        funcsToDelete.push_back(func->name);
       }
-    }
-
-    // Find what is called by what.
-    for (auto& pair : map) {
-      auto* func = pair.first;
-      auto& info = pair.second;
-      for (auto* target : info.callsTo) {
-        map[target].calledBy.insert(func);
+      std::vector<Function*> callersToDelete;
+      for (auto* target : callsTo) {
+        if (target->imported() && target->module == ASYNCIFY) {
+          callersToDelete.push_back(target);
+        }
       }
-    }
-
-    // Close over, finding all functions that can reach something that can
-    // change the state.
-    // The work queue contains an item we just learned can change the state.
-    UniqueDeferredQueue<Function*> work;
-    for (auto& func : module.functions) {
-      if (map[func.get()].canChangeState) {
-        work.push(func.get());
+      for (auto* target : callersToDelete) {
+        callsTo.erase(target);
       }
     }
-    while (!work.empty()) {
-      auto* func = work.pop();
-      for (auto* caller : map[func].calledBy) {
-        if (!map[caller].canChangeState && !map[caller].isBottomMostRuntime &&
-            !blacklist.match(caller->name)) {
-          map[caller].canChangeState = true;
-          work.push(caller);
-        }
-      }
+    for (auto name : funcsToDelete) {
+      module.removeFunction(name);
     }
 
+    scanner.propagateBack([](const Info& info) { return info.canChangeState; },
+                          [](const Info& info) {
+                            return !info.isBottomMostRuntime &&
+                                   !info.inBlacklist;
+                          },
+                          [](Info& info) { info.canChangeState = true; });
+
+    map.swap(scanner.map);
+
     if (!whitelistInput.empty()) {
       // Only the functions in the whitelist can change the state.
       for (auto& func : module.functions) {