1 files changed, 106 insertions, 0 deletions
diff --git a/src/dataflow/users.h b/src/dataflow/users.h
new file mode 100644
index 000000000..ab9a2ccef
--- /dev/null
+++ b/src/dataflow/users.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2018 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.
+ */
+
+//
+// DataFlow IR is an SSA representation. It can be built from the main
+// Binaryen IR.
+//
+// THe main initial use case was an IR that could easily be converted to
+// Souper IR, and the design favors that.
+//
+
+#ifndef wasm_dataflow_users_h
+#define wasm_dataflow_users_h
+
+#include "dataflow/graph.h"
+
+namespace wasm {
+
+namespace DataFlow {
+
+// Calculates the users of each node.
+//   users[x] = { y, z, .. }
+// where y, z etc. are nodes that use x, that is, x is in their
+// values vector.
+class Users {
+  typedef std::unordered_set<DataFlow::Node*> UserSet;
+
+  std::unordered_map<DataFlow::Node*, UserSet> users;
+
+public:
+  void build(Graph& graph) {
+    for (auto& node : graph.nodes) {
+      for (auto* value : node->values) {
+        users[value].insert(node.get());
+      }
+    }
+  }
+
+  UserSet& getUsers(Node* node) {
+    auto iter = users.find(node);
+    if (iter == users.end()) {
+      static UserSet empty; // FIXME thread_local?
+      return empty;
+    }
+    return iter->second;
+  }
+
+  Index getNumUses(Node* node) {
+    auto& users = getUsers(node);
+    // A user may have more than one use
+    Index numUses = 0;
+    for (auto* user : users) {
+#ifndef NDEBUG
+      bool found = false;
+#endif
+      for (auto* value : user->values) {
+        if (value == node) {
+          numUses++;
+#ifndef NDEBUG
+          found = true;
+#endif
+        }
+      }
+      assert(found);
+    }
+    return numUses;
+  }
+
+  // Stops using all the values of this node. Called when a node is being
+  // removed.
+  void stopUsingValues(Node* node) {
+    for (auto* value : node->values) {
+      auto& users = getUsers(value);
+      users.erase(node);
+    }
+  }
+
+  // Adds a new user to a node. Called when we add or change a value of a node.
+  void addUser(Node* node, Node* newUser) {
+    users[node].insert(newUser);
+  }
+
+  // Remove all uses of a node. Called when a node is being removed.
+  void removeAllUsesOf(Node* node) {
+    users.erase(node);
+  }
+};
+
+} // namespace DataFlow
+
+} // namespace wasm
+
+#endif // wasm_dataflow_users