parse.c (17644B)
1 #define _GNU_SOURCE 2 #define DLIB_IMPLEMENTATION 3 #include "dlib.h" 4 5 #include "lexer.h" 6 7 #include "backend.h" 8 #include "phi.c" 9 #include "ir_backend.c" 10 #include "x86_64-codegen.c" 11 12 char *input_source_2 = 13 /* "extern $printf(ptr, i32) -> i32\n" */ 14 "extern $printf\n" 15 "$foo() -> i32 {\n" 16 "#0:\n" 17 " %0 =i32 0\n" 18 " jump #1\n" 19 "#1:\n" 20 " %1 =i32 phi [(#0 %0) (#2 %5)]\n" 21 " %2 =i32 phi [(#0 %0) (#2 %4)]\n" 22 " %3 =i8 %1 <i32 11\n" 23 " branch %3 #2 #3\n" 24 "#2:\n" 25 " %4 =i32 call $printf (ptr \"%i\\n\", i32 %1)\n" 26 " %5 =i32 %1 +i32 1\n" 27 " jump #1\n" 28 "#3:\n" 29 " return i32 %2\n" 30 "}" 31 32 /* char *input_source = */ 33 "$main() -> i32 {\n" 34 "#0:\n" 35 " %0 =i32 call $foo()\n" 36 " return i32 %0\n" 37 "}"; 38 39 bool 40 is_binary_operator(Token t) 41 { 42 Token_kind k = t.kind; 43 return k == '+' || 44 k == '<'; 45 } 46 47 Ir_binop 48 ir_binop_from_token(Token t) 49 { 50 if (t.kind == '+') return OP_ADD; 51 else if (t.kind == '<') return OP_LT; 52 unreachable("binop token"); 53 } 54 55 bool 56 parse_ir_extern(Ir_program *out_prog, Lexer *lexer) 57 { 58 skip_whitespace(lexer); 59 Token peek = peek_token(lexer); 60 if (peek.kind != T_CONST_SYMBOL && peek.kind != T_VARIABLE_SYMBOL && peek.kind != T_FUNCTION_SYMBOL) { 61 print_loc(peek.loc); 62 fprintf(stderr, "Error: Expected a constant, variable, or function name following extern\n"); 63 return false; 64 } 65 next_token(lexer); 66 da_append(&out_prog->externs, ((Ir_extern) { .symbol = lexer->last_tok.sv })); 67 if (!expect_end_statement(lexer)) { 68 return false; 69 } 70 return true; 71 } 72 73 bool 74 parse_ir_type(Ir_type *out_type, Lexer *lexer) 75 { 76 Token t = next_token(lexer); 77 if (t.kind == T_I8) { 78 *out_type = TYPE_I8; 79 } else if (t.kind == T_I16) { 80 *out_type = TYPE_I16; 81 } else if (t.kind == T_I32) { 82 *out_type = TYPE_I32; 83 } else if (t.kind == T_I64) { 84 *out_type = TYPE_I64; 85 } else if (t.kind == T_PTR) { 86 *out_type = TYPE_PTR; 87 } else if (t.kind == T_VOID) { 88 *out_type = TYPE_VOID; 89 } else { 90 print_loc(t.loc); 91 fprintf(stderr, "Error: expected type\n"); 92 return false; 93 } 94 return true; 95 } 96 97 bool 98 parse_ir_value(Ir_arg *out_arg, Lexer *lexer) 99 { 100 Token t = next_token(lexer); 101 if (t.kind == T_TEMP) { 102 *out_arg = (Ir_arg) { 103 .kind = ARG_TEMP_STORAGE, 104 .type = TYPE_UNKNOWN, 105 .temp_id = t.i64, 106 }; 107 } else if (t.kind == T_NUMBER) { 108 *out_arg = (Ir_arg) { 109 .kind = ARG_INT_LITERAL, 110 .type = TYPE_UNKNOWN, 111 .temp_id = t.i64, 112 }; 113 } else if (t.kind == T_DQ_STRING) { 114 *out_arg = (Ir_arg) { 115 .kind = ARG_CSTRING_LITERAL, 116 .type = TYPE_PTR, 117 .sv = t.sv, 118 }; 119 } else if (t.kind == T_VARIABLE_SYMBOL) { 120 *out_arg = (Ir_arg) { 121 .kind = ARG_STATIC_VARIABLE, 122 .type = TYPE_PTR, 123 .name = t.sv, 124 }; 125 } else { 126 print_loc(t.loc); 127 fprintf(stderr, "Error: expected value\n"); 128 debug_print_token(t); 129 return false; 130 } 131 return true; 132 } 133 134 bool 135 parse_ir_call(Ir_call_args *out_call_args, Lexer *lexer) 136 { 137 if (!expect_token_kind(lexer, T_FUNCTION_SYMBOL)) { 138 return false; 139 } 140 out_call_args->name = lexer->last_tok.sv; 141 skip_whitespace(lexer); 142 if (!expect_token_kind(lexer, '(')) { 143 return false; 144 } 145 skip_whitespace(lexer); 146 while (peek_token(lexer).kind != ')') { 147 Ir_type type = {0}; 148 Ir_arg arg = {0}; 149 if (!parse_ir_type(&type, lexer)) { 150 return false; 151 } 152 skip_whitespace(lexer); 153 if (!parse_ir_value(&arg, lexer)) { 154 return false; 155 } 156 skip_whitespace(lexer); 157 arg.type = type; 158 da_append(&out_call_args->args, arg); 159 skip_whitespace(lexer); 160 if (peek_token(lexer).kind != ',') { 161 break; 162 } 163 next_token(lexer); 164 skip_whitespace(lexer); 165 } 166 if (!expect_token_kind(lexer, ')')) { 167 return false; 168 } 169 return true; 170 } 171 172 bool 173 parse_ir_syscall(Ir_syscall_args *out_syscall_args, Lexer *lexer) 174 { 175 if (!parse_ir_value(&out_syscall_args->syscall, lexer)) { 176 return false; 177 } 178 skip_whitespace(lexer); 179 if (!expect_token_kind(lexer, '(')) { 180 return false; 181 } 182 skip_whitespace(lexer); 183 while (peek_token(lexer).kind != ')') { 184 Ir_type type = {0}; 185 Ir_arg arg = {0}; 186 if (!parse_ir_type(&type, lexer)) { 187 return false; 188 } 189 skip_whitespace(lexer); 190 if (!parse_ir_value(&arg, lexer)) { 191 return false; 192 } 193 skip_whitespace(lexer); 194 arg.type = type; 195 da_append(&out_syscall_args->args, arg); 196 skip_whitespace(lexer); 197 if (peek_token(lexer).kind != ',') { 198 break; 199 } 200 next_token(lexer); 201 skip_whitespace(lexer); 202 } 203 if (!expect_token_kind(lexer, ')')) { 204 return false; 205 } 206 return true; 207 } 208 209 bool 210 parse_ir_phi_list(Phi_entry_list *out_phi_list, Lexer *lexer) 211 { 212 if (!expect_token_kind(lexer, '[')) { 213 return false; 214 } 215 skip_whitespace(lexer); 216 do { 217 Phi_entry phi = {0}; 218 if (!expect_token_kind(lexer, '(')) { 219 return false; 220 } 221 skip_whitespace(lexer); 222 if (!expect_token_kind(lexer, T_LABEL)) { 223 return false; 224 } 225 phi.label.sv = lexer->last_tok.sv; 226 skip_whitespace(lexer); 227 if (!expect_token_kind(lexer, T_TEMP)) { 228 return false; 229 } 230 phi.temp_id = lexer->last_tok.i64; 231 skip_whitespace(lexer); 232 if (!expect_token_kind(lexer, ')')) { 233 return false; 234 } 235 da_append(out_phi_list, phi); 236 skip_whitespace(lexer); 237 } while (peek_token(lexer).kind != ']'); 238 next_token(lexer); 239 return true; 240 } 241 242 bool 243 parse_ir_assignment(Ir *out_ins, Lexer *lexer) 244 { 245 Ir_arg result = { .kind = ARG_TEMP_STORAGE, .temp_id = lexer->last_tok.i64 }; 246 Ir_type type = {0}; 247 Ir_arg arg1 = {0}; 248 Ir_arg arg2 = {0}; 249 skip_whitespace(lexer); 250 if (!expect_token_kind(lexer, '=')) { 251 return false; 252 } 253 skip_whitespace(lexer); 254 if (!parse_ir_type(&result.type, lexer)) { 255 return false; 256 } 257 skip_whitespace(lexer); 258 259 Token t = peek_token(lexer); 260 if (t.kind == T_LOAD) { 261 next_token(lexer); 262 skip_whitespace(lexer); 263 Ir_type load_type = {0}; 264 Ir_arg load_loc = {0}; 265 if (!parse_ir_type(&load_type, lexer)) { 266 return false; 267 } 268 skip_whitespace(lexer); 269 if (!parse_ir_value(&load_loc, lexer)) { 270 return false; 271 } 272 *out_ins = (Ir) { 273 .kind = IR_LOAD, 274 .result = result, 275 .load = { 276 .type = load_type, 277 .loc = load_loc, 278 }, 279 }; 280 } else if (t.kind == T_STORE) { 281 todo("parse store"); 282 } else if (t.kind == T_CALL) { 283 next_token(lexer); 284 skip_whitespace(lexer); 285 Ir_call_args call_args = {0}; 286 if (!parse_ir_call(&call_args, lexer)) { 287 return false; 288 } 289 *out_ins = (Ir) { 290 .kind = IR_CALL, 291 .result = result, 292 .call = call_args, 293 }; 294 } else if (t.kind == T_SYSCALL) { 295 next_token(lexer); 296 skip_whitespace(lexer); 297 Ir_syscall_args syscall_args = {0}; 298 if (!parse_ir_syscall(&syscall_args, lexer)) { 299 return false; 300 } 301 *out_ins = (Ir) { 302 .kind = IR_SYSCALL, 303 .result = result, 304 .syscall = syscall_args, 305 }; 306 } else if (t.kind == T_PHI) { 307 next_token(lexer); 308 skip_whitespace(lexer); 309 Phi_entry_list phi_list = {0}; 310 if (!parse_ir_phi_list(&phi_list, lexer)) { 311 return false; 312 } 313 *out_ins = (Ir) { 314 .kind = IR_PHI, 315 .result = result, 316 .phi_list = phi_list, 317 }; 318 } else { 319 if (!parse_ir_value(&arg1, lexer)) { 320 return false; 321 } 322 next_token_if_kind(lexer, T_WHITESPACE); 323 t = peek_token(lexer); 324 if (is_binary_operator(t)) { 325 next_token(lexer); 326 skip_whitespace(lexer); 327 if (!parse_ir_type(&type, lexer)) { 328 return false; 329 } 330 skip_whitespace(lexer); 331 if (!parse_ir_value(&arg2, lexer)) { 332 return false; 333 } 334 arg1.type = type; 335 arg2.type = type; 336 *out_ins = (Ir) { 337 .kind = IR_BINOP, 338 .result = result, 339 .binop = { 340 .op = ir_binop_from_token(t), 341 .op_type = type, 342 .left = arg1, 343 .right = arg2, 344 }, 345 }; 346 } else { 347 arg1.type = type; 348 *out_ins = (Ir) { 349 .kind = IR_ASSIGN, 350 .result = result, 351 .assign = arg1, 352 }; 353 } 354 } 355 return true; 356 } 357 358 bool 359 parse_ir_return(Ir *out_ins, Lexer *lexer) 360 { 361 Ir_arg value = {0}; 362 363 Ir_type type = {0}; 364 skip_whitespace(lexer); 365 if (!parse_ir_type(&type, lexer)) { 366 return false; 367 } 368 369 skip_whitespace(lexer); 370 if (!parse_ir_value(&value, lexer)) { 371 return false; 372 } 373 374 value.type = type; 375 *out_ins = (Ir) { 376 .kind = IR_RETURN, 377 .ret = value, 378 }; 379 return true; 380 } 381 382 bool 383 parse_ir_jump(Ir *out_ins, Lexer *lexer) 384 { 385 skip_whitespace(lexer); 386 if (!expect_token_kind(lexer, T_LABEL)) { 387 return false; 388 } 389 390 *out_ins = (Ir) { 391 .kind = IR_JUMP, 392 .jump = { .label = { .sv = lexer->last_tok.sv }}, 393 }; 394 return true; 395 } 396 397 bool 398 parse_ir_branch(Ir *out_ins, Lexer *lexer) 399 { 400 Ir_arg cond = {0}; 401 skip_whitespace(lexer); 402 if (!parse_ir_value(&cond, lexer)) { 403 return false; 404 } 405 skip_whitespace(lexer); 406 if (!expect_token_kind(lexer, T_LABEL)) { 407 return false; 408 } 409 Sv true_label = lexer->last_tok.sv; 410 skip_whitespace(lexer); 411 if (!expect_token_kind(lexer, T_LABEL)) { 412 return false; 413 } 414 Sv false_label = lexer->last_tok.sv; 415 *out_ins = (Ir) { 416 .kind = IR_BRANCH, 417 .branch = { 418 .cond = cond, 419 .true_label = { 420 .sv = true_label, 421 }, 422 .false_label = { 423 .sv = false_label, 424 }, 425 }, 426 }; 427 return true; 428 } 429 430 bool 431 parse_ir_basic_block(Ir_block *out_block, Lexer *lexer) 432 { 433 bool found_end_statement = false; 434 Ir ins = {0}; 435 while (!found_end_statement) { 436 Token t = next_token(lexer); 437 if (t.kind == T_TEMP) { 438 if (!parse_ir_assignment(&ins, lexer)) { 439 return false; 440 } 441 } else if (t.kind == T_RETURN) { 442 if (!parse_ir_return(&ins, lexer)) { 443 return false; 444 } 445 found_end_statement = true; 446 } else if (t.kind == T_JUMP) { 447 if (!parse_ir_jump(&ins, lexer)) { 448 return false; 449 } 450 found_end_statement = true; 451 } else if (t.kind == T_BRANCH) { 452 if (!parse_ir_branch(&ins, lexer)) { 453 return false; 454 } 455 found_end_statement = true; 456 } else { 457 Sb error = {0}; 458 sb_append_loc(&error, t.loc); 459 sb_printf(&error, "Error: invalid token "); 460 sb_append_token_kind(&error, t.kind); 461 da_append(&error, '\n'); 462 sb_write(2, error); 463 unreachable("statement"); 464 } 465 da_append(out_block, ins); 466 ins = (Ir) {0}; 467 if (!expect_end_statement(lexer)) { 468 return false; 469 } 470 } 471 return true; 472 } 473 474 bool 475 parse_ir_function_body(Ir_function *out_func, Lexer *lexer) 476 { 477 Ir_block block; 478 if (!expect_token_kind(lexer, '{')) { 479 return false; 480 } 481 skip_whitespace(lexer); 482 483 while (peek_token(lexer).kind != '}') { 484 block = (Ir_block) {0}; 485 if (!expect_token_kind(lexer, T_LABEL)) { 486 return false; 487 } 488 da_append(&out_func->labels, lexer->last_tok.sv); 489 skip_whitespace(lexer); 490 if (!expect_token_kind(lexer, ':')) { 491 return false; 492 } 493 if (!expect_end_statement(lexer)) { 494 return false; 495 } 496 if (!parse_ir_basic_block(&block, lexer)) { 497 return false; 498 } 499 da_append(&out_func->body, block); 500 } 501 if (!expect_token_kind(lexer, '}')) { 502 return false; 503 } 504 return true; 505 } 506 507 bool 508 parse_ir_function(Ir_program *out_prog, Lexer *lexer) 509 { 510 Ir_function func = {.name = lexer->last_tok.sv}; 511 512 skip_whitespace(lexer); 513 if (!expect_token_kind(lexer, '(')) { 514 return false; 515 } 516 skip_whitespace(lexer); 517 if (peek_token(lexer).kind != ')') { 518 for (;;) { 519 Ir_type type = {0}; 520 if (!parse_ir_type(&type, lexer)) { 521 return false; 522 } 523 da_append(&func.argument_types, type); 524 skip_whitespace(lexer); 525 if (peek_token(lexer).kind != ',') { 526 break; 527 } 528 next_token(lexer); 529 skip_whitespace(lexer); 530 } 531 } 532 if (!expect_token_kind(lexer, ')')) { 533 return false; 534 } 535 skip_whitespace(lexer); 536 if (!expect_token_kind(lexer, T_ARROW)) { 537 return false; 538 } 539 skip_whitespace(lexer); 540 if (!parse_ir_type(&func.return_type, lexer)) { 541 return false; 542 } 543 skip_whitespace(lexer); 544 if (!parse_ir_function_body(&func, lexer)) { 545 return false; 546 } 547 da_append(&out_prog->functions, func); 548 549 return true; 550 } 551 552 bool 553 parse_ir_const(Ir_program *out_prog, Lexer *lexer) 554 { 555 Ir_static_data const_ = { .name = lexer->last_tok.sv }; 556 557 skip_whitespace(lexer); 558 if (!expect_token_kind(lexer, '=')) { 559 return false; 560 } 561 skip_whitespace(lexer); 562 if (!parse_ir_type(&const_.type, lexer)) { 563 return false; 564 } 565 skip_whitespace(lexer); 566 if (!parse_ir_value(&const_.default_value, lexer)) { 567 return false; 568 } 569 if (const_.default_value.kind == ARG_TEMP_STORAGE) { 570 fprintf(stderr, "Error: Cannot assign a const to a temporary\n"); 571 return false; 572 } 573 da_append(&out_prog->const_data, const_); 574 return true; 575 } 576 577 bool 578 parse_ir_variable(Ir_program *out_prog, Lexer *lexer) 579 { 580 Ir_static_data var = { .name = lexer->last_tok.sv }; 581 582 skip_whitespace(lexer); 583 if (!expect_token_kind(lexer, '=')) { 584 return false; 585 } 586 skip_whitespace(lexer); 587 if (!parse_ir_type(&var.type, lexer)) { 588 return false; 589 } 590 skip_whitespace(lexer); 591 if (!parse_ir_value(&var.default_value, lexer)) { 592 return false; 593 } 594 if (var.default_value.kind == ARG_TEMP_STORAGE) { 595 fprintf(stderr, "Error: Cannot assign a static variable to a temporary\n"); 596 return false; 597 } 598 da_append(&out_prog->variable_data, var); 599 return true; 600 } 601 602 bool 603 parse_ir_top(Ir_program *out_prog, Lexer *lexer) 604 { 605 while (peek_token(lexer).kind != T_EOF) { 606 Token t = next_token(lexer); 607 if (t.kind == T_EXTERN) { 608 if (!parse_ir_extern(out_prog, lexer)) { 609 return false; 610 } 611 } else if (t.kind == T_CONST_SYMBOL) { 612 if (!parse_ir_const(out_prog, lexer)) { 613 return false; 614 } 615 } else if (t.kind == T_VARIABLE_SYMBOL) { 616 if (!parse_ir_variable(out_prog, lexer)) { 617 return false; 618 } 619 } else if (t.kind == T_FUNCTION_SYMBOL) { 620 if (!parse_ir_function(out_prog, lexer)) { 621 return false; 622 } 623 } else { 624 Sb error = {0}; 625 sb_append_loc(&error, t.loc); 626 sb_printf(&error, "Error: Invalid top level token "); 627 sb_append_token_kind(&error, t.kind); 628 da_append(&error, '\n'); 629 sb_write(2, error); 630 return false; 631 } 632 skip_whitespace(lexer); 633 } 634 return true; 635 } 636 637 bool 638 parse_ir_cstr(const char *in_cstr, Ir_program *out_prog) 639 { 640 Sv input = sv_from_cstr(in_cstr); 641 Lexer lexer = {.source = input, .current_loc = {.filename = sv_literal("(cstr)"), .line = 1, .column = 1}}; 642 skip_whitespace(&lexer); 643 return parse_ir_top(out_prog, &lexer); 644 } 645 646 bool 647 parse_ir_from_file(const char *file_name, Ir_program *out_prog) 648 { 649 Sb input_source = {0}; 650 if (!sb_read_file(&input_source, file_name)) { 651 return false; 652 } 653 Lexer lexer = {.source = sv_from_sb(input_source), .current_loc = {.filename = sv_from_cstr(file_name), .line = 1, .column = 1}}; 654 return parse_ir_top(out_prog, &lexer); 655 } 656 657 bool 658 resolve_labels(Ir_function *fn) 659 { 660 bool looping; 661 size_t i, j, k, l; 662 Label *target; 663 Ir *ir; 664 if (fn->resolved_labels) { 665 return true; 666 } 667 if (fn->labels.count != fn->body.count) { 668 fprintf(stderr, "Error: Label count (%zu) doesn't match Basic block count (%zu)\n", fn->labels.count, fn->body.count); 669 return false; 670 } 671 for (j = 0; j < fn->body.count; j++) { 672 for (k = 0; k < fn->body.items[j].count; k++) { 673 ir = &fn->body.items[j].items[k]; 674 looping = true; 675 for (l = 0; looping; l++) { 676 if (ir->kind == IR_JUMP) { 677 looping = false; 678 target = &ir->jump.label; 679 } else if (ir->kind == IR_BRANCH) { 680 fprintf(stderr, "Found branch\n"); 681 if (l) { 682 looping = false; 683 target = &ir->branch.false_label; 684 } else { 685 target = &ir->branch.true_label; 686 } 687 } else if (ir->kind == IR_PHI) { 688 if (l < ir->phi_list.count) { 689 target = &ir->phi_list.items[l].label; 690 } else { 691 break; 692 } 693 } else { 694 break; 695 } 696 assert(!target->resolved); 697 for (i = 0; i < fn->labels.count; i++) { 698 if (sv_equal(fn->labels.items[i], target->sv)) { 699 target->id = i; 700 target->resolved = true; 701 break; 702 } 703 } 704 if (i == fn->labels.count) { 705 fprintf(stderr, "Error: Non-existant label: %.*s\n", (int) target->sv.count, target->sv.items); 706 return false; 707 } 708 } 709 } 710 } 711 fn->resolved_labels = true; 712 return true; 713 } 714 715 void 716 usage(FILE *output, const char *program_name) 717 { 718 fprintf(output, "Usage: %s <input file>\n", program_name); 719 } 720 721 int 722 main(int argc, const char * const *argv) 723 { 724 if (!argc) { 725 usage(stderr, "parse"); 726 return 2; 727 } 728 const char *prog_name = pop_arg(argc, argv); 729 if (!argc) { 730 usage(stderr, prog_name); 731 return 1; 732 } 733 const char *input_file_name = pop_arg(argc, argv); 734 bool success = true; 735 size_t i; 736 Ir_program prog = {0}; 737 Sb sb = {0}; 738 if (!parse_ir_from_file(input_file_name, &prog)) { 739 return 1; 740 } 741 742 ir_dump(prog, &sb); 743 sb_write(1, sb); 744 sb.count = 0; 745 746 for (i = 0; i < prog.functions.count; i++) { 747 if (!resolve_labels(&prog.functions.items[i])) { 748 return 1; 749 } 750 if (!remove_phi_nodes(prog.functions.items[i])) { 751 return 1; 752 } 753 } 754 755 ir_dump(prog, &sb); 756 sb_write(1, sb); 757 sb.count = 0; 758 success = x86_64_compile_and_emit(prog, &sb); 759 sb_write(1, sb); 760 761 int out_fd = open("build/parse_output.nasm", O_WRONLY | O_CREAT | O_TRUNC, 0644); 762 if (out_fd < 0) { 763 return 1; 764 } 765 sb_write(out_fd, sb); 766 sb.count = 0; 767 768 return success ? 0 : 1; 769 }