diff options
6 files changed, 377 insertions, 26 deletions
diff --git a/source/blender/functions/FN_multi_function_procedure.hh b/source/blender/functions/FN_multi_function_procedure.hh index b9540540992..aacc3f9331f 100644 --- a/source/blender/functions/FN_multi_function_procedure.hh +++ b/source/blender/functions/FN_multi_function_procedure.hh @@ -30,6 +30,7 @@ class MFCallInstruction; class MFBranchInstruction; class MFDestructInstruction; class MFDummyInstruction; +class MFReturnInstruction; class MFProcedure; enum class MFInstructionType { @@ -37,6 +38,7 @@ enum class MFInstructionType { Branch, Destruct, Dummy, + Return, }; class MFVariable : NonCopyable, NonMovable { @@ -71,6 +73,7 @@ class MFInstruction : NonCopyable, NonMovable { friend MFBranchInstruction; friend MFDestructInstruction; friend MFDummyInstruction; + friend MFReturnInstruction; public: MFInstructionType type() const; @@ -104,6 +107,8 @@ class MFBranchInstruction : public MFInstruction { MFInstruction *branch_true_ = nullptr; MFInstruction *branch_false_ = nullptr; + friend MFProcedure; + public: MFVariable *condition(); const MFVariable *condition() const; @@ -123,6 +128,8 @@ class MFDestructInstruction : public MFInstruction { MFVariable *variable_ = nullptr; MFInstruction *next_ = nullptr; + friend MFProcedure; + public: MFVariable *variable(); const MFVariable *variable() const; @@ -137,12 +144,27 @@ class MFDummyInstruction : public MFInstruction { private: MFInstruction *next_ = nullptr; + friend MFProcedure; + public: MFInstruction *next(); const MFInstruction *next() const; void set_next(MFInstruction *instruction); }; +class MFReturnInstruction : public MFInstruction { +}; + +struct MFParameter { + MFParamType::InterfaceType type; + MFVariable *variable; +}; + +struct ConstMFParameter { + MFParamType::InterfaceType type; + const MFVariable *variable; +}; + class MFProcedure : NonCopyable, NonMovable { private: LinearAllocator<> allocator_; @@ -150,8 +172,9 @@ class MFProcedure : NonCopyable, NonMovable { Vector<MFBranchInstruction *> branch_instructions_; Vector<MFDestructInstruction *> destruct_instructions_; Vector<MFDummyInstruction *> dummy_instructions_; + Vector<MFReturnInstruction *> return_instructions_; Vector<MFVariable *> variables_; - Vector<std::pair<MFParamType::InterfaceType, MFVariable *>> params_; + Vector<MFParameter> params_; MFInstruction *entry_ = nullptr; public: @@ -163,10 +186,11 @@ class MFProcedure : NonCopyable, NonMovable { MFBranchInstruction &new_branch_instruction(); MFDestructInstruction &new_destruct_instruction(); MFDummyInstruction &new_dummy_instruction(); + MFReturnInstruction &new_return_instruction(); void add_parameter(MFParamType::InterfaceType interface_type, MFVariable &variable); - Span<std::pair<MFParamType::InterfaceType, const MFVariable *>> params() const; + Span<ConstMFParameter> params() const; MFInstruction *entry(); const MFInstruction *entry() const; @@ -178,6 +202,23 @@ class MFProcedure : NonCopyable, NonMovable { void assert_valid() const; std::string to_dot() const; + + bool validate() const; + + private: + bool validate_all_instruction_pointers_set() const; + bool validate_all_params_provided() const; + bool validate_same_variables_in_one_call() const; + bool validate_parameters() const; + bool validate_initialization() const; + + struct InitState { + bool can_be_initialized = false; + bool can_be_uninitialized = false; + }; + + InitState find_initialization_state_before_instruction(const MFInstruction &target_instruction, + const MFVariable &variable) const; }; namespace multi_function_procedure_types { @@ -332,9 +373,10 @@ inline const MFInstruction *MFDummyInstruction::next() const * MFProcedure inline methods. */ -inline Span<std::pair<MFParamType::InterfaceType, const MFVariable *>> MFProcedure::params() const +inline Span<ConstMFParameter> MFProcedure::params() const { - return params_.as_span().cast<std::pair<MFParamType::InterfaceType, const MFVariable *>>(); + static_assert(sizeof(MFParameter) == sizeof(ConstMFParameter)); + return params_.as_span().cast<ConstMFParameter>(); } inline MFInstruction *MFProcedure::entry() diff --git a/source/blender/functions/FN_multi_function_procedure_builder.hh b/source/blender/functions/FN_multi_function_procedure_builder.hh index 1088c18a8b9..397a9b08beb 100644 --- a/source/blender/functions/FN_multi_function_procedure_builder.hh +++ b/source/blender/functions/FN_multi_function_procedure_builder.hh @@ -70,6 +70,8 @@ class MFProcedureBuilder { void add_destruct(MFVariable &variable); void add_destruct(Span<MFVariable *> variables); + MFReturnInstruction &add_return(); + Branch add_branch(MFVariable &condition); Loop add_loop(); diff --git a/source/blender/functions/intern/multi_function_procedure.cc b/source/blender/functions/intern/multi_function_procedure.cc index d9bf611fa34..bb7c2a98e32 100644 --- a/source/blender/functions/intern/multi_function_procedure.cc +++ b/source/blender/functions/intern/multi_function_procedure.cc @@ -17,6 +17,7 @@ #include "FN_multi_function_procedure.hh" #include "BLI_dot_export.hh" +#include "BLI_stack.hh" namespace blender::fn { @@ -167,6 +168,14 @@ MFDummyInstruction &MFProcedure::new_dummy_instruction() return instruction; } +MFReturnInstruction &MFProcedure::new_return_instruction() +{ + MFReturnInstruction &instruction = *allocator_.construct<MFReturnInstruction>().release(); + instruction.type_ = MFInstructionType::Return; + return_instructions_.append(&instruction); + return instruction; +} + void MFProcedure::add_parameter(MFParamType::InterfaceType interface_type, MFVariable &variable) { params_.append({interface_type, &variable}); @@ -205,6 +214,9 @@ MFProcedure::~MFProcedure() for (MFDummyInstruction *instruction : dummy_instructions_) { instruction->~MFDummyInstruction(); } + for (MFReturnInstruction *instruction : return_instructions_) { + instruction->~MFReturnInstruction(); + } for (MFVariable *variable : variables_) { variable->~MFVariable(); } @@ -220,6 +232,269 @@ static std::string optional_variable_to_string(const MFVariable *variable) return ss.str(); } +bool MFProcedure::validate() const +{ + if (!this->validate_all_instruction_pointers_set()) { + return false; + } + if (!this->validate_all_params_provided()) { + return false; + } + if (!this->validate_same_variables_in_one_call()) { + return false; + } + if (!this->validate_parameters()) { + return false; + } + if (!this->validate_initialization()) { + return false; + } + return true; +} + +bool MFProcedure::validate_all_instruction_pointers_set() const +{ + for (const MFCallInstruction *instruction : call_instructions_) { + if (instruction->next_ == nullptr) { + return false; + } + } + for (const MFDestructInstruction *instruction : destruct_instructions_) { + if (instruction->next_ == nullptr) { + return false; + } + } + for (const MFBranchInstruction *instruction : branch_instructions_) { + if (instruction->branch_true_ == nullptr) { + return false; + } + if (instruction->branch_false_ == nullptr) { + return false; + } + } + for (const MFDummyInstruction *instruction : dummy_instructions_) { + if (instruction->next_ == nullptr) { + return false; + } + } + return true; +} + +bool MFProcedure::validate_all_params_provided() const +{ + for (const MFCallInstruction *instruction : call_instructions_) { + for (const MFVariable *variable : instruction->params_) { + if (variable == nullptr) { + return false; + } + } + } + for (const MFBranchInstruction *instruction : branch_instructions_) { + if (instruction->condition_ == nullptr) { + return false; + } + } + for (const MFDestructInstruction *instruction : destruct_instructions_) { + if (instruction->variable_ == nullptr) { + return false; + } + } + return true; +} + +bool MFProcedure::validate_same_variables_in_one_call() const +{ + for (const MFCallInstruction *instruction : call_instructions_) { + const MultiFunction &fn = *instruction->fn_; + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + const MFVariable *variable = instruction->params_[param_index]; + for (const int other_param_index : fn.param_indices()) { + if (other_param_index == param_index) { + continue; + } + const MFVariable *other_variable = instruction->params_[other_param_index]; + if (other_variable != variable) { + continue; + } + if (ELEM(param_type.interface_type(), MFParamType::Mutable, MFParamType::Output)) { + /* When a variable is used as mutable or output parameter, it can only be used once. */ + return false; + } + const MFParamType other_param_type = fn.param_type(other_param_index); + /* A variable is allowed to be used as input more than once. */ + if (other_param_type.interface_type() != MFParamType::Input) { + return false; + } + } + } + } + return true; +} + +bool MFProcedure::validate_parameters() const +{ + Set<const MFVariable *> variables; + for (const MFParameter ¶m : params_) { + /* One variable cannot be used as multiple parameters. */ + if (!variables.add(param.variable)) { + return false; + } + } + return true; +} + +bool MFProcedure::validate_initialization() const +{ + /* TODO: Issue warning when it maybe wrongly initialized. */ + for (const MFDestructInstruction *instruction : destruct_instructions_) { + const MFVariable &variable = *instruction->variable_; + const InitState state = this->find_initialization_state_before_instruction(*instruction, + variable); + if (!state.can_be_initialized) { + return false; + } + } + for (const MFBranchInstruction *instruction : branch_instructions_) { + const MFVariable &variable = *instruction->condition_; + const InitState state = this->find_initialization_state_before_instruction(*instruction, + variable); + if (!state.can_be_initialized) { + return false; + } + } + for (const MFCallInstruction *instruction : call_instructions_) { + const MultiFunction &fn = *instruction->fn_; + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + const MFVariable &variable = *instruction->params_[param_index]; + const InitState state = this->find_initialization_state_before_instruction(*instruction, + variable); + switch (param_type.interface_type()) { + case MFParamType::Input: + case MFParamType::Mutable: { + if (!state.can_be_initialized) { + return false; + } + break; + } + case MFParamType::Output: { + if (!state.can_be_uninitialized) { + return false; + } + break; + } + } + } + } + Set<const MFVariable *> variables_that_should_be_initialized_on_return; + for (const MFParameter ¶m : params_) { + if (ELEM(param.type, MFParamType::Mutable, MFParamType::Output)) { + variables_that_should_be_initialized_on_return.add_new(param.variable); + } + } + for (const MFReturnInstruction *instruction : return_instructions_) { + for (const MFVariable *variable : variables_) { + const InitState init_state = this->find_initialization_state_before_instruction(*instruction, + *variable); + if (variables_that_should_be_initialized_on_return.contains(variable)) { + if (!init_state.can_be_initialized) { + return false; + } + } + else { + if (!init_state.can_be_uninitialized) { + return false; + } + } + } + } + return true; +} + +MFProcedure::InitState MFProcedure::find_initialization_state_before_instruction( + const MFInstruction &target_instruction, const MFVariable &target_variable) const +{ + InitState state; + + auto check_entry_instruction = [&]() { + bool caller_initialized_variable = false; + for (const MFParameter ¶m : params_) { + if (param.variable == &target_variable) { + if (ELEM(param.type, MFParamType::Input, MFParamType::Mutable)) { + caller_initialized_variable = true; + break; + } + } + } + if (caller_initialized_variable) { + state.can_be_initialized = true; + } + else { + state.can_be_uninitialized = true; + } + }; + + if (&target_instruction == entry_) { + check_entry_instruction(); + } + + Set<const MFInstruction *> checked_instructions; + Stack<const MFInstruction *> instructions_to_check; + instructions_to_check.push_multiple(target_instruction.prev_); + + while (!instructions_to_check.is_empty()) { + const MFInstruction &instruction = *instructions_to_check.pop(); + if (!checked_instructions.add(&instruction)) { + /* Skip if the instruction has been checked already. */ + continue; + } + bool state_modified = false; + switch (instruction.type_) { + case MFInstructionType::Call: { + const MFCallInstruction &call_instruction = static_cast<const MFCallInstruction &>( + instruction); + const MultiFunction &fn = *call_instruction.fn_; + for (const int param_index : fn.param_indices()) { + if (call_instruction.params_[param_index] == &target_variable) { + const MFParamType param_type = fn.param_type(param_index); + if (param_type.interface_type() == MFParamType::Output) { + state.can_be_initialized = true; + state_modified = true; + break; + } + } + } + break; + } + case MFInstructionType::Destruct: { + const MFDestructInstruction &destruct_instruction = + static_cast<const MFDestructInstruction &>(instruction); + if (destruct_instruction.variable_ == &target_variable) { + state.can_be_uninitialized = true; + state_modified = true; + } + break; + } + case MFInstructionType::Branch: + case MFInstructionType::Dummy: + case MFInstructionType::Return: { + /* These instruction types don't change the initialization state of variables. */ + break; + } + } + + if (!state_modified) { + if (&instruction == entry_) { + check_entry_instruction(); + } + instructions_to_check.push_multiple(instruction.prev_); + } + } + + return state; +} + std::string MFProcedure::to_dot() const { dot::DirectedGraph digraph; @@ -278,16 +553,22 @@ std::string MFProcedure::to_dot() const dot_node.set_shape(dot::Attr_shape::Rectangle); dot_nodes.add_new(instruction, &dot_node); } + for (MFReturnInstruction *instruction : return_instructions_) { + dot::Node &dot_node = digraph.new_node(""); + dot_node.set_shape(dot::Attr_shape::Circle); + dot_nodes.add_new(instruction, &dot_node); + } - auto create_end_node = [&]() -> dot::Node & { + auto create_missing_end_node = [&]() -> dot::Node & { dot::Node &node = digraph.new_node(""); - node.set_shape(dot::Attr_shape::Circle); + node.set_shape(dot::Attr_shape::Diamond); + node.set_background_color("red"); return node; }; auto add_edge_to_instruction_or_end = [&](dot::Node &dot_from, MFInstruction *to) { if (to == nullptr) { - dot::Node &dot_end_node = create_end_node(); + dot::Node &dot_end_node = create_missing_end_node(); digraph.new_edge(dot_from, dot_end_node); } else { @@ -300,18 +581,15 @@ std::string MFProcedure::to_dot() const dot::Node &dot_node = *dot_nodes.lookup(instruction); add_edge_to_instruction_or_end(dot_node, instruction->next()); } - for (MFBranchInstruction *instruction : branch_instructions_) { dot::Node &dot_node = *dot_nodes.lookup(instruction); add_edge_to_instruction_or_end(dot_node, instruction->branch_true()); add_edge_to_instruction_or_end(dot_node, instruction->branch_false()); } - for (MFDestructInstruction *instruction : destruct_instructions_) { dot::Node &dot_node = *dot_nodes.lookup(instruction); add_edge_to_instruction_or_end(dot_node, instruction->next()); } - for (MFDummyInstruction *instruction : dummy_instructions_) { dot::Node &dot_node = *dot_nodes.lookup(instruction); add_edge_to_instruction_or_end(dot_node, instruction->next()); diff --git a/source/blender/functions/intern/multi_function_procedure_builder.cc b/source/blender/functions/intern/multi_function_procedure_builder.cc index 1e686bbd94d..1036bb5f720 100644 --- a/source/blender/functions/intern/multi_function_procedure_builder.cc +++ b/source/blender/functions/intern/multi_function_procedure_builder.cc @@ -53,6 +53,11 @@ void MFInstructionCursor::insert(MFProcedure &procedure, MFInstruction *new_inst 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; + } } } } @@ -72,6 +77,14 @@ void MFProcedureBuilder::add_destruct(Span<MFVariable *> variables) } } +MFReturnInstruction &MFProcedureBuilder::add_return() +{ + MFReturnInstruction &instruction = procedure_->new_return_instruction(); + this->link_to_cursors(&instruction); + cursors_ = {}; + return instruction; +} + MFCallInstruction &MFProcedureBuilder::add_call_with_no_variables(const MultiFunction &fn) { MFCallInstruction &instruction = procedure_->new_call_instruction(fn); diff --git a/source/blender/functions/intern/multi_function_procedure_executor.cc b/source/blender/functions/intern/multi_function_procedure_executor.cc index 7337f53f293..92e407714f7 100644 --- a/source/blender/functions/intern/multi_function_procedure_executor.cc +++ b/source/blender/functions/intern/multi_function_procedure_executor.cc @@ -25,9 +25,8 @@ MFProcedureExecutor::MFProcedureExecutor(std::string name, const MFProcedure &pr { MFSignatureBuilder signature(std::move(name)); - for (const std::pair<MFParamType::InterfaceType, const MFVariable *> ¶m : - procedure.params()) { - signature.add(param.second->name(), MFParamType(param.first, param.second->data_type())); + for (const ConstMFParameter ¶m : procedure.params()) { + signature.add(param.variable->name(), MFParamType(param.type, param.variable->data_type())); } signature_ = signature.build(); @@ -835,7 +834,7 @@ class VariableStates { { for (const int param_index : fn.param_indices()) { MFParamType param_type = fn.param_type(param_index); - const MFVariable *variable = procedure.params()[param_index].second; + const MFVariable *variable = procedure.params()[param_index].variable; auto add_state = [&](VariableValue *value, bool input_is_initialized, @@ -1047,19 +1046,16 @@ class InstructionScheduler { indices_by_instruction_.lookup_or_add_default(instruction).append(mask.indices()); } - void add_owned_indices(const MFInstruction *instruction, Vector<int64_t> indices) + void add_owned_indices(const MFInstruction &instruction, Vector<int64_t> indices) { - if (instruction == nullptr) { - return; - } if (indices.is_empty()) { return; } BLI_assert(IndexMask::indices_are_valid_index_mask(indices)); - indices_by_instruction_.lookup_or_add_default(instruction).append(std::move(indices)); + indices_by_instruction_.lookup_or_add_default(&instruction).append(std::move(indices)); } - void add_previous_instruction_indices(const MFInstruction *instruction, + void add_previous_instruction_indices(const MFInstruction &instruction, NextInstructionInfo &instr_info) { this->add_owned_indices(instruction, std::move(instr_info.owned_indices)); @@ -1123,7 +1119,7 @@ void MFProcedureExecutor::call(IndexMask full_mask, MFParams params, MFContext c const MFCallInstruction &call_instruction = static_cast<const MFCallInstruction &>( instruction); execute_call_instruction(call_instruction, instr_info.mask(), variable_states, context); - scheduler.add_previous_instruction_indices(call_instruction.next(), instr_info); + scheduler.add_previous_instruction_indices(*call_instruction.next(), instr_info); break; } case MFInstructionType::Branch: { @@ -1134,8 +1130,8 @@ void MFProcedureExecutor::call(IndexMask full_mask, MFParams params, MFContext c IndicesSplitVectors new_indices; variable_state.indices_split(instr_info.mask(), new_indices); - scheduler.add_owned_indices(branch_instruction.branch_false(), new_indices[false]); - scheduler.add_owned_indices(branch_instruction.branch_true(), new_indices[true]); + scheduler.add_owned_indices(*branch_instruction.branch_false(), new_indices[false]); + scheduler.add_owned_indices(*branch_instruction.branch_true(), new_indices[true]); break; } case MFInstructionType::Destruct: { @@ -1143,13 +1139,17 @@ void MFProcedureExecutor::call(IndexMask full_mask, MFParams params, MFContext c static_cast<const MFDestructInstruction &>(instruction); const MFVariable *variable = destruct_instruction.variable(); variable_states.destruct(*variable, instr_info.mask()); - scheduler.add_previous_instruction_indices(destruct_instruction.next(), instr_info); + scheduler.add_previous_instruction_indices(*destruct_instruction.next(), instr_info); break; } case MFInstructionType::Dummy: { const MFDummyInstruction &dummy_instruction = static_cast<const MFDummyInstruction &>( instruction); - scheduler.add_previous_instruction_indices(dummy_instruction.next(), instr_info); + scheduler.add_previous_instruction_indices(*dummy_instruction.next(), instr_info); + break; + } + case MFInstructionType::Return: { + /* Don't insert the indices back into the scheduler. */ break; } } @@ -1157,7 +1157,7 @@ void MFProcedureExecutor::call(IndexMask full_mask, MFParams params, MFContext c for (const int param_index : this->param_indices()) { const MFParamType param_type = this->param_type(param_index); - const MFVariable *variable = procedure_.params()[param_index].second; + const MFVariable *variable = procedure_.params()[param_index].variable; VariableState &variable_state = variable_states.get_variable_state(*variable); switch (param_type.interface_type()) { case MFParamType::Input: { diff --git a/source/blender/functions/tests/FN_multi_function_procedure_test.cc b/source/blender/functions/tests/FN_multi_function_procedure_test.cc index 95267e3cf37..05efb15b0f0 100644 --- a/source/blender/functions/tests/FN_multi_function_procedure_test.cc +++ b/source/blender/functions/tests/FN_multi_function_procedure_test.cc @@ -31,8 +31,11 @@ TEST(multi_function_procedure, SimpleTest) auto [var4] = builder.add_call<1>(add_fn, {var2, var3}); builder.add_call(add_10_fn, {var4}); builder.add_destruct({var1, var2, var3}); + builder.add_return(); builder.add_output_parameter(*var4); + EXPECT_TRUE(procedure.validate()); + MFProcedureExecutor executor{"My Procedure", procedure}; MFParamsBuilder params{executor, 3}; @@ -81,6 +84,9 @@ TEST(multi_function_procedure, BranchTest) builder.set_cursor_after_branch(branch); builder.add_call(add_10_fn, {var1}); builder.add_destruct({var2}); + builder.add_return(); + + EXPECT_TRUE(procedure.validate()); MFProcedureExecutor procedure_fn{"Condition Test", procedure}; MFParamsBuilder params(procedure_fn, 5); @@ -121,6 +127,7 @@ TEST(multi_function_procedure, EvaluateOne) MFVariable *var1 = &builder.add_single_input_parameter<int>(); auto [var2] = builder.add_call<1>(add_10_fn, {var1}); builder.add_destruct(*var1); + builder.add_return(); builder.add_output_parameter(*var2); MFProcedureExecutor procedure_fn{"Evaluate One", procedure}; @@ -190,8 +197,11 @@ TEST(multi_function_procedure, SimpleLoop) builder.set_cursor_after_loop(loop); builder.add_call(add_1000_fn, {var_out}); builder.add_destruct({var_count, var_index}); + builder.add_return(); builder.add_output_parameter(*var_out); + EXPECT_TRUE(procedure.validate()); + MFProcedureExecutor procedure_fn{"Simple Loop", procedure}; MFParamsBuilder params{procedure_fn, 5}; @@ -243,8 +253,11 @@ TEST(multi_function_procedure, Vectors) auto [var_len] = builder.add_call<1>(sum_elements_fn, {var_v2}); auto [var_v3] = builder.add_call<1>(create_range_fn, {var_len}); builder.add_destruct({var_v1, var_len}); + builder.add_return(); builder.add_output_parameter(*var_v3); + EXPECT_TRUE(procedure.validate()); + MFProcedureExecutor procedure_fn{"Vectors", procedure}; MFParamsBuilder params{procedure_fn, 5}; @@ -304,8 +317,11 @@ TEST(multi_function_procedure, BufferReuse) builder.add_destruct(*var_d); auto [var_out] = builder.add_call<1>(add_10_fn, {var_e}); builder.add_destruct(*var_e); + builder.add_return(); builder.add_output_parameter(*var_out); + EXPECT_TRUE(procedure.validate()); + MFProcedureExecutor procedure_fn{"Buffer Reuse", procedure}; Array<int> inputs = {4, 1, 6, 2, 3}; |