Optimizacija kompilatora
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
[уреди | уреди извор]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.
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.
- unswitch-ovanje petlje
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.
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 :
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).
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 :
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
[уреди | уреди извор]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.
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.
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.
Neke druge optimizacije
[уреди | уреди извор]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.
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.
- Povezivanje skokova
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
[уреди | уреди извор]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.
Lista optimizacija kompilatora
[уреди | уреди извор]- Automatska paralelizacija
- Slaganje konstanti
- Pojednostavljanje algebre
- Brojanje vrednosti
- Umnožavanje kopija
- Umnožavanje konstanti
- Eliminacija prostih podizraza
- Delimična eliminacija suvišnosti
- Eliminacija mrtvog koda
- Redukcija snage
- Optimizacija petlji
- Protočna obrada softvera
- Generisanje koda
- Vektorizacija
- Naređivanje u etapama