부록 A. ILOC

책 전체에서 쓰는 가짜 ISA — RISC 스타일의 깔끔한 학습용 명령어 집합.

A.1 들어가며: 책에 등장하는 그 어셈블리

책을 한 장이라도 넘겨봤다면 loadAI, addI, cbr 같은 낯선 단어들을 봤을 것이다. 이게 바로 ILOC이다. ILOC은 Rice 대학교의 Massively Scalar Compiler Project에서 만든 중간 표현(intermediate representation)을 책에 맞게 깎아낸 버전이다. 책에서는 두 가지 역할을 동시에 한다.

• 최적화기(optimizer)의 IR로 — 데이터 흐름 분석, SSA, 스칼라 최적화 같은 미들엔드 알고리즘을 설명할 때 입력/출력으로 등장.
• 코드 생성의 단순화된 타깃으로 — 코드 모양, 명령어 선택, 스케줄링, 레지스터 할당 같은 백엔드 챕터에서 "가상의 기계어"로 등장.

추상 기계의 가정

ILOC이 그리는 가상 머신은 단순하다.

• 레지스터는 무한히 있다. r1, r2, ..., r1776 같이 그냥 끝없이 쓸 수 있다고 가정한다. (현실에서 레지스터는 부족한 자원이라는 점은 13장 레지스터 할당에서 다룬다.)
• 3-주소 형식의 레지스터-투-레지스터(register-to-register) 연산. 두 소스 레지스터를 읽어 결과를 한 타깃 레지스터에 쓴다.
• load/store가 메모리를 만지는 유일한 통로. 산술 연산은 메모리에 직접 닿지 못한다 — 전형적인 RISC 스타일.
• 주소 모드는 네 가지뿐 — direct, address+offset, address+immediate, immediate. 단순 그 자체.
• 실행 모델은 사이클 단위. 소스 피연산자는 사이클 시작에 읽고, 결과는 사이클 끝에 쓴다. 별 말 없으면 단일 기능 단위가 명령어를 나열된 순서대로 실행한다고 보면 된다.

프로그램의 골격

ILOC 프로그램은 명령어를 한 줄씩 쭉 늘어놓은 텍스트다. 각 명령어 앞에는 라벨(label)이 붙을 수 있고, 라벨과 명령어는 콜론(:)으로 분리한다. 라벨은 그냥 알파벳/숫자/하이픈으로 된 문자열이다. 한 명령어에 라벨이 두 개 이상 필요하면? nop(아무 일도 안 하는 명령어)을 끼워서 라벨을 분산시킨다 — 가짜 ISA의 사치라고 할 수 있다.

한 줄에 연산이 하나면 그냥 적고, 여러 연산을 한 사이클에 묶고 싶으면 대괄호로 감싸고 세미콜론으로 구분한다. 후자는 12장(명령어 스케줄링)에서 다중 발행(multi-issue) 기계를 설명할 때 쓴다.

       loadAI rarp,@x => r1     // 단일 연산 명령어
       [ add r1,r2 => r3 ; load r4 => r5 ]   // 두 연산을 한 사이클에 묶음
L1:    sub r3,r5 => r6

피연산자 표기와 화살표

한 연산은 opcode, 콤마로 구분된 소스 목록, 콤마로 구분된 타깃 목록으로 이루어진다. 소스와 타깃은 화살표로 분리하는데, 이 화살표가 ILOC만의 작은 디테일이다.

• => ("into") — 일반 연산. 결과가 우측 타깃에 정의된다는 뜻.
  add r1,r2 => r3 — "r1과 r2를 더해서 r3에 넣어라"
• -> — 제어 흐름 연산(분기, 점프). 타깃 라벨은 PC를 옮기는 곳일 뿐 "정의"되는 값이 아니라서 화살표 모양도 다르다.

피연산자는 register, num(정수 상수), label 셋 중 하나다. 라벨은 항상 l(소문자 엘)로 시작하게 적어서 한눈에 알아보게 한다 — 강제 규칙은 아니지만 책 전체가 따르는 관습이다.

A.2 명명 관습 — 변수, 레지스터, 그리고 ARP

예제 코드에는 같은 패턴이 반복적으로 나오는데, 그 안에 깔린 약속이 셋이다.

1. 변수의 메모리 오프셋은 @ 접두사로 표기. 즉 @x는 "변수 x가 활성 레코드 안에서 차지하는 오프셋(상수값)"이다.
2. 레지스터는 무제한이며 r로 시작. 숫자 이름(r1776)이든 기호 이름(ri)이든 둘 다 가능.
3. rarp는 예약 레지스터. 현재 활성 레코드(activation record)를 가리키는 포인터로 고정되어 있다. 6장에서 다룬 ARP다.

이 셋을 합치면 책에서 가장 자주 보는 패턴이 나온다.

loadAI rarp,@x => r1

주석은 //로 시작해서 줄 끝까지. 스캐너가 떼어낸다고 가정하므로 문법에는 등장하지 않는다.

A.3 개별 연산들

ILOC의 명령어 집합은 일부러 작게 유지되어 있다. 책 전체에서 다음 다섯 묶음만 알면 어떤 예제든 읽을 수 있다.

A.3.1 산술 연산 (Arithmetic)

전형적인 3-주소 레지스터-투-레지스터 산술. 소스가 둘, 타깃이 하나. 즉시값(immediate) 형태도 함께 제공되는데, 이건 "두 번째 피연산자가 상수"라는 뜻으로 opcode 끝에 I를 붙인다.

여기서 rsubI와 rdivI가 따로 있는 이유는 단순하다 — 뺄셈과 나눗셈은 교환법칙이 안 되니까, 즉시값을 어느 쪽에 두느냐에 따라 결과가 달라진다. 두 형태를 모두 두면 최적화기가 더 자연스럽게 코드를 줄일 수 있다.

참고로 ILOC 본문에는 데이터 타입이 정수 하나로 통일돼 있지만, 실제 ILOC 기반 처리기였다면 add가 정수용·부동소수점용·복소수용 등 여러 변종으로 갈래가 났을 것이다. Rice 연구 컴파일러에는 그렇게 타입별로 쪼개진 산술 연산이 따로 있었다고 책은 슬쩍 언급한다.

A.3.2 시프트 (Shifts)

왼쪽/오른쪽 산술 시프트가 레지스터 형태와 즉시값 형태로 각각 있다.

비슷한 결로 비트 논리 연산도 있다 — and, or, xor과 그 즉시값 형태(andI, orI, xorI). 인터페이스는 산술과 똑같다.

A.3.3 메모리 연산 (Memory Operations)

RISC답게 메모리는 load/store로만 만진다. ILOC은 정수용(load 계열)과 문자용(cload 계열)을 각각 갖고 있다.

주소 모드의 차이만 잘 봐두면 된다.

• load: 레지스터 하나가 곧 주소.
• loadAI: 레지스터 + 즉시값 — 책에서 가장 자주 보는 형태(예: loadAI rarp,@x).
• loadAO: 레지스터 + 레지스터 — 인덱스가 런타임에 계산되는 배열 접근에 적합.
• loadI: 메모리는 안 만짐. 그냥 즉시값을 레지스터에 박는다.

store는 load의 거울상이다. 다만 storeI는 없다 — 즉시값을 메모리에 직접 쓰는 연산은 정의돼 있지 않으니, 필요하면 loadI + store를 조합해야 한다.

A.3.4 레지스터-투-레지스터 복사 (Register-to-Register Copy)

메모리를 거치지 않고 값을 옮기고 싶을 때 쓴다. 정수용, 문자용, 그리고 둘 사이를 변환하는 두 형태까지 네 가지.

A.4 제어 흐름 연산

ILOC의 비교/분기는 두 가지 다른 스타일을 모두 지원한다. 책에서 어떤 경우에 어떤 스타일을 쓰는지가 7장(코드 모양) 토론의 한 축이기도 하다.

기본 스타일: 비교 결과를 레지스터에 담기

비교 연산 cmp_*는 두 레지스터를 비교해 결과(true/false)를 일반 레지스터에 쓴다. 그 다음 cbr이 이 불리언 레지스터를 보고 두 라벨 중 하나로 점프한다.

cbr의 핵심 디자인 결정은 두 라벨을 모두 명시한다는 점이다. 한쪽은 참일 때, 다른 한쪽은 거짓일 때. 보통의 어셈블리라면 "참이면 점프, 아니면 흘러내려간다(fall-through)" 형태인데, ILOC은 일부러 fall-through를 없앴다.

A.4.1 대안 문법: 조건 코드 스타일

현실의 ISA들은 비교 결과를 일반 레지스터가 아니라 조건 코드 레지스터(condition code register)에 따로 쓴다. 7장에서 이 스타일을 쓰는 칩의 코드 모양을 논하기 위해 ILOC은 대안 문법도 정의해둔다.

여기서 cci는 일반 레지스터가 아니라 조건 코드 전용 레지스터다. 차이의 핵심은 판단 책임의 위치다. 기본 스타일에서는 비교가 끝나고 결과 불리언만 남기지만, 조건 코드 스타일에서는 비교는 그냥 "비교했다"고만 표시하고, 어떤 관계인지(LT인가 EQ인가)는 분기 쪽에서 결정한다.

A.4.2 점프 (Jumps)

무조건 분기는 두 가지가 있다.

jumpI는 거의 모든 예제에서 보는 일반적인 점프다. jump는 좀 위험한 친구다 — 점프할 곳이 컴파일 타임에는 모르는 런타임 주소이기 때문이다. 이게 왜 문제인가? 컴파일러가 그 점프가 어느 라벨로 갈 수 있는지 알아낼 수가 없으면, 제어 흐름 그래프가 흐려져서 후속 분석/최적화가 다 약해진다.

그래서 책은 가급적 jump를 피하라고 권한다. 하지만 FORTRAN의 라벨 변수 점프(jump-to-label-variable) 같은 구조는 사실상 jump로 구현하는 게 가장 자연스럽다 — 즉시 분기들로 풀어내려면 라벨 후보마다 비교+분기를 늘어놓는 case 문 같은 모양이 되니까.

tbl: 점프 후의 힌트

이 손실을 조금 메우려고 ILOC은 의사연산(pseudo-op) tbl을 둔다. tbl은 실제로 실행되는 명령어가 아니라 컴파일러에게 주는 단서다 — "이 레지스터는 이 라벨일 가능성이 있다"고 적어두는 메모.

관습은 이렇다. tbl은 반드시 jump 직후에 등장하고, 한 점프 뒤에 여러 tbl이 줄지어 있을 수 있다. 컴파일러는 그 묶음을 "이 점프가 도달할 수 있는 라벨의 후보 집합"으로 해석한다.

       jump      -> ri          // ri로 점프
       tbl       ri, L01        // 후보: L01
       tbl       ri, L03        // 후보: L03
       tbl       ri, L05        // 후보: L05
       tbl       ri, L08        // 후보: L08

A.5 SSA 형태의 표현 — phi 함수

9장과 10장에서 SSA(Static Single Assignment) 형태가 등장한다. SSA를 ILOC으로 적으려면 φ-함수를 명령어로 표현해야 하는데, ILOC은 이를 위해 phi 의사연산을 정의한다.

다른 ILOC 연산과 달리 phi는 소스의 개수가 가변이다 — 해당 기본 블록으로 합류(merge)하는 들어오는 간선 수만큼 소스를 갖는다. 타깃은 항상 하나. SSA의 본질이 "이 변수의 도달 정의(reaching definition)들 중 어느 것이 살아남는가"를 합류점에서 골라내는 함수이므로, 이 가변 사이즈는 자연스럽다.

한눈에 보는 요약

책 본문의 코드를 읽다가 막히면 다음 표를 사전처럼 펼쳐보면 된다. 부록 마지막에 실린 ILOC 연산 요약(opcode summary)을 한국어로 정리한 것이다.

일반 연산 모음

제어 흐름 모음