Introduction to Computer Systems 15-213/18-243, spring 2009 1st Lecture, Jan. 12th
Data Structures in Assembly
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structs
Alignment
1
CMPT 295
L09 – Arrays
1
Array Example
2
Example arrays happened to be allocated in successive 20 byte blocks
Not guaranteed to happen in general
zip_dig cmu;
1
5
2
1
3
16
20
24
28
32
36
zip_dig sfu;
9
8
1
9
5
36
40
44
48
52
56
zip_dig ucb;
9
4
7
2
0
56
60
64
68
72
76
typedef int zip_dig[5];
zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig sfu = { 9, 8, 1, 9, 5 };
zip_dig ucb = { 9, 4, 7, 2, 0 };
CMPT 295
L09 – Arrays
20 B each
No gap in this case
Could have stuff in between
Array Accessing Example
3
int get_digit(zip_dig z, int digit){
return z[digit];
}
zip_dig sfu;
9
8
1
9
5
36
40
44
48
52
56
get_digit:
slli a1,a1,2
add a1,a0,a1
lw a0,0(a1)
ret
Register %a0 contains starting address of array
Register %a1 contains array index
Desired digit at %a0+4*%a1
typedef int zip_dig[5];
CMPT 295
L09 – Arrays
Array also explain funky memory addressing instructions
3
Nested Array Row Access
Row vectors
Given T A[R][C],
A[i] is an array of C elements (“row i”)
A is address of array
Starting address of row i =
4
• • •
• • •
A
[i]
[0]
A
[i]
[C-1]
A[i]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
A[R-1]
• • •
A
• • •
A
[0]
[0]
A
[0]
[C-1]
A[0]
A+i*C*4
A+(R-1)*C*4
int A[R][C];
A + i*(C * sizeof(T))
CMPT 295
L09 – Arrays
Row is just an address
Nested Array Row Access Code
5
int* get_sea_zip(int index)
{
return sea[index];
}
int sea[4][5] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};
CMPT 295
L09 – Arrays
Sea is a global variable here, so its in memory
Nested Array Row Access Code
Row Vector
sea[index] is array of 5 ints
Starting address = sea+20*index
Assembly Code
Computes and returns address
Compute as: sea+4*(index + 4*index) = sea+20*index
6
int* get_sea_zip(int index)
{
return sea[index];
}
int sea[4][5] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};
What data type is sea[index]?
What is its value?
CMPT 295
L09 – Arrays
Returns an address, no access
• • •
• • • • • •
A
[i]
[j]
A[i]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
A[R-1]
• • •
A
• • •
A
[0]
[0]
A
[0]
[C-1]
A[0]
A + i*C*4
A + (R-1)*C*4
int A[R][C];
Nested Array Element Access
Array Elements
A[i][j] is element of type T, which requires K bytes
Address of A[i][j] is
7
?
CMPT 295
L09 – Arrays
A + i*(C*K) + j*K
Nested Array Element Access
Array Elements
A[i][j] is element of type T, which requires K bytes
Address of A[i][j] is
A + i*(C*K) + j*K == A + (i*C + j)*K
8
A + i*C*4 + j*4
• • •
• • • • • •
A
[i]
[j]
A[i]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
A[R-1]
• • •
A
• • •
A
[0]
[0]
A
[0]
[C-1]
A[0]
A + i*C*4
A + (R-1)*C*4
int A[R][C];
CMPT 295
L09 – Arrays
Nested Array Element Access Code
9
int get_sea_digit
(int index, int digit)
{
return sea[index][digit];
}
int sea[4][5] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};
CMPT 295
L09 – Arrays
Asm is 3 steps
Compute row
Compute loctation in row
Access with scaling
Multi-Dimensional Referencing Examples
Reference Address Value Guaranteed?
sea[3][3]
sea[2][5]
sea[2][-1]
sea[4][-1]
sea[0][19]
sea[0][-1]
Code does not do any bounds checking
Ordering of elements within array guaranteed
10
zip_dig sea[4];
76
96
116
136
156
9
8
1
9
5
9
8
1
0
5
9
8
1
0
3
9
8
1
1
5
CMPT 295
L09 – Arrays
148 1 yes
136 9 yes
112 5 yes
152 5 yes
152 5 yes
72 ?? no
Multi-Level Array Example
11
int cmu[5] = { 1, 5, 2, 1, 3 };
int sfu[5] = { 9, 8, 1, 9, 5 };
int ucb[5] = { 9, 4, 7, 2, 0 };
int* univ[3] = {sfu, cmu, ucb};
Is a multi-level array the
same thing as a 2D array?
zip_dig univ2D[3] = {
{ 9, 8, 1, 9, 5 },
{ 1, 5, 2, 1, 3 },
{ 9, 4, 7, 2, 0 }
};
One array declaration = one contiguous block of memory
NO
2D Array Declaration:
Multi-Level Array Declaration(s):
CMPT 295
L09 – Arrays
Multi-Level Array Example
12
Variable univ denotes array of 3 elements
Each element is a pointer
8 bytes each
Each pointer points to array of ints
36
160
16
60
168
176
univ
cmu
sfu
ucb
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
60
64
68
72
76
80
Note: this is how Java represents multi-dimensional arrays
int* univ[3] = {sfu, cmu, ucb};
int cmu[5] = { 1, 5, 2, 1, 3 };
int sfu[5] = { 9, 8, 1, 9, 5 };
int ucb[5] = { 9, 4, 7, 2, 0 };
CMPT 295
L09 – Arrays
Element Access in Multi-Level Array
13
Computation
Element access Mem[Mem[univ+8*index]+4*digit]
Must do two memory reads
First get pointer to row array
Then access element within array
But allows inner arrays to be different lengths (not in this example)
add a5,a5,a0
ld a5,0(a5) # univ[index]
slli a1,a1,2 # 4*digit
add a5,a5,a1 # univ[index]+4*digit
lw a0,0(a5) # *p
int get_univ_digit
(int index, int digit)
{
return univ[index][digit];
}
36
160
16
60
168
176
univ
cmu
sfu
ucb
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
60
64
68
72
76
80
CMPT 295
L09 – Arrays
Just two array reads
Array Element Accesses
14
int get_sea_digit
(int index, int digit)
{
return sea[index][digit];
}
int get_univ_digit
(int index, int digit)
{
return univ[index][digit];
}
Nested array
Multi-level array
Access looks the same, but it isn’t:
Mem[sea+20*index+4*digit]
Mem[Mem[univ+8*index]+4*digit]
36
160
16
60
168
176
univ
cmu
sfu
ucb
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
60
64
68
72
76
80
CMPT 295
L09 – Arrays
Depends on how array is declared
Multi-dimensional arrays are a special construct!
Multi-Level Referencing Examples
Reference Address Value Guaranteed?
univ[2][3]
univ[1][5]
univ[2][-2]
univ[3][-1]
univ[1][12]
C code does not do any bounds checking
Location of each lower-level array in memory is not guaranteed
15
36
160
16
60
168
176
univ
cmu
sfu
ucb
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
60
64
68
72
76
80
CMPT 295
L09 – Arrays
72 2 yes
36 9 no
52 5 no
?? ?? No
64 4 no
int zd2int(zip_dig z)
{
int i;
int zi = 0;
for (i = 0; i < 5; i++) {
zi = 10 * zi + z[i];
}
return zi;
}
Array Loop Example
16
zi = 10*0 + 9 = 9
zi = 10*9 + 8 = 98
zi = 10*98 + 1 = 981
zi = 10*981 + 9 = 9819
zi = 10*9819 + 5 = 98195
9
8
1
9
5
typedef int zip_dig[5];
CMPT 295
L09 - Arrays
Array Loop Example
Original:
Transformed:
Eliminate loop variable i,
use pointer zend instead
Convert array code to
pointer code
Pointer arithmetic on z
Express in do-while form
(no test at entrance)
17
int zd2int(zip_dig z)
{
int zi = 0;
int *zend = z + 5;
do {
zi = 10 * zi + *z;
z++;
} while (z < zend);
return zi;
}
zip_dig sfu;
9
8
1
9
5
36
40
44
48
52
56
address just past
5th digit
Increments by 4 (size of int)
int zd2int(zip_dig z)
{
int i;
int zi = 0;
for (i = 0; i < 5; i++) {
zi = 10 * zi + z[i];
}
return zi;
}
CMPT 295
L09 - Arrays
15au: With –Og, gcc will generate different code for each of these. With –O1, the same code.
int zd2int(zip_dig z)
{
int zi = 0;
int *zend = z + 5;
do {
zi = 10 * zi + *z;
z++;
} while (z < zend);
return zi;
}
Array Loop Implementation
18
gcc with –O1
zd2int(int*): # @zd2int(int*)
a3=10,a4=20
mv a2, a0
add a4, a0, a4 # a4=zend
# a0 = Base address
# a2 = Loop variable
.LBB0_1: Loop
lw a5, 0(a2) # *z
mul a1, a1, a3 # 10 * zi
add a1, a1, a5 # 10 * zi + *z
addi a2, a2, 4 # increment pointer z++
bne a2, a4, .LBB0_1 # z < zend
add a0, zero, a1
ret
CMPT 295
L09 - Arrays
Arrvindh Shriraman (AS) -
Arrvindh Shriraman (AS) -
Strange Referencing Examples
Reference Address Value Guaranteed?
sea[3][3]
sea[2][5]
sea[2][-1]
sea[4][-1]
sea[0][19]
sea[0][-1]
Code does not do any bounds checking
Ordering of elements within array guaranteed
19
76+20*3+4*3 = 148 1 Yes
76+20*2+4*5 = 136 9 Yes
76+20*2+4*-1 = 112 5 Yes
76+20*4+4*-1 = 152 5 Yes
76+20*0+4*19 = 152 5 Yes
76+20*0+4*-1 = 72 ?? No
typedef int zip_dig[5];
zip_dig sea[4];
76
96
116
136
156
9
8
1
9
5
9
8
1
0
5
9
8
1
0
3
9
8
1
1
5
CMPT 295
L09 - Arrays