Understanding GHC Core

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 its face Core appears to be very similar to Haskell, there are a few important differences:

• type applications are always explicit

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 equalities¹. 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.

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,

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,

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

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.