solution

Cho đoạn mã TAC tuyến tính (không rẽ nhánh) gồm $n$ dòng, mỗi dòng dạng x = a hoặc x = a op b (a, b là tên biến hoặc hằng số nguyên, op $\in \{+,-,*,/\}$), và tập các biến "sống ở đầu ra" (live-out) ngay sau khi thực hiện xong dòng lệnh cuối cùng (các biến này còn được sử dụng ở phần mã phía sau, không được cho biết trong đề).

Với straight-line code, định nghĩa dataflow lùi (backward) kinh điển: gọi $\mathrm{def}(i)$ là biến được gán ở dòng $i$ (vế trái), $\mathrm{use}(i)$ là tập các biến (không tính hằng số) xuất hiện ở vế phải dòng $i$. Đặt $\mathrm{OUT}(n) = \text{live\_out}$ (cho trước). Với $i$ chạy từ $n$ xuống $1$: $\mathrm{IN}(i) = \big(\mathrm{OUT}(i) \setminus \{\mathrm{def}(i)\}\big) \cup \mathrm{use}(i)$ và với $i > 1$: $\mathrm{OUT}(i-1) = \mathrm{IN}(i)$.

$\mathrm{IN}(i)$ chính là tập các biến còn sống ngay trước khi thực hiện dòng $i$. Hãy in ra tập $\mathrm{IN}(i)$ cho mọi $i$ từ $1$ đến $n$.

Ví dụ: với đoạn mã a=1; b=2; c=a+b; d=c*2 và live-out $=\{d\}$, kết quả là $\mathrm{IN}(1)=\emptyset$, $\mathrm{IN}(2)=\{a\}$, $\mathrm{IN}(3)=\{a,b\}$, $\mathrm{IN}(4)=\{c\}$.