Transcript CDA 3101 Spring 2001 Introduction to Computer Organization

CDA 3101
Fall 2013
Introduction to Computer Organization
Procedure Support
& Number Representations
11,13 September 2013
Review
• 3 formats of MIPS instructions in binary:
– Op field determines format
R
I
J
6 bits
op
op
op
5 bits
rs
rs
5 bits
rt
rt
5 bits
rd
5 bits
shamt
immediate
destination address
6 bits
funct
• Operands
– Registers: $0 to $31 mapped onto: $zero, $at,
$v_, $a_, $s_, $t_, $gp, $sp, $fp, $ra
– Memory : Mem[0], Mem[4], … , Mem[4294967292]
• Index is the “address” (Array index => Memory index)
• Stored program concept (instructions are numbers!)
Overview
•
•
•
•
•
•
•
Memory layout
C functions
MIPS support (instructions) for procedures
The stack
Procedure Conventions
Manual Compilation
Conclusion
Memory Layout
0x00000000
(4MB)
0x00400000
Text segment
0x10000000
$gp (0x10008000)
0x10010000
Static data
Data segment
Dynamic data
Stack segment
0x7FFFFFFF
(2GB)
0xFFFFFFFF
Data Segment
0x10000000
$gp (0x10008000)
0x10008020
(64KB)
lui $s0, 0x1001
# s0 = 0x10010000
lw $v0, 0x8020($s0) # 0x8020 = (-7fe0)16
lw $v0, 0x0020($gp)
0x10010000
2 instructions (lui and lw) are
needed to access this memory
0xFFFFFFFF
C Functions / Procedures
main() {
int i, j, k;
int fact (int mcand, int mlier) {
int product;
product = 0;
while (mlier > 0) {
product = product + mcand;
mlier = mlier -1; }
return product;
…
i = fact(j,k);
…
}
}
What information must compiler keep track of?
Procedure Call Bookkeeping
• Problems
–
–
–
–
–
Procedure address
Return address
Arguments
Return value
Local variables
• Register conventions
Labels
$ra
$a0, $a1, $a2, $a3
$v0, $v1
$s0, $s1, …, $s7
• Dynamic nature of procedures
• Procedure call frames
• Arguments, save registers, local variables
Procedure Call Convention
• Software rules for using registers
Name
$zero
$at
$v0-$v1
$a0-$a3
$t0-$t7
$s0-$s7
$t8-$t9
$k0-$k1
$gp
$sp
$fp
$ra
Register Number
0
1
2-3
4-7
8-15
16-23
24-25
26-27
28
29
30
31
Usage
the constant value 0
reserved for the assembler
expr. evaluation and function result
arguments (procedures/functions)
temporaries
saved
more temporaries
reserved for the operating system
global pointer
stack pointer
frame pointer
return address
Preserved on call
n.a.
n.a.
no
yes
no
yes
no
n.a.
yes
yes
yes
yes
The Stack
ProcedureTwo
ProcedureOne
main
0x7FFFFFFF
0xFFFFFFFF
Stack
Frames
Stack Frames
$sp
$a0
$a1
$a2
$a3
local variables
saved registers
ProcedureOne’s
(callee) frame
$fp, $ra, S-registers
$v0
$v1
$fp
argument 5
argument 6
Saved VAT registers
Main’s (caller) frame
Caller / Callee Conventions
• Immediately before the caller invokes the callee
– Pass arguments ($a0 - $a3). Extra args: push on the stack
– Save caller-saved registers ($a0 - $a3; $t0 - $t9)
– Execute jal (jumps and links to callee; saves return addr)
• Just before the callee starts executing
– Allocate memory for the frame ($sp = $sp – fsize)
– Save callee-saved registers ($s0-$s7; $fp; $ra)
– $fp = $sp + (fsize – 4)
• Immediately before the callee returns to caller
–
–
–
–
Place the returned value in register $v0
Restore all callee-saved registers
Pop the stack frame ($sp = $sp + fsize); restore $fp
Return by jumping to the address in $ra
Procedure Support
main( ) {
…
s = sum (a, b);
…
}
address
1000
1004
1008
1012
1016
2000
2004
add
add
addi
j
...
sum:
jr
int sum(int x, int y) {
return x + y;
}
$a0,$s0,$zero
$a1,$s1,$zero
$ra,$zero,1016
sum
#
#
#
#
$a0 = x
$a1 = y
$ra=1016
jump to sum
add $v0,$a0,$a1
$ra
# jump to 1016
Jump and Link Instruction
•
Single instruction to jump and save return
address
– jal: jump and link (Make the common case fast)
– J Format Instruction: jal label
– Should be called laj
1. (link): save address of next instruction into $ra
2. (jump): jump to label
1000
1004
1008
1012
2000
2004
add
add
jal
...
sum:
jr
$a0,$s0,$zero # $a0 = x
$a1,$s1,$zero # $a1 = y
sum # $ra = 1012; jump to sum
add $v0,$a0,$a1
$ra
# jump to 1012
Nested Procedures
int sumSquare(int x, int y) {
return mult(x,x) + y;
}
sumSquare:
subi $sp,$sp,12
# space on stack
sw $ra,$ 8($sp)
# save ret addr
sw $a0,$ 0($sp)
# save x
sw $a1,$ 4($sp)
# save y
addi $a1,$a0,$zero # mult(x,x)
jal mult
# call mult
lw $ra,$ 8($sp)
# get ret addr
lw $a0,$ 0($sp)
# restore x
lw $a1,$ 4($sp)
# restore y
add $vo,$v0,$a1
# mult()+y
addi $sp,$sp,12
# free stack space
jr $ra
Example (1/2)
main( ) {
int f;
f = fact (10);
printf (“Fact(10) = %d\n”, f);
}
int fact ( int n) {
if (n < 1)
return (1);
else
return (n * fact(n-1);
}
Old $a0
Old $ra
Old $fp
fact (8)
Old $a0
Old $ra
Old $fp
fact (9)
Old $a0
Old $ra
Old $fp
fact (10)
Old $ra
Old $fp
main
Example (2/2)
main:
subu
sw
sw
addiu
li
la
syscall
li
jal
addu
li
syscall
lw
lw
addiu
jr
$sp, $sp, 32
$ra, 20($sp)
$fp, 16($sp)
$fp, $sp, 28
$v0, 4
$a0, str
fact:
$a0, 10
fact
$a0, $v0, $zero
$v0, 1
L2:
$ra, 20($sp)
$fp, 16($sp)
$sp, $sp, 32
$ra
L1:
subu
sw
sw
addiu
sw
lw
bgtz
li
j
lw
subu
move
jal
lw
mul
lw
lw
addiu
jr
$sp, $sp, 32
$ra, 20($sp)
$fp, 16($sp)
$fp, $sp, 28
$a0, 0($fp)
$v0, 0($fp)
$v0, L2
$v0, 1
L1
$v1, 0($fp)
$v0, $v1, 1
$a0, $v0
fact
$v1, 0($fp)
$v0, $v0, $v1
$ra, 20($sp)
$fp, 16($sp)
$sp, $sp, 32
$ra
Summary
• Caller / callee conventions
– Rights and responsibilities
– Callee uses VAT registers freely
– Caller uses S registers without fear of being overwritten
• Instruction support: jal label and jr $ra
• Use stack to save anything you need. Remember to
leave it the way you found it
• Register conventions
– Purpose and limits of the usage
– Follow the rules even if you are writing all the code
yourself
New Topic – Number Systems
Application (browser)
Software
Compiler
Assembler
Operating
System
(Linux, Win)
Instruction Set Architecture (ISA)
Datapath & Control
Hardware
Memory
Digital Logic
Circuit Design
Transistors
I/O System
The Arithmetic and Logic Unit
Datapath
Memory
load/store
0000
1010
1100
0101
1001
1111
0110
1000
1100
0101
1010
0000
0110
1000
1111
1001
1010
0000
0101
1100
1111
1001
1000
0110
0101
1100
0000
1010
1000
0110
1001
1111
...
program & data
Control
add $t0, $s1, $s2
and $t0, $s1, $s2
lw $t0, 100($s1)
beq $s1, $s2, L
#
#
#
#
$s1 + $s2
$s1 AND $s2
$s1 + 100
$s1 = = $s2
I/O
Computer Arithmetic
• Computer arithmetic vs. Mathematical theory
– Fixed-precision numbers
• Not closed with respect to +, -, *, /
– Overflow
– Underflow
– Undefined
Expressible Integers
-231
231-1
• Laws of normal algebra do not always hold in computers
– a + (b - c) = (a + b) - c
– a * (b – c) = a * b – a * c
– Binary numbers
( 1101 1010 1101 )2
• Base: 2
• Digits: 0 and 1
( B
A
n-1
• Decimal number = Σ di * 2i
i=0
(d31 d30 d29
D )16
. . . d2 d 1 d0)
Data Representation
Bits can represent anything:
• Characters
– 26 letters => 5 bits
– Upper/lower case + punctuation => 7 bits (in 8)
– Rest of the world’s languages => 16 bits (unicode)
• Unsigned numbers (0, 1, …, 2n-1)
• Logical values
– 0 -> False, 1 => True
• Colors
• Locations / addresses / commands
• But n bits can only represent 2n distinct objects
Negative Numbers
• We discussed unsigned numbers – What about the sign?
• Naive solution: define leftmost bit to be sign
– 0 means +, 1 means - => sign bit
– Remainder of bits can be numerical value of number
• This representation called sign and magnitude
• MIPS uses 32-bit integers (16-bit immediates/displacements)
+1ten would be:
0000 0000 0000 0000 0000 0000 0000 0001
- 1ten would be:
1000 0000 0000 0000 0000 0000 0000 0001
Problems with Sign and Magnitude
1. Arithmetic circuit more complicated
–
Special steps depending whether signs are the
same or different (e.g., -x . -y = xy = x * y)
2. Two zero representations
–
–
–
•
0x00000000 = +0ten
0x80000000 = -0ten
Programming implications (+0 == -0)
Sign and magnitude was abandoned
because of confusion over zero
Let’s Try: One’s Complement
• Complement the bits to get the negative
• Example:
710 = 001112
-710 = 110002
• Positive numbers have leading 0s, negative
numbers have leadings 1s.
00000
10000
...
11110
00001
11111
• Still two zeros (oops.. )
– 0x00000000 = +0ten
– 0xFFFFFFFF = -0ten
• Arithmetic not too hard 
...
01111
Better: Two’s Complement
• Positive numbers start with 0
• Negative numbers are the inverse of positive + ONE
• Example
110 = 000000012
-110 = 111111102 + 12 = 111111112
710 = 000001112
-710 = 111110002 + 12 = 111110012
• Positive numbers can have infinitely many leading 0’s
• Negative numbers can also have infinitely many leading
1’s
Two’s Complement Number Line
0000
0001
1111
1110
0010
0
-1
1
-2
2
0011
1101
3
-3
1100
4
-4
5
-5
0101
1011
6
-6
-7
1010
1001
-8 -6
0100
-4
-8
7
0111
1000
-2
0
0110
2
4
6
8
•
•
•
•
•
•
2 n-1 non-negatives
2 n-1 negatives
one zero
2 n-1-1 positives
comparison
Overflow due to
circulant domain
Example: Two’s Complement
0000 ... 0000 0000 0000 0000two =
0000 ... 0000 0000 0000 0001two =
0000 ... 0000 0000 0000 0010two =
...
0111 ... 1111 1111 1111 1101two =
0111 ... 1111 1111 1111 1110two =
0111 ... 1111 1111 1111 1111two =
1000 ... 0000 0000 0000 0000two =
1000 ... 0000 0000 0000 0001two =
1000 ... 0000 0000 0000 0010two =
...
1111 ... 1111 1111 1111 1101two =
1111 ... 1111 1111 1111 1110two =
1111 ... 1111 1111 1111 1111two =
0ten
1ten
2ten
2,147,483,645ten
2,147,483,646ten
2,147,483,647ten
–2,147,483,648ten
–2,147,483,647ten
–2,147,483,646ten
–3ten
–2ten
–1ten
Two’s Complement How-To
• Can represent positive and negative numbers by
first bit (MSB) as –231 position, then positive 2n:
d31 x -231 + d30 x 230 + ... + d2 x 22 + d1 x 21 + d0 x 20
• Example
1111 1111 1111 1111 1111 1111 1111 1100two
= 1x-231 +1x230 +1x229+... +1x22+0x21+0x20
= -231 + 230 + 229 + ... + 22 + 0 + 0
= -2,147,483,648ten + 2,147,483,644ten
= -4ten
• Note! Must specify width to find MSB => 32bits
is used in MIPS, so d31 is MSB
Two’s Complement Negation
• Invert (every 0 to 1 and every 1 to 0),
then add 1 to the result
– Sum of number and its one’s complement must be
111...111two = -1ten
– Let x’ denote the inverted representation of x
– Then x + x’ = -1  x + x’ + 1 = 0  x’ + 1 = -x
• Example: x = -4 to +4 to -4
x=-4 : 1111 1111 1111 1111 1111 1111 1111 1100two
x’ : 0000 0000 0000 0000 0000 0000 0000 0011two
x’ + 1: 0000 0000 0000 0000 0000 0000 0000 0100two
invert: 1111 1111 1111 1111 1111 1111 1111 1011two
add 1 : 1111 1111 1111 1111 1111 1111 1111 1100two
Signed vs. Unsigned Comparisons
• X = 1111 1111 1111 1111 1111 1111 1111 1100two
• Y = 0011 1011 1001 1010 1000 1010 0000 0000two
Ambiguity:
• Is X > Y?
– Unsigned: YES
– Signed: NO
• Converting to decimal to check
– Signed comparison:
-4ten < 1,000,000,000ten?
– Unsigned comparison:
-4,294,967,292ten < 1,000,000,000ten
2’s Compl. Sign Extension
• Problem: Convert 2’s complement number using n
bits to more than n bits
• Solution: Replicate the most significant bit (sign
bit) of smaller to fill new bits
–2’s comp. positive number has infinite 0s to the left
–2’s comp. negative number has infinite 1s to the left
–Bit representation hides leading bits; sign extension
restores some of the infinite number of leading bits
MSB
–16-bit -4ten to 32-bit:
16-bit
1111 1111 1111 1100two
32-bit
1111 1111 1111 1111 1111 1111 1111 1100two
Conclusion
• We represent objects in computers as bit patterns:
n bits =>2n distinct patterns
• Decimal for humans, binary for computers
• 2’s complement universal in computing: cannot
avoid, so we will learn
• Computer operations on the representation are
abstraction of real operations on the real thing
• Overflow:
- Numbers infinite
- Computer finite
• Enjoy: Weekend!