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] Khử mã chết bằng phân tích sống ngược

    Khử mã chết (dead code elimination) là phép tối ưu loại bỏ các câu lệnh gán giá trị cho một biến mà giá trị đó không bao giờ được sử dụng về sau (trước khi biến bị ghi đè hoặc chương trình kết thúc).

    Cho một chương trình mã ba địa chỉ (TAC) tuyến tính gồm nnn lệnh, mỗi lệnh thuộc một trong ba dạng:

    • dst = src (gán/sao chép),
    • dst = src1 op src2 với op ∈{+,−,∗,/}\in \{+,-,*,/\}∈{+,−,∗,/},
    • PRINT var (in giá trị của biến var).

    Mỗi toán hạng src, src1, src2 là tên biến hoặc hằng số nguyên.

    Hãy xác định các lệnh sống (cần giữ lại) bằng phân tích ngược (từ lệnh cuối về lệnh đầu), duy trì tập hợp live các biến "còn cần dùng giá trị hiện tại" (ban đầu rỗng), xử lý lần lượt từng lệnh iii từ lệnh thứ nnn về lệnh thứ 111:

    • Nếu lệnh là PRINT var: đánh dấu lệnh này là sống; thêm var vào live.
    • Nếu lệnh là dst = ...:
      • Nếu dst ∈\in∈ live: đánh dấu lệnh là sống; loại dst khỏi live; sau đó thêm vào live tất cả toán hạng vế phải là tên biến (bỏ qua toán hạng là hằng số).
      • Ngược lại (dst ∉\notin∈/ live): lệnh này là mã chết, không giữ lại, và không thêm toán hạng vế phải của nó vào live.

    Chương trình kết quả là dãy con các lệnh được đánh dấu sống, giữ nguyên thứ tự tương đối ban đầu.

    Ví dụ: với 5 lệnh

    a = 1
b = 2
c = a + 1
d = b + 2
PRINT c

    biến b và d không bao giờ được in ra hay dùng ở đâu khác, nên b = 2 và d = b + 2 đều là mã chết (bị loại theo dây chuyền); kết quả còn lại 3 lệnh: a = 1, c = a + 1, PRINT c.

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

      Dòng đầu tiên chứa số nguyên nnn (0≤n≤2000 \le n \le 2000≤n≤200) — số lệnh.

      nnn dòng tiếp theo, mỗi dòng một lệnh dạng dst = src, dst = src1 op src2, hoặc PRINT var.

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

      Dòng đầu tiên in ra số nguyên mmm — số lệnh còn lại sau khi khử mã chết. mmm dòng tiếp theo là các lệnh được giữ lại, theo đúng thứ tự tương đối ban đầu, giữ nguyên cú pháp gốc.

    Ví dụ:

    Đầu vào:

    0

    Đầu ra:

    0

    Đầu vào:

    5
a = 1
b = 2
c = a + 1
d = b + 2
PRINT c

    Đầu ra:

    3
a = 1
c = a + 1
PRINT c

    Đang tải editor...