Swap Procedure in MIPS

enter image description here enter image description here I'm learning MIPS in a CO course, I encounter the swap procedure in MIPS.

I'm wondering that if the load word and store word just load and store the "VALUE" at the expected address, so how can we actually change the content in the array's address. Because I suppose $t0 and $a0 (which is the address of the array) is different. Thank you for all your explanation!

Solution

That swap procedure does the following in C:

void swap(int v[], int k) {
    int *p = v + k;          // sll, add
    int temp1 = p[0];        // lw
    int temp2 = p[1];        // lw
    p[0] = temp2;            // sw
    p[1] = temp1;            // sw
}

Let's imagine that v is at 0x10010000 (a global data memory location for some MIPS memory models) and k is 3.

meaning/variable	memory address	stored value
v aka v[0]	0x10010000	5
v[1]	0x10010004	3
v[2]	0x10010008	7
v[3], v[k] since k=3	0x1001000C	9
v[4], v[k+1]	0x10010010	2

Then the values 9 and 2 are loaded from v[k] and v[k+1], respectively, and stored back to v[k+1] and v[k] respectively, so now the last two rows are:

meaning/variable	memory address	stored value
v[3], v[k]	0x1001000C	2
v[4], v[k+1]	0x10010010	9

If we do this operation in context, i.e. multiple times within a sort algorithm, the the whole array of values becomes sorted, while the index positions and addresses simply remain fixed.

I'm wondering that if the load word and store word just load and store the "VALUE" at the expected address,

Yes, and the "VALUE" at the expected address is what we want to change. The sws accomplish updating the values in the array.

so how can we actually change the content in the array's address.

Contents and values in the array are the same thing. The stores accomplish changing the values at the position k and k+1.

Addresses (themselves as numerical values) are unaffected by loads and stores. Memory has addresses but they are effectively immutable, only values stored at memory locations can be updated, so that is what we do. The array has a base address and elements starting at that base address, and then every 4 addresses later is another element of the array. These addresses are fixed but the values they store can be updated, swapped, etc.. We sort an array by moving values from one position in the array to another, while the positions themselves remain fixed — just as in the C code, we don't change k or v, only what is stored at v[k] and v[k+1].

In another data structure we could store complex values, for example, a value pair: (priority, value). With such a structure, we would have two values per element in an array. That changes the indexing we do: e.g. one pair will occupy 8 bytes each now instead of 4 each with the array of int. We can update, swap, and sort these pairs in their array. (To sort them we need a criteria, such as by priority and/or by value). Yet the addressing used remains fixed.

Allocating an array (in C, e.g. using malloc, or in assembly) is an operation where you provide a size as byte count (e.g. 40 for array of 10 integers) and the system returns to you a single memory address that has enough storage after to hold the whole size of bytes. Once the array is allocated, its base address remains fixed, and all its elements are at addresses computable from that base address. In C, we can free an allocated array, and then those memory addresses used for the array can be used for another purpose.

(Other languages have more complicated data structures that allow moving the array to a new allocation for purposes of dynamic expansion of the size of the array, though all of it is done in terms of immutable memory addresses.)