solution

Tối ưu hoá peephole (peephole optimization) là kỹ thuật tối ưu bytecode bằng cách xét một cửa sổ nhỏ các lệnh liên tiếp và thay thế bằng một dãy lệnh tương đương ngắn/nhanh hơn. Cho một chương trình thẳng (không nhãn, không rẽ nhánh) gồm các lệnh PUSH x, ADD, SUB, MUL, DUP, POP (lưu ý: chương trình chỉ mang tính cú pháp để luyện viết lại, không cần đảm bảo có thể thực thi hợp lệ mà không tràn dưới ngăn xếp — bạn chỉ cần áp dụng máy móc các luật viết lại dưới đây trên dãy lệnh).

Áp dụng lặp đi lặp lại các luật viết lại sau, cho đến khi không còn luật nào áp dụng được (điểm bất động):

1. PUSH a, PUSH b, ADD $\to$ PUSH (a+b)
2. PUSH a, PUSH b, SUB $\to$ PUSH (a-b)
3. PUSH a, PUSH b, MUL $\to$ PUSH (a*b)
4. PUSH a, POP $\to$ (xoá cả hai lệnh)
5. PUSH a, DUP $\to$ PUSH a, PUSH a

Thuật toán xác định (bắt buộc tuân theo để đảm bảo kết quả duy nhất): lặp lại nhiều vòng; ở mỗi vòng, quét từ trái sang phải để tìm vị trí $i$ nhỏ nhất mà tại đó có một luật khớp (luật 1–3 xét cửa sổ 3 lệnh, luật 4–5 xét cửa sổ 2 lệnh; tại một vị trí không thể có hai luật cùng khớp), áp dụng luật đó, rồi bắt đầu lại việc quét từ đầu danh sách đã cập nhật. Dừng khi một vòng quét đầy đủ không tìm thấy vị trí nào khớp.

Ví dụ: PUSH 3; DUP; ADD $\to$ (luật 5 tại vị trí 0) PUSH 3; PUSH 3; ADD $\to$ (luật 1 tại vị trí 0) PUSH 6.