Stack and Frame Pointers

Proper management of the stack pointer and frame pointer is essential to avoid issues such as buffer overflows during recursion. It also assists in debugging, as correctly setting up the function's stack frame enables debugging tools to generate accurate stack traces.

The figure below shows a properly set up stack frame. The last position (higher address) of the stack frame is used to save the return address register (ra), and the second to last is used for the old frame pointer (fp). Then, the stack pointer (sp) can be update to allocate memory space on the stack for the current function, and the frame pointer is used to store the previous sp value (top of the stack for the previous function scope). The memory space between sp and fp encompasses the stack frame of the current function.

Figure 8.3.1: Function Stack Frame

Convert the following C functions to assembly code.

int factorial(int n){
    if (n < 2){
        return 1;
    }
    return n*factorial(n-1);
}

Assistant Link

Convert the following C functions to assembly code.

int fibonacci(n){
    mysterious_function(n);
    if (n > 1) {
        return fibonacci(n-1) + fibonacci(n-2);
    }
    return n;
};

Assistant Link

Convert the following C functions to assembly code, using the program stack to store local variables.

void reverse_str(char *str, int start, int end) {
    if (start >= end) return;
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;
    reverse(str, start + 1, end - 1);
}

Assistant Link

Convert the following C function to assembly code.

 typedef struct Node {
   struct Node *left, *right;
 } Node;

int tree_depth(Node *root){
     mysterious_function(root);
     if (root == NULL){
         return 0;
     }
     int left = tree_depth(root->left);
     int right = tree_depth(root->right);
     int max = left > right ? left : right
     return max + 1;
 }

Assistant Link

Convert the following C function to assembly code, using the program stack to store local variables.

void merge(int* array, int left, int mid, int right) {
    int n_left = mid - left + 1;
    int n_right = right - mid;

    int L[n_left], R[n_right]; // These arrays should be created using malloc, but we will use use the program stack to store these arrays. Since array will have at most 30 values, 120 bytes should be enough to store the largest L and R together 

    for (int i = 0; i < n_left; i++){
        L[i] = array[left + i];
    }
    for (int j = 0; j < n_right; j++){
        R[j] = array[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]){
            array[k++] = L[i++];
        } else {
            array[k++] = R[j++];
        }
    }

    while (i < n1) {
        array[k++] = L[i++];
    }
    while (j < n2){
        array[k++] = R[j++];
    }
}

void merge_sort(int* array, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(array, left, mid);
        merge_sort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

Assistant Link