EGCS 1.1
-=-=-=-=-=
V minulém čísle Výhně jsem psal o novém projektu EGCS (Extended
GNU Compiler System), který má za úkol otestovat otevřený vývojový
model na GNU C Compileru, zrychlit jeho vývoj, a vytvořit prostředí
pro testování nových nápadů a složitějších změn. Slíbil jsem také,
že se časem napíšu, jak si vede.
Dnes byla vydána druhá major release (1.1) a proto myslím,
že je vhodný čas. Co se tedy podařilo vyvinout za necelý rok mezi
1.0 a 1.1? Pouze patch z verze 1.0 na verzi 1.1 je dlouhý 6MB
po zabalení gzipem. Zdrojové kódy jsou dlouhé 11MB, což ukazuje,
že změn není málo. Nejdůležitější jsou:
Global CSE/Partial Redundancy Elimination
Jedna z nejšílenějších optimalizací, kterou GCC provadí je CSE
(Common Subexpression Elimination). Jejím úkolem je najít stejné
podvýrazy a použít výsledek z předchozího. Tato optimalizace je
nečekaně efektivní, protoře už jenom kód:
if (pole[i]<0) pole[i]=-1;
takovou optimalizaci umožňuje. Bez ní by se adresa prvku pole[i]
zbytečně počítala dvakrát.
Pořádně fungující CSE je ale velmi složité, ptotože stejné
hodnoty lze spočítat mnoha různými způsoby a proto CSE musí provádět
mnoho algebraických úprav. Proto je cse.c jeden z nejdelších
a nekomplikovanějších zdrojových souborů v GCC.
Toto CSE má ale jedno velké omezení. Umí pracovat pouze v rámci
jednoho basic bloku (to je blok instrukcí, ve kterém nejsou žádné
skoky a ani do něho žádné skoky nevedou, instrukce se tedy provádí
pokaždé ve stejném pořadí). Například i v úvodním příkladu if
generuje skok a tak CSE optimalizaci neprovede.
Doug Evans ale implementoval globalní CSE, které má za úkol
tento problém odstranit. Vytvoří si jakýsi vývojový diagram celé
funkce a udělá podrobnější analýzy a díky tomu může detekovat tyto
komplikovanější případy. Například v následujícím příkladu odstraní
druhý výskyt expr1:
expr1
/ \
/ \
expr2 expr3
| |
expr4 expr2
\ /
\ /
expr1
Navíc ale implementoval i PRE (Partial Redundancy Elimination),
která dokáže najít i expr2 a umístit ji před rozvětvení programu.
Expr2 se tedy počítá pouze jednou. PRE dokonce dokáže objevit
invarianty ve smyčkách (výrazy co mají pokaždé stejnou hodnoru)
a spočítat je vně smyčky. Tato optimalizace je ale vypnuta, protože
ji mnohem lépe provádí loop optimizer.
V současné implementaci GCSE provádí méně algebraických úprav,
než CSE a proto je dokonce rychlejší. Spolu se starým CSE odvádí
velmi dobrou práci. Jeho výsledky se ale projevují zejména v ne
příliš optimalizovaných programech (protože jinak udělá programátor
práci za něj) a proto nelze čekat žádné větší zrychlení interní
smyčky Vašeho programu. Pomůže ale v případě velmi komplikovaných
algoritmů.
Tento kód je také zajímavý tím, že přináší základ pro
optimalizaci známou jako Lazy Code Motion. Jejím úkolem je
přeházet kód tak, aby se snížil rozsah, kde je nutné proměnou
uložit do paměti (mezi jejím nastavením a použitím). To by mělo
ušetřit registry nutné pro uchovávání proměných, což pomůže zejména
na Intelu a ostatních architekturách s malým počtem registrů.
LCM je zase základem pro řadu dalších optimalizací - dead store
elimination (pokud se uloží hodnota na ukazatel a potom jiná a mezi
nejsou žádné kolidující přístupy, první uložení se může vynechat),
shring wrapping, spill code motion a generic load/store motion. Tato
optimalizace snad vyřeší problem, že většina ostatních optimalizací
má tendenci tyto intervaly zvětšovat a proto jsou jejich výsledky
na Intelu sporné. Na LCM pracuje na zakázku firma Cygnus (podobně
jako na GCSE apod.) a slibuje její zveřejnění do konce roku.
Alias Analysis
Další zajímavou optimalizací je alias analysis. Ta výchází
z ANSI C standardu, který říká, že není možné do stejného bloku
paměti uložit dva shorty a později je načíst jako jeden long či jiné
podobné kombinování typů.
Pro programy, které odpovídají tomuto standardu (to by měly být
všechny) je možné přidat optimalizaci, kde překladač nebude očekávat
kolizi mezi ukazately s různými typy. Tedy v následujícím kódu:
int *i;
short s,d;
....
*i=5;
printf("%i\n",s);
překladač klidně může přehodit poslední dva řádky, aniž by se
obával toho, že ukazatel i ukazuje na adresu s. To dává dalším
optimalizacím (jako je loop optimizer, (G)CSE, či scheduler) větší
volnost.
Tuto optimalizaci vyvinula firma Mark Mitchell Consulting jako
součást zakázky pro Los Alamos National Laboratory. Stejná firma už
asi před rokem přidala podobnou optimalizaci, která si u ukazatelů
pamatuje, jestli ukazují do zásobníku, haldy či statických polí
a nepředpokládá kolizi mezi těmito bloky paměti.
Tato optimalizace není standardně zapnutá (protože některé
programy neodpovídají ANSI C standardům) a je nutné ji ručně zapnout
pomocí -fstrict-aliasing.
Ostatní optimalizace
Nová verze samozřejmě obsahuje mnoho různých změn do optimizeru.
Mezi ty největší změny patří:
- Regmove optimalizace byla téměř úplně přepsána. (regmove řeší
situace, kde instrukce vyžaduje jiný registr, než dostane - snaží
se minimalizovat instrukce typu mov registr, registr)
- Alokace registrů si spočítá přesnější údaje o použití jednotlivých
proměných a obsahuje některé vylepšení v heruistice na přidělování
registrů.
- Exception handling nyní zabírá méně místa a je o něco rychlejší.
- Register reloading produkuje lepší kód (což poměrně hodně pomůže
na x86).
- Nový přepínač -Os pro optimalizaci na velikost (zatím ale oproti
-O2 moc nepomůže)
- Lepší optimalizace pro Inline funkce
- Architekturově závislé optimalizace pro i386: Velké změny
v zarovnávání dat. Pokud máte nový GAS (2.9.x), použije se nová
.p2align pseudoinstrukce, která zarovnává podle Intelovského
manuálu. Tyto optimalizace na Pentiu opravdu znatelně pomůžou.
Další optimalizace zahrnují například conditinal move pro
PentiumPro.
Ostatní změny
Nejenom optimalizacemi živ je člověk a proto Egcs obsahuje
i některé další změny. Například přepínač --help apod.
Mnoho vývoje bylo oděláno na podpoře C++. GCC mívalo v době
2.7.x jednu z nejlepších podpor C++ vůbec. Ta za dva roky do vydání
2.8.x poměrně zastarala a proto je třeba udělat hodně práce.
Egcs 1.1 obsahuje změny zejména v podpoře templates, namespace
a exception handlingu. Navíc podporuje nové experimentalní ABI.
Stabilita
Díky otevřenému vývojovému modelu jsou jednotlivé vyvojové verze
testovány mnoha uživately a proto je egcs poměrně stabilní. Navíc
GCC obsauje velký počet testů a i u stabilních verzí některé z nich
neprojdou. Autoři se rozhodli, že egcs nebude mít žádné chyby,
které se projeví na několika základních platformách v těchto testech
a proto vypnuli některé menší optimalizace, které způsobovaly
potíže. Navíc egcs testují na kompilaci jádra Linuxu, knihovně glibc
a všech programech v distribuci RedHat. Proto by tato verze měla být
opravdu stabilní.
Výsledky
Osobně používám vývojové verze egcs 1.1 už delší dobu a nesetkal
jsem se s žádnými problémy vyjma kompilace některých verzí jádra
Linuxu, ale v tomto případě se nejedná o chybu egcs.
Výsledný kód je téměř vždy rychlejší a dokonce o něco kratší,
než v případě gcc 2.8.x (delší oproti gcc 2.7.x). Zrychlení jsou
ale většinou dost malá, jak nicméně ukazuje i následující srovnání
na Alphe:
SPEC Benchmark CINT95 Summary
Base 1.0.3 1.0.3 1.1 1.1
Benchmarks Ref Time Run Time Ratio Run Time Ratio
------------ -------- -------- -------- -------- --------
099.go 4600 660 6.97 687 6.69
124.m88ksim 1900 397 4.79 374 5.08
126.gcc 1700 284 5.98 275 6.18
129.compress 1800 416 4.33 380 4.74
130.li 1900 381 4.98 379 5.01
132.ijpeg 2400 406 5.90 380 6.32
134.perl 1900 278 6.84 278 6.84
147.vortex 2700 681 3.97 571 4.73
SPECint_base95 (Geom. Mean) 5.37 5.64
SPEC Benchmark CFP95 Summary
Base 1.0.3 1.0.3 1.1 1.1
Benchmarks Ref Time Run Time Ratio Run Time Ratio
------------ -------- -------- -------- -------- --------
101.tomcatv 3700 448 8.26 439 8.42
102.swim 8600 877 9.80 764 11.3
103.su2cor 1400 428 3.27 413 3.39
104.hydro2d 2400 693 3.46 679 3.53
107.mgrid 2500 438 5.71 430 5.81
110.applu 2200 472 4.66 473 4.65
125.turb3d 4100 569 7.20 555 7.38
141.apsi 2100 341 6.15 341 6.16
145.fpppp 9600 767 12.5 1075 8.93
146.wave5 3000 622 4.82 559 5.37
SPECfp_base95 (Geom. Mean) 6.05 6.06
Na Intelu bych odhadoval poněkud větší zrychlení díky
optimalizacím v alokaci registrů, reloadu a zarovnávání dat. Podle
mých soukromých testů jsou cca 15 až 30%.
Změny v rychlosti nejsou příliš velké, protože většina
změn v překladači je spíše začátkem dalšího vývoje a jejich
přínos se projeví později. Často se ale projeví velké změny
u neoptimalizovaných programů, protože se překladač stává
chytřejším. Pokud chcete za každou cenu rycheljší kód, je možné
použít PGCC, které ale není tak stabilní a někdy generuje výrazně
horší kód. Většinou ale přináší zrychlení o cca 10% oproti Egcs.
Další vývoj
Protože už asi měsíc je verze 1.1 ve feature freeze stadiu,
je už uděláno poměrně hodně práce na další verzi. David Miler
kompletně přepsal backend pro Sparc a proto lze očekávat výrazně
lepší kód zejména na Ultrasparcu. Loop optimizer byl rozšířen tak,
aby uměl unroolovat i některé smyčky bez pevného počtu průchodu
apod. Cygnus dodal nový frontend pro jazyk Chill. Firma Mark Michel
Computing vyvinula další zajímavou optimalizaci pro Los Alamos,
která vyndavá přístupy na ukazatele vně smyček (ve staré verzi se
vždy hodnota načetla z ukazatele, změnila a uložila, nyní překladač
uchová hodnotu v registru a uloží až za smyčkou).
Velké změny se plánují do reload průchodu. Ten má za úkol
nahrávat hodnoty do registrů tak, aby instrukce měly data
v registrech, které podporují. Tento průchod často není třeba,
protože se o to normálně postará alokátor registrů. Někdy se ale
stane, že se to alokátoru registrů a regmove průchodu nepodaří.
Aktuální implementace funguje tak, že jeden z registrů označí jako
reload registr a předělá celou funkci tak, že registr nepoužívá.
Tento registr se potom používá pro reloading.
Na Intelu toto často není možné, protože registry mají různé
speciální významy. V této situaci je jistá šance, že reload změní
registr v případě, že je zrovna použit. Takové situace vznikají
zejména při používání asm statementů a registrových konvencí pro
volání funkcí (to je důvod, proč je GCC nepoužívá). Díky zmatku,
které "odhalení" této letité chyby způsobilo na mailing listu
kernelu Linuxu ale už existuje patch (cca 100Kb), který upravuje
reload aby si napřed zjistil, které registry se kdy používají
a pro reloading používal nepoužité registry. Výsledkem je lepší
kód a odstraňuje se riziko chyby. Bude ale třeba mnoha dalších
zásahů do překladače, aby tento nový algoritmus fungoval spolehlivě
(některé další části překladače spoléhají na staré chování reloadu).
Spolu s dalším malým patchem snad ale budou konečně chodit
registrové volací konvence.
Také se plánuje lepší zarovnávání dat na Intelu. Pokud je
double hodnota zarovnána na adresu dělitelnou osmi, funguje mnohem
rychleji. To je za použití přepínaře -falign-double zaručeno
u struktur a dalších typů. Na zásobník se ale stále ukládají stejně.
Existuje už ale patch, který zaručí ukládání na adresy dělitelné
osmi. To je poměrně komplikované, protože musí být zaručeno,
aby adresa byla dělitelná už při vstupu do funkce. Navíc standard
pro volání funkcí nepodporuje toto zarovnávání a proto je nutné
udělat patch tak, aby uměl volat funkce "postaru", což není úplně
jednoduché.
Plánuje se zamozřejmě mnoho dalších změn, jako už zmiňované Lazy
Code Motion. David Miler pracuje na novém algoritmu pro alokaci
registrů atd.
Celkově myslím, že egcs je velmi úspešný projekt a že se máme
na co těšit.
výheň