# CS 211 - Lecture 12 - Instruction Set Architectures

Bernhard Firner

2025-10-09

---

## Review

* Assembly!

---

## What is Assembly?

* Human-readable (and writeable) programming
  * Thin translation into machine code, which runs directly on the machine

---

## Concepts

* No variables, just registers and memory
* Function arguments are just values stored in a register
* Return values are just values stored in another register
* Loops are just jumps to a previous memory location
* Functions are just instructions sitting in memory

---

## Allocating stack memory

* Just subtract what you want from the `stack pointer` (rsp)

<pre>
// Calculate the nth sequence number and return it.
unsigned long long sequence(unsigned long long n) {
    if (n < 2) {
        return 1;
    }
    // This function cannot clear its stack memory until the next call returns.
    return n + sequence(n-1);
}
</pre>

</div>
<div class="col">

<pre>
sequence:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	cmpq	$1, -8(%rbp)
	ja	.L2
	movl	$1, %eax
	jmp	.L3
.L2:
	movq	-8(%rbp), %rax
	subq	$1, %rax
	movq	%rax, %rdi
	call	sequence
	movq	-8(%rbp), %rdx
	addq	%rdx, %rax
.L3:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
</pre>

</div>
</div>

---

## Stack Documentation

* From Intel 64 and IA-32 Architecture Software Development Manual

---

## Stack Memory

* Decrease the stack `stack pointer` (in esp/rsp) to "allocate" stack memory
* The `push` functions do two things:
  * Set the value at the stack pointer
  * Decrement the stack pointer

---

## Functions and the Stack

* The initial stack value is stored in the `base pointer` (ebp/rbp) for reference
* When a function returns, the stack pointer is set back to the previous value
  * Handled by the `leave` instruction
* When a function completes, it needs to return to the calling location
  * The current code location is the `instruction pointer`
    * Stored in the `eip` or `rip` register
* The calling instruction pointer was pushed onto the stack before a function is called
* The `ret` function pops the `eip` value and jumps back

---

## Accessing Data

* Data is usually accessed through `registers`
* Three addressing types:
  * Immediate (constant values)
  * Register (value in a register)
  * Memory (value where a register points)
    * Direct
    * Indirect

---

## Immediate and Register Addressing

* Immediate: use a constant
  * e.g. `$5` refers to the constant value 5
  * `movq $5, %rdx` moves 5 into rdx
* Register addressing get the value in a register
  * `movq %rax, %rdi` copies the value in rax to rdi

---

## Memory Addressing

* These are pointers in C
  * `movq	%rdi, -8(%rbp)`
  * Moves the register value at rdi into the memory at (rbp - 8)
  * The stack grows down, so in C:
    * `*(rbp - 8) = rdi`
* If the memory location is hard-coded, we call it `direct`
* When the location is in a register, it is `indirect`

---

## Displacement and Scaling

* Arrays are very common, so syntax supports them
  * `8(%rax)` is `memory[%rax + 8]`
  * like `char_ptr[8]`
* But most displacement has a scaling factor
  * E.g. ints have a scale of 4 bytes
  * `8(%rax, %rcx, 4)` is `memory[%rax + 8 + 4*%rcx]`
* Can skip the displacement for familiar array access
  * `(%rax, %rcx, 4)` is `memory[%rax + 4*%rcx]`

---

## What is happening?

* What does all of this have to do with computer architecture?
* Content outline:
  * Walk through the life of an instruction
    * Begin with idyllic view
    * Introduce pipeline complexity
  * Zoom back out to C, showing performance ramifications on the way

---

## The Life of an Instruction

* You run a program. Now what?
* It is loaded into memory.
* Where does it start?
  * At main
* What does that mean?
  * The `instruction pointer` is set to the address of main

</div>
<div class="col">

</div>
</div>

---

## Instruction Loading (idyllic)

* Instructions are loaded one at a time and executed
* Each clock cycle, we increment the `instruction pointer` by one
  * (aside: some architectures call the `instruction pointer` the `program counter`)

</div>
<div class="col">

</div>
</div>

---

## First Problem

* Some instructions change the instruction pointer
* Could jump to a specific address
* Could calculate it relative to something else

---

## Instruction Loading

* Okay, some math may find a new IP value
* Speaking of math
  * The opcode of the loaded instruction may be math
  * We'll have to load some register values

</div>
<div class="col">

</div>
</div>

---

## Halfway There

* MUX stands for "multiplexor"
  * Allow you to select an input
  * Imagine control lines from the opcodes of the fetched instruction

</div>
<div class="col">

</div>
</div>

---

## Missing Pieces

* Remember all of the access types?
  * Immediate requires an opcode input to the ALU
  * Register inputs to both ALUs
  * But what about direct and indirect memory access?
* And what about calculated instruction ponters?

---

## Everything But Memory

* We select between the next instruction and a calculated instruction
* But what about a fetched memory location?
* And what about the memory in general?

</div>
<div class="col">

</div>
</div>

---

## What About movq?

* Now we can use direct and indirect memory access
* And we can set the instruction pointer several ways
  * Increment
  * Jump to an absolute address
  * Jump to a calculated address
* But how do we get values into registers?

</div>
<div class="col">

</div>
</div>

---

## Complete?

* Math
  * Either immediate, from the instruction, or from registers
* Memory
  * Access from the instruction, register, or math
* Instruction Pointer
  * Incremented by 1, from math, or from memory

</div>
<div class="col">

</div>
</div>

---

## Example

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6.png" />

</div>
</div>

---

## Example

* pushq puts value in register rbp into memory

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-1.png" />

</div>
</div>

---

## Example

* movq loads one register and writes back into another

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-2.png" />

</div>
</div>

---

## Example

* subq subtracts an immediate from a register and writes back to a register

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-3.png" />

</div>
</div>

---

## Example

* movq inserts a value into a calculated location

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-4.png" />

</div>
</div>

---

## Great!

* Now let's make it more complicated
* We don't want to wait for each instruction to finish before going on to the next
* So we'll add buffers at some steps to remember the current state of things
  * Clock ticks will cause values to leave the buffers and begin execution
  * That keeps things synchronized
* This is called `pipelined` execution

---

## Pipeline

* Each gray bar is a buffer
* This is a pipeline
  * Increases throughput roughly 5x

</div>
<div class="col">

</div>
</div>

---

## Canonical Drawing (wikipedia)

---

## Named Steps

* Instruction Fetch
* Instruction Decode and Register Fetch
* Execute or Address Calculation
* Memory Access
* Write back

---

## Done? No!

* There are obviously depedencies between instructions
* And what if there is a conditional jump? 
  * How do we know which branch we should execute?
* Pipelining brings up a lot of issues, which we'll have to cover

---

## Realistic View - 1995

---

## Realistic View - 2000

---

## Realistic View - 2006
<img style="width: 100%" class="r-stretch" src="./figures/IntelFigure2-2_IntelCoreMicroarchitecturePipelineFunctionality2006.png" />

---

## Big field

* There are plenty of optimizations
  * Branch prediction
  * Speculative execution
  * Instruction reordering and rewriting
  * And more!
* We won't be able to go into everything
* Next time we'll go over a few pipelining problems and solutions