Development of a Bitrout compiler, a programming language for a primitive architecture

Adrian Sebastian Šiška Mentor: Aleš Volčini

1. Quick recap

  • MUHI architecture

1.1. MUHI

00000001111111101. Byte2. Byte1. Address2. AddressOp codeMeta bitInstruction:Registers:bazKEControl unitLELogical unitKE->LEram1-bit registersKE->ramLE->KEPGMProgram memoryPGM->KEram->KEIOI/Oram->IOIO->ram

1.1.1. Instructions

  • 1-bit
    • Nand, Xor
  • 16-bit
    • copy, load

2. Motivation

  • Code optimisation

2.1. Hassle of a bad assembler

3. The Bitrout™ language

  • keywords: fn, var, include, if, else
  • builtins: set, get, x, a, goto

3.1. Example function

fn to_hex(in:4b| out:8b) {
    var check;
    leeq in 9 check;
    is in out[-4..];
    if check {
        add "0" out;
    } else {
        add "a" out;
    }
}

3.2. Function arguments

fn example(a, b:1, c:2b, d:3r | e, f:1, g:4b, h:1r)
                ^    ^     ^  ^
                |    |     |  \_ explicit length
                |    |     \____ bitwise length
                |    \__________ bitwise length reversed
                \_______________ mutability seperator
fn print(string:8b){...}

{
    print "abc";
}
fn print(string:8b){...}

{
    print "c";
    print "b";
    print "a";
}

3.3. Syscalls

  • 2 system calls for I/O

3.3.1. Go-like exceptions

⋮
var E;
syscall1 arg1 E;
set arg2 E;
syscall2 arg3 E;
if E {
    var E2;
    set "Catching exception!" E2;
}

3.4. Limitations

  • No runtime recursion ⇒ differnt runtime and comptime

3.4.1. comptime example

fn ComptimeIncrement(|A){
    var length;
    lenOf A length;

    var T;
    neq length 0 T;
    if T {
        if A[0]{
          is 0 A[0];
          ComptimeIncrement A[1..];
        } else {
            is 1 A[0];
        }
    }
}

3.4.2. runtime equivalent code

fn _inc(|A:1b, Carry:1){
    if Carry {
        is A Carry;
        not A;
    }
}

fn inc(|A) {
    var Carry:1 = 1;
    _inc A Carry;
}

4. Compiler

  1. Lexical analysis
  2. Syntactic analysis
  3. Length deduction
  4. Translation into “branches”
  5. Branch reduction (optional)
  6. Memory acquisition

4.1. Branch reduction

<start>
├──┬──┬>─╮
│  ├╴ ╰──╯
│  ├╴
│
│
├╴
├╴
├╴
├╴
├╴
⋮

4.1.1. removing redundant instructions

<start>        -(-x) = x
├──┬──┬>─╮
├╴ ├╴ ╰──╯
├╴ ├╴
├╴
├╴
├╴
⋮

4.1.2. eliminating dead branches

<start>        if (false) { => b;
├─────┬>─╮         a;
├╴    ╰──╯     } else {
├╴ ├╴              b;
├╴ ├╴          }
├╴
├╴
⋮

4.1.3. The parts left behind

  • structure
  • branch reuse
<start>
├──────┬>─╮
│ a+ɛ  ╰──╯
├──╴
│ a
├─╴
│ a
├─╴
⋮