bernsteinbear.com
this repo has no description
1// vim: set tabstop=2 shiftwidth=2 textwidth=79 expandtab:
2// gcc -O2 -g -Wall -Wextra -pedantic -fno-strict-aliasing
3// assets/code/lisp/compiling-binary.c
4
5#define _GNU_SOURCE
6#include <assert.h> // for assert
7#include <stdbool.h> // for bool
8#include <stddef.h> // for NULL
9#include <stdint.h> // for int32_t, etc
10#include <string.h> // for memcpy
11#include <sys/mman.h> // for mmap
12#undef _GNU_SOURCE
13
14#include "greatest.h"
15
16// Objects
17
18typedef int64_t word;
19typedef uint64_t uword;
20
21// These constants are defined in a enum because the right hand side of a
22// statement like
23// static const int kFoo = ...;
24// must be a so-called "Integer Constant Expression". Compilers are required to
25// support a certain set of these expressions, but are not required to support
26// arbitrary arithmetic with other integer constants. Compilers such as gcc
27// before gcc-8 just decided not to play this game, while gcc-8+ and Clang play
28// just fine.
29// Since this arithmetic with constant values works just fine for enums, make
30// all these constants enum values instead.
31// See https://twitter.com/tekknolagi/status/1328449329472835586 for more info.
32enum {
33 kBitsPerByte = 8, // bits
34 kWordSize = sizeof(word), // bytes
35 kBitsPerWord = kWordSize * kBitsPerByte, // bits
36
37 kIntegerTag = 0x0, // 0b00
38 kIntegerTagMask = 0x3, // 0b11
39 kIntegerShift = 2,
40 kIntegerBits = kBitsPerWord - kIntegerShift,
41
42 kImmediateTagMask = 0x3f,
43
44 kCharTag = 0x0f, // 0b00001111
45 kCharMask = 0xff, // 0b11111111
46 kCharShift = 8,
47
48 kBoolTag = 0x1f, // 0b0011111
49 kBoolMask = 0x80, // 0b10000000
50 kBoolShift = 7,
51
52 kNilTag = 0x2f, // 0b101111
53
54 kErrorTag = 0x3f, // 0b111111
55
56 kPairTag = 0x1, // 0b001
57 kSymbolTag = 0x5, // 0b101
58 kClosureTag = 0x6, // 0b110
59 kHeapTagMask = ((uword)0x7), // 0b000...111
60 kHeapPtrMask = ~kHeapTagMask, // 0b1111...1000
61};
62
63// These are defined as macros because they will not work as static const int
64// constants (per above explanation), and enum constants are only required to
65// be an int wide (per ISO C).
66#define INTEGER_MAX ((1LL << (kIntegerBits - 1)) - 1)
67#define INTEGER_MIN (-(1LL << (kIntegerBits - 1)))
68
69uword Object_encode_integer(word value) {
70 assert(value < INTEGER_MAX && "too big");
71 assert(value > INTEGER_MIN && "too small");
72 return value << kIntegerShift;
73}
74
75word Object_decode_integer(uword value) { return (word)value >> kIntegerShift; }
76
77uword Object_encode_char(char value) {
78 return ((uword)value << kCharShift) | kCharTag;
79}
80
81char Object_decode_char(uword value) {
82 return (value >> kCharShift) & kCharMask;
83}
84
85uword Object_encode_bool(bool value) {
86 return ((uword)value << kBoolShift) | kBoolTag;
87}
88
89bool Object_decode_bool(uword value) { return value & kBoolMask; }
90
91uword Object_true() { return Object_encode_bool(true); }
92
93uword Object_false() { return Object_encode_bool(false); }
94
95uword Object_nil() { return 0x2f; }
96
97uword Object_address(void *obj) { return (uword)obj & kHeapPtrMask; }
98
99// End Objects
100
101// Buffer
102
103typedef unsigned char byte;
104
105typedef enum {
106 kWritable,
107 kExecutable,
108} BufferState;
109
110typedef struct {
111 byte *address;
112 BufferState state;
113 size_t len;
114 size_t capacity;
115} Buffer;
116
117byte *Buffer_alloc_writable(size_t capacity) {
118 byte *result = mmap(/*addr=*/NULL, capacity, PROT_READ | PROT_WRITE,
119 MAP_ANONYMOUS | MAP_PRIVATE,
120 /*filedes=*/-1, /*off=*/0);
121 assert(result != MAP_FAILED);
122 return result;
123}
124
125void Buffer_init(Buffer *result, size_t capacity) {
126 result->address = Buffer_alloc_writable(capacity);
127 assert(result->address != MAP_FAILED);
128 result->state = kWritable;
129 result->len = 0;
130 result->capacity = capacity;
131}
132
133void Buffer_deinit(Buffer *buf) {
134 munmap(buf->address, buf->capacity);
135 buf->address = NULL;
136 buf->len = 0;
137 buf->capacity = 0;
138}
139
140int Buffer_make_executable(Buffer *buf) {
141 int result = mprotect(buf->address, buf->len, PROT_EXEC);
142 buf->state = kExecutable;
143 return result;
144}
145
146byte Buffer_at8(Buffer *buf, size_t pos) { return buf->address[pos]; }
147
148void Buffer_at_put8(Buffer *buf, size_t pos, byte b) { buf->address[pos] = b; }
149
150word max(word left, word right) { return left > right ? left : right; }
151
152void Buffer_ensure_capacity(Buffer *buf, word additional_capacity) {
153 if (buf->len + additional_capacity <= buf->capacity) {
154 return;
155 }
156 word new_capacity =
157 max(buf->capacity * 2, buf->capacity + additional_capacity);
158 byte *address = Buffer_alloc_writable(new_capacity);
159 memcpy(address, buf->address, buf->len);
160 int result = munmap(buf->address, buf->capacity);
161 assert(result == 0 && "munmap failed");
162 buf->address = address;
163 buf->capacity = new_capacity;
164}
165
166void Buffer_write8(Buffer *buf, byte b) {
167 Buffer_ensure_capacity(buf, sizeof b);
168 Buffer_at_put8(buf, buf->len++, b);
169}
170
171void Buffer_write32(Buffer *buf, int32_t value) {
172 for (size_t i = 0; i < 4; i++) {
173 Buffer_write8(buf, (value >> (i * kBitsPerByte)) & 0xff);
174 }
175}
176
177void Buffer_write_arr(Buffer *buf, const byte *arr, word arr_size) {
178 Buffer_ensure_capacity(buf, arr_size);
179 for (word i = 0; i < arr_size; i++) {
180 Buffer_write8(buf, arr[i]);
181 }
182}
183
184// End Buffer
185
186// Emit
187
188typedef enum {
189 kRax = 0,
190 kRcx,
191 kRdx,
192 kRbx,
193 kRsp,
194 kRbp,
195 kRsi,
196 kRdi,
197} Register;
198
199typedef enum {
200 kAl = 0,
201 kCl,
202 kDl,
203 kBl,
204 kAh,
205 kCh,
206 kDh,
207 kBh,
208} PartialRegister;
209
210typedef enum {
211 kOverflow = 0,
212 kNotOverflow,
213 kBelow,
214 kCarry = kBelow,
215 kNotAboveOrEqual = kBelow,
216 kAboveOrEqual,
217 kNotBelow = kAboveOrEqual,
218 kNotCarry = kAboveOrEqual,
219 kEqual,
220 kZero = kEqual,
221 kLess = 0xc,
222 kNotGreaterOrEqual = kLess,
223 // TODO(max): Add more
224} Condition;
225
226typedef struct Indirect {
227 Register reg;
228 int8_t disp;
229} Indirect;
230
231Indirect Ind(Register reg, int8_t disp) {
232 return (Indirect){.reg = reg, .disp = disp};
233}
234
235enum {
236 kRexPrefix = 0x48,
237};
238
239void Emit_mov_reg_imm32(Buffer *buf, Register dst, int32_t src) {
240 Buffer_write8(buf, kRexPrefix);
241 Buffer_write8(buf, 0xc7);
242 Buffer_write8(buf, 0xc0 + dst);
243 Buffer_write32(buf, src);
244}
245
246void Emit_ret(Buffer *buf) { Buffer_write8(buf, 0xc3); }
247
248void Emit_add_reg_imm32(Buffer *buf, Register dst, int32_t src) {
249 Buffer_write8(buf, kRexPrefix);
250 if (dst == kRax) {
251 // Optimization: add eax, {imm32} can either be encoded as 05 {imm32} or 81
252 // c0 {imm32}.
253 Buffer_write8(buf, 0x05);
254 } else {
255 Buffer_write8(buf, 0x81);
256 Buffer_write8(buf, 0xc0 + dst);
257 }
258 Buffer_write32(buf, src);
259}
260
261void Emit_sub_reg_imm32(Buffer *buf, Register dst, int32_t src) {
262 Buffer_write8(buf, kRexPrefix);
263 if (dst == kRax) {
264 // Optimization: sub eax, {imm32} can either be encoded as 2d {imm32} or 81
265 // e8 {imm32}.
266 Buffer_write8(buf, 0x2d);
267 } else {
268 Buffer_write8(buf, 0x81);
269 Buffer_write8(buf, 0xe8 + dst);
270 }
271 Buffer_write32(buf, src);
272}
273
274void Emit_shl_reg_imm8(Buffer *buf, Register dst, int8_t bits) {
275 Buffer_write8(buf, kRexPrefix);
276 Buffer_write8(buf, 0xc1);
277 Buffer_write8(buf, 0xe0 + dst);
278 Buffer_write8(buf, bits);
279}
280
281void Emit_shr_reg_imm8(Buffer *buf, Register dst, int8_t bits) {
282 Buffer_write8(buf, kRexPrefix);
283 Buffer_write8(buf, 0xc1);
284 Buffer_write8(buf, 0xe8 + dst);
285 Buffer_write8(buf, bits);
286}
287
288void Emit_or_reg_imm8(Buffer *buf, Register dst, uint8_t tag) {
289 Buffer_write8(buf, kRexPrefix);
290 Buffer_write8(buf, 0x83);
291 Buffer_write8(buf, 0xc8 + dst);
292 Buffer_write8(buf, tag);
293}
294
295void Emit_and_reg_imm8(Buffer *buf, Register dst, uint8_t tag) {
296 Buffer_write8(buf, kRexPrefix);
297 Buffer_write8(buf, 0x83);
298 Buffer_write8(buf, 0xe0 + dst);
299 Buffer_write8(buf, tag);
300}
301
302void Emit_cmp_reg_imm32(Buffer *buf, Register left, int32_t right) {
303 Buffer_write8(buf, kRexPrefix);
304 if (left == kRax) {
305 // Optimization: cmp rax, {imm32} can either be encoded as 3d {imm32} or 81
306 // f8 {imm32}.
307 Buffer_write8(buf, 0x3d);
308 } else {
309 Buffer_write8(buf, 0x81);
310 Buffer_write8(buf, 0xf8 + left);
311 }
312 Buffer_write32(buf, right);
313}
314
315void Emit_setcc_imm8(Buffer *buf, Condition cond, PartialRegister dst) {
316 Buffer_write8(buf, 0x0f);
317 Buffer_write8(buf, 0x90 + cond);
318 Buffer_write8(buf, 0xc0 + dst);
319}
320
321uint8_t disp8(int8_t disp) { return disp >= 0 ? disp : 0x100 + disp; }
322
323// mov [dst+disp], src
324// or
325// mov %src, disp(%dst)
326void Emit_store_reg_indirect(Buffer *buf, Indirect dst, Register src) {
327 Buffer_write8(buf, kRexPrefix);
328 Buffer_write8(buf, 0x89);
329 Buffer_write8(buf, 0x40 + src * 8 + dst.reg);
330 Buffer_write8(buf, disp8(dst.disp));
331}
332
333// add dst, [src+disp]
334// or
335// add disp(%src), %dst
336void Emit_add_reg_indirect(Buffer *buf, Register dst, Indirect src) {
337 Buffer_write8(buf, kRexPrefix);
338 Buffer_write8(buf, 0x03);
339 Buffer_write8(buf, 0x40 + dst * 8 + src.reg);
340 Buffer_write8(buf, disp8(src.disp));
341}
342
343// sub dst, [src+disp]
344// or
345// sub disp(%src), %dst
346void Emit_sub_reg_indirect(Buffer *buf, Register dst, Indirect src) {
347 Buffer_write8(buf, kRexPrefix);
348 Buffer_write8(buf, 0x2b);
349 Buffer_write8(buf, 0x40 + dst * 8 + src.reg);
350 Buffer_write8(buf, disp8(src.disp));
351}
352
353// mul rax, [src+disp]
354// or
355// mul disp(%src), %rax
356void Emit_mul_reg_indirect(Buffer *buf, Indirect src) {
357 Buffer_write8(buf, kRexPrefix);
358 Buffer_write8(buf, 0xf7);
359 Buffer_write8(buf, 0x60 + src.reg);
360 Buffer_write8(buf, disp8(src.disp));
361}
362
363// cmp left, [right+disp]
364// or
365// cmp disp(%right), %left
366void Emit_cmp_reg_indirect(Buffer *buf, Register left, Indirect right) {
367 Buffer_write8(buf, kRexPrefix);
368 Buffer_write8(buf, 0x3b);
369 Buffer_write8(buf, 0x40 + left * 8 + right.reg);
370 Buffer_write8(buf, disp8(right.disp));
371}
372
373// End Emit
374
375// AST
376
377typedef struct ASTNode ASTNode;
378
379typedef struct Pair {
380 ASTNode *car;
381 ASTNode *cdr;
382} Pair;
383
384typedef struct Symbol {
385 word length;
386 char cstr[];
387} Symbol;
388
389bool AST_is_integer(ASTNode *node) {
390 return ((uword)node & kIntegerTagMask) == kIntegerTag;
391}
392
393word AST_get_integer(ASTNode *node) {
394 return Object_decode_integer((uword)node);
395}
396
397ASTNode *AST_new_integer(word value) {
398 return (ASTNode *)Object_encode_integer(value);
399}
400
401bool AST_is_char(ASTNode *node) {
402 return ((uword)node & kImmediateTagMask) == kCharTag;
403}
404
405char AST_get_char(ASTNode *node) { return Object_decode_char((uword)node); }
406
407ASTNode *AST_new_char(char value) {
408 return (ASTNode *)Object_encode_char(value);
409}
410
411bool AST_is_bool(ASTNode *node) {
412 return ((uword)node & kImmediateTagMask) == kBoolTag;
413}
414
415bool AST_get_bool(ASTNode *node) { return Object_decode_bool((uword)node); }
416
417ASTNode *AST_new_bool(bool value) {
418 return (ASTNode *)Object_encode_bool(value);
419}
420
421bool AST_is_nil(ASTNode *node) { return (uword)node == Object_nil(); }
422
423ASTNode *AST_nil() { return (ASTNode *)Object_nil(); }
424
425ASTNode *AST_heap_alloc(unsigned char tag, uword size) {
426 // Initialize to 0
427 uword address = (uword)calloc(size, 1);
428 return (ASTNode *)(address | tag);
429}
430
431bool AST_is_heap_object(ASTNode *node) {
432 // For some reason masking out the tag first and then doing the comparison
433 // makes this branchless
434 unsigned char tag = (uword)node & kHeapTagMask;
435 // Heap object tags are between 0b001 and 0b110 except for 0b100 (which is an
436 // integer)
437 return (tag & kIntegerTagMask) > 0 && (tag & kImmediateTagMask) != 0x7;
438}
439
440void AST_pair_set_car(ASTNode *node, ASTNode *car);
441void AST_pair_set_cdr(ASTNode *node, ASTNode *cdr);
442
443ASTNode *AST_new_pair(ASTNode *car, ASTNode *cdr) {
444 ASTNode *node = AST_heap_alloc(kPairTag, sizeof(Pair));
445 AST_pair_set_car(node, car);
446 AST_pair_set_cdr(node, cdr);
447 return node;
448}
449
450bool AST_is_pair(ASTNode *node) {
451 return ((uword)node & kHeapTagMask) == kPairTag;
452}
453
454Pair *AST_as_pair(ASTNode *node) {
455 assert(AST_is_pair(node));
456 return (Pair *)Object_address(node);
457}
458
459ASTNode *AST_pair_car(ASTNode *node) { return AST_as_pair(node)->car; }
460
461void AST_pair_set_car(ASTNode *node, ASTNode *car) {
462 AST_as_pair(node)->car = car;
463}
464
465ASTNode *AST_pair_cdr(ASTNode *node) { return AST_as_pair(node)->cdr; }
466
467void AST_pair_set_cdr(ASTNode *node, ASTNode *cdr) {
468 AST_as_pair(node)->cdr = cdr;
469}
470
471void AST_heap_free(ASTNode *node) {
472 if (!AST_is_heap_object(node)) {
473 return;
474 }
475 if (AST_is_pair(node)) {
476 AST_heap_free(AST_pair_car(node));
477 AST_heap_free(AST_pair_cdr(node));
478 }
479 free((void *)Object_address(node));
480}
481
482Symbol *AST_as_symbol(ASTNode *node);
483
484ASTNode *AST_new_symbol(const char *str) {
485 word data_length = strlen(str) + 1; // for NUL
486 ASTNode *node = AST_heap_alloc(kSymbolTag, sizeof(Symbol) + data_length);
487 Symbol *s = AST_as_symbol(node);
488 s->length = data_length;
489 memcpy(s->cstr, str, data_length);
490 return node;
491}
492
493bool AST_is_symbol(ASTNode *node) {
494 return ((uword)node & kHeapTagMask) == kSymbolTag;
495}
496
497Symbol *AST_as_symbol(ASTNode *node) {
498 assert(AST_is_symbol(node));
499 return (Symbol *)Object_address(node);
500}
501
502const char *AST_symbol_cstr(ASTNode *node) {
503 return (const char *)AST_as_symbol(node)->cstr;
504}
505
506bool AST_symbol_matches(ASTNode *node, const char *cstr) {
507 return strcmp(AST_symbol_cstr(node), cstr) == 0;
508}
509
510int node_to_str(ASTNode *node, char *buf, word size);
511
512int list_to_str(ASTNode *node, char *buf, word size) {
513 if (AST_is_pair(node)) {
514 word result = 0;
515 result += snprintf(buf + result, size, " ");
516 result += node_to_str(AST_pair_car(node), buf + result, size);
517 result += list_to_str(AST_pair_cdr(node), buf + result, size);
518 return result;
519 }
520 if (AST_is_nil(node)) {
521 return snprintf(buf, size, ")");
522 }
523 word result = 0;
524 result += snprintf(buf + result, size, " . ");
525 result += node_to_str(node, buf + result, size);
526 result += snprintf(buf + result, size, ")");
527 return result;
528}
529
530int node_to_str(ASTNode *node, char *buf, word size) {
531 assert(node != NULL);
532 if (AST_is_integer(node)) {
533 return snprintf(buf, size, "%ld", AST_get_integer(node));
534 }
535 if (AST_is_char(node)) {
536 return snprintf(buf, size, "'%c'", AST_get_char(node));
537 }
538 if (AST_is_bool(node)) {
539 return snprintf(buf, size, "%s", AST_get_bool(node) ? "true" : "false");
540 }
541 if (AST_is_nil(node)) {
542 return snprintf(buf, size, "nil");
543 }
544 if (AST_is_pair(node)) {
545 word result = 0;
546 result += snprintf(buf + result, size, "(");
547 result += node_to_str(AST_pair_car(node), buf + result, size);
548 result += list_to_str(AST_pair_cdr(node), buf + result, size);
549 return result;
550 }
551 if (AST_is_symbol(node)) {
552 return snprintf(buf, size, "%s", AST_symbol_cstr(node));
553 }
554 assert(0 && "unknown ast");
555}
556
557char *AST_to_cstr(ASTNode *node) {
558 int size = node_to_str(node, NULL, 0);
559 char *buf = malloc(size + 1);
560 assert(buf != NULL);
561 node_to_str(node, buf, size + 1);
562 buf[size] = '\0';
563 return buf;
564}
565
566// End AST
567
568// Compile
569
570int Compile_expr(Buffer *buf, ASTNode *node, word stack_index);
571
572ASTNode *operand1(ASTNode *args) { return AST_pair_car(args); }
573
574ASTNode *operand2(ASTNode *args) { return AST_pair_car(AST_pair_cdr(args)); }
575
576#define _(exp) \
577 do { \
578 int result = exp; \
579 if (result != 0) \
580 return result; \
581 } while (0)
582
583void Compile_compare_imm32(Buffer *buf, int32_t value) {
584 Emit_cmp_reg_imm32(buf, kRax, value);
585 Emit_mov_reg_imm32(buf, kRax, 0);
586 Emit_setcc_imm8(buf, kEqual, kAl);
587 Emit_shl_reg_imm8(buf, kRax, kBoolShift);
588 Emit_or_reg_imm8(buf, kRax, kBoolTag);
589}
590
591int Compile_call(Buffer *buf, ASTNode *callable, ASTNode *args,
592 word stack_index) {
593 if (AST_is_symbol(callable)) {
594 if (AST_symbol_matches(callable, "add1")) {
595 _(Compile_expr(buf, operand1(args), stack_index));
596 Emit_add_reg_imm32(buf, kRax, Object_encode_integer(1));
597 return 0;
598 }
599 if (AST_symbol_matches(callable, "sub1")) {
600 _(Compile_expr(buf, operand1(args), stack_index));
601 Emit_sub_reg_imm32(buf, kRax, Object_encode_integer(1));
602 return 0;
603 }
604 if (AST_symbol_matches(callable, "integer->char")) {
605 _(Compile_expr(buf, operand1(args), stack_index));
606 Emit_shl_reg_imm8(buf, kRax, kCharShift - kIntegerShift);
607 Emit_or_reg_imm8(buf, kRax, kCharTag);
608 return 0;
609 }
610 if (AST_symbol_matches(callable, "char->integer")) {
611 _(Compile_expr(buf, operand1(args), stack_index));
612 Emit_shr_reg_imm8(buf, kRax, kCharShift - kIntegerShift);
613 return 0;
614 }
615 if (AST_symbol_matches(callable, "nil?")) {
616 _(Compile_expr(buf, operand1(args), stack_index));
617 Compile_compare_imm32(buf, Object_nil());
618 return 0;
619 }
620 if (AST_symbol_matches(callable, "zero?")) {
621 _(Compile_expr(buf, operand1(args), stack_index));
622 Compile_compare_imm32(buf, Object_encode_integer(0));
623 return 0;
624 }
625 if (AST_symbol_matches(callable, "not")) {
626 _(Compile_expr(buf, operand1(args), stack_index));
627 // All non #f values are truthy
628 // ...this might be a problem if we want to make nil falsey
629 Compile_compare_imm32(buf, Object_false());
630 return 0;
631 }
632 if (AST_symbol_matches(callable, "integer?")) {
633 _(Compile_expr(buf, operand1(args), stack_index));
634 Emit_and_reg_imm8(buf, kRax, kIntegerTagMask);
635 Compile_compare_imm32(buf, kIntegerTag);
636 return 0;
637 }
638 if (AST_symbol_matches(callable, "boolean?")) {
639 _(Compile_expr(buf, operand1(args), stack_index));
640 Emit_and_reg_imm8(buf, kRax, kImmediateTagMask);
641 Compile_compare_imm32(buf, kBoolTag);
642 return 0;
643 }
644 if (AST_symbol_matches(callable, "+")) {
645 _(Compile_expr(buf, operand2(args), stack_index));
646 Emit_store_reg_indirect(buf, /*dst=*/Ind(kRbp, stack_index),
647 /*src=*/kRax);
648 _(Compile_expr(buf, operand1(args), stack_index - kWordSize));
649 Emit_add_reg_indirect(buf, /*dst=*/kRax, /*src=*/Ind(kRbp, stack_index));
650 return 0;
651 }
652 if (AST_symbol_matches(callable, "-")) {
653 _(Compile_expr(buf, operand2(args), stack_index));
654 Emit_store_reg_indirect(buf, /*dst=*/Ind(kRbp, stack_index),
655 /*src=*/kRax);
656 _(Compile_expr(buf, operand1(args), stack_index - kWordSize));
657 Emit_sub_reg_indirect(buf, /*dst=*/kRax, /*src=*/Ind(kRbp, stack_index));
658 return 0;
659 }
660 if (AST_symbol_matches(callable, "*")) {
661 _(Compile_expr(buf, operand2(args), stack_index));
662 // Remove the tag so that the result is still only tagged with 0b00
663 // instead of 0b0000
664 Emit_shr_reg_imm8(buf, kRax, kIntegerShift);
665 Emit_store_reg_indirect(buf, /*dst=*/Ind(kRbp, stack_index),
666 /*src=*/kRax);
667 _(Compile_expr(buf, operand1(args), stack_index - kWordSize));
668 Emit_mul_reg_indirect(buf, /*src=*/Ind(kRbp, stack_index));
669 return 0;
670 }
671 if (AST_symbol_matches(callable, "=")) {
672 _(Compile_expr(buf, operand2(args), stack_index));
673 Emit_store_reg_indirect(buf, /*dst=*/Ind(kRbp, stack_index),
674 /*src=*/kRax);
675 _(Compile_expr(buf, operand1(args), stack_index - kWordSize));
676 Emit_cmp_reg_indirect(buf, kRax, Ind(kRbp, stack_index));
677 Emit_mov_reg_imm32(buf, kRax, 0);
678 Emit_setcc_imm8(buf, kEqual, kAl);
679 Emit_shl_reg_imm8(buf, kRax, kBoolShift);
680 Emit_or_reg_imm8(buf, kRax, kBoolTag);
681 return 0;
682 }
683 if (AST_symbol_matches(callable, "<")) {
684 _(Compile_expr(buf, operand2(args), stack_index));
685 Emit_store_reg_indirect(buf, /*dst=*/Ind(kRbp, stack_index),
686 /*src=*/kRax);
687 _(Compile_expr(buf, operand1(args), stack_index - kWordSize));
688 Emit_cmp_reg_indirect(buf, kRax, Ind(kRbp, stack_index));
689 Emit_mov_reg_imm32(buf, kRax, 0);
690 Emit_setcc_imm8(buf, kLess, kAl);
691 Emit_shl_reg_imm8(buf, kRax, kBoolShift);
692 Emit_or_reg_imm8(buf, kRax, kBoolTag);
693 return 0;
694 }
695 }
696 assert(0 && "unexpected call type");
697}
698
699int Compile_expr(Buffer *buf, ASTNode *node, word stack_index) {
700 if (AST_is_integer(node)) {
701 word value = AST_get_integer(node);
702 Emit_mov_reg_imm32(buf, kRax, Object_encode_integer(value));
703 return 0;
704 }
705 if (AST_is_char(node)) {
706 char value = AST_get_char(node);
707 Emit_mov_reg_imm32(buf, kRax, Object_encode_char(value));
708 return 0;
709 }
710 if (AST_is_bool(node)) {
711 bool value = AST_get_bool(node);
712 Emit_mov_reg_imm32(buf, kRax, Object_encode_bool(value));
713 return 0;
714 }
715 if (AST_is_nil(node)) {
716 Emit_mov_reg_imm32(buf, kRax, Object_nil());
717 return 0;
718 }
719 if (AST_is_pair(node)) {
720 return Compile_call(buf, AST_pair_car(node), AST_pair_cdr(node),
721 stack_index);
722 }
723 assert(0 && "unexpected node type");
724}
725
726static const byte kFunctionPrologue[] = {
727 // push rbp
728 0x55,
729 // mov rbp, rsp
730 kRexPrefix,
731 0x89,
732 0xe5,
733};
734
735static const byte kFunctionEpilogue[] = {
736 // pop rbp
737 0x5d,
738 // ret
739 0xc3,
740};
741
742int Compile_function(Buffer *buf, ASTNode *node) {
743 Buffer_write_arr(buf, kFunctionPrologue, sizeof kFunctionPrologue);
744 _(Compile_expr(buf, node, -kWordSize));
745 Buffer_write_arr(buf, kFunctionEpilogue, sizeof kFunctionEpilogue);
746 return 0;
747}
748
749// End Compile
750
751typedef int (*JitFunction)();
752
753// Testing
754
755uword Testing_execute_expr(Buffer *buf) {
756 assert(buf != NULL);
757 assert(buf->address != NULL);
758 assert(buf->state == kExecutable);
759 // The pointer-pointer cast is allowed but the underlying
760 // data-to-function-pointer back-and-forth is only guaranteed to work on
761 // POSIX systems (because of eg dlsym).
762 JitFunction function = *(JitFunction *)(&buf->address);
763 return function();
764}
765
766TEST Testing_expect_function_has_contents(Buffer *buf, byte *arr,
767 size_t arr_size) {
768 size_t total_size =
769 sizeof kFunctionPrologue + arr_size + sizeof kFunctionEpilogue;
770 ASSERT_EQ(total_size, buf->len);
771
772 byte *ptr = buf->address;
773 ASSERT_MEM_EQ(kFunctionPrologue, ptr, sizeof kFunctionPrologue);
774 ptr += sizeof kFunctionPrologue;
775 ASSERT_MEM_EQ(arr, ptr, arr_size);
776 ptr += arr_size;
777 ASSERT_MEM_EQ(kFunctionEpilogue, ptr, sizeof kFunctionEpilogue);
778 ptr += sizeof kFunctionEpilogue;
779 PASS();
780}
781
782#define EXPECT_EQUALS_BYTES(buf, arr) \
783 ASSERT_MEM_EQ(arr, (buf)->address, sizeof arr)
784
785#define EXPECT_FUNCTION_CONTAINS_CODE(buf, arr) \
786 CHECK_CALL(Testing_expect_function_has_contents(buf, arr, sizeof arr))
787
788#define RUN_BUFFER_TEST(test_name) \
789 do { \
790 Buffer buf; \
791 Buffer_init(&buf, 1); \
792 GREATEST_RUN_TEST1(test_name, &buf); \
793 Buffer_deinit(&buf); \
794 } while (0)
795
796ASTNode *list1(ASTNode *item0) { return AST_new_pair(item0, AST_nil()); }
797
798ASTNode *list2(ASTNode *item0, ASTNode *item1) {
799 return AST_new_pair(item0, list1(item1));
800}
801
802ASTNode *list3(ASTNode *item0, ASTNode *item1, ASTNode *item2) {
803 return AST_new_pair(item0, list2(item1, item2));
804}
805
806ASTNode *new_unary_call(const char *name, ASTNode *arg) {
807 return list2(AST_new_symbol(name), arg);
808}
809
810ASTNode *new_binary_call(const char *name, ASTNode *arg0, ASTNode *arg1) {
811 return list3(AST_new_symbol(name), arg0, arg1);
812}
813
814// End Testing
815
816// Tests
817
818TEST encode_positive_integer(void) {
819 ASSERT_EQ(Object_encode_integer(0), 0x0);
820 ASSERT_EQ(Object_encode_integer(1), 0x4);
821 ASSERT_EQ(Object_encode_integer(10), 0x28);
822 PASS();
823}
824
825TEST encode_negative_integer(void) {
826 ASSERT_EQ(Object_encode_integer(0), 0x0);
827 ASSERT_EQ(Object_encode_integer(-1), 0xfffffffffffffffc);
828 ASSERT_EQ(Object_encode_integer(-10), 0xffffffffffffffd8);
829 PASS();
830}
831
832TEST encode_char(void) {
833 ASSERT_EQ(Object_encode_char('\0'), 0xf);
834 ASSERT_EQ(Object_encode_char('a'), 0x610f);
835 PASS();
836}
837
838TEST decode_char(void) {
839 ASSERT_EQ(Object_decode_char(0xf), '\0');
840 ASSERT_EQ(Object_decode_char(0x610f), 'a');
841 PASS();
842}
843
844TEST encode_bool(void) {
845 ASSERT_EQ(Object_encode_bool(true), 0x9f);
846 ASSERT_EQ(Object_encode_bool(false), 0x1f);
847 ASSERT_EQ(Object_true(), 0x9f);
848 ASSERT_EQ(Object_false(), 0x1f);
849 PASS();
850}
851
852TEST decode_bool(void) {
853 ASSERT_EQ(Object_decode_bool(0x9f), true);
854 ASSERT_EQ(Object_decode_bool(0x1f), false);
855 PASS();
856}
857
858TEST address(void) {
859 ASSERT_EQ(Object_address((void *)0xFF01), 0xFF00);
860 PASS();
861}
862
863TEST ast_new_pair(void) {
864 ASTNode *node = AST_new_pair(NULL, NULL);
865 ASSERT(AST_is_pair(node));
866 AST_heap_free(node);
867 PASS();
868}
869
870TEST ast_pair_car_returns_car(void) {
871 ASTNode *node = AST_new_pair(AST_new_integer(123), NULL);
872 ASTNode *car = AST_pair_car(node);
873 ASSERT(AST_is_integer(car));
874 ASSERT_EQ(Object_decode_integer((uword)car), 123);
875 AST_heap_free(node);
876 PASS();
877}
878
879TEST ast_pair_cdr_returns_cdr(void) {
880 ASTNode *node = AST_new_pair(NULL, AST_new_integer(123));
881 ASTNode *cdr = AST_pair_cdr(node);
882 ASSERT(AST_is_integer(cdr));
883 ASSERT_EQ(Object_decode_integer((uword)cdr), 123);
884 AST_heap_free(node);
885 PASS();
886}
887
888TEST ast_new_symbol(void) {
889 const char *value = "my symbol";
890 ASTNode *node = AST_new_symbol(value);
891 ASSERT(AST_is_symbol(node));
892 ASSERT_STR_EQ(AST_symbol_cstr(node), value);
893 AST_heap_free(node);
894 PASS();
895}
896
897TEST buffer_write8_increases_length(Buffer *buf) {
898 ASSERT_EQ(buf->len, 0);
899 Buffer_write8(buf, 0xdb);
900 ASSERT_EQ(Buffer_at8(buf, 0), 0xdb);
901 ASSERT_EQ(buf->len, 1);
902 PASS();
903}
904
905TEST buffer_write8_expands_buffer(void) {
906 Buffer buf;
907 Buffer_init(&buf, 1);
908 ASSERT_EQ(buf.capacity, 1);
909 ASSERT_EQ(buf.len, 0);
910 Buffer_write8(&buf, 0xdb);
911 Buffer_write8(&buf, 0xef);
912 ASSERT(buf.capacity > 1);
913 ASSERT_EQ(buf.len, 2);
914 Buffer_deinit(&buf);
915 PASS();
916}
917
918TEST buffer_write32_expands_buffer(void) {
919 Buffer buf;
920 Buffer_init(&buf, 1);
921 ASSERT_EQ(buf.capacity, 1);
922 ASSERT_EQ(buf.len, 0);
923 Buffer_write32(&buf, 0xdeadbeef);
924 ASSERT(buf.capacity > 1);
925 ASSERT_EQ(buf.len, 4);
926 Buffer_deinit(&buf);
927 PASS();
928}
929
930TEST buffer_write32_writes_little_endian(Buffer *buf) {
931 Buffer_write32(buf, 0xdeadbeef);
932 ASSERT_EQ(Buffer_at8(buf, 0), 0xef);
933 ASSERT_EQ(Buffer_at8(buf, 1), 0xbe);
934 ASSERT_EQ(Buffer_at8(buf, 2), 0xad);
935 ASSERT_EQ(Buffer_at8(buf, 3), 0xde);
936 PASS();
937}
938
939TEST compile_positive_integer(Buffer *buf) {
940 word value = 123;
941 ASTNode *node = AST_new_integer(value);
942 int compile_result = Compile_function(buf, node);
943 ASSERT_EQ(compile_result, 0);
944 // mov eax, imm(123)
945 byte expected[] = {0x48, 0xc7, 0xc0, 0xec, 0x01, 0x00, 0x00};
946 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
947 Buffer_make_executable(buf);
948 uword result = Testing_execute_expr(buf);
949 ASSERT_EQ(result, Object_encode_integer(value));
950 PASS();
951}
952
953TEST compile_negative_integer(Buffer *buf) {
954 word value = -123;
955 ASTNode *node = AST_new_integer(value);
956 int compile_result = Compile_function(buf, node);
957 ASSERT_EQ(compile_result, 0);
958 // mov eax, imm(-123)
959 byte expected[] = {0x48, 0xc7, 0xc0, 0x14, 0xfe, 0xff, 0xff};
960 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
961 Buffer_make_executable(buf);
962 uword result = Testing_execute_expr(buf);
963 ASSERT_EQ(result, Object_encode_integer(value));
964 PASS();
965}
966
967TEST compile_char(Buffer *buf) {
968 char value = 'a';
969 ASTNode *node = AST_new_char(value);
970 int compile_result = Compile_function(buf, node);
971 ASSERT_EQ(compile_result, 0);
972 // mov eax, imm('a')
973 byte expected[] = {0x48, 0xc7, 0xc0, 0x0f, 0x61, 0x00, 0x00};
974 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
975 Buffer_make_executable(buf);
976 uword result = Testing_execute_expr(buf);
977 ASSERT_EQ(result, Object_encode_char(value));
978 PASS();
979}
980
981TEST compile_true(Buffer *buf) {
982 ASTNode *node = AST_new_bool(true);
983 int compile_result = Compile_function(buf, node);
984 ASSERT_EQ(compile_result, 0);
985 // mov eax, imm(true)
986 byte expected[] = {0x48, 0xc7, 0xc0, 0x9f, 0x0, 0x0, 0x0};
987 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
988 Buffer_make_executable(buf);
989 uword result = Testing_execute_expr(buf);
990 ASSERT_EQ(result, Object_true());
991 PASS();
992}
993
994TEST compile_false(Buffer *buf) {
995 ASTNode *node = AST_new_bool(false);
996 int compile_result = Compile_function(buf, node);
997 ASSERT_EQ(compile_result, 0);
998 // mov eax, imm(false)
999 byte expected[] = {0x48, 0xc7, 0xc0, 0x1f, 0x00, 0x00, 0x00};
1000 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1001 Buffer_make_executable(buf);
1002 uword result = Testing_execute_expr(buf);
1003 ASSERT_EQ(result, Object_false());
1004 PASS();
1005}
1006
1007TEST compile_nil(Buffer *buf) {
1008 ASTNode *node = AST_nil();
1009 int compile_result = Compile_function(buf, node);
1010 ASSERT_EQ(compile_result, 0);
1011 // mov eax, imm(nil)
1012 byte expected[] = {0x48, 0xc7, 0xc0, 0x2f, 0x00, 0x00, 0x00};
1013 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1014 Buffer_make_executable(buf);
1015 uword result = Testing_execute_expr(buf);
1016 ASSERT_EQ(result, Object_nil());
1017 PASS();
1018}
1019
1020TEST compile_unary_add1(Buffer *buf) {
1021 ASTNode *node = new_unary_call("add1", AST_new_integer(123));
1022 int compile_result = Compile_function(buf, node);
1023 ASSERT_EQ(compile_result, 0);
1024 // mov rax, imm(123); add rax, imm(1)
1025 byte expected[] = {0x48, 0xc7, 0xc0, 0xec, 0x01, 0x00, 0x00,
1026 0x48, 0x05, 0x04, 0x00, 0x00, 0x00};
1027 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1028 Buffer_make_executable(buf);
1029 uword result = Testing_execute_expr(buf);
1030 ASSERT_EQ(result, Object_encode_integer(124));
1031 AST_heap_free(node);
1032 PASS();
1033}
1034
1035TEST compile_unary_add1_nested(Buffer *buf) {
1036 ASTNode *node =
1037 new_unary_call("add1", new_unary_call("add1", AST_new_integer(123)));
1038 int compile_result = Compile_function(buf, node);
1039 ASSERT_EQ(compile_result, 0);
1040 // mov rax, imm(123); add rax, imm(1); add rax, imm(1)
1041 byte expected[] = {0x48, 0xc7, 0xc0, 0xec, 0x01, 0x00, 0x00, 0x48, 0x05, 0x04,
1042 0x00, 0x00, 0x00, 0x48, 0x05, 0x04, 0x00, 0x00, 0x00};
1043 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1044 Buffer_make_executable(buf);
1045 uword result = Testing_execute_expr(buf);
1046 ASSERT_EQ(result, Object_encode_integer(125));
1047 AST_heap_free(node);
1048 PASS();
1049}
1050
1051TEST compile_unary_sub1(Buffer *buf) {
1052 ASTNode *node = new_unary_call("sub1", AST_new_integer(123));
1053 int compile_result = Compile_function(buf, node);
1054 ASSERT_EQ(compile_result, 0);
1055 // mov rax, imm(123); sub rax, imm(1)
1056 byte expected[] = {0x48, 0xc7, 0xc0, 0xec, 0x01, 0x00, 0x00,
1057 0x48, 0x2d, 0x04, 0x00, 0x00, 0x00};
1058 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1059 Buffer_make_executable(buf);
1060 uword result = Testing_execute_expr(buf);
1061 ASSERT_EQ(result, Object_encode_integer(122));
1062 AST_heap_free(node);
1063 PASS();
1064}
1065
1066TEST compile_unary_integer_to_char(Buffer *buf) {
1067 ASTNode *node = new_unary_call("integer->char", AST_new_integer(97));
1068 int compile_result = Compile_function(buf, node);
1069 ASSERT_EQ(compile_result, 0);
1070 // mov rax, imm(97); shl rax, 6; or rax, 0xf
1071 byte expected[] = {0x48, 0xc7, 0xc0, 0x84, 0x01, 0x00, 0x00, 0x48,
1072 0xc1, 0xe0, 0x06, 0x48, 0x83, 0xc8, 0x0f};
1073 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1074 Buffer_make_executable(buf);
1075 uword result = Testing_execute_expr(buf);
1076 ASSERT_EQ(result, Object_encode_char('a'));
1077 AST_heap_free(node);
1078 PASS();
1079}
1080
1081TEST compile_unary_char_to_integer(Buffer *buf) {
1082 ASTNode *node = new_unary_call("char->integer", AST_new_char('a'));
1083 int compile_result = Compile_function(buf, node);
1084 ASSERT_EQ(compile_result, 0);
1085 // mov rax, imm('a'); shr rax, 6
1086 byte expected[] = {0x48, 0xc7, 0xc0, 0x0f, 0x61, 0x00,
1087 0x00, 0x48, 0xc1, 0xe8, 0x06};
1088 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1089 Buffer_make_executable(buf);
1090 uword result = Testing_execute_expr(buf);
1091 ASSERT_EQ(result, Object_encode_integer(97));
1092 AST_heap_free(node);
1093 PASS();
1094}
1095
1096TEST compile_unary_nilp_with_nil_returns_true(Buffer *buf) {
1097 ASTNode *node = new_unary_call("nil?", AST_nil());
1098 int compile_result = Compile_function(buf, node);
1099 ASSERT_EQ(compile_result, 0);
1100 // 0: 48 c7 c0 2f 00 00 00 mov rax,0x2f
1101 // 7: 48 3d 2f 00 00 00 cmp rax,0x0000002f
1102 // d: 48 c7 c0 00 00 00 00 mov rax,0x0
1103 // 14: 0f 94 c0 sete al
1104 // 17: 48 c1 e0 07 shl rax,0x7
1105 // 1b: 48 83 c8 1f or rax,0x1f
1106 byte expected[] = {0x48, 0xc7, 0xc0, 0x2f, 0x00, 0x00, 0x00, 0x48,
1107 0x3d, 0x2f, 0x00, 0x00, 0x00, 0x48, 0xc7, 0xc0,
1108 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0, 0x48,
1109 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1110 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1111 Buffer_make_executable(buf);
1112 uword result = Testing_execute_expr(buf);
1113 ASSERT_EQ(result, Object_true());
1114 AST_heap_free(node);
1115 PASS();
1116}
1117
1118TEST compile_unary_nilp_with_non_nil_returns_false(Buffer *buf) {
1119 ASTNode *node = new_unary_call("nil?", AST_new_integer(5));
1120 int compile_result = Compile_function(buf, node);
1121 ASSERT_EQ(compile_result, 0);
1122 // 0: 48 c7 c0 14 00 00 00 mov rax,0x14
1123 // 7: 48 3d 2f 00 00 00 cmp rax,0x0000002f
1124 // d: 48 c7 c0 00 00 00 00 mov rax,0x0
1125 // 14: 0f 94 c0 sete al
1126 // 17: 48 c1 e0 07 shl rax,0x7
1127 // 1b: 48 83 c8 1f or rax,0x1f
1128 byte expected[] = {0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00, 0x48,
1129 0x3d, 0x2f, 0x00, 0x00, 0x00, 0x48, 0xc7, 0xc0,
1130 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0, 0x48,
1131 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1132 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1133 Buffer_make_executable(buf);
1134 uword result = Testing_execute_expr(buf);
1135 ASSERT_EQ(result, Object_false());
1136 AST_heap_free(node);
1137 PASS();
1138}
1139
1140TEST compile_unary_zerop_with_zero_returns_true(Buffer *buf) {
1141 ASTNode *node = new_unary_call("zero?", AST_new_integer(0));
1142 int compile_result = Compile_function(buf, node);
1143 ASSERT_EQ(compile_result, 0);
1144 // 0: 48 c7 c0 00 00 00 00 mov rax,0x0
1145 // 7: 48 3d 00 00 00 00 cmp rax,0x00000000
1146 // d: 48 c7 c0 00 00 00 00 mov rax,0x0
1147 // 14: 0f 94 c0 sete al
1148 // 17: 48 c1 e0 07 shl rax,0x7
1149 // 1b: 48 83 c8 1f or rax,0x1f
1150 byte expected[] = {0x48, 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x48,
1151 0x3d, 0x00, 0x00, 0x00, 0x00, 0x48, 0xc7, 0xc0,
1152 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0, 0x48,
1153 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1154 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1155 Buffer_make_executable(buf);
1156 uword result = Testing_execute_expr(buf);
1157 ASSERT_EQ(result, Object_true());
1158 AST_heap_free(node);
1159 PASS();
1160}
1161
1162TEST compile_unary_zerop_with_non_zero_returns_false(Buffer *buf) {
1163 ASTNode *node = new_unary_call("zero?", AST_new_integer(5));
1164 int compile_result = Compile_function(buf, node);
1165 ASSERT_EQ(compile_result, 0);
1166 // 0: 48 c7 c0 14 00 00 00 mov rax,0x14
1167 // 7: 48 3d 00 00 00 00 cmp rax,0x00000000
1168 // d: 48 c7 c0 00 00 00 00 mov rax,0x0
1169 // 14: 0f 94 c0 sete al
1170 // 17: 48 c1 e0 07 shl rax,0x7
1171 // 1b: 48 83 c8 1f or rax,0x1f
1172 byte expected[] = {0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00, 0x48,
1173 0x3d, 0x00, 0x00, 0x00, 0x00, 0x48, 0xc7, 0xc0,
1174 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0, 0x48,
1175 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1176 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1177 Buffer_make_executable(buf);
1178 uword result = Testing_execute_expr(buf);
1179 ASSERT_EQ(result, Object_false());
1180 AST_heap_free(node);
1181 PASS();
1182}
1183
1184TEST compile_unary_not_with_false_returns_true(Buffer *buf) {
1185 ASTNode *node = new_unary_call("not", AST_new_bool(false));
1186 int compile_result = Compile_function(buf, node);
1187 ASSERT_EQ(compile_result, 0);
1188 // 0: 48 c7 c0 1f 00 00 00 mov rax,0x1f
1189 // 7: 48 3d 1f 00 00 00 cmp rax,0x0000001f
1190 // d: 48 c7 c0 00 00 00 00 mov rax,0x0
1191 // 14: 0f 94 c0 sete al
1192 // 17: 48 c1 e0 07 shl rax,0x7
1193 // 1b: 48 83 c8 1f or rax,0x1f
1194 byte expected[] = {0x48, 0xc7, 0xc0, 0x1f, 0x00, 0x00, 0x00, 0x48,
1195 0x3d, 0x1f, 0x00, 0x00, 0x00, 0x48, 0xc7, 0xc0,
1196 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0, 0x48,
1197 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1198 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1199 Buffer_make_executable(buf);
1200 uword result = Testing_execute_expr(buf);
1201 ASSERT_EQ(result, Object_true());
1202 AST_heap_free(node);
1203 PASS();
1204}
1205
1206TEST compile_unary_not_with_non_false_returns_false(Buffer *buf) {
1207 ASTNode *node = new_unary_call("not", AST_new_integer(5));
1208 int compile_result = Compile_function(buf, node);
1209 ASSERT_EQ(compile_result, 0);
1210 // 0: 48 c7 c0 14 00 00 00 mov rax,0x14
1211 // 7: 48 3d 1f 00 00 00 cmp rax,0x0000001f
1212 // d: 48 c7 c0 00 00 00 00 mov rax,0x0
1213 // 14: 0f 94 c0 sete al
1214 // 17: 48 c1 e0 07 shl rax,0x7
1215 // 1b: 48 83 c8 1f or rax,0x1f
1216 byte expected[] = {0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00, 0x48,
1217 0x3d, 0x1f, 0x00, 0x00, 0x00, 0x48, 0xc7, 0xc0,
1218 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0, 0x48,
1219 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1220 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1221 Buffer_make_executable(buf);
1222 uword result = Testing_execute_expr(buf);
1223 ASSERT_EQ(result, Object_false());
1224 AST_heap_free(node);
1225 PASS();
1226}
1227
1228TEST compile_unary_integerp_with_integer_returns_true(Buffer *buf) {
1229 ASTNode *node = new_unary_call("integer?", AST_new_integer(5));
1230 int compile_result = Compile_function(buf, node);
1231 ASSERT_EQ(compile_result, 0);
1232 // 0: 48 c7 c0 14 00 00 00 mov rax,0x14
1233 // 7: 48 83 e0 03 and rax,0x3
1234 // b: 48 3d 00 00 00 00 cmp rax,0x00000000
1235 // 11: 48 c7 c0 00 00 00 00 mov rax,0x0
1236 // 18: 0f 94 c0 sete al
1237 // 1b: 48 c1 e0 07 shl rax,0x7
1238 // 1f: 48 83 c8 1f or rax,0x1f
1239 byte expected[] = {0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00, 0x48, 0x83,
1240 0xe0, 0x03, 0x48, 0x3d, 0x00, 0x00, 0x00, 0x00, 0x48,
1241 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0,
1242 0x48, 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1243 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1244 Buffer_make_executable(buf);
1245 uword result = Testing_execute_expr(buf);
1246 ASSERT_EQ(result, Object_true());
1247 AST_heap_free(node);
1248 PASS();
1249}
1250
1251TEST compile_unary_integerp_with_non_integer_returns_false(Buffer *buf) {
1252 ASTNode *node = new_unary_call("integer?", AST_nil());
1253 int compile_result = Compile_function(buf, node);
1254 ASSERT_EQ(compile_result, 0);
1255 // 0: 48 c7 c0 2f 00 00 00 mov rax,0x2f
1256 // 7: 48 83 e0 03 and rax,0x3
1257 // b: 48 3d 00 00 00 00 cmp rax,0x00000000
1258 // 11: 48 c7 c0 00 00 00 00 mov rax,0x0
1259 // 18: 0f 94 c0 sete al
1260 // 1b: 48 c1 e0 07 shl rax,0x7
1261 // 1f: 48 83 c8 1f or rax,0x1f
1262 byte expected[] = {0x48, 0xc7, 0xc0, 0x2f, 0x00, 0x00, 0x00, 0x48, 0x83,
1263 0xe0, 0x03, 0x48, 0x3d, 0x00, 0x00, 0x00, 0x00, 0x48,
1264 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0,
1265 0x48, 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1266 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1267 Buffer_make_executable(buf);
1268 uword result = Testing_execute_expr(buf);
1269 ASSERT_EQ(result, Object_false());
1270 AST_heap_free(node);
1271 PASS();
1272}
1273
1274TEST compile_unary_booleanp_with_boolean_returns_true(Buffer *buf) {
1275 ASTNode *node = new_unary_call("boolean?", AST_new_bool(true));
1276 int compile_result = Compile_function(buf, node);
1277 ASSERT_EQ(compile_result, 0);
1278 // 0: 48 c7 c0 9f 00 00 00 mov rax,0x9f
1279 // 7: 48 83 e0 3f and rax,0x3f
1280 // b: 48 3d 1f 00 00 00 cmp rax,0x0000001f
1281 // 11: 48 c7 c0 00 00 00 00 mov rax,0x0
1282 // 18: 0f 94 c0 sete al
1283 // 1b: 48 c1 e0 07 shl rax,0x7
1284 // 1f: 48 83 c8 1f or rax,0x1f
1285 byte expected[] = {0x48, 0xc7, 0xc0, 0x9f, 0x00, 0x00, 0x00, 0x48, 0x83,
1286 0xe0, 0x3f, 0x48, 0x3d, 0x1f, 0x00, 0x00, 0x00, 0x48,
1287 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0,
1288 0x48, 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1289 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1290 Buffer_make_executable(buf);
1291 uword result = Testing_execute_expr(buf);
1292 ASSERT_EQ(result, Object_true());
1293 AST_heap_free(node);
1294 PASS();
1295}
1296
1297TEST compile_unary_booleanp_with_non_boolean_returns_false(Buffer *buf) {
1298 ASTNode *node = new_unary_call("boolean?", AST_new_integer(5));
1299 int compile_result = Compile_function(buf, node);
1300 ASSERT_EQ(compile_result, 0);
1301 // 0: 48 c7 c0 14 00 00 00 mov rax,0x14
1302 // 7: 48 83 e0 3f and rax,0x3f
1303 // b: 48 3d 1f 00 00 00 cmp rax,0x0000001f
1304 // 11: 48 c7 c0 00 00 00 00 mov rax,0x0
1305 // 18: 0f 94 c0 sete al
1306 // 1b: 48 c1 e0 07 shl rax,0x7
1307 // 1f: 48 83 c8 1f or rax,0x1f
1308 byte expected[] = {0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00, 0x48, 0x83,
1309 0xe0, 0x3f, 0x48, 0x3d, 0x1f, 0x00, 0x00, 0x00, 0x48,
1310 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x94, 0xc0,
1311 0x48, 0xc1, 0xe0, 0x07, 0x48, 0x83, 0xc8, 0x1f};
1312 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1313 Buffer_make_executable(buf);
1314 uword result = Testing_execute_expr(buf);
1315 ASSERT_EQ(result, Object_false());
1316 AST_heap_free(node);
1317 PASS();
1318}
1319
1320TEST compile_binary_plus(Buffer *buf) {
1321 ASTNode *node = new_binary_call("+", AST_new_integer(5), AST_new_integer(8));
1322 int compile_result = Compile_function(buf, node);
1323 ASSERT_EQ(compile_result, 0);
1324 byte expected[] = {
1325 // 0: 48 c7 c0 20 00 00 00 mov rax,0x20
1326 0x48, 0xc7, 0xc0, 0x20, 0x00, 0x00, 0x00,
1327 // 7: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
1328 0x48, 0x89, 0x45, 0xf8,
1329 // b: 48 c7 c0 14 00 00 00 mov rax,0x14
1330 0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00,
1331 // 12: 48 03 45 f8 add rax,QWORD PTR [rbp-0x8]
1332 0x48, 0x03, 0x45, 0xf8};
1333 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1334 Buffer_make_executable(buf);
1335 uword result = Testing_execute_expr(buf);
1336 ASSERT_EQ(result, Object_encode_integer(13));
1337 AST_heap_free(node);
1338 PASS();
1339}
1340
1341TEST compile_binary_plus_nested(Buffer *buf) {
1342 ASTNode *node = new_binary_call(
1343 "+", new_binary_call("+", AST_new_integer(1), AST_new_integer(2)),
1344 new_binary_call("+", AST_new_integer(3), AST_new_integer(4)));
1345 int compile_result = Compile_function(buf, node);
1346 ASSERT_EQ(compile_result, 0);
1347 byte expected[] = {
1348 // 4: 48 c7 c0 10 00 00 00 mov rax,0x10
1349 0x48, 0xc7, 0xc0, 0x10, 0x00, 0x00, 0x00,
1350 // b: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
1351 0x48, 0x89, 0x45, 0xf8,
1352 // f: 48 c7 c0 0c 00 00 00 mov rax,0xc
1353 0x48, 0xc7, 0xc0, 0x0c, 0x00, 0x00, 0x00,
1354 // 16: 48 03 45 f8 add rax,QWORD PTR [rbp-0x8]
1355 0x48, 0x03, 0x45, 0xf8,
1356 // 1a: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
1357 0x48, 0x89, 0x45, 0xf8,
1358 // 1e: 48 c7 c0 08 00 00 00 mov rax,0x8
1359 0x48, 0xc7, 0xc0, 0x08, 0x00, 0x00, 0x00,
1360 // 25: 48 89 45 f0 mov QWORD PTR [rbp-0x10],rax
1361 0x48, 0x89, 0x45, 0xf0,
1362 // 29: 48 c7 c0 04 00 00 00 mov rax,0x4
1363 0x48, 0xc7, 0xc0, 0x04, 0x00, 0x00, 0x00,
1364 // 30: 48 03 45 f0 add rax,QWORD PTR [rbp-0x10]
1365 0x48, 0x03, 0x45, 0xf0,
1366 // 34: 48 03 45 f8 add rax,QWORD PTR [rbp-0x8]
1367 0x48, 0x03, 0x45, 0xf8};
1368 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1369 Buffer_make_executable(buf);
1370 uword result = Testing_execute_expr(buf);
1371 ASSERT_EQ(result, Object_encode_integer(10));
1372 AST_heap_free(node);
1373 PASS();
1374}
1375
1376TEST compile_binary_minus(Buffer *buf) {
1377 ASTNode *node = new_binary_call("-", AST_new_integer(5), AST_new_integer(8));
1378 int compile_result = Compile_function(buf, node);
1379 ASSERT_EQ(compile_result, 0);
1380 byte expected[] = {
1381 // 0: 48 c7 c0 20 00 00 00 mov rax,0x20
1382 0x48, 0xc7, 0xc0, 0x20, 0x00, 0x00, 0x00,
1383 // 7: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
1384 0x48, 0x89, 0x45, 0xf8,
1385 // b: 48 c7 c0 14 00 00 00 mov rax,0x14
1386 0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00,
1387 // 12: 48 2b 45 f8 add rax,QWORD PTR [rbp-0x8]
1388 0x48, 0x2b, 0x45, 0xf8};
1389 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1390 Buffer_make_executable(buf);
1391 uword result = Testing_execute_expr(buf);
1392 ASSERT_EQ(result, Object_encode_integer(-3));
1393 AST_heap_free(node);
1394 PASS();
1395}
1396
1397TEST compile_binary_minus_nested(Buffer *buf) {
1398 ASTNode *node = new_binary_call(
1399 "-", new_binary_call("-", AST_new_integer(5), AST_new_integer(1)),
1400 new_binary_call("-", AST_new_integer(4), AST_new_integer(3)));
1401 int compile_result = Compile_function(buf, node);
1402 ASSERT_EQ(compile_result, 0);
1403 byte expected[] = {
1404 // 4: 48 c7 c0 0c 00 00 00 mov rax,0xc
1405 0x48, 0xc7, 0xc0, 0x0c, 0x00, 0x00, 0x00,
1406 // b: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
1407 0x48, 0x89, 0x45, 0xf8,
1408 // f: 48 c7 c0 10 00 00 00 mov rax,0x10
1409 0x48, 0xc7, 0xc0, 0x10, 0x00, 0x00, 0x00,
1410 // 16: 48 2b 45 f8 add rax,QWORD PTR [rbp-0x8]
1411 0x48, 0x2b, 0x45, 0xf8,
1412 // 1a: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
1413 0x48, 0x89, 0x45, 0xf8,
1414 // 1e: 48 c7 c0 04 00 00 00 mov rax,0x4
1415 0x48, 0xc7, 0xc0, 0x04, 0x00, 0x00, 0x00,
1416 // 25: 48 89 45 f0 mov QWORD PTR [rbp-0x10],rax
1417 0x48, 0x89, 0x45, 0xf0,
1418 // 29: 48 c7 c0 14 00 00 00 mov rax,0x14
1419 0x48, 0xc7, 0xc0, 0x14, 0x00, 0x00, 0x00,
1420 // 30: 48 2b 45 f0 add rax,QWORD PTR [rbp-0x10]
1421 0x48, 0x2b, 0x45, 0xf0,
1422 // 34: 48 2b 45 f8 add rax,QWORD PTR [rbp-0x8]
1423 0x48, 0x2b, 0x45, 0xf8};
1424 EXPECT_FUNCTION_CONTAINS_CODE(buf, expected);
1425 Buffer_make_executable(buf);
1426 uword result = Testing_execute_expr(buf);
1427 ASSERT_EQ(result, Object_encode_integer(3));
1428 AST_heap_free(node);
1429 PASS();
1430}
1431
1432TEST compile_binary_mul(Buffer *buf) {
1433 ASTNode *node = new_binary_call("*", AST_new_integer(5), AST_new_integer(8));
1434 int compile_result = Compile_function(buf, node);
1435 ASSERT_EQ(compile_result, 0);
1436 Buffer_make_executable(buf);
1437 uword result = Testing_execute_expr(buf);
1438 ASSERT_EQ_FMT(Object_encode_integer(40), result, "0x%lx");
1439 AST_heap_free(node);
1440 PASS();
1441}
1442
1443TEST compile_binary_mul_nested(Buffer *buf) {
1444 ASTNode *node = new_binary_call(
1445 "*", new_binary_call("*", AST_new_integer(1), AST_new_integer(2)),
1446 new_binary_call("*", AST_new_integer(3), AST_new_integer(4)));
1447 int compile_result = Compile_function(buf, node);
1448 ASSERT_EQ(compile_result, 0);
1449 Buffer_make_executable(buf);
1450 uword result = Testing_execute_expr(buf);
1451 ASSERT_EQ_FMT(Object_encode_integer(24), result, "0x%lx");
1452 AST_heap_free(node);
1453 PASS();
1454}
1455
1456TEST compile_binary_eq_with_same_address_returns_true(Buffer *buf) {
1457 ASTNode *node = new_binary_call("=", AST_new_integer(5), AST_new_integer(5));
1458 int compile_result = Compile_function(buf, node);
1459 ASSERT_EQ(compile_result, 0);
1460 Buffer_make_executable(buf);
1461 uword result = Testing_execute_expr(buf);
1462 ASSERT_EQ_FMT(Object_true(), result, "0x%lx");
1463 AST_heap_free(node);
1464 PASS();
1465}
1466
1467TEST compile_binary_eq_with_different_address_returns_false(Buffer *buf) {
1468 ASTNode *node = new_binary_call("=", AST_new_integer(5), AST_new_integer(4));
1469 int compile_result = Compile_function(buf, node);
1470 ASSERT_EQ(compile_result, 0);
1471 Buffer_make_executable(buf);
1472 uword result = Testing_execute_expr(buf);
1473 ASSERT_EQ_FMT(Object_false(), result, "0x%lx");
1474 AST_heap_free(node);
1475 PASS();
1476}
1477
1478TEST compile_binary_lt_with_left_less_than_right_returns_true(Buffer *buf) {
1479 ASTNode *node = new_binary_call("<", AST_new_integer(-5), AST_new_integer(5));
1480 int compile_result = Compile_function(buf, node);
1481 ASSERT_EQ(compile_result, 0);
1482 Buffer_make_executable(buf);
1483 uword result = Testing_execute_expr(buf);
1484 ASSERT_EQ_FMT(Object_true(), result, "0x%lx");
1485 AST_heap_free(node);
1486 PASS();
1487}
1488
1489TEST compile_binary_lt_with_left_equal_to_right_returns_false(Buffer *buf) {
1490 ASTNode *node = new_binary_call("<", AST_new_integer(5), AST_new_integer(5));
1491 int compile_result = Compile_function(buf, node);
1492 ASSERT_EQ(compile_result, 0);
1493 Buffer_make_executable(buf);
1494 uword result = Testing_execute_expr(buf);
1495 ASSERT_EQ_FMT(Object_false(), result, "0x%lx");
1496 AST_heap_free(node);
1497 PASS();
1498}
1499
1500TEST compile_binary_lt_with_left_greater_than_right_returns_false(Buffer *buf) {
1501 ASTNode *node = new_binary_call("<", AST_new_integer(6), AST_new_integer(5));
1502 int compile_result = Compile_function(buf, node);
1503 ASSERT_EQ(compile_result, 0);
1504 Buffer_make_executable(buf);
1505 uword result = Testing_execute_expr(buf);
1506 ASSERT_EQ_FMT(Object_false(), result, "0x%lx");
1507 AST_heap_free(node);
1508 PASS();
1509}
1510
1511SUITE(object_tests) {
1512 RUN_TEST(encode_positive_integer);
1513 RUN_TEST(encode_negative_integer);
1514 RUN_TEST(encode_char);
1515 RUN_TEST(decode_char);
1516 RUN_TEST(encode_bool);
1517 RUN_TEST(decode_bool);
1518 RUN_TEST(address);
1519}
1520
1521SUITE(ast_tests) {
1522 RUN_TEST(ast_new_pair);
1523 RUN_TEST(ast_pair_car_returns_car);
1524 RUN_TEST(ast_pair_cdr_returns_cdr);
1525 RUN_TEST(ast_new_symbol);
1526}
1527
1528SUITE(buffer_tests) {
1529 RUN_BUFFER_TEST(buffer_write8_increases_length);
1530 RUN_TEST(buffer_write8_expands_buffer);
1531 RUN_TEST(buffer_write32_expands_buffer);
1532 RUN_BUFFER_TEST(buffer_write32_writes_little_endian);
1533}
1534
1535SUITE(compiler_tests) {
1536 RUN_BUFFER_TEST(compile_positive_integer);
1537 RUN_BUFFER_TEST(compile_negative_integer);
1538 RUN_BUFFER_TEST(compile_char);
1539 RUN_BUFFER_TEST(compile_true);
1540 RUN_BUFFER_TEST(compile_false);
1541 RUN_BUFFER_TEST(compile_nil);
1542 RUN_BUFFER_TEST(compile_unary_add1);
1543 RUN_BUFFER_TEST(compile_unary_add1_nested);
1544 RUN_BUFFER_TEST(compile_unary_sub1);
1545 RUN_BUFFER_TEST(compile_unary_integer_to_char);
1546 RUN_BUFFER_TEST(compile_unary_char_to_integer);
1547 RUN_BUFFER_TEST(compile_unary_nilp_with_nil_returns_true);
1548 RUN_BUFFER_TEST(compile_unary_nilp_with_non_nil_returns_false);
1549 RUN_BUFFER_TEST(compile_unary_zerop_with_zero_returns_true);
1550 RUN_BUFFER_TEST(compile_unary_zerop_with_non_zero_returns_false);
1551 RUN_BUFFER_TEST(compile_unary_not_with_false_returns_true);
1552 RUN_BUFFER_TEST(compile_unary_not_with_non_false_returns_false);
1553 RUN_BUFFER_TEST(compile_unary_integerp_with_integer_returns_true);
1554 RUN_BUFFER_TEST(compile_unary_integerp_with_non_integer_returns_false);
1555 RUN_BUFFER_TEST(compile_unary_booleanp_with_boolean_returns_true);
1556 RUN_BUFFER_TEST(compile_unary_booleanp_with_non_boolean_returns_false);
1557 RUN_BUFFER_TEST(compile_binary_plus);
1558 RUN_BUFFER_TEST(compile_binary_plus_nested);
1559 RUN_BUFFER_TEST(compile_binary_minus);
1560 RUN_BUFFER_TEST(compile_binary_minus_nested);
1561 RUN_BUFFER_TEST(compile_binary_mul);
1562 RUN_BUFFER_TEST(compile_binary_mul_nested);
1563 RUN_BUFFER_TEST(compile_binary_eq_with_same_address_returns_true);
1564 RUN_BUFFER_TEST(compile_binary_eq_with_different_address_returns_false);
1565 RUN_BUFFER_TEST(compile_binary_lt_with_left_less_than_right_returns_true);
1566 RUN_BUFFER_TEST(compile_binary_lt_with_left_equal_to_right_returns_false);
1567 RUN_BUFFER_TEST(compile_binary_lt_with_left_greater_than_right_returns_false);
1568}
1569
1570// End Tests
1571
1572GREATEST_MAIN_DEFS();
1573
1574int main(int argc, char **argv) {
1575 GREATEST_MAIN_BEGIN();
1576 RUN_SUITE(object_tests);
1577 RUN_SUITE(ast_tests);
1578 RUN_SUITE(buffer_tests);
1579 RUN_SUITE(compiler_tests);
1580 GREATEST_MAIN_END();
1581}