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 superskalarni (MIPS - 2xFPU, 2xALU, adresace) superpipeline (ANDES) vyrovnávací paměti IA039 2 Jaro 2008 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 Jaro 2008 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é tn ■ Skoky: podmínka počítána samostatně ■ Skoky: na absolutní adresy IA039 4 Základní while ( j < n ) { k = k + j*2 m = j*2 } IA039 5 překlad B ti : = j t2 : = n t3 : = ti < 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 tlO : = j tll : = tlO+1 j : = tll jmp (a; ) TRUE Jaro 2008 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 2008 t4 t5 tß t7 t8 t9 m tlO til j Directed Acyclic Graph = k J = t5*2 = t4+t6 = t7 = J = t8*2 = t9 = J = tlO+1 = tll HO" J,t5,t85t10 t6,t9,M 11^ ii 1 jmp (A) TRUE Jaro 2008 Modifikovaný překlad B: : t4 t5 t6 t7 k t8 t9 m tlO tll j = k J = t5*2 = t4+t6 = t7 = J = t8*2 = t9 = J = tlO+1 = tll B: : t4 t5 t6 m t7 tll j = k J = t5*2 = t6 = t6+t4 = t7 = t5+l = tll jmp (A) TRUE jmp (A) TRUE IA039 8 Jaro 2008 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 Jaro 2008 Optimalizovaný překlad ti • = j t2 ; = n t3 ; = ti < 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 tlO ; = j til ; = tlO+1 j ; = til jmp ca: ) TRUE B Bl ti = J t2 = n t4 = k t9 = m tl2 = tl+tl t3 = ti >= t2 jmp :B1) t3 t4 = t4+tl2 t9 = tl2 ti = tl+1 tl2 = tl2+2 t3 = ti < t2 jmp :B) t3 k = t4 m = t9 10 Jaro 2008 Klasické Propagace kopírováním Příklad: X = Y \ X Z = 1. + X / z Zpracování konstant ■ propagace konstant Odstranění mrtvého kódu ■ nedosažitelný kód ■ šetření cache pro instrukce IA039 )ptimalizace = Y = 1. + Y 11 Jaro 2008 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ýrazu (podstatné zejména pro výpočet adres prvků polí) IA039 12 Jaro 2008 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) + (I-l)*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 2008 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 2008 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 Jaro 2008 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 Redukce - Asociativní transformace ■ Numerická nepřesnost: (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 1=1,N SUM=SUM+A(I)*B(I) redukce s rekurzivní závislostí - můžeme použít stejný trik jako u min redukce? IA039 17 Jaro 2008 Odstraňovaní smetí 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 2008 Optimalizace cyklů - Cíle: ■ Redukce režie ■ Zlepšení přístupu k paměti (cache) ■ Zvýšení paralelismu IA039 19 Jaro 2008 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 DO 1=1:N A'(I) = B(I) * E A(I) = B(I) * E =^> B(I) = AQ+2) * C B(I) = A(I+2) * C A(I) = A'(I) IA039 20 Jaro 2008 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 2008 Rozvoj cyklů (loo| 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 unrolling) I Jaro 2008 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 (iniining) ■ 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 2008 9111 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 2008 ■ opakované použití dat ■ větší tělo cyklu ■ kompilátor zvládne sám, for(i=0;i- c[i]=a[i]/2 d[i-l]=l/c[i] } d[n-l]=l/c[n+l] 26 Jaro 2008 Rozvoj vnějších cyklů ■ Příklad DO 1=1,N DO J=1,N A(I)=A(I)+B(I,J)*C(J) ■ A(l) je v vnitřním cyklu konstanta, C(J) se prochází správně ■ B(I,J) se prochází opačně! DO 1=1,N,4 DO J=1,N A(I+0)=A(I+0)+B(I+0,J)*C(J) A(I+1)=A(I+1)+B(I+1,J)*C(J) A(I+2)=A(I+2)+B(I+2,J)*C(J) A(I+3)=A(I+3)+B(I+3,J)*C(J) IA039 27 Jaro 2008 Optimalizace přístupů k paměti ■ Optimální: nejmenší krok (práce s cache) ■ Práce s maticemi - C vs. Fortran ■ C: ukládá po řádcích, nejrychleji se mění pravý index ■ Fortran: ukládá pa sloupcích, nejrychleji se mění levý index ■ Obrácení indexu ■ Příklad: DO 1=1,N DO J=1,N DO 10 J=1,N =^ 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 2008 Optimalizace přístupů k paměti II ■ Blokování ■ 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+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 Jaro 2008 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á pamět ■ „Ruční" zpracování ■ Virtuální pamět IA039 30 Jaro 2008