Search code examples
mipscpu-registerspreserve

Is $s necessary when implementing a function that swaps while looping through a loop in MIPS?

void sort (int v[], int n)
{
    int i, j;
    for (i = 0;  i<n; i+=1){
        for(j=i-1; j>=0; && v[j]>v[j+1]; j-=1){
            swap(v,j);
            }
        }
    }
    
void swap(int v[], int k)
    {
        int temp;
        temp = v[k+1];
        v[k+1]= temp;
    }

below is MIPS code of swap function

swap : sll $t1, $a0, 2   // reg $t = k*4 
       add $t1, $a0, $t1 // reg $t1 = v+(k*4)
                         // reg $t1 has the address of v[k]
       lw  $t0, 0($t1)   // reg $t0 (temp) =v[k]
       lw  $t2, 4($t1)   // reg $t2 = v[k+1]
                         // refers to next element of v
       sw  $t2, 0($t1)   // v[k] = reg $t2
       sw  $t0, 4($t1)   // v[k+1] = reg $t0 (temp)
     
       jr  $ra           // return to calling routine

I am studying computer architecture. Through several procedures, we learned that values ​​that should not be changed are stored using a stack pointer or stored in $S.

However, in the code above, the parameters v[] ($a0) and n($a1) of the sort function are stored in $s0 $s1 using the stack pointer, and before running the innermost loop, $s0 in $a0, The data is shown as assigning the value of $s1 to $a1.

However, in the code above, v[] has to keep the changed state inside the swap function, and j also has to change the value while looping, so there is no need to save and put the previous value.

Is my explanation correct? That is, when implementing the above code in MIPS, there is no problem in using the stack pointer to not store it in $s?

Solution

  • Is $s necessary when implementing a function that swaps while looping through a loop in MIPS?

    The $s registers are never necessary.  What is necessary is that the variable values of v, n, i, and j survive the function call to swap.  There are two ways to make values survive the function call, and one is to use (stack) memory and the other is to use $s registers, so, $s register are not strictly necessary at all.  (Both forms involve stack memory (and the same amount, as well), but the former uses the stack memory directly for the variable values, and the latter uses the stack memory in preservation of the $s registers' original values).

    However, $s registers are preferred for variables that have multiple uses, (measured dynamically by instruction execution at runtime rather than statically as seen in code listing) and where also such variable must survive a function call.  (Of course, arrays cannot live in $s registers, but a reference to the array (a pointer variable) can.)

    Why do these variables have to survive the function call?  Because they are each consumed (used, sourced) after the call, though having been defined (set, targeted) before the function call.  Programs expect continuity of their variables whether or not function calls happen.

    Let's call out the difference between logical variables used by high level language and pseudo code vs. the physical storage of machine code.

    Logical variables have names, types, scope/lifetime (they come and go, some frequently during program execution, as local variables and parameters).  There is an infinite number of possible ones — just create a new name as we like (and can also be unnamed, as with heap data structures).  A program using logical variables has an expectation of continuity — that once set, a variable retains its value until changed by the program (and then retains that new value).

    The physical storage of the machine is permanent and global and just groups of bits.  The CPU registers are always present, as is memory (let's gloss over virtualization).  The CPU does not see variables, their declarations, their names, their types or their lifetimes — the CPU sees physical storage.  (How does it work then?  The CPU is told, via machine instructions, how to interact with physical storage; it is so told as needed, every time it runs a machine code instruction.)

    Part of the job of translating a high level language program into machine code is managing the mapping of the program's logical variables to the hardware's physical storage.  Since physical storage has constraints, machine code programs must work within them in doing those mappings.

    Sometimes a logical variable has to be relocated to alternative physical storage (e.g. from $a register to either $s register or stack memory).  A machine code instruction (or sequence) is usually required to do such relocation, plus, the compiler or assembly programmer has to be aware that the mapping from variable to storage can be different at different points in the same program.

    (Sometimes a logical variable's value is actually in more than one physical storage location, as is the case when manipulating global variables that live in memory and copies are brought into CPU registers to work with.  Similar is true for elements of arrays.)