path: root/src/ir.h

#ifndef BDL_IR_H
#define BDL_IR_H

typedef struct LineInfo {
    size_t line;
    size_t col;
} LineInfo;

typedef enum Op {
    // Arithmetic ops.
    // - Binary operations.
    // - Arguments are passed via the stack.
    OP_ADD,
    OP_SUB,
    OP_MUL,
    OP_DIV,
    OP_MOD,
    // Logic ops.
    OP_NOT,
    // Stack ops.
    // - Requires an Object to push into the stack.
    OP_PUSH,
    // - Discards the last value in the stack.
    OP_DROP,
    // - Duplicates the last value in the stack.
    OP_DUP,
    // - Rotates the last three elements in the stack.
    // - Right: [ a b c -> c a b ]
    // - Left:  [ a b c -> b c a]
    OP_ROT_RIGHT,
    OP_ROT_LEFT,
    // A label for memory access.
    // - The argument should be a unique value.
    OP_LABEL,
    // Jump/conditional ops.
    // - Take a label as argument.
    // - For conditional jumps, the last value in the stack is used.
    OP_JUMP,
    OP_JUMP_IF_TRUE,
    OP_JUMP_IF_FALSE,
    // - These require numerical objects on the stack.
    // - Consume two items in the stack.
    // - Jumps to the given label as argument when appropriate.
    OP_JUMP_IF_EQ,
    OP_JUMP_IF_NEQ,
    OP_JUMP_IF_GT,
    OP_JUMP_IF_LT,
    OP_JUMP_IF_GE,
    OP_JUMP_IF_LE,
    // Primitive complex commands.
    // - Prints the last object in the stack.
    OP_PRINT,
    // Procedures.
    // - Requires a function name as parameter.
    OP_CALL,
    // - Return position is on a know location of the stack based on the offset
    // of locals, parameters, etc.
    OP_RETURN,
    // TODO: add remaining ops.
} Op;

static const char* ops_str[] = {
    [OP_ADD]           = "OP_ADD",
    [OP_SUB]           = "OP_SUB",
    [OP_MUL]           = "OP_MUL",
    [OP_DIV]           = "OP_DIV",
    [OP_MOD]           = "OP_MOD",
    [OP_NOT]           = "OP_NOT",
    [OP_PUSH]          = "OP_PUSH",
    [OP_DROP]          = "OP_DROP",
    [OP_DUP]           = "OP_DUP",
    [OP_ROT_RIGHT]     = "OP_ROT_RIGHT",
    [OP_ROT_LEFT]      = "OP_ROT_LEFT",
    [OP_LABEL]         = "OP_LABEL",
    [OP_JUMP]          = "OP_JUMP",
    [OP_JUMP_IF_TRUE]  = "OP_JUMP_IF_TRUE",
    [OP_JUMP_IF_FALSE] = "OP_JUMP_IF_FALSE",
    [OP_JUMP_IF_EQ]    = "OP_JUMP_IF_EQ",
    [OP_JUMP_IF_NEQ]   = "OP_JUMP_IF_NEQ",
    [OP_JUMP_IF_GT]    = "OP_JUMP_IF_GT",
    [OP_JUMP_IF_LT]    = "OP_JUMP_IF_LT",
    [OP_JUMP_IF_GE]    = "OP_JUMP_IF_GE",
    [OP_JUMP_IF_LE]    = "OP_JUMP_IF_LE",
    [OP_PRINT]         = "OP_PRINT",
    [OP_CALL]          = "OP_CALL",
    [OP_RETURN]        = "OP_RETURN",
};

typedef struct Instruction {
    Op op;

    // Op arguments.
    union {
        // OP_PUSH
        Object *argument;

        // OP_LABEL
        // OP_JUMP
        // OP_JUMP_IF_FALSE
        size_t label_id;
    };

    // Original line/column for debugging purposes.
    size_t line;
    size_t col;
} Instruction;

typedef struct Procedure {
    // Procedure name.
    char *name;

    // Program code.
    Instruction *instructions;

    // Number of locals and parameters.
    size_t n_params;
    size_t n_locals;
} Procedure;

typedef struct ProgramIr {
    Procedure **procedures;
    size_t labels;
} ProgramIr;

#define INST_SIMPLE(PROC, OP, LINE, COL) \
    do { \
        Instruction inst = (Instruction){(OP), NULL, (LINE), (COL)}; \
        array_push((PROC)->instructions, inst); \
    } while(false);

#define INST_ARG(PROC, OP, ARG, LINE, COL) \
    do { \
        Instruction inst = (Instruction){(OP), (ARG), (LINE), (COL)}; \
        array_push((PROC)->instructions, inst); \
    } while(false);

void
print_instruction(Instruction *instruction) {
    printf("%4ld:%-4ld ", instruction->line, instruction->col);
    Op op = instruction->op;
    switch (op) {
        case OP_PUSH: {
            printf("%-16s -> ", ops_str[op]);
            OBJ_PRINT(instruction->argument);
        } break;
        case OP_JUMP:
        case OP_JUMP_IF_TRUE:
        case OP_JUMP_IF_FALSE:
        case OP_JUMP_IF_EQ:
        case OP_JUMP_IF_NEQ:
        case OP_JUMP_IF_GT:
        case OP_JUMP_IF_LT:
        case OP_JUMP_IF_GE:
        case OP_JUMP_IF_LE:
        case OP_LABEL: {
            printf("%-16s -> %zu\n", ops_str[op], instruction->label_id);
        } break;
        default: {
            printf("%s\n", ops_str[op]);
        } break;
    }
}

void
print_procedure(Procedure *proc) {
    printf("=====  %.*s  =====\n", (int)array_size(proc->name), proc->name);
    printf("code:\n");
    for (size_t i = 0; i < array_size(proc->instructions); ++i) {
        print_instruction(&proc->instructions[i]);
    }
}

Procedure *
proc_alloc(ProgramIr *program, StringView name) {
    Procedure *proc = calloc(1, sizeof(Procedure));
    array_init(proc->name, name.n);
    array_insert(proc->name, name.start, name.n);
    array_init(proc->instructions, 0);
    array_push(program->procedures, proc);
    return proc;
}

void compile_object(ProgramIr *program, Procedure *proc, Object *obj);

void
compile_arithmetic(ProgramIr *program, Procedure *proc, Op op,
        size_t line, size_t col, Object *args) {
    compile_object(program, proc, args->head);
    args = args->tail;
    while (args != NULL) {
        compile_object(program, proc, args->head);
        args = args->tail;
        INST_SIMPLE(proc, op, line, col);
    }
}

void
compile_numeric_cmp(ProgramIr *program, Procedure *proc, Op op,
        size_t line, size_t col, Object *args) {
    size_t label_false = program->labels++;
    size_t label_exit = program->labels++;
    compile_object(program, proc, args->head);
    args = args->tail;
    while (args != NULL) {
        compile_object(program, proc, args->head);
        args = args->tail;
        INST_SIMPLE(proc, OP_DUP, line, col);
        INST_SIMPLE(proc, OP_ROT_RIGHT, line, col);
        INST_ARG(proc, op, label_false, line, col);
    }
    INST_SIMPLE(proc, OP_DROP, line, col);
    INST_ARG(proc, OP_PUSH, &obj_true, line, col);
    INST_ARG(proc, OP_JUMP, label_exit, line, col);
    INST_ARG(proc, OP_LABEL, label_false, line, col);
    INST_SIMPLE(proc, OP_DROP, line, col);
    INST_ARG(proc, OP_PUSH, &obj_false, line, col);
    INST_ARG(proc, OP_LABEL, label_exit, line, col);
}

void
compile_print(ProgramIr *program, Procedure *proc,
        size_t line, size_t col, Object *args) {
    while (args != NULL) {
        compile_object(program, proc, args->head);
        args = args->tail;
        INST_SIMPLE(proc, OP_PRINT, line, col);
    }
}

void
compile_not(ProgramIr *program, Procedure *proc,
        size_t line, size_t col, Object *args) {
    compile_object(program, proc, args->head);
    INST_SIMPLE(proc, OP_NOT, line, col);
}

void
compile_and(ProgramIr *program, Procedure *proc,
        size_t line, size_t col, Object *args) {
    size_t label_false = program->labels++;
    size_t label_exit = program->labels++;
    while (args != NULL) {
        compile_object(program, proc, args->head);
        args = args->tail;
        INST_ARG(proc, OP_JUMP_IF_FALSE, label_false, line, col);
    }
    INST_ARG(proc, OP_PUSH, &obj_true, line, col);
    INST_ARG(proc, OP_JUMP, label_exit, line, col);
    INST_ARG(proc, OP_LABEL, label_false, line, col);
    INST_ARG(proc, OP_PUSH, &obj_false, line, col);
    INST_ARG(proc, OP_LABEL, label_exit, line, col);
}

void
compile_or(ProgramIr *program, Procedure *proc,
        size_t line, size_t col, Object *args) {
    size_t label_true = program->labels++;
    size_t label_exit = program->labels++;
    while (args != NULL) {
        compile_object(program, proc, args->head);
        args = args->tail;
        INST_ARG(proc, OP_JUMP_IF_TRUE, label_true, line, col);
    }
    INST_ARG(proc, OP_PUSH, &obj_false, line, col);
    INST_ARG(proc, OP_JUMP, label_exit, line, col);
    INST_ARG(proc, OP_LABEL, label_true, line, col);
    INST_ARG(proc, OP_PUSH, &obj_true, line, col);
    INST_ARG(proc, OP_LABEL, label_exit, line, col);
}

void
compile_proc_call(ProgramIr *program, Procedure *proc, Object *obj) {
    size_t line = obj->line;
    size_t col = obj->col;
    if (obj->head->type == OBJ_TYPE_BUILTIN) {
        switch (obj->head->builtin) {
            case BUILTIN_ADD: {
                compile_arithmetic(program, proc, OP_ADD, line, col, obj->tail);
            } break;
            case BUILTIN_SUB: {
                compile_arithmetic(program, proc, OP_SUB, line, col, obj->tail);
            } break;
            case BUILTIN_MUL: {
                compile_arithmetic(program, proc, OP_MUL, line, col, obj->tail);
            } break;
            case BUILTIN_DIV: {
                compile_arithmetic(program, proc, OP_DIV, line, col, obj->tail);
            } break;
            case BUILTIN_MOD: {
                compile_arithmetic(program, proc, OP_MOD, line, col, obj->tail);
            } break;
            case BUILTIN_PRINT: {
                compile_print(program, proc, line, col, obj->tail);
            } break;
            case BUILTIN_NOT: {
                compile_not(program, proc, line, col, obj->tail);
            } break;
            case BUILTIN_AND: {
                compile_and(program, proc, line, col, obj->tail);
            } break;
            case BUILTIN_OR: {
                compile_or(program, proc, line, col, obj->tail);
            } break;
            case BUILTIN_EQ: {
                compile_numeric_cmp(program, proc, OP_JUMP_IF_NEQ, line, col, obj->tail);
            } break;
            case BUILTIN_GT: {
                compile_numeric_cmp(program, proc, OP_JUMP_IF_LE, line, col, obj->tail);
            } break;
            case BUILTIN_LT: {
                compile_numeric_cmp(program, proc, OP_JUMP_IF_GE, line, col, obj->tail);
            } break;
            case BUILTIN_GE: {
                compile_numeric_cmp(program, proc, OP_JUMP_IF_LT, line, col, obj->tail);
            } break;
            case BUILTIN_LE: {
                compile_numeric_cmp(program, proc, OP_JUMP_IF_GT, line, col, obj->tail);
            } break;
            default: {
                assert(false && "builtin not implemented");
            } break;
        }
    } else {
        assert(false && "compile_proc_call: not implemented");
    }
}

void
compile_object(ProgramIr *program, Procedure *proc, Object *obj) {
    switch (obj->type) {
        case OBJ_TYPE_NIL:
        case OBJ_TYPE_TRUE:
        case OBJ_TYPE_FALSE:
        case OBJ_TYPE_STRING:
        case OBJ_TYPE_FIXNUM: {
            INST_ARG(proc, OP_PUSH, obj, obj->line, obj->col);
        } break;
        case OBJ_TYPE_PAIR: { compile_proc_call(program, proc, obj); } break;
        // case OBJ_TYPE_IF: { compile_if(obj); } break;
        // case OBJ_TYPE_LAMBDA: { compile_lambda(obj); } break;
        // case OBJ_TYPE_DEF: { compile_def(obj); } break;
        // case OBJ_TYPE_SYMBOL: { compile_symbol(obj); } break;
        default: {
            // TODO: assert?
            fprintf(stderr, "NOT IMPLEMENTED: compile_object for ");
            OBJ_PRINT(obj);
            exit(-1);
        } break;
    }
}

ProgramIr
compile(Program program) {
    ProgramIr program_ir = {0};
    array_init(program_ir.procedures, 0);
    Procedure *main = proc_alloc(&program_ir, STRING("main"));

    for (size_t i = 0; i < array_size(program.roots); i++) {
        Object *root = program.roots[i];
        compile_object(&program_ir, main, root);
    }

    // DEBUG:...
    for (size_t i = 0; i < array_size(program_ir.procedures); ++i) {
        print_procedure(program_ir.procedures[i]);
    }

    return program_ir;
}

#endif // BDL_IR_H