SBCL: 终极汇编代码面包板 (2014)

# SBCL：终极的汇编代码插板 来源：https://pvk.ca/Blog/2014/03/15/sbcl-the-ultimate-assembly-code-breadboard/ *编辑：Lutz Euler 指出，`NEXT` 序列（曾）对带索引寄存器但无基址的有效地址进行了编码。该错误不影响指令含义，但强制使用了浪费的编码方式。机器码差异如下所示。* *之前（14 字节）：* `` 1 2 3 4 `` `` ; 03: 8B043D00000000 MOV EAX, [RDI] ; _5_ 个无用字节！ ; 0A: 4883C704 ADD RDI, 4 ; 0E: 4801F0 ADD RAX, RSI ; 11: FFE0 JMP RAX `` *现在（9 字节）：* `` 1 2 3 4 `` `` ; 93: 8B07 MOV EAX, [RDI] ; 95: 4883C704 ADD RDI, 4 ; 99: 4801F0 ADD RAX, RSI ; 9C: FFE0 JMP RAX `` *我已修正了 `NEXT` 的定义，但未修改下面的反汇编片段；它们仍显示旧的机器码。* 本周早些时候，我再次审视了 F18 (http://www.greenarraychips.com/)。就像 Chuck Moore 的通常作品一样，很难区分这是疯狂还是纯粹的才华 ;) 让我印象深刻的一点是栈非常小：只有 10 个槽位，没有任何花哨的溢出/下溢陷阱。其理由是，如果你需要更多槽位，那说明你做错了，而当你清楚自己在做什么时，静默溢出是有用的。这与我使用 HP-41C 和 x87 的经验相符。这也让我想起 djb 的一篇文章 (http://cr.yp.to/qhasm/20050210-fxch.txt) ，他批评了我们对 x87 旋转栈的误用：他的论点是，通过精心调度，一个“免费”的 `FXCH` 使得栈与寄存器等效，甚至更优。文章以一个（非流水线）循环结束，该循环利用 x87 隐式栈旋转，没有浪费任何周期在数据移动上。 这让我思考，对于将栈限制为，例如，8 个槽位的基于栈的虚拟机，有哪些实现技术可用。显然，理想情况是将所有内容保留在寄存器中。然而，如果我们天真地这样做，push 和 pop 会变得复杂得多；这就是为什么 Forth 引擎通常只缓存栈顶的 1-2 个元素。 我决定模仿 x87 和 F18（编辑：忽略后者的两个 TOS 缓存寄存器）：push/pop 不会引起任何数据移动。相反，如下面的图所示，它们递减/递增一个指向栈顶（TOS）的模计数器。这在软件中仍然会很慢（大多数 ISA 无法索引寄存器）。关键在于计数器只能取很少的值：如果栈有 8 个槽位，则只有 8 个值。栈虚拟机出于性能原因已经复制了原语操作（例如，通过将同一原语的执行分散到多个地址来帮助 BTB），因此为栈计数器可以取的所有 8 个值专门化原语似乎是合理的。 在一个常规的直接线程化虚拟机中，大多数原语操作会以跳转到下一个原语的代码序列结束（`NEXT`），类似于： ``` add rsi, 8 ; 在跳转前递增虚拟 IP jmp [rsi-8] ; 跳转到 RSI 先前指向的地址 ``` 其中 `rsi` 是虚拟指令指针，而虚拟机指令仅仅是指向相关原语机器码的指针。 我将对这个序列做两处修改。我不喜欢在字节码中硬编码地址，而且每条虚拟指令使用 64 位过于浪费。相反，我将编码相对于原语代码块的偏移量： ``` mov eax, [rsi] add rsi, 4 add rax, rdi jmp rax ``` 其中 `rdi` 是原语的基地址。 我还需要根据隐式栈计数器的新值进行分发。我决定通过以固定间隔（例如一页）存储每个原语的变体，使分发尽可能简单。我将其四舍五入到 `64 * 67 = 4288` 字节，以最大程度减少别名冲突。`NEXT` 变成类似： ``` mov eax, [rsi] add rsi, 4 lea rax, [rax + rdi + variant_offset] jmp rax ``` 诀窍在于 `variant_offset = 4288 * stack_counter`，而栈计数器通常在编译原语时是已知的。如果栈保持不变，计数器也保持不变；推送值会递减计数器，弹出值会递增计数器。 这看起来足够合理。让我们看看能否让它工作。 ## 准备工作 我想探索一个问题，为此我将生成大量重复的机器码。SLIME 的 REPL 和 SBCL 的汇编器非常适合这项任务！（希望我清楚我正在使用不受支持的内部接口；如果出现问题，一切后果自负。） 虚拟机的基本设计是： - `r8`-`r15`：栈槽位（32 位）； - `rsi`：机器码原语的基地址； - `rdi`：虚拟指令指针（指向*下一条*指令）； - `rax`、`rbx`、`rcx`、`rdx`：临时寄存器； - `rsp`：（虚拟）返回栈指针。 `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 `` `` (import '(sb-assem:inst sb-vm::make-ea)) ; 我们将大量使用这两个 ;; 我们栈的后备存储 (defvar *stack* (make-array 8 :initial-contents (list sb-vm::r8d-tn sb-vm::r9d-tn sb-vm::r10d-tn sb-vm::r11d-tn sb-vm::r12d-tn sb-vm::r13d-tn sb-vm::r14d-tn sb-vm::r15d-tn))) ;; 原语生成时的栈指针 (defvar *stack-pointer*) ;; (@ 0) 返回（当前）TOS 的寄存器，(@ 1) 返回其下面的一个，以此类推。 (defun @ (i) (aref *stack* (mod (+ i *stack-pointer*) (length *stack*)))) (defvar *code-base* sb-vm::rsi-tn) (defvar *virtual-ip* sb-vm::rdi-tn) (defvar *rax* sb-vm::rax-tn) (defvar *rbx* sb-vm::rax-tn) (defvar *rcx* sb-vm::rax-tn) (defvar *rdx* sb-vm::rax-tn) ;; 变体之间相隔 *primitive-code-offset* 字节 (defvar *primitive-code-offset* (* 64 67)) ;; 每个 *stack-pointer* 值拥有自己的代码页 (defstruct code-page (alloc 0) ; 下一个空闲字节的索引。 (code (make-array *primitive-code-offset* :element-type '(unsigned-byte 8)))) `` 想法是，我们将为每个原语定义函数来发射汇编代码；这些函数将通过 `@` 隐式地参数化 `*stack-pointer*`。然后我们可以根据需要多次调用它们，以覆盖 `*stack-pointer*` 的所有值。唯一的复杂之处在于代码序列的长度会不同，因此我们必须插入填充以保持同步。这就是 `emit-code` 所做的： `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `` `` (defun emit-code (pages emitter) ;; 必须有与栈槽位数同样多的代码页 (assert (= (length *stack*) (length pages))) ;; 找到最右边的起始点，并 16 字节对齐 (let* ((alloc (logandc2 (+ 15 (reduce #'max pages :key #'code-page-alloc)) 15)) (bytes (loop for i below (length pages) for page = (elt pages i) collect (let ((segment (sb-assem:make-segment)) (*stack-pointer* i)) ;; 在新鲜的代码段中为此 *stack-pointer* 值组装变体 (sb-assem:assemble (segment) ;; 但首先，插入填充 (sb-vm::emit-long-nop segment (- alloc (code-page-alloc page))) (funcall emitter)) ;; 清理任何反向引用 (sb-assem:finalize-segment segment) ;; 然后获取（位置无关的）机器码作为字节向量 (sb-assem:segment-contents-as-vector segment))))) ;; 最后，将每个机器码序列复制到正确的代码页 (map nil (lambda (page bytes) (let ((alloc (code-page-alloc page))) (replace (code-page-code page) bytes :start1 alloc) (assert (<= (+ alloc (length bytes)) (length (code-page-code page)))) (setf (code-page-alloc page) (+ alloc (length bytes))))) pages bytes) ;; 并返回该代码序列的偏移量 alloc)) `` 此函数由 `emit-all-code` 使用，用于为一组原语发射机器码，同时跟踪每个原语的起始偏移量。 `` 1 2 3 4 5 6 7 8 9 10 `` `` (defun emit-all-code (&rest emitters) (let ((pages (loop repeat (length *stack*) for page = (make-code-page) ;; 预先用单字节 NOP 填充所有内容 do (fill (code-page-code page) #x90) collect page))) (values (mapcar (lambda (emitter) (emit-code pages emitter)) emitters) pages))) `` 现在，压轴戏： `` 1 2 3 4 5 6 7 8 9 10 11 12 13 `` `` (defun next (&optional offset) (setf offset (or offset 0)) ; 适应处理 IP 的原语 (let ((rotation (mod *stack-pointer* (length *stack*)))) (inst movzx *rax* (make-ea :dword :base *virtual-ip* :disp offset)) (unless (= -4 offset) (inst add *virtual-ip* (+ 4 offset))) (if (zerop rotation) (inst add *rax* *code-base*) (inst lea *rax* (make-ea :qword :base *code-base* :index *rax* :disp (* rotation *primitive-code-offset*)))) (inst jmp *rax*))) `` ## 第一步 让我们添加几个简单的原语。 `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `` `` (defun swap () (inst xchg (@ 0) (@ 1)) ; 交换栈顶和 stack[1] (next)) (defun dup () (decf *stack-pointer*) ; 增长栈（向下增长） (inst mov (@ 0) (@ 1)) ; 并覆盖 TOS (next)) (defun drop (&optional offset) (incf *stack-pointer*) ; 仅缩小栈 (next offset)) (defun add () (inst add (@ 1) (@ 0)) ; 第二个元素成为 TOS (drop)) (defun sub () (inst sub (@ 1) (@ 0)) (drop)) `` `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `` `` CL-USER> (setf *print-length* 100) 100 CL-USER> (emit-all-code 'swap 'dup 'drop 'add 'sub) (0 32 64 96 128) (#S(CODE-PAGE :ALLOC 152 :CODE #(69 135 193 139 4 61 0 0 0 0 72 131 199 4 72 1 240 255 224 102 15 31 132 0 0 0 0 0 15 31 64 0 69 139 248 139 4 61 0 0 0 0 72 131 199 4 72 141 132 6 64 117 0 0 255 224 15 31 132 0 0 0 0 0 139 4 61 0 0 0 0 72 131 199 4 72 141 132 6 192 16 0 0 255 224 102 15 31 132 0 0 0 0 0 102 144 69 1 193 139 ...)) ...) CL-USER> (defparameter *code0* (code-page-code (first (second /)))) *CODE0* CL-USER> (defparameter *code1* (code-page-code (second (second //)))) *CODE1* `` `swap` 的代码位于字节 0 到 32 之间。让我们看看 `*stack-pointer* = 0` 和 `*stack-pointer* = 1` 的版本。 `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `` `` CL-USER> (sb-sys:with-pinned-objects (*code0*) (sb-disassem:disassemble-memory (sb-sys:vector-sap *code0*) 32)) ; Size: 32 bytes ; 0669C700: 4587C1 XCHG R8D, R9D ; 03: 8B043D00000000 MOV EAX, [RDI] ; 0A: 4883C704 ADD RDI, 4 ; 0E: 4801F0 ADD RAX, RSI ; 11: FFE0 JMP RAX ; 13: 660F1F840000000000 NOP ; 填充 NOP ; 1C: 0F1F4000 NOP NIL CL-USER> (sb-sys:with-pinned-objects (*code1*) (sb-disassem:disassemble-memory (sb-sys:vector-sap *code1*) 32)) ; Size: 32 bytes ; 0669D810: 4587CA XCHG R9D, R10D ; 13: 8B043D00000000 MOV EAX, [RDI] ; 1A: 4883C704 ADD RDI, 4 ; 1E: 488D8406C0100000 LEA RAX, [RSI+RAX+4288] ; 26: FFE0 JMP RAX ; 28: 0F1F840000000000 NOP NIL `` `dup` 位于 32-64，`sub` 位于 128-152： `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `` `` CL-USER> (sb-sys:with-pinned-objects (*code0*) (sb-disassem:disassemble-memory (sb-sys:sap+ (sb-sys:vector-sap *code0*) 32) 32)) ; Size: 32 bytes ; 0669C720: 458BF8 MOV R15D, R8D ; 23: 8B043D00000000 MOV EAX, [RDI] ; 2A: 4883C704 ADD RDI, 4 ; 2E: 488D840640750000 LEA RAX, [RSI+RAX+30016] ; 36: FFE0 JMP RAX ; 38: 0F1F840000000000 NOP NIL CL-USER> (sb-sys:with-pinned-objects (*code0*) (sb-disassem:disassemble-memory (sb-sys:sap+ (sb-sys:vector-sap *code0*) 128) 24)) ; Size: 24 bytes ; 0669C780: 4529C1 SUB R9D, R8D ; 83: 8B043D00000000 MOV EAX, [RDI] ; 8A: 4883C704 ADD RDI, 4 ; 8E: 488D8406C0100000 LEA RAX, [RSI+RAX+4288] ; 96: FFE0 JMP RAX NIL `` 这些相当紧凑。我当然喜欢数据移动如此之少；`NEXT` 序列有点棘手，但间接分支很可能是其最薄弱（且最难以避免）的点。 ## 控制流原语 没有控制流的虚拟机甚至算不上玩具。首先是无条件相对跳转。这些可以编码为 `[jmp] [offset]`，其中 32 位偏移量相对于 `offset` 的结尾。我们只需用新地址覆盖 `*virtual-ip*`。 `` 1 2 3 4 5 `` `` (defun jmp () (inst movsx *rax* (make-ea :dword :base *virtual-ip*)) (inst lea *virtual-ip* (make-ea :dword :base *virtual-ip* :index *rax* :disp 4)) (next)) `` 调用和返回是类 Forth 引擎的核心。`ret` 很简单：只需从控制栈弹出到 `*virtual-ip*`。 `` 1 2 3 `` `` (defun ret () (inst pop *virtual-ip*) (next)) `` 调用稍微复杂一些。它类似于 `jmp`，但将*下一条*指令的地址推送到控制栈： `` 1 2 3 4 5 6 `` `` (defun call () (inst movsx *rax* (make-ea :dword :base *virtual-ip*)) (inst add *virtual-ip* 4) (inst push *virtual-ip*) (inst add *virtual-ip* *rax*) (next)) `` 让我们看看生成的机器码。 `` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `` `` CL-USER> (emit-all-code 'jmp 'ret 'call) (0 32 64) (#S(CODE-PAGE :ALLOC 91 :CODE #(72 99 7 72 141 124 7 4 139 4 61 0 0 0 0 72 131 199 4 72 1 240 255 224 15 31 132 0 0 0 0 0 95 139 4 61 0 0 0 0 72 131 199 4 72 1 240 255 224 102 15 31 132 0 0 0 0 0 102 15 31 68 0 0 72 99 7 72 131 199 4 87 72 1 199 139 4 61 0 0 0 0 72 131 199 4 72 1 240 255 224 144 144 144 144 144 144 144 144 144 ...)) ...) CL-USER> (let ((code (code-page-code (first (second /))))) (sb-sys:with-pinned-objects (code) (sb-disassem:disassemble-memory (sb-sys:vector-sap code) 91))) ; Size: 91 bytes ; 08395200: 486307 MOVSXD RAX, DWORD PTR [RDI] ; jmp ; 03: 488D7C0704 LEA RDI, [RDI+RAX+4] ; 08: 8B043D00000000 MOV EAX, [RDI] ; 0F: 4883C704 ADD RDI, 4 ; 13: 4801F0 ADD RAX, RSI ; 16: FFE0 JMP RAX ; 18: 0F1F840000000000 NOP ; 20: 5F POP RDI ; ret ; 21: 8B043D0