9장. 데이터 흐름 분석

"이 변수 살아있나? 죽었나?" — 반복 알고리즘과 SSA 구축, dominance frontier의 세계.

원서 범위: pp. 475–538 키워드: iterative data-flow, dominance, live variables, SSA, dominance frontier, phi function

9.1 들어가며: 컴파일러는 어떻게 "프로그램을 이해하는가"

8장에서 우리는 최적화(optimization)라는 거대한 게임의 입구에 서 있었다. 게임의 룰은 단순했다. (1) 코드를 고치면 좋아질 법한 자리를 찾아라. (2) 그 자리를 고쳐도 안전한지 증명하라. 그런데 두 룰 모두, 컴파일러가 코드를 "꽤 깊게" 이해하고 있어야 가능하다. 프론트엔드가 만들어낸 IR(중간 표현)만 보고는 어림도 없다.

이 깊은 이해의 도구가 바로 정적 분석(static analysis)이다. 정적이라는 건 "컴파일 시점에" 한다는 뜻. 프로그램을 실행하지 않은 채 — 입력값도 모르는 채 — 런타임에 무슨 일이 벌어질지 추론한다. 점쟁이라기보다는 보수적인 회계사에 가깝다. "확실히 안전한 것"만 안전하다고 말한다.

이 장의 주인공은 그 정적 분석의 고전 중의 고전, 데이터 흐름 분석(data-flow analysis)이다. CFG(제어 흐름 그래프) 위에 방정식을 깔고, 그걸 반복 알고리즘으로 풀어서 "이 지점에서 살아있는 변수는?", "이 시점에 이미 계산해 둔 식은?", "이 사용에 도달할 수 있는 정의는?" 같은 질문에 답한다.

장의 후반부는 SSA(정적 단일 할당) 형식으로 넘어간다. SSA는 데이터 흐름 정보와 제어 흐름 정보를 IR 자체에 박아넣는 영리한 표현인데, 현대 컴파일러의 사실상 표준이다. 마지막에는 절(procedure) 경계를 넘는 분석 — 호출 그래프와 절차간 상수 전파 — 까지 살핀다.

이 장이 답하는 질문
프로그램을 실행하지 않고도, "런타임에 어떤 값들이 어디로 흘러갈지"를 어떻게 추론할까? 그리고 그 추론을 어떻게 IR에 직접 인코딩해서 모든 후속 최적화가 거저 활용할 수 있게 만들까?

로드맵

지역 최적화는 지역 정보만으로 충분하다. 슈퍼로컬도 한 분기 트리 안에 갇혀 있으니 까다롭지 않다. 하지만 절 전체를 보는 전역(global) 최적화에 들어서면 얘기가 달라진다. 루프가 있고, 여러 경로가 합쳐지는 합류점(join point)이 있고, 같은 변수가 여러 정의에서 흘러들어올 수도 있다. 이런 골치 아픈 그래프를 사이클까지 포함해서 다룰 수 있는 도구가 데이터 흐름 분석이다.

합류점 (join point) — CFG에서 들어오는 간선이 둘 이상인 노드. 여러 경로의 정보가 한 곳에서 만나는 자리. 데이터 흐름 분석을 어렵게 만드는 주범.

9.2 반복 데이터 흐름 분석

데이터 흐름 분석은 결국 다음 두 가지로 요약된다.

  1. 그래프의 각 노드(보통 기본 블록)에 어떤 집합(set)을 매단다. "이 블록 입구에서 살아있는 변수들의 집합" 같은 식.
  2. 그 집합들 사이의 관계를 방정식(equation)으로 적는다. 그리고 모든 방정식이 동시에 만족될 때까지 반복해서 푼다.

"동시에 만족된다"라는 건 고정점(fixed point)에 도달했다는 뜻이다. 한 번 더 돌려봤는데 아무 집합도 안 변하면, 그게 답이다.

9.2.1 Dominance — 누가 누구의 길목인가

첫 예시는 일부러 단순한 걸 골랐다. 지배 관계(dominance). 진입 노드 b0에서 노드 bj로 가는 모든 경로에 bi가 반드시 들어 있다면, "bi가 bj를 지배한다"고 한다. 기호로는 bi ≫ bj. 모든 노드는 자기 자신을 지배한다.

지배 관계 (dominance) — bi가 bj를 지배한다 ≡ 진입점에서 bj로 가는 모든 경로가 bi를 통과한다. bj로 가려면 무조건 bi를 거쳐야 한다는 뜻.

책에서 쓰는 예시 CFG를 ASCII로 그려보자.

        B0
        │
        B1
       ╱  ╲
      B2   B5
      │   ╱  ╲
      B6 B6  B8
       ╲ │  ╱
         B7
        ╱
       B3 ◀─┐
        │   │
        B4  │  (B3 → B1 back edge)
        └───┘
예제 CFG. B3 → B1이 백 엣지(back edge), 루프를 만든다.

각 노드에 대해 "그 노드를 지배하는 모든 노드들의 집합" Dom(n)을 구한다. 방정식은 이렇게 생겼다.

   Dom(n) = {n} ∪ ( ⋂  Dom(m) )
                  m ∈ preds(n)

해석은 자연스럽다. "n을 지배하는 노드들" = "n 자신" + "n의 모든 선행 노드를 동시에 지배하는 노드들". 모든 길로 들어오는 정보의 교집합이라는 점이 핵심이다 — 모든 길에 등장해야 진짜 지배자니까.

초기 조건: Dom(n0) = {n0}, 나머지는 Dom(n) = N(전체 노드 집합). "다 지배자다" 라는 비관적인 추정으로 시작해서, 반복하며 하나씩 깎아낸다.

반복 풀이 알고리즘

// Round-robin 반복 풀이기
Dom(0) ← {0}
for i ← 1 to n
    Dom(i) ← N

changed ← true
while (changed)
    changed ← false
    for i ← 1 to n
        temp ← {i} ∪ ( ⋂j∈preds(i) Dom(j) )
        if temp ≠ Dom(i) then
            Dom(i) ← temp
            changed ← true
Dominance를 위한 반복 풀이기. 변화가 멈출 때까지 돈다.

이 단순한 루프에 세 가지 의문이 따라붙는다.

종료성: Dom 집합은 단조 감소(monotonic shrink)한다. 한 번 빠진 노드는 다시 들어오지 않는다. 집합은 비어 있을 수 없고(자기 자신은 항상 들어있다), 크기는 |N|을 넘을 수 없다. 단조 + 유한 = 반드시 멈춘다.

정확성: 이 방정식들의 고정점은 유일하다(증명은 데이터 흐름 분석 이론 영역). 그리고 그 유일한 고정점이 정의에 따른 "모든-경로의-합치(meet-over-all-paths)" 해와 같다. 그래서 반복 알고리즘이 내놓는 답은 정의에 부합한다.

효율성: 노드를 어떤 순서로 방문하느냐가 반복 횟수를 결정한다. 전방 문제(Dom 같은)는 역후위 순회(reverse postorder, RPO)가 거의 최적이다. RPO는 "가능한 한 모든 선행 노드를 방문한 뒤에 자기를 방문"하는 순서다. 한 번 돌면서 가능한 한 많은 정보를 모은 뒤에 노드를 평가하니, 변화가 빠르게 전파된다.

역후위 순회 (reverse postorder, RPO) — 후위 순회(postorder)의 역순. 전방 데이터 흐름 문제는 RPO로, 후방 문제는 역방향 CFG의 RPO로 도는 게 일반적인 베스트 프랙티스.

9.2.2 Live-Variable Analysis — 살아있는 변수

다음 예시는 좀 더 진짜 같은 거다. 8장에서 만났던 LiveOut 분석을 다시 끌어온다.

"변수 v가 점 p에서 살아있다(live)"는 건 이런 뜻이다. p에서 출발해서 v를 다시 정의하지 않은 채 v의 사용에 도달할 수 있는 경로가 적어도 하나 있다. 짧게 말해 "p 이후에 누군가 v의 현재 값을 읽을 가능성"이 있느냐. 가능성만 있어도 살아있다고 본다 — 보수적이다.

   LiveOut(n) = ⋃ ( UEVar(m) ∪ ( LiveOut(m) ∩ ¬VarKill(m) ) )
              m ∈ succ(n)

각 항의 의미를 풀어보자.

한 줄로: "n을 빠져나가는 시점에 살아있는 변수" = 모든 후속 m에 대해 "(m이 들어가자마자 쓰는 것) ∪ (m을 통과해 살아남은 것)" 의 합집합. 합집합이다 — 어느 한 길에서라도 살아있으면 전체적으로 살아있다고 봐야 안전하다.

Dom과 LiveOut 비교
  • Dom은 전방(forward) 문제 (선행 노드들의 정보 활용), 합치 연산은 교집합.
  • LiveOut은 후방(backward) 문제 (후속 노드들의 정보 활용), 합치 연산은 합집합.
  • Dom은 그래프 구조만 본다. LiveOut은 각 블록의 코드까지 본다(UEVar, VarKill).
프레임워크는 같다. 방향이 다르고, 합치 연산이 다르고, 블록별 상수 집합이 다를 뿐이다.

후방 문제니까 RPO를 어떤 그래프에 대해 도는가? 역방향 CFG다. 모든 간선의 방향을 뒤집은 그래프 위에서 RPO를 매겨야 의미가 있다 — 그래야 "후속들의 정보가 충분히 모였을 때 자기를 본다".

9.2.3 데이터 흐름 분석의 한계

데이터 흐름 분석은 강력하지만, 맹점도 있다. 컴파일러가 어디까지 알 수 있고, 어디서부터는 손을 놓아야 하는지 알아야 한다.

실행 불가능한 경로(infeasible path): CFG는 모든 간선이 실행 가능하다고 가정한다. 하지만 다음 같은 코드를 보자.

   B0:  x ← f(17)
        if (y < x) // 만약 항상 false라면?
   B1:  z ← x + 3   //   여긴 절대 실행 안 됨
   B2:  x ← 0

만약 (y < x)가 늘 거짓이라면 B1은 죽은 코드. 그러면 B0에서 x의 값은 B2가 곧 덮어쓸 거니까 살아있지 않다고 볼 수 있다. 그런데 분석기는 양쪽 가지를 다 가능하다고 보니까, x ∈ LiveOut(B0)으로 결론짓는다. 정밀도(precision)는 "기호적 실행(symbolic execution)까지만 정확"하다.

배열, 포인터, 함수 호출: A[i,j,k] 같은 참조는 어느 원소를 건드리는지 분석기가 모른다. 보통은 "A 전체를 사용/정의"한 것으로 뭉뚱그린다. 포인터는 더 심하다. 포인터 분석이 따로 없다면, 포인터 대입은 "어느 변수에든 영향을 줄 수 있다"고 가정해야 한다. 그래서 컴파일러들은 보수적으로 "포인터의 잠재적 타깃이 되는 변수는 레지스터에 머무르게 두지 않는다." 함수 호출도 같은 골칫거리. 호출된 함수가 무슨 짓을 하는지 모르면, 모든 가시 변수를 건드린 것으로 봐야 한다.

9.2.4 다른 데이터 흐름 문제들

같은 프레임워크, 다른 변형들. 각각이 특정 최적화를 위한 도구다.

가용 표현식 (Available Expressions)

"점 p에 도달하는 모든 경로에서 식 e가 이미 계산되었고, 그 사이에 e의 어떤 피연산자도 다시 정의되지 않았다"면, p에서 e는 가용(available)하다. 즉, e를 또 계산할 필요가 없다 — 이미 어딘가에 답이 있다. 이게 전역 공통 부분식 제거(global CSE)의 기반이다.

   AvailIn(n) = ⋂ ( DEExpr(m) ∪ ( AvailIn(m) ∩ ¬ExprKill(m) ) )
              m ∈ preds(n)

전방, 교집합. "모든 선행 경로에서 살아남아야" 가용이다 — 한 길에서라도 죽었으면 못 믿는다.

도달 정의 (Reaching Definitions)

"이 사용에 도달할 수 있는 정의는 어느 것들인가?" 변수 v의 정의 d가 연산 i에 도달한다 ≡ i가 v를 읽고, d에서 i까지 v를 다시 정의하지 않은 경로가 있다. 합류점에서 여러 정의가 만나면 그게 곧 ϕ-함수 후보다 — 미리보기.

예측 표현식 (Anticipable Expressions, very busy)

"블록 b 끝에서 식 e가 예측 가능(anticipable)하다"는 건, b를 떠나는 모든 경로에서 e가 곧 평가된다는 뜻. 그렇다면 b 끝에서 e를 미리 계산해도 손해 안 본다. 후방 문제, 교집합. 코드 호이스팅(code hoisting)과 lazy code motion의 기반이다.

절차간 요약 (MayMod, MayRef)

호출 사이트 c = call f를 만났을 때, "f가 건드릴 수 있는 변수들의 집합"을 미리 계산해 두면 단일-절차 분석의 결과를 살릴 수 있다. 이걸 MayMod(p)(p가 수정할 수도 있는 변수들), MayRef(p)(p가 참조할 수도 있는 변수들)로 정리한다. 호출 그래프 위에서 푸는 데이터 흐름 문제다.

패턴이 보이는가
대부분의 데이터 흐름 방정식은 다음 꼴이다: 
f(x) = c1 op1 (x op2 c2)
c1, c2는 코드에서 뽑은 상수 집합, op는 ∪/∩. 이 구조 덕분에 컴파일러 작성자는 일반화된 분석기 하나로 여러 분석을 동시에 처리할 수 있다.

9.3 정적 단일 할당 형식 (SSA Form)

여기까지 보면 한 가지 의문이 떠오른다. 변환마다 자기만의 데이터 흐름 분석을 하나씩 돌리는 건 너무 비싸지 않나? 같은 정보를 또 계산하고, 또 계산하고...

SSA(Static Single-Assignment) 형식은 이 문제에 대한 답이다. IR 자체에 데이터 흐름 정보를 박아넣어서, 한 번 만들어두면 여러 변환이 거저 활용한다.

SSA의 두 가지 룰:

  1. 모든 정의는 고유한 이름을 만든다. 같은 변수를 두 번 쓰면 x0, x1처럼 첨자가 붙는다.
  2. 모든 사용은 정확히 하나의 정의를 가리킨다. 어느 정의에서 왔는지 헷갈릴 일 없다.

이 둘이 맞으려면 합류점이 문제다. 두 길에서 다른 첨자가 들어올 수 있는데 어떻게 사용은 하나만 가리키게 하나? 답: ϕ-함수(phi function)를 끼워 넣는다.

ϕ-함수 (phi function) — 합류점에 놓이는 가짜 연산. 어느 길로 들어왔는지에 따라 인자 중 하나를 골라 결과로 내놓는다. x3 ← ϕ(x2, x0) 은 "왼쪽 간선으로 들어왔으면 x2, 오른쪽 간선으로 들어왔으면 x0"이라는 뜻.

실행 시점에는 ϕ-함수가 진짜 명령어로 존재할 수 없다 — 어느 인자를 고를지를 "어떻게 도착했는지"로 결정해야 하니까. 그래서 SSA는 분석/최적화용 IR이고, 코드 생성 직전에는 다시 풀어야 한다(9.3.5에서). 그 사이의 분석 시기에는 환상적인 도구다.

원본 코드:                       SSA 형식:
   x ← 17 - 4                       x0 ← 17 - 4
   x ← a + b                        x1 ← a + b
   x ← y · z                        x2 ← y · z
            ╲                                ╲
             ╲                                x3 ← ϕ(x2, x0)
   x ← 13                           x4 ← 13
            ╲                                ╲
             ╲                                x5 ← ϕ(x4, x3)
   z ← x · q                        z ← x5 · q
            ╲                                ╲
             ╲                                x6 ← ϕ(x1, x5)
   s ← w · x                        s ← w · x6
SSA로 변환하면 합류점마다 ϕ-함수가 끼어든다. 모든 사용은 정확히 하나의 정의를 가리킨다.

9.3.1 단순한 SSA 만들기

2단계 절차다.

  1. ϕ-함수 삽입. 합류점(=선행 노드가 둘 이상인 블록)의 맨 위에, 절 안에 등장하는 모든 변수에 대해 ϕ-함수를 박아넣는다. 무지막지하다.
  2. 이름 바꾸기. 도달 정의를 계산하고, 정의마다 새 첨자를 부여하고, 사용은 자기에게 도달한 정의를 가리키도록 다시 쓴다.

이 방식은 정확하지만, ϕ-함수를 너무 많이 만든다. 최대 SSA(maximal SSA)라고 부른다. 메모리 낭비, 후속 분석의 비용 상승, 죽은 ϕ-함수까지 가득. 더 똑똑하게 깎아야 한다.

그 똑똑한 깎기를 위해 등장하는 도구가 지배 경계(dominance frontier)다. ϕ-함수가 정확히 어느 자리에 필요한지를 콕 집어준다.

9.3.2 지배 경계 (Dominance Frontiers)

핵심 아이디어: 노드 n의 정의가 ϕ-함수를 강제하는 자리는, "n이 지배하는 영역의 바로 바깥의 합류점"이다.

좀 더 정확히. 노드 n에서의 정의가 합류점 m에서 ϕ-함수를 강제하는 조건은 (1) n이 m의 어떤 선행 노드 q를 지배하고, (2) n이 m을 엄격히 지배(strictly dominate)하지 않는다 — 즉 m에 다른 길로도 도달할 수 있다는 뜻. 이 조건을 만족하는 m들의 집합이 n의 지배 경계 DF(n)이다.

지배 경계 (dominance frontier) — DF(n) = "n이 (지배하는 영역에서 시작해) 지배하지 못하게 되는 첫 노드들의 집합". n이 정의를 두면, DF(n)의 모든 노드에 ϕ-함수가 필요해진다.

예시 CFG에서 B5는 B6, B7, B8을 지배하지만 B3은 지배하지 못한다. B5를 떠나는 모든 경로에서 B3이 "B5가 지배하지 못하는 첫 노드"다. 따라서 DF(B5) = {B3}.

지배자 트리 (Dominator Tree)

지배 경계를 효율적으로 계산하려면 지배자 트리(dominator tree)가 필요하다. n에 가장 가까운 지배자 — 즉 자신을 빼고 n을 지배하는 노드들 중 n에 가장 가까운 것 — 을 직속 지배자 IDom(n)이라 부른다. 이 직속 지배자 관계가 트리를 이룬다.

        B0
        │
        B1
       ╱  ╲
      B2   B5
          ╱│╲
         B6 B7 B8
         │
         B3
         │
         B4
예제 CFG의 지배자 트리. CFG와 다르게 사이클이 없고, 각 노드의 부모는 그 노드의 IDom이다.

지배자 트리는 Dom 정보를 압축해서 담는다. 어떤 노드 n에 대해 Dom(n)은 "트리의 루트에서 n까지의 경로 위 노드들"이다. IDom(n)은 트리에서의 부모.

지배 경계 계산하기

for all nodes n in CFG
    DF(n) ← ∅

for all nodes n in CFG
    if n has multiple predecessors then
        for each predecessor p of n
            runner ← p
            while runner ≠ IDom(n)
                DF(runner) ← DF(runner) ∪ {n}
                runner ← IDom(runner)
지배 경계 계산. 합류점 n의 각 선행자에서 출발해 IDom(n)까지 트리를 거슬러 올라가며 n을 DF에 추가한다.

알고리즘의 직관. 합류점 n의 선행자 p에서 출발해서 지배자 트리를 거슬러 오른다. 멈추는 지점은 IDom(n) — 그 위로는 n을 이미 지배하는 영역이니까. 지나친 모든 노드 r에 대해 "r은 n을 지배하지 못하는데, n으로 가는 길을 가질 수 있다"가 성립하므로 n을 DF(r)에 추가한다.

9.3.3 ϕ-함수 배치

이제 ϕ-함수를 똑똑하게 박는다.

이 방식이 만들어내는 SSA를 준-가지친 SSA(semipruned SSA)라고 부른다. 단일 블록에 갇힌 이름은 자동으로 빠지고, 죽은 ϕ-함수도 어느 정도 줄어든다. 더 적극적으로 LiveOut을 활용해 죽은 ϕ-함수까지 다 쳐낸 게 가지친 SSA(pruned SSA)지만, 그만큼 비싸다.

SSA의 세 종류
  • Minimal SSA — 두 개의 다른 정의가 만나는 합류점에 정확히 ϕ-함수를 둔다. 죽은 ϕ-함수가 남을 수 있음.
  • Semipruned SSA — 단일 블록에 갇힌 이름은 제외. UEVar만으로 판단. 가성비 좋음.
  • Pruned SSA — LiveOut까지 계산해서 죽은 ϕ-함수를 모두 제거. 가장 깔끔하지만 가장 비쌈.

9.3.4 이름 바꾸기 (Renaming)

ϕ-함수를 박았으니, 이제 첨자를 부여한다. 알고리즘은 지배자 트리를 전위 순회(preorder)한다. 각 전역 이름마다 카운터(다음 첨자 번호)와 스택(현재 유효한 첨자)을 둔다.

for each global name i
    counter[i] ← 0
    stack[i] ← ∅
Rename(n0)

NewName(n)                        Rename(b)
    i ← counter[n]                    for each ϕ-function "x ← ϕ(...)" in b
    counter[n] ← counter[n]+1             rewrite x as NewName(x)
    push i onto stack[n]              for each operation "x ← y op z" in b
    return ni                          rewrite y as ytop(stack[y])
                                          rewrite z as ztop(stack[z])
                                          rewrite x as NewName(x)
                                      for each successor s in CFG
                                          fill in ϕ-function parameters
                                      for each child s in dominator tree
                                          Rename(s)
                                      for each "x ← y op z" and "x ← ϕ(...)" in b
                                          pop(stack[x])
이름 바꾸기 알고리즘. 지배자 트리를 전위 순회하며 스택과 카운터로 현재 이름을 관리한다.

스택과 카운터의 역할 분담이 깔끔하다. 카운터는 단조 증가해서 모든 정의에 고유한 번호를 보장한다. 스택은 푸시/팝으로 "지금 이 위치에서 유효한 이름"만 유지한다. 지배자 트리를 거슬러 올라갈 때 스택을 팝하면, 형제 서브트리를 처리할 때 적절한 이름으로 돌아간다.

주의 깊게 봐야 할 부분: 블록 b의 처리가 끝나면, b의 CFG 후속 s들로 가서 s의 ϕ-함수에서 "b로부터 들어오는 인자 슬롯"을 현재 스택 탑으로 채운다. 어느 슬롯인지는 CFG에서 b가 s의 몇 번째 선행자인지로 결정된다.

9.3.5 SSA에서 빠져나오기 (Translation Out of SSA)

실제 머신은 ϕ-함수를 실행할 줄 모른다. 코드 생성 전에 SSA를 풀어야 한다. 가장 단순한 발상: "첨자만 떼고 ϕ-함수 지우자". 안타깝게도 이게 항상 옳지 않다.

// LVN 후 SSA 형식
   a0 ← x0 + y0
   b0 ← a0           // b0 = x0+y0임을 LVN이 알아냄
   a1 ← 17
   c0 ← a0           // c0도 같은 값

여기서 첨자만 떼면 c는 17을 받게 된다 — 망가졌다. 안전한 방법은 ϕ-함수를 복사 연산(copy)들로 풀어내는 것이다. ϕ-함수 xi ← ϕ(xj, xk)는 "j 쪽 간선에 xi ← xj, k 쪽 간선에 xi ← xk"로 분해한다.

잃어버린 복사 문제 (Lost-Copy Problem)

그런데 복사 분해도 문제가 있다. 임계 간선(critical edge)에서 발생한다. 임계 간선이란 출발 노드의 후속이 여럿이고 도착 노드의 선행이 여럿인 간선. 보통은 임계 간선을 분할(split)해서 새 블록을 끼워넣고 거기에 복사를 둔다. 하지만 분할이 곤란할 때(루프 닫힘 분기 등)가 있고, 그러면 복사가 잘못된 자리에 가서 값이 망가진다.

스왑 문제 (Swap Problem)

또 하나의 함정. ϕ-함수들은 모두 동시에 평가된다고 정의되어 있다. 하지만 복사 연산은 순차적이다. x1 ← ϕ(x0, y1), y1 ← ϕ(y0, x1) 같은 ϕ 쌍을 단순 복사로 풀면, 첫 복사가 두 번째 복사에 사용될 값을 망가뜨린다 — 두 변수가 같은 값을 받아버린다. 해결: 임시 변수에 한 번 더 복사를 두는 2단계 프로토콜.

9.3.6 SSA 활용: Sparse Simple Constant Propagation

SSA의 위력을 보여주는 단골 예시가 SSCP(Sparse Simple Constant Propagation)다. "이 변수는 항상 상수 c다"를 찾아내는 분석이다.

각 SSA 이름에 격자(lattice) 값을 매단다. 격자는 다음 세 층:

              ⊤  (Top: 모르는 값)
              │
        ┌─┬─┬─┴─┬─┬─┐
        c1 c2 c3  ...  cn   (구체적인 상수들)
        └─┴─┴─┬─┴─┴─┘
              │
              ⊥  (Bottom: 상수 아님 / 변동값)
상수 전파를 위한 격자. ⊤(미지) → c(상수) → ⊥(변동) 으로만 이동 가능. 한 방향만.

합치 연산의 규칙: ⊤ ∧ x = x, ⊥ ∧ x = ⊥, ci ∧ cj = ci if 같음, 다르면 ⊥.

알고리즘은 워크리스트 기반.

  1. 초기화. 각 SSA 이름의 Value를 ⊤ 또는 알려진 상수로 설정. ϕ-함수는 ⊤로 시작.
  2. 전파. 워크리스트에서 이름 n을 꺼내, n을 사용하는 모든 연산에서 정의되는 이름 m의 새 Value를 계산. Value(m)이 더 낮아지면 갱신하고 m을 워크리스트에 넣는다.

각 이름은 최대 두 번까지만 워크리스트에 들어간다(⊤ → c → ⊥). 그래서 전체 비용은 사용 횟수의 상수배. 굉장히 빠르다.

낙관주의의 위력

왜 ⊤에서 시작하는 게 중요한가? 루프 안의 ϕ-함수 x1 ← ϕ(17, x2), x2 ← x1 + i12를 보자. 만약 x1, x2를 ⊥로 시작했다면(비관적), x1 = 17 ∧ ⊥ = ⊥. 끝. 17이 들어와도 못 본 척 한다. 반면 ⊤로 시작하면(낙관적), x1 = 17 ∧ ⊤ = 17. 그리고 i12가 0이라면 x2 = 17 + 0 = 17. 다시 ϕ를 평가하니 17 ∧ 17 = 17. 수렴!

요지: 사이클이 있는 영역에 정보를 전파하려면 낙관적 초기화가 필요하다. SSA가 이걸 자연스럽게 받아들이게 해주는 게 또 하나의 매력이다.

9.4 절차간 분석 (Interprocedural Analysis)

지금까지는 절(procedure) 하나 안에서 일어나는 일이었다. 절 호출이 끼면 분석이 갑자기 어려워진다. 호출된 함수가 무엇을 건드리는지 모르면 보수적으로 "다 건드린다"고 봐야 하고, 그러면 데이터 흐름 사실의 전파가 호출 사이트에서 멈춘다. 이걸 막으려면 프로그램 전체를 보는 분석이 필요하다.

9.4.1 호출 그래프 구성

모든 절차간 분석은 호출 그래프(call graph)에서 시작한다. 노드는 절차, 간선은 "이 절차가 저 절차를 부른다". 단순한 경우 — call foo(x) 같은 — 라면 쉽다. 절차마다 노드 하나, 호출 사이트마다 간선 하나.

그런데 다음 같은 언어 기능들이 호출 그래프 구성을 험난하게 한다.

9.4.2 절차간 상수 전파 (Interprocedural Constant Propagation)

한 절에서 항상 같은 상수를 매개변수로 받는 절차를 찾으면, 그 절을 그 상수 값에 맞게 특화(specialize)할 수 있다. 절차간 상수 전파는 이런 기회를 호출 그래프 전체에 걸쳐 찾는다.

3단계로 쪼갠다.

  1. 초기 상수 집합 발견. 호출 사이트에서 어느 실인자가 알려진 상수인지 식별. 가장 단순하게는 리터럴 상수, 더 정교하게는 SSCP를 호출자에서 돌린 결과.
  2. 호출 그래프 위에서 전파. 호출자 → 피호출자로 매개변수 값을 전파, 합류점에서는 격자 합치(lattice meet)로 결합.
  3. 절차 통과 모델링: 점프 함수(jump functions). "이 호출 사이트의 매개변수 i가 호출자의 어떤 형식 매개변수에 의존하는가"를 함수로 표현. 가장 단순한 점프 함수는 "그냥 형식 매개변수 그 자체" 또는 "리터럴 상수". 더 복잡하게는 SSA 식 트리.

알고리즘 구조는 SSCP와 닮았다. 워크리스트 기반 반복, 각 형식 매개변수마다 Value를 ⊤로 시작, 격자에서 한 방향으로만 떨어진다. 호출 그래프가 사이클(상호 재귀)을 가져도 잘 작동한다.

9.5 고급 주제

9.5.1 구조적 데이터 흐름과 환원 가능성 (Reducibility)

반복 알고리즘은 보편적이지만 — 어떤 그래프든 풀어준다 — 그래프가 "잘 생겼다"면 더 빠른 알고리즘들이 있다. 그 "잘 생긴"의 정의가 환원 가능 그래프(reducible graph)다.

두 변환을 정의한다.

T1: 자기 루프 제거
       ┌──┐
       │  │
       v  │           v
       a──┘   ⇒       a

T2: 단일 선행자 노드 흡수
       a              a
       │      ⇒
       b
T1은 자기 자신으로 돌아오는 간선을 지운다. T2는 부모가 하나뿐인 자식을 부모에 합친다.

그래프에 T1과 T2를 반복 적용해서 단일 노드로 줄어들면 환원 가능. 안 줄어들면 환원 불가능(irreducible).

구조적 데이터 흐름 알고리즘들은 이 축소 과정을 따라가며 부분 그래프의 데이터 흐름 효과를 합쳐낸 다음, 다시 펼치면서 각 노드에 정보를 전파한다. 환원 불가능한 그래프에서는 이 방식이 망가진다.

희망적인 사실: 환원 불가능 그래프는 실제 코드에서 흔치 않다. 1970년대 구조적 프로그래밍의 보급 이후, 임의의 goto가 줄었기 때문이다. do, while, for, until 같은 구조적 루프는 환원 불가능을 만들어내지 않는다. C의 break처럼 루프를 빠져나가는 건 환원 불가능한 역방향 CFG를 만들 수 있지만, 절차간 분석이 아닌 한 큰 문제는 아니다. 그리고 어차피 반복 알고리즘은 환원 불가능에서도 (느리지만) 정확히 동작한다.

9.5.2 반복 Dominance 빠르게 하기

지배자 정보를 매번 큰 집합으로 들고 다니는 건 메모리가 아깝다. 핵심 통찰: IDom(n) 하나만 알면 Dom(n) 전체를 복원할 수 있다. Dom(n) = "지배자 트리에서 n에서 루트까지의 경로". 그러면 IDom 배열만 들고 다니면 된다.

두 IDom 집합의 교집합은 "두 노드를 지배자 트리에서 거슬러 올라갈 때의 공통 접미부(common suffix)" — 즉 가장 가까운 공통 조상(LCA)이다. RPO 번호를 쓰면 두 포인터로 빠르게 찾을 수 있다(클래식 "two-finger" 알고리즘).

Intersect(i, j)
    finger1 ← i
    finger2 ← j
    while (finger1 ≠ finger2)
        while (RPO(finger1) > RPO(finger2))
            finger1 ← IDoms[finger1]
        while (RPO(finger2) > RPO(finger1))
            finger2 ← IDoms[finger2]
    return finger1
두 노드의 가장 가까운 공통 조상 찾기 — RPO 번호로 트리에서 양쪽 손가락이 만날 때까지 거슬러 올라간다.

전체 알고리즘:

  1. IDoms 배열을 미정으로 초기화, 루트만 자기 자신으로.
  2. RPO 순서대로 노드를 돌며, 각 노드의 새 IDom을 계산(이미 처리된 선행자들의 IDom을 Intersect로 합치는 방식).
  3. 변화가 멈출 때까지 반복.

환원 가능한 그래프에서는 정확히 두 패스만에 끝난다. 첫 패스가 답을 만들고, 두 번째 패스가 변화 없음을 확인. 환원 불가능 그래프는 더 걸린다 — 그래서 이 알고리즘은 환원 가능성 테스트로도 쓸 수 있다(두 번째 패스에서 IDom이 바뀌면 환원 불가능).

9.6 마무리

이 장에서 얻고 가야 할 것들.

다음 10장에서는 이 분석들을 진짜 코드 변환에 어떻게 쓰는지를 본다. 죽은 코드 제거, 강도 감소, 코드 모션, 그리고 지금까지의 모든 기반 위에서 SSA가 빛을 발하는 자리들이다.

← 이전8장. 최적화 입문 다음 →10장. 스칼라 최적화