NEMU RISC-V32 指令模式匹配与汇编级优化

TL;DR

本文沿着一条「先问为什么，再看怎么做」的线索，拆开 NEMU 的 RISC-V32 指令解码：从「怎么知道当前是哪条指令」这个问题出发，引出模式字符串，再手推 pattern_decode 如何把它变成 key/mask/shift，最后贴出宿主机 Intel 汇编，证明这套写法在 -O2 下被折叠成纯粹的立即数比较——并和一个普通 for 循环查表解码器做对照。

起点：怎么分辨一条指令

NEMU 执行一条指令的流程很朴素：从 pc 取 4 字节（inst_fetch），拿到一个 32 位整数，然后必须回答一个问题——这 32 位到底是 add、lw、sb，还是别的什么？

回答完还要顺手把操作数拆出来：rd 是谁、rs1 是谁、立即数是多少。这一整套动作叫指令解码。

最直白的做法是手写字段提取：

uint32_t opcode = BITS(inst, 6, 0);
uint32_t funct3 = BITS(inst, 14, 12);
uint32_t funct7 = BITS(inst, 31, 25);

if (opcode == 0x33 && funct3 == 0x0 && funct7 == 0x0) { /* add */ }
else if (opcode == 0x03 && funct3 == 0x4) { /* lbu */ }
...

能跑，但问题很明显：

• RISC-V 指令有上百条，if-else 链会越堆越长；
• 每条指令关心的字段位置都不同，BITS(inst, ...) 的具体参数极易写错；
• 新增一条指令就要改这一大坨逻辑。

于是自然会想：能不能不逐个抠字段，而是直接拿整个 32 位去「对形状」？

抽象：模式字符串

观察指令的二进制，会发现每条指令其实就是「一部分位是固定的，另一部分位是变化的」。

以 lbu（Load Byte Unsigned）为例，它的 32 位组成是：

imm[11:5] imm[4:0]   rs1   funct3    rd   opcode[6:2] opcode[1:0]
 ???????   ?????    ?????     100   ?????      00000         11

把固定位和可变位直接写成一行，就得到了 NEMU 用的模式字符串：

"??????? ????? ????? 100 ????? 00000 11"

规则很简单：

• 0 / 1：固定位，必须精确匹配
• ?：通配符，匹配任意 bit
• 空格：只是位域分隔，方便人读，不参与匹配

一眼就能看出：这条模式说的是「funct3 = 100，且低 7 位 opcode 部分是 0000011」，其余随便——正是 lbu。

这个抽象好读、好写、好改。但马上遇到下一个问题：一行字符串，怎么和 32 位整数做比较？

预计算：匹配即掩码比较

最笨的办法是运行时逐字符扫：

for (int i = 0; i < strlen(pattern); i++) {
  if (pattern[i] == '0' || pattern[i] == '1') {
    if (bit_of(inst, i) != pattern[i] - '0') return false;
  }
}

每条指令、每条模式都扫 32 个字符，代价太高。

但注意一个关键事实：模式字符串是编译期就写死的常量。既然它不变，为什么要在运行时反复解析？应该把「匹配模式」这件事，提前翻译成一个等价的、只要几条机器指令就能算完的形式。

怎么翻译？把「匹配模式」等价改写成「先把可变位遮掉，再和固定值比较」：

(inst & mask) == key

• mask：哪些是固定位，对应 bit 置 1
• key：这些固定位应该是什么值

到这里思路就清楚了：需要一个函数，把模式字符串一次性转成 mask 和 key。但还差一点——字符串是「从高位往低位」读的，而通配符会让位发生错位，所以还需要第三个量 shift 来做对齐。这三个量，就是 pattern_decode 的输出。

手推 pattern_decode

pattern_decode（decode.h:31-60）的核心只用三个累加器：

uint64_t __key = 0, __mask = 0, __shift = 0;

从左到右（高位到低位）逐字符处理，每个字符 c 的规则是：

翻译成人话：

• 固定位（0/1）→ 写进 key，mask 对应位填 1，同时把 __shift 清零；
• 通配符 ? → key/mask 都填 0（不参与比较），__shift 加一。

注意 __shift 遇固定位会清零，所以它最终等于「模式结尾连续 ? 的个数」，而不是 ? 的总数。这一点很关键，下面会看到。

遍历结束后统一右移：

*key   = __key   >> __shift;
*mask  = __mask  >> __shift;
*shift = __shift;

情形一：结尾无 ?

模式 "100"（3 位，最高位在前）：

结尾字符是 0（固定位），__shift 保持 0。所以不右移，直接得：

• key = 0b100 = 4
• mask = 0b111 = 7
• shift = 0

比较就是 (inst & 0b111) == 0b100，正好检查最低 3 位是否等于 100。

情形二：结尾有 ?

模式 "??100"（5 位）：

等等——最后一位是 0，__shift 被清零了。最终 key = 0b100、mask = 0b111、shift = 0。

这说明前面两个 ? 已经在左移过程中被「推」到了高位并填了 0，右移 0 位也没关系：(inst & 0b111) 本来就只关心低 3 位。只要结尾是固定位，前面的 ? 不需要 shift 处理。

那 shift 到底什么时候才不为 0？看 inv 的模式：

"??????? ????? ????? ??? ????? ????? ??"

结尾是 ??，所以 __shift 最终停在 2。此时 key=0, mask=0, shift=2。 比较式 ((inst >> 2) & 0) == 0 恒成立——它本来就是兜底分支，任何指令都命中。

为什么要右移：字符串从左到右拼接，处理完后 key/mask 的最低位对应模式的最后一位。如果结尾是 ?，这些低位是无效的 0，右移 __shift 位正好把它们丢掉，使有效比较位重新对齐到最低位；与此同时指令也右移 shift 位配合对齐。反过来，RISC-V 的真实指令模式几乎都以固定位 11（opcode 低两位）结尾，所以它们的 shift 基本都是 0。

验证：真实 lbu 模式

把 lbu 的模式按位域展开，每段对应的 bit 范围如下：

加粗的是固定位，只有三处：100 在 [14:12]，00000 在 [6:2]，11 在 [1:0]。拼起来：

• mask = 0x7000 | 0x007c | 0x0003 = 0x707f
• key = (0b100 << 12) | (0b00000 << 2) | 0b11 = 0x4000 | 0x0000 | 0x0003 = 0x4003
• shift = 0（结尾是固定位 1）

这个结论先记住：0x707f 和 0x4003。下一节的汇编里，它们会原封不动地出现。

INSTPAT 怎么用

机制清楚了，使用就非常简单。NEMU 把它包成一个宏（decode.h:90-97）：

#define INSTPAT(pattern, ...) do { \
  uint64_t key, mask, shift; \
  pattern_decode(pattern, STRLEN(pattern), &key, &mask, &shift); \
  if ((((uint64_t)INSTPAT_INST(s) >> shift) & mask) == key) { \
    INSTPAT_MATCH(s, ##__VA_ARGS__); \
    goto *(__instpat_end); \
  } \
} while (0)

三步：解码模式 → ((inst >> shift) & mask) == key 比较 → 命中则执行动作并跳到末尾。

命中之后由 INSTPAT_MATCH（decode.h:54-59）负责按类型取操作数：

#define INSTPAT_MATCH(s, name, type, ... /* execute body */ ) { \
  int rd = 0; \
  word_t src1 = 0, src2 = 0, imm = 0; \
  decode_operand(s, &rd, &src1, &src2, &imm, concat(TYPE_, type)); \
  __VA_ARGS__ ; \
}

type 决定用哪种立即数提取方式（TYPE_I / TYPE_U / TYPE_S / TYPE_N），具体在 decode_operand（inst.c:36-48）里用一组宏 immI()/immU()/immS() 实现。

真正定义指令时，inst.c:61-68 就长这样：

INSTPAT_START();
INSTPAT("??????? ????? ????? ??? ????? 00101 11", auipc  , U, R(rd) = s->pc + imm);
INSTPAT("??????? ????? ????? 100 ????? 00000 11", lbu    , I, R(rd) = Mr(src1 + imm, 1));
INSTPAT("??????? ????? ????? 000 ????? 01000 11", sb     , S, Mw(src1 + imm, 1, src2));

INSTPAT("0000000 00001 00000 000 00000 11100 11", ebreak , N, NEMUTRAP(s->pc, R(10)));
INSTPAT("??????? ????? ????? ??? ????? ????? ??", inv    , N, INV(s->pc));
INSTPAT_END();

每条指令一行，模式、类型、动作一目了然。最后 inv 全是 ?，mask=0，兜底。

编译器真的优化掉了吗

前面说了这么多「预计算」，但 pattern_decode 终究是个运行时函数。它真的会在运行时被执行吗？ 我们用真实汇编来验证。

实验设置

NEMU 是跑在宿主机（x86-64）上的普通 C 程序，所以我直接用宿主机编译。写两份等价解码器，gcc -O2 -masm=intel -S：

• A 版：照搬 NEMU 的 pattern_decode + INSTPAT
• B 版：普通 for 循环遍历一张运行期传入的模式表 {mask, key, type}

A 版：折叠成立即数

pattern_decode 带 always_inline，-O2 下整个函数被内联并常量折叠。生成的匹配核心（Intel 语法，节选）：

.L6:
        mov     eax, DWORD PTR [rdi]     ; eax = inst
        mov     edx, eax
        and     edx, 127                 ; mask = 0x7f      (auipc)
        cmp     edx, 23                  ; key  = 0x17      (auipc)
        mov     edx, eax
        jne     .L3
        ; ... auipc 命中，执行 R(rd) = pc + imm
        jmp     .L4
.L3:
        and     edx, 28799               ; mask = 0x707f
        cmp     edx, 16387               ; key  = 0x4003    (lbu)
        je      .L9
        cmp     edx, 35                  ; key  = 0x23      (sb)
        je      .L10
.L4:
        mov     DWORD PTR gpr[rip], 0    ; R(0) = 0
        add     rdi, 4                   ; 下一条指令
        cmp     rdi, rcx
        je      .L2
        ; 落回 .L6，处理下一条

注意那几个立即数：

• 28799 = 0x707f、16387 = 0x4003 —— 正是前面手推 lbu 得到的 mask 和 key；
• 127 = 0x7f、23 = 0x17 —— auipc 只需匹配低 7 位的 opcode。

pattern_decode 的整个字符串遍历消失了，运行时没有任何计算，也没有加载任何模式数据。 编译器在编译期就把 lbu 那串 "??????? ... 00000 11" 算成了两个立即数。

B 版：for 循环查表

同样的 -O2，但模式表是运行期参数，编译器无法内联，循环内层长这样：

.L4:
        mov     rdx, r9                  ; rdx = &table[0]
.L6:
        mov     ebx, DWORD PTR [rdx]     ; 读取 table[k].mask
        and     ebx, eax                 ; inst & mask
        cmp     ebx, DWORD PTR 4[rdx]    ; 与 table[k].key 比较
        je      .L5                      ; 命中，跳出
        add     rdx, 12                  ; k++（每个 entry 12 字节）
        cmp     rdx, r10
        jne     .L6                      ; 未命中，继续下一轮

每匹配一个 entry，都要：从内存读 mask、从内存读 key、再做循环自增和边界判断。

对比

两者其实都在做位掩码比较，真正的区别在于：INSTPAT 的掩码来自指令流里的立即数，for 循环的掩码来自内存，还额外拖着循环骨架。

反例：去掉 always_inline

为了确认「内联 + 编译期折叠」是关键，我把 always_inline 去掉再编译。GCC 立刻把 pattern_decode 提成一个独立函数 pattern_decode.constprop.0（737 条指令），匹配变成了运行时调用：

        lea     rdi, .LC1[rip]           ; 传入模式字符串
        call    pattern_decode.constprop.0
        mov     rcx, QWORD PTR 32[rsp]   ; 从栈上取 shift
        shr     rdx, cl                  ; 变量移位
        and     rdx, QWORD PTR 24[rsp]   ; 从栈上取 mask
        cmp     rdx, QWORD PTR 16[rsp]   ; 从栈上取 key
        je      .L277

key/mask/shift 全跑到栈上、运行时才算。整个汇编文件从 94 行膨胀到 1093 行。

为什么能优化干净

三点原因：

1. 模式是编译期常量。pattern_decode 的入参是字符串字面量和 sizeof 出来的常量长度，always_inline 后整个遍历被展开折叠，结果直接落成立即数。
2. 没有隐藏状态。每个 INSTPAT 之间只共享 inst，没有表指针、没有索引，编译器可以自由做公共子表达式消除（上面 and edx, 28799 就是被复用的）。
3. 结构化 goto 退出。goto *(__instpat_end) 把「命中」变成一次前向跳转，天然对应分支预测友好的控制流，也让编译器更容易把这一串比较整理成判断链。

总结

一句话：INSTPAT 把「模式匹配」从运行时的查表循环，变成了编译期折叠出来的「一条 and 加一条 cmp」。而这之所以成立，前提是 pattern_decode 被 always_inline 强制内联、且模式的全部输入都是编译期常量。

参考资料

• NEMU 源码仓库
• RISC-V 官方文档：指令格式
• Mulan PSL v2 许可证

关键文件引用

• include/cpu/decode.h:31-60 - pattern_decode 函数实现
• include/cpu/decode.h:90-97 - INSTPAT 宏定义
• src/isa/riscv32/inst.c:36-48 - decode_operand 操作数提取
• src/isa/riscv32/inst.c:61-68 - 指令模式定义案例