PKU Introduction to Computer Systems

Welcome to Seminar of ICS26!

Instructor: Wenxin Li(李文新) lwx@pku.edu.cn

TA: Junqi Xu(许俊岐) qwq4006@stu.pku.edu.cn

Time: Wednesday 18:40–20:30

Location: 地学208

Codeberg: https://codeberg.org/Lychnis/pku-ics-course-materials

NEWS

Important

2026.10.20

Warning

This lab is very challenging. Please start early.

Arch Lab is released!

Due: Mon, Nov. 3 at 11:59pm

Estimated Time to Complete without AI: more than 10 hours

Estimated Time to Complete with AI: 20 minutes (weak LLM may fail)

Important

2026.10.8

Attack Lab is released!

Due: Mon, Oct 22 at 8:00am

Estimated Time to Complete without AI: 3 hours

Estimated Time to Complete with AI: 10 minutes (using GPT-6.1 Sol)

Important

2026.9.22

Bomb Lab is released!

Due: Thu, Oct 13 at 11:59pm

Estimated Time to Complete without AI or decompiler: 4 hours (1 more hour for 「CENSORED」)

Estimated Time to Complete with AI: 10 minutes (using GPT-5.6 Sol)

Estimated Time to Complete with decompiler: 5 minutes (you are cheating!)

Warning

Be careful! If you call explode_bomb on xLab, your score would be permanently blown off! (Well, minus 0.5 per call.)

Tip

You have to complete this lab on xLab at least once to gain score. But to protect your GPA, you could try to solve the puzzle locally first. Using GDB is also a good (and maybe necessary) choice.

Important

2026.9.14

Data Lab is released!

Due: Mon, Sep 28 at 8:00am

Estimated Time to Complete without AI: 4 hours

Estimated Time to Complete with AI: 5 minutes (depends on response time)

Tip

2026.9.13

The AutoLab website is now live at https://autolab.pku-ics.com!

SEPTEMBER 2026

Important

16 Weds.

Week 1 Note

Week 2 Slides

Week 2 Note

Important

23 Weds.

Week 3 Slides

Week 3 Note

Important

30 Weds.

Week 4 Slides

Week 4 Note

OCTOBER 2026

Important

14 Weds.

Week 6 Slides

Important

21 Weds.

Week 7 Slides

Lecture Notes

Week 1 - Overview

Week 2 - Data

Week 3 - Assembly I

Week 4 - Assembly II

Overview

Lab Wanderings

You need to complete the following 8 experiments within one semester:

Data Lab - Write code using a very limited set of operators (^, |, &, etc.).

/*
 * bitXnor - ~(x^y) using only ~ and |
 *   Example: bitXnor(6, -5) = 2
 *   Legal ops: ~ |
 *   Max ops: 7
 *   Rating: 1
 */
int bitXnor(int x, int y) {
    // Replace 0 with your implementation of bitXnor.
    return 0;
}

Bomb Lab - Read assembly code (x86-64) and solve puzzles.

    .section .rodata
.Lformat:
    .string "%d %d"

    .text
    .globl phase_1
    .type phase_1, @function
    .extern explode_bomb
    .extern __isoc99_sscanf

phase_1:
    subq    $24, %rsp              

    leaq    8(%rsp), %rdx         
    leaq    12(%rsp), %rcx        
    leaq    .Lformat(%rip), %rsi  
    xorl    %eax, %eax            
    call    __isoc99_sscanf@PLT

    cmpl    $2, %eax               
    jne     .Lexplode

    cmpl    $6, 8(%rsp)            
    jne     .Lexplode

    movl    8(%rsp), %eax          
    addl    %eax, %eax             
    addl    $1, %eax               

    cmpl    %eax, 12(%rsp)         
    jne     .Lexplode

    addq    $24, %rsp              
    ret

.Lexplode:
    call    explode_bomb           
    addq    $24, %rsp
    ret

    .size phase_1, .-phase_1
    .section .note.GNU-stack,"",@progbits

Attack Lab - Read vulnerable assembly code and hack it.

    .section .rodata
success_msg:
    .string "Attack successful: touch1 reached."

normal_msg:
    .string "Returned normally."

    .text

    .globl main
    .type main, @function

main:
    pushq   %rbp
    movq    %rsp, %rbp

    call    getbuf                  

    leaq    normal_msg(%rip), %rdi
    call    puts@PLT                # Printed only if getbuf returns normally

    xorl    %eax, %eax
    popq    %rbp
    ret


    .globl getbuf
    .type getbuf, @function

getbuf:
    subq    $40, %rsp               

    movq    %rsp, %rsi              
    xorl    %edi, %edi              
    movl    $128, %edx              
    call    read@PLT                

    movl    $1, %eax
    addq    $40, %rsp
    ret                             


    .globl touch1
    .type touch1, @function

touch1:
    leaq    success_msg(%rip), %rdi
    call    puts@PLT

    xorl    %edi, %edi
    call    exit@PLT                # Terminate after successful exploitation

    ud2                             # Should never be reached


    .size main, .-main
    .size getbuf, .-getbuf
    .size touch1, .-touch1

    .section .note.GNU-stack,"",@progbits

Arch Lab - Write assembly code that leverages the pipeline for very high execution efficiency.

Cache Lab - Write C code that leverages the cache, minimizing the number of cache misses.

Shell Lab - Write a tiny OS-level shell.

Malloc Lab - Write a C-style memory allocator that uses memory efficiently.

Proxy Lab - Write an I/O proxy for a server.

Happy coding~

Use Linux via CLI

Just like Windows, Linux is an operating system. Unlike Windows, Linux is distributed under an open-source license, and it is extremely lightweight. For most computer users, Windows (or macOS) can fully meet their needs, and there is no reason for them to learn Linux. But for programmers or CS researchers like us, Linux is likely to be our main operating system.

All the labs in our course run on Ubuntu 24.04 LTS. Ubuntu is a Linux distribution (or, in short, a “distro”). You may wonder what a Linux distribution is. In short, Linux provides just the “kernel” of an operating system, with little user interface, making it hard to “use” on its own. A Linux distribution provides a “shell” for Linux, allowing users to interact with it more easily.

Tip

Want to learn a little more about Linux? Click here!

Want to install an Ubuntu virtual machine on your local Windows or macOS machine? You could visit the official Ubuntu website.

Want to connect your virtual machine through vscode? This document may help. Turning to your AI agents is even better.

In this course, we focus only on Ubuntu 24.04 LTS. We can generally use Ubuntu in two ways: through a GUI or the CLI. A GUI (Graphical User Interface) is a popular and visually oriented way to interact with a computer. It is the only interface most people have encountered and is likely what you are using to browse this document right now. A CLI (Command-Line Interface), however, is an old-school textual interface used primarily by programmers.

It seems that the GUI is the GOAT and there is no reason to learn the “outdated” CLI. Unfortunately, the reason programmers prefer the CLI is not simply that using it looks cool (at least, that is not the main reason). You might find the answer in the following two articles:

Nature: Five reasons why researchers should learn to love the command line

Course Overview + Introduction to the Shell · Missing Semester

Whether or not you read the articles above, my job is to teach you how to use Ubuntu via the CLI. It is actually quite simple, so here we go.

Ubuntu CLI Basics

Whichever way you installed Ubuntu, start it. You are likely to see a text window with your cursor on the last line:

                               Your Cursor
                                    |
                                    v
your-user-name@your-machine-name:~$

We call all the text before your cursor on the last line the shell prompt. By default, it tells you who you are and where you are. You can customize your shell prompt in Ubuntu just for fun.

Note

For things that are just for fun, I won’t tell you the details, but I will tell you that they exist. In the era of AI, it won’t be hard to learn about things you know exist, and all you need is interest.

Let’s type something, such as a greeting, and press Enter:

Hello?

Unfortunately, the Ubuntu shell is not an AI agent, so it won’t reply “Hello, user!” or anything similar. Instead, it will likely display a message:

Hello?: command not found

Here we encounter the technical term “command”. Actually, the shell (sh) is a command-language interpreter, so it treats all your input as commands. The shell reads your input, tries to run it, and gives you the result. For example, the error message Hello? command not found is the result of “running” our greeting command Hello?. It seems that Hello? is not a valid command, so what is a valid command? Remember, in the CLI world, if you need help, just type help.

help

help itself is a valid command and shows all built-in commands, including itself. However, built-in commands are far from meeting our needs. GNU Coreutils provides more powerful shell commands. You could use the info command to take a look.

info coreutils

Well, I have to admit that learning the CLI from reference pages is not always a pleasant experience. When possible, we prefer to consult a cheat sheet. Turning to AI agents is also a good choice.

Note

To be exact, bash, an essential component of the Ubuntu shell, is the program that actually serves as the interpreter. We won’t go into implementation details because this course is for beginners and we want to focus on things that are really interesting.

Note

The term interpreter shouldn’t be new to you, given that all your Python code is executed by a Python interpreter (CPython, most likely). Using the shell is like using Python in interactive mode (python -i): you type one line of code and press Enter; the interpreter then parses and “evaluates” your code before waiting for your next input.

The shell also has a non-interactive mode. You can write a .sh script and execute it with the shell. For more information, click here.

If you have taken Practice of Software Design, another course I teach as a TA, you should already be familiar with these concepts, since you have implemented a Lisp interpreter yourself :>.

Basic Commands

Since each command is fairly easy to learn, I will just show you the most important ones.

pwd - Print the path of the current working directory.

pwd

ls - List files and directories. Use -l for a detailed list and -a to include hidden files.

ls -la

cd - Change the current working directory.

cd ~/projects

mkdir - Create a new directory. The -p option also creates missing parent directories.

mkdir -p projects/ics

touch - Create an empty file, or update a file’s modification time if it already exists.

touch notes.txt

cp - Copy a file or directory.

cp main.c main-backup.c

mv - Move or rename a file or directory.

mv old-name.c new-name.c

rm - Remove a file. Be careful: removed files are not normally put in a recycle bin.

rm old-name.c

cat - Print the contents of a file to the terminal.

cat README.md

less - Read a long text file one page at a time.

less large-log.txt

head and tail - Show the first or last lines of a file.

head -n 5 output.txt
tail -n 5 output.txt

grep - Search for lines that contain a pattern.

grep -n "main" main.c

find - Search for files and directories under a given path.

find . -name "*.c"

echo - Print text or the value of a shell variable.

echo $PATH

man - Open the manual page for a command.

man ls

info - Read the GNU Info documentation for a command or topic.

info coreutils

chmod - Change file permissions, such as making a script executable.

chmod +x run.sh

gcc - Compile C source code into an executable program.

gcc hello.c -o hello

make - Build a project according to the rules in its Makefile.

make

Tip

A directory (often called a folder) is a container for files and other directories.

A file stores data, such as text or source code.

In projects/ics/main.c, projects and ics are directories, while main.c is a file.

Tip

Use man for a concise command reference. Use info for more detailed, topic-oriented documentation, especially for GNU programs.

Reference Materials

1. What is Linux? - Linux.com
2. Nature: Five reasons why researchers should learn to love the command line
3. MIT CSAIL: The Missing Semester
4. The Linux command line for beginners | Ubuntu
5. Welcome to the terminal - Ubuntu Server documentation
6. Ubuntu CLI Cheat Sheet
7. Ubuntu CLI Cheat Sheet (PDF ver.)

A Journey through CSAPP

You may have heard that ICS is horrible, difficult, time consuming, GPA threatening…

Now I tell you they are all true.

You may also have heard that ICS is important, useful, inspiring, high-quality…

They are all true either.

And it is also true that you have to overcome ICS to graduate.

I will introduce what you would get from CSAPP, and I will try my best to help you find motivations to learn CSAPP. Anyway, to learn what you want to learn would usually be easier than to learn what you are forced to learn.

ICS teaches C, but it is not mainly about writing algorithms in C. Instead, it explores how C works under the hood and how to use it for advanced programming tasks such as signal processing, network programming, and concurrent programming, which play key roles in frontiers of computer science even in era of AI.

ICS focuses on the deeper principles beneath C. Once you understand them, you will have a stronger foundation for learning other programming languages.

By studying ICS, you will gain a deeper understanding of high-level languages, explain phenomena that may seem mysterious to ordinary programmers, and make small but highly significant optimizations to your programs.

Chapter 2: Data

An int can represent negative numbers. Have you ever wondered how a computer stores them?

char and double are common C types. Have you wondered how a computer stores characters and floating-point values?

An int variable occupies 4 bytes, while a char variable occupies 1 byte. How many bytes does the following structure occupy? Is the answer really 5 bytes?

struct {
    int i;
    char c;
};

After this chapter, you will have a comprehensive and clear understanding of how data is represented and stored in a computer.

Chapter 3: Assembly

When we program in a high-level language such as C, have you ever wondered how a computer executes the program we write?

A compiler transforms high-level code into an intermediate representation (IR), then into assembly language (A). After linking and other possible transformations, the result becomes executable code.

High-level code -> IR -> assembly -> executable code

Compared with high-level languages, assembly language gives a clearer picture of how programs run on a machine. Many compiler optimizations also take place at the assembly level. In this chapter, you will begin to understand x86-64 assembly and glimpse the lower-level form of code.

Chapter 4: Arch

When a computer is asked to execute a piece of code, how does it organize the work? Does it simply execute one instruction after another?

In this chapter, you will understand the secrets behind single-core CPU performance and experience the power of pipelining firsthand.

Chapter 6: Cache

When buying a laptop, we often see specifications such as:

RAM: 16 GB
Storage: 512 GB

What is the difference between memory and storage capacity? How does memory work? Is it really just a very large array?

In this chapter, you will uncover the workings of computer storage systems and understand why 16 GB of RAM and a 512 GB solid-state drive can cost roughly the same.

Chapter 7: Linking

Have you ever wondered about these questions?

• Why must a C program be compiled before it can run?
• What does #include <stdio.h> mean, and what exactly does it do?
• Does a Hello, world! program really execute only one output statement?
• What is a library file, and how is it different from our main.c?

In this chapter, you will gain an initial understanding of compilation, compilers and linkers. You will also appreciate the importance of code reuse and the effort programmers have invested in making it possible.

Chapter 8: Signal

Our computers can clearly run multiple programs at the same time. For example, your browser and your operating system appear to be running simultaneously now.

How can programs run at the same time? Can a single-core CPU run multiple programs simultaneously? Can different programs communicate with one another, and how do they do it?

In this chapter, you will get your first look at concurrency and parallelism, and develop a clearer understanding of operating systems, shells, and cooperation between programs.

Chapter 9: Malloc

Suppose two unrelated programs, A and B, each have a pointer named pa and pb. If the two programs are running simultaneously and the two pointers have the same value at runtime, do they point to the same address of the memory?

Memory errors are common and serious problems in C programs. Why do they happen? Why can’t the compiler detect them automatically?

In this chapter, you will develop a deep understanding of the computer’s address system and appreciate the importance of address-space isolation.

Chapter 10: I/O

Do you remember the file streams introduced in Introduction to Computing? What is the difference between a file stream and the standard input/output streams?

I/O is an important way for a program to communicate with the outside world, but it also hides many security risks. In this chapter, you will gain a thorough understanding of I/O streams and learn how to read and write data robustly.

Chapter 11: Web

When we turn on a computer, the first thing we do is often connect to the Internet.

We can insert a USB drive into a computer and exchange information between the drive and the computer. That is easy to understand. But when we open WeChat and message a classmate in Shanghai, we are exchanging information between a computer in Shanghai and a computer in Beijing. That is far more remarkable.

In this chapter, you will gain an initial understanding of how the Internet works and try using C to send and receive data over a network.

Chapter 12: Concurrency

Concurrency is everywhere today, but concurrent programming is not trivial.

for (int i = 0; i < 500; ++i) {
    ++j;
}

Suppose j initially equals 0. After one program executes the loop above, its value becomes 500. If two programs execute the loop concurrently, the final value may be any number between 500 and 1000, inclusive.

In this chapter, you will learn to handle one of the most common problems in concurrent programming: race conditions. You will also understand the principles behind seemingly inexplicable concurrent behavior.

Epilogue

It would be a long but meaningful journey. Keep up, and you would gain more than you could imagine.

Good luck!

Data

Let’s begin with pointers.

int x = 42;
int* px = &x;

#![allow(unused)]
fn main() {
let x = 42;
let px = &raw const x;
}

Raw pointers store addresses, and nothing else. Raw pointers even don’t guarantee the validity of addresses they hold. Raw pointers usually have types in modern programming languages, int* for example, which makes it easier to access data from it.

It is easy for programmers to access data from a pointer, thanks to abstractions:

int tmp = *px;

#![allow(unused)]
fn main() {
let tmp = unsafe { *px };
}

However, it is not that easy for a compiler to process a data access. To complete an access, the compiler needs to know not only where the data is stored, but also how the data is organized. This is our topic today: information structure.

At the lowest level that is useful to us, memory is a long sequence of bytes. Each byte has a numeric address, and an object occupies a consecutive range of addresses. A pointer stores the address of (usually) the first byte of an object. The pointer’s type tells the compiler how many bytes to read, how those bytes are aligned, and how to interpret them.

The same bytes can therefore have different meanings. The bit pattern 01000001 can be the integer 65, the character A, part of a floating-point value, or an instruction. An encoding gives a bit pattern a meaning; a type tells a programming language which encoding and operations to use.

Information Structure - Top-Down

Stack & Heap

Let’s dive a litter deeper into the memory - from programs’ perspective. Programs view memory as consisting of two parts: the stack and the heap.

The stack is commonly used for function calls. A call creates a stack frame containing information such as parameters, local variables, and the return address. A local variable normally lives until its function returns. The stack is fast and automatically reclaimed, but its size is limited.

Note

Stack vs. Stack Frame

A stack is allocated in memory, while a stack frame is created on the stack.

A stack is created when a program executes. (More precisely, each thread has its own stack.) A stack frame is created when a function is called.

You may have heard of stack overflow. As you can imagine, if you call a recursive function, many stack frames are created during the call. If too many stack frames exist at the same time, the stack runs out of space, and a stack overflow occurs. That’s why standard libraries prefer iteration over recursion.

The heap is a region managed by a memory allocator. It is used when an object must outlive the current function or when its size is known only at run time. The heap is much larger than the stack, but accessing it is usually slower.

#include <stdio.h>
#include <stdlib.h>

// Allocate an int on the heap with an initial value of val.
// val is a parameter, which is stored on the stack
int* make_number(int val) {
    // p is a local variable, which is stored on the stack.
    int* p = malloc(sizeof *p); // sizeof *p === sizeof int
    if (p == NULL) { // If malloc fails, it returns NULL.
        return NULL;
    }
    // *p accesses an address on the heap.
    *p = val;
    return p;
}

int main(void) {
    int* p = make_number();
    if (p != NULL) {
        printf("%d\n", *p);
        free(p); // The pointer returned by malloc must be freed manually.
    }
}

fn make_number() -> Box<i32> {
    Box::new(42)
}

/// This function can safely leak an i32 on the heap.
fn make_number_leak() -> &'static mut i32 {
    Box::new(42).leak()
} 

fn main() {
    // number is a local variable, which is stored on the stack.
    let number = make_number();
    // *number accesses an address on the heap.
    println!("{}", *number);
    // number is a local variable, which is stored on the stack.
    let number = make_number_leak()
    // Rust automatically dereference number, which also accesses an address on the heap.
    println!("{}", number);
}

For more details, see the GNU C Library memory allocation documentation and the Rust documentation for Box.

Type Layout

An abstract type has values and operations. A concrete implementation also needs a layout: the size of each value, its alignment requirement, and the position of every field. sizeof in C and size_of in Rust report the size in bytes, but the result depends on the type and the target machine.

sizeof(char) is exactly 1 in C, but a C byte is defined by CHAR_BIT and is not required by the language standard to contain eight bits. On our Ubuntu machines, char has 8 bits. The sizes of int, pointers, and structures are implementation-defined. Rust’s primitive integer types have fixed widths (u8, i32, u64, and so on), while usize and isize are chosen to hold a pointer-sized value on the target.

Most types also have an alignment. An object with alignment 4 must start at an address divisible by 4. A structure can consequently contain padding between fields and at its end. The trailing padding makes every element of an array correctly aligned.

#include <stdio.h>

int main() {
    printf("int: size = %zu, alignment = %zu\n",
           sizeof(int), _Alignof(int));
    printf("char: size = %zu, alignment = %zu\n",
           sizeof(char), _Alignof(char));
    printf("double: size = %zu, alignment = %zu\n",
           sizeof(double), _Alignof(double));
}

#include<stdio.h>

int main() {
    printf("int*: size = %zu, alignment = %zu\n",
           sizeof(int*), _Alignof(int*));
}

#include <stddef.h>
#include <stdio.h>

typedef struct Student {
    unsigned id;
    char name[20];
    double score;
} Student;

int main(void) {
    Student student = {2200015213, "Jill", 3.92};

    printf("size = %zu\n", sizeof(Student));
    printf("alignment = %zu\n", _Alignof(Student));
    printf("offset of id = %zu\n", offsetof(Student, id));
    printf("offset of name = %zu\n", offsetof(Student, name));
    printf("offset of score = %zu\n", offsetof(Student, score));
}

#include <stdio.h>

typedef union VariantNumber {
    int integer;
    char big_integer[20];
    double real_number;
} VariantNumber;

int main(void) {
    VariantNumber uni = {.real_number = 0.33};

    printf("size = %zu\n", sizeof(VariantNumber));
    printf("alignment = %zu\n", _Alignof(VariantNumber));
    printf("real number = %f\n", uni.real_number);

    uni.integer = 42; // The integer member is now the value we just wrote.
    printf("integer = %d\n", uni.integer);
}

#include <stdio.h>

int main(void) {
    int arr[4] = {1, 2, 3, 4};

    printf("array size = %zu\n", sizeof arr);
    printf("element count = %zu\n", sizeof arr / sizeof arr[0]);
    printf("third element = %d\n", arr[2]);
}

For exact rules, see the C17 object representation and alignment clauses and the Rust Reference: Type layout.

Bytes

The smallest addressable unit is a byte. Hexadecimal is a convenient way to write bytes: one hexadecimal digit represents four bits, so two digits represent an 8-bit byte. The following program prints the native byte order of 0x12345678.

#include <stdint.h>
#include <stdio.h>
#include <string.h>

int main(void) {
    uint32_t value = UINT32_C(0x12345678);
    unsigned char bytes[sizeof value];
    memcpy(bytes, &value, sizeof bytes);

    for (size_t i = 0; i < sizeof bytes; ++i) {
        printf("%02x%s", bytes[i], i + 1 == sizeof bytes ? "\n" : " ");
    }
}

fn main() {
    let value: u32 = 0x1234_5678;
    let bytes = value.to_ne_bytes();

    for (i, byte) in bytes.iter().enumerate() {
        if i != 0 {
            print!(" ");
        }
        print!("{byte:02x}");
    }
    println!();
}

On a little-endian machine, the output is 78 56 34 12: the least significant byte is stored at the lowest address. On a big-endian machine, it is 12 34 56 78.

You can read more in the C standard’s object representation rules and the Rust documentation for integer byte-order conversions.

Encodings

An encoding is a rule that maps values to bit patterns. A fixed-width encoding has a finite number of patterns, so it cannot represent every mathematical value. When a value does not fit, the language or library must define what happens: wrap around, report an error, round, or refuse the conversion.

Do not confuse a value with its encoding. The number 65 and the character A are different concepts even though ASCII assigns the same code point to them. Likewise, the bytes of a signed integer and the bytes of an unsigned integer can be identical while their interpreted values differ.

Integer

An unsigned w-bit integer uses the bits as a binary positional number. For example, 00000101 is \(2^2 + 2^0 = 5\). With w bits, unsigned values range from \(0\) to \(2^w - 1\). Arithmetic is performed modulo \(2^w\): after \(255\) comes \(0\) in an 8-bit unsigned type. (11111111 + 00000001 = 00000000)

Signed integers on the machines used in this course use two’s complement. For a w-bit signed value, the range is \(-2^{w-1}\) through \(2^{w-1}-1\). The highest bit contributes a negative weight, so the pattern for -1 is all ones. Two’s complement makes addition and subtraction use the same circuitry for signed and unsigned values.

The C17 standard permits more than one signed representation, although two’s complement is used by modern desktop systems. Rust specifies two’s-complement signed integers. When exchanging binary data, choose an explicit width such as uint32_t or u32; plain int is not a portable file format.

Here the bit pattern is preserved while the interpretation changes:

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

int main(void) {
    uint32_t u = UINT32_MAX;
    printf("u + 1 = %" PRIu32 "\n", u + 1);

    int32_t n = -1;
    printf("same bits as unsigned = %" PRIu32 "\n", (uint32_t)n);
}

fn main() {
    let u = u32::MAX;
    println!("u + 1 = {}", u.wrapping_add(1));

    let n: i32 = -1;
    println!("same bits as unsigned = {}", n as u32);
}

Unsigned overflow is defined modulo the width in both examples. In C, signed overflow is undefined behavior; the compiler may assume it never happens and optimize based on that assumption. In Rust, a + b checks for overflow in debug builds and can panic, while a release profile may use wrapping behavior. Rust makes the desired policy explicit with checked_add, saturating_add, and wrapping_add.

Bitwise operations work directly on bits: & keeps bits set in both operands, | keeps bits set in either operand, ^ keeps bits that differ, and ~ flips every bit. A left shift usually multiplies an unsigned value by a power of two when no significant bit is lost. Right shift of an unsigned value fills with zeroes; right shift of a signed negative value is language- and implementation-specific in C, while Rust defines an arithmetic right shift for signed integers.

Note

SAR vs. SHR

SAR, Shift Arithmetic Right, fills with the value of the sign bit. SHR, SHift logical Right, fills with zeroes. For signed negative integers, most C compilers do SAR for them.

Mixed signed and unsigned arithmetic is a common C surprise. The usual arithmetic conversions may convert a negative int to a very large unsigned value. Rust refuses to compare different integer types until the programmer writes an explicit conversion. Prefer one integer type for an expression and use checked conversions at boundaries.

For the exact rules, see C17 integer representations and conversions, sections 6.2.6.2 and 6.3.1.3, the Rust Reference: Numeric types, and the Rust book’s integer chapter.

Real Number

Computers cannot store most real numbers exactly with a finite number of bits. A floating-point value is similar to scientific notation, but its base is usually 2:

\(value = (-1)^{sign} * {significand} * 2^{exponent - bias}\)

Tip

By contrast, 10 base scientific notation could be written as:

\(value = (-1)^{sign} * {significand} * 10^{exponent}\)

IEEE 754 binary32 (float in common C implementations and f32 in Rust) has 1 sign bit, 8 exponent bits, and 23 fraction bits. Binary64 (double and f64) has 1 sign bit, 11 exponent bits, and 52 fraction bits. The exponent is stored with a bias so that ordinary positive and negative exponents can be compared as unsigned fields. There are also encodings for positive and negative zero, subnormal numbers close to zero, positive and negative infinity, and NaN (not a number).

Tip

According to IEEE 754, the bias of a k-bits exponent floating-point value is \(2^{k-1} - 1\).

The decimal value 0.1 has no finite binary expansion, so converting it to binary64 rounds it to the nearest representable value. Repeated operations accumulate rounding error, and floating-point addition is not generally associative: (a + b) + c can differ from a + (b + c).

Note

Floating-point precision issues are one of the main problems currently facing deep learning frameworks and deep learning optimization. The main reason is the non-associativeness of floating-point operations.

For comparisons, use a tolerance chosen for the scale and meaning of the calculation, or compare an exact invariant instead. There is no single epsilon that is correct for every program. NaN is especially unusual: it is not equal to itself, so use isnan in C or is_nan in Rust when testing for it.

The authoritative specification is the IEEE 754-2019 standard. For language-specific behavior, consult the C floating-point clauses in N1570 and the Rust primitive f64 documentation.

Character

Text is encoded too. A character set assigns abstract characters to numbers called code points. An encoding turns code points into bytes. ASCII assigns values to 128 basic characters. Unicode assigns code points to characters from many writing systems, and UTF-8 encodes a Unicode code point using one to four bytes while preserving ASCII as a prefix-compatible subset.

Tip

UTF-8 is currently the most widely used character encoding.

#include <stdio.h>
#include <string.h>

int main(void) {
    const char ascii[] = "A";
    const unsigned char utf8[] = "\xC3\xA9"; /* UTF-8 for U+00E9 */

    printf("ASCII: sizeof = %zu, strlen = %zu\n",
           sizeof ascii, strlen(ascii));
    printf("UTF-8: bytes = %zu, strlen = %zu\n",
           sizeof utf8 - 1, strlen((const char *)utf8));
}

fn main() {
    let ascii = "A";
    let letter = "\u{00E9}"; // U+00E9, encoded as two UTF-8 bytes

    println!("ASCII: bytes = {}, chars = {}", ascii.len(), ascii.chars().count());
    println!("UTF-8: bytes = {}, chars = {}", letter.len(), letter.chars().count());
}

For the standards behind these choices, read the Unicode Core Specification, Chapter 3, RFC 3629: UTF-8, the C17 string library clauses in N1570, and the Rust documentation for str.

Extra

Literals

What is a literal in C？For example:

#include <stdio.h>

int main(){
    int a = 42; // 42 here is a literal
    int b = -15213; // 15213 here is a literal, and '-' is an operator
    printf("Hello, world!\n"); //"Hello, world!\n" here is also a literal
}

If you are not familiar with this concept, the article below could help:

Literals in C - GeeksforGeeks

Noting that literals also have type, 42 is an int for example.

Consider what are the types of the literals below:

0xFFFFFFFF

2147483647

0x80000000

2147483648

Get confused？The following table may help:

Now you should be able to explain why we use:

-2147483647 - 1

to represent INT_MIN，rather than:

0x80000000 or -2147483648

Type Casting

Type castings are very common in C programming language, most of which are implicit.

int main(){
    int i = 42;
    unsigned ui = 37;
    long l = i * ui;
    // equal to: long l = (long)((unsigned) i * ui);
}

If you are not fimiliar with type casting, read this short article:

C- TypeCasting - GeeksforGeeks

Now consider this C program below:

#include <stdio.h>

int main(){
    char ci = 0xE9, cj = 0xD5;
    int i = 0xE9, j = 0xD5;
    int product_c = ci * cj;
    int product = i * j;
    printf("Product of chars is: 0x%x\n", product_c);
    printf("Product of ints is: 0x%x\n", product);
    
}

What is the output of this program? Try to compile and run it and check your answer. If you are wrong, you could ask your AI agents “what is the ‘Integral Promotion’ in C?” to find out why.

The linking below delivers a very detailed explanation about implicit type casting (or conversion in CPP):

Implicit conversions - cppreference.com

Assembly I

The examples use GNU assembler’s AT&T syntax:

# source, destination; % prefixes a register and $ prefixes an immediate
movq $1, %rax
movq (%rdi), %rax

For a complete introduction to the instruction set, use the Intel 64 and IA-32 Software Developer’s Manuals. For the assembler syntax used here, see GNU as’s i386 syntax reference.

PC-Relative

An address can be encoded as an absolute value or as a displacement from the current instruction. x86-64 code commonly uses the second form. It makes the same machine code usable after the code segment is moved, which is the basis of position-independent code.

In x86-64, the program counter is the %rip register. A RIP-relative operand uses the address of the next instruction plus a signed displacement:

movq global(%rip), %rax       # load a nearby symbol
leaq message(%rip), %rdi      # form a nearby address

The assembler and linker fill in the displacement through a relocation entry. The exact relocation type depends on whether the symbol is local, preemptible, or supplied by another object or shared library.

Position-Independent Code (PIC)

Position-independent code can execute correctly when loaded at different virtual addresses. Shared libraries are normally built this way. PIC allowing the loader to combine it with address-space layout randomization (ASLR).

PIC avoids embedding absolute addresses in instructions. Local data can often be reached with RIP-relative addressing; addresses of externally visible objects are commonly loaded through the Global Offset Table (GOT). Function calls may use the Procedure Linkage Table (PLT), discussed below.

The names of the compiler options describe the intended output:

# Shared-library object and shared library
gcc -fPIC -c library.c -o library.o
gcc -shared library.o -o libexample.so

# Position-independent executable
gcc -fPIE -c main.c -o main.o
gcc -pie main.o -o app

-fpic/-fPIC affect compilation, while -pie affects linking. On a toolchain that defaults to PIE, -fno-PIE -no-pie can be used for a deliberately position-dependent executable when that is useful for an experiment.

Further reading:

• GCC’s -fpic, -fPIC, -fpie, and -fPIE documentation
• GCC’s -pie and -no-pie link options
• The Linux Foundation’s AMD64 ELF coding examples

Relative Addressing

A direct jmp or call normally stores a displacement from the end of that instruction to its target. The target does not have to be at a fixed absolute address:

jmp loop
call function

The assembler emits a relocation for a symbol whose final distance is not known yet. The static linker resolves references between input objects; a dynamic linker may apply remaining relocations when a program or shared library is loaded.

Do not confuse a direct relative call with an indirect call through a register or memory operand:

call function       # direct, normally PC-relative
call *%rax          # indirect, target comes from %rax

GNU as documents x86 jumps and calls and RIP-relative memory operands. The ELF specification’s relocation chapter explains why the linker needs these relocation entries.

Memory Addressing

To evaluate a[5], generated code must locate the object a, compute an offset of five elements, and load from the resulting address. The instruction used for the load depends on where the symbol lives:

movq 24(%rsp), %rax                 # a local value in the current stack frame
movq global(%rip), %rax             # a nearby global symbol
movq external@GOTPCREL(%rip), %rax  # address/value reached through the GOT

The first form uses a register-relative displacement. The second uses a link-time PC-relative relocation. The third asks the linker to resolve the address of an external symbol through a GOT entry. These are representative forms; compiler output also depends on symbol visibility, code model, optimization, and whether the value or its address is needed.

Useful tools for seeing the result are:

objdump -drwC -Mintel program.o
readelf -rW program.o
readelf -SW program

Read GNU as’s memory reference documentation, the ELF specification, and the AMD64 ELF ABI index for the complete relocation and object-file rules.

PLT & GOT

The Global Offset Table (GOT) is a table of addresses or pointers that may need to be changed by the dynamic linker. A compiler can reach a GOT entry with a RIP-relative relocation and then load the current value from that entry.

The Procedure Linkage Table (PLT) is a set of small stubs for calling functions whose final addresses are not known when an object is compiled. A typical lazy-binding sequence is:

1. The call enters a PLT entry.
2. The PLT entry jumps through its GOT slot.
3. On the first call, the dynamic linker resolves the symbol and updates that slot.
4. Later calls use the resolved address directly.

For example, call printf@PLT names a PLT relocation rather than the final address of printf. Local, non-preemptible functions can usually be called directly without a PLT entry.

Binding policy is separate from the call sequence. -Wl,-z,lazy permits deferred function binding, while -Wl,-z,now asks the linker/loader to resolve it at load time. GCC’s -fno-plt changes how external calls are generated; it should not be confused with -z now.

Further reading:

• The Linux Foundation’s ELF GOT and PLT specification
• The AMD64 ELF ABI’s GOT/PLT and relocation index
• MaskRay’s detailed article All about Procedure Linkage Table
• GNU ld’s -z lazy and -z now options

Addressing Modes

In AT&T syntax, the general x86 memory operand is:

displacement(base, index, scale)

Its effective address is:

displacement + base + index * scale

The base and index are registers. The scale is one of 1, 2, 4, or 8, which makes common array element sizes cheap to express:

movq (%rax), %rdx                 # *a
movq 40(%rax), %rdx               # a[5] when sizeof(*a) == 8
movq (%rax,%rsi,8), %rdx          # a[i] when i is in %rsi
movq 320(%rcx,%rdi,8), %rdx       # b[5][j] for double b[8][8]

If a row stride is not one of the available scales, the compiler can use leaq or another instruction to form an intermediate address. leaq computes an address-shaped integer and does not access memory.

The GNU assembler manual has the formal x86 memory-reference syntax. Intel’s instruction reference is useful when checking the operand-size and addressing restrictions of a particular instruction.

Extra

Condition Flags

Many integer instructions update bits in RFLAGS. The flags most often used by conditional branches are:

cmp performs a subtraction and discards the result; test performs an AND and discards the result. In AT&T syntax, cmpq %rsi, %rdi computes %rdi - %rsi for flag purposes:

cmpq %rsi, %rdi
je equal             # ZF == 1
jl signed_less       # SF != OF
jb unsigned_less     # CF == 1

Signed and unsigned comparisons use different condition codes. lea does not modify condition flags, and inc/dec preserve CF; do not assume that every arithmetic-looking instruction sets every flag.

For exact flag definitions and every jcc/setcc condition, see Intel’s instruction-set reference.

Name of Registers

You may wonder why registers are named %rax, %rbx, %rsi, %r8, %r9, etc., other than %rax, %rbx…%rmx, %rnx(abc ver.) or %r0, %r1…%r14, %r15(123 ver.).

Well, almost all ISA today use 123 ver. to name their registers (Risc-V for example), and all extensions to x86-64 also use 123 ver. However, x86 has a long history and its ancient ancestor refused to use 123 ver. to name its registers.

That old stuff used a more “meaningful” naming norm, like this:

• EAX - Accumulator Register
• EBX - Base Register
• ECX - Counter Register
• EDX - Data Register
• ESI - Source Index
• EDI - Destination Index
• EBP - Base Pointer
• ESP - Stack Pointer

So abc ver. coincidentally becomes abc ver., huh?

To explore more about their meaning, click this link:

The Art of Picking Intel Registers (swansontec.com)

But today, the meaning of these registers’ name becomes legacy, and the meaningful thing becomes meaningless. We could never predict what would happen in the future, right?

GCC Compiler Flags

These options are most useful when the goal is to inspect compiler-generated assembly. Options can affect compilation, assembling, or linking, so keep the stages separate.

Emit Assembly and Debug Information

# Generate AT&T-syntax assembly without assembling it.
gcc -S -O0 -g -fverbose-asm -fno-omit-frame-pointer \
    -o demo.s demo.c

# Generate an executable with DWARF information for GDB.
gcc -g -O0 -fno-omit-frame-pointer -o demo demo.c

# Select Intel syntax instead of GCC's default AT&T syntax.
gcc -S -masm=intel -o demo.s demo.c

• -S stops after compilation and writes an assembly file.
• -g emits debugging information. With -S, it also makes source-location and related assembler directives visible; keep -g for the final link when GDB should show source lines.
• -fverbose-asm adds human-readable comments to GCC’s assembly output. The comments are for inspection and are not a stable interface.
• -masm=att and -masm=intel select the assembly dialect.

See GCC’s overall options, debugging options, and code-generation options.

Control Optimization

gcc -S -O0 demo.c -o demo.s       # disable most optimization passes
gcc -S -Og demo.c -o demo.s       # debug-friendly optimization
gcc -S -O2 -fno-inline \
    -fno-omit-frame-pointer -fno-optimize-sibling-calls \
    demo.c -o demo.s

-O0 is the clearest starting point, while -Og often produces a more useful debugging experience. Individual -fno-... options are useful when investigating a specific transformation, but they do not make optimized output equivalent to -O0. GCC documents these levels and switches in its optimization options.

Choose PIC/PIE and PLT Behavior

# Compile code for a shared library.
gcc -fPIC -c library.c -o library.o

# Compile and link a position-independent executable.
gcc -fPIE -pie main.c -o app

# Deliberately build a position-dependent executable.
gcc -fno-PIE -no-pie main.c -o app

# Compare external-call sequences.
gcc -S -fplt external.c -o with-plt.s
gcc -S -fno-plt external.c -o through-got.s

• -fPIC/-fpic generate position-independent object code for shared libraries.
• -fPIE/-fpie generate position-independent code intended for an executable; -pie enables the corresponding link mode.
• -fno-pic/-fno-PIE controls compilation, while -no-pie controls the final link. A distribution’s GCC driver may enable PIE by default, so inspect the complete command when comparing output.
• -fplt requests PLT-based external calls (the usual default on targets that support it). -fno-plt loads the function address from the GOT at the call site.

For binding policy, pass linker options through GCC: -Wl,-z,lazy permits lazy function binding and -Wl,-z,now requests eager binding. Read the GCC PIC/PIE options, link options, and GNU ld’s -z options.

GDB

GDB is the GNU Debugger. It can stop a running program, inspect registers, memory, stack frames, and variables, disassemble instructions, and modify state while investigating a bug. Compile with debug information first:

gcc -g -O0 -fno-omit-frame-pointer demo.c -o demo
gdb ./demo

The following commands cover a first assembly-level session:

Inside GDB, $pc and $sp refer to the program counter and stack pointer; on x86-64 they correspond to %rip and %rsp. Use help command to inspect any command’s syntax.

Start with the official sample GDB session, then use the GDB documentation index and the full GDB manual. For a compact command reference, see the GDB Cheat Sheet from the University of Pittsburgh.

Assembly II

The assembly examples use GNU assembler’s AT&T syntax: source comes before destination, registers have a % prefix, and immediate values have a $ prefix. A few examples use names such as %1 and %2 for virtual registers; these are compiler intermediate-representation notation, not registers that can be written directly in x86-64 assembly.

For the x86-64 System V calling convention, see the AMD64 System V ABI. For instruction semantics, use Intel’s 64 and IA-32 Software Developer’s Manuals or AMD’s AMD64 Architecture Programmer’s Manual, Volume 3.

Registers

Caller-Saved and Callee-Saved

A function-call ABI specifies which register values must survive a call. From the caller’s point of view:

• A caller-saved register may be overwritten by the function being called. If the caller still needs its value afterward, the caller must save it or arrange for the compiler to keep it elsewhere.
• A callee-saved register must have its original value when the called function returns. A function that uses one must save and restore it, often in its stack frame.

Under the x86-64 System V ABI, the general-purpose caller-saved registers are %rax, %rcx, %rdx, %rsi, %rdi, and %r8–%r11. The callee-saved registers are %rbx, %rbp, and %r12–%r15; %rsp must also be restored to its required value before returning. Other ABIs can make different choices, so check the ABI for the target system.

Caller-saved registers are convenient for short-lived values and for passing function arguments. Their values do not survive a call unless the caller saves them. Callee-saved registers are useful when a value needs to remain available across calls: the callee pays the cost of preserving a register it uses, rather than every caller saving a live value around every call.

For example, both the loop index and its bound may be needed after each call:

for (int i = 0; i < size; ++i) {
    func(i);
}

If the compiler keeps i and size in registers across func, it must ensure they survive the call. It might choose callee-saved registers, or save and restore caller-saved registers. The best choice depends on the function and surrounding code.

In this ABI, the first six integer or pointer arguments are passed in %rdi, %rsi, %rdx, %rcx, %r8, and %r9. %r10 and %r11 are caller-saved, but are not argument registers for ordinary function calls.

Static Link Pointer: %r10

Some languages allow a function to be defined inside another function. The inner function can then refer to variables in the enclosing function. A static link (also called a static chain) points to the enclosing function’s stack frame, where those variables live.

The x86-64 System V ABI assigns %r10 for passing this pointer when a nested-function implementation needs one. GCC supports nested functions as a C extension; nested functions are not part of standard C. Closures in languages such as C++, Python, and Rust also carry an environment, though their representation and calling convention need not use a static chain or %r10.

int func_p(int arg1, int arg2) {
    int a_p = arg1 + arg2;

    int func_c(int arg1, int arg2) {
        int a_c = arg1 - arg2;
        return a_p + a_c;  // reads a_p from the enclosing frame
    }

    return func_c(arg1, arg2);
}

When func_c runs, its static chain lets it find a_p in func_p’s frame. See GCC’s documentation on nested functions and the AMD64 System V ABI.

RFLAGS

RFLAGS holds processor status and control bits. Arithmetic and comparison instructions set status flags such as ZF (zero), CF (carry), SF (sign), and OF (signed overflow); conditional branches read them. For example, cmp sets flags as though it subtracted its source operand from its destination operand, without keeping the result:

cmpq %rsi, %rdi       # flags for %rdi - %rsi
je equal              # branch if ZF is set
jl signed_less        # signed comparison
jb unsigned_less      # unsigned comparison

RFLAGS also matters when control crosses from a user program into the operating-system kernel. A normal function call follows the function ABI; a system call follows the processor’s system-call mechanism and the operating system’s syscall ABI.

System Calls: syscall and sysret

A process runs with restricted privileges and cannot directly perform operations such as reading a file or creating a process. It requests these services from the operating-system kernel through system calls.

On x86-64, the syscall instruction transfers control to an operating-system entry point. The processor saves the next instruction address in %rcx and the old RFLAGS value in %r11; the kernel saves any state it needs before using those registers. The kernel eventually returns to user mode, commonly with sysret, which uses the saved return state. Thus %rcx and %r11 are clobbered by the syscall instruction.

The Linux x86-64 syscall convention is different from the ordinary function-call convention. The syscall number is in %rax; up to six arguments are in %rdi, %rsi, %rdx, %r10, %r8, and %r9; the result is returned in %rax. In particular, the fourth syscall argument uses %r10, even though %r10 is not an argument register for an ordinary function call.

For the processor behavior, see AMD’s AMD64 Architecture Programmer’s Manual, Volume 3 or Intel’s instruction-set manuals. The AMD64 System V ABI describes the Linux kernel calling convention.

Physical and Virtual Registers

Physical registers are the finite registers provided by the processor, such as %rax or %r12. Their use is constrained by the instruction set and the ABI.

Compilers often first translate a program into an intermediate form with virtual registers such as %1, %2, and %3. These names represent values, not fixed hardware locations. A compiler can create as many as its intermediate code needs, then assign virtual registers to physical registers or to stack slots. Liveness and register allocation are discussed below.

Control Flow

Control flow describes the order in which instructions execute:

• Sequential execution moves to the next instruction.
• A jump transfers control to another instruction in the current function.
• A call transfers control to a function and records where execution should continue after the function returns.

Basic Blocks and Control-Flow Graphs

A basic block is a straight-line sequence of instructions with one entry point: execution starts at its first instruction and does not jump into its middle. A control-flow graph (CFG) represents each block as a node and each possible transfer between blocks as an edge. Conditional branches give a block multiple outgoing edges; loops create cycles in the graph.

For example, this loop can be divided into an entry block, a test block, a body block, and an exit block:

entry:
    i = 0
    sum = 0
    jump test

test:
    if i >= n, jump exit

body:
    sum = sum + i
    i = i + 1
    jump test

exit:
    return sum

The CFG has edges entry → test, test → body, test → exit, and body → test. Thinking in blocks makes it easier to see loops, branches, and which values can reach each part of the program. In a per-function CFG, calls are usually represented as instructions with a continuation; interprocedural graphs add edges into and out of called functions.

GCC’s internals manual describes basic blocks and the structures used to represent them.

Call Graph and Interprocedural CFG

A call graph (CG) has one node for each function and an edge from a caller to each function it may call. For example:

main ──→ fun1 ──→ fun2
  ├──────────────→ fun2
  └──────────────→ fun_rec ──→ fun_rec

The self-edge represents recursion. A call graph records which functions call one another, but it does not show the individual basic blocks inside each function.

An interprocedural control-flow graph (ICFG) includes basic blocks from multiple functions. It adds an edge from a call site to the callee’s entry and a return edge from the callee back to the continuation after that call. An ICFG therefore exposes how control can move across function boundaries.

Data Flow

Data-flow analysis follows values through instructions and control-flow edges. It helps a compiler decide where values are needed, which registers can share hardware, and which computations have no effect on the result.

Lifetime and Liveness

A value is live at a point if some possible future path reads that value before replacing it. Its live range is the part of the program where it remains live. Two values whose live ranges never overlap can often use the same physical register. The compiler builds this information across CFG edges, so branches and loops affect liveness.

Consider these illustrative instructions using virtual registers:

1  mov 8(%rsp), %1
2  mov 16(%rsp), %2
3  add %1, %2
4  mov 24(%rsp), %3
5  mov 32(%rsp), %4
6  mul %4, %3
7  call fun
8  sub %3, %2
9  mov %2, %rax
10 ret

After instruction 3, %1 is no longer needed. %4 is no longer needed after instruction 6, so %1 and %4 have non-overlapping live ranges and may share a physical register. %2 and %3 are both needed after the call, so they are live across it. The compiler can place them in callee-saved registers or save and reload them around the call if it uses caller-saved registers.

This is why register allocation is connected to both control flow and the calling convention: it must account for overlapping live ranges, branches, and calls that overwrite caller-saved registers. GCC documents liveness information used by its compiler passes.

Branches

At a conditional branch, only one successor executes at a time. Values used on different paths may therefore have non-overlapping live ranges and can sometimes share a physical register. At a point where paths join, the compiler must account for every value that may be needed along any incoming path.

cmp $0, %3
je ELSE
mov %4, %1
add $1, %1
mov %1, %rax
ret
ELSE:
mov %5, %2
add $1, %2
mov %2, %rax
ret

%1 and %2 are used on separate paths. Their live ranges do not overlap, so if they use compatible registers, the compiler can assign them the same physical register.

A value may also be created before a branch and remain live after the paths join:

mov 8(%rsp), %1       # value needed after the branch
cmp $0, %2
je ELSE
mov $1, %3
jmp JOIN
ELSE:
mov $2, %3
JOIN:
add %3, %1
mov %1, %rax
ret

%1 is defined before the branch and used after JOIN, so it must keep its value along both paths. %3 is also needed at JOIN; there the two values are live at the same time and cannot share a physical register.

Dead-Code Elimination

A computation is dead if its result is never used and it has no observable side effect. A compiler can remove dead computations. Branches also provide information: if every path produces the same result, the condition and the branch may be unnecessary.

mov 8(%rsp), %1
mov 16(%rsp), %2
add %1, %2            # result is never used
mov %1, %rax
ret

The result in %2 is never read, so the addition is dead. After removing it, the load into %2 is dead as well. A computation that writes through a pointer, performs I/O, calls a function with side effects, or accesses a volatile object cannot be removed merely because its numeric result is unused.

Conditional branches can also provide facts that make an inner branch unreachable:

cmp $0, %1
je ZERO

NONZERO:
cmp $0, %1
je DEAD               # impossible on this path
mov $1, %rax
jmp DONE
DEAD:
mov $2, %rax
jmp DONE

ZERO:
mov $0, %rax
DONE:
ret

If execution falls through the first je ZERO, %1 must be nonzero. Since %1 does not change before the second comparison, je DEAD can never be taken. Conditional data-flow analysis can fold that branch away, after which the unreachable DEAD block can be removed:

cmp $0, %1
je ZERO
mov $1, %rax
jmp DONE
ZERO:
mov $0, %rax
DONE:
ret

Extra

Liveness and Register Allocation

One way to picture register allocation is as a graph-coloring problem. Each virtual register is a node. Two nodes are connected when their values are live at the same time, meaning they cannot use the same physical register. Assigning physical registers is like assigning colors so connected nodes receive different colors. If there are not enough suitable registers, the compiler can move some values to memory (called spilling) and load them again when needed.

This is a simplified picture: real register allocators must also consider register classes, instruction constraints, calling conventions, and optimization costs. GCC’s documentation on RTL optimization passes describes its implementation stages.

Tutorials

xLab Quick Start

This document is intended for students of Peking University only, so it will be in Chinese.

安装SSH

Windows

Windows 10（版本 1809 及之后）和 Windows 11 通常已经自带 OpenSSH 客户端。打开“设置”→“应用”→“可选功能”，在列表中确认已安装“OpenSSH 客户端”；如果没有，点击“查看功能”，搜索并安装它。也可以使用管理员身份打开 PowerShell，执行：

Add-WindowsCapability -Online -Name OpenSSH.Client~~~~0.0.1.0

安装完成后打开 PowerShell 或“Windows Terminal”，检查 SSH 是否可用：

ssh -V

macOS

macOS 已经自带 OpenSSH。打开“终端”（可在“应用”→“实用工具”中找到），检查 SSH 是否可用：

ssh -V

生成 SSH 密钥对

在 PowerShell、Windows Terminal 或 macOS 的“终端”中执行以下命令。命令中的邮箱仅用于标识密钥，可以替换为自己的邮箱：

ssh-keygen -t ed25519 -C "your_email@example.com"

看到 Enter file in which to save the key 时直接按回车，使用默认保存位置；看到 Enter passphrase 时可以设置一个密钥密码，也可以直接按回车留空。命令会生成一对密钥：

• 私钥：Windows 通常位于 C:\Users\你的用户名\.ssh\id_ed25519，macOS 位于 ~/.ssh/id_ed25519。私钥只能自己保存，不能上传或发送给他人。
• 公钥：与私钥同名并以 .pub 结尾，即 id_ed25519.pub。接下来需要将公钥的完整内容添加到 xLab。

查看并复制公钥内容：

Windows（PowerShell）：

Get-Content $HOME\.ssh\id_ed25519.pub

macOS：

cat ~/.ssh/id_ed25519.pub

复制输出的整行文本（以 ssh-ed25519 开头），不要复制私钥。然后继续下面“配置 xLab”中的“添加公钥”步骤。

在xLab上添加公钥

首先，访问xLab主页，完成登录，进入“我的节点”界面。然后点击右上角的账户按钮（显示文本为你的名字 s你的学号），会弹出一个表单。

在弹出的表单中，把你刚刚复制的公钥内容粘贴到“公钥”表单中，然后给你的公钥起一个你喜欢的名字。都填完后，点击添加公钥，退出表单进入到下一步。

在xLab上新建节点

回到“我的节点”界面，点击右上角的“新建节点”按钮。理论上你什么都不需要配置，直接点击新建节点即可。

节点创建可能需要一些时间，静待一到两分钟，刷新界面，如果你的节点显示“运行中”，说明创建已经成功。

连接xLab

通过网页终端

点击“通过网页终端”即可。

如果你需要完成大量的代码编写任务，不推荐通过这种形式连接，除非你是vim/nano/emacs/其他非图形化代码编辑器领域大神。（其实北大里还真有这样一位大神，他甚至非常年轻，他就是Prof. Mechtaev。）

通过本地终端

复制右侧的ssh -p ...指令，打开你的终端，粘贴，按回车即可。

比起网页终端，你或许可以整出更多的活，但是依旧不如直接用vscode。

通过vscode

首先，打开你的vscode，下载拓展Remote-SSH，在下载完成后关掉你的vscode。

然后回到“我的节点”界面，点击“打开VS Code”按钮，找到弹出的每个窗口的确认键，点击它们。然后你的vscode会自动启动，可能会弹出一个选项卡让你选择连接目标的平台，选择Linux即可。然后等待vscode远程服务器部署好，即可完成连接。

你也可以尝试不依赖xLab为你提供的一键式连接，实际上这并不困难，问问你的AI agents吧。

More Resources

xLab Official(?) Slides

xLab Official Documents

Advanced Topic Recommendations

The course has reached Chapter 3 for now. The topics below go one step beyond the first pass through CSAPP. This list is intentionally short for now and will grow as the course moves forward.

RISC-V

Estimated Difficulty: ⭐⭐

RISC-V is an open instruction-set architecture (ISA), not a particular processor. Its small base instruction set can be combined with extensions for features such as multiplication, atomics, compressed instructions, and vectors. After learning x86-64 assembly, comparing the two ISAs is a useful way to separate ideas that belong to all machines from choices made by one architecture. An especially useful next step is to read the RISC-V calling convention and inspect how a compiler maps function arguments, return values, and stack frames to registers.

For further reading:

• RISC-V ISA Manuals — Ratified Specifications Library
• The RISC-V Unprivileged Architecture
• RISC-V Procedure Calling Convention

LLVM IR

Estimated Difficulty: ⭐⭐⭐

LLVM IR is a typed, low-level intermediate representation between a source language and target-specific machine code. It uses static single assignment (SSA) form for register-like values, so data dependencies and control-flow joins are visible before the compiler chooses physical registers. This makes LLVM IR a good place to observe what an optimizer changes while keeping the machine details that matter for code generation. Try comparing the IR produced by clang -S -emit-llvm at different optimization levels, then relate its load, store, and phi instructions to the assembly you already know.

For further reading:

• LLVM Language Reference Manual
• My First Language Frontend with LLVM
• The LLVM Target-Independent Code Generator

Register Assignment

Estimated Difficulty: ⭐⭐⭐⭐⭐

Register assignment, usually called register allocation, maps the many temporary values used by a compiler to the small set of physical registers provided by a processor. The compiler tracks when each value is live and tries to keep values whose live ranges overlap in different registers. When the registers are not enough, it spills a value to the stack; calling conventions and instruction constraints add further restrictions. These decisions explain many of the moves, stack accesses, and reused registers that appear in optimized assembly.

For further reading:

• The LLVM Target-Independent Code Generator
• Register Allocation via Coloring
• Register Allocation & Spilling via Graph Coloring