Chapter 2 Language of the Computer
1
H igh-level language program (in C)
swap(int v[], int k) {int temp;
Assembly swap: language
p ro g ra m
(for MIPS)
muli
add $2, $4,$2 lw $15, 0($2) lw $16, 4($2) sw $16, 0($2) sw $15, 4($2) jr $31
Binary machine language
p ro g ra m
(for MIPS)
00000000101000010000000000011000 00000000000110000001100000100001 10001100011000100000000000000000 10001100111100100000000000000100 10101100111100100000000000000000 10101100011000100000000000000100 00000011111000000000000000001000
}
temp = v[k]; v[k] = v[k+1]; v[k+1] = temp;
Compiler
Assembler
$2, $5,4
PAT01F04.eps 2
Review: Number and Base
• Number with base b: uses b digits
– Decimalnumber:base=10,
– Binary number: base = 2,
– Hexadecimal number: base = 16,
e.g.,108ten
e.g., 1101100 two e.g., 6C hex
(uses 16 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F)
3
Review: Converting to Decimal
• (d n-1 d n-2 … d2 d0 ) b
= d n-1 * b n-1 + d n-2 * b n-2 + …..+ d 1 * b 1 + d 0 * b 0
108ten =1*102 +0*101 +8*100
1101110two =1*26 +1*25 +0*24 +1*23 +1*22 +1*21 +0*20 6Chex =6*161 +C*160
4
Conversion from decimal to binary Convert 25 ten to a binary number.
Keep dividing by a base 2, and keep track of remainders.
2 )_25
2 )_12 –1 2 )_6 –0 2)_3 –0 2 )_1 –1
Write in bottom up order 11001 two
0 –1
5
Decimal, Hexadecimal, and Binary
Dec Hex Bin
00 0 0000
01 1 0001
02 2 0010
03 3 0011
04 4 0100
05 5 0101
06 6 0110
07 7 0111
08 8 1000
09 9 1001
10 A 1010
11 B 1011
12 C 1100
13 D 1101
14 E 1110
15 F 1111
Examples:
1010 1100 0011 (binary) = 0xAC3 10111 (binary) = 0001 0111 (binary)
= 0x17
0x3F9 = 0011 1111 1001 (binary)
6
Instructions:
• Language of the Machine/Computer
• We’ll be working with the MIPS (Million Instruction Per Second) instruction set architecture
– similartootherarchitecturesdevelopedsincethe1980’s
– Almost100millionMIPSprocessorsmanufacturedin2002
– usedbyNEC,Nintendo,Cisco,SiliconGraphics,Sony,…
1400 1300 1200 1100 1000
Other SPARC Hitachi SH PowerPC Motorola 68K MIPS
900
800 ARM 700
600
500
400
300
200
100
0
IA-32
1998 1999 2000
2001 2002
7
MIPS arithmetic
• All arithmetic instructions have 3 operands
• Operand order is fixed (destination first) Example:
C code:
a = b + c;
MIPS ‘code’:
add a, b, c
Example:
C code:
a = b – c;
sub a, b, c
MIPS ‘code’:
(we’ll talk about registers in a bit)
8
MIPS arithmetic
• Of course this complicates some things…
C code: a = b + c + d;
MIPS code: add a, b, c add a, a, d
• Operands must be registers, only 32 registers provided
• Each register contains 32 bits (in MIPS)
9
Operands of Hardware
• Operands in MIPS arithmetic instructions must be registers, not variables as in C.
• A compiler associates variables with registers
• There are only 32 registers, each of which is 32 bits long.
• (“smaller is faster” -> too many registers may increase clock cycle time)
• Registers can be numbered or named $s0 – $s7 maps to register #16 – 23 $t0 – $t7 maps to register #8 – 15
10
Registers vs. Memory
• Arithmetic instructions (such as “add” and “sub”) operands must be registers,
— only 32 registers provided
• Compiler associates variables with registers
Control
Input
Datapath Processor
Output I/O
Memory
11
Spilling Registers
• What if a program has more variables than registers?
• The compiler tries to keep the most frequently used variables in registers and place the rest in memory, using loads and stores to move variables between registers and memory.
• The process of putting less commonly used variables into memory is called “spilling registers”.
12
Name
Register number
Registers Usage
$zero
$v0-$v1
$a0-$a3
$t0-$t7
$s0-$s7
$t8-$t9
$gp 28 $sp 29 $fp 30 $ra 31
0 2-3 4-7 8-15 16-23 24-25
the constant value 0
values for results and expression evaluation arguments
temporaries (caller saves/callee can clobber) saved (callee saves/caler can clobber)
more temporaries
global pointer
stack pointer
frame pointer
return address
Register 1 ($at) reserved for assembler, 26-27 ($k0,$k1) for operating system
13
Example
• What is the output (MIPS) of the compiler for the following C statement?
d = (a + b) – (a + c)
Assume that the compiler associates the variables a, b, c, and d with the registers $s1, $s2, $s3, and $s4 respectively.
add $t1, $s1, $s2 add $t2, $s1, $s3 sub $s4, $t1, $t2
14
Memory Organization
• Viewed as a large, single-dimension array, with an address.
• A memory address is an index into the array
• “Byte addressing” means that the index points to a byte (8 bits) of memory.
…
6 5 4 3 2 1 0
8 bits of data 8 bits of data 8 bits of data 8 bits of data 8 bits of data 8 bits of data 8 bits of data
15
Memory Organization
• Bytes are nice, but most data items use larger “words”
• For MIPS, a “word “ is 32 bits or 4 bytes. …
12 32 bits of data
8 4 0
32 bits of data 32 bits of data 32 bits of data
Registers hold 32 bits of data
• Each register holds 1 word.
• Alignment restriction; words must start at addresses 0, 4, 8, …
• 232 bytes with byte addresses from 0 to 232-1
• 230 words with byte addresses 0, 4, 8, … 232-4
16
Load Word instruction • Load Word
lw $s1, 0($s2)
# $s1 <- Memory[$s2]
$s1 $s2
1024 0
8
1024
# load the word whose starting address is the # one stored in $s2, into $s1
memory
17
Save Word instruction
• Save Word
sw $s1, 32($s2)
# $s1 -> Memory[$s2 + 32]
$s1 $s2
13 1056 1024
# copes what is in $s1 into a register of the # memory
1024 0
memory
18
Instructions • Example:
• Assume: h is associated with $s2, and the base address of the array A is in $s3.
C code: A[12] = h + A[8];
MIPS code: lw $t0, 32($s3) add $t0, $s2, $t0
sw $t0, 48($s3)
• A[0] is stored in 0($3), so A[8] is in (0+8*4) = 32 ($2)
• A[12] is at (0+12*4)= 48 (1 word is 4 bytes)
• Remember arithmetic operands are registers, not memory! Can’t write: add 48($s3), $s2, 32($s3)
19
Our First Example
• Can we figure out the code?
swap(int v[], int k);
{ int temp;
}
swap:
muli $2, $5, 4
temp = v[k] v[k] = v[k+1]; v[k+1] = temp;
add $2, $4, $2 lw $15, 0($2) lw $16, 4($2) sw $16, 0($2) sw $15, 4($2) jr $31
20
So far we’ve learned: • MIPS
• Instruction
Meaning
— loading words but addressing bytes — arithmetic on registers only
add $s1, $s2, $s3
sub $s1, $s2, $s3
lw $s1, 100($s2)
sw $s1, 100($s2)
$s1 = $s2 + $s3
$s1 = $s2 – $s3
$s1 = Memory[$s2+100]
Memory[$s2+100] = $s1
21
Immediate instruction
• Add constant 4 to register $s3?
If AddrConstant4 is the memory address of the constant 4, then lw $t0, AddrConstant4($s1)
add $s3, $s3, $t0
Instead, we can use add immediate or addi addi $s3, $s3, 4 # $s3 = $s3 + 4
Design Principle: Make the common case fast
22
Review: Decimal, Hexadecimal, and Binary
Dec Hex Bin
00 0 0000
01 1 0001
02 2 0010
03 3 0011
04 4 0100
05 5 0101
06 6 0110
07 7 0111
08 8 1000
09 9 1001
10 A 1010
11 B 1011
12 C 1100
13 D 1101
14 E 1110
15 F 1111
Examples:
1010 1100 0011 (binary) = 0xAC3 10111 (binary) = 0001 0111 (binary)
= 0x17
0x3F9 = 0011 1111 1001 (binary)
23
Representing Instructions in Machine Language (R-type)
• Instructions, like registers and words of data, are also 32 bits long – Example: add $t0, $s1, $s2
– registershavenumbers,$t0=8,$s1=17,$s2=18
• Instruction Format:
00000010001 10010 01000 00000 100000
op rs rt rd shamt funct
• #of bits
6 5 5 5 5 6 =32total
Other arithmetic instructions have the same format.
24
Representing Instructions in Machine Language (R-type)
• Instruction Format:
00000010001 10010 01000 00000 100000
register)
op rs rt rd shamt funct
• op: opcode (operation instruction)
• rs: The first register source operand (source
• rt: The second register source operand (target register)
• rd: The register destination operation, gets the result
• shamt: shift amount
• funct: function code. It selects the specific variants
of the operation in the op field.
This format is called R-type (or R-format).
25
MIPS instruction encoding
26
Representing Instructions in Machine Language (I-type)
• Consider the load-word and store-word instructions,
– Whatwouldtheregularityprinciplehaveusdo?
– New principle: Good design demands a compromise
• Introduce a new type of instruction format – I-typefordatatransferinstructions
– otherformatwasR-typeforregister
• Example: lw $t0, 32($s2)
35 18 8 32
op rs rt constant or address
27
Representing Instructions in Machine Language (I-type)
• I-type
Example: lw $t0, 32($s2)
35 18 8 32
op rs rt constant or address # of bits
6 5 5 16
= 32 total
Example: sw $t0, 32($s2)
43 18 8 32
28
Figures
29
Decoding Machine Code
• What is the assembly language statement corresponding to this machine instruction?
00af8020hex
Convert it to binary:
0000 0000 1010 1111 1000 0000 0010 0000
Bits 31-29 are 000, bits 28-26 are 000, it is an R-format (Fig 2.25)
op rs rt rd shamt funct
000000 00101 01111 10000 00000 100000
From the figure in the previous page, add $s0, $a1, $t7
30
Stored Program Concept (Von Neumann Architecture)
• Instructions are represented as bits
• Programs are stored in memory — to be read or written just like
data
• Fetch & Execute Cycle
– Instructionsarefetchedandputintoaspecialregister – Bitsintheregister”control”thesubsequentactions
– Fetchthe“next”instructionandcontinue
31
Logical Operations
Shift left logical
sll $t2, $s0, 4 srl $t2, $s0, 4
# $s2 = $s0 << 4
Shift right logical
# $s2 = $s0 >> 4
Bit-by-bit AND
Bit-by-bit AND immediate Bit-by-bit OR
Bit-by-bit OR immediate Bit-by-bit NOT
and andi or ori nor
$t0, $t1, $t2 $t0, $t1, 100 $t0, $t1, $t2 $t0, $t1, 100 $t0, $t1, $t2
nor -> not or
$t0 = ~($t1 | $t2)
A nor 0 = not (A or 0) = not (A)
32
Logical operations
• sll $t2,$s0,4 #$s2=$s0<<4
unused $s0 $t2
00000000000 10000 01010 00100 000000 0 0 16 10 4 0
op rs rt rd shamt funct
• R-type as in arithmetic instructions
33
and
or
nor
and immediate or immediate
and $s1, $s2, $s3 or $s1, $s2, $s3 nor $s1, $s2, $s3 andi $s1, $s2, 100 ori $s1, $s2, 100 sll $s1, $s2, 10
$s1 = $s2 & $s3
Three reg. operands; bit-by-bit AND
shift left logical shift right logical
$s1 = $s2 << 10 $s1 = $s2 >> 10
Shift left by constant
srl $s1, $s2, 10
Shift right by constant
$s1 = $s2 | $s3
Three reg. operands; bit-by-bit OR
$s1 = ~($s2 | $s3)
Three reg. operands; bit-by-bit NOR
$s1 = $s2 & 100
Bit-by-bit AND reg with constant
$s1 = $s2 | 100
Bit-by-bit OR reg with constant
34
and
or
nor
and immediate or immediate shift left logical shift right logical
0 0 0 12 13 0 0
36 R 37 R 39 R — I — I 0 R 2 R
Op code
Funct code type
35
Figure
36
Multiplication / Division Multiplication
mult $t0, $t1
# multiply $t0 and $t1, and
# store the lower 32 bits of result in LO (special memory)
# and the upper 32 bits of result in HI (special memory spot) # $t2 gets lower 32 bits of the multiplication result
# $t3 gets higher 32 bits of the multiplication result
mflo $t2 mfhi $t3
mult, mflo (move from LO), and mfhi (move from HI) are of R-type.
If you multiply two 32-bits numbers, the result can become a 64-bits number, which does not fit in one register.
37
Division
Division div $t0, $t1
# divide $t0 by $t1, and
# store the quotient in LO (special memory spot) # and the remainder in HI (special memory spot) # $t2 gets $t0 / $t1
# $t3 gets $t0 % $t1 (remainder of the division)
mflo $t2 mfhi $t3
div, mflo (move from LO), and mfhi (move from HI) are of R-type.
38
Control / Decision making – bne, beq (I-type)
• Decision making instructions
– alterthecontrolflow,
– i.e.,changethe”next”instructiontobeexecuted
• MIPS conditional branch instructions:
bne $t0, $t1, Label # if ($t0 ≠ $t1) goto Label
• Example: C:
MIPS:
attention: opposite of each other
beq $t0, $t1, Label # if ($t0 = $t1) goto Label
if (i==j) h = i + j;
bne $s0, $s1, Label #$s0,$s1,& $s3 are i,j,& h
add $s3, $s0, $s1 Label: ….
39
Control – j
• MIPS unconditional branch instructions (J-type) :
• Example:
j label
if (i!=j)
beq $s4, $s5, Lab1
add $s3, $s4, $s5
j Lab2
Lab1: sub $s3, $s4, $s5 Lab2: …
h=i+j;
else h=i-j;
40
Loops C:
…
while ( save[i] == k ) i = i+1;
(Assume that i, k, and save are $s3, $s5, and $s6 respectively) MIPS:
Loop: sll $t1, $s3, 2 add $t1, $t1, $s6
# $t1 = i*4
# $t1 = address of save[i]
# $t0 = save[i] (value of save[i])
Exit:
lw $t0, 0($t1) bne $t0, $s5, Exit
# goto Exit if save[i] ≠ k #i=i+1
# go back to Loop
addi $s3,$s3,1 j Loop
41
So far:
• Instruction
Meaning
I J
op op
rs
rt 16 bit address 26 bit address
add $s1,$s2,$s3 sub $s1,$s2,$s3 lw $s1,100($s2) sw $s1,100($s2) bne $s4,$s5,L beq $s4,$s5,L j Label
$s1 = $s2 + $s3
$s1 = $s2 – $s3
$s1 = Memory[$s2+100] Memory[$s2+100] = $s1
Next instr. is at Label if $s4 ≠ $s5 Next instr. is at Label if $s4 = $s5 Next instr. is at Label (J-type)
• Formats:
R op rs rt rd shamt funct
6 bits
42
Control Flow – slt (set on less than) • What about Branch-if-less-than?
• New instruction slt (set on less than): slt $t0, $s1, $s2
if $s1 < $s2 then
$t0 = 1
slti $t0, $s2, 10
#constant operand
else
$t0 = 0
43
Pseudo-Instructions
• Common variations of assembly language instructions.
• Not implemented in the hardware.
• Therefore, we can use them in our assembly programs for our convenience, but they cannot be translated into machine languages directly.
Ex:
move $t0, $t1 #$t0 gets $t1, or $t0=$t1
assembler converts to: add $t0, $zero, $t1
More examples:
blt (branch on less than) bgt
bge
ble
Assembler converts using slt, bne, beq
More examples: li, la
44
Name
Register number
Usage
$zero
$v0-$v1
$a0-$a3
$t0-$t7
$s0-$s7
$t8-$t9
$gp 28 $sp 29 $fp 30 $ra 31
Policy of Use Conventions
0 2-3 4-7 8-15 16-23 24-25
the constant value 0
values for results and expression evaluation arguments
temporaries (caller saves/callee can clobber) saved (callee saves/caler can clobber)
more temporaries
global pointer
stack pointer
frame pointer
return address
Register 1 ($at) reserved for assembler, 26-27 ($k0,$k1) for operating system
45
Procedure execution
So far, we have used following registers:
– $s0,$s1,...(forsavedvariablevalues) – $t0, $t1, ... (for temporary)
Now we will be using the following for procedure executions:
• $a0 - $a3: registers for arguments (passed from caller to callee)
• $v0 - $v1: registers for return values (passed from callee to caller)
• $ra: register for storing return address
PC – the program counter
– contains the address of the current instruction.
For procedure call: jal ProcLabel
# change $ra = PC + 4; goto ProcLabel # jal – jump and link
For procedure return: jr $ra
# goto $ra (jr – jump register)
46
Procedure execution
1. Placeparametersinaplacewheretheprocedurecanaccessthem. -caller puts the parameters in $a0 - $a3
2. Transfercontroltotheprocedure. -caller uses “jal ProcLabel”
3. Acquire the storage resources needed for the procedure - done callee
4. Perform the desired task. -done by callee
5. Place the result value in a place where the calling program can access it.
-callee places the result in $v0 - $v1
6. Return control to the point of origin, since a procedure can be called from several points in a program.
-callee uses “jr $ra”
47
Spilling Registers
• What if a program has more variables than registers?
• The compiler tries to keep the most frequently used variables in registers and place the rest in memory, using loads and stores to move variables between registers and memory.
• The process of putting less commonly used variables into memory is called “spilling registers”.
48
Spill registers using stack
• Stack has “Last In First Out” (LIFO) structure,
– i.e., Last one that went in comes out first.
– An example of stack structure is a Pez candy dispenser
Where in the memory do we store these data, using the stack? We also need to remember where we put them.
--- we use the higher address end of the memory,
and use the stack pointer $sp to keep track the last used space in the stack.
49
Stack operations:
“push” is to insert, “pop” is to remove
Push T
Push I
Push N
T Pop N
T Pop I
T
Pop T
I T
T
50
N II
MIPS Memory Layout
high address
$sp stack pointer
Stack
Space for saved procedure information (here, the stack is up side down.)
address 0
Heap
Explicitly created space, (e.g., malloc() in C) Variables declared once per program
Static
Code reserved
Programs
51
Using more registers
• Spill registers using stack (LIFO)
• Stack pointer, push, pop
• $sp – stack pointer
Register $sp always points to the last used space in the stack.
To use stack, we decrement this pointer by the amount of space
we need and then fill it with info.
52
Example: Procedure that does not call another one
C:
MIPS: leaf_example:
//$a0, $a1, $a2, $s3 int leaf_example(int g, int h, int i, int j)
# need to store data from calling proc. addi $sp, $sp, -12
sw $t1, 8($sp)
sw $t0, 4($sp)
{
int f; //$s0
}
f = (g+h) – (i+j); return f;
sw $s0, 0($sp)
#now we are free to use $s0,$t0,$t1 add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
-----------------------------------------
Here, we want to use registers $s0, $t0, $t1,
# set the return value in $v0 add $v0, $s0, $zero
but if these were used in the calling procedure
such as main, then their data should be stored in the memory before this procedure starts using $s0, $t0, $t1.
lw $s0, 0($sp) lw $t0, 4($sp) lw $t1, 8($sp) addi $sp, $sp, 12
At the end of the procedure, we copy those saved data back to these registers so that the calling procedure can use them again.
jr $ra 53
Using more registers
addi $sp, $sp, -12 sw $t1, 8($sp) sw $t0, 4($sp) sw $s0, 0($sp)
lw $s0, 0($sp) lw $t0, 4($sp) lw $t1, 8($sp) addi $sp, $sp, 12
The value of the stack pointer and the stack (a) before, (b) during, and (c) after the procedure call.)
54
Procedures that call others
• Recursion? A recursive procedure is a procedure that calls itself.
int factorial(int n) {
}
if (n < 1) return 1;
else
return n*factorial(n-1);
-Recursive procedure (it calls itself)
factorial(0) = 1
factorial(1) = 1 * factorial(0) = 1 * 1 = 1
factorial(2) = 2 * factorial(1) = 2 * (1 * 1) = 2 factorial(3) = 3 * factorial(2) = 3 * (2 * 1 * 1) = 6 factorial(4) = 4 * factorial(3) = 4 * (3 * 2 * 1 * 1)= 24
55
MIPS: factorial:
Label1: fac_bk:
addi $a0, $a0, -1 jal factorial
#n >= 1, so decrement n
addi $sp, $sp, -8 sw $ra, 4($sp) sw $a0, 0($sp)
#adjust stack pointer #save return address #save argument n
slti $t0, $a0, 1
beq $t0, $zero, Label1
#test for n < 1
#if n >=1, goto Label1
addi $v0, $zero, 1 addi $sp, $sp, 8
#else return 1 in $v0
jr $ra
#return to caller
lw $a0, 0($sp) lw $ra, 4($sp) addi $sp, $sp, 8 mul $v0, $a0, $v0 jr $ra
#restore argument n
#adjust stack pointer
#call factorial with (n-1) #this is where factorial returns
#restore return address
#adjust stack pointer #$v0 = n * factorial(n-1) #return to caller
56
Factorial is called with $a0 = 2
7fff fffc
0
old top of stack Caller rt addr $a0 = 2 Fac_bk $a0 = 1 Fac_bk $a0 = 0
….
57
Example
C:
MIPS:
int main() {
… sum(a, b);
}
int sum(int x, int y) {
main:
add $a0, $s0, $zero add $a1, $s1, $zero jal sum
return x+y;
}
sum:
add $v0, $a1, $a2 jr $ra
58
Nested Functions
int main(int x) {…….
//*Executions starts from main function
sumSquare(x, y); ….
//*main calls sumSquare
// *$ra contains the address of the instruction // after sumSquare
}
int sumSquare(int x, int y) { ……
return mult(x,x) + y; …
//*sumSquare calls mult
// *cannot overwrite $ra, Need to save $ra
}
int mult(int x, int x)
//*Also registers that main was using across //sumSquare function
{ …..
return x*x;
//*need to be saved
}
//*Assume $ra is uninitialized
59
Nested Functions
• When a C program is run, there are 3 memory areas allocated:
– StaticVariablesdeclaredonceperprogram,ceasetoexistonly after execution completes, e.g., C global
– Heap:Variablesdeclareddynamically
– Stack: Space to be used by procedure during execution; this is where we can save register values
60
Requirements for Functions
• Pass arguments to the function – $a0,$a1,$a2,$a3
• Get results from the function – $v0,$v1
• Can call from anywhere – jal
• Can always return back – jr
• Nested and Recursive Functions (using the stack and $sp) – Save$raonstack
• Saving and Restoring Registers (using the stack and $sp)
61
Name
Register number
Usage
$zero
$v0-$v1
$a0-$a3
$t0-$t7
$s0-$s7
$t8-$t9
$gp 28 $sp 29 $fp 30 $ra 31
Policy of Use Conventions
0 2-3 4-7 8-15 16-23 24-25
the constant value 0
values for results and expression evaluation arguments
temporaries (caller saves/callee can clobber) saved (callee saves/caler can clobber)
more temporaries
global pointer
stack pointer
frame pointer
return address
Register 1 ($at) reserved for assembler, 26-27 ($k0,$k1) for operating system
62
Register Conventions – Saved Registers • $zero – No Change, always 0
• $s0 – $s7: Restore if you change. If the callee changes them, it must restore the original values before returning.
• $sp: Restore if you change. The stack pointer much point to the same place before and after the jal call, or else the caller won’t be able to restore values from the stack.
63
Register Conventions – Volatile Registers
• $ra: Can change. The jal call itself will change this register. Call needs to save on stack if nested call.
• $v0 – $v1: Can change. They will contain the new return values.
• $a0 – $a3: Can change. These are volatile argument registers. Caller
needs to save if they will need them after the call.
• $t0 – $t9: Can change. Temporary: any procedure may change them at any time. Caller needs to save if they will need them afterwards.
64
Procedure frame
• The segment of the stack containing a procedure’s save registers
and local variables.
• FP – Frame pointer – to point to the first word of the frame of a procedure. A stack pointer might change during the procedure, and so references to a local variable in memory might have different offsets depending on where they are in the procedure, making the procedure harder to understand.
65
MIPS memory allocation
• Heap: memory segment used for dynamic memory allocation
66
Procedure SWAP
C:
MIPS: swap:
void swap(int v[], int k) {
sll $t1, $a1, 2 #$t1=k*4 add $t1, $a0, $t1 #t1=v[k]
}
int temp;
temp = v[k]; v[k] = v[k+1]; v[k+1] = temp;
lw $t0, 0($t1) #load v[k] address lw $t2, 4($t1) #load v[k+1]
sw $t2, 0($t1)
sw $t0, 4($t1)
jr $ra
67
Additional Load/Save instructions
• lb $s1, 100($s2) #read byte from source such as a character
• sb $s1, 100($s2) #write byte (right most 8 bits) to destination
• lh $s1, 100($s2) #read half word (16 bits) from source
• sh $s1, 100($s2) #write half word (right most 16 bits) to destination
68
Constants
• Small constants are used quite frequently (50% of operands) e.g., A = A + 5;
• MIPS Instructions:
B = B + 1; C = C – 18;
• Solutions? Why not?
– put’typicalconstants’inmemoryandloadthem.
– create hard-wired registers (like $zero) for constants like one.
addi $29, $29, 4
slti $8, $18, 10
andi $29, $29, 6
ori $29, $29, 4
• Constants fit into the 16-bit field.
69
How about larger constants?
• We’d like to be able to load a 32 bit constant into a register
• lui – load upper immediate – set the upper 16 bits of a constant in a register)
lui $t0, 1010101010101010
filled with zeros
1010101010101010 0000000000000000
• Then must get the lower order bits right, i.e., (ori – or immediate) ori $t0, $t0, 1010101010101010
ori
1010101010101010 0000000000000000 0000000000000000 1010101010101010
1010101010101010 1010101010101010
70
Addresses in Branches and Jumps
• Instructions:
bne $t4,$t5,Label
Next instruction is at Label if $t4 ≠ $t5 Next instruction is at Label if $t4 = $t5 Next instruction is at Label
• Formats:
I J
op op
rs
rt 16 bit address 26 bit address
beq $t4,$t5,Label
j Label
• Addresses are not 32 bits
71
Addressing in Branches and Jumps • j 1000
2 1000
6 bits 26 bits
• MIPS uses J format for j, jal, instructions.
• bne $s0, $s1, EXIT
5 16 17 EXIT
6 bits 5bits 5 bits 16 bits
• MIPS uses PC-relative addressing for conditional branches
72
Addresses in Branches • Instructions:
bne $t4,$t5,Label
beq $t4,$t5,Label
Next instruction is at Label if $t4≠$t5 Next instruction is at Label if $t4=$t5
• Formats: I
op rs
rt 16 bit address
• Could specify a register (like lw and sw) and add it to address – useInstructionAddressRegister(PC=programcounter) – mostbranchesarelocal(principleoflocality)
• Jump instructions just use high order bits of PC – addressboundariesof256MB
73
Addressing in Branches: PC-relative addressing
•
Next instruction address (new PC)
•
bne $s0, $s1, EXIT
5 16 17 EXIT
= Program Counter + “Branch distance” = (PC+4) + Branch distance
6 bits 5bits 5 bits 16 bits
Branch distance = content of 16 bits field x 4
Ex: bne $s0, $s1, EXIT
is converted to:
80012 5 16 17 2
Then the next instruction address (new PC) = (80012)+4+(2*4bytes) = 80024
74
Addressing in Jumps : Pseudo-direct addressing • Next instruction address (new PC)
= concatenation of the upper 4 bits of the PC+4 and (26 bits * 4 bytes) • jLoop
Ex: j Loop
is converted to: 80020 2
2
6 bits
Loop 26 bits
20000
20000 (words) * 4 bytes = 80000 bytes
Then the next instruction address (new PC) = Concatenation the upper 4 bits of the PC+4 and 80000
75
Example:
In MIPS:
Loop: sll $t1, $t3, 2
80000 80004 80008 80012 80016 80020 80024
0 0 19 9 2 0
add $t1, $t1, $s6 lw $t0, 0($t1) bne $t0, $s5, Exit addi $s3, $s3, 1
j Loop Exit:
In Machine Language:
0 9 22 9 0 32
35 9 8 0
5821 2 81919 1 2 20000
…
76
MIPS Addressing Mode
1. Register addressing: where the operand is a register e.g., add, sub
2. Base or displacement addressing, where the operand is at the memory location whose address is the sum of a register and a constant in the instruction.
e.g., lw, sw
3. Immediate addressing, where the operand is a constant within the
instruction itself. e.g., addi
4. PC-relativeaddressing,wheretheaddressisthesumofthePCand a constant in the instruction.
e.g., bne, beq
5. Pseudo-direct addressing, where the jump address is the 26 bits of
the instruction concatenated with the upper bits of the PC.
e.g., j
77
1. Immediate addressing
op rs rt Immediate
2. Register addressing
op rs rt rd … funct
Registers Register
3. Base addressing op rs rt
Address
Memory
Halfword Word
4. PC-relative addressing op rs rt
Address
Memory Word
5. Pseudodirect addressing
op Address
Memory Word
Register
+
Byte
PC
+
PC
78
Assembly Language vs. Machine Language
• Assembly provides convenient symbolic representation – mucheasierthanwritingdownnumbers
– e.g.,destinationfirst
• Machine language is the underlying reality – e.g.,destinationisnolongerfirst
• Assembly can provide ‘pseudo-instructions’
– e.g.,“move$t0,$t1”existsonlyinAssembly
– wouldbeimplementedusing“add$t0,$t1,$zero”
• When considering performance you should count real instructions
79
Overview of MIPS
• simple instructions all 32 bits wide
• only three instruction formats
R op rs rt rd shamt funct
I J
op rs op
rt 16 bit address 26 bit address
80
To summarize:
Name
Example
Comments
32 registers
$s0-$s7, $t0-$t9, $zero, $a0-$a3, $v0-$v1, $gp, $fp, $sp, $ra, $at
Fast locations for data. In MIPS, data must be in registers to perform arithmetic. MIPS register $zero always equals 0. Register $at is
reserved for the assembler to handle large constants.
Accessed only by data transfer instructions. MIPS uses byte addresses, so sequential words differ by 4. Memory holds data structures, such as arrays, and spilled registers, such as those saved on procedure calls.
230 memory words
Memory[0], Memory[4], …, Memory[4294967292]
Category Arithmetic
Instruction
Example
Meaning
Comments
Three operands; data in registers
Data transfer
Memory[$s2 + 100] = $s1 $s1 = Memory[$s2 + 100] Memory[$s2 + 100] = $s1
Conditional branch
if ($s1 != $s2) go to PC + 4 + 100
Uncondi- tional jump
jump
jump register jump and link
j 2500 jr $ra jal 2500
go to 10000
go to $ra
$ra = PC + 4; go to 10000
For switch, procedure return For procedure call
81
add subtract
add $s1, $s2, $s3 sub $s1, $s2, $s3
$s1 = $s2 + $s3
add immediate load word store word load byte
addi $s1, $s2, 100 lw $s1, 100($s2) sw $s1, 100($s2) lb $s1, 100($s2) sb $s1, 100($s2) lui $s1, 100
$s1=$s2+100
$s1 = Memory[$s2 + 100]
Used to add constants
Word from memory to register Word from register to memory Byte from memory to register Byte from register to memory Loads constant in upper 16 bits
store byte
load upper immediate
$s1=100*216
branch on equal beq branch on not equal bne set on less than slt
$s1, $s2, 25 $s1, $s2, 25 $s1, $s2, $s3
if ($s1 == $s2) go to PC + 4 + 100
Equal test; PC-relative branch Not equal test; PC-relative Compare less than; for beq, bne Compare less than constant Jump to target address
set less than immediate
slti $s1, $s2, 100
if ($s2 < 100) $s1 = 1; else $s1 = 0
MIPS operands
MIPS assembly language
$s1=$s2-$s3
Three operands; data in registers
if ($s2 < $s3) $s1 = 1; else $s1 = 0
MIPS Simulation
• SOUN us a simulator
– ReadaMIPSassemblylanguageprogram – Simulateeachinstruction
– Displayvaluesofregistersandmemory
– Supportbreakpointsandsinglestepping
– ProvidesimpleI/Oforinteractionwithuser
82
Simple Example
#data declarations
.data
message1: .asciiz "Hello world.\n" #create a string "Hello \n"
#program code is contained below under .text .text
.globl main #define a global function main
# the program begins execution at main()
main:
la
li syscall jr
$a0, message1 # $a0 = address of message1
$v0, 4 $ra
# $v0 = 4 --- this is to call print_string() # call print_string()
# return
83
Data Definitions
• You can define variables/constants with: – .word: #define 32 bit quantities
– .byte: #define 8 bit quantities
– .asciiz:#zero-delimitedasciistrings – .space:#allocatesomebytes
Note: the name you create will be the address of each data
84
Data Examples
prompt: num1: array1: array2:
.data
.asciiz “Hello World\n” .word 25
.word 2, 3, 4, 5
.space 80
85
I/O Functions
• Syscall (system call) is used to communicate with the system and do simple I/O.
• Load the system call code into the register $v0.
• Load arguments (if any) into the register $a0, $a1, and $f12 (for floating
point).
• Do “syscall”
• Result values will be in the registers $v0 or $v1.
System Call Number
System Call Operation
System Call Description
1 4 5
print_int print_string read_int
$v0 = 1, $a0 = int to be printed
$v0 = 4, $a0 = address of beginning of ASCIIZ string $v0 = 5; user types int at keyboard;
8
read_string
$v0 = 8; user types string at keybd;
10
exit
len in $a1
$v0 = 10; terminates the program
11 12
print_char read_char
$v0 = 11; $a0 = char to be printed
$v0 = 12; user types char at keyboard;
value is store in $v0
addr of beginning of string is store in $a0;
value is store in $v0
86
Reading an int, printing an int
#reading an int
li $v0, 5 #$v0 gets 5, indicating to read an int syscall
#upon return from the syscall, $v0 will have the integer typed #by a user in the SPIM console
#printing an int
move $a0, $v0 #$a0 needs to have a value to be printed, here $v0 value
#that we just read
li $v0, 1 #$v0 gets 5, indicating to perform print –int operation syscall
87