solution

Tối ưu hoá cửa sổ trượt (peephole optimization) là một kỹ thuật tối ưu mã máy/bytecode: quét qua chương trình bằng một "cửa sổ" nhỏ vài lệnh liên tiếp, và thay thế các mẫu (pattern) đã biết bằng đoạn mã ngắn gọn/hiệu quả hơn, lặp lại cho tới khi không còn mẫu nào để thay (đạt điểm bất động, fixed point).

Cho chương trình bytecode ngăn xếp gồm các lệnh PUSH x (x nguyên), ADD, SUB, MUL (phép toán hai ngôi), NEG (đảo dấu phần tử đỉnh ngăn xếp), DUP (nhân đôi đỉnh ngăn xếp) và NOP (không làm gì). Dữ liệu vào đảm bảo mỗi lệnh DUP luôn đứng ngay sau một lệnh PUSH. Hãy áp dụng tuần tự các bước tối ưu sau:

Bước 1 — Loại bỏ NOP: xoá mọi lệnh NOP khỏi chương trình.

Bước 2 — Khai triển DUP: lặp lại việc quét chương trình từ trái sang phải; mỗi khi gặp mẫu PUSH a, DUP (ở vị trí sớm nhất tìm thấy khi quét lại từ đầu sau mỗi lần thay), thay bằng PUSH a, PUSH a (2 lệnh PUSH giống hệt nhau), rồi tiếp tục quét lại từ đầu; lặp cho tới khi một lượt quét không còn thay đổi nào (không còn DUP nào theo sau một PUSH).

Bước 3 — Gộp hằng số (constant folding) tới điểm bất động: lặp lại: quét chương trình hiện tại từ trái sang phải một lượt; tại mỗi vị trí, nếu khớp mẫu PUSH a, NEG thì thay ngay bằng PUSH (-a) và tiếp tục quét từ vị trí ngay sau chỗ vừa thay (không quay lại đầu); nếu khớp mẫu PUSH a, PUSH b, OP với OP $\in \{$ADD, SUB, MUL$\}$ thì thay ngay bằng PUSH v với $v = a + b$, $a - b$ hoặc $a \times b$ tương ứng, và tiếp tục quét từ vị trí ngay sau; nếu không khớp mẫu nào tại vị trí hiện tại, giữ nguyên lệnh và quét tiếp lệnh kế. Lặp lại toàn bộ lượt quét như vậy cho tới khi một lượt hoàn chỉnh không thực hiện thay thế nào.

In ra chương trình bytecode kết quả sau khi hoàn tất cả 3 bước.

Ví dụ: chương trình PUSH 4, DUP, ADD → sau bước 2 thành PUSH 4, PUSH 4, ADD → sau bước 3 gộp thành PUSH 8.