Thiết kế trình biên dịch

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 3)

Thiết kế trình biên dịch

Chaitin-Briggs Register Allocation

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

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

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).