CPSC 213 Introduction to Computer Systems
Winter Session 2020, Term 2
Unit 1f – Mar 8
Dynamic Control Flow
Overview
‣ Reading
• Companion: 2.7.4, 2.7.7-2.7.8
‣ Reference
• Text: 3.6.7, 3.10
‣ Learning Goals
• Write C programs that use function pointers
• Explain how Java implements polymorphism
• Identify the number of memory references that occur when a static method is called in Java and when an instance method is called
• 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 (a gcc extension to C)
• 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
2
Dynamic Control Flow
‣ Function Call/Return
foo: gpc $6, r6
j ping
…
ping: j (r6)
‣ Return is dynamic control flow! ‣ Calling different functions
beq r0, L2
L1: gpc$6,r6 #runfunc1ifr0!=0
j func1
br L3
L2: gpc$6,r6 #runfunc2ifr0==0
j func2
L3: …
Dynamic Control Flow
‣ Calling different functions
beq r0, L2
L1: gpc$6,r6
j func1
br L3
L2: gpc$6,r6
j func2
L3: …
‣ Can we do better?
#runfunc1ifr0!=0 #runfunc2ifr0==0
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)
Dynamic Control Flow
‣ Dynamic Control Flow!
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)
‣ Functions have addresses – can make pointers to functions ‣ Lots of uses for dynamic control flow
‣ Polymorphism
‣ Function Arguments
‣ Jump Tables/Switch Statements
Return vs. Dynamic Call
‣ Return is usually at the end of a function
‣ By convention, only use r6 when returning
ld (r5), r6
inca r5
j (r6)
‣ Dynamic call is in the middle of a function ‣ gpc to set return address
gpc $2, r6
j (r1)
Dynamic Jumps in C
‣ Function pointer
• a variable that stores a pointer to a procedure
• declared
–
• used to make dynamic call
–
‣ Example
void ping() {}
void foo() {
void (*aFunc)();
aFunc = ping;
calls ping
procedure name without () variable name with ()
aFunc(); }
Uses for Dynamic Control Flow
8
Reference Counting
‣ From A5…
‣ Problem: value needs the same refcount as the element
• Because value can’t automatically be freed otherwise
struct element {
int num;
char *value;
};
struct element *element_new(int num, char *value) {
struct element *e = rc_malloc(sizeof(*e));
e->value = rc_malloc(strlen(value) + 1);
…
}
void element_keep_ref(struct element *e) {
rc_keep_ref(e->value);
rc_keep_ref(e);
}
void element_free_ref(struct element *e) {
rc_free_ref(e->value);
rc_free_ref(e);
}
9
Reference Counting
‣ Finalizers to the rescue!
‣ Can just rc_keep_ref/rc_free_ref element
‣ Finalizer is called automatically when refcount == 0
struct element {
int num;
char *value;
};
void element_finalizer(struct element *e) {
free(e->value);
}
struct element *element_new(int num, char *value) {
struct element *e = rc_malloc(sizeof(*e), element_finalizer); e->value = malloc(strlen(value) + 1);
…
}
10
Reference Counting
‣ A7…Reference Counting with Finalizers
struct rc_header {
int refcount;
rc_finalizer_t finalizer;
};
void *rc_malloc(int nbytes, rc_finalizer_t finalizer) {
struct rc_header *rc = malloc(nbytes + sizeof(struct rc_header));
rc->refcount = 1;
rc->finalizer = finalizer;
return (void *)(rc + 1);
}
void rc_keep_ref(void *p) {
struct rc_header *rc = ((struct rc_header *)p) – 1;
rc->refcount++;
}
void rc_free_ref(void *p) {
struct rc_header *rc = ((struct rc_header *)p) – 1;
rc->refcount–;
if(rc->refcount == 0) {
if(rc->finalizer)
rc->finalizer(p);
free(rc); }
}
11
Question 1f.1
‣ Which of the following is valid syntax for declaring a finalizer pointer (which points to a function that takes a pointer and returns nothing)?
‣ A. void f(void *x)
‣ B. void (void *x) *f ‣ C. void (*)f(void *x) ‣ D. void (*f)(void *x) ‣ E. void *(*f)(void *x)
Generic Functions
‣ Consider, for example, writing Quicksort to sort integers
int partition (int* array, int left, int right, int pivotIndex) {
int pivotValue, t;
int storeIndex, i;
pivotValue = array [pivotIndex];
array [pivotIndex] = array [right];
array [right] = pivotValue;
storeIndex = left;
for (i=left; i
Comparable
int storeIndex, i;
pivotValue = array [pivotIndex];
array [pivotIndex] = array [right];
array [right] = pivotValue;
storeIndex = left;
for (i=left; i
@Override
int compareTo(Integer i) {
return intValue() < i.intValue()? -1: intValue == i.intValue()? 0: 1;
} }
16
Genericity
‣ C library qsort function
void qsort(void *base, size_t nel, size_t width,
int (*compare)(const void *, const void *))
‣ Full genericity through width parameter • struct A *ap;
qsort(ap, 5, sizeof(struct A), compare_A)
• int *ip;
qsort(ip, 16, sizeof(int), compare_int)
struct
struct
struct
struct
struct
int
int
int
int
int
int
int
int
int
int
int
int
int
int
int
int
17
Using the Parameterized Quicksort
‣ To sort integers
‣ To sort strings
int cmpIntegers(void *av, void *bv) { int a = *(int *)av;
int b = *(int *)bv;
return a < b? -1: a == b? 0 : 1;
}
int intArray[] = {3, 8, 1};
qsort(intArray, 3, sizeof(int), cmpIntegers);
int cmpStrings(void *av, void *bv) {
char *a = *(char **)av;
char *b = *(char **)bv;
while(*a != 0 && *b != 0 && *a == *b) {
a++; b++;
r} e t u r n * a < * b ? - 1 : * a = = * b ? 0 : 1 ; }
char *strArray[] = {"Mike", "Ben", "Liam", "Ace"};
qsort(strArray, 4, sizeof(char *), cmpStrings);
18
Higher-Order Functions
19
Remember Dr Racket
‣Map – (map f lst ...)
• (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 list iterators • foldl, filter, …
(foldl + 0 (list 1 2 3))
(filter (lambda (a) (> a 3)) (list 1 2 3 4 5))
‣ Other languages
• python, javascript and Java …
20
Implementing map in C
‣Map – (map f lst …)
• (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)
‣In C
‣ We can do it with an int array
‣ But to generalize, we need void *
void map(void (*f)(void*, void*, void**), int n, void** s0, void** s1, void** d)
‣
21
How about foldl – aka reduce ?
‣ Consider
• using (foldl f init lst …) to compute sum, min, max, count of an array • (foldl + 0 (list 1 2 3 4))
‣In C }
void foldl (void (*f)(void*, void**), int n, void** v, void** a) {
for (int i=0; i
void A_pong(void *thisv) { printf(“A_pong\n”); } • Static Allocation and Initialization of Class Object
struct A_class A_class_table = {A_ping, A_pong};
ping pong
‣ Object (Instance of Class) • Object Template
struct A {
struct A_class *class;
int i;
};
• Constructor Method
A_ping
A_pong
struct A *new_A(int i) {
struct A *obj = malloc(sizeof(struct A));
obj->class = &A_class_table;
obj->i = i;
return obj;
}
• Allocating an Instance
struct A *a = new_A(10); • Calling Instance Methods
a->class->ping(a);
a->class->pong(a);
class i=10
a
30
ping pong
The same thing for class B extends A
‣ The class struct is a super set of A’s
struct B_class {
void (*ping)(void*);
void (*pong)(void*);
void (*wiff)(void*);
};
‣ B’s methods and class object
void B_ping(void *this) { printf (“B_ping\n”); }
void B_wiff(void *this) { printf (“B_wiff\n”); }
struct B_class B_class_table = {B_ping, A_pong, B_wiff};
A_ping
A_pong
ping pong
ping
pong
wiff
class B extends A {
void ping () {}
void wiff () {}
}
struct A_class {
void (*ping)(void*);
void (*pong)(void*);
};
31
Dispatch Diagram for C
class i=10
void foo(void *av) {
struct A *a = av;
a->class->ping(a);
a->class->pong(a);
}
void bar() {
foo (new_A(10));
foo (new_B(20));
}
r5
aa
A_ping
A_pong
ping B_ping pong B_wiff
class i=20
ping
pong
wiff
foo (a) (some procedure call details left out)
r[0] ← m[r[5]+4] # r0 = a
r[1] ← m[r[0]] # r1 = a->class
pc ← m[r[1]+0*4] # a->class->ping (a) pc ← m[r[1]+1*4] # a->class->pong (a)
r5
32
Runtime Stack
ISA for Polymorphic Dispatch
void foo (void* av) {
void A* a = av;
a->class->ping (a);
a->class->pong (a);
}
‣ How do we compile • a->class->ping () ?
‣ Pseudo code
• pc ← m[r[1]+1*4]
‣ Broken down
• r[1] ← m[r[1]+1*4]
• pc ← r[1]
‣ As assembly
• ld 4(r1), r1 • j (r1)
r[0] ← m[r[5]] # r0 = a
r[1] ← m[r[0]] # r1 = a->class
pc ← m[r[1]+0*4] # a->class->ping() pc ← m[r[1]+1*4] # a->class->pong()
Switch Statements
Switch Statement
int i; int j;
void foo () {
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;
} }}
‣ Semantics the same as simplified nested if statements • where condition of each if tests the same variable
• unless you leave out the break at the end of a case block
‣ So, why bother putting this in the language?
• is it for humans, facilitate writing and reading of code?
• is it for compilers, permitting a more efficient implementation?
‣ Implementing switch statements
• we already know how to implement if statements; is there anything more to consider?
void bar () {
if (i==0)
j=10;
else if (i==1)
j = 11;
else if (i==2)
j = 12;
else if (i==3)
j = 13;
else
j = 14;
Human vs Compiler
‣ Benefits for humans
• the syntax models a common idiom: choosing one computation from a set
‣ But, switch statements have interesting restrictions
• case labels must be static, cardinal values
– a cardinal value is a number that specifies a position relative to the beginning of an ordered set – for example, integers are cardinal values, but strings are not
• case labels must be compared for equality to a single dynamic expression – some languages permit the expression to be an inequality
‣ Do these restrictions benefit humans? • have you ever wanted to do something like this?
switch (treeName) {
case “larch”:
case “cedar”:
case “hemlock”:
}
switch (i,j) {
case i>0:
case i==0 & j>a:
case i<0 & j==a:
default:
}
Why Compilers like Switch Statements
‣ Notice what we have
• switch condition evaluates to a number • each case arm has a distinct number
‣ And so, the implementation has a simplified form
• build a table with the address of every case arm, indexed by case value • switch by indexing into this table and jumping to matching case arm
‣ For example
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;
}
static const
L0:
L1:
void* jt[4] = { &&L0, &&L1, &&L2, &&L3 }; if(i<0||i>3)gotoDEFAULT;
goto *jt [i];
j=10;
goto CONT; j=11; goto CONT;
L2: j = 12;
goto CONT;
L3: j = 13;
goto CONT;
DEFAULT:
j = 14;
goto CONT;
CONT:
Switch Statement Control Flow with Jump Table
if (i < 0 || i > 3) goto DEFAULT;
goto *jt [i];
L0:
j = 10;
goto CONT;
L1:
j = 11;
goto CONT;
L2:
j = 12;
goto CONT;
CONT:
L3:
j = 13;
goto CONT;
DEFAULT:
j = 14;
goto CONT;
&&L0
&&L1
&&L2
&&L3
&&DEFAULT
jt:
38
Happy Compilers mean Happy People
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;
}
L0:
L1:
void* jt[4] = { &&L0, &&L1, &&L2, &&L3 };
if (i < 0 || i > 3) goto DEFAULT;
goto *jt [i];
j = 10;
‣ Computation can be much more efficient • compare the running time to if-based alternative
if (i==0)
j=10;
else if (i==1)
j = 11;
else if (i==2)
j = 12;
else if (i==3)
j = 13;
else
‣
‣ Guidelines for writing efficient switch statements
But, could it all go horribly wrong?
• construct a switch statement where this implementation technique is a really bad idea
goto CONT;
j = 11;
goto CONT;
L2: j = 12;
goto CONT;
L3: j = 13;
goto CONT;
DEFAULT:
j = 14;
goto CONT;
CONT:
j = 14;
The basic implementation strategy
‣ General form of a switch statement
switch (
case
default:
}
‣ Naive implementation strategy
goto address of code_default if cond > max_label_value
goto address in jumptable [label_i]
statically: jumptable [label_i] = address of code_i forall label_i
‣ But there are two additional considerations • case labels are not always contiguous
• the lowest case label is not always 0
Refining the implementation strategy
‣ Naive strategy
goto address of code_default if cond > max_label_value
goto address in jumptable [label_i]
statically: jumptable [label_i] = address of code_i forall label_i
‣ Non-contiguous case labels • what is the problem
switch (i) {
case 0: j=10; break;
case 3: j=13; break;
default: j=14; break;
• what is the solution }
‣ Case labels not starting at 0 • what is the problem
• what is the solution
switch (i) {
case 1000: j=10; break;
case 1001: j=11; break;
case 1002: j=12; break;
case 1003: j=13; break;
default: j=14; break;
}
Implementing Switch Statements
‣ Choose strategy
• use jump-table unless case labels are sparse or there are very few of them • use nested-if-statements otherwise
‣ Jump-table strategy • statically
– build jump table for all label values between lowest and highest
• generate code to
– goto default if condition is less than minimum case label or greater than maximum
– normalize condition value to lowest case label
– use jump table to go directly to code selected case arm
goto address of code_default if cond < min_label_value
goto address of code_default if cond > max_label_value
goto address in jumptable [cond-min_label_value]
statically: jumptable [i-min_label_value] = address of code_i
forall i: min_label_value <= i <= max_label_value
Snippet B: In jump-table form
switch (i) {
case 20: j=10; break;
case 21: j=11; break;
case 23: j=13; break;
default: j=14; break;
}
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:
Snippet B: In Assembly Code
foo: ld $i,r0 #r0=&i ld 0x0(r0), r0 # r0 = i
ld $0xffffffed, r1 # r1 = -19
case20: ld
br done
…
default: ld
add r0, r1
bgt r1, l0
br default
# r0 = i-19
# goto l0 if i>19
# goto default if i<20
l0: ld $0xffffffe9, r1 # r1 = -23
add r0, r1 # r1 = i-23
bgt r1, default # goto default if i>23
ld $0xffffffec, r1 # r1 = -20
add r1, r0 # r0 = i-20
ld $jmptable, r1 # r1 = &jmptable
ld (r1, r0, 4), r1 # r1 = jmptable[i-20]
j (r1)
# goto jmptable[i-20]
#r1=10
# goto done
#r1=14
# goto done #r0=&j
# j = r1
# goto cont
# & (case 20)
# & (case 21)
# & (case 22)
# & (case 23)
done: ld
st r1, 0x0(r0)
$0xa, r1
$0xe, r1
br done
$j, r0 br cont
jmptable: .long case20
.long case21
.long default
.long case23
Simulator …
Summary
‣ Static vs Dynamic flow control
• static if jump target is known by compiler
• dynamic for polymorphic dispatch, function pointers, and switch statements
‣ Polymorphic Dispatch in Java
• invoking a method on an object in java
• method address depends on object’s type, which is not know statically
• object has pointer to class object; class object contains method jump table • procedure call is this a double-indirect jump – i.e., target address in memory
‣ Function Pointers in C
• a variable that stores the address of a procedure
• used to implement dynamic procedure call, similar to polymorphic dispatch
‣ Switch Statements
• syntax restricted so that they can be implemented with jump table
• jump-table implementation running time is independent of the number of case labels • but, only works if case label values are reasonably dense