[Bf-blender-cvs] [d8ca0ea86dc] functions: cleanup dead node elimination

[Jacques Lucke]

Commit: d8ca0ea86dc46ac983700481757cb1e52d4b9e3c
Author: Jacques Lucke
Date:   Sat Jan 11 17:15:52 2020 +0100
Branches: functions
https://developer.blender.org/rBd8ca0ea86dc46ac983700481757cb1e52d4b9e3c

cleanup dead node elimination

===================================================================

M	source/blender/functions/FN_multi_function_network.h
M	source/blender/functions/FN_multi_function_network_optimization.h
M	source/blender/functions/intern/multi_function_network.cc
M	source/blender/functions/intern/multi_function_network_optimization.cc
M	source/blender/functions/intern/node_tree_multi_function_network/generate.cc

===================================================================

diff --git a/source/blender/functions/FN_multi_function_network.h b/source/blender/functions/FN_multi_function_network.h
index 386e1de75f4..8285c72f259 100644
--- a/source/blender/functions/FN_multi_function_network.h
+++ b/source/blender/functions/FN_multi_function_network.h
@@ -160,6 +160,12 @@ class MFNetworkBuilder : BLI::NonCopyable, BLI::NonMovable {
   void add_link(MFBuilderOutputSocket &from, MFBuilderInputSocket &to);
   void remove_link(MFBuilderOutputSocket &from, MFBuilderInputSocket &to);
   void remove_node(MFBuilderNode &node);
+  void remove_nodes(ArrayRef<MFBuilderNode *> nodes);
+
+  Vector<MFBuilderNode *> find_nodes_whose_inputs_do_not_depend_on_these_nodes(
+      ArrayRef<MFBuilderNode *> nodes);
+  Vector<MFBuilderNode *> find_nodes_none_of_these_nodes_depends_on(
+      ArrayRef<MFBuilderNode *> nodes);
 
   uint current_index_of(MFBuilderFunctionNode &node) const
   {
diff --git a/source/blender/functions/FN_multi_function_network_optimization.h b/source/blender/functions/FN_multi_function_network_optimization.h
index 6d58201c795..0e6d5eb2fc4 100644
--- a/source/blender/functions/FN_multi_function_network_optimization.h
+++ b/source/blender/functions/FN_multi_function_network_optimization.h
@@ -10,8 +10,7 @@ namespace FN {
 using BLI::ResourceCollector;
 
 void optimize_network__constant_folding(MFNetworkBuilder &network, ResourceCollector &resources);
-void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder,
-                                           ArrayRef<MFBuilderNode *> fixed_nodes);
+void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder);
 
 }  // namespace FN
 
diff --git a/source/blender/functions/intern/multi_function_network.cc b/source/blender/functions/intern/multi_function_network.cc
index 39c17b48416..7087161763f 100644
--- a/source/blender/functions/intern/multi_function_network.cc
+++ b/source/blender/functions/intern/multi_function_network.cc
@@ -200,6 +200,88 @@ void MFNetworkBuilder::remove_node(MFBuilderNode &node)
   }
 }
 
+void MFNetworkBuilder::remove_nodes(ArrayRef<MFBuilderNode *> nodes)
+{
+  for (MFBuilderNode *node : nodes) {
+    this->remove_node(*node);
+  }
+}
+
+static bool set_tag_and_check_if_modified(bool &tag, bool new_value)
+{
+  if (tag != new_value) {
+    tag = new_value;
+    return true;
+  }
+  else {
+    return false;
+  }
+}
+
+Vector<MFBuilderNode *> MFNetworkBuilder::find_nodes_whose_inputs_do_not_depend_on_these_nodes(
+    ArrayRef<MFBuilderNode *> nodes)
+{
+  Array<bool> depends_on_nodes_tag(this->node_id_amount(), false);
+
+  for (MFBuilderNode *node : nodes) {
+    depends_on_nodes_tag[node->id()] = true;
+  }
+
+  Stack<MFBuilderNode *> nodes_to_check = nodes;
+  while (!nodes_to_check.is_empty()) {
+    MFBuilderNode &node = *nodes_to_check.pop();
+
+    if (depends_on_nodes_tag[node.id()]) {
+      node.foreach_target_node([&](MFBuilderNode &other_node) {
+        if (set_tag_and_check_if_modified(depends_on_nodes_tag[other_node.id()], true)) {
+          nodes_to_check.push(&other_node);
+        }
+      });
+    }
+  }
+
+  Vector<MFBuilderNode *> result;
+  for (uint id : m_node_or_null_by_id.index_range()) {
+    MFBuilderNode *node = m_node_or_null_by_id[id];
+    if (node != nullptr && !depends_on_nodes_tag[id]) {
+      result.append(node);
+    }
+  }
+  return result;
+}
+
+Vector<MFBuilderNode *> MFNetworkBuilder::find_nodes_none_of_these_nodes_depends_on(
+    ArrayRef<MFBuilderNode *> nodes)
+{
+  Array<bool> is_dependency_tag(this->node_id_amount(), false);
+
+  for (MFBuilderNode *node : nodes) {
+    is_dependency_tag[node->id()] = true;
+  }
+
+  Stack<MFBuilderNode *> nodes_to_check = nodes;
+  while (!nodes_to_check.is_empty()) {
+    MFBuilderNode &node = *nodes_to_check.pop();
+
+    if (is_dependency_tag[node.id()]) {
+      node.foreach_origin_node([&](MFBuilderNode &other_node) {
+        if (set_tag_and_check_if_modified(is_dependency_tag[other_node.id()], true)) {
+          nodes_to_check.push(&other_node);
+        }
+      });
+    }
+  }
+
+  Vector<MFBuilderNode *> result;
+  for (uint id : m_node_or_null_by_id.index_range()) {
+    MFBuilderNode *node = m_node_or_null_by_id[id];
+    if (node != nullptr && !is_dependency_tag[id]) {
+      result.append(node);
+    }
+  }
+  return result;
+}
+
 std::string MFNetworkBuilder::to_dot(const Set<MFBuilderNode *> &marked_nodes)
 {
   using BLI::DotExport::Utils::NodeWithSocketsWrapper;
diff --git a/source/blender/functions/intern/multi_function_network_optimization.cc b/source/blender/functions/intern/multi_function_network_optimization.cc
index 6a44d07fdfd..06e19951baf 100644
--- a/source/blender/functions/intern/multi_function_network_optimization.cc
+++ b/source/blender/functions/intern/multi_function_network_optimization.cc
@@ -8,37 +8,12 @@ namespace FN {
 
 using BLI::Stack;
 
-void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder,
-                                           ArrayRef<MFBuilderNode *> fixed_nodes)
+void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder)
 {
-  Array<bool> unused_tag_per_id(network_builder.node_id_amount(), false);
-
-  for (MFBuilderNode *fixed_node : fixed_nodes) {
-    unused_tag_per_id[fixed_node->id()] = true;
-  }
-
-  Stack<MFBuilderNode *> nodes_to_check = fixed_nodes;
-  while (!nodes_to_check.is_empty()) {
-    MFBuilderNode &current_node = *nodes_to_check.pop();
-    if (!unused_tag_per_id[current_node.id()]) {
-      continue;
-    }
-
-    current_node.foreach_origin_node([&](MFBuilderNode &other_node) {
-      bool &other_is_connected = unused_tag_per_id[other_node.id()];
-      if (!other_is_connected) {
-        other_is_connected = true;
-        nodes_to_check.push(&other_node);
-      }
-    });
-  }
-
-  for (uint id : unused_tag_per_id.index_range()) {
-    if (network_builder.node_id_is_valid(id) && !unused_tag_per_id[id]) {
-      MFBuilderNode &node = network_builder.node_by_id(id);
-      network_builder.remove_node(node);
-    }
-  }
+  ArrayRef<MFBuilderNode *> dummy_nodes = network_builder.dummy_nodes();
+  Vector<MFBuilderNode *> nodes = network_builder.find_nodes_none_of_these_nodes_depends_on(
+      dummy_nodes);
+  network_builder.remove_nodes(nodes);
 }
 
 void optimize_network__constant_folding(MFNetworkBuilder &network_builder,
diff --git a/source/blender/functions/intern/node_tree_multi_function_network/generate.cc b/source/blender/functions/intern/node_tree_multi_function_network/generate.cc
index a3d4c4ea34d..87271a381f2 100644
--- a/source/blender/functions/intern/node_tree_multi_function_network/generate.cc
+++ b/source/blender/functions/intern/node_tree_multi_function_network/generate.cc
@@ -273,7 +273,7 @@ std::unique_ptr<FunctionTreeMFNetwork> generate_node_tree_multi_function_network
   }
 
   optimize_network__constant_folding(network_builder, resources);
-  optimize_network__remove_unused_nodes(network_builder, network_builder.dummy_nodes());
+  optimize_network__remove_unused_nodes(network_builder);
   // network_builder.to_dot__clipboard();
   auto function_tree_network = build(function_tree, network_builder, dummy_socket_mapping);
   return function_tree_network;