Programming paradigms — part 3

These notes are meant to give the reader the fundamentals to follow what is covered under Stanford CS107 Programming paradigms.

Part 3 covers lectures 8 to 10, which is basically about:

• The stack memory
• Some intuition on assembly code

No medium membership? No problem, you can access all of the content of my notes here: https://github.com/GabrielBarberini/EECS/blob/master/notes/personal/Programming_paradigms_CS107.pdf

The stack pointer

The stack pointer is a special CPU register that holds the memory address of the top of the stack. it essentially moves step-by-step along with every piece of data that is allocated on the stack during the function call and execution process.

Naming conventions

• SP (Stack Pointer): Used in 16-bit architectures.
• ESP (Extended Stack Pointer): Used in 32-bit architectures.
• RSP (Register Stack Pointer): Used in 64-bit architectures.

Activation record

An activation record is a logical concept used to describe the data structure that holds all the information necessary to execute a function. It’s the formal name for the information held in a stack frame. Mind that the exact contents and layout of the stack vary by processor architecture and function call convention (more info at: https://manybutfinite.com/post/journey-to-the-stack/)

Suppose we have:

When:

int main() {
    A();
    return 0;
}

is executed, the stack pointer descends (higher memory address → lower memory address) by the amount given by A’s activation record memory footprint, then B’s and C’s, without losing track of the higher frames.

Zeroing on the activation record

Now suppose we have:

void foo(int bar, int *baz) {
    char snink[4];
    short *why;
}

Foo’s activation record of would be filled top-down starting right-to-left on the function signature:

Where Saved PC is also known as Program Counter or Return Address and it stores the address of the instruction to be executed upon the function’s exit.

It’s worth mentioning that some architectures like Intel’s x86 also contain something called the Frame Pointer, Base Pointer or EBP, which sits on top of the Saved PC pointing to a fixed location within the stack frame of the function currently running providing a stable reference point (base) for access to arguments and local variables, traditionally for such architectures both the base pointer (EBP) and the return address (Saved PC) are saved on the stack during a function call.

Intel x86 stack example, source: https://manybutfinite.com/post/journey-to-the-stack/

In modern compilers and architectures, there’s a technique called frame pointer omission (FPO). This technique eliminates the use of the base pointer (EBP) to save registers, making the function more efficient by freeing up EBP for general-purpose use. In these cases:

• Only the Saved PC (return address) is pushed onto the stack.
• The stack is managed solely by the stack pointer (ESP), and offsets from ESP are used to access local variables and parameters.

This results in slightly faster and smaller code because there’s no need to preserve or restore the base pointer, and fewer instructions are used during function calls and returns.

Continuing, suppose we now have:

int main(int argc, char** argv) {
    int i = 4;
    foo(i, &i);
    return 0;
}

In such case, the activation record diagram for it would look like:

More information about argc and argv can be found here: https://stackoverflow.com/questions/3024197/what-does-int-argc-char-argv-mean

Partial activation record of main():

During the partial activation record for main (performed by main’s caller), we have parameters and program counter initialization followed by control delegation, namely:

1. caller makes room for main stack data
2. argc and argv are initialized (pushed into main stack) by the caller;
3. control is transferred to main and saved PC (return address) is initialized with the address for which execution will continue once main() returns;

Once main’s partial activation is complete, main’s function prologue allocates space for its local variables and initializes them.

Partial activation record of foo():

During the partial activation record for foo (performed by main), the cycle repeats itself and we also have parameters and program counter initialization followed control delegation, namely:

1. main makes room for foo stack data
2. The parameters passed to foo() within main (i and &i) are pushed by the caller (main) onto foo’s stack;
3. control is transferred to foo and saved PC is also pushed onto foo’s stack;

Once foo’s partial activation is complete, foo’s function prologue allocates space for its local variables and initializes them.

Taking M as a notation for “all RAM”, we could rewrite the partial activation record of foo() with a mock assembly language to help grasp the flow:

...

SP = SP - 4;         # Allocate space for main's local variable 'i'
M[SP] = 4;           # Initialize 'i' with the value 4

# -------------------------
# Partial Activation of foo
# -------------------------
SP = SP - 8;         # Allocate space for foo's arguments
R1 = M[SP+8];        # Load the value of `i` into register R1
R2 = SP + 8;         # Load the address of `i` into register R2
M[SP] = R1;          # Push the value of R1 as foo's first argument
M[SP+4] = R2;        # Push the value of R2 as foo's second argument

# Control transfer to foo(), automatically pushes the return address (Saved PC) onto the stack
call <foo>

Assembly

Assembly code (or assembly language) is a low-level programming language that is closely related to machine code, the instructions directly executed by a computer’s CPU. However, instead of writing in binary or hexadecimal (which machine code uses), assembly code allows programmers to use symbolic names and mnemonics that are easier to understand. Each assembly instruction corresponds to a single machine instruction, providing control over hardware at a detailed level.

Registers

Registers are small and fast storage locations within the CPU that hold data temporarily during instruction execution. The relationship between assembly code and registers is tight because assembly instructions often involve manipulating data stored directly in these registers.

The CPU constantly moves data between RAM (which is slow compared to registers) and registers. Data and instructions are loaded from RAM into registers, processed by the CPU, and then results may be written back to RAM.

C to assembly

Continuing with our mock assembly language where M is a notation for “all RAM”, suppose we have the following C code:

int i;
int j;

i = 10;
j = i+7;
j++;

How would it translate to our mock assembly?

Half word notation

Registers are typically designed to hold a single word and its operations are made in word-wide steps.

To properly store s1 in RAM at s1 = i we have to cast/truncate the 200 int (4 bytes) to short (2 bytes) by using a different mnemonic that operates only half-a-word.

Please note that the memory allocation is made arbitrarily here to illustrate the potential for collision when casting from a larger to a smaller data type if not handled properly at the assembly level. In fact, if we are not using structs, the order of allocation on the stack can vary and is not always trivial. For more information, see: https://stackoverflow.com/questions/1102049/order-of-local-variable-allocation-on-the-stack.

Enjoyed it so far?
See you in part 4!