for loop
extern putchard(char);
def printstar(n)
for i = 1, i < n, 1.0 in
putchard(42); # ascii 42 = '*'
# print 100 '*' characters
printstar(100);
Kaleidoscope의 for 문 예시는 위와 같다.
i = 1: i를 1에서 시작
i < n: i가 n보다 작은 동안 반복
1.0: 매 반복마다 i를 1.0씩 증가
in ...: for 루프의 내부 실행 코드(여기선 putchard)
putchard(42): 42는 아스키코드로 별( * ) 문자.
기본적인 시퀸스는 if/then/else 와 동일하다.
하지만 llvm 생성 단계에서 특정 조건이 만족되는 동안 계속해서 특정 블록으로 되돌아오게끔 즉 순환 구조를 만들어야 하므로, 단순히 두 갈래로 나뉘었다가 합쳐지는 것과는 다르다.
Lexer Extension
먼저 enum Token에 새로운 값 추가, for과 in을 각기 고유한 토큰으로 처리할 수 있게끔 만든다.
이후, gettok 함수에서 식별자를 읽어들일 때 아래와 같이 새로운 키워드를 인식하도록 if문을 추가한다.
// control
tok_if = -6, tok_then = -7, tok_else = -8,
tok_for = -9, tok_in = -10
if (IdentifierStr == "def")
return tok_def;
if (IdentifierStr == "extern")
return tok_extern;
if (IdentifierStr == "if")
return tok_if;
if (IdentifierStr == "then")
return tok_then;
if (IdentifierStr == "else")
return tok_else;
if (IdentifierStr == "for")
return tok_for;
if (IdentifierStr == "in")
return tok_in;
return tok_identifier;AST Extension
/// ForExprAST - for/in 표현식을 위한 AST 클래스
class ForExprAST : public ExprAST {
std::string VarName; // 루프 변수 이름
std::unique_ptr<ExprAST> Start, End, Step, Body; // 각 부분 표현식
public:
ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
std::unique_ptr<ExprAST> Body)
: VarName(VarName), Start(std::move(Start)), End(std::move(End)),
Step(std::move(Step)), Body(std::move(Body)) {}
Value *codegen() override; // LLVM IR 코드 생성 함수
};
이후 for 루프를 표현하기 위해, AST를 위와 같이 정의할 수 있다.
루프 변수 이름과 for루프 각 부분의 표현식을 저장한다.
- VarName: for 루프에서 사용할 변수의 이름 (예:
for i = ...의i) - Start: 루프 변수의 시작 값 (초기화 표현식)
- End: 루프 종료 조건 표현식
- Step: 루프 변수의 증가(혹은 감소) 값 (스텝 표현식, 생략 가능)
- Body: 루프 본문(반복해서 실행할 표현식)
이렇게 각 부분이 다른 EXprAST로 저장되어, recursive한 구조도 표현할 수 있게 된다.
std::unique_ptr를 사용해 자동으로 메모리 관리를 할 수 있고, 위에서 보았든 codegen() 함수는 LLVM IR 코드로 변환할 때 호출된다.
Paser Extension
static std::unique_ptr<ExprAST> ParseForExpr() {
getNextToken(); // 'for' 토큰 소비
if (CurTok != tok_identifier)
return LogError("expected identifier after for");
std::string IdName = IdentifierStr;
getNextToken(); // 변수명 소비
if (CurTok != '=')
return LogError("expected '=' after for");
getNextToken(); // '=' 소비
auto Start = ParseExpression();
if (!Start)
return nullptr;
if (CurTok != ',')
return LogError("expected ',' after for start value");
getNextToken(); // ',' 소비
auto End = ParseExpression();
if (!End)
return nullptr;
// 스텝 값은 선택적(optional)
std::unique_ptr<ExprAST> Step;
if (CurTok == ',') {
getNextToken();
Step = ParseExpression();
if (!Step)
return nullptr;
}
if (CurTok != tok_in)
return LogError("expected 'in' after for");
getNextToken(); // 'in' 소비
auto Body = ParseExpression();
if (!Body)
return nullptr;
return std::make_unique<ForExprAST>(IdName, std::move(Start),
std::move(End), std::move(Step),
std::move(Body));
}
위의 예시처럼, for / 변수명/ =/ 시작값/ , / 종료조건을 parsing한다. 모든 정보가 모이면 For ExprAST노드를 생성하여 return하게 된다.
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();
case tok_for:
return ParseForExpr();
}
}for 토큰을 만나면, ParseForExpr()을 호출하여 for 루프 구문을 파싱한다. 이를 통하여 for 루프또한 하나의 expression으로 파싱될수 있다.
LLVM IR Extension
declare double @putchard(double)
define double @printstar(double %n) {
entry:
; 초기값 = 1.0 (phi 노드에 직접 대입)
br label %loop
loop: ; preds = %loop, %entry
%i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
; 루프 본문
%calltmp = call double @putchard(double 4.200000e+01)
; 증가
%nextvar = fadd double %i, 1.000000e+00
; 종료 조건 검사
%cmptmp = fcmp ult double %i, %n
%booltmp = uitofp i1 %cmptmp to double
%loopcond = fcmp one double %booltmp, 0.000000e+00
br i1 %loopcond, label %loop, label %afterloop
afterloop: ; preds = %loop
; 루프는 항상 0.0을 반환
ret double 0.000000e+00
}- entry 블록
• 루프의 시작점.
• 바로loop블록으로 분기 (br label %loop). - loop 블록
• phi 노드로 루프 변수 i 초기화 및 갱신
•%i = phi double 1.0, %entry , %nextvar, %loop
• 첫 진입 시:%i = 1.0(초기값)
• 반복 시:%i = %nextvar(이전 반복에서 계산된 값)
• 루프 본문 실행
•@putchard(42)호출로 ‘*’ 출력
• 루프 변수 증가
•%nextvar = fadd double %i, 1.0
(i에 1.0을 더해 다음 반복값 생성)
• 종료 조건 검사
•%cmptmp = fcmp ult double %i, %n
(i < n비교, 결과는 i1 타입)
•%booltmp = uitofp i1%cmptmp to double
(불리언을 double로 변환)
•%loopcond = fcmp one double %booltmp, 0.0
(0.0과 다르면 참, 같으면 거짓)
• 분기
•br i1%loopcond, label %loop, label %afterloop
• 조건이 참이면 다시 loop 블록으로,
• 조건이 거짓이면 afterloop 블록으로 이동 - afterloop 블록
• 루프 종료 후 항상0.0을 반환
(ret double 0.0)
맨 처음에 보았던, printstar 함수의 llvm 코드
아래 Code Generation Extension에서 어떻게 해당 llvm 코드가 만들어지는지 보자.
Code Generation Extension
if문과 마찬가지로, 여러가지의 Basic Block을 사용한다.
가장 중요한 차이점으로 loop count 변수 (i) 의 값을 반복 과정동안 기억하고, 초기화해야한다는 점이다.
이를 위하여, alloca 명령어를 통하여 stack에 count변수의 메모리 공간을 할당한다.
Basic Block
Preheader: 진입 블록
alloca 명령어를 통하여 루프 카운터 변수 i를 저장할 공간을 stack에 만든다.
시작값의 코드를 생성하고, 그 값을 alloca로 만든 메모리 공간에 store 한다.
Loop : 루프 헤더 블록
루프의 시작점
스택에서 현재 루프 변수 값을 load하여 종료값과 fcmp(비교)한다.
조건부 분기 -> 비교 결과가 참이면 LoopBody 블록으로 가서 루프를 계속 돌고, 거짓이면 AfterLoop 블록으로 jump
LoopBody : 루프 본문 블록
루프 본문 표현식 코드 생성 -> 루프 변수를 지속적으로 업데이트 해야한다.
1. 스택에서 현재 변수 값을 load
2. Step(증가값)을 더함
3. 새로운 값을 다시 스택에 store
무조건 분기 -> 작업이 끝나면 다시 Loop 블록으로 되돌아가서 다시 검사
AfterLoop
루프가 완전히 끝났을때 실행 -> Kaleidoscope의 for 루프는 항상 0.0을 반환하도록 설계되었다.
+--------------------------------+
| Preheader: |
| i = alloca double |
| store double <start_val>, i |
| br label %Loop |
+--------------------------------+
|
V
+----------------------------------<--+
| LoopBody: | |
| ... (루프 본문 코드 생성) | |
| ... | |
| next_i = cur_i + <step_val> | |
| store next_i, i | |
| br label %Loop | |
+----------------------------------+ |
^ |
| |
+--------------------------------+ |
| Loop: | |
| cur_i = load i | |
| cond = fcmp cur_i, <end_val> | |
| br i1 cond, %LoopBody, %After|---+
+--------------------------------+
| (참)
|------------------------>+
| |
(거짓) V
+--------------------------------+
| AfterLoop: |
| ... (루프 이후 코드) |
+--------------------------------+
1. 루프 시작값 코드 생성
Value *StartVal = Start->codegen();
if (!StartVal)
return nullptr;루프 변수의 시작값을 먼저 계산한다. 아직 변수 i가 스코프에 등록되지 않은 상태이다.
2. 루프 헤더 블록 생성
Function *TheFunction = Builder->GetInsertBlock()->getParent();
BasicBlock *PreheaderBB = Builder->GetInsertBlock();
BasicBlock *LoopBB = BasicBlock::Create(*TheContext, "loop", TheFunction);
Builder->CreateBr(LoopBB);현재 함수와 블록을 저장하고, 반복이 시작될 때, 루프 블록 BB를 생성한다. 그리고 현재 블록에서 LoopBB로 무조건분기하는 명령을 추가한다.
3. 루프 본문 코드 생성 준비
Builder->SetInsertPoint(LoopBB);
PHINode *Variable = Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, VarName);
Variable->addIncoming(StartVal, PreheaderBB);코드 생성 위치를 LoopBB로 이동 -> phi 노드를 생성하여 루프변수 i 값 관리.
첫 진입 시에는 시작값을 사용한다.
4. 변수 테이블 관리
Value *OldVal = NamedValues[VarName];
NamedValues[VarName] = Variable;루프변수를 심볼테이블에 등록, shadowing 지원
5. 루프 본문 코드 생성
if (!Body->codegen())
return nullptr;루프 본문을 재귀적으로 생성
6. step 값 계산
Value *StepVal = nullptr;
if (Step) {
StepVal = Step->codegen();
if (!StepVal)
return nullptr;
} else {
StepVal = ConstantFP::get(*TheContext, APFloat(1.0));
}
Value *NextVar = Builder->CreateFAdd(Variable, StepVal, "nextvar");
스텝 값이 없다면 1.0 사용, 현재 루프변수에 스텝을 더하여 다음 루프변수를 계산
7. 종료 조건 계산
Value *EndCond = End->codegen();
if (!EndCond)
return nullptr;
EndCond = Builder->CreateFCmpONE(
EndCond, ConstantFP::get(*TheContext, APFloat(0.0)), "loopcond");0.0과 비교하여 true 즉 0.0 (false)라면 다시 루프를 돎
8. 루프 종료 블록 생성 및 분기
BasicBlock *LoopEndBB = Builder->GetInsertBlock();
BasicBlock *AfterBB = BasicBlock::Create(*TheContext, "afterloop", TheFunction);
Builder->CreateCondBr(EndCond, LoopBB, AfterBB);
Builder->SetInsertPoint(AfterBB);루프가 끝나면 이동할 afterloop 블록 생성, 조건에 따라 루프를 반복할지 종료할지,,
이후 생성되는 코드는 afterloop 블록에 삽입된다.
9. phi 노드에 backedge 반복 값 추가
Variable->addIncoming(NextVar, LoopEndBB);phi 노드에 반복 경로에서 온 값을 추가, 새로운 i값을 업데이트(phi노드에 연결)
10. 변수 스코프 복구 및 반환
if (OldVal)
NamedValues[VarName] = OldVal;
else
NamedValues.erase(VarName);
return Constant::getNullValue(Type::getDoubleTy(*TheContext));
쉐도잉 기능을 지원하므로, 쉐도잉된 변수가 있으면 복원, 없으면 삭제한다. 항상 0.0을 반환.
- i,j 등 count 변수의 충돌 방지
시작값 계산 → phi 노드로 변수 관리 → 본문 코드 생성 → 스텝 계산 → 종료 조건 검사 → 분기 → phi 노드 갱신 순서로 진행
for 루프에서는 phi 노드를 명시적으로 사용하지 않는다.
if문에서는 두개의 독립적인 경로가 있었다. 이때
then 에서 왔으면 1을
else 에서 왔으면 2를 선택해라. 라고 알려주는 노드가 phi 노드였는데,
then --(값 A)--> Merge
|
PHI --> 최종 값
|
else --(값 B)--> Merge말한 대로 for 루프는 항상 0.0만 반환하도록 설계되었다. 무조건 for 표현식 전체의 결과는 0.0 으로 반환되므로, 여러 경로에서 온 값 중 하나를 선택할 필요는 없다.
대신 store: 값을 덮어쓰고
load: 값을 읽어와
하나의 흐름, 하나의 메모리 안에서 계속 갱신된다.
+------------------------------------------------+
| 스택 메모리 (i) |
+------------------------------------------------+
^ |
(store: 값 덮어쓰기) | (load: 값 읽어오기)
| V
+------------------------------------------------+
| 루프 본문 |
+------------------------------------------------+