Trong một khối lệnh cơ bản (basic block), mỗi biến tạm chỉ được định nghĩa (gán) đúng một lần — đây là giả thiết chuẩn khi sinh mã ba địa chỉ dạng cây biểu thức. Kỹ thuật loại bỏ biểu thức con chung cục bộ (local CSE) phát hiện các lệnh tính ra cùng một giá trị và thay thế bằng cách dùng lại kết quả đã tính trước đó, dựa trên đánh số giá trị (value numbering).
Cho n lệnh TAC theo đúng thứ tự, mỗi lệnh có dạng X = A OP B với OP∈{+,−,∗,/}; X là tên biến tạm (được định nghĩa đúng một lần trong toàn bộ khối); A, B là tên biến/biến tạm hoặc hằng số nguyên. Hãy xử lý tuần tự và với mỗi lệnh:
A, B bằng biến tạm gốc mà chúng thực sự đại diện (nếu A hoặc B từng bị loại bỏ ở bước trước, dùng tên biến tạm đã được giữ lại thay cho nó).X được coi là bí danh (alias) của biến tạm đã giữ lại đó, và lệnh này bị loại bỏ.Ví dụ: 4 lệnh t1 = a + b, t2 = a + b, t3 = t2 * c, t4 = t1 * c → t2 bị loại vì trùng t1; sau khi thay thế, t4 = t1 * c trùng với t3 = t2 * c (vì t2 chính là t1) nên cũng bị loại. Kết quả: 2 lệnh bị loại bỏ, 2 lệnh được giữ lại.
Dòng 1: số nguyên n (1≤n≤500).
n dòng tiếp theo: mỗi dòng một lệnh dạng X = A OP B (các token cách nhau đúng một khoảng trắng, OP là đúng một trong bốn ký tự + - * /).
In ra hai số nguyên trên một dòng, cách nhau một khoảng trắng: số lệnh bị loại bỏ, và số lệnh được giữ lại (tổng hai số này luôn bằng n).
Ví dụ:
Đầu vào:
2
t1 = a + b
t2 = a - b
Đầu ra:
0 2
Đầu vào:
4
t1 = a + b
t2 = a + b
t3 = t2 * c
t4 = t1 * c
Đầu ra:
2 2
Đang tải editor...