<commit_before>#include <vector>
#include <sys/mman.h>

#include "it.x64.asm.h"


static const struct rejit_threadset_t *NFA    = NULL;  // used for offset calculation
static const struct rejit_thread_t    *THREAD = NULL;

struct re2jit::native
{
    void *_code;
    void *_entry;
    size_t _size;

    native(re2::Prog *prog) : _code(NULL), _entry(NULL), _size(0)
    {
        size_t i;
        size_t n = prog->size();

        as code;
        std::vector< as::label* > labels(n);

        for (auto& ref : labels) ref = &code.mark();

        as::label& fail    = code.mark();  // return 0, meaning did not enter an accepting state
        as::label& succeed = code.mark();  // "fail" without zeroing return value
        code.xor_(as::eax, as::eax).mark(succeed).ret();

        // How many transitions have the i-th opcode as a target.
        // Opcodes with indegree 1 don't need to be tracked in the bit vector
        // (as there is only one way to reach them and we've already checked that).
        // Opcodes with indegree 0 are completely unreachable, no need to compile those.
        std::vector< unsigned > indegree(n);

        ssize_t *stack = new ssize_t[prog->size()];
        ssize_t *stptr = stack;
        indegree[*stptr++ = prog->start()]++;

        while (stptr != stack) {
            auto op  = prog->inst(*--stptr);
            auto vec = re2jit::is_extcode(prog, op);

            for (auto& op : vec)
                if (!indegree[op.out()]++)
                    *stptr++ = op.out();

            if (!vec.size())
                switch (op->opcode()) {
                    case re2::kInstAlt:
                    case re2::kInstAltMatch:
                        if (!indegree[op->out1()]++)
                            *stptr++ = op->out1();

                    default:
                        if (!indegree[op->out()]++)
                            *stptr++ = op->out();

                    case re2::kInstFail:
                    case re2::kInstMatch:
                        break;

                    case re2::kInstByteRange:
                        if (!indegree[op->out()])
                            *stptr++ = op->out();
                        // subsequent byte ranges are concatenated into one block of code
                        if (prog->inst(op->out())->opcode() != re2::kInstByteRange)
                            indegree[op->out()]++;
                }
        }

        delete[] stack;

        for (i = 0; i < n; i++) if (indegree[i]) {
            code.mark(*labels[i]);
            // Each opcode should conform to the System V ABI calling convention.
            //   argument 1: %rdi = struct rejit_threadset_t *nfa
            //   return reg: %rax = 1 iff found a match somewhere
            auto op  = prog->inst(i);
            auto vec = re2jit::is_extcode(prog, op);

            // kInstFail will do `ret` anyway.
            if (op->opcode() != re2::kInstFail && indegree[i] > 1)
                code// if (bit(nfa->visited, i) == 1) return; bit(nfa->visited, i) = 1;
                    .mov  (as::mem{as::rdi} + &NFA->visited, as::rsi)
                    .test ((as::i8) (1 << (i % 8)), as::mem{as::rsi} + i / 8).jmp(fail, as::not_zero)
                    .or_  ((as::i8) (1 << (i % 8)), as::mem{as::rsi} + i / 8);

            if (vec.size()) {
                size_t i = 0;
                std::vector< as::label* > options(vec.size() - 1);

                for (auto& op : vec) {
                    as::label* lb;

                    if (i != 0)
                        code.mark(*options[i - 1]);

                    if (++i != vec.size()) {
                        code.push  (as::rdi).call  (*(lb = &code.mark()))
                            .pop   (as::rdi).jmp   (*(options[i - 1] = &code.mark()));
                        code.mark(*lb);
                    }

                    switch (op.opcode()) {
                        case re2jit::inst::kUnicodeType:
                            code// utf8_chr = rejit_read_utf8(nfa->input, nfa->length);
                                .push (as::rdi)
                                .mov  (as::mem{as::rdi} + &NFA->length, as::rsi)
                                .mov  (as::mem{as::rdi} + &NFA->input,  as::rdi)
                                .call ((void *) &rejit_read_utf8)
                                .pop  (as::rdi)
                                // if ((utf8_length = utf8_chr >> 32) == 0) return;<commit_msg>x64: emit alternating pseudo-insts in reverse order.<commit_after>#include <vector>
#include <sys/mman.h>

#include "it.x64.asm.h"


static const struct rejit_threadset_t *NFA    = NULL;  // used for offset calculation
static const struct rejit_thread_t    *THREAD = NULL;

struct re2jit::native
{
    void *_code;
    void *_entry;
    size_t _size;

    native(re2::Prog *prog) : _code(NULL), _entry(NULL), _size(0)
    {
        size_t i;
        size_t n = prog->size();

        as code;
        std::vector< as::label* > labels(n);

        for (auto& ref : labels) ref = &code.mark();

        as::label& fail    = code.mark();  // return 0, meaning did not enter an accepting state
        as::label& succeed = code.mark();  // "fail" without zeroing return value
        code.xor_(as::eax, as::eax).mark(succeed).ret();

        // How many transitions have the i-th opcode as a target.
        // Opcodes with indegree 1 don't need to be tracked in the bit vector
        // (as there is only one way to reach them and we've already checked that).
        // Opcodes with indegree 0 are completely unreachable, no need to compile those.
        std::vector< unsigned > indegree(n);

        ssize_t *stack = new ssize_t[prog->size()];
        ssize_t *stptr = stack;
        indegree[*stptr++ = prog->start()]++;

        while (stptr != stack) {
            auto op  = prog->inst(*--stptr);
            auto vec = re2jit::is_extcode(prog, op);

            for (auto& op : vec)
                if (!indegree[op.out()]++)
                    *stptr++ = op.out();

            if (!vec.size())
                switch (op->opcode()) {
                    case re2::kInstAlt:
                    case re2::kInstAltMatch:
                        if (!indegree[op->out1()]++)
                            *stptr++ = op->out1();

                    default:
                        if (!indegree[op->out()]++)
                            *stptr++ = op->out();

                    case re2::kInstFail:
                    case re2::kInstMatch:
                        break;

                    case re2::kInstByteRange:
                        if (!indegree[op->out()])
                            *stptr++ = op->out();
                        // subsequent byte ranges are concatenated into one block of code
                        if (prog->inst(op->out())->opcode() != re2::kInstByteRange)
                            indegree[op->out()]++;
                }
        }

        delete[] stack;

        for (i = 0; i < n; i++) if (indegree[i]) {
            code.mark(*labels[i]);
            // Each opcode should conform to the System V ABI calling convention.
            //   argument 1: %rdi = struct rejit_threadset_t *nfa
            //   return reg: %rax = 1 iff found a match somewhere
            auto op  = prog->inst(i);
            auto vec = re2jit::is_extcode(prog, op);

            // kInstFail will do `ret` anyway.
            if (op->opcode() != re2::kInstFail && indegree[i] > 1)
                code// if (bit(nfa->visited, i) == 1) return; bit(nfa->visited, i) = 1;
                    .mov  (as::mem{as::rdi} + &NFA->visited, as::rsi)
                    .test ((as::i8) (1 << (i % 8)), as::mem{as::rsi} + i / 8).jmp(fail, as::not_zero)
                    .or_  ((as::i8) (1 << (i % 8)), as::mem{as::rsi} + i / 8);

            if (vec.size()) {
                std::vector< as::label* > options(vec.size() - 1);

                for (size_t i = vec.size(); i; ) {
                    if (i != vec.size())
                        code.mark(*options[i]);
                    // alternate between all opcodes in `vec`
                    auto& op = vec[--i];
                    // code is emitted in reverse priority order within this loop.
                    // first call the next opcode (it has higher priority), and only then
                    // evaluate this one.
                    if (i != 0)
                        code.push  (as::rdi)
                            .call  (*(options[i - 1] = &code.mark()))
                            .pop   (as::rdi);

                    switch (op.opcode()) {
                        case re2jit::inst::kUnicodeType:
                            code// utf8_chr = rejit_read_utf8(nfa->input, nfa->length);
                                .push (as::rdi)
                                .mov  (as::mem{as::rdi} + &NFA->length, as::rsi)
                                .mov  (as::mem{as::rdi} + &NFA->input,  as::rdi)
                                .call ((void *) &rejit_read_utf8)
                                .pop  (as::rdi)
                                // if ((utf8_length = utf8_chr >> 32) == 0) return;
{'fraction_non_alphanumeric': 0.14454148471615721, 'fraction_numerical': 0.010262008733624454, 'mean_word_length': 1.32159148504815, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 67, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '61211', 'n_tokens_mistral': 2892, 'n_tokens_neox': 2694, 'n_words': 712}