3 a86: a Little Assembly Language

You need to let the little things that would ordinarily bore you suddenly thrill you.

3.1 Overview

x86 is an instruction set architecture (ISA), which is a fancy way of saying a programming language whose interpreter is implemented in hardware. Really, x86 is a family of instruction set architectures, and the first member of the family was 8086, a 16-bit ISA for Intel’s 8086 chipset.

x86 is old. It’s older than the professors teaching this class. But it lives on today in Intel and AMD based computers in the form x86-64, the 64-bit descendant of the 8086 language.

Because it’s old and because the design of each generation of x86 has had significant backwards compatability requirements and because modern processors are sophisticated pieces of machinery, the x86-64 language is, well, complicated. For example, Intel’s x86 software developer’s manual is 5,066 pages long. AMD’s manual is 3,242 pages.

x86-64 is going to be used as the target language of our compiler. We’ll build up a translation from a very high-level language, based on Racket, down to the very low-level langauge of x86-64.

However, that doesn’t mean we need to digest 8K+ pages of dense technical manuals. We will only use very small fraction of the x86-64 instruction set.

To make our lives easier, we will do what programming language designers often do, we will abstract the behemoth of x86-64 to a small, core language (which we call a86). Our compilers will target a86 and compiling from a86 to x86 as the last step in the compiler pipeline will be dead simple.

This chapter describes the a86 language.

3.2 Giving x86 a try

Before describing a86, let’s take a brief look at x86.

There are a few different human-readable formats for writing x86 assembly code, but we’ll be using the one supported by the Netwide Assembler (NASM).

Here’s an example x86 program, written using nasm syntax. The program has one global label called entry, which will be the main entry point for the program. This program computes the 36th triangular number, which will reside in register rax when the code returns.

The conventions for label names differ between Mac and Linux systems. On MacOS, you need to prefix all label names with an underscore, while on Linux you do not. So on a Mac, you would use the names _entry, _tri, and _done, while on Linux you would use entry, tri, and done.

This example is shown using the Linux naming convention, because that’s what operating system was used when this web page was built.

a86/tri.s

        default rel
        section .text
        global entry
entry:
        mov rbx, 36             ; the "input"
;;; tri: a recursive function for computing nth
;;; triangular number, where n is given in rbx.
tri:
        cmp rbx, 0              ; if rbx = 0, done
        je done
        push rbx                ; save rbx
        sub rbx, 1
        call tri                ; compute tri(rbx-1) in rax
        pop rbx                 ; restore rbx
        add rax, rbx            ; result is rbx+tri(rbx-1)
        ret
done:                           ; jump here for base case
        mov rax, 0              ; return 0
        ret

The nth triangular number is the sum of the integers from 0 to n, so the 36th triangular number is 0 + 1 + 2 + 3 + ... + 34 + 35 + 36.

This code is not intended to be a model of efficient computation, rather it demonstrates some important x86 instructions and shows how to compute in a recursive style, even at a low-level.

Without getting too bogged down in the details, here how the code works. Instructions execute one after another. There are a number of registers which can be used to hold values. This code makes use of the rax and rbx register (and some other registers are implicitly used and altered by the call, push, pop and ret instructions). The lines like entry:, tri:, and done: are not instructions, but labels – they are names for locations in the source code and can be used as the targets of jumps and calls.

Suppose we start executing at entry.

• mov rbx, 36 sets the rbx register to 36.

• cmp rbx 0 compares the value in register rbx to zero. Executing this instruction sets a flag in the CPU, which affects subsequent “conditional” instructions. In this program, the next instruction is a conditional jump.

• je done either jumps to the instruction following label done or proceeds to the next instruction, based on the state of the comparison flag. The je instruction jumps if the comparison was equal, so control jumps to done if rbx was 0 in this program. If not, the next instruction is executed.

• push rbx uses memory as a stack to save the value of rbx. Under the hood this is modifying a register that holds a pointer to the stack memory location (register rsp).

• sub rbx, 1 decrements rbx by 1.

• call tri performs something like a function call; it uses memory as a stack to save the current location in the code (which is where control should return to after the function has completed). After saving this return pointer, it jumps to the label tri. There aren’t really functions, but this uses the stack to mimic the call-and-return mechanism of functions.

• pop rbx uses the stack memory to pop off the top element and move it into rbx, adjusting the stack pointer appropriately. This has the effect of restoring rbx to the value saved earlier by the push, i.e. before the decrement and any changes done in the call to tri.

• add rax, rbx updates rax to hold rax plus rbx.

• ret does a “return,” i.e. it pops an address from the stack and jumps to it. In this case, the jump either returns from to a previous call to tri or to original caller of entry.

• mov rax, 0 this instruction is only reached from the earlier conditional jump. It sets rax to 0. This program computes its result in rax so this is saying that when rbx (the “input”) is 0, then (the “output”) is 0.

• ret does a “return,” either to a prior call to tri or the caller of entry.

Despite the lower-level mechanisms, this code computes in a way similar to a non-tail recursive definition of the tri function written in Racket:

(define (tri n)

(if (= n 0)

0

(+ n (tri (sub1 n)))))

(tri 36)

As an exercise to check your understanding, try writing a tail-recursive version of tri and the corresponding x86 code, which should not need to push anything to the stack or use the call instruction.

We can compile the tri.s assembly program to an object file with nasm:

The format argument should be macho64 on Mac OS and elf64 on Linux.

shell

> nasm -f elf64 -o tri.o tri.s

To run the object file, we will need to link with a small C program that can call the entry label of our assembly code and then print the result:

a86/main.c

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

int64_t entry();

int main(int argc, char** argv) {
  int64_t result = entry();
  printf("%" PRId64 "\n", result);
  return 0;
}

Notice that from the C program’s perspective, the assembly code defines what looks like a C function called entry that returns an int64_t result.

How does this work? When the C program calls entry it places a return pointer on the stack and jumps to entry. The fact that we decided to put the result in register rax was not arbitrary – that’s the register that by convention is used for a return value. When the assembly code executes it’s final ret instruction, it jumps back to C with the 36th triangular number in rax, which the C side knows is the return value. This convention is part of a larger set of conventions known as the Application Binary Interface. For a reference, see the Texts section of the notes.

We can compile the main.c C program to an object file with gcc:

shell

> gcc -c main.c -o main.o

Now we can make an executable by linking the two together:

shell

> gcc main.o tri.o -o tri

Finally, we can run the executable:

shell

> ./tri
666

There, of course, is a lot more to x86-64 than what’s been shown here. If you want to dig deeper, check the references in Texts. But now let’s turn to a86.

3.3 a86: Representing x86 Code as Data

Here we will employ one of the great ideas in computer science: we will represent programs as data. Rather than toil away at the level of x86, writing programs directly in nasm syntax, compiling, and running them, we will instead design a data type definition for representing x86 programs and compute programs.

Our representation will not be complete – this is going to help us simplify x86 down to something manageable. We won’t cover every instruction and we won’t cover every variation of the instructions we do cover.

An a86 program is a list of a86 instructions. Each instruction is represented as a structure, described in the following section.

Before working through these examples, you’ll need to install the a86 module, part of the langs package for this course. See The langs package for details on installing.

Here’s the triangular number example:

%, %%, and %%% are constructors for assembly comments.

Examples

; import the a86 library

> (require a86)

; a86 code that computes the 36th triangular number

> (define tri-36     (list (Global 'entry)           (Label 'entry)           (Mov 'rbx 36)     (% "the \"input\"")           (%%% "tri: a recursive function for computing nth")           (%%% "triangular number, where n is given in rbx.")           (Label 'tri)           (Cmp 'rbx 0)      (% "if rbx = 0, done")           (Je 'done)           (Push 'rbx)       (% "save rbx")           (Sub 'rbx 1)           (Call 'tri)       (% "compute tri(rbx-1) in rax")           (Pop 'rbx)        (% "restore rbx")           (Add 'rax 'rbx)   (% "result is rbx+tri(rbx-1)")           (Ret)           (Label 'done)     (% "jump here for base case")           (Mov 'rax 0)      (% "return 0")           (Ret)))

So for example, let’s say you have two a86 programs and you want to glue them together into one: well that just append. Suppose you want to compute which registers are used in a given a86 program? Suppose you want to replace uses of 'rax with 'rdi? It just a matter of writing the right Racket function to do it.

Here’s another immediate benefit. Instead of writing a single x86 program, let’s write an infinite set of a86 programs, one for computing each nth triangular number. Easy-peasy:

Examples

; Natural -> a86

; Computes a86 code that computes the nth triangular number

> (define (tri n)     (list (Global 'entry)           (Label 'entry)           (Mov 'rbx n)      (% "the \"input\"")           (%%% "tri: a recursive function for computing nth")           (%%% "triangular number, where n is given in rbx.")           (Label 'tri)           (Cmp 'rbx 0)      (% "if rbx = 0, done")           (Je 'done)           (Push 'rbx)       (% "save rbx")           (Sub 'rbx 1)           (Call 'tri)       (% "compute tri(rbx-1) in rax")           (Pop 'rbx)        (% "restore rbx")           (Add 'rax 'rbx)   (% "result is rbx+tri(rbx-1)")           (Ret)           (Label 'done)           (Mov 'rax 0)           (Ret)))

; recreate original program

> (define tri-36 (tri 36))

It’s also easy to go from our data representation to its interpretation as an x86 program.

There is a function provided for printing an a86 program as an x86 program using nasm notation, called asm-display. Calling this function prints to the current output port, but it’s also possible to write the output to a file or convert it to a string.

The asm-display function knows what OS you are using and adjusts the label naming convention to use underscores or not, so that you don’t have to worry about it.

Examples

> (asm-display (tri 36))

default rel         section .text         global entry entry:         mov rbx, 36             ; the "input" ;;; tri: a recursive function for computing nth ;;; triangular number, where n is given in rbx. tri:         cmp rbx, 0              ; if rbx = 0, done         je done         push rbx                ; save rbx         sub rbx, 1         call tri                ; compute tri(rbx-1) in rax         pop rbx                 ; restore rbx         add rax, rbx            ; result is rbx+tri(rbx-1)         ret done:         mov rax, 0         ret

Notice how this generates exactly what you saw in tri.s.

From here, we can assemble, link, and execute.

We can also, since we have a general purpose programming language at our disposal in the meta-language, write a program to do all that for us:

Examples

> (asm-interp (tri 36))

666

The asm-interp function consumes an a86 program as input and produces the integer result the program computes, i.e. it is an Interpreter for a86. Behind the scenes it does this by converting to nasm, assemblying, compiling a thin C wrapper, executing the program, and reading the result. This will be a rather handy tool both in interactively exploring the a86 language (you can write assembly in a REPL), but also an important tool when it comes time to test the compilers we write.

3.4 Stacks: pushing, popping, calling, returning

The a86 execution model includes access to memory that can be used as a stack data structure. There are operations that manipulate the stack, such as Push, Pop, Call, and Ret, and the stack register pointer 'rsp is dedicated to the stack. Stack memory is allocated in “low” address space and grows downward. So pushing an element on to the stack decrements 'rsp.

The stack is useful as a way to save away values that may be needed later. For example, let’s say you have two (assembly-level) functions and you want to produce the sum of their results. By convention, functions return their result in 'rax, so doing something like this won’t work:

(seq (Call 'f)

(Call 'g)

(Add 'rax ...))

The problem is the return value of 'f gets clobbered by 'g. You might be tempted to fix the problem by moving the result to another register:

(seq (Call 'f)

(Mov 'rbx 'rax)

(Call 'g)

(Add 'rax 'rbx))

This works only so long as 'g doesn’t clobber 'rbx. In general, it might not be possible to avoid that situation. So the solution is to use the stack to save the return value of 'f while the call to 'g proceeds:

(seq (Call 'f)

(Push 'rax)

(Call 'g)

(Pop 'rbx)

(Add 'rax 'rbx))

This code pushes the value in 'rax on to the stack and then pops it off and into 'rbx after 'g returns. Everything works out so long as 'g maintains a stack-discipline, i.e. the stack should be in the same state when 'g returns as when it was called.

We can make a complete example to confirm that this works as expected. First let’s set up a little function for letting us try out examples:

Examples

> (define (eg asm)     (asm-interp      (prog       (Global 'entry)       (Label 'entry)       asm  ; the example code we want to try out       (Ret)          (Label 'f)      ; calling 'f returns 36       (Mov 'rax 36)       (Ret)          (Label 'g)      ; calling 'g returns 6, but       (Mov 'rbx 4)    ; it clobbers 'rbx just for the lulz       (Mov 'rax 6)       (Ret))))

Now let’s try it, using the stack to confirm it does the right thing:

Examples

> (eg (seq (Call 'f)            (Push 'rax)            (Call 'g)            (Pop 'rbx)            (Add 'rax 'rbx)))

42

Compare that with the first version that used a register to save the result of 'f:

Examples

> (eg (seq (Call 'f)            (Mov 'rbx 'rax)            (Call 'g)            (Add 'rax 'rbx)))

10

The Push and Pop instructions offer a useful illusion, but of course, there’s not really any data structure abstraction here; there’s just raw memory and registers. But so long as code abides by conventions, the illusion turns out to be the true state of affairs.

What’s really going on under the hood of Push and Pop is that the 'rsp register is decremented and the value is written to the memory location pointed to by the value of 'rsp.

The following code is equivalent to what we wrote above:

Examples

> (eg (seq (Call 'f)            (Sub 'rsp 8)                ; "allocate" a word on the stack            (Mov (Offset 'rsp 0) 'rax)  ; write 'rax to top frame            (Call 'g)            (Mov 'rbx (Offset 'rsp 0))  ; load top frame into 'rbx            (Add 'rsp 8)                ; "deallocate" word on the stack            (Add 'rax 'rbx)))

42

As you can see from this code, it would be easy to violate the usual invariants of stack data structure to, for example, access elements beyond the top of the stack. The value of Push and Pop is they make clear that you are using things in a stack-like way and they keep you from screwing up the accesses, offsets, and adjustments to 'rsp.

Just as Push and Pop are useful illusions, so too are Call and Ret. They give the impression that there is a notion of a procedure and procedure call mechanism in assembly, but actually there’s no such thing.

Think for a moment about what it means to “call” 'f in the examples above. When executing (Call 'f), control jumps to the instruction following (Label 'f). When we then get to (Ret), somehow the CPU knows to jump back to the instruction following the (Call 'f) that we started with.

What’s really going on is that (Call 'f) is pushing the address of subsequent instruction on to the stack and then jumping to the label 'f. This works in concert with Ret, which pops the return address off the stack and jumping to it.

Just as we could write equivalent code without Push and Pop, we can write the same code without Call and Ret.

We do need one new trick, which is the Lea instruction, which loads an effective address. You can think of it like Mov except that it loads the address of something rather than what is pointed to by an address. For our purposes, it is useful for loading the address of a label:

(Lea 'rax 'f)

This instruction puts the address of label 'f into rax. You can think of this as loading a function pointer into 'rax. With this new instruction, we can illuminate what is really going on with Call and Ret:

Examples

> (eg (seq (Lea 'rax 'fret)  ; load address of 'fret label into 'rax            (Push 'rax)       ; push the return pointer on to stack            (Jmp 'f)          ; jump to 'f            (Label 'fret)     ; <– return point for "call" to 'f            (Push 'rax)       ; save result (like before)            (Lea 'rax 'gret)  ; load address of 'gret label into 'rax            (Push 'rax)       ; push the return pointer on to stack            (Jmp 'g)          ; jump to 'g            (Label 'gret)     ; <– return point for "call" to 'g            (Pop 'rbx)        ; pop saved result from calling 'f            (Add 'rax 'rbx)))

42

The above shows how to encode Call as Lea, Push, and Jmp. The encoding of Ret is just:

(seq (Pop 'rbx)

(Jmp 'rbx))

3.5 a86 Reference

The a86 language may evolve some over the course of the semester, but we will aim to document any changes by updating this section. Also, because the run-time system changes for each language, you may need to do some work to have asm-interp cooperate with your run-time system.

This module provides all of the bindings from a86/ast,a86/printer, and a86/interp, described below

3.6 Instruction set

This section describes the instruction set of a86.

There are 16 registers: 'rax, 'rbx, 'rcx, 'rdx, 'rbp, 'rsp, 'rsi, 'rdi, 'r8, 'r9, 'r10, 'r11, 'r12, 'r13, 'r14, and 'r15. These registers are 64-bits wide. There is also 'eax which accesses the lower 32-bits of 'rax. This is useful in case you need to read or write 32-bits of memory.

Each register plays the same role as in x86, so for example 'rsp holds the current location of the stack.

Labels must also follow the NASM restrictions on label names: "Valid characters in labels are letters, numbers, _, $, #, @, ~, ., and ?. The only characters which may be used as the first character of an identifier are letters, . (with special meaning), _ and ?."

Examples

> (label? 'foo)

#t

> (label? "foo")

#f

> (label? 'rax)

#f

> (label? 'foo-bar)

#f

> (label? 'foo.bar)

#t

Examples

> (64-bit-integer? 0)

#t

> (64-bit-integer? (sub1 (expt 2 64)))

#t

> (64-bit-integer? (expt 2 64))

#f

> (64-bit-integer? (- (expt 2 63)))

#t

> (64-bit-integer? (sub1 (- (expt 2 63))))

#t

Examples

> (32-bit-integer? 0)

#t

> (32-bit-integer? (sub1 (expt 2 32)))

#t

> (32-bit-integer? (expt 2 32))

#f

> (32-bit-integer? (- (expt 2 32)))

#t

> (32-bit-integer? (sub1 (- (expt 2 32))))

#f

Examples

> (seq)

'()

> (seq (Label 'foo))

(list (Label 'foo))

> (seq (list (Label 'foo)))

(list (Label 'foo))

> (seq (list (Label 'foo)              (Mov 'rax 0))        (Mov 'rdx 'rax)        (list (Call 'bar)              (Ret)))

(list  (Label 'foo)  (Mov 'rax 0)  (Mov 'rdx 'rax)  (Call 'bar)  (Ret))

• Programs have at least one label; the first label is used as the entry point.

• All label declarations are unique.

• All label targets are declared.

• ... other properties may be added in the future.

This function is useful to do some early error checking over whole programs and can help avoid confusing NASM errors. Unlike seq it should be called at the outermost level of a function that produces a86 code and not nested.

Examples

> (prog (Label 'foo))

(list (Label 'foo))

> (prog (list (Label 'foo)))

(list (Label 'foo))

> (prog (Mov 'rax 32))

prog: no initial label found

> (prog (Label 'foo)         (Label 'foo))

prog: duplicate label declaration found: 'foo

> (prog (Jmp 'foo))

prog: undeclared labels found: '(foo)

> (prog (Label 'foo)         (Jmp 'foo))

(list (Label 'foo) (Jmp 'foo))

Examples

> (asm-display     (prog (%%% "Start of foo")           (Label 'foo)           ; Racket comments won't appear           (%% "Inputs one argument in rdi")           (Mov 'rax 'rdi)           (Add 'rax 'rax)    (% "double it")           (Sub 'rax 1)       (% "subtract one")           (%% "we're done!")           (Ret)))

default rel         section .text ;;; Start of foo foo:         ;; Inputs one argument in rdi         mov rax, rdi         add rax, rax            ; double it         sub rax, 1              ; subtract one         ;; we're done!         ret

Examples

> (Offset 'rax 0)

(Offset 'rax 0)

> (Offset 'rax 4.1)

Offset: expects exact integer as second argument; given 4.1

Examples

> (Label 'fred)

(Label 'fred)

> (Label "fred")

Label: expects symbol; given "fred"

> (Label 'rax)

Label: cannot use register as label name; given 'rax

> (Label 'fred-wilma)

Label: label names must conform to nasm restrictions

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Call 'f)     (Add 'rax 1)     (Ret)     (Label 'f)     (Mov 'rax 41)     (Ret)))

42

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Ret)))

42

Either dst or src may be offsets, but not both.

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rbx 42)     (Mov 'rax 'rbx)     (Ret)))

42

> (Mov (Offset 'rax 0) (Offset 'rbx 0))

Mov: cannot use two memory locations; given (Offset 'rax 0),

(Offset 'rbx 0)

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 32)     (Add 'rax 10)     (Ret)))

42

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 32)     (Sub 'rax 10)     (Ret)))

22

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Cmp 'rax 2)     (Jg 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

42

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Jmp 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

42

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Pop 'rbx)     (Jmp 'rbx)))

42

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Cmp 'rax 2)     (Je 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

0

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Cmp 'rax 2)     (Jne 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

42

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Cmp 'rax 2)     (Jl 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

0

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 42)     (Cmp 'rax 2)     (Jg 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

42

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax (sub1 (expt 2 63)))     (Add 'rax 1)     (Jo 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

-9223372036854775808

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax (sub1 (expt 2 63)))     (Add 'rax 1)     (Jno 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

0

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax -1)     (Add 'rax 1)     (Jc 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

0

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax -1)     (Add 'rax 1)     (Jnc 'l1)     (Mov 'rax 0)     (Label 'l1)     (Ret)))

0

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 0)     (Cmp 'rax 0)     (Mov 'r9 1)     (Cmove 'rax 'r9)     (Ret)))

1

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 2)     (Cmp 'rax 0)     (Mov 'r9 1)     (Cmove 'rax 'r9)     (Ret)))

2

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 0)     (Cmp 'rax 0)     (Mov 'r9 1)     (Cmovne 'rax 'r9)     (Ret)))

0

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 2)     (Cmp 'rax 0)     (Mov 'r9 1)     (Cmovne 'rax 'r9)     (Ret)))

1

Examples

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax 0)     (Cmp 'rax 0)     (Mov 'r9 1)     (Cmovl 'rax 'r9)     (Ret)))

0

> (asm-interp    (prog     (Global 'entry)     (Label 'entry)     (Mov 'rax -1)     (Cmp 'rax 0)     (Mov 'r9 1)     (Cmovl 'rax 'r9)     (Ret)))

1