Demand analyser in GHC
This wiki page focuses on information that GHC devs need to know about demand analysis and the corresponding worker/wrapper transformation that feeds on strictness and absence info.
As a first step, it is recommended to get up to speed on demand analysis and notation of demand signatures that is relevant to users of GHC, as explained in the user's guide entry on
Unfortunately, there isn't a single paper (yet) that describes demand analysis as a whole. The relevant sources are:
- The demand-analyser draft paper (2017) is as yet unpublished, but gives the most accurate overview of the way GHC's demand analyser works.
- The cardinality paper (2014) describes what we call usage analysis today and introduces higher-order call demands. Also described in the demand-analysis draft paper.
- SG wrote a more colloquial blog post series about strictness analysis. Uses old demand notation, unfortunately.
See the info in the user's guide entry on
Demand analysis in GHC drives the worker-wrapper transformation, which exposes specialised calling conventions to the rest of the compiler. In particular, the worker-wrapper transformation implements the unboxing optimisation.
The worker-wrapper transformation splits each
f into a wrapper, with the
ordinary calling convention, and a worker, with a specialised
calling convention. The wrapper serves as an impedance-matcher to the
worker; it simply calls the worker using the specialised calling convention.
The transformation can be expressed directly in GHC's intermediate language.
f is defined thus:
f :: (Int,Int) -> Int f p = <rhs>
and that we know that
f is strict in its argument (the pair, that is),
and uses its components.
What worker-wrapper split shall we make? Here is one
f :: (Int,Int) -> Int f p = case p of (a,b) -> $wf a b $wf :: Int -> Int -> Int $wf a b = let p = (a,b) in <rhs>
Now the wrapper,
f, can be inlined at every call site, so that
the caller evaluates
p, passing only the components to the worker
$wf, thereby implementing the unboxing transformation.
But what if
f did not use
b? Then it would be silly to
pass them to the worker
$wf. Hence the need for absence
analysis. Suppose, then, that we know that
b is not needed. Then
we can transform to:
f :: (Int,Int) -> Int f p = case p of (a,b) -> $wf a $wf :: Int -> Int $wf a = let p = (a,error "abs") in <rhs>
b is not needed, we can avoid passing it from the wrapper to
the worker; while in the worker, we can use
error "abs" instead of
In short, the worker-wrapper transformation allows the knowledge gained from strictness and absence analysis to be exposed to the rest of the compiler simply by performing a local transformation on the function definition. Then ordinary inlining and case elimination will do the rest, transformations the compiler does anyway.
There's ongoing discussion about improvements to the demand analyser.
- Inspired by Call Arity's Co-Call graphs, this page discusses how to make the LetUp rule more flow sensitive
Relevant compiler parts
Multiple parts of GHC are sensitive to changes in the nature of demand signatures and results of the demand analysis, which might cause unexpected errors when hacking into demands. This list enumerates the parts of the compiler that are sensitive to demand, with brief summaries of how so.
For the Journal version of the demand analysis paper we created some instrumentation
- to measure how often a thunk is entered (to see if the update code was useful), and also
- to find out why a thunk is expected to be entered multiple times.
The code adds significant complexity to the demand analyser and the code generator, so we decided not to merge it into master (not even hidden behind flags), but should it ever have to be resurrected, it can be found in the branch
wip/T10613. View the full diff (at least as long as the link is valid, as it hard-codes the base commit).