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
);
void go() { void go(void (*proc)()) {
printf(foo
); }}
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
, 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
, 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 Schroeder14In 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
“, foldl(add, 0, a, 3); CPSC 213 2020 WT2 2021 Jonatan Schroeder15The 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 elementsAny size of each element (e.g., int, structs, strings, pointers) Any comparison function CPSC 213 2020 WT2 2021 Jonatan Schroeder 16int (*x)(char *);What does the variable x above represent?A. A function that receives a char pointer as argument and returns an int pointerB. A function that receives a function pointer as argument and returns an int pointerC. A pointer to a function that receives a char pointer as argument and returns an intD. A pointer to a function that receives a function pointer as argument and returns an intE. None of the aboveCPSC 213 2020 WT2 2021 Jonatan Schroeder 17 Invoking a method on an object in JavaVariable that stores the object has a static (apparent) typeObject reference is dynamic, with dynamic (actual) typeObjects actual type must be a subtype of the apparent type of the referring variableObjects actual type may override methods of the apparent type Polymorphic dispatchTarget method address (destination of the jump) depends on the actual type of the referenced objectCall can invoke different methods at different timesCPSC 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 Schroeder19Method address is determined dynamically Compiler cannot hardcode target address in procedure call Lookup of procedure address happens in runtime Address is obtained from memoryClass Jump tableEvery class is represented by a class objectObjects store a pointer to their class object (actual type)Class object stores the classs jump tableJump table stores the address of methods implemented by the class Address of jump table is determined dynamicallyMethods offset into jump table is determined statically CPSC 213 2020 WT2 2021 Jonatan Schroeder 20static void foo(A a) {a.ping();a.pong();}static void bar() {foo(new A());foo(new B()); }ObjectClass: AObjectClass: BClass Aping() pong()Class Bping()pong()wiff()MethodA.ping()MethodA.pong()MethodB.ping()MethodB.wiff() CPSC 213 2020 WT2 2021 Jonatan Schroeder21r5a 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 22Object (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 As, 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};
Bs 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 objects 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
Reviews
There are no reviews yet.