Transcript chapter2part2

CS/COE0447
Computer Organization & Assembly
Language
Chapter 2 Part 2
1
Topics
• More types of instructions
– Translation into machine code
– How they work (execution)
– Understanding the technical documentation (green card)
• Immediate values
– Sign and Zero extension of immediates
– Loading large immediate values into registers, which leads us to pseudo
instructions (source versus basic in MARS)
• Addressing: bytes, half-words, words, and alignment Ask
any remaining questions from Lab 2
• Algorithms in assembly language: arrays, loops, ifstatements (presented through example code).
• Assembly and execution of branch and jump instructions
2
Example: LUI, ANDI and ORI
lui $t1, 0x7F40 # load 0x7F400000 into $t1
#lui is load upper immediate
#upper: upper 2 bytes (4 hex digits; 16 bits)
#immediate: part of the instruction
addi $t2, $t1, 0x777
andi $t3, $t2, 0x5555 # bitwise and
ori $t4,$t2,0x5555
# bitwise or
Trace in lecture
3
Documentation [greencard]: LUI, ANDI, ORI
lui
I
andi I
ori
I
R[rt] = {imm,16’b0}
R[rt] = R[rs] & ZeroExtImm
R[rt] = R[rs] | ZeroExtImm
(3)
(3)
f_hex
c_hex
d_hex
(3) ZeroExtImm = {16{1’b0},immediate}
In Verilog: 16‘b1
1’b0
{a,b}
3{a}
{3{a},b}
// 16 bits, with binary value 1
// 1 bit, which is 0
// ab
// aaa
// aaab
In lecture: machine code
understand the green card info above
4
Shift Instructions
Name
R-format
Fields
op
NOT
USED
rt
Comments
rd
shamt
funct
shamt is “shift amount”
• Bit-wise logic operations
• <op> <rdestination> <rsource> <shamt>
• Examples
– sll $t0, $s0, 4
– srl $s0, $t0, 2
# $t0 = $s0 << 4
# $s0 = $t0 >> 2
• These are the only shift instructions in the core instruction set
5
Shift Instructions
• Variations in the full MIPS-32 instruction set (see pp. 279-282):
– Shift amount can be in a register (“shamt” field not used)
• sllv, srlv, srav
– Shift right arithmetic (SRA) keeps the sign of a number
• sra $s0, $t0, 4
• Pseudo instructions:
– Rotate right/left: ror, rol
• The point: lots of possible variations in shift instructions.
6
Example of Shifts
.text
li $t0,0x77
li $t2,3
sll $t0,$t0,3
srl $t2,$t2,2
$t0 = 0000 0000 0000 0000 0000 0000 0111 0111 000
$t2 = 00 0000 0000 0000 0000 0000 0000 0000 0011
So, $t0 becomes 0x000003b8
$t2 becomes 0x00000000
7
Puzzle: How we do we load a 32 bit immediate
value into a register using core IS?
• Suppose we want to load 0x76B52134 into $t0
• What instruction will do this?
• lw? Nope: lw loads a value from memory, e.g.,
– lw $t0,4($t2) loads the word at M[4+$t2] into $t0
• lbu? Nope: lbu also loads a value from memory, e.g.,
– lbu $t0,4($t2) loads the byte at M[4+$t2] padded to left with 24 0s
• lhu? Nope: lhu also loads a value from memory, e.g.,
– lhu $t0,4($t2) loads the 16 bits at M[4+$t2] padded to left with 16 0s
• lui? Nope:
– lui $t0,0x7F40 loads a 16-bit immediate value followed by 16 0s
• That’s all the load instructions in the core instruction
set!
8
Puzzle: How we do we load a 32 bit
immediate value into a register?
• Let’s try defining an instruction:
•
li $t0, 0x76B52134
• We need to choose an instruction format
– R: op (6) rs (5) rt (5) rd (5) shmt (5) funct(6)
– I: op(6), rs (5), rt (5), imm (16)
– J: op(6), address (26)
• MIPS: a key design decision is that all
instructions are 32 bits. This is not true for
many other ISAs
• How will we fit a 32-bit immediate value into
an instruction?
9
Puzzle: how will we fit a 32-bit immediate
value into an instruction?
• We can’t! Recall, we want: 0x76b52134  $t0
• li $t0,0x76b52134 is translated into 2 instructions [“li” is a
pseudo instruction; not implemented in the hardware]
• lui $at, 0x76b5
$at
0111011010110101
0000000000000000
• ori $t0, $at, 0x2134
$t0
0111011010110101
0010000100110100
• There’s a tradeoff between simplicity of instructions and
the number of instructions needed to do something
10
• MIPS is RISC: reduced instruction set computer
Loading 32-bit immediate value into
registers
• Recall, we want: 0x76b52134  $t0
Basic
Source
lui $1, 30389
li $t0, 0x76b52134
ori $8, $1, 8500
In Mars.jar, after you assemble the code
11
Loading addresses into registers
• .data places values in memory starting at 0x10010000.
So, 32 bits are needed to specify memory addresses.
• 1 instruction is impossible: the address would take up
the entire instruction!
• Use another pseudo instruction called la
Basic
lui $1, 4097
ori $8, $1, 8
Source
la $t0, 0x10010008
In Mars.jar, after you assemble the code
12
Quick Exercise
• Appendix B-57 (in text in 4th edition):
load immediate
li rdest, imm e.g., li $t0,0xffffffff
“Move the immediate imm into register rdest”
• What type of instruction is this? E.g., is this
an R-format instruction? Perhaps an I-format
one? … Please explain.
13
Quick Exercise Answer
• “li” is a pseudo instruction. The instruction
is translated by the assembler into two
instructions in the actual machine code that
is executed by the computer.
• We saw an example on slide 11
14
Addresses Specify Byte Locations
– Addresses are aligned:
addresses are multiples of X,
where X is the number of
bytes. [practice in a lab]
– word (4 bytes) addresses are
multiples of 4; half-word (2
bytes) addresses are
multiples of 2
Half
32-bit
Words Words
0000
Addr
=
0000
??
0002
0004
Addr
=
0004
??
0006
0008
– In lecture: what this looks
like in Mars.
Addr
=
0008
??
000A
000C
Addr
=
000C
??
000E
Bytes Addr.
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
000A
000B
000C
000D
000E
000F
15
Memory Transfer Instructions
• Review: To load/store a word from/to memory:
– LOAD: move data from memory to register
• lw $t3, 4($t2)
# $t3  M[$t2 + 4]
– STORE: move data from register to memory
• sw $t4, 16($t1) # M[$t1 + 16]  $t4
• Support for other data types than 32-bit word is needed
– 16-bit half-word
• “short” type in C
• 16-bit processing is common in signal processing
• lhu and sh in MIPS
– 8-bit byte
• “char” type in C
• 8-bit processing is common in controller applications
• lbu and sb
16
Byte Ordering
• How should bytes within multi-byte words be ordered in
memory?
• Conventions
.data
.word 3 (0x00000003; 03 is the least significant byte)
– “Big Endian” machines
• Least significant byte has highest address
• 03 would be in 10010003
– “Little Endian” machines
• Least significant byte has lowest address
• 03 would be in 10010000
– MIPS can be either; MARS is little-endian
17
.data
b2: .byte 2,3
b3: .byte 4
.align 2
b4:
.word 5,6,7
.text
la $t0,b2
lbu $t2,0($t0)
lbu $t2,1($t0)
lbu $t2,2($t0)
lbu $t2,3($t0)
lbu $t2,4($t0)
#
#
#
#
#
$t2
$t2
$t2
$t2
$t2
=
=
=
=
=
0x00000002
0x00000003
0x00000004
0x00000000 (nothing was stored here)
0x00000005
18
Procedure Example
$a0: pointer to array
$a1: k
void swap(int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
swap:
sll
add
lw
lw
sw
sw
jr
$t0, $a1, 2
$t1, $a0, $t0
$t3, 0($t1)
$t4, 4($t1)
$t4, 0($t1)
$t3, 4($t1)
$ra
19
Control
• In any typical computer (Von Neumann
architecture) you have 2 options for control
– Proceed to the next instruction, or
– Go to another instruction
• beq $t0,$zero,label1
• # if $t0 == zero, then goto label1
• Why? The next instruction executed is the one
whose address is in the program counter (PC).
The PC can be
– Incremented to point to the next instruction, or
– Updated to include the address of another instruction
20
Implementing a for-loop
for (i = 0; i < n; i++)
<body>
<next instruction>
Same as:
i = 0;
loop: if (i < n) {
<body>;
i = i + 1;
goto loop; }
<next instruction>
Let’s focus on “if i < n:” …
21
Implementing a for-loop
loop: if (i < n) {
<body>;
i = i + 1;
goto loop; }
<next instruction>
How is “if i < n” implemented in assembly language/
machine code? Do we test i < n?
22
Implementing a for-loop
loop: if (i < n) {
<body>;
i = i + 1;
goto loop; }
<next instruction>
•How is “if i < n” implemented in assembly language/
machine code? Do we test i < n?
•Nope. if i < n becomes:
If i >= n: go to <next instruction>
•Similar for while loops, if-statements, and so on.
High-level languages specify conditions for doing
something. Machine code specifies the opposite:
conditions for not doing something, by going
somewhere else
23
If Statement Example
Suppose: $s0 is i
$s1 is h
$s3 is j
if (i == h) h =i+j;
YES
NO
bne $s0, $s1, LABEL
add $s1, $s0, $s3
LABEL: …
(i == h)?
h=i+j;
LABEL:
24
If Then Else Example
i ~ $s4; h ~ $s5; f ~ $s3; g ~ $s2
if (i == h) f=g+h;
else f=g–h;
YES
NO
bne $s4, $s5, ELSE
add $s3, $s2, $s5
j EXIT
ELSE: sub $s3, $s2, $s5
EXIT: …
(i == h)?
f=g+h;
f=g–h
EXIT
25
# sum = 0
# for (i = 0; i < n; i++)
#
sum += i
addi $s0,$zero,0
# $s0 sum = 0
addi $s1,$zero,5
# $s1 n = 5; arbitrary value
addi $t0,$zero,0
# $t0 i = 0
loop:
slt $t1,$t0,$s1
# i < n?
beq $t1,$zero,exitloop # if not, exit
add $s0,$s0,$t0
# sum += i
addi $t0,$t0,1
# i++
j loop
exitloop:
add $v0,$zero,$s0
# $v0 has the sum
26
Same as previous version, but uses bge pseudo
instruction rather than the slt + beq instructions
# sum = 0
# for (i = 0; i < n; i++)
#
sum += i
addi $s0,$zero,0 # $s0 sum = 0
addi $s1,$zero,5 # $s1 n = 5; a random value
addi $t0,$zero,0 # $t0 i = 0
loop:
bge $t0,$s1,exitloop # i < n? PSEUDO INSTRUCTION!
# if $t0 >= $s1, jump to exitloop
add $s0,$s0,$t0 # sum += i
addi $t0,$t0,1
# i++
j loop
exitloop:
add $v0,$zero,$s0 # $v0 has the sum
27
Instruction Format for Branches
I format
op
rs
rt
16-bit immediate
• Address in the instruction is not a 32-bit number – it’s only 16 bits
– The 16-bit immediate value is in signed, 2’s complement form
• Addressing in branch instructions:
• The 16-bit number in the instruction specifies the number of
instructions away
• Next address = PC + 4 + sign_extend(16-bit immediate << 2)
• Why <<2? Specifying number of words, not bytes
28
0x00400024
bne $t0,$s5,exitloop
0x00400028
addi $s3,$s3,1
0x0040002c
j loop
0x00400030
exitloop: add $s6,$s3,$zero
BNE machine code in binary:
000101 01000 10101 0000000000000010
BNE machine code in hex: 15150002
When BNE instruction is executed:
Next address = PC + 4 + sign_extend(16-bit immediate << 2)
Next address = 00400024 + 4 + 00000008
= 00400030 address of the exitloop instruction
29
Instruction Format for Jumps
Jump
op
26-bit immediate
• The address of next instruction is obtained by concatenating with PC
PC = {PC[31:28],IMM[25:0],00}
30
0x00400018
0x0040001c
0x00400020
ELSE:
0x00400024
0x00400028
0x0040002c
bne $s4, $s5, ELSE
add $s3, $s2, $s5
j EXIT
sub $s3, $s2, $s5
addi $s5, $s5, 1
EXIT: addi $s4,$s4,1
j instruction machine code: 0x0810000b. Look at execution:
PC = {PC[31:28],IMM[25:0],00}
PC[31:28] = 0000
IMM = 00 0001 0000 0000 0000 0000 1011
{0000, IMM, 00} =
0000 00 0001 0000 0000 0000 0000 1011 00 BIN
0
0
4
0
0
0
2
c
HEX
The address EXIT stands for!
31