solution

Cho một đoạn mã ba địa chỉ (TAC) tuyến tính (không nhãn, không rẽ nhánh) gồm $n$ lệnh liên tiếp, lệnh thứ $i$ luôn có đích là $t_i$ ($i=1,\ldots,n$). Mỗi lệnh có dạng tK = A op B (op $\in \{+,-,*,/\}$) hoặc dạng sao chép tK = A, trong đó A, B là biến gốc, hằng số, hoặc một tJ ($J<K$).

Hãy tối ưu đoạn mã bằng kỹ thuật đánh số giá trị cục bộ (local value numbering) để loại bỏ các phép tính trùng lặp, theo đúng quy tắc sau. Gọi $canon(x)$ là "giá trị canonical hiện tại" của $x$: với biến gốc/hằng số chưa từng được định nghĩa, $canon(x)=x$; với $t_i$ đã xử lý, $canon(t_i)$ được xác định như dưới đây. Xử lý các lệnh theo thứ tự $i=1,\ldots,n$:

• Lệnh sao chép tK = A: đặt $canon(t_K) = canon(A)$; dòng xuất ra là tK = canon(A).
• Lệnh tính toán tK = A op B: gọi $a=canon(A)$, $b=canon(B)$. Nếu op là + hoặc * (giao hoán), khóa biểu thức là (op, $a$, $b$ đã sắp xếp theo thứ tự từ điển); nếu op là - hoặc / (không giao hoán), khóa là (op, $a$, $b$) giữ nguyên thứ tự.
  • Nếu khóa này trùng với khóa của một lệnh tP ($P<K$) đã xử lý trước đó: đặt $canon(t_K)=canon(t_P)$, dòng xuất ra thay bằng tK = canon(t_P), và tính là 1 lệnh bị loại bỏ.
  • Nếu khóa mới: đặt $canon(t_K)=t_K$, ghi nhớ khóa này ứng với $t_K$, dòng xuất ra là tK = a op b.

Lưu ý $canon(t_P)$ luôn chính bằng $t_P$ (vì lần đầu một khóa mới xuất hiện, $canon$ của đích được đặt bằng chính tên đích đó).