solution

Cấp phát thanh ghi (register allocation) bằng tô màu đồ thị giao (interference graph coloring) là kỹ thuật tối ưu cốt lõi ở giai đoạn sinh mã: các biến tạm (temporary) xung đột (cùng "sống" tại một thời điểm) không được cấp cùng một thanh ghi. Bài này yêu cầu cài đặt thuật toán simplify/select đơn giản hoá của Chaitin.

Cho đồ thị giao gồm $n$ biến tạm (đánh số $0, \ldots, n-1$), $m$ cạnh xung đột, và $k$ thanh ghi khả dụng (đánh số $0, \ldots, k-1$). Thực hiện hai giai đoạn sau:

Giai đoạn 1 — Đơn giản hoá (simplify), lặp cho tới khi đồ thị (phần còn lại) rỗng:

• Xét các đỉnh còn lại trong đồ thị và bậc (số cạnh nối tới các đỉnh còn lại) của chúng.
• Nếu tồn tại (các) đỉnh còn lại có bậc nhỏ hơn $k$: chọn đỉnh có chỉ số nhỏ nhất trong số đó, loại khỏi đồ thị (cùng các cạnh liên quan) và đẩy vào một ngăn xếp $S$.
• Nếu không còn đỉnh nào có bậc nhỏ hơn $k$ (mọi đỉnh còn lại đều có bậc $\ge k$): chọn đỉnh có bậc lớn nhất; nếu có nhiều đỉnh cùng đạt bậc lớn nhất, chọn đỉnh có chỉ số nhỏ nhất trong số đó (đây là ứng viên tràn thanh ghi — potential spill); loại khỏi đồ thị và đẩy vào $S$.

Giai đoạn 2 — Tô màu (select): rút các đỉnh ra khỏi $S$ theo thứ tự ngược lại với thứ tự đã đẩy vào (đỉnh đẩy vào sau cùng được tô màu đầu tiên). Với mỗi đỉnh $v$ được rút ra, xét tập màu đã dùng bởi các đỉnh kề với $v$ trong đồ thị gốc mà đã được tô màu (tính đến thời điểm này); gán cho $v$ màu nhỏ nhất trong $\{0, \ldots, k-1\}$ chưa bị các đỉnh kề đã tô dùng. Nếu cả $k$ màu đều đã bị dùng bởi các đỉnh kề đã tô, đỉnh $v$ bị tràn thanh ghi (SPILL) — không có thanh ghi nào được gán.

Ví dụ: đồ thị tam giác (3 đỉnh, 3 cạnh đôi một xung đột) với $k=2$: không đủ 2 thanh ghi để tô 3 đỉnh xung đột đôi một, nên đúng một đỉnh sẽ bị SPILL, hai đỉnh còn lại nhận hai thanh ghi khác nhau.