solution

Cho CFG gồm $n$ khối ($1$ là khối vào entry, mọi khối đều reachable từ khối 1) và $m$ cạnh có hướng.

Bước 1 — Cây thống trị: tính $Dom[b]$ bằng lặp điểm bất động chuẩn: $Dom[1] = \{1\}, \qquad Dom[b] = \{b\} \cup \bigcap_{p \in pred(b)} Dom[p] \ (b \ne 1)$ khởi tạo $Dom[b] = \{1,\ldots,n\}$ với $b \ne 1$, lặp đến ổn định. $idom[b]$ (immediate dominator, $b \ne 1$) là phần tử của $Dom[b] \setminus \{b\}$ có $|Dom[\cdot]|$ lớn nhất (vì các dominator của $b$ luôn tạo thành một dây chuyền — chain — theo quan hệ bao hàm, nên phần tử này là duy nhất và gần $b$ nhất).

Bước 2 — Biên thống trị (dominance frontier, thuật toán Cytron et al.): với mỗi nút $b$ có $\ge 2$ tiền tố, với mỗi tiền tố $p \in pred(b)$: đặt $x \leftarrow p$; trong khi $x \ne idom[b]$: thêm $b$ vào $DF[x]$, rồi $x \leftarrow idom[x]$.

Bước 3 — Đặt hàm $\phi$: cho tập $S$ các khối mà biến $v$ được gán trực tiếp (cho trước). Tính tập tối thiểu $Phi$ các khối cần chèn hàm $\phi$ cho $v$ bằng closure:

worklist = S;  Phi = {}
while worklist không rỗng:
    lấy node n ra khỏi worklist
    for d in DF[n]:
        if d not in Phi:
            Phi.add(d); worklist.add(d)   # phi tại d cũng là 1 định nghĩa mới của v

In ra danh sách các khối thuộc $Phi$, thứ tự tăng dần, cách nhau dấu phẩy (không khoảng trắng); nếu rỗng in -.

Ví dụ

Input:

4 4
1 2
1 3
2 4
3 4
2
2 3

(CFG hình thoi: $1\to2$, $1\to3$, $2\to4$, $3\to4$; biến $v$ được gán ở khối 2 và khối 3)

Output:

4