Koncepcja wywołania funkcji z parametrami przenoszonymi przez stos
Zapewne wiele osób zastanawiało się, w jaki sposób radzą sobie kompilatory języków wysokiego poziomu (przykładowo języka C) realizując wywołanie funkcji. Przenoszenie wartości parametrów wywołania funkcji przez rejestry mikrokontrolera jest najprostszą metodą. Ma ona jednak poważne wady, których eliminacja czasami nastręcza trochę problemów. Dodatkowym problemem jest realizacja algorytmów rekurencyjnych (takich, gdzie dochodzi do wywołania funkcji, w której już znajduje się wykonanie programu). Można oczywiście przed rekurencyjnym wywołaniem funkcji przechować zawartość istotnych rejestrów w obszarze zmiennych. Zaproponowana i opisana poniżej metoda stanowi prostą i uniwersalną metodę przekazywania parametrów. Jej podstawowe cechy użytkowe odpowiadają możliwościom jakie oferują języki wysokiego poziomu (nie znaczy to, że popularny kompilator GCC w ten sposób realizuje wywołanie funkcji). Do najważniejszych należy zaliczyć:
- brak konieczności jakiejkolwiek ochrony rejestrów zawierających parametry wywołania funkcji (gdyż te znajdują się w pamięci RAM),
- możliwość realizacji algorytmów rekurencyjnych,
- praktycznie nie istnieje ograniczenie liczby parametrów (limitem jest wielkość pamięci RAM mikrokontrolera).
Kod: Zaznacz cały
; x := Fun ( 3 ) ;
ldi acc,3 ; umieszczenie na szczycie stosu liczby 3 jako
push acc ; parametru wywołania funkcji
rcall Fun ; wywołanie funkcji
pop acc2 ; usunięcie ze stosu parametru wywołania
sts x,acc ; zakładając, że wynik funkcji jest
; pozostawiony w rejestrze acc ....
W wyniku ich wykonania, na stosie zostaje zachowana zawartość rejestru, w którym zapisany jest parametr wywołania funkcji (w tym przypadku jest to stała o wartości 3). Stan stosu przed jej wywołaniem przedstawia rysunek 1.
Wywołanie funkcji (instrukcja rcall Fun) spowoduje zapisanie na stosie dwubajtowej informacji będącej adresem powrotu z jej wywołania. W tym momencie stan stosu przedstawia rysunek 2. Analizując ten rysunek można zauważyć, że bezpośrednio za adresem powrotu z wywołanej funkcji Fun, w pamięci RAM mikrokontrolera znajduje się komórka, która przechowuje parametr jej wywołania. Położenie (adres) w pamięci tej komórki może być określone poprzez zawartość rejestru wskaźnika stosu SP. Tuż po wykonaniu instrukcji rcall Fun, rejestr ten wskazuje na pierwsze wolne miejsce w obszarze stosu. Traktując zawartość rejestru SP jako adres w pamięci RAM, można określić położenie poszczególnych elementów zachowanych na stosie. Pamiętając, że każda operacja zapisu danych na stos oznacza dekrementację zawartości rejestru SP (stos rośnie w dół), to wskazanie SP+1 oraz SP+2 określa położenie w pamięci informacji będącej adresem powrotu z procedury Fun. Analogicznie, zawartość rejestru SP powiększona o 3, jest adresem w pamięci danych komórki przechowującej parametr wywołania. Ponieważ mikrokontrolery AVR nie mają możliwości użycia wskaźnika stosu jako rejestru adresowego w operacjach wymiany danych pomiędzy rejestrami roboczymi i pamięcią, konieczne jest przepisanie zawartości rejestru SP do odpowiedniej pary rejestrów pozwalających na pośrednie adresowanie operandów w instrukcjach przesyłania danych. Do tej roli doskonale nadaje się rejestr Y (yh:yl), gdyż oprócz możliwości adresowania pośredniego operandów (przykładowo instrukcja ld oraz st) możliwe jest użycie go do adresowania z przesunięciem (instrukcje ldd i std). Po wykonaniu następujących instrukcji:
Kod: Zaznacz cały
in yh,sph ;
in yl,spl ;
Kod: Zaznacz cały
ldd acc,y+3 ;
Po wykonaniu wszystkich operacji przewidzianych w wywołanej funkcji, wykonanie programu po napotkaniu instrukcji ret, powraca do miejsca wywołania. W tym momencie stan stosu powraca do postaci, jaka była przed wywołaniem funkcji (rysunek 1) i należy usunąć ze stosu zbędne już informacje będące parametrami wywołania. W tym przypadku wystarczy wykonać instrukcję pop a zawartość odtworzonego rejestru potraktować jako nieistotną.
Powyższa koncepcja przekazywania parametrów wywołania do procedur oraz funkcji może być rozszerzona na większą ich liczbę. Ilustruje to następujący przykład:
Kod: Zaznacz cały
ldi acc,param1 ;
push acc ;
ldi acc,param2 ;
push acc ;
lds acc,param3 ;
push acc ;
lds acc,param4 ;
push acc ;
rcall Fun ;
Po wykonaniu powyższych instrukcji, stan stosu przedstawia rysunek 3. Wykonując analogiczne operacje dotyczące przepisania zawartości rejestru SP do rejestru adresowego Y, możliwy jest dostęp do poszczególnych parametrów wywołania za pośrednictwem rejestru adresowego Y z odpowiednim, stałym dla każdego parametru przesunięciem.
Kod: Zaznacz cały
ldi acc3,<wielkość obszaru> ;
in acc2,sreg ;
; Zapamiętanie w rejestrze acc2 aktualnego stanu rejestru wskaźnikowego,
cli ;
in acc,spl ;
; przepisanie zawartości młodszej części rejestru wskaźnika stosu do wybranego rejestru roboczego,
add acc,acc3 ;
out spl,acc ;
; arytmetyczne dodanie liczby będącej wielkością wyrażoną w bajtach zajętego przez
; parametry obszaru. Wynik zostaje zapamiętany w młodszej części rejestru wskaźnika stosu.
in acc,sph ;
ldi acc3,0 ;
adc acc,acc3 ;
out sph,acc ;
; Mogące wystąpić z dodawania dla młodszej części przeniesienie musi być
; uwzględnione w starszej części rejestru wskaźnika stosu (tak jak w operacjach
; dodawania 16-bitowego).
out sreg,acc2 ;
Kod: Zaznacz cały
in acc,spl
do wykonania instrukcji:
Kod: Zaznacz cały
out sph,acc
Kod: Zaznacz cały
in acc2,sreg ;
cli ;
(...)
out sreg,acc2 ;
Kod: Zaznacz cały
in acc2,sreg
Kod: Zaznacz cały
out sreg,acc2
W sytuacji użycia mikrokontrolerów AVR, które posiadają 8-bitowy rejestr wskaźnika stosu, powyższa operacja dodawania z użyciem rejestru SP ulega znaczącemu uproszczeniu. Ponieważ sam rejestr wskaźnika stosu redukuje się tylko do części młodszej oraz zapis do rejestru jest operacją niepodzielną, nie jest konieczna realizacja tych działań w kontekście zablokowanej możliwości obsługi przerwań. Pociąga to za sobą w algorytmie kolejną redukcję instrukcji związanej z obsługą wskaźnika I. Odpowiedni ciąg instrukcji może być następujący:
Kod: Zaznacz cały
ldi acc3,<wielkość obszaru> ;
in acc,spl ;
add acc,acc3 ;
out spl,acc ;
Kod: Zaznacz cały
Fun : ;FUNCTION Fun
;******** ;
.equ Fun_Param = 0 ; ( Param : BYTE ) : BYTE[xl] ;
; Stała pozwalająca na adresowanie komórki zawierającej
; parametr wywołania. Wykonanie przykładowo instrukcji
; ldd acc,y+Fun_Param
; pozwala pobrać do rejestru acc parametr wywołania
; (szczegółowe wyjaśnienia są w dalszej części).
.equ FunParamSize = 1 ;
; Stała określająca wielkość obszaru na stosie zajętego
; przez parametry wywołania.
rcall _OpenCallParam ;BEGIN (* Fun *)
; Na początku implementacji funkcji/procedury należy
; wywołać bezparametrową procedurę, której zadaniem jest
; zachowanie dotychczasowej zawartości rejestru Y raz
; określenie nowego jego wskazania.
.
.
.
ldi xl,1 ; Fun := 1 ;
ldi param,FunParamSize;
rcall _CloseCallParam ;
; Przed zakończeniem działania funkcji/procedury należy
; wywołać inną procedurę, której zadaniem jest wykonanie
; operacji odwrotnych w stosunku do wcześniej wywołanej
; procedury (_OpenCallParam). Do procedury jest
; dostarczona informacja określająca wielkość obszaru na
; stosie przeznaczonego na parametry (poprzez rejestr
; param), co jednocześnie pozwala wykonać czynności
; związane z usunięciem ich ze stosu.
Ret ;END (* Fun *) ;
;-------------------------------------------------------------
(...)
; ... := Fun ( 5 ) ;
ldi acc,5 ; przygotowanie parametru wywołania
push acc ; utworzenie na stosie obszaru
; zawierającego wartość parametru
; wywołania
rcall Fun ; wywołanie funkcji
… ; parametr wywołania funkcji jest już
; usunięty ze stosu (patrz: implementacja
; procedury _CloseCallParam).
;-------------------------------------------------------------
- adres powrotu z procedury _OpenCallParam (jako efekt wykonania instrukcji rcall _OpenCallParam z funkcji Fun),
- adres powrotu z funkcji Fun (jako efekt wykonania instrukcji rcall Fun),
- ciąg parametrów wywołania funkcji Fun (jako efekt działania instrukcji push wykonanych przed wywołaniem funkcji; w zaprezentowanym wyżej przykładzie występuje jeden parametr).
Kod: Zaznacz cały
_OpenCallParam : ;
;*************** ;
; Stan stosu przedstawia rysunek 4.
pop acc2 ;
pop acc3 ;
; Instrukcje pop nakazują pobranie ze szczytu stosu ostatnio zapisanych tam informacji. W rezultacie
; adres powrotu z bieżącej procedury znajduje się w dwóch rejestrach acc2 i acc3. Stan stosu
; przedstawia rysunek 5 w fazie A.
push yh ;
push yl ;
; W kolejnym kroku, na szczycie stosu umieszczona zostaje zawartość rejestru yh:yl.
in yh,sph ;
in yl,spl ;
; Aktualna zawartość 16-bitowego wskaźnika stosu SP zostaje przepisana do rejestru Y (yh:yl).
Adiw yl,5 ;
; Po zwiększeniu zawartości rejestru yh:yl o 5 wskazuje on w pamięci danych na miejsce,
; gdzie znajduje się blok zawierający parametry wywołania. Stan stosu przedstawia
; rysunek 5 w fazie B. Adres Y+0 pozwala zaadresować komórkę będącą parametrem wywołania
; funkcji (patrz: wartość stałej Fun_Param w powyższym przykładzie).
push acc3 ;
push acc2 ;
; Odpowiednie adresy powrotu z wywołania, chwilowo przechowywane w rejestrach, zostają
; umieszczone na stosie. Efektem działania procedury jest zmodyfikowany stos oraz nowa
; zawartość rejestru przeznaczonego do adresowania parametrów wywołania. Stan stosu
; przedstawia rysunek 5 w fazie C.
ret ;
; Polecenie ret pobiera ze szczytu stosu adres powrotu z bieżącej procedury i wykonanie
; instrukcji programu przenosi się do odpowiedniego miejsca w implementacji funkcji Fun.
; Stan stosu (po powrocie z procedury _OpenCallParam) przedstawia rysunek 6.
Kod: Zaznacz cały
_CloseCallParam : ;
; Procedura wymaga przed jej wywołaniem określenia w rejestrze param
; wielkości obszaru zajmowanego przez blok parametrów (wyrażonej w
; bajtach). W przykładzie jest użyte:
; ldi param,FunParamSize
; rcall _CloseCallParam
; Stan stosu przedstawiony jest na rysunku 7 w fazie A.
pop acc3 ;
pop acc2 ;
; Aktualnie znajdujący się na szczycie stosu adres powrotu z wywołania
; procedury zostaje przepisany do rejestrów. Po tych operacjach stan
; stosu pokazany jest na rysunku 7 w fazie B.
pop yl ;
pop yh ;
pop zl ;
pop zh ;
; Kolejne instrukcje pozwalają odtworzyć wcześniej zapamiętaną
; zawartość rejestru adresowego Y (operacja ta była wykonana w
; procedurze _OpenCallParam). Znajdujący się na szczycie stosu adres
; powrotu z wywołanej funkcji (Fun) również jest przepisany do
; rejestrów roboczych mikrokontrolera. Po tych operacjach stos ma
; postać pokazaną na rysunku 7 w fazie C.
in acc4,sreg ;
cli ;
in acc,spl ;
add acc,param ;
out spl,acc ;
in acc,sph ;
ldi param,0 ;
adc acc,param ;
out sph,acc ;
out sreg,acc4 ;
; W analogiczny sposób jak było to już opisane, usuwany jest ze stosu
; obszar zawierający parametry wywołania. Aktualny stan stosu pokazuje
; rysunek 7 w fazie D.
push zh ;
push zl ;
push acc2 ;
push acc3 ;
; Po umieszczeniu na stosie adresów powrotów z wywołanych funkcji i
; procedur (przechowywanych chwilowo w rejestrach roboczych) stan
; stosu pokazany jest na rysunku 7 w fazie E.
Ret ;
; Wykonanie instrukcji ret w naturalny sposób przenosi wykonanie
; programu do miejsca wywołania.
jeżeli N=1, to wynikiem N! jest 1,
jeżeli N>1 należy wykonać działanie N * (N-1)!.
Tekst programu jest następujący (sam program prezentuje jedynie istotne z punktu widzenia przekazywania parametrów elementy i nie zawiera żadnych dodatkowych operacji, jak przykładowo prezentacja wyniku na wyświetlaczu):
Kod: Zaznacz cały
(...)
.nolist
;*******************************************************
.include "m8515def.inc"
;*******************************************************
(...)
.def acc = r16
.def acc2 = r17
.def acc3 = r18
.def acc4 = r19
.def param = r20
(...)
;-------------------------------------------------------
.dseg
; ;VAR
Res : .byte 2 ; Res : WORD ;
;-------------------------------------------------------
.cseg
(...)
;-------------------------------------------------------
.org 0 ;
rjmp ResetProcessor ;
;-------------------------------------------------------
(...)
;-------------------------------------------------------
_OpenCallParam : ;
(...)
;-------------------------------------------------------
_CloseCallParam : ;
(...)
;-------------------------------------------------------
Silnia : ;FUNCTION Silnia
;******** ;
.equ Silnia_N = 0 ; ( N : BYTE ) : WORD[x] ;
.equ SilniaParamSize = 1 ;
; Nagłówek funkcji rekurencyjnego obliczenia silni, która posiada
; jeden parametr wywołania będący jednobajtową liczbą. Parametr ten
; jest dostępny w pamięci RAM pod adresem Y+Silnia_N (Y+0), zgodnie
; z rysunkiem 6. Nie znaleziono źródła odwołania. Łączna wielkość
; bloku zajmowanego przez parametry wywołania wynosi 1 bajt (stała
; SilniaParamSize).
rcall _OpenCallParam ;BEGIN (* Silnia *)
; Wywołanie niezbędnej procedury, której zadaniem jest odpowiednia
; modyfikacja stosu i określenie w parze rejestrów yh:yl wskazania w
; pamięci RAM na obszar parametrów wywołania.
ldd acc,y+Silnia_N ; IF N <> 1 THEN
cpi acc,1 ;
; Zbadanie, czy aktualny parametr wywołania nie jest liczbą o
; wartości 1.
breq Sil_1 ; BEGIN
; W przypadku prawdziwości badanego warunku,
dec acc ; Silnia := Silnia ( N - 1 ) * N ;
push acc ;
rcall Silnia ;
; przygotowany jest parametr do kolejnego rekurencyjnego wywołania
; funkcji.
mov Argument1LL,xl ;
mov Argument1LH,xh ;
; Zawarta w rejestrach xh:xl liczba, jako wynik wywołanej funkcji
; Silnia(N-1), jest przepisana do odpowiednich rejestrów jako
; pierwszy argument w operacji mnożenia.
ldd Argument2LL,y+Silnia_N ;
ldi acc,0 ;
mov Argument2LH,acc ;
; Drugim argumentem w mnożeniu jest liczba będąca aktualnym
; parametrem wywołania (ponieważ parametr N wywołania funkcji jest
; jednobajtowy, starsza część odpowiedniego zespołu rejestrów jest
; wyzerowana).
rcall MultArg1AndArg2 ;
mov xl,ResultLL ;
mov xh,ResultLH ;
; Po wykonaniu mnożenia, jego wynik zostaje przepisany do rejestru
; wynikowego funkcji (xh:xl).
rjmp Sil_0 ; RETURN ;
; Zakończenie działania funkcji wymaga wykonania odpowiednich
; czynności związanych z modyfikacją stosu, więc następuje skok do
; odpowiedniego miejsca.
Sil_1 : ; END (* IF *) ;
ldi xl,1 ; Silnia := 1 ;
ldi xh,0 ;
; W przeciwnym wypadku (IF N <> 1 THEN), jako wynik funkcji zwrócona
; jest liczba 1.
Sil_0 : ;END (* Silnia *) ;
ldi param,SilniaParamSize ;
rcall _CloseCallParam ;
ret ;
; Właściwe zakończenie działania funkcji sprowadza się do wywołania
; odpowiedniej procedury.
;-------------------------------------------------------
ResetProcessor : ;
ldi acc,HIGH(RAMEND) ;
out SPH,acc ;
ldi acc,LOW(RAMEND) ;
out SPL,acc ;
Main : ;BEGIN (* Main *)
rcall ClearRAM ; ClearRAM ( ) ;
rcall ClearRegs ; ClearRegs ( ) ;
rcall HardwareInit ; HardwareInit ( ) ;
rcall EnvirInit ; EnvirInit ( ) ;
rcall SoftwareInit ; SoftwareInit ( ) ;
sei ; EI ( ) ;
Main_0 : ; LOOP
ldi acc,3 ; Res := Silnia ( 3 ) ;
push acc ;
rcall Silnia ;
; Wywołanie funkcji, której zadaniem jest obliczenie silni dla
; liczby 3.
ldz Res ;
st z+,xl ;
st z,xh ;
; Wynik jest zachowany w pamięci.
rjmp Main_0 ; END (* LOOP *) ;
;END (* Main *) ;
;-------------------------------------------------------
.exit
Zaprezentowane rozwiązanie posiada jedno ograniczenie, mianowicie lista parametrów wywołania funkcji musi być stała, nie można zrealizować wywołania funkcji z różną liczbą parametrów (raz zdefiniowanej funkcji Fun mającej przykładowo jeden parametr wywołania nie można raz wywołać z jednym parametrem a w innym miejscu wywołać z dwoma parametrami). Wynika to z tego, że wewnątrz funkcji w trakcie usuwania ze stosu parametrów wywołania funkcja usuwa obszar wynikający z liczby spodziewanych parametrów wywołania. Powyższy sposób można nazwać typem PASCAL-CALL. Definicja języka nie dopuszcza tworzenia funkcji i procedur ze zmienną liczbą parametrów wywołania. Niektóre języki (jak przykładowo C) oferują mechanizmy pozwalające na wywoływanie funkcji z różną liczbą parametrów. Rozwiązanie w sumie jest proste, opiera się o podobny do powyższego mechanizm i sprowadza się do następujących różnic w realizacji:
parametry są umieszczone na stosie w odwrotnej kolejności (ostatnim położonym na stosie parametrem jest pierwszy z listy wywołania),
parametry są zdejmowane ze stosu w miejscu wywołania funkcji (skoro wywołując funkcję z parametrami wiadomo ile ich jest umieszczonych na stosie, to również wiadomo ile ich zdjąć ze stosu).
Odwrotna kolejność parametrów na stosie wynika z braku jednoznacznego określenia położenia pierwszego parametru (skoro nie jest znana liczba parametrów). Oddzielną kwestią już jest dowiedzenie się wewnątrz funkcji z iloma parametrami została wywołana funkcja. Taki sposób można nazwać typem C-CALL. Klasycznym wręcz przykładem jest wywołanie funkcji printf w języku C. Przykładowo poprawne są:
- printf ( "Jakiś napis" ) ; – wywołanie z jednym parametrem,
- printf ( "Liczba A=%d" , A ) ; – wywołanie z dwoma parametrem,
- printf ( "Liczba A=%d liczba B=%d liczba C=%d” , A , B , C ) ; – wywołanie z czterema parametrami.
Załącznik: