Type specialisation
Type specialisation involves generating concrete versions of polymorphic functions for each call to such a function. This is needed because the MIR does not have polymorphic functions.
We start by finding the top-level polymorphic calls, and then create the concrete versions if we haven't already. We then traverse the bodies of the functions and recursively specialise polymorphic calls in them.
The end result is that all reachable calls are now non-polymorphic.
We can then remove all polymorphic which have bodies.
Calls to polymorphic functions without bodies are left as-is and not specialised since they would be interpreter builtins.
Example
function any $T: foo(any $T: x) = bar(x);
function any $T: bar(any $T: x) = x;
any: a = foo(1);
any: b = bar(2);
First we process the call foo(1)
and generate
function int: foo(int: x) = bar(x);
Then we process the call in the body of the newly generated foo
, which is bar(x)
, and generate
function int: bar(int: x) = x;
Then we process the call bar(2)
, but don't need to generate anything since we already generated an
integer version.
The final result is
function int: foo(int: x) = bar(x);
function int: bar(int: x) = x;
any: a = foo(1);
any: b = bar(2);
Dynamic dispatch
In order to facilitate dynamic dispatch, we need to ensure that when there are multiple compatible polymorphic overloads of a function, we instantiate all versions which are more specific that the one that has been called. Otherwise, the more specific versions won't be in the model which we create the function dispatch preambles.
For example, consider:
function int: foo(any $T: x) = 1;
function int: foo(var $$E: x) = 2;
function int: foo($U: x) = 3;
var opt 1..1: x;
constraint foo(x);
If we only instantiated the var opt int
version of foo(any $T)
, then we would not be able to
dispatch to the other versions at runtime.
To do this, we find the type-inst var instantiations for each polymorphic overload (other than the original) given the argument types, and then instantiate calls using those types.
In this case, we have two other overloads and an argument of var opt int
:
foo(var $$E)
gives$$E = int
, and so the signature becomesfoo(var int)
.foo($U)
gives$U = int
, and so the signature becomesfoo(int)
.
We then instantiate foo(var int)
and foo(int)
and will be able to generate function dispatch
preambles as required.
Note that it's possible for multiple overloads to give the same signature - so we actually have to
re-lookup the best matches to prevent instantiating the wrong versions. For example, if the second
overload was foo($$E)
, then both foo($$E)
and foo($U)
would give foo(int)
to instantiate,
and in that case, we need to use the more specific $$E
version and not the $U
one.
Finally, we also have keep track of which polymorphic function each specialised function comes from, because dynamic dispatch should not happen between different instantiations of the same polymorphic function.
Generation of show
for erased types
Enums, option types and records (and types containing them) need to have specialised versions of
show
generated. The definition of show
for plain enums is actually generated during
enum erasure, but the others are generated at this stage.
Optimisation for enum functions
In the future, it would be possible to add an optimisation for functions which are polymorphic over
enum types. Functions which take a $$E
can actually just specialise into the type-erased int
version if the call does not lead to a show($$E)
call somewhere down the line.
However, it should be noted that since the fzn_...
functions are never polymorphic, there probably
aren't that many layers of depth to most calls.
Looking up function calls after specialisation
Once specialisation has occurred, we it's no longer valid to perform function lookups on non-builtin polymorphic functions (as we would have had to specialise them in order to use them correctly).
So all calls introduced after this stage must either be to builtins, or to concrete functions (or exactly matching an existing specialised version).