aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/IMPLEMENTATION.md2
-rw-r--r--include/ast.h3
-rw-r--r--include/compiler.h1
-rw-r--r--include/ssa/ssa.h56
-rw-r--r--include/std/buffer.h2
-rw-r--r--include/std/hash_map.h8
-rw-r--r--src/ast.c17
-rw-r--r--src/compiler.c79
-rw-r--r--src/ssa/ssa.c165
-rw-r--r--src/std/hash_map.c14
10 files changed, 333 insertions, 14 deletions
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/*<SsaNumberType, IntermediateIndex>*/ 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 <assert.h>
+
+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;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 23:16:48 +0000