fish-compiler.dasc

#include "dasm_proto.h"
#include "dasm_x86.h"
#include "fish-codebox.h"
#include "fish-compiler.h"
#include "fish-runtime.h"
#include "fish-stack.h"
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <uthash.h>

/* used by 'n' instruction to invoke printf */
static char *format_int = "%ld";
static char *format_float = "%.16g";

#ifdef DEBUG
static char *format_instr = " Instruction: '%c', stack: ";
#endif

/* allocate a buffer and link/encode instructions, storing it into a struct */
bool
fish_link_and_encode(dasm_State **Dst, struct fish_code *code)
{
    /* link and get resulting code size */
    if (dasm_link(Dst, &code->size) != 0)
        return false;

    /* allocate writable buffer for code */
    code->buffer = mmap(NULL, code->size, PROT_READ | PROT_WRITE,
                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (code->buffer == MAP_FAILED)
    {
        code->buffer = NULL;
        return false;
    }

    /* encode instructions */
    if (dasm_encode(Dst, code->buffer) != 0)
        return false;

    /* make buffer executable */
    if (mprotect(code->buffer, code->size, PROT_READ | PROT_EXEC) != 0)
        return false;

    return true;
}

/* free DynASM state and other compiler structures */
void
fish_free_compiler(dasm_State **Dst, struct fish_state *seen_states)
{
    /* free DynASM state */
    dasm_free(Dst);

    /* free seen states hash table */
    struct fish_state *state, *tmp;
    HASH_ITER(hh, seen_states, state, tmp)
    {
        HASH_DEL(seen_states, state);
        free(state);
    }
}

void
fish_free_code(struct fish_code *code)
{
    if (!code)
        return;

    munmap(code->buffer, code->size);
    free(code);
}

struct fish_code *
fish_compile(struct fish_codebox *codebox, struct fish_state state)
{
    /* setup DynASM state */
    dasm_State *dasm_state;
    dasm_State **Dst = &dasm_state;

    |.if X64
        |.arch x64
        |.include fish-compiler-x64.dash
    |.elif X86
        |.arch x86
        |.fatal "x86 is not supported"
    |.else
        |.arch x64
        |.fatal "no valid architecture specified"
    |.endif

    |.include fish-compiler-common.dash

    |.section code

    dasm_init(Dst, DASM_MAXSECTION);

    |.globals label
    void *labels[label_MAX];
    dasm_setupglobal(Dst, labels, label_MAX);

    |.actionlist actions
    dasm_setup(Dst, actions);

    /* begin generating code */
    |.code
    |->_entry:
    | prologue

    /* keep a cache (a hash table) of seen instruction pointer states.
     * this is used to detect cycles, so we know when to stop assembling this
     * line of execution */
    struct fish_state *seen_states = NULL;

    /* flag that previous instruction was a conditional skip, or a skip
     * dependent on one */
    bool condskip = false;

    /* flag that a skip label should be placed after this instruction */
    bool addskip = false;

    /* count the number of items added/removed from stack */
    int max_stack_change = 0;

    while (state.direction != FINISHED)
    {
        /* get instruction from codebox */
        fish_number instr = fish_get(codebox, state.row, state.column);

        if (!condskip)
        {
            /* check if we've been in this state before */
            struct fish_state *seen_state = NULL;
            HASH_FIND(hh, seen_states, &state, FISH_STATE_KEYLEN, seen_state);
            if (seen_state)
            {
                /* we have been in this exact location with the same direction
                 * before; modify the end state to reflect the current state
                 * and exit */
                | mov aword end_state->row, state.row
                | mov aword end_state->column, state.column
                | mov aword end_state->direction, state.direction

                break;
            }

            /* store a copy of this state in a hash table */
            struct fish_state *heapstate = malloc(sizeof(struct fish_state));
            if (!heapstate)
            {
                fish_free_compiler(Dst, seen_states);
                return NULL;
            }

            *heapstate = state;
            HASH_ADD(hh, seen_states, row, FISH_STATE_KEYLEN, heapstate);
        }

        /* if last instruction was a skip, set a flag to place a skip label */
        if (condskip)
        {
            condskip = false;
            addskip = true;
        }

        switch (instr)
        {
            case '>': /* right */
                state.direction = RIGHT;
                break;
            case '<': /* left */
                state.direction = LEFT;
                break;
            case '^': /* up */
                state.direction = UP;
                break;
            case 'v': /* down */
                state.direction = DOWN;
                break;
            case '/': /* right <-> up, left <-> down */
                switch (state.direction)
                {
                    case RIGHT:
                        state.direction = UP;
                        break;
                    case LEFT:
                        state.direction = DOWN;
                        break;
                    case UP:
                        state.direction = RIGHT;
                        break;
                    case DOWN:
                        state.direction = LEFT;
                        break;
                    case FINISHED:
                        /* never reached */
                        break;
                }
                break;
            case '\\': /* right <-> down, left <-> up */
                switch (state.direction)
                {
                    case RIGHT:
                        state.direction = DOWN;
                        break;
                    case LEFT:
                        state.direction = UP;
                        break;
                    case UP:
                        state.direction = LEFT;
                        break;
                    case DOWN:
                        state.direction = RIGHT;
                        break;
                    case FINISHED:
                        /* never reached */
                        break;
                }
                break;
            case '|': /* right <-> left */
                switch (state.direction)
                {
                    case RIGHT:
                        state.direction = LEFT;
                        break;
                    case LEFT:
                        state.direction = RIGHT;
                        break;
                    default:
                        break;
                }
                break;
            case '_': /* up <-> down */
                switch (state.direction)
                {
                    case UP:
                        state.direction = DOWN;
                        break;
                    case DOWN:
                        state.direction = UP;
                        break;
                    default:
                        break;
                }
                break;
            case '#': /* right <-> left, up <-> down */
                switch (state.direction)
                {
                    case RIGHT:
                        state.direction = LEFT;
                        break;
                    case LEFT:
                        state.direction = RIGHT;
                        break;
                    case UP:
                        state.direction = DOWN;
                        break;
                    case DOWN:
                        state.direction = UP;
                        break;
                    case FINISHED:
                        /* never reached */
                        break;
                }
                break;
            case 'x': /* random direction */
            {
                struct fish_state temp_state;

                /* get rand() % 4 and pick a new direction */
                | call_extern rand
                | and r0, 3
                | cmp r0, 1
                | jl >1
                | je >2
                | cmp r0, 2
                | je >3
                | jmp >4

                |.macro setdirection, lbl
                    |lbl:
                    | mov aword end_state->row, temp_state.row
                    | mov aword end_state->column, temp_state.column
                    | mov aword end_state->direction, temp_state.direction
                    |jmp >5
                |.endmacro

                temp_state = state;
                temp_state.direction = RIGHT;
                fish_next(&temp_state, codebox);
                | setdirection 1
                temp_state = state;
                temp_state.direction = LEFT;
                fish_next(&temp_state, codebox);
                | setdirection 2
                temp_state = state;
                temp_state.direction = UP;
                fish_next(&temp_state, codebox);
                | setdirection 3
                temp_state = state;
                temp_state.direction = DOWN;
                fish_next(&temp_state, codebox);
                | setdirection 4

                |5:

                state.direction = FINISHED;
                break;
            }
            case '.':
                | instr_goto
                state.direction = FINISHED;
                break;
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9': /* push values 0-9 */
                | mov qword [r_stacktop], instr-'0'
                | mov byte [r_stacktop+8], INTEGER
                | fish_inc_stack 1
                break;
            case 'a':
            case 'b':
            case 'c':
            case 'd':
            case 'e':
            case 'f': /* push values 10-15 */
                | mov qword [r_stacktop], instr-'a'+10
                | mov byte [r_stacktop+8], INTEGER
                | fish_inc_stack 1
                break;
            case '+':
                | instr_add
                break;
            case '-':
                | instr_sub
                break;
            case '*':
                | instr_mul
                break;
            case ',':
                | instr_div
                break;
            case '%':
                | instr_mod
                break;
            case '=':
                | instr_eq
                break;
            case '(':
                | instr_lt
                break;
            case ')':
                | instr_gt
                break;
            case '"':
            case '\'': /* string mode - read entire string and push it */
            {
                fish_number *const string = fish_read_string(&state, codebox);
                if (string == NULL)
                {
                    fish_free_compiler(Dst, seen_states);
                    return NULL;
                }

                size_t i = 0;
                while (string[i])
                {
                    | mov qword [r_stacktop], string[i]
                    | mov byte [r_stacktop+8], INTEGER
                    | fish_inc_stack 1
                    ++i;
                }

                max_stack_change += i;

                free(string);
            }
            break;
            case '!': /* skip next instruction by adding an extra next */
                fish_next(&state, codebox);
                break;
            case '?': /* skip next instruction if popped value is zero */
                | fish_check_underflow 1
                /* get type */
                | cmp byte [r_stacktop-1], INTEGER
                | je >2
                /* compare floating point */
                | fish_load_x87 byte [r_stacktop+8]
                | fldz
                | fcomip st1
                | fstp st0
                | jmp >3
                |2:
                /* compare integer */
                | fish_dec_stack 1
                | cmp qword [r_stacktop], 0
                |3:
                /* comparison flags are now set */

                {
                    /* read following ! instructions, if any */
                    bool inverted = false;
                    while (fish_peek_next(codebox, state) == '!')
                    {
                        inverted = !inverted;
                        fish_next(&state, codebox);
                    }

                    fish_number next_instr = fish_peek_next(codebox, state);

                    if (strchr("0123456789abcdef+-*,%=():~$@onigp;",
                               next_instr))
                    {
                        /* for these simple instructions, we can insert a local
                         * label and jump to it conditionally */
                        condskip = true;

                        if (inverted)
                            | jne >9
                        else
                            | je >9
                    }
                    else
                    {
                        /* for other instructions, drop back to interpreter */
                        if (inverted)
                            | jne >1
                        else
                            | je >1

                        fish_next(&state, codebox);

                        | mov aword end_state->row, state.row
                        | mov aword end_state->column, state.column
                        | mov aword end_state->direction, state.direction
                        | jmp >2

                        fish_next(&state, codebox);

                        |1:
                        | mov aword end_state->row, state.row
                        | mov aword end_state->column, state.column
                        | mov aword end_state->direction, state.direction
                        |2:

                        state.direction = FINISHED;
                    }
                }
                break;
            case '~': /* pop and discard a value */
                | fish_check_underflow, 1
                | fish_dec_stack, 1
                break;
            case ':':
                | instr_dup
                break;
            case '$':
                | instr_swap
                break;
            case '@':
                | instr_rot
                break;
            case 'r': /* reverse stack */
                | mov stack->num_items, r_stacknum
                | prepcall1 r_stack
                | call_extern fish_reverse_stack
                break;
            case '{': /* shift stack left */
                | mov stack->num_items, r_stacknum
                | prepcall1 r_stack
                | call_extern fish_shift_left
                break;
            case '}': /* shift stack right */
                | mov stack->num_items, r_stacknum
                | prepcall1 r_stack
                | call_extern fish_shift_right
                break;
            case 'l': /* push stack size */
                | mov qword [r_stacktop], r_stacknum
                | mov byte [r_stacktop+8], INTEGER
                | fish_inc_stack 1
                break;
            case '&':
                | instr_register
                break;
            case 'o':
                | instr_output
                break;
            case 'n': /* pop a value and output a character */
                | fish_check_underflow 1
                | fish_dec_stack 1
                | cmp byte [r_stacktop+8], INTEGER
                | jne >1
                | prepcall2 format_int, [r_stacktop]
                | xor r0, r0
                | jmp >2
                |1:
                /* floating point argument in xmm0 */
                | movsd xmm0, qword [r_stacktop]
                | prepcall1 format_float
                | mov r0, 1
                |2:
                | call_extern printf
                break;
            case 'i': /* push a character from standard input */
                | call_extern getchar
                /* check for EOF */
                switch (sizeof(int))
                {
                    case 2:
                        | cmp ax, EOF
                        break;
                    case 4:
                        | cmp eax, EOF
                        break;
                    case 8:
                        | cmp rax, EOF
                        break;
                }
                | jne >1
                | mov r0, -1
                |1:
                | mov [r_stacktop], rax
                | mov byte [r_stacktop+8], INTEGER
                | fish_inc_stack 1
                break;
            case 'g':
                | instr_get
                break;
            case ';': /* end program */
                | mov aword end_state->direction, FINISHED
                | xor r_ret, r_ret
                | jmp ->epilogue

                /* if this instruction can't be skipped, stop compiling */
                if (!addskip)
                    state.direction = FINISHED;

                break;
            case ' ': /* no-op */
                break;
            default: /* syntax error */
                fish_free_compiler(Dst, seen_states);
                return NULL;
                break;
        }

        /* instructions adding one item */
        if (strchr("0123456789abcdef:lig&", instr))
            ++max_stack_change;

        /* add a forward skip label if one is needed */
        if (addskip)
        {
            addskip = false;
            |9:
        }

#ifdef DEBUG
        | mov rdi, format_instr
        | mov rsi, instr
        | mov64 rax, (uint64_t)&printf
        | call rax

        | mov r9, stack->data

        |4:
        | cmp r9, r_stacktop
        | je >3

        | push r9
        | sub r4, 8
        | prepcall1 ' '
        | call_extern putchar
        | add r4, 8
        | pop r9

        | cmp byte [r9+8], INTEGER
        | jne >1
        | prepcall2 format_int, [r9]
        | jmp >2
        |1:
        | mov rax, 1
        | movsd xmm0, qword [r9]
        | prepcall1 format_float
        |2:
        | sub r4, 8
        | push r9
        | call_extern printf
        | pop r9
        | add r4, 8

        | add r9, 9
        | jmp <4

        |3:
        | prepcall1 '\n'
        | call_extern putchar
#endif

        /* increment instruction pointer */
        fish_next(&state, codebox);
    }

    | epilogue

    /* allocate a struct to hold the compiled code */
    struct fish_code *code = malloc(sizeof(struct fish_code));

    /* link and encode */
    if (!code || !fish_link_and_encode(Dst, code))
    {
        fish_free_compiler(Dst, seen_states);
        fish_free_code(code);
        return NULL;
    }

    code->entry = labels[label_entry];
    code->max_stack_change = max_stack_change;

    return code;
}

/* vim: set ft=c : */