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, $t1exists only in assembly
would be implemented usingadd $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: .word12 # 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)
jalprint# 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
InstructionFormat Meaning
add $s1,$s2,$s3R$s1 = $s2 + $s3
sub $s1,$s2,$s3R$s1 = $s2 – $s3
lw $s1,100($s2)I$s1 = Memory[$s2+100]
sw $s1,100($s2)IMemory[$s2+100] = $s1
bne $s4,$s5,Lab1INext instr. is at Lab1 if $s4 != $s5
beq $s4,$s5,Lab2INext instr. is at Lab2 if $s4 = $s5
j Lab3JNext instr. is at Lab3
Formats:
R
I
J
oprsrtrdshamtfunct
oprsrt16 bit address
op26 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 codeadd $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
InstructionMeaning
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 10010010000000001111101010
oprs rt16 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):
1718 8
Machine Language
10001
10010
01000
00000
100000
000000
6 bits5 bits 5 bits 5 bits 5 bits 6 bits
oprs rtrdshamtfunct
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 11000000 0000
$t1
1111111111111111 11000011 11111111
$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-$7hold 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 010010000000000011001
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 ofthe 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
jLoop
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)
00000000(0)
while (save[i] == k) i += 1;00010100(4)
00101000(8)
i k save[0] addr00111100(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, 2800000019940
add$t1, $t1, $s68000409229032
lw $t0, 0($t1)8000835980
bne$t0, $s5, Exit8001258212(PC+i*4)
addi $s3, $s3, 180016819191PC
jLoop80020220000 (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, constantif (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 ScienceThe University of Adelaide, School of Computer Science*Chapter 2 — Instructions: Language of the Computer*Chapter 2 — Instructions: Language of the ComputerBranch Instruction DesignWhy not blt, bge, etc?Hardware for <, ≥, … slower than =, ≠Combining with branch involves more work per instruction, requiring a slower clockAll instructions penalized!beq and bne are the common caseThis is a good design compromiseThe University of Adelaide, School of Computer ScienceThe University of Adelaide, School of Computer Science*Chapter 2 — Instructions: Language of the Computer*Chapter 2 — Instructions: Language of the ComputerSigned vs. Unsigned for sltSlt: set on less thanslt$t0, $s0, $s1 #if $s0 < $s1, then $t0 = 1Signed comparison: slt, sltiUnsigned comparison: sltu, sltuiExample$s0 = 1111 1111 1111 1111 1111 1111 1111 1111$s1 = 0000 0000 0000 0000 0000 0000 0000 0001slt$t0, $s0, $s1# signed–1 < +1$t0 = 1sltu $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
OperationCJavaMIPS
Shift left<<<<sllShift 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: .word12 # 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)
jalprint# 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 $s0i=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
0zeroconstant 0
1at reserved for assembler
2v0results from function call
3v1returned to caller
4 a0arguments to function
5a1from caller: caller saves
6a2
7a3
8t0temporary: caller saves
. . .(callee can clobber)
15t7
MIPS: Software Conventions
for Registers
16s0callee saves
. . . (caller can clobber)
23s7
24t8 temporary (cont’d)
25t9
26k0reserved for OS kernel
27k1
28gppointer to global area
29spstack pointer
30fpframe pointer
rareturn 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 mainmain:addi $a0, $0, 7 jal fact nopmove $a0, $v0li $v0, 1syscall li$v0, 10syscall fact:addi $sp, $sp, -8sw $ra, 4($sp)sw $a0, 0($sp) slti $t0, $a0, 1beq $t0, $0, NGE1nop addi $v0, $0, 1addi $sp, $sp, 8jr $raNGE1:addi $a0, $a0, -1jal factnoplw $a0, 0($sp)lw $ra, 4($sp)addi $sp, $sp, 8mul $v0, $a0, $v0jr $rastack return address and argumentexitprint valuereturned byfactbranch to GT0 if n>=1
if n < 1 return 1if 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 = 0loop1: 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
Reviews
There are no reviews yet.