GHC Handbook

Follow one module through GHC

This page takes one small module and walks it through the compiler, phase by phase. Each section shows what the phase actually produced for this module, and the path the compiler takes through its own source to do it: the chain of calls from the driver down to the function that touches your expression, every step linked to its definition in ghc-9.14.1-release. Every caller-to-callee edge shown is verified against that source when the data is generated, so the paths cannot quietly drift from the code. Read it once and you will know where each phase lives; follow a path with the links and you are navigating GHC itself.

The module is ten lines, chosen so that every phase has something visible to do. describe carries a class constraint, which will become a dictionary you can watch travel through the pipeline. classify has a case, a where, and an if, which between them exercise the pattern-match compiler and the optimiser. 

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"

The shape of the program

Each phase hands the next a different type. Watch the module change representation, and read the signature of the function that does it: the types below are extracted from ghc-9.14.1-release itself.

Text

Ten lines of Haskell. Everything below is this module, seen through GHC.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x
HsModule GhcPs

The syntax tree as parsed: "trees that grow", parameterised by phase, names still plain strings.

produced by hscParse 
hscParse :: HscEnv -> ModSummary -> IO HsParsedModule
(L
 { examples/Journey.hs:1:1 }
 (HsModule
  (XModulePs
   (EpAnn
    (EpaSpan { examples/Journey.hs:1:1 })
    (AnnsModule
     (NoEpTok)
     (EpTok
…

Read this phase in full ↓

HsGroup GhcRn

The same tree shape, but the phase parameter changed: every name is now a Name with a unique.

produced by rnTopSrcDecls 
rnTopSrcDecls :: HsGroup GhcPs -> TcM (TcGblEnv, HsGroup GhcRn)
describe :: Show a => a -> String
describe x = "value: " ++ show x
classify :: Int -> String
classify n
  = case compare n 0 of
      LT -> "negative"
      EQ -> "zero"
      GT -> positive
  where
…

Read this phase in full ↓

LHsBinds GhcTc

The third growth of the tree: every node knows its type, and evidence bindings have appeared.

produced by tcTopBinds 
tcTopBinds :: [(RecFlag, LHsBinds GhcRn)] -> [LSig GhcRn]
           -> TcM (TcGblEnv, TcLclEnv)
$trModule = Module (TrNameS "main"#) (TrNameS "Journey"#)
AbsBinds [] []
  {Exports: [classify <= classify
               wrap: <>]
   Exported types: classify :: Int -> String
   Binds: classify n
            = case compare @Int $dOrd n 0 of
                LT{EvBinds{}} -> "negative"
                EQ{EvBinds{}} -> "zero"
…

Read this phase in full ↓

CoreProgram

A different language entirely: a handful of constructors, and no sugar left.

produced by dsTopLHsBinds 
dsTopLHsBinds :: LHsBinds GhcTc -> DsM (OrdList (Id,CoreExpr))
Result size of Desugar (after optimization)
  = {terms: 43, types: 19, coercions: 0, joins: 0/0}

-- RHS size: {terms: 9, types: 6, coercions: 0, joins: 0/0}
describe :: forall a. Show a => a -> String
describe
  = \ (@a) ($dShow :: Show a) (x :: a) ->
      ++ (unpackCString# "value: "#) (show $dShow x)

…

Read this phase in full ↓

CoreProgram

Same type in, same type out. The entire middle end is Core to Core.

produced by simplifyPgm 
simplifyPgm :: Logger
            -> UnitEnv
            -> NamePprCtx                -- For dumping
            -> SimplifyOpts
            -> ModGuts
            -> IO (SimplCount, ModGuts)  -- New bindings
Result size of Tidy Core
  = {terms: 70, types: 36, coercions: 0, joins: 0/0}

-- RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0}
describe1 :: Addr#
describe1 = "value: "#

-- RHS size: {terms: 8, types: 5, coercions: 0, joins: 0/0}
describe :: forall a. Show a => a -> String
…

Read this phase in full ↓

[StgTopBinding]

Operational at last: closures with listed free variables, update flags, saturated applications.

produced by coreToStg 
coreToStg :: CoreToStgOpts -> Module -> ModLocation -> CoreProgram
          -> ([StgTopBinding], InfoTableProvMap, CollectedCCs)
classify6 :: Addr# = "big"#;

classify8 :: Addr# = "small"#;

classify4 :: Addr# = "zero"#;

classify2 :: Addr# = "negative"#;

$trModule2 :: Addr# = "Journey"#;
…

Read this phase in full ↓

CmmGroup

An imperative program: procedures, an explicit stack, registers and jumps.

produced by codeGen 
codeGen :: Logger
        -> TmpFs
        -> StgToCmmConfig
        -> InfoTableProvMap
        -> [TyCon]
        -> CollectedCCs                -- (Local/global) cost-centres needing declaring/registering.
        -> [CgStgTopBinding]           -- Bindings to convert
        -> CgStream CmmGroup (ModuleLFInfos, DetUniqFM) -- See Note [Deterministic Uniques in the CG] on CgStream
                                       -- Output as a stream, so codegen can
                                       -- be interleaved with output

Read this phase in full ↓

1. Parsing

The lexer turns characters into tokens, applying the layout algorithm: the indentation under where becomes virtual braces and semicolons before the parser ever runs. The grammar then builds the tree you can see in the Parsed AST tab, with every node wrapped in the annotations that let GHC reprint your source byte for byte. Nothing is resolved yet: show and positive are just names.

What you wrote.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"
The raw tree, and the same tree printed back as Haskell. Note what layout became.
The path the compiler takes
hscParseDriver/Main.hs:481The driver asks for a parsed module.
hscParse'Driver/Main.hs:485The worker: reads the file, sets up the parser state.
parseModuleParser.y:4620The entry point exported from the generated parser.
parseModuleNoHaddockParser.y:774The happy grammar entry production. Everything below it is generated.
lexerParser/Lexer.x:3154Pulled per token by the parser; home of the layout algorithm.
runPVParser/PostProcess.hs:3444Runs the disambiguation monad in grammar actions, where expression-versus-pattern ambiguity is resolved.
Note [Ambiguous syntactic categories] GHC/Parser/PostProcess.hs:2498 
There are places in the grammar where we do not know whether we are parsing an
expression or a pattern without unlimited lookahead (which we do not have in
'happy'):

View patterns:

    f (Con a b     ) = ...  -- 'Con a b' is a pattern
    f (Con a b -> x) = ...  -- 'Con a b' is an expression

do-notation:

    do { Con a b <- x } -- 'Con a b' is a pattern
    do { Con a b }      -- 'Con a b' is an expression

Guards:

    x | True <- p && q = ...  -- 'True' is a pattern
    x | True           = ...  -- 'True' is an expression

Top-level value/function declarations (FunBind/PatBind):
Show the rest of this Note (89 more lines) 
    f ! a         -- TH splice
    f ! a = ...   -- function declaration

    Until we encounter the = sign, we don't know if it's a top-level
    TemplateHaskell splice where ! is used, or if it's a function declaration
    where ! is bound.

There are also places in the grammar where we do not know whether we are
parsing an expression or a command:

    proc x -> do { (stuff) -< x }   -- 'stuff' is an expression
    proc x -> do { (stuff) }        -- 'stuff' is a command

    Until we encounter arrow syntax (-<) we don't know whether to parse 'stuff'
    as an expression or a command.

In fact, do-notation is subject to both ambiguities:

    proc x -> do { (stuff) -< x }        -- 'stuff' is an expression
    proc x -> do { (stuff) <- f -< x }   -- 'stuff' is a pattern
    proc x -> do { (stuff) }             -- 'stuff' is a command

There are many possible solutions to this problem. For an overview of the ones
we decided against, see Note [Resolving parsing ambiguities: non-taken alternatives]

The solution that keeps basic definitions (such as HsExpr) clean, keeps the
concerns local to the parser, and does not require duplication of hsSyn types,
or an extra pass over the entire AST, is to parse into an overloaded
parser-validator (a so-called tagless final encoding):

    class DisambECP b where ...
    instance DisambECP (HsCmd GhcPs) where ...
    instance DisambECP (HsExp GhcPs) where ...
    instance DisambECP (PatBuilder GhcPs) where ...

The 'DisambECP' class contains functions to build and validate 'b'. For example,
to add parentheses we have:

  mkHsParPV :: DisambECP b => SrcSpan -> Located b -> PV (Located b)

'mkHsParPV' will wrap the inner value in HsCmdPar for commands, HsPar for
expressions, and 'PatBuilderPar' for patterns (later transformed into ParPat,
see Note [PatBuilder]).

Consider the 'alts' production used to parse case-of alternatives:

  alts :: { Located ([AddEpAnn],[LMatch GhcPs (LHsExpr GhcPs)]) }
    : alts1     { sL1 $1 (fst $ unLoc $1,snd $ unLoc $1) }
    | ';' alts  { sLL $1 $> ((mj AnnSemi $1:(fst $ unLoc $2)),snd $ unLoc $2) }

We abstract over LHsExpr GhcPs, and it becomes:

  alts :: { forall b. DisambECP b => PV (Located ([AddEpAnn],[LMatch GhcPs (Located b)])) }
    : alts1     { $1 >>= \ $1 ->
                  return $ sL1 $1 (fst $ unLoc $1,snd $ unLoc $1) }
    | ';' alts  { $2 >>= \ $2 ->
                  return $ sLL $1 $> ((mj AnnSemi $1:(fst $ unLoc $2)),snd $ unLoc $2) }

Compared to the initial definition, the added bits are:

    forall b. DisambECP b => PV ( ... ) -- in the type signature
    $1 >>= \ $1 -> return $             -- in one reduction rule
    $2 >>= \ $2 -> return $             -- in another reduction rule

The overhead is constant relative to the size of the rest of the reduction
rule, so this approach scales well to large parser productions.

Note that we write ($1 >>= \ $1 -> ...), so the second $1 is in a binding
position and shadows the previous $1. We can do this because internally
'happy' desugars $n to happy_var_n, and the rationale behind this idiom
is to be able to write (sLL $1 $>) later on. The alternative would be to
write this as ($1 >>= \ fresh_name -> ...), but then we couldn't refer
to the last fresh name as $>.

Finally, we instantiate the polymorphic type to a concrete one, and run the
parser-validator, for example:

    stmt   :: { forall b. DisambECP b => PV (LStmt GhcPs (Located b)) }
    e_stmt :: { LStmt GhcPs (LHsExpr GhcPs) }
            : stmt {% runPV $1 }

In e_stmt, three things happen:

  1. we instantiate: b ~ HsExpr GhcPs
  2. we embed the PV computation into P by using runPV
  3. we run validation by using a monadic production, {% ... }

At this point the ambiguity is resolved.

Depth: the parser chapter.

2. Renaming

The renamer decides what every name refers to. In the readable view the program looks almost untouched; the change is invisible because it is in the names themselves, not their spelling. Switch on Full detail and the qualification appears: ++ is GHC.Internal.Base.++, compare is the class method from GHC.Internal.Classes. This is also where positive is connected to its where binding, and where an unbound name would have died with an error.

What you wrote.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"
Same program, but every occurrence now points at one specific entity.
The path the compiler takes
tcRnModuleTc/Module.hs:202One entry point drives renaming and typechecking together.
tcRnModuleTcRnMTc/Module.hs:242Sets up the module context: imports, exports, the local environment.
tcRnSrcDeclsTc/Module.hs:554Processes the declarations, then hands the collected constraints to the solver.
tc_rn_src_declsTc/Module.hs:700The loop over declaration groups; Template Haskell splices force it to alternate renaming and typechecking.
rnTopSrcDeclsTc/Module.hs:1684Renames one top-level group.
rnSrcDeclsRename/Module.hs:105Dispatches by declaration kind. Its signature is the phase in one line.
rnValBindsRHSRename/Bind.hs:331Right-hand sides of value bindings, collecting free variables for dependency analysis.
rnLBindRename/Bind.hs:489One located binding.
rnBindRename/Bind.hs:498The binding itself.
rnMatchGroupRename/Bind.hs:1382Into the equations, and from here through the match walkers to every expression.
rnExprRename/Expr.hs:307Where the walkers land: one equation per expression form.
lookupExprOccRnRename/Env.hs:1371The lookup itself: an occurrence, resolved against everything in scope.

Depth: the renamer chapter.

3. Typechecking

The typechecker walks the module writing down what must be true: show x needs Show a, compare n 0 and n > 100 need Ord Int, and the literals need Num Int. The solver then discharges the pile: Ord Int from the instance, Show a from describe's own signature. Its own dump looks quiet, still printed at source level, because the interesting output is evidence, and evidence only becomes visible syntax in the next tab.

What you wrote.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"
The elaborated program. The solved constraints are here, but you will see them in Core.
The path the compiler takes
tc_rn_src_declsTc/Module.hs:700The same loop that renamed the group now typechecks it.
tcTopSrcDeclsTc/Module.hs:1706One renamed group, typechecked kind by kind.
tcTopBindsTc/Gen/Bind.hs:189The value bindings.
tcValBindsTc/Gen/Bind.hs:261Brings signatures into scope, then the groups.
tcBindGroupsTc/Gen/Bind.hs:299Strongly-connected groups, in dependency order.
tc_groupTc/Gen/Bind.hs:339One group, recursive or not.
tcPolyBindsTc/Gen/Bind.hs:452Decides how to generalise the group.
tcPolyCheckTc/Gen/Bind.hs:565The path taken here, because both Journey functions have signatures: check against the signature, no inference needed.
tcFunBindMatchesTc/Gen/Match.hs:108A function binding’s equations against its type.
tcMatchesTc/Gen/Match.hs:227All equations get the same type.
tcMatchTc/Gen/Match.hs:310One equation: patterns, then right-hand sides.
tcGRHSsTc/Gen/Match.hs:344Guards and bodies; from here the walkers reach every expression.
tcExprTc/Gen/Expr.hs:284Where the walkers land: one equation per expression form, generating constraints.
tcCaseMatchesTc/Gen/Match.hs:182Case alternatives: classify’s three branches are checked here.
tcAppTc/Gen/App.hs:369Applications, including instantiation: this is what show x goes through.
simplifyTopTc/Solver.hs:131After the walk: the collected WantedConstraints go to the solver.
simplifyTopWantedsTc/Solver.hs:482The top-level solving strategy, including defaulting.
solveWantedsTc/Solver/Solve.hs:80The solver loop: work list in, inert set maintained, residual constraints out.

The descent stops at tcGRHSs because from there generic walkers carry every right-hand side into tcExpr, which is why it appears as its own root: it is where all roads land. To watch this path executing rather than reading it, the Traces page shows -ddump-tc-trace for a module small enough to follow.

Note [Bidirectional type checking] GHC/Tc/Gen/HsType.hs:1037 
In types, as in terms, we use bidirectional type infefence.  The main workhorse
function looks like this:

    type ExpKind = ExpType
    data ExpType = Check TcSigmaKind | Infer ...(hole TcRhoType)...

    tcHsType :: TcTyMode -> HsType GhcRn -> ExpKind -> TcM TcType

* When the `ExpKind` argument is (Check ki), we /check/ that the type has
  kind `ki`
* When the `ExpKind` argument is (Infer hole), we /infer/ the kind of the
  type, and fill the hole with that kind

Depth: the typechecker and the constraint solver.

4. Desugaring

Now the evidence is a term you can point at. describe has grown a second argument, $dShow :: Show a: the dictionary. show $dShow x is a record selection from it. In classify, compare $fOrdInt n (I# 0#) names the concrete Ord Int instance the solver chose. The if is gone, compiled to a case; and positive has already vanished, inlined by the desugarer's simple optimiser before the real one has even started.

What you wrote.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"
All of Haskell reduced to Core. The dictionary argument $dShow is the typechecker's work made visible.
The path the compiler takes
hscDesugarDriver/Main.hs:757The driver moves to Core.
hscDesugar'Driver/Main.hs:761The worker behind the -Werror-safe wrapper.
deSugarHsToCore.hs:112The phase entry: elaborated Haskell in, Core out.
dsTopLHsBindsHsToCore/Binds.hs:100Top-level bindings, including the evidence the solver left behind.
dsLHsBindsHsToCore/Binds.hs:172The list.
dsLHsBindHsToCore/Binds.hs:179One located binding.
dsHsBindHsToCore/Binds.hs:188The binding itself; AbsBinds is where dictionary abstraction becomes a lambda.
dsLExprHsToCore/Expr.hs:269Into the expression.
dsExprHsToCore/Expr.hs:273One equation per expression form, each returning plain Core.
matchWrapperHsToCore/Match.hs:763The pattern-match compiler’s front door.
matchHsToCore/Match.hs:187Equations and guards become case trees; classify’s case is compiled here.
Note [Long-distance information] GHC/HsToCore/Pmc.hs:666 
Consider

  data Color = R | G | B
  f :: Color -> Int
  f R = …
  f c = … (case c of
          G -> True
          B -> False) …

Humans can make the "long-distance connection" between the outer pattern match
and the nested case pattern match to see that the inner pattern match is
exhaustive: @c@ can't be @R@ anymore because it was matched in the first clause
of @f@.

To achieve similar reasoning in the coverage checker, we keep track of the set
of values that can reach a particular program point (often loosely referred to
as "Covered set") in 'GHC.HsToCore.Monad.dsl_nablas'.
We fill that set with Covered Nablas returned by the exported checking
Show the rest of this Note (5 more lines) 
functions, which the call sites put into place with
'GHC.HsToCore.Monad.updPmNablas'.
Call sites also extend this set with facts from type-constraint dictionaries,
case scrutinees, etc. with the exported functions 'addTyCs', 'addCoreScrutTmCs'
and 'addHsScrutTmCs'.

Depth: the desugarer chapter.

5. The simplifier

Compare the two functions now, because the optimiser treats them completely differently. classify works at the known type Int, so its dictionary is gone: the comparisons are the raw primops <# and ># on an unboxed Int#, unboxed once at entry, and the string results have floated out as top-level constants. describe still carries $dShow, because a is whatever the caller chooses; polymorphism has a runtime cost you can see.

What you wrote.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"
One function specialised to bare primops; the other keeps its dictionary. That difference is the cost of polymorphism.
The path the compiler takes
hscSimplifyDriver/Main.hs:1864The driver hands Core to the middle end.
hscSimplify'Driver/Main.hs:1870The worker, with plugins loaded.
core2coreCore/Opt/Pipeline.hs:75The middle end as a whole.
getCoreToDoCore/Opt/Pipeline.hs:120Builds the pass list for this optimisation level. Read it to learn what -O actually means.
runCorePassesCore/Opt/Pipeline.hs:443Folds the program through the passes.
doCorePassCore/Opt/Pipeline.hs:459Dispatches one pass.
simplifyPgmCore/Opt/Simplify.hs:141One simplifier run: rewrites applied everywhere, to a fixed point or the iteration cap.
occurAnalysePgmCore/Opt/OccurAnal.hs:85Runs before each iteration; nearly every inlining decision consults its output.
simplTopBindsCore/Opt/Simplify/Iteration.hs:199Walks every top-level binding; the rewrites live under it.
Note [Specialising polymorphic dictionaries] GHC/Core/Opt/Specialise.hs:2835 
Note June 2023: This has proved to be quite a tricky optimisation to get right
see (#23469, #23109, #21229, #23445) so it is now guarded by a flag
`-fpolymorphic-specialisation`.

Consider
    class M a where { foo :: a -> Int }

    instance M (ST s) where ...
    dMST :: forall s. M (ST s)

    wimwam :: forall a. M a => a -> Int
    wimwam = /\a \(d::M a). body

    f :: ST s -> Int
    f = /\s \(x::ST s). wimwam @(ST s) (dMST @s) dx + 1

We'd like to specialise wimwam at (ST s), thus
    $swimwam :: forall s. ST s -> Int
Show the rest of this Note (82 more lines) 
    $swimwam = /\s. body[ST s/a, (dMST @s)/d]

    RULE forall s (d :: M (ST s)).
         wimwam @(ST s) d = $swimwam @s

Here are the moving parts:

(MP1) We must /not/ dump the CallInfo
        CIS wimwam (CI { ci_key = [@(ST s), dMST @s]
                       , ci_fvs = {dMST} })
      when we come to the /\s.  Instead, we simply let it continue to float
      upwards. Hence ci_fvs is an IdSet, listing the /Ids/ that
      are free in the call, but not the /TyVars/.  Hence using specArgFreeIds
      in singleCall.

  NB to be fully kosher we should explicitly quantifying the CallInfo
  over 's', but we don't bother.  This would matter if there was an
  enclosing binding of the same 's', which I don't expect to happen.

(MP2) When we come to specialise the call, we must remember to quantify
      over 's'.  That is done in the SpecType case of specHeader, where
      we add 's' (called qvars) to the binders of the RULE and the specialised
      function.

(MP3) If we have f :: forall m. Monoid m => blah, and two calls
        (f @(Endo b)      (d1 :: Monoid (Endo b))
        (f @(Endo (c->c)) (d2 :: Monoid (Endo (c->c)))
      we want to generate a specialisation only for the first.  The second
      is just a substitution instance of the first, with no greater specialisation.
      Hence the use of `removeDupCalls` in `filterCalls`.

      You might wonder if `d2` might be more specialised than `d1`; but no.
      This `removeDupCalls` thing is at the definition site of `f`, and both `d1`
      and `d2` are in scope. So `d1` is simply more polymorphic than `d2`, but
      is just as specialised.

      This distinction is sadly lost once we build a RULE, so `alreadyCovered`
      can't be so clever.  E.g if we have an existing RULE
            forall @a (d1:Ord Int) (d2: Eq a). f @a @Int d1 d2 = ...
      and a putative new rule
            forall (d1:Ord Int) (d2: Eq Int). f @Int @Int d1 d2 = ...
      we /don't/ want the existing rule to subsume the new one.

      So we sadly put up with having two rather different places where we
      eliminate duplicates: `alreadyCovered` and `removeDupCalls`.

All this arose in #13873, in the unexpected form that a SPECIALISE
pragma made the program slower!  The reason was that the specialised
function $sinsertWith arising from the pragma looked rather like `f`
above, and failed to specialise a call in its body like wimwam.
Without the pragma, the original call to `insertWith` was completely
monomorpic, and specialised in one go.

Wrinkles.

* See Note [Weird special case for SpecDict]

* With -XOverlappingInstances you might worry about this:
    class C a where ...
    instance C (Maybe Int) where ...   -- $df1 :: C (Maybe Int)
    instance C (Maybe a)   where ...   -- $df2 :: forall a. C (Maybe a)

    f :: C a => blah
    f = rhs

    g = /\a.  ...(f @(Maybe a) ($df2 a))...
    h = ...f @(Maybe Int) $df1

  There are two calls to f, but with different evidence.  This patch will
  combine them into one.  But it's OK: this code will never arise unless you
  use -XIncoherentInstances.  Even with -XOverlappingInstances, GHC tries hard
  to keep dictionaries as singleton types.  But that goes out of the window
  with -XIncoherentInstances -- and that is true even with ordianry type-class
  specialisation (at least if any inlining has taken place).

  GHC makes very few guarantees when you use -XIncoherentInstances, and its
  not worth crippling the normal case for the incoherent corner.  (The best
  thing might be to switch off specialisation altogether if incoherence is
  involved... but incoherence is a property of an instance, not a class, so
  it's a hard test to make.)

  But see Note [Specialisation and overlapping instances].

Depth: the simplifier chapter.

6. STG

In STG the memory behaviour is syntax. describe contains let describe_sat = {$dShow, x} \s [] show $dShow x: a closure, with its free variables printed in the braces, allocated on every call. That binding did not exist in your source; CorePrep introduced it to put the program in A-normal form, where every argument is a variable. The \u bindings are updatable thunks, evaluated at most once; \r marks re-entrant functions.

What you wrote.

-- | The module the "follow one module" walkthrough traces through GHC.
--   Two functions, chosen so every phase has something visible to do:
--   'describe' carries a class constraint, which becomes a dictionary
--   argument in Core, and 'classify' has a case and a local binding,
--   which become a decision tree and a let.
module Journey (describe, classify) where

describe :: Show a => a -> String
describe x = "value: " ++ show x

classify :: Int -> String
classify n =
  case compare n 0 of
    LT -> "negative"
    EQ -> "zero"
    GT -> positive
  where
    positive = if n > 100 then "big" else "small"
Count the lets and you have counted the allocations.
The path the compiler takes
hscGenHardCodeDriver/Main.hs:1917The driver’s back-end entry: everything from optimised Core to object code.
corePrepPgmCoreToStg/Prep.hs:235Normalises Core to A-normal form; describe_sat in the dump is its work.
myCoreToStgDriver/Main.hs:2371The Core-to-STG leg.
coreToStgCoreToStg.hs:245The translation itself; on the far side, a let is an allocation.
stg2stgStg/Pipeline.hs:77The STG-to-STG pass pipeline.
unariseStg/Unarise.hs:486Flattens unboxed tuples and sums away.
Note [Speculative evaluation] GHC/CoreToStg/Prep.hs:1859 
Since call-by-value is much cheaper than call-by-need, we case-bind arguments
that are either

  1. Strictly evaluated anyway, according to the DmdSig of the callee, or
  2. ok-for-spec, according to 'exprOkForSpeculation'.
     This includes DFuns `$fEqList a`, for example.
     (Could identify more in the future; see reference to !1866 below.)

While (1) is a no-brainer and always beneficial, (2) is a bit
more subtle, as the careful haddock for 'exprOkForSpeculation'
points out. Still, by case-binding the argument we don't need
to allocate a thunk for it, whose closure must be retained as
long as the callee might evaluate it. And if it is evaluated on
most code paths anyway, we get to turn the unknown eval in the
callee into a known call at the call site.

Very Nasty Wrinkle
Show the rest of this Note (65 more lines) 
We must be very careful not to speculate recursive calls!  Doing so
might well change termination behavior.

That comes up in practice for DFuns, which are considered ok-for-spec,
because they always immediately return a constructor.
See Note [NON-BOTTOM-DICTS invariant] in GHC.Core.

But not so if you speculate the recursive call, as #20836 shows:

  class Foo m => Foo m where
    runFoo :: m a -> m a
  newtype Trans m a = Trans { runTrans :: m a }
  instance Monad m => Foo (Trans m) where
    runFoo = id

(NB: class Foo m => Foo m` looks weird and needs -XUndecidableSuperClasses. The
example in #20836 is more compelling, but boils down to the same thing.)
This program compiles to the following DFun for the `Trans` instance:

  Rec {
  $fFooTrans
    = \ @m $dMonad -> C:Foo ($fFooTrans $dMonad) (\ @a -> id)
  end Rec }

Note that the DFun immediately terminates and produces a dictionary, just
like DFuns ought to, but it calls itself recursively to produce the `Foo m`
dictionary. But alas, if we treat `$fFooTrans` as always-terminating, so
that we can speculate its calls, and hence use call-by-value, we get:

  $fFooTrans
    = \ @m $dMonad -> case ($fFooTrans $dMonad) of sc ->
                      C:Foo sc (\ @a -> id)

and that's an infinite loop!
Note that this bad-ness only happens in `$fFooTrans`'s own RHS. In the
*body* of the letrec, it's absolutely fine to use call-by-value on
`foo ($fFooTrans d)`.

Our solution is this: we track in cpe_rec_ids the set of enclosing
recursively-bound Ids, the RHSs of which we are currently transforming and then
in 'exprOkForSpecEval' (a special entry point to 'exprOkForSpeculation',
basically) we'll say that any binder in this set is not ok-for-spec.

Note if we have a letrec group `Rec { f1 = rhs1; ...; fn = rhsn }`, and we
prep up `rhs1`, we have to include not only `f1`, but all binders of the group
`f1..fn` in this set, otherwise our fix is not robust wrt. mutual recursive
DFuns.

NB: If at some point we decide to have a termination analysis for general
functions (#8655, !1866), we need to take similar precautions for (guarded)
recursive functions:

  repeat x = x : repeat x

Same problem here: As written, repeat evaluates rapidly to WHNF. So `repeat x`
is a cheap call that we are willing to speculate, but *not* in repeat's RHS.
Fortunately, pce_rec_ids already has all the information we need in that case.

The problem is very similar to Note [Eta reduction in recursive RHSs].
Here as well as there it is *unsound* to change the termination properties
of the very function whose termination properties we are exploiting.

It is also similar to Note [Do not strictify a DFun's parameter dictionaries],
where marking recursive DFuns (of undecidable *instances*) strict in dictionary
*parameters* leads to quite the same change in termination as above.

Depth: the STG chapter.

7. Code generation

From here each STG closure becomes a C-- procedure with explicit stack and heap manipulation, then real machine code. The handbook's dumps stop at STG, where the interesting decisions have all been made; the chapters below follow the story into the runtime.

The path the compiler takes
hscGenHardCodeDriver/Main.hs:1917The same back-end entry, continuing past STG.
doCodeGenDriver/Main.hs:2282STG to C--, as a stream.
codeGenStgToCmm.hs:70One closure at a time.
cmmPipelineCmm/Pipeline.hs:43The C-- optimisation pipeline: stack layout, proc-point splitting.
codeOutputDriver/CodeOutput.hs:77Writes whatever the target wants: assembly, LLVM, C.
outputAsmDriver/CodeOutput.hs:200The native-assembly branch.
nativeCodeGenCmmToAsm.hs:135Instruction selection, register allocation, assembly out.

Depth: the Cmm chapter and the RTS chapter.

Where to go next

Every function named above is a place you can start reading GHC. Pick the phase that interested you, open its chapter for the ideas, and use the Note index when a comment refers to reasoning recorded elsewhere. The compiler is large, but it is a pipeline of comprehensible steps, and you have now watched all of them handle the same ten lines.