solution

Khi chuyển chương trình sang dạng SSA (Static Single Assignment), tại các điểm hợp nhất (join point) của nhiều luồng định nghĩa cùng một biến, trình biên dịch phải chèn một hàm phi ($\phi$) để gộp các giá trị đến từ nhiều nhánh. Vị trí cần chèn $\phi$ cho một biến được xác định chính xác bằng biên trội lặp (Iterated Dominance Frontier — IDF) của tập các khối chứa định nghĩa của biến đó.

Cho một CFG gồm $n$ khối đánh số $1..n$ (khối $1$ là điểm vào, mọi khối đều tới được từ khối $1$), và tập $S$ gồm $k$ khối có chứa định nghĩa của một biến $v$. Hãy tính tập các khối cần chèn hàm $\phi$ cho $v$, theo thuật toán chuẩn:

1. Với hai khối $a,b$: $a$ trội (dominate) $b$ nếu mọi đường đi từ khối $1$ đến $b$ đều đi qua $a$ (quy ước $a$ luôn trội chính nó). $a$ trội thực sự $b$ nếu $a$ trội $b$ và $a \ne b$.
2. Biên trội của khối $n$, ký hiệu $DF(n)$, là tập các khối $m$ sao cho tồn tại một cạnh $(p \to m)$ trong CFG với $n$ trội $p$, nhưng $n$ không trội thực sự $m$.
3. Biên trội lặp $IDF(S)$ là bao đóng nhỏ nhất chứa $DF(x)$ cho mọi $x \in S$, và với mọi khối $m$ vừa được thêm vào, tiếp tục thêm $DF(m)$, lặp lại cho đến khi không còn khối mới nào — chính là tập các khối cần chèn hàm $\phi$ cho biến $v$ (lưu ý: một khối $s \in S$ chỉ được tính là cần $\phi$ nếu bản thân nó cũng xuất hiện trong bao đóng này).

Ví dụ: CFG hình thoi $1\to2$, $1\to3$, $2\to4$, $3\to4$, với $S=\{2,3\}$ (biến được định nghĩa ở cả hai nhánh). Khối 4 là điểm hợp nhất của hai nhánh nên $DF(2)=DF(3)=\{4\}$, do đó cần chèn $\phi$ tại khối 4 — kết quả là $\{4\}$.