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 procedures 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 4In 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 Schroeder5Keep 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 Schroeder6Trade-off:Pointers require less assembly indexed computation Indexes (usually) make code easier to understand CPSC 213 2020 ST1 2020 Jonatan Schroeder 7Copying 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 8int 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 12Program counter (PC)special CPU register that stores address of next instruction toexecuteFor sequential instructions, PC is updated in fetchincremented by 2 or 6 depending on instruction sizeSo, to implement a goto, all we need is to change the PC CPSC 213 2020 ST1 2020 Jonatan Schroeder 13loop: goto end_loop if not (i<10)New instruction: conditional jump go to
ifPC
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-10end_loop: CPSC 213 2020 ST1 2020 Jonatan Schroeder22 i = 0;loop: goto end_loop if not (i<10)s += a[i]; i++;goto loopend_loop:ld $0, r0 ld $a, r1 ld $s, r2 ld (r2), r2 ld $-10, r4loop: mov r0, r5 add r4, r5beq r5, end_loopld (r1, r0, 4), r3 add r3, r2inc r0br loopend_loop: ld $s, r1 st r2, (r1)st r0, 4(r1) 23r0Value of ir1Address of ar2Value of sr3Value of a[i]r4Constant: -10r5i-10 CPSC 213 2020 ST1 2020 Jonatan SchroederIn 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=a4;
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: incr0
decr3
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 Well 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
jping
ping:
j (r6)
# r6 = pc of instruction after jump
# goto ping
# return
CPSC 213 2020 ST1 2020 Jonatan Schroeder 34
Reviews
There are no reviews yet.