Transcript powerpoint

9/29: Lecture Topics
•
•
•
•
Conditional branch instructions
Unconditional jump instructions
Hexadecimal/Binary/Decimal
Instruction encoding
1
Mailing List and Computer Labs
• CSE410 mailing list
– Subscribe if you weren’t automatically or
you use a different account
• Send email to [email protected]
with ‘subscribe cse410’ in the body
• Computer accounts
– MSCC Lab in basement of Communications
building
– Username =
passwd =
2
Conditional Branch
A change of the
flow of control of
the program that
depends on a
condition
...
...
?
yes
...
no
...
3
Control flow in C
• Conditional branch constructs:
– while, do while loops
– for loops
• Unconditional jump constructs:
– goto
– switch statements
4
Branching Instructions
• beq
• bne
• other real instructions: b, bgez, bgtz,
more...
• other pseudoinstructions: beqz, bge,
bgt, ble, blt, more...
5
Pseudoinstructions
• One-to-one mapping between assembly
and machine language not strictly true
• Assembler can do some of the work for
you
• Example: slt is a real instruction; blt
is a pseudoinstruction
• move is a pseudoinstruction
6
Labels in MIPS
• MIPS allows text tags
– a name for a place to branch to
loop:
add $t0, $t0, $t0
#
bne $t0, $t1, loop
#
sw
#
$t2, 0($t3)
• Under the covers, the assembler
converts the text tag into an address
7
Building a while loop in MIPS
Idea: translate
i=0;
while(i<100) {
i++;
}
into assembly.
8
How about a for loop?
• One answer: translate from for to while,
then use while loop conventions
for(i=0; i<N; i++) {
do_stuff(i);
}
i=0;
while(i<N) {
do_stuff(i);
i++;
}
• This is typically how compilers handle
loops
9
Example C Program
int array[100];
void main() {
int i;
for(i=0; i<100; i++)
array[i] = i;
}
10
An Assembly Version
main:
start:
exit:
move $t0, $0
#
la
$t1, array
#
bge
$t0, 100, exit #
sw
$t0, 0($t1)
#
addi $t0, $t0, 1
#
addi $t1, $t1, 4
#
j start
#
j $ra
#
11
Unconditional Jump
• (Mostly) the same as branch
• No choice about it; just go to the label
• How are branch and jump different?
– we’ll see when we get to instruction
encoding
12
Binary Numbers
• Instead of 0-9 we can only use 0 and 1
• Also known as base-2
• Counting to 10ten in binary 0, 1, 10, 11,
100, 101, 110, 111, 1000, 1001, 1010
• Binary arithmetic
1
1011
+1010
10101
11001001
- 1010110
13
Binary -> Decimal
• Converting from Base-2 to Base-10
12 = 20 = 110
102 = 21 = 210
1002 = 22 = 410
10002 = 23 = 810
11102 = 1*23 + 1*22 + 1*21 + 0*20
= 8+4+2+0 = 1410
1010112 =
14
Decimal -> Binary
• Repeatedly divide by 2 until you reach 0
• Reverse the order of the remainders
5010
50/2
25/2
12/2
6/2
3/2
1/2
7510
= 25 remainder 0
= 12 remainder 1
= 6 remainder 0
= 3 remainder 0
= 1 remainder 1
= 0 remainder 1
75/2
/2
/2
/2
/2
/2
/2
=
=
=
=
=
=
=
remainder
remainder
remainder
remainder
remainder
remainder
remainder
1100102
15
Hexadecimal Numbers
•
•
•
•
Instead of 0-9 we use 0-15
0-15 is confusing so we use 0-9, A-F
Also known as base-16
Counting to 18ten in hex 1, 2, 3, 4, 5, 6,
7, 8, 9, A, B, C, D, E, F, 10, 11, 12
• Hex arithmetic
1 1
2E97
+A2B3
D14A
A3AD38B993CA93C930B
-A3AD38B993CA93C930A
16
Hexadecimal <-> Binary
• Each four binary digits
represents one hexadecimal
digit
• Can quickly convert either way
– 0x2A07 = 0010 1010 0000 0111
– 1111 0011 0101 1011 =
00002
00012
00102
00112
01002
01012
01102
01112
10002
10012
10102
10112
11002
11012
11102
11112
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
016
116
216
316
416
516
616
716
816
916
A16
B16
C16
D16
E16
F16
17
Hexadecimal -> Decimal
• Converting from Base-16 to Base-10
116 = 160 = 110
1016 = 161 = 1610
10016 = 162 = 25610
100016 = 163 = 153610
A32 = A*161 + 3*160
= 10*161 + 3*160 = 160 + 3 = 163
18
Decimal -> Hexadecimal
• Repeatedly divide by 16 until you reach 0
• Reverse the order of the remainders
50010
500/16 = 31 remainder 4
31/16 = 1 remainder 15 (F)
1/16 = 0 remainder 1
1F416
19
What you need to know
• Be able to convert to/from small
decimal numbers from/to binary or hex
• Be able to/from convert any binary
number from/to a hex number
20
Stored Program
• So far, we’ve seen that data comes from
memory
• It turns out that the program comes
from memory also
• Each instruction in the program has an
address
• Von Neumann computer (p. 33)
21
Program Layout (p. 160)
Address
0
0x00400000
Reserved
Text
Program
instructions
Static data
Global variables
0x10000000
0x10008000
Dynamic data
and stack
0x7fffffff
22
The Text Segment
• Let’s zoom in on the text segment:
0x00400000
Text
0x10000000
0x00400000
add
$t0, $t1, $t2
0x00400004
sub
lw
$t0, $t0, $t3
$s1, 4($t0)
0x00400008
23
Jump Register
• Now we’re ready for the jr instruction
• Syntax:
jr
$t0
• Effect: jump to the instruction at the
address in $t0
24
Another Look at Labels
• Labels are text tags
loop:
add $t0, $t0, $t0
bne $t0, $t1, loop
sw
$t2, 0($t3)
• The assembler translates them into
addresses and does search-and-replace
25
Instruction Encoding
• How does the assembler translate each
instruction into bits?
add $t0, $s1, $s2
assembler
00000010001100100100000000100000
29
Fields
• Split the 32-bit instruction into fields:
32 bits
op
rs
rt
rd
shamt
funct
6 bits
5 bits
5 bits
5 bits
5 bits
6 bits
• op+funct: Which instruction?
• rs, rt: Register source operands
• rd: Register destination operand
30
Encoding an add instruction
• Let’s translate:
add $t0, $s1, $s2
•
•
•
•
•
Opcode for add is 000000 (p. A-55)
The funct for add is 100000
The code for $t0 is 01000 (p. A-23)
The code for $s1 is 10001
The code for $s2 is 10010
31
Instruction Formats
• The 32 bits can be split up more than
one way
• For add, it was 6-5-5-5-5-6
– This is called R-format
• For lw, we use 6-5-5-16 instead
– This is called I-format
32 bits
op
rs
rt
address
6 bits
5 bits
5 bits
16 bits
32
Translating into I-format
lw $t0, 100($t1)
• The opcode for lw is 100011
• The code for $t0 is 01000
• The code for $t1 is 01001
• Binary for 100 is
33
Branch vs. Jump
• Branch instructions use the I-format
– The destination address is 16 bits
– You can only branch ±32KB away
• Jump instructions use another format
called the J-format
– The destination address is 26 bits
– You can jump up to ±32MB away
• What’s the tradeoff?
34
What to Take Away
• I don’t care if you:
– Know how many bits are in each field
– Know what the opcodes are
– Know what the codes for the registers are
• I do care that you:
– Know what fields are
– Know why we need more than one
instruction format
35