Розподіл регістрів

Розподілом регістрів у процесі компіляції називають відображення множини великого числа змінних фрагмента комп'ютерної програми (віртуальних регістрів проміжного подання) на, як правило, невелику множину фізичних регістрів процесора. Розподіл регістрів може виконуватися в окремо взятому базовому блоці (локальний розподіл регістрів) або у всій процедурі (глобальний розподіл регістрів).

Як правило комп'ютерним програмам доводиться працювати з великою кількістю даних, проте більшість мікропроцесорів підтримує операції тільки на фіксованому числі невеликих «комірок», званих регістрами. Деякі процесори дозволяють використовувати операнди, що зберігаються в пам'яті, однак звернення до регістрів відбувається значно швидше, ніж звернення до пам'яті (навіть з урахуванням того, що зазначена ділянка пам'яті може міститися в кеші).

Проблеми

Задача розподілу регістрів є NP-повною. Зазвичай кількість змінних у програмі значно перевершує кількість доступних фізичних регістрів, тому деякі змінні доводиться зберігати в локальному стеку. Звернення до пам'яті можна мінімізувати, якщо зберігати там найрідше використовувані змінні, проте визначити, які змінні використовуються найрідше, не завжди легко.

Крім того, деякі регістри часто мають системне або службове призначення і їх використання обмежене.

Глобальний розподіл регістрів

Як і більшість інших оптимізацій, розподіл регістрів базується на використанні деякого аналізу. В цьому випадку це, найчастіше, аналіз часу життя змінних і аналіз потоку даних.

Традиційним алгоритмом розподілу регістрів вважається розфарбовування графу несумісності, запропоноване математиком Грегорі Хайтіном.

Кожній змінній (символьному регістру) відповідає вузол ${\displaystyle N}$ графа ${\displaystyle G}$. Якщо часи життя змінних перетинаються, відповідні їм вузли з'єднують дугою. Граф потрібно розфарбувати ${\displaystyle R}$ кольорами (де ${\displaystyle R}$ відповідає кількості доступних фізичних регістрів) так, щоб жодна пара сусідніх вузлів не мала однакового кольору.

Степенем вузла графа називається кількість його сусідів. Якщо степінь вузла графа менше ${\displaystyle R}$, то для нього завжди можна знайти колір, не призначений жодному із сусідів. Якщо всі вузли мають степінь більше ${\displaystyle R}$, одна зі змінних зберігається в пам'яті, і утворюється кілька вузлів меншого степеня.

Поки граф G не можна розфарбувати R кольорами Ітеративно видаляти всі вузли графа зі степенем < R, поміщаючи їх у стек Якщо всі вузли графа видалено, граф можна розфарбувати R кольорами Виштовхнути вузол N зі стека і додати його в граф, призначивши йому колір В іншому випадку граф G не можна розфарбувати R кольорами Спростити G, вибравши вузол для збереження в пам'яті і розбивши його на кілька вузлів (вузол для збереження в пам'яті вибирається евристично) 

Престон Бріггс (Preston Briggs) запропонував модифікувати алгоритм Хайтіна, відкладаючи збереження змінної в пам'яті до призначення кольорів вузлам графа. Для деяких нерозфарбовуваних ${\displaystyle R}$ кольорами графів це дозволяє обійтися без збереження змінних у пам'яті. Наприклад, квадрат з вузлами у вершинах можна розфарбувати ${\displaystyle R=2}$ кольорами, тоді як степінь усіх його вузлів дорівнює двом і за алгоритмом Хайтіна доведеться зберегти одну зі змінних у пам'яті.

Примітки

1. . Архів оригіналу за 28 липня 2021. Процитовано 28 липня 2021.
2. Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. «Register allocation via coloring.» Computer Languages, 6:47-57, 1981.(англ.)
3. Fernando Magno Quintão Pereira, Jens Palsberg, «Register Allocation after Classical SSA Elimination is NP-complete»(англ.), http://pike.cs.ucla.edu/~palsberg/paper/fossacs06.pdf [ 4 березня 2016 у Wayback Machine.]
4. Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. «Coloring Heuristics for Register Allocation.» ACM SIGPLAN Notices, Volume 24, Issue 7, 275—284, 1989.(англ.)

Посилання

• http://www.intuit.ru/studies/courses/1157/173/lecture/4707?page=5 [ 28 липня 2021 у Wayback Machine.] 7
• Компіляція. 7: Призначення регістрів [ 1 грудня 2017 у Wayback Machine.], 2010
• Караваєв Д. Ю. Про реалізацію методу розподілу регістрів при компіляції [ 7 липня 2017 у Wayback Machine.], RSDN 2012
• Hadi Brais, Оптимізації компілятором — Що кожен програміст повинен знати про оптимізації коду компілятором. Частина 2 [ 1 грудня 2017 у Wayback Machine.], травень 2015
• Keith Schwarz, Register Allocation [ 11 травня 2021 у Wayback Machine.], Stanford's cs143 Compilers, 2012