상수를 접고, CFG 를 세우고, φ 자리를 구한다

목표

AST 의 상수를 접고 정해진 가지를 걷어 내며, 6모듈의 청크에서 기본 블록과 CFG 를 세워 닿지 않는 코드를 지웁니다. 그 그래프에서 지배자·지배 경계를 구해 SSA 의 φ 가 들어갈 블록을 계산합니다. 최적화한 프로그램은 같은 결과를 내면서 명령을 덜 실행해야 합니다.

왜 중요한가

최적화는 "할 수 있는 것" 보다 "하면 안 되는 것" 이 먼저입니다. 0 나누기를 미리 계산해 버리거나, 코드를 지운 뒤 점프를 다시 잇지 않으면 빠르지만 틀린 프로그램이 됩니다. 그리고 CFG·지배자·SSA 는 실무 컴파일러의 최적화가 모두 딛고 선 자료 구조라, 여기서 손으로 계산해 본 것이 10모듈에서 LLVM IR 을 읽는 눈이 됩니다.

규칙

fold(식)          양쪽이 리터럴이면 계산해 리터럴 하나로(64비트 감기·0 쪽 나눗셈은 인터프리터와 같다).
                  0 으로 나누기·나머지, 음수 지수, 타입이 다른 ==, 타입이 맞지 않는 연산은 접지 않는다.
                  접은 값은 원래 노드의 위치를 물려받는다. 원래 트리는 바꾸지 않는다(copy 로 새 노드).
                  && 의 왼쪽이 false(|| 는 true)면 그 왼쪽 리터럴, 반대면 오른쪽을 접은 것.
fold_program      식을 모두 접고: if(true) → then 블록, if(false) → else(없으면 문장째 삭제), while(false) → 삭제.
leaders(code)     0, 점프 목적지(코드 끝이 아니면), 점프·RETURN 바로 다음(끝이 아니면) — 오름차순
basic_blocks      [[시작, 끝)] · cfg(code) → {"blocks", "succ"}: 흘러내리는 쪽 먼저, 점프하는 쪽 다음
                  JUMP 는 흘러내리지 않고 RETURN 은 다음이 없다. 코드 끝으로 가는 것은 적지 않는다.
remove_unreachable  입구(블록 0)에서 닿지 않는 블록을 지우고, 남은 점프의 오프셋을 새 자리로 다시 잰다.
                  상수 풀의 함수 청크도 같은 방법으로. 이름·인자 수·상수 풀은 그대로.
dominators(succ)  블록마다 지배자(자기 포함, 오름차순). 닿지 않는 블록은 []. 고정점까지 되풀이.
idom(succ)        직속 지배자(입구와 닿지 않는 블록은 None)
dominance_frontier / phi_blocks(succ, {변수: [정의 블록]})  반복 지배 경계로 φ 가 필요한 블록(오름차순)
optimize_source   (전 청크, 뒤 청크, 오류) = 파싱·의미 분석 → compile(원래) / compile(fold_program) → remove_unreachable

단계

/root/mini/opt.py 의 fold(n) 을 채웁니다 — 채점기가 고정 식과 무작위 식 250개의 접은 트리와 노드 위치를 대조합니다.
fold_stmt·fold_list·fold_program 을 채웁니다 — 접기 전후의 실행 결과가 같아야 합니다.
JUMPS·jump_target·leaders·basic_blocks 를 채웁니다.
cfg(code) 를 채웁니다.
reachable(succ) 와 remove_unreachable(chunk) 를 채웁니다.
dominators(succ) 와 idom(succ) 를 채웁니다.
dominance_frontier(succ) 와 phi_blocks(succ, defs) 를 채웁니다.
optimize_source(src) 를 채우고, /opt/fixtures/mini/programs/manifest.json 의 opt 목록 프로그램마다 전·후 청크를 VM 으로 돌려 /root/mini/opt_report.json 에 {이름: {"before": 명령 수, "after": 명령 수, "same_output": true/false}} 를 적습니다.

참고

python3 /root/mini/mini.py opt /opt/fixtures/mini/programs/const.mini 가 최적화 전후 명령 수를 보여 줍니다.
컴파일러·VM 까지의 파일은 실습을 시작할 때 깔려 있습니다.
흔한 실수: 0 나누기를 접다가 컴파일러가 죽는 것, 접은 값의 위치를 버리는 것, true && x 를 true 로 접는 것, 지운 뒤 점프 오프셋을 그대로 두는 것, JUMP 도 흘러내린다고 보는 것, φ 를 한 번만 넓히는 것.
세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다.

상수를 접는다 — 접으면 안 되는 것부터

copy.copy 로 노드를 복사한 뒤 자식을 먼저 접습니다. 양쪽이 Int·Bool 리터럴이고 타입이 맞을 때만 계산하되, 나누는 수가 0 이거나 지수가 음수면 그대로 둡니다. 새 리터럴은 원래 노드의 line·col 로 만듭니다.

정해진 가지를 걷는다

문장마다 식을 fold 합니다. if 의 조건이 Bool 리터럴이 되면 고른 가지(Block 이라 스코프가 남습니다)를 다시 fold_stmt 하고, 가지가 없으면 None 으로 문장을 지웁니다. fold_list 는 None 을 버립니다. 함수 몸체도 잊지 마세요.

기본 블록

리더 집합에 0 을 넣고, 명령마다 점프면 목적지(i + 1 + 오프셋)가 코드 안일 때 넣고, 점프나 RETURN 이면 바로 다음(i + 1)이 코드 안일 때 넣습니다. 정렬한 리더를 이웃끼리 짝지으면 [시작, 끝) 입니다.

제어 흐름 그래프

블록의 마지막 명령을 봅니다. RETURN 이면 다음이 없고, JUMP 면 목적지 블록 하나, 조건 점프면 흘러내리는 블록(끝 자리가 리더인 블록)과 목적지 블록 — 같으면 하나만. 그 밖은 흘러내리는 블록 하나입니다. 목적지가 코드 끝이면 적지 않습니다.

닿지 않는 코드를 지우고 점프를 다시 잇는다

블록 0 에서 succ 를 따라 닿는 블록을 모읍니다. 남길 명령의 옛 자리 → 새 자리 표를 만들고(코드 끝도 새 끝으로), 점프마다 새 오프셋 = 새 목적지 - (새 자리 + 1) 로 다시 잽니다. 상수 풀의 dict 는 재귀로 같은 일을 합니다.

지배자

닿는 블록마다 처음엔 '모든 닿는 블록' 으로 두고 입구만 {0} 으로 둡니다. 입구가 아닌 블록은 앞 블록들(닿는 것만)의 지배자 교집합에 자기를 더한 것으로 바꾸기를, 한 바퀴 동안 아무것도 바뀌지 않을 때까지 되풀이합니다. 직속 지배자는 엄격한 지배자 가운데 가장 가까운(지배자 집합이 가장 큰) 것입니다.

지배 경계와 φ 자리

앞 블록이 둘 이상인 블록 b 마다, 앞 블록 p 에서 시작해 b 의 직속 지배자에 닿을 때까지 직속 지배자 사슬을 올라가며 지나는 블록의 경계에 b 를 넣습니다. φ 자리는 정의 블록들의 경계에서 시작해, 새로 둔 φ 블록도 정의로 쳐서 더는 늘지 않을 때까지 넓힙니다.

최적화 전후를 잰다

optimize_source 는 같은 프로그램을 두 번 컴파일합니다 — 한 번은 그대로, 한 번은 fold_program 한 뒤 remove_unreachable. 보고서는 두 청크를 run_chunk 로 돌린 executed 와, 출력·오류가 같은지를 적습니다. 숫자는 코드로 만들어 쓰세요.