1

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.

closed as too broad by amon, user40980, Martijn Pieters, gnat, GlenH7 Feb 25 '14 at 23:49

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • Almost no high level language compiler needs to bother with things like ELF files, relocations or instruction encoding. There are a number of targets you can emit code for that will take care of that; almost all compilers can and should use on of these. The traditional option (but not necessarily easiest or best) is to emit textual assembly files and pass them to an external linker. – user7043 Feb 24 '14 at 22:50
  • 1
    @delnan That is a fair point but the whole point of me doing this is to learn about how things like this are constructed, no to learn how to execute a program. – APott Feb 24 '14 at 22:52
  • 1
    That's a fine goal in itself, I'm just saying it has nothing in common with the goals you state in the introduction (programming language implementation; compiler back ends). – user7043 Feb 24 '14 at 23:14
  • @delnan So you're saying that tcc calls an external assembler? I think not, that would void the purpose of tcc itself, all code is generated in house, being the reason why it's so speedy. So this is relevant to compiler back ends, what do you think LLVM is? It's an abstraction, this is exactly what it's doing under the hood. There are plenty of small hand written compilers that generate their own code. Machine code is also generated to implement things like JIT systems. Ignoring this though, can anyone answer my questions? – APott Feb 24 '14 at 23:22
  • 1
    recommended reading: Where to start – gnat Feb 25 '14 at 15:06
7

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...

  • 1
    That is a fantastic answer. All of this was extremely handy (except for the cliche at the end (yes, you know what I'm talking about xD)). I will definitely use some of your advice and dive deeper, thanks for the help m8. – APott Feb 25 '14 at 0:23
  • No worries, and good luck. – sjmeverett Feb 25 '14 at 0:43
  • +1 for targeting ARM! Intel x86 is a nightmare even the Intel chips rewrite it internally. – James Anderson Feb 25 '14 at 6:54
4

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*99 becomes mov 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 become lea eax,[ebx + 0] and could be optimised to mov eax,ebx without 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 80x86), 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
    Fantastic answer. That walk through helps a ton, thanks again! – APott Feb 25 '14 at 20:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.