IA039 Překlad a překladače Opakování - RICS procesory ■ limitovaný počet instrukcí, jednotná délka ■ jednoduché adresní módy, load/store, hodně registrů ■ delay branches, brach prediction, out-of-order execution ■ superskalární (MIPS - 2xFPU, 2xALU, adresace) ■ superpipeline (ANDES) ■ vyrovnávací paměti IA039 2 Optimalizující překladač ■ překlad do mezijazyka ■ optimalizace ■ meziprocedurální analýza ■ optimalizace cyklů ■ globální optimalizace ■ generování kódu ■ využití všech jednotek IA039 3 Mezijazyk ■ Čtveřice (obecně n-tice) ■ Instrukce: operátor, dva operandy, výsledek ■ Příklad * Přiřazení: x := Y op z ■ Pamět: přes dočasné proměnné tra ■ Skoky: podmínka počítána samostatně ■ Skoky: na absolutní adresy IA039 4 Základní překlad while ( j < n ) { k = k + j*2 m = j*2 B: : tl := J t2 := n t3 := tl < jmp (B) t3 jmp (C) TRUE t4 := k t5 := J t6 := t5*2 t7 := t4+t6 k := 17 t8 := J t9 := t8*2 m := t9 tio := J tll := tlO+1 j := tll (A) TRUE IA039 5 Jaro 2012 Základní bloky ■ Program je pak reprezentován grafem toku (flow graph) ■ Blok -část programu bez skoků ■ Jeden vstupní a jeden výstupní bod ■ Blok jako DAG (Directed Acyclic Graph) ■ Optimalizace uvnitř bloků ■ Odstranění opakovaných (pod)výrazů ■ Odstranění přebytečných proměnných IA039 6 Jaro 2012 Directed Acyclic Graph IA039 7 Jaro 2012 B: : t4 k t5 • — j t6 ' — t5*2 tľ ; = t4+t6 k ; = tľ t8 • = j t9 • = t8*2 m ; = t9 tio • = j tll • = tlO+1 j ; = tll (A) TRUE Modifikovaný překlad B: : t4 := k t5 j t6 := t5*2 m := t6 tľ := t6+t4 k := tľ tll := t5+l J := tll (A) TRUE IA039 8 Jaro 2012 Další pojmy ■ Proměnné ■ Definice a místa použití ■ Cykly ■ Proces generování cílového kódu ■ Součástí tzv. peephole optimalizace IA039 9 Optimalizovaný překlad tl := J t2 := n A: : tl := j t3 := tl < t2 t2 := n jmp (B) t3 t4 := k jmp (C) TRUE t9 := m t4 := k tl2 := tl+tl t5 := J t3 := tl >= t2 t6 := t5*2 jmp (Bl) t3 tl := t4+t6 B: : t4 := t4+tl2 k := t7 t9 := tl2 t8 := J tl := tl+1 t9 := t8*2 tl2 := tl2+2 m := t9 t3 := tl < t2 tlO := J jmp (B) t3 til := tlO+1 Bl: : k := t4 j := til m := t9 (A) TRUE C: : C: : IA039 10 Jaro 2012 Klasické optimalizace ■ Propagace kopírováním ■ Příklad: X = Y X = Y Z = 1. + X Z = 1. + Y ■ Zpracování konstant ■ propagace konstant ■ Odstranění mrtvého kódu nedosažitelný kód ■ šetření cache pro instrukce IA039 11 Jaro 2012 Klasické optimalizace II Strength reduction ■ Příklad: K**2 K*K Přejmenování proměnných ■ Příklad x = y*z; xO = y*z; q = r+x+x; q = r+xO+xO; x = a+b x = a+b Odstraňování společných podvýrazů (podstatné zejména pro výpočet adres prvků polí) IA039 12 Jaro 2012 Klasické optimalizace III ■ Přesun invariantního kódu z cyklů ■ Zjednodušení indukčních proměnných (výrazů s) ■ A(i) je většinou počítáno jako: address = base_address(A) + (1-1)*sizeof_datatype(A) což lze snadno v lineárním cyklu převést na mimo cyklus: address = base_address(A) - sizeof_datatype(A) v cyklu: address = address + sizeof_datatype(A) ■ Přiřazení registrů proměnným IA039 13 Jaro 2012 Odstraňování smetí ■ Podprogramy, makra ■ Inlining ■ Podmíněné výrazy ■ Reorganizace složitých výrazů ■ Nadbytečné testy (if versus case) ■ Podmíněné výrazy uprostřed cyklů ■ Nezávislé na cyklu ■ Závislé na cyklu * Nezávislé na iteraci * Závislé mezi iteracemi IA039 14 Jaro 2012 Podmíněné výrazy - příklad DO 1=1,K IF (N .EQ 0) THEN A(I)=A(I)+B(I)*C ELSE A(I)=0 END IF IF (N .EQ 0) THEN DO 1=1,K A(I)=A(I)+B(I)*C CONTINUE ELSE DO 1=1,K A(I)=0 CONTINUE END IF IA039 15 Odstraňování smetí II ■ Redukce min (nebo max): for(i=0;i z) ? a[i] : z; ■ jak obejít rekurzivní závislost: for(i=0;i zO) ? a[i] : zO; zl=(a[i+l] > zl) ? a[i+l] : zl; } z=(zO < zl) ? zl : zO; IA039 16 Jaro 2012 Redukce - Asociativní transformace ■ Numerická nepřesnost: 4 platná desetinná místa (X + Y) + Z = (.00005 + .00005) + 1.0000 .00010 + + 1.0000 ale X + (Y + Z) = .00005 + (.00005 + 1.0000) .00005 + 1.0000 ■ Redukce DO 1=1,N SUM=SUM+A(I)*B(I) Redukce s rekurzivní závislostí - můžeme použít stejný trik jako u min redukce? = 1.0001 = 1.0000 IA039 17 Jaro 2012 Odstraňování smetí III ■ Skoky ■ Konverze typů REAL*8 A(1000) REAL*4 B(1000) DO I 1=1,1000 A(I)=A(I)*B(I) ■ Ruční optimalizace ■ Společné podvýrazy ■ Přesun kódu ■ Zpracování polí (inteligentní překladač, C a ukazatele) IA039 18 Jaro 2012 Optimalizace cyklů - Cíle: ■ Redukce režie ■ Zlepšení přístupu k paměti (cache) ■ Zvýšení paralelismu IA039 19 Jaro 2012 Datové závislosti I ■ Flow Dependencies (backward dependencies) ■ Příklad: DO 1=2,N,2 DO 1=2,N =>• A(I)=A(I-1)+B(I) A(I)=A(I-1)+B(I) A(I+1)=A(I-1)+B(I)+B(I+1) ■ Anti-Dependencies ■ Standardně přejmenování proměnných - Příklad DO 1=1 :N A> (I)= B(I) * E DO 1=1:N DO I=1:N A(I) = B(I) * E =>• B(I) = A(I+2) * C B(I) = A(I+2) * C DO I=1:N A(I) = AUD IA039 20 Jaro 2012 Datové závislosti II ■ Output Dependencies ■ Příklad: A(I) = C(I) * 2 A(I+2) = D(I) + E ■ V cyklu je vypočteno několik hodnot konkrétní proměnné, zapsat však lze pouze tu „poslední" ■ Může být problém zjistit, která je ta „poslední" IA039 21 Jaro 2012 Rozvoj cyklů (loop unrolling) I ■ Tělo cyklu se několikrát zkopíruje: DO 1=1,N A(I)=A(I)+B(I)*C DO 1=1,N,4 A(I)=A(I)+B(I)*C A(I+1)=A(I+1)+B(I+1)*C A(I+2)=A(I+2)+B(I+2)*C A(I+3)=A(I+3)+B(I+3)*C IA039 22 Jaro 2012 Rozvoj cyklů (loop unrolling) II ■ Hlavní smysl ■ Snížení režie * Snížení počtu průchodů cyklem ■ Zvýšení paralelizace (i v rámci jednoho procesoru) * Software pipelining ■ Pre- a postconditioning loops ■ Adaptace na skutečný počet průchodů IA039 23 Rozvoj cyklů (loop unrolling) III ■ Nevhodné cykly ■ Malý počet iterací —► úplný rozvoj cyklů ■ „Tlusté" (=velké) cykly: samy obsahují dostatek příležitostí k paralelizaci ■ Cykly s voláním procedur: souvislost s rozvojem procedur (inlining) ■ Cykly s podmíněnými výrazy: spíše starší typy procesorů ■ „Rekurzivní" cykly: cykly s vnitřními závislostmi (a[i]=a[i]+a[i-l]*b) IA039 24 Jaro 2012 Problémy s rozvojem cyklů ■ Rozvoj špatným počtem iterací ■ Zahlcení registrů ■ Výpadky vyrovnávací paměti instrukcí (příliš velký cyklus) ■ Hardwarové problémy ■ Především na multiprocesorech se sdílenou pamětí (cache koherence, přetížení sběrnice) ■ Speciální případy: rozvoj vnějších cyklů, spojování cyklů IA039 25 Jaro 2012 Spojování cyklů opakované použití dat větší tělo cyklu kompilátor zvládne sám, pokud mezi cykly není jiný kód a[0]=b[0]+l for(i=0;i• DO 10 1=1,N A(I,J)=B(I,J)+C(I)*D A(I,J)=B(I,J)+C(J)*D IA039 28 Jaro 2012 Optimalizace přístupů k paměti II ■ Skládání do bloků ■ Příklad: DO 1=1,N DO 10 J=1,N A(J,I)=A(J,I)+B(I,J) DO 1=1,N,2 DO 10 J=1,N,2 A(J,I)=A(J,I)+B(I,J) A(J+1,I)=A(J+1,I)+B(I,J+l) A(J,I+1)=A(J,I+1)+B(I+1,J) A(J+1,I+1)=A(J+1,I+1)+B(I+1,J+l) IA039 29 Jaro 2012 Optimalizace přístupů k paměti III ■ Nepřímá adresace ■ Příklad: b [i] =a [i+k] *c, hodnota k neznáma při překladu a[k[i]] += b[i]*c ■ Použití ukazatelů ■ Nedostatečná kapacita paměti ■ „Ruční" zpracování ■ Virtuální pamět IA039 30