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] Xóa mã chết khi có lệnh sinh hiệu ứng phụ

    Một khối lệnh cơ bản (basic block) gồm nnn câu lệnh thực thi tuần tự, mỗi câu lệnh có một trong hai dạng:

    • x = y op z (op ∈{+,−,∗,/}\in \{+,-,*,/\}∈{+,−,∗,/}): gán giá trị cho biến xxx, KHÔNG có hiệu ứng phụ nào khác.
    • PRINT y: in giá trị của biến yyy ra màn hình khi thực thi — đây là lệnh có hiệu ứng phụ (side effect), do đó không bao giờ được coi là mã chết, dù giá trị của nó có được dùng lại về sau hay không.

    Cho tập LLL các biến "sống ở đầu ra" (live-out) của khối, tức là các biến còn được cần dùng ở phần code phía sau khối này (không thuộc khối đang xét). Áp dụng phân tích biến sống lùi (backward liveness) chuẩn trên khối: bắt đầu với tập biến sống live=Llive = Llive=L, quét các câu lệnh theo thứ tự NGƯỢC (từ cuối lên đầu):

    • Nếu là PRINT y: luôn giữ lại (SỐNG); thêm yyy vào livelivelive.
    • Nếu là x = y op z: nếu x∈livex \in livex∈live, câu lệnh này SỐNG — loại xxx khỏi livelivelive (vì đây là nơi định nghĩa nó), rồi thêm các toán hạng là biến (trong y,zy, zy,z) vào livelivelive. Nếu x∉livex \notin livex∈/live, câu lệnh này CHẾT (bị loại bỏ) và livelivelive giữ nguyên (các toán hạng của một lệnh chết không được thêm vào, vì lệnh không bao giờ thực sự cần thực thi) — điều này khiến việc xóa mã chết có thể lan truyền dây chuyền.

    Hãy đếm số lệnh CHẾT bị loại bỏ, và liệt kê chỉ số (1-indexed, theo thứ tự gốc trong khối) của các lệnh còn SỐNG.

    Ví dụ: n=3n=3n=3, live-out ={y}=\{y\}={y}:

    x = a + b
y = a * b
w = x + 1

    Quét ngược: w = x + 1 có w∉{y}w \notin \{y\}w∈/{y} ⇒\Rightarrow⇒ CHẾT (không thêm xxx vào live); y = a * b có y∈{y}y \in \{y\}y∈{y} ⇒\Rightarrow⇒ SỐNG, live trở thành {a,b}\{a,b\}{a,b}; x = a + b có x∉{a,b}x \notin \{a,b\}x∈/{a,b} ⇒\Rightarrow⇒ CHẾT (dây chuyền, vì kết quả của nó chỉ được dùng bởi lệnh đã bị xóa). Kết quả: 2 lệnh chết, chỉ còn lệnh số 2 sống.

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

      Dòng 1: hai số nguyên nnn và mmm (0≤n≤10000 \le n \le 10000≤n≤1000, 0≤m≤500 \le m \le 500≤m≤50) — số câu lệnh và số biến live-out. Dòng 2: mmm tên biến live-out cách nhau khoảng trắng (nếu m=0m=0m=0, đây là một dòng trống). nnn dòng tiếp theo, mỗi dòng là một câu lệnh dạng x = y op z hoặc PRINT y (đúng như mô tả).

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

      Dòng 1: một số nguyên — số lệnh chết bị loại bỏ. Dòng 2: danh sách chỉ số (1-indexed) của các lệnh còn sống, cách nhau bởi một khoảng trắng, theo thứ tự tăng dần (nếu không có lệnh nào sống, in ra một dòng trống).

    Ví dụ:

    Đầu vào:

    3 1
y
x = a + b
y = a * b
w = x + 1

    Đầu ra:

    2
2

    Đầu vào:

    4 1
z
x = a + b
y = a * b
z = x + 1
PRINT y

    Đầu ra:

    0
1 2 3 4

    Đang tải editor...