Расподела регистра

У оптимизацији компилатора, расподела регистра је процес додељивања великог броја циљева програма променљивих на мали број CPU (процесорских) регистара. Расподела регистра се може догодити преко основног блока (локална расподела регистра), преко целе функције / процедуре (глобална расподела регистра), или преко граница функције укрштених преко позивног графикона (интерпроцедурална расподела регисра). Када се заврши по функцији / процедури за позивање конвенција, може се захтевати убацивање чувања/повраћаја око сваког позивног сајта.

Увод[уреди | уреди извор]

У многим програмским језицима, програмер има илузију произвољне доделе многим променљивим. Међутим, током компилације, преводилац мора да одлучи како да издвоји ове променљиве у малом, коначном скупу регистара. Нису све променљиве у употреби (или "тренутне") у исто време, тако да неки регистри могу бити распоређени на више од једне променљиве. Међутим, две променљиве у употреби у исто време не могу бити додељене на исти регистар без оштећења својих вредност. Променљиве које се не могу приписати неком регистру морају да се чувају на RAM-у и учитавају улаз / излаз за свако читање / писање, процес који се зове просипање. Приступ RAM-у је знатно спорији него приступање регистрима и успорава брзину извршења у саставу програма, тако да оптимизација преводиоца има за циљ да додели онолико променљивих регистрима колико је могуће. Притисак регистрације је термин који се користи када постоје мањи хардверски регистри на располагању него што би било оптимално; већи притисак обично значи да су још просипања и поновна учитавања неопходна.

Поред тога, програми могу да се додатно оптимизују за додељивање истог регистар извору и одредишту move инструкције када год је то могуће. Ово је посебно важно ако преводилац користи друге оптимизације као што су SSA анализе, које вештачки генеришу додатне move инструкције у средњем коду.

Просипање[уреди | уреди извор]

У већини матичних раздељивача, свака променљива је додељена или CPU регистру или главној меморији. Предност коришћења регистра је брзина. Компјутери имају ограничен број регистара, тако да не могу све променљиве бити додељене регистрима. "Просута променљива" је променљива у главној меморији пре него у CPU регистру. Операција која премешта променљиву из регистра у меморију се зове просипање, док се обрнута операција која премешта променљиву из меморије у регистар назива пуњење. На пример, 32-битна променљива просута у меморију добија 32 бита стек простора и све референце додељене променљивој су тада од те меморије. Таква променљива има много мању брзину обраде од променљиве у регистру. При одлучивању која ће се променљива пролити, бројни фактори се узимају у обзир: време извршења, простор кода, простор података.

Изоморфизам графика боја[уреди | уреди извор]

Путем анализе тренутне променљиве, компилатори могу утврдити који скупови променљивих су ту истовремено, као и варијабле које су укључене у move инструкције. Користећи ове информације, компилатор може да конструише графикон где сваки чвор представља јединствену променљиву у програму. Интерферентне ивице омогућују повезивање пара чворова који су ту у исто време, а ивице које су у предности повезивање пара чворова који су укључени у покрету упутства. Регистрација расподеле се затим може редуковати на проблем К-бојења насталог графика, где је К број регистара доступних на циљаним архитектурама. Не постоје два темена која могу бити распоређена на исту боју, и темена која деле преференце предности требало би дати исту боју ако је могуће. Нека од темена могу бити пребојена за почетак, што представља променљиве које се морају водити у одређеним регистрима због позива конвенције или комуникацију између модула. Како је бојење графова генерално НП-комплетни проблем, тако да је и алокација регистрована. Међутим, добри алгоритми постоји који балансирају перформансе са квалитетом састављеног кода.

Може бити случај да је бојење графова алгоритам који не налази бојење интерферентног графа. У овом случају, неке променљиве морају бити проливене у меморију како би се омогућило преосталим променљивим да се распореде на регистрима. Ово се може постићи помоћу рекурзивне потраге која покушава да просипа једну променљиву, а затим рекурзивно или бојама преостали скуп променљивих или наставља рекурзивно просипање док све преостале променљиве које нису просуте могу бити у боји и додељене регистрима.

Итеративно сједињавање регистра[уреди | уреди извор]

Алокатори регистара имају неколико врста, са Итеративним сједињавањем регистара (ИСР) који могу бити више од једног. ИСР је измислио ЛАЛ Џорџ и Ендру Апел 1996. године, радећи на ранијем раду Грегора Чејтина. ИСР ради на основу неколико принципа. Прво, ако постоје непокретне вертикале у вези темена у графу са степеном мањим од К, графикон се може поједноставити уклањањем тих темена, јер кад се једном та темена додају још се гарантује да се боја може наћи за њих (поједностављење ). Друго, два темена која деле преферентне ивице чија су суседства сетови у комбинацији која имају степен мањи од К могу бити комбиновани у једном темену, истим образложењем (сједињавање). Ако ни један од два корака може да поједностави график, поједностављење се може поново покренути на потезу у вези са теменима (замрзавање). На крају, ако ништа друго не ради, темена могу бити означена као потенцијална просипања и уклоњена из графикона (изливање). Од свих ових корака смањити степен темена у графу, темена се могу трансформисати од високог степена (> К) до ниског степена током алгоритма, омогућавајући им да се поједноставе и сједине. Дакле, фазе алгоритма се итератују да осигурају агресивно поједностављивање и окупљање. Псеудо-код је овако:

 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

Сједињавање које ради у ИСР је конзервативно, јер агресивна сједињавања могу увести изливања у графу. Међутим, додатни хеуристици сједињавања попут Џорџа окупљају се да споје више темена док се обезбеђује да се не додају додатна изливања . Радне листе се користе у алгоритму како би се осигурало да свака итерација ИСР захтева субквадратно време.

Скорији развоји[уреди | уреди извор]

Граф бојења алокатора производи ефикаснији код, али њихово време алокација је високо. У случају статичке компилације, време алокација није значајан проблем. У случају динамичке компилације, као што је just-in-time компилација (JIT) компајлера, брза алокација регистра је важна. Ефикасна техника предложена од стране Полета и Саркара је линеарна расподела скенирања. Ова техника захтева само један потез преко листе променљивих тренутних опсега. Опсези са кратким животом се додељују регистрима, док они са дугим животима имају тенденцију да се пролију, или бораве у меморији. Резултати су у просеку само 12% мање ефикасни од графикона бојења алокатора.

Линеарно скенирање алгоритма следи:

Извршити анализу dataflow да се прикупе тренутне информације. Пратите тренутне интервале свих променљивих, интервал када је променљива тренутна, на листи је поређано како је повећана почетна тачка (имајте на уму да је ово уређење бесплатно ако је листа изграђена). Ми сматрамо променљиве и њихове интервале да могу бити замењени у овом алгоритму.
Посматрајте кроз тренутни старт поена и издвојите регистар из доступних регистара базена у свакој тренутној променљивој.
На сваком кораку одржава списак активних интервала сортираних по крајњој тачки тренутних интервала. (Напомена: такво убацивање у уравнотеженом бинарном стаблу може да се користи за одржавање ове листе на линеарној цени.) Уклоните истекле интервале од активног списка и ослободите регистрованеинтервале на слободни регистровани базен.
У случају када је активна листа величине R не можемо издвојити регистар. У том случају додајте текући интервал на активном базену без доделе регистра. Поделите интервал од активног списка са најудаљенијом крајњом тачком. Доделите регистре са просутим интервалом важећем интервалу или ако је тренутни интервал просут, не мењајте задатке регистра.

Купер и Дасгупта су недавно развили алгоритам графа боја Чејтин-Бригс са "губицима" погодан за употребу у ЈИТ.^[1] Надимак "губитак" односи се на непрецизност алгоритма који уводи у интерференције графикона. Ова оптимизација смањује цену изградње графикона Чејтин-Бригс што га чини погодним за runtime компилацију. Експерименти показују да овај регистар алокатор са губитком надмашује линеарно скенирање на већини тестова.

"Оптимални" регистар расподеле алгоритама заснованим на Integer Programming су развили Гудвин и Вилкен за редовне архитектуре. Ови алгоритми су продужени до нерегуларних архитектура од Конга и Вилкена.

Док је најгоре време извршења експоненцијално, експериментални резултати показују да је стварно време обичног реда $O(n^{2.5})$ броја ограничења $n$ .^[2]

Могућност да се уради расподела регистра SSA-form програма је приоритет данашњих истраживања.^[3] Графикони интерференције SSA-form програма су чордал, и као такви, они могу бити обојени у полиномијалном времену. Да појаснимо изворе NP-комплетност, недавно истраживање је испитивало расподелу регистара у ширем контексту.^[4]

Види још[уреди | уреди извор]

Стралеров број, минималан број регистара који су потребни за процену експресије стабла.^[5]

Референце[уреди | уреди извор]

^ Cooper, Dasgupta, "Tailoring Graph-coloring Register Allocation For Runtime Compilation", http://llvm.org/pubs/2006-04-04-CGO-GraphColoring.html
^ Kong, Wilken, "Precise Register Allocation for Irregular Architectures", http://www.ece.ucdavis.edu/cerl/cerl_arch/irreg.pdf Архивирано на сајту Wayback Machine (6. децембар 2012)
^ Brisk, Hack, Palsberg, Pereira, Rastello, "SSA-Based Register Allocation", ESWEEK Tutorial http://thedude.cc.gt.atl.ga.us/tutorials/1/^{[мртва веза]}
^ 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. стр. 283—298. ISBN 978-3-540-72520-6. doi:10.1007/978-3-540-72521-3_21.
^ 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. .

[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 Архивирано на сајту Wayback Machine (6. децембар 2012)

[3] Brisk, Hack, Palsberg, Pereira, Rastello, "SSA-Based Register Allocation", ESWEEK Tutorial http://thedude.cc.gt.atl.ga.us/tutorials/1/^{[мртва веза]}

[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. стр. 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. .

[1]

[2]

[3]

[4]

[5]