Bloki podstawowe i grafy obliczeń (Basic blocks & Flow graphs)



Pobieranie 34.56 Kb.
Data04.05.2016
Rozmiar34.56 Kb.
Bloki podstawowe i grafy obliczeń (Basic blocks & Flow graphs)
Graf obliczeń jest to skierowany graf tworzony na podstawie kodu trójadresowego. Ścieżki w grafie wskazują możliwą kolejność wykonywania obliczeń. Wierzchołkami grafu są bloki podstawowe. Blok podstawowy jest ciągiem instrukcji trójadresowych, takich że jeśli sterowanie zostanie przekazane do pierwszej instrukcji tego bloku, to opuści blok po wykonaniu ostatniej instrukcji (nie będzie wewnątrz bloku skoków ani rozkazu stopu).

Dzielenie kodu trójadresowego na bloki podstawowe :

(1) wyodrębniamy pierwsze instrukcje (liderów)

(a) pierwsza instrukcja kodu trójadresowego jest liderem

(b) każda instrukcja, do której prowadzi skok warunkowy lub bezwarunkowy jest liderem

(c) każda instrukcja, która następuje bezpośrednio po skoku warunkowym lub

bezwarunkowym jest liderem

(2) każdy blok rozpoczyna się swoim liderem i zawiera wszystkie instrukcje, aż do

napotkania kolejnego lidera lub końca kodu.
Mając podział na bloki podstawowe tworzymy graf obliczeń uwzględniający możliwą kolejność wykonywania obliczeń. Pierwszy blok jest wyróżnionym wierzchołkiem początkowym w grafie .W grafie biegnie krawędź od wierzchołka Bi do Bj, jeśli:

(a) istnieje skok warunkowy lub bezwarunkowy z ostatniej instrukcji Bi do pierwszej instrukcji Bj

(b) Bj bezpośrednio następuje po Bi w kodzie trójadresowym , przy czym Bi nie kończy się skokiem bezwarunkowym.


Przykład :

void quicksort(m,n)

int m , n;

{

int i , j;



int v, x;

if (n <= m ) return;



Początek

i = m – 1;

j = n; v = a[n];

while(1){

do i = i + 1; while (a[i] < v );

do j = j – 1; while (a[j] > v );

if ( i >= j ) break;

x = a[i] ; a[i] = a[j]; a[j] = x;

}

x = a[i] ; a[i] = a[n] ; a[n] = x;



Koniec

quicksort(m,j); quicksort(i + 1 ,n);

}

Założenie : zmienna „S” zawiera sizeof(int)


(1) i := m – 1

(2) j := n

(3) t1 := s * n B1

(4) v := a[t1]


(5) i := i + 1

(6) t2 := s * i

(7) t3 := a[t2] B2

(8) if t3 < v goto(5)




(9) j := j – 1

(10) t4 := s * j

(11) t5 := a[t4] B3

(12) if t5 > v goto (9)
(13) if i ≥ j goto(23) B4


(14) t6 := s * i

(15) x := a[t6]

(16) t7 := s * i

(17) t8 := s * j

(18) t9 := a[t8] B5

(19) a[t7] := t9

(20) t10 := s * j

(21) a[t10] := x

(22) goto(5)


(23) t11 := s*i

(24) x := a[t11]

(25) t12 := s * i

(26) t13 := s * n

(27) t14 := a[t13] B6

(28) a[t12] := t14

(29) t15 := s * n

(30) a[t15] := x







Transformacje nie zmieniające funkcji realizowanych przez program

  1. Eliminacja wspólnych podwyrażeń

    1. lokalna (wewnątrz bloków)




    1. globalna (w całym grafie)



2. Propagacja kopiowania




a := b zastąpić a := b



c := a c := b
PRZED : PO :


x := t3

a[t2] := t5

a[t4] := x

goto B2




x := t3

a[t2] := t5

a[t4] := t3

goto B2

B 5 B5 (podobnie w bloku B6)

Pozornie nie przynosi efektów, ale : ...
3. Eliminacja martwego kodu
Eliminuje się te instrukcje trójadresowe, które nadają wartość takim zmiennym, które nie będą potem używane.
PRZED : PO:


a[t2] := t5

a[t4] := t3

goto B2


x := t3

a[t2] := t5

a[t4] := t3

goto B2

B5 wyeliminowane


4. Zmienne indukowane i redukcja mocy

Zmienne indukowane: zmienne ściśle ze sobą związane w pętli wewnętrznej.

Redukcja mocy, przykład: zamiana mnożenia na dodawanie,

zamiana potęgowania na mnożenie.

Wykrycie zmiennych indukowanych pozwala na redukcję mocy kodu.



Zmienne indukowane :

j t4

zmiana j o 1 powoduje zmianę t4 o s  możliwość redukcji mocy

Można teraz wyeliminować zmienną j w bloku B3 (oraz „i” w bloku B2) zmieniając warunek w B4


Ostatecznie :


5.Przemieszczanie kodu

Przykład :

while ( i <= limit – 2) { ...

/* instrukcje nie zmieniające wartości zmiennej ”limit” */

}

może być przekształcone do postaci równoważnej :


t = limit – 2;

while ( i <= t ) { ...

/* instrukcje nie zmieniające wartości zmiennych ”limit” i ”t” */

}

Optymalizacja ”przez szparkę” (Peephole optimization – dosłownie :

”optymalizacja przez judasza”)
1. Eliminacja zbędnych skoków
Przykład:
if a

goto L1 instrukcja zbędna

L1 : if c < d goto L2

goto L4


L2 : if e < f goto L3

goto L4


if a < b goto L3

if c < d goto L2 można wyeliminować „skok przez skok”

goto L4 zmieniając warunek na przeciwny

L2 : if e < f goto L3

goto L4

if a < b goto L3



if c >= d goto L4

if e < f goto L3 optymalizacja tego fragmentu

goto L4 uzależniona jest od położenia

etykiet: L3 i L4

2. Eliminacja nieosiągalnego kodu


Przykład :

# define debug 0

...

if (debug) { ...



/* print debug information */

}

if debug = 1 goto L1



goto L2 eliminacja ”skoku przez skok”

L1: /* print debug information */

L2:

if debug ≠ 1 goto L2 uwzględnianie tego, że



/* print debug information */ debug = 0

L2:


if 0 ≠ 1 goto L2

/* print debug information */ kod nieosiągalny

L2: można usunąć

goto L2 Eliminacja zbędnego skoku powoduje

L2: całkowite wyeliminowanie rozważanego

fragmentu kodu


3.Optymalizacja przebiegu sterowania


Przykład:

goto L1 goto L2

... ...

L1: goto L2 L1: goto L2



if a < b goto L1 if a < b goto L2

... ...

L1: goto L2 L1: goto L2

goto L1 if a < b goto L2

... goto L3

goto L4 ...

L1: if a < b goto L2 L3 : ...

L3: ...


Zakładamy, że do L1 jest tylko jeden skok

(liczba skoków do każdej etykiety może być

pamiętana w tablicy symboli)
Optymalizacja tego typu nie zmniejsza liczby instrukcji ale zmniejsza liczbę wykonywanych skoków w czasie wykonania programu.

4.Eliminacja tożsamości algebraicznych


Przykład:


x := x + 0 mogą być wyeliminowane

x := x * 1 gdyż faktycznie nie zmieniają

wartości zmiennej x


5. Redukcja mocy
Przykład :
y := 2 * x
może być zastąpione przez
y := x + x
gdyż mnożenie trwa znacznie dłużej niż dodawanie





©absta.pl 2016
wyślij wiadomość

    Strona główna