대학원생을 위한 LLVM

출처 : LLVM for Grad Students (Adrian Sampson) (일어번역판) 大学院生のためのLLVM

LLVM에 대해 개괄적으로 설명한 문서 중에 입문용으로 가장 적합한 것 같아서 번역합니다.

영어 원문과 일어 번역판을 동시에 참고해가면서 번역합니다.

 

본업이 따로 있기 때문에 주말에 틈틈히, 천천히 번역합니다. 원문에 있는 하이퍼링크들은 번역이 완료되면 여기에도 최대한 구현합니다.

 

 

-------------------------

 

 

이 글은 LLVM 컴파일러를 기반으로 리서치를 하고자 하는 사람을 위한 입문서입니다. 컴파일러에 대해 전혀 관심이 없는 사람도 LLVM을 즐겁게 사용하면서 좋은 성과를 낼 수 있을 것 입니다.

 

LLVM이란 무엇인가.

LLVM은 매우 훌륭하고, 해킹하기 쉬우며, 시대를 앞서가고 있는 C/C++과 같은 네이티브 언어를 위한 컴파일러입니다.

물론 LLVM이 훌륭하기 때문에 더 많은 기능에 대해 들을 수 있을 것 입니다.(JIT이 될 수도 있고 C계열이 아닌 언어에서 대응 가능하다든가, APP Store에서 새로운 배포 형태 라든가 등등...) 물론 전부 사실입니다만 이 글의 목표를 위해서는 위에 기술한 정의가 가장 중요합니다.

 

LLVM이 이 외의 컴파일러와 차별화되는 이유에는 몇개의 중요한 특징이 있습니다.

 

- LLVM의 중간표현(IR)은 훌륭한 혁신기술입니다. LLVM은 어셈블리 언어를 읽을 수 있다면 실제로 읽을 수 있는 프로그램 표현으로서 기능합니다. 이것이 대단하게 느껴지지 않을지도 모릅니다만 실제로는 대단한 것입니다. 다른 컴파일러들의 IR은 in-memory구조를 가지고 있어서 너무나 복잡하기 때문에 글로 쓰기 힘듭니다. 이것이 다른 컴파일러가 이해가기 어렵고 이식하는 것이 복잡한 이유입니다.

- LLVM은 잘 쓰여있습니다. 이것의 아키텍쳐는 다른 컴파일러보다 훨씬 더 모듈화 되어있습니다. 이런 장점이 가능했던 이유는 우리 중의 한명이기도 한 첫 개발자 덕분입니다.

- LLVM은 우리같이 이리저리 옮겨다니는 학문적인 hacker들의 리서치용 툴로 사용 될 뿐만 아니라 지구상에 가장 큰 기업에 의해 서포트되고 있는 산업적으로도 강한 컴파일러입니다. 이것은 자바에서 HotSpot까 Jikes사이에서 고민하듯이 훌륭한 컴파일러와 해킹가능한 컴파일러 사이에서 고민하지 않아도 된다는 것을 뜻합니다.

 

대학원생이 왜 LLVM을 신경써야 하는가

 LLVM은 좋은 컴파일러입니다. 하지만 컴파일러에 대한 공부가 아니라면 왜 이것을 신경써야 할까요?

 

컴파일러 인프라는 여러분이 프로그램에 관련된 무언가를 할 때마다 유용합니다. 내 경험에서 이런 경우는 매우 많죠. 당신은 프로그램이 얼마나 무언가를 자주 행하는지 분석하거나, 당신의 시스템에 맞춰서 더 효율적으로 일하도록 변경하거나, 당신의 새로운 아키텍쳐나 OS를 실제로 새로 칩을 찍어보거나 커널 모듈을 쓰지 않고도 마치 사용하고 있는 것 처럼 만들 수 있습니다. 대학원생에게 있어서 컴파일러 인프라는 사람들이 보증하는 것보다 더 적합한 수단입니다. 당신이 다음 툴들을 사용해야할 더 나은 이유가 있기 전까지는 LLVM을 기본적으로 사용해보길 바랍니다.

- 아키텍쳐 시뮬레이터

- Pin과 같은 dynamic binary instrumentation tool

- source-level transformation (sed와 같은 간단한 것에서부터 AST 파싱과 직렬화와 같은 것을 행하는 복잡한 툴들까지)

- system call들을 중간에 가로채기 위한 커널 해킹

- hypervisor 비슷한 무언가들

당신의 작업에 완벽하게 알맞지 않는 것처럼 보이더라도 source-to-source변환에 비하면 90%는 더 빨리 원하는 지점에 도달할 수 있습니다.

 

컴파일러와 깊은 관계까지는 아닌 연구 프로젝트에 LLVM을 적용해 효과적이었던 예는 다음과 같습니다.

- UIUC의 Virtual Ghost는 오류가 있는 OS kernel로부터 프로세스들을 보호하기 위해 컴파일러 패스를 사용할 수 있다는 것을 보여주었습니다.

- UW의 CoreDet는 멀티스레드 프로그램이 deterministic한 결과를 내도록 했습니다.

- 우리의 approximate computing 연구에서는 LLVM 패스를 프로그램에 에러를 내기 쉬운 하드웨어를 시뮬레이션 하는데 사용합니다.

 

다시 한번 강조하건대 LLVM은 단순히 새로운 컴파일러 최적화를 적용하기 위한 것이 아닙니다.

 

구성요소

여기에 그린 것은 LLVM 아키텍쳐의 주요 구성요소입니다. (모던 컴파일러 아키텍쳐이기도 합니다.)

여기에는

- 프론트 엔드 : 소스 코드를 중간 언어 혹은 IR로 불리는 언어로 변환시킵니다. 이 변환은 컴파일러의 나머지 부분이 해야 하는 일을 단순화 시킵니다. C++소스 코드의 복잡함을 더이상 고려하지 않아도 되기 때문이죠. 과감한 대학생인 여러분은 Clang을 수정하지 않고 사용함으로써 이부분은 해킹할 필요가 없을 것입니다.

- pass들 : IR에서 IR로 변환합니다. 일반적인 상황에서 패스들은 코드를 최적화합니다 - 즉, IR을 입력으로 받아 더 빠른 IR을 산출물로 내놓습니다. 이것이 여러분이 해킹해야하는 부분입니다. 여러분의 research용 도구는 컴파일 과정에 따라 IR을 따라가거나 바꾸게 됩니다.

- 백 엔드 : 실제 기계어 코드를 만들어내는 부분입니다. 이 부분은 건드릴 필요가 없습니다.

 

비록 이것이 근대의 대부분의 컴파일러의 구조라고 하더라도 LLVM만의 특별한 점은 봐 둘 필요가 있습니다. 프로그램들은 이 과정에서 동일한 IR을 사용합니다. 다른 컴파일러들에서 각 pass는 고유의 형태로 된 코드를 생성합니다. LLVM은 정 반대의 접근을 했고 이것은 해커들에게 매우 유용했습니다 : 우리는 우리의 코드가 어떤 환경에서 돌아가는 신경 쓸 필요가 사라졌습니다. 프론트엔드와 백엔드 사이의 어디쯤에서 돌아갈 것이란 것만 알면 됩니다.

 

 

시작하기

그럼 해킹을 시작해보도록 합시다.

 

LLVM 받기

LLVM을 설치해야 합니다. Linux 디스트리뷰션 중에는 LLVM와 Clang을 제공하는 것들이 있습니다. 하지만 당신이 해킹할 모든 헤더파일들을 가지고 있는 버젼인지 확인해야 합니다. Xcode에 따라오는 OS X빌드 같은 경우는 충분하지 않습니다. 다행스럽게도 CMake를 이용해 LLVM을 빌드하는 것은 ㅡ그다지 어렵지 않습니다. 일반적으로 LLVM자체를 빌드하기만 하면 됩니다 : 버젼이 맞는 한 시스템이 제공한 Clang이 잘 작동 할 것입니다. (물론 Clang을 빌드하기 위한 절차도 있습니다.)

OS X에 한해서는 Brandon Holt씨가 빌드를 잘 하기 위한 과정을 올려주었습니다. Homebrew formula또한 존재합니다.

 

레퍼런스를 읽읍시다.

문서들을 가까이 할 필요가 있습니다. 다음 링크들은 반복해서 참고할 만 합니다.

● 자동으로 만들어진 Doxygen 페이지는 매우 중요합니다. 여러분은 LLVM을 해킹하는 동안 조금이라도 나아가기 위해선 이 API 페이지들을 계속 파야 합니다. 이 페이지들은 검색이 힘드니 구글을 통해 들어가는 것을 추천합니다. 아무 함수나 클래스 이름에 'LLVM'을 붙여서 검색하면 Google은 보통 Doxygen 페이지를 찾아줍니다. (여러분이 조금만 부지런하다면 LLVM을 칠 필요도 없이 LLVM 결과를 맨 처음 가져오도록 만들 수도 있습니다!) 이것이 이상하게 들릴 수도 있습니다만, 살아남기 위해서는 LLVM의 API 문서 여기저기를 찾아다녀야 합니다 - 그리고 API를 찾아다니는 더 나은 방법을 저는 찾지 못했습니다.

● Language reference manual은 LLVM IR의 덤프를 보는데 문법이 헷깔린다면 참고하기 편합니다.

● programmer's manual은 LLVM 특유의 자료 구조의 toolchest를 설명하고 있습니다. 이는 효과적인 string, map이나 vector를 위한 STL의 대체재 등을 포함합니다. 또한 시시각각 마주치게 될 fast type introspection 툴들(isa, cast 그리고 dyn_cast)에 대한 설명도 있습니다.

● 여러분의 pass가 어떤 일을 할 수 있는지 궁금할 때마다 Wriring an LLVM Pass 튜토리얼을 읽는 것이 좋습니다. 여러분은 어디까지나 연구자이지 매일매일 컴파일러를 해킹하는 사람은 아니기 때문에 이 글의 몇몇 디테일에 관한 부분은 중요하지 않다고 봅니다. (가장 크게는 Makefile을 기반으로 한 빌드 시스템 명령을 스킵하고 바로 CMake를 기반으로 한 'out-of-source' 명령을 바로 보는 것이 좋습니다.) 하지만 그럼에도 불구하고 일반적인 pass에 관해서는 가장 고전적인 자료입니다.

● GitHub 미러는 온라인에서 LLVM소스를 보는데 편리합니다.

 

Pass를 만들어봅시다.

LLVM을 사용하여 생산적인 연구를 하기 위해서는 일반적으로 pass를 수정 할 필요가 있습니다. 이 섹션에서는 그때그때 프로그램을 변경할 수 있는 간단한 pass를 빌드하고 실행하는 과정을 설명합니다.

 

Skeleton

실용적이지 않은 LLVM pass가 있는 템플렛용 레포지터리를 만들어 놓았으므로 여기서부터 시작하겠습니다. 처음부터 시작하려면 build configuration의 설정이 어려울 수 있습니다.

GitHub에서 llvm-pass-skeleton 레포지터리를 clone합니다.

$ git clone https://github.com/sampsyo/llvm-pass-skeleton.git

실제 작업은 skeleton/Skeleton.cpp파일에서 이루어집니다. 따라서 이 파일을 열어줍니다. 실제 작업이 진행되는 공간은 아래와 같습니다.

virtual bool runOnFunction(Function &F) { errs() << "I saw a function called " << F.getName() << "!\n"; return false; }

LLVM pass에는 여러 종류가 있습니다만, 우리는 function pass라는 pass를 사용합니다. (처음 시작하기에 좋은 pass입니다.) 여러분이 생각하는 바와 같이 LLVM은 우리가 컴파일하려는 프로그램에서 함수를 만날때마다 위 함수를 실행합니다. 지금은 단순히 이름을 프린트하기만 합니다.

 

추가 설명:

● err()라고 되어있는 것은 LLVM이 제공하는 C++ output stream으로 console창에 출력하는데 사용할 수 있습니다.

● 함수 F를 수정하지 않았기 때문에 false를 리턴합니다. 이후로 프로그램을 변형하는 경우에는 true로 리턴해야 합니다.

 

빌드하기

CMake를 이용해 pass를 빌드합니다.

$ cd llvm-pass-skeleton $ mkdir build $ cd build $ cmake .. # Generate the Makefile. $ make # Actually build the pass.

LLVM이 전역으로 설치되어있지 않다면 CMake에게 어디에서 찾아야 하는지 지정해줘야 합니다. LLVM_DIR 환경변수 안에 LLVM이 있는 share/llvm/cmake/ 디렉터리 중 하나를 경로로 지정합니다. Homebrew의 경로의 예는 다음과 같습니다.

$ LLVM_DIR=/usr/local/opt/llvm/share/llvm/cmake cmake ..

pass를 빌드하면 공유 라이브러리를 생성하게 됩니다. build/skeleton/libSkeletonPass.so나 플랫폼에 따라서는 그와 비슷한 이름에서 이를 찾아볼 수 있습니다. 다음 단계에서는 이 라이브러리를 불러와서 실제 코드 위에서 실행시켜 보겠습니다.

 

실행하기

새로운 Pass를 실행시키기 위해선 C 프로그램에서 clang을 불러와 방금 컴파일 한 공유 라이브러리를 가리키는 특수한 플래그를 사용합니다.

$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.* something.c I saw a function called main!

이 -Xclang -load -Xclang path/to/lib.so를 사용하면 Clang 상에서 여러분의 pass를 읽어와 활성화 시킬 수 있습니다. 보다 큰 프로젝트를 처리 할 필요가 있다면 Makefile의 CFLAGS나 사용 중인 빌드 시스템 상의 CFLAGS의 동등한 것에 이 argument를 더해주면 됩니다.

(clang에서 불러들이지 않고 pass를 한번에 실행하는 방법도 있습니다. 이는 LLVM의 opt 커맨드를 쓰는 것인데, 공식 문서에도 기술되어있는 것이지만 이 글에서는 다루지 않습니다.)

축하합니다. 컴파일러의 해킹이 완료되었습니다! 앞으로는 이 hello-world pass이 프로그램에 재미있는 동작을 하도록 확장시켜보겠습니다.

 

LLVM IR 이해하기

LLVM을 가지고 프로그램들을 다루기 위해서는 IR의 구조를 조금 알아야 합니다.

모듈은 함수를 포함하고 이 함수들은 BasicBlock들을 가지고 있고 BasicBlock들은 명령들을 가지고 있습니다. 모듈을 제외한 것들은 Value에서 파생된 것들입니다.

 

컨테이너

LLVM 프로그램에서 가장 요소들의 개요는 다음과 같습니다.

● 모듈은 크게 봤을 때는 소스 파일, 전문적인 용어로는 translation unit을 의미합니다. 다른 모든 것은 모듈 안에 포함되게 됩니다.

● 가장 특징적인 것으로 모듈은 함수를 가지고 있습니다. 함수는 이름 그대로 실행 가능한 코드의 묶음입니다. (C++에서는 함수와 미소드 둘 다 LLVM 함수를 가리킵니다.)

● 함수명이나 인수의 선언 등은 제외하고, 함수는 주로 BasicBlocks들을 가지고 있습니다. Basic block은 컴파일러에서는 유명한 개념입니다만 우리의 목적을 위해서는 명령의 집합이라고만 알아둡시다.

● 그리고 이 명령은 단일 코드 연산자입니다. 추상화의 정도는 크게 RISC 계열의 기계언어와 같습니다. 명령의 예로는 정수의 덧셈, 실수의 나눗셈, 혹은 메모리에의 저장 등이 있습니다.

 

LLVM에서 대부분의 것-함수, BasicBlock, 그리고 명령 등을 포함하여-은 다방면에서 쓰이는 Value라는 클래스를 상속받습니다. Value는 숫자나 코드의 주소 등 계산에 사용될 수 있는 값들 모든 것을 포함합니다. 글로벌 변수나 정수('5'와 같은 리터럴들)도 Value 입니다.

 

명령

LLVM IR에서 사람이 읽을 수 있는 형식의 명령의 예는 다음과 같습니다.

%5 = add i32 %4, 2

이 명렁은 (i32라는 타입에서 알 수 있는)32비트 정수 값 두개를 더합니다. %4가 가리키는 4번 레지스터 안의 숫자와 2가 가르키는 정수 2를 더합니다. 그리고 그 결과값을 5번 레지스터 안에 저장합니다. 이것이 제가 LLVM IR이 이상적인 RISC 기계어 코드처럼 보인다고 하는 이유입니다. 레지스터와 같은 동일한 용어를 사용합니다. 하지만 무한개의 레지스터가 존재합니다.

 

이 명령은 컴파일러 안에서 C++ 클래스인 명령의 인스턴스로서 나타납니다. 객체에는 명령 코드(opcode)가 있고 opcode는 덧셈, 타입, 그리고 다른 Value 객체의 포인터인 operand들의 리스트들을 가지고 있습니다. 위 명령의 경우, 이는 상수 객체인 숫자 '2'를 가리키고 다른 명령은 레지스터 %4를 가리킵니다. (LLVM IR이 static single assignment 형식을 가지고 있기 때문에, 레지스터와 명령들은 사실상 하나 뿐이고 같습니다. 레지스터 숫자는 텍스트로 표현하기 위해 인공적으로 만들어집니다.)

 

만약 당신이 만든 프로그램의 LLVM IR을 보고 싶다면 Clang을 이용해 이를 만들어낼 수 있습니다.

$ clang -emit-llvm -S -o - something.c

 

Pass 안에서 IR 살펴보기

작업하고 있던 LLVM IR로 되돌아 가 봅시다. 우리는 dump()라는 일반적이면서 편리한 메소드를 통해 중요한 IR 객체들을 모두 살펴볼 수 있습니다. 이것은 사람이 읽을 수 있는 형태로 IR객체들을 출력해줍니다. 우리들의 Pass가 함수 단위를 가져오기 때문에 dump를 각 함수의 BasicBlocks, 그리고 각 BasicBlock들의 명령어들에 대해 반복하게 만드는데 사용 해 봅시다.

 

다음은 이 작업을 하기 위한 코드입니다. llvm-pass-skeleton의 git repository에서 체크아웃 하면 됩니다.

errs() << "Function body:\n"; F.dump();   for (auto& B : F) { errs() << "Basic block:\n"; B.dump();   for (auto& I : B) { errs() << "Instruction: "; I.dump(); } }

C++11의 멋진 자동 type과 foreach 문법을 사용하면 LLVM IR의 계층 구조를 더 간단하게 탐색할 수 있습니다.

 

pass를 다시 한번 빌드하고 이를 통해 프로그램을 실행한다면 여러 부분의 IR들이 우리가 직접 traverse하는 것처럼 분기하는 것을 볼 수 있습니다.

 

Pass를 이용해 좀 더 재밌는 것 하기.

 여러분이 프로그램에서 패턴을 찾아내고 이 패턴을 찾을 때 코드를 바꾸게 만들면 마법같은 일이 일어나게 됩니다. 간단한 예는 다음과 같습니다 : 우리가 모든 함수 안의 첫번째 binary operator(+, - 등)를 *로 바꿔본다고 합시다. 왠지 쓸모있을 것 같지 않나요?

그것을 하게 만드는 코드는 다음과 같습니다. 이 버젼은 실제로 실험해볼 수 있는 프로그램과 함께 llvm-pass-skeleton의 the mutate branch에서 가져올 수 있습니다.

for (auto& B : F) { for (auto& I : B) { if (auto* op = dyn_cast<BinaryOperator>(&I)) { // Insert at the point where the instruction `op` appears. IRBuilder<> builder(op);   // Make a multiply with the same operands as `op`. Value* lhs = op->getOperand(0); Value* rhs = op->getOperand(1); Value* mul = builder.CreateMul(lhs, rhs);   // Everywhere the old instruction was used as an operand, use our // new multiply instruction instead. for (auto& U : op->uses()) { User* user = U.getUser(); // A User is anything with operands. user->setOperand(U.getOperandNo(), mul); }   // We modified the code. return true; } } }

 

해설:

● dyn_cast<T>(p)는 LLVM 고유의 introspection utility입니다. 동적 타입 테스트를 효율적으로 하기 위해 LLVM codebase에 있는 몇개의 convention 들을 사용합니다. 컴파일러들은 이런 convention들을 항상 지켜야만 합니다. 이 construct(dyn_Cast를 가리킴)는 이것이 Binary Operator가 아니라면 null pointer를 리턴합니다. 따라서 이런 경우에 사용하지 매우 좋습니다.

● IR Builder는 코드를 만들기 위해 사용합니다. 여기에는 여러분이 만드려는 코드들을 만들기 위한 수많은 방법들이 있습니다.