Dealing with calls is by far the most complicated bit of the execution model, and hence of the code generator. GHC uses an eval/apply strategy for compiling function calls; all the details of the design are in the paper Making a fast curry: push/enter vs. eval/apply for higher-order languages.
First, we need some terminology:
- The arity of a function is the number of lambdas statically used in the lambda-form of its definition. Note that arity is not deducible from the type. Example:
f :: Bool -> Bool -> Bool f = \x -> case x of True -> not False -> idHere, f has arity 1, even though its type suggests it takes two arguments. The point is that the compiled code for f will expect to be passed just one argument, x.
- The entry point (sometimes called the fast entry point) of a function of arity N expects its first N arguments to be passed in accordance with the standard calling conventions.
- A known call is a call of a function whose binding site is statically visible:
- The function is bound at top level in this module; or,
- The function is bound at top level in another module, and optimistion is on, so we can see the details (notably arity) of the function in the module's interface file; or,
- The function is bound by an let binding that encloses the call.
When compiling a call, there are several cases to consider, which are treated separately.
- Unknown function; a call in which we do not statically know what the function is. In that case we must do a "generic apply". This is so exciting that it deserves its own section.
- Known function, saturated call. The function is applied to exactly the right number of arguments to satisfy its arity. In that case, we simply load the arguments according to the standard entry convention, and tail-call (jump to) the function's entry point. On average, about 80% of all calls fall into this category (see the eval/apply paper for measurements).
- Known function, too few arguments. In this case, we want to build a partial application (PAP), and return with a pointer to the PAP in the return register. Since building a PAP is a complicated business, instead we just behave as for an unknown function call, which will end up calling into the Generic apply code, which will build the PAP for us.
- Known function, too many arguments. We want to save the extra arguments on the stack, push a return address, and then behave just like a saturated call. When the result comes back, we should behave like "unknown call". However, to avoid needing to generate code for a new continuation here, the return address that we push on the stack is that of an appropriate Generic apply function, which will perform the application of the extra arguments to the (unknown) function returned by the saturated call.
When compiling a call that has an unknown function, we must generate code to
- Evaluate the function
- Scrutinise the function value returned to see its arity, and dispatch into the same three cases as in the case of known calls:
- Exactly the right number of arguments: load them into the standard locations and tail-call the function's entry point
- Too few arguments: build a PAP
- Too many arguments: save the excess arguments, and tail call the function as for a saturated cal.
All of this takes quite a lot of code, so we pre-generate a whole bunch of generic-apply code sequencues, one for each combination of arguments. This code is generated by the tool utils/genapply, and the generated code appears in rts/AutoApply.cmm.
For example, if we find a call to an unknown function applied to two (boxed) Int arguments, load the function and its two arguments as for the standard entry convention and jump to stg_ap_pp_fast. This latter code is in rts/AutoApply.cmm, generated by the genapply tool. The "pp" part is the bit that says the code is specialised for two pointer arguments.
In addition to the family of stg_ap_<pattern>_fast functions for making calls to unknown functions with various argument patterns, there is a corresponding family of return addresses stg_ap_<pattern>_info. The idea is that you can push a continuation that will make a call to the function that is returned to it. For example, to push a continuation that will apply a single pointer argument, we would push the following words on the stack: