Depsgraph: remove unused no-op nodes after building

This is the companion of D7031. That patch adds a new DIMENSIONS node to
the depsgraph for each object that has geometry. However, this node is
only necessary when there are drivers using an object's dimensions as
variable. Since this is rare, it's easiest to remove these nodes after
they turn out to be unnecessary. This is what (almost) happens in this
patch.

Removing nodes from the depsgraph is hard, and there are no functions to
do this yet. Instead, this patch recursively removes all the incoming
relations from unused no-op nodes (i.e. no-op operation nodes without
outgoing connections). Actually removing the nodes will be left as a
future improvement.

I've tested this on a Spring file [1]. Here are there results of blender
--debug-depsgraph-time spring_02_055_A.eevee.blend and letting it run
for a while to stabilise the reported FPS:

    master: 11.7 FPS
    Just D7031: 11.7 FPS
    Just D7033: 11.8 FPS
    Both D7031 + D7033: 12.3 FPS

[1] https://cloud.blender.org/p/spring/5d30a1076249366fa1939cf1

Differential Revision: https://developer.blender.org/D7033

4 files changed, 113 insertions, 0 deletions

diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt
index 737d66e07cb..169e7f00744 100644
--- a/source/blender/depsgraph/CMakeLists.txt
+++ b/source/blender/depsgraph/CMakeLists.txt
@@ -50,6 +50,7 @@ set(SRC
   intern/builder/deg_builder_relations_rig.cc
   intern/builder/deg_builder_relations_scene.cc
   intern/builder/deg_builder_relations_view_layer.cc
+  intern/builder/deg_builder_remove_noop.cc
   intern/builder/deg_builder_rna.cc
   intern/builder/deg_builder_transitive.cc
   intern/debug/deg_debug.cc
@@ -103,6 +104,7 @@ set(SRC
   intern/builder/deg_builder_pchanmap.h
   intern/builder/deg_builder_relations.h
   intern/builder/deg_builder_relations_impl.h
+  intern/builder/deg_builder_remove_noop.h
   intern/builder/deg_builder_rna.h
   intern/builder/deg_builder_transitive.h
   intern/debug/deg_debug.h
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc b/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc
new file mode 100644
index 00000000000..33de20133db
--- /dev/null
+++ b/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc
@@ -0,0 +1,76 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2020 Blender Foundation.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup depsgraph
+ */
+
+#include "intern/builder/deg_builder_remove_noop.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "intern/node/deg_node.h"
+#include "intern/node/deg_node_operation.h"
+
+#include "intern/depsgraph.h"
+#include "intern/depsgraph_type.h"
+#include "intern/depsgraph_relation.h"
+#include "intern/debug/deg_debug.h"
+
+namespace DEG {
+
+void deg_graph_remove_unused_noops(Depsgraph *graph)
+{
+  int num_removed_relations = 0;
+  deque<OperationNode *> queue;
+
+  for (OperationNode *node : graph->operations) {
+    if (node->is_noop() && node->outlinks.empty()) {
+      queue.push_back(node);
+    }
+  }
+
+  while (!queue.empty()) {
+    OperationNode *to_remove = queue.front();
+    queue.pop_front();
+
+    while (!to_remove->inlinks.empty()) {
+      Relation *rel_in = to_remove->inlinks[0];
+      Node *dependency = rel_in->from;
+
+      /* Remove the relation. */
+      rel_in->unlink();
+      OBJECT_GUARDED_DELETE(rel_in, Relation);
+      num_removed_relations++;
+
+      /* Queue parent no-op node that has now become unused. */
+      OperationNode *operation = dependency->get_exit_operation();
+      if (operation != nullptr && operation->is_noop() && operation->outlinks.empty()) {
+        queue.push_back(operation);
+      }
+    }
+
+    /* TODO(Sybren): Remove the node itself. */
+  }
+
+  DEG_DEBUG_PRINTF(
+      (::Depsgraph *)graph, BUILD, "Removed %d relations to no-op nodes\n", num_removed_relations);
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.h b/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.h
new file mode 100644
index 00000000000..e7a2e90cf7c
--- /dev/null
+++ b/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.h
@@ -0,0 +1,33 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2020 Blender Foundation.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup depsgraph
+ */
+
+#pragma once
+
+namespace DEG {
+
+struct Depsgraph;
+
+/* Remove all no-op nodes that have zero outgoing relations. */
+void deg_graph_remove_unused_noops(Depsgraph *graph);
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index 3fe585ff73c..75031a2140e 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cc
+++ b/source/blender/depsgraph/intern/depsgraph_build.cc
@@ -50,6 +50,7 @@ extern "C" {
 #include "builder/deg_builder_cycle.h"
 #include "builder/deg_builder_nodes.h"
 #include "builder/deg_builder_relations.h"
+#include "builder/deg_builder_remove_noop.h"
 #include "builder/deg_builder_transitive.h"
 
 #include "intern/debug/deg_debug.h"
@@ -210,6 +211,7 @@ static void graph_build_finalize_common(DEG::Depsgraph *deg_graph, Main *bmain)
   if (G.debug_value == 799) {
     DEG::deg_graph_transitive_reduction(deg_graph);
   }
+  DEG::deg_graph_remove_unused_noops(deg_graph);
   /* Store pointers to commonly used valuated datablocks. */
   deg_graph->scene_cow = (Scene *)deg_graph->get_cow_id(&deg_graph->scene->id);
   /* Flush visibility layer and re-schedule nodes for update. */