Compiler - Code Generation

이번 포스트는 컴파일러의 마지막 6번째 단계인 Code Generation에 대해 다룬다.

Code Generation

• Code Generation 단계 = Compiler의 마지막 단계 중 하나
• TAC 코드 (Optimization이 된 단계)를 실제 머신 코드(또는 어셈블리)로 변환하는 단계이다.
  • 중간 코드 IR을 받아서 타겟 머신의 Instruction으로 Mapping
  • 단순한 변환이 아니라 효율적인 레지스터 사용, 올바른 메모리 참조, Stack Frame 구성, Procedure Call 처리가 자동적으로 관리되어야 한다.
• Symbol Table 정보를 활용한다.
  • 이는 Address 계산에서 필수 사용된다.

Memory Layout

위로 갈수록 High Address, 아래로 갈 수록 Low Address 이다.

+--------------------+
| Command-line args  |
| Environment vars   |
+--------------------+
| Program Stack      | ↓ (Stack grows downwards)
| (Local variables,  |
|  function frames)  |
+--------------------+
| Heap               | ↑ (Heap grows upwards)
| (Dynamic allocation) |
+--------------------+
| Global data        |
| (Global variables, static vars) |
+--------------------+
| Program code       |
| (Instructions)     |
+--------------------+

• 특징
  • Stack은 위에서 아래로 진행된다.
  • Heap은 아래에서 위로 진행된다.
  • Global Data는 프로그램 전체에서 고정된 주소를 사용한다.
  • Code 영역은 고정이다. (실행 명령어 저장)
• 각 영역 설명

1. Code 영역
   • Program Instruction을 저장한다.
   • 일반적으로 실행만 가능하다.
2. Global Data 영역
   • 전역 변수 / static 변수를 저장한다.
   • 프로그램 lifetime동안 고정된 주소를 사용한다.
3. Heap 영역
   • Dynamic memory allocation (malloc, new) 시 사용된다.
   • Runtime 시에 동적으로 크기가 변한다.
   • Heap Pointer가 관리한다.
4. Stack 영역
   • Function Call 시마다 새로 Stack Frame(Activation Record)를 생성한다.
   • Stack Pointer (SP)가 관리한다.
   • Stack은 “재귀 함수 호출”을 가능하게 해준다.

Load / Store Architecture (MIPS Architecture의 특징)

• MIPS 는 Load/Store Architecture로 연산은 레지스터끼리만 가능하다.
• 메모리 접근시에 반드시 load (메모리 -> 레지스터), store (레지스터 -> 메모리) 명령어를 사용해야 한다.

예시)

a = b + c;

• In MIPS,

  lw $t0, b_address   // b → t0
  lw $t1, c_address   // c → t1
  add $t2, $t0, $t1   // t2 = t0 + t1
  sw $t2, a_address   // t2 → a
  

  • address를 나타낼 때는 offset($reg)를 사용한다.
    • 예시 ) lw $r0 4($sp)

Stack Frame

• Stack Frame = Activation Record
• Function call 시마다 Stack 영역이 새로운 Frame(Activation Record)를 Push한다.
  • Function이 호출될 때:
    • 매개변수, Return Address, Old Frame Pointer, Local Variable을 저장한다.
  • Function Return시:
    • 해당 Stack Frame POP

• 재귀 호출 지원이 가능하다. (매 호출마다 별도 Frame을 형성한다.)

• Stack Frame 구조

  +--------------------+
  | Arguments          |  ↑ (Caller pushes)
  +--------------------+
  | Return Address     |  ← Saved by jal
  +--------------------+
  | Old Frame Pointer  |  ← Saved by callee
  +--------------------+
  | Local Variables    |  ← Callee allocates
  +--------------------+
  | Temporary Storage  |
  +--------------------+
  

Frame Pointer, Stack Pointer

Stack Pointer (SP)

• Stack의 Top 위치를 가리킨다.
• Stack Frame Push / Pop 시 Stack Pointer를 조정한다.

Frame Pointer (FP)

• Stack Frame 내에서 기준 위치 (고정된 위치)를 제공한다.
• Local Variables, Arguments는 FP를 기준으로 Offset으로 접근한다.

SP는 계속 변하지만, FP는 Function 실행 중에는 고정된다.

• 접근이 쉽고 빠르다.

Function에서 Stack Frame

Function Call : Caller -> Callee

1. Caller가 Arguments Push
   • Arguments 영역을 확보한다.
2. jal (Jump and Link) 명령어로 Function Call
   • Return Address가 자동으로 저장된다.
3. Callee가 Stack Frame을 생성
   • Old Frame Pointer를 저장한다.
   • New Frame Pointer를 설정한다. (FP = SP)
   • Local Variables 영역을 확보한다.
     • 이로써 Function 실행 준비가 끝났다. (실행 시작)

Stack Frame 해제 : Function Return (Callee -> Caller)

1. Callee가 Local Variables 영역을 해제한다.
   • Stack Pointer가 복원된다.
2. Old Frame Pointer가 복원된다.
3. Return Address를 이용하여 Return
   • Control Back to Caller
4. Caller가 Arguments 영역 해제
   • 이로써 Stack Frame을 완전히 해제한다.

MIPS Assembly

• MIPS 주요 특징
  • 연산은 전부 레지스터끼리만 가능하다
  • 메모리 접근은 반드시 load, store 명령어를 사용해야 한다.
• 기본 MIPS Instruction

연산 종류	명령어 예시	설명
Load	lw $t0, offset($fp)	Stack에서 Load
Store	sw $t0, offset($fp)	Stack에 Store
Add	add $t0, $t1, $t2	$t0 = $t1 + $t2
Subtract	sub $t0, $t1, $t2	$t0 = $t1 - $t2
Multiply	mul $t0, $t1, $t2	$t0 = $t1 * $t2
Divide	div $t0, $t1	$t0 = $t0 / $t1
Conditional Branch	beq, bne, blt, bgt, ble, bge	조건 분기
Jump	j label	무조건 Jump
Function Call	jal func	Jump and Link (RA에 Return Address 저장)
Function Return	jr $ra	Return to Caller

• 사용 예시

TAC 코드 :

• x = y + z

lw $t1, y_offset($fp)   # Load y into $t1
lw $t2, z_offset($fp)   # Load z into $t2
add $t3, $t1, $t2       # t3 = t1 + t2
sw $t3, x_offset($fp)   # Store t3 into x

• if a < b goto L1

lw $t0, a_offset($fp)   # Load a into $t0
lw $t1, b_offset($fp)   # Load b into $t1
blt $t0, $t1, L1        # if a < b goto L1

• return a;

lw $v0, a_offset($fp)   # Move a into return register $v0
move $sp, $fp           # Restore SP from FP
lw $fp, -4($sp)         # Restore old FP
jr $ra                  # Return to caller

---

이로써 컴파일러의 총 6단계를 다 정리했다.

컴파일러는 처음에 단순한 텍스트였던 프로그램이

Lexical Analysis → Syntax Analysis → Semantic Analysis → Intermediate Code Generation → Code Optimization → Code Generation → Target Machine Code

이 흐름을 전부 거쳐 실행 가능한 프로그램으로 변환한다.

• 이번 과정에서 배운 개념들
  • 언어의 구조 이해
  • 최적화가 왜 필요하고 어떻게 하는지
  • 실제 시스템이 돌아가는 원리

요약 : 앞으로 어떤 고급 프로그래밍을 하든, 코드가 어떻게 실행되는지 어떤 최적화가 적용되는지 확인할 수 있게 되었다.