What is a compiler?

A few logistics points for now:

• The course website has most of the details you need about course structure!
• One (short!) assignments and another (even shorter!) assignment are due next week:
  • The first homework assignment, HW0. Homeworks will be due weekly or biweekly. HW0 is a very short programming assignment in the OCaml programming language. We’re not expecting you to have written any OCaml before this course; the point of this homework is just to make sure everyone has the development environment set up and has started to learn the language. We’ll talk more about OCaml very soon.
  • The first drill. There will be drills due every week, except this first week. These are short quizzes, graded on completion; the idea is to get an idea of how comfortable everyone is feeling with the week’s class material, so we can spend more time on the topics you need most. This first drill asks you to look over the course syllabus, including the course collaboration and professionalism policies.
• Most of your grade for the course will be based on the homeworks. You’ll also get some points for completing the drills. The other component of your grade will be exams; you’ll have two of these, one midterm and one final.

We can find out by writing such a program in C:

#include <stdio.h>
#include <inttypes.h>

int64_t entry() {
  return 4000000000000;
}


int main(int argc, char **argv) {
  printf("%" PRIi64, entry());
  return 0;
}

This program is a bit more complex than it needs to be for now. We’re separating out the entry and main functions because doing so will be useful later.

If you haven’t seen C before, that’s OK–all this program is doing is printing a string to the screen and then exiting. The reason we’ve written it in C is that we already have a compiler from C to machine code, gcc. So, let’s make sure our program works:

$ gcc -o program program.c
$ ./program
4000000000000$

OK, it seems to do the right thing (it’s just printing the number, not a newline). Let’s try to take a look at the code it produced!

$ cat program # the [cat] command prints out the contents of a file

This command results in a lot of unreadable garbage. That’s not very helpful! What’s going on here? Some of that stuff is actually x86-64 machine code, in binary format. Other parts are sort of boilerplate that tells the operating system how to execute this program. We can get a more useful output like this:

$ gcc -S -masm=intel -m64 program.c
$ cat program.s

	.section        __TEXT,__text,regular,pure_instructions
	.build_version macos, 10, 14    sdk_version 10, 14
	.intel_syntax noprefix
	.globl  _entry                  ## -- Begin function entry
	.p2align        4, 0x90
_entry:                                 ## @entry
	.cfi_startproc
## %bb.0:
	push    rbp
	.cfi_def_cfa_offset 16
	.cfi_offset rbp, -16
	mov     rbp, rsp
	.cfi_def_cfa_register rbp
	movabs  rax, 4000000000000
	pop     rbp
	ret
	.cfi_endproc
					## -- End function
	.globl  _main                   ## -- Begin function main
	.p2align        4, 0x90
_main:                                  ## @main
	.cfi_startproc
## %bb.0:
	push    rbp
	.cfi_def_cfa_offset 16
	.cfi_offset rbp, -16
	mov     rbp, rsp
	.cfi_def_cfa_register rbp
	sub     rsp, 32
	mov     dword ptr [rbp - 4], 0
	mov     dword ptr [rbp - 8], edi
	mov     qword ptr [rbp - 16], rsi
	call    _entry
	lea     rdi, [rip + L_.str]
	mov     rsi, rax
	mov     al, 0
	call    _printf
	xor     ecx, ecx
	mov     dword ptr [rbp - 20], eax ## 4-byte Spill
	mov     eax, ecx
	add     rsp, 32
	pop     rbp
	ret
	.cfi_endproc
					## -- End function
	.section        __TEXT,__cstring,cstring_literals
L_.str:                                 ## @.str
	.asciz  "%lli"


.subsections_via_symbols

This is called assembly language. It’s basically a human-readable form of machine-code. Translating between assembly language and machine code is a simple mechanical process; we call this assembling.

Let’s look at the code above. There are two big sections, starting with _entry and _main¹. These correspond to the two functions, entry and main, in our C code.

In order to write our compiler, we’re going to replace the entry function (we’ve called it that because it’s the entry point to the code our compiler is producing). We’re going to replace it with code that looks a lot like the code up there, but simpler. We’re going to split that code out into its own file, and that’s what our compiler will produce.

First, we’ll modify our C program:

#include <stdio.h>
#include <inttypes.h>

extern int64_t entry();

int main(int argc, char **argv) {
  printf("%" PRIi64, entry());
  return 0;
}

This program is called the runtime for our compiler. The runtime will be included in every program our compiler produces. Here, it just handles calling our function and printing the result. Later we’ll extend it to do more things.

Note that we’re writing the runtime in C, but we don’t have to–we could write it in assembly, or some other language that can produce machine code. C is a convenient language for this purpose, but it’s certainly not the only choice! Because we’ve written the runtime in C, C’s runtime gets included in our programs as well.

We can compile the runtime like this:

$ gcc -c runtime.c -o runtime.o

That -c is just telling GCC not to try to compile it into a whole program, but instead to make a chunk of machine code that we can then include in other programs.

Back to our entry function. We can write it in assembly language like this:

global _entry
_entry:
	mov rax, 4000000000000
	ret        

Line by line, this program:

1. Declares that it’s going to define one function, called _entry
2. Starts the _entry function
3. Writes the value 4000000000000 into the rax register. We’ll talk more about registers later; for now, the important thing is that by convention in x86-64, the return value of a function goes in rax.
4. Returns from the function.

We can build this program like this:

$ nasm program.s -f macho64 -o program.o # change "-f macho64" to "-f elf64" if you're on Linux

Finally, we can combine the runtime and the program:

$ gcc program.o runtime.o -o program
$ ./program
4000000000000$ 

I know, I know, here we are running another compiler after we just made our own! We wrote that runtime, and we wrote our assembly. Why do we need GCC again? All that’s happening here is it’s running something called a linker, telling these components how to talk to each other. If you want to see that it’s really just running the linker, go ahead and run:

$ gcc program.o runtime.o -o program --verbose

OK, so now we know what our compiler needs to do. It needs to turn a “program” like

4000000000000

into an assembly-language program like

global _entry
_entry:
	mov rax, 4000000000000
	ret        

Let’s write a program to do this! We’ll write our program in OCaml (a programming language we’ll discuss in much more detail next time). Here’s what it might look like:

let compile (program: string): string =
  String.concat "\n" 
  [ "global _entry"; 
  "_entry:"; 
  Printf.sprintf "\tmov rax, %s" program;
  "\tret" ]

This program just makes a list of our assembly-language lines and then glues them together with newlines.

We can see our compiler work if we open up an OCaml interaction environment:

$ utop

And in utop:

>>> #use "compile.ml";;
>>> print_endline (compile "4000000000000");;
global _entry
_entry:
	mov rax, 4000000000000
	ret        

We can glue everything together like this:

let compile (program: string) : string =
  String.concat "\n" 
  ["global _entry";
  "_entry:";
  Printf.sprintf "\tmov rax, %s" program;
  "\tret"]

let compile_to_file (program: string): unit =
  let file = open_out "program.s" in
  output_string file (compile program);
  close_out file

let compile_and_run (program: string): string =
  compile_to_file program;
  ignore (Unix.system "nasm program.s -f macho64 -o program.o");
  ignore (Unix.system "gcc program.o runtime.o -o program");
  let inp = Unix.open_process_in "./program" in
  let r = input_line inp in
  close_in inp; r

Now in our utop we can run:

>>> #use "compile.ml";;
>>> utop # compile_to_file "42";;
- : unit = ()      

And if we look back inside program.s, we’ll see 42.

And in utop we can run:

>>> utop # compile_and_run "7";;
- : string = "7"   

We see it produces 7. And we can pop out of utop and run:

$ ./program
7$ 

And again we see whatever number we provided as our input progam when we called compile_and_run.

So–that’s our first compiler. Next time, we’ll talk more about the language we’re trying to compile. We’ll also do a quick introduction to OCaml.