고속도로에서 나들목과 나들목 사이 구간은 한번 들어서면 끝까지 달릴 수밖에 없다. 컴파일러가 만든 코드에서도 중간에 끼어들거나 빠져나갈 수 없이 처음부터 끝까지 한 줄씩 차례로 실행되는 구간을 한 덩어리로 묶고, 덩어리에서 덩어리로 갈 수 있는 길을 화살표로 이으면 프로그램의 지도가 된다. 덩어리 안에서는 “윗줄이 반드시 먼저 실행됐다”고 믿을 수 있어서 코드를 고치기 쉽다. 덩어리 밖으로 나가면 어느 길로 왔는지 모르기 때문에 훨씬 조심해야 한다.
예시로 보기
코드를 고쳐 더 빠르게 만들려면 “이 줄에 올 때 저 변수 값이 무엇인가”를 알아야 한다. 점프가 섞여 있으면 바로 윗줄이 방금 실행됐는지조차 알 수 없다. 그래서 먼저 코드를 “위에서 아래로만 흐르는 구간”으로 자른다.
int x, y, z;
y = 10 + 100;
if (x == 10) z = y;
else x = y;
y = 10;
이 코드의 3주소 코드 열 줄은 네 덩어리로 잘린다.
┌──────────────────┐
│ t0 = 10 + 100 │
│ y = t0 │ 블록 1
│ t1 = x == 10 │
│ if t1 goto L0 │ ← 점프는 블록의 마지막 줄
├──────────────────┤
│ x = y │ 블록 2
│ goto L1 │
├──────────────────┤
│ L0: │ ← 레이블은 블록의 첫 줄
│ z = y │ 블록 3
├──────────────────┤
│ L1: │ 블록 4
│ y = 10 │
└──────────────────┘
덩어리들을 길로 이으면 이렇다.
flowchart TD
S(["START"]) --> B1["블록 1<br/>t0 = 10 + 100<br/>y = t0<br/>t1 = x == 10<br/>if t1 goto L0"]
B1 -->|"t1이 참"| B3["블록 3<br/>L0:<br/>z = y"]
B1 -->|"t1이 거짓"| B2["블록 2<br/>x = y<br/>goto L1"]
B2 --> B4["블록 4<br/>L1:<br/>y = 10"]
B3 --> B4
B4 --> E(["END"])
블록 1에서 길이 둘로 갈린다. 블록 3은 끝에 점프가 없어서 바로 아래의 블록 4로 흘러간다. 블록 2는 goto L1로 블록 4에 간다.
정의
기본 블록(basic block). 연달아 놓인 3주소 명령의 줄 가운데 더 늘릴 수 없이 긴 것으로, 두 조건을 지킨다.
- 프로그램은 블록의 첫 명령으로만 블록에 들어올 수 있다. 중간 줄로 뛰어 들어오는 점프가 없다.
- 프로그램은 블록의 마지막 명령에서만 멈추거나 갈라진다. 중간 줄에서는 멈추지도 다른 곳으로 뛰지도 않는다.
“더 늘릴 수 없이 길다(maximal)”는 위아래로 한 줄을 더 붙이면 두 조건 중 하나가 깨진다는 뜻이다. 블록 1에 x = y를 붙이면 if t1 goto L0가 중간 줄이 되어 둘째 조건이 깨진다.
블록 자르는 법. 블록의 첫 줄이 될 자리 세 가지를 찾고, 한 첫 줄부터 다음 첫 줄 바로 앞까지를 한 블록으로 묶는다1.
- 코드의 맨 첫 명령.
- 점프가 닿는 곳, 곧 레이블이 붙은 줄.
- 점프(
goto,if … goto,ifnot … goto) 바로 다음 줄.
위 예에서 첫 줄은 t0 = 10 + 100(규칙 1), x = y(규칙 3), L0:(규칙 2), L1:(규칙 2, 3)이다.
제어 흐름 그래프(control flow graph). 기본 블록을 점으로 하는 그래프다. 화살표는 어느 블록 다음에 어느 블록이 실행될 수 있는지를 나타낸다. 블록 \(B\)에서 블록 \(C\)로 화살표를 긋는 경우는 둘이다1.
- \(B\)의 마지막 줄이 \(C\)의 레이블로 가는 점프다.
- \(C\)가 코드에서 \(B\) 바로 다음에 있고, \(B\)의 마지막 줄이 무조건 점프(
goto)가 아니다.
조건 분기로 끝나는 블록은 화살표가 둘 나간다. 시작과 끝을 나타내는 START와 END를 덧붙인다.
지역과 전역. 최적화가 기본 블록 하나 안에서만 일하면 지역(local) 최적화, 제어 흐름 그래프 전체를 보고 일하면 전역(global) 최적화다.
| 지역 최적화 | 전역 최적화 | |
|---|---|---|
| 보는 범위 | 기본 블록 하나 | 그래프 전체 |
| 예 | 블록 1의 t0 = 10 + 100, y = t0를 y = 110으로 |
블록 3의 z = y를 z = 110으로, 블록 2의 x = y를 x = 110으로 |
| 믿을 수 있는 것 | 블록 안 윗줄은 반드시 먼저 실행됐다 | 어느 길로 왔는지 모른다. 들어오는 모든 길을 따져야 한다 |
z = y를 z = 110으로 바꿔도 되는 까닭은 블록 3에 들어오는 길이 블록 1에서 오는 것 하나뿐이고, 블록 1을 나올 때 y가 110이기 때문이다. 이것은 블록 3만 봐서는 알 수 없다. 블록 4의 y = 10 뒤에서는 y가 10이다2.
활용
- 블록 안에서 하는 일: 지역 최적화 기법, 사용 가능한 식 분석, 생존 변수 분석
- 그래프 전체로 넓히기: 전역 생존 변수 분석, 전역 사용 가능한 식 분석
- 구현: 40_basic-block-cfg_impl.py
- 반복문은 그래프에서 아래 블록에서 위 블록으로 되돌아가는 화살표로 나타난다. 화살표를 따라가다 같은 블록으로 돌아오는 길(사이클)이 있으면 반복이 있다는 뜻이다2.
- 흔한 실수: 레이블 줄을 앞 블록의 끝에 붙인다. 조건 분기 뒤에 “분기하지 않고 그냥 내려가는” 화살표를 빠뜨린다.
goto로 끝나는 블록에서 바로 아래 블록으로 화살표를 긋는다.
연결
확인 문제
C1 기본 블록의 정의를 두 조건과 함께 쓰고, 제어 흐름 그래프에서 점과 화살표가 각각 무엇인지 쓰라.
답: 기본 블록은 연달아 놓인 3주소 명령의 줄 가운데 더 늘릴 수 없이 긴 것으로, ① 첫 명령으로만 들어올 수 있고 ② 마지막 명령에서만 멈추거나 갈라진다. 제어 흐름 그래프의 점은 기본 블록이고, 화살표는 한 블록 다음에 실행될 수 있는 블록을 가리킨다.
C2 다음 코드를 기본 블록으로 자르고 화살표를 모두 쓰라. L0: / t0 = y + z / t1 = x < t0 / ifnot t1 goto L1 / t2 = x + 1 / x = t2 / goto L0 / L1: / r = x
답: 블록 A: L0:부터 ifnot t1 goto L1까지 네 줄. 블록 B: t2 = x + 1, x = t2, goto L0 세 줄. 블록 C: L1:, r = x 두 줄. 화살표: START → A, A → B(조건이 참이라 그냥 내려감), A → C(L1로 점프), B → A(goto L0), C → END.
이유: B → A가 되돌아가는 화살표다. B는 goto로 끝나므로 B → C 화살표는 없다.
C3 예시 코드에서 (가) t0 = 10 + 100, y = t0를 y = 110으로 바꾸는 것과 (나) z = y를 z = 110으로 바꾸는 것은 각각 지역 최적화인가 전역 최적화인가? (나)를 블록 4 뒤의 w = y에 똑같이 해서 w = 110으로 바꾸면 왜 틀리는가?
답: (가)는 지역. 두 줄이 같은 블록 안에 있어 그 블록만 보고 고친다. (나)는 전역. y가 110이라는 사실은 블록 1에 있고 z = y는 블록 3에 있어, 블록 사이의 길을 봐야 한다. 블록 4에서 y = 10으로 다시 넣기 때문에 그 뒤의 y는 10이다. w = 110은 틀린다.
이유: x = 10으로 실행하면 끝에서 (x, y, z) = (10, 10, 110), x = 3이면 (110, 10, 처음 z 그대로)다. 고친 코드도 같은 값을 낸다.