| Home | Classes | Papers | Essays | Short Fiction | About |

CS211: Compilation & Execution

Table of Contents

Introduction

In a previous lecture, we discussed a little bit about computer architecture. We learned that we can think of a computer as a machine which takes input, performs calculations based on that input, and returns output. What we're primarily interested in in this class is how we can write the "input" that the computer will use to perform calculations.

What is Machine Code?

Computers come in many different shapes and sizes, but, at base, they all follow the exact same design philosophy: there will be some internal unit which will read instructions to perform actions. In the case of a modern personal computer that philosophy is concretized by the Central Processing Unit (CPU). A familiar refrain is used by both the lowliest hacks and the holiest hackers in computer science: "The CPU is the brain of the computer". What they mean is that the CPU "drives" all of the components connected to the motherboard. All peripherals "listen" to what the CPU has to "say". But the CPU itself is "listening". What it's "listening" to are blocks of binary digits called words1.

A typical, simplified CPU loop is as follows:

  1. Fetch a binary word representing an instruction2
  2. Decode that word to determine the desired operation
  3. Execute the operation

This loop is performed for as long as the CPU is powered on.

All of these steps use a language tailored to the particular components of the given computer called machine code. This sort of code refers to the binary-to-instruction mappings provided by the instruction set manual of the target CPU. Below is a snapshot of the instruction set, in octal, that came with the CDC160A (the first microcomputer3):

OPCODE F E G Description
NOP 00 0X ---- No operation
HLT 77 00 ---- Terminates
ADN 06 XX ---- Add XX to A
LDN 04 XX ---- Load XX into A
STM 41 00 YYYY Store A into (i)YYYY

Where F is the Function Opcode, E is the "Execution Address", G is the second instruction word, A is the accumulator register, X is an octal operand, and Y is an octal address. So, if I wanted to perform the operation x = 2 + 1 I could write the following: 

04 02       # Load 2 into A
06 01       # Add 1 to A
41 00 0001  # Store A in memory (x)

In an unformatted binary blob it would look like: 

000100000001000110000010100001000000000000000001

which is closer to what the machine will "see". It is very difficult for human beings to parse the latter example which is why practically no one writes machine code directly when programming4. Many people, however, write in what's called an assembly language.

What is an Assembly Language?

Assembly languages are one rung up the ladder of abstraction relative to machine code. They provide readable, symbolic abstractions for the pure binary strings directly processed by the CPU. Below is a snapshot of x86-64 assembly code:

Operation Op1 Op2 Description
mov src dst dst = src
add src dst dst = dst + src

If I wanted to repeat the code from Listing 1 I could write: 

1: mov $2, %rdi  # Move constant 2 into register rdi
2: add $1, %rdi  # Add 1 to register rdi
3: mov %rdi, 0x1 # Store value of rdi into mem address 1 (x)

Here, instead of octal or binary values, I have symbols representing familiar words ("mov" for "move", "add" for addition, etc.). If I store the above code in a file called "simple_add.s", I can use an assembler to turn it into a binary file: 

1: as simple_add.s -o simple_add.o
2: objcopy -O binary --only-section=.text simple_add.o simple_add.bin

The first line invokes the GNU assembler, as, which turns the assembly code into an ELF file; the second line invokes objcopy which copies the contents of an object file to pure binary (the .text section is where code is stored in compiled files). If we try to directly cat out the .bin file we'll see a strange pseudo-binary string. This is because cat looks for UTF-8 encoded characters to print out to the screen, not unencoded binary strings! We can properly view the binary contents of the file with: 

xxd -b -c 1 simple_add.bin | awk '{printf("%s",$2)} END{print ""}'

Which should spit out the following: 

01001000110001111100011100000010000000000000000000000000010010001000001111000111000000010100100010001001001111000010010100000001000000000000000000000000

Wow! Over a hundred bits for only 3 short lines of assembly! Again, this should show you why it's not easy to program in machine code directly…but, even assembly looks a bit tough on the eyes. Both Listings 1 and 3 write more than one line of code to represent the logic of x = 2 + 1. The process that translates the x = 2 + 1 to the machine code seen above is called compilation.

What is Compilation?

Put simply, compilation is the translation of one computer language to another (Language A → Language B). Compilation is a rich and complex topic in computer science, and therefore not one we can spend much time on in class; however, it is important that you are aware of the basic steps of compilation needed to turn C source code into a runnable executable. Compilation begins with the compiler.

What is a Compiler?

A compiler is a program which translates computer code from one language to another. All compilers roughly follow the below path5: 

  position = initial + rate * 60
                |
                v
     +----------------------+
     |   Lexical Analyzer   |
     +----------------------+
                |
                v
  <id,1> <=> <id,2> <+> <id,3> <*> <60>
                |
                v
     +----------------------+
     |   Syntax Analyzer    |
     +----------------------+
                |
                v
        =
       / \
  <id,1>  +
         / \
    <id,2>  *
           / \
      <id,3>  60
                |
                v
     +----------------------+
     |   Semantic Analyzer  |
     +----------------------+
                |
                v
        =
       / \
  <id,1>  +
         / \
    <id,2>  *
           / \
      <id,3>  inttofloat
                    \
                     60
                |
                v
+--------------------------------+
|  Intermediate Code Generator  |
+--------------------------------+
                |
                v
     t1 = inttofloat(60)
     t2 = id3 * t1
     t3 = id2 + t2
     id1 = t3
                |
                v
     +----------------------+
     |    Code Optimizer    |
     +----------------------+
                |
                v
     t1 = id3 * 60.0
     id1 = id2 + t1
                |
                v
     +----------------------+
     |    Code Generator    |
     +----------------------+
                |
                v
     LDF   R2, id3
     MULF  R2, R2, #60.0
     LDF   R1, id2
     ADDF  R1, R1, R2
     STF   id1, R1

For this class we're mainly interested in the first three stages: lexical analysis, syntactical analysis, and semantic analysis. These represent three facets of a programming languge: its symbol set, structure, and rules. In other words, what "words" we can use, how we arrange those "words", and what those arrangements "mean". In the programming language world we group the first two under "syntax" and the one remaining under "semantics"—in reasonably complicated programming languages, like C, neither can be totally separated from one another.

Let's use an example in a language we all know very well: "The dog flew quite orangely this Mars." Each word exists within the symbol-set of the English language, i.e., they can all be found in a dictionary. Additionally, we can analyze the structure of the sentence:

  • "The dog"
    • noun phrase acting as subject. "The" is a definite article modifying the noun "dog."
  • "flew"
    • simple past tense intransitive verb, the predicate.
  • "quite orangely"
    • adverb phrase acting as adverbial modifier of "flew." "Quite" is an adverb of degree modifying the manner adverb "orangely."
  • "this Mars"
    • noun phrase acting as adverbial of time/place, modifying "flew." "This" is a demonstrative determiner modifying "Mars."

The sentence is well-formed, but it is completely devoid of semantic meaning—it's complete nonsense!6

Much the same, I can construct lines of C code which appear to be correct, but have no actual place in the language: "hello world" + 1. Syntactically, I have placed two operands on either side of an infix operator, but semantically I've tried to add the number one to a constant that represents a string of characters. Compilers exist to catch errors of this nature.

GCC

As this is a C course we will be using a C compiler. There are many different C compilers available to use, but we choose gcc or the GNU Compiler Collection due to its popularity and wide availability on Linux platforms. 

1: #include <stdio.h>
2: int main(){
3:   printf("Hello, World!\n");
4: }

For our purposes, using gcc is pretty easy7. If we have a C program, say hello_world.c (from Listing 8), we can compile it into an executable with the following command: gcc hello_world.c. gcc will automatically create an executable called a.out which can be run by specifying the path to it in the shell: 

josephraskind@stargazer:/tmp/hello$ gcc hello_world.c 
josephraskind@stargazer:/tmp/hello$ ls
a.out  hello_world.c
josephraskind@stargazer:/tmp/hello$ ./a.out 
Hello, World!

In the blink of an eye gcc expanded the include macros, went through every stage detailed in 7, called the assembler, as, and called the linker, ld! Each step in the process could be studied for weeks. We'll have to make do with occasionally referencing them when they're relevant.

What are Compilation Tools?

Compilation can be rather tricky to wrap one's head around, and it can get really overwhelming when you are working on a project that spans not just two files, but two hundred or two thousand files!8 This is where getting familiar with compilation tools can really pay off.

Make

Make is a popular compilation tool for C projects in Linux environments. It is yet another GNU tool which is often pre-installed in most Linux distros. Make has its own language, albeit one much more limited in scope than C, whose programs are stored in makefiles. The structure of a makefile looks a bit like this: 

1: VARIABLE = lorum
2: target: dependencies
3:       commands

Let's assume I still have my file hello_world.c. I can write a makefile to compile my program as follows: 

1: hello_world: hello_world.c
2:         gcc hello_world.c -o hello_world

I define the rule "hello world" (before the ":") which is dependent on the file hello_world.c. When the rule is triggered, make checks to see if hello_world.c needs to be compiled, i.e. "has it changed since the last compilation attempt?", then performs the set of commands defined beneath the rule. As long as there is a file named makefile or Makefile in my working directory I can invoke the file with a simple call to the make executable: 

josephraskind@stargazer:/tmp/hello$ make
gcc -Wall hello_world.c -o hello_world
josephraskind@stargazer:/tmp/hello$ ./hello_world 
Hello, World!
josephraskind@stargazer:/tmp/hello$ make
make: 'hello_world' is up to date.

You'll notice that a second call to make did not call gcc. This is significant for projects which have hundreds or thousands of C files which need to be compiled prior to producing an executable.

We can also add extra rules which perform various non-compilation tasks: 

1: hello_world: hello_world.c
2:     gcc hello_world.c -o hello_world
3: clean:
4:     rm hello_world

This makefile has a new "dummy" rule which will remove the executable from the working directory: 

josephraskind@stargazer:/tmp/hello$ ls
hello_world  hello_world.c  makefile
josephraskind@stargazer:/tmp/hello$ make clean
rm hello_world
josephraskind@stargazer:/tmp/hello$ ls
hello_world.c  makefile

make always calls the first rule by default!

We can use variables to further abstract our rules: 

1: FILE = hello_world
2: FLAGS = -Wall
3: CC = gcc
4: $(FILE): $(FILE).c
5:     $(CC) $(FLAGS) $(FILE).c -o $(FILE)
6: clean:
7:     rm $(FILE)

Now, instead of rewriting a makefile for every new single-shot file I write, I can just replace the "hello_world" at the top.

Be careful when copy-pasting makefile rules, make expects a TAB before every command!

If you do enough C programming, you will encounter makefiles. It's best to get familiar with them now in a low(er) stakes environment.

Exercises

  1. Using gcc, compile the hello world program from Listing 8 and run it. Then remove the quotations and see what happens. Reason about the output.
  2. Write a makefile for the hello world program that includes three rules: one to compile the program, one clean rule to remove the executable, and one run rule that compiles and immediately runs it. What happens when you call make run?
  3. Using the CDC160A instruction set from the lecture, write the machine code (in octal) to perform the operation x = 5 + 3. What would the equivalent x86-64 assembly look like?
  4. Assemble the x86-64 addition code from Listing 4 using as and objcopy. Then use the xxd command from Listing 6 to dump the raw binary. How many bits does the output contain? Does this match what you'd expect?
  5. Take the hello world makefile from Exercise 2 and convert it to use variables for the filename, compiler, and flags as shown in Listing 15. Then use it to compile a second program of your choice by only changing the variable at the top.
  6. The lecture states that cat cannot properly display a .bin file. Try it yourself, run cat simple_add.bin after assembling. Describe what you see and explain why it looks that way.
  7. The lecture mentions that gcc internally calls as and ld. Try compiling hello world manually step by step: first use gcc -S to produce assembly, then as to assemble it, then ld to link it. What errors or surprises do you encounter?
  8. A makefile rule only recompiles when its dependency has changed. Compile hello_world with make, then run make again without changing anything. Now touch hello_world.c (which updates its timestamp without changing its contents) and run make again. What happens and why?

Footnotes:

1

Word size varies depending on architecture. For this class, we focus on x86-64 which has a word size of 64 bits. Instructions are not always word length.

2

Instructions will come from a component called the Instruction Cache, or I-Cache.

3

A History of Modern Computing, Paul E. Ceruzzi.

4

There are exceptions, but this is true in the broad strokes.

5

Diagram transcribed from Compilers: Principles, Techniques, and Tools by Aho et al.

6

Noam Chomsky famously used the sentence "Colorless green ideas sleep furiously" in Syntactic Structures.

7

You will likely not feel like that at first. That's okay! The more you practice, the more it will start to make sense.

8

In this course we do not go beyond more than a few files in one project.

Previous | Index | Next

Contact: [email protected] | rss feed | Compiled with org-mode | Licensed under CC BY-NC-SA 4.0