▼(CPSC 411 2019W2 – Introduction to Compiler Construction
►5 Compiler 0:   x64 to elf64
On this page:
5.1 Assignment Summary
5.2 Language Diagram
5.3 Preface
5.4 x64:   The First Target Language
5.4.1 x64 by example
5.4.2 x64-linux
5.4.3 x64-macos
5.4.4 x64-windows
5.5 Testing Your Development Machine
5.6 x64 References
7.5.0.17
    ← prev  up  next → 

5 Compiler 0: x64 to elf64

5.1 Assignment Summary

The goal of this assignment is to ensure that you have a working environment to start writing your compiler. Modern compiler construction always starts from an existing language and toolchain. This assignment will instruct you to install and test the required tools.

This assignment is due Sunday, Jan 12, 2019 at 11:59pm.

Assignment Checklist
You should find a new repository in your https://github.students.cs.ubc.ca account named a0_<userid> with a code skeleton. The skeleton code is documented. You should complete the exercise in that git repository and push it to the GitHub Students instance.

If we patch the code skeleton after the release, the most recent version will be available here at a0-skeleton.rkt. A GitHub repo you can merge or rebase from will be available here at https://github.students.cs.ubc.ca/cpsc411-2019w-t2/a0_wilbowma.

5.2 Language Diagram

5.3 Preface

Throughout this course, each assignment will come in two parts: an existing target language, and a new source language. The target language will be the same as the source language from the previous week’s assignment. The goal of the assignment will be to identify limitations in the target language, design new abstractions that address those limitations, and implement a new source language with those abstractions. The implementation will be at least a compiler from source to target.

However, for the first compiler, we have a problem: there is no previous week’s target language.

5.4 x64: The First Target Language

The first target language is x86-64 plus system calls, which we will call x64 for short. We’ll start with a subset of this language and expand it slightly throughout the course.

As far as we are concerned, the first target language was not designed—it was discovered

Take a computer architecture course if you want to learn how it was designed.

It is the language of wild CPU found by geologists in cave somewhere, probably in the amazon. It is primordial. It is not sensible to ask questions like "why"—x64 is. And, because we want to talk to the CPU, we must deal with it.

In this course, we will use the NASM assembler to assemble x64 into binary machine code. It is easy to get NASM installed on all three major desktop operating systems.

We will also use Intel assembler syntax, as it maps more closely to familiar imperative language syntax.

5.4.1 x64 by example

To get started with x64, let’s consider the factorial function fact. In Racket, following the design recipe, we would simply write:

Examples:
; Natural Number -> Natural Number
; Takes a natural number n and returns the factorial of n.
; (fact 0) -> 1
; (fact 1) -> 1
; (fact 5) -> 120
> (define (fact n)
    (if (zero? n)
        1
        (* n (fact (sub1 n)))))
> (module+ test
    (require rackunit)
    (check-equal? (fact 0) 1)
    (check-equal? (fact 1) 1)
    (check-equal? (fact 5) 120))
> (fact 5)

120

We run this and the computer prints 120.

We can implement the equivalent computation in x64 as follows.
  global start   ; Declare starting block for linker.
   
  section .text                   ; Start of the "code"
   
  ;; Compute (fact 5)
  start:
    mov r8, 5
   
  ;; Compute the factorial of the value in r8.
  ;; Expects  r8 : Positive int64
  ;; Produces r9 : Positive int64, the result of the factorial of r8.
  fact:
    mov r9, 1                     ; Initialize accumulator to (fact 0).
   
  ;; Computes the factorial of r8 with accumulator r9
  fact_acc:
    cmp r8, 0                     ; compare r8 and 0, i.e., (zero? r8)
    je fact_done                  ; jump if last comparison was equal
    imul r9, r8                   ; (set! r9 (* r9 r8))
    dec r8                        ; (set! r8 (sub1 r8))
    jmp fact_acc                  ; (fact r8)
   
  fact_done:
  ;; Done. The result is in r9.
   
  section .data ; The data section. This is where we declare initialized memory locations.
   
  dummy: db 0
> nasm -f elf64 -o plain-fact-x64.o plain-fact-x64.s
> ld -e start -o plain-fact-x64.exe plain-fact-x64.o
> ./plain-fact-x64.exe
 

In this example, we just compute the result, which is stored in r9. Then, the machine happily tries to execute the next instruction in memory. There is no next instruction, so it executes whatever happens to be in that memory location. The program will hopefully crash with a SEGFAULT or SIGBUS error, but this depends on the operating system (OS).

This fact that the behavior depends on the OS is our first clue that this example is not implemented in just x86-64, the language of the CPU. Some of the code can depend critically on the operating system. For example, the linker for each OS assumes a different entry label for where to start executing (although you can usually override this default). The entry label is assumed to be "start" on macOS (at least, on some versions), "_start" on Linux, and "Start" on Windows (depending on the linker). On macOS, the .data section, which is used to declare initialized memory locations, cannot be empty. In this example, we don’t actually use the heap, so we just declare a dummy value to ensure compatibility with macOS. Most operating systems require that you explicitly "exit" the process, by calling an exit system call or function defined by the operating system. Each OS uses different system calls to interact with the rest of the operating system. This example is compatible with macOS, Linux, and Windows, as long as you specify "start" as the entry label, and don’t mind exiting with a bang.

Because of this critical dependence on the operating system, the target language in this course cannot really be "plain" x64—x64 is a family of programming languages, indexed by an operating system. In this class, we will never program the raw CPU—we will program the operating system. The CPU plus the operating system implements a different programming language than the CPU by itself. From a programming languages perspective, the operating system (e.g., Linux) is the run-time system for the x64 programming language (e.g., x64-linux).

Take an operating systems course if you want to know more about how to program the "raw" CPU to implement the "lowest" level of run-time systems.

In x64, the result of the computation is not implicitly returned like it is in Racket. Instead, we have to explicitly say what the result is, and how to communicate it to the user. To do this, we need system calls, to make the x64 code interact with the operating system.

5.4.2 x64-linux

In this course, we will assume you are running on a linux machine, and your compiler must produce code for x64-linux, so we start with examples of Linux system calls. System calls are x64 primitives provided by the operating system. Once we start using system calls, the code becomes operating system specific. We encourage you to try to support other operating systems by modifying your compiler to generate operating system specific parts based on the host machine, but all assignments must run on x64-linux.

There are multiple system calls we could use to return a value to the system. For example, we could modify the code to return a value as an exit code through the exit system call. The exit system call should be called to terminate any program, and can be given an exit code that can be returned to the parent process. Usually, the exit code indicates whether the process terminated normally (0) or not (non-zero). But we could just as well use it to return the value of factorial.

  global start
   
  section .text
   
  start:
    mov r8, 5
   
  fact:
    mov r9, 1
   
  fact_acc:
    cmp r8, 0
    je fact_done
    imul r9, r8
    dec r8
    jmp fact_acc
   
  fact_done:
  exit:
    mov     rax, 60         ; I'm about to call the OS sys_exit function
    mov     rdi, r9         ; The exit code is the value from r9.
    syscall
> nasm -f elf64 -o exit-fact-x64-linux.o exit-fact-x64-linux.s
> ld -e start -o exit-fact-x64-linux.exe exit-fact-x64-linux.o
> ./exit-fact-x64-linux.exe
> echo $?
> 120

Now, when fact completes, we call the exit system call. This requires we set the register rax to the value 60, which corresponds to the exit system call in Linux. This system call expects one argument, the exit code, passed in register rdi.

To compile this on Linux, we run nasm -f elf64 exit-fact-x64-linux.s -o exit-fact-x64-linux.o. This will generate an elf64 binary. The elf64 is a binary format used on Linux, and includes the x64 instructions and additional structure that allows the Linux operating system to control the binary. Next link the file by running ld -e start -o exit-fact-x64-linux.exe exit-fact-x64-linux.o, which essentially connects the binary to the operating system and any other external libraries. We can execute the file exit-fact-x64-linux.exe on the command line in the usual way, e.g. chmod +x exit-fact-x64-linux.exe; ./exit-fact-x64-linux.exe, and can get the result of the exit code using echo $? or echo $status, depending on your shell.

Most programming languages communicate their result by printing. Thankfully, the OS does provide a print system call. We could write the program below to print the answer instead of using the exit status, to get a somewhat friendly user interface.

  global start
   
  section .text
   
  start:
    mov r8, 5
   
  fact:
    mov r9, 1
   
  fact_acc:
    cmp r8, 0
    je fact_done
    imul r9, r8
    dec r8
    jmp fact_acc
   
  fact_done:
    mov r8, msg  ; Move the address of `msg` into `r8`.
    mov [r8], r9 ; move r9 into the 0th index of the address pointed to by r8.
   
  print_msg:
    mov     rax, 1      ; Say, "I'm about to call the OS sys_write function"
    mov     rdi, 1      ; And I want it to write to the standard output port
    mov     rsi, msg    ; The message to print is stored in msg
    mov     rdx, len    ; Length is len.
    syscall
   
  exit:
    mov     rax, 60
    mov     rdi, 0                ; The exit code is 0; normal.
    syscall
   
  section .data
   
  len:   equ   1         ; The constant 1, representing the length of the message.
  msg:   times len dw 0  ; A `len` length, in bytes, buffer, initialized to be full of 0.
> nasm -f elf64 -o fact-x64-linux.o fact-x64-linux.s
> ld -e start -o fact-x64-linux.exe fact-x64-linux.o
> ./fact-x64-linux.exe
x

To use the print system call, we need to create a memory buffer to store the message we wish to print. We do this in the data section by creating a label, msg:, and using the times keyword to allocate len bytes (indicated by dw) of space, and initializing each to 0. Then we call the print system call, number 1, specifying the standard output port as the file to print to by setting rdi to 1, specifying msg as the address to print from in rsi, and the length of the buffer in rdx. When we run the program, it prints the expected result—x.

Question: Why did this print x instead of 120?

5.4.3 x64-macos

macOS is very similar to Linux, and we can easily adapt the above examples to macOS. On macOS, there are 4 system call tables, computed by adding the system call number to a specific prefix. The BSD system call table, the most generic and Linux-like, uses the hex prefix #x2000000. The exit system call is system call 1 in the BSD table, so we use the system call number #x2000001. The example "exit-fact-x64-linux.s" from above is rewritten for macOS below.

  global start
   
  section .text
   
  start:
    mov r8, 5
   
  fact:
    mov r9, 1
   
  fact_acc:
    cmp r8, 0
    je fact_done
    imul r9, r8
    dec r8
    jmp fact_acc
   
  fact_done:
  exit:
    mov     rax, 0x2000001       ; I'm about to call the OS sys_exit function.
                                 ; Specifying the value in hex for readability,
                                 ; but could convert it to decimal for a simpler
                                 ; assembler.
    mov     rdi, r9              ; The exit code is the value from r9.
    syscall
   
  section .data
   
  dummy: db 0
> nasm -f macho64 -o exit-fact-x64-macos.o exit-fact-x64-macos.s
> ld -macosx_version_min 10.6 -e start -o exit-fact-x64-macos.exe exit-fact-x64-macos.o
> ./exit-fact-x64-macos.exe
> echo $?
> 120

To compile this file, we run nasm -f macho64 exit-fact-x64-macos.s exit-fact-x64-macos.o. macho64 is the binary formatted used by 64-bit macOS. To link, we run ld -macosx_version_min 10.6 -e start -o exit-fact-x64-macos.exe exit-fact-x64-macos.o. We need to specify a minimum macOS version number of 10.6, otherwise the linker will ignore the custom entry label and fail to link. We can execute the file exit-fact-x64-macos.exe on the command line in the usual way, and can get the result of the exit code using echo $? or echo $status, depending on your shell.

macOS also has a similar write system call: number 4 in the BSD table. The file fact-x64-linux.s is ported to macOS below.

  global start
   
  section .text
   
  start:
    mov r8, 5
   
  fact:
    mov r9, 1
   
  fact_acc:
    cmp r8, 0
    je fact_done
    imul r9, r8
    dec r8
    jmp fact_acc
   
  fact_done:
    mov r8, msg  ; Move the address of `msg` into `r8`.
    mov [r8], r9 ; move r9 into the 0th index of the address pointed to by r8.
   
  print_msg:
    mov     rax, 0x2000004    ; Say, "I'm about to call the OS sys_write function"
    mov     rdi, 1            ; And I want it to write to the standard output port
    mov     rsi, msg          ; The message to print is stored in msg
    mov     rdx, len          ; Length is len.
    syscall
   
  exit:
    mov     rax, 0x2000001
    mov     rdi, 0                ; The exit code is 0; normal.
    syscall
   
  section .data
   
  len:   equ   1         ; The constant 1, representing the length of the message.
  msg:   times len dw 0  ; A `len` length, in bytes, buffer, initialized to be full of 0.
> nasm -f macho64 -o fact-x64-macos.o fact-x64-macos.s
> ld -macosx_version_min 10.6 -e start -o fact-x64-macos.exe fact-x64-macos.o
> ./fact-x64-macos.exe
x

5.4.4 x64-windows

Windows does not allow user processes to perform system calls. Instead, we have to call kernel functions that provide similar functionality. The ExitProcess kernel function provides the same functionality as the exit system call on Linux and macOS. However, making a function call is more complex than making a system call. We have to declare external functions for the linker, and ensure we link with the library that includes that function.

  global Start   ; GoLink expects "Start"
    extern ExitProcess ; Declare that ExitProcess is an external symbol to be resolved by the linker.
   
  section .text
   
  Start:
    mov r8, 5
   
  fact:
    mov r9, 1
   
  fact_acc:
    cmp r8, 0
    je fact_done
    imul r9, r8
    dec r8
    jmp fact_acc
   
  fact_done:
  exit:
    mov rcx, r8                   ; Windows 64-bit calling convention uses rcx as first argument
    call ExitProcess              ; Windows doesn't expose system calls to user processes; call ExitProcess function to exit.
> nasm -f win64 -o exit-fact-x64-windows.o exit-fact-x64-windows.s
> golink /entry Start /fo exit-fact-x64-windows.exe exit-fact-x64-windows.o kernel32.dll
> ./exit-fact-x64-windows.exe
> echo $?
> 120

Windows also doesn’t ship with a linker. GoLink is a small, freely available linker. After downloading nasm and GoLink, you can compile using nasm -f win64 exit-fact-x64-windows.s -o exit-fact-x64-windows.o and link using golink /entry Start /fo exit-fact-x64-windows.exe exit-fact-x64-windows.o kernel32.dll.

5.5 Testing Your Development Machine

If you’re running your own Linux machine, I trust you can figure out how to install racket and nasm.

If you don’t have a Linux machine, you can use remote.students.cs.ubc.ca, which has the correct version of nasm and racket. You can sign up for an account at https://www.cs.ubc.ca/getacct/.

If you want a local development environment, you can use this Dockerfile to setup a development container that mirrors remote.students.cs.ubc.ca. This will install a container with all the appropriate build tools and version. We recommend editing the compiler assignment files in the host machine, mounting them in the Docker container, and running tests in the container. You can create a new image using docker image build -t cpsc411 https://www.students.cs.ubc.ca/~cs-411/2019w2//share/Dockerfile. Assuming your compilers assignments are in stored in the path ~/workspace/, you can launch a new container with access to your assignments via docker run -i -t -v ~/workspace:/app/workspace cpsc411.

Whichever you choose, the following exercises will make sure your machine is setup and working properly.

First, let’s ensure Racket is installed properly and the right version. You will need racket version 6.11 or higher.

Exercise 1: Run racket --version, and check that a message like "Welcome to Racket v7.4.0.1" is printed, and that the version is at least "v6.11".

Next, we’ll test nasm. We need nasm version 2.13 or higher.

Exercise 2: Run nasm --version, and check that a message like "NASM version 2.14.02" is printed and that the version is at least "2.13".

We also need to be sure racket can find "nasm".

Exercise 3: Run racket -e "(with-output-to-string (thunk (system \"nasm --version\")))", and check that a message like "NASM version 2.14.02" is printed and that the version is at least "2.13".

Now you should be able to compile the following file "fact.s"

  global start
   
  section .text
   
  start:
    mov r8, 5
   
  fact:
    mov r9, 1
   
  fact_acc:
    cmp r8, 0
    je fact_done
    imul r9, r8
    dec r8
    jmp fact_acc
   
  fact_done:
  exit:
    mov     rax, 60
    mov     rdi, r9
    syscall
> nasm -f elf64 -o fact.o fact.s
> ld -e start -o fact.exe fact.o
> ./fact.exe
> echo $?
> 120

Exercise 4: Compile and execute "fact.s" from the command line. You should observe 120 as the exit code.

We can compile and execute a file from Racket using system or system/exit-code to make calls to command line programs. This is how the last pass of the compiler will translate your code into an executable, and how you will test your compiler from Racket.

Exercise 5: Rename the the skeleton file a0-skeleton.rkt to fact.rkt. Complete all TODOs in the file. Run the file to ensure the test passes, using raco test fact.rkt.

5.6 x64 References

    ← prev  up  next →