diff options
author | Jacques Lucke <jacques@blender.org> | 2021-09-11 12:43:59 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2021-09-11 12:43:59 +0300 |
commit | aeeffb935e9406fa2cdcb84828aa0e498b2df664 (patch) | |
tree | 338e0e5e153415b7f93846ac024ecea9bb925781 /source/blender/functions | |
parent | 6ae8de474299ec4c7c5bf2439e97998779ed4221 (diff) |
Functions: store cursors to previous instructions
Now an instruction knows the cursors where it is inserted instead
of just the instruction that references it. This has two benefits:
* An instruction knows when it is the entry instruction.
* The cursor can contain more information, e.g. if it is linked to the
true or false branch of a branch instruction.
This also simplifies updating the procedure in future optimization
passes.
Diffstat (limited to 'source/blender/functions')
4 files changed, 183 insertions, 129 deletions
diff --git a/source/blender/functions/FN_multi_function_procedure.hh b/source/blender/functions/FN_multi_function_procedure.hh index 62f2292c1d9..4c06ce98ee3 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; }; /** @@ -276,6 +324,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. */ @@ -308,12 +400,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/multi_function_procedure.cc b/source/blender/functions/intern/multi_function_procedure.cc index 6eff7bc09f8..e024cee79c8 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; } @@ -183,7 +242,11 @@ void MFProcedure::add_parameter(MFParamType::InterfaceType interface_type, MFVar void MFProcedure::set_entry(MFInstruction &entry) { + if (entry_ != NULL) { + entry_->prev_.remove_first_occurrence_and_reorder(MFInstructionCursor::ForEntry()); + } entry_ = &entry; + entry_->prev_.append(MFInstructionCursor::ForEntry()); } MFProcedure::~MFProcedure() @@ -420,7 +483,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 +534,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 +678,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 +691,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(); |