Slide 1
Instructions:
Language of the Computer
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Assembly provides convenient symbolic representation
much easier than writing down numbers
regular rules: e.g., destination first
Machine language is the underlying reality
e.g., destination is no longer first
Assembly can provide pseudo-instructions
e.g., move $t0, $t1 exists only in assembly
would be implemented using add $t0, $t1, $zero
When considering performance you should count actual number of machine instructions that will execute
Assembly Language vs. Machine Language
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Instruction Set
The repertoire of instructions of a computer
Different computers have different instruction sets
But with many aspects in common
Early computers had very simple instruction sets
Simplified implementation
Many modern computers also have simple instruction sets
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
The MIPS Instruction Set
Stanford MIPS commercialized by MIPS Technologies (www.mips.com)
Large share of embedded core market
Applications in consumer electronics, network/storage equipment, cameras, printers, …
Typical of many modern ISAs
See MIPS Reference Data tear-out card, and Appendixes B and E
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Compute first twelve Fibonacci numbers and put in array, then print
.data
fibs: .word 0 : 12 # “array” of 12 words to contain fib values
size: .word 12 # size of “array”
.text
la $t0, fibs # load address of array (Fib. source ptr)
la $t5, size # load address of size variable
lw $t5, 0($t5) # $t5 = 12
li $t2, 1 # 1 is first and second Fib. number
add.d $f0, $f2, $f4 # add.d – double precision add
sw $t2, 0($t0) # F[0] = 1
sw $t2, 4($t0) # F[1] = F[0] = 1
addi $t1, $t5, -2 # Counter for loop, will execute (size-2) times
loop: lw $t3, 0($t0) # Get value from array F[n]
lw $t4, 4($t0) # Get value from array F[n+1]
add $t2, $t3, $t4 # $t2 = F[n] + F[n+1]
sw $t2, 8($t0) # Store F[n+2] = F[n] + F[n+1] in array
addi $t0, $t0, 4 # increment address of Fib. number source (ptr)
addi $t1, $t1, -1 # decrement loop counter
bgtz $t1, loop # repeat if not finished yet.
la $a0, fibs # first argument for print (array)
add $a1, $zero, $t5 # second argument for print (size)
jal print # call print routine.
li $v0, 10 # system call for exit
syscall # we are out of here.
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Representing Instructions
Instructions are encoded in binary
Called machine code
MIPS instructions
Encoded as 32-bit instruction words
Small number of formats encoding operation code (opcode), register numbers, …
Regularity!
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Convention for Registers
Register 1, called $at, is reserved for the assembler; registers 26-27,
called $k0 and $k1 are reserved for the operating system.
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
So far
Instruction Format Meaning
add $s1,$s2,$s3 R $s1 = $s2 + $s3
sub $s1,$s2,$s3 R $s1 = $s2 – $s3
lw $s1,100($s2) I $s1 = Memory[$s2+100]
sw $s1,100($s2) I Memory[$s2+100] = $s1
bne $s4,$s5,Lab1 I Next instr. is at Lab1 if $s4 != $s5
beq $s4,$s5,Lab2 I Next instr. is at Lab2 if $s4 = $s5
j Lab3 J Next instr. is at Lab3
Formats:
R
I
J
op rs rt rd shamt funct
op rs rt 16 bit address
op 26 bit address
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Arithmetic Operations
Add and subtract, three operands
Two sources and one destination
add a, b, c # a gets b + c
All arithmetic operations have this form
Design Principle 1: Simplicity favors regularity
Regularity makes implementation simpler
Simplicity enables higher performance at lower cost
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
MIPS Arithmetic
All MIPS arithmetic instructions have 3 operands
Operand order is fixed (e.g., destination first)
Example:
C code: A = B + C
MIPS code: add $s0, $s1, $s2
compiler’s job to associate
variables with registers
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Small constants are used quite frequently (50% of operands)
e.g., A = A + 5;
B = B + 1;
C = C – 18;
Solutions? Will these work?
create hard-wired registers (like $zero) for constants
put program constants in memory and load them as required
MIPS Instructions:
addi $29, $29, 4
slti $8, $18, 10
andi $29, $29, 6
ori $29, $29, 4
How to make this work?
Constants
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
The Constant Zero
MIPS register 0 ($zero) is the constant 0
Cannot be overwritten
Useful for common operation, e.g., move between registers
add $t2, $s1, $zero
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
MIPS R-format Instructions
Instruction fields:
op: operation code (opcode)
rs: first source register number
rt: second source register number
rd: destination register number
shamt: shift amount (00000 for now)
funct: function code (extends opcode)
op
rs
rt
rd
shamt
funct
6 bits
6 bits
5 bits
5 bits
5 bits
5 bits
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
R-format Example
add $t0, $s1, $s2
special
$s1
$s2
$t0
0
add
0
17
18
8
0
32
000000
10001
10010
01000
00000
100000
000000100011001001000000001000002 = 0232402016
op
rs
rt
rd
shamt
funct
6 bits
6 bits
5 bits
5 bits
5 bits
5 bits
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
MIPS Arithmetic
Design Principle 1: simplicity favors regularity.
Translation: Regular instructions make for simple hardware!
Simpler hardware reduces design time and manufacturing cost.
Of course this complicates some things…
C code: A = B + C + D;
E = F – A;
MIPS code add $t0, $s1, $s2
(arithmetic): add $s0, $t0, $s3
sub $s4, $s5, $s0
Performance penalty: high-level code translates to denser machine code.
Allowing variable number
of operands would
simplify the assembly
code but complicate the
hardware.
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
MIPS Arithmetic
Operands must be in registers – only 32 registers provided (which require 5 bits to select one register). Reason for small number of registers:
Design Principle 2: smaller is faster. Why?
Electronic signals have to travel further on a physically larger chip increasing clock cycle time.
Smaller is also cheaper!
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Simple MIPS instructions:
MIPS
loading words but addressing bytes
arithmetic on registers only
Instruction Meaning
add $s1, $s2, $s3 $s1 = $s2 + $s3
sub $s1, $s2, $s3 $s1 = $s2 – $s3
lw $s1, 100($s2) $s1 Memory[$s2+100]
sw $s1, 100($s2) Memory[$s2+100] $s1
must contain an address
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Consider the load-word and store-word instructions,
what would the regularity principle have us do?
we would have only 5 or 6 bits to determine the offset from a base register – too little…
Design Principle 3: Good design demands a compromise
Introduce a new type of instruction format
I-type (“I” for Immediate) for data transfer instructions
Example: lw $t0, 1002($s2) # $t0 $8, $2 $18
100011 10010 01000 0000001111101010
op rs rt 16 bit offset
Machine Language
18 8 1002
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
MIPS I-format Instructions
Immediate arithmetic and load/store instructions
rt: destination or source register number
Constant: –215 to +215 – 1
Address: offset added to base address in rs
Design Principle 4: Good design demands good compromises
Different formats complicate decoding, but allow 32-bit instructions uniformly
Keep formats as similar as possible
op
rs
rt
constant or address
6 bits
5 bits
5 bits
16 bits
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Instructions, like registers and words of data, are also 32 bits long
Example: add $t0, $s1, $s2 #MARS
registers are numbered, e.g., $t0 is 8, $s1 is 17, $s2 is 18
or in MIPS: add $8, $17, $18
Instruction Format R-type (“R” for aRithmetic):
17 18 8
Machine Language
10001
10010
01000
00000
100000
000000
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
op rs rt rd shamt funct
opcode –
operation
first
register
source
operand
second
register
source
operand
register
destin-
ation
operand
shift
amount
function field –
selects variant
of operation
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Immediate Operands
Constant data specified in an instruction
addi $s3, $s3, 4
No subtract immediate instruction
Just use a negative constant
addi $s2, $s1, -1
Design Principle 3: Make the common case fast
Small constants are common
Immediate operand avoids a load instruction
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
AND Operations
Useful to mask bits in a word
Select some bits, clear others to 0
and $t0, $t1, $t2
0000 0000 0000 0000 0000 1101 1100 0000
0000 0000 0000 0000 0011 1100 0000 0000
$t2
$t1
0000 0000 0000 0000 0000 1100 0000 0000
$t0
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
OR Operations
Useful to include bits in a word
Set some bits to 1, leave others unchanged
or $t0, $t1, $t2
0000 0000 0000 0000 0000 1101 1100 0000
0000 0000 0000 0000 0011 1100 0000 0000
$t2
$t1
0000 0000 0000 0000 0011 1101 1100 0000
$t0
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
XOR Operations
Useful to check to see if two words have the same bits
Set some bits to 1, leave others unchanged
xor $t0, $t1, $t2
0000 0000 0000 0000 0000 1101 0000 0000
0000 0000 0000 0000 0000 1101 0000 0000
$t2
$t1
0000 0000 0000 0000 0000 0000 0000 0000
$t0
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
NOT Operations
Useful to invert bits in a word
Change 0 to 1, and 1 to 0
MIPS has NOR 3-operand instruction
a NOR b == NOT ( a OR b )
nor $t0, $t1, $zero
0000 0000 0000 0000 0011 1100 0000 0000
$t1
1111 1111 1111 1111 1100 0011 1111 1111
$t0
Register 0: always read as zero
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Registers vs. Memory
Arithmetic instructions operands must be in registers
MIPS has 32 registers
Compiler associates variables with registers
What about programs with lots of variables (arrays, etc.)? Use memory, load/store operations to transfer data from memory to register – if not enough registers spill registers to memory
MIPS is a load/store architecture
Processor
I/O
Control
Datapath
Memory
Input
Output
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Memory Organization
Viewed as a large single-dimension array with access by address
A memory address is an index into the memory array
Byte addressing means that the index points to a byte of memory, and that the unit of memory accessed by a load/store is a byte
0
1
2
3
4
5
6
…
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
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Memory Organization
Bytes are load/store units, but most data items use larger words
For MIPS, a word is 32 bits or 4 bytes.
232 bytes with byte addresses from 0 to 232-1
230 words with byte addresses 0, 4, 8, … 232-4
i.e., words are aligned
what are the least 2 significant bits of a word address?
0
4
8
12
…
32 bits of data
32 bits of data
32 bits of data
32 bits of data
Registers correspondingly hold 32 bits of data
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Load/Store Instructions
Load and store instructions
Example:
C code: A[8] = h + A[8];
MIPS code (load): lw $t0, 32($s3)
(arithmetic): add $t0, $s2, $t0
(store): sw $t0, 32($s3)
Load word has destination first, store has destination last
Remember MIPS arithmetic operands are registers, not memory locations
therefore, words must first be moved from memory to registers using loads before they can be operated on; then result can be stored back to memory
offset
address
value
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
A MIPS Example
Can we figure out the assembly code?
swap(int v[], int k);
{ int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
swap:
muli $2, $5, 4 # index k*4 words
sll $2, $5, 2
add $2, $4, $2 # address of v[k]
lw $15, 0($2) # $15 = v[k]
lw $16, 4($2) # $16 = v[k+1]
sw $16, 0($2) # $16 v[k]
sw $15, 4($2) # $15 v[k+1]
jr $31
#$4-$7 hold first 5 function arguments, i.e.,
$4 = v[ ] (address)
$5 = k
v[k]
$4
$2
0($2)
0($4)
v[k+1]
v[0]
:
:
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Conditional Operations
Branch to a labeled instruction if a condition is true
Otherwise, continue sequentially
beq rs, rt, L1
if (rs == rt) branch to instruction labeled L1;
bne rs, rt, L1
if (rs != rt) branch to instruction labeled L1;
j L1
unconditional jump to instruction labeled L1
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Decision making instructions
alter the control flow,
i.e., change the next instruction to be executed
MIPS conditional branch instructions:
bne $t0, $t1, Label
beq $t0, $t1, Label
Example: if (i==j) h = i + j;
bne $s0, $s1, Label
add $s3, $s0, $s1
Label: ….
Control: Conditional Branch
I-type instructions
000100 01000 01001 0000000000011001
beq $t0, $t1, Label
(= addr.100) + PC
word-relative addressing:
25 words = 100 bytes
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Further extend reach of branch by observing all MIPS instructions are a word (= 4 bytes), therefore word-relative addressing:
MIPS branch destination address = (PC + 4) + (4 * offset)
so offset = (branch destination address – PC – 4)/4 number of words offset
MIPS does: offset = (branch destination address – PC)/4
Addresses in Branch
Because hardware typically increments PC early
in execute cycle to point to next instruction
MIPS unconditional branch instructions:
j Label
Example:
if (i!=j) beq $s4, $s5, DoThis
h=i+j; add $s3, $s4, $s5
else j DoThat
h=i-j; DoThis: sub $s3, $s4, $s5
DoThat: …
J-type (“J” for Jump) instruction format
Example: j Label # 25 instructions away
Control: Unconditional Branch (Jump)
6 bits 26 bits
op
26 bit number
000010
00000000000000000000011001
word-relative
addressing:
25 words = 100 bytes
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Addresses in Jump
Word-relative addressing also for jump instructions
MIPS jump j instruction replaces lower 28 bits of the PC with A00 where A is the 26 bit address; it never changes upper 4 bits (sll by 2)
Example: if PC = 1011X (where X = 28 bits), it is replaced with 1011A00
there are 16(=24) partitions of the 232 size address space, each partition of size 256 MB (=228), such that, in each partition the upper 4 bits of the address is same.
if a program crosses an address partition, then a j that reaches a different partition has to be replaced by jr with a full 32-bit address first loaded into the jump register
therefore, OS should always try to load a program inside a single partition
op 26 bit address
J
Branching Far Away
If branch target is too far to encode with 16-bit offset, assembler rewrites the code
Example
beq $s0,$s1, L1
↓
bne $s0,$s1, L2
j L1
L2: …
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Compiling if Statements
C code:
if (i==j) f = g+h;
else f = g-h;
f, g, … in $s0, $s1, …
Compiled MIPS code:
bne $s3, $s4, Else
add $s0, $s1, $s2
j Exit
Else: sub $s0, $s1, $s2
Exit: …
Assembler calculates addresses
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Compiling Loop Statements
C code:
while (save[i] == k) i += 1;
i in $s3, k in $s5, address of save[0] in $s6
Compiled MIPS code:
Loop: sll $t1, $s3, 2 # shift left logical 2 bits: # or t1=i*4
add $t1, $t1, $s6 # t1 = addr(save[i]) # = addr(save[0]) + 4i
lw $t0, 0($t1) # t0 =save[i] next element
bne $t0, $s5, Exit # if (save[i] != k) exit
addi $s3, $s3, 1 # i += 1
j Loop
Exit: …
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Target Addressing Example
Assume Loop at location 80000 (i) $s3 sll 2 (t1)
0000 0000 (0)
while (save[i] == k) i += 1; 0001 0100 (4)
0010 1000 (8)
i k save[0] addr 0011 1100 (12)
When bne instruction runs, PC is already updated by 4
When executing bne command: PC = addr(bne) = 80012 + 4 = 80016 = next cmd
Addr(Exit) = two hops from PC = 80016 + (2 * 4 (bytes per word)) = 80024
Loop: sll $t1, $s3, 2 80000 0 0 19 9 4 0
add $t1, $t1, $s6 80004 0 9 22 9 0 32
lw $t0, 0($t1) 80008 35 9 8 0
bne $t0, $s5, Exit 80012 5 8 21 2 (PC+i*4)
addi $s3, $s3, 1 80016 8 19 19 1 PC
j Loop 80020 2 20000 (x 4)
Exit: … 80024
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
More Conditional Operations
Set result to 1 if a condition is true
Otherwise, set to 0
slt rd, rs, rt
if (rs < rt) rd = 1; else rd = 0; slti rt, rs, constant if (rs < constant) rt = 1; else rt = 0; blt, bne: pseudo-instructions that can be executed as: slt $t0, $s1, $s2 # if ($s1 < $s2) Why are they not included in the ISA? The University of Adelaide, School of Computer Science The University of Adelaide, School of Computer Science * Chapter 2 — Instructions: Language of the Computer * Chapter 2 — Instructions: Language of the Computer Branch Instruction Design Why not blt, bge, etc? Hardware for <, ≥, … slower than =, ≠ Combining with branch involves more work per instruction, requiring a slower clock All instructions penalized! beq and bne are the common case This is a good design compromise The University of Adelaide, School of Computer Science The University of Adelaide, School of Computer Science * Chapter 2 — Instructions: Language of the Computer * Chapter 2 — Instructions: Language of the Computer Signed vs. Unsigned for slt Slt: set on less than slt $t0, $s0, $s1 # if $s0 < $s1, then $t0 = 1 Signed comparison: slt, slti Unsigned comparison: sltu, sltui Example $s0 = 1111 1111 1111 1111 1111 1111 1111 1111 $s1 = 0000 0000 0000 0000 0000 0000 0000 0001 slt $t0, $s0, $s1 # signed –1 < +1 $t0 = 1 sltu $t0, $s0, $s1 # unsigned +4,294,967,295 > +1 $t0 = 0
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Logical Operations
Instructions for bitwise manipulation
Useful for extracting and inserting groups of bits in a word
Operation C Java MIPS
Shift left << << sll
Shift right >> >>> srl
Bitwise AND & & and, andi
Bitwise OR
Bitwise XOR
Bitwise NOT |
^
~ |
^
~ or, ori
xor
nor
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Shift Operations
shamt: how many positions to shift
Shift left logical
Shift left and fill with 0 bits
sll by i bits multiplies by 2i
Shift right logical
Shift right and fill with 0 bits
srl by i bits divides by 2i (unsigned only)
op
rs
rt
rd
shamt
funct
6 bits
6 bits
5 bits
5 bits
5 bits
5 bits
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Summary – MIPS Addressing Modes
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Register Usage
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Addressing
Mode
Summary
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
I/O Service Codes
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Input/Output
A number of system services, mainly for input and output, are available for use by your MIPS program.
SYSCALL System Services
Load the service number in register $v0.
Load argument values, if any, in $a0, $a1, $a2, or $f12 as specified.
3. Issue the SYSCALL instruction.
4. Retrieve return values, if any, from result registers as specified.
E.g.,
Print value in $t0 to console
li $v0, 1 # service 1 is print integer
add $a0, $t0, $zero # load desired value into argument register
# $a0, using pseudo-op
syscall
I/O Example
Print double value in $t1 to console
li $v0, 3 # service 3 is print double
add $f12, $t1, $zero # load desired value into argument register
# $a0, using pseudo-op
syscall
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
.data
getInput: .asciiz “Input a value: ”
.text
li $v0,4 # Specifies the print string service
la $a0,getInput # loads the start string
syscall # displays the string
li $v0,5 # specifies the read integer service
syscall # starts the read int service
add $a0,$v0,$0 # $a0 = value read from read service
li $v0,1 # specifies the print integer service
syscall
li $v0,10 # specifies the exit service
syscall # exits the program
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Compute first twelve Fibonacci numbers and put in array, then print
.data
fibs: .word 0 : 12 # “array” of 12 words to contain fib values
size: .word 12 # size of “array”
.text
la $t0, fibs # load address of array (Fib. source ptr)
la $t5, size # load address of size variable
lw $t5, 0($t5) # load array size
li $t2, 1 # 1 is first and second Fib. number
add.d $f0, $f2, $f4 # add.d – double precision add
sw $t2, 0($t0) # F[0] = 1
sw $t2, 4($t0) # F[1] = F[0] = 1
addi $t1, $t5, -2 # Counter for loop, will execute (size-2) times
loop: lw $t3, 0($t0) # Get value from array F[n]
lw $t4, 4($t0) # Get value from array F[n+1]
add $t2, $t3, $t4 # $t2 = F[n] + F[n+1]
sw $t2, 8($t0) # Store F[n+2] = F[n] + F[n+1] in array
addi $t0, $t0, 4 # increment address of Fib. number source (ptr)
addi $t1, $t1, -1 # decrement loop counter
bgtz $t1, loop # repeat if not finished yet.
la $a0, fibs # first argument for print (array)
add $a1, $zero, $t5 # second argument for print (size)
jal print # call print routine.
li $v0, 10 # system call for exit
syscall # we are out of here.
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Procedure Calling
Steps required
Place parameters in registers
Transfer control to procedure
Acquire storage for procedure
Perform procedure’s operations
Place result in register for caller
Return to place of call
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Procedure Call Instructions
Procedure call: jump and link
jal ProcedureLabel
Address of following instruction put in $ra
Jumps to target address
Procedure return: jump register
jr $ra
Copies $ra to program counter
Can also be used for computed jumps
e.g., for case/switch statements
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Example C code:
// procedure adds 10 to input parameter
int main(){
int i, j;
i = 5;
j = add10(i);
i = j;
return 0;
}
int add10(int i){
return (i + 10);
}
$a0 – contains argument of function
$v0 – contains return value of function
.text
main:
addi $s0, $0, 5 # i=5
add $a0, $s0, $0 # arg =5
jal add10
add $s1, $v0, $0 # j=retValue
add $s0, $s1, $0 # i=j
li $v0, 10
syscall
add10:
addi $sp, $sp, -4
sw $s0,0($sp)#i=5 to
memory
addi $s0,$a0,10 #$s0=15
add $v0, $s0, $0 # i=15
lw $s0, 0($sp) addi $sp, $sp, 4
jr $ra
$sp-4
$sp
Content of $s0 i=5
Low address
High address
MEMORY
argument
to function
return result
to caller
Call func
control returns here
after call
save register
in stack, see
figure below
restore
$s0 to 5
system code
& call to
exit
return
0 zero constant 0
1 at reserved for assembler
2 v0 results from function call
3 v1 returned to caller
4 a0 arguments to function
5 a1 from caller: caller saves
6 a2
7 a3
8 t0 temporary: caller saves
. . . (callee can clobber)
15 t7
MIPS: Software Conventions
for Registers
16 s0 callee saves
. . . (caller can clobber)
23 s7
24 t8 temporary (cont’d)
25 t9
26 k0 reserved for OS kernel
27 k1
28 gp pointer to global area
29 sp stack pointer
30 fp frame pointer
ra return address:
caller saves
Memory Layout
Text: program code
Static data: global variables
e.g., static variables in C, constant arrays and strings
$gp initialized to address allowing ±offsets into this segment
Dynamic data: heap
E.g., malloc in C, new in Java
Stack: automatic storage
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Local Data on the Stack
Variables that are local to a procedure but do not fit into registers (e.g., local arrays,
structures, etc.) are also stored in the stack. This area of the stack is the frame. The frame
pointer $fp points to the top of the frame and the stack pointer to the bottom.
$fp does not change during procedure execution, unlike the stack pointer, so it is a stable base
register from which to compute offsets to local variables.
Use of the frame pointer is optional. If there are no local variables to store in the stack it is
not efficient to use a frame pointer.
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Procedures (recursive)
int main(){ int fact(int n){
int i; if (n <= 1) return (1);
i = 7; else return (n*fact(n-1));
j = fact(i); }
return 0;
}
Translated MIPS assembly:
.text
.globl main
main:
addi $a0, $0, 7
jal fact
nop
move $a0, $v0
li $v0, 1
syscall
li $v0, 10
syscall
fact:
addi $sp, $sp, -8
sw $ra, 4($sp)
sw $a0, 0($sp)
slti $t0, $a0, 1
beq $t0, $0, NGE1
nop
addi $v0, $0, 1
addi $sp, $sp, 8
jr $ra
NGE1:
addi $a0, $a0, -1
jal fact
nop
lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
mul $v0, $a0, $v0
jr $ra
stack return
address and
argument
exit
print value
returned by
fact
branch to
GT0 if n>=1
if n < 1
return 1
if n>=1 call
fact(n-1)
restore return
address, argument,
and stack pointer
return
n*fact(n-1)
return control
control
returns
from fact
n = 7
Character Data Set
Byte-encoded character sets
ASCII: 128 characters (7 bits)
95 graphic, 33 control
Latin-1: 256 characters
ASCII, +96 more graphic characters
Unicode: 32-bit character set
Used in Java, C++ wide characters, …
Most of the world’s alphabets, plus symbols
UTF-8, UTF-16: variable-length encodings
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Byte/Halfword Operations
Could use bitwise operations
MIPS byte/halfword load/store
String processing is a common case
lb rt, offset(rs) lh rt, offset(rs)
Sign extend to 32 bits in rt
lbu rt, offset(rs) lhu rt, offset(rs)
Zero extend to 32 bits in rt
sb rt, offset(rs) sh rt, offset(rs)
Store just rightmost byte/halfword
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Branch Addressing
Branch instructions specify
Opcode, two registers, target address
Most branch targets are near branch
Forward or backward
PC-relative addressing
Target address = PC + offset × 4
PC already incremented by 4 by this time
op
rs
rt
constant or address
6 bits
5 bits
5 bits
16 bits
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Synchronization
Two processors sharing an area of memory
P1 writes, then P2 reads
Data race if P1 and P2 don’t synchronize
Result depends of order of accesses
Hardware support required
Atomic read/write memory operation
No other access to the location allowed between the read and write
Could be a single instruction
E.g., atomic swap of register ↔ memory
Or an atomic pair of instructions
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Race Condition
count++ could be implemented as
register1 = count // lw $1,0(count)
register1 = register1 + 1 // addi $1, $1, 1
count = register1 // sw $1, 0(count)
count– could be implemented as
register2 = count
register2 = register2 – 1
count = register2
Consider this execution interleaving with “count = 5” initially:
step 0: process A execute register1 = count {register1 = 5}
step 1: process A execute register1 = register1 + 1 {register1 = 6}
// clock interrupt – context switched (before value is updated to memory)
step 2: process B execute register2 = count {register2 = 5}
step 3: process B execute register2 = register2 – 1 {register2 = 4}
// clock interrupt – context switched
step 4: process A execute count = register1 {count = 6 }
// clock interrupt – context switched
step 5: process B execute count = register2 {count = 4}
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
Atomic Operations in MIPS
Used together to implement lock-free atomic read-modify-write operation:
Load linked: ll rt, offset(rs)
Returns current value at memory indicated in offset(rs)
Store conditional: sc $s1, offset(rs)
Stores value to offset(rs) location if memory location has not been updated since load-link command. Returns 1 in rt
Fails if location is changed
Returns 0 in rt
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Synchronization in MIPS
Example: atomic swap (to test/set lock variable)
# swap $s4 $s1
try: add $t0,$s4,$zero # copy exchange value
ll $t1,0($s1) # load linked
sc $t0,0($s1) # store conditional
beq $t0,$zero,try # branch store fails
add $s4,$t1,$zero # put load value in $s4
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Translation and Startup
Many compilers produce object modules directly
Static linking
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Assembler Pseudoinstructions
Most assembler instructions represent machine instructions one-to-one
Pseudoinstructions: figments of the assembler’s imagination
move $t0, $t1 → add $t0, $zero, $t1
blt $t0, $t1, L → slt $at, $t0, $t1
bne $at, $zero, L
$at (register 1): assembler temporary
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Loading a Program
Load from image file on disk into memory
1. Read header to determine segment sizes
2. Create virtual address space
3. Copy text and initialized data into memory
Or set page table entries so they can be faulted in
4. Set up arguments on stack
5. Initialize registers (including $sp, $fp, $gp)
6. Jump to startup routine
Copies arguments to $a0, … and calls main
When main returns, do exit syscall
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Effect of Language and Algorithm
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Lessons Learnt
Instruction count and CPI are not good performance indicators in isolation
Compiler optimizations are sensitive to the algorithm
Java/JIT compiled code is significantly faster than JVM interpreted
Comparable to optimized C in some cases
Nothing can fix a dumb algorithm!
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Arrays vs. Pointers
Array indexing involves
Multiplying index by element size
Adding to array base address
Pointers correspond directly to memory addresses
Can avoid indexing complexity
The University of Adelaide, School of Computer Science
The University of Adelaide, School of Computer Science
*
Chapter 2 — Instructions: Language of the Computer
*
Chapter 2 — Instructions: Language of the Computer
Example: Clearing and Array
6 instructions in loop vs. 4.
clear1(int array[], int size) {
int i;
for (i = 0; i < size; i += 1)
array[i] = 0;
} clear2(int *array, int size) {
int *p;
for (p = &array[0]; p < &array[size];
p = p + 1)
*p = 0;
}
move $t0,$zero # i = 0
loop1: sll $t1,$t0,2 # $t1 = i * 4
add $t2,$a0,$t1 # $t2=array[i]
sw $zero, 0($t2) # array[i] = 0
addi $t0,$t0,1 # i = i + 1
slt $t3,$t0,$a1 # $t3=(i