LLVM은 크고 복잡한 컴파일러이기 때문에 여러 버그가 끊이지 않고 생겨난다. 이는 컴파일러가 무한 루프를 돌거나, crash를 발생시키며 죽는 문제도 존재하지만 사용자에게 겉으로 드러나지 않는고질적인 miscompilation 버그 문제가 존재한다. 이는 개발자가 작성한 소스코드가 잘못된 머신코드로 번역되는 것이다. 여기서 잘못된이라는 개념은 굉장히 모호하게 해석될 수 있다. LLVM은 컴파일 과정에서 수많은 최적화를 수행하기에 개발자가 처음에 의돈한 소스코드와는 꽤 다른 머신코드로 컴파일 될 수 있다. 그렇기에 이를 개발자가 보고, 의도되지 않은 머신코드가 나왔는지를 알기에는 굉장히 어렵다.
이런 문제를 해결하기 위해서 Alive2라는 번역검산기가 등장하게 되었다. 이는 미들엔드에 대해서 최적화 전 LLVM IR과 최적화 후 LLVM IR를 입력받아 각각의 의미를 인코딩하고, 두 프로그램의 의미를 계산하여 일어난 최적화가 올바른지 검사한다. 이는 정확히는 Refinement Relation을 만족해야 올바른 최적화가 일어난다고 정의되며 Alive2는 이런 최적화 전 후 LLVM IR에 대해 Refinement Relation을 검사한다. 두 프로그램의 의미가 완전히 똑같을 때만 올바른 최적화가 아닌 왜 Refinement Relation을 검사해야 하는 이유는 프로그램에 Undefined Behavior가 존재할 수 있기 때문이다. 예를 들어, 프로그램이 초기화되지 않은 메모리의 값을 반환하는 프로그램이 있다고 치자. 만약 컴파일러가 이를 그냥 return 1; 이라는 프로그램으로 컴파일해도 이는 잘못된 것이 아니다. 애초에 정의되지 않은 동작이기 때문이다. 이는 LLVM IR에 존재하는 Undef와 Poison에 의해 더욱 복잡해지게 된다. 이 글을 통해서 LLVM의 Undef와 Posion에 대해서 이해할 수 있다. 이러한 복잡한 올바른 최적화를 잘 정의하고 검사해주는 Alive2에 의해서 LLVM의 미들엔드 최적화에 존재하는 miscompilation 버그들을 잘 이해할 수 있다.
이 글에서는 miscompilation bugs 중에서도 미들엔드 최적화에 의해 일어나는 버그에 대해 중점적으로 다루고자 한다.
이 글에서는 Alive2를 기준으로 LLVM 최적화 버그들을 이해해보자 한다.
이는 정말 프로그램이 최적화 전과 최적화 후에 다른 값을 내놓는 경우를 의미한다. 이는 개발자가 작성한 소스코드와는 다른 동작을 하는 프로그램이 생겨나게 되기에 매우 치명적인 버그이다. 아래는 우리의 연구에서 발견한 버그이다.
; 최적화 전
define <2 x i32> @src(<2 x i1> %y) {
%sext = sext <2 x i1> %y to <2 x i32>
%2 = or <2 x i32> %sext, <i32 0, i32 1>
%3 = udiv <2 x i32> <i32 42, i32 -7>, %2
ret <2 x i32> %3
}
; 최적화 후
define <2 x i32> @tgt(<2 x i1> %y) {
ret <2 x i32> <i32 0, i32 0>
}
이는 컴파일러가 함수를 분석했을 때, 해당 함수가 항상 0을 반환할 것이라고 계산을 하고, 그냥 0을 반환하도록 최적화 한 경우이다. LLVM IR에 익숙한 사람들은 이미 알아차렸겠지만, 위의 함수는 항상 0을 반환하는 프로그램이 아니다.
@src함수의 인자로 <i1 1 , i1 0>이 들어왔을 때를 생각해보면 %sext = <i32 -1, i32 0>, %2 = <i32 -1 ,i32 1>, %3 = <i32 0, i32 -7> 으로 최종적으로 <i32 0, i32 -7>이 반환되지만 최적화 후에는 <i32 0, i32 0>이 반환되게 되면서 잘못된 최적화가 일어났다는 것을 알 수 있다.
흔히 최적화 전보다 최적화 후에 undef 값의 사용이 늘어나면 발생하는 문제이다. undef값은 사용될 때마다 다른 값이 나올 수 있기 때문에, 최적화 후 프로그램이 undef를 더 많이 사용될 경우, 더 많은 쓰레기 값이 프로그램에 쓰이게 되고, 이는 프로그램의 의미를 해치게 된다. 이 역시 Refinement Relation에 의해 정의하여 잘못된 최적화를 체크하게 된다. 아래는 우리가 찾은 이 패턴의 버그이다.
; 최적화 전
define <4 x i1> @src(<4 x i1> %val0, <4 x i1> %val1, <4 x i1> %val2) {
entry:
%val3 = add <4 x i1> %val1, <i1 true, i1 true, i1 true, i1 true>
%val4 = xor <4 x i1> <i1 false, i1 undef, i1 undef, i1 true>, %val0
%val5 = and <4 x i1> %val4, %val3
%val6 = sub <4 x i1> %val5, %val0
ret <4 x i1> %val6
}
; 최적화 후
define <4 x i1> @tgt(<4 x i1> %val0, <4 x i1> %val1, <4 x i1> %val2) {
entry:
%val4 = xor <4 x i1> %val0, <i1 0, i1 undef, i1 undef, i1 1>
%0 = and <4 x i1> %val4, %val1
%val6 = xor <4 x i1> %#0, <i1 0, i1 undef, i1 undef, i1 1>
ret <4 x i1> %val6
}
최적화 전 프로그램의 경우에는 undef 가 2 번만 사용되지만 최적화 후에는 4번이 사용되게 된다. 이 경우에는 최적화 후 프로그램에서 더 많은 쓰레기 값이 사용되게 되고, 이는 최적화 전 후 프로그램이 다른 값을 (쓰레기 값이더라도) 내뱉게 된다. 이 경우에 대해서는 위에서도 언급한 이 글을 읽으면 더 잘 이해할 수 있다. 이 버그들은 현실에 치명적인 경우도 있지만, 미들엔드 최적화 특성상 현실에서 일어나기 힘든 경우도 많다. undef값이 초기화되지 않은 메모리의 값등 쓰레기 값을 의미하기 때문에, 애초에 이러한 값으로 연산을 하는 코드를 작성한 개발자의 문제도 있기에, 이러한 최적화 버그는 undef라는 개념을 없애고, 더 강력하게 제제함으로써 개발자가 쓰레기 값을 연산하는 코드를 작성하지 않도록 하려고 LLVM에서 논의 중이다.
Poison이라는 값은 개발자의 의도와 값이 달라진 경우를 의미한다. 예를 들어 정수가 overflow가 난 경우, 이러한 값은 컴파일러의 판단 하에 프로그램의 의미를 해칠 수 있는 경우, poison이라는 값으로 표현하여 좀 더 안전한 프로그램이 컴파일되도록 돕는다.
이러한 poison의 값의 경우도 최적화 전에 poison이 아닌 값이 최적화 후에 poison이 된 경우, 잘못된 최적화이다. 아래의 우리가 발견한 버그가 예시이다.
; 최적화 전
define i32 @src(i32 %val0, i32 %val1, i32 %val2) {
%val4 = and i32 %val2, %val0
%val5 = xor i32 %val2, -1
%val6 = and i32 %val5, %val1
%val7 = xor i32 %val4, %val6
ret i32 %val7
}
; 최적화 후
define i32 @tgt(i32 %val0, i32 %val1, i32 %val2) {
%val4 = and i32 %val2, %val0
%val5 = xor i32 %val2, -1
%val6 = and i32 %val5, %val1
%val7 = or disjoint i32 %val4, %val6
ret i32 %val7
}
위 버그를 이해하기 위해서는 LLVM IR의 or 연산자에 새로 등장한 flag인 disjoint에 대해 알아야 한다. 이는 or연산을 할 두 값둘 중 둘 모두 다 1인 비트위치가 있으면 poison을 연산 결과로 내놓게 된다. 이는 or 연산을 add와 똑같이 생각하고 싶은 경우에 compiler가 이러한 flag를 붙이게 된다. 따라서 최적화 전 프로그램은 반환값이 poison이 되는 경우는 프로그램 인자가 이미 poison인 경우밖에 없지만, 최적화 후 프로그램은 특정 값에 의해 반환값이 poison이 될 수 있기 때문에 잘못된 최적화이다. 이 역시 LLVM 개발자들이 심각하게 고려하는 miscompilation 버그 종류이다.
컴파일러를는 구조화된 입력인 프로그램을 입력받아 그 프로그램의 의미를 이해하고, 같은 의미로 동작하는 새로운 프로그램(머신코드)으로 번역해야 하기 때문에 컴파일러를 만들 때는 입력 프로그램의 구조를 정확히 이해해야 한다. 하지만 프로그램의 복잡한 구조 특성상, 모든 corner case를 고려하여 최적화를 작성하고, 컴파일러 구조를 만드는 것이 매우 어렵다. 그렇기에 적어도 컴파일러가 올바르게 컴파일하고 있는지를 자동화해서 버그를 찾고, 완전 자동화를 못하더라도 컴파일러 개발자들이 좀 더 버그를 쉽게 이해하고 컴파일러 개발을 할 때 고려해야 하는 점들을 쉽게 알 수 있도록 하는 것이 중요한다.
최근, 컴파일러 최적화를 잘 유발하는 프로그램을 지향성 퍼징으로 똑똑하게 생성하고, 이를 통해서 컴파일러의 최적화 버그를 자동으로 발견하려는 연구를 진행하고 있고, 최근 LLVM의 최신 버전에서 많은 버그를 발견하고 있다. 컴파일러의 특성상 우리가 발견한 버그를 유발하는 입력은 그 최적화의 유닛테스트로 쓰일 수 있으며, regression test에도 쉽게 사용되고 있다. 이 논문이 통과돼서 우리의 아이디어를 이 블로그의 글로 작성할 수 있는 날이 왔으면 한다.