Multiple versions of the same function

Created by: wks

This issue addresses the representation of multiple versions of a function due to function redefinition.

Affects: the MicroVM reference implementation, the MicroVM-Client interface. Does not affect: the MicroVM IR language

Background

In the current microvm-refimpl, there are several classes whose relations are as following:

1. Function: represents a callable function. One per function ID
2. CFG: a concrete function definition. Has many basic blocks, each of which has many instructions.
3. A Function has zero or one CFG: if zero, the function is declared but not defined; if one, the refers to the most recent version of the function definition.
4. Stack: represents the contexts of nested function activations.
5. Frame: the context of a function activation
6. A Stack has many Frame
7. A Frame has one Function: the function this frame is created for.

Problem

After function re-definition, a new CFG is created and Function.cfg is set to the new CFG. The old CFG is discarded. This is problematic because:

a. Function redefinition only affects future invocations, but there are existing activations deep in the stack. b. A frame corresponds to a concrete CFG, not an abstract callable Function. When a Function is redefined, the CFG of an existing Frame remains the same (is not redefined). c. When a trap in an old version of a function is triggered, the client will introspect the frame which requires the metadata of the old version of a function, i.e. the CFG. It cannot be disposed.

Example

Assume we have a naive Fibonacci number function:

int executeCount = 0;
int fib(int n) { // version 1
    if (executeCount++ == 1024) { trap(keepalive=[n]); }
    if (n<=1) return n; else return fib(n-1) + fib(n-2);
}

In the MicroVM, a dictionary is kept so that

functions = { "fib" : <version 1 of fib> }

When this is executed for too many times, the trap is triggered and the client decides to redefine fib as following:

int fib(int n) { // version 2
    int a=0, b=1;
    while(n--) { int tmp=a+b; a=b; b=tmp; }
    return a;
}

And in MicroVM:

functions = { "fib" : <version 2 of fib> }

However, when the trap is triggered again (this is possible for this scenario), the control goes to the client and the client looks up functions["fib"] to get the metadata. The frame is still for version 1, but it gets <version 2 of fib>. This will cause error.

solution

Change the object relations so that:

• In 3, a Function not only has the most recent CFG, but also maintains a list of historical CFGs.
• In 7, a Frame no longer has a Function, but has a CFG, instead.
• When introspecting a frame, during trap or by other means, the client gets the concrete version of a function rather than just a function ID.
• Specify that instructions in the newer version cannot reuse the IDs from instructions in the older version (as is already like this in the refimpl) so that all instructions (especially TRAP instructions) have unique IDs through time. Each TRAP instruction can uniquely identify the CFG this instruction is defined in.

All function definitions, i.e. CFGs, are kept alive until the last activation have returned.

open questions

How to identify a particular version of a function? Does the MicroVM really need an interface for getting a specific version of a CFG? The client certainly has more information than the MicroVM about the program.