RISC-V Assembly Code Generation

# RISC-V Assembly Code Generation

## CS 631 Systems Foundations — Mar 12, 2026

---

## Today's Agenda

1. The compilation pipeline
2. Stack machine code generation
3. Assembly patterns for each node type
4. Code generation implementation (Rust)
5. The preamble: `codegen_main.s`
6. Complete example walkthrough
7. Comparing eval and compile

---

## From Eval to Compile

Recall NTLang's **expression mode**:

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

Now we add **compile mode**:

```text
$ ntlang -c "(a0 + a1) * a2" > expr.s
```

Instead of computing the result, we generate RISC-V assembly that computes it.

---

## Compilation Pipeline

<div class="mermaid">
graph LR
    A["Expression"] --> B["Scanner"]
    B --> C["Tokens"]
    C --> D["Parser"]
    D --> E["AST"]
    E --> F["Code Gen"]
    F --> G[".s file"]
    G --> H["Assembler"]
    H --> I["Executable"]
</div>

Same front-end (scanner → parser → AST), different back-end.

---

## Two-Part Output

The compiled program has two assembly files:

1. **`codegen_main.s`** — provided preamble (parses args, calls function, prints result)
2. **Generated `.s` file** — your compiler produces this

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

---

## Build Process

```text
$ 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
```

- Arguments `3 4 7` → registers `a0`, `a1`, `a2`
- Preamble calls `ntlang_expr`, prints return value

---

## What is a Stack Machine?

All intermediate values stored on the **program stack**:

1. **Push** values onto the stack
2. **Pop** operands, apply operation, **push** result back

<div class="info-box">
Simple to implement — naturally maps to recursive tree traversal.
</div>

---

## Stack Evolution: `(3 + 4) * 7`

```text
Step 1: Push 3       Stack: [3]
Step 2: Push 4       Stack: [4, 3]
Step 3: Add          Stack: [7]        (pop 4, pop 3, push 3+4)
Step 4: Push 7       Stack: [7, 7]
Step 5: Mul          Stack: [49]       (pop 7, pop 7, push 7*7)
```

Final value on stack = **49** (the result).

---

## Assembly Pattern: Push Constant

Push an integer literal onto the stack:

```asm
# 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
```

Stack grows **downward** (toward lower addresses).

---

## Assembly Pattern: Push Register

Push an argument register (`a0`–`a7`) onto the stack:

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

NTLang expressions reference `a0`–`a7` as variables — code generator pushes the corresponding register.

---

## Assembly Pattern: Unary Operator

Pop operand, apply operation, push result:

```asm
# Unary operation (e.g., negation)
lw t0, (sp)           # load operand from top
neg t0, t0            # apply operation
sw t0, (sp)           # store result back
```

<div class="highlight-box">
Stack pointer doesn't change — we replace the top value in place.
</div>

---

## Assembly Pattern: Binary Operator

Pop two operands, apply operation, push result:

```asm
# 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)
add t0, t0, t1        # apply operation
sw t0, (sp)           # store result (replaces left)
```

Two values popped, one pushed back → stack shrinks by one slot.

---

## Why This Ordering?

After recursive calls, the stack looks like:

```text
         ┌─────────────┐
  sp →   │ right value  │  (pushed second)
         ├─────────────┤
         │ left value   │  (pushed first)
         ├─────────────┤
         │ ...          │
```

So we pop right first (`lw t1, (sp)`), then access left.

---

## Code Gen Structure

The code generator **mirrors** the evaluator:

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

---

## `compile_tree_expr`: IntLit

```rust
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"));
        }
        // ... other cases
    }
    code
}
```

---

## `compile_tree_expr`: BinaryOp

```rust
ParseNode::BinaryOp { op, left, right } => {
    // Emit code for both children
    code.push_str(&compile_tree_expr(left));
    code.push_str(&compile_tree_expr(right));

// Pop right, load left
    code.push_str("    lw t1, (sp)\n");
    code.push_str("    addi sp, sp, 4\n");
    code.push_str("    lw t0, (sp)\n");

// Emit operation
    match op {
        BinaryOp::Add =>
            code.push_str("    addw t0, t0, t1\n"),
        // ... other operators
    }

code.push_str("    sw t0, (sp)\n");
}
```

---

## `compile_tree`: Entry Point

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

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 Preamble: `codegen_main.s`

What it does (Rust equivalent):

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

// Parse 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 generated function
    let result = ntlang_expr(regs[0], regs[1], ...);

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

<div class="info-box">
The preamble is <strong>provided</strong> — you only generate the expression function.
</div>

---

## Complete Example: `(a0 + a1) * a2`

**Parse tree**:

```text
        *
       / \
      +   a2
     / \
    a0  a1
```

Traversal order: `a0`, `a1`, `+`, `a2`, `*`

---

## Generated Assembly

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

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

lw t1, (sp)         # Add
    addi sp, sp, 4
    lw t0, (sp)
    addw t0, t0, t1
    sw t0, (sp)

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

lw t1, (sp)         # Mul
    addi sp, sp, 4
    lw t0, (sp)
    mul t0, t0, t1
    sw t0, (sp)

lw a0, (sp)         # Return result
    addi sp, sp, 4
    ret
```

---

## Stack Trace: `(a0 + a1) * a2`

With arguments `3 4 7`:

| Step | Action | Stack |
|---|---|---|
| 1 | Push a0 (3) | [3] |
| 2 | Push a1 (4) | [4, 3] |
| 3 | Add → 7 | [7] |
| 4 | Push a2 (7) | [7, 7] |
| 5 | Mul → 49 | [49] |
| 6 | Pop → a0 | [] |

Result: **49**

---

## Eval vs Compile: Side by Side

**Eval** — returns value

```rust
match node {
    ParseNode::IntLit(val) =>
        *val,

ParseNode::BinaryOp {
        op, left, right
    } => {
        let l = eval(left, env);
        let r = eval(right, env);
        match op {
            Add => l.wrapping_add(r),
            // ...
        }
    }
}
```

</div>
<div>

**Compile** — returns asm

```rust
match node {
    ParseNode::IntLit(val) => {
        // emit push constant
    }

ParseNode::BinaryOp {
        op, left, right
    } => {
        code += &compile(left);
        code += &compile(right);
        // emit pop, op, store
    }
}
```

</div>
</div>

---

## Key Differences

| Aspect | Eval | Compile |
|---|---|---|
| Output | `u32` value | `String` of assembly |
| Variables | HashMap lookup | Push register |
| Operations | Computed in Rust | Emitted as instructions |
| Intermediate values | Rust variables | Program stack |
| Environment | `HashMap<String, u32>` | Argument registers |

---

## Operator Reference: Binary

| NTLang | RISC-V | Description |
|---|---|---|
| `+` | `addw t0, t0, t1` | Addition |
| `-` | `subw t0, t0, t1` | Subtraction |
| `*` | `mul t0, t0, t1` | Multiplication |
| `/` | `div t0, t0, t1` | 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 |
| `>>` | `srlw t0, t0, t1` | Logical shift right |
| `>-` | `sraw t0, t0, t1` | Arithmetic shift right |

---

## Operator Reference: Unary

| NTLang | RISC-V | Description |
|---|---|---|
| `-` | `neg t0, t0` | Negation |
| `~` | `not t0, t0` | Bitwise NOT |

<div class="highlight-box">
Use <code>w</code>-suffix variants (<code>addw</code>, <code>subw</code>, <code>sllw</code>, etc.) for proper 32-bit behavior on RV64.
</div>

---

## Key Takeaways

- **Compile mode** generates RISC-V assembly instead of evaluating
- **Stack machine**: push values, pop operands, push results
- **Same recursive structure** as eval — different output type
- **Four patterns**: push constant, push register, unary op, binary op
- **Preamble** handles args and printing — you generate the function
- **No environment needed** — registers are the variables

---

## Further Reading

- [RISC-V ISA Specification](https://riscv.org/technical/specifications/)
- [RISC-V Assembly Programmer's Manual](https://github.com/riscv-non-isa/riscv-asm-manual/blob/main/riscv-asm.md)
- [The RISC-V Reader](http://www.riscvbook.com/) — Patterson & Waterman
- [Stack machine — Wikipedia](https://en.wikipedia.org/wiki/Stack_machine)