CS 241

CS 241: Foundations of Sequential Programs

40% assignments
20% midterm
40% final

1 | Data Representation

1.1 | Binary Data Representations

Bit = 0/1 Nibble = 4 bits Byte = 8 bits

1.2 | What’s in a Word?

Word = machine-specific grouping of bytes (8 bytes in a 64-bit architecture) Halfword / doubleword = yk

1.3 | Numbers

The most significant bit (MSB) in a binary sequence is the left-most bit (when written normally). The least significant bit (LSB) in a binary sequence is the right-most bit (when written normally).

1.4 | Binary Representation of Numbers

Sign-Magnitude Representation

• MSB represents the sign

Two’s Complement Representation:

• D to TC: negate a value by flipping the bits and adding 1 (faster: locate the rightmost 1 and flip the bits)
• TC to D: flip the bits and add 1

Arithmetic of signed integers

• Works by ignoring overflow because it’s in $Z_{256}$, so the first carry bit is ignored

1.5 | Hexadecimal as a Binary Shorthand

0x

1.6 | Endianness

Endianness = Where the largest bit is

• Big-endian: largest bits come first (English)
• Little-endian: smallest bits come first (all modern computers)

MSB and LSB change based on endianness

1.7 | ASCII Representation for English Text

ASCII is not decimal 'a' = 97 in ASCII 0xa = 10 in decimal

Uppercase and lowercase differ by 32 for convenience A = 65 = 01000001 a = 97 = 01100001

Bitwise operators (can be combined with the assignment operator, c &= 5;') ~= NOT&= AND|= OR^= XOR>>= right shift<<` = left shift

2 | Machine Language

2.1 | ARM64 Hardware

15 = 00001111
-15 = 11110001 (flip then add 1)

24 = 00011000

-1 = 11111111

What is a computer program

• Programs operate on data
• Programs are data. von Neumann architecture: programs live on the same memory space as the data they operate on

CPU (Central Processing Unit): “Brain” of computer

• Registers x0,...,x30, xzr, sp
  • x30 is the link register or return address
  • x29 is a frame pointer
  • xzr (0), sp (stack pointer) are very specific
• Control Unit: Decodes instructions and dispatches
  • PC (Program Counter)
  • IR (Instruction Register)
• Memory: MDR (Memory Data Register) and MAR (Memory Address Register)
• ALU (Arithmetic Logic Unit): Does arithmetic

CPU with memory

• Bus: Data travels along it
• Memory of many kinds. From fastest to slowest:
  • CPU/registers (fastest, 32 x 64 bits = 256B)
  • L1 cache
  • L2 cache
  • RAM (16,000,000,000B)
  • disk
  • network memory (slowest, outside, your local machine)

ARM64

• Recall: Code is just data.
  • Code is stored in RAM.
  • Code is a sequence of instructions
  • Each instruction is a halfword (32 bits)
• ARM64 takes instructions from RAM and attempts to execute them
  • We need a convention to say “this location definitely has an instruction”
  • We assume location 0 has an instruction
  • Have a special counter called Program Counter (PC) to tell us what instruction to do next

2.2 | How ARM64 Executes Programs

PC = 0x00 // start at address 0
while True do // infinite loop
	IR = MEM[PC] // fetch the 32 bit halfword in PC, put it in IR
	NPC = PC + 4 // compute the next PC (next halfword)
	Decode and execute instruction in IR
	PC = NPC // repeats the loop

Fetch-execute cycle

• NPC = next PC (Program Counter) value
  • Usually PC + 4 (next byte / halfword)
  • We run instructions in order: 0,4,8,12, etc.

2.3 | ARM64 Machine Language

The Simplest Program (Jump Register)

Branch to Register (NPC = xn): 11010110 000 11111 000000 nn nnn 00000
Branch to Register (x30):      11010110 000 11111 000000 11 110 00000
														(30)

Basic Arithmetic (Add and Subtract)

Ex: Addition:

• Add values in x8 and x9, store result in x3
• Shown in big endian, but stored in little endian

01001011001mmmmm011000nnnnnddddd
          (01001)    (01000)(00011)
          (9)        (8)    (3)
01001011001010010110000100000011

n, m = source registers, d = destination
d = n + m

Loading Constants (PC-Relative Load)

Load-and-skip pattern

• Instructions are in memory, and read values from somewhere else in memory
• PC-Relative Load
• xd = MEM[PC + i*4]
• Take a word near the PC, copy it into a register (xd) $i$ halfwords (4i bytes) after the PC
  • If $i=0$, this copies the instruction + next halfword into xd

Load $11(1011_2)$ into x8

01011000iiiiiiiiiiiiiiiiiiiddddd
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

01011000000000000000000000101000
(opcode)				  (01000) = destination x8
00000000000000000000000000001011
						  (01011) = value 11
00000000000000000000000000000000  = all 0s because a word is 64 bits

Does this work?

• Almost: It loads 11 into x8, but remember the fetch-execute cycle
• It tries to run 11 as an instruction, which will crash
• Problem: Our data has to be near the PC to load, but we can’t run it as code
• Solution: We need a second instruction to skip the data

Branching = skipping or jumping code in ARM64

• Branch Instruction: NPC = PC + i*4
• This means “skip i instructions” (including the PC itself)

01011000iiiiiiiiiiiiiiiiiiiddddd
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

01011000000000000000000000000011
						  (00011) = branch 3 halfwords past value
00000000000000000000000000001011
						  (01011) = value 11
00000000000000000000000000000000
(next instruction..............)

We combine PC-relative load and branch to make the load-and-skip pattern

• 1st halfword: PC-relative load from 3rd, 4th halfword
• 2nd halfword: Branch past 3rd, 4th halfword
• 3rd, 4th halfword: the data

Load and skip 11 into x8

(opcode)             (00010) = 2 
01011000000000000000000001001000
						  (01000) = load from PC+2 halfwords into x8
00010100000000000000000000000011
						  (00011) = i = skip 3 halfwords (after data)
00000000000000000000000000001011
						  (01011) = the value 11
00000000000000000000000000000000

Registers are 64 bits

• Split between high bits (32) | low bits (32)
  • High memory (0x0), low memory (0xffff)
• In little endian, it’s stored as low bits | high bits

A complete program

Add the values 11 and 13, and stores the result in x3

• Load-and-skip 11 into x8 (arbitrarily)
• Load-and-skip 13 into x9 (arbitrarily)
• Add x8 and x9 into x3

OLD
01011000000000000000000001001000 
00010100000000000000000000000011 
00000000000000000000000000001011 
00000000000000000000000000000000 

NEW
01011000000000000000000001001001
						  (01001) = change the x8 into x9
00010100000000000000000000000011 
00000000000000000000000000001101 
						  (01101) = change the 11 into 13
00000000000000000000000000000000 

ADD INSTRUCTION
01001011001010010110000100000011 
		  (01001)    (0100000011) = x9 + x8 = x3

How do we end the program?

• x30 is special
• br x30 = branch to x30 to end the problem (equivalent of return 0)

Branch to x30 - how it gets there is not our problem

1101011000011111000000nnnnn00000
11010110000111110000001111000000
					 (11100) = 30

More Math

Multiplication

• Multiplying creates a product that’s twice as much space: $2^{60}\cdot 2^{60}=2^{120}$
• Solution: we split the result into a high and low section

3 types of multiplication

• Multiply: multiplies xn * xm and places the low 64 bits into xd
• Multiply Overflow Signed / Unsigned = places high 64 bits into xd

Division

• Divide Signed / Unsigned
• NOTE THE ORDER: xd = xn/xm (quotient)
• To get remainder: xd = xn - (xn/xm)*xm

Memory

RAM

• Has more memory than CPU but is slower (data travels via bus)
• Every memory block has an address (from 0 to n-1)
• Words are formed by every consecutive 8 bytes
• Cannot directly use data in RAM; must transfer first to registers

Alignment

• Some machines require that all addresses be aligned to (divisible by) some size
• ARM64 has no requirement but our emulator requires halfword alignment

Operations on RAM

11111000010iiiiiiiii00nnnnnddddd

• xd = MEM[xn+i]
• Load a word from location xn+i into xd

11111000000iiiiiiiii00nnnnnddddd

• MEM[xn+i] = xd
• Store a word from xd into location xn+i

i

• is an immediate: not the number of a register, but an actual value
• For storing / loading from RAM, it’s an offset (xn+i)

2.4 | ARM64 Assembly Language

Assembly Language = text language with a roughly 1-1 correspondence with machine code

• Assembler = compiler to assembly

Tutorial 1

br x30 without using br

0: 01011000 00000000 00000000 010 00000 // ldr x0, 8 (8 = 2 x 4)
4: 000101 00 00000000 00000000 00000011 // b 12 (12 = 3 x 4)
8: 11010110 00011111 00000 11110 00000 // br x30 (high)
12: 00000000 00000000 00000000 00000000 // 0xd61f03c0 (low) 00001 
16: 11001011 001 00001 011000 00001 00001 // sub x1, x1, x1
20: 11111000 000 000011000 00 00001 00000 // stur x0, xzr, 24 (x1 = 0)
24: x0 = brx30

stur xd, [xn, i]
MEM [xn+i] = xd
MEM [0+24] = x0

3 | Scanning and Regular Language

3.1 | The scanner

Tokenization

• Maximal Munch Scanning: always choose the longest meaningful token

3.2 | Formal Languages

Formal Languages

• Alphabet ($\Sigma$)
• String / Word ($w$) / all words in ${\Sigma }^w$
• Empty string = $ϵ$
• Language = set of strings
• Length of string = $|w|$

$\Sigma \ast$ = all concatenations of characters in an alphabet

3.3 | Regular Languages

Deterministic Finite Automata (will draw on exams)

• An arrow into the initial start state
• Accepting states are two circles
• Arrows from state to state are labelled
• Error state(s) are implicit (a common “hack”)

Regular Language over alphabet $\Sigma$

1. Empty language and the language consisting of the empty word are regular
2. All languages $\{a\}$ for all $a\in \Sigma$ are regular
3. The union, concatenation, or Kleene star of any two regular languages are regular
4. Nothing else

If $L,L_1,L_2$ are regular languages, then so are the following Union

$$L_1\cup L_2=\{x:x\in L\text{ or }x\in L_2\}$$

Concatenation

$$L_1\cdot L_2=L_1{L}_2=\{xy:x\in L1,y\in L_2\}$$

Kleene star: infinite combination of union and concatenation

$$L\ast =\{ϵ\}\cup \{xy:x\in L\ast ,y\in L\}=U_{n=0}^{\infty }{L}^n$$

Operator Precedence

$$a\ast b>ab>a\cup b$$

Let $\Sigma =\{a,b\}$. Explain why $L=\{a{b}^{n}a:n\in \mathbb{N}\}$ is regular

• Regular languages are closed under Kleene star, so $\{b\}\ast$ is regular
• Concatenation of regular languages are also regular, so $\{a\}\cdot \{b\}\ast \cdot \{a\}$ is regular

Regular Expressions

• Notation
• Union
• Concatenation
• Kleene star
• Order of operations

Deterministic finite automata

• Every state has one transition for each $c\in \Sigma$
• Including the ERROR state if there is one
• NFA (nondeterministic) can have multiple transitions per character
• $ϵ-NFA$ can consume no character

3.4 | DFAs

A DFA is a 5-tuple ($\Sigma ,Q,q_0,A,\delta$)

• $\Sigma$ = finite non-empty set (alphabet)
• Q = finite non-empty set of states
• $q_0\in Q$ = start state
• $A\subseteq Q$ = set of accepting states
• $\delta :(Q\times \Sigma )\to Q$ = total transition function (given a state and symbol, what state should we go to)

Language of a DFA = the set of all strings accepted by w

$$L(M)=\{w:M\text{ accepts }w\}$$

Theorem (Kleene) L is regular if and only if $L=L(M)$ for some DFA M. That is, the regular languages are precisely the languages accepted by DFAs

3.5 | Back to scanning

General idea: Consume the largest possible token that makes sense. Produce the token and then proceed.

• Maximal Munch: Consume characters until you no longer have a valid transition. If you have characters left to consume, backtrack to the last valid accepting state and resume.
• Simplified Maximal Munch: Consume characters until you no longer have a valid transition. If you are currently in an accepting state, produce the token and proceed. Otherwise go to an error state.

Tokens:
a
abbb
bbbb

Input:
abbbb

MM:
abbb - reject

SMM:
abbb - reject

Practical implications

vector<pair<string, int>> v; // used to be confused with '>>'

Tutorial 2

Ex: Regular Language

$$aa\mid ab\mid ba\mid bb$$ $$(a\mid b)(a\mid b)$$

Ex 2:

$$(0\mid 1)0(0\mid 1)(0\mid 1)1(0\mid 1)\ast$$

Ex 3:

$$(a\mid b)[(+\mid -\mid \ast \mid /)(a\mid b)]\ast$$

Ex: 4

$$(0\mid 1)\ast 110101(0\mid 1)\ast$$

Ex: 5 Naive

$$(0\mid 2)\ast 1(0\mid 1\mid 2)\ast$$

Even | 1 | Even

$$2^{\ast }(02^{\ast }02^{\ast }{)}^{\ast }1(1\mid 2{)}^{\ast }(0(1\mid 2{)}^{\ast }0(1\mid 2{)}^{\ast }{)}^{\ast }$$

Odd | 1 | Odd

$$2^{\ast }(02^{\ast }02^{\ast }{)}^{\ast }(1\mid 02^{\ast }1(1\mid 2{)}^{\ast }0)(1\mid 2{)}^{\ast }(0(1\mid 2{)}^{\ast }(1\mid 2{)}^{\ast }{)}^{\ast }$$

4 | Assembly Language

4.1 | Machine Language to Assembly

Bit masking (shifting to be OR’d into position)

(bitwise-ior (arithmetic-shift 2 5) … 
			(bitwise-and offset #x7FFFF))

4.2 | Assembly basics

Suppose that x0 contains the address of an array and x1 has the number of elements (words) in this array (assume small enough that we don’t have to worry about overflow). Place the number 7 in the last possible spot in the array.

 0: ldr x7, 8 ; x7 = 8 (line 0+8=8)
 4: b 12 ; jump to line 4+12=16 
 8: .8byte 7 ; occupies bytes 8 - 15 (8 bytes)
16: ldr x8, 8 ; x8 = 8 (line 16+8=24)  
20: b 12 ; jump to line 20+12=32
24: .8byte 8 ; occupies bytes 24-31
32: mul x3, x1, x8 ; x3 = x1 * x8
36: add x3, x0, x3 ; x3 = x0 + x3 (base address + offset)
40: stur x7 [x3, 8] ; store x7 to memory at [x3+8]

Literals like 8byte 7 take 8 bytes

4.3 | Conditional Branching (IF)

Comparison

cmp xn, xm

• Supports many codes (eq, ne, hs, lo, etc)

Conditional Branch

b.cond i

(IF STATEMENTS) Write an ARM64 assembly program that checks whether x3 is greater than 10. If it is, put 1 in x0, otherwise, put 0 in x0.

ldr x10, 8 // load-and-skip 10 (in 8 bytes) into x10
b 12
.8byte 10
cmp x3, x10 // compare x3 and x10 (10)
b.le 24 // if <=, skip loading 1 (to a)
ldr x0, 8 // load-and-skip 1 into x0 (IF)
b 12
.8byte 1
b 20 // skip loading 0
ldr x0, 8 // a
b 12 // load-and-skip 0 into x0 (ELSE)
.8byte 0
br x30 // return to OS

Write a program to get the negative absolute value of x1. (That is, negate it if it’s positive.)

ldr x3, 8 // load-and-skip 0 into x3
b 12
.8byte 0
cmp x1, x3 // compare x1 to x3 (0)
b.lt 8 // if negative (Less Than 0), skip to the end of the program
sub x1, x3, x1 // if positive, negate it (x1 = 0 - x1)
br x30 // return to OS

Why can’t we use xzr?

• xzr can only be in xm

4.4 | The mystery of x31

The bit pattern 11111 is used to access two special registers:

• sp = stack pointer, occurs when 11111 appears as xd, xn
• xzr = the zero register, always containing 0
• In assembly, x31 isn’t allowed

Why?

• Copy a value by adding it to zero
  • add x0, x1, xzr
• Compare something to zero
  • cmp x0, xzr

4.5 | Looping (WHILE)

Write an ARM64 assembly program that adds the even numbers from 2 to 20 into x0.

ldr x20, 8 // x20 = 20
b 12
.8byte 20
ldr x2, 8 // x2 = 2
b 12
.8byte 2
add x1, x2, xzr // x1 = 2 + 0 = 2
sub x0, x0, x0 // trick to zero a register; x0 = 0
add x0, x0, x1 // -12 // x0 = 2 + 0 = 2
add x1, x1, x2 // -8 // x1 = 2 + 2 = 4
cmp x1, x20 // -4
b.le -12 // 0 // 4 < 20
br x30

Insight: branching upwards does the same thing as WHILE

Labelling: not machine code, doesn’t take space

label: instruction

Ex:

sub x3, x0, x0
sample: // has address 0x4 (same location of add x1, x0, x0)
add x1, x0, x0

4.6 | Procedures

Only xd, xn can be sp

add sp, sp, x10 // allowed
add sp, x10, sp // not allowed

It’s common but not necessary for both xd and xn to be sp

sub sp, sp, x10 // normal stack-y behavior
sub sp, x4, x10 // weird but allowed

4.7 | Call and return

Warm up: Does a+++++b compile?

(a++)++ // invalid lvalue
a++ + ++b // fix by adding whitespace

What about a+++--b?

a++ + --b // fine

Recall: save a restore register

• main (caller) calls f (callee)

Who should be responsible?

• Either is ok - just a convention
• General registers, “callee” will save

Returning

ldr x8, 8
b 12
.8byte f // Label in .8byte is an
 // address
br x8 // Branch to f
// (NEXT LINE) More code here

Once $f$ completes, we want to jump back to (NEXT LINE). How?

Branch and link:blr xn

• NPC = xn, x30 = PC + 4
• Sets the next PC to the procedure; leaves the next line (where to return) in x30
• At the end, the function just needs to br x30

Boilerplate for procedures

f: // label for the procedure
	stur x1, [sp, -8] // save registers we
	stur x2, [sp, -16] // change
	ldr x1, 8 // load value to subtract from sp
	b 12
	.8byte 8
	sub sp, sp, x1 // decrement stack pointer (i.e., complete the push)
	// insert actual procedure here
	add sp, sp, x1 // IF x1 is still 8. Otherwise, reload it.
	ldr x2, [sp, -16] // restore changed
	ldr x1, [sp, -8] // registers
	br x30 // return to caller

Boilerplate for main code

stur x30, [sp, -8] // save OS return address
ldr x30, 8 // weird, but we CAN use x30 as a normal register if we want to
b 12
.8byte 8
sub sp, sp, x30
ldr x30, 8 // load address of f
b 12
.8byte f
blr x30 // branch to f
// f returns here
ldr x30, 8
b 12
.8byte 8
add sp, sp, x30 // restore sp address
ldur x30, [sp, -8] // restore x30
br x30 // return to OS

4.8 | Procedure arguments

// sum even numbers from 1 to n
// Arguments:
// x0 = n
// Returns in x0
// Other registers:
// x1: n
// x2: 2
// x3: step

sumEvens1toN:
	// prologue
	stur x1, [sp, -8]
	stur x2, [sp, -16]
	stur x3, [sp, -24]
	ldr x1, 8
	b 12
	.8byte 24
	sub sp, sp, x1
 
	 // setup
	 add x1, x0, xzr // move n to x1
	 ldr x2, 8
	 b 12
	 .8byte 2
	 sub x0, x0, x0
	 add x3, x2, xzr
 
 loop:
	 add x0, x0, x3
	 add x3, x3, x2
	 cmp x3, x1
	 b.le loop
	 
 // epilogue
 ldr x1, 8
 b 12
 .8byte 24
 add sp, sp, x1
 ldur x1, [sp, -8]
 ldur x2, [sp, -16]
 ldur x3, [sp, -24]
 br x30
 
// example main code for calling sumEvens1toN
stur x30, [sp, -8] // save x30
ldr x30, 8
b 12
.8byte 8
sub sp, sp, x30

// put a value into x0 (the argument)

ldr x30, 8 // get address to sumEvens1toN
b 12
.8byte sumEvens1toN
blr x30 // call it

// do something with x0 (the result)

ldr x30, 8 // restore x30
b 12
.8byte 8
add sp, sp, x30
ldur x30, [sp, -8]
br x30

4.9 | Input and Output

Memory-mapped I/O addresses:

• stdin: 0xc000000000010000
• stdout: 0xc000000000010008
• (You are not expected to memorize these)
• Just stur to stdout to write, and ldur from stdin to read

4.10 | The assembler

b.le myLabel
myLabel:
add x1, x1, x1

Problem: myLabel is used before it’s defined

Solution: perform 2 passes

• Pass 1: Group tokens into instructions and record addresses of labels (dictionary / label table)
  • Note: Multiple labels are possible for the same line!
  • For example, f: g: add x1, x1, x1
  • Note: Be careful while counting! Every instruction is a halfword, but .8byte is a full word.
• Pass 2: translate each instructions into machine code. If it refers to a label, look up the associated address compute the value.

Tutorial 3

Write an ARM64 assembly program which takes a nonnegative integer n in x0 and stores n! in x1

Input: non-neg int n in x0
Output: n1 in x1

IDEA:
x1 = solution
x11 = 1
x0 = counter

CODE:
ldr x1, 8 ; x1 = 1
b 12
.8byte 1 
add x11, x1, xzr ; x11 = 1

loop:
	cmp x0, x11 ; break when x0 = 1
	b.eq end
	mult x1, x1, x0 ; x1 = x1 * x0 
	sub x0, x0 x11 ; x0 = x0 - 1
	b loop

end: br x30

Fibonacci

Input; non-neg int in x0
Output: f_n n x3

IDEA:
x1 = f_{n-1}
x2 = f_{n-2}
x3 = x1 + x2
x4 = counter
x4 = 1

CODE
ldr x11, 8
b 12
.8byte 1 ; x11 = 1
add x1, xzr, x11 ; f1 = f_{n-1} = 1
add x2, xzr, xzr ; f2 = f_{n-2} = 0
add x3, xzr, xzr ; x3 = 0
add x4, xzr, xzr ; x4 = 0

loop:
	cmp x4, 0
	b.eq end
	add x3, x2, x1 ; f_n = f_{n-1} + f_{n-2}
	add x2, x1, xzr ; f_{n-2} = f_{n-1}
	add x1, x3, xzr ; f_{n-1} = f_n
	add x4. x4, x11 ; x4++
	b loop

end: br x30

Length of arry

x0 = addr of array
x1 = len(array)

IDEA
x8 = 8
x2 = retval
x2 = value of current element
x1 = coutner

CODE
ldr x8, x
b 12
.8byte 8 ; x8 = 8
mul x1, x1, x8 ; x1 = x1 * 8 ; x1 = 1
sub x2, x2, x2 ; x2 = 0 ; x1 = 8
loop:
	cmp x1, xzr;
	b.eq end
	sub x1, x1, x8
	add x3, x0, x1 ; x3 = addr of the current element
	ldur x3, [x3, 0] ; x3 = val of the current element
	add x2, x2, x3
	b loop

end: br x30

5 | Regular Languages Continued (NFAs)

5.1 | NFAs

Extending $\delta$ (transition function)

• $\delta :(Q\times \Sigma )\to Q$ to a function defined over $(Q\times \Sigma \ast )$ via:

$$\begin{array}{rl}\delta \ast & :(Q\times \Sigma \ast )\to Q\\ & :(q,ϵ)\to q\\ & :(q,aw)\to \delta \ast (\delta (q,a),w)\end{array}$$

• where $a\in \Sigma$ and $w\in \Sigma \ast$ ($aw$) is concatenation
• Basically, process a letter first then process the rest of the string

Definition A DFA given by $M=(\Sigma ,Q,q_0,A,\delta )$ accepts a string $w$ if and only if

$$\delta \ast (q_0,w)\in A$$

Warm-up: Write a regex for words that start and end with the same pair

$$aa(a\mid b)\ast aa\mid bb(a\mid b)\ast bb\mid ab(a\mid b)\ast ab\mid aa\mid bb\mid aaa\mid bbb$$

NFA: Suppose we allowed more than one transition from a state with the same symbol

• $\delta (Q\times \Sigma )\to 2^Q$ is our (total) transition function
• Note that $2^Q$ denotes the power set of q, that is, the set of all subsets of $Q$
• This allows us to go to multiple states at once

Extend the definition of $\delta :Q\times \Sigma \to 2^Q$ to a function $\delta \ast :(2^Q\times \Sigma \ast \to 2^Q)$

$$\begin{array}{rl}\delta \ast (2^Q\times \Sigma \ast )& \mapsto 2^Q\\ (S,ϵ)& \mapsto S\\ (S,aw)& \mapsto \delta \ast (\bigcup _{q\in S}\delta (q,a),w)\end{array}$$

Decision Problems / P = NP

• Polynomial vs Nondeterministic Polynomial
• Currently, we only know how to track nondeterminism in exponential $(2^n)$, not polynomial runtimes

NFA: Track every path in a set $S\in 2^Q$

• If your set of final states after processing $ϵ$ contains an accepting state, accept

NFAs are not more powerful than DFAs

• One could write down all of the $2^Q$ possible states and connect each one
• More simply, go through the NFA and determine what happens for each character on each state
• Each subset $S$ is its own state
• NFA has $n$ states, DFA has $2^n$ (time vs space tradeoff)

5.2 | $ϵ$-NFAs

$ϵ$-transitions make it easy to join multiple NFAs

The $ϵ$-NFA recognition algorithm can follow any number of $ϵ$ transitions in between consuming each symbol of the input

• Compute the $ϵ$ closure of the current state between each transition
• This is the set of all states we can reach from the current state set by following $ϵ$ transitions

$abca$ $\{q_0\}\to \{q_1\},E(\{q_1\})=\{q_1,q_2\}$ $\{q_1,q_2\}\to \{q_1\},E(\{q_1\})=\{q_1,q_2\}$

5.3 | Regular to $ϵ$-NFA (to DFA)

Summary

• All regular languages have an $ϵ$-NFA
• ALL $ϵ$-NFAs can be DFAs
• Both processes can be automated
• All DFAs can be regular languages (we won’t discuss)

Where are we now?

1. Identify tokens (Scanning) (Complete!)
2. Check order of tokens (Syntactic Analysis) (Now)
3. Type Checking (Semantic Analysis) (Later)
4. Code Generation (Also later)

Syntax = order of tokens, parentheses balance Semantics = does what’s written make sense (right variables in functions, etc.)

Tutorial 4

Read characters from stdin, print out uppercase to stdout and leave unchanged if not lowercase

ldr x27, 24 ; stdin
ldr x28, 28 ; stdout
ldr x20, 32 ; 'a'
ldr x21, 36 ; 'z'
ldr x22, 40 ; 'a' - 'A"'
b 44
.8byte 0xc 0000 0000 0000 1000
.8byte 0xc 0000 0000 0000 1008
.8byte 97
.8bbyte 122
.8byte 32
loop:
	ldur x1 [x27, 0]  ; load into stdin
	cmp x1, xzr       ; if eof, end
	b.lt end
	cmp x1, x20       ; if < 'a', print
	b.lt print
	cmp x1. x21       ; if > 'z', print
	b.gt print   
	sub x1, x1, x22   ; make it uppercase
print:
	stur x1, [x28, 0] ; store in stdout
	b loop
end:
	br x30

Factorial

IDEA:
x1 = solution
x11 = 1
x0 = counter (decreasing)

fact(x0):
	if x0 == 0
		return 1
	x0 -= 1
	x1 = fact (x0)
	x0 += 1
	x1 = x0 * x1

fact:
	// prologue
	stur x30 [sp, -8] ; go here after done
	stur x0 [sp, -16] ; n
	stur x11 [sp -24] ; x11
	ldr x30, 8
	b 12
	.8byte 24
	sub sp, sp x30 ; sp = sp - 24
	ldr x11, 8
	b 12
	.8byte 1 // x11 = 1
	// function
	cmp x0, xzr ; x0 != 0, recurse
	b.ne recur
	add x1, x11, xzr
	b clean
recur:
	sub x0, x0, x11
	ldr x30, 8
	b 12
	.8byte fact
	blr x30 ; branch and link, x1 <- (x0-1)!
	add x0, x0, x11
	mul x1, x0, x1 ; x1 <- x0(x0-1)!
clean:
	ldr x30, 8
	b 12
	.8byte 24
	add sp, sp, x30
	ldur x30, [sp, -8] ; from prologue
	ldur x0, [sp, -16]
	ldur x11, [sp, -24]
	br x30

Label Tables

   begin:
0  label: b.eq after
4  br x4

   after:
8  stur x30, [x0, 16]
12 br x5
16 abc0: abc1: .8byte after

   loadStore:
24 ldur x20, [x0, 8]
28 b.ne abc0

32 end:

NOTES ON IMPLEMENTATION

1. Use unordered_map in C++ to store symbol table — fast lookups
2. Use signed integers to store memory addresses in C++ — subtraction of 2 unsigned integers could cause underflow
3. Keep track of both number of lines read & current location — the former for outputting error messages
4. Create an Instruction class possibly during the Analysis phase (before complete symbol table)

class Instruction {
    location (mem addr)
    line #
    opcode
    operands
    int assemble() {...}
}

• operands should not be integers (label might not exist yet)
• maybe a Token type
• Opcode can be an Enum type (good for switch statements)

5 | Regular Languages Continued (CFGs)

5.1 | We need more power!

Context-free languages = regular languages + recursion

5.2 | Context-free grammars

Context Free Grammar (CFG) is a 4-tuple $(N,\Sigma ,P,S)$

• $N$ = finite non-empty set of non-terminal symbols
• $\Sigma$ = alphabet, set of non-empty terminal symbols
• $P$ = finite set of productions, each of the form $A\to \beta$ where $A\in N,\beta \in (N\cup \Sigma {)}^{\ast }$
• $S\in N$ is a starting symbol

Conventions

• $a,b,c\dots$ = terminals (symbols or characters) from $\Sigma$
• $w,x,y,\dots$ = words (strings) from $\Sigma \ast$
• $A,B,\dots ,S,\dots$ = non-terminals (variables) from $N$
• $S$ = start symbol, a non-terminal from $N$
• $\alpha ,\beta ,\gamma$ = words from $V\ast =\{N\cup \Sigma \}\ast$

Notations and terminology

• $\alpha ⟹\beta$ = $\alpha$ derives $\beta$ in one step
• $\alpha ⟹\ast \beta$ = $\alpha$ derives $\beta$ eventually
• $\alpha A\beta =⟹\alpha \gamma \beta$ = if there exists $A\to \gamma$ in $P$

Example $\Sigma =\{(,)\},L=\{w:w\text{ is a balanced string of parentheses}\}$

• $S\to ϵ$
• $S\to (S)$
• $S\to SS$

$$S\to ϵ\mid (S)\mid SS$$

Context-free languages can’t understand this:

long a;
(*a) + 12; // need context to know a is an int, so this isn't allowed

Definition Language of a CFG

$$L(G)=\{w\in \Sigma \ast :S\to \ast w\}$$

Definition A language is context-free if and only if there exists a CFG $G$ such that

$$L=L(G)$$

All regular languages are context free!

5.3 | Arithmetic

Leftmost (rightmost) derivation = always substitute leftmost (rightmost) non-terminal

ex. arithmetic ops over $\Sigma =\{a,b,c,+,\ast ,/,(,)\}$ CFG for $L_1$: arithmetic expressions from $\Sigma$ without parentheses, and derivation for $a-b$

• S -> a|b|c|SRS
• R -> +|-|\*|/ CFG for $L_2$: w balanced parentheses, and a derivation for $((a)-b)$
• S -> a|b|c|SRS|(S) Derivation for $a-b\ast c$:
• Leftmost derivation (always substitute leftmost non-terminal): S => SRS => SRSRS => aRSRS => a-SRS => a-bRS => a-b\*S => a-b\*c

        S
      / | \
     S  R  S
     |  |  |\ \
     a  -  S  R  S
           |  |  |
           b  *  c

• S => SRS => S\*S => S\*c => SRS\*c => S-S\*c => a-S\*c => a-b\*c
• Rightmost derivation: S => SRS => SRSRS => SRSRc => SRS\*c => SRb\*c => S-b\*c => a-b\*c

        S
      / | \
     S  R  S
     |  |  |\ \
     a  -  S  R  S
           |  |  |
           b  *  c

^ BUT could also be a leftmost derivation: S => SRS => aRS => a-S => a-SRS =>* a-b\*c

5.4 | Ambiguity

Definition A grammar for which some word has more than one distinct leftmost derivation/rightmost derivation/parse tree is called ambiguous

Leftmost != rightmost derivation - the whole reason we have PEMDAS

S → a | b | c | SRS 
R → + | − | ∗ | /

$$(a-b)\times c\ne a-(b\times c)$$

For our compiler

• structure/shape of parse tree gives meaning to the string
• two diff parse trees ⇒ 2 diff meanings ⇒ CFG is ambiguous
  • 2 diff parse trees
  • 2 diff leftmost derivations We want
• remove ambiguity
• use parse tree to evaluate expression
  • post-order traversal (left → right → root)
  • evaluate depth first so for above, want second tree bc want to evaluate b*c first (BEDMAS). but if a-b-c, want left first bc left-to-right (left-associativity)
  • S ⇒ SRS: problem - can extend expression by substituting either first or last S
    • fix: force expansion on only 1 side, not both. S ⇒ SRL OR S ⇒ LRS

5.5 | Fixing Ambiguity

Forcing left/right associativity

6 | Top-Down Parsing and LL (1)

6.1 | Top-down parsing

Two broad ideas

1. Start with $S$ and try to get to $w$ (top-down)
2. Start with $w$ and work backwards to $S$ (bottom-up)

6.2 | Top-down algorithm

Method for CFLs

• DFA of a stack uses stack for arbitrary counting, eg. $\{a^n{b}^n:n\ge 0\}$

Using this grammar:

• S → LRS | L
• L → a | b | c
• R → + | − | ∗ | /

Let’s check these strings: • a+b*c • c-c/c • b/c+ • lolwut

Stack

• Push symbol (LRS / L)
• Match symbol with terminals (a / b / c)

Faeries aren’t real

6.3 | The oracle

Use a single lookahead to determine where to go

• Given a non-terminal on the stack and a next input symbol, what rule should we use

Top-down parsing sucks

• But it’s easier to implement

Predictor tables: trace in reverse to get to each terminal symbol

• $A\to \gamma \in Predict(A,a)$ if
• $\gamma$ can derive a string whose first symbol is $a$
• $\gamma$ can derive $ϵ$, and it’s possible for the terminal $a$ to immediately follow $A$

6.4 | LL(1), formally

LL(1) A grammar is called LL(1) if and only if each cell of the predictor table contains at most one entry.

$First(\beta )$: set of characters that can start a derived string starting from $\beta \in V\ast$

• $First(LM)=First(L)$ (first terminal)

$Predict(A,a)$: production rule(s) that apply when $A\in N$ is on the stack and $a\in \Sigma$ is the next input character

• Problem: $A⟹\ast ϵ$

$Nullable(\beta )$: true iff $\beta ⟹\ast ϵ$

• $\beta \in V\ast$ is nullable if and only if $Nullable(\beta )=true$

$Follow(A)$: A character $c$ follows $A$ if it’s possible to derive a string that has $Ac$

• Whatever follows the thing

Predict

$$\begin{array}{rl}Predict(A,a)& =\{A\to \beta :A\in First(\beta )\}\\ & \cup \{A\to \beta :Nullable(\beta )+a\in Follow(A)\}\end{array}$$

6.5 | Nullable, First, and Follow

Nullable

• $Nullable(\beta )$ is false whenever $\beta$ contains a terminal symbol
• $Nullable(AB)=Nullable(A)\wedge Nullable(B)$

First

• Ignore trivial productions of the form $A\to ϵ$
• $First(S^{\prime })=\{⊢\}$ always

Predict table = any number of iterations

Cheat sheet and examples Nullable

• $A\in ϵ$ implies $Nullable(A)$ and $Nullable(ϵ)$
• If $A\to B_1\dots B_n$ and each of $Nullable(B_i)$, then $Nullable(A)$

First

• $A\to aa$ then $a\in First(A)$
• $A\to B_1\dots B_n$ then $First(A)=First(A)\cup First(B_i)$ until $Nullable(B_i)$ is false

Follow

• $A\to aB\beta$ then $Follow(B)=First(\beta )$
• $A\to ab\beta$ and $Nullable(\beta )$, then $Follow(B)=Follow(B)\cup Follow(A)$

$$\begin{array}{rl}Predict(A,a)& =\{A\to \beta :A\in First(\beta )\}\\ & \cup \{A\to \beta :Nullable(\beta )+a\in Follow(A)\}\end{array}$$

6.6 | LL(1) practice

LL(1) can’t handle

• Left recursion (when a grammar can derive a string starting with itself)

$$S\to S+S\mid S-S\mid S\times S\mid S/S$$

• PREDICT conflicts

6.7 | Fixing grammars for LL(1)

A grammar is not LL(1) if you can get to a different state from the same start character

Making a left recursive grammar right recursive

$$A\to Aa\mid \beta$$

Becomes

$$A\to \beta A^{\prime }$$ $$A^{\prime }\to a{A}^{\prime }\mid ϵ$$

Left factoring

$$A\to a{\beta }_1\mid \dots \mid a{\beta }_n\mid y$$

Becomes

$$A\to aB\mid y$$ $$B\to {\beta }_{!}\mid \dots \mid {\beta }_n$$

Right-recursive + right-factored = LL(1)

Tutorial 6

Example: Predict Table

Step 1: Compute $Nullable(A)$ for each non-terminal

Non-terminal	Nullable	Rule #
$S^{\prime }$	F
$S$	T	3
$X$	T	5
$Y$	T	7

Step 2: Compute $First(A)$ for each non-terminal $A$ and fill out predict table

Non-terminal	First
$S^{\prime }$	$⊢$
$S$	a, p, q
$X$	p
$Y$	q

Step 3: Follow Table and fill out predict table

Non-terminal	Folllow
$S^{\prime }$	$\varnothing$
$S$	$⊣$
$X$	$first(Y)\cup b\cup follow(S)=\{b,q,⊣\}$
$Y$	$b\cup follow(S)=\{b,⊣\}$

Predict	$⊢$	$⊣$	$a$	$b$	$p$	$q$
$S^{\prime }$	1
$S$		3	2		3	3
$X$		5		5	4	5
$Y$		7		7		6

Example: Parse

Stack	Consumed	Remaining	Action
$S^{\prime }$	$ϵ$	$⊢appqb⊣$	apply 1
$⊣S⊢$	$ϵ$	$⊢appqb⊣$	pop
$⊣S$	$⊢$	$appqb⊣$	apply 2
$⊣bYXa$	$⊢$	$appqb⊣$	pop
$⊣bYX$	$⊢a$	$ppqb⊣$	apply 4
$⊣bYXp$	$⊢a$	$ppqb⊣$	pop
$⊣YX$	$⊢ap$	$pqb⊣$	apply 4
$⊣bYXp$	$⊢ap$	$pqb⊣$	pop
$⊣bYX$	$⊢app$	$qb⊣$	apply 5
$⊣bY$	$⊢app$	$qb⊣$	apply 6
$⊣bq$	$⊢app$	$qb⊣$	pop
$⊣b$	$⊢appq$	$b⊣$	pop
$⊣$	$⊢appqb$	$⊣$	pop
$ϵ$	$⊢appqb⊣$	$ϵ$	accept

Example: Predict Table, nothing nullable

Compute $First(A)$ for each non-terminal $A$ and fill out predict table

Non-terminal	First
$S^{\prime }$	$⊢$
$S$	a, b
$A$	a, b
$B$	b

Follow Table and fill out predict table

Predict	$⊢$	$⊣$	$a$	$b$
$S^{\prime }$	1
$S$			2	2
$A$			3	4
$B$				5, 6

This is not LL(1)!

7 | Bottom-Up Parsing, LR(0), SLR(1)

7.1 | Bottom-up parsing

Bottom-up parsing

• Move through the word left to right
• If the string in “Read” matches a transition, reduce it with one of the rules
• Pop the string, push result onto stack

7.2 | The LR(0) oracle

Knuth’s Theorem

$$\begin{array}{rl}\{aa:a& \in V\ast \text{is a stack}\\ a& \in \Sigma \text{ is the next character}\\ \exists x& \in \Sigma \ast \text{ such that }S⟹\ast aax\}\end{array}$$

Is a regular language

Item A production with a dot / bookmark $(\bullet )$ on the RHS of a rule, indicating a partially completed rule

Automaton

• One transition per box like a DFA/NFA
• Move the dot to the right
• Benefit: no ambiguity like bottom-up parsing (eg. with $⊢Acdef$, do you pop $def$ or $ef$?)

7.3 | Efficient LR(0)

Time complexity

• Naive DFA approach that re-runs itself is $O(n^2)$
  • Changes are occurring at the top of stack, bottom remains unchanged
• Solution is to move through the DFA in a state stack, and push/pop to it the same time as the symbol stack, making the time $O(n)$

LR(0)

• Left-to-right
• Rightmost derivation
• 0 lookahead

7.4 | Bottom-up parsing conflicts

Issue one (shift-reduce)

• $A\to a\bullet a\beta$ (shift)
• $B\to y\bullet$ (reduce)

$B\to ab\bullet$ $A\to b\bullet c$ Stack: $ab$

Issue two (reduce-reduce)

• $A\to A\bullet$
• $B\to y\bullet$

$A\to c\bullet$ $B\to bc\bullet$ Stack: $abc$

A grammar is LR(0) if and only if after creating the automaton, no state has a shift-reduce or reduce-reduce conflict

7.5 | SLR(1)

SLR = Simplified LR with 1 character lookahead

Follow sets (if statements): $Follow(S)=\{⊣\},Follow(T)=\{+,⊣\}$

$$S\to T\bullet +sS\to T\bullet :\{⊣\}$$

• If the next token is $+$, apply the first
• If the next token is $⊣$, apply the second
• Else, ERROR

If $Follow(E)=\{+,⊣\}$, then it’s not SLR(1)

• $E\to T\bullet +E$
• $E\to T\bullet +\{+,⊣\}$

7.6 | Bottom-up parse trees

Same as top-down string parsing with predict table

Tutorial 6.5

8 | Context-Sensitive Analysis

8.1 | Context-sensitive languages

Traverse parse tree

• Visit all children, then figure out what to do with root node

8.2 | Semantic and type checking

Errors we still need to check for

• Variable declared more than once
• Variable used but not declared
• Type errors
• Scoping error

Thought experiment: With labels in ARM64 in the assembler, we needed two passes. Why do we only need one in the compiler?

• We can use labels before declaration, unlike variables
• Symbol table should contain the types of the variables - in WLP4, just long or long*

8.3 | Symbol Table

map<string, string> symbolTable; // name -> type

Scoping rules

• Duplicated variables in different procedures - OK
• Variable out of scope - NOT OK
• Function signature overloading - NOT OK

Global symbol table

• foo: [long], wain:[long*, long]

Local symbol tables:

• foo: a:long, x:long
• wain: a:long*, b:long

8.4 | Type rules

Name Errors: need context to determine if variables / functions are valid

1. Create a symbol table for each function
   1. If there’s a duplicate, there’s a duplicate declaration error
2. Recursively inspect all of the identifiers in each function
   1. If you find a variable here that is not in your symbol table, then this is a use without declaration error

Type Errors: Contradiction between combinations of different identifiers

• Recursively traverse the tree. Each node should have a field to store its type.
  • If it’s an ID, look it up in the symbol table, cache the type
  • Otherwise, recursively type the children, use their types to see if the current node is well-typed

Tutorial 7

Procedure	Signature	Variable	Type
f	[] -> long	x	long
wain	[long, long] -> long	a b x	long long long
No duplicates + everything was used after declaration - good!

Procedure	Signature	Variable	Type
f	[] -> long	x	long
wain	[long, long] -> long	a b	long long
x is not part of the symbol table under wain - use without declaration error

Procedure	Signature	Variable	Type
f	[] -> long	x	long
g	[long] -> long	g	long
wain	[long, long] -> long	a b	long long
No duplicates + everything was used after declaration - good!

Procedure	Signature	Variable	Type
f	[] -> long	x	long
f	[] -> long	x	long
wain	[long, long] -> long	x y	long long
no signature overloading in WLP4 - semantic error

Which type of error? Tokenization error:

• (1) using unknown symbol like ^
• (5) using long a = 'a'

Semantic error:

• (2) declaring long y = 0 twice
• (3, 7) using variable / function without declaration

Parsing error:

• (4) declaration after statement

Runtime error:

• (6) infinite loop

9 | Code Generation (1)

9.1 | Translation Basics

There are infinitely many equivalent ARM64 programs for a single WLP4 program. Which should we output?

• Correctness
• Simplicity
• Efficiency (LOC)
• Efficiency (speed)

The parse tree can be the same for different programs (`return a vs return b)

9.2 | Symbol Table

Storing variables and params in registers will force us to run out of registers quickly

• Store them on the stack
• Symbol table stores offsets of the stack pointer

How do we arrange it so when we see the variable, we know what the offset is?

• Keep a fixed point in the stack in x29 (frame pointer)
• In the example, x29 always contains the address of b so we can return b

9.3 | Template compilation

Conventions

• x0 = retval
• x1 = intermediate scratch values
• x8 = 8
• x20 = 0
• x29 = fixed point in stack (sp)
• x30 = return address

Template-based code gen = always use the same code for a step

Abstraction

# code(expr1 – expr2) =
code(expr1)        // x0 = expr1
stur x0, [sp, -8]  // store expr1
sub sp, sp, x8     // sp -= 8
code(expr2)        // x0 = expr2
add sp, sp, x8     // sp += 8
ldur x1, [sp, -8]  // x1 = expr1
sub x0, x1, x0     // x0 = expr1 - expr2

# push(x) =
stur x, [sp, -8]
sub sp, sp, x8

# pop(x) =
add sp, sp, x8
ldur x, [sp, -8]

# code(expr → expr1 – expr2) =
code(expr1) // result in x0
push(x0)
code(expr2) // result in x0
pop(x1)
sub x0, x1, x0

Example:

long wain(long a, long b) {
	long c = 3;
	return a + (b - c);
}

code(a + (b - c))
	code(a)
	push(x0)
	code(b - c)
		code(b)
		push(x0)
		code(c)
		pop(x1)
	pop(x1)

9.4 | I/O and linking

Output: putchar, println Input: getchar

Runtime Environment Execution environment provided to an application or software by the OS to assist programs in executions Examples: procedures, libraries, env variables, etc.

Tutorial 8

code (Node node){
	...
	if (node.rule is factor -> PLUS PLUS lvalue){
		code(node.children[2]) // x0 = &lvalue
		ldur x1, [x0, 0]       // x1 = value
		add x1, x1, x11        // x1 = x1 + 1
		stur x1, [x0, 0]       // store x0
		add x0, x1, xzr        // x0 = x1 + 1
	}
	if (node.rule is factor -> lvalue PLUS PLUS){
		code(node.children[0]) // x0 = &lvalue
		ldur x1, [x0, 0]       // x1 = value
		add x2 x1, xzr         // x2 = x1
		add x1, x1, x11        // x1 = x1 + 1
		stur x1, [x0, 0]       // store x0
		add x0, x2, xzr        // x0 = x2
	}
	ir (node.rule is statement -> lvalue PLUSBECOMES expr SEMI){
		code(node.children[0]) // x0 = &lvalue
		push(x0)               // store x0 on stack
		code(node.children[2]) // x0 = &expr
		add x1, x0, xzr        // x1 = x0 (expr)
		pop(x2)                // x2 = &lvalue
		ldur x0 [x2, 0]        // x0 = lvalue
		add x0, x0, x1         // x0 = x1 (expr) + x0 (lvalue)
		stur x0, [x2, 0]       // store x0
	}
}

ARMCOM Files

• Begins with 5 halfword header
  • 1: b20 (unconditional jump)
  • 2-3: file length (in bytes)
  • 4-5: code length (byte offset of word)
• Relocation entries tell us which spots need relocation
  • 0x01
  • loc = byte offset

f: .8byte g     0
   .8byte f     8
g: .br x30      16

0  b 20
4  .8byte endModule
12 .8byte endCode
20 .8byte 36             // label g starts at 36
28 .8byte 20             // label f starts at 20
36 br x30
40 .8byte 1 (endCode)    // REL entry
48 .8byte 20
56 .8byte 1              // REL entry
64 .8byte 28
72          (endmodule)

Load ARMCOM file into 0x300

alpha = 0x300
header size = 20

endModule = 56
endCode = 40

0  0x14000005 // b 20
4  0x00000038 // .8byte endModule
8  0x00000000
12 0x00000028 // .8byte endCode
16 0x00000000
20 0x00000034 // to relocate
24 0x0000010c
28 0x00000001
32 0x00000018
36 0x00000000
40 0x00000001 // 0x1 = start of relocation entry
44 0x00000000
48 0x00000014 // 0x14 = 20 = relocate what's at line 20
52 0x00000000
56

   (read word) - (header size)
MEM[0x300 + 20 - 20] += 0x300 - 20
0x34 + 0x300 - 0x14 = 0x320

ANSWER       (320) 
0x300  0x00000320
0x304  0x0000010c
0x308  0x00000001
0x30x  0x00000018
0x310  0x00000000

9 | Code Generation (2)

9.1 | Conditionals

start -> IF ( tests ) { stats }
test -> expr EQ expr 
stats -> ...

code (nodefromparsetree)
	if node is IF ...
	cmp
	b.cond else // problem
else:
	// generated recursively
endif:
	// generated recursively

What about nesting?

if () {
	if () {
	}
	else if () {
	}
}

	cmp
	b.cond else
	b endif
// use current counter
else:
	cmp 
	b.cond else
	b endif
	else:
		...
	endif:
		...
// use current counter, then increment
endif:
	...

If counter:

• Keep a counter of how many if statements you have
• Use label names like else#, endif#, where # corresponds to the if counter
• Be careful with recursion - code(then branch) can generate its own ifs and change the if counter
• Need to remember the local level of nesting on top of the global counter!

9.2 | Loops

While = if with unconditional branch back at the end

Add comments and blank lines!

9.3 | Pointers (NULL)

Prologue

• Load 8 into x8
• Import print into x10
• Store return address on stack
• Initialize frame pointer (x29)
• Store registers 0 and 1 (args)

Body

• Store local variables in stack frame

Epilogue

• Pop stack frame
• Restore previous variables

NULL

• We want NULL to crash if we try to dereference it
• Can’t be 0x0 because that’s a valid memory address (C was designed to protect 0)
• We should pick a negative number so it won’t be a valid memory address - start using signed ints
• If you pick -1, there might be problems if you try to *(p+1) = *(0)
• Pick a very high number like 0xFFFFFFFFFFFF0000 == -65536
• New convention: x6 = -65536
• Attempting to dereference NULL gives ldur x0 [x6, 0] - hardware crash
  • Either because the positive num is too big or negative number is disallowed

code (factor -> NULL)
add x0, x6, xzr

9.4 | Pointers (* and &)

factor1 -> STAR factor2 // factor2 must be a pointer otherwise type error

code (factor1 -> STAR factor2) = code (factor2)
								 ldur x0, [x0, 0] // dereference

ALLOWED:

• * long*
• *NULL - valid code, but crashes from hardware
• *5 - valid code, but crashes from semantic rules in A6

BANNED:

• & long*
• &5

lvalues vs pointers

• Pointers can be null, lvalues must have an address

Address-of

• An lvalue is something that can appear as the LHF of an assignment rule
• factor -> AMP lvlaue
• If we get ID = 'a', use the symbol table to find the offset and location (frame pointer, x29)

9.5 | Pointers (arithmetic)

*(p+i) = p[i]

Pointers cannot be negative because they represent memory addresses

• we should use b.hi instead of b.gt

int *p, q;
test -> expr COND expr
- if expr = long, treat as signed
- if expr = long*, treat as unsigned

code(expr -> expr + term)
	if (expr is long*, term must be long) // array adderss
		code (expr)      // result in x0
		push (x0)
		code (term)      // result in x0
		mul x0, x0, x8   // multiply by 8 bc array
		pop (x1)         // pop first of expr into scratch register
		add x0, x1, x0

Add / subtract

long + long = long                     a + b
long + long* = long*   (mult by 8)     a[b]
long* + long = long*   (mult by 8)     a[b]
long* + long* = ERROR

long - long = long                     a - b
long - long* = ERROR
long* - long = long*   (mult by 8)     a[-b]
long* - long* = long   (div by 8)      dist btwn ptrs

new long[long] = long*

9.6 | Allocation

import init
import new
import delete

init

• Initializes the heap, takes a parameter in x1 and initializes data structure
• If there’s an array, x1 is the length of the array
• Otherwise, x1 = 0

new

• Allocates (arg in x0) many words and returns a pointer
• If unsuccessful, return 0, then you assign the NULL value

code (expr) // result in x0
load and branch to new
check result == 0?
if 0, we didn't allocate
	assign NULL
	add x0, x6, xzr

delete

• Deletes argument in x0
• Delete function doesn’t handle null - need to check

9.7 | Procedures

What do we need to do for wain?

• Import print, init, new, delete
• Initialize x8, x6 (don’t need this for other procedures!)
• Call init
• Save x0, x1 (these are our parameters).
• Reset stack (at end)
• Call br x30 (at end)

f calls g Who should be responsible for saving and restoring registers - caller or callee?

• We’ll do callee-saving - procedure knows the registers it will overwrite so it can save / restore them
• x30 is caller-save - we use blr so by the time we get to the callee, it’s too late

Callee (g) has 2 tasks at the start. What order?

• Save regs
• Point x29 to g’s stack frame

(1) Save regs, then set x29

• Where do we want x29 to be?
• If we want it to be bottom of stack frame - we need to track # regs saved
• If after saving x29 the parameter offsets are lower down, we need to count # of saved regs to compute parameter offsets

(2) Set x29, then save regs

• Don’t need # of regs saved to determine frame pointer
• Still saved x29, so setting x29 from sp isn’t the bottom of the stack frame
• Could add 8 to set it

Alt: caller-save x29

push(x29)
push(x30)
load-and-skip(g, x1)
blr x1
pop(x30)
pop(x29)

9.8 | Procedure arguments

f calls g

• f has the arguments to place into g’s params
• Our approach:
  • put them on the stack so f can put them on the stack
  • use this location as g’s params to avoid work

Why save x29, x30 before args?

• We plan to set x29 to be the bottom of g’s stack frame
• Saving args last places x29 right above them, so args have offset 0, 8, 16…
• f is responsible to setup and remove g’s args/params from the stack

9.9 | Label conflicts

We prepend an ‘F’ to the front of labels (eg. Fprint)

Tutorial 9

Switch statements

if (node.rule is "statement -> SWITCH LPAREN expr RPAREN LBRACE cases default RBRACE") {
	x = genLabelID()
	endLabel = "endswtch" + x
	code(node.children[2])                    // expr
	push(x0)                                  // save on stack*
	node.children[5].parentLabel = endLabel   
	code(node.children[5])                    // expr
	code(node.children[6])                    // default
	print(endLabel + ":")
}
if (node.rule is "cases -> cases case) {
	node.children[0].parentLabel = node.parentLabel
	code(node.children[0])   // cases
	node.children[1].parentLabel = node.parentLabel
	code(node.children[1])   // case
}
if (node.rule is "cases -> .EMPTY"){
	// the mbappe special
}
if (node.rule is "case -> CASE LPAREN expr RPAREN LBRACE statements RBRACE){
	x = genLabelID()
	endLabel = "endCase" + x
	code(node.children[2])      // expr
	pop(x1)                     // x1 = expr we want to match with*
	print("cmp x0, x1")
	print("b.ne " endLabel)     // if, jump to endLabel
	code(node.children[5])
	print("b" node.parentLabel) // else, jump to parentLabel
	print(endLabel + ":")
	push(x1)
}
if (node.rule is "default -> DEFAULT LBRACE statements RBRACE) {
	pop(x0)
	code(node.children[2])
}

Adding break statement

statement -> break

Semantic changes

recur (stmt)
	if (stmt == while)
		skip
	else if (stmt == break)
		error
	else
		for each stmt child in stmt_children
			recur(child)
		for each stmt in code
			recur(stmt)

Code-gen changes

• Branch to the end label of the current while loop and keep track of the level of nesting
• code(Node* node, string whileLabel)
• print("b" + whileLabel)

Pre and post-increment

factor -> PLUS PLUS lvalue
factor -> lvalue PLUS PLUS

lvalue is long -> factor is long
lvalue is long* -> factor is long*

Modifying pre-increment to work on long*

if (node.rule is factor -> PLUS PLUS lvalue){
	code(node.children[2]) // x0 = &lvalue
	ldur x1, [x0, 0]       // x1 = value
	if (lvalue.type == "long"){
		add x1, x1, x11    // x1 = x1 + 1
	}
	else {
		add x1, x1, x8     // x1 = x1 + 8
	}
	stur x1, [x0, 0]       // store x0
	add x0, x1, xzr        // x0 = x1 + 1
}

Grammar for checking null pointers

test -> expr
expr -> term
term -> factor
factor -> STAR factor
factor -> ID

Codegen

if (rule is "test" -> "expr") {
	code(expr)          // x0 = expr
	add x1, x0, xzr     // x1 = expr
	sub x0, x0, x0      // x0 = 0
	cmp x1, x6          // x1 == null (-65536)?
	b.eq 8
	add x0, x0, x11     // cond is true	
}

10 | Loading

10.1 | Loading

Loader’s job:

• Take a program P as input
• Find a location α in memory for P
• Copy P to memory, starting at α
• Return α to the OS

Problem: need to remember which .words were labels

Two passes

1. Load code from file into selected location in memory
2. Using relocation table, update any memory addresses with relocation entries

Tutorial 10

Ex: ARMCOM file to Assembly

0  p: .8byte q
8     br x30
12 q: .8byte p

CODE
b 20
.8byte endModule 
.8byte endCode
.8byte 32         // 20*
br x30            // 28
.8byte 20         // 32*

endcode:
	.8byte 0x1    // relocation entry
	.8byte 20     // first relocation, header takes 20 bytes
	.8byte 0x1
	.8byte 32     // 32
endModule:	

Ex: load to 0x240

0  0x14000005 // b 20
4  0x00000038 // .8byte endModule = 56
8  0x00000000
12 0x00000028 // .8byte endCode = 40
16 0x00000000
20 0x00000024 // to relocate
24 0x0000010c
28 0x00000001
32 0x00000018
36 0x00000000
40 0x00000001 // 0x1 = start of relocation entry
44 0x00000000
48 0x00000014 // 0x14 = 20 = relocate what's at line 20
52 0x00000000

MEM[a + rel - 20] += a - 20
MEM[0x240 + 20 - 20] += 0x240 - 20
0x24 += 0x240 - 0x14 = 0x250

            (250)
0x240 0x00000024
0x244 0x0000010c
0x248 0x00000001
0x24c 0x00000018
0x250 0x00000000

ESD (Extenral Symbol Definition) = specifies a label which must be visible to other programs, like .export

• 0x12
• val = a word with value of label sym
• len = a word which is the length of label sym
• len words, specifying the name of the label sym in ASCII

ESR (External Symbol Reference) = ?

• 0x11
• loc = location of the use of a label sym
• len = a word which is the length of the label sym
• len words, specifying the name of the label sym in ASCII

ESD

.export abc
abc:
0	cmp x3, x4
4	.8byte abc
12	br x30

ANS
b 20
.8byte endModule
.8byte endCode
cmp x3, x4          // 20
.8byte 20           // 24
br x30

endCode:
	.8byte 0x1      // REL entry
	.8byte 24
	.8byte 0x12     // ESD
	.8byte 20       // val = abc was defined at addr 20
	.8byte 3        // len = abc has length 3
	.8byte 97       // 'a'
	.8byte 98       // 'b'
	.8byte 99       // 'c'
	
endModule:

ESR

.import abc
.8byte def
cmp x2, x3
.8byte abc
def:
	br x30

ANS	
b 20
.8byte endModule
.8byte endCode
.8byte 40           // 20 + 20 = 40
cmp x2, x3          // 28
.8byte 0            // 32*
br x30

endCode:
	.8byte 0x1      // REL entry
	.8byte 20
	.8byte 0x11     // ESR
	.8byte 32       // loc = 32*
	.8byte 3        // len = abc has length 3
	.8byte 97       // 'a'
	.8byte 98       // 'b'
	.8byte 99       // 'c'
	
endModule:

Linking Algorithm

1. Check for duplicate exports (can’t be two ESDs for same label)
2. Concatenate code segments
3. Relocate footer of second ARMCOM file
4. Relocate code of second ARMCOM file using REL entries
5. Resolve imports
6. b
7. c

Ex: Link program 1 and 2

b 20
.8byte endModule
.8byte endCode
cmp x3, x4        // push down 16 bytes bc p1 has 16 bytes
.8byte 20
br x30
.8byte 56         // 40 + 16
cmp x2, x3
.8byte 0
br x30
endCode:
	.8byte 24     // REL
	.8byte 0x12
	.8byte 20     // ESD for 'abc'
	.8byte 3
	.8byte 97
	.8byte 98
	.9byte 99

REL:
	.8byte 1
	.8byte 36
REL:
	.8byte 1
	.8byte 48

endModule:

// ASIDE: pushing everything down 16
.8byte 1
.8byte 36         // 20 + 16
.8byte 0x11
.8byte 48         // 36 + 48