Înregistrați alocarea

Distribuția registrelor în procesul de compilare [1] este maparea unui set de un număr mare de variabile ale unui fragment de program de calculator (registre virtuale ale unei reprezentări intermediare) pe, de regulă, un mic set de microprocesoare fizice. registre . Alocarea registrului se poate face într-un singur bloc de bază ( alocarea registrului local ) sau în întreaga procedură ( alocarea registrului global ).

În mod obișnuit, programele de calculator trebuie să funcționeze cu cantități mari de date, dar majoritatea microprocesoarelor acceptă doar operațiuni pe un număr fix de „celule” mici numite registre. Unele procesoare permit utilizarea operanzilor stocați în memorie , dar accesarea registrelor este mult mai rapidă decât accesarea memoriei (chiar dacă zona de memorie specificată poate fi stocată în cache ).

Probleme

Problema de alocare a registrului este NP-complet [2] [3] . De obicei, numărul de variabile dintr-un program depășește cu mult registrele fizice disponibile, așa că unele variabile trebuie să fie stocate în stiva locală. Accesurile la memorie pot fi minimizate prin stocarea variabilelor cel mai puțin frecvent utilizate, dar determinarea care variabile sunt mai puțin utilizate nu este întotdeauna ușoară.

De asemenea, este de remarcat faptul că unele registre au adesea un scop de sistem sau serviciu și utilizarea lor este limitată.

Alocarea registrului global

Ca majoritatea celorlalte optimizări, alocarea registrului se bazează pe utilizarea unor analize. În acest caz, este cel mai adesea analiza duratei de viață a variabilelor și analiza fluxului de date.

Colorarea graficului de incompatibilitate propusă de matematicianul Gregory Khaitin este considerată a fi un algoritm tradițional de alocare a registrelor .

Fiecare variabilă (registru simbolic) corespunde unui nod grafic . Dacă duratele de viață ale variabilelor se intersectează, nodurile corespunzătoare sunt conectate printr-un arc. Graficul trebuie colorat cu culori (unde corespunde numărului de registre fizice disponibile) astfel încât nicio pereche de noduri învecinate să nu aibă aceeași culoare.

Gradul unui nod de graf este numărul vecinilor săi. Dacă gradul unui nod grafic este mai mic decât , atunci este întotdeauna posibil să găsești o culoare pentru acesta care să nu fie atribuită niciunuia dintre vecini. Dacă toate nodurile au un grad mai mare decât , una dintre variabile este stocată în memorie, împărțindu-se în mai multe noduri de grad mai mic.

Până când graficul G poate fi colorat cu culorile R Îndepărtați iterativ toate nodurile unui grafic de gradul < R, împingându-le pe o stivă Dacă toate nodurile graficului au fost eliminate, graficul poate fi colorat cu R culori Scoateți nodul N din stivă și adăugați-l la grafic atribuindu-i o culoare În caz contrar, graficul G nu poate fi colorat cu culorile R Simplificați G selectând un nod de stocat în memorie și împărțindu-l în mai multe noduri (nodul de stocat în memorie este ales euristic)

Preston Briggs a propus să modifice algoritmul lui Khaitin [4] prin amânarea stocării variabilei în memorie până când culorile sunt alocate nodurilor graficului. Pentru unele grafice necolorabile, acest lucru evită stocarea variabilelor în memorie. De exemplu, un pătrat cu noduri la vârfuri poate fi colorat cu culori, în timp ce gradul tuturor nodurilor sale este egal cu doi, iar algoritmul lui Khaitin va fi forțat să stocheze una dintre variabile în memorie.


Note

  1. ↑ CUNOAȘTE INTUIT | Prelegere | Alegerea instrucțiunilor în generarea codului . Consultat la 28 noiembrie 2017. Arhivat din original la 28 iulie 2021.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins și Peter W. Markstein. „Înregistrați alocarea prin colorare”. 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 Arhivat din 4 martie 2016 la Wayback Mașinărie
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. „Euristică de colorare pentru alocare de registru”. Notificări ACM SIGPLAN, volumul 24, numărul 7, 275-284, 1989  .

Link -uri