solution

Khử biểu thức con chung (Common Subexpression Elimination — CSE) là phép tối ưu tránh tính lại một biểu thức đã được tính trước đó với cùng toán hạng, nếu các toán hạng đó chưa hề thay đổi giá trị kể từ lần tính trước.

Cho chương trình mã ba địa chỉ (TAC) tuyến tính gồm $n$ lệnh, mỗi lệnh có dạng dst = o1 op o2 với op $\in \{+,-,*,/\}$; o1, o2 là tên biến hoặc hằng số nguyên (chỉ xét dạng phép toán hai ngôi, không có lệnh gán đơn thuần).

Duy trì một bảng biểu thức khả dụng avail: ánh xạ từ "khoá biểu thức" sang tên biến hiện đang lưu giá trị của biểu thức đó. Khoá của lệnh dst = o1 op o2 được xác định như sau: nếu op là + hoặc * (giao hoán), khoá là (op, o1, o2) với o1, o2 đã sắp xếp theo thứ tự từ điển (để a+b và b+a cho cùng một khoá); nếu op là - hoặc / (không giao hoán), khoá là (op, o1, o2) giữ nguyên thứ tự.

Xử lý tuần tự từng lệnh dst = o1 op o2:

1. Tính khoá key của lệnh.
2. Nếu key đã có trong avail (ứng với biến T nào đó đã tính sẵn giá trị này): thay lệnh này bằng lệnh sao chép dst = T (không tính lại), và tăng biến đếm số lệnh bị loại bỏ lên 1.
3. Nếu key chưa có trong avail: giữ nguyên lệnh gốc.
4. Sau đó (dù ở nhánh 2 hay 3), vì dst vừa được gán giá trị mới, hãy loại khỏi avail mọi mục mà (a) tên biến đang lưu (giá trị ánh xạ) chính là dst, hoặc (b) một trong hai toán hạng của khoá đó chính là dst (các biểu thức này đã "cũ" — không còn phản ánh đúng giá trị hiện tại của dst).
5. Cuối cùng, nếu ở nhánh 3 (không phải bản sao chép), thêm mục mới avail[key] = dst.

Ví dụ: với 3 lệnh t1 = a + b, t2 = a + b, t3 = t1 + t2: lệnh thứ hai trùng biểu thức với lệnh thứ nhất nên được thay bằng t2 = t1 (1 lệnh bị loại); lệnh thứ ba giữ nguyên. Kết quả in ra:

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