Интерпроцедурална оптимизација
Интерпроцедурална оптимизација (ИПО) је скуп техника компилатора који се користе у програмирању за побољшање перформанси у програмима који садрже многе најчешће коришћене функције мале или средње дужине. ИПО се разликује од осталих компилатора оптимизације, јер анализира цео програм; друге оптимизације гледају само једну функцију, или чак један блок кода.
ИПО настоји да смањи или елиминише дупликате калкулације, неефикасно коришћење меморије, као и да поједностави итеративне секвенце као што су петље. Ако постоји позив на другу рутину која се одвија унутар петље, ИПО анализа може утврдити да је најбоље да се уради редно проширење за то. Поред тога, ИПО може да понови рутине за бољи изглед меморије и локалитета.
ИПО може обухватити и типичне компилаторе оптимизације на нивоу целог програма, на пример, елиминација мртвог кода, која уклања код који се никада не извршава. Да би се то постигло, компилатор тестира гране које се никад не предузимају и отклања код у тој грани. ИПО такође покушава да обезбеди боље коришћење константи. Модерни компилатори нуде ИПО као опцију код компилирања. Стварни ИПО процес се може десити на сваком кораку између изворног кода који је читљив и производње готовог извршног бинарног програма.
Цео програм оптимизације је оптимизација компилатора програма која користи информације о свим модулима у програму. Нормално, оптимизације се изводе по модулу; али овај приступ, иако је лакши за писање и тестирање и мање захтева ресурса у току саме компилације, не дозвољава прецизност о безбедности једног броја оптимизација као што су агресивно редно проширење и на тај начин не могу да их обављају чак иако би се заправо испоставили добици у ефикасности који не мењају семантику емитованог кода објекта.
Линк времена оптимизације је врста оптимизације програма коју врши компилатор на програму у време линка. Време линка оптимизације је релевантно у програмским језицима који састављају програме по принципу file-by-file, а затим повезују ове фајлове заједно (као што су С и Фортран), пре него одједном (као што су Јавина "Just in time" (JIT) компилација).
Када су сви фајлови састављени одвојено у предметима датотеке, компилатор веза (спаја) предмет датотека у једну датотеку, извршну. Као што је у процесу рада овог (или одмах након тога) компилатор са временом линка могућности оптимизације могу да се пријаве различити облици интерпроцедуралне оптимизације за ново направљени фајл. Процес спајања датотеке може да уклони ограничења знања која су се догодила у ранијим фазама компилације, омогућавајући дубље анализе, више оптимизације, и на крају боље перформансе програма.
Анализа[уреди | уреди извор]
Циљ сваке оптимизације је да има програм који ће радити што је брже могуће; проблем је у томе што није могуће за компилатора да исправно анализира програм и утврди шта *ће* урадити, а још мање шта је програмер * наумио* за то да уради. Насупрот томе, програмери почињу на другом крају са циљем, и покушајавају да направе програм који ће га остварити, пожељно без пуно размишљања у процесу.
Из разних разлога, укључујући и читљивост, програми су често разбијени у великом броју поступака, који рукују са неколико општих предмета. Међутим, општост сваког поступка може довести до изгубљеног напора у одређеним употребама. Интерпроцедурална оптимизација представља покушај да се смањи отпад.
Претпоставимо да постоји процедура која процењује F(x), а код захтева резултат F(6) и касније, F(6)поново. Ова друга процена је готово сигурно непотребна: резултат је могао уместо да буде сачуван и да се односио на касније, да претпоставља да је F чиста функција. Ова једноставна оптимизација је осујећена оног тренутка када имплементација F(x) постаје нечиста; то јест, њено извршење подразумева позивање помоћу параметара осим експлицитног аргумента 6 који се променио од позива, или споредних ефеката, као што су штампање неке поруке у дневнику, рачунајући број евалуација, које гомилају трошење времена процесора, припремање интерне табеле тако да ће након призивања сродних параметара бити олакшано, и тако даље. Губљење ових споредних ефеката без евалуације други пут може бити прихватљиво, или не.
Уопштено говорећи, поред оптимизације, други разлог за коришћење процедуре је да се избегне дуплирање кода који ће произвести исте резултате, или готово исте резултате, сваки пут када се операција изводи. Општи приступ оптимизацији стога би да преокрене ово: нека или свака позивања на одређене процедуре су замењена одговарајућим кодом, са параметрима одговарајућих замена. Компилатор ће онда покушати да оптимизује резултат.
Пример[уреди | уреди извор]
Program example; integer b; %A променљива "global" процедуре Silly. Procedure Silly(a,x) if x < 0 then a:=x + b else a:=-6; End Silly; %Односи се на b, не a параметар, онда је Silly "impure" генерално. integer a,x; %Ове променљиве су видљиве Silly. x:=7; b:=5; Silly(a,x); Print x; Silly(x,a); Print x; Silly(b,b); print b; End example;
Ако параметри за Silly доносе вредност, акције поступка немају утицаја на оригиналне порменљиве, а пошто Silly не чини ништа у својој околини (чита се из датотеке, пишу се у фајл, мењају се глобалне променљиве као што је b, итд .) њен код и сва призивања могу бити оптимизована далеко у потпуности, остављајући вредност недефинисану (која нема везе), тако да само изјаве print остану, а они за константне вредности.
Ако су параметри прошли позивањем пролазних рефернци, онда акције на њих у Silly заиста утичу на оригинале. Ово се обично ради слањем адресе машина параметара у поступку прилагођавања, тако да су поступци у оригиналном складишном простору. Тако је у предмету позива референци, процедура Silly има ефекат. Претпоставимо да су њена призивања проширена на месту, са параметрима који су идентификовани помоћу адресе: код износи
x:=7; b:=5; if x < 0 then a:=x + b else a:=-6; print x; %a је промењено. if a < 0 then x:=a + b else x:=-6; print x; %Зато што су параметри замењени. if b < 0 then b:=b + b else b:=-6; print b; %Две верзије променљиве b у Silly, плус коришћење глобалне.
Компилатор би онда у овом веома малом примеру следио константе дуж логике (као што јесте) и сматрао да су предикати if-изјаве константни и тако даље ...
x:=7; b:=5; a:=-6; print 7; %b није реферисано x:=-1; print -1; %b јесте реферисано... b:=-6; print -6; %b модификовано је.
А пошто задатака на a, b и x не дају ништа са спољним светом - они се не појављују у излазним изјавама, ни као улаз у наредним прорачунима (чији резултати заузврат не доводе до излаза, или су непотребни) - нема никаквог смисла у овом коду, па је резултат
print 7; print -1; print -6;
Метод варијанте за доношење пролазних параметара који изгледа као "пролазна рефернца" је copy-in, copy-out при чему поступак ради на локалну копију параметара чије вредности се копирају назад у оригиналу на излазу из процедуре. Ако поступак има приступ истом параметру, али на различите начине, као што су Silly(a,a) или Silly(a,b), разлике могу настати. Дакле, ако су параметри прошли од копирања у и ван у реду лево-десно онда би Silly(b,b) се проширила у
p1:=b; p2:=b; %Копирање. Локалне променљиве p1 и p2 су једнаке. if p2 < 0 then p1:=p2 + b else p1:=-6; %Онда p1 није више једнако p2. b:=p1; b:=p2; %Копирање. Слева надесно, вредност p1 се мења.
И у овом случају, копирање вредност p1 (која је промењена) у b је бесмислено, јер је одмах преписана вредност p2, чија вредност није модификована у поступку из првобитне вредности b, и тако трећа изјава постаје
print 5; %Није -6
Такве разлике у понашању ће вероватно изазвати збуњеност, погоршана питањима као на поредак у којем се параметри копирају: да ли ће бити слева надесно на излазу као и на улазу? Ови детаљи вероватно нису пажљиво објашњени у упутству компилатора, а ако јесу, вероватно ће бити донети преко као да нису релевантни за непосредни задатак и давно заборављени у тренутку представљања проблем настаје. Ако (као што је вероватно) привремене вредности се пружају преко шеме на стек за складиштење, онда је вероватно да ће се процес копирања вратити у обрнутом редоследу на копији, што би у овом примеру значило да ће p1 ће бити последња вредност која се враћа у b.
Процес проширења процедуре in-line не треба посматрати као варијанту текстуалне замене (као у макро експанзији), јер грешке синтаксе могу настати као када су параметри измењени и посебно позивани да користе константе као параметре. Зато је важно да будемо сигурни да ли се константе напајају као параметри који неће имати њихову вредност (константе могу бити у меморији као променљиве) и који иду наопако, уобичајена техника за компилатора за генерисање кода је копирање вредности из сталног у привремене променљиве чије адресе су прошле у поступку, а ако се његова вредност мења, без обзира; никада се не копира назад у локацију константе.
Другачије речено, пажљиво написан програм тестирања може пријавити да ли параметри доносе вредности или референце, а ако се користи copy-in and copy-out шема. Међутим, варијација је бескрајна: једноставни параметри могу бити донети од стране копија, док велики агрегати као што су низови могу бити донети по референци; једноставне константе као што су нуле могу бити генерисане од стране специјалних кодова машина (као што су Clear или LoadZ), док се сложеније константе могу чувати у меморији означене само за читање са сваким покушајем мењања који га резултира тренутним раскидом програма, итд.
Генерално[уреди | уреди извор]
Овај пример је крајње једноставан, иако су компликације већ очигледне. Вероватније да ће бити случај многих поступака, који имају различите изводљиве или проглашене особине од стране програмера које могу омогућити оптимизацију компилатора да пронађу неку предност. Сваки параметар за поступак може се прочитати само, написан онда је може да се чита и пише, или да се потпуно игнорише што доводи до могућности, као што су константе којима није потребна заштита преко привремених променљивих, али оно што се дешава у сваком призивању може добро зависити од комплекса веб разматрања. Остали поступци, процедуре нарочито функције које имају одређена понашања да у одређеним призивањима могу омогућити неки посао који треба избегавати: на пример, Гама функција, ако се позива са параметра целобројне вредности, може се претворити у обрачун који укључује целобројне факторијале.
Неки рачунарски језици омогућују (или чак захтевају) тврдње за употребу параметара, и можда додатно нуде могућност да се изјасни да су променљиве њихове вредности ограничен на неки скуп (на пример, 6 <х ≤ 28) чиме се обезбеђује додатно мноштво за процес оптимизације да иде кроз, као и пружање вредних провера на кохерентност изворног кода откривања грешака. Али то никада није довољно - само неке променљиве могу дати једноставна ограничења, док друге захтевају сложене спецификације: како би то могло бити прецизирано да променљива P да буде прост број, и ако јесте, јесте или није вредност 1 укључена? Компликације су непосредне: шта су валидни распони за дан, за месец D имајући у виду да је М broj месеци? И све су то прекршаји достојни непосредног раскида? Чак и ако са свим тим може да се рукује, која корист би могла да уследи? А по којој цени? Спецификације би довеле до поновног податка о функцији програма у другом облику и обрадиле би их, на тај начин ће бити предмет грешака. Уместо тога, само једноставне спецификације могу бити са run-time опсега провере обезбеђене.
У случајевима када програм чита да нема улаза (као у примеру), могла би се замислити анализа компилатора како спроводи напред, тако да резултат неће бити више од низа штампаних изјава или евентуално неке петље целисходно генерисане такве вредности. Да ли би то онда признало програм за генерисање простих бројева, и претворило у најпознатије методе за то, или садашње, уместо референцу у библиотеку? Мало вероватно! У принципу, произвољно сложене околности настају (у Entscheidungsproblem) да спрече ово, и не постоји опција да покренете код са ограниченим побољшањима.
Историја[уреди | уреди извор]
За процедурал, или језике попут Алгола, интерпроцедурална анализа и оптимизација изгледа као да је ушао у комерцијалну праксу у раним 1970-их. IBM-ов PL/I компилатор оптимизације обавља интерпроцедуралну анализу да разуме нежељена дејства оба поступка позива и изузетака (у PL/I условима као и "под условима")[1] и у папирима Фран Ален.[2][3] Рад на компилацији APL програмског језика је, из нужде, интерпроцедуралан.[4][5]
Технике интерпроцедуралне анализе и оптимизације били су предмет академских истраживања у 1980 и 1990. Они су се поново појавили у комерцијалном свету компилатора у раним 1990-им са компилаторима из оба Convex (на "захтев компилатора" за Convex С4) и од Ardent (компилатор за Ardent Titan). Ови компилатори су показали да технологија може бити довољно брза да буде прихватљива у комерцијалном комапјлирању; потом интерпроцедуралне технике су се појавиле у великом броју комерцијалних и некомерцијалних система.
Имплементација и заставе[уреди | уреди извор]
Интелови C/C++ компилатори омогућавају цео програм IPO. Застава која омогућује интерпроцедуралну оптимизацију за један фајл је -ip, застава омогућује интерпроцедуралну оптимизацију у свим фајловима у програму је -ipo.[6][7]
GNU GCC компилатор има функцију inlining, која је подразумевано укључена у -О3, а може се укључити ручно преко доношења прекидача (-finline-functions) у компајлирања.[8] GCC верзија 4.1 има нову инфраструктуру за интерпроцедуралну оптимизацију.[9]
Такође GCC има опцију за IPO: <i>-fwhole-program --combine</i>.
Мајкрософт Visual С++, интегрисан у Visual Studio, такође подржава интерпроцедуралну оптимизацију.[10]
GNU GCC и Јека компилатори подржавају IPO на нивоу оптимизације -flto.
Види још[уреди | уреди извор]
Референце[уреди | уреди извор]
- ^ Thomas C. Spillman, "Exposing side effects in a PL/I optimizing compiler", in Proceedings of IFIPS 1971, North-Holland Publishing Company, pages 376-381.
- ^ Frances E. Allen, "Interprocedural Data Flow Analysis", IFIPS Proceedings, 1974.
- ^ Frances E. Allen, and Jack Schwartz, "Determining the Data Flow Relationships in a Collection of Procedures", IBM Research Report RC 4989, Aug. 1974.
- ^ Philip Abrams, "An APL Machine", Stanford University Computer Science Department, Report STAN-CS-70-158, February, 1970.
- ^ Terrence C. Miller, "Tentative Compilation: A Design for an APL Compiler", Ph.D. Thesis, Yale University, 1978.
- ^ "Intel compiler 8 documentation" Архивирано на сајту Wayback Machine (21. септембар 2006).
- ^ Intel Visual Fortran Compiler 9.1, Standard and Professional Editions, for Windows* - Intel Software Network
- ^ "GCC optimization options".
- ^ "GCC interprocedural optimizations".
- ^ "Visual Studio Optimization" Архивирано на сајту Wayback Machine (8. април 2008).