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.
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:
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
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.
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.
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.
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.
Ponovno korišćenje rezultata koji su već izračunati i čuvanje istih za kasnije, umesto ponovnog izračunavanja.
Izbacivanje beskorisnih izračunavanja i međuvrednosti. Manje posla za procesor, keš, memoriju je obično brže.
Manje komplikovan kod. Skokovi ometaju pripremu instrukcija, i time usporavaju kod.
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.
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.
Razmeštanje operacija tako da se omogući njihovo paralelno izračunavanje, bilo na nivou instrukcije, memorije, ili niti.
Što preciznije informacije kompilator ima, to će bolje upotrebiti tehnike optimizacije.
Tehnike koje su dizajnirane da uglavnom rade na petljama su :
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 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.
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.
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.
Ove optimizacije zamenjuju unutrašnje sa spoljašnjim petljama. Kada se promenljive indeksiraju u niz poboljašava se položaj referenci.
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.
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 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 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 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.
Pomera uslove iz unutrašnjosti petlje van petlje tako što duplira petljino telo unutar svake if i else klauzule.
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.
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 :
U izrazu "(a+b)-(a+b)/4" ovo se odnosi na eliminaciju duplog (a+b) tako što ga kompilator računa samo jednom.
Zamena izraza koji se sastoje od konstanti njihovim rezultatom (na primer 1+2 sa 3).
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.
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 :
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.
Je ekvivalentno uzastopnom ponavljanju slaganja konstanti, i eliminaciji mrtvog koda sve dok više nema promena.
Najčešće korišćene promenljive trebaju da se čuvaju u procesorskim registrima zbog najbržeg pristupa. A da bi se saznalo koje su to promenljive konstruiše se grafik interferencije.
Većina arhitektura, naročito CISC arhitekture, i one koje imaju više modova adresiranja, nude više različitih načina za izvođenje jedne neke operacije koristeći potpuno različite nizove instrukcija. Ova optimizacija bira instrukcije koje će najbolje odraditi posao.
Ovo je bitna optimizacija za moderne procesore sa protočnom obradom, koja izbegava zastoje i mehuriće u protočnoj obradi tako što sakuplja instrukcije bez zavisnosti, dok pažljivo očuvava originalnu semantiku.
Bazirana na celobrojnom linearnom programiranju, restrukturira kompilatorovo poboljšavanje položaja podataka i poboljšava paralelizam reorganizujući izračunavanja.
Iako se koristi i na nefunkcionalne jezike, potiče, a i najviše se koristi u funkcionalnim jezicima kao na primer jeziku Lisp.
Repno rekurzivni algoritmi mogu se pretvoriti u iteraciju, koja je znatno brža.
S obzirom na način na koji su strukture podataka specifikovane u funkcionalnim jezicima, moguće je kombinovati nekoliko rekurzivnih funkcija koje proizvode i koriste privremene strukture podataka, tako da se podaci prosleđuju direktno bez gubljenja vremena na konstruisanje struktura podataka.
Mnogi moderni jezici, na primer Java, primenjuju proveru granica svih pristupa nizovima. Ovo loše utiče na performanse. Ova optimizacija dozvoljava kompilatoru da ukloni neke provere granica, kada može da odredi da je indeks u granicama, na primer ako je to obična promenljiva petlje.
Bira najkraći put do cilja u nekom drvetu.
Odstranjuje naredbe koje ne utiču na ponašanje programa. Ovo smanjuje dužinu koda i izbacuje nepotrebna računanja.
Ako se neki izraz radi i kada je uslov ispunjen i kad nije, može se izostaviti ispitivanje uslova. Slično ako se neki tipovi izraza pojavljuju unutar petlje, mogu se pomeriti i ispred ako nema razloga da se izvrše jednom ili više puta.
Kada neki kod pozove proceduru moguće je direktno ubaciti telo procedure unutar pozivnog koda. Ovime se dozvoljavaju razne druge optimizacije, ali se koristi više prostora.
Kada se u prolazu kroz uslovno grananje skoči na kod sa istim, ili suprotnim uslovom, može se nastaviti dalje.
Podrazumeva zamenu kompleksnih, teških, ili skupih operacija nekim jednostavnijim.
Preuređivanje drveta izraza tako da se minimiziraju resursi potrebni za izračunavanje izraza
Ako imamo više testova koji su uslov za nešto prvo se proveravaju jednostavniji. Ovo može da se primeni jedino ako testovi ne zavise jedan od drugog.
Interproceduralne optimizacije rade na celom programu. Neke od njih su gore nabrojane. Koriste ih svi moderni komercijalni kompilatori, mada ne bez korisnikovog izbora jer one troše dosta vremena i prostora.
Ranije su ručno odrađene optimizacije bile bolje od optimizacija kompilatora, ali kako su se tehnologije kompilatora poboljšale, dobri kompilatori bolje optimizuju nego programeri. za RISC arhitekturu procesora, a čak i više za VLIW hardver, optimizacija kompilatora je ključ za dobijanje efikasnog koda, zato što su skupovi RISC instrukcija tako kompaktni da je teško čoveku da ručno organizuje ili kombinuje sitne instrukcije da bi dobio bolje rezultate. Kako god, optimizacije kompilatora nisu nikako savršene. Ni jedan kompilator ne može da garantuje da je za svaki izvorni kod najbolji ekvivalent izlazni kod. Takav kompilator je nemoguće napraviti jer bi on rešio problem stajanja (halting problem). Ovo se može dokazati pomoću funkcije foo(). Ova funkcija ne vraća ništa i ne radi ništa sa strane. Najbrži ekvivalent programa bio bi jednostavno eliminacija poziva funkcije. S druge strane ako funkcija foo() ne vraća ništa, onda bi program sa pozivom te funkcije bio različit od programa bez poziva. Dodatno, postoje i mnogi drugi probelim sa tehnologijom optimizacije kompilatorom:
Posao poboljšanja tehnologija optimizacije se nastavlja. Jedan od pristupa je takozvana optimizacija posle prolaza. Ona uzima izvršni program pa ga optimizuje dalje. To je dobro zato što ona radi optimizacije na asemblerskom jeziku. Mada oni su takođe ograničeni činjenicom da je mnogo informacija nađenih u izvornom kodu izgubljeno.
S obzirom da performanse procesora rastu sve više i više sad se teži ka optimizaciji korišćenja memorije na račun brzine.