Dạng SSA (Static Single Assignment) yêu cầu mỗi biến chỉ được gán giá trị đúng một lần; tại các điểm hợp nhất luồng điều khiển (nơi nhiều nhánh gặp lại nhau), trình biên dịch phải chèn một hàm φ (phi-function) cho mỗi biến có thể mang giá trị khác nhau tùy theo nhánh đã đi qua.
Bài này dùng một tiêu chí chèn φ đơn giản hoá (chỉ xét khối tiền nhiệm trực tiếp trong CFG, không tính đến biên thống trị — dominance frontier — đầy đủ như thuật toán SSA chuẩn): cho một khối đích q trong đồ thị luồng điều khiển (CFG) gồm n khối và m cạnh có hướng, cùng tập biến được định nghĩa (gán giá trị) trong mỗi khối. Biến v cần chèn φ tại q khi và chỉ khi tồn tại ít nhất 2 khối tiền nhiệm trực tiếp khác nhau của q (tức các khối u có cạnh u→q) mà v nằm trong tập biến được định nghĩa của khối đó (một khối tự nối tới chính q qua vòng lặp cũng được tính là một tiền nhiệm trực tiếp).
Hãy liệt kê tất cả các biến cần chèn φ tại khối truy vấn q.
Dòng 1: hai số nguyên n, m.
m dòng tiếp theo: mỗi dòng u v — cạnh có hướng từ khối u tới khối v.
n dòng tiếp theo (lần lượt cho khối 0,1,…,n−1): mỗi dòng bắt đầu bằng số nguyên ki — số biến được định nghĩa trong khối i — theo sau là ki tên biến cách nhau khoảng trắng (ki có thể bằng 0, khi đó dòng chỉ chứa số 0).
Dòng cuối: số nguyên q — chỉ số khối truy vấn (0≤q<n).
In ra một dòng chứa các biến cần chèn φ tại khối q, đã sắp xếp theo thứ tự alphabet, cách nhau một khoảng trắng (nếu không có biến nào thỏa mãn, in một dòng trống).
Ví dụ:
Đầu vào:
4 4
0 1
0 2
1 3
2 3
0
1 x
1 y
0
3
Đầu ra:
Đầu vào:
4 4
0 1
0 2
1 3
2 3
0
1 x
1 x
0
3
Đầu ra:
x
Đang tải editor...