Code Generation — AST에서 Assembly로

📌단원 개요

scanning, parsing, AST 구성, type checking, intermediate representation(IR) 생성을 모두 마친 컴파일러의 마지막 단계. 이제 실제 assembly code를 만든다. 이 장은 naïve approach로, 프로그램의 각 요소를 고립(isolation)시켜 독립적으로 생성한다.

Code Generation 함수 계층 (Figure 11.1)

상위 함수가 하위 함수를 호출하는 구조. decl_codegen이 stmt_codegen을, 그것이 다시 expr_codegen을 호출하고, 최하위에서 symbol_codegen·scratch_alloc·scratch_free 같은 supporting function이 쓰인다.

11.1Introduction

code generation은 컴파일러의 final stage이며, 이 장에서는 가장 단순한 naïve 방식을 먼저 익힌다.

11.2Supporting Functions

본격적인 code generation 전에, 세부 사항을 추적할 supporting function들을 먼저 만든다: scratch register 관리, label 생성, symbol 주소 계산.

① Scratch Register 관리

expression을 생성하려면 operator 사이의 intermediate value를 담을 scratch register가 필요하다. 다음 인터페이스의 세 함수를 작성한다.

int scratch_alloc();
void scratch_free( int r );
const char * scratch_name( int r );

Chapter 10에서 각 register는 용도가 정해져 있었다: 일부는 function argument용, 일부는 stack frame management용, 나머지가 scratch value용이다. scratch register들을 다음과 같은 table로 관리한다.

② Label 생성

jump와 conditional branch의 target이 될 unique, anonymous label을 대량으로 생성해야 한다. 두 함수를 작성한다.

int label_create();
const char * label_name( int label );

• label_create: global counter를 증가시켜 현재 값을 반환.
• label_name: 그 label을 string 형태로 반환. 예를 들어 label 15는 ".L15"로 표현된다.

③ Symbol 주소 계산: symbol_codegen

프로그램의 symbol을 그 symbol을 나타내는 assembly code로 mapping해야 한다. symbol의 주소를 생성하는 함수를 작성한다.

const char * symbol_codegen( struct symbol *s );

이 함수는 주어진 symbol에 필요한 address computation을 나타내는 instruction fragment 문자열을 반환한다. 먼저 symbol의 scope를 검사한다.

f: function void ( x: integer, y: integer ) =
{
    z: integer = 10;
    return x + y + z;
}

11.3Generating Expressions

expression의 assembly code 생성의 기본 방식은 AST 또는 DAG의 post-order traversal을 수행하며 각 node마다 instruction을 하나 이상 emit하는 것이다.

예시: DAG로부터 X86 code 생성 (Figure 11.2)

아래 DAG는 c = (a+3) - b를 표현 (a, b, c는 global integer).

1. MOVQ a, R0
2. MOVQ $3, R1
3. ADDQ R0, R1
4. MOVQ b, R0
5. SUBQ R0, R1
6. MOVQ R1, c

Post-order traversal의 단계별 동작

1. a node: scratch_alloc으로 register 0 할당, node->reg에 저장. MOVQ a, R0 emit.
2. 3 node: register 1 할당. MOVQ $3, R1 emit.
3. IADD node: 두 child가 R0, R1에 있으므로 ADDQ R0, R1 emit. 이는 destructive two-address instruction으로 결과가 R1에 남는다. R0는 불필요 → scratch_free(0).
4. b node: register 0 할당. MOVQ b, R0 emit.
5. ISUB node: SUBQ R0, R1 emit. 결과 R1, R0 해제.
6. c node: assignment의 target이므로 아무것도 emit하지 않음.
7. ASSIGN node: MOVQ R1, c emit.

MOVQ    a, %rbx
MOVQ   $3, %r10
ADDQ %r10, %rbx
MOVQ    b, %rbx
SUBQ %rbx, %r10
MOVQ %r10, c

expr_codegen 구현 골격 (Figure 11.3)

먼저 left·right child에 대해 재귀적으로 expr_codegen을 호출한다. 각 child가 결과를 자신의 reg field에 남기면, 현재 node가 그 register들을 이용해 code를 생성하고 더 이상 필요 없는 register를 free한다.

void expr_codegen( struct expr *e )
{
    if(!e) return;

    switch(e->kind) {

        // Leaf node: allocate register and load value.

        case EXPR_NAME:
            e->reg = scratch_alloc();
            printf("MOVQ %s, %s\n",
                symbol_codegen(e->symbol),
                scratch_name(e->reg));
            break;

        // Interior node: generate children, then add them.

        case EXPR_ADD:
            expr_codegen(e->left);
            expr_codegen(e->right);
            printf("ADDQ %s, %s\n",
                scratch_name(e->left->reg),
                scratch_name(e->right->reg));
            e->reg = e->right->reg;
            scratch_free(e->left->reg);
            break;

        case EXPR_ASSIGN:
            expr_codegen(e->left);
            printf("MOVQ %s, %s\n",
                scratch_name(e->left->reg),
                symbol_codegen(e->right->symbol));
            e->reg = e->left->reg;
            break;
        . . .
    }
}

기본 과정에 필요한 보완 (refinements)

MOVQ -8(%rbp), %rbx

MOV $10, %rbx
MOV x,    %r10
MOV %rbx, %rax
IMUL %r10
MOV %rax, %r11

보완 3 — function 호출 (Figure 11.4)

function은 단일 CALL node로 표현되고, 각 argument는 ARG node의 unbalanced tree로 표현된다. 아래는 a=f(10,b+c)를 표현하는 DAG이다.

MOVQ $10, %rbx
MOVQ b, %r10
MOVQ c, %r11
ADDQ %r10, %r11
MOVQ %r11, %rsi
MOVQ %rbx, %rdi
PUSHQ %r10
PUSHQ %r11
CALL f
POPQ %r11
POPQ %r10
MOVQ %rax, %rbx
MOVQ %rbx, a

11.4Generating Statements

expression 생성을 expr_codegen에 캡슐화했으니, 이를 기반으로 더 큰 code 구조를 만든다. stmt_codegen이 모든 control flow statement의 code를 만든다.

void stmt_codegen( struct stmt *s )
{
    if(!s) return;

    switch(s->kind) {
        case STMT_EXPR:
            ...
            break;
        case STMT_DECL:
            ...
            break;
        ...
    }
    stmt_codegen(s->next);
}

마지막에 stmt_codegen(s->next)를 호출하여 statement list를 순차적으로 처리한다.

쉬운 경우들

case STMT_DECL:
    decl_codegen(s->decl);
    break;

case STMT_EXPR:
    expr_codegen(s->expr);
    scratch_free(s->expr->reg);
    break;

return statement

expression을 평가하여 return value 전용 register %rax로 옮기고, stack을 풀고 호출 지점으로 돌아가는 function epilogue로 jump한다.

case STMT_RETURN:
    expr_codegen(s->expr);
    printf("MOV %s, %%rax\n",scratch_name(s->expr->reg));
    printf("JMP .%s_epilogue\n",function_name);
    scratch_free(s->expr->reg);
    break;

if statement (conditional)

원하는 출력 assembly를 먼저 생각하고 거꾸로 생성기를 작성하는 것이 유용하다. control expression을 평가해 값이 known register에 있게 하고, CMP로 0(false)인지 검사한다. false면 JE(jump-if-equal)로 false branch로 jump, 아니면 true branch로 진행. true statement 끝에서 JMP로 else body를 건너뛴다.

      expr
     CMP $0, register
     JE false-label
      true-statements
     JMP done-label
false-label :
      false-statements
done-label :

case STMT_IF:
    int else_label = label_create();
    int done_label = label_create();
    expr_codegen(s->expr);
    printf("CMP $0, %s\n",scratch_name(s->expr->reg));
    scratch_free(s->expr->reg);
    printf("JE %s\n",label_name(else_label));
    stmt_codegen(s->body);
    printf("JMP %s\n",label_name(done_label));
    printf("%s:\n",label_name(else_label));
    stmt_codegen(s->else_body);
    printf("%s:\n",label_name(done_label));
    break;

for loop

source template: for ( init-expr ; expr ; next-expr ) { body-statements }. init-expr을 먼저 평가하고, 매 iteration마다 control expression을 평가한다. false면 loop 끝으로 jump, 아니면 body 실행 후 next-expression 평가.

      init-expr
top-label:
      expr
     CMP $0, register
     JE done-label
      body-statements
     next-expression
    JMP top-label
done-label :

print statement (B-Minor)

출력할 expression의 type에 따라 동작이 달라지는 imperative statement의 특수 사례. integer·boolean·string마다 약간 다른 code가 필요하다.

i: integer = 10;
b: boolean = true;
s: string = "\n";
print i, b, s;

print_integer(i);
print_boolean(b);
print_string(s);

11.5Conditional Expressions

conditional expression(less-than, greater-than, equals 등)은 두 값을 비교해 boolean을 반환한다. control flow에 흔히 나타나지만 단순 값으로도 쓸 수 있다(예: b: boolean = x < y;).

conditional expression 생성 template

left-expr < right-expr에 대한 생성 코드:

       left-expr
      right-expr
    CMP left-register, right-register
    JLT true-label
    MOV false, result-register
    JMP done-label
true-label:
    MOV true, result-register
done-label:

• different conditional operator에는 알맞은 자리에 different jump instruction을 사용한다.
• 약간의 변형으로 ternary conditional operator (x?a:b)도 같은 방식으로 구현 가능.

11.6Generating Declarations

전체 프로그램 emit은 각 declaration(code 또는 data)을 순회하며 기본 구조를 내보내는 일이다. declaration은 세 경우로 나뉜다.

(B-Minor는 local function declaration을 허용하지 않는다.)

① Global data declaration

label과 함께 적절한 directive로 공간을 예약하고, 필요시 initializer를 emit한다.

i: integer = 10;
s: string = "hello";
b: array [4] boolean = {true, false, true, false};

.data
i: .quad 10
s: .string "hello"
b: .quad 1, 0, 1, 0

② Local variable declaration

• stmt_codegen이 function declaration 내부에서 decl_codegen을 호출할 때만 발생.
• local variable 공간은 이미 function prologue가 확보했다고 가정 → stack 조작 불필요.
• 단, initializing expression이 있으면(x:integer=y*10;) expression code를 생성하고 local variable에 저장한 뒤 register를 free한다.

③ Function declaration (마지막 조각)

11.7Exercises (연습문제)

⭐핵심 정리 / 시험 포인트

📋한눈에 보기 — Cheat Sheet