CS计算机代考程序代写 c/c++ compiler assembler OSU CSE 2421

OSU CSE 2421
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
J.E.Jones

OSU CSE 2421
 Arrays
One-dimensional Multi-dimensional (nested) Multi-level
 Structures ◦ Allocation ◦ Access
◦ Alignment
J. E. Jones

OSU CSE 2421
struct rec { int a[4];
r a[0]|a[1]|a[2]|a[3]
size_t i;
i next
16 24 32
struct rec *next; }r;
0
 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
J. E. Jones

OSU CSE 2421
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.
J. E. Jones

OSU CSE 2421
struct rec { int a[4];
r r+4*idx a[0]|a[1]|a[2]|a[3]
size_t i;
i next
16 24 32
struct rec *next; };
0
 Generating Pointer to an Array Element
int *get_ap(struct rec *r, size_t idx) {
◦ Offset of each structure member determined at compile time
return &(r->a[idx]); }
◦ Compute as
r + 4*idx
# r in %rdi, idx in %rsi leaq (%rdi,%rsi,4), %rax ret
J. E. Jones

OSU CSE 2421
struct rec { int a[4];
r r+4*idx a[0]|a[1]|a[2]|a[3]
size_t i;
i next
16 24 32
struct rec *next; };
0
 Generating Pointer to an Array Element
int *get_ap(struct rec *r, size_t idx) {
◦ Offset of each structure member determined at compile time
return &(r->a[idx]); }
◦ Compute as
r + 4*idx
# r in %rdi, idx in %rsi leaq (%rdi,%rsi,4), %rax ret
Anyone curious about this?
J. E. Jones

OSU CSE 2421
} }
i next
 C Code
struct rec { int a[4]; size_t i;
void set_val(struct rec *r, int val) {
struct rec *next; };
while (r!=NULL) { int i = r->i; r->a[i] = val;
r = r->next;
r
loop:
movzlq 16(%rdi), %rax
Element i # loop:
movl movq testq
jne loop
%esi, (%rdi,%rax,4) 24(%rdi), %rdi
%rdi r %rsi val
%rdi, %rdi
#movslq=>Fig 3.6, move sign-extended double to quad
J. E. Jones
0
a[0]|a[1]|a[2]|a[3]
16 24 32
# i = M[r+16]
# M[r+4*i] = val
# r = M[r+24]
# Test r
# if !=0 goto loop
Register Value

OSU CSE 2421
 Unaligned Data
c i[0] p p+1
i[1]
v
p+9 p+17
c 3 bytes i[0] p+0 p+4
i[1]
4 bytes
v
p+24
Multiple of 4 Multiple of 8
Multiple of 8
p+5
 Aligned Data
◦ Primitive data type requires K bytes
struct S1 { char c; int i[2]; double v;
◦ Address must be multiple of K
◦ Structure beginning always starts at address multiple of 8
p+8
p+12 p+16 Multiple of 8
} *p, S1_r; p=&S1_r;
J. E. Jones

OSU CSE 2421
 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
J. E. Jones

OSU CSE 2421
 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
J. E. Jones

OSU CSE 2421
 Within structure:
◦ Must satisfy each element’s alignment requirement
struct S1 { char c; int i[2]; double v;
 Overall structure placement
◦ Each structure has alignment requirement K
} *p;
 K = Largest alignment of any element
◦ Initial address & structure length must be multiples of K
 Example:
◦ K = 8, due to double element
c 3 bytes i[0] p+0 p+4
i[1]
4 bytes
v
p+24
Multiple of 4 Multiple of 8
Multiple of 8
p+8
p+16 Multiple of 8
J. E. Jones

OSU CSE 2421
 For largest alignment requirement K
 Overall structure must be multiple of K
p+0
p+8
p+24
S2[0]
S2[1]
struct S2 { double v; int i[2]; char c;
} *p, S2[10];
v
i[0] i[1] c p+16
7bytes
Multiple of K=8
J. E. Jones

OSU CSE 2421
+24
a+48
 Overall structure length multiple of K  Satisfy alignment requirement
struct S2 { double v; int i[2]; char c;
for every element
} a[10];
a+0
a+24
v
i[0] i[1] c a+32 a+40
7bytes
a[0]
a[1] a[2]
a+48
• • • a+72
J. E. Jones

OSU CSE 2421
 Compute array offset 12*idx
◦ sizeof(S3), including alignment spacers
struct S3 { short i; float v; short j;
 Element j is at offset 8 within structure  Assembler gives offset a+8
} a[10];
◦ Resolved during linking
a[0] ••• a[idx]
•••
a+0 a+12
a+12*idx
short get_j(int idx) {
# %rdi = idx
}
J. E. Jones
return a[idx].j;
movzwl a+8(,%rax,4),%eax
#Fig 3.5,move zero-extended word to double
i a+12*idx
2 bytes v j 2 bytes a+12*idx+8
leaq (%rdi,%rdi,2),%rax # 3*idx

OSU CSE 2421
 Put large data types first
 Effect (K=4) c 3bytes
i
d 3bytes
struct S4 { char c; int i; char d;
struct S5 { int i; char c; char d;
} *p;
} *p;
icd
2 bytes
J. E. Jones

OSU CSE 2421
 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
J. E. Jones