solution

Cho một khối lệnh cơ bản gồm $n$ câu lệnh dạng x = y op z, với op $\in \{+, *\}$ (hai phép toán giao hoán), $y, z$ mỗi cái là tên một biến hoặc một hằng số nguyên. Hãy áp dụng thuật toán đánh số giá trị cục bộ (local value numbering) để khử biểu thức con chung (local CSE):

• Mỗi "giá trị" khác nhau xuất hiện trong khối (dù là giá trị của một hằng số, của một biến chưa từng được gán trong khối trước khi dùng làm toán hạng, hay của kết quả một phép tính) được cấp một value number — số nguyên duy nhất, cấp tăng dần bắt đầu từ 1 theo đúng thứ tự lần đầu giá trị đó xuất hiện trong khối.
• Hai hằng số bằng nhau luôn có cùng value number. Một biến luôn mang value number của giá trị nó đang giữ tại thời điểm hiện tại (được cập nhật sau mỗi lần gán).
• Vì op giao hoán, biểu thức y op z được nhận diện duy nhất bởi cặp (op, $\{vn(y), vn(z)\}$) — tập hợp không phân biệt thứ tự hai toán hạng.
• Xét lần lượt từng câu lệnh x = y op z: nếu đã tồn tại một câu lệnh TRƯỚC ĐÓ có cùng cặp (op, $\{vn(y),vn(z)\}$) (đã sinh ra value number $V$), thì phép tính hiện tại là THỪA — thay vì tính lại, $x$ chỉ cần được gán bằng giá trị $V$ đã có sẵn (copy), và câu lệnh được thay bằng x = w, với $w$ là biến (hoặc hằng số) đầu tiên từng mang value number $V$ đó (tức biến ở vế trái của chính câu lệnh đã tạo ra $V$ lần đầu, hoặc hằng số/biến gốc nếu $V$ chỉ là value number của một toán hạng đơn). Nếu KHÔNG thừa, cấp một value number mới cho biểu thức và giữ nguyên câu lệnh gốc.

Yêu cầu: in ra mã đã được tối ưu — với mỗi câu lệnh, theo đúng thứ tự gốc, in dạng đã tối ưu như mô tả ở trên (giữ nguyên x = y op z nếu không thừa, hoặc x = w nếu thừa).

Ví dụ:

4
t1 = a + b
t2 = b + a
t3 = a * b
t4 = t1 + 1

Kết quả:

t1 = a + b
t2 = t1
t3 = a * b
t4 = t1 + 1

(t2 = b + a trùng biểu thức giao hoán với t1 = a + b nên được thay bằng t2 = t1; t3 dùng phép * khác + nên không trùng; t4 cộng với hằng số 1 nên là một biểu thức khác, không thừa.)