Transcript Ch2a

Chapter 2
Instructions:
•
•
Language of the Machine
We’ll be working with the MIPS instruction set architecture
– MIPS (originally an acronym for Microprocessor without Interlocked Pipeline Stages)
is a RISC microprocessor architecture developed by MIPS Technologies. By the late
1990s it was estimated that one in three RISC chips produced were MIPS-based
designs
– MIPS :It presently stands for million instructions per second
– similar to other architectures developed since the 1980's
– Almost 100 million MIPS processors manufactured in 2002
– used by NEC, Nintendo, Cisco, Silicon Graphics, Sony, …
MIPS arithmetic
•
•
All instructions have 3 operands
Operand order is fixed (destination first)
Example:
C code:
a = b + c
MIPS ‘code’:
add a, b, c
“The natural number of operands for an operation like addition is
three…requiring every instruction to have exactly three operands,
no more and no less, conforms to the philosophy of keeping the
hardware simple”
4 Design Principles
Design Principle 1:
Design Principle 2:
Design Principle 3:
Design Principle 4:
compromises.
Simplicity favors regularity.
Smaller is faster.
Make the common case fast.
Good design demands good
MIPS arithmetic
•
•
Design Principle: Simplicity favors regularity.
Of course this complicates some things...
C code:
a = b + c + d + e;
MIPS code:
add a, b, c
add a, a, d
add a, a, e
•
Eg.1.
•
Eg.2.
•
•
Operands must be registers, only 32 registers provided
Each register contains 32 bits.
a = b + c;
d=a–e;
Show the MIPS code produced by the compiler
f = (g + h) - ( i + j);
Design Principle: smaller is faster.
Why?
Registers
•
•
•
•
•
•
MIPS convention is to use two character names following a dollar sign to
represent a register.
Temporary registers
– $t0 thru $t7 correspond to registers 8-15
Registers for holding variables
– $s0 thru $s7 correspond to registers 16-23
Constant 0
– $zero used for the constant 0
– Also corresponds to register 0
It is the compiler’s job to associate program variables with registers.
Eg. F =(g + h) – (i +j ); the variables f,g,h,I,j are assigned to the registers
$s0,$s1,$s2,$s3,$s4 respectively. What is the complied MIPS code?
Registers vs. Memory
•
•
•
Arithmetic instructions operands MUST be registers,
— only 32 registers provided
Compiler associates variables with registers
What about programs with lots of variables
Control
Input
Memory
Datapath
Processor
Output
I/O
Memory Organization
•
•
•
•
•
Viewed as a large, single-dimension array, with an address.
A memory address is an index into the array
Assume that A is an array of 100 words, the compiler has associated the variables
g and h with the registers $s1 and $s2 as before. The base address of the array is
in $s3. Compile the C assignment statement
g = h + A[8];
The data transfer instruction that copies data from memory to a register is called
“load”.
"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
Instructions
•
•
•
Load and store instructions
Example:
C code:
A[12] = h + A[8];
MIPS code:
lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 48($s3)
Remember arithmetic operands are registers, not memory!
Can’t write:
add 48($s3), $s2, 32($s3)
Constants
•
•
•
Small constants are used quite frequently (50% of operands)
e.g.,
A = A + 5;
B = B + 1;
C = C - 18;
Solutions? Why not?
– put 'typical constants' in memory and load them.
– create hard-wired registers (like $zero) for constants like zero.
MIPS Instructions:
addi $s3, $s3, 4
•
•
# $s3 = $s3 + 4
Design Principle: Make the common case fast.
Constant operands occur frequently, and by including constants
inside arithmetic instructions, they are much faster than if constants
were loaded from memory.
Machine Language
•
Instructions, like registers, are also 32 bits long
– Example: add $t1, $s1, $s2
– registers have numbers, $t1=9, $s1=17, $s2=18
•
Instruction Format:
R-type (Register format)
000000 10001 10010
op
•
rs
rt
01000
rd
00000
100000
shamt
funct
Can you guess what the field names stand for?
Machine Language
•
•
•
Consider the load-word and store-word instructions,
– What would the regularity principle have us do?
– A conflict between the desire to keep all instructions the same length
and the desire to have a single instruction format.
– New principle: Good design demands a compromise
Introduce a new type of instruction format
– I-type for data transfer instructions
– other format was R-type for register
Example: lw $t0, 32($s2)
35
18
9
32
op
•
rs
rt
16 bit number
Although multiple formats complicate the hardware, we can reduce the
complexity by keeping the formats similar. Formats are distinguished by
the values in the first field.
Translating MIPS Assembly Level
Language into machine language
•
Eg. If $t1 has the base of the array A and $s2 corresponds to h,
Compile into MIPS code. What is the machine language code for these
instructions corresponding to the assignment statement
A[300] = h + A[300];
Logical Operations
•
Shift left logical(sll) and shift right logical(srl)
•
Example
Sll $t2, $s0, 4
•
R-format
0
•
•
# $t2 = $s0 << 4 bits
0
16
10
4
Shifting left corresponds to what arithmetic operation?
Shifting right corresponds to what arithmetic operation?
0
Logical Operations
•
•
AND
and $t0, $t2, $t1
# $t0 = $t2 AND $t1
or $t0, $t2, $t1
# $t0 = $t2 OR $t1
OR
•
NOT
– Implemented with NOR with one operand 0 (why?)
nor $t0, $t2, 0
# $t0 = NOT ($t2)
•
Also have immediate versions
andi $t0, $t1, 0
ori $t0, $t1, 0
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
•
Example:
if (i==j) h = i + j;
bne $s0, $s1, Label
add $s3, $s0, $s1
Label: ....
Control
•
•
MIPS unconditional branch instructions:
j label
Example:
if (i!=j)
h=i+j;
else
h=i-j;
beq $s4, $s5, L1
add $s3, $s4, $s5
j L2
L1:
sub $s3, $s4, $s5
L2:
...
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
26 bit address
funct