RISC-V Assembly Code Generation¶

Overview¶

This lecture covers how the NTLang compiler transforms parsed expressions into executable RISC-V assembly code. We examine stack-based code generation, where a recursive traversal of the AST emits assembly instructions that use the stack to store intermediate values. The same tree-walking structure used for evaluation is reused for compilation — but instead of computing values, the compiler emits assembly text. This is the foundation for Project02's -c (compile) mode.

Learning Objectives¶

Understand the stack machine model for code generation
Implement recursive AST traversal that emits RISC-V assembly
Explain the preamble structure and its role in the compiled program
Compare evaluation (interpret) vs compilation (code generation) approaches
Trace generated assembly for a given expression

Prerequisites¶

RISC-V Assembly 1 & 2 (Lectures 05–06): registers, instructions, memory operations, control flow, functions, calling convention
RISC-V Assembly Strings and Bits (Lecture 07): byte operations, bitwise instructions
NTLang parsing and AST representation (Lectures 02–03)
Expression evaluation with recursive tree traversal (Lecture 04)

1. The Compilation Pipeline¶

Expression Mode vs Compile Mode¶

NTLang operates in two modes:

Expression mode (-e): Evaluates an expression and prints the result.

$ ntlang -e "(3 + 4) * 7"
49

Compile mode (-c): Generates RISC-V assembly instead of evaluating.

$ ntlang -c "(a0 + a1) * a2" > my_expr.s

Full Pipeline¶

In compile mode, the expression goes through the same front-end (scanner → parser → AST), but the back-end generates assembly instead of evaluating:

graph LR
    A[Expression] --> B[Scanner]
    B --> C[Tokens]
    C --> D[Parser]
    D --> E[AST]
    E --> F[Code Generator]
    F --> G[".s file"]
    G --> H[Assembler]
    H --> I[Executable]

The generated .s file is combined with a preamble (codegen_main.s) that handles argument parsing, calling the generated function, and printing the result.

Two-Part Output¶

The compiled program consists of two assembly files:

codegen_main.s — The preamble: parses command-line arguments, calls the generated expression function, and prints the result. This file is provided and does not change.
Generated .s file — Contains a function that evaluates the expression using the stack. This is what your compiler produces.

codegen_main.s  +  generated_expr.s  →  assembler  →  executable
(provided)         (your compiler)

Build Process¶

$ ntlang -c "(a0 + a1) * a2" > expr.s
$ riscv64-linux-gnu-gcc -o expr codegen_main.s expr.s -static
$ qemu-riscv64 ./expr 3 4 7
49

The arguments 3 4 7 are passed to registers a0, a1, a2 by the preamble before calling the generated function.

2. Stack Machine Code Generation¶

What is a Stack Machine?¶

A stack machine uses the program stack to store all intermediate values during computation. Instead of keeping track of which register holds which value, we simply:

Push values onto the stack
Pop operands, apply an operation, push the result back

This approach is simple to implement and naturally maps to recursive tree traversal.

Stack Evolution Example¶

Consider (3 + 4) * 7:

Step 1: Push 3          Stack: [3]
Step 2: Push 4          Stack: [3, 4]
Step 3: Pop 4, Pop 3    Stack: []
        Compute 3 + 4 = 7
        Push 7          Stack: [7]
Step 4: Push 7          Stack: [7, 7]
Step 5: Pop 7, Pop 7    Stack: []
        Compute 7 * 7 = 49
        Push 49         Stack: [49]

The final value on the stack (49) is the result.

Assembly Patterns¶

Each operation in the code generator follows a fixed pattern of assembly instructions. The stack grows downward (toward lower addresses), and we use sp (the stack pointer) to track the top.

Push Constant (Integer Literal)¶

Push an integer value onto the stack:

# Push constant <val>
addi sp, sp, -4       # make room on stack
li t0, <val>          # load immediate value
sw t0, (sp)           # store to top of stack

Push Register (Variable Reference — `a0`–`a7`)¶

Push the value of an argument register onto the stack:

# Push register aX
addi sp, sp, -4       # make room on stack
sw aX, (sp)           # store register to top of stack

Since NTLang expressions can reference a0–a7 as variables, the code generator emits a push of the corresponding register.

Unary Operator¶

Pop the operand, apply the operation, push the result:

# Unary operation (e.g., negation)
lw t0, (sp)           # load operand from top of stack
<unary_op> t0, t0     # apply operation (e.g., neg t0, t0)
sw t0, (sp)           # store result back to top of stack

Note: the stack pointer doesn't change — we replace the top value in place.

Binary Operator¶

Pop two operands, apply the operation, push the result:

# Binary operation (e.g., add)
lw t1, (sp)           # load right operand
addi sp, sp, 4        # pop right operand
lw t0, (sp)           # load left operand (now at top)
<binary_op> t0, t0, t1  # apply operation (e.g., add t0, t0, t1)
sw t0, (sp)           # store result (replaces left operand)

Two values are popped but only one is pushed back, so the stack shrinks by one slot.

3. Code Generation Implementation¶

Structure Overview¶

The code generator mirrors the evaluator's recursive structure. Where eval_expression returns a u32 value, the code generator builds a String of assembly instructions:

Evaluator	Code Generator
Returns computed value (`u32`)	Returns assembly text (`String`)
`eval_expression(node, env)`	`compile_tree_expr(node)`
Applies operation to values	Emits instructions for operation
Recursion computes sub-results	Recursion emits code for sub-expressions

The `compile_tree_expr` Function¶

The core code generation function uses match on the ParseNode enum, just like the evaluator:

fn compile_tree_expr(node: &ParseNode) -> String {
    let mut code = String::new();

    match node {
        ParseNode::IntLit(val) => {
            // Push constant onto stack
            code.push_str(&format!("    addi sp, sp, -4\n"));
            code.push_str(&format!("    li t0, {}\n", val));
            code.push_str(&format!("    sw t0, (sp)\n"));
        }

        // Handle other node types...
        // ParseNode::Ident(name) => { ... }
        // ParseNode::UnaryOp { op, operand } => { ... }
        // ParseNode::BinaryOp { op, left, right } => { ... }

        _ => panic!("Unexpected node type in code generation"),
    }

    code
}

Binary Operation Pattern¶

For binary operations, the code generator recursively emits code for both children, then emits the operation:

ParseNode::BinaryOp { op, left, right } => {
    // Emit code for left operand (pushes result onto stack)
    code.push_str(&compile_tree_expr(left));
    // Emit code for right operand (pushes result onto stack)
    code.push_str(&compile_tree_expr(right));

    // Pop right operand, load left operand, apply op, store result
    code.push_str("    lw t1, (sp)\n");       // right operand
    code.push_str("    addi sp, sp, 4\n");    // pop
    code.push_str("    lw t0, (sp)\n");       // left operand

    // Emit the specific instruction based on operator
    match op {
        BinaryOp::Add => code.push_str("    add t0, t0, t1\n"),
        // ... other operators
        _ => panic!("Unknown binary operator"),
    }

    code.push_str("    sw t0, (sp)\n");       // store result
}

The key insight: by the time we reach the binary operation code, both children have already emitted their push instructions. The left operand's result is below the right operand's result on the stack.

The `compile_tree` Entry Point¶

The entry point wraps the expression code in a function:

fn compile_tree(node: &ParseNode) -> String {
    let mut code = String::new();

    // Function label
    code.push_str(".global ntlang_expr\n");
    code.push_str(".text\n");
    code.push_str("ntlang_expr:\n");

    // Generate expression code
    code.push_str(&compile_tree_expr(node));

    // Pop result into a0 and return
    code.push_str("    lw a0, (sp)\n");
    code.push_str("    addi sp, sp, 4\n");
    code.push_str("    ret\n");

    code
}

The generated function:

Starts with the label ntlang_expr (called by the preamble)
Executes the expression code (which pushes the final result onto the stack)
Pops the result into a0 (the return value register)
Returns to the caller (the preamble)

4. The Preamble: `codegen_main.s`¶

Purpose¶

The preamble is a provided assembly file that:

Parses command-line arguments (converting strings to integers)
Places argument values into registers a0–a7
Calls the generated ntlang_expr function
Prints the return value (from a0)
Exits the program

What the Preamble Does (Rust Equivalent)¶

The preamble's behavior is equivalent to this Rust code:

fn main() {
    let args: Vec<String> = std::env::args().collect();

    // Parse command-line args into a0-a7
    let mut regs = [0i32; 8];
    for i in 1..args.len().min(9) {
        regs[i - 1] = args[i].parse().unwrap();
    }

    // Call the generated expression function
    let result = ntlang_expr(regs[0], regs[1], regs[2], regs[3],
                              regs[4], regs[5], regs[6], regs[7]);

    // Print the result
    println!("{}", result);
}

Preamble Assembly Structure¶

The preamble performs these steps in assembly:

1. Save callee-saved registers (ra, s0-s3)
2. Store argc and argv
3. Loop through argv[1..argc]:
   a. Call atoi() to convert string to integer
   b. Store result in appropriate aX register slot on stack
4. Load a0-a7 from stored values
5. Call ntlang_expr
6. Print result using printf
7. Restore callee-saved registers
8. Exit

The preamble handles the "plumbing" so that your generated code only needs to focus on the expression computation.

Stack Layout During Execution¶

High addresses
┌─────────────────┐
│  Preamble frame  │  (saved registers, args)
├─────────────────┤
│  a0-a7 values   │  (parsed from command line)
├─────────────────┤  ← sp when ntlang_expr is called
│                 │
│  Stack space    │  (used by generated code for
│  for expression │   intermediate values)
│                 │
├─────────────────┤  ← sp grows downward during execution
│                 │
Low addresses

5. Complete Example¶

Expression: `(a0 + a1) * a2`¶

Parse tree:

Traversal order (depth-first, left-to-right): a0, a1, +, a2, *

Generated Assembly¶

.global ntlang_expr
.text
ntlang_expr:
    # Push a0
    addi sp, sp, -4
    sw a0, (sp)

    # Push a1
    addi sp, sp, -4
    sw a1, (sp)

    # Binary add: pop right (a1), load left (a0), add, store
    lw t1, (sp)
    addi sp, sp, 4
    lw t0, (sp)
    add t0, t0, t1
    sw t0, (sp)

    # Push a2
    addi sp, sp, -4
    sw a2, (sp)

    # Binary mul: pop right (a2), load left (a0+a1), mul, store
    lw t1, (sp)
    addi sp, sp, 4
    lw t0, (sp)
    mul t0, t0, t1
    sw t0, (sp)

    # Pop result into a0 and return
    lw a0, (sp)
    addi sp, sp, 4
    ret

Stack Trace¶

Running with arguments 3 4 7 (a0=3, a1=4, a2=7):

Step	Action	Stack (top → bottom)
1	Push a0 (3)	[3]
2	Push a1 (4)	[4, 3]
3	Pop 4, load 3, add → 7	[7]
4	Push a2 (7)	[7, 7]
5	Pop 7, load 7, mul → 49	[49]
6	Pop result into a0	[]

Return value: 49

6. Comparing Eval and Compile¶

Side-by-Side Structure¶

The evaluator and code generator have the same recursive structure — they differ only in what they produce:

Evaluator — returns a computed value:

fn eval_expression(node: &ParseNode, env: &mut Environment) -> u32 {
    match node {
        ParseNode::IntLit(val) => *val,

        ParseNode::BinaryOp { op, left, right } => {
            let left_val = eval_expression(left, env);
            let right_val = eval_expression(right, env);
            match op {
                BinaryOp::Add => left_val.wrapping_add(right_val),
                // ...
            }
        }
        // ...
    }
}

Code Generator — returns assembly text:

fn compile_tree_expr(node: &ParseNode) -> String {
    let mut code = String::new();
    match node {
        ParseNode::IntLit(val) => {
            code.push_str(&format!("    addi sp, sp, -4\n"));
            code.push_str(&format!("    li t0, {}\n", val));
            code.push_str(&format!("    sw t0, (sp)\n"));
        }

        ParseNode::BinaryOp { op, left, right } => {
            code.push_str(&compile_tree_expr(left));
            code.push_str(&compile_tree_expr(right));
            // ... emit pop, operation, store instructions
        }
        // ...
    }
    code
}

Key Differences¶

Aspect	Eval	Compile
Output	`u32` value	`String` of assembly
Variables	Looked up in environment	Push register value
Operations	Computed directly in Rust	Emit assembly instructions
Intermediate results	Held in Rust variables	Pushed to program stack
When computation happens	At eval time	At run time (of generated code)
Environment needed?	Yes (`HashMap`)	No (registers are the "environment")

No Environment Needed¶

In compile mode, variable references like a0–a7 are not looked up in a hash map. Instead, the code generator emits a push of the corresponding register. The "environment" is the set of argument registers, populated by the preamble from command-line arguments.

7. Operator Reference¶

Binary Operators¶

NTLang Operator	RISC-V Instruction	Description
`+`	`addw t0, t0, t1`	Addition (32-bit)
`-`	`subw t0, t0, t1`	Subtraction (32-bit)
`*`	`mul t0, t0, t1`	Multiplication
`/`	`div t0, t0, t1`	Signed division
`&`	`and t0, t0, t1`	Bitwise AND
`\\|`	`or t0, t0, t1`	Bitwise OR
`^`	`xor t0, t0, t1`	Bitwise XOR
`<<`	`sllw t0, t0, t1`	Shift left logical (32-bit)
`>>`	`srlw t0, t0, t1`	Shift right logical (32-bit)
`>-`	`sraw t0, t0, t1`	Shift right arithmetic (32-bit)

Unary Operators¶

NTLang Operator	RISC-V Instruction	Description
`-` (negation)	`neg t0, t0`	Two's complement negation
`~` (bitwise NOT)	`not t0, t0`	Bitwise complement

Note on 32-bit Operations¶

NTLang uses 32-bit values. On RV64, use the w-suffix variants (addw, subw, sllw, srlw, sraw) to get proper 32-bit behavior with sign extension. For mul and div, the standard instructions work with 32-bit values stored in registers.

8. Practice Problems¶

Problem 1: Trace Code Generation¶

Given the expression (5 + 3) * 2, draw the parse tree and write the generated assembly code.

Click to reveal solution

**Parse tree**:

**Generated assembly**:

.global ntlang_expr
.text
ntlang_expr:
    # Push 5
    addi sp, sp, -4
    li t0, 5
    sw t0, (sp)

    # Push 3
    addi sp, sp, -4
    li t0, 3
    sw t0, (sp)

    # Add: pop 3, load 5, add -> 8
    lw t1, (sp)
    addi sp, sp, 4
    lw t0, (sp)
    addw t0, t0, t1
    sw t0, (sp)

    # Push 2
    addi sp, sp, -4
    li t0, 2
    sw t0, (sp)

    # Mul: pop 2, load 8, mul -> 16
    lw t1, (sp)
    addi sp, sp, 4
    lw t0, (sp)
    mul t0, t0, t1
    sw t0, (sp)

    # Pop result and return
    lw a0, (sp)
    addi sp, sp, 4
    ret

**Stack trace**: Push 5 → Push 3 → Add (8) → Push 2 → Mul (16) → Result: **16**

Problem 2: Unary Operator¶

Write the generated assembly for the expression -a0.

Click to reveal solution

.global ntlang_expr
.text
ntlang_expr:
    # Push a0
    addi sp, sp, -4
    sw a0, (sp)

    # Unary negation: load, negate, store
    lw t0, (sp)
    neg t0, t0
    sw t0, (sp)

    # Pop result and return
    lw a0, (sp)
    addi sp, sp, 4
    ret

The unary operator pattern: load the top of stack, apply the operation, store back. The stack pointer doesn't change because we're replacing the value in place.

Problem 3: Bitwise Operations¶

Write the generated assembly for a0 & 0xFF.

Click to reveal solution

.global ntlang_expr
.text
ntlang_expr:
    # Push a0
    addi sp, sp, -4
    sw a0, (sp)

    # Push 255 (0xFF)
    addi sp, sp, -4
    li t0, 255
    sw t0, (sp)

    # AND: pop 255, load a0, and
    lw t1, (sp)
    addi sp, sp, 4
    lw t0, (sp)
    and t0, t0, t1
    sw t0, (sp)

    # Pop result and return
    lw a0, (sp)
    addi sp, sp, 4
    ret

This expression masks `a0` to its low byte. Running with `a0 = 0x12345678` would return `0x78` (120 in decimal).

Problem 4: Stack Depth Analysis¶

For the expression (a0 + a1) * (a2 + a3), what is the maximum number of values on the stack at any point during execution?

Click to reveal solution

Parse tree:
            *
           / \
          +   +
         / \ / \
        a0 a1 a2 a3

Traversal (depth-first, left-to-right):

Step 1: Push a0          Stack depth: 1  [a0]
Step 2: Push a1          Stack depth: 2  [a1, a0]
Step 3: Add a0+a1        Stack depth: 1  [a0+a1]
Step 4: Push a2          Stack depth: 2  [a2, a0+a1]
Step 5: Push a3          Stack depth: 3  [a3, a2, a0+a1]  ← MAXIMUM
Step 6: Add a2+a3        Stack depth: 2  [a2+a3, a0+a1]
Step 7: Mul              Stack depth: 1  [result]

Maximum stack depth: 3 values = 12 bytes

In general, the maximum stack depth depends on the tree structure.
A balanced binary tree of depth d has maximum stack depth d+1.

Problem 5: Extending the Compiler¶

The NTLang operator >- performs arithmetic shift right. What RISC-V instruction should the code generator emit for this operator? Write the match arm.

Click to reveal solution

BinaryOp::Asr => code.push_str("    sraw t0, t0, t1\n"),

The `sraw` instruction performs a 32-bit arithmetic right shift, which preserves the sign bit. This matches the NTLang `>-` operator semantics. Example: `-8 >- 2` should produce `-2`:

-8 in 32-bit: 0xFFFFFFF8
sraw by 2:    0xFFFFFFFE = -2

The sign bit (1 for negative numbers) is replicated into the vacated high bits.

Summary¶

Code generation transforms a parsed AST into RISC-V assembly text. The NTLang compiler's -c mode generates a .s file instead of evaluating the expression.
Stack machine approach: all intermediate values are pushed onto and popped from the program stack. Push constants with li/sw, push registers with sw, apply operations by popping operands and pushing results.
Recursive tree traversal drives code generation. The compile_tree_expr function uses match on ParseNode variants — the same structure as eval_expression, but emitting assembly text instead of computing values.
The preamble (codegen_main.s) handles argument parsing, register setup, calling the generated function, and printing the result. Your compiler only generates the expression function.
Assembly patterns are fixed for each node type: integer literals push a constant, identifiers push a register, unary operators modify the top of stack, and binary operators pop two values and push one result.
Eval vs compile share the same recursive structure — the difference is output type (u32 vs String) and where computation happens (immediately in Rust vs later in the generated assembly).

RISC-V Assembly Code Generation¶

Overview¶

Learning Objectives¶

Prerequisites¶

1. The Compilation Pipeline¶

Expression Mode vs Compile Mode¶

Full Pipeline¶

Two-Part Output¶

Build Process¶

2. Stack Machine Code Generation¶

What is a Stack Machine?¶

Stack Evolution Example¶

Assembly Patterns¶

Push Constant (Integer Literal)¶

Push Register (Variable Reference — a0–a7)¶

Unary Operator¶

Binary Operator¶

3. Code Generation Implementation¶

Structure Overview¶

The compile_tree_expr Function¶

Binary Operation Pattern¶

The compile_tree Entry Point¶

4. The Preamble: codegen_main.s¶

Purpose¶

What the Preamble Does (Rust Equivalent)¶

Preamble Assembly Structure¶

Stack Layout During Execution¶

5. Complete Example¶

Expression: (a0 + a1) * a2¶

Generated Assembly¶

Stack Trace¶

6. Comparing Eval and Compile¶

Side-by-Side Structure¶

Key Differences¶

No Environment Needed¶

7. Operator Reference¶

Binary Operators¶

Unary Operators¶

Note on 32-bit Operations¶

8. Practice Problems¶

Problem 1: Trace Code Generation¶

Problem 2: Unary Operator¶

Problem 3: Bitwise Operations¶

Problem 4: Stack Depth Analysis¶

Problem 5: Extending the Compiler¶

Further Reading¶

Summary¶

Push Register (Variable Reference — `a0`–`a7`)¶

The `compile_tree_expr` Function¶

The `compile_tree` Entry Point¶

4. The Preamble: `codegen_main.s`¶

Expression: `(a0 + a1) * a2`¶