urbach.dev / q
馃尡 A minimal programming language and compiler. git.urbach.dev/cli/q
high-performance programming-language compiler
Star
Fork 0
Watch
q docs source.md
6.2 kB
Markdown
at main

Source #

The source code structure uses a flat layout without nesting:

  • arm - arm64 architecture
  • asm - Generic assembler
  • ast - Abstract syntax tree
  • cli - Command line interface
  • codegen - SSA to assembly code generation
  • compiler - Compiler frontend
  • config - Build configuration
  • core - Defines Function and compiles tokens to SSA
  • cpu - Types to represent a generic CPU
  • data - Data container that can reuse existing data
  • dll - DLL support for Windows systems
  • elf - ELF format for Linux executables
  • errors - Error handling that reports lines and columns
  • exe - Generic executable format to calculate section offsets
  • expression - Expression parser generating trees
  • fs - File system access
  • global - Global variables like the working directory
  • linker - Frontend for generating executable files
  • linter - Linter that catches common mistakes
  • macho - Mach-O format for Mac executables
  • memfile - Memory backed file descriptors
  • optimizer - Code optimization
  • pe - PE format for Windows executables
  • resolver - Type token resolver
  • scanner - Scanner that parses top-level instructions
  • set - Generic set implementation
  • ssa - Static single assignment types
  • token - Tokenizer
  • types - Type system
  • verbose - Verbose output
  • x86 - x86-64 architecture

Flow #

The typical flow for a build command is the following:

  1. main
  2. cli.Exec
  3. compiler.Compile
  4. scanner.Scan
  5. core.Compile
  6. linker.Write

Tools #

Static Single Assignment #

The SSA IR follows a simple rule: every value is assigned exactly once.

Basic Blocks #

Every function has a list of basic blocks. Basic blocks store values in the order they appear in the original code.

Instructions #

Instructions are no different from values. The calculation 1 + 2 is represented as 3 values using 2 int constants and 1 binary operation:

t0 = 1
t1 = 2
t2 = t0 + t1

All of these are considered values even in cases where the type of the value is void such as in procedural function calls with side effects.

Pointers #

There are no IDs or indices, therefore values don't know their position in a basic block.

Values reference other values by including a pointer to them.

Executable formats #

Linux (ELF) #

Basic structure #

  1. ELF header [0x00 : 0x40]
  2. Program headers
  3. String table
  4. Section headers
  5. Padding
  6. Executable code
  7. Padding
  8. Read-only data

Entry point #

The executables are compiled as position-independent executables (PIE). Therefore the entry point is defined as a file offset instead of a static virtual address.

Padding #

Permissions like read, write and execute can only be applied to an entire page in memory. To ensure that execution permissions are properly applied, the code section and the data section are aligned on page boundaries.

Mac (Mach-O) #

Notes #

  • The start of the file must be loaded in some segment.
  • The start of the file must be marked as readable + executable.
  • Load command size must be divisible by 8.
  • Segments must be page-aligned in the file.

Windows (PE) #

Notes #

Unlike Linux, Windows does not ignore zero-length sections at the end of a file and will fail loading them because they don't exist within the file. Adding a single byte to the section can fix this problem, but it's easier to just remove the section header entirely. The solution used here is to guarantee that the data section is never empty by always importing a few core functions from "kernel32.dll".

DLL function pointers #

The section where the DLL function pointers are stored does not need to be marked as writable. The Windows executable loader resolves the pointers before they are loaded into memory.

The stack must be 16 byte aligned before a DLL function is called.