Оптимизација компилатора
Оптимизација компилатора је процес подешавња излаза компилатора тако да се максимизирају или минимизирају неки атрибути извршног програма, као на пример минимизација времена извршавања програма, коришћења меморије итд. Показано је да су неки кодови оптимизације НП-комплетни проблеми. У пракси фактори, као на пример време потребно да компилатор изврши свој задатак, постављају горњу границу оптимизације коју имплементатор компилатора може дати. Такође у прошлости су ограничења меморије била главни фактор у избору оптимизације.
Типови оптимизације уреди
Технике оптимизације се могу поделити у неколико група које утичу на било ста између једног исказа и целог програма. У принципу локалне технике се много лакше имплементирају него глобалне али зато и мање доприносе оптимизацији. Неки примери група су:
- Peephole оптимизација : Обично се извршава после превођења на машински језик. Ова форма оптимизације испитује неколико оближњих инструкција да види да ли могу бити замењене краћим низом инструкција, као на пример множење бројем два се може брже извршити шифтовањем у лево.
- Локалне оптимизације : Оне само узимају у обзир информације које су локалне за неку функцију. Ово смањује количину потребне анализе, али значи да претпоставке у најгорем случају морају да се донесу када дође до позива функције или коришћења глобалних промењивих
- Оптимизација целог програма : Оне анализирају изворни код целог програма. Већа количина прикупљених информација значи да оптимизација може да буде много ефективинија у поређењу са оптимизацијама заснованим на локалним информацијама. Ова врста оптимизације такође дозвољава коришћење неких других техника, као на пример замену позива функције целим телом функције
- Оптимизација петљи (loop optimization) : Оне делују на исказе који чине петљу, као на пример for петља. Овакве оптимизације имају велики утицај зато што су многи програми највише времена у својим петљама.
- Оптимизације које зависе/не зависе од програмског језика : Већина језика високог нивоа има сличне програмске конструкције (if, switch, case, for, while.... ) , па се тако и користе сличне технике оптимизације. Ипак неке карактеристике неких програмских језика чине неке оптимизације тешко применљивим. На пример показивачи у језицима C и C++ отежавају оптимизацију низова. Такође неке карактеристике и олакшавају употребу оптимизација.
- Оптимизације које зависе/не зависе од машине : Многе оптимизације које раде на концептима апстрактног програмирања (петље, објекти, структуре) не зависе од машине за коју је компилатор направљен, али многе најефикасније оптимизације су оне које најбоље користе специјалне могућности одеређених машина.
Фактори који утичу на оптимизацију уреди
- Машина
Избор оптимизација које могу и требају да се ураде умногоме зависи од одређене машине. Понекад је могуће параметаризовати неке факторе машине, тако да се исти део кода компилатора мозе користити на различитим машинама само изменама описних параметара машине. GCC је један такав компилатор
- Архитектура одабраног процесора (CPU-a)
- Број CPU регистара : Већи број регистара омогућава лакшу оптимизацију. Локалне променљиве се могу чувати у регистрима а не на стеку. Такође се и резултати могу оставити у регистрима без уписивања и читања из меморије.
- RISC vs. CISC : Скупови CISC инструкција већином имају различите дузине инструкција, понекад и већи број инструкција које се могу искористити, и свака инструкција може различито трајати. Скупови RISC инструкција покушавају да уклоне те разлике (скупови инструкција су константне дужине, обично има мање комбинација операција са регистрима и меморијом... ). Може постојати више начина за извршавање неког задатка, где CISC обично даје више могућности него RISC. Компилатори морају да знају релативне цене различитих инструкција и да изаберу најбољи редослед инструкција.
- Проточна обрада (енгл. Pipeline) : Компилатори могу да распореде тако да се застоји проточне обраде (када процесор губи време док чека разрешавање неких конфликата, до којих долази када инструкција на неком нивоу проточне обраде зависи од резултата друге инструкције испред ње, али која још није завршена) ређе дешавају.
- Број функционалних јединица : Неки процесори имају више ALU-ове и FPR-ова (Floating point unit). ово им омогућава да изврше неколико инструкција одједном. Такође могу постојати ограничења у томе које инструкције се могу одједном извршити са којим инструкцијама, и које функционалне јединице могу извршити које инструкције. Овде такође постоје слични проблеми као и са проточном обрадом, и компилатор их исто тако разрешава.
- Архитектура машине
- Величина и тип кеша (cache) : Технике као inline expansion и loop unrolling могу повећати величину излазног кода а смањити размештеност кода. Програм се драстично успорава ако на пример унутрашња петља одједном не може да стане у кеш.
- Брзина преноса Кеша/Меморије : Дају компилатору наговештај о последицама грешака. Ово се већином користи у специјализованим апликацијама
Намена генерисаног кода уреди
- Дебаговање (Дебуггинг, Требљење)
Када програмер пише апликацију, он ће рекомпајлирати и тестирати веома често, па тако компилација мора да буде брза. Ово је један од разлога зашто се већина оптимизација не примењује у току дебаговања. Такође неке оптимизације као на пример оне које мењају редослед инструкција у коду могу отежају идентификацију излазног кода са бројевима линија изворног кода. Ово може да збуни и алате за дебаговање као и самог програмера који их користи.
- Генерална намена
Од унапред упакованог софтвера се очекује да може да се изврши на разним машинама и процесорима који могу да имају исти скуп инструкција, али имају другачије карактеристике кеша или меморије. Тако да код није наштимован да најбоље ради на неком одређеном процесору, или мозе да ради добро на најпопуларнијим процесорима, а на осталима задовољавајуће.
- Специјална намена
Ако је софтвер компајлиран за коришћење на једној или неколико сличних машина, са унапред познатим карактеристикама, онда компилатор може одлично да наштимује код за те машине. Битни специјални случајеви укључују код намењен за паралелне и векторске процесоре.
Технике оптимизације уреди
Уобичајене теме уреди
- Оптимизација уобичајеног случаја
Уобичајен случај може имати јединствена својства која дозвољавају брз пут уместо спорог пута. Ако се најчешће узме брз пут, резултат је бољи укупан учинак.
- Избегавање сувишности
Поновно коришћење резултата који су већ израчунати и чување истих за касније, уместо поновног израчунавања.
- Мање кода
Избацивање бескорисних израчунавања и међувредности. Мање посла за процесор, кеш, меморију је обично брже.
- Праволонијски код, са мање скокова
Мање компликован код. Скокови ометају припрему инструкција, и тиме успоравају код.
- Положај
Код и подаци којима се приступа у малим временским размацима требају да стоје и близу у меморији да би повећали просторни положај референци.
- Коришћење хијерархије меморије
Приступ меморији све више кошта са растом нивоа хијерархије меморије, тако да се најчешће коришћени ајтеми прво стављају у регистре, онда у кеш, па у главну меморију, и тек на крају на диск.
- Паралелизовање
Размештање операција тако да се омогући њихово паралелно израчунавање, било на нивоу инструкције, меморије, или нити.
- Прецизније информације су боље
Што прецизније информације компилатор има, то ће боље употребити технике оптимизације.
Технике оптимизације уреди
Оптимизација петље уреди
Технике које су дизајниране да углавном раде на петљама су :
- Индукцијска анализа променљивих (induction variable analysis)
Ако је променљива у петљи једноставна функција индексиране променљиве, као на пример j:=4*i+1, може се прописно обновити сваки пут када се променљива петље промени. Ово је редукција снаге (strength reduction), и такође дозвољава да дефиниције индексираних променљивих постану мртав код (dead code). Ова информација је такође корисна за bounds-checking елиминацију и анализу зависности (dependence analysis).
- Дељење петље (loop fission)
Дељење петље покушава да разбије петљу на више петљи истог асортимана индекса али да свака узме само део тела првобитне петље. Ово може побољшати положај референци података којима се приступа у петљи као и кода саме петље.
- Комбиновање петљи (loop fusion)
Још једна техника која покушава да смањи overhead петље. Када две оближње петље имају исти број итерација, њихова тела се могу комбиновати доклегод не праве референце једни другима на податке.
Ова техника мења стандардну while петљу у do while (repeat until) петљу умотану у иф кондиционал, смањујући број скокова за два. Тиме такође дуплира проверу услова, али је ефикаснија с обзиром да скокови обично доводе до застоја проточне обраде. Приде ако је услов познат за време компајлирања и зна се да неће довести до неких споредних ефеката, иф се може прескочити.
Ове оптимизације замењују унутрашње са спољашњим петљама. Када се променљиве индексирају у низ побољашава се положај референци.
Ако је резултат неког израчунавања исти у сваком пролазу кроз петљу, онда се то израчунавање може извући и испред петље, и тиме много повећа ефикасност кода.
Неки алгоритми попут множења матрица који слабо користе кеш, а имају прекомеран број приступа меморији. Овом оптимизацијом се повећава број приступа кешу тако што се операције раде по мањим блоковима користећи оптимизацију измена петље.
Обртање петље обрће редослед у којем су вредности додељене индексираним променљивима. Ово је префињена оптимизација која помаже елиминисању зависности, чиме омогућава употребу других оптимизација.
Одмотавање дуплира тело петље више пута у намери да смањи број тестирања услова петље, и броја скокова, који смањују перформансе оштећујући проточну обраду инструкција. Комплетно одмотавање петље елиминише сав overhead, али тражи да се зна број итерација унапред.
Цепање петље покушава да упрости петљу или елиминише зависности тако што разбија петљу на више мањих које имају исто тело, али врше итерацију на различитим деловима ланца индекса.
- unswitch-овање петље
Помера услове из унутрашњости петље ван петље тако што дуплира петљино тело унутар сваке if и else клаузуле.
Петља је реконструисана тако што се посао урађен у једној итерацији дели на неколико делова који се раде у неколико итерација. У тесној петљи ова техника сакрива кашњење између учитавања и коришћења вредности.
Оптимизације тока података data-flow уреди
Ове оптимизације, базиране на анализи тока података, примарно зависе од тога како се поједине особине података умножавају контролном ивицом у control flow графику. Неке од њих су :
У изразу "(а+б)-(а+б)/4" ово се односи на елиминацију дуплог (а+б) тако што га компилатор рачуна само једном.
- Слагање константи (constant folding and propagation)
Замена израза који се састоје од константи њиховим резултатом (на пример 1+2 са 3).
У присуству показивача тешко је урадити било какву оптимизацију. Спецификацијом који показивач показује на коју променљиву се онда неповезани показивачи могу игнорисати.
SSA базиране оптимизације уреди
Ове оптимизације су намењене за рад са програмима трансформисаним у специјалну форму звану static single assignment (SSA), у којој је свака променљива додељена на само једном месту. Неке од њих су :
Елиминише сувишности конструишући график вредности програма, онда одређује које вредности су израчунате истим изразима. Ова оптимизација идентификује и неке ствари које елиминација обичних подизраза не може, и обрнуто.
- Ретко условно слагање константи
Је еквивалентно узастопном понављању слагања константи, и елиминацији мртвог кода све док више нема промена.
Оптимизације генератора кода уреди
Најчешће коришћене променљиве требају да се чувају у процесорским регистрима због најбржег приступа. А да би се сазнало које су то променљиве конструише се график интерференције.
Већина архитектура, нарочито ЦИСЦ архитектуре, и оне које имају више модова адресирања, нуде више различитих начина за извођење једне неке операције користећи потпуно различите низове инструкција. Ова оптимизација бира инструкције које ће најбоље одрадити посао.
Ово је битна оптимизација за модерне процесоре са проточном обрадом, која избегава застоје и мехуриће у проточној обради тако што сакупља инструкције без зависности, док пажљиво очувава оригиналну семантику.
Базирана на целобројном линеарном програмирању, реструктурира компилаторово побољшавање положаја података и побољшава паралелизам реорганизујући израчунавања.
Оптимизације функционалног језика уреди
Иако се користи и на нефункционалне језике, потиче, а и највише се користи у функционалним језицима као на пример језику Lisp.
Репно рекурзивни алгоритми могу се претворити у итерацију, која је знатно бржа.
С обзиром на начин на који су структуре података спецификоване у функционалним језицима, могуће је комбиновати неколико рекурзивних функција које производе и користе привремене структуре података, тако да се подаци прослеђују директно без губљења времена на конструисање структура података.
Неке друге оптимизације уреди
Многи модерни језици, на пример Java, примењују проверу граница свих приступа низовима. Ово лоше утиче на перформансе. Ова оптимизација дозвољава компилатору да уклони неке провере граница, када може да одреди да је индекс у границама, на пример ако је то обична променљива петље.
- Оптимизација изданака гране (Branch offset)
Бира најкраћи пут до циља у неком дрвету.
Одстрањује наредбе које не утичу на понашање програма. Ово смањује дужину кода и избацује непотребна рачунања.
Ако се неки израз ради и када је услов испуњен и кад није, може се изоставити испитивање услова. Слично ако се неки типови израза појављују унутар петље, могу се померити и испред ако нема разлога да се изврше једном или више пута.
Када неки код позове процедуру могуће је директно убацити тело процедуре унутар позивног кода. Овиме се дозвољавају разне друге оптимизације, али се користи више простора.
- Повезивање скокова
Када се у пролазу кроз условно гранање скочи на код са истим, или супротним условом, може се наставити даље.
Подразумева замену комплексних, тешких, или скупих операција неким једноставнијим.
Преуређивање дрвета израза тако да се минимизирају ресурси потребни за израчунавање израза
Ако имамо више тестова који су услов за нешто прво се проверавају једноставнији. Ово може да се примени једино ако тестови не зависе један од другог.
Интерпроцедуралне оптимизације уреди
Интерпроцедуралне оптимизације раде на целом програму. Неке од њих су горе набројане. Користе их сви модерни комерцијални компилатори, мада не без корисниковог избора јер оне троше доста времена и простора.
Проблеми са оптимизацијама уреди
Раније су ручно одрађене оптимизације биле боље од оптимизација компилатора, али како су се технологије компилатора побољшале, добри компилатори боље оптимизују него програмери. за RISC архитектуру процесора, а чак и више за VLIW хардвер, оптимизација компилатора је кључ за добијање ефикасног кода, зато што су скупови RISC инструкција тако компактни да је тешко човеку да ручно организује или комбинује ситне инструкције да би добио боље резултате. Како год, оптимизације компилатора нису никако савршене. Ни један компилатор не може да гарантује да је за сваки изворни код најбољи еквивалент излазни код. Такав компилатор је немогуће направити јер би он решио проблем стајања (halting problem). Ово се може доказати помоћу функције foo(). Ова функција не враћа ништа и не ради ништа са стране. Најбржи еквивалент програма био би једноставно елиминација позива функције. С друге стране ако функција foo() не враћа ништа, онда би програм са позивом те функције био различит од програма без позива. Додатно, постоје и многи други пробелим са технологијом оптимизације компилатором:
- Обично оптимизујући компилатор ради само мале промене на малим скуповима операција. То значи да велике неефикасности изворног програма остају нетакнуте.
- Компилатор обично ради само са малим деловима целог програма одједном, тако да не може да размотри неке битне контекстне инфоррмације.
- Сваки додатни посао троши време. Оптимизација целог програма има велику цену.
- Интеракција фаза оптимизације компилатора: које комбинације оптимизација и у које време свака треба да буде примењена, и колико пута.
Посао побољшања технологија оптимизације се наставља. Један од приступа је такозвана оптимизација после пролаза. Она узима извршни програм па га оптимизује даље. То је добро зато што она ради оптимизације на асемблерском језику. Мада они су такође ограничени чињеницом да је много информација нађених у изворном коду изгубљено.
С обзиром да перформансе процесора расту све више и више сад се тежи ка оптимизацији коришћења меморије на рачун брзине.
Листа оптимизација компилатора уреди
- Аутоматска паралелизација
- Слагање константи
- Поједностављање алгебре
- Бројање вредности
- Умножавање копија
- Умножавање константи
- Елиминација простих подизраза
- Делимична елиминација сувишности
- Елиминација мртвог кода
- Редукција снаге
- Оптимизација петљи
- Проточна обрада софтвера
- Генерисање кода
- Векторизација
- Наређивање у етапама