ECE4680 Computer Organization & Architecture MIPS Instruction Set Architecture

Why is MIPS a good example? Learn ISA further by this example. How does IS fill up the gap between HLL and machine?

ECE4680 Lec4 MIPS.1

February 6, 2002

RISC Vs. CISC

RISC CISC
Determined by VLSI technology. Software cost goes up constantly. To be convenient for programmers. To shorten the semantic gap between HLL and architecture without advanced compilers. To reduce the program length because memory was expensive.
VAX 11/780 reached the climax with >300 instructions and >20 addressing modes.

CISC

RISC

Things changed: HLL, Advanced Compiler, Memory size, Finding: 25% instructions used in 95% time. Size: usually <100 instructions and <5 addressing modes. Other properties: fixed instruction format, register based, hardware control Gains: CPI is smaller, Clock cycle shorter, Hardware simpler, Pipeline easier Loss: Program becomes longer, but memory becomes larger and larger, cheaper and cheaper. Programmability becomes poor, but people use HLL instead of IS. Result: although program is prolonged, the total gain is still a plus.
ECE4680 Lec4 MIPS.2

February 6, 2002

MIPS R2000 / R3000 Registers

32-bit machine --> Programmable storage 31 x 32-bit GPRs (R0 = 0) 32 x 32-bit FP regs (f0 - f31, paired DP) HI, LO, PC: SPRegisters Big Endian 2 nomenclatures(next slide)
See Fig. A.18 at P. A-50 for more details

232 x bytes
r0 r1 r31 PC lo hi
0

Addressing modes: immediate register displacement All instructions are 32-bit wide and must be aligned.

ECE4680 Lec4 MIPS.3

February 6, 2002

2 Nomenclatures of MIPS Registers (p.140, A-23)

Name zero at v0 v1 a0 a3 t0 t7 s0 s7 t8 t9 k0 k1 gp sp fp ra number 0 1 23 47 8 15 16 23 24 25 26 27 28 29 30 31 Usage constant value =0 reserved for assembler (p.147,157) Reserved on call? n.a. n.a.

values for results and expression evaluation no arguments temporaries saved more temporaries Reserved for kernel global pointer stack pointer frame pointer return address no no yes no n.a. yes yes yes yes

zero at v0-v1 a0 - a3 t0 - t7 s0 - s7 t8 - t9 k0 - k1 gp sp fp ra
0 1 2 - 3 4-7 8 --- 15 16 --- 23 24 - 25 26 - 27 28 29 30 31
ECE4680 Lec4 MIPS.4

February 6, 2002

MIPS arithmetic and logic instructions

Instruction add subtract add immediate multiply divide Move from Hi Move from Lo Example add $1,$2,$3 sub $1,$2,$3 addi $1,$2,100 mult $2,$3 div $2,$3 mfhi $1 mflo $1 Meaning $1 = $2 + $3 $1 = $2 $3 $1 = $2 + 100 Comments 3 operands; exception possible 3 operands; exception possible + constant; exception possible

Hi, Lo = $2 x $3 64-bit signed product Lo = $2 $3, Lo = quotient, Hi = remainder Hi = $2 mod $3 $1=Hi get a copy of Hi $1=lo

Instruction and or xor nor

ECE4680 Lec4 MIPS.5

Example and $1,$2,$3 or $1,$2,$3 xor $1,$2,$3 nor $1,$2,$3

Meaning $1 = $2 & $3 $1 = $2 | $3 $1 = $2 $3 $1 = ~($2 |$3)

Comment Logical AND Logical OR Logical XOR Logical NOR

February 6, 2002

Example (p110) E.g. f= (g+h) - (i+j), assuming f, g, h, i, j be assigned to $1, $2, $3, $4, $5 add $7, $2, $3 add $8, $4, $5 sub $1, $7, $8

ECE4680 Lec4 MIPS.6

February 6, 2002

MIPS data transfer instructions

Instruction SW 500($4), $3 SH 502($2), $3 SB 41($3), $2 LW $1, 30($2) LH $1, 40($3) LB $1, 40($3) Comment Store word Store half Store byte Load word Load half a word Load byte

ECE4680 Lec4 MIPS.7

February 6, 2002

Example (pp112-114) Assume A is an array of 100 words, and compiler has associated the varialbes g and h with the register $1 and $2. Assume the base address of the array is in $3. Translate g = h + A[8] lw $4, 8($3); add $1, $2, $4; $4 <-- A[8]
offset or displacement
base register

lw $4, 32($3); add $1, $2, $4 A[12] = h+A[8] SW $1, 48($3)

ECE4680 Lec4 MIPS.8

February 6, 2002

Example (p114) Assume A is an array of 100 words, and compiler has associated the varialbes g, h, and i with the register $1, $2, $5. Assume the base address of the array is in $3. Translate g = h + A[i] addi $6, $0, 4; mult $5, $6; mflo $6; add $4, $3, $6; add $1, $2, $4 $6 = 4 Hi,Lo = i*4 $6 = i*4, assuming i is small $4 address of A[i]

ECE4680 Lec4 MIPS.9

February 6, 2002

MIPS jump, branch, compare instructions

Instruction branch on equal Example Meaning beq $1,$2,100 if ($1 == $2) go to PC+4+100 Equal test; PC relative branch

branch on not eq. bne $1,$2,100 if ($1!= $2) go to PC+4+100 Not equal test; PC relative Pseudoinstruction blt, ble, bgt, bge not implemented by hardware, but synthesized by assembler

set on less than

slt $1,$2,$3 if ($2 < $3) $1=1; else $1=0 Compare less than; 2s comp.

set less than imm. slti $1,$2,100 if ($2 < 100) $1=1; else $1=0 Compare < constant; 2s comp. jump jump register jump and link j 10000 go to 10000 Jump to target address jr $31 go to $31 For switch, procedure return jal 10000 $31 = PC + 4; go to 10000 For procedure call
February 6, 2002

ECE4680 Lec4 MIPS.10

Example (p123) if (i==j) go to L1; f = g+ h; f = f - i; if (i >=j) go to L1;

L1:

Assuming f, g, h, i, j ~ $1, $2, $3, $4, $5

L1:

beq $4, $5, L1 add $1, $2, $3 sub $1, $1, $4

pseudoinstruction

bqe $4, $5, L1

assembler

slt $1, $4, $5 beq $0, $1, L1

ECE4680 Lec4 MIPS.11

February 6, 2002

Example (p126) Loop: g = g +A[i]; i = i+ j; if (i != h) go to Loop: Assuming variables g, h, i, j ~ $1, $2, $3, $4 and base address of array is in $5 Loop: add $7, $3, $3; add $7, $7, $7; add $7, $7, $5 lw $6, 0($7); add $1, $1, $6; add $3, $3, $4 bne $3, $2, Loop; i*2 i*4 $6=A[i] g= g+A[i]

ECE4680 Lec4 MIPS.12

February 6, 2002

Example (p127) while (A[i]==k) i = i+j; Assume i, j, and k ~ $17, $18, $19 and base of A is in $3 Loop: add $20, $17, $17 add $20, $20, $20 add $20, $20, $3 lw $21,0($20) bne $21, $19, Exit add $17, $17, $18 j Loop Exit:

ECE4680 Lec4 MIPS.13

February 6, 2002

MIPS Addressing Modes/Instruction Formats (p118,148,152)

R-format: Register (direct) 6 op 5 rs 5 rt 5 rd 5
smt

6 func

I-format: Immediate Base+index

register op op rs rs rt rt immed immed + immed + Memory Memory

Memory

register PC-relative op rs rt

PC + 4

J-format:
op

addr.

ECE4680 Lec4 MIPS.14

February 6, 2002

Example: See machine code in memory (p149)

while (A[i]==k) i = i+j; Assume i, j, and k ~ $17, $18, $19 and base of A is in $3

Loop: add $20, $17, $17 add $20, $20, $20 add $20, $20, $3 lw $21,0($20) bne $21, $19, Exit add $17, $17, $18 j Loop Exit:

Assume the loop is placed starting at loc 8000 8000: 0 17 17 20 0 32 0 0 5 0 2 20 20 21 17 20 3 21 19 18 8000 17 20 20 0 8 2 0 32 2000 0 0 32 32

35 20

Offset in branch is relative. Address in jump is absolute. Address in Branch or Jump instruction is word address so that they can go 4 times far as opposed to byte address. (p150)
ECE4680 Lec4 MIPS.15

February 6, 2002

Procedure Call and Stack

Stacking of Subroutine Calls & Returns and Environments: A: CALL B B: CALL C C: RET A B RET A Some machines provide a memory stack(special hardware) as part of the architecture (e.g. the VAX). Use special instructions, e.g. pop, push. Sometimes stacks are implemented via software convention (e.g. MIPS). Use same data transfer instructions, e.g., lw, sw. A B C A B A

ECE4680 Lec4 MIPS.16

February 6, 2002

Example in C: swap (pp163-165)

Assume swap is called as a procedure Assume temp is register $15; arguments v and k ~ $16 and $17; Write MIPS code swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; }

sll addu lw lw sw sw

$18, $17, 2 $18, $18, $16 $15, 0($18) $19, 4($18) $19, 0($18) $15, 4($18)

; mulitply k by 4 ; address of v[k] ; load v[k] ; load v[k+1] ; store v[k+1] into v[k] ; store old v[k] into v[k+1]

Registers $15, $16, $17, $18, $19 are occupied by caller ??

ECE4680 Lec4 MIPS.17

February 6, 2002

Example: Swap
Given a procedure swap(v, j) Calling swap is as simple as jal swap jal --- jump and link $31 = PC+4; goto swap

$31=$ra : always store return address

ECE4680 Lec4 MIPS.18

February 6, 2002

swap: MIPS
swap: addi sw sw sw sw sw sw .... lw lw lw lw lw lw addi jr $19, 0($sp) $18, 4($sp) $17, 8($sp) $16, 12($sp) $15, 16($sp) $31, 20($sp) $sp,$sp, 24 $31 ; Restore return address ; restore top of stack ; return to place that called swap
February 6, 2002

$sp,$sp, 24 $31, 20($sp) $15, 16($sp) $16, 12($sp) $17, 8($sp) $18, 4($sp) $19, 0(sp)

; Make room on stack for 6 registers ; Save return address ; Save registers on stack

; Restored registers from stack

ECE4680 Lec4 MIPS.19

Other ISAs
Intel 8086/88 => 80286 => 80386 => 80486 => Pentium => P6 8086 few transistors to implement 16-bit microprocessor tried to be somewhat compatible with 8-bit microprocessor 8080 successors added features which were missing from 8086 over next 15 years product of several different Intel engineers over 10 to 15 years Announced 1978 VAX simple compilers & small code size => efficient instruction encoding powerful addressing modes powerful instructions few registers product of a single talented architect Announced 1977

ECE4680 Lec4 MIPS.20

February 6, 2002

Machine Examples: Address & Registers

Intel 8086 2 20 x 8 bit bytes AX, BX, CX, DX SP, BP, SI, DI CS, SS, DS IP, Flags 32 2 x 8 bit bytes 16 x 32 bit GPRs 24 2 x 8 bit bytes 8 x 32 bit GPRs 7 x 32 bit addr reg 1 x 32 bit SP 1 x 32 bit PC 32 2 x 8 bit bytes 32 x 32 bit GPRs 32 x 32 bit FPRs HI, LO, PC acc, index, count, quot stack, string code,stack,data segment

VAX 11

r15-- program counter r14-- stack pointer r13-- frame pointer r12-- argument ptr

MC 68000

MIPS

ECE4680 Lec4 MIPS.21

February 6, 2002

Homework 2, due Feb. 20, 2002

Questions 3.2, 3.3, 3.5, 3.6, 3.7, 3.9, 3.11 To answer question 3.7, please refer to Figure 3.13 (page 140) for register convention To answer 3.11, please refer to sort example in pages 166 for a skeleton of for loop

ECE4680 Lec4 MIPS.22

February 6, 2002