Interproceduralna optimizacija
Interproceduralna optimizacija (IPO) je skup tehnika kompilatora koji se koriste u programiranju za poboljšanje performansi u programima koji sadrže mnoge najčešće korišćene funkcije male ili srednje dužine. IPO se razlikuje od ostalih kompilatora optimizacije, jer analizira ceo program; druge optimizacije gledaju samo jednu funkciju, ili čak jedan blok koda.
IPO nastoji da smanji ili eliminiše duplikate kalkulacije, neefikasno korišćenje memorije, kao i da pojednostavi iterativne sekvence kao što su petlje. Ako postoji poziv na drugu rutinu koja se odvija unutar petlje, IPO analiza može utvrditi da je najbolje da se uradi redno proširenje za to. Pored toga, IPO može da ponovi rutine za bolji izgled memorije i lokaliteta.
IPO može obuhvatiti i tipične kompilatore optimizacije na nivou celog programa, na primer, eliminacija mrtvog koda, koja uklanja kod koji se nikada ne izvršava. Da bi se to postiglo, kompilator testira grane koje se nikad ne preduzimaju i otklanja kod u toj grani. IPO takođe pokušava da obezbedi bolje korišćenje konstanti. Moderni kompilatori nude IPO kao opciju kod kompiliranja. Stvarni IPO proces se može desiti na svakom koraku između izvornog koda koji je čitljiv i proizvodnje gotovog izvršnog binarnog programa.
Ceo program optimizacije je optimizacija kompilatora programa koja koristi informacije o svim modulima u programu. Normalno, optimizacije se izvode po modulu; ali ovaj pristup, iako je lakši za pisanje i testiranje i manje zahteva resursa u toku same kompilacije, ne dozvoljava preciznost o bezbednosti jednog broja optimizacija kao što su agresivno redno proširenje i na taj način ne mogu da ih obavljaju čak iako bi se zapravo ispostavili dobici u efikasnosti koji ne menjaju semantiku emitovanog koda objekta.
Link vremena optimizacije je vrsta optimizacije programa koju vrši kompilator na programu u vreme linka. Vreme linka optimizacije je relevantno u programskim jezicima koji sastavljaju programe po principu file-by-file, a zatim povezuju ove fajlove zajedno (kao što su S i Fortran), pre nego odjednom (kao što su Javina "Just in time" (JIT) kompilacija).
Kada su svi fajlovi sastavljeni odvojeno u predmetima datoteke, kompilator veza (spaja) predmet datoteka u jednu datoteku, izvršnu. Kao što je u procesu rada ovog (ili odmah nakon toga) kompilator sa vremenom linka mogućnosti optimizacije mogu da se prijave različiti oblici interproceduralne optimizacije za novo napravljeni fajl. Proces spajanja datoteke može da ukloni ograničenja znanja koja su se dogodila u ranijim fazama kompilacije, omogućavajući dublje analize, više optimizacije, i na kraju bolje performanse programa.
Analiza[uredi | uredi izvor]
Cilj svake optimizacije je da ima program koji će raditi što je brže moguće; problem je u tome što nije moguće za kompilatora da ispravno analizira program i utvrdi šta *će* uraditi, a još manje šta je programer * naumio* za to da uradi. Nasuprot tome, programeri počinju na drugom kraju sa ciljem, i pokušajavaju da naprave program koji će ga ostvariti, poželjno bez puno razmišljanja u procesu.
Iz raznih razloga, uključujući i čitljivost, programi su često razbijeni u velikom broju postupaka, koji rukuju sa nekoliko opštih predmeta. Međutim, opštost svakog postupka može dovesti do izgubljenog napora u određenim upotrebama. Interproceduralna optimizacija predstavlja pokušaj da se smanji otpad.
Pretpostavimo da postoji procedura koja procenjuje F(x), a kod zahteva rezultat F(6) i kasnije, F(6)ponovo. Ova druga procena je gotovo sigurno nepotrebna: rezultat je mogao umesto da bude sačuvan i da se odnosio na kasnije, da pretpostavlja da je F čista funkcija. Ova jednostavna optimizacija je osujećena onog trenutka kada implementacija F(x) postaje nečista; to jest, njeno izvršenje podrazumeva pozivanje pomoću parametara osim eksplicitnog argumenta 6 koji se promenio od poziva, ili sporednih efekata, kao što su štampanje neke poruke u dnevniku, računajući broj evaluacija, koje gomilaju trošenje vremena procesora, pripremanje interne tabele tako da će nakon prizivanja srodnih parametara biti olakšano, i tako dalje. Gubljenje ovih sporednih efekata bez evaluacije drugi put može biti prihvatljivo, ili ne.
Uopšteno govoreći, pored optimizacije, drugi razlog za korišćenje procedure je da se izbegne dupliranje koda koji će proizvesti iste rezultate, ili gotovo iste rezultate, svaki put kada se operacija izvodi. Opšti pristup optimizaciji stoga bi da preokrene ovo: neka ili svaka pozivanja na određene procedure su zamenjena odgovarajućim kodom, sa parametrima odgovarajućih zamena. Kompilator će onda pokušati da optimizuje rezultat.
Primer[uredi | uredi izvor]
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;
Ako parametri za Silly donose vrednost, akcije postupka nemaju uticaja na originalne pormenljive, a pošto Silly ne čini ništa u svojoj okolini (čita se iz datoteke, pišu se u fajl, menjaju se globalne promenljive kao što je b, itd .) njen kod i sva prizivanja mogu biti optimizovana daleko u potpunosti, ostavljajući vrednost nedefinisanu (koja nema veze), tako da samo izjave print ostanu, a oni za konstantne vrednosti.
Ako su parametri prošli pozivanjem prolaznih refernci, onda akcije na njih u Silly zaista utiču na originale. Ovo se obično radi slanjem adrese mašina parametara u postupku prilagođavanja, tako da su postupci u originalnom skladišnom prostoru. Tako je u predmetu poziva referenci, procedura Silly ima efekat. Pretpostavimo da su njena prizivanja proširena na mestu, sa parametrima koji su identifikovani pomoću adrese: kod iznosi
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, плус коришћење глобалне.
Kompilator bi onda u ovom veoma malom primeru sledio konstante duž logike (kao što jeste) i smatrao da su predikati if-izjave konstantni i tako dalje ...
x:=7; b:=5; a:=-6; print 7; %b није реферисано x:=-1; print -1; %b јесте реферисано... b:=-6; print -6; %b модификовано је.
A pošto zadataka na a, b i x ne daju ništa sa spoljnim svetom - oni se ne pojavljuju u izlaznim izjavama, ni kao ulaz u narednim proračunima (čiji rezultati zauzvrat ne dovode do izlaza, ili su nepotrebni) - nema nikakvog smisla u ovom kodu, pa je rezultat
print 7; print -1; print -6;
Metod varijante za donošenje prolaznih parametara koji izgleda kao "prolazna refernca" je copy-in, copy-out pri čemu postupak radi na lokalnu kopiju parametara čije vrednosti se kopiraju nazad u originalu na izlazu iz procedure. Ako postupak ima pristup istom parametru, ali na različite načine, kao što su Silly(a,a) ili Silly(a,b), razlike mogu nastati. Dakle, ako su parametri prošli od kopiranja u i van u redu levo-desno onda bi Silly(b,b) se proširila u
p1:=b; p2:=b; %Копирање. Локалне променљиве p1 и p2 су једнаке. if p2 < 0 then p1:=p2 + b else p1:=-6; %Онда p1 није више једнако p2. b:=p1; b:=p2; %Копирање. Слева надесно, вредност p1 се мења.
I u ovom slučaju, kopiranje vrednost p1 (koja je promenjena) u b je besmisleno, jer je odmah prepisana vrednost p2, čija vrednost nije modifikovana u postupku iz prvobitne vrednosti b, i tako treća izjava postaje
print 5; %Није -6
Takve razlike u ponašanju će verovatno izazvati zbunjenost, pogoršana pitanjima kao na poredak u kojem se parametri kopiraju: da li će biti sleva nadesno na izlazu kao i na ulazu? Ovi detalji verovatno nisu pažljivo objašnjeni u uputstvu kompilatora, a ako jesu, verovatno će biti doneti preko kao da nisu relevantni za neposredni zadatak i davno zaboravljeni u trenutku predstavljanja problem nastaje. Ako (kao što je verovatno) privremene vrednosti se pružaju preko šeme na stek za skladištenje, onda je verovatno da će se proces kopiranja vratiti u obrnutom redosledu na kopiji, što bi u ovom primeru značilo da će p1 će biti poslednja vrednost koja se vraća u b.
Proces proširenja procedure in-line ne treba posmatrati kao varijantu tekstualne zamene (kao u makro ekspanziji), jer greške sintakse mogu nastati kao kada su parametri izmenjeni i posebno pozivani da koriste konstante kao parametre. Zato je važno da budemo sigurni da li se konstante napajaju kao parametri koji neće imati njihovu vrednost (konstante mogu biti u memoriji kao promenljive) i koji idu naopako, uobičajena tehnika za kompilatora za generisanje koda je kopiranje vrednosti iz stalnog u privremene promenljive čije adrese su prošle u postupku, a ako se njegova vrednost menja, bez obzira; nikada se ne kopira nazad u lokaciju konstante.
Drugačije rečeno, pažljivo napisan program testiranja može prijaviti da li parametri donose vrednosti ili reference, a ako se koristi copy-in and copy-out šema. Međutim, varijacija je beskrajna: jednostavni parametri mogu biti doneti od strane kopija, dok veliki agregati kao što su nizovi mogu biti doneti po referenci; jednostavne konstante kao što su nule mogu biti generisane od strane specijalnih kodova mašina (kao što su Clear ili LoadZ), dok se složenije konstante mogu čuvati u memoriji označene samo za čitanje sa svakim pokušajem menjanja koji ga rezultira trenutnim raskidom programa, itd.
Generalno[uredi | uredi izvor]
Ovaj primer je krajnje jednostavan, iako su komplikacije već očigledne. Verovatnije da će biti slučaj mnogih postupaka, koji imaju različite izvodljive ili proglašene osobine od strane programera koje mogu omogućiti optimizaciju kompilatora da pronađu neku prednost. Svaki parametar za postupak može se pročitati samo, napisan onda je može da se čita i piše, ili da se potpuno ignoriše što dovodi do mogućnosti, kao što su konstante kojima nije potrebna zaštita preko privremenih promenljivih, ali ono što se dešava u svakom prizivanju može dobro zavisiti od kompleksa veb razmatranja. Ostali postupci, procedure naročito funkcije koje imaju određena ponašanja da u određenim prizivanjima mogu omogućiti neki posao koji treba izbegavati: na primer, Gama funkcija, ako se poziva sa parametra celobrojne vrednosti, može se pretvoriti u obračun koji uključuje celobrojne faktorijale.
Neki računarski jezici omogućuju (ili čak zahtevaju) tvrdnje za upotrebu parametara, i možda dodatno nude mogućnost da se izjasni da su promenljive njihove vrednosti ograničen na neki skup (na primer, 6 <h ≤ 28) čime se obezbeđuje dodatno mnoštvo za proces optimizacije da ide kroz, kao i pružanje vrednih provera na koherentnost izvornog koda otkrivanja grešaka. Ali to nikada nije dovoljno - samo neke promenljive mogu dati jednostavna ograničenja, dok druge zahtevaju složene specifikacije: kako bi to moglo biti precizirano da promenljiva P da bude prost broj, i ako jeste, jeste ili nije vrednost 1 uključena? Komplikacije su neposredne: šta su validni rasponi za dan, za mesec D imajući u vidu da je M broj meseci? I sve su to prekršaji dostojni neposrednog raskida? Čak i ako sa svim tim može da se rukuje, koja korist bi mogla da usledi? A po kojoj ceni? Specifikacije bi dovele do ponovnog podatka o funkciji programa u drugom obliku i obradile bi ih, na taj način će biti predmet grešaka. Umesto toga, samo jednostavne specifikacije mogu biti sa run-time opsega provere obezbeđene.
U slučajevima kada program čita da nema ulaza (kao u primeru), mogla bi se zamisliti analiza kompilatora kako sprovodi napred, tako da rezultat neće biti više od niza štampanih izjava ili eventualno neke petlje celishodno generisane takve vrednosti. Da li bi to onda priznalo program za generisanje prostih brojeva, i pretvorilo u najpoznatije metode za to, ili sadašnje, umesto referencu u biblioteku? Malo verovatno! U principu, proizvoljno složene okolnosti nastaju (u Entscheidungsproblem) da spreče ovo, i ne postoji opcija da pokrenete kod sa ograničenim poboljšanjima.
Istorija[uredi | uredi izvor]
Za procedural, ili jezike poput Algola, interproceduralna analiza i optimizacija izgleda kao da je ušao u komercijalnu praksu u ranim 1970-ih. IBM-ov PL/I kompilator optimizacije obavlja interproceduralnu analizu da razume neželjena dejstva oba postupka poziva i izuzetaka (u PL/I uslovima kao i "pod uslovima")[1] i u papirima Fran Alen.[2][3] Rad na kompilaciji APL programskog jezika je, iz nužde, interproceduralan.[4][5]
Tehnike interproceduralne analize i optimizacije bili su predmet akademskih istraživanja u 1980 i 1990. Oni su se ponovo pojavili u komercijalnom svetu kompilatora u ranim 1990-im sa kompilatorima iz oba Convex (na "zahtev kompilatora" za Convex S4) i od Ardent (kompilator za Ardent Titan). Ovi kompilatori su pokazali da tehnologija može biti dovoljno brza da bude prihvatljiva u komercijalnom komapjliranju; potom interproceduralne tehnike su se pojavile u velikom broju komercijalnih i nekomercijalnih sistema.
Implementacija i zastave[uredi | uredi izvor]
Intelovi C/C++ kompilatori omogućavaju ceo program IPO. Zastava koja omogućuje interproceduralnu optimizaciju za jedan fajl je -ip, zastava omogućuje interproceduralnu optimizaciju u svim fajlovima u programu je -ipo.[6][7]
GNU GCC kompilator ima funkciju inlining, koja je podrazumevano uključena u -O3, a može se uključiti ručno preko donošenja prekidača (-finline-functions) u kompajliranja.[8] GCC verzija 4.1 ima novu infrastrukturu za interproceduralnu optimizaciju.[9]
Takođe GCC ima opciju za IPO: <i>-fwhole-program --combine</i>.
Majkrosoft Visual S++, integrisan u Visual Studio, takođe podržava interproceduralnu optimizaciju.[10]
GNU GCC i Jeka kompilatori podržavaju IPO na nivou optimizacije -flto.
Vidi još[uredi | uredi izvor]
Reference[uredi | uredi izvor]
- ^ 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" Arhivirano na sajtu Wayback Machine (21. septembar 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" Arhivirano na sajtu Wayback Machine (8. april 2008).