Demand Analysis vs. Call Arity
GHC integrates a number of analyses on its Core language to enable optimizations such as the worker/wrapper transformation and arity expansion to produce efficient code.
Of vital importance is GHC’s Demand Analyser: Besides gathering strictness information for the simplifier, an interleaved usage analysis answers questions about maximum cardinality, such as
- At most how many times is a binding accessed during a single evaluation?
- At most how many times is the body of a lambda expression called, relative to its enclosing expression?
There is also Call Arity, an analysis trying to eta-expand bindings based on usage information. Call Arity interleaves an arity analysis with a usage analysis to justify eta-expansion of single-entry thunks.
The analyses operate independent from another, while both answer related questions about usage. My master’s thesis was concerned with assessing if an information flow between analyses would be beneficial and whether they could even be combined into a single analysis. The latter seems to be the case, but there were some problems to be solved with respect to iteration order and correspondence of analysis domains.
This talk introduces the generalising usage analysis and how the results of both analyses can be reconstructed. We will see how the need for a graph-baesd approach to data-flow analysis detached from the syntax tree arises. Finally, we close with a discussion about practicability and evaluation results.