ghc-7.0.2: The GHC API

CoreSyn

Contents

Description

CoreSyn holds all the main data types for use by for the Glasgow Haskell Compiler midsection

Synopsis

Main data types

data Expr b Source

This is the data type that represents GHCs core intermediate language. Currently GHC uses System FC http://research.microsoft.com/~simonpj/papers/ext-f/ for this purpose, which is closely related to the simpler and better known System F http://en.wikipedia.org/wiki/System_F.

We get from Haskell source to this Core language in a number of stages:

  1. The source code is parsed into an abstract syntax tree, which is represented by the data type HsExpr.HsExpr with the names being RdrName.RdrNames
  2. This syntax tree is renamed, which attaches a Unique.Unique to every RdrName.RdrName (yielding a Name) to disambiguate identifiers which are lexically identical. For example, this program: 
      f x = let f x = x + 1
            in f (x - 2)

Would be renamed by having Uniques attached so it looked something like this: 

      f_1 x_2 = let f_3 x_4 = x_4 + 1
                in f_3 (x_2 - 2)
  1. The resulting syntax tree undergoes type checking (which also deals with instantiating type class arguments) to yield a HsExpr.HsExpr type that has Id.Id as it's names.
  2. Finally the syntax tree is desugared from the expressive HsExpr.HsExpr type into this Expr type, which has far fewer constructors and hence is easier to perform optimization, analysis and code generation on.

The type parameter b is for the type of binders in the expression tree.

Constructors

Var Id

Variables

Lit Literal

Primitive literals

App (Expr b) (Arg b)

Applications: note that the argument may be a Type.

See CoreSyn for another invariant

Lam b (Expr b)

Lambda abstraction

Let (Bind b) (Expr b)

Recursive and non recursive lets. Operationally this corresponds to allocating a thunk for the things bound and then executing the sub-expression.

The right hand sides of all top-level and recursive lets must be of lifted type (see Type for the meaning of lifted vs. unlifted).

The right hand side of of a non-recursive Let _and_ the argument of an App, may be of unlifted type, but only if the expression is ok-for-speculation. This means that the let can be floated around without difficulty. For example, this is OK: 

 y::Int# = x +# 1#

But this is not, as it may affect termination if the expression is floated out: 

 y::Int# = fac 4#

In this situation you should use case rather than a let. The function CoreUtils.needsCaseBinding can help you determine which to generate, or alternatively use MkCore.mkCoreLet rather than this constructor directly, which will generate a case if necessary

We allow a non-recursive let to bind a type variable, thus: 

 Let (NonRec tv (Type ty)) body

This can be very convenient for postponing type substitutions until the next run of the simplifier.

At the moment, the rest of the compiler only deals with type-let in a Let expression, rather than at top level. We may want to revist this choice.

Case (Expr b) b Type [Alt b]

Case split. Operationally this corresponds to evaluating the scrutinee (expression examined) to weak head normal form and then examining at most one level of resulting constructor (i.e. you cannot do nested pattern matching directly with this).

The binder gets bound to the value of the scrutinee, and the Type must be that of all the case alternatives

This is one of the more complicated elements of the Core language, and comes with a number of restrictions:

The DEFAULT case alternative must be first in the list, if it occurs at all.

The remaining cases are in order of increasing tag (for DataAlts) or lit (for LitAlts). This makes finding the relevant constructor easy, and makes comparison easier too.

The list of alternatives must be exhaustive. An exhaustive case does not necessarily mention all constructors: 

      data Foo = Red | Green | Blue
 ... case x of 
      Red   -> True
      other -> f (case x of 
                      Green -> ...
                      Blue  -> ... ) ...

The inner case does not need a Red alternative, because x can't be Red at that program point.

Cast (Expr b) Coercion

Cast an expression to a particular type. This is used to implement newtypes (a newtype constructor or destructor just becomes a Cast in Core) and GADTs.

Note Note (Expr b)

Notes. These allow general information to be added to expressions in the syntax tree

Type Type

A type: this should only show up at the top level of an Arg

Instances

type Alt b = (AltCon, [b], Expr b)Source

A case split alternative. Consists of the constructor leading to the alternative, the variables bound from the constructor, and the expression to be executed given that binding. The default alternative is (DEFAULT, [], rhs)

data Bind b Source

Binding, used for top level bindings in a module and local bindings in a let.

Constructors

NonRec b (Expr b) 
Rec [(b, Expr b)] 

Instances

data AltCon Source

A case alternative constructor (i.e. pattern match)

Constructors

DataAlt DataCon

A plain data constructor: case e of { Foo x -> ... }. Invariant: the DataCon is always from a data type, and never from a newtype

LitAlt Literal

A literal: case e of { 1 -> ... }

DEFAULT

Trivial alternative: case e of { _ -> ... }

Instances

type Arg b = Expr bSource

Type synonym for expressions that occur in function argument positions. Only Arg should contain a Type at top level, general Expr should not

data Note Source

Allows attaching extra information to points in expressions rather than e.g. identifiers.

Constructors

SCC CostCentre

A cost centre annotation for profiling

CoreNote String

A generic core annotation, propagated but not used by GHC

Instances

type CoreExpr = Expr CoreBndrSource

Expressions where binders are CoreBndrs

type CoreAlt = Alt CoreBndrSource

Case alternatives where binders are CoreBndrs

type CoreBind = Bind CoreBndrSource

Binding groups where binders are CoreBndrs

type CoreArg = Arg CoreBndrSource

Argument expressions where binders are CoreBndrs

type CoreBndr = VarSource

The common case for the type of binders and variables when we are manipulating the Core language within GHC

type TaggedExpr t = Expr (TaggedBndr t)Source

type TaggedAlt t = Alt (TaggedBndr t)Source

type TaggedBind t = Bind (TaggedBndr t)Source

type TaggedArg t = Arg (TaggedBndr t)Source

data TaggedBndr t Source

Binders are tagged with a t

Constructors

TB CoreBndr t 

Instances

Expr construction

mkLets :: [Bind b] -> Expr b -> Expr bSource

Bind all supplied binding groups over an expression in a nested let expression. Prefer to use CoreUtils.mkCoreLets if possible

mkLams :: [b] -> Expr b -> Expr bSource

Bind all supplied binders over an expression in a nested lambda expression. Prefer to use CoreUtils.mkCoreLams if possible

mkApps :: Expr b -> [Arg b] -> Expr bSource

Apply a list of argument expressions to a function expression in a nested fashion. Prefer to use CoreUtils.mkCoreApps if possible

mkTyApps :: Expr b -> [Type] -> Expr bSource

Apply a list of type argument expressions to a function expression in a nested fashion

mkVarApps :: Expr b -> [Var] -> Expr bSource

Apply a list of type or value variables to a function expression in a nested fashion

mkIntLit :: Integer -> Expr bSource

Create a machine integer literal expression of type Int# from an Integer. If you want an expression of type Int use MkCore.mkIntExpr

mkIntLitInt :: Int -> Expr bSource

Create a machine integer literal expression of type Int# from an Int. If you want an expression of type Int use MkCore.mkIntExpr

mkWordLit :: Integer -> Expr bSource

Create a machine word literal expression of type Word# from an Integer. If you want an expression of type Word use MkCore.mkWordExpr

mkWordLitWord :: Word -> Expr bSource

Create a machine word literal expression of type Word# from a Word. If you want an expression of type Word use MkCore.mkWordExpr

mkCharLit :: Char -> Expr bSource

Create a machine character literal expression of type Char#. If you want an expression of type Char use MkCore.mkCharExpr

mkStringLit :: String -> Expr bSource

Create a machine string literal expression of type Addr#. If you want an expression of type String use MkCore.mkStringExpr

mkFloatLit :: Rational -> Expr bSource

Create a machine single precision literal expression of type Float# from a Rational. If you want an expression of type Float use MkCore.mkFloatExpr

mkFloatLitFloat :: Float -> Expr bSource

Create a machine single precision literal expression of type Float# from a Float. If you want an expression of type Float use MkCore.mkFloatExpr

mkDoubleLit :: Rational -> Expr bSource

Create a machine double precision literal expression of type Double# from a Rational. If you want an expression of type Double use MkCore.mkDoubleExpr

mkDoubleLitDouble :: Double -> Expr bSource

Create a machine double precision literal expression of type Double# from a Double. If you want an expression of type Double use MkCore.mkDoubleExpr

mkConApp :: DataCon -> [Arg b] -> Expr bSource

Apply a list of argument expressions to a data constructor in a nested fashion. Prefer to use MkCore.mkCoreConApps if possible

mkTyBind :: TyVar -> Type -> CoreBindSource

Create a binding group where a type variable is bound to a type. Per CoreSyn, this can only be used to bind something in a non-recursive let expression

varToCoreExpr :: CoreBndr -> Expr bSource

Convert a binder into either a Var or Type Expr appropriately

varsToCoreExprs :: [CoreBndr] -> [Expr b]Source

isTyCoVar :: Var -> BoolSource

isId :: Var -> BoolSource

cmpAltCon :: AltCon -> AltCon -> OrderingSource

Compares AltCons within a single list of alternatives

cmpAlt :: Alt b -> Alt b -> OrderingSource

ltAlt :: Alt b -> Alt b -> BoolSource

Simple Expr access functions and predicates

bindersOf :: Bind b -> [b]Source

Extract every variable by this group

bindersOfBinds :: [Bind b] -> [b]Source

bindersOf applied to a list of binding groups

rhssOfBind :: Bind b -> [Expr b]Source

rhssOfAlts :: [Alt b] -> [Expr b]Source

collectBinders :: Expr b -> ([b], Expr b)Source

We often want to strip off leading lambdas before getting down to business. This function is your friend.

collectTyBinders :: CoreExpr -> ([TyVar], CoreExpr)Source

Collect as many type bindings as possible from the front of a nested lambda

collectValBinders :: CoreExpr -> ([Id], CoreExpr)Source

Collect as many value bindings as possible from the front of a nested lambda

collectTyAndValBinders :: CoreExpr -> ([TyVar], [Id], CoreExpr)Source

Collect type binders from the front of the lambda first, then follow up by collecting as many value bindings as possible from the resulting stripped expression

collectArgs :: Expr b -> (Expr b, [Arg b])Source

Takes a nested application expression and returns the the function being applied and the arguments to which it is applied

coreExprCc :: Expr b -> CostCentreSource

Gets the cost centre enclosing an expression, if any. It looks inside lambdas because (scc "foo" \x.e) = \x. scc "foo" e

flattenBinds :: [Bind b] -> [(b, Expr b)]Source

Collapse all the bindings in the supplied groups into a single list of lhs/rhs pairs suitable for binding in a Rec binding group

isValArg :: Expr b -> BoolSource

Returns False iff the expression is a Type expression at its top level

isTypeArg :: Expr b -> BoolSource

Returns True iff the expression is a Type expression at its top level

valArgCount :: [Arg b] -> IntSource

The number of argument expressions that are values rather than types at their top level

valBndrCount :: [CoreBndr] -> IntSource

The number of binders that bind values rather than types

isRuntimeArg :: CoreExpr -> BoolSource

Will this argument expression exist at runtime?

isRuntimeVar :: Var -> BoolSource

Will this variable exist at runtime?

notSccNote :: Note -> BoolSource

Unfolding data types

data Unfolding Source

Records the unfolding of an identifier, which is approximately the form the identifier would have if we substituted its definition in for the identifier. This type should be treated as abstract everywhere except in CoreUnfold

Constructors

NoUnfolding

We have no information about the unfolding

OtherCon [AltCon]

It ain't one of these constructors. OtherCon xs also indicates that something has been evaluated and hence there's no point in re-evaluating it. OtherCon [] is used even for non-data-type values to indicated evaluated-ness. Notably: 

 data C = C !(Int -> Int)
 case x of { C f -> ... }

Here, f gets an OtherCon [] unfolding.

DFunUnfolding Arity DataCon [DFunArg CoreExpr] 
CoreUnfolding

An unfolding with redundant cached information. Parameters:

uf_tmpl: Template used to perform unfolding; NB: Occurrence info is guaranteed correct: see Note [OccInfo in unfoldings and rules]

uf_is_top: Is this a top level binding?

uf_is_value: exprIsHNF template (cached); it is ok to discard a seq on this variable

uf_is_cheap: Does this waste only a little work if we expand it inside an inlining? Basically this is a cached version of exprIsCheap

uf_guidance: Tells us about the size of the unfolding template

Fields

uf_tmpl :: CoreExpr
 
uf_src :: UnfoldingSource
 
uf_is_top :: Bool
 
uf_arity :: Arity
 
uf_is_value :: Bool
 
uf_is_conlike :: Bool
 
uf_is_cheap :: Bool
 
uf_expandable :: Bool
 
uf_guidance :: UnfoldingGuidance
 

Instances

data UnfoldingGuidance Source

UnfoldingGuidance says when unfolding should take place

Constructors

UnfWhen 

Fields

ug_unsat_ok :: Bool
 
ug_boring_ok :: Bool
 
UnfIfGoodArgs 

Fields

ug_args :: [Int]
 
ug_size :: Int
 
ug_res :: Int
 
UnfNever 

Instances

data UnfoldingSource Source

Constructors

InlineRhs 
InlineStable 
InlineCompulsory 
InlineWrapper Id 

Instances

data DFunArg e Source

Constructors

DFunPolyArg e 
DFunConstArg e 
DFunLamArg Int 

Instances

dfunArgExprs :: [DFunArg e] -> [e]Source

Constructing Unfoldings

noUnfolding :: UnfoldingSource

There is no known Unfolding

evaldUnfolding :: UnfoldingSource

This unfolding marks the associated thing as being evaluated

mkOtherCon :: [AltCon] -> UnfoldingSource

unSaturatedOk :: BoolSource

needSaturated :: BoolSource

boringCxtOk :: BoolSource

boringCxtNotOk :: BoolSource

Predicates and deconstruction on Unfolding

unfoldingTemplate :: Unfolding -> CoreExprSource

Retrieves the template of an unfolding: panics if none is known

setUnfoldingTemplate :: Unfolding -> CoreExpr -> UnfoldingSource

expandUnfolding_maybe :: Unfolding -> Maybe CoreExprSource

maybeUnfoldingTemplate :: Unfolding -> Maybe CoreExprSource

Retrieves the template of an unfolding if possible

otherCons :: Unfolding -> [AltCon]Source

The constructors that the unfolding could never be: returns [] if no information is available

unfoldingArity :: Unfolding -> AritySource

isValueUnfolding :: Unfolding -> BoolSource

Determines if it is certainly the case that the unfolding will yield a value (something in HNF): returns False if unsure

isEvaldUnfolding :: Unfolding -> BoolSource

Determines if it possibly the case that the unfolding will yield a value. Unlike isValueUnfolding it returns True for OtherCon

isCheapUnfolding :: Unfolding -> BoolSource

Is the thing we will unfold into certainly cheap?

isExpandableUnfolding :: Unfolding -> BoolSource

isConLikeUnfolding :: Unfolding -> BoolSource

True if the unfolding is a constructor application, the application of a CONLIKE function or OtherCon

isCompulsoryUnfolding :: Unfolding -> BoolSource

isStableUnfolding :: Unfolding -> BoolSource

isStableCoreUnfolding_maybe :: Unfolding -> Maybe UnfoldingSourceSource

isClosedUnfolding :: Unfolding -> BoolSource

hasSomeUnfolding :: Unfolding -> BoolSource

Only returns False if there is no unfolding information available at all

canUnfold :: Unfolding -> BoolSource

neverUnfoldGuidance :: UnfoldingGuidance -> BoolSource

isStableSource :: UnfoldingSource -> BoolSource

Strictness

seqExpr :: CoreExpr -> ()Source

seqExprs :: [CoreExpr] -> ()Source

seqUnfolding :: Unfolding -> ()Source

Annotated expression data types

type AnnExpr bndr annot = (annot, AnnExpr' bndr annot)Source

Annotated core: allows annotation at every node in the tree

data AnnExpr' bndr annot Source

A clone of the Expr type but allowing annotation at every tree node

Constructors

AnnVar Id 
AnnLit Literal 
AnnLam bndr (AnnExpr bndr annot) 
AnnApp (AnnExpr bndr annot) (AnnExpr bndr annot) 
AnnCase (AnnExpr bndr annot) bndr Type [AnnAlt bndr annot] 
AnnLet (AnnBind bndr annot) (AnnExpr bndr annot) 
AnnCast (AnnExpr bndr annot) Coercion 
AnnNote Note (AnnExpr bndr annot) 
AnnType Type 

data AnnBind bndr annot Source

A clone of the Bind type but allowing annotation at every tree node

Constructors

AnnNonRec bndr (AnnExpr bndr annot) 
AnnRec [(bndr, AnnExpr bndr annot)] 

type AnnAlt bndr annot = (AltCon, [bndr], AnnExpr bndr annot)Source

A clone of the Alt type but allowing annotation at every tree node

Operations on annotated expressions

collectAnnArgs :: AnnExpr b a -> (AnnExpr b a, [AnnExpr b a])Source

Takes a nested application expression and returns the the function being applied and the arguments to which it is applied

Operations on annotations

deAnnotate :: AnnExpr bndr annot -> Expr bndrSource

deAnnotate' :: AnnExpr' bndr annot -> Expr bndrSource

deAnnAlt :: AnnAlt bndr annot -> Alt bndrSource

collectAnnBndrs :: AnnExpr bndr annot -> ([bndr], AnnExpr bndr annot)Source

As collectBinders but for AnnExpr rather than Expr

Core rule data types

data CoreRule Source

A CoreRule is:

  • "Local" if the function it is a rule for is defined in the same module as the rule itself.
  • "Orphan" if nothing on the LHS is defined in the same module as the rule itself

Constructors

Rule 

Fields

ru_name :: RuleName

Name of the rule, for communication with the user

ru_act :: Activation

When the rule is active

ru_fn :: Name

Name of the Id.Id at the head of this rule

ru_rough :: [Maybe Name]

Name at the head of each argument to the left hand side

ru_bndrs :: [CoreBndr]

Variables quantified over

ru_args :: [CoreExpr]

Left hand side arguments

ru_rhs :: CoreExpr

Right hand side of the rule Occurrence info is guaranteed correct See Note [OccInfo in unfoldings and rules]

ru_auto :: Bool

True = this rule is auto-generated False = generated at the users behest Main effect: reporting of orphan-hood

ru_local :: Bool

True iff the fn at the head of the rule is defined in the same module as the rule and is not an implicit Id (like a record selector, class operation, or data constructor)

BuiltinRule

Built-in rules are used for constant folding and suchlike. They have no free variables.

Fields

ru_name :: RuleName

Name of the rule, for communication with the user

ru_fn :: Name

Name of the Id.Id at the head of this rule

ru_nargs :: Int

Number of arguments that ru_try consumes, if it fires, including type arguments

ru_try :: IdUnfoldingFun -> [CoreExpr] -> Maybe CoreExpr

This function does the rewrite. It given too many arguments, it simply discards them; the returned CoreExpr is just the rewrite of ru_fn applied to the first ru_nargs args

Instances

type RuleName = FastStringSource

type IdUnfoldingFun = Id -> UnfoldingSource

Operations on CoreRules

seqRules :: [CoreRule] -> ()Source

ruleArity :: CoreRule -> IntSource

The number of arguments the ru_fn must be applied to before the rule can match on it

ruleName :: CoreRule -> RuleNameSource

ruleIdName :: CoreRule -> NameSource

The Name of the Id.Id at the head of the rule left hand side

ruleActivation :: CoreRule -> ActivationSource

setRuleIdName :: Name -> CoreRule -> CoreRuleSource

Set the Name of the Id.Id at the head of the rule left hand side

isBuiltinRule :: CoreRule -> BoolSource

isLocalRule :: CoreRule -> BoolSource