How do I return to the call after the function has finished executing?

Professor Zhou Ligong's years of hard work "Programming and Data Structure" and "Programming for AMetal Framework and Interface (I)", after the publication of the book content, set off a learning boom in the electronics industry. Authorized by Professor Zhou Ligong, this public number has serialized the contents of the book "Programming and Data Structure" and is willing to share it.

The second chapter is programming techniques. This article returns 2.3 stacks and functions.

When the function is executed, how do I return to the call? Since the function may be called multiple times, and the location of each call is likely to be different, it is impossible for the called function to know where it should return, so you must tell the called function where to return when calling the function. ?

> > > 2.3.1 Stack

In order to save variables (data), usually the computer will provide a lot of memory. To facilitate management of memory, the memory used by all variables is called a stack, and the unallocated memory area is called a heap. These unallocated memory areas, the programmer can request it in blocks. This part of the memory is managed by the operating system. Once a piece of memory is allocated, it can only be used by the original code to which the memory is allocated, and the pointer is used to access the memory. Since memory is a scarce resource, it should be released when the program no longer needs it. If you don't do this, the program will run out of memory, causing it to slow down or even crash. This is because the programmer did not release the memory that should have been released, causing a so-called memory leak.

Heap and stack are two common data structures, mainly used for dynamic storage of data. When the program is executed, the stack stores the execution of the program. For example, the local variables argc and argv of the main() function are on the stack, and the memory dynamically allocated using the malloc() function is stored in the heap. Share the same block of memory. Usually the program stack occupies the lower part of the area, while the heap uses the upper part. When the function is called, the stack frame of the function is pushed onto the stack, and the stack "grows out" a stack frame. When the function terminates, its stack frame pops up from the program stack. Although the memory used by the stack will not be cleaned up, it may eventually be pushed to another stack frame on the stack. The dynamically allocated memory comes from the heap and the heap grows down. As the memory is allocated and released, the heap is full of fragments. Although the heap grows downwards, this is only the general direction, and in fact the memory may be allocated anywhere on the heap.

The "stack" that everyone usually refers to is the stack, and the computer directly supports the stack on the hardware. In computer science, the stack is an abstract concept. Its abstract behavior is that the stack can store the same type of data, and usually the data in the stack is called an element. It is only allowed to push an element into the stack (ie push onto the stack), or remove an element from the stack (ie pop pop), and the elements are processed in the "last in first out" principle (last in, first out, LIFO). It is forbidden to test or modify elements that are not on the top of the stack.

Figure 2.7 Schematic diagram of four stacks

Figure 2.7 shows a stack of four general-purpose computers, called the full-decrement stack, the empty-decrement stack, the full-increment stack, and the null-increment stack, which are the physical structures of the stack. The "decrement" refers to the decrease in the value of the stack pointer when the data is pushed onto the stack, that is, the stack grows from the high address down, just like stalactites. "Incremental" means that the value of the stack pointer increases when data is pushed onto the stack, that is, the stack grows upward from the low address, just like a stalagmites. "Full" means that the storage unit pointed to by the SP holds the last data that is pushed onto the stack; "empty" means that the storage unit pointed to by the SP will hold the next data that is pushed onto the stack. The four types of stacks all correspond to the same logical data structure. The subsequent chapters of this book use the "full increment stack" as an example unless otherwise specified.

> > > 2.3.2 Stacking and popping

Assume that the push and pop data is allowed to be int, ie sp is an (int *) type variable. If the data pushed onto the stack is smaller than sizeof(int) bytes, it needs to be converted into int type data to be pushed onto the stack, and the corresponding type conversion is also performed after the stack is popped. For the data on the stack is larger than sizeof(int) bytes, only the data can be split, and a part of the data is once pushed into the stack, and the entire data is pushed into the stack by multiple times of stacking; All are popped and then combined into raw data.

Push operation

If sp is treated as a variable of type (int *), then for a full-increment stack, the data is pushed onto the stack as described in C (see Figure 2.8):

Figure 2.8 Schematic diagram of the stack operation

If the length of data is greater than sizeof(int), the data needs to be split into multiple times after being split. The order of stacking can be low or high, or vice versa. If the order of the stack is first low and then high, an example is shown in Listing 2.27.

Listing 2.27 Example of low order followed by high order stacking

It is assumed here that data can be shifted like an integer, and sizeof(data) is four times larger than sizeof(int).

2. Pop operation

If sp is treated as a variable of type (int *), then for a full-increment stack, the data is popped out in C as follows (assuming the stacked data is saved to the variable data, see Figure 2.9):

Figure 2.9 Schematic diagram of the pop operation

If the length of the data to be stacked is greater than sizeof(int), the data needs to be spliced ​​after being popped multiple times, and the order of splicing is the reverse order of the stack. If the order of the stack is first low and then high, see Listing 2.28.

Listing 2.28. Example of high order followed by low order popping

It is assumed here that data can be bit-operated like an integer, and sizeof(data) is four times larger than sizeof(int).

> > > 2.3.3 Calling and returning functions

Before discussing the ADT stack, first look at a system stack for handling function calls at runtime. Whenever a function is called, the system first creates a structure called an active record or stack frame, placing it on top of the stack of the system stack. Initially, the active record of the called function contains only one pointer to the previous active record and one return address. The pointer to the previous activity record points to the active record of the calling function, and the return address contains the address of the next execution statement after the function call ends. Because only one function is executed at any time, the function being executed is the function whose active record is at the top of the system stack.

If the function calls other functions, the local variables in the function (except static local variables) and their parameters will also be added to their active records, then create a new active record for the called function and store it on the top of the system stack. The function. When the called function ends, the activity record is deleted. At this point, the active record of the calling function is located at the top of the stack of the system stack, and the function continues to run.

The C language saves the return address of the function through the hardware stack, and the called function pops the return address to the program counter PC to return to the call point. The sample code is shown in Listing 2.29.

Listing 2.29 Call and return examples of functions

For the program list 2.29 (10), the following is described in C:

For program listing 2.29(5), the following is described in C:

It can be seen that when the function is called, the address of the next instruction of the main program code line is saved to the stack; when the function returns, the program will obtain the address from the stack and continue to execute downward from that point. In the case where the function calls other functions, put each return address on the stack; when the function ends, you can find their address on the stack.