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.
Sat 9 SepDisplayed time zone: Belfast change
14:00 - 15:00
Working in CoreHIW at L1
Chair(s): Adam Gundry Well-Typed LLP
|Why GHC Core and Linear Logic Should be Best Friends|
|Demand Analysis vs. Call Arity|
Sebastian Graf Karlsruhe Institute of Technology
|Lightning Talk Slot #2|