control_flow.hpp

Go to the documentation of this file.

#pragma once
 
#include "barretenberg/avm_fuzzer/fuzz_lib/instruction.hpp"
#include "barretenberg/avm_fuzzer/fuzz_lib/program_block.hpp"
#include "barretenberg/serialize/msgpack.hpp"
#include "barretenberg/vm2/testing/instruction_builder.hpp"
#include <vector>
 
struct ReturnOptions {
    uint8_t return_size;
    MemoryTagWrapper return_value_tag;
    uint16_t return_value_offset_index;
 
    MSGPACK_FIELDS(return_size, return_value_tag, return_value_offset_index);
};
 
struct InsertSimpleInstructionBlock {
    uint16_t instruction_block_idx;
 
    MSGPACK_FIELDS(instruction_block_idx);
};
 
struct JumpToNewBlock {
    uint16_t target_program_block_instruction_block_idx;
 
    MSGPACK_FIELDS(target_program_block_instruction_block_idx);
};
 
struct JumpIfToNewBlock {
    uint16_t then_program_block_instruction_block_idx;
    uint16_t else_program_block_instruction_block_idx;
    uint16_t condition_offset_index;
 
    MSGPACK_FIELDS(then_program_block_instruction_block_idx,
                   else_program_block_instruction_block_idx,
                   condition_offset_index);
};
 
struct JumpToBlock {
    uint16_t target_block_idx;
 
    MSGPACK_FIELDS(target_block_idx);
};
 
struct JumpIfToBlock {
    uint16_t target_then_block_idx;
    uint16_t target_else_block_idx;
    uint16_t condition_offset_index;
    MSGPACK_FIELDS(target_then_block_idx, target_else_block_idx, condition_offset_index);
};
 
struct FinalizeWithReturn {
    ReturnOptions return_options;
    MSGPACK_FIELDS(return_options);
};
 
struct SwitchToNonTerminatedBlock {
    uint16_t non_terminated_block_idx;
    MSGPACK_FIELDS(non_terminated_block_idx);
};
 
struct InsertInternalCall {
    uint16_t target_program_block_instruction_block_idx;
    MSGPACK_FIELDS(target_program_block_instruction_block_idx);
};
 
using CFGInstruction = std::variant<InsertSimpleInstructionBlock,
                                    JumpToNewBlock,
                                    JumpIfToNewBlock,
                                    JumpToBlock,
                                    JumpIfToBlock,
                                    FinalizeWithReturn,
                                    SwitchToNonTerminatedBlock,
                                    InsertInternalCall>;
template <class... Ts> struct overloaded_cfg_instruction : Ts... {
    using Ts::operator()...;
};
template <class... Ts> overloaded_cfg_instruction(Ts...) -> overloaded_cfg_instruction<Ts...>;
 
inline std::ostream& operator<<(std::ostream& os, const CFGInstruction& instruction)
{
    std::visit(
        overloaded_cfg_instruction{
            [&](InsertSimpleInstructionBlock arg) {
                os << "InsertSimpleInstructionBlock " << arg.instruction_block_idx;
            },
            [&](JumpToNewBlock arg) { os << "JumpToNewBlock " << arg.target_program_block_instruction_block_idx; },
            [&](JumpIfToNewBlock arg) {
                os << "JumpIfToNewBlock " << arg.then_program_block_instruction_block_idx << " "
                   << arg.else_program_block_instruction_block_idx << " " << arg.condition_offset_index;
            },
            [&](JumpToBlock arg) { os << "JumpToBlock " << arg.target_block_idx; },
            [&](JumpIfToBlock arg) {
                os << "JumpIToBlock " << arg.target_then_block_idx << " " << arg.target_else_block_idx << " "
                   << arg.condition_offset_index;
            },
            [&](FinalizeWithReturn arg) {
                os << "FinalizeWithReturn " << arg.return_options.return_size << " "
                   << arg.return_options.return_value_tag << " " << arg.return_options.return_value_offset_index;
            },
            [&](SwitchToNonTerminatedBlock arg) {
                os << "SwitchToNonTerminatedBlock " << arg.non_terminated_block_idx;
            },
            [&](InsertInternalCall arg) {
                os << "InsertInternalCall " << arg.target_program_block_instruction_block_idx;
            },
        },
        instruction);
    return os;
}
 
// TODO(defkit) make a graph for jumps, loops, etc.
class ControlFlow {
  private:
    ProgramBlock* current_block;
    ProgramBlock* start_block;
    std::vector<std::vector<FuzzInstruction>>* instruction_blocks;
 
    void process_insert_simple_instruction_block(InsertSimpleInstructionBlock instruction);
 
    void process_jump_to_new_block(JumpToNewBlock instruction);
 
    void process_jump_if_to_new_block(JumpIfToNewBlock instruction);
 
    void process_jump_to_block(JumpToBlock instruction);
 
    void process_jump_if_to_block(JumpIfToBlock instruction);
 
    void process_finalize_with_return(FinalizeWithReturn instruction);
 
    void process_switch_to_non_terminated_block(SwitchToNonTerminatedBlock instruction);
 
    void process_insert_internal_call(InsertInternalCall instruction);
 
    static std::vector<ProgramBlock*> dfs_traverse(ProgramBlock* start_block, bool reverse = false);
 
    std::vector<ProgramBlock*> get_non_terminated_blocks();
 
    std::vector<ProgramBlock*> get_reachable_blocks(ProgramBlock* block);
 
  public:
    ControlFlow(std::vector<std::vector<FuzzInstruction>>& instruction_blocks)
        : current_block(new ProgramBlock())
        , start_block(current_block)
        , instruction_blocks(&instruction_blocks)
    {}
 
    ~ControlFlow()
    {
        for (ProgramBlock* block : dfs_traverse(start_block)) {
            delete block;
        }
    }
 
    void process_cfg_instruction(CFGInstruction instruction);
 
    std::vector<uint8_t> build_bytecode(const ReturnOptions& return_options);
};