컴파일러 중간 표현(IR)의 설계 공간에서, 로컬 정보만으로 의사결정을 가능하게 하는 접근을 중심으로 CFG, 레지스터 기반 IR, SSA/SSI, 노드의 바다, 명세의 실체화 등 다양한 아이디어를 살펴본다.
컴파일러 중간 표현(intermediate representation, IR)의 설계에 대해 나는 생각이 정말 많다. 이 글에서는 그 아이디어들 일부와, 내가 왜 그것들이 중요하다고 생각하는지 전달해 보려고 한다.
전체를 관통하는 생각은 오직 로컬 정보만으로도 의사결정을 내릴 수 있게 하는 것 이다.
이는 몇 가지 서로 다른 형태로 나타난다. 여기서는 트레이스처럼 동작하는 것(트레이싱, 트레이슬릿, 베이직 블록 버저닝 등)보다는, 한 번에 메서드 하나를 컴파일한다고 가정하겠다.
함수는 보통 어떤 형태로든 제어 흐름(control-flow)을 가진다: if, while, for, 그리고 함수 내부에서 여기저기 점프하는 다양한 형태들. 고급 제어 흐름 구문을 가진 언어에서의 예시 함수를 보자:
int sumto(int n) {
int result = 0;
for (result = 0; n >= 0; n -= 1) {
result += n;
}
return result;
}
대부분의 컴파일러는 여러 겹으로 중첩된 표현식을 가진 이 for를 단순한 비교와 점프로 분해한다. 컴파일러에서 점프 타겟을 해석하기 위해 라벨(여기서는 콜론으로 끝나는 단어들) 같은 개념을 둘 수 있다:
int sumto(int n) {
entry:
int result = 0
header:
if n < 0, jumpto end
result = result + n
n = n - 1
jumpto header
end:
return result
}
이건 일종의 의사 어셈블리 언어처럼 보인다. 고수준 언어 기능들이 더 작은 여러 명령으로 분해되어 있다. 또한 라벨이 붙은 구간들 사이에 암묵적 fallthrough가 있다(예: entry에서 header로).
이런 점들을 언급하는 이유는, 이 글의 다른 아이디어들과 마찬가지로 이것들도 IR 설계 공간의 한 지점이기 때문이다. 이렇게 코드를 표현하는 것은 당연한 전제가 아니라 명시적인 선택이다. 예를 들어 entry 끝에 jumpto header를 추가해 점프를 명시적으로 만들 수도 있다.
그 명령을 추가하는 순간 코드는 위치 독립(position-independent)이 된다: entry에서 시작하기만 하면, 라벨 사이의 코드 조각들은 어떤 순서로 배치해도 된다. 이름으로 참조되며 암묵적 순서 요구가 없다.
이건 임의적으로 보일 수도 있지만, 최적화기에 더 큰 유연성을 준다. 예컨대 어떤 최적화 규칙이 block4로 가는 분기가 드물게 수행될 것이라고 판단하면, 더 뜨거운(hot) 코드가 단일 캐시 라인에 놓이도록 그 블록을 함수의 끝쪽(혹은 다른 페이지!)으로 자유롭게 재배치할 수 있다.
명시적 점프와 라벨은 코드를 엄격히 선형인 어셈블리에서 control-flow graph (CFG)로 바꾼다. 내부 제어 흐름이 없는 코드의 연속을 _basic block_이라 부르며, 이는 그래프의 정점(vertex)이 된다. 방향 간선(directed edge)은 블록 간 점프를 나타낸다. 예를 들어 아래의 투박한 GraphViz 표현을 보라:
각 베이직 블록은 그래프에서 자체 노드를 가지며, 노드 간의 방향 간선은 점프를 나타낸다.
우리는 사실 extended basic blocks (EBB)를 보고 있는 셈인데, 이는 블록당 제어 진입은 하나만 허용하지만 제어 탈출은 여러 개 허용한다. 위 코드를 엄격한 베이직 블록 표현으로 만들면 텍스트로는 대략 이렇게 된다:
int sumto(int n) {
entry:
int result = 0
condbranch n < 0, iftrue: end, iffalse: header
header:
result = result + n
n = n - 1
condbranch n < 0, iftrue: end, iffalse: header
end:
return result
}
각 블록이 정확히 하나의 terminator(제어 흐름 명령)를 가지며 (이 경우) 타겟이 0개 또는 2개인 것을 볼 수 있다.
EBB와 일반 베이직 블록의 장단점과 문제에 대해서는 의견이 갈린다. 내가 보는 대부분의 컴파일러는 일반 베이직 블록을 사용한다. 어느 쪽이든 IR을 그래프 형태로 만들면 장점이 있는데, Cousot와 Cousot라는 우리가 사랑하는 파워 커플 덕분에 그래프 위에서 추상 해석(abstract interpretation)을 수행하는 방법을 알고 있고, 이를 이용해 고급 최적화기를 만들 수 있다. 예를 들어 내 글 추상 해석 입문을 보라.
어떤 IR은 스택 기반이다. 연결형(concatenative) 언어나 일부 최신 JIT 컴파일러의 경우, IR이 각 opcode가 스택에서 피연산자를 읽고 스택에 결과를 쓰는 방식으로 구성되곤 한다. 이는 Haskell이나 OCaml 같은 언어의 포인트-프리(point-free) 코딩 스타일을 떠올리게 한다.
inc = (+ 1)
이 스타일에는 암묵적으로 공유되는 상태가 있다: 스택이다. 데이터 흐름은 (push와 pop으로) 명시적이며, 명령을 재배치하려면 스택 구조가 유지되어야 한다. 이는 비로컬(non-local) 추론을 요구한다: 어떤 명령을 옮기려면 스택도 함께 재배치해야 한다.
PUSH 1
PUSH 2
ADD
반면 레지스터 기반 IR에서는 더 명시적이다. 명령은 이름 있는 입력(v0, v12 등)을 받고 이름 있는 출력을 만든다. (효과를 고려해야 한다는 점을 제외하면) 입력이 계속 정의되어 있는 한 명령을 조금 더 쉽게 이동시킬 수 있다. 로컬 변수는 존재하지 않는다. 스택도 존재하지 않는다. 모든 것이 IR “변수”다.
v1 = CONST 1
v2 = CONST 2
v3 = ADD v1 v2
제약(이름이 정의되어야 함)은 IR의 일부 다. 그런데 어떤 이름을 여러 번 정의할 수 있다면 이것은 조금 까다로워진다.
v1 = CONST 1
v2 = CONST 2
x = ADD v1 v2
x = ADD x v2
v3 = MUL x 12
v3의 명령에서 x는 무엇을 의미하는가? 어느 정의를 가리키는가? v3 = MUL x 12를 추론하려면 어떤 문맥을 계속 들고 있어야 한다. 이는 사소하지 않다. 컴파일러 작성자가 분석을 하는 동안 부가 테이블(side-table)을 계속 들고 다니며 업데이트하도록 요구하는 것은 느리고 오류가 나기 쉽다. 다행히 흥미로운 규칙들을 강제하면 그 분석 작업을 사전에 한 번의 패스로 밀어 넣을 수 있다…
Static single assignment (SSA)는 IBM의 여러 사람들에 의해 도입되었다(서로 다른 구현에 대해서는 내 블로그 글을 보라). SSA 기반 IR에서는 각 변수를 오직 한 번만 정의할 수 있다. 다른 말로 하면, 변수는 그 변수를 정의하는 명령이다1; 또는 변수와 그 정의 명령은 같은 이름으로 주소 지정된다. 앞의 예시는 SSA가 아니다. x가 두 번 정의되기 때문이다.
앞의 예시를 SSA로 바꾸면, 각 명령에 대해 다른 이름을 쓸 수 있다. 이는 unique name assumption 또는 전역 이름 속성과 관련이 있는데, 이름이 문맥에 의존하지 않는다.
v1 = CONST 1
v2 = CONST 2
x0 = ADD v1 v2
x1 = ADD x0 v2
이제 각기 다른 ADD 명령을 그것이 정의하는 변수로 식별할 수 있다. 이는 분석에서 유용하다…
continuation-passing style (CPS) 기반 IR을 언급하지 않으면 빠뜨린 꼴이 될 것이다(사실 원고 초안에서는 잊어버렸었다). IR로서 CPS는 보통 함수형 프로그램의 분석과 최적화에서 사용되는데, 예컨대 OCaml과 Racket 컴파일러에서 그렇다. 하지만 필수는 아니다. 예를 들어 MLton은 Standard ML 컴파일러에서 SSA를 사용한다.
SSA와 CPS는 대체로 같은 프로그램을 표현할 수 있지만, 서로 다른 언어(그리고 다른 컴파일러 작성자)에게 각각 자연스럽게 느껴질 수 있다. 여기서 더 말할 만한 자격이 있다고는 느끼지 않는다. 더 잘 알고 있는 견해를 원한다면 Andy Wingo의 approaching cps soup를 보라. 특히 끝부분 근처의 장점과 단점이 좋다.
CPS 이야기가 나와서 말인데, 나는 Olin Shivers와 수업을 들은 적이 있고 그는 추상 해석을 “자동화된 정리 찾기(automated theorem finding)”라고 설명했다. Lean과 Rocq 같은 정리 증명기 와 달리(원하는 성질을 손으로 증명해야 한다), 정적 분석은 프로그램 안에 이미 존재하는 흥미로운 사실을 찾아내고(그리고 최적화기는 그것들을 사용해 프로그램을 더 빠르게 만든다).
정적 분석 패스는 IR 노드에 다음 같은 작은 정보 조각을 주석으로 붙일 수 있다:
타입이 int다
값이 5다
2와 5 사이에 있다
표현식 y*z와 동치다
record_known_result 설명을 보라: A Hint for Language-Specific Runtime Function Optimization in RPython’s Meta-JIT부작용이 없다
루프 불변이다
탈출(escape)하지 않는다
…
정적 분석이 SSA 위에서 이루어진다면, 일반적으로 정적 분석이 더 쉽고 (잠재적으로) 사실을 저장하는 것도 더 쉽다. 이는 sparseness 라는 속성 때문이다. SSA가 아닌 프로그램에 대한 정적 분석은 모든 프로그램 지점 에서 모든 변수 에 대한 사실을 저장해야 하는 반면, SSA에 대한 분석은 문맥과 무관하게 모든 변수에 대한 사실만 저장하면 된다.
나는 이를 가끔 “IR을 통해 시간을 밀어 넣는다”라고 설명하곤 하지만, 그게 크게 말이 되는지는 모르겠다.
여기서 더 미묘할 수 있는 점은, 위 IR 조각을 튜플의 리스트로 표현할 수도 있다는 것이다. 이때 명령들은 다른 테이블(예: “변수 환경”)을 통해 서로 연결된다:
code = [
("v1", "CONST", 1),
("v2", "CONST", 2),
("x0", "ADD", "v1", "v2"),
("x1", "ADD", "x0", "v2"),
]
하지만 대신 각 명령마다 객체를 할당하고, 서로를 포인터로(혹은 Rust 같은 것을 쓴다면 인덱스로) 참조하게 만들 수도 있다. 그러면 서로를 직접 참조하게 되어(부가 테이블이 필요 없다) 더 빠르고 더 컴팩트할 수 있다. 출력 시에는 필요에 따라 보기 좋은 이름을 다시 만들어낼 수 있다. 그러면 최적화할 때 피연산자의 타입 정보를 직접 필드를 읽는 방식으로 조회한다(operands[N]->type 같은 것).
또 한 가지: IR에 타입 정보를 추가하기 시작하면, 분석에서 타입 정보에 대한 질문을 하게 된다. “이 명령의 타입은 무엇인가?” 같은 질문인데, 여기서 “타입”은 반격자(semilattice)를 가로지를 수도 있고, 포인터로 특정 런타임 객체를 가리킬 수도 있다. 그런 경우 올바른 질문 을 하는 것이 중요하다. 예를 들어:
Const 명령인가?Const 명령만이 특정 객체를 만들어낼 수 있는 유일한 opcode가 아닐 가능성이 크다. 예를 들어 생성된 코드에 특정 기대 포인터를 박아 넣는 GuardIsObject 같은 명령이 있다면, 타입(따라서 포인터)은 GuardIsObject 명령에서 온다.
큰 아이디어는 타입이 opcode들과는 다른 축으로 IR을 가로지르는 슬라이스를 나타내며, 그에 맞게 다뤄져야 한다는 것이다.
어쨌든 SSA는 명령에 대한 타입 정보만 저장하고, 나중에 알게 될지 모르는 정보를 IR 안에 인코딩하진 않는다. 기본 SSA만으로는 refinement를 인코딩할 좋은 방법이 없다…
Static single information (SSI) form은 명령(변수)에 대한 메타데이터를 인코딩할 새로운 방법들을 제공한다. 이는 1999년에 C. Scott Ananian이 그의 석사 논문 (PDF)에서 소개했다. (나는 Scrapscript IR 글에서도 이를 짧게 언급했다.) 다음 SSA 프로그램(의사 Python으로 표현)을 보자:
# @0
x = int(...)
# @1
if x >= 0:
# @2
return x
else:
# @4
result = -x
# @5
return result
x는 @0에서 정의되지 않았다. x는 @1에서 정의되어 있고 정수 다. 그런데 여기서 흥미로운 일을 한다: x의 런타임 값에 따라 제어 흐름을 분기한다. 우리는 이 분기를 이용해 x에 대한 새롭고 흥미로운 정보를 추가할 수 있다. sparse가 아닌 분석에서는 어떤 사실을 옆에 기록할 수 있다. 괜찮다.
# @0
x = int(...)
# @1
if x >= 0:
# @2
LearnFact(x, nonnegative)
# @3
return x
else:
# @4
LearnFact(x, negative)
# @5
result = -x
# @6
return result
데이터 흐름 분석을 할 때 @3에서는 x가 음이 아님(nonnegative)이라는 사실을, @5에서는 x가 음수(negative)라는 사실을 추적할 수 있다. 이는 멋지다. 그러면 이 함수로 들어오는 모든 경로가 양의 정수를 반환한다는 것도 알아낼 수 있다.
중요한 점은 LearnFact(x, nonnegative)가 x에 대해 기존에 알려진 타입을 덮어쓰지 않는다는 것이다. 대신 refinement다: 집합의 교집합. 격자의 meet. 두 개의 겹치는 원 Integer와 Nonnegative의 벤 다이어그램에서 가운데 겹치는 부분.
하지만 정보를 sparse하게 유지하고 싶다면, IR에 새로운 정의를 추가해야 한다.
# @0
x = int(...)
# @1
if x >= 0:
# @2
newx0 = LearnFact(x, nonnegative)
# @3
return newx0
else:
# @4
newx1 = LearnFact(x, negative)
# @5
result = -newx1
# @6
return result
이는 복잡하다(어떤 변수를 분할할지 고르고, 모든 사용처를 치환하고, SSA를 유지하기 위해 등등). 하지만 IR 안에 정보를 저장할 새로운 지점을 제공한다. 즉 newx0를 참조할 때마다 그것이 음이 아님을 알고, newx1를 참조할 때마다 그것이 음수임을 안다. 이 정보는 문맥과 무관하다!
또 한 가지: “완전한 SSI”로 가지 않고도 SSI의 이점 상당 부분을 얻을 수 있다. 모든 분기에서 모든 변수를 분할할 필요도 없고, 특별한 새 merge 명령을 추가할 필요도 없다.
좋다. 우리는 IR에 아주 sparse하게 많은 정보를 인코딩할 수 있다. 멋지다. 강력하다. 하지만 이 매우 sparse한 표현에서도 우리가 원치 않을 수 있는 정보를 암묵적으로 인코딩하고 있다는 점을 의식해야 한다: 실행 순서.
전통적인 CFG 표현에서는 명령들이 이미 스케줄링 되어 있거나, 즉 순서가 매겨져 있다. 보통 이는 원래 소스 형태에서 프로그래머가 준 순서에서 오며, 충실히 유지된다. SSA 같은 IR에서는 데이터 사용(use) 간선을 얻지만, 제어 정보는 암묵적으로 남는다. 하지만 어떤 형태의 IR은 데이터 및 제어 의존성을 모두 IR 자체 안에서 실체화(reify)하려고 한다. 그런 IR 설계 중 하나가 sea of nodes (SoN)이며, Cliff Click이 박사 과정 중에 처음 설계했다.
sea of nodes에서는 모든 명령이 그래프의 정점 하나씩을 가진다. 명령은 자신의 피연산자들에 대한 사용 간선을 가지며, 이는 데이터일 수도 있고 다른 어떤 순서 속성(제어, 효과 등)일 수도 있다. 핵심 아이디어는 IR 노드들이 기본적으로 무순서이며, 효과 분석이 많은 사용 간선을 제거한 뒤에야 순서가 매겨진다는 것이다.
Per Vognsen은 sea of nodes의 또 다른 동기 예시도 언급한다: 앞의 SSI 예시에서 LearnFact(x, nonnegative)는 n >= 0 검사 위로 유효하게 끌어올릴(hoist) 수 없다. “일반적인” IR에서는 이것이 순서에 의해 암묵적으로 보장된다. sea of nodes 세계에서는 이것이 LearnFact에서 if n >= 0로 가는 간선으로 명시적으로 표시된다. 예를 들어 Graal은 이런 LearnFact 노드를 “Pi 노드”라고 부르는 것 같다.
나는 원 논문을 다시 읽고, 현대 구현을 읽어 보고(더 이상 정확히 같은 방식으로 하진 않는 느낌이 든다), 나중에 더 써야 할 것 같다. 지금은 Cliff Click과 동료들의 Simple을 보라. Java로 된 구현과 함께 짧은 책이 있다.
설계상의 이웃으로는 value dependence graphs (VDG), value state dependence graphs (VSDG), region value state dependence graphs (RVSDG), 그리고 program dependence graphs (PDG)가 있다.
Cliff Click 이야기가 나왔으니, 예전에 그가 말한/쓴 것 중 정말 흥미롭게 들린 것을 하나 소개하겠다. 대략 “연산의 전체 의미론을 IR로 정교하게 풀어 써 두고, 최적화기가 알아서 정리하게 하라”는 것이었다. 즉 의미론을 “오픈 코드(open code)” 하거나 “인라인(inline)” 하라는 것이다.
예를 들어 나중에 특수화할 일반 덧셈 연산을 위한 코드를 내보내지 말고:
v2 = GENERIC_ADD v0, v1
대신, 로컬 언어에서 그 연산의 문서화된 의미론이 무엇이든, 그것을 그대로 복제하는 코드를 내보내라. 여기에는 낙관적인 빠른 경로도 포함될 수 있다:
v1 = TYPE_OF v0
v2 = TYPE_OF v1
if (v1 == Fixnum && v2 == Fixnum) {
v3 = FIXNUM_ADD v0, v1
}
else if (v1 == String && v2 == String) {
v4 = STRING_CONCAT v0, v1
}
else {
v5 = LOOKUP_METHOD v0, "add"
v6 = CALL_METHOD v5, v0, v1
}
v7 = PHI v3, v4, v6
이는 특수화된 rewrite 규칙이 더 적어도 될 수 있다는 장점이 있다. 상수 전파와 분기 접기(branch folding)가 이런 특수화를 “공짜로” 처리해 주기 때문이다.
이 모든 것이 전혀 특수화되지 않았을 때를 대비해, 더 가능성 높은/낮은 분기에 확률을 붙여 아웃라이닝(outlining) 힌트를 제공할 수도 있다.
물론 단점도 있다. 생성된 IR이 더 커질 수 있고, 그러면 최적화기가 느려질 수도 있다—혹은 더 나쁘게는 최종 생성 코드가 더 커질 수도 있다. 하지만 아웃라이닝, 중복 제거(함수화(functionalization?)?), 그리고 아마 다른 영리한 기법들이 여기서 도움을 줄 수 있다.
비슷하게, Maxime Chevalier-Boisvert와 Marc Feeley는 basic block versioning 맥락에서 이를 글로 설명 (PDF)한다. 런타임의 일반 덧셈 함수가 IR로 작성되어 있다면, 그 함수를 호출하는 쪽은 서로 다른 베이직 블록 문맥에서 호출함으로써 그 “너머로” 특수화할 수 있다. 이는 대체로 호출 지점 특수화(call-site specialization)를 “공짜로” 얻게 해준다. 그들의 논문 Figure 4(내가 약간 편집함)를 보라. 달러 접두 변수 이름은 컴파일러가 아는 특수 함수들을 나타내는 것 같다:
function $rt_add(x, y) {
if ($ir_is_i32(x)) { // If x is integer
if ($ir_is_i32(y)) {
var r = $ir_add_i32_ovf(x, y);
if (r)
return r;
else // Handle the overflow case
return $ir_add_f64($ir_i32_to_f64(x),
$ir_i32_to_f64(y));
} else if ($ir_is_f64(y))
return $ir_add_f64($ir_i32_to_f64(x), y);
} else if ($ir_is_f64(x)) { // If x is floating point
if ($ir_is_i32(y))
return $ir_add_f64(x, $ir_i32_to_f64(y));
else if ($ir_is_f64(y))
return $ir_add_f64(x, y);
}
// Evaluate arguments as strings and concatenate them
return $rt_strcat($rt_toString(x), $rt_toString(y));
}
이는 런타임을 처음부터 만들고 있거나, 런타임의 일부를 IR로 다시 작성하는 데 자원을 투입할 수 있다면 좋은 접근이다. 그러면 메서드 JIT에서도 함수의 (부분) 인라이닝으로 인라인된 언어 의미론을 얻을 수 있다.
지금도 이와 비슷한 방향으로 더 탐구할 만한 것이 있을 것 같고, 미래에는 더 발명될 것도 많을 것이다. 생각해 볼 만한 다른 흥미로운 개념으로는 다음이 있다:
union-find
e-graphs
ae-graphs 및 IR에서의 실체화 (또한 PLDI eqsat paper도 보라)
Webs: 어떤 “것”에 대해 모두 관련된 IR 노드들의 연결 성분(connected components)을 다루기 위한 것(예: call과 function 노드는 호출 대상의 시그니처에 관심이 있다)
저수준 작업 전에, 고수준 IR과 언어 의미론의 strength reduction(내 고수준 IR에는 저수준 관심사는 제발 없었으면 한다)
내가 동의하게 되었던 몇몇 논문과 글
이 글 초안에 대해 귀중한 피드백을 준 Chris Fallin, Hunter Goldstein, Per Vognsen에게 감사한다.