80386 Barrel Shifter의 비밀: 모든 것은 Right Shift로 통한다

최근 80386 프로세서를 SystemVerilog로 구현하며 실제 실리콘에서 추출한 마이크로코드(Microcode)를 분석하는 프로젝트를 흥미롭게 지켜보고 있습니다. 요즘처럼 트랜지스터가 남아도는 시대에는 ‘그냥 하드웨어로 때려 박지’라고 생각하기 쉽지만, 당시 인텔 엔지니어들이 제한된 리소스 안에서 CISC 명령어 셋을 구현하기 위해 부린 기교는 지금 봐도 감탄이 나옵니다.

오늘은 그중에서도 Barrel Shifter 에 대한 이야기를 해볼까 합니다. 단순히 비트를 미는 회로가 뭐 그리 대수냐고 할 수 있겠지만, 386의 구현 방식을 들여다보면 “최적화란 이런 것이다”라는 걸 뼈저리게 느끼게 됩니다.

Full Crossbar는 사치다

Barrel Shifter는 한 클럭 사이클 안에 데이터를 원하는 만큼 시프트(Shift) 할 수 있는 조합 회로(Combinational Circuit)입니다. 가장 직관적인 구현은 입력 비트와 출력 비트를 N:N으로 연결하는 Crossbar 방식이지만, 32비트 기준으로 보면 배선 복잡도가 폭발합니다.

386은 여기서 Hybrid 2-stage 디자인 이라는 영리한 타협을 했습니다.

  • Coarse Shifter: 4비트 단위로 이동 (0, 4, 8, … 28)
  • Fine Shifter: 0~3비트 단위로 이동

이 두 단계를 거치면 0부터 31까지 모든 시프트가 가능합니다. 결과적으로 약 2,000개의 트랜지스터만으로 6502 프로세서 전체 트랜지스터 수의 절반 정도 되는 면적에 32비트 시프터를 구현해냈습니다. Ken Shirriff의 리버스 엔지니어링 자료를 보면 이 회로가 얼마나 오밀조밀하게 배치되어 있는지 알 수 있죠.

충격적인 마이크로코드의 재사용성

이번 분석 글에서 가장 소름 돋았던 부분은 마이크로코드 레벨의 구현입니다. x86에는 ROL, ROR, SHL, SHR, SAR 등 다양한 시프트/로테이트 명령어가 있습니다. 상식적으로 생각하면 각각 다른 제어 로직이 필요할 것 같죠?

놀랍게도 386은 이 모든 명령어에 완벽하게 동일한 마이크로코드 시퀀스 를 사용합니다.

; ROL/ROR/SHL/SHR/SAR r, imm8 (entry 0F9)
0F9 DSTREG IMM <<>>?      ; SHIFT1: Barrel Shifter 설정
0FA SIGMA DSTREG >><<? RNI ; SHIFT2: 시프트 실행
0FB SIGMA -> DSTREG        ; 결과 저장

SHL(왼쪽 시프트)과 SHR(오른쪽 시프트)이 같은 코드를 탄다니, 말이 되나 싶었습니다. 비밀은 하드웨어 레벨의 추상화에 있었습니다.

”Everything is a Right Shift”

386의 Barrel Shifter 하드웨어는 오직 오른쪽 시프트(Right Shift)만 할 줄 압니다.

그럼 왼쪽 시프트는 어떻게 하느냐? 64비트 입력 윈도우를 활용한 기가 막힌 꼼수를 부립니다. 32비트 연산을 위해 64비트 입력을 받고, 여기서 32비트 윈도우를 잘라내는 방식입니다.

  • Right Shift: 입력의 하위 32비트에 데이터를 놓고 밉니다.
  • Left Shift: 입력의 상위 32비트 에 데이터를 놓고, width - count만큼 오른쪽으로 밉니다.

즉, x << 5를 수행하는 대신 {x, 0} >> 27을 수행하는 겁니다. 결과는 수학적으로 동일하죠. 하드웨어 신호 하나(shift_swap)가 피연산자의 위치를 바꾸고, 시프트 카운트를 보수(complement)로 뒤집어버립니다. 덕분에 마이크로코드는 “그냥 설정된 대로 밀어라”라고 명령만 내리면 되는 구조입니다.

이런 설계 철학은 정말 매력적입니다. 복잡성은 하드웨어의 전처리 로직에 숨기고, 제어 흐름(Microcode)은 극도로 단순화했습니다. 유지보수성과 공간 효율성을 동시에 잡은 것이죠.

RCL/RCR: 우아함 속에 숨겨진 ‘Hack’

하지만 모든 것이 완벽할 순 없습니다. Carry Flag를 포함해서 회전하는 RCL/RCR 명령어는 이 깔끔한 패턴을 깨뜨리는 주범입니다.

문제는 두 가지입니다.

  1. 연산 폭이 32비트가 아니라 33비트(32 + CF)가 됩니다.
  2. 33은 2의 거듭제곱이 아니라서 모듈로 연산이 더럽습니다.

결국 386은 이 경우에만 별도의 느린 마이크로코드 경로(Slow Path)를 탑니다. 루프를 돌면서 width만큼 빼고 시프트를 반복하는 방식이죠. Hacker News의 한 유저(anon)가 지적했듯, 이는 상당히 비효율적인 구현입니다.

“Implementing rotate through carry like that was a really bad decision IMO…”

대부분의 RCL/RCR이 1비트 회전에 쓰인다는 점을 감안하면, RCL x, 1 같은 케이스는 최적화할 수 있었을 텐데 아쉬움이 남습니다. 아마도 출시 일정에 쫓겨 “작동하면 됐다”고 넘어간 코드가 아닐까 하는 합리적 의심이 듭니다. (우리도 자주 겪는 일이죠?)

Bit Test 명령어의 재발견

BT, BTS 같은 비트 테스트 명령어들도 이 Barrel Shifter를 재사용합니다. 특정 비트를 테스트하기 위해 복잡한 인덱싱 회로를 만드는 대신, 그냥 해당 비트가 0번 위치에 오도록 데이터를 회전 시켜버립니다. 그러고 나서 0번 비트만 지지고 볶는 거죠.

메모리 오프셋 계산까지 Barrel Shifter로 처리한다는 점은 인텔 엔지니어들이 이 하드웨어를 얼마나 알뜰살뜰하게 써먹었는지 보여줍니다.

결론: 제약이 만들어낸 예술

80386의 Barrel Shifter는 하드웨어 가속과 마이크로코드의 유연성 사이에서 줄타기 를 보여주는 교과서적인 예제입니다. 2,000개의 트랜지스터로 이 모든 케이스를 커버하기 위해 데이터 패스(Data Path)를 64비트로 확장하고, 모든 연산을 Right Shift로 환원시킨 아이디어는 지금 봐도 세련됐습니다.

물론 RCL의 구현처럼 냄새나는 레거시도 섞여 있지만, 그것조차 엔지니어링의 현실을 보여주는 것 같아 인간미가 느껴집니다. 요즘 CPU들은 수십억 개의 트랜지스터를 쓰지만, 가끔은 이렇게 비트 하나, 게이트 하나를 아끼던 시절의 설계를 보며 ‘기본기’를 되새길 필요가 있어 보입니다.

Reference: