Please do not redistribute these slides without prior written permission

1

CS 3650

Computer Systems

Dr. Alden Jackson

2

Course Logistics

• Homework 3 has been released!
• Make sure you are doing the readings on the syllabus before class!
• They will help prepare you!
• See Mike Shah’s 3650 site for a recording of his lecture:

http://www.mshah.io/comp/Fall18/Systems/index.html

​

​

3

Last Class

• We were in Lab
• We worked in Assembly!
• Mea culpa - godbolt.org oddities
• Forgot to set the intel switch: output was not x86-64 assembly
• The operands are reversed (DEST, SRC, not SRC, DEST)
• Memory offsets: 1480 vs 1600
• Using the 128 byte stack "red zone" for the extra array space (1480+128 = 1608)
• This area is reserved and can be used for entire stack frame for leaf functions
• For more details and a picture, see https://eli.thegreenplace.net/2011/09/06/stack-frame-layout-on-x86-64/

4

Lecture 4 - Compilers, Linkers

Dr. Alden Jackson

Question: “Any advice for the future?

Answer: Yes, I do have one thing. Students aren't joining our field, computer science, and I don't know why. It's just such an amazing field, and it's changed the world, and we're just at the beginning of the change. We have to find a way to get our excitement out to be more publicly visible. It is exciting—in the 50 years that I've been involved, the change has been astounding.

” - Frances Allen

6

Frances Allen

• Contributed to compilers, code optimization, parallelization
• First woman to win the Turing award in 2006
• (More her interview here)
• (More on getting good at optimizations and compilers to be covered)
• https://www.youtube.com/watch?v=fHNmRkzxHWs
• https://www.youtube.com/watch?v=UHv_Jog9Xuc

​

7

Compilers

8

Compilers have their hands everywhere!

• They have to!
• So it makes them interesting to study and figure out how we can use them as tools
• (We’ll also see a Linker which really also has control over everything with slightly different information)

9

Compilation Pipeline

• This has turned out to be a pretty important diagram!
• (A journey from C program to executable!)
• Let’s continue investigating each step a little more in-depth.

10

The C preprocessor [More info]

• Before we even get to compiling the code, the C preprocessor runs.
• The preprocessor takes care of anything that starts with ‘#’ in C/C++
• Let’s look at an example.

11

preprocessor.c example

• So here’s an example C program.
• You’ll notice a few things with pound (i.e. #) symbols followed by define.
• This program will compile, run, and print “Hello” with a newline.
• This is because the preprocessor does a ‘text’ substitution first, before compiling the code.

12

preprocessor.c example | gcc -E preprocessor.c

• You can use the “-E” option to output the code after the preprocessor.
• Notice (to the right) a piece of the code, and the substitution of our #define has taken place.

13

preprocessor.c example | gcc -E preprocessor.c

• There are more pieces as well, such as ‘printf’.
• printf is actually declared in the <stdio.h> library file.
• So the preprocessor expands this file within our C file providing a definition (as well as for many other functions in stdio.h)

14

preprocessor.c example | gcc -E preprocessor.c

• More on compilation options (including -E) here: https://gcc.gnu.org/onlinedocs/gcc-4.5.3/gcc/Overall-Options.html#Overall-Options

15

preprocessor2.c example | gcc -E preprocessor.c

• Here is a quick example on conditional compilation

16

preprocessor2.c example | gcc -E preprocessor.c

• Here is a quick example on conditional compilation

17

preprocessor3.c example | gcc -E preprocessor.c

• Here is a quick example on MACROS
• A MACRO ‘expands’ some piece of code
• (image on left is code, on right the output, and bottom-right the expansion

18

Already a few ideas in stage 1 with the preprocessor

1. Our programs undergo transformations
2. There are libraries of code that are, or otherwise need to be brought into our code.

19

Stage 1!

Stage 2: The compiler

20

Stage 2!

21

Let’s now take a look at the stages of compiling a program

22

Consider this a mini-crash course--take a full compilers course for more

A Compiler has two phases

• A compiler is typically broken into two phases
• The front end
• The back end

23

A Compiler has two phases

​

• A compiler is typically broken into two phases
• The front end
• The back end

24

The front ends main responsibility is to build an intermediate representation from which code can be generated.

A Compiler has two phases

​

• A compiler is typically broken into two phases
• The front end
• The back end

25

The front ends main responsibility is to build an intermediate representation (i.e. not C code) from which code can be generated.

A Compiler has two phases

• A compiler is typically broken into two phases
• The front end

​

​

• The back end

26

Job is to generate code (10010101...) on our machine

[Front End]

Scanning (Lexical Analysis)

27

Scanning (Lexical analysis)

• To perform a lexical analysis.
• We read an input (a text file of our source language) and process that as a stream of characters
• Our goal is to generate tokens (otherwise known as individual lexemes).
• This process is known as lexing or tokenization.

28

Scanning (Lexical analysis)

• Given part of a character stream: if( x > 3.1
• This is broken into:
• KEYWORD: if
• Left_Paren
• IDENTIFIER: x
• Greater_than_operator
• float: 3.1
• This stream is broken into these individual lexem’s by a space or other delimiter
• (Note a ‘lexeme’ is something indivisible like “3.1” “x” or a variable named “mike”)

29

Scanning (Lexical analysis)

• Given part of a character stream: if( x > 3.1
• This is broken into:
• KEYWORD: if
• Left_Paren
• IDENTIFIER: x
• Greater_than_operator
• float: 3.1
• This stream is broken into these individual lexem’s by a space or other delimiter
• (Note a ‘lexeme’ is something indivisible like “3.1” “x” or a variable named “mike”)

30

Now each individual lexeme is categorized into tokens.

Scanning (Lexical analysis)

• Given part of a character stream: if( x > 3.1
• This is broken into:
• KEYWORD: if
• Left_Paren
• IDENTIFIER: x
• Greater_than_operator
• float: 3.1
• This stream is broken into these individual lexem’s by a space or other delimiter
• (Note a ‘lexeme’ is something indivisible like “3.1” “x” or a variable named “mike”)

31

Now each individual lexeme is categorized into tokens.

However, we do not know if we have a valid program yet!

[Front End]

Parsing (Syntactic Analysis)

32

Parsing (Syntactic Analysis)

• This is the step of figuring out if we have a valid program.
• That is, did the user input symbols and lines of source that have a valid meaning in our “C” language.
• Our goal at this stage is to convert our ‘stream of tokens’ from the previous steps into an abstract syntax tree (AST).
• The tree data structure that we are building is determined by the grammar.
• An example of the English grammar is below [wiki]

33

S = Sentence

NP = Noun Phrase

VP = Verb Phrase

V = Verb

Adv = Adverb

A = Adjective

Parsing (Syntactic Analysis)

• This is the step of figuring out if we have a valid program.
• That is, did the user input symbols and lines of source that have a valid meaning in our “C” language.
• Our goal at this stage is to convert our ‘stream of tokens’ from the previous steps into an abstract syntax tree (AST).
• The tree data structure that we are building is determined by the grammar.
• An example of the English grammar is below [wiki]

34

A syntactically correct sentence (but semantically does not make sense) [source]

Context-free Grammar (CFG)

• Similar to the English language, programming languages follow rules.
• We build what is called a Context-free Grammar which identifies the rules of our language.
• That is, if we are given a stream of tokens, would these tokens make a valid sentence.
• English
• The fox jumps over the log -- valid
• The jumps log fox over the -- invalid stream of tokens (subject and verb placement error!)

35

Context-free Grammar (CFG) Example

• (Explanation on next slide)

36

Context-free Grammar (CFG) Definitions

• Terminal symbols - Alphabet of our language
• Nonterminals - Symbols defined in terms of other terminals and nonterminals
• Productions - Rules for how a nonterminal is defined in terms of a sequence of other symbols.
• Start symbol -- Where do we begin, typically main

37

Context-free Grammar (CFG) Definitions

• Terminal symbols - Alphabet of our language
• Nonterminals - Symbols defined in terms of other terminals and nonterminals
• Productions - Rules for how a nonterminal is defined in terms of a sequence of other symbols.
• Start symbol -- Where do we begin, typically main

38

Production is some rule or sequence of rules. It also happens to be our ‘start rule’ listed at the top.

Context-free Grammar (CFG) Definitions

• Terminal symbols - Alphabet of our language
• Nonterminals - Symbols defined in terms of other terminals and nonterminals
• Productions - Rules for how a nonterminal is defined in terms of a sequence of other symbols.
• Start symbol -- Where do we begin, typically main

39

Terminal symbol for the production ‘Program’. It consists of 1 Statement token ‘Stmt’

Context-free Grammar (CFG) Definitions

• Terminal symbols - Alphabet of our language
• Nonterminals - Symbols defined in terms of other terminals and nonterminals
• Productions - Rules for how a nonterminal is defined in terms of a sequence of other symbols.
• Start symbol -- Where do we begin, typically main

40

The right hand side here are terminal symbols

Context-free Grammar (CFG) Definitions

• Terminal symbols - Alphabet of our language
• Nonterminals - Symbols defined in terms of other terminals and nonterminals
• Productions - Rules for how a nonterminal is defined in terms of a sequence of other symbols.
• Start symbol -- Where do we begin, typically main

41

The left hand side here are nonterminal symbols. (That is, they consist of other things after them)

Parsing

• So if we get a stream of tokens for simply ‘Stmt’, then our program is valid if we find something of the form.
• if (0) then 1 else 2
• A stream of tokens for:
• if (if if) then 1 else 2
• ^ this is invalid, we cannot have two terminal symbol tokens ‘if’ together (there is no production).

42

Abstract Syntax Tree (AST) and Concrete Trees

• Given a valid stream of tokens (verified by our parser)we can then build an abstract syntax tree
• This is a tree data structure
• Given the actual symbols, we can build concrete trees, to follow operations.
• Let’s look at some examples given a production rule for computing expressions.

43

E-> E*E (Concrete Tree)

In English:Starting from the bottom left, I find E, then traverse up the tree, then down to the next child, and then up, and then to the rightmost E.

44

E-> E*E (Follow the red arrows)

In English:Starting from the bottom left, I find E from the root, then traverse up the tree, then down to the next child, and then up, and then to the rightmost E.

45

E-> identifier + E * E (A slightly larger example)

46

A Note on Abstract Syntax Trees/Concrete Trees

​

• There are a variety of ways to traverse a tree
• Depending on how we traverse the tree and form our grammar, it could be ambiguous.
• That is, the same stream of tokens would have two different meanings.
• ^This is frowned upon!
• From this tree, we can generate an intermediate representation of code by traversing the tree (example coming up)
• But first--we need to discuss semantic analysis
• I showed a concrete tree because it maps nicely, an abstract tree may have replaced ‘+’ with ‘PLUS’

47

Example AST | x=1 y=2 3* x+y;

(We can derive the full parse tree from this--AST is more condensed)�(Full parse tree may be x=1; y=2; 3*(x+y);

48

[Front End]

Semantic Analysis

49

Semantic Analysis

• The linguistics definition of semantic analysis is that given a set of words, a sensible relationship can be formed.
• e.g. “Sly as a fox”
• In compilers however, the definition is a little more strict, in that our programs must verifiably have a meaningful relationship.
• Statements we make must be correct.
• 0 = 1 does not make sense (both in English and a compiler)
• “joe” = 1234 does not make sense
• The above is an example of ‘type checking’

50

Symbol Table

• During our parsing phase (syntax analysis), a symbol table is built
• The symbol table keeps track of variables, and their type information.
• Example:
• ​

51

Symbol Table

• We notice the name of a variable or function, what it is (KIND, a function, parameter, variable), type (int, bool, etc.), and any OTHER qualifiers.
• (Often implemented as a ‘hash table’ for speed.)

52

Using symbol information for Type-checking

• Make sure every time we declare something as an ‘int’, it is used in contexts of an int.
• This includes things like matching function arguments.
• Sometimes values may be cast (coerced) into others.
• e.g. A float can act as an int, but it will get truncated.
• i.e. 3.14 will become 3 // sometimes this will give a warning, sometimes not!

53

Type-checking

• The type-checker also makes sure that you are only using code that has previously been declared before its first use.
• You can use something called ‘forward declaring’ to tell the compiler a function/variable exists.
• In assembly we do not have any real notion of this, in the sense that we can ‘jmp’ to any valid address. But in C, the type-system is trying to prevent us from making mistakes.

54

So how might we verify types? (Part of semantic analysis)

• Traverse our AST (or parse tree)
• Anytime we find a symbol, look it up in our symbol table
• Verify that both sides of the equation match.

55

So how might we verify types? (Part of semantic analysis)

• Traverse our AST (or parse tree)
• Anytime we find a symbol, look it up in our symbol table
• Verify that both sides of the equation match.

56

If our symbol table says ‘x’ is an int, then the right side better also be an integer value

Generation of intermediate Language

57

AST-> Intermediate representation (IR)

• From our abstract syntax tree(AST), we can generate the intermediate representation
• Prior to this step, we have verified we have valid and semantically correct programs.
• Some compilers might skip this IR stage completely if there is only 1 target language
• i.e. if only one translation needs to be made, then do not do any extra work.
• Why might this be a bad idea?

58

GCC, and Clang compiler IR

• GCC has an intermediate form known as RTL
• (Register Transfer Language)
• http://engels.mortega.net/index.php?entry=20041217093918
• Clang is another ‘C compiler’ that has an intermediate form called bitcode (sometimes just referred to as ‘the IR’)

59

Clang’s LLVM framework has an intermediate form called bitcode

• Here is an example of Clang’s IR (which is a bit more readable)
• Here is what a conditional statement may look like when converted to an intermediate form.

​

60

Intermediate Representations

• Most intermediate representations look quite similar to ASM actually!
• Typically they are more compact and flexible
• We however:
• do not have to worry about registers
• (We have infinite)
• do not have to worry about types
• Can have one or two types of instructions
• say sdiv and div instead of
• divq, divl, divb, idiv, etc.

61

[Typically the Middle End if it exists]

Code Optimization

62

Code Optimization

• This stage is where we perform various code optimizations
• Dead code elimination
• code motion
• loop unrolling, etc
• Typically this is done by manipulating the intermediate representation
• Again, the intermediate representation is often ‘cleaner’ to work with, there is a more finite set of instructions to work with.
• So ,while Clang’s or GCC’s IR looks messy, it is actually quite regular!
• Consider an intermediate representation that has a range of 10-100 possible instructions
• Compare this with a programming language which has 100s of keywords and operations can be used in any permutation!

63

Code Optimization

• This stage is where we perform various code optimizations
• Dead code elimination
• code motion
• loop unrolling, etc
• Typically this is done by manipulating the intermediate representation
• Again, the intermediate representation is often ‘cleaner’ to work with, there is a more finite set of instructions to work with.
• So ,while Clang’s or GCC’s IR looks messy, it is actually quite regular!
• Consider an intermediate representation that has a range of 10-100 possible instructions
• Compare this with a programming language which has 100s of keywords and operations can be used in any permutation!

64

We will revisit some topics in code optimization throughout the course

[Back End]

Code Generation

65

GCC and Clang compilers

• GCC’s Front/Backend is shown on the left, and Clang’s on the right
• Clang itself can have several different machine code representations because of how the compiler is setup.
• Notice how the backend has many smaller separate backends for each target (ARM, x86, etc)

66

Looking closer at Clang as a compiler

• The only limitation is how expressive our intermediate representation is
• That is, if it loses data from any of the frontends, then it will be difficult to generate data for the appropriate backend
• e.g. Think about translating English to French to Swahili back to English
• We may lose some information (perhaps type information for subjects?).

67

Telephone game example [showing information loss]

http://cs.lmu.edu/~ray/notes/introcompilers/

​

68

Short 5 minute break

• 1 hour 40 minutes is a long time.
• I will try to never lecture for more than half of that time without some sort of ‘break’ or transition to an in-class activity/lab.
• Use this time to stretch, check your phones, eat/drink something, etc.

​

69

70

Okay, we made it!

​

Now we can generate assembly code for our target architecture

• We have already learned some x86-64 Assembly
• Assembly gets translated from an instruction into machine code.
• 1 to 1 translation
• Instructions have opcodes that correspond to 1’s and 0’s.
• (We have investigated this in a previous lecture--example below)

​

71

Linkers

72

Linking

• Linkers typically do not get the respect they deserve in the programming world.
• There are whole courses dedicated to compilers, but why not the linker?
• If you can understand the linker, then you can become a power user in a sense.
• Many people do not know how to debug linker errors and their messages.
• A common one is “unresolved external symbol”

73

Linking

• Linkers typically do not get the respect they deserve in the programming world.
• There are whole courses dedicated to compilers, but why not the linker?
• If you can understand the linker, then you can become a power user in a sense.
• Many people do not know how to debug linker errors and their messages.
• A common one is “unresolved external symbol”

74

Example with the linker

Here are two different c files (main.c on the left, and sum.c on the right).

75

Example with the linker

In our main.c file, sum is declared but not defined. The body of code for sum is in sum.c.

76

The Linkers job is to combine two (or more) files

Note that main.o and sum.o are generated from our compiler.

77

The Linkers job is to combine two (or more) files

Note that main.o and sum.o are generated from our compiler.

78

Compiler does this part

The Linkers job is to combine two (or more) files

Note that main.o and sum.o are generated from our compiler.

79

Linker combines output

Open Question: Why use a Linker? Your thoughts?

80

Why use a Linker? Modularity

• Programs can be written as a set of smaller source files
• Once you get more than a few hundred lines of code in a file, it becomes difficult to manage.
• We can also organize this code and build ‘libraries’ of code.
• I can have a math library with math functions for example.
• Or an I/O library (like stdio)

81

Why use a Linker? Modularity

• In the example on the right, there are no dependencies so I can generate the object file (.o) files in parallel or only as I make changes to one or the other.
• I can then share these files with my friends.
• (even if they are created in different languages)

82

Why use a Linker? Time Efficiency

• Time: Separate compilation
• Remember the whole first part of this lecture going through the compilation process?
• That takes time!
• If we can separate files, then we only need to recompile files that we modify
• Compilation time can be hours or days for large projects.
• Some projects are compiled constantly overnight as new features are added (nightly builds)
• This is part of “continuous integration”
• Some companies (e.g. fastbuild) work exclusively on compilation systems.

​

83

Why use a Linker? Space Efficiency

• The most common files can be aggregated into a single file
• Option 1: Static Linking
• This is the process of putting only the library code that is used into a file.
• So if we do not use ‘printf’, no need to include printf in our source code.
• (Analogy: Can think of this as putting only the library books in our backpack that we need)
• Option 2: Dynamic Linking
• Executable file contains no library code
• Only when the program is running does library code get executed, and it is shared from a single library source (e.g. .dll file on windows or .so on linux).
• (Analogy: Can think of this as locating and shouting to a librarian and a librarian telling us the answer)

84

The Linker has 2 jobs

85

Reminder: Linker from a 40,000 foot view

• The linkers job at a high level is to carefully glue and bind a bunch of files together

86

What does the linker do? (Job 1) |Symbol Resolution

• Primary task is symbol resolution.
• Symbol definitions are stored in object files symbol table (i.e. what we compiled into)
• Here is an example

• When the linker runs, there is a “symbol resolution” stage, in which only one symbol can be found?
• Question: Why only one?

87

What does the linker do? (Job 1) |Symbol Resolution

• Primary task is symbol resolution.
• Symbol definitions are stored in object files symbol table (i.e. what we compiled into)
• Here is an example

• When the linker runs, there is a “symbol resolution” stage, in which only one symbol can be found?
• Question: Why only one?
• Answer: More than one symbol results in ambiguity!

88

Example (Finding the symbols)

89

Remember objdump? objdump -t sum

This gives us the symbol table of an executable or .o file

90

What does the linker do? (Job 2)| Relocation

​

• The linker is not a compiler
• Its job is to fill in the blanks to make sure code that is linked together can be run.
• This consists of relocating symbols from their relative location in a .o file, to their final location in a single executable.
• Because remember, those symbols could be anywhere in memory, and we want to place them correctly within our executable.

91

Relocation example from: http://www.bravegnu.org/gnu-eprog/linker.html

​

• The takeaway is there is a procedure ‘strcpy’ and ‘strlen’ from two different files.
• The linker merges them in together, and gives new addresses as needed.

92

Linker works with the three kind of object files to perform its job

1. Executable file (a.out)
• This is what we have been using already.
2. Relocatable object file (.o) file
• This contains some code in data file, that needs to be combined to form an executable.
• Note there is still only 1 main function amongst all files.
3. Shared object file (.so file or .dll on windows)
• This is a library that can be called dynamically (example of shouting to a librarian)

​

93

Future Reading

• Linkers & Loaders by Levine
• If you are interested in building your own linker

​

94

In-Class Activity

95

In-Class Activity

1. Complete the in-class activity from the schedule
1. (Do this during class, not before :) )
2. This is the 1% of your grade!
3. We will review answers in the next class.

​

​

96