Regisztrálás kiosztása

A regiszterek elosztása a fordítási folyamatban [1] egy számítógépes program egy töredékének nagyszámú változójának (köztes reprezentáció virtuális regisztereinek) leképezése általában egy kis fizikai mikroprocesszor -készletre. regiszterek . A regiszterek kiosztása történhet egyetlen alapblokkban ( helyi regiszter-allokáció ), vagy a teljes eljárásban ( globális regiszter-allokáció ).

Általában a számítógépes programoknak nagy mennyiségű adattal kell dolgozniuk, de a legtöbb mikroprocesszor csak meghatározott számú kis "cellán", úgynevezett regiszteren támogatja a műveleteket. Egyes processzorok lehetővé teszik a memóriában tárolt operandusok használatát , de a regiszterekhez való hozzáférés sokkal gyorsabb, mint a memória elérése (annak ellenére, hogy a megadott memóriaterület gyorsítótárazható ).

Problémák

A regiszter allokációs probléma NP-teljes [2] [3] . Általában egy programban a változók száma messze meghaladja a rendelkezésre álló fizikai regiszterek számát, ezért néhány változót a helyi veremben kell tárolni. A memóriaelérések minimalizálhatók, ha a legritkábban használt változókat tároljuk ott, de nem mindig könnyű meghatározni, hogy mely változókat használjuk a legkevésbé.

Azt is érdemes megjegyezni, hogy egyes regiszterek gyakran rendszer- vagy szolgáltatási céllal rendelkeznek, és felhasználásuk korlátozott.

Globális regiszter allokáció

A legtöbb egyéb optimalizáláshoz hasonlóan a regiszterelosztás is bizonyos elemzések felhasználásán alapul. Ebben az esetben leggyakrabban a változók élettartamának elemzése és az adatáramlás elemzése.

Az inkompatibilitási gráf Gregory Khaitin matematikus által javasolt színezése hagyományos regiszterallokációs algoritmusnak tekinthető .

Minden változó (szimbolikus regiszter) egy gráf csomópontnak felel meg . Ha a változók élettartama metszi egymást, a megfelelő csomópontokat egy ív köti össze. A gráfot színekkel kell kiszínezni (ahol ez megfelel a rendelkezésre álló fizikai regiszterek számának), oly módon, hogy a szomszédos csomópontok egyetlen párja se legyen azonos színű.

Egy gráfcsomópont foka a szomszédjainak száma. Ha egy gráfcsomópont foka kisebb, mint , akkor mindig találhatunk neki olyan színt, amely nincs hozzárendelve egyik szomszédhoz sem. Ha az összes csomópont fokozata nagyobb, mint , akkor az egyik változó a memóriában tárolódik, több kisebb fokú csomópontra osztva.

Amíg a G gráf R színnel színezhető Iteratív módon távolítsa el az < R fokú gráf összes csomópontját, és tolja őket a verembe Ha a gráf összes csomópontját eltávolította, a gráf R színnel színezhető Vegye ki az N csomópontot a veremből, és adja hozzá a grafikonhoz úgy, hogy színt rendel hozzá Ellenkező esetben a G gráf nem színezhető R színnel Egyszerűsítse a G-t úgy, hogy kiválaszt egy csomópontot a memóriában tárolni, és több csomópontra osztja fel (a memóriában tárolandó csomópont heurisztikusan van kiválasztva)

Preston Briggs azt javasolta, hogy módosítsák Khaitin algoritmusát [4] oly módon, hogy elhalasztják a változó memóriában való tárolását, amíg a színek hozzá nem rendelődnek a gráf csomópontjaihoz. Egyes nem színezhető grafikonok esetében ez elkerüli a változók memóriában való tárolását. Például egy négyzet, amelynek csúcsaiban csomópontok vannak, színekkel színezhető, miközben az összes csomópontjának foka kettő, és Khaitin algoritmusa kénytelen lesz az egyik változót a memóriában tárolni.


Jegyzetek

  1. ↑ KNOW INTUIT | Előadás | Választható utasítások a kódgeneráláshoz . Letöltve: 2017. november 28. Az eredetiből archiválva : 2021. július 28.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins és Peter W. Markstein. "Regisztráljon kiosztást színezéssel." Computer Languages, 6:47-57, 1981  .
  3. ↑ Fernando Magno Quintão Pereira, Jens Palsberg, "A regisztrációs kiosztás a klasszikus SSA elimináció után NP-teljes"  , http://pike.cs.ucla.edu/~palsberg/paper/fossacs06.pdf Archiválva 2016. március 4- től a Waybacken Gép
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Színezési heurisztika a regiszterkiosztáshoz." ACM SIGPLAN közlemények, 24. kötet, 7. szám, 275-284, 1989  .

Linkek