Користувач:Хацькевич/Чернетки/Розподіл регістрів

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

Вступ

В багатьох мовах програмування, програміст має ілюзію наявності довільного числа змінних. However, під час компіляції, компілятор має вірішити як розподілити ці змінні у невеличкий, обмежений набір регістрів. Не всі змінні використовуються (або "живуть") одночасно, тому деякі регістри можуть бути розподілені до більш ніж однієї змінної. Проте, дві змінних, що використовуються одночасно, не можуть бути призначені тому ж самому регістру без пошкодження їх значень. Змінні, які не можуть бути призначеними у регістрах мають бути збережені RAM та завантажені/отримані для кожного читання/писання, цей процесс зветься проливання. Доступ до оперативної памяті значно повільніший ніж до регістрів та знижує швидкість виконання скомпільованої програми, тому метою оптимізації компілятором є розподілення багатьох змінних за регістрами наскільки це можливо. Тиск регістрів цей термін використовується коли декілька апаратних регістрів наявні ніж було б оптимальним; високий тиск звичайно значить що більше розливів і завантажень необхідно.

Треба додати, що програми можуть додатково оптимізована використанням однакового регістра для джерела та призначення інструкції переміщення де це можливо. Це дуже важливо якщо компілятор використовує іншу оптимізацію - таку як, яка розумно створює додаткові інструкції переміщення в проміжному коді.

Ізоморфізм в розфарбуванні графів

За допомогою життєвого аналізу, компілятор може визначити який набір змінних живе одночасно за допомогою аналізу участі змінних в інструкціях переміщення. Використовуючи цю інформацію, компілятор створює граф, в якому кожна вершина відтворює унікальну змінну в програмі. Interference edges поєднують пари вершин, що живуть одночасно, та preference edges поєднують пари вершин, що задіяні в інструкціях переміщення. Розподілення регістрів може бути зведено до проблеми отриманого графа, де K є числом регістрів наявних на цільовій системі. No two vertices sharing an interference edge may be assigned the same color, and vertices sharing a preference edge should be assigned the same color if possible. Деякі з вершин повинні розфарбовані попередньо до початку, відтворюючи змінні, що мають зберігатися в регістрах через угоду про виклик або зв'язок між модулями. Треба зазначити, що деякі регістри мають системне значення і не беруть участь в розподілі регістрів. Оскільки розфарбування графів в цілому є NP-повною задачею, тому є розподілення регістрів. Проте, гарний алгоритм балансує між швидкодією та якістю скомпільованого кода.

Техніка розфарбовування графів є такою ефективною тому що це takes into account не лише змінна розглядається для розподілу регістрів, але також всі змінні що живуть в той же час. Логікою цього є те, що якщо всі сусідні живі змінні змінної V можуть бути розподілено регістри, тоді ви можете V + всіх сусідів. So it is a recursive case of removing a variable from the set(list) of live variables at a point, called the graph, and then examining the resulting "graph" minus one variable. The loop continues until the reduced graph can be allocated, and all the other variables are spilled to memory.