LLVM 최적화와 연관된 C의 정의되지 않은 동작 개념을 소개하고, 성능 측면에서 왜 이를 도입했는지와 대표 사례들을 설명하는 3부작 시리즈의 1편.
사람들은 가끔 최적화를 켜면 LLVM이 컴파일한 코드에서 SIGTRAP 시그널이 발생하는 이유를 묻곤 합니다. 자세히 들여다보면(여기서는 X86 코드를 가정) Clang이 __builtin_trap()과 동일한 "ud2" 명령을 생성했음을 발견합니다. 여기에는 여러 가지 이슈가 얽혀 있는데, 핵심은 C 코드의 정의되지 않은 동작과 LLVM이 이를 어떻게 다루는가에 있습니다.
이 블로그 글(3부작 중 첫 번째)은 이러한 이슈들 가운데 일부를 설명하여, 관련 트레이드오프와 복잡성을 더 잘 이해하도록 돕고, 아울러 C의 어두운 면 몇 가지를 더 배우도록 하는 데 목적이 있습니다. 많은 저수준 지향의 숙련된 C 프로그래머들이 생각하듯 C가 "고수준 어셈블러"는 _아님_이 드러나며, C++와 Objective-C도 그 문제점들을 그대로 상당 부분 물려받았다는 점을 보게 될 것입니다.
다른 언어로 된 글: 일본어, 스페인어 C 언어와 LLVM IR 모두 "정의되지 않은 동작(Undefined Behavior)"이라는 개념을 가지고 있습니다. 정의되지 않은 동작은 광범위하고 미묘한 주제입니다. 이에 대한 최고의 입문 자료로는 John Regehr의 블로그 글을 꼽을 만합니다. 이 훌륭한 글을 한 문장으로 요약하면, C에서 겉보기에 그럴듯한 많은 일들이 실제로는 정의되지 않은 동작이며, 이것이 프로그램 버그의 흔한 원인이라는 것입니다. 더 나아가, C에서의 어떤 정의되지 않은 동작도 구현(컴파일러와 런타임)에게 당신의 하드 드라이브를 포맷하거나, 완전히 예상치 못한 일을 하거나, 그보다 더 나쁜 일을 하도록 허용합니다. 다시 한 번, John의 글을 강력히 추천합니다.
C 계열 언어에 정의되지 않은 동작이 존재하는 이유는 C 설계자들이 C를 극도로 효율적인 저수준 프로그래밍 언어로 만들고자 했기 때문입니다. 반대로 Java 같은(그리고 많은 다른 ‘안전한’) 언어들은 구현 간에 안전하고 재현 가능한 동작을 보장하기 위해 정의되지 않은 동작을 배제했고, 이를 위해 성능을 희생할 의향이 있습니다. 어느 쪽이 “정답”이라고 단정할 수는 없지만, C 프로그래머라면 정의되지 않은 동작이 무엇인지 반드시 이해해야 합니다.
세부사항으로 들어가기 전에, 컴파일러가 폭넓은 종류의 C 애플리케이션에서 좋은 성능을 끌어내려면 무엇이 필요한지 간단히 언급할 가치가 있습니다. 왜냐하면 마법의 탄환은 없기 때문입니다. 매우 높은 수준에서 보자면, 컴파일러는 다음을 통해 고성능 앱을 만듭니다. a) 레지스터 할당, 스케줄링 같은 기본기 알고리즘을 잘한다. b) 피프홀 최적화, 루프 변환 등 수많은 “요령”을 알고 이득이 날 때마다 적용한다. c) 불필요한 추상화를 잘 제거한다(예: C의 매크로로 인한 중복, 함수 인라이닝, C++의 임시 객체 제거 등). d) 아무 것도 망치지 않는다. 아래의 어떤 최적화는 사소해 보일 수 있지만, 실제로는 중요한 루프에서 단 1사이클을 절약하는 것만으로도 어떤 코덱은 10% 더 빨라지거나 전력을 10% 덜 쓰게 될 수 있습니다.
정의되지 않은 동작의 어두운 면과 C 컴파일러로서의 LLVM의 정책과 동작에 들어가기 전에, 몇 가지 구체적인 정의되지 않은 동작 사례를 살펴보고, 각각이 Java 같은 안전한 언어보다 어떻게 더 나은 성능을 가능하게 하는지 이야기해보겠습니다. 이를 정의되지 않은 동작이 “가능하게 하는 최적화”로 보아도 좋고, 각 경우를 정의하도록 만들기 위해 필요한 “오버헤드를 피한 것”으로 보아도 좋습니다. 물론 컴파일러 최적화가 이러한 오버헤드를 일부 상황에서는 제거할 수 있겠지만, 일반적으로(모든 경우에 대해) 그렇게 하려면 정지 문제를 풀어야 하는 등 수많은 “흥미로운 도전”이 필요합니다. 또한 Clang과 GCC는 C 표준이 미정으로 남겨 둔 몇몇 동작을 실제로는 고정해 둔다는 점도 언급할 가치가 있습니다. 여기서 설명하는 것들은 표준상 미정이며, 두 컴파일러 모두 기본 모드에서 정의되지 않은 동작으로 취급합니다.
초기화되지 않은 변수를 사용: 이것은 C 프로그램에서 문제의 원천으로 널리 알려져 있으며, 이를 잡아내기 위한 도구도 많습니다. 컴파일러 경고부터 정적/동적 분석기까지 다양하죠. 이로 인해 성능이 좋아지는 이유는, Java처럼 스코프에 들어오는 모든 변수를 0으로 초기화할 필요가 없기 때문입니다. 대부분의 스칼라 변수의 경우 오버헤드는 크지 않겠지만, 스택 배열과 malloc으로 할당한 메모리는 저장소를 memset으로 채워야 하고, 대개 그 저장소는 곧 완전히 덮어쓰여지기 때문에 특히 비용이 클 수 있습니다.
부호 있는 정수 오버플로: 예를 들어 'int' 타입의 산술 연산에서 오버플로가 발생하면 그 결과는 정의되지 않습니다. “INT_MAX+1”이 INT_MIN이 되리라는 보장은 없습니다. 이 동작은 특정 범주의 최적화를 가능하게 하며, 이는 어떤 코드에는 중요합니다. 예를 들어, INT_MAX+1이 정의되지 않다는 사실은 “X+1 > X”를 “true”로 최적화할 수 있게 해줍니다. 곱셈이 오버플로 “할 수 없다”(그렇게 되면 정의되지 않기 때문)고 알면 “X*2/2”를 “X”로 최적화할 수 있습니다. 사소해 보일 수 있지만, 이런 것들은 인라이닝과 매크로 확장 과정에서 흔히 드러납니다. 더 중요한 최적화는 다음과 같은 "<=" 루프에 대해 가능합니다:
for (i = 0; i <= N; ++i) { ... }
이 루프에서, 만약 “i”가 오버플로 시 정의되지 않는다면 컴파일러는 루프가 정확히 N+1번 반복한다고 가정할 수 있고, 그 결과 폭넓은 루프 최적화가 작동합니다. 반대로, 오버플로 시 값이 래핑되도록 정의되어 있다면(예: N이 INT_MAX인 경우) 루프가 무한 루프일 가능성을 컴파일러가 가정해야 하며, 이는 중요한 루프 최적화들을 비활성화합니다. 이는 특히 많은 코드가 유도 변수로 'int'를 사용하는 64비트 플랫폼에 영향을 크게 미칩니다. 한편, 부호 없는 정수의 오버플로는 2의 보수(래핑) 오버플로로 정의되어 있으므로 언제든 사용할 수 있습니다. 부호 있는 정수 오버플로를 정의되도록 만드는 대가는 이런 종류의 최적화를 잃는 것입니다(예: 64비트 대상에서 루프 안에 부호 확장이 잔뜩 생기는 것이 흔한 증상입니다). Clang과 GCC는 "-fwrapv" 플래그를 지원하는데, 이는 컴파일러가 부호 있는 정수 오버플로를(단, INT_MIN을 -1로 나누는 경우를 제외하고) 정의된 것으로 취급하도록 강제합니다.
과도한 시프트 양: uint32_t를 32비트 이상 시프트하는 것은 정의되지 않습니다. 제 추측으로, 이것은 다양한 CPU에서 하부 시프트 연산이 서로 다르게 동작하기 때문입니다. 예를 들어 X86은 32비트 시프트 양을 5비트로 잘라내므로(32비트 시프트는 0비트 시프트와 동일) 반면 PowerPC는 32비트 시프트 양을 6비트로 잘라내기 때문에(32비트 시프트는 0을 생성) 그렇습니다. 이러한 하드웨어 차이 때문에 C는 동작을 전적으로 미정으로 둡니다(따라서 PowerPC에서 32비트 시프트는 하드 드라이브를 포맷할 수도 있으며, 0을 생성한다고 보장되지 않습니다). 이 정의되지 않은 동작을 없애려면, 변수 시프트마다 추가 연산(예: 'and')을 내보내야 하며, 이는 일반적인 CPU에서 시프트 비용을 두 배로 늘립니다.
엉뚱한 포인터 역참조와 배열 경계 밖 접근: 무작위 포인터(NULL, 해제한 메모리를 가리키는 포인터 등)를 역참조하거나, 그 특수한 경우인 배열의 경계 밖 접근은 C 애플리케이션에서 흔한 버그이며 설명이 굳이 필요 없을 것입니다. 이 정의되지 않은 동작의 원인을 제거하려면 모든 배열 접근에 대해 범위 검사를 수행해야 하며, 포인터 산술의 대상이 될 수 있는 포인터에는 범위 정보가 따라다니도록 ABI를 바꿔야 합니다. 이는 많은 수치/기타 애플리케이션에 극도로 높은 비용을 부과할 뿐 아니라, 기존 모든 C 라이브러리와의 바이너리 호환성을 깨뜨립니다.
NULL 포인터 역참조: 흔한 믿음과 달리, C에서 NULL 포인터를 역참조하는 것은 정의되지 않았습니다. 트랩하도록 정의되어 있지도 않으며, 0번지에 페이지를 mmap하더라도 그 페이지에 접근할 수 있도록 정의되어 있지 않습니다. 이는 엉뚱한 포인터의 역참조를 금하고, NULL을 센티넬로 사용하는 규칙에서 자연스럽게 따르는 결과입니다. NULL 포인터 역참조가 정의되지 않았다는 사실은 폭넓은 최적화를 가능하게 합니다. 반대로 Java에서는, 최적화기가 널이 아님을 증명하지 못하는 어떤 객체 포인터 역참조에 대해서도 컴파일러가 부수효과가 있는 연산을 그 경계 너머로 이동시키는 것이 금지됩니다. 이는 스케줄링과 기타 최적화를 크게 제약합니다. C 계열 언어에서는 NULL이 정의되지 않았기 때문에, 매크로 확장과 인라이닝의 결과로 드러나는 수많은 간단한 스칼라 최적화가 가능해집니다.
LLVM 기반 컴파일러를 사용한다면, “volatile” NULL 포인터를 역참조해서 크래시를 유발할 수 있습니다. 보통 volatile 로드/스토어는 최적화기가 건드리지 않기 때문입니다. 현재 무작위 NULL 포인터 로드를 유효한 접근으로 간주하게 하거나, 무작위 로드가 “널이 허용된다”고 알리게 하는 플래그는 없습니다.
타입 규칙 위반: int를 float로 캐스팅한 뒤 역참조하여(“int”를 “float”인 것처럼 접근하는) 사용하는 것은 정의되지 않은 동작입니다. C는 이러한 종류의 타입 변환이 memcpy를 통해 일어나도록 요구합니다. 포인터 캐스트를 사용하는 것은 올바르지 않으며 정의되지 않은 동작을 유발합니다. 이 규칙은 꽤 미묘하여 여기서 자세히 다루지는 않겠습니다(char*에 대한 예외, 벡터의 특수한 속성, union이 끼치는 영향 등). 이 동작은 "타입 기반 별칭 분석(Type-Based Alias Analysis, TBAA)"이라는 분석을 가능하게 하며, 컴파일러의 폭넓은 메모리 접근 최적화에 사용되어 생성 코드의 성능을 크게 개선할 수 있습니다. 예를 들어, 이 규칙 덕분에 clang은 다음 함수를 최적화할 수 있습니다:
float *P;
void zero_array() {
int i;
for (i = 0; i < 10000; ++i)
P[i] = 0.0f;
}
이를 "memset(P, 0, 40000)"으로 바꿉니다. 이 최적화는 또한 많은 로드를 루프 밖으로 끌어올리고, 공통 부분식을 제거하는 등 다양한 최적화를 가능하게 합니다. 이 범주의 정의되지 않은 동작은 -fno-strict-aliasing 플래그를 전달해 비활성화할 수 있으며, 그러면 이 분석이 금지됩니다. 이 플래그가 전달되면 Clang은 이 루프를 4바이트 스토어 10000개로 컴파일해야 합니다(여러 배 느립니다). 왜냐하면 다음과 같은 상황처럼, 어떤 스토어라도 P의 값을 바꿀 수 있다고 가정해야 하기 때문입니다:
int main() {
P = (float*)&P; // zero_array에서 TBAA 위반을 일으키는 캐스트
zero_array();
}
이런 종류의 타입 남용은 꽤 드뭅니다. 그래서 표준 위원회는, “그럴듯해 보이는” 타입 캐스트에서 뜻밖의 결과가 생기더라도, 상당한 성능 이득이 그만한 가치가 있다고 판단했습니다. Java는 언어에 안전하지 않은 포인터 캐스팅이 아예 없기 때문에, 이러한 단점 없이 타입 기반 최적화의 이점을 얻을 수 있다는 점도 짚어둘 만합니다. 어쨌든, 위 내용이 C에서 정의되지 않은 동작이 가능하게 하는 최적화의 범주들에 대한 감을 주었기를 바랍니다. 물론 이 밖에도 시퀀스 포인트 위반(예: “foo(i, ++i)”), 멀티스레드 프로그램의 경쟁 상태, 'restrict' 위반, 0으로 나누기 등 다양한 종류가 더 있습니다.
다음 글에서는, 성능만이 유일한 목표가 아니라면 C의 정의되지 않은 동작이 왜 꽤 무서운 것인지 논의하겠습니다. 시리즈의 마지막 글에서는 LLVM과 Clang이 이를 어떻게 다루는지 이야기합니다.