Phân tích bí danh (alias analysis) kiểu may-point-to xác định, tại mỗi điểm trong chương trình, tập các ô nhớ mà một con trỏ có thể trỏ tới — thông tin then chốt để trình biên dịch quyết định các tối ưu hóa an toàn (ví dụ CSE, loại bỏ tải/lưu dư thừa).
Cho một CFG gồm n khối đánh số 1..n (khối 1 là điểm vào), mỗi khối chứa một dãy lệnh con trỏ theo thứ tự, mỗi lệnh có một trong hai dạng:
p = &x — con trỏ p được gán trỏ tới ô nhớ x (tập trỏ-tới của p trở thành {x}, ghi đè hoàn toàn tập cũ);p = q — con trỏ p được sao chép từ con trỏ q (tập trỏ-tới của p trở thành đúng tập trỏ-tới hiện tại của q, ghi đè tập cũ của p).Tập trỏ-tới của một con trỏ tại điểm vào của khối b là hợp (union) các tập trỏ-tới của nó tại điểm ra của tất cả khối cha (predecessor) của b (nếu b là khối 1, mọi con trỏ có tập trỏ-tới rỗng tại điểm vào — không phụ thuộc khối cha). Các lệnh trong khối được xử lý tuần tự để tính tập trỏ-tới tại điểm ra. Vì đồ thị có thể có vòng lặp, cần lặp lại việc tính toán trên toàn bộ CFG cho đến khi tập trỏ-tới của mọi khối không còn thay đổi (điểm bất động).
Cho một truy vấn gồm chỉ số khối Q và tên con trỏ p, hãy in ra tập trỏ-tới của p tại điểm ra của khối Q sau khi đạt điểm bất động.
Ví dụ: CFG hình thoi 1→2, 1→3, 2→4, 3→4; khối 2 có lệnh p = &x, khối 3 có lệnh p = &y, khối 4 có lệnh q = p. Tại điểm vào khối 4, tập trỏ-tới của p là hợp của {x} (từ khối 2) và {y} (từ khối 3), tức {x,y}; do đó sau lệnh q = p, tập trỏ-tới của q tại điểm ra khối 4 là {x,y}.
p = &x hoặc p = q (tên con trỏ/ô nhớ là chuỗi chữ cái thường, các token cách nhau đúng một khoảng trắng).In ra một dòng: danh sách các ô nhớ trong tập trỏ-tới của p tại điểm ra của khối Q, sắp xếp theo thứ tự từ điển, cách nhau bởi dấu phẩy (không có khoảng trắng). Nếu tập rỗng (hoặc p chưa từng được gán), in ký tự -.
Ví dụ:
Đầu vào:
4
1
p = &x
0
1
p = &y
0
4
1 2
2 3
3 2
2 4
2 p
Đầu ra:
x,y
Đầu vào:
4
1
p = &x
1
p = &y
0
1
q = p
4
1 2
1 3
2 4
3 4
4 q
Đầu ra:
x,y
Đang tải editor...