Interpreter implementations of my dispatching talk: https://jonathanmueller.dev/talk/meetingcpp2022

bytecode.hpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#ifndef BYTECODE_HPP_INCLUDED
#define BYTECODE_HPP_INCLUDED

#include <cstdint>
#include <vector>

union bytecode_inst;
using bytecode    = std::vector<bytecode_inst>;
using bytecode_ip = const bytecode_inst*;

#if DIRECT_THREADING

#    define DECLARE_OP(Op)                                                                         \
        int Op(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc);

using bytecode_op_t = int (*)(bytecode_ip, int*, bytecode_ip*, const bytecode&);

namespace bytecode_op
{
#    define BYTECODE_OP(Name, ...) int Name(bytecode_ip, int*, bytecode_ip*, const bytecode&);
#    include "bytecode_ops.inl"
#    undef BYTECODE_OP
} // namespace bytecode_op

#else

enum class bytecode_op : std::uint8_t
{
#    define BYTECODE_OP(Name, ...) Name,
#    include "bytecode_ops.inl"
#    undef BYTECODE_OP
};

using bytecode_op_t = bytecode_op;

#endif

union bytecode_inst
{
    bytecode_op_t op;
    std::uint8_t  value;
    std::int8_t   offset;

    bytecode_inst(bytecode_op_t op) : op(op) {}
    bytecode_inst(std::uint8_t value) : value(value) {}
    bytecode_inst(std::int8_t offset) : offset(offset) {}
    template <typename T>
    bytecode_inst(T) = delete;
};

#endif // BYTECODE_HPP_INCLUDED

bytecode_ops.inl

BYTECODE_OP(push, //
            {
                *vstack_ptr++ = ip[1].value;
                ip += 2;
            })

BYTECODE_OP(dup, //
            {
                auto top      = vstack_ptr[-1];
                *vstack_ptr++ = top;
                ++ip;
            })
BYTECODE_OP(swap, //
            {
                auto rhs      = *--vstack_ptr;
                auto lhs      = *--vstack_ptr;
                *vstack_ptr++ = rhs;
                *vstack_ptr++ = lhs;
                ++ip;
            })

BYTECODE_OP(add, //
            {
                auto rhs      = *--vstack_ptr;
                auto lhs      = *--vstack_ptr;
                *vstack_ptr++ = lhs + rhs;
                ++ip;
            })
BYTECODE_OP(sub, //
            {
                auto rhs      = *--vstack_ptr;
                auto lhs      = *--vstack_ptr;
                *vstack_ptr++ = lhs - rhs;
                ++ip;
            })
BYTECODE_OP(cmp_ge, //
            {
                auto rhs      = *--vstack_ptr;
                auto lhs      = *--vstack_ptr;
                *vstack_ptr++ = lhs >= rhs;
                ++ip;
            })

BYTECODE_OP(jump_if, //
            {
                auto condition = *--vstack_ptr;
                if (condition != 0)
                    ip += ip[1].offset;
                else
                    ip += 2;
            })
BYTECODE_OP(recurse, //
            {
                *cstack_ptr++ = ip + 1;
                ip            = bc.data();
            })
BYTECODE_OP(return_, //
            { ip = *--cstack_ptr; })

#if HOIST_PRINT42
BYTECODE_OP(print42, //
            {
                if (vstack_ptr[0] == 42) [[clang::musttail]]
                    return do_print_impl(ip, vstack_ptr, cstack_ptr, bc);
                ++ip;
            })
#else
BYTECODE_OP(print42, //
            {
                if (vstack_ptr[0] == 42)
                    std::puts("42");
                ++ip;
            })
#endif

BYTECODE_OP(exit, //
            { return *--vstack_ptr; })

main.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <cstdio>

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc);

int execute(const bytecode& bc, int argument)
{
    constexpr auto vstack_size = 256;
    constexpr auto cstack_size = 256;

    int         vstack[vstack_size];
    bytecode_ip cstack[cstack_size];

    auto ip         = bc.data();
    auto vstack_ptr = &vstack[0];
    auto cstack_ptr = &cstack[0];

    static const bytecode_inst exit(bytecode_op::exit);
    *cstack_ptr++ = &exit;
    *vstack_ptr++ = argument;

    return dispatch(ip, vstack_ptr, cstack_ptr, bc);
}

bytecode fib(bool print42)
{
    bytecode result;

    if (print42)
        result.push_back(bytecode_op::print42);

    // if (n < 2)
    result.push_back(bytecode_op::dup);
    result.push_back(bytecode_op::push);
    result.push_back(std::uint8_t(2));
    result.push_back(bytecode_op::cmp_ge);
    result.push_back(bytecode_op::jump_if);
    result.push_back(std::int8_t(2 + 1));

    // return n
    result.push_back(bytecode_op::return_);

    // return fib(n - 1) + fib(n - 2)
    result.push_back(bytecode_op::dup);
    result.push_back(bytecode_op::push);
    result.push_back(std::uint8_t(1));
    result.push_back(bytecode_op::sub);
    result.push_back(bytecode_op::recurse);

    result.push_back(bytecode_op::swap);
    result.push_back(bytecode_op::push);
    result.push_back(std::uint8_t(2));
    result.push_back(bytecode_op::sub);
    result.push_back(bytecode_op::recurse);

    result.push_back(bytecode_op::add);
    result.push_back(bytecode_op::return_);

    return result;
}

int main()
{
    auto result = execute(fib(false), 35);
    if (result != 9227465)
        return 1;

    std::printf("result: %d\n", result);
}

vm_call_threading.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <array>
#include <cstdio>

#if DIRECT_THREADING
#    error "direct threading is not supported"
#endif

#define BYTECODE_OP(Name, ...)                                                                     \
    int do_execute_##Name(bytecode_ip& ip, int*& vstack_ptr, bytecode_ip*& cstack_ptr,             \
                          const bytecode& bc)                                                      \
    {                                                                                              \
        __VA_ARGS__                                                                                \
        return 0;                                                                                  \
    }
#include "bytecode_ops.inl"
#undef BYTECODE_OP

constexpr std::array execute_table = {
#define BYTECODE_OP(Name, ...) &do_execute_##Name,
#include "bytecode_ops.inl"
#undef BYTECODE_OP
};

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc)
{
    while (ip->op != bytecode_op::exit)
    {
        execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);
    }

    return *--vstack_ptr;
}

vm_direct_tail_call.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <array>
#include <cstdio>

#if !DIRECT_THREADING
#    error "direct threading is required"
#endif

[[gnu::noinline]] int do_print_impl(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,
                                    const bytecode& bc)
{
    std::puts("42");
    ++ip;
    [[clang::musttail]] return ip->op(ip, vstack_ptr, cstack_ptr, bc);
}

#define BYTECODE_OP(Name, ...)                                                                     \
    int bytecode_op::Name(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,                \
                          const bytecode& bc)                                                      \
    {                                                                                              \
        __VA_ARGS__                                                                                \
        [[clang::musttail]] return ip->op(ip, vstack_ptr, cstack_ptr, bc);                         \
    }
#include "bytecode_ops.inl"
#undef BYTECODE_OP

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc)
{
    [[clang::musttail]] return ip->op(ip, vstack_ptr, cstack_ptr, bc);
}

vm_switch.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <cstdio>

#if DIRECT_THREADING
#    error "inline threading is not supported"
#endif

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc)
{
    while (true)
    {
        switch (ip->op)
        {
#define BYTECODE_OP(Name, ...)                                                                     \
    case bytecode_op::Name:                                                                        \
        __VA_ARGS__ break;
#include "bytecode_ops.inl"
#undef BYTECODE_OP

        default:
            __builtin_unreachable();
        }
    }
}

vm_switch_tail_call.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <array>
#include <cstdio>

#if DIRECT_THREADING
#    error "direct threading is not supported"
#endif

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc);

[[gnu::noinline]] int do_print_impl(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,
                                    const bytecode& bc)
{
    std::puts("42");
    ++ip;
    [[clang::musttail]] return dispatch(ip, vstack_ptr, cstack_ptr, bc);
}

#define BYTECODE_OP(Name, ...)                                                                     \
    int do_execute_##Name(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,                \
                          const bytecode& bc)                                                      \
    {                                                                                              \
        __VA_ARGS__                                                                                \
        [[clang::musttail]] return dispatch(ip, vstack_ptr, cstack_ptr, bc);                       \
    }
#include "bytecode_ops.inl"
#undef BYTECODE_OP

[[gnu::always_inline]] int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,
                                    const bytecode& bc)
{
    switch (ip->op)
    {
#define BYTECODE_OP(Name, ...)                                                                     \
    case bytecode_op::Name:                                                                        \
        [[clang::musttail]] return do_execute_##Name(ip, vstack_ptr, cstack_ptr, bc);
#include "bytecode_ops.inl"
#undef BYTECODE_OP

    default:
        __builtin_unreachable();
    }
}

vm_token_tail_call.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <array>
#include <cstdio>

#if DIRECT_THREADING
#    error "direct threading is not supported"
#endif

#define BYTECODE_OP(Name, ...)                                                                     \
    int do_execute_##Name(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,                \
                          const bytecode& bc);
#include "bytecode_ops.inl"
#undef BYTECODE_OP

constexpr std::array execute_table = {
#define BYTECODE_OP(Name, ...) &do_execute_##Name,
#include "bytecode_ops.inl"
#undef BYTECODE_OP
};

[[gnu::noinline]] int do_print_impl(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,
                                    const bytecode& bc)
{
    std::puts("42");
    ++ip;
    [[clang::musttail]] return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);
}

#define BYTECODE_OP(Name, ...)                                                                     \
    int do_execute_##Name(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,                \
                          const bytecode& bc)                                                      \
    {                                                                                              \
        __VA_ARGS__                                                                                \
        [[clang::musttail]] return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);     \
    }
#include "bytecode_ops.inl"
#undef BYTECODE_OP

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc)
{
    [[clang::musttail]] return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);
}

vm_token_threading.cpp

// Copyright (C) 2022 Jonathan Müller
// SPDX-License-Identifier: BSL-1.0

#include "bytecode.hpp"
#include <array>
#include <cstdio>

#if DIRECT_THREADING
#    error "direct threading is not supported"
#endif

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr, const bytecode& bc)
{
    constexpr std::array execute_table = {
#define BYTECODE_OP(Name, ...) &&do_execute_##Name,
#include "bytecode_ops.inl"
#undef BYTECODE_OP
    };
    goto* execute_table[int(ip->op)];

#define BYTECODE_OP(Name, ...) do_execute_##Name : __VA_ARGS__ goto* execute_table[int(ip->op)];
#include "bytecode_ops.inl"
#undef BYTECODE_OP
}