Machine Instructions:
• Language of the Machine
• Lowest level of programming, control directly the hardware
• Assembly instructions are symbolic versions of machine
instructions
• More primitive than higher level languages
• Very restrictive
• Programs are stored in the memory, one instruction is fetched
and executed at a time
• We’ll be working with the MIPS instruction set architecture
1998 Morgan Kaufmann Publishers
1
MIPS instruction set:
• Load from memory
Store in memory
• Logic operations
– and, or, negation, shift, ...
• Arithmetic operations
– addition, subtraction, ...
• Branch
1998 Morgan Kaufmann Publishers
2
Instruction types:
• 1 operand
Jump #address
Jump $register number
• 2 operands
Multiply $reg1, $reg2
• 3 operands
Add $reg1, $reg2, $reg3
1998 Morgan Kaufmann Publishers
3
MIPS arithmetic
• Instructions have 3 operands
• Operand order is fixed (destination first)
Example:
C code:
A=B+C
MIPS code:
add $s0, $s1, $s2
$s0, etc. are registers
(associated with variables by compiler)
1998 Morgan Kaufmann Publishers
4
MIPS arithmetic
• Design Principle 1: simplicity favours regularity.
• Of course this complicates some things...
C code:
A = B + C + D;
E = F - A;
MIPS code:
add $t0, $s1, $s2
add $s0, $t0, $s3
sub $s4, $s5, $s0
• Operands must be registers, 32 registers provided
• Design Principle 2: smaller is faster.
1998 Morgan Kaufmann Publishers
5
Registers vs. Memory
• Arithmetic instructions operands are registers.
• Compiler associates variables with registers.
• What about programs with lots of variables? Memory!
Control
Input
Memory
Datapath
Processor
Output
I/O
1998 Morgan Kaufmann Publishers
6
Memory Organization
• Viewed as a large, single-dimension array, with an address.
• A memory address is an index into the array.
• "Byte addressing" means that the index points to a byte of
memory.
0
1
2
3
4
5
6
...
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
1998 Morgan Kaufmann Publishers
7
Memory Organization
• Bytes are nice, but most data items use larger "words”.
• For MIPS, a word is 32 bits or 4 bytes.
0
4
8
12
...
32 bits of data
32 bits of data
32 bits of data
Registers hold 32 bits of data.
32 bits of data
• 232 bytes with byte addresses from 0 to 232-1
• 230 words with byte addresses 0, 4, 8, ... 232-4
• Words are aligned, i.e., the 2 least significant bits of a word
address are equal to 0.
– Not in all architectures!
1998 Morgan Kaufmann Publishers
8
Load and store instructions
• Example:
C code:
A[8] = h + A[8];
MIPS code: lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 32($s3)
• $s3 contains the base of the array.
$s2 contains h.
• Word offset 8 equals byte offset 32.
• Store word has destination last.
• Remember arithmetic operands are registers, not memory!
1998 Morgan Kaufmann Publishers
9
So far we’ve learned:
• MIPS
— loading and storing words but addressing bytes
— arithmetic on registers only
• Instruction
add $s1, $s2, $s3
sub $s1, $s2, $s3
lw $s1, 100($s2)
sw $s1, 100($s2)
Meaning
$s1 = $s2 + $s3
$s1 = $s2 – $s3
$s1 = Memory[$s2+100]
Memory[$s2+100] = $s1
1998 Morgan Kaufmann Publishers
10
Machine Language
• Instructions, like registers and words of data, are also 32 bits
long.
• Example: add $t0, $s1, $s2
R-type instruction Format:
000000 10001
op
op
rs
rt
rd
shamt
funct
rs
10010
rt
01000
rd
00000
100000
shamt
funct
opcode, basic operation
1st source reg.
2nd source reg.
destination reg
shift amount (in shift instructions)
function, selects the specific variant
of the operation
1998 Morgan Kaufmann Publishers
11
Machine Language
• Introduce a new type of instruction format
– I-type for data transfer instructions
Example: lw $t0, 32($s2)
35
18
9
op
rs
rt
32
16 bit number
rt = destination register
address range =  215 B =  213 words
new instruction format but fields 1…3 are the same
• Design principle 3: Good design demands good
compromises
1998 Morgan Kaufmann Publishers
12
Stored Program Concept
• Instructions are groups of bits
• Programs are stored in memory
— to be read or written just like data
Processor
Memory
memory for data, programs,
compilers, editors, etc.
• Fetch & Execute Cycle
– Instructions are fetched and put into a special register
– Bits in the register "control" the subsequent actions
– Fetch the “next” instruction and continue
1998 Morgan Kaufmann Publishers
13
Control
• Decision making instructions
– alter the control flow,
– i.e., change the "next" instruction to be executed
• MIPS conditional branch instructions:
bne $t0, $t1, Label
beq $t0, $t1, Label
# branch if not equal
# branch if equal
• Example (if): if (i==j) h = i + j;
bne $s0, $s1, Label
add $s3, $s0, $s1
Label:
....
1998 Morgan Kaufmann Publishers
14
Control
• MIPS unconditional branch instructions:
j label
• Example (if - then - else):
if (i!=j)
h=i+j;
else
h=i-j;
beq $s4, $s5, Label1
add $s3, $s4, $s5
j Label2
Label1: sub $s3, $s4, $s5
Label2:
...
1998 Morgan Kaufmann Publishers
15
Control
• Example (loop):
Loop:
---i=i+j;
if(i!=h) go to Loop
---
• Loop: --add $s1, $s1, $s2 #i=i+j
bne $s1, $s3, Loop
---
1998 Morgan Kaufmann Publishers
16
So far:
•
•
•
Instruction
Meaning
add $s1,$s2,$s3
sub $s1,$s2,$s3
lw $s1,100($s2)
sw $s1,100($s2)
bne $s4,$s5,L
beq $s4,$s5,L
j Label
$s1 = $s2 + $s3
$s1 = $s2 – $s3
$s1 = Memory[$s2+100]
Memory[$s2+100] = $s1
Next instr. is at Label if $s4  $s5
Next instr. is at Label if $s4 = $s5
Next instr. is at Label
Formats:
R
op
rs
rt
rd
I
op
rs
rt
16 bit address
J
op
shamt
funct
26 bit address
the 16 b and 26 b addresses are word addresses
1998 Morgan Kaufmann Publishers
17
Control Flow
• We have: beq, bne, what about Branch-if-less-than?
• New instruction: set on less than
if $s1 < $s2 then
$t0 = 1
slt $t0, $s1, $s2
else
$t0 = 0
• slt and bne can be used to implement branch on less than
slt $t0, $s0, $s1
bne $t0, $zero, Less
• Note that the assembler needs a register to do this, there are
register conventions for the MIPS assembly language
• we can now build general control structures
1998 Morgan Kaufmann Publishers
18
MIPS Register Convention
Na m e
$zero
•
•
•
•
R e g is te r n u m b e r
0
Us a g e
the c o ns ta nt v a lue 0
$v0-$v1
2 -3
v a lue s fo r re s ults a nd e xpre s s io n e v a lua tio n
$a0-$a3
4 -7
a rgume nts
$t0-$t7
8 -1 5
$s0-$s7
1 6 -2 3
saved
$t8-$t9
2 4 -2 5
mo re te mpo ra rie s
te mpo ra rie s
$gp
28
glo ba l po inte r
$sp
29
s ta c k po inte r
$fp
30
fra me po inte r
$ra
31
re turn a ddre s s
$at, 1 reserved for assembler
$k0, $k1, 26-27 reserved for operating system
$t0…$t7, $t8, $t9 subroutine does not save
$s0…$s7 subroutine saves if uses
1998 Morgan Kaufmann Publishers
19
Procedure calls
• Procedures and subroutines allow reuse and structuring of
code
• Steps
– Place parameters in a place where the procedure can access
them
– Transfer control to the procedure
– Acquire the storage needed for the procedure
– Perform the desired task
– Place the results in a place where the calling program can
access them
– Return control to the point of origin
1998 Morgan Kaufmann Publishers
20
Register assignments for procedure calls
• $a0...$a3
• $v0...$v1
• $ra
four argument registers for passing parameters
two return value registers
return address register
• use of argument and return value register: compiler
• handling of control passing mechanism: machine
• jump and link instruction: jal ProcAddress
– saves return address (PC+4) in $ra (Program Counter
holds the address of the current instruction)
– loads ProcAddress in PC
• return jump:
jr $ra
– loads return address in PC
1998 Morgan Kaufmann Publishers
21
Stack
• Used if four argument registers and two return value registers
are not enough or if nested subroutines (a subroutine calls
another one) are used
• Can also contain temporary data
• The stack is a last-in-first-out structure in the memory
• Stack pointer ($sp) points at the top of the stack
• Push and pop instructions
• MIPS stack grows from higher addresses to lower addresses
1998 Morgan Kaufmann Publishers
22
Stack and Stack Pointer
elements
in the stack
bottom
elements
in the stack
SP
top
in
out
stack
grows
1998 Morgan Kaufmann Publishers
23
Constants
• Small constants are used quite frequently
e.g.,
A = A + 5;
B = B - 1;
• Solution 1: put constants in memory and load them
To add a constant to a register:
lw $t0, AddrConstant($zero)
add $sp,$sp,$t0
• Solution 2: to avoid extra instructions keep the constant
inside the instruction itself
addi $29, $29, 4
# i means immediate
slti $8, $18, 10
andi $29, $29, 6
• Design principle 4: Make the common case fast.
1998 Morgan Kaufmann Publishers
24
How about larger constants?
• We'd like to be able to load a 32 bit constant into a register
• Must use two instructions, new "load upper immediate"
instruction
lui $t0, 1010101010101010
1010101010101010
filled with zeros
0000000000000000
• Then must get the lower order bits right, i.e.,
ori $t0, $t0, 1010101010101010
ori
1010101010101010
0000000000000000
0000000000000000
1010101010101010
1010101010101010
1010101010101010
1998 Morgan Kaufmann Publishers
25
Overview of MIPS
• simple instructions all 32 bits wide
• very structured, no unnecessary baggage
• only three instruction formats
R
op
rs
rt
rd
I
op
rs
rt
16 bit address
J
op
shamt
funct
26 bit address
• rely on compiler to achieve performance
— what are the compiler's goals?
• help compiler where we can
1998 Morgan Kaufmann Publishers
26
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:
I
op
J
op
rs
rt
16 bit address
26 bit address
• Addresses are not 32 bits
1998 Morgan Kaufmann Publishers
27
Addresses in Branches
• Instructions:
bne $t4,$t5,Label
beq $t4,$t5,Label
Next instruction is at Label if $t4$t5
Next instruction is at Label if $t4=$t5
• Format:
I
op
rs
rt
16 bit address
• We need 32 bit addresses; use PC-relative addressing
– add the 16-bit address (2’s complement number) to the PC;
– most branches are local, so 16-bit offset or  215 word (
128 kB) address range is usually enough
1998 Morgan Kaufmann Publishers
28
Addresses in Jumps
• Instruction:
j Label
Next instruction is at Label
• Format:
J
op
26 bit address
• To get a 32 bit address the upper bits of the PC are
concatenated with the 26-bit address
• 226 word (256 MB) address range
• if range is not enough, use the jr instruction (not discussed in
detail)
jr Register
1998 Morgan Kaufmann Publishers
29
MIPS addressing mode summary
•
•
•
•
•
Register addressing
– operand in a register
Base or displacement addressing
– operand in the memory
– address is the sum of a register and a constant in the
instruction
Immediate addressing
– operand is a constant within the instruction
PC-relative addressing
– address is the sum of the PC and a constant in the
instruction
– used e.g. in branch instructions
Pseudodirect addressing
– jump address is the 26 bits of the instruction concatenated
with the upper bits of the PC
1998 Morgan Kaufmann Publishers
30
MIPS addressing mode summary
1. Im m e diate a d d re s sin g
op
rs
rt
Im m ed ia te
2. R eg is ter ad dr e ss in g
op
rs
rt
rd
. ..
fu nc t
R eg is te rs
R eg is te r
3. B as e a d dr es s in g
op
rs
rt
M emory
Ad dress
+
R e gister
B y te
H a lfw or d
W o rd
4. P C -re la tive a d d re ss in g
op
rs
rt
M emory
Ad dress
PC
+
W o rd
5. P se u d o dir e ct ad dr e s s in g
op
A d d re ss
PC
M emory
W o rd
1998 Morgan Kaufmann Publishers
31
Additional addressing modes
•
•
•
•
Direct addressing
– operand in the memory
– address in the instruction
Register indirect addressing
– operand in the memory
– address in a register
Implied addressing
– operand location specified by the operation code
Used in other computers
1998 Morgan Kaufmann Publishers
32
To summarize:
M IP S o p e ra n d s
Nam e
3 2 re g is te rs
2
30
E x a m p le
$s0-$s7, $t0-$t9, $zero,
F a s t lo c a tio n s fo r d a ta . In M IP S , d a ta m u s t b e in re g is te rs to p e rfo rm
$a0-$a3, $v0-$v1, $gp,
a rith m e tic . M IP S re g is te r $ z e ro a lw a y s e q u a ls 0 . R e g is te r $ a t is
$fp, $sp, $ra, $at
re s e rv e d fo r th e a s s e m b le r to h a n d le la rg e c o n s ta n ts .
M e m o ry [0 ],
A c c e s s e d o n ly b y d a ta tra n s fe r in s tru c tio n s . M IP S u s e s b y te a d d re s s e s , s o
m e m o ry M e m o ry [4 ], ...,
w o rd s
C o m m e n ts
s e q u e n tia l w o rd s d iffe r b y 4 . M e m o ry h o ld s d a ta s tru c tu re s , s u c h a s a rra y s ,
M e m o ry [4 2 9 4 9 6 7 2 9 2 ]
a n d s p ille d re g is te rs , s u c h a s th o s e s a v e d o n p ro c e d u re c a lls .
M IP S a s s e m b ly la n g u a g e
C a te g o ry
A rith m e tic
D a ta tra n s fe r
In s tru c tio n
add
E x a m p le
add $s1, $s2, $s3
M e a n in g
$s1 = $s2 + $s3
T h re e o p e ra n d s ; d a ta in re g is te rs
s u b tra c t
sub $s1, $s2, $s3
$s1 = $s2 - $s3
T h re e o p e ra n d s ; d a ta in re g is te rs
a d d im m e d ia te
addi $s1, $s2, 100
$s1 = $s2 + 100
U s e d to a d d c o n s ta n ts
lo a d w o rd
lw
$s1, 100($s2)
s to re w o rd
sw
$s1, 100($s2)
lo a d b y te
lb
$s1, 100($s2)
$ s 1 = M e m o ry [ $ s 2 + 1 0 0 ] W o rd fro m m e m o ry to re g is te r
W o rd fro m re g is te r to m e m o ry
M e m o ry [ $ s 2 + 1 0 0 ] = $ s 1
$ s 1 = M e m o ry [ $ s 2 + 1 0 0 ] B y te fro m m e m o ry to re g is te r
sb
$s1, 100($s2)
lo a d u p p e r im m e d ia te l u i $ s 1 , 1 0 0
s to re b y te
b ra n c h o n e q u a l
beq
$s1, $s2, 25
M e m o ry [ $ s 2 + 1 0 0 ] = $ s 1
$s1 = 100 * 2
16
if ( $ s 1 = = $ s 2 ) g o to
C o m m e n ts
B y te fro m re g is te r to m e m o ry
L o a d s c o n s ta n t in u p p e r 1 6 b its
E q u a l te s t; P C -re la tiv e b ra n c h
PC + 4 + 100
b ra n c h o n n o t e q u a l
bne
$s1, $s2, 25
N o t e q u a l te s t; P C -re la tiv e
PC + 4 + 100
C o n d itio n a l
b ra n c h
if ( $ s 1 ! = $ s 2 ) g o to
s e t o n le s s th a n
slt
s e t le s s th a n
slti
$s1, $s2, $s3
$s1, $s2, 100
im m e d ia te
if ( $ s 2 < $ s 3 ) $ s 1 = 1 ;
e ls e $ s 1 = 0
C o m p a re le s s th a n ; fo r b e q , b n e
if ( $ s 2 < 1 0 0 ) $ s 1 = 1 ;
e ls e $ s 1 = 0
C o m p a re le s s th a n c o n s ta n t
ju m p
j
2500
ju m p re g is te r
$ra
g o to 1 0 0 0 0
g o to $ r a
J u m p to ta rg e t a d d re s s
U n c o n d i-
jr
tio n a l ju m p
ju m p a n d lin k
jal
2500
$ r a = P C + 4 ; g o to 1 0 0 0 0
F o r p ro c e d u re c a ll
F o r s w itc h , p ro c e d u re re tu rn
1998 Morgan Kaufmann Publishers
33
Assembly Language vs. Machine Language
• Assembly provides convenient symbolic representation
– much easier than writing down numbers
– e.g., destination first
• Machine language is the underlying reality
– e.g., destination is no longer first
• Assembly can provide 'pseudoinstructions'
– e.g., “move $t0, $t1” exists only in Assembly
– would be implemented using “add $t0,$t1,$zero”
• When considering performance you should count real
instructions
1998 Morgan Kaufmann Publishers
34
Alternative Architectures
• Design alternative:
– provide more powerful operations than found in MIPS
– goal is to reduce number of instructions executed
– danger is a slower cycle time and/or a higher CPI
• Sometimes referred to as “RISC vs. CISC”
– Reduced Instruction Set Computers
– Complex Instruction Set Computers
– virtually all new instruction sets since 1982 have been
RISC
1998 Morgan Kaufmann Publishers
35
Reduced Instruction Set Computers
• Common characteristics of all RISCs
– Single cycle issue
– Small number of fixed length instruction formats
– Load/store architecture
– Large number of registers
• Additional characteristics of most RISCs
– Small number of instructions
– Small number of addressing modes
– Fast control unit
1998 Morgan Kaufmann Publishers
36
An alternative architecture: 80x86
• 1978: The Intel 8086 is announced (16 bit architecture)
• 1980: The 8087 floating point coprocessor is added
• 1982: The 80286 increases address space to 24 bits,
+instructions
• 1985: The 80386 extends to 32 bits, new addressing modes
• 1989-1995: The 80486, Pentium, Pentium Pro add a few
instructions (mostly designed for higher performance)
• 1997: MMX is added
1998 Morgan Kaufmann Publishers
37
An alternative architecture: 80x86
• Intel had a 16-bit microprocessor two years before its
competitors’ more elegant architectures which led to the
selection of the 8086 as the CPU for the IBM PC
• “This history illustrates the impact of the “golden handcuffs” of
compatibility”
“an architecture that is difficult to explain and impossible to love”
1998 Morgan Kaufmann Publishers
38
A dominant architecture: 80x86
• See your textbook for a more detailed description
• Complexity:
– Instructions from 1 to 17 bytes long
– one operand must act as both a source and destination
– one operand can come from memory
– complex addressing modes
e.g., “base or scaled index with 8 or 32 bit displacement”
• Saving grace:
– the most frequently used architectural components are not
too difficult to implement
– compilers avoid the portions of the architecture that are
slow
1998 Morgan Kaufmann Publishers
39
Summary
• Instruction complexity is only one variable
– lower instruction count vs. higher CPI / lower clock rate
• Design Principles:
– simplicity favours regularity
– smaller is faster
– good design demands good compromises
– make the common case fast
• Instruction set architecture
– a very important abstraction indeed!
1998 Morgan Kaufmann Publishers
40
Descargar

Lectures for 2nd Edition