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.
This commit is contained in:
parent
6ae8de4742
commit
aeeffb935e
|
@ -42,6 +42,55 @@ enum class MFInstructionType {
|
|||
Return,
|
||||
};
|
||||
|
||||
/**
|
||||
* 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
|
||||
|
@ -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;
|
||||
};
|
||||
|
||||
/**
|
||||
|
@ -275,6 +323,50 @@ using MFDestructInstruction = fn::MFDestructInstruction;
|
|||
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_;
|
||||
}
|
||||
|
|
|
@ -24,31 +24,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.
|
||||
*/
|
||||
|
@ -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);
|
||||
|
||||
|
@ -121,38 +96,6 @@ struct MFProcedureBuilder::Loop {
|
|||
MFDummyInstruction *end = nullptr;
|
||||
};
|
||||
|
||||
/* --------------------------------------------------------------------
|
||||
* 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);
|
||||
}
|
||||
}
|
||||
|
||||
|
|
|
@ -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;
|
||||
|
|
|
@ -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();
|
||||
|
|
Loading…
Reference in New Issue