2020 – Winter Term 2
Unit 1f – Dynamic Control Flow
1
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
▪Reading: Companion: 2.7.4, 2.7.7-2.7.8; Textbook (reference): 3.6.7, 3.10
▪Learning Goals
▪ Write C programs that use function pointers
▪ Explain how Java implements polymorphism
▪ Identify memory references on static method and instance method calls in Java
▪ Convert Java instance-method call into equivalent C code that uses function pointers
▪ Convert C programs that use function pointers into assembly code
▪Explain why switch statements in C (and Java until version 1.7) restrict case labels to cardinal types (i.e, things that map to natural numbers)
▪ Convert C switch statement into equivalent C statement using gotos and an array of label pointers
▪ Convert C switch statement into equivalent assembly language that uses a jump table
▪ Determine whether a given switch statement would be better implemented using if
statements or a jump table and explain the tradeoffs involved
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 2
▪Static method invocations and procedure calls ▪Target method/procedure address is known statically
▪In Java: static methods are class methods ▪Invoked by naming the class, not an object
▪In C: direct procedure calls
▪However, returns are dynamic control flow!
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 3
▪Calling different functions
beq r0, L2
L1: gpc $6, r6 # run func1 if r0 != 0
j func1
br L3
L2: gpc $6, r6 # run func2 if r0 == 0
j func2 L3: …
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 4
▪Different approach:
beq r0, L2
L1: ld $func1, r1 # run func1 if r0 != 0
br L3
L2: ld $func2, r1 # run func2 if r0 == 0 L3: gpc $2, r6
j (r1)
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 5
▪Functions have addresses
▪So we can make pointers to functions
▪Useful for:
▪Function arguments (generic operations) ▪Polymorphism (method calls in Java) ▪Jump tables (switch statements)
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 6
▪Function pointer
▪A variable that stores a pointer to a procedure
▪ Declared:
▪Example:
}
void ping() {} void foo() {
void (*aFunc) ();
aFunc = ping; // Assigns function ping to variable
aFunc(); // Calls ping
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
7
▪These two snippets have the same behaviour void foo() { void foo() {
printf(“foo\n”);
void go() { void go(void (*proc)()) {
printf(“foo\n”); }}
foo(); }}
proc();
void bat() { void bat() {
go(); }}
go(foo);
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
8
▪ Consider the linked list implementation below: struct node {
int key;
int value;
struct node *next;
};
void print_list(struct node *list) {
while (list) {
printf(“%d: %d\n”, list->key, list->value); list = list->next;
} }
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 9
▪The function print_list is very specific:
▪What if we need to print in a different format?
▪What if we want to print to a file?
▪What if we want to perform another task with each key-value pair?
▪Solution: function pointer
▪Parameter to print_list: what to do with each key-value pair
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 10
void follow_list(struct node *list,
void (*fn)(int, int)) {
while (list) {
fn(list->key, list->value);
list = list->next;
} }
void print_element(int key, int value) { printf(“%10d: %10d\n”, key, value);
}
// Print all elements in the list
follow_list(list, print_element);
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 11
follow_list:
deca r5
st r6, (r5)
ld 4(r5), r0
loop:
beq r0, L0
ld 8(r5), r1
ld 0(r0), r2 ld 4(r0), r3 deca r5
deca r5
st r2, 0(r5)
# save r.a. #r0=list
# while(list)
#r1=fn
# r2 = list->key
# r3 = list->value
# arg0 = key
st r3, 4(r5) # arg1 = value
gpc $2, r6 # load r.a. j (r1) # call fn inca r5
inca r5
ld 4(r5), r0 # r0 = list
ld 8(r0), r0 # r0 = list->next br loop # back to loop
L0:
ld (r5), r6 # restore r.a. inca r5
j (r6) # return
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
12
▪map receives a function and two lists, applies function to pairs of elements
▪(map + (list 1 4 3) (list 7 2 5)) => (list 8 6 8) ▪(map (lambda (a b) (+ a b)) (list 1 4 3) (list 7 2 5))
▪(map max (list 1 4 3) (list 7 2 5)) => (list 7 4 5)
▪Other iterators:
▪(foldl + 0 (list 1 2 3))
▪(filter (lambda (a) (> a 3)) (list 1 2 3 4 5))
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 13
▪In C:
void map(int (*fn)(int, int), int n,
int add(int a, int b) {
return a+b;
int *s0, int *s1, int *d) {
}
int i;
for (i = 0; i < n; i++) {
d[i] = fn(s0[i], s1[i]);
}
}
// ...
map (add, 3, a, b, c);
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
14
▪In C:
int foldl(int (*fn)(int, int), int v, int *a, int n) {
int i;
for (i = 0; i < n; i++) {
v = fn(v, a[i]);
}
return v; }
int add(int a, int b) {
return a+b;
}
// ...
printf("%d\n", foldl(add, 0, a, 3);
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
15
▪The C library qsort function is declared as:
void qsort(void *base, size_t nel, size_t width,
int (*compare)(const void *, const void *));
▪Can call the function with:
▪Any number of elements
▪Any size of each element (e.g., int, structs, strings, pointers) ▪Any comparison function
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 16
int (*x)(char *);
What does the variable x above represent?
A. A function that receives a char pointer as argument and returns an int pointer
B. A function that receives a function pointer as argument and returns an int pointer
C. A pointer to a function that receives a char pointer as argument and returns an int
D. A pointer to a function that receives a function pointer as argument and returns an int
E. None of the above
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 17
▪Invoking a method on an object in Java
▪Variable that stores the object has a static (apparent) type
▪Object reference is dynamic, with dynamic (actual) type
▪Object’s actual type must be a subtype of the apparent type of the referring variable
▪Object’s actual type may override methods of the apparent type ▪Polymorphic dispatch
▪Target method address (destination of the jump) depends on the actual type of the referenced object
▪Call can invoke different methods at different times
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 18
class A {
void ping() { ... } void pong() { ... }
static void foo(A a) {
}}
class B extends A { void ping() { ... } void wiff() { ... }
static void bar() { foo(new A()); foo(new B());
}}
a.ping(); a.pong();
Which ping is called?
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
19
▪Method address is determined dynamically ▪Compiler cannot hardcode target address in procedure call ▪Lookup of procedure address happens in runtime ▪Address is obtained from memory
▪Class Jump table
▪Every class is represented by a class object
▪Objects store a pointer to their class object (actual type)
▪Class object stores the class’s jump table
▪Jump table stores the address of methods implemented by the class ▪Address of jump table is determined dynamically
▪Method’s offset into jump table is determined statically
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 20
static void foo(A a) {
a.ping();
a.pong();
}
static void bar() {
foo(new A());
foo(new B()); }
Object
Class: A
Object
Class: B
Class A
ping() pong()
Class B
ping()
pong()
wiff()
Method
A.ping()
Method
A.pong()
Method
B.ping()
Method
B.wiff()
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
21
r5
a
▪Use a struct to store jump table: ▪Class jump table declaration:
struct A_class {
void (*ping) (void *); void (*pong) (void *);
};
▪Instance methods:
void A_ping (void *this) { ... }
void A_pong (void *this) { ... }
▪Static class object:
struct A_class A_class_obj = {A_ping, A_pong};
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 22
▪Object (instance of class) ▪Object template:
struct A {
struct A_class *class;
// instance variables
};
▪ Constructor:
struct A *new_A() {
struct A *obj = malloc(sizeof(struct A)); obj->class = &A_class_obj;
return obj;
}
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 23
▪Object use: ▪Allocating an instance
struct A *a = new_A();
▪Calling instance methods a->class->ping(a);
a->class->pong(a);
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 24
▪Extending a class:
▪Class jump table (must be a super set of A’s, in same order)
struct B_class {
void (*ping) (void *); void (*pong) (void *); void (*wiff) (void *);
}
void B_ping (void *this) { … }
void B_wiff (void *this) { … }
struct B_class B_class_obj = {B_ping, A_pong, B_wiff};
▪B’s methods and class object
// or struct A_class super_class;
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 25
▪Object (instance of class) ▪Object template:
struct B {
struct B_class *class;
// same instance variables as A in same order, followed by new ones
};
▪ Constructor:
struct B *new_B() {
struct B *obj = malloc(sizeof(struct B)); obj->class = &B_class_obj;
return obj;
}
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 26
▪Using polymorphic classes: void foo (struct A* a) {
a->class->ping(a);
a->class->pong(a);
}
void bar () {
foo (new_A());
foo ((struct A *) new_B());
}
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 27
▪How do we represent this function call in Assembly? a->class->pong(a);
▪Pseudo-code (assuming a->class in r[1]):
pc ← m[r[1]+4]
▪Currently we support
▪Absolute jump (static address)
▪Relative branch (static offset from current PC)
▪ Indirect jump (destination in register, with possible offset)
▪We can convert the above to:
r[2] ← m[r[1]+4] # ld 4(r1), r2 pc ←r[2] #j(r2)
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 28
r[2] ← m[r[1]+4] # ld 4(r1), r2 pc ← r[2] # j (r2)
▪Can we join both instructions in one?
▪Method calls are common in Java, so a single instruction is better
▪Double-indirect jump: jump to address stored in memory ▪using base+offset addressing
Name
Semantics
Assembly
Machine
jump
pc ←a
ja
b— aaaaaaaa
indirect jump
pc ← r[t] + o (or r[t]+p*2)
j o(rt)
ctpp
double-indirect jump
pc ← m[r[t] + o]
(or m[r[t]+p*4])
j *o(rt)
dtpp
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 29
ld (r5),r0 #r0=a
ld (r0), r1 # r1 = a->class
void foo (struct A* a) { a->class->ping(a); a->class->pong(a);
}
deca r5
st r0, (r5) gpc $2, r6
j *0(r1) inca r5
deca r5
st r0, (r5) gpc $2, r6
j *4(r1) inca r5
# allocate argument frame
# store a as 1st argument in stack # save return address
# a->class->ping(a)
# free argument frame
# allocate argument frame
# store a as 1st argument in stack # save return address
# a->class->pong(a)
# free argument frame
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
30
▪Semantics the same as simplified nested if statements ▪Condition of each if tests the same variable
▪Assembly implementation: sequence of branches? switch (i) {
case 0: j = 10; break; case 1: j = 11; break; case 2: j = 12; break; case 3: j = 13; break; default: j = 14; break;
}
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 31
▪Switch models a common idiom
▪Choosing the result of one computation from a set
▪Switch statements have interesting restrictions ▪Case labels must be static, cardinal values
▪ Integers, characters, but not strings
▪Case labels must be compared for equality to a single expression
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 32
▪Note that each case label represents a code starting line ▪So each case value could represent a jump
▪Break is explicit, so jump out is handled separately
▪Implementation can work with array of jump addresses ▪Array position represented by case value
▪Jump based on array element
▪Special case for default outside the range of array
▪Computation can be more efficient
▪Less conditional branches, less instructions in general
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 33
void *jt[4] = { &&L0, &&L1, &&L2, &&L3 }; if (i < 0 || i > 3) goto DEFAULT;
else goto *jt[i];
L0: j = 10;
goto CONTINUE;
L1: j = 11;
goto CONTINUE;
L2: j = 12;
goto CONTINUE;
L3: j = 13;
goto CONTINUE;
DEFAULT: j = 14;
goto CONTINUE;
CONTINUE:
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 34
▪Jump tables have a limitation:
▪You need addresses for all values from 0 up to the table limit
▪Special considerations:
▪What if there are gaps?
▪What if there is no case 0?
▪What if cases start at large values (e.g., 1000)? ▪What about negative cases?
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 35
▪Strategy depends on case
▪If labels are sparse, or there are very few cases, use nested ifs ▪Otherwise, use jump table
▪Jump table implementation
▪Build jump table for all label values between lowest and highest ▪Generate code to goto default if condition is outside range ▪Normalize condition value to lowest case label
▪Use jump table to go directly to code selected case arm
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 36
switch (i) {
case -20: … break; case 0: … break; case 5: … break; case 11: … break; default: … break;
}
Which of the following implementations is the most appropriate in this case?
A. A jump table
B. A sequence of “if”
statements
C. Either option is equally appropriate
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
37
switch (i) {
case -207: … break; case -208: … break; case -209: … break; case -210: … break; case -211: … break; case -212: … break; case -214: … break; case -215: … break; default: … break;
}
Which of the following implementations is the most appropriate in this case?
A. A jump table
B. A sequence of “if”
statements
C. Either option is equally appropriate
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
38
switch (i) {
case 20: j=10; break; case 21: j=11; break; case 23: j=13; break; default: j=14; break;
}
OR
switch (i-20) {
case 0: j=10; break; case 1: j=11; break; case 3: j=13; break; default: j=14; break;
}
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
39
static const void* jt[4] =
{ &&L20, &&L21, &&DEFAULT, &&L23 };
if (i < 20 || i > 23) goto DEFAULT;
goto *jt [i-20];
L20: j = 10;
goto CONT; L21: j = 11;
goto CONT;
L23: j = 13;
goto CONT; DEFAULT:
j = 14;
goto CONT; CONT:
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 40
foo: ld $i, r0 # r0 = &i ld 0x0(r0), r0 # r0 = i ld $0xffffffed, r1 # r1 = -19
L0:
add r0, r1
bgt r1, L0
br default
ld $0xffffffe9, r1 add r0, r1
# r0 = i-19
# goto l0 if i>19
# goto default if i<20 # r1 = -23
# r1 = i-23
# goto default if i>23
bgt r1, default
ld $0xffffffec, r1 # r1 = -20
add r1, r0
ld $jmptable, r1 j *(r1, r0, 4)
# r0 = i-20
# r1 = &jmptable
# goto jmptable[i-20]
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder
41
jmptable: .long case20 # & (case 20) .long case21 # & (case 21) .long default # & (case 22)
.long case23
case20: ld $0xa, r1
br done
case21: ld $0xb, r1
br done
…
default: ld $0xe, r1 done: ld $j, r0
# & (case 23) # r1 = 10
# goto done
# r1 = 11
# goto done
# r1 = 14
# r0 = &j st r1, 0x0(r0) # j = r1
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 42
▪Existing double-indirect jump:
▪jump to address stored in memory using base+offset addressing
▪We need a new double-indirect jump:
▪jump to address stored in memory using indexed addressing ▪can also be used for array of function pointers
Name
Semantics
Assembly
Machine
jump
pc ←a
ja
b— aaaaaaaa
indirect jump
pc ← r[t] + o (or r[t]+p*2)
j o(rt)
ctpp
double-indirect jump, base/offset
pc ← m[r[t] + o]
(or m[r[t]+p*4])
j *o(rt)
dtpp
double-indirect jump, indexed
pc ← m[r[t] + r[i]*4]
j *(rt,ri,4)
eti-
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 43
The double indirect jumps do not provide any additional functionality. Everything that can be done with double indirect jumps can also be done with a memory load (ld) followed by a regular indirect jump.
A. True B. False
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 44
▪Function pointers in C
▪A variable that stores the address of a procedure
▪Procedure call is indirect or double-indirect jump, depending where value is stored
▪Polymorphic Dispatch in Java
▪Invoking a method on an object in Java
▪Method address depends on object’s type, which is dynamic ▪Object has pointer to class object, which has jump table ▪Procedure call is double-indirect jump, target address in memory
▪Switch statements
▪Syntax restricted so that they can be implemented using jump table ▪Implementation running time independent of number of cases ▪Only works if case label values are reasonably dense
CPSC 213 2020 WT2 © 2021 Jonatan Schroeder 45