Changes between Version 4 and Version 5 of Commentary/Compiler/Demand

Sep 17, 2012 10:43:48 AM (5 years ago)



  • Commentary/Compiler/Demand

    v4 v5  
    99== Demand signatures ==
    11 [TODO]
     11Let us compile the following program with `-O2 -ddump-stranal` flags:
     14f c p = case p
     15          of (a, b) -> if c
     16                       then (a, True)
     17                       else (True, False)
     20The resulting demand signature for function `f` will be the following one:
     23Str=DmdType <S,U><S,U(UA)>m
     26This should be read as "`f` puts stricts demands on both its arguments (hence, `S`); `f` might use its first  and second arguments. but in the second argument (which is a product), the second component is ignored". The suffix `m` in the demand signature indicates that the function returns '''CPR''', a constructed product result (for more information on CPR see the JFP paper [ Constructed Product Result Analysis for Haskell]).
     28Current implementation of demand analysis in Haskell performs annotation of all binders with demands, put on them in the context of their use. For functions, it is assumed, that the result of the function is used strictly. The analysis infers strictness and usage information separately, as two components of a cartesian product domain. The same analysis also performs inference CPR and bottoming properties for functions, which can be read from the suffix of the signature. Demand signatures of inner definitions may also include ''demand environments'' that indicate demands, which a closure puts to its free variables, once strictly used, e.g. the signature
     31Str=DmdType <L,U> {skY-><S,U>}
     34indicates that the function has one parameter, which is used lazily (hence `<L,U>`), however, when its result is used strictly, the free variable `skY` in its body is also used strictly.
     36=== Demand description ===
     38Strictness demands
     40  * `B` -- a ''hyperstrict'' demand. The expression `e` puts this demand on its argument `x` if every evaluation of `e` is guaranteed to diverge, regardless of the value of the argument. We call this demand ''hyperstrict'' because it is safe to evaluate `x` to arbitrary depth before evaluating `e`.
     42  * `L`  -- a ''lazy'' demand. If an expression `e` places demand `L` on a variable  `x`, we can deduce nothing about how `e` uses `x`. `L` is the completely uninformative demand, the top element of the lattice.
     44  * `S` -- a ''head-strict'' demand.  If `e` places demand `S` on `x` then `e` evaluates `x` to at least head-normal form; that is, to the outermost constructor of `x`.  The demand `S(L ... L)` places a lazy demand on all the components, and so is equivalent to `S`; hence the identity `S = S(L ... L)`.
     46  * `S(s1 ... sn)` -- a structured strictness demand on a product.  It is at least head-strict, and perhaps more.
     48  * `C(s)`  -- a ''call-demand'', when placed on a binder `x`, indicates that the value is a function, which is always called and its result is used according to the demand `s`.
     51Absence demands
     53  * `A` -- when placed on a binder `x` it means that `x` is definitely unused.
     55  * `U` -- the value is used on some execution path.  This demand is a top of usage domain.
     57  * `H` -- a ''head-used'' demand. Indicates that a product value is used itself, however its components are certainly ignored.
     59  * `U(u1 ... un)` -- a structured usage demand on a product. It is at least head-used, and perhaps more.
     61  * `C(u)` -- a ''call-demand'' for usage information. When put on a binder `x`, indicates that `x` in all executions paths where `x` is used, it is ''applied'' to some argument, and the result of the application is used with a demand `u`.
     63Additional information (demand signature suffix)
     65  * `m`  -- a function returns a constructed product result (CPR)
     67  * `b` -- the function is a ''bottoming'' one, i.e., some decoration of `error` and friends.
    1369== Worker-Wrapper split ==
    1773== Relevant compiler parts ==
    19 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.
    21   * `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;
    23   * `compiler/stranal/DmdAnal.lhs` -- the demand analysis itself. Check multiple comments for to figure out main principles of the algorithm.
    25   * `compiler/stranal/WorkWrap.lhs` -- a worker-wrapper transform, main client of the demand analysis. The function split is performed in `worthSplittingFun` basing on demand annotations of a function's parameters.
    27   *  `compiler/stranal/WwLib.lhs` -- a helper module for the worker-wrapper machinery. The "deep" splitting of a product type argument makes use of the strictness info and is implemented by the function `mkWWstr_one`. The function `mkWWcpr` makes use of the CPR info.
    29   * `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;
    31   * `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).
    33   * `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:
    35 {{{
    36   wkr_sig = mkStrictSig (mkTopDmdType (replicate wkr_arity top) cpr_info)
    37 }}}
    39   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`).
    41   * `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`;
    43   * `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`.
    45   * `compiler/coreSyn/CoreLint.lhs` -- the checks are performed (in `lintSingleBinding`):
    46     * whether arity and demand type are consistent (only if demand analysis already happened);
    47     * if the binder is top-level or recursive, it's not demanded (i.e., its demand is not strict).
    49   * `compiler/coreSyn/CorePrep.lhs` -- strictness signatures are examining before converting expression to A-normal form.
    51   * `compiler/coreSyn/MkCore.lhs` -- a bottoming strictness signature created for `error`-like functions (see `pc_bottoming_Id`).
    53   * `compiler/coreSyn/PprCore.lhs` -- standard pretty-printing machinery, should be modified to change PP of demands.
    55   * `compiler/iface/IfaceSyn.lhs`  -- serialization, grep for `HsStrictness` constructors.
    57   * `compiler/iface/MkIface.lhs`  -- a client of `IfaceSyn`, see usages of `HsStrictness`.
    59   * `compiler/iface/TcIface.lhs` -- the function `tcUnfolding` checks if an identifier binds a bottoming function in order to decide if it should be unfolded or not
    61   * `compiler/main/TidyPgm.lhs` -- Multiple checks of an identifier to bind a bottoming expression, running a cheap-an-cheerful bottom analyser. See `addExternal` and occurrences of `exprBotStrictness_maybe`.
    63   * `compiler/simplCore/SetLevels.lhs` -- It is important to zap demand information, when an identifier is moved to a top-level (due to let-floating), hence look for occurrences of `zapDemandIdInfo`.
    65   * `compiler/simplCore/SimplCore.lhs` -- this module is responsible for running the demand analyser and the subsequent worker-wrapper split passes.
    67   * `compiler/simplCore/SimplUtils.lhs`  -- is a new arity is less than the arity of the demand type, a warning is emitted; check `tryEtaExpand`.
    69   * `compiler/specialise/SpecConstr.lhs` -- strictness info is used when creating a specialized copy of a function, see `spec_one` and `calcSpecStrictness`.
     75Multiple 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. See the [wiki:Commentary/Compiler/Demand/RelevantParts full list of relevant compiler parts] for more details.