PROFILBARU.COM

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 (engl. Pipeline) : 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.

Retko uslovno slaganje konstanti

Je ekvivalentno uzastopnom ponavljanju slaganja konstanti, i eliminaciji mrtvog koda sve dok više nema promena.

Optimizacije generatora koda

Alokacija registara

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.

Izbor Instrukcija

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.

Planiranje instrukcija

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.

Rematerijalizacija

Bazirana na celobrojnom linearnom programiranju, restrukturira kompilatorovo poboljšavanje položaja podataka i poboljšava paralelizam reorganizujući izračunavanja.

Optimizacije funkcionalnog jezika

Iako se koristi i na nefunkcionalne jezike, potiče, a i najviše se koristi u funkcionalnim jezicima kao na primer jeziku Lisp.

Odstranjivanje rekurzije

Repno rekurzivni algoritmi mogu se pretvoriti u iteraciju, koja je znatno brža.

Spajanje struktura podataka

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.

Neke druge optimizacije

Eliminacija provera granica

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.

Optimizacija izdanaka grane (Branch offset)

Bira najkraći put do cilja u nekom drvetu.

Eliminacija mrtvog koda

Odstranjuje naredbe koje ne utiču na ponašanje programa. Ovo smanjuje dužinu koda i izbacuje nepotrebna računanja.

Totalna eliminacija suvišnosti

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.

Neposredno proširivanje

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.

Povezivanje skokova

Kada se u prolazu kroz uslovno grananje skoči na kod sa istim, ili suprotnim uslovom, može se nastaviti dalje.

Redukcija snage

Podrazumeva zamenu kompleksnih, teških, ili skupih operacija nekim jednostavnijim.

Redukcija kolizije keša

Redukcija visine steka

Preuređivanje drveta izraza tako da se minimiziraju resursi potrebni za izračunavanje izraza

Reorganizacija testova

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

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.

Problemi sa optimizacijama

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:

Obično optimizujući kompilator radi samo male promene na malim skupovima operacija. To znači da velike neefikasnosti izvornog programa ostaju netaknute.
Kompilator obično radi samo sa malim delovima celog programa odjednom, tako da ne može da razmotri neke bitne kontekstne inforrmacije.
Svaki dodatni posao troši vreme. Optimizacija celog programa ima veliku cenu.
Interakcija faza optimizacije kompilatora: koje kombinacije optimizacija i u koje vreme svaka treba da bude primenjena, i koliko puta.

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.