Pointer based array access in MIPS

Question

What do we mean by the pointer based array access in MIPS?

Answer 1

There is an additional possible meaning or implication to "pointer based array access":

You may have a pointer to an array, rather than an array at a fixed address. Actually, in C/C++, a "pointer to an array" is really usually just a pointer to the first element of the array. Basically, you have an array that is a parameter to a function, or a pointer to an array that is a member of a struct or class:

 void Foo(char a[]); 
   /*or*/ void Foo(char *a);
 struct Bar {  int offset4bytes; char* a; };

Typically, when you want to use such an array, the base address of the array will be loaded into a register.

Now say you want to access element i of such an array,

 char tmp = a[i];

Let's say that r1 contains the array address. (Actually, probably a different register, specified by the calling convention, for the function paramaters. Whatever the compiler finds available for other code.)

Let's say that i lives in register r2.

And, for good measure, let tmp be r3.

On some instruction sets, e.g. Intel x86, there is an addressing mode that looks like

  MOV r3, (r2,r1)4

i.e. the addressing mode can add two registers and an offset (I arbitrarily added a field to the struct example so that I could show this).

Heck, they can even scale one of the registers, the so-called index register:

  MOV r3, (r2*2,r1)4

or as I prefer to write it

  r3 := load( Memory[r2<<1+r1+4]

MIPS, however, does not have this sort of base+_index*scale+offset addressing mode. Most MIPS memory access instructions are limited to register+offset. Therefore, for MIPS, you might have to do

  ADDU r10, r1,r1    ; dest on left. r10 = 2*r1
  ADDU r11, r2,r10  
  LB r3,(r11)4

i.e. you might have to add extra RISC instructions to accomplish what x86 does in one CISC instruction with a complicated addressing mode. However, such addressing is not common, and canm often be avoided.

---

Further, even just addressing an array at a fixed address may require extra instructions in MIPS. x86 instructions can have a 32 bit memory offset - which in this case may actually be an absolute address of an array. MIPS instructions are limited to a 16 bit offset - MIPS instructions are fixed width, 32 bits wide. Therefore, a separate instruction may be required even to access an array at a fixed address, typically to load the upper bits of the address into a register.

And more - MIPS has newer instructions like LUXC1, that have reg+reg addressing modes. But not scaled index, and no third offset component.

---

Because of this restricted addressing modes, the code that a naive compiler generates for a lop such as

   for(int i=0;i<N;i++) {
      this->a[i] = 0;
   }

would be inefficient, if the loop contained the multiple instruction sequence mentioned above.

A loop such as

   for(char *p=this->a;p<&(this->a[N]);p++) {
      *p=0;
   }

or, equivalently

   for(char *p=this->a;p<this->a+N;p++) {
      *p;
   }

or even sometimes

   for(i=-N,*p=this->a;i<0;i++,p++) {
      *p=0;
   }

might be more efficient, because, e.g. in the first two there would only be a single instruction to do the store. (The last is usually only a win if traversing several arrays.

Now, in a simple example any good compiler will do this optimization for you. But sometimes the compiler prefers such pointer based accesses.

Answer 2

You will have a pointer that points to the beginning of the array of values. To traverse the array you will use pointer arithmetic (usually adding/subtracting 1, 2, or 4) to advance the pointer to the next/previous element in the array.