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ử biểu thức con chung bằng đánh số giá trị cục bộ

    Cho mmm câu lệnh mã ba địa chỉ dạng SSA (mỗi biến tạm chỉ được gán đúng một lần), mỗi câu lệnh có dạng:

    tI = A OP B

    với OP∈{+,−,∗,/}OP \in \{+, -, *, /\}OP∈{+,−,∗,/}, trong đó mỗi toán hạng AAA, BBB hoặc là một hằng số nguyên, hoặc là một biến (có thể là biến nguồn như a, b, ... hoặc một biến tạm tjt_jtj​ đã được định nghĩa trước đó, j<Ij < Ij<I).

    Áp dụng kỹ thuật đánh số giá trị cục bộ (local value numbering - LVN) để phát hiện các biểu thức con chung: gán cho mỗi giá trị khác nhau xuất hiện trong chương trình (mỗi hằng số, mỗi biến nguồn lần đầu xuất hiện, hoặc mỗi kết quả phép toán) một số hiệu giá trị (value number - VN) duy nhất - hai toán hạng có cùng VN được xem là luôn có cùng giá trị tại thời điểm đó. Với hai toán tử giao hoán (+,∗+, *+,∗), biểu thức A OP BA\ OP\ BA OP B và B OP AB\ OP\ AB OP A được coi là cùng một biểu thức nếu cặp VN của toán hạng giống nhau (không phân biệt thứ tự); với −,/-, /−,/ (không giao hoán) thì thứ tự toán hạng có phân biệt.

    Một câu lệnh tI=A OP Bt_I = A\ OP\ BtI​=A OP B được xem là dư thừa (redundant) nếu đã tồn tại một câu lệnh trước đó tính ra cùng giá trị (cùng OPOPOP, cùng cặp VN toán hạng theo quy tắc trên) - khi đó lệnh này lẽ ra có thể thay bằng phép gán từ kết quả đã tính trước đó thay vì tính lại. Hãy đếm số câu lệnh dư thừa trong toàn bộ chương trình.

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

      Dòng 1: số nguyên mmm. mmm dòng tiếp theo: mỗi câu lệnh tI = A OP B (token cách nhau đúng 1 khoảng trắng; tI là t nối số thứ tự lệnh iii).

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

      In ra duy nhất một số nguyên - số câu lệnh dư thừa (redundant).

      Ví dụ input:

      4
t1 = a + b
t2 = b + a
t3 = a * b
t4 = t1 + t3

      Output: 1 (t2 tính lại đúng giá trị đã có ở t1 do phép + giao hoán; t3, t4 là các giá trị mới).

    Ví dụ:

    Đầu vào:

    3
t1 = a + b
t2 = a - b
t3 = a * b

    Đầu ra:

    0

    Đầu vào:

    4
t1 = a + b
t2 = b + a
t3 = a * b
t4 = t1 + t3

    Đầu ra:

    1

    Đang tải editor...