Function pointers using relative jumps

[jjcnn]

Consider a variable in the source language that gets initialized to a function pointer:

let f = if ... { fun1 } else { fun2 }
...
let x = f (a, b, c);

The question is how to perform the dispatch to the function that f points to when only relative jumps are available in the assembly target.
To do this we need two things for every function type T in the program (there are a finite number of such types, and they are known statically):

1. An entry in the constant pool containing an array of addresses of the functions that have type T. (There are a finite number of function of that type, and those functions are known statically).
2. A dispatch function which, given an index i and a set of arguments, looks up item i in the function pointer array, and calls that function with the set of arguments (the typechecker guarantees that the types of the arguments match the function being called).
   In pseudo-code the dispatch function looks something like this:
   fn dispatch_X_Y_Z_W (index: int, x: X, y: Y, z: Z) -> W {
   let fps = <constant pool array for type (X, Y, Z) -> W>;
   fps[index](x, y, z) // This is the call point for fun1 or fun2
   }
   In the example above we would get something like the following:

• There is a single function type (X, Y, Z) -> W, and two functions of that type fun1 and fun2.
• In the compiled program the functions fun1 and fun2 will be located at addresses addr_fun1 and addr_fun2, respectively.
• The dispatch function for type (X, Y, Z) -> W contains a single call point for the functions of type (X, Y, Z) -> W. That callpoint is located at address addr_callpoint_X_Y_Z_W.
• The constant pool entry will contain the array [ addr_fun1 - addr_callpoint_X_Y_Z_W, addr_fun2 - addr_callpoint_X_Y_Z_W ]. These are the addresses of the functions of types (X, Y, Z) -> W relative to the single call point for those functions.
  in the example above the line let f = if ... { fun1 } else { fun2 } would evaluate to a struct containing
• An integer that represents the index into the constant pool array. The index would depend on whether the then branch or the else branch gets taken. Whichever function pointer the expression evaluates to we know statically which index in the constant pool entry each potential result corresponds to.
• An indicator of which dispatch function to use when the struct gets applied. During compilation this could be the name of the dispatch function or the type of the function pointer (from which the dispatch function can be determined), but in any case is obviously known statically.
  Once the function pointer gets applied in the line let x = f (a, b, c), this performs a call to the dispatch function:
• The concrete dispatch function is determined by the dispatch indicator in the struct value of f.
• The dispatch function is called with arguments (index, a, b, c), where index is the index from the struct value of f.
  Since the address of the dispatch function is known statically, we can always statically determine the relative address from any call site to the dispatch function. And since the addresses of the functions of the relevant type are known statically, and now only have a single call site (inside the dispatch function), the relative addresses of the calls to those functions are also known statically.
  The end result is that function pointers can be implemented using relative addresses.

[jjcnn]

@IGI-111 : As promised.