컴파일러 IR의 정밀한 의미론과 포인터 프로비넌스의 필요성을 설명한다. 세 가지 LLVM 최적화의 조합이 잘못된 결과를 낳는 예를 통해 프로비넌스를 무시할 때 생기는 문제를 보이고, 올바른 최적화를 위해 IR 명세를 명확히 해야 함을 주장한다. 또한 포인터에는 프로비넌스가 있지만 정수에는 없어야 한다는 방향을 제시한다.
얼마 전, 나는 포인터에는 우리가 눈으로 보는 것 이상의 것이 있다는 내용의 블로그 글을 썼다. 내가 강조하려던 핵심 포인트 중 하나는 다음과 같다.
두 포인터가 같은 주소를 가리킨다고 해서, 서로를 대체 가능하게 쓸 수 있다는 의미의 “같다”가 되는 것은 아니다.
같은 주소를 가리키는 서로 다른 포인터를 구분하게 만드는 이 “추가 정보”는 보통 프로비넌스(provenance)라고 부른다. 이 글은 최적화하는 컴파일러에서 프로비넌스를 충분히 주의 깊게 고려하지 않으면 무슨 일이 잘못될 수 있는지를 보여주는 경고담을 통해, 프로비넌스가 “실재한다”는 점을 다시 한번 설득하려는 시도다. 글은 자기완결적이며, 앞선 글을 읽었다고 가정하지 않는다. 더 나아가, 컴파일러 IR의 명세에 더 많은 노력을 기울이면 미래에 이런 문제가 나타나는 것을 막을 수 있다는 더 큰 메시지도 담고 있다.
아래에서는 “직관적으로 타당해 보이는” 세 가지 컴파일러 변환을 차례로 보여 주는데, 이들을 함께 적용하면 명백히 잘못된 결과로 이어진다. 예시에는 LLVM을 사용하지만, 목표는 LLVM을 꼬집는 것이 아니다—다른 컴파일러들도 비슷한 문제를 겪는다. 목표는 C, C++, Rust처럼 안전하지 않은 포인터 조작을 허용하는 언어를 위한 올바른 컴파일러를 만들려면, IR 의미론(특히 프로비넌스)을 더 진지하게 받아들여야 한다는 점을 설득하는 것이다. LLVM은 단일하고 방대한 문서를 갖춘 IR과 그 주변 생태계 덕분에 연구하기 특히 쉬워서 예시에 채택했을 뿐이다. 시작해 보자!
워밍업으로, LLVM IR 같은 컴파일러 IR에 정밀하고(그리고 정밀하게 문서화된) 의미론이 필요하다는 것을 보여 주는 간단한 예를 들어 보겠다. 이미 컴파일러 IR을 그 자체로 하나의 제대로 된 프로그래밍 언어로 다루는 생각에 익숙하거나, 아니면 포인터와 그 프로비넌스에 관심이 있어서 여기에 온 것이라면 다음 절로 건너뛰어도 된다.
다음과 같은 간단한(그리고 이 예시를 위해 일부러 만든) C 코드가 n * (i+j)를 계산한다고 하자:
int sum_up(int i, int j, unsigned int n) {
int result = 0;
while (n > 0) {
result += i + j;
n -= 1;
}
return result;
}
컴파일러가 하고 싶어 할 수 있는 한 가지 변환은 덧셈 i+j를 루프 밖으로 옮겨 매번 합을 계산하지 않도록 하는 것이다(이를 “루프 불변 코드 이동(loop-invariant code motion)”이라 한다1):
int sum_up(int i, int j, unsigned int n) { // 최적화된 버전
int result = 0;
int s = i + j;
while (n > 0) {
result += s;
n -= 1;
}
return result;
}
하지만 이 변환은 사실 틀렸다. 호출자가 sum_up(INT_MAX, 1, 0)처럼 이 함수를 사용한다고 상상해 보자. 이는 sum_up을 호출하는 완전히 올바른 방법이다: 루프는 한 번도 실행되지 않으므로, 오버플로우를 일으키는 INT_MAX+1 덧셈은 결코 수행되지 않는다. 그러나 원하는 최적화를 거친 뒤에는, 프로그램이 부호 있는 정수 오버플로우를 일으키게 되며, 이는 UB(정의되지 않은 동작, Undefined Behavior)이고 따라서 “절대 일어나면 안 된다!”2
이 문제를 무시하고 싶어질 수도 있다. 정수 오버플로우에서의 UB는 컴파일러에게만 존재하는 개념이고, 컴파일러가 지원하는 모든 타깃은 뻔하게 오버플로우된 결과를 낼 것이기 때문이다. 하지만 우리가 고려 중인 최적화 뒤에도 다른 컴파일러 패스가 더 돌 수 있다. 예컨대, 어떤 패스는 sum_up을 인라인할 수 있고, 또 다른 패스는 INT_MAX+1을 감지하고 UB 코드는 “정의상” 도달 불가능하므로 이를 unreachable로 바꿀 수 있으며, 또 다른 패스는 그 결과 모든 코드가 도달 불가능하므로 통째로 제거해 버릴 수도 있다. 각각의 패스는 존재할 만한 좋은 이유가 있다(실제 코드의 성능을 크게 높이거나 죽은 코드를 잘라내는 데 도움이 된다). 그러나 이들을 루프 불변 코드 이동과 결합하면 결과는 재앙이 된다.
이런 문제를 피하는 하나의 방법(그리고 내가 아는 한 유일하게 체계적인 방법)은 각 최적화의 올바름을 개별적으로 정당화할 수 있도록 하는 것이다. 각 최적화는 가능한 모든 프로그램에 대해 올바르다 여야 하며, 여기서 _올바르다_는 것은 최적화된 프로그램이 오직 원래 프로그램도 할 수 있었던 일만 “한다”는 뜻이다. (이는 C 표준의 “as-if” 규칙과 사실상 같고, 학계에서는 보통 “정제(refinement)”라 부른다.) 특히, 어떤 최적화도 UB가 없던 프로그램에 UB를 새로 도입해서는 안 된다.
이 전제 아래에서는 우리가 고려 중인 루프 불변 코드 이동을 수행하는 것이 불가능하다고 보일 수도 있다. 그러나 그렇지 않다! 지금까지 본 것은, 이 최적화가 C 프로그램에 수행될 때 _올바르지 않다_는 점이다. 하지만 LLVM이 이러한 최적화를 수행할 때, 프로그램이 C로 작성되었다고 보지 않는다—LLVM IR로 작성되었다고 본다. 그리고 LLVM IR은 C와 다른 의미론을 가진다. 구체적으로 LLVM LangRef는 LLVM IR에서 부호 있는 정수 오버플로우의 결과가 poison 값이라고 말한다. poison을 만들어 내는 것 자체는 UB가 아니며, 다만 poison을 특정 방식으로 사용하는 것이 UB다(세부 사항은 여기서 중요하지 않다). 최적화된 sum_up(INT_MAX, 1, 0) 호출에서는, 루프 불변 코드 이동으로 도입된 변수 s는 사용되지 않으므로 그 값이 poison이라는 사실은 문제가 되지 않는다!
이와 같은 부호 정수 오버플로우의 동작 때문에, 이 경우의 루프 불변 코드 이동은 프로그램이 LLVM IR로 작성되었다고 볼 때 올바르다3. 우리가 치러야 할 “대가”는, LLVM IR에서는 INT_MAX+1을 unreachable로 바꾸는 것이 _올바르지 않다_는 점이다. 그 연산이 UB가 아니기 때문이다.
올바른 최적화의 훌륭한 점은, 어떤 순서로든 원하는 만큼 결합할 수 있고(예: 인라인, 명확한 UB를 unreachable로 대체, 도달 불가능한 코드 제거), 그 결과가 언제나 원래 프로그램의 올바른 컴파일 결과임을 보장할 수 있다는 것이다. (학계 용어로는 “정제는 추이적이다”라고 말한다.)
그러나 어떤 최적화가 _올바르다_고 주장하려면, LLVM IR의 정확한 의미론(가능한 모든 프로그램의 동작과 언제 UB가 되는지)이 문서화되어 있어야 한다. 모든 관련 최적화는 무엇이 UB이고 무엇이 아닌지에 대해 정확히 합의해야 하며, 그래야 자신들이 만든 코드가 이후의 최적화에 의해 UB로 간주되지 않는다. 이는 C 같은 프로그래밍 언어의 명세에 기대하는 것과 정확히 동일하다. 그래서 나는 컴파일러 IR을 그 자체로 제대로 된 프로그래밍 언어로 간주하고, “일반” 언어를 명세할 때와 같은 성실함으로 명세해야 한다고 생각한다4. 물론 사람이 LLVM IR로 직접 많은 프로그램을 작성하는 일은 없을 것이므로 문법은 거의 중요하지 않다. 하지만 clang과 rustc는 항상 LLVM IR 프로그램을 만들어 내며, 우리가 본 것처럼 프로그램 동작을 지배하는 정확한 규칙을 이해하는 것은 LLVM이 수행하는 최적화가 프로그램의 동작을 바꾸지 않도록 보장하는 데 결정적으로 중요하다.
요점: 컴파일러의 올바름을 모듈식으로, 즉 한 번에 하나의 최적화만 고려해서 정당화하려면, 프로그램 동작의 모든 측면(UB 포함)에 대해 정밀한 명세를 갖춘 IR에서 이러한 최적화를 수행해야 한다. 그리고 각 최적화에 대해 다음을 묻는다: 이 최적화가 프로그램의 동작을 바꾸는가? UB가 없던 프로그램에 UB를 도입하는가? 올바른 최적화라면 그 답은 “아니오”여야 한다.
워밍업을 마쳤으니, 이제 언어 명세가 얼마나 정밀해야 하는지 탐구하기 위해 좀 더 까다로운 최적화들을 살펴보자. LLVM이 수행할 수 있는 세 가지 서로 다른 최적화를 볼 것이고, 이들이 _모두 동시에 올바를 수는 없음_을 보여 주겠다. 실제로 우리가 살펴볼 첫 번째 프로그램과 마지막 프로그램은 _서로 다른 동작_을 보이기 때문이다. (더 정확히는: 마지막 프로그램에는 첫 번째 프로그램에서는 불가능했던 동작이 가능하다.) 이는 적어도 하나의 최적화가 부적절하게 프로그램 동작을 바꾸었다는 뜻이지만, 정확히 어느 최적화가 범인인지는 명확하지 않다.
이 일련의 예시는 Chung-Kil Hur의 이 발표에서 가져왔다. 이는 LLVM의 수학적으로 엄밀한 명세를 만들던 중 발견되었다.
다음이 소스 프로그램이다:
char p[1], q[1] = {0};
uintptr_t ip = (uintptr_t)(p+1);
uintptr_t iq = (uintptr_t)q;
if (iq == ip) {
*(char*)iq = 10;
print(q[0]);
}
여기서는 단지 LLVM IR로 프로그램을 쓰는 편리한 방법으로 C 문법을 쓰고 있다.
이 프로그램은 두 가지 가능한 동작을 가진다. ip(p의 끝 다음 포인터(one-past-the-end))와 iq(q의 주소)가 다르면 아무것도 출력하지 않는다. 두 값이 같으면 프로그램은 “10”을 출력한다(iq는 q를 정수로 캐스팅한 결과이므로, 다시 캐스팅하면 원래의 포인터, 적어도 같은 객체/메모리 위치를 가리키는 포인터가 된다).
우리가 수행할 첫 번째 “최적화”는, if 본문 내부로 들어갔을 때 iq == ip임을 이용해 모든 iq를 ip로 대체하는 것이다. 이어서 ip의 정의를 인라인한다:
char p[1], q[1] = {0};
uintptr_t ip = (uintptr_t)(p+1);
uintptr_t iq = (uintptr_t)q;
if (iq == ip) {
*(char*)(uintptr_t)(p+1) = 10; // <- 이 줄이 바뀜
print(q[0]);
}
두 번째 최적화는 포인터 p+1을 정수로 캐스팅했다가 다시 포인터로 캐스팅한다는 점을 알아차리고, 이 캐스트 왕복을 제거한다:
char p[1], q[1] = {0};
uintptr_t ip = (uintptr_t)(p+1);
uintptr_t iq = (uintptr_t)q;
if (iq == ip) {
*(p+1) = 10; // <- 이 줄이 바뀜
print(q[0]);
}
마지막 최적화는 q가 한 번도 쓰이지 않는다는 사실을 알아차리고, q[0]을 그 초기값 0으로 대체한다:
char p[1], q[1] = {0};
uintptr_t ip = (uintptr_t)(p+1);
uintptr_t iq = (uintptr_t)q;
if (iq == ip) {
*(p+1) = 10;
print(0); // <- 이 줄이 바뀜
}
하지만 이 마지막 프로그램은 첫 번째 것과 다르다! 구체적으로, 마지막 프로그램은 아무것도 출력하지 않거나 “0”을 출력하지만, 원래 프로그램은 절대로 “0”을 출력할 수 없었다. 이는 우리가 수행한 세 가지 최적화의 연쇄가 전체적으로는 _올바르지 않다_는 것을 보여 준다.
분명히, 세 가지 최적화 중 하나는 프로그램 동작을 바꾸는 의미에서 잘못되었다. 그런데 어느 것일까?
이상적으로는, LLVM IR에 대해 충분히 정밀한 의미론이 있다면 문서를 읽기만(또는 더 좋게는 Miri 같은 도구를 돌리기만) 하면 답을 찾을 수 있을 것이다. 하지만 이 수준의 정밀함으로 언어 의미론을 기술하는 것은 어렵고, 많은 절충이 필요하다. LLVM LangRef는 여기서 분명한 답을 주지 않으며, 실은 분명한 답을 얻으려면 아직 명시적으로 내려지지 않은 결정을 해야 한다.
계속하려면, 앞서 살펴본 세 가지 최적화를 단서로 사용해 보자. 해당 최적화가 LLVM IR에서 올바르다고 가정하면, 의미론에 대해 무엇을 말해 주는가?
마지막 최적화부터 시작하자. 여기서는 print의 인수가 q[0]에서 0으로 바뀐다. 이 최적화는 별칭 분석에 기반한다. q[0]은 프로그램 시작 시 0으로 초기화되며, 그 초기화와 print 사이에서 벌어지는 유일한 쓰기는 포인터 p+1을 통해서다. q와 p는 서로 다른 지역 변수들을 가리키므로, p에서 유도된 포인터는 q[0]와 별칭(alias)일 수 없다. 따라서 이 쓰기가 q[0]에 저장된 값을 바꿀 수 없다는 결론을 얻는다.
하지만 좀 더 면밀히 보면, 일이 그리 단순하지 않음을 알 수 있다! p+1은 끝 다음 포인터이므로 실제로 q[0]와 같은 주소를 가질 수도 있다(사실 조건문 내부에서는 두 값이 같다는 것을 알고 있다). 하지만 LLVM IR(그리고 C도 마찬가지)은 끝 다음 포인터를 통한 메모리 접근을 허용하지 않는다. if 안에서 같은 메모리 위치를 가리킨다는 사실을 알고 있더라도, p+1을 쓰는지 q를 쓰는지는 차이를 만든다. 이는 LLVM IR에서 포인터가 단지 가리키는 주소만이 아니라—그 주소가 _어떻게 계산되었는지_도 중요하다는 것을 보여 준다. 이 추가 정보를 일반적으로 _프로비넌스_라고 부른다. LLVM IR 프로그램의 의미론에서 프로비넌스가 실재한다는 사실을 인정하지 않고는 세 번째 최적화의 _올바름_을 주장할 수 없다. 포인터가 그저 정수인 평면 메모리 모델(대다수의 어셈블리 언어처럼)에서는 이 최적화는 단순히 틀렸다.
이제 포인터에 프로비넌스가 존재함을 알았으니, 포인터가 정수로 캐스팅되었다가 다시 돌아올 때 프로비넌스에 무슨 일이 일어나는지도 고려해야 한다. 두 번째 최적화는 LLVM IR 의미론의 이 측면에 대한 단서를 준다. 포인터→정수→포인터 캐스트가 제거되므로, 정수도 프로비넌스를 가진다. 왜 그런지 보자. 두 표현식 (char*)(uintptr_t)(p+1)과 (char*)(uintptr_t)q를 고려하자. 포인터-정수-포인터 왕복 제거 최적화가 올바르다면, 첫 연산은 p+1을, 두 번째는 q를 결과로 낸다. 우리는 방금 p+1과 q가 서로 다른 포인터(프로비넌스가 다름)임을 확인했다. 이를 설명할 유일한 방법은 (char*) 캐스트의 입력이 서로 다르다고 말하는 것이다. 그런데 (uintptr_t)(p+1)과 (uintptr_t)q로 계산한 정수 값(즉, CPU 레지스터에 저장되는 비트 패턴)은 동일하다는 것을 알고 있다. 따라서 차이가 생기려면 이 정수들이 이 비트 패턴 이상의 무언가로 이루어져 있어야 한다—포인터처럼 정수도 프로비넌스를 가진다는 뜻이다.
마지막으로 첫 번째 최적화를 보자. 여기서는 iq == ip 비교가 성공하면, 최적화기가 한 값을 다른 값으로 대체한다. 이 최적화는 _정수에는 프로비넌스가 없다_는 점을 보여 준다. 이 최적화가 올바르려면, 런타임의 동등성 테스트가 성공했다는 사실이 언어 의미론을 기술하는 “추상 기계(Abstract Machine)”에서도 두 값이 동등함을 의미해야 한다. 그런데 이는 그 값의 추상 기계 표현에 런타임에 표현되지 않는 “이상한(extra)” 부분이 포함될 수 없다는 뜻이다. 물론 프로비넌스야말로 그런 “이상한” 추가 부분이다. 같은 논리를 다른 방식으로 표현하면, 이 최적화가 올바르려면 iq == ip가 true를 낸다면 두 값은 같은 “추상 기계” 표현을 가져야 하며, 그 표현에 프로비넌스가 포함된다면 두 값은 같은 프로비넌스를 가져야 한다. 이는 원칙적으로 LLVM IR에서 ==를 정의하는 한 가지 가능성이지만, 현실적으로는 LLVM 백엔드가 ==를 컴파일할 때 포인터 프로비넌스를 고려해야 한다는 뜻이 되고, 이는 불가능하다.
요점: 세 가지 최적화를 각각 LLVM IR 의미론이 무엇을 말해 주는가의 관점에서 살펴본 결과, 우리는 포인터에 프로비넌스가 있고, 포인터를 정수로 캐스팅했다가 돌아올 때 정수는 그 프로비넌스를 기억하며, 동시에 정수에는 프로비넌스가 없다는 결론을 얻었다. 이는 모순이며, 이 모순이 세 가지 최적화를 같은 프로그램에 모두 적용했을 때 잘못된 컴파일 결과가 나타난 이유를 설명해 준다.
이 문제를 고치려면 세 가지 최적화 중 하나를 틀렸다고 선언하고 수행을 중단해야 한다. LLVM IR 의미론의 관점에서 말하면, 포인터와/또는 정수가 프로비넌스를 가지는지 여부를 결정하는 일과 같다.
내 생각에 첫 번째와 마지막 선택지는 견딜 수 없다. 프로비넌스를 완전히 없애면 가장 단순한 별칭 분석을 제외한 거의 모든 것이 무너진다5. 반면 정수가 프로비넌스를 가진다고 선언하면, 위에서 본 첫 번째 최적화만 비활성화되는 것이 아니라 x - x를 0과 동등하다고 보는 흔한 산술 최적화도 비활성화된다. 정수가 프로비넌스를 가지면 +의 교환법칙과 결합법칙을 성립시키는 것조차 사소하지 않다.
그래서 나는 포인터에는 프로비넌스가 있지만 정수에는 없다고 말함으로써(즉, 두 번째 최적화가 틀렸다고 봄으로써) 문제를 해결해야 한다고 생각한다. 이는 최근 C 표준 위원회에 제안된 내용과도 일치한다. 그래서 LLVM 버그 #34548에서는 포인터→정수→포인터 왕복을 최적화로 없애는 것이 일반적으로는 틀렸으며, LLVM이 이를 중지해야 한다고 말한다. 여전히 가능한 특수한 경우가 있을 수는 있지만, 그 한계를 규명하려면 우리가 이 논문에서 제안한 것과 같은 더 정밀한 LLVM IR 의미론 기술이 필요하다.
하지만 최종적으로는 LLVM 커뮤니티가 결정을 내려야 한다. 확실한 것은 선택을 해야 한다는 점이다. 현재처럼 세 가지 최적화를 모두 수행하는 상태는 잘못된 컴파일 결과를 낳기 때문이다.
무엇을 배웠는가? 우선, 포인터는 복잡하다. 일반적인 별칭 분석과 일관되게 그 의미론을 정확히 설명하려면 “프로비넌스”라는 개념을 도입해야 한다. 포인터의 표현을 관찰할 수 없는 Java나 ML 같은 언어에서는 사실 이 작업이 꽤 쉽다. 하지만 포인터-정수 캐스트를 지원하는 Rust, C, C++ 같은 언어에서는 프로비넌스를 도입하는 것이 정말 까다로운 질문들을 낳으며, 이 영역에서 일반적으로 수행되는 최적화들 중 적어도 하나는 포기해야 한다.
LLVM에 버그가 있다는 것도 배웠지만, 그것이 이 글의 요점은 아니다. GCC 개발자들도 정확히 같은 실수를 했고, MSVC와 ICC도 같은 문제가 있다는 소식을 들었다(검증 방법은 모르겠다). 그리고 나는 그들을 탓할 수 없다. 컴파일러 개발이 보통 작동하는 방식에서는, 이런 버그는 불가피하다고 생각한다. IR에서 정확히 언제 UB가 발생하는지에 대한 명세가 종종 느슨하게만 정해져 있고, 많은 경우 “누락을 통한” 방식(명세에 포함되지 않은 경우는 암묵적으로 UB)으로 되어 있기 때문이다. 따라서 앞서 정의한 의미에서 어떤 최적화가 올바른지 평가하는 것은 매우 어렵거나 아예 불가능할 수 있다. 포인터 프로비넌스는 그중 특히 좋고(그리고 미묘한) 예시일 뿐이다. 또 다른 사례로, 이 논문의 §2.3(코드는 그림 3)을 보라. 두 가지 최적화의 연쇄가 오컴파일(miscompilation)로 이어지는데, 첫 번째 최적화는 LLVM 동시성 모델 하에서 올바르고, 두 번째 최적화는 C++11 동시성 모델 하에서 올바르다. 하지만 둘 다 올바른 동시성 모델은 없으며, 따라서 각 컴파일러(정확히는 각 컴파일러 IR)는 둘 중 하나를 선택해야 한다. 마지막으로, undef와 poison에 관한 이 논문은 LLVM에서 undef의 존재로 인해 부서지는 최적화의 예를 들고, poison의 의미론을 정의할 때 생기는 여러 절충을 설명한다. 여기서도 오컴파일이 발생하는 이유는 명세의 한 부분에서 한 진술의 결과(undef는 매 사용 시마다 새로운 값을 택함)가 다른 곳에서는 고려되지 않았기 때문이다(정수를 0과 같은지 테스트했다고 해서 0임을 뜻하지 않는다; undef일 수도 있다).
여기서 이 글의 핵심 결론에 이른다. 서로 양립할 수 없는 최적화 문제를 피하려면, 컴파일러 IR을 그 자체로 하나의 프로그래밍 언어로 더 진지하게 다루고, 모든 UB를 포함한 정밀한 명세를 부여해야 한다고 나는 생각한다. “LLVM에는 풍부한 LangRef가 있는데도, 그 명세를 읽으면 위의 세 최적화 각각이 올바르다고 스스로 납득할 수 있었고, 이것이 서로 모순이 되었던 것은 어쩌란 말이냐?”라고 반문할 수 있다. 무엇이 빠져 있는가? 이런 모호함을 막으려면 수학적으로 형식적인 정의가 필요할까? 나는 그렇게 보지 않는다. 더 단순하지만 큰 도움이 될 것이 있다고 본다. 모순의 근원은 명세의 일부가 포인터에 프로비넌스가 있다고 암묵적으로 가정한다는 점이며, 이는 다른 연산을 고려할 때 쉽게 잊힌다. 그래서 나는 이런 가정을 더 명시적으로 만드는 것이 매우 중요하다고 생각한다. 명세는 값이 무엇으로 “구성되는지”(프로비넌스, 그리고 그 값이(전부 또는 일부) 초기화되었는지 여부 같은 것들)를 명시적으로 기술해야 한다6. 이 정보는 가상의 인터프리터가 모든 UB를 감지하는 데 충분할 정도로 상세해야 한다. 그렇게 하면 포인터에 프로비넌스가 있다는 사실이 자명해진다. 그렇지 않으면 끝 다음 포인터를 허용하면서도 범위를 벗어난 포인터 산술을 제대로 검사할 수 없기 때문이다.
이것이 내가 충분히 정밀한 언어 명세의 기준으로 보는 바다. UB 검사 인터프리터를 작성하는 데 필요한 모든 정보가 명세에 담겨 있어 “수고만 들이면” 구현할 수 있어야 하며, 명세에 기술되지 않은 새로운 것을 도입할 필요가 없어야 한다.
좋은 소식은, 이런 더 정밀한 명세를 개발하는 작업이 이미 진행 중이라는 것이다!
Rust 쪽에서는 주로 Miri 인터프리터에서 이를 볼 수 있는데, 내가 위에서 말한 “가상의” 인터프리터를 구체화한 것이다. 사실 이것이 내가 원래 Miri 작업을 시작한 이유였다. 현재 Miri의 주된 목적은 안전하지 않은 코드 작성자가 UB를 피하도록 돕는 것이지만, 개인적으로는 Rust와 MIR의 의미론을 다른 방식으로 생각하도록 도와준다는 점이 똑같이 중요하다고 본다. 또한 사람들이 사용하길 원하거나 필요로 하지만 현재 Miri가 허용하지 않는 패턴을 발견하여 UB 규칙 설계에 피드백을 주기도 한다.
LLVM 쪽에서는 Alive가 이 영역의 주요 발전이다. 이는 LLVM이 수행하는 최적화를 자동으로 검증할 수 있는 도구다. Alive는 LLVM 최적화에서 많은 버그를 찾아냈으며, 더욱이 LLVM 커뮤니티와의 최근 대화—더 정밀한 IR 의미론을 목표로 하는—의 많은 부분이 Nuno P. Lopes와 John Regehr가 주도하는 Alive 개발자들에 의해 추진되고 있다.
이러한 명세 노력이 특히 LLVM IR 의미론이 바뀌어야 한다고 판명될 때는 더디게 진행되곤 한다. 이 글이 최적화 컴파일러가 직면한 미묘한 문제들에 대한 인식을 높이고, 컴파일러 IR의 명세를 규명하는 일이 중요하고 흥미로운 연구 주제라는 점에 더 많은 사람이 동의하도록 설득할 수 있기를 바란다. :)
오늘은 여기까지. 끝까지 읽어 주셔서 감사하다! 언제나처럼, 이 글은 Rust 포럼과 Reddit에서 토론할 수 있다. 여기서 논의한 문제를 겪지 않는 컴파일러를 어떻게 만들 수 있을지에 대한 여러분의 생각이 궁금하다.
내 블로그를 자주 읽는 분이라면, 이것이 이미 이전 글에 중요한 역할을 했던 바로 그 최적화임을 알아챘을 것이다. 루프 불변 코드 이동은 IR 의미론의 모서리 케이스를 살펴볼 때 아주 좋은 최적화다.↩
Rust 관점에 익숙한 분이라면, i + j를 i.unchecked_add(j)로 썼다고 상상해 보라.↩
만약 지금 우리가 어떤 식으로든 반칙을 한 것 같다고 느낀다면, 즉 언제나 C에서 LLVM IR로 번역하고, 그쪽에서 최적화한 뒤 다시 번역해 오면 되는 것 아니냐고 생각한다면, 이것을 고려해 보라: LLVM IR에서 C로 번역하는 일은 정말 어렵다! 특히 LLVM IR의 부호 정수 덧셈은 C의 부호 정수 덧셈으로 번역할 수 없다. 전자는 오버플로우 시 poison 결과로 잘 정의되지만, 후자는 오버플로우가 UB이기 때문이다. C는 (정수 산술에 관해) LLVM IR보다 UB가 확실히 더 많다. 이는 한 방향의 번역은 쉽지만, 반대 방향은 어렵다는 뜻이다.↩
특히, UB 규칙이 다른 두 가지 IR 변형은 정말로 _서로 다른 프로그래밍 언어_다. 한 언어에서 잘 정의된 프로그램이 다른 언어에서는 UB를 가질 수 있으므로, 프로그램이 한 규칙 집합에서 다른 규칙 집합으로 넘어갈 때에는 각별한 주의가 필요하다.↩
안타깝게도 세 번째 선택지를 택했을 때 성능 영향에 대한 체계적인 연구를 알지 못한다. 별칭 분석의 어떤 부분이 여전히 올바른지, 그리고 그런 제한된 형태의 별칭 분석만 수행하는 컴파일러는 얼마나 느려지는지 등이다. 많은 컴파일러 개발자들이 이 선택지는 “너무나” 비용이 많이 드는 해결책이라고 “자명하게” 여기는 것으로 이해하고 있지만, 그래도 제대로 된 데이터로 뒷받침되면 좋겠다. 어쨌든, 세 번째 선택지는 LLVM의 noalias를 완전히 재설계해야 하며, 이는 Rust(레퍼런스 타입에 내장된 별칭 정보를 noalias로 인코딩)와 clang(C의 restrict를 noalias로 인코딩) 모두에 나쁜 소식일 것이다.↩
눈치 빠른 독자는 이러한 정보가 C와 C++ 명세에서도 부재하다는 점을 깨달을 것이다. 이것이 바로 내가 이들 명세를 비판하는 주요 지점 중 하나다. 이는 프로비넌스(여기에는 내가 다루지 않은 restrict도 포함)를 논의할 때뿐 아니라, 불확정(indeterminate) 및 미지정(unspecified) 값이나 유효 타입(effective type) 규칙을 논의할 때도 많은 열린 질문을 낳는다.↩
용어에 대한 주: 최적화를 “검증(validate)”한다는 것은, 최적화 전후 프로그램 텍스트가 주어졌을 때 이 특정 변환이 올바르다는 것을 도구가 증명하려고 시도함을 뜻한다. 이는 최적화를 “증명(verify)”하는 것—한 번으로 끝나는 증명을 통해 그 최적화가 언제나 올바른 변환을 수행함을 보이는 것—과 대조된다. 검증은 훨씬 더 강력한 결과를 주지만, 수행하기 극도로 어렵다. 따라서 검증은 여전히 많은 버그를 찾아낼 수 있는 훌륭한 중간 지점이다.↩