Introduction to LLVM (3)

이 포스트는 2019년 1월 20일에 발행되었습니다.

12. Static Single Assignment (SSA) Form

어디서 어떤 변수가 선언/사용되고 있는지 추척하는 것이 최적화의 주된 질문 중 하나.

x = y + 1;
z1 = x + k1;

if (z == 0) a = 0;
else a = 1;

x = a + 1;
z2 = x + k2

위와 같은 상황에서는 if를 전후로 x의 역할이 바뀐다. Line 1의 x와 Line 7의 x는 전혀 연관이 없다. 이런 경우에는 두 변수를 구분해줘야 LLVM이 변수의 선언/사용을 추적하는 게 더 쉽지 않을까? 극단적인 상황을 가정해보자. 하나의 int 변수로 서로 다른 10개의 역할을 코드에서 사용한다면 과연 컴파일러가 그 변수를 최적화하는 것이 쉬울까? 하나의 void *로 서로 다른 10개의 역할을 과연 최적화할 수 있을까? 이러한 이유로 LLVM에서 SSA Form으로 모든 변수들을 다루는 것을 선호하며, SSA Form으로의 이주는 이름 있는 최신 컴파일러라면 모두 지원하고 있는 형식이기도 하다. SSA Form을 사용하는 컴파일러 목록 (위키피디아) SSA Form: 프로그램의 모든 변수에 최대 한 번만 값이 할당(Assignment)하는 것.

12.1 Phi(Φ) Function

if (foo) v = 1;
else v = 2;

x = v + 1;

위의 C코드를 우리의 현재 지식으로 SSA Form으로 바꾸면 다음과 같다.

if (foo) v1 = 1;
else v2 = 2;

x = v? + 1;

여기서 v? 가 어떤 값이 될지는 전적으로 foo 값에 의존한다. 이런 경우 LLVM은 Phi 함수를 사용하여 다음과 같은 형태로 바꾼다.

if (foo) v1 = 1;
else v2 = 2;

v3 = phi(v1, v2);
x = v3 + 1;

이전 장에서 간단하게 훑고 넘어갔던 그 함수 맞다. 어떤 Basic Block으로부터 Instruction에 도달했냐에 따라 다른 값을 고르게 된다.

12.2 Phi Function in Detail

변수에 한 번만 값이 할당된다는 것의 의미를 좀 더 뜯어보자. 코드를 기반으로 Control Flow Graph를 그린 뒤에 변수 x의 선언(= Def)을 시작으로 하고, 변수 x의 사용(= Use)을 끝으로 하는 화살표를 모두 그려보자. 우리의 ssa2.c 코드를 기준으로 v에 도달하는 화살표가 2개인 것을 확인할 수 있을 것이다. 그리고 SSA Form에서는 모든 변수에 도달하는 Def가 한 개만 존재해야 하기 때문에 Phi 함수가 고안된 것이다. Phi 함수의 사용으로 우리는 분기의 병합지점에서 SSA Form을 유지할 수 있다. 쉽게 말하자면, v? 같은 변수가 나오는 경우 Phi 함수를 사용하자.

12.3 Pros and Cons

장점
- 변수 하나 = Def 하나라는 구조적 특성에서 몇몇 최적화가 더 쉬워진다.
- 희소(Sparse)하다. Def-Use를 모두 탐색한다는 것은 Pseudo-polynomial하기 때문에 Def-Use Matrix가 Sparse해질 수록 Pruning이 많아진다.
단점
- struct, array에 대해서는 적용 불가 (scalar에 대해서만 실용적)
- scalar에 대한 pointer에도 쓰기 힘듦
- phi는 실제로 구현되어있지 않기 때문에 기계어를 생성할 때 변환이 필요함 (어려운 일은 아님)

12.4 SSA in LLVM

Clang으로 처음 만들어진 IR은 SSA Form이 아닌, 간단하며 최적화되지 않은 코드
sroa, mem2reg 등의 최적화 패스를 거치면 SSA Form으로 바뀜
물론 포인터 연산 등으로 명시적인 Addressing이 이뤄지는 경우는 제외됨

13. LLVM Classes

StringRef: LLVM이 사용하는 문자열 클래스.
- char *는 너무 구식이고, std::string는 너무 느림
- LLVM의 어떤 함수가 StringRef를 파라미터로 받을 때, string literal이나 std::string 둘 다 넘길 수 있음
- StringRef.str()를 사용하면 std::string 객체를 얻을 수 있음
outs(): std::cout이 너무 느려서 따로 만듦
errs(): std::cerr가 너무 느려서 따로 만듦
std::endl: 없음. \n을 쓸 것
심지어 C++ STL에 있는 클래스들은 너무 제너럴한 녀석들이라며, 특정 상황에서 더 나은 구현체를 따로 만들어서 사용함 => LLVM이 성능에 얼마나 미쳐있는지 잘 보여주는 부분.
- BitVector, SmallBitVector, StringMap, SparseSet 등...
- STL을 그대로 가져다 써도 큰 문제는 없지만 JIT 돌리면 확실히 느림.
Basic Instruction methods:
- eraseFromParent(): 있던 자리에서도 없애고, reference도 다 없앰
- removeFromParent(): 있던 자리에서 없애지만, reference는 살려둠. 다른 곳에 다시 끼워넣지 않으면 null function pointer가 되니 주의
- moveBefore, insertBefore, insertAfter... 등도 있고,
- replaceInstWithValue(), replaceInstWithInst() 도 있음

Appendix A. Final Project

기회가 된다면 내가 어떤 Final Project를 제안했었고 어떤 실패를 했는지 별도의 글로 정리해보려다가, 넘나 부끄러워져서 그냥 여기에 짧게 소개만 해보는 정도로 만족해볼까 한다.

long a = 1;
long b = 2;
long c = a + b;

char x = 1;
char y = 2;
char z = x + y;

위 코드를 보자. 1, 2, 3은 64bit 정수 타입을 써야할 만큼 큰 정수가 아니다. 이런 경우에 Overflow, underflow가 일어나지 않을 만큼 타입의 범위를 낮추면 어떨까? 따라서, overflow가 없음이 확실한 special case에 해당하는 조작된 배열을 하나 초기화한다. 짝수개의 길이를 갖는 배열이고,

a[i] = random_divided_by_SHRT_MAX;
a[i + 1] = -a[i];

와 같은 특성을 갖게 하여 배열의 모든 요소들을 합했을 때 0이 나오는 zerosum array를 int8_t, int16_t, int32_t, int64_t 4개의 타입에 대해 생성한 뒤에 루프를 사용해서 다 더해보는 하드코딩 벤치마크를 짜봤다.

template <class T>
T sum(T* arr, int n) {
    T sum = 0;
    for (in i = 0; i < n; ++i) {
        sum += arr[i];
    }
    return sum;
}

template <class T>
T* generate_zerosum_array(int n) {
    if (n % 2 != 0) throw "n must be even!";
    T* arr = new T[n]();
    for (int i = 0; i < n; i += 2) {
        arr[i] = static_cast<T>(rand() % SHRT_MAX);
        arr[i + 1] = -arr[i];
    }
    return arr;
}

template <class T>
void benchmark(string name, int arr_len) {
    auto begin = clock();
    cout << "Start generation" << endl;
    auto arr = generate_zerosum_array<T>(arr_len);
    auto end = clock();
    auto elapsed = double(end - begin) / CLOCKS_PER_SEC;
    cout << "End generation, elapsed " << fixed << elpased << endl;

    begin = clock();
    auto res = sum<T>(arr, arr_len);
    end = clock();
    elapsed = double(end - begin) / CLOCKS_PER_SEC;

    cout << name << " sum: " << res << ", elapsed " << fixed << elapsed << endl;
    delete[] arr;
}

int main(int argc, char** argc) {
    srand((unsigned int) time(0));
    cout.unsetf(ios::floatfield);
    cout.precision(20);

    int arr_len = atoi(argv[1]);
    benchmark<int8_t>("int8_t", arr_len);
    benchmark<int16_t>("int16_t", arr_len);
    benchmark<int32_t>("int32_t", arr_len);
    benchmark<int64_t>("int64_t", arr_len);

    return 0;
}

길이 500,000,000의 zerosum_array의 벤치마크 결과는 다음과 같다.

	Generation avg.	Computation avg.
8bit	1.7973842	0.244892
16bit	1.9260221	0.052441
32bit	2.1577346	0.102552
64bit	2.6699116	0.2026716

놀랍게도 작은 크기의 타입이 더 빠르게 계산되는 것을 볼 수 있었다. 하지만, 정해지지 않은 값에 대해서는 overflow 가능성을 사전에 예측하기란 불가능에 가까웠고, 이미 값을 알고 있는 변수에 대해서는 타입의 크기를 줄이기 보다는 미리 계산해버리는 Scalar Evolution이 오히려 더 적합한 최적화였다. 결국 결말은 탁상공론같은 Term Project Proposal이였던 걸로. 그 외에는 8bit 배열을 초기화할 때 0b10101010 8개를 메모리에 올리는 대신 64bit 0b1010101010101010101010101010101010101010101010101010101010101010를 한 번에 넣는 것이 어떨까 + 64bit 정수를 한 번에 하나씩 store하지 말고 코어개수만큼 병렬적으로 올리면 어떨까 => 로도 접근해봤었다. (벤치마크에 생성 시간을 측정했던 이유)

하지만... 이 또한 LLVM IR만을 이용해서 멀티스레딩을 해야하는 부분이라, OpenML 라이브러리를 같이 섞어쓰는 것을 강제하거나 LLVM을 포크한 프로젝트, Tapir-LLVM를 이용해야 깔끔하게 구현할 수 있을 것 같아서 포기했다. 뭐 어쨌든, 둘 다 프로그램의 주요 병목이 되는 루프(=배열)을 최적화하려한 시도, 그리고 일말의 실현가능성으로 행복회로를 돌려만 봤다는 것. 하하...

Appendix B. Further Readings

그 뒤로는 CFG에서의 Dominance 개념, Post-dominance 개념을 이용하여 Loop Simplification 하는 방법, Aggressive Dead-code Elimination을 하는 방법등을 배웠고, 등차/등비수열과 비슷한 개념을 가져와서 Scalar Evolution의 이론적 배경과 구현 방법을 배웠다. 고등학생 때 배웠던 계차수열의 향수를 대학원 수업에서 느낄 줄은. 수업 하나 하나가 길어지면서 교수님이 맨 처음에 구성하셨던 실러버스를 다 따라가지 못했지만, Memory hierarchy optimizations, Recent advances in compiler optimizations등의 챕터가 더 준비되어 있었다는 것만 언급하고 Introduction to LLVM 포스팅을 마친다. 원래 2019년에 들어서는 존댓말로 글을 써보려고 했었다. 비록 1편이 1월 12일에 첫 업로드가 되었지만 첫 타이핑을 시작한 것은 2018년이였고, 형식과 구성을 여러차례 뒤엎어서 포스팅이 늦어졌다. 그래서 부득이하게 LLVM 포스팅들은 그냥 반말로 진행했다. 끼얏호우!

여기까지 읽어주신 분이 있다면 부족한 글을 읽어주시느라 고생 많으셨다는 감사의 말씀을 드리고 싶고, 아울러 1편의 글머리에서 밝혔 듯 대부분의 문장과 개념, 코드는 번트 벅스텔러 교수님의 강의자료를 참고하여 씌여졌다는 것을 다시 한 번 밝힌다.

olaf.kr