Current plan to make Thorin an extensible IR

ir.cpp

// g++ -std=c++17 ir.cpp -pedantic -Wall -Wextra -g -o ir
#include <type_traits>
#include <unordered_set>
#include <cassert>
#include <cstdint>
#include <iostream>

// Def is just exposing the data, nothing more
struct Def {
    uint32_t gid;
    uint32_t tag;
    const Def* op; // just one op for demo.

    Def(uint32_t gid, uint32_t tag, const Def* op)
        : gid(gid), tag(tag), op(op)
    {}

    struct Hash {
        uint32_t operator () (const Def* def) const {
            return def->op ? (33 * def->op->gid) ^ def->tag : def->tag;
        }
    };
    struct Equal {
        bool operator () (const Def* a, const Def* b) const {
            return a->tag == b->tag &&
                   !((a->op != nullptr) ^ (b->op != nullptr)) &&
                   (a->op == nullptr || (a->op->gid == b->op->gid));
        }
    };
};

// Matchers allow custom pattern matching on IR nodes
template <class M, class... Args>
struct MatchAnd {
    static bool match(const Def* def) { return M::match(def) && MatchAnd<Args...>::match(def); }
};

template <class M>
struct MatchAnd<M> {
    static bool match(const Def* def) { return M::match(def); }
};

template <class M, bool Default = false>
struct MatchOp {
    static bool match(const Def* def) { return def->op ? M::match(def->op) : Default; }
};

template <uint32_t Tag>
struct MatchTag {
    static bool match(const Def* def) { return def->tag == Tag; }
};

// Dispatch mechanism to select the proper wrapper depending on the IR nodes
#define DECLARE_DISPATCH(IR) \
    template <> \
    struct Dispatch<IR> { \
        template <class F> \
        static typename std::invoke_result<F, IR>::type dispatch(const Def*, F); \
    };
#define DISPATCH_BEGIN(IR) \
    template <class F> \
    typename std::invoke_result<F, IR>::type Dispatch<IR>::dispatch(const Def* def, F f) { \
        if
#define DISPATCH(T) \
        (T::match(def)) return f(T(def)); else if
#define DISPATCH_END(IR) \
        (true) { \
            assert(false); \
            return typename std::invoke_result<F, IR>::type(); \
        } \
    }

// Core IR, common to all nodes
namespace core {

template <class IR>
struct Dispatch {};

// Base functionality for all IR nodes
template <class IR>
class Node {
    template <class F>
    using DispatchResult = typename std::invoke_result<F, IR>::type;

public:
    enum Tag : uint32_t {
        Star,
        Bot,
        Max
    };

    Node(const Def* def)
        : def_(def)
    {}

    const Def* def() const { return def_; }

    template <class T>
    T isa() {
        static_assert(std::is_base_of<Node, T>::value);
        return T::match(def()) ? def() : nullptr;
    }
    template <class T>
    T as() {
        static_assert(std::is_base_of<Node, T>::value);
        assert(isa<T>());
        return def();
    }
    template <class T> const T isa() const { return const_cast<Node*>(this)->isa<T>(); }
    template <class T> const T as()  const { return const_cast<Node*>(this)-> as<T>(); }

    operator bool () const { return def(); }
    bool operator == (const Node& other) const { return other.def() == def(); }
    bool operator != (const Node& other) const { return other.def() != def(); }

    // Example of inheritable functionality
    template <class T> static bool has_arity(T) { return &T::arity != &Node::arity; }
    size_t arity() const { return dispatch([] (auto type) { assert(has_arity(type)); return type.arity(); }); }

    template <class F>
    DispatchResult<F> dispatch(F f) const { return Dispatch<IR>::dispatch(def(), f); }
    template <class F>
    DispatchResult<F> dispatch(F f) { return Dispatch<IR>::dispatch(def(), f); }

private:
    const Def* def_;
};

template <class> class World;

template <class IR>
class Star : public IR, public MatchTag<Node<IR>::Star> {
public:
    Star(const Def* def)
        : IR(def)
    {}

    size_t arity() const { return 0; }

    friend World<IR>;
    friend Node<IR>;
};

template <class IR>
class Bot : public IR, public MatchTag<Node<IR>::Bot> {
public:
    Bot(const Def* def)
        : IR(def)
    {}

    size_t arity() const { return 0; }

    friend World<IR>;
    friend Node<IR>;
};

// Constructor for all core nodes
template <class IR>
class World {
public:
    virtual ~World() {
        for (auto def : defs_)
            delete def;
    }

    const Star<IR> star() { return insert(Node<IR>::Star, nullptr); }
    const Bot<IR>  bot(const IR& type) { return insert(Node<IR>::Bot, type.def()); }

protected:
    template <class... Args>
    const Def* insert(Args&&... args) {
        Def def(gid_, std::forward<Args&&>(args)...);
        auto it = defs_.find(&def);
        if (it != defs_.end())
            return *it;
        gid_++;
        return *defs_.insert(new Def { def }).first;
    }

private:
    std::unordered_set<const Def*, Def::Hash, Def::Equal> defs_;
    uint32_t gid_ = 0;
};

}

// Forward declare the dispatcher so that it is available to core::Node
namespace artic {
    class Type;
}
namespace core {
    DECLARE_DISPATCH(artic::Type)
}

// Custom IR (e.g. artic)
namespace artic {

// Artic type, inherits from all the functionality in core::Node
class Type : public core::Node<Type> {
public:
    // Custom tags go here
    enum Tag {
        Top = core::Node<Type>::Max, 
        Max
    };

    Type(const Def* def)
        : Node(def)
    {}

    // New functionality (not available in the core)
    template <class T> static bool has_print(T) { return &T::print != &Type::print; }
    template <class T> static bool has_subtype(T) { return &T::subtype != &Type::subtype; }

    void print() const { dispatch([&] (auto type) { assert(has_print(type)); type.print(); }); }
    void println() const { print(); std::cout << std::endl; }
    bool subtype(const Type& other) const { return dispatch([&] (auto type) { assert(has_subtype(type)); return type.subtype(other); }); }
};

// Examples of inherited IR nodes
class Star : public core::Star<Type> {
public:
    Star(const Def* def)
        : core::Star<Type>(def)
    {}

    void print() const { std::cout << "*"; }
    bool subtype(const Type&) const { return false; }
};

class Bot : public core::Bot<Type> {
public:
    Bot(const Def* def)
        : core::Bot<Type>(def)
    {}

    size_t arity() const { return 32; } // Can override the behaviour of core::Bot

    void print() const { std::cout << "bot: "; Type(def()->op).print(); }
    bool subtype(const Type& other) const { return !other.isa<artic::Star>(); }
};

// Example of custom IR node
class Top : public Type, public MatchTag<Type::Top> {
public:
    Top(const Def* def)
        : Type(def)
    {}

    size_t arity() const { return 0; }

    void print() const { std::cout << "top: "; Type(def()->op).print(); }
    bool subtype(const Type& other) const { return other.isa<artic::Top>(); }

    friend class TypeTable;
    friend class Type;
};

// Example of custom matcher on IR nodes
class BotTop : public Type, public MatchAnd<MatchTag<Type::Bot>, MatchOp<MatchTag<Type::Top>>> {
public:
    BotTop(const Def* def)
        : Type(def)
    {
        assert(!def || match(def));
    }

    size_t arity() const { return 73; }

    void print() const { std::cout << "bottop: "; Type(def()->op->op).print(); }
    bool subtype(const Type& other) const { return artic::Bot(def()).subtype(other); }
};

class TypeTable : protected core::World<Type> {
public:
    const Star star() { return core::World<Type>::star().def(); }
    const Bot bot(const Type& type) { return core::World<Type>::bot(type).def(); }
    const Top top(const Type& type) { return insert(Type::Top, type.def()); }
    const BotTop bottop(const Type& type) { return bot(top(type)).def(); }
};

}

namespace core {
    DISPATCH_BEGIN(artic::Type)
        DISPATCH(artic::Star)
        DISPATCH(artic::BotTop)
        DISPATCH(artic::Bot)
        DISPATCH(artic::Top)
    DISPATCH_END(artic::Type)
}

int main() {
    artic::TypeTable table;
    const artic::Star star = table.star();
    const artic::Bot bot   = table.bot(table.star());
    const artic::Top top   = table.top(table.star());
    assert(bot.isa<artic::Bot>());
    assert(!bot.isa<artic::Star>());
    assert(!bot.isa<artic::Top>());
    assert(top.isa<artic::Top>());
    assert(!top.isa<artic::Bot>());
    assert(!top.isa<artic::Star>());
    assert(star.isa<artic::Star>());
    assert(!star.isa<artic::Bot>());
    assert(!star.isa<artic::Top>());
    assert(star != bot);
    assert(star != top);
    assert(star == star);
    assert(bot == bot);
    assert(bot != top);
    assert(top == top);
    assert(!bot.subtype(star));
    assert(bot.subtype(top));
    assert(!star.subtype(bot));
    assert(!star.subtype(top));
    assert(star == table.star());
    assert(bot == table.bot(table.star()));
    assert(top == table.top(table.star()));
    const artic::BotTop bottop = table.bottop(table.star());
    assert(bottop == table.bot(table.top(table.star())));
    assert(bottop.arity() == 73);
    assert(top.arity() == 0);
    assert(bot.arity() == 32);
    assert(star.arity() == 0);
    assert(artic::Type(bottop.def()).arity() == 73);
    assert(artic::Type(top.def()).arity() == 0);
    assert(artic::Type(bot.def()).arity() == 32);
    assert(artic::Type(star.def()).arity() == 0);
    star.println();
    bot.println();
    top.println();
    bottop.println();
    return 0;
}