Cranelift 레지스터 할당기(regalloc.rs)의 정확성을 보장하기 위해, 추상 해석 기반의 기호적 체커를 만들고 이를 퍼징 오라클로 활용한 방법을 설명한다.
이 글은 Cranelift에 관한 3부작 시리즈의 마지막 글이다. 첫 번째 글에서는 전체 맥락과 명령 선택(instruction selection) 문제를 다뤘고, 두 번째 글에서는 신중한 알고리즘 설계를 통해 컴파일러 성능을 끌어올리는 방법을 깊게 파헤쳤다.
이번 글에서는 모든 컴파일러 프로젝트에서 아마도 가장 중요한 측면인 정확성(correctness) 을 어떻게 엔지니어링하고 보장하려 노력하는지 살펴보려 한다. 컴파일러는 보통 복잡한 괴물이다. 합리적인 성능을 얻으려면 상당히 복잡한 분석을 수행하고, 임의의 프로그램을 그 의미를 보존하는 방식으로 조심스럽게 변환해야 한다. 특히 컴포넌트 사이의 틈새에서 미묘한 코너 케이스를 놓치거나 실수하기 쉽다. 그럼에도 올바른 코드 생성은 필수 인데, 잘못된 컴파일(miscompilation)의 결과는 잠재적으로 너무나 심각하기 때문이다. 시스템 스택의 더 높은 수준에서 우리가 제공하는 (보안 관련이든 아니든) 사실상 모든 보장은 “컴퓨터가 우리가 작성한 소스 코드를 충실히 실행할 것”이라는 (아주 합리적인!) 가정에 의존한다. 컴파일러가 코드를 다른 것으로 번역해버리면, 그 모든 보장은 무너진다.
이 위험을 줄이기 위해 좋은 엔지니어링 원칙을 적용하는 방법이 있다. 매우 강력한 기법 중 하나는 “결과를 확인(check)하는 것이 보통 계산(compute)하는 것보다 쉽다”는 통찰에서 출발한다. 임의로 많은 입력을 생성하고, 그 입력에 대해 컴파일러(또는 다른 프로그램)를 실행한 뒤, 출력을 검사하면 “모든 입력에 대해 컴파일러가 올바른 출력을 만든다”는 주장에 대한 통계적 근사 에 도달할 수 있다. 더 많은 무작위 입력을 시도할수록 이 주장은 더 강해진다. 이 기법은 퍼징(fuzzing) 과 프로그램 특화 오라클(oracle) 로 알려져 있으며, 버그를 찾아내는 그 기묘한 힘에 대한 장문의 찬가를 쓸 수도 있겠다(이미 많은 사람이 써왔다).
이 글에서는 레지스터 할당기 regalloc.rs의 정확성을 보장하기 위해, 특정 레지스터 할당 결과에 대해 추상 해석(abstract interpretation)으로 정확성을 증명하는 기호적 체커(symbolic checker)를 개발한 방법을 다룬다. 이 체커를 퍼징 오라클로 사용하고, 레지스터 할당기만을 대상으로 한 집중 퍼징 타깃으로 구동함으로써, 흥미롭고 미묘한 버그들을 발견할 수 있었고, 할당기의 견고성에 대해 상당히 높은 신뢰를 얻을 수 있었다.
본격적으로 들어가기 전에 몇 가지 기본을 짚고 가자. 가장 중요하게는: 레지스터 할당 문제(register allocation problem)는 무엇이며, 무엇이 이를 어렵게 만드는가?
일반적인 프로그래밍 언어에서 프로그램은 스코프 내에 임의 개수의 변수나 값을 둘 수 있다. 이는 매우 유용한 추상화다. 값들을 어디에 저장할지 걱정하지 않아도 될 때 알고리즘을 기술하기 가장 쉽기 때문이다.
예를 들어 다음과 같은 프로그램을 쓸 수 있다:
cvoid f() { int x0 = compute(0); int x1 = compute(1); // ... int x99 = compute(99); // --- consume(x0); consume(x1); // ... consume(x99); }
프로그램의 중간 지점(--- 표시)에는 int 크기의 값 100개가 계산되어 이후에 사용된다. 컴파일러가 이 함수의 머신 코드를 만들 때, 이 값들은 어디에 저장되는가?
값이 몇 개 되지 않는 작은 함수라면, 모든 값을 CPU 레지스터에 넣기 쉽다. 하지만 대부분의 CPU에는 정수 저장을 위한 범용 레지스터가 100개나 있지 않다1. 일반적으로 대부분의 언어는 지역 변수 개수에 제한을 두지 않거나, 두더라도 CPU 레지스터 수보다 훨씬, 훨씬 높은 제한을 둔다. 따라서 (x86-64에서 약 16개, aarch64에서 약 32개처럼) 동시에 사용되는 값이 그 정도를 넘어가는 경우에도 확장 가능한 접근이 필요하다.
아주 단순한 답은 각 지역 변수에 대해 메모리 위치를 할당하는 것이다. 사실 이는 C의 프로그래밍 모델이 제공하는 것과 정확히 같다. 위의 xN 변수들은 의미적으로(semantically) 메모리에 존재하며 &xN 주소도 취할 수 있다. 이렇게 하면 그 주소들이 스택 의 일부임을 알게 된다. 함수가 호출되면 스택에 스택 프레임(stack frame) 이라는 새 영역을 할당하고 이를 지역 변수 저장에 사용한다.
하지만 여기서 멈추기엔 너무 아쉽다! 지역 변수에 실제로 연산을 수행할 때 어떤 의미가 되는지 생각해보자. 두 지역 변수를 읽어 더한 뒤, 그 결과를 세 번째에 저장한다고 하자:
cx0 = x1 + x2;
대부분의 CPU는 메모리 내 값 두 개를 읽고 메모리에 세 번째 결과를 쓰는 명령을 제공하지 않으므로, 머신 코드로는 대략 다음처럼 해야 한다:
ld r0, [address of x1]
ld r1, [address of x2]
add r0, r0, r1 // r0 := r0 + r1
st r0, [address of x0]
이 방식으로 컴파일하는 것은 거의 결정할 게 없기 때문에 매우 빠르다. 예를 들어 변수 참조는 항상 메모리 로드가 된다. 실제로 이것이 “베이스라인 JIT 컴파일러”가 흔히 동작하는 방식이다. 예컨대 SpiderMonkey의 JS/Wasm JIT에서 베이스라인 티어(매우 매우 빠르게 그럴듯한 코드를 만드는 것이 목적)는 JS 바이트코드나 Wasm 바이트코드의 값 스택과 1:1로 대응되는 값 스택을 메모리에 유지한다. (코드는 여기에서 볼 수 있다. 실제로는 오퍼랜드 스택 최상단의 가장 최근 값 몇 개는 고정 레지스터에 두고, 나머지는 메모리에 둔다.)
하지만 불행히도, 매 연산마다 메모리에 여러 번 접근하는 것은 매우 느리다. 게다가 값이 생성된 직후 곧바로 재사용 되는 경우가 많다. 예를 들어:
cx0 = x1 + x2; x3 = x0 * 2;
x0로 x3를 계산할 때, 방금 메모리에 저장한 x0 값을 즉시 다시 메모리에서 로드해야 할까? 더 똑똑한 컴파일러라면 방금 계산한 값을 기억하고 레지스터에 유지하여, 메모리를 거치는 왕복을 완전히 피할 수 있어야 한다.
이것이 레지스터 할당(register allocation) 이다. 즉, 프로그램의 값을 저장하기 위해 레지스터에 배정하는 일이다. 레지스터 할당이 흥미로운 이유는 (앞서 말했듯) CPU 레지스터 수가 프로그램 값의 수보다 적기 때문에, 어떤 값들의 부분집합을 레지스터에 둘지 선택해야 하기 때문이다. 또한 보통 여러 제약이 있다. 예를 들어 RISC 계열 CPU의 add 명령은 레지스터에서만 읽고 레지스터에만 쓸 수 있으므로, + 연산자로 사용되기 직전의 값은 레지스터에 있어야 한다. 다행히 위치 할당은 시간에 따라 바뀔 수 있어서, 머신 코드의 서로 다른 지점에서는 같은 레지스터가 서로 다른 값을 담을 수 있다. 레지스터 할당기의 임무는 메모리와 레지스터 간, 혹은 레지스터 간에 값을 어떻게 섞어 옮길지 결정하여, 필요한 시점마다 레지스터에 있어야 할 값들이 실제로 레지스터에 있도록 하는 것이다.
우리 설계에서 레지스터 할당기는 “가상 레지스터 코드(virtual-register code)” 혹은 VCode라고 부르는 거의-머신코드 형태를 입력으로 받는다. 이는 머신 명령들의 시퀀스를 갖지만, 명령이 참조하는 레지스터는 가상 레지스터이며 컴파일러는 필요한 만큼 많이 사용할 수 있다. 레지스터 할당기는 (i) 명령 내 레지스터 참조를 실제 머신 레지스터 이름으로 다시 쓰고, (ii) 필요에 따라 데이터를 섞어 옮기는 명령을 삽입한다. 이 명령들은 레지스터에서 메모리로 값을 옮기면 스필(spill), 메모리에서 레지스터로 옮기면 리로드(reload), 레지스터 간 이동이면 무브(move) 라고 한다. 레지스터에 없을 때 값이 저장되는 메모리 위치는 스필 슬롯(spill slot) 이라고 부른다.
아래는 네 개 명령으로 된 프로그램에서의 레지스터 할당 예이다:
이 할당은 두 개 레지스터(r0, r1)만 있는 머신을 대상으로 한다. 왼쪽은 가상 레지스터 로 쓴 원래 프로그램이고, 오른쪽은 실제 레지스터 만을 사용하도록 수정된 프로그램이다.
각 명령 사이에는 가상 레지스터에서 실제 레지스터로의 매핑을 적어 두었다. 레지스터 할당기의 작업은 바로(“바로”!) 이 매핑들을 계산하고, 명령의 레지스터 참조를 매핑을 통해 치환하는 것이다.
이 프로그램은 어느 시점에 세 개 의 라이브 값(이후에 쓰일 것이므로 보존해야 하는 값)을 가진다. 첫 번째와 두 번째 명령 사이에서는 v0, v1, v2가 모두 라이브다. 머신에는 레지스터가 두 개뿐이므로 라이브 값을 모두 담을 수 없고, 최소 하나는 스필해야 한다. 이것이 스택 슬롯 [sp+0]에 저장하는 스필 명령 이 들어가는 이유다.
일반적으로 레지스터 할당기는 먼저 프로그램을 분석하여 어느 프로그램 지점에서 어떤 값이 라이브인지 알아낸다. 이 라이브니스 정보와 관련 제약은 조합 최적화(combinatorial optimization) 문제를 정의한다. 각 지점에서 값들은 어딘가 에 저장되어야 하고, 제약이 선택지를 제한하며, 선택지끼리 충돌할 수 있고(예: 두 값이 동시에 같은 레지스터를 점유할 수 없음), 선택의 집합은 데이터 이동 비용이라는 비용을 유도한다. 할당기는 레지스터 할당기 종류에 따라 어떤 휴리스틱을 사용하여 이 최적화 문제를 최대한 잘 풀려 한다.
이게 정말 어려운가? 사실 구어적으로도 어렵지만, NP-완전(NP-complete)이다. 즉 최악의 경우 지수 시간의 완전탐색 알고리즘밖에 모르는 모든 다른 NP 문제만큼 어렵다는 뜻이다23. 그 이유는 이 문제가 최적 부분 구조(optimal substructure)를 갖지 않기 때문이다. 서로 간섭하지 않는 부분문제로 분해해 각각 풀고 조립하는 방식이 불가능하고, 한 지점의 결정이 함수 본문 어디에서든 다른 결정에 영향을 줄 수 있다. 따라서 최적해를 원한다면 최악의 경우 완전탐색보다 나은 방법이 없다.
최적 레지스터 할당의 좋은 근사 들은 많이 있다. 흔한 예로 선형 스캔(linear-scan) 레지스터 할당은 (코드 크기에 대해) 거의 선형 시간으로 동작한다. 더 시간을 쓸 수 있는 할당기는 더 복잡하다. 예를 들어 regalloc.rs에는 (뛰어난 동료 Benjamin Bouvier가 작성한) 선형 스캔 구현 외에도, (또 다른 뛰어난 동료 Julian Seward가 작성한) 우선순위가 더 높은 레지스터 사용을 발견하면 선택을 수정하고 개선할 수 있는 “백트래킹(backtracking)” 알고리즘이 있다.
이 알고리즘들이 어떻게 동작하는지는 여기서 크게 중요하지 않다. 중요한 것은 이들이 매우 복잡하고 제대로 만들기 어렵다는 점이다. 개념 수준이나 의사코드에서는 비교적 단순해 보이는 알고리즘도, 실제 세계의 제약이 들어오면 미묘한 고려사항이 급격히 늘어난다. regalloc.rs 코드베이스는 알고리즘 중심의 Rust 코드 약 2.5만 줄이며, 합리적인 엔지니어라면 여기에 적어도 몇 개의 버그가 있을 것이라 예상할 것이다. 게다가 레지스터 할당 버그는 프로그램의 데이터플로우 “배선”을 담당하는 요소에 생기는 문제이므로, 임의의 잘못된 결과를 만들 수 있다. 프로그램 내 임의의 값을 다른 임의의 값과 바꿔치기하면 무슨 일이든 벌어질 수 있다.
그렇다면 올바른 레지스터 할당기를 만들고 싶다. 이런 과업은 어디서부터 시작해야 할까?
“정확하다”의 의미를 나눠 생각해보면 도움이 된다. 레지스터 할당 문제는 멋진 성질이 하나 있는데, 할당 전 과 후 프로그램 모두가 잘 정의된 의미론(semantics)을 가진다는 점이다. 특히 레지스터 할당을, 무한 레지스터 머신 (원하는 만큼 가상 레지스터를 쓸 수 있음)에서 실행되는 프로그램을 유한 레지스터 머신 (CPU 레지스터 집합이 고정됨)에서 실행되는 프로그램으로 변환하는 변환이라고 볼 수 있다. 무한 레지스터 머신의 원래 프로그램이 유한 레지스터 머신의 변환된(레지스터 할당된) 프로그램과 동일한 결과를 낸다면, 올바른 레지스터 할당을 달성한 것이다.
이 동등성을 어떻게 테스트할까?
두 프로그램이 동등한지 테스트하는 가장 단순한 방법은 실행해보고 결과를 비교하는 것이다! 하나의 프로그램을 택해 임의 입력 몇 개를 고르고, 가상 레지스터 프로그램과 그 레지스터-할당 버전을 적절한 인터프리터에서 함께 실행한다. 마지막에 레지스터와 메모리 상태를 비교한다.
최종 머신 상태가 같다면 무엇을 의미할까? 이 하나의 프로그램 에 대해, 레지스터 할당기가 만든 변환이 이 하나의 프로그램 입력 에 대해 올바르다는 뜻이다. 여기에는 두 가지 단서가 있다. 첫째, 다른 입력에 대해서도 올바르다는 것이 아니다. 다른 입력은 분기를 다른 경로로 보낼 수 있고, 그 경로에서 레지스터 할당기가 오류를 도입했을 수 있다. 둘째, 다른 프로그램에 대해서는 아무것도 말해주지 않는다. 단 하나의 프로그램만 테스트한 것이다.
첫 번째 한계(한 입력에 대해서만 정확함)는 샘플을 더 많이 뽑아 완화할 수 있다. 예컨대 천 개의 임의 입력을 고르고, 퍼저처럼 제어흐름 커버리지나 “흥미로운” 행동을 최대화하도록 피드백을 주며 입력을 고를 수도 있다. 충분한 테스트 케이스가 있으면, 이 단일 레지스터 할당 결과가 올바르다는 데 어느 정도 신뢰를 얻을 수 있을 것이다.
하지만 여전히 매우 비싸다. 샘플 수가 N이면 프로그램을 N번 실행해야 한다. 단 한 번 실행도 비쌀 수 있다. 레지스터 할당을 적용한 프로그램 자체가 컴파일러나 비디오게임일 수도 있다.
프로그램을 전혀 실행하지 않고 레지스터-할당 버전이 올바른지 테스트할 수 있을까?
의외로 답은 간단하다. 실행 도메인을 바꾸면 된다. 우리는 보통 CPU 레지스터가 64비트 정수 같은 구체적인 숫자를 담는다고 생각한다. 대신 심볼(symbol) 을 담는다면 어떨까?
프로그램 값을 심볼로 일반화하면, 입력이 무엇인지 상관하지 않고도 시스템 상태를 입력의 함수로 표현할 수 있다. 예를 들어 다음 프로그램:
ld v0, [A]
ld v1, [B]
ld v2, [C]
add v3, v0, v1
add v4, v2, v3
return v4
이 다음과 같이 레지스터 할당되었다고 하자:
ld r0, [A]
ld r1, [B]
ld r2, [C]
add r0, r0, r1
add r0, r2, r0
return r0
심볼 추론이 없다면, 메모리 A, B, C에 임의 정수를 저장해 두 버전을 시뮬레이션해보고 불일치를 못 찾을 수도 있다. 하지만 가능한 모든 값을 다 돌지 않는 한 아무것도 증명하지 못한다. 반면 세 번의 로드 뒤에 r0가 (무엇이든) v0를, r1이 v1을, r2가 v2를 담는다고(심볼 값으로) 가정하고, 첫 번째 add 후 r0가 v3, 두 번째 add 후 v4를 담는다고 하면, 심볼을 맞춰봄으로써 대응을 확인할 수 있다.
이는 매우 단순한 예라서 이 접근의 통찰과 힘을 다 보여주지 못할 수도 있다. 아래에서 추상 해석(Abstract Interpretation) 을 이야기할 때 다시 돌아오자.
어쨌든, 단일 레지스터 할당 문제 인스턴스에 대해 올바르게 변환했음을 증명 할 수 있음을 보였다. 구체적으로, 우리가 생성한 머신 코드는 가상 레지스터 코드를 인터프리팅하는 것과 동일하게 실행된다. 가상 레지스터 코드를 올바르게 생성할 수만 있다면, 컴파일러는 올바르다. 훌륭하다! 더 나아갈 수 있을까?
레지스터 할당기가 항상 어떤 프로그램이든 올바르게 변환한다는 것을 사전에 증명할 수도 있다. 즉, 입력값뿐 아니라 레지스터 할당 대상 프로그램 자체에 대해서도 추상화하는 것이다.
이를 증명할 수 있다면 런타임에서 어떤 검사도 실행할 필요가 없다. 입력을 추상화하면 프로그램 실행이 필요 없듯, 프로그램까지 추상화하면 레지스터 할당기를 실행할 필요도 없다. 레지스터 할당기 가 모든 프로그램 과 그 모든 입력 에 대해 올바르다고 알 수 있기 때문이다.
하지만 이는 훨씬 더 어렵다. 실제로 가능하긴 하지만, 막대한 증명 엔지니어링 노력이 들어가며 활발한 연구 분야다. 기본적으로 컴파일러 알고리즘이 올바르다는 것을 기계적으로 검증 가능한 증명으로 작성해야 한다. 예컨대 CompCert는 C를 여러 플랫폼의 머신 코드로 올바르게 컴파일함을 증명했다. 하지만 이런 노력은 증명 엔지니어링 비용에 강하게 제약되므로, 그 자체가 주요 목표가 아닌 이상 일반 컴파일러에서는 현실적으로 어렵다.
위 모든 것을 고려해 우리는 가장 합리적인 절충안이라 믿는 방법을 택한다. 레지스터 할당기 출력에 대한 기호적 체커(symbolic checker) 를 만든다. 이는 레지스터 할당기가 정적으로 “항상 올바르다”는 주장을 하게 해주진 않지만, 각 컴파일러 실행에서 나온 결과가 올바름을 증명 하게 해준다. 그리고 이를 퍼징 오라클로 쓰면, 모든 컴파일러 실행에 대해 올바르다는 통계적 신뢰 를 쌓을 수 있다.
전체 흐름은 아래 그림과 같다:
레지스터 할당기 체커를 시스템에 추가하는 방식은 두 가지다. 첫째(왼쪽)는 “런타임 검사(runtime checking)”라 부른다. 이 모드에서는 모든 레지스터 할당 실행을 검사하고, 체커가 동등성을 검증하기 전에는 할당 결과를 사용하는 머신 코드가 실행되도록 허용하지 않는다(즉 컴파일러가 결과를 반환하지 않는다). 이는 가장 안전한 모드로, 위에서 말한 “증명된-정확한 할당기”와 같은 보장을 제공한다(“모든 프로그램에 대한 동등성”). 다만 매 컴파일에 오버헤드를 추가하므로 바람직하지 않을 수 있다. 그래서 Cranelift에서는 체커와 함께 레지스터 할당기를 실행하는 옵션을 지원하지만 기본값은 아니다.
둘째 모드는 체커를 퍼징 워크플로에 적용하는 방식이며, 우리가 일반적으로 선호해온 접근이다. regalloc.rs에는 임의 입력 프로그램을 생성해 체커를 돌리는 퍼즈 타깃이 있고, Wasmtime가 Google의 oss-fuzz 지속 퍼징 이니셔티브에 참여하는 일환으로 이를 지속적으로 실행하고 있다. 이 모드에서는 체커를 퍼징 엔진을 위한 애플리케이션 특화 오라클로 사용한다. 퍼징 엔진이 무작위 프로그램(테스트 케이스)을 생성하면, 그 프로그램에 레지스터 할당을 실행하고, 결과에 체커를 실행하여 패스/실패를 엔진에 알려준다. 퍼저는 실패하는 테스트 케이스를 사람 개발자가 디버깅하도록 표시한다. 오랫동안 문제가 발견되지 않으면(체커를 항상 실행하지 않더라도) 레지스터 할당기가 올바르다는 신뢰를 더 얻을 수 있고, 오래 돌릴수록 신뢰도는 커진다. 애플리케이션 특화 오라클은 프로그램 크래시나 잘못된 출력 같은 일반적 피드백 메커니즘보다 훨씬 강력하다. 레지스터 할당 버그는 즉시 잘못된 실행으로 나타나지 않을 수도 있고, 나타나더라도 크래시가 실제 레지스터 오할당과 명확히 연결되지 않을 수 있다. 반면 체커는 특정 명령의 특정 레지스터 사용을 가리키며 “이 레지스터가 틀렸다”고 말해줄 수 있다. 디버깅이 훨씬 매끄러워진다.
이제 특정 레지스터 할당 결과가 올바른지 검증하는 “체커”를 어떻게 만드는지 단계별로 살펴보자. 먼저 가장 쉬운 경우인 직선 코드(straight-line code)를 다룬 뒤 제어흐름을 도입한다. 끝에 이르면 코드 크기에 대해 선형 시간으로 동작하는 단순한 알고리즘을 얻게 되며, 그 단순함 덕분에 보장에 대해 합리적인 신뢰를 가질 수 있다.
앞서 실행을 기호적으로 해석하는 방식을 설명했다. CPU 레지스터가 “기호적” 값을 담는다고 보고, 각 기호가 원래 코드의 가상 레지스터를 나타내는 방식이다. 예를 들어:
mov v0, 1
mov v1, 2
add v2, v0, v1
return v2
가 다음과 같이 레지스터 할당되었다고 하자:
mov r0, 1
mov r1, 2
add r0, r0, r1
return r0
그리고 어떤 방식으로든 이들이 동등하도록 만드는 치환 집합을 찾고 싶다:
mov r0, 1
[ r0 = v0 ]
mov r1, 2
[ r1 = v1 ]
add r0, r0, r1
[ r0 = v2 ]
return r0
그런데 이 치환은 어떻게 구할까? 위에서 암시했듯이 값 대신 기호로 동작하도록 실행 의미론을 다시 써서, 코드 위를 한 단계씩 진행하며 모든 실행 을 한 번에 대표하는 표현을 얻을 수 있다. 이를 심볼릭 실행(symbolic execution)이라 하며, 아래에서 설명할 강화와 함께 추상 해석(abstract interpretation)4의 기반이 된다. 매우 강력한 기법이다.
여기서 중요한 ISA 의미론은 무엇일까? 레지스터 할당기는 프로그램의 원래 명령들을 수정하지 않기 때문에5, 각 명령은 대부분 임의의 불투명한 연산자로 이해해도 된다. 중요한 정보는 그 명령이 어떤 레지스터를 읽는지 (연산 전에)와 어떤 레지스터를 쓰는지 (연산 후)뿐이다6.
스필을 검증하고, 레지스터 간 무브를 검증하려면, 스필/리로드/무브에 대해서는 특별한 지식이 필요하다. 따라서 입력 프로그램을 기호 추론에 중요한 것만 담는 최소 ISA로 줄일 수 있다(정의는 여기에 있으며, 이 글에서는 조금 단순화한다):
Spill <스필슬롯>, <CPU 레지스터>: 레지스터의 데이터(가상 레지스터를 나타내는 심볼)를 스필 슬롯으로 복사.Reload <CPU 레지스터>, <스필슬롯>: 스필 슬롯의 데이터를 레지스터로 복사.Move <CPU 레지스터>, <CPU 레지스터>: 한 CPU 레지스터에서 다른 레지스터로 데이터 이동. (주의: 원래 입력 프로그램의 move가 아니라, regalloc이 삽입한 move만 Move로 인식한다.)Op read:<CPU 레지스터 목록> read_orig:<가상 레지스터 목록> write:<CPU 레지스터 목록> write_orig:<가상 레지스터 목록>: 어떤 임의의 연산. 일부 레지스터를 읽고 다른 레지스터에 쓴다.마지막 Op가 가장 흥미롭다. 이 명령은 해당 명령의 원래 가상 레지스터들과 레지스터 할당 후 CPU 레지스터들을 함께 담고 있다. 이는 아래에서 더 명확해지겠지만, 두 세계 간 대응(correspondence) 을 세우기 위해 둘 다 봐야 한다는 직관이 있다.
위 명령들은 레지스터 할당기가 코드를 스캔하며 편집하는 동안 만들 수 있고, 이는 직관적인 변환이다. 이렇게 추상화된 프로그램을 얻고 나면, 심볼 도메인 위에서 이를 “실행”할 수 있다. 규칙은 다음과 같다:
실제 CPU처럼 상태(state) 를 유지한다. 각 CPU 레지스터와 스택 프레임의 각 위치에 대해, (정수 값 대신) 심볼 을 추적한다. 심볼은 그 위치가 현재 어떤 가상 레지스터의 값을 담고 있음을 아는 경우 가상 레지스터 이름이 될 수 있다. 혹은 체커가 모르는 경우 Unknown, 여러 가상 레지스터 중 하나일 수 있으면 Conflicted가 될 수 있다. (Unknown과 Conflicted의 차이는 제어흐름을 다룰 때 더 분명해진다. 지금은 “그 슬롯이 어떤 값(심볼)인지 안다” 또는 “아무것도 모른다”로 추상화한다고 보면 충분하다.)
Spill, Reload, Move를 만나면, 소스 위치(레지스터 또는 스필 슬롯)의 심볼 상태를 목적지 위치로 복사한다. 이 명령들은 어떤 정수 값이든 그대로 이동시키므로, 소스에 대해 모든 실행에서 성립하는 심볼 지식이 있다면 목적지로 확장할 수 있다.
Op를 만나면, 검사한 뒤 업데이트한다:
각 읽기(read) 레지스터(입력)에 대해, 주어진 CPU 레지스터(할당 후 위치)에 저장된 심볼 값을 확인한다. 그 심볼이 원래 명령이 사용한 가상 레지스터와 일치하면, 할당기는 이 사용 지점에 해당 가상 레지스터의 값을 올바르게 전달한 것이므로 할당은 정확 하다(프로그램 데이터플로우를 보존). 일치하지 않으면 체커 오류를 보고하고 레지스터 할당기 버그를 찾으면 된다. 우리는 이게 확실히 버그임을 안다(즉, 오탐이 없음). 어떤 저장 위치에 심볼을 부여하는 것은 그 위치가 모든 실행에서 해당 가상 레지스터 값을 담는다는 것을 증명했을 때뿐이기 때문이다.
각 쓰기(write) 레지스터(출력)에 대해, 해당 CPU 레지스터에 저장된 심볼 값을 (할당 전) 가상 레지스터로 설정한다. 즉 각 write는 심볼을 생성 하며, 이 심볼은 스필/리로드/무브로 프로그램을 따라 흐르다가 소비자에 도달한다.
이게 전부다! 점프가 없는 직선 코드에 대해서는 이 규칙이 정확히 맞다는 것(오탐/미탐이 없음)을 비교적 간단히 증명할 수 있다. 귀납법으로 가능하다. 어떤 명령 전의 심볼 상태가 정확하다면, 위 규칙은 구체 실행이 수행하는 데이터 이동을 그대로 부호화하고 있으므로, 명령 후의 심볼 상태도 정확하게 업데이트된다.
또한 이는 선형 이다. 직선 코드에 대해 단 한 번 스캔하면 되므로 매우 빠르다. 레지스터 할당기가 스필/리로드/삽입 무브에 대한 정보를 제공하고, 다른 모든 명령에 대해 할당 전/후 레지스터를 모두 알려주기 때문에 가능하다. 만약 이런 힌트가 없고 머신 명령만 본다면 어떨까? 그 경우 로드/스토어/무브가 원래 프로그램에서 온 것인지 할당기에서 온 것인지 구분할 수 없다. 연산자 그래프와 연결성만 남고, 그래프 동형(graph isomorphism) 문제를 풀어야 한다. 훨씬 어렵고 느리다.
그럼 끝일까? 아직 아니다. 지금까지는 직선 코드만 고려했다. 점프가 나오면 어떻게 될까?
제어흐름이 분석을 흥미롭게 만드는 이유는 여러 가능성 을 허용하기 때문이다. 다음처럼 if-then-else 패턴(종종 모양 때문에 “제어흐름 다이아몬드”라 부름)을 생각해보자:
기호적 분석이 왼쪽 분기에서는 r0의 상태가 A, 오른쪽 분기에서는 B라고 결론냈다고 하자. 두 경로가 다시 합쳐진 아래 블록에서 r0는 어떤 상태인가?
정확한 답을 주려면 “술어화(predicate)” 즉 다른 프로그램 상태에 조건을 달아 답을 표현해야 한다. 예컨대 if 조건을 불리언 타입의 어떤 심볼 C로 안다면, 추상 표현 언어를 만들어 if C { A } else { B } 같은 형태로 쓸 수 있다.
하지만 이는 곧 감당 불가능해진다. 루프가 있는 프로그램은 무한한 심볼 표현으로 이어질 수 있다. (심볼 표현이 입력보다 더 커질 수 있고, 루프를 도는 순환 의존이 있으면 무한히 커질 수 있다.) 루프가 없는 비순환 제어흐름만 있어도, 경로 민감(path-sensitive) 심볼 표현은 프로그램 크기에 대해 지수적으로 커질 수 있다. N개의 기본 블록을 가진 루프 없는 CFG는 블록을 통과하는 경로가 O(2^N)개일 수 있고, 완전히 정확한 심볼 표현은 각 경로의 효과를 모두 담아야 한다.
따라서 근사 가 필요하다. 추상 해석은 프로그램 행동을 손실 없이 완전히 정확하게 포착할 필요가 없다. 예를 들어 정수 변수의 가능한 부호(양/음/미정)만 추적하는 추상 해석도 있다. 즉, 계산 가능성을 위해 요약하고 상세를 버리는 것은 괜찮다. 그렇다면 여러 가능성이 있을 때 상태를 어떻게 “병합”할까?
이를 아주 유용하게 포착하는 수학적 구조가 있다: 격자(lattice)이다. 격자는 원소들의 집합과 그 사이의 부분순서(partial order) , 최소 원소 “bottom”과 최대 원소 “top”, 두 원소의 “가장 큰 하한”을 구하는 연산인 “meet”, “가장 작은 상한”을 구하는 “join”을 가진다.
(그림 출처: Wikimedia, CC BY-SA 3.0)
격자의 매우 유용한 성질은 meet와 join 병합 연산이 교환 가능(commutative), 결합 가능(associative), 반사적(reflexive) 이라는 점이다. 즉 결과는 처리 순서나 중복과 무관하게 “섞어 넣은 원소들의 집합”에만 의존한다. 여러 원소의 meet는 처리 순서가 아니라 원소들의 집합에만 의존한다.
이게 왜 유용할까? 우리의 분석 상태—구체적으로는 CPU 레지스터와 스필 슬롯에서 심볼 가상 레지스터로의 맵—를 격자 원소로 보고, 상태들을 병합하는 “meet 함수”를 정의하면, 루프가 있는 프로그램까지 포함하여 모든 프로그램에 대해, 분석 크기가 무한히 커지지 않는 방식으로 분석을 수행할 수 있다. 이를 “모든 경로에 대한 meet(meet-over-all-paths)” 해라고 하며, 오늘날 컴파일러가 수행하는 표준 데이터플로우 분석(dataflow analysis) 방식이다7.
프로그램 분석에서 격자가 “병합”을 유용하게 표현하는 방법은, 격자의 순서 관계(위 그림의 화살표)를 한 상태가 다른 상태보다 더 정밀한지(더 많은/적은 지식을 담는지)로 해석하는 것이다. “top”에서 시작하면 아무거나 가능하고 아무것도 모른다. 이후 점점 더 정밀한 상태로 이동한다. 한 상태가 다른 상태보다 “작다”는 것은, 다른 상태가 담는 모든 제약에 더해 추가 제약까지 담는다는 뜻이다. 두 상태의 가장 큰 하한을 구하는 meet 연산은, 두 입력이 가진 지식을 모두 담되 그 이상은 담지 않는 상태를 준다8.
임의 CFG에서 분석을 수행하는 일반적 접근은 다음과 같다:
이 방식으로 프로그램의 어떤 경로에 대해서도 명령 의미론을 만족하는 데이터플로우 해를 찾는다. 완전히 정밀하지 않을 수는 있지만(루프 포함 실행을 완전히 정밀하게 포착하는 것은 종종 불가능하고, 제어흐름이 많은 프로그램에서는 비현실적임), 건전(sound) 하다. 즉 분석 결과로부터 우리가 주장하는 바는 항상 올바르다.
이제 어떤 프로그램에 대해서도 레지스터 할당기 출력을 검사하는 데 필요한 모든 조각을 갖췄다. 직선 코드에서는 머신 상태를 기호적으로 모델링하여 레지스터 할당 오류를 정확하게(오탐/미탐 없이) 탐지할 수 있었다. 이어서 제어흐름에 대한 표준 정적 분석 접근을 논의했다. 둘을 어떻게 결합할까?
답은 기호적 레지스터 상태 에 대한 격자 를 정의하고, 위에서와 같은 명령 단위 의미론을 고정점 데이터플로우 분석으로 수행하는 것이다. 간단히 말해, 각 저장 위치(CPU 레지스터 또는 스필 슬롯)에 대해 다음과 같은 격자를 둔다:
Unknown 상태는 “top” 격자 값이다. 분석이 아직 수렴하지 않았거나(또는 아직 write가 없어서) 레지스터에 무엇이 있는지 모른다는 뜻이다.
Conflicted 상태는 “bottom” 격자 값이다. 두 개 이상의 심볼 정의가 병합되었다는 뜻이다. 어떤 술어화나 루프 요약으로 둘을 함께 표현하려 하지 않고, 그냥 포기하고 “나쁜 값”을 나타내는 상태로 내려간다. 이는 사용되지 않는 한 체커 오류가 아니다. 언제든 정상 값으로 덮어쓸 수 있다. 하지만 이 값이 명령의 소스로 사용되면 오류를 보고한다.
meet 함수는 매우 단순하다. 두 레지스터는 같은 레지스터가 아니면 meet 결과가 Conflicted가 된다. Unknown은 무엇과 meet하든 상대를 만든다. Conflicted는 전염성이 있어 어떤 상태와 meet해도 Conflicted다.
앞서 분석 상태는 단일 심볼 상태가 아니라 레지스터/스필슬롯에서 심볼 상태로의 맵 이라고 했다. 그러므로 우리의 격자는 각 저장 위치 상태들의 곱(product)이고, 심볼을 위치별로 meet한다. (결과 맵은 모든 meet 입력에 공통으로 존재하는 키만 포함한다. 즉 도메인의 교집합을 취한다.)
이 분석 상태와 meet 함수를 정의했으면, 데이터플로우 분석 루프를 돌려 수렴시키고 오류를 찾으면 끝이다!
이게 전부다
짧게 말하면, 그렇다. 상당히 미묘한 버그들을 찾아낼 수 있다!
regalloc.rs 체커의 이점은 두 가지다:
실제 버그를 찾아냈다. 위 예에서는 참조 타입(정밀 GC 루팅) 지원에서 개념적 오류가 있었다. 어떤 경우에는 포인터 타입 값에 대해 스필 슬롯이 할당되었지만 실제로 사용되진 않았는데, 그 스필 슬롯이 GC에 제공되는 스택맵(포인터 타입 스필 슬롯 목록)에 추가될 수 있었다. 이 버그는 특정 조건이 필요하다. 레지스터 압박이 충분히 커서 가상 레지스터에 스필 슬롯을 할당해야 하지만, 이후 (드문) 코드 경로에서 실제 스필은 필요 없게 되는 경우(레지스터가 가용해짐)를 타야 한다. 우리는 GC(Wasm 참조 타입)에 대한 다른 수작업 테스트들에서는 이를 전혀 맞닥뜨리지 못했다. Cranelift 백엔드를 구동하는 SpiderMonkey의 WebAssembly 테스트 스위트에는 꽤광범위한테스트도 있었는데 말이다. 퍼저는 전체 커버리지를 향해 탐색해 이 희귀 경로에 도달했고, 체커가 오류를 발견하도록 했다.
새 레지스터 할당기를 개발할 때 골드 스탠더드 테스트로 기능한다. 선형 스캔 할당기 개발 중(참조 타입/정밀 GC 루팅 지원은 백트래킹 할당기보다 조금 늦게 들어왔다), 체커 피드백은 많은 실제 문제를 찾아내어 더 빠르고 자신 있게 진행할 수 있게 했다.
개별 레지스터 할당 실행을 검증하는 체커에 대한 선행 연구를 찾기는 의외로 어렵다. 완전 검증된 컴파일러는 여러 개가 존재하며, CompCert와 CakeML은 현실적인 언어(C와 ML)를 컴파일할 수 있는 두 예다. 이 컴파일러들은 알고리즘 자체가 증명되어 있어 레지스터 할당기도 완전 검증되어 있으며, 개별 컴파일 결과에 대해 체커를 돌릴 필요가 없다. 하지만 이런 엔지니어링 노력은 체커 작성보다 훨씬 크다(후자는 Rust 약 700줄).
CakeML의 레지스터 할당 정확성 증명 접근은 Tan 등 저자의 “The Verified CakeML Compiler Backend”(J. Func Prog 29, 2019)에 설명되어 있다. 이들은 유효한 그래프 컬러링 또는 “퍼뮤테이션”(프로그램 값을 저장 슬롯에 매핑)이 주어지면 컴파일이 올바르도록 문제를 잘 인수분해한 것으로 보인다. 이는 할당 전후의 데이터플로우 동등성이라는 핵심을, 할당기 상세(그래프 컬러링 알고리즘)와 분리해 추론할 수 있게 해준다.
증명-생성(proof-producing) 컴파일러도 존재한다. 예를 들어 Crellvm은 여러 LLVM 패스를 확장하여 변환된 프로그램과 함께 (기계 검사 가능한) 정확성 증명을 생성한다. 개념적으로는 우리의 레지스터-할당 체커와 같은 수준이다. 단일 컴파일러 실행을 검증하지만, 완전한 사전 증명보다 만들기 쉽다. 다만 이 노력은 아직 레지스터 할당을 다루는 것으로 보이진 않는다.
Rideau와 Leroy의 “Validating Register Allocation and Spilling”(CC 2010)은 “한 번에 영원히(once and for all)” 정확성 증명과 “번역 검증(translation validation)” 체크를 구분하는 유사한 분류를 제시하고, 후자를 제공한다. 하지만 그 검증기는 동등성 제약 집합을 만들고 이를 푸는 꽤 복잡한 전달 함수(transfer function)를 정의한다. 특히 원래 프로그램의 load/store/move와 구분되는, spills/reloads/삽입 moves에 대한 할당기 힌트를 활용하지 않는 것으로 보이며, 이 힌트가 없으면 훨씬 일반적이고 복잡한 데이터플로우 동등성 스킴이 필요하다.
Nandivada 등 저자의 “A Framework for End-to-End Verification andEvaluation of Register Allocators”(SAS 2007)는 물리 레지스터 내용을 가상 레지스터(또는 “pseudo”) 심볼로 인코딩해 post-regalloc IR로 만들고 이를 타입체킹하는, 우리의 체커와 매우 유사한 시스템을 설명한다. 그 타입체커는 우리 체커가 찾는 것과 같은 종류의 regalloc 오류를 찾아낼 수 있다. 따라서 접근은 대체로 동등하며, 주요 차이는 우리가 전용 IR에서 타입체킹으로 풀지 않고 독립적인 정적 분석으로 구현했다는 점이다.
이 글로 지난 1년 동안 Cranelift의 새 백엔드를 구성하는 모든 조각을 개발하며 우리가 해온 작업을 설명하는 3부작(1, 2)이 마무리된다! 개인적으로 매우 흥미롭고 교육적인 여정이었다. 일반적으로 더 많이 가르치고 연구하는 “미들엔드”(IR 수준 최적화)와는 구분되는, 백엔드에서 해결해야 할 흥미로운 문제들의 완전히 새로운 세계를 발견했다. 또한 빠른 컴파일에 대한 초점은 흥미로운 변주이며, 충분히 연구되지 않았다고 믿는다. 더 정밀한 분석과 더 좋은 코드 생성을 정당화하기 위해 점점 더 복잡한 기법을 도입하는 것은 쉽다. 반면 빠른 컴파일을 위한 설계 트레이드오프에서 얻을 수 있는 이득은 더 주관적이고 워크로드에 더 의존적이다.
이 글들이 우리의 설계 결정에 담긴 사고를 비추는 데 도움이 되길 바란다. 하지만 우리의 작업은 아직 끝나지 않았다! 2021년 Cranelift 작업 로드맵에는 더 높은 컴파일러 성능과 더 좋은 코드 품질을 위해 논의해온 여러 아이디어가 담겨 있다. 다가오는 해에 이를 더 탐구하는 것이 기대되며, 어쩌면 또 다른 블로그 글로 이어질지도 모른다. 그때까지, 즐거운 컴파일링을!
이 글에 대한 토론은 Zulip 인스턴스의 이 스레드로 참여해 달라.
Reddit의 /u/po8에게, 내가 반영한 여러 제안에 대해 감사한다. bjorn3에게도 여러 제안에 감사한다. 마지막으로 Fernando M Q Pereira에게, SAS 2007의 그의 논문에서 매우 유사한 아이디어를 제안하고 있음을 알려준 것에 감사한다(관련 연구 섹션에 추가했다). 어떤 피드백이든 환영한다!
1
왜 CPU의 레지스터 수는 제한되어 있을까? 이 상한은 대부분 ISA 인코딩 제한 때문이다. 명령어 안에서 특정 레지스터 소스/목적지를 지정할 수 있는 비트 수는 제한되어 있다. CPU 설계자가 레지스터 수를 정할 때, 더 많이 제공하면(어느 정도까지는) CPU가 한 번에 더 많은 상태를 담을 수 있어 성능이 좋아지지만, 코드 크기와 CPU 복잡도 증가라는 비용도 커진다.
컴퓨터 아키텍트의 여담: 레지스터 리네이밍(register renaming) 덕분에 현대의 고성능 비순차(out-of-order) CPU는 훨씬 더 많은 물리 레지스터를 갖는다. 어떤 프로그램 지점에서 아키텍처 레지스터 이름은 리네이밍 하드웨어(흔히 레지스터 할당 테이블(RAT)이라고 부름)가 물리 레지스터로 매핑한다. 그럼에도 ISA 인코딩 제약은 어떤 시점에 아키텍처 이름을 가진 레지스터 수를 제한한다. 레지스터 리네이밍의 존재는 “레지스터가 그렇게 많은데 왜 그렇게 적은 레지스터로 리네임하나?” 같은 혼란을 야기하기도 한다. 답은, 그들을 모두 가리킬 비트가 더 있었다면 훨씬 더 잘할 수 있었을 것이라는 점이다! 아키텍처 표준화도 이유다. PRF(물리 레지스터 파일)가 커질 때마다 코드를 다시 컴파일하고 싶진 않다. “x86-64는 정수 레지스터가 16개”라고 단정하는 편이 단순하다10.
2
다만 최악의 경우 지수 시간이 최선 인지 우리는 모른다. 많은 컴퓨터 과학자들은 그렇다고 의심하지만, 이는 유명한 P=NP 문제이며, 만약 풀면 백만 달러를 받는다.
4
추상 해석은 Radhia Cousot와 Patrick Cousot가 1977년 POPL의 기념비적 논문 “Abstract interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints”에서 처음 소개했다(pdf).
5
무브 제거(move elimination)를 제외하면 그렇다. 하지만 지금은 무시해도 된다. 나중에 이를 고려하도록 추상 해석 규칙을 적응시키는 것도 가능하다.
6
regalloc.rs에는 “레지스터를 수정(modifies)하는” 명령 개념도 있는데, 이는 read와 write를 결합한 것과 비슷하지만 둘 다 같은 레지스터로 매핑되어야 한다는 점이 다르다. 여기서 설명하려는 핵심에는 본질적이지 않으므로 생략한다.
7
이 데이터플로우 분석 접근은 Gary Kildall이 1973년 POPL 논문 “A unified approach to global program optimization”에서 제안했다. (그는 마이크로컴퓨터 OS CP/M—DOS의 전신—을 만든 것으로 더 잘 알려져 있을지도 모른다.) Kildall의 데이터플로우 분석은 수년 전 Fran Allen이 발명한 제어흐름 그래프 아이디어 위에 구축된다. 그녀의 1970년 논문 Control Flow Analysis에서는 구간(interval) 기반 데이터플로우 분석을 제안했는데, 이는 오늘날 알려져 있고 사용되는 또 다른 주요 접근이다.
8
여기서 방향성에 대해 다소 모호하게 말했음을 유의하자. “더 제약됨/더 정밀함”은 무엇을 의미할까? 실제로 분석에는 두 방향이 있으며, 이는 부정확성(imprecision)을 어떻게 다루는지와 관련이 있다. “may 분석”(또는 widening 분석)은 프로그램이 할 수 있는 일을 계산한다. 보통 “공집합” 같은 것에서 시작해—변수의 가능한 값이 없음, 문장이 부작용 없음, 레지스터가 아무것도 담지 않음—가능한 모든 가능성 을 합치는 합집합 류 meet 연산으로 확장한다. 실제 프로그램 행동은 이 가능성들의 부분집합이다. 반대로 “must 분석”(또는 narrowing 분석)은 프로그램이 반드시 하는 것만 계산한다. 보통 “우주집합”에서 시작해 교집합 류 meet 연산으로 줄여나간다. 실제 프로그램 행동은 이 분석이 설명하는 것의 상위집합이다. 일반적으로 둘 다를 동시에 가지기는 어렵다. 분석이 완전히 정밀할 수 없기 때문이다.
관례상 분석 값은 항상 “top”에서 시작해 meet로 격자를 내려가며 수렴하게 하지만, 격자의 순서 관계를 뒤집고 meet/join을 바꾸면 또 다른 격자가 되므로, “bottom”에서 시작해 join으로 올리는 방식도 가능하다.
9
사실 “거의” 전부다. 예상했겠지만 한 가지 중요한 세부를 생략했다. 참조 타입(reference types) 과 정밀 가비지 컬렉션(precise GC) 처리를 어떻게 하느냐이다. 정밀 GC 루팅은 각 레지스터와 스필슬롯에 대해 특정 종류의 타입 정보 를 추적해야 한다. 구체적으로 각 저장 위치가 GC가 추적해야 할 포인터 를 담는지 여부다. 많은 응용에서 “정밀함”이 중요하며, 이는 실제로 포인터가 있을 때만 포인터가 있다고 말할 수 있고, 포인터를 담는 모든 레지스터를 반드시 포함해야 함을 뜻한다. 정밀함이 중요한 이유는, GC는 자신이 추적한 루트 포인터가 유효한 객체를 가리킨다고 가정하므로(오탐이 나쁘다), 그리고 이동형 GC라면 객체를 재배치할 때 모든 포인터를 알아야 하기 때문이다(미탐도 나쁘다).
우리 변형 문제에서는 이 정보가 세이프포인트(safepoint) 에서 필요했다. 즉 GC가 호출될 수 있는 지점이다. (프로그램 모든 지점에서 GC 호출을 대비하는 것은 너무 비싸다.) 또한 레지스터가 아니라 스택(즉 스필슬롯)의 포인터만 추적할 수 있는 GC도 지원해야 했다. 그래서 세이프포인트 주변에 추가 스필 을 유도하여, 포인터가 레지스터가 아닌 스택에서만 라이브하도록 해야 했다.
이를 검사하기 위해, 우리는 추상 값 격자를 확장하여 각 가상 레지스터가 포인터 타입인지 아닌지를 기록했다. 그리고 각 세이프포인트에서 (i) 스필슬롯에 있는 모든 실제 포인터 타입 값이 GC에 제공되는 스택맵에 나열되어 있는지 확인하고, (ii) 스택맵에 나열되지 않은 다른 포인터 타입 스택 위치는 Unknown 상태로 지웠다. 왜 후자가 필요할까? 포인터 타입 값이 스택 슬롯에 있더라도 “죽은(dead)” 값(다시 사용되지 않음)일 수 있으므로 스택맵에서 생략하는 것이 합법적이다. 제외됐다고 즉시 오류를 내기보다는, 나중에 그 값을 사용하려 하면 그것이 부적절함을 보장하도록 만든다.
10
일부 아키텍처는 컴파일러에게 어떤 형태의 레지스터 리네이밍을 맡기기도 한다. 예를 들어 Intel Itanium(IA-64)는 루프를 위한 “회전 레지스터 참조(rotating register reference)”라는 독특한 기능이 있었고, 컴파일러가 정수 128개와 부동소수점 128개 레지스터 전체를 관리하도록 했다. 현대 GPU 역시 컴파일러가 관리하는 수천 개의 “레지스터”를 가진다.
