Википедија

Raspodela registra

U optimizaciji kompilatora, raspodela registra je proces dodeljivanja velikog broja ciljeva programa promenljivih na mali broj  CPU (procesorskih) registara. Raspodela registra se može dogoditi preko osnovnog bloka (lokalna raspodela registra), preko cele funkcije / procedure (globalna raspodela registra), ili preko granica funkcije ukrštenih preko pozivnog grafikona (interproceduralna raspodela regisra). Kada se završi po funkciji / proceduri za pozivanje konvencija, može se zahtevati ubacivanje čuvanja/povraćaja oko svakog pozivnog sajta.

Uvod uredi

U mnogim programskim jezicima, programer ima iluziju proizvoljne dodele mnogim promenljivim. Međutim, tokom kompilacije, prevodilac mora da odluči kako da izdvoji ove promenljive u malom, konačnom skupu registara. Nisu sve promenljive u upotrebi (ili "trenutne") u isto vreme, tako da neki registri mogu biti raspoređeni na više od jedne promenljive. Međutim, dve promenljive u upotrebi u isto vreme ne mogu biti dodeljene na isti registar bez oštećenja svojih vrednost. Promenljive koje se ne mogu pripisati nekom registru moraju da se čuvaju na RAM-u i učitavaju ulaz / izlaz za svako čitanje / pisanje, proces koji se zove prosipanje. Pristup RAM-u je znatno sporiji nego pristupanje registrima i usporava brzinu izvršenja u sastavu programa, tako da optimizacija prevodioca ima za cilj da dodeli onoliko promenljivih registrima koliko je moguće. Pritisak registracije je termin koji se koristi kada postoje manji hardverski registri na raspolaganju nego što bi bilo optimalno; veći pritisak obično znači da su još prosipanja i ponovna učitavanja neophodna.

Pored toga, programi mogu da se dodatno optimizuju za dodeljivanje istog registar izvoru i odredištu  move instrukcije kada god je to moguće. Ovo je posebno važno ako prevodilac koristi druge optimizacije kao što su SSA analize, koje veštački generišu dodatne move instrukcije u srednjem kodu.

Prosipanje uredi

U većini matičnih razdeljivača, svaka promenljiva je dodeljena ili CPU registru ili glavnoj memoriji. Prednost korišćenja registra je brzina. Kompjuteri imaju ograničen broj registara, tako da ne mogu sve promenljive biti dodeljene registrima. "Prosuta promenljiva" je promenljiva u glavnoj memoriji pre nego u CPU registru. Operacija koja premešta promenljivu iz registra u memoriju se zove prosipanje, dok se obrnuta operacija koja premešta promenljivu iz memorije u registar naziva punjenje. Na primer, 32-bitna promenljiva prosuta u memoriju dobija 32 bita stek prostora i sve reference dodeljene promenljivoj su tada od te memorije. Takva promenljiva ima mnogo manju brzinu obrade od promenljive u registru. Pri odlučivanju koja će se promenljiva proliti, brojni faktori se uzimaju u obzir: vreme izvršenja, prostor koda, prostor podataka.

Izomorfizam grafika boja uredi

Putem analize trenutne promenljive, kompilatori mogu utvrditi koji skupovi promenljivih su tu istovremeno, kao i varijable koje su uključene u move instrukcije. Koristeći ove informacije, kompilator može da konstruiše grafikon gde svaki čvor predstavlja jedinstvenu promenljivu u programu. Interferentne ivice omogućuju povezivanje para čvorova koji su tu u isto vreme, a ivice koje su u prednosti povezivanje para čvorova koji su uključeni u pokretu uputstva. Registracija raspodele se zatim može redukovati na problem K-bojenja nastalog grafika, gde je K broj registara dostupnih na ciljanim arhitekturama. Ne postoje dva temena koja mogu biti raspoređena na istu boju, i temena koja dele preference prednosti trebalo bi dati istu boju ako je moguće. Neka od temena mogu biti prebojena za početak, što predstavlja promenljive koje se moraju voditi u određenim registrima zbog poziva konvencije ili komunikaciju između modula. Kako je bojenje grafova generalno NP-kompletni problem, tako da je i alokacija registrovana. Međutim, dobri algoritmi postoji koji balansiraju performanse sa kvalitetom sastavljenog koda.

Može biti slučaj da je bojenje grafova algoritam koji ne nalazi bojenje interferentnog grafa. U ovom slučaju, neke promenljive moraju biti prolivene u memoriju kako bi se omogućilo preostalim promenljivim da se rasporede na registrima. Ovo se može postići pomoću rekurzivne potrage koja pokušava da prosipa jednu promenljivu, a zatim rekurzivno ili bojama preostali skup promenljivih ili nastavlja rekurzivno prosipanje dok sve preostale promenljive koje nisu prosute mogu biti u boji i dodeljene registrima.

Iterativno sjedinjavanje registra uredi

Alokatori registara imaju nekoliko vrsta, sa Iterativnim sjedinjavanjem registara (ISR) koji mogu biti više od jednog. ISR je izmislio LAL Džordž i Endru Apel 1996. godine, radeći na ranijem radu Gregora Čejtina. ISR radi na osnovu nekoliko principa. Prvo, ako postoje nepokretne vertikale u vezi temena u grafu sa stepenom manjim od K, grafikon se može pojednostaviti uklanjanjem tih temena, jer kad se jednom ta temena dodaju još se garantuje da se boja može naći za njih (pojednostavljenje ). Drugo, dva temena koja dele preferentne ivice čija su susedstva setovi u kombinaciji koja imaju stepen manji od K mogu biti kombinovani u jednom temenu, istim obrazloženjem (sjedinjavanje). Ako ni jedan od dva koraka može da pojednostavi grafik, pojednostavljenje se može ponovo pokrenuti na potezu u vezi sa temenima (zamrzavanje). Na kraju, ako ništa drugo ne radi, temena mogu biti označena kao potencijalna prosipanja i uklonjena iz grafikona (izlivanje). Od svih ovih koraka smanjiti stepen temena u grafu, temena se mogu transformisati od visokog stepena (> K) do niskog stepena tokom algoritma, omogućavajući im da se pojednostave i sjedine. Dakle, faze algoritma se iteratuju da osiguraju agresivno pojednostavljivanje i okupljanje. Pseudo-kod je ovako: 

 function IRC_color g K :
 repeat
   if ∃v s.t. ¬moveRelated(v) ∧ degree(v) < K then simplify v
   else if ∃e s.t. cardinality(neighbors(first e) ∪ neighbors(second e)) < K then coalesce e
   else if ∃v s.t. moveRelated(v) then deletePreferenceEdges v
   else if ∃v s.t. ¬precolored(v) then spill v
   else return
 loop

Sjedinjavanje koje radi u ISR je konzervativno, jer agresivna sjedinjavanja mogu uvesti izlivanja u grafu. Međutim, dodatni heuristici sjedinjavanja poput Džordža okupljaju se da spoje više temena dok se obezbeđuje da se ne dodaju dodatna izlivanja . Radne liste se koriste u algoritmu kako bi se osiguralo da svaka iteracija ISR zahteva subkvadratno vreme.

Skoriji razvoji uredi

Graf bojenja alokatora proizvodi efikasniji kod, ali njihovo vreme alokacija je visoko. U slučaju statičke kompilacije, vreme alokacija nije značajan problem. U slučaju dinamičke kompilacije, kao što je just-in-time kompilacija (JIT) kompajlera, brza alokacija registra je važna. Efikasna tehnika predložena od strane Poleta i Sarkara je linearna raspodela skeniranja. Ova tehnika zahteva samo jedan potez preko liste promenljivih trenutnih opsega. Opsezi sa kratkim životom se dodeljuju registrima, dok oni sa dugim životima imaju tendenciju da se proliju, ili borave u memoriji. Rezultati su u proseku samo 12% manje efikasni od grafikona bojenja alokatora.

Linearno skeniranje algoritma sledi:

  1. Izvršiti analizu dataflow da se prikupe trenutne informacije. Pratite trenutne intervale svih promenljivih, interval kada je promenljiva trenutna, na listi je poređano kako je povećana početna tačka (imajte na umu da je ovo uređenje besplatno ako je lista izgrađena). Mi smatramo promenljive i njihove intervale da mogu biti zamenjeni u ovom algoritmu.
  2. Posmatrajte kroz trenutni start poena i izdvojite registar iz dostupnih registara bazena u svakoj trenutnoj promenljivoj.
  3. Na svakom koraku održava spisak aktivnih intervala sortiranih po krajnjoj tački trenutnih  intervala. (Napomena: takvo ubacivanje u uravnoteženom binarnom stablu može da se koristi za održavanje ove liste na linearnoj ceni.) Uklonite istekle intervale od aktivnog spiska i oslobodite registrovaneintervale na slobodni registrovani bazen.
  4. U slučaju kada je aktivna lista veličine R ne možemo izdvojiti registar. U tom slučaju dodajte tekući interval na aktivnom bazenu bez dodele registra. Podelite interval od aktivnog spiska sa najudaljenijom krajnjom tačkom. Dodelite registre sa prosutim intervalom važećem intervalu ili ako je trenutni interval  prosut, ne menjajte zadatke registra.

Kuper i Dasgupta su nedavno razvili algoritam grafa boja Čejtin-Brigs sa "gubicima"  pogodan za upotrebu u JIT.[1] Nadimak "gubitak" odnosi se na nepreciznost algoritma koji uvodi u interferencije grafikona. Ova optimizacija smanjuje cenu izgradnje grafikona  Čejtin-Brigs što ga čini pogodnim za runtime kompilaciju. Eksperimenti pokazuju da ovaj registar alokator sa gubitkom nadmašuje linearno skeniranje na većini testova.

"Optimalni" registar raspodele algoritama zasnovanim na Integer Programming su razvili Gudvin i Vilken za redovne arhitekture. Ovi algoritmi su produženi do neregularnih arhitektura od Konga i Vilkena.

Dok je najgore vreme izvršenja eksponencijalno, eksperimentalni rezultati pokazuju da je stvarno vreme običnog reda   broja ograničenja  .[2]

Mogućnost da se uradi raspodela registra SSA-form programa je prioritet današnjih istraživanja.[3] Grafikoni interferencije SSA-form programa su čordal, i kao takvi, oni mogu biti obojeni u polinomijalnom vremenu. Da pojasnimo izvore NP-kompletnost, nedavno istraživanje je ispitivalo raspodelu registara u širem kontekstu.[4]

Vidi još uredi

  • Stralerov broj, minimalan broj registara koji su potrebni za procenu ekspresije stabla.[5]

Reference uredi

  1. ^ Cooper, Dasgupta, "Tailoring Graph-coloring Register Allocation For Runtime Compilation", http://llvm.org/pubs/2006-04-04-CGO-GraphColoring.html
  2. ^ Kong, Wilken, "Precise Register Allocation for Irregular Architectures", http://www.ece.ucdavis.edu/cerl/cerl_arch/irreg.pdf Arhivirano na sajtu Wayback Machine (6. decembar 2012)
  3. ^ Brisk, Hack, Palsberg, Pereira, Rastello, "SSA-Based Register Allocation", ESWEEK Tutorial http://thedude.cc.gt.atl.ga.us/tutorials/1/[mrtva veza]
  4. ^ Bouchez, Florent; Darte, Alain; Guillon, Christophe; Rastello, Fabrice (2007). „Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How” (PDF). Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science. 4382. str. 283—298. ISBN 978-3-540-72520-6. doi:10.1007/978-3-540-72521-3_21. 
  5. ^ Flajolet, P.; Raoult, J.C.; Vuillemin, J. (1979). „The number of registers required for evaluating arithmetic expressions”. Theoretical Computer Science. 9: 99—125. doi:10.1016/0304-3975(79)90009-4. .
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Расподела_регистра&oldid=26987335”