GHC Handbook

Chapter 9

STG and CorePrep

Where laziness stops being an abstraction. Every thunk, every closure and every allocation becomes something you can point at in the syntax.

Where this lives in the tree

Core is a lambda calculus: it says what a program means, not how it runs. let in Core creates a binding; whether that costs an allocation is left open.

STG (the Spineless Tagless G-machine) closes that gap. It is still recognisably functional, but every construct now corresponds to something the runtime does. A let in STG is an allocation. An application is an entry into a closure. Reading STG tells you what your program will actually do.

CorePrep first

Core cannot be translated directly, because it permits shapes the code generator has no answer for: arbitrary expressions in argument position, unsaturated constructor applications, complex nested lets. CorePrep normalises these away, producing Core in A-normal form: every argument is a variable or literal, every constructor and primop saturated.

It also does a few things that are genuinely semantic rather than cosmetic:

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

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.
Show the rest of this Note (59 more lines) 
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.

Speculative evaluation is a small, real optimisation: if a thunk is cheap and certain to be demanded, build the value now rather than a thunk that will be forced immediately. Saving a thunk saves an allocation, a write, and a later indirection.

What STG makes explicit

Three things become visible that Core left implicit.

Closures and their free variables. An STG closure records exactly which variables it captures. The size of the heap object is right there.

Update flags. A thunk that is updated after evaluation, so it is not recomputed, is distinguished from one that is not. This is memoisation made syntactic.

Constructor saturation. Every constructor application has all its arguments, so the code generator knows the size of the heap object without any analysis.

Unarisation

Unboxed tuples and unboxed sums do not exist at runtime: an unboxed tuple is not a heap object, it is several values in registers. Unarisation flattens them away, rewriting binders and applications so that one binder of an unboxed tuple type becomes several binders of component types.

The invariants afterwards are strict, because everything downstream assumes them:

Note [Post-unarisation invariants] GHC/Stg/Unarise.hs:368 
STG programs after unarisation have these invariants:

 1. No unboxed sums at all.

 2. No unboxed tuple binders. Tuples only appear in return position.

 3. Binders and literals always have zero (for void arguments) or one PrimRep.
    (i.e. typePrimRep1 won't crash; see Note [VoidRep] in GHC.Types.RepType.)

 4. DataCon applications (StgRhsCon and StgConApp) don't have void arguments.
    This means that it's safe to wrap `StgArg`s of DataCon applications with
    `GHC.StgToCmm.Env.NonVoid`, for example.

 5. Alt binders (binders in patterns) are always non-void.

Pointer tagging

The “tagless” in Spineless Tagless G-machine is historical; modern GHC very much does tag pointers. The low bits of a heap pointer, which are always zero from alignment, carry which constructor the object is, so a case on an already- evaluated value can branch on the pointer itself rather than dereferencing it and reading an info table.

Getting this right requires knowing which pointers are guaranteed already evaluated and tagged, which is a property STG must track and preserve:

Note [EPT enforcement] GHC/Stg/EnforceEpt.hs:68 
The goal of EnforceEPT pass is to mark as many binders as possible as EPT
(see Note [Evaluated and Properly Tagged]).
To find more EPT binders, it establishes the following

EPT INVARIANT:
> Any binder of
>   * a strict field (see Note [Strict fields in Core]), or
>   * a CBV argument (see Note [CBV Function Ids])
> is EPT.

(Note that prior to EPT enforcement, this invariant may *not* always be upheld.
An example can be found at the end of this Note.)
This is all to optimise code such as the following:

  data SPair a b = SP !a !b
  case p :: SP Bool Bool of
    SP x y ->
      case x of
        True  -> ...
        False -> ...

We can infer that the strict field x is EPT and hence may safely
omit the code to enter x and the check for the presence of a tag that goes along
with it. However we still branch on the tag as usual to jump to the True or
Show the rest of this Note (108 more lines) 
False case.

Note that for every example involving strict fields we could find a similar
example using CBV functions, e.g.

  $wf x[EPT] y =
    case x of
      True  -> ...
      False -> ...

is the above example translated to use a CBV function $wf.
Note that /any/ strict function can in principle be chosen as a CBV function;
however, we presently only promote worker functions such as $wf to CBV because
we see all its call sites and can use the proper by-value calling convention.
More precisely, with -O0, we guarantee that no CBV functions are visible in
the interface file, so that naïve clients do not need to know how to call CBV
functions. See Note [CBV Function Ids] for more details.

Specification

EPT enforcement works like implicit type conversions in C, such as from int to
float, only much simpler (no overloaded operations such as +).
For EPT enforcement, the "type system" in question is whether a binder is
statically EPT. We differentiate "EPT binder" from "non-EPT binder", where the
latter means "might be EPT, but we could not prove it so".
In this sense, EPT binders form a subtype of non-EPT binders.
We differentiate two conversion directions:

  * Downcast: EPT binders can be converted into non-EPT binders for free.
  * Upcast: non-EPT binders can be converted into EPT binders by inserting an eval.

The EPT invariant expresses type signatures. In particular, these type
signatures entail two things:

  * A _precondition_: Any binder that is passed as a CBV arg/strict field
    must be EPT (i.e. must have type "EPT binder").
  * A _postcondition_: Any binder of a CBV arg/strict field is EPT.

EPT enforcement is then simply a matter of figuring out where to insert
Upcasts (remember that Downcasts are free).
Since Upcasts (evals!) are not free, it is desirable to insert as few as possible.
To this end, we run a static *EPT analysis*, the purpose of which is to identify
as many EPT binders as possible.
Beyond discovering case binders and value bindings, EPT analysis exploits the
type signatures provided by the EPT invariant, looks inside returned tuples and
does some limited amount of fixpointing.
Afterwards, the *EPT rewriter* inserts the actual evals realising Upcasts.

Implementation


* EPT analysis is implemented in GHC.Stg.EnforceEpt.inferTags.
  It attaches its result to /binders/, not occurrence sites.
* The EPT rewriter establishes the EPT invariant by inserting evals. That is, if
    (a) a binder x is used to
          * construct a strict field (`SP x y`), or
          * passed as a CBV argument (`$wf x`),
        and
    (b) x was not inferred EPT,
  then the EPT rewriter inserts an eval prior to the call, e.g.
    case x of x' { __ DEFAULT -> SP x' y }.
    case x of x' { __ DEFAULT -> $wf x' }.
  (Recall that the case binder x' is always EPT.)
  This is implemented in GHC.Stg.EnforceEpt.Rewrite.rewriteTopBinds.
  This pass also propagates the EPTness from binders to occurrences.
  It is sound to insert evals on strict fields (Note [Strict fields in Core]),
  and on CBV arguments as well (Note [CBV Function Ids]).
* We also export the EPTness of top level bindings to allow this optimisation
  to work across module boundaries.
  NB: The EPT Invariant *must* be upheld, regardless of the optimisation level;
  hence EPTness is practically part of the internal ABI of a strict data
  constructor or CBV function. Note [CBV Function Ids] contains the details.
* Finally, code generation skips the thunk check when branching on binders that
  are EPT. This is done by `cgExpr`/`cgCase` in the backend.

Evaluation

EPT enforcement can have large impact on spine-strict tree data structure
performance. For containers the reduction in runtimes with this optimization
was as follows:

intmap-benchmarks:    89.30%
intset-benchmarks:    90.87%
map-benchmarks:       88.00%
sequence-benchmarks:  99.84%
set-benchmarks:       85.00%
set-operations-intmap:88.64%
set-operations-map:   74.23%
set-operations-set:   76.50%
lookupge-intmap:      89.57%
lookupge-map:         70.95%

With nofib being ~0.3% faster as well.

Note that EPT enforcement may cause regressions in rare cases.
For example consider this code:

  foo x = ...
    let c = StrictJust x
    in ...

When x cannot be inferred EPT, the rewriter transforms to

  foo x = ...
    let c = case x of x' -> StrictJust x'
    in ...

which allocates an additional thunk for `c` that returns the constructor.  Boo!

Seeing it happen

What you wrote.

{-# LANGUAGE BangPatterns #-}

-- | What demand analysis and worker/wrapper are for.
--
-- `sumStrict` is a strict accumulator loop. Demand analysis proves the
-- accumulator is always forced, and worker/wrapper splits the function into a
-- wrapper with the original boxed type and a worker taking an unboxed `Int#`.
-- Look for `$wsumStrict` in the optimised Core, and note the loop allocates
-- nothing.
--
-- `sumLazy` is the same fold without the bang. Compare the two in STG: the lazy
-- version builds a thunk per iteration, and every `let` in STG is an allocation.
module Strict where

sumStrict :: [Int] -> Int
sumStrict = go 0
  where
    go !acc [] = acc
    go !acc (x : xs) = go (acc + x) xs

sumLazy :: [Int] -> Int
sumLazy = go 0
  where
    go acc [] = acc
    go acc (x : xs) = go (acc + x) xs

-- A strict data type: the bangs let GHC unpack the fields, so a Point is two
-- unboxed Ints in one heap object rather than two pointers to two boxes.
data Point = Point !Int !Int

shift :: Int -> Point -> Point
shift d (Point x y) = Point (x + d) (y + d)

-- Constructed product result: `minMax` returns a pair, and CPR analysis lets the
-- caller receive the components directly rather than allocating the tuple.
minMax :: [Int] -> (Int, Int)
minMax [] = (0, 0)
minMax (z : zs) = go z z zs
  where
    go !lo !hi [] = (lo, hi)
    go !lo !hi (w : ws) = go (min lo w) (max hi w) ws
Two folds that differ only by a bang pattern. In STG the consequence is countable: every let is an allocation.

This is the most practical skill the dump offers. let in STG means allocate a closure, so counting lets inside a loop tells you what it costs per iteration, no profiling required.

Compare sumStrict with sumLazy here. The strict version’s loop runs on unboxed values with nothing allocated per iteration. The lazy one accumulates a chain of thunks, and each one is a let you can see.

Point, with its strict fields, shows the other half: the unpacked representation means shift builds one heap object rather than one plus two boxed Ints.

Reading the source yourself

  1. GHC/Stg/Syntax.hs: small, and the closest thing to a description of GHC’s execution model in the compiler itself.
  2. GHC/CoreToStg/Prep.hs for the normalisation, which is where most of the fiddly cases live.
  3. GHC/Stg/Unarise.hs when you first meet an unboxed tuple in anger.
  4. The STG paper (Simon Peyton Jones, Implementing lazy functional languages on stock hardware) remains the best explanation of why the machine is shaped this way. docs/stg-spec/ in the tree has the formal version.

-ddump-stg-final shows the result. It is the single most useful dump for answering “why is this allocating?”, because in STG the allocations are exactly the lets.