Transcript Memory

Memory and Stack
Natawut Nupairoj
Assembly Language
1
Memory
•
•
•
•
In SPARC, there are only 32 registers.
Not enough to hold all data for computation.
We use memory to store variables.
Variables in memory can be:
C
char
short
int, long
Natawut Nupairoj
SPARC
byte
halfword
word
bits
8
16
32
Assembly Language
2
Memory
• All variables in memory must be “aligned”.
– A “short” variable is 16-bit long or halfword (2 bytes)
– It must be stored in the addressed that are divisible by
“two”, or “even address” (aligned to two-byte boundary)
– For example, 0, 2, 4, …, 1024, 1026, etc.
– An “int” variable is 32-bit long or one word (4 bytes)
– It must be stored in the addressed that are divisible by
“four”. (aligned to four-byte boundary).
– For example, 0, 4, 8, …, 1024, 1028, etc.
• This is for efficiency in hardware.
Natawut Nupairoj
Assembly Language
3
Memory
• The SPARC architecture is big endian.
• Store LSB (the smallest-numbered byte) at the
first address.
• For example: to store a short variable containing
0x0932 at address 1026 (must be aligned!)
• 0x32 (LSB) is stored at address 1026.
• 0x09 (MSB) is stored at address 1027.
• Note: an instruction must be word-aligned.
Why ?
Natawut Nupairoj
Assembly Language
4
The Stack
• We store automatic or “local” variables in the
memory called “Stack”.
• An automatic variable is a variable that is
accessible only inside a function.
int g;
int main() {
int i, j;
...
}
Natawut Nupairoj
Global var
Assembly Language
Local vars
5
The Stack Pointer
•
•
•
•
The stack is last-in-first-out (LIFO).
Each program has its own private stack.
%o6 aka. %sp is the stack pointer.
Stack is located near the top of memory (biggest
addressed).
• When the stack grows, the %sp decreases.
• When the stack shrinks, the %sp increases.
• Thus to get more spaces in the stack, we
subtract the number of bytes from the stack
pointer.
Natawut Nupairoj
Assembly Language
6
The Stack Pointer
0x00000000
• To get 64 bytes more:
– Sub %sp, 64, %sp
Program
Grows downward
new
%sp
%sp
Top of the stack
current
%sp
The Stack
The Stack
0xf8000000
Natawut Nupairoj
Assembly Language
7
The Stack Pointer
• The stack must be doubleword (8-byte) aligned.
• Thus, the address must be divisible by eight.
• If we want 94 bytes, we must ask for 96 bytes to
keep the stack aligned.
• Thus:
sub
%sp, 96, %sp
Done by assembler*
• Or we can:
add
%sp, -94 & -8, %sp
• Why -94&-8 ? Check out two’s complement.
Natawut Nupairoj
Assembly Language
8
The Frame Pointer
• The stack pointer is always changed as more
variables are needed.
• How can we refer to a variable ?
• Use the frame pointer, %fp or %i6.
• The frame pointer remains fixed for each
subroutine.
• At the beginning of the program, we execute a
“save” instruction to allocate space in the stack.
Natawut Nupairoj
Assembly Language
9
Frame and Stack Pointers
• Subroutine A calls B:
%sp
Stack area for A
int A() {
...
B();
...
}
%fp
%sp
Stack area for B
int B() {
...
}
Natawut Nupairoj
Before
Call
(%sp) %fp
After
Call
Stack area for A
(%fp)
Assembly Language
10
Save Instruction
• The save instruction must allocate space for
both local variables and registers.
• Must allocate 64 bytes + spaces for variables.
save %sp, -64-bytes_for_vars, %sp
• Suppose we want to store five “int” (4-byte)
variables (var0 - var4):
save %sp, (-64-(5*4)) & -8, %sp
• This is actually:
save %sp, -88, %sp
Natawut Nupairoj
Assembly Language
11
Save Instruction
%sp
64 bytes of storage to
save registers
var4: %fp - 20
var3: %fp - 16
var2: %fp - 12
Natawut Nupairoj
var1: %fp -
8
var0: %fp -
4
Assembly Language
%fp
12
Addressing Stack Variables
• As SPARC is the load-store architecture, we
cannot compute variables data from the stack
directly.
• We must load them to registers, compute, and
then store back to the stack.
• Remember all variables must be aligned based
on its size.
• SPARC has different load/store instructions for
each type.
Natawut Nupairoj
Assembly Language
13
Load Instructions
• ldsb - load signed byte, propagate sign.
• ldub - load unsigned byte, clear high 24 bits of
register.
• ldsh - load signed halfword, propagate sign.
• lduh - load unsigned halfword, clear high 16
bits of register.
• ld - load word
• ldd - load double, register number even, first
four bytes into register n, next four into register
n+1.
Natawut Nupairoj
Assembly Language
14
Load Instructions
ld
ld
[%fp - 4], %l1
[%fp - 8], %o2
mov -16, %l4
ld [%fp + %l4], %l3
ldd [%fp - 16], %g2
ldd [%fp - 16], %l5
Natawut Nupairoj
! Load var0 into %l1
! Load var1 into %o2
! Load var3 into %l3
! Load var3 into %g2
! and var2 into %g3
! Illegal, why ?
Assembly Language
15
Store Instructions
• stb - store low byte of register, bits 0 - 7 into
memory.
• sth - store low two bytes of register, bits 0 - 15
into memory.
• st - store register.
• std - store double, register number even, first
four bytes from register n, next four from
register n+1.
Natawut Nupairoj
Assembly Language
16
Store Instructions
st
st
sth
sth
st
st
%l1,
%o2,
%l4,
%l4,
%o2,
%o2,
Natawut Nupairoj
[%fp
[%fp
[%fp
[%fp
[%fp
[%fp
-
4]
! Store %l1 into
8]
! Store %o2 into
6]
! Store halfword
9]
! Illegal, why ?
4 + %l2]
! Illegal,
5120] ! Illegal, why ?
Assembly Language
var0
var1
of %l4
why ?
17
Variable Offsets in Stack
• We use the frame pointer as the base reference
to variables in the stack.
• All variables must be properly aligned.
• Example:
int a, b;
char ch;
short c, d;
unsigned e;
Natawut Nupairoj
//
//
//
//
4
1
2
4
bytes each
byte
bytes each
bytes
Assembly Language
18
Variable Offsets in Stack
%fp - 20
e
%fp - 16
%fp - 14
d
%fp - 12
c
a:
b:
ch:
c:
d:
e:
%fp - 10
%fp - 9
-
4
8
9
12
14
20
ch
%fp - 8
b
%fp - 4
a
Natawut Nupairoj
%fp
%fp
%fp
%fp
%fp
%fp
Assembly Language
19
Actual Addresses
%fp - 20
e
fp-20
fp-19
fp-18
fp-17
fp-4
fp-3
fp-2
fp-1
%fp - 16
%fp - 14
d
%fp - 12
c
%fp - 10
%fp - 9
ch
%fp - 8
b
%fp - 4
a
Natawut Nupairoj
Assembly Language
20
Offsets and Stack Allocation
• Use macro to arrange the offsets
define(a_s, -4)
define(b_s, -8)
define(ch_s, -9)
define(c_s, -12)
define(d_s, -14)
define(e_s, -20)
• Allocate spaces on stack:
save %sp, ((-64 - 20) & -8), %sp
==> save %sp, -84 & -8, %sp
==> save %sp, -88, %sp
Natawut Nupairoj
Assembly Language
21
Manipulate Variables in Stack
• To load and store
ld
ldub
ldsh
ld
[%fp
[%fp
[%fp
[%fp
+
+
+
+
a_s], %l0
ch_s], %l1
d_s], %l2
e_s], %l3
! char type is unsigned.
! short type is signed.
• To compute:
b = a + c;
Natawut Nupairoj
ld
ldsh
add
st
[%fp+a_s], %l0
[%fp+c_s], %l1
%l0, %l1, %l2
%l2, [%fp+b_s]
Assembly Language
22
Variables in Registers
• Some variables are used very often.
– Loop counters
• We can use registers to hold their values
instead of using stack.
• In C, we use a keyword “register”.
register int i;
// i is in a register.
• When referred to these variables, we use values
from registers directly.
Natawut Nupairoj
Assembly Language
23
Variables in Registers
int a, b;
register int j, k;
int x, y;
• Only a, b, x, and y are in the stack.
• j and k are in registers.
define(a_s,
define(b_s,
define(x_s,
define(y_s,
define(j_r,
define(k_r,
Natawut Nupairoj
-4)
-8)
-12)
-16)
l0)
l1)
Assembly Language
24
Variables in Registers
• To compute:
j = 19;
a = 8;
y = j - 3 + a;
mov
mov
st
sub
ld
add
st
19, %j_r
9, %l2
%l2, [%fp+a_s]
%j_r, 3, %l2
%l3, [%fp+a_s]
%l2, %l3, %l2
%l2, [%fp+y_s]
• Note: we use %l2 and %l3 as temporary
registers.
Natawut Nupairoj
Assembly Language
25
Our Fourth Program
main()
{
int a, b, c;
register int i;
i
a
b
c
=
=
=
=
0;
100;
15;
0;
Natawut Nupairoj
while(i < 20) {
c += a - b;
a--;
i = i + 2;
}
}
Assembly Language
26
Our Fourth Program
define(a_s, -4)
define(b_s, -8)
define(c_s, -12)
define(i_r, l0)
.global main
main: save %sp, (-64 + -12) & -8, %sp
clr %i_r
! i = 0;
mov 100, %l1
st
%l1, [%fp + a_s]
! a = 100;
mov 15, %l1
st
%l1, [%fp + b_s]
! b = 15;
Natawut Nupairoj
Assembly Language
27
Our Fourth Program
clr
st
loop: cmp
bge
nop
ld
ld
sub
ld
add
st
Natawut Nupairoj
%l1
%l1, [%fp + c_s]
%i_r, 20
done
[%fp
[%fp
%l1,
[%fp
%l1,
%l1,
+ a_s], %l1
+ b_s], %l2
%l2, %l3
+ c_s], %l1
%l3, %l1
[%fp + c_s]
! c = 0;
! a - b
! c + a - b
! c += a - b;
Assembly Language
28
Our Fourth Program
ld
sub
st
[%fp + a_s], %l1
%l1, 1, %l1
%l1, [%fp + a_s]
add
ba
nop
%i_r, 2, %i_r
loop
done: mov
ta
Natawut Nupairoj
! a--;
! i = i + 2
1, %g1
0
Assembly Language
29