IA039
Překlad a překladače
Optimalizující překladač
* Základní principy práce překladače
* 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 2 Jaro 2008
Příklad
while ( j < n ) {
k = k + j * 2
m = j * 2
}
IA039 3 Jaro 2008
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
Základní překlad
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 5 Jaro 2008
Modifikovaný překlad
B: : t4 := k
t5 := j
t6 := t5*2
m := t6
t7 := t6+t4
k := t7
tll := t5+l
j := tll
jmp (A) TRUE
IA039 6
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 7 Jaro 2008
Optimalizovaný překlad
tl := j
t2 := n
t4 := k
t9 := m
tl2 := tl+tl
t3 := tl >= t2
jmp (Bl) t3
t4 := t4+tl2
t9 := tl2
tl := tl+1
tl2 := tl2+2
t3 := tl < t2
jmp (B) t3
k := t4
m := t9
8 Jaro 2008
Klasické optimalizace
* Propagace kopírováním
* Příklad:
X = Y X = Y
Z = 1 . + X Z = 1 . + Y
* Zpracování konstant
* Odstranění mrtvého kódu
IA039 9 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 10 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 11 Jaro 2008
Přenositelnost a efektivita
* Aliasing
* Dva různé formální argumenty vs. stejné aktuální argumenty
* Typy formálních a konkrétních argumentů
* Pamět
Equivalence
* Zarovnání
IA039 12 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 13 Jaro 2008
Odstraňování smetí II
* Redukce
* min, max
* Skoky
* Konverze typů
* Ruční optimalizace
* Společné podvýrazy
* Přesun kódu
* Zpracování polí (inteligentní překladač, C a ukazatele)
IA039 14 Jaro 2008
Optimalizace cyklů
- Cíle:
* Redukce režie
* Zlepšení přístupu k paměti (cache)
* Zvýšení paralelismu
IA039 15 Jaro 2008
Datové závislosti
* Flow Dependencies (backward dependencies)
* A(2:N) = A(1:N-1)+B(2:N)
* Anti-Dependencies
* Standardně přejmenování proměnných
- Příklad
A(I) = B(I) * E
B(I) = AQ+2) * C
lze přepsat na
A'(1:N) = B(1:N) * E
B(1:N) = A(3:N+2) * C
A(1:N) = A'(1:N)
IA039 16
Datové závislosti
* 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í".
IA039 17 Jaro 2008
Rozvoj cyklů (loop unrolling)
* Tělo cyklu se několikrát zkopíruje (změna velikosti iteračního
kroku)
* 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 18 Jaro 2008
Rozvoj cyklů II
* 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 19 Jaro 2008
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řípad: Rozvoj vnějších cyklů
IA039 20 Jaro 2008
Asociativní transformace
* Souvisí především s paralelismem
* Redukce
* Skalární součin (daxpy)
* Násobení matic
* Obracení cyklů
* Závislé výpočty
IA039 21 Jaro 2008
Optimalizace přístupů k paměti
* Optimální: nejmenší krok (práce s cache)
* FORTRAN: levý index
* C: pravý index
* Příklad:
DO 10 J=1,N
DO 10 1=1,N
A(I,J)=B(I,J)+C(I,J)*D
10 CONTINUE
DO 10 J=1,N
DO 10 1=1,N
A(J,I)=B(J,I)+C(J,I)*D
10 CONTINUE
IA039 22 Jaro 2008
Optimalizace přístupů k paměti II
* Blokování
* Příklad:
DO 10 1=1,N
DO 10 J=1,N
A(J,I)=A(J,I)+B(I,J)
10 CONTINUE
DO 10 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)
10 CONTINUE
IA039 23 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 24 Jaro 2008