Rekisterin allokointi

Rekistereiden jakaminen käännösprosessissa [1] on tietokoneohjelman fragmentin suuren määrän muuttujia (väliesityksen virtuaalirekisterit) kartoittamista pääsääntöisesti pieneen fyysisen mikroprosessorin joukkoon. rekisterit . Rekisterin allokointi voidaan tehdä yhdessä peruslohkossa ( paikallinen rekisteriallokaatio ) tai koko menettelyssä ( globaalirekisterin allokointi ).

Tyypillisesti tietokoneohjelmien on toimittava suurten tietomäärien kanssa, mutta useimmat mikroprosessorit tukevat toimintoja vain tietyllä määrällä pieniä "soluja", joita kutsutaan rekistereiksi. Jotkut prosessorit sallivat muistiin tallennettujen operandien käytön , mutta rekistereihin pääsy on paljon nopeampaa kuin muistiin pääsy (vaikka määritetty muistialue voidaan tallentaa välimuistiin ).

Ongelmia

Rekisterin allokointiongelma on NP-täydellinen [2] [3] . Tyypillisesti ohjelman muuttujien määrä on paljon enemmän kuin käytettävissä olevat fyysiset rekisterit, joten jotkut muuttujat on tallennettava paikalliseen pinoon. Muistin käyttöjä voidaan minimoida tallentamalla sinne vähiten käytetyt muuttujat, mutta vähiten käytettyjen muuttujien määrittäminen ei ole aina helppoa.

On myös syytä huomata, että joillakin rekistereillä on usein järjestelmä- tai palvelutarkoitus ja niiden käyttö on rajoitettua.

Globaali rekisteriallokaatio

Kuten useimmat muutkin optimoinnit, rekisterin allokointi perustuu jonkin analyysin käyttöön. Tässä tapauksessa kyse on useimmiten muuttujien eliniän analysoinnista ja tietovirran analysoinnista.

Matemaatikko Gregory Khaitinin ehdottaman yhteensopimattomuusgraafin väritystä pidetään perinteisenä rekisterin allokointialgoritmina .

Jokainen muuttuja (symbolirekisteri) vastaa graafin solmua . Jos muuttujien elinajat leikkaavat, vastaavat solmut yhdistetään kaarella. Graafi on väritettävä väreillä (jos se vastaa käytettävissä olevien fyysisten rekisterien määrää) siten, että millään naapurisolmuparilla ei ole samaa väriä.

Graafin solmun aste on sen naapureiden lukumäärä. Jos graafin solmun aste on pienempi kuin , niin sille on aina mahdollista löytää väri, jota ei ole osoitettu millekään naapurista. Jos kaikkien solmujen aste on suurempi kuin , yksi muuttujista tallennetaan muistiin jaettuna useisiin solmuihin, joiden aste on pienempi.

Kunnes kuvaaja G voidaan värjätä R-väreillä Poista iteratiivisesti kaikki kaavion solmut, joiden aste on < R, työntämällä ne pinoon Jos kaikki graafin solmut on poistettu, graafi voidaan värjätä R-väreillä Nosta solmu N pinosta ja lisää se kuvaajaan määrittämällä sille väri Muuten kuvaajaa G ei voi värjätä R-väreillä Yksinkertaista G valitsemalla solmu muistiin tallennettavaksi ja jakamalla se useisiin solmuihin (muistiin tallennettava solmu valitaan heuristisesti)

Preston Briggs ehdotti Khaitinin algoritmin [4] muokkaamista lykkäämällä muuttujan tallentamista muistiin, kunnes värit on osoitettu graafin solmuille. Joillekin värittämättömille kaavioille tämä välttää muuttujien tallentamisen muistiin. Esimerkiksi neliö, jonka kärjessä on solmuja, voidaan värjätä väreillä, kun taas sen kaikkien solmujen aste on kaksi, ja Khaitinin algoritmin on pakko tallentaa yksi muuttujista muistiin.


Muistiinpanot

  1. ↑ TIEDÄ INTUITTI | Luento | Ohjeiden valinta koodin luomisessa . Haettu 28. marraskuuta 2017. Arkistoitu alkuperäisestä 28. heinäkuuta 2021.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins ja Peter W. Markstein. "Rekisteröi jakaminen värityksen kautta." 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 Arkistoitu 4. maaliskuuta 2016 Waybackissa Kone
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Väritysheuristiikka rekisterivarausta varten." ACM SIGPLAN Notices, Volume 24, Issue 7, 275-284, 1989  .

Linkit