I’ve always been interested in how programming languages are created, so for the past 8 months I’ve been researching, practicing and more about the creation of compilers. I’ve been able to quite easily write front ends for languages and withing the past couple months have been reading more about the back end pieces of a compiler. On top of this I’ve been reading about and practicing things with the x86 instruction set.
It has been my dream to write a compiler and I would like to make my first big step of understanding back ends, this being attempting a simple x86 assembler. My goal for this is to learn more about code generation, x86 instruction set, executables and figure out the best algorithms and techniques (don’t answer anything about the front end, I have this down lol). Eventually to be satisfied in my progression I would like it to output an executable for my platform (Ubuntu Linux amd64, ELF executable) written in the assembly language.
This is a daunting task, though I feel I’m ready with some blood, sweat, and tears. So, my question is: what and in what way does my assembler need to do things? I know it needs to process the actual source, the what? From all I’ve gathered after processing the source I need to, write out a ELF header and then output the generated x86 code after this correct? I can’t find much in depth information on how the x86 code is stored in the executable or even relocatable object files. I know there’s sections of some sort but I can’t find out how these are expressed, and what they’re for.
Anyone willing to answer any of these questions or point me in the right direction is awesome, I’ve been working on this a long time.
9
It’s sort of difficult to work out what you already know and what you need to know, but I’ll have a go anyway. Sorry if I patronise you.
Architectures
The Intel Instruction Set Architecture is extremely large and complicated, for various historical reasons. Fortunately, you only actually need to support a very small subset of the instruction set to be able to target a general purpose compiler at it. That said it may be easier to target a different architecture, at least at first, because it is still a considerable undertaking.
There exist virtual architectures specifically designed to be good for compilers to target, such as Common Intermediate Language, the Java VM, or LLVM. The first two run on a virtual machine with well defined object formats, and the third can be translated into machine code for many platforms using different back ends.
Targeting a RISC processor such as ARM or MIPS would be much easier than x86 too, as they have smaller, better designed and more uniform instruction sets. Because of their ubiquity in mobile and embedded computing, emulators exist for these processors which would let you test the machine code your assembler outputs. Another idea rather than jumping in at the deep end would be to target an old, obsolete architecture, as these tend to be smaller and well documented. Again, emulators exist to let you test your code.
Or if you just want a hard thinking challenge rather than sheer volume of work challenge, you could try making a compiler target something esoteric like the One Instruction Set Computer…
Basic assembler operation
Since you’ve already got high level languages working, I’m going to assume you can parse and so on. An assembler usually runs in two passes—first it translates most of the code, leaving blanks for the symbols it doesn’t know yet. After the first pass, it should know all the symbols, and it runs over the object file again and fills in the addresses of the symbols.
Typically one object file is generated for each assembler file. Any symbols defined in other files are therefore listed in a symbol table in the object header, and the linker (often a separate program) uses this information to stitch the objects together into an executable afterwards.
Segments
You asked about sections. In x86 (and other architectures) the memory is segmented to allow the amount of addressable memory to be much bigger than the actual amount of physical memory. A program has a number of segments assigned to it by the operating system. The stack gets its own segment, so that if you push more onto the stack than you’ve got space for, you don’t start overwriting stuff. Strings and other constants defined in your assembler file typically get put into the .rodata segment. The .bss segment contains enough space for the uninitialised data in your application. The actual code goes in the .text segment, and the operating system and hardware usually protects against writing in this segment to prevent various kinds of exploits. The operating system is in charge of loading these segments out the object file and putting them in different places in virtual and physical memory.
If a program is sitting about in the background, then operating system may choose to remove some of the (lesser used) pages from physical memory and write them to disk, in order to make more space for other programs. A memory access to those addresses then causes the processor to interrupt, and the operating system loads up the page from disk again and lets the program continue unaware that anything happened.
Other information
The Dragon Book is often considered ‘the bible’ on compiler development. osdev.org has some useful information on ELF format. Since you’re interested in this sort of stuff, and since an appreciation of operating system structures is required once you start getting into things like object file formats, Operating Systems: Design and Implementation is like the bible on operating systems.
Oops, got a bit carried away…
3
For a stand-alone assembler, you need to:
- (optionally) pre-process, including handling things like “%include”, conditional code, macros, etc
- tokenise the text into, um, tokens
- (optionally) do initial constant expression evaluation, e.g. something like
mov eax,123+456*99becomesmov eax,0x29889
For a compiler back-end, you’d start with pre-tokenised assembly and skip all of the above.
In any case; the next step is to:
- sort the code to determine which section/s different pieces go into
- find labels and store them somewhere (symbol table), typically with a “section”, with an “offset within section” if possible/known
- convert tokens into either machine code or data as much as possible (where no labels with unknown “offset within section” is involved)
After that (optionally):
- do a “peephole like” optimisation pass. There’s typically a lot of instructions that can be simplified. For example, something like
lea eax,[ebx + myStructure.firstMember]might becomelea eax,[ebx + 0]and could be optimised tomov eax,ebxwithout breaking anything.
After that:
- fix any references to labels that you couldn’t do in the previous steps
Note: for a decent assembler (at least for 80×86), this is typically repeated until everything is resolved. The reason for this is optimisation – there are several different control transfer instructions (jmp, call) with different sizes, so you can’t know the “offset within section” of most labels until you’ve found the smallest/best control transfer instructions in previous code.
Finally; you generate the output file. This may be a flat binary (where you can, and must, resolve all references to labels to actual addresses). This may also be one of many different object file formats (where you can’t resolve references to labels down to actual addresses).
Note: If you are not constrained by “compatibility with existing tools” limitations; and if you are smart; then you can use the “pre-tokenised assembly” as your own object file format (e.g. where compiler and the first half of the assembler generate “pre-tokenised assembly object files”) and use the latter half of the assembler in place of a traditional linker. This allows you to do much more aggressive optimisation in the latter half of the assembler/linker (basically, you end up with the equivalent of link-time optimisation without any of the normal hassles).
1