Understanding GHC Core

| tagged with
  • ghc
  • core
  • work-in-progress

This document is a work-in-progress. If there is something that you would like to see discussed feel free to let me know.

While there have been a variety of writings about GHC’s Core representation, the language is a living entity which changes quickly in ways that aren’t always well documented. This

## What is Core?

GHC Core is a close relative of the System FC language and the first of a series of intermediate representations used by GHC to turn Haskell into machine code (the others being STG and C–).

While on face value Core appears very similar to Haskell, there are a few

Type application A transformation-based optimiser for Haskell

## Coercions

Core preserves newtypes as types unique from their representation (e.g. the type that they wrap). Wrapping and unwrapping of newtype values are represented by applications of the cast function. This essentially has the type,

data Coercion a b

cast :: a -> Coercion a b -> b

Coercions are GHC’s internal representation for type equalities1. On account of various

TODO ~R#

@~: type application of a coercion. For instance myFunction @~ (<a>_N :: a GHC.Prim.~# a) means that myFunction is being given a coercion argument <a>_N, a nominal coercion between a and a.

cast

Sym

Sub

<ty>_R is a type parameter with representational role. Roughly speaking this means that given a type constructor T and types A and B, T <A>_R and T <B>_R are representationally distinct. @~

## IdInfo

Attached to identifiers GHC will often keep metadata known as IdInfo to inform various optimization passes. This information can be found within brackets in Core’s textual representation. In the event that you just want to merely see the “shape” of a program IdInfo annotations are often noise that can be safely suppressed with -dsuppress-idinfo.

The information in IdInfo can be useful when examining the optimization with respect to specific passes. In this case it can be useful hto have a rough understanding of what these annotations mean. A brief summary of the IdInfo annotations used by GHC 7.10 is included below although these will likely change with future compiler versions.

annotation example meaning
Caf Caf=NoCafRefs The value is a a function or static constructor that refers to no CAFs defined in basicTypes/IdInfo.hs(CafInfo).
Arity Arity=1 An ArityInfo of \(n\) tells us that partial application of the value to up to \(n-1\) value arguments does essentially no work. defined in basicTypes/IdInfo.hs(ArityInfo)
GlbId GblId[[RecSel]] TODO
Unf Unf=Unf{...} The value has an associated unfolding template.
SpecInfo TODO Records the available specializations of the identifier defined in basicTypes/IdInfo.hs(SpecInfo).
OS OS=OneShot Records that the identifier will be used precisely once TODO
Str Str=DmdType <S(L...) The result of demand analysis. defined in basicTypes/Demand.hs(DmdType).
Occ Occ=Dead The result of occurrence analysis

### Unfolding templates

Unfolding (sometimes known as inlining) is one of the central optimizations performed by GHC’s Core optimizer. In this optimization, identifier occurrences are substituted by the right-hand side of their respective definition.

Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
        WorkFree=True, Expandable=True,
        Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=False)
        Tmpl= \ (ds_daj5 [Occ=Once!] :: Memcpy2Dargs) ->
                case ds_daj5
                of _ [Occ=Dead]
                { Memcpy2Dargs _ [Occ=Dead] ds2_daj7 [Occ=Once] _ [Occ=Dead]
                               _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                               _ [Occ=Dead] _ [Occ=Dead] ->
                ds2_daj7
                }}]

Src

### How are values used?

GHC uses a variety of local analyses to determine various ways function arguments are used (or unused). These analyses include,

  • strictness (or sometimes called demand) analysis: Is an argument forced (partially or completely) by a function?
  • absence analysis: Is an argument entirely unused by the function?
  • occurrence analysis:

When optimization is enabled GHC runs these analyses on all top-level bindings and records the results in the binding’s IdInfo. These results are then examined by later stages of compilation to help guide further optimizations (notably the worker-wrapper transformation).

In the external Core output, the results of demand analysis can be found in the Str= section of IdInfo,

foldl' :: forall a b. (b -> a -> b) -> b -> [a] -> b
[Str=DmdType <L,C(C1(U))><S,1*U><S,1*U>]
foldl' = ...

Here we see the IdInfo of the usual strict left fold on list. Here we see that GHC has associated with each argument a tuple enclosed in angle brackets. These tuples consist of the strictness and usage annotations of the argument. Let’s look at each,

argument type demand annotation
b -> a -> a <L,C(C1(U))>
b <S,1*U>
[a] <S,1*U>

We will discuss the meaning of these annotations in the following sections.

#### Demand analysis

Demand analysis (or strictness analysis) is an analysis which attempts to determine how the arguments of a function or binders of a let-block are used by its right-hand side. The result of the analysis is a demand signature. Note that demand signatures are computed for both let-bound and lambda-bound (argument) binders; however, for the sake of simplicity we will talk only about arguments below. Most everything applies equally to let-bound binders as well.

Note that demand analysis is necessarily conservative; GHC can not conclude that a value is forced unless all possible code-paths force it. Afterall, we may otherwise perform unnecessary work or, even worse, force a bottoming expression.

Demand signatures consist of two parts:

  • a strictness signature denoting how much of the value is forced

  • an absence (or usage) signature denoting how many times the value might be used

In GHC Core syntax demand signatures are rendered inside angle brackets (e.g. <...>) and separated by a comma, e.g.,

<strictness1, usage1> <strictness2, usage2> ... <strictnessN, usageN> suffixes

where there is one signature pair per argument. The strictness and absence signatures themselves are rendered in abbreviated form,

signature description
strictness
L lazy. As far as the analysis could tell, the argument isn’t demanded
S head-strict. The analysis determined that the argument will be evaluated at least to head-normal form.
S(...) strict product demand. The argument (which must be a product) will itself be evaluated to at least head-normal form and each of its fields will be evaluated to at least the strictnesses given in parentheses.
C strict call. The binder (which must be a function) is applied to arguments and the result is forced.
B hyper-strict. All codepaths which force the argument will eventually diverge.
x... handles exceptions. This isn’t a demand itself, but rather modifies a strict demand, denoting that while the argument is forced, its divergence does not imply that the function will diverge (e.g. the function may catch exceptions thrown during evaluation of the argument).
absence
U used. The binder is used
C used as function. The argument is
S(...) product usage. The argument (which must be a product) and some portion of its fields are used.
A absent == definitely unused. Indicates that the binder is certainly not used.
1*... used once. Not a usage but rather modifies a “used” demand denoting that the argument is used precisely once.

In addition, following the argument signatures there may also be a variety of miscellaneous flags that describe the result of the functionm,

signature description
m returns a constructed product result.
b bottoming. The result of the function (when saturated) is known to be bottom.

Let’s consider a few examples (including several stolen from the paper),

-- Demand signature: <S,1*U>
null :: [a] -> Bool
null v = case v of []   -> True
                   x:xs -> False

The S (strict) strictness here arises from the case-analysis, which implies that if we evaluate null v then v must be evaluated to at least WHNF. The 1*U usage signature means that the binder occurs in exactly one context (namely as the scrutinee of the case).

Now let’s look at a slightly tricker example,

-- Demand signature: <S(SL),1*U(1*U,A)>
fst :: (a,b) -> a
fst p = case p of (x,_) -> x

Here we see that the strictness signature of p is S(SL), meaning that the (,) constructor will be forced to WHNF, as will its first field. The usage signature suggests that, as one would expect, p and its first field are used precisely once. The second field of p has a lazy (L) strictness and absent (A) usage, as it is nowhere mentioned in fst’s right-hand side.

-- Demand signature: <S,1*U(U,U)>m
swap :: (a,b) -> (b,a)
swap p = case p of (x,y) -> (y,x)

Here we see that p is evaluated to WHNF, however neither of the fields will be further forced despite the fact that they are both mentioned. Additionally, we see that swap returns a [constructed product result](???).

-- Demand signature: <S,1*U(U)><L,A>m
f :: Int -> Int -> Int
f x y = case x of 
          I# x# -> I# (x# +# 1#)

This is another simple case: the first argument, x, has a demand of <S,1*U(U)>, owing to the fact that it is scrutinized by the case.

Now let’s look at a combinator involving a higher-order function,

-- Demand signature: <L,C(C1(U))><L,U><S,1*U>
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f y xs =
    case xs of
      []    -> y
      x:xs' -> foldl' f (f y x) xs'

The first thing to notice here is the lazy strictness on f; this is due to the conservative nature of strictness analysis. Afterall, evaluating foldl' f to an empty list will never force f. However, we nevertheless see that f’s usage signature reflects that it is called with two arguments: .

Exceptions tend to make

#### Absence analysis

Consider the function,

f :: (Int, Int) -> Int
f (a,_) = a + 42

The strictness analysis discussed above allows us to determine that the first element of the tuple argument is demanded strictly. This observation allows to perform the [worker-wrapper transformation][worker-wrapper] on f, resulting in,

f_workerer

However, what of the second element?

It is quite obvious that the second element is not called for at all

## Trick: Locating Outputable instances As GHC Core is an internal representation there is a tendency for documentation to fall behind what GHC actually emits. For this reason, it can be useful to quickly find the Outputable instance defintion from which a given piece of output originated. ghci is quite handy for this purpose,

$ ghci
GHCi, version 7.10.2.20151118: http://www.haskell.org/ghc/  :? for help
λ> :set -package ghc
package flags have changed, resetting and loading new packages...
λ> import GHC
λ> import Outputable
λ> :info Outputable
class Outputable a where
  ppr :: a -> SDoc
  pprPrec :: Rational -> a -> SDoc
    -- Defined in ‘Outputable’
instance Outputable BreakInfo -- Defined in ‘ByteCodeInstr’
instance Outputable Type -- Defined in ‘TypeRep’
instance Outputable TyThing -- Defined in ‘TypeRep’
instance Outputable TyCon -- Defined in ‘TyCon’
instance Outputable ClsInst -- Defined in ‘InstEnv’

## Optimizations ### Float-out ### Float-in ### Float-

In brackets: IdInfo

Role annotations

# A language deeper: STG

STG is a Haskell-like language which Core is lowered to. While it doesn’t technically fit in this article, I’ve plopped it here regardless.

let-no-escape closure update flags * \r: re-entrant: may be entered multiple times and therefore shouldn’t be updated or black-hole’d * \s: single-entry: will be entered at most once and therefore needn’t be updated * \u: updatable: should be updated after evaluation (and may be blackhole’d during evaluation) sat-only: Marks a closure that will only be used in fully-saturated applications.

## Glossary

binding

the introduction of a name for a value. For instance, let hello = 5 in ... is a binding.

binder

the name of a binding. For instance, in let hello = 5 in ... hello is the binder

MFE (Maximal Free Expression)

A maximal free expression (or MFE) of a lambda abstraction is an expression which contains no occurrences of the variable bound by the abstraction, and is not a sub-expression of a larger expression with this property.

For instance, of the expression, \x -> (4 * 3) + x, (4 * 3) is an MFE as it contains no references to x.


  1. GHC’s Core language is known in the literature as System FC, owing to the fact that it is closely related to System F. In fact, the “C” in “FC” stands for “coercion”, indicative of the fact that System FC is simply System F with coercions.