| ... |
... |
@@ -179,99 +179,166 @@ These data types are the heart of the compiler |
|
179
|
179
|
-- optimization, analysis and code generation on.
|
|
180
|
180
|
--
|
|
181
|
181
|
-- The type parameter @b@ is for the type of binders in the expression tree.
|
|
182
|
|
---
|
|
183
|
|
--- The language consists of the following elements:
|
|
184
|
|
---
|
|
185
|
|
--- * Variables
|
|
186
|
|
--- See Note [Variable occurrences in Core]
|
|
187
|
|
---
|
|
188
|
|
--- * Primitive literals
|
|
189
|
|
---
|
|
190
|
|
--- * Applications: note that the argument may be a 'Type'.
|
|
191
|
|
--- See Note [Representation polymorphism invariants]
|
|
192
|
|
---
|
|
193
|
|
--- * Lambda abstraction
|
|
194
|
|
--- See Note [Representation polymorphism invariants]
|
|
195
|
|
---
|
|
196
|
|
--- * Recursive and non recursive @let@s. Operationally
|
|
197
|
|
--- this corresponds to allocating a thunk for the things
|
|
198
|
|
--- bound and then executing the sub-expression.
|
|
199
|
|
---
|
|
200
|
|
--- See Note [Core letrec invariant]
|
|
201
|
|
--- See Note [Core let-can-float invariant]
|
|
202
|
|
--- See Note [Representation polymorphism invariants]
|
|
203
|
|
--- See Note [Core type and coercion invariant]
|
|
204
|
|
---
|
|
205
|
|
--- * Case expression. Operationally this corresponds to evaluating
|
|
206
|
|
--- the scrutinee (expression examined) to weak head normal form
|
|
207
|
|
--- and then examining at most one level of resulting constructor (i.e. you
|
|
208
|
|
--- cannot do nested pattern matching directly with this).
|
|
209
|
|
---
|
|
210
|
|
--- The binder gets bound to the value of the scrutinee,
|
|
211
|
|
--- and the 'Type' must be that of all the case alternatives
|
|
212
|
|
---
|
|
213
|
|
--- IMPORTANT: see Note [Case expression invariants]
|
|
214
|
|
---
|
|
215
|
|
--- * Cast an expression to a particular type.
|
|
216
|
|
--- This is used to implement @newtype@s (a @newtype@ constructor or
|
|
217
|
|
--- destructor just becomes a 'Cast' in Core) and GADTs.
|
|
218
|
|
---
|
|
219
|
|
--- * Ticks. These are used to represent all the source annotation we
|
|
220
|
|
--- support: profiling SCCs, HPC ticks, and GHCi breakpoints.
|
|
221
|
|
---
|
|
222
|
|
--- * A type: this should only show up at the top level of an Arg
|
|
223
|
|
---
|
|
224
|
|
--- * A coercion
|
|
225
|
|
-
|
|
226
|
|
-{- Note [Why does Case have a 'Type' field?]
|
|
227
|
|
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
228
|
|
-The obvious alternative is
|
|
229
|
|
- exprType (Case scrut bndr alts)
|
|
230
|
|
- | (_,_,rhs1):_ <- alts
|
|
231
|
|
- = exprType rhs1
|
|
232
|
|
-
|
|
233
|
|
-But caching the type in the Case constructor
|
|
234
|
|
- exprType (Case scrut bndr ty alts) = ty
|
|
235
|
|
-is better for at least three reasons:
|
|
236
|
|
-
|
|
237
|
|
-* It works when there are no alternatives (see case invariant 1 above)
|
|
238
|
|
-
|
|
239
|
|
-* It might be faster in deeply-nested situations.
|
|
240
|
|
-
|
|
241
|
|
-* It might not be quite the same as (exprType rhs) for one
|
|
242
|
|
- of the RHSs in alts. Consider a phantom type synonym
|
|
243
|
|
- type S a = Int
|
|
244
|
|
- and we want to form the case expression
|
|
245
|
|
- case x of { K (a::*) -> (e :: S a) }
|
|
246
|
|
- Then exprType of the RHS is (S a), but we cannot make that be
|
|
247
|
|
- the 'ty' in the Case constructor because 'a' is simply not in
|
|
248
|
|
- scope there. Instead we must expand the synonym to Int before
|
|
249
|
|
- putting it in the Case constructor. See GHC.Core.Utils.mkSingleAltCase.
|
|
250
|
|
-
|
|
251
|
|
- So we'd have to do synonym expansion in exprType which would
|
|
252
|
|
- be inefficient.
|
|
253
|
|
-
|
|
254
|
|
-* The type stored in the case is checked with lintInTy. This checks
|
|
255
|
|
- (among other things) that it does not mention any variables that are
|
|
256
|
|
- not in scope. If we did not have the type there, it would be a bit
|
|
257
|
|
- harder for Core Lint to reject case blah of Ex x -> x where
|
|
258
|
|
- data Ex = forall a. Ex a.
|
|
259
|
|
--}
|
|
|
182
|
+-- It is usually instantiated to 'Var' (in 'CoreExpr', the commonly used type
|
|
|
183
|
+-- alias). To see why @b@ is useful, see 'TaggedExpr' and its use in
|
|
|
184
|
+-- "GHC.Core.Opt.SetLevels".
|
|
260
|
185
|
|
|
261
|
186
|
-- If you edit this type, you may need to update the GHC formalism
|
|
262
|
187
|
-- See Note [GHC Formalism] in GHC.Core.Lint
|
|
263
|
188
|
data Expr b
|
|
264
|
189
|
= Var Id
|
|
|
190
|
+ -- ^ A (term-level, hence 'Id') variable occurrence,
|
|
|
191
|
+ -- see Note [Variable occurrences in Core].
|
|
|
192
|
+ --
|
|
|
193
|
+ -- Refers to the 'Id' record of its binding site;
|
|
|
194
|
+ -- if you change its 'GHC.Types.Id.idInfo' you probably want to change the
|
|
|
195
|
+ -- 'GHC.Types.Id.idInfo' of the binding site as well.
|
|
|
196
|
+
|
|
265
|
197
|
| Lit Literal
|
|
|
198
|
+ -- ^ A primitive literal. It has an unlifted type, except for 'LitRubbish',
|
|
|
199
|
+ -- which may have a lifted type; see Note [Rubbish literals] in GHC.Types.Literal.
|
|
|
200
|
+ --
|
|
|
201
|
+ -- Haskell's number literals such as @0 :: Int@ (where @Int@ is a lifted data type)
|
|
|
202
|
+ -- do /not/ have a representation as a Core 'Literal'; rather they get desugared
|
|
|
203
|
+ -- to @I# 0#@, where @0#@ is a Literal of type @Int#@ (which has unlifted kind
|
|
|
204
|
+ -- @TYPE IntRep@).
|
|
|
205
|
+ --
|
|
|
206
|
+ -- There are a few utility functions to create literals, for example
|
|
|
207
|
+ -- 'mkIntLit', 'mkDoubleLit', 'mkCharLit', 'mkStringLit'.
|
|
|
208
|
+
|
|
266
|
209
|
| App (Expr b) (Arg b)
|
|
|
210
|
+ -- ^ A unary application, often occurring in left-associated chains.
|
|
|
211
|
+ --
|
|
|
212
|
+ -- There are a few utility functions working on application chains;
|
|
|
213
|
+ -- see 'collectArgs' and friends.
|
|
|
214
|
+ --
|
|
|
215
|
+ -- Args have fixed runtime representation;
|
|
|
216
|
+ -- see Note [Representation polymorphism invariants].
|
|
|
217
|
+
|
|
267
|
218
|
| Lam b (Expr b)
|
|
|
219
|
+ -- ^ A lambda, binding term arguments ('Id'), type or kind arguments ('TyVar')
|
|
|
220
|
+ -- or coercion arguments ('CoVar').
|
|
|
221
|
+ --
|
|
|
222
|
+ -- Note that type and coercion binders are dependently quantified. E.g., in
|
|
|
223
|
+ -- pretty-printed Core,
|
|
|
224
|
+ --
|
|
|
225
|
+ -- > f = \(@a) (@co :: a ~# Int) -> <expr> :: (<ty> a |> (... co))
|
|
|
226
|
+ --
|
|
|
227
|
+ -- Where you can pick out dependent quantifiers by the leading @\@@.
|
|
|
228
|
+ -- Here, @a@ occurs in the kind of @co@ (the next lambda binder) and in the
|
|
|
229
|
+ -- type of @<expr>@, so both the kind of @co@ /and/ the type of @<expr>@
|
|
|
230
|
+ -- depend on @a@. Furthermore, the type of @<expr>@ is cast via a
|
|
|
231
|
+ -- coercion mentioning @co@.
|
|
|
232
|
+ --
|
|
|
233
|
+ -- Subject to Note [Shadowing in Core] for the lambda binder.
|
|
|
234
|
+ -- Lambda binders have fixed runtime representation;
|
|
|
235
|
+ -- see Note [Representation polymorphism invariants].
|
|
|
236
|
+ --
|
|
|
237
|
+ -- Use 'mkLams' to create multiple lambdas at once and 'wrapLamBody' to
|
|
|
238
|
+ -- map over the body of a lambda without touching its binders (beware of
|
|
|
239
|
+ -- name capture!).
|
|
|
240
|
+
|
|
268
|
241
|
| Let (Bind b) (Expr b)
|
|
269
|
|
- | Case (Expr b) b Type [Alt b] -- See Note [Case expression invariants]
|
|
270
|
|
- -- and Note [Why does Case have a 'Type' field?]
|
|
271
|
|
- | Cast (Expr b) CoercionR -- The Coercion has Representational role
|
|
|
242
|
+ -- ^ A let binding. 'Bind' is either a single, 'NonRec'ursive binding or a
|
|
|
243
|
+ -- list of mutually 'Rec'ursive bindings.
|
|
|
244
|
+ -- Operationally, this corresponds to allocating a thunk for the things bound
|
|
|
245
|
+ -- and then executing the sub-expression.
|
|
|
246
|
+ --
|
|
|
247
|
+ -- Almost exclusively used for value bindings, e.g., 'Id's, in which case be
|
|
|
248
|
+ -- aware of the following invariants:
|
|
|
249
|
+ --
|
|
|
250
|
+ -- * Note [Core letrec invariant]
|
|
|
251
|
+ -- * Note [Core let-can-float invariant]
|
|
|
252
|
+ -- * Note [Shadowing in Core] of the let binders
|
|
|
253
|
+ -- * Let binders have fixed runtime representation;
|
|
|
254
|
+ -- see Note [Representation polymorphism invariants].
|
|
|
255
|
+ --
|
|
|
256
|
+ -- A very special kind of let binding is a /join point/, which can be detected
|
|
|
257
|
+ -- with 'GHC.Types.Id.isJoinId' (or 'GHC.Types.Id.idJoinPointHood') or
|
|
|
258
|
+ -- 'GHC.Core.Utils.isJoinBind'.
|
|
|
259
|
+ -- Consult Note [Join points] for details.
|
|
|
260
|
+ --
|
|
|
261
|
+ -- In exception to \"exclusively\" above, we may bind a 'TyVar' or a 'CoVar'
|
|
|
262
|
+ -- in a non-recursive 'Bind', see Note [Core type and coercion invariant].
|
|
|
263
|
+ --
|
|
|
264
|
+ -- See also utility functions 'mkLet', 'mkLets', 'mkLetNonRec', 'mkLetRec'.
|
|
|
265
|
+
|
|
|
266
|
+ | Case (Expr b) b Type [Alt b]
|
|
|
267
|
+ -- ^ Represents a Case expression, doing one level of pattern-matching.
|
|
|
268
|
+ -- Pretty-printed as
|
|
|
269
|
+ --
|
|
|
270
|
+ -- > case scrut of wild {
|
|
|
271
|
+ -- > __DEFAULT -> rhs1;
|
|
|
272
|
+ -- > (:) x xs -> rhs2;
|
|
|
273
|
+ -- > }
|
|
|
274
|
+ --
|
|
|
275
|
+ -- Operationally, the /scrutinee/ expression @scrut@ is evaluated to weak
|
|
|
276
|
+ -- head normal form. The value is bound to the /case binder/ @wild@ and is then
|
|
|
277
|
+ -- examined to do a one-level switch on the data constructor tag/literal to
|
|
|
278
|
+ -- jump to one of the /alternatives/. (Nested matches in Haskell have been
|
|
|
279
|
+ -- desugared to multiple Case matches in Core.)
|
|
|
280
|
+ --
|
|
|
281
|
+ -- The type is the cached return type of the whole case
|
|
|
282
|
+ -- expression and hence matches that of the case alternatives,
|
|
|
283
|
+ -- see Note [Why does Case have a 'Type' field?].
|
|
|
284
|
+ -- The list of case alternatives is roughly represented as
|
|
|
285
|
+ --
|
|
|
286
|
+ -- > [ Alt DEFAULT [] rhs1, Alt (DataAlt (:)) [x, xs] rhs2 ]
|
|
|
287
|
+ --
|
|
|
288
|
+ -- Note that there is at most one catch-all @__DEFAULT@ case and no overlap
|
|
|
289
|
+ -- between other alternatives, so there is /no/ first-match semantics. The
|
|
|
290
|
+ -- list is nevertheless kept in a canonical order (@__DEFAULT@ first, then
|
|
|
291
|
+ -- sorted); see Note [Case expression invariants].
|
|
|
292
|
+ --
|
|
|
293
|
+ -- See also
|
|
|
294
|
+ --
|
|
|
295
|
+ -- * Note [Case expression invariants]
|
|
|
296
|
+ -- * Note [Empty case alternatives]
|
|
|
297
|
+ -- * Note [Shadowing in Core] of the case binder
|
|
|
298
|
+ -- * Case binders have fixed runtime representation;
|
|
|
299
|
+ -- see Note [Representation polymorphism invariants].
|
|
|
300
|
+ --
|
|
|
301
|
+ -- Utility functions: 'GHC.Core.Utils.mkAltExpr',
|
|
|
302
|
+ -- 'GHC.Core.Utils.mkDefaultCase', 'GHC.Core.Utils.mkSingleAltCase' and the
|
|
|
303
|
+ -- various helper functions around case alternatives in "GHC.Core.Utils".
|
|
|
304
|
+
|
|
|
305
|
+ | Cast (Expr b) CoercionR
|
|
|
306
|
+ -- ^ Cast an expression's type via a 'CoercionR' (the R denotes that it has a
|
|
|
307
|
+ -- Representational role). Doing so has no effect at runtime, but it is
|
|
|
308
|
+ -- crucial for justifying term-level transformations in the type system.
|
|
|
309
|
+ --
|
|
|
310
|
+ -- This is used to implement @newtype@s (a @newtype@ constructor or
|
|
|
311
|
+ -- destructor just becomes a 'Cast' in Core) and GADTs.
|
|
|
312
|
+
|
|
272
|
313
|
| Tick CoreTickish (Expr b)
|
|
|
314
|
+ -- ^ Wraps various sorts of debug information around an expression, such as
|
|
|
315
|
+ -- profiling SCCs, HPC ticks, and GHCi breakpoints.
|
|
|
316
|
+ --
|
|
|
317
|
+ -- We try to preserve meaning throughout transformations as best as possible.
|
|
|
318
|
+ --
|
|
|
319
|
+ -- There are quite a few utility functions that work on 'Ticks':
|
|
|
320
|
+ -- 'collectArgsTicks', 'GHC.Core.Utils.stripTicksTop' and friends in
|
|
|
321
|
+ -- "GHC.Core.Utils".
|
|
|
322
|
+
|
|
273
|
323
|
| Type Type
|
|
|
324
|
+ -- ^ Signals leaving of the \"term level\" and injects a type expression.
|
|
|
325
|
+ --
|
|
|
326
|
+ -- Occurs only in argument position of an 'App' such as @id \@Int (I# 42#)@
|
|
|
327
|
+ -- (where there is a non-pretty-printed @Type ...@ wrapped around the type
|
|
|
328
|
+ -- expression @Int@) or (rarely) in the RHS of a 'Let' that binds a type
|
|
|
329
|
+ -- variable, such as @let { a = \@(Rep MyBigGenericRecord) } in ...@
|
|
|
330
|
+ -- as in Note [Core type and coercion invariant].
|
|
|
331
|
+ --
|
|
|
332
|
+ -- If you want to turn a 'Var' into an argument and don't know whether it's a
|
|
|
333
|
+ -- term-level 'Id', a type-level 'TyVar' or a 'CoVar', use 'varToCoreExpr'.
|
|
|
334
|
+
|
|
274
|
335
|
| Coercion Coercion
|
|
|
336
|
+ -- ^ Quite the same as the 'Type' constructor, but for introducing coercion
|
|
|
337
|
+ -- arguments (which encode equalities between types).
|
|
|
338
|
+ --
|
|
|
339
|
+ -- Coercion arguments are morally values and should be treated as such (e.g.,
|
|
|
340
|
+ -- somewhat close to tokens of type @()@) until they are erased in STG.
|
|
|
341
|
+
|
|
275
|
342
|
deriving Data
|
|
276
|
343
|
|
|
277
|
344
|
-- | Type synonym for expressions that occur in function argument positions.
|
| ... |
... |
@@ -783,6 +850,40 @@ checked by Core Lint. |
|
783
|
850
|
multiplicity of the corresponding field /scaled by the multiplicity of the
|
|
784
|
851
|
case binder/. Checked in lintCoreAlt.
|
|
785
|
852
|
|
|
|
853
|
+Note [Why does Case have a 'Type' field?]
|
|
|
854
|
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
|
855
|
+The obvious alternative is
|
|
|
856
|
+ exprType (Case scrut bndr alts)
|
|
|
857
|
+ | (_,_,rhs1):_ <- alts
|
|
|
858
|
+ = exprType rhs1
|
|
|
859
|
+
|
|
|
860
|
+But caching the type in the Case constructor
|
|
|
861
|
+ exprType (Case scrut bndr ty alts) = ty
|
|
|
862
|
+is better for at least three reasons:
|
|
|
863
|
+
|
|
|
864
|
+* It works when there are no alternatives (see case invariant 1 above)
|
|
|
865
|
+
|
|
|
866
|
+* It might be faster in deeply-nested situations.
|
|
|
867
|
+
|
|
|
868
|
+* It might not be quite the same as (exprType rhs) for one
|
|
|
869
|
+ of the RHSs in alts. Consider a phantom type synonym
|
|
|
870
|
+ type S a = Int
|
|
|
871
|
+ and we want to form the case expression
|
|
|
872
|
+ case x of { K (a::*) -> (e :: S a) }
|
|
|
873
|
+ Then exprType of the RHS is (S a), but we cannot make that be
|
|
|
874
|
+ the 'ty' in the Case constructor because 'a' is simply not in
|
|
|
875
|
+ scope there. Instead we must expand the synonym to Int before
|
|
|
876
|
+ putting it in the Case constructor. See GHC.Core.Utils.mkSingleAltCase.
|
|
|
877
|
+
|
|
|
878
|
+ So we'd have to do synonym expansion in exprType which would
|
|
|
879
|
+ be inefficient.
|
|
|
880
|
+
|
|
|
881
|
+* The type stored in the case is checked with lintInTy. This checks
|
|
|
882
|
+ (among other things) that it does not mention any variables that are
|
|
|
883
|
+ not in scope. If we did not have the type there, it would be a bit
|
|
|
884
|
+ harder for Core Lint to reject case blah of Ex x -> x where
|
|
|
885
|
+ data Ex = forall a. Ex a.
|
|
|
886
|
+
|
|
786
|
887
|
Note [Core type and coercion invariant]
|
|
787
|
888
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
788
|
889
|
We allow a /non-recursive/, /non-top-level/ let to bind type and
|