From b35b3e1bf70bf764940498247b1db5bb02761160 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Tue, 12 Mar 2019 01:27:54 +0100 Subject: Starting on ssa --- doc/IMPLEMENTATION.md | 2 +- include/ast.h | 3 + include/compiler.h | 1 + include/ssa/ssa.h | 56 +++++++++++++++++ include/std/buffer.h | 2 +- include/std/hash_map.h | 8 +-- src/ast.c | 17 +++++ src/compiler.c | 79 ++++++++++++++++++++++- src/ssa/ssa.c | 165 +++++++++++++++++++++++++++++++++++++++++++++++++ src/std/hash_map.c | 14 ++--- 10 files changed, 333 insertions(+), 14 deletions(-) create mode 100644 include/ssa/ssa.h create mode 100644 src/ssa/ssa.c diff --git a/doc/IMPLEMENTATION.md b/doc/IMPLEMENTATION.md index 5dc6ef5..3956de2 100644 --- a/doc/IMPLEMENTATION.md +++ b/doc/IMPLEMENTATION.md @@ -15,6 +15,6 @@ is optimized before creating the bytecode. # Progress 1. Parsing using multiple threads is done, but the parser is not finished. 2. Resolving ast using multiple threads is done, but the ast resolver is not finished. -3. Not started. +3. Generating ssa using multiple threads is done, but the ssa generator is not finished. 4. Not started. 5. Not started. \ No newline at end of file diff --git a/include/ast.h b/include/ast.h index 3eb7bb6..497488f 100644 --- a/include/ast.h +++ b/include/ast.h @@ -131,6 +131,9 @@ void binop_init(Binop *self); CHECK_RESULT int scope_init(Scope *self, ScopedAllocator *allocator); CHECK_RESULT int scope_add_child(Scope *self, Ast *child); +/* longjump to compiler env on failure */ void scope_resolve(Scope *self, AstCompilerContext *context); +/* longjump to compiler env on failure */ +void scope_generate_ssa(Scope *self, AstCompilerContext *context); #endif diff --git a/include/compiler.h b/include/compiler.h index d7314cc..4e24f11 100644 --- a/include/compiler.h +++ b/include/compiler.h @@ -22,6 +22,7 @@ struct amal_compiler { bool started; amal_mutex mutex; int resolve_ast_index; + int generate_ssa_index; }; CHECK_RESULT int amal_compiler_init(amal_compiler *self); diff --git a/include/ssa/ssa.h b/include/ssa/ssa.h new file mode 100644 index 0000000..e5bd86b --- /dev/null +++ b/include/ssa/ssa.h @@ -0,0 +1,56 @@ +#ifndef AMALGAM_SSA_H +#define AMALGAM_SSA_H + +#include "../std/buffer.h" +#include "../std/hash_map.h" +#include "../std/defs.h" + +typedef enum { + SSA_ASSIGN_INTER, + SSA_ASSIGN_REG, + SSA_ADD, + SSA_SUB, + SSA_MUL, + SSA_DIV, + SSA_FUNC_START, + SSA_FUNC_END, + SSA_PUSH, + SSA_CALL +} SsaInstructionType; + +typedef enum { + SSA_NUMBER_TYPE_INTEGER, + SSA_NUMBER_TYPE_FLOAT +} SsaNumberType; + +typedef struct { + i64 value; + SsaNumberType type; +} SsaNumber; + +typedef u16 SsaRegister; +typedef u16 SsaIntermediateIndex; +typedef u32 SsaFuncIndex; + +typedef struct { + Buffer/*instruction data*/ instructions; + HashMap/**/ intermediates; + SsaIntermediateIndex intermediate_counter; + SsaRegister reg_counter; + SsaFuncIndex func_counter; +} Ssa; + +/* None of these functions are thread-safe */ +SsaNumber create_ssa_number(i64 value, SsaNumberType type); + +CHECK_RESULT int ssa_init(Ssa *self, ScopedAllocator *allocator); +CHECK_RESULT int ssa_get_unique_reg(Ssa *self, SsaRegister *result); +CHECK_RESULT int ssa_ins_assign_inter(Ssa *self, SsaRegister dest, SsaNumber number); +CHECK_RESULT int ssa_ins_assign_reg(Ssa *self, SsaRegister dest, SsaRegister src); +CHECK_RESULT int ssa_ins_binop(Ssa *self, SsaInstructionType binop_type, SsaRegister lhs, SsaRegister rhs, SsaRegister *result); +CHECK_RESULT int ssa_ins_func_start(Ssa *self, u8 num_args, SsaFuncIndex *result); +CHECK_RESULT int ssa_ins_func_end(Ssa *self); +CHECK_RESULT int ssa_ins_push(Ssa *self, SsaRegister reg); +CHECK_RESULT int ssa_ins_call(Ssa *self, SsaFuncIndex func, SsaRegister *result); + +#endif diff --git a/include/std/buffer.h b/include/std/buffer.h index 688f18a..c961b6e 100644 --- a/include/std/buffer.h +++ b/include/std/buffer.h @@ -3,6 +3,7 @@ #include "types.h" #include "misc.h" +#include "defs.h" #define BUFFER_OK 0 #define BUFFER_ALLOC_FAIL -1 @@ -13,7 +14,6 @@ typedef struct { usize capacity; } Buffer; -struct ScopedAllocator; CHECK_RESULT int buffer_init(Buffer *self, struct ScopedAllocator *allocator); /* @data can be NULL */ diff --git a/include/std/hash_map.h b/include/std/hash_map.h index c36ecc4..97b0745 100644 --- a/include/std/hash_map.h +++ b/include/std/hash_map.h @@ -15,21 +15,21 @@ typedef usize(*HashMapHash)(const u8 *data, usize size); struct HashMap { ScopedAllocator *allocator; /* borrowed */ Buffer/*HashMapBucket*/ buckets; - usize type_size; + usize value_type_size; usize num_elements; HashMapCompare compare_func; HashMapHash hash_func; }; -CHECK_RESULT int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size, HashMapCompare compare_func, HashMapHash hash_func); +CHECK_RESULT int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize value_type_size, HashMapCompare compare_func, HashMapHash hash_func); /* Not thread-safe. -Expected @value size to be @self->type_size. +Expected @value size to be @self->value_type_size. */ CHECK_RESULT int hash_map_insert(HashMap *self, BufferView key, void *value); /* Thread-safe unless @hash_map_insert is used in another thread at the same time. -Expected @value size to be @self->type_size. +Expected @value size to be @self->value_type_size. */ CHECK_RESULT bool hash_map_get(HashMap *self, BufferView key, void *value); diff --git a/src/ast.c b/src/ast.c index 079d45a..b0852b5 100644 --- a/src/ast.c +++ b/src/ast.c @@ -14,6 +14,7 @@ do { \ } while(0) static void ast_resolve(Ast *self, AstCompilerContext *context); +static void ast_generate_ssa(Ast *self, AstCompilerContext *context); Ast ast_none() { Ast ast; @@ -225,3 +226,19 @@ void ast_resolve(Ast *self, AstCompilerContext *context) { } /*self->resolve_status = AST_RESOLVED;*/ } + +void scope_generate_ssa(Scope *self, AstCompilerContext *context) { + Ast *ast; + Ast *ast_end; + ast = buffer_start(&self->ast_objects); + ast_end = buffer_end(&self->ast_objects); + for(; ast != ast_end; ++ast) { + ast_generate_ssa(ast, context); + } +} + +void ast_generate_ssa(Ast *self, AstCompilerContext *context) { + /* TODO: Implement */ + (void)self; + (void)context; +} \ No newline at end of file diff --git a/src/compiler.c b/src/compiler.c index 6988b20..f464005 100644 --- a/src/compiler.c +++ b/src/compiler.c @@ -39,6 +39,7 @@ int amal_compiler_init(amal_compiler *self) { am_memset(&self->main_thread_allocator, 0, sizeof(self->main_thread_allocator)); self->started = bool_false; self->resolve_ast_index = 0; + self->generate_ssa_index = 0; amal_mutex_init(&self->mutex); return_if_error(scoped_allocator_init(&self->allocator)); @@ -88,9 +89,16 @@ typedef struct { Parser *parser; } CompilerAstResolverThreadUserData; +typedef struct { + amal_compiler *compiler; + ParserThreadData *parser_thread_data; + Parser *parser; +} CompilerSsaGeneratorThreadUserData; + typedef enum { THREAD_WORK_PARSE, - THREAD_WORK_RESOLVE_AST + THREAD_WORK_RESOLVE_AST, + THREAD_WORK_GENERATE_SSA } ThreadWorkType; typedef struct { @@ -186,6 +194,44 @@ static void* thread_callback_resolve_ast(void *userdata) { return result; } +/* TODO: Handle errors (stop generating ssa in all other threads and report errors/warnings) */ +static void* thread_callback_generate_ssa(void *userdata) { + CompilerSsaGeneratorThreadUserData compiler_ssa_generator_userdata; + Parser *parser; + AstCompilerContext compiler_context; + void *result; + assert(!amal_thread_is_main()); + + am_memcpy(&compiler_ssa_generator_userdata, userdata, sizeof(compiler_ssa_generator_userdata)); + am_free(userdata); + parser = compiler_ssa_generator_userdata.parser; + compiler_context.parser = parser; + result = (void*)AMAL_COMPILER_ERR; + for(;;) { + int result; + amal_log_debug("Generating SSA for file: %.*s", parser->tokenizer.code_name.size, parser->tokenizer.code_name.data); + result = setjmp(compiler_context.env); + if(result == 0) + scope_generate_ssa(&parser->scope, &compiler_context); + else { + /* TODO: stop generating ssa in all other threads */ + break; + } + cleanup_if_error(amal_mutex_lock(&compiler_ssa_generator_userdata.compiler->mutex, "thread_callback_generate_ssa")); + if(compiler_ssa_generator_userdata.compiler->generate_ssa_index + 1 >= (int)buffer_get_size(&compiler_ssa_generator_userdata.compiler->parsers, Parser)) + break; + ++compiler_ssa_generator_userdata.compiler->generate_ssa_index; + parser = buffer_get(&compiler_ssa_generator_userdata.compiler->parsers, compiler_ssa_generator_userdata.compiler->generate_ssa_index, sizeof(Parser)); + amal_mutex_tryunlock(&compiler_ssa_generator_userdata.compiler->mutex); + } + result = NULL; + + cleanup: + compiler_ssa_generator_userdata.parser_thread_data->status = PARSER_THREAD_STATUS_IDLE; + amal_mutex_tryunlock(&compiler_ssa_generator_userdata.compiler->mutex); + return result; +} + static CHECK_RESULT int amal_compiler_select_thread_for_work(amal_compiler *self, ThreadWorkData work_data, ParserThreadData **thread_selected) { int i; int result; @@ -223,6 +269,17 @@ static CHECK_RESULT int amal_compiler_select_thread_for_work(amal_compiler *self result = parser_thread_data_start(parser_thread_data, thread_callback_resolve_ast, userdata); break; } + case THREAD_WORK_GENERATE_SSA: { + CompilerSsaGeneratorThreadUserData *userdata; + cleanup_if_error(am_malloc(sizeof(CompilerSsaGeneratorThreadUserData), (void**)&userdata)); + thread_user_data = userdata; + userdata->compiler = self; + userdata->parser_thread_data = parser_thread_data; + userdata->parser = work_data.value.parser; + ++self->generate_ssa_index; + result = parser_thread_data_start(parser_thread_data, thread_callback_generate_ssa, userdata); + break; + } } *thread_selected = parser_thread_data; break; @@ -319,6 +376,24 @@ static CHECK_RESULT int amal_compiler_resolve_ast(amal_compiler *self) { return amal_compiler_load_file_join_threads(self); } +static CHECK_RESULT int amal_compiler_generate_ssa(amal_compiler *self) { + Parser *parser; + Parser *parser_end; + parser = buffer_start(&self->parsers); + parser_end = buffer_end(&self->parsers); + for(; parser != parser_end; ++parser) { + ParserThreadData *thread_selected; + ThreadWorkData thread_work_data; + thread_work_data.type = THREAD_WORK_GENERATE_SSA; + thread_work_data.value.parser = parser; + return_if_error(amal_compiler_select_thread_for_work(self, thread_work_data, &thread_selected)); + /* After all threads have been used, they will handle using the remaining parsers or stop if there is an error */ + if(!thread_selected) + break; + } + return amal_compiler_load_file_join_threads(self); +} + int amal_compiler_load_file(amal_compiler *self, BufferView filepath) { int result; ParserThreadData *parser_thread_data; @@ -340,6 +415,8 @@ int amal_compiler_load_file(amal_compiler *self, BufferView filepath) { return_if_error(amal_compiler_load_file_join_threads(self)); amal_log_debug("Finished parsing all files, resolving AST"); return_if_error(amal_compiler_resolve_ast(self)); + amal_log_debug("Finished resolving AST, generating SSA"); + return_if_error(amal_compiler_generate_ssa(self)); return AMAL_COMPILER_OK; } diff --git a/src/ssa/ssa.c b/src/ssa/ssa.c new file mode 100644 index 0000000..3433e8d --- /dev/null +++ b/src/ssa/ssa.c @@ -0,0 +1,165 @@ +#include "../../include/ssa/ssa.h" +#include "../../include/std/mem.h" +#include "../../include/std/log.h" +#include + +static int compare_number(const void *a, const void *b) { + const SsaNumber *lhs; + const SsaNumber *rhs; + lhs = a; + rhs = b; + if(rhs->type == lhs->type && rhs->value == lhs->value) + return 0; + return 1; +} + +static usize hash_number(const u8 *data, usize size) { + SsaNumber number; + assert(size == sizeof(SsaNumber)); + am_memcpy(&number, data, size); + return number.value; +} + +SsaNumber create_ssa_number(i64 value, SsaNumberType type) { + SsaNumber result; + result.value = value; + result.type = type; + return result; +} + +int ssa_init(Ssa *self, ScopedAllocator *allocator) { + return_if_error(buffer_init(&self->instructions, allocator)); + return_if_error(hash_map_init(&self->intermediates, allocator, sizeof(SsaIntermediateIndex), compare_number, hash_number)); + self->intermediate_counter = 0; + self->reg_counter = 0; + self->func_counter = 0; + return 0; +} + +int ssa_get_unique_reg(Ssa *self, SsaRegister *result) { + /* Overflow */ + if(self->reg_counter + 1 < self->reg_counter) + return -1; + *result = self->reg_counter++; + return 0; +} + +static CHECK_RESULT int ssa_try_add_intermediate(Ssa *self, i64 intermediate, SsaNumberType number_type, SsaIntermediateIndex *result_index) { + SsaNumber number; + bool exists; + BufferView key; + + assert(result_index); + number = create_ssa_number(intermediate, number_type); + key = create_buffer_view((const char*)&number, sizeof(number)); + + exists = hash_map_get(&self->intermediates, key, result_index); + if(exists) + return 0; + + /* Overflow */ + if(self->intermediate_counter + 1 < self->intermediate_counter) + return -1; + + *result_index = self->intermediate_counter; + ++self->intermediate_counter; + return hash_map_insert(&self->intermediates, key, result_index); +} + +static CHECK_RESULT int ssa_add_ins_form1(Ssa *self, SsaInstructionType ins_type, SsaRegister lhs, u16 rhs) { + usize index; + index = self->instructions.size; + + return_if_error(buffer_append(&self->instructions, NULL, sizeof(u8) + sizeof(SsaRegister) + sizeof(u16))); + self->instructions.data[index + 0] = ins_type; + *(SsaRegister*)&self->instructions.data[index + 1] = lhs; + *(u16*)&self->instructions.data[index + 3] = rhs; + return 0; +} + +static CHECK_RESULT int ssa_add_ins_form2(Ssa *self, SsaInstructionType ins_type, SsaRegister lhs, SsaRegister rhs, SsaRegister *result) { + usize index; + index = self->instructions.size; + + /* Overflow */ + if(self->reg_counter + 1 < self->reg_counter) + return -1; + + assert(result); + return_if_error(buffer_append(&self->instructions, NULL, sizeof(u8) + sizeof(SsaRegister) + sizeof(SsaRegister) + sizeof(SsaRegister))); + *result = self->reg_counter++; + self->instructions.data[index + 0] = ins_type; + *(SsaRegister*)&self->instructions.data[index + 1] = *result; + *(SsaRegister*)&self->instructions.data[index + 3] = lhs; + *(SsaRegister*)&self->instructions.data[index + 5] = rhs; + amal_log_debug("r%u = r%u + r%u", *result, lhs, rhs); + return 0; +} + +int ssa_ins_assign_inter(Ssa *self, SsaRegister dest, SsaNumber number) { + SsaIntermediateIndex index; + return_if_error(ssa_try_add_intermediate(self, number.value, number.type, &index)); + amal_log_debug("r%u = i%u", dest, index); + return ssa_add_ins_form1(self, SSA_ASSIGN_INTER, dest, index); +} + +int ssa_ins_assign_reg(Ssa *self, SsaRegister dest, SsaRegister src) { + amal_log_debug("r%u = r%u", dest, src); + return ssa_add_ins_form1(self, SSA_ASSIGN_INTER, dest, src); +} + +int ssa_ins_binop(Ssa *self, SsaInstructionType binop_type, SsaRegister lhs, SsaRegister rhs, SsaRegister *result) { + assert(binop_type >= SSA_ADD && binop_type <= SSA_DIV); + return ssa_add_ins_form2(self, binop_type, lhs, rhs, result); +} + +int ssa_ins_func_start(Ssa *self, u8 num_args, SsaFuncIndex *result) { + usize index; + index = self->instructions.size; + + /* Overflow */ + if(self->func_counter + 1 < self->func_counter) + return -1; + + return_if_error(buffer_append(&self->instructions, NULL, sizeof(u8) + sizeof(SsaFuncIndex) + sizeof(u8))); + *result = self->func_counter++; + self->instructions.data[index + 0] = SSA_FUNC_START; + *(SsaFuncIndex*)&self->instructions.data[index + 1] = *result; + self->instructions.data[index + 3] = num_args; + amal_log_debug("FUNC_START f%u(%u)", *result, num_args); + return 0; +} + +int ssa_ins_func_end(Ssa *self) { + SsaInstructionType ins; + ins = SSA_FUNC_END; + return buffer_append(&self->instructions, &ins, 1); +} + +int ssa_ins_push(Ssa *self, SsaRegister reg) { + usize index; + index = self->instructions.size; + + return_if_error(buffer_append(&self->instructions, NULL, sizeof(u8) + sizeof(SsaRegister))); + self->instructions.data[index + 0] = SSA_PUSH; + *(SsaRegister*)&self->instructions.data[index + 1] = reg; + amal_log_debug("PUSH r%u", reg); + return 0; +} + +int ssa_ins_call(Ssa *self, SsaFuncIndex func, SsaRegister *result) { + usize index; + index = self->instructions.size; + + /* Overflow */ + if(self->reg_counter + 1 < self->reg_counter) + return -1; + + return_if_error(buffer_append(&self->instructions, NULL, sizeof(u8) + sizeof(SsaFuncIndex) + sizeof(SsaRegister))); + *result = self->reg_counter++; + self->instructions.data[index + 0] = SSA_CALL; + *(SsaFuncIndex*)&self->instructions.data[index + 1] = func; + *(SsaRegister*)&self->instructions.data[index + 3] = *result; + amal_log_debug("r%u = CALL f%u", *result, func); + return 0; +} diff --git a/src/std/hash_map.c b/src/std/hash_map.c index a649a95..402c56d 100644 --- a/src/std/hash_map.c +++ b/src/std/hash_map.c @@ -42,10 +42,10 @@ static BufferView bucket_node_get_key(HashMapBucketNode *self) { return key; } -static void bucket_node_set_value(HashMapBucketNode *self, void *value, usize type_size) { +static void bucket_node_set_value(HashMapBucketNode *self, void *value, usize value_type_size) { u32 key_size; am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(key_size)); - am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(u32) + key_size, value, type_size); + am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(u32) + key_size, value, value_type_size); } static void* bucket_node_get_value(HashMapBucketNode *self) { @@ -56,12 +56,12 @@ static void* bucket_node_get_value(HashMapBucketNode *self) { return value; } -int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size, +int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize value_type_size, HashMapCompare compare_func, HashMapHash hash_func) { assert(compare_func); assert(hash_func); self->allocator = allocator; - self->type_size = type_size; + self->value_type_size = value_type_size; self->num_elements = 0; self->compare_func = compare_func; self->hash_func = hash_func; @@ -75,11 +75,11 @@ int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size, static CHECK_RESULT int hash_map_bucket_add(HashMap *self, HashMapBucket *bucket, BufferView key, void *value) { HashMapBucketNode *new_bucket_node; return_if_error(scoped_allocator_alloc(self->allocator, - sizeof(HashMapBucketNode*) + sizeof(u32) + key.size + self->type_size, + sizeof(HashMapBucketNode*) + sizeof(u32) + key.size + self->value_type_size, (void**)&new_bucket_node)); bucket_node_set_next(new_bucket_node, bucket->start); bucket_node_set_key(new_bucket_node, key); - bucket_node_set_value(new_bucket_node, value, self->type_size); + bucket_node_set_value(new_bucket_node, value, self->value_type_size); bucket->start = new_bucket_node; return 0; } @@ -176,7 +176,7 @@ bool hash_map_get(HashMap *self, BufferView key, void *value) { BufferView bucket_key; bucket_key = bucket_node_get_key(bucket_node); if(self->compare_func(&key, &bucket_key) == 0) { - am_memcpy(value, bucket_node_get_value(bucket_node), self->type_size); + am_memcpy(value, bucket_node_get_value(bucket_node), self->value_type_size); return bool_true; } } -- cgit v1.2.3