Introduction to LLVM (1)

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

이번 학기에 고급 컴파일러 설계를 수강했습니다. 물론, 대학원 수업이기 때문에 형식적으로 “고급”이 붙었을 뿐이라 정말 완벽하게 고급진 내용은 아니였지만 LLVM의 구조, 철학, 사용하고 있는 이론적 배경 등을 배우는 수업이였기에 LLVM 소개글 정도로 포스팅의 목적을 정했어요. 수업에서 배운 내용을, 그리고 교수님이 내주셨던 과제와 개인이 제안해서 진행했던 과제들을 수행하면서 겪었던 시행착오들을 정리해 봅니다. 대부분의 내용은 Bernd Burgstaller 교수님의 2018년 2학기 CSI8015-01을 정리한 내용임을 미리 밝혀둡니다.

1. 역사

  1. 진공관과 케이블, 천공카드로 코딩하던 시절이 있다. 이 때는 코드를 재활용한다는 개념이 없었다.
  2. 기계어 등장.
  3. 그 뒤에는 기계어를 어셈블리어로 1:1 매핑해 사용하기 시작했고 기계어에 비해 사람이 이해하기 쉬운 코드였지만, 큰 코드베이스에서는 소스를 관리하기 힘들었고 다른 아키텍쳐로 이식하기도 힘들었다.
  4. 그 뒤에 고급 프로그래밍 언어(High-Level Programming Language)가 등장했다. 그와 동시에 컴파일러(Compiler)도 같이 고안됐다.
    1. Source code => Assembly code (by compiler)
    2. Assembly code => Machine code (by assembler)

2. 기초

  • 컴파일러는 다음과 같은 기능을 수행할 수 있어야 한다.
    1. 유효한 프로그램과 유효하지 않은 프로그램을 구분할 수 있어야 한다.
    2. 정확하고 (바라건대) 효율적인 코드를 생성해야 한다.
    3. 생성된 코드를 사용자가 실행할 수 있어야 한다.
  • 컴파일러를 세 가지 부분으로 구분해본다면,
    1. 프론트엔드 (Front-end): 소스코드를 분석하여 Intermediate Representation(IR)을 생성한다.
    2. 미들엔드 (Middle-end): 주어진 IR를 최적화한다.
    3. 백엔드 (Back-end): 주어진 IR을 바탕으로 기계어를 생성한다.
  • 프론트엔드
    1. Source code => Tokens (by Lexical Analyzer)
    2. Tokens => Abstract Syntax Tree(AST) (by Syntax Analyzer)
    3. AST => Decorated AST (by Semantic Analyzer)
    4. Decorated AST => IR (by Intermediate Code Generator)
  • 미들엔드
    1. IR => IR (by various Optimizers)
  • 백엔드
    1. IR => IR (by Instruction Selection)
    2. IR => IR (by Register Allocation)
    3. IR => Target Code (by Instruction Scheduling)
  • LLVM IR의 특징
    1. LLVM IR의 표현력이 매우 우수하다.
    2. 2000년에 나온 SGI Pro64 Compiler 같은 경우에는, 네 가지 종류의 IR을 사용했고, 이는 반복적인 최적화(Iterative Optimization)를 막는 주요한 원인이다.
    3. LLVM이 단일 형식의 IR을 사용하는 것은 꽤나 대단한 일이며, LLVM은 이것을 표현력이 풍부한 Single Static Assignment (SSA) Form을 이용하여 달성함.
    4. Perform machine-independent optimizations in Middle-end, and machine-dependent opts in Back-end.

3. 최적화

  • 실행시간 = 명령어 개수 * CPI
  • 최적화를 하기 위해서는
    1. 명령어 개수를 줄이거나,
    2. 비용이 큰 작업을 작은 작업으로 치환하거나,
    3. 병렬로 수행해야 한다.
  • LLVM 최적화 패스(Pass)에는 두 가지 종류가 있다.
    1. 분석(Analysis)
    2. 변형(Transformation)
    3. 우리말로 적어놓으니 너무 이상해서 이건 영어로...
  • Analysis Pass
    1. 프로그램을 분석하여 특징을 뽑아낸다.
    2. 안전하고(safe), 회의적인(pessimistic) 가정이 기본
  • Transformation Pass
    1. 분석 결과를 바탕으로 프로그램을 향상시킨다.
  • Pass를 두가지로 나눠놓은 이유
    • 같은 Analysis Pass 분석결과를 여러 Transformation Pass에서 가져다 쓰기 때문에
    • 즉, 코드의 직교성(Orthogonality)을 높이기 위해
  • Control Flow Graph (CFG)
    1. Control Flow: 각 statements, instructions, 또는 function call들이 실행/평가되는 순서
    2. Basic Block: instruction, statements 따위의 순서 있는 묶음
    3. CFG: Basic Block들을 Control Flow(= edge)로 연결한 그래프
  • 최적화 범위
    1. Local
      • 하나의 Basic Block에 대해서만 수행
      • 다른 BB의 내용은 건드리지 않음
    2. Intra-procedural
      • 하나의 함수에 대해서만 수행
      • Local 최적화로는 수행할 수 없는 것들을 여기다가
    3. Inter-procedual
      • 프로그램 전체에 대해 수행
      • 많은 최적화 포인트가 생겨남과 동시에 어려움도 많아짐

4. 기초적인 최적화

4.1 Procedure Cloning

분기가 많은 코드일 수록 성능이 낮다. 다음 코드의 t() 함수는 if-statement를 가지고 있다. 컴파일 타임에서 분기가 예측 가능한 경우에, 그 분기를 없애기 위해 분기했을 때 실행되는 코드를 가지고 새로운 함수를 만드는 최적화 기법이다.

private static int[] data = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

public static void t(int i, int x) {
    if (i < 5) data[i] = i * x;
    else data[i] = -x;
}

public static void main() {
    int x = 100;
    t(1, x); // A
    t(5, x); // B
    int y = getFromUserSomehow();
    t(y, x); // C
}

위 코드에서 AB는 함수 t의 첫 번째 파라미터가 상수로 주어졌기에 컴파일 타임에 분기를 예측할 수 있다.

public static void t_1(int x) {
    data[1] = x;
}
public static void t_5(int x) {
    data[5] = -x;
}

따라서 위와 같은 함수를 추가적으로 만들어서 분기를 삭제할 수 있다.

  • 하지만, 최신 프로세서는 분기 예측도 꽤나 잘 맞는 편이며, 이렇게 Procedure Cloning을 남발하여 바이너리의 instruction이 많아지는 경우, I-Cache의 miss rate가 올라가기 때문에 무조건적으로 적용해서는 안된다고 한다.
  • 또한 main() 가장 마지막에 보이는 C 부분은 컴파일 타임에 알 수 없는 경우에 해당, 최적화 할 수 없다.

4.2 Common Subexpression Elimination

i = 0;
while (i < m) {
    j = 0;
    while (j < n) {
        temp = Base(a) + i * n + j;
        *(temp) = *(Base(b) + i * n + j) + *(Base(c) + i * n + j);
        j += 1;
    }
    i += 1;
}

위 식에서 i * n + j가 반복적으로 계산되고 있다. 이를 t1 = i * n + j와 같이 밖으로 빼내어 t1 변수를 사용하는 것이 더 빠르다.

i = 0;
while (i < m) {
    j = 0;
    while (j < n) {
        t1 = i * n + j; // Changed
        temp = Base(a) + t1; // Changed
        *(temp) = *(Base(b) + t1) + *(Base(c) + t1); // Changed
        j += 1;
    }
    i += 1;
}

4.3 Loop Invariant Detection

4.2절의 마지막 코드 예제에서 i * n은 inner while loop의 iteration마다 계산되고 있지만, 그 값은 모두 같다. 이런 값을 Loop Invariant라고 부르며, 이런 값들을 루프 밖으로 빼주는 것이 더 좋다.

i = 0;
while (i < m) {
    j = 0;
    t2 = i * n; // Changed
    while (j < n) {
        t1 = t2 + j; // Changed
        temp = Base(a) + t1;
        *(temp) = *(Base(b) + t1) + *(Base(c) + t1);
        j += 1;
    }
    i += 1;
}

4.4 Strength Reduction

4.3절의 코드에서는, t2 is incremented by n for each iteration. 이 경우 매 번 곱셈을 하는 것 보다는 n씩 늘리는 식으로 바꾸는 것이 더 좋다. (Target Architecture에 따라 다를 수는 있겠지만, 대부분의 프로세서에서 곱셈보다 덧셈이 더 가벼우니까)

i = 0;
t3 = 0; // Changed
while (i < m) {
    j = 0;
    t2 = t3; // Changed
    while (j < n) {
        t1 = t2 + j;
        temp = Base(a) + t1;
        *(temp) = *(Base(b) + t1) + *(Base(c) + t1);
        j += 1;
    }
    i += 1;
    t3 += n; // Changed
}

4.5 Copy Propagation

4.4절의 코드에서 이상한 낌새를 느꼈을 것이다. 왜 굳이 t3를 새로 만들지? 질문에 바로 대답하는 대신, 최적화 과정을 더 따라가보자. 이 최적화는 어떤 변수의 값이 항상 다른 변수와 같은 경우를 찾아서 바꿔주는 역할만을 수행한다.

i = 0;
t3 = 0;
while (i < m) {
    j = 0;
    t2 = t3;
    while (j < n) {
        t1 = t3 + j; // Changed
        temp = Base(a) + t1;
        *(temp) = *(Base(b) + t1) + *(Base(c) + t1);
        j += 1;
    }
    i += 1;
    t3 += n;
}

4.6 Dead Code Elimination

이제 저 지겨운 t2를 지워보자. 더 이상 쓰이지 않는 변수를 찾아내서 지우는 부분이다. 4.5절의 코드 예제에서 t2 = t3;부분, 그리고 코드에서 보이지 않지만, 위에 있을 변수 선언 부분 int t2; 등이 사라지게 된다. 코드는 생략한다.


지금까지 알아본 6개의 기본적인 최적화 패스들은 모두 Transformation Pass이다. 각 절마다 쓰이지 않는 변수를 찾아내서, 어떤 변수의 값이 항상 다른 변수와 같은 경우를 찾아서 라고 짧게 언급하고 지나간 부분들이 Analysis Pass이며, Call sites 찾기, Available Expression Analysis, Induction Variable Detection, Copy Analysis, Live Variable Analysis등의 Analysis 통해 필요한 정보를 수집하여 Transformation Pass를 실행한다.

5. 객체지향 언어를 위한 최적화

class Point {
public:
    int x, y;
    void move(int x, int y) { ... }
    virtual void draw() { ... }
}

class ColorPoint: public Point {
public:
    int color;
    void draw() { ... }
    void setColor(int c) { ... }
}

Point p = new ColorPoint();
p.move(3, 5); // A
p.draw(); // B

위와 같은 C++ 코드를 살펴보자. B에서 draw()를 호출하면 ColorPoint Class에 있는 Virtual Method Table 포인터에서 VMT를 불러오고, 다시 거기서 draw()를 가리키는 포인터로부터 draw()를 받아와 실행한다. C++에서는 가상 함수에 대해서, Java에서는 모든 메소드에 대해 위와 같은 dispatch overhead가 존재하며, 이는 컴파일 타임에 해결될 수 있으며, 이와 같은 최적화를 Devirtualization이라 한다. 이 외에도 getter, setter가 많이 쓰인 경우에 유용한 Inlining,잠깐 살아있는 heap allocated variable들을 stack으로 바꾸는 등의 최적화 또한 수행할 수 있다.


코드가 들어가니 많이 길어지네요. 끊고 2편에서 이어가겠습니다.