I am learning about MIPS and I am trying to express the codes written in C language with MIPS.

Among them, when I studied the registers that should be preserved, I thought that I decided whether to preserve them by simply considering the types of registers.

int leaf_example (int g, int h, int i , int j)
{
    int f;
    f = (g h)-(i j);
    return f;
 }

For example, there is the above code, and there are conditions that g~j is $a0~a3, f is $s0, and the return value is stored in $v0.

At this time, because of the condition in question, f is stored in $s and $s needs to be preserved, so I understood that the value of $s0 was stored on the stack and then $s was restored later.

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

However, when there is a code like the one above, it is expressed in MIPS as follows:

Why is it that the two values ​​that come in as arguments of the sort() function are stored separately and then used when they are not stored in $s? I don't know how to determine which registers should be preserved.

In the code above, I want to know why you need to preserve $a0 $a1. That said, I'd really appreciate it if you could tell me how to distinguish which values ​​should be preserved in the code.

CodePudding user response：

In C or pseudo code, we have logical variables that have limited lifetime, that come and go by scope (e.g. local variables and parameters), whereas in assembly we have physical storage.  When we translate an algorithm into assembly language, we must map the logical variables into physical storage.

The particular storage that is chosen for variables must meet their lifetime and usage requirements.  By a convention of software, MIPS subdivides the registers (physical storage), into call preserved and call clobbered registers.

What we need to do is an analysis on the variables and how they are used.  You want to answer the question of: for each variable, is the value it holds defined before a function call, and used after one.  If the answer is yes for any variable, then that variable must be stored in a preserved location that will survive the function call, and such locations are either $s registers or (local) stack memory.  But either way, memory is involved, directly in the latter case, and in former case with the usage of $s registers, those registers themselves must be preserved in order to follow the convention.

The $s registers are advantageous and desirable if the code uses the variables many times (by dynamic count), as is often the case with loops.  Otherwise if the variables are used only once (or on a dynamic path unexpected or unimportant for performance), for example, memory may be a better location for them than an $s register.

In the first function, it would be silly to use an $s register for local variable f — f should go in $v0.  Why?  Two reasons:

• $v0 is available, and won't be clobbered by anything this function does from the first use of f to the last, and,
• the function ends with return f;, which means that at the end of the function, f's value needs to be in $v0.

So, putting it there in the first place makes sense, and avoids the overhead of using $s registers, plus no need to copy into $v0 at the end.

In the second function, it is calling swap inside the loop, and so, then

• the function call is assumed to wipe out all argument registers (which are part of the call clobbered set)
• sort itself is going to wipe out $a0 and $a1 as the parameter passing part of making that function call.

The variables i, j, v, and n are all defined before the function call and used after.  i is both a usage and another definition of i — the variable is expected to survive the function call.  Same for j--.  v and n are both defined upon function entry and repeatedly used, so obviously they must also survive the swap function call (or else a next iteration of the loop won't work).

Since these 4 variables are used rather frequently, $s registers are good candidates, as the alternative, memory, would require insertions of additional loads and stores into the bodies of the loops.

The trade off is of doing save & restore to $s registers once each in prologue and epilogue vs. doing loads & stores in the body of the loop, and if the loop executes more than once that is a good trade.

When we map logical variables into physical storage, those are not necessarily permanent, so sometimes a logical variable "lives" (is mapped to) different physical storage in one part of the code than another.