Compiler Over the Weekend: Finally, Assembler
We continue our conversation about the toy compiler of the simplest language I invented, wend. This time we have reached a certain milestone: we will finally generate not Python code, but assembler code.
Well, when it works, I suggest solving the problem: how to emulate bitwise and-not-xor-or operations using four arithmetic ones.
This is already the sixth article in the series; to understand what is happening, you need to read, if not all of them, then at least the previous one.
Table of contents of the cycle
Syntax trees and a naive Python translator
Lexer/parser
2'. The Cursed Fire, or the Magic of the C Preprocessor
Symbol Tables: Variable Scopes and Type Checking
Stack and translator to python without using python variables
Translator to assembler (This article)
Getting rid of dependencies: writing a lexer and parser ourselves
Optimizing compiler?
Garbage collector?
We covered stack and register handling, which are the biggest problems for assembler beginners, in the previous article, so this time there's very little left to do. At the moment, our compiler generates Python code, the structure of which fully corresponds to the desired assembler code. The only thing left to figure out is output to the screen, everything else is already decidedly ready.
Hello world, or displaying strings on the screen
Most often, the MIPS assembler is chosen in educational compilers, but I don’t like running code in an emulator, so I didn’t think long and chose the x86 GNU assembler, fortunately, it comes with gcc. I can’t say exactly why, but I wanted a 32-bit version. For our purposes, there is absolutely no need to be an assembler guru, but you need to be able to write programs at the level of Halloween.
Let's make a template from which we will later push off. Let's imagine that we have a file helloworld.s with the following contents:
.global _start
.data
hello: .ascii "hello world\n"
hello_len = . - hello
.align 2
.text
_start:
movl $4, %eax # sys_write system call (check asm/unistd_32.h for the table)
movl $1, %ebx # file descriptor (stdout)
movl $hello, %ecx # message to write
movl $hello_len, %edx # message length
int $0x80 # make system call
_end:
movl $1, %eax # sys_exit system call
movl $0, %ebx # error code 0
int $0x80 # make system call
Then we can compile it using the as and ld commands as follows:
as --march=i386 --32 -o helloworld.o helloworld.s &&
ld -m elf_i386 helloworld.o -o helloworld &&
./helloworldIf everything went well, then a proud greeting should appear on the screen. Now let's figure out what's going on there. And there are only two system calls – sys_write and sys_exit. In sys, the same could be written as follows:
#include <sys/syscall.h>
#include <unistd.h>
int main(void) {
syscall(SYS_write, 1, "hello world\n", 12);
return 0;
}If the stars align correctly, gcc will generate roughly the same assembler code. For our purposes, no other system calls are needed, write and exit are more than enough, since the only interaction with the outside world in wend is output to the screen.
Wend can't do any string operations, only output constant strings to the screen, so my compiler simply creates a unique identifier in the header for each string, just like for our hello world. To output Boolean values to the screen, there are two constant strings, true and false. And what about numbers? Well, that's where I'll have to work a little. I'm lazy, and I didn't want to deal with glibc linking and the like, so the luxury of printf is not available to me. Oh well, we'll manage with sys_write 🙂
Displaying decimal numbers on the screen
sys_write can print strings to the screen, so we need to learn how to convert numbers (I only have signed 32-bit ones) to string representation. To do this, I rolled up my sleeves and wrote the print_int32 function:
.global _start
.data
.align 2
.text
_start:
pushl $-729
call print_int32
addl $4, %esp
_end:
movl $1, %eax # sys_exit system call
movl $0, %ebx # error code 0
int $0x80 # make system call
print_int32:
movl 4(%esp), %eax # the number to print
cdq
xorl %edx, %eax
subl %edx, %eax # abs(%eax)
pushl $10 # base 10
movl %esp, %ecx # buffer for the string to print
subl $16, %esp # max 10 digits for a 32-bit number (keep %esp dword-aligned)
0: xorl %edx, %edx # %edx = 0
divl 16(%esp) # %eax = %edx:%eax/10 ; %edx = %edx:%eax % 10
decl %ecx # allocate one more digit
addb $48, %dl # %edx += '0' # 0,0,0,0,0,0,0,0,0,0,'1','2','3','4','5','6'
movb %dl, (%ecx) # store the digit # ^ ^ ^
test %eax, %eax # # %esp %ecx (after) %ecx (before)
jnz 0b # until %eax==0 # <----- %edx = 6 ----->
cmp %eax, 24(%esp) # if the number is negative |
jge 0f # |
decl %ecx # allocate one more character |
movb $45, 0(%ecx) # '-' |
0: movl $4, %eax # write system call |
movl $1, %ebx # stdout |
leal 16(%esp), %edx # the buffer to print |
subl %ecx, %edx # number of digits <--------------------------------┘
int $0x80 # make system call
addl $20, %esp # deallocate the buffer
retIt's hard to read someone else's assembly code, so let me give you the Python equivalent of our function:
def print_int32(n):
buffer = [ None ]*16 # output string buffer
ecx = 0 # number of characters stored in the buffer
eax = abs(n)
while True:
edx = eax % 10
eax = eax // 10
buffer[ecx] = chr(edx + ord('0'))
ecx += 1
if eax == 0: break
if n<0:
buffer[ecx] = '-'
ecx += 1
print(''.join(buffer[ecx-1::-1]))
print_int32(-729)I will only call Write once, so I need to prepare a string buffer. A 32-bit number will not require more than 11 characters, so I allocate 16 for the buffer (so that the stack is aligned to the edge of the machine word). Then I convert the absolute value of the given number to a string, and at the end I stick a minus if the number was negative.
With the help of such simple gymnastics we can display strings and numbers on the screen, and, what is typical, without the headache of linking with some 32-bit version of libc on a 64-bit system.
And such output to the screen is necessary not only to support the print instruction of our language, but also for debugging. GDB is for the faint of heart, inserting output to the screen anywhere is our everything 😉
Putting it all together
Well, that’s all, actually. Now we take a template for generating Python code, and instead of outputting Python print() it's enough to write call print_int32instead of eax = eax * ebx write imull %ebx, %eax. Thus, we systematically translate Python instructions into assembler, and the job is done! There are no subtleties left, the long-awaited compiler is almost ready. You can take release v0.0.5 and play with it.
Let's program in wend already! Bitwise operations.
If you were paying attention to what was happening, you saw that the only numeric types I have are signed 32-bit integers, and only basic arithmetic operations are allowed on them, while more advanced languages allow, for example, bitwise logical operations. Am I a ginger? I can do that too 🙂
Actually, this is a great exercise, I recommend not looking at my code and trying to write the code yourself. Note that I know for sure that my numbers are stored in two's complement, and there is no undefined behavior with signed overflows 🙂
AND
Let's try to emulate a bitwise “and” using standard arithmetic. Without thinking twice, I process the most significant bit, and then simply run a trivial loop over the remaining 31 bits:
// _ _ _____
// /\ | \ | | __ \
// / \ | \| | | | |
// / /\ \ | . ` | | | |
// / ____ \| |\ | |__| |
// /_/ \_\_| \_|_____/
fun and(a:int, b:int) : int {
var result:int;
var pow:int;
result = 0;
if (a<0 && b<0) {
result = -2147483648;
}
if (a<0) {
a = a + 2147483648;
}
if (b<0) {
b = b + 2147483648;
}
pow = 1;
while a>0 || b>0 {
if a % 2 == 1 && b % 2 == 1 {
result = result + pow;
}
a = a / 2;
b = b / 2;
pow = pow * 2;
}
return result;
}The code is quite oaky, if someone can suggest a more elegant approach, I will gladly adopt it!
NOT
The bitwise “not” looks much simpler:
// _ _ ____ _______
// | \ | |/ __ \__ __|
// | \| | | | | | |
// | . ` | | | | | |
// | |\ | |__| | | |
// |_| \_|\____/ |_|
fun not(a:int) : int {
return -1 - a;
}
XOR and OR
Well, since “and” and “not” are not enough to model all other operations, then “or” is trivial to do:
// __ ______ _____
// \ \ / / __ \| __ \
// \ V / | | | |__) |
// > <| | | | _ /
// / . \ |__| | | \ \
// /_/ \_\____/|_| \_\
fun xor(a:int, b:int) : int {
return a - and(a,b) + b - and(a,b);
}
// ____ _____
// / __ \| __ \
// | | | | |__) |
// | | | | _ /
// | |__| | | \ \
// \____/|_| \_\
fun or(a:int, b:int) : int {
return xor(xor(a,b),and(a,b));
}
Test
Let's launch test on carefully prepared random data, and look, it works!
bitwise and -1804289383 1681692777 1957747793 -719885386 596516649 1025202362 783368690 -2044897763
-1804289383 -1804289383 70555657 338728977 -1810617712 268809 336599192 70254736 -2079059431
1681692777 70555657 1681692777 1680906305 1142163488 537663529 605558824 607125600 68947977
1957747793 338728977 1680906305 1957747793 1410353168 545266689 873486352 615530576 68178961
-719885386 -1810617712 1142163488 1410353168 -719885386 17173280 353585330 68239794 -2078981612
596516649 268809 537663529 545266689 17173280 596516649 554309672 578814240 34346505
1025202362 336599192 605558824 873486352 353585330 554309672 1025202362 739328178 68767768
783368690 70254736 607125600 615530576 68239794 578814240 739328178 783368690 101793808
-2044897763 -2079059431 68947977 68178961 -2078981612 34346505 68767768 101793808 -2044897763
bitwise or -1804289383 1681692777 1957747793 -719885386 596516649 1025202362 783368690 -2044897763
-1804289383 -1804289383 -193152263 -185270567 -713557057 -1208041543 -1115686213 -1091175429 -1770127715
1681692777 -193152263 1681692777 1958534265 -180356097 1740545897 2101336315 1857935867 -432152963
1957747793 -185270567 1958534265 1957747793 -172490761 2008997753 2109463803 2125585907 -155328931
-719885386 -713557057 -180356097 -172490761 -719885386 -140542017 -48268354 -4756490 -685801537
596516649 -1208041543 1740545897 2008997753 -140542017 596516649 1067409339 801071099 -1482727619
1025202362 -1115686213 2101336315 2109463803 -48268354 1067409339 1025202362 1069242874 -1088463169
783368690 -1091175429 1857935867 2125585907 -4756490 801071099 1069242874 783368690 -1363322881
-2044897763 -1770127715 -432152963 -155328931 -685801537 -1482727619 -1088463169 -1363322881 -2044897763
bitwise xor -1804289383 1681692777 1957747793 -719885386 596516649 1025202362 783368690 -2044897763
-1804289383 0 -263707920 -523999544 1097060655 -1208310352 -1452285405 -1161430165 308931716
1681692777 -263707920 0 277627960 -1322519585 1202882368 1495777491 1250810267 -501100940
1957747793 -523999544 277627960 0 -1582843929 1463731064 1235977451 1510055331 -223507892
-719885386 1097060655 -1322519585 -1582843929 0 -157715297 -401853684 -72996284 1393180075
596516649 -1208310352 1202882368 1463731064 -157715297 0 513099667 222256859 -1517074124
1025202362 -1452285405 1495777491 1235977451 -401853684 513099667 0 329914696 -1157230937
783368690 -1161430165 1250810267 1510055331 -72996284 222256859 329914696 0 -1465116689
-2044897763 308931716 -501100940 -223507892 1393180075 -1517074124 -1157230937 -1465116689 0
-1804289383 1681692777 1957747793 -719885386 596516649 1025202362 783368690 -2044897763
bitwise not 1804289382 -1681692778 -1957747794 719885385 -596516650 -1025202363 -783368691 2044897762Let's sum it up
The intermediate goal has been achieved: we have learned to compile our own language into a real x86 gnu assembler. At the moment, I use a third-party library sly for parsing, but along the way I got a little carried away, and it turned out that writing your own parser is not at all difficult. And at the same time, it will be possible to correct the grammar of the language, so that it would be more pleasant to write!
So the next two articles will be about how to make a lexer and parser yourself, the finished code is already in the repository.
And here's what happens next… I have a strong suspicion (I'm not a real welder, I found a mask!) that the most interesting things start right after that. I'll try to figure it out, and at the same time tell you how the optimizing compiler works. As an intermediate representation, I'll choose LLVM IR, so that you can run the code using LLVM at any time, but everything will be done manually without LLVM. I will allocate myself about five hundred additional lines of Python code for the “optimizing” (only showing the principle) compiler budget. Let's see what happens 🙂
Stay tuned, have fun!
![[Проект вуза] Psychoanalytic coaching that works](https://prog.world/wp-content/uploads/2023/02/cc3f6051be2b047be8c49ffdc7d6f61e-768x403.png)
