程序代写代做代考 mips compiler assembly assembler PowerPoint 演示文稿

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