The intermediate representation used in Glouton is based on Bril and currently uses the core subset, might extend to the memory subset once we start handling pointers and such.
The core bril subset is a well formed intermediate representation with support for extensions. The IR groups all instructions into three subsets depending on what each instruction does.
- Constant operations: operations that produce a literal value.
- Value operations: operations that produce a value.
- Effect operations: operations that produce side effects.
The entire core IR is described in the reference section but please visit the Bril reference for more details.
The following are examples of the intermediate representation of some small functions.
Some oddities you'll notice in the IR.
-
Every value ends up in a storage location, for example literals are assigned to a local variable for e.g
v0before they are used. -
Arguments and named expressions are stored via the
idoperation, this is a useful pattern to simplify the program. -
There is no notion of scopes anymore when generating programs, the entire function de-scoped and duplicate names are renamed similar to LLVM IR.
Let's consider what the "Hello World" of every compiler writer looks like.
int main() {
return 0;
}@main: int {
v0: int = const 0
ret v0;
}
An empty function and another function with arguments.
int main() {}
int f(int a, int b) {
return a + b;
}@main: int {
}
@f(a: int, b: int): int {
v0: int = id a
v1: int = id b
v2: int = add v0 v1
ret v2;
}
A more complex example with all binary operators.
int main() {
int a = 1 + 1;
int b = 2 - 2;
int c = 3 * 3;
int d = 4 / 4;
bool e = a == b;
bool f = b != c;
bool g = c > d;
bool h = d >= c;
bool i = a < b;
bool j = a <= b;
return 0;
}@main: int {
v0: int = const 1
v1: int = const 1
v2: int = add v0 v1
a: int = id v2
v3: int = const 2
v4: int = const 2
v5: int = sub v3 v4
b: int = id v5
v6: int = const 3
v7: int = const 3
v8: int = mul v6 v7
c: int = id v8
v9: int = const 4
v10: int = const 4
v11: int = div v9 v10
d: int = id v11
v12: int = id a
v13: int = id b
v14: int = eq v12 v13
e: bool = id v14
v15: int = id b
v16: int = id c
v17: int = neq v15 v16
f: bool = id v17
v18: int = id c
v19: int = id d
v20: int = gt v18 v19
g: bool = id v20
v21: int = id c
v22: int = id d
v23: int = gte v21 v22
h: bool = id v23
v24: int = id d
v25: int = id c
v26: int = lt v24 v25
i: bool = id v26
v27: int = id d
v28: int = id c
v29: int = lte v27 v28
j: bool = id v29
v30: int = const 0
ret v30;
}
A simple loop that does a sum.
int main() {
int i = 0;
int x = 0;
for (i = 1;i <= 100;i = i+1) {
x = i + 1;
}
return 0;
}@main: int {
# Initialize i = 0
v0: int = const 0
i: int = id v0
# Initialize x = 0
v1: int = const 0
x: int = id v1
# Loop initialization i = 1
v2: int = const 1
i: int = id v2
# Loop body
.LABEL_0
# x = i + 1
v3: int = const 1
v4: int = add i v3
x: int = id v4
# Loop iteration
# i = i + 1
v5: int = const 1
v6: int = add i v5
i: int = id v6
# Loop condition
# i <= 100
v7: int = const 100
v8: int = lte i v7
br v8 .LABEL_0 .LABEL_1
# Loop exit
.LABEL_1
v9: int = const 0
ret v9
}
While loops.
int main() {
int i = 0;
int x = 0;
while (i <= 100) {
x = x + 1;
i = i + 1;
}
return x;
}@main: int {
v0: int = const 0
i: int = id v0
v1: int = const 0
x: int = id v1
.LABEL_0
v2: int = const 1
v3: int = add x v2
x: int = id v3
v4: int = const 1
v5: int = add i v4
i: int = id v5
v6: int = const 100
v7: int = lte i v6
br v7 .LABEL_0 .LABEL_1
.LABEL_1
ret x
}
Function calls
int f(int a, int b) { return a + b;}
int main() {
return f(1,2);
}@f(a: int, b: int): int {
v0: int = add a b
ret v0
}
@main: int {
v1: int = const 1
v2: int = const 2
v3: int = call @f @v1 @v2
ret v3
}
Conditionals
int main() {
int a = 42;
int b = 17;
if (a > b) {
return a - b;
}
return a + b;
}@main: int {
v0: int = const 42
a: int = id v0
v1: int = const 17
b: int = id v1
v2: int = gt a b
br v2 .LABEL_0 .LABEL_1
.LABEL_0
v3: int = sub a b
ret v3
jmp .LABEL_2
.LABEL_1
jmp .LABEL_2
.LABEL_2
v4: int = add a b
ret v4
}
Core Bril defines two primitive types:
int: 64-bit, two's complement, signed integers.bool: True or false.
These instructions are the obvious binary integer arithmetic operations.
They all take two arguments, which must be names of variables of type int
and produce a result of type int:
add: x + y.mul: x × y.sub: x - y.div: x ÷ y.
In each case, overflow follows two's complement rules.
It is an error to div by zero.
These instructions compare integers.
They all take two arguments of type int and produce a result of type bool:
eq: Equal.lt: Less than.gt: Greater than.le: Less than or equal to.ge: Greater than or equal to.
These are the basic Boolean logic operators.
They take arguments of type bool and produce a result of type bool:
not(1 argument)and(2 arguments)or(2 arguments)
Control operations unlike the value operations above, take labels and functions in addition to normal arguments.
jmp: Unconditional jump. One label: the label to jump to.br: Conditional branch. One argument: a variable of typebool. Two labels: a true label and a false label. Transfer control to one of the two labels depending on the value of the variable.call: Function invocation. Takes the name of the function to call and, as its arguments, the function parameters. Thecallinstruction can be a Value Operation or an Effect Operation, depending on whether the function returns a value.ret: Function return. Stop executing the current activation record and return to the parent or exit the program if this is the top-level main activation record. It has one optional argument: the return value for the function.
Only call may (optionally) produce a result; the rest appear only as Effect
Operations.
id: A type-insensitive identity. Takes one argument, which is a variable of any type, and produces the same value.print: Output values to the console (with a newline). Takes any number of arguments of any type and does not produce a result.nop: Do nothing. Takes no arguments and produces no result.