CS计算机代考程序代写 python javascript compiler Java arm assembly CPSC 213 Introduction to Computer Systems

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 array[], …, int pivotIndex) {
Comparable pivotValue, t;
int storeIndex, i;
pivotValue = array [pivotIndex];
array [pivotIndex] = array [right];
array [right] = pivotValue;
storeIndex = left;
for (i=left; i extends Integer {
@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; ii);
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 : repeated 0 or more times
default: optional
}
‣ 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