kodtabla

[Andras Tantos]

> Haliho!

Neked is!

>
> >> Az optimalizáció nem is csak fv.en belül optimalizál!!! Épp ez a
> >> lényeg! Az _egész_ forrásfájlban tud. Egy régebbi menürendszer
> >> kezelõ - adatbeviteli stb. programon így nyertem kb. 2 kByteot,
> >> mert a hasonló részeket (amik logikailag mások kicsit, ezért én
> >> külön obj-ba raktam õket) összevonta, miután egy fájlba kerültek.
> >> Ezt a több száz soros C programot (tele pointerrel - itt
> >> visszajön a topicindítás :-) - különbözõ nyelvek kezelésével)
> >> lehetett volna kézzel is optimalizálni, de megelégedtem a
> >> fordítóval.
> >>
> > Ez erdekes, egy sima C fordito a library fuggvenyekhez pl hozza sem
> > nyul. Meghivja egy call-lal, akkor is ha 6 byte hosszu.
>
> Ha ez probléma, akkor ne használj C library-t! Nem pont az a lényeg,
> hogy azért használunk vmit mert könnyebb, gyorsabb, egyszerûbb használni?

Nos, a helyzet a kovetkezo (tudtommal): a legregebbi forditok nem tudtak, 
csak egy fv.-en belul optimalizalni. Sot, a meg regebbiek meg ezt se tudtak, 
csak u.n. basic block-okon belul tudtak optimalizalni. Ezek durvan olyan 
programreszletek, amikben nincs elagazas, es nincs olyan pont se, ahova a 
program mashonnan ugrana. Ezeken belul sok mindent lehet csinalni, az alabbi 
(EWAVR) listabol ezek azt hiszem mind basic-block-okon mukodnek:

- Common subexpression elimination-t
- Code motion (bizonyos elemei)-t
- Constant folding-ot
- Dead code elimination-t

A ket kovetkezo meg alapvetobb szinten van:
- Register Variables
- Peephole Optimizing
Ezek meg csak nem is a program logikai szerkezeten vegzett muveletek, hanem 
vagy a program gepi kodra valo atirasa soran (register variables, ami a 
register-allocator mukodesenek egyik mellektermeke) vagy mar magan a gepi 
kodu programon vegzett atalakitasok.

Aztan vannak azok a muveletek, amik egy fv-en belul, de a basic-blockok 
kozotti kapcsolatok figyelembevetelevel elvegezheto muveletek (ezekhez 
tipikusan SSA vagy data-flow grafokat epitenek fel a forditok):

- Code motion (azt amit itt leirnak, mashol strenght-reduction-nak, vagy 
hoisting-nak hivjak).
- Clustering of variables (bizonyos esetei)
- Data Overlaying (megintcsak bizonyos esetei, az, amit itt leirnak speciel 
nem)
- Global Common Subexpression Elimination
- Loop Rotation
- Common Tail Merging
- Common Block Subroutines
- Case/Switch Optimizing
- Jump Negation-t

Es persze a fentiek maradekat is el lehet vegezni ezen a szinten is, azaz a 
Constant folding-ot es a Dead code elimination-t.

A kovetkezo lepcso a teljes forditasi egyseg (ertsd C fajl az osszes 
header-evel) vizsgalata. Itt lehet ujabb grafokat (tipikusan call-graph-ot) 
epiteni es ezen tovabbi analiziseket vegezni. Ebbe a lepcsobe tartoznak a 
kovetkezok:

- Clustering of variables (maradek esetei)
- Data Overlaying (amit itt leirnak)
- Function inlining
- Cross call (masok ezt outlining-nak hivjak, az inlining forditottja)

Es persze megint egy csomo minden elvegezheto ujra ezen a szinten is, pl:

- Common Block Subroutines

A klasszikus esetben ezen a szinten a fordito leteszi a lantot, es kiirja az 
OBJ fajlt. A linker ezeket a fajlokat fogja osszerakni egy vegrahajthato 
programma. A linker klasszikusan nem sok optimalizalast csinal, tipikusan 
csak azt donti el, hogy mely OBJ-ektek kellenek, es melyek nem. Ezzel az a 
problema, hogy ha csak egesz OBJ-eketen tud muveleteket vegezni, akkor sok 
esetben olyan fuggvenyek is bekerulnek a kesz binary-ba, amiket senki nem 
hiv, ezzel novelve a kod meretet. Ezert van az, hogy sok library-ben minden 
egyes fuggveny kulon C fajlban van definialva. Igy egy buta linker is jo 
munkat tud vegezni, de persze, ha megnezitek a fenti listat kiderul, hogy ez 
kilovi a fodito harmadik csoportben felsorolt munkajat.

A megoldas az, hogy a linker fel tudja torni az obj fajokat, es ugynevezett 
szegmenseket linkel ossze. Ekkor a fordito feladata, hogy minden egyes 
fuggvenyt egy OBJ-ben a sajat kis szebmensebe tegye (es persze ezt meg lehet 
tenni minden egyes globalis valtozoval is). Igy a linker mar jobb munkat tud 
vegezni, es ami meg fontosabb nem teszi tonkre azt, amit a fordito mar 
egyszer kitalalt. Ugyanakkor meg is neheziti a fordito munkajat, mert nem 
tud olyan dolgokat kihasznalni, hogy ket (egy C fajlban deklaralt) fuggeny 
egymashoz viszonyitott helyezete ismert, vagy hogy pl. ha az egyik benne van 
a programban, akkor a masik is.

Korul belul ez az a pont, ahol a legtobb mai fordito all (kiveve egy-ket 
PC-s forditot - VC++ es Intel C).

A kovetkezo lepes az, hogy a program teljes egeszet analizaljuk, es 
forditasi egysegek (OBJ-ek) kozott is vegzunk optimalizalast. A problema 
ezzel csupan az, hogy az osszes OBJ-et csak a linker latja, az meg nem 
fordito. A megoldast idonkent 'whole program optimization'-nek, askor 
'link-time code generation'-nek hivjak, de a lenyege az, hogy a linker 
vissza tudja hivni a forditot valamilyen formaban.

Ha ezt a lepest is belerakjuk a kepbe, akkor a fenti optimalizalasokat, es 
meg joparat el lehet vegezni a teljes programon is. A hatranya a megoldasnak 
az irdatlan (forditoasi ideju) memoriaigeny es a lassu kodgeneralas.

Ami kimaradt:

Type-based alias analysis: ez minden egyes pontjan fontos a forditonak, egy 
baj van vele: a C nem eleg erosen tipusos nyelv ahhoz, hogy ez az analizis 
(ez meg nem optimalizacio, csak segitheti az optimalizalast) igazan hasznos 
legyen. C++-ban sokkal fontosabb es hasznosabb.

Extended Index Access Optimizing: ez egy tipikusan eszkoz-specifikus 
optimalizalas, es valoszinuleg egy basic-block-on belul csinaljak.

Es persze van egy csomo olyan optimalizalas, mi a felsoroasban nincs benne. 
Egy kis izelito:
- Loop-unrolling
- Induction-variable merging
- Induction-variable splitting
- Tail-call elimination
- Vectorization
- Stack optimization
- Data alignment
- Stack alignment
- Intrinsic function inlining (memcpy-bol rep movsd es hasonlok)
stb. stb.

Es persze a minden optimalizalasnal ket nehez problema eldontese var a 
forditora:
- Szabad-e meglepni a valtoztatast (azaz az eredeti es a modositott kod 
ugyanugy mukodik minden *ervenyes* forraskodra)
- Erdemes-e meglepni a valtoztatast (azaz a modositott kod kisebb/gyorsabb-e 
mint az eredeti)

>
> > Optimalizalasrol szo sincs. Hasonlo reszek keresese? Errol valami
> > doksit produkalj, de meg akkor sem hiszem el egeszen.
>
> Na, akkor lássuk:
> EWAVR 4.10, Compiler reference, p. 123

... sok szoveg torolve ...
>
> Ez volt az EW AVR, most nézzük a Keil-t 7.5, Optimizing C Compiler and 
> Library Reference, p. 63:

... meg tobb szoveg torolve ...

> >>> Szóval teszem azt, nagyon sok hasonló vizsgálat van egy forrásban
> >>> (if (vmi rendkívül bonyolult) {} else {}) na, itt a fordító
> >>> észreveszi, hogy közös - hasonló a feltétel és kiteszi egy
> >>> szubrutinba. Ezt assemblyben k*rvanehéz megcsinálni, mert nem
> >>> veszed éeszre triviálisan a logikai hasonlóságokat. Ezek sokat
> >>> lehet nyerni.
>
> Mi ebben a durva? Menyiben tér el ez a fent idézett optimalizációs 
> lehetõségektõl?

Semmi, es ezt raadasul aranylag egyszeru is megcsinalni (legalabbis bizonyos 
eseteit). Itt a feltetel egy logikai kifelyezes, aminek a kiiertekelese 
(vagy annak egy resze) kivonhato a sokszoros kiiertekeles ele - felteve, 
hogy kozben nem ugrasz at ertekadast, ami megvaltoztathatja a kifelyezes 
erteket. Teljesen altalanos 'global optimalization' muvelet, a 'hoisting' 
kategoriaba esik. Aranylag ritkan szoktak kulon szubrutinba tenni: inkabb az 
eredmenyt rakjak el egy atmeneti valtozoba/regiszterbe. A kulon szubrutinba 
rakas az 'outlining' kategoria, es a baj vele az, hogy ritkan segit valoban 
a programon (felteve, hogy sebessegre optimalizalunk).

Udv,
Tantos Andras