path: root/src/compiler.h

#ifndef BDL_COMPILER_H
#define BDL_COMPILER_H


#define PRELUDE_FILE "src/x86_64/prelude.asm"
#define POSTLUDE_FILE "src/x86_64/postlude.asm"

#define NIL_VAL      1
#define BOOL_MASK    3
#define BOOL_TAG     3
#define BOOL_SHIFT   2
#define TRUE_VAL     ((1 << BOOL_SHIFT) | BOOL_TAG)
#define FALSE_VAL    ((0 << BOOL_SHIFT) | BOOL_TAG)
#define FIXNUM_MASK  1
#define FIXNUM_TAG   0
#define FIXNUM_SHIFT 1

void compile_object(Object *obj);
void compile_fixnum(Object *obj);
void compile_proc_call(Object *obj);
void compile(Root *roots);

char *
generate_label(void) {
    // Generate a unique label allocated on the heap. The caller is responsible
    // for freeing the memory.
    static size_t label_counter = 0;
    char buf[32];
    memset(buf, 0, 32);
    sprintf(buf, ".BDLL%ld", label_counter++);
    char * ret = malloc(strlen(buf));
    memcpy(ret, buf, strlen(buf));
    return ret;
}

void
emit_file(char *file_name) {
    FILE *file = fopen(file_name, "r");
    if (!file) {
        fprintf(stderr, "error: couldn't open input file: %s\n", file_name);
        exit(EXIT_FAILURE);
    }
    char buf[1024];
    size_t n = 0;
    while ((n = fread(&buf, 1, 1024, file)) > 0) {
        fwrite(buf, 1, n, stdout);
    }
}

void
compile_fixnum(Object *obj) {
    printf("    ;; --> compile_fixnum\n");
    printf("    mov     rax, %ld\n", (obj->fixnum << FIXNUM_SHIFT) | FIXNUM_TAG);
    printf("    push    rax\n");
    printf("    ;; <-- compile_fixnum\n");
}

void
compile_boolean(Object *obj) {
    printf("    ;; --> compile_boolean\n");
    int is_true = obj->type == OBJ_TYPE_TRUE;
    printf("    mov     rax, %d\n", (is_true << BOOL_SHIFT) | BOOL_TAG);
    printf("    push    rax\n");
    printf("    ;; <-- compile_boolean\n");
}

void
compile_nil(void) {
    printf("    ;; --> compile_nil\n");
    printf("    mov     rax, %d\n", NIL_VAL);
    printf("    push    rax\n");
    printf("    ;; <-- compile_nil\n");
}

typedef enum OpType {
    // Arithmetic.
    OP_ADD,
    OP_SUB,
    OP_MUL,
    OP_DIV,
    OP_MOD,
    // Type predicates.
    OP_IS_NIL,
    OP_IS_ZERO,
    OP_IS_BOOL,
    OP_IS_FIXNUM,
    // Logic operations.
    OP_NOT,
    OP_AND,
    OP_OR,
    OP_EQUAL,
    OP_GREATER,
    OP_LESS,
    OP_GREATER_EQ,
    OP_LESS_EQ,
} OpType;

void
compile_type_predicate(OpType op, Object* args) {
    printf("    ;; --> compile_type_predicate\n");
    compile_object(args->head);
    printf("    pop     rax\n");
    switch (op) {
        case OP_IS_NIL: {
            printf("    cmp     rax, %d\n", NIL_VAL);
        } break;
        case OP_IS_ZERO: {
            printf("    cmp     rax, 0\n");
        } break;
        case OP_IS_BOOL: {
            printf("    and     rax, %d\n", BOOL_MASK);
            printf("    cmp     rax, %d\n", BOOL_TAG);
        } break;
        case OP_IS_FIXNUM: {
            printf("    and     rax, %d\n", FIXNUM_MASK);
            printf("    cmp     rax, %d\n", FIXNUM_TAG);
        } break;
        default: break;
    }
    printf("    mov     rax, 0\n");
    printf("    sete    al\n");
    printf("    shl     rax, %d\n", BOOL_SHIFT);
    printf("    or      rax, %d\n", BOOL_TAG);
    printf("    push    rax\n");
    printf("    ;; <-- compile_type_predicate\n");
}

void
compile_logic_list(OpType op, Object* args) {
    printf("    ;; --> compile_logic_list\n");
    compile_object(args->head);
    if (op == OP_NOT) {
        printf("    pop     rax\n");
        printf("    cmp     rax, %d\n", FALSE_VAL);
        printf("    mov     rax, 0\n");
        printf("    sete    al\n");
        printf("    shl     rax, %d\n", BOOL_SHIFT);
        printf("    or      rax, %d\n", BOOL_TAG);
        printf("    push    rax\n");
        printf("    ;; <-- compile_logic_list\n");
        return;
    }

    // TODO: Make sure to stop evaluating if the condition is not met.
    args = args->tail;
    while (args != NULL) {
        compile_object(args->head);
        args = args->tail;

        // Current value.
        printf("    pop     rcx\n");
        printf("    cmp     rcx, %d\n", FALSE_VAL);
        printf("    mov     rcx, 0\n");
        printf("    setne   cl\n");

        // Previous value.
        printf("    pop     rax\n");
        printf("    cmp     rax, %d\n", FALSE_VAL);
        printf("    mov     rax, 0\n");
        printf("    setne   al\n");

        switch (op) {
            case OP_AND: { printf("    and     al, cl\n"); } break;
            case OP_OR:  { printf("    or      al, cl\n"); } break;
            default: break;
        }
        printf("    shl     rax, %d\n", BOOL_SHIFT);
        printf("    or      rax, %d\n", BOOL_TAG);
        printf("    push    rax\n");
    }
    printf("    ;; <-- compile_logic_list\n");
}

void
compile_cmp_list(OpType op, Object* args) {
    printf("    ;; --> compile_cmp_list\n");
    compile_object(args->head);

    // TODO: Make sure to stop evaluating if the condition is not met.
    // FIXME: Only working for two argument lists right now because we can't
    // accumulate the bool and compare it with an int. We can fix it by passing
    // two values on the stack (previous value and current result) or by only
    // passing a previous value and having a conditional jump (need labels for
    // that).
    args = args->tail;
    while (args != NULL) {
        compile_object(args->head);
        args = args->tail;

        // Current value.
        printf("    pop     rcx\n");
        printf("    sar     rcx, %d\n", FIXNUM_SHIFT);

        // Previous value.
        printf("    pop     rax\n");
        printf("    sar     rax, %d\n", FIXNUM_SHIFT);

        printf("    cmp     rax, rcx\n");
        printf("    mov     rax, 0\n");

        switch (op) {
            case OP_EQUAL: {
                printf("    sete    al\n");
            } break;
            case OP_GREATER: {
                printf("    setg    al\n");
            } break;
            case OP_LESS: {
                printf("    setl    al\n");
            } break;
            case OP_GREATER_EQ: {
                printf("    setge   al\n");
            } break;
            case OP_LESS_EQ: {
                printf("    setle   al\n");
            } break;
            default: break;
        }
        printf("    shl     rax, %d\n", BOOL_SHIFT);
        printf("    or      rax, %d\n", BOOL_TAG);
        printf("    push    rax\n");
    }
    printf("    ;; <-- compile_cmp_list\n");
}

void
compile_arithmetic_list(OpType op, Object* args) {
    printf("    ;; --> compile_arithmetic\n");
    compile_object(args->head);
    args = args->tail;
    while (args != NULL) {
        compile_object(args->head);
        args = args->tail;
        printf("    pop     rcx\n");
        printf("    pop     rax\n");
        switch (op) {
            case OP_ADD: { printf("    add     rax, rcx\n"); } break;
            case OP_SUB: { printf("    sub     rax, rcx\n"); } break;
            case OP_MUL: {
                printf("    sar     rax, %d\n", FIXNUM_SHIFT);
                printf("    sar     rcx, %d\n", FIXNUM_SHIFT);
                printf("    mul     rcx\n");
                printf("    shl     rax, %d\n", FIXNUM_SHIFT);
            } break;
            case OP_DIV: {
                printf("    sar     rax, %d\n", FIXNUM_SHIFT);
                printf("    sar     rcx, %d\n", FIXNUM_SHIFT);
                printf("    mov     rdx, 0\n");
                printf("    div     rcx\n");
                printf("    shl     rax, %d\n", FIXNUM_SHIFT);
            } break;
            case OP_MOD: {
                printf("    sar     rax, %d\n", FIXNUM_SHIFT);
                printf("    sar     rcx, %d\n", FIXNUM_SHIFT);
                printf("    mov     rdx, 0\n");
                printf("    div     rcx\n");
                printf("    mov     rax, rdx\n");
                printf("    shl     rax, %d\n", FIXNUM_SHIFT);
            } break;
            default: break;
        }
        printf("    push    rax\n");
    }
    printf("    ;; <-- compile_arithmetic\n");
}

void
compile_proc_call(Object *obj) {
    // TODO: Probably we want to use a hash table for these lookups that is
    // initialized at the start of the compilation procedure.
    if (sv_equal(&obj->head->text, &STRING("+"))) {
        compile_arithmetic_list(OP_ADD, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("-"))) {
        compile_arithmetic_list(OP_SUB, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("*"))) {
        compile_arithmetic_list(OP_MUL, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("/"))) {
        compile_arithmetic_list(OP_DIV, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("%"))) {
        compile_arithmetic_list(OP_MOD, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("nil?"))) {
        compile_type_predicate(OP_IS_NIL, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("zero?"))) {
        compile_type_predicate(OP_IS_ZERO, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("fixnum?"))) {
        compile_type_predicate(OP_IS_FIXNUM, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("bool?"))) {
        compile_type_predicate(OP_IS_BOOL, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("display"))) {
        compile_object(obj->tail->head);
        printf("    pop     rdi\n");
        printf("    call    display\n");
    } else if (sv_equal(&obj->head->text, &STRING("not"))) {
        compile_logic_list(OP_NOT, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("and"))) {
        compile_logic_list(OP_AND, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("or"))) {
        compile_logic_list(OP_OR, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("="))) {
        compile_cmp_list(OP_EQUAL, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING(">"))) {
        compile_cmp_list(OP_GREATER, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("<"))) {
        compile_cmp_list(OP_LESS, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING(">="))) {
        compile_cmp_list(OP_GREATER_EQ, obj->tail);
    } else if (sv_equal(&obj->head->text, &STRING("<="))) {
        compile_cmp_list(OP_LESS_EQ, obj->tail);
    } else {
        fprintf(stderr, "error: not implemented\n");
        exit(EXIT_FAILURE);
    }
}

void
compile_object(Object *obj) {
    switch (obj->type) {
        case OBJ_TYPE_NIL: { compile_nil(); } break;
        case OBJ_TYPE_TRUE:
        case OBJ_TYPE_FALSE: { compile_boolean(obj); } break;
        case OBJ_TYPE_FIXNUM: { compile_fixnum(obj); } break;
        case OBJ_TYPE_PAIR: { compile_proc_call(obj); } break;
        default: break;
    }
}

void
compile(Root *roots) {
    printf("%%define NIL_VAL      %d\n", NIL_VAL);
    printf("%%define BOOL_MASK    %d\n", BOOL_MASK);
    printf("%%define BOOL_TAG     %d\n", BOOL_TAG);
    printf("%%define BOOL_SHIFT   %d\n", BOOL_SHIFT);
    printf("%%define FIXNUM_MASK  %d\n", FIXNUM_MASK);
    printf("%%define FIXNUM_TAG   %d\n", FIXNUM_TAG);
    printf("%%define FIXNUM_SHIFT %d\n", FIXNUM_SHIFT);
    printf("\n");
    emit_file(PRELUDE_FILE);
    for (size_t i = 0; i < array_size(roots); i++) {
        Object *root = roots[i];
        compile_object(root);
        // OBJ_PRINT(root);
    }
    emit_file(POSTLUDE_FILE);
}

#endif // BDL_COMPILER_H