Version 5 (modified by ilya, 19 months 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

Let us compile the following program with -O2 -ddump-stranal flags:

f c p = case p 
          of (a, b) -> if c 
                       then (a, True) 
                       else (True, False)

The resulting demand signature for function f will be the following one:

Str=DmdType <S,U><S,U(UA)>m

This 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).

Current 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

Str=DmdType <L,U> {skY-><S,U>}

indicates 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.

Demand description

Strictness demands

  • 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.

  • 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.
  • 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).
  • S(s1 ... sn) -- a structured strictness demand on a product. It is at least head-strict, and perhaps more.
  • 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.

Absence demands

  • A -- when placed on a binder x it means that x is definitely unused.
  • U -- the value is used on some execution path. This demand is a top of usage domain.
  • H -- a head-used demand. Indicates that a product value is used itself, however its components are certainly ignored.
  • U(u1 ... un) -- a structured usage demand on a product. It is at least head-used, and perhaps more.
  • 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.

Additional information (demand signature suffix)

  • m -- a function returns a constructed product result (CPR)
  • b -- the function is a bottoming one, i.e., some decoration of error and friends.

Worker-Wrapper split


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. See the full list of relevant compiler parts for more details.