SBCL: 어셈블리 코드 브레드보드

가상 머신(VM) 설계와 저수준 머신 코드 최적화의 교차점에서는 종종 유연성과 성능 사이의 긴장 관계가 나타납니다. 전통적인 스택 기반 VM에서는 데이터를 푸시(push)하고 팝(pop)하는 오버헤드—종종 메모리 액세스나 복잡한 레지스터 셔플링을 수반함—가 상당한 병목 현상이 될 수 있습니다.

이 기술적 탐구에서는 Steel Bank Common Lisp (SBCL) 어셈블러를 활용하여 고성능 스택 기반 VM을 구현하는 방법을 조사합니다. 목표는 소수의 하드웨어 레지스터를 회전하는 스택(rotating stack)으로 취급하여 스택 포인터의 가능한 모든 위치에 대해 머신 코드를 특수화함으로써, 스택 작업 중의 데이터 이동을 제거하는 것입니다.

회전하는 스택 개념

F18과 x87 부동 소수점 장치에서 영감을 얻은 핵심 아이디어는 VM 스택을 작고 고정된 수의 슬롯(예: 8개)으로 제한하는 것입니다. push 또는 pop 중에 레지스터나 메모리 사이에서 물리적으로 데이터를 이동시키는 대신, VM은 현재 스택의 최상단(TOS)을 가리키는 모듈러 카운터를 유지합니다.

소프트웨어 구현에서 레지스터를 동적으로 인덱싱하는 것은 일반적으로 불가능하거나 매우 느립니다. 이를 해결하기 위해 VM은 primitive specialization이라는 기술을 사용합니다. 모든 기본 연산(예: ADD 또는 DUP)에 대해, VM은 스택 카운터의 가능한 각 값에 대해 8개의 서로 다른 머신 코드 버전을 생성합니다.

레지스터 매핑

이를 x86_64에서 구현하기 위해 다음과 같은 레지스터 할당이 사용됩니다:

r8부터 r15까지: 8개의 스택 슬롯.
rsi: 머신 코드 프리미티브의 기본 주소.
rdi: 가상 명령어 포인터 (VIP).
rax, rbx, rcx, rdx: 스크래치 레지스터.
rsp: 가상 리턴 스택 포인터.

SBCL을 이용한 VM 구현

이 프로젝트에서 SBCL은 "매크로 어셈블러" 역할을 합니다. SBCL은 머신 코드의 대화형 생성 및 검사를 허용하므로, 가상 스택 포인터의 현재 상태에 따라 어셈블리를 방출출하는 Lisp 함수를 작성하는 것이 가능합니다.

`NEXT` 시퀀스

직접 스레드형(direct-threaded) VM에서 각 프리미티브는 다음 명령어로 점프하기 위한 NEXT 시퀀스로 끝납니다. 회전하는 스택을 지원하기 위해, NEXT 시퀀스는 새로운 스택 포인터 값에 일치하는 다음 프리미티브의 버전으로 디스패치되어야 합니다.

구현에서는 각 primop의 변형(variant)을 일정한 간격(예: 4288 바이트 간격)으로 저장합니다. 디스패치 로직은 다음과 같이 오프셋을 계산합니다: variant_offset = 4288 * stack_counter

이를 통해 VM은 런타임에 조건부 검사나 복잡한 룩업 테이블을 수행하지 않고도 현재 스택 깊이에 특화된 코드로 직접 점프할 수 있습니다.

명령어 세트 구축

기본 프리미티브

SWAP, DUP, ADD와 같은 간단한 연산은 현재 TOS와 그 아래 요소에 매핑된 레지스터에 대해 특정 x86 명령어를 방출함으로써 구현됩니다. 예를 들어, ADD 연산은 단순히 (@ 1)에 있는 레지스터를 (@ 0)에 있는 레지스터에 더하고 가상 스택 포인터를 증가시킵니다.

제어 흐름

VM을 기능적으로 만들기 위해 제어 흐름 프리미티브가 필수적입니다:

JMP: 가상 IP를 상대 오프셋으로 덮어씁니다.
CALL/RET: 하드웨어 스택(rsp)을 사용하여 가상 IP의 리턴 주소를 저장합니다.
Conditionals (JZ/JNZ): CMOV (조건부 이동) 또는 중복된 NEXT 시퀀스를 사용하여 TOS 값에 기반하여 가상 IP를 업데이트합니다.

성능 분석 및 최적화

이 구현에서 가장 중요한 발견 중 하나는 연산자 "fusing"의 영향입니다. 카운터를 감소시키고 0이 아니면 점프하는 간단한 루프는 여러 방식으로 구현될 수 있습니다:

Unspecialized Bytecode: LIT $ ightarrow$ SUB $ ightarrow$ JNZ. 이것은 가장 느린 방식입니다 (네이티브 코드보다 11-15배 느림).
Fused Operator (DJN): 감소와 점프를 한 번에 처리하는 단일 프리미티브. 이는 성능을 크게 향상시킵니다.
Optimized Fused Operator (DJN2): 조건부 이동(CMOV)을 predictable한 하드웨어 분기로 교드하고 NEXT 시퀀스를 중복화함으로써, 루프는 네이티브 어셈블리보다 약 6배 느린 수준이 됩니다.

비교 요약

구현	상대적 성능 (Cycles/Iter)
Native Assembly	1x
Specialized `DJN2`	~6x
Specialized `DJN`	~8x
Unspecialized Bytecode	11-15x

결론

스택 크기가 작게 유지된다면, 가상 스택 포인터에 기반하여 프리미티브를 특수화하는 것은 스레드형 인터프리터의 오버헤드를 줄이는 실행 가능한 전략입니다. 저자가 스택 언어에 주로 관심이 있는 것은 아니지만, 이 아키텍처는 효율적인 런타임 중간 표현(IR)으로서 역할을 합니다.

이 프로젝트는 저수준 시스템 프로그래밍을 위한 도구로서 SBCL의 강력함을 강조합니다. 고수준 Lisp 추상화와 로우 레벨 머신 코드 생성 사이의 가교 역할을 함으로써, SBCL은 C나 전통적인 어셈블리 언어에서 번거로울 수 있는 어셈블리 기술의 빠른 반복과 "브레드보딩"을 가능하게 합니다.