[Bf-blender-cvs] [f6c377aa5bf] functions: remove unused nodes optimization

[Jacques Lucke]

Commit: f6c377aa5bf12f17b924e17178dbf91d9c8698eb
Author: Jacques Lucke
Date:   Sat Jan 11 16:35:35 2020 +0100
Branches: functions
https://developer.blender.org/rBf6c377aa5bf12f17b924e17178dbf91d9c8698eb

remove unused nodes optimization

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

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_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 fa1b6ca6813..386e1de75f4 100644
--- a/source/blender/functions/FN_multi_function_network.h
+++ b/source/blender/functions/FN_multi_function_network.h
@@ -59,6 +59,9 @@ class MFBuilderNode : BLI::NonCopyable, BLI::NonMovable {
   MFBuilderDummyNode &as_dummy();
 
   template<typename FuncT> void foreach_target_socket(const FuncT &func);
+  template<typename FuncT> void foreach_target_node(const FuncT &func);
+  template<typename FuncT> void foreach_origin_node(const FuncT &func);
+  template<typename FuncT> void foreach_linked_node(const FuncT &func);
 };
 
 class MFBuilderFunctionNode : public MFBuilderNode {
@@ -168,9 +171,19 @@ class MFNetworkBuilder : BLI::NonCopyable, BLI::NonMovable {
     return m_dummy_nodes.index(&node);
   }
 
+  uint node_id_amount() const
+  {
+    return m_node_or_null_by_id.size();
+  }
+
+  bool node_id_is_valid(uint id) const
+  {
+    return m_node_or_null_by_id[id] != nullptr;
+  }
+
   MFBuilderNode &node_by_id(uint id)
   {
-    BLI_assert(m_node_or_null_by_id[id] != nullptr);
+    BLI_assert(this->node_id_is_valid(id));
     return *m_node_or_null_by_id[id];
   }
 
@@ -445,6 +458,31 @@ template<typename FuncT> inline void MFBuilderNode::foreach_target_socket(const
   }
 }
 
+template<typename FuncT> inline void MFBuilderNode::foreach_target_node(const FuncT &func)
+{
+  for (MFBuilderOutputSocket *socket : m_outputs) {
+    for (MFBuilderInputSocket *target : socket->targets()) {
+      func(target->node());
+    }
+  }
+}
+
+template<typename FuncT> inline void MFBuilderNode::foreach_origin_node(const FuncT &func)
+{
+  for (MFBuilderInputSocket *socket : m_inputs) {
+    MFBuilderOutputSocket *origin = socket->origin();
+    if (origin != nullptr) {
+      func(origin->node());
+    }
+  }
+}
+
+template<typename FuncT> inline void MFBuilderNode::foreach_linked_node(const FuncT &func)
+{
+  this->foreach_origin_node(func);
+  this->foreach_target_node(func);
+}
+
 inline const MultiFunction &MFBuilderFunctionNode::function()
 {
   return *m_function;
diff --git a/source/blender/functions/FN_multi_function_network_optimization.h b/source/blender/functions/FN_multi_function_network_optimization.h
index f2117f28032..6d58201c795 100644
--- a/source/blender/functions/FN_multi_function_network_optimization.h
+++ b/source/blender/functions/FN_multi_function_network_optimization.h
@@ -10,6 +10,8 @@ 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);
 
 }  // namespace FN
 
diff --git a/source/blender/functions/intern/multi_function_network_optimization.cc b/source/blender/functions/intern/multi_function_network_optimization.cc
index 11528a78a3e..6a44d07fdfd 100644
--- a/source/blender/functions/intern/multi_function_network_optimization.cc
+++ b/source/blender/functions/intern/multi_function_network_optimization.cc
@@ -8,6 +8,39 @@ namespace FN {
 
 using BLI::Stack;
 
+void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder,
+                                           ArrayRef<MFBuilderNode *> fixed_nodes)
+{
+  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);
+    }
+  }
+}
+
 void optimize_network__constant_folding(MFNetworkBuilder &network_builder,
                                         ResourceCollector &resources)
 {
@@ -184,24 +217,10 @@ void optimize_network__constant_folding(MFNetworkBuilder &network_builder,
       left_most_constant_nodes.append(constant_node);
     }
   }
-  for (MFBuilderFunctionNode *node : inner_constant_nodes) {
-    network_builder.remove_node(*node);
-  }
-  for (MFBuilderFunctionNode *node : left_most_constant_nodes) {
-    uint target_amount = 0;
-    for (MFBuilderOutputSocket *output_socket : node->outputs()) {
-      target_amount += output_socket->targets().size();
-    }
-    if (target_amount == 0) {
-      network_builder.remove_node(*node);
-    }
-  }
 
   for (MFBuilderDummyNode *dummy_node : dummy_nodes_to_compute) {
     network_builder.remove_node(*dummy_node);
   }
-
-  network_builder.to_dot__clipboard();
 }
 
 }  // namespace FN
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 a2632bdde75..a3d4c4ea34d 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,6 +273,8 @@ 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());
+  // network_builder.to_dot__clipboard();
   auto function_tree_network = build(function_tree, network_builder, dummy_socket_mapping);
   return function_tree_network;
 }