diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/all.h | 5 | ||||
| -rw-r--r-- | src/ast_dump.c | 68 | ||||
| -rw-r--r-- | src/bfc.c | 61 | ||||
| -rw-r--r-- | src/codegen.c | 81 | ||||
| -rw-r--r-- | src/optimizer.c | 134 |
5 files changed, 312 insertions, 37 deletions
@@ -40,7 +40,8 @@ typedef enum { AST_PTR_DEC, AST_OUT, AST_IN, - AST_LOOP + AST_LOOP, + AST_CLEAR } ast_type_e; struct ast_node { @@ -58,7 +59,9 @@ typedef struct { parser_t parser_init(lexer_t *lx); ast_node_t *parse_program(parser_t *p); +ast_node_t *optimize_ast(ast_node_t *ast); void ast_free(ast_node_t *node); +void ast_dump(ast_node_t *node, int depth); // codegen diff --git a/src/ast_dump.c b/src/ast_dump.c new file mode 100644 index 0000000..0224c09 --- /dev/null +++ b/src/ast_dump.c @@ -0,0 +1,68 @@ +#include "all.h" +#include <stddef.h> +#include <stdio.h> + +static const char *type_name(ast_type_e type) { + switch (type) { + case AST_INC: + return "INC"; + case AST_DEC: + return "DEC"; + case AST_PTR_INC: + return "PTR_INC"; + case AST_PTR_DEC: + return "PTR_DEC"; + case AST_OUT: + return "OUT"; + case AST_IN: + return "IN"; + case AST_LOOP: + return "LOOP"; + case AST_CLEAR: + return "CLEAR"; + default: + return "?"; + } +} + +void ast_dump(ast_node_t *node, int depth) { + while (node) { + + for (int i = 0; i < depth; i++) + fprintf(stderr, " "); + + fprintf(stderr, "%s(%dx / %zu len)", type_name(node->type), node->val, + node->children.len); + + switch (node->type) { + case AST_INC: + case AST_DEC: + case AST_PTR_INC: + case AST_PTR_DEC: + break; + + default: + break; + } + + fprintf(stderr, "\n"); + + if (node->type == AST_LOOP) { + + for (int i = 0; i < depth; i++) + fprintf(stderr, " "); + + fprintf(stderr, "{\n"); + + for (int i = 0; i < node->children.len; i++) + ast_dump(node->children._data[i], depth + 1); + + for (size_t i = 0; i < depth; i++) + fprintf(stderr, " "); + + fprintf(stderr, "}\n"); + } + + node = node->next; + } +} @@ -1,12 +1,25 @@ #include "all.h" #include "str.h" +#include <stdbool.h> #include <stdio.h> #include <string.h> #include <sys/types.h> #include <sys/wait.h> #include <unistd.h> -int main(void) { +int main(int argc, char *argv[]) { + bool dump_c = false; + bool dump_ast = false; + + for (int i = 1; i < argc; i++) { + if (strcmp("-cdump", argv[i]) == 0) { + dump_c = true; + } + if (strcmp("-ast_dump", argv[i]) == 0) { + dump_ast = true; + } + } + str input = {0}; str_append_fread(&input, stdin); @@ -18,8 +31,14 @@ int main(void) { // Run the parser and turn tokens into an AST representation parser_t p = parser_init(&lexer); ast_node_t *ast = parse_program(&p); + ast = optimize_ast(ast); + if (dump_ast) + ast_dump(ast, 0); str c_code = gen_code(ast); + if (dump_c) + fprintf(stderr, "%s\n", c_code.data); + // Run gcc int fd[2]; pipe(fd); @@ -29,14 +48,23 @@ int main(void) { close(fd[0]); close(fd[1]); - char *argv[] = {"gcc", "-Os", - "-flto", "-fuse-linker-plugin", - "-DNDEBUG", "-fomit-frame-pointer", - "-nostdlib", "-nostartfiles", - "-no-pie", "-fno-stack-protector", - "-o", "/proc/self/fd/1", - "-x", "c", - "-", NULL}; + char *argv[] = {"gcc", + "-Os", + "-flto", + "-fuse-linker-plugin", + "-DNDEBUG", + "-fomit-frame-pointer", + "-nostdlib", + "-nostartfiles", + "-ffreestanding", + "-no-pie", + "-fno-stack-protector", + "-o", + "/proc/self/fd/1", + "-x", + "c", + "-", + NULL}; execvp("gcc", argv); perror("execvp"); @@ -47,7 +75,20 @@ int main(void) { close(fd[0]); write(fd[1], c_code.data, strlen(c_code.data)); close(fd[1]); - wait(NULL); + int status; + wait(&status); + + if (WIFEXITED(status)) { + int code = WEXITSTATUS(status); + if (code != 0) { + fprintf(stderr, "GCC failed with exit code %d\n", code); + fprintf(stderr, "Dumping C code:\n%s\n", c_code.data); + } + } else if (WIFSIGNALED(status)) { + fprintf(stderr, "GCC killed by signal %d\n", WTERMSIG(status)); + } else { + fprintf(stderr, "GCC died in an unknown and mysterious way\n"); + } ast_free(ast); free_str(&input); diff --git a/src/codegen.c b/src/codegen.c index a019af6..00a4e16 100644 --- a/src/codegen.c +++ b/src/codegen.c @@ -1,66 +1,95 @@ #include "all.h" +#include "str.h" static void emit_prelude(str *out) { str_append(out, "void _start(void){" - "uint8_t tape[30000]={0};" - "uint8_t*ptr=tape+15000;"); + "struct termios orig;" + "rawon(0, &orig);" + "u8 t[30000]={0};" + "u8*p=t+15000;"); } static void emit_runtime(str *out) { - str_append(out, "typedef unsigned long size_t;" - "typedef unsigned char uint8_t;"); + str_append(out, "typedef unsigned long sz;" + "typedef unsigned char u8;"); - str_append(out, - "static inline long syscall3(long n, long a1, void *a2, long a3){" - "long ret;" - "__asm__ volatile (" - "\"syscall\"" - ":\"=a\"(ret)" - ":\"a\"(n),\"D\"(a1),\"S\"(a2),\"d\"(a3)" - ":\"rcx\",\"r11\",\"memory\"" - ");" - "return ret;" - "}"); + str_append(out, "typedef unsigned int tcflag_t;" + "typedef unsigned char cc_t;" + "typedef unsigned int speed_t;"); + + str_append(out, "struct termios{tcflag_t c_iflag;tcflag_t c_oflag;tcflag_t " + "c_cflag;tcflag_t c_lflag;cc_t c_line;cc_t c_cc[19];speed_t " + "c_ispeed; speed_t c_ospeed;};"); + + str_append(out, "static inline long sys3(long n, long a1, long a2, long a3){" + "long ret;" + "__asm__ volatile (" + "\"syscall\"" + ":\"=a\"(ret)" + ":\"a\"(n),\"D\"(a1),\"S\"(a2),\"d\"(a3)" + ":\"rcx\",\"r11\",\"memory\"" + ");" + "return ret;" + "}"); + + str_append(out, "static void rawon(int fd,struct termios *orig){" + "sys3(16,fd,0x5401,(long)orig);" + "struct termios t=*orig;" + "t.c_lflag&=~(2|010|0100000);" + "t.c_cc[6]=1;" + "t.c_cc[5]=0;" + "sys3(16,fd,0x5402,(long)&t);" + "}"); + + str_append(out, "static void rawoff(int fd,struct termios *orig){" + "sys3(16,fd,0x5402,(long)orig);" + "}"); } -static void emit_epilogue(str *out) { str_append(out, "syscall3(60,0,0,0);}"); } +static void emit_epilogue(str *out) { + str_append(out, "rawoff(0,&orig);sys3(60,0,0,0);}"); +} -void emit_node(str *out, ast_node_t *node, int indent) { +void emit_node(str *out, ast_node_t *node) { for (; node; node = node->next) { switch (node->type) { + case AST_INC: - str_appendf(out, "*ptr+=%d;", node->val); + str_appendf(out, "*p+=%d;", node->val); break; case AST_DEC: - str_appendf(out, "*ptr-=%d;", node->val); + str_appendf(out, "*p-=%d;", node->val); break; case AST_PTR_INC: - str_appendf(out, "ptr+=%d;", node->val); + str_appendf(out, "p+=%d;", node->val); break; case AST_PTR_DEC: - str_appendf(out, "ptr-=%d;", node->val); + str_appendf(out, "p-=%d;", node->val); break; case AST_OUT: - str_appendf(out, "syscall3(1,1,ptr,1);"); + str_appendf(out, "sys3(1,1,(long)p,1);"); break; case AST_IN: - str_appendf(out, "syscall3(0,0,ptr,1);"); + str_appendf(out, "sys3(0,0,(long)p,1);"); break; case AST_LOOP: - str_append(out, "while(*ptr){"); + str_append(out, "while(*p){"); for (size_t i = 0; i < node->children.len; i++) { - emit_node(out, node->children._data[i], indent + 1); + emit_node(out, node->children._data[i]); } str_append(out, "}"); break; + case AST_CLEAR: + str_append(out, "*p=0;"); + break; } } } @@ -70,7 +99,7 @@ str gen_code(ast_node_t *ast) { emit_runtime(&out); emit_prelude(&out); - emit_node(&out, ast, 1); + emit_node(&out, ast); emit_epilogue(&out); return out; diff --git a/src/optimizer.c b/src/optimizer.c new file mode 100644 index 0000000..18a88c5 --- /dev/null +++ b/src/optimizer.c @@ -0,0 +1,134 @@ +#include "all.h" +#include <stdbool.h> +#include <stddef.h> + +static void mark_changed(bool *ch) { *ch = true; } + +static bool is_arith(ast_type_e t) { return t == AST_INC || t == AST_DEC; } + +static bool is_ptr(ast_type_e t) { + return t == AST_PTR_INC || t == AST_PTR_DEC; +} + +static int node_signed_value(const ast_node_t *n) { + if (n->type == AST_DEC || n->type == AST_PTR_DEC) + return -n->val; + return n->val; +} + +static void set_arith_node(ast_node_t *n, int v) { + if (v > 0) { + n->type = AST_INC; + n->val = v; + } else { + n->type = AST_DEC; + n->val = -v; + } +} + +static void set_ptr_node(ast_node_t *n, int v) { + if (v > 0) { + n->type = AST_PTR_INC; + n->val = v; + } else { + n->type = AST_PTR_DEC; + n->val = -v; + } +} + +static void optimize_list(ast_node_t **head, bool *ch); + +static void optimize_loop_node(ast_node_t *n, bool *ch) { + if (!n || n->type != AST_LOOP) + return; + + if (n->children.len == 0 || n->children._data[0] == NULL) { + n->children.len = 0; + return; + } + + optimize_list(&n->children._data[0], ch); + + if (n->children._data[0] == NULL) { + n->children.len = 0; + return; + } + + if (n->children.len == 1) { + ast_node_t *c = n->children._data[0]; + + if ((c->type == AST_INC || c->type == AST_DEC) && c->val == 1) { + n->type = AST_CLEAR; + n->val = 0; + n->children.len = 0; + n->children._data[0] = NULL; + mark_changed(ch); + } + } +} + +static void optimize_list(ast_node_t **head, bool *ch) { + ast_node_t **p = head; + + while (*p) { + ast_node_t *n = *p; + + if (n->type == AST_LOOP) { + optimize_loop_node(n, ch); + + if (n->type == AST_LOOP && n->children.len == 0) { + *p = n->next; + mark_changed(ch); + continue; + } + } + + if (*p && (*p)->next) { + ast_node_t *a = *p; + ast_node_t *b = a->next; + + if (is_arith(a->type) && is_arith(b->type)) { + int v = node_signed_value(a) + node_signed_value(b); + + if (v == 0) { + a->next = b->next; + mark_changed(ch); + continue; + } + + set_arith_node(a, v); + a->next = b->next; + mark_changed(ch); + continue; + } + + if (is_ptr(a->type) && is_ptr(b->type)) { + int v = node_signed_value(a) + node_signed_value(b); + + if (v == 0) { + a->next = b->next; + mark_changed(ch); + continue; + } + + set_ptr_node(a, v); + a->next = b->next; + mark_changed(ch); + continue; + } + } + + p = &(*p)->next; + } +} + +ast_node_t *optimize_ast(ast_node_t *ast) { + bool ch; + + do { + ch = false; + optimize_list(&ast, &ch); + } while (ch); + + return ast; +} |