Transcript CS 230 Chapter 2 Instructions: Language of the Computer

CS 230: Computer Organization
and Assembly Language
Aviral Shrivastava
Department of Computer Science and Engineering
School of Computing and Informatics
Arizona State University
Slides courtesy: Prof. Yann Hang Lee, ASU, Prof. Mary
Jane Irwin, PSU, Ande Carle, UCB
M
C L
Question
• What is the difference between a calculator and a computer
• A desk calculator is a “fixed program computer”.
– Cannot change the program of such a machine
– You have to re-wire, re-structure, or even re-design the machine
• Computers are “stored program computers”
– The program is a software
– You can feed in new set of instructions and you have a completely
different functionality
• BIG IDEA – Stored Program Concept
• Chief Instrument of change
– Instruction Set Architecture
M
C L
Stored Program Concept
• Everything is represented and
stored as a “bit sequence”
– The program, compiler, editor,
Operating
System,
input
interface, GUI, etc…
• Provides amazing degree of
flexibility
– Computers can be used to
simulate “anything that is
simulatable”
– Compare this with a calculator
M
C L
Announcements
• Quiz 1 on Thursday, Sept 10, 2009
– Open Book, Open notes, open internet
– Chapter 2, (2.1-2.6) Arithmetic, Load Store and Branch
instructions
– Just no function calls
• Project 0
– Start exploring MARS MIPS simulator
• Install it on your machine
• Write some assembly language programs, e.g., add two numbers
– DO NOT SUBMIT
• Project 1
– Will be online on Thursday
– About writing some assembly language programs
– Due in 1 week, end of Wednesday
M
C L
What you need to know
• So far –
– Should be able to write assembly programs for
• Arithmetic operations
• Given memory state, and some load store operations, you
should be able to tell what is the final state of the memory
• Convert assembly instructions to binary forms
– R and I format instructions
• Today –
– Should be able to write assembly programs for
• Control flow - Branches, loops
• Except function calls
M
C L
Below the Program

High-level language program (in C)
swap (int v[], int k)
. . .
Assembly
swap:

language program (for MIPS)
sll
add
lw
lw
sw
sw
jr
C - Compiler
$2, $5, 2
$2, $4, $2
$15, 0($2)
$16, 4($2)
$16, 0($2)
$15, 4($2)
$31
Machine (object) code (for MIPS)
000000
000000
100011
100011
101011
101011
000000
00000
00100
00010
00010
00010
00010
11111
00101
00010
01111
10000
10000
01111
00000
0001000010000000
0001000000100000
0000000000000000
0000000000000100
0000000000000000
0000000000000100
0000000000001000
Assembler
M
C L
MIPS Instructions, so far
Category
Arithmetic
(R format)
Data
transfer
(I format)
Instr
Op Code
Example
Meaning
add
0 and 32
add $s1, $s2, $s3
$s1 = $s2 + $s3
subtract
0 and 34
sub $s1, $s2, $s3
$s1 = $s2 - $s3
load word
35
lw
$s1, 100($s2)
$s1 = Memory($s2+100)
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
M
C L
MIPS R3000 ISA
Registers
• Instruction Categories
–
–
–
–
R0 - R31
Arithmetic
Load/Store
Jump and Branch
Floating Point
PC
HI
• coprocessor
LO
– Memory Management
– Special
• 3 Instruction Formats: all 32 bits wide
6 bits
5 bits
OP
rs
6 bits
OP
OP
5 bits
5 bits
5 bits
rt
rd
sa
5 bits
5 bits
5 bits
5 bits
rs
rt
immediate
jump target
6 bits
funct
R Format
6 bits
I Format
M
C L
Naming Convention for Registers
0
$zero constant 0 (Hardware)
16
1
$at reserved for assembler
...
2
$v0 expression evaluation &
23
$s7
3
$v1 function results
24
$t8
4
$a0 arguments
25
$t9
5
$a1
26
$k0 reserved for OS kernel
6
$a2
27
$k1
7
$a3
28
$gp pointer to global area
8
$t0 temporary: caller saves
29
$sp stack pointer
(callee can clobber)
30
$fp frame pointer
31
$ra return address (Hardware)
...
15
$t7
$s0 callee saves
(caller can clobber)
temporary (cont’d)
M
C L
MIPS Organization so far
• Arithmetic instructions – to/from the register file
• Load/store instructions - to/from memory
Memory
Processor
1…1100
Register File
src1 addr
src2 addr
dst addr
write
data
src1
32 data
5
5
5
32
registers
($zero - $ra)
32
32 bits
32 ALU
32
src2
data
32
read/write
addr
230 words
32
read data
32
write data
32
32
4
0
byte address
(big Endian)
5
1
6
2
32 bits
7
3
0…1100
0…1000
0…0100
0…0000
word address
(binary)
M
C L
Which end do you break your egg?
• Gulliver’s Travel
– Lilliput: Sharp-end
– Blefuscu: Rounded-end
(Little-endian)
(Big-endian)
• Suppose, we have these two values in registers
$s1 =
1111 1111 0000 0000 1111 0000 0000 1111
$s2 =
0000 0000 1111 1111 0000 1111 1111 0000
• We store these values in memory
lw $s1 4($t0)
lw $s2 8($t0)
$t0= 0x4080
M
C L
What does the memory look like?
12
408b
408a
1111 0000
4089
4088
1111 1111
4087
4086
0000 1111
4085
4084
0000 0000
0000 1111
0000 0000
1111 0000
1111 1111
.
..
1111 1111
0000 0000
1111 0000
0000 1111
0000 0000
1111 1111
0000 1111
1111 0000
$t0= 0x4080
lw $s1 4($t0)
lw $s2 8($t0)
Increasing Address
Increasing Address
$s1 =
$s2 =
408b
408a
0000 0000
4089
4088
0000 1111
4087
4086
1111 1111
4085
4084
1111 0000
1111 0000
0000 0000
0000 1111
.
..
1
1
0
0
7/7/2015
1111 1111
M
C L
Memory Addressing
• What is the word at address 4080?
1111 1111 0000 0000 1111 0000 0000 1111
• What is the byte at address 4086?
Memory
Memory
4088
0000 0000 1111 0000 0000 1111 1111 1111
0000 0000 1111 0000 0000 1111 1111 1111
4084
1111 0000 0000 1111 1111 1111 0000 0000
1111 0000 0000 1111 1111 1111 0000 0000
1111 1111 0000 0000 1111 0000 0000 1111
1111 1111 0000 0000 1111 0000 0000 1111
4080
8
4
0
9
5
1
10
6
2
11
7
3
7/7/2015
7
3
Address
13
11
10
6
2
9
5
1
8
4088
4084
4
0
4080
Address
M
C L
Memory Addressing
• What is the word at address
4080?
1111 1111 0000 0000 1111 0000 0000 1111
• What is the byte at address 4086?
4088
1111 1111
0000 1111
Big Endian Memory
Little Endian Memory
0000 0000 1111 0000 0000 1111 1111 1111
0000 0000 1111 0000 0000 1111 1111 1111
1111 0000 0000 1111 1111 1111 0000 0000
1111 0000 0000 1111 1111 1111 0000 0000
1111 1111 0000 0000 1111 0000 0000 1111
1111 1111 0000 0000 1111 0000 0000 1111
8
4084
4
4080
0
9
5
1
10
6
2
11
7
3
7
3
10
6
2
9
5
1
8
4084
4
4080
0
Address
Address
14
11
4088
Leftmost byte is word address
Rightmost byte is word address
e.g., Motorola 68k, MIPS, Sparc, HP PA
e.g., Intel 80x86, DEC Vax, DEC Alpha
7/7/2015
M
C L
Endian-ness and Alignment
• Big Endian: leftmost byte is at word address
• Little Endian: rightmost byte is at word address
little endian byte 0
3
2
1
0
msb
0
big endian byte 0
lsb
1
2
3
0
1
2
3
Aligned
Alignment restriction: requires that
objects fall on address that is multiple
of their size.
15
7/7/2015
Not
Aligned
M
C L
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
op
rs
rt
16 bit number
• 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
16
7/7/2015
M
C L
Example of Loading and Storing Bytes
• Given following code sequence and memory state (contents are given
in hexadecimal), what is the state of the memory after executing the
code?
add
lb
sb
$s3, $zero, $zero
$t0, 1($s3)
$t0, 6($s3)
mem(4) = 0xFFFF90FF
Memory
17
00000000
24
00000000
20
00000000
16
10000010
12
01000402
8
FFFFFFFF
4
009012A0
0
Data
7/7/2015

What value is left in $t0?
$t0 = 0x00000090

What if the machine was little Endian?
mem(4) = 0xFF12FFFF
$t0 = 0x00000012
Word Address (Decimal)
M
C L
Instructions for Making Decisions
• Decision making instructions
– alter the control flow
– i.e., change the "next"
• MIPS
instruction
conditional
branch
bne $s0, $s1, Label #go
beq $s0, $s1, Label #go
to
to
• Example:
Lab1:
to
be
executed
instructions:
Label
Label
if
if
$s0$s1
$s0=$s1
if (i==j) h = i + j;
bne
add
...
$s0,
$s3,
$s1,
$s0,
Lab1
$s1
M
C L
Assembling Branches
• Instructions:
bne $s0, $s1, Label #go to Label if $s0$s1
beq $s0, $s1, Label #go to Label if $s0=$s1
• Machine Formats:
op
rs
rt
16 bit number
5
16
17
????
4
16
17
????
I format
• How is the branch destination address specified?
M
C L
Specifying Branch Destinations
• Could specify the memory address
– But that would require 32 bit field
• Could use a register (like lw and sw) and
add to it the 16-bit offset
– which register?
• Instruction Address Register
PC  bne $s0,$s1,Lab1
add $s3,$s0,$s1
Lab1:
...
– PC = program counter
• its use is automatically implied by
instruction
• PC gets updated (PC+4) during the fetch
cycle so that it holds the address of the
next instruction
– limits the branch distance to -215 to +215-1
instructions from the (instruction after
the) branch instruction, but
• most branches are local anyway (principle
of locality)
M
C L
Disassembling Branch Destinations
• The contents of the updated PC (PC+4) is added to the low
order 16 bits of the branch instruction which is converted into a
32 bit value by
– concatenated two low-order zeros to create an 18 bit number
– sign-extending those 18 bits
• The result is written into the PC if the branch condition is true
prior to the next Fetch cycle
from the low order 16 bits of the branch instruction
16
offset
sign-extend
00
32
32 Add
PC
32
32
4
32
Add
32
branch dst
address
32
?
M
C L
Assembling Branches Example
• Assembly code
Lab1:
bne
add
...
$s0,
$s3,
$s1,
$s0,
Lab1
$s1
• Machine Format of bne:
op
rs
rt
5
16
17
16 bit offset
I format
1
• Remember
– After the bne instruction is fetched, the PC is updated to
address the add instruction (PC = PC + 4).
– Two low-order zeros are concatenated to the offset number
and that value sign-extended is added to the (updated) PC
M
C L
Another Instruction for Changing Flow
• MIPS also has an unconditional branch instruction or
jump
instruction:
j
label
#go to label
if
• Example:
else
Lab1:
Lab2:
beq
add
$s0,
$s3,
sub
...
$s3,
(i!=j)
h=i+j;
h=i-j;
j
$s1,
$s0,
Lab2
$s0,
Lab1
$s1
$s1
M
C L
Assembling Jumps
• Instruction:
j label
• Machine
op
2
#go to label
Format:
26-bit address
J format
????
• How is the jump destination address specified?
– As an absolute address formed by
• concatenating the upper 4 bits of the current PC (now PC+4) to
the 26-bit address and
• concatenating 00 as the 2 low-order bits
M
C L
Disassembling Jump Destinations
• The low order 26 bits of the jump instruction is converted into a 32
bit jump instruction destination address by
– concatenating two low-order zeros to create an 28 bit (word) address
– concatenating the upper 4 bits of the current PC (now PC+4)
• to create a 32 bit instruction address that is placed into the PC prior
to the next Fetch cycle
from the low order 26 bits of the jump instruction
26
00
32
PC
4
32
M
C L
Assembling Branches and Jumps
• Assemble the MIPS machine code (in decimal is fine) for the following
code sequence. Assume that the address of the beq instruction is
0x00400020 (hex address)
Lab1:
beq
add
$s0,
$s3,
sub
$s3,
Lab2:
j
$s1,
$s0,
Lab2
$s0,
...
Lab1
$s1
$s1
0x00400020
4
16
17
2
0x00400024
0
16
17
0x00400028
2
0000 0100 0 ... 0 0011 002
19
0
32
jmp dst = (0x0) 0x040003 002(002)
= 0x00400030
0x0040002c
0
0x00400030
...
16
17
19
0
34
M
C L
Compiling While Loops
• Compile the assembly code for the C
while loop where i is in $s0, j is in $s1,
and k is in $s2
while
(i!=k)
i=i+j;
Loop:
Exit:
beq $s0, $s2, Exit
add $s0, $s0, $s1
j
Loop
. . .
M
C L
More Instructions for Making Decisions
• We have beq, bne, but what about branch-if-less-than?
• New instruction:
slt $t0, $s0, $s1
# if $s0 < $s1
#
#
$t0
#
#
$t0 = 0
then
=
1
else
• Machine format:
op
0
rs
rt
16
17
rd
8
funct
0
42 = 0x2a
M
C L
2
Other Branch Instructions
• Can use slt, beq, bne, and the fixed value of 0 in
create all relative conditions
– less than
blt $s1, $s2, Label
– less than or equal to
ble $s1, $s2,
– greater than
bgt $s1, $s2,
– great than or equal to
bge $s1, $s2,
register $zero to
Label
Label
Label
• Example slt
bne
$t0, $s1, $s2
#$t0 set to 1 if
$t0, $zero, Label
# $s1 < $s2
M
C L
Another Instruction for Changing Flow
• Most higher level languages have case or switch
statements allowing the code to select one of many
alternatives depending on a single value.
• Instruction:
jr $t1
#go to address in $t1
• Machine format:
op
rs
0
9
funct
0
0
0
8 = 0x08
M
C L
2
Compiling a Case (Switch) Statement
Memory
switch (k) {
case 0: h=i+j; break; /*k=0*/
case 1: h=i+h; break; /*k=1*/
case 2: h=i-j; break; /*k=2*/
$t4
• Assuming three sequential words in memory starting at
the address in $t4 have the addresses of the labels L0, L1,
and L2 and k is in $s2
L2:
add
add
add
lw
jr
add
j
add
j
sub
Exit:
. . .
L0:
L1:
$t1,
$t1,
$t1,
$t0,
$t0
$s3,
Exit
$s3,
Exit
$s3,
$s2, $s2
$t1, $t1
$t1, $t4
0($t1)
L0
L1
L2
$s0, $s1
#$t1 = 2*k
#$t1 = 4*k
#$t1 = addr of JT[k]
#$t0 = JT[k]
#jump based on $t0
#k=0 so h=i+j
$s0, $s3
#k=1 so h=i+h
$s0, $s1
#k=2 so h=i-j
M
C L
MIPS Instructions, so far
Category
Instr
Op Code
Example
Meaning
Arithmetic
(R format)
add
0 and 32
add $s1, $s2, $s3
$s1 = $s2 + $s3
subtract
0 and 34
sub $s1, $s2, $s3
$s1 = $s2 - $s3
Data
transfer
(I format)
load word
35
lw
$s1, 100($s2)
$s1 = Memory($s2+100)
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
load byte
32
lb
$s1, 101($s2)
$s1 = Memory($s2+101)
store byte
40
sb
$s1, 101($s2)
Memory($s2+101) = $s1
br on equal
4
beq $s1, $s2, L
if ($s1==$s2) go to L
br on not equal
5
bne $s1, $s2, L
set on less than
0 and 42
if ($s1 !=$s2) go to L
if ($s2<$s3) $s1=1 else
$s1=0
Cond.
Branch
Uncond.
Jump
jump
jump register
slt
$s1, $s2, $s3
2
j
2500
go to 10000
0 and 8
jr
$t1
go to $t1
M
C L
MIPS Organization
Processor
Memory
Register File
src1 addr
5
src2 addr
5
dst addr
write data
5
1…1100
src1
32 data
32
registers
($zero - $ra)
read/write
addr
src2
data
32
32
32
32 bits
br offset
32
Fetch
PC = PC+4
Exec
32 Add
PC
32 Add
4
read data
32
32
32
write data
32
Decode
230
words
32
32 ALU
32
32
4
0
5
1
6
2
32 bits
byte address
(big Endian)
7
3
0…1100
0…1000
0…0100
0…0000
word address
(binary)
M
C L
MIPS R3000 ISA
Registers
• Instruction Categories
–
–
–
–
R0 - R31
Arithmetic
Load/Store
Jump and Branch
Floating Point
PC
HI
• coprocessor
LO
– Memory Management
– Special
• 3 Instruction Formats: all 32 bits wide
6 bits
5 bits
OP
rs
rt
6 bits
5 bits
5 bits
OP
rs
rt
6 bits
OP
5 bits
5 bits
5 bits
rd
sa
6 bits
funct
R Format
16 bits
immediate
26 bits
26-bit jump target
I Format
M
C L
J Format
Yoda says…
• Luke: What's in there?
Yoda: Only what you take with you
M
C L