Bài tập | NEU OJ

Trong tối ưu hóa mã máy, một phép lưu (store) vào ô nhớ được gọi là lưu chết (dead store) nếu giá trị vừa ghi bị một phép lưu khác ghi đè lên cùng địa chỉ trước khi có bất kỳ phép đọc (load) nào từ địa chỉ đó — tức giá trị vừa ghi không bao giờ được dùng tới.

Cho một dãy $n$ lệnh truy cập bộ nhớ tuyến tính (không có nhánh, không có vòng lặp) trên các ô nhớ được đánh địa chỉ bằng số nguyên, mỗi lệnh có một trong hai dạng:

STORE a v — ghi giá trị $v$ vào địa chỉ $a$ ;
LOAD a — đọc giá trị hiện có tại địa chỉ $a$ (không làm thay đổi bộ nhớ).

Một lệnh STORE a v ở dòng $i$ được gọi là chết nếu, xét các lệnh từ dòng $i+1$ đến dòng $n$ theo thứ tự, ta gặp một lệnh STORE khác cùng địa chỉ $a$ trước khi gặp bất kỳ lệnh LOAD a nào (nếu không có STORE/LOAD nào cùng địa chỉ $a$ xuất hiện phía sau, hoặc LOAD a xuất hiện trước STORE cùng địa chỉ tiếp theo, thì lệnh đó không chết).

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

STORE 1 5
STORE 1 7
LOAD 1
STORE 1 9

Lệnh 1 (STORE 1 5) là chết vì bị lệnh 2 ghi đè cùng địa chỉ 1 trước khi có LOAD 1. Lệnh 2 không chết vì LOAD 1 ở dòng 3 đọc đúng giá trị nó ghi, trước khi bị ghi đè ở dòng 4. Lệnh 4 không chết vì không còn lệnh nào phía sau. Vậy đáp số là: có 1 lệnh chết, đó là lệnh số 1.

Định dạng đầu vào:
- Dòng đầu tiên: số nguyên $n$ ( $0 \le n \le 1000$ ) — số lệnh.
- $n$ dòng tiếp theo, mỗi dòng là một lệnh có dạng STORE a v hoặc LOAD a, trong đó $a$ ( $0 \le a \le 10^5$ ) là địa chỉ và $v$ ( $-10^9 \le v \le 10^9$ ) là giá trị ghi (số nguyên).
Định dạng đầu ra:
In ra một dòng duy nhất: số lượng lệnh STORE chết, tiếp theo (nếu có) là chỉ số (1-indexed) của các lệnh đó theo thứ tự tăng dần, các số cách nhau bởi đúng một khoảng trắng. Nếu không có lệnh chết nào thì chỉ in số 0.

solution

Đề bài: [Trình biên dịch] Loại bỏ phép lưu chết (Dead Store Elimination)