solution

Trong một basic block gồm $n$ lệnh ba địa chỉ dạng t = a op b (op ∈ {+, -, *, /}), áp dụng kỹ thuật đánh số giá trị cục bộ (local value numbering) để phát hiện biểu thức con chung (common subexpression) có thể loại bỏ.

Với phép + và * (giao hoán), a op b và b op a tạo ra cùng một giá trị. Với - và /, thứ tự toán hạng có ý nghĩa (không hoán đổi). Toán hạng a, b có thể là tên biến hoặc hằng số nguyên.

Quy tắc đánh số:

• Mỗi hằng số nguyên, MỌI lần xuất hiện của cùng một giá trị luôn có cùng số hiệu giá trị (value number - VN).
• Mỗi tên biến, lần đầu được ĐỌC làm toán hạng mà trước đó chưa từng được gán trong khối, được cấp một VN mới đại diện cho giá trị "đầu vào" của nó.
• Với lệnh thứ $i$ (tính từ 1) t = a op b: lấy VN hiện tại của a, b (theo trạng thái ngay TRƯỚC lệnh $i$), tạo khóa (op, VN(a), VN(b)) (không phân biệt thứ tự nếu op giao hoán). Nếu khóa này đã xuất hiện ở lệnh $j < i$: lệnh $i$ là dư thừa, gán cho t VN giống hệt kết quả của lệnh $j$, in CSE j. Ngược lại: cấp VN hoàn toàn mới cho biểu thức, lưu khóa lại, gán cho t, in NEW.
• Việc gán t (dù NEW hay CSE) LUÔN cập nhật VN hiện tại của biến t cho các lệnh sau.

Sau khi in xong $n$ dòng kết quả, in thêm dòng cuối SAVED=k với k là tổng số lệnh được xác định là CSE (dư thừa, có thể loại bỏ).

Ví dụ

Input:

4
t1 = a + b
t2 = b + a
t3 = a - b
t4 = b - a

Output:

NEW
CSE 1
NEW
NEW
SAVED=1

(t2 = b + a trùng giá trị với t1 = a + b do + giao hoán; t3, t4 dùng - không giao hoán nên là hai giá trị khác nhau.)