Compositor: Refactor recursive methods to iterative

In order to reduce stack size this patch converts full frame 
recursive methods into iterative.
- No functional changes.
- No performance changes.
- Memory peak may slightly vary depending on the tree because
 now breadth-first traversal is used instead of depth-first.

Tests in D11113 have same results except for test1 memory peak:
360MBs instead of 329.50MBs.

Reviewed By: Jeroen Bakker (jbakker)

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

4 files changed, 86 insertions, 50 deletions

diff --git a/source/blender/compositor/intern/COM_FullFrameExecutionModel.cc b/source/blender/compositor/intern/COM_FullFrameExecutionModel.cc
index 396aa2fcf6f..21075bb7255 100644
--- a/source/blender/compositor/intern/COM_FullFrameExecutionModel.cc
+++ b/source/blender/compositor/intern/COM_FullFrameExecutionModel.cc
@@ -84,18 +84,6 @@ void FullFrameExecutionModel::determine_areas_to_render_and_reads()
   }
 }
 
-void FullFrameExecutionModel::ensure_inputs_rendered(NodeOperation *op,
-                                                     ExecutionSystem &exec_system)
-{
-  const int num_inputs = op->getNumberOfInputSockets();
-  for (int i = 0; i < num_inputs; i++) {
-    NodeOperation *input_op = op->get_input_operation(i);
-    if (!active_buffers_.is_operation_rendered(input_op)) {
-      render_operation(input_op, exec_system);
-    }
-  }
-}
-
 Vector<MemoryBuffer *> FullFrameExecutionModel::get_input_buffers(NodeOperation *op)
 {
   const int num_inputs = op->getNumberOfInputSockets();
@@ -121,11 +109,6 @@ MemoryBuffer *FullFrameExecutionModel::create_operation_buffer(NodeOperation *op
 
 void FullFrameExecutionModel::render_operation(NodeOperation *op, ExecutionSystem &exec_system)
 {
-  if (active_buffers_.is_operation_rendered(op)) {
-    return;
-  }
-
-  ensure_inputs_rendered(op, exec_system);
   Vector<MemoryBuffer *> input_bufs = get_input_buffers(op);
 
   const bool has_outputs = op->getNumberOfOutputSockets() > 0;
@@ -148,6 +131,7 @@ void FullFrameExecutionModel::render_operations(ExecutionSystem &exec_system)
   for (eCompositorPriority priority : priorities_) {
     for (NodeOperation *op : operations_) {
       if (op->isOutputOperation(is_rendering) && op->getRenderPriority() == priority) {
+        render_output_dependencies(op, exec_system);
         render_operation(op, exec_system);
       }
     }
@@ -156,48 +140,99 @@ void FullFrameExecutionModel::render_operations(ExecutionSystem &exec_system)
 }
 
 /**
- * Determines all input operations areas needed to render given operation area.
- * \param operation: Renderer operation.
- * \param render_area: Area within given operation bounds to render.
+ * Returns all dependencies from inputs to outputs. A dependency may be repeated when
+ * several operations depend on it.
  */
-void FullFrameExecutionModel::determine_areas_to_render(NodeOperation *operation,
-                                                        const rcti &render_area)
+static Vector<NodeOperation *> get_operation_dependencies(NodeOperation *operation)
 {
-  if (active_buffers_.is_area_registered(operation, render_area)) {
-    return;
+  /* Get dependencies from outputs to inputs. */
+  Vector<NodeOperation *> dependencies;
+  Vector<NodeOperation *> next_outputs;
+  next_outputs.append(operation);
+  while (next_outputs.size() > 0) {
+    Vector<NodeOperation *> outputs(next_outputs);
+    next_outputs.clear();
+    for (NodeOperation *output : outputs) {
+      for (int i = 0; i < output->getNumberOfInputSockets(); i++) {
+        next_outputs.append(output->get_input_operation(i));
+      }
+    }
+    dependencies.extend(next_outputs);
   }
 
-  active_buffers_.register_area(operation, render_area);
+  /* Reverse to get dependencies from inputs to outputs. */
+  std::reverse(dependencies.begin(), dependencies.end());
 
-  const int num_inputs = operation->getNumberOfInputSockets();
-  for (int i = 0; i < num_inputs; i++) {
-    NodeOperation *input_op = operation->get_input_operation(i);
-    rcti input_op_rect, input_area;
-    BLI_rcti_init(&input_op_rect, 0, input_op->getWidth(), 0, input_op->getHeight());
-    operation->get_area_of_interest(input_op, render_area, input_area);
+  return dependencies;
+}
+
+void FullFrameExecutionModel::render_output_dependencies(NodeOperation *output_op,
+                                                         ExecutionSystem &exec_system)
+{
+  BLI_assert(output_op->isOutputOperation(context_.isRendering()));
+  Vector<NodeOperation *> dependencies = get_operation_dependencies(output_op);
+  for (NodeOperation *op : dependencies) {
+    if (!active_buffers_.is_operation_rendered(op)) {
+      render_operation(op, exec_system);
+    }
+  }
+}
+
+/**
+ * Determines all operations areas needed to render given output area.
+ */
+void FullFrameExecutionModel::determine_areas_to_render(NodeOperation *output_op,
+                                                        const rcti &output_area)
+{
+  BLI_assert(output_op->isOutputOperation(context_.isRendering()));
+
+  Vector<std::pair<NodeOperation *, const rcti>> stack;
+  stack.append({output_op, output_area});
+  while (stack.size() > 0) {
+    std::pair<NodeOperation *, rcti> pair = stack.pop_last();
+    NodeOperation *operation = pair.first;
+    const rcti &render_area = pair.second;
+    if (active_buffers_.is_area_registered(operation, render_area)) {
+      continue;
+    }
 
-    /* Ensure area of interest is within operation bounds, cropping areas outside. */
-    BLI_rcti_isect(&input_area, &input_op_rect, &input_area);
+    active_buffers_.register_area(operation, render_area);
 
-    determine_areas_to_render(input_op, input_area);
+    const int num_inputs = operation->getNumberOfInputSockets();
+    for (int i = 0; i < num_inputs; i++) {
+      NodeOperation *input_op = operation->get_input_operation(i);
+      rcti input_op_rect, input_area;
+      BLI_rcti_init(&input_op_rect, 0, input_op->getWidth(), 0, input_op->getHeight());
+      operation->get_area_of_interest(input_op, render_area, input_area);
+
+      /* Ensure area of interest is within operation bounds, cropping areas outside. */
+      BLI_rcti_isect(&input_area, &input_op_rect, &input_area);
+
+      stack.append({input_op, input_area});
+    }
   }
 }
 
 /**
- * Determines the reads given operation and its inputs will receive (i.e: Number of dependent
+ * Determines reads to receive by operations in output operation tree (i.e: Number of dependent
  * operations each operation has).
  */
-void FullFrameExecutionModel::determine_reads(NodeOperation *operation)
+void FullFrameExecutionModel::determine_reads(NodeOperation *output_op)
 {
-  if (active_buffers_.has_registered_reads(operation)) {
-    return;
-  }
+  BLI_assert(output_op->isOutputOperation(context_.isRendering()));
 
-  const int num_inputs = operation->getNumberOfInputSockets();
-  for (int i = 0; i < num_inputs; i++) {
-    NodeOperation *input_op = operation->get_input_operation(i);
-    determine_reads(input_op);
-    active_buffers_.register_read(input_op);
+  Vector<NodeOperation *> stack;
+  stack.append(output_op);
+  while (stack.size() > 0) {
+    NodeOperation *operation = stack.pop_last();
+    const int num_inputs = operation->getNumberOfInputSockets();
+    for (int i = 0; i < num_inputs; i++) {
+      NodeOperation *input_op = operation->get_input_operation(i);
+      if (!active_buffers_.has_registered_reads(input_op)) {
+        stack.append(input_op);
+      }
+      active_buffers_.register_read(input_op);
+    }
   }
 }
 
diff --git a/source/blender/compositor/intern/COM_FullFrameExecutionModel.h b/source/blender/compositor/intern/COM_FullFrameExecutionModel.h
index 2c0d5e0460a..e68ad93b407 100644
--- a/source/blender/compositor/intern/COM_FullFrameExecutionModel.h
+++ b/source/blender/compositor/intern/COM_FullFrameExecutionModel.h
@@ -67,8 +67,7 @@ class FullFrameExecutionModel : public ExecutionModel {
  private:
   void determine_areas_to_render_and_reads();
   void render_operations(ExecutionSystem &exec_system);
-
-  void ensure_inputs_rendered(NodeOperation *op, ExecutionSystem &exec_system);
+  void render_output_dependencies(NodeOperation *output_op, ExecutionSystem &exec_system);
   Vector<MemoryBuffer *> get_input_buffers(NodeOperation *op);
   MemoryBuffer *create_operation_buffer(NodeOperation *op);
   void render_operation(NodeOperation *op, ExecutionSystem &exec_system);
@@ -76,8 +75,8 @@ class FullFrameExecutionModel : public ExecutionModel {
   void operation_finished(NodeOperation *operation);
 
   void get_output_render_area(NodeOperation *output_op, rcti &r_area);
-  void determine_areas_to_render(NodeOperation *operation, const rcti &render_area);
-  void determine_reads(NodeOperation *operation);
+  void determine_areas_to_render(NodeOperation *output_op, const rcti &output_area);
+  void determine_reads(NodeOperation *output_op);
 
   void update_progress_bar();
 
diff --git a/source/blender/compositor/intern/COM_SharedOperationBuffers.cc b/source/blender/compositor/intern/COM_SharedOperationBuffers.cc
index 4ce674a1c25..7e0486b0f54 100644
--- a/source/blender/compositor/intern/COM_SharedOperationBuffers.cc
+++ b/source/blender/compositor/intern/COM_SharedOperationBuffers.cc
@@ -23,7 +23,7 @@
 namespace blender::compositor {
 
 SharedOperationBuffers::BufferData::BufferData()
-    : buffer(nullptr), registered_reads(0), received_reads(0)
+    : buffer(nullptr), registered_reads(0), received_reads(0), is_rendered(false)
 {
 }
 
@@ -86,7 +86,7 @@ blender::Span<rcti> SharedOperationBuffers::get_areas_to_render(NodeOperation *o
  */
 bool SharedOperationBuffers::is_operation_rendered(NodeOperation *op)
 {
-  return get_buffer_data(op).buffer != nullptr;
+  return get_buffer_data(op).is_rendered;
 }
 
 /**
@@ -99,6 +99,7 @@ void SharedOperationBuffers::set_rendered_buffer(NodeOperation *op,
   BLI_assert(buf_data.received_reads == 0);
   BLI_assert(buf_data.buffer == nullptr);
   buf_data.buffer = std::move(buffer);
+  buf_data.is_rendered = true;
 }
 
 /**
diff --git a/source/blender/compositor/intern/COM_SharedOperationBuffers.h b/source/blender/compositor/intern/COM_SharedOperationBuffers.h
index 480a799d89f..f7763cd8ae4 100644
--- a/source/blender/compositor/intern/COM_SharedOperationBuffers.h
+++ b/source/blender/compositor/intern/COM_SharedOperationBuffers.h
@@ -42,6 +42,7 @@ class SharedOperationBuffers {
     blender::Vector<rcti> render_areas;
     int registered_reads;
     int received_reads;
+    bool is_rendered;
   } BufferData;
   blender::Map<NodeOperation *, BufferData> buffers_;