Unit 1f - Dynamic Control Flow

Polymorphism

• Invoking a method on a object in Java

  • Variable that stores the object has a static (apparent) type
  • Object reference is dynamic, with (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 depends on the type of the referenced object
  • On call site can invoke different methods at different times

 
xxxxxxxxxx
19
1
class A {
2
  void ping() {...}
3
  void pong() {...}
4
}
5
class B extends A {
6
  void ping() {...}
7
  void pong() {...}
8
  void wiff() {...}
9
}
10
​
11
static void foo(A a) {
12
  a.ping();
13
  a.pong();
14
}
15
​
16
static void bar() {
17
  foo(new A());
18
  foo(new B());
19
}

Polymorphism Dispatch

• Method address is determined dynamically

  • Compiler cannot hardcode target addresses 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
  • Class object stores the class's jump table
  • Jump table stores the address of address of methods implemented by the class
  • Address of jump table is determined dynamically
  • Method's offset into jump table is determined statically

Dynamic Jumps in C

• Function pointer

  • A variable that stores a pointer to a procedure

  • Declared:

    <return-type> (*<var-name>)(<argument-list>);

  • Dynamic call uses same format as regular function call:

    <var-name> (<arguments>);

• Example:

  

Static vs Dynamic Call

• These two snippets have the same behaviour

Implementing Polymorphism in C

• Use a struct to store jump table:

  • Class jump table declaration:

     
    xxxxxxxxxx
    4
    1
    struct A_class {
    2
      void (*ping) (void *);
    3
      void (*pong) (void *);
    4
    };
    

• Instance methods:

   
  xxxxxxxxxx
  2
  1
  void A_ping (void *this) {...}
  2
  void A_pong (void *this) {...}
  

• Static class object:

  struct A_class A_class_obj = {A_ping, A_pong};

  ---

• Object (instance of class)

  • Object template:

   
  xxxxxxxxxx
  3
  1
  struct A {
  2
    struct A_class *class;
  3
  }
  

  • Constructor:

   
  xxxxxxxxxx
  5
  1
  struct A *new_A() {
  2
    struct A *obj = malloc(sizeof(struct A));
  3
    obj->class = &A_class_obj;
  4
    return obj;
  5
  }
  

  ---

• Object use:

  • Allocating an instance

  struct A *a = new_A();

  • Calling instance methods

  a->class->ping(a);

  a->class->pong(a);

• Extending a Class

  • Class jump table (must be a super set of A's, in same order)

 
xxxxxxxxxx
5
1
struct B_class {
2
  void (*ping) (void *);
3
  void (*pong) (void *); // or struct A_class super_class;
4
  void (*wiff) (void *);
5
}

• B's methods and class object

 
xxxxxxxxxx
3
1
void B_ping (void *this) {...}
2
void B_wiff (void *this) {...}
3
struct B_class B_class_obj = {B_ping, A_pong, B_wiff}

• Using polymorphic classes:

 
xxxxxxxxxx
8
1
void foo (struct A* a) {
2
  a->class->ping(a);
3
  a->class->pong(a);
4
}
5
void bar () {
6
  foo (new_A());
7
  foo ((struct A *) new_B());
8
}

Polymorphic Dispatch in Assembly

• How do we compile this function call?

a->class->ping(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:

 
xxxxxxxxxx
2
1
r[2]    <-  m[r[1] + 4] # ld 4(r1), r2
2
pc      <-  r[2]        # j(r2)

Double Indirect Jump

• 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

Implementing Method Calls

 
xxxxxxxxxx
12
1
ld  (r5), r0    # r0 = a
2
ld  (r0), r1    # r1 = a->class
3
deca    r5      # allocate argument frame
4
st  r0, (r5)    # store a as 1st argument in stack
5
gpc $2, r6      # save return address
6
j   *0(r1)      # a->class->ping(a)
7
inca    r5      # free argument frame
8
deca    r5      # allocate argument frame
9
st r0, (r5)     # store a as 1st argument in stack
10
gpc $2, r6      # save return address
11
j   *4(r1)      # a->class->pong(a)
12
inca    r5      # free argument frame

Linked List: Follow All Elements

• Consider the linked list implementation below:

 
xxxxxxxxxx
12
1
struct node {
2
  int key;
3
  int value;
4
  struct node *next;
5
};
6
// ..
7
void print_list(struct node *list){
8
  while(list) {
9
    printf("%d: %d\n", list->key, list->value);
10
    list = list->next;
11
  }
12
}

Problems with print_list

• 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.

Generalized Version

 
xxxxxxxxxx
13
1
void follow_list(struct node *list,
2
                 void (*fn)(int, int)) {
3
  while(list) {
4
    fn(list->key, list->value);
5
    list = list->next;
6
  }
7
}
8
​
9
void print_element(int key, int value) {
10
  printf("%10d: %10d\n", list->key, list->value)
11
}
12
// Print all elements in the list
13
follow_list(list, print_element);

Function Pointer in Dr Racket

• 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))

• Other languages also include "lambda" calculation

  • Including Java version 8

Implementing Map in C

• In C:

 
xxxxxxxxxx
12
1
void map(int (*fn)(int, int), int n, int *s0, int *s1, int *d) {
2
  int i;
3
  for (i = 0; i < n; i++) {
4
    d[i] = fn(s0[i], s1[i])
5
  }
6
}
7
​
8
int add(int a, int b) {
9
  return a+b;
10
}
11
// ...
12
map(add, 3, a, b, c);

Implementing Foldl in C

• In C:

 
xxxxxxxxxx
13
1
int foldl(int (*fn)(int, int), int v, int *a, int n) {
2
  int i;
3
  for (i = 0; i < n; i++) {
4
    v = fn(v, a[i])
5
  }
6
  return v;
7
}
8
​
9
int add(int a, int b) {
10
  return a+b;
11
}
12
// ...
13
printf("%d\n", foldl(add, 0, a, 3));

Switch Statement

• Semantics the same as simplified nested if statements

  • Condition of each if tests the same variable

• Assembly implementation: sequence of branches?

 
xxxxxxxxxx
12
1
switch (i) {
2
  case 0:
3
    j = 10; break;
4
  case 1:
5
    j = 11; break;
6
  case 2:
7
    j = 12; break;
8
  case 3:
9
    j = 13; break;
10
  default:
11
    j = 14; break;
12
}

Switch: The Human Perspective

• Switch models a common idion

  • Choosing 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

Switch: The Compiler Perspective

• 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 seperately

• Implementation can work with:

  • An 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

Switch Using GOTO

 
xxxxxxxxxx
14
1
        void *jt[4] = { &&L0, &&L1, &&L2, &&L3 };
2
        if (i < 0 || i > 3) goto DEFAULT;
3
        else goto *jt[i];
4
L0:     j = 10;
5
        goto CONTINUE;
6
L1:     j = 11;
7
        goto CONTINUE;
8
L2:     j = 12;
9
        goto CONTINUE;
10
L3:     j = 13;
11
        goto CONTINUE;
12
DEFAULT:j = 14;
13
        goto CONTINUE;
14
CONTINUE:

Problems with Switch Jump Table

• Jump table have a limitation:

  • You need addresses for all values from 0 up to the table limit

• Special consideration:

  • 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?

Switch Statement Implementation

• 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 directly to code selected case arm

Switch Example: Original Code

 
xxxxxxxxxx
6
1
switch (i) {
2
  case 20: j = 10; break;
3
  case 21: j = 11; break;
4
  case 23: j = 13; break;
5
  default: j = 14; break;
6
}

Switch Example: Using GOTO

 
xxxxxxxxxx
14
1
        static const void* jt[4] = 
2
          { &&L20, &&L21, &&DEFAULT, &&L23 };
3
        if (i < 20 || i > 23) goto DEFAULT;
4
        goto *jt [i-20];
5
L20:    j = 10;
6
        goto CONT;
7
L21:    j = 11;
8
        goto CONT;
9
L23:    j = 13;
10
        goto CONT;
11
DEFAULT:
12
        j = 14;
13
        goto CONT;
14
CONT:

Switch Example: Assembly, Part 1

 
xxxxxxxxxx
27
1
foo:    ld  $i, r0          # r0 = &i
2
        ld  0x0(r0), r0     # r0 = i
3
        ld  $0xffffffed, r1 # r1 = -19
4
        add r0, r1          # r0 = i - 19
5
        bgt r1, l0          # goto l0 if i>19
6
        br  default         # goto default if i<20
7
l0:     ld  $0xffffffe9, r1 # r1 = -23
8
        add r0, r1          # r1 = i-23
9
        bgt r1, default     # goto default if i>23
10
        ld  $0xffffffec, r1 # r1 = -20
11
        add r1, r0          # r0 = i-20
12
        ld  $jmptable, r1   # r1 = &jmptable
13
        j   *(r1, r0, 4)    # goto jmptable[i-20]
14
case20: ld  $0xa, r1        # r1 = 10
15
        br  done            # goto done
16
case21: ld  $0xb, r1        # r1 = 11
17
        br  done            # goto done
18
...
19
default:ld  $0xe, r1        # r1 = 14
20
done:   ld  $j, r0          # r0 = &j
21
        st  r1, 0x0(r0)     # j = r1
22
...
23
jmptable:
24
        .long   case20      # & (case 20)
25
        .long   case21      # & (case 21)
26
        .long   default     # & (case 22)
27
        .long   case23      # & (case 23)

Double Indirect Jump: Extended

• 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