UEFI 스터디 18차 - 지배자 트리와 루프감지

2 minute read

Published: July 10, 2026

Basic Block (복습)

진입하면 마지막까지 탈출 없이 쭉 실행되는 가장 큰 단위의 코드 시퀀스.

리더(leader)를 잡는 규칙:

entry / exit 노드는 유일하게 두는 게 관례. exit이 여러 개면 단일 exit을 하나 만들어 전부 연결한다. → post-dominator를 정의하려면 단일 exit이 필수.
실행 불가능한 경로도 엣지는 연결한다. 예: if(false)구조상 가능한 흐름. “모든 가능한 경로”라고 해서 실제로 다 갈 수 있는 건 아니다.

마찬가지로 언급될 지배자트리와 루프 탐지에서 사용.

블록 간의 ‘반드시 선행됨’ 관계를 나타낸다.

정의. A dom B ⟺ entry에서 B로 가는 모든 경로가 A를 지난다. = “B가 실행됐으면 A는 반드시 실행됐다.”

entry를 출발점으로 <- 매우 중요 = 출발점이 있어야 함
경로 중 하나라도 A를 안 지나면 정의가 성립하지 않는다.
자기 자신을 제외한 dominator(strict dominator)들은 반드시 일렬로 정렬된다 -> 바로 윗 predecessor만 가리키게하면 공간복잡도 O(N)으로 구현가능.

(예시들때 쓸사진.)

계산 — fixpoint 방식.

당연히 직접 구현할일은 없을테니 이해만해보자! (위에 뭔소리인가했는데, 식을 보고 개념이해가 좀 잘됨)

Dom(entry) = {entry}
Dom(n) = {n} ∪ ( ⋂ Dom(p) )   for all p ∈ pred(n)

entry부터 시작 (자기 자신은 자기 자신을 지배).
블록 n을 지배하는 집합 = 자기 자신 + 모든 predecessor의 지배 집합의 교집합.
- why 교집합? 모든 가능한 이전 노드에서 공통으로 지배해야 나(n)도 지배할 수 있으니까.

위 방식은 O(N^2) 복잡도를 가지며 실전에서는 (거의) 선형 알고리즘을 쓴다: (Cooper-Harvey-Kennedy, Lengauer-Tarjan** )

post-dominator (pdom). dominator의 방향만 뒤집은 것 = reverse CFG(exit 기준)에서의 dominator.

정의. B ∈ DF(A) ⟺ A가 B를 strictly dominate 하지는 않지만, B의 predecessor 중 적어도 하나는 A가 dominate 한다.

→ A의 지배 영향력이 끊기는 경계. = φ-function(mult_equal)을 꽂을 자리를 구할 수 있다.(SSA 구축시 활용가능)

주의: A가 자기 자신의 DF에 들어올 수 있다. “dominate”에는 A = predecessor인 경우도 포함되므로, 루프 헤더는 A ∈ DF(A)가 될 수 있다. φ 배치 이해할 때 헷갈리는 지점.
iterated dominance frontier (DF⁺). 단일 DF만으로 끝나지 않는다. φ가 새 정의를 만들기 때문에, DF를 fixpoint까지 반복 적용해야 SSA의 φ 배치가 완성된다.

백엣지(back edge). 엣지 B → A 중 A dom B

natural loop 구하기. 백엣지 B → A에 대해:

해당 방식으로 못 잡는 경우 — 진입점이 여러 개인 루프.

why? 진입점이 여러 개 => 루프 내부에서 단일 header가 dominate 하는 관계가 안나옴.
이런 CFG를 irreducible flow graph라 부른다.
구조적 프로그래밍(임의 goto 없이 while/for/if/continue/break 같은 제한된 구문만 사용)에서는 절대 안 나온다 → 이 경우 항상 reducible.
주로 바이너리 / 난독화 코드에서 등장.

이미 기드라가 루프탐지 같은거 다해줬는데 어디서쓸수 있을까

써봄직 한곳(클로드 추천)