C Extension: Decompressor, 16-Bit Fetch, and Misaligned 32-Bit Instructions

In parts 19 and 20 we added M and A to the RV32I 5-stage pipelined core. Both were about the execution side (EX and MEM). The C extension, by contrast, changes only the front end (IF). The instruction formats were covered in part 11, so this time I build Python models of how to pull a stream of mixed 16-bit and 32-bit instructions out of memory organized in 32-bit words, how to expand 16 bits into 32 bits, and which 16-bit values must be treated as illegal, and compare them against GNU objdump and QEMU execution traces.

1. What the C extension asks of a core

With the C extension, a 32-bit instruction can start at any 2-byte boundary, not only at a 4-byte boundary (IALIGN = 16, Unprivileged spec section 26.1). The specification sets one overarching principle: every compressed instruction expands to a single 32-bit instruction in the base ISA (or F/D). The specification itself cites the benefit that "the hardware can simply expand it in the decode stage."

The last row is easy to miss. With C, a branch or jump target only needs to be a multiple of 2, and the specification states that "with the C extension, no instruction raises an instruction-address-misaligned exception." jalr already clears bit 0 of the target, so no case is left over.

2. The decompressor: 16 bits to 32 bits

The decompressor is pure combinational logic. It picks the instruction by quadrant (op = [1:0]) and funct3 ([15:13]), gathers the scattered immediate bits, and places them back into the 32-bit format. The 3-bit register fields (rd′, rs1′, rs2′) get 01 prepended to become x8–x15.

Let's expand by hand 0xf77d, at the end of the CRC loop in the program I ran.

Lining up the offset bits from the most significant gives 1_1110_1110, which is −18 as a 9-bit signed value. The expansion is bne a4, x0, -18, machine code 0xfe0717e3, and −18 from 0x80000170 matches the target 0x8000015e that objdump showed. What matters is that the offset of the expanded 32-bit instruction is also relative to the compressed instruction's own pc. The pc doesn't change, so the branch address circuit is reused as is.

Expanding a few more makes the pattern visible.

Only c.jalr does not map exactly. It expands to jalr x1, 0(rs1), but the link value is pc + 2, not pc + 4. The specification points this out too, saying that "supporting both offsets of 2 and 4 is a small change." In an implementation, the is_rvc bit the decompressor emits can serve as the select signal for the link address adder. The same goes for c.jal.

3. Illegal compressed instructions and HINTs

In the 16-bit space, 49,152 values have low two bits other than 11. Only some of them are valid instructions in RV32C (no F or D). The decompressor must raise illegal for the rest. Here is how the model classified them.

The illegal/reserved class mixes encodings of different kinds. Each becomes a condition in the decompressor.

HINTs are encodings that "have no effect because rd = x0." The decompressor can simply expand them to 32 bits. c.li x0, 5 becomes addi x0, x0, 5, and since writes to x0 are discarded, it naturally does nothing. No special handling is needed.

I compared the model's results against objdump. I placed all 49,152 values at 4-byte intervals with .insn, assembled them, and compared the lines objdump read with the lines it read for my decompressor's expanded 32-bit instructions placed at the same addresses. Alias differences, such as mv meaning both addi rd,rs,0 and add rd,x0,rs, were treated as having the same meaning.

The 1,537 are c.slli with shamt[5] = 1 (1,024), c.srli/c.srai with shamt[5] = 1 (512), and c.addi16sp with imm = 0 (1). objdump simply displayed these as c.slli zero,0x20, srli s0,s0,0x20, addi sp,sp,0, and so on. A disassembler is a display tool, so it reads leniently. A hardware decompressor must treat them as illegal, as the specification says. Executing shamt[5] = 1 on RV32 as a shift by 32 in a core without custom extensions is a common bug.

4. The fetch buffer: pulling out instructions that span words

Instruction memory (or the cache) delivers aligned 32-bit words. But instructions start at 2-byte boundaries, so the lower half of a 32-bit instruction can be in the upper part of one word and the upper half in the lower part of the next word. There are three cases.

The simplest approach is to re-read the needed words for every instruction. A spanning instruction is read twice. If instead you keep a small buffer that holds the leftover 16 bits, each word is read only once during sequential execution. The model's buffer has three 16-bit slots. It checks the length from [1:0] of the front slot and emits the instruction once the needed slots are full. When two or more slots are empty, it reads the next word to fill them.

def ready(self):
    if not self.q: return 0
    n = 1 if self.q[0][1] & 3 != 3 else 2   # number of 16-bit slots
    return n if len(self.q) >= n else 0

def redirect(self, pc):
    self.q = []; self.fetch_addr = pc & ~3
    self.skip = pc & 2   # if the target is at +2, drop the lower half of the first word

When a branch or jump changes the pc, the buffer is flushed and reading restarts from the word that contains the target. If the target is at a 4-byte boundary + 2, the lower half of the first word is dropped. If the target instruction is 32-bit, the first word alone isn't enough, so one more read is needed. That adds one more bubble cycle to the fetch.

I measured how often this case comes up in a real program. I built a C program (prog.c) mixing sorting, CRC32, string reversal, and matrix multiplication with -march=rv32imc -O1. Its .text was 880 bytes, 23% smaller than the rv32im build of the same program (1,144 bytes).

5. Hands-on 1: checking the static instruction stream against objdump

First, I pulled the whole .text through the fetch buffer in order from the start. For each instruction pulled, I compared the address, bits, and length with the corresponding riscv64-elf-objdump -d line, and for compressed instructions I read my expanded 32-bit instruction back through objdump to confirm it had the same meaning as the original line.

Almost half of the 32-bit instructions span two words. Once a single compressed instruction is inserted, the 32-bit instructions after it are shifted by 2 bytes, so this is expected. The 46.2% compression ratio for this program is slightly below the "typically 50–60%" the specification mentions.

6. Hands-on 2: counting fetches in execution order

Next is the actual execution order. I ran QEMU with one translation block per instruction (-accel tcg,one-insn-per-tb=on -d exec,nochain) and recorded the executed pcs in order. I cut off the spin loop at the end of the trace (j 1b; the number of iterations until QEMU stopped varied every run). Feeding this pc sequence into the fetch buffer model, whenever the next pc is not pc + length, it is treated as a branch and the buffer is flushed. I ran it while checking that the address of each instruction the model pulled matched QEMU's pc every time.

That nearly all targets sit at +2 is particular to this program. The two most frequent targets are the CRC inner loop (1,792 times) and the sort inner loop (1,059 times), and both happened to start with a 32-bit instruction at a +2 position. So I rebuilt with GCC's alignment options (-falign-loops=4 -falign-jumps=4 -falign-labels=4) and repeated the measurement.

Fetch bubbles are the cycles spent waiting for the first instruction after a branch to be fully assembled. Each branch costs at least 1 (reading the target word), and 1 more if the target is a spanning 32-bit instruction. 3,409 + 3,184 + 1 at the start = 6,594, which checks out. Aligning the targets cut spanning targets down to 1, reducing bubbles to 3,411, at the cost of the code growing from 880 to 900 bytes and executed instructions rising slightly to 24,738 (when execution passes through alignment nops).

Also worth noting is that rv32im and rv32imc execute the same 24,713 instructions. Compression changes only the size, not the instructions. Yet re-reading every time without a buffer actually reads 37% more than uncompressed code. To save instruction memory bandwidth with the C extension, a fetch buffer is essential.

The machine is a Mac M1 Max, with riscv64-elf GCC 16.2 and binutils 2.47, and QEMU 11.1.3. Running the whole model (including checking every 16-bit value) took about 1 second.

7. Design checklist: the C extension

Of the last two rows, the page boundary issue comes up again from part 30 on, which deals with virtual memory. If the upper half of a spanning instruction is on the next page and that page is missing, the fault address (mtval) may point not to the instruction's start address but to the part that actually failed (within what the Privileged spec allows; to be checked in that part).

Summary

• Implementing the C extension comes down to the fetch buffer, length detection, and decompressor in the IF stage. The decoder and execution units stay as they are, and a single is_rvc bit selects pc+2/+4 and the link address for c.jal/c.jalr.
• I expanded all 49,152 16-bit values and compared them against objdump. 28,823 valid/HINT encodings had the same meaning, and the 1,537 that objdump decoded are reserved in RV32C, so hardware must treat them as illegal.
• In a real program, 36.7% of executed instructions were 32-bit instructions spanning two words. A fetch buffer with three 16-bit slots cut word reads from 33,771 to 23,903, fewer than uncompressed code (24,713).
• If a branch target is a 32-bit instruction at a +2 position, one more fetch bubble occurs. In this program, aligning targets cut bubbles from 6,594 to 3,411 at the cost of 20 more bytes of code.

Next post: Part 22 covers the last instruction-side problem, FENCE.I and self-modifying code. Using QEMU and a Python model, it examines why freshly written code is invisible on a core with split instruction and data caches, what FENCE.I does and does not guarantee (same hart only), and why even a simple core without caches must flush this part's fetch buffer.

References

• The RISC-V Instruction Set Manual, Volume I: Unprivileged Architecture, Version 20240411. Chapter 26, "C" Extension (26.1 Overview, 26.2 Formats, 26.4 Control Transfer, 26.5 Integer Computational and 26.5.4 Defined Illegal Instruction, 26.6 LR/SC Ordering, 26.7 HINTs, 26.8 Instruction Listings). https://github.com/riscv/riscv-isa-manual
• D. Harris et al., RISC-V System-on-Chip Design, 2023. Compressed instruction decompressor and fetch implementation (CORE-V Wally)
• D. Patterson, A. Waterman, The RISC-V Reader, 2017. Chapter 7, RV32C
• A. Waterman, "Improving Energy Efficiency and Reducing Code Size with RISC-V Compressed," M.S. thesis, UC Berkeley, 2011
• QEMU logging options (-d exec, one-insn-per-tb). https://www.qemu.org/docs/master/devel/tcg.html