Chapter 5 Introduction
1~4장까지는 기본 언어 구조와 LLVM IR 생성을 구현하고, 최적화된 JIT(just in time) 컴파일러까지 도입하였다.
1. Kaleidoscope: Kaleidoscope Introduction and the Lexer
kaleidoscope는 아주 간단한 프로그래밍 언어이다. 함수 정의, 수학 연산, 외부 함수 호출 등 기본적인 기능만 가지고 있다.
def foo(a b)
a * a + 2 * a * b + b * b;
foo(3, 4);
kaleidoscope는 변수 선언 없이 함수 인자만으로 계산하고, 모든 값은 double type이다.
expression 기반 언어로 모든 구문이 값을 반환한다.
따라서 5장에서 다룰 if,then,else,for 모두 계산이 끝나면 하나의 값이 된다.
Lexer는 컴파일러의 첫 단계로 소스 코드를 아주 작은 단위인 Token으로 쪼개는 역할을 한다.
def fib(x) -> def, fin, (, x, )
2. Kaleidoscope: Implementing a Parser and AST
Paser는 렉서가 만든 Token을 가져와서, 토큰들이 문법적으로 어떤 구조를 가지는지 파악한다.
2, +, 3 토큰이 들어왔다면 -> 2와 3을 더하는 연산
Abstract Syntax Tree는 파서가 파악한 코드의 구조를 Tree 형태로 표현한 것이다.
+ (add)
/ \
/ \
a * (multiply)
/ \
/ \
b 2
Parse tree는 소스 코드의 모든 문법적 세부사항을 포함한다. (괄호 등)
AST는 parse tree에서 불필요한 문법 정보는 제거되고, 연산의 의미만 간결하게 표현된다.
3. Kaleidoscope: Code generation to LLVM IR
AST를 실제 컴퓨터가 이해할 수 있는 언어와 비슷한 형태인 LLVM IR로 변환한다. AST의 각 노드를 보고 그에 맞는 LLVM IR 함수를 생성하는 codegen() 함수를 구현
4. Kaleidoscope: Adding JIT and Optimizer Support
전통적인 컴파일러는 코드를 한번에 모두 기계어로 컴파일한 뒤, 실행 파일을 만들어 실행한다. Just In Time 컴파일러는 코드를 실행하는 순간, 필요한 부분만 기계어로 번역하여 바로 실행한다. 즉 입력한 코드를 즉시 컴파일하여 결과를 바로 보여줄 수 있다.
컴파일러는 LLVM IR을 받아서, 실행 중에 바로 컴퓨터가 이해할 수 있는 기계어로 바꿔준다.
하여, 컴파일 시간에 미리 5*4를 20으로 계산하여 결과로 만들 수 있다.
소스 코드 -> Clang/Clang++ 으로 IR생성(.bc , BiteCode file) -> IR 최적화 -> IR 파일 병합 -> 기계어 코드인 llc 생성 -> 실행 파일 완성
+--------------------------------------------------------------------------+
| 소스 코드 |
+--------------------------------------------------------------------------+
|
V
+--------------------------------------------------------------------------+
| 프론트엔드 (Frontend) |
| |
| [ 렉서 (Lexer) ] -> [ 파서 (Parser) ] -> [ AST 생성 ] |
| (코드를 토큰으로 분해) (토큰으로 문법 구조 분석) (코드 구조를 트리로 표현) |
| |
+--------------------------------------------------------------------------+
|
V
+--------------------------------------------------------------------------+
| LLVM IR (중간 표현 ) |
| (프론트엔드와 백엔드를 연결하는 표준 언어) |
+--------------------------------------------------------------------------+
|
V
+--------------------------------------------------------------------------+
| 백엔드 (Backend) |
| |
| [ 최적화 (Optimizer) ] -> [ 기계어 코드 생성 ] |
| (IR 코드를 더 효율적으로 변경) (특정 CPU에 맞는 코드로 변환) |
| |
+--------------------------------------------------------------------------+
|
V
+--------------------------------------------------------------------------+
| 기계어 (Machine Code) |
| (컴퓨터가 직접 실행하는 이진 코드) |
+--------------------------------------------------------------------------+
LLVM 튜토리얼은, Lexer Parser, AST을 직접 구현하고 AST를 바탕으로 LLVM IR을 직접 생성하여 최적화한다.
5장에서 제어 흐름을 구현해보도록 하자.
If/Then/else
그 전에 앞 장에서 구현했던 기능들의 확장이 필요하다.
Lexer Extension
Lexer: 새로운 keyword인 if,then,else를 인식하도록 한다.
// control
tok_if = -6,
tok_then = -7,
tok_else = -8,먼저 새로운 토큰을 정의한다. if, then, else를 키위드로 인식하여 고유한 토큰으로 처리되도록 한다.
이때 일반적인 문자(아스키 코드)는 0~255의 값을 가진다. (a=97 등)
keyword와 같이 특별한 토큰은 문자와 겹치지 않게 하기 위하여, 음수 값을 사용하게 된다.
if (IdentifierStr == "def")
return tok_def; // "def"면 tok_def 토큰 반환
if (IdentifierStr == "extern")
return tok_extern; // "extern"면 tok_extern 토큰 반환
if (IdentifierStr == "if")
return tok_if; // "if"면 tok_if 토큰 반환
if (IdentifierStr == "then")
return tok_then; // "then"면 tok_then 토큰 반환
if (IdentifierStr == "else")
return tok_else; // "else"면 tok_else 토큰 반환
return tok_identifier; // 위에 해당 안 되면 그냥 식별자 토큰 반환이후 입력 문자열이 if/then/else 중 하나이면 해당 토큰을 반환한다.
AST Extension
기존에는 숫자,변수,사칙연산 등의 표현식만 처리할 수 있는 AST 클래스만 있었다.
- AST Class? : 코드가 트리로 바꿔주는 설계도
새로운 IfExprAST 라는 클래스를 만들어,
조건
참일 때
거짓일 때
각각의 표현식을 트리의 자식 노드로 저장할 수 있게 해주자.
class IfExprAST : public ExprAST {
std::unique_ptr<ExprAST> Cond, Then, Else;
public:
// if문을 파싱할 떄 cond,then,else 부분의 AST를 만들어 생성자에 전달,
IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
std::unique_ptr<ExprAST> Else)
// 전달받은 포인터의 소유권을 std::move로 해당 객체로 이동
: Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}
Value *codegen() override; // codegen : AST노드를 LLVM IR 코드로 생성.
};IfExprAST는 ExprAST의 자식 노드이다. 즉, if,then,else 구문 또한 하나의 Expression으로 표현한다는 뜻이다. kaleidoscope는 statment가 없다. 따라서 C언어의 삼항 연산자와 같이 조건을 boolean "값" 으로 해석한다.
예를 들어
if x<3 then 1 else 2
ExprAST : x<3 (조건)
ExprAST : 1 (참인 경우)
ExprAST : 2 (거짓인 경우)
IfExprAST 객체는 파싱이 끝난 후 코드의 구조를 메모리에 저장하기 위하여 존재한다.
Paser Extension
/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
getNextToken(); // 'if' 토큰을 소비
// 조건식 파싱
auto Cond = ParseExpression();
if (!Cond)
return nullptr;
// 'then' 토큰 확인 및 소비
if (CurTok != tok_then)
return LogError("expected then");
getNextToken();
// then 부분 파싱
auto Then = ParseExpression();
if (!Then)
return nullptr;
// 'else' 토큰 확인 및 소비
if (CurTok != tok_else)
return LogError("expected else");
getNextToken();
// else 부분 파싱
auto Else = ParseExpression();
if (!Else)
return nullptr;
// IfExprAST 노드 생성
return std::make_unique<IfExprAST>(std::move(Cond), std::move(Then), std::move(Else));
}소스 코드에서 부분을 parsing 한다. -> IfExprAST를 실제로 생성하는 코드
현재 토큰 스트림에서 if 키워드를 발견했을때, if/then/else 구문 전체를 재귀적으로 파싱한다.
paser에서 if토큰을 인식하면 ParseIfExpr을 호출하기 위하여
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (CurTok) {
default:
return LogError("unknown token when expecting an expression");
case tok_identifier:
return ParseIdentifierExpr();
case tok_number:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
case tok_if:
return ParseIfExpr();
}
}현재까지의 과정을 정리하면
1. parser가 if라는 token을 만남
2. ParserIfExpr 호출 -> if/then/else 구문 전체 파싱
3-1. cond 조건식을 파싱하기 위해 ParseExpression 호출 : 조건식에 대한 ExprAST 객체 생성
3-2. then
3-3. else
4. ParseIfExpr 함수는 3개의 ExprAST 객체를 사용하여 -> IfExprAST 생성
5. IfExprAST 객체를 호출한 곳으로 반환
LLVM IR Extension
llvm에서 제어 흐름은 Basic Block과 Branch 명령어를 통하여 구현된다.
- Branch 명령어 : 실행 흐름을 한 블록에서 다른 블록으로 이동시킨다.
- Conditional Branch: 조건에 따라 두 블록 중 하나로 분기
- Unconditional Branch: 항상 특정 블록으로 이동
Basic Block
Basic Block (BB) : 분기 없이 순차적으로 실행되는 명령어들의 묶음
Entry block: 진입 블록, if의 조건식을 평가 -> 참/거짓 결과에 따라 then블록으로 갈지 else블록으로 갈지 결장하는 conditional branch 명령어로 끝난다.
Then block: then 부분의 IR 코드를 포함. -> 끝에 if문 전체가 끝난 후 Merge block으로 이동하는 무조건 분기 명령어로 끝난다.
Else block: else 부분의 코드 포함 -> 끝에 Merge block으로 이동하는 무조건 분기 명령어로 끝남.
Merge Block: then과 else 두 갈래의 블록이 하나로 합쳐지는 지점
- Kaleidoscope는 항상 값을 결과로 내놓아야 함. then블록의 결과 혹은 else 블록의 결과 중 어떤 것을 최종 결과로 선택할지 반환. 이때 사용하는 것이 아래의 phi 노드이다.
PHI Node
then과 else 중 어떤 경로를 거쳐왔는지에 따라 결과 값을 선택해야 한다.
PHI노드는 어떤 기본 블록에서 왔느냐에 따라, 다른 값을 취하는 특별한 명령어이다.
if/then/else는 항상 어떤 값을 반환해야 함 -> merge 블록에서 then/else 블록 각각의 결과 중 적절한 값을 선택해야 한다.
entry:
; x != 0.0 인지 비교하여 참/거짓(i1) 값을 얻는다
%ifcond = fcmp one double %x, 0.0
; %ifcond 값에 따라 then 또는 else 블록으로 분기한다
br i1 %ifcond, label %then, label %else
then: ; "then" 블록
%calltmp = call double @foo() ; foo() 함수의 결과를 얻는다
br label %ifcont ; 병합 블록으로 점프한다
else: ; "else" 블록
%calltmp1 = call double @bar() ; bar() 함수의 결과를 얻는다
br label %ifcont ; 병합 블록으로 점프한다
ifcont: ; "병합" 블록
; PHI 노드: then에서 왔으면 %calltmp를, else에서 왔으면 %calltmp1을 값으로
선택한다
%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
ret double %iftmp ; 선택된 값을 반환한다
%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
만약 ifcont 블록에 then 블록을 거쳐서 왔다면 -> %calltmp
else 블록 -> %calltmp1
SSA (Static Single Assignment)
각 변수 할당마다 유일한 1회용 이름을 부여
왜?? 모든 정의를 한번만 사용하여, 분석이 간단해진다.
왼쪽 그래프에서
B0는 if문의 분기점이다. B1,B2로 분기하여 최종적으로는 Merge Block에서 y에 x를 대입한다.
x라는 동일한 이름이 여러 번 사용되고, B3에서 y에 어떤 x 즉 3인지 5인지 분명하지 않다. 제어 흐름에 따라 x라는 값이 달라진다.
LLVM-IR은 레지스터들은 오른쪽 그림과 같은 SSA 이다.
B1에서 x0를 사용하고, B2에서 x1을 사용한다.
B3에서 x2에 파이 노드 φ(x0, x1) 를 할당하여 y에 x2를 대입한다.
B1에서 왔다면 x0, B2에서 왔다면 x1을 선택
이렇듯 제어 흐름이 합쳐지는 지점에서 PHI 노드를 사용하여 각 경로에서 온 값을 명확히 구분하고, 모든 변수 사용이 단 하나의 정의만을 참조하여 분석이 보다 쉬워진다.
example
//def baz(x) if x then foo() else bar(); 변환
declare double @foo()
declare double @bar()
define double @baz(double %x) {
entry:
%ifcond = fcmp one double %x, 0.000000e+00
br i1 %ifcond, label %then, label %else
then: ; preds = %entry
%calltmp = call double @foo()
br label %ifcont
else: ; preds = %entry
%calltmp1 = call double @bar()
br label %ifcont
ifcont: ; preds = %else, %then
%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
ret double %iftmp
}
코드 생성의 핵심 개념
•조건 분기(Branch):
fcmp one 명령으조건을 평가하고, br 명령으로 then/else 블록으로 분기
•then/else 블록:
각각의 블록에서 필요한 연산(여기서는 함수 호출)을 수행한 후, 공통 블록(ifcont)으로 이동
•PHI 노드:
ifcont 블록에서는 PHI 노드를 사용해, 어떤 경로에서 왔는지에 따라 값을 선택하여 반환. SSA(Static Single Assignment)
C++ 코드로의 매핑 (핵심 로직)
IfExprAST::codegen()
1.조건식 코드 생성:
조건식을 평가하여 Value*를 얻고, fcmp 명령을 사용해 0.0과 비교(불리언 변환)
2.분기 생성:
LLVM IR에서 CreateCondBr를 이용해 then/else 블록으로 분기하는 명령을 추가
3.then/else 코드 생성
각각의 블록에서 AST 하위 노드의 codegen을 호출하여 값을 생성합
4.PHI 노드 생성
두 블록의 결과 값을 PHI 노드로 결합하여 if/then/else 전체의 결과로 반환
Code generation Extension
앞서 봤던 ifExprAST의 codegen 메서드는 다음과 같다.
Value *CondV = Cond->codegen();
if (!CondV)
return nullptr;
// 0.0과 같지 않은지 비교하여 조건을 bool로 변환
CondV = Builder->CreateFCmpONE(
CondV, ConstantFP::get(*TheContext, APFloat(0.0)), "ifcond");
Function *TheFunction = Builder->GetInsertBlock()->getParent();
// then과 else 케이스를 위한 블록을 생성 'then' 블록은 함수 끝에 삽입
BasicBlock *ThenBB =
BasicBlock::Create(*TheContext, "then", TheFunction);
BasicBlock *ElseBB = BasicBlock::Create(*TheContext, "else");
BasicBlock *MergeBB = BasicBlock::Create(*TheContext, "ifcont");
Builder->CreateCondBr(CondV, ThenBB, ElseBB);Builder는 LLVM IR 코드를 효율적으로 삽입할 수 있도록 하는 도구,,
1. 현재 함수 포인터 얻기
Function *TheFunction = Builder->GetInsertBlock()->getParent();- Builder는 지금 "어느 함수, 어느 블록"에 명령어를 만들고 있는지 기억함
- GetInsertBlock()으로 "지금 명령어가 쌓이는 블록"을 찾고
- getParent()로 이 블록이 소속된 함수를 얻음
- 결과: TheFunction에는 현재 명령어를 넣는 함수 포인터가 들어옴
2. then 블록 만들면서 함수에 바로 넣기
BasicBlock *ThenBB = BasicBlock::Create(*TheContext, "then", TheFunction);- 새 블록을 만들 때 함수 포인터(TheFunction)를 같이 넘김
- so, ThenBB는 만들어짐과 동시에 함수에 소속(즉, 블록 리스트에 바로 포함)
- 블록 이름 붙여주면 IR 읽을 때 눈에 잘 띔
3. else/merge 블록 만들기
BasicBlock ElseBB = BasicBlock::Create(TheContext, "else");
BasicBlock MergeBB = BasicBlock::Create(TheContext, "ifcont");
- 함수 포인터 없이 만듦 -> 떠있는? 블록으로 생성
- 분기 명령 또는 코드 생성 과정에서 해당 블록들이 함수에 자동으로 연결된다..
ex)
Builder->CreateCondBr(CondV, ThenBB, ElseBB);
// 조건분기 명령 생성: 조건에 따라 ThenBB나 ElseBB로 점프
즉시 함수에 넣고 싶은 블록은 함수 포인터까지 넣어 생성
나머지 블록? 나중에 함수에 자동 편입될 수 있도록 그냥 만들어두기
Then BB 만 함수에 바로 삽입하는 이유는, 명백히 해당 함수에 속한다는 것을 보여주기 위함으로 동작 상 차이는 없다.
과정을 요약하면 다음과 같다.
- if 이전 상태
[ Function: main ]
+----------------------------------+
| entry: |
| ... |
| ... |
| <-- Builder 커서 위치 |
+----------------------------------+- 세 블록 생성 직후
[ Function: main ]
+----------------------------------+
| entry: |
| ... |
| ... |
| <-- Builder 커서 위치 ` |
+----------------------------------+
| then: |
| |
+----------------------------------+
[ 허공에 떠 있는 블록들 ]
+----------------------------------+ +----------------------------------+
| else: | | ifcont: |
| | | |
+----------------------------------+ +----------------------------------+- CreateCondBr(...) 실행 후
[ Function: main ]
+----------------------------------------------------+
| entry: |
| ... |
| br i1 %ifcond, label %then, label %else |
+----------------------------------------------------+
| |
+----(참일 때)-------->|
| |
+----(거짓일 때)------>+------------------------+
| |
V V
+--------------------------+ +--------------------------+
| then: | | else: |
| | | |
+--------------------------+ +--------------------------+
[ 허공에 떠 있는 블록 ]
+----------------------------------+
| ifcont: |
| |
+----------------------------------+- 모든 코드 생성 완료 후
[ Function: main ]
+----------------------------------------------------+
| entry: |
| ... |
| br i1 %ifcond, label %then, label %else |
+----------------------------------------------------+
| |
+------(참)---------->|
| |
+------(거짓)-------->+------------------------+
| |
V V
+--------------------------+ +--------------------------+
| then: | | else: |
| ... (then 로직) | | ... (else 로직) |
| br label %ifcont | | br label %ifcont |
+--------------------------+ +--------------------------+
| |
+---------(점프)------> |
|
+---------(점프)------>+
|
V
+--------------------------+
| ifcont: |
| %val = phi ... |
| ... |
+--------------------------+
// then 값 생성
Builder->SetInsertPoint(ThenBB);
Value *ThenV = Then->codegen();
if (!ThenV)
return nullptr;
Builder->CreateBr(MergeBB);
// 'Then'의 codegen이 현재 블록을 바꿀 수 있으므로, PHI를 위해 ThenBB를 업데이트
ThenBB = Builder->GetInsertBloc
그리고 then 블록 코드를 생성한다. 빌더의 명령어 삽입 위치를 then 블록으로 설정하여 여기서부터 the블록에 명령어가 삽입된다. 이후 then 부분이 참일 때의 식을 재귀적으로 IR 생성한다.
llvm IR은 모든 기본 블록이 return이나 branch같은 제어 흐름 명령으로 무조건 종료되어야 한다. then 블록을 마무리하기 위하여, merge 블록으로 무조건 분기하는 명령어를 작성하고,
ThenBB = Builder->GetInsertBlock();
merge블록에서 PHI 노드를 생성할 떄, PHI가 어떻게 동작할지 블록/값 쌍 설정.
// else 블록 생성
TheFunction->insert(TheFunction->end(), ElseBB);
Builder->SetInsertPoint(ElseBB);
Value *ElseV = Else->codegen();
if (!ElseV)
return nullptr;
Builder->CreateBr(MergeBB);
// 'Else'의 codegen이 현재 블록을 바꿀 수 있으므로, PHI를 위해 ElseBB를 업데이트
ElseBB = Builder->GetInsertBlock();
// merge 블록 생성
TheFunction->insert(TheFunction->end(), MergeBB);
Builder->SetInsertPoint(MergeBB);
PHINode *PN =
Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, "iftmp");
PN->addIncoming(ThenV, ThenBB);
PN->addIncoming(ElseV, ElseBB);
return PN;else 블록의 코드 생성 또한 then 블록과 같다.
