IAO39 Překlad a překladače Opakování - RICS procesory ■ limitovaný počet instrukcí, jednotná délka ■ jednoduché adresní modý, load/store, hodné registru ■ delaý branches, brach prediction, out-of-order execution ■ superskalarní (MIPS - 2xFPU, 2xALU, adresace) ■ superpipeline (ANDES) ■ výrovnavací pameti IA039 2 Jaro 2010 Optimalizující překladač: ■ překlad do mezijazyka ■ optimalizace ■ meziprocedurainí analýza ■ optimalizace cyklU ■ globalní optimalizace ■ generovaní kódu ■ vyuzití všech jednotek IA039 3 Jaro 2010 Mezijazyk ■ Ctverice (obecne n-tice) ■ instrukce: operátor, dva operandy, výsledek ■ Příklad * Přiřazení: x := Y op Z ■ Pamet: přes docasne promenne tn ■ Skoky: podmínka podtana samostatne ■ Skoky: na absolutní adresy ÍA039 4 Jaro 2010 Základní překlad while ( j < n ) { k = k + j*2 m = j*2 } B:: tl • = j t2 : = n t3 : = tl < t2 (B) t3 (C) TRUE t4 : = k t5 : = j t6 : = t5*2 t7 : = t4+t6 k : = t7 t8 : = j t9 : = t8*2 m : = t9 t10 : = j tll : = tl0+l j : = tll (A) TRUE C:: IA039 5 Jaro 2010 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 Acýclic Graph) ■ Optimalizace uvnitř bloků ■ Odstranení opakovaných (pod)výrazů ■ Odstranení prebýtecných promenných IA039 6 Jaro 2010 Directed Acyclic Graph B:: t4 • — k t5 j t6 t5*2 J,t5,t8,t10 K,t4 "1" t7 t4+t6 \ / k t7 \ / \ / / t8 j \ / t9 m t8*2 t9 t6,t9,M\. t10 j t11 • — t10+1 t7,K ® tn,j j • — t11 (A) TRUE IA039 7 Jaro 2010 Modifikovaný překlad B:: t4 • — k t5 j t6 t5*2 B:: t4 : = k t7 t4+t6 t5 : = j k t7 t6 : = t5*2 t8 j m : = t6 t9 t8*2 t7 : = t6+t4 m t9 k : = t7 t10 j : = t5+1 t11 t10+1 j : = t11 j t11 jmP (A) TRUE (A) TRUE IA039 8 Jaro 2010 Další pojmy ■ Proměnné ■ Definice a místa použití ■ Cykly ■ Proces generování cílového kodu ■ SouCastí tžv. peephole optimalizace IA039 9 Jaro 2010 Optimalizovaný překlad B:: tl • = j t2 : = n t3 : = tl < t2 jmp (B) t3 jmp (C) TRUE t4 := k t5 := j t6 := t5*2 t7 := t4+t6 k := t7 t8 := j t9 := t8*2 m := t9 t10 := j tll := t10+1 j := tll jmp (A) TRUE C:: A:: tl := j t2 := n t4 := k t9 := m tl2 := tl+tl t3 := tl >= t2 jmp (Bl) t3 B:: t4 := t4+tl2 t9 := tl2 tl := tl+l tl2 := tl2+2 t3 := tl < t2 jmp (B) t3 Bl:: k := t4 m := t9 C:: IA039 10 Jaro 2010 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ý kod ■ setrení cache pro instrukce IA039 11 Jaro 2010 Klasické optimalizace II ■ Strength reduction ■ Příklad: K**2 => K*K ■ Přejmenovaní promeénných ■ Příklad x = y*z; x0 = y*z; q = r+x+x; => q = r+x0+x0; x = a+b x = a+b ■ Odstranovaní spoleCných podvýrazU (podstatne zejména pro výpoCet adres prvkU polí) IA039 12 Jaro 2010 Klasické optimalizace III ■ Přesun invariantního kódu z cýklů ■ Zjednodusení indukcních promenných (výrazu s) ■ A(I) je veetsinou pocítano jako: address = base_address(A) + (I-1)*sizeof_datatype(A) coz lze snadno v linearním cýklu převest na mimo cyklus: address = base_address(A) - sizeofdatatype(A) v cyklu: address = address + sizeofdatatype(A) ■ Přiřazení registru promeenným IA039 13 Jaro 2010 Odstraňovaní smetí ■ Podprogramy, makra ■ inlining ■ Podmínene vyrazy ■ Reorganizace sloZitych vyrazU ■ Nadbytecne testy (if versus case) ■ Podmínene vyrazy uprostřed cyklU ■ Nezavisle na cyklu ■ Zavisle na cyklu * Nezavisle na iteraci * Zavisle mezi iteracemi iA039 14 Jaro 2010 Podmíněné výrazy - příklad DO I=1,K IF (N .EQ 0) THEN A(I)=A(I)+B(I)*C ELSE A(I)=0 ENDIF IF (N .EQ 0) THEN DO I=1,K A(I)=A(I)+B(I)*C CONTINUE ELSE DO I=1,K A(I)=0 CONTINUE ENDIF IA039 15 Jaro 2010 Odstraňovaní smetí II ■ Redukce ■ min (nebo max): for(i=0;i z) ? a[i] : z; ■ jak obejít rekurzivní zavislost: for(i=0;i z0) ? a[i] : z0; z1=(a[i+1] > zl) ? a[i+1] : zl; } z=(z0 < z1) ? z1 : z0; IA039 16 Jaro 2010 Redukce - Asociativní transformace ■ Numerická nepřesnost: 4 platna desetinná místa (X + Y) + Z = (.00005 + .00005) + 1.0000 .00010 + + 1.0000 = 1.0001 ale X + (Y + Z) = .00005 + (.00005 + 1.0000) = .00005 + 1.0000 = 1.0000 ■ Redukce DO I=1,N SUM=SUM+A(I)*B(I) Redukce s rekurzivní zavislostí - mUžeme použít stejný trik jako u min redukce? IA039 17 Jaro 2010 Odstraňování smetí III ■ Skoký ■ Konverze týpU REAL*8 A(1000) REAL*4 B(1000) DO I 1=1,1000 A(I)=A(I)*B(I) ■ Rucní optimalizace ■ Spolecne podvýražý ■ Přesun kodu ■ Zpracovaní polí (inteligentní prekladac, C a ukazatele) IA039 18 Jaro 2010 Optimalizace cyklu Cíle: ■ Redukce reZie ■ Zlepsení přístupu k pameti (cache) ■ Zvýsení paralelismu IA039 19 Jaro 2010 Dátové závislosti I Flow Dependencies (backward dependencies) ■ Príklad: DO I=2,N,2 DO I=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-Dépéndénciés ■ Štandardne prejmenovaní promenných ■ Príklad DO I=1:N DO I=1:N A(I) = B(I) * E B(I) = A(I+2) * C A'(I)= B(I) * E DO I=1:N B(I) = A(I+2) * C DO I=1:N A(I) = A'(I) IA039 20 Jaro2010 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í" ■ MUZe byt problem zjistit, ktera je ta „poslední" IA039 21 Jaro 2010 Rozvoj cyklu (loop unrolling) I ■ Telo cyklu se několikrát zkopíruje: DO I=1,N A(I)=A(I)+B(I)*C DO I=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 Járo 2010 Rozvoj cyklu (loop unrolling) II Hlavní smýsl ■ Snízení rezie * Snízení poctu pruchodu cýklem ■ Zvýsení paralelizace (i v ramci jednoho procesoru) * Software pipelining Pre- a postconditioning loops ■ Adaptace na skutecný pocet pruchodu IA039 23 Jaro 2010 Rozvoj cyklu (loop unrolling) III ■ Nevhodné cykly ■ Malý poCet iterací —► úplny rozvoj cyklů ■ „Tlústé" (=velké) cykly: samy obsahují dostatek příležitostí k paralelizaci ■ Cykly s volaním procedúr: souvislost s rozvojem procedúr (inlining) ■ Cykly s podmínenymi vyrazy: spíse starsí typy procesorů ■ „Rekurzivní" cykly: cykly s vnitrními závislostmi (a[i]=a[i]+a[i-1]*b) IA039 24 Jaro 2010 Problémy s rozvojem cyklu ■ Rozvoj špatným počtem iterací ■ Zahlcení registrů ■ Výpadky vyrovnávací pameti instrukcí (příliš velký cýklůš) ■ Hardwarove problemý ■ Především na můltiprocešorech še šdílenoů pametí (cache koherence, přetíZení šbernice) ■ Specialní případý: rozvoj vnejších cýklů, špojovaní cýklů IA039 25 Jaro 2010 Spojování cyklu ■ opakovane použití dat ■ vetsí teio cýklu ■ kompilator zvladne sam, pokud mezi cýklý není jiný kod a[0]=b[0]+1 for(i=0;i DO 10 I=1,N A(I,J)=B(I,J)+C(I)*D A(I,J)=B(I,J)+C(J)*D IA039 28 Jaro 2010 Optimalizace přístupu k paměti II ■ Skládání do bloků ■ Príklád: DO I=1,N DO 10 J=1,N A(J,I)=A(J,I)+B(I,J) DO I=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+1) 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+1) IA039 29 Járo 2010 Optimalizace přístupu k paměti III ■ Nepříma adresace ■ Príklad: b[i]=a[i+k]*c, hodnota k neznama pri prekladu a[k[i]] += b[i]*c ■ Pouzití ukazatelu ■ Nedostatecna kapacita pameti ■ „Rucní" zpracovaní ■ Virtualní pamet IA039 30 Jaro 2010