ILVM
====

The *intermediate-level virtual machine* (ILVM) is an interpreter for a
language that has a few features that make it higher-level than typical
assembly languages:

1.  ILVM has *malloc* and *free* instructions that work similar to the C
    functions. However, the free list is not in program memory, so a program
    cannot accidentally clobber it.

2. ILVM has an *if ... then .. else* instruction, so it supports structured
   control flow.

3. ILVM has primitive instructions to print to screen.

Note: ILVM implements a Harvard architecture and does not have a stack.

Language Overview
-----------------

### Blocks

A program in ILVM is a collection of *blocks*, where each contains a sequence
of instructions. Each block has a unique number and execution always starts
at block zero. For example, the following program has a single block
and prints *30*:

```
block 0 {
    exit(30);
}
```

The following program uses the *goto* instruction to jump to block 1 and then
print *20*:

```
block 1 {
    exit(20);
}
block 0 {
    goto(1);
}
```

Note that the order in which blocks appear is not relevant.

### Register, Loads, and Stores

ILVM has registers numbered *r0* through *rn*, where *n* can be set by the
user. ILVM supports basic binary operations (+, -, *) that take either
registers or constants as arguments, and store their results in registers.
It also supports operations to load data into registers from the heap, and to
store values from registers in the heap. Some examples of these operations
are given below:

```
block 0 {
    r0 = 10;     // set r0 to 10
    r1 = r0 * 2; // set r1 to 20
    *r1 = 50;    // store 50 at heap address 20
    r2 = *r1;    // load the value at heap address in r1 into r2 (i.e., set
                 // r2 to 50
    exit(0);
}
```

### Control Flow

The *goto(n);* instruction jumps to block *n*. The argument may either be
a literal constant, or it may be value stored in a register. For example,
the following program calculates the address of the block to jump to:

```
block 0 {
    r0 = 10;
    r1 = r0 - 9;
    goto(r1); // jumps to block 1
}
block 1 {
    exit(0);
}
```

The *ifz r trueBlock else falseBlock* instruction is a conditional with two
sub-blocks. If the value in the register is zero, it executes *trueBlock*, else
it executes *falseBlock*. For example, the following program calculates
*factorial(5)*:

```
block 0 {
    r2 = 1;
    r1 = 5;
    goto(1);
}
block 1 {
    ifz r1 {
        exit(r2);
    }
    else {
        r2 = r2 * r1;
        r1 = r1 - 1;
        goto(1);
    }
}
```

Note that the sub-blocks may have nested *ifz* instructions. Also note
that sub-blocks are not numbered. Therefore, a program cannot use
*goto* to jump to a sub-block.

### Termination and (lack of) fall-through

The *exit(n)* instruction terminates the program normally, and produces
the value *n*. The *abort;* instruction is an abnormal exit and should be
avoided if possible. Note that the sequence of instructions
in every block *must* end with either *exit*, *goto*, or *abort*. In other
words, a program cannot "fall-through" from one block to the next, and must
explicitly jump to another block or terminate.

### Memory allocation

The *word size* of ILVM is 32-bits.

A program can read and write to any memory address. The initial value stored at
all memory addresses and registers is zero. Each memory location and register
is one word long (i.e., 32 bits).

ILVM has a *malloc(n)* instruction that returns the address of
a free block of memory that is *n* **words** long, and a *free(a)* instruction that
frees the block that was allocated at the address *a*. It may be convenient
to use these functions instead of writing an allocation manually. Note that
these operators maintain their metadata in an independent part of memory, so
it is not possible for an ill-behaved program to corrupt the state that
*malloc* and *free* require.

Programs do not have to use *malloc* and *free*. However, it may be convenient
to do so.

Concrete Syntax
---------------

```
Registers         r ::= "r0" | ... | "r64"

Values          val ::= r
                      | i                     Signed 32-bit integers

Operators        op ::= "+"
                      | "-"
                      | "*"
                      | "/"
                      | "%"
                      | "=="
                      | "<"

Instructions  instr ::= "goto" "(" val ")" ";"
                      | "exit" "(" val ")" ";"
                      | "abort" ";"
                      | r "=" val op val ";" instr
                      | r "=" val ";" instr
                      | r "=" "*" val ";" instr
                      | "*" r "=" val ";" instr
                      | "ifz" val "{" instr "}" "else" "{" instr "}""
                      | r "=" "malloc" "(" val ")" ";" instr
                      | "free" "("r ")" ";" instr

Blocks        block ::= "block" n "{" instr "}"

Programs          p ::= block
                      | block p
```

Command-Line Interface
----------------------

Run `ilvm --help` for documentation.