Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Tối ưu hoá gộp hằng số trên bytecode

    Một kỹ thuật tối ưu hoá phổ biến trong trình biên dịch là gộp hằng số (constant folding): nếu tại thời điểm biên dịch đã biết trước kết quả của một phép toán trên các hằng số, ta tính sẵn kết quả đó thay vì sinh mã tính toán lúc chạy.

    Cho một chương trình bytecode cho máy ảo ngăn xếp, gồm các lệnh PUSH x, ADD, SUB, MUL, DIV, DUP, POP, PRINT (không có HALT, không có nhãn/lệnh nhảy). Hãy thực hiện tối ưu hoá gộp hằng số theo đúng thuật toán sau (mô phỏng một bước peephole optimization):

    Lặp lại nhiều lượt: ở mỗi lượt, quét danh sách lệnh từ trái sang phải, tìm bộ ba lệnh liên tiếp đầu tiên có dạng PUSH a, PUSH b, rồi tới một trong ADD/SUB/MUL/DIV. Ngay khi tìm thấy, thay thế cả 3 lệnh đó bằng một lệnh duy nhất PUSH r, với r=ar = ar=a op bbb (riêng DIV làm tròn phần nguyên về 0, giống phép chia C/C++/Java). Sau khi thay thế, bắt đầu lại việc quét từ đầu danh sách lệnh (đã cập nhật). Quá trình dừng lại khi quét hết toàn bộ danh sách mà không tìm thấy bộ ba nào như vậy nữa.

    Lưu ý: các lệnh DUP, POP, PRINT không tham gia gộp và chặn việc gộp giữa hai lệnh PUSH không kề nhau trực tiếp (chỉ những bộ ba PUSH, PUSH, toán tử nằm liền kề nhau trong danh sách hiện tại mới được xét). Dữ liệu đảm bảo không có phép DIV nào trong quá trình gộp có b=0b = 0b=0.

    Cho danh sách lệnh ban đầu, hãy in ra danh sách lệnh sau khi tối ưu hoá xong (không còn bộ ba nào để gộp nữa).

    Ví dụ: chương trình PUSH 2 / PUSH 3 / ADD / PUSH 4 / MUL — trước tiên gộp PUSH 2, PUSH 3, ADD thành PUSH 5, được PUSH 5 / PUSH 4 / MUL; gộp tiếp thành PUSH 20. Kết quả cuối cùng chỉ còn một lệnh PUSH 20.

    • Định dạng đầu vào:

      Dòng đầu chứa số nguyên nnn (1≤n≤10001 \le n \le 10001≤n≤1000). nnn dòng tiếp theo là các lệnh PUSH x, ADD, SUB, MUL, DIV, DUP, POP, PRINT (đây chỉ là danh sách lệnh cần tối ưu hoá tĩnh, không cần và không được mô phỏng thực thi — nghĩa là các lệnh DUP/POP/PRINT không nhất thiết phải hợp lệ về mặt ngăn xếp khi thực thi thật, ta chỉ quan tâm việc gộp các bộ ba PUSH, PUSH, toán tử).

    • Định dạng đầu ra:

      Dòng đầu tiên in ra số nguyên mmm — số lượng lệnh sau khi tối ưu hoá. mmm dòng tiếp theo là các lệnh theo đúng thứ tự sau tối ưu hoá, giữ nguyên định dạng mnemonic ban đầu (PUSH x, ADD, SUB, MUL, DIV, DUP, POP, PRINT).

    Ví dụ:

    Đầu vào:

    5
PUSH 2
PUSH 3
ADD
PUSH 4
MUL

    Đầu ra:

    1
PUSH 20

    Đầu vào:

    8
PUSH 2
PUSH 3
ADD
PRINT
PUSH 4
PUSH 5
MUL
PRINT

    Đầu ra:

    4
PUSH 5
PRINT
PUSH 20
PRINT

    Đang tải editor...