8.5 Stack
A stack is a section of memory serving for temporaty storage of data (e.g. while calculating complex expressions). Its most important task is keeping the states of significant registers during jumps to subprograms, interrupts, traps, etc. During a jump to a subprogram in this part of the memory are kept the parameter values (if any) at the t ime of calling a function or a procedure, value of the PC register (the place reached during the execution of a program), and the frame register W14. The values of the PC and W14 registers are copied to the stack automatically, increasing the value of the W15 register by 6 (three times by 2). The compiler takes care to copy the parameters to the stack by adding a part of the code required for copying the parameters to the top-of-stack on each user call of a function or a procedure.
A stack is a section of memory which is usually accessed sequentially. The access is possible, of course, to any memory location, even to the locations constituting the stack, but such concept is very seldom used. An increase or a decrease of the stack, however, can be done only by a sequential access. When a datum is copied to the stack, it is pushed to the top-of-stack. Only the value from the top-of-stack can be read by the W15 register. Thus a stack is a LIFO (Last In First Out) buffer. In order to know at each moment which address is read or which address is written, one of the registers is reserved as the stack pointer register. This is the W15 register. Therefore, when a datum is copied to the stack, it is written to the location pointed by the W15 register and then the W15 register is increased by 2 to point at the next free location. When a datum is read from the stack, the value of the W15 register is at first decreased by 2 and then the value from the top-of-stack is read.
How does this work in practice? The following example gives a program consisting of the main program and one procedure.
Example of a call of a procedure:
program MemoryTest
dim m as word
sub procedure MyProc1(dim a as word)
dim i as word
i = a + 2
end sub
main:
TRISB = 0
m = 3
nop
MyProc1(m)
m = 2
end.
The main program begins by executing the instruction TRISB :=0;. After that, variable m is allocated the value 3. Then, the procedure is called. What happens at that moment? The compiler has generated a code for copying to the stack the variable m (Fig. 8-4a) and then jumps to the memory address where the subprogram is located.
Fig. 8-4a Stack before entering subprogram
The hardware automatically copies to the stack the program register PC (Program Counter) in order to determine the location from which the execution of the program continues after the subprogram is done, Fig. 8-4b. Since the width of the PC register is 24-bit, two memory locations are required for copying the PC register. The lower 16 bits (PCL) are copied first and then the higher (PCH) 8 bits (extended to 16 bits).
Fig. 8-4b Stack after jump to subprogram (W15=0x806, W14=xxxx)
After the PC register is saved, the hardware also copies and saves the W14 register (frame register) and then writes into it the current value of the W15 register, Fig. 8-4c. This saves the information where the last location used by the main progam is. Whatever the subprogram would do with the section of the stack after this address will have no influence on the execution of the main program. Therefore, the W14 register is the boundary between the local variables of the subprogram and the parameters pushed in the stack from the main program. In addition, this allows to find the address where the parameter value valid at the time of calling the subprogram is. This is done simply by subtracting from W14 the number of locations occupied by the PC and W14 registers at the moment of jumping to the subprogram.
Fig. 8-4c Stack after entry to subprogram (W15=0x808, W14=0x808)
Upon jumping to the subprogram (procedure in this example), the compiler has the task of providing the locations required by the local variables. In this example the local variable is i of the type
word. Fig. 8-4d shows the memory location 0x808 reserved for the local variable i. Value of the W15 register is increased to account for the reservation made for the local variables, but the value of the W14 register remains the same.
Fig. 8-4d Stack after entry to subprogram (W15=0x80A, W14=0x808)
How many locations have been occupied? The answer is three. The W14 register is 16-bit wide and occupies only one location, whereas the PC register is 24-bit wide thus it occupies two locations. The 4 bits unused for saving the PC register are used for saving the current priority level. The parameter address is claculated as W14-8. The register W14 points to the memory location next to those where the parameter, PC register, and W14 register are saved. From this value one should subtract 2 because of the W14 register, 4 because of the PC register which occupies two memory locations, and 2 because of the parameter. For this reason from the value saved in the frame register W14 one should subtract 8. The compiler has generated additional code which reserves the place at the top-of-stack occupied by the local variable i. This has not influenced the value of the register W14 but did influence the value of the register W15 because it always has to point to the top-of-stack.
After entering the procedure, the register W15 points at the location 0x80A, the register W14 to location 0x808, and the parameter is at W14-8=0x800. After the procedure is comlpeted, it is not required to check how many data has been put on the stack and how many has been taken off the stack. The register W14 points to the location next to the locations where the important registers have been saved. The value of the register W14 is written into the W15 register, previous value of the register W14 is taken off the stack and immediatley after, so is the value of the PC register. This is done automatically by the hardware. The compiler has added a section of the code to the main program which then calls the procedures on the stack and reads all parameters saved in it in order to recover the value of the W15 register and return the position of the stack to the previous state.
The following example gives a program consisting of one function and a program using this function. The difference between a function and a procedure lies in the result returned to the main program by the function.
Example of calling a function:
program MemoryTest2
dim m,n as word
sub function MyFunc1(dim a,b as word) as word
dim i, j as word
i = a+2
j = b-1
result = i+j
end sub
main:
TRISD = 0
m = 3
n = 5
nop
m = MyFunc1(m, n)
LATD = 2
end.
The program starts by executing the instruction
TRISD :=0;. After that, it allocates the value 3 to the variable
m. Then, it calls the function. What happens at this moment? The compiler has generated a code which push to the stack the variables
m and
n, Fig. 8-5a, and then jumps to the address in the memory corresponding to the subprogram (function).
Fig. 8-5a Stack before subprogram is entered (W15=0x804, W14=xxxx)
The hardware automatically saves on the stack the PC register to determine, after the subprograme is completed, the address from which the main program resumes the execution, Fig. 8-5b. The PC register is 24 bit wide, two memory locations are required in the data memory to save this register. The lower 16 bits (PCL) are copied first and then the higher (PCH) 8 bits (extended to 16 bits).
Fig. 8-5b Stack after jump to subprogram (W15=0x808, W14=xxxx)
After the PC register is saved, the hardware also copies and saves the W14 register (frame register) and then writes into it the current value of the W15 register, Fig. 8-5c. This saves the information where the last location used by the main progam is. Whatever the subprogram would do with the section of the stack after this address will have no influence on the execution of the main program. Therefore, the W14 register is the boundary between the local variables of the subprogram (function in this case) and the parameters pushed in the stack from the main program. In addition, this allows to find the address where the values of the parameters a and b, valid at the time of calling the function, are. This is done simply by subtracting from W14 the number of locations occupied by the PC and W14 registers at the moment of jumping to the subprogram.
Fig. 8-5c Stack after entry to subprogram (W15=0x80A, W14=0x80A)
Upon jumping to the subprogram (function in this example), the compiler has the task of providing the locations required for the result and the local variables. In this example the result is of the type word and the local variables i and j are of the type
word. Fig. 8-5d shows the memory locations 0x80A, 0x80C, and 0x80E reserved for the rersult of the function result and the local variables i and j. Value of the W15 register is increased to account for the reservation made for the result and the local variables, but the value of the W14 register remains the same.
Fig. 8-5d Stack after entry to subprogram (W15=0x80F, W14=0x80A)
Similarly to the call of a procedure, the parameter is in the memory location W14-8, but the parameter i is in W14+2, and the result of the function (result) is written in the location W14.
What would have happened if the locations for the local variables were reserved first and then the location for the
result? Fig. 8-5e shows the case of calling the function
MyFunc1 from the previous example if the locations for the local variables i and j were reserved first and then the location for the result.
Fig. 8-5e Stack after entry to subprogram when the locations for the local variables i and j were reserved first and then the location for the result (W15=0x80C, W14=0x808)
The local variable
i is in the memory location W14,
j is in W14+2, and the result is in W14+4. The function could end correctly and return the result to some location. The main program could not read the result because it depends on the number of the locations reserved for the local variables. For each function the main program would have to read differently the result of the function. For this reason by reserving
first the memory location for the result ensures that the main program knows the exact location containing the result of the function.
After completion of a subprogram (function), the content of the register W14 is written into the W15 register. This releases the memory locations of the local variables. They are of no importance for further execution of the main program. The location where the result was saved is released together wtih these locations. The process of releasing these locations does not write anything into the memory, therefore the value of the result remains the same. From the stack the previous value of the register W14 is written into the W14 register, and the values saved at the memory locations 0x806 and 0x804 are written into the PC register which points to the next instruction of the main program after the subprogram (function) was called. Only the parameters a and b remain on the stack, as shown in Fig. 8-5f. All this is done by the hardware, i.e. a microcontroller from the dsPIC30F family does that automatically. After this, the floor is taken by the compiler.
Fig. 8-5f Stack after return from subprogram (W15=0x804, W14=xxxx)
After return from the subprogram, on the top-of-stack are the parameters used for calling the function. Since they are no longer required, they are taken off the stack. Now the value of the stack register W15 is 0x800. The result of the function should be read. It is in the location W15+10, i.e. 0x800+0x00A=0x80A. Between the top-of-stack (pointed by the register W15) and the location where the result is saved are the memory locations where the parameters were saved (2 locations, 4 addresses) and the memory locations where the registers PC and W14 were saved (3 locations, 6 addresses). This gives the value 10 by which W15 should be increased to obtain the address of the location containing the result.
The initial value of the register W15 (pointer of the top-of-stack) is 0x800. The value of the W15 register could be changed by writing into it, but this is not recommened due to potential loss of data located on the top-of-stack.
Care should be taken that the stack is in the X space of the data memory. If the memory space is not adequately used, there is a possibility that, as the stack grows, some of the local variables are overwritten by the stack values. The probability of this type of collision increases during the exceution of DSP instructions which use the X space.
Thanks to this algorithm and the memory model, it is possible to nest the procedures and functions or call procedures and functions from the interrupt routines and traps without fear that after the return to the main program some of the registers can be overwritten and their values lost. It should be mentioned that the compiler when calling an interrupt routine, in addition to the already mentioned tasks, generates a code for saving
all general purpose registers on the stack which ensures that while writing an interrupt routine one does not have to take into account which register was used, but the interrupt routine can be considered a program independent of the main program in so far as the general purpose registers are concerned.
The parameters and variables which take more than one memory location, e.g. 32-bit integers, are kept in the memory in the following way. The lower 16 bits are saved first (in the lower address) and then the higher 16 bit are saved (in the higher address).
At the end of this section a description is given of the registers used to control modulo and bit-reversed addressing.
NAME |
ADR |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RESET STATE |
MODCON |
0X0046 |
XMODEN |
YMODEN |
- |
- |
BWM<3:0> |
YWM<3:0> |
XWM<3:0> |
0x0000 |
Table 8-3 MODCON register
XMODEN - X space modulo addressing enable bit
YMODEN - Y space modulo addressing enable bit
BWM<3:0> - Register select for bit-reversed addressing bits
YWM<3:0> - Y space register select for modulo addressing bits
XWM<3:0> - X space register select for modulo addressing bits
NAME |
ADR |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RESET STATE |
XMODSRT |
0X0048 |
XS<15:1> |
0 |
0x0000 |
Table 8-4 XMODSRT register
XS<15:1> - X space modulo addressing start address bits
NAME |
ADR |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RESET STATE |
XMODEND |
0X0050 |
XE<15:1> |
1 |
0x0001 |
Table 8-5 XMODEND register
XE<15:1> - X space modulo addressing end address bits
NAME |
ADR |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RESET STATE |
YMODSRT |
0X0052 |
YS<15:1> |
0 |
0x0000 |
Table 8-6 YMODSRT register
YS<15:1> - Y space modulo addressing start address bits
NAME |
ADR |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RESET STATE |
YMODEND |
0X0054 |
YE<15:1> |
1 |
0x0001 |
Table 8-7 YMODEND register
YE<15:1> - Y space modulo addressing end address bits
NAME |
ADR |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RESET STATE |
XBREV |
0X0056 |
BREN |
XB<14:1> |
0x0000 |
Table 8-8 XBREV register
BREN - Bit-reversed addressing enable bit
XB<14:1> - Bit-reversed modifier bits