Microsoft PowerPoint – 29_X86-64_Assembly_Language_Part_9
O
SU
C
SE
2
42
1
J.E.Jones
Required Reading:
Computer Systems: A Programmer’s Perspective, 3rd Edition
Chapter 3, Sections 3.9.1 and 3.9.3; 3.9.2 is optional
O
SU
C
SE
2
42
1
J. E. Jones
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structures
◦ Allocation
◦ Access
◦ Alignment
O
SU
C
SE
2
42
1
J. E. Jones
Structure represented as block of memory
◦ Big enough to hold all fields
Fields ordered according to declaration
◦ Even if another ordering could yield a more compact
representation
Compiler determines overall size + positions of fields
◦ Machine-level program has no understanding of the
structures in the source code
a[0]|a[1]|a[2]|a[3]
r
i next
0 16 24 32
struct rec {
int a[4];
size_t i;
struct rec *next;
}r;
O
SU
C
SE
2
42
1
J. E. Jones
From Wikipedia:
According to the 1999 ISO C standard (C99), size_t is an unsigned
integer type of at least 16 bits (see sections 7.17 and 7.18.3).
size_t is an unsigned data type defined by several C/C++ standards,
(e.g., the C99 ISO/IEC 9899 standard) that is defined in stddef.h. It can
be further imported by inclusion of stdlib.h as this file internally sub
includes stddef.h.
This type is used to represent the size of an object. Library functions
that take or return sizes expect them to be of type or have the return
type of size_t. Further, the most frequently used compiler-based
operator sizeof should evaluate to a constant value that is compatible
with size_t.
As an implication, size_t is a type guaranteed to hold any array index.
O
SU
C
SE
2
42
1
J. E. Jones
# r in %rdi, idx in %rsi
leaq (%rdi,%rsi,4), %rax
ret
int *get_ap(struct rec *r, size_t idx)
{
return &(r->a[idx]);
}
Generating Pointer to
an Array Element
◦ Offset of each structure
member determined at
compile time
◦ Compute as
r + 4*idx
r+4*idx
a[0]|a[1]|a[2]|a[3]
r
i next
0 16 24 32
struct rec {
int a[4];
size_t i;
struct rec *next;
};
O
SU
C
SE
2
42
1
J. E. Jones
# r in %rdi, idx in %rsi
leaq (%rdi,%rsi,4), %rax
ret
int *get_ap(struct rec *r, size_t idx)
{
return &(r->a[idx]);
}
Generating Pointer to
an Array Element
◦ Offset of each structure
member determined at
compile time
◦ Compute as
r + 4*idx
r+4*idx
a[0]|a[1]|a[2]|a[3]
r
i next
0 16 24 32
struct rec {
int a[4];
size_t i;
struct rec *next;
};
Anyone curious
about this?
O
SU
C
SE
2
42
1
J. E. Jones
loop: # loop:
movzlq 16(%rdi), %rax # i = M[r+16]
movl %esi, (%rdi,%rax,4) # M[r+4*i] = val
movq 24(%rdi), %rdi # r = M[r+24]
testq %rdi, %rdi # Test r
jne loop # if !=0 goto loop
#movslq=>Fig 3.6, move sign-extended double to quad
void set_val(struct rec *r, int val)
{
while (r!=NULL) {
int i = r->i;
r->a[i] = val;
r = r->next;
}
}
C Code
Register Value
%rdi r
%rsi val
struct rec {
int a[4];
size_t i;
struct rec *next;
};
Element i
r
i next
0 16 24 32
a[0]|a[1]|a[2]|a[3]
O
SU
C
SE
2
42
1
J. E. Jones
Unaligned Data
Aligned Data
◦ Primitive data type requires K bytes
◦ Address must be multiple of K
◦ Structure beginning always starts at address multiple of 8
c i[0] i[1] v3 bytes 4 bytes
p+0 p+4 p+8 p+16 p+24
Multiple of 4 Multiple of 8
Multiple of 8 Multiple of 8
c i[0] i[1] v
p p+1 p+5 p+9 p+17
struct S1 {
char c;
int i[2];
double v;
} *p, S1_r; p=&S1_r;
p+12
O
SU
C
SE
2
42
1
J. E. Jones
Aligned Data
◦ Primitive data type requires K bytes
◦ Address must be multiple of K
◦ Required on some machines; advised on x86-64
Motivation for Aligning Data
◦ Memory accessed by (aligned) chunks of 4 or 8 bytes (system
dependent)
Inefficient to load or store datum that spans quad word boundaries
Virtual memory trickier when datum spans 2 pages (Systems II
topic)
C Compiler
◦ Inserts gaps in structure to ensure correct alignment of fields
O
SU
C
SE
2
42
1
J. E. Jones
1 byte: char, …
◦ no restrictions on address
2 bytes: short, …
◦ lowest 1 bit of address must be 02
4 bytes: int, float, …
◦ lowest 2 bits of address must be 002
8 bytes: double, long, char *, …
◦ lowest 3 bits of address must be 0002
16 bytes: long long, long double (gcc on Linux)
◦ lowest 4 bits of address must be 00002
O
SU
C
SE
2
42
1
J. E. Jones
struct S1 {
char c;
int i[2];
double v;
} *p;
Within structure:
◦ Must satisfy each element’s alignment requirement
Overall structure placement
◦ Each structure has alignment requirement K
K = Largest alignment of any element
◦ Initial address & structure length must be multiples of K
Example:
◦ K = 8, due to double element
c i[0] i[1] v3 bytes 4 bytes
p+0 p+4 p+8 p+16 p+24
Multiple of 4 Multiple of 8
Multiple of 8 Multiple of 8
O
SU
C
SE
2
42
1
J. E. Jones
For largest alignment requirement K
Overall structure must be multiple of K
struct S2 {
double v;
int i[2];
char c;
} *p, S2[10];
v i[0] i[1] c 7 bytes
p+0 p+8 p+16 p+24
Multiple of K=8
S2[1]S2[0]
O
SU
C
SE
2
42
1
J. E. Jones
Overall structure length multiple of K
Satisfy alignment requirement
for every element
struct S2 {
double v;
int i[2];
char c;
} a[10];
v i[0] i[1] c 7 bytes
+24 a+32 a+40 a+48
a[0] a[1] a[2] • • •
a+0 a+24 a+48 a+72
O
SU
C
SE
2
42
1
J. E. Jones
Compute array offset 12*idx
◦ sizeof(S3), including alignment spacers
Element j is at offset 8 within structure
Assembler gives offset a+8
◦ Resolved during linking
struct S3 {
short i;
float v;
short j;
} a[10];
}
short get_j(int idx)
{
return a[idx].j;
}
# %rdi = idx
leaq (%rdi,%rdi,2),%rax # 3*idx
movzwl a+8(,%rax,4),%eax
#Fig 3.5,move zero-extended word to double
a[0] • • • a[idx] • • •
a+0 a+12 a+12*idx
i 2 bytes v j 2 bytes
a+12*idx a+12*idx+8
O
SU
C
SE
2
42
1
J. E. Jones
Put large data types first
Effect (K=4)
struct S4 {
char c;
int i;
char d;
} *p;
struct S5 {
int i;
char c;
char d;
} *p;
c i3 bytes d 3 bytes
ci d 2 bytes
O
SU
C
SE
2
42
1
J. E. Jones
Arrays
◦ Elements packed into contiguous region of memory
◦ Use index arithmetic to locate individual elements
Structures
◦ Elements packed into single region of memory
◦ Access using offsets determined by compiler
◦ Possible to require internal and external padding to ensure
alignment
Combinations
◦ Can nest structure and array code arbitrarily