[컴파일러] 12. 코드 생성 알고리즘과 레지스터 할당

초기 상태:
  R1: 비어있음
  R2: 비어있음
  R3: 비어있음

명령어 "LD R1, a" 실행 후:
  R1: a
  R2: 비어있음
  R3: 비어있음

변수 a: 메모리
변수 b: R1, 메모리
변수 c: R2

// 세 주소 코드
t = a - b
u = a - c
v = t + u
d = v + u

명령어: t = a - b
  getReg -> R1 (비어있음)
  코드: LD  R1, a      // R1 = a
        LD  R2, b      // R2 = b
        SUB R1, R1, R2 // R1 = a - b = t
  레지스터: R1=t, R2=b
  디스크립터: t->R1, a->메모리, b->R2/메모리

명령어: u = a - c
  getReg -> R2 (b는 이후 불필요)
  코드: LD  R2, a      // R2 = a
        SUB R2, R2, c  // R2 = a - c = u
  레지스터: R1=t, R2=u

명령어: v = t + u
  getReg -> R1 (t는 이후 불필요)
  코드: ADD R1, R1, R2 // R1 = t + u = v
  레지스터: R1=v, R2=u

명령어: d = v + u
  getReg -> R1 (v는 이후 불필요)
  코드: ADD R1, R1, R2 // R1 = v + u = d
  레지스터: R1=d, R2=u

// 기본 블록 끝: 살아있는 변수 d를 메모리에 저장
  코드: ST  d, R1

LD  R1, a
LD  R2, b
SUB R1, R1, R2
LD  R2, a
SUB R2, R2, c
ADD R1, R1, R2
ADD R1, R1, R2
ST  d, R1

// DAG:
//        (d: +)
//       /      \
//    (v: +)    (u: -)
//    /    \    /    \
// (t: -)  (u) a0    c0
//  /   \
// a0   b0

// 좋은 순서: t, u, v, d (사용 직후 소비)
// 나쁜 순서: t, v, u, d (t를 오래 유지해야 함)

알고리즘: DAG 노드 순서 결정

1. 루트 노드(출력이 없는 노드)를 스택에 넣음
2. 스택이 비어있지 않은 동안:
   a. 스택 꼭대기의 노드 n을 pop하여 출력
   b. n의 자식 중 모든 부모가 이미 출력된 것을 스택에 push
   c. 여러 자식이 조건을 만족하면 가장 왼쪽 자식을 먼저 push

1. 리프 노드: label = 1 (왼쪽 자식) 또는 0 (오른쪽 자식이 메모리)
2. 내부 노드의 두 자식 label이 다르면: label = max(l1, l2)
3. 두 자식 label이 같으면: label = l1 + 1

//       (*)      label = 2
//      /   \
//    (+)    (-)   label = 1, 1
//   / \    / \
//  a   b  c   d   리프
//
// (+)의 label: max(1,1) -> 같으므로 1+1 = 2? 아니요
// 리프: 왼쪽=1, 오른쪽=0
// (+): l=1, r=0 -> 다르므로 max(1,0) = 1
// (-): l=1, r=0 -> 다르므로 max(1,0) = 1
// (*): l=1, r=1 -> 같으므로 1+1 = 2
//
// 결론: 레지스터 2개 필요

알고리즘: genCode(node)

if node가 리프이면:
    LD Ri, node.name
else:
    left = node.leftChild
    right = node.rightChild

    if left.label >= right.label:
        genCode(left)   // 결과가 Ri에
        genCode(right)  // 결과가 Rj에
        emit("OP Ri, Ri, Rj")
    else:
        genCode(right)  // 오른쪽을 먼저
        genCode(left)
        emit("OP Ri, Rj, Ri")

// 코드:
// 1: a = ...
// 2: b = ...     (a live)
// 3: c = a + b   (a, b live)
// 4: d = c       (c live)
// 5: e = b + d   (b, d live)
// 6: return e

// 간섭 그래프:
//   a --- b
//   |
//   c     d --- b
//         |
//         e

알고리즘: 그래프 컬러링 레지스터 할당

1. 간소화(Simplify):
   - 차수(degree)가 k 미만인 노드를 그래프에서 제거하고 스택에 push
   - 제거 후 다른 노드의 차수가 감소할 수 있으므로 반복

2. Spill:
   - 모든 노드의 차수가 k 이상이면, 하나를 잠재적 spill로 표시하고 제거
   - spill 대상 선택 기준: 사용 빈도가 낮은 변수, 루프 밖의 변수

3. 선택(Select):
   - 스택에서 노드를 하나씩 꺼내면서 그래프에 다시 추가
   - 이웃이 사용하지 않는 색(레지스터)을 배정
   - 배정 가능한 색이 없으면 실제 spill 발생

4. 실제 Spill 처리:
   - spill된 변수에 로드/저장 코드 삽입
   - 간섭 그래프를 다시 구성하고 알고리즘 반복

// 간섭 그래프:
//   a --- b --- c
//
// 차수: a=1, b=2, c=1

// 간소화: a(차수1 < 2) 제거 -> c(차수1 < 2) 제거 -> b(차수0 < 2) 제거
// 스택: [a, c, b]

// 선택:
//   b -> R1 (이웃 없음, 아무 색이나 가능)
//   c -> R2 (이웃 b=R1이므로 R2)
//   a -> R2 (이웃 b=R1이므로 R2)

// 결과: a=R2, b=R1, c=R2

// 최적화 전
ST a, R1
LD R1, a    // 불필요한 로드

// 최적화 후
ST a, R1
// LD 제거 (R1에 이미 a의 값이 있음)

// 최적화 전
BR L2
ADD R1, R2, R3   // 도달 불가능
SUB R4, R5, R6   // 도달 불가능
L2:

// 최적화 후
BR L2
L2:
// 또는 BR 자체도 제거 가능 (연속된 레이블이면)

// 최적화 전
BR L1
...
L1: BR L2

// 최적화 후
BR L2     // L1을 건너뛰고 직접 L2로

// 최적화 전
ADD R1, R1, #0   // x + 0 = x
MUL R2, R2, #1   // x * 1 = x
MUL R3, R3, #2   // x * 2

// 최적화 후
// ADD 제거 (항등 연산)
// MUL 제거 (항등 연산)
SHL R3, R3, #1   // 곱셈을 시프트로 대체 (강도 감소)

// 최적화 전
MUL R1, R2, #4    // 곱셈 (느림)
MUL R3, R4, #8
DIV R5, R6, #2

// 최적화 후
SHL R1, R2, #2    // 왼쪽 시프트 (빠름): x*4 = x<<2
SHL R3, R4, #3    // x*8 = x<<3
SHR R5, R6, #1    // 오른쪽 시프트: x/2 = x>>1

// 최적화 전
LD  R1, a
ADD R1, R1, #1
ST  a, R1

// 최적화 후 (기계가 INC 명령어를 지원하는 경우)
INC a