For as long as I can remember, I have always wanted to write my own compiler. The chicken-and-egg problem of how the first programming languages were created or how modern compilers are written in the same language they compile was a topic I often dove into on StackOverFlow. As it turns out, it is just Bootstrapping.
GCC, RMS and Free Software Movement
I even corresponded with Richard M. Stallman on this, though conversation was focused on getting the source code for GCC version 0.1 and the original RTL code, rather than the first published version from 1987. I ended the conversation quickly, worrying about my own incompetence and my inability to actually make a compiler for a language similar to C. I also feared that he would judge my computing practices, which, while I tried to align with FSF philosophies, were not feasible. I am an engineering student and using non-free software is almost unavoidable in my country. To my surprise, Mr. Stallman was chill throughout our talk. I wished him well and set out to make a language by using other resources. Spoiler: I failed. But that was 3 years ago. My C/C++ skills were not mature enough at the time.
Approach
3 years later, I thought, maybe the approach was wrong. Maybe start with something small, something manageable and work your way up through it.
Idea
On the evening of Febraury 26, I thought: what if I made an interpreter for BrainFuck? That could be done in just one Github Gist. But in addition to that, what if I also made a JIT compiler? I knew little about JIT compilers but, having never implemented it, I thought this would be a fairly strong challenge.
But then again, there must and, mind you, there will always — be a smarter bloke, who might have thought of the same thing. Lo and behold, there were at least 5 instances of people making BrainFuck JIT compilers in a quick Google Search.
I decided to make it anyways in C++, since, for this bootstrapping is like growing your own wheat to make bread when you could just get it from the supermarket.
Technical
Premature optimization is the root of all evil
I decided to follow Dr. Knuth's words and first made the interpreter part. Fairly simple.
But first, what is BrainFuck? It's an esoteric programming language that while being Turing Complete, is unusable in any practical sense. Quoting the EsoLangs site:
Brainfuck operates on an array of memory cells, each initially set to zero. ... There is a pointer, initially pointing to the first memory cell.
My implementation assumes that memory cell count grows dynamically, rather than the fixed 30000 cells specified by the original implementation, for flexibility purposes. But for the JIT compiler to work efficiently, we later convert it into fixed size memory.
The following are the only language tokens/keywords:
| Keyword | Usage |
|---|---|
| > | Move the pointer to the right |
| < | Move the pointer to the left |
| + | Increment the memory cell at the pointer |
| - | Decrement the memory cell at the pointer |
| . | Output the character signified by the cell at the pointer |
| , | Input a character and store it in the cell at the pointer |
| [ | Jump past the matching ] if the cell at the pointer is 0 |
| ] | Jump back to the matching [ if the cell at the pointer is nonzero |
Source: EsoLangs
while (tok_idx < program.size())
{
switch (program[tok_idx])
{
case '>':
bf.moveRight();
break;
case '<':
bf.moveLeft();
break;
case '+':
bf.increment();
...
...
}
}
bf object has the BrainFuck language state machine. The functions are self explanatory.
Interpreter Hurdle
The first problem came when I tried to load the source code. How do we do it?
COPY THE SOURCE CODE INTO A STRING!!!
But can we assume that the source code will always be small? Loading the source code into a is string is almost never a good design. But for this case, we might have a trick up our sleeves.
We can clean the strings of any whitespace and comments since, first, it is an esoteric language, and second, we have std::ifstream_iterator, which can store the source code into a string in chunks using the std::ifstream.
A point to note is that any other character used besides the ones mentioned in the token/keyword table above is automatically considered as a comment.
Loops Hurdle
For loops, we have to check if the current cell is zero on not. If it is, we skip the entire [ ... ] block. And if not, we enter and execute the blocks inside [...] until the current cell is zero.
For my interpreter, which is one-pass, it becomes tricky because for every loop we encounter, we have to scan forward and count the nested [ and find the matching one.
This is where doing lots of LeetCode comes into play. First, we check if there are equal number of matching [ and ] brackets using stack data structure. Then we make a hash for all the matching brackets' location beforehand.
This can be done by using C++'s dictionary equivalent data structure, std::unordered_map but here the optimization is that we store the hash in std::vector, since the locations of the matching brackets are of the same data type (size_t).
This way, we can instantly jump to matching bracket when necessary loop conditions are met.
for (size_t i = 0; i < program.size(); ++i)
{
if (program[i] == '[')
{
stack.push(i);
}
else if (program[i] == ']')
{
if (stack.empty())
{
throw //...
}
auto match = stack.top();
stack.pop();
bracketMatchingDict[match] = i;
bracketMatchingDict[i] = match;
}
}
...
}
JIT
For the execution, we accept --jit flags from the user. If not used, the standard non-JIT interpreter will be used.
The JIT compiler takes the cleaned source source code, maps it to an enum of BrainFuck operations and scans the source code for repeating operations, namely, + , - , > , < and saves the count for Run Length Encoding optimization at runtime.
typedef struct
{
BF_OPERATION op{};
std::size_t non_immediate_arg{};
} IR_MNEMONIC;
A note here is that this compiler eagerly compiles the entire program instead of waiting for hotspots. A cases where we do emit machine code but is still buggy is when we encounter loops. This is something that still needs fixing.
Another note is that, for the , and . operations, we use dlsym(defined in POSIX standard) to dynamically link getchar and putchar functions from libc.
We store the machine code in a byte buffer, namely std::vector<uint8_t> code{}
For the emission, we first setup the stack frame as:
push rbp
mov rbp, rsp
push rbx
push rsi
push rdi
Then we use rdi for the tape pointer.
- For
>operation, we increase therdiand vice versa for\<. - For
+operation, we increase the value pointed by pointer to address, addressed by rdi as [rdi]. And in the case where the RLE optimization detects, more than one+, we increase it by value pointed by argument/RLE count.
For now, our JIT compiler only patches short jumps using rel8 because, frankly, I am no expert in x86. As I am writing this, I came to know that rel32 exits. So, unless I fix it, expect some loops to break your program.
The most important thing here is that, emitting code alone does nothing, we need to execute those machine instructions.
This is where my favorite function in all of C/C++ comes in handy. The mmap() function. This allows us to bypass the heap allocator to allocate memory directly from the kernel and the fun thing is that we can choose the permissions for the memory allocated. The flags for making the allocated memory executable or writable or readable are passed as arguments to the function as following:
void *exec = mmap(... PROT_READ | PROT_WRITE | PROT_EXEC ...)
Few security holes like code injection are fixed by calling mprotect() which I used to remove the executable flag from the memory block after writing the machine code. But I am no security expert. I am just a bum with a computer and a reliable internet connection.
This is still a work in progress project. I plan to keep improving it.
License
Cover Image of this post: By Rocky Acosta - Own work, CC BY 3.0, Link
Top comments (0)