int $0x80

4. Kaleidoscope: Adding JIT and Optimizer Support 한글 번역 본문

컴퓨터공부/엘엘비엠

4. Kaleidoscope: Adding JIT and Optimizer Support 한글 번역

cd80 cd80 2017.07.27 14:45

4.1. Chapter 4 Introduction

챕터3까지는 소스코드를 분석하고 이를 LLVM IR로 변환해봤습니다

이 튜토리얼은 프론트엔드 -> 최적화 -> 백엔드 순으로 진행되기 때문에, 오브젝트파일을 만드는 컴파일은 튜토리얼의 후반부에 나오게 됩니다

그래서 4,5,6,7을 거치는동안은 지금까지 한것처럼 프롬프트에 코드를 치면 바로 처리되는, 인터프리터 형식의 언어라고 생각하시면됩니다

인터프리터는 코드를 작성하면 그게 바로 실행돼서 결과를 보여주죠. 그 동작을 위해 JIT 기능을 추가 할 것입니다

그리고 컴파일 시스템이라는 구색을 맞추기 위해 최적화를 추가할텐데, 최적화 패스를 만드는법을 설명하진 않고 그냥 기존 LLVM에 구현돼있는 최적화 기법들을 불러와 사용하기만 할 것입니다



4.2. Trivial Constant Folding

(제목은 간단한 상수최적화 라고 해석하시면 됩니다)


챕터3에서 작성한 코드들은 깔끔하고, 확장하기 쉽습니다. 하지만 공학적으로 봤을 때 정말 아름다운 코드를 만들진 못합니다

사실 최적화를 직접 하지 않아도 아주 간단한 최적화는 이미 IR Builder에서 하고 있고, 그걸 이미 3장에서 봤었습니다



1+2+x 가 코드 그대로 들어가 있지 않고 3+x로 변환돼서, 즉 최적화돼서 들어가있습니다

이런 최적화 기법을 Constant Folding이라고 합니다


만약 최적화가 돼있지 않았다면


(구조를 같게하기 위해 텍스트파일에 임의로 작성했습니다)

이렇게 명령이 하나 더 추가돼서 처리가 됐겠죠


이렇게 IRBuilder에서 지원을 해주기 때문에 우리 코드에 굳이 이런 간단한 형태의 constant folding을 구현해놓을 필요는 없습니다


조금더 복잡한 예제를 볼까요

이 코드도 최적화가 잘 됐다면 %addtmp1 없이



이렇게 조금더 깔끔한 코드가 나올 수 있었을 겁니다. 하지만 IRBuilder에서 지원하는 최적화는 아주 간단한 형태만을 지원하기 때문에 한계가 명확합니다. 이를 위해서 추가적인 최적화 정책을 코드로직접 명시해주어야 합니다


LLVM은 완전 독립적인 시스템으로, 각기 다른 최적화 코드들이 어떤 형태로 배치돼도 효과적으로 돌 수 있게 돼있습니다. 최적화를 위한 LLVM 모듈들을 Pass라고 부르고, 최적화 대상에 따라 ModulePass FunctionPass BasicBlockPass 등으로 쪼개집니다


사실 그렇다고 모든 모듈들이 아무렇게나 배치돼도 똑같은 효과를 내는것은 아니고

어떤 모듈을 앞에두고 어떤모듈을 뒤에 넣었을 때 더 효과적일 때가 있고

analysis pass와 transformation pass들이 짝을 이루고 사용돼야 하는 경우도 있습니다



4.3. LLVM Optimization Passes

LLVM은 오픈소스고, 위에서 얘기한것처럼 최적화 모듈들 간의 상호 의존성이 없습니다. 필요에 의해서 의존성을 만들수는 있겠지만 자기 최적화 모듈은 자기만 신경쓰면 되도록 돼있습니다

이 장점덕분에 다른 최적화 패스에서 뭘하든지 간에 나는 내 것만 알아서 잘하면 됩니다

덕분에 되게 강력하고 다양한 최적화 패스들이 있고, 이걸 우리 컴파일러에 갖다쓰는게 굉장히 쉽습니다


그리고 언어에 특화된 최적화 패스를 구현해두면, 그 언어를 컴파일할때만 쓸수도 있는 등, 하나의 컴파일러 툴셋에서 여러 언어를 지원하면서 각 언어에 특화된 최적화를 붙이기도 쉽습니다


현재 시점에서 Kaleidoscope는 명령 한줄한줄을 그때그때 해석합니다

나중에 8장쯤 가서 바이너리 형태로 컴파일하게 되면 Module 전체에 대한 최적화를 수행하는 ModulePass를 쓰게 되겠지만, 현재 우리의 모든 코드는 함수단위로 생성됩니다

예를들어 그냥 3+4 를 쳐도 @0 이란 함수가 선언되면서 그 함수 안의 코드로 생성되죠


그래서 현재 우리거에 맞게, 우리가 어떤 코드를 작성해서 엔터를 치면 그때 FunctionPass를 실행시켜 함수별 최적화를 하겠습니다


먼저, LLVM에는 PassManager라는 클래스가 있습니다. ModulePassManager, FunctionPassManager등등 각 패스에 대한 매니져 클래스가 모두 선언돼있고, 우리는 FunctionPassManager 클래스의 한 인스턴스를 생성해서 우리 코드 최적화 패스들을 추가시켜주면 됩니다



바꿔야할부분은 총 세가지입니다

우선 Optimization.cpp를 만들어서 InitializePassManager()를 작성할거고

main.cpp에서는 module init 이후에 InitializePassManager를 실행해주는 코드를 넣을거고

CodeGen.cpp에서 함수 body생성하고나서 그 LLVM함수를 TheFPM으로 최적화할겁니다


원래 주석을 다 지우고 국문으로 설명했었는데 Optimization.cpp는 일부러 주석을 안지웠습니다

Optimization.cpp


정확하게 이해는 못했지만 튜토리얼에서 예시로 보여준 def test(x) (1+2+x)*(x+(1+2)); 이걸 최적화 하기 위해선 먼저 expression들간의 reassociation이 필요하고 Common Subexpression Elimination 을 이용해 중복되는 표현식을 최적화해야합니다. 네 저도 무슨소린지 모르겠습니다


Optimization.h


main.cpp


CodeGen.cpp


이렇게하고 

clang++ -o main *.cpp -std=c++17 `/Users/cd80/AppSolidiOS/DevAppsolidiOS/build/Ninja-ReleaseAssert/llvm-macosx-x86_64/bin/llvm-config --cxxflags --ldflags --system-libs --libs core native`

컴파일을 해봅시다



아까는 addtmp두개로 계산했던것이 최적화를 거치면서 addtmp를 하나만 만들도록 변경됐습니다


여러종류의 최적화 기법을 더 알아보고 싶으시면 이 문서를 읽어보세요. 원하는 언어나 아키텍쳐에 특화된 최적화기법을 직접 컴파일러에 추가해볼수도 있습니다



4.4. Adding a JIT Compiler

LLVM IR형태로 변환된 코드들은 되게 다양한 목적을 위해 사용될 수 있습니다

예를들어 위에서 한것처럼 LLVM 에서의 최적화를 할 수도 있고, IR을 텍스트나 바이너리 형태로 덤프해볼 수도 있고, 백엔드로 넘겨 .s나 .o로 컴파일할 수도 있습니다

혹은 이번절에서 해볼것처럼 JIT 엔진의 인풋으로써도 사용할 수 있죠

이것이 바로 중간언어를 갖는것의 이점입니다. LLVM IR은 LLVM 컴파일러 프레임워크 전체에서 "표준통화"처럼 사용되면서 컴파일러 전체가 통일성을 갖게 합니다


이전까지는 우리가 명령을 치면 그게 LLVM IR로 덤프된 것만 볼 수 있었지만, 보통 인터프리터들은 그 명령의 수행 결과까지 볼 수 있죠

이번 절에서는 그러한 인터프리터의 속성을 만족시키기 위해 JIT 기능을 우리 인터프리터에 추가시킬것입니다

예를들어 1+2를 치면 3이 나올것이고 def factorial(x) 란 함수를 선언해서 factorial(4)를 치면 24를 출력해줄겁니다


LLVM에는 MCJIT, ORCJIT가 현재로써 제일 많이 사용되고, 각각의 특징을 비교해서 자기에게 어울리는 JIT를 사용하면됩니다.

Kaleidoscope는 MCJIT를 사용해 만든 Kaleidoscope라는 커스텀 JIT 클래스를 이용해 JIT를 사용합니다


KaleidoscopeJIT는 나중챕터에서 좀더 자세히 다루고 기능을 추가해볼겁니다 우선은 그냥 갖다 쓰기만 합시다

이렇게 다운받으신 LLVM 코드베이스로 가보시면 examples/Kaleidoscope/include에 KaleidoscopeJIT.h 가 있습니다. 이걸 인클루드 하면됩니다


main.cpp를 열어 코드를 추가해줍니다



gist가 이뻐서 그렇게 보기 힘들진 않습니다

그다음에 jit를 사용해봅시다

main loop에 있는 핸들러는

HandleExtern

HandleDefinition

HandleTopLevelExpression 입니다

즉, 함수 정의, 선언이 아닌 모든 처리를 HandleTopLevelExpression에서 합니다(함수 호출 포함)


HandleTopLevelExpression에서는 먼저 현재 정의된 anonymous expression, 즉 top level expression을 갖고 있는 TheModule을 TheJIT에 추가해줍니다

이 때 JIT에서 LLVM IR이 머신코드로 변환됩니다

그다음 InitializeModuleAndPassManager는 새로운 모듈을 준비하는 함수입니다. 즉 초기화 함수입니다


그다음에 __anon_expr이라는 함수를 찾는데, 원래 Parser.cpp에서 top level expression에 이름을 주지 않았었는데 주도록합니다


그리고 anon_expr이 머신코드로 변환된 주소를 가져온 다음 호출하고 결과를 출력합니다


자, JIT가 성공적으로 잘 실행됩니다

4 + 5; 를 쳤더니 9를 출력해주고

함수 정의한걸 호출했더니 함수 코드를 실행시켜 결과를 출력해줍니다


그런데 마지막줄에서 testfunc함수가 호출이 되지 않았습니다. 그 이유는 JIT를 실행할 때 TheModule을 삭제해버렸기 때문입니다

다시말하면 함수를 정의할때까지는 TheModule이 바뀌지 않고 그대로 있지만

함수를 호출하면서 TheModule이 삭제되었기 떄문에 그 안에 있는 testfunc이 지워진겁니다

C++에 익숙하지 않으신분들을 위해 설명드리면 첫번째 실행때도 TheModule안에 있는 testfunc은 지워진 상태지만 std::move를 써서 복사를 해놓고 그 복사본으로 처리한거라서 실행이 잘 된겁니다


이 문제를 해결하기 제일 쉬운 방법은 함수 선언에 사용하는 JIT와 anon expr을 처리하는 JIT를 분리시켜 사용하는겁니다. JIT 엔진이 다르다고 해도 같은 타겟으로 설정만 돼있다면 메모리베이스가 조금 다른거는 아무런 상관이없겠죠


이렇게 하는 대신에, 우리 언어에 기능을 하나 더 추가해주면서 이 문제를 해결하는 멋있는 방법이 있습니다.

바로 함수 하나당 모듈 하나로 처리하는겁니다

이렇게하면 파이썬에서처럼 같은 이름을 갖는 함수를 여러번 선언해줄 수 있습니다. 물론 그 함수를 호출하면 가장 마지막으로 정의된 함수가 호출됩니다

그러니까 함수의 이름을 모듈의 이름으로써 사용해서, 각 함수가 독립된 공간을 갖도록 하는겁니다


이 스샷처럼 말이죠



먼저 CodeGen.cpp에 이렇게 FunctionProtos 라는 전역변수에 선언해줍니다


그리고 CallExprAST::codegen() 위에 getFunction함수를 작성해주고, CallExprAST::codegen()에서 TheModule->getFunction 을 getFunction함수로 바꿔줍니다

getFunction함수는 현재 모듈에 만약 함수가 이미 LLVM IR형태로 codegen돼있다면 그 함수를 리턴해주고, 아니라면 FunctionProtos에 그 이름으로 저장된 PrototypeAST의 codegen을 실행합니다


이부분이 함수의 중복선언을 가능하게 하는 부분이죠, FunctionProtos는 map이기 때문에 이렇게 덮어쓸수 있습니다. 이부분은 중복선언을 가능하게 하는 부분이자, 중복선언시에 마지막 함수만 호출되게 하는 부분입니다



main함수의 HandleDefinition과 HandleExtern도 바꿔줍니다.



여기까지 따라오셨으면 이제 extern함수를 호출해주는것도 해볼 수 있습니다

그런데 어떻게 sin과 cos를 자동으로 알아냈을까요?

방법은 그렇게 어렵지 않습니다, 그냥 KaleidoscopeJIT가 먼저 JIT안에서 심볼을 찾고, 심볼이 없으면 네이티브 프로세스에서까지 찾기 때문입니다

double sin(double x); 는 glibc에 선언돼있고, 우리 인터프리터의 메모리에는 glibc가 로딩돼있기 때문에, 최종적으로 glibc까지 dlsym("sin") 을 하면서 sin함수를 찾아주는겁니다


이런 symbol resolution 루틴을 바꿔서 예를들어서 제한된 몇개의 API만 JIT안에서 호출이 가능하게 한다던지, lazy binding같은 기법들을 구현해볼수 있을겁니다


현재의 symbol resolution방식덕분에 일종의 내장함수를 쉽게 구현해볼 수도 있습니다



main함수를 열어서 putchard를 아무데나 선언해보세요


그러면 이렇게 불러와서 호출해볼수도 있습니다. (a 와 b가 각각 아스키코드 97, 98에 대응됩니다)




여기까지해서 JIT와 Optimization기능을 추가해봤습니다

다음 챕터에서는 if, else, for를 Kaleidoscope 언어에 추가해보겠습니다


Chapter4.zip


신고
0 Comments
댓글쓰기 폼