This page documents my project to create a compiler and tools for a simple imperative language.
The code for this project is on Bitbucket. It isn't very interesting yet, but you can try it out if you really want to.
February 7, 2017
Implementing functions has forced me to face several issues that I've been putting off. First, I had to start actually tracking type information so that the compiler knows how to call each function. When calling a function, you need to know its parameter types, its return type, its calling convention, and whether you know the function address or are calling it indirectly through a pointer.
A more exciting problem is dealing with forward references. I don't want to require forward declarations. This is a nice goal, but the implementation can be tricky! (I now appreciate why so many languages require forward declarations...)
If I'm compiling a function and it refers to some other symbol that I haven't compiled yet, I either need to insert a fixup and come back to it, or go and compile the other symbol and then come back. Inserting fixups is sometimes easy, but sometimes not. An example of an easy fixup is a forward jump address -- for example, for skipping over the body of an "if" statement. You reserve space for the offset (which has a fixed size... unless you want to be clever) and just come back later to fill in the actual jump offset.
test eax // Test the "if" condition. jz else // If the condition is false, take the "else" branch. ... // The "if-true" block (unknown length!) jmp end_if // Skip the "if-false" block. else: ... // The "if-false" block (unknown length!) end_if: ... // The program continues.
Sample generated code for an if..else block. In this case, two forward jumps are required: one to conditionally skip the "if-true" block and one to skip over the "if-false" block after executing the "if-true" block. Since you don't know how long the code in each block will be, the only option is to go back and fix the jump offsets after you've generated all the code in the blocks.
A more difficult fixup is required if you want to declare a local variable that has a type which has not yet been compiled. Since you don't know the type's size, you don't know how much stack space to reserve, and this affects all subsequent allocations of and references to locals. Because of difficult cases like this, I would prefer to avoid fixups wherever possible, and just go compile the other symbol on demand so that I can use the needed type information immediately.
Of course, going off and compiling a different function while you are in the middle of compiling a function has its own problems! At least, it does if your compiler works like mine. Currently, my code generator just appends machine code onto a buffer. This works fine if you are compiling functions sequentially -- but I am not.
So, if I want to compile functions in whatever order I want (and interleaved), I need a different approach. My current plan is to generate the code for each function in a separate buffer ("section"), and then to merge them together later. This is remarkably similar to what linkers do, which I suppose shouldn't be surprising. I am really learning why things are done the way they are -- the hard way.
One benefit of compiling definitions "on demand" is that only the definitions required by the program will actually be included in the binary. Automatic dead code elimination!
February 8, 2017
After trying a few different approaches to solving the function compilation problem, I finally found a simple enough solution. The plan described in the previous post, to compile functions into separate sections and link them together at the end, would have required extensive changes to my code. Instead, I used an approach similar to how I deal with dynamically loaded functions.
The compiler now works like this:
Inspecting all top-level definitions before any actual code is generated means that the compiler knows about all the global symbols before any code is generated. This means I can still compile functions one at a time, and in any order. It also means that the programmer never needs to create forward declarations.
As part of the declaration step, each user-defined function has an address slot reserved for it. All function calls are made indirectly through this slot. Later, when each function is compiled, the actual address of the function's code is written into this slot. These indirect calls are slightly inefficient, but it makes it very easy to compile functions in any order. It also happens to be almost exactly how calls to imported functions work.
// For each function, there is a pointer to its implementation. Main: dd Main_Impl MyFunction: dd MyFunction_Impl Main_Impl: ... call [MyFunction] ... MyFunction_Impl: ... ret
The call to "MyFunction" can be generated before the address of MyFunction's implementation is known.
It would be possible to call functions directly instead of indirectly, but it would require me to keep track of every function call location and patch them all up after their target function was defined. This is possible, but requires additional bookkeeping.
For the first time in quite a while, the compiler produces working programs. This means I can return to working on new features!
February 10, 2017
Today I implemented a top-level "include" directive. I tried to choose a simple and useful definition of file inclusion:
My motivation for this feature was that I wanted to be able to reuse my Win32 API bindings in multiple sample programs.
March 5, 2017
- Current generator is a mess of special cases. - Should switch to x64 anyway. - but I would have to change the linker. - Lots of redundancy in converting Storage to opcodes and absolute addresses. - I should use an orthogonal, table-driven scheme to generate all relevant x86 instructions. - I can probably postpone this task indefinitely, but I shouldn't. - It will only get harder to change later, as I add support for more operations. - Generate better/shorter code? - Cons: Using more instruction types complicates the compiler and disassembler.
If you have comments, questions, or suggestions regarding this topic, please email me at firstname.lastname@example.org!