solution

Một tối ưu hoá kinh điển trong pha sinh mã trung gian là loại bỏ mã chết (dead code elimination) dựa trên phân tích biến sống (liveness analysis): một lệnh gán là mã chết nếu giá trị nó tạo ra không bao giờ được dùng.

Cho một khối lệnh ba địa chỉ (three-address code) tuyến tính gồm $n$ lệnh đánh số $1..n$ theo thứ tự xuất hiện, không có nhãn, không có lệnh nhảy. Lệnh thứ $i$ có một trong hai dạng:

• x = y op z (với op $\in \{+, -, *\}$), hoặc
• x = y (phép gán trực tiếp),

trong đó x luôn là tên biến, còn y, z mỗi cái có thể là tên biến hoặc một hằng số nguyên. Tên biến là chuỗi chữ cái thường độ dài từ 1 đến 10.

Cho tập hợp $L$ các biến sống ngay sau lệnh cuối cùng (live-out của toàn khối — ví dụ các biến còn được dùng ở phần chương trình phía sau khối này). Áp dụng một lượt duyệt lùi (từ lệnh $n$ về lệnh $1$) theo đúng quy tắc phân tích sống chuẩn sau, với $live$ ban đầu $= L$:

• Xét lệnh $i$ theo thứ tự lùi: nếu biến x (vế trái) của lệnh $i$ đang sống (thuộc $live$) thì lệnh $i$ được giữ lại; loại x khỏi $live$, sau đó thêm vào $live$ các biến xuất hiện ở vế phải (y, và z nếu có — bỏ qua nếu chúng là hằng số).
• Nếu x không sống (không thuộc $live$) thì lệnh $i$ là mã chết, bị loại bỏ hoàn toàn — vế phải của nó không đóng góp thêm biến nào vào $live$, và $live$ giữ nguyên.

Vì lượt duyệt là từ cuối lên đầu, việc loại một lệnh có thể khiến biến ở vế phải của nó không còn được dùng nữa, kéo theo lệnh sinh ra biến đó (nếu đứng trước) cũng bị phát hiện là mã chết ngay trong cùng lượt duyệt.

Ví dụ: với 3 lệnh a = x + y, b = a * 2, c = 5 và live-out $=\{c\}$: lệnh 3 giữ lại (sinh c); lệnh 2 bị loại vì b không sống; do đó lệnh 1 cũng bị loại vì a (chỉ được dùng bởi lệnh 2, đã chết) không còn sống. Kết quả: chỉ giữ lại lệnh số 3.