Thiết kế trình biên dịch
Chaitin-Briggs Register Allocation
ID: #422
Xem trên trang chủ
Thời gian (Time)
O(V^2)
Không gian (Space)
O(V + E)
Mô tả nguyên lý
Phân bổ thanh ghi phần cứng cho biến chương trình dựa trên bài toán tô màu đồ thị sống (Liveness Analysis).
Cài đặt mẫu (Implementation)
// Xây dựng đồ thị giao thoa (interference graph) và làm tràn thanh ghi (spill) khi đồ thị không tô màu được.
Thiết kế trình biên dịch
Dominance Frontier Calculation
ID: #424
Xem trên trang chủ
Thời gian (Time)
O(V * (V + E))
Không gian (Space)
O(V^2)
Mô tả nguyên lý
Tính toán biên thống trị trong đồ thị luồng điều khiển để đặt hàm Phi trong dạng SSA.
Cài đặt mẫu (Implementation)
// Xác định tập hợp các nút mà một nút thống trị nhưng không thống trị nghiêm ngặt các hậu duệ của nó.
Thiết kế trình biên dịch
Static Single Assignment (SSA) Construction
ID: #423
Xem trên trang chủ
Thời gian (Time)
O(N log N)
Không gian (Space)
O(N)
Mô tả nguyên lý
Biến đổi mã nguồn trung gian sao cho mỗi biến chỉ được gán giá trị đúng một lần.
Cài đặt mẫu (Implementation)
// Chèn các hàm Phi (Phi-nodes) tại điểm hợp lưu của đồ thị luồng điều khiển (CFG).