-
Notifications
You must be signed in to change notification settings - Fork 0
Devlog
The control flow graph used for holding the three address code intermediate language is complete. Statements are split into basic blocks where control flow enters at the start and exits at the end of each block. Once all three address code have been generated from the abstract syntax tree, it removes any unreachable blocks. For example
int main(int argc, char** argv) {
if (argc == 1)
return 9;
else if (argc == 2)
return 8;
else if (argc == 3) {
return 7;
}
else
return 6;
}generates the following graph
Control flow graph [11]
Block 0
IL:
0 ce __t0, argc, 1
1 jz __l0, __t0
-> 1 3
Block 1
IL:
0 ret 9
->
Block 2
IL:
0 jmp __l1
-> 10
Block 3
Labels: __l0
IL:
0 ce __t1, argc, 2
1 jz __l2, __t1
-> 4 6
Block 4
IL:
0 ret 8
->
Block 5
IL:
0 jmp __l3
-> 10
Block 6
Labels: __l2
IL:
0 ce __t2, argc, 3
1 jz __l4, __t2
-> 7 9
Block 7
IL:
0 ret 7
->
Block 8
IL:
0 jmp __l5
-> 10
Block 9
Labels: __l4
IL:
0 ret 6
->
Block 10
Labels: __l5 __l3 __l1
IL:
->
with unreachable blocks eliminated
Control flow graph [7]
Block 0
IL:
0 ce __t0, argc, 1
1 jz __l0, __t0
-> 1 2
Block 1
IL:
0 ret 9
->
Block 2
Labels: __l0
IL:
0 ce __t1, argc, 2
1 jz __l2, __t1
-> 3 4
Block 3
IL:
0 ret 8
->
Block 4
Labels: __l2
IL:
0 ce __t2, argc, 3
1 jz __l4, __t2
-> 5 6
Block 5
IL:
0 ret 7
->
Block 6
Labels: __l4
IL:
0 ret 6
->
I have had some time recently which I spent improving the parser. Previously, the parse tree it generated was very difficult to convert to the intermediate language as it had too many nodes and was not annotated with much information by the parser. The new parser now generates a tree closer to typical abstract syntax trees, shown below
int main(int argc, char** argv) {
int a = argc;
int b = 2 - (3 + 4 * (5 + a) - a);
return (b + 20000) % 255;
}root
└ function_definition
├ declaration_specifiers(int)
├ pointer(0)
├ new_identifier(main)
├ parameter_type_list
| ├ parameter_list
| | ├ declaration_specifiers(int)
| | ├ pointer(0)
| | └ new_identifier(argc)
| └ parameter_list
| ├ declaration_specifiers(char)
| ├ pointer(2)
| └ new_identifier(argv)
└ compound_statement
├ declaration
| ├ declaration_specifiers(int)
| ├ pointer(0)
| ├ identifier(a)
| └ identifier(argc)
├ declaration
| ├ declaration_specifiers(int)
| ├ pointer(0)
| ├ identifier(b)
| └ binary_expression(-)
| ├ constant(2)
| └ binary_expression(-)
| ├ binary_expression(+)
| | ├ constant(3)
| | └ binary_expression(*)
| | ├ constant(4)
| | └ binary_expression(+)
| | ├ constant(5)
| | └ identifier(a)
| └ identifier(a)
└ jump_statement(return)
└ binary_expression(%)
├ binary_expression(+)
| ├ identifier(b)
| └ constant(20000)
└ constant(255)
Error handling has also been improved, it can catch some basic syntax errors and report the location where it occurred with good accuracy, shown below
int main(int argc, char** argv) {
int a = 1 + 2 + 3 + 4;
int b = 5 * 6 * 7 * 8 + a
}Expected ';'
4:1 | }
| ~
Another example
int main(int argc, char** argv) {
int a = 1 + 2 + 3 + 4 + b + 4 + 3 + 2 + 1;
}Unknown identifier 'b'
2:29 | int a = 1 + 2 + 3 + 4 + b
| ~
Function calls are implemented, they can be nested, call each other, perform recursion, everything you expect (excluding function pointers). The calling system V calling convention is followed, allowing calls to library functions in the future. The implementation required the instruction selector be modified as function calls need some addition logic to determine where to put its arguments, and the register coalesce stage is currently disabled as there are some bugs regarding the implementation of division which has yet been fixed, resulting in extra copy operations.
// Recursive integer powers
int pow(unsigned base, unsigned exponent) {
if (exponent == 0) {
return 1;
}
return base * pow(base, exponent - 1);
}
int main(int argc, char** argv) {
return pow(2, argc);
}pow:
push rbp
mov rbp, rsp
sub rsp, 8
push rbx
mov DWORD [rbp-4], edi
mov ebx, 0
xor eax, eax
cmp esi, ebx
sete al
test eax, eax
jz _Z3__l0
mov eax, 1
jmp pow@ep
_Z3__l0:
mov eax, 1
mov DWORD [rbp-8], esi
sub DWORD [rbp-8], eax
mov edi, DWORD [rbp-4]
mov esi, DWORD [rbp-8]
call pow
mov ebx, eax
mov eax, DWORD [rbp-4]
imul eax, ebx
jmp pow@ep
pow@ep:
pop rbx
leave
ret
main:
push rbp
mov rbp, rsp
sub rsp, 4
mov DWORD [rbp-4], edi
mov edi, 2
mov esi, DWORD [rbp-4]
call pow
jmp main@ep
main@ep:
leave
ret
After much more work than expected, static arrays on the stack are implemented. Their implementation required the introduction of a new array type, introduction of a new addressing mode in the instruction selector of the form mov [base+index], src, changes to how the intermediate representation of instructions are stored in the assembly generator to support the addressing modes required, and changes to liveness calculations to handle memory accesses.
int main(int argc, char** argv) {
int a[5];
a[0] = 5;
a[1] = 4;
a[2] = 3;
a[3] = 2;
a[4] = 1;
return a[argc];
} push rbp
mov rbp, rsp
sub rsp, 20
mov rax, 0
imul rax, 4
mov DWORD [rbp-20+rax], 5
mov rax, 1
imul rax, 4
mov DWORD [rbp-20+rax], 4
mov rax, 2
imul rax, 4
mov DWORD [rbp-20+rax], 3
mov rax, 3
imul rax, 4
mov DWORD [rbp-20+rax], 2
mov rax, 4
imul rax, 4
mov DWORD [rbp-20+rax], 1
movsx rax, edi
imul rax, 4
mov eax, DWORD [rbp-20+rax]
leave
retIn the future, the plan is to have an optimizer which is capable of folding the constants used to access the array.
The assembly generator improvements are complete for now and implicit integer conversions were added. The register allocator now attempts to merge variables together if their lifespans do not overlap to reduce copies. Most importantly, it now correctly generates spill code if variables had to be spilled onto the stack.
The assembly generator now has a register allocator using graph coloring. It is now capable of generating better assembly, though it is not perfect and sometimes emits incorrect instructions.
Improvements can still be made and is in progress - a register preference system to guide the allocator on which register to choose (right now it chooses the first available register), and switching to a tree rewriting instruction selector instead of a macro expander to better take advantage of the X86 instruction set.
An example of an improvement using the new instruction selector is better assembly for testing conditionals, currently:
if (argc == 1) { /* body */ }generates the assembly with 3 unnecessary instructions:
cmp edi, 1
sete al ; Unnecessary
movzx eax, al ; Unnecessary
test eax, eax ; Unnecessary
jz _Z2__l0
; body
_Z2__l0:Here is the assembly generated for the same program as last time compared to the old assembly:
int main(int argc, char** argv) {
int a = 5;
if (argc == 1) {}
if (argc == 2)
a = 7;
if (argc == 3) {
a = 8;
}
if (argc == 4) {
int a = 9;
a = 10;
}
return a;
}New:
; 30 instructions
f@main:
push rbp
mov rbp, rsp
mov ebx, 5
cmp edi, 1
sete al
movzx eax, al
test eax, eax
jz _Z2__l0
_Z2__l0:
cmp edi, 2
sete al
movzx eax, al
test eax, eax
jz _Z4__l1
mov ebx, 7
_Z4__l1:
cmp edi, 3
sete al
movzx eax, al
test eax, eax
jz _Z5__l2
mov ebx, 8
_Z5__l2:
cmp edi, 4
sete al
movzx eax, al
test eax, eax
jz _Z7__l3
mov eax, 9
mov eax, 10
_Z7__l3:
mov eax, ebx
leave
retOld:
; 57 Instructions
f@main:
push rbp
mov rbp, rsp
sub rsp, 4
mov eax, 5
mov DWORD [rbp-4], eax
sub rsp, 4
mov eax, edi
mov ecx, 1
cmp eax, ecx
sete al
movzx eax, al
mov DWORD [rbp-8], eax
mov eax, DWORD [rbp-8]
test eax, eax
jz _Z1__l0
_Z1__l0:
sub rsp, 4
mov eax, edi
mov ecx,2
cmp eax, ecx
sete al
movzx eax, al
mov DWORD [rbp-12], eax
mov eax, DWORD [rbp-12]
test eax, eax
jz _Z1__l1
mov eax, 7
mov DWORD [rbp-4], eax
_Z1__l1:
sub rsp, 4
mov eax, edi
mov ecx,3
cmp eax, ecx
sete al
movzx eax, al
mov DWORD [rbp-16], eax
mov eax, DWORD [rbp-16]
test eax, eax
jz _Z1__l2
mov eax, 8
mov DWORD [rbp-4], eax
_Z1__l2:
sub rsp, 4
mov eax, edi
mov ecx, 4
cmp eax, ecx
sete al
movzx eax, al
mov DWORD [rbp-20], eax
mov eax, DWORD [rbp-20]
test eax, eax
jz _Z1__l3
sub rsp, 4
mov eax, 9
mov DWORD [rbp-24], eax
mov eax, 10
mov DWORD [rbp-24], eax
_Z1__l3:
mov eax, DWORD [rbp-4]
leave
retThe compiler can now generate (poor) assembly for if else statements as it is now capable of translating boolean expressions, comparisons, and understands scopes. It also understands the standard arithmetic operations, assignment, and prefix/postfix increment/decrement.
Here is an example:
int main(int argc, char** argv) {
int a = 5;
if (argc == 1) {}
if (argc == 2)
a = 7;
if (argc == 3) {
a = 8;
}
if (argc == 4) {
int a = 9;
a = 10;
}
return a;
}generates the intermediate language (formatted to be easier to read):
func main,i32,i32 argc,i8** argv
def i32 _Z1a
mov _Z1a, 5
def void _Z1__l0
def i32 _Z1__t0
ce _Z1__t0, argc, 1
jz _Z1__l0, _Z1__t0
lab _Z1__l0
def void _Z1__l1
def i32 _Z1__t1
ce _Z1__t1, argc, 2
jz _Z1__l1, _Z1__t1
mov _Z1a, 7
lab _Z1__l1
def void _Z1__l2
def i32 _Z1__t2
ce _Z1__t2, argc, 3
jz _Z1__l2, _Z1__t2
mov _Z1a, 8
lab _Z1__l2
def void _Z1__l3
def i32 _Z1__t3
ce _Z1__t3, argc, 4
jz _Z1__l3, _Z1__t3
def i32 _Z3a
mov _Z3a, 9
mov _Z3a, 10
lab _Z1__l3
ret _Z1a
which generates x86 assembly:
; func main,i32,i32 argc,i8** argv
global _start
_start:
mov rdi, QWORD [rsp]
mov rsi, QWORD [rsp+8]
call f@main
mov rdi, rax
mov rax, 60
syscall
f@main:
push rbp
mov rbp,rsp
; def i32 _Z1a
sub rsp,4
; mov _Z1a,5
mov eax,5
mov DWORD [rbp-4],eax
; def void _Z1__l0
; def i32 _Z1__t0
sub rsp,4
; ce _Z1__t0,argc,1
mov eax,edi
mov ecx,1
cmp eax,ecx
sete al
movzx eax,al
mov DWORD [rbp-8],eax
; jz _Z1__l0,_Z1__t0
mov eax,DWORD [rbp-8]
test eax,eax
jz _Z1__l0
; lab _Z1__l0
_Z1__l0:
; def void _Z1__l1
; def i32 _Z1__t1
sub rsp,4
; ce _Z1__t1,argc,2
mov eax,edi
mov ecx,2
cmp eax,ecx
sete al
movzx eax,al
mov DWORD [rbp-12],eax
; jz _Z1__l1,_Z1__t1
mov eax,DWORD [rbp-12]
test eax,eax
jz _Z1__l1
; mov _Z1a,7
mov eax,7
mov DWORD [rbp-4],eax
; lab _Z1__l1
_Z1__l1:
; def void _Z1__l2
; def i32 _Z1__t2
sub rsp,4
; ce _Z1__t2,argc,3
mov eax,edi
mov ecx,3
cmp eax,ecx
sete al
movzx eax,al
mov DWORD [rbp-16],eax
; jz _Z1__l2,_Z1__t2
mov eax,DWORD [rbp-16]
test eax,eax
jz _Z1__l2
; mov _Z1a,8
mov eax,8
mov DWORD [rbp-4],eax
; lab _Z1__l2
_Z1__l2:
; def void _Z1__l3
; def i32 _Z1__t3
sub rsp,4
; ce _Z1__t3,argc,4
mov eax,edi
mov ecx,4
cmp eax,ecx
sete al
movzx eax,al
mov DWORD [rbp-20],eax
; jz _Z1__l3,_Z1__t3
mov eax,DWORD [rbp-20]
test eax,eax
jz _Z1__l3
; def i32 _Z3a
sub rsp,4
; mov _Z3a,9
mov eax,9
mov DWORD [rbp-24],eax
; mov _Z3a,10
mov eax,10
mov DWORD [rbp-24],eax
; lab _Z1__l3
_Z1__l3:
; ret _Z1a
mov eax,DWORD [rbp-4]
leave
retThe parser is now capable of generating a parse tree for a small subset of the language. The parser will walk this parse tree in order to generate intermediate code.
Input:
int main(int argc, char** argv) {
return argc;
}Parse tree:
root
└ function_definition
├ declaration_specifiers
| └ type_specifier
| └ "int"
├ declarator
| └ direct_declarator
| ├ identifier
| | └ "main"
| └ direct_declarator
| └ parameter_type_list
| └ parameter_list
| ├ parameter_declaration
| | ├ declaration_specifiers
| | | └ type_specifier
| | | └ "int"
| | └ declarator
| | └ direct_declarator
| | └ identifier
| | └ "argc"
| └ parameter_list
| └ parameter_declaration
| ├ declaration_specifiers
| | └ type_specifier
| | └ "char"
| └ declarator
| ├ pointer
| | ├ "*"
| | └ pointer
| | └ "*"
| └ direct_declarator
| └ identifier
| └ "argv"
└ compound_statement
└ block_item_list
└ block_item
└ statement
└ jump_statement
└ expression
└ assignment_expression
└ conditional_expression
└ logical_or_expression
└ logical_and_expression
└ inclusive_or_expression
└ exclusive_or_expression
└ and_expression
└ equality_expression
└ relational_expression
└ shift_expression
└ additive_expression
└ multiplicative_expression
└ cast_expression
└ unary_expression
└ postfix_expression
└ primary_expression
└ identifier
└ "argc"