2020 – Winter Term 2
Unit 1d – Static Control Flow
1
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
▪ Reading: Companion: 2.7.1-3, 2.7.5-6; Textbook: 3.6.1-5
▪ Learning Goals
▪ explain the role of the program counter register for normal execution and for branch and jump instructions
▪ compare the relative benefits of pc-relative and absolute addressing
▪ explain why condition branch instructions are necessary for an ISA to be “Turning Complete”
▪ translate a for loop that executes a static number of times into an equivalent, unrolled loop that contains no branch instructions
▪ translate a for loop into equivalent C code that uses only if-then and goto statements for control flow
▪ translate C code containing for loops into SM213 assembly language
▪ identify for loops in SM213 assembly language and describe their semantics by writing an equivalent C for loop
▪ translate an if-then-else statement into equivalent C code that uses only if-then and goto statements for flow control
▪ translate C code containing if-then-else statements into SM213 assembly language
▪ identify if-then-else statements in SM213 assembly language and describe their semantics by writing an equivalent C if-then- else statement
▪ explain why a procedure’s return address is a dynamic value
▪ translate the control-flow portion of a C static procedure call into SM213 assembly
▪ translate the control-flow portion of a C return statement into SM213 assembly
▪ identify procedure calls and returns in SM213 assembly language and describe their semantics by writing equivalent C procedure call and return statements.
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 2
▪Flow of control:
▪sequence of instruction executions performed by a program
▪Every program execution can be described by such a linear sequence
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 3
▪In Java:
public class Foo {
static int s = 0;
static int i;
static int a[] = new int[] {2,4,6,8,10,…,20}; static void foo() {
for (i = 0; i < 10; i++) s += a[i];
} }
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 4
▪In C:
int s = 0;
int i;
int a[] = {2,4,6,8,10,12,14,16,18,20}; void foo() {
for (i = 0; i < 10; i++)
s += a[i];
}
Alternative:
i < sizeof(a) / sizeof(a[0]);
(only works for arrays, not pointers)
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
5
▪Keep a pointer (instead of index) at current location: int s = 0;
int *p;
int a[] = {2,4,6,8,10,12,14,16,18,20}; void foo() {
p = a;
while (p < a + 10)
s += *p++; }
Would this be valid?
s = *a++;
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
6
▪Trade-off:
▪Pointers require less assembly indexed computation ▪Indexes (usually) make code easier to understand
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 7
▪Copying an array using array syntax: void intcpy(int *s, int *d, int n) {
for (int i = 0; i < n; i++)
d[i] = s[i];
}
▪Copying an array using pointer arithmetic: void intcpy(int *s, int *d, int n) {
while (n--)
*d++ = *s++;
}
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 8
int s = 0;
int i;
int a[] = {2,4,6,8,10,12,14,16,18,20}; void foo() {
for (i = 0; i < 10; i++) s += a[i];
}
▪Can we implement this loop with existing ISA?
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 9
Which of the following loops can we implement with our existing ISA?
(assume i is an int and n is a value provided by the user)
1. for (i = 0; i < 42; i++) 2. for (i = 42; i > 0; i–) 3. for (i = 0; i < n; i++) 4. for (i = 42; i > n; i–)
A. 1 and 3
B. 1 and 2
C. 3 and 4
D. 2 and 4
E. none of them
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
10
▪This code is equivalent (“unrolled” version): int s = 0;
int a[] = {2,4,6,8,10,12,14,16,18,20}; void foo() {
s += a[0]; s += a[1]; …
s += a[9];
}
▪Can we generalize this technique?
▪Unrolling only works if number of iterations is statically known
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 11
for (i = 0; i < 10; i++) s += a[i]; ▪Can also be translated to: i = 0; loop: goto end_loop if not (i<10) s += a[i]; i++; goto loop end_loop: CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 12 ▪Program counter (PC) ▪special CPU register that stores address of next instruction to execute ▪For sequential instructions, PC is updated in fetch ▪incremented by 2 or 6 depending on instruction size ▪So, to implement a goto, all we need is to change the PC CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 13 loop: goto end_loop if not (i<10) ▪New instruction: conditional jump ▪go to
if▪PC ← if
▪Options for evaluating condition
▪Unconditional (always jump)
▪Conditional based on register value ▪ common in RISC, used in SM213
▪Conditional based on result of last ALU instruction ▪used in Intel-based (x86/x86-64) architecture
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 14
▪Problem: memory addresses are big
▪so, instructions that go to specific address must be big ▪control-flow instruction are common
▪Jumps usually move a short distance (forward or backward) ▪e.g., loops, if statements
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 15
▪Solution: relative addressing
▪instead of specifying the address to jump, specify the offset from
current instruction
▪use current value of PC as base address ▪remember PC has already been updated in fetch
▪must be signed number (can jump backward) ▪jumps using relative address are called branches
▪Assembly still specifies actual address/label ▪converted to offset by assembler
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 16
1000: goto 1008 1002: …
1004: …
1006: …
1008: …
▪Option 1: absolute addressing (jump) X— 00001008
▪Option 2: relative addressing (branch) Y-03
PC after fetch is 1002, target is 1008,
so offset is 6
Since offset is always even,
we can divide by 2 17
Y-06
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
▪So, we need the following instructions: ▪at least one PC-relative jump (branch)
▪at least one absolute jump
▪some form of conditional jumps
▪make these relative (why?) ▪New instructions:
Name
Semantics
Assembly
Machine
branch
pc ← a (or pc+p*2)
br a
8-pp
branch if equal
pc ← a (or pc+p*2) if r[c] == 0
beq rc, a
9cpp
branch if greater
pc ← a (or pc+p*2) if r[c] > 0
bgt rc, a
acpp
jump
pc ← a
ja
b— aaaaaaaa
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 18
Convert the bgt instruction below to its machine code:
.pos 0x10
bgt r0, L1 .pos 0x20
L1: halt
A. 0xa0 0x10 B. 0xa0 0x08 C. 0xa0 0x0e D. 0xa0 0x07 E. 0xa0 0x20
Name
Semantics
Assembly
Machine
branch if greater
pc ← a (or pc+p*2) if r[c] > 0
bgt rc, a
acpp
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
19
Convert the br instruction below to its machine code.
(note: each instruction here is 2 bytes)
loop: mov r0, r5 add r4, r5
beq r5, end_loop inc r0
br loop
A. 0x80 0xf5 B. 0x80 0xf8 C. 0x80 0xfc D. 0x80 0xfb E. 0xa0 0xf6
Name
Semantics
Assembly
Machine
branch
pc ← a (or pc+p*2)
br a
8-pp
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
20
What does the following instruction do?
0xa0 0x00
A. infinite loop
B. sets PC to zero
C. sets PC to beginning of program
D. nothing
E. something else
Name
Semantics
Assembly
Machine
branch if greater
pc ← a (or pc+p*2) if r[c] > 0
bgt rc, a
acpp
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
21
loop:
i = 0;
goto end_loop if n i
s += a[i]; i++;
goto loop
o
–
10
=
) 0
t
(i
<
10
=
r0
Value of i
r1
Address of a
r2
Value of s
r3
Value of a[i]
r4
Constant: -10
r5
i-10
end_loop:
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
22
i = 0;
loop: goto end_loop if not (i<10)
s += a[i]; i++;
goto loop
end_loop:
ld $0, r0 ld $a, r1 ld $s, r2 ld (r2), r2 ld $-10, r4
loop: mov r0, r5 add r4, r5
beq r5, end_loop
ld (r1, r0, 4), r3 add r3, r2
inc r0
br loop
end_loop: ld $s, r1 st r2, (r1)
st r0, 4(r1) 23
r0
Value of i
r1
Address of a
r2
Value of s
r3
Value of a[i]
r4
Constant: -10
r5
i-10
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
▪In Java or C:
if (
▪Pseudo-code using goto: c = not
goto then if (c == 0)
else:
goto end_if
then:
if (a > b)
max = a;
else
max = b;
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 24
ld $a, r0
ld (r0), r0
ld $b, r1
ld (r1), r1
mov r1, r2
not r2
inc r2 then:
r0
Value of a
r1
Value of b
r2
a-b
r3
max
add r0, r2
bgt r2, then
end_if:
else:
mov r1, r3
br end_if
mov r0, r3 ld $max, r0 st r3, (r0)
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
25
What does this code do?
ld $a,r0
ld (r0), r0 L0: deca r0
bgt r0, L0 ld $b, r1 st r0, (r1)
A.b=a–4;
B. b = a % 4; C.b = 0;
D. Loops forever E. Something else
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
26
.pos 0x1000
ld $0, r0
ld $0, r1 ld $1, r2 ld $j, r3 ld (r3), r3 ld $a, r4
L1: inc r0
dec r3
br L0
L9: ld $o, r0
st r1, (r0)
halt
.pos 0x2000 j: .long 2 a: .long 1
.long 2 o: .long 0
r3, L9
L0: beq
ld (r4, r0, 4), r5 and r2, r5
beq r5, L1
inc r1
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder
27
▪In C:
void ping () {} void foo () {
ping (); }
▪Procedure/function: subroutine with a name, arguments and local scope
▪Term “function” usually restricted to the ones with return value
▪Procedure call: causes the procedure to run with: ▪Values bound to arguments
▪Possible result bound to the invocation
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 28
▪In Java:
public class A {
public static void ping () {}
}
public class Foo {
public static void foo () {
A.ping (); }
}
▪Method: subroutine with a name, arguments and local scope
▪Method invocation: causes the method to run with: ▪ Values bound to arguments
▪ Possible result bound to the invocation
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 29
void foo () { ping();
}
▪Caller: goto ping (jump) ▪Caller: continue executing
void ping () {}
▪Question: return is a jump, but to where? ▪Static or dynamic?
▪Callee: do whatever ping does ▪Callee: return to ???
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 30
▪Return address is:
▪The address the procedure jumps to when it completes
▪The address of the instruction following the call that caused the run
▪A dynamic property of the program
▪A function may be called from different locations
▪Questions
▪How does the procedure know the return address? ▪How does it jump to a dynamic address?
▪How are recursive calls handled?
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 31
▪Only the caller knows the address
▪So the caller must save it before it makes the call
▪Convention: caller will save the return address in r[6] ▪ There is a problem here, more on this later
▪We need a new instruction to read the PC ▪We’ll call itgpc
▪Jumping back to return address
▪We need a new instruction to jump to dynamic address ▪Callee assumes caller saved address in r[6]
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 32
▪New requirements:
▪Read the value of PC
▪Jump to a dynamically determined target address
▪New instructions:
Name
Semantics
Assembly
Machine
branch
pc ← a (or pc+p*2)
br a
8-pp
branch if equal
pc ← a (or pc+p*2) if r[c] == 0
beq rc, a
9cpp
branch if greater
pc ← a (or pc+p*2) if r[c] > 0
bgt rc, a
acpp
jump
pc ←a
ja
b— aaaaaaaa
get pc
r[d] ← pc + o (or pc+p*2)
gpc $o, rd
6fpd
indirect jump
pc ← r[t] + o (or r[t]+p*2)
j o(rt)
ctpp
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 33
void foo () { ping();
void ping () {}
}
foo: gpc $6, r6
j ping
…
ping: …
j (r6)
# r6 = pc of instruction after jump
# goto ping
# return
CPSC 213 2020 ST1 © 2020 Jonatan Schroeder 34