progresstemp-parallel-multi-function

6 files changed, 212 insertions, 167 deletions

diff --git a/source/blender/functions/FN_multi_function_procedure.hh b/source/blender/functions/FN_multi_function_procedure.hh
index 407d87fde63..c6733dd2dc8 100644
--- a/source/blender/functions/FN_multi_function_procedure.hh
+++ b/source/blender/functions/FN_multi_function_procedure.hh
@@ -43,6 +43,55 @@ enum class MFInstructionType {
 };
 
 /**
+ * An #MFInstructionCursor points to a position in a multi-function procedure, where an instruction
+ * can be inserted.
+ */
+class MFInstructionCursor {
+ public:
+  enum Type {
+    None,
+    Entry,
+    Call,
+    Destruct,
+    Branch,
+    Dummy,
+  };
+
+ private:
+  Type type_ = None;
+  MFInstruction *instruction_ = nullptr;
+  /* Only used when it is a branch instruction. */
+  bool branch_output_ = false;
+
+ public:
+  MFInstructionCursor() = default;
+  MFInstructionCursor(MFCallInstruction &instruction);
+  MFInstructionCursor(MFDestructInstruction &instruction);
+  MFInstructionCursor(MFBranchInstruction &instruction, bool branch_output);
+  MFInstructionCursor(MFDummyInstruction &instruction);
+
+  static MFInstructionCursor ForEntry();
+
+  MFInstruction *next(MFProcedure &procedure) const;
+  void set_next(MFProcedure &procedure, MFInstruction *new_instruction) const;
+
+  MFInstruction *instruction() const;
+
+  Type type() const;
+
+  friend bool operator==(const MFInstructionCursor &a, const MFInstructionCursor &b)
+  {
+    return a.type_ == b.type_ && a.instruction_ == b.instruction_ &&
+           a.branch_output_ == b.branch_output_;
+  }
+
+  friend bool operator!=(const MFInstructionCursor &a, const MFInstructionCursor &b)
+  {
+    return !(a == b);
+  }
+};
+
+/**
  * A variable is similar to a virtual register in other libraries. During evaluation, every is
  * either uninitialized or contains a value for every index (remember, a multi-function procedure
  * is always evaluated for many indices at the same time).
@@ -73,7 +122,7 @@ class MFVariable : NonCopyable, NonMovable {
 class MFInstruction : NonCopyable, NonMovable {
  protected:
   MFInstructionType type_;
-  Vector<MFInstruction *> prev_;
+  Vector<MFInstructionCursor> prev_;
 
   friend MFProcedure;
   friend MFCallInstruction;
@@ -89,8 +138,7 @@ class MFInstruction : NonCopyable, NonMovable {
    * Other instructions that come before this instruction. There can be multiple previous
    * instructions when branching is used in the procedure.
    */
-  Span<MFInstruction *> prev();
-  Span<const MFInstruction *> prev() const;
+  Span<MFInstructionCursor> prev() const;
 };
 
 /**
@@ -279,6 +327,50 @@ using MFProcedure = fn::MFProcedure;
 }  // namespace multi_function_procedure_types
 
 /* --------------------------------------------------------------------
+ * MFInstructionCursor inline methods.
+ */
+
+inline MFInstructionCursor::MFInstructionCursor(MFCallInstruction &instruction)
+    : type_(Call), instruction_(&instruction)
+{
+}
+
+inline MFInstructionCursor::MFInstructionCursor(MFDestructInstruction &instruction)
+    : type_(Destruct), instruction_(&instruction)
+{
+}
+
+inline MFInstructionCursor::MFInstructionCursor(MFBranchInstruction &instruction,
+                                                bool branch_output)
+    : type_(Branch), instruction_(&instruction), branch_output_(branch_output)
+{
+}
+
+inline MFInstructionCursor::MFInstructionCursor(MFDummyInstruction &instruction)
+    : type_(Dummy), instruction_(&instruction)
+{
+}
+
+inline MFInstructionCursor MFInstructionCursor::ForEntry()
+{
+  MFInstructionCursor cursor;
+  cursor.type_ = Type::Entry;
+  return cursor;
+}
+
+inline MFInstruction *MFInstructionCursor::instruction() const
+{
+  /* This isn't really const correct unfortunately, because to make it correct we'll need a const
+   * version of #MFInstructionCursor. */
+  return instruction_;
+}
+
+inline MFInstructionCursor::Type MFInstructionCursor::type() const
+{
+  return type_;
+}
+
+/* --------------------------------------------------------------------
  * MFVariable inline methods.
  */
 
@@ -311,12 +403,7 @@ inline MFInstructionType MFInstruction::type() const
   return type_;
 }
 
-inline Span<MFInstruction *> MFInstruction::prev()
-{
-  return prev_;
-}
-
-inline Span<const MFInstruction *> MFInstruction::prev() const
+inline Span<MFInstructionCursor> MFInstruction::prev() const
 {
   return prev_;
 }
diff --git a/source/blender/functions/FN_multi_function_procedure_builder.hh b/source/blender/functions/FN_multi_function_procedure_builder.hh
index d5e45470a0e..e416f7e500d 100644
--- a/source/blender/functions/FN_multi_function_procedure_builder.hh
+++ b/source/blender/functions/FN_multi_function_procedure_builder.hh
@@ -25,31 +25,6 @@
 namespace blender::fn {
 
 /**
- * An #MFInstructionCursor points to a position in a multi-function procedure, where an instruction
- * can be inserted.
- */
-class MFInstructionCursor {
- private:
-  MFInstruction *instruction_ = nullptr;
-  /* Only used when it is a branch instruction. */
-  bool branch_output_ = false;
-  /* Only used when instruction is null. */
-  bool is_entry_ = false;
-
- public:
-  MFInstructionCursor() = default;
-
-  MFInstructionCursor(MFCallInstruction &instruction);
-  MFInstructionCursor(MFDestructInstruction &instruction);
-  MFInstructionCursor(MFBranchInstruction &instruction, bool branch_output);
-  MFInstructionCursor(MFDummyInstruction &instruction);
-
-  static MFInstructionCursor Entry();
-
-  void insert(MFProcedure &procedure, MFInstruction *new_instruction);
-};
-
-/**
  * Utility class to build a #MFProcedure.
  */
 class MFProcedureBuilder {
@@ -64,7 +39,7 @@ class MFProcedureBuilder {
   struct Loop;
 
   MFProcedureBuilder(MFProcedure &procedure,
-                     MFInstructionCursor initial_cursor = MFInstructionCursor::Entry());
+                     MFInstructionCursor initial_cursor = MFInstructionCursor::ForEntry());
 
   MFProcedureBuilder(Span<MFProcedureBuilder *> builders);
 
@@ -122,38 +97,6 @@ struct MFProcedureBuilder::Loop {
 };
 
 /* --------------------------------------------------------------------
- * MFInstructionCursor inline methods.
- */
-
-inline MFInstructionCursor::MFInstructionCursor(MFCallInstruction &instruction)
-    : instruction_(&instruction)
-{
-}
-
-inline MFInstructionCursor::MFInstructionCursor(MFDestructInstruction &instruction)
-    : instruction_(&instruction)
-{
-}
-
-inline MFInstructionCursor::MFInstructionCursor(MFBranchInstruction &instruction,
-                                                bool branch_output)
-    : instruction_(&instruction), branch_output_(branch_output)
-{
-}
-
-inline MFInstructionCursor::MFInstructionCursor(MFDummyInstruction &instruction)
-    : instruction_(&instruction)
-{
-}
-
-inline MFInstructionCursor MFInstructionCursor::Entry()
-{
-  MFInstructionCursor cursor;
-  cursor.is_entry_ = true;
-  return cursor;
-}
-
-/* --------------------------------------------------------------------
  * MFProcedureBuilder inline methods.
  */
 
@@ -253,7 +196,7 @@ inline void MFProcedureBuilder::add_output_parameter(MFVariable &variable)
 inline void MFProcedureBuilder::link_to_cursors(MFInstruction *instruction)
 {
   for (MFInstructionCursor &cursor : cursors_) {
-    cursor.insert(*procedure_, instruction);
+    cursor.set_next(*procedure_, instruction);
   }
 }
 
diff --git a/source/blender/functions/intern/field.cc b/source/blender/functions/intern/field.cc
index 5f695e14988..e35d858d40b 100644
--- a/source/blender/functions/intern/field.cc
+++ b/source/blender/functions/intern/field.cc
@@ -276,7 +276,6 @@ Vector<const GVArray *> evaluate_fields(ResourceScope &scope,
                                         const FieldContext &context,
                                         Span<GVMutableArray *> dst_varrays)
 {
-  SCOPED_TIMER(__func__);
 
   Vector<const GVArray *> r_varrays(fields_to_evaluate.size(), nullptr);
   const int array_size = mask.min_array_size();
@@ -340,9 +339,9 @@ Vector<const GVArray *> evaluate_fields(ResourceScope &scope,
     MFProcedure procedure;
     build_multi_function_procedure_for_fields(
         procedure, scope, field_tree_info, varying_fields_to_evaluate);
-    std::cout << procedure.to_dot() << "\n";
-    fn::procedure_optimization::move_destructs_up(procedure);
-    std::cout << procedure.to_dot() << "\n";
+    // std::cout << procedure.to_dot() << "\n";
+    // fn::procedure_optimization::move_destructs_up(procedure);
+    // std::cout << procedure.to_dot() << "\n";
     MFProcedureExecutor procedure_executor{"Procedure", procedure};
     fn::ParallelMultiFunction parallel_fn{procedure_executor, 10000};
     const MultiFunction &fn_to_execute = parallel_fn;
@@ -389,6 +388,7 @@ Vector<const GVArray *> evaluate_fields(ResourceScope &scope,
       mf_params.add_uninitialized_single_output(span);
     }
 
+    SCOPED_TIMER(__func__);
     fn_to_execute.call(mask, mf_params, mf_context);
   }
 
diff --git a/source/blender/functions/intern/multi_function_procedure.cc b/source/blender/functions/intern/multi_function_procedure.cc
index 6eff7bc09f8..7fc5d403e84 100644
--- a/source/blender/functions/intern/multi_function_procedure.cc
+++ b/source/blender/functions/intern/multi_function_procedure.cc
@@ -21,6 +21,65 @@
 
 namespace blender::fn {
 
+void MFInstructionCursor::set_next(MFProcedure &procedure, MFInstruction *new_instruction) const
+{
+  switch (type_) {
+    case Type::None: {
+      break;
+    }
+    case Type::Entry: {
+      procedure.set_entry(*new_instruction);
+      break;
+    }
+    case Type::Call: {
+      static_cast<MFCallInstruction *>(instruction_)->set_next(new_instruction);
+      break;
+    }
+    case Type::Branch: {
+      MFBranchInstruction &branch_instruction = *static_cast<MFBranchInstruction *>(instruction_);
+      if (branch_output_) {
+        branch_instruction.set_branch_true(new_instruction);
+      }
+      else {
+        branch_instruction.set_branch_false(new_instruction);
+      }
+      break;
+    }
+    case Type::Destruct: {
+      static_cast<MFDestructInstruction *>(instruction_)->set_next(new_instruction);
+      break;
+    }
+    case Type::Dummy: {
+      static_cast<MFDummyInstruction *>(instruction_)->set_next(new_instruction);
+      break;
+    }
+  }
+}
+
+MFInstruction *MFInstructionCursor::next(MFProcedure &procedure) const
+{
+  switch (type_) {
+    case Type::None:
+      return nullptr;
+    case Type::Entry:
+      return procedure.entry();
+    case Type::Call:
+      return static_cast<MFCallInstruction *>(instruction_)->next();
+    case Type::Branch: {
+      MFBranchInstruction &branch_instruction = *static_cast<MFBranchInstruction *>(instruction_);
+      if (branch_output_) {
+        return branch_instruction.branch_true();
+      }
+      return branch_instruction.branch_false();
+    }
+    case Type::Destruct:
+      return static_cast<MFDestructInstruction *>(instruction_)->next();
+    case Type::Dummy:
+      return static_cast<MFDummyInstruction *>(instruction_)->next();
+  }
+  return nullptr;
+}
+
 void MFVariable::set_name(std::string name)
 {
   name_ = std::move(name);
@@ -29,10 +88,10 @@ void MFVariable::set_name(std::string name)
 void MFCallInstruction::set_next(MFInstruction *instruction)
 {
   if (next_ != nullptr) {
-    next_->prev_.remove_first_occurrence_and_reorder(this);
+    next_->prev_.remove_first_occurrence_and_reorder(*this);
   }
   if (instruction != nullptr) {
-    instruction->prev_.append(this);
+    instruction->prev_.append(*this);
   }
   next_ = instruction;
 }
@@ -71,10 +130,10 @@ void MFBranchInstruction::set_condition(MFVariable *variable)
 void MFBranchInstruction::set_branch_true(MFInstruction *instruction)
 {
   if (branch_true_ != nullptr) {
-    branch_true_->prev_.remove_first_occurrence_and_reorder(this);
+    branch_true_->prev_.remove_first_occurrence_and_reorder({*this, true});
   }
   if (instruction != nullptr) {
-    instruction->prev_.append(this);
+    instruction->prev_.append({*this, true});
   }
   branch_true_ = instruction;
 }
@@ -82,10 +141,10 @@ void MFBranchInstruction::set_branch_true(MFInstruction *instruction)
 void MFBranchInstruction::set_branch_false(MFInstruction *instruction)
 {
   if (branch_false_ != nullptr) {
-    branch_false_->prev_.remove_first_occurrence_and_reorder(this);
+    branch_false_->prev_.remove_first_occurrence_and_reorder({*this, false});
   }
   if (instruction != nullptr) {
-    instruction->prev_.append(this);
+    instruction->prev_.append({*this, false});
   }
   branch_false_ = instruction;
 }
@@ -104,10 +163,10 @@ void MFDestructInstruction::set_variable(MFVariable *variable)
 void MFDestructInstruction::set_next(MFInstruction *instruction)
 {
   if (next_ != nullptr) {
-    next_->prev_.remove_first_occurrence_and_reorder(this);
+    next_->prev_.remove_first_occurrence_and_reorder(*this);
   }
   if (instruction != nullptr) {
-    instruction->prev_.append(this);
+    instruction->prev_.append(*this);
   }
   next_ = instruction;
 }
@@ -115,10 +174,10 @@ void MFDestructInstruction::set_next(MFInstruction *instruction)
 void MFDummyInstruction::set_next(MFInstruction *instruction)
 {
   if (next_ != nullptr) {
-    next_->prev_.remove_first_occurrence_and_reorder(this);
+    next_->prev_.remove_first_occurrence_and_reorder(*this);
   }
   if (instruction != nullptr) {
-    instruction->prev_.append(this);
+    instruction->prev_.append(*this);
   }
   next_ = instruction;
 }
@@ -420,7 +479,11 @@ MFProcedure::InitState MFProcedure::find_initialization_state_before_instruction
 
   Set<const MFInstruction *> checked_instructions;
   Stack<const MFInstruction *> instructions_to_check;
-  instructions_to_check.push_multiple(target_instruction.prev_);
+  for (const MFInstructionCursor &cursor : target_instruction.prev_) {
+    if (cursor.instruction() != nullptr) {
+      instructions_to_check.push(cursor.instruction());
+    }
+  }
 
   while (!instructions_to_check.is_empty()) {
     const MFInstruction &instruction = *instructions_to_check.pop();
@@ -467,7 +530,11 @@ MFProcedure::InitState MFProcedure::find_initialization_state_before_instruction
       if (&instruction == entry_) {
         check_entry_instruction();
       }
-      instructions_to_check.push_multiple(instruction.prev_);
+      for (const MFInstructionCursor &cursor : instruction.prev_) {
+        if (cursor.instruction() != nullptr) {
+          instructions_to_check.push(cursor.instruction());
+        }
+      }
     }
   }
 
@@ -607,13 +674,10 @@ class MFProcedureDotExport {
 
   bool has_to_be_block_begin(const MFInstruction &instruction)
   {
-    if (procedure_.entry() == &instruction) {
-      return true;
-    }
     if (instruction.prev().size() != 1) {
       return true;
     }
-    if (instruction.prev()[0]->type() == MFInstructionType::Branch) {
+    if (instruction.prev()[0].type() == MFInstructionCursor::Type::Branch) {
       return true;
     }
     return false;
@@ -623,7 +687,7 @@ class MFProcedureDotExport {
   {
     const MFInstruction *current = &representative;
     while (!this->has_to_be_block_begin(*current)) {
-      current = current->prev()[0];
+      current = current->prev()[0].instruction();
       if (current == &representative) {
         /* There is a loop without entry or exit, just break it up here. */
         break;
diff --git a/source/blender/functions/intern/multi_function_procedure_builder.cc b/source/blender/functions/intern/multi_function_procedure_builder.cc
index 3c088776bea..d30e6c0e14a 100644
--- a/source/blender/functions/intern/multi_function_procedure_builder.cc
+++ b/source/blender/functions/intern/multi_function_procedure_builder.cc
@@ -18,50 +18,6 @@
 
 namespace blender::fn {
 
-void MFInstructionCursor::insert(MFProcedure &procedure, MFInstruction *new_instruction)
-{
-  if (instruction_ == nullptr) {
-    if (is_entry_) {
-      procedure.set_entry(*new_instruction);
-    }
-    else {
-      /* The cursors points at nothing, nothing to do. */
-    }
-  }
-  else {
-    switch (instruction_->type()) {
-      case MFInstructionType::Call: {
-        static_cast<MFCallInstruction *>(instruction_)->set_next(new_instruction);
-        break;
-      }
-      case MFInstructionType::Branch: {
-        MFBranchInstruction &branch_instruction = *static_cast<MFBranchInstruction *>(
-            instruction_);
-        if (branch_output_) {
-          branch_instruction.set_branch_true(new_instruction);
-        }
-        else {
-          branch_instruction.set_branch_false(new_instruction);
-        }
-        break;
-      }
-      case MFInstructionType::Destruct: {
-        static_cast<MFDestructInstruction *>(instruction_)->set_next(new_instruction);
-        break;
-      }
-      case MFInstructionType::Dummy: {
-        static_cast<MFDummyInstruction *>(instruction_)->set_next(new_instruction);
-        break;
-      }
-      case MFInstructionType::Return: {
-        /* It shouldn't be possible to build a cursor that points to a return instruction. */
-        BLI_assert_unreachable();
-        break;
-      }
-    }
-  }
-}
-
 void MFProcedureBuilder::add_destruct(MFVariable &variable)
 {
   MFDestructInstruction &instruction = procedure_->new_destruct_instruction();
diff --git a/source/blender/functions/intern/multi_function_procedure_optimization.cc b/source/blender/functions/intern/multi_function_procedure_optimization.cc
index 8321dc7d405..728a1aead39 100644
--- a/source/blender/functions/intern/multi_function_procedure_optimization.cc
+++ b/source/blender/functions/intern/multi_function_procedure_optimization.cc
@@ -18,6 +18,20 @@
 
 namespace blender::fn::procedure_optimization {
 
+static bool uses_variable(const MFInstruction &instr, const MFVariable &variable)
+{
+  switch (instr.type()) {
+    case MFInstructionType::Branch:
+      return static_cast<const MFBranchInstruction &>(instr).condition() == &variable;
+    case MFInstructionType::Call:
+      return static_cast<const MFCallInstruction &>(instr).params().contains(&variable);
+    case MFInstructionType::Destruct:
+      return static_cast<const MFDestructInstruction &>(instr).variable() == &variable;
+    default:
+      return false;
+  }
+}
+
 void move_destructs_up(MFProcedure &procedure)
 {
   for (MFDestructInstruction *destruct_instr : procedure.destruct_instructions()) {
@@ -25,46 +39,27 @@ void move_destructs_up(MFProcedure &procedure)
     if (variable == nullptr) {
       continue;
     }
-    if (variable->users().size() != 3) {
-      /* Only support the simple case with two uses of the variable for now. */
-      continue;
-    }
-    /* TODO: This is not working yet. */
-    MFCallInstruction *last_call_instr = nullptr;
-    for (MFInstruction *instr : variable->users()) {
-      if (instr->type() == MFInstructionType::Call) {
-        MFCallInstruction *call_instr = static_cast<MFCallInstruction *>(instr);
-        const int first_param_index = call_instr->params().first_index_try(variable);
-        if (call_instr->fn().param_type(first_param_index).interface_type() ==
-            MFParamType::Output) {
-          last_call_instr = call_instr;
-        }
+    MFInstruction *last_use_in_block_instr = nullptr;
+    MFInstruction *current_instr = destruct_instr;
+    while (current_instr->prev().size() == 1) {
+      current_instr = current_instr->prev()[0].instruction();
+      if (current_instr == nullptr) {
+        break;
+      }
+      if (uses_variable(*current_instr, *variable)) {
+        last_use_in_block_instr = current_instr;
         break;
       }
     }
-    if (last_call_instr == nullptr) {
-      continue;
-    }
-    MFInstruction *after_last_call_instr = last_call_instr->next();
-    if (after_last_call_instr == destruct_instr) {
-      continue;
-    }
-    if (destruct_instr->prev().size() != 1) {
+    if (last_use_in_block_instr == nullptr) {
       continue;
     }
-    MFInstruction *before_destruct_instr = destruct_instr->prev()[0];
-    MFInstruction *after_destruct_instr = destruct_instr->next();
-    if (before_destruct_instr->type() == MFInstructionType::Call) {
-      static_cast<MFCallInstruction *>(before_destruct_instr)->set_next(after_destruct_instr);
-    }
-    else if (before_destruct_instr->type() == MFInstructionType::Destruct) {
-      static_cast<MFDestructInstruction *>(before_destruct_instr)->set_next(after_destruct_instr);
-    }
-    else {
-      continue;
+    if (last_use_in_block_instr->type() == MFInstructionType::Call) {
+      MFCallInstruction &call_instr = static_cast<MFCallInstruction &>(*last_use_in_block_instr);
+      destruct_instr->prev()[0].set_next(procedure, destruct_instr->next());
+      destruct_instr->set_next(call_instr.next());
+      call_instr.set_next(destruct_instr);
     }
-    last_call_instr->set_next(destruct_instr);
-    destruct_instr->set_next(after_last_call_instr);
   }
 }