Starting on ssa

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;
         }
     }