solution

Cho một đồ thị luồng điều khiển (CFG) gồm $n$ khối cơ bản đánh số $1..n$ và $m$ cạnh có hướng. Khối $1$ là khối bắt đầu (entry): quy ước $IN[1] = \emptyset$ luôn luôn, bất kể có cạnh nào đi vào khối 1 hay không.

Mỗi khối $i$ có một danh sách các định nghĩa (assignment) xảy ra theo thứ tự bên trong khối; mỗi định nghĩa là một cặp (tên biến, id định nghĩa) với id là số nguyên duy nhất toàn chương trình (cho sẵn trong input). Định nghĩa cuối cùng của mỗi biến trong khối $i$ mới được khối đó "sinh ra" ở đầu ra: $GEN[i]$ = tập id của định nghĩa CUỐI CÙNG (trong khối $i$) của mỗi biến được định nghĩa trong khối $i$. $KILL[i]$ = tập TẤT CẢ các id định nghĩa (ở BẤT KỲ khối nào trong toàn chương trình, kể cả khối $i$) của các biến mà khối $i$ có định nghĩa, TRỪ đi các id thuộc $GEN[i]$.

Bài toán định nghĩa tới được (reaching definitions) được tính bằng lặp tới điểm cố định:

$IN[i] = \bigcup_{p \to i} OUT[p] \quad (IN[1] = \emptyset), \qquad OUT[i] = GEN[i] \cup (IN[i] \setminus KILL[i])$

Với mỗi truy vấn gồm một khối $q$ và một biến $v$, hãy cho biết trạng thái của biến $v$ tại đầu vào ($IN[q]$) của khối $q$ khi đạt điểm cố định — đây chính là thông tin trình biên dịch cần để quyết định có thể lan truyền hằng số/copy an toàn tại điểm đó hay không:

• Nếu không có định nghĩa nào của $v$ trong $IN[q]$: in UNDEFINED.
• Nếu có đúng một định nghĩa của $v$ trong $IN[q]$: in UNIQUE <id>.
• Nếu có từ hai định nghĩa trở lên của $v$ trong $IN[q]$ (không an toàn để suy ra một hằng số/nguồn duy nhất): in AMBIGUOUS <k> <id_1> <id_2> ... <id_k> với $k$ là số định nghĩa và các id liệt kê tăng dần.