ghc-9.2.0.20210821: The GHC API
Safe HaskellSafe-Inferred
LanguageHaskell2010

GHC.Types.Demand

Description

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.

Synopsis

Demands

data Card Source #

Describes an interval of evaluation cardinalities. See Note [Evaluation cardinalities]

Constructors

C_00

{0} Absent.

C_01

{0,1} Used at most once.

C_0N

{0,1,n} Every possible cardinality; the top element.

C_11

{1} Strict and used once.

C_1N

{1,n} Strict and used (possibly) many times.

C_10

{} The empty interval; the bottom element of the lattice.

Instances

Instances details
Binary Card Source # 
Instance details

Defined in GHC.Types.Demand

Outputable Card Source #

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

Instance details

Defined in GHC.Types.Demand

Methods

ppr :: Card -> SDoc Source #

Eq Card Source # 
Instance details

Defined in GHC.Types.Demand

Methods

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

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

data Demand Source #

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.

Constructors

!Card :* !SubDemand 

Instances

Instances details
Binary Demand Source # 
Instance details

Defined in GHC.Types.Demand

Outputable Demand Source #

See Note [Demand notation]

Instance details

Defined in GHC.Types.Demand

Methods

ppr :: Demand -> SDoc Source #

Eq Demand Source # 
Instance details

Defined in GHC.Types.Demand

Methods

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

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

data SubDemand Source #

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

Constructors

Prod ![Demand]

Prod ds describes the evaluation context of a case scrutinisation on an expression of product type, where the product components are evaluated according to ds.

Instances

Instances details
Binary SubDemand Source # 
Instance details

Defined in GHC.Types.Demand

Outputable SubDemand Source #

See Note [Demand notation]

Instance details

Defined in GHC.Types.Demand

Methods

ppr :: SubDemand -> SDoc Source #

Eq SubDemand Source # 
Instance details

Defined in GHC.Types.Demand

mkProd :: [Demand] -> SubDemand Source #

A smart constructor for Prod, applying rewrite rules along the semantic equality Prod [polyDmd n, ...] === polyDmd n, simplifying to Poly SubDemands when possible. Note that this degrades boxity information! E.g. a polymorphic demand will never unbox.

viewProd :: Arity -> SubDemand -> Maybe [Demand] Source #

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

Algebra

Least upper bound

lubCard :: Card -> Card -> Card Source #

Denotes on Card.

lubDmd :: Demand -> Demand -> Demand Source #

Denotes on Demand.

Plus

plusCard :: Card -> Card -> Card Source #

Denotes + on Card.

plusDmd :: Demand -> Demand -> Demand Source #

Denotes + on Demand.

Multiply

multCard :: Card -> Card -> Card Source #

Denotes * on Card.

Predicates on Cardinalities and Demands

isAbs :: Card -> Bool Source #

True = upper bound is 0.

isUsedOnce :: Card -> Bool Source #

True = upper bound is 1.

isStrict :: Card -> Bool Source #

True = lower bound is 1.

isUsedOnceDmd :: Demand -> Bool Source #

Is the value used at most once?

isStrUsedDmd :: Demand -> Bool Source #

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

isStrictDmd :: Demand -> Bool Source #

Contrast with isStrictUsedDmd. See Note [Strict demands]

isTopDmd :: Demand -> Bool Source #

Used to suppress pretty-printing of an uninformative demand

isWeakDmd :: Demand -> Bool Source #

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.

Special demands

Demands used in PrimOp signatures

lazyApply1Dmd :: Demand Source #

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

lazyApply2Dmd :: Demand Source #

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

strictOnceApply1Dmd :: Demand Source #

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

strictManyApply1Dmd :: Demand Source #

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

Other Demand operations

oneifyCard :: Card -> Card Source #

Intersect with [0,1].

oneifyDmd :: Demand -> Demand Source #

Make a Demand evaluated at-most-once.

strictifyDmd :: Demand -> Demand Source #

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

strictifyDictDmd :: Type -> Demand -> Demand Source #

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.

peelCallDmd :: SubDemand -> (Card, SubDemand) Source #

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

mkCalledOnceDmd :: SubDemand -> SubDemand Source #

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

mkCalledOnceDmds :: Arity -> SubDemand -> SubDemand Source #

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

Extracting one-shot information

argOneShots Source #

Arguments

:: Demand

depending on saturation

-> [OneShotInfo] 

See Note [Computing one-shot info]

argsOneShots :: StrictSig -> Arity -> [[OneShotInfo]] Source #

See Note [Computing one-shot info]

saturatedByOneShots :: Int -> Demand -> Bool Source #

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

Demand environments

keepAliveDmdEnv :: DmdEnv -> IdSet -> DmdEnv Source #

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.

Divergence

data Divergence Source #

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

Instances details
Binary Divergence Source # 
Instance details

Defined in GHC.Types.Demand

Outputable Divergence Source # 
Instance details

Defined in GHC.Types.Demand

Methods

ppr :: Divergence -> SDoc Source #

Eq Divergence Source # 
Instance details

Defined in GHC.Types.Demand

isDeadEndDiv :: Divergence -> Bool Source #

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

Demand types

data DmdType Source #

Characterises how an expression * Evaluates its free variables (dt_env) * Evaluates its arguments (dt_args) * Diverges on every code path or not (dt_div)

Constructors

DmdType 

Fields

Instances

Instances details
Binary DmdType Source # 
Instance details

Defined in GHC.Types.Demand

Outputable DmdType Source # 
Instance details

Defined in GHC.Types.Demand

Methods

ppr :: DmdType -> SDoc Source #

Eq DmdType Source # 
Instance details

Defined in GHC.Types.Demand

Methods

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

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

Algebra

nopDmdType :: DmdType Source #

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.

lubDmdType :: DmdType -> DmdType -> DmdType Source #

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

PlusDmdArg

Other operations

deferAfterPreciseException :: DmdType -> DmdType Source #

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) in all free variables and arguments * has exnDiv Divergence result 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. See Note [Precise exceptions and strictness analysis]

Demand signatures

newtype StrictSig Source #

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

Constructors

StrictSig DmdType 

Instances

Instances details
Binary StrictSig Source # 
Instance details

Defined in GHC.Types.Demand

Outputable StrictSig Source # 
Instance details

Defined in GHC.Types.Demand

Methods

ppr :: StrictSig -> SDoc Source #

Eq StrictSig Source # 
Instance details

Defined in GHC.Types.Demand

mkStrictSigForArity :: Arity -> DmdType -> StrictSig Source #

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

isDeadEndSig :: StrictSig -> Bool Source #

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

appIsDeadEnd :: StrictSig -> Int -> Bool Source #

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

Handling arity adjustments

prependArgsStrictSig :: Int -> StrictSig -> StrictSig Source #

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

etaConvertStrictSig :: Arity -> StrictSig -> StrictSig Source #

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 prependArgsStrictSig, 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 Source #

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 StrictSig] and Note [What are demand signatures?].

dmdTransformSig :: StrictSig -> DmdTransformer Source #

Extrapolate a demand signature (StrictSig) into a DmdTransformer.

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

dmdTransformDataConSig :: Arity -> DmdTransformer Source #

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

dmdTransformDictSelSig :: StrictSig -> DmdTransformer Source #

A special DmdTransformer for dictionary selectors that feeds the demand on the result into the indicated dictionary component (if saturated).

Trim to a type shape

data TypeShape Source #

Instances

Instances details
Outputable TypeShape Source # 
Instance details

Defined in GHC.Types.Demand

Methods

ppr :: TypeShape -> SDoc Source #

seqing stuff

Zapping usage information

zapDmdEnvSig :: StrictSig -> StrictSig Source #

Remove the demand environment from the signature.

zapUsedOnceDemand :: Demand -> Demand Source #

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

zapUsedOnceSig :: StrictSig -> StrictSig Source #

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