Kodovani P°edchozφ Nßsledujφcφ Obsah

---

4. P°ekladaΦ

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.

Klasick² p°ekladaΦ nap°ed naΦte vstup, rozlo╛φ ho na tokeny a porozumφ mu. Kdy╛ u╛ vφ, co programßtor napsal, p°id∞lφ pam∞╗ovß mφsta prom∞nn²m (modern∞j╣φ pou╛φvajφ i registry) a potom pomocφ jak²chsi prefabrikßt∙ na ka╛d² p°φkaz jazyka slo╛φ v²sledn² k≤d. P°φpadn∞ se je╣t∞ pokusφ p°edvyhodnotit v²razy, nebo se rozhlΘdne po vzniklΘm assembleru a vym∞nφ pßr instrukcφ, kterΘ se Φasto ╣patn∞ generujφ. Vzniklou sklßdaΦku potom po╣le dßl.

P°ekladaΦ od GNU mß jinΘ °e╣enφ. Nejprve porozumφ programu. Toto je jedinß Φßst zßvislß na jazyce a naz²vß se parsing. Potom se vygeneruje mezijazyk zvan² Register transfer language (RTL). Od tohoto okam╛iku u╛ je p°ekladaΦi jedno, jestli kompiluje C, nebo Pascal. Mezijazyk je podobn² lispu. Tedy ideßlnφ pro strojovΘ zpracovßnφ, proto╛e v╣echny p°φkazy majφ stejnou syntax (li╣φ se pouze akcφ) a obsahujφ dodateΦn∞ ╣ikovnΘ informace, jako t°eba co pot°ebuje za vstup a v²stup a co modifikuje. V╣echny prom∞nnΘ a pam∞╗ jsou unifikovßny do registr∙ (t°eba pole je takΘ registr). Jazyk nenφ reprezentovßn textov∞, ale ve specißlnφ struktu°e tak, aby se s nφm dob°e pracovalo. Je mo╛nΘ ulo╛it jej do textovΘ podoby.

Je pravda, ╛e existujφ i jinΘ p°ekladaΦe, kterΘ majφ mezik≤d, ale je to spφ╣e vyjφmka.

Nßsledujφcφ p°iklad:

      main()
      {
        return(0);
      }

Potom se dostanou ke slovu optimalizßtory. Valnß v∞t╣ina je nezßvislß na architektu°e (procesoru), proto╛e ani RTL se zatφm moc asembleru nepodobß (snad a╛ na jmΘna registr∙). Optimalizßtor∙ je hodn∞. Tak╛e jenom krßtk² popis:

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.

Nß╣ p°φklad po optimalizaci

Vyrobit assembler je u╛ snadnΘ: (Je v  AT&T syntaxi . Ale snad to je jasnΘ)

      main:
             xorl %eax,%eax
             ret

A je╣t∞ jeden pon∞kud slo╛it∞j╣φ p°φklad:

      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.

4.1 Srovnßnφ s ostatnφmi

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 DOSem s himemem. Sna╛il jsem se v╣echny p°ekladaΦe donutit k co nejlep╣φm v²sledk∙m. Program jsem se sna╛il napsat co nejrychlej╣φ.

Jak je vid∞t, Borland C je 5.77krßt pomalej╣φ. Pascal je na tom o n∞co lΘpe, tedy 4.58 krßt. Assemblerov² zdrojßk se mi poda°ilo zφskat jenom z  Borland C a  GCC . NapoΦφtal jsem 20 instrukcφ v internφ smyΦce u GNU a 35 u Borland C. Nov∞j╣φ Borland C se celkem slu╣n∞ vylep╣il. Ve verzi 4.5 je u╛ ,,pouze'' 2.6krßt pomalej╣φ. Naprosto m∞ ale p°ekvapil test ve verzi 4.0. Tam se zpomalil a po zapnutφ optimalizacφ na velikost se program natolik zrychlil, ╛e zφskal zßporn² Φas. Nevφm, jak n∞kdo m∙╛e kompilßtor s tolika chybami pustit do sv∞ta. Dal╣φ zajφmavß v∞c ohledn∞ Borland C je to, ╛e ve verzi 3.1 byl .exe dlouh² 14KB, ve verzi 4.0 u╛ 48KB a v 4.5 cel²ch 61KB. V poslednφch Borland C jsem napoΦφtal 34 instrukcφ v internφ smyΦce. FractalZoom, kter² mß smyΦku v assembleru se py╣nφ 22 instrukcemi a jeho test °φkß 3.9 milion∙ smyΦek za sekundu. ZajφmavΘ je, ╛e starΘ GCC vy╣lo z testu o 2.2% lΘpe. Je to tφm, ╛e jako novΘ DJGPP jako jedinΘ poΦφtß 18.2 tik∙ do sekundy mφsto 18. Watcom C p°esto, ╛e na rozdφl od GCC podporuje Pentium, schedulding instrukcφ pro Pentium a fp optimalizace pro Pentia, bylo tΘm∞° dvakrßt pomalej╣φ. Je╣t∞ v∞t╣φho zrychlenφ dosßhla v²vojovß verze GCC - egcs pomocφ unroolovßnφ smyΦky, proto╛e Pentiov² koprocesor opravdu ╣patn∞ snß╣φ skoky. P°i zapnutφ optimalizacφ pro 480 se smyΦka takΘ unrooluje, ale proto, aby bylo mΘn∞ fxch intrukcφ, kterΘ na 486 zabφrajφ Φas(na pentiu u╛ ne). Navφc koneΦnß podmφnka je zkombinvanß s poΦßteΦnφ dal╣φho testu, tak╛e se u╣et°φ jeden skok.

Provedl jsem je╣t∞ testy na SUNech a Siliconech GCC versus p°ekladaΦ dodßvan² s OS. V²sledky jsou v tabulce 2 a 3

Musφm °φct, ╛e v²sledky m∞ opravdu p°ekvapily, proto╛e jsou mnohem vyrovnan∞j╣φ, ne╛ u DOSov²ch p°ekladaΦ∙. Napadly m∞ nßsledujφcφ vysv∞tlenφ:

• GCC generuje hor╣φ k≤d na neintelov²ch platformßch
• SUN a SGI ud∞lali tak dobr² kompilßtor, ╛e mu v╣echny komerΦnφ DOSovΘ nesahajφ ani po kotnφky
• Sparc a Mips majφ jednodu╣╣φ prßci s floating point registry a proto generovßnφ k≤du je pro n∞ jednodu╣╣φ.

Proto jsem ud∞lal dal╣φ test. Nahradil jsem long double za int. Te∩ je u╛ celß matematika jednoduchß i na Intelu. V²sledky jsou v tabulce 4.

Po°ßd je ale Borland C o hodn∞ pomalej╣φ. To, ╛e GCC by generovalo na mipsech hor╣φ k≤d se mi zdß nepravd∞podobnΘ, proto╛e optimalizery jsou z velkΘ Φßsti nezßvislΘ na architektu°e. A tak si myslφm, ╛e to bude tak p∙l na p∙l mezi lep╣φ architekturou a tφm, ╛e UNIXovΘ kompilßtory b²vajφ kvalitnφ.

Myslφm, ╛e testy mluvφ samy za sebe a ukazujφ, ╛e tady GNU odvedlo opravdu dobrou prßci. Psanφ rutin v assembleru, aby byly rychlej╣φ u╛ skoro nemß smysl. Je to d∙vod, proΦ programy v Linuxu b²vajφ rychlej╣φ (klasick² p°φklad je Doom). Mß to bohu╛el i nev²hodu. P°e╛havenΘ stroje Φasto programy kompilovanΘ pomocφ GCC nevydr╛φ (moje 486DX2 normßln∞ pracujφcφ v pokojovΘ teplot∞ se p°i kompilaci jßdra zah°eje tak, ╛e na nφ neudr╛φm ruku). LidΘ si Φasto myslφ, ╛e je to chyba programu. TakΘ proces kompilace je docela slo╛it² a tak to kompilßtoru chvφli trvß.

Poslednφ dost d∙le╛itß v∞c je to, ╛e oproti Borland C je GCC tΘm∞° bez chyb. B∞hem ╣estiletΘho pou╛φvßnφ jsem narazil jen asi na t°i problΘmy. Jinak v╛dy v╣echno fungovalo.