Introduction to LLVM (2)

Photo by dylan nolte on Unsplash

Introduction to LLVM (2)

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

6. LLVM Compiler System

  • For Compiler Developer, 컴파일러를 만들기 위한 모듈화된, 재사용 가능한 컴포넌트들을 제공 -> 컴파일러 제작 시간, 비용 등을 절감
    • Intermediate Representation(IR)이 매우 잘 정의되어 있음.
    • 깔끔한 구조, 고품질의 컴포넌트가 풍부.
    • C, C++, Objective-C, Swift 등의 프로덕션 레벨 컴파일러의 기반.
    • LLVM JIT, OpenMP RT, AMD OpenCL 등도 LLVM 기반.
    • LLVM Debugger도 굉장히 좋음. (교수님: 내가 GCC 보다 LLVM을 더 좋아하는 이유)
    • 새로운 컴파일러를 만들고 싶을 때, 오직 프로그래밍 언어를 LLVM IR로 변환하는 Language Front-end만 구현하면 나머지 컴포넌트를 그대로 사용할 수 있음.
  • For Compiler User, e2e compiler를 제공, 다양한 언어와 플랫폼을 지원.

7. LLVM IR의 특징

  • 단일 형식 IR의 이점
    • 2000년에 나온 SGI Pro64 Compiler를 예를 들자면, Fortran, C/C++, Java등의 언어를 4가지 형식의 IR을 사용하여 Binary를 생성했다. Loop 최적화 뒤에 Global 최적화가 끝나면, 다시 Loop 최적화를 할 수 없다. => 임의의 analyses, transformations 시퀀스가 불가능.
    • LLVM IR은 단일 형식 => 원하는 만큼, 원하는 순서대로 최적화 패스를 돌릴 수 있음.
  • LLVM IR의 목표
    • 생산하기, 이해하기, 정의하기 쉬워야 한다.
    • LLVM내의 대부분의 컴포넌트에서 사용/활용 가능한 형식이어야 한다.
    • 언어와 타겟에 독립적이어야 한다.
    • 다양한 analyses와 transformations를 지원해야 한다.
      • a = a * 2a = a << 1로 바꾸는 저수준의 최적화부터, 사용되지 않는 코드를 지우는 고수준의 최적화까지 모두 지원할 수 있는, 표현력이 풍부한 형식이어야 한다.
  • LLVM IR의 특징
    • Typed Virtual Instruction Set으로 설계됨.
    • RISC와 유사한 3-어드레스 코드 (Three-address Code)
    • Virtual Register의 개수에 제한이 없음

8. LLVM IR 기본

int g = 5;

int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

위 코드를 다음과 같은 bash 명령어로 LLVM IR로 변환할 수 있다.

clang-7 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -emit-llvm -c factorial.c
opt-7 -mem2reg factorial.bc -o factorial.mem2reg.bc
llvm-dis-7 factorial.mem2reg.bc -o factorial.mem2reg.ll
  • clang-7: LLVM Front-end for C
    • -O0: Optimization zero. 최적화를 수행하지 않음.
    • -Xclang: 이 옵션 뒤로 따라오는 파라미터는 clang compiler에게 넘길 녀석들.
    • -disable-o0-optnone: Opt zero를 적용하면 output function에 모두 optnone이라는 태그가 붙음. 이게 붙은 함수들은 LLVM 최적화 대상에서 제외됨. 우리가 비록 zero optimization을 수행하긴 하지만, 이후에 수동으로 최적화 패스들을 적용하고 싶은 상황이므로 optnone이 붙는 것을 피하고 싶음.
    • -fno-discard-value-names: input source code의 변수명을 그대로 유지해줌.
    • -emit-llvm: 이게 없으면 바로 executable binary 생성됨.
    • -c factorial.c: input source code + language
  • opt-7: LLVM Middle-end
    • -mem2reg: 메모리 변수들을 가상 레지스터에 할당해준다. [gist]gist.github.com/adoji92/288556fac5eff7b5d0b.. 와 같은 코드가 있을 때, load a, load b 수행하고, c 계산해서 다시 store하고, 다시 load c, load d 수행해서, e 계산해서 다시 store하는 것이 f.bc 였다면, 그걸 좀 더 똑똑하게 바꿔준다.
    • f.bc -o f.mem2reg.bc: 앞이 input llvm bitcode, 뒤가 output.
  • llvm-dis-7: LLVM Dis-assembler
    • LLVM Bitcode (=.bc)는 binary 파일이다.
    • llvm-dis는 bc파일을 사람이 읽을 수 있는 LLVM IR 형식으로 변환해준다.

위 bash 명령어로 생성된 LLVM IR은 다음과 같다.

; ModuleID = 'factorial.mem2reg.bc'
source_filename = "tests/factorial.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@g = dso_local global i32 5, align 4

; Function Attrs: noinline nounwind uwtable
define dso_local i32 @factorial(i32 %n) #0 {
entry:
  %cmp = icmp eq i32 %n, 1
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  br label %return

if.end:                                           ; preds = %entry
  %sub = sub nsw i32 %n, 1
  %call = call i32 @factorial(i32 %sub)
  %mul = mul nsw i32 %n, %call
  br label %return

return:                                           ; preds = %if.end, %if.then
  %retval.0 = phi i32 [ 1, %if.then ], [ %mul, %if.end ]
  ret i32 %retval.0
}

attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 7.0.1-svn348686-1~exp1~20190104180606.53 (branches/release_70)"}

처음과 끝에는 설정, 메타데이터들이 담겨있다. @g로 시작하는 부분부터가 우리가 작성한 factorial.c의 int g = ...로 생각하면 된다. 하나 하나 천천히 시작해보자.

@g = dso_local global i32 5, align 4
  • LLVM IR에서 변수는 @ 또는 %로 시작하는데, @로 시작하는 변수는 전역변수라는 뜻이다.
  • i32는 이 변수의 타입, 5는 이 변수에 대입할 값, align 4는 4 byte를 넣겠다는 뜻이다.
  • dso_local은 여기를 참고.

여기서 의문인 점은 i32에서 4 byte를 쓴다는 것이 너무나 자명한데, 왜 굳이 또 쓰냐는 것. 내 생각에는 모든 LLVM 변수들은 포인터이고, 포인터가 몇 바이트를 먹냐는 부분 아닐까. align 4가 다른 의미를 갖진 않는 것 같고... -> 링크

define dso_local i32 @factorial(i32 %n) #0 {
entry:
  %cmp = icmp eq i32 %n, 1
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  br label %return

if.end:                                           ; preds = %entry
  %sub = sub nsw i32 %n, 1
  %call = call i32 @factorial(i32 %sub)
  %mul = mul nsw i32 %n, %call
  br label %return

return:                                           ; preds = %if.end, %if.then
  %retval.0 = phi i32 [ 1, %if.then ], [ %mul, %if.end ]
  ret i32 %retval.0
}

위 코드는 우리가 작성한 factorial의 IR이다.

  • define: 함수를 선언할 때는 define으로 시작한다.
  • i32 @factorial: JavaScript, Scala는 함수 내에 함수를 선언할 수 있다. C, C++는 문법 수준에서 모든 함수가 global이기 떄문에 factorial 앞에 골뱅이가 붙었다. 반환 타입이 int이므로 i32가 붙었다. #0는 이 함수가 사용할 attribute을 명시하는 것인데, factorial.mem2reg.ll의 끝 부분에 있는 그 attributes #0를 가리킨다.
  • 이제 @factorial{, curly bracket ,안에 있는 %로 시작하는 지역 변수들은 curly bracket 바깥에서 보이지 않는다. (= 지역 변수들의 scope는 curly bracket 내부로 한정된다.)
  • entry:: Basic Block

그 외에는 기본적인 RISC Assembly를 해본 사람이라면 어렵지 않게 읽을 수 있다. 다만, phi 부분은 이해가 되지 않을 수도 있는데, phi는 어떤 basic block으로부터 진입했는가에 따라서 다른 값을 골라주는 함수라고 보면 되며, LLVM이 SSA Form을 달성하기 위해 사용하는 트릭이라는 것... 정도만 알아두고 여기서는 넘어가자.

9. LLVM IR Type

  • Basic Concepts
    • class같은 개념은 없지만 struct같은 개념은 있다.
    • 다양한 type간의 casting을 허용한다.
  • Void Type
    • 값도 없고 물리적으로 차지하는 공간도 없다.
  • Integer Type
    • i1: 1비트 정수 타입, boolean
    • i16: 16비트 정수 타입.
    • i32: 32비트 정수 타입.
  • Floating-point Type
    • half: 16-bit float.
    • float: 32-bit float.
    • double: 64-bit float.
    • fp128: 128-bit float.
  • Array Type
    • [엘리먼트 개수 x 엘리먼트 타입] 의 형식.
    • [40 x i32]: 32비트 정수 40개짜리 배열
    • [3 x [4 * i32]]: 32비트 정수의 3 * 4 배열
  • Structure Type
    • { 타입 리스트 }: 일반적인 struct 타입.
    • <{ 타입 리스트 }>: c에서의 union 타입. (packed struct)
    • { i32, i32, i32 }: 세 개의 32비트 정수를 갖는 struct.
  • Function Type
    • C에서 함수 프로토타입같은 개념.
    • return type + parameter types을 가진다.
    • i16 (i32): 32비트 정수 하나를 인수로 받아 16비트를 반환하는 함수 타입.
    • {i32, i32} (i32): 32비트 정수 하나를 인수로 받아 두 개의 32비트 정수를 갖는 struct 타입을 반환하는 함수 타입.
  • Pointer Type
    • <타입> *
  • Vector Type
    • C++의 #include <vector>로 쓸 수 있는 그 벡터 말고, SIMD에 쓰이는 그 Vector의 레지스터에 들어갈 피연산자.
    • <4 x i32>: 네 개의 i32를 갖는 벡터

10. LLVM Program Structure

  • Module: Function, 전역 변수를 갖는다.
  • Function: 인수, Basic Block을 갖는다.
  • Basic Block: instruction의 목록을 갖는다.
  • Instruction: opcode와 operands로 이루어진다.

11. LLVM Compiler Passes

이전에 살펴봤던 analysis, transformation pass로 나뉘어졌던 pass 말고, 적용 범위에 따른 분류를 알아본다.

  1. Module Pass: general interprocedural pass
  2. Call Graph SCC Pass: bottom-up pass on the call graph
  3. Function Pass: processes one function at a time
  4. Loop Pass: processes on loop a time (from innermost to outermost nested loop)
  5. Basic Block Pass: processes a basic block at a time
  6. Region Pass: processes a single-entry single-exit portion of the CFG
  7. Machine Function Pass: part of the LLVM code generator, executes on machine-dependent representation of functions. Derived from Function pass.

  • 만들어진 pass는 등록 후에 사용할 수 있다.
  • 어떤 pass는 특정 선행 pass가 필요할 때도 있다.
    • 분석 정보가 있어야, transformation pass를 진행할 수 있으니까.
  • 어떤 pass는 이미 진행된 analysis pass를 무효화 하기도 한다.
    • Control Flow Graph를 떠 놓음 -> Dead Code Elimination -> 이전에 있던 instruction들이 없어졌으니 CFG 무효화.

3편에서 이어가겠습니다.