Compositor: Merge equal operations

Some operations can take a lot of time to execute and
any duplication should be avoided.

This patch implements a compile step that detects
operations with the same type, inputs and parameters that
produce the same result and merge them. Now operations
can generate a hash that represents their output result. They only
need to implement `hash_output_params` and hash any parameter
that affects the output result.

Reviewed By: jbakker

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

5 files changed, 184 insertions, 11 deletions

diff --git a/source/blender/compositor/intern/COM_Debug.cc b/source/blender/compositor/intern/COM_Debug.cc
index a0333cf96cf..007085ee528 100644
--- a/source/blender/compositor/intern/COM_Debug.cc
+++ b/source/blender/compositor/intern/COM_Debug.cc
@@ -425,7 +425,8 @@ bool DebugInfo::graphviz_system(const ExecutionSystem *system, char *str, int ma
   }
 
   const bool has_execution_groups = system->getContext().get_execution_model() ==
-                                    eExecutionModel::Tiled;
+                                        eExecutionModel::Tiled &&
+                                    system->m_groups.size() > 0;
   len += graphviz_legend(str + len, maxlen > len ? maxlen - len : 0, has_execution_groups);
 
   len += snprintf(str + len, maxlen > len ? maxlen - len : 0, "}\r\n");
diff --git a/source/blender/compositor/intern/COM_NodeOperation.cc b/source/blender/compositor/intern/COM_NodeOperation.cc
index 1b87cdf72fb..a87485fd51c 100644
--- a/source/blender/compositor/intern/COM_NodeOperation.cc
+++ b/source/blender/compositor/intern/COM_NodeOperation.cc
@@ -41,6 +41,49 @@ NodeOperation::NodeOperation()
   this->m_btree = nullptr;
 }
 
+/**
+ * Generate a hash that identifies the operation result in the current execution.
+ * Requires `hash_output_params` to be implemented, otherwise `std::nullopt` is returned.
+ * If the operation parameters or its linked inputs change, the hash must be re-generated.
+ */
+std::optional<NodeOperationHash> NodeOperation::generate_hash()
+{
+  params_hash_ = get_default_hash_2(m_width, m_height);
+
+  /* Hash subclasses params. */
+  is_hash_output_params_implemented_ = true;
+  hash_output_params();
+  if (!is_hash_output_params_implemented_) {
+    return std::nullopt;
+  }
+
+  hash_param(getOutputSocket()->getDataType());
+  NodeOperationHash hash;
+  hash.params_hash_ = params_hash_;
+
+  hash.parents_hash_ = 0;
+  for (NodeOperationInput &socket : m_inputs) {
+    NodeOperation &input = socket.getLink()->getOperation();
+    const bool is_constant = input.get_flags().is_constant_operation;
+    combine_hashes(hash.parents_hash_, get_default_hash(is_constant));
+    if (is_constant) {
+      const float *elem = ((ConstantOperation *)&input)->get_constant_elem();
+      const int num_channels = COM_data_type_num_channels(socket.getDataType());
+      for (const int i : IndexRange(num_channels)) {
+        combine_hashes(hash.parents_hash_, get_default_hash(elem[i]));
+      }
+    }
+    else {
+      combine_hashes(hash.parents_hash_, get_default_hash(input.get_id()));
+    }
+  }
+
+  hash.type_hash_ = typeid(*this).hash_code();
+  hash.operation_ = this;
+
+  return hash;
+}
+
 NodeOperationOutput *NodeOperation::getOutputSocket(unsigned int index)
 {
   return &m_outputs[index];
diff --git a/source/blender/compositor/intern/COM_NodeOperation.h b/source/blender/compositor/intern/COM_NodeOperation.h
index b402dc7f174..ef7cf319222 100644
--- a/source/blender/compositor/intern/COM_NodeOperation.h
+++ b/source/blender/compositor/intern/COM_NodeOperation.h
@@ -22,6 +22,8 @@
 #include <sstream>
 #include <string>
 
+#include "BLI_ghash.h"
+#include "BLI_hash.hh"
 #include "BLI_math_color.h"
 #include "BLI_math_vector.h"
 #include "BLI_threads.h"
@@ -269,6 +271,42 @@ struct NodeOperationFlags {
   }
 };
 
+/** Hash that identifies an operation output result in the current execution. */
+struct NodeOperationHash {
+ private:
+  NodeOperation *operation_;
+  size_t type_hash_;
+  size_t parents_hash_;
+  size_t params_hash_;
+
+  friend class NodeOperation;
+
+ public:
+  NodeOperation *get_operation() const
+  {
+    return operation_;
+  }
+
+  bool operator==(const NodeOperationHash &other) const
+  {
+    return type_hash_ == other.type_hash_ && parents_hash_ == other.parents_hash_ &&
+           params_hash_ == other.params_hash_;
+  }
+
+  bool operator!=(const NodeOperationHash &other) const
+  {
+    return !(*this == other);
+  }
+
+  bool operator<(const NodeOperationHash &other) const
+  {
+    return type_hash_ < other.type_hash_ ||
+           (type_hash_ == other.type_hash_ && parents_hash_ < other.parents_hash_) ||
+           (type_hash_ == other.type_hash_ && parents_hash_ == other.parents_hash_ &&
+            params_hash_ < other.params_hash_);
+  }
+};
+
 /**
  * \brief NodeOperation contains calculation logic
  *
@@ -282,6 +320,9 @@ class NodeOperation {
   Vector<NodeOperationInput> m_inputs;
   Vector<NodeOperationOutput> m_outputs;
 
+  size_t params_hash_;
+  bool is_hash_output_params_implemented_;
+
   /**
    * \brief the index of the input socket that will be used to determine the resolution
    */
@@ -363,6 +404,8 @@ class NodeOperation {
     return flags;
   }
 
+  std::optional<NodeOperationHash> generate_hash();
+
   unsigned int getNumberOfInputSockets() const
   {
     return m_inputs.size();
@@ -624,6 +667,33 @@ class NodeOperation {
  protected:
   NodeOperation();
 
+  /* Overridden by subclasses to allow merging equal operations on compiling. Implementations must
+   * hash any subclass parameter that affects the output result using `hash_params` methods. */
+  virtual void hash_output_params()
+  {
+    is_hash_output_params_implemented_ = false;
+  }
+
+  static void combine_hashes(size_t &combined, size_t other)
+  {
+    combined = BLI_ghashutil_combine_hash(combined, other);
+  }
+
+  template<typename T> void hash_param(T param)
+  {
+    combine_hashes(params_hash_, get_default_hash(param));
+  }
+
+  template<typename T1, typename T2> void hash_params(T1 param1, T2 param2)
+  {
+    combine_hashes(params_hash_, get_default_hash_2(param1, param2));
+  }
+
+  template<typename T1, typename T2, typename T3> void hash_params(T1 param1, T2 param2, T3 param3)
+  {
+    combine_hashes(params_hash_, get_default_hash_3(param1, param2, param3));
+  }
+
   void addInputSocket(DataType datatype, ResizeMode resize_mode = ResizeMode::Center);
   void addOutputSocket(DataType datatype);
 
diff --git a/source/blender/compositor/intern/COM_NodeOperationBuilder.cc b/source/blender/compositor/intern/COM_NodeOperationBuilder.cc
index 10a91bbcd3e..5e18b5396b1 100644
--- a/source/blender/compositor/intern/COM_NodeOperationBuilder.cc
+++ b/source/blender/compositor/intern/COM_NodeOperationBuilder.cc
@@ -101,16 +101,16 @@ void NodeOperationBuilder::convertToOperations(ExecutionSystem *system)
   add_datatype_conversions();
 
   if (m_context->get_execution_model() == eExecutionModel::FullFrame) {
-    /* Copy operations to system. Needed for graphviz. */
-    system->set_operations(m_operations, {});
-
-    DebugInfo::graphviz(system, "compositor_prior_folding");
+    save_graphviz("compositor_prior_folding");
     ConstantFolder folder(*this);
     folder.fold_operations();
   }
 
   determineResolutions();
 
+  save_graphviz("compositor_prior_merging");
+  merge_equal_operations();
+
   if (m_context->get_execution_model() == eExecutionModel::Tiled) {
     /* surround complex ops with read/write buffer */
     add_complex_operation_buffers();
@@ -149,22 +149,28 @@ void NodeOperationBuilder::replace_operation_with_constant(NodeOperation *operat
                                                            ConstantOperation *constant_operation)
 {
   BLI_assert(constant_operation->getNumberOfInputSockets() == 0);
+  unlink_inputs_and_relink_outputs(operation, constant_operation);
+  addOperation(constant_operation);
+}
+
+void NodeOperationBuilder::unlink_inputs_and_relink_outputs(NodeOperation *unlinked_op,
+                                                            NodeOperation *linked_op)
+{
   int i = 0;
   while (i < m_links.size()) {
     Link &link = m_links[i];
-    if (&link.to()->getOperation() == operation) {
+    if (&link.to()->getOperation() == unlinked_op) {
       link.to()->setLink(nullptr);
       m_links.remove(i);
       continue;
     }
 
-    if (&link.from()->getOperation() == operation) {
-      link.to()->setLink(constant_operation->getOutputSocket());
-      m_links[i] = Link(constant_operation->getOutputSocket(), link.to());
+    if (&link.from()->getOperation() == unlinked_op) {
+      link.to()->setLink(linked_op->getOutputSocket());
+      m_links[i] = Link(linked_op->getOutputSocket(), link.to());
     }
     i++;
   }
-  addOperation(constant_operation);
 }
 
 void NodeOperationBuilder::mapInputSocket(NodeInput *node_socket,
@@ -456,6 +462,48 @@ void NodeOperationBuilder::determineResolutions()
   }
 }
 
+static Vector<NodeOperationHash> generate_hashes(Span<NodeOperation *> operations)
+{
+  Vector<NodeOperationHash> hashes;
+  for (NodeOperation *op : operations) {
+    std::optional<NodeOperationHash> hash = op->generate_hash();
+    if (hash) {
+      hashes.append(std::move(*hash));
+    }
+  }
+  return hashes;
+}
+
+/** Merge operations with same type, inputs and parameters that produce the same result. */
+void NodeOperationBuilder::merge_equal_operations()
+{
+  bool any_merged = true;
+  while (any_merged) {
+    /* Re-generate hashes with any change. */
+    Vector<NodeOperationHash> hashes = generate_hashes(m_operations);
+
+    /* Make hashes be consecutive when they are equal. */
+    std::sort(hashes.begin(), hashes.end());
+
+    any_merged = false;
+    const NodeOperationHash *prev_hash = nullptr;
+    for (const NodeOperationHash &hash : hashes) {
+      if (prev_hash && *prev_hash == hash) {
+        merge_equal_operations(prev_hash->get_operation(), hash.get_operation());
+        any_merged = true;
+      }
+      prev_hash = &hash;
+    }
+  }
+}
+
+void NodeOperationBuilder::merge_equal_operations(NodeOperation *from, NodeOperation *into)
+{
+  unlink_inputs_and_relink_outputs(from, into);
+  m_operations.remove_first_occurrence_and_reorder(from);
+  delete from;
+}
+
 Vector<NodeOperationInput *> NodeOperationBuilder::cache_output_links(
     NodeOperationOutput *output) const
 {
@@ -728,6 +776,14 @@ void NodeOperationBuilder::group_operations()
   }
 }
 
+void NodeOperationBuilder::save_graphviz(StringRefNull name)
+{
+  if (COM_EXPORT_GRAPHVIZ) {
+    exec_system_->set_operations(m_operations, m_groups);
+    DebugInfo::graphviz(exec_system_, name);
+  }
+}
+
 /** Create a graphviz representation of the NodeOperationBuilder. */
 std::ostream &operator<<(std::ostream &os, const NodeOperationBuilder &builder)
 {
diff --git a/source/blender/compositor/intern/COM_NodeOperationBuilder.h b/source/blender/compositor/intern/COM_NodeOperationBuilder.h
index 1f76765c846..aca4d043d41 100644
--- a/source/blender/compositor/intern/COM_NodeOperationBuilder.h
+++ b/source/blender/compositor/intern/COM_NodeOperationBuilder.h
@@ -169,7 +169,10 @@ class NodeOperationBuilder {
 
  private:
   PreviewOperation *make_preview_operation() const;
-
+  void unlink_inputs_and_relink_outputs(NodeOperation *unlinked_op, NodeOperation *linked_op);
+  void merge_equal_operations();
+  void merge_equal_operations(NodeOperation *from, NodeOperation *into);
+  void save_graphviz(StringRefNull name = "");
 #ifdef WITH_CXX_GUARDEDALLOC
   MEM_CXX_CLASS_ALLOC_FUNCS("COM:NodeCompilerImpl")
 #endif