GHC.Types.Demand

A language to express the evaluation context of an expression as a Demand and track how an expression evaluates free variables and arguments in turn as a DmdType.

Lays out the abstract domain for GHC.Core.Opt.DmdAnal.

Demands

data Boxity

Constructors

Boxed

Unboxed

Instances

Eq Boxity

Defined in GHC.Types.Basic

Methods

(==) :: Boxity -> Boxity -> Bool

(/=) :: Boxity -> Boxity -> Bool

Data Boxity

Defined in GHC.Types.Basic

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Boxity -> c Boxity

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Boxity

toConstr :: Boxity -> Constr

dataTypeOf :: Boxity -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Boxity)

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Boxity)

gmapT :: (forall b. Data b => b -> b) -> Boxity -> Boxity

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Boxity -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Boxity -> r

gmapQ :: (forall d. Data d => d -> u) -> Boxity -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Boxity -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Boxity -> m Boxity

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Boxity -> m Boxity

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Boxity -> m Boxity

Outputable Boxity

Defined in GHC.Types.Basic

Methods

ppr :: Boxity -> SDoc

Binary Boxity

Defined in GHC.Types.Basic

Methods

put_ :: BinHandle -> Boxity -> IO ()

put :: BinHandle -> Boxity -> IO (Bin Boxity)

get :: BinHandle -> IO Boxity

data Card where

Describes an interval of evaluation cardinalities. See Note [Evaluation cardinalities] See Note [Bit vector representation for Card]

Bundled Patterns

pattern C_00 :: Card

Absent, {0}. Pretty-printed as A.

pattern C_01 :: Card

Used at most once, {0,1}. Pretty-printed as M.

pattern C_0N :: Card

Every possible cardinality; the top element, {0,1,n}. Pretty-printed as L.

pattern C_10 :: Card

Bottom, {}. Pretty-printed as A.

pattern C_11 :: Card

Strict and used once, {1}. Pretty-printed as 1.

pattern C_1N :: Card

Strict and used (possibly) many times, {1,n}. Pretty-printed as S.

Instances

Eq Card

Defined in GHC.Types.Demand

Methods

(==) :: Card -> Card -> Bool

(/=) :: Card -> Card -> Bool

Show Card

Defined in GHC.Types.Demand

Methods

showsPrec :: Int -> Card -> ShowS

show :: Card -> String

showList :: [Card] -> ShowS

Outputable Card

See Note [Demand notation] Current syntax was discussed in #19016.

Defined in GHC.Types.Demand

Methods

ppr :: Card -> SDoc

Binary Card

Defined in GHC.Types.Demand

Methods

put_ :: BinHandle -> Card -> IO ()

put :: BinHandle -> Card -> IO (Bin Card)

get :: BinHandle -> IO Card

type CardNonAbs = Card

A subtype of Card for which the upper bound is never 0 (no C_00 or C_10). The only four inhabitants are C_01, C_0N, C_11, C_1N. Membership can be tested with isCardNonAbs. See D and Call for use sites and explanation.

type CardNonOnce = Card

A subtype of Card for which the upper bound is never 1 (no C_01 or C_11). The only four inhabitants are C_00, C_0N, C_10, C_1N. Membership can be tested with isCardNonOnce. See Poly for use sites and explanation.

data Demand

A demand describes a scaled evaluation context, e.g. how many times and how deep the denoted thing is evaluated.

The "how many" component is represented by a Cardinality. The "how deep" component is represented by a SubDemand. Examples (using Note [Demand notation]):

• seq puts demand 1A on its first argument: It evaluates the argument strictly (1), but not any deeper (A).
• fst puts demand 1P(1L,A) on its argument: It evaluates the argument pair strictly and the first component strictly, but no nested info beyond that (L). Its second argument is not used at all.
• $ puts demand 1C1(L) on its first argument: It calls (C) the argument function with one argument, exactly once (1). No info on how the result of that call is evaluated (L).
• maybe puts demand MCM(L) on its second argument: It evaluates the argument function at most once ((M)aybe) and calls it once when it is evaluated.
• fst p + fst p puts demand SP(SL,A) on p: It's 1P(1L,A) multiplied by two, so we get S (used at least once, possibly multiple times).

This data type is quite similar to Scaled SubDemand, but it's scaled by Card, which is an interval on Multiplicity, the upper bound of which could be used to infer uniqueness types. Also we treat AbsDmd and BotDmd specially, as the concept of a SubDemand doesn't apply when there isn't any evaluation at all. If you don't care, simply use (:*).

Constructors

BotDmd

A bottoming demand, produced by a diverging function (C_10), hence there is no SubDemand that describes how it was evaluated.

AbsDmd

An absent demand: Evaluated exactly 0 times (C_00), hence there is no SubDemand that describes how it was evaluated.

Bundled Patterns

pattern (:*) :: HasDebugCallStack => Card -> SubDemand -> Demand

c :* sd is a demand that says "evaluated c times, and each time it was evaluated, it was at least as deep as sd".

Matching on this pattern synonym is a complete match. If the matched demand was AbsDmd, it will match as C_00 :* seqSubDmd. If the matched demand was BotDmd, it will match as C_10 :* botSubDmd. The builder of this pattern synonym simply discards the SubDemand if the Card was absent and returns AbsDmd or BotDmd instead. It will assert that the discarded sub-demand was seqSubDmd and botSubDmd, respectively.

Call sites should consider whether they really want to look at the SubDemand of an absent demand and match on AbsDmd and/or BotDmd otherwise. Really, any other SubDemand would be allowed and might work better, depending on context.

Instances

Eq Demand

Defined in GHC.Types.Demand

Methods

(==) :: Demand -> Demand -> Bool

(/=) :: Demand -> Demand -> Bool

Outputable Demand

See Note [Demand notation]

Defined in GHC.Types.Demand

Methods

ppr :: Demand -> SDoc

Binary Demand

Defined in GHC.Types.Demand

Methods

put_ :: BinHandle -> Demand -> IO ()

put :: BinHandle -> Demand -> IO (Bin Demand)

get :: BinHandle -> IO Demand

data SubDemand

A sub-demand describes an evaluation context, e.g. how deep the denoted thing is evaluated. See Demand for examples.

The nested SubDemand d of a Call Cn(d) is relative to a single such call. E.g. The expression f 1 2 + f 3 4 puts call demand SCS(C1(L)) on f: f is called exactly twice (S), each time exactly once (1) with an additional argument.

The nested Demands dn of a Prod P(d1,d2,...) apply absolutely: If dn is a used once demand (cf. isUsedOnce), then that means that the denoted sub-expression is used once in the entire evaluation context described by the surrounding Demand. E.g., LP(ML) means that the field of the denoted expression is used at most once, although the entire expression might be used many times.

See Note [Call demands are relative] and Note [Demand notation]. See also Note [Why Boxity in SubDemand and not in Demand?].

Constructors

Poly !Boxity !CardNonOnce

Polymorphic demand, the denoted thing is evaluated arbitrarily deep, with the specified cardinality at every level. The Boxity applies only to the outer evaluation context as well as all inner evaluation context. See Note [Boxity in Poly] for why we want it to carry Boxity. Expands to Call via viewCall and to Prod via viewProd.

Poly b n is semantically equivalent to Prod b [n :* Poly b n, ...] or Call n (Poly Boxed n)@. viewCall and viewProd do these rewrites.

In Note [Demand notation]: L === P(L,L,...) and L === CL(L), B === P(B,B,...) and B === CB(B), !A === !P(A,A,...) and !A === !CA(A), and so on.

We'll only see Poly with C_10 (B), C_00 (A), C_0N (L) and sometimes C_1N (S) through plusSubDmd, never C_01 (M) or C_11 (1) (grep the source code). Hence CardNonOnce, which is closed under lub and plus.

Prod !Boxity ![Demand]

Prod b ds describes the evaluation context of a case scrutinisation on an expression of product type, where the product components are evaluated according to ds. The Boxity b says whether or not the box of the product was used.

Instances

Eq SubDemand

We have to respect Poly rewrites through viewCall and viewProd.

Defined in GHC.Types.Demand

Methods

(==) :: SubDemand -> SubDemand -> Bool

(/=) :: SubDemand -> SubDemand -> Bool

Outputable SubDemand

See Note [Demand notation]

Defined in GHC.Types.Demand

Methods

ppr :: SubDemand -> SDoc

Binary SubDemand

Defined in GHC.Types.Demand

Methods

put_ :: BinHandle -> SubDemand -> IO ()

put :: BinHandle -> SubDemand -> IO (Bin SubDemand)

get :: BinHandle -> IO SubDemand

mkProd :: Boxity -> [Demand] -> SubDemand

A smart constructor for Prod, applying rewrite rules along the semantic equality Prod b [n :* Poly Boxed n, ...] === Poly b n, simplifying to Poly SubDemands when possible. Examples:

• Rewrites P(L,L) (e.g., arguments Boxed, [L,L]) to L
• Rewrites !P(L!L,L!L) (e.g., arguments Unboxed, [L!L,L!L]) to !L
• Does not rewrite P(1L), P(L!L), !P(L) or P(L,A)

viewProd :: Arity -> SubDemand -> Maybe (Boxity, [Demand])

viewProd n sd interprets sd as a Prod of arity n, expanding Poly demands as necessary.

Algebra

absDmd :: Demand

topDmd :: Demand

botDmd :: Demand

seqDmd :: Demand

topSubDmd :: SubDemand

Least upper bound

lubCard :: Card -> Card -> Card

Denotes ∪ on Card.

lubDmd :: Demand -> Demand -> Demand

Denotes ∪ on Demand.

lubSubDmd :: SubDemand -> SubDemand -> SubDemand

Denotes ∪ on SubDemand.

Plus

plusCard :: Card -> Card -> Card

Denotes + on lower and upper bounds of Card.

plusDmd :: Demand -> Demand -> Demand

Denotes + on Demand.

plusSubDmd :: SubDemand -> SubDemand -> SubDemand

Denotes + on SubDemand.

Multiply

multCard :: Card -> Card -> Card

Denotes * on lower and upper bounds of Card.

multDmd :: Card -> Demand -> Demand

multSubDmd :: Card -> SubDemand -> SubDemand

Predicates on Cardinalities and Demands

isAbs :: Card -> Bool

True = upper bound is 0.

isUsedOnce :: Card -> Bool

True = upper bound is 1.

isStrict :: Card -> Bool

True = lower bound is 1.

isAbsDmd :: Demand -> Bool

isUsedOnceDmd :: Demand -> Bool

Is the value used at most once?

isStrUsedDmd :: Demand -> Bool

Not absent and used strictly. See Note [Strict demands]

isStrictDmd :: Demand -> Bool

Contrast with isStrictUsedDmd. See Note [Strict demands]

isTopDmd :: Demand -> Bool

Used to suppress pretty-printing of an uninformative demand

isWeakDmd :: Demand -> Bool

We try to avoid tracking weak free variable demands in strictness signatures for analysis performance reasons. See Note [Lazy and unleashable free variables] in GHC.Core.Opt.DmdAnal.

onlyBoxedArguments :: DmdSig -> Bool

True when the signature indicates all arguments are boxed

Special demands

evalDmd :: Demand

Demands used in PrimOp signatures

lazyApply1Dmd :: Demand

First argument of catch#: MCM(L). Evaluates its arg lazily, but then applies it exactly once to one argument.

lazyApply2Dmd :: Demand

Second argument of catch#: MCM(C1(L)). Calls its arg lazily, but then applies it exactly once to an additional argument.

strictOnceApply1Dmd :: Demand

First argument of 'GHC.Exts.maskAsyncExceptions#': 1C1(L). Called exactly once.

strictManyApply1Dmd :: Demand

First argument of 'GHC.Exts.atomically#': SCS(L). Called at least once, possibly many times.

Other Demand operations

oneifyCard :: Card -> Card

Intersect with [0,1].

oneifyDmd :: Demand -> Demand

Make a Demand evaluated at-most-once.

strictifyDmd :: Demand -> Demand

Make a Demand evaluated at-least-once (e.g. strict).

strictifyDictDmd :: Type -> Demand -> Demand

If the argument is a used non-newtype dictionary, give it strict demand. Also split the product type & demand and recur in order to similarly strictify the argument's contained used non-newtype superclass dictionaries. We use the demand as our recursive measure to guarantee termination.

lazifyDmd :: Demand -> Demand

Make a Demand lazy, setting all lower bounds (outside Calls) to 0.

peelCallDmd :: SubDemand -> (Card, SubDemand)

Peels one call level from the sub-demand, and also returns how many times we entered the lambda body.

peelManyCalls :: Int -> SubDemand -> Card

mkCalledOnceDmd :: SubDemand -> SubDemand

Wraps the SubDemand with a one-shot call demand: d -> C1(d).

mkCalledOnceDmds :: Arity -> SubDemand -> SubDemand

mkCalledOnceDmds n d returns C1(C1...(C1 d)) where there are n C1's.

mkWorkerDemand :: Int -> Demand

Extracting one-shot information

argOneShots

Arguments

:: Demand

depending on saturation

-> [OneShotInfo]

See Note [Computing one-shot info]

argsOneShots :: DmdSig -> Arity -> [[OneShotInfo]]

See Note [Computing one-shot info]

saturatedByOneShots :: Int -> Demand -> Bool

saturatedByOneShots n CM(CM(...)) = True = There are at least n nested CM(..) calls. See Note [Demand on the worker] in GHC.Core.Opt.WorkWrap

Manipulating Boxity of a Demand

unboxDeeplyDmd :: Demand -> Demand

Sets Boxity to Unboxed for the Demand, recursing into Prods.

Demand environments

type DmdEnv = VarEnv Demand

emptyDmdEnv :: DmdEnv

keepAliveDmdEnv :: DmdEnv -> IdSet -> DmdEnv

keepAliveDmdType dt vs makes sure that the Ids in vs have some usage in the returned demand types -- they are not Absent. See Note [Absence analysis for stable unfoldings and RULES] in GHC.Core.Opt.DmdAnal.

reuseEnv :: DmdEnv -> DmdEnv

Divergence

data Divergence

Divergence characterises whether something surely diverges. Models a subset lattice of the following exhaustive set of divergence results:

n

nontermination (e.g. loops)

i

throws imprecise exception

p

throws precise exceTtion

c

converges (reduces to WHNF).

The different lattice elements correspond to different subsets, indicated by juxtaposition of indicators (e.g. nc definitely doesn't throw an exception, and may or may not reduce to WHNF).

            Dunno (nipc)
                 |
           ExnOrDiv (nip)
                 |
           Diverges (ni)

As you can see, we don't distinguish n and i. See Note [Precise exceptions and strictness analysis] for why p is so special compared to i.

Constructors

Diverges

Definitely throws an imprecise exception or diverges.

ExnOrDiv

Definitely throws a *precise* exception, an imprecise exception or diverges. Never converges, hence isDeadEndDiv! See scenario 1 in Note [Precise exceptions and strictness analysis].

Dunno

Might diverge, throw any kind of exception or converge.

Instances

Eq Divergence

Defined in GHC.Types.Demand

Methods

(==) :: Divergence -> Divergence -> Bool

(/=) :: Divergence -> Divergence -> Bool

Outputable Divergence

Defined in GHC.Types.Demand

Methods

ppr :: Divergence -> SDoc

Binary Divergence

Defined in GHC.Types.Demand

Methods

put_ :: BinHandle -> Divergence -> IO ()

put :: BinHandle -> Divergence -> IO (Bin Divergence)

get :: BinHandle -> IO Divergence

topDiv :: Divergence

botDiv :: Divergence

exnDiv :: Divergence

lubDivergence :: Divergence -> Divergence -> Divergence

isDeadEndDiv :: Divergence -> Bool

True if the Divergence indicates that evaluation will not return. See Note [Dead ends].

Demand types

data DmdType

Characterises how an expression

• Evaluates its free variables (dt_env)
• Evaluates its arguments (dt_args)
• Diverges on every code path or not (dt_div)

Equality is defined modulo defaultFvDmds in dt_env. See Note [Demand type Equality].

Constructors

DmdType

Fields

• dt_env :: !DmdEnv

  Demand on explicitly-mentioned free variables

• dt_args :: ![Demand]

  Demand on arguments

• dt_div :: !Divergence

  Whether evaluation diverges. See Note [Demand type Divergence]

Instances

Eq DmdType

See Note [Demand type Equality].

Defined in GHC.Types.Demand

Methods

(==) :: DmdType -> DmdType -> Bool

(/=) :: DmdType -> DmdType -> Bool

Outputable DmdType

Defined in GHC.Types.Demand

Methods

ppr :: DmdType -> SDoc

Binary DmdType

Defined in GHC.Types.Demand

Methods

put_ :: BinHandle -> DmdType -> IO ()

put :: BinHandle -> DmdType -> IO (Bin DmdType)

get :: BinHandle -> IO DmdType

dmdTypeDepth :: DmdType -> Arity

Algebra

nopDmdType :: DmdType

The demand type of doing nothing (lazy, absent, no Divergence information). Note that it is 'not' the top of the lattice (which would be "may use everything"), so it is (no longer) called topDmdType.

botDmdType :: DmdType

lubDmdType :: DmdType -> DmdType -> DmdType

Compute the least upper bound of two DmdTypes elicited /by the same incoming demand/!

plusDmdType :: DmdType -> PlusDmdArg -> DmdType

multDmdType :: Card -> DmdType -> DmdType

PlusDmdArg

type PlusDmdArg = (DmdEnv, Divergence)

mkPlusDmdArg :: DmdEnv -> PlusDmdArg

toPlusDmdArg :: DmdType -> PlusDmdArg

Other operations

peelFV :: DmdType -> Var -> (DmdType, Demand)

findIdDemand :: DmdType -> Var -> Demand

addDemand :: Demand -> DmdType -> DmdType

splitDmdTy :: DmdType -> (Demand, DmdType)

deferAfterPreciseException :: DmdType -> DmdType

When e is evaluated after executing an IO action that may throw a precise exception, we act as if there is an additional control flow path that is taken if e throws a precise exception. The demand type of this control flow path * is lazy and absent (topDmd) and boxed in all free variables and arguments * has exnDiv Divergence result See Note [Precise exceptions and strictness analysis]

So we can simply take a variant of nopDmdType, exnDmdType. Why not nopDmdType? Because then the result of e can never be exnDiv! That means failure to drop dead-ends, see #18086.

keepAliveDmdType :: DmdType -> VarSet -> DmdType

See keepAliveDmdEnv.

Demand signatures

newtype DmdSig

The depth of the wrapped DmdType encodes the arity at which it is safe to unleash. Better construct this through mkDmdSigForArity. See Note [Understanding DmdType and DmdSig]

Constructors

DmdSig DmdType

Instances

Eq DmdSig

Defined in GHC.Types.Demand

Methods

(==) :: DmdSig -> DmdSig -> Bool

(/=) :: DmdSig -> DmdSig -> Bool

Outputable DmdSig

Defined in GHC.Types.Demand

Methods

ppr :: DmdSig -> SDoc

Binary DmdSig

Defined in GHC.Types.Demand

Methods

put_ :: BinHandle -> DmdSig -> IO ()

put :: BinHandle -> DmdSig -> IO (Bin DmdSig)

get :: BinHandle -> IO DmdSig

mkDmdSigForArity :: Arity -> DmdType -> DmdSig

Turns a DmdType computed for the particular Arity into a DmdSig unleashable at that arity. See Note [Understanding DmdType and DmdSig].

mkClosedDmdSig :: [Demand] -> Divergence -> DmdSig

splitDmdSig :: DmdSig -> ([Demand], Divergence)

dmdSigDmdEnv :: DmdSig -> DmdEnv

hasDemandEnvSig :: DmdSig -> Bool

nopSig :: DmdSig

botSig :: DmdSig

isTopSig :: DmdSig -> Bool

isDeadEndSig :: DmdSig -> Bool

True if the signature diverges or throws an exception in a saturated call. See Note [Dead ends].

appIsDeadEnd :: DmdSig -> Int -> Bool

Returns true if an application to n args would diverge or throw an exception.

If a function having botDiv is applied to a less number of arguments than its syntactic arity, we cannot say for sure that it is going to diverge. Hence this function conservatively returns False in that case. See Note [Dead ends].

trimBoxityDmdSig :: DmdSig -> DmdSig

Handling arity adjustments

prependArgsDmdSig :: Int -> DmdSig -> DmdSig

Add extra (topDmd) arguments to a strictness signature. In contrast to etaConvertDmdSig, this prepends additional argument demands. This is used by FloatOut.

etaConvertDmdSig :: Arity -> DmdSig -> DmdSig

We are expanding (x y. e) to (x y z. e z) or reducing from the latter to the former (when the Simplifier identifies a new join points, for example). In contrast to prependArgsDmdSig, this appends extra arg demands if necessary. This works by looking at the DmdType (which was produced under a call demand for the old arity) and trying to transfer as many facts as we can to the call demand of new arity. An arity increase (resulting in a stronger incoming demand) can retain much of the info, while an arity decrease (a weakening of the incoming demand) must fall back to a conservative default.

Demand transformers from demand signatures

type DmdTransformer = SubDemand -> DmdType

A demand transformer is a monotone function from an incoming evaluation context (SubDemand) to a DmdType, describing how the denoted thing (i.e. expression, function) uses its arguments and free variables, and whether it diverges.

See Note [Understanding DmdType and DmdSig] and Note [What are demand signatures?].

dmdTransformSig :: DmdSig -> DmdTransformer

Extrapolate a demand signature (DmdSig) into a DmdTransformer.

Given a function's DmdSig and a SubDemand for the evaluation context, return how the function evaluates its free variables and arguments.

dmdTransformDataConSig :: Arity -> DmdTransformer

A special DmdTransformer for data constructors that feeds product demands into the constructor arguments.

dmdTransformDictSelSig :: DmdSig -> DmdTransformer

A special DmdTransformer for dictionary selectors that feeds the demand on the result into the indicated dictionary component (if saturated). See Note [Demand transformer for a dictionary selector].

Trim to a type shape

data TypeShape

Constructors

TsFun TypeShape

TsProd [TypeShape]

TsUnk

Instances

Outputable TypeShape

Defined in GHC.Types.Demand

Methods

ppr :: TypeShape -> SDoc

trimToType :: Demand -> TypeShape -> Demand

trimBoxity :: Demand -> Demand

Drop all boxity

seqing stuff

seqDemand :: Demand -> ()

seqDemandList :: [Demand] -> ()

seqDmdType :: DmdType -> ()

seqDmdSig :: DmdSig -> ()

Zapping usage information

zapUsageDemand :: Demand -> Demand

zapDmdEnvSig :: DmdSig -> DmdSig

Remove the demand environment from the signature.

zapUsedOnceDemand :: Demand -> Demand

Remove all `C_01 :*` info (but not CM sub-demands) from the demand

zapUsedOnceSig :: DmdSig -> DmdSig

Remove all `C_01 :*` info (but not CM sub-demands) from the strictness signature