Design Goals:
Minimize the number of memory accesses
Minimize the instruction size
Variables:
Always static: name, type, size, scope
Always dynamic: value (unless final or const)
Depends: memory location and lifetime
Register Transfer Language (RTL)
The pseudo language we will use to describe instruct semantics
The Simple Machine (SM213) memory access instructions:
Assume the variable a is stored at address 0x1234 with value 7.
Write comments beside each line to describe the following sequence of
instructions:
SM213 logical instructions (i.e., shifting), NOP, and halt:
r[0] <- 10
r[1] <- 0x1234
r[2] <- m[r[1]]
r[2]<-r[0]+r[2] r2=10+7=17 m[r[1]] <- r[2] a = 17
r0 = 10
r1 = address of a
r2 = value of a (7)
Remember that array access is computed from base and index. Write out the ASSM and Machine Instructions for each RTL line.
Internal state:
pc: address of next instruction to fetch instruction: value of current instruction
SM213 arithmetic instructions:
Syntax
Each line is in the form:
Value in memory at address a: Register number i:
Examples:
LHS <- RHS
m[a]
r[i]
Putting it all together:
r0 = 0 r1 = &a a=0
r2 = a
r3 = &b b[a] = [a]
base r3 (b) offset r2 (a) store r2 (a)
Cycle stages:
SHOW DEMO WITH SNIPPET 1b
r0=0
r1 = 0x1000 r2 = 0
r3 = 0x2000
0x1000: -1 0 a
0x2000: 0x2004: 0x2008
-1 -1
0 b[0] b[1] b[2]
Declaration of variables:
int a=5; Declare an integer variable, value: integer (5) int* b=&a; Declare a pointer variable, value: integer address
The variable b has a static address, but a dynamic value. The value of b is an address (that’s why its type is int*)
Dereferencing
&x: get the address assigned to variable x
x : get the value in memory at the address assigned to x *x: get the value at the memory location pointed to by x
Dynamic allocation
malloc: allocates memory dynamically. No type, constructor sizeof: number of bytes to allocate
Code and Memory tracing examples:
Syntax for accessing an element of a static array is the same as for a dynamic array.
Static:
Dynamic:
Code:
int a; int* b;
a = 5; b = &a;
Output:
a: 5
&a: 0x1000 b: 0x1000 *b: 5
&b: 0x2000
Code:
int a;
int b[10];
int* c= &a;
a = 8;
b[0] = a-2;
c = &b[0];
Output:
a: 8
&a: 0x1000 b[0]: 6 &b[0]:0x2000 c: 0x2000 &c: 0x3000 *c: 6
Address 0x1000
... 0x2000
Address 0x1000 ...
0x2000 0x2004 0x2008
... 0x3000
Value 5a
0x1000 b
Value 8a
06 b[0] 0 b[1]
0
0x1000 c 0x2000
...
Pointer arithmetic
Which implementation is faster? Why?
Static – the compiler does not know the array address of the dynamic version, resulting in an extra memory read. Thus, accessing dynamic arrays is slower.
Tradeoffs - Performance vs flexibility
Static array benefits:
Faster: allocation done at compile time. Fewer instructions Array bounds checking (size of array is known)
Cons: cannot resize (difficult to predict right size)
Dynamic array benefits:
Flexible: don’t need to know size ahead of time
Cons: Slower, extra instr. (extra bad: memory access!)
Adding x to a pointer of type Y*, adds (x * sizeof(Y)) to the pointers memory address value.
From example above:
printf(“%d\n”, *(c+4));
c = c+2;
printf(“%d\n”, *c);
Output:
0 i.e. value at b[4] 0 i.e. value at b[2]
Note: b is allocated statically
The array is allocated dynamically, and then the address of the dynamically allocated memory is assigned to b.