solution

Gấp hằng số (constant folding) và lan truyền hằng số (constant propagation) là các phép tối ưu mã cơ bản: nếu tất cả toán hạng của một phép tính đều đã biết là hằng số tại thời điểm biên dịch, trình biên dịch tính luôn kết quả thay vì để lại phép tính đó cho lúc chạy; đồng thời, giá trị hằng đã biết của một biến được "lan truyền" vào các phép tính sử dụng biến đó sau này.

Cho một chương trình dạng mã ba địa chỉ (TAC) tuyến tính (không có rẽ nhánh/vòng lặp), gồm $n$ lệnh, mỗi lệnh có một trong hai dạng:

• dst = src (phép gán/sao chép), hoặc
• dst = src1 op src2 với op $\in \{+, -, *, /\}$,

trong đó dst luôn là tên biến (chuỗi chữ cái/chữ số, bắt đầu bằng chữ cái), còn src, src1, src2 mỗi cái là hoặc tên biến, hoặc một hằng số nguyên (có thể âm). Phép / là chia lấy phần nguyên làm tròn về 0 (truncation, giống phép chia số nguyên trong C/C++, ví dụ $-7 / 2 = -3$).

Hãy xử lý tuần tự từng lệnh theo thuật toán sau, duy trì một bảng các biến đã biết là hằng số (ban đầu rỗng):

1. Với mỗi toán hạng (biến hoặc hằng), "giá trị đã biết" của nó là: chính nó nếu là hằng số; hoặc giá trị hằng đang lưu trong bảng nếu là biến và biến đó hiện có mặt trong bảng; hoặc "chưa biết" nếu là biến không có trong bảng.
2. Nếu tất cả toán hạng ở vế phải đều đã biết giá trị hằng: tính luôn kết quả, ghi dst vào bảng với giá trị này, và xuất ra lệnh dst = <kết quả>.
3. Nếu có ít nhất một toán hạng chưa biết: loại dst khỏi bảng (vì từ nay giá trị của nó không còn là hằng số đã biết), và xuất ra lệnh gốc nhưng thay mỗi toán hạng đã biết hằng số bằng giá trị hằng của nó (lan truyền hằng số), còn toán hạng chưa biết giữ nguyên tên biến.

Lưu ý: nếu một biến dst được gán lại sau đó bằng một biểu thức không hằng, nó sẽ bị loại khỏi bảng (không còn được coi là hằng số nữa) cho tới khi được gán lại bằng một hằng số.

Ví dụ: với 3 lệnh t1 = 3 + 4, t2 = t1 * 2, t3 = x + t2 (biến x không xuất hiện ở vế trái lệnh nào trước đó nên luôn chưa biết), kết quả là:

t1 = 7
t2 = 14
t3 = x + 14