Wybrane zagadnienia związane z przydziałem pamięci



Pobieranie 236,46 Kb.
Strona1/3
Data22.02.2018
Rozmiar236,46 Kb.
  1   2   3



Generacja kodu :

Generator kodu docelowego:



We : kod pośredni niezależny sprzętowo
: kod assemblera

Wy : kod pośredni zależny sprzętowo

: kod absolutny


Problem generacji optymalnego kodu zależnego sprzętowo jest matematycznie nierozwiązywalny bądź też praktycznie niemożliwy do rozwiązania. Dlatego też w praktyce zadowalamy się technikami heurystycznymi dającymi dobry kod, ale nie zawsze optymalny.

Problemy:

-przydział zasobów, efektywne wykorzystanie zasobów

-wybór instrukcji, minimalizacja kosztów (czasowych)


Przykład: a := a + 1

-zmiana kolejności obliczeń, itd.

Generowanie kodu dla bloków podstawowych
(a) Informacje nt. ”życia” i ”używania” zmiennych
(i) x := y op z (i) definiuje ”x”,

: ”x” nie występuje następne użycie ”x” w (j),

: ”x” żyje.

(j) ... := x op ... (j) używa ”x” obliczonego w (i)

odtąd ”x” może być martwy

o ile nie będzie dalej używany


Badanie ”życia” i ”używania”:

Znajduje się koniec bloku podstawowego . Analiza grafu przepływu programu daje odpowiedź na pytanie: jaki jest stan zmiennych (”życie”) na końcu danego bloku . Informacje te zawarte są w tablicy symboli. Następnie przegląda się poszczególne zapisy w bloku podstawowym w kolejności odwrotnej (od końca do początku). Stosując poniższy algorytm można ustalić, czy w danym miejscu kodu trójadresowego zmienna żyje oraz gdzie będzie użyta. Jeżeli w trakcie przeszukiwania napotkano zapis:

(i) x := y op z

(1) Dla instrukcji (i) określamy stan zmiennych na podstawie aktualnej zawartości tablicy

symboli.

(2) Wstawiamy do tablicy symboli dla ”x” (wynik) ”NIE ŻYJE” oraz ”BRAK

NASTĘPNEGO UŻYCIA”

(3) Wstawiamy do tablicy symboli dla ”y” oraz ”z” (argumenty) „żyje” oraz „NASTĘPNE



UŻYCIE w (i)”
Kolejność kroków (1) (2) (3) nie może być zmieniona , gdyż ta sama zmienna może być równocześnie argumentem oraz wynikiem.

Przykład:




Wynik

Argument 1

Argument 2




życie

użycie

życie

użycie

życie

użycie

(1) t1 := a * a

tak

(4)

tak

(2)

tak

(2)

(2) t2 := a* b

tak

(3)

tak




tak

(5)

(3) t3 := 2 * t2

tak

(4)







nie

-

(4) t4 := t1 + t3

tak

(6)

nie

-

nie

-

(5) t5 := b * b

tak

(6)

tak




tak




(6) t6 := t4 + t5

tak

(7)

nie

-

nie

-

(7) x := t6

tak

(dalej)

nie

-






x := a * a + 2 * a * b + b * b



a

b

x

t1

t2

t3

t4

t5

t6

Ż

U

Ż

U

Ż

U

Ż

U

Ż

U

Ż

U

Ż

U

Ż

U

Ż

U

tak




tak




tak

nie

-


nie

-

nie

-

nie

-

nie

tak


-

(6)


nie

tak


-

(6)


nie

tak


nie

-

(7)


-
Tablica symboli

0 stan początkowy

I ustalenie stanu zmiennych dla (7)

II zmiana tablicy symboli dla wyniku (7)

III zmiana tablicy symboli dla argumentu (7)

I ustalenie stanu zmiennych dla (6)

II zmiana tablicy symboli dla wyniku (6)

III zmiana tablicy symboli dla argumentów (6)



itd.

”Życie” zmiennych tymczasowych


t1 t2 t3 t4 t5 t6

(1) t1 := a * a

(2) t2 := a * b t1 i t2 żyją równocześnie

(3) t3 := 2 * t2 t1 i t3 żyją równocześnie

(4) t4 := t1 + t3

(5) t5 := b * b t4 i t5 też

(6) t6 := t4 + t5

(7) x := t6 t1 t2 t2 t1 t2 t1

Na podstawie informacji o ”życiu” można dokonać lokalizacji zmiennych tymczasowych według generalnej zasady, że dwie zmienne mogą zajmować tę samą lokalizacją, gdy nie są równocześnie ”żywe”
Stąd:
(1) t1 := a * a

(2) t2 := a * b

(3) t2 := 2 * t2

(4) t1 := t1 +t2

(5) t2 := b * b

(6) t1 := t1 + t2

(7) x := t1




  1   2   3


©operacji.org 2017
wyślij wiadomość

    Strona główna