Překladač


If the Tao is great, then the operating system is great. If the operating system is great, then the compiler is great. If the compiler is great, then the application is great. If the application is great, then the user is pleased and there is harmony in the world.

The Tao gave birth to machine language. Machine language gave birth to the assembler.

The assembler gave birth to the compiler. Now there are ten thousand languages.

Each language has its purpose, however humble. Each language expresses the Yin and Yang of software. Each language has its place within the Tao.

But do not program in COBOL if you can avoid it.

-- Geoffrey James, The Tao of Programming

Nejdůležitější GNU program je nesporně překladač. Ten umožnil, aby vzniklo všechno ostatní. Jedná se o jeden z nejkvalitnějších překladačů vůbec - je snadno přenositelný na novou architekturu (jedná se pouze o napsaní několika souborů s popisem architektury a pro generování assembleru), umí překládat mnoho různých jazyků (není tedy třeba jeden překladač pro Pascal a jiný pro C) a má výborný optimizer.

Překlad se provádí pomocí mezijazyku zveného Register transfer language (RTL). Ten je navržen tak, aby zastřešil rozdíly mezi vstupnímy jazyky a vístupní platformou a je velmi vhodný pro optimalizace. Narozdíl od většiny ostatních překladačů je ale svým způsobem závislý na cílovém procesoru a proto GNU C dokáže své optimalizace dobře přizpůsobit specifickým potřebám dané platformy.

Provádějí se tyto základní optimalizace:

Optimalizace skoků
zrušení skoků na skoky
Scanování registrů
tady se najde, kdy který registr (krycí název pro proměnnou) byl použit poprvé a naposled
Optimalizace skoků na stejný nebo opačný test
ty mohou být vynechány
Propagace konstant, eliminace výrazů
propagace konstant se snaží dosadit konstanty za registry. Odstraňuje výrazy bez výstupů a vedlejších efektů a vyhodnocuje výrazy bez vstupů. To výrazy zkracuje, vyhodí nepotřebné části programu atd.
Optimalizace smyček
Snaží se všechno, co jenom jde, dostat mimo smyčku. Znova proběhne eliminace expresion.
Analýza toku dat
Rozdělí program do bloků, vyhazuje nedosažitelné smyčky, a zjišťuje, kde který registr je živý - to znamená, že je třeba uchovávat jeho hodnotu - najde výpočty, kde výsledek není použit.
Kombinace instrukcí
(ne assemblerových, ale těch RTL) Spojuje instrukce, které jdou sjednotit do jedné, používá algebru na optimalizaci matematických výrazů a přidělí RTL kódu opravdové instrukce, které odpovídají popisu procesoru. (ano, tato část je částečně závislá na architektuře).
Scheduling instrukcí
poskládá instrukce pro superskalární riscové procesory tak, aby bylo možné jich provádět více naráz. Verze 2.8.0 (která ještě není) to bude dělat i pro Pentia a Pentia pro.
Třídy registrů
hardwarové registry mají několik tříd. Tak třeba paměť (zásobník), registry procesoru, registry koprocesoru. Tato část rozhodne, které třídy registrů lze použít pro ten daný pseudoregistr.
Alokace registrů
tady se konečně rozhodne, které proměnné budou ve výsledném programu uloženy a kdy.
Globální alokace registrů
to samé, ale pro globální proměnné.
Reloading
tady se dosadí hardwarové registry registrům a zbytek se uloží do zásobníku.
Další scheduling
aby se instrukce nehádaly o paměť, potom se opakuje optimalizace skoků a ještě jednou scheduling
optimalizace zásobníkových registrů
to je speciálně pro koprocesor i386
Převod do assembleru
a dílo je hotovo.

Samozřejmě, že překladač provádí i mnoho dalších malých optimalizací.

Znalci assembleru možná docení výsledný kód následujícího příkladu:

      main()
      {int i,a=1,b=0;
          for(i=0;i<9999;i++)
          a=a+b,b=2*a;
          printf("%i\n",a);
      }

Výsledek z GCC a Borland C 2.0.

Srovnání s ostatními

Toto je malé ilustrační srovnání. Testuji zde jen jeden malý program a proto výsledky nejsou příliš přesné, ale ukazují, že GCC si opravdu nestojí špatně. K testům jsem se rozhodl použít výpočet Mandelbrotovy množiny. Je to netriviální, koprocesor využívající smyčka z reálného života. Tak se překladač má co činit.

Zdrojový kód v C, a v Pascalu

Pro testy jsem použil Pentium/100 na 120, 512KB burst cache pod čistým DOSem s himem.sys. Snažil jsem se všechny překladače donutit k co nejlepším výsledkům.

Kompilátor přepínače Smyček za sekundu
pgcc2.7.2p -O6 -ffast-math -mpentium -frisc -fomit-frame-pointer -funroll-loops-fopt-reg-use -frisc 5 464 480
egcs-1.0 -O3 -ffast-math -mpentium -fomit-frame-pointer -funroll-loops 5 405 405
egcs-1.0+HAIFA -O3 -ffast-math -mpentium -fomit-frame-pointer -funroll-loops 5 005 005
egcs-1.0 -O3 -ffast-math -m486 -fomit-frame-pointer -funroll-loops 4 807 692
gcc2.6.3 -O3 -ffast-math -m486 -fomit-frame-pointer -funroll-loops 4 233 641
gcc2.7.2.1 -O3 -ffast-math -m486 -fomit-frame-pointer -funroll-loops 4 419 377
gpc2.0 -O3 -ffast-math -m486 -fomit-frame-pointer -funroll-loops 3 433 962
wc11 -7 -5 -ol -ol+ -om -op -or -ot -fp5 -fpi87 3 090 090
vc5.0 (optimalizace na max) 3 060 908
wc10.0 -7 -5 -ol -ol+ -om -op -or -ot -fp5 -fpi87 2 222 222
wc10.0 -5 -7 2 217 249
delphi max. speed 1 807 288
plan9 default 1 623 376
vc1.0 (v IDE-586,speed+size optim.) 1 531 393
bc4.5 (v IDE-486,fastest executable) 1 455 604
bc3.1 (v IDE-386,fastest executable) 1 433 070
gcc2.7.2.1 (bez optimalizací) 1 281 348
gpc2.0 (bez optimalizací) 1 109 756
bp7.0 max. speed 901 713
tc2.0 -1 -f87 -O -r -Z -G -a -mt 846 511
bc4.0 (v IDE-486,speed optimizations) 755 857
bc2.0 (bez optimalizací) 716 535
bc2.0 -G -O -2 -Z -r 716 535
tc2.0 max. speed 546 546
bc4.0 (v IDE-486,speed+size optim.) -3.6676456...

Vc znamená Visual C++ 1.0/5.0. GCC 2.6.3 bylo použito v DJGPP 1.0. Wc znamená Watcom C. Plan9 je kompilátor ve stejnojmenném OS. Gpc je GNU Pascal compiler. Egcs je odštěpená větev od vývoje GCC 2.8.0. Nyní je oficiální verzí GCC 2.95.0 PGCC je GCC pro Pentium, ktere původně začal vyvíjet Intel. Potom co dosáhl 30% urychlení ve smíšených benchmarkách, nechal vývoje a uvolnil zdrojové kódy. Vývoje se ujala skupina jménem Pentium Support Group, která odstranila velkou část chyb, které Intel zavedl, přidala podporu PentiaPro, k5, k6 a Cyrixe.