PowerPoint 演示文稿
CO101
Principle of Computer
Organization
Lecture 07: Instruction Set
Architecture 3
Liang Yanyan
澳門科技大學
Macau of University of Science and Technology
Assembly Language vs. Machine Language
• Assembly provides convenient symbolic representation
• easier to understand by human, e.g. add $t0, $s1, $s2
• can provide ‘pseudoinstructions‘, e.g., “mov $t0, $t1” exists only
in Assembly would be implemented using “add $t0,$t1,$zero”
• much easier than writing down numbers
• But machines only understand binary numbers (Machine language)
• 10010001000 …. ( It is too difficult to understand! )
• Convert assembly instructions to machine format
• Each register has an ID: use a number to represent each register
2
add $t0, $s1, $s2
00000010001100100100000000100000
Arithmetic, memory, branch instructions
• 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
bne $s4,$s5,L Jump to Label if $s4 != $s5
beq $s4,$s5,L Jump to Label if $s4 = $s5
j Label Jump to Label
• Divide MIPS instructions into 3 categories
• Machine formats:
• 3 formats, all 32 bits wide
• Very structured, rely on compiler to achieve performance
3
op rs rt rd shamt funct
op rs rt immediate
op jump target
R format
I format
J format
4
Aside: MIPS Register Convention
5
0 zero constant 0
1 at reserved for assembler
2 v0 expression evaluation &
3 v1 function results
4 a0 arguments (proc. call)
5 a1
6 a2
7 a3
8 t0 temporary
. . . (callee can clobber)
15 t7
16 s0 preserved, callee
saves and restore
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
31 ra Return Address (HW)
R type
• Mainly used to represent instructions that all their
operands are registers: op rd, rs, rt
• e.g. add $t0, $s1, $s2
• There are exceptional cases: e.g. sll $s0, $s1, 8
• op: opcode
• Operation of the instruction, such as add, sub, …
• rd: destination register
• rs: first source operand
• rt: second source operand
• shamt: shift amount
• The number of bits a data being shifted/rotated
• e.g. sll $s0, $s1, 8 → $s0 = $s1 << 8
• funct: for function that share the same opcode
• Distinguish different operations
6
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
bit 0
bit 31
Example
and t0, t2, s1
op = and = 0 = 000000
rs = t2 = 10 = 01010
rt = s1 = 17 = 10001
rd = t0 = 8 = 01000
shamt = 0 = 00000
funct = 36 = 100100
7
op rs rt rd shamt funct
and t2 s1 t0 0 100100
0 10 17 8 00000 100100
000000 01010 10001 01000 00000 100100
Machine format = 0000 0001 0101 0001 0100 0000 0010 0100
0 1 5 1 4 0 2 4
Example
sll s2, s1, 8
op = sll = 0 = 000000
rs = = 0 = 00000
rt = s1 = 17 = 10001
rd = s2 = 18 = 10010
shamt = 8 = 01000
funct = 0 = 000000
8
op rs rt rd shamt funct
sll s1 s2 8 000000
000000 0 17 18 01000 000000
000000 00000 10001 10010 01000 000000
Machine format = 0000 0000 0001 0001 1001 0010 0000 0000
0 0 1 1 9 2 0 0
I type
• Mainly used to represent instructions that one of their
operands is a constant: op rt, rs, imm
• e.g. addi $s0, $s1, 100
• op: opcode
• Operation of the instruction
• rt: destination register
• rs: first source operand
• imm: immediate value, signed 16 bit number
9
op rs rt immediate value
6 bits 5 bits 5 bits 16 bits
bit 0
bit 31
Aside: How About Larger Constants?
• Immediate can only store 16 bit value, we'd also like to be able to
load a 32 bit constant into a register,
• E.g. 00000000000010000000000000000111
• For this we must use two instructions, a new "load upper immediate"
instruction.
lui $t0, 0000000000001000
• Then must get the lower order bits right, i.e.
addiu $t0, $t0, 0000000000000111
10
0000000000001000 0000000000000000
0000000000000000 0000000000000111
0000000000001000 0000000000000111
+
0000000000001000 0000000000000000
filled with zeros
Example
addi t4, t3, 24
op = addi = 8 = 001000
rs = t3 = 11 = 01011
rt = t4 = 12 = 01100
imm = 24 = 0000 0000 0001 1000
Machine format = 0010 0001 0110 1100 0000 0000 0001 1000
2 1 6 C 0 0 1 8
11
op rs rt imm
andi t3 t4 24
001000 11 12 0000 0000 0001 1000
001000 01011 01100 0000 0000 0001 1000
Load Instruction
• Load/Store Instruction Format (I format):
12
Byte Addresses
• Since 8--bit bytes are so useful, most architectures
address individual bytes in memory.
• Alignment restriction -- the memory address of a word must be
on natural word boundaries (a multiple of 4 in MIPS--32).
• Big Endian: leftmost byte is word address
• IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA
• Little Endian: rightmost byte is word address
• Intel 80x86, DEC Vax, DEC Alpha (Windows NT)
13
Aside: Loading and Storing Bytes
• MIPS provides special instructions to move bytes
lb $t0, 1($s3) #load byte from memory
sb $t0, 6($s3) #store byte to memory
• What 8 bits get loaded and stored?
• load byte places the byte from memory in the rightmost 8 bits of
the destination register
• what happens to the other bits in the register?
• store byte takes the byte from the rightmost 8 bits of a register
and writes it to a byte in memory
• what happens to the other bits in the memory word?
14
EX:
• Given following code sequence and memory state what
is the state of the memory after executing the code?
add $s3, $zero, $zero
lb $t0, 1($s3)
sb $t0, 6($s3)
• What value is left in $t0?
• What word is changed in Memory
and to what?
• What if the machine was little
Endian?
15
Example
lw s4, 4(s3)
op = lw = 100011
rs = s3 = 19 = 10011
rt = s4 = 20 = 10100
imm = 4 = 0000 0000 0000 0100
Machine format = 1000 1110 0111 0100 0000 0000 0000 0100
4 E 7 4 0 0 0 4
16
op rs rt imm
lw s3 s4 4
100011 19 20 0000 0000 0000 0100
100011 10011 10100 0000 0000 0000 0100
J type
• Mainly used for jump instructions: op label
• e.g. j Label
• op: opcode
• Operation of the instruction, e.g. j
• label: 26-bit address
17
op value
6 bits 26 bits
bit 0
bit 31
Addresses in Branches and Jumps
• Instructions:
bne $t4,$t5,Label Next instruction is at Label if $t4 != $t5
beq $t4,$t5,Label Next instruction is at Label if $t4 = $t5
j Label Next instruction is at Label
• Formats:
• What value shall we use to represent Label?
18
op rs rt 16 bit immediate value
op 26 bit address
I
J
Conditional branch
19
addi $t0,$zero,9
addi $t1,$zero,10
beq $t0, $t1, endif
add $t0,$t0,$t1
endif: xor $t1,$t1,$t1
What is the value of address in the compiled machine code?
immediate = 1
assembly code:
beq t0 t1 immediate
If “endif” is below the branch instruction:
immediate = the number of instruction jump over.
If “endif” is above the branch instruction:
immediate = - (2 + the number of instruction jump over)
If jump to the same instruction:
immediate = - 1
Examples
20
Assembly code
beq $s1, $s2, label
beq $s1, $s2, label
label: beq $s1, $s2, label
beq $s1, $s2, label
beq $s1, $s2, label
0x4 0x11 0x12 0x0001
0x4 0x11 0x12 0x0000
0x4 0x11 0x12 0xFFFF
0x4 0x11 0x12 0xFFFE
0x4 0x11 0x12 0xFFFD
op rs rt immediate
Why?
21
op rs rt address
PC +
Memory
Word
Address of next inst. (target PC) = PC + 4 + immediate × 4
compiled machine
code:
The way that processor calculates branch address:
→ immediate = (target PC – PC)/4 - 1
(target PC – PC)/4-1: number of instructions between current and target instruction.
immediate
Examples
22
Address Instruction
0x00000004 beq $s1, $s2, label
0x00000008 beq $s1, $s2, label
0x0000000C beq $s1, $s2, label
0x00000010 beq $s1, $s2, label
0x00000014 beq $s1, $s2, label
label
Address of next inst. (target PC) = PC + 4 + immediate × 4
limits the branch distance to -215 to +215-1 (word)
instructions from the (instruction after the) branch
instruction, but most branches are local anyway.
Jump instruction
23
op address
PC concat
Memory
Word
j END
…
END
…
Address of next inst. (target PC) = (upper 4 bits of (PC + 4) : value) << 2
compiled machine
code:
assembly code:
value
Examples
24
Address Instruction
0x00000004 j lab1
0x00000008 add $t3, $t4, $t5
0x0000000C sub $t5, $t6, $t7
0x00000010 and $t7, $t8, $t9
0x00000014 j lab2
lab1
Address of next inst. (target PC) = (upper 4 bits of (PC + 4) : 26 bit address) << 2
e.g. What is the machine code of “j lab1” ?
1. find the address of lab1: 0 0 0 0 0 0 0 1 0
2. get the target PC = 0000 00000000000000000000000100 00
3. so we get the 26 bit address value 00000000000000000000000100
4. j lab1 000010 00000000000000000000000100
lab2
The upper 4 bits of the target PC and (PC+4) MUST be the same. In other words,
the process must put the target instruction in a position that having the same
upper 4 bits address with the (PC+4).
Summary
• beq label computation
• Given instruction in machine format, how to compute next pc
• Given pc and next pc, how to compute immediate
• j label computation
• Given instruction in machine format, how to compute next pc
• Given pc and next pc, how to compute offset
25
Overview from high level to low level
• High-level language program (in C)
swap (int v[], int k)
(int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
)
• Assembly language program (for MIPS)
swap: sll $t2, $t5, 2
add $t2, $t4, $t2
lw $s5, 0($t2)
lw $s6, 4($t2)
sw $s6, 0($t2)
sw $s5, 4($t2)
jr $ra
• Machine (object, binary) code (for MIPS)
000000 00000 00101 0001000010000000
000000 00100 00010 0001000000100000
. . .
26
C compiler
assembler
one-to-many
one-to-one
CO101�Principle of Computer Organization
Assembly Language vs. Machine Language
Arithmetic, memory, branch instructions
幻灯片编号 4
Aside: MIPS Register Convention
R type
Example
Example
I type
Aside: How About Larger Constants?
Example
Load Instruction
Byte Addresses
Aside: Loading and Storing Bytes
EX:
Example
J type
Addresses in Branches and Jumps
Conditional branch
Examples
Why?
Examples
Jump instruction
Examples
Summary
Overview from high level to low level