solution

Khử biểu thức con chung (Common Subexpression Elimination - CSE) là tối ưu hoá thay các phép tính lặp lại của cùng một biểu thức bằng một phép sao chép giá trị đã tính trước đó, giúp giảm số phép toán thực sự phải thực hiện.

Cho $n$ lệnh ba địa chỉ tuyến tính, mỗi lệnh có đúng dạng t = a op b với op $\in \{+, -, *\}$, a, b mỗi cái là một hằng số nguyên hoặc tên biến/biến tạm (chuỗi chữ cái thường). Đề bảo đảm chuỗi lệnh ở dạng gán đơn tĩnh (SSA): mỗi tên ở vế trái t chỉ xuất hiện đúng một lần duy nhất trong toàn bộ $n$ lệnh (do đó không biến nào bị ghi đè, việc một biểu thức từng tính được luôn giữ nguyên giá trị available cho đến hết khối).

Chi phí thực hiện trước khi tối ưu bằng $n$ (mỗi lệnh tốn đúng 1 phép toán).

Sau khi tối ưu bằng CSE: xét từng lệnh theo thứ tự xuất hiện; lệnh thứ $i$ với vế phải $(op, a, b)$ được coi là trùng lặp (và được thay bằng một phép sao chép, không tốn phép toán) nếu đã tồn tại một lệnh đứng trước có đúng cùng toán tử và đúng cùng thứ tự hai toán hạng $(op, a, b)$ (chú ý: không áp dụng luật giao hoán, tức a + b và b + a được coi là hai biểu thức khác nhau). Chi phí sau khi tối ưu bằng số lệnh không trùng lặp (mỗi biểu thức $(op,a,b)$ phân biệt chỉ tính phí 1 lần cho lần xuất hiện đầu tiên).

Ví dụ: 3 lệnh t1 = a + b, t2 = a + b, t3 = a - b có chi phí trước $=3$; lệnh t2 trùng với t1 nên chi phí sau $=2$.