Clemson University -- CPSC 231 -- Fall 2009

One-dimensional array

  storage allocation                         address arithmetic

    low addresses  +------+                    address of a[i] =
                   | a[0] |<--- base address     base address +
                   +------+  |                   (i * element_size)
                   | a[1] |  |
                   +------+  | index i           for 0-origin indexing
                   |      |  |
                      ...    |
                   |      |  |
                   +------+  v                 address of a(i) =
                   | a[i] |<---                  base address +
                   +------+                      ((i-origin) * element_size)
                   |      |
                      ...                        for nonzero-origin indexing
                   |      |
                   +------+
                   |a[n-1]|
    high addresses +------+


  access to stack-allocated array, 0-origin (p. 182)
    (I find this approach inelegant -- see alternate approach below)

    sll  %i_r, 2, %o0      ! i in i_r, multiply by 4 to get byte offset
    add  %fp, %o0, %o0     ! add offset of element i to %fp
    ld   [%o0 + a_s], %o0  ! access by adding array start offset to %o0


                                                (low addresses)
                    +======+
    stack pointer ->|......|                 top of stack frame top
                    !other.!
                       ...
                    !.stuff!
                    !......!
                    +======+
    base address -->| a[0] |<----------.
                    +------+  |        |
    base + 4 ------>| a[1] |  |        |
                    +------+  |        |
    base + 8 ------>|      |  | i      |
                       ...    |        |
                    |      |  |        |
                    +------+  v        |
    base + i*4 ---->| a[i] |<---       |
                    +------+           |
    base + (i+1)*4  |      |           |
                       ...             |
                    |      |           | a_s  (will be negative value)
                    +------+           |
                    |a[n-1]|           |
                    +======+           |
                    !......!           |
                    !other.!           |
                       ...             |
                    !.stuff!           |
                    !......!           |
                    +======+           |
    frame pointer ->        <------------
                                               (high addresses)


  alternate way to access element in a stack-allocated array, 0-origin

    add %fp, a_s, %base_r           ! add array start offset to %fp to get base
    sll %i_r, 2, %offset_r          ! multiply i by 4 to get byte offset
    ld  [%base_r + %offset_r], %o0  ! access by adding base and byte offset


  similar to accessing an element in a global data array, 0-origin
    (only the first instruction is different)

    set a, %base_r                  ! place the base address in register
    sll %i_r, 2, %offset_r          ! multiply i by 4 to get byte offset
    ld  [%base_r + %offset_r], %o0  ! access by adding base and byte offset



Two-dimensional array

  storage allocation now more difficult -- row major or column major

        a0,0 \                      a0,0 \
        a0,1 | row 0                a1,0 | column 0
        a0,2 |                      a2,0 |
        ...  /                      ...  /
        a1,0 \                      a0,1 \
        a1,1 | row 1                a1,1 | column 1
        a1,2 |                      a2,1 |
        ...  /                      ...  /

  C is row-major, Fortran is column-major

    e.g., in C
                                  ...
      int mat[2][2];        mat | mat[0][0] | mat +  0  \ row 0
                                | mat[0][1] | mat +  4  /
                                | mat[1][0] | mat +  8  \ row 1
                                | mat[1][1] | mat + 12  /
                                     ...

  address of a(i,j) in row-major storage order =

    base_address + [(i-origin1)*#_elements_per_row + (j-origin2)] * element_size


  consider this example C code

    int main(void){
      int a[5][5];
      register int i=3,j=4;
      a[i][j] = 0;
    }

  annotated assembly output from compiler

        .global main
main:
        save    %sp, -216, %sp

        mov     3, %i5          ; %i5 = i = 3
        mov     4, %i4          ; %i4 = j = 4

        mov     %i5, %g1        ; %g1 = i

        sll     %g1, 2, %g1     ; %g1 = 4*i
        add     %g1, %i5, %g1   ; %g1 = 4*i + i = 5*i

        add     %g1, %i4, %g1   ; %g1 = 5*i + j

        sll     %g1, 2, %i5     ; %i5 = 4*( 5*i + j )

        add     %fp, -16, %g1   ; %g1 = %fp - 16
        add     %i5, %g1, %g1   ; %g1 = %fp - 16 + 4*( 5*i + j )

        st      %g0, [%g1-104]  ; eff addr = %g1 - 104
                                ;          = %fp - 16 + 4*( 5*i + j ) - 104
                                ;          = %fp - 120 +    4*( 5*i + j )
                                ;          = %fp - a_s + size*(row_length*i+j)

        mov     %g1, %i0        ; return code
        ret
         restore


  a cleaner approach to do a[i][j] = 0;

        add   %fp, -120, %base_r

        sll   %i_r,   2, %o0        ; 4*i
        add   %i_r, %o0, %o0        ; 5*i
        add   %j_r, %o0, %o0        ; 5*i + j
        sll   %o0,    2, %offset_r  ; 4*( 5*i + j )

        st    %g0, [ %base_r + %offset_r ]



traversing an array (visiting all elements)

  two options in accessing:  (assume array is global)

  1) adding a scaled index to a base address

        // element = a[i];

        set a, %base_r                   // can set base address outside loop
        clr %i_r
        ...
     loop:
        ...
        sll %i_r, SCALE_FACTOR, %o0         // e.g., SCALE_FACTOR = 2 for int
        ld  [ %base_r + %o0 ], %element_r
        ...
        inc %i_r
        ...
     
  2) dereferencing a pointer and incrementing the pointer

        // int *ptr = a;
        // ...
        // element = *ptr++;

        set a, %ptr_r        // initialize ptr to base address outside loop
        ...
     loop:
        ...
        ld  [ %ptr_r ], %element_r        // dereference ptr   -- *ptr
        add %ptr_r, ELEMENT_SIZE, %ptr_r  // postincrement ptr -- ptr++
        ...                               //   e.g., ELEMENT_SIZE = 4
                                          //   for an int pointer
     
    note that in the second approach you can choose to make the loop control
    a test against an address limit rather than testing a loop counter

        // int a[N];
        //
        // int *ptr = a;         -- like a.begin() for a C++ vector
        // int *limit = a+N;     -- like a.end() for a C++ vector
        //
        // while( ptr != limit ){
        //   ...
        //   element = *ptr++;
        //   ...
        // }

        set a, %ptr_r;               // initialize ptr to base address

        mov N, %o0                   // initialize limit to point to
        sll %o0, 2, %o0              //   one element beyond the last
        add %ptr_r, %o0, %limit_r    //   element in the array
        ...
     loop:
        cmp %ptr_r, %limit_r
        beq done
         nop
        ...
        ld  [ %ptr_r ], %element_r   // dereference ptr   -- *ptr
        add %ptr_r, 4, %ptr_r        // postincrement ptr -- ptr++
        ...
        ba  loop
         nop
     done:
        ...