Cho một khối cơ bản (basic block) gồm n lệnh TAC, mỗi lệnh có dạng tK = a op b, trong đó tất cả các tK ở vế trái là biến tạm phân biệt đôi một (mỗi biến tạm chỉ được gán đúng một lần trong toàn bộ khối — tính chất SSA cục bộ); a, b là tên biến/biến tạm hoặc hằng số nguyên; op ∈{+,−,∗,/}.
Hãy thực hiện loại bỏ biểu thức con chung cục bộ (local CSE): duy trì một bảng "biểu thức khả dụng" ánh xạ (toán tử, cặp toán hạng đã chuẩn hoá) → tên biến tạm đầu tiên đã tính biểu thức đó. Với + và * (giao hoán), coi cặp toán hạng (a,b) và (b,a) là tương đương (chuẩn hoá bằng cách sắp xếp 2 toán hạng theo thứ tự từ điển của chuỗi biểu diễn của chúng trước khi tra bảng). Với - và / (không giao hoán) giữ nguyên thứ tự.
Xử lý tuần tự từng lệnh t = a op b: tính khoá chuẩn hoá của biểu thức; nếu khoá đã có trong bảng (ứng với biến tạm t' đã tính trước đó), thay lệnh hiện tại bằng lệnh sao chép t = t' (không tính lại, không thêm khoá mới vào bảng); nếu chưa có, giữ nguyên lệnh và thêm khoá này vào bảng, ánh xạ tới t.
In ra n dòng kết quả sau khi loại bỏ (theo đúng thứ tự ban đầu), sau đó in dòng cho biết tổng số lệnh đã được thay thế bằng lệnh sao chép.
Dòng 1: số nguyên n.
n dòng tiếp theo: các lệnh TAC dạng tK = a op b, đúng định dạng mô tả ở trên.
In n dòng lệnh sau khi áp dụng CSE (theo đúng thứ tự ban đầu), sau đó in dòng SO_LOAI_BO = <so lenh da duoc thay the boi lenh sao chep>.
Ví dụ:
Đầu vào:
5
t1 = a + b
t2 = b + a
t3 = t1 * c
t4 = a - b
t5 = b - a
Đầu ra:
t1 = a + b
t2 = t1
t3 = t1 * c
t4 = a - b
t5 = b - a
SO_LOAI_BO = 1
Đầu vào:
1
t1 = x + y
Đầu ra:
t1 = x + y
SO_LOAI_BO = 0
Đang tải editor...