GHC Handbook

Chapter 8

The simplifier

The densest part of GHC: 450 Notes of inlining, case-of-case, strictness and rewrite rules, run to a fixed point. Where three list traversals become one loop that allocates nothing.

Where this lives in the tree

GHC.Core.Opt.* holds 450 Notes: more than any other part of the compiler, more than the entire back end. This is where GHC’s reputation was earned, and it is also where the compiler is least like a textbook.

The middle end is not one pass. It is a sequence, configured by optimisation level, in which the simplifier runs several times with analyses interleaved between its runs. Each analysis annotates the program; the simplifier exploits the annotations; the result enables the next analysis.

The simplifier

At its heart is a set of local rewrites applied everywhere, repeatedly, until nothing changes: beta reduction, let floating, inlining, case-of-known-constructor, dead code elimination.

The most consequential is case-of-case. Given

case (case x of { A -> e1; B -> e2 }) of { ... alts ... }

the outer case can be pushed into both branches of the inner one, duplicating alts. This looks like it makes the program bigger, and sometimes it does. But it is what makes short-circuiting boolean operators, && chains, and fused pipelines compile to straight-line tests instead of building and immediately scrutinising intermediate values.

Deciding when to inline is the hardest judgement in the compiler. Inline too little and nothing else fires; inline too much and code size explodes, and because inlining enables further inlining, the feedback is nonlinear. GHC’s answer is a mass of heuristics informed by occurrence analysis: a binder used exactly once in a non-recursive position is nearly always worth inlining, because it cannot duplicate work.

Occurrence analysis

OccurAnal runs before each simplifier pass and answers how each binder is used: once, many times, under a lambda, in a tail position. That last one is how join points are found: a let-bound function only ever tail-called becomes a label rather than a closure.

It also breaks recursive groups into strongly-connected components and picks loop breakers, without which the simplifier would inline a recursive function into itself forever.

Strictness, and unboxing

Demand analysis asks: if this function is called, will it definitely evaluate this argument? A yes is licence to do something valuable: pass the argument evaluated and unboxed, rather than as a thunk.

Worker/wrapper is the transformation that cashes it in. A function f becomes a small wrapper with the original type that unpacks its arguments, plus a worker taking unboxed values. The wrapper is inlined at every call site, so the boxing usually disappears entirely.

Note [Worker/wrapper for INLINABLE functions] GHC/Core/Opt/WorkWrap.hs:182 
If we have
  {-# INLINABLE f #

This is why a strict accumulator loop over Int in Haskell can run with no allocation at all: after worker/wrapper the accumulator is an Int# in a register, and the I# box never exists.

Rewrite rules and fusion

RULES pragmas let library authors state equations that GHC applies as left-to-right rewrites. This is how fusion works, and it lives in libraries rather than in the compiler.

The canonical example is map f (map g xs) = map (f . g) xs. Modern base uses a more general scheme built on build/foldr, but the principle is the same: the library says which rewrites are valid, and the simplifier applies them.

Specialisation is the same idea applied to dictionaries. A polymorphic function called at a known type can be cloned with the dictionary inlined, turning indirect calls into direct ones:

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
    $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:
Show the rest of this Note (76 more lines) 
(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].

Seeing it happen

This is what the Fusion.hs example exists for.

What you wrote.

-- | What the optimiser is actually for.
--
-- `pipeline` reads as three traversals building two intermediate lists. Compare
-- the desugared Core with the optimised Core: rewrite rules and the simplifier
-- fuse the whole thing into a single loop that allocates no list at all.
module Fusion where

pipeline :: [Int] -> Int
pipeline = sum . map (* 2) . filter even

countdown :: Int -> Int
countdown n = go n 0
  where
    go 0 acc = acc
    go k acc = go (k - 1) (acc + k)
`pipeline = sum . map (*2) . filter even` reads as three traversals building two intermediate lists. Compare desugared with optimised Core.

In Core (desugared) you can see the composition and the intermediate lists. In Core (optimised) they are gone: fusion has collapsed the pipeline into a single recursive worker over the input list, with no intermediate list allocated.

Worker/wrapper has a demonstration of its own:

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
`sumStrict` and `sumLazy` are the same fold, one with a bang pattern. Compare what the optimiser does to each.

In Core (optimised), sumStrict’s inner loop has become:

$wgo1 :: Int# -> [Int] -> Int#
$wgo1
  = \ (ww :: Int#) (ds :: [Int]) ->
      case ds of {
        [] -> ww;
        : x xs -> case x of { I# y -> $wgo1 (+# ww y) xs }
      }

The accumulator is an unboxed Int#, the addition is the primop +#, and no I# box is ever allocated for it. That is demand analysis proving the accumulator is forced, and worker/wrapper cashing the proof in.

sumLazy is the same source without the bang, and the difference in what the optimiser can do is the point of the example.

Reading the source yourself

The middle end is large enough that reading it front to back is not a plan. Pick a transformation and follow it.

  1. GHC/Core/Opt/OccurAnal.hs first, despite being an analysis rather than a transformation. Nearly every simplifier decision consults its output.
  2. GHC/Core/Opt/Simplify/Iteration.hs for the rewrites themselves.
  3. GHC/Core/Opt/DmdAnal.hs and WorkWrap.hs as a pair: the analysis is only interesting because of what the transformation does with it.
  4. GHC/Core/Opt/Pipeline.hs to see the order everything runs in, which explains a lot about why a given optimisation did or did not fire.

-ddump-simpl-iterations shows the program after each pass, and -ddump-rule-firings names every rule that fired. When an expected optimisation does not happen, those two flags usually explain it faster than reading the code. Both are pre-run on a minimal fusion pipeline in the trace explorer: watch fold/build fire, pass by pass.