[컴파일러] 14. 데이터 흐름 분석 프레임워크

// 블록 B:
//  [지점 1] d1: x = a + b [지점 2]
//  [지점 2] d2: y = x * c [지점 3]
//
// IN[B] = 지점 1에서의 정보
// OUT[B] = 지점 3에서의 정보

OUT[B] = f_B(IN[B])

OUT[B] = gen[B] U (IN[B] - kill[B])

// 합집합(Union): 어느 경로에서든 성립하면 포함
IN[B] = U OUT[P]  (P는 B의 모든 선행자)

// 교집합(Intersection): 모든 경로에서 성립해야 포함
IN[B] = n OUT[P]  (P는 B의 모든 선행자)

명령어 d: x = y op z에 대해:
  gen = 정의 d 자체
  kill = x에 대한 모든 다른 정의

// 블록 B에 d1, d2, ..., dk 명령어가 순서대로 있을 때
// 뒤의 명령어가 앞의 명령어를 덮어쓸 수 있음

gen[B] = gen(dk) U (gen(dk-1) - kill(dk)) U ...
kill[B] = kill(d1) U kill(d2) U ... U kill(dk)

OUT[B] = gen[B] U (IN[B] - kill[B])
IN[B]  = U OUT[P]  (P는 B의 모든 선행자)

// 흐름 그래프:
//   B1 -> B2 -> B3
//          ^     |
//          +-----+

// B1: d1: x = 5        gen={d1}, kill={d2,d4}
// B2: d2: x = x + 1    gen={d2}, kill={d1,d4}
// B3: d3: y = x         gen={d3}, kill={}
//     d4: x = y + 1     gen={d4}, kill={d1,d2}

// gen[B3] = {d4} U ({d3} - {d1,d2}) = {d3, d4}
// kill[B3] = {d1, d2}

초기값: OUT[B] = {} (모든 B에 대해)

반복 1:
  IN[B1] = {}
  OUT[B1] = {d1} U ({} - {d2,d4}) = {d1}

  IN[B2] = OUT[B1] U OUT[B3] = {d1} U {} = {d1}
  OUT[B2] = {d2} U ({d1} - {d1,d4}) = {d2}

  IN[B3] = OUT[B2] = {d2}
  OUT[B3] = {d3,d4} U ({d2} - {d1,d2}) = {d3,d4}

반복 2:
  IN[B2] = OUT[B1] U OUT[B3] = {d1} U {d3,d4} = {d1,d3,d4}
  OUT[B2] = {d2} U ({d1,d3,d4} - {d1,d4}) = {d2,d3}

  IN[B3] = OUT[B2] = {d2,d3}
  OUT[B3] = {d3,d4} U ({d2,d3} - {d1,d2}) = {d3,d4}

반복 3:
  IN[B2] = {d1} U {d3,d4} = {d1,d3,d4}  (변화 없음)
  -> 수렴!

// 전달 함수 (역방향)
IN[B]  = use[B] U (OUT[B] - def[B])
OUT[B] = U IN[S]  (S는 B의 모든 후속자)

// 블록 B:
//   x = y + z    // use: {y, z}, def: {x}
//   a = x + 1    // use: {x}, def: {a}  (x는 위에서 정의되었으므로 use[B]에 포함 안됨)

// use[B] = {y, z}  (정의 전에 사용된 변수)
// def[B] = {x, a}  (정의된 변수)

// B1: a = 1; b = 2
// B2: c = a + b; d = c - a
// B3: d = b + d; (출구)

// use[B1] = {}, def[B1] = {a, b}
// use[B2] = {a, b}, def[B2] = {c, d}
// use[B3] = {b, d}, def[B3] = {d}

// 초기값: IN[B] = {} (모든 B에 대해)

반복 1: (역방향: B3 -> B2 -> B1)
  OUT[B3] = {}  (출구 블록)
  IN[B3] = {b, d} U ({} - {d}) = {b, d}

  OUT[B2] = IN[B3] = {b, d}
  IN[B2] = {a, b} U ({b, d} - {c, d}) = {a, b}

  OUT[B1] = IN[B2] = {a, b}
  IN[B1] = {} U ({a, b} - {a, b}) = {}

  -> 수렴! (변화 없음)

OUT[B]   = e_gen[B] U (IN[B] - e_kill[B])
IN[B]    = n OUT[P]  (P는 B의 모든 선행자)
IN[ENTRY] = {}

// B1: t1 = a + b; c = t1
//     e_gen[B1] = {a+b}
//     e_kill[B1] = {c를 포함하는 수식}

// B2: t2 = a + b; d = t2 - c
//     e_gen[B2] = {a+b, t2-c}
//     e_kill[B2] = {d를 포함하는 수식}

// B3: a = 1
//     e_gen[B3] = {}
//     e_kill[B3] = {a를 포함하는 모든 수식} = {a+b}

OUT[ENTRY] = {}     // 진입점에서는 아무 수식도 가용하지 않음
OUT[B] = U          // 다른 블록은 전체 집합(모든 수식)으로 초기화
                    // (교집합이므로 큰 값에서 시작해야 올바르게 수렴)

알고리즘: 순방향 데이터 흐름 분석

입력: 흐름 그래프, gen/kill 집합, 합류 연산
출력: 각 블록의 IN/OUT 집합

1. 초기화
   OUT[ENTRY] = 초기값
   for (모든 블록 B != ENTRY)
       OUT[B] = 초기값

2. 반복
   changed = true
   while (changed):
       changed = false
       for (모든 블록 B != ENTRY):
           IN[B] = meet(OUT[P] for all predecessors P)
           oldOUT = OUT[B]
           OUT[B] = gen[B] U (IN[B] - kill[B])
           if OUT[B] != oldOUT:
               changed = true

// 도달 정의 분석의 격자
// 원소: 정의들의 부분집합 (2^D)
// 순서: 집합 포함관계 (부분집합)
// meet 연산: 합집합 (U)
// bottom: 공집합 ({})
// top: 전체집합 (D)

// 가용 수식 분석의 격자
// 원소: 수식들의 부분집합 (2^E)
// 순서: 역방향 집합 포함관계 (상위집합)
// meet 연산: 교집합
// bottom: 전체집합 (E)
// top: 공집합 ({})

// 보수적(conservative) 분석:
// - 안전한 쪽으로 근사
// - 최적화 기회를 놓칠 수 있지만, 잘못된 최적화는 하지 않음

// 도달 정의: 실제보다 더 많은 정의가 도달한다고 분석
//   -> 상수 전파를 적용하지 못하는 경우가 생길 수 있음 (안전)

// 가용 수식: 실제보다 더 적은 수식이 가용하다고 분석
//   -> 공통 부분식 제거를 적용하지 못하는 경우가 생김 (안전)

// 정의 d1, d2, d3, d4가 있을 때
// gen[B] = {d1, d3} -> 비트 벡터: 1010
// kill[B] = {d2}    -> 비트 벡터: 0100

// 전달 함수 계산:
// OUT = gen | (IN & ~kill)  (비트 연산으로 한번에 처리)

알고리즘: 워크리스트 기반 반복

1. 모든 블록을 워크리스트에 추가
2. 워크리스트가 비어있지 않은 동안:
   a. 블록 B를 워크리스트에서 꺼냄
   b. OUT[B]를 다시 계산
   c. OUT[B]가 변경되었으면 B의 후속자들을 워크리스트에 추가