LLVM #1 IR 이해 하기

llvm 은 컴파일러의 중간 단계에 위치한다. 언어 기능을 단순화한 후지만, 특정 머신 아키텍처(x86, ARM 등)를 타겟으로 하는 백엔드 이전 단계다.

llvm의 ir은 꽤 저수준이다. 일부 언어에는 있지만 다른 언어에는 없는 언어 기능을 포함할 수 없다. (예: 클래스는 c++에는 있지만 c 에는 없다.) 명령어 집합을 접해본적이 있다면 llvm ir은 RISC 명령어 집합이다.

 

결과적으로 LLVM IR은 어셈블리를 좀더 읽기 쉽게 만든 형태로 보인다. LLVM IR은 머신 독립적이므로 레지스터 개수, 데이터 타입 크기, 호출 규약이나 기타 머신별 세부사항들을 걱정할 필요가 없다. 

 

따라서 고정된 개수의 물리 레지스터 대신 LLVM IR 에서는 무제한의 가상 레지스터 세트(%0, %1, %2, %3... 로 라벨링됨)를 가지며 여기에 읽고 쓸 수 있다. 가상 레지스터를 물리 레지스터로 매핑하는 것은 백엔드의 역할이다. 

 

그리고 특정 크기의 데이터 타입을 할당하는 대신, LLVM IR 에서는 타입을 유지한다. 다시 말해 백엔드가 이 타입 정보를 받아서 데이터 타입의 크기로 매핑한다. LLVM 은 다양한 크기의 int 와 float 타입을 가지고 있다. (예: int32, int8 , int1, 포인터 타입, 배열 타입, 구조체 타입, 함수 타입 등... Type 문서 참고)

 

이제 LLVM 에는 LLVM IR 에 대해 실행할 수 있는 일련의 최적화들이 내장되어있다. (예: 죽은 코드 제거 dead-code elimination , 함수 인라이닝 function inlining, 공통 부분식 제거 common subexpression elimination 등) 이러한 알고리즘의 세부 사항은 중요하지 않다. LLVM이 구현해준다. 

 

우리가 해야할 일은 LLVM IR 을 SSA 형태로 작성하는 것이다. SSA 형태가 최적화 작성자들의 삶을 더 쉽게 만들어주기 때문이다. SSA 형태는 멋져보이지만 단순히 변수를 사용하기 전에 정의하고 변수에 한번만 할당한다는 의미이다. SSA 형태에서는 변수를 재할당할 수 없다. (예: x = x + 1) 대신 매번 새로운 변수에 할당한다. (x2 = x1 + 1) 

 

요약하자면

LLVM IR은 타입이 있는 어셈블리처럼 보이며 복잡한 머신별 세부사항은 제외된다. LLVM IR 은 SSA 형태여야하며 이것이 최적화를 더 쉽게 만든다.

 

 

factorial.bolt

function int factorial(int n){
  if (n==0) {
    1
  }
  else{
    n * factorial(n - 1)
  }
}

대응하는 LLVM IR은 다음과 같다.

 

factorial.ll

define i32 @factorial(i32) {
entry:
  %eq = icmp eq i32 %0, 0   // n == 0
  br i1 %eq, label %then, label %else

then:                                             ; preds = %entry
  br label %ifcont

else:                                             ; preds = %entry
  %sub = sub i32 %0, 1   // n - 1
  %2 = call i32 @factorial(i32 %sub) // factorial(n-1)
  %mult = mul i32 %0, %2  // n * factorial(n-1)
  br label %ifcont

ifcont:                                           ; preds = %else, %then
  %iftmp = phi i32 [ 1, %then ], [ %mult, %else ]
  ret i32 %iftmp
}