2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
4 \section[CoreSyn]{A data type for the Haskell compiler midsection}
7 #include "HsVersions.h"
10 GenCoreBinding(..), GenCoreExpr(..),
11 GenCoreArg(..), GenCoreBinder(..), GenCoreCaseAlts(..),
12 GenCoreCaseDefault(..),
15 bindersOf, pairsFromCoreBinds, rhssOfBind,
17 mkGenApp, mkValApp, mkTyApp, mkUseApp,
19 mkValLam, mkTyLam, mkUseLam,
21 collectBinders, isValBinder, notValBinder,
23 collectArgs, isValArg, notValArg, numValArgs,
25 mkCoLetAny, mkCoLetNoUnboxed, mkCoLetUnboxedToCase,
26 mkCoLetsAny, mkCoLetsNoUnboxed, mkCoLetsUnboxedToCase,
27 mkCoLetrecAny, mkCoLetrecNoUnboxed,
31 -- Common type instantiation...
37 SYN_IE(CoreCaseDefault),
39 -- And not-so-common type instantiations...
40 SYN_IE(TaggedCoreBinding),
41 SYN_IE(TaggedCoreExpr),
42 SYN_IE(TaggedCoreBinder),
43 SYN_IE(TaggedCoreArg),
44 SYN_IE(TaggedCoreCaseAlts),
45 SYN_IE(TaggedCoreCaseDefault),
47 SYN_IE(SimplifiableCoreBinding),
48 SYN_IE(SimplifiableCoreExpr),
49 SYN_IE(SimplifiableCoreBinder),
50 SYN_IE(SimplifiableCoreArg),
51 SYN_IE(SimplifiableCoreCaseAlts),
52 SYN_IE(SimplifiableCoreCaseDefault)
57 import CostCentre ( showCostCentre, CostCentre )
58 import Id ( idType, GenId{-instance Eq-} )
59 import Type ( isUnboxedType )
60 import Usage ( SYN_IE(UVar) )
61 import Util ( panic, assertPanic {-pprTrace:ToDo:rm-} )
64 %************************************************************************
66 \subsection[CoreTopBinding_and_CoreBinding]{@CoreTopBinding@ and @GenCoreBinding@}
68 %************************************************************************
70 Core programs, bindings, expressions, etc., are parameterised with
71 respect to the information kept about binding and bound occurrences of
72 variables, called {\em binders} and {\em val_occ tyvar uvars}, respectively. [I
73 don't really like the pair of names; I prefer {\em binder} and {\em
74 bounder}. Or {\em binder} and {\em var}.]
76 A @GenCoreBinding@ is either a single non-recursive binding of a
77 ``binder'' to an expression, or a mutually-recursive blob of same.
79 data GenCoreBinding val_bdr val_occ tyvar uvar
80 = NonRec val_bdr (GenCoreExpr val_bdr val_occ tyvar uvar)
81 | Rec [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
85 bindersOf :: GenCoreBinding val_bdr val_occ tyvar uvar -> [val_bdr]
88 [GenCoreBinding val_bdr val_occ tyvar uvar] ->
89 [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
91 rhssOfBind :: GenCoreBinding val_bdr val_occ tyvar uvar -> [GenCoreExpr val_bdr val_occ tyvar uvar]
93 bindersOf (NonRec binder _) = [binder]
94 bindersOf (Rec pairs) = [binder | (binder, _) <- pairs]
96 pairsFromCoreBinds [] = []
97 pairsFromCoreBinds ((NonRec b e) : bs) = (b,e) : pairsFromCoreBinds bs
98 pairsFromCoreBinds ((Rec pairs) : bs) = pairs ++ pairsFromCoreBinds bs
100 rhssOfBind (NonRec _ rhs) = [rhs]
101 rhssOfBind (Rec pairs) = [rhs | (_,rhs) <- pairs]
104 %************************************************************************
106 \subsection[GenCoreExpr]{Core expressions: @GenCoreExpr@}
108 %************************************************************************
110 @GenCoreExpr@ is the heart of the ``core'' data types; it is
111 (more-or-less) boiled-down second-order polymorphic lambda calculus.
112 For types in the core world, we just keep using @Types@.
114 data GenCoreExpr val_bdr val_occ tyvar uvar
116 | Lit Literal -- literal constants
119 @Cons@ and @Prims@ are saturated constructor and primitive-op
120 applications (see the comment). Note: @Con@s are only set up by the
121 simplifier (and by the desugarer when it knows what it's doing). The
122 desugarer sets up constructors as applications of global @Vars@s.
125 | Con Id [GenCoreArg val_occ tyvar uvar]
126 -- Saturated constructor application:
127 -- The constructor is a function of the form:
128 -- /\ a1 -> ... /\ am -> \ b1 -> ... \ bn ->
129 -- <expr> where "/\" is a type lambda and "\" the
130 -- regular kind; there will be "m" Types and
131 -- "n" bindees in the Con args.
133 | Prim PrimOp [GenCoreArg val_occ tyvar uvar]
134 -- saturated primitive operation;
135 -- comment on Cons applies here, too.
138 Ye olde abstraction and application operators.
140 | Lam (GenCoreBinder val_bdr tyvar uvar)
141 (GenCoreExpr val_bdr val_occ tyvar uvar)
143 | App (GenCoreExpr val_bdr val_occ tyvar uvar)
144 (GenCoreArg val_occ tyvar uvar)
147 Case expressions (\tr{case <expr> of <List of alternatives>}): there
148 are really two flavours masquerading here---those for scrutinising
149 {\em algebraic} types and those for {\em primitive} types. Please see
150 under @GenCoreCaseAlts@.
152 | Case (GenCoreExpr val_bdr val_occ tyvar uvar)
153 (GenCoreCaseAlts val_bdr val_occ tyvar uvar)
156 A Core case expression \tr{case e of v -> ...} implies evaluation of
157 \tr{e}; it is not equivalent to \tr{let v = in ...} (as with a Haskell
160 Non-recursive @Lets@ only have one binding; having more than one
161 doesn't buy you much, and it is an easy way to mess up variable
164 | Let (GenCoreBinding val_bdr val_occ tyvar uvar)
165 (GenCoreExpr val_bdr val_occ tyvar uvar)
166 -- both recursive and non-.
167 -- The "GenCoreBinding" records that information
170 For cost centre scc expressions we introduce a new core construct
171 @SCC@ so transforming passes have to deal with it explicitly. The
172 alternative of using a new PrimativeOp may result in a bad
173 transformations of which we are unaware.
175 | SCC CostCentre -- label of scc
176 (GenCoreExpr val_bdr val_occ tyvar uvar) -- scc expression
179 Coercions arise from uses of the constructor of a @newtype@
180 declaration, either in construction (resulting in a @CoreceIn@) or
181 pattern matching (resulting in a @CoerceOut@).
185 (GenType tyvar uvar) -- Type of the whole expression
186 (GenCoreExpr val_bdr val_occ tyvar uvar)
190 data Coercion = CoerceIn Id -- Apply this constructor
191 | CoerceOut Id -- Strip this constructor
195 %************************************************************************
197 \subsection{Core-constructing functions with checking}
199 %************************************************************************
201 When making @Lets@, we may want to take evasive action if the thing
202 being bound has unboxed type. We have different variants ...
204 @mkCoLet(s|rec)Any@ let-binds any binding, regardless of type
205 @mkCoLet(s|rec)NoUnboxed@ prohibits unboxed bindings
206 @mkCoLet(s)UnboxedToCase@ converts an unboxed binding to a case
207 (unboxed bindings in a letrec are still prohibited)
210 mkCoLetAny :: GenCoreBinding Id Id tyvar uvar
211 -> GenCoreExpr Id Id tyvar uvar
212 -> GenCoreExpr Id Id tyvar uvar
213 mkCoLetsAny :: [GenCoreBinding Id Id tyvar uvar] ->
214 GenCoreExpr Id Id tyvar uvar ->
215 GenCoreExpr Id Id tyvar uvar
217 mkCoLetrecAny :: [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
218 -> GenCoreExpr val_bdr val_occ tyvar uvar
219 -> GenCoreExpr val_bdr val_occ tyvar uvar
221 mkCoLetrecAny [] body = body
222 mkCoLetrecAny binds body = Let (Rec binds) body
224 mkCoLetsAny [] expr = expr
225 mkCoLetsAny binds expr = foldr mkCoLetAny expr binds
227 mkCoLetAny bind@(Rec binds) body = mkCoLetrecAny binds body
228 mkCoLetAny bind@(NonRec binder rhs) body
230 Var binder2 | binder == binder2
231 -> rhs -- hey, I have the rhs
237 mkCoLetNoUnboxed bind@(Rec binds) body
238 = mkCoLetrecNoUnboxed binds body
240 mkCoLetNoUnboxed bind@(NonRec binder rhs) body
241 = --ASSERT (not (isUnboxedType (idType binder)))
243 Var binder2 | binder == binder2
244 -> rhs -- hey, I have the rhs
248 mkCoLetsNoUnboxed [] expr = expr
249 mkCoLetsNoUnboxed binds expr = foldr mkCoLetNoUnboxed expr binds
251 mkCoLetrecNoUnboxed [] body = body
252 mkCoLetrecNoUnboxed binds body
253 = ASSERT (all is_boxed_bind binds)
256 is_boxed_bind (binder, rhs)
257 = (not . isUnboxedType . idType) binder
261 mkCoLetUnboxedToCase bind@(Rec binds) body
262 = mkCoLetrecNoUnboxed binds body
264 mkCoLetUnboxedToCase bind@(NonRec binder rhs) body
266 Var binder2 | binder == binder2
267 -> rhs -- hey, I have the rhs
269 -> if (not (isUnboxedType (idType binder))) then
270 Let bind body -- boxed...
272 Case rhs -- unboxed...
274 (BindDefault binder body))
276 mkCoLetsUnboxedToCase [] expr = expr
277 mkCoLetsUnboxedToCase binds expr = foldr mkCoLetUnboxedToCase expr binds
280 %************************************************************************
282 \subsection{Case alternatives in @GenCoreExpr@}
284 %************************************************************************
286 We have different kinds of @case@s, the differences being reflected in
287 the kinds of alternatives a case has. We maintain a distinction
288 between cases for scrutinising algebraic datatypes, as opposed to
289 primitive types. In both cases, we carry around a @TyCon@, as a
290 handle with which we can get info about the case (e.g., total number
291 of data constructors for this type).
299 Case e [ BindDefaultAlt x -> b ]
303 data GenCoreCaseAlts val_bdr val_occ tyvar uvar
304 = AlgAlts [(Id, -- alts: data constructor,
305 [val_bdr], -- constructor's parameters,
306 GenCoreExpr val_bdr val_occ tyvar uvar)] -- rhs.
307 (GenCoreCaseDefault val_bdr val_occ tyvar uvar)
309 | PrimAlts [(Literal, -- alts: unboxed literal,
310 GenCoreExpr val_bdr val_occ tyvar uvar)] -- rhs.
311 (GenCoreCaseDefault val_bdr val_occ tyvar uvar)
313 -- obvious things: if there are no alts in the list, then the default
314 -- can't be NoDefault.
316 data GenCoreCaseDefault val_bdr val_occ tyvar uvar
317 = NoDefault -- small con family: all
318 -- constructor accounted for
319 | BindDefault val_bdr -- form: var -> expr;
320 (GenCoreExpr val_bdr val_occ tyvar uvar) -- "val_bdr" may or may not
325 rhssOfAlts (AlgAlts alts deflt) = rhssOfDeflt deflt ++ [rhs | (_,_,rhs) <- alts]
326 rhssOfAlts (PrimAlts alts deflt) = rhssOfDeflt deflt ++ [rhs | (_,rhs) <- alts]
328 rhssOfDeflt NoDefault = []
329 rhssOfDeflt (BindDefault _ rhs) = [rhs]
332 %************************************************************************
334 \subsection{Core binders}
336 %************************************************************************
339 data GenCoreBinder val_bdr tyvar uvar
344 isValBinder (ValBinder _) = True
345 isValBinder _ = False
347 notValBinder = not . isValBinder
350 Clump Lams together if possible.
353 mkValLam :: [val_bdr]
354 -> GenCoreExpr val_bdr val_occ tyvar uvar
355 -> GenCoreExpr val_bdr val_occ tyvar uvar
357 -> GenCoreExpr val_bdr val_occ tyvar uvar
358 -> GenCoreExpr val_bdr val_occ tyvar uvar
360 -> GenCoreExpr val_bdr val_occ tyvar uvar
361 -> GenCoreExpr val_bdr val_occ tyvar uvar
363 mkValLam binders body = foldr (Lam . ValBinder) body binders
364 mkTyLam binders body = foldr (Lam . TyBinder) body binders
365 mkUseLam binders body = foldr (Lam . UsageBinder) body binders
367 mkLam :: [tyvar] -> [val_bdr] -- ToDo: could add a [uvar] arg...
368 -> GenCoreExpr val_bdr val_occ tyvar uvar
369 -> GenCoreExpr val_bdr val_occ tyvar uvar
371 mkLam tyvars valvars body
372 = mkTyLam tyvars (mkValLam valvars body)
375 We often want to strip off leading lambdas before getting down to
376 business. @collectBinders@ is your friend.
378 We expect (by convention) usage-, type-, and value- lambdas in that
383 GenCoreExpr val_bdr val_occ tyvar uvar ->
384 ([uvar], [tyvar], [val_bdr], GenCoreExpr val_bdr val_occ tyvar uvar)
389 usages (Lam (UsageBinder u) body) uacc = usages body (u:uacc)
391 = case (tyvars other []) of { (tacc, vacc, expr) ->
392 (reverse uacc, tacc, vacc, expr) }
394 tyvars (Lam (TyBinder t) body) tacc = tyvars body (t:tacc)
396 = ASSERT(not (usage_lambda other))
397 case (valvars other []) of { (vacc, expr) ->
398 (reverse tacc, vacc, expr) }
400 valvars (Lam (ValBinder v) body) vacc = valvars body (v:vacc)
402 = ASSERT(not (usage_lambda other))
403 ASSERT(not (tyvar_lambda other))
404 (reverse vacc, other)
406 ---------------------------------------
407 usage_lambda (Lam (UsageBinder _) _) = True
408 usage_lambda _ = False
410 tyvar_lambda (Lam (TyBinder _) _) = True
411 tyvar_lambda _ = False
414 %************************************************************************
416 \subsection{Core arguments (atoms)}
418 %************************************************************************
421 data GenCoreArg val_occ tyvar uvar
424 | TyArg (GenType tyvar uvar)
425 | UsageArg (GenUsage uvar)
428 General and specific forms:
430 mkGenApp :: GenCoreExpr val_bdr val_occ tyvar uvar
431 -> [GenCoreArg val_occ tyvar uvar]
432 -> GenCoreExpr val_bdr val_occ tyvar uvar
433 mkTyApp :: GenCoreExpr val_bdr val_occ tyvar uvar
434 -> [GenType tyvar uvar]
435 -> GenCoreExpr val_bdr val_occ tyvar uvar
436 mkUseApp :: GenCoreExpr val_bdr val_occ tyvar uvar
438 -> GenCoreExpr val_bdr val_occ tyvar uvar
439 mkValApp :: GenCoreExpr val_bdr val_occ tyvar uvar
440 -> [GenCoreArg val_occ tyvar uvar] -- but we ASSERT they are LitArg or VarArg
441 -> GenCoreExpr val_bdr val_occ tyvar uvar
443 mkGenApp f args = foldl App f args
444 mkTyApp f args = foldl (\ e a -> App e (TyArg a)) f args
445 mkUseApp f args = foldl (\ e a -> App e (UsageArg a)) f args
446 mkValApp f args = foldl (\ e a -> App e (is_Lit_or_Var a)) f args
452 = if isValArg a then a else panic "CoreSyn.mkValApps:not LitArg or VarArg"
455 isValArg (LitArg _) = True -- often used for sanity-checking
456 isValArg (VarArg _) = True
459 notValArg = not . isValArg -- exists only because it's a common use of isValArg
461 numValArgs as = length [ a | a <- as, isValArg a ] -- again, convenience
465 mkApp fun = mk_thing (mkGenApp fun)
466 mkCon con = mk_thing (Con con)
467 mkPrim op = mk_thing (Prim op)
469 mk_thing thing uses tys vals
470 = thing (map UsageArg uses ++ map TyArg tys ++ map is_Lit_or_Var vals)
473 @collectArgs@ takes an application expression, returning the function
474 and the arguments to which it is applied.
477 collectArgs :: GenCoreExpr val_bdr val_occ tyvar uvar
478 -> (GenCoreExpr val_bdr val_occ tyvar uvar,
480 [GenType tyvar uvar],
481 [GenCoreArg val_occ tyvar uvar]{-ValArgs-})
486 valvars (App fun v) vacc | isValArg v = valvars fun (v:vacc)
488 = case (tyvars fun []) of { (expr, uacc, tacc) ->
489 (expr, uacc, tacc, vacc) }
491 tyvars (App fun (TyArg t)) tacc = tyvars fun (t:tacc)
493 = case (usages fun []) of { (expr, uacc) ->
496 usages (App fun (UsageArg u)) uacc = usages fun (u:uacc)
501 %************************************************************************
503 \subsection{The main @Core*@ instantiation of the @GenCore*@ types}
505 %************************************************************************
508 type CoreBinding = GenCoreBinding Id Id TyVar UVar
509 type CoreExpr = GenCoreExpr Id Id TyVar UVar
510 type CoreBinder = GenCoreBinder Id TyVar UVar
511 type CoreArg = GenCoreArg Id TyVar UVar
513 type CoreCaseAlts = GenCoreCaseAlts Id Id TyVar UVar
514 type CoreCaseDefault = GenCoreCaseDefault Id Id TyVar UVar
517 %************************************************************************
519 \subsection{The @TaggedCore*@ instantiation of the @GenCore*@ types}
521 %************************************************************************
523 Binders are ``tagged'' with a \tr{t}:
525 type Tagged t = (Id, t)
527 type TaggedCoreBinding t = GenCoreBinding (Tagged t) Id TyVar UVar
528 type TaggedCoreExpr t = GenCoreExpr (Tagged t) Id TyVar UVar
529 type TaggedCoreBinder t = GenCoreBinder (Tagged t) TyVar UVar
530 type TaggedCoreArg t = GenCoreArg Id TyVar UVar
532 type TaggedCoreCaseAlts t = GenCoreCaseAlts (Tagged t) Id TyVar UVar
533 type TaggedCoreCaseDefault t = GenCoreCaseDefault (Tagged t) Id TyVar UVar
536 %************************************************************************
538 \subsection{The @SimplifiableCore*@ instantiation of the @GenCore*@ types}
540 %************************************************************************
542 Binders are tagged with @BinderInfo@:
544 type Simplifiable = (Id, BinderInfo)
546 type SimplifiableCoreBinding = GenCoreBinding Simplifiable Id TyVar UVar
547 type SimplifiableCoreExpr = GenCoreExpr Simplifiable Id TyVar UVar
548 type SimplifiableCoreBinder = GenCoreBinder Simplifiable TyVar UVar
549 type SimplifiableCoreArg = GenCoreArg Id TyVar UVar
551 type SimplifiableCoreCaseAlts = GenCoreCaseAlts Simplifiable Id TyVar UVar
552 type SimplifiableCoreCaseDefault = GenCoreCaseDefault Simplifiable Id TyVar UVar