Thanh ghi là vị trí nhanh nhất trong hệ thống phân cấp bộ nhớ. Tuy nhiên, tài nguyên này có hạn và là một trong những tài nguyên bị ràng buộc nhiều nhất của bộ xử lý đích. Việc phân bổ thanh ghi là một bài toán NP-đầy đủ. Tuy nhiên, bài toán này có thể được quy về bài toán tô màu đồ thị để đạt được việc phân bổ và gán. Do đó, một bộ phân bổ thanh ghi tốt sẽ tính toán một giải pháp xấp xỉ hiệu quả cho bài toán khó này.
Bộ phân bổ thanh ghi xác định giá trị nào sẽ nằm trong thanh ghi và thanh ghi nào sẽ giữ mỗi giá trị đó. Nó nhận đầu vào là một chương trình với số lượng thanh ghi tùy ý và tạo ra một chương trình với tập hợp thanh ghi hữu hạn có thể phù hợp với máy đích.
Phân bổ (Allocation) vs Gán (Assignment):
Phân bổ: Ánh xạ một không gian tên không giới hạn vào tập hợp thanh ghi của máy đích.
- Mô hình Thanh ghi đến Thanh ghi (Reg. to Reg. Model): Ánh xạ các thanh ghi ảo đến các thanh ghi vật lý nhưng tràn số lượng dư thừa vào bộ nhớ.
- Mô hình Bộ nhớ đến Bộ nhớ (Mem. to Mem. Model): Ánh xạ một tập hợp con của vị trí bộ nhớ đến một tập hợp các tên mô phỏng tập hợp thanh ghi vật lý.
Phân bổ đảm bảo rằng mã sẽ phù hợp với tập hợp thanh ghi của máy đích tại mỗi lệnh.
Gán: Ánh xạ một tập hợp tên đã được phân bổ vào tập hợp thanh ghi vật lý của máy đích.
- Giả định rằng việc phân bổ đã được thực hiện để mã sẽ phù hợp với tập hợp các thanh ghi vật lý.
- Không quá ‘k’ giá trị được chỉ định vào các thanh ghi, trong đó ‘k’ là số lượng thanh ghi vật lý.
Phân bổ thanh ghi tổng quát là một bài toán NP-đầy đủ:
- Được giải quyết trong thời gian đa thức, khi (số lượng thanh ghi cần thiết) < (số lượng thanh ghi vật lý khả dụng).
- Một phép gán có thể được tạo ra trong thời gian tuyến tính bằng cách sử dụng Tô màu Đồ thị Khoảng.
Phân bổ bên trong một khối cơ bản được gọi là Phân bổ Thanh ghi Cục bộ. Có hai phương pháp cho phân bổ thanh ghi cục bộ: Phương pháp từ trên xuống và phương pháp từ dưới lên. Phương pháp từ trên xuống là một phương pháp đơn giản dựa trên ‘Số lần xuất hiện’. Xác định các giá trị nên được giữ trong thanh ghi và giá trị nào nên được giữ trong bộ nhớ.
Thuật toán:
- Tính toán mức độ ưu tiên cho mỗi thanh ghi ảo.
- Sắp xếp các thanh ghi theo thứ tự ưu tiên.
- Gán thanh ghi theo thứ tự ưu tiên.
- Viết lại mã.
Việc phân bổ phức tạp hơn khi luồng điều khiển đi vào bức tranh. Phạm vi sống (Live Ranges) bao gồm một tập hợp các định nghĩa và sử dụng có liên quan đến nhau, tức là không có thanh ghi nào có thể dùng chung trong một cặp lệnh/dữ liệu như vậy.
Một phạm vi sống được biểu diễn dưới dạng một khoảng [i, j], trong đó i là định nghĩa và j là lần sử dụng cuối cùng.
Phân bổ và Gán Thanh ghi Toàn cục: Vấn đề chính của bộ phân bổ thanh ghi là giảm thiểu tác động của mã tràn; thời gian thực thi cho mã tràn, không gian mã cho hoạt động tràn và không gian dữ liệu cho các giá trị bị tràn. Phân bổ toàn cục không thể đảm bảo giải pháp tối ưu cho thời gian thực thi của mã tràn.
Sự khác biệt chính giữa Phân bổ Cục bộ và Toàn cục: Cấu trúc của một phạm vi sống toàn cục phức tạp hơn so với phạm vi cục bộ. Trong một phạm vi sống toàn cục, các tham chiếu riêng biệt có thể thực thi một số lần khác nhau (khi các khối cơ bản tạo thành một vòng lặp).
Để đưa ra quyết định về phân bổ và gán, bộ phân bổ toàn cục chủ yếu sử dụng tô màu đồ thị bằng cách xây dựng một đồ thị giao thoa. Bộ phân bổ thanh ghi sau đó cố gắng xây dựng một phép tô màu k cho đồ thị đó, trong đó ‘k’ là số lượng thanh ghi vật lý.
Từ sơ đồ trên, có thể thấy rằng phạm vi sống LRA bắt đầu trong khối cơ bản đầu tiên và kết thúc trong khối cơ bản cuối cùng. Do đó, nó sẽ chia sẻ một cạnh với mọi Phạm vi sống khác, tức là Lrb, Lrc, Lrd. Tuy nhiên, Lrb, Lrc, Lrd không chồng chéo với bất kỳ phạm vi sống nào khác ngoại trừ Lra nên chúng chỉ chia sẻ một cạnh với Lra.
Xây dựng Bộ phân bổ: Lưu ý rằng việc tìm kiếm đồ thị k-màu là một bài toán NP-đầy đủ, vì vậy chúng ta cần một phép xấp xỉ cho việc này. Thử với việc chia phạm vi sống thành một số khối không tầm thường (những khối được sử dụng nhiều nhất).
Trình biên dịch có thể sử dụng đồ thị giao thoa để hợp nhất hai phạm vi sống. Việc hợp nhất có thể mang lại lợi ích bằng cách giảm số lượng nút trong đồ thị, giúp đơn giản hóa quá trình tô màu.
