int $0x80

5. Kaleidoscope: Extending the Language: Control Flow 한글 번역 본문

컴퓨터공부/엘엘비엠

5. Kaleidoscope: Extending the Language: Control Flow 한글 번역

cd80 cd80 2017.08.03 16:51

5.1. Chapter 5 Introduction

챕터 1 ~ 4에서는 Kaleidoscope 언어를 처음부터 구축해서 lexer, parser를 만들고 AST를 만든뒤 LLVM IR로 변환하고, 여기에 최적화와 JIT를 추가시켜 실행결과를 눈으로 볼 수 있는데까지 해봤습니다


Kaleidoscope는 아직 실제로 사용할 정도로 완성되진 않았습니다. 언어의 모든것을 정의하고 처음부터 모든것을 구현하면 난이도가 높아지고 지루해질 수 있기 때문에 최소한의 기능만을 정의하고 시작했던것입니다.

사실 LLVM 프레임워크의 구조를 보면 우리는 Frontend 구현을 모두 했고, Optimizer까지 구현했습니다. 그다음에 Backend만 구현하면 Kaleidoscope 컴파일러는 구현이 완료된것이죠

그러나 백엔드를 구현하기전에 언어를 조금더 완성시키기 위해 5,6,7장에서는 언어에 여러가지 기능을 추가합니다


이번 장에서는 Control Flow를 조금더 보완할것입니다. 지금까지 Kaleidoscope에는 call과 return만 있었고 if, else, for 문 등이 없었습니다

이번글에서 이 if, else, for를 추가해보겠습니다



5.2. If/Then/Else

언어에 새 기능을 추가하는것은 그렇게 어렵진 않습니다

한 기능을 추가하기 위해 어떤곳을 변경하면되는지가 명확하기 때문이죠

첫째로 Lexer에서 if, then, else에 대한 토큰을 만들어 처리하고

Parser에서 각각에 대한 AST노드를 만들어 전체 AST에 통합될 수 있도록 하고

CodeGen에서 새로 추가된 AST클래스들의 codegen메소드를 구현해 LLVM IR로 변형해주면 됩니다

그 다음일은 LLVM Optimizer와 백엔드가 알아서 해줄거기 때문에 이렇게만 하면 언어에 기능 추가하는건 바로 끝입니다


이 기능들을 실제로 구현하기 앞서 구현된 후에 어떻게 보일지 먼저 슥 볼까요



지금까지 Kaleidoscope에서 함수를 선언할 때도 별도의 return문 없이 그냥 표현식(expression)이 함수의 결과값이 됐습니다

여기서도 if문의 조건이 만족되면 then 후에 나오는 expression이 리턴값으로 사용되고 아니라면 else문 후에 나오는 expression이 리턴값으로 사용됩니다

그러니까 사실 우리의 if/then/else 문은 C언어로 치면 삼항연산자 같은 역할을 하는 겁니다




참고로 우리 언어에는 이미 비교연산자는 구현돼있습니다. BinaryExpr에 들어가있죠

3 < 5 는 true기 때문에 1.0이 리턴되고, 5 < 3 은 false기 때문에 0.0이 리턴됩니다

그러나 반대 방향인 3 > 5; 는 > 가 정의되지 않았기 때문에 에러가 났죠

>를 추가하는건 어렵지 않을겁니다


저는 한번 추가해봤습니다. 단순 이항연산자를 추가하는건 되게 쉽네요


팁을 드리자면 main.cpp와 CodeGen.cpp를 수정하면 되고

main.cpp에서는 BinOpPrecedence['>'] = 10; ('<'도 10으로 설정돼있음) 을 추가하고

CodeGen.cpp에서는 BinaryExprAST::codegen()에서 case '>' 을 추가해서 case '<'을 그대로 복붙한뒤

L과 R의 위치만 바꾸시면 됩니다




5.2.1. Lexer Extensions for If/Then/Else

이항연산자를 추가할땐 Lexer를 건들 필요는 없습니다. 이항연산자는 "expression"으로써 처리되기 때문이죠(BinOpPrecedence에서 가져올수 있냐 없냐를 기준으로 BinOp인지 Identifier인지 구분)

그러나 If Then Else와 같은 문법적인 요소를 추가할 땐 별도의 토큰을 두고 처리해줘야 합니다


Lexer.h


Lexer.cpp에도 추가해줍니다



5.2.2. AST Extensions for If/Then/Else

우리의 if문은 if문만 단독으로 나올 순 없고 항상 if-then-else 의 구조를 가집니다

따라서 ifexpr thenexpr elseexpr같은게 아니라 IfExprAST에서 if, then, else를 모두 갖고 있는 구조로 만들겁니다


Parser.h에 IfExprAST를 추가합니다



5.2.3. Parser Extensions for If/Then/Else

파서 함수를 작성합니다

Parser.cpp를 열어 ParsePrimary 정의 위에 작성합니다


다음으로 primary expression 핸들러에 ParseIfExpr을 등록합니다




5.2.4. LLVM IR for If/Then/Else

렉서에서 if 토큰을 처리했고, Parser에서 AST를 이미 다 만들었습니다. 

그럼 이제 남은건 LLVM IR로 변환하는것이죠

위에서 한것들은 그냥 1~3장에서 했던것들을 If/Then/Else에 대해 한번 더 해본것에 불과하지만 이번 절은 새로운개념을 설명합니다


If/Then/Else를 CodeGen해서 나올 LLVM IR의 형태를 한번 알아보죠

[주: C언어로 if else 문을 작성해서 LLVM IR 로 보는걸로도 힌트를 얻을 수 있겠지만 튜토리얼에서 단순 텍스트로 소개한 내용을 그대로 사용하겠습니다]



예를들어, 

이런 코드가 있다고 할 때,

최적화를 안했다고 한다면 아래와 같은 LLVM IR이 만들어 질겁니다


이걸 복사 붙여넣기해서 t.ll 을 만들고 llvm-as < t.ll | opt -analyze -view-cfg 를 실행해보시면

이렇게 CFG로도 볼 수 있습니다

이 CFG는 LLVM단에서 개발을 할 때도 LLVM Function에 있는 viewCFG() 함수를 실행시키면 딱 그함수의 CFG를 볼 수 있습니다.

F->viewCFG()처럼요


위의 그래프를 보면 if then else가 구현된 형태는 단순합니다

fcmp one(Ordered and Not Equal) 명령을 이용해 x가 0.0과 같은지 비교합니다. 즉 if안에있는 condition의 결과가 0.0인지 비교하는겁니다(false)

그 아래있는 LLVM IR의 br명령은 첫번째가 조건, 두번째가 true일때 도착지, 세번째가 false일때 도착지인데

0.0과 같지 않을때 true bb(basic block)로 가겠다는 거죠


then과 else모두 실행후의 도착지는 같습니다

그런데 then에서는 %calltmp을 사용하고 else에서는 %calltmp1 을 사용하죠

둘중에 하나는 리턴값으로 사용이 될텐데 둘중에 어떤걸 리턴하는지는 어떻게 알까요?

사실 추측하기 어렵진않습니다. phi 라는 llvm 명령이 뭔지는 몰라도

phi double [ %calltmp, %then ], [ %caltmp1, %else ] 로 돼있으니까 만약 이전 BB가 then이였다면 %calltmp를 쓰고 else였다면 %calltmp1 을 쓰겠죠


t.ll을 수정해서 %calltmp1 -> %calltmp로 수정하면 

llvm-as: <stdin>:15:3: error: multiple definition of local value named 'calltmp'

  %calltmp = call double @bar()

이런 에러가 뜹니다

이는 LLVM IR이 SSA 형태를 갖기 때문인데, SSA를 처음 들어보시는 분은 SSA Form 이라고 구글에 검색해서 뭔지 찾아보고 오시면 됩니다(Single Static Assigment). 쉽게 말해 하나의 "변수"는 평생 하나의 값만을 갖게 되는 형태입니다.



PHI Instruction에 대한 설명도 SSA에 같이 설명돼있습니다. 여기서 설명한것만 알아도 되는데 좀더 알고싶으신 분은 위키 페이지를 읽어보시면 됩니다



5.2.5. Code Generation for If/Then/Else

IfExprAST::codegen 을 정의해봅시다


If의 Cond->codegen()을 먼저 한 후 그 결과가 0.0과 같지 않은지 확인합니다

즉 Cond가 True라면 CondV가 True입니다


먼저 현재 삽입 포인트(BB)를 가져와 Parent(Function)를 알아냅니다

그다음 ThenBB와 ElseBB, 그리고 두 BB가 실행 후 공통적으로 가게 될 MergeBB를 만듭니다

CreateCondBr은 첫번째 인자가 컨디션, 두번째인자가 true일 때 갈 BB, 세번째인자가 false일 때 갈 BB입니다.

BB가 아직 비어있는 상태긴하지만 지금 브랜치를 만들어도 괜찮습니다. LLVM이 알아서 중간에 잘 삽입해줍니다


브랜치를 만든후에 BB를 채워줍니다

Builder.SetInsertPoint(ThenBB)를 하면 그다음 instruction emit부터 ThenBB에 차곡차곡 들어가게 됩니다

정확히는 BB의 마지막을 가르키게 되는데, 현재 ThenBB가 비어있기 때문에 처음을 가르키게 됩니다


Then->codegen()으로 안의 표현식을 LLVM IR로 변환한 뒤 MergeBB로 가는 분기를 삽입합니다

마지막줄이 살짝 난해한데, ThenBB를 SetInsertBlock으로 설정을 해놓고 왜 굳이 다시 GetInsertBlock으로 가져와서 ThenBB에 넣어줄까요?

그 이유는 Then->codegen()에서 codegen을 여러번 호출하면서 예를들어 그 안에 또 if-then-else 문이 있을 때, 하나라고 생각했던 ThenBB가 그 안에서 또 잘게 잘라질겁니다

그러면서 우리가 위에서 만들었던 ThenBB가 잘라진 윗부분만을 가르키게 될 수도 있는거죠, 우리는 아랫부분이 중요합니다(Phi에서 처리하기 위해)


한가지 더 중요한것은, LLVM에서는 BB가 항상 '종료' 되어야 합니다

BB라는것은 선형코드들을 분기에 따라 잘라놓은 일종의 단위라고 봐야 하는데

BB안에 모든 코드들은 BB가 끝날 때 까지 선형으로 실행됩니다

즉 BB는 항상 branch나 return으로 끝나야 합니다. 이 규칙을 지키지 않으면 verifier에서 에러를 발생시킵니다


ElseBB도 비슷합니다. 첫번째줄만 다르죠

위에서 ThenBB, ElseBB, MergeBB를 만들때 ThenBB에만 Parent를 지정해서 만들었습니다

왜 굳이 그렇게했는지는 안나오는데 그냥 다 Parent지정해서 만들어도 아무 문제 없습니다

그냥 BB를 parent없이 만들고 중간에 추가하는 방법도 있다는걸 소개하는것 같네요


이제 Then과 Else가 모두 만들어졌으니 이제 MergeBB에서 Phi노드를 만들어줍니다


첫 이전과 두 라인은 똑같습니다.

Phi node를 만들땐 Block/Value 쌍을 지정해주면 됩니다

어떤 Block에서 왔을 때 어떤 Value를 쓸 것이냐를 명시하는것이죠


이제 우리 언어는 If/Then/Else문을 갖게 되었습니다



짜잔~ 첫라인에서는 1 < 2 를 비교해서 잘 됐는데

음수가 나와버리니까 Lexer에서 카오스가 발생합니다

하는 김에 음수도 처리할 수 있게 해봤습니다

Lexer.cpp의 gettok만 바꿔주면 됩니다

이전 토큰의 타입을 저장하게 해서 처리했습니다

무려 10 - -8도 가능합니다

직접 음수지원을 추가해보시고, 정 안되실때 글 맨 마지막에 첨부된 소스코드를 참고하시면 됩니다


컴파일은 

 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 mcjit`  -I/Users/cd80/AppsolidiOS/DevAppsolidiOS/llvm/examples/Kaleidoscope/include

이런식으로 하시면됩니다. C++17로 컴파일하고, llvm-config는 직접 빌드한 llvm 바이너리에 있는 llvm-config를 쓰셔야 하고

kaleidoscope include디렉토리는 직접 llvm/examples/Kaleidoscope/include 로 명시해주어야 합니다



5.3. 'for' Loop Expression

이제 언어에 새로운 기능을 추가하는 법을 알았습니다.

for 문을 추가하기 전에 한번 직접 원하는 기능을 추가해보세요

저는 if/then/else를 만들었으니 삼항연산자를 추가하기는 쉬울거라 생각해서 시도해봤는데 실패했습니다. 실패하면서 배운게 많아 이 글을 보시는 분들도 직접 원하는 문법을 추가해보시길 추천드립니다. if문에 중괄호를 추가해보는것도 재밌겠군요


이제 for문을 언어에 추가해 반복기능을 사용해봅시다

특이하게도 변수를 사용합니다. for scope 안에서만 유효하고, 현재는 변수 테이블을 만들지 않을거기때문에 루프 변수를 루프문 안에서 사용하는것도 불가능 합니다

단순히 카운터 역할만 해주는거죠

그 다음 카운터의 조건을 명시하고, 증감 값을 넣어줍니다(여기서는 1.0), 증감값은 생략해도 되고, 생략됐을 시엔 1.0으로 설정됩니다

그리고 in 은 if/then/else 의 then처럼 그 다음부터 expression이 올것이란 지시어입니다




5.3.1. Lexer Extensions for the 'for' Loop

Lexer에서 할건 이전과 똑같습니다


Lexer.h를 열어 토큰을 추가합니다


그 다음으로 Lexer.cpp를 바꿔야 하는데, 이 부분은 제 코드와 튜토리얼 코드가 약간 다릅니다.(음수지원 추가 때문)

제 음수지원 코드가 제대로 된 방법이 아닐 가능성이 크기 때문에 원본 튜토리얼코드를 원하시면 원문을 참고 바랍니다.

Lexer.cpp

파일이 길어 gist로 첨부하지 않고 파일을 업로드 했습니다. 적당히 본인에 맞게 변형해서 쓰시면 될 것 같습니다


Lexer.cpp에 아래 코드를 추가합니다



5.3.2. AST Extensions for the 'for' Loop

AST를 만드는것도 쉽습니다. 뭐가 필요한지 다시 한 번 보죠

먼저 'for' 로 시작하죠, 이건 Lexer.cpp에서 처리돼서 파서에서 getNextToken으로 바로 넘겨줄겁니다

그 다음 변수 이름이 나오고, 초기값이 주어집니다. 그 다음 종료할 조건문이 주어지죠. 다음으로 증감값, 그다음 코드가 나옵니다

이걸 그대로 선언해봅시다



5.3.3. Parser Extensions for the 'for' Loop

파싱도 이전과 크게 다르지 않습니다. 그런데 우리 문법에는 optional한것이 있죠, 바로 증감값입니다

C언어에서 if문이 짝을 이루는 else문이 있을수도있고 없을수도 있는 것 처럼

우리 for문에서는 증감값이 있어도되고 없어도 됩니다




5.3.4. LLVM IR for the 'for' Loop

이제 우리 언어에서 사용한 for문이 어떤 LLVM IR로 바뀌어야 할지 알아봅시다

위의 별을 100개찍는 예제를 IR로 CodeGen하면 아래와 같습니다(최적화 X)


이전 절에서 알게된 Phi 노드도 있고, 베이직블록도 세개(엔트리, for loop, 에필로그) 있습니다

LLVM IR은 x86어셈처럼 직관적인 명령들로 이루어져있기 때문에 자세한 설명은 하지 않습니다



5.3.5. Code Generation for the 'for' Loop

우선 처음에 시작값을 LLVM IR에서의 표현식으로 생성합니다. (값부터 만들어야 변수를 생성하고 넣을 수 있습니다)

그리고, 루프문의 코드를 채워넣기 전에 베이직 블럭부터 만들어줍니다

if/then/else 를 구현할 때와 비슷한 형태입니다. 5.3.4의 예시 IR을 보면 phi node를 이용해 카운터 변수의 값을 결정하는 것을 볼 수 있습니다. 

phi node가 제대로 작동할 수 있게 하기위해 loop body로의 브랜치문을 생성해주는 것입니다


LoopBB의 코드를 생성합니다. LoopBB의 Phi node는 PreheaderBB에서 들어오는 분기와, LoopBB의 마지막에서 들어오는 분기가 있습니다.

아직 LoopBB코드를 만들지 않았기 때문에 PreheaderBB 부터 phi node에 등록합니다


for문에서는 루프 변수라는 임시변수를 생성합니다. 그런데 이 임시변수의 이름이 상위스코프에서 선언된 변수이름과 같은 이름일 경우 이 변수를 덮어써야 할지, 아니면 중복선언으로 에러를 뿜어야할지 그런 정책들을 정해야 하는데

Kaleidoscope에서는 상위스코프의 변수를 백업해둔 뒤 for문이 끝나면 상위스코프의 변수값으로 변경해줍니다


이렇게하면 두가지 효과가 있습니다

우선 

i = 20

for i = 0, i < 30, 10.0 in

putchard(65)

이렇게하면 for문이 끝났을 때 i 의 값은 20이고

맨 위의 i = 20 없이


for i = 0, i < 30, 10.0 in

putchard(65)

를 하면 for문 밖에서 i는 undeclared variable이 됩니다


그리고 맨 마지막에 Body->codegen을 해서 nullptr가 리턴됐을 시에는 비정상 종료를 하지만 Body->codegen의 결과, 즉 for문의 expression은 리턴하지 않습니다. 

사실 for문 자체는 어떤 값을 리턴하지 않고, for body를 실행하기만 합니다. (조금 생각해보면 충분히 납득이 가는 구현입니다)


이 위의 코드까지 Body가 모두 CodeGen이 완료된 상태입니다

for문에서는 for body의 실행이 끝나면 카운터 변수를 증감시키죠, 이 코드도 마찬가지로 증감값을 계산해 루프변수에 더해줍니다. 증감값이 없을 경우엔 1.0으로 초기화합니다


종료 조건을 가져와서 조건문이 0.0 과 Not Equal인지 (FCmpONE) 비교합니다


마지막으로  PhiNode를 위한 LoopEndBB 변수를 선언하고

for문이 끝난 후에 갈 BB를 생성합니다


그 다음, EndCond가 true일때 LoopBB로 가고 false일때 루프를 종료합니다

EndCond가 true라는 뜻은 코드에서의 조건문 결과가 0.0이랑 같지 않다. 즉 1.0이란 뜻이죠


이제 Phi Node에서 카운터변수의 다음값을 갖고 있습니다(기존변수 + Step). 이 값을 Phi node에 등록합니다

그 다음 카운터변수가 상위스코프에서 선언이 돼있었다면 원래 값으로 바꾸고, 아니라면 변수를 심볼테이블에서 삭제합니다



여기까지 if/then/else문과 for문을 추가해 Kaleidoscope언어에 Control Flow를 추가하였습니다

추가하면서 이제 언어에 새로운 기능을 추가하는게 익숙해 지셨을 거라 생각합니다

다음 챕터에서는 약간 더 어려울 수 있는 사용자 정의 이항연산자 기능을 추가합니다




빌드는 계속 똑같습니다

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 mcjit`  -I/Users/cd80/AppsolidiOS/DevAppsolidiOS/llvm/examples/Kaleidoscope/include





Chapter5.zip




신고
0 Comments
댓글쓰기 폼