ts-c-compiler

Multipass portable C lang compiler toolkit with IR code generator including backend, frontend, and optimizer phases. Designed to simple prototyping 16bit toy operating systems and games.

Currently supported architectures:

1. X86 16bit real mode code emitter with floating point X87 coprocessor support

🚧 Warn! The project is unstable so please do not use it on production!

What does it offer? ⭐

1. Reasonable assembly code quality in NASM syntax
2. Simple prototyping boot sector games
3. Designed especially for old-school 16bit computers with Intel 80286 (and newer) CPU and produces only simple ASM instructions
4. Backend / Frontend architecture that allows you to add new backends in TypeScript (especially useful for homebrew FPGA CPU)
5. Peephole optimization of IR code, precompute of constant expressions during compile time and optimizer phase
6. Slow compile times - feel the vibe of old computing

What works? 🔥

• Multi-pass branch optimisation (it uses jmp rel8 instructions when offset is smaller than rel16)
• Local / Global variables
• float / double operations using X87 stack-based registers
• Advanced types struct, union, enum
• Loops and if conditions while, if, do while, for, break, continue
• Basic preprocessor with #ifdef, #define, #include
• goto jumps
• VA lists va_arg, va_end, va_start
• In expression compound statements
• Ternary operators a > 1 ? 1 : 2
• Arithmetic operations a + b, a * b, a / b, etc.
• Binary operations a | b, a & b etc.
• Logic operations that are casted to numbers a && 2 || 2 > 1
• Assign operators a += 1, a <<= b, etc.
• Designated and C89 initializers
• Dynamic stack alloc using alloca
• Type aliasing typedef
• Variable and function pointers
• RVO optimization of larger structs
• Peephole optimization of expensive instruction like a *= 2 -> a <<= 1
• Constant expressions eval optimizations a = 2 * 4 -> a = 8
• Constant branch optimization for loops and ifs for (;;) {} -> L1: jmp L1

What does not work? 🚧

• Bitfields
• Multiple files support
• Linker

Online editor

Available at: https://mati365.github.io/ts-c-compiler

Install

yarn add @ts-cc/cli @ts-cc/machine

Usage: ts-c [options] <source>
Arguments:
  source                       Relative or absolute path to source file
Options:
  -b, --binary                 Emits binary stdout
  -o, --output <string>        Relative path to your output binary
  -d, --debug                  Print AST tree and assembly output
  -ps, --print-assembly        Print assembly output
  -pjs, --print-jump-assembly  Print assembly output with jmps
  -bs, --bootsector            Generate 512B bootsector output. Remember to
                               have main entrypoint.
  -h, --help                   display help for command

Usage

Example main.c file:

#include <stdio.h>
#include <kernel/textmode.h>
int main() {
  int rows = 8, coef = 1, space, i, j;
  kernel_screen_clear();
  for (i = 0; i < rows; i++) {
    for (space = 1; space <= rows - i; space++) {
      printf("  ");
    }
    for (j = 0; j <= i; j++) {
      if (j == 0 || i == 0) {
        coef = 1;
      } else {
        coef = coef * (i - j + 1) / j;
      }
      printf("%4d", coef);
    }
    printf("\n");
  }
  for (;;) {}
  return 0;
}

Compile main.c and boot-it in 16bit VM available in web-browser:

npx ts-c main.c --bootsector --binary | APP_PORT=3002 npx run-x86_16-vm

Compile main.c to x86-16 binary:

npx ts-c ./main.c -o ./output.bin

Print assembly output without generate binary file:

npx ts-c ./main.c -ps
0x000000                      55                            push bp
0x000001                      89 e5                         mov bp, sp
0x000003                      83 ec 02                      sub sp, 0x2
0x000006                      c7 46 fe 04 00                mov word [bp-2], 0x4
0x00000b                      89 ec                         mov sp, bp
0x00000d                      5d                            pop bp
0x00000e                      c3                            ret

Examples

Simple macros with constant expressions optimization

#include "file.h"
#define PRINT_SUM 1
#define A 1
#define B 1
#define esum(...) sum(__VA_ARGS__)
#define internal_fn(name) internal_ ## name
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define sum(a,b) (min(a, b) + max(a, b))
enum {
  TEN = 10,
  FIVE = 5
};
#ifdef PRINT_SUM
  #if A + B == 12 || A - B == 0
    int main() {
      int k = esum(TEN, FIVE + 1);
    }
  #endif
#elifdef ABC
  int s = 2;
#elifndef DBEF
  struct Vec2 { int x, y; };
  struct Vec2 sum_vec(int k, struct Vec2 vec, int x) {
    struct Vec2 result = {
      .x = k + vec.x * vec.y - x,
      .y = vec.y * 3
    };
    return result;
  }
  int main() {
    struct Vec2 vec = { .x = 4, .y = 3 };
    struct Vec2 k = sum_vec(2, vec, 5);
    int d = k.x + k.y;
    asm("xchg dx, dx");
  }
#else
  int internal_fn(main)() {
    int k = 2;
  }
#endif

Floating point operations

float calculate_pi(int nbofterms) {
  float x = 0.0;
  for (int n = 0; n < nbofterms; n++) {
    float z = 1.0 / (2 * n + 1);
    if (n % 2 == 1) {
      z *= -1;
    }
    x = (x + z);
  }
  return 4 * x;
}
int main() {
  float pi = calculate_pi(500);
  int trunc_pi = pi;
  asm("xchg bx, bx");
  return 0;
}

Advanced structures with recursive calls

int fibbonacci(int n)
{
  if (n == 1)
    return 0;
  if (n <= 3)
    return 1;
  return fibbonacci(n-1) + fibbonacci(n-2);
}
struct Vec2 { int x, y; };
struct Vec2 sum_vec(int k, struct Vec2 vec, int x) {
  struct Vec2 result = {
    .x = k + vec.x * vec.y - x,
    .y = vec.y * 3 + (fibbonacci(10) * 2 + fibbonacci(10) * 15)
  };
  return result;
}
int main() {
  struct Vec2 vec = { .x = 4, .y = 3 };
  struct Vec2 k = sum_vec(2, vec, 5);
  int d = k.x + k.y;
  asm("xchg dx, dx");
}

Compound statements

GCC Docs

void main() {
  int dupa = (({
                int c = 3, k, d;
                k = 16;
                d = 20;
                c + k + d * 4;
              }) *
              2 * ({
                int k = 15;
                k * 2;
              })) *
             ({ 5 + 2; });
  asm("xchg dx, dx");
}

Advanced array / pointers / ternary expressions

  int strlen(const char* str) {
    for (int i = 0;;++i) {
      if (*(str + i) == 0) {
        return i;
      }
    }
    return -1;
  }
  typedef struct Box {
    int x, y;
    const char* str;
  } box_t;
  int max (int a, int b) {
    return a > b ? a : b;
  }
  void main() {
    box_t vec[] = { { .y = 5 }, { .x = 4, .str = "ABC" } };
    vec[0].str = "Hello world!";
    vec[0].y++;
    vec[1].x += 3;
    int k = vec[1].x * vec[0].y + strlen(vec[0].str);
    int d = max(666, k * 20);
    asm("xchg dx, dx");
  }

Dynamic alloca

  #include <alloca.h>
  int main() {
    int k = 10;
    char* buffer = alloca(k);
    return 0;
  }

Simple function calls with peephole optimization

  #define int16_t int
  int16_t sum(int x) {
    return x * 2 / 4;
  }
  int16_t main() {
    return sum(3);
  }

Function pointers

  int sum(int x, int y) {
    return x + y * 2;
  }
  int addPtr(int (*functionPtr)(int, int)) {
    return (*functionPtr)(2, 3);
  }
  int main() {
    int sum = addPtr(sum);
  }

Bubble sort

void bubble_sort(int a[], int n) {
  int i = 0, j = 0, tmp;
  for (i = 0; i < n; i++) {   // loop n times - 1 per element
    for (j = 0; j < n - i - 1; j++) { // last i elements are sorted already
      if (a[j] > a[j + 1]) {  // swop if order is broken
        tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
}

Printing BIOS charset

Printing BIOS charset:

  const char* VRAM_ADDR = 0xB800;
  const char* KERNEL_INIT_MESSAGES[] = {
    "Tiny kernel!",
    "Charset table:"
  };
  struct Vec2 {
    int x, y;
  };
  struct Vec2 kernel_screen_cursor = {
    .x = 0,
    .y = 0,
  };
  int strlen(const char* str) {
    for (int i = 0;;++i) {
      if (*(str + i) == 0) {
        return i;
      }
    }
    return -1;
  }
  void kernel_screen_clear() {
    asm(
      "mov cx, 0x7d0\n"
      "mov ax, 0xF00\n"
      "mov dx, 0xB800\n"
      "mov es, dx\n"
      "xor di, di\n"
      "rep stosw\n"
    );
  }
  void kernel_print_char_at(int x, int y, char color, char letter) {
    const int offset = (y * 80 + x) * 2;
    asm(
      "mov gs, %[vram]\n"
      "mov dl, %[color]\n"
      "mov dh, %[letter]\n"
      "mov bx, %[offset]\n"
      "mov byte [gs:bx + 1], dl\n"
      "mov byte [gs:bx], dh\n"
      ::
        [vram] "r" (VRAM_ADDR),
        [offset] "m" (offset),
        [letter] "m" (letter),
        [color] "m" (color)
      : "dx", "bx", "gs"
    );
  }
  void kernel_screen_print_at(int x, int y, char color, const char* str) {
    const int len = strlen(str);
    for (int i = 0; i < len; ++i) {
      kernel_print_char_at(x + i, y, color, str[i]);
    }
  }
  void kernel_screen_newline() {
    kernel_screen_cursor.x = 0;
    kernel_screen_cursor.y++;
  }
  void kernel_screen_println(char color, const char* str) {
    kernel_screen_print_at(
      kernel_screen_cursor.x,
      kernel_screen_cursor.y,
      color,
      str
    );
    kernel_screen_newline();
  }
  void main() {
    kernel_screen_clear();
    for (int i = 0; i < 0x2; ++i) {
      kernel_screen_println(0xF, KERNEL_INIT_MESSAGES[i]);
    }
    kernel_screen_newline();
    for (int x = 0; x < 0xFF; ++x) {
      kernel_print_char_at(x, kernel_screen_cursor.y, 0xF, 0x1 + x);
    }
  }

ASM syntax

It’s pretty similar to NASM syntax (including preprocessor), examples:

https://github.com/Mati365/i8086.js/tree/master/packages/x86-assembler/tests/asm

Architecture

Multipass steps

• [x] Frontend (source)

  • Lexer (source)
  • AST creator (source)
  • Type checking (source)
  • IR generation (source)

• [x] Backend (source)

  • X86 arch backend (source)
    • X86 Register linear scan allocation (source)
    • X86 ASM generators (source)

X86 Arch support

• [x] 16bit real mode X86 arch support

  • [x] X86 16bit Multipass Assembler compatible with NASM syntax (source)

    • Preprocessor (source) compatible with NASM that supports:
      • Conditions and definitions: %if, %ifn, %ifdef, %ifndef, %else, %elif, %elifndef, %elifdef, %elifn, %define, %undef
      • Macros: %macro, %define, %imacro
      • Predefined variables: __TIMES__
      • Inline expressions calls: %[__TIMES__]

  • [x] X86 CPU 16bit Intel 8086 virtual machine (source)

    • VGA graphical mode support (source)
    • VGA text mode support (source)

Current progress

• C compiler
  • Frontend
    • Syntax parser
    • Typechecker
    • IR code generator
  • Backend
    • IR optimizer
    • X86-16 Code generator
      • Register allocator
        • Basic allocation using ownership checking
        • Spilling regs and detection lifetime of IR vars
      • Compile math integer instruction
        • Compile *, +, -, /
        • Compile <<, >>
        • Compile xor / and / or / not
      • Compile if stmts
      • Compile loops while {}, do { } while, for (...) {}
      • Compile typedefs
      • Compile pointers
        • Basic pointer access *k = 5
        • Array access k[4]
      • Compile function calls
      • Compile asm tag
        • Basic asm tag without args
        • asm tag with arguments
      • Unions
      • Preprocessor
      • Stdlib
• ASM Compiler
  • NASM syntax instruction compiler matcher with expression eval mov ax, byte [ds:label+bx+12+(1/3)]
  • Instruction prefix support rep movsw
  • Compiler bits/org config [bits 16], [org 0x7C00]
  • Labels support jmp_label:
  • Data define support db, dw, dd, dq, dt
  • EQU, times support
  • Floating point numbers support
  • Preprocessor
    • Basic lang keywords support: %if, %ifn, %ifdef, %ifndef, %else, %elif, %elifndef, %elifdef, %elifn, %define, %undef
    • Macros support: %macro, %define, %imacro
    • Predefined macros like __TIMES__
    • Inline expressions calls %[__TIMES__]
  • Output logger
    • Basic logger binary blob serializer helpers
    • Diassembler binary view
    • Branch arrows (for jmp, call, jz etc.)
• CPU Emulator
  • Magic breakpoint support xchg bx, bx
  • Interrupts handlers support
  • Basic Intel ~80186 instructions set
  • ALU instructions support
  • FPU Support
    • Assembler
    • Emulator
  • Basic PIT/PIC support
    • PIT
    • PIC
    • IDE
    • PS2
  • Graphics mode
    • Basic canvas graphics driver
    • Text Mode
    • Graphics VGA
    • VGA IO ports bindings
  • BIOS
    • Basic bios interrupt handlers
• App frontend
  • Basic front CSS UI
  • Debugger

Screens

Docs

https://cs.lmu.edu/~ray/notes/ir

https://www.youtube.com/watch?v=yTXCPGAD3SQ

https://books.google.pl/books?id=Lq4yDwAAQBAJ&pg=PA120&lpg=PA120&dq=chain4+mode&source=bl&ots=Eun_wNFE7b&sig=ACfU3U37tSXE7qOZn0AKGeFwaaNLS4nrKg&hl=pl&sa=X&ved=2ahUKEwjlupT5-u_pAhVNxhoKHVfRA7YQ6AEwAnoECAoQAQ#v=onepage&q=chain4%20mode&f=false

https://bellard.org/otcc/otccn.c

https://bellard.org/otcc

https://gist.github.com/nikAizuddin/0e307cac142792dcdeba

http://www.plantation-productions.com/Webster/www.artofasm.com/Windows/HTML/RealArithmetica3.html

https://gist.github.com/mikesmullin/6259449

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt

http://ece425web.groups.et.byu.net/stable/labs/8086Assembly.html

http://dsearls.org/courses/C391OrgSys/IntelAL/8086_instruction_set.html

https://pdos.csail.mit.edu/6.828/2008/readings/i386/s17_02.htm

https://xem.github.io/minix86/manual/intel-x86-and-64-manual-vol1/o_7281d5ea06a5b67a-194.html

https://johnloomis.org/ece314/notes/fpu/fpu.pdf

https://www.felixcloutier.com/x86/index.html

https://c9x.me/x86/html/file_module_x86_id_87.html

http://www.osdever.net/FreeVGA/vga/graphreg.htm#06

http://www.osdever.net/FreeVGA/vga/vgamem.htm

http://www.osdever.net/FreeVGA/home.htm

License

The MIT License (MIT)
Copyright (c) 2023/2024 Mateusz Bagiński

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.