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

PowerPoint 演示文稿

CO101

Principle of Computer

Organization

Lecture 06: Instruction Set
Architecture 2

Liang Yanyan

澳門科技大學
Macau of University of Science and Technology

MIPS Arithmetic Instructions

• MIPS assembly language arithmetic statement

• Each arithmetic instruction performs one operation

• Each specifies exactly three operands that are all

contained in the datapath’s register file ($t0,$s1,$s2)

• Instruction Format (R format)

add $t0, $s1, $s2

sub $t0, $s1, $s2

destination = source1 op source2

MIPS Logical Instructions

• There are a number of bit–wise logical operations in the

MIPS ISA

and $t0, $t1, $t2 #$t0 = $t1 & $t2

or $t0, $t1, $t2 #$t0 = $t1 | $t2

nor $t0, $t1, $t2 #$t0 = not($t1 | $t2)

• Instruction Format (R format)

MIPS Shift Instructions

• Need operations to pack and unpack 8–bit characters

into 32–bit words.

• Shifts move all the bits in a word left or right.

sll $t2, $s0, 8 #$t2 = $s0 << 8 bits srl $t2, $s0, 8 #$t2 = $s0 >> 8 bits

• Such shifts are called logical because they fill with zeros.

MIPS Immediate Instructions
• Small constants are used quite frequently (50% of operands)

Solutions? Why not?
• put ‘typical constants’ in memory and load them.

e.g. count: .word 35

this assembly instruction defines a constant value 35
and this data is stored in memory. The variable
“count” is the memory address of the data 35.

• create hard-wired registers like $zero, which is special register
always store a zero.

• MIPS Arithmetic Instructions with constants:

e.g. addi $s1, $zero, 5 (A = 5)

addi $s2, $s2, 4 (A = A + 4)

slti $s5, $s5, 10
andi $s2, $s2, 6 (A = A & 6)
ori $s2, $s2, 4 (A = A | 4)

MIPS Memory Access Instructions

• MIPS has two basic data transfer instructions for

accessing memory

lw $t0, 4($s3) #load word from memory

sw $t0, 8($s3) #store word to memory

• The data is loaded into (lw) or stored from (sw) a register

in the register file – a 5 bit address.

• The memory address – a 32 bit address – is formed by

adding the contents of the base address register to the

offset value.

• A 16–bit field meaning access is limited to memory locations

within a region of 213 or 8,192 words ( 215 or 32,768 bytes) of the

address in the base register.

MIPS load and store instructions
• Load data from memory and

store data to memory.

• lw $t0, 20($s3)

• lw: load word.

• Meaning: load the data at
memory address [s3+20]
into processor and store into
register t0.

• E.g. if s3 stores a data 24.
The memory address [s3+20]
is 44. The processor loads
the data at memory address
44, which is 79. This data is
loaded into processor and
stored into t0. As a result,
register t0 will store a value
79.

• sw $t0, 20($s3) ??

• sw: store word.

32 bits data

…

32 bits data

…

CPU

Memory (RAM)

…

32 bits data

MIPS load and store instructions
• Example:

C code: b[12] = h + b[8];

MIPS code: lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 48($s3)

Note:
lw $t0, 32($s3) means $t0 = Memory[$s3+32]

sw $t0, 48($s3) means Memory[$s3+48] = $t0

assume $s3 is the address of b[0] → base address

• Remember:
• Arithmetic operands are registers, not memory!

• Loading words but addressing bytes!

why 32 & 48?

32 = 4*8

48 = 4*12

Example

• Can we figure out the code?

swap(int v[], int k);
{ int temp;
temp = v[k]
v[k] = v[k+1];
v[k+1] = temp;
}

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

Assume: $t5 → k

$t4 → base address of v

$t2 → address of v[k]

More MIPS data transfer instructions

Instruction Comment

SW $t1, 100($t2) Store word to location [t2 + 100]

SH $t1, 102($t2) Store lower halfword of t1 to location [t2+102]

SB $t1, 103($t2) Store least significant byte of t1 to [t2+103]

LW $t1, 100($t2) Load word from location [t2+100]

LH $t1, 102($t2) Load halfword with sign extend from [t2+102]

LHU $t1, 102($t2) Load halfword unsigned from [t2+102]

LB $t1, 103($t2) Load byte with sign extend from [t2+103]

LBU $t1, 103($t2) Load byte unsigned from [t2+103]

MIPS control based instructions

• Decision making instructions
• alter the execution flow.

• i.e., change the “next” instruction to be executed.

• MIPS conditional branch instructions:

bne $t0, $t1, Label
beq $t0, $t1, Label

• bne: branch on not equal
• The program jumps to “Label” when the values of t0 and t1 are

not equal.

• beq: branch on equal
• The program jumps to “Label” when the values of t0 and t1 are

equal.

MIPS control based instructions

• When the processor executes the

following assembly program. Since the

value of s0 is 6, and the value of s1 is 9,

it means they are not equal. The

program jumps from “bne” to “abc”,

where the instruction “sub” is executed

and instruction “add” is ignored. After

“sub” is executed, “lw” will be executed.

bne $s0, $s1, abc
add $s3, $s0, $s1

abc: sub $s4, $s1, $s2

lw $t0, 8($t1)

…

32 bits data

…

32 bits data

…

CPU

MIPS control based instructions

• Example: if (i==j) {

h = i + j;

}

k = j – f;

bne $s0, $s1, abc

add $s3, $s0, $s1

abc: sub $s4, $s1, $s2

…

MIPS control based instructions

• MIPS unconditional branch instructions: jump to “Label” directly.

j Label

• Example 1:

abc: a = b + c; abc: add $s1, $s2, $s3

goto abc; j abc;

• Example 2:

if (i!=j) beq $s4, $s5, abc1
h=i+j; add $s3, $s4, $s5
else j abc2
h=i-j; abc1: sub $s3, $s4, $s5
abc2: …

• Can you build a simple for-loop?

In Support of Branch Instructions

• We have beq, bne, but what about other kinds of

branches (e.g., branch–if–less–than)? For this, we need
yet another instruction, slt

• Set on less than instruction:

slt $t0, $s0, $s1 # if $s0 < $s1 then # $t0 = 1 else # $t0 = 0 • Instruction format (R format) • Alternate versions of slt slti $t0, $s0, 25 # if $s0 < 25 then $t0=1 ... sltu $t0, $s0, $s1 # if $s0 < $s1 then $t0=1 ... sltiu $t0, $s0, 25 # if $s0 < 25 then $t0=1 ... 15 Signed vs. Unsigned Comparison R1= 0…00 0000 0000 0000 0001 R2= 0…00 0000 0000 0000 0010 R3= 1…11 1111 1111 1111 1111 • After executing these instructions: slt r4,r2,r1 ; if (r2 < r1) r4=1 else r4=0 slt r5,r3,r1 ; if (r3 < r1) r5=1 else r5=0 sltu r6,r2,r1 ; if (r2 < r1) r6=1 else r6=0 sltu r7,r3,r1 ; if (r3 < r1) r7=1 else r7=0 • What are values of registers r4 - r7? Why? r4 = ; r5 = ; r6 = ; r7 = ; 16 -110 110 210 Signed 429496729510 110 210 Unsigned 0 1 0 0 Aside: More Branch Instructions • Can use slt, beq, bne, and the fixed value of 0 in register $zero to create other conditions • less than blt $s1, $s2, Label slt $at, $s1, $s2 #$at set to 1 if bne $at, $zero, Label #$s1 < $s2 • less than or equal to ble $s1, $s2, Label • greater than bgt $s1, $s2, Label • great than or equal to bge $s1, $s2, Label • Such branches are included in the instruction set as pseudo instructions -- recognized (and expanded) by the assembler. • Its why the assembler needs a reserved register ($at). 17 Bounds Check Shortcut • Treating signed numbers as if they were unsigned gives a low cost way of checking if 0 ≤ x < y (index out of bounds for arrays) sltu $t0, $s1, $t2 # $t0 = 0 if # $s1 > $t2 (max)

# or $s1 < 0 (min) beq $t0,$zero,IOOB # go to IOOB if # $t0 = 0 • The key is that negative integers in two’s complement look like large numbers in unsigned notation. Thus, an unsigned comparison of x < y also checks if x is negative as well as if x is less than y. 18 Looping using compare & branch instructions • Do-while loop 19 …… (Loop body start) …… (Loop body) …… Checking Repeat (Conditional Branch) …… i = 0; do { do something; i = i + 1; } while (i < 10) addi $s1, $zero, 0 START: do something; addi $s1, $s1, 1 slti $t1, $s1, 10 bne $t1, $zero, START Looping using compare & branch instructions 20 • While loop …… Checking break (Conditional Branch) …… (Loop body) …… Unconditional Branch …… i = 0; while (i < 10) { do something; i = i + 1; } addi $s1, $zero, 0 j CHECK START: do something; addi $s1, $s1, 1 CHECK: slti $t1, $s1, 10 bne $t1, $zero, START Looping using compare & branch instructions 21 • FOR loop Initialization control register Checking break (Conditional Branch) …… (Loop body) …… Update control register Unconditional Branch …… for (i = 0; i < 10; i++) { do something; } addi $s1, $zero, 0 START: slti $t1, $s1, 10 beq $t1, $zero, QUIT do something; addi $s1, $s1, 1 j START QUIT: .... Alternative implementation of FOR 22 for (i = 0; i < 10; i++) { do something; } addi $s1, $zero, 0 j CHECK START: do something; addi $s1, $s1, 1 CHECK: slti $t1, $s1, 10 bne $t1, $zero, START MIPS arithmetic instructions Instruction Example Meaning Comments add add $t1,$t2,$t3 $t1 = $t2 + $t3 3 operands; subtract sub $t1,$t2,$t3 $t1 = $t2 – $t3 3 operands; add immediate addi $t1,$t2,100 $t1 = $t2 + 100 + constant; add unsigned addu $t1,$t2,$3 $t1 = $t2 + $t3 3 operands; subtract unsigned subu $t1,$t2,$3 $t1 = $t2 – $t3 3 operands; add imm. unsign. addiu $t1,$t2,100 $t1 = $t2 + 100 + constant; multiply mult $t2,$t3 Hi, Lo = $t2 x $t3 64-bit signed product multiply unsigned multu $t2,$t3 Hi, Lo = $t2 x $t3 64-bit unsigned product divide div $t2,$t3 Lo = $t2 ÷ $t3, Lo = quotient, Hi = remainder Hi = $t2 mod $t3 divide unsigned divu $t2,$t3 Lo = $t2 ÷ $t3, Unsigned quotient & remainder Hi = $t2 mod $t3 Move from Hi mfhi $t1 $t1 = Hi Used to get copy of Hi Move from Lo mflo $t1 $t1 = Lo Used to get copy of Lo 23 MIPS bitwise and logical instructions Instruction Example Meaning Comment and and $t1,$t2,$t3 $t1 = $t2 & $t3 3 reg. operands; Logical AND or or $t1,$t2,$t3 $t1 = $t2 | $t3 3 reg. operands; Logical OR xor xor $t1,$t2,$t3 $t1 = $t2 $t3 3 reg. operands; Logical XOR nor nor $t1,$t2,$t3 $t1 = ~($t2 |$t3) 3 reg. operands; Logical NOR and immediate andi $t1,$t2,10 $t1 = $t2 & 10 Logical AND reg, constant or immediate ori $t1,$t2,10 $t1 = $t2 | 10 Logical OR reg, constant xor immediate xori $t1, $t2,10 $t1 = $t2 10 Logical XOR reg, constant shift left logical sll $t1,$t2,10 $t1 = $t2 << 10 Shift left by constant shift right logical srl $t1,$t2,10 $t1 = $t2 >> 10 Shift right by constant

shift right arithm. sra $t1,$t2,10 $t1 = $t2 >> 10 Shift right (sign extend)

shift left logical sllv $t1,$t2,$t3 $t1 = $t2 << $t3 Shift left by variable shift right logical srlv $t1,$t2, $t3 $t1 = $t2 >> $t3 Shift right by variable

shift right arithm. srav $t1,$t2, $t3 $t1 = $t2 >> $t3 Shift right arith. by variable

MIPS jump, branch, compare instructions

Instruction Example Meaning

branch on equal beq $t1,$t2,abc if ($t1 == $t2) jump to PC+4+imm×4
Equal test; PC relative branch

branch on not eq. bne $t1,$t2,abc if ($t1!= $t2) jump to PC+4+imm×4
Not equal test; PC relative

set on less than slt $t1,$t2,$t3 if ($t2 < $t3) $t1=1; else $t1=0 Compare less than; $t2 and $t3 are 2’s complement set less than imm. slti $t1,$t2,100 if ($t2 < 100) $t1=1; else $t1=0 Compare < constant; $t2 is 2’s complement set less than uns. sltu $t1,$t2,$t3 if ($t2 < $t3) $t1=1; else $t1=0 Compare less than; $t2 and $t3 are natural numbers set l. t. imm. uns. sltiu $t1,$t2,100 if ($t2 < 100) $t1=1; else $t1=0 Compare < constant; $t2 is natural number jump j Label jump to Label jump and link jal Label $t31 = PC + 4; jump to Label For procedure call, $t31 stores the return address jump register jr $ra jump to a location specified by $ra For procedure return 25 MIPS: Software conventions for Registers 26 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) Why do we need register backup? 27 int a = 10; void main() { int b=1; b = addOne(b); a = a + b; } int addOne(int c) { int b; a = 1; b = a + c; return b; } int a = 10; void main() { int b=1; b = addOne(b); a = a + b; } int addOne(int c) { int tmp; int b; tmp = a; a = 1; b = a + c; a = tmp; return b; } Instructions for Accessing Procedures • MIPS procedure call instruction: jal ProcedureAddress #jump and link • Saves PC+4 in register $ra to have a link to the next instruction for the procedure return. • Instruction format (J format) • Then can do procedure return with a jr $ra #return • Instruction format (R format) 28 Six Steps in Execution of a Procedure • 1. Main routine (caller) places parameters in a place where the procedure (callee) can access them • $a0 -- $a3: four argument registers • 2. Caller transfers control to the callee • 3. Callee acquires the storage resources needed • 4. Callee performs the desired task • 5. Callee places the result value in a place where the caller can access it • $v0 -- $v1: two value registers for result values • 6. Callee returns control to the caller • $ra: one return address register to return to the point of origin 29 Register backup in Procedure Call • Some compilers can generate it automatically. • If you write your own assembly program, you need to handle it manually. 30 Procedure Call • Caller • Backup registers • Place arguments where procedure can access them ($a0..$a3, or stack) • Call procedure (execute a “jal” instruction) • Collect result from stack or registers • Restore registers • Callee • Backup registers • Get the arguments from stack or registers ($a0-$a3) • Do the work • Save result to stack or registers • Restore registers • Return 31 Basic Procedure Flow • For a procedure that computes the GCD of two values i (in $t0) and j (in $t1) gcd(i,j); • The caller puts the i and j (the parameters values) in $a0 and $a1 and issues a jal gcd #jump to routine gcd • The callee computes the GCD, puts the result in $v0, and returns control to the caller using gcd: . . . #code to compute gcd jr $ra #return 32 Stack • Last in first out, first in last out 33 a b a b c a after push ‘a’ after push ‘b’ after push ‘c’ a b after 1st pop a after 2nd pop Memory Stacks • MIPS: software convention, i.e. stack is implemented by memory. • SP (Stack pointer): a special register points to the top of stack, i.e. the address of the first element in the stack. • FP (Frame pointer): a special register points to the bottom of stack. 34 a b c High memory address SP Low memory address • Push data to stack • decrement SP • store data to the place pointed by SP • Pop data from stack • load data pointed by SP • increment SP FP Calls: Why Are Stacks So Great? 35 Stacking of Subroutine Calls & Returns and Environments: A: CALL B CALL C C: RET RET B: A A B A B C A B A Example 36 • Before Calling Procedure High Memory Address Low Memory Address Main: …… RESULT = abc(D1, D2); …… $sp $fp Example 37 • Passing arguments High Memory Address D1 D2 {for return result} Low Memory Address Main: …… RESULT = abc(D1, D2); …… $sp $fp Example 38 • Before executing procedure body High Memory Address D1 D2 {for return result} Registers Backup $fp backup Return Address z y x Low Memory Address $sp $fp int abc(int par1, int par2) { int x, y, z; …… …… return x; } Example 39 • Before returning to caller High Memory Address D1 D2 return result <= x Low Memory Address $sp $fp int abc(int par1, int par2) { int x, y, z; …… …… return x; } Example 40 • After Calling Procedure High Memory Address Low Memory Address $sp $fp Main: …… RESULT = function(D1, D2); …… Compiling a C Leaf Procedure • Leaf procedures are ones that do not call other procedures. Give the MIPS assembler code for int leaf_ex (int g, int h, int i, int j) { int f; f = (g+h) – (i+j); return f; } where g, h, i, and j are in $a0, $a1, $a2, $a3 leaf_ex: addi $sp,$sp,-8 #make stack room sw $t1,4($sp) #save $t1 on stack sw $t0,0($sp) #save $t0 on stack add $t0,$a0,$a1 add $t1,$a2,$a3 sub $v0,$t0,$t1 lw $t0,0($sp) #restore $t0 lw $t1,4($sp) #restore $t1 addi $sp,$sp,8 #adjust stack ptr jr $ra 41 Nested Procedures • What happens to return addresses with nested procedures? 42 Nested Procedures Outcome • On the call to rt_1, the return address (next in the caller routine) gets stored in $ra. What happens to the value in $ra (when $a0!=0) when rt_1 makes a call to rt_2? 43 Saving the Return Address, Part 1 • Nested procedures (i passed in $a0, return value in $v0) 44 Saving the Return Address, Part 2 • Nested procedures (i passed in $a0, return value in $v0) 45 Compiling a Recursive Procedure • A procedure for calculating factorial int fact (int n) { if (n < 1) return 1; else return (n * fact (n-1)); } • A recursive procedure (one that calls itself!) fact (0) = 1 fact (1) = 1 * 1 = 1 fact (2) = 2 * 1 * 1 = 2 fact (3) = 3 * 2 * 1 * 1 = 6 fact (4) = 4 * 3 * 2 * 1 * 1 = 24 . . . • Assume n is passed in $a0; result returned in $v0 46 Compiling a Recursive Procedure fact: addi $sp, $sp, -8 #adjust stack pointer sw $ra, 4($sp) #save return address sw $a0, 0($sp) #save argument n slti $t0, $a0, 1 #test for n < 1 beq $t0, $zero, L1 #if n >=1, go to L1

addi $v0, $zero, 1 #else return 1 in $v0

addi $sp, $sp, 8 #adjust stack pointer

jr $ra #return to caller

L1: addi $a0, $a0, -1 #n >=1, so decrement n

jal fact #call fact with (n-1)

#this is where fact
#returns

bk_f: lw $a0, 0($sp) #restore argument n

lw $ra, 4($sp) #restore return address

addi $sp, $sp, 8 #adjust stack pointer

mul $v0, $a0, $v0 #$v0 = n * fact(n-1)

jr $ra #return to caller

A Look at the Stack for $a0 = 2, Part 1

A Look at the Stack for $a0 = 2, Part 2

A Look at the Stack for $a0 = 2, Part 3

A Look at the Stack for $a0 = 2, Part 4

A Look at the Stack for $a0 = 2, Part 5

Aside: Allocating Space on the Stack

• The segment of the stack

containing a procedure’s saved

registers and local variables is

its procedure frame (aka

activation record)

• The frame pointer ($fp) points to

the first word of the frame of a

procedure – providing a stable

“base” register for the procedure

• $fp is initialized using $sp on a

call and $sp is restored using $fp

on a return

Aside: Allocating Space on the Stack

• Static data segment for

constants and other static

variables (e.g., arrays)

• Dynamic data segment

(aka heap) for structures

that grow and shrink (e.g.,

linked lists)

• Allocate space on the heap
with malloc() and free it

with free() in C

Related Posts