int a[20];
char b[20];
short c[20];
What happens if we access c[45]? What do we get? Well, the C
compiler doesn't care, it blindly calculates the offset and adds it to
the base. The result is that we make a reference to address:
860 + 45 * 2 = 950;
Previously we noted that &a = 920, &b = 900, and
&c = 860. So a reference to c[45] is really a
reference to part of the array a!
This could happen all too easily. Say we executed:
short j;
int x = 45;
j = c[x];
What would j contain? It would contain a short made up of the low two
bytes from element a[7]. That is, garbage. There is no
check either in C or in assembly language that an array reference is
safe; you just have to be sure of what you are doing.
Even more dangerously, consider what might happen if an assignment were made to c[45]. The programmer might not even know that she had inadvertently (and wierdly) modified the value of a[7].
In contrast to C and assembler, some languages do provide bounds-checks on each array reference. As you can see, the hardware doesn't help do this, so the language's compiler must insert extra code before each array reference to make sure that the index is in range. These bounds checks slow the program down, but they ensure that the programmer is always notified as soon as an erroneous array reference is made. This is another example of a tradeoff between ease-of-use and performance.
How should we decide this tradeoff? A language like C has decided to .... you guessed it, optimize the common case. (Note that C has become a very popular language, in part due to design decisions like this one). Most often, array references are not in error. So the reference checks are usually not reporting anything. However, if reference checks are used, the programmer must always pay for them.
Two alternative approaches are sometimes used. First, languages like Pascal allow reference checks to be "turned off". That is, while the program is being developed and debugged, we tell the compiler to insert reference checks. Correctness is more important than performance at this point in the process. Later, when we are (more or less) convinced that the program is correct, we turn reference checks off. Then program will run at top speed.
The other approach is the one used with C and assembler. The basic idea is to use some other tool to tell us when references are out of bounds -- that is, the debugger. Some debuggers don't work as well for this job, but if it's not a common problem, then we are willing to use this approach in the rare instances it's necessary. And we get fast code from the compiler all the time.
address_of_first_element + i * size_of_array_element_in_bytesto calculate the address of array element i.
However, arrays of two dimensions and higher are quite useful so we need a way of mapping them onto linear memory, too. If you look at a 2D array, there are two obvious ways to map it onto memory:
When indexing an array, the index order is always (row, column). That is, the column index is last. So under row-major ordering, if you look at the elements in memory, it is the column index that varies fastest. For example, consider the array
int a[3][3];
in memory this looks like:
---------------------------------------------------------------------- | a[0][0] | a[0][1] | a[0][2] | a[1][0] | a[1][1] | a[1][2] | a[2][0] ... ----------------------------------------------------------------------So, for row major ordering, the LAST index varies FASTest.
How do you calculate the location in memory of array element a[i][j]?
You need to calculate the start of its row in memory, which is:
row index * elements per row * sizeof an element = i * 3 * 4and then determine its offset within a row, which is:
column index * sizeof an element = j * 4So the complete expressions is
(row index * elements per row * sizeof an element) + (column index * sizeof an element)For the array a, this is: (i * 3 * 4) + (j * 4).
It's important to note that in order to calculate the address of an element, you need to know the size of a row. Compare this to 1-D arrays where the size of the array was unimportant in calculating addresses.
We can define higher dimension arrays analogously. In the case of
int b[4][3][2];the last dimesion varies fastest, the middle dimension not as fast, and the first dimension varies slowest:
---------------------------------------------------------------------- | b[0][0][0] | b[0][0][1] | b[0][1][0] | b[0][1][1] | b[0][2][0] ... ----------------------------------------------------------------------
The element of the array can be accessed as:
int arr[i][j][k] ;
Here, i,j,k, are the locations of the element to be accessed.
Here also, if we assume a row-major ordering of the array, then the elements of the array are stored in contiguous memory locations such that the elements increase in the order.
The element stored in arr[i][j][k] can be accesssed by :
%fp + (arr_s) + (i * dj * dk * 4) + (j * dk * 4) + (k* 4)
or
%fp + (arr_s) + ((i * dj + j) * dk + k) * 4
where 4 is the number of bytes required to store an integer.
Also, di,dj,dk are the maximum values for each dimension.
In column major, the formula will be the same, but i,j,k would be replaced by k,j,i respectively, and di,dj,dk by dk,dj,di respectively.
In case of Sparc Assembly, C qnd C++, we assume a row-major ordering of arrays and other data structures.
Another Example:
int ary[5][10][6];
In this case, a total of 5*10*6*4 = 1200 bytes of storage required on the stack.
define(ary_s, -1200) save %sp, (-64 -1200) & -8, %sp ==> save %sp, -1264, %sp
Also, to access any element, eg. arr[3][4][5], the offset will be:
[%fp + ary_s + (3 * 10 * 6 * 4) + (4 * 6 * 4) + ( 5 * 4)]
Another simple example: Let us consider a two dimensional array:
arr[3][2]
There are a total of 6 elements in this array :
arr[0][0], arr[0][1], arr[1][0], arr[1][1], arr[2][0], arr[2][1] in that order at locations -24, -20, -16, -12, -8, and -4.
They require 3 * 2 * 4 bytes of memory = 24 bytes. So the array would be defined as:
define(arr_s, -24)Now, to access element arr[2][1], the command will be:
[%fp + arr_s + (2 * 2 * 4 + 1 * 4)]
= [%fp + (-24) + (16 + 4)]
= [%fp - 4]
When we have to calculate the offset from an address in case of multi-dimensional arrays, it usually involves multiplication of addresses with constants.
The best way to accomplish these multiplications is by shifting and adding rather than by using .mul instruction. e.g.
Multiply contents of %o0 by 5 mov %o0, %o1 ! times 1 sll %o0, 2, %o0 ! times 4 add %o0, %o1, %o1 ! times 5