wiki:Commentary/Compiler/Demand

Version 3 (modified by ilya, 3 years ago) (diff)

--

Demand analyser in GHC

This page explains basics of the so-called demand analysis in GHC, comprising strictness and absence analyses. Meanings of demand signatures are explained and examples are provided. Also, components of the compiler possibly affected by the results of the demand analysis are listed with explanations provided.


Demand signatures

[TODO]

Worker-Wrapper split

[TODO]

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. Below, some of the demand-sensitive compiler parts are enumerated with indications, which bits of the demand information are actually used.

  • compiler/basicTypes/Demand.lhs -- contains all information about demands and operations on them, as well as about serialization/deserialization of demand signatures. This module is supposed to be changes whenever the demand nature should be enhanced;
  • compiler/basicTypes/Id.lhs -- implementation of identifiers contains a number of utility functions to check/set demand annotations of binders. All of them are just delegating to appropriate functions/fields of the IdInfo record;
  • compiler/basicTypes/IdInfo.lhs -- IdInfo record contains all information about demand and strictness annotations of an identifier. strictnessInfo contains a representation of an abstract two-point demand transformer of a binder, considered as a reference to a value. demandInfo indicates, which demand is put to the identifier, which is a function parameter, if the function is called in a strict/used context. seq*-functions are invoked to avoid memory leaks caused by transforming new ASTs by each of the compiler passes (i.e., no thunks pointing to the parts of the processed trees are left).
  • compiler/basicTypes/MkId.lhs -- A machinery, responsible for generation of worker-wrappers makes use of demands. For instance, when a signature for a worker is generated, the following strictness signature is created:
  wkr_sig = mkStrictSig (mkTopDmdType (replicate wkr_arity top) cpr_info)

In words, a non-bottoming demand type with N lazy/used arguments (top) is created for a worker, where N is just a worker's pre-computed arity. Also, particular demands are used when creating signatures for dictionary selectors (see mkDictSelId).

  • compiler/prelude/primops.txt.pp -- this file defines demand signatures for primitive operations, which are inserted by cpp pass on the module compiler/basicTypes/MkId.lhs;
  • compiler/coreSyn/CoreArity.lhs -- demand signatures are used in order to compute the unfolding info of a function: bottoming functions should no be unfolded. See exprBotStrictness_maybe and arityType.
  • compiler/coreSyn/CoreLint.lhs -- the checks are performed (in lintSingleBinding):
    • whether arity and demand type are consistent (only if demand analysis already happened);
    • if the binder is top-level or recursive, it's not demanded (i.e., its demand is not strict).
  • compiler/coreSyn/CorePrep.lhs -- strictness signatures are examining before converting expression to A-normal form.
  • compiler/coreSyn/MkCore.lhs -- a bottoming strictness signature created for error-like functions (see pc_bottoming_Id).
  • compiler/coreSyn/PprCore.lhs -- standard pretty-printing machinery, should be modified to change PP of demands.
  • compiler/iface/IfaceSyn.lhs -- serialization, grep for HsStrictness constructors.
  • compiler/iface/MkIface.lhs -- a client of IfaceSyn, see usages of HsStrictness.
  • compiler/iface/TcIface.lhs -- TODO