#include "../../include/ssa/ssa.h" #include "../../include/std/mem.h" #include "../../include/std/log.h" #include "../../include/std/hash.h" #include "../../include/std/thread.h" #include "../../include/ast.h" #include "../../include/compiler.h" #include #define throw(result) do { longjmp(context->env, (result)); } while(0) #define throw_if_error(result) \ do { \ int return_if_result; \ return_if_result = (result); \ if((return_if_result) != 0) \ throw(return_if_result); \ } while(0) /* Max length of a string that fits in u16 */ #define MAX_STRING_LENGTH UINT16_MAX 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.integer == lhs->value.integer) 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.integer; } SsaNumber create_ssa_integer(i64 value) { SsaNumber result; result.value.integer = value; result.type = SSA_NUMBER_TYPE_INTEGER; return result; } SsaNumber create_ssa_float(f64 value) { SsaNumber result; result.value.floating = value; result.type = SSA_NUMBER_TYPE_FLOAT; 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_map, allocator, sizeof(SsaIntermediateIndex), compare_number, hash_number)); return_if_error(buffer_init(&self->intermediates, allocator)); return_if_error(hash_map_init(&self->strings_map, allocator, sizeof(SsaStringIndex), hash_map_compare_string, amal_hash_string)); return_if_error(buffer_init(&self->strings, allocator)); self->intermediate_counter = 0; self->string_counter = 0; self->reg_counter = 0; self->func_counter = 0; return 0; } static CHECK_RESULT 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; } SsaNumber ssa_get_intermediate(Ssa *self, SsaIntermediateIndex index) { SsaNumber result; assert(index < buffer_get_size(&self->intermediates, SsaNumber)); am_memcpy(&result, buffer_get(&self->intermediates, index, sizeof(SsaNumber)), sizeof(SsaNumber)); return result; } BufferView ssa_get_string(Ssa *self, SsaStringIndex index) { BufferView result; assert(index < buffer_get_size(&self->strings, BufferView)); am_memcpy(&result, buffer_get(&self->strings, index, sizeof(BufferView)), sizeof(BufferView)); return result; } static CHECK_RESULT int ssa_try_add_intermediate(Ssa *self, SsaNumber number, SsaIntermediateIndex *result_index) { bool exists; BufferView key; assert(result_index); key = create_buffer_view((const char*)&number, sizeof(number)); exists = hash_map_get(&self->intermediates_map, 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; switch(number.type) { case SSA_NUMBER_TYPE_INTEGER: { amal_log_debug("i%u = %lld", *result_index, number.value.integer); break; } case SSA_NUMBER_TYPE_FLOAT: { amal_log_debug("i%u = %f", *result_index, number.value.floating); break; } } return_if_error(buffer_append(&self->intermediates, &number, sizeof(number))); return hash_map_insert(&self->intermediates_map, key, result_index); } static CHECK_RESULT int ssa_try_add_string(Ssa *self, BufferView str, SsaStringIndex *result_index) { bool exists; assert(result_index); exists = hash_map_get(&self->strings_map, str, result_index); if(exists) return 0; /* Overflow */ if(self->string_counter + 1 < self->string_counter) return -1; if(str.size > MAX_STRING_LENGTH) { amal_log_error("String \"%.*s\" is longer than %d\n", str.size, str.data, MAX_STRING_LENGTH); return -2; } *result_index = self->string_counter; ++self->string_counter; amal_log_debug("s%u = \"%.*s\"", *result_index, str.size, str.data); return_if_error(buffer_append(&self->strings, &str, sizeof(str))); return hash_map_insert(&self->strings_map, str, result_index); } static CHECK_RESULT int ssa_add_ins_form1(Ssa *self, SsaInstruction ins_type, SsaRegister lhs, u16 rhs) { usize index; index = self->instructions.size; return_if_error(buffer_append_empty(&self->instructions, sizeof(u8) + sizeof(SsaRegister) + sizeof(u16))); self->instructions.data[index + 0] = ins_type; am_memcpy(self->instructions.data + index + 1, &lhs, sizeof(lhs)); am_memcpy(self->instructions.data + index + 3, &rhs, sizeof(rhs)); return 0; } static const char* binop_type_to_string(SsaInstruction binop_type) { assert(binop_type >= SSA_ADD && binop_type <= SSA_EQUALS); switch(binop_type) { case SSA_ADD: return "+"; case SSA_SUB: return "-"; case SSA_MUL: return "*"; case SSA_DIV: return "/"; case SSA_EQUALS: return "=="; default: return ""; } } static CHECK_RESULT int ssa_add_ins_form2(Ssa *self, SsaInstruction 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_empty(&self->instructions, sizeof(u8) + sizeof(SsaRegister) + sizeof(SsaRegister) + sizeof(SsaRegister))); *result = self->reg_counter++; self->instructions.data[index + 0] = ins_type; am_memcpy(self->instructions.data + index + 1, result, sizeof(SsaRegister)); am_memcpy(self->instructions.data + index + 3, &lhs, sizeof(lhs)); am_memcpy(self->instructions.data + index + 5, &rhs, sizeof(rhs)); amal_log_debug("r%u = r%u %s r%u", *result, lhs, binop_type_to_string(ins_type), rhs); return 0; } static CHECK_RESULT int ssa_ins_assign_inter(Ssa *self, SsaRegister dest, SsaNumber number) { SsaIntermediateIndex index; return_if_error(ssa_try_add_intermediate(self, number, &index)); amal_log_debug("r%u = i%u", dest, index); return ssa_add_ins_form1(self, SSA_ASSIGN_INTER, dest, index); } static CHECK_RESULT int ssa_ins_assign_string(Ssa *self, SsaRegister dest, BufferView str) { SsaStringIndex index; return_if_error(ssa_try_add_string(self, str, &index)); amal_log_debug("r%u = s%u", dest, index); return ssa_add_ins_form1(self, SSA_ASSIGN_STRING, dest, index); } static CHECK_RESULT 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_REG, dest, src); } static CHECK_RESULT int ssa_ins_binop(Ssa *self, SsaInstruction binop_type, SsaRegister lhs, SsaRegister rhs, SsaRegister *result) { assert(binop_type >= SSA_ADD && binop_type <= SSA_EQUALS); return ssa_add_ins_form2(self, binop_type, lhs, rhs, result); } static CHECK_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_empty(&self->instructions, sizeof(u8) + sizeof(SsaFuncIndex) + sizeof(u8))); *result = self->func_counter++; self->instructions.data[index + 0] = SSA_FUNC_START; am_memcpy(self->instructions.data + index + 1, result, sizeof(SsaFuncIndex)); self->instructions.data[index + 1 + sizeof(SsaFuncIndex)] = num_args; amal_log_debug("FUNC_START f%u(%u)", *result, num_args); return 0; } static CHECK_RESULT int ssa_ins_func_end(Ssa *self) { u8 ins; ins = SSA_FUNC_END; amal_log_debug("FUNC_END"); return buffer_append(&self->instructions, &ins, 1); } static CHECK_RESULT int ssa_ins_push(Ssa *self, SsaRegister reg) { usize index; index = self->instructions.size; return_if_error(buffer_append_empty(&self->instructions, sizeof(u8) + sizeof(SsaRegister))); self->instructions.data[index + 0] = SSA_PUSH; am_memcpy(self->instructions.data + index + 1, ®, sizeof(SsaRegister)); amal_log_debug("PUSH r%u", reg); return 0; } static CHECK_RESULT int ssa_ins_call(Ssa *self, FunctionDecl *func_decl, SsaRegister *result) { usize index; index = self->instructions.size; /* Overflow */ if(self->reg_counter + 1 < self->reg_counter) return -1; return_if_error(buffer_append_empty(&self->instructions, sizeof(u8) + sizeof(SsaRegister) + sizeof(func_decl))); *result = self->reg_counter++; self->instructions.data[index + 0] = SSA_CALL; am_memcpy(self->instructions.data + index + 1, result, sizeof(SsaRegister)); am_memcpy(self->instructions.data + index + 1 + sizeof(SsaRegister), &func_decl, sizeof(func_decl)); amal_log_debug("r%u = CALL %p", *result, func_decl); return 0; } static CHECK_RESULT int ssa_ins_jumpzero(Ssa *self, SsaRegister condition_reg, JumpOffset jump_offset) { usize index; index = self->instructions.size; return_if_error(buffer_append_empty(&self->instructions, sizeof(u8) + sizeof(SsaRegister) + sizeof(JumpOffset))); self->instructions.data[index + 0] = SSA_JUMP_ZERO; am_memcpy(self->instructions.data + index + 1, &condition_reg, sizeof(SsaRegister)); am_memcpy(self->instructions.data + index + 1 + sizeof(SsaRegister), &jump_offset, sizeof(JumpOffset)); if(jump_offset == 0) amal_log_debug("JUMP_ZERO r%u, DUMMY", condition_reg); else amal_log_debug("JUMP_ZERO r%u, %d", condition_reg, jump_offset); return 0; } static CHECK_RESULT int ssa_ins_jump(Ssa *self, JumpOffset jump_offset) { usize index; index = self->instructions.size; return_if_error(buffer_append_empty(&self->instructions, sizeof(u8) + sizeof(JumpOffset))); self->instructions.data[index + 0] = SSA_JUMP; am_memcpy(self->instructions.data + index + 1, &jump_offset, sizeof(JumpOffset)); amal_log_debug("JUMP %d", jump_offset); return 0; } static usize ssa_ins_get_index(Ssa *self) { return self->instructions.size; } /* Set target of jump instruction to current location */ static CHECK_RESULT int ssa_ins_jump_set_target(Ssa *self, usize jump_ins_index) { switch(self->instructions.data[jump_ins_index]) { case SSA_JUMP_ZERO: { isize jump_offset = (isize)ssa_ins_get_index(self) - (isize)jump_ins_index; /* TODO: Should something be done about this? */ if(jump_offset < -0x7FFF || jump_offset > 0x7FFF) { amal_log_error("Unexpected error. Jump offset has to be less than +-32767, was %d", jump_offset); return 1; } am_memcpy(self->instructions.data + jump_ins_index + 1 + sizeof(SsaRegister), &jump_offset, sizeof(JumpOffset)); break; } default: assert(bool_false && "Unexpected error... jump_ins_index doesn't point to a valid index to a jump instruction"); break; } return 0; } static CHECK_RESULT SsaRegister ast_generate_ssa(Ast *self, SsaCompilerContext *context); static CHECK_RESULT SsaRegister number_generate_ssa(Number *self, SsaCompilerContext *context) { SsaRegister reg; SsaNumber number; if(self->is_integer) number = create_ssa_integer(self->value.integer); else number = create_ssa_float(self->value.floating); throw_if_error(ssa_get_unique_reg(context->ssa, ®)); throw_if_error(ssa_ins_assign_inter(context->ssa, reg, number)); return reg; } static CHECK_RESULT SsaRegister lhsexpr_extern_generate_ssa(LhsExpr *self, SsaCompilerContext *context) { /* TODO: SsaRegister should be extended to include static and extern data */ (void)self; (void)context; amal_log_error("TODO: Implement lhsexpr_extern_generate_ssa"); return 0; } static CHECK_RESULT SsaRegister lhsexpr_generate_ssa(Ast *self, SsaCompilerContext *context) { LhsExpr *lhs_expr; SsaRegister reg; assert(self->type == AST_LHS); lhs_expr = self->value.lhs_expr; if(lhs_expr->is_extern) return lhsexpr_extern_generate_ssa(lhs_expr, context); if(lhs_expr->rhs_expr) { SsaRegister rhs_reg; rhs_reg = ast_generate_ssa(lhs_expr->rhs_expr, context); /* Declarations (struct and function declaration) resolves to itself and in that case this expression is just a compile-time name for the declaration. Import expression also has no meaning in SSA until it's used. TODO: Shouldn't lhsexpr that have struct/function declaration as rhs be different ast expression types? */ if(self->resolve_data.type == lhs_expr || lhs_expr->rhs_expr->type == AST_IMPORT) { /*assert(bool_false);*/ return 0; } throw_if_error(ssa_get_unique_reg(context->ssa, ®)); if(reg == rhs_reg) { amal_log_error("rhs_expr is same as reg.. rhs type: %d", lhs_expr->rhs_expr->type); } assert(reg != rhs_reg); throw_if_error(ssa_ins_assign_reg(context->ssa, reg, rhs_reg)); } else { /* TODO: Do not assign if we dont want default value */ SsaNumber number; if(self->resolve_data.type == context->compiler->default_types.i64) number = create_ssa_integer(0); else if(self->resolve_data.type == context->compiler->default_types.f64) number = create_ssa_float(0.0); else assert(bool_false && "TODO: assign default value to reg depending on LhsExpr type"); throw_if_error(ssa_get_unique_reg(context->ssa, ®)); throw_if_error(ssa_ins_assign_inter(context->ssa, reg, number)); } return reg; } static CHECK_RESULT SsaRegister assignmentexpr_generate_ssa(Ast *ast, SsaCompilerContext *context) { AssignmentExpr *self; SsaRegister lhs_reg, rhs_reg; assert(ast->type == AST_ASSIGN); self = ast->value.assign_expr; lhs_reg = ast_generate_ssa(self->lhs_expr, context); rhs_reg = ast_generate_ssa(self->rhs_expr, context); throw_if_error(ssa_ins_assign_reg(context->ssa, lhs_reg, rhs_reg)); return lhs_reg; } /* TODO: Each function declaration should be in separate SSA instances so ast can be converted into ssa in any order. */ static CHECK_RESULT SsaRegister funcdecl_generate_ssa(FunctionDecl *self, SsaCompilerContext *context) { /* TODO: Implement */ /* Reset reg counter in each function, because each function has a separate register context that is reset after function end */ SsaRegister prev_reg_counter; prev_reg_counter = context->ssa->reg_counter; context->ssa->reg_counter = 0; amal_log_debug("SSA funcdecl %p", self); throw_if_error(ssa_ins_func_start(context->ssa, 0, &self->ssa_func_index)); scope_generate_ssa(&self->body, context); throw_if_error(ssa_ins_func_end(context->ssa)); context->ssa->reg_counter = prev_reg_counter; /*assert(bool_false);*/ return 0; } static CHECK_RESULT SsaRegister funccall_generate_ssa(Ast *self, SsaCompilerContext *context) { /* TODO: Implement */ FunctionCall *func_call; FunctionDecl *func_to_call; Ast **ast; Ast **ast_end; SsaRegister reg; assert(self->type == AST_FUNCTION_CALL); func_call = self->value.func_call; ast = buffer_begin(&func_call->args); ast_end = buffer_end(&func_call->args); for(; ast != ast_end; ++ast) { SsaRegister arg_reg; arg_reg = ast_generate_ssa(*ast, context); throw_if_error(ssa_ins_push(context->ssa, arg_reg)); } assert(self->resolve_data.type->rhs_expr->type == AST_FUNCTION_DECL); func_to_call = self->resolve_data.type->rhs_expr->value.func_decl; /* TODO: Implement func reference instead of using 0. Perhaps the best way is to use function declaration pointer value? then there is no need for mutex locks. */ amal_log_debug("SSA funccall %.*s, func index ptr: %p", func_call->func.name.size, func_call->func.name.data, func_to_call); throw_if_error(ssa_ins_call(context->ssa, func_to_call, ®)); return reg; } static CHECK_RESULT SsaRegister structdecl_generate_ssa(StructDecl *self, SsaCompilerContext *context) { /* TODO: Implement */ /*assert(bool_false);*/ scope_generate_ssa(&self->body, context); return 0; } static CHECK_RESULT SsaRegister structfield_generate_ssa(StructField *self, SsaCompilerContext *context) { /* TODO: Implement */ /*assert(bool_false);*/ (void)self; (void)context; return 0; } static CHECK_RESULT SsaRegister string_generate_ssa(String *self, SsaCompilerContext *context) { SsaRegister reg; throw_if_error(ssa_get_unique_reg(context->ssa, ®)); throw_if_error(ssa_ins_assign_string(context->ssa, reg, self->str)); return reg; } static CHECK_RESULT SsaRegister variable_generate_ssa(Variable *self, SsaCompilerContext *context) { /* TODO: If resolved_var refers to a variable in another file, use a cross file reference that requires no locking (not yet implemented) */ /* This is not thread-safe:*/ assert(self->resolved_var); return ast_generate_ssa(self->resolved_var, context); } static SsaInstruction binop_type_to_ssa_type(BinopType binop_type) { switch(binop_type) { case BINOP_ADD: return SSA_ADD; case BINOP_SUB: return SSA_SUB; case BINOP_MUL: return SSA_MUL; case BINOP_DIV: return SSA_DIV; case BINOP_DOT: assert(bool_false && "Binop dot not valid for arithmetic operation and requires special functionality"); return 0; case BINOP_EQUALS: return SSA_EQUALS; } return 0; } static CHECK_RESULT SsaRegister binop_generate_ssa(Binop *self, SsaCompilerContext *context) { SsaRegister lhs_reg; SsaRegister rhs_reg; SsaRegister reg; if(self->type == BINOP_DOT && self->rhs->resolve_data.type->rhs_expr->type == AST_FUNCTION_DECL) { reg = ast_generate_ssa(self->rhs, context); } else { lhs_reg = ast_generate_ssa(self->lhs, context); rhs_reg = ast_generate_ssa(self->rhs, context); throw_if_error(ssa_ins_binop(context->ssa, binop_type_to_ssa_type(self->type), lhs_reg, rhs_reg, ®)); } return reg; } static void else_if_statement_generate_ssa(ElseIfStatement *else_if_stmt, SsaCompilerContext *context) { usize jump_ins_index; if(else_if_stmt->condition) { SsaRegister condition_reg; condition_reg = ast_generate_ssa(else_if_stmt->condition, context); jump_ins_index = ssa_ins_get_index(context->ssa); throw_if_error(ssa_ins_jumpzero(context->ssa, condition_reg, 0)); } scope_generate_ssa(&else_if_stmt->body, context); if(else_if_stmt->condition) throw_if_error(ssa_ins_jump_set_target(context->ssa, jump_ins_index)); if(else_if_stmt->next_else_if_stmt) else_if_statement_generate_ssa(else_if_stmt->next_else_if_stmt, context); } static void if_statement_generate_ssa(IfStatement *if_stmt, SsaCompilerContext *context) { SsaRegister condition_reg; usize jump_ins_index; condition_reg = ast_generate_ssa(if_stmt->condition, context); jump_ins_index = ssa_ins_get_index(context->ssa); throw_if_error(ssa_ins_jumpzero(context->ssa, condition_reg, 0)); scope_generate_ssa(&if_stmt->body, context); throw_if_error(ssa_ins_jump_set_target(context->ssa, jump_ins_index)); if(if_stmt->else_if_stmt) else_if_statement_generate_ssa(if_stmt->else_if_stmt, context); } static void while_statement_generate_ssa(WhileStatement *while_stmt, SsaCompilerContext *context) { SsaRegister condition_reg; usize jump_back_ins_index; usize jump_condition_ins_index; isize jump_offset; jump_back_ins_index = ssa_ins_get_index(context->ssa); condition_reg = ast_generate_ssa(while_stmt->condition, context); jump_condition_ins_index = ssa_ins_get_index(context->ssa); throw_if_error(ssa_ins_jumpzero(context->ssa, condition_reg, 0)); scope_generate_ssa(&while_stmt->body, context); /* Jump back and check condition again before running the content of the loop again */ jump_offset = (isize)jump_back_ins_index - (isize)ssa_ins_get_index(context->ssa); /* TODO: Should something be done about this? */ if(jump_offset < -0x7FFF || jump_offset > 0x7FFF) { amal_log_error("Unexpected error. Jump offset has to be less than +-32767, was %d", jump_offset); throw(1); } throw_if_error(ssa_ins_jump(context->ssa, (JumpOffset)jump_offset)); throw_if_error(ssa_ins_jump_set_target(context->ssa, jump_condition_ins_index)); } static CHECK_RESULT SsaRegister ast_generate_ssa(Ast *self, SsaCompilerContext *context) { assert(self); #ifdef DEBUG if(self->resolve_data.status != AST_RESOLVED && self->resolve_data.status != AST_SSA_RESOLVED) { amal_log_error("Ast type not resolved: %d", self->type); assert(bool_false); } #endif if(self->resolve_data.status == AST_SSA_RESOLVED) return self->ssa_reg; switch(self->type) { case AST_NUMBER: self->ssa_reg = number_generate_ssa(self->value.number, context); break; case AST_FUNCTION_DECL: self->ssa_reg = funcdecl_generate_ssa(self->value.func_decl, context); break; case AST_FUNCTION_CALL: self->ssa_reg = funccall_generate_ssa(self, context); break; case AST_STRUCT_DECL: self->ssa_reg = structdecl_generate_ssa(self->value.struct_decl, context); break; case AST_STRUCT_FIELD: self->ssa_reg = structfield_generate_ssa(self->value.struct_field, context); break; case AST_LHS: self->ssa_reg = lhsexpr_generate_ssa(self, context); break; case AST_ASSIGN: self->ssa_reg = assignmentexpr_generate_ssa(self, context); break; case AST_IMPORT: /* TODO: Implement cross file references */ self->ssa_reg = 0; break; case AST_STRING: self->ssa_reg = string_generate_ssa(self->value.string, context); break; case AST_VARIABLE: self->ssa_reg = variable_generate_ssa(self->value.variable, context); break; case AST_BINOP: self->ssa_reg = binop_generate_ssa(self->value.binop, context); break; case AST_IF_STATEMENT: if_statement_generate_ssa(self->value.if_stmt, context); break; case AST_WHILE_STATEMENT: while_statement_generate_ssa(self->value.while_stmt, context); break; } self->resolve_data.status = AST_SSA_RESOLVED; return self->ssa_reg; } void scope_generate_ssa(Scope *self, SsaCompilerContext *context) { Ast **ast; Ast **ast_end; ast = buffer_begin(&self->ast_objects); ast_end = buffer_end(&self->ast_objects); for(; ast != ast_end; ++ast) { ignore_result_int(ast_generate_ssa(*ast, context)); } }