{-
(c) The GRASP/AQUA Project, Glasgow University, 1993-1998


                        -----------------
                        A demand analysis
                        -----------------
-}

{-# LANGUAGE CPP #-}

module GHC.Core.Opt.DmdAnal ( dmdAnalProgram ) where

#include "GhclibHsVersions.h"

import GHC.Prelude

import GHC.Driver.Session
import GHC.Core.Opt.WorkWrap.Utils
import GHC.Types.Demand   -- All of it
import GHC.Core
import GHC.Core.Multiplicity ( scaledThing )
import GHC.Core.Seq     ( seqBinds )
import GHC.Utils.Outputable
import GHC.Types.Var.Env
import GHC.Types.Basic
import Data.List        ( mapAccumL )
import GHC.Core.DataCon
import GHC.Types.ForeignCall ( isSafeForeignCall )
import GHC.Types.Id
import GHC.Types.Id.Info
import GHC.Core.Utils
import GHC.Core.TyCon
import GHC.Core.Type
import GHC.Core.Coercion ( Coercion, coVarsOfCo )
import GHC.Core.FamInstEnv
import GHC.Utils.Misc
import GHC.Data.Maybe         ( isJust )
import GHC.Builtin.PrimOps
import GHC.Builtin.Types.Prim ( realWorldStatePrimTy )
import GHC.Utils.Error        ( dumpIfSet_dyn, DumpFormat (..) )
import GHC.Types.Unique.Set

{-
************************************************************************
*                                                                      *
\subsection{Top level stuff}
*                                                                      *
************************************************************************
-}

dmdAnalProgram :: DynFlags -> FamInstEnvs -> CoreProgram -> IO CoreProgram
dmdAnalProgram :: DynFlags -> FamInstEnvs -> CoreProgram -> IO CoreProgram
dmdAnalProgram DynFlags
dflags FamInstEnvs
fam_envs CoreProgram
binds = do
  let env :: AnalEnv
env             = DynFlags -> FamInstEnvs -> AnalEnv
emptyAnalEnv DynFlags
dflags FamInstEnvs
fam_envs
  let binds_plus_dmds :: CoreProgram
binds_plus_dmds = (AnalEnv, CoreProgram) -> CoreProgram
forall a b. (a, b) -> b
snd ((AnalEnv, CoreProgram) -> CoreProgram)
-> (AnalEnv, CoreProgram) -> CoreProgram
forall a b. (a -> b) -> a -> b
$ (AnalEnv -> CoreBind -> (AnalEnv, CoreBind))
-> AnalEnv -> CoreProgram -> (AnalEnv, CoreProgram)
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL AnalEnv -> CoreBind -> (AnalEnv, CoreBind)
dmdAnalTopBind AnalEnv
env CoreProgram
binds
  DynFlags -> DumpFlag -> String -> DumpFormat -> SDoc -> IO ()
dumpIfSet_dyn DynFlags
dflags DumpFlag
Opt_D_dump_str_signatures String
"Strictness signatures" DumpFormat
FormatText (SDoc -> IO ()) -> SDoc -> IO ()
forall a b. (a -> b) -> a -> b
$
    (IdInfo -> SDoc) -> CoreProgram -> SDoc
dumpIdInfoOfProgram (StrictSig -> SDoc
pprIfaceStrictSig (StrictSig -> SDoc) -> (IdInfo -> StrictSig) -> IdInfo -> SDoc
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IdInfo -> StrictSig
strictnessInfo) CoreProgram
binds_plus_dmds
  -- See Note [Stamp out space leaks in demand analysis]
  CoreProgram -> ()
seqBinds CoreProgram
binds_plus_dmds () -> IO CoreProgram -> IO CoreProgram
`seq` CoreProgram -> IO CoreProgram
forall (m :: * -> *) a. Monad m => a -> m a
return CoreProgram
binds_plus_dmds

-- Analyse a (group of) top-level binding(s)
dmdAnalTopBind :: AnalEnv
               -> CoreBind
               -> (AnalEnv, CoreBind)
dmdAnalTopBind :: AnalEnv -> CoreBind -> (AnalEnv, CoreBind)
dmdAnalTopBind AnalEnv
env (NonRec CoreBndr
id Expr CoreBndr
rhs)
  = ( TopLevelFlag -> AnalEnv -> CoreBndr -> StrictSig -> AnalEnv
extendAnalEnv TopLevelFlag
TopLevel AnalEnv
env CoreBndr
id StrictSig
sig
    , CoreBndr -> Expr CoreBndr -> CoreBind
forall b. b -> Expr b -> Bind b
NonRec (CoreBndr -> StrictSig -> CoreBndr
setIdStrictness CoreBndr
id StrictSig
sig) Expr CoreBndr
rhs')
  where
    ( DmdEnv
_, StrictSig
sig, Expr CoreBndr
rhs') = Maybe [CoreBndr]
-> AnalEnv
-> CleanDemand
-> CoreBndr
-> Expr CoreBndr
-> (DmdEnv, StrictSig, Expr CoreBndr)
dmdAnalRhsLetDown Maybe [CoreBndr]
forall a. Maybe a
Nothing AnalEnv
env CleanDemand
cleanEvalDmd CoreBndr
id Expr CoreBndr
rhs

dmdAnalTopBind AnalEnv
env (Rec [(CoreBndr, Expr CoreBndr)]
pairs)
  = (AnalEnv
env', [(CoreBndr, Expr CoreBndr)] -> CoreBind
forall b. [(b, Expr b)] -> Bind b
Rec [(CoreBndr, Expr CoreBndr)]
pairs')
  where
    (AnalEnv
env', DmdEnv
_, [(CoreBndr, Expr CoreBndr)]
pairs')  = TopLevelFlag
-> AnalEnv
-> CleanDemand
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
dmdFix TopLevelFlag
TopLevel AnalEnv
env CleanDemand
cleanEvalDmd [(CoreBndr, Expr CoreBndr)]
pairs
                -- We get two iterations automatically
                -- c.f. the NonRec case above

{- Note [Stamp out space leaks in demand analysis]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The demand analysis pass outputs a new copy of the Core program in
which binders have been annotated with demand and strictness
information. It's tiresome to ensure that this information is fully
evaluated everywhere that we produce it, so we just run a single
seqBinds over the output before returning it, to ensure that there are
no references holding on to the input Core program.

This makes a ~30% reduction in peak memory usage when compiling
DynFlags (cf #9675 and #13426).

This is particularly important when we are doing late demand analysis,
since we don't do a seqBinds at any point thereafter. Hence code
generation would hold on to an extra copy of the Core program, via
unforced thunks in demand or strictness information; and it is the
most memory-intensive part of the compilation process, so this added
seqBinds makes a big difference in peak memory usage.
-}


{-
************************************************************************
*                                                                      *
\subsection{The analyser itself}
*                                                                      *
************************************************************************

Note [Ensure demand is strict]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
It's important not to analyse e with a lazy demand because
a) When we encounter   case s of (a,b) ->
        we demand s with U(d1d2)... but if the overall demand is lazy
        that is wrong, and we'd need to reduce the demand on s,
        which is inconvenient
b) More important, consider
        f (let x = R in x+x), where f is lazy
   We still want to mark x as demanded, because it will be when we
   enter the let.  If we analyse f's arg with a Lazy demand, we'll
   just mark x as Lazy
c) The application rule wouldn't be right either
   Evaluating (f x) in a L demand does *not* cause
   evaluation of f in a C(L) demand!
-}

-- If e is complicated enough to become a thunk, its contents will be evaluated
-- at most once, so oneify it.
dmdTransformThunkDmd :: CoreExpr -> Demand -> Demand
dmdTransformThunkDmd :: Expr CoreBndr -> Demand -> Demand
dmdTransformThunkDmd Expr CoreBndr
e
  | Expr CoreBndr -> Bool
exprIsTrivial Expr CoreBndr
e = Demand -> Demand
forall a. a -> a
id
  | Bool
otherwise       = Demand -> Demand
forall s u. JointDmd s (Use u) -> JointDmd s (Use u)
oneifyDmd

-- Do not process absent demands
-- Otherwise act like in a normal demand analysis
-- See ↦* relation in the Cardinality Analysis paper
dmdAnalStar :: AnalEnv
            -> Demand   -- This one takes a *Demand*
            -> CoreExpr -- Should obey the let/app invariant
            -> (BothDmdArg, CoreExpr)
dmdAnalStar :: AnalEnv -> Demand -> Expr CoreBndr -> (BothDmdArg, Expr CoreBndr)
dmdAnalStar AnalEnv
env Demand
dmd Expr CoreBndr
e
  | (DmdShell
dmd_shell, CleanDemand
cd) <- Demand -> (DmdShell, CleanDemand)
toCleanDmd Demand
dmd
  , (DmdType
dmd_ty, Expr CoreBndr
e')    <- AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
cd Expr CoreBndr
e
  = ASSERT2( not (isUnliftedType (exprType e)) || exprOkForSpeculation e, ppr e )
    -- The argument 'e' should satisfy the let/app invariant
    -- See Note [Analysing with absent demand] in GHC.Types.Demand
    (DmdShell -> DmdType -> BothDmdArg
postProcessDmdType DmdShell
dmd_shell DmdType
dmd_ty, Expr CoreBndr
e')

-- Main Demand Analsysis machinery
dmdAnal, dmdAnal' :: AnalEnv
        -> CleanDemand         -- The main one takes a *CleanDemand*
        -> CoreExpr -> (DmdType, CoreExpr)

-- The CleanDemand is always strict and not absent
--    See Note [Ensure demand is strict]

dmdAnal :: AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
d Expr CoreBndr
e = -- pprTrace "dmdAnal" (ppr d <+> ppr e) $
                  AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal' AnalEnv
env CleanDemand
d Expr CoreBndr
e

dmdAnal' :: AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal' AnalEnv
_ CleanDemand
_ (Lit Literal
lit)     = (DmdType
nopDmdType, Literal -> Expr CoreBndr
forall b. Literal -> Expr b
Lit Literal
lit)
dmdAnal' AnalEnv
_ CleanDemand
_ (Type Type
ty)     = (DmdType
nopDmdType, Type -> Expr CoreBndr
forall b. Type -> Expr b
Type Type
ty) -- Doesn't happen, in fact
dmdAnal' AnalEnv
_ CleanDemand
_ (Coercion Coercion
co)
  = (DmdEnv -> DmdType
unitDmdType (Coercion -> DmdEnv
coercionDmdEnv Coercion
co), Coercion -> Expr CoreBndr
forall b. Coercion -> Expr b
Coercion Coercion
co)

dmdAnal' AnalEnv
env CleanDemand
dmd (Var CoreBndr
var)
  = (AnalEnv -> CoreBndr -> CleanDemand -> DmdType
dmdTransform AnalEnv
env CoreBndr
var CleanDemand
dmd, CoreBndr -> Expr CoreBndr
forall b. CoreBndr -> Expr b
Var CoreBndr
var)

dmdAnal' AnalEnv
env CleanDemand
dmd (Cast Expr CoreBndr
e Coercion
co)
  = (DmdType
dmd_ty DmdType -> BothDmdArg -> DmdType
`bothDmdType` DmdEnv -> BothDmdArg
mkBothDmdArg (Coercion -> DmdEnv
coercionDmdEnv Coercion
co), Expr CoreBndr -> Coercion -> Expr CoreBndr
forall b. Expr b -> Coercion -> Expr b
Cast Expr CoreBndr
e' Coercion
co)
  where
    (DmdType
dmd_ty, Expr CoreBndr
e') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
e

dmdAnal' AnalEnv
env CleanDemand
dmd (Tick Tickish CoreBndr
t Expr CoreBndr
e)
  = (DmdType
dmd_ty, Tickish CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. Tickish CoreBndr -> Expr b -> Expr b
Tick Tickish CoreBndr
t Expr CoreBndr
e')
  where
    (DmdType
dmd_ty, Expr CoreBndr
e') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
e

dmdAnal' AnalEnv
env CleanDemand
dmd (App Expr CoreBndr
fun (Type Type
ty))
  = (DmdType
fun_ty, Expr CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. Expr b -> Expr b -> Expr b
App Expr CoreBndr
fun' (Type -> Expr CoreBndr
forall b. Type -> Expr b
Type Type
ty))
  where
    (DmdType
fun_ty, Expr CoreBndr
fun') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
fun

-- Lots of the other code is there to make this
-- beautiful, compositional, application rule :-)
dmdAnal' AnalEnv
env CleanDemand
dmd (App Expr CoreBndr
fun Expr CoreBndr
arg)
  = -- This case handles value arguments (type args handled above)
    -- Crucially, coercions /are/ handled here, because they are
    -- value arguments (#10288)
    let
        call_dmd :: CleanDemand
call_dmd          = CleanDemand -> CleanDemand
mkCallDmd CleanDemand
dmd
        (DmdType
fun_ty, Expr CoreBndr
fun')    = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
call_dmd Expr CoreBndr
fun
        (Demand
arg_dmd, DmdType
res_ty) = DmdType -> (Demand, DmdType)
splitDmdTy DmdType
fun_ty
        (BothDmdArg
arg_ty, Expr CoreBndr
arg')    = AnalEnv -> Demand -> Expr CoreBndr -> (BothDmdArg, Expr CoreBndr)
dmdAnalStar AnalEnv
env (Expr CoreBndr -> Demand -> Demand
dmdTransformThunkDmd Expr CoreBndr
arg Demand
arg_dmd) Expr CoreBndr
arg
    in
--    pprTrace "dmdAnal:app" (vcat
--         [ text "dmd =" <+> ppr dmd
--         , text "expr =" <+> ppr (App fun arg)
--         , text "fun dmd_ty =" <+> ppr fun_ty
--         , text "arg dmd =" <+> ppr arg_dmd
--         , text "arg dmd_ty =" <+> ppr arg_ty
--         , text "res dmd_ty =" <+> ppr res_ty
--         , text "overall res dmd_ty =" <+> ppr (res_ty `bothDmdType` arg_ty) ])
    (DmdType
res_ty DmdType -> BothDmdArg -> DmdType
`bothDmdType` BothDmdArg
arg_ty, Expr CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. Expr b -> Expr b -> Expr b
App Expr CoreBndr
fun' Expr CoreBndr
arg')

dmdAnal' AnalEnv
env CleanDemand
dmd (Lam CoreBndr
var Expr CoreBndr
body)
  | CoreBndr -> Bool
isTyVar CoreBndr
var
  = let
        (DmdType
body_ty, Expr CoreBndr
body') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
body
    in
    (DmdType
body_ty, CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. b -> Expr b -> Expr b
Lam CoreBndr
var Expr CoreBndr
body')

  | Bool
otherwise
  = let (CleanDemand
body_dmd, DmdShell
defer_and_use) = CleanDemand -> (CleanDemand, DmdShell)
peelCallDmd CleanDemand
dmd
          -- body_dmd: a demand to analyze the body

        (DmdType
body_ty, Expr CoreBndr
body') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
body_dmd Expr CoreBndr
body
        (DmdType
lam_ty, CoreBndr
var')   = AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, CoreBndr)
annotateLamIdBndr AnalEnv
env Bool
notArgOfDfun DmdType
body_ty CoreBndr
var
    in
    (DmdShell -> DmdType -> DmdType
postProcessUnsat DmdShell
defer_and_use DmdType
lam_ty, CoreBndr -> Expr CoreBndr -> Expr CoreBndr
forall b. b -> Expr b -> Expr b
Lam CoreBndr
var' Expr CoreBndr
body')

dmdAnal' AnalEnv
env CleanDemand
dmd (Case Expr CoreBndr
scrut CoreBndr
case_bndr Type
ty [(DataAlt DataCon
dc, [CoreBndr]
bndrs, Expr CoreBndr
rhs)])
  -- Only one alternative with a product constructor
  | let tycon :: TyCon
tycon = DataCon -> TyCon
dataConTyCon DataCon
dc
  , Maybe DataCon -> Bool
forall a. Maybe a -> Bool
isJust (TyCon -> Maybe DataCon
isDataProductTyCon_maybe TyCon
tycon)
  = let
        (DmdType
rhs_ty, Expr CoreBndr
rhs')           = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
rhs
        (DmdType
alt_ty1, [Demand]
dmds)          = AnalEnv -> DmdType -> [CoreBndr] -> (DmdType, [Demand])
findBndrsDmds AnalEnv
env DmdType
rhs_ty [CoreBndr]
bndrs
        (DmdType
alt_ty2, Demand
case_bndr_dmd) = AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, Demand)
findBndrDmd AnalEnv
env Bool
False DmdType
alt_ty1 CoreBndr
case_bndr
        id_dmds :: [Demand]
id_dmds                  = Demand -> [Demand] -> [Demand]
addCaseBndrDmd Demand
case_bndr_dmd [Demand]
dmds
        fam_envs :: FamInstEnvs
fam_envs                 = AnalEnv -> FamInstEnvs
ae_fam_envs AnalEnv
env
        alt_ty3 :: DmdType
alt_ty3
          -- See Note [Precise exceptions and strictness analysis] in "GHC.Types.Demand"
          | FamInstEnvs -> Expr CoreBndr -> Bool
exprMayThrowPreciseException FamInstEnvs
fam_envs Expr CoreBndr
scrut
          = DmdType -> DmdType
deferAfterPreciseException DmdType
alt_ty2
          | Bool
otherwise
          = DmdType
alt_ty2

        -- Compute demand on the scrutinee
        -- See Note [Demand on scrutinee of a product case]
        scrut_dmd :: CleanDemand
scrut_dmd          = [Demand] -> CleanDemand
mkProdDmd [Demand]
id_dmds
        (DmdType
scrut_ty, Expr CoreBndr
scrut') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
scrut_dmd Expr CoreBndr
scrut
        res_ty :: DmdType
res_ty             = DmdType
alt_ty3 DmdType -> BothDmdArg -> DmdType
`bothDmdType` DmdType -> BothDmdArg
toBothDmdArg DmdType
scrut_ty
        case_bndr' :: CoreBndr
case_bndr'         = CoreBndr -> Demand -> CoreBndr
setIdDemandInfo CoreBndr
case_bndr Demand
case_bndr_dmd
        bndrs' :: [CoreBndr]
bndrs'             = [CoreBndr] -> [Demand] -> [CoreBndr]
setBndrsDemandInfo [CoreBndr]
bndrs [Demand]
id_dmds
    in
--    pprTrace "dmdAnal:Case1" (vcat [ text "scrut" <+> ppr scrut
--                                   , text "dmd" <+> ppr dmd
--                                   , text "case_bndr_dmd" <+> ppr (idDemandInfo case_bndr')
--                                   , text "id_dmds" <+> ppr id_dmds
--                                   , text "scrut_dmd" <+> ppr scrut_dmd
--                                   , text "scrut_ty" <+> ppr scrut_ty
--                                   , text "alt_ty" <+> ppr alt_ty2
--                                   , text "res_ty" <+> ppr res_ty ]) $
    (DmdType
res_ty, Expr CoreBndr
-> CoreBndr -> Type -> [Alt CoreBndr] -> Expr CoreBndr
forall b. Expr b -> b -> Type -> [Alt b] -> Expr b
Case Expr CoreBndr
scrut' CoreBndr
case_bndr' Type
ty [(DataCon -> AltCon
DataAlt DataCon
dc, [CoreBndr]
bndrs', Expr CoreBndr
rhs')])

dmdAnal' AnalEnv
env CleanDemand
dmd (Case Expr CoreBndr
scrut CoreBndr
case_bndr Type
ty [Alt CoreBndr]
alts)
  = let      -- Case expression with multiple alternatives
        ([DmdType]
alt_tys, [Alt CoreBndr]
alts')     = (Alt CoreBndr -> (DmdType, Alt CoreBndr))
-> [Alt CoreBndr] -> ([DmdType], [Alt CoreBndr])
forall a b c. (a -> (b, c)) -> [a] -> ([b], [c])
mapAndUnzip (AnalEnv
-> CleanDemand
-> CoreBndr
-> Alt CoreBndr
-> (DmdType, Alt CoreBndr)
dmdAnalAlt AnalEnv
env CleanDemand
dmd CoreBndr
case_bndr) [Alt CoreBndr]
alts
        (DmdType
scrut_ty, Expr CoreBndr
scrut')   = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
cleanEvalDmd Expr CoreBndr
scrut
        (DmdType
alt_ty, CoreBndr
case_bndr') = AnalEnv -> DmdType -> CoreBndr -> (DmdType, CoreBndr)
annotateBndr AnalEnv
env ((DmdType -> DmdType -> DmdType) -> DmdType -> [DmdType] -> DmdType
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr DmdType -> DmdType -> DmdType
lubDmdType DmdType
botDmdType [DmdType]
alt_tys) CoreBndr
case_bndr
                               -- NB: Base case is botDmdType, for empty case alternatives
                               --     This is a unit for lubDmdType, and the right result
                               --     when there really are no alternatives
        fam_envs :: FamInstEnvs
fam_envs             = AnalEnv -> FamInstEnvs
ae_fam_envs AnalEnv
env
        alt_ty2 :: DmdType
alt_ty2
          -- See Note [Precise exceptions and strictness analysis] in "GHC.Types.Demand"
          | FamInstEnvs -> Expr CoreBndr -> Bool
exprMayThrowPreciseException FamInstEnvs
fam_envs Expr CoreBndr
scrut
          = DmdType -> DmdType
deferAfterPreciseException DmdType
alt_ty
          | Bool
otherwise
          = DmdType
alt_ty
        res_ty :: DmdType
res_ty               = DmdType
alt_ty2 DmdType -> BothDmdArg -> DmdType
`bothDmdType` DmdType -> BothDmdArg
toBothDmdArg DmdType
scrut_ty

    in
--    pprTrace "dmdAnal:Case2" (vcat [ text "scrut" <+> ppr scrut
--                                   , text "scrut_ty" <+> ppr scrut_ty
--                                   , text "alt_tys" <+> ppr alt_tys
--                                   , text "alt_ty2" <+> ppr alt_ty2
--                                   , text "res_ty" <+> ppr res_ty ]) $
    (DmdType
res_ty, Expr CoreBndr
-> CoreBndr -> Type -> [Alt CoreBndr] -> Expr CoreBndr
forall b. Expr b -> b -> Type -> [Alt b] -> Expr b
Case Expr CoreBndr
scrut' CoreBndr
case_bndr' Type
ty [Alt CoreBndr]
alts')

-- Let bindings can be processed in two ways:
-- Down (RHS before body) or Up (body before RHS).
-- The following case handle the up variant.
--
-- It is very simple. For  let x = rhs in body
--   * Demand-analyse 'body' in the current environment
--   * Find the demand, 'rhs_dmd' placed on 'x' by 'body'
--   * Demand-analyse 'rhs' in 'rhs_dmd'
--
-- This is used for a non-recursive local let without manifest lambdas.
-- This is the LetUp rule in the paper “Higher-Order Cardinality Analysis”.
dmdAnal' AnalEnv
env CleanDemand
dmd (Let (NonRec CoreBndr
id Expr CoreBndr
rhs) Expr CoreBndr
body)
  | CoreBndr -> Bool
useLetUp CoreBndr
id
  = (DmdType
final_ty, CoreBind -> Expr CoreBndr -> Expr CoreBndr
forall b. Bind b -> Expr b -> Expr b
Let (CoreBndr -> Expr CoreBndr -> CoreBind
forall b. b -> Expr b -> Bind b
NonRec CoreBndr
id' Expr CoreBndr
rhs') Expr CoreBndr
body')
  where
    (DmdType
body_ty, Expr CoreBndr
body')   = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
body
    (DmdType
body_ty', Demand
id_dmd) = AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, Demand)
findBndrDmd AnalEnv
env Bool
notArgOfDfun DmdType
body_ty CoreBndr
id
    id' :: CoreBndr
id'                = CoreBndr -> Demand -> CoreBndr
setIdDemandInfo CoreBndr
id Demand
id_dmd

    (BothDmdArg
rhs_ty, Expr CoreBndr
rhs')     = AnalEnv -> Demand -> Expr CoreBndr -> (BothDmdArg, Expr CoreBndr)
dmdAnalStar AnalEnv
env (Expr CoreBndr -> Demand -> Demand
dmdTransformThunkDmd Expr CoreBndr
rhs Demand
id_dmd) Expr CoreBndr
rhs
    final_ty :: DmdType
final_ty           = DmdType
body_ty' DmdType -> BothDmdArg -> DmdType
`bothDmdType` BothDmdArg
rhs_ty

dmdAnal' AnalEnv
env CleanDemand
dmd (Let (NonRec CoreBndr
id Expr CoreBndr
rhs) Expr CoreBndr
body)
  = (DmdType
body_ty2, CoreBind -> Expr CoreBndr -> Expr CoreBndr
forall b. Bind b -> Expr b -> Expr b
Let (CoreBndr -> Expr CoreBndr -> CoreBind
forall b. b -> Expr b -> Bind b
NonRec CoreBndr
id2 Expr CoreBndr
rhs') Expr CoreBndr
body')
  where
    (DmdEnv
lazy_fv, StrictSig
sig, Expr CoreBndr
rhs') = Maybe [CoreBndr]
-> AnalEnv
-> CleanDemand
-> CoreBndr
-> Expr CoreBndr
-> (DmdEnv, StrictSig, Expr CoreBndr)
dmdAnalRhsLetDown Maybe [CoreBndr]
forall a. Maybe a
Nothing AnalEnv
env CleanDemand
dmd CoreBndr
id Expr CoreBndr
rhs
    id1 :: CoreBndr
id1                  = CoreBndr -> StrictSig -> CoreBndr
setIdStrictness CoreBndr
id StrictSig
sig
    env1 :: AnalEnv
env1                 = TopLevelFlag -> AnalEnv -> CoreBndr -> StrictSig -> AnalEnv
extendAnalEnv TopLevelFlag
NotTopLevel AnalEnv
env CoreBndr
id StrictSig
sig
    (DmdType
body_ty, Expr CoreBndr
body')     = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env1 CleanDemand
dmd Expr CoreBndr
body
    (DmdType
body_ty1, CoreBndr
id2)      = AnalEnv -> DmdType -> CoreBndr -> (DmdType, CoreBndr)
annotateBndr AnalEnv
env DmdType
body_ty CoreBndr
id1
    body_ty2 :: DmdType
body_ty2             = DmdType -> DmdEnv -> DmdType
addLazyFVs DmdType
body_ty1 DmdEnv
lazy_fv -- see Note [Lazy and unleashable free variables]

        -- If the actual demand is better than the vanilla call
        -- demand, you might think that we might do better to re-analyse
        -- the RHS with the stronger demand.
        -- But (a) That seldom happens, because it means that *every* path in
        --         the body of the let has to use that stronger demand
        -- (b) It often happens temporarily in when fixpointing, because
        --     the recursive function at first seems to place a massive demand.
        --     But we don't want to go to extra work when the function will
        --     probably iterate to something less demanding.
        -- In practice, all the times the actual demand on id2 is more than
        -- the vanilla call demand seem to be due to (b).  So we don't
        -- bother to re-analyse the RHS.

dmdAnal' AnalEnv
env CleanDemand
dmd (Let (Rec [(CoreBndr, Expr CoreBndr)]
pairs) Expr CoreBndr
body)
  = let
        (AnalEnv
env', DmdEnv
lazy_fv, [(CoreBndr, Expr CoreBndr)]
pairs') = TopLevelFlag
-> AnalEnv
-> CleanDemand
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
dmdFix TopLevelFlag
NotTopLevel AnalEnv
env CleanDemand
dmd [(CoreBndr, Expr CoreBndr)]
pairs
        (DmdType
body_ty, Expr CoreBndr
body')        = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env' CleanDemand
dmd Expr CoreBndr
body
        body_ty1 :: DmdType
body_ty1                = DmdType -> [CoreBndr] -> DmdType
deleteFVs DmdType
body_ty (((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> [(CoreBndr, Expr CoreBndr)] -> [CoreBndr]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst [(CoreBndr, Expr CoreBndr)]
pairs)
        body_ty2 :: DmdType
body_ty2                = DmdType -> DmdEnv -> DmdType
addLazyFVs DmdType
body_ty1 DmdEnv
lazy_fv -- see Note [Lazy and unleashable free variables]
    in
    DmdType
body_ty2 DmdType -> (DmdType, Expr CoreBndr) -> (DmdType, Expr CoreBndr)
`seq`
    (DmdType
body_ty2,  CoreBind -> Expr CoreBndr -> Expr CoreBndr
forall b. Bind b -> Expr b -> Expr b
Let ([(CoreBndr, Expr CoreBndr)] -> CoreBind
forall b. [(b, Expr b)] -> Bind b
Rec [(CoreBndr, Expr CoreBndr)]
pairs') Expr CoreBndr
body')

-- | A simple, syntactic analysis of whether an expression MAY throw a precise
-- exception when evaluated. It's always sound to return 'True'.
-- See Note [Which scrutinees may throw precise exceptions].
exprMayThrowPreciseException :: FamInstEnvs -> CoreExpr -> Bool
exprMayThrowPreciseException :: FamInstEnvs -> Expr CoreBndr -> Bool
exprMayThrowPreciseException FamInstEnvs
envs Expr CoreBndr
e
  | Bool -> Bool
not (FamInstEnvs -> Type -> Bool
forcesRealWorld FamInstEnvs
envs (Expr CoreBndr -> Type
exprType Expr CoreBndr
e))
  = Bool
False -- 1. in the Note
  | (Var CoreBndr
f, [Expr CoreBndr]
_) <- Expr CoreBndr -> (Expr CoreBndr, [Expr CoreBndr])
forall b. Expr b -> (Expr b, [Expr b])
collectArgs Expr CoreBndr
e
  , Just PrimOp
op    <- CoreBndr -> Maybe PrimOp
isPrimOpId_maybe CoreBndr
f
  , PrimOp
op PrimOp -> PrimOp -> Bool
forall a. Eq a => a -> a -> Bool
/= PrimOp
RaiseIOOp
  = Bool
False -- 2. in the Note
  | (Var CoreBndr
f, [Expr CoreBndr]
_) <- Expr CoreBndr -> (Expr CoreBndr, [Expr CoreBndr])
forall b. Expr b -> (Expr b, [Expr b])
collectArgs Expr CoreBndr
e
  , Just ForeignCall
fcall <- CoreBndr -> Maybe ForeignCall
isFCallId_maybe CoreBndr
f
  , Bool -> Bool
not (ForeignCall -> Bool
isSafeForeignCall ForeignCall
fcall)
  = Bool
False -- 3. in the Note
  | Bool
otherwise
  = Bool
True  -- _. in the Note

-- | Recognises types that are
--    * @State# RealWorld@
--    * Unboxed tuples with a @State# RealWorld@ field
-- modulo coercions. This will detect 'IO' actions (even post Nested CPR! See
-- T13380e) and user-written variants thereof by their type.
forcesRealWorld :: FamInstEnvs -> Type -> Bool
forcesRealWorld :: FamInstEnvs -> Type -> Bool
forcesRealWorld FamInstEnvs
fam_envs Type
ty
  | Type
ty Type -> Type -> Bool
`eqType` Type
realWorldStatePrimTy
  = Bool
True
  | Just DataConAppContext{ dcac_dc :: DataConAppContext -> DataCon
dcac_dc = DataCon
dc, dcac_arg_tys :: DataConAppContext -> [(Scaled Type, StrictnessMark)]
dcac_arg_tys = [(Scaled Type, StrictnessMark)]
field_tys }
      <- FamInstEnvs -> Type -> Maybe DataConAppContext
deepSplitProductType_maybe FamInstEnvs
fam_envs Type
ty
  , DataCon -> Bool
isUnboxedTupleCon DataCon
dc
  = ((Scaled Type, StrictnessMark) -> Bool)
-> [(Scaled Type, StrictnessMark)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\(Scaled Type
ty,StrictnessMark
_) -> Scaled Type -> Type
forall a. Scaled a -> a
scaledThing Scaled Type
ty Type -> Type -> Bool
`eqType` Type
realWorldStatePrimTy) [(Scaled Type, StrictnessMark)]
field_tys
  | Bool
otherwise
  = Bool
False

dmdAnalAlt :: AnalEnv -> CleanDemand -> Id -> Alt Var -> (DmdType, Alt Var)
dmdAnalAlt :: AnalEnv
-> CleanDemand
-> CoreBndr
-> Alt CoreBndr
-> (DmdType, Alt CoreBndr)
dmdAnalAlt AnalEnv
env CleanDemand
dmd CoreBndr
case_bndr (AltCon
con,[CoreBndr]
bndrs,Expr CoreBndr
rhs)
  | [CoreBndr] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [CoreBndr]
bndrs    -- Literals, DEFAULT, and nullary constructors
  , (DmdType
rhs_ty, Expr CoreBndr
rhs') <- AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
rhs
  = (DmdType
rhs_ty, (AltCon
con, [], Expr CoreBndr
rhs'))

  | Bool
otherwise     -- Non-nullary data constructors
  , (DmdType
rhs_ty, Expr CoreBndr
rhs') <- AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
dmd Expr CoreBndr
rhs
  , (DmdType
alt_ty, [Demand]
dmds) <- AnalEnv -> DmdType -> [CoreBndr] -> (DmdType, [Demand])
findBndrsDmds AnalEnv
env DmdType
rhs_ty [CoreBndr]
bndrs
  , let case_bndr_dmd :: Demand
case_bndr_dmd = DmdType -> CoreBndr -> Demand
findIdDemand DmdType
alt_ty CoreBndr
case_bndr
        id_dmds :: [Demand]
id_dmds       = Demand -> [Demand] -> [Demand]
addCaseBndrDmd Demand
case_bndr_dmd [Demand]
dmds
  = (DmdType
alt_ty, (AltCon
con, [CoreBndr] -> [Demand] -> [CoreBndr]
setBndrsDemandInfo [CoreBndr]
bndrs [Demand]
id_dmds, Expr CoreBndr
rhs'))

{- Note [Which scrutinees may throw precise exceptions]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This is the specification of 'exprMayThrowPreciseExceptions',
which is important for Scenario 2 of
Note [Precise exceptions and strictness analysis] in GHC.Types.Demand.

For an expression @f a1 ... an :: ty@ we determine that
  1. False  If ty is *not* @State# RealWorld@ or an unboxed tuple thereof.
            This check is done by 'forcesRealWorld'.
            (Why not simply unboxed pairs as above? This is motivated by
            T13380{d,e}.)
  2. False  If f is a PrimOp, and it is *not* raiseIO#
  3. False  If f is an unsafe FFI call ('PlayRisky')
  _. True   Otherwise "give up".

It is sound to return False in those cases, because
  1. We don't give any guarantees for unsafePerformIO, so no precise exceptions
     from pure code.
  2. raiseIO# is the only primop that may throw a precise exception.
  3. Unsafe FFI calls may not interact with the RTS (to throw, for example).
     See haddock on GHC.Types.ForeignCall.PlayRisky.

We *need* to return False in those cases, because
  1. We would lose too much strictness in pure code, all over the place.
  2. We would lose strictness for primops like getMaskingState#, which
     introduces a substantial regression in
     GHC.IO.Handle.Internals.wantReadableHandle.
  3. We would lose strictness for code like GHC.Fingerprint.fingerprintData,
     where an intermittent FFI call to c_MD5Init would otherwise lose
     strictness on the arguments len and buf, leading to regressions in T9203
     (2%) and i386's haddock.base (5%). Tested by T13380f.

In !3014 we tried a more sophisticated analysis by introducing ConOrDiv (nic)
to the Divergence lattice, but in practice it turned out to be hard to untaint
from 'topDiv' to 'conDiv', leading to bugs, performance regressions and
complexity that didn't justify the single fixed testcase T13380c.

Note [Demand on the scrutinee of a product case]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When figuring out the demand on the scrutinee of a product case,
we use the demands of the case alternative, i.e. id_dmds.
But note that these include the demand on the case binder;
see Note [Demand on case-alternative binders] in GHC.Types.Demand.
This is crucial. Example:
   f x = case x of y { (a,b) -> k y a }
If we just take scrut_demand = U(L,A), then we won't pass x to the
worker, so the worker will rebuild
     x = (a, absent-error)
and that'll crash.

Note [Aggregated demand for cardinality]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We use different strategies for strictness and usage/cardinality to
"unleash" demands captured on free variables by bindings. Let us
consider the example:

f1 y = let {-# NOINLINE h #-}
           h = y
       in  (h, h)

We are interested in obtaining cardinality demand U1 on |y|, as it is
used only in a thunk, and, therefore, is not going to be updated any
more. Therefore, the demand on |y|, captured and unleashed by usage of
|h| is U1. However, if we unleash this demand every time |h| is used,
and then sum up the effects, the ultimate demand on |y| will be U1 +
U1 = U. In order to avoid it, we *first* collect the aggregate demand
on |h| in the body of let-expression, and only then apply the demand
transformer:

transf[x](U) = {y |-> U1}

so the resulting demand on |y| is U1.

The situation is, however, different for strictness, where this
aggregating approach exhibits worse results because of the nature of
|both| operation for strictness. Consider the example:

f y c =
  let h x = y |seq| x
   in case of
        True  -> h True
        False -> y

It is clear that |f| is strict in |y|, however, the suggested analysis
will infer from the body of |let| that |h| is used lazily (as it is
used in one branch only), therefore lazy demand will be put on its
free variable |y|. Conversely, if the demand on |h| is unleashed right
on the spot, we will get the desired result, namely, that |f| is
strict in |y|.


************************************************************************
*                                                                      *
                    Demand transformer
*                                                                      *
************************************************************************
-}

dmdTransform :: AnalEnv         -- The strictness environment
             -> Id              -- The function
             -> CleanDemand     -- The demand on the function
             -> DmdType         -- The demand type of the function in this context
        -- Returned DmdEnv includes the demand on
        -- this function plus demand on its free variables

dmdTransform :: AnalEnv -> CoreBndr -> CleanDemand -> DmdType
dmdTransform AnalEnv
env CoreBndr
var CleanDemand
dmd
  -- Data constructors
  | CoreBndr -> Bool
isDataConWorkId CoreBndr
var
  = Int -> CleanDemand -> DmdType
dmdTransformDataConSig (CoreBndr -> Int
idArity CoreBndr
var) CleanDemand
dmd
  -- Dictionary component selectors
  | GeneralFlag -> DynFlags -> Bool
gopt GeneralFlag
Opt_DmdTxDictSel (AnalEnv -> DynFlags
ae_dflags AnalEnv
env),
    Just Class
_ <- CoreBndr -> Maybe Class
isClassOpId_maybe CoreBndr
var
  = StrictSig -> CleanDemand -> DmdType
dmdTransformDictSelSig (CoreBndr -> StrictSig
idStrictness CoreBndr
var) CleanDemand
dmd
  -- Imported functions
  | CoreBndr -> Bool
isGlobalId CoreBndr
var
  , let res :: DmdType
res = StrictSig -> CleanDemand -> DmdType
dmdTransformSig (CoreBndr -> StrictSig
idStrictness CoreBndr
var) CleanDemand
dmd
  = -- pprTrace "dmdTransform:import" (vcat [ppr var, ppr (idStrictness var), ppr dmd, ppr res])
    DmdType
res
  -- Top-level or local let-bound thing for which we use LetDown ('useLetUp').
  -- In that case, we have a strictness signature to unleash in our AnalEnv.
  | Just (StrictSig
sig, TopLevelFlag
top_lvl) <- AnalEnv -> CoreBndr -> Maybe (StrictSig, TopLevelFlag)
lookupSigEnv AnalEnv
env CoreBndr
var
  , let fn_ty :: DmdType
fn_ty = StrictSig -> CleanDemand -> DmdType
dmdTransformSig StrictSig
sig CleanDemand
dmd
  = -- pprTrace "dmdTransform:LetDown" (vcat [ppr var, ppr sig, ppr dmd, ppr fn_ty]) $
    if TopLevelFlag -> Bool
isTopLevel TopLevelFlag
top_lvl
    then DmdType
fn_ty   -- Don't record demand on top-level things
    else DmdType -> CoreBndr -> Demand -> DmdType
addVarDmd DmdType
fn_ty CoreBndr
var (CleanDemand -> Demand
mkOnceUsedDmd CleanDemand
dmd)
  -- Everything else:
  --   * Local let binders for which we use LetUp (cf. 'useLetUp')
  --   * Lambda binders
  --   * Case and constructor field binders
  | Bool
otherwise
  = -- pprTrace "dmdTransform:other" (vcat [ppr var, ppr sig, ppr dmd, ppr res]) $
    DmdEnv -> DmdType
unitDmdType (CoreBndr -> Demand -> DmdEnv
forall a. CoreBndr -> a -> VarEnv a
unitVarEnv CoreBndr
var (CleanDemand -> Demand
mkOnceUsedDmd CleanDemand
dmd))

{- *********************************************************************
*                                                                      *
                      Binding right-hand sides
*                                                                      *
********************************************************************* -}

-- Let bindings can be processed in two ways:
-- Down (RHS before body) or Up (body before RHS).
-- dmdAnalRhsLetDown implements the Down variant:
--  * assuming a demand of <L,U>
--  * looking at the definition
--  * determining a strictness signature
--
-- It is used for toplevel definition, recursive definitions and local
-- non-recursive definitions that have manifest lambdas.
-- Local non-recursive definitions without a lambda are handled with LetUp.
--
-- This is the LetDown rule in the paper “Higher-Order Cardinality Analysis”.
dmdAnalRhsLetDown
  :: Maybe [Id]   -- Just bs <=> recursive, Nothing <=> non-recursive
  -> AnalEnv -> CleanDemand
  -> Id -> CoreExpr
  -> (DmdEnv, StrictSig, CoreExpr)
-- Process the RHS of the binding, add the strictness signature
-- to the Id, and augment the environment with the signature as well.
-- See Note [NOINLINE and strictness]
dmdAnalRhsLetDown :: Maybe [CoreBndr]
-> AnalEnv
-> CleanDemand
-> CoreBndr
-> Expr CoreBndr
-> (DmdEnv, StrictSig, Expr CoreBndr)
dmdAnalRhsLetDown Maybe [CoreBndr]
rec_flag AnalEnv
env CleanDemand
let_dmd CoreBndr
id Expr CoreBndr
rhs
  = (DmdEnv
lazy_fv, StrictSig
sig, Expr CoreBndr
rhs')
  where
    rhs_arity :: Int
rhs_arity = CoreBndr -> Int
idArity CoreBndr
id
    rhs_dmd :: CleanDemand
rhs_dmd -- See Note [Demand analysis for join points]
            -- See Note [Invariants on join points] invariant 2b, in GHC.Core
            --     rhs_arity matches the join arity of the join point
            | CoreBndr -> Bool
isJoinId CoreBndr
id
            = Int -> CleanDemand -> CleanDemand
mkCallDmds Int
rhs_arity CleanDemand
let_dmd
            | Bool
otherwise
            -- NB: rhs_arity
            -- See Note [Demand signatures are computed for a threshold demand based on idArity]
            = AnalEnv -> Int -> Expr CoreBndr -> CleanDemand
mkRhsDmd AnalEnv
env Int
rhs_arity Expr CoreBndr
rhs

    (DmdType DmdEnv
rhs_fv [Demand]
rhs_dmds Divergence
rhs_div, Expr CoreBndr
rhs') = AnalEnv -> CleanDemand -> Expr CoreBndr -> (DmdType, Expr CoreBndr)
dmdAnal AnalEnv
env CleanDemand
rhs_dmd Expr CoreBndr
rhs
    sig :: StrictSig
sig = Int -> DmdType -> StrictSig
mkStrictSigForArity Int
rhs_arity (DmdEnv -> [Demand] -> Divergence -> DmdType
DmdType DmdEnv
sig_fv [Demand]
rhs_dmds Divergence
rhs_div)

    -- See Note [Aggregated demand for cardinality]
    rhs_fv1 :: DmdEnv
rhs_fv1 = case Maybe [CoreBndr]
rec_flag of
                Just [CoreBndr]
bs -> DmdEnv -> DmdEnv
reuseEnv (DmdEnv -> [CoreBndr] -> DmdEnv
forall a. VarEnv a -> [CoreBndr] -> VarEnv a
delVarEnvList DmdEnv
rhs_fv [CoreBndr]
bs)
                Maybe [CoreBndr]
Nothing -> DmdEnv
rhs_fv

    -- See Note [Lazy and unleashable free variables]
    (DmdEnv
lazy_fv, DmdEnv
sig_fv) = Bool -> DmdEnv -> (DmdEnv, DmdEnv)
splitFVs Bool
is_thunk DmdEnv
rhs_fv1
    is_thunk :: Bool
is_thunk = Bool -> Bool
not (Expr CoreBndr -> Bool
exprIsHNF Expr CoreBndr
rhs) Bool -> Bool -> Bool
&& Bool -> Bool
not (CoreBndr -> Bool
isJoinId CoreBndr
id)

-- | @mkRhsDmd env rhs_arity rhs@ creates a 'CleanDemand' for
-- unleashing on the given function's @rhs@, by creating
-- a call demand of @rhs_arity@
-- See Historical Note [Product demands for function body]
mkRhsDmd :: AnalEnv -> Arity -> CoreExpr -> CleanDemand
mkRhsDmd :: AnalEnv -> Int -> Expr CoreBndr -> CleanDemand
mkRhsDmd AnalEnv
_env Int
rhs_arity Expr CoreBndr
_rhs = Int -> CleanDemand -> CleanDemand
mkCallDmds Int
rhs_arity CleanDemand
cleanEvalDmd

-- | If given the let-bound 'Id', 'useLetUp' determines whether we should
-- process the binding up (body before rhs) or down (rhs before body).
--
-- We use LetDown if there is a chance to get a useful strictness signature to
-- unleash at call sites. LetDown is generally more precise than LetUp if we can
-- correctly guess how it will be used in the body, that is, for which incoming
-- demand the strictness signature should be computed, which allows us to
-- unleash higher-order demands on arguments at call sites. This is mostly the
-- case when
--
--   * The binding takes any arguments before performing meaningful work (cf.
--     'idArity'), in which case we are interested to see how it uses them.
--   * The binding is a join point, hence acting like a function, not a value.
--     As a big plus, we know *precisely* how it will be used in the body; since
--     it's always tail-called, we can directly unleash the incoming demand of
--     the let binding on its RHS when computing a strictness signature. See
--     [Demand analysis for join points].
--
-- Thus, if the binding is not a join point and its arity is 0, we have a thunk
-- and use LetUp, implying that we have no usable demand signature available
-- when we analyse the let body.
--
-- Since thunk evaluation is memoised, we want to unleash its 'DmdEnv' of free
-- vars at most once, regardless of how many times it was forced in the body.
-- This makes a real difference wrt. usage demands. The other reason is being
-- able to unleash a more precise product demand on its RHS once we know how the
-- thunk was used in the let body.
--
-- Characteristic examples, always assuming a single evaluation:
--
--   * @let x = 2*y in x + x@ => LetUp. Compared to LetDown, we find out that
--     the expression uses @y@ at most once.
--   * @let x = (a,b) in fst x@ => LetUp. Compared to LetDown, we find out that
--     @b@ is absent.
--   * @let f x = x*2 in f y@ => LetDown. Compared to LetUp, we find out that
--     the expression uses @y@ strictly, because we have @f@'s demand signature
--     available at the call site.
--   * @join exit = 2*y in if a then exit else if b then exit else 3*y@ =>
--     LetDown. Compared to LetUp, we find out that the expression uses @y@
--     strictly, because we can unleash @exit@'s signature at each call site.
--   * For a more convincing example with join points, see Note [Demand analysis
--     for join points].
--
useLetUp :: Var -> Bool
useLetUp :: CoreBndr -> Bool
useLetUp CoreBndr
f = CoreBndr -> Int
idArity CoreBndr
f Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& Bool -> Bool
not (CoreBndr -> Bool
isJoinId CoreBndr
f)

{- Note [Demand analysis for join points]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider
   g :: (Int,Int) -> Int
   g (p,q) = p+q

   f :: T -> Int -> Int
   f x p = g (join j y = (p,y)
              in case x of
                   A -> j 3
                   B -> j 4
                   C -> (p,7))

If j was a vanilla function definition, we'd analyse its body with
evalDmd, and think that it was lazy in p.  But for join points we can
do better!  We know that j's body will (if called at all) be evaluated
with the demand that consumes the entire join-binding, in this case
the argument demand from g.  Whizzo!  g evaluates both components of
its argument pair, so p will certainly be evaluated if j is called.

For f to be strict in p, we need /all/ paths to evaluate p; in this
case the C branch does so too, so we are fine.  So, as usual, we need
to transport demands on free variables to the call site(s).  Compare
Note [Lazy and unleashable free variables].

The implementation is easy.  When analysing a join point, we can
analyse its body with the demand from the entire join-binding (written
let_dmd here).

Another win for join points!  #13543.

However, note that the strictness signature for a join point can
look a little puzzling.  E.g.

    (join j x = \y. error "urk")
    (in case v of              )
    (     A -> j 3             )  x
    (     B -> j 4             )
    (     C -> \y. blah        )

The entire thing is in a C(S) context, so j's strictness signature
will be    [A]b
meaning one absent argument, returns bottom.  That seems odd because
there's a \y inside.  But it's right because when consumed in a C(1)
context the RHS of the join point is indeed bottom.

Note [Demand signatures are computed for a threshold demand based on idArity]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We compute demand signatures assuming idArity incoming arguments to approximate
behavior for when we have a call site with at least that many arguments. idArity
is /at least/ the number of manifest lambdas, but might be higher for PAPs and
trivial RHS (see Note [Demand analysis for trivial right-hand sides]).

Because idArity of a function varies independently of its cardinality properties
(cf. Note [idArity varies independently of dmdTypeDepth]), we implicitly encode
the arity for when a demand signature is sound to unleash in its 'dmdTypeDepth'
(cf. Note [Understanding DmdType and StrictSig] in GHC.Types.Demand). It is unsound to
unleash a demand signature when the incoming number of arguments is less than
that. See Note [What are demand signatures?] for more details on soundness.

Why idArity arguments? Because that's a conservative estimate of how many
arguments we must feed a function before it does anything interesting with them.
Also it elegantly subsumes the trivial RHS and PAP case.

There might be functions for which we might want to analyse for more incoming
arguments than idArity. Example:

  f x =
    if expensive
      then \y -> ... y ...
      else \y -> ... y ...

We'd analyse `f` under a unary call demand C(S), corresponding to idArity
being 1. That's enough to look under the manifest lambda and find out how a
unary call would use `x`, but not enough to look into the lambdas in the if
branches.

On the other hand, if we analysed for call demand C(C(S)), we'd get useful
strictness info for `y` (and more precise info on `x`) and possibly CPR
information, but

  * We would no longer be able to unleash the signature at unary call sites
  * Performing the worker/wrapper split based on this information would be
    implicitly eta-expanding `f`, playing fast and loose with divergence and
    even being unsound in the presence of newtypes, so we refrain from doing so.
    Also see Note [Don't eta expand in w/w] in GHC.Core.Opt.WorkWrap.

Since we only compute one signature, we do so for arity 1. Computing multiple
signatures for different arities (i.e., polyvariance) would be entirely
possible, if it weren't for the additional runtime and implementation
complexity.

Note [idArity varies independently of dmdTypeDepth]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We used to check in GHC.Core.Lint that dmdTypeDepth <= idArity for a let-bound
identifier. But that means we would have to zap demand signatures every time we
reset or decrease arity. That's an unnecessary dependency, because

  * The demand signature captures a semantic property that is independent of
    what the binding's current arity is
  * idArity is analysis information itself, thus volatile
  * We already *have* dmdTypeDepth, wo why not just use it to encode the
    threshold for when to unleash the signature
    (cf. Note [Understanding DmdType and StrictSig] in GHC.Types.Demand)

Consider the following expression, for example:

    (let go x y = `x` seq ... in go) |> co

`go` might have a strictness signature of `<S><L>`. The simplifier will identify
`go` as a nullary join point through `joinPointBinding_maybe` and float the
coercion into the binding, leading to an arity decrease:

    join go = (\x y -> `x` seq ...) |> co in go

With the CoreLint check, we would have to zap `go`'s perfectly viable strictness
signature.

Note [What are demand signatures?]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Demand analysis interprets expressions in the abstract domain of demand
transformers. Given an incoming demand we put an expression under, its abstract
transformer gives us back a demand type denoting how other things (like
arguments and free vars) were used when the expression was evaluated.
Here's an example:

  f x y =
    if x + expensive
      then \z -> z + y * ...
      else \z -> z * ...

The abstract transformer (let's call it F_e) of the if expression (let's call it
e) would transform an incoming head demand <S,HU> into a demand type like
{x-><S,1*U>,y-><L,U>}<L,U>. In pictures:

     Demand ---F_e---> DmdType
     <S,HU>            {x-><S,1*U>,y-><L,U>}<L,U>

Let's assume that the demand transformers we compute for an expression are
correct wrt. to some concrete semantics for Core. How do demand signatures fit
in? They are strange beasts, given that they come with strict rules when to
it's sound to unleash them.

Fortunately, we can formalise the rules with Galois connections. Consider
f's strictness signature, {}<S,1*U><L,U>. It's a single-point approximation of
the actual abstract transformer of f's RHS for arity 2. So, what happens is that
we abstract *once more* from the abstract domain we already are in, replacing
the incoming Demand by a simple lattice with two elements denoting incoming
arity: A_2 = {<2, >=2} (where '<2' is the top element and >=2 the bottom
element). Here's the diagram:

     A_2 -----f_f----> DmdType
      ^                   |
      | α               γ |
      |                   v
     Demand ---F_f---> DmdType

With
  α(C1(C1(_))) = >=2 -- example for usage demands, but similar for strictness
  α(_)         =  <2
  γ(ty)        =  ty
and F_f being the abstract transformer of f's RHS and f_f being the abstracted
abstract transformer computable from our demand signature simply by

  f_f(>=2) = {}<S,1*U><L,U>
  f_f(<2)  = postProcessUnsat {}<S,1*U><L,U>

where postProcessUnsat makes a proper top element out of the given demand type.

Note [Demand analysis for trivial right-hand sides]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider
    foo = plusInt |> co
where plusInt is an arity-2 function with known strictness.  Clearly
we want plusInt's strictness to propagate to foo!  But because it has
no manifest lambdas, it won't do so automatically, and indeed 'co' might
have type (Int->Int->Int) ~ T.

Fortunately, GHC.Core.Opt.Arity gives 'foo' arity 2, which is enough for LetDown to
forward plusInt's demand signature, and all is well (see Note [Newtype arity] in
GHC.Core.Opt.Arity)! A small example is the test case NewtypeArity.


Historical Note [Product demands for function body]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In 2013 I spotted this example, in shootout/binary_trees:

    Main.check' = \ b z ds. case z of z' { I# ip ->
                                case ds_d13s of
                                  Main.Nil -> z'
                                  Main.Node s14k s14l s14m ->
                                    Main.check' (not b)
                                      (Main.check' b
                                         (case b {
                                            False -> I# (-# s14h s14k);
                                            True  -> I# (+# s14h s14k)
                                          })
                                         s14l)
                                     s14m   }   }   }

Here we *really* want to unbox z, even though it appears to be used boxed in
the Nil case.  Partly the Nil case is not a hot path.  But more specifically,
the whole function gets the CPR property if we do.

That motivated using a demand of C(C(C(S(L,L)))) for the RHS, where
(solely because the result was a product) we used a product demand
(albeit with lazy components) for the body. But that gives very silly
behaviour -- see #17932.   Happily it turns out now to be entirely
unnecessary: we get good results with C(C(C(S))).   So I simply
deleted the special case.
-}

{- *********************************************************************
*                                                                      *
                      Fixpoints
*                                                                      *
********************************************************************* -}

-- Recursive bindings
dmdFix :: TopLevelFlag
       -> AnalEnv                            -- Does not include bindings for this binding
       -> CleanDemand
       -> [(Id,CoreExpr)]
       -> (AnalEnv, DmdEnv, [(Id,CoreExpr)]) -- Binders annotated with strictness info

dmdFix :: TopLevelFlag
-> AnalEnv
-> CleanDemand
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
dmdFix TopLevelFlag
top_lvl AnalEnv
env CleanDemand
let_dmd [(CoreBndr, Expr CoreBndr)]
orig_pairs
  = Int
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
loop Int
1 [(CoreBndr, Expr CoreBndr)]
initial_pairs
  where
    bndrs :: [CoreBndr]
bndrs = ((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> [(CoreBndr, Expr CoreBndr)] -> [CoreBndr]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst [(CoreBndr, Expr CoreBndr)]
orig_pairs

    -- See Note [Initialising strictness]
    initial_pairs :: [(CoreBndr, Expr CoreBndr)]
initial_pairs | AnalEnv -> Bool
ae_virgin AnalEnv
env = [(CoreBndr -> StrictSig -> CoreBndr
setIdStrictness CoreBndr
id StrictSig
botSig, Expr CoreBndr
rhs) | (CoreBndr
id, Expr CoreBndr
rhs) <- [(CoreBndr, Expr CoreBndr)]
orig_pairs ]
                  | Bool
otherwise     = [(CoreBndr, Expr CoreBndr)]
orig_pairs

    -- If fixed-point iteration does not yield a result we use this instead
    -- See Note [Safe abortion in the fixed-point iteration]
    abort :: (AnalEnv, DmdEnv, [(Id,CoreExpr)])
    abort :: (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
abort = (AnalEnv
env, DmdEnv
lazy_fv', [(CoreBndr, Expr CoreBndr)]
zapped_pairs)
      where (DmdEnv
lazy_fv, [(CoreBndr, Expr CoreBndr)]
pairs') = Bool
-> [(CoreBndr, Expr CoreBndr)]
-> (DmdEnv, [(CoreBndr, Expr CoreBndr)])
step Bool
True ([(CoreBndr, Expr CoreBndr)] -> [(CoreBndr, Expr CoreBndr)]
zapIdStrictness [(CoreBndr, Expr CoreBndr)]
orig_pairs)
            -- Note [Lazy and unleashable free variables]
            non_lazy_fvs :: DmdEnv
non_lazy_fvs = [DmdEnv] -> DmdEnv
forall a. [VarEnv a] -> VarEnv a
plusVarEnvList ([DmdEnv] -> DmdEnv) -> [DmdEnv] -> DmdEnv
forall a b. (a -> b) -> a -> b
$ ((CoreBndr, Expr CoreBndr) -> DmdEnv)
-> [(CoreBndr, Expr CoreBndr)] -> [DmdEnv]
forall a b. (a -> b) -> [a] -> [b]
map (StrictSig -> DmdEnv
strictSigDmdEnv (StrictSig -> DmdEnv)
-> ((CoreBndr, Expr CoreBndr) -> StrictSig)
-> (CoreBndr, Expr CoreBndr)
-> DmdEnv
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CoreBndr -> StrictSig
idStrictness (CoreBndr -> StrictSig)
-> ((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> (CoreBndr, Expr CoreBndr)
-> StrictSig
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst) [(CoreBndr, Expr CoreBndr)]
pairs'
            lazy_fv' :: DmdEnv
lazy_fv'     = DmdEnv
lazy_fv DmdEnv -> DmdEnv -> DmdEnv
forall a. VarEnv a -> VarEnv a -> VarEnv a
`plusVarEnv` (Demand -> Demand) -> DmdEnv -> DmdEnv
forall a b. (a -> b) -> VarEnv a -> VarEnv b
mapVarEnv (Demand -> Demand -> Demand
forall a b. a -> b -> a
const Demand
topDmd) DmdEnv
non_lazy_fvs
            zapped_pairs :: [(CoreBndr, Expr CoreBndr)]
zapped_pairs = [(CoreBndr, Expr CoreBndr)] -> [(CoreBndr, Expr CoreBndr)]
zapIdStrictness [(CoreBndr, Expr CoreBndr)]
pairs'

    -- The fixed-point varies the idStrictness field of the binders, and terminates if that
    -- annotation does not change any more.
    loop :: Int -> [(Id,CoreExpr)] -> (AnalEnv, DmdEnv, [(Id,CoreExpr)])
    loop :: Int
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
loop Int
n [(CoreBndr, Expr CoreBndr)]
pairs = -- pprTrace "dmdFix" (ppr n <+> vcat [ ppr id <+> ppr (idStrictness id)
                   --                                     | (id,_)<- pairs]) $
                   Int
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
loop' Int
n [(CoreBndr, Expr CoreBndr)]
pairs

    loop' :: Int
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
loop' Int
n [(CoreBndr, Expr CoreBndr)]
pairs
      | Bool
found_fixpoint = (AnalEnv
final_anal_env, DmdEnv
lazy_fv, [(CoreBndr, Expr CoreBndr)]
pairs')
      | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
10        = (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
abort
      | Bool
otherwise      = Int
-> [(CoreBndr, Expr CoreBndr)]
-> (AnalEnv, DmdEnv, [(CoreBndr, Expr CoreBndr)])
loop (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) [(CoreBndr, Expr CoreBndr)]
pairs'
      where
        found_fixpoint :: Bool
found_fixpoint    = ((CoreBndr, Expr CoreBndr) -> StrictSig)
-> [(CoreBndr, Expr CoreBndr)] -> [StrictSig]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr -> StrictSig
idStrictness (CoreBndr -> StrictSig)
-> ((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> (CoreBndr, Expr CoreBndr)
-> StrictSig
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst) [(CoreBndr, Expr CoreBndr)]
pairs' [StrictSig] -> [StrictSig] -> Bool
forall a. Eq a => a -> a -> Bool
== ((CoreBndr, Expr CoreBndr) -> StrictSig)
-> [(CoreBndr, Expr CoreBndr)] -> [StrictSig]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr -> StrictSig
idStrictness (CoreBndr -> StrictSig)
-> ((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> (CoreBndr, Expr CoreBndr)
-> StrictSig
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst) [(CoreBndr, Expr CoreBndr)]
pairs
        first_round :: Bool
first_round       = Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
        (DmdEnv
lazy_fv, [(CoreBndr, Expr CoreBndr)]
pairs') = Bool
-> [(CoreBndr, Expr CoreBndr)]
-> (DmdEnv, [(CoreBndr, Expr CoreBndr)])
step Bool
first_round [(CoreBndr, Expr CoreBndr)]
pairs
        final_anal_env :: AnalEnv
final_anal_env    = TopLevelFlag -> AnalEnv -> [CoreBndr] -> AnalEnv
extendAnalEnvs TopLevelFlag
top_lvl AnalEnv
env (((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> [(CoreBndr, Expr CoreBndr)] -> [CoreBndr]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst [(CoreBndr, Expr CoreBndr)]
pairs')

    step :: Bool -> [(Id, CoreExpr)] -> (DmdEnv, [(Id, CoreExpr)])
    step :: Bool
-> [(CoreBndr, Expr CoreBndr)]
-> (DmdEnv, [(CoreBndr, Expr CoreBndr)])
step Bool
first_round [(CoreBndr, Expr CoreBndr)]
pairs = (DmdEnv
lazy_fv, [(CoreBndr, Expr CoreBndr)]
pairs')
      where
        -- In all but the first iteration, delete the virgin flag
        start_env :: AnalEnv
start_env | Bool
first_round = AnalEnv
env
                  | Bool
otherwise   = AnalEnv -> AnalEnv
nonVirgin AnalEnv
env

        start :: (AnalEnv, DmdEnv)
start = (TopLevelFlag -> AnalEnv -> [CoreBndr] -> AnalEnv
extendAnalEnvs TopLevelFlag
top_lvl AnalEnv
start_env (((CoreBndr, Expr CoreBndr) -> CoreBndr)
-> [(CoreBndr, Expr CoreBndr)] -> [CoreBndr]
forall a b. (a -> b) -> [a] -> [b]
map (CoreBndr, Expr CoreBndr) -> CoreBndr
forall a b. (a, b) -> a
fst [(CoreBndr, Expr CoreBndr)]
pairs), DmdEnv
emptyDmdEnv)

        ((AnalEnv
_,DmdEnv
lazy_fv), [(CoreBndr, Expr CoreBndr)]
pairs') = ((AnalEnv, DmdEnv)
 -> (CoreBndr, Expr CoreBndr)
 -> ((AnalEnv, DmdEnv), (CoreBndr, Expr CoreBndr)))
-> (AnalEnv, DmdEnv)
-> [(CoreBndr, Expr CoreBndr)]
-> ((AnalEnv, DmdEnv), [(CoreBndr, Expr CoreBndr)])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL (AnalEnv, DmdEnv)
-> (CoreBndr, Expr CoreBndr)
-> ((AnalEnv, DmdEnv), (CoreBndr, Expr CoreBndr))
my_downRhs (AnalEnv, DmdEnv)
start [(CoreBndr, Expr CoreBndr)]
pairs
                -- mapAccumL: Use the new signature to do the next pair
                -- The occurrence analyser has arranged them in a good order
                -- so this can significantly reduce the number of iterations needed

        my_downRhs :: (AnalEnv, DmdEnv)
-> (CoreBndr, Expr CoreBndr)
-> ((AnalEnv, DmdEnv), (CoreBndr, Expr CoreBndr))
my_downRhs (AnalEnv
env, DmdEnv
lazy_fv) (CoreBndr
id,Expr CoreBndr
rhs)
          = ((AnalEnv
env', DmdEnv
lazy_fv'), (CoreBndr
id', Expr CoreBndr
rhs'))
          where
            (DmdEnv
lazy_fv1, StrictSig
sig, Expr CoreBndr
rhs') = Maybe [CoreBndr]
-> AnalEnv
-> CleanDemand
-> CoreBndr
-> Expr CoreBndr
-> (DmdEnv, StrictSig, Expr CoreBndr)
dmdAnalRhsLetDown ([CoreBndr] -> Maybe [CoreBndr]
forall a. a -> Maybe a
Just [CoreBndr]
bndrs) AnalEnv
env CleanDemand
let_dmd CoreBndr
id Expr CoreBndr
rhs
            lazy_fv' :: DmdEnv
lazy_fv'              = (Demand -> Demand -> Demand) -> DmdEnv -> DmdEnv -> DmdEnv
forall a. (a -> a -> a) -> VarEnv a -> VarEnv a -> VarEnv a
plusVarEnv_C Demand -> Demand -> Demand
bothDmd DmdEnv
lazy_fv DmdEnv
lazy_fv1
            env' :: AnalEnv
env'                  = TopLevelFlag -> AnalEnv -> CoreBndr -> StrictSig -> AnalEnv
extendAnalEnv TopLevelFlag
top_lvl AnalEnv
env CoreBndr
id StrictSig
sig
            id' :: CoreBndr
id'                   = CoreBndr -> StrictSig -> CoreBndr
setIdStrictness CoreBndr
id StrictSig
sig

    zapIdStrictness :: [(Id, CoreExpr)] -> [(Id, CoreExpr)]
    zapIdStrictness :: [(CoreBndr, Expr CoreBndr)] -> [(CoreBndr, Expr CoreBndr)]
zapIdStrictness [(CoreBndr, Expr CoreBndr)]
pairs = [(CoreBndr -> StrictSig -> CoreBndr
setIdStrictness CoreBndr
id StrictSig
nopSig, Expr CoreBndr
rhs) | (CoreBndr
id, Expr CoreBndr
rhs) <- [(CoreBndr, Expr CoreBndr)]
pairs ]

{- Note [Safe abortion in the fixed-point iteration]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Fixed-point iteration may fail to terminate. But we cannot simply give up and
return the environment and code unchanged! We still need to do one additional
round, for two reasons:

 * To get information on used free variables (both lazy and strict!)
   (see Note [Lazy and unleashable free variables])
 * To ensure that all expressions have been traversed at least once, and any left-over
   strictness annotations have been updated.

This final iteration does not add the variables to the strictness signature
environment, which effectively assigns them 'nopSig' (see "getStrictness")

Note [Trimming a demand to a type]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
There are two reasons we sometimes trim a demand to match a type.
  1. GADTs
  2. Recursive products and widening

More on both below.  But the botttom line is: we really don't want to
have a binder whose demand is more deeply-nested than its type
"allows". So in findBndrDmd we call trimToType and findTypeShape to
trim the demand on the binder to a form that matches the type

Now to the reasons. For (1) consider
  f :: a -> Bool
  f x = case ... of
          A g1 -> case (x |> g1) of (p,q) -> ...
          B    -> error "urk"

where A,B are the constructors of a GADT.  We'll get a U(U,U) demand
on x from the A branch, but that's a stupid demand for x itself, which
has type 'a'. Indeed we get ASSERTs going off (notably in
splitUseProdDmd, #8569).

For (2) consider
  data T = MkT Int T    -- A recursive product
  f :: Int -> T -> Int
  f 0 _         = 0
  f _ (MkT n t) = f n t

Here f is lazy in T, but its *usage* is infinite: U(U,U(U,U(U, ...))).
Notice that this happens becuase T is a product type, and is recrusive.
If we are not careful, we'll fail to iterate to a fixpoint in dmdFix,
and bale out entirely, which is inefficient and over-conservative.

Worse, as we discovered in #18304, the size of the usages we compute
can grow /exponentially/, so even 10 iterations costs far too much.
Especially since we then discard the result.

To avoid this we use the same findTypeShape function as for (1), but
arrange that it trims the demand if it encounters the same type constructor
twice (or three times, etc).  We use our standard RecTcChecker mechanism
for this -- see GHC.Core.Opt.WorkWrap.Utils.findTypeShape.

This is usually call "widening".  We could do it just in dmdFix, but
since are doing this findTypeShape business /anyway/ because of (1),
and it has all the right information to hand, it's extremely
convenient to do it there.

-}

{- *********************************************************************
*                                                                      *
                 Strictness signatures and types
*                                                                      *
********************************************************************* -}

unitDmdType :: DmdEnv -> DmdType
unitDmdType :: DmdEnv -> DmdType
unitDmdType DmdEnv
dmd_env = DmdEnv -> [Demand] -> Divergence -> DmdType
DmdType DmdEnv
dmd_env [] Divergence
topDiv

coercionDmdEnv :: Coercion -> DmdEnv
coercionDmdEnv :: Coercion -> DmdEnv
coercionDmdEnv Coercion
co = (CoreBndr -> Demand) -> VarEnv CoreBndr -> DmdEnv
forall a b. (a -> b) -> VarEnv a -> VarEnv b
mapVarEnv (Demand -> CoreBndr -> Demand
forall a b. a -> b -> a
const Demand
topDmd) (UniqSet CoreBndr -> VarEnv CoreBndr
forall a. UniqSet a -> UniqFM a a
getUniqSet (UniqSet CoreBndr -> VarEnv CoreBndr)
-> UniqSet CoreBndr -> VarEnv CoreBndr
forall a b. (a -> b) -> a -> b
$ Coercion -> UniqSet CoreBndr
coVarsOfCo Coercion
co)
                    -- The VarSet from coVarsOfCo is really a VarEnv Var

addVarDmd :: DmdType -> Var -> Demand -> DmdType
addVarDmd :: DmdType -> CoreBndr -> Demand -> DmdType
addVarDmd (DmdType DmdEnv
fv [Demand]
ds Divergence
res) CoreBndr
var Demand
dmd
  = DmdEnv -> [Demand] -> Divergence -> DmdType
DmdType ((Demand -> Demand -> Demand)
-> DmdEnv -> CoreBndr -> Demand -> DmdEnv
forall a. (a -> a -> a) -> VarEnv a -> CoreBndr -> a -> VarEnv a
extendVarEnv_C Demand -> Demand -> Demand
bothDmd DmdEnv
fv CoreBndr
var Demand
dmd) [Demand]
ds Divergence
res

addLazyFVs :: DmdType -> DmdEnv -> DmdType
addLazyFVs :: DmdType -> DmdEnv -> DmdType
addLazyFVs DmdType
dmd_ty DmdEnv
lazy_fvs
  = DmdType
dmd_ty DmdType -> BothDmdArg -> DmdType
`bothDmdType` DmdEnv -> BothDmdArg
mkBothDmdArg DmdEnv
lazy_fvs
        -- Using bothDmdType (rather than just both'ing the envs)
        -- is vital.  Consider
        --      let f = \x -> (x,y)
        --      in  error (f 3)
        -- Here, y is treated as a lazy-fv of f, but we must `bothDmd` that L
        -- demand with the bottom coming up from 'error'
        --
        -- I got a loop in the fixpointer without this, due to an interaction
        -- with the lazy_fv filtering in dmdAnalRhsLetDown.  Roughly, it was
        --      letrec f n x
        --          = letrec g y = x `fatbar`
        --                         letrec h z = z + ...g...
        --                         in h (f (n-1) x)
        --      in ...
        -- In the initial iteration for f, f=Bot
        -- Suppose h is found to be strict in z, but the occurrence of g in its RHS
        -- is lazy.  Now consider the fixpoint iteration for g, esp the demands it
        -- places on its free variables.  Suppose it places none.  Then the
        --      x `fatbar` ...call to h...
        -- will give a x->V demand for x.  That turns into a L demand for x,
        -- which floats out of the defn for h.  Without the modifyEnv, that
        -- L demand doesn't get both'd with the Bot coming up from the inner
        -- call to f.  So we just get an L demand for x for g.

{-
Note [Do not strictify the argument dictionaries of a dfun]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The typechecker can tie recursive knots involving dfuns, so we do the
conservative thing and refrain from strictifying a dfun's argument
dictionaries.
-}

setBndrsDemandInfo :: [Var] -> [Demand] -> [Var]
setBndrsDemandInfo :: [CoreBndr] -> [Demand] -> [CoreBndr]
setBndrsDemandInfo (CoreBndr
b:[CoreBndr]
bs) (Demand
d:[Demand]
ds)
  | CoreBndr -> Bool
isTyVar CoreBndr
b = CoreBndr
b CoreBndr -> [CoreBndr] -> [CoreBndr]
forall a. a -> [a] -> [a]
: [CoreBndr] -> [Demand] -> [CoreBndr]
setBndrsDemandInfo [CoreBndr]
bs (Demand
dDemand -> [Demand] -> [Demand]
forall a. a -> [a] -> [a]
:[Demand]
ds)
  | Bool
otherwise = CoreBndr -> Demand -> CoreBndr
setIdDemandInfo CoreBndr
b Demand
d CoreBndr -> [CoreBndr] -> [CoreBndr]
forall a. a -> [a] -> [a]
: [CoreBndr] -> [Demand] -> [CoreBndr]
setBndrsDemandInfo [CoreBndr]
bs [Demand]
ds
setBndrsDemandInfo [] [Demand]
ds = ASSERT( null ds ) []
setBndrsDemandInfo [CoreBndr]
bs [Demand]
_  = String -> SDoc -> [CoreBndr]
forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"setBndrsDemandInfo" ([CoreBndr] -> SDoc
forall a. Outputable a => a -> SDoc
ppr [CoreBndr]
bs)

annotateBndr :: AnalEnv -> DmdType -> Var -> (DmdType, Var)
-- The returned env has the var deleted
-- The returned var is annotated with demand info
-- according to the result demand of the provided demand type
-- No effect on the argument demands
annotateBndr :: AnalEnv -> DmdType -> CoreBndr -> (DmdType, CoreBndr)
annotateBndr AnalEnv
env DmdType
dmd_ty CoreBndr
var
  | CoreBndr -> Bool
isId CoreBndr
var  = (DmdType
dmd_ty', CoreBndr -> Demand -> CoreBndr
setIdDemandInfo CoreBndr
var Demand
dmd)
  | Bool
otherwise = (DmdType
dmd_ty, CoreBndr
var)
  where
    (DmdType
dmd_ty', Demand
dmd) = AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, Demand)
findBndrDmd AnalEnv
env Bool
False DmdType
dmd_ty CoreBndr
var

annotateLamIdBndr :: AnalEnv
                  -> DFunFlag   -- is this lambda at the top of the RHS of a dfun?
                  -> DmdType    -- Demand type of body
                  -> Id         -- Lambda binder
                  -> (DmdType,  -- Demand type of lambda
                      Id)       -- and binder annotated with demand

annotateLamIdBndr :: AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, CoreBndr)
annotateLamIdBndr AnalEnv
env Bool
arg_of_dfun DmdType
dmd_ty CoreBndr
id
-- For lambdas we add the demand to the argument demands
-- Only called for Ids
  = ASSERT( isId id )
    -- pprTrace "annLamBndr" (vcat [ppr id, ppr _dmd_ty]) $
    (DmdType
final_ty, CoreBndr -> Demand -> CoreBndr
setIdDemandInfo CoreBndr
id Demand
dmd)
  where
      -- Watch out!  See note [Lambda-bound unfoldings]
    final_ty :: DmdType
final_ty = case Unfolding -> Maybe (Expr CoreBndr)
maybeUnfoldingTemplate (CoreBndr -> Unfolding
idUnfolding CoreBndr
id) of
                 Maybe (Expr CoreBndr)
Nothing  -> DmdType
main_ty
                 Just Expr CoreBndr
unf -> DmdType
main_ty DmdType -> BothDmdArg -> DmdType
`bothDmdType` BothDmdArg
unf_ty
                          where
                             (BothDmdArg
unf_ty, Expr CoreBndr
_) = AnalEnv -> Demand -> Expr CoreBndr -> (BothDmdArg, Expr CoreBndr)
dmdAnalStar AnalEnv
env Demand
dmd Expr CoreBndr
unf

    main_ty :: DmdType
main_ty = Demand -> DmdType -> DmdType
addDemand Demand
dmd DmdType
dmd_ty'
    (DmdType
dmd_ty', Demand
dmd) = AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, Demand)
findBndrDmd AnalEnv
env Bool
arg_of_dfun DmdType
dmd_ty CoreBndr
id

deleteFVs :: DmdType -> [Var] -> DmdType
deleteFVs :: DmdType -> [CoreBndr] -> DmdType
deleteFVs (DmdType DmdEnv
fvs [Demand]
dmds Divergence
res) [CoreBndr]
bndrs
  = DmdEnv -> [Demand] -> Divergence -> DmdType
DmdType (DmdEnv -> [CoreBndr] -> DmdEnv
forall a. VarEnv a -> [CoreBndr] -> VarEnv a
delVarEnvList DmdEnv
fvs [CoreBndr]
bndrs) [Demand]
dmds Divergence
res

{-
Note [NOINLINE and strictness]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The strictness analyser used to have a HACK which ensured that NOINLNE
things were not strictness-analysed.  The reason was unsafePerformIO.
Left to itself, the strictness analyser would discover this strictness
for unsafePerformIO:
        unsafePerformIO:  C(U(AV))
But then consider this sub-expression
        unsafePerformIO (\s -> let r = f x in
                               case writeIORef v r s of (# s1, _ #) ->
                               (# s1, r #)
The strictness analyser will now find that r is sure to be eval'd,
and may then hoist it out.  This makes tests/lib/should_run/memo002
deadlock.

Solving this by making all NOINLINE things have no strictness info is overkill.
In particular, it's overkill for runST, which is perfectly respectable.
Consider
        f x = runST (return x)
This should be strict in x.

So the new plan is to define unsafePerformIO using the 'lazy' combinator:

        unsafePerformIO (IO m) = lazy (case m realWorld# of (# _, r #) -> r)

Remember, 'lazy' is a wired-in identity-function Id, of type a->a, which is
magically NON-STRICT, and is inlined after strictness analysis.  So
unsafePerformIO will look non-strict, and that's what we want.

Now we don't need the hack in the strictness analyser.  HOWEVER, this
decision does mean that even a NOINLINE function is not entirely
opaque: some aspect of its implementation leaks out, notably its
strictness.  For example, if you have a function implemented by an
error stub, but which has RULES, you may want it not to be eliminated
in favour of error!

Note [Lazy and unleashable free variables]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We put the strict and once-used FVs in the DmdType of the Id, so
that at its call sites we unleash demands on its strict fvs.
An example is 'roll' in imaginary/wheel-sieve2
Something like this:
        roll x = letrec
                     go y = if ... then roll (x-1) else x+1
                 in
                 go ms
We want to see that roll is strict in x, which is because
go is called.   So we put the DmdEnv for x in go's DmdType.

Another example:

        f :: Int -> Int -> Int
        f x y = let t = x+1
            h z = if z==0 then t else
                  if z==1 then x+1 else
                  x + h (z-1)
        in h y

Calling h does indeed evaluate x, but we can only see
that if we unleash a demand on x at the call site for t.

Incidentally, here's a place where lambda-lifting h would
lose the cigar --- we couldn't see the joint strictness in t/x

        ON THE OTHER HAND

We don't want to put *all* the fv's from the RHS into the
DmdType. Because

 * it makes the strictness signatures larger, and hence slows down fixpointing

and

 * it is useless information at the call site anyways:
   For lazy, used-many times fv's we will never get any better result than
   that, no matter how good the actual demand on the function at the call site
   is (unless it is always absent, but then the whole binder is useless).

Therefore we exclude lazy multiple-used fv's from the environment in the
DmdType.

But now the signature lies! (Missing variables are assumed to be absent.) To
make up for this, the code that analyses the binding keeps the demand on those
variable separate (usually called "lazy_fv") and adds it to the demand of the
whole binding later.

What if we decide _not_ to store a strictness signature for a binding at all, as
we do when aborting a fixed-point iteration? The we risk losing the information
that the strict variables are being used. In that case, we take all free variables
mentioned in the (unsound) strictness signature, conservatively approximate the
demand put on them (topDmd), and add that to the "lazy_fv" returned by "dmdFix".


Note [Lambda-bound unfoldings]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We allow a lambda-bound variable to carry an unfolding, a facility that is used
exclusively for join points; see Note [Case binders and join points].  If so,
we must be careful to demand-analyse the RHS of the unfolding!  Example
   \x. \y{=Just x}. <body>
Then if <body> uses 'y', then transitively it uses 'x', and we must not
forget that fact, otherwise we might make 'x' absent when it isn't.


************************************************************************
*                                                                      *
\subsection{Strictness signatures}
*                                                                      *
************************************************************************
-}

type DFunFlag = Bool  -- indicates if the lambda being considered is in the
                      -- sequence of lambdas at the top of the RHS of a dfun
notArgOfDfun :: DFunFlag
notArgOfDfun :: Bool
notArgOfDfun = Bool
False

{-  Note [dmdAnalEnv performance]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

It's tempting to think that removing the dynflags from AnalEnv would improve
performance. After all when analysing recursive groups we end up allocating
a lot of environments. However this is not the case.

We do get some performance by making AnalEnv smaller. However very often we
defer computation which means we have to capture the dynflags in the thunks
we allocate. Doing this naively in practice causes more allocation than the
removal of DynFlags saves us.

In theory it should be possible to make this better if we are stricter in
the analysis and therefore allocate fewer thunks. But I couldn't get there
in a few hours and overall the impact on GHC here is small, and there are
bigger fish to fry. So for new the env will keep a reference to the flags.
-}

data AnalEnv
  = AE { AnalEnv -> DynFlags
ae_dflags :: DynFlags -- See Note [dmdAnalEnv performance]
       , AnalEnv -> SigEnv
ae_sigs   :: SigEnv
       , AnalEnv -> Bool
ae_virgin :: Bool    -- True on first iteration only
                              -- See Note [Initialising strictness]
       , AnalEnv -> FamInstEnvs
ae_fam_envs :: FamInstEnvs
 }

        -- We use the se_env to tell us whether to
        -- record info about a variable in the DmdEnv
        -- We do so if it's a LocalId, but not top-level
        --
        -- The DmdEnv gives the demand on the free vars of the function
        -- when it is given enough args to satisfy the strictness signature

type SigEnv = VarEnv (StrictSig, TopLevelFlag)

instance Outputable AnalEnv where
  ppr :: AnalEnv -> SDoc
ppr (AE { ae_sigs :: AnalEnv -> SigEnv
ae_sigs = SigEnv
env, ae_virgin :: AnalEnv -> Bool
ae_virgin = Bool
virgin })
    = String -> SDoc
text String
"AE" SDoc -> SDoc -> SDoc
<+> SDoc -> SDoc
braces ([SDoc] -> SDoc
vcat
         [ String -> SDoc
text String
"ae_virgin =" SDoc -> SDoc -> SDoc
<+> Bool -> SDoc
forall a. Outputable a => a -> SDoc
ppr Bool
virgin
         , String -> SDoc
text String
"ae_sigs =" SDoc -> SDoc -> SDoc
<+> SigEnv -> SDoc
forall a. Outputable a => a -> SDoc
ppr SigEnv
env ])

emptyAnalEnv :: DynFlags -> FamInstEnvs -> AnalEnv
emptyAnalEnv :: DynFlags -> FamInstEnvs -> AnalEnv
emptyAnalEnv DynFlags
dflags FamInstEnvs
fam_envs
    = AE :: DynFlags -> SigEnv -> Bool -> FamInstEnvs -> AnalEnv
AE { ae_dflags :: DynFlags
ae_dflags = DynFlags
dflags
         , ae_sigs :: SigEnv
ae_sigs = SigEnv
emptySigEnv
         , ae_virgin :: Bool
ae_virgin = Bool
True
         , ae_fam_envs :: FamInstEnvs
ae_fam_envs = FamInstEnvs
fam_envs
         }

emptySigEnv :: SigEnv
emptySigEnv :: SigEnv
emptySigEnv = SigEnv
forall a. VarEnv a
emptyVarEnv

-- | Extend an environment with the strictness IDs attached to the id
extendAnalEnvs :: TopLevelFlag -> AnalEnv -> [Id] -> AnalEnv
extendAnalEnvs :: TopLevelFlag -> AnalEnv -> [CoreBndr] -> AnalEnv
extendAnalEnvs TopLevelFlag
top_lvl AnalEnv
env [CoreBndr]
vars
  = AnalEnv
env { ae_sigs :: SigEnv
ae_sigs = TopLevelFlag -> SigEnv -> [CoreBndr] -> SigEnv
extendSigEnvs TopLevelFlag
top_lvl (AnalEnv -> SigEnv
ae_sigs AnalEnv
env) [CoreBndr]
vars }

extendSigEnvs :: TopLevelFlag -> SigEnv -> [Id] -> SigEnv
extendSigEnvs :: TopLevelFlag -> SigEnv -> [CoreBndr] -> SigEnv
extendSigEnvs TopLevelFlag
top_lvl SigEnv
sigs [CoreBndr]
vars
  = SigEnv -> [(CoreBndr, (StrictSig, TopLevelFlag))] -> SigEnv
forall a. VarEnv a -> [(CoreBndr, a)] -> VarEnv a
extendVarEnvList SigEnv
sigs [ (CoreBndr
var, (CoreBndr -> StrictSig
idStrictness CoreBndr
var, TopLevelFlag
top_lvl)) | CoreBndr
var <- [CoreBndr]
vars]

extendAnalEnv :: TopLevelFlag -> AnalEnv -> Id -> StrictSig -> AnalEnv
extendAnalEnv :: TopLevelFlag -> AnalEnv -> CoreBndr -> StrictSig -> AnalEnv
extendAnalEnv TopLevelFlag
top_lvl AnalEnv
env CoreBndr
var StrictSig
sig
  = AnalEnv
env { ae_sigs :: SigEnv
ae_sigs = TopLevelFlag -> SigEnv -> CoreBndr -> StrictSig -> SigEnv
extendSigEnv TopLevelFlag
top_lvl (AnalEnv -> SigEnv
ae_sigs AnalEnv
env) CoreBndr
var StrictSig
sig }

extendSigEnv :: TopLevelFlag -> SigEnv -> Id -> StrictSig -> SigEnv
extendSigEnv :: TopLevelFlag -> SigEnv -> CoreBndr -> StrictSig -> SigEnv
extendSigEnv TopLevelFlag
top_lvl SigEnv
sigs CoreBndr
var StrictSig
sig = SigEnv -> CoreBndr -> (StrictSig, TopLevelFlag) -> SigEnv
forall a. VarEnv a -> CoreBndr -> a -> VarEnv a
extendVarEnv SigEnv
sigs CoreBndr
var (StrictSig
sig, TopLevelFlag
top_lvl)

lookupSigEnv :: AnalEnv -> Id -> Maybe (StrictSig, TopLevelFlag)
lookupSigEnv :: AnalEnv -> CoreBndr -> Maybe (StrictSig, TopLevelFlag)
lookupSigEnv AnalEnv
env CoreBndr
id = SigEnv -> CoreBndr -> Maybe (StrictSig, TopLevelFlag)
forall a. VarEnv a -> CoreBndr -> Maybe a
lookupVarEnv (AnalEnv -> SigEnv
ae_sigs AnalEnv
env) CoreBndr
id

nonVirgin :: AnalEnv -> AnalEnv
nonVirgin :: AnalEnv -> AnalEnv
nonVirgin AnalEnv
env = AnalEnv
env { ae_virgin :: Bool
ae_virgin = Bool
False }

findBndrsDmds :: AnalEnv -> DmdType -> [Var] -> (DmdType, [Demand])
-- Return the demands on the Ids in the [Var]
findBndrsDmds :: AnalEnv -> DmdType -> [CoreBndr] -> (DmdType, [Demand])
findBndrsDmds AnalEnv
env DmdType
dmd_ty [CoreBndr]
bndrs
  = DmdType -> [CoreBndr] -> (DmdType, [Demand])
go DmdType
dmd_ty [CoreBndr]
bndrs
  where
    go :: DmdType -> [CoreBndr] -> (DmdType, [Demand])
go DmdType
dmd_ty []  = (DmdType
dmd_ty, [])
    go DmdType
dmd_ty (CoreBndr
b:[CoreBndr]
bs)
      | CoreBndr -> Bool
isId CoreBndr
b    = let (DmdType
dmd_ty1, [Demand]
dmds) = DmdType -> [CoreBndr] -> (DmdType, [Demand])
go DmdType
dmd_ty [CoreBndr]
bs
                        (DmdType
dmd_ty2, Demand
dmd)  = AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, Demand)
findBndrDmd AnalEnv
env Bool
False DmdType
dmd_ty1 CoreBndr
b
                    in (DmdType
dmd_ty2, Demand
dmd Demand -> [Demand] -> [Demand]
forall a. a -> [a] -> [a]
: [Demand]
dmds)
      | Bool
otherwise = DmdType -> [CoreBndr] -> (DmdType, [Demand])
go DmdType
dmd_ty [CoreBndr]
bs

findBndrDmd :: AnalEnv -> Bool -> DmdType -> Id -> (DmdType, Demand)
-- See Note [Trimming a demand to a type]
findBndrDmd :: AnalEnv -> Bool -> DmdType -> CoreBndr -> (DmdType, Demand)
findBndrDmd AnalEnv
env Bool
arg_of_dfun DmdType
dmd_ty CoreBndr
id
  = (DmdType
dmd_ty', Demand
dmd')
  where
    dmd' :: Demand
dmd' = Demand -> Demand
strictify (Demand -> Demand) -> Demand -> Demand
forall a b. (a -> b) -> a -> b
$
           Demand -> TypeShape -> Demand
trimToType Demand
starting_dmd (FamInstEnvs -> Type -> TypeShape
findTypeShape FamInstEnvs
fam_envs Type
id_ty)

    (DmdType
dmd_ty', Demand
starting_dmd) = DmdType -> CoreBndr -> (DmdType, Demand)
peelFV DmdType
dmd_ty CoreBndr
id

    id_ty :: Type
id_ty = CoreBndr -> Type
idType CoreBndr
id

    strictify :: Demand -> Demand
strictify Demand
dmd
      | GeneralFlag -> DynFlags -> Bool
gopt GeneralFlag
Opt_DictsStrict (AnalEnv -> DynFlags
ae_dflags AnalEnv
env)
             -- We never want to strictify a recursive let. At the moment
             -- annotateBndr is only call for non-recursive lets; if that
             -- changes, we need a RecFlag parameter and another guard here.
      , Bool -> Bool
not Bool
arg_of_dfun -- See Note [Do not strictify the argument dictionaries of a dfun]
      = Type -> Demand -> Demand
strictifyDictDmd Type
id_ty Demand
dmd
      | Bool
otherwise
      = Demand
dmd

    fam_envs :: FamInstEnvs
fam_envs = AnalEnv -> FamInstEnvs
ae_fam_envs AnalEnv
env

{- Note [Initialising strictness]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
See section 9.2 (Finding fixpoints) of the paper.

Our basic plan is to initialise the strictness of each Id in a
recursive group to "bottom", and find a fixpoint from there.  However,
this group B might be inside an *enclosing* recursive group A, in
which case we'll do the entire fixpoint shebang on for each iteration
of A. This can be illustrated by the following example:

Example:

  f [] = []
  f (x:xs) = let g []     = f xs
                 g (y:ys) = y+1 : g ys
              in g (h x)

At each iteration of the fixpoint for f, the analyser has to find a
fixpoint for the enclosed function g. In the meantime, the demand
values for g at each iteration for f are *greater* than those we
encountered in the previous iteration for f. Therefore, we can begin
the fixpoint for g not with the bottom value but rather with the
result of the previous analysis. I.e., when beginning the fixpoint
process for g, we can start from the demand signature computed for g
previously and attached to the binding occurrence of g.

To speed things up, we initialise each iteration of A (the enclosing
one) from the result of the last one, which is neatly recorded in each
binder.  That way we make use of earlier iterations of the fixpoint
algorithm. (Cunning plan.)

But on the *first* iteration we want to *ignore* the current strictness
of the Id, and start from "bottom".  Nowadays the Id can have a current
strictness, because interface files record strictness for nested bindings.
To know when we are in the first iteration, we look at the ae_virgin
field of the AnalEnv.


Note [Final Demand Analyser run]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Some of the information that the demand analyser determines is not always
preserved by the simplifier.  For example, the simplifier will happily rewrite
  \y [Demand=1*U] let x = y in x + x
to
  \y [Demand=1*U] y + y
which is quite a lie.

The once-used information is (currently) only used by the code
generator, though.  So:

 * We zap the used-once info in the worker-wrapper;
   see Note [Zapping Used Once info in WorkWrap] in
   GHC.Core.Opt.WorkWrap.
   If it's not reliable, it's better not to have it at all.

 * Just before TidyCore, we add a pass of the demand analyser,
      but WITHOUT subsequent worker/wrapper and simplifier,
   right before TidyCore.  See SimplCore.getCoreToDo.

   This way, correct information finds its way into the module interface
   (strictness signatures!) and the code generator (single-entry thunks!)

Note that, in contrast, the single-call information (C1(..)) /can/ be
relied upon, as the simplifier tends to be very careful about not
duplicating actual function calls.

Also see #11731.
-}