diff options
-rw-r--r-- | 05/codegen.b | 167 | ||||
-rw-r--r-- | 05/main.c | 10 | ||||
-rw-r--r-- | README.md | 33 |
3 files changed, 188 insertions, 22 deletions
diff --git a/05/codegen.b b/05/codegen.b index 7dd7f37..d5ec907 100644 --- a/05/codegen.b +++ b/05/codegen.b @@ -662,12 +662,44 @@ function emit_jae_rel32 code_output += 4 return +function emit_cmp_rax_rbx + ; 48 39 d8 + *2code_output = 0x3948 + code_output += 2 + *1code_output = 0xd8 + code_output += 1 + return + function emit_comisd_xmm0_xmm1 ; 66 0f 2f c1 *4code_output = 0xc12f0f66 code_output += 4 return +#define COMPARISON_E 0x4 +#define COMPARISON_NE 0x5 +#define COMPARISON_L 0xc +#define COMPARISON_G 0xf +#define COMPARISON_LE 0xe +#define COMPARISON_GE 0xd +#define COMPARISON_B 0x2 +#define COMPARISON_A 0x7 +#define COMPARISON_BE 0x6 +#define COMPARISON_AE 0x3 + +; emits two instructions: +; setC al +; movzx rax, al +function emit_setC_rax + ; 0f 9C c0 48 0f b6 c0 + argument comparison + local a + a = 0xc0b60f48c0900f + a |= comparison < 8 + *8code_output = a + code_output += 7 + return + ; make sure you put the return value in the proper place before calling this function generate_return emit_mov_reg(REG_RSP, REG_RBP) @@ -1436,7 +1468,78 @@ function generate_push_address_of_expression expr += 8 return expr - +; pop the top two things off the stack of type `type` and compare them +function generate_stack_compare + argument statement + argument type + local p + p = types + type + + emit_add_rsp_imm32(16) ; add rsp, 16 + + ; NB: we do float comparisons as double comparisons (see function comparison_type) + if *1p == TYPE_DOUBLE goto stack_compare_double + if *1p > TYPE_UNSIGNED_LONG goto stack_compare_bad + + emit_mov_rax_qword_rsp_plus_imm32(-16) ; mov rax, [rsp-16] (second operand) + emit_mov_reg(REG_RBX, REG_RAX) ; mov rbx, rax + emit_mov_rax_qword_rsp_plus_imm32(-8) ; mov rax, [rsp-8] (first operand) + emit_cmp_rax_rbx() ; cmp rax, rbx + return + + :stack_compare_bad + die(.str_stack_compare_bad) + :str_stack_compare_bad + string Bad types passed to generate_stack_compare() + byte 0 + :stack_compare_double + emit_mov_rax_qword_rsp_plus_imm32(-8) ; mov rax, [rsp-8] (first operand) + emit_movq_xmm0_rax() ; movq xmm0, rax + emit_mov_rax_qword_rsp_plus_imm32(-16) ; mov rax, [rsp-16] (second operand) + emit_movq_xmm1_rax() ; movq xmm1, rax + emit_comisd_xmm0_xmm1() ; comisd xmm0, xmm1 + return + +; given that expr is a comparison expression, which type should both operands be converted to? +function comparison_type + argument statement + argument expr + local type1 + local type2 + expr += 8 + + type1 = expr + 4 + type1 = *4type1 + expr = expression_get_end(expr) + type2 = expr + 4 + type2 = *4type2 + + type1 += types + type1 = *1type1 + type2 += types + type2 = *1type2 + + ; do float comparisons as double comparisons to make things simpler + if type1 == TYPE_FLOAT goto return_type_double + if type2 == TYPE_FLOAT goto return_type_double + + if type1 == TYPE_POINTER goto return_type_unsigned_long + if type2 == TYPE_POINTER goto return_type_unsigned_long + return expr_binary_type_usual_conversions(statement, type1, type2) + +; is this comparison expression a comparison between unsigned integers or floats? +function comparison_is_unsigned + argument statement + argument expr + local type + type = comparison_type(statement, expr) + type += types + type = *1type + if type > TYPE_UNSIGNED_LONG goto return_1 ; double comparisons use setb/seta not setl/setg + type &= 1 + if type == 0 goto return_1 + return 0 + ; `statement` is used for errors ; returns pointer to end of expression function generate_push_expression @@ -1446,6 +1549,7 @@ function generate_push_expression local c local d local p + local comparison local addr1 local addr2 local type @@ -1475,6 +1579,12 @@ function generate_push_expression if c == EXPRESSION_BITWISE_XOR goto generate_bitwise_xor if c == EXPRESSION_LSHIFT goto generate_lshift if c == EXPRESSION_RSHIFT goto generate_rshift + if c == EXPRESSION_EQ goto generate_eq + if c == EXPRESSION_NEQ goto generate_neq + if c == EXPRESSION_LT goto generate_lt + if c == EXPRESSION_GT goto generate_gt + if c == EXPRESSION_LEQ goto generate_leq + if c == EXPRESSION_GEQ goto generate_geq if c == EXPRESSION_ASSIGN goto generate_assign if c == EXPRESSION_ASSIGN_ADD goto generate_assign_add if c == EXPRESSION_ASSIGN_SUB goto generate_assign_sub @@ -1850,13 +1960,56 @@ function generate_push_expression p = expr + 4 expr = generate_push_expression(statement, expr) generate_stack_compare_against_zero(statement, *4p) - emit_je_rel32(7) ; je +7 (2 bytes for xor eax, eax; 5 bytes for jmp +10) - emit_zero_rax() ; xor eax, eax - emit_jmp_rel32(10) ; jmp +10 (10 bytes for mov rax, 1) - emit_mov_rax_imm64(1) ; mov rax, 1 - emit_push_rax() ; push rax + emit_setC_rax(COMPARISON_E) ; sete al ; movzx rax, al + emit_push_rax() ; push rax + return expr + :generate_eq + comparison = COMPARISON_E + goto generate_comparison + :generate_neq + comparison = COMPARISON_NE + goto generate_comparison + :generate_lt + b = comparison_is_unsigned(statement, expr) + if b != 0 goto comparison_b + comparison = COMPARISON_L + goto generate_comparison + :comparison_b + comparison = COMPARISON_B + goto generate_comparison + :generate_leq + b = comparison_is_unsigned(statement, expr) + if b != 0 goto comparison_be + comparison = COMPARISON_LE + goto generate_comparison + :comparison_be + comparison = COMPARISON_BE + goto generate_comparison + :generate_gt + b = comparison_is_unsigned(statement, expr) + if b != 0 goto comparison_a + comparison = COMPARISON_G + goto generate_comparison + :comparison_a + comparison = COMPARISON_A + goto generate_comparison + :generate_geq + b = comparison_is_unsigned(statement, expr) + if b != 0 goto comparison_ae + comparison = COMPARISON_GE + goto generate_comparison + :comparison_ae + comparison = COMPARISON_AE + goto generate_comparison + :generate_comparison + c = comparison_type(statement, expr) + expr += 8 + expr = generate_push_expression_casted(statement, expr, c) + expr = generate_push_expression_casted(statement, expr, c) + generate_stack_compare(statement, c) + emit_setC_rax(comparison) + emit_push_rax() return expr - :generate_conditional expr += 8 p = expr + 4 @@ -1,19 +1,17 @@ long factorial(long x) { - return x ? x * factorial(x - 1) + return x > 0 ? x * factorial(x - 1) : 1; } long fibonacci(long x) { - return x ? - x-1 ? + return x > 0 ? + x > 1 ? fibonacci(x-1) + fibonacci(x-2) : 1 : 0; } int main(int argc, char **argv) { - int x = 104; - x >>= 3; - return x; + return factorial(6); } @@ -31,13 +31,8 @@ command codes. ## prerequisite knowledge -In this series, I want to *everything* that's going on to be understandable. I'm going to -need to assume some passing knowledge, so here's a quick overview of what you'll -want to know before starting. -You don't need to understand everything about each of these, just get -a general idea: +If you want to follow along with this series, you'll probably want to know about: -- the basics of programming - what a system call is - what memory is - what a compiler is @@ -56,8 +51,7 @@ decimal. - how pointers work - how floating-point numbers work -If you aren't familiar with x86-64 assembly, be sure to check out the instruction list -below. +If you're unfamiliar with x86-64 assembly, you should check out the instruction list below. ## principles @@ -99,7 +93,18 @@ x86-64 has a *gigantic* instruction set. The manual for it is over 2,000 pages long! To make things simpler, we will only use a small subset. Here are all the instructions we'll be using. If you're not familiar with -x86-64 assembly, you might want to look over these (but you don't need to understand everything). +x86-64 assembly, you might want to look over these. + +x86-64 has 16 integer registers: rax, rbx, rcx, rdx, rsp, rbp, rsi, rdi, r8, r9, r10, r11, r12, r13, r14, r15. +We will almost entirely be using the first 8 of these. +al refers to the bottom 8 bits of rax, likewise with bl, cl, dl; +ax refers to the bottom 16 bits of rax, likewise with bx, cx, dx; +eax refers to the bottom 32 bits of rax, likewise with ebx, ecx, edx. + +x86-64 also has 16 floating-point registers: xmm0 through xmm15. We'll only be using +xmm0 and xmm1. These registers can hold either four 32-bit floating-point numbers (`float`s) or +two 64-bit floating-point numbers (`double`s), but we'll only be using them to hold either one +`float` or one `double`. In the table below, `IMM64` means a 64-bit *immediate* (a constant number). `rdx:rax` refers to the 128-bit number you get by combining `rdx` and `rax`. @@ -184,6 +189,16 @@ ax bx cx dx sp bp si di │ ja IMM32 │ 0f 87 IMM32 │ jump if "above" (like jg but unsigned) │ │ jbe IMM32 │ 0f 86 IMM32 │ jump if below or equal to │ │ jae IMM32 │ 0f 83 IMM32 │ jump if above or equal to │ +│ sete al │ 0f 94 c0 │ set al to 1 if equal; 0 otherwise │ +│ setne al │ 0f 95 c0 │ set al to 1 if not equal │ +│ setl al │ 0f 9c c0 │ set al to 1 if less than │ +│ setg al │ 0f 9f c0 │ set al to 1 if greater than │ +│ setle al │ 0f 9e c0 │ set al to 1 if less than or equal to │ +│ setge al │ 0f 9d c0 │ set al to 1 if greater than or equal to│ +│ setb al │ 0f 92 c0 │ set al to 1 if below │ +│ seta al │ 0f 97 c0 │ set al to 1 if above │ +│ setbe al │ 0f 96 c0 │ set al to 1 if below or equal to │ +│ setae al │ 0f 93 c0 │ set al to 1 if above or equal to │ | movq rax, xmm0 | 66 48 0f 7e c0 | set rax to xmm0 | | movq xmm0, rax | 66 48 0f 6e c0 | set xmm0 to rax | | movq xmm1, rax | 66 48 0f 6e c8 | set xmm1 to rax | |