Optimizacija kompilatora je proces podešavnja izlaza kompilatora tako da se maksimiziraju ili minimiziraju neki atributi izvršnog programa, kao na primer minimizacija vremena izvršavanja programa, korišćenja memorije itd. Pokazano je da su neki kodovi optimizacije NP-kompletni problemi. U praksi faktori, kao na primer vreme potrebno da kompilator izvrši svoj zadatak, postavljaju gornju granicu optimizacije koju implementator kompilatora može dati. Takođe u prošlosti su ograničenja memorije bila glavni faktor u izboru optimizacije.

Tipovi optimizacije Tehnike optimizacije se mogu podeliti u nekoliko grupa koje utiču na bilo sta između jednog iskaza i celog programa. U principu lokalne tehnike se mnogo lakše implementiraju nego globalne ali zato i manje doprinose optimizaciji. Neki primeri grupa su:

-{Peephole}- optimizacija : Obično se izvršava posle prevođenja na mašinski jezik. Ova forma optimizacije ispituje nekoliko obližnjih instrukcija da vidi da li mogu biti zamenjene kraćim nizom instrukcija, kao na primer množenje brojem dva se može brže izvršiti šiftovanjem u levo.

Lokalne optimizacije : One samo uzimaju u obzir informacije koje su lokalne za neku funkciju. Ovo smanjuje količinu potrebne analize, ali znači da pretpostavke u najgorem slučaju moraju da se donesu kada dođe do poziva funkcije ili korišćenja globalnih promenjivih

Optimizacija celog programa : One analiziraju izvorni kod celog programa. Veća količina prikupljenih informacija znači da optimizacija može da bude mnogo efektivinija u poređenju sa optimizacijama zasnovanim na lokalnim informacijama. Ova vrsta optimizacije takođe dozvoljava korišćenje nekih drugih tehnika, kao na primer zamenu poziva funkcije celim telom funkcije

Optimizacija petlji (-{loop optimization}-) : One deluju na iskaze koji čine petlju, kao na primer -{for}- petlja. Ovakve optimizacije imaju veliki uticaj zato što su mnogi programi najviše vremena u svojim petljama.

Optimizacije koje zavise/ne zavise od programskog jezika : Većina jezika visokog nivoa ima slične programske konstrukcije (-{if, switch, case, for, while.... }-) , pa se tako i koriste slične tehnike optimizacije. Ipak neke karakteristike nekih programskih jezika čine neke optimizacije teško primenljivim. Na primer pokazivači u jezicima -{C}- i -{C++}- otežavaju optimizaciju nizova. Takođe neke karakteristike i olakšavaju upotrebu optimizacija.

Optimizacije koje zavise/ne zavise od mašine : Mnoge optimizacije koje rade na konceptima apstraktnog programiranja (petlje, objekti, strukture) ne zavise od mašine za koju je kompilator napravljen, ali mnoge najefikasnije optimizacije su one koje najbolje koriste specijalne mogućnosti odeređenih mašina.

Faktori koji utiču na optimizaciju

Mašina Izbor optimizacija koje mogu i trebaju da se urade umnogome zavisi od određene mašine. Ponekad je moguće parametarizovati neke faktore mašine, tako da se isti deo koda kompilatora moze koristiti na različitim mašinama samo izmenama opisnih parametara mašine. -{GCC}- je jedan takav kompilator

Arhitektura odabranog procesora (-{CPU-a}-)

Broj -{CPU}- registara : Veći broj registara omogućava lakšu optimizaciju. Lokalne promenljive se mogu čuvati u registrima a ne na steku. Takođe se i rezultati mogu ostaviti u registrima bez upisivanja i čitanja iz memorije.

-{RISC vs. CISC}- : Skupovi -{CISC}- instrukcija većinom imaju različite duzine instrukcija, ponekad i veći broj instrukcija koje se mogu iskoristiti, i svaka instrukcija može različito trajati. Skupovi -{RISC}- instrukcija pokušavaju da uklone te razlike (skupovi instrukcija su konstantne dužine, obično ima manje kombinacija operacija sa registrima i memorijom... ). Može postojati više načina za izvršavanje nekog zadatka, gde -{CISC}- obično daje više mogućnosti nego -{RISC}-. Kompilatori moraju da znaju relativne cene različitih instrukcija i da izaberu najbolji redosled instrukcija.

Protočna obrada () : Kompilatori mogu da rasporede tako da se zastoji protočne obrade (kada procesor gubi vreme dok čeka razrešavanje nekih konflikata, do kojih dolazi kada instrukcija na nekom nivou protočne obrade zavisi od rezultata druge instrukcije ispred nje, ali koja još nije završena) ređe dešavaju.

Broj funkcionalnih jedinica : Neki procesori imaju više -{ALU}--ove i -{FPR}--ova (-{Floating point unit}-). ovo im omogućava da izvrše nekoliko instrukcija odjednom. Takođe mogu postojati ograničenja u tome koje instrukcije se mogu odjednom izvršiti sa kojim instrukcijama, i koje funkcionalne jedinice mogu izvršiti koje instrukcije. Ovde takođe postoje slični problemi kao i sa protočnom obradom, i kompilator ih isto tako razrešava.

Arhitektura mašine

Veličina i tip keša (-{cache}-) : Tehnike kao -{inline expansion}- i -{loop unrolling}- mogu povećati veličinu izlaznog koda a smanjiti razmeštenost koda. Program se drastično usporava ako na primer unutrašnja petlja odjednom ne može da stane u keš.

Brzina prenosa Keša/Memorije : Daju kompilatoru nagoveštaj o posledicama grešaka. Ovo se većinom koristi u specijalizovanim aplikacijama

Namena generisanog koda

Debagovanje (Debugging, Trebljenje) Kada programer piše aplikaciju, on će rekompajlirati i testirati veoma često, pa tako kompilacija mora da bude brza. Ovo je jedan od razloga zašto se većina optimizacija ne primenjuje u toku debagovanja. Takođe neke optimizacije kao na primer one koje menjaju redosled instrukcija u kodu mogu otežaju identifikaciju izlaznog koda sa brojevima linija izvornog koda. Ovo može da zbuni i alate za debagovanje kao i samog programera koji ih koristi.

Generalna namena Od unapred upakovanog softvera se očekuje da može da se izvrši na raznim mašinama i procesorima koji mogu da imaju isti skup instrukcija, ali imaju drugačije karakteristike keša ili memorije. Tako da kod nije naštimovan da najbolje radi na nekom određenom procesoru, ili moze da radi dobro na najpopularnijim procesorima, a na ostalima zadovoljavajuće.

Specijalna namena Ako je softver kompajliran za korišćenje na jednoj ili nekoliko sličnih mašina, sa unapred poznatim karakteristikama, onda kompilator može odlično da naštimuje kod za te mašine. Bitni specijalni slučajevi uključuju kod namenjen za paralelne i vektorske procesore.

Tehnike optimizacije

Uobičajene teme

Optimizacija uobičajenog slučaja Uobičajen slučaj može imati jedinstvena svojstva koja dozvoljavaju brz put umesto sporog puta. Ako se najčešće uzme brz put, rezultat je bolji ukupan učinak.

Izbegavanje suvišnosti Ponovno korišćenje rezultata koji su već izračunati i čuvanje istih za kasnije, umesto ponovnog izračunavanja.

Manje koda Izbacivanje beskorisnih izračunavanja i međuvrednosti. Manje posla za procesor, keš, memoriju je obično brže.

Pravolonijski kod, sa manje skokova Manje komplikovan kod. Skokovi ometaju pripremu instrukcija, i time usporavaju kod.

Položaj Kod i podaci kojima se pristupa u malim vremenskim razmacima trebaju da stoje i blizu u memoriji da bi povećali prostorni položaj referenci.

Korišćenje hijerarhije memorije Pristup memoriji sve više košta sa rastom nivoa hijerarhije memorije, tako da se najčešće korišćeni ajtemi prvo stavljaju u registre, onda u keš, pa u glavnu memoriju, i tek na kraju na disk.

Paralelizovanje Razmeštanje operacija tako da se omogući njihovo paralelno izračunavanje, bilo na nivou instrukcije, memorije, ili niti.

Preciznije informacije su bolje Što preciznije informacije kompilator ima, to će bolje upotrebiti tehnike optimizacije.

Tehnike optimizacije Optimizacija petlje Tehnike koje su dizajnirane da uglavnom rade na petljama su :

Indukcijska analiza promenljivih (-{induction variable analysis}-) Ako je promenljiva u petlji jednostavna funkcija indeksirane promenljive, kao na primer -{j:=4*i+1}-, može se propisno obnoviti svaki put kada se promenljiva petlje promeni. Ovo je redukcija snage (-{strength reduction}-), i takođe dozvoljava da definicije indeksiranih promenljivih postanu mrtav kod (-{dead code}-). Ova informacija je takođe korisna za -{bounds-checking}- eliminaciju i analizu zavisnosti (-{dependence analysis}-).

Deljenje petlje (-{loop fission}-) Deljenje petlje pokušava da razbije petlju na više petlji istog asortimana indeksa ali da svaka uzme samo deo tela prvobitne petlje. Ovo može poboljšati položaj referenci podataka kojima se pristupa u petlji kao i koda same petlje.

Kombinovanje petlji (-{loop fusion}-) Još jedna tehnika koja pokušava da smanji -{overhead}- petlje. Kada dve obližnje petlje imaju isti broj iteracija, njihova tela se mogu kombinovati doklegod ne prave reference jedni drugima na podatke.

Inverzija petlje Ova tehnika menja standardnu -{while}- petlju u -{do while}- (-{repeat until}-) petlju umotanu u if kondicional, smanjujući broj skokova za dva. Time takođe duplira proveru uslova, ali je efikasnija s obzirom da skokovi obično dovode do zastoja protočne obrade. Pride ako je uslov poznat za vreme kompajliranja i zna se da neće dovesti do nekih sporednih efekata, if se može preskočiti.

Izmena petlje Ove optimizacije zamenjuju unutrašnje sa spoljašnjim petljama. Kada se promenljive indeksiraju u niz poboljašava se položaj referenci.

Pomeranje koda ne menjajući petlju Ako je rezultat nekog izračunavanja isti u svakom prolazu kroz petlju, onda se to izračunavanje može izvući i ispred petlje, i time mnogo poveća efikasnost koda.

Optimizacija gnezda petlje Neki algoritmi poput množenja matrica koji slabo koriste keš, a imaju prekomeran broj pristupa memoriji. Ovom optimizacijom se povećava broj pristupa kešu tako što se operacije rade po manjim blokovima koristeći optimizaciju izmena petlje.

Obrtanje petlje Obrtanje petlje obrće redosled u kojem su vrednosti dodeljene indeksiranim promenljivima. Ovo je prefinjena optimizacija koja pomaže eliminisanju zavisnosti, čime omogućava upotrebu drugih optimizacija.

Odmotavanje petlje Odmotavanje duplira telo petlje više puta u nameri da smanji broj testiranja uslova petlje, i broja skokova, koji smanjuju performanse oštećujući protočnu obradu instrukcija. Kompletno odmotavanje petlje eliminiše sav -{overhead}-, ali traži da se zna broj iteracija unapred.

Cepanje petlje Cepanje petlje pokušava da uprosti petlju ili eliminiše zavisnosti tako što razbija petlju na više manjih koje imaju isto telo, ali vrše iteraciju na različitim delovima lanca indeksa.

-{unswitch}--ovanje petlje Pomera uslove iz unutrašnjosti petlje van petlje tako što duplira petljino telo unutar svake -{if}- i -{else}- klauzule.

Protočna obrada softvera Petlja je rekonstruisana tako što se posao urađen u jednoj iteraciji deli na nekoliko delova koji se rade u nekoliko iteracija. U tesnoj petlji ova tehnika sakriva kašnjenje između učitavanja i korišćenja vrednosti.

Optimizacije toka podataka -{data-flow}-

Ove optimizacije, bazirane na analizi toka podataka, primarno zavise od toga kako se pojedine osobine podataka umnožavaju kontrolnom ivicom u -{control flow}- grafiku. Neke od njih su :

Standardna eliminacija podizraza U izrazu "(a+b)-(a+b)/4" ovo se odnosi na eliminaciju duplog (a+b) tako što ga kompilator računa samo jednom.

Slaganje konstanti (-{constant folding and propagation}-) Zamena izraza koji se sastoje od konstanti njihovim rezultatom (na primer 1+2 sa 3).

Prepoznavanje indukcijskih promenljivih i njihova eliminacija

Klasifikacija i analiza pokazivaća U prisustvu pokazivača teško je uraditi bilo kakvu optimizaciju. Specifikacijom koji pokazivač pokazuje na koju promenljivu se onda nepovezani pokazivači mogu ignorisati.

-{SSA}- bazirane optimizacije Ove optimizacije su namenjene za rad sa programima transformisanim u specijalnu formu zvanu -{static single assignment}- (-{SSA}-), u kojoj je svaka promenljiva dodeljena na samo jednom mestu. Neke od njih su :

Numerisanje globalnih vrednosti Eliminiše suvišnosti konstruišući grafik vrednosti programa, onda određuje koje vrednosti su izračunate istim izrazima. Ova optimizacija identifikuje i neke stvari koje eliminacija običnih podizraza ne može, i obrnuto.