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 toàn cục bằng phân tích biến sống trên CFG

    Cho một đồ thị luồng điều khiển (CFG) gồm nnn khối cơ bản và mmm cạnh có hướng — CFG có thể chứa chu trình (vòng lặp). Mỗi khối gồm một dãy lệnh tuần tự, mỗi lệnh có một trong hai dạng x = y op z (op ∈{+,−,∗,/}\in \{+,-,*,/\}∈{+,−,∗,/}, không hiệu ứng phụ) hoặc PRINT y (LUÔN được giữ lại vì có hiệu ứng phụ, không bao giờ là mã chết). Khối nào không có cạnh ra (out-degree 0) được coi là khối thoát (exit) của chương trình, có LiveOut=∅LiveOut = \emptysetLiveOut=∅ (không biến nào cần dùng sau khi chương trình kết thúc).

    Áp dụng thuật toán phân tích biến sống (live variable analysis) chuẩn, lặp tới điểm cố định (cần thiết vì CFG có thể có chu trình):

    LiveOut[b]=⋃s laˋ khoˆˊi keˆˊ tieˆˊp của bLiveIn[s](hoặc ∅ neˆˊu b khoˆng coˊ khoˆˊi keˆˊ tieˆˊp)LiveOut[b] = \bigcup_{s \text{ là khối kế tiếp của } b} LiveIn[s] \quad (\text{hoặc } \emptyset \text{ nếu } b \text{ không có khối kế tiếp})LiveOut[b]=⋃s laˋ khoˆˊi keˆˊ tieˆˊp của b​LiveIn[s](hoặc ∅ neˆˊu b khoˆng coˊ khoˆˊi keˆˊ tieˆˊp)

    LiveIn[b]LiveIn[b]LiveIn[b] được tính bằng cách quét NGƯỢC các câu lệnh trong khối bbb, xuất phát từ live=LiveOut[b]live = LiveOut[b]live=LiveOut[b]: gặp PRINT y thì giữ và thêm yyy vào livelivelive; gặp x = y op z thì nếu x∈livex \in livex∈live giữ lại lệnh (SỐNG), cập nhật live←(live∖{x})∪{caˊc toaˊn hạng laˋ bieˆˊn trong y,z}live \leftarrow (live \setminus \{x\}) \cup \{\text{các toán hạng là biến trong } y, z\}live←(live∖{x})∪{caˊc toaˊn hạng laˋ bieˆˊn trong y,z}; nếu x∉livex \notin livex∈/live, lệnh CHẾT và livelivelive giữ nguyên.

    Tại điểm cố định (khi LiveInLiveInLiveIn, LiveOutLiveOutLiveOut mọi khối không đổi qua một vòng lặp toàn bộ các khối), hãy đếm TỔNG số câu lệnh x = y op z trên TOÀN BỘ CFG được xác định là CHẾT (không tính các lệnh PRINT).

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

      Dòng 1: hai số nguyên nnn, mmm (1≤n≤1001 \le n \le 1001≤n≤100, 0≤m≤3000 \le m \le 3000≤m≤300). mmm dòng tiếp theo, mỗi dòng "ppp qqq" là cạnh có hướng p→qp \to qp→q. Sau đó lần lượt nnn khối, khối thứ iii gồm: một dòng số nguyên kik_iki​ (số câu lệnh trong khối, có thể 0), rồi kik_iki​ dòng câu lệnh dạng x = y op z hoặc PRINT y.

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

      In ra đúng một số nguyên duy nhất — tổng số câu lệnh gán bị xác định là mã chết trên toàn CFG.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    3

    Đầu vào:

    4 4
1 2
2 3
3 2
2 4
3
a = 1 + 0
b = 2 + 0
d = 5 + 5
0
2
c = a + b
a = c + 1
1
PRINT a

    Đầu ra:

    1

    Đang tải editor...