Transcript Data Structures and Flow Control

Flow Control
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 1
Flow Control: Goals
• Branching
– Condition code register
– Branch instructions
• Conditional branches
• Unconditional branches
• Know how to implement:
– For loops
– While loops
– if/then/else statements
• Assigned Reading:
– HVZ: 3.11 Program Flow Control
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 2
Flow Control: The Condition Code Register
• The Condition Code Register (CCR) holds
information about the result of the most recently
executed arithmetic instruction.
• There are five bits that are set by the ALU.
–
–
–
–
N – 1 if the last result was Negative
Z – 1 if the last result was Zero
V – 1 if the last operation resulted in arithmetic overflow
C – 1 if the last operation produced a carry
• addition – 1 if there was a carry out from most significant bit
• subtraction – 1 if there was a borrow required
– X – special operand for multiprecision computations. We
won’t be using this bit.
ALU
…NZVC…
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 3
Table C.5
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 4
Table C.4
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 5
Flow Control: Branch Instructions
• The mnemonics for the branch instructions
assume that you are following a SUB or a
CMP instruction:
– BEQ (branch when equal) Z=1
SUB.W
BEQ
D3,D4
LOOP
– when does Z=1?
• When [D3] and [D4] are equal!
• Remember that CMP and SUB compute
[dest] – [src]
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 6
CMP & Bcc instructions
• CMP Operations performed: [d] – [s]
– Result doesn’t go anywhere! Why?
• Bcc represents many instructions:
–
–
–
–
–
–
BEQ – branch when equal (Z=1)
BNE – branch when not equal (Z=0)
BVS – branch when overflow set (V=1)
BPL – branch when result positive (N=0)
BRA – always branch
See table C.6
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 7
Flow Control: Conditional Branch Instructions - Bcc
• CMP src, dest
–
–
–
–
BEQ – Branch to TARGET if src = dest
BNE – Branch to TARGET if src != dest
BLT – Branch to TARGET if dest is less than src
BLE – Branch to TARGET if dest is less than or
equal to src
– BGT – Branch to TARGET if dest is greater than
src
– BGE – Branch to TARGET if dest is greater than
or equal to src
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 8
Flow Control: Bcc
• You can also think of Bcc as comparing the
result of the last operation to zero:
LOOP
ARRAY
MOVE.W
LEA
ADD.W
ADDQ.W
BLT
DC.W
#-3,D0
ARRAY,A0
(A0)+,D1
#1,D0
LOOP
12,4,8
; D0 is a counter, starting
; … at the value -12
;Add 1 to the counter
;Loop while result < 0
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 9
Flow Control: for loops
• for(i=0; i<5; i++) {…}
LOOP
CLR.B
…
ADDQ.B
CMPI.B
BLT
D0
#1,D0
#5,D0
LOOP
This is easy to read,
and necessary if
you want to use the
value of i.
D0 - #5
However, you have to get the immediate value #5 from memory
repeatedly. There is a more efficient way to loop 5 times…
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 10
Flow Control: Fixed loops
• Using a down counter. A more efficient way
to loop 5 times:
MOVEI.B
LOOP
#5,D0
do something…
SUBQ.B
#1,D0
BNE
LOOP ;
move on…
CEG 320/520: Computer Organization and Assembly Language Programming
BRA if Z=0
Flow Control 11
Flow Control: while loops
• while (j < 5) {…} Test at beginning.
• condition: (j < 5) opposite: (j  5)
MOVE.W
LOOP CMPI.W
BGE
…
ADDQ
BRA
NEXT …
j
DC.W
j,D0 ;get j from memory
#5,D0
NEXT ; exit loop if
; condition false
#1,D0
LOOP
2
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 12
Flow Control: Other ways to use branch
• You don’t have to follow the mnemonics
• The best thing to do is to look at the branch
condition in Table C.6
• EXAMPLE: for(j=-5; j!=0; j++){…}
LOOP
DONE
MOVE.B
#-5,D0
BEQ
DONE
do something…
ADDQ.B
#1,D0
BRA
LOOP
move on…
CEG 320/520: Computer Organization and Assembly Language Programming
We’ll use D0 for j
BRA if Z=1
BRA doesn’t
affect the CCR
Flow Control 13
Flow Control: Conditionals
• if (x == 5) {…}
• The most efficient way to code this is to skip
the code {…} if the condition is not true.
SKIP
MOVE.W x,D2
CMPI.W #5,D2
BNE
SKIP
…
; {…}
…
next instruction…
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 14
Flow Control: If…then…else
• if (y > 3)
{
true-code
}
else
{
false-code
};
MOVE.W
Y,D0
CMPI.W
#3,D0
BLE
ELSE
true-code
BRA
NEXT
ELSE false-code
NEXT next-instruction
Again we test for the opposite of the if condition, and skip the
true-code if necessary. At the end of the true-code, we use a
BRA to avoid also executing the false code.
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 15
Example – Adding n integers
MOVE.W N,D1
MOVE.W #NUM,A2
CLR.W
D0
LOOP ADD.W
(A2)+,D0
SUB.W
#1,D1
BGT
LOOP
MOVE.W D0,SUM
END
ORG $001000
N
DC.W
7
NUM DC.W 3,5,8,10,5,12,14
SUM
DS 1
CEG 320/520: Computer Organization and Assembly Language Programming
MEMORY
$1000
$1002
$1004
$1006
$1008
$100A
$100C
$100E
$1010
7
3
5
8
10
5
12
14
?
N
NUM
SUM
Flow Control 16
Branches and Overflow
• In the 68000 the V bit is set on 2’s complement
overflow for the operand size (B, W, L)
– BGE (branch when greater or equal)
• Branch when NV = 0
– Example: SUB.B D1, D2 (DEST – SRC)
• N=0 when D2  D1
• What if [D1] = 1, and [D2] = –128?
• Can we represent –129 in an 8-bit byte in 2’s
complement?
(10000000 + 11111111)
• The result is 127 (positive), N=0, V=1
• We don’t branch, which is good since –128 < 1 !
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 17
Operation sizes and Overflow
• In the 68000, the V-bit is set when there is a
2’s complement overflow for the size of
operand specified in the instruction!
• In other words, suppose D0 = $00000063
– ADD.B #$60,D0 sets V=1 and N=1
– ADD.W #$60,D0 sets V=0 and N=0
• Same thing goes for the carry bit
– If a byte operation would produce a carry into bit
8, the C bit is set, and bit 8 retains its old value.
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 18
Machine Code: Branches
• 0110 CCCC PPPP PPPP or
0110 CCCC 0000 0000
PPPP PPPP PPPP PPPP
• Displacement can be an 8-bit or 16-bit value.
– Determined by assembler
– Dependent on the size of the jump
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 19
Machine Code: Branches - example
LOOP
ADD.W
SUB.W
BGE
D2,D3
NUM, D1
LOOP
1 word
3 words
1 word
• Assuming LOOP is at address 1000, then the
PC contains 1008 after fetching the BGE
instruction, so the offset is –10 or $F6
• The entire instruction is:
0110 1100 1111 0110
= $6CF6
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 20
Putting it together: Summing an array
ORG
$1000
CLR.W
D3
MOVEA.L
LOOP
#NUMS,A1
; The sum will go into D3
; A1 -> current array element
MOVE.W
LEN,D2
; D2 = number of array elements remaining
ADD.W
(A1)+,D3
; Add the next element
SUBQ.W
#1,D2
; Now there is one less remaining
BNE
LOOP
; Continue if D2 != 0
MOVE.B
#EXIT,D7
;
TRAP
#14
; Exit back to the simulator
EQU
228
LEN
DC.W
5
; LEN = Size of the array
NUMS
DC.W
123,-56,453,-1045,765
; NUMS = the array
;
EXIT
;
End
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 21
Flow Control: In-Class Exercises
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 22
Did you know?
• You can give C a “hint” about which variables
to keep in registers?
register int counter;
int i, j;
counter = 0;
for (i=0; i<100; i++) {
for (j=0; j<100; j++) {
counter += 3;
}
}
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 23
Flow Control: You Should Know…
• Review
– Condition code register
– LEA instructions
– Branch instructions
• Know how to implement:
–
–
–
–
For loops
While loops
if/then/else statements
Unconditional branches
• Next Topic:
– The Stack and Subroutines
– HVZ: 3.13 Stacks and Subroutines
CEG 320/520: Computer Organization and Assembly Language Programming
Flow Control 24